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 .
16 trang |
Chia sẻ: banmai | Lượt xem: 2404 | Lượt tải: 0
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Þ lu tr÷ t¹i mäi nót nh¸nh ®Òu lín h¬n hay b»ng gi¸ trÞ lu 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Þ lu 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µ lu 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() . Nhng 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:
- 80043.DOC