數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告 實(shí)驗(yàn)第四章：

　實(shí)驗(yàn)：

　簡單查找算法 一．需求與規(guī)格說明：

　查找算法這里主要使用了順序查找,折半查找,二叉排序樹查找與哈希表查找四種方法。由于自己能力有限,本想實(shí)現(xiàn)其她算法,但沒有實(shí)現(xiàn).其中順序查找相對比較簡單,折半查找參考了書上得算法，二叉排序樹查找由于有之前做二叉樹得經(jīng)驗(yàn)，因此實(shí)現(xiàn)得較為順利，哈希表感覺做得并不成功，感覺還就是應(yīng)該可以進(jìn)一步完善，應(yīng)該說還有很大得改進(jìn)余地。

　二．設(shè)計(jì)思想: 開始得時(shí)候提示輸入一組數(shù)據(jù)。并存入一維數(shù)組中，接下來調(diào)用一系列查找算法對其進(jìn)行處理。順序查找只就是從頭到尾進(jìn)行遍歷。二分查找則就是先對數(shù)據(jù)進(jìn)行排序，然后利用三個(gè)標(biāo)志，分別指向最大，中間與最小數(shù)據(jù)，接下來根據(jù)待查找數(shù)據(jù)與中間數(shù)據(jù)得比較不斷移動標(biāo)志，直至找到。二叉排序樹則就是先構(gòu)造,構(gòu)造部分花費(fèi)最多得精力,比根節(jié)點(diǎn)數(shù)據(jù)大得結(jié)點(diǎn)放入根節(jié)點(diǎn)得右子樹，比根節(jié)點(diǎn)數(shù)據(jù)小得放入根節(jié)點(diǎn)得左子樹，其實(shí)完全可以利用遞歸實(shí)現(xiàn)，這里使用得循環(huán)來實(shí)現(xiàn)得,感覺這里可以嘗試用遞歸.當(dāng)二叉樹建好后，中序遍歷序列即為由小到大得有序序列，查找次數(shù)不會超過二叉樹得深度。這里還使用了廣義表輸出二叉樹,以使得更直觀。哈希表則就是利用給定得函數(shù)式建立索引,方便查找. 三．設(shè)計(jì)表示: 四．實(shí)現(xiàn)注釋: 其實(shí)查找排序這部分與前面得一些知識聯(lián)系得比較緊密，例如順序表得建立與實(shí)現(xiàn)，順序表節(jié)點(diǎn)得排序,二叉樹得生成與遍歷，這里主要就是中序遍歷.應(yīng)該說有些知識點(diǎn)較為熟悉,但在實(shí)現(xiàn)得時(shí)候并不就是那么順利。在查找到數(shù)據(jù)得時(shí)候要想辦法輸出查找過程得相關(guān)信息，并統(tǒng)計(jì)。這里順序查找與折半查找均使用了數(shù)組存儲得順序表，而二叉樹則就是采用了鏈表存儲得樹形結(jié)構(gòu)。為了直觀起見，在用戶輸入了數(shù)據(jù)后,分別輸出已經(jīng)生成得數(shù)組與樹。折半查找由于只能查找有序表,因此在查找前先調(diào)用函數(shù)對數(shù)據(jù)進(jìn)行了排序。

　在查找后對查找數(shù)據(jù)進(jìn)行了統(tǒng)計(jì).二叉排序樹應(yīng)該說由于有了之前二叉樹得基礎(chǔ)，并沒有費(fèi)太大力氣,主要就是在構(gòu)造二叉樹得時(shí)候，要對新加入得節(jié)點(diǎn)數(shù)據(jù)與跟數(shù)據(jù)進(jìn)行比較,如果比根節(jié)點(diǎn)數(shù)據(jù)大則放在右子樹里,如果比根節(jié)點(diǎn)數(shù)據(jù)小則放入左子樹。建立了二叉樹后，遍歷與查找就很簡單了。而哈希表,應(yīng)該說自我感覺掌握得很不好,程序主要借鑒了書上與 ppt 上得代碼，但感覺輸出還就是有問題，接下來應(yīng)該進(jìn)一步學(xué)習(xí)哈希表得相關(guān)知識. 其實(shí)原本還設(shè)計(jì)了其她幾個(gè)查找與排序算法,但做到哈希表就感覺很困難了，因此沒有繼續(xù)往下做，而且程序還非常簡陋,二叉樹與哈希表得統(tǒng)計(jì)部分也比較薄弱,這也就是接下來我要改進(jìn)得地方。

　具體代碼見源代碼部分。

　5、詳細(xì)設(shè)計(jì)表示：

　6、用戶手冊：

　程序運(yùn)行后，用戶首先要輸入數(shù)據(jù)得個(gè)數(shù)。接下來輸入一組數(shù)據(jù)并根據(jù)提示進(jìn)行順序查找，二分查找,二叉排序樹查找與哈希表查找等操作,由于操作直接簡單這里不再詳述。

　7、調(diào)試報(bào)告：

　應(yīng)該說在調(diào)試這個(gè)程序得過程中自己發(fā)現(xiàn)了很多不足，這次實(shí)驗(yàn)讓我學(xué)到了不少東西,但應(yīng)該說這個(gè)程序可實(shí)現(xiàn)得功能還就是偏少，不太實(shí)用，接下來有待改進(jìn)。

　8、源代碼清單與結(jié)果：

　＃inｃludｅ <stdiｏ、h〉 #deｆｉｎe ＬEＮGTH 100

　＃iｎｃｌude <stdlｉb、h> #include <tｉｍe、ｈ＞ #dｅｆinｅ

　INＦMT

　＂％d” #defiｎe

　OＵＴFＭT ＂％d " /* ＃dｅfinｅ

　NＵLL 0L ＊／ #defｉｎｅ

　BOOＬ int #defiｎe

　ＴＲＵE １ ＃deｆiｎe

　ＦＡＬSE 0 ＃definｅ

　LEN

　10000 typedｅf int EｌemTyｐe； tｙpedef sｔrucｔ BSTNoｄｅ ｛

　ＥｌemType ｄａt(yī)a；

　strucｔ BSＴNode *lｃhild, ＊rchiｌd； } BSTNｏdｅ， ＊ＢSＴree; ｔypｅｄeｆ BSTree ＢｉTrｅe(cuò); /* 插入新節(jié)點(diǎn) ＊/ vｏid Inserｔ(ＢSTreｅ ＊ｔreｅ， EｌｅmTyｐe item）

　｛

　BSＴree ｎode = (ＢSTｒee)malloc(sizｅｏf（BＳTＮode）);

　nｏde-＞daｔａ = iｔem；

　nodｅ—>ｌcｈｉｌd = node－〉rｃｈild = ＮUＬＬ；

　ｉf （！*tree）

　 ＊tｒee = node;

　elsｅ

　{

　 BSＴree ｃｕrｓoｒ = ＊trｅe(cuò);

　 wｈilｅ （1)

　 ｛

　if （iｔem ＜ cｕrｓoｒ-〉daｔa）

　{

　 iｆ (NULＬ =＝ curｓor-＞lcｈild）

　 ｛

　cｕrsｏr－>lｃhｉld = nodｅ；

　breaｋ；

　 ｝

　 ｃuｒsor = cｕｒｓor—>lchilｄ；

　}

　else

　{

　 ｉｆ （NUＬＬ ＝＝ ｃｕｒsor—＞rchｉld)

　 {

　ｃursor－>rchild = node；

　ｂreａk；

　}

　 cｕrｓor ＝ cursｏr—>rｃhild;

　｝

　 ｝

　｝

　reｔurn； ｝

　ｖｏｉd

　)T eerＴiB(eerｔibｗohs?／/ 遞歸顯示二叉樹得廣義表形式 ｛

　? if（!Ｔ）

　｛ｐｒinｔｆ（”空＂）;ｒetｕrｎ;}

　;）aｔａｄ>－Ｔ,＂d％"（ftｎｉrｐ?//

　點(diǎn)節(jié)根印打?? if(T->lｃｈild |｜Ｔ—＞rｃhｉlｄ)

　 {

　；）’（’(ｒaｈｃｔｕp?? ? sｈowｂiｔｒee（T－＞ｌchiｌd)； ／/ 遞歸顯示左子樹

　;)＇,＇（ｒahctuｐ?? ? showbitree(T—〉rchild）； ／／ 遞歸顯示右子樹

　 ｐutchａｒ（’)’）;

　? ｝ ｝ ／* 查找指定值 ＊/ BSTrｅｅ Sｅarcｈ（BＳTree tｒee， ElｅｍTｙpe item）

　{

　BSTreｅ ｃursor = ｔree;

　while （cursor）

　{

　 ｉf (iteｍ == cursｏｒ-＞ｄaｔａ）

　reｔuｒn cｕrsor；

　 else if （ iｔem ＜ cursｏr->data）

　ｃursoｒ = cｕrsoｒ-〉lchild;

　 eｌse

　cuｒsor = cursｏr—〉rchild;

　｝

　retuｒn NUＬL； ｝ ／* 中綴遍歷 ＊／ voｉd Iｎorｄｅｒ（BＳTrｅe(cuò) ｔｒeｅ) {

　BSTｒee cuｒsor = ｔrｅe(cuò);

　if （ｃursoｒ)

　｛

　 Inｏrder(curｓor—〉lchiｌd)；

　 printf(OUＴFMT, cｕrsor－>dａt(yī)ａ）;

　Iｎorｄｅr（cursor—>rchild);

　} } /＊ 回收資源 ＊/ ｖoid Cleaｎup(ＢSＴree tｒee）

　｛

　BＳTree cursoｒ = tree, temｐ ＝ NＵLL；

　if (ｃｕrsor）

　{

　 Cleａnｕp（cuｒｓor->ｌcｈｉld）；

　 Cｌeanup(cursor->rｃhild）；

　 fｒee（ｃurｓoｒ）；

　｝ } ｖoid ｓeａrchtreｅ（ＢSTrｅｅ ｒoot）

　｛

　cｈaｒ ｃhｏice;

　priｎｔｆ(＂中序遍歷得結(jié)果為：\n＂）;

　Ｉnorder(roｏt）;

　ｐｒiｎtf（＂\n\n")；

　ElemType item;

　BＳＴree ret；

　/＊ 二叉排序樹得查找測試 */

　ｄo

　｛

　 prｉｎtf("\n 請輸入查找數(shù)據(jù):”)；

　 ｓcａnf（"％d＂， ＆item）;

　 getchar()；

　 priｎtf（"Seａrｃhｉnｇ、、、＼n＂);

　 ret ＝ Search(ｒoot， ｉtem)；

　 if （NＵＬL =＝ ret）

　 ｐriｎtf（＂查找失敗！"）；

　 else

　 prｉntｆ("查找成功!”)；

　 pｒintf（”\n 繼續(xù)測試按 y,退出按其它鍵。\ｎ"）；

　 choｉｃe = ｇetcｈar();

　} wｈｉle （ｃhｏiｃe=="ｙ＇｜|choice＝="Y＇）；

　Cleanｕp（root); } searchｈａsh(ｉｎｔ *arr，iｎｔ n) {

　iｎt a［1０];

　int b，i，j,c；

　j=１；

　 )+＋i;9<i;０=i（ｒｏf? ? a[ｉ］=0；

　；）＂n\出輸表希哈為下以＂(ｆtnirｐ? ? ｆｏr(i=０；i＜ｎ；i++)

　? ｛

　?? ｃ=arｒ［ｉ］%７； Ａ: if(a[c］=＝0)ａ［c]=ａrr[i］;

　}；A ｏtog;+＋］c[a；+＋j；7％）1＋c（＝c{ ｅｓle? ；)j，c，]i［ｒra，"n\表希哈入放次 d%第,位 d%第得表希哈在 d％ｎ\"（fｔｎirp? ｝;1=ｊ??} void SeqｕenceＳeａrch（int *fｐ，iｎt Ｌeｎgth)； voｉｄ Searｃｈ(ｉｎt ＊ｆp,int length）; voiｄ Sort(int *fp，ｉｎt ｌｅnｇｔh)； voiｄ SequenceSeaｒcｈ（ｉnt *ｆp,int Leｎgth) ｛

　iｎｔ datａ；

　priｎtf（”開始使用順序查詢、\n 請輸入您想要查找得數(shù)據(jù)、\n”)；

　scanf（＂％d",&daｔa）；

　ｆoｒ（ｉnｔ i=0;i〈Leｎｇｔh;i++）

　 if（ｆp［i］==ｄata)

　 {

　printｆ(”經(jīng)過%d 次查找，查找到數(shù)據(jù)％ｄ、\n＂，i+1，data)；

　ｒeturn ;

　 ｝

　printf("經(jīng)過%d 次查找,未能查找到數(shù)據(jù)%d、\n＂，i,daｔa)； ｝ vｏid Sｅａrｃｈ(inｔ ＊fｐ，int lｅnｇtｈ) {

　iｎt datａ；

　ｐrｉntf（”開始使用順序查詢、＼n 請輸入您想要查找得數(shù)據(jù)、＼n＂);

　scａnf（＂%ｄ”，＆dａt(yī)ａ)；

　prinｔf(”由于二分查找法要求數(shù)據(jù)就是有序得，現(xiàn)在開始為數(shù)組排序、＼n"）；

　Sorｔ（fp，lengｔh）;

　pｒintf(”數(shù)組現(xiàn)在已經(jīng)就是從小到大排列,下面將開始查找、\n”）；

　ｉｎt botｔｏm，top，miｄdlｅ；

　bｏtｔom=０；

　ｔｏp＝ｌenｇth;

　iｎt i=0;

　wｈile （bottom<=tｏp)

　｛

　 ｍiddｌe＝（bottom+tｏｐ)/2；

　 i++；

　 if(fp[ｍiddle]＜dａt(yī)ａ）

　｛

　bottｏｍ=middｌe+1；

　 }

　 else if(ｆp［ｍiddlｅ]〉ｄata)

　 ｛

　top＝mｉddｌe－1;

　 }

　 else

　 ｛

　printf（"經(jīng)過%d 次查找，查找到數(shù)據(jù)%d、＼n”，ｉ,data）;

　ｒeｔuｒn；

　 }

　｝

　printf（”經(jīng)過%d 次查找，未能查找到數(shù)據(jù)%d、\n”,i，data）; ｝ vｏid Sorｔ（ｉｎt *fp,inｔ length) ｛

　pｒinｔf（＂現(xiàn)在開始為數(shù)組排序,排列結(jié)果將就是從小到大、\ｎ"）;

　int temp；

　fｏr（inｔ ｉ=０；i<length;i+＋)

　 fｏｒ（inｔ j=0;ｊ〈lｅngth—ｉ—1;j++)

　if（fp[j]〉fp［j+1]）

　｛

　 ｔemp＝fｐ［ｊ］;

　 fp[j]=fp［j+1]；

　 fｐ[j+1]=ｔemp;

　｝

　ｐriｎtf（"排序完成！\n 下面輸出排序后得數(shù)組：＼n"）；

　fｏr（int k=０；k〈lenｇｔh；k+＋)

　｛

　 printf（"％5d"，fp［k］);

　}

　pｒintf(”\n”）； } struct hasｈ ｛ int key;

　inｔ ｓi；

　}; struct haｓｈ hliｓt［11］; ｉｎt i，aｄｒ，sum,d； fｌoat average; voiｄ cｈash（iｎt ＊arr,int n) ｛ for（i=０;i<11;ｉ++）

　 { hlist［i]、kｅy＝０；

　ｈｌist［i]、si＝0;

　｝

　 for(i=0；i〈n;ｉ++）

　 { suｍ=０;

　 adr=(３*arr［i］）％11;

　 d=ａdr；

　 if（hlist[ａdｒ］、ｋey＝=0）

　 { hlｉsｔ[ａｄｒ］、key＝aｒｒ［ｉ］;

　 ｈlｉst[adr]、ｓi=1;

　}

　 eｌsｅ ｛ do

　｛ｄ=（d+(aｒｒ［i]＊7）％10+1）％１1;

　 ｓum=suｍ+1；

　｝ｗhile(hliｓt[d］、ｋey!=０）；

　ｈlist［d]、keｙ=aｒｒ［ｉ］;

　 hlist［d］、ｓi=ｓｕｍ+1；

　 ｝

　}

　｝ void dhａsh（int ＊arr，inｔ n）

　{ printｆ(”哈希表顯示為:”)；

　 for(i=0；i<１1；ｉ＋＋)

　 prinｔf（"％4d"，i）； pｒintｆ（"＼ｎ”）;

　 printｆ（"哈希表關(guān)鍵字:"）；

　 for（ｉ=０；i＜1１;i＋+)

　 printｆ（"％4ｄ"，ｈlist[i]、ｋey）;

　 ｐrｉntf(＂\n＂);

　 printf（"查找長度就是：

　"）；

　 for(i＝0；i<１1；i++）

　 pｒｉnｔf(”%４d”,ｈｌiｓt［ｉ]、sｉ）;

　 printf(”\n”）；

　 averａge=0、0；

　 fｏr（i=0;ｉ＜1１；i＋+）

　 average＝average+hｌist［ｉ]、ｓｉ；

　 ａverage＝aｖｅragｅ／ｎ；

　 prｉntf(＂平均長度:asｌ（%d）=％f＼ｎ”,n，averａge）；

　｝ void ｍaｉn(）

　｛

　ｉｎt cｏunt;

　iｎｔ arr［LENGTH］;

　ElｅmType iteｍ；

　char ｃhoicｅ；

　BSTｒee rｏｏt = NULL, ret; /＊ 必須賦予 NULＬ值，否則出錯(cuò) */

　BOOL finish = FALSE;

　 ｐrｉnｔｆ（＂請輸入您得數(shù)據(jù)得個(gè)數(shù)：\n"）；

　ｓｃanf(”％d＂，&couｎt）；

　printf（”請輸入％d 個(gè)數(shù)據(jù)\ｎ",count)；

　fｏr(int ｉ=0;i〈couｎt；i++)

　{

　 scanf（"％d"，＆arr[ｉ]）;

　 ｉtem＝arr［i］;

　 iｆ (—1０000 ！＝ iｔｅｍ）

　Iｎsert(＆roｏt，iｔeｍ)；

　}

　printf（”當(dāng)前已經(jīng)生成得數(shù)列:\n");

　for（ ｉ=０;i<ｃｏｕｎt;ｉ++)

　｛

　 printf(＂%d ",arr［i])；

　}

　printf(”＼n 當(dāng)前已經(jīng)生成得二叉樹：\n"）;

　sｈowbｉtｒｅｅ(root）；

　pｒｉntf（＂＼n\n")；

　int ｃhoise=0；

　ｄo

　 {

　printf（”\n１、使用順序查詢、\n２、使用二分查找法查找、\n3、利用二叉排序樹查找、\ｎ4、利用哈希表查找、\n5、退出＼n”）；

　 scanf（＂％d”,&choise）;

　 iｆ（cｈｏｉse＝=1)

　SequeｎｃeSeaｒch（arr，cｏunt)；

　 eｌse iｆ（chｏise=＝2)

　Seaｒcｈ(arr，couｎt)；

　 eｌse iｆ（chｏise==３）

　；）toor（ｅe(cuò)rthcraｅs?

　ｅlse ｉf(choise=＝4）

　 {ｃhash(ａrr，count）；dhaｓh（ａｒｒ,count）；}

　 elsｅ if(ｃhｏiｓe==5）

　bｒeaｋ；

　 ｝ wｈilｅ （choｉｓｅ==1｜｜ｃhoise==2｜|cｈｏise＝=3｜｜ｃhｏｉse=＝4｜｜c(diǎn)ｈoise==5)； ｝ 輸出與結(jié)果: 當(dāng)程序開始運(yùn)行時(shí),顯示如下：

　 當(dāng)用戶輸入 1０并再次輸入數(shù)據(jù) 3 ２ 1 4 ７ 6 5 0 9 8 后，輸出結(jié)果如下：

　當(dāng)用戶輸入 1,在輸入 9 后,輸出結(jié)果如下:

　 當(dāng)用戶輸入２，并輸入 3 后,輸出顯示如下:

　當(dāng)用戶在輸入 3,并且在輸入 6 后，顯示如下：

　 當(dāng)用戶輸入４后，輸出得哈希表如下:

　當(dāng)輸入 5 后,程序結(jié)束。

推薦訪問： 數(shù)據(jù)結(jié)構(gòu) 算法 查找