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

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

1. Chương 10 void pop(); // Tháo gỡ cửa sổ và khôi phục màn hình Một số chương trình hướng đối tượng trên C++ int get_ra_mh(); Chương này trình bầy thêm một số chương trình hướng đối + Lớp stack (dùng để quản lý một dẫy cửa sổ) tượng trên C++. Đây là các chương trình tương đối phức tạp, hữu ích và sử dụng các công cụ mạnh của C++ như: Cách Thuộc tính gồm: truy nhập trực tiếp bộ nhớ màn hình, kỹ thuật đồ hoạ, con trỏ int max; //Số cửa sổ cực đại có thể quản lý void, tính kế thừa, lớp cơ sở trừu tượng, tương ứng bội, int num; //Số cửa sổ hiện có trong stack phương thức ảo. cua_so pcs; //Con trỏ trỏ đến vùng nhớ chứa § 1. Lớp cửa sổ //địa chỉ của các đối tượng cua_so Chương trình gồm lớp cua_so và lớp stack Phương thức gồm: + Lớp cửa sổ stack(); stack(int max_cs); Thuộc tính gồm: int accept(cua_so *cs,int x,int y); //Đưa một cửa sổ char *noidung; // Trỏ đến vùng nhớ chứa nội dung //vào stack, nó sẽ hiện lên màn // soạn thảo trên cửa sổ hình int cao,rong ; // Chiều cao và chiều rộng cửa sổ void del(); // Loại cửa sổ khỏi stack, nó sẽ bị xoá int mau; // mau = 16*mau_nen + mau_chu // khỏi màn hình int ra_mh; // Cho biết cửa sổ đã được đưa ra màn hình chưa? Nội dung chương trình: int posx,posy; // Vị trí trên trái của cửa sổ trên màn hình + Đầu tiên hiện cửa sổ thứ nhất nền GREEN chữa WHITE. word *pluu; // Trỏ đến vùng nhớ chứa nội dung Có thể soạn thảo trên đó. // phần màn hình bị cửa sổ đè lên + Nếu bấm ESC kết thúc chương trình, nếu bấm F6 thì hiện thêm cửa sổ thứ hai nền CYAN chữ MAGENTA. Có thể soạn Phương thức gồm: thảo trên đó. cua_so(); + Nếu bấm ESC kết thúc chương trình, nếu bấm F6 thì hiện cua_so(int c,int r,byte mau_nen, byte mau_chu); thêm cửa sổ thứ ba nền RED chữ YELLOW. Có thể soạn thảo trên đó. int push(int x,int y); // Đưa cửa sổ ra màn hình tại (x,y) + Đang ở một cửa sổ, nếu bấm ESC thì kết thúc chương // cho phép soạn thảo trên cửa sổ trình, nếu bấm F6 thì hiện cửa sổ tiếp theo (theo thứ tự vòng // Bấm F6 chuyển sang cửa sổ khác quanh: 1 -> 2 -> 3 -> 1). // Bấm ESC kết thúc 504 505
2. Chương trình sử dụng phương pháp truy nhập trực tiếp bộ private: nhớ màn hình trình bầy trong chương 9. char *noidung; // CT10_01.CPP int cao, rong; // lop cua_so int mau; // mau = 16*mau_nen + mau_chu #include int ra_mh; #include int posx,posy; #include 506 word *pluu; 507 #include public: typedef unsigned int word; cua_so(); typedef unsigned char byte; cua_so(int c,int r,byte mau_nen, byte mau_chu); struct kt_word int push(int x,int y); { void pop(); word kt; int get_ra_mh(); }; }; struct kt_byte { cua_so::cua_so() byte ma, mau; { }; cao=rong=mau=ra_mh=posx=posy=0; union ky_tu noidung=NULL; pluu=NULL; { } struct kt_byte h; cua_so::cua_so(int c,int r,byte mau_nen, byte mau_chu) struct kt_word x; { }; cao=c; rong=r; typedef union ky_tu far *VP; mau= 16*mau_nen+mau_chu; VP vptr=(VP)MK_FP(0xb800,0); ra_mh=posx=posy=0; // Vi tri x,y tren man hinh noidung = (char*)malloc(cao*rong); #define VPOS(x,y) (VP)(vptr + ((y)-1)*80+(x)-1) for (int i=0;i<cao*rong;++i) class cua_so noidung[i]=32; { pluu= (word*)malloc(2*cao*rong);
3. } if ((ch1=getch())==0) ch2=getch(); int cua_so::push(int x,int y) if (ch1==27)break; // ESC Ket Thuc Soan Thao { else if (ch1==0&&ch2==64)break; //F6 word *p= pluu; char *pnd=noidung; else if (ch1==13) VP ptr; { int i,j; ++yy; xx=posx; if(yy>=posy+cao) break; // Luu man hinh } if (ra_mh==0) else if (ch1!=0) { 508 { 509 ra_mh=1; posx=x;posy=y; ptr=VPOS(xx,yy); for (i=posx;i h.ma=ch1; for (j=posy;j =posx+rong) {++yy; xx=posx;} ptr=VPOS(i,j); *p=ptr->x.kt; ++p; if (yy>=posy+cao) break; } } } else if (ch2==72||ch2==80||ch2==75||ch2==77) // Hien noi dung dang soan thao tren cua so { for (i=posx;i h.mau=mau; if (xx h.ma=*pnd; ++pnd; if (xx>=posx+rong) {++yy; xx=posx;} } if (yy =posy+cao) break; int xx=posx,yy=posy,ch1,ch2; } while (1) } { // Luu ket qua soan thao gotoxy(xx,yy); pnd=noidung;
4. for (i=posx;i h.ma; ++pnd; stack(); } if (ch1==0&&ch2==64) return 0; //F6 stack(int max_cs); else return 1; int accept(cua_so *cs,int x,int y); } void del(); void cua_so::pop() // Khoi phuc vung nho bi cua so chiem }; stack::stack() { 510 511 if (ra_mh==0) return; { ra_mh=0; max=num=0; pcs=NULL; word *p=pluu; } VP ptr; stack::stack(int max_cs) int i,j; { for (i=posx;i x.kt=*p; ++p; } } int stack::accept(cua_so *cs,int x,int y) } { int cua_so::get_ra_mh() int gt; { if (num==max)return 0; return ra_mh; if (!cs->get_ra_mh()) } { //class stack pcs[num]=cs; ++num; class stack } {
5. gt=cs->push(x,y); s.del(); s.del(); s.del(); return gt; } } void stack::del() § 2. Lớp menu { Lớp cmenu có 2 phương thức để tạo lập và sử dụng menu: if (num==0) return; 1. Hàm tạo num; cmenu(int so_cn_menu,char nd_menu); pcs[num]->pop(); dùng để tạo một menu (đối tượng kiểu cmenu). Hàm tạo chứa pcs[num]=NULL; 2 đối là: } + Biến so_cn_menu chứa số chức năng của menu main() + Con trỏ nd_menu trỏ tới một vùng nhớ chứa địa chỉ các chuỗi ký tự dùng làm tiêu đề menu và tiêu đề các chức năng { 512menu. 513 int ch; Ví dụ các câu lệnh: cua_so w1(10,40,GREEN,WHITE), char *nd[]={"Quản lý vật tư", "Nhập số liệu", w2(12,42,CYAN,MAGENTA), "Tìm kiếm","Kết thúc"}; w3(14,44,RED,YELLOW); cmenu mc(3,nd); stack s(4); sẽ tạo một menu mc gồm 3 chức năng: Nhập số liệu, Tìm clrscr(); kiếm và Kết thúc. Menu có tiêu đề là: Quản lý vật tư while(1) 2. Phương thức { int menu(int x,int y,int mau_nen,int mau_chon); ch=s.accept(&w1,5,5); thực hiện các việc sau: if(ch==1)break; + Hiển thị menu tại vị trí (x,y) trên màn hình. Menu có mầu ch=s.accept(&w2,8,8); nền xác định bởi đối mau_nen và mầu chức năng định chọn if(ch==1)break; (hộp sáng) xác định bởi đối mau_chon. ch=s.accept(&w3,11,11); + Cho phép sử dụng các phím mũi tên lên, xuống để di if(ch==1)break; chuyển hộp sáng và dùng phím Enter để thoát khỏi phương thức. }
6. + Sau khi thoát khỏi, phương thức trả về giá trị bằng số thứ }; tự (tính từ 1) của chức năng được chọn. typedef union ky_tu far *VP; Chương trình dưới đây xây dựng lớp cmenu và minh hoạ VP vptr=(VP)MK_FP(0xb800,0); cách sử dụng lớp này. // Vi tri x,y tren man hinh /* CT10_02.CPP #define VPOS(x,y) (VP)(vptr + ((y)-1)*80+(x)-1) menu.cpp class cmenu lop cmenu { */ private: #include int so_cn,cao,rong,posx,posy; #include int chon; #include char nd; #include private: #include void hiendc(char *dc,int x,int y, int mau); typedef unsigned int word; void hien_menu(int x,int y,int mau_nen,int typedef unsigned char byte; mau_chon); struct kt_word 514 public: 515 { cmenu(int so_cn_menu,char nd_menu); word kt; int menu(int x,int y,int mau_nen,int mau_chon); }; }; struct kt_byte cmenu::cmenu(int so_cn_menu,char nd_menu) { { byte ma, mau; cao=so_cn=so_cn_menu; nd=nd_menu; }; rong=0; union ky_tu chon=1; { int d; for(int i=0;i rong) rong=d; struct kt_word x; }
7. void cmenu::hiendc(char *dc,int x,int y, int mau) //Bat phim { while(1) VP ptr; int i; { byte m=16*mau+15; //chu trang if( (ch1=getch())==0 ) ch2=getch(); for(i=0;i h.mau=m ; { ptr->h.ma=32; //Di chuyen hop sang } chonluu=chon; for(i=0;i h.ma=dc[i]; else if(chon>cao) chon=1; } if(chon!=chonluu) } { void cmenu::hien_menu(int x,int y,int mau_nen,int hiendc(nd[chonluu],x,y+chonluu,mau_nen); mau_chon) hiendc(nd[chon],x,y+chon,mau_chon); { } 516 517 for(int i=0;i<=so_cn;++i) } hiendc(nd[i],x,y+i,mau_nen); } hiendc(nd[chon],x,y+chon,mau_chon); } char *nd[]={"TINH DIEN TICH", "Tam giac","Hinh tron", } "Chu nhat", "Hinh vuong", "Ket thuc chuong int cmenu::menu(int x,int y,int mau_nen,int mau_chon) trinh"}; { void main() int ch1,ch2,chonluu; { //Trinh bay cmenu mc(5,nd); int chon; hien_menu(x,y,mau_nen,mau_chon); clrscr();
8. while(1) } { } chon=mc.menu(5,5,BLUE,MAGENTA); if(chon==1) § 3. Lớp hình học { Chương trình dưới đây gồm: clrscr(); + Lớp “hinh” là lớp cơ sở trừu tượng puts("TAM GIAC"); getch(); clrscr(); + Và 3 lớp dẫn suất từ lớp “hình” là: } - Lớp “khoihop” biểu thị các khối hộp lập phương else if(chon==2) - Lớp “duong” biểu thị các đoạn thẳng qua 2 điểm { - Lớp “tron” biểu thị các đường tròn clrscr(); Chương trình minh hoạ cách dùng tượng ứng bội và puts("HINH TRON"); phương thức ảo. Nội dung chương trình như sau: getch();clrscr(); + Khi chạy chương trình sẽ thấy xuất hiện một khối hộp lập } phương. else if(chon==3) + Có thể di chuyển khối hộp bằng các phím mũi tên. { + Bấm phím Q sẽ xuất hiện một đoạn thẳng. clrscr(); + Có thể di chuyển đoạn thẳng bằng các phím mũi tên. puts("CHU NHAT"); + Bấm phím Q sẽ xuất hiện một đường tròn. getch();clrscr(); + Có thể di chuyển đường tròn bằng các phím mũi tên. } + Bấm phím Q sẽ kết thúc chương trình. else if(chon==4) /* { 518 CT10_03.CPP 519 clrscr(); LOP hinh hoc puts("HINH VUONG"); Minh hoa cach dung: getch(); clrscr(); + lop co so truu tuong } + Tuong ung boi va phuong thuc ao else break; */
9. #include x=y=a=0; #include } #include khoihop(int m,int x1,int y1, int a1):hinh(m) #include { char getkey(int &dx,int &dy); x=x1; class hinh y=y1; { a=a1; protected: } int mau; virtual void dchuyen(int b); public: void hien(void) hinh(void) { { setfillstyle(1,mau); mau=0; bar3d(x,y,x+a,y+a,a/2,1); } } hinh(int m) { void an(void) mau=m; { } setfillstyle(1,getbkcolor()); virtual void dchuyen(int b)=0; bar(x,y-a/2,x+a+a/2,y+a+a/2); }; } class khoihop : public hinh }; { class duong:public hinh private: { int x,y; private: 520 521 int a ; int x1,y1,x2,y2; public: public: khoihop(void):hinh() duong(void):hinh() { {
10. x1=x2=y1=y1=0; { } x=a; y=b; r=d; duong(int m,int a,int b,int c,int d):hinh(m) } { virtual void dchuyen(int b); x1=a;y1=b;x2=c;y2=d; void hien(void) } { virtual void dchuyen(int b); setcolor(mau); circle(x,y,r); void hien(void) } { void an(void) setcolor(mau); { line(x1,y1,x2,y2); setcolor(getbkcolor()); } circle(x,y,r); void an(void) } { }; setcolor(getbkcolor()); char getkey(int &dx,int &dy) line(x1,y1,x2,y2); { } int ch1,ch2; }; dx=dy=0; class tron:public hinh while (1) { { private: ch1=getch(); int x,y,r; if (ch1==0) public: ch2=getch(); tron(void):hinh() if (ch1=='q'||ch1=='Q') return('q'); { if x=y=r=0; ((ch1==0&&(ch2==80||ch2==72||ch2==75||ch2==77))) } 522 { 523 tron(int m,int a,int b,int d):hinh(m) if (ch2==80) dy=1;
11. else if (ch2==72) dy=-1; x2+=b*dx; else if (ch2==77) dx=1; y1+=b*dy; else dx=-1; y2+=b*dy; return(0); } } } } void tron::dchuyen(int b) } { void khoihop::dchuyen(int b) int dx,dy; { while (1) int dx,dy; { while (1) hien(); { if (getkey(dx,dy)=='q') break; an(); hien(); x+=b*dx; if (getkey(dx,dy)=='q') break; y+=b*dy; an(); } x+=b*dx; } y+=b*dy; } void main() { } int mh=0,mode=0; void duong::dchuyen(int b) initgraph(&mh,&mode,""); { if (graphresult()) int dx,dy; { while (1) printf("\n LOI"); { getch(); hien(); exit(0); if (getkey(dx,dy)=='q') break; } an(); setbkcolor(0); x1+=b*dx; 524 525
12. // setwritemode(0); 3. Lớp stack thừa kế từ lớp s_list hinh *h[3]; 4. Lớp queue thừa kế từ lớp stack khoihop M(4,300,200,15); Các lớp stack và queue không có các thuộc tính riêng. Hai duong D(10,10,10,60,60); phương thức quan trọng của các lớp này là: tron T(14,200,200,50); virtual int store(void *item) ; // Cất vào một phần tử h[0]=&M; h[1]=&D;h[2]=&T; virtual void *retrieve () ; // Lấy ra một phần tử for(int i=0;i dchuyen(10); sau ra trước) còn lớp queue hoạt động theo nguyên tắc FIFO (vào trước ra trước) . closegraph(); Chương trình sau minh hoạ cách dùng liên kết bội, phương } thức ảo và con trỏ kiểu void để quản lý các kiểu dữ liệu khác nhau. § 4. Các lớp ngăn xếp và hàng đợi Hoạt động của chương trình như sau: Chương trình tổ chức thành 4 lớp chính: + Trước tiên lần lượt đưa địa chỉ của biến đối tượng ts1, chuỗi “HA NOI”, biến nguyên a, biến đối tượng ts2 và biến 1. Lớp container (thùng chứa) gồm 2 thuộc tính: thực x vào ngăn xếp s1 và hàng đợi q1. unsigned long count; //Số phần tử trong thùng chứa + Thực hiện phép gán các biến đối tượng: void (*errhandler)(); //Con trỏ tới hàm xử lý lỗi s2 = s1 ; 2. Lớp s_list thừa kế từ lớp container, có thêm 2 thuộc q2 = q1 ; tính các con trỏ kiểu cấu trúc listnode: + Lấy các phần tử trong ngăn xếp s2 theo trình tự ngược struct listnode với lúc đưa vào. { + Lấy các phần tử trong hàng đợi q2 theo trình tự như lúc void *dataptr; đưa vào. listnode *next; /* }; CT10_05.CPP listnode *head; // Trỏ tới đầu danh sách Lop vat chua (container) listnode *tail; // Trỏ tới cuối danh sách Lop danh sach moc noi Các phần tử được chứa trong lớp s_list dưới dạng một Lop ngan xep danh sách móc nối đơn. Mỗi nút chứa địa chỉ của một phần tử. Do ở đây dùng kiểu con trỏ void nên có thể đưa vào lớp Lop hang doi s_list các phần tử có kiểu bất kỳ.
13. Chu y: virtual int store(void *item)=0;//Cat mot phan tu vao 1. constructor sao chep cua lop dan suat thung 2. toan tu gan cua lop dan suat virtual void *examine()=0; // Xem gia tri mot phan tu 3. co the dung cac phuong thuc khac virtual void *retrieve ()=0; // Lay mot pt ra 526 527 de viet constructor va destructor virtual void empty()=0; // Lam cho thung tro nen rong 4. Dung con tro this }; */ // Cai dat #include // Ham xl loi mac dinh #include void defaulthandler(); #include void defaulthandler() { #include puts("\nContainer error: memory allocation failure"); #include } #include container::container () //Lop container { class container count=0; errhandler= defaulthandler; { } protected: container::container(const container &c) unsigned long count; //so pt trong thung chua { void (*errhandler)(); count=c.count; errhandler=c.errhandler; public: } container(); // Gan container(const container &c); // Ham tao sao chep void container::operator=(const container &c) void operator=(const container &c); // Gan { unsigned long getcount(); // Cho biet so phan tu count=c.count; errhandler=c.errhandler; // Dinh ham xl loi } void seterrorhandler(void (*userhandler)()); // Cho biet so pt // 4 phuong thuc thuan ao unsigned long container::getcount() {
14. return count; // 4 phuong thuc ao } virtual int store(void *item)=0; // Cat mot phan tu vao // Dinh ham xl loi // thung void container::seterrorhandler(void (*userhandler)()) virtual void *examine()=0; // Xem gia tri mot phan tu { virtual void *retrieve ()=0; // Lay mot pt ra errhandler=userhandler; virtual void empty(); // Lam cho thung tro nen rong } }; // Lop danh sach moc noi don 528 //Cai dat 529 class s_list:public container void s_list::copy(const s_list &s1) { { protected: head=NULL; tail=NULL; //Cau truc mot nut trong ds listnode *temp = s1.head; struct listnode while(temp!=NULL) { { void *dataptr; if(head==NULL) listnode *next; { }; head= new listnode; listnode *head; if(head==NULL) errhandler(); listnode *tail; tail=head; private: } // phuong thuc sao chep else void copy(const s_list &s1); { public: tail->next = new listnode; s_list(); if(tail->next == NULL) errhandler(); tail = tail->next; s_list(const s_list &s1); } ~s_list(); tail->dataptr= temp->dataptr; void operator=(const s_list &s1);
15. tail->next=NULL; { temp = temp->next; q=p; p=p->next; } delete q; } } // constructor } s_list::s_list() : container() // Lop stack { class stack:public s_list head=NULL; tail=NULL; { } public: s_list::s_list(const s_list &s1):container(s1) stack(); 530 531 { stack(const stack &st); copy(s1); void operator=(const stack &st); } virtual int store(void *item); // Cat mot phan tu vao thung s_list::~s_list() virtual void *examine(); // Xem gia tri mot phan tu { virtual void *retrieve(); // Lay mot pt ra this->empty(); }; } stack::stack():s_list() void s_list::operator=(const s_list &s1) { { } this->empty(); stack::stack(const stack &st):s_list(st) { count=s1.count; } copy(s1); void stack::operator=(const stack &st) } { void s_list::empty() this->s_list::operator=(st); //Dung toan tu gan cua s_list { } listnode *q,*p; int stack::store(void *item) // Cat mot phan tu vao thung p = head; head=NULL; tail=NULL; { while (p!=NULL) //Dua vao dau danh sach
16. listnode *p; { p= new listnode ; public: if(p==NULL) return 1; queue(); count++; queue(const queue &q); p->dataptr=item; p->next=head; void operator=(const queue &q); head=p; return 0; } virtual int store(void *item); // Cat mot phan tu vao thung void *stack::examine() // Xem gia tri mot phan tu { }; if(count==0) return NULL; queue::queue(): stack() else { return head->dataptr; } } queue::queue(const queue &q):stack(q) void *stack::retrieve() // Lay mot pt ra { 532 533 { } if(count==NULL) return NULL; void queue::operator=(const queue &q) else { { this->stack::operator=(q); //Dung toan tu gan cua stack listnode *p; void *value; } value = head->dataptr; int queue::store(void *item) p=head; { head = p->next; // Dat vao cuoi delete p; listnode *q; count ; q=new listnode; return value; if(q==NULL)return 1; } // Bo sung } q->next=NULL; q->dataptr=item; // Lop queue if(count==0) class queue:public stack {
17. head=q; tail=q; cout next=q; > sobd; s1.store(&ts2); q1.store(&ts2); cout > td; //Lay ra tu ngan xep theo nguyen tac LIFO } cout <<"\n\nLay ra tu ngan xep:" ; void xuat() s2=s1; { y = *((float*)s2.retrieve());
18. cout << "\nSo thuc = " <<setiosflags(ios::showpoint) § 5. Các lớp sắp xếp << setprecision(2)<< y; Trong tệp C_SORT.H dưới đây sẽ chứa 4 lớp sắp xếp: ts = *((TS*)s2.retrieve()); sort, select_sort, quick_sort và heap_sort. tổng quát hơn. So § ts.xuat(); 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ỗ: b = *((int*)s2.retrieve()); + Các lớp trong mục §7 chương 6 chỉ cho phép sắp xếp cout << "\nSo nguyen = " << b; một dẫy số nguyên theo thứ tự tăng dần. str = (char*)s2.retrieve(); + Các lớp dưới đây cho phép sắp xếp một dẫy phần tử có cout << "\nChuoi ky tu: " << str; kiểu bất kỳ (nguyên, thực, cấu trúc, lớp, ) và theo một tiêu ts = *((TS*)s2.retrieve()); chuẩn sắp xếp bất kỳ. ts.xuat(); 1. Lớp sort là lớp cơ sở trừu tượng //Lay ra tu hang doi theo nguyen tac FIFO + Các thuộc tính: cout <<"\n\nLay ra tu hang doi:" ; protected: q2=q1; void *a ; // Trỏ tới vùng nhớ chứa dẫy ts = *((TS*)q2.retrieve()); // phần tử cần sắp xếp ts.xuat(); int size ; // Độ lớn tính theo byte của phần tử str = (char*)q2.retrieve(); cout << "\nChuoi ky tu: " << str; int (*nho_hon)(void* pt1, void* pt2); // Con trỏ hàm b = *((int*)q2.retrieve()); // định nghĩa pt1 nhỏ hơn pt2 + Các phương thức: 536 537 cout << "\nSo nguyen = " << b; protected: ts = *((TS*)q2.retrieve()); void hoan_vi(int i, int j) ; // Hoán vị các phần tử thứ i và ts.xuat(); j y = *((float*)q2.retrieve()); void * dia_chi (int m); // Cho địa chỉ của phần tử thứ cout << "\nSo thuc = " << setiosflags(ios::showpoint) m << setprecision(2)<< y; public: getch(); virtual void sapxep(void *a1,int n,int itemsize, } int (*ss_nho_hon)(void* ,void* )) ; // Sắp xếp dẫy
19. // n phần tử chứa trong vùng nhớ a1, mỗi private: phần tử void shift(int i, int n); // có độ dài itemsize, thứ tự tăng được quy public: định virtual void sapxep(void *a1,int n,int itemsize, // bởi hàm ss_nho_hon int (*ss_nho_hon)(void* ,void* )) ; // thực 2. Lớp select_sort dẫn xuất từ lớp sort. Lớp này sẽ thực hiện hiện việc sắp xếp theo phương pháp chon (xem mục §7 // sắp xếp theo phương pháp heap chương 6). sort + Các phương thức: Dưới đây là nội dung tệp C_SORT.H //C_SORT.H public: // Lop co so truu tuong virtual void sapxep(void *a1,int n,int itemsize, // Lop sort int (*ss_nho_hon)(void* ,void* )) ; // thực hiện #include // sắp xếp theo phương pháp chọn #include 3. Lớp quick_sort dẫn xuất từ lớp sort. Lớp này sẽ thực #include hiện việc sắp xếp theo phương pháp quick sort (xem mục §7 #include chương 6) #include + Các phương thức: #include class sort private: { void q_sort(int l, int r); protected: public: void *a; virtual void sapxep(void *a1,int n,int itemsize, int size; int (*ss_nho_hon)(void* ,void* )) ; // thực hiện int (*nho_hon)(void*,void*); void* dia_chi(int m) // 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 return (void*) ((char*)a + size*(m-1)); 538hiện việc sắp xếp theo phương pháp heap sort (xem mục §7 539 chương 6). } void hoan_vi(int i, int j) + Các phương thức:
20. { sort::sapxep(a1,n,itemsize,ss_nho_hon); void *tg, *di, *dj; for(i=1; i<n; ++i) di= dia_chi(i); { dj= dia_chi(j); r=i; tg = new char[size]; for(j=i+1; j<=n; ++j) memcpy(tg,di,size); if(nho_hon(dia_chi(j),dia_chi(r))) r = j; memcpy(di,dj,size); if(r!=i) hoan_vi(i,r); memcpy(dj,tg,size); } } } public: class quick_sort : public sort virtual void sapxep(void *a1,int n,int itemsize, { int (*ss_nho_hon)(void*,void*)) private: { void q_sort(int l, int r); a=a1; public: size=n; // Cho C++ hai long virtual void sapxep(void *a1,int n,int itemsize, size=itemsize; int (*ss_nho_hon)(void*,void*)) ; nho_hon= ss_nho_hon; } ; } } ; void quick_sort::q_sort(int l, int r) class select_sort : public sort { { void *x; public: int i,j; virtual void sapxep(void *a1,int n,int itemsize, x = new char[size]; int (*ss_nho_hon)(void*,void*)) ; if(l < r) } ; { void select_sort::sapxep(void *a1,int n,int itemsize, memcpy(x, dia_chi(l), size); int (*ss_nho_hon)(void*,void*)) i = l; j = r+1; { do int i,j,r; { 540 541
21. ++i; j; l = 2*i; r = l+1; while(i n) return; while(nho_hon(x,dia_chi(j)) ) j ; if(l==n) 542 543 if(i =1; i) shift(i,n); // Lap void heap_sort::shift(int i, int n) for(i=n ; i>=2; i) { { int l,r,k; hoan_vi(1,i);
22. shift(1,i-1); cout > sobd; Trong mục này trình bầy 2 chương trình minh hoạ cách 544 cout > td; 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 để void xuat() 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 cout get_td() > ((TS*)ts2)->get_td()) ; float td; } public: int ss_tong_diem_tang(void *ts1, void *ts2) float get_td() { { return ( ((TS*)ts1)->get_td() get_td()) ; return td; } } void nhap() void main() { {
23. TS t[100]; delete sa; sort *sa; getch(); int n,i; cout > n; sa->sapxep( t+1,n,sizeof(TS),ss_tong_diem_tang); for(i=1; i sapxep( t+1,n,sizeof(TS),ss_tong_diem_giam); sa->sapxep( t+1,n,sizeof(TS),ss_tong_diem_giam); 546 547 for(i=1; i sapxep( t+1,n,sizeof(TS),ss_tong_diem_tang); sa->sapxep( t+1,n,sizeof(TS),ss_tong_diem_tang); for(i=1; i sapxep( t+1,n,sizeof(TS),ss_tong_diem_giam); // Lop co so truu tuong for(i=1; i<=n; ++i) t[i].xuat(); // Lop sort
24. #include "c_sort.h" for(k=0; k sapxep (a+1,n,sizeof(int),ss_tang); int ss_giam(void *i1,void *i2) //In { for(i=1;i *((int*)i2); } } cout sapxep (a+1,n,sizeof(int),ss_giam); sort *s[3]; 548 //In 549 select_sort ss; for(i=1;i<=n;++i) cout <<a[i]<<" "; quick_sort qs; cout << "\n"; heap_sort hs; s[0]=&ss; s[1]=&qs; s[2]=&hs; } clrscr(); getch(); 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";