数据结构实验 查找

实验4查找

一、实验目的或任务

通过指导学生上机实践，对常用数据结构的基本概念及其不同的实现方法的理论得到进一步的掌握，并对在不同存储结构上实现不同的运算方式和技巧有所体会。

二、实验教学基本要求

1.了解实验目的及实验原理；

2.编写程序，并附上程序代码和结果图；

3.总结在编程过程中遇到的问题、解决办法和收获。

三、实验教学的内容或要求

1.编写函数,建立有序表,采用折半查找实现某一已知的关键字的查找(采用顺序表存储结构)

2.编写函数,随机产生一组关键字,利用二叉排序树的插入算法建立二叉排序树

3.编写函数,在以上二叉排序树中删除某一指定关键字元素

4.编写一个主函数,在主函数中设计一个简单的菜单,分别调试上述算法

四、实验类型或性质

验证性

五、实验开出要求

必做

六、实验所需仪器设备

1.计算机

2.相关软件（如C,C++,PASCAL,VC,DELPHI等等）

七、实验所用材料

计算机耗材

一、程序运行界面：

二、源程序

#define _CRT_SECURE_NO_W ARNINGS

#include<stdio.h>

#include<malloc.h>

#define MAXNODE 256

typedefstruct Node

{

int data;

struct Node *lchild,*rchild;

}NodeType;

typedefstruct

{

int num;

}datatype;

typedefstruct

{

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(kx>p->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(kx>p->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;

}

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(kx<tbl->data[mid].num)

{

high=mid-1;

}

elseif(kx>tbl->data[mid].num)

{

low=mid+1;

}

else

{

flag=mid; break;

}

}

return flag;

}

/*主菜单*/

void menu()

{

printf("1、插入并建立二叉树\n");

printf("2、删除二叉树上的结点\n");

printf("3、中序遍历二叉树\n");

printf("4、折半查找\n");

printf("0、退出\n");

}

void main()

{

int n,m=1;

NodeType *T=NULL;

menu();

while(m)

{

printf("请输入选项：");

scanf("%d",&n);

switch(n)

{

case 1:

{/*插入并建立二叉树*/

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;i<=tbl->length;i++)

{

scanf("%d",&((tbl->data[i]).num));

}

printf("请输入你要查找的数:");

scanf("%d",&kx);

flag=Binary_Search(tbl,kx);

if(flag==0)

{

printf("查找失败!\n");

}

else

{

printf("位置=%6d\n",flag);

}

break;

}

case 0:

{

m=0;

break;

}

}

}

}

三、实验总结

通过本次实验，我对常用数据结构的基本概念及其不同的实现方法的理论得到进一步的掌握，并对用折半查找实现某一已知的关键字的查找有了较为深刻的认识，同时对用二叉排序树的插入算法建立二叉排序树，以及在二叉排序树中删除某一指定关键字元素的具体操作也自己动手实践了。总的来说，加深了我对课本上所学到的东西的记忆及理解。

本文来源：https://www.bwwdw.com/article/vj31.html