實驗9：查找子系統(tǒng)

驗證性實驗9：查找子系統(tǒng)班級：H1001學號：09姓名：陸俊實驗日期：1．實驗?zāi)康摹?〕通過查找實驗理解查找的根本算法?！?〕熟悉各種查找方法的適用場合及平均查找長度?！?〕掌握靜態(tài)查找和動態(tài)查找的區(qū)別?！?〕掌握順序查找、二分查找的根本思想及其算法?！?〕掌握二叉排序樹根本思想及其算法。2．實驗內(nèi)容〔1〕編寫順序查找程序?！?〕編寫二分查找程序?！?〕編寫建立二叉排序樹的程序?！?〕編寫在二叉排序樹上的查找、插入、刪除結(jié)點的程序?！?〕編寫使二叉排序樹中序輸出的程序?！?〕設(shè)計一個選擇式菜單，一級菜單形式如下：查找子系統(tǒng)*******************************************1------順序查找**2------二分查找**3------二叉排序樹**0------返回*******************************************請選擇菜單號(0--3)：二叉排序樹二級子菜單如下：二叉排序樹********************************************1------更新二叉排序樹**2------查找結(jié)點**3------插入結(jié)點**4------刪除結(jié)點**5------中序輸出排序樹**0------返回********************************************請選擇菜單號(0--5)：3．實驗程序#include<stdio.h>#include<string.h>#defineSEARCHMAX100#defineN10voidSeqSearch(){ inta[N],i,x,y; charch; printf("\n\t\t建立一個整數(shù)的順序表〔以回車符為間隔，以-1結(jié)束〕：\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請輸入要查找的數(shù)據(jù)："); scanf("%d",&x);getchar(); i=y-1; while(i>=0&&a[i]!=x) i--; if(i==-1) printf("\n\t\t抱歉！沒有您要查找的數(shù)據(jù)。\n"); else printf("\n\t\t您要查找的數(shù)據(jù)在第%d個位置上。\n",i+1); printf("\n\t\t繼續(xù)查找輸入Y，否那么輸入N："); scanf("%c",&ch); }}voidBinSearch(){ intR[SEARCHMAX],i,k,low,mid,high,m,nn; charch; printf("\n\t\t建立遞增有序的查找順序表〔以回車符間隔，以-1結(jié)束〕：\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請輸入要查找的數(shù)據(jù)："); 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抱歉！沒有您要查找的數(shù)據(jù)。\n"); printf("\n\t\t共進行%d次比擬。\n",m); if(R[mid]<k) mid++; printf("\n\t\t可將此數(shù)據(jù)插入到第%d個位置上。\n",mid+1); } else { printf("\n\t\t要找的數(shù)據(jù)%d在第%d個位置上。\n",k,mid+1); printf("\n\t\t共進行%d次比擬。\n",m); } printf("\n\t\t繼續(xù)查找輸入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------查找結(jié)點*"); printf("\n\t\t*3------插入結(jié)點*"); printf("\n\t\t*4------刪除結(jié)點*"); 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請輸入要查找的數(shù)據(jù)："); scanf("%d",&Key); getchar(); SearchBST(T,Key); printf("\n\t\t查找完畢。\n");break; case'3':printf("\n\t\t請輸入要插入的數(shù)據(jù)："); scanf("%d",&Key); getchar(); InsBST(&T,Key); printf("\n\t\t插入完畢。\n");break; case'4':printf("\n\t\t請輸入要刪除的數(shù)據(jù)："); 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請輸入一個整數(shù)關(guān)鍵字〔輸入0時結(jié)束輸入〕："); scanf("%d",&Key); while(Key) { InsBST(&T,Key); printf("\n\t\t請輸入下一個整數(shù)關(guān)鍵字〔輸入0時結(jié)束輸入〕："); scanf("%d",&Key); } returnT;}voidSearchBST(BSTreeT,KeyTypeKey){ BSTNode*p=T; while(p) { if(p->key==Key) { printf("\n\t\t已經(jīng)找到您輸入的數(shù)據(jù)。\n"); return; } p=(Key<p->key)?p->lchild:p->rchild; } printf("\n\t\t沒有找到您輸入的數(shù)據(jù)。\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沒有找到您要刪除的結(jié)點。"); 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查找子系統(tǒng)"); 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．實驗小結(jié)這次的實驗，在輸入程序代碼的時候，我也犯了很多小錯誤，當程序代碼全部輸入完畢、運行時花了點時間才改正了錯誤的地方，因為這次代碼中有“key〞和“key〞這兩個成員，在輸入的時候，不小心把兩塊地方的“key〞和“key〞的“K〞和“k〞搞錯了，然后提示了不是某〔node〕類的成員。還有就是，這本書上本身的參考程序也是有錯誤的，functionheader漏了個“#include<stdio.h>〞所以會提示三個錯誤“printf〞、“scanf〞、“getchar〞這三個成了未定義〔未聲明〕，正常情況來說，這三個是不會提示未聲明之類的錯誤提示的，還有就是兩個菜單里的都有問題，是