实验五 查找和排序实验报告

学院专业班学号姓名协作者_____________教师评定_________________ 实验题目查询与排序综合实验评分表实验报告一、实验目的与要求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. 通过实际操作，验证排序检验的有效性。

二、实验原理排序检验（Rank Test）是一种非参数检验方法，用于检验两个独立样本是否来自同一总体。

其基本思想是将样本数据从小到大排序，计算两个样本的秩和，然后根据秩和比较两个样本是否具有显著差异。

三、实验材料1. 计算机2. 数据处理软件（如SPSS、R等）3. 实验数据四、实验步骤1. 收集实验数据，确保两组数据相互独立。

2. 对两组数据进行排序，得到各自的秩。

3. 计算两组数据的秩和。

4. 根据秩和计算检验统计量。

5. 根据检验统计量查表得到临界值。

6. 判断两组数据是否来自同一总体。

五、实验结果与分析1. 数据描述本实验选取了两组独立样本，分别为样本A和样本B。

样本A包含10个数据，样本B包含10个数据。

两组数据如下：样本A：3, 5, 7, 8, 9, 10, 12, 13, 14, 15样本B：1, 4, 6, 7, 8, 9, 10, 11, 12, 132. 排序及秩计算将两组数据从小到大排序，得到各自的秩：样本A：1, 2, 3, 4, 5, 6, 7, 8, 9, 10样本B：1, 2, 3, 4, 5, 6, 7, 8, 9, 103. 秩和计算计算两组数据的秩和：样本A秩和：1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 = 55样本B秩和：1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 = 554. 检验统计量及临界值计算检验统计量：T = |秩和A - 秩和B| / √[nA nB (nA + nB + 1) / 12]T = |55 - 55| / √[10 10 (10 + 10 + 1) / 12]T = 0查表得到临界值，以α = 0.05为例，查表得到临界值为1.98。

5. 判断结果由于计算得到的检验统计量T = 0小于临界值1.98，因此无法拒绝原假设，即两组数据来自同一总体。

实验作业五：查找与排序1. 写出在二叉排序树中删除一个结点的算法，使删除后仍为二叉排序树。

设删除结点由指针p所指，其双亲结点由指针f所指，并假设被删除结点是其双亲结点的右孩子。

2. 试修改起泡排序算法，在正反两个方向交替进行扫描，即第一趟把排序码最大的对象放到序列的最后，第二趟把排序码最小的对象放到序列的最前面。

如此反复进行。

3. 奇偶交换排序是另一种交换排序。

它的第一趟对序列中的所有奇数项i扫描，第二趟对序列中的所有偶数项i扫描。

若A[i] > A[i+1]，则交换它们。

第三趟有对所有的奇数项，第四趟对所有的偶数项，…，如此反复，直到整个序列全部排好序为止。

编写实习报告要求：一、需求分析二、概要设计1.抽象数据类型2.算法三、详细设计程序代码（注释）四、调试分析调试过程中所做的工作，时间复杂度等五、测试结果输入数据和输出数据示例六、说明（如果有）编程语言：C语言或C++语言实习报告提交方式：下次上机前，将实习报告(.doc)和源程序(.cpp)压缩成一个rar 文件，文件名称为学号_班级_姓名_第几次作业。

例如：_六班_张三_第五次作业.rar。

实习报告作为本课程的平时成绩。

抄袭、雷同，双方均为0分。

第一题：需求分析题目需要建立一个二叉排序树，之后输入节点数据，根据内容查找得到节点，然后对此节点进行删除操作。

二、概要设计1.抽象数据类型typedef struct Node{int data;struct Node *left;struct Node *right;Node(int val){left = right = NULL,data = val;}}Node;2.算法（1）.创建一个二叉排序树。

void InsertTree(Node **root,int val){if(root == NULL) return;Node *e = new Node(val);if(e == NULL) return;if(*root == NULL){*root = e;}else{Node *p = *root,*pre = NULL;while(p != NULL){pre = p;if(e->data < p->data){p = p->left;}else if(e->data > p->data){p = p->right;}else{delete e;return;}}if(e->data < pre->data)pre->left = e;else{pre->right = e;}}}（2）.删除某个右节点。

附件（四）深圳大学实验报告课程名称：数据结构实验与课程设计实验项目名称：查找排序实验.学院：计算机与软件学院专业：指导教师：报告人：学号：班级：实验时间：实验报告提交时间：教务处制①②③④Problem B: 数据结构实验--二叉排序树之查找QSort(a,1,1);④(①b)low=4;high=5;6 22 55 111 333 444↑↑privotloc=4;a. QSort(a,low,pivotloc-1);QSort(a,4,3);b. QSort(a,pivotloc+1,high);QSort(a,5,5);排序完毕。

流程图：四、实验结论：1、根据你完成的每个实验要求，给出相应的实验结果图，并结合图来解析运行过程2、如果运行过程简单，只要贴出VC运行的结果图。

3、如果无结果图，有网站的判定结果，贴出相应结果Contest1657 - DS实验--静态查找Problem A: 数据结构实验--静态查找之顺序查找Sample Input833 66 22 88 11 27 44 553221199Sample Output35errorProblem B: 数据结构实验--静态查找之折半查找Sampl e Input811 22 33 44 55 66 77 883228899Sampl e Output28errorProblem C: 数据结构实验--静态查找之顺序索引查找Sampl e Input1822 12 13 8 9 20 33 42 44 38 24 48 60 58 74 57 86 53322 48 86613548405390Sampl e Output3-4error12-8error18-9errorContest1040 - DS实验--动态查找Problem A: 数据结构实验--二叉排序树之创建和插入Sample Input1622 33 55 66 11 443775010Sample Output11 22 33 44 55 6611 22 33 44 55 66 7711 22 33 44 50 55 66 7710 11 22 33 44 50 55 66 77Problem B: 数据结构实验--二叉排序树之查找Sample Input1622 33 55 66 11 44711223344556677Sample Output11 22 33 44 55 66212434-1Problem C: 数据结构实验--二叉排序树之删除Sample Input1622 33 55 66 11 443662277Sample Output11 22 33 44 55 6611 22 33 44 5511 33 44 5511 33 44 55Contest1050 - DS实验--哈希查找Problem A: 数据结构实验--哈希查找Sample Input11 23 39 48 75 626395252636352Sample Output6 1error8 1error8 18 2Contest1060 - DS实验--排序算法Problem A: 数据结构实验--希尔排序Sample Input6111 22 6 444 333 55877 555 33 1 444 77 666 2222Sample Output6 22 55 111 333 4441 33 77 77 444 555 666 2222Problem B: 数据结构实验--快速排序Sample Input26111 22 6 444 333 55877 555 33 1 444 77 666 2222Sample Output6 22 55 111 333 4441 33 77 77 444 555 666 2222。

《编程实训》实验报告书专业：计算机科学与技术班级：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 主要的算法查找：①建立顺序存储结构，构建一个顺序表，实现顺序查找算法。

淮海工学院计算机科学系实验报告书课程名：《数据结构》题目：查找、排序的应用实验班级：软件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.不能太过死板，要灵活运用所学知识。

实验五查找和排序应用一、实验目的1．掌握查找的不同方法，并能用高级语言实现查找算法。

2．熟练掌握顺序表和有序表的顺序查找和二分查找方法。

3．掌握排序的不同方法，并能用高级语言实现排序算法。

4．熟练掌握顺序表的选择排序、冒泡排序和直接插入排序算法的实现。

二、实验内容1．学生信息如下：学号姓名数据结构程序设计1 王立76 882 张秋88 773 刘丽79 654 王通86 855 赵阳71 906 李艳68 707 钱娜89 958 孙胜60 762．创建顺序查找表，输入学生信息。

【选做：也可以将学生信息存入文件，直接从文件读取学生信息】3．使用顺序查找方法按姓名查找学生。

如果查找成功，则显示该生的相关信息；如果查找不成功，则给出相应的提示信息。

4．使用二分查找方法，查找学生学号信息。

如果查找成功，则显示该生的相关信息；如果查找不成功，则给出相应的提示信息。

5．使用直接插入排序方法，对学生信息中的姓名进行排序。

输出排序前和排序后的学生信息表，验证排序结果。

6．使用直接选择排序方法，对学生信息中的数据结构成绩进行排序。

输出排序前和排序后的学生信息表，验证排序结果。

7．使用冒泡排序方法，对学生信息中的程序设计成绩进行排序。

输出排序前和排序后的学生信息表，验证排序结果。

8．编写一个菜单，来实现各项功能的选择。

*******************学生成绩管理系统****************** 1．信息初始化2．顺序查找** 3．二分查找4．直接插入排序** 5．冒泡排序6．直接选择排序** 0．退出*****************************************************9．利用工程完成本次实验任务，各个功能分别放到一个函数中。

三、实验结果#include<iostream>#include<string>using namespace std;# define size 10struct student{string num;string name;string classnum;int datascore;int cxscore;};struct seqlist{student stu[size];int len;};void create_seq(seqlist &L){int n;cout<<"请输入学生的人数：";cin>>n;L.len=n;cout<<endl;cout<<"请输入学生信息："<<endl;cout<<"学号"<<" "<<"姓名"<<" "<<"数据结构"<<" "<<"程序设计"<<endl;for(int i=1;i<=L.len;i++){cin>>L.stu[i].num>>L.stu[i].name>>L.stu[i].datascore>>L.stu[i].cxscore;}}void display(seqlist L){cout<<"学号"<<" "<<"姓名"<<" "<<"数据结构"<<" "<<"程序设计"<<endl;for(int i=1;i<=L.len;i++){cout<<L.stu[i].num<<" "<<L.stu[i].name<<" "<<L.stu[i].datascore<<" "<<L.stu[i].cxscore<<endl;}cout<<endl;}void seq_search(seqlist L,string n){int i=1;while(i<=L.len&&L.stu[i].name!=n){i++;}if(i>L.len){cout<<"该生不存在"<<endl;return;}cout<<L.stu[i].num<<" "<<L.stu[i].name<<" "<<L.stu[i].datascore<<" "<<L.stu[i].cxscore<<endl;}void bin_search(seqlist L,string n){int low,high,mid;low=1;high=L.len;while(low<=high){mid=(low+high)/2;if(L.stu[mid].num==n){cout<<L.stu[mid].num<<" "<<L.stu[mid].name<<" "<<L.stu[mid].datascore<<" "<<L.stu[mid].cxscore<<endl;return;}else if(n<L.stu[mid].num){high=mid-1;}else{low=mid+1;}}cout<<"该学生不存在"<<endl;}void selectsort(seqlist L){int k;student temp;for(int i=1;i<=L.len-1;i++){k=i;for(int j=i+1;j<=L.len;j++){if(L.stu[j].datascore<L.stu[k].datascore)k=j;}if(k!=i){temp=L.stu [i];L.stu[i]=L.stu[k];L.stu[k]=temp;}}display(L);}void bubblesort(seqlist L){int i,j,flag=1;student w;for(i=1;(i<=L.len-1)&&(flag);i++){flag=0;for(j=L.len;j>=j+1;j--)if(L.stu[j].cxscore<L.stu[j-1].cxscore){w=L.stu[j];L.stu[j]=L.stu[j-1];L.stu[j-1]=w;flag=1;}}display(L);}void insertsort2(seqlist L){int i,j;for(i-2;i<=L.len;i++)if(L.stu[i].name<L.stu[i-1].name){L.stu[0]=L.stu[i];for(j=i-1;L.stu[0].name<L.stu[j].name;j--)L.stu[j+1]=L.stu[j];L.stu[j+1]=L.stu[0];}cout<<"排序后学生的信息如下："<<endl;display(L);}int main(){seqlist L;cout<<"创建顺序表"<<endl;create_seq(L);cout<<"输出顺序表"<<endl;display(L);7 cout<<"顺序查找"<<endl;seq_search(L,"赵阳");seq_search(L,"王通");cout<<"折半查找"<<endl;bin_search(L,"7");bin_search(L,"12");cout<<"直接插入排序"<<endl;insertsort2(L);cout<<"直接选择排序"<<endl;selectsort(L);cout<<"冒泡排序"<<endl;bubblesort(L);return 0;}这个代码没法运行出来，vc6显示有一个错误。

查找、排序实验班级B09521 学号20094052127 姓名王海亮一、实验目的1 掌握不同的查找和排序方法，并能用高级语言实现相应算法。

2 熟练掌握顺序查找和二分查找方法。

3 熟练掌握直接插入排序、选择排序、冒泡排序、快速排序。

二、实验内容1 创建给定的静态查找表。

表中共包含十条学生信息，信息如下：学号姓名班级C++ 数据结构1 王立03511 85 762 张秋03511 78 883 刘丽03511 90 794 王通03511 75 865 赵阳03511 60 716 李艳03511 58 687 钱娜03511 95 898 孙胜03511 45 602 使用顺序查找方法，从查找表中查找姓名为赵阳和王夏的学生。

如果查找成功，则显示该生的相关信息；如果查找不成功，则给出相应的提示信息。

3使用快速排序方法，对学生信息中的学号进行排序，然后使用二分查找方法，从查找表中查找学号为7和12的学生。

如果查找成功，则显示该生的相关信息；如果查找不成功，则给出相应的提示信息。

4 使用直接插入排序方法，对学生信息中的姓名进行排序。

输出排序前和排序后的学生信息表，验证排序结果。

5 使用选择排序方法，对学生信息中的C成绩进行排序。

输出排序前和排序后的学生信息表，验证排序结果。

6 使用冒泡排序方法，对学生信息中的数据结构成绩进行排序。

输出排序前和排序后的学生信息表，验证排序结果。

7 编写一个主函数，将上面函数连在一起，构成一个完整程序。

8 调试实验源程序并运行。

三、实验结果程序的源代码如下：#include <iostream>#include <string>#define MAXSIZE 10using namespace std;typedef int KeyType1;typedef string KeyType2;typedef struct{int num;string name;string classnum;int C_score;int shu_score;}DataType;typedef struct //采用顺序存储结构{DataType data[MAXSIZE];int len; //表示长度}SeqList;void Create(SeqList &L) //创建静态表{L.data[0].num=0;L.data[0].name="0";L.data[0].classnum="03511";L.data[0].C_score=0;L.data[0].shu_score=0;L.data[8].num=1;L.data[8].name="王立";L.data[8].classnum="03511";L.data[8].C_score=85;L.data[8].shu_score=76;L.data[6].num=2;L.data[6].name="张秋";L.data[6].classnum="03511";L.data[6].C_score=78;L.data[6].shu_score=88;L.data[3].num=3;L.data[3].name="刘丽";L.data[3].classnum="03511";L.data[3].C_score=90;L.data[3].shu_score=88;L.data[1].num=4;L.data[1].name="王通";L.data[1].classnum="03511";L.data[1].C_score=75;L.data[1].shu_score=86;L.data[5].num=5;L.data[5].name="赵阳";L.data[5].classnum="03511";L.data[5].C_score=60;L.data[5].shu_score=71;L.data[2].num=6;L.data[2].name="李艳";L.data[2].classnum="03511";L.data[2].C_score=58;L.data[2].shu_score=68;L.data[7].num=7;L.data[7].name="钱娜";L.data[7].classnum="03511";L.data[7].C_score=95;L.data[7].shu_score=89;L.data[4].num=8;L.data[4].name="孙胜";L.data[4].classnum="03511";L.data[4].C_score=45;L.data[4].shu_score=60;L.len=9;}void show(SeqList L)//显示函数{cout<<"学号"<<" "<<"姓名"<<" "<<"班级"<<" "<<"C++"<<" "<<"数据结构"<<endl;for(int i=1;i<9;i++){cout<<L.data[i].num<<" "<<L.data[i].name<<" "<<L.data[i].classnum<<""<<L.data[i].C_score<<" "<<L.data[i].shu_score<<endl;}}void name_Search(SeqList L,KeyType2 kx)//按照姓名直接查找{int i=1;while((i<L.len) && (L.data[i].name!=kx))i++;if(i<L.len){ cout<<"姓名为"<<kx<<"的学生的信息如下所示："<<endl;cout<<"学号: "<<L.data[i].num<<endl;cout<<"姓名:"<<L.data[i].name<<endl;cout<<"班级: "<<L.data[i].classnum<<endl;cout<<"C++成绩: "<<L.data[i].C_score<<endl;cout<<"数据结构成绩:"<<L.data[i].shu_score<<endl;}else cout<<"姓名为"<<kx<<"的学生不存在！"<<endl;}int Partition(SeqList &L, int low, int high)//一趟划归算法{int pkey;L.data[0]=L.data[low];pkey=L.data[low].num;while(low<high){ while(low<high && L.data[high].num>=pkey)high--;L.data[low]=L.data[high];while(low<high && L.data[low].num<=pkey)low++;L.data[high]=L.data[low];}L.data[low]=L.data[0];return low;}void num_QSort(SeqList &L,int low,int high)//快速排序（对学号进行排序）{int pivotloc;if(low<high){ pivotloc=Partition(L,low,high);num_QSort(L,low,pivotloc-1);num_QSort(L,pivotloc+1,high);}}void num_Search(SeqList &L,KeyType1 kx)//二分查找（对学号进行查找）{int low=1,high=L.len,mid;int flag=-1;while(low<=high){ mid=(low+high)/2;if(L.data[mid].num>kx){high=mid-1;}else{ if(L.data[mid].num<kx)low=mid+1;else{flag=mid; break;}}}if(flag==-1){ cout<<"学号为"<<kx<<"的学生不存在！"<<endl; return;}if(flag!=0){ cout<<"学号为"<<kx<<"的学生的信息如下所示："<<endl;cout<<"学号: "<<L.data[mid].num<<endl;cout<<"姓名:"<<L.data[mid].name<<endl;cout<<"班级: "<<L.data[mid].classnum<<endl;cout<<"C++成绩: "<<L.data[mid].C_score<<endl;cout<<"数据结构成绩:"<<L.data[mid].shu_score<<endl;}}void name_InsertSort(SeqList &L) //直接插入排序（按照姓名进行排序）{int i, j;for(i=2;i<L.len;++i )if (L.data[i].name<L.data[i-1].name){ L.data[0]=L.data[i];for(j=i-1; L.data[0].name<L.data[j].name; --j )L.data[j+1]=L.data[j];L.data[j+1]=L.data[0];}}void C_SelectSort(SeqList &L)//选择排序（按照C++成绩进行从小到大进行排序）{int i,j,k;DataType x;for(i=1;i<L.len;i++){for(k=i,j=i+1;j<L.len;j++){if(L.data[j].C_score<L.data[k].C_score) k=j;}if(i!=k){ x=L.data[k];L.data[k]=L.data[i];L.data[i]=x; }}}void shu_BubbleSort(SeqList &L )//冒泡排序（按照数据结构成绩从小到大进行排序）{int i,j,swap;DataType temp;for( i=1;i<L.len-1;i++){ swap=0;for(j=1;j<=L.len-i;j++){ if(L.data[j+1].shu_score>L.data[j].shu_score){ temp=L.data[j+1];L.data[j+1]=L.data[j];L.data[j]=temp;swap=1;}}if(swap==0) break;}}void main(){SeqList L;Create(L);cout<<"学生原始信息表如下所示："<<endl;show(L);cout<<endl;cout<<"查找姓名为赵阳的学生信息情况如下："<<endl;name_Search(L,"赵阳");cout<<endl;cout<<"查找姓名为王夏的学生信息情况如下："<<endl;name_Search(L,"王夏");cout<<endl;cout<<"运用快速排序法按照学号从大到小进行排序结果如下："<<endl;num_QSort(L,1,8);show(L);cout<<endl;cout<<"查找学号为7的学生的信息如下："<<endl;num_Search(L,7);cout<<endl;cout<<"查找学号为12的学生的信息如下："<<endl;num_Search(L,12);cout<<endl;cout<<"运用直接插入排序法按照姓名进行排序结果如下："<<endl;name_InsertSort(L);show(L);cout<<endl;cout<<"运用选择排序法按照C++成绩从大到小进行排序结果如下："<<endl;C_SelectSort(L);show(L);cout<<endl;cout<<"运用冒泡排序法按照数据结构成绩从大到小进行排序结果如下："<<endl;shu_BubbleSort(L);show(L);cout<<endl;}程序运行结果如下图所示：图1图2（上接图1）图3（上接图2）图4（上接图3）四、实验总结1、通过本次实验对静态表的直接查找和折半查找有了深刻的认识，并理解了它们的思想和算法，同时对直接插入排序、选择排序以及冒泡排序有了深刻的认识，实验中运用直接插入排序对姓名进行排序，运用选择排序对C++成绩从小到大进行排序，运用冒泡排序对数据结构成绩进行从大到小进行排序。

第1篇一、实验目的1. 了解排序检验的基本原理和适用条件。

2. 掌握排序检验的步骤和方法。

3. 通过实际操作，验证排序检验的有效性。

二、实验背景排序检验（Rank Test）是一种非参数检验方法，适用于检验两组或多组数据是否存在显著差异。

当数据不符合正态分布，或者数据量较小，无法使用参数检验时，排序检验是一种较好的选择。

三、实验材料1. 实验数据：两组或多组数据，每组数据包含多个观测值。

2. 计算工具：Excel、SPSS等统计软件。

四、实验步骤1. 收集实验数据，确保数据符合排序检验的适用条件。

2. 对每组数据进行排序，从大到小排列。

3. 计算每组的秩和，即每组的观测值在排序后所在的位置。

4. 计算各组秩和的平均值和标准差。

5. 计算检验统计量，即各组秩和的平均值之差除以标准差。

6. 根据检验统计量，查找相应的临界值表，确定显著性水平。

7. 判断两组或多组数据是否存在显著差异。

五、实验结果与分析1. 实验数据实验数据如下：组别1：[12, 15, 18, 20, 22]组别2：[10, 14, 17, 19, 21]2. 排序及秩和计算对两组数据进行排序，得到以下结果：组别1：[22, 20, 18, 15, 12]组别2：[21, 19, 17, 14, 10]计算秩和：组别1秩和 = 22 + 20 + 18 + 15 + 12 = 87组别2秩和 = 21 + 19 + 17 + 14 + 10 = 883. 检验统计量计算计算各组秩和的平均值和标准差：组别1平均值 = 87 / 5 = 17.4组别2平均值 = 88 / 5 = 17.6组别1标准差= √[(22-17.4)² + (20-17.4)² + (18-17.4)² + (15-17.4)² + (12-17.4)²] / 4 = 3.16组别2标准差= √[(21-17.6)² + (19-17.6)² + (17-17.6)² + (14-17.6)² + (10-17.6)²] / 4 = 3.16计算检验统计量：检验统计量 = (组别1平均值 - 组别2平均值) / 组别1标准差 = (17.4 - 17.6) / 3.16 = -0.01594. 判断显著性根据检验统计量，查找相应的临界值表，以显著性水平α=0.05为例，临界值为1.96。

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

二、实验内容#include""#include""#include""#include""#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-00)%11);}void insert(RNode t[],RNode x) /*插入函数，以线性探查方法解决冲突*/ {int i,j=0;i=h;while((j<MAX)&&(t[(i+j)%MAX].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==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>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;=310900***;strcpy," ***");=90;insert(t,x);break;}case 1:{RNode x;=31090***1;strcpy," ***");=95;insert(t,x);break;}case 2:{RNode x;=3109005***;strcpy," ***");=92;insert(t,x);break;}case 3:{RNode x;=31090***;strcpy," ***");=93;insert(t,x);break;}case 4:{RNode x;=3109005***;strcpy," ***");=94;insert(t,x);break;}case 5:{RNode x;=310900***;strcpy," ***");=91;insert(t,x);break;}case 6:{RNode x;=3109005***;strcpy," ***");=96;insert(t,x);break;}case 7:{RNode x;=310900***;strcpy," ***");=99;insert(t,x);break;}case 8:{RNode x;=310900***;strcpy," ***");=98;insert(t,x);break;}case 9:{RNode x;=310900***;strcpy,"***");=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",&;s=search(t,;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）排序四、总结这次的课程实验完成了主控界面，录入，输出，排序，查找，结束界面等功能。