Giáo trình Cấu trúc dữ liệu và giải thuật 1 - Trương Chí Tín

Giáo trình này nhằm cung cấp cho sinh viên các kiến thức căn bản về các cấu trúc dữ liệu cơ sở có cấu trúc tuyến tính tĩnh, động (danh sách liên kết), cấu trúc cây và các giải thuật cơ bản liên quan đến chúng như sắp xếp, tìm kiếm ở bộ nhớ trong, cũng như so sánh độ phức tạp của các giải thuật này. Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Giáo trình Cấu trúc dữ liệu và giải thuật 1 - Trương Chí Tín TRÖÔØNG ÑAÏI HOÏC ÑAØ LAÏT KHOA TOAÙN - TIN HOÏC TRÖÔNG CHÍ TÍN CAÁU TRUÙC DÖÕ LIEÄU VAØ GIAÛI THUAÄT 1 (Giaùo Trình) -- Löu haønh noäi boä -- Ñaø Laït 2008 LỜI MỞ ĐẦU Giáo trình này nhằm cung cấp cho sinh viên các kiến thức căn bản về các cấu trúc dữ liệu cơ sở có cấu trúc tuyến tính tĩnh, động (danh sách liên kết), cấu trúc cây và các giải thuật cơ bản liên quan đến chúng như sắp xếp, tìm kiếm ở bộ nhớ trong, cũng như so sánh độ phức tạp của các giải thuật này. Để có thể nắm bắt các kiến thức trình bày học phần này, sinh viên cần nắm được các kiến thức về tin học đại cương, nhập môn lập trình. Ngôn ngữ lập trình được chọn để minh họa các kiến thức trên là C++. Các kiến thức này sẽ tạo điều kiện cho học viên tiếp tục dễ dàng nắm bắt các kiến thức các học phần tin học về sau như: cấu trúc dữ liệu và giải thuật nâng cao, phân tích và thiết kế giải thuật, đồ hoạ, hệ điều hành, trí tuệ nhân tạo, ... Nội dung giáo trình gồm 4 chương: - Chương 1: Giới thiệu các khái niệm ban đầu về mối liên hệ mật thiết giữa cấu trúc dữ liệu và giải thuật, kiểu dữ liệu, thiết kế và phân tích giải thuật, độ phức tạp giải thuật, ... - Chương 2: Giới thiệu các phương pháp cơ bản về tìm kiếm và sắp xếp trong trên kiểu dữ liệu tuyến tính mảng. Thông qua đó, trình bày một số ý tưởng và kỹ thuật cơ bản nhằm cải tiến các giải thuật. - Chương 3: Trình bày kiểu dữ liệu con trỏ. Trên cơ sở đó, trình bày các kiểu dữ liệu động tuyến tính và có nhiều ứng dụng trong tin học là các kiểu danh sách liên kết khác nhau, ngăn xếp, hàng đợi, cũng như một số ứng dụng của chúng. - Chương 4: Giới thiệu một loại cấu trúc dữ liệu động khác là cây và các thao tác cơ bản trên cây nhị phân, cây nhị phân tìm kiếm, cây cân bằng AVL. Nhằm mục đích dành thời gian nhiều hơn cho sinh viên để làm các bài tập lớn, nên trong một số phần tác giả đã trình bày khá chi tiết các dạng cài đặt biến thể khác nhau cho các giải thuật. Các phần thứ yếu hoặc khá phức tạp sẽ được in cỡ chữ nhỏ dành cho sinh viên đọc thêm. Chắn chắn rằng trong giáo trình sẽ còn nhiều khiếm khuyết, tác giả mong muốn nhận được và rất biết ơn các ý kiến quí báu đóng góp của đồng nghiệp cũng như bạn đọc để giáo trình này có thể hoàn thiện hơn nữa về mặt nội dung cũng như hình thức trong lần tái bản sau. Đà lạt, 04/2008 Tác giả MỤC LỤC Chương I. GIỚI THIỆU CẤU TRÚC DỮ LIỆU, PHÂN TÍCH GIẢI THUẬT Trang I.1. Quan hệ giữa cấu trúc dữ liệu và giải thuật, kiểu dữ liệu I.1 I.1.1. Biểu diễn dữ liệu I.1 I.1.2. Quan hệ giữa cấu trúc dữ liệu và giải thuật, kiểu dữ liệu I.1 I.1.3. Các bước chính để giải một bài toán trên máy tính I.2 I.2. Thiết kế và phân tích giải thuật I.4 I.2.1. Thiết kế giải thuật theo phương pháp Top-Down I.4 I.2.2. Các chiến lược khác để thiết kế giải thuật I.5 I.2.3. Phân tích giải thuật và độ phức tạp của giải thuật I.5 I.2.4. Qui ước về ngôn ngữ mã giả I.9 Chương II. TÌM KIẾM VÀ SẮP XẾP TRONG II.1. Giới thiệu về sắp xếp và tìm kiếm II.1 II.1.1. Sắp xếp II.1 a. Định nghĩa sắp xếp II.1 b. Phân loại phương pháp sắp xếp II.1 c. Vài qui uớc về kiểu dữ liệu khi xét các giải thuật sắp xếp II.1 II.1.2. Tìm kiếm II.3 a. Định nghĩa phép tìm kiếm II.3 b. Phân loại các phương pháp tìm kiếm II.3 II.2. Phương pháp tìm kiếm trong II.3 II.2.1. Phương pháp tìm kiếm tuyến tính II.3 a. Dãy chưa được sắp II.3 b. Dãy đã được sắp II.5 II.2.2. Phương pháp tìm kiếm nhị phân II.6 II.3. Phương pháp sắp xếp trong II.7 II.3.1. Phương pháp sắp xếp chọn đơn giản II.8 II.3.2. Phương pháp sắp xếp chèn đơn giản II.9 II.3.3. Phương pháp sắp xếp đổi chỗ đơn giản II.10 II.3.4. Phương pháp sắp xếp đổi chỗ cải tiến (Shake Sort) II.12 II.3.5. Phương pháp sắp xếp chèn cải tiến (Shell Sort) II.14 II.3.6. Phương pháp sắp xếp phân hoạch (Quick Sort) II.16 II.3.7. Phương pháp sắp xếp trên cây có thứ tự (HeapSort) II.19 II.3.8. Phương pháp sắp xếp trộn (Merge Sort) II.25 II.3.9. Phương pháp sắp xếp dựa trên cơ số (Radix Sort) II.28 II.3.10. So sánh các phương pháp sắp xếp trong II.31 Trang Chương III. CẤU TRÚC DANH SÁCH LIÊN KẾT III.1. Giới thiệu đối tượng dữ liệu con trỏ III.1 III.1.1. So sánh cấu trúc dữ liệu tĩnh và cấu trúc dữ liệu động III.1 III.1.2. Kiểu dữ liệu con trỏ ...