Cấu trúc dữ liệu và giải thuật - 18 chương chi tiết

Phần 1 – PHẦN MỞ ĐẦUChương 1 – GIỚI THIỆU
1.1. Về phương pháp phân tích thiết kế hướng đối tượng...............................1
1.2. Giới thiệu môn học Cấu trúc dữ liệu (CTDL) và giải thuật .....................1
1.3. Cách tiếp cận trong quá trình tìm hiểu các lớp CTDL ............................4
1.3.1. Các bước trong quá trình phân tích thiết kế hướng đối tượng.........4
1.3.2. Quá trình xây dựng các lớp CTDL.............................................. ........5
1.4. Một số định nghĩa cơ bản .................................................. .........................6
1.4.1. Định nghĩa kiểu dữ liệu .................................................. .....................6
1.4.2. Kiểu nguyên tố và các kiểu có cấu trúc............................................. ..6
1.4.3. Chuỗi nối tiếp và danh sách............................................. ...................6
1.4.4. Các kiểu dữ liệu trừu tượng.......................................... ........................7
1.5. Một số nguyên tắc và phương pháp để học tốt môn CTDL và giải
thuật........................................... .................................................. .................8
1.5.1. Cách tiếp cận và phương hướng suy nghĩ tích cực ............................8
1.5.2. Các nguyên tắc........................................... .. .........................................9
1.5.3. Phong cách lập trình (style of programming) và các kỹ năng:.......10
1.6. Giới thiệu về ngôn ngữ giả: .................................................. ....................14
Phần 2 – CÁC CẤU TRÚC DỮ LIỆU
Chương 2 – NGĂN XẾP
2.1. Định nghĩa ngăn xếp........................................... .. ....................................17
2.2. Đặc tả ngăn xếp........................................... .. ............................................18
2.3. Các phương án hiện thực ngăn xếp........................................... .. .............22
2.4. Hiện thực ngăn xếp .................................................. .................................22
2.4.1. Hiện thực ngăn xếp liên tục .................................................. ............22
2.4.2. Hiện thực ngăn xếp liên kết........................................... .. .................25
2.4.3. Ngăn xếp liên kết với sự an toàn............................................. .........29
2.4.4. Đặc tả ngăn xếp liên kết đã hiệu chỉnh.......................................... . 34


Chương 3 – HÀNG ĐỢI
3.1. Định nghĩa hàng .................................................. ..................................... 37
3.2. Đặc tả hàng .................................................. ............................................. 38
3.3. Các phương án hiện thực hàng .................................................. .............. 41
3.3.1. Các phương án hiện thực hàng liên tục ........................................... 41
3.3.2. Phương án hiện thực hàng liên kết........................................... .. ..... 45
3.4. Hiện thực hàng............................................. ............................................. 46
3.4.1. Hiện thực hàng liên tục........................................... .. ........................ 46
3.4.2. Hiện thực hàng liên kết .................................................. .................. 48
3.4.3. Hàng liên kết mở rộng .................................................. .................... 50
Chương 4 – DANH SÁCH
4.1. Định nghĩa danh sách .................................................. ............................ 51
4.2. Đặc tả các phương thức cho danh sách .................................................. . 51
4.3. Hiện thực danh sách............................................. .................................... 54
4.3.1. Hiện thực danh sách liên tục........................................... .. ............... 54
4.3.2. Hiện thực danh sách liên kết đơn giản ........................................... 56
4.3.3. Lưu lại vị trí hiện tại........................................... .. ............................ 61
4.3.4. Danh sách liên kết kép .................................................. ................... 63
4.4. So sánh các cách hiện thực của danh sách ............................................. 66
4.5. Danh sách liên kết trong mảng liên tục ................................................. 67
4.5.1. Phương pháp............................................. .......................................... 67
4.5.2. Các tác vụ quản lý vùng nhớ............................................ . ................ 70
4.5.3. Các tác vụ khác .................................................. ................................ 73
4.5.4. Các biến thể của danh sách liên kết trong mảng liên tục ............. 74
Chương 5 – CHUỖI KÝ TƯ
5.1. Chuỗi ký tự trong C và trong C++............................................... ............ 75
5.2. Đặc tả của lớp String............................................ .................................... 77
5.2.1. Các phép so sánh .................................................. ............................. 77
5.2.2. Một số constructor tiện dụng .................................................. .......... 77
5.3. Hiện thực lớp String............................................ ..................................... 79
5.4. Các tác vụ trên String .................................................. ............................ 81
5.5. Các giải thuật tìm một chuỗi con trong một chuỗi................................. 83
5.5.1. Giải thuật Brute-Force .................................................. .................... 83
5.5.2. Giải thuật Knuth-Morris-Pratt .................................................. ....... 85


Chương 6 – ĐỆ QUY
6.1. Giới thiệu về đệ quy .................................................. ................................91
6.1.1. Cơ cấu ngăn xếp cho các lần gọi hàm.............................................. .91
6.1.2. Cây biểu diễn các lần gọi hàm .................................................. ........92
6.1.3. Giai thừa: Một định nghĩa đệ quy............................................... ......93
6.1.4. Chia để trị: Bài toán Tháp Hà Nội .................................................. .95
6.2. Các nguyên tắc của đệ quy............................................... .......................100
6.2.1. Thiết kế giải thuật đệ quy .................................................. .............100
6.2.2. Cách thực hiện của đệ quy............................................... ................102
6.2.3. Đệ quy đuôi .................................................. .....................................104
6.2.4. Phân tích một số trường hợp nên và không nên dùng đệ quy .....106
6.2.5. Các nhận xét.............................................. .......................................110
6.3. Phương pháp quay lui (backtracking).................................... .................112
6.3.1. Lời giải cho bài toán tám con hậu .................................................. 112
6.3.2. Ví dụ với bốn con Hậu........................................... .. .........................114
6.3.3. Phương pháp quay lui (Backtracking) .............................................115
6.3.4. Phác thảo chung cho chương trình đặt các con hậu lên bàn cờ ...115
6.3.5. Tinh chế: Cấu trúc dữ liệu đầu tiên và các phương thức...............118
6.3.6. Xem xét lại và tinh chế .................................................. .................120
6.3.7. Phân tích về phương pháp quay lui ................................................12 4
6.4. Các chương trình có cấu trúc cây: dự đoán trước trong các trò chơi ...127
6.4.1. Các cây trò chơi .................................................. ..............................127
6.4.2. Phương pháp Minimax........................................... ..........................128
6.4.3. Phát triển giải thuật .................................................. ......................130
6.4.4. Tinh chế .................................................. ..........................................131
6.4.5. Tic-Tac-Toe............................................... .........................................132
Chương 7 – TÌM KIẾM
7.1. Giới thiệu........................................... .................................................. .....137
7.1.1. Khóa............................................. .................................................. ....137
7.1.2. Phân tích............................................. ..............................................137
7.1.3. Tìm kiếm nội và tìm kiếm ngoại .................................................. ..137
7.1.4. Lớp Record và lớp Key............................................... ......................138
7.1.5. Thông số............................................ .. ..............................................139
7.2. Tìm kiếm tuần tự............................................ .. .......................................139
7.2.1. Giải thuật và hàm.............................................. .............................. 139
7.2.2. Phân tích .................................................. ........................................ 140
7.3. Tìm kiếm nhị phân............................................. .................................... 141
7.3.1. Danh sách có thứ tự............................................ .. ........................... 142
7.3.2. Xây dựng giải thuật .................................................. ....................... 143
7.3.3. Phiên bản thứ nhất........................................... . .............................. 143
7.3.4. Nhận biết sớm phần tử có chứa khóa đích.................................... 145
7.4. Cây so sánh .................................................. ........................................... 147
Chương 8 – SẮP XẾP
8.1. Giới thiệu .................................................. ............................................... 149
8.2. Sắp xếp kiểu chèn (Insertion Sort)............................................. ........... 150
8.2.1. Chèn phần tử vào danh sách đã có thứ tự..................................... 150
8.2.2. Sắp xếp kiểu chèn cho danh sách liên tục..................................... 151
8.2.3. Sắp xếp kiểu chèn cho danh sách liên kết .................................... 153
8.3. Sắp xếp kiểu chọn (Selection Sort)............................................. ........... 155
8.3.1. Giải thuật........................................... ............................................... 155
8.3.2. Sắp xếp chọn trên danh sách liên tục........................................... . 156
8.4. Shell_sort........................................ .................................................. ....... 158
8.5. Các phương pháp sắp xếp theo kiểu chia để trị ................................... 160
8.5.1. Ý tưởng cơ bản .................................................. ............................... 160
8.5.2. Ví dụ............................................ .. .................................................. .. 161
8.6. Merge_sort cho danh sách liên kết .................................................. ..... 164
8.7. Quick_sort cho danh sách liên tục........................................... .. ............ 167
8.7.1. Các hàm .................................................. .......................................... 167
8.7.2. Phân hoạch danh sách .................................................. .................. 168
8.8. Heap và Heap_sort......................................... ......................................... 170
8.8.1. Định nghĩa heap nhị phân............................................. ................. 171
8.8.2. Phát triển giải thuật Heap_sort .................................................. ... 172
8.9. Radix Sort.............................................. .................................................. 176
8.9.1. Ý tưởng.......................................... .................................................. .. 177
8.9.2. Hiện thực .................................................. ........................................ 177
8.9.3. Phân tích phương pháp radix_sort........................................ ......... 181
Chương 9 – CÂY NHỊ PHÂN
9.1. Các khái niệm cơ bản về cây .................................................. ............... 183
9.2. Cây nhị phân .................................................. .........................................185
9.2.1. Các định nghĩa............................................ ......................................185
9.2.2. Duyệt cây nhị phân .................................................. ........................187
9.2.3. Hiện thực liên kết của cây nhị phân ..............................................193
9.3. Cây nhị phân tìm kiếm........................................... . ...............................197
9.3.1. Các danh sách có thứ tự và các cách hiện thực .............................198
9.3.2. Tìm kiếm trên cây.............................................. ..............................199
9.3.3. Thêm phần tử vào cây nhị phân tìm kiếm ....................................203
9.3.4. Sắp thứ tự theo cây .................................................. ........................206
9.3.5. Loại phần tử trong cây nhị phân tìm kiếm ...................................207
9.4. Xây dựng một cây nhị phân tìm kiếm .................................................. .210
9.4.1. Thiết kế giải thuật .................................................. .........................212
9.4.2. Các khai báo và hàm main.............................................. ................213
9.4.3. Thêm một nút .................................................. .................................214
9.4.4. Hoàn tất công việc........................................... . ................................215
9.4.5. Đánh giá.............................................. ..............................................217
9.5. Cân bằng chiều cao: Cây AVL............................................... .................218
9.5.1. Định nghĩa .................................................. ......................................218
9.5.2. Thêm một nút .................................................. .................................222
9.5.3. Loại một nút .................................................. ...................................230
9.5.4. Chiều cao của cây AVL............................................... ......................234
Chương 10 – CÂY NHIỀU NHÁNH
10.1. Vườn cây, cây, và cây nhị phân............................................. .................237
10.1.1. Các tên gọi cho cây.............................................. .............................237
10.1.2. Cây có thứ tự............................................ .. .......................................239
10.1.3. Rừng và vườn .................................................. ..................................241
10.1.4. Sự tương ứng hình thức........................................... . ........................243
10.1.5. Phép quay.............................................. ............................................244
10.1.6. Tổng kết .................................................. ..........................................244
10.2. Cây từ điển tìm kiếm: Trie .................................................. ...................245
10.2.1. Tries............................................. .................................................. ....245
10.2.2. Tìm kiếm một khóa .................................................. ........................245
10.2.3. Giải thuật C++............................................... ...................................246
10.2.4. Tìm kiếm trong cây Trie.............................................. ....................247
10.2.5. Thêm phần tử vào Trie .................................................. ..................247
10.2.6. Loại phần tử trong Trie .................................................. .................248
10.2.7. Truy xuất Trie .................................................. ................................ 248
10.3. Tìm kiếm ngoài: B-tree .................................................. ........................ 249
10.3.1. Thời gian truy xuất .................................................. ........................ 249
10.3.2. Cây tìm kiếm nhiều nhánh............................................ ................. 250
10.3.3. Cây nhiều nhánh cân bằng .................................................. ........... 250
10.3.4. Thêm phần tử vào B-tree .................................................. .............. 251
10.3.5. Giải thuật C++: tìm kiếm và thêm vào.......................................... 253
10.3.6. Loại phần tử trong B-tree .................................................. ............. 263
10.4. Cây đỏ-đen .................................................. ............................................. 271
10.4.1. Dẫn nhập .................................................. ........................................ 271
10.4.2. Định nghĩa và phân tích .................................................. ............... 272
10.4.3. Đặc tả cây đỏ đen........................................... ... ............................... 274
10.4.4. Thêm phần tử............................................ .. ..................................... 276
10.4.5. Phương thức thêm vào. Hiện thực .................................................. 279
10.4.6. Loại một nút.............................................. ....................................... 282
Chương 11 – HÀNG ƯU TIÊN
11.1. Định nghĩa hàng ưu tiên .................................................. ...................... 283
11.2. Các phương án hiện thực hàng ưu tiên ................................................. 283
11.3. Hiện thực các tác vụ cơ bản trên heap nhị phân ................................. 284
11.3.1. Tác vụ thêm phần tử .................................................. ..................... 284
11.3.2. Tác vụ loại phần tử .................................................. ........................ 286
11.4. Các tác vụ khác trên heap nhị phân............................................. ........ 287
11.4.1. Tác vụ tìm phần tử lớn nhất........................................... . ............... 287
11.4.2. Tác vụ tăng giảm độ ưu tiên .................................................. ......... 287
11.4.3. Tác vụ loại một phần tử không ở đầu hàng................................... 288
11.5. Một số phương án khác của heap .................................................. ........ 288
11.5.1. d-heaps............................................. ................................................. 288
11.5.2. Heap lệch trái (Leftist heap) .................................................. ......... 289
11.5.3. Skew heap .................................................. ...................................... 295
11.5.4. Hàng nhị thức (Binomial Queue)............................................ ........ 295
Chương 12 – BẢNG VÀ TRUY XUẤT THÔNG TIN
12.1. Dẫn nhập: phá vỡ rào cản lgn .................................................. ............. 305
12.2. Các bảng chữ nhật .................................................. ................................ 306
12.2.1. Thứ tự ưu tiên hàng và thứ tự ưu tiên cột...................................... 306
12.2.2. Đánh chỉ số cho bảng chữ nhật........................................... . ...........307
12.2.3. Biến thể: mảng truy xuất........................................... . .....................308
12.3. Các bảng với nhiều hình dạng khác nhau.............................................3 08
12.3.1. Các bảng tam giác .................................................. ..........................309
12.3.2. Các bảng lồi lõm.............................................. .................................310
12.3.3. Các bảng chuyển đổi .................................................. ......................311
12.4. Bảng: Một kiểu dữ liệu trừu tượng mới........................................... .. .....313
12.4.1. Các hàm.............................................. ...............................................313
12.4.2. Một kiểu dữ liệu trừu tượng .................................................. ...........314
12.4.3. Hiện thực........................................... . ...............................................315
12.4.4. So sánh giữa danh sách và bảng.......................................... .. .........315
12.5. Bảng băm .................................................. ...............................................317
12.5.1. Các bảng thưa .................................................. .................................317
12.5.2. Lựa chọn hàm băm............................................ .. .............................318
12.5.3. Phác thảo giải thuật cho các thao tác dữ liệu trong bảng băm....321
12.5.4. Ví dụ trong C++ .................................................. ..............................322
12.5.5. Giải quyết đụng độ bằng phương pháp địa chỉ mở ........................323
12.5.6. Giải quyết đụng độ bằng phương pháp nối kết..............................323
12.6. Phân tích bảng băm .................................................. ..............................331
12.6.1. Điều ngạc nhiên về ngày sinh.............................................. ...........331
12.6.2. Đếm số lần thử .................................................. ...............................332
12.6.3. Phân tích phương pháp nối kết........................................... .. ..........332
12.6.4. Phân tích phương pháp địa chỉ mở............................................ .. ...333
12.6.5. Các so sánh lý thuyết.......................................... .............................334
12.6.6. Các so sánh thực nghiệm.......................................... .......................335
12.7. Kết luận: so sánh các phương pháp .................................................. .....336
Chương 13 – ĐỒ THỊ
13.1. Nền tảng toán học .................................................. .................................339
13.1.1. Các định nghĩa và ví dụ............................................ .. .....................339
13.1.2. Đồ thị vô hướng .................................................. ..............................340
13.1.3. Đồ thị có hướng.......................................... .......................................341
13.2. Biểu diễn bằng máy tính .................................................. ......................341
13.2.1. Biểu diễn của tập hợp .................................................. ....................342
13.2.2. Danh sách kề .................................................. ..................................344
13.2.3. Các thông tin khác trong đồ thị............................................ . .........346
13.3. Duyệt đồ thị .................................................. ...........................................346
13.3.1. Các phương pháp............................................. ................................. 346
13.3.2. Giải thuật duyệt theo chiều sâu.............................................. ........ 347
13.3.3. Giải thuật duyệt theo chiều rộng.......................................... .. ........ 348
13.4. Sắp thứ tự topo.............................................. .......................................... 349
13.4.1. Đặt vấn đề .................................................. ...................................... 349
13.4.2. Giải thuật duyệt theo chiều sâu.............................................. ........ 350
13.4.3. Giải thuật duyệt theo chiều rộng.......................................... .. ........ 352
13.5. Giải thuật Greedy: Tìm đường đi ngắn nhất ........................................ 353
13.5.1. Đặt vấn đề .................................................. ...................................... 353
13.5.2. Phương pháp............................................. ........................................ 354
13.5.3. Ví dụ............................................ .. .................................................. .. 356
13.5.4. Hiện thực .................................................. ........................................ 356
13.6. Cây phủ tối tiểu........................................... . ........................................... 357
13.6.1. Đặt vấn đề .................................................. ...................................... 357
13.6.2. Phương pháp............................................. ........................................ 359
13.6.3. Hiện thực .................................................. ........................................ 361
13.6.4. Kiểm tra giải thuật Prim .................................................. .............. 362
13.7. Sử dụng đồ thị như là cấu trúc dữ liệu .................................................. 364
Phần 3 – CÁC ỨNG DỤNG CỦA CÁC LỚP CTDL
Chương 14 – ỨNG DỤNG CỦA NGĂN XẾP
14.1. Đảo ngược dữ liệu .................................................. .................................. 365
14.2. Phân tích biên dịch (parsing) dữ liệu........................................... . ........ 366
14.3. Trì hoãn công việc........................................... . ....................................... 368
14.3.1. Ứng dụng tính trị của biểu thức postfix ......................................... 368
14.3.2. Ứng dụng chuyển đổi biểu thức dạng infix thành dạng postfix ... 371
14.4. Giải thuật quay lui (backtracking) .................................................. ....... 372
14.4.1. Ứng dụng trong bài toán tìm đích (goal seeking). ........................ 372
14.4.2. Bài toán mã đi tuần và bài toán tám con hậu............................... 375
Chương 15 – ỨNG DỤNG CỦA HÀNG ĐỢI
15.1. Các dịch vụ .................................................. ............................................ 377
15.2. Phân loại........................................... . .................................................. .... 377
15.3. Phương pháp sắp thứ tự Radix Sort .................................................. .... 377
15.4. Tính trị cho biểu thức prefix............................................ .......................378
15.5. Ứng dụng phép tính trên đa thức .................................................. ........378
15.5.1. Mục đích của ứng dụng.......................................... .. .........................378
15.5.2. Chương trình............................................ .........................................378
15.5.3. Cấu trúc dữ liệu của đa thức .................................................. ..........381
15.5.4. Đọc và ghi các đa thức .................................................. ...................384
15.5.5. Phép cộng đa thức .................................................. ..........................385
15.5.6. Hoàn tất chương trình .................................................. ...................386
Chương 16 – ỨNG DỤNG XỬ LÝ VĂN BẢN
16.1. Các đặc tả............................................ .. .................................................. .387
16.2. Hiện thực........................................... . .................................................. ....388
16.2.1. Chương trình chính............................................ ..............................388
16.2.2. Đặc tả lớp Editor .................................................. ............................389
16.2.3. Nhận lệnh từ người sử dụng .................................................. ..........390
16.2.4. Thực hiện lệnh.......................................... .. ......................................390
16.2.5. Đọc và ghi tập tin............................................... ..............................392
16.2.6. Chèn một hàng .................................................. ...............................393
16.2.7. Tìm một chuỗi ký tự .................................................. .......................393
16.2.8. Biến đổi chuỗi ký tự .................................................. .......................394
Chương 17 – ỨNG DỤNG SINH CÁC HOÁN VỊ
17.1. Ý tưởng .................................................. .................................................. .395
17.2. Tinh chế............................................ . .................................................. .....396
17.3. Thủ tục chung............................................. ..............................................396
17.4. Tối ưu hóa cấu trúc dữ liệu để tăng tốc độ cho chương trình sinh các
hoán vị............................................ .. .................................................. ......397
17.5. Chương trình............................................ ................................................39 8
Chương 18 – ỨNG DỤNG DANH SÁCH LIÊN KẾT VÀ
BẢNG BĂM
18.1. Giới thiệu về chương trình Game_Of_Life ............................................401
18.2. Các ví dụ............................................ .. .................................................. ...401
18.3. Giải thuật .................................................. ...............................................402
18.4. Chương trình chính cho Game_Of_Life .................................................4 03