Tài liệu Giáo trình cấu trúc dữ liệu

Giáo trình cấu trúc dữ liệu

MỤC LỤC

CHƯƠNG I MỞĐẦU 9U

I. TỪ BÀI TOÁN ĐẾN CH ƯƠNG TRÌNH .9
1. Mô hình hóa bài toán thực tế 9
2. Giải thuật (algorithms) .12
3. Ngôn ngữ giả và tinh chế từng bước (Pseudo-language and stepwise refinement) .15
4. Tóm tắt 17

II. KIỂU DỮ LIỆU TRỪU TƯỢNG (ABSTRACT DATA TYPE) 18
1. Khái niệm trừu tượng hóa .18
2. Trừu tượng hóa chương trình .18
3. Trừu tượng hóa dữ liệu .19

III. KIỂU DỮ LIỆU - CẤU TRÚC DỮ LIỆU VÀ KIỂU DỮ LIỆU TRỪU TƯỢNG (DATA
TYPES, DATA STRUCTURES, ABSTRACT DATA TYPES) 20
CHƯƠNG II CÁC KIỂU DỮ LIỆU TRỪU TƯỢNG CƠ BẢN .22
(BASIC ABSTRACT DATA TYPES) 22

I. KIỂU DỮ LIỆU TRỪU TƯỢNG DANH SÁCH (LIST) .24
1. Khái niệm danh sách 24
2. Các phép toán trên danh sách .24
3. Cài đặt danh sách 26

II. NGĂN XẾP (STACK) .43
1. Định nghĩa ngăn xếp .43
2. Các phép toán trên ngăn xếp 44
3. Cài đặt ngăn xếp .45
4. Ứng dụng ngăn xếp để loại bỏđệ qui của chương trình .48

III. HÀNG ĐỢI (QUEUE) 53
1. Định Nghĩa .53
2. Các phép toán cơ bản trên hàng 53
3. Cài đặt hàng 53
4. Một sốứng dụng của cấu trúc hàng 62

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

BÀI TẬP 68

CHƯƠNG III CẤU TRÚC CÂY (TREES) .73

I. CÁC THUẬT NGỮ CƠ BẢN TRÊN CÂY .74
1. Định nghĩa 74
2. Thứ tự các nút trong cây .75
3. Các thứ tự duyệt cây quan trọng .75
4. Cây có nhãn và cây biểu thức .76

II. KIỂU DỮ LIỆU TRỪU TƯỢNG CÂY .78

III. CÀI ĐẶT CÂY .79
1. Cài đặt cây bằng mảng .79

Cấu trúc dữ liệu Mục lục

2. Biểu diễn cây bằng danh sách các con .85
3. Biểu diễn theo con trái nhất và anh em ruột phải: 86
4. Cài đặt cây bằng con trỏ .87

IV. CÂY NHỊ PHÂN (BINARY TREES) 87
1. Định nghĩa 87
2. Duyệt cây nhị phân .88
3. Cài đặt cây nhị phân .89

V. CÂY TÌM KIẾM NHỊ PHÂN (BINARY SEARCH TREES) .92
1. Định nghĩa 92
2. Cài đặt cây tìm kiếm nhị phân 93

BÀI TẬP 100

CHƯƠNG IV TẬP HỢP 103

I. KHÁI NIỆM TẬP HỢP .104

II. KIỂU DỮ LIỆU TRỪU TƯỢNG TẬP HỢP 104

III. CÀI ĐẶT TẬP HỢP 105
1. Cài đặt tập hợp bằng vector Bit 105
2. Cài đặt bằng danh sách liên kết 107

IV. TỪĐIỂN (dictionary) .111
1. Cài đặt từđiển bằng mảng 111
2. Cài đặt từđiển bằng bảng băm .113
3. Các phương pháp xác định hàm băm .122

V. HÀNG ƯU TIÊN (priority queue) 123
1. Khái niệm hàng ưu tiên 123
2. Cài đặt hàng ưu tiên 124

BÀI TẬP 131

CHƯƠNG V ĐỒ THỊ (GRAPH) .133

I. CÁC ĐỊNH NGHĨA 134

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

III. BIỂU DIỄN ĐỒ THỊ 136
1. Biểu diễn đồ thị bằng ma trận kề 136
2. Biểu diễn đồ thị bằng danh sách các đỉnh kề: 138

IV. CÁC PHÉP DUYỆT ĐỒ THỊ (traversals of graph) .138
1. Duyệt theo chiều sâu (depth-first search) .139
2. Duyệt theo chiều rộng (breadth-first search) 140

V. MỘT SỐ BÀI TOÁN TRÊN ĐỒ THỊ 143
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
problem) .143
2. Tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh .145
3. Bài toán tìm bao đóng chuyển tiếp (transitive closure) 146

Trang 4