资源描述：
《数据结构查找实验.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、实验四查找一、实验目的或任务通过指导学生上机实践，对常用数据结构的基本概念及其不同的实现方法的理论得到进一步的掌握，并对在不同存储结构上实现不同的运算方式和技巧有所体会。二、实验教学基本要求1.了解实验目的及实验原理；2.编写程序，并附上程序代码和结果图；3.总结在编程过程中遇到的问题、解决办法和收获。三、实验教学的内容或要求1.编写函数,建立有序表,采用折半查找实现某一已知的关键字的查找(采用顺序表存储结构)2.编写函数,随机产生一组关键字,利用二叉排序树的插入算法建立二叉排序树3.编写函数,在以上二叉排序树中
2、删除某一指定关键字元素4.编写一个主函数,在主函数中设计一个简单的菜单,分别调试上述算法四、实验类型或性质验证性五、实验开出要求必做六、实验所需仪器设备1.计算机2.相关软件（如C,C++,PASCAL,VC,DELPHI等等）七、实验所用材料计算机耗材八.运行结果1.建立有序表,采用折半查找实现某一已知的关键字的查找(采用顺序表存储结构)选择1，用折半查找法查找一个关键字，输入关键字长度，输入元素，输入要查找的数，则输出该关键字的序号，如下图2-1所示。图2-1采用折半查找实现某一已知的关键字的查找2.随机产生
3、一组关键字,利用二叉排序树的插入算法建立二叉排序树选择2，随机输入一组数据（以000结尾），输出二叉排序树，如下图2-2所示图2-2随机产生一组关键字,利用二叉排序树的插入算法建立二叉排序树3.在以上二叉排序树中删除某一指定关键字元素选择3，输入要删除的关键字元素，输出删除成功与否与删除关键字元素后的二叉排序树，如下图2-3所示图2-3在以上二叉排序树中删除某一指定关键字元素附录实验程序代码#include#includetypedefstructNode{intdata;s
4、tructNode*lchild,*rchild;}NodeType;typedefstruct{intnum;}datatype;typedefstruct{datatype*data;intlength;}S_TBL;intSearchData(NodeType*T,NodeType**p,NodeType**q,intkx){intflag=0;*q=T;while(*q){if(kx>(*q)->data){*p=*q;*q=(*q)->rchild;}else{if(kx<(*q)->data){*p=
5、*q;*q=(*q)->lchild;}else{flag=1;break;}}}returnflag;}intInsertNode(NodeType**T,intkx){intflag=0;NodeType*p=*T,*q,*s;if(!SearchData(*T,&p,&q,kx)){s=(NodeType*)malloc(sizeof(NodeType));s->data=kx;s->lchild=NULL;s->rchild=NULL;if(p==NULL){*T=s;}else{if(kx>p->dat
6、a)p->rchild=s;elsep->lchild=s;}flag=1;}returnflag;}intDeleteNode(NodeType**T,intkx){intflag=0;NodeType*p=*T,*q,*s,**f;if(SearchData(*T,&p,&q,kx)){if(p==q){f=T;}else{f=&(p->lchild);if(kx>p->data)f=&(p->rchild);}if(q->rchild==NULL){*f=q->lchild;}else{if(q->lchi
7、ld==NULL){*f=q->rchild;}else{p=q->rchild;s=p;while(p->lchild){s=p;p=p->lchild;}*f=p;p->lchild=q->lchild;if(s!=p){s->lchild=p->rchild;p->rchild=q->rchild;}}}free(q);flag=1;}returnflag;}voidInOrder(NodeType*bt){if(bt==NULL)return;InOrder(bt->lchild);printf("t%
8、5d",bt->data);InOrder(bt->rchild);}intBinary_Search(S_TBL*tbl,intkx){intlow,high,mid,flag;flag=0;low=1;high=tbl->length;while(low<=high){mid=(low+high)/2;if(kxdata[mid].num){high=mi
