数据结构实验 查找

《数据结构实验 查找》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验名称：查找班级：学号：姓名：报告日期：一、实验目的及要求1.了解实验目的及实验原理；2.编写程序，并附上程序代码和结果图；3.总结在编程过程中遇到的问题、解决办法和收获。二、实验内容1.编写函数,建立有序表,采用折半查找实现某一已知的关键字的查找(采用顺序表存储结构);2.编写函数,随机产生一组关键字,利用二叉排序树的插入算法建立二叉排序树;3.编写函数,在以上二叉排序树中删除某一指定关键字元素;4.编写一个主函数,在主函数中设计一个简单的菜单,分别调试上述算法.三、实验结果四、实验总结这次实验是对查找算法的编程实现，而

2、查找算法有很多，这次我选的是折半法。折半法其实和我们以往学的二分法有很大的相似，所以对算法的理解较为容易。主要难以解决则是编程的实现，但是在老师、同学以及网络的帮助下，最终勉强的编写出程序。而其中也再此让我感受到了循环算法的妙用，这次没有用for语句作循环，用的是switch语句，使我对其用法更加熟练，其次，还是老话，细心最重要，一定要注意细节。附录#include#include#defineLIST_SIZE20#defineENDKEY0#includetypede

3、fintKeyType;typedefintOtherType;typedefstructnode{KeyTypekey;/*关键字的值*/structnode*lchild,*rchild;/*左右指针*/}BSTNode,*BSTree;typedefstruct{KeyTypekey;OtherTypeother_data;}RecordType;typedefstruct{RecordTyper[LIST_SIZE+1];/*r[0]为工作单元*/intlength;}RecordList;voidcreatelis

4、t(RecordList*l){inti;intlen;KeyTypech;printf("请输入线性表的长度:");scanf("%d",&len);l->length=len;for(i=1;i<=len;i++){printf("请输入线性表的第%d个元素:",i);fflush(stdin);scanf("%c",&ch);l->r[i].key=ch;}}intBinSrch(RecordListl,KeyTypek)/*在有序表l中折半查找其关键字等于k的元素，若找到，则函数值为该元素在表中的位置*/{intlo

5、w,high,mid;low=1;high=l.length;/*置区间初值*/while(low<=high){mid=(low+high)/2;if(k==l.r[mid].key)return(mid);/*找到待查元素*/elseif(k

6、y的元素，插入该元素*/{BSTrees;if(*bst==NULL)/*递归结束条件*/{s=(BSTree)malloc(sizeof(BSTNode));/*申请新的结点s*/s->key=key;s->lchild=NULL;s->rchild=NULL;*bst=s;}elseif(key<(*bst)->key)InsertBST(&((*bst)->lchild),key);/*将s插入左子树*/elseif(key>(*bst)->key)InsertBST(&((*bst)->rchild),key);/*

7、将s插入右子树*/}/*intInsertBST(BSTree*bst,KeyTypeK){BSTreef,q,s;s=(BSTree)malloc(sizeof(BSTNode));s->key=K;s->lchild=NULL;s->rchild=NULL;if(*bst==NULL){*bst=s;return1;}f=NULL;q=*bst;while(q){if(q->key==K)return0;if(Kkey){f=q;q=q->lchild;}else{f=q;q=q->rchild;}}if(K

8、->key)f->lchild=s;elsef->rchild=s;return1;}*/voidCreateBST(BSTree*bst)/*从键盘输入元素的值，创建相应的二叉排序树*/{KeyTypekey;*bst=NULL;inti;srand((unsigned)time(NUL