Bài giảng Lập trình: Chương 6 - Vũ Song Tùng

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:25

Thêm vào BST

Báo xấu

22
lượt xem 3
download

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

Bài giảng Lập trình chương 6 trang bị cho người học những kiến thức cơ bản về lập trình tổng quát như: Khuôn mẫu hàm (function template), khuân mẫu lớp, thuật toán tổng quát. Mời các bạn cùng tham khảo.

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 Lập trình: Chương 6 - Vũ Song Tùng

om .c Lập trình ng co an Chương 6: Lập trình tổng quát th o ng du u cu 2/10/2017 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Nội dung  6.1 Khuân mẫu hàm (Function template) om  6.2 Khuân mẫu lớp .c  6.3 Thuật toán tổng quát ng co an th o ng du u cu Chương 5: Lập trình tổng quát 2 CuuDuongThanCong.com https://fb.com/tailieudientucntt
6.1 Khuân mẫu hàm  Ví dụ hàm tìm giá trị lớn nhất om a. Tìm max hai số nguyên int max(const int &a, const int &b){ .c return (a > b)? a: b; ng } co an b. Tìm max hai số thực th float max(const float &a, const float &b){ ng return (a > b)? a: b; o } du  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, u thuật toán giống nhau. cu  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 CuuDuongThanCong.com https://fb.com/tailieudientucntt
 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 om return (a > b)? a: b; class hoặc typename để khai báo tham số .c } khuôn mẫu ng  Khuôn mẫu hàm inline co template inline T max(const T &a,const T &b) { an return (a > b)? a : b; th } Compiler sẽ tạo một hàm theo khuôn mẫu ng  Sử dụng có dạng int max(const int&, const int&) o int max(5,7); du u cu Chương 5: Lập trình tổng quát 4 CuuDuongThanCong.com https://fb.com/tailieudientucntt
 Ví dụ sử dụng void main() { int i1 = 1, i2 = 5; double d1 = 1.0, d2 = 2.0; om double d = max(d1,d2); // max(double,double) char c = max('c','a'); // max(char, char) .c d = max(i1,d1); // error: ambiguous ng c = max('c',i1); // error: ambiguous d = max(d1,i1); // OK: explicit qualification co c = max('c',i1); // OK: explicit qualification } an  Áp dụng cho complex? th ng class complex{ void main{ double real, imag; complex c1(1.1,2.0); o complex c2(2.0,2.2); du public: complex(double r=0,int complex c = max(c1,c2); u i=0); }; cu 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 CuuDuongThanCong.com https://fb.com/tailieudientucntt
 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 om 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 .c tham số) ng – Hàm cùng tên để thực hiện cho các thuật toán đặc biệt. (Ví co dụ, hàm max giữa hai chuỗi ký tự có thuật toán thực hiện an khác với tìm max của hai số int hoặc double) th – Khuôn mẫu hàm cùng tên ng template T max(T a, T b, T c) {...} o template T max(T* a, int n) {...} du nhưng không được như thế này: u template T max(T a, T b, T c) {...} cu template X max(X a, X b, X c) {...} Chương 5: Lập trình tổng quát 6 CuuDuongThanCong.com https://fb.com/tailieudientucntt
 Tham số khuôn mẫu hàm có thể có hơn một tham số om kiểu, ví dụ: template void swap(A& a, B& b){…} .c ng  Ví dụ: co template void swap( A &a, B &b){ an A temp = a; th a = b; //đúng khi b tương thích với a b = temp; //đúng khi temp tương thích với b ng } o void main(){ du int a = 5; double b = 10.2; u swap(a,b); //swap(int,double) cu swap(b,a); //swap(double,int) } Chương 5: Lập trình tổng quát 7 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Tóm lược  Khi sử dụng compiler cần biết mã nguồn thực hiện om 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 .c template sẽ công khai hết phần thực hiện ng  Mã hàm khuôn mẫu chỉ được thực sự sinh ra khi và co chỉ khi khuôn mẫu hàm được sử dụng với kiểu cụ thể an th  Một khuôn mẫu hàm được sử dụng nhiều lần với các ng kiểu khác nhau thì nhiều hàm khuôn mẫu được tạo o ra du  Một khuôn mẫu hàm được sử dụng nhiều lần với u cu 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 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Ưu/nhược điểm của khuôn mẫu hàm  Ưu điểm om – Tiết kiệm được mã nguồn .c – 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 ng – Cho phép xây dựng các thư viên chuẩn rất mạnh như các co thư viện thuật toán thông dụng: sao chép, tìm kiếm, sắp xếp, an lựa chọn,… th  Nhược điểm ng – Không che giấu được mã nguồn thực thi, vì compiler phải o biết mã nguồn khi biên dịch du – Theo dõi, tìm kiếm lỗi phức tạp, đôi khi lỗi nằm ở phần sử u cu 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 CuuDuongThanCong.com https://fb.com/tailieudientucntt
6.2 Khuôn mẫu lớp  Nghiên cứu lớp số phức om #include class IntComplex{ .c int real,imag; ng public: Complex(int r = 0, int i =0): real(r),imag(i) {} co int get_real() const { return real; } int get_imag() const { return imag; } an Complex operator+(const Complex& b) const { th Complex z(real + b.real, imag + b.image); ng return z; } o Complex operator-(const Complex& b) const { du return Complex(real - b.real, imag - b.imag); u } cu ... }; Chương 5: Lập trình tổng quát 10 CuuDuongThanCong.com https://fb.com/tailieudientucntt
class DoubleComplex{ double real,imag; public: om Complex(double r = 0, double i =0): real(r),imag(i) {} double get_real() const { return real; } .c double get_imag() const { return imag; } Complex operator+(const Complex& b) const { ng Complex z(real + b.real, imag + b.image); return z; co } an Complex operator-(const Complex& b) const { return Complex(real - b.real, imag - b.imag); th } ng ... }; o du  Hai lớp số phức trên khác nhau gì? Giống nhau gì? u cu Chương 5: Lập trình tổng quát 11 CuuDuongThanCong.com https://fb.com/tailieudientucntt
 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,… om  Để tiết kiệm mã nguồn thực thi  tổng quát hóa kiểu .c dữ liệu cho lớp ng template class Complex{ co T real,imag; public: an Complex(T r = 0, T i =0): real(r),imag(i) {} th T get_real() const { return real; } ng T get_imag() const { return imag; } Complex operator+(const Complex& b) const { o Complex z(real + b.real, imag + b.image); du return z; u } cu Complex operator-(const Complex& b) const; ... }; Chương 5: Lập trình tổng quát 12 CuuDuongThanCong.com https://fb.com/tailieudientucntt
 Đị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 { om return Complex(real - b.real, imag - b.imag); .c } ng co  Sử dụng an void main{ th Complex c1(1,1), c2(2,3); ng Complex c3 = c1+c2; Complex c4(1.0,2.0), c5(3.0,5.0); o Complex c6 = c4 + c5; du }; u cu Chương 5: Lập trình tổng quát 13 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Tham số khuôn mẫu  Tham số khuôn mẫu có thể là hằng hoặc kiểu (để làm om tham số mặc định) .c template class Array{ ng T data[N]; public: co ... Tham số mặc định an }; th  Sử dụng ng o void main(){ du Array a; Giống nhau u Array b; cu Array c; } Chương 5: Lập trình tổng quát 14 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Bài tập  Xây dựng một khuôn mẫu hàm cho phép tìm giá trị om lớn nhất/hoặc nhỏ nhất trong một mảng .c  Tổng quát hóa kiểu dữ liệu cho lớp array, thực hiện ng các hàm thành viên cần thiết để có thể co – Khai báo và khởi tạo giá trị ban đầu – Hủy bộ nhớ khi không còn sử dụng an th – Thực hiện các phép toán +,-, +=, -=,… o ng du u cu Chương 5: Lập trình tổng quát 15 CuuDuongThanCong.com https://fb.com/tailieudientucntt
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 om mảng theo thứ tự từ nhỏ đến lớn .c void sort(int *p, int n){ for(int i = 0; i < n-1; i++) ng for(int j = n-1; j > i; --j) if(p[j] < p[j-1]) co swap(p[j], p[j-1]); an } void swap(int &a, int &b){ th int t = a; ng a = b; b = t; o } du u cu Chương 5: Lập trình tổng quát 16 CuuDuongThanCong.com https://fb.com/tailieudientucntt
 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 < n-1; i++) om for(int j = n-1; j > i; --j) if(p[j] < p[j-1]) .c swap(p[j], p[j-1]); } ng void swap(T &a, T &b){ co T t = a; a = b; an b = t; th } ng  Thuật toán trên áp dụng cho nhiều kiểu dữ liệu có o định nghĩa phép so sánh nhỏ hơn du Int p[100]; u sort(p,100); //OK cu char p2[100]; sort(p2,100); //OK complex 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 CuuDuongThanCong.com https://fb.com/tailieudientucntt
 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}; om template void sort(T *p, int n,comparetype c){ .c for(int i = 0; i < n-1; i++) for(int j = n-1; j > i; --j) ng switch(c){ case less: co if(p[j] < p[j-1]) swap(p[j], p[j-1]); an break; th case greater: if(p[j] > p[j-1]) ng swap(p[j], p[j-1]); break; o case abs_less: du if(abs(p[j]) < abs(p[j-1]) swap(p[j], p[j-1]); u break; cu case abs_greater: 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 CuuDuongThanCong.com https://fb.com/tailieudientucntt
 Nhược điểm: – Hiệu quả không cao – Tốc độ chậm om – 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 .c  Giải pháp: tổng quát hóa phép toán ng template co void sort(T *p, int n, Compare comp){ an for(int i = 0; i < n-1; i++) for(int j = n-1; j > i; --j) th if(comp(p[j], p[j-1])) ng swap(p[j], p[j-1]); } o du  Kiểu Compare có thể là u – Một hàm cu – 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 CuuDuongThanCong.com https://fb.com/tailieudientucntt
 Kiểu Compare là một hàm template inline bool less(const T &a, const T &b){ return a < b; //return operator b; //return operator>(a,b) co } an – Sử dụng th int v[100]; ng double d[100]; Một hàm o sort(v,100,less); du sort(d,100,greater) u cu Chương 5: Lập trình tổng quát 20 CuuDuongThanCong.com https://fb.com/tailieudientucntt