Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 1: Tổng quan

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 1: Tổng quan

1. TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP THÀNH PHỐ HỒ CHÍ MINH Cấu trúc dữ liệu và giải thuật Tổng quan TS. Ngô Hữu Dũng
2. Dẫn nhập  Data structures and algorithms  Data structures?  Array  Struct  Linked list  Stack  Queue  Tree  Graph  Algorithm?  Search Blog ngohuudung.blogspot.com  Sort Email ngohuudung@iuh.edu.vn  Recursion 2 Cấu trúc dữ liệu và giải thuật - Tổng quan
3. Nội dung  Tổng quan  Ôn tập căn bản  Độ phức tạp thuật toán  Giải thuật tìm kiếm  Giải thuật sắp xếp  Danh sách liên kết  Ngăn xếp – stack  Hàng đợi – Queue  Cấu trúc cây – Tree  Cấu trúc nâng cao 3 Cấu trúc dữ liệu và giải thuật - Tổng quan
4. Tài liệu  Trần Hạnh Nhi, Dương Anh Đức: Nhập môn cấu trúc dữ liệu và thuật toán. Khoa Công nghệ thông tin, ĐH KHTN TP HCM – 2000.  Slide bài giảng  Bài tập thực hành  Đề tài bài tập lớn  Tham khảo thêm  Robert L.Kruse, Alexander J.Ryba, Data Structures And Program Design In C++, PrenticeHall International Inc., 1999.  Nguyễn Ngô Bảo Trân, Giáo trình cấu trúc dữ liệu và giải thuật – Trường Đại học Bách Khoa TP.HCM, 2005.  Internet 4 Cấu trúc dữ liệu và giải thuật - Tổng quan
5. Lịch trình Lý Thực Tuần Nội dung Kiểm tra thuyết hành 1 Giới thiệu môn học- Tổng quan 3 2 Giải thuật tìm kiếm 3 3 Giải thuật sắp xếp 3 3 4 Bài toán tìm kiếm, sắp xếp 3 3 5-6 Danh sách liên kết 6 6 TK 7 Bài toán danh sách liên kết 3 3 GK 8-9 Ngăn xếp & Hàng đợi 6 6 10 Bài toán ngăn xếp & Hàng đợi 3 3 11 Cấu trúc cây 3 3 TK 12 Bài toán cấu trúc cây 3 3 Bài tập lớn 13-14 Bài toán tổng hợp 6 15 Ôn tập 3 CK 45 30 5 Cấu trúc dữ liệu và giải thuật - Tổng quan
6. Kiểm tra đánh giá  Lý thuyết  Kiểm tra thường kỳ  Thi cuối kỳ  Thực hành  Kiểm tra thường kỳ  Thi giữa kỳ  Bài tập lớn  Điểm liệt: <3  Số tín chỉ: 4  Lý thuyết: 45  Thực hành: 30  Tự học: 105 6 Cấu trúc dữ liệu và giải thuật - Tổng quan
7. Tìm kiếm – search  Tìm kiếm nhị phân  Binary search a Start here 1 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 low mid high  Tìm kiếm tuyến tính  Sequential search (Linear search) a Start here 1 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 7 Cấu trúc dữ liệu và giải thuật - Tổng quan
8. Binary vs Sequential search 8 Cấu trúc dữ liệu và giải thuật - Tổng quan
9. Binary search – worst case 9 Cấu trúc dữ liệu và giải thuật - Tổng quan
10. Binary search – best case 10 Cấu trúc dữ liệu và giải thuật - Tổng quan
11. Binary search tree  Viết mã giả cho thuật toán tìm kiếm nhị phân? 23 mid 7 41 3 13 31 47 1 5 11 17 29 37 43 53 low 19 59 high 11 Cấu trúc dữ liệu và giải thuật - Tổng quan
12. How’s binary search tree work? 12 Cấu trúc dữ liệu và giải thuật - Tổng quan
13. Sắp xếp – sort  Selection Sort  Insertion Sort và Shell Sort  Interchange Sort  Bubble sort và Shaker Sort  Quick Sort  Heap Sort  Merge Sort 13 Cấu trúc dữ liệu và giải thuật - Tổng quan
14. Các thuật toán sắp xếp  14 Cấu trúc dữ liệu và giải thuật - Tổng quan
15. Độ phức tạp của thuật toán? Algorithm Best case Average case Worst case Linear search O(1) O(n) O(n) Binary search O(1) O(log n) O(log n) Selection sort O(n2) O(n2) O(n2) Insertion sort O(n) O(n2) O(n2) Bubble sort O(n) O(n2) O(n2) Shell sort O(n) O((nlog(n))2) O((nlog(n))2) Merge sort O(nlogn) O(nlogn) O(nlogn) Heap sort O(nlogn) O(nlogn) O(nlogn) Quick sort O(nlogn) O(nlogn) O(n2) 15 Cấu trúc dữ liệu và giải thuật - Tổng quan
16. Độ phức tạp big Oh 16 Cấu trúc dữ liệu và giải thuật - Tổng quan
17. Danh sách liên kết – Linked list  Một dãy tuần tự các nút (Node)  Giữa hai nút có con trỏ liên kết  Các nút không cần phải lưu trữ liên tiếp nhau trong bộ nhớ  Có thể mở rộng tuỳ ý  data next data next data next tail head 42 29 76 NULL pre. data next pre. data next pre. data next tail head 42 42 42 NULL NULL 17 Cấu trúc dữ liệu và giải thuật - Tổng quan
18. Các thao tác cơ bản trên danh sách liên kết  Thêm một nút  Vào đầu danh sách  Vào cuối danh sách  Vào sau một vị trí được chỉ ra (chèn)  Duyệt danh sách  Xuất, trích xuất  Tìm kiếm  Max, min, giá trị x  Xóa một nút  Ở đầu, cuối hoặc vị trí xác định trên danh sách  Sắp xếp danh sách 18 Cấu trúc dữ liệu và giải thuật - Tổng quan
19. Ngăn xếp và hàng đợi – Stack & Queue Push 34 56 45 37 19 28 Pop Stack – Last in, first out Top Dequeue 34 56 45 37 19 28 Enqueue Queue – First in, first out Front Rear 19 Cấu trúc dữ liệu và giải thuật - Tổng quan
20. Ví dụ về Stack và Queue 20 Cấu trúc dữ liệu và giải thuật - Tổng quan
21. Cấu trúc cây 21 Cấu trúc dữ liệu và giải thuật - Tổng quan
22. Củng cố kiến thức qua bài tập ví dụ  Đề bài: Để quản lý sinh viên gồm các thông tin: ID, Tên, Điểm thường kỳ, Điểm giữa kỳ, Điểm cuối kỳ, và Điểm tổng kết (20%ĐTK + 30%ĐGK + 50%ĐCK) bạn hãy xây dựng các tác vụ theo mô tả sau: 1. Nhập thông tin một sinh viên 2. Xuất thông tin một sinh viên 3. Thêm một sinh viên vào danh sách 4. Xuất tất cả danh sách sinh viên 5. Tìm kiếm sinh viên theo mã 6. Xóa một sinh viên tại vị trí chỉ ra 7. Cập nhật (sửa) thông tin một sinh viên 8. Hiển thị sinh viên có số điểm cao nhất 9. Sắp xếp sinh viên theo điểm tổng kết 10. Menu thực hiện các tác vụ trên 22 Cấu trúc dữ liệu và giải thuật - Tổng quan