实验 4查找成绩一、实验目的或任务 通过指导学生上机实践，对常用数据结构的基本概念及其不同的实现方法的 理论得到进一步的掌握，并对在不同存储结构上实现不同的运算方式和技巧有所 体会。二、实验教学基本要求1. 了解实验目的及实验原理；2. 编写程序，并附上程序代码和结果图；3. 总结在编程过程中遇到的问题、解决办法和收获。三、实验教学的内容或要求1. 编写函数,建立有序表,采用折半查找实现某一已知的关键字的查找（采用顺 序表存储结构）2. 编写函数,随机产生一组关键字,利用二叉排序树的插入算法建立二叉排序 树3. 编写函数,在以上二叉排序树中删除某一指定关键字元素4. 编写一个主函数,在主函数中设计一个简单的菜单,分别调试上述算法四、实验类型或性质验证性五、实验开出要求必做六、实验所需仪器设备1.计算机2.相关软件（如 C,C+,PASCAL,VC,DELPHI 等等）七、实验所用材料 计算机耗材一、程序运行界面：3 7 ? 10 5 8 4 -17tn.62 结T点 叉餌树 二上X 立树二 幵二薯:3=3查 项组Ksr项4:麥 ； 口选-选要功选选长元你选意 U入入入入成入丁入入入入一一入任 ? 2 SUB 沪 主垦后青青刪土月 青主星星月应青青5勺4找回练2 ft项键- -Is.-二、源程序#define _CRT_SECURE_NO_WARNINGS#include#include#define MAXNODE 256 typedefstruct Nodeint data;struct Node *lchild,*rchild;NodeType;typedefstructint num;datatype;typedefstructdatatype *data;int length;S_TBL;int SearchData(NodeType *T,NodeType *p,NodeType * int kx) int flag=0;*q=T;while(*q)if(kx(*q)-data)*p=*q;*q=(*q)-rchild;elseif(kxdata)*p=*q;*q=(*q)-lchild;elseflag=1;break;return flag;int InsertNode(NodeType *Tint kx)int flag=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;elseif(kxp-data) p-rchild=s;p-lchild=s;flag=1;return flag;int DeleteNode(NodeType *Tint kx)int flag=0;NodeType *p=*T,*q,*s,*f; if(SearchData(*T,&p,&q,kx) if(p=q)f=T;elsef=&(p-lchild);if(kxp-data)f=&(p-rchild);if(q-rchild=NULL)*f=q-lchild;elseif(q-lchild=NULL)*f=q-rchild;elsep=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;return flag;void InOrder(NodeType *bt)if(bt=NULL) return; InOrder(bt-lchild); printf(%3d,bt-data); InOrder(bt-rchild);/*折半查找*/int Binary_Search(S_TBL *tbl,int kx)int low,high,mid,flag;flag=0;low=1; high=tbl-length; while(low=high)mid=(low+high)/2; if(kxdatamid.num) high=mid-1;elseif(kxtbl-datamid.num)low=mid+1;flag=mid; break; return flag;/*主菜单*/void menu() printf(l、插入并建立二叉树n); printf(2、删除二叉树上的结点n); printf(3、中序遍历二叉树n); printf(4、折半查找 n);printf(0、退出 n);void main()int n,m=l;NodeType *T=NULL;menu(); while(m)printf(请输入选项：”)； scanf(%d,&n); switch(n) case l:/*插入并建立二叉树*/ int flag; int kx;printf(请输入一组数据以-1结尾:”); scanf(%d,&kx);while(kx!=-1) flag=InsertNode(&T,kx);if(flag=0)printf(插入失败!n); break; scanf(%d,&kx);break;case 2:/*删除二叉树上的结点*/int flag;int kx;printf(“请输入要删除的数:”)； scanf(%d,&kx);flag=DeleteNode(&T,kx)； if(flag=0)printf(删除失败!n); else printf(删除成功!n); break;case 3:InOrder(T);printf(n); break;case 4:int i,flag;int kx;S_TBL *tbl=(S_TBL *)malloc(sizeof(S_TBL);printf( ”请输入长度:”)； scanf(%d,&(tbl-length);tbl-data=(datatype *)calloc( tbl-length,sizeof(datatype) ); printf(请输入元素:)；for(i=1;ilength;i+) scanf(%d,&(tbl-datai).num);printf(请输入你要查找的数:”)； scanf(%d,&kx);flag=Binary_Search(tbl,kx)； if(flag=0)printf(查找失败!n); elseprintf（位置=%6dn,flag）;break;case 0:m=0;break;三、实验总结通过本次实验，我对常用数据结构的基本概念及其不同的实现方法的理论得 到进一步的掌握，并对用折半查找实现某一已知的关键字的查找有了较为深刻的 认识，同时对用二叉排序树的插入算法建立二叉排序树，以及在二叉排序树中删 除某一指定关键字元素的具体操作也自己动手实践了。总的来说，加深了我对课 本上所学到的东西的记忆及理解。