C++ và Lập trình hướng đối tượng - Chương 10: Một số chương trình hướng đối tượng trên C++

{
cout << "\nHo ten: " ;
fflush(stdin);
gets(ht);
cout << "So bao danh: " ;
cin >> sobd;
cout << "Tong diem: " ;
cin >> td;
}
void xuat()
{
cout << "\nHo ten: " << ht;
cout << "\nSo bao danh: " << sobd;
cout << "\nTong diem: " << setiosflags(ios::showpoint)
<< setprecision(1)<<setw(5)<< td;
}
};
// Ham main
void main()
{
stack s1,s2; queue q1,q2;
TS ts1,ts2,ts;
int a=123,b;
float x=3.14,y;
char *str;
clrscr();
ts1.nhap();
ts2.nhap();
//Gui vao
s1.store(&ts1); q1.store(&ts1);
s1.store("HA NOI"); q1.store("HA NOI");
s1.store(&a); q1.store(&a);
s1.store(&ts2); q1.store(&ts2);
s1.store(&x); q1.store(&x);
//Lay ra tu ngan xep theo nguyen tac LIFO
cout <<"\n\nLay ra tu ngan xep:" ;
s2=s1;
y = *((float*)s2.retrieve());
cout << "\nSo thuc = " <<setiosflags(ios::showpoint)
<< setprecision(2)<< y;
ts = *((TS*)s2.retrieve());
ts.xuat();
b = *((int*)s2.retrieve());
cout << "\nSo nguyen = " << b;
str = (char*)s2.retrieve();
cout << "\nChuoi ky tu: " << str;
ts = *((TS*)s2.retrieve());
ts.xuat();
//Lay ra tu hang doi theo nguyen tac FIFO
cout <<"\n\nLay ra tu hang doi:" ;
q2=q1;
ts = *((TS*)q2.retrieve());
ts.xuat();
str = (char*)q2.retrieve();
cout << "\nChuoi ky tu: " << str;
536	537
b = *((int*)q2.retrieve());
cout << "\nSo nguyen = " << b;
ts = *((TS*)q2.retrieve());
ts.xuat();
y = *((float*)q2.retrieve());
cout << "\nSo thuc = " << setiosflags(ios::showpoint)
<< setprecision(2)<< y;
getch();
}
Đ 5. Các lớp sắp xếp
Trong tệp C_SORT.H dưới đây sẽ chứa 4 lớp sắp xếp: sort, select_sort, quick_sort và heap_sort. tổng quát hơn. So với các lớp sắp xếp trong mục Đ7 chương 6 thì các lớp ở đây tổng quát hơn ở chỗ: 
+ Các lớp trong mục Đ7 chương 6 chỉ cho phép sắp xếp một dẫy số nguyên theo thứ tự tăng dần.
+ Các lớp dưới đây cho phép sắp xếp một dẫy phần tử có kiểu bất kỳ (nguyên, thực, cấu trúc, lớp, ...) và theo một tiêu chuẩn sắp xếp bất kỳ.
1. Lớp sort là lớp cơ sở trừu tượng
 + Các thuộc tính:
protected:
void *a ; // Trỏ tới vùng nhớ chứa dẫy 
// phần tử cần sắp xếp
int size ; // Độ lớn tính theo byte của phần tử 
int (*nho_hon)(void* pt1, void* pt2); // Con trỏ hàm
// định nghĩa pt1 nhỏ hơn pt2
+ Các phương thức:
protected:
void hoan_vi(int i, int j) ; // Hoán vị các phần tử thứ i và j
void * dia_chi (int m); // Cho địa chỉ của phần tử thứ m
public:
virtual void sapxep(void *a1,int n,int itemsize,
int (*ss_nho_hon)(void* ,void* )) ; // Sắp xếp dẫy
// n phần tử chứa trong vùng nhớ a1, mỗi phần tử
// có độ dài itemsize, thứ tự tăng được quy định
// bởi hàm ss_nho_hon
2. Lớp select_sort dẫn xuất từ lớp sort. Lớp này sẽ thực hiện việc sắp xếp theo phương pháp chon (xem mục Đ7 chương 6).
 + Các phương thức:
public:
virtual void sapxep(void *a1,int n,int itemsize,
int (*ss_nho_hon)(void* ,void* )) ; // thực hiện
// sắp xếp theo phương pháp chọn
3. Lớp quick_sort dẫn xuất từ lớp sort. Lớp này sẽ thực hiện việc sắp xếp theo phương pháp quick sort (xem mục Đ7 chương 6)
 + Các phương thức:
private:
void q_sort(int l, int r);
public:
virtual void sapxep(void *a1,int n,int itemsize,
int (*ss_nho_hon)(void* ,void* )) ; // thực hiện
538	539
// sắp xếp theo phương pháp quick sort
4. Lớp heap_sort dẫn xuất từ lớp sort. Lớp này sẽ thực hiện việc sắp xếp theo phương pháp heap sort (xem mục Đ7 chương 6).
 + Các phương thức:
private:
void shift(int i, int n);
public:
virtual void sapxep(void *a1,int n,int itemsize,
int (*ss_nho_hon)(void* ,void* )) ; // thực hiện
// sắp xếp theo phương pháp heap sort
Dưới đây là nội dung tệp C_SORT.H
//C_SORT.H
// Lop co so truu tuong
// Lop sort
#include 
#include 
#include 
#include 
#include 
#include 
class sort
{
protected:
void *a;
int size;
int (*nho_hon)(void*,void*);
void* dia_chi(int m)
{
return (void*) ((char*)a + size*(m-1));
}
void hoan_vi(int i, int j)
{
void *tg, *di, *dj;
di= dia_chi(i);
dj= dia_chi(j);
tg = new char[size];
memcpy(tg,di,size);
memcpy(di,dj,size);
memcpy(dj,tg,size);
}
public:
virtual void sapxep(void *a1,int n,int itemsize,
int (*ss_nho_hon)(void*,void*))
{
a=a1;
size=n; // Cho C++ hai long
size=itemsize;
nho_hon= ss_nho_hon;
}
} ;
class select_sort : public sort
{
public:
virtual void sapxep(void *a1,int n,int itemsize,
int (*ss_nho_hon)(void*,void*)) ;
} ;
void select_sort::sapxep(void *a1,int n,int itemsize,
int (*ss_nho_hon)(void*,void*))
{
540	541
int i,j,r;
sort::sapxep(a1,n,itemsize,ss_nho_hon);
for(i=1; i<n; ++i)
{
r=i;
for(j=i+1; j<=n; ++j)
if(nho_hon(dia_chi(j),dia_chi(r))) r = j;
if(r!=i) hoan_vi(i,r);
}
}
class quick_sort : public sort
{
private:
void q_sort(int l, int r);
public:
virtual void sapxep(void *a1,int n,int itemsize,
int (*ss_nho_hon)(void*,void*)) ;
} ;
void quick_sort::q_sort(int l, int r)
{
void *x;
int i,j;
x = new char[size];
if(l < r)
{
memcpy(x, dia_chi(l), size);
i = l; j = r+1;
do
{
++i; --j;
while(i<r && nho_hon(dia_chi(i),x)) ++i ;
while(nho_hon(x,dia_chi(j)) ) --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(void *a1,int n,int itemsize,
int (*ss_nho_hon)(void*,void*))
{
sort::sapxep(a1,n,itemsize,ss_nho_hon);
q_sort(1,n);
}
class heap_sort : public sort
{
private:
void shift(int i, int n);
public:
virtual void sapxep(void *a1,int n,int itemsize,
int (*ss_nho_hon)(void*,void*));
} ;
void heap_sort::shift(int i, int n)
{
int l,r,k;
l = 2*i; r = l+1;
542	543
if(l>n) return;
if(l==n)
{
if (nho_hon(dia_chi(i), dia_chi(l)))
hoan_vi(i,l);
return;
}
if(nho_hon(dia_chi(r), dia_chi(l)))
k = l;
else
k = r;
if (!nho_hon(dia_chi(i), dia_chi(k)))
return;
else
{
hoan_vi(i,k);
shift(k,n);
}
}
void heap_sort::sapxep(void *a1,int n,int itemsize,
int (*ss_nho_hon)(void*,void*))
{
long i;
sort::sapxep(a1,n,itemsize,ss_nho_hon);
// Tao dong 
for(i=n/2 ; i>=1; --i) shift(i,n);
// Lap 
for(i=n ; i>=2; --i)
{
hoan_vi(1,i);
shift(1,i-1);
}
}
Đ 6. Ví dụ về Các lớp sắp xếp
Trong mục này trình bầy 2 chương trình minh hoạ cách dùng các lớp nói trên. Chương trình thứ nhất minh hoạ cách sử dụng các lớp trong tệp C_SORT.H để sắp xếp một dẫy thí sinh theo thứ tự giảm và thứ tự tăng của tổng điểm. Chương trình thứ hai minh hoạ cách dùng các lớp trong C_SORT.H để sắp xếp một dẫy số nguyên theo chiều tăng và chiều giảm.
Chương trình 1
//CT10-08
// Lop co so truu tuong
// Lop sort
#include "c_sort.h"
class TS
{
private:
char ht[25];
int sobd;
float td;
public:
float get_td()
{
return td;
}
void nhap()
{
cout << "\nHo ten: " ;
fflush(stdin);
gets(ht);
544	545
cout << "So bao danh: " ;
cin >> sobd;
cout << "Tong diem: " ;
cin >> td;
}
void xuat()
{
cout << "\nHo ten: " << ht;
cout << "\nSo bao danh: " << sobd;
cout << "\nTong diem: " << setiosflags(ios::showpoint)
<< setprecision(1)<<setw(5)<< td;
}
};
int ss_tong_diem_giam(void *ts1, void *ts2)
{
return ( ((TS*)ts1)->get_td() > ((TS*)ts2)->get_td()) ;
}
int ss_tong_diem_tang(void *ts1, void *ts2)
{
return ( ((TS*)ts1)->get_td() get_td()) ;
}
void main()
{
TS t[100];
sort *sa;
int n,i;
clrscr();
cout << "\nSo thi sinh: ";
cin >> n;
for(i=1; i<=n; ++i) t[i].nhap();
for(i=1; i<=n; ++i) t[i].xuat();
getch();
cout << "\n\nSap xep giam theo tong diem - PP Select Sort" ;
sa= new select_sort;
sa->sapxep( t+1,n,sizeof(TS),ss_tong_diem_giam);
for(i=1; i<=n; ++i) t[i].xuat();
delete sa;
getch();
cout << "\n\nSap xep tang theo tong diem - PP Select Sort";
sa= new select_sort;
sa->sapxep( t+1,n,sizeof(TS),ss_tong_diem_tang);
for(i=1; i<=n; ++i) t[i].xuat();
delete sa;
getch();
cout << "\n\nSap xep giam theo tong diem - PP Quick Sort" ;
sa= new quick_sort;
sa->sapxep( t+1,n,sizeof(TS),ss_tong_diem_giam);
for(i=1; i<=n; ++i) t[i].xuat();
delete sa;
getch();
cout << "\n\nSap xep tang theo tong diem - PP Quick Sort" ;
sa= new quick_sort;
sa->sapxep( t+1,n,sizeof(TS),ss_tong_diem_tang);
for(i=1; i<=n; ++i) t[i].xuat();
delete sa;
getch();
cout << "\n\nSap xep giam theo tong diem - PP Heap Sort" ;
546	547
sa= new heap_sort;
sa->sapxep( t+1,n,sizeof(TS),ss_tong_diem_giam);
for(i=1; i<=n; ++i) t[i].xuat();
delete sa;
getch();
cout << "\n\nSap xep tang theo tong diem - PP Heap Sort" ;
sa= new heap_sort;
sa->sapxep( t+1,n,sizeof(TS),ss_tong_diem_tang);
for(i=1; i<=n; ++i) t[i].xuat();
delete sa;
getch();
}
Chương trình 2
//CT10-09
// Lop co so truu tuong
// Lop sort
#include "c_sort.h"
int ss_tang(void *i1,void *i2)
{
return *((int*)i1) < *((int*)i2);
}
int ss_giam(void *i1,void *i2)
{
return *((int*)i1) > *((int*)i2);
}
void main()
{
int i,n;
struct time t1,t2;
int b[20],a[20], k, tg, sec, hund;
n=10;
sort *s[3];
select_sort ss;
quick_sort qs;
heap_sort hs;
s[0]=&ss; s[1]=&qs; s[2]=&hs;
clrscr();
srand(5000);
for(i=1;i<=n;++i)
b[i]=rand();
cout<<"\nDay ban dau\n ";
for(i=1;i<=n;++i) cout <<b[i]<<" ";
cout<<"\n\nCac day tang sap xep theo ";
cout << "select_sort, quick_sort, heap_sort\n";
for(k=0; k<3; ++k)
{
for(i=1;i<=n;++i)
a[i]=b[i];
s[k]->sapxep (a+1,n,sizeof(int),ss_tang);
//In
for(i=1;i<=n;++i) cout <<a[i]<<" ";
cout<<"\n";
}
cout<<"\n\nCac day giam sap xep theo ";
cout << "select_sort, quick_sort, heap_sort\n";
for(k=0; k<3; ++k)
{
for(i=1;i<=n;++i)
548	549
a[i]=b[i];
s[k]->sapxep (a+1,n,sizeof(int),ss_giam);
//In
for(i=1;i<=n;++i) cout <<a[i]<<" ";
cout << "\n";
}
getch();
}