数据结构查找实验.doc

实验四 查找 实验目的或任务 通过指导学生上机实践，对常用数据结构的基本概念及其不同的实现方法的理论得到进一步的掌握，并对在不同存储结构上实现不同的运算方式和技巧有所体会。 实验教学基本要求 1了解实验目的及实验原理； 2编写程序，并附上程序代码和结果图； 3总结在编程过程中遇到的问题、解决办法和收获。 实验教学的内容或要求 1编写函数,建立有序表,采用折半查找实现某一已知的关键字的查找(采用顺序表存储结构) 2.编写函数,随机产生一组关键字,利用二叉排序树的插入算法建立二叉排序树 3.编写函数,在以上二叉排序树中删除某一指定关键字元素 4.编写一个主函数,在主函数中设计一个简单的菜单,分别调试上述算法 实验类型或性质 验证性 实验开出要求 必做 实验所需仪器设备 1计算机 2相关软件（如C,C++,PASCAL,VC,DELPHI等等） 实验所用材料 计算机耗材 建立有序表,采用折半查找实现某一已知的关键字的查找(采用顺序表存储结构) 折半查找 图2-1 采用折半查找实现某一已知的关键字的查找 随机产生一组关键字,利用二叉排序树的插入算法建立二叉排序树 图2-2 随机产生一组关键字,利用二叉排序树的插入算法建立二叉排序树 3.在以上二叉排序树中删除某一指定关键字元素 图2-3 在以上二叉排序树中删除某一指定关键字元素#include stdio.h #include malloc.h typedef struct Node { int data; struct Node *lchild,*rchild; }NodeType; typedef struct { int num; }datatype; typedef struct { datatype *data; int length; }S_TBL; int SearchData(NodeType *T,NodeType **p,NodeType **q,int kx) { int flag=0; *q=T; while(*q) { if(kx(*q)-data) { *p=*q; *q=(*q)-rchild; } else { if(kx(*q)-data) { *p=*q; *q=(*q)-lchild; } else { flag=1; break; } } } return flag; } int InsertNode(NodeType **T,int 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; } else { if(kxp-data) p-rchild=s; else p-lchild=s; } flag=1; } return flag; } int DeleteNode(NodeType **T,int kx) { int flag=0; NodeType *p=*T,*q,*s,**f; if(SearchData(*T,p,q,kx)) { if(p==q) { f=T; } else { f=(p-lchild); if(kxp-data) f=(p-rchild); } if(q-rchild==NULL) { *f=q-lchild; } else { if(q-lchild==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