Bài giảng Lập trình - Chương 6: Lập trình tổng quát

Nội dung text: Bài giảng Lập trình - Chương 6: Lập trình tổng quát

1. Lập trình Chương 6: Lập trình tổng quát 2/10/2017
2. Nội dung . 6.1 Khuân mẫu hàm (Function template) . 6.2 Khuân mẫu lớp . 6.3 Thuật toán tổng quát Chương 5: Lập trình tổng quát 2
3. 6.1 Khuân mẫu hàm . Ví dụ hàm tìm giá trị lớn nhất a. Tìm max hai số nguyên int max(const int &a, const int &b){ return (a > b)? a: b; } b. Tìm max hai số thực float max(const float &a, const float &b){ return (a > b)? a: b; } . Nhận xét: Các hàm tìm max của hai số chỉ khác nhau về kiểu dữ liệu, thuật toán giống nhau. . Tương tự như vậy có rất nhiều hàm chỉ khác nhau về kiểu dữ liệu, không khác về thuật toán . Giải pháp: tổng quát hóa các hàm chỉ khác nhau về kiểu khuôn mẫu hàm Chương 5: Lập trình tổng quát 3
4. . Ví dụ tổng quát hóa hàm max Tham số khuôn mẫu template T max(const T &a,const T &b){ Sử dụng từ khóa return (a > b)? a: b; class hoặc typename để khai báo tham số } khuôn mẫu . Khuôn mẫu hàm inline template inline T max(const T &a,const T &b) { return (a > b)? a : b; } . Sử dụng Compiler sẽ tạo một hàm theo khuôn mẫu có dạng int max(const int&, const int&) int max(5,7); Chương 5: Lập trình tổng quát 4
5. . Ví dụ sử dụng void main() { int i1 = 1, i2 = 5; double d1 = 1.0, d2 = 2.0; double d = max(d1,d2); // max (double,double) char c = max('c','a'); // max (char, char) d = max(i1,d1); // error: ambiguous c = max('c',i1); // error: ambiguous d = max (d1,i1); // OK: explicit qualification c = max ('c',i1); // OK: explicit qualification } . Áp dụng cho complex? class complex{ void main{ double real, imag; complex c1(1.1,2.0); public: complex c2(2.0,2.2); complex(double r=0,int complex c = max(c1,c2); i=0); }; double get_real(); Lỗi, vì lớp complex trên chưa định void set_real(double); nghĩa phép so sánh > sử dụng trong double get_imag(); hàm khuôn mẫu max void set_imag(double); }; Chương 5: Lập trình tổng quát 5
6. . Giải pháp cho trường hợp trên là định nghĩa toán tử so sánh lớn hơn cho lớp complex. . Một khuôn mẫu hàm cũng có thể được nạp chồng bởi hàm cùng tên hoặc bởi một khuôn mẫu hàm cùng tên (khác số lượng các tham số hoặc kiểu của ít nhất một tham số) – Hàm cùng tên để thực hiện cho các thuật toán đặc biệt. (Ví dụ, hàm max giữa hai chuỗi ký tự có thuật toán thực hiện khác với tìm max của hai số int hoặc double) – Khuôn mẫu hàm cùng tên template T max(T a, T b, T c) { } template T max(T* a, int n) { } nhưng không được như thế này: template T max(T a, T b, T c) { } template X max(X a, X b, X c) { } Chương 5: Lập trình tổng quát 6
7. . Tham số khuôn mẫu hàm có thể có hơn một tham số kiểu, ví dụ: template void swap(A& a, B& b){ } . Ví dụ: template void swap( A &a, B &b){ A temp = a; a = b; //đúng khi b tương thích với a b = temp; //đúng khi temp tương thích với b } void main(){ int a = 5; double b = 10.2; swap(a,b); //swap (int,double) swap(b,a); //swap (double,int) } Chương 5: Lập trình tổng quát 7
8. Tóm lược . Khi sử dụng compiler cần biết mã nguồn thực hiện khuôn mẫu hàm, do vậy khai báo và định nghĩa khuôn mẫu hàm nên để ở header file sử dụng template sẽ công khai hết phần thực hiện . Mã hàm khuôn mẫu chỉ được thực sự sinh ra khi và chỉ khi khuôn mẫu hàm được sử dụng với kiểu cụ thể . Một khuôn mẫu hàm được sử dụng nhiều lần với các kiểu khác nhau thì nhiều hàm khuôn mẫu được tạo ra . Một khuôn mẫu hàm được sử dụng nhiều lần với cùng một kiểu, thì chỉ có một hàm khuôn mẫu được tạo Chương 5: Lập trình tổng quát 8
9. Ưu/nhược điểm của khuôn mẫu hàm . Ưu điểm – Tiết kiệm được mã nguồn – Tính mở: nâng cao tính sử dụng lại, thuật toán viết một lần sử dụng vô số lần – Cho phép xây dựng các thư viên chuẩn rất mạnh như các thư viện thuật toán thông dụng: sao chép, tìm kiếm, sắp xếp, lựa chọn, . Nhược điểm – Không che giấu được mã nguồn thực thi, vì compiler phải biết mã nguồn khi biên dịch – Theo dõi, tìm kiếm lỗi phức tạp, đôi khi lỗi nằm ở phần sử dụng nhưng compiler lại báo trong phần định nghĩa khuôn mẫu hàm Chương 5: Lập trình tổng quát 9
10. 6.2 Khuôn mẫu lớp . Nghiên cứu lớp số phức #include class IntComplex{ int real,imag; public: Complex(int r = 0, int i =0): real(r),imag(i) {} int get_real() const { return real; } int get_imag() const { return imag; } Complex operator+(const Complex& b) const { Complex z(real + b.real, imag + b.image); return z; } Complex operator-(const Complex& b) const { return Complex(real - b.real, imag - b.imag); } }; Chương 5: Lập trình tổng quát 10
11. class DoubleComplex{ double real,imag; public: Complex(double r = 0, double i =0): real(r),imag(i) {} double get_real() const { return real; } double get_imag() const { return imag; } Complex operator+(const Complex& b) const { Complex z(real + b.real, imag + b.image); return z; } Complex operator-(const Complex& b) const { return Complex(real - b.real, imag - b.imag); } }; . Hai lớp số phức trên khác nhau gì? Giống nhau gì? Chương 5: Lập trình tổng quát 11
12. . Tương tự nhu vậy, trong thực tế có rất nhiều cấu trúc dữ liệu chỉ khác nhau về kiểu dữ liệu còn hoàn toàn giống về phép toán, ví dụ như vector, list, complex, . Để tiết kiệm mã nguồn thực thi tổng quát hóa kiểu dữ liệu cho lớp template class Complex{ T real,imag; public: Complex(T r = 0, T i =0): real(r),imag(i) {} T get_real() const { return real; } T get_imag() const { return imag; } Complex operator+(const Complex& b) const { Complex z(real + b.real, imag + b.image); return z; } Complex operator-(const Complex& b) const; }; Chương 5: Lập trình tổng quát 12
13. . Định nghĩa hàm thành viên bên ngoài khai báo lớp template Complex ::Complex operator-(const Complex & b) const { return Complex (real - b.real, imag - b.imag); } . Sử dụng void main{ Complex c1(1,1), c2(2,3); Complex c3 = c1+c2; Complex c4(1.0,2.0), c5(3.0,5.0); Complex c6 = c4 + c5; }; Chương 5: Lập trình tổng quát 13
14. Tham số khuôn mẫu . Tham số khuôn mẫu có thể là hằng hoặc kiểu (để làm tham số mặc định) template class Array{ T data[N]; public: Tham số mặc định }; . Sử dụng void main(){ Array a; Giống nhau Array b; Array<> c; } Chương 5: Lập trình tổng quát 14
15. Bài tập . Xây dựng một khuôn mẫu hàm cho phép tìm giá trị lớn nhất/hoặc nhỏ nhất trong một mảng . Tổng quát hóa kiểu dữ liệu cho lớp array, thực hiện các hàm thành viên cần thiết để có thể – Khai báo và khởi tạo giá trị ban đầu – Hủy bộ nhớ khi không còn sử dụng – Thực hiện các phép toán +,-, +=, -=, Chương 5: Lập trình tổng quát 15
16. 6.3 Thuật toán tổng quát . Ví dụ: hãy viết hàm sắp xếp các phần tử của một mảng theo thứ tự từ nhỏ đến lớn void sort(int *p, int n){ for(int i = 0; i i; j) if(p[j] < p[j-1]) swap(p[j], p[j-1]); } void swap(int &a, int &b){ int t = a; a = b; b = t; } Chương 5: Lập trình tổng quát 16
17. . 1. Tổng quát hóa kiểu dữ liệu của các phần tử template void sort(T *p, int n){ for(int i = 0; i i; j) if(p[j] p3[100]; sort(p3,100) //Lỗi, chỉ áp dụng được khi lớp complex định //nghĩa phép so sánh nhỏ hơn Chương 5: Lập trình tổng quát 17
18. . Câu hỏi: làm thế nào để ta có thể sắp xếp lại từ lớn đến nhỏ mà không cần phải viết lại hàm . Giải pháp: cho thêm tham biến vào khai báo hàm enum comparetype {less, greater, abs_less, abs_greater}; template void sort(T *p, int n,comparetype c){ for(int i = 0; i i; j) switch(c){ case less: if(p[j] p[j-1]) swap(p[j], p[j-1]); break; case abs_less: if(abs(p[j]) abs(p[j-1])) swap(p[j], p[j-1]); break; } } Chương 5: Lập trình tổng quát 18
19. . Nhược điểm: – Hiệu quả không cao – Tốc độ chậm – Không có tính năng mở: ví dụ nếu muốn só sánh số phức theo phần thực thì không dùng được cách trên . Giải pháp: tổng quát hóa phép toán template void sort(T *p, int n, Compare comp){ for(int i = 0; i i; j) if(comp(p[j], p[j-1])) swap(p[j], p[j-1]); } . Kiểu Compare có thể là – Một hàm – Một đối tượng thuộc lớp có định nghĩa lại toán tử gọi hàm Chương 5: Lập trình tổng quát 19
20. . Kiểu Compare là một hàm template inline bool less(const T &a, const T &b){ return a inline bool greater(const T &a, const T &b){ return a > b; //return operator>(a,b) } – Sử dụng int v[100]; double d[100]; Một hàm sort(v,100,less ); sort(d,100,greater ) Chương 5: Lập trình tổng quát 20
21. – So sánh số phức template inline bool less_real(const complex &a, const complex &b){ return (a.get_real() > b.get_real()) //return operator>(a,b) } – Sử dụng complex c[100]; Sort(c,100,less_real ); Chương 5: Lập trình tổng quát 21
22. . Kiểu compare là một đối tượng có định nghĩa lại toán tử gọi hàm template struct Less { bool operator()(const T &a, const T &b){ return a struct Greater { bool operator()(const T &a, const T &b){ return a>b; } }; – Sử dụng int v[100]; double d[100]; Một đối tượng sort(v,100,Less ()); sort(d,100,Greater ()) Chương 5: Lập trình tổng quát 22
23. Bài tập . Áp dụng tổng quát hóa kiểu dữ liệu và tổng quát hóa phép toán để xây dựng các hàm càn thiết thực hiện các phép toán cộng, trừ, nhân, chia từng phần tử của hai mảng. Sau đó viết chương trình minh họa cách sử dụng. . Gợi ý: – Hàm thực hiện phép toán template void operation(T *p1, T *p2, T *result,int n, OP op){ } – Định nghĩa phép toán theo dạng hàm template T add(const T &a, const T &b){ } – Hoặc định nghĩa phép toán theo dạng đối tượng template struct Add{ }; Chương 5: Lập trình tổng quát 23
24. Chương trình template void operation(T* p1, T* p2,T* result,int n, OP op){ for(int i = 0;i T add(const T& a, const T& b){ return a+b;} template struct Add{ T operator()(const T& a, const T& b){ return a+b;} }; template void display(const T& a, int n){ cout<<"\n"; for(int i = 0;i<n;i++) cout<<"\t"<<a[i]; } Chương 5: Lập trình tổng quát 24
25. Chương trình void main(){ int a[5] = {1,2,3,4,5}; int b[5] = {11,12,13,14,15}; int result[5]; operation(a,b,result,5,add ); display(result,5); operation(a,b,result,5,Add ()); display(result,5); } Chương 5: Lập trình tổng quát 25