Xem mẫu
- 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
nguon tai.lieu . vn