paixu.h

数据结构程序设计21

#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>& x){this->key=x.key;}
	   void operator =(const Type & x){key=x;}              //元素x的值赋给this

	   int operator == (const Element<Type> & x){return key<x.key == x.key<key;}        //判this与x相等
       int operator != (const Element<Type> & x){return key<x.key != x.key<key;}            //判this与x不等
	   int operator <= (const Element<Type> & x){return (key<=x.key);}                   //判this小于或等于x
	   int operator >= (const Element<Type> & x){return key>=x.key;}                   //判this大于或等于x
	   int operator < (const Element<Type> & x){return key<x.key;}                       //判this小于x
	   int operator > (const Element<Type> &x){return key>x.key;}
	   int operator !=(const int &x){return x!=key;}
	   friend ostream& operator <<(ostream &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> & x,Element <Type> & y)
		{Element <Type> temp=x;x=y;y=temp;}
		 void InsertionSort(datalist<Type> &list);
		 int Insert(datalist<Type> &list,int i);
		 void BubbleSort(datalist <Type> &list);
		 int BubbleExchange(datalist <Type> &list,const int i,int &exchange);
	     void Shellsort(datalist<Type> &list);
		 int ShellInsert(datalist<Type> &list,const int gap);
		 void QuickSort(datalist<Type> &list,const int left,const int right);
		 int Partition(datalist<Type> &list,const int low,const int high);
		 void SelectSort (datalist<Type> & list);
         int SelectExchange (datalist<Type> & list,const int i);
		 void BinaryInsertSort(datalist<Type> &list);
		 int BinaryInsert(datalist<Type> &list,int i);
		 void MergeSort(datalist<Type> &list);
		 int MergePass(datalist<Type> &initList,datalist<Type> &mergedList,const int len);
		 int merge(datalist<Type> &initList,datalist<Type> &mergedList,const int l,const int m,const int n);
		 int FilterDown (const int i,const int EndOfHeap,datalist<Type> &list);
		 void HeapSort (datalist<Type> & list);


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

};


//插入排序的折半插入排序
template<class Type> void datalist<Type>::BinaryInsertSort(datalist<Type> &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> &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> &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> &list,int i){
	int z=0;
	Element<Type> temp=list.Vector[i];int j=i;
	while(j>0 && temp.getKey()<list.Vector[j-1].getKey()){
		list.Vector[j]=list.Vector[j-1];j--;
	  z++;
	}
	if(j>0 && temp.getKey()>=list.Vector[j-1].getKey())
		z++;
	list.Vector[j]=temp;
	return z;
}


//插入排序的希尔排序
template<class Type> void datalist<Type>::Shellsort(datalist<Type> &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> &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 && 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 && temp.getKey()>=list.Vector[j-gap].getKey())
			z++;
         list.Vector[j]=temp;              //插入
      }
	return z;
 }





//交换排序的起泡排序
template <class Type> void datalist<Type>::BubbleSort(datalist <Type> &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 && 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> &list,const int i,int &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> &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> &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() && ++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> &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> &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() && ++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> & 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> & 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;//当前具最小关键码的对象
	  z++;