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

Chia sẻ: Vu Van Hieu | Ngày: | Loại File: PPT | Số trang:63

Thêm vào BST

Báo xấu

300
lượt xem 112
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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ình Chươ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ình Chương II. TÌM KIẾM VÀ SẮP XẾP I. 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ân II. 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ình Chương III. CẤU TRÚC DỮ LIỆU ĐỘNG I. Kiểu dữ liệu con trỏ II. Danh sách liên kết-khái niệm III. 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 Queue IV. 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ình Chương IV. CẤU TRÚC CÂY I. Khái niệm về cây II. 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át III. 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ình Phầ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ảo 1. 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í Minh 1. Đỗ Xuân Lôi, Cấu trúc dữ liệu và giải thuật, NXB Khoa học kỹ thuật, 1996 2. 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. HCM 3. N. Wirth: Algorithms+Data structures=Programs (Prentice Hall, 1976) V v… 7
Chươ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 8
I. Khái niệm về cấu trúc dữ liệu và giải thuật 9
1. 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 10
2. Khái niệm Cấu trúc dữ liệu và giải thuậ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 11
3. 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ạn bước 12
3. Các đặc trưng của giải thuật c. Tính đúng đắn Sau khi thực hiện tất cả các thao tác của thuật toán ta phải được kết quả mong muốn d. Tính phổ dụng Thuật toán có thể giải bất kỳ bài toán nào trong cùng một lớp các bài toán 13
3. Các đặc trưng của giải thuật (tiếp) e. Tính có đại lượng vào, đại lượng ra - Khi bắt đầu giải thuật bao giờ cũng nhận các đại lượng vào mà ta thường gọi là dữ liệu vào - Sau khi kết thúc, một thuật toán bao giờ cũng cho một số đại lượng ra tuỳ theo các chức năng mà thuật toán đảm nhiệm, chúng thường được gọi là dữ liệu ra. 14
3. Các đặc trưng của giải thuật (tiếp) f. Tính có hiệu quả Tính có hiệu quả của giải thuật được đánh giá dựa trên các tiêu chuẩn sau • Dung lượng bộ nhớ cần có • Số các phép tính cần thực hiện • Thời gian cần thiết để chạy • Có dễ hiểu không • Có dễ cài đặt trên máy không 15
4. Ngôn ngữ diÔn đạt giải thuậtLiệt kê từng bước (ngôn ngữ tự nhiên) a. -Liệt kê các bước thực hiện giải thuật theo thứ tự thực hiện Ví dụ b. Sơ đồ khối • Khối bắt đầu hoặc kết thúc • Nhập dữ liệu • Khối thao tác • Khối điều kiện • Chỉ hướng thực hiện của Ví dụ giải thuật 16
4. Ngôn ngữ diÔn đạt giải thuật (tiếp) c. Dùng ngôn ngữ phỏng trình (tựa ngôn ngữ lập -Sử trình) cú pháp của một ngôn ngữ lập trình +Ngôn ngữ tự dụng nhiên để diễn đạt giải thuật Ví dụ d. Dùng ngôn ngữ lập trình -Dùng ngôn ngữ lập trình nào đó để viết giải thuật Ví dụ -Hạn chế: Phụ thuộc vào ngữ nghĩa, cú phápnặng nề, gò bó Không được nhiều người dùng ưa thích và sử dụng -Lưu ý: Trong quá trình học môn học này, chủ yếu dùng ngôn ngữ phỏng trình tựa Pascal /C để diễn đạt giải thuật 17
5. Kiểu dữ liệu • Dữ liệu : Số, ký tự, hình ảnh, âm thanh… •Thuộc tính của một kiểu dữ liệu bao gồm: - Tên kiểu dữ liệu - Mièn giá trị - Kích thức lưu trữ - Tập các phép toán tác động lên KDL đó 18
5. Kiểu dữ liệu Các kiểu dữ liệu Rời rạc: Số nguyên, ký tự, logic, liệt kê, miền con • KDL cơ bản: Liên tục: Số thực Kiểu chuỗi (String) Kiểu Mảng (Array) • KDL cấu trúc Kiểu bản ghi (Recorrd) Kiểu tập hợp (Union) 19
5. Kiểu dữ liệu Các kiểu dữ liệu Danh sách móc nối (List) • KDL trừu tượng Cây (Tree) Đồ thị (Graph) Tập hợp (union) 20