Kỹ thuật lập trình - Chương 10: Thuật toán tổng quát

 ₫ịa chỉ phần tử ₫ầu tiên trong một mảng có giá
trị lớn hơn một số cho trước:
template 
T* find_elem(T *first, T* last, T k) {
while (first != last && !(*first > k))
++first;
return first;
}
void main() {
int a[] = { 1, 3, 5, 2, 7, 9, 6 };
int *p = find_elem(a,a+7,4);
if (p != a+7) {
cout 4 :" << *p;
p = find_elem(p+1,a+7,4);
if (p != a+7) cout 4:" << *p;
}
double b[] = { 1.5, 3.2, 5.1, 2.4, 7.6, 9.7, 6.5 };
double *q = find_elem(b+2,b+6,7.0);
*q = 7.0;
...
}
5Chương 10: Thuật toán tổng quát
ƒ Ví dụ: Thuật toán cộng hai vector, kết quả lưu vào vector thứ ba
#include 
#include "myvector.h"
template 
void addVector(const Vector& a, const Vector& b,
Vector& c) {
assert(a.size() == b.size() && a.size() == c.size()); 
for (int i= 0; i < a.size(); ++i)
c[i] = a[i] + b[i];
} 
template 
Vector operator+(const Vector&a, const Vector& b) {
Vector c(a.size());
addVector(a,b,c);
return c;
}
6Chương 10: Thuật toán tổng quát
10.2 Tổng quát hóa phép toán cơ sở
ƒ Vấn ₫ề: Nhiều thuật toán chỉ khác nhau ở một vài phép toán 
(cơ sở) trong khi thực hiện hàm
ƒ Ví dụ:
— Các thuật toán tìm ₫ịa chỉ phần tử ₫ầu tiên trong một mảng số
nguyên có giá trị lớn hơn, nhỏ hơn, lớn hơn hoặc bằng, nhỏ hơn 
hoặc bằng, ... một số cho trước
— Các thuật toán cộng, trừ, nhân, chia,... từng phần tử của hai mảng 
số thực, kết quả lưu vào một mảng mới
— Các thuật toán cộng, trừ, nhân, chia,... từng phần tử của hai 
vector (hoặc của hai danh sách, hai ma trận, ...)
ƒ Giải pháp: Tổng quát hóa thuật toán cho các phép toán cơ sở
khác nhau!
7Chương 10: Thuật toán tổng quát
template 
int* find_elem(int* first, int* last, int k, COMP comp) {
while (first != last && !comp(*first, k)) 
++first;
return first;
}
bool is_greater(int a, int b) { return a > b; }
bool is_less(int a, int b) { return a < b; }
bool is_equal(int a, int b) { return a == b;}
void main() {
int a[] = { 1, 3, 5, 2, 7, 9, 6 };
int* alast = a+7;
int* p1 = find_elem(a,alast,4,is_greater);
int* p2 = find_elem(a,alast,4,is_less);
int* p3 = find_elem(a,alast,4,is_equal);
if (p1 != alast) cout 4 is " << *p1;
if (p2 != alast) cout << "First number < 4 is " << *p2;
if (p3 != alast) cout << "First number = 4 is at index " 
<< p3 - a;
char c; cin >> c;
}
8Chương 10: Thuật toán tổng quát
Tham số khuôn mẫu cho phép toán
ƒ Có thể là một hàm, ví dụ
bool is_greater(int a, int b){ return a > b; }
bool is_less(int a, int b) { return a < b; }
int add(int a, int b) { return a + b; }
int sub(int a, int b) { return a - b; }
...
ƒ Hoặc tốt hơn hết là một ₫ối tượng thuộc một lớp có hỗ trợ (nạp
chồng) toán tử gọi hàm => ₫ối tượng hàm, ví dụ
struct Greater {
bool operator()(int a, int b) { return a > b; }
};
struct Less {
bool operator()(int a, int b) { return a < b; }
};
struct Add {
int operator()(int a, int b) { return a + b; }
};
...
9Chương 10: Thuật toán tổng quát
ƒ Ví dụ sử dụng ₫ối tượng hàm
void main() {
int a[] = { 1, 3, 5, 2, 7, 9, 6 };
int* alast = a+7;
Greater greater;
Less less;
int* p1 = find_elem(a,alast,4,greater);
int* p2 = find_elem(a,alast,4,less);
if (p1 != alast) cout 4 is " << *p1;
if (p2 != alast) cout << "First number < 4 is " << *p2;
p1 = find_elem(a,alast,4,Greater());
p2 = find_elem(a,alast,4,Less());
char c; cin >> c;
}
10Chương 10: Thuật toán tổng quát
Ưu ₫iểm của ₫ối tượng hàm
ƒ Đối tượng hàm có thể chứa trạng thái
ƒ Hàm toán tử () có thể ₫ịnh nghĩa inline => tăng hiệu suất
template 
void apply(int* first, int* last, OP& op) {
while (first != last) {
op(*first);
++first;
}
}
class Sum {
int val;
public:
Sum(int init = 0) : val(init) {}
void operator()(int k) { val += k; }
int value() const { return val; }
};
11Chương 10: Thuật toán tổng quát
class Prod {
int val;
public:
Prod(int init=1): val(init) {}
void operator()(int k) { val *= k; }
int value() const { return val; }
};
struct Negate {void operator()(int& k) { k = -k;} };
struct Print { void operator()(int& k) { cout << k << ' ';} };
void main() {
int a[] = {1, 2, 3, 4, 5, 6, 7};
Sum sum_op; 
Prod prod_op;
apply(a,a+7,sum_op); cout << sum_op.value() << endl;
apply(a,a+7,prod_op); cout << prod_op.value() << endl;
apply(a,a+7,Negate());
apply(a,a+7,Print());
char c; cin >> c;
}
12Chương 10: Thuật toán tổng quát
Kết hợp 2 bước tổng quát hóa
template 
T* find_elem(T* first, T* last, T k, COMP comp) {
while (first != last && !comp(*first, k)) 
++first;
return first;
}
template 
void apply(T* first, T* last, OP& op) {
while (first != last) {
op(*first);
++first;
}
}
13Chương 10: Thuật toán tổng quát
Khuôn mẫu lớp cho các ₫ối tượng hàm
template struct Greater{
bool operator()(const T& a, const T& b) 
{ return a > b; } 
};
template struct Less{
bool operator()(const T& a, const T& b) 
{ return a > b; }
};
template class Sum {
T val;
public:
Sum(const T& init = T(0)) : val(init) {}
void operator()(const T& k) { val += k; }
T value() const { return val; }
};
14Chương 10: Thuật toán tổng quát
template struct Negate {
void operator()(T& k) { k = -k;} 
};
template struct Print { 
void operator()(const T& k) { cout << k << ' ';} 
};
void main() {
int a[] = { 1, 3, 5, 2, 7, 9, 6 };
int* alast = a+7;
int* p1 = find_elem(a,alast,4,Greater());
int* p2 = find_elem(a,alast,4,Less());
if (p1 != alast) cout 4 is " << *p1;
if (p2 != alast) cout << "\nFirst number < 4 is " << *p2;
Sum sum_op; apply(a,a+7,sum_op); 
cout<< "\nSum of the sequence " << sum_op.value() << endl;
apply(a,a+7,Negate());
apply(a,a+7,Print());
char c; cin >> c;
}
15Chương 10: Thuật toán tổng quát
10.3 Tổng quát hóa truy lặp phần tử
ƒ Vấn ₫ề 1: Một thuật toán (tìm kiếm, lựa chọn, phân loại, tính 
tổng, ...) áp dụng cho một mảng, một vector, một danh sách 
họăc một cấu trúc khác thực chất chỉ khác nhau ở cách truy 
lặp phần tử
ƒ Vấn ₫ề 2: Theo phương pháp truyền thống, ₫ể truy lặp phần tử
của một cấu trúc "container", nói chung ta cần biết cấu trúc ₫ó 
₫ược xây dựng như thế nào
— Mảng: Truy lặp qua chỉ số hoặc qua con trỏ
— Vector: Truy lặp qua chỉ số
— List: Truy lặp qua quan hệ móc nối (sử dụng con trỏ)
— ...
16Chương 10: Thuật toán tổng quát
Ví dụ thuật toán copy
ƒ Áp dụng cho kiểu mảng thô
template void copy(const T* s, T* d, int n) {
while (n--) { *d = *s; ++s; ++d; }
}
ƒ Áp dụng cho kiểu Vector
template 
void copy(const Vector& s, Vector& d) {
for (int i=0; i < s.size(); ++i) d[i] = s[i];
}
ƒ Áp dụng cho kiểu List
template 
void copy(const List& s, List& d) {
ListItem *sItem=s.getHead(), *dItem=d.getHead();
while (sItem != 0) { 
dItem->data = sItem->data;
dIem = dItem->getNext(); sItem=sItem->getNext();
}
}
17Chương 10: Thuật toán tổng quát
Ví dụ thuật toán find_max
ƒ Áp dụng cho kiểu mảng thô
template T* find_max(T* first, T* last) {
T* pMax = first;
while (first != last) {
if (*first > *pMax) pMax = first;
++first; 
}
return pMax;
}
ƒ Áp dụng cho kiểu Vector
template T* find_max(const Vector& v) {
int iMax = 0;
for (int i=0; i < v.size(); ++ i)
if (v[i] > v[iMax]) iMax = i;
return &v[iMax]; 
}
18Chương 10: Thuật toán tổng quát
ƒ Áp dụng cho kiểu List (₫ã làm quen):
template 
ListItem* find_max(List& l) {
ListItem *pItem = l.getHead();
ListItem *pMaxItem = pItem;
while (pItem != 0) { 
if (pItem->data > pMaxItem->data) pMaxItem = pItem;
pItem = pItem->getNext();
}
return pMaxItem;
}
 Cần tổng quát hóa phương pháp truy lặp phần tử!
19Chương 10: Thuật toán tổng quát
Bộ truy lặp (iterator)
ƒ Mục ₫ích: Tạo một cơ chế thống nhất cho việc truy lặp phần tử
cho các cấu trúc dữ liệu mà không cần biết chi tiết thực thi bên
trong từng cấu trúc
ƒ Ý tưởng: Mỗi cấu trúc dữ liệu cung cấp một kiểu bộ truy lặp
riêng, có ₫ặc tính tương tự như một con trỏ (trong trường
hợp ₫ặc biệt có thể là một con trỏ thực)
ƒ Tổng quát hóa thuật toán copy:
template 
void copy(Iterator1 s, Iterator2 d, int n) {
while (n--) { 
*d = *s; 
++s; 
++d; 
}
}
Các phép toán áp dụng
₫ược tương tự con trỏ
20Chương 10: Thuật toán tổng quát
ƒ Tổng quát hóa thuật toán find_max:
template 
ITERATOR find_max(ITERATOR first, ITERATOR last) {
ITERATOR pMax = first;
while (first != last) {
if (*first > *pMax) pMax = first;
++first; 
}
return pMax;
}
Các phép toán áp dụng
₫ược tương tự con trỏ
21Chương 10: Thuật toán tổng quát
Bổ sung bộ truy lặp cho kiểu Vector
ƒ Kiểu Vector lưu trữ dữ liệu dưới dạng một mảng => có thể sử
dụng bộ truy lặp dưới dạng con trỏ!
template class Vector {
int nelem;
T* data;
public:
...
typedef T* Iterator;
Iteratator begin() { return data; }
Iteratator end() { return data + nElem; }
};
void main() {
Vector a(5,1.0),b(6);
copy(a.begin(),b.begin(),a.size());
...
}
22Chương 10: Thuật toán tổng quát
Bổ sung bộ truy lặp cho kiểu List
template class ListIterator {
ListItem *pItem;
ListIterator(ListItem* p = 0) : pItem(p) {}
friend class List;
public:
T& operator*() { return pItem->data; }
ListIterator& operator++() {
if (pItem != 0) pItem = pItem->getNext();
return *this;
}
friend bool operator!=(ListIterator a,
ListIterator b) {
return a.pItem != b.pItem;
}
};
23Chương 10: Thuật toán tổng quát
Khuôn mẫu List cải tiến
template class List {
ListItem *pHead;
public:
...
ListIterator begin() { 
return ListIterator(pHead);
}
ListIterator end() { 
return ListIterator(0);
}
};
24Chương 10: Thuật toán tổng quát
Bài tập về nhà
ƒ Xây dựng thuật toán sắp xếp tổng quát ₫ể có thể áp dụng cho
nhiều cấu trúc dữ liệu tập hợp khác nhau cũng như nhiều tiêu
chuẩn sắp xếp khác nhau. Viết chương trình minh họa.
ƒ Xây dựng thuật toán cộng/trừ/nhân/chia từng phần tử của hai
cấu trúc dữ liệu tập hợp bất kỳ. Viết chương trình minh họa.