实验9：查找子系统

验证性实验9：查找子系统班级：H1001学号：09姓名：陆俊实验日期：1．实验目的〔1〕通过查找实验理解查找的根本算法。〔2〕熟悉各种查找方法的适用场合及平均查找长度。〔3〕掌握静态查找和动态查找的区别。〔4〕掌握顺序查找、二分查找的根本思想及其算法。〔5〕掌握二叉排序树根本思想及其算法。2．实验内容〔1〕编写顺序查找程序。〔2〕编写二分查找程序。〔3〕编写建立二叉排序树的程序。〔4〕编写在二叉排序树上的查找、插入、删除结点的程序。〔5〕编写使二叉排序树中序输出的程序。〔6〕设计一个选择式菜单，一级菜单形式如下：查找子系统*******************************************1------顺序查找**2------二分查找**3------二叉排序树**0------返回*******************************************请选择菜单号(0--3)：二叉排序树二级子菜单如下：二叉排序树********************************************1------更新二叉排序树**2------查找结点**3------插入结点**4------删除结点**5------中序输出排序树**0------返回********************************************请选择菜单号(0--5)：3．实验程序#include<stdio.h>#include<string.h>#defineSEARCHMAX100#defineN10voidSeqSearch(){ inta[N],i,x,y; charch; printf("\n\t\t建立一个整数的顺序表〔以回车符为间隔，以-1结束〕：\n"); for(i=0;i<SEARCHMAX;i++) { printf("\t\t"); scanf("%d",&a[i]); getchar(); if(a[i]==-1) { y=i;break; } } printf("\n\t\t需要查找请输入Y，否那么输入N："); scanf("%c",&ch); while(ch=='y'||ch=='Y') { printf("\n\t\t请输入要查找的数据："); scanf("%d",&x);getchar(); i=y-1; while(i>=0&&a[i]!=x) i--; if(i==-1) printf("\n\t\t抱歉！没有您要查找的数据。\n"); else printf("\n\t\t您要查找的数据在第%d个位置上。\n",i+1); printf("\n\t\t继续查找输入Y，否那么输入N："); scanf("%c",&ch); }}voidBinSearch(){ intR[SEARCHMAX],i,k,low,mid,high,m,nn; charch; printf("\n\t\t建立递增有序的查找顺序表〔以回车符间隔，以-1结束〕：\n"); for(i=0;i<SEARCHMAX;i++) { printf("\t\t"); scanf("%d",&R[i]); getchar(); if(R[i]==-1) { nn=i;break; } } printf("\n\t\t查找请输入Y，退出输入N："); scanf("%c",&ch); getchar(); while(ch=='y'||ch=='Y') { printf("\n\t\t请输入要查找的数据："); scanf("%d",&k);getchar(); low=0; high=nn-1; m=0; while(low<=high) { mid=(low+high)/2; m++; if(R[mid]>k) high=mid-1; else if(R[mid]<k) low=mid+1; else break; } if(low>high) { printf("\n\t\t抱歉！没有您要查找的数据。\n"); printf("\n\t\t共进行%d次比拟。\n",m); if(R[mid]<k) mid++; printf("\n\t\t可将此数据插入到第%d个位置上。\n",mid+1); } else { printf("\n\t\t要找的数据%d在第%d个位置上。\n",k,mid+1); printf("\n\t\t共进行%d次比拟。\n",m); } printf("\n\t\t继续查找输入Y，否那么输入N："); scanf("%c",&ch);getchar(); }}typedefintKeyType;typedefstructnode{ KeyTypekey; structnode*lchild,*rchild;}BSTNode;typedefBSTNode*BSTree;BSTreeCreateBST(void);voidSearchBST(BSTreeT,KeyTypekey);voidInsBST(BSTree*Tptr,KeyTypekey);voidDelBSTNode(BSTree*Tptr,KeyTypekey);voidInorderBST(BSTreeT);voidBTSearch(){ BSTreeT; charch1,ch2; KeyTypeKey; printf("\n\t\t建立一颗二叉树的二叉链表存储\n"); T=CreateBST(); ch1='y'; getchar(); while(ch1=='y'||ch1=='Y') { printf("\n"); printf("\n\t\t二叉排序树"); printf("\n\t\t*********************************************"); printf("\n\t\t*1------更新二叉排序树*"); printf("\n\t\t*2------查找结点*"); printf("\n\t\t*3------插入结点*"); printf("\n\t\t*4------删除结点*"); printf("\n\t\t*5------中序输出排序树*"); printf("\n\t\t*0------返回*"); printf("\n\t\t*********************************************"); printf("\n\t\t 请选择菜单号(0--5)："); scanf("%c",&ch2); getchar(); switch(ch2) { case'1':T=CreateBST();break; case'2':printf("\n\t\t请输入要查找的数据："); scanf("%d",&Key); getchar(); SearchBST(T,Key); printf("\n\t\t查找完毕。\n");break; case'3':printf("\n\t\t请输入要插入的数据："); scanf("%d",&Key); getchar(); InsBST(&T,Key); printf("\n\t\t插入完毕。\n");break; case'4':printf("\n\t\t请输入要删除的数据："); scanf("%d",&Key); getchar(); DelBSTNode(&T,Key); printf("\n\t\t删除完毕。\n");break; case'5':printf("\n\t\t"); InorderBST(T); printf("\n\t\t二叉排序树输出完毕。\n");break; case'0':ch1='n'; return; default:printf("\n\t\t输出错误！请重新输入。\n");break; } }}BSTreeCreateBST(void){ BSTreeT; KeyTypeKey; T=NULL; printf("\n\t\t请输入一个整数关键字〔输入0时结束输入〕："); scanf("%d",&Key); while(Key) { InsBST(&T,Key); printf("\n\t\t请输入下一个整数关键字〔输入0时结束输入〕："); scanf("%d",&Key); } returnT;}voidSearchBST(BSTreeT,KeyTypeKey){ BSTNode*p=T; while(p) { if(p->key==Key) { printf("\n\t\t已经找到您输入的数据。\n"); return; } p=(Key<p->key)?p->lchild:p->rchild; } printf("\n\t\t没有找到您输入的数据。\n");}voidInsBST(BSTree*T,KeyTypeKey){ BSTNode*f,*p; p=(*T); while(p) { if(p->key==Key) { printf("\n\t\t树中已有%d，不需插入。\n",Key); return; } f=p; p=(Key<p->key)?p->lchild:p->rchild; } p=newBSTNode; p->key=Key; p->lchild=p->rchild=NULL; if((*T)==NULL) (*T)=p; else if(Key<f->key) f->lchild=p; else f->rchild=p;}voidDelBSTNode(BSTree*T,KeyTypeKey){ BSTNode*parent=NULL,*p,*q,*child; p=*T; while(p) { if(p->key==Key) break; parent=p; p=(Key<p->key)?p->lchild:p->rchild; } if(!p) { printf("\n\t\t没有找到您要删除的结点。"); return; } q=p; if(q->lchild&&q->rchild) for(parent=q,p=q->rchild;p->lchild;parent=p,p=p->lchild); child=(p->lchild)?p->lchild:p->rchild; if(!parent) *T=child; else { if(p==parent->lchild) parent->lchild=child; else parent->rchild=child; if(p!=q) q->key=p->key; } delete(p);}voidInorderBST(BSTreeT){ if(T!=NULL) { InorderBST(T->lchild); printf("\t%d",T->key); InorderBST(T->rchild); }}voidmain(){ intchoice; charch; ch='y'; while(ch=='y'||ch=='Y') { printf("\n"); printf("\n\t\t查找子系统"); printf("\n\t\t********************************************"); printf("\n\t\t*1------顺序查找*"); printf("\n\t\t*2------二分查找*"); printf("\n\t\t*3------二叉排序树*"); printf("\n\t\t*0------返回*"); printf("\n\t\t********************************************"); printf("\n\t\t请选择菜单号(0--3)："); scanf("%d",&choice); switch(choice) { case1:SeqSearch();break; case2:BinSearch();break; case3:BTSearch();break; case0:ch='n';break; default:printf("\n\t\t菜单项选择择错误！请重新输入。"); } }}4．程序运行5．实验小结这次的实验，在输入程序代码的时候，我也犯了很多小错误，当程序代码全部输入完毕、运行时花了点时间才改正了错误的地方，因为这次代码中有“key〞和“key〞这两个成员，在输入的时候，不小心把两块地方的“key〞和“key〞的“K〞和“k〞搞错了，然后提示了不是某〔node〕类的成员。还有就是，这本书上本身的参考程序也是有错误的，functionheader漏了个“#include<stdio.h>〞所以会提示三个错误“printf〞、“scanf〞、“getchar〞这三个成了未定义〔未声明〕，正常情况来说，这三个是不会提示未声明之类的错误提示的，还有就是两个菜单里的都有问题，是