MỤC LỤC
i
TRƯỜNG CAO ĐẲNG VIỆT MỸ
GIÁO TRÌNH
MÔN HỌC: CẤU TRÚC DỮ LIỆU & GIẢI THUẬT
NGÀNH: CÔNG NGHỆ
TRÌNH ĐỘ: CAO ĐẲNG
(Ban hành kèm theo Quyết định số: /QĐ-CĐVM ngày ..… tháng ....... năm……..
của Trường Cao đẳng Việt Mỹ)
Thành phố Hồ Chí Minh, năm 20…
(Lưu hành nội bộ)
MỤC LỤC
ii
LỜI GIỚI THIỆU
Giáo trình Thiết kế web được biên soạn dựa trên khung chương trình đào tạo cao đẳng nghề Công nghệ thông tin đã
được Trường Cao đẳng Việt Mỹ phê duyệt.
Tác giả đã nghiên cứu một số tài liệu, giáo trình môn thiết kế web và nhiều nguồn tài liệu khác, kết hợp kinh nghiệm
giảng dạy và làm việc của bản thân để viết nên cuốn giáo trình này. Nội dung được tác giả trình bày cô đọng, dễ
hiểu, các kiến thức mới đều có ví dụ đi kèm theo giúp người đọc hiểu và ghi nhớ lâu. Giáo trình được viết ra theo
nguyên tắc quan tâm đến kết quả đầu ra, khả năng tự học và kỹ năng cần thiết để sinh viên có thể nắm vững kiến
thức và thành thạo thao tác. Mục tiêu chính của giáo trình là giúp sinh viên nắm vững các kiến thức về website, các
bước xây dựng trang web, thông thạo ngôn ngữ HTML và CSS để xây dựng và trang trí trang web.
Sau khi học xong người học sẽ được làm quen với framework Bootstrap cực kỳ mạnh mẽ trong khả năng xây dựng
web một cách nhanh chóng, đẹp, đồng bộ trong giao diện và mượt mà trong xử lý hiệu ứng ở môn Thiết kế web 2,
từ đó nâng cao được chất lượng giao diện và hiệu ứng của trang web.
Trong quá trình biên soạn, giáo trình không tránh khỏi có sai sót. Tác giả rất mong nhận được ý kiến đánh giá của
quý thầy cô, các em sinh viên để giáo trình ngày càng hoàn thiện.
Xin chân thành cảm ơn quý đồng nghiệp, bạn bè, doanh nghiệp đã có những ý kiến đóng góp trong quá trình tác giả
biên soạn giáo trình này.
Thành phố Hồ Chí Minh, ngày 24 tháng 9 năm 2023
Tham gia biên soạn
Chủ biên ThS. Phạm Đào Minh Vũ
MỤC LỤC
iii
MỤC LỤC i
CHƯƠNG 1. GIỚI THIỆU CHUNG...........................................................................................................................5
1.1.
Kiểu và cấu trúc dữ liệu........................................................................................................................................5
1.1.1.
Kiểu dữ liệu................................................................................................................................................... 5
1.1.2.
Biến................................................................................................................................................................8
1.2.
Thuật toán và một số vấn đề liên quan..................................................................................................................9
1.3.
Biểu diễn thuật toán............................................................................................................................................ 10
1.4.
Độ phức tạp thời gian của thuật toán.................................................................................................................. 11
1.4.1.
Khái niệm độ phức tạp thuật toán................................................................................................................ 12
1.4.2.
Một số qui tắc xác định độ phức tạp thuật toán........................................................................................... 13
1.4.3.
Một số dạng hàm được dùng xác định độ phức tạp thuật toán.....................................................................14
1.5.
Độ phức tạp của các cấu trúc lệnh...................................................................................................................... 15
1.6.
Qui trình giải quyết bài toán trên máy tính......................................................................................................... 17
BÀI TẬP....................................................................................................................................................................18
CHƯƠNG 2. MỘT SỐ LƯỢC ĐỒ THUẬT TOÁN KINH ĐIỂN.......................................................................... 22
2.1.
Mô hình thuật toán sinh (Generative Algorithm)................................................................................................22
2.2.
Mô hình thuật toán đệ qui (Recursion Algorithm)..............................................................................................28
2.3.
Mô hình thuật toán quay lui (Back-track Algorithm)......................................................................................... 30
2.4.
Mô hình thuật toán tham lam (Greedy Algorithm)............................................................................................. 37
2.5.
Mô hình thuật toán chia và trị (Devide and Conquer Algorithm)....................................................................... 46
2.6.
Mô hình thuật toán nhánh cận (Branch and Bound Algorithm)..........................................................................47
2.7.
Mô hình thuật toán qui hoạch động (Dynamic Programming Algorithm).......................................................... 51
BÀI TẬP....................................................................................................................................................................54
CHƯƠNG 3. SẮP XẾP VÀ TÌM KIẾM....................................................................................................................59
3.1.
Giới thiệu vấn đề.................................................................................................................................................59
3.2.
Các thuật toán sắp xếp đơn giản......................................................................................................................... 59
3.2.1.
Thuật toán Selection-Sort............................................................................................................................ 60
3.2.2.
Thuật toán Insertion Sort............................................................................................................................. 62
3.2.3.
Thuật toán Bubble Sort................................................................................................................................ 64
3.3.
Thuật toán Quick Sort.........................................................................................................................................66
3.4.
Thuật toán Merge Sort........................................................................................................................................ 69
3.5.
Thuật toán Heap Sort.......................................................................................................................................... 73
3.6.
Một số thuật toán tìm kiếm thông dụng.............................................................................................................. 75
3.6.1.
Thuật toán tìm kiếm tuyến tính (Sequential Serch)..................................................................................... 75
3.6.2.
Thuật toán tìm kiếm nhị phân...................................................................................................................... 76
3.6.3.
Thuật toán tìm kiếm nội suy........................................................................................................................ 78
3.6.4.
Thuật toán tìm kiếm Jumping...................................................................................................................... 80
BÀI TẬP....................................................................................................................................................................82
MỤC LỤC
iv
CHƯƠNG 4. NGĂN XẾP, HÀNG ĐỢI, DANH SÁCH LIÊN KẾT....................................................................... 88
4.1.
Danh sách liên kết đơn (Single Linked List)......................................................................................................88
4.1.1.
Định nghĩa danh sách liên kết đơn...............................................................................................................88
4.1.2.
Biểu diễn danh sách liên kết đơn................................................................................................................. 88
4.1.3.
Thao tác trên danh sách liên kết đơn............................................................................................................89
4.1.4.
Ứng dụng của danh sách liên kết đơn........................................................................................................ 104
4.2.
Danh sách liên kết kép (double linked list)....................................................................................................... 105
4.2.1.
Định nghĩa................................................................................................................................................. 105
4.2.2.
Biểu diễn....................................................................................................................................................105
4.2.3.
Các thao tác trên danh sách liên kết kép.................................................................................................... 106
4.2.4.
Xây dựng danh sách liên kết kép bằng STL.............................................................................................. 114
4.3.
Ngăn xếp (Stack).............................................................................................................................................. 117
4.3.1.
Định nghĩa ngăn xếp.................................................................................................................................. 117
4.3.2.
Biểu diễn ngăn xếp.................................................................................................................................... 118
4.3.3.
Các thao tác trên ngăn xếp......................................................................................................................... 118
4.3.4.
Ứng dụng của ngăn xếp............................................................................................................................. 124
4.4.
Hàng đợi (Queue)............................................................................................................................................. 128
4.4.1.
Định nghĩa hàng đợi...................................................................................................................................128
4.4.2.
Biểu diễn hàng đợi.....................................................................................................................................129
4.4.3.
Thao tác trên hàng đợi............................................................................................................................... 129
4.4.4.
Ứng dụng của hàng đợi..............................................................................................................................138
BÀI TẬP..................................................................................................................................................................140
CHƯƠNG 5. CÂY NHỊ PHÂN (BINARY TREE)..................................................................................................145
5.1.
Định nghĩa và khái niệm.................................................................................................................................. 145
4.1.1.
Định nghĩa................................................................................................................................................. 145
5.1.2.
Một số tính chất của cây nhị phân..............................................................................................................146
5.1.3.
Các loại cây nhị phân.................................................................................................................................147
5.2.
Biểu diễn cây nhị phân......................................................................................................................................151
5.2.1.
Biểu diễn cây nhị phân bằng mảng............................................................................................................ 151
5.2.2.
Biểu diễn cây nhị phân bằng danh sách liên kết........................................................................................ 151
5.3.
Các thao tác trên cây nhị phân.......................................................................................................................... 152
5.3.1.
Định nghĩa và khai báo cây nhị phân.........................................................................................................152
5.3.2.
Các thao tác thêm node vào cây nhị phân.................................................................................................. 153
5.3.3.
Các thao tác loại node khỏi cây nhị phân...................................................................................................157
5.3.4.
Ba phép duyệt cây nhị phân.......................................................................................................................160
5.3.5.
Chương trình cài đặt các thao tác trên cây nhị phân.................................................................................. 162
5.4.
Ứng dụng của cây nhị phân...............................................................................................................................167
5.5.
Cây nhị phân tìm kiếm (Binary Search Tree)................................................................................................... 167
MỤC LỤC
v
5.5.1.
Định nghĩa cây nhị phân tìm kiếm............................................................................................................. 167
5.5.2.
Biểu diễn cây nhị phân tìm kiếm............................................................................................................... 168
5.5.3.
Các thao tác trên cây nhị phân tìm kiếm....................................................................................................168
5.5.4.
Chương trình cài đặt cây nhị phân tìm kiếm..............................................................................................172
5.6.
Cây nhị phân tìm kiếm cân bằng.......................................................................................................................176
5.6.1.
Định nghĩa cây nhị phân tìm kiếm cân bằng..............................................................................................176
5.6.2.
Biểu diễn cây nhị phân tìm kiếm cân bằng................................................................................................ 177
5.6.3.
Các thao tác trên cây nhị phân tìm kiếm cân bằng.....................................................................................177
5.6.4.
Chương trình cài đặt cây nhị phân tìm kiếm cân bằng...............................................................................184
BÀI TẬP..................................................................................................................................................................191
CHƯƠNG 6. ĐỒ THỊ (GRAPH)..............................................................................................................................199
6.1.
Định nghĩa và khái niệm.................................................................................................................................. 199
5.1.1.
Một số thuật ngữ cơ bản trên đồ thị........................................................................................................... 199
6.1.2.
Một số thuật ngữ trên đồ thị vô hướng.......................................................................................................200
6.1.3.
Một số thuật ngữ trên đồ thị có hướng.......................................................................................................200
6.1.4.
Một số loại đồ thị đặc biệt..........................................................................................................................201
6.2.
Biểu diễn đồ thị................................................................................................................................................202
6.2.1.
Biểu diễn bằng ma trận kề......................................................................................................................... 202
6.2.2.
Biểu diễn đồ thị bằng danh sách cạnh........................................................................................................203
6.2.3.
Biểu diễn đồ thị bằng danh sách kề........................................................................................................... 204
6.2.4.
Biểu diễn đồ thị bằng danh sách kề dựa vào danh sách liên kết................................................................ 205
6.2.5.
Biểu diễn đồ thị bằng danh sách kề dựa vào list STL................................................................................ 208
6.3.
Các thuật toán tìm kiếm trên đồ thị...................................................................................................................209
6.3.1.
Thuật toán tìm kiếm theo chiều sâu (Depth First Search)..........................................................................209
6.3.2.
Thuật toán tìm kiếm theo chiều rộng (Breadth First Search).....................................................................213
6.3.3.
Ứng dụng của thuật toán DFS và BFS....................................................................................................... 216
6.4.
Đồ thị Euler...................................................................................................................................................... 217
6.4.1.
Thuật toán tìm một chu trình Euler trên đồ thị vô hướng...........................................................................218
6.4.2.
Thuật toán tìm một chu trình Euler trên đồ thị có hướng...........................................................................221
6.4.3.
Thuật toán tìm một đường đi Euler trên đồ thị vô hướng...........................................................................225
6.4.4.
Thuật toán tìm một đường đi Euler trên đồ thị có hướng...........................................................................228
6.5.
Bài toán xây dựng cây khung của đồ thị...........................................................................................................231
6.5.1.
Xây dựng cây khung của đồ thị bằng thuật toán DFS................................................................................231
6.5.2.
Xây dựng cây khung của đồ thị bằng thuật toán BFS................................................................................234
6.5.3.
Xây dựng cây khung nhỏ nhất của đồ thị bằng thuật toán Kruskal............................................................237
6.5.4.
Xây dựng cây khung nhỏ nhất của đồ thị bằng thuật toán PRIM...............................................................241
6.6.
Bài toán tìm đường đi ngắn nhất.......................................................................................................................244
6.6.1.
Thuật toán Dijkstra.................................................................................................................................... 245