paixu.cpp.txt

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

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


#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; 

}