BỘ NÔNG NGHIỆP VÀ PHÁT TRIỂN NÔNG THÔN
TRƯỜNG CAO ĐẲNG CƠ GIỚI NINH BÌNH
GIÁO TRÌNH
MÔN HỌC: MH19_CẤU TRÚC DỮ LIỆU
VÀ GIẢI THUẬT
NGHỀ: LẬP TRÌNH MÁY TÍNH
TRÌNH ĐỘ: Cao đẳng/ trung cấp
Ban hành kèm theo Quyết định số: /QĐ-…TCGNB
ngày…….tháng….năm .... của Hiệu trưởng Trường Cao Đẳng Cơ giới Ninh Bình
Ninh Bình, năm 2018
1
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.
2
Lời giới thiệu
Các kiến thức về cấu trúc dữ liệu (CTDL) và giải thuật đóng vai trò quan
trọng trong việc đào tạo nghề Lập trình máy tính. Sách này đựơc hình thành trên cơ
sở các bài giảng về CTDL và giải thuật mà tôi cùng các đồng nghiệp đã đọc nhiều
năm tại khoa Toán-Cơ-Tin học - Trường Đại học Khoa học Tự nhiên – Đại học
Quốc Gia Hà Nội; Khoa Công nghệ thông tin - Đại học Bách Khoa Hà Nội; Khoa
Công nghệ thông tin - Đại học Giao thông vận tải. Sách được biên soạn chủ yếu để
làm tài liệu tham khảo cho học sinh, sinh viên nghề Lập trình máy tính, nhưng nó
cũng rất bổ ích cho các độc giả khác cần có hiểu biết đầy đủ hơn về CTDL và giải
thuật.
Giáo trình này gồm bốn chương
Chương 1. Giới thiệu về cấu trúc dữ liệu và giải thuật
Chương 2. Kiểu dữ liệu nâng cao
Chương 3. Danh sách
Chương 4. Ngăn xếp và hàng đợi
Chương 5. Sắp xếp và tìm kiếm
Để biên soạn giáo trình này, chúng tôi đã tham khảo các tài liệu: Cấu trúc dữ
liệu và giải thuật, PTS Đinh Mạnh Tường; Lê Minh Hoàng, Cấu trúc dữ liệu và
giải thuật.
Giáo trình Cấu trúc dữ liệu và giải thuật đã được Hổi đồng thẩm định
Trường Cao đẳng nghề Cơ Giới Ninh Bình xét duyệt. Tuy nhiên trong quá trình
biên soạn không tránh khỏi những sai sót, rất mong được sự đóng góp quý báu
chân thành của bạn đọc.
Ninh Bình, ngày tháng năm 2018
Tham gia biên soạn:
1. Chủ biên Đoàn Xuân Luận
2. Phạm Thị Thoa
3. Nguyễn Anh Văn
3
Mục lục
Lời giới thiệu ............................................................................................................. 3
Mục lục ...................................................................................................................... 4
Chương 1 ................................................................................................................... 8
Giới thiệu cấu trúc dữ liệu và giải thuật .................................................................... 8
1. Mối liên hệ giữa cấu trúc dữ liệu và giải thuật .................................................. 9
1.1. Xây dựng cấu trúc dữ liệu .......................................................................... 9
1.2. Xây dựng giải thuật .................................................................................... 9
1.3. Mối quan hệ giữa cấu trúc dữ liệu và giải thuật ....................................... 10
2. Kiểu dữ liệu và mô hình dữ liệu ...................................................................... 10
2.1. Biểu diễn dữ liệu ....................................................................................... 10
2.3. Hệ kiểu của ngôn ngữ Pascal .................................................................... 14
2.4. Mô hình dữ liệu và kiểu dữ liệu trừu tượng .............................................. 16
3. Thiết kế và giải thuật ....................................................................................... 20
3.1. Các tiêu chuẩn đánh giá cấu trúc dữ liệu .................................................. 20
3.2. Đánh giá độ phức tạp của thuật toán ........................................................ 21
Chương 2 ................................................................................................................. 22
Các kiểu dữ liệu nâng cao ........................................................................................ 22
1. Mảng ............................................................................................................... 22
2. Con trỏ ............................................................................................................. 24
2.1. Con trỏ và địa chỉ ..................................................................................... 24
2.2. Con trỏ và mảng một chiều ...................................................................... 26
2.2.2. Tên mảng là một hằng địa chỉ .............................................................. 26
2.2.3. Con trỏ trỏ tới các phần tử của mảng một chiều ................................... 26
2.3. Con trỏ và mảng nhiều chiều ................................................................... 30
2.4. Kiểu con trỏ, kiểu địa chỉ, các phép toán trên con trỏ ............................. 32
3. Cấu trúc và hợp ............................................................................................... 39
3.1. Cấu trúc (struct) ........................................................................................ 39
3.2. Kiểu union ................................................................................................ 40
4. File ................................................................................................................... 41
4.1. Khái niệm về tệp tin ................................................................................. 41
4
4.2. Khai báo sử dụng tệp - một số hàm thường dùng khi thao tác trên tệp ... 43
Chươ ng 3 ................................................................................................................. 49
Danh sách ................................................................................................................ 49
1. Các khái niệm ............................................................................................. 49
1.1. Khái niệm về danh sách ............................................................................ 49
1.2. Các phép toán trên danh sách ................................................................... 49
2. Lưu tữ kế tiếp đối với danh sách tuyến tính ................................................... 51
2.1. Định nghĩa ................................................................................................ 51
2.2. Danh sách liên kết đơn (Singly Linked List) ............................................ 51
3. Lưu trữ móc nối đối với danh sách tuyến tính ............................................... 76
3.1. Cấu trúc dữ liệu ........................................................................................ 76
3.2. Các thao tác trên danh sách ..................................................................... 78
Chương 4 ............................................................................................................... 100
Ngăn xếp và hàng đợi ............................................................................................ 100
1. Định nghĩa ngăn xếp (stack) ......................................................................... 100
2. Lưu trữ stack bằng mảng .............................................................................. 102
2.1. Khởi tạo ngăn xếp ................................................................................... 102
2.2. Thêm (Đẩy) một phần tử vào ngăn xếp (Push) ....................................... 102
2.3. Lấy nội dung một phần tử trong ngăn xếp ra để xử lý (Pop) .................. 103
2.4. Hủy ngăn xếp .......................................................................................... 104
3.Ví dụ về ứng dụng stack ................................................................................. 104
4. Định nghĩa hàng đợi(Queue) .................................................................... 108
5. Lưu trữ queue bằng mảng ........................................................................ 110
5.1. Khởi tạo hàng đợi (Initialize) ................................................................. 110
5.2. Thêm (Đưa) một phần tử vào hàng đợi (Add) ........................................ 111
5.3. Lấy nội dung một phần tử trong hàng đợi ra để xử lý (Get) ................... 112
5.4. Hủy hàng đợi .......................................................................................... 113
6. Stack và queue móc nối ................................................................................. 113
6.1. Stack móc nối ......................................................................................... 113
6.2. Queue móc nối ........................................................................................ 116
Chương 5 ............................................................................................................... 119
5