查找子系统(1)

1、数据结构实验报告实验名称：查找子系统 日期：XXXX年XX月xx日 得分： 指导老师：XX专业：XXXX 班次：XXXX班 姓名：xxx 学号：XXXXXXXXXXX1实验内容：编写顺序查找、二分查找程序（二选一）；编写建立二叉排序树的程序；编写在二叉排序树上的查找、插入、删除结点的程序；编写二叉排序树中序输出的程序（选做）；设计一个选择式菜单。2实验要求：通过查找实验理解查找的基本算法；熟悉各种查找方法的适用场合及平均查找长度；掌握静态查找和动态查找的区别；掌握顺序查找、二分查找的基本思想及其算法；掌握二叉排序树基本思想及其算法。3程序代码：#include#include#define S

2、EARCHMAX 100#define N 10void SeqSearch()int aN,i,x,y;char ch;printf(ntt建立一个整数的顺序表（以回车符为间隔，以-1结束）：n);for(i=0;i=0&ai!=x)i-;if(i=-1)printf(ntt抱歉！没有您要查找的数据。n);elseprintf(ntt您要查找的数据在第%d个位置上。n,i+1);printf(ntt继续查找输入Y，否则输入N：);scanf(%c,&ch);void BinSearch()int RSEARCHMAX,i,k,low,mid,high,m,nn;char ch;printf(

3、ntt建立递增有序的查找顺序表（以回车符间隔，以-1结束）：n);for(i=0;iSEARCHMAX;i+)printf(tt);scanf(%d,&Ri);getchar();if(Ri=-1)nn=i;break;printf(ntt查找请输入Y，退出输入N：);scanf(%c,&ch);getchar();while(ch=y|ch=Y)printf(ntt请输入要查找的数据：);scanf(%d,&k);getchar();low=0;high=nn-1;m=0;while(lowk)high=mid-1;elseif(Rmidhigh)printf(ntt抱歉！没有您要查找的数据

4、。n);printf(ntt共进行%d次比较。n,m);if(Rmidkey=Key)printf(ntt已经找到您输入的数据。n);return;p=(Keykey)?p-lchild:p-rchild;printf(ntt没有找到您输入的数据。n);void InsBST(BSTree *T,KeyType Key)BSTNode *f,*p;p=(*T);while(p)if(p-key=Key)printf(ntt树中已有%d，不需插入。n,Key);return;f=p;p=(Keykey)?p-lchild:p-rchild;p=new BSTNode;p-key=Key;p-lc

5、hild=p-rchild=NULL;if(*T)=NULL)(*T)=p;elseif(Keykey)f-lchild=p;elsef-rchild=p;void DelBSTNode(BSTree *T,KeyType Key)BSTNode *parent=NULL,*p,*q,*child;p=*T;while(p)if(p-key=Key)break;parent=p;p=(Keykey)?p-lchild:p-rchild;if(!p)printf(ntt没有找到您要删除的结点。);return;q=p;if(q-lchild&q-rchild)for(parent=q,p=q-r

6、child;p-lchild;parent=p,p=p-lchild);child=(p-lchild)?p-lchild:p-rchild;if(!parent)*T=child;elseif(p=parent-lchild)parent-lchild=child;elseparent-rchild=child;if(p!=q)q-key=p-key;delete(p);void InorderBST(BSTree T)if(T!=NULL)InorderBST(T-lchild);printf(t%d,T-key);InorderBST(T-rchild);void main()int c

7、hoice;char ch;ch=y;while(ch=y|ch=Y)printf(n);printf(ntt 查 找 子 系 统 );printf(ntt*);printf(ntt* 1-顺 序 查 找 *);printf(ntt* 2-二 分 查 找 *);printf(ntt* 3-二 叉 排 序 树 *);printf(ntt* 0-返 回 *);printf(ntt*);printf(ntt请选择菜单号(0-3)：);scanf(%d,&choice);switch(choice)case 1:SeqSearch();break;case 2:BinSearch();break;case 3:BTSearch();break;case 0:ch=n;break;default:printf(ntt菜单选择错误！请