多种查找算法实现及其比较

《多种查找算法实现及其比较》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、广西工学院计算机学院《数据结构》课程实验报告书实验八多种查找算法实现及其比较学生姓名：学号：班级：计指导老师专业：计算机学院软件学院提交日期：2013年6月28日-22-1．实验目的1）掌握常见的静态查找表和动态查找表的表示和操作方法。2）能根据具体的查找方法设计合理的查找表的数据结构。2.实验内容1）用静态查找结构实现静态查找算法，包括顺序查找—用顺序表、链表（流程图）折半查找—用有序顺序表（流程图）基本操作：Create(&ST,n);//构造含有n个元素的静态查找表STDestroy(&ST);//销毁表Search(ST

2、,key);//查找关键字为key的数据元素Traverse(ST,visit());//遍历查找表数据结构定义：typedefstruct{intkey;}Eletype;typedefstruct{Elemtype*elem;intlength;}SSTable;#defineBLOCK_NUM32）用动态查找结构实现动态查找算法，包括二叉排序树—无重复关键字AVL树—平衡二叉排序树动态查找：表结构本身是在查找过程中动态生成的。基本操作：InitDSTable(&DT);//构造一个空的动态查找表DTDestroyDSTab

3、le(&DT);//销毁表SearchDSTable(DT,key);//查找关键字为key的数据元素-22-InsertDSTable(&DT,e);DeleteDSTable(&DT,key);TraverseDSTable(DT,visit());//遍历查找表二叉排序树的数据类型描述：typedefstruct{intkey;}ElemType;typedefstructBiTNode{ElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;3）．用以上方法中

4、的一种，编程实现在n个数据（n>=10）中查找某个数3．实验要求（1）上机前交实验源程序（纸质版），由学习委员统一收好交老师（附上不交同学名单）。（2）用一切你能想到的办法解决遇到的问题，培养解决问题的能力。（3）实验课上进行答辩。（4）实验报告当场交。报告内容包括：实验目的、实验内容、实验代码、实验运行结果以及实验体会供五部分。3．主要算法3.1顺序存储结构（1）结构定义：#include#include#include#include//各头文件#d

5、efineN10#defineOK1#defineERROR0#defineOVERFLOW-2typedefintkeyType;//设关键字域为长整型-22-typedefintTElemType;//定义宏参//定义静态表存储结构typedefstruct{TElemType*elem;//定义数据类型intlength;//记录当前长度}SSTable;//定义动态表存储结构typedefstruct{intkey;//关键字}ElemType;//定义动态表指针typedefstructBiTNode{ElemType

6、data;//定义数据类型structBiTNode*lchild;//左孩子指针structBiTNode*rchild;//右孩子指针}BiTNode,*BiTree;voidInsert_BST(BiTree&T,BiTreeS);intDelete(BiTree&p);//建立静态表voidCreat_seq(SSTable&ST,TElemTyper[],intn){//操作结果:建立一个静态表-22-inti;ST.elem=(TElemType*)calloc(n+1,sizeof(TElemType));//分配

7、存储空间if(!ST.elem)//分配存储空间失败exit(0);for(i=1;i<=n;i++)//把r中的数据元素复制给STST.elem[i]=r[i];ST.length=n;////记录当前长度}//静态表清空voidClear(SSTable&ST){//初始条件:静态表已存在//操作结果:清空静态表inti=ST.length;for(i=1;i<=ST.length;i++)//把ST当前长度赋值为0ST.elem[i]=0;return;}//静态顺序查找intsearch_seq(SSTableST,ke

8、yTypekey){//初始条件:静态表已存在//操作结果:在顺序表中顺序查找其关键字等于key的数据元素，//若存在，则返回该元素，否则返回0inti=ST.length;ST.elem[0]=key;while(ST.elem[i]!=key)--i;-22