Giáo trình Cấu trúc dữ liệu và giải thuật - Nguyễn Ngô Bảo Trân

MỤC LỤC

Phần 1– PHẦN MỞ ĐẦU

Chươ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ố constructortiệ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 .124

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 ưutiê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.308

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ươngphá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.398

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 .403

18.4.1. Phiên bản thứ nhất cho lớp Life . 404

18.4.2. Phiên bản thứ hai với CTDL mới cho Life . 407