BÀI GIẢNG VỀ CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT ( Data structure and algorithms )

Cấu trúc dữ liệu: là tập các dữ liệu có quan hệ với nhau,được tổ chức theo những phương thức nhất định. Giải thuật: là một dãy hữu hạn các thao tác chặt chẽ và rõ ràng được sắp xếp theo một trình tự xác định sao cho sau khi thực hiện dãy thao tác đó, ta nhận được mục tiêu định trước.
Nội dung trích xuất từ tài liệu:
BÀI GIẢNG VỀ CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT ( Data structure and algorithms )Cấu trúc dữ liệu và giải thuật (Data structure and Algorithms) 1 Nội dung chương trìnhChương I TỔNG QUAN VỀ GIẢI THUẬT VÀ CẤU TRÚC DỮ LIỆU I. Khái niệm về cấu trúc dữ liệu và giải thuật II. Một số cú pháp điều khiển III. Đánh giá độ phức tạp của giải thuật 2 Nội dung chương trìnhChương II. TÌM KIẾM VÀ SẮP XẾPI. Các giải thuật tìm kiếm nội 1. Tìm kiếm tuyến tính 2. Tìm kiếm nhị phânII. Các giải thuật sắp xếp nội 1. Chọn trực tiếp (Selection sort) 2. Chèn trực tiếp (Insertion sort) 3. Đổi chỗ trực tiếp (Interchange Sort) 4. Nổi bọt (Buble sort) 5. Sắp xếp cây (Heap sort) 6. Sắp xếp dựa trên phân hoạch (Quick sort) 7. Sắp xếp trộn trực tiếp (Merge sort ) 3 Nội dung chương trìnhChương III. CẤU TRÚC DỮ LIỆU ĐỘNGI. Kiểu dữ liệu con trỏII. Danh sách liên kết-khái niệmIII. Danh sách liên kết đơn 1. Tổ chức danh sách đơn 2. Các thao tác cơ bản trên danh sách đơn a. Tạo danh sách b. Duyệt danh sách c. Chèn phần tử vào danh sách d. Xoá phần tử khỏi danh sách 3. Sắp xếp dánh sách (lý thuyết+đọc thêm) 4. Các cấu trúc đặc biệt của danh sách đơn Stack QueueIV. Một số cấu trúc dữ liệu dạng danh sách liên kết khác 1. Danh sách liên kết kép 2. Hàng đợi 2 đầu 3. Danh sách liên kết có thứ tự 4. Danh sách liên kết vòng 5. Danh sách có nhiều mối liên kết 4 Nội dung chương trìnhChương IV. CẤU TRÚC CÂYI. Khái niệm về câyII. Cây nhị phân 1. Một số tính chất của cây nhị phân 2. Biểu diễn cây nhị phân 3. Duyệt cây nhị phân 4. Biểu diễn cây tổng quátIII. Cây nhị phân tìm kiếm 1. Tìm một phần tử 2. Thêm một phần tử 3. Huỷ một phần tửIV. Cây nhị phân cân bằng 1. Cây nhị phân cân bằng hoàn toàn 2. Cây nhị phân cân bằng 5 Nội dung chương trìnhPhần II.Bài tập+Thực hành + Ceminar- Cài đặt các chương thuật toán trong phần lý thuyết đã học 6 Tài liệu tham khảo1. Trần Hạnh Nhi-Dương Anh Đức, Giáo trình cấu trúc dữ liệu và giải thuật ĐH Quốc gia Tp Hồ Chí Minh1. Đỗ Xuân Lôi, Cấu trúc dữ liệu và giải thuật, NXB Khoa học kỹ thuật, 19962. Robert Sedgewick, Cẩm nang thuật toán, tập 1, NXB Khoa học kỹ thuật, 1994, bản dịch của nhóm tác giả ĐH TH Tp. HCM3. N. Wirth: Algorithms+Data structures=Programs (Prentice Hall, 1976)V v… 7Chương I Tổng quan về các giải thuật và cấu trúc dữ liệu I. Khái niệm về cấu trúc dữ liệu và giải thuật II. Một số cú pháp điều khiển III. Đánh giá độ phức tạp của giải thuật 8I. Khái niệm về cấu trúc dữ liệu và giải thuật 91. Khái niệm bài toán Trong phạm vi tin học, ta có thể quan niệm bài toán (Problems) là công việc mà ta muốn máy tính thực hiện VD: In dòng chữ ra màn hình, giải phương trình bậc 2, quản lý cán bộ trong một cơ quan… * Diễn đạt bài toán thành 2 thành phần Input: Thông tin đầu vào Ví dụ Output: Thông tin đầu ra 102. Khái niệm Cấu trúc dữ liệu và giảithuật Cấu trúc dữ liệu: là tập các dữ liệu có quan hệ với nhau, được tổ chức theo những phương thức nhất định Giải thuật (thuật toán-Algorithm): là một dãy hữu hạn các thao tác chặt chẽ và rõ ràng được sắp xếp theo một trình tự xác định sao cho sau khi thực hiện dãy thao tác đó, ta nhận được mục tiêu định trước 113. Các đặc trưng của giải thuật a. Tính xác định Ở mỗi bước của thuật toán các thao tác phải hết sức rõ ràng: Không thể gây nên sự nhập nhằng, tuỳ tiện. Nói một cách khác là trong cùng một điều kiện, hai bộ xử lý cùng thực hiện một bước của giải thuật thì phải cho cùng một kết quả b. Tính hữu hạn dừng Giải thuật bao giờ cũng phải dừng sau một số hữu hạ ...