數(shù)據(jù)結(jié)構(gòu)試驗查找

1、實驗名稱：查找班級：學(xué)號：姓名：報告日期：一、實驗?zāi)康募耙? .了解實驗?zāi)康募皩嶒炘恚? .編寫程序，并附上程序代碼和結(jié)果圖；3 .總結(jié)在編程過程中遇到的問題、解決辦法和收獲。二、實驗內(nèi)容1 .編寫函數(shù)，建立有序表，采用折半查找實現(xiàn)某一已知的關(guān)鍵字的查找（采用順序表存儲結(jié)構(gòu)）；2 .編寫函數(shù)，隨機產(chǎn)生一組關(guān)鍵字，利用二叉排序樹的插入算法建立二叉排序樹；3 .編寫函數(shù)，在以上二叉排序樹中刪除某一指定關(guān)鍵字元素；4 .編寫一個主函數(shù)，在主函數(shù)中設(shè)計一個簡單的菜單，分別調(diào)試上述算法.三、實驗結(jié)果叵2)HC:U&e!r£a5.usDe£ktopDebijgz4.eMe機

2、編寫函數(shù).在二叉排序樹中刪除某一指定關(guān)鍵字元素:請輸入相應(yīng)的選項1律輸入線忖表的長度律輸入線忖表的.第1個元素壯詔輸入線忖表的.第芝個元素二謂輸入線性表的第甘個元素l4諾輸入線忖表的.第4個元素：5諾輸入線性表的.第5個元素：G諾輸入要杳擾的元素：5該元素在表中的位置為41一據(jù)寫函數(shù).建立有序表.采用折半杳找實現(xiàn)某已知的關(guān)鋌宇的查找;乙的機產(chǎn)生一組關(guān)鋌字.利用一又排序樹的插入算法:建立一區(qū)和序捌；3一想寫函數(shù).在二又排序樹中刪除墓-指定關(guān)鍵字元素：*結(jié)束請輸入相應(yīng)的選項：2建立二叉排序樹,請輸入序列（用空格隔開.用電結(jié)束輸入?。?7112427先序遍歷輸出序列為演1247L戰(zhàn)寫函數(shù).建立有序

3、表，采用護半查找實現(xiàn)某已知的關(guān)鋌字的查找:，隨機產(chǎn)生一組關(guān)例字，利用二叉排序樹的插入算法:建立二叉洋序謝；四、實驗總結(jié)這次實驗是對查找算法的編程實現(xiàn)，而查找算法有很多，這次我選的是折半法。折半法其實和我們以往學(xué)的二分法有很大的相似，所以對算法的理解較為容易。主要難以解決則是編程的實現(xiàn)，但是在老師、同學(xué)以及網(wǎng)絡(luò)的幫助下，最終勉強的編寫出程序。而其中也再此讓我感受到了循環(huán)算法的妙用，這次沒有用for語句作循環(huán)，用的是switch語句，使我對其用法更加熟練，其次，還是老話，細心最重要，一定要注意細節(jié)。附錄#include<stdio.h>#include<stdlib.h>#

4、defineLISTSIZE20#defineENDKEY0#include<time.h>typedefintKeyType;typedefintOtherType;typedefstructnodeLKeyTypekey;/*關(guān)4建字的俏*/structnode*lchild,*rchild;/*左右才旨針*/BSTNode,*BSTree;typedefstructKeyTypekey;OtherTypeother_data;RecordType;typedefstructRecordTyperLISTSIZE+1;/*r0為工作單元*/intlength;RecordLis

5、t;voidcreatelist(RecordList*l)Linti;intlen;KeyTypech;printf("請輸入線性表的長度：");scanf("%d”,&len);l->length=len;for(i=1;i<=len;i+)(printf("請輸入線性表的第d個元素：i);fflush(stdin);scanf("%c”,&ch);l->ri.key=ch;_1上intBinSrch(RecordListl,KeyTypek)/*在有序表l中折半查找其關(guān)鍵字等于k的元素，若找到，則函數(shù)值為

6、該元素在表中的位置*/intlow,high,mid;low=1;high=l.length;/*置區(qū)間初值*/while(low<=high)(mid=(low+high)/2;if(k=l.rmid.key)return(mid);/*找至口彳寺杳元素*/elseif(k<l.rmid.key)high=mid-1;/*未找至口，貝吆保絨在前半?yún)^(qū)間進行查找*/elselow=mid+1;/*烏米紈在后半?yún)^(qū)間I井行杳找*/return(0);voidInsertBST(BSTree*bst,KeyTypekey)/*若在二叉排序樹中不存在關(guān)鍵字等于key的元素，插入該元素*/BS

7、Trees;if(*bst=NULL)/*遞歸結(jié)束條件*/(s=(BSTree)malloc(sizeof(BSTNode);/*申請新的結(jié)點s*/s->key=key;s->lchild=NULL;s->rchild=NULL;*bst=s;elseif(key<(*bst)->key)InsertBST(&(*bst)->lchild),key);/*將s插入左子樹*/elseif(key>(*bst)->key)InsertBST(&(*bst)->rchild),key);/*將s插入右子樹*/上巴intInsert

8、BST(BSTree*bst,KeyTypeK)BSTreef,q,s;s=(BSTree)malloc(sizeof(BSTNode);s->key=K;s->lchild=NULL;s->rchild=NULL;if(*bst=NULL)-L*bst=s;return1;1f=NULL;q=*bst;while(q)-Uif(q->key=K)return0;if(K<q->key)Lf=q；q=q->lchild;1elseL_f=q；q=q->rchild;1if(K<f->key)f->lchild=s;elsef-&

9、gt;rchild=s;return1;上voidCreateBST(BSTree*bst)/*從鍵盤輸入元素的伯，創(chuàng)建相應(yīng)的二叉排序樹*/KeyTypekey;*bst=NULL;inti;srand(unsigned)time(NULL);/初始化隨機數(shù)for(i=0;i<8;i+)key=(rand()%10+1);printf("%d",key);產(chǎn)牛110之間的隨機數(shù)while(key!=ENDKEY)/*ENDKEY為自岸義常量*/InsertBST(bst,key);/scanf("%d”,&key);Q1上voidPreOrder(B

10、STreeroot)/*先庠遍歷二叉樹，root為指向二叉樹根結(jié)點的指針*/if(root!=NULL)printf("%d",root->key);/*輸出結(jié)點*/PreOrder(root->lchild);/*先序遍歷左子樹*/PreOrder(root->rchild);/*先序遍歷右子樹*/_上/1BSTreeSearchBST(BSTreebst,KeyTypekey)/*在根指針bst所指二叉排序樹中、遞歸查找某關(guān)鍵字等于key的元素、若查找成功，返回指向該元素結(jié)點指針，否則返回空指針*/if(!bst)returnNULL;elseif(b

11、st->key=key)returnbst;/*查找成功*/elseif(bst->key>key)returnSearchBST(bst->lchild,key);/*在左子樹繼續(xù)杳找*/elsereturnSearchBST(bst->rchild,key);/*在右子樹2續(xù)查找*/*/BSTreeSearchBST(BSTreebst,KeyTypekey)/*在木艮針bst所#f二叉序樹bst上：杳找關(guān)彳建字等于key的結(jié)點：若杳找成功：返回指向該元素結(jié)點指針、否則返回空指針*/BSTreeq;q=bst;while(q)if(q->key=key)

12、returnq;/*查找成功*/if(q->key>key)q=q->lchild;/*在左子樹中杳找*/elseq=q->rchild;/*在右子樹中查找*/returnNULL;/*杳找失敗*/*SearchBST*/BSTNode*DelBST(BSTreet,KeyTypek)/*在二叉用E序樹t中刪I去關(guān)彳津字為k的結(jié)點*/LBSTNode*p,*f,*s,*q;p=t;f=NULL;while(p)/*查找關(guān)鍵字為k的待刪結(jié)點p*/if(p->key=k)break;/*找至1貝U跳出循環(huán)*/f=p;/半指向p結(jié)點的雙親結(jié)點*/if(p->key

13、>k)p=p->lchild;elsep=p->rchild;-Eif(p=NULL)returnt;/*若找不至L返回原來的二叉排序樹*/if(p->lchild=NULL)/*p無左子樹*/if(f=NULL)t=p->rchild;/*p是原二叉排序樹的根*/elseif(f->lchild=p)/*p是f的左孩子*/f->lchild=p->rchild;/*將p的右子樹鏈至Uf的左鏈上*/else/*p是f的右孩子*/f->rchild=p->rchild;/*將p的右子樹鏈至Uf的右鏈上*/free(p);/*釋放被刪除的

14、結(jié)點p*/else/*p有左子樹*/-Uq=p;s=p->lchild;while(s->rchild)/*在p的左子樹中杳找最右下結(jié)點*/q=s;s=s->rchild;1if(q=p)q->lchild=s->lchild;/*1辱s的左子樹鏈至口q7*/elseq->rchild=s->lchild;p->key=s->key;/*4辱s的俏/就給p*/free(s);returnt;/*DelBST*/voidmain()Lintflag=0;intn,t=1;while(t)printf("*n");print

15、f("1.編寫函數(shù)，建立有序表，采用折半查找實現(xiàn)某一已知的關(guān)鍵字的查找血");printf("2.隨機產(chǎn)生一組關(guān)鍵字，利用二叉排序樹的插入算法建立二叉排序樹;n");printf("3.編寫函數(shù)，在隨機產(chǎn)生的二叉排序樹中刪除某一指定關(guān)鍵字元素;n");printf("4.結(jié)束n");printf("*n*);printf("請輸入相應(yīng)的選項：");scanf("%d",&n);switch(n)(case1:RecordListl;intlocate;Key

16、Typek;createlist(&l);printf("請輸入要杳找的元素：”);fflush(stdin);scanf("%c",&k);locate=BinSrch(l,k);if(locate=0)printf("未找至U!n");elseprintf(“該元素在表中的位置為dn”,locate);break;case 2:BSTreeT;BSTreeresult;printf("建立二叉排序樹，謂輸入序列(用空格隔開，用0結(jié)束輸入！)：n");CreateBST(&T);printf(&qu

17、ot;n");printf("先序遍歷輸出序列為：");PreOrder(T);/*printf("n請輸入要刪除的元素：”);fflush(stdin);scanfC'%d&k);result=SearchBST(T,k);if(result!=NULL)printf("%d元素已經(jīng)被刪除！刪除后的二叉樹的先序遍歷：'n'Jesult-Akey);elseprintf("未找至U!n");result=DelBST(T,k);PreOrder(result);*/printf("n");/getch();break;case 3:printf("建立二叉排序樹、請輸入序列(用空格隔開、用0結(jié)束輸入！)：n");CreateBST(&T);printf("n");printf("先序遍.歷輸出序列為：");PreOrder(T);printfC'W請輸入要刪除的元素：”);fflush(stdin);scanf(''%d",&am