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

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

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

3、if (bt=NULL) return NULL;/在排序二叉樹中進行遞歸查找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)/*在二叉排序樹中插入一個新結(jié)點，即依次插入輸入的數(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;/*建立一棵二叉排序樹，元素從鍵盤按先序輸入，直到輸入關(guān)鍵字等于-1為止*/printf("n請輸入元素(-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/*二叉排序樹的查找，可多次查找，并輸出查找的結(jié)果*/do printf("n輸入你想要查找的元素：");scanf("%d",&key);s=searchBST(bt,key);if (s!=NULL) printf("

6、;n 成功！這個等價元素是%d.n",s->data.key);elseprintf("n 沒有找到！n");printf("n 是否繼續(xù)？(y/n):");scanf("%c",&ch);ch=getchar();while (ch='y' | ch='Y');getchar();main實驗結(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女功，這外警價元素足34. k由繼續(xù)五、實驗結(jié)果與分析(2)習題1:采用先序遍歷的方式生成二叉樹，程序中多次使用的遞歸的算法。使程序看起來很簡潔。如果把頭結(jié)點的生成也放到生成樹的函數(shù)中，會使程序看起來更加調(diào)理。六、實驗心得及體會查找是很多程序的基礎， 很多程序中都會用到查找。比如在線性表的插入和刪除時要查找合適的位置。所以學好查找是很必要的。本次實驗只要是采取了這般查找的方法。其實還有很多查找的方法。如順序查找，索引順序表查找。每種查找方法各有優(yōu)劣。如折半查找的平均查找長度小于順序查找，但它要求查找的表為有序的。所以需將無序表排序成有序表。這又會浪費運行時間。編寫程序時遇到

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

9、前為已排序序列，r以后為未排序序列。再從 未排序序列中找出最小結(jié)點插入r的后面，讓r指向這個結(jié)點。反復執(zhí)行這個過程， 直到排好序。參考源程序#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請輸入元素：");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ù)時的初始化 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; 相當于 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初始化時min就已經(jīng)指向了最小數(shù)if(flag=0)/第一次找到最小數(shù)r=min;p=r;elser=min;/

13、elseflag+;又排好一個數(shù)if(flag=n-1)return p;while(1);int main()struct Number* H;printf("n請輸入元素個數(shù)n (n>=2) :");/輸入數(shù)據(jù)(不得少于2個)scanf("%d",&n);while(n<2)printf("nError!請重新輸入元素個數(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();五、實驗結(jié)果與分析習題1:這題要從前面和后面同時進行處理，只有這樣才能保證