在二叉排序樹(shù)中查找關(guān)鍵字為key的記錄

-4-學(xué)院名稱專業(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)題描述]編寫程序?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ù)在右子樹(shù)中查找。太原理工大學(xué)學(xué)生實(shí)驗(yàn)報(bào)告學(xué)院名稱計(jì)算機(jī)科學(xué)與技術(shù)專業(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è)計(jì)一個(gè)用鏈表表示的直接選擇排序算法，并用程序?qū)崿F(xiàn)。[輸入]n個(gè)數(shù)據(jù)。[輸出]n個(gè)數(shù)據(jù)由小到大排列的結(jié)果。[存儲(chǔ)結(jié)構(gòu)]待排序記錄順序存儲(chǔ)。[算法的基本思想]已知待排序初始序列用單鏈表存儲(chǔ)，頭指針head指向第一個(gè)結(jié)點(diǎn)，從這個(gè)待排序列中找出最小結(jié)點(diǎn)，插入head之后，用r來(lái)指示。r以前為已排序序列，r以后為未排序序列。再?gòu)奈磁判蛐蛄兄姓页鲎钚〗Y(jié)點(diǎn)插入r的后面，讓r指向這個(gè)結(jié)點(diǎn)。反復(fù)執(zhí)行這個(gè)過(guò)程，直到排好序。[參考源程序]#include<stdio.h>#include<malloc.h>intn;structNumber{intdata;structNumber*next;};structNumber*Creat_H(intk){//創(chuàng)建單鏈表structNumber*L;structNumber*p;p=(structNumber*)malloc(sizeof(structNumber));L=p;inttemp;inti;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=(structNumber*)malloc(sizeof(structNumber));p=p->next;}//forreturnL;}//structNumber*Creat_HstructNumber*Sort(structNumber*p){//直接選擇排序structNumber*max;structNumber*min;structNumber*temp;structNumber*r;r=p;intflag=0;do{if(flag==0){//第一次找最小數(shù)時(shí)的初始化temp=min=max=r;}else{temp=min=max=r->next;}//dowhile(1){//找出最小數(shù)if(min->data<=max->next->data){if(max->next->next!=NULL){max=max->next;}else{break;}}//ifelse{temp=max;//相當(dāng)于temp->next=minmin=max->next;if(max->next->next!=NULL){max=max->next;}else{break;}}//else}//while(1)if(temp!=min){if(min->next==NULL){temp->next=NULL;}else{temp->next=min->next;}if(flag==0){r=min;r->next=p;p=r;}else{min->next=r->next;r->next=min;r=min;}}//ifelse{//初始化時(shí)min就已經(jīng)指向了最小數(shù)if(flag==0){//第一次找到最小數(shù)r=min;p=r;}else{r=min;}}//elseflag++;//又排好一個(gè)數(shù)if(flag==n-1){returnp;}}while(1);}intmain(){structNumber*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");return0;getchar();}五、實(shí)驗(yàn)結(jié)果與分析習(xí)題1：這題要從前面和后面同時(shí)進(jìn)行處理，只有這樣才能保證時(shí)間復(fù)雜度為O(N)。六、實(shí)驗(yàn)心得及體會(huì)排序有很多種方法，如冒泡排序、直接插入排序、希爾排序、歸并排序、選擇排序等等。各個(gè)排序的方法各有優(yōu)劣，時(shí)間復(fù)雜度各不相同。習(xí)題二中使用的快速排