MỤC LỤC
CHƯƠNG I MỞ ĐẦU ..............................................................................................................9 U
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
Trang 3
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
Cấu trúc dữliệu Mục lục
4. Bài toán tìm cây bao trùm tối thiểu (minimum-cost spanning tree).................................147
BÀI TẬP ..........................................................................................................................................150