數(shù)據(jù)結(jié)構(gòu)：查找子系統(tǒng)

數(shù)據(jù)結(jié)構(gòu)：查找子系統(tǒng)-可編輯修改-數(shù)據(jù)結(jié)構(gòu)：查找子系統(tǒng)全文共11頁，當(dāng)前為第1頁。/*數(shù)據(jù)結(jié)構(gòu)：查找子系統(tǒng)全文共11頁，當(dāng)前為第1頁。*題目：編寫循序查找程序*編寫二分查找程序*編寫建立二叉排序樹的程序*編寫在二叉排序樹上的查找、輸入、刪除結(jié)點(diǎn)的程序*編寫二叉排序樹的中序輸出的程序*設(shè)計(jì)一個(gè)選擇式菜單，一級(jí)菜單形式如下：*查找子系統(tǒng)************************************1------順序查找***2------二分查找***3------二叉排序樹***0------返回************************************請選擇菜單號(hào)（0--3）：*二叉排序樹的二級(jí)菜單如下：*二叉排序樹***************************************1------更新二叉排序樹***2------查找結(jié)點(diǎn)***3------插入結(jié)點(diǎn)***4------刪除結(jié)點(diǎn)***5------中序輸出排序樹***0------返回***************************************請選擇菜單號(hào)（0--5）：*/#include<stdio.h>#include<string.h>#include<stdlib.h>#defineSEARCHMAX30typedefstructnode{inttrData;//根節(jié)點(diǎn)structnode*lchild;//左子樹structnode*rchild;//右子樹}BtNode,*pBtNode;voidseqSearch();voidbinSearch();voidbtSearch();pBtNodecreateBT();數(shù)據(jù)結(jié)構(gòu)：查找子系統(tǒng)全文共11頁，當(dāng)前為第2頁。voidsearchBT(pBtNodeT,intk);數(shù)據(jù)結(jié)構(gòu)：查找子系統(tǒng)全文共11頁，當(dāng)前為第2頁。voidinsBT(pBtNode*T,intk);voiddelBT(pBtNode*T,intk);voidinorderBT(pBtNodeT);voidmain(){intchoice,k=1;while(k){printf("\n查找子系統(tǒng)\n");printf("*********************************\n");printf("*1------順序查找*\n");printf("*2------二分查找*\n");printf("*3------二叉排序樹*\n");printf("*0------返回*\n");printf("*********************************\n");printf("請選擇菜單號(hào)（0--3）：");fflush(stdin);scanf("%d",&choice);switch(choice){case1:seqSearch();break;case2:binSearch();break;case3:btSearch();break;case0:k=0;break;default:printf("輸入錯(cuò)誤，請重新輸入。");getchar();k=1;break;}}}數(shù)據(jù)結(jié)構(gòu)：查找子系統(tǒng)全文共11頁，當(dāng)前為第3頁。數(shù)據(jù)結(jié)構(gòu)：查找子系統(tǒng)全文共11頁，當(dāng)前為第3頁。voidseqSearch()//順序查找{inta[SEARCHMAX],x,y,i;charch;printf("建立一個(gè)整數(shù)的順序表（以-1結(jié)束）：");for(i=0;i<SEARCHMAX;i++){scanf("%d",&a[i]);getchar();if(a[i]==-1)//記錄結(jié)束位置，結(jié)束循環(huán){y=i;break;}}printf("是否需要查找（Y/N）：");scanf("%c",&ch);while(ch=='y'||ch=='Y'){printf("請輸入要查找的數(shù)據(jù)：\n");scanf("%d",&x);getchar();i=0;//找到數(shù)組的結(jié)束位置。while(i<y-1&&a[i]!=x)//找到要查找的數(shù)據(jù)的位置{i++;}if(i==-1)//沒找到{printf("對不起，沒有找到。\n");}else{printf("該數(shù)據(jù)在第%d個(gè)位置上。\n",i+1);}printf("是否繼續(xù)查找（Y/N）：");scanf("%c",&ch);}}數(shù)據(jù)結(jié)構(gòu)：查找子系統(tǒng)全文共11頁，當(dāng)前為第4頁。數(shù)據(jù)結(jié)構(gòu)：查找子系統(tǒng)全文共11頁，當(dāng)前為第4頁。voidbinSearch()//二分查找{intb[SEARCHMAX],i,y,x,low,mid,high,n;charch;printf("建立遞增有序的查找順序表（以-1結(jié)束）：\n");for(i=0;i<SEARCHMAX;i++){scanf("%d",&b[i]);getchar();if(b[i]==-1)//記錄結(jié)束位置，結(jié)束循環(huán){y=i;break;}}printf("是否需要查找（Y/N）：");scanf("%c",&ch);while(ch=='y'||ch=='Y'){printf("請輸入要查找的數(shù)據(jù)：");scanf("%d",&x);getchar();low=0;//低high=y-1;//高n=0;//記錄次數(shù)while(low<=high){mid=(low+high)/2;n++;if(b[mid]>x)//在左邊{high=mid-1;}elseif(b[mid]<x)//在右邊{low=mid+1;}else//找到{break;數(shù)據(jù)結(jié)構(gòu)：查找子系統(tǒng)全文共11頁，當(dāng)前為第5頁。}數(shù)據(jù)結(jié)構(gòu)：查找子系統(tǒng)全文共11頁，當(dāng)前為第5頁。}if(low>high){printf("對不起，沒有找到該數(shù)據(jù)。\n");printf("共進(jìn)行%d次比較。\n",n);if(b[mid]<x)//查找最后小于該數(shù)據(jù)的位置{mid++;}printf("可將此數(shù)據(jù)插入第個(gè)%d位置",mid+1);}else{printf("找到該數(shù)據(jù)在第%d個(gè)位置。\n",mid+1);printf("共進(jìn)行%d次比較。\n",n);}printf("是否需要查找（Y/N）：");scanf("%c",&ch);}}voidbtSearch()//二叉排序樹{intchoice,x,l=1;pBtNodeT;printf("建立一棵二叉排序樹存儲(chǔ)\n");T=createBT();getchar();while(l){printf("\n二叉排序樹\n");printf("***********************************\n");printf("*1------更新二叉排序樹*\n");printf("*2------查找結(jié)點(diǎn)*\n");printf("*3------插入結(jié)點(diǎn)*\n");printf("*4------刪除結(jié)點(diǎn)*\n");printf("*5------中序輸出排序樹*\n");printf("*0------返回*\n");printf("************************************\n");printf("請選擇菜單號(hào)（0--5）：");fflush(stdin);數(shù)據(jù)結(jié)構(gòu)：查找子系統(tǒng)全文共11頁，當(dāng)前為第6頁。scanf("%d",&choice);數(shù)據(jù)結(jié)構(gòu)：查找子系統(tǒng)全文共11頁，當(dāng)前為第6頁。switch(choice){case1:T=createBT();break;case2:printf("請輸入要查找的數(shù)據(jù)：");scanf("%d",&x);getchar();searchBT(T,x);break;case3:printf("請輸入要插入的數(shù)據(jù)：");scanf("%d",&x);insBT(&T,x);break;case4:printf("請輸入要?jiǎng)h除的數(shù)據(jù)：");scanf("%d",&x);delBT(&T,x);break;case5:inorderBT(T);break;case0:l=0;break;default:printf("輸入錯(cuò)誤，請重新輸入。");getchar();l=1;break;}}}pBtNodecreateBT()//建立二叉樹{pBtNodeT;//聲明指針intx;T=NULL;數(shù)據(jù)結(jié)構(gòu)：查找子系統(tǒng)全文共11頁，當(dāng)前為第7頁。printf("請輸入一個(gè)整數(shù)（輸入0結(jié)束）：");數(shù)據(jù)結(jié)構(gòu)：查找子系統(tǒng)全文共11頁，當(dāng)前為第7頁。fflush(stdin);scanf("%d",&x);getchar();while(x)//輸入的數(shù)據(jù)非零時(shí){insBT(&T,x);//二叉樹中插入數(shù)據(jù)printf("請輸入下一個(gè)整數(shù)（輸入0結(jié)束）：");fflush(stdin);scanf("%d",&x);getchar();}returnT;//返回指針}voidsearchBT(pBtNodeT,intk)//查找二叉樹結(jié)點(diǎn){pBtNodef=T;while(f){if(f->trData==k)//判斷是否找到該數(shù)據(jù){printf("已找到數(shù)據(jù)。\n");return;}f=(k<f->trData)?f->lchild:f->rchild;//判斷下一個(gè)查找的位置}printf("沒有找到數(shù)據(jù)。\n");}voidinsBT(pBtNode*T,intk)//插入二叉樹結(jié)點(diǎn){pBtNodef,p;p=(*T);//指向指針的指針while(p)//當(dāng)結(jié)點(diǎn)不為空{(diào)if(p->trData==k){printf("樹中已有%d，不需要插入。",k);return;}數(shù)據(jù)結(jié)構(gòu)：查找子系統(tǒng)全文共11頁，當(dāng)前為第8頁。else數(shù)據(jù)結(jié)構(gòu)：查找子系統(tǒng)全文共11頁，當(dāng)前為第8頁。{f=p;p=(k<p->trData)?p->lchild:p->rchild;//判斷插入的數(shù)據(jù)的位置}}p=(BtNode*)malloc(sizeof(BtNode));//分配空間p->trData=k;p->lchild=p->rchild=NULL;if((*T)==NULL){(*T)=p;}else{if(k<f->trData){f->lchild=p;}else{f->rchild=p;}}}voiddelBT(pBtNode*T,intk)//刪除二叉樹結(jié)點(diǎn){pBtNodep,q,child,parent=NULL;p=*T;while(p)//找到輸入的數(shù)據(jù)的位置{if(p->trData==k){break;}parent=p;//記錄上一個(gè)結(jié)點(diǎn)p=(k<p->trData)?p->lchild:p->rchild;}if(!p)//沒有找到位置{printf("沒有找到你要?jiǎng)h除的數(shù)據(jù)結(jié)點(diǎn)。\n");數(shù)據(jù)結(jié)構(gòu)：查找子系統(tǒng)全文共11頁，當(dāng)前為第9頁。return;數(shù)據(jù)結(jié)構(gòu)：查找子系統(tǒng)全文共11頁，當(dāng)前為第9頁。