查找、排序的应用实验.doc

《查找、排序的应用实验.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

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

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

3、使用菜单机制，在一个主程序下实现题目要求的排序和查找以及结果显示）3实验步骤与源程序#include#include/*链式基数法排序声明*/#defineRADIX10#defineKEY_SIZE6#defineLIST_SIZE20#defineTRUE1#defineFALSE0typedefintKeyType;typedefintOtherType;typedefstruct{KeyTypekey[KEY_SIZE];/*子关键字数组*/OtherTypeother_data;/*其它数据项*/intne

4、xt;/*静态链域*/}RecordType1;typedefstruct{RecordType1r[LIST_SIZE+1];/*r[0]为头结点*/intlength;intkeynum;}SLinkList;/*静态链表*/typedefintPVector[RADIX];typedefstruct{intnext;KeyTypekey;OtherTypeother_data;}RecordType;voidInsSort(RecordTyper[],intlength)/*对记录数组r做直接插入排序，length为数组中待排序记录的数目*/{in

5、ti,j;for(i=2;i<=length;i++){r[0]=r[i];/*将待插入记录存放到监视哨r[0]中*/j=i-1;while(r[0].key

6、的位置是%d",i);}//冒泡排序voidBubbleSort(RecordTyper[],intlength)/*对记录数组r做冒泡排序，length为数组的长度*/{intn,i,j;intchange;RecordTypex;n=length;change=TRUE;for(i=1;i<=n-1&&change;++i){change=FALSE;for(j=1;j<=n-i;++j)if(r[j].key>r[j+1].key){x=r[j];r[j]=r[j+1];r[j+1]=x;change=TRUE;}}}/*BubbleSort*//

7、/快速排序intQKPass(RecordTyper[],intleft,intright)/*对记录数组r中的r[left]至r[right]部分进行一趟排序，并得到基准的位置，使得排序后的结果满足其之后（前）的记录的关键字均不小于（大于）于基准记录*/{RecordTypex;intlow,high;x=r[left];/*选择基准记录*/low=left;high=right;while(low=x.key)/*high从右到左找小于x.key的记录*/high--;if(low

8、