查找排序综合实验

查找、排序综合实验 淮海工学院计算机科学系 实验报告书

课程名：《数据结构》 题目：搜寻、排序综合实验 班级：学号：姓名：

评语：成绩：指导教师：审阅时间：年月日 《数据结构》实验报告-1-

排序、搜寻的应用领域实验报告建议 1目的与要求:

1）搜寻、排序就是日常数据处理过程中经常必须展开的操作方式和运算，掌控其算法与应用领域对于提升学生数据处理能力和综合应用领域能力变得十分关键。

2）本次实验前，要求同学完整理解有关排序和查找的相关算法和基本思想以及种算法使用的数据存储结构；

3）利用c或c++语言单一制顺利完成本次实验内容或题目，程序具备较好的交互性（以菜单机制同时实现实验程序的可视化运转）和实用性；

4）本次实验在机房现场验收和平分，希望同学们认真对待，并按时完成实验任务；5）认真书写实验报告（包括程序清单及相关实验数据与完整运行结果），并于16周周五前提交，综合实验纸质报告每班收10份。 2实验内容或题目

题目：对记录序列（查找表）：{55，13，23，72，109，67，02，78,13}分别实现如下操作： 1)顺序搜寻；

2)分别使用直接插入排序、冒泡排序、快速排序对原纪录序列进行排序（本次要做）；3)对排好序的纪录序列表进行折半查找；

4)利用原纪录序列创建一颗二叉排序一棵，并在其上时同时实现特定关键字值结点的搜寻；5)按照“除领余数法”哈希构造函数和线性观测再杂凑的冲突处置方法建立表长为m=11的哈希表中 （本次实验做）；

6)同时实现5）建立哈希单上的搜寻。

7)看懂书上“链式基数排序”方法的分配收集排序举例，并以书上例题为例，实现这种排序方法。 （选并作） 3实验步骤与源程序

#include#include#definemaxsize12#definetrue1#definefalse0#definenull0#definelistsize9#definekeysize9#definemax100#defineradix9 typedefintkeytype;typedefstruct{ intkey;

《数据结构》实验报告-2- intflag;}elemtype; typedefstruct{

elemtype*elem;intsizeindex;intcount;}hashtable; typedefstructnode{ intkey;

structnode*lchild,*rchild;}bstnode,*bstree; typedefstruct{

intkey;intnext;}recordtype;typedefstruct{

keytypekey[keysize];inttype;intnext;}recordtype1;typedefstruct{ recordtype1r[keysize+1];intlength;intkeynum;}slinklist; typedefstruct{

recordtyper[listsize+1];intlength;}recordlist; typedefintpvector[radix];//建立哈希表中 intcreathashtable(hashtable*h,intm){ inti,keys,p,len;

h->elem=(elemtype*)malloc(sizeof(elemtype));h->sizeindex=max; 《数据结构》实验报告-3- h->count=0; cout<>m; cout<>len;

h->sizeindex=len;for(i=0;ielem[i].flag=0;} cout<

cin>>keys;p=keys%m; while(h->elem[p].flag==1){ intd=1; p=(p+d)%m;d++;}

h->elem[p].key=keys;h->elem[p].flag=1;h->count++;} for(intj=h->count;jelem[j].key=0; cout< cout< cout<