paixu.h.txt

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

www.pudn.com > asd.rar > paixu.h


#include<fstream.h> 
const int DefaultSize=200; 
template <class Type> class datalist; //数据表的前视声明 
template <class Type> class Element{ //数据表元素类的定义 
friend class datalist<Type>; 
private: 
Type key; //关键码 
public: 
Type getKey(){return key;} //取当前结点的关键码 
void setKey(const Type x) {key=x;} //将当前结点的关键码修改为x 
void setInt(int x){key=x;} 
Element() 
{ 
key=0; 
} 


void operator = (Element<Type>&amt; x){this->key=x.key;} 
void operator =(const Type &amt; x){key=x;} //元素x的值赋给this 

int operator == (const Element<Type> &amt; x){return key<x.key == x.key<key;} //判this与x相等 
int operator != (const Element<Type> &amt; x){return key<x.key != x.key<key;} //判this与x不等 
int operator <= (const Element<Type> &amt; x){return (key<=x.key);} //判this小于或等于x 
int operator >= (const Element<Type> &amt; x){return key>=x.key;} //判this大于或等于x 
int operator < (const Element<Type> &amt; x){return key<x.key;} //判this小于x 
int operator > (const Element<Type> &amt;x){return key>x.key;} 
int operator !=(const int &amt;x){return x!=key;} 
friend ostream&amt; operator <<(ostream &amt;out,Element<Type> x) 
{ 
out<<x.key; 
return out; 
} 


}; 

template <class Type> class datalist{ //用顺序表来存储待排序的元素,这些元素的类型是Type 
friend int suiji(datalist <int> list); 
friend int jiaohu(datalist <int> list); 
friend void shuchu(int x,datalist <int> list); 
//friend int memu(int x,datalist <int> list); 
friend void memu(int x,datalist <int> list); 
friend void memu1(datalist <int> list); 
public: 
int ci; 
datalist(int MaxSz=DefaultSize) : MaxSize(MaxSz),CurrentSize(0) 
{Vector=new Element <Type> [MaxSz];} 
void Swap(Element <Type> &amt; x,Element <Type> &amt; y) 
{Element <Type> temp=x;x=y;y=temp;} 
void InsertionSort(datalist<Type> &amt;list); 
int Insert(datalist<Type> &amt;list,int i); 
void BubbleSort(datalist <Type> &amt;list); 
int BubbleExchange(datalist <Type> &amt;list,const int i,int &amt;exchange); 
void Shellsort(datalist<Type> &amt;list); 
int ShellInsert(datalist<Type> &amt;list,const int gap); 
void QuickSort(datalist<Type> &amt;list,const int left,const int right); 
int Partition(datalist<Type> &amt;list,const int low,const int high); 
void SelectSort (datalist<Type> &amt; list); 
int SelectExchange (datalist<Type> &amt; list,const int i); 
void BinaryInsertSort(datalist<Type> &amt;list); 
int BinaryInsert(datalist<Type> &amt;list,int i); 
void MergeSort(datalist<Type> &amt;list); 
int MergePass(datalist<Type> &amt;initList,datalist<Type> &amt;mergedList,const int len); 
int merge(datalist<Type> &amt;initList,datalist<Type> &amt;mergedList,const int l,const int m,const int n); 
int FilterDown (const int i,const int EndOfHeap,datalist<Type> &amt;list); 
void HeapSort (datalist<Type> &amt; list); 


void InsertionSort1(datalist<Type> &amt;list); 
void Insert1(datalist<Type> &amt;list,int i); 
void BinaryInsertSort1(datalist<Type> &amt;list); 
void BinaryInsert1(datalist<Type> &amt;list,int i); 
void BubbleSort1(datalist <Type> &amt;list); 
void BubbleExchange1(datalist <Type> &amt;list,const int i,int &amt;exchange); 
void Shellsort1(datalist<Type> &amt;list); 
void ShellInsert1(datalist<Type> &amt;list,const int gap); 
void QuickSort1(datalist<Type> &amt;list,const int left,const int right); 
int Partition1(datalist<Type> &amt;list,const int low,const int high); 
void SelectSort1(datalist<Type> &amt; list); 
void SelectExchange1(datalist<Type> &amt; list,const int i); 
void MergeSort1(datalist<Type> &amt;list); 
void MergePass1(datalist<Type> &amt;initList,datalist<Type> &amt;mergedList,const int len); 
void merge1(datalist<Type> &amt;initList,datalist<Type> &amt;mergedList,const int l,const int m,const int n); 
void HeapSort1(datalist<Type> &amt; list); 
void FilterDown1(const int i,const int EndOfHeap,datalist<Type> &amt;list); 
private: 
Element <Type> * Vector; //存储待排序元素的向量 
int MaxSize, CurrentSize,size; //向量中最大元素个数与当前元素个数 

}; 


//插入排序的折半插入排序 
template<class Type> void datalist<Type>::BinaryInsertSort(datalist<Type> &amt;list){ 
int z; //用z来记录每趟的比较数 
ofstream out("折半插入排序.txt"); 
for(int i=1;i<list.CurrentSize;i++) { 
z=BinaryInsert(list,i); 
cout<<"第"<<i<<"趟:"; 
out<<"第"<<i<<"趟:"; 
for(int 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> int datalist<Type>::BinaryInsert(datalist<Type> &amt;list,int i){ 
int z=0; //用z来计算比较次数 
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; //否则，向右缩小区间 
z++; 
} 
for(int k=i-1;k>=left;k--) list.Vector[k+1]=list.Vector[k]; //成块移动空出插入位置 
list.Vector[left]=temp; //插入 
return z; 
} 


//插入排序的直接插入排序 
template<class Type> void datalist<Type>::InsertionSort(datalist<Type> &amt;list){ 
int z; 
ofstream out("直接插入排序.txt"); 
for(int i=1;i<list.CurrentSize;i++) 
{ z=Insert(list,i); 
cout<<"第"<<i<<"趟:"; 
out<<"第"<<i<<"趟:"; 
for(int 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> int datalist<Type>::Insert(datalist<Type> &amt;list,int i){ 
int z=0; 
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--; 
z++; 
} 
if(j>0 &amt;&amt; temp.getKey()>=list.Vector[j-1].getKey()) 
z++; 
list.Vector[j]=temp; 
return z; 
} 


//插入排序的希尔排序 
template<class Type> void datalist<Type>::Shellsort(datalist<Type> &amt;list){ 
ofstream out("希尔排序.txt");int i=0,z; 
int gap=list.CurrentSize/2; //增量的初始值 

while(gap){ //循环条件是gap>=1 
z=ShellInsert(list,gap); //按增量gap划分子序列，分别进行插入排序 
gap=gap==2?1:(int)(gap/2); //缩小增量gap 
i++; 
cout<<"第"<<i<<"趟:"; 
out<<"第"<<i<<"趟:"; 
for(int 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> int datalist<Type>::ShellInsert(datalist<Type> &amt;list,const int gap){ 
int z=0; 
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指标前指 
z++; 
} 
if(j>=gap &amt;&amt; temp.getKey()>=list.Vector[j-gap].getKey()) 
z++; 
list.Vector[j]=temp; //插入 
} 
return z; 
} 





//交换排序的起泡排序 
template <class Type> void datalist<Type>::BubbleSort(datalist <Type> &amt;list){ 
ofstream out("起泡排序.txt"); 
//对表list.Vector[0]到list.Vector[n-1]逐趟进行比较,遇到逆序即交换。n是表当前长度 
int pass=1;int exchange=1; int z; //当exchange为0则停止排序,z来记录每躺比较次数 
while(pass<list.CurrentSize &amt;&amt; exchange){ //起泡排序趟数不超过n-1 
z=BubbleExchange(list,pass,exchange); 
cout<<"第"<<pass<<"趟:"; 
out<<"第"<<pass<<"趟:"; 
for(int j=0;j<list.CurrentSize;j++) //输出每趟排序后的结果 
{cout<<list.Vector[j].getKey()<<" "; 
out<<list.Vector[j].getKey()<<" ";} //把结果输入文本文件 
cout<<"比较:"<<z<<"次"; 
cout<<endl; 
out<<"比较"<<z<<"次"; 
out<<endl; 
pass++; 
} 
} 

template <class Type> int datalist<Type>::BubbleExchange(datalist <Type> &amt;list,const int i,int &amt;exchange){ 
exchange=0; int z=0; //假定元素未交换,z来计算比较次数 
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;} //交换,做"发生了交换"标志 
z++; 
} 
return z; 
} 

//交换排序的快速排序 

ofstream out2("快速排序.txt"); 
template<class Type> void datalist<Type>::QuickSort(datalist<Type> &amt;list,const int left,const int right){ 
if(left<right){ 
int pivotpos=Partition(list,left,right); 
QuickSort(list,left,pivotpos-1); //对左侧子序列施行划分 
QuickSort(list,pivotpos+1,right); //对右侧子序列施行划分 
} 
} 

template<class Type> int datalist<Type>::Partition(datalist<Type> &amt;list,const int low,const int high){ 
int pivotpos=low;Element<Type> pivot=list.Vector[low]; 

for(int i=low+1;i<=high;i++) 
{ if(list.Vector[i].getKey()<pivot.getKey() &amt;&amt; ++pivotpos !=i)//算法中执行一个循环，只要是关键码小于基准对象关键码的对象 
//都移动序列左侧，关键码大于基准对象关键码的对象都移动序列右侧 
{ Swap(list.Vector[pivotpos],list.Vector[i]); 
} 
} 
Swap(list.Vector[low],list.Vector[pivotpos]);//基准对象安放到位 
int k; 
if(ci<=list.CurrentSize)//输出每趟结果 
{ 
cout<<"第"<<ci+1<<"趟结果:"; 
out2<<"第"<<ci+1<<"趟结果:"; 
for(k=0;k<list.CurrentSize;k++) 
{ cout<<list.Vector[k].getKey()<<" "; 
out2<<list.Vector[k].getKey()<<" "; 
} 
cout<<endl; 
out2<<endl; 
} 
ci++; 

return pivotpos;//返回基准对象位置 
} 




//交换排序的快速排序 
template<class Type> void datalist<Type>::QuickSort1(datalist<Type> &amt;list,const int left,const int right){ 

if(left<right){ 
int pivotpos=Partition1(list,left,right); 
QuickSort1(list,left,pivotpos-1); 
QuickSort1(list,pivotpos+1,right); 
} 
} 

template<class Type> int datalist<Type>::Partition1(datalist<Type> &amt;list,const int low,const int high){ 
int pivotpos=low;Element<Type> pivot=list.Vector[low]; 

for(int i=low+1;i<=high;i++) 
{ if(list.Vector[i].getKey()<pivot.getKey() &amt;&amt; ++pivotpos !=i) 
{ Swap(list.Vector[pivotpos],list.Vector[i]); 
} 
} 
Swap(list.Vector[low],list.Vector[pivotpos]); 

return pivotpos; 
} 




//选择排序的直接排序 
template <class Type> void datalist<Type>::SelectSort (datalist<Type> &amt; list){ 
//对表 list.vector[0]到 list.vector[n-1]进行排序，n表示当前长度。 
ofstream out("直接排序.txt"); 
int z; //z来记录每躺比较次数 
for (int i=0;i<list.CurrentSize-1;i++) 
{z=SelectExchange(list,i); 
cout<<"第"<<i<<"趟:"; 
out<<"第"<<i<<"趟:"; 
for(int j=0;j<list.CurrentSize;j++) //输出每趟排序后的结果 
{cout<<list.Vector[j].getKey()<<" "; 
out<<list.Vector[j].getKey()<<" ";} //把结果输入文本文件 
cout<<"比较"<<z<<"次"; 
cout<<endl; 
out<<"比较"<<z<<"次"; 
out<<endl; 

} 
} 

template <class Type> int datalist<Type>::SelectExchange (datalist<Type> &amt; list,const int i){ 
int k=i; //在list.vector[i].key到list.vector[n-1].key中找具有最小关键码的对象 
int z=0; //z来计算比较次数 
for(int j=i+1;j<list.CurrentSize;j++) 
{if(list.Vector[j].getKey()<list.Vector[k].getKey()) k = j;//当前具最小关键码的对象