[FONT="]MỤC LỤC

[FONT="]CHƯƠNG I

[FONT="]MỞ ĐẦU 9

U

[FONT="]I.TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH .9

[FONT="]1. Mô hình hóa bài toán thực tế 9

[FONT="]2. Giải thuật (algorithms) .12

[FONT="]3. Ngôn ngữ giả và tinh chế từng bước (Pseudo-language and stepwise refinement) .15

[FONT="]4. Tóm tắt 17

[FONT="]II.KIỂU DỮ LIỆU TRỪU TƯỢNG (ABSTRACT DATA TYPE) 18

[FONT="]1. Khái niệm trừu tượng hóa .18

[FONT="]2. Trừu tượng hóa chương trình .18

[FONT="]3. Trừu tượng hóa dữ liệu .19

[FONT="]III.KIỂU DỮ LIỆU - CẤU TRÚC DỮ LIỆU VÀ KIỂU DỮ LIỆU TRỪU TƯỢNG (DATA

[FONT="]TYPES, DATA STRUCTURES, ABSTRACT DATA TYPES) 20

[FONT="]CHƯƠNG II CÁC KIỂU DỮ LIỆU TRỪU TƯỢNG CƠ BẢN .22

[FONT="](BASIC ABSTRACT DATA TYPES) 22

[FONT="]I.KIỂU DỮ LIỆU TRỪU TƯỢNG DANH SÁCH (LIST) .24

[FONT="]1. Khái niệm danh sách 24

[FONT="]2. Các phép toán trên danh sách .24

[FONT="]3. Cài đặt danh sách 26

[FONT="]II.NGĂN XẾP (STACK) .43

[FONT="]1. Định nghĩa ngăn xếp .43

[FONT="]2. Các phép toán trên ngăn xếp 44

[FONT="]3. Cài đặt ngăn xếp .45

[FONT="]4. Ứng dụng ngăn xếp để loại bỏ đệ qui của chương trình .48

[FONT="]III.HÀNG ĐỢI (QUEUE) 53

[FONT="]1.Định Nghĩa .53

[FONT="]2.Các phép toán cơ bản trên hàng 53

[FONT="]3.Cài đặt hàng 53

[FONT="]4.Một số ứng dụng của cấu trúc hàng 62

[FONT="]IV.DANH SÁCH LIÊN KẾT KÉP (double - lists) .62

[FONT="]BÀI TẬP 68

[FONT="]CHƯƠNG III CẤU TRÚC CÂY (TREES) .73

[FONT="]I.CÁC THUẬT NGỮ CƠ BẢN TRÊN CÂY .74

[FONT="]1. Định nghĩa 74

[FONT="]2. Thứ tự các nút trong cây .75

[FONT="]3. Các thứ tự duyệt cây quan trọng .75

[FONT="]4. Cây có nhãn và cây biểu thức .76

[FONT="]II.KIỂU DỮ LIỆU TRỪU TƯỢNG CÂY .78

[FONT="]III.CÀI ĐẶT CÂY .79

[FONT="]1.Cài đặt cây bằng mảng .79

[FONT="]2.Biểu diễn cây bằng danh sách các con .85

[FONT="]3.Biểu diễn theo con trái nhất và anh em ruột phải: 86

[FONT="]4.Cài đặt cây bằng con trỏ .87

[FONT="]IV.CÂY NHỊ PHÂN (BINARY TREES) 87

[FONT="]1.Định nghĩa 87

[FONT="]2.Duyệt cây nhị phân .88

[FONT="]3.Cài đặt cây nhị phân .89

[FONT="]V.CÂY TÌM KIẾM NHỊ PHÂN (BINARY SEARCH TREES) .92

[FONT="]1. Định nghĩa 92

[FONT="]2. Cài đặt cây tìm kiếm nhị phân 93

[FONT="]BÀI TẬP 100

[FONT="]CHƯƠNG IVTẬP HỢP 103

[FONT="]I.KHÁI NIỆM TẬP HỢP .104

[FONT="]II.KIỂU DỮ LIỆU TRỪU TƯỢNG TẬP HỢP 104

[FONT="]III.CÀI ĐẶT TẬP HỢP 105

[FONT="]1.Cài đặt tập hợp bằng vector Bit 105

[FONT="]2.Cài đặt bằng danh sách liên kết 107

[FONT="]IV.TỪ ĐIỂN (dictionary) .111

[FONT="]1.Cài đặt từ điển bằng mảng 111

[FONT="]2.Cài đặt từ điển bằng bảng băm .113

[FONT="]3.Các phương pháp xác định hàm băm .122

[FONT="]V.HÀNG ƯU TIÊN (priority queue) 123

[FONT="]1.Khái niệm hàng ưu tiên 123

[FONT="]2.Cài đặt hàng ưu tiên 124

[FONT="]BÀI TẬP 131

[FONT="]CHƯƠNG V ĐỒ THỊ (GRAPH) .133

[FONT="]I.CÁC ĐỊNH NGHĨA 134

[FONT="]II.KIỂU DỮ LIỆU TRỪU TƯỢNG ĐỒ THỊ 135

[FONT="]III.BIỂU DIỄN ĐỒ THỊ 136

[FONT="]1.Biểu diễn đồ thị bằng ma trận kề 136

[FONT="]2.Biểu diễn đồ thị bằng danh sách các đỉnh kề: 138

[FONT="]IVCÁC PHÉP DUYỆT ĐỒ THỊ (traversals of graph) .138

[FONT="]1.Duyệt theo chiều sâu (depth-first search) .139

[FONT="]2.Duyệt theo chiều rộng (breadth-first search) 140

[FONT="]V.MỘT SỐ BÀI TOÁN TRÊN ĐỒ THỊ 143

[FONT="]1. Bài toán tìm đuờng đi ngắn nhất từ một đỉnh của đồ thị (the single source shorted path

[FONT="]problem) .143

[FONT="]2. Tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh .145

[FONT="]3. Bài toán tìm bao đóng chuyển tiếp (transitive closure) 146

[FONT="]4.Bài toán tìm cây bao trùm tối thiểu (minimum-cost spanning tree) .147

[FONT="]BÀI TẬP 15