Bài giảng Cấu trúc dữ liệu và giải thuật - Nguyễn Hữu Dũng
Danh sách liên kết – Linked list
Cấu trúc dữ liệu và giải thuật - Tổng quan
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ỳ ý
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)
Xóa một nút
Ở đầu, cuối hoặc vị trí xác định trên danh sách
Duyệt danh sách
Xuất, trích xuất, đếm, tính toán
Tìm kiếm
Max, min, giá trị x
Sắp xếp danh sách
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Cấu trúc dữ liệu và giải thuật - Nguyễn Hữu Dũng", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
Tóm tắt nội dung tài liệu: Bài giảng Cấu trúc dữ liệu và giải thuật - Nguyễn Hữu Dũng
![Bài giảng Cấu trúc dữ liệu và giải thuật - Nguyễn Hữu Dũng Bài giảng Cấu trúc dữ liệu và giải thuật - Nguyễn Hữu Dũng](https://s1.tailieubachkhoa.net/rl6k7x3q9zfh00j8/thumb/2021/12/03/bai-giang-cau-truc-du-lieu-va-giai-thuat-nguyen-huu-dung_TyPzSLAiAw.jpg)
Cấu trúc dữ liệu và giải thuật Tổng quan TS. Ngô Hữu Dũng TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP THÀNH PHỐ HỒ CHÍ MINH Dẫn nhập Cấu trúc dữ liệu và giải thuật - Tổng quan Data structures and algorithms Data structures? Array Struct Linked list Stack Queue Tree Graph Algorithm? Search Sort Recursion Blog ngohuudung.blogspot.com Email ngohuudung@iuh.edu.vn 2 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 Cấu trúc dữ liệu và giải thuật - Tổng quan3 Tài liệu Cấu trúc dữ liệu và giải thuật - Tổng quan 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 Lịch trình Cấu trúc dữ liệu và giải thuật - Tổng quan Tuần Nội dung Lý thuyết Thực hành Kiểm tra 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 Kiểm tra đánh giá Cấu trúc dữ liệu và giải thuật - Tổng quan 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 Tìm kiếm – search Cấu trúc dữ liệu và giải thuật - Tổng quan7 Tìm kiếm nhị phân Binary search Tìm kiếm tuyến tính Sequential search (Linear search) 1 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 a 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 low mid high Start here 1 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 a 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Start here Binary vs Sequential search Cấu trúc dữ liệu và giải thuật - Tổng quan8 Binary search – worst case Cấu trúc dữ liệu và giải thuật - Tổng quan9 Binary search – best case Cấu trúc dữ liệu và giải thuật - Tổng quan10 Binary search tree Cấu trúc dữ liệu và giải thuật - Tổng quan11 Viết mã giả cho thuật toán tìm kiếm nhị phân? 1 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 mid low high How’s binary search tree work? Cấu trúc dữ liệu và giải thuật - Tổng quan12 Sắp xếp – sort Cấu trúc dữ liệu và giải thuật - Tổng quan13 Selection Sort Insertion Sort và Shell Sort Interchange Sort Bubble sort và Shaker Sort Quick Sort Heap Sort Merge Sort Các thuật toán sắp xếp Cấu trúc dữ liệu và giải thuật - Tổng quan14 https://www.toptal.com/developers/sorting-algorithms/ Độ phức tạp của thuật toán? Cấu trúc dữ liệu và giải thuật - Tổng quan15 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) Độ phức tạp big Oh Cấu trúc dữ liệu và giải thuật - Tổng quan16 Danh sách liên kết – Linked list Cấu trúc dữ liệu và giải thuật - Tổng quan17 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ỳ ý 42 data next head pre. 42 data nextpre. 42 data nextpre. NULLNULL tail 42 data next 29 data next 76 data next NULL head tail Các thao tác cơ bản trên danh sách liên kết Cấu trúc dữ liệu và giải thuật - Tổng quan18 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) Xóa một nút Ở đầu, cuối hoặc vị trí xác định trên danh sách Duyệt danh sách Xuất, trích xuất, đếm, tính toán Tìm kiếm Max, min, giá trị x Sắp xếp danh sách Ngăn xếp và hàng đợi – Stack & Queue Cấu trúc dữ liệu và giải thuật - Tổng quan19 34 56 45 37 19 28 34 56 45 37 19 28 EnqueueDequeue Queue – First in, first out Stack – Last in, first out Push Pop Front Rear Top Ví dụ về Stack và Queue Cấu trúc dữ liệu và giải thuật - Tổng quan20 Cấu trúc cây Cấu trúc dữ liệu và giải thuật - Tổng quan21 Củng cố kiến thức qua bài tập ví dụ Cấu trúc dữ liệu và giải thuật - Tổng quan22 Đề 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 Cấu trúc dữ liệu và giải thuật Giải thuật tìm kiếm TS. Ngô Hữu Dũng TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP THÀNH PHỐ HỒ CHÍ MINH Tìm kiếm – Searching Cấu trúc dữ liệu và giải thuật - Tìm kiếm24 Tìm kiếm tuần tự - Sequential search Còn gọi là tuyến tính – Linear search Danh sách chưa sắp xếp hoặc đã sắp xếp Thời gian tỉ lệ với n (số phần tử) Độ phức tạp O(n) Tìm kiếm nhị phân – Binary search Danh sách đã sắp xếp Thời gian tỉ lệ với log2 n Độ phức tạp O(log n) Sequential search Cấu trúc dữ liệu và giải thuật - Tìm kiếm25 Duyệt danh sách từ đầu đến cuối Dừng khi tìm thấy hoặc kết thúc danh sách Nếu tìm thấy: Trả về kết quả tìm thấy True hoặc vị trí được tìm thấy hoặc thông báo Nếu không tìm thấy: Trả về kết quả không tìm thấy False hoặc một giá trị như -1 hoặc thông báo Sequential search – Vòng lặp Cấu trúc dữ liệu và giải thuật - Tìm kiếm26 Trả về vị trí khi tìm thấy Trả về -1 khi không tìm thấy Lưu ý: Các code chỉ mang tính minh hoạ cho giải thuật Có nhiều cách diễn đạt và cải tiến thuật toán 1. int linearSearch(int a[], int n, int x) 2. { 3. int i; 4. for(i=0; i<n; i++) 5. if(a[i] == x) 6. return i; 7. return -1; 8. } Sequential search – Vòng lặp Cấu trúc dữ liệu và giải thuật - Tìm kiếm27 Trả về kiểu bool True: Tìm thấy False: Không tìm thấy 1. bool linearSearch(int a[], int n, int x) 2. { 3. int i; 4. for(i=0; i<n; i++) 5. if(a[i] == x) 6. return true; 7. return false; 8. } Sequential search – Thông báo Cấu trúc dữ liệu và giải thuật - Tìm kiếm28 Xuất ra màn hình kết quả 1. void linearSearch(int a[], int n, int x) 2. { 3. int i; 4. for(i=0; i<n; i++) 5. if(a[i] == x) 6. { 7. printf("Tim thay o vi tri %d", i); 8. break; 9. } 10. if(i==n) 11. printf("Khong tim thay"); 12.} Sequential search – Cờ hiệu Cấu trúc dữ liệu và giải thuật - Tìm kiếm29 Dùng cờ hiệu: Chương trình rõ ràng, dễ hiểu 1. void linearSearch(int a[], int n, int x) 2. { 3. int i, flag = 0; // Chưa tìm thấy 4. for(i=0; i<n; i++) 5. if(a[i] == x){ 6. printf("Tim thay o vi tri %d", i); 7. flag = 1; // Đã tìm thấy 8. break; 9. } 10. if(!flag) 11. printf("Khong tim thay"); 12.} Sequential search – Đệ quy Cấu trúc dữ liệu và giải thuật - Tìm kiếm30 Dùng đệ quy Thực hiện gọi hàm nhiều lần 1. int linearSearch(int a[], int n, int x) 2. { 3. if(n<0) 4. return -1; 5. else if(a[n-1] == x) 6. return n-1; 7. else 8. return linearSearch(a, n-1, x); 9. } Sequential search – Cầm canh Cấu trúc dữ liệu và giải thuật - Tìm kiếm31 Dùng phần tử cầm canh Giảm bớt số lần so sánh 1. int linearSearch(int a[], int n, int x) 2. { 3. int i = 0; 4. a[n]=x; // Phần tử cầm canh 5. while(a[i]!=x) 6. i++; 7. if(i<n) 8. return i; 9. return -1; 10.} Sequential search – Rút gọn Cấu trúc dữ liệu và giải thuật - Tìm kiếm32 Giảm thiểu số phép toán 1. int linearSearch(int a[], int n, int x) 2. { 3. do{ 4. n--; 5. }while(a[n]!=x && n>=0); 6. return n; 7. } Sequential search – Hai chiều Cấu trúc dữ liệu và giải thuật - Tìm kiếm33 Tìm cả hai chiều 1. int doubleSearch(int a[], int n, int x) 2. { 3. int i=-1; 4. do{ 5. if(a[--n]==x) return n; 6. if(a[++i]==x) return i; 7. }while(i<n); 8. return -1; 9. } So sánh thực nghiệm Cấu trúc dữ liệu và giải thuật - Tìm kiếm34 Thực hiện 1 triệu phép lặp cho mỗi hàm Cơ bản Đệ quy Cầm canh Rút gọn Hai chiều Phần tử cần tìm nằm ở vị trí trong trường hợp xấu nhất (worst case) Đo thời gian thực hiện của mỗi hàm để so sánh kết quả 1. for(int i=0;i<1000; i++) 2. for(int j=0;j<1000; j++) 3. k = linearSearch(a, n, x); Cách đo thời gian Cấu trúc dữ liệu và giải thuật - Tìm kiếm35 Một số IDE có sẵn chức năng đo thời gian 1. #include 2. #include 3. int main() 4. { 5. clock_t t = clock(); 6. // Đoạn code cần đo thời gian 7. t = clock()-t; 8. printf("Time: %.2fs\n",(float)t/CLOCKS_PER_SEC); 9. return 0; 10.} Đánh giá Cấu trúc dữ liệu và giải thuật - Tìm kiếm36 Bài tập vận dụng Cấu trúc dữ liệu và giải thuật - Tìm kiếm37 Viết hàm tìm kiếm phần tử x trong khoảng từ left đến right trong mảng. Nguyên mẫu hàm? Sử dụng hàm? Binary search Cấu trúc dữ liệu và giải thuật - Tìm kiếm38 Danh sách đã được sắp xếp, giả sử tăng dần So sánh X với phần tử ở giữa danh sách Nếu bằng nhau: Tìm kiếm thành công Nếu X nhỏ hơn: Tiếp tục tìm bên trái danh sách Nếu X lớn hơn: Tiếp tục tìm bên phải danh sách Binary search – Iteration Cấu trúc dữ liệu và giải thuật - Tìm kiếm39 1. int binarySearch(int a[],int left,int right,int x) 2. { 3. while(left<=right) 4. { 5. int mid = (left + right)/2; 6. if(x==a[mid]) 7. return mid; 8. if(x<a[mid]) 9. right = mid-1; 10. else 11. left = mid+1; 12. } 13. return -1; 14.} Binary search – Recursion Cấu trúc dữ liệu và giải thuật - Tìm kiếm40 1. int binarySearch(int a[],int left,int right,int x) 2. { 3. if (left <= right) 4. { 5. int mid = left + (right - left)/2; //? 6. if (x == a[mid]) 7. return mid; 8. if (x < a[mid]) 9. return binarySearch(a, left, mid-1, x); 10. else 11. return binarySearch(a, mid+1, right, x); 12. } 13. return -1; 14.} Exponential Search Cấu trúc dữ liệu và giải thuật - Tìm kiếm41 Bao gồm hai bước Xác định vùng chứa X trong mảng Lần lượt so sánh X với các phần tử i bắt đầu từ 1, 2, 4, 8, 16 tăng dần theo lũy thừa 2. Khi tìm được vị trí của phần tử i có giá trị lớn hơn X, vùng cần tìm là từ i/2 đến min(i,n) Dùng binary search để tìm trong vùng đã xác định 1 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 0 20 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 21 22 23 1 Exponential Search Cấu trúc dữ liệu và giải thuật - Tìm kiếm42 1. int exponentialSearch(int a[], int n, int x) 2. { 3. if (a[0] == x) 4. return 0; 5. 6. int i=1; 7. while (i < n && a[i] <= x) 8. i = i*2; 9. return binarySearch(a, i/2, (i<n)?i:n, x); 10.} Interpolation Search Cấu trúc dữ liệu và giải thuật - Tìm kiếm43 Điểm mid không nhất thiết chính giữa Cách tính điểm ở giữa mid = low+(x-a[low])*(high-low)/(a[high]-a[low]); mid sẽ gần điểm low khi x gần a[low] hơn mid sẽ gần điếm high khi x gần a[high] hơn Interpolation Search Cấu trúc dữ liệu và giải thuật - Tìm kiếm44 1. int interpolationSearch(int a[], int size, int x) 2. { 3. int low = 0, high = size – 1, mid; 4. while(high>=low && x>=a[low] && x<=a[high]) 5. { 6. mid = low+(x-a[low])*(high-low)/(a[high]-a[low]); 7. if (a[mid] < x) 8. low = mid + 1; 9. else if (x < a[mid]) 10. high = mid - 1; 11. else 12. return mid; 13. } 14. return -1; 15.} Một kết quả so sánh Cấu trúc dữ liệu và giải thuật - Tìm kiếm45 Độ phức tạp? Cấu trúc dữ liệu và giải thuật - Tìm kiếm46 Một trường hợp so sánh không đánh giá đầy đủ về các thuật toán Cần nhiều trường hợp hơ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) Exponential Search O(1) O(log i) O(log i) Với i là vị trí cần tìm Interpolation Search O(1) O(log(log n)) O(n) Bài tập vận dụng Cấu trúc dữ liệu và giải thuật - Tìm kiếm47 Viết chương trình Phát sinh ngẫu nhiên một mảng tăng dần Cài đặt các hàm tìm kiếm Tìm giá trị x nhập từ bàn phím Xuất ra số lần so sánh của mỗi phương pháp Đánh giá các phương pháp Tìm hiểu hoặc đề xuất phương pháp mới Cấu trúc dữ liệu và giải thuật Giải thuật sắp xếp TS. Ngô Hữu Dũng TRƯỜNG ĐẠI HỌC CÔNG NGHIỆP THÀNH PHỐ HỒ CHÍ MINH Sắp xếp – sort Cấu trúc dữ liệu và giải thuật - Sắp xếp49 Selection Sort Insertion Sort Bubble sort Shell Sort Merge Sort Heap Sort Quick Sort Lưu ý: Các code ở đây chỉ mang tính chất minh hoạ cho giải thuật Có nhiều cách diễn đạt và cải tiến thuật toán Các thuật toán sắp xếp Cấu trúc dữ liệu và giải thuật - Sắp xếp50 https://www.toptal.com/developers/sorting-algorithms/ Interchange sort Cấu trúc dữ liệu và giải thuật - Sắp xếp51 1. void interchangeSort(int a[], int n) 2. { 3. for(int i=0; i<n-1; i++) 4. for(int j=i+1; j<n; j++) 5. if(a[i]>a[j]) 6. swap(&a[i], &a[j]); 7. } 51 90 26 23 63 26 90 51 23 63 Thừa vô ích 23 90 51 26 63 23 51 90 26 63 23 26 90 51 63 23 26 51 90 63 Luôn lặp n2 lần 23 26 51 63 90 Có nhiều hoán vị thừa Insertion sort Cấu trúc dữ liệu và giải thuật - Sắp xếp52 for i = 2:n, for (k = i; k > 1 and a[k] < a[k-1]; k--) swap a[k,k-1] → invariant: a[1..i] is sorted end 51 90 26 23 63 26 51 90 23 63 Dịch chuyển nhiều phần tử 23 26 51 90 63 Dịch chuyển nhiều lần 23 26 51 63 90 Luôn lặp n2 lần Insertion sort – Minh hoạ Cấu trúc dữ liệu và giải thuật - Sắp xếp53 1. void insertionSort(int a[], int n) 2. { 3. int i, key, j; 4. for (int i = 1; i < n; i++) 5. { 6. int temp = a[i]; 7. int j = i-1; 8. 9. while (j >= 0 && a[j] > temp) 10. { 11. a[j+1] = a[j]; 12. j = j-1; 13. } 14. a[j+1] = temp; 15. } 16.} Selection sort Cấu trúc dữ liệu và giải thuật - Sắp xếp54 for i = 1:n, k = i for j = i+1:n, if a[j] < a[k], k = j → invariant: a[k] smallest of a[i..n] swap a[i,k] → invariant: a[1..i] in final position end Selection sort Cấu trúc dữ liệu và giải thuật - Sắp xếp55 51 90 26 23 63 23 90 26 51 63 23 26 90 51 63 23 26 51 90 63 23 26 51 63 90 Loại những hoán vị thừa ở thuật toán cơ bản Selection sort – Minh hoạ Cấu trúc dữ liệu và giải thuật - Sắp xếp56 1. void selectionSort(int a[], int n) 2. { 3. for(int i=0; i<n; i++) 4. { 5. int k = i; 6. for(int j=i+1; j<n; j++) 7. if (a[j]<a[k]) 8. k=j; 9. if(i!=k) 10. swap(&a[i], &a[k]); 11. } 12.} Bubble Sort Cấu trúc dữ liệu và giải thuật - Sắp xếp57 for i = 1:n, swapped = false for j = n:i+1, if a[j] < a[j-1], swap a[j,j-1] swapped = true → invariant: a[1..i] i ... pNext; } STACK_NODE; typedef struct STACK { int StkCount; STACK_NODE *StkTop; }; 193 Stack – Sử dụng DSLK VD: Thực hiện một số thao tác trên stack STACK s; InitStack(s); Push(s, 7); Push(s, 4); Pop(s, x); // x = ? N StkCnt StkTop 7 Data Link 4 194 Stack số nguyên – Sử dụng DSLK void InitStack(STACK &s) { s.StkTop = NULL; s.StkCount = 0; } 195 Stack số nguyên – Sử dụng DSLK bool IsEmpty(const STACK &s) { if (s.StkTop == NULL) return true; return false; } 196 Stack số nguyên – Sử dụng DSLK bool IsFull (const STACK s) { STACK_NODE* temp = new STACK_NODE; if (temp == NULL) return true; delete temp; return false; } 197 Stack số nguyên – Sử dụng DSLK bool Push(STACK &s, int newitem) { if (IsFull(s)) return false; STACK_NODE *pNew = new STACK_NODE; pNew->Data = newitem; pNew->pNext = s.StkTop; s.StkTop = pNew; s.StkCount++; return true; } N StkCnt StkTop 7 Data Link 4 198 Stack số nguyên – Sử dụng DSLK bool Pop(STACK &s, int &outitem) { if (IsEmpty(s)) return false; STACK_NODE *temp = s.StkTop; outitem = s.StkTop->Data; s.StkTop = s.StkTop->pNext; delete temp; s.StkCount--; return true; } N StkCnt StkTop 7 Data Link 4 Data Link temp outitem = 4 199 Stack – Ứng dụng Stack có nhiều ứng dụng: Lưu vết trong thuật toán “back-tracking” (theo dõi dấu vết) Tính giá trị biểu thức toán học (thuật toán Balan ngược) Khử đệ quy 200 Stack – Quick Sort Để khử đệ quy cho Quick Sort, ta sử dụng một stack để lưu lại các partition (phân hoạch) cần tiến hành sắp xếp. Ý tưởng: Push phân hoạch đầu tiên (0, n-1) vào stack Trong khi stack chưa rỗng Pop một phân hoạch từ stack Chọn phần tử trục trên phân hoạch này Điều chỉnh phân hoạch tương ứng với trục Push 2 phân hoạch bên trái và phải trục vào stack 201 Stack – Quick Sort Push phân hoạch đầu tiên (0, n-1) vào stack Trong khi stack chưa rỗng Pop một phân hoạch từ stack Chọn phần tử trục trên phân hoạch này Điều chỉnh phân hoạch tương ứng với trục Push 2 phân hoạch bên trái và phải trục vào stack (0,4) 1 5 4 7 3 0 1 2 3 4 i j t 3 5 1 (3,4) 5 7 Stack rỗng Stop 202 Queue Hàng đợi Cấu trúc dữ liệu và giải thuật - Stack&Queue203 34 56 45 37 enQueuedeQueue Front Rear Queue – First in, first out Queue Phòng vé 204 Queue – Định nghĩa Hàng đợi là một cấu trúc: Gồm nhiều phần tử có thứ tự Hoạt động theo cơ chế “Vào trước, ra trước” (FIFO - First In First Out) 205 Queue – Định nghĩa Các thao tác cơ bản trên hàng đợi: InitQueue: khởi tạo hàng đợi rỗng IsEmpty: kiểm tra hàng đợi rỗng? IsFull: kiểm tra hàng đợi đầy? EnQueue: thêm 1 phần tử vào cuối hàng đợi, có thể làm hàng đợi đầy DeQueue: lấy ra 1 phần tử từ đầu Queue, có thể làm Queue rỗng 206 Queue Minh họa thao tác EnQueue Minh họa thao tác DeQueue 207 Cách xây dựng Queue Sử dụng mảng một chiều Sử dụng danh sách liên kết đơn 208 Queue – Sử dụng mảng Dùng 1 mảng (QArray) để chứa các phần tử. Dùng 1 số nguyên (QMax)để lưu số phần tử tối đa trong hàng đợi Dùng 2 số nguyên (QFront, QRear) để xác định vị trí đầu, cuối hàng đợi Dùng 1 số nguyên (QNumItems) để lưu số phần tử hiện có trong hàng đợi 209 Queue – Sử dụng mảng 0 1 2 3 4 5 6 Qarray 37 22 15 3 QMax = 7 QNumItems = 4 QFront = 1 QRear = 4 210 Queue số nguyên – Sử dụng mảng typedef struct QUEUE { int* QArray; int QMax; int QNumItems; int QFront; int QRear; }; 211 Queue số nguyên – Sử dụng mảng Khi thêm nhiều phần tử sẽ xảy ra hiện tượng “tràn giả” Giải pháp? Nối dài mảng (mảng động) hay sử dụng một mảng vô cùng lớn? 0 1 2 3 4 5 6 Qarray 37 22 15 3 7 9 QMax = 7 QNumItems = 6 QFront = 1 QRear = 6 212 Queue số nguyên – Sử dụng mảng Xử lý mảng như một danh sách liên kết vòng 0 1 2 3 4 5 6 Qarray 37 22 15 3 7 9 QMax = 7 QNumItems = 6 QFront = 1 QRear = 6 213 Chỉ số mảng 0 1 2 3 4 5 6 QArray 11 7 19 21 81 QMax 7 QNumItems 5 QFront 1 QRear 5 VD: Cho queue như sau Queue số nguyên – Sử dụng mảng 1. Thêm giá trị 123 vào hàng đợi Queue số nguyên – Sử dụng mảng Chỉ số mảng 0 1 2 3 4 5 6 QArray 11 7 19 21 81 123 QMax 7 QNumItems 6 QFront 1 QRear 6 2. Lấy một phần tử khỏi hàng đợi Queue số nguyên – Sử dụng mảng Chỉ số mảng 0 1 2 3 4 5 6 QArray 11 7 19 21 81 123 QMax 7 QNumItems 5 QFront 2 QRear 6 3. Thêm giá trị 456 vào hàng đợi Queue số nguyên – Sử dụng mảng Chỉ số mảng 0 1 2 3 4 5 6 QArray 456 11 7 19 21 81 123 QMax 7 QNumItems 6 QFront 2 QRear 0 Queue số nguyên – Sử dụng mảng bool InitQueue(QUEUE &q, int MaxItem) { q.QArray = new int[MaxItem]; if (q.QArray == NULL) return false; q.QMax = MaxItem; q.QNumItems = 0; q.QFront = q.QRear = -1; return true; } 218 Queue số nguyên – Sử dụng mảng bool IsEmpty(QUEUE q) { if (q.QNumItems == 0) return true; return false; } 219 Queue số nguyên – Sử dụng mảng bool IsFull(QUEUE q) { if (q.QMax == q.QNumItems) return true; return false; } 220 Queue số nguyên – Sử dụng mảng bool EnQueue(QUEUE &q, int newitem) { if (IsFull(q)) return false; q.QRear++; if (q.QRear==q.QMax) q.QRear = 0; q.QArray[q.QRear] = newitem; if (q.QNumItems==0) q.QFront = 0; q.QNumItems++; return true; } 221 Queue số nguyên – Sử dụng mảng bool DeQueue(QUEUE &q, int &itemout) { if (IsEmpty(q)) return false; itemout = q.QArray[q.QFront]; q.QFront++; q.QNumItems--; if (q.QFront==q.QMax) q.QFront = 0; if (q.QNumItems==0) q.QFront = q.QRear = -1; return true; } 222 Queue số nguyên – Sử dụng mảng bool QueueFront(const QUEUE &q, int &itemout) { if (IsEmpty(q)) return false; itemout = q.QArray[q.QFront]; return true; } 223 Queue số nguyên – Sử dụng mảng bool QueueRear(const QUEUE &q, int &itemout) { if (IsEmpty(q)) return false; itemout = q.QArray[q.QRear]; return true; } 224 Queue – Ví dụ ứng dụng Quản lý việc thực hiện các tác vụ (task) trong môi trường xử lý song song Hàng đợi in ấn các tài liệu Vùng nhớ đệm (buffer) dùng cho bàn phím Quản lý thang máy 225 Queue – Sử dụng DSLK typedef struct tagNODE { int data; tagNODE* pNext; } NODE, *PNODE; typedef struct tagQUEUE { int NumItems; PNODE pFront, pRear; } QUEUE; 226 Queue – Sử dụng DSLK Các thao tác cơ bản bool InitQueue(QUEUE &q); bool IsEmpty(const QUEUE &q); bool IsFull(const QUEUE &q); bool EnQueue(QUEUE &q, int newitem); bool DeQueue(QUEUE &q, int& itemout); 227 Queue – Sử dụng DSLK bool InitQueue(QUEUE &q) { q.NumItems = 0; q.pFront = q.pRear = NULL; return true; } 228 Queue – Sử dụng DSLK bool IsEmpty(const QUEUE& q) { return (q.NumItems==0); } 229 Queue – Sử dụng DSLK bool IsFull(const QUEUE &q) { PNODE tmp = new NODE; if (tmp==NULL) return true; delete tmp; return false; } 230 Queue – Sử dụng DSLK bool EnQueue(QUEUE &q, int newitem) { if (IsFull(q)) return false; PNODE p = new NODE; p->data = newitem; p->pNext = NULL; if (q.pFront==NULL && q.pRear==NULL) q.pFront = q.pRear = p; else { q.pRear->pNext = p; q.pRear = p; } q.NumItems++; return true; } 231 Queue – Sử dụng DSLK bool DeQueue(QUEUE &q, int &itemout) { if (IsEmpty(q)) return false; PNODE p = q.pFront; q.pFront = p->pNext; itemout = p->data; q.NumItems--; delete p; if (q.NumItems==0) InitQueue(q); return true; } 232 Data structures and algorithms Tree structure INDUSTRIAL UNIVERSITY OF HO CHI MINH CITY Nội dung 1. Khái niệm 2. Đặc điểm 3. Hình dạng 4. Định nghĩa kiểu dữ liệu 5. Các lưu ý khi cài đặt 6. Các thao tác 234 Khái niệm Bậc của một nút: là số cây con của nút đó Nút gốc: là nút không có nút cha Nút lá: là nút có bậc bằng 0 Nút nhánh: là nút có bậc khác 0 và không phải là gốc 235 2 22 110 0 0 0 Mức 3 Mức 2 Mức 1 Mức 0 Khái niệm Độ dài đường đi từ gốc đến nút x: là số nhánh cần đi qua kể từ gốc đến x Độ cao của cây: Độ dài đường đi từ gốc đến nút lá ở mức thấp nhất 236 Đặc điểm cây nhị phân tìm kiếm Là cây nhị phân Giá trị của một node bất kỳ luôn lớn hơn giá trị của tất cả các node bên trái và nhỏ hơn giá trị tất cả các node bên phải Nút có giá trị nhỏ nhất nằm ở trái nhất của cây Nút có giá trị lớn nhất nằm ở phải nhất của cây 237 7 3 36 1 6 15 40 234 Định nghĩa kiểu dữ liệu 238 typedef struct TNODE { Key; struct TNODE *pLeft, *pRight; } *TREE; Nút Giá trị Trỏ trái Trỏ phải TNODE Key pLeft pRight Ví dụ khai báo typedef struct TNODE { int Key; struct TNODE *pLeft, *pRight; } *TREE; 239 Các lưu ý khi cài đặt Bước 1: Khai báo kiểu dữ liệu biểu diễn cây Bước 2: Xây dựng hàm đưa dữ liệu (nhập) vào cây Bước 3: Xây dựng các thao tác duyệt, tìm kiếm, huỷ, 240 Cấu trúc chương trình 241 Khai báo cấu trúc cây Khởi tạo cây rỗng Xây dựng cây Các thao tác Hủy cây Các thao tác 1. Tạo cây 2. Duyệt cây 3. Cho biết các thông tin của cây 4. Tìm kiếm 5. Xoá node trên cây 242 Tạo cây 243 401546136 7 36 3 1 6 4 15 40 7 Nếu node cần thêm nhỏ hơn node đang xét thì thêm về bên trái Ngược lại thì thêm về bên phải Hàm tạo cây 244 int ThemNut (TREE & t, int x) { if(t!=NULL) { if(x==t->Key) return 0; // x đã có trong cây else { if(xKey) return ThemNut(t->pLeft, x); else return ThemNut(t->pRight, x); } } else { t=new TNODE; if(t==NULL) return -1; //không đủ bộ nhớ t->Key=x; t->pLeft=t->pRight=NULL; return 1; //thêm x thành công } } Duyệt cây Thứ tự trước (NLR) Thứ tự giữa (LNR) Thứ tự sau (LRN) 245 246 Bước Kết quả duyệt theo thứ tự NLR 1 7 L7 R7 2 3 L3 R3 R7 3 1 R3 R7 4 6 L6 R7 5 4 R7 6 36 L36 R36 7 15 R15 R36 8 23 R36 9 40 KQ 7 3 1 6 4 36 15 23 40 7 3 36 1 6 15 40 234 Hàm duyệt NLR Tại node t đang xét, nếu khác rỗng thì In giá trị của t Duyệt cây con bên trái của t theo thứ tự NLR Duyệt cây con bên phải của t theo thứ tự NLR 247 void NLR (TREE t) { if(t!=NULL) { coutKey<<“\t”; NLR(t->pLeft); NLR(t->pRight); } } Bài tập Vẽ cây nhị phân tìm kiếm theo thứ tự nhập từ trái sang phải và duyệt cây theo thứ tự trước: a. 27; 19; 10; 21; 35; 25; 41; 12; 46; 7 b. H; B; C; A; E; D; Z; M; P; T c. Huế; Đà Nẵng; Hà Nội; Vĩnh Long; Cần Thơ; Sóc Trăng; Nha Trang; Đồng Nai; Vũng Tàu; An Giang; Tiền Giang; Bình Dương; Hải Dương 248 249 Bước Kết quả duyệt theo thứ tự LNR 1 L7 7 R7 2 L3 3 R3 7 R7 3 1 3 R3 7 R7 4 3 R3 7 R7 5 L6 6 7 R7 6 4 6 7 R7 7 6 7 R7 8 7 R7 9 L36 36 R36 10 15 R15 36 R36 11 23 36 R36 12 36 R36 13 40 KQ 1 3 4 6 7 15 23 36 40 7 3 36 1 6 15 40 234 Hàm duyệt LNR Tại node t đang xét, nếu khác rỗng thì Duyệt cây con bên trái của t theo thứ tự LNR In giá trị của t Duyệt cây con bên phải của t theo thứ tự LNR 250 void LNR (TREE t) { if(t!=NULL) { LNR(t->pLeft); coutKey<<“ “; LNR(t->pRight); } } 251 Bước Kết quả duyệt theo thứ tự LRN 1 L7 R7 7 2 L3 R3 3 R7 7 3 1 R3 3 R7 7 4 L6 6 3 R7 7 5 4 6 3 R7 7 6 6 3 R7 7 7 3 R7 7 8 L36 R36 36 7 9 R15 15 R36 36 7 10 23 15 R36 36 7 11 15 R36 36 7 12 40 36 7 13 36 7 14 7 KQ 1 4 6 3 23 15 40 36 7 7 3 36 1 6 15 40 234 Hàm duyệt LRN Tại node t đang xét, nếu khác rỗng thì Duyệt cây con bên trái của t theo thứ tự LRN Duyệt cây con bên phải của t theo thứ tự LRN In giá trị của t 252 void LRN (TREE t) { if(t!=NULL) { LRN(t->pLeft); LRN(t->pRight); coutKey<<“ “; } } Bài tập Bài 4 Vẽ cây nhị phân tìm kiếm theo thứ tự nhập: 27, 19, 10, 21, 3, 15, 41, 50, 30, 27 Hãy duyệt cây trên theo thứ tự giữa Bài 5 Vẽ cây nhị phân tìm kiếm theo thứ tự nhập: H, B, C, A, E, D, T, M, X, O Hãy duyệt cây trên theo thứ tự sau 253 Vấn đề cần quan tâm Tạo cây từ kết quả duyệt NLR Chọn giá trị đầu tiên làm node gốc Lần lượt đưa các giá trị còn lại từ trái sang phải vào cây theo nguyên tắc tạo cây Tạo cây từ kết quả duyệt LRN Chọn giá trị cuối cùng làm node gốc Lần lượt đưa các giá trị còn lại từ phải sang trái vào cây theo nguyên tắc tạo cây 254 Vấn đề cần quan tâm Tạo cây từ kết quả duyệt LNR Gọi r: Số lượng giá trị cho trước Gọi m = r div 2: Giá trị ở giữa Chọn giá trị thứ m làm node gốc Lần lượt đưa các giá trị bắt đầu từ vị trí m-1 lùi về trái vào cây theo nguyên tắc tạo cây Lần lượt đưa các giá trị bắt đầu từ vị trí m+1 đến cuối vào cây theo nguyên tắc tạo cây 255 Bài tập Bài 6 Vẽ cây nhị phân tìm kiếm T biết rằng khi duyệt cây T theo thứ tự NLR thì được dãy sau: 9, 4, 1, 3, 8, 6, 5, 7, 10, 14, 12, 13, 16, 19 Hãy duyệt cây T trên theo thứ tự LRN Liệt kê các nút lá của cây. Liệt kê các nút nhánh của cây 256 Bài 7 Vẽ cây nhị phân tìm kiếm T biết rằng khi duyệt cây T theo thứ tự LRN thì được dãy sau: 1, 4, 7, 5, 3, 16, 18, 15, 29, 25, 30, 20, 8 Hãy duyệt cây T trên theo thứ tự NLR Cây T có chiều cao là bao nhiêu? Tìm các đường đi từ gốc có độ dài là 4 trên cây 257 Bài tập Hàm nhập dữ liệu vào cây void Nhap(TREE &t) { int x; do{ cout<<“Nhap gia tri: “; cin>>x; int kq=ThemNut(t, x); if(kq==0||kq==-1) break; }while (true); } 258 Hàm main gọi thao tác duyệt LNR void main() { TREE t; t=NULL; Nhap(t); cout<<“Duyet cay theo thu tu giua: “; LNR(t); Huy(t); } 259 Các thao tác 1. Tạo cây 2. Duyệt cây 3. Cho biết các thông tin của cây 4. Tìm kiếm 5. Xoá node trên cây 260 Các thao tác 1. Tạo cây 2. Duyệt cây 3. Cho biết các thông tin của cây 4. Tìm kiếm 5. Xoá node trên cây 261 Cho biết các thông tin của cây 1. Số node lá (node bậc 0) 2. Số node có 1 cây con (node bậc 1) 3. Số node chỉ có 1 cây con phải 4. Số node chỉ có 1 cây con trái 5. Số node có 2 cây con (node bậc 2) 6. Độ cao của cây 7. Số node của cây 8. Các node trên từng mức của cây 9. Độ dài đường đi từ gốc đến node x 262 Các thao tác 1. Tạo cây 2. Duyệt cây 3. Cho biết các thông tin của cây 4. Tìm kiếm 5. Xoá node trên cây 263 Các thao tác 1. Tạo cây 2. Duyệt cây 3. Cho biết các thông tin của cây 4. Tìm kiếm 5. Xoá node trên cây 264 Tìm kiếm 1. Tìm x 2. Tìm min 3. Tìm min của cây con bên phải 4. Tìm max 5. Tìm max của cây con bên trái 265 Ví dụ tìm x = 23 266 7 3 36 1 6 15 40 234 Các thao tác 1. Tạo cây 2. Duyệt cây 3. Cho biết các thông tin của cây 4. Tìm kiếm 5. Xoá node trên cây 267 Các thao tác 1. Tạo cây 2. Duyệt cây 3. Cho biết các thông tin của cây 4. Tìm kiếm 5. Xoá node trên cây 268 Xóa node trên cây 1. Node lá 2. Node có 1 cây con 3. Node có 2 cây con 269 7 3 36 1 6 15 40 234 Xóa node lá Xóa 1 Xóa 23 270 7 3 36 1 6 15 40 234 Xóa node 1 cây con Xóa 6 Xóa 15 271 7 3 36 1 6 15 40 234 4 23 Xóa node 2 cây con Tìm node thế mạng Cách 1: Tìm node trái nhất của cây con phải (min của T->Right) Cách 2: Tìm node phải nhất của cây con trái (max của T->Left) Xóa 36 (Cách 2) 272 7 3 36 1 6 15 40 234 16 23 Cho dãy số theo thứ tự nhập từ trái sang phải: 20, 15, 35, 30, 11, 13, 17, 36, 47, 16, 38, 28, 14 Vẽ cây nhị phân tìm kiếm cho dãy số trên Cho biết kết quả duyệt cây trên theo thứ tự trước, giữa và sau Cho biết độ cao của cây, các nút lá, các nút có bậc 2 Vẽ lại cây sau khi thêm nút: 25 và 91 Trình bày từng bước và vẽ lại cây sau khi lần lượt xoá các nút: 11 và 35 273
File đính kèm:
bai_giang_cau_truc_du_lieu_va_giai_thuat_nguyen_huu_dung.pdf