TRƯỜNG CAO ĐẲNG NGHỀ CÔNG NGHIỆP HÀ NỘI
Chủ biên: Vũ Thị Kim Phượng Đồng tác giả: Nguyễn Thị Nhung
GIÁO TRÌNH
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
(Lưu hành nội bộ)
Hà Nội năm 2012
Tuyên bố bản quyền
Giáo trình này sử dụng làm tài liệu giảng dạy nội bộ trong trường cao đẳng nghề Công nghiệp Hà Nội
Trường Cao đẳng nghề Công nghiệp Hà Nội không sử dụng và không cho phép bất kỳ cá nhân hay tổ chức nào sử dụng giáo trình này với mục đích kinh doanh.
Mọi trích dẫn, sử dụng giáo trình này với mục đích khác hay ở nơi khác đều phải được sự đồng ý bằng văn bản của trường Cao đẳng nghề Công nghiệp Hà Nội
LỜI NÓI ĐẦU
Giáo trình “Cấu trúc dữ liệu và giải thuật” biên soạn dựa theo đề cương chương trình môn học Cấu trúc dữ liệu và giải thuật thuộc chương trình đào tạo Cao đẳng nghề Quản trị mạng của trường Cao đẳng nghề Công nghiệp Hà nội, ban hành năm 2011, với số tiết là 90h.
Giáo trình gồm 7 chương, đề cập đến những kiến thức cơ bản về cấu trúc dữ liệu và các giải thuật có liên quan. Từng chương trong giáo trình cũng cố gắng gắn kết và phát triển nội dung có liên quan ở các môn học trước hay ở các chương trong giáo trình với nhau, giúp sinh viên nâng cao về kỹ thuật lập trình, về chọn cấu trúc dữ liệu phù hợp và xây dựng các giải thuật giải các bài toán cơ bản.
Giáo trình cố gắng trình bày để phục vụ cho đối tượng sinh viên năm thứ hai vừa học qua một ngôn ngữ lập trình. Trong mỗi chương đều có ví dụ diễn giải làm rõ những định nghĩa, khái niệm và đặc biệt với mỗi giải thuật đều có mô tả và cài đặt giải thuật hoặc ví dụ áp dụng. Cuối mỗi chương là những câu hỏi về lý thuyết và bài tập ở mức độ dễ, vừa, giúp sinh viên củng cố kiến thức.
Cùng với giáo trình này, giáo viên có thể yêu cầu sinh viên tự đọc một số phần, như vậy sẽ có nhiều thời gian giảng kỹ những phần chính, khó hoặc luyện được nhiều bài tập. Bên cạnh đó cũng giúp sinh viên rèn luyện khả năng tự học của bản thân.
Nhóm tác giả chân thành cảm ơn những đồng nghiệp trong khoa Công nghệ thông tin trường Cao đẳng nghề Công nghiệp Hà nội đã tham gia xây dựng đề cương chi tiết giáo trình, đọc bản thảo và đóng góp những ý kiến quý báu.
Nhóm tác giả mong muốn nhận được những ý kiến đóng góp của bạn đọc để nâng cao chất lượng giáo trình cho lần tái bản sau.
Mọi ý kiến đóng góp xin gửi về:
Vũ Thị Kim Phượng
Email: vkphuong2010@gmail.com
Hà Nội, ngày..... tháng....năm 2012
Tham gia biên soạn giáo trình
1. Vũ Thị Kim Phượng – Chủ biên
2. Nguyễn Thị Nhung – Thành viên
MỤC LỤC
MỤC TIÊU CỦA MÔN HỌC 6
NỘI DUNG CỦA MÔN HỌC 6
CHƯƠNG 1:TỔNG QUAN VỀ CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 9
1. Khái niệm cấu trúc dữ liệu và giải thuật, cấu trúc lưu trữ và cấu trúc dữ liệu. 9
1.1. Khái niệm cấu trúc dữ liệu và giải thuật 9
1.2. Cấu trúc dữ liệu và cấu trúc lưu trữ 12
2. Cấu trúc dữ liệu 12
2.1. Các kiểu dữ liệu cơ bản 12
2.2. Các kiểu dữ liệu cấu trúc 13
2.3. Các kiểu dữ liệu trừu tượng 15
2.4. Các tiêu chuẩn đánh giá cấu trúc dữ liệu 15
2.5. Các thao tác cơ bản trên một cấu trúc dữ liệu 15
3. Giải thuật và đánh giá độ phức tạp của giải thuật 16
3.1. Giải thuật 16
3.2. Biểu diễn giải thuật 16
3.2.1. Bằng ngôn ngữ tự nhiên 16
3.2.2. Bằng lưu đồ giải thuật 17
3.2.3. Bằng ngôn ngữ diễn đạt giải thuật (mã giả) 18
3.3. Một số đặc trưng của giải thuật 19
3.4. Đánh giá độ phức tạp của giải thuật 20
3.4.1. Đặt vấn đề 20
3.4.2. Độ phức tạp tính toán của giải thuật 21
3.4.3. Xác định độ phức tạp tính toán của giải thuật 21
CHƯƠNG 2: ĐỆ QUI VÀ GIẢI THUẬT ĐỆ QUI 26
1. Khái niệm đệ qui 26
2. Giải thuật đệ qui và chương trình đệ qui 26
2.1. Giải thuật đệ qui 27
2.2. Chương trình con đệ qui 27
2.3. Đặc điểm của một chương trình con đệ qui: 28
3. Thiết kế giải thuật đệ qui 28
3.1. Giải thuật đệ qui đơn giản 28
3.2. Nguyên tắc thiết kế một giải thuật đệ qui: 30
3.3. Nguyên tắc thực hiện một hàm đệ qui trong máy tính: 33
4. Nhận xét giải thuật đệ qui 33
CHƯƠNG 3: DANH SÁCH 36
1. Danh sách và các phép toán cơ bản trên danh sách 36
1.1. Khái niệm danh sách tuyến tính 36
1.2. Cài đặt danh sách theo cấu trúc mảng 36
1.3. Danh sách liên kết 49
1.3.1. Cài đặt theo cấu trúc danh sách liên kết đơn 49
1.3.2. Cài đặt theo cấu trúc danh sách liên kết kép 61
1.3.3. Cài đặt theo cấu trúc danh sách liên kết nối vòng 68
2. Cài đặt danh sách theo các cấu trúc đặc biệt (ngăn xếp, hàng đợi) 68
2.1. Ngăn xếp (Stack) 68
2.1.1. Khái niệm 68
2.1.2. Các thao cơ bản của Stack 68
2.1.3. Cài đặt Stack bằng mảng 69
2.1.4. Cái đặt Stack bằng danh sách liên kết đơn 74
2.1.5. Ứng dụng của Stack 76
2.2. Hàng đợi (Queue) 77
2.2.1. Khái niệm 77
2.2.2. Các thao cơ bản của Queue 77
2.2.3. Cài đặt Queue bằng mảng 77
2.2.4. Cái đặt Queue bằng danh sách liên kết đơn 80
2.2.5. Ứng dụng của Queue 83
CHƯƠNG 4: CÁC PHƯƠNG PHÁP SĂP XẾP CƠ BẢN 88
1. Định nghĩa bài toán sắp xếp 88
2. Phương pháp sắp xếp chèn (Insertion sort) 89
2.1. Ý tưởng giải thuât Insertion sort 89
2.2. Mô tả giải thuật 89
2.3. Cài đặt giải thuật 90
2.4. Biểu diễn giải thuật 90
3. Phương pháp sắp xếp chọn (Selection sort) 91
3.1. Ý tưởng giải thuật Selection sort 91
3.2. Mô tả giải thuật 91
3.3. Cài đặt giải thuật 91
3.4. Biểu diễn giải thuật 92
4. Phương pháp sắp xếp đổi chỗ (Interchange sort) 93
4.1. Ý tưởng của giải thuật Interchange sort 93
4.2. Mô tả giải thuật 93
4.3. Cài đặt giải thuật 94
4.4. Biểu diễn giải thuật 94
5. Phương pháp sắp xếp nổi bọt (Bubble sort) 95
5.1. Ý tưởng giải thuật Bubble sort 95
5.2. Mô tả giải thuật 95
5.3. Cài đặt giải thuật 96
5.4. Biểu diễn giải thuật 96
6. Phương pháp sắp xếp nhanh (Quick sort) 97
6.1. Ý tưởng giải thuật Quick sort 97
6.2. Mô tả giải thuật 98
6.3. Cài đặt giải thuật 99
6.4. Biểu diễn giải thuật 100
CHƯƠNG 5:TÌM KIẾM 104
1. Bài toán tìm kiếm 104
2. Tìm kiếm tuyến tính 104
2.1. Ý tưởng giải thuật 104
2.2. Mô tả giải thuật 104
2.3. Cài đặt giải thuật 105
2.4. Biểu diễn giải thuật 105
3. Tìm kiếm nhị phân 106
3.1. Ý tưởng giải thuật 106
3.2. Mô tả giải thuật 106
3.3. Cài đặt giải thuật 107
3.4. Biểu diễn giải thuật 107
CHƯƠNG 6: CÂY 110
1. Khái niệm về cây 110
1.1. Khái niệm cây 110
1.2. Một số khái niệm của cây 111
2. Cây nhị phân 111
2.1. Khái niệm cây nhị phân 111
2.2. Một số tính chất của cây nhị phân 111
2.3. Biểu diễn cây nhị phân 112
2.3.1. Lưu trữ cây bằng véc tơ kế tiếp (lưu trữ kế tiếp) 112
2.3.2. Lưu trữ cây bằng danh sách liên kết 114
3. Các phép duyệt cây nhị phân 116
3.1. Duyệt cây theo thứ tự trước (Preorder traversal) 116
3.2. Duyệt cây theo thứ tự giữa (Inorder traversal) 117
3.3. Duyệt cây theo thứ tự sau (Postorder traversal) 118
3.4. Ví dụ áp dụng 118
CHƯƠNG 7: ĐỒ THỊ 124
1. Khái niệm về đồ thị 124
1.1. Định nghĩa 124
1.2. Các khái niệm 124
2. Biểu diễn đồ thị 126
2.1. Biểu diễn bằng ma trận kề 126
2.2. Biểu diễn đồ thị bằng danh sách kề 128
3. Các phép duyệt đồ thị 128
3.1. Duyệt theo chiều sâu (Depth First Search) 128
3.2. Duyệt theo chiều rộng (Bredth First Search) 130
PHỤ LỤC 1 134
Biến con trỏ và cấp phát động 134
1. Khái niệm biến tĩnh, biến động và biến con trỏ 134
2. Khai báo biến con trỏ 135
3. Các phép toán trên biến con trỏ 136
3.1. Toán tử địa chỉ & 136
3.2. Toán tử tham chiếu * 137
3.3. Phép chuyển (ép) kiểu: 139
3.4. Toán tử cộng, trừ con trỏ với một số nguyên và phép tăng giảm
140
3.5. Toán tử so sánh: 140
3.6. Hằng con trỏ 141
3.7. Cấp phát vùng nhớ cho biến con trỏ 143
4. Mối liên quan giữa con trỏ, hàm, mảng, chuỗi và cấu trúc 144
4.1. Biến con trỏ là tham số hình thức của hàm 144
4.2. Biến con trỏ là kiểu kết quả hàm trả về 146
4.3. Sự tương quan giữa con trỏ và mảng 146
4.4. Con trỏ và chuỗi ký tự 149
4.5. Con trỏ và kiểu cấu trúc 154
PHỤ LỤC 2 162
1) Chương trình quản lý điểm sinh viên được cài đặt bằng danh sách liên kết đơn. 162
2) Chương trình chuyển đổi một số hệ 10 sang hệ 2. Sử dụng các thao tác của Stack cài đặt bằng danh sách liên kết đơn để viết chương trình
170
3) Chương trình cài đặt các giải thuật sắp xếp và tìm kiếm với danh sách sinh viên được cài đặt bằng mảng 173
TÀI LIỆU THAM KHẢO 184
MỤC TIÊU:
Kiến thức:
Trình bày được các khái niệm về cấu trúc dữ liệu và giải thuật, kiểu dữ liệu, kiểu dữ liệu trừu tượng (danh sách, cây, đồ thị).
Trình bày được các phép toán cơ bản tương ứng với các cấu trúc dữ liệu và các giải thuật.
Kỹ năng:
Biết cách tổ chức dữ liệu hợp lý, khoa học cho một chương trình đơn giản.
Biết áp dụng thuật toán hợp lý đối với cấu trúc dữ liệu tương ứng để giải quyết bài toán trên máy tính.
Áp dụng được các phương pháp sắp xếp, tìm kiếm cơ bản trong các bài toán khi cần.
NỘI DUNG:
Tên chương, mục | Thời | gian | |||
Tổng số | Lý thuyết | Thực hành | Kiểm tra* (LT hoặcTH) | ||
I | Tổng quan về Cấu trúc dữ liệu và giải thuật | 6 | 4 | 2 | 0 |
Khái niệm cấu trúc dữ liệu và | 2 | 1 | 1 | ||
giải thuật. Mối quan hệ giữa | |||||
CTDL và giải thuật. | |||||
Các kiểu dữ liệu cơ bản | 0.5 | 0.5 | 0 | ||
Các kiểu dữ liệu có cấu trúc | 0.5 | 0.5 | 0 | ||
Các kiểu dữ liệu trừu tượng | 1 | 1 | 0 | ||
Giải thuật và đánh giá độ phức | 2 | 1 | 1 | ||
tạp của giải thuật. | |||||
II | Đệ qui và giải thuật đệ qui | 6 | 3 | 2 | 1 |
Khái niệm đệ qui | 0.5 | 0.5 | 0 | ||
Giải thuật đệ qui và chương trình đệ qui | 0.5 | 0.5 | 0 | ||
Các bài toán đệ qui căn bản | 5 | 2 | 2 | 1 |
Có thể bạn quan tâm!
-
Cấu trúc dữ liệu và giải thuật - CĐN Công nghiệp Hà Nội - 2 -
Giải Thuật Và Đánh Giá Độ Phức Tạp Của Giải Thuật -
Giải Thuật Đệ Qui Và Chương Trình Đệ Qui.
Xem toàn bộ 200 trang tài liệu này.
Danh sách | 30 | 15 | 14 | 1 | |
Danh sách và các phép toán cơ bản trên danh sách | 2 | 2 | 0 | 0 | |
Cài đặt danh sách theo cấu trúc | 4 | 2 | 2 | 0 | |
mảng | |||||
Cài đặt danh sách theo cấu trúc | 12 | 6 | 6 | 0 | |
danh sách liên kết (đơn, kép) | |||||
Cài đặt danh sách theo các cấu | 12 | 5 | 6 | 1 | |
trúc đặc biệt (ngăn xếp, hàng | |||||
đợi) | |||||
IV | Các phương pháp sắp xếp cơ bản | 24 | 12 | 11 | 1 |
Định nghĩa bài toán sắp xếp. | 1 | 1 | 0 | 0 | |
Phương pháp chọn (Selection | 4 | 2 | 2 | 0 | |
sort). | |||||
Phương pháp chèn (Insertion | 4 | 2 | 2 | 0 | |
sort). | |||||
Phương pháp đổi chỗ | 4 | 2 | 2 | 0 | |
(Interchange sort). | |||||
Phương pháp nổi bọt (Bubble | 4 | 2 | 2 | 0 | |
sort). | |||||
Phương pháp sắp xếp nhanh | 7 | 3 | 3 | 1 | |
(Quick sort). | |||||
V | Tìm kiếm. | 6 | 2 | 3 | 1 |
Tìm kiếm tuyến tính. | 2 | 1 | 1 | 0 | |
Tìm kiếm nhị phân. | 4 | 1 | 2 | 1 | |
VI | Cây. | 10 | 5 | 4 | 1 |
Khái niệm về cây và cây nhị | 2 | 2 | 0 | 0 | |
phân. | |||||
Biểu diễn cây nhị phân và cây tổng quát. | 4 | 2 | 2 | 0 | |
Bài toán duyệt cây nhị phân. | 4 | 1 | 2 | 1 | |
VII | Đồ thị. | 8 | 4 | 4 | 0 |
Khái niệm về đồ thị. | 2 | 1 | 1 |