数据结构 实验的所有代码

#include <iostream> #include<stdlib.h>//使用库函数srand ,rand() #include<time.h>//time函数用于返回某一特定时间的小数值 using namespace std; const int Max=10;//最大值为10 void Creat(int r[],int n);//生成待排序记录 void InsertSort(int r[],int n);//直接插入排序 void ShellSort(int r[],int n);//希尔排序 void BubbleSort(int r[],int n);//起泡排序 int Partition(int r[],int first,int end);//一次排序 void QuickSort(int r[],int first,int end);//快速排序 void SelectSort(int r[],int n);//简单选择排序 void Sift(int r[],int k,int m);//筛选法调整堆 void HeapSort(int r[],int n);//堆排序 int main() { int a[Max+1]= {0},b[Max+1]= {0}; //初始化大小为Max+1的int类型数组，其中元素默认值为0 int i=0; Creat(a,Max); for(i=1; i<=Max; i++) b[i]=a[i];//将数组a复制一份到b cout<<"Disordered sequence:";//无序序列为 for(i=1; i<=Max; i++) cout<<b[i]<<" ";//输出无序序列 cout<<endl; cout<<"1.Shell sorting"<<endl;//希尔排序 cout<<"2.Insert directly into the order"<<endl;//直接插入排序序列为 cout<<"3.BubbleSort"<<endl;//起泡排序 cout<<"4.QuickSort"<<endl;//快速排序 cout<<"5.SelectSort"<<endl;//简单选择排序 cout<<"6.HeapSort"<<endl;//堆排序 int h; while(cin>>h&&h!=0) { switch(h) { case 1: ShellSort(a,Max); for(i=1; i<=Max; i++) cout<<a[i]<<" ";////希尔排序为 cout<<endl; break; case 2: InsertSort(b,Max); for(i=1; i<=Max; i++) cout<<a[i]<<" ";//输出直接插入排序序列 cout<<endl; break; case 3: BubbleSort(b,Max); for(i=1; i<=Max; i++) cout<<b[i]<<" ";////希尔排序为 cout<<endl; break; case 4: QuickSort(a,1,Max); for(i=1; i<=Max; i++) cout<<a[i]<<" ";////希尔排序为 cout<<endl; break; case 5: SelectSort(b,Max); for(i=1; i<=Max; i++) cout<<b[i]<<" ";////希尔排序为 cout<<endl; break; case 6: HeapSort(a,Max); for(i=1; i<=Max; i++) cout<<a[i]<<" ";////希尔排序为 cout<<endl; break; default: cout<<"Please enter a valid number:"<<endl; break; } } return 0; } void Creat(int r[],int n) { int i=0; srand(time(NULL));//是以当前时间为种子，产生随意数。 for(i=1; i<=n; i++) r[i]=1+rand()%100;//从数组下标1开始存放 } void InsertSort(int r[],int n) { int i,j; for( i=2; i<=n; i++)//0号单元为暂存单元和监哨 { r[0]=r[i];//设置哨兵 for( j=i-1; r[0]<r[j]; j--)//寻找插入位置 { r[j+1]=r[j]; //记录后移 } r[j+1]=r[0];//j+1位正确的插入位置 } } void ShellSort(int r[],int n) { int j; for(int d=n/2; d>=1; d=d/2)//增量为d { for(int i=d+1; i<=n; i++) { r[0]=r[i];//暂存被插入记录 for(j=i-d; j>0&&r[0]<r[j]; j=j-d) r[j+d]=r[j];//记录后移 r[j+d]=r[0]; } } } void BubbleSort(int r[],int n)//起泡排序 { int exchange=n,bound=n; while(exchange!=0)//第一趟排序的区间是1~n { bound=exchange;exchange=0; for(int j=1;j<bound;j++)//当上一趟排序有交换记录时 if(r[j]>r[j+1]) { r[0]=r[j];//0暂存j的位置 r[j]=r[j+1]; r[j+1]=r[0]; exchange=j;//记录每一次交换的位置 } } } int Partition(int r[],int first,int end)//一次排序 { int i=first,j=end; while(i<j)//右侧扫描 { while(i<j&&r[i]<=r[j])j--; if(i<j) { r[0]=r[i];//0zancunj的位置 r[i]=r[j]; r[j]=r[0]; i++; } while(i<j&&r[i]<=r[j])i++;//左侧扫描 if(i<j) { r[0]=r[i];//0zancunj的位置 r[i]=r[j]; r[j]=r[0]; j--; } } return i; } void QuickSort(int r[],int first,int end)//快速排序 { if(first<end)//区间长度》1，执行一次划分，否则递归结束 { int pivot=Partition(r,first,end);//一次划分 QuickSort(r,first,pivot-1);//递归的对左边进行快速排序 QuickSort(r,pivot+1,end);//递归的对左边进行快速排序 } } void SelectSort(int r[],int n)//简单选择排序 { for(int i=1;i<n;i++)//对n个记录进行n-1趟排序 { int index=i; for(int j=i+1;j<=n;j++) if(r[j]<r[index])index=j;//在无序区间找一个最小记录 if(index!=i) { r[0]=r[i];//0暂存j的位置 r[i]=r[index]; r[index]=r[0]; } } } void Sift(int r[],int k,int m)//筛选法调整堆 { int i=k,j=2*i;//i为被筛选的节点，j为i的左孩子 while(j<=m)//筛选还没有进行到叶子 { if(j<m&&r[j]<=r[j+1])j++;//比较1的左右孩子，j指向较大者 if(r[i]>r[j])break; else { r[0]=r[i];//0zancunj的位置 r[i]=r[j];//根节点与j交换 r[j]=r[0]; i=j; j=2*i;//被筛选节点为原来j的位置 } } } void HeapSort(int r[],int n)//堆排序 { int i=0; for(i=n/2;i>=1;i--)//初始建队，从最后一个分支节点到根节点1 Sift(r,i,n); for(i=1;i<n;i++)//重复执行一走堆顶和重建堆的操作 { r[0]=r[1];//0zancunj的位置 r[1]=r[n-i+1];//根节点与j交换 r[n-i+1]=r[0]; Sift(r,1,n-i); } }