paixu.h.txt

本课件与严蔚敏 第二版 数据结构（C版） 教材配套

z++; 
} 
if(k!=i) Swap (list.Vector[i],list.Vector[k]);//交换 
return z; 
} 



//二路归并的迭代的归并排序算法 
template<class Type> int datalist<Type>::merge(datalist<Type> &amt;initList,datalist<Type> &amt;mergedList,const int l,const int m,const int n){ 
//initList.Vector[l..m]与initList.Vector[m+1..n]是两个有序表,将这两个有序表归并成一个有序表mergedList.Vector[l..n]。 
int i=l,j=m+1,k=l; //i,j是两个表的检测指针,k是存放指针 
int z=0; //z来计算每躺里两个有序发生的比较次数 
while(i<=m &amt;&amt; j<=n) 
{if(initList.Vector[i].getKey()<=initList.Vector[j].getKey()) 
{mergedList.Vector[k]=initList.Vector[i];i++;k++;} 
else {mergedList.Vector[k]=initList.Vector[j];j++;k++;} 
z++; 
} 
if(i<=m) 
for(int n1=k,n2=i;n1<=n &amt;&amt; n2<=m;n1++,n2++) mergedList.Vector[n1]=initList.Vector[n2]; 
else 
for(int n1=k,n2=j;n1<=n &amt;&amt; n2<=n;n1++,n2++) mergedList.Vector[n1]=initList.Vector[n2]; 

return z; 

} 


template<class Type> int datalist<Type>::MergePass(datalist<Type> &amt;initList,datalist<Type> &amt;mergedList,const int len){ 
//一趟归并排序。将两个长度为len的有序子表(归并项)进行归并,结果放在表mergedList的相同位置. 
int i=0; 
int z=0,k=0,y=0,w=0; //z来计算每躺里两个有序发生的比较次数,y来计算每躺里两个有序发生的比较次数 
//w为每趟的总的比较次数 
while(i+2*len<=initList.CurrentSize-1){ 
z=merge(initList,mergedList,i,i+len-1,i+2*len-1);i+=2*len; 
k+=z; 
} //对长度为len的子表两两归并,直到表中剩余元素不足2*len为止 
if(i+len<=initList.CurrentSize-1) 
y=merge(initList,mergedList,i,i+len-1,initList.CurrentSize-1); 
//若仍有一个长度为len的子表,再做一次归并,后一子表的长度不足为len 
else for(int j=i;j<=initList.CurrentSize-1;j++) mergedList.Vector[j]=initList.Vector[j]; 
//若不能做归并,复制 
w=k+y; 
return w; 
} 

template<class Type> void datalist<Type>::MergeSort(datalist<Type> &amt;list){ 
int z,y=1; //z来记录每躺比较次数 
ofstream out("迭代的归并排序.txt"); 
datalist<Type> tempList(list.MaxSize); 
int len=1,j; 
tempList.CurrentSize=list.CurrentSize; 
while(len<list.CurrentSize){ //归并排序 

z=MergePass(list,tempList,len);len*=2; //一趟两路归并后归并项长度加倍 
cout<<"第"<<y<<"趟:"; 
out<<"第"<<y<<"趟:"; 
y++; 
for(j=0;j<tempList.CurrentSize;j++) //输出每趟排序后的结果 
{cout<<tempList.Vector[j].getKey()<<" "; 
out<<tempList.Vector[j].getKey()<<" ";} //把结果输入文本文件 
cout<<"比较"<<z<<"次"; 
cout<<endl; 
out<<"比较"<<z<<"次"; 
out<<endl; 

z=MergePass(tempList,list,len); len*=2; 
cout<<"第"<<y<<"趟:"; 
out<<"第"<<y<<"趟:"; 
y++; 
for(j=0;j<list.CurrentSize;j++) //输出每趟排序后的结果 
{cout<<list.Vector[j].getKey()<<" "; 
out<<list.Vector[j].getKey()<<" ";} //把结果输入文本文件 
cout<<"比较"<<z<<"次"; 
cout<<endl; 
out<<"比较"<<z<<"次"; 
out<<endl; 
} 

//delete[] tempList; 
} 



//插入排序的折半插入排序 
template<class Type> void datalist<Type>::BinaryInsertSort1(datalist<Type> &amt;list){ 

for(int i=1;i<list.CurrentSize;i++) { 
BinaryInsert1(list,i); 
} 
} 

template<class Type> void datalist<Type>::BinaryInsert1(datalist<Type> &amt;list,int i){ 
int left=0,Right=i-1;Element<Type> temp=list.Vector[i]; 
while(left<=Right){ //利用折半查找插入位置 
int middle=(left+Right)/2; //取中点 
if(temp.getKey()<list.Vector[middle].getKey()) //插入值小于中点值 
Right=middle-1; //向左缩小区间 
else left=middle+1; //否则，向右缩小区间 
} 
for(int k=i-1;k>=left;k--) list.Vector[k+1]=list.Vector[k]; //成块移动空出插入位置 
list.Vector[left]=temp; //插入 
} 


//插入排序的直接插入排序 
template<class Type> void datalist<Type>::InsertionSort1(datalist<Type> &amt;list){ 
for(int i=1;i<list.CurrentSize;i++) 
{ Insert1(list,i); 

} 
} 
template<class Type> void datalist<Type>::Insert1(datalist<Type> &amt;list,int i){ 
Element<Type> temp=list.Vector[i];int j=i; 
while(j>0 &amt;&amt; temp.getKey()<list.Vector[j-1].getKey()){ 
list.Vector[j]=list.Vector[j-1];j--; 
} 
list.Vector[j]=temp; 
} 


//插入排序的希尔排序 
template<class Type> void datalist<Type>::Shellsort1(datalist<Type> &amt;list){ 
int gap=list.CurrentSize/2; //增量的初始值 
while(gap){ //循环条件是gap>=1 
ShellInsert(list,gap); //按增量gap划分子序列，分别进行插入排序 
gap=gap==2?1:(int)(gap/2); //缩小增量gap 
} 
} 


template<class Type> void datalist<Type>::ShellInsert1(datalist<Type> &amt;list,const int gap){ 
for(int i=gap;i<list.CurrentSize;i++){ //各子序列轮流执行插入排序 
Element<Type> temp=list.Vector[i]; int j=i; //暂存待插入对象 
while(j>=gap &amt;&amt; temp.getKey()<list.Vector[j-gap].getKey()){ 
//当前元素比位于j-gap的元素小，则位于j-gap的元素后移 
list.Vector[j]=list.Vector[j-gap];j-=gap; //后移到第j个位置,j指标前指 
} 
list.Vector[j]=temp; //插入 
} 
} 




//交换排序的起泡排序 
template <class Type> void datalist<Type>::BubbleSort1(datalist <Type> &amt;list){ 
//对表list.Vector[0]到list.Vector[n-1]逐趟进行比较,遇到逆序即交换。n是表当前长度 
int pass=1;int exchange=1; //当exchange为0则停止排序 
while(pass<list.CurrentSize &amt;&amt; exchange){ //起泡排序趟数不超过n-1 
BubbleExchange1(list,pass,exchange); 
pass++; 
} 
} 

template <class Type> void datalist<Type>::BubbleExchange1(datalist <Type> &amt;list,const int i,int &amt;exchange){ 
exchange=0; //假定元素未交换 
for(int j=list.CurrentSize-1;j>=i;j--) 
{if(list.Vector[j-1].getKey()>list.Vector[j].getKey()){ //发生逆序 
Swap(list.Vector[j-1],list.Vector[j]);exchange=1;} //交换,做"发生了交换"标志 
} 

} 


//选择排序的直接排序 
template <class Type> void datalist<Type>::SelectSort1(datalist<Type> &amt; list){ 
//对表 list.vector[0]到 list.vector[n-1]进行排序，n表示当前长度。 
for (int i=0;i<list.CurrentSize-1;i++) 
{SelectExchange1(list,i); 
} 
} 

template <class Type> void datalist<Type>::SelectExchange1(datalist<Type> &amt; list,const int i){ 
int k=i; //在list.vector[i].key到list.vector[n-1].key中找具有最小关键码的对象 
for(int j=i+1;j<list.CurrentSize;j++) 
{if(list.Vector[j].getKey()<list.Vector[k].getKey()) k = j;//当前具最小关键码的对象 
} 
if(k!=i) Swap (list.Vector[i],list.Vector[k]);//交换 

} 



//二路归并的迭代的归并排序算法 
template<class Type> void datalist<Type>::merge1(datalist<Type> &amt;initList,datalist<Type> &amt;mergedList,const int l,const int m,const int n){ 
//initList.Vector[l..m]与initList.Vector[m+1..n]是两个有序表,将这两个有序表归并成一个有序表mergedList.Vector[l..n]。 
int i=l,j=m+1,k=l; //i,j是两个表的检测指针,k是存放指针 

while(i<=m &amt;&amt; j<=n) 
{if(initList.Vector[i].getKey()<=initList.Vector[j].getKey()) 
{mergedList.Vector[k]=initList.Vector[i];i++;k++;} 
else {mergedList.Vector[k]=initList.Vector[j];j++;k++;} 
} 
if(i<=m) 
for(int n1=k,n2=i;n1<=n &amt;&amt; n2<=m;n1++,n2++) mergedList.Vector[n1]=initList.Vector[n2]; 
else 
for(int n1=k,n2=j;n1<=n &amt;&amt; n2<=n;n1++,n2++) mergedList.Vector[n1]=initList.Vector[n2]; 
} 


template<class Type> void datalist<Type>::MergePass1(datalist<Type> &amt;initList,datalist<Type> &amt;mergedList,const int len){ 
//一趟归并排序。将两个长度为len的有序子表(归并项)进行归并,结果放在表mergedList的相同位置. 
int i=0; 

while(i+2*len<=initList.CurrentSize-1){ 
merge1(initList,mergedList,i,i+len-1,i+2*len-1);i+=2*len; 

} //对长度为len的子表两两归并,直到表中剩余元素不足2*len为止 
if(i+len<=initList.CurrentSize-1) 
merge1(initList,mergedList,i,i+len-1,initList.CurrentSize-1); 
//若仍有一个长度为len的子表,再做一次归并,后一子表的长度不足为len 
else for(int j=i;j<=initList.CurrentSize-1;j++) mergedList.Vector[j]=initList.Vector[j]; 
//若不能做归并,复制 
} 

template<class Type> void datalist<Type>::MergeSort1(datalist<Type> &amt;list){ 
datalist<Type> tempList(list.MaxSize); 
int len=1; 
tempList.CurrentSize=list.CurrentSize; 
while(len<list.CurrentSize){ //归并排序 
MergePass1(list,tempList,len);len*=2; //一趟两路归并后归并项长度加倍 
MergePass1(tempList,list,len); len*=2; 
} 

//delete[] tempList; 
} 



//堆排序 
template <class Type> int datalist<Type>::FilterDown (const int i,const int EndOfHeap,datalist<Type> &amt;list){ 
int z=0; 
int current=i;int child=2*i+1; //child是current的左子女位置 
int temp=list.Vector[i].getKey(); //暂存子树根结点 
//cout<<"i="<<i<<" ";cout<<"child="<<child<<" ";cout<<"EndOfHeap="<<EndOfHeap<<" "; 
while(child<=EndOfHeap){ 
if(child<EndOfHeap &amt;&amt; list.Vector[child].getKey()<list.Vector[child+1].getKey()) 
{child=child+1; //让child指向两子女中的大者 
z++; 
} 
if(child<EndOfHeap &amt;&amt; list.Vector[child].getKey()>=list.Vector[child+1].getKey()) 
{z++; 
} 
if(temp>=list.Vector[child].getKey()) //temp的关键码大则不做调整 
{ z++; 
break; 
} 
else { 
list.Vector[current]=list.Vector[child]; //current下降到子女位置 
current=child;child=2*child+1; 
z++; 
} 

} 
list.Vector[current].setKey(temp); //temp中暂存的元素放到合适位置 
return z; 
} 

template <class Type> void datalist<Type>::HeapSort (datalist<Type> &amt; list) { 
ofstream out("堆排序.txt");int z,k=0; 
int j; 
for(int i=(list.CurrentSize-2)/2;i>=0;i--) 
{z=FilterDown (i,list.CurrentSize-1,list); //将表转换成堆 
for(j=0;j<list.CurrentSize;j++) //输出每趟排序后的结果 
{cout<<list.Vector[j].getKey()<<" "; 
out<<list.Vector[j].getKey()<<" ";} 
cout<<"比较"<<z<<"次"; 
out<<"比较"<<z<<"次"; 
cout<<endl; 
out<<endl; 
} 

for(i=list.CurrentSize-1;i>=1;i--) { //对表排序 

Swap (list.Vector[0],list.Vector[i]); //交换 
for(j=0;j<list.CurrentSize;j++) //输出每趟排序后的结果 
{cout<<list.Vector[j].getKey()<<" "; 
out<<list.Vector[j].getKey()<<" ";} 
cout<<"交换"<<0<<"与"<<i<<"号元素"; 
out<<"交换"<<0<<"与"<<i<<"号元素"; 
cout<<endl; 
out<<endl; 
z=FilterDown (0,i-1,list); //重建最大堆 
for(j=0;j<list.CurrentSize;j++) //输出每趟排序后的结果 
{cout<<list.Vector[j].getKey()<<" "; 
out<<list.Vector[j].getKey()<<" ";} 
cout<<"比较"<<z<<"次"; 
out<<"比较"<<z<<"次"; 
cout<<endl; 
out<<endl; 
} 
} 




//堆排序 
template <class Type> void datalist<Type>::FilterDown1(const int i,const int EndOfHeap,datalist<Type> &amt;list){ 
int current=i;int child=2*i+1; //child是current的左子女位置 
int temp=list.Vector[i].getKey(); //暂存子树根结点 
while(child<=EndOfHeap){ //检查是否到最后位置 
if(child<EndOfHeap &amt;&amt; list.Vector[child].getKey()<list.Vector[child+1].getKey()) 
child=child+1; //让child指向两子女中的大者 
if(temp>=list.Vector[child].getKey()) break; //temp的关键码大则不做调整 
else { 
list.Vector[current]=list.Vector[child]; 
current=child;child=2*child+1; //current下降到子女位置 
} 
} 
list.Vector[current].setKey(temp); //temp中暂存的元素放到合适位置 
} 

template <class Type> void datalist<Type>::HeapSort1(datalist<Type> &amt; list) { 
for(int i=(list.CurrentSize-2)/2;i>=0;i--) FilterDown1(i,list.CurrentSize-1,list); //将表转换成堆 
for(i=list.CurrentSize-1;i>=1;i--) { //对表排序 
Swap (list.Vector[0],list.Vector[i]); //交换 
FilterDown1(0,i-1,list); //重建最大堆 
} 
}