Xem mẫu
TRƯỜNG ĐẠI HỌC ĐÀ LẠT
KHOA CÔNG NGHỆ THÔNG TIN
NGUYỄN THỊ THANH BÌNH TRẦN TUẤN MINH
GIÁO TRÌNH
CẤU TRÚC DỮ LIỆU VÀ THUẬT GIẢI 1
Dành cho sinh viên ngành Công Nghệ Thông Tin
Đà Lạt - 2010
Cấu trúc dữ liệu và thuật giải 1
MỤC LỤC
MỤC LỤC LỜI NÓI ĐẦU
Chương 1. Giới Thiệu Cấu Trúc Dữ Liệu Và Phân Tích Thuật Giải
1.1.
.........................................................................................................4
Từ bài toán đến chương trình............................................................................................. 4
1.1.1 Mô hình hóa bài toán thực tế ............................................................................................ 4 1.1.2 Thuật giải (algorithms) ..................................................................................................... 7 1.2. Kiểu dữ liệu trừu tượng (Abstract Data Type - ADT) ..................................................... 12 1.2.1 Khái niệm trừu tượng hóa ............................................................................................... 12 1.2.2 Trừu tượng hóa chương trình.......................................................................................... 12 1.2.3 Trừu tượng hóa dữ liệu ................................................................................................... 13 1.2.4 Kiểu dữ liệu, cấu trúc dữ liệu và kiểu dữ liệu trừu tượng (Data Types, Data Structures, Abstract Data Types) ............................................................................................................... 14 1.3. PHÂN TÍCH THUẬT GIẢI ............................................................................................ 15 Thuật giải và các vấn đề liên quan........................................................................... 15 Tính hiệu quả của thuật giải..................................................................................... 16 Ký hiệu O và biểu diễn thời gian chạy bởi ký hiệu O.............................................. 19 Đánh giá thời gian chạy của thuật giải..................................................................... 23 1.3.1 1.3.2 1.3.3 1.3.4
Chương 2. Tìm kiếm và sắp xếp trong .............................................35
2.1 Các phương pháp tìm kiếm trong .................................................................................... 35 Tìm kiếm nhị phân ................................................................................................... 37 Thuật giải sắp xếp chọn (Selection Sort) ................................................................. 40 Thuật giải sắp xếp chèn (Insertion Sort) .................................................................. 43 Thuật giải sắp xếp đổi chỗ trực tiếp (Interchange Sort)........................................... 46 Thuật giải sắp xếp nổi bọt (Bubble Sort) ................................................................. 48 Thuật giải shaker (Shaker Sort) ............................................................................... 50 2.1.1. Phương pháp tìm kiếm tuyến tính.................................................................................. 35 2.1.2. 2.2. 2.2.1. 2.2.2. 2.2.3. 2.2.4. 2.2.5. Các phương pháp sắp xếp trong....................................................................................... 39
1
Cấu trúc dữ liệu và thuật giải 1 2.2.6. 2.2.7. 2.2.8. 2.2.9. 2.2.10. Thuật giải Shell (Shell Sort) .................................................................................... 51 Thuật giải vun đống (Heap Sort) ............................................................................. 53 Thuật giải sắp xếp nhanh (Quick Sort) .................................................................... 57 Thuật giải sắp xếp trộn (Merge Sort)....................................................................... 61 Phương pháp sắp xếp theo cơ số (Radix Sort)......................................................... 66
Chương 3. Cấu trúc danh sách liên kết ...........................................76
3.1 Giới thiệu đối tượng dữ liệu con trỏ ................................................................................ 76 Cấu trúc dữ liệu tĩnh và cấu trúc dữ liệu động......................................................... 76 Kiểu con trỏ.............................................................................................................. 76 Định nghĩa................................................................................................................ 79 Tổ chức danh sách liên kết....................................................................................... 80 Tổ chức danh sách theo cách cấp phát liên kết........................................................ 81 Định nghĩa cấu trúc danh sách liên kết .................................................................... 82 Các thao tác cơ bản trên danh sách liên kết đơn ...................................................... 84 3.1.1. 3.1.2. 3.2. 3.2.1. 3.2.2. 3.3. 3.3.1. 3.3.2. 3.3.3. 3.4. 3.5. 3.6
Danh sách liên kết............................................................................................................ 79
Danh sách liên kết đơn..................................................................................................... 81
Cài đặt tập hợp bằng danh sách liên kết đơn ................................................................. 101 Cài đặt đa thức rời rạc bằng danh sách liên kết đơn. ..................................................... 105 Một số cấu trúc đặc biệt của danh sách liên kết đơn...................................................... 110 Ngăn xếp (Stack).................................................................................................... 110 Hàng đợi (Queue)................................................................................................... 122 Danh sách liên kết vòng......................................................................................... 128 Danh sách liên kết kép ........................................................................................... 131
3.6.1 3.6.2 3.7 3.7.1 3.7.2
Một số cấu trúc dữ liệu dạng danh sách liên kết khác ................................................... 128
TÀI LIỆU THAM KHẢO .......................................................................147
2
Cấu trúc dữ liệu và thuật giải 1
LỜI NÓI ĐẦU
Cấu trúc dữ liệu và thuật giải là kiến thức nền tảng của chương trình đào tạo ngành công nghệ thông tin. Trong hệ thống tín chỉ của chương trình đào tạo tại khoa Công nghệ thông tin trường Đại học Đà Lạt, lĩnh vực này được tổ chức thành 2 học phần: cấu trúc dữ liệu và thuật giải 1, cấu trúc dữ liệu và thuật giải 2 Nội dung học phần cấu trúc dữ liệu và thuật giải 1 được tổ chức trong 3 chương: • Chương 1 trình bày tổng quan về cấu trúc dữ liệu và thuật giải. o Các bước trong lập trình để giải quyết cho một bài toán, o Các khái niệm kiểu dữ liệu, kiểu dữ liệu trừu tượng, o Tiếp cận phân tích thuật giải. • Chương 2 trình bày các phương pháp tìm kiếm và sắp xếp trong. o Phương pháp tìm kiếm tuyến tính, tìm kiếm nhị phân; o Các thuật giải sắp xếp: Chọn trực tiếp, Chèn trực tiếp, đổi chỗ trực tiếp, Heap sort, Quick sort, . . • Chương 3 trình bày cấu trúc dữ liệu danh sách liên kết. o Định nghĩa và tổ chức danh sách liên kết o Danh sách liên kết đơn: định nghĩa, cách tổ chức và các thao tác cơ bản o Các cấu trúc đặc biệt của danh sách liên kết đơn: Ngăn xếp, Hàng đợi o Các cấu trúc dữ liệu dạng danh sách liên kết khác như danh sách liên kết vòng, danh sách liên kết kép. Vì trình độ người biên soạn có hạn nên tập giáo trình không tránh khỏi nhiều khiếm khuyết, Chúng tôi rất mong sự góp ý của các bạn đồng nghiệp và sinh viên. Cuối cùng, Chúng tôi cảm ơn sự động viên, giúp đỡ của các bạn đồng nghiệp trong khoa Công nghệ thông tin để tập giáo trình tóm tắt này được hoàn thành. Các tác giả
3
Cấu trúc dữ liệu và thuật giải 1
Chương 1.
Mục tiêu
Giới Thiệu Cấu Trúc Dữ Liệu Và Phân Tích Thuật Giải
Sau khi học xong chương này, sinh viên sẽ: Nắm được các bước trong lập trình để giải quyết cho một bài toán. Nắm vững khái niệm kiểu dữ liệu trừu tượng, sự khác nhau giữa kiểu dữ liệu, kiểu dữ liệu trừu tượng và cấu trúc dữ liệu. Tiếp cận phân tích thuật giải
Kiến thức cơ bản cần thiết Các kiến thức cơ bản cần thiết để học chương này bao gồm: Khả năng nhận biết và giải quyết bài toán theo hướng tin học hóa. Nội dung cốt lõi Chương này chúng ta sẽ nghiên cứu các vấn đề sau: 1.1. Cách tiếp cận từ bài toán đến chương trình Kiểu dữ liệu trừu tượng (Abstract Data Type). Kiểu dữ liệu – Kiểu dữ liệu trừu tượng – Cấu trúc dữ liệu. Phân tích thuật giải
Từ bài toán đến chương trình
1.1.1 Mô hình hóa bài toán thực tế Để giải một bài toán trong thực tế bằng máy tính ta phải bắt đầu từ việc xác định bài toán. Nhiều thời gian và công sức bỏ ra để xác định bài toán cần giải quyết, tức là phải trả lời rõ ràng câu hỏi "phải làm gì?" sau đó là "làm như thế nào?". Thông thường, khi khởi đầu, hầu hết các bài toán là không đơn giản, không rõ ràng. Để giảm bớt sự phức
4
nguon tai.lieu . vn
KHOA CÔNG NGHỆ THÔNG TIN
NGUYỄN THỊ THANH BÌNH TRẦN TUẤN MINH
GIÁO TRÌNH
CẤU TRÚC DỮ LIỆU VÀ THUẬT GIẢI 1
Dành cho sinh viên ngành Công Nghệ Thông Tin
Đà Lạt - 2010
Cấu trúc dữ liệu và thuật giải 1
MỤC LỤC
MỤC LỤC LỜI NÓI ĐẦU
Chương 1. Giới Thiệu Cấu Trúc Dữ Liệu Và Phân Tích Thuật Giải
1.1.
.........................................................................................................4
Từ bài toán đến chương trình............................................................................................. 4
1.1.1 Mô hình hóa bài toán thực tế ............................................................................................ 4 1.1.2 Thuật giải (algorithms) ..................................................................................................... 7 1.2. Kiểu dữ liệu trừu tượng (Abstract Data Type - ADT) ..................................................... 12 1.2.1 Khái niệm trừu tượng hóa ............................................................................................... 12 1.2.2 Trừu tượng hóa chương trình.......................................................................................... 12 1.2.3 Trừu tượng hóa dữ liệu ................................................................................................... 13 1.2.4 Kiểu dữ liệu, cấu trúc dữ liệu và kiểu dữ liệu trừu tượng (Data Types, Data Structures, Abstract Data Types) ............................................................................................................... 14 1.3. PHÂN TÍCH THUẬT GIẢI ............................................................................................ 15 Thuật giải và các vấn đề liên quan........................................................................... 15 Tính hiệu quả của thuật giải..................................................................................... 16 Ký hiệu O và biểu diễn thời gian chạy bởi ký hiệu O.............................................. 19 Đánh giá thời gian chạy của thuật giải..................................................................... 23 1.3.1 1.3.2 1.3.3 1.3.4
Chương 2. Tìm kiếm và sắp xếp trong .............................................35
2.1 Các phương pháp tìm kiếm trong .................................................................................... 35 Tìm kiếm nhị phân ................................................................................................... 37 Thuật giải sắp xếp chọn (Selection Sort) ................................................................. 40 Thuật giải sắp xếp chèn (Insertion Sort) .................................................................. 43 Thuật giải sắp xếp đổi chỗ trực tiếp (Interchange Sort)........................................... 46 Thuật giải sắp xếp nổi bọt (Bubble Sort) ................................................................. 48 Thuật giải shaker (Shaker Sort) ............................................................................... 50 2.1.1. Phương pháp tìm kiếm tuyến tính.................................................................................. 35 2.1.2. 2.2. 2.2.1. 2.2.2. 2.2.3. 2.2.4. 2.2.5. Các phương pháp sắp xếp trong....................................................................................... 39
1
Cấu trúc dữ liệu và thuật giải 1 2.2.6. 2.2.7. 2.2.8. 2.2.9. 2.2.10. Thuật giải Shell (Shell Sort) .................................................................................... 51 Thuật giải vun đống (Heap Sort) ............................................................................. 53 Thuật giải sắp xếp nhanh (Quick Sort) .................................................................... 57 Thuật giải sắp xếp trộn (Merge Sort)....................................................................... 61 Phương pháp sắp xếp theo cơ số (Radix Sort)......................................................... 66
Chương 3. Cấu trúc danh sách liên kết ...........................................76
3.1 Giới thiệu đối tượng dữ liệu con trỏ ................................................................................ 76 Cấu trúc dữ liệu tĩnh và cấu trúc dữ liệu động......................................................... 76 Kiểu con trỏ.............................................................................................................. 76 Định nghĩa................................................................................................................ 79 Tổ chức danh sách liên kết....................................................................................... 80 Tổ chức danh sách theo cách cấp phát liên kết........................................................ 81 Định nghĩa cấu trúc danh sách liên kết .................................................................... 82 Các thao tác cơ bản trên danh sách liên kết đơn ...................................................... 84 3.1.1. 3.1.2. 3.2. 3.2.1. 3.2.2. 3.3. 3.3.1. 3.3.2. 3.3.3. 3.4. 3.5. 3.6
Danh sách liên kết............................................................................................................ 79
Danh sách liên kết đơn..................................................................................................... 81
Cài đặt tập hợp bằng danh sách liên kết đơn ................................................................. 101 Cài đặt đa thức rời rạc bằng danh sách liên kết đơn. ..................................................... 105 Một số cấu trúc đặc biệt của danh sách liên kết đơn...................................................... 110 Ngăn xếp (Stack).................................................................................................... 110 Hàng đợi (Queue)................................................................................................... 122 Danh sách liên kết vòng......................................................................................... 128 Danh sách liên kết kép ........................................................................................... 131
3.6.1 3.6.2 3.7 3.7.1 3.7.2
Một số cấu trúc dữ liệu dạng danh sách liên kết khác ................................................... 128
TÀI LIỆU THAM KHẢO .......................................................................147
2
Cấu trúc dữ liệu và thuật giải 1
LỜI NÓI ĐẦU
Cấu trúc dữ liệu và thuật giải là kiến thức nền tảng của chương trình đào tạo ngành công nghệ thông tin. Trong hệ thống tín chỉ của chương trình đào tạo tại khoa Công nghệ thông tin trường Đại học Đà Lạt, lĩnh vực này được tổ chức thành 2 học phần: cấu trúc dữ liệu và thuật giải 1, cấu trúc dữ liệu và thuật giải 2 Nội dung học phần cấu trúc dữ liệu và thuật giải 1 được tổ chức trong 3 chương: • Chương 1 trình bày tổng quan về cấu trúc dữ liệu và thuật giải. o Các bước trong lập trình để giải quyết cho một bài toán, o Các khái niệm kiểu dữ liệu, kiểu dữ liệu trừu tượng, o Tiếp cận phân tích thuật giải. • Chương 2 trình bày các phương pháp tìm kiếm và sắp xếp trong. o Phương pháp tìm kiếm tuyến tính, tìm kiếm nhị phân; o Các thuật giải sắp xếp: Chọn trực tiếp, Chèn trực tiếp, đổi chỗ trực tiếp, Heap sort, Quick sort, . . • Chương 3 trình bày cấu trúc dữ liệu danh sách liên kết. o Định nghĩa và tổ chức danh sách liên kết o Danh sách liên kết đơn: định nghĩa, cách tổ chức và các thao tác cơ bản o Các cấu trúc đặc biệt của danh sách liên kết đơn: Ngăn xếp, Hàng đợi o Các cấu trúc dữ liệu dạng danh sách liên kết khác như danh sách liên kết vòng, danh sách liên kết kép. Vì trình độ người biên soạn có hạn nên tập giáo trình không tránh khỏi nhiều khiếm khuyết, Chúng tôi rất mong sự góp ý của các bạn đồng nghiệp và sinh viên. Cuối cùng, Chúng tôi cảm ơn sự động viên, giúp đỡ của các bạn đồng nghiệp trong khoa Công nghệ thông tin để tập giáo trình tóm tắt này được hoàn thành. Các tác giả
3
Cấu trúc dữ liệu và thuật giải 1
Chương 1.
Mục tiêu
Giới Thiệu Cấu Trúc Dữ Liệu Và Phân Tích Thuật Giải
Sau khi học xong chương này, sinh viên sẽ: Nắm được các bước trong lập trình để giải quyết cho một bài toán. Nắm vững khái niệm kiểu dữ liệu trừu tượng, sự khác nhau giữa kiểu dữ liệu, kiểu dữ liệu trừu tượng và cấu trúc dữ liệu. Tiếp cận phân tích thuật giải
Kiến thức cơ bản cần thiết Các kiến thức cơ bản cần thiết để học chương này bao gồm: Khả năng nhận biết và giải quyết bài toán theo hướng tin học hóa. Nội dung cốt lõi Chương này chúng ta sẽ nghiên cứu các vấn đề sau: 1.1. Cách tiếp cận từ bài toán đến chương trình Kiểu dữ liệu trừu tượng (Abstract Data Type). Kiểu dữ liệu – Kiểu dữ liệu trừu tượng – Cấu trúc dữ liệu. Phân tích thuật giải
Từ bài toán đến chương trình
1.1.1 Mô hình hóa bài toán thực tế Để giải một bài toán trong thực tế bằng máy tính ta phải bắt đầu từ việc xác định bài toán. Nhiều thời gian và công sức bỏ ra để xác định bài toán cần giải quyết, tức là phải trả lời rõ ràng câu hỏi "phải làm gì?" sau đó là "làm như thế nào?". Thông thường, khi khởi đầu, hầu hết các bài toán là không đơn giản, không rõ ràng. Để giảm bớt sự phức
4