(完整word版)在二叉排序樹(shù)中查找關(guān)鍵字為key地記錄簿

1、實(shí)用標(biāo)準(zhǔn)文案學(xué)院名稱專(zhuān)業(yè)班級(jí)實(shí)驗(yàn)成績(jī)學(xué)生姓名學(xué)號(hào)實(shí)驗(yàn)日期課程名稱數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)題目4 查找一、實(shí)驗(yàn)?zāi)康呐c要求通過(guò)本次實(shí)驗(yàn)，掌握查找表上的有關(guān)查找方法，并分析時(shí)間復(fù)雜度。二、主要儀器設(shè)備Cfree三、實(shí)驗(yàn)內(nèi)容和原理2.實(shí)習(xí)題1問(wèn)題描述編寫(xiě)程序?qū)崿F(xiàn)下面運(yùn)算：在二叉排序樹(shù)中查找關(guān)鍵字為key的記錄。輸入排序二叉樹(shù)，以及要查找的數(shù)字（節(jié)點(diǎn)）。輸出顯不該節(jié)點(diǎn)是否存在。存儲(chǔ)結(jié)構(gòu)有序表采用順序方式存儲(chǔ)。算法的基本思想若一叉排序樹(shù)為空樹(shù)，查找失敗，返回null或0;否則，將key與根節(jié)點(diǎn)的關(guān)鍵字比較：若key=根節(jié)點(diǎn)的關(guān)鍵字，查找成功；若key根節(jié)點(diǎn)的關(guān)鍵字，繼續(xù)在左子樹(shù)中查找；若key根節(jié)點(diǎn)的關(guān)鍵字，繼續(xù)在右

2、子樹(shù)中查找。精彩文檔參考源程序#include <malloc.h>#include <stdio.h>#define NULL 0typedef int KeyType;typedef struct KeyType key;ElemType; 元素類(lèi)型typedef struct BiTNodeElemType data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;BiTree searchBST(BiTree bt,KeyType key)/*在二叉排序樹(shù)bt中查找其關(guān)鍵字等于給定值的結(jié)點(diǎn)是否存在，并輸出相應(yīng)信息*/

3、if (bt=NULL) return NULL;/在排序二叉樹(shù)中進(jìn)行遞歸查找else if (bt->data.key=key) return bt;else if (key<bt->data.key) return searchBST(bt->lchild,key);else return searchBST(bt->rchild,key);void insertBST(BiTree *bt,BiTree s)/*在二叉排序樹(shù)中插入一個(gè)新結(jié)點(diǎn)，即依次插入輸入的數(shù)*/if (*bt=NULL) *bt=s;else if (s->data.key<(

4、*bt)->data.key) insertBST(&(*bt)->lchild),s);else if (s->data.key>(*bt)->data.key) insertBST(&(*bt)->rchild),s);main()char ch;KeyType key;BiTree bt,s;int i=0;/*建立一棵二叉排序樹(shù)，元素從鍵盤(pán)按先序輸入，直到輸入關(guān)鍵字等于-1為止*/printf("n請(qǐng)輸入元素(-1:結(jié)束)：n");以-1為結(jié)束scanf("%d",&key);bt=NU

5、LL;while (key!=-1)s=(BiTree)malloc(sizeof(BiTNode);(s->data).key=key;s->lchild=s->rchild=NULL;insertBST(&bt,s);scanf("%d",&key);/while/*二叉排序樹(shù)的查找，可多次查找，并輸出查找的結(jié)果*/do printf("n輸入你想要查找的元素：");scanf("%d",&key);s=searchBST(bt,key);if (s!=NULL) printf("

6、;n 成功！這個(gè)等價(jià)元素是%d.n",s->data.key);elseprintf("n 沒(méi)有找到！n");printf("n 是否繼續(xù)？(y/n):");scanf("%c",&ch);ch=getchar();while (ch='y' | ch='Y');getchar();main實(shí)驗(yàn)結(jié)果：1FJ 相 U 入 J L,本4-1 -)：Q3 4 35 324 23 354 65 34 23 3 45 23 12kl，入你楣要杳找的7T素；2 k有找到？出否繼續(xù)？y諭入你想

7、熨古找的.元素二34女功，這外警價(jià)元素足34. k由繼續(xù)五、實(shí)驗(yàn)結(jié)果與分析(2)習(xí)題1:采用先序遍歷的方式生成二叉樹(shù)，程序中多次使用的遞歸的算法。使程序看起來(lái)很簡(jiǎn)潔。如果把頭結(jié)點(diǎn)的生成也放到生成樹(shù)的函數(shù)中，會(huì)使程序看起來(lái)更加調(diào)理。六、實(shí)驗(yàn)心得及體會(huì)查找是很多程序的基礎(chǔ)， 很多程序中都會(huì)用到查找。比如在線性表的插入和刪除時(shí)要查找合適的位置。所以學(xué)好查找是很必要的。本次實(shí)驗(yàn)只要是采取了這般查找的方法。其實(shí)還有很多查找的方法。如順序查找，索引順序表查找。每種查找方法各有優(yōu)劣。如折半查找的平均查找長(zhǎng)度小于順序查找，但它要求查找的表為有序的。所以需將無(wú)序表排序成有序表。這又會(huì)浪費(fèi)運(yùn)行時(shí)間。編寫(xiě)程序時(shí)遇到

8、了很多的困難，如先序生成樹(shù)更好還是中序生成更好。太原理工大學(xué)學(xué)生實(shí)驗(yàn)報(bào)告學(xué)院名稱計(jì)算機(jī)科學(xué)與技術(shù)專(zhuān)業(yè)班級(jí)計(jì)Z1002班實(shí)驗(yàn)成績(jī)學(xué)生姓名鄭海兵學(xué)號(hào)2010001420實(shí)驗(yàn)日期1月2日課程名稱數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)題目5內(nèi)排序一、實(shí)驗(yàn)?zāi)康呐c要求通過(guò)本次實(shí)驗(yàn)，掌握線性表的排序方法，并分析時(shí)間復(fù)雜度。二、主要儀器設(shè)備Cfree三、實(shí)驗(yàn)內(nèi)容和原理問(wèn)題描述設(shè)一個(gè)用鏈表表示的直接選擇排序算法，并用程序?qū)崿F(xiàn)。輸入n個(gè)數(shù)據(jù)。輸出n個(gè)數(shù)據(jù)由小到大排列的結(jié)果。存儲(chǔ)結(jié)構(gòu)待排序記錄順序存儲(chǔ)。算法的基本思想已知待排序初始序列用單鏈表存儲(chǔ)，頭指針head指向A個(gè)結(jié)點(diǎn)，從這個(gè)待排序列中找出最小結(jié)點(diǎn)，插入 head之后，用r來(lái)指示。r以

9、前為已排序序列，r以后為未排序序列。再?gòu)?未排序序列中找出最小結(jié)點(diǎn)插入r的后面，讓r指向這個(gè)結(jié)點(diǎn)。反復(fù)執(zhí)行這個(gè)過(guò)程， 直到排好序。參考源程序#include<stdio.h>#include<malloc.h>int n;struct Numberint data;struct Number* next;；struct Number* Creat_H(int k)/ 創(chuàng)建單鏈表struct Number* L;struct Number* p;p=(struct Number*)malloc(sizeof(struct Number);L=p;int temp;int

10、i;printf("n請(qǐng)輸入元素：");for(i=1;i<=k;i+)scanf("%d",&temp);p->data=temp;if(i=k)p->next=NULL;break;p->next=(struct Number*)malloc(sizeof(struct Number);p=p->next;/forreturn L;/struct Number* Creat_Hstruct Number* Sort(struct Number* p)/直接選擇排序struct Number* max;struct

11、 Number* min;struct Number* temp;struct Number* r;r=p;int flag=0;doif(flag=0)第一次找最小數(shù)時(shí)的初始化 temp=min=max=r;elsetemp=min=max=r->next;/dowhile(1)找出最小數(shù)if(min->data<=max->next->data)if(max->next->next!=NULL)max=max->next;elsebreak;/ifelsetemp=max; 相當(dāng)于 temp->next=minmin=max->n

12、ext;if(max->next->next!=NULL)max=max->next;elsebreak;elsewhileif(temp!=min)if(min->next=NULL)temp->next=NULL;elsetemp->next=min->next;if(flag=0)r=min;r->next=p;p=r;elsemin->next=r->next;r->next=min;r=min;/ifelse初始化時(shí)min就已經(jīng)指向了最小數(shù)if(flag=0)/第一次找到最小數(shù)r=min;p=r;elser=min;/

13、elseflag+;又排好一個(gè)數(shù)if(flag=n-1)return p;while(1);int main()struct Number* H;printf("n請(qǐng)輸入元素個(gè)數(shù)n (n>=2) :");/輸入數(shù)據(jù)(不得少于2個(gè))scanf("%d",&n);while(n<2)printf("nError!請(qǐng)重新輸入元素個(gè)數(shù)n：");scanf("%d",&n);H=Creat_H(n);H=Sort(H);printf("n排序后的數(shù)為：");/數(shù)據(jù)排序后的序列while(H!=NULL)printf("%-4d”,H->data);H=H->next;printf("n");system("pause");return 0;getchar();五、實(shí)驗(yàn)結(jié)果與分析習(xí)題1:這題要從前面和后面同時(shí)進(jìn)行處理，只有這樣才能保證