Tác giả | Hoàng Nghĩa Tý |
ISBN | 978-604-82-7419-1 |
ISBN điện tử | 978-604-82-4412-5 |
Khổ sách | 17x24 cm |
Năm xuất bản (tái bản) | 2023 |
Danh mục | Hoàng Nghĩa Tý |
Số trang | 267 |
Ngôn ngữ | vi |
Loại sách | Ebook;Sách giấy; |
Quốc gia | Việt Nam |
Cấu trúc dữ liệu và thuật toán là môn học cơ sở ngành của ngành công nghệ thông tin. Chúng ta hãy hình dung một tòa nhà có phần nền móng, phần tường cột (kết cấu chịu lực) và những phần khác còn lại, nếu phần kết cấu chịu lực không vững thì tòa nhà không thể vững được. Môn "Cấu trúc dữ liệu và thuật toán" chính là môn học thuộc phần rường cột, phần kết cấu chịu lực đó của tòa nhà "Công nghệ thông tin". Khi học môn học này đòi hỏi sinh viên phải có đầu óc tư duy logic toán học để hiểu thuật toán, đồng thời phải có kỹ năng lập trình để diễn đạt sơ đồ thuật toán thành câu lệnh. Có thể sơ đồ thuật toán vẽ hết cả một trang giấy nhưng chuyển sang lập trình chỉ có vài dòng; có thể sơ đồ thuật toán trình bày theo kiểu kiểm tra điều kiện để tiếp tục ngay ở đầu nhưng khi chuyển sang lập trình có thể dùng các câu lệnh có cấu trúc điều khiển lặp với kiểu kiểm tra điều kiện trước hoặc sau...
Giáo trình "Cấu trúc dữ liệu và thuật toán" này được xuất bản lần đầu năm 2006, do Nhà xuất bản Xây dựng ấn hành. Từ đó đến nay thời lượng cũng như kết cấu môn học đã cố nhiều thay đổi. Ở Trường Đại học Xây dựng từ năm 2009 môn "Cấu trúc dữ liệu và thuật toán" đã được tách thành hai học phần là "Nhập môn Cấu trúc dữ liệu và thuật toán" và "Cấu trúc dữ liệu và thuật toán nâng cao" với mỗi học phần có 2 tín chỉ. Lý do là vì trong Khoa Công nghệ thông tin có nhiều chuyên ngành khác nhau, có chuyên ngành chỉ cần học một học phần, có chuyên ngành cần phải học cả hai học phần.
Để đáp ứng sự thay đổi trên, trong mấy năm qua tác giả đã biên soạn lại đê cương chi tiết cho từng học phần và nội dung chương mục tương ứng, đã viết lại một số chương trình cho một số thuật toán, trình bày lại một số sơ đồ thuật toán (hoán vị ma trận thưa, danh sách liên kết, sắp xếp theo kiểu chèn..), viết thêm một số nội dung cho học phần Cấu trúc dữ liệu và thuật toán nâng cao (kiến thức nâng cao về con trỏ, đệ quy, duyệt cây nhị phân, file mã, file text, danh sách liên kết, danh sách liên kết vòng và liên kết đôi...).
Lời nói đầu | 3 |
PHẦN 1. CẤU TRÚC DỮ LIỆU |
|
Chương 1. Nhập môn cấu trúc dữ liệu |
|
1.1. Khái niệm cấu trúc dữ liệu | 5 |
1.2. Các mô hình dữ liệu | 9 |
Chương 2. Cấu trúc dữ liệu tuyến tính |
|
2.1. Mảng - Arrays | 18 |
2.2. Ngăn xếp - Stacks | 26 |
2.3. Hàng Đợi - Queue | 32 |
2.4. Danh sách - List | 38 |
2.5. Bài tập | 42 |
Chương 3. Cấu trúc dữ liệu phi tuyến |
|
3.1. Bản ghi - RECORD | 46 |
3.2. Kiểu dữ liệu tệp | 53 |
3.3. Kiểu dữ liệu tập hợp | 68 |
3.4. Con trỏ và cấu trúc dữ liệu động | 72 |
3.5. Danh sách liên kết | 81 |
3.6. Ngăn xếp và hàng đợi liên kết | 104 |
3.7. Phép đệ quy | 108 |
3.8. Cây - Tree | 112 |
3.9. Bài tập | 120 |
PHẦN II. THUẬT TOÁN |
|
Chương 4. Nhập môn thuật toán |
|
4.1. Xuất xứ của thuật toán | 123 |
4.2. Các phương pháp trình bày thuật toán | 126 |
4.3. Bài tập | 129 |
Chương 5. Các dạng thuật toán cơ bản |
|
5.1. Thuật toán có cấu trúc | 130 |
5.2. Thuật toán của bài toán tuần tự | 133 |
5.3. Thuật toán rẽ nhánh đơn giản | 134 |
5.4. Thuật toán rẽ nhánh theo nhiều trường hợp | 136 |
5.5. Thuật toán bài toán lặp (chu trình) | 137 |
Chương 6. Phân tích thuật toán |
|
6.1. Khái niệm | 153 |
6.2. Độ hiệu quả và độ phức tạp của thuật toán | 154 |
Chương 7. Các thuật toán sắp xếp |
|
7.1. Sắp xếp bằng chọn lựa đơn giản cho mảng | 159 |
7.2. Sắp xếp theo chọn lựa đơn giản cho danh sách liên kết | 160 |
7.3. Sắp xếp kiểu nổi bọt - sắp xếp dần | 162 |
7.4. Sắp xếp kiểu chèn | 164 |
7.5. Sắp xếp nhanh | 166 |
7.8. Sắp xếp trộn - Mergesort | 169 |
Chương 8. Các thuật toán tìm kiếm |
|
8.1. Tìm kiếm trong danh sách | 172 |
8.2. Cây tìm kiếm nhị phân | 174 |
8.3. Tìm lời giải tối ưu trên sơ đồ mạng | 175 |
Chương 9. Quy hoạch động |
|
9.1. Khái niên chung | 190 |
9.2. Nguyên lý tối ưu Bellman | 194 |
9.3. Áp dụng quy hoạch động trong thiết kế xây dựng đường | 207 |
Phụ lục | 217 |