查询与排序 实验报告

电子科技大学实验报告课程名称：数据结构与算法学生姓名：学号：点名序号：指导教师：实验地点：基础实验大楼实验时间： 5月20日2014-2015-2学期信息与软件工程学院实验报告（二）学生姓名学号：指导教师：实验地点：基础实验大楼实验时间：5月20日一、实验室名称：软件实验室二、实验项目名称：数据结构与算法—排序与查找三、实验学时：4四、实验原理：快速排序的基本思想是：通过一躺排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的所有数据都要小，然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

假设要排序的数组是A[1]……A[N]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一躺快速排序。

一躺快速排序的算法是：1）设置两个变量I、J，排序开始的时候I：=1，J：=N2）以第一个数组元素作为关键数据，赋值给X，即X：=A[1]；3）从J开始向前搜索，即（J：=J-1），找到第一个小于X的值，两者交换；4）从I开始向后搜索，即（I：=I+1），找到第一个大于X的值，两者交换；5）重复第3、4步，直到I=J。

二分法查找（折半查找）的基本思想：（1）确定该区间的中点位置：mid=（low+high）/2min代表区间中间的结点的位置，low代表区间最左结点位置，high代表区间最右结点位置（2）将待查a值与结点mid的关键字（下面用R[mid].key）比较，若相等，则查找成功，否则确定新的查找区间：A)如果R[mid].key>a，则由表的有序性可知，R[mid].key右侧的值都大于a，所以等于a的关键字如果存在，必然在R[mid].key左边的表中,这时high=mid-1;B)如果R[mid].key<a,则等于a的关键字如果存在，必然在R[mid].key右边的表中。

学院专业班学号姓名协作者_____________教师评定_________________ 实验题目查询与排序综合实验评分表实验报告一、实验目的与要求1、掌握散列表的构造及实现散列查找；2、掌握堆排序的算法；3、综合比较各类排序算法的性能。

二、实验内容#include"stdio.h"#include"stdlib.h"#include"string.h"#include"windows.h"#define MAX 20typedef struct{unsigned long key;int result;char name[30];}RNode;RNode t[MAX],r[MAX];int h(unsigned long k) /*散列函数*/{return((k-3109005700)%11);}void insert(RNode t[],RNode x) /*插入函数，以线性探查方法解决冲突*/{int i,j=0;i=h(x.key);while((j<MAX)&&(t[(i+j)%MAX].key!=x.key)&&(t[(i+j)%MAX].key>0))j++;if(j==MAX) printf("full\n");i=(i+j)%MAX;if(t[i].key==0){t[i]=x;}else{if(t[i].key==x.key)printf("记录已存在!\n");}}int search(RNode t[],unsigned long k) /*插入函数，以线性探查方法解决冲突*/int i,j=0;i=h(k);while((j<MAX)&&(t[(i+j)%MAX].key!=k)&&(t[(i+j)%MAX].key!=0)) j++;i=(i+j)%MAX;if(t[i].key==k)return(i);if(j==MAX)return MAX;elsereturn(-i);}void sift(RNode r[],int v,int w){int i,j;RNode a;i=v;a=r[i];j=2*i+1;while(j<=w){if((j<w)&&(r[j].result>r[j+1].result))j++;if(a.result>r[j].result){r[i]=r[j];i=j;j=2*j+1;}else break;}r[i]=a;}void sort(RNode r[],int n){int i;RNode y;for(i=n/2-1;i>=0;i--)sift(r,i,n-1);for(i=n-1;i>0;i--){y=r[0];r[0]=r[i];r[i]=y;printf("学生姓名：%s\t学生学号：%u\t学生成绩：%d\n",r[i].name,r[i].key,r[i].result);sift(r,0,i-1);}printf("学生姓名：%s\t学生学号：%u\t学生成绩：%d\n",r[0].name,r[0].key,r[0].result);}int menu() /*菜单函数*/{int select;printf("\n\n");printf("\n");printf("\t\t*************查找排序实验******************\n"); printf("\t\t*\n");printf("\t\t*************欢迎进入系统******************\n"); printf("\t\t* menu: *\n"); printf("\t\t* 1.查找 *\n");printf("\t\t* 2.排序 *\n");printf("\t\t* 0.退出 *\n");printf("\t\t*******************************************\n"); printf("\n");printf("\t\t\t请输入0--2\n ");printf("\n");printf("请选择您所要的操作(选择(0)退出):");scanf("%d",&select);getchar();return(select);}void main() /*主函数*/{int i,s,n,select;int j=0,m=0;RNode y;for(i=0;i<MAX;i++)t[i].key=0; /*初始化*/for(i=0;i<10;i++) /*导入记录*/{switch(i){case 0:{RNode x;x.key=310900***;strcpy(," ***");x.result=90;insert(t,x);break;}case 1:{RNode x;x.key=31090***1;strcpy(," ***");x.result=95;insert(t,x);case 2:{RNode x;x.key=3109005***;strcpy(," ***");x.result=92;insert(t,x);break;}case 3:{RNode x;x.key=31090***;strcpy(," ***"); x.result=93;insert(t,x);break;}case 4:{RNode x;x.key=3109005***;strcpy(," ***");x.result=94;insert(t,x);break;}case 5:{RNode x;x.key=310900***;strcpy(," ***");x.result=91;insert(t,x);break;}case 6:{RNode x;x.key=3109005***;strcpy(," ***");x.result=96;insert(t,x);break;}case 7:{RNode x;x.key=310900***;strcpy(," ***");x.result=99;insert(t,x);break;}case 8:{RNode x;x.key=310900***;x.result=98;insert(t,x);break;}case 9:{RNode x;x.key=310900***;strcpy(,"***");x.result=97;insert(t,x);break;}}}printf("\n\n\n\n\n\n\n");system("cls");loop:{printf("\n\n\n");select=menu();switch(select){case 1:{printf("\n请输入要查找的学生学号：");scanf("%u",&y.key);s=search(t,y.key);if(s==MAX||s<0) printf("not find\n");else{ printf("\n\n你要查找的学生信息\n");printf("学生姓名：%s\t学生学号：%u",t[s].name,t[s].key);} break; }case 2:{for(i=0;i<MAX;i++){if(t[i].key!=0){r[j++]=t[i];m++;}}printf("排序之前：\n\n");for(i=0;i<m;i++)printf("学生姓名：%s\t学生学号：%u\t学生成绩：%d\n",r[i].name,r[i].key,r[i].result);printf("\n排序之后：\n");sort(r,m);break;}case 0:exit(0);getchar();goto loop;}}三、实验结果和数据处理（1）查找数据（310900****）（2）排序四、总结这次的课程实验完成了主控界面，录入，输出，排序，查找，结束界面等功能。

数据结构实验报告五,查找与排序-查找与排序一、实验目的：1．理解掌握查找与排序在计算机中的各种实现方法。

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

3．熟练掌握常用排序算法在顺序表上的实现。

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

三、实验内容及分析：设计一个学生信息管理系统，学生对象至少要包含：学号、性别、成绩1、成绩总成绩等信息。

要求实现以下功能：1．平均成绩要求自动计算；2．查找：分别给定学生学号、性别，能够查找到学生的基本信息（要求至少用两种查找算法实现）；3．? 排序：分别按学生的学号、成绩1、成绩2、平均成绩进行排序（要求至少用两种排序算法实现）。

四、程序的调试及运行结果五、程序代码#includestdio.h#includestring.hstruct student//定义结构体{char name;int a1,a2,a3,num;double pow;}zl;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",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",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",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'count100);//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'count100);paixv(count);diaoyong(count);}void xianshi() //显示{int i;printf("学号\t \t姓名\t\t\t平均成绩\n");for(i=0;icount;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;icount;i++){for(j=1;jcount-i;j++){if(zl[j-1].powzl[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;icount;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();printf("学号\t姓名\t成绩1\t成绩2\t成绩3\t平均成绩\n");for(i=0;icount;i++){if((strcmp(zl[i].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;icount;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;icount;i++){if(zl[i].num==num){for(j=i;jcount;j++){zl[j]=zl[j+1];}}}count--;xianshi();diaoyong(count);}。

《编程实训》实验报告书专业：计算机科学与技术班级：151班学号：姓名：指导教师：日期：2016年6月30日目录一、需求分析 (3)1.任务要求 (3)2.软件功能分析 (3)3.数据准备 (3)二、概要设计 (3)1.功能模块图 (4)2.模块间调用关系 (4)3.主程序模块 (5)4.抽象数据类型描述 (5)三、详细设计 (6)1.存储结构定义 (6)2.各功能模块的详细设计 (7)四、实现和调试 (7)1.主要的算法 (7)2.主要问题及解决 (8)3.测试执行及结果 (8)五、改进 (9)六、附录 (9)1.查找源程序 (9)2.排序源程序 (9)目录1 需求分析1.1 任务要求对于从键盘随机输入的一个序列的数据，存入计算机内，给出各种查找算法的实现；以及各种排序算法的实现。

1.2 软件功能分析任意输入n个正整数，该程序可以实现各类查找及排序的功能并将结果输出。

1.3 数据准备任意输入了5个正整数如下：12 23 45 56 782 概要设计（如果2，3合并可以省略2.4）2.1 功能模块图（注：含功能说明）2.2 模块间调用关系2.3 主程序模块2.4 抽象数据类型描述存储结构：数据结构在计算机中的表示（也称映像）叫做物理结构。

又称为存储结构。

数据类型（data type）是一个“值”的集合和定义在此集合上的一组操作的总称。

3 详细设计3.1 存储结构定义查找：typedef int ElemType ;//顺序存储结构typedef struct{ElemType *elem; //数据元素存储空间基址，建表时按实际长度分配，号单元留空int length; //表的长度}SSTable;排序：typedef struct{ //定义记录类型int key; //关键字项}RecType;typedef RecType SeqList[Max+1]; //SeqList为顺序表，表中第0个元素作为哨兵3.2 各功能模块的详细设计查找：void Create(SSTable *table, int length); // 构建顺序表void FillTable(SSTable *table) // 无序表的输入int Search_Seq(SSTable *table, ElemType key); //哨兵查找算法void Sort(SSTable *table ) // 排序算法int Search_Bin(SSTable *table, ElemType key) // 二分法查找（非递归）排序：void InsertSort(SeqList R) //对顺序表R中的记录R[1‥n]按递增序进行插入排序void BubbleSort(SeqList R) //自下向上扫描对R做冒泡排序int Partition(SeqList R,int i,int j)//对R[i‥j]做一次划分，并返回基准记录的位置void QuickSort(SeqList R,int low,int high) //R[low..high]快速排序void SelectSort(SeqList R) //直接选择排序void Heapify(SeqList R,int low,int high) //大根堆调整函数void MergePass(SeqList R,int length) //归并排序4 实现和调试4.1 主要的算法查找：①建立顺序存储结构，构建一个顺序表，实现顺序查找算法。

实验七查找、排序的应用一、实验目的1、本实验可以使学生更进一步巩固各种查找和排序的基本知识。

2、学会比较各种排序与查找算法的优劣。

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

4、掌握利用常用的排序与选择算法的思想来解决一般问题的方法和技巧。

二、实验内容[问题描述]对学生的基本信息进行管理。

[基本要求]设计一个学生信息管理系统，学生对象至少要包含：学号、姓名、性别、成绩1、成绩2、总成绩等信息。

要求实现以下功能：1．总成绩要求自动计算；2．查询：分别给定学生学号、姓名、性别，能够查找到学生的基本信息（要求至少用两种查找算法实现）；3．排序：分别按学生的学号、成绩1、成绩2、总成绩进行排序（要求至少用两种排序算法实现）。

[测试数据]由学生依据软件工程的测试技术自己确定。

三、实验前的准备工作1、掌握哈希表的定义，哈希函数的构造方法。

2、掌握一些常用的查找方法。

1、掌握几种常用的排序方法。

2、掌握直接排序方法。

四、实验报告要求1、实验报告要按照实验报告格式规范书写。

2、实验上要写出多批测试数据的运行结果。

3、结合运行结果，对程序进行分析。

五、算法设计a、折半查找设表长为n，low、high和mid分别指向待查元素所在区间的下界、上界和中点,key为给定值。

初始时，令low=1,high=n,mid=(low+high)/2，让key与mid指向的记录比较，若key==r[mid].key，查找成功若key<r[mid].key，则high=mid-1若key>r[mid].key，则low=mid+1重复上述操作，直至low>high时，查找失败b、顺序查找从表的一端开始逐个进行记录的关键字和给定值的比较。

在这里从表尾开始并把下标为0的作为哨兵。

void chaxun(SqList &ST) //查询信息{ cout<<"\n************************"<<endl;cout<<"~ (1)根据学号查询 ~"<<endl;cout<<"~ (2)根据姓名查询 ~"<<endl;cout<<"~ (3)根据性别查询 ~"<<endl;cout<<"~ (4)退出 ~"<<endl;cout<<"************************"<<endl; if(m==1) 折半查找算法：for(int i=1;i<ST.length;i++)//使学号变为有序for(int j=i;j>=1;j--)if(ST.r[j].xuehao<ST.r[j-1].xuehao){LI=ST.r[j];ST.r[j]=ST.r[j-1];ST.r[j-1]=LI;}int a=0;cout<<"输入要查找的学号"<<endl;cin>>n;int low,high,mid;low=0;high=ST.length-1; // 置区间初值while (low<=high){mid=(low+high)/2;if(n==ST.r[mid].xuehao){cout<<ST.r[mid].xuehao<<""<<ST.r[mid].xingming<<""<<ST.r[mid].xingbei<<""<<ST.r[mid].chengji1<<""<<ST.r[mid].chengji2<<""<<ST.r[mid].zong<<endl;a=1;break;}else if(n<ST.r[mid].xuehao )high=mid-1; // 继续在前半区间进行查找elselow=mid+1; // 继续在后半区间进行查找顺序查找算法:cout<<"输入要查找的姓名"<<endl;cin>>name;for(int i=0;i<ST.length;i++){if(name==ST.r[i].xingming){cout<<ST.r[i].xuehao<<""<<ST.r[i].xingming<<""<<ST.r[i].xingbei<<""<<ST.r[i].chengji1<<""<<ST.r[i].chengji2<<""<<ST.r[i].zong<<endl;a=1;}1、插入排序每步将一个待排序的记录，按其关键码大小，插入到前面已经排好序的一组记录的适当位置上，直到记录全部插入为止。

实验四：查找与排序【实验目的】1.掌握顺序查找算法的实现。

2.掌握折半查找算法的实现。

【实验内容】1.编写顺序查找程序，对以下数据查找37所在的位置。

5，13，19，21，37，56，64，75，80，88，922.编写折半查找程序，对以下数据查找37所在的位置。

5，13，19，21，37，56，64，75，80，88，92【实验步骤】1.打开VC++。

2.建立工程：点File->New，选Project标签，在列表中选Win32 ConsoleApplication，再在右边的框里为工程起好名字，选好路径，点OK->finish。

至此工程建立完毕。

3.创建源文件或头文件：点File->New，选File标签，在列表里选C++ SourceFile。

给文件起好名字，选好路径，点OK。

至此一个源文件就被添加到了你刚创建的工程之中。

4．写好代码5．编译－＞链接－＞调试#include "stdio.h"#include "malloc.h"#define OVERFLOW -1#define OK 1#define MAXNUM 100typedef int Elemtype;typedef int Status;typedef struct{Elemtype *elem;int length;}SSTable;Status InitList(SSTable &ST ){int i,n;ST.elem = (Elemtype*) malloc (MAXNUM*sizeof (Elemtype)); if (!ST.elem) return(OVERFLOW);printf("输入元素个数和各元素的值:");scanf("%d\n",&n);for(i=1;i<=n;i++){scanf("%d",&ST.elem[i]);}ST.length = n;return OK;}int Seq_Search(SSTable ST,Elemtype key){int i;ST.elem[0]=key;for(i=ST.length;ST.elem[i]!=key;--i);return i;}int BinarySearch(SSTable ST,Elemtype key){int low,high,mid;low=1;high=ST.length;while(low<=high){mid=(low+high)/2;if(ST.elem[mid]==key)return mid;else if(key<ST.elem[mid])high=mid-1;elselow=mid+1;}return 0;}void main(){int key;SSTable ST;InitList(ST);printf("输入查找的元素的值:");scanf("%d",&key);Seq_Search(ST,key);printf("查找的元素所在的位置:%d\n",Seq_Search(ST,key));printf("输入查找的元素的值:");scanf("%d",&key);BinarySearch(ST,key);printf("查找的元素所在的位置:%d\n",BinarySearch(ST,key));}【实验心得】这是本学期的最后一节实验课，实验的内容是查找与排序。

一、实验目的1. 熟悉常用的查找和排序算法，掌握它们的原理和实现方法。

2. 提高编程能力，提高算法分析能力。

3. 通过实验验证查找和排序算法的性能。

二、实验环境1. 操作系统：Windows 102. 编程语言：Python3.83. 开发工具：PyCharm三、实验内容1. 查找算法：二分查找、线性查找2. 排序算法：冒泡排序、选择排序、插入排序、快速排序、归并排序四、实验步骤1. 设计一个数据结构，用于存储待查找和排序的数据。

2. 实现二分查找算法，用于查找特定元素。

3. 实现线性查找算法，用于查找特定元素。

4. 实现冒泡排序、选择排序、插入排序、快速排序、归并排序算法，对数据进行排序。

5. 分别测试查找和排序算法的性能，记录时间消耗。

五、实验结果与分析1. 查找算法（1）二分查找算法输入数据：[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]查找目标：11查找结果：成功，位置为5（2）线性查找算法输入数据：[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]查找目标：11查找结果：成功，位置为52. 排序算法（1）冒泡排序输入数据：[5, 3, 8, 4, 2]排序结果：[2, 3, 4, 5, 8]（2）选择排序输入数据：[5, 3, 8, 4, 2]排序结果：[2, 3, 4, 5, 8]（3）插入排序输入数据：[5, 3, 8, 4, 2]排序结果：[2, 3, 4, 5, 8]（4）快速排序输入数据：[5, 3, 8, 4, 2]排序结果：[2, 3, 4, 5, 8]（5）归并排序输入数据：[5, 3, 8, 4, 2]排序结果：[2, 3, 4, 5, 8]3. 性能测试（1）查找算法性能测试二分查找算法在数据量较大的情况下，查找效率明显优于线性查找算法。

（2）排序算法性能测试在数据量较大的情况下，快速排序和归并排序的性能明显优于冒泡排序、选择排序和插入排序。

淮海工学院计算机工程学院实验报告书课程名：《数据结构》题目：查找、排序的应用实验班级：学号：姓名：实验报告要求1目的与要求:1）完整理解二叉排序树的基本概念;2) 掌握二叉排序树的建立、查找、插入和删除算法实现思想和基本应用方法；3）掌握二叉排序树的建立、查找、插入和删除算法实现的c语言编程技巧；4）完整理解有关排序的基本概念;5) 掌握各种排序方法的算法实现思想和存储表示方法；6）掌握所选排序方法的C语言编程技巧；7）按照实验题目要求独立正确地完成实验内容（提交程序清单及相关实验数据与运行结果）；8）认真书写实验报告,并按时提交。

2 实验内容或题目题目1：用C或C++语言设计实现二叉排序树的基本操作应用程序，功能包括：二叉排序树的建立，二叉排序树的查找，二叉排序树的插入，二叉排序树的删除。

程序实现后，用记录关键字序列：{55，59，45，23，72，109，89，112，48，2，3}进行正确性验证（在建立、删除、插入操作后要给出相应二叉排序树遍历结果）。

题目2：用C或C++语言设计实现快速排序方法的排序应用程序。

程序实现后，以待排序记录序列：{55，13，23，72，109，67，2，78, 23}进行正确性验证。

选做题目：用C或C++语言实现快速排序之外的其他算法，并以序列：{55，13，23，72，109，67，2，78,23}对程序进行正确性验证。

3 实验步骤与源程序（1）#include<stdio.h>#include<stdlib.h>#include<malloc.h>typedef struct Bstnode{int key;struct Bstnode *lchild,*rchild;}Bstnode,* Bstree;Bstree Create();Bstree Insert(Bstree tree,int key);Bstree Search(Bstree tree,int key);void Traverse(Bstree tree);Bstree Create(){int key; Bstree tree=NULL; scanf("%d",&key); while(key!=0){tree=Insert(tree,key);scanf("%d",&key);}return tree;}Bstree Insert(Bstree tree,int key){Bstree p=tree;Bstree s,f;while (p!=NULL){f=p;if(key==p->key) return tree;if(key<p->key) p=p->lchild;else p=p->rchild;}s=(Bstree)malloc(sizeof(Bstnode));s->key=key;s->lchild=NULL;s->rchild=NULL;if(tree==NULL)return s;if(key<f->key)f->lchild=s;elsef->rchild=s;return tree;}Bstree Search(Bstree tree,int key){Bstree p=tree;int flag=0;while(p!=NULL){if(p->key==key){printf("查询到该节点！");flag=1;return(p);}if (key<p->key)p=p->lchild;elsep=p->rchild;}if(flag==0){printf("查询不到关键字为%d的节点！",key);return NULL;}}void Traverse(Bstree tree){if(tree){Traverse(tree->lchild);printf("%4d",tree->key);Traverse(tree->rchild);}}Bstree Delete(Bstree tree,int key){Bstree p=tree;Bstree f,s,q;f=NULL;while(p){//查找关键字为key的节点if(p->key==key)break;f=p;if(p->key>key)p=p->lchild;elsep=p->rchild;}if (p==NULL)return tree;if ((p->lchild==NULL)||(p->rchild==NULL)){if(f==NULL) if(p->lchild==NULL)tree=p->rchild;elseelse if (p->lchild==NULL)if(f->lchild==p)f->lchild=p->rchild;elsef->rchild=p->rchild;else if(f->lchild==p)f->lchild=p->lchild;elsef->lchild=p->lchild;free(p);}else{q=p;s=p->lchild;while(s->rchild){q=s;s=s->rchild;}if(q==p) q->lchild=s->lchild;p->key=s->key;free(s);}return tree;}void main(){Bstree tree,p;int key1,key2,key3;int select,flag;printf("############################################\n"); printf("|* 欢迎您使用本系统 *|\n"); printf("|******************************************|\n"); printf("|* 1.创建二叉排序树 *|\n"); printf("|* 2.插入 *|\n"); printf("|* 3.查找 *|\n"); printf("|* 4.遍历 *|\n"); printf("|* 5.删除 *|\n"); printf("|* 6.退出 *|\n"); printf("********************************************\n"); while(select!=6){printf("选择的功能：");scanf("%d",&select);switch(select)case 1: printf("请输入节点信息(0为结束符):\n");tree=Create();break;case 2: printf("插入一个新的节点:");scanf("%d",&key1);Insert(tree,key1);printf("插入后得序列为:\n");Traverse(tree);printf("\n");break;case 3: printf("输入查找的数据:");scanf("%d",&key2);p=Search(tree,key2);printf("\n");break;case 4: printf("遍历所得序列为:\n");Traverse(tree);printf("\n");break;case 5: printf("输入删除的数据:");scanf("%d",&key3);tree=Delete(tree,key3);printf("删除后遍历所得序列:\n");Traverse(tree);printf("\n");break;case 6: printf("谢谢您的使用，再见！\n");flag=0;break;default:printf("输入错误,请重新输入\n");break;}}}（2）#include<stdio.h>typedef int KeyType;typedef int OtherType;typedef struct{KeyType key;}RecordType;int QKPass(RecordType r[],int left,int right){RecordType x;int low=left;int high=right;while(low<high){while(low<high&&r[high].key>=x.key){high--;}if(low<high){r[low]=r[high];low++;}while(low<high&&r[low].key<x.key){low++;}if(low<high){r[high]=r[low];high--;}}r[low]=x;return low;}void QKSort(RecordType r[],int low,int high) {if(low<high){int pos=QKPass(r,low,high);QKSort(r,low,pos-1);QKSort(r,pos+1,high);}}void main(){RecordType r[9];printf("请输入要排序的数据:\n");for(int i=0;i<9;i++){scanf("%d",&r[i]);}QKSort(r,0,8);printf("快速排序结果为:\n");{printf("%d ",r[i]);}printf("\n");}4 测试数据与实验结果（可以抓图粘贴）（1）（2）5 结果分析与实验体会本次试验是有关查找和排序的一些操作，要求理解二叉排序树的基本概念并实现二叉树的建立、查找、插入和删除算法。

淮海工学院计算机科学系实验报告书课程名：《数据结构》题目：查找、排序的应用实验班级：软件112学号：2011122635姓名：排序、查找的应用实验报告要求1目的与要求:1）查找、排序是日常数据处理过程中经常要进行的操作和运算，掌握其算法与应用对于提高学生数据处理能力和综合应用能力显得十分重要。

2）本次实验前，要求同学完整理解有关排序和查找的相关算法和基本思想以及种算法使用的数据存储结构；3）利用C或C++语言独立完成本次实验内容或题目，程序具有良好的交互性（以菜单形式列出实验排序和显示命令，并可进行交互操作）和实用性；4）本次实验为实验成绩评定主要验收内容之一，希望同学们认真对待，并按时完成实验任务；5）本次实验为综合性实验，请于2012年12月23日按时提交实验报告（纸质报告每班10份）；6）下周开始数据结构课程设计，务必按时提交实验报告，任何同学不得拖延。

2 实验内容或题目题目：对记录序列（查找表）：{287，109，063，930，589，184，505，269,008，083}分别实现如下操作：1)分别使用直接插入排序、冒泡排序、快速排序、简单选择排序、堆排序（可选）、链式基数排序算法对纪录序列进行排序，并显示排序结果；2)对上述纪录列表排好序，然后对其进行折半查找或顺序查找；3 实验步骤与源程序#include "stdio.h"#include "stdlib.h"#define LIST_SIZE 20#define TRUE 1#define FALSE 0typedef int KeyType;typedef struct{KeyType key;}RecordType;typedef struct{RecordType r[LIST_SIZE+1];int length;}RecordList;void seqSearch(RecordList *l){KeyType k; int i;printf("请输出要查询的元素k:");fflush(stdin);scanf("%d",&k);i=l->length;while (i>=0&&l->r[i].key!=k)i--;printf("该元素的位置是");printf("%d",i+1);//cout<<"该元素在图中第"<<i<<"个位置"<<endl; printf("\n");}void BinSrch(RecordList *l){KeyType q;int mid;printf("请输入要查询的元素k:");fflush(stdin);scanf("%d",&q);int low=1;int high=l->length;while(low<=high){mid=(low+high)/2;if(q==l->r[mid].key){printf("该元素的位置为:");printf("%d",mid+1);//注意不能随便使用&printf("\n");break;}else if(q<l->r[mid].key)high=mid-1;elselow=mid+1;}}void inputkey(RecordList *l){int i;printf("请输入线性表长度:");//遇到错误：1.print用法scanf("%d",&(l->length));//&将变量的地址赋值，而不是变量的值for(i=1;i<=l->length ;i++){printf("请输入第%d个元素的值:",i);fflush(stdin);scanf("%d",&(l->r[i].key));}}void InsSort(RecordList *l){for(int i=2;i<=l->length;i++){l->r[0].key=l->r[i].key;int j=i-1;while(l->r[0].key<l->r[j].key){l->r[j+1].key=l->r[j].key;j=j-1;}l->r[j+1].key=l->r[0].key;}}//直接插入排序void BubbleSort(RecordList *l){int x,i,n,change,j;n=l->length;change=TRUE;for(i=1;i<=n-1&&change;++i){change=FALSE;for(j=1;j<=n-i;++j)if(l->r[j].key>l->r[j+1].key){x=l->r[j].key;l->r[j].key=l->r[j+1].key ;l->r[j+1].key=x;change=TRUE;}}}//冒泡排序法int QKPass(RecordList *l,int left,int right) {int x;x=l->r[left].key ;int low=left;int high=right;while(low<high){while(low<high&&l->r[high].key>=x)high--;if(low<high){l->r[low].key=l->r[high].key;low++;}while(low<high&&l->r[low].key<=x)low++;if(low<high){l->r[high].key=l->r[low].key;high--;}}l->r[low].key=x;return(low);}void QKSort(RecordList *l,int low,int high){int pos;if(low<high){pos=QKPass(l,low,high);QKSort(l,low,pos-1);QKSort(l,pos+1,high);}}//快速排序void SelectSort(RecordList *l){int n,i,k,j,x;n=l->length;for(i=1;i<=n-1;++i){k=i;for(j=i+1;j<=n;++j)if(l->r[j].key<l->r[k].key) k=j;if(k!=i){x=l->r[i].key;l->r[i].key=l->r[k].key;l->r[k].key=x;} }}void output(RecordList *l){for(int i=1;i<=l->length;i++){printf("%d",l->r[i].key);printf("\n");}}void main(){RecordList *l,*t,*m,*n;l=(RecordList *)malloc(sizeof(RecordList));int low;int high;int flag=1;int xuanze;while(flag!=0){printf("####################################################\n");printf("###### 请选择你要进行的操作! #########\n");printf("###### 1.直接插入排序; #########\n");printf("###### 2.冒泡排序; #########\n");printf("###### 3.快速排序; #########\n");printf("###### 4.简单选择排序; #########\n");printf("###### 5.顺序查找; #########\n");printf("###### 6.折半查找; #########\n");printf("###### 7.退出! #########\n");printf("####################################################\n");scanf("%d",&xuanze);switch(xuanze){case 1:inputkey(l);InsSort(l);printf("直接插入排序结果是:\n");output(l);break;case 2:inputkey(l);BubbleSort(l);printf("冒泡排序结果是:\n");output(l);break;case 3:inputkey(l);low=1;high=l->length;QKSort(l,low,high);printf("快速排序结果是:\n");output(l);break;case 4:inputkey(l);SelectSort(l);printf("简单选择排序结果是:\n");output(l);break;case 5:inputkey(l);InsSort(l);printf("排序结果是:\n");output(l);seqSearch(l);break;case 6:inputkey(l);InsSort(l);printf("排序结果是:\n");output(l);break;BinSrch(l);case 7:flag=0;break;}}}4 测试数据与实验结果（可以抓图粘贴）《数据结构》实验报告- 10 -5 结果分析与实验体会1.编程时要细心，避免不必要的错误；2.要先熟悉书本上的内容，否则编译会有困难；3.不能太过死板，要灵活运用所学知识。