Giáo trình Cấu trúc dữ liệu và giải thuật

anh sách 
2. Các phép toán trên danh sách 
3. Danh sách đặc (Condensed List) 
3.1. Định nghĩa 
3.2. Biểu diễn và Các thao tác 
const int MaxLen = 10000; // hoặc: #define MaxLen 10000 
int Length; 
T CD_LIST[MaxLen]; // hoặc: T * CD_LIST = new T[MaxLen]; 
3.3. Ưu nhược điểm và Ứng dụng 
4. Danh sách liên kết (Linked List) 
4.1. Định nghĩa 
4.2. Danh sách liên kết đơn (Singly Linked List) 
typedef struct SLL_Node 
{ T Key; 
SLL_Node * NextNode; 
} SLL_OneNode; 
typedef SLL_OneNode * SLL_Type; 
4.3. Danh sách liên kết kép (Doubly Linked List) 
typedef struct DLL_Node 
{ T Key; 
DLL_Node * NextNode; 
DLL_Node * PreNode; 
} DLL_OneNode; 
typedef DLL_OneNode * DLL_Type; 
4.4. Ưu nhược điểm của danh sách liên kết 
5. Danh sách hạn chế 
5.1. Hàng đợi (Q ueue) 
typedef struct Q_C 
Giáo trình: Cấu Trúc Dữ Liệu và Giải Thuật 
 Trang: 226 
{ int Len; // Chiều dài hàng đợi 
int Front, Rear; 
T * List; // Nội dung hàng đợi 
} C_QUEUE; 
C_QUEUE CQ_List; 
5.2. Ngăn xếp (Stack) 
typedef struct S_C 
{ int Size; // Kích thước ngăn xếp 
int SP; 
T * List; // Nội dung ngăn xếp 
} C_STACK; 
C_STACK CS_List; 
Chương 5: Cây (Tree) 
1. Các khái niệm 
2. Cây nhị phân (Binary tree) 
2.1. Định nghĩa 
2.2. Biểu diễn và Các thao tác 
typedef struct BinT_Node 
{ T Key; 
BinT_Node * BinT_Left; 
BinT_Node * BinT_Right; 
} BinT_OneNode; 
typedef BinT_OneNode * BinT_Type; 
2.3. Cây nhị phân tìm kiếm (Binary Searching Tree) 
typedef struct BST_Node 
{ T Key; 
BST_Node * BST_Left; 
BST_Node * BST_Right; 
} BST_OneNode; 
typedef BST_OneNode * BST_Type; 
3. Cây cân bằng (Balanced tree) 
3.1. Định nghĩa 
typedef struct BAL_Node 
{ T Key; 
int Bal; 
BAL_Node * BAL_Left; 
BAL_Node * BAL_Right; 
} BAL_OneNode; 
typedef BAL_OneNode * BAL_Type; 
3.2. Các thao tác 
Giáo trình: Cấu Trúc Dữ Liệu và Giải Thuật 
 Trang: 227 
Câu hỏi và Bài tập ôn tập tổng hợp 
1. Phân biệt về cấu trúc dữ liệu, ý nghĩa và tác dụng giữa: danh sách liên kết đôi, danh 
sách đa liên kết có hai mối liên kết và cây nhị phân? 
2. Hãy sử dụng cấu trúc dữ liệu thích hợp để lưu trữ các số nguyên có dấu có giá trị 
tuyệt đối quá lớn trong bộ nhớ trong của máy tính. Với cấu trúc dữ liệu này, hãy 
trình bày thuật toán và cài đặt chương trình thực hiện việc cộng, trừ, nhân, chia 
nguyên, lấy dư, so sánh các số nguyên có giá trị lớn này. 
3. Hãy sử dụng cấu trúc dữ liệu thích hợp để lưu trữ độ dài đường đi giữa các Thành 
phố với nhau trong một quốc gia vào trong bộ nhớ trong của máy tính. Với cấu trúc 
dữ liệu này, hãy trình bày thuật toán và cài đặt chương trình thực hiện việc liệt kê tất 
cả các đường đi từ Thành phố A đến Thành phố B? Đường đi nào là đường đi ngắn 
nhất? 
4. Các văn bản được lưu trữ thành từng dòng trên các file văn bản, mỗi dòng có chiều 
dài không quá 127 ký tự. Hãy đề xuất cấu trúc dữ liệu thích hợp để lưu trữ trong bộ 
nhớ trong của máy tính tần suất xuất hiện của các từ trong tập tin văn bản này. Với 
cấu trúc dữ liệu này, hãy trình bày thuật toán và cài đặt chương trình thực hiện việc 
thống kê xem các từ trong file văn bản xuất hiện với tần suất như thế nào? Cho biết 
văn bản có bao nhiêu t ừ, bao nhiêu tên từ? 
5. Các văn bản được lưu trữ thành từng dòng trên các file văn bản, mỗi dòng có chiều 
dài không quá 127 ký tự. Hãy đề xuất cấu trúc dữ liệu thích hợp để lưu trữ trong bộ 
nhớ trong của máy tính các dòng văn bản trong tập tin văn bản này (có thể bộ nhớ 
không đủ để lưu toàn bộ nội dung tập tin văn bản này vào trong bộ nhớ trong của 
máy tính). Với cấu trúc dữ liệu này, hãy trình bày thuật toán và cài đặt chương trình 
thực hiện việc hiện nội tập tin văn bản này theo từng trang màn hình sao cho chúng 
ta có thể sử dụng các phím PgUp/PgDn để lật lên/xuống theo từng trang màn hình và 
sử dụng các phím Up-arrow/Down-arrow để cho trôi lên/xuống từng dòng văn bản 
trên màn hình? Cho biết văn bản có bao nhiêu dòng? 
6. Hãy sử dụng cấu trúc dữ liệu thích hợp để lưu trữ các ma trận thưa (ma trận mà chủ 
yếu giá trị các phần tử bằng 0) trong bộ nhớ trong của máy tính. Với cấu trúc dữ liệu 
này, hãy trình bày thuật toán và cài đặt chương trình thực hiện việc cộng, trừ, nhân 
hai ma trận thưa với nhau, tạo ma trận thưa chuyển vị từ một ma trận thưa khác. 
7. Hãy sử dụng cấu trúc dữ liệu thích hợp để lưu trữ Gia phả của một dòng họ nào đó 
trong bộ nhớ trong của máy tính. Với cấu trúc dữ liệu này, hãy trình bày thuật toán 
và cài đặt chương trình thực hiện việc kiểm tra xem 02 người có tên là X và Y có 
phải là hai anh em ruột hay không? Nếu không phải thì ai có “vai vế” cao hơn? Giả 
sử rằng mỗi cặp vợ chồng có không quá 05 người con. 
8. Hãy sử dụng cấu trúc dữ liệu thích hợp để lưu trữ một hệ thống Menu có nhiều mục 
chọn, nhiều cấp trong bộ nhớ trong của máy tính. Với cấu trúc dữ liệu này, hãy trình 
bày thuật toán và cài đặt chương trình thực hiện việc cho menu xuất hiện trên màn 
hình và cho phép người sử dụng chọn một chức năng nào đó của menu. 
9. Kết hợp cấu trúc dữ liệu ở trong bài tập và 4, 5 và 8. Hãy trình bày thuật toán và cài 
đặt chương trình thực hiện các chức năng của một phần mềm soạn thảo văn bản 
đơn giản? 
Giáo trình: Cấu Trúc Dữ Liệu và Giải Thuật 
 Trang: 228 
10. Hãy sử dụng cấu trúc dữ liệu thích hợp để lưu trữ các từ của một từ điển vào trong 
tập tin có tên DICT.DAT. Thông tin giải nghĩa về một từ bao gồm: Tên từ, Loại từ 
(Danh từ, động từ, tính từ, …), nghĩa tiếng Việt. 
a) Sử dụng tập tin chỉ mục để liệt kê các từ theo thứ tự Alphabet (A -> Z). 
b) Hãy đề xuất cấu trúc dữ liệu thích hợp để lưu trữ trong bộ nhớ trong của máy tính 
thông tin giải nghĩa của các từ trong tập tin DICT.DAT này (có thể bộ nhớ không 
đủ để lưu toàn bộ nội dung tập tin DICT.DAT này vào trong bộ nhớ trong của máy 
tính). Với cấu trúc dữ liệu này, hãy trình bày thuật toán và cài đặt chương trình 
thực hiện việc tra nghĩa cho một từ. Ngoài ra, ta có thể sử dụng các phím 
PgUp/PgDn để lật lên/xuống theo từng trang (do mình quy định) màn hình và sử 
dụng các phím Up-arrow/Down-arrow để cho trôi lên/xuống từng từ trên màn 
hình? Sử dụng cấu trúc dữ liệu thích hợp để lưu trữ trong bộ nhớ trong các từ đã 
được tra nghĩa. 
11. Người ta lưu trữ các hệ số của một đa thức bậc n thành các dòng văn bản trong file 
DATHUC.DAT theo nguyên tắc: Mỗi dòng là hệ số và số mũ của 1 đa thức và các hệ 
số và số mũ này cách nhau ít nhất là một khoảng trắng. 
Hãy sử dụng cấu trúc dữ liệu thích hợp để lưu trữ một đa thức vào trong bộ nhớ 
trong của máy tính. Với cấu trúc dữ liệu này, hãy trình bày thuật toán và cài đặt 
chương trình thực hiện các công việc sau: 
- Xuất các đa thức trong file DATHUC.DAT ra màn hình; 
- Tính đa thức tổng, đa thức hiệu của các đa t hức này; 
- Tính đa thức tích của các đa thức này. 
12. Một hình vuông có độ dài cạnh là a được tô 02 màu: trắng và đen. Người ta tiến 
hành chia hình vuông này thành 04 hình vuông con đều nhau và ghi nhận vị trí của 
chúng trong hình vuông lớn. Nếu trong mỗi hình vuông con chỉ gồm toàn màu trắng 
hoặc màu đen thì giữ nguyên, còn nếu trong hình vuông con còn có 02 màu thì tiếp 
tục chia hình vuông con này thành 04 hình vuông con nhỏ hơn và ghi nhận vị trí, …, 
cứ như vậy sau một số hữu hạn phép chia sẽ kết thúc việc chia. Hãy sử dụng cấu 
trúc dữ liệu thích hợp để lưu trữ các hình vuông này vào trong bộ nhớ trong của máy 
tính. Với cấu trúc dữ liệu lựa chọn, hãy trình bày thuật toán và cài đặt chương trình 
thực hiện các công việc sau: 
- Tính tổng số hình vuông tạo thành qua các lần chia. 
- Tính tổng số hình vuông màu trắng, màu đen và tổng diện tích tương ứng của 
chúng. 
- Tái tạo lại hình vuông ban đầu. 
13. Định nghĩa cấu trúc dữ liệu thích hợp để lưu trữ các giá trị trong tam giác Pascal 
vào trong bộ nhớ trong của máy tính. Với cấu trúc dữ liệu này hãy trình bày thuật 
toán và viết chương trình thực hiện các công việc sau: 
- In tam giác Pascal có N dòng ra màn hình. 
- In và tính giá trị biểu thức (a+b)N ra màn hình. 
14. Trình bày thuật toán và viết chương trình thực hiện công việc minh họa (Demo) quá 
trình thực hiện tất cả các thuật toán đã học. 
Giáo trình: Cấu Trúc Dữ Liệu và Giải Thuật 
 Trang: 229 
IV. HƯỚNG DẪN SỬ DỤNG TÀI LIỆU THAM KHẢO 
1. Cấu trúc dữ liệu 
Tác giả: Nguyễn Trung Trực 
Khoa CNTT, trường ĐHBK TP.HCM 
2. Giáo trình Cấu trúc dữ liệu 1 
Tác giả: Trần Hạnh Nhi – Dương Anh Đức 
Khoa CNTT, trường ĐHKHTN – ĐHQG TP.HCM 
3. Algorithms + Data Structures = Programs 
Tác giả: N.Wirth 
NXB: Prentice Hall, 1976 
4. Data Structures and Algorithms 
Tác giả: Alfred V.Aho - John E.Hopcroft – Jeffrey D.Ullman 
NXB: Addison-Wesley Publishing Company 
5. Algorithms (Second Edition) 
Tác giả: Robert Sedgewick 
NXB: Addison-Wesley Publishing Company 
6. Data Structures and Program Design (Third Edition) 
Tác giả: Robert L.Kruse 
NXB: Prentice Hall