SỞ LAO ĐỘNG, THƯƠNG BINH VÀ XÃ HỘI ĐẮK LẮK
TRƯỜNG TRUNG CẤP TRƯỜNG SƠN
GIÁO TRÌNH
MÔN HỌC: CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
NGHỀ: CÔNG NGHỆ THÔNG TIN
TRÌNH ĐỘ: TRUNG CẤP
Ban hành kèm theo Quyết định số: 140/QĐ-TCTS ngày 02 tháng 8 năm 2022
của Hiệu trưởng Trường trung cấp Trường Sơn
Đắk Lắk, năm 2022
ii
TUYÊN BỐ BẢN QUYỀN
Tài liệu này thuộc loại sách giáo trình nên các nguồn thông tin có thể được phép
dùng nguyên bản hoặc trích dùng cho các mục đích về đào tạo và tham khảo.
Mọi mục đích khác mang tính lệch lạc hoặc sử dụng với mục đích kinh doanh
thiếu lành mạnh sẽ bị nghiêm cấm.
iii
LỜI GIỚI THIỆU
Hiện nay, tại Trường chưa có giáo trình Cấu trúc dữ liệu & giải thuật. Đặc biệt
trên thị trường không có tài liệu học tập, tham khảo phù hợp với chương trình khung
Cao đẳng nghề, trung cấp nghề thuộc nghề Công nghệ thông tin (CNTT) trong quá
trình đào tạo nghề hiện nay.
Nhóm tác giả biên soạn giáo trình lập trình cơ bản nhằm mục đích giúp học
sinh, sinh viên (HSSV) sử dụng giáo trình làm tài liệu nghiên cứu và học tập một cách
thuận tiện. Chương trình môn học được sử dụng để giảng dạy cho sinh viên trung cấp
nghề Công nghệ thông tin (ứng dụng phần mềm) và làm tài liệu tham khảo cho các
nghề thuộc các ngành nghề kỹ thuật.
Vậy, rất mong được sự góp ý của bạn đọc để tài liệu này ngày càng được hoàn
thiện hơn, chúng tôi xin chân thành cảm ơn..
Xin chân thành cảm ơn!.
Đắk Lắk, ngày 02 tháng 8 năm 2022
Tham gia biên soạn
1. Nguyễn Như Cường - Chủ biên
2. Nguyễn Thị Nhung
3. Lưu Thị Thương
iv
MỤC LỤC
LỜI GIỚI THIỆU .......................................................................................................... III
GIÁO TRÌNH MÔN HỌC .............................................................................................. 7
CHƯƠNG I. THIẾT KẾ VÀ PHÂN TÍCH GIẢI THUẬT ............................................ 9
1. TỪ BÀI TOÁN ĐẾN CHƯƠNG TRÌNH: ............................................................................................... 9
1.1 Modul hóa việc giải quyết bài toán: ................................................................................................ 9
1.2 Phương pháp tinh chỉnh từng bước ................................................................................................. 9
2. PHÂN TÍCH GIẢI THUẬT: ................................................................................................................. 9
3. ĐỘ PHỨC TẠP TÍNH TOÁN CỦA GIẢI THUẬT .............................................................................. 10
3.1 Khái niệm: ................................................................................................................................................ 10
3.2. Ví dụ .......................................................................................................................................................... 10
3.3 Xác định độ phức tạp tính toán của giải thuật: ......................................................................... 10
CHƯƠNG II. ĐỆ QUY VÀ GIẢI THUẬT ĐỆ QUY .................................................. 12
1. KHÁI NIỆM ĐỆ QUY: ...................................................................................................................... 12
2. GIẢI THUẬT ĐỆ QUY VÀ THỦ TỤC ĐỆ QUY ................................................................................ 12
3. THIẾT KẾ GIẢI THUẬT ĐỆ QUY ..................................................................................................... 12
3.1 Bài toán tính n! ....................................................................................................................................... 12
3.2. Dãy số Fibonacci: ................................................................................................................................ 14
3.3 Bài toán tháp Hà Nội: .......................................................................................................................... 14
4. HIỆU LỰC ĐỆ QUY: ......................................................................................................................... 14
CHƯƠNG III. MẢNG VÀ DANH SÁCH ................................................................... 15
1. CÁC KHÁI NIỆM: ............................................................................................................................. 15
1.1. Mảng: ........................................................................................................................................................ 15
2. CẤU TRÚC LƯU TRỮ CỦA MẢNG ................................................................................................. 16
2.1 Khái niệm: ................................................................................................................................................ 16
2.2 Định nghĩa kiểu cấu trúc .................................................................................................................... 17
2.3 Khai báo biến cấu trúc ........................................................................................................................ 18
3. LƯU TRỮ KẾ TIẾP CỦA DANH SÁCH TUYẾN TÍNH ..................................................................... 18
3.1. Khái niệm: ............................................................................................................................................... 18
3.2. Khai báo biến tập hợp: ....................................................................................................................... 18
3.3 Khai báo biến kiểu tập hợp: .............................................................................................................. 19
4 STACK HAY DANH SÁCH KIỂU NGĂN XẾP: ................................................................................. 20
v
4.1. Khái niệm - Cấu trúc dữ liệu: ...................................................................................................... 20
4.2 Lưu trữ Stack bằng mảng .................................................................................................................. 20
4.3 Ứng dụng của ngăn xếp (Biểu thức hậu tố - ký pháp Ba Lan) .......................................... 21
5.
HÀNG
ĐỢI
(QUEUE) ................................................................................................................... 22
5.1 Khái niệm: ............................................................................................................................................... 22
5.2 Lưu trữ Queue bằng mảng: ............................................................................................................... 23
CHƯƠNG IV. CÂY ...................................................................................................... 25
1. CÁC KHÁI NIỆM CƠ BẢN: .............................................................................................................. 25
1.1.
Định
nghĩa
cây: .................................................................................................................................. 25
1.2. Một số khái niệm liên quan ............................................................................................................. 27
1.3.
Biểu
diễn
cây ...................................................................................................................................... 28
2. CÂY NHỊ PHÂN (BINARY TREE): .................................................................................................. 29
2.2. Biểu diễn cây nhị phân: ................................................................................................................... 30
3. PHÉP DUYỆT CÂY NHỊ PHÂN: ....................................................................................................... 30
3.1 Duyệt theo thứ tự trước NLR (Node – Left – Right) ............................................................ 31
3.2 Duyệt theo thứ tự giữa LNR (Left – Node – Right) .............................................................. 31
3.3 Duyệt theo thứ tự sau LRN (Left – Right – Node ) ............................................................... 33
4. CÂY NHỊ PHÂN TÌM KIẾM: ............................................................................................................. 33
4.1. Định nghĩa ............................................................................................................................................... 33
4.2. Tìm kiếm trên cây nhị phân tìm kiếm ......................................................................................... 34
4.3.Thêm phần tử mới vào cây nhị phân tìm kiếm......................................................................... 35
4.4.Xóa phần tử khỏi cây nhị phân tìm kiếm .................................................................................... 36
4.5. Xóa toàn bộ cây nhị phân ................................................................................................................. 39
5. BÀI TẬP: .......................................................................................................................................... 39
CHƯƠNG V. ĐỒ THỊ VÀ MỘT VÀI CẤU TRÚC PHI TUYẾN .............................. 40
1. CÁC KHÁI NIỆM VỀ ĐỒ THỊ ........................................................................................................... 40
2. BIỂU DIỄN ĐỒ THỊ .......................................................................................................................... 41
2.1 Biểu diễn bằng ma trận lân cận: ..................................................................................................... 41
2.2 Biểu diễn bằng danh sách lân cận ................................................................................................. 42
3. PHÉP DUYỆT MỘT ĐỒ THỊ ............................................................................................................. 42
3.1 Tìm kiếm theo chiều sâu: .................................................................................................................. 42
3.2 Tìm kiếm theo chiều rộng: ............................................................................................................... 42