实验六    查找与排序

一、实验目的：

1．理解掌握查找与排序在计算机中的各种实现方法。

2．学会 针对 所给问题选用最适合的算法。

3．熟练掌握常用排序算法在顺序表上的实现。
二、实验要求：

掌握利用常用的查找排序算法的思想来解决一般问题的方法和技巧，进行算法分析并写出实习报告。

三、实验内容及分析：

设计一个学生信息管理系统，学生对象至少要包含：学号、性别、成绩1、成绩总成绩等信息。要求实现以下功能：

1．平均成绩要求自动计算；

2．查找：分别给定学生学号、性别，能够查找到学生的基本信息（要求至少用两种查找算法实现）；

3．  排序：分别按学生的学号、成绩1、成绩2、平均成绩进行排序（要求至少用两种排序算法实现）。

四、程序的调试及运行结果

五、程序代码

#include<stdio.h>

#include<string.h>

struct student//定义结构体

{

       char name[30];

       int a1,a2,a3,num;

       double pow;

}zl[100];

int count=0;

void jiemian1(); //主界面//函数声明

int jiemian2();  //选择界面

void luru();  //录入函数

void xianshi();  //显示

void paixv();  //排序

void diaoyong(int); //循环调用选择界面

void tianjia();  //添加信息

void chaxun1();  //按学号查询详细信息

void chaxun2();  //按姓名查询详细信息

void xiugai();  //修改信息

void shanchu();  //删除信息

void main()     //main函数

{

       jiemian1();//函数点用

}

void jiemian1()    //主界面定义

{

       char a;

       printf("\n\n\n\n\t\t\t学  员  信  息  管  理  器\n\n\n\t\t\t  数据结构课程设计练习六 \n\n\n\t\t\t   09信计2:于学彬\n\n");

       printf("\n\t\t\t   按回车键继续:");

       scanf("%c",&a);

       system("cls");

       jiemian2();

}

int jiemian2()    //选择界面

{

       int a,b;

       printf("*******************************主   要   功   能********************************");

       printf("\n\n\n\n\t\t\t\t1.录入信息\n\n\t\t\t\t2.添加信息\n\n\t\t\t\t3.查看信息\n\n\t\t\t\t4.查询信息\n\n\t\t\t\t5.修改信息\n\n\t\t\t\t6.删除信息\n\n\t\t\t\t7.退  出\n\n\t\t\t\t请选择:");

       scanf("%d",&a);

       switch(a)

       {

              case 1:system("cls");luru();break;

              case 2:system("cls");tianjia();break;

              case 3:system("cls");paixv();break;

              case 4:system("cls");

                       printf("1.按学号查询详细信息\n2.按姓名查询详细信息\n请选择:");

                       scanf("%d",&b);

                       switch(b)

                       {

                              case 1:system("cls");chaxun1();break;

                              case 2:system("cls");chaxun2();break;

                           }  break;

             case 5:system("cls");xiugai();break;

             case 6:system("cls");shanchu();break;

             case 7:system("cls");return a;break;

       }

}

void diaoyong(int b)  //循环调用选择界面

{

       char a='y';

       printf("是否返回选择页(y/n):");

       fflush(stdin);//清空输入缓冲区，通常是为了确保不影响后面的数据读取（例如在读完一个字符串后紧接着又要读取一个字符，此时应该先执行fflush(stdin);)

       a=getchar();

       system("cls");

       while(a=='y'||a=='Y')

       {

             b=jiemian2();

             if(b==7)

             {

                   break;

             }

 

       }

}

void luru()     //录入函数

{

       char a;//='y';

       do

       {

             printf("请输入学员信息:\n");

             printf("学号:");

             scanf("%d",&zl[count].num);//调用结构体

             printf("姓名:");

            fflush(stdin);

             gets(zl[count].name);

             printf("三门成绩:\n");

             printf("成绩1:");

             scanf("%d",&zl[count].a1);

             printf("成绩2:");

            scanf("%d",&zl[count].a2);

             printf("成绩3:");

             scanf("%d",&zl[count].a3);

             zl[count].pow=(zl[count].a1+zl[count].a2+zl[count].a3)/3;//求平均数

             printf("是否继续(y/n):");

             fflush(stdin);

             a=getchar();

             count++;

             system("cls");

       }

       while(a=='y'&&count<100);

             

              //paixv();

              diaoyong(count);

}

void tianjia()    //添加信息

{

       char a='y';

       do

       {

              printf("请输入学员信息:\n");

              printf("学号:");

              scanf("%d",&zl[count].num);

              printf("姓名:");

              //fflush(stdin);

              gets(zl[count].name);

              printf("三门成绩:\n");

              printf("成绩1:");

              scanf("%d",&zl[count].a1);

              printf("成绩2:");

              scanf("%d",&zl[count].a2);

              printf("成绩3:");

              scanf("%d",&zl[count].a3);

              zl[count].pow=(zl[count].a1+zl[count].a2+zl[count].a3)/3;

              printf("是否继续(y/n):");

              //fflush(stdin);

              a=getchar();

              count++;

              system("cls");

       }

       while(a=='y'&&count<100);

              paixv(count);

              diaoyong(count);

}

void xianshi()    //显示

{

       int i;

       printf("学号\t  \t姓名\t\t\t平均成绩\n");

       for(i=0;i<count;i++)

       {

             printf("%d\t   \t%s\t\t\t%f\n",zl[i].num,zl[i].name,zl[i].pow);

       }

}

void paixv()    //排序

{

       int i,j;

       struct student zl1;

       printf("排序前:\n");

       xianshi();

       for(i=0;i<count;i++)

       {

             for(j=1;j<count-i;j++)

             {

                   if(zl[j-1].pow<zl[j].pow)

                   {

                         zl1=zl[j-1];

                         zl[j-1]=zl[j];

                         zl[j]=zl1;

                   }

             }

       }

       printf("排序后:\n");

       xianshi();

       diaoyong(count);

}

void chaxun1()    //按学号查询详细信息

{

       int i,num;

       printf("请输入要查询学员的学号:");

       scanf("%d",&num);

       printf("学号\t姓名\t成绩1\t成绩2\t成绩3\t平均成绩\n");

       for(i=0;i<count;i++)

       {

             if(zl[i].num==num)

             {

                   printf("%d\t%s\t%d\t%d\t%d\t%.2f\n",zl[i].num,zl[i].name,zl[i].a1,zl[i].a2,zl[i].a3,zl[i].pow);

             }

       }

       diaoyong(count);

}

void chaxun2()    //按姓名查询详细信息

{

       int i;

       struct student zl1;

       printf("请输入要查询学员的姓名:");

       fflush(stdin);

       gets(zl1.name);

       printf("学号\t姓名\t成绩1\t成绩2\t成绩3\t平均成绩\n");

       for(i=0;i<count;i++)

       {

             if((strcmp(zl[i].name,zl1.name))==0)//比较两个字符串的大小

             {

                   printf("%d\t%s\t%d\t%d\t%d\t%.2f\n",zl[i].num,zl[i].name,zl[i].a1,zl[i].a2,zl[i].a3,zl[i].pow);

             }

       }

       diaoyong(count);

}

void xiugai()    //修改信息

{

       int i,num;

       printf("请输入要查询学员的学号:");

       scanf("%d",&num);

       printf("学号\t姓名\t成绩1\t成绩2\t成绩3\t平均成绩\n");

       for(i=0;i<count;i++)

       {

             if(zl[i].num==num)

             {

                   break;

             }

       }

       printf("%d\t%s\t%d\t%d\t%d\t%.2f\n",zl[i].num,zl[i].name,zl[i].a1,zl[i].a2,zl[i].a3,zl[i].pow);

       printf("请输入学员信息:\n");

       printf("学号:");

       scanf("%d",&zl[i].num);

       printf("姓名:");

       fflush(stdin);

       gets(zl[i].name);

       printf("三门成绩:\n");

       printf("成绩1:");

       scanf("%d",&zl[i].a1);

       printf("成绩2:");

       scanf("%d",&zl[i].a2);

       printf("成绩3:");

       scanf("%d",&zl[i].a3);

       zl[i].pow=(zl[i].a1+zl[i].a2+zl[i].a3)/3;

       printf("学号\t姓名\t成绩1\t成绩2\t成绩3\t平均成绩\n");

       printf("%d\t%s\t%d\t%d\t%d\t%.2f\n",zl[i].num,zl[i].name,zl[i].a1,zl[i].a2,zl[i].a3,zl[i].pow);

       diaoyong(count);

}

void shanchu()    //删除信息

{

       int num,i,j;

       printf("请输入要删除的学员学号:");

       scanf("%d",&num);

       for(i=0;i<count;i++)

       {

             if(zl[i].num==num)

             {

                     for(j=i;j<count;j++)

                   {

                         zl[j]=zl[j+1];

                   }

             }

       }

       count--;

       xianshi();

       diaoyong(count);

}

 

第二篇：数据结构实验报告——排序

1．实验要求

【实验目的】

学习、实现、对比各种排序算法，掌握各种排序算法的优劣，以及各种算法使用的情况。

【实验内容】

使用简单数组实现下面各种排序算法，并进行比较。

排序算法：

1、插入排序

2、希尔排序

3、冒泡排序

4、快速排序

5、简单选择排序

6、堆排序（选作）

7、归并排序（选作）

8、基数排序（选作）

9、其他

要求：

1、测试数据分成三类：正序、逆序、随机数据

2、对于这三类数据，比较上述排序算法中关键字的比较次数和移动次数（其中关键字交换计为3次移动）。

3、对于这三类数据，比较上述排序算法中不同算法的执行时间，精确到微秒（选作）

4、对2和3的结果进行分析，验证上述各种算法的时间复杂度

编写测试main()函数测试线性表的正确性。

2. 程序分析

2.1 存储结构

存储结构：数组

2.2 关键算法分析

//插入排序

void InsertSort(int r[], int n)

{

int count1=0,count2=0;

for (int i=2; i＜n; i++)

{

r[0]=r[i]; //设置哨兵

for (int j=i-1; r[0]＜r[j]; j--) //寻找插入位置

r[j+1]=r[j]; //记录后移

r[j+1]=r[0];

count1++;

count2++;

}

for(int k=1;k＜n;k++)

cout＜＜r[k]＜＜" ";

cout＜＜endl;

cout＜＜"比较次数为 "＜＜count1＜＜" 移动次数为 "＜＜count2＜＜endl;

}

//希尔排序

void ShellSort(int r[], int n)

{

int i;

int d;

int j;

int count1=0,count2=0;

for (d=n/2; d＞=1; d=d/2) //以增量为d进行直接插入排序

{

for (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]; //记录后移d个位置

r[j+d]=r[0];

count1++;

count2=count2+d;

}

count1++;

}

for(i=1;i＜n;i++)

cout＜＜r[i]＜＜" ";

cout＜＜endl;

cout＜＜"比较次数为 "＜＜count1＜＜" 移动次数为 "＜＜count2＜＜endl;

}

//起泡排序

void BubbleSort(int r[], int n)

{

int temp;

int exchange;

int bound;

int count1=0,count2=0;

exchange=n-1; //第一趟起泡排序的范围是r[1]到r[n]

while (exchange) //仅当上一趟排序有记录交换才进行本趟排序

{

bound=exchange;

exchange=0;

for(int j=0;j＜bound;j++) //一趟起泡排序

{

count1++; //接下来有一次比较

if(r[j]＞r[j+1])

{

temp=r[j]; //交换r[j]和r[j+1]

r[j]=r[j+1];

r[j+1]=temp;

exchange=j; //记录每一次发生记录交换的位置

count2=count2+3; //移动了3次

}

}

}

for(int i=1;i＜n;i++)

cout＜＜r[i]＜＜" ";

cout＜＜endl;

cout＜＜"比较次数为 "＜＜count1＜＜" 移动次数为 "＜＜count2＜＜endl;

}

//快速排序一次划分

int Partition(int r[], int first, int end,int &count1,int &count2)

{

int i=first; //初始化

int j=end;

int temp;

while (i＜j)

{

while (i＜j && r[i]＜= r[j])

{

j--; //右侧扫描

count1++;

}

count1++;

if (i＜j)

{

temp=r[i]; //将较小记录交换到前面

r[i]=r[j];

r[j]=temp;

i++;

count2=count2+3;

}

while (i＜j && r[i]＜= r[j])

{

i++; //左侧扫描

count1++;

}

count1++;

if (i＜j)

{

temp=r[j];

r[j]=r[i];

r[i]=temp; //将较大记录交换到后面

j--;

count2=count2+3;

}

}

return i; //i为轴值记录的最终位置

}

//快速排序

void QuickSort(int r[], int first, int end,int &count1,int &count2)

{

if (first＜end)

{ //递归结束

int pivot=Partition(r, first, end,count1,count2); //一次划分

QuickSort(r, first, pivot-1,count1,count2);//递归地对左侧子序列进行快速排序

QuickSort(r, pivot+1, end,count1,count2); //递归地对右侧子序列进行快速排序

}

}

//简单选择排序

void SelectSort(int r[ ], int n)

{

int i;

int j;

int index;

int temp;

int count1=0,count2=0;

for (i=0; i＜n-1; i++) //对n个记录进行n-1趟简单选择排序

{

index=i;

for(j=i+1;j＜n;j++) //在无序区中选取最小记录

{

count1++; //比较次数加一

if(r[j]＜r[index]) //如果该元素比现在第i个位置的元素小

index=j;

}

count1++; //在判断不满足循环条件j＜n时，比较了一次

if(index!=i)

{

temp=r[i]; //将无序区的最小记录与第i个位置上的记录交换

r[i]=r[index];

r[index]=temp;

count2=count2+3; //移动次数加3

}

}

for(i=1;i＜n;i++)

cout＜＜r[i]＜＜" ";

cout＜＜endl;

cout＜＜"比较次数为 "＜＜count1＜＜" 移动次数为 "＜＜count2＜＜endl;

}

//筛选法调整堆

void Sift(int r[],int k,int m,int &count1,int &count2) //s，t分别为比较和移动次数

{

int i;

int j;

int temp;

i=k;

j=2*i+1; //置i为要筛的结点，j为i的左孩子

while(j＜=m) //筛选还没有进行到叶子

{

if(j＜m && r[j]＜r[j+1]) j++; //比较i的左右孩子，j为较大者

count1=count1+2; //该语句之前和之后分别有一次比较

if(r[i]＞r[j])

break; //根结点已经大于左右孩子中的较大者

else

{

temp=r[i];

r[i]=r[j];

r[j]=temp; //将根结点与结点j交换

i=j;

j=2*i+1; //下一个被筛结点位于原来结点j的位置

count2=count2+3; //移动次数加3

}

}

}

//堆排序

void HeapSort(int r[],int n)

{

int count1=0,count2=0; //计数器，计比较和移动次数

int i;

int temp;

for(i=n/2;i＞=0;i--) //初始建堆，从最后一个非终端结点至根结点

Sift(r,i,n,count1,count2) ;

for(i=n-1; i＞0; i--) //重复执行移走堆顶及重建堆的操作

{

temp=r[i]; //将堆顶元素与最后一个元素交换

r[i]=r[0];

r[0]=temp; //完成一趟排序，输出记录的次序状态

Sift(r,0,i-1,count1,count2); //重建堆

}

for(i=1;i＜n;i++)

cout＜＜r[i]＜＜" ";

cout＜＜endl;

cout＜＜"比较次数为 "＜＜count1＜＜" 移动次数为 "＜＜count2＜＜endl;

}

//一次归并

void Merge(int r[], int r1[], int s, int m, int t)

{

int i=s;

int j=m+1;

int k=s;

while (i＜=m && j＜=t)

{

if (r[i]＜=r[j])

r1[k++]=r[i++]; //取r[i]和r[j]中较小者放入r1[k]

else

r1[k++]=r[j++];

}

if (i＜=m)

while (i＜=m) //若第一个子序列没处理完，则进行收尾处理

r1[k++]=r[i++];

else

while (j＜=t) //若第二个子序列没处理完，则进行收尾处理

r1[k++]=r[j++];

}

//一趟归并

void MergePass(int r[ ], int r1[ ], int n, int h)

{

int i=0;

int k;

while (i＜=n-2*h) //待归并记录至少有两个长度为h的子序列

{

Merge(r, r1, i, i+h-1, i+2*h-1);

i+=2*h;

}

if (i＜n-h)

Merge(r, r1, i, i+h-1, n); //待归并序列中有一个长度小于h

else for (k=i; k＜=n; k++) //待归并序列中只剩一个子序列

r1[k]=r[k];

}

//归并排序

void MergeSort(int r[ ], int r1[ ], int n )

{

int h=1;

int i;

while (h＜n)

{

MergePass(r, r1, n-1, h); //归并

h=2*h;

MergePass(r1, r, n-1, h);

h=2*h;

}

for(i=1;i＜n;i++)

cout＜＜r[i]＜＜" ";

cout＜＜endl;

}

void Newarray(int a[],int b[],int c[])

{

cout＜＜"新随机数组：";

c[0]=0;

a[0]=0;

b[0]=0;

for(int s=1;s＜11;s++)

{

a[s]=s;

b[s]=20-s;

c[s]=rand()%50+1;

cout＜＜c[s]＜＜" ";

}

cout＜＜endl;

}

2.3 其他

3. 程序运行结果

void main()

{

srand(time(NULL));

const int num=11; //赋值

int a[num];

int b[num];

int c[num];

int c1[num];

c[0]=0;

a[0]=0;

b[0]=0;

Newarray(a,b,c);

cout＜＜"顺序数组：";

for(int j=1;j＜num;j++)

cout＜＜a[j]＜＜" ";

cout＜＜endl;

cout＜＜"逆序数组：";

for(j=1;j＜num;j++)

cout＜＜b[j]＜＜" ";

cout＜＜endl;

cout＜＜endl;

cout＜＜"插入排序结果为："＜＜"\n";

InsertSort(a,num);

InsertSort(b,num);

InsertSort(c,num);

cout＜＜endl;

Newarray(a,b,c);

cout＜＜"希尔排序结果为："＜＜"\n";

ShellSort(a, num);

ShellSort(b, num);

ShellSort(c, num);

cout＜＜endl;

Newarray(a,b,c);

cout＜＜"起泡排序结果为："＜＜"\n";

BubbleSort(a, num);

BubbleSort(b, num);

BubbleSort(c, num);

cout＜＜endl;

int count1=0,count2=0;

Newarray(a,b,c);

cout＜＜"快速排序结果为："＜＜"\n";

QuickSort(a,0,num-1,count1,count2);

for(int i=1;i＜num;i++)

cout＜＜a[i]＜＜" ";

cout＜＜endl;

cout＜＜"比较次数为 "＜＜count1＜＜" 移动次数为 "＜＜count2＜＜endl;

count1=0,count2=0;

QuickSort(b,0,num-1,count1,count2);

for(i=1;i＜num;i++)

cout＜＜b[i]＜＜" ";

cout＜＜endl;

cout＜＜"比较次数为 "＜＜count1＜＜" 移动次数为 "＜＜count2＜＜endl;

count1=0,count2=0;

QuickSort(c,0,num-1,count1,count2);

for(i=1;i＜num;i++)

cout＜＜c[i]＜＜" ";

cout＜＜endl;

cout＜＜"比较次数为 "＜＜count1＜＜" 移动次数为 "＜＜count2＜＜endl;

cout＜＜endl;

cout＜＜endl;

Newarray(a,b,c);

cout ＜＜ "简单选择排序结果为：" ＜＜ "\n";

SelectSort(a,num);

SelectSort(b,num);

SelectSort(c,num);

cout＜＜endl;

Newarray(a,b,c);

cout ＜＜ "堆排序结果为：" ＜＜ "\n";

HeapSort(a, num);

HeapSort(b, num);

HeapSort(c, num);

cout＜＜endl;

Newarray(a,b,c);

cout ＜＜ "归并排序结果为：" ＜＜ "\n";

MergeSort(a, c1,num );

MergeSort(b, c1,num );

MergeSort(c, c1,num );

}