查找、排序应用实验

1、精选优质文档-倾情为你奉上淮海工学院计算机科学系实验报告书课程名： 数据结构 题 目： 查找、排序的应用实验 班 级： 学 号： 姓 名： 评语：成绩： 指导教师： 批阅时间： 年 月 日专心-专注-专业排序、查找的应用实验报告要求1目的与要求:1）查找、排序是日常数据处理过程中经常要进行的操作和运算，掌握其算法与应用对于提高学生数据处理能力和综合应用能力显得十分重要。2）本次实验前，要求同学完整理解有关排序和查找的相关算法和基本思想以及种算法使用的数据存储结构；3）利用C或C+语言独立完成本次实验内容或题目，程序具有良好的交互性（以菜单形式列出实验排序和显示命令，并可进行交互操作）和实用性；

2、4）本次实验为实验成绩评定主要验收内容之一，希望同学们认真对待，并按时完成实验任务；5）本次实验为综合性实验，请于2012年12月23日按时提交实验报告（纸质报告每班10份）；6）下周开始数据结构课程设计，务必按时提交实验报告，任何同学不得拖延。2 实验内容或题目题目：对记录序列（查找表）：287，109，063，930，589，184，505，269,008，083分别实现如下操作：1) 分别使用直接插入排序、冒泡排序、快速排序、简单选择排序、堆排序（可选）、链式基数排序算法对纪录序列进行排序，并显示排序结果；2) 对上述纪录列表排好序，然后对其进行折半查找或顺序查找；（特别要求：使用菜单机

3、制，在一个主程序下实现题目要求的排序和查找以及结果显示）3 实验步骤与源程序#include <stdio.h>#include <stdlib.h>/*链式基数法排序声明*/ #define RADIX 10#define KEY_SIZE 6#define LIST_SIZE 20#define TRUE 1#define FALSE 0typedef int KeyType;typedef int OtherType;typedef struct KeyType keyKEY_SIZE; /* 子关键字数组 */ OtherType other_data; /*

4、其它数据项 */ int next; /* 静态链域 */ RecordType1;typedef struct RecordType1 rLIST_SIZE+1;/* r0为头结点 */int length;int keynum;SLinkList; /* 静态链表 */typedef int PVectorRADIX;typedef structint next;KeyType key;OtherType other_data;RecordType;void InsSort(RecordType r, int length)/* 对记录数组r做直接插入排序，length为数组中待排序记录的

5、数目*/ int i,j;for (i=2; i<=length; i+) r0=ri; /*将待插入记录存放到监视哨r0中*/j=i-1; while (r0.key< rj.key ) /* 寻找插入位置 */rj+1= rj; j=j-1;rj+1=r0; /*将待插入记录插入到已排序的序列中*/ /* InsSort */ /顺序查找void SeqSearch(RecordType r,int length,KeyType k)int i;r0.key=k;i=length;while(ri.key!=k) i-;printf("该元素在数组中的位置是%d&qu

6、ot;,i);/冒泡排序void BubbleSort(RecordType r, int length )/*对记录数组r做冒泡排序，length为数组的长度*/int n,i,j;int change;RecordType x;n=length; change=TRUE;for ( i=1 ; i<= n-1 && change ;+i ) change=FALSE;for ( j=1 ; j<= n-i ; +j) if (rj.key > rj+1.key ) x= rj;rj= rj+1;rj+1= x;change=TRUE; /* BubbleS

7、ort */ 快速排序int QKPass(RecordType r,int left,int right)/*对记录数组r 中的rleft至rright部分进行一趟排序，并得到基准的位置，使得排序后的结果满足其之后（前）的记录的关键字均不小于（大于）于基准记录*/ RecordType x;int low,high;x= rleft; /* 选择基准记录*/ low=left; high=right;while ( low<high )while (low< high && rhigh.key>=x.key ) /* high从右到左找小于x.key的记录

8、*/high-;if ( low <high ) rlow= rhigh;low+; /* 找到小于x.key的记录，则进行交换*/while (low<high && rlow.key<x.key ) /* low从左到右找大于x.key的记录 */low+; if ( low<high ) rhigh= rlow;high-; /* 找到大于x.key的记录，则交换*/rlow=x; /*将基准记录保存到low=high的位置*/return low; /*返回基准记录的位置*/ /* QKPass */ void SelectSort(Record

9、Type r,int length)/*对记录数组r做简单选择排序，length为数组的长度*/int i,j,k,n; RecordType x;n=length;for(i=1;i<=n-1;+i)k=i;for(j=i+1;j<=n;+j)if(rj.key<rk.key) k=j;if(k!=i)x=ri;ri=rk;rk=x;void QKSort(RecordType r,int low, int high )/*对记录数组rlow.high用快速排序算法进行排序*/int pos;if(low<high)pos=QKPass(r, low, high);

10、/*调用一趟快速排序，将枢轴元素为界划分两个子表*/QKSort(r, low, pos-1); /*对左部子表快速排序*/QKSort(r, pos+1, high); /*对右部子表快速排序*/ 堆排序void sift(RecordType r, int k, int m)/* 假设k.m是以k为根的完全二叉树，且分别以2k和2k+1为根的左、右子树为大根堆，调整rk，使整个序列rk.m满足堆的性质 */RecordType t;int i,j;int x;int finished;t= rk; /* 暂存"根"记录rk */ x=rk.key;i=k;j=2*i;f

11、inished=FALSE;while( j<=m && !finished ) if (j<m && rj.key< rj+1.key ) j=j+1; /* 若存在右子树，且右子树根的关键字大，则沿右分支"筛选" */if ( x>= rj.key)finished=TRUE; /* 筛选完毕 */ else ri = rj;i=j;j=2*i; /* 继续筛选 */ ri =t; /* rk填入到恰当的位置 */ void crt_heap(RecordType r, int length )/*对记录数组r建堆

12、，length为数组的长度*/int i,n; n= length;for ( i=n/2; i >= 1; -i) /* 自第n/2个记录开始进行筛选建堆 */ sift(r,i,n);void HeapSort(RecordType r,int length)/* 对r1.n进行堆排序，执行本算法后，r中记录按关键字由大到小有序排列 */ int i,n;RecordType b;crt_heap(r, length);n= length;for ( i=n ; i>= 2; -i) b=r1; /* 将堆顶记录和堆中的最后一个记录互换 */ r1= ri;ri=b; sift

13、(r,1,i-1); /* 进行调整，使r1.i-1变成堆 */ /* HeapSort */链式基数排序void Distribute(RecordType1 r, int i, PVector head, PVector tail)/* 记录数组r中记录已按低位关键字keyi+1，keyd进行过"低位优先"排序。本算法按第i位关键字keyi建立RADIX个队列，同一个队列中记录的keyi相同。headj和tailj分别指向各队列中第一个和最后一个记录（j=0，1，2，RADIX-1）。headj=0表示相应队列为空队列*/ int j;int p;for ( j=0 ;

14、 j<=RADIX-1 ; +j)headj=0; /* 将RADIX个队列初始化为空队列 */ p= r0.next; /* p指向链表中的第一个记录 */ while( p!=0 ) j=rp.keyi; /* 用记录中第i位关键字求相应队列号 */if ( headj=0 ) headj=p; /* 将p所指向的结点加入第j个队列中 */ elsertailj.next=p;tailj=p;p= rp.next; /* Distribute */ void Collect(RecordType1 r, PVector head, PVector tail)/* 本算法从0到RADI

15、X-1 扫描各队列，将所有非空队列首尾相接，重新链接成一个链表 */ int j;int t;j=0;while (headj=0 ) /* 找第一个非空队列 */ +j;r0.next =headj;t=tailj;while ( j<RADIX-1 ) /* 寻找并串接所有非空队列 */+j;while ( (j<RADIX-1 ) && (headj=0 ) ) /* 找下一个非空队列 */ +j;if ( headj!=0 ) /* 链接非空队列 */ rt.next =headj;t=tailj; rt.next =0; /* t指向最后一个非空队列中的最

16、后一个结点 */ /* Collect */ void RadixSort (RecordType1 r,int length )/* length个记录存放在数组r中，执行本算法进行基数排序后，链表中的记录将按关键字从小到大的顺序相链接。 */ int i,n;int d;PVector head;PVector tail; n= length;for ( i=0 ; i<= n-1 ; +i) ri.next=i+1; /* 构造静态链表 */rn.next =0;d= 3;for ( i =d-1; i>= 0; -i ) /* 从最低位子关键字开始，进行d趟分配 和 收集*

17、/ Distribute(r,i,head,tail); /* 第i趟分配 */ Collect(r,head,tail); /* 第i趟收集 */ /* RadixSort */void main()int flag=1,i,j,k,b;RecordType r20;int len;printf("*功能菜单*n");printf("1.直接插入排序; 2.冒泡排序;n");printf("3.快速排序; 4.简单选择排序;n");printf("5.堆排序; 6.顺序查找;n");printf("7.

18、链式基数排序; 8.退出;n");printf("请输入待排序记录的长度:");scanf("%d",&len);for(i=1;i<=len;i+)printf("请输入第%d个记录元素:",i);fflush(stdin);scanf("%d",&j);ri.key = j;printf("原记录序列：");for(i=1;i<=len;i+)printf("%d ",ri.key);printf("n");whi

19、le(flag)printf("请选择操作："); scanf("%d",&b);switch(b)case 1:/ 直接插入排序printf("n直接插入排序结果：n");InsSort(r,len);for(i=1;i<=len;i+)printf("%d ",ri.key);printf("n");break;case 2:/冒泡排序printf("冒泡排序结果：n");BubbleSort(r,len);for(i=1;i<=len;i+)prin

20、tf("%d ",ri.key);printf("n");break;case 3:/ 快速排序printf("快速排序结果：n");QKSort(r,1,len);for(i=1;i<=len;i+)printf("%d ",ri.key);printf("n");break;case 4:/简单选择排序SelectSort(r,len);for(i=1;i<=len;i+)printf("%d ",ri.key);printf("n");b

21、reak;case 5:/ 堆排序printf("堆排序结果：n");HeapSort(r,len); for(i=1;i<=len;i+)printf("%d ",ri.key);printf("n");break;case 6:/进行顺序查找printf("请输入您要查找的元素：");fflush(stdin);scanf("%d",&k);SeqSearch(r,len,k);printf("n");break; case 7:/链式基数排序 RecordType1 a20; in