數(shù)據(jù)結(jié)構(gòu)查找算法實(shí)驗(yàn)報(bào)告.doc

《數(shù)據(jù)結(jié)構(gòu)查找算法實(shí)驗(yàn)報(bào)告.doc》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫(kù)。

1、數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)第四章：實(shí)驗(yàn):簡(jiǎn)單查找算法一．需求和規(guī)格說(shuō)明：查找算法這里主要使用了順序查找，折半查找，二叉排序樹(shù)查找和哈希表查找四種方法。由于自己能力有限，本想實(shí)現(xiàn)其他算法，但沒(méi)有實(shí)現(xiàn)。其中順序查找相對(duì)比較簡(jiǎn)單，折半查找參考了書(shū)上的算法，二叉排序樹(shù)查找由于有之前做二叉樹(shù)的經(jīng)驗(yàn)，因此實(shí)現(xiàn)的較為順利，哈希表感覺(jué)做的并不成功，感覺(jué)還是應(yīng)該可以進(jìn)一步完善，應(yīng)該說(shuō)還有很大的改進(jìn)余地。二．設(shè)計(jì)思想：開(kāi)始的時(shí)候提示輸入一組數(shù)據(jù)。并存入一維數(shù)組中，接下來(lái)調(diào)用一系列查找算法對(duì)其進(jìn)行處理。順序查找只是從頭到尾進(jìn)行遍歷。二分查找則是先對(duì)數(shù)據(jù)進(jìn)行排

2、序，然后利用三個(gè)標(biāo)志，分別指向最大，中間和最小數(shù)據(jù)，接下來(lái)根據(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ù)式建立索引，方便查找。三．設(shè)計(jì)表示：四．實(shí)現(xiàn)注釋?zhuān)浩鋵?shí)查找排序這部分和前面的一

3、些知識(shí)聯(lián)系的比較緊密，例如順序表的建立和實(shí)現(xiàn)，順序表節(jié)點(diǎn)的排序，二叉樹(shù)的生成和遍歷，這里主要是中序遍歷。應(yīng)該說(shuō)有些知識(shí)點(diǎn)較為熟悉，但在實(shí)現(xiàn)的時(shí)候并不是那么順利。在查找到數(shù)據(jù)的時(shí)候要想辦法輸出查找過(guò)程的相關(guān)信息，并統(tǒng)計(jì)。這里順序查找和折半查找均使用了數(shù)組存儲(chǔ)的順序表，而二叉樹(shù)則是采用了鏈表存儲(chǔ)的樹(shù)形結(jié)構(gòu)。為了直觀起見(jiàn)，在用戶輸入了數(shù)據(jù)后，分別輸出已經(jīng)生成的數(shù)組和樹(shù)。折半查找由于只能查找有序表，因此在查找前先調(diào)用函數(shù)對(duì)數(shù)據(jù)進(jìn)行了排序。在查找后對(duì)查找數(shù)據(jù)進(jìn)行了統(tǒng)計(jì)。二叉排序樹(shù)應(yīng)該說(shuō)由于有了之前二叉樹(shù)的基礎(chǔ)，并沒(méi)有費(fèi)太大力氣，主要是在構(gòu)造

4、二叉樹(shù)的時(shí)候，要對(duì)新加入的節(jié)點(diǎn)數(shù)據(jù)和跟數(shù)據(jù)進(jìn)行比較，如果比根節(jié)點(diǎn)數(shù)據(jù)大則放在右子樹(shù)里，如果比根節(jié)點(diǎn)數(shù)據(jù)小則放入左子樹(shù)。建立了二叉樹(shù)后，遍歷和查找就很簡(jiǎn)單了。而哈希表，應(yīng)該說(shuō)自我感覺(jué)掌握的很不好，程序主要借鑒了書(shū)上和ppt上的代碼，但感覺(jué)輸出還是有問(wèn)題，接下來(lái)應(yīng)該進(jìn)一步學(xué)習(xí)哈希表的相關(guān)知識(shí)。其實(shí)原本還設(shè)計(jì)了其他幾個(gè)查找和排序算法，但做到哈希表就感覺(jué)很困難了，因此沒(méi)有繼續(xù)往下做，而且程序還非常簡(jiǎn)陋，二叉樹(shù)和哈希表的統(tǒng)計(jì)部分也比較薄弱，這也是接下來(lái)我要改進(jìn)的地方。具體代碼見(jiàn)源代碼部分。5.詳細(xì)設(shè)計(jì)表示：6.用戶手冊(cè)：程序運(yùn)行后，用戶首先

5、要輸入數(shù)據(jù)的個(gè)數(shù)。接下來(lái)輸入一組數(shù)據(jù)并根據(jù)提示進(jìn)行順序查找，二分查找，二叉排序樹(shù)查找和哈希表查找等操作，由于操作直接簡(jiǎn)單這里不再詳述。7.調(diào)試報(bào)告：應(yīng)該說(shuō)在調(diào)試這個(gè)程序的過(guò)程中自己發(fā)現(xiàn)了很多不足，這次實(shí)驗(yàn)讓我學(xué)到了不少東西，但應(yīng)該說(shuō)這個(gè)程序可實(shí)現(xiàn)的功能還是偏少，不太實(shí)用，接下來(lái)有待改進(jìn)。8.源代碼清單和結(jié)果：#include#defineLENGTH100#include#include#defineINFMT"%d"#defineOUTFMT"%d"/*#defineNULL

6、0L*/#defineBOOLint#defineTRUE1#defineFALSE0#defineLEN10000typedefintElemType;typedefstructBSTNode{ElemTypedata;structBSTNode*lchild,*rchild;}BSTNode,*BSTree;typedefBSTreeBiTree;/*插入新節(jié)點(diǎn)*/voidInsert(BSTree*tree,ElemTypeitem){BSTreenode=(BSTree)malloc(sizeof(BSTNode));no

7、de->data=item;node->lchild=node->rchild=NULL;if(!*tree)*tree=node;else{BSTreecursor=*tree;while(1){if(itemdata){if(NULL==cursor->lchild){cursor->lchild=node;break;}cursor=cursor->lchild;}else{if(NULL==cursor->rchild){cursor->rchild=node;break;}cursor=cursor->

8、rchild;}}}return;}voidshowbitree(BiTreeT)//遞歸顯示二叉樹(shù)的廣義表形式{if(!T){printf("空");return;}printf("%d",T->data);//打印根節(jié)點(diǎn)if(T->lchild