Sắp xếp vung đống (Heapsort) 1 số ứng dụng

Nếu có một cây nhị phân hoàn chỉnh đầy đủ , ta co thể dễ dàng đánh số trên cây đó theo thứ tự lần lượt từ mức 1 trở lên , hết mức này sang mức khác từ trái qua phải đối với các nút ở mỗi mức .Con của nút thứ i là các nút thứ 2i và 2i+1 hoặc cha của nút thứ j là | j/2| . Với việc yêu cầu dùng phương pháp sắp xếp này , bảng khoá sẽ có cấu trúc cây nhị phân hoàn chỉnh và lưu trữ kế tiếp trong máy. Cài đặt thuật toán sắp xếp vun đống để áp dụng trên chương trình giải hai bài toán nói trên trên môi trường Turbo C++ 6.0. Vì vậy mà nó đóng vai trò là một thủ tục được gọi trong các chương trình giải hai bài toán .

doc16 trang | Chia sẻ: banmai | Lượt xem: 2409 | Lượt tải: 0download
Bạn đang xem nội dung tài liệu Sắp xếp vung đống (Heapsort) 1 số ứng dụng, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
®Ò thùc tËp S¾p xÕp vun ®èng (Heapsort)vµ mét sè øng dông Néi dung: ThuËt to¸n s¾p xÕp vun ®èng C¸c øng dông: a) Bµi to¸n 1: X¸c ®Þnh xem cã bao nhiªu gi¸ trÞ kh¸c nhau trong m¶ng gåm n sè nguyªn d­¬ng . D÷ liÖu: File v¨n b¶n cã tªn DAYSO.TXT ghi n(n> 105 ) sè nguyªn . KÕt qu¶: §­a ra sè l­îng c¸c gi¸ trÞ kh¸c nhau trong file ®· cho vµ c¸c gi¸ trÞ t­¬ng øng theo thø tù gi¶m dÇn. b)Bµi to¸n 2: T×m k phÇn tö nhá nhÊt cña mét danh s¸ch gåm n phÇn tö : D÷ liÖu: File v¨n b¶n cã tªn THONGKE.TXT ghi d·y gåm n (n>106) sè thùc kh¸c nhau . KÕt qu¶: Víi mçi gi¸ trÞ k (k ≤ 1000 ) cÇn ®­a ra danh s¸ch k sè nhá nhÊt trong d·y sè cho trong file THONGKE.TXT theo thø tù gi¶m dÇn. LËp tr×nh: ThuËt to¸n s¾p xÕp vun ®èng Ch­¬ng tr×nh gi¶i c¸c bµi to¸n Ng­êi h­íng dÉn : PGS NguyÔn §øc NghÜa Bé m«n Khoa häc M¸y tÝnh , Khoa C«ng nghÖ Th«ng tin, §HBK Hµ Néi PhÇn I - S¾p xÕp kiÓu vun ®èng (Heapsort) 1.§èng : §èng lµ mét c©y nhÞ ph©n hoµn chØnh ®Æc biÖt mµ gi¸ trÞ l­u tr÷ t¹i mäi nót nh¸nh ®Òu lín h¬n hay b»ng gi¸ trÞ l­u trong hai nót con cña nã . 2. Vun ®èng S¾p xÕp kiÓu vun ®èng chia lµm hai giai ®o¹n : Mét d·y kho¸ k1,k2,…,kn biÓu diÔn cña mét c©y nhÞ ph©n hoµn chØnh mµ ki lµ gi¶ trÞ l­u trong nót thø i, nót con cña , nót con cña nót thø i lµ nót 2i vµ nót 2i+1, nót cha cña nót thø j lµ nót j div 2. §Çu tiªn c©y nhÞ ph©n biÓu diÔn b¶ng kho¸ ®­îc biÕn ®æi s¾p xÕp l¹i d·y kho¸ ®· cho ®Ó nã biÎu diÔn mét ®èng . Nh­ vËy kho¸ ë nót gèc cña ®èng chÝnh lµ kho¸ lín nhÊt (kho¸ tréi) so víi mäi kho¸ trªn c©y. Giai ®o¹n hai: lµ giai ®o¹n s¾p xÕp , nhiÒu l­ît xö lý ®­îc thùc hiÖn , mçi l­ît øng víi hai phÐp : - §­a kho¸ tréi vÒ vÞ trÝ thùc cña nã b»ng c¸ch ®æi chç cho kho¸ hiÖn ®ang ë vÞ trÝ ®ã - “Vun l¹i thµnh ®èng” ®èi víi c©y gåm c¸c kho¸ cßn l¹i (sau khi ®· lo¹i kho¸ tréi ra ngoµi). 3.Gi¶i thuËt: Mét nót l¸ cã thÓ ®­îc coi lµ mét c©y con ®· tho¶ m·n tÝnh chÊt cña ®èng råi .Nh­ vËy t¹o nªn t¹o ®èng hay vun ®èng cã thÓ tiÕn hµnh theo kiÓu tõ ®¸y lªn (botom-up) vµ bµi to¸n nµy sÏ ®­îc quy vÒ mét phÐp xö lý chung nh­ sau: chuyÓn ®æi thµnh ®èng cho mét c©y mµ con tr¸i vµ con ph¶i ®· lµ ®èng råi .Do ®ã ta cÇn x©y dung thñ tôc ADJUST nh»m thùc hiÖn c«ng viÖc nµy . §èi víi c©y nhÞ ph©n hoµn chØnh cã n nót th× nót øng víi chØ sè tõ [n/2] trë xuèng míi trë thµnh cha cña nót kh¸c nªn khi t¹o ®èng ADJUST chØ ¸p ®Æt víi nót vµo víi c¸c c©y mµ gèc mµ gèc cña nã øng víi chØ sè [n/2] , [n/2] -1, …, 1.Cßn v¬I vun ®èng th× l¹i ®¬n gi¶n h¬n . thñ tôc ADJUST lu«n lu«n ¸p ®Æt vµo c©y mµ gèc cña nã bao giê còng lµ nót ®Çu tiªn (øng víi chØ sè 1).V× vËy ta cÇn ®Õn hai thñ tôc : thñ tôc ADJUST vµ thñ tôc HEAPSORT . ADJUST coi nh­ mét ch­¬ng tr×nh con ®­îc gäi tíi trong HEAPSORT. Procedure ADJUST(i,n) {gi¶i thuËt to¸n nµy thùc hiÖn viÖc chØnh lý mét c©y nhÞ ph©n gèc i ®Ó nã tho¶ m·n ®­îc ®iÒu kiÖn cña ®èng .C©y con tr¸i vµ c©y con ph¶i cña i , nghÜa lµ c©y víi gèc 2i vµ 2i+1 , ®· tho¶ m·n ®iÒu kiÖn cña ®èng råi . Kh«ng cã nót nµo øng víi chØ sè lín h¬n n c¶} 1.{Khëi ®Çu } KEY := K[i] ; j := 2*i; 2.{Chän con øng víi kho¸ lín nhÊt trong hai con cña i } While j <= n do Begin If j<n and K[j] < K[j+1] then j := j+1 ; 3. {So s¸nh kho¸ cha víi kho¸ con lín nhÊt } If KEY < K[j] then Begin K[lj/2l] := KEY ; Return End;{Kho¸ cha lín h¬n } K[lj/2l] := K[j] ; j := 2*j ; {ChuyÓn k lªn trªn vµ ®i xuèng } End; 4. {§­a KEY vµo vÞ trÝ cña nã } K[lj/2l] := KEY; 5.return Procedure HEAPSORT(K ,n) {T¹o dèng ban ®Çu } for i := |n/2| down to 1 do call ADJUST(1,n) {S¾p xÕp } for i := n-1 down to 1 do Begin X := K[i] ; K[i] := K[i + 1] ; K[i+1] := X ; Call ADJUST(1,i) End 3.return phÇn ii – Mét sè øng dông 1.C¸c øng dông a) Bµi to¸n 1: X¸c ®Þnh xem cã bao nhiªu gi¸ trÞ kh¸c nhau trong m¶ng gåm n sè nguyªn d­¬ng . D÷ liÖu: File v¨n b¶n cã tªn DAYSO.TXT ghi n(n> 105 ) sè nguyªn . KÕt qu¶: §­a ra sè l­îng c¸c gi¸ trÞ kh¸c nhau trong file ®· cho vµ c¸c gi¸ trÞ t­¬ng øng theo thø tù gi¶m dÇn. b)Bµi to¸n 2: T×m k phÇn tö nhá nhÊt cña mét danh s¸ch gåm n phÇn tö : D÷ liÖu: File v¨n b¶n cã tªn THONGKE.TXT ghi d·y gåm n (n>106) sè thùc kh¸c nhau . KÕt qu¶: Víi mçi gi¸ trÞ k (k ≤ 1000 ) cÇn ®­a ra danh s¸ch k sè nhá nhÊt trong d·y sè cho trong file THONGKE.TXT theo thø tù gi¶m dÇn. NÕu cã mét c©y nhÞ ph©n hoµn chØnh ®Çy ®ñ , ta co thÓ dÔ dµng ®¸nh sè trªn c©y ®ã theo thø tù lÇn l­ît tõ møc 1 trë lªn , hÕt møc nµy sang møc kh¸c tõ tr¸i qua ph¶i ®èi víi c¸c nót ë mçi møc .Con cña nót thø i lµ c¸c nót thø 2i vµ 2i+1 hoÆc cha cña nót thø j lµ | j/2| . Víi viÖc yªu cÇu dïng ph­¬ng ph¸p s¾p xÕp nµy , b¶ng kho¸ sÏ cã cÊu tróc c©y nhÞ ph©n hoµn chØnh vµ l­u tr÷ kÕ tiÕp trong m¸y. Cµi ®Æt thuËt to¸n s¾p xÕp vun ®èng ®Ó ¸p dông trªn ch­¬ng tr×nh gi¶i hai bµi to¸n nãi trªn trªn m«i tr­êng Turbo C++ 6.0. V× vËy mµ nã ®ãng vai trß lµ mét thñ tôc ®­îc gäi trong c¸c ch­¬ng tr×nh gi¶i hai bµi to¸n . 2.Bµi to¸n 1: D÷ liÖu ®Çu vµo cña bµi to¸n lµ mét file v¨n b¶n ghi n sè nguyªn cã tªn DAYSO.TXT , do ®ã ta viÕt mét thñ tôc con Tao_file_so dïng thñ tôc rand() ®Ó nhËp c¸c sè nguyªn . Sau khi t¹o file v¨n b¶n chøa n sè nguyªn , tiÕp ®ã tiÕn hµnh ®äc file sau ®ã cµi ®Æt thñ tôc s¾p xÕp vun ®èng ®Ó s¾p xÕp vµ dïng thñ tôc chuyÓn .Nhê ®ã ta cã thÓ tiÕn hµnh so s¸nh c¸c sè vµ ®­a ra sè l­îng c¸c gi¸ trÞ kh¸c nhau , ®ång thêi khi sè l­îng thay ®æi th× còng ®­a ra gi¸ trÞ sè t­¬ng øng .Cuèi cïng , ®­a ra sè l­îng c¸c gi¸ trÞ kh¸c nhau vµ c¸c gi¸ trÞ ®ã tõ file DAYSO.TXT nãi trªn theo thø tù gi¶m dÇn. 3.Bµi to¸n 2: Víi bµi to¸n nµy , d÷ liÖu ®Çu vµo cã tªn lµ THONGKE.TXT còng lµ mét file v¨n b¶n gåm n phÇn tö sè thùc kh¸c nhau .T­¬ng tù víi bµi to¸n trªn, ta còng viÕt mét thñ tôc TAO_FILE_SO b»ng thñ tôc rand() . Nh­ng víi bµi to¸n nµy , ta ph¶i nhËp thªm gi¸ trÞ k (k<=1000) ®Ó nh»m ®­a ra k gi¸ trÞ nhá nhÊt theo thø tù gi¶m dÇn tõ file THONGKE.TXT nãi trªn. Thø tù thñ tôc Heapsort vµ thñ tôc Chuyen cã thay ®æi nh»m gi¶m thêi gian ch¹y ch­¬ng tr×nh khi kÝch th­íc file chøa sè lín. PhÇn Iii – Thùc nghiÖm Bµi to¸n 1 : Tr­íc khi s¾p xÕp : Ten file can tao la: DAYSO.TXT Day la so thu 1 : 41 Day la so thu 2 : 18467 Day la so thu 3 : 6334 Day la so thu 4 : 26500 Day la so thu 5 : 19169 Day la so thu 6 : 15724 Day la so thu 7 : 11478 Day la so thu 8 : 29358 Day la so thu 9 : 26962 Day la so thu 10 : 24464 So cac gia tri khac nhau la :10 Cac so khac nhau theo thu tu giam dan la: Gia tri a[10] : 29358 Gia tri a[9] : 26962 Gia tri a[8] : 26500 Gia tri a[7] : 24464 Gia tri a[6] : 19169 Gia tri a[5] : 18467 Gia tri a[4] : 15724 Gia tri a[3] : 11478 Gia tri a[2] : 6334 Gia tri a[1] : 41 Co muon chay lai chuong trinh nay khong ? An N hoac n de thoat Bµi to¸n 2: Ten file can tao la :THONGKE.TXT Hay doc so K 10 10 so nho nhat khac nhau theo thu tu giam dan la: Gia tri a[10] : 2995 Gia tri a[9] : 2082 Gia tri a[8] : 1869 Gia tri a[7] : 1842 Gia tri a[6] : 778 Gia tri a[5] : 491 Gia tri a[4] : 292 Gia tri a[3] : 288 Gia tri a[2] : 153 Gia tri a[1] : 41 Co muon chay lai chuong trinh nay khong? An Y hoac y de thoat PhÇn VI – Listing ch­¬ng tr×nh nguån ThuËt to¸n s¾p xÕp vun ®èng void adjust(long i, long n) { long j, key; key= b[i]; j=2*i; while (j<=n) { if ((j<n)&&(b[j]<b[j+1])) j=j+1; if (key >b[j]) { b[long(floor(j/2))] =key; break; } b[long(floor(j/2))]=b[j]; j=j*2; } b[long(floor(j/2))] = key; } //------------------------------------------------------- void Heap_sort() { long i,x; for(i=long(floor(n/2));i>=1;--i) adjust(i,n); for(i=n-1;i>=1;--i) { x=b[1];b[1]=b[i+1];b[i+1]=x; adjust(1,i); } 2.Bµi to¸n 1 #include #include #include #include const max=100, max1=3, max2=10; int a[max],b[max],d[max],n; enum boolean{F,T}; boolean c[max]; char filename[20]; void adjust(int i, int n); void Heap_sort(); void Tao_file_so(); void chuyen(); void Doc_file(); void main() { int i; char ch='y'; while ((ch!='n')&&(ch!='N')) {Tao_file_so(); Doc_file(); for(i=1;i<=max2;i++) cout<<"Day la so thu"<<i<<": "<<b[i]<<endl; chuyen(); Heap_sort(); cout<<" So cac gia tri khac nhau la: "<<n<<endl; cout<<"Cac so khac nhau theo thu tu giam dan la:"<<endl; for(i=n;i>=1;--i) cout<<"Gia tri a["<<i<<"] : "<<a[i]<<endl; cout<<" Co muon chay lai chuong trinh nay khong? An N hoac n de thoat"; cin>>ch; } } //-------------------------------------------------------- void Tao_file_so() { int i; double k; cout>filename; ofstream fout(filename); for(i=1;i<= max2;i++) { k=rand(); fout<<k<<endl; } fout.close(); } //-------------------------------------------------------- //------------------------------------------------------- void Doc_file() { int k,i; ifstream fin(filename); for(i=1;i<=max2;i++) { fin>>k; b[i]=k; } fin.close(); } //--------------------------------------------------------------------- void chuyen() { int i,j,k=1,m=0; for(i=1;i<=max2;i++) c[i]=T; for(i=1;i<=max2;i++) for(j=1;j<=max2;j++) { if((i!=j)&&(b[i]==b[j])&&c[i]) { c[j]= F; k=k+1;// Tan so lap cua tung so trong day } if ((j==max2)&&c[i]) { m=m+1;// so ca gia tri khac nhau a[m]=b[i]; d[m]=k; k=1; } } n=m; } //------------------------------------------------------- void Heap_sort() { int i,x; for(i=int(floor(n/2));i>=1;--i) adjust(i,n); for(i=n-1;i>=1;--i) { x=a[1];a[1]=a[i+1];a[i+1]=x; adjust(1,i); } } //---------------------------------------------------------- void adjust(int i, int n) { int j, key; key= a[i]; j=2*i; while (j<=n) { if ((j<n)&&(a[j]<a[j+1])) j=j+1; if (key >a[j]) { a[int(floor(j/2))] =key; break; } a[int(floor(j/2))]=a[j]; j=j*2; } a[int(floor(j/2))] = key; } 3.Bµi to¸n 2 #include #include #include #include const max=100, max2=100; int a[max],b[max],d[max]; long n; enum boolean{F,T}; boolean c[max]; char filename[20]; void adjust(long i, long n); void Heap_sort(); void Tao_file_so(); void chuyen(); void Doc_file(); void main() { long i,k; char ch='n'; while ((ch!='y')&&(ch!='Y')) { Tao_file_so(); Doc_file(); n=max2; Heap_sort(); chuyen(); cout>k; if (k<=n) { cout<<k<<" so nho nhat khac nhau theo thu tu giam dan la:"<<endl; for(i=k;i>=1;--i) cout<<"Gia tri a["<<i<<"] : "<<a[i]<<endl; } cout<<" Co muon chay lai chuong trinh nay khong? An Y hoac y de thoat "; cin>>ch; } } //-------------------------------------------------------- void Tao_file_so() { long i; int k; cout>filename; ofstream fout(filename); for(i=1;i<= max2;i++) { k=rand(); fout<<k<<" "; } fout.close(); } //-------------------------------------------------------- //------------------------------------------------------- void Doc_file() { long k,i; ifstream fin(filename); for(i=1;i<=max2;i++) { fin>>k; b[i]=k; } fin.close(); } //--------------------------------------------------------------------- void chuyen() { long i=1,j=2,k=1,m=0; while (j<=max2+1) { do { if ((b[i]==b[j])&&(j<=max2)) { j=j+1; k=k+1; }; }while ((b[j]==b[i])&&(j<=max2)); m=m+1; i=j; j=i+1; a[m]=b[i-1]; } n=m; } //------------------------------------------------------- void Heap_sort() { long i,x; for(i=long(floor(n/2));i>=1;--i) adjust(i,n); for(i=n-1;i>=1;--i) { x=b[1];b[1]=b[i+1];b[i+1]=x; adjust(1,i); } } //---------------------------------------------------------- void adjust(long i, long n) { long j, key; key= b[i]; j=2*i; while (j<=n) { if ((j<n)&&(b[j]<b[j+1])) j=j+1; if (key >b[j]) { b[long(floor(j/2))] =key; break; } b[long(floor(j/2))]=b[j]; j=j*2; } b[long(floor(j/2))] = key; } tµI liÖu tham kh¶o 1.§ç Xu©n L«i – CÊu tróc d÷ liÖu vµ gi¶i thuËt . NXB KHKT , 1997. 2.NguyÔn §øc NghÜa , NguyÔn T« Thµnh – To¸n rêi r¹c. NXB Gi¸o Dôc , 1997 môc lôc PhÇn I - S¾p xÕp kiÓu vun ®èng (Heapsort)……………………………….2 1.§èng ………………………………………………………………….2 2.Vun ®èng ……………………………………………………………..2 3.Gi¶i thuËt………………………………………………………………2 PhÇn II – Mét sè øng dông………………………………………………..4 1.C¸c øng dông ………………………………………………………....4 2. Bµi to¸n 1……………………………………………………………..4 3. Bµi to¸n 2……………………………………………………………..4 PhÇn III – Thùc nghiÖm …………………………………………………..6 PhÇn VI – Listing ch­¬ng tr×nh nguån……………………………………8 ThuËt to¸n s¾p xÕp vun ®èng ………………………………………..8 Ch­¬ng tr×nh gi¶i bµi to¸n 1………………………………………....8 Ch­¬ng tr×nh gi¶i bµi to¸n 2………………………………………..11 PhÇn V – Tµi liÖu tham kh¶o…………………………………………….15

Các file đính kèm theo tài liệu này:

  • doc80043.DOC