查找、排序的应用实验

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

1、浪海工曇浣针篇机科曇系实验报告书课程名：《数据结构》题目：查找、排序的应用实验班级：学号：姓名：评语：成绩：指导教师：批阅吋间：年月日排序、查找的应用实验报告要求1目的与要求：1）查找、排序是LI常数据处理过程中经常要进行的操作和运算，学握其算法与应用对于提高学生数据处理能力和综合应用能力显得卜分重要。2）本次实验前，要求同学完整理解有关排序和查找的相关算法和基本思想以及种算法使川的数据存储结构；3）利用C或C++语言独立完成本次实验内容或题目，程序具有良好的交互性（以菜单机制实现实验程序的交互运行）和实用性；4）木次实验在机房现场验收和平分，希望同学们认真对待，并按时完成实验任务

2、；5）认真书写实验报告（包括程序清单及相关实验数据与完整运行结果），并于卜周周三以前提交（12月11n）按时提交。2实验内容或题目题冃：对记录序列（查找表）：{55,13,23,72,109,67,2,7&更}分别实现如下操作：1）顺序査找；2）分别使用直接插入排序、冒泡排序、快速排序对原纪录序列进行排序；（愆没学，可以H己排序）3）对排好序的纪录序列表进行折半杳找；4）利用1）中记录序列建立一颗二叉排序树，并在其上实现特定关键字值结点的查找；5）按照“除帘余数法”哈希构造函数和线性探测再散列的冲突处理方法创建表长为m=ll的哈希表;6）实现5）创建哈希表上的查找。注释：上述实验内

3、容（即各种查找功能）请使用菜单机制以交互方式实现操作。3实验步骤与源程序ttinclude★include#include#defineLTST_STZE20#defineTRUE1SdefineFALSE0#defineSUCCESS1tfdefineUNSUCCESS-1#defineMAXSIZE100typedefcharKeyType;typedefintOtherType;typedefstruct{KeyTypekey;OtherTypeother_data;}RccordTypo;typedefstructR

4、ecordTyper[LIST_SIZE+1];/*讥0]为工作单元*/intIongth;}RecordList;〃二叉排序树的创建与杏找#defineENDKEY0typedefstructnode{KeyTypekey;/*关键字的值*/structnode*lchild,*rch订d;/*左右指针*/}BSTNode,*BSTree;/*哈希表的创建*/typedefstruct{intkey;intflag;//fla沪1时表示有关键字，flag=0时表示没冇关键字}Elemtype;typedefstruct{Elemtype*elem;//动态分配哈希表的首地址int

5、sizeindex;//hashsize[sizeindex]为当前容量intcount;//当前数据元素个数}HashTable;voidcreatelist(RecordList*1){inti;intIon;KeyTypech;printfC请输入线性表的长度：〃)；scanf&len);l->length=len;for(i=l;i<=len;i++){printfC请输入线性表的第％d个元素：〃，i);fflush(stdin);scanf&ch);l->r[i].key=ch;voidSeqSearch(RecordList1,KeyTypek)/*在顺序表1中顺序査找

6、其关键字等于k的元素，若找到，则函数值为该元素在表中的位置，否则为0*/inti;1.r[0].key二k;i=l.length;while(1.r[i].key!=k)i--;if(i>=l){printfC该元素所在的位置是：〃)；printf("%d",i);}elseprintfC^找失败!“)；}voidInsSort(RecordTyper[],intlength)/*对记录数组r做点接插入排序‘length为数组中待排序记录的数目*/{inti,j；for(i=2;i<=length;i++){r[0]=r[i];/*将待插入记录存放到监视哨r[0]中*/j=i-l；

7、while(r[0].key