中南大學(xué)大數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告材料

1、實(shí)用文檔中南大學(xué)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)題目：（1）單鏈表的實(shí)現(xiàn)（2）棧和隊(duì)列（3）二叉樹(shù)的遍歷（4）查找與排序?qū)W生姓名：代巍學(xué)生學(xué)號(hào)：0909121615指導(dǎo)老師：余臘生所在學(xué)院：信息科學(xué)與工程學(xué)院專業(yè)班級(jí)：信息安全1201班指導(dǎo)教師評(píng)定!：簽名：實(shí)驗(yàn)一 單鏈表的實(shí)現(xiàn)一、實(shí)驗(yàn)?zāi)康牧私饩€性表的邏輯結(jié)構(gòu)和各種存儲(chǔ)表示方法， 以及定義在邏輯結(jié)構(gòu)上的各種基本運(yùn)算及其在某種存儲(chǔ)結(jié)構(gòu)上如何實(shí)現(xiàn)這些基本運(yùn)算。 在熟悉上述內(nèi)容的 基礎(chǔ)上，能夠針對(duì)具體應(yīng)用問(wèn)題的要求和性質(zhì)， 選擇合適的存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)出相應(yīng) 的有效算法，解決與線性表相關(guān)的實(shí)際問(wèn)題二、實(shí)驗(yàn)內(nèi)容用C/C+語(yǔ)言編寫程序，完成以下功能：（1）運(yùn)行時(shí)輸入數(shù)據(jù)，

2、創(chuàng)建一個(gè)單鏈表（2）可在單鏈表的任意位置插入新結(jié)點(diǎn)（3）可刪除單鏈表的任意一個(gè)結(jié)點(diǎn)（4）在單鏈表中查找結(jié)點(diǎn)（5）輸出單鏈表三、程序設(shè)計(jì)的基本思想，原理和算法描述 ：（包括程序的結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)，輸入 /輸出設(shè)計(jì)，符號(hào)名說(shuō)明等）用一組地址任意的存儲(chǔ)單元存放線性表中的數(shù)據(jù)元素。以元素 （ 數(shù)據(jù)元素的映象 ） + 指針（ 指示后繼元素存儲(chǔ)位置 ） = 結(jié)點(diǎn)（ 表示數(shù)據(jù)元 素 或 數(shù)據(jù)元素的映象 ）以“結(jié)點(diǎn)的序列”表示線性表稱作線性鏈表（單鏈表）單鏈表是指數(shù)據(jù)接點(diǎn)是單向排列的。 一個(gè)單鏈表結(jié)點(diǎn)， 其結(jié)構(gòu)類型分為兩部 分：（1）、數(shù)據(jù)域：用來(lái)存儲(chǔ)本身數(shù)據(jù)。（2）、鏈域或稱為指針域： 用來(lái)存儲(chǔ)下一個(gè)結(jié)點(diǎn)地址

3、或者說(shuō)指向其直接后 繼的指針。1、單鏈表的查找對(duì)單鏈表進(jìn)行查找的思路為： 對(duì)單鏈表的結(jié)點(diǎn)依次掃描， 檢測(cè)其數(shù)據(jù)域是否 是我們所要查好的值，若是返回該結(jié)點(diǎn)的指針，否則返回NULL。2、單鏈表的插入因?yàn)樵趩捂湵淼逆溣蛑邪撕罄^結(jié)點(diǎn)的存儲(chǔ)地址， 所以當(dāng)我們實(shí)現(xiàn)的時(shí)候， 只要知道該單鏈表的頭指針，即可依次對(duì)每個(gè)結(jié)點(diǎn)的數(shù)據(jù)域進(jìn)行檢測(cè)。假設(shè)在一個(gè)單鏈表中存在2個(gè)連續(xù)結(jié)點(diǎn)p、q (其中p為q的直接前驅(qū))，若 我們需要在p、q之間插入一個(gè)新結(jié)點(diǎn)s,那么我們必須先為s分配空間并賦值， 然后使p的鏈域存儲(chǔ)s的地址，s的鏈域存儲(chǔ)q的地址即可。(p- link=s;s- link=q) ，這樣就完成了插入操作。3、

4、單鏈表的刪除刪除運(yùn)算思想方法刪除運(yùn)算是將表的第 i 個(gè)結(jié)點(diǎn)刪去。具體步驟：找 到i-1的存儲(chǔ)位置p令p-next指向i的直接后繼結(jié)點(diǎn)釋放結(jié)點(diǎn)i的空間，將其歸還給 存儲(chǔ)池 。四、源程序及注釋#include #include #include #include #include #define ElemType int/ 鏈表類型typedef struct LNodeElemType data;struct LNode *next; LNode, *LinkList;int EmptyList(LinkList &L) if(L-next=NULL) return 0;elsereturn 1

5、;/ 手動(dòng)建立一個(gè)帶頭結(jié)點(diǎn)的線性鏈表 L void SCreateList_L(LinkList &L) LinkList l,p;int i;ElemType d;l=(LinkList) malloc(sizeof(LNode);L=(LinkList) malloc(sizeof(LNode); /l=L;L-next=NULL;coutd;if(d!=0)p=(LinkList) malloc(sizeof(LNode); / p-data=d;p-next=l-next;l-next=p;l=l-next;else break;if(EmptyList(L) cout 生成鏈表成功！

6、 else cout 鏈表為空，未生成！ ！ ; cin.get();cin.get(); /SCreate_L生成頭結(jié)點(diǎn)next=NULL;srand(unsigned)time(NULL);for(int i=n;i0;-i)p=(LinkList) malloc(sizeof(LNode); /生成新結(jié)點(diǎn)p-data=(rand()%100+1); p-next=l-next;l-next=p;l=l-next; cout 生成鏈表成功！ ！ ;cin.get();cin.get(); /ZCreate_L/ 建立一個(gè)帶頭結(jié)點(diǎn)的線性鏈表LinkList CreateList_L() ch

7、ar c;int n;LinkList L;cout* 建立線性鏈表*endl;cout1. 手動(dòng)建立 endl;cout2. 自動(dòng)建立 endl;cout|*|c;if(c=1) SCreateList_L(L);else if(c=2) coutn;ZCreateList_L(L,n);else cout 輸入錯(cuò)誤，請(qǐng)重新輸入 :next;int i=0;while (p)+i;p=p-next;return i;cin.get();cin.get(); /LengthList/在線性鏈表L中第i個(gè)結(jié)點(diǎn)之前插入新的數(shù)據(jù)元素evoid ListInsert_L(LinkList &L)int

8、 i;ElemType e;couti;while(iLengthList(L)couti;LinkList p,s;p=L;int j=0;while(p & jnext;+j;if(!p | ji-1) cout輸入錯(cuò)誤！ cin.get();cin.get();else coute;s=(LinkList) malloc(sizeof(LNode); s-data=e;s-next=p-next;p-next=s;cout 插入成功！ ;cin.get();cin.get(); /ListInsert_L/ 刪除線性鏈表 L 中的第 i 個(gè)結(jié)點(diǎn)void ListDelete_L(Link

9、List &L)int i;ElemType e;couti;while(iLengthList(L)couti;LinkList p,q;p=L; int j=0;q=(LinkList) malloc(sizeof(LNode);while (p-next & jnext;+j; / 尋找第 i 個(gè)結(jié)點(diǎn)if(!(p-next) | ji-1) coutnext;p-next=q-next;e=q-data;cout 刪除成功！ endl 刪除的結(jié)點(diǎn)值為： next; cout 所有數(shù)據(jù)如下所示： endl;while (p)coutdatanext;cin.get();cin.get();

10、 /PrintListvoid SearchList(LinkList &L)/ 查找某一結(jié)點(diǎn)，顯示其位置int i=0;ElemType n;coutn;if(L=NULL) coutnext;while (p-data!=n & p-next!=NULL) p=p-next; i=i+1;if(p-data=n) cout 找到了對(duì)應(yīng)的結(jié)點(diǎn)，在鏈表的第 i+1 位上！ ; else coutnext;free(p);L=NULL;cout 線性鏈表 L 已銷毀 !endl;/DestroyListint menu_select() / 選擇函數(shù)char *m7= 1. 建立線性鏈表 ,2.

11、 某一結(jié)點(diǎn)前插入一個(gè)結(jié)點(diǎn) ,3. 刪除一個(gè)結(jié)點(diǎn) ,4. 計(jì)算結(jié)點(diǎn)個(gè)數(shù)并輸出 ,5. 查找并顯示某一結(jié)點(diǎn)位置 ,6. 輸出所有節(jié)點(diǎn) ,0. 退出系統(tǒng) ;int i;char c1;dosystem(cls);/* 清屏 */coutnn= 鏈表的基本操作 =nn; for(i=0;i7;i+)coutmiendl; coutn=n; coutc1;while(c16);return(c1-0);void main()LinkList L=NULL;for( ; ; )switch(menu_select()case 1:L=CreateList_L(); system(pause); break

12、;case 2:if(L!=NULL) ListInsert_L(L);else cout 鏈表為空，請(qǐng)先建鏈表！ ！ cin.get();cin.get();break;system(pause); break;case 3:if(L!=NULL) ListDelete_L(L);else cout 鏈表為空，請(qǐng)先建鏈表！ ！ cin.get();cin.get();break;system(pause);break;case 4:i;if(L!=NULL) int i=LengthList(L);cout 結(jié)點(diǎn)的個(gè)數(shù)為： cin.get();cin.get();else cout 鏈表為空

13、，請(qǐng)先建鏈表！ ！ ;cin.get();cin.get();break;system(pause);break;case 5:if(L!=NULL) SearchList(L);else cout 鏈表為空，請(qǐng)先建鏈表！ ！ ;cin.get();cin.get();break;system(pause);break;case 6:if(L!=NULL) PrintList(L);else cout 鏈表為空，請(qǐng)先建鏈表！ ！cin.get();cin.get();break;system(pause);break;case 0:if(L!=NULL) DestroyList(L); exi

14、t(0);五、實(shí)驗(yàn)結(jié)果一槌表的基本操作占S 結(jié) 位 個(gè)出點(diǎn) 一S 入并- 性點(diǎn)工 線結(jié)一結(jié)并紫 立一隧岀 僅-1、廠咅一剩一入輸2 1 請(qǐng)- 與1=1=:2插新.72也竄重?fù)?jù)！繼 耘：數(shù)！鍵1 ft?選2置置結(jié)入按 請(qǐng)請(qǐng)實(shí)驗(yàn)二 棧和隊(duì)列、實(shí)驗(yàn)?zāi)康牧私鈼：完?duì)列的特性。 掌握棧的順序表示和實(shí)現(xiàn)。 掌握棧的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)。 掌握隊(duì)列的順序表示和實(shí)現(xiàn)。 掌握隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)。 掌握棧和隊(duì)列在實(shí)際問(wèn)題中的應(yīng)用、實(shí)驗(yàn)內(nèi)容編寫一個(gè)程序?qū)崿F(xiàn)順序棧的各種基本運(yùn)算， 并在此基礎(chǔ)上設(shè)計(jì)一個(gè)主程序完 成如下功能：初始化順序棧，插入元素，刪除棧頂元素，取棧頂元素，遍歷順序 棧，置空順序棧。三、程序設(shè)計(jì)的基本思想，原

15、理和算法描述棧的修改時(shí)按照先進(jìn)后出的原則進(jìn)行的， 試驗(yàn)中用到構(gòu)造空棧， 及入棧出棧 操作。隊(duì)列是一種先進(jìn)先出的線性表， 只允許在表的一端插入， 而在另一端刪除 元素，試驗(yàn)中構(gòu)造隊(duì)并且入隊(duì)出隊(duì)。立順序棧SeqStack，存放測(cè)試數(shù)據(jù)；建立隊(duì)列SeqQueue存放出棧數(shù)據(jù)；建立 InitStack、StackEmpty、StackFull、Pop Push、GetTop 函數(shù)用作順 序棧的基本操作； 建立 InitQueue 、 QEmpty、 Qfull 、 InQueue、 OutQueue、 ReadFront 函數(shù)用作隊(duì)列的基本操作；建立主函數(shù)依次按序?qū)ψ雍瘮?shù)進(jìn)行操作：Ini tStack

16、 初始化棧Push壓入數(shù) 據(jù)f Ini tQueue初始化隊(duì)列Pop彈出數(shù)據(jù)In Queue存入隊(duì)列OutQueue出隊(duì) 列一 Push壓入棧Pop彈出數(shù)據(jù)free清空棧與隊(duì)列。在數(shù)據(jù)的輸入與數(shù)據(jù)的 輸出時(shí)提供必要的提示信息。四、源程序及其注釋#include #include stack.h#include #define MAXSIZE 100/ 作用 ：對(duì)棧進(jìn)行初始化/ 參數(shù)：無(wú)/ 返回值： SeqStackSeqStack SeqStackInit()SeqStack S ;S.top = -1 ;return S ;/ 作用 ：對(duì)棧進(jìn)行判斷是否為空/ 參數(shù)：傳入要判斷的棧/返回值：返

17、回TRUE為空，返回FLASE為非空int SeqStackEmpty(SeqStack S)if(S.top top - ;printf(n清空！ n) ;/ 作用 ：把元素 x 壓入棧，使其成為新的棧頂元素/ 參數(shù)：傳入棧和要輸入的數(shù)字/ 返回值：無(wú)void SeqStackPush(SeqStack *S,DataType x)S-top+ ;/ 要求是先挖坑，再種蘿卜S-dataS-top = x ;/ 作用 ：出棧/ 參數(shù)：要從該棧出來(lái)/ 返回值：從棧中出來(lái)的數(shù)DataType SeqStackPop(SeqStack *S)DataType temp ;if(SeqStackEmp

18、ty(*S)printf(sorry ！為空棧！ ) ;/ exit(1) ;elsetemp = S-dataS-top ;/ 出棧是當(dāng)前出棧，要求先挖蘿卜再填坑 S-top - ;printf(n%dn,temp) ;/ 作用 ：取棧頂元素/ 參數(shù)：要操作的棧/ 返回值：從棧中出來(lái)的數(shù)DataType SeqStackGetTop(SeqStack S)DataType temp ;if(SeqStackEmpty(S)printf(sorry ！為空棧！ ) ;/ exit(1) ;elsetemp = S.dataS.top ;/ 出棧是當(dāng)前出棧，要求先挖蘿卜再填坑printf(n%d

19、n,temp)/ 作用 輸出順序棧中的元素/ 參數(shù)：要操作的棧/ 返回值：從棧中出來(lái)的數(shù)void SeqStackPrint(SeqStack S)DataType temp ;SeqStack p ;p = S ;printf( 輸出棧中的所有元素 :) ;while(!SeqStackEmpty(p)temp = p.datap.top ;/ 出棧是當(dāng)前出棧，要求先挖蘿卜再填坑p.top - ;printf(n% d n,temp) ;/ 當(dāng)這里位置數(shù)據(jù)類型怎么辦void main(void)int num ;int input ;SeqStack p ;p = SeqStackInit(

20、) ;/ 這里調(diào)用入棧函數(shù)，把 10,20,30 進(jìn)棧SeqStackPush(&p,10) ;SeqStackPush(&p,20) ;SeqStackPush(&p,30) ;while(1)printf(nt實(shí)驗(yàn)二 nn) ;printf(n1.入棧) ;printf(n2.棧頂元素彈出 ) ;printf(n3.取棧頂元素 ) ;printf(n4.輸出順序棧中的元素 )printf(n5.清空棧 n) ;printf(t請(qǐng)輸入要實(shí)現(xiàn)的功能 n)scanf(%d,&num) ;switch(num)case 1 :ttn) ;printf(n 請(qǐng)輸入要入棧的數(shù)： scanf(%d, &

21、input) ;SeqStackPush(&p,input) ;break;case 2 :SeqStackPop(&p) ;break;case 3 :SeqStackGetTop(p) ;break;case 4 :SeqStackPrint(p) ;break;case 5 :ClearStack(&p) ;break;五、實(shí)驗(yàn)結(jié)果棧脛元 恚豐出駱中的元素“請(qǐng)輸入要實(shí)現(xiàn)的功能請(qǐng)輸入要實(shí)現(xiàn)的功能4輸岀棧中的所有元素：4231212枝頂棧岀空 人棧暮詬 12 3 4 5 1元素彈岀請(qǐng)輸入要實(shí)現(xiàn)的功能請(qǐng)輸入要入棧的數(shù);2請(qǐng)瀚人要究現(xiàn)的功能清空!實(shí)驗(yàn)三 二叉樹(shù)的建立和遍歷一、實(shí)驗(yàn)?zāi)康?、學(xué)會(huì)實(shí)現(xiàn)

22、二叉樹(shù)結(jié)點(diǎn)結(jié)構(gòu)和對(duì)二叉樹(shù)的基本操作。2、掌握對(duì)二叉樹(shù)每種操作的具體實(shí)現(xiàn)，學(xué)會(huì)利用遞歸方法編寫對(duì)二叉樹(shù)這種遞 歸數(shù)據(jù)結(jié)構(gòu)進(jìn)行處理的算法。二、實(shí)驗(yàn)內(nèi)容 編寫程序任意輸入二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)和結(jié)點(diǎn)值， 構(gòu)造一棵二叉樹(shù)， 采用三種遞歸 遍歷算法 （ 前序、中序、后序 ） 對(duì)這棵二叉樹(shù)進(jìn)行遍歷并計(jì)算出二叉樹(shù)的高度 。三、程序設(shè)計(jì)的基本思想，原理和算法描述1、數(shù)據(jù)結(jié)構(gòu)的定義 二叉樹(shù)是另一種樹(shù)型結(jié)構(gòu)， 它的特點(diǎn)是每個(gè)結(jié)點(diǎn)至多只有兩棵子樹(shù)， 并且二叉樹(shù) 有左右之分， 其次序不能任意顛倒。 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)分為順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ) 結(jié)構(gòu)，本次我們主要應(yīng)用二叉樹(shù)的二叉鏈表的方式存儲(chǔ)方式， 實(shí)驗(yàn)中首先必須對(duì) 二叉樹(shù)的數(shù)據(jù)

23、結(jié)構(gòu)進(jìn)行定義， 即定義一個(gè)二叉鏈表， 其中其數(shù)據(jù)成員包括節(jié)點(diǎn)的 數(shù)據(jù)、左子樹(shù)的指針、右子樹(shù)的指針。2、二叉樹(shù)的建立在實(shí)驗(yàn)開(kāi)始前我們要建立一個(gè)以先序形式的二叉樹(shù)， 先序的二叉樹(shù)就是先訪問(wèn)根 結(jié)點(diǎn)，然后訪問(wèn)左子樹(shù)，最后訪問(wèn)右子樹(shù)的遍歷。3、二叉樹(shù)的遍歷 二叉樹(shù)的遍歷分為先序、中序、后序，需先取遍歷的節(jié)點(diǎn)的數(shù)據(jù)存入隊(duì)列中，然 后輸出。4、程序中要的函數(shù)的介紹 （ 1）二叉樹(shù)的類型定義 （2）定義鏈?zhǔn)疥?duì)列類型 （ 3）初始化鏈?zhǔn)疥?duì)列的函數(shù) （4）主函數(shù)四、源程序及注釋#include#includetypedef struct BiTNodechar data;struct BiTNode *lchi

24、ld,*rchild;BiTNode,*BiTree;void CreatBiTree(BiTree &T)/ 前序法創(chuàng)建二叉樹(shù)char ch;if(ch=getchar()=n)T=NULL;elseT=(BiTNode*)malloc(sizeof(BiTNode);if(!T)exit(1);T-data=ch;CreatBiTree(T-lchild);CreatBiTree(T-rchild);void PreTravel(BiTree &T)/ 前序遍歷if(T)printf(%c,T-data);PreTravel(T-lchild);PreTravel(T-rchild);vo

25、id MidTravel(BiTree &T)/ 中序遍歷if(T)MidTravel(T-lchild);printf(%c,T-data);MidTravel(T-rchild);void PostTravel(BiTree &T)/ 后序遍歷if(T)PostTravel(T-lchild);PostTravel(T-rchild);printf(%c,T-data);void main()BiTree T;printf(please input the bitree:n );CreatBiTree(T);printf(The Pretravel is:n);PreTravel(T);p

26、rintf(n);/*/printf(The Midtravel is:n);MidTravel(T);printf(n);/*/printf(The PostTravel is:n);PostTravel(T);printf(n);五、實(shí)驗(yàn)結(jié)果p 1 e.s e inline thu bitree : 13I he Pr-e travel135The Midtrvel is =135The PostTiael is-531Press any key t;o continue實(shí)驗(yàn)四 查找和排序一、實(shí)驗(yàn)?zāi)康?1) 掌握查找的不同方法，并能用 c 語(yǔ)言實(shí)現(xiàn)查找算法。(2) 掌握常用的排序方法，并掌

27、握用 c 語(yǔ)言實(shí)現(xiàn)排序算法的方法。(3) 熟練掌握順序表的選擇排序、冒泡排序、直接插入排序等算法的實(shí)現(xiàn)；(4) 了解各種方法的排序過(guò)程及其時(shí)間復(fù)雜度的分析方法。二、實(shí)驗(yàn)內(nèi)容(1) 完整理解有關(guān)排序和查找的相關(guān)算法和基本思想以及種種算法使用的數(shù)據(jù)存 儲(chǔ)結(jié)構(gòu)；(2) 通過(guò)線性表對(duì)一組數(shù)據(jù)中的某個(gè)數(shù)據(jù)進(jìn)行查找； 對(duì)該組數(shù)據(jù)進(jìn)行從小到大的順序進(jìn)行排序； 三、程序設(shè)計(jì)的基本思想，原理和算法描述 ：開(kāi)始的時(shí)候提示輸入一組數(shù)據(jù)。 并存入一維數(shù)組中， 接下來(lái)調(diào)用一系列查找算法 對(duì)其進(jìn)行處理。 順序查找只是從頭到尾進(jìn)行遍歷。 二分查找則是先對(duì)數(shù)據(jù)進(jìn)行排 序，然后利用三個(gè)標(biāo)志，分別指向最大，中間和最小數(shù)據(jù)，接下來(lái)

28、根據(jù)待查找數(shù) 據(jù)和中間數(shù)據(jù)的比較不斷移動(dòng)標(biāo)志， 直至找到。 二叉排序樹(shù)則是先構(gòu)造， 構(gòu)造部 分花費(fèi)最多的精力， 比根節(jié)點(diǎn)數(shù)據(jù)大的結(jié)點(diǎn)放入根節(jié)點(diǎn)的右子樹(shù)， 比根節(jié)點(diǎn)數(shù)據(jù) 小的放入根節(jié)點(diǎn)的左子樹(shù)， 其實(shí)完全可以利用遞歸實(shí)現(xiàn)， 這里使用的循環(huán)來(lái)實(shí)現(xiàn) 的，感覺(jué)這里可以嘗試用遞歸。 當(dāng)二叉樹(shù)建好后， 中序遍歷序列即為由小到大的 有序序列，查找次數(shù)不會(huì)超過(guò)二叉樹(shù)的深度。這里還使用了廣義表輸出二叉樹(shù)， 以使得更直觀。哈希表則是利用給定的函數(shù)式建立索引，方便查找。四、源程序及其注釋#include #define LENGTH 100#include #include #define INFMT %d#def

29、ine OUTFMT %d /* #define NULL 0L */ #define BOOL int#define TRUE 1 #define FALSE 0#define LEN 10000typedef int ElemType;typedef struct BSTNodeElemType data;struct BSTNode *lchild, *rchild; BSTNode, *BSTree; typedef BSTree BiTree;/* 插入新節(jié)點(diǎn) */void Insert(BSTree *tree, ElemType item)BSTree node = (BSTre

30、e)malloc(sizeof(BSTNode); node-data = item;node-lchild = node-rchild = NULL;if (!*tree)*tree = node;elseBSTree cursor = *tree;while (1)if (item data)if (NULL = cursor-lchild)cursor-lchild = node;break;cursor = cursor-lchild;elseif (NULL = cursor-rchild)cursor-rchild = node;break;cursor = cursor-rchi

31、ld;return;voidshowbitree(BiTree T)/ 遞歸顯示二叉樹(shù)的廣義表形式打印根節(jié)點(diǎn)if(!T) printf( 空 );return; printf(%d,T-data); / if(T-lchild |T-rchild)putchar();showbitree(T-lchild);/ 遞歸顯示左子樹(shù)putchar(,);showbitree(T-rchild);/ 遞歸顯示右子樹(shù)putchar();/* 查找指定值 */BSTree Search(BSTree tree, ElemType item) BSTree cursor = tree;while (curs

32、or)if (item = cursor-data)return cursor;else if ( item data)cursor = cursor-lchild;elsecursor = cursor-rchild;return NULL;/* 中綴遍歷 */void Inorder(BSTree tree)BSTree cursor = tree;if (cursor)Inorder(cursor-lchild);printf(OUTFMT, cursor-data);Inorder(cursor-rchild);/* 回收資源 */void Cleanup(BSTree tree)BS

33、Tree cursor = tree, temp = NULL;if (cursor)Cleanup(cursor-lchild);Cleanup(cursor-rchild);free(cursor);void searchtree(BSTree root)char choice;printf( 中序遍歷的結(jié)果為 :n);Inorder(root);printf(nn);ElemType item;BSTree ret;/* 二叉排序樹(shù)的查找測(cè)試 */doprintf(n 請(qǐng)輸入查找數(shù)據(jù)： );scanf(%d, &item);getchar();printf(Searching.n);re

34、t = Search(root, item);if (NULL = ret)printf( 查找失??！ );elseprintf( 查找成功！ );n);printf(n 繼續(xù)測(cè)試按 y ，退出按其它鍵。choice = getchar(); while (choice=y|choice=Y);Cleanup(root);searchhash(int *arr,int n)int a10;int b,i,j,c;j=1;for(i=0;i9;i+)ai=0;printf( 以下為哈希表輸出 n);for(i=0;in;i+)c=arri%7;A: if(ac=0)ac=arri;else c=

35、(c+1)%7;j+;ac+;goto A;printf(n%d 在哈希表的第4位，第4次放入哈希表n,arri,c,j);j=1;void SequenceSearch(int *fp,int Length);void Search(int *fp,int length);void Sort(int *fp,int length);void SequenceSearch(int *fp,int Length)int data;printf( 開(kāi)始使用順序查詢 .n 請(qǐng)輸入你想要查找的數(shù)據(jù) .n); scanf(%d,&data);for(int i=0;iLength;i+)if(fpi=d

36、ata)printf(經(jīng)過(guò)d次查找，查找到數(shù)據(jù) %d.n,i+1,data);return ;printf（ 經(jīng)過(guò)d次查找，未能查找到數(shù)據(jù)%d.n,i,data）; void Search(int *fp,int length)int data;printf( 開(kāi)始使用順序查詢 .n 請(qǐng)輸入你想要查找的數(shù)據(jù) .n); scanf(%d,&data);.n);printf( 由于二分查找法要求數(shù)據(jù)是有序的，現(xiàn)在開(kāi)始為數(shù)組排序 Sort(fp,length);printf( 數(shù)組現(xiàn)在已經(jīng)是從小到大排列 , 下面將開(kāi)始查找 .n);int bottom,top,middle;bottom=0;top

37、=length;int i=0;while (bottom=top)middle=(bottom+top)/2;i+;if(fpmiddledata)top=middle-1; elseprintf(”經(jīng)過(guò)d次查找，查找到數(shù)據(jù)d.n,i,data);return;printf( 經(jīng)過(guò)d次查找，未能查找到數(shù)據(jù)%d.n,i,data);void Sort(int *fp,int length).n);printf( 現(xiàn)在開(kāi)始為數(shù)組排序，排列結(jié)果將是從小到大int temp;for(int i=0;ilength;i+)for(int j=0;jfpj+1)temp=fpj;fpj=fpj+1;fp

38、j+1=temp;printf( 排序完成 !n 下面輸出排序后的數(shù)組 :n);for(int k=0;klength;k+)printf(%5d,fpk);printf(n);struct hash int key;int si;struct hash hlist11;int i,adr,sum,d;float average;void chash(int *arr,int n) for(i=0;i11;i+) hlisti.key=0;hlisti.si=0;for(i=0;in;i+) sum=0;adr=(3*arri)%11;d=adr;if(hlistadr.key=0) hlistadr.key=arri;hlistadr.si=1;else