UBND TỈNH THANH HÓA
TRƯỜNG CAO ĐẲNG NÔNG NGHIỆP THANH HÓA
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(ƯDPM)
TRÌNH ĐỘ: CAO ĐẲNG
(Ban hành kèm theo quyết định số /QĐ – TCĐNN ngày / /2022 của
Hiệu trưởng trường Cao Đẳng Nông Nghiệp Thanh Hóa)
Thanh Hóa, năm 2022
LỜI GIỚI THIỆU
Cấu trúc dữ liệu và giải thuật là một trong những môn học cơ bản của học
sinh ngành Công nghệ thông tin. Các cấu trúc dữ liệu và các giải thuật được xem
như là 2 yếu tố quan trọng nhất trong lập trình, đúng như câu nói nổi tiếng của
Niklaus Wirth: Chương trình = Cấu trúc dữ liệu + Giải thuật (Programs = Data
Structures + Algorithms). Nắm vững các cấu trúc dữ liệu và các giải thuật là cơ sở
để học sinh tiếp cận với việc thiết kế và xây dựng phần mềm cũng như sử dụng
các công cụ lập trình hiện đại.
Cấu trúc dữ liệu có thể được xem như là một phương pháp lưu trữ dữ liệu
trong máy tính nhằm sử dụng một cách có hiệu quả các dữ liệu này. Và để sử
dụng các dữ liệu một cách hiệu quả thì cần phải có các thuật toán áp dụng trên các
dữ liệu đó. Do vậy, cấu trúc dữ liệu và giải thuật là 2 yếu tố không thể tách rời và
có những liên quan chặt chẽ với nhau.
Giáo trình môn “Cấu trúc dữ liệu và giải thuật” bao gồm 6 chương, trình bày
về các cấu trúc dữ liệu và các giải thuật cơ bản nhất trong tin học.
Mặc dù đã rất cố gắng trong quá trình biên soạn nhưng không thể tránh khỏi
những sai sót, rất mong nhận được sự góp ý của đồng nghiệp và người đọc để giáo
trình ngày càng được hoàn thiện hơn.
Xin chân thành cảm ơn!
Thanh Hóa, ngày tháng năm 2022
CHỦ BIÊN
Trần Thị Hà
MỤC LỤC
ĐỀ MỤC TRANG
CHƯƠNG 1:..............................................................................................................1
THIẾT KẾ VÀ PHÂN TÍCH GIẢI THUẬT........................................................1
1.1. MỞ ĐẦU...........................................................................................................1
1.1.1. Giải thuật và cấu trúc dữ liệu.......................................................................1
1.1.2. Ngôn ngữ diễn đạt giải thuật........................................................................2
1.1.2.1. Quy cách về cấu trúc chương trình..............................................................2
1.1.2.2. Kí tự và biểu thức.........................................................................................3
1.1.2.3. Các câu lệnh hay các chỉ thị.........................................................................3
1.2. THIẾT KẾ GIẢI THUẬT...............................................................................7
1.3. PHÂN TÍCH GIẢI THUẬT..........................................................................10
1.3.1. Phân tích tính đúng đắn………………………………………….….10
1.3.2. Phân tích tính đơn giản………………………………………………11
1.4. MỘT SỐ GIẢI THUẬT CƠ BẢN................................................................11
1.4.1. Hoán vị hai phần tử.....................................................................................11
1.4.1.1 Ý tưởng của thuật toán................................................................................11
1.4.1.2 Giải thuật.....................................................................................................11
1.4.2. Tìm số lớn nhất, nhỏ nhất...........................................................................12
1.4.2.1 Tìm số lớn nhất............................................................................................12
1.4.2.2 Tìm số nhỏ nhất...........................................................................................12
1.4.3. Đệ quy...........................................................................................................12
1.4.3.1. Khái niệm....................................................................................................12
1.4.3.2. Ví dụ đệ quy................................................................................................13
BÀI TẬP:................................................................................................................14
CHƯƠNG 2: CÁC KIỂU DỮ LIỆU CƠ SỞ......................................................16
2.1. CÁC KIỂU DỮ LIỆU CƠ BẢN....................................................................16
2.1.1. Kiểu số......................................................................................................…16
2.1.2. Kiểu ký tự, chuỗi.....................................................................................….17
2.2. KIỂU DỮ LIỆU CÓ CẤU TRÚC.................................................................17
2.2.1. Kiểu chuỗi ký tự...........................................................................................17
2.2.2. Kiểu bản ghi.................................................................................................19
2.2.3. Kiểu con trỏ..................................................................................................20
2.3. KIỂU TẬP HỢP.............................................................................................21
2.3.1. Khái niệm.....................................................................................................21
3.3.2. Các phép xử lý kiểu dữ liệu tập hợp..........................................................21
2.3.3. Cài đặt tập hợp............................................................................................22
BÀI TẬP.................................................................................................................24
CHƯƠNG 3:...........................................................................................................28
MẢNG, DANH SÁCH VÀ CÁC KIỂU DỮ LIỆU TRÌU TƯỢNG..................28
3.1. MẢNG.............................................................................................................28
3.1.1. Khái niệm.....................................................................................................28
3.1.2. Cấu trúc lưu trữ của mảng.........................................................................29
3.2. DANH SÁCH LIÊN KẾT..............................................................................32
3.2.1. Danh sách liên kết đơn................................................................................32
3.2.1.1. Khái niệm...................................................................................................32
3.2.1.2. Một số phép toán trên danh sách liên kết đơn.........................................33
3.2.2. Danh sách liên kết vòng…………………………………………………36
3.2.2.1. Khái niêm……………………………………………………….………36
3.2.1.2. Một số phép toán trên danh sách liên kết vòng........................................37
3.2.3. Danh sách liên kết kép…………………………………………………..40
3.2.3.1. Khái niêm……………………………………………………….………40
3.2.3.2. Các phép toán trên danh sách liên kết kép...............................................37
3.3. CÁC KIỂU DỮ LIỆU TRỪU TƯỢNG........................................................43
3.3.1. Ngăn xếp (stack)..........................................................................................43
3.3.1.1. Khái niệm...................................................................................................43
3.3.1.2. Các phép toán trên ngăn xếp...............................................................43
3.3.1.3. Ví dụ....................................................................................................44
3.3.2. Hàng đợi (Queue)........................................................................................44
3.3.1.1. Khái niệm...................................................................................................44
3.3.2.2. Các phép toán trên hàng đợi.....................................................................45
3.3.2.3. Ví dụ...................................................................................................45
BÀI TẬP.................................................................................................................47
CHƯƠNG 4: CÂY.................................................................................................49
4.1. KHÁI NIỆM VỀ CÂY...................................................................................49
4.2. CÂY NHỊ PHÂN.............................................................................................50
4.2.1. Biểu diễn cây nhị phân................................................................................50
4.2.1.1. Lưu trữ kế tiếp............................................................................................51
4.2.1.2. Lưu trữ móc nối………………………………………………………………….52
4.2.2. Duyệt cây nhị phân......................................................................................52
4.2.2.1. Duyệt theo thứ tự trước (PreOrder Traversal)…………………………..….53
4.2.2.1. Duyệt theo thứ tự trước (PreOrder Traversal)…………………………..….53
4.2.2.3. Duyệt theo thứ tự sau (PostOrder Traversal)………………………….……54
4.2.3. Cài đặt cây nhị phân...................................................................................54
BÀI TẬP.................................................................................................................57
5.1. SẮP XẾP KIỂU CHỌN, CHÈN, NỔI BỌT.................................................59
5.1.1. Sắp xếp kiểu chọn........................................................................................59
5.1.2. Sắp xếp kiểu chèn........................................................................................61
5.1.3. Sắp xếp kiểu nổi bọt....................................................................................64
5.2. SẮP XẾP KIỂU PHÂN ĐOẠN.....................................................................66
5.2.1. Ý tưởng ....................................................................................................66
5.2.2. Giải thuật...................................................................................................67
5.3. SẮP XẾP KIỂU VUN ĐỐNG........................................................................68
5.3.1. Ý tưởng ....................................................................................................68
5.3.2. Giải thuật...................................................................................................69
BÀI TẬP.................................................................................................................70
CHƯƠNG 6. TÌM KIẾM......................................................................................72
6.1. TÌM KIẾM TUẦN TỰ...................................................................................72
6.1.1. Ý tưởng ....................................................................................................72
6.1.2. Giải thuật...................................................................................................72
6.2. TÌM KIẾM NHỊ PHÂN.................................................................................73
6.2.1. Ý tưởng .....................................................................................................73
6.2.2. Giải thuật....................................................................................................73
6.3. CÂY TÌM KIẾM NHỊ PHÂN.......................................................................75
6.3.1. Định nghĩa....................................................................................................75
6.3.2. Cài đặt cây tìm kiếm nhị phân...................................................................75
6.3.2.1. Thăm các nút trên cây……………………………………………………....…..75
6.3.2.2. Tìm một phần tử x trong cây……………………………………………...……76
6.3.2.3. Thêm một phần tử x vào cây……………………………………………….......77
6.3.2.4. Hủy một phần tử có khóa x ………………………………………………...….77
BÀI TẬP .................................................................................................................79