數(shù)據(jù)結(jié)構(gòu)查找算法課程設(shè)計報告書

1、|西安 *課程設(shè)計說明書設(shè)計題目：查找算法性能分析系別：計算機學(xué)院專業(yè)：計算機科學(xué)班級：計科*姓名：王*（共頁）2015年01月07日*計算機科學(xué) 專業(yè)課程設(shè)計任務(wù)書姓名： *班級： 計科*學(xué)號： *一、設(shè)計或?qū)嵺`題目查找算法性能分析二、內(nèi)容及要求設(shè)計程序，對比分析順序查找、折半查找、索引查找、二叉排序樹查找和散列查找 五種查找算法的性能1、測試數(shù)據(jù)的個數(shù)不少于 50個；2、對每一種查找算法設(shè)計實現(xiàn)適應(yīng)的存儲結(jié)構(gòu)；3、輸出每種查找算法的查找成功時的平均長度三、完成形式1、設(shè)計報告;2、源程序四、系（部）審核意見指導(dǎo)教師： *發(fā)題日期： 2015-01-05完成日期： 2015-01-09需求分

2、析1. 1 問題描述查找又稱檢索，是指在某種數(shù)據(jù)結(jié)構(gòu)中找出滿足給定條件的元素。查找是 一種十分有用的操作。而查找也有內(nèi)外之分，若整個查找過程只在內(nèi)存中進(jìn)行 稱為內(nèi)查找；若查找過程中需要訪問外存，則稱為外查找，若在查找的同時對 表做修改運算(插入或刪除) ，則相應(yīng)的表成為動態(tài)查找表，反之稱為靜態(tài)查找 表。由于查找運算的主要運算是關(guān)鍵字的比較，所以通常把查找過程中對關(guān)鍵 字的平均比較次數(shù)(也叫平均查找長度)作為一個查找算法效率優(yōu)劣的標(biāo)準(zhǔn)。 平均查找程度 ASL 定義為：ASL=刀 PiCi (i 從 1 到 n)其中 Pi 代表查找第 i 個元素的概率，一般認(rèn)為每個元素的查找概率相等， Ci 代表

3、找到第 i 個元素所需要比較的次數(shù)。查找算法有順序查找、折半查找、索引查找、二叉樹查找和散列查找(又叫哈 希查找)，它們的性能各有千秋，對數(shù)據(jù)的存儲結(jié)構(gòu)要求也不同，譬如在順序查找中 對表的結(jié)果沒有嚴(yán)格的要求，無論用順序表或鏈?zhǔn)奖泶鎯υ囟伎梢圆檎页晒?；?半查找要求則是需要順序表；索引表則需要建立索引表；動態(tài)查找需要的樹表查找 則需要建立建立相應(yīng)的二叉樹鏈表；哈希查找相應(yīng)的需要建立一個哈希表。1. 2 基本要求(1) 輸入的形式和輸入值的范圍；在設(shè)計查找算法性能分析的過程中，我們調(diào)用產(chǎn)生隨機數(shù)函數(shù)： srand(int)time(0);產(chǎn)生N個隨機數(shù)。注：折半查找中需要對產(chǎn)生的隨機數(shù)進(jìn)行排序，

4、需要進(jìn)行排序后再進(jìn)行輸入， N<50;( 2 ) 輸出形式；查找算法分析過程中，只要對查找算法稍作修改就可以利用平均查找 長度的公式：ASL= 刀 PiCi (i 從 1 到 n) 輸出各種查找算法的平均查找長度。注：平均查找長度 =總的平均查找長度 /N ；(3) 程序所能達(dá)到的功能通過輸出幾種查找算法的 ASL,我們很顯然能得在數(shù)據(jù)量較小時(N100)我們在實現(xiàn)靜態(tài)查找時應(yīng)該選擇如何調(diào)用哪種查找算法。二 概要設(shè)計 說明本程序中用到的所有抽象數(shù)據(jù)類型的定義。主程序的流程以及各程序模塊之間 的層次(調(diào)用 )關(guān)系。1、數(shù)據(jù)結(jié)構(gòu)順序查找 ：在進(jìn)行順序查找順序表類型定時需要定義 typedef

5、 int KeyType ； 順序表類型為 SeqList 類型。 typedef NodeType SeqList【MaxSize】；/它的基本思路是：從表的一端開始，順序掃描線性表，依次將掃描到的關(guān)鍵字和給定值k相比較，若當(dāng)前掃描到的關(guān)鍵字與k相等，查找成功。折半查找：在進(jìn)行順序查找順序表類型定時需要定義typedef int KeyType，并且需要調(diào)用排序函數(shù)對其進(jìn)行排序。折半查找類型為 SeqList 類型。 typedef NodeType SeqList【MaxSize】；折半查找又叫二分查找，效率較高，但折半查找要求被查找的表示順序表，它的基本思路是：設(shè) R【low.high】

6、是當(dāng)前的查找區(qū)間，首先確定該區(qū)間的中 點位置mid= L (low+high ) /2，然后將待查的 k值與R【mid】.key。 如果中點值的值是 k,返回該元素的邏輯符號； 如果中點值k，則中點值之后的數(shù)都大于k，所以k值在該表的左邊，所以確定一個新的查找區(qū)間； 如果中點值k，則中點值之后的數(shù)都小于k, k值在該表的右邊，再在 依次循環(huán)。索引查找：/索引存儲結(jié)構(gòu)是在存儲數(shù)據(jù)的同時還建立附加的索引表，索引表包括關(guān)鍵字和地址。索引表的數(shù)據(jù)類型 KeyType key、int link ，link 代表對應(yīng) 塊的起始下標(biāo)。typedef IdxType IDXMaxSize /索引表的類型分塊查

7、找又稱索引順序查找，它的性能介于順序查找和折半查找之間的一種算法，它的分塊的思想是： 將表均分成b塊，前b-1塊中的關(guān)鍵字個數(shù)為 s=廠n/b n； 每一塊的關(guān)鍵字不一定有序，但前一塊中的最大關(guān)鍵字必須小于后一塊中的最小關(guān)鍵字； 取各塊中最大的關(guān)鍵字及該塊在R中的起始位置。注：索引表是一個遞增有序表分塊查找的基本思路是： 首先查找索引表，因為索引表是有序表，所以可以采用折半查找或者 順序查找，來確定待查元素在哪一塊； 再已確定的塊中進(jìn)行順序查找（因為塊內(nèi)元素?zé)o序，所以只能用順序 查找）列：設(shè)有一個線性表采用順序存儲，有20個元素，將其分成 4 （b=4）部分，每部分有5個元素（s=5）,該索引

8、表的存儲結(jié)構(gòu)如下圖所示：I08114I2639014410r>>53452210666341585718Li nkKey81993110401138125413661446157116781780188519100在如圖所示的存儲結(jié)構(gòu)中， 查找關(guān)鍵字k=80時，首先將k和索引表中個關(guān)鍵字比較， 直到找到大于等于 k的值，因此若關(guān)鍵字 k=80存在則必定在第四塊中，由IDX3ink找到起始地址15,從該地址開始在 R【1519】中進(jìn)行查找，直到找到關(guān)R【8 .key=k為止，如果查找不成功說明不存在關(guān)鍵字k=80。二叉樹查找：線性表可以有三種查找法，其中折半查找的效率最高，但是折半查

9、找要求元素 時順序表，而且不能用鏈?zhǔn)酱鎯Y(jié)構(gòu)，因此有表的插入或刪除操作時，需要移動大 量元素，這時候二叉樹查找的優(yōu)勢就體現(xiàn)出來了。即動態(tài)查找時就需要用到鏈?zhǔn)酱?儲結(jié)構(gòu)。二叉排序樹（BST又稱二叉查找樹，其定義為：二叉排序樹或者是空樹，或者是滿 足如下性質(zhì)的二叉樹： 若它的左孩子非空，則左子樹上的所有元素的值均小于根元素的值； 若它的右孩子非空，則左子樹上的所有元素的值均大于根元素的值； 左右子樹本身是一顆二叉樹。重要性質(zhì)：中序遍歷二叉排序樹所得到中序序列是以一個遞增有序序列。 二叉排序樹算法思想：它可以看做是一個有序表，所以在二叉樹上查找，和折半查 找類似，也是一個逐步縮小查找范圍的過程，運用

10、遞歸查找算法SearchBST()。哈希表查找：在用哈希表查找時先建立一個哈希表，哈希表主要用于快速查找，哈希表的查 找過程和建表過程類似。它的算法是： 設(shè)給定的值為k，根據(jù)建表時設(shè)定的散列函數(shù)h (k)計算哈希地址； 存儲的個數(shù)為 n,設(shè)置一個長度為M( M>r)的連續(xù)內(nèi)存單元，以線性表中的每個對象 Ki為自變量，通過 h(k)把Ki映射為內(nèi)存單元的地址，并把 該對象存儲字這個內(nèi)存單元中。哈希函數(shù)的構(gòu)造有直接定址法、除留余數(shù)法和數(shù)字分析法,常用的是除留余數(shù)法，它是用關(guān)鍵字 k除以某個不大于哈希表長度m的數(shù)p，將所得到的余數(shù)作為哈希地址。除留余數(shù)法的哈希函數(shù) h(k)：H( k)=K m

11、od P ( mod為取余運算，p<=m)2、程序模塊順序查找：int SeqSearch(SeqList R,int n,KeyType k) /*函數(shù)的返回值是整型，有三個參數(shù)分別是順序表 SeqList 、元素個數(shù) n 和需要查找的關(guān)鍵字 k*/int i=0;while (i<n && Ri.key!=k) /*從表頭開始找 */i+;if(i>=n) /* 未找到返回 0/*return 0;elsereturn i+1; /* 找到時返回邏輯符號 i+1*/折半查找 ：int BinSearch(SeqList R,int n,KeyType k)

12、/*函數(shù)的返回值是整型，有三個參數(shù)分別是順序表 SeqList 、元素個數(shù) n 和需要查找的關(guān)鍵字 */int low=0,high=n-1,mid;int count=0;while(low<=high) /*當(dāng)前區(qū)域存在元素時循環(huán) */count+; /*每循環(huán)一次 count+*/mid=(low+high)/2;if(Rmid.key=k)/*如果查找成功返回其邏輯序號 mid+1*/return mid+1;if(Rmid.key>k) /*繼續(xù)在R【lowmid-1】中查找*/elsehigh=mid-1;/*繼續(xù)在R【mid+1high】中查找*/return cou

13、nt+1; /*返回的是總的平均查找長度 */索引查找 ：int IdxSearch(IDX I,int b,SeqList R,int n,KeyType k) /*索引查找函數(shù)值返回的是整型，函數(shù)有五個參數(shù)，分別是索引表 I、分的塊數(shù)b、順序表R、 關(guān)鍵字個數(shù)和關(guān)鍵字 */int low=0,high=b-1,mid,i,count=0;int s=n/b; /*s為每塊的元素個數(shù)，應(yīng)為 n/b 的向上取整 */while(low<=high) /* 索引表中進(jìn)行折半查找、找到的位置為 high+1*/count+;mid=(low+high)/2;if(Imid.key>=k

14、) high=mid-1;elselow=mid+1;/* 應(yīng)在索引表的 high+1 中，再在對應(yīng)的線性表中進(jìn)行順序查找 */ i=Ihigh+1.link;while(i<=Ihigh+1.link+s-1&&Ri.key!=k)if(i<=Ihigh+1.link+s-1) /* 查找成功 */i+; count+;return count+1;int SearchBST(BSTNode *bt,KeyType k) /* 二叉排序樹查找函數(shù)的返回值是BSTNode類型，函數(shù)有兩個參數(shù)分別是二叉排序樹bt和關(guān)鍵字k*/ if(bt=NULL|bt->ke

15、y=k) /* 遞歸的終結(jié)條件 */return 1;if(k < bt->key) return SearchBST(bt->lchild ,k) + 1; /*在左子樹中的遞歸查找*/在右子樹中的遞歸查elsereturn SearchBST(bt->rchild ,k) + 1;/*找*/int SearchHT(HashTable ha,i nt p,KeyType k) /*哈希查找的返回值是整型有三個參數(shù)，分別是哈希表 ha、小于哈希表長度的最小素數(shù)p和關(guān)鍵字k*/int i=O,adr=O;int m=50;adr =k%p;采用線性探查法查while (

16、haadr.key!=NULLKEY && haadr.key!=k) /*找下一個地址*/i+;adr =(adr+1)%m; /*adr=( adr+1) mod m*/if(haadr.key=k)return i+1;/*查找成功 */elsereturn -1;/*查找失敗 */3、各模塊之間的調(diào)用關(guān)系以及算法設(shè)計函數(shù)的調(diào)用關(guān)系圖:Mai nV V V V VSeqSearchBin SearchIdxSearchSearchHTSearchBST*CreateHTInsertHTCreateBSTInsertBST在主函數(shù)中需要定義一個SeqList R的順序表；H

17、ashTable ha 哈希表；索引表IDXI。用srand函數(shù)(產(chǎn)生隨機數(shù))隨機產(chǎn)生50個1到100的整數(shù)并輸出，因為折半查找需要的是順序表，所以再對產(chǎn)生的50個隨機數(shù)再進(jìn)行排序。調(diào)用SeqSearch、Bin Search、IdxSearch、SearchHT、SearchBST( CreateBST )。依次進(jìn)行輸出。注意：每次都要給 sum重新賦值為零。三詳細(xì)設(shè)計#in clude<stdlib.h>#in clude<stdio.h>#in clude<time.h>#defi ne MAXL 100#defi ne MAXI 100#defi n

18、e NULLKEY -1#defi ne DELKEY -2 typedef int KeyType; typedef int In foType;typedef structKeyType key;int link;IdxType;typedef IdxType IDXMAXI;typedef structKeyType key;InfoType data;NodeType;typedef NodeType SeqListMAXL;typedef struct nodeKeyType key;InfoType data;struct node *lchild,*rchild;BSTNode;

19、typedef struct KeyType key;InfoType data;int count;HashTableMAXL;順序查找int SeqSearch(SeqList R,int n,KeyType k) / int i=0;while(i<n && Ri.key!=k)折半查找索引查找return i+1;int BinSearch(SeqList R,int n,KeyType k) /int low=0,high=n-1,mid,count=0;while(low<=high)count+;mid=(low+high)/2;if(Rmid.key

20、=k)return count+1;if(Rmid.key>k)high=mid-1;elselow=mid+1;return 0;int IdxSearch(IDX I,int b,SeqList R,int n,KeyType k) /int low=0,high=b-1,mid,i;int count=0;int s=n/b;while(low<=high)count+;mid=(low+high)/2;if(Imid.key>=k)high=mid-1;elselow=mid+1;i=Ihigh+1.link;while(i<=Ihigh+1.link+s-1&

21、amp;&Ri.key!=k)count+;i+;if(i<=Ihigh+1.link+s-1)return count+1;elsereturn 0;散列查找int SearchHT(HashTable ha,int p,KeyType k) /int i=0,adr=0;int m=50;adr =k%p;while (haadr.key!=NULLKEY && haadr.key!=k)i+;adr =(adr+1)%m;if(haadr.key=k)return i+1;elsereturn -1;哈希表的插入void InsertHT(HashTable

22、 ha,int &n,KeyType k,int p) /int i,adr;adr=k%p;if(haadr.key=NULLKEY|haadr.key=DELKEY)haadr.key=k;haadr.count=1;elsei=1;doadr=(adr+1)%p;while(haadr.key!=NULLKEY&&haadr.key!=DELKEY);haadr.key=k;haadr.count=i;n+;哈希表的創(chuàng)void CreateHT(HashTable ha,KeyType x,int n,int m,int p) /建int i,n1=0;for(i

23、=0;i<m;i+)hai.key=NULLKEY;hai.count=0;for(i=0;i<n;i+)InsertHT(ha,n1,xi,p);int InsertBST(BSTNode * &p,KeyType k) / 二叉排序樹的插入if(p=NULL)p=(BSTNode *)malloc(sizeof(BSTNode);p->key=k;二叉排序樹的創(chuàng)建二叉排序樹查找p->lchild=p->rchild=NULL;return 1;else if(k=p->key)return 0;else if(k<p->key)ret

24、urn InsertBST(p->lchild,k);elsereturn InsertBST(p->rchild,k);BSTNode *CreateBST(KeyType a,int n) /BSTNode *bt=NULL;int i=0;while (i<n)InsertBST(bt,ai);i+;return bt;int SearchBST(BSTNode *bt,KeyType k) /if(bt=NULL|bt->key=k) return 1;if(k < bt->key)return SearchBST(bt->lchild ,k)

25、 + 1;elsereturn SearchBST(bt->rchild ,k) + 1;void main()SeqList R;int i;int e;int a;int b;HashTable ha;int T50;IDX I;double j,k,m,n,sum=0;srand(int)time(0);for(i=0;i<50;i+)Ri.key=1+(int)(50.0*rand()/(RAND_MAX+1.0);printf("%dt",Ri.key);*n");for(i=0;i<50;i+) for(a=i+1;a<50;a

26、+) if(Ri.key>Ra.key) e=Ri.key;Ri.key=Ra.key;Ra.key=e;for(i=0;i<50;i+)Ti=Ri.key;for(i=0;i<50;i+)sum=sum+SeqSearch(R,50,Ri.key);printf(" 順序查找平均查找長度： %6.2fn",sum/50.0); sum=0;for(i=0;i<50;i+)sum=sum+BinSearch(R,50,Ri.key);printf(" 折半查找平均查找長度： %6.2fn",sum/50.0);sum=0;for(

27、i=0;i<5;i+)Ii.link=i*10;Ii.key=Ri*10+9.key;for(i=0;i<50;i+)sum=sum+IdxSearch(I,5,R,50,Ri.key);printf(" 索引查找平均查找長度： %6.2fn",sum/50.0);sum=0;CreateHT(ha,b,50,53,53);for(i=0;i<50;i+)sum=sum+SearchHT(ha,53,hai.key);printf(" 哈希表查找平均查找長度： %6.2fn",sum/50.0); sum=0;for(i=0;i<50;i+)sum=sum+SearchBST(CreateBST(b,50),bi);printf（" 二叉樹查找平均查找長度： %6.2fn",sum/50.0）;四 測試與分析輸出結(jié)果： 結(jié)果分析：由結(jié)果顯然可以看出，在線性表存儲結(jié)構(gòu)中折半查找的效率最高，順序查找的 效率最低，索引查找介于兩者之間