C++ và Lập trình hướng đối tượng - Chương 6: Tương ứng bội và phương thức ảo

VAT::xuat(int n)
{
if (n max_so_con_vat)
return NULL ;
--n ;
if (h[n])
{
CON_VAT *c = h[n];
h[n]=NULL;
so_con_vat-- ;
return c;
}
else
return NULL;
}
void DS_CON_VAT::thong_ke()
{
if (so_con_vat)
{
cout << "\n" ;
for (int i=0; i<max_so_con_vat; ++i)
if (h[i])
h[i]->xung_ten();
}
}
CON_CHO c1("MUC");
CON_CHO c2("VEN");
CON_CHO c3("LAI");
CON_CHO c4("NHAT");
CON_CHO c5("BONG");
CON_MEO m1("MUOP");
CON_MEO m2("DEN");
CON_MEO m3("TRANG");
CON_MEO m4("TAM THE");
CON_MEO m5("VANG");
void main()
{
DS_CON_VAT d(20);
clrscr();
d.nhap(&c1);
int im2 = d.nhap(&m2);
349	350	
d.nhap(&c3);
d.nhap(&m1);
int ic4 = d.nhap(&c4);
d.nhap(&c5);
d.nhap(&m5);
d.nhap(&c2);
d.nhap(&m3);
d.thong_ke();
d.xuat(im2);
d.xuat(ic4);
d.thong_ke();
getch();
}
Chỳ ý: Theo quan điểm chung về cỏch thức sử dụng, thỡ lớp CON_VAT là lớp cơ sở trừu tượng. Tuy nhiờn theo quan điểm của C++ thỡ lớp này chưa phải là lớp cơ sở trừu tượng, vỡ trong lớp khụng cú cỏc phương thức thuần tuý ảo. Phương thức xung_ten: 
virtual void xung_ten()
{
}
là phương thức ảo, được định nghĩa đầy đủ , mặc dự thõn của nú là rỗng. 
Do vậy khai bỏo:
CON_VAT cv(“Con vat chung”);
vẫn được C++ chấp nhận.
Bõy giờ nếu định nghĩa lại phương thức xung_ten như sau: 
virtual void xung_ten() = 0 ;
thỡ nú trở thành phương thức thuần ảo và C++ sẽ quan niệm lớp CON_VAT là lớp trừu tượng. Khi đú cõu lệnh khai bỏo:
CON_VAT cv(“Con vat chung”);
sẽ bị C++ bắt lỗi với thụng bỏo:
Cannot create instance of abstruct class ‘CON_VAT’
Đ 6. Sử dụng tương ứng bội và phương thức ảo
6.1. Chiến lược sử dụng tương ứng bội
Tương ứng bội cho phộp xột cỏc vấn đề khỏc nhau, cỏc đối tượng khỏc nhau, cỏc phương phỏp khỏc nhau, cỏc cỏch giải quyết khỏc nhau theo cựng một lược đồ chung. 
Cỏc bước ỏp dụng tương ứng bội cú thể tổng kết lại như sau:
1. Xõy dựng lớp cơ sở trừu tượng bao gồm những thuộc tớnh chung nhất của cỏc thực thể cần quản lý. Đưa vào cỏc phương thức ảo hay thuần ảo dựng để xõy dựng cỏc nhúm phương thức ảo cho cỏc lớp dẫn xuất sau này. Mỗi nhúm phương thức ảo sẽ thực hiện một chức năng nào đú trờn cỏc lớp.
2. Xõy dựng cỏc lớp dẫn xuất bắt đầu từ lớp cơ sở ảo. Số mức dẫn xuất là khụng hạn chế. Cỏc lớp dẫn xuất sẽ mụ tả cỏc đối tượng cụ thể cần quản lý.
3. Xõy dựng cỏc phương thức ảo trong cỏc dẫn xuất. Cỏc phương thức này tạo thành cỏc nhúm phương thức ảo trong sơ đồ cỏc lớp cú quan hệ thừa kế.
4. Xõy dựng lớp quản lý cỏc đối tượng. Dữ liệu của lớp này là một dẫy con trỏ của lớp cơ sở trừu tượng ban đầu. Cỏc con trỏ này cú thể chứa địa chỉ đối tượng của cỏc lớp dẫn xuất. Do vậy cú thể dựng cỏc con trỏ này để thực hiện cỏc thao tỏc trờn cỏc đối tượng của bất kỳ lớp dẫn xuất nào.
6.2. Vớ dụ
Chương trỡnh quản lý cỏc con vật trong Đ5 là một vớ dụ về cỏch sử dụng tương ứng bội. Dưới đõy là một vớ dụ khỏc. Giả sử cú 4 hỡnh vẽ: Đoạn thẳng, hỡnh trũn, hỡnh chữ nhật và hỡnh vuụng. Bốn hỡnh cho hiện thẳng hàng trờn màn hỡnh tạo thành một bức tranh. Nếu thay đổi thứ tự cỏc hỡnh sẽ nhận được cỏc bức tranh khỏc nhau. Chương trỡnh dưới đõy sẽ cho hiện tất cả cỏc bức tranh khỏc nhau. Chương trỡnh được tổ chức theo cỏc bước nờu trong 6.1:
351	352	
+ Lớp cơ sở trừu tượng là lớp HINH (hỡnh) gồm một thuộc tớnh mau (mầu) và một phương thức ảo thuần tuý:
virtual void draw(int x, int y) = 0 ;
+ Cỏc lớp dẫn xuất trực tiếp từ lớp hỡnh là : DTHANG , HTRON và CHUNHAT.
+ Lớp VUONG dẫn xuất từ lớp CHUNHAT.
+ Lớp quản lý chung là lớp picture cú thuộc tớnh là một mảng con trỏ kiểu HINH gồm 4 phần tử dựng để chứa địa chỉ 4 đối tượng: DTHANG, HTRON, CHUNHAT và VUONG. Sử dụng phương thức draw gọi từ 4 phần tử mảng núi trờn sẽ nhận được một bức tranh. Bằng cỏch hoỏn vị cỏc phần tử này, sẽ nhận được tất cả cỏc bức tranh khỏc nhau.
//CT6-05
// Lop co so truu tuong
// Lop hinh hoc
#include 
#include 
class HINH
{
private:
int mau;
public:
HINH(int m)
{
mau = m;
}
getmau()
{
return mau;
}
virtual void draw(int x, int y) = 0;
};
class DTHANG : public HINH
{
private:
int dodai;
public:
DTHANG(int d, int m):HINH(m)
{
dodai = d ;
}
virtual void draw(int x, int y)
{
setcolor(getmau()) ;
line(x,y,x+dodai,y);
}
};
class CHUNHAT: public HINH
{
private:
int rong, cao;
public:
CHUNHAT(int r, int c, int m):HINH(m)
{
rong = r; cao = c;
}
virtual void draw(int x, int y )
{
setcolor(getmau()) ;
rectangle(x,y,x+rong,y+cao);
setfillstyle(1,getmau());
353	354	
floodfill(x+rong/2,y+cao/2, getmau() );
}
};
class VUONG : public CHUNHAT
{
public:
VUONG(int a, int m): CHUNHAT(a,a,m)
{
}
};
class HTRON: public HINH
{
private:
int bk; //Ban kinh
public:
HTRON(int bk1, int m):HINH(m)
{
bk = bk1;
}
virtual void draw(int x, int y)
{
setcolor(getmau()) ;
circle(x+bk,y+bk,bk);
setfillstyle(1,getmau());
floodfill(x + bk, y + bk,getmau());
}
};
class picture
{
private:
HINH *h[4];
public:
picture(HINH *h0,HINH *h1,HINH *h2,HINH *h3)
{
h[0]=h0;
h[1]=h1;
h[2]=h2;
h[3]=h3;
}
void paint(int *k);
void listpaint();
} ;
void picture::paint(int *k)
{
for (int i=0; i<4; ++i)
h[k[i]]->draw(10+i*150, 200);
}
void picture::listpaint()
{
int k[4],i1,i2,i3,i4;
for (i1=0;i1<4;++i1)
for (i2=0;i2<4;++i2)
if (i2!=i1)
for (i3=0;i3<4;++i3)
if (i3!=i2 && i3!=i1)
for (i4=0;i4<4;++i4)
if (i4!=i3 && i4!=i2 && i4!=i1)
{
k[0]=i1;k[1]=i2;
355	356	
k[2]=i3;k[3]=i4;
paint(k);
getch();
cleardevice();
}
}
DTHANG dt(120,14);
HTRON ht(60,RED);
CHUNHAT cn(120,100,MAGENTA);
VUONG v(120,CYAN);
} ;
void main()
{
int mh=0,mode=0;
initgraph(&mh,&mode,"");
picture pic(&dt,&ht,&cn,&v);
pic.listpaint();
getch();
closegraph();
}
Đ 7. Xử lý cỏc thuật toỏn khỏc nhau
Cú thể sử dụng tương ứng bội để tổ chức thực hiện cỏc thuật toỏn khỏc nhau trờn cựng một bài toỏn như sau:
+ Lớp cơ sở trừu tượng sẽ chứa dữ liệu bài toỏn và một phương thức ảo.
+ Mỗi lớp dẫn xuất ứng với một thuật toỏn cụ thể. Phương thức ảo của lớp dẫn xuất sẽ thực hiện một thuật toỏn cụ thể. 
+ Sử dụng một mảng con trỏ của lớp cơ sở và gỏn cho mỗi phần tử mảng địa chỉ của một đối tượng của lớp dẫn xuất. Sau đú dựng cỏc phần tử mảng con trỏ để gọi tới cỏc phương thức ảo. Bằng cỏch đú sẽ thực hiện cựng một bài toỏn theo cỏc thuật toỏn khỏc nhau và dễ dàng so sỏnh hiờụ quả của cỏc thuật toỏn.
Vớ dụ sau minh hoạ việc thực hiện bài toỏn sắp xếp dẫy số nguyờn theo thứ tự tăng bằng cỏch dựng đồng thời 3 thuật toỏn: Thuật toỏn lựa chọn (Select_Sort), thuật toỏn sắp xếp nhanh (Quick_Sort) và thuật toỏn vun đống (Heap_Sort). Chương trỡnh gồm 4 lớp:
+ Lớp cơ sở trừu tượng:
class sort
{
protected:
int *a;
void hoan_vi(long i, long j) ;	 
public:
virtual void sapxep(int *a1, long n) ;
} ;
Lớp này gồm:
- Một thành phần dữ liệu là con trỏ a trỏ tới một vựng nhớ chứa dẫy số nguyờn cần sắp xếp.
- Phương thức hoan_vi(i,j) dựng để hoỏn vị cỏc phần tử a[i] và a[j]. Phương thức này được dựng trong 3 lớp dẫn xuất bờn dưới.
- Phương thức ảo sapxep(a1,n) dựng để sắp xếp dẫy n số nguyờn chứa trong mảng a1.
+ Ba lớp dẫn xuất là: SELECT_SORT, QUICK_SORT và HEAP_SORT. Mỗi lớp đều cú phương thức ảo:
virtual void sapxep(int *a1, long n) ;
để thực hiện hiện việc sắp xếp theo theo một thuật toỏn cụ thể.
+ Trong hàm main() sẽ tạo ra một dẫy 30000 số nguyờn một cỏch ngẫu nhiờn, sau đú lần lượt sử dụng 3 thuật toỏn sắp xếp để so sỏnh. Kết quả như sau:
357	358	
Thời gian sắp xếp theo thuật toỏn Select sort là: 19.20 giõy
Thời gian sắp xếp theo thuật toỏn Quick sort là: 0.11 giõy
Thời gian sắp xếp theo thuật toỏn Heap sort là: 0.44 giõy
Nội dung chương trỡnh như sau:
//CT6-06
// Lop co so truu tuong
// Lop sort
#include 
#include 
#include 
#include 
#include 
#include 
class sort
{
protected:
int *a;
void hoan_vi(long i, long j)
{
int tg = a[i];
a[i] = a[j];
a[j] = tg;
}
public:
virtual void sapxep(int *a1, long n)
{
a = a1;
}
} ;
class select_sort : public sort
{
public:
virtual void sapxep(int *a1, long n) ;
} ;
void select_sort::sapxep(int *a1, long n)
{
long i,j,r;
sort::sapxep(a1,n);
for (i=1; i<n; ++i)
{
r=i;
for (j=i+1; j<=n; ++j)
if(a[j] < a[r]) r = j;
if(r!=i) hoan_vi(i,r);
}
}
class quick_sort : public sort
{
private:
void q_sort(long l, long r);
public:
virtual void sapxep(int *a1, long n) ;
} ;
void quick_sort::q_sort(long l, long r)
{
int x;
long i,j;
if (l < r)
359	360	
{
x = a[l]; i = l; j = r+1;
do
{
++i; --j;
while (i<r && a[i] < x) ++i ;
while (a[j] > x) --j ;
if (i<j) hoan_vi(i,j);
} while (i<j);
hoan_vi(l,j);
q_sort(l,j-1);
q_sort(j+1,r);
}
}
void quick_sort::sapxep(int *a1, long n)
{
sort::sapxep(a1,n);
q_sort(1,n);
}
class heap_sort : public sort
{
private:
void shift(long i, long n);
public:
virtual void sapxep(int *a1, long n) ;
} ;
void heap_sort::shift(long i, long n)
{
long l,r,k;
l = 2*i; r = l+1;
if (l>n) return;
if (l==n)
{
if (a[i]<a[l]) hoan_vi(i,l);
return;
}
if (a[l] > a[r])
k = l;
else
k = r;
if (a[i]>=a[k])
return;
else
{
hoan_vi(i,k);
shift(k,n);
}
}
void heap_sort::sapxep(int *a1, long n)
{
long i;
sort::sapxep(a1,n);
/* Tao dong */
for (i=n/2 ; i>=1; --i) shift(i,n);
/* Lap */
for (i=n ; i>=2; --i)
{
hoan_vi(1,i);
361	362	
shift(1,i-1);
}
}
void main()
{
long i,n;
struct time t1,t2;
int *a, k, tg, sec, hund;
n=30000;
a=(int*) malloc((n+1)*sizeof(int));
if (a==NULL)
{
puts("\nLoi BN"); 
getch(); 
exit(0);
}
sort *s[3];
select_sort ss;
quick_sort qs;
heap_sort hs;
s[0]=&ss; s[1]=&qs; s[2]=&hs;
clrscr();
for (k=0; k<3; ++k)
{
srand(5000);
for (i=1;i<=n;++i)
a[i]=rand();
gettime(&t1);
s[k]->sapxep(a,n);
gettime(&t2);
tg = (t2.ti_sec - t1.ti_sec)*100 + t2.ti_hund - t1.ti_hund ;
sec = tg / 100;
hund = tg % 100;
printf("\n Sap xep %d %d %d %d %d",k+1,
t2.ti_sec,t2.ti_hund,t1.ti_sec,t1.ti_hund);
printf("\n Sap xep %d Thoi gian %d sec %d hund", 
k+1,sec,hund);
}
getch();
}
363