Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 5: KDLTT danh sách cài đặt bằng mảng động

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 5: KDLTT danh sách cài đặt bằng mảng động

1. Bài 5: KDLTT danh sách cài đặt bằng mảng động Giảng viên: Hoàng Thị Điệp Khoa Công nghệ Thông tin – Đại học Công Nghệ Cấu trúc dữ liệu và giải thuật HKI, 2013-2014
2. Nội dung chính 1. Thư viện khuôn mẫu chuẩn STL 2. Con trỏ và bộ nhớ động C++ 3. KDLTT danh sách cài bằng mảng động  Bộ ba quan trọng  Cải tiến hàm insert, append 4. Ứng dụng KDLTT danh sách  Tập động  Đa thức  Ma trận thưa Mã nguồn minh họa 2 phần đầu được lấy và chỉnh sửa từ cplusplus.com 2 diepht@vnu
3. Thư viện khuôn mẫu chuẩn STL                   3 diepht@vnu
4. Khuôn mẫu (template) // khai báo thư viện // khai báo thư viện int getMaxI(int a, int b){ template int result; T getMax(T a, T b){ result = (a > b)? a : b; T result; return (result); result = (a > b)? a : b; } return (result); double getMaxD(double a, double b){ } double result; result = (a > b)? a : b; int main(){ return (result); int i=5, j=6, k; } double l=10.3, m=5.1, n; int main(){ k=getMax (i,j); int i=5, j=6, k; n=getMax (l,m); double l=10.3, m=5.1, n; cout << k << endl; k=getMaxI(i,j); cout << n << endl; n=getMaxD(l,m); return 0; cout << k << endl; } cout << n << endl; return 0; } 4 diepht@vnu
5. Ví dụ thư viện :: push_back() // vector::push_back #include #include #include using namespace std; int main() { vector myvector; int myint; cout > myint; myvector.push_back(myint); }while(myint); cout << "myvector chua " << int(myvector.size()) << " so nguyen.\n"; getch(); return 0; } 5 diepht@vnu
6. Ví dụ thư viện ::insert() // vector::insert // #include cac thu vien can thiet int main(){ vector myvector(3,100); vector ::iterator it; it = myvector.begin(); it = myvector.insert(it, 200); myvector.insert(it, 1, 300); // "it" khong con hop le, lap 1 gia tri moi: it = myvector.begin(); vector anothervector(2, 400); myvector.insert(it + 1, anothervector.begin(), anothervector.end()); int myarray[] = {501, 502, 503}; myvector.insert(myvector.begin(), myarray, myarray + 3); cout << "myvector chua day so:"; for(it = myvector.begin(); it < myvector.end(); it++) cout << ' ' << *it; cout << '\n'; getch(); return 0; 6 } diepht@vnu
7. Ví dụ thư viện ::erase() // vector::erase // #include cac thu vien can thiet int main(){ vector myvector; // them 1 vai gia tri ban dau (tu 1 den 10) for(int i = 1; i <= 10; i++) myvector.push_back(i); // xoa phan tu thu 6 myvector.erase(myvector.begin() + 5); // xoa 3 phan tu dau tien: myvector.erase(myvector.begin(), myvector.begin() + 3); cout << "myvector chua day so:"; for(unsigned i = 0; i < myvector.size(); ++i) cout << ' ' << myvector[i]; cout << '\n'; getch(); return 0; } 7 diepht@vnu
8. Nội dung chính 1. Thư viện khuôn mẫu chuẩn STL 2. Con trỏ và bộ nhớ động C++ 3. KDLTT danh sách cài bằng mảng động  Bộ ba quan trọng  Cải tiến hàm insert, append 4. Ứng dụng KDLTT danh sách  Tập động  Đa thức  Ma trận thưa 8 diepht@vnu
9. Con trỏ và bộ nhớ động  Các vấn đề chính  Bộ nhớ máy tính  Biến và địa chỉ của biến  Biến con trỏ  Mảng và con trỏ  Bộ nhớ động: cấp phát và giải phóng  Mảng động và con trỏ  Truyền tham số là con trỏ  Tham khảo  Chương 6, Giáo trình: Lập trình cơ bản với C++  Tác giả: Trần Minh Châu, Lê Sỹ Vinh, Hồ Sĩ Đàm,   Day 8, Teach Yourself C++ in 21 Days 9 diepht@vnu
10. Toán tử lấy địa chỉ (&) andy = 25; fred = andy; ted = &andy; 10 diepht@vnu
11. Toán tử giải tham chiếu (*) beth = *ted; 11 diepht@vnu
12. Khai báo biến con trỏ: VD1 #include #include using namespace std; int main(){ int v1, v2; int * p; p = &v1; *p = 10; p = &v2; *p = 20; cout << "v1 = " << v1 << endl; cout << "v2 = " << v2 << endl; getch(); return 0; } 12 diepht@vnu
13. Khai báo biến con trỏ: VD2 #include #include using namespace std; int main(){ int v1 = 5, v2 = 15; int * p1, * p2; p1 = &v1; // p1 = dia chi cua v1 p2 = &v2; // p2 = dia chi cua v2 *p1 = 10; // gia tri cua bien tro boi p1 = 10 *p2 = *p1; // gtri cua bien tro boi p2 = // gtri cua bien tro boi p1 p1 = p2; // p1 = p2 (value of pointer is copied) *p1 = 20; // gia tri cua bien tro boi p1 = 20 cout << "v1 = " << v1 << endl; cout << "v2 = " << v2 << endl; getch(); return 0; } 13 diepht@vnu
14. Con trỏ và mảng #include #include using namespace std; int main() { int numbers[5]; int * p; p = numbers; *p = 2; p++; *p = 3; p = &numbers[2]; *p = 5; p = numbers + 3; *p = 7; p = numbers; *(p+4) = 9; for(int n = 0; n<5; n++) cout << numbers[n] << ", "; getch(); return 0; } 14 diepht@vnu
15. Khởi tạo con trỏ const char * terry = "hello"; 15 diepht@vnu
16. Phép toán số học trên con trỏ char *mychar; short *myshort; long *mylong; mychar++; myshort++; mylong++; 16 diepht@vnu
17. Con trỏ tới con trỏ char a; char * b; char c; a = 'z'; b = &a; c = &b; 17 diepht@vnu
18. new và delete biến đơn 18 diepht@vnu
19. new và delete mảng 19 diepht@vnu
20. Nội dung chính 1. Thư viện khuôn mẫu chuẩn STL 2. Con trỏ và bộ nhớ động C++ 3. KDLTT danh sách cài bằng mảng động  Bộ ba quan trọng  Cải tiến hàm insert, append 4. Ứng dụng KDLTT danh sách  Tập động  Đa thức  Ma trận thưa 20 diepht@vnu
21. KDLTT danh sách cài bằng mảng C++ Cấp phát tĩnh Cấp phát động template template class List{ class Dlist{ public: public: static const int MAX = 50; // // private: private: Item * element; Item element[MAX]; int size; int last; int last; }; }; 21 diepht@vnu
22. Bộ ba quan trọng Dlist có thành phần dữ liệu cấp phát động nên phải cài đặt bộ ba 1. Hàm kiến tạo sao chép  copy constructor 2. Toán tử gán  operator=  overloading operator 3. Hàm hủy  destructor 22 diepht@vnu
23. Hàm insert, append của Dlist  L = (1, 3, 4, 8); size = 4; last = 3  insert(L, 3, 50) cũ mới 1 3 4 8 1 3 4 8 1 3 4 1 3 4 8 1 3 4 50 1 3 4 8 1 3 4 50 8 1 3 4 8 L = (1, 3, 4, 50, 8); size = 8; last = 4 23 diepht@vnu
24. Hàm insert, append của Dlist Khi mảng đầy  Cấp phát động một mảng mới có cỡ gấp đôi mảng cũ  Chép đoạn đầu của mảng cũ sang mảng mới  Đưa phần tử cần xen vào mảng mới  Chép đoạn còn lại của mảng cũ sang mảng mới  Hủy mảng cũ  Cập nhật size, last Viết mã C++! 24 diepht@vnu
25. Nội dung chính 1. Thư viện khuôn mẫu chuẩn STL 2. Con trỏ và bộ nhớ động C++ 3. KDLTT danh sách cài bằng mảng động  Bộ ba quan trọng  Cải tiến hàm insert, append 4. Ứng dụng KDLTT danh sách  Tập động  Đa thức  Ma trận thưa 25 diepht@vnu
26. Ứng dụng KDLTT danh sách  Tập động  Mỗi phần tử có thành phần khóa phân biệt. Các giá trị khóa có quan hệ thứ tự  Các phép toán: empty, insert, erase, seach, getMax, getMin  Ví dụ: ((“An”, 1985), (“Bình”, 1986), (“Cường, 1985), (“Dung”, 1987))  Cài bằng danh sách được sắp hay không được sắp thì tốt hơn? 26 diepht@vnu
27. Bài tập  Dùng ngôn ngữ C++, viết khai báo lớp IntSet cài đặt KDLTT tập động các số nguyên. 27 diepht@vnu
28. Ứng dụng KDLTT danh sách  Đa thức  Ví dụ: ((17,5), (-25, 2), (14, 1), (-32, 0)) biểu diễn đa thức 17x5 – 25x2 + 14x – 32  Các phép toán: cộng, trừ, nhân 28 diepht@vnu
29. Ứng dụng KDLTT danh sách  Ma trận thưa  Ma trận chỉ chứa một số ít các phần tử khác 0  Cách biểu diễn:  Xem ma trận như danh sách các dòng  Mỗi dòng là một danh sách biểu diễn các phần tử khác 0  Mỗi phần tử khác 0 là một cặp (chỉ số cột, giá trị)  Ví dụ: (((2, 7), (5, 3)), ((3, 8)), (), ((2, 5), (4, 9)))  Các phép toán trên ma trận, trên dòng, trên phần tử 29 diepht@vnu
30. Tìm kiếm nhị phân Algorithm binarySearch(x, A, first, last): Input: search keyword x and array A of Items with two ends marked by indexes first and last Output: true if x in A, false otherwise if first > last then return false mid  (first + last) / 2 if x = A[mid].key then return true else if x < A[mid].key then binarySearch(x, A, first, mid - 1) else binarySearch(x, A, mid + 1, last) 30 diepht@vnu
31. Tìm kiếm nhị phân A  1 3 4 6 8 9 11 chỉ số  0 1 2 3 4 5 6 A = (1, 3, 4, 6, 8, 9, 11); x = 4. search(x, A).  binarySearch(x, A, first, last)  binarySearch(x, A, 0, 6)  So x với A[3]. x nhỏ hơn.  binarySearch(x, A, 0, 2)  So x với A[1]. x lớn hơn.  binarySearch(x, A, 2, 2)  So x với A[2]. Bằng. Trả về true. 31 diepht@vnu