ỦY BAN NHÂN DÂN TỈNH TRÀ VINH
TRƯỜNG CAO ĐẲNG NGHỀ TRÀ VINH
GIÁO TRÌNH
MÔN HỌC: CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
NGÀNH, NGHỀ: CÔNG NGHỆ THÔNG TIN
TRÌNH ĐỘ: CAO ĐẲNG NGHỀ
( Ban hành kèm theo Quyết định số: QĐ/CĐN, ngày tháng năm
của Hiệu trưởng trường cao đẳng nghề Trà Vinh)
Trà Vinh, năm 2019
( Lưu hành nội bộ)
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.
LỜI GIỚI THIỆU
Cấu trúc dữ liệu và giải thuật là một môn học bắt buộc trong chương trình đào
tạo Công nghệ thông tin. Giáo trình này cung cấp cho người học một số kiến thức sâu
hơn về các cấu trúc dữ liệu thường dùng trong lập trình.
Trong cuốn giáo trình này sử dụng ngôn ngữ lập trình C để minh họa các cấu trúc
dữ liệu và giải thuật để để giúp người học dễ hình dung hơn trong cài đặt chương trình
thực tế trên máy tính.
Tìm hiểu về “Cấu trúc dữ liệu và giải thuật” là một đòi hỏi cần thiết đối với
những người làm tin học khi muốn tiếp cận với việc lập trình để giải các bài toán trên
máy tính điện tử cũng như khi muốn đi sâu thêm vào các lĩnh vực kiến thức khác của
công nghệ thông tin. Cấu trúc của giáo trình gồm các nội dung sau:
Chương 1: Tổng quan về Cấu trúc dữ liệu và giải thuật
Chương 2: Đệ qui và giải thuật đệ qui
Chương 3: Danh sách
Chương 4: Các phương pháp sắp xếp cơ bản
Chương 5: Tìm kiếm
Để hoàn thành giáo trình này tác giả đã nhận được nhiều ý kiến đóng góp và
động viên của các đồng nghiệp. Bên cạnh đó tác giả cũng tham khảo các giáo trình và
tài liệu giảng dạy môn học Cấu trúc dữ liệu và giải thuật của một số trường Cao đẳng,
Đại học trong và ngoài nước để giáo trình đạt yêu cầu cao về nội dung và thích hợp đối
với đối tượng là sinh viên của trường Cao đẳng nghề Trà Vinh.
Xin chân thành cảm ơn các đồng nghiệp đã đóng góp rất quý báu. Khi viết tác giả
cũng đã cố gắng hết sức để hoàn thiện cuốn giáo trình này. Tuy nhiên, chắc chắn
không tránh khỏi những thiếu sót, vì vậy rất mong được sự góp ý của người học.
Trà Vinh, ngày …. tháng … năm 2019
Tham gia biên soạn
1. Chủ biên, tác giả: Phan Thanh Tú
2. Thành viên: Võ Thị Thu Trang
3. Thành viên: Đào Ngọc Hải
1
MỤC LỤC
LỜI GIỚI THIỆU...................................................................................................................................1
CHƯƠNG 1: TỔNG QUAN VỀ CẤU TRUC DỮ LIỆU VÀ GIẢI THUẬT.......................................4
1. Mối quan hệ giữa CTDL và giải thuật................................................................................................4
2. Các tiêu chuẩn đánh giá CTDL..........................................................................................................5
3. Các kiểu dữ liệu cơ bản......................................................................................................................5
4. Các kiểu dữ liệu có cấu trúc...............................................................................................................7
5. Đánh giá độ phức tạp giải thuật..........................................................................................................9
CHƯƠNG 2: ĐỆ QUI VÀ GIẢI THUẬT DỆ QUI..............................................................................13
1. Giải thuật đệ qui và chương trình đệ qui...........................................................................................13
2. Ưu và nhược điểm của giải thuật đệ qui...........................................................................................14
3. Các bài toán đệ qui căn bản..............................................................................................................14
CHƯƠNG 3: DANH SÁCH.................................................................................................................18
1. Danh sách liên kết đơn.....................................................................................................................18
2. Danh sách liên kết kép......................................................................................................................25
CHƯƠNG 4: CÁC PHƯƠNG PHÁP SẮP XẾP CƠ BẢN..................................................................32
1. Định nghĩa bài toán sắp xếp.............................................................................................................32
2. Phương pháp chọn trực tiếp (Selection sort).....................................................................................33
3. Phương pháp chèn trực tiếp (Insertion sort)......................................................................................36
4. Phương pháp sắp xếp chèn nhị phân (Binary Insertion sort)............................................................38
5. Phương pháp đổi chỗ trực tiếp(Interchange sort)..............................................................................38
6. Phương pháp nổi bọt (Bubble sort)...................................................................................................42
7. Phương pháp sắp xếp nhanh (Quick sort).........................................................................................45
8. Phương pháp sắp xếp trộn (Merge sort)............................................................................................48
CHƯƠNG 5:TÌM KIẾM......................................................................................................................54
1.Tìm kiếm tuyến tính..........................................................................................................................54
2. Tìm kiếm nhị phân........................................................................................................................... 57
TÀI LIỆU THAM KHẢO.................................................................................................................... 60
2
GIÁO TRÌNH MÔN HỌC
Tên môn học: Cấu trúc dữ liệu và giải thuật
Mã môn học: MH 11
Vị trí, tính chất, ý nghĩa và vai trò của môn học:
- Vị trí: Môn học được bố trí sau khi sinh viên học xong các môn học chung, các môn
học cơ sở chuyên ngành đào tạo chuyên môn nghề.
- Tính chất: Môn học chuyên ngành.
- Ý nghĩa và vai trò của môn học: Là môn học chuyên ngành, giúp sinh viên thành
thạo với công việc lập trình có cấu trúc.
Mục tiêu của môn học:
- Về kiến thức:
+ Trình bày được dữ liệu là gì, giải thuật là gì, mối quan hệ mật thiết giữa cấu
trúc dữ liệu và giải thuật.
+ Phân tích được đâu là dữ liệu, đâu là giải thuật, sự kết hợp chúng để tạo thành
một chương trình máy tính.
- Về kỹ năng:
+ Tổ chức dữ liệu hợp lý, khoa học cho một chương trình đơn giản.
+ Áp dụng thuật toán hợp lý nhất đối với cấu trúc dữ liệu tương thích để giải
quyết bài toán tối ưu nhất.
+ Áp dụng được các phương pháp sắp xếp, tìm kiếm từ đơn giản.
- Về năng lực tự chủ và trách nhiệm:
+ Tạo tính sáng tạo trong quá trình tìm kiếm các giải thuật.
+ Tự giác, tính kỷ luật cao, tinh thần trách nhiệm trong học tập.
Nội dung của môn học:
3