paixu.cpp

数据结构程序设计21

#include<iostream.h>
#include<stdlib.h>
#include<fstream.h>
#include <time.h> 
#include<cmath>
#include"paixu.h"
#include"paixu1.h"
#include"JBS.h"

int suiji(datalist <int> list);             
int jiaohu(datalist <int> list);
void memu(int x,datalist <int> list);
void memu1(datalist <int> list);
void main(){
		system("mode 125,450");                          //调整显示屏幕
     
	 cout<<"*****************************************************************"<<endl;
	 cout<<"*     组员：梁裕来、崔成发、梁志豪、张宇棠、陈榆                *"<<endl;
	 cout<<"*           欧文博、黎彦、廖育强、陈基、刘稳健                  *"<<endl;
	 cout<<"*****************************************************************"<<endl;
     

	 datalist<int> list;                  
	 datalist<int> list1;

	cout<<endl;
	cout<<"                         1.随机产生数"<<endl;
	cout<<"                         2.交互输入"<<endl;
	cout<<"                         3.退出"<<endl;
    cout<<"请输入你的选择:";
	int g,y;
here1:
	cin>>g;
		switch(g)
		{case 1:
	        y=suiji(list);
			memu(y,list);
			break;
	     case 2:
		    y=jiaohu(list);
			memu(y,list);
		    break;
	     case 3:
		    exit(1);
		 default:
	         cout<<"请输入正确的选择(1~3):";
	         goto here1;
	 
		}



}





int suiji(datalist <int> list){      //i为随机生成数的个数
	int i,j;
	cout<<"请输入要随机产生的数的个数(<=200):";
	cin>>i;
	int a[200];
	srand( (unsigned)time( NULL ) );
	for(j=0;j<i;j++)
	 a[j]=rand()%1000;	                         //随机生成数
	for(j=0;j<i;j++)
	{	list.Vector[j].setKey(a[j]);            //把随机生成的数赋给list.Vector[j]
	    list.CurrentSize=list.CurrentSize+1;
	}
	for(j=0;j<list.CurrentSize;j++)
	{cout<<list.Vector[j].getKey()<<" ";}
	cout<<endl;
	return list.CurrentSize;
} 



int jiaohu(datalist <int> list){
	int j;
	int a[200];
	cout<<"请输入你要排序的数(0结束):";
    for(j=0;;j++)
	{cin>>a[j];                              //交互输入数
	 if (a[j]!=0 )
     {   list.Vector[j].setKey(a[j]);           //把输入的数赋给list.Vector[j]
	     list.CurrentSize=list.CurrentSize+1;
		
	 }
	 else
        break;
	}

	for(j=0;j<list.CurrentSize;j++)
	{cout<<list.Vector[j].getKey()<<" ";           //输出list.Vector[j]里的数
	}
	cout<<endl;
	return list.CurrentSize;
}


void memu(int x,datalist <int> list){                          //排序菜单
here0:
	datalist <int> list1;
	staticlinklist <int> list2;
	list.CurrentSize=x;
	cout<<endl;
    cout<<"                      1.插入排序"<<endl;
	cout<<"                      2.交换排序"<<endl;
	cout<<"                      3.选择排序"<<endl;
	cout<<"                      4.归并排序"<<endl;
	cout<<"                      5.比较"<<endl;
	cout<<"                      6.退出"<<endl;
    cout<<"请输入你的选择:";
	int k;
	int i;
	int g;
here3:
	cin>>g;	
		switch(g){
		  case 1:
				 cout<<"              1.折半排序"<<endl;
				 cout<<"              2.直接排序"<<endl;
	             cout<<"              3.希尔排序"<<endl;
				 cout<<"              4.链表插入"<<endl;
				 cout<<"              5.返回上一层"<<endl;
				 cout<<"请输入你的选择:";
                 here2: 
				 cin>>k;   
					switch(k){
			                case 1:
                                   for(i=0;i<list.CurrentSize;i++)               //把list.Vector记录的数赋给list1.Vector
								   {list1.Vector[i].setKey(list.Vector[i].getKey());
								    list1.CurrentSize=list1.CurrentSize+1;
								   }
								   list1.BinaryInsertSort(list1);         //折半排序
								   break;
							case 2:
								   for(i=0;i<list.CurrentSize;i++)
								   {list1.Vector[i].setKey(list.Vector[i].getKey());
								    list1.CurrentSize=list1.CurrentSize+1;
								   }
								   list1.InsertionSort(list1);             //直接排序
								   break;
		                    case 3:
								   for(i=0;i<list.CurrentSize;i++)
								   {list1.Vector[i].setKey(list.Vector[i].getKey());
								    list1.CurrentSize=list1.CurrentSize+1;
								   }
								   list1.Shellsort(list1);                  //希尔排序
								   break;
                            case 4:								   
				 					for(i=1;i<=list.CurrentSize;i++)
								   {list2.Vector[i].setKey(list.Vector[i-1].getKey());
								    list2.CurrentSize=list2.CurrentSize+1;
								   }
		  						   list2.LinkInsertSort(list2);             //链表插入
				                   break;
							case 5:
								goto here0;
							default:
				                   cout<<"请输入1~5的数:";
					               goto here2;
					}
				 break;

		  case 2:
			     cout<<"              1.起泡排序"<<endl;
				 cout<<"              2.快速排序"<<endl;
				 cout<<"              3.返回上一层"<<endl;
				 cout<<"请输入你的选择:";
                 here4:
				 cin>>k;  
					 switch(k){
					 case 1:
                            for(i=0;i<list.CurrentSize;i++)
							{list1.Vector[i].setKey(list.Vector[i].getKey());
							 list1.CurrentSize=list1.CurrentSize+1;
							 }
							 list1.BubbleSort(list1);              //起泡排序
							 break;
					 case 2:
						    for(i=0;i<list.CurrentSize;i++)
							{list1.Vector[i].setKey(list.Vector[i].getKey());
							 list1.CurrentSize=list1.CurrentSize+1;
							 }
							list1.ci=0;
							list1.QuickSort(list1,0,list1.CurrentSize-1);        //快速排序
							break;
					 case 3:
						 goto here0;
					 default:
						     cout<<"请输入1~3的数:";
				             goto here4;
					 }
				 break;
		  case 3:
				 cout<<"              1.直接选择排序"<<endl;
				 cout<<"              2.堆排序"<<endl;
	             cout<<"              3.锦标赛排序"<<endl;
				 cout<<"              4.返回上一层"<<endl;
				 cout<<"请输入你的选择:";
                 here5:
				 cin>>k;   
					 switch(k){
					 case 1:
                            for(i=0;i<list.CurrentSize;i++)
							{list1.Vector[i].setKey(list.Vector[i].getKey());
							 list1.CurrentSize=list1.CurrentSize+1;
							 }
							 list1.SelectSort(list1);                     //直接选择排序
							 break;
					 case 2:
						    for(i=0;i<list.CurrentSize;i++)
							{list1.Vector[i].setKey(list.Vector[i].getKey());
							 list1.CurrentSize=list1.CurrentSize+1;
							 }
							list1.HeapSort(list1);                      //堆排序
							break;
					 case 3:
						 cout<<"---------------特别鸣谢：黄锦洪---------------"<<endl;
						 cout<<"----------二叉树算法由黄锦洪友情赞助----------"<<endl;
						    for(i=0;i<list.CurrentSize;i++)
							{list1.Vector[i].setKey(list.Vector[i].getKey());
							 list1.CurrentSize=list1.CurrentSize+1;
							 }
						    TournamentSort(list1.Vector,list1.CurrentSize,true);      //锦标赛排序
							printResult(list1.Vector,list1.CurrentSize);
							break;
					 case 4:
						 goto here0;
                     default:
						    cout<<"请输入1~3的数:";
				             goto here5;
					 }
				 break;
		case 4:
			   cout<<"              1.迭代排序算法"<<endl;
			   cout<<"              2.返回上一层"<<endl;
			   cout<<"请输入你的选择:"; 
               here6:
			   cin>>k;   
					 switch(k){
					 case 1:
                            for(i=0;i<list.CurrentSize;i++)
							{list1.Vector[i].setKey(list.Vector[i].getKey());
							 list1.CurrentSize=list1.CurrentSize+1;
							 }
							 list1.MergeSort(list1);                        //迭代排序算法
							 break;
					 case 2:
						 goto here0;
                     default:
						    cout<<"请输入1~2:";
				             goto here6;
					 }
				 break;				 
		
		case 5:
			  cout<<"            1.插入排序的折半排序"<<endl;
              cout<<"            2.插入排序的直接排序"<<endl;
			  cout<<"            3.插入排序的希尔排序"<<endl;
			  cout<<"            4.插入排序的链表插入"<<endl;
   	          cout<<"            5.交换排序的起泡排序"<<endl;
			  cout<<"            6.交换排序的快速排序"<<endl;
	          cout<<"            7.选择排序的直接选择排序"<<endl;
			  cout<<"            8.选择排序堆排序"<<endl;
			  cout<<"            9.选择排序锦标赛排序"<<endl;
	          cout<<"            10.二路归并的迭代排序"<<endl;
			  cout<<"            11.退出"<<endl;
              memu1(list);
              memu1(list);



		case 6:
			  exit(1);
	     
	
	
	      default:
	            cout<<"请输入1~6的数:";
	            goto here3;
	  }
	

goto here0;
}






void memu1(datalist <int> list)                          //比较菜单,用运行时间比较
{    datalist <int> list1;
     staticlinklist <int> list2;
     int i;
     for(i=0;i<list.CurrentSize;i++)
	{list1.Vector[i].setKey(list.Vector[i].getKey());
	list1.CurrentSize=list1.CurrentSize+1;
	}


			  int y;
			  int d;
			  long int t=100000;
			  double start,finish;
			  double time1;
			 
			  
			  
            here7:
			  cout<<endl<<"请要输入要比较的算法:";
			  
			  cin>>y;

              switch(y){
			     case 1:
					 start=clock();        //开始运行的时间
					 for(d=0;d<t;d++)
					 list1.BinaryInsertSort1(list1);
					 finish=clock();       //结束运行的时间
                     time1=(double)(finish-start)/t;    //排序总耗费的时间
					   cout<<"折半排序算法运行时间:"<<time1<<"ms";
					   goto here7;
				 case 2:
					 start=clock();        //开始运行的时间
					 for(d=0;d<t;d++)
					 list1.InsertionSort1(list1);
					 finish=clock();       //结束运行的时间
                     time1=(double)(finish-start)/t;    //排序总耗费的时间
					   cout<<"直接排序算法运行时间:"<<time1<<"ms";
					   goto here7;
                 case 3:
                     start=clock();        //开始运行的时间
					 for(d=0;d<t;d++)
					 list1.Shellsort1(list1);
					 finish=clock();       //结束运行的时间
                     time1=(double)(finish-start)/t;    //排序总耗费的时间
					   cout<<"希尔排序算法运行时间:"<<time1<<"ms";
					   goto here7;
				 case 4:
					 for(i=1;i<=list.CurrentSize;i++)
					{list2.Vector[i].setKey(list.Vector[i-1].getKey());
	                 list2.CurrentSize=list2.CurrentSize+1;
					}
                     start=clock();        //开始运行的时间
					 for(d=0;d<t;d++)
					 list1.Shellsort1(list1);
					 finish=clock();       //结束运行的时间
                     time1=(double)(finish-start)/t;    //排序总耗费的时间
					   cout<<"链表插入算法运行时间:"<<time1<<"ms";
					   goto here7;

				 case 5: 
					 start=clock();
					 for(d=0;d<t;d++)
					 list1.BubbleSort1(list1);
					 finish=clock();
                     time1=(double)(finish-start)/t;
                       cout<<"起泡排序算法运行时间:"<<time1<<"ms";
					   goto here7;
				 case 6:
					 start=clock();
					 for(d=0;d<t;d++)
					 list1.QuickSort1(list1,0,list1.CurrentSize-1);
					 finish=clock();
                     time1=(double)(finish-start)/t;
                       cout<<"快速排序算法运行时间:"<<time1<<"ms";
					   goto here7;
				 
				 case 7: 
					 start=clock();
					 for(d=0;d<t;d++)
					 list1.SelectSort1(list1);
					 finish=clock();
                     time1=(double)(finish-start)/t;
                     cout<<"直接选择排序算法运行时间:"<<time1<<"ms";
					 goto here7;
                 case 8:
					 start=clock();
					 for(d=0;d<t;d++)
					 list1.HeapSort1(list1);
					 finish=clock();
                     time1=(double)(finish-start)/t;
                     cout<<"堆排序算法运行时间:"<<time1<<"ms";
					 goto here7;
				 case 9:
					 start=clock();        //开始运行的时间
		             for(d=0;d<t;d++)
			         TournamentSort(list1.Vector,list1.CurrentSize,false);
		             finish=clock();       //结束运行的时间
					 time1=(double)(finish-start)/t;    //排序总耗费的时间
		             cout<<"锦标赛排序算法运行时间:"<<time1<<"ms";
					 goto here7;
				 case 10: 
					 start=clock();
					 for(d=0;d<t;d++)
					  list1.MergeSort1(list1);
					 finish=clock();
                     time1=(double)(finish-start)/t;
					  cout<<"二路归并的迭代排序算法运行时间:"<<time1<<"ms";
					 goto here7;
				 case 11:
					 exit(1);
				 default: 
					 cout<<"请输入1~11的数"<<endl;
					 goto here7;
			  }
			  cout<<endl;
			 
}