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

2、，中間和最 小數(shù)據(jù)，接下來根據(jù)待查找數(shù)據(jù)和中間數(shù)據(jù)的比較不斷移動標(biāo)志，直至找到。二叉排序樹則是先構(gòu)造，構(gòu) 造部分花費最多的精力，比根節(jié)點數(shù)據(jù)大的結(jié)點放入根節(jié)點的右子樹，比根節(jié)點數(shù)據(jù)小的放入根節(jié)點的左 子樹，其實完全可以利用遞歸實現(xiàn)，這里使用的循環(huán)來實現(xiàn)的，感覺這里可以嘗試用遞歸。當(dāng)二叉樹建好 后，中序遍歷序列即為由小到大的有序序列，查找次數(shù)不會超過二叉樹的深度。這里還使用了廣義表輸岀 二叉樹，以使得更直觀。哈希表則是利用給定的函數(shù)式建立索引，方便查找。三.設(shè)計表示：四實現(xiàn)注釋：其實查找排序這部分和前面的一些知識聯(lián)系的比較緊密，例如順序表的建立和實現(xiàn)，順序表節(jié)點的排序， 二叉樹的生成和遍歷，這里

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

4、查找就很簡單了。而哈希表，應(yīng)該說自 我感覺掌握的很不好，程序主要借鑒了書上和ppt上的代碼，但感覺輸岀還是有問題，接下來應(yīng)該進一步學(xué)習(xí)哈希表的相關(guān)知識。其實原本還設(shè)計了其他幾個查找和排序算法，但做到哈希表就感覺很困難了，因此沒有繼續(xù)往下做，而且程序還非常簡陋，二叉樹和哈希表的統(tǒng)計部分也比較薄弱，這也是接下來我要改進的地方。 具體代碼見源代碼部分。5. 詳細設(shè)計表示：6. 用戶手冊：程序運行后，用戶首先要輸入數(shù)據(jù)的個數(shù)。接下來輸入一組數(shù)據(jù)并根據(jù)提示進行順序查找，二分查找，二 叉排序樹查找和哈希表查找等操作，由于操作直接簡單這里不再詳述。7. 調(diào)試報告：應(yīng)該說在調(diào)試這個程序的過程中自己發(fā)現(xiàn)了很多不

5、足，這次實驗讓我學(xué)到了不少東西，但應(yīng)該說這個程序 可實現(xiàn)的功能還是偏少，不太實用，接下來有待改進。8. 源代碼清單和結(jié)果：#include <stdio.h>#define LENGTH 100#include <stdlib.h>#include <time.h>#defineINFMT"%d"#defineOUTFMT"%d "/* #defineNULL 0L */#defineBOOL int#defineTRUE 1#defineFALSE 0#defineLEN10000typedef int ElemTy

6、pe;typedef struct BSTNodeElemType data;struct BSTNode *lchild, *rchild; BSTNode, *BSTree;typedef BSTree BiTree;/*插入新節(jié)點*/void Insert(BSTree *tree, ElemType item)BSTree node = (BSTree)malloc(sizeof(BSTNode);node->data = item;node->lchild = node->rchild = NULL;if (!*tree)*tree = node;elseBSTre

7、e cursor = *tree;while (1)if (item < cursor->data)if (NULL = cursor->lchild)cursor->lchild = node; break;cursor = cursor->lchild;elseif (NULL = cursor->rchild) cursor->rchild = node; break;cursor = cursor->rchild;return;void showbitree(BiTree T)/遞歸顯示二叉樹的廣義表形式if(!T) printf(” 空

8、”);return; printf("%d",T->data);/ 打印根節(jié)點if(T->lchild |T->rchild)putchar('(');showbitree(T->lchild); / 遞歸顯示左子樹putchar(',');showbitree(T->rchild); / 遞歸顯示右子樹putchar(')');/*查找指定值*/BSTree Search(BSTree tree, ElemType item)BSTree cursor = tree;while (cursor)

9、if (item = cursor->data) return cursor;else if ( item < cursor->data) cursor = cursor->lchild;elsecursor = cursor->rchild;return NULL;/*中綴遍歷*/void lnorder(BSTree tree)BSTree cursor = tree;if (cursor)Inorder(cursor->lchild); printf(OUTFMT, cursor->data); Inorder(cursor->rchild

10、);/*回收資源*/void Cleanup(BSTree tree)BSTree 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;/*二叉排序樹的查找測試 */dopr

11、intf("n請輸入查找數(shù)據(jù)：");scanf("%d", &i tem);getchar();printf("Searching.n");ret = Search(root, item);if (NULL = ret)printf("查找失??！");elseprintf("查找成功！");printf("n繼續(xù)測試按y,退出按其它鍵。n");choice = getchar(); while (choice='y'|choice='Y'

12、;);Cleanup(root); searchhash(int *arr,int n)int a10;int b,i,j,c;j=1;for(i=0;i<9;i+)ai=0;printf("以下為哈希表輸出n");for(i=0;i<n;i+)c=arri%7;A:if(ac=0)ac=arri;else c=(c+1)%7;j+;ac+;goto A;printf("n%d在哈希表的第 %d位，第%d次放入哈希表n",arri,c,j);j=1; void SequenceSearch(int *fp,int Length);void S

13、earch(int *fp,int length);void Sort(int *fp,int length);void SequenceSearch(int *fp,int Length)int data;printf("開始使用順序查詢.n請輸入你想要查找的數(shù)據(jù).n");scanf("%d",&data);for(int i=O;i<Length;i+)if(fpi=data)printf("經(jīng)過%d次查找，查找到數(shù)據(jù) %d.n",i+1,data); return ;printf("經(jīng)過%d次查找，未能查

14、找到數(shù)據(jù)%d.n",i,data);void Search(int *fp,int length)int data;printf("開始使用順序查詢.n請輸入你想要查找的數(shù)據(jù).n");scanf("%d",&data);.n");printf("由于二分查找法要求數(shù)據(jù)是有序的，現(xiàn)在開始為數(shù)組排序Sort(fp,length);printf("數(shù)組現(xiàn)在已經(jīng)是從小到大排列，下面將開始查找.n");int bottom,top,middle;bottom=0;top=length;int i=0;whi

15、le (bottom<=top)middle=(bottom+top)/2;i+;if(fpmiddle<data)bottom=middle+1;else if(fpmiddle>data)top=middle-1;elseprintf(”經(jīng)過%d次查找，查找到數(shù)據(jù) %d.n",i,data); return;printf("經(jīng)過%d次查找，未能查找到數(shù)據(jù)%d.n",i,data);void Sort(int *fp,int length)printf("現(xiàn)在開始為數(shù)組排序，排列結(jié)果將是從小到大.n");int temp;f

16、or(int i=O;i<length;i+)for(int j=0;j<length-i-1;j+)if(fpj>fpj+1)temp=fpj;fpj=fpj+1;fpj+1=temp;printf("排序完成!n下面輸出排序后的數(shù)組:n");for(int k=O;k<length;k+)printf("%5d",fpk);printf("n");struct hash int key;int si;struct hash hlist11;int i,adr,sum,d; float average;voi

17、d chash(int *arr,int n) for(i=0;i<11;i+) hlisti.key=O;hlisti.si=O;for(i=0;i<n;i+) sum=0;adr=(3*arri)%11;d=adr;if(hlistadr.key=O) hlistadr.key=arri;hlistadr.si=1;else dod=(d+(arri*7)%10+1)%11; sum=sum+1;while(hlistd.key!=O);hlistd.key=arri;hlistd.si=sum+1; void dhash(int *arr,int n) printf(”哈希表

18、顯示為：")；for(i=0;i<11;i+)printf("%4d",i); printf("n");printf("哈希表關(guān)鍵字:");for(i=0;i<11;i+)printf("%4d",hlisti.key);printf("n");printf("查找長度是:");for(i=0;i<11;i+)printf("%4d",hlisti.si);printf("n");average=0.0;fo

19、r(i=0;i<11;i+)average=average+hlisti.si;average=average/n;printf("平均長度:asl(%d)=%fn",n,average); void main()int count;int arrLENGTH;ElemType item;char choice;BSTree root = NULL, ret; /* 必須賦予 NULL 值，否則出錯 */BOOL finish = FALSE;printf("請輸入你的數(shù)據(jù)的個數(shù):n"); scanf("%d",&cou

20、nt);printf("請輸入 %d 個數(shù)據(jù) n",count);for(int i=0;i<count;i+)scanf("%d", &arri);item=arri;if (-10000 != item)Insert (&root,item);printf("當(dāng)前已經(jīng)生成的數(shù)列：n");for( i=0;i<count;i+)printf("%d ",arri);printf("n當(dāng)前已經(jīng)生成的二叉樹：n"); showbitree(root);printf(&q

21、uot;nn");int choise=0;doprintf("n1.使用順序查詢.n2.使用二分查找法查找.n3.利用二叉排序樹查找.n4.利用哈希表查找.n5.退出 n");scanf("%d", &choise);if(choise=1)SequenceSearch(arr,count);else if(choise=2)Search(arr,count);else if(choise=3)searchtree(root);else if(choise=4)chash(arr,count);dhash(arr,count);els

22、e if(choise=5)break; while (choise=1|choise=2|choise=3|choise=4|choise=5);輸出和結(jié)果：當(dāng)程序開始運行時，顯示如下:當(dāng)用戶輸入10并再次輸入數(shù)據(jù) 3 2 1 4 7 6 5 0 9 8后，輸出結(jié)果如下:環(huán)據(jù)結(jié)梅實鑿'查找一綜合2Debug查找綜臺也exe-日回惰輸用的數(shù)據(jù)的個數(shù)J請輸入佃個數(shù)據(jù)3214765098當(dāng)前已經(jīng)生成的數(shù)列：；2147651398當(dāng)前已經(jīng)生成的二叉樹：:K2C15 空，空，必空，"魚匚空佃，空咅查. 詢找 查查榮 ，客叉希 順二二哈 用用用 使使退當(dāng)用戶輸入1，在輸入9后，輸出結(jié)果如下:輕=據(jù)結(jié)構(gòu)實鯊'查找_綜2DebufiW找一綜合障輸入謫個數(shù)據(jù)321