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

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

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

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

4、進(jìn)行排序，需要進(jìn)行排序后再進(jìn)行輸入，N50;（2） 輸出形式；查找算法分析過程中，只要對(duì)查找算法稍作修改就可以利用平均查找長度的公式： ASL=PiCi（i從1到n）輸出各種查找算法的平均查找長度。注：平均查找長度=總的平均查找長度/N；（3） 程序所能達(dá)到的功能通過輸出幾種查找算法的ASL，我們很顯然能得在數(shù)據(jù)量較小時(shí)（Nk，則中點(diǎn)值之后的數(shù)都大于k，所以k值在該表的左邊，所以確定一個(gè)新的查找區(qū)間； 如果中點(diǎn)值n）的連續(xù)內(nèi)存單元，以線性表中的每個(gè)對(duì)象Ki為自變量，通過h（k）把Ki映射為內(nèi)存單元的地址，并把該對(duì)象存儲(chǔ)字這個(gè)內(nèi)存單元中。哈希函數(shù)的構(gòu)造有直接定址法、除留余數(shù)法和數(shù)字分析法，常用的

5、是除留余數(shù)法，它是用關(guān)鍵字k除以某個(gè)不大于哈希表長度m的數(shù)p，將所得到的余數(shù)作為哈希地址。除留余數(shù)法的哈希函數(shù)h（k）： H（k）=K mod P（mod為取余運(yùn)算，p=m）2、 程序模塊順序查找：int SeqSearch(SeqList R,int n,KeyType k) /*函數(shù)的返回值是整型，有三個(gè)參數(shù)分別是順序表SeqList、元素個(gè)數(shù)n和需要查找的關(guān)鍵字k*/int i=0;while (i=n) /*未找到返回0/*return 0;elsereturn i+1; /*找到時(shí)返回邏輯符號(hào)i+1*/折半查找：int BinSearch(SeqList R,int n,KeyTyp

6、e k)/*函數(shù)的返回值是整型，有三個(gè)參數(shù)分別是順序表SeqList、元素個(gè)數(shù)n和需要查找的關(guān)鍵字*/int low=0,high=n-1,mid;int count=0;while(lowk) /*繼續(xù)在R【lowmid-1】中查找*/high=mid-1;else /* 繼續(xù)在R【mid+1high】中查找*/return count+1; /*返回的是總的平均查找長度*/索引查找：int IdxSearch(IDX I,int b,SeqList R,int n,KeyType k) /*索引查找函數(shù)值返回的是整型，函數(shù)有五個(gè)參數(shù)，分別是索引表I、分的塊數(shù)b、順序表R、關(guān)鍵字個(gè)數(shù)和關(guān)鍵字

7、*/int low=0,high=b-1,mid,i,count=0;int s=n/b; /*s為每塊的元素個(gè)數(shù)，應(yīng)為n/b的向上取整*/while(low=k)high=mid-1;elselow=mid+1;/* 應(yīng)在索引表的high+1中，再在對(duì)應(yīng)的線性表中進(jìn)行順序查找*/i=Ihigh+1.link;while(i=Ihigh+1.link+s-1&Ri.key!=k)if(ikey=k) /*遞歸的終結(jié)條件*/return 1;if(k key) return SearchBST(bt-lchild ,k) + 1; /*在左子樹中的遞歸查找*/elsereturn SearchB

8、ST(bt-rchild ,k) + 1; /*在右子樹中的遞歸查找*/int SearchHT(HashTable ha,int p,KeyType k) /*哈希查找的返回值是整型有三個(gè)參數(shù)，分別是哈希表ha、小于哈希表長度的最小素?cái)?shù)p和關(guān)鍵字k*/ int i=0,adr=0;int m=50;adr =k%p;while (haadr.key!=NULLKEY & haadr.key!=k) /*采用線性探查法查找下一個(gè)地址*/i+; adr =(adr+1)%m; /*adr=（adr+1）mod m*/if(haadr.key=k)return i+1; /*查找成功*/elser

9、eturn -1; /*查找失敗*/3、 各模塊之間的調(diào)用關(guān)系以及算法設(shè)計(jì)函數(shù)的調(diào)用關(guān)系圖：MainSeqSearchBinSearchIdxSearchSearchHTSearchBSTCreateHTInsertHTCreateBSTInsertBST在主函數(shù)中需要定義一個(gè)SeqList R的順序表；HashTable ha 哈希表；索引表IDX I。用srand函數(shù)（產(chǎn)生隨機(jī)數(shù)）隨機(jī)產(chǎn)生50個(gè)1到100的整數(shù)并輸出，因?yàn)檎郯氩檎倚枰氖琼樞虮?，所以再?duì)產(chǎn)生的50個(gè)隨機(jī)數(shù)再進(jìn)行排序。調(diào)用SeqSearch、BinSearch、IdxSearch、SearchHT、SearchBST（Cre

10、ateBST）。依次進(jìn)行輸出。注意：每次都要給sum重新賦值為零。三 詳細(xì)設(shè)計(jì)#include#include#include#define MAXL 100#define MAXI 100#define NULLKEY -1#define DELKEY -2typedef int KeyType;typedef int InfoType;typedef structKeyType key;int link;IdxType;typedef IdxType IDXMAXI; typedef structKeyType key;InfoType data;NodeType;typedef Node

11、Type SeqListMAXL;typedef struct nodeKeyType key;InfoType data;struct node *lchild,*rchild;BSTNode;typedef structKeyType key;InfoType data;int count;HashTableMAXL;int SeqSearch(SeqList R,int n,KeyType k) /順序查找int i=0;while(in & Ri.key!=k)i+;return i+1;int BinSearch(SeqList R,int n,KeyType k) /折半查找int

12、 low=0,high=n-1,mid,count=0;while(lowk)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=k)high=mid-1;elselow=mid+1;i=Ihigh+1.link;while(i=Ihigh+1.link+s-1&Ri.key!=k)count+;i+;if(i=Ihigh+1.link+s-1)ret

13、urn count+1;else return 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 ha,int &n,KeyType k,int p) /哈希表的插入int i,adr;adr=k%p;if(haadr.key=NULL

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

15、;return 1;else if(k=p-key)return 0;else if(kkey)return InsertBST(p-lchild,k);elsereturn InsertBST(p-rchild,k);BSTNode *CreateBST(KeyType a,int n) /二叉排序樹的創(chuàng)建BSTNode *bt=NULL;int i=0;while (ikey=k)return 1;if(k key) return SearchBST(bt-lchild ,k) + 1;elsereturn SearchBST(bt-rchild ,k) + 1;void main()Se

16、qList 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;i50;i+)Ri.key=1+(int)(50.0*rand()/(RAND_MAX+1.0);printf(%dt,Ri.key);printf(*n);for(i=0;i50;i+) for(a=i+1;aRa.key)e=Ri.key;Ri.key=Ra.key;Ra.key=e;for(i=0;i50;i+)Ti=Ri.key;for(i=0;i50;i+)sum=sum+S

17、eqSearch(R,50,Ri.key);printf(順序查找平均查找長度：%6.2fn,sum/50.0);sum=0;for(i=0;i50;i+)sum=sum+BinSearch(R,50,Ri.key);printf(折半查找平均查找長度：%6.2fn,sum/50.0);sum=0;for(i=0;i5;i+)Ii.link=i*10;Ii.key=Ri*10+9.key;for(i=0;i50;i+)sum=sum+IdxSearch(I,5,R,50,Ri.key);printf(索引查找平均查找長度：%6.2fn,sum/50.0);sum=0;CreateHT(ha,b

18、,50,53,53);for(i=0;i50;i+)sum=sum+SearchHT(ha,53,hai.key);printf(哈希表查找平均查找長度：%6.2fn,sum/50.0);sum=0;for(i=0;i50;i+)sum=sum+SearchBST(CreateBST(b,50),bi);printf(二叉樹查找平均查找長度：%6.2fn,sum/50.0);四 測(cè)試與分析輸出結(jié)果：結(jié)果分析： 由結(jié)果顯然可以看出，在線性表存儲(chǔ)結(jié)構(gòu)中折半查找的效率最高，順序查找的效率最低，索引查找介于兩者之間。在順序表存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)、索引表存儲(chǔ)結(jié)構(gòu)和哈希表存儲(chǔ)結(jié)構(gòu)中效率最高的是哈希表。還有一種在動(dòng)態(tài)查找時(shí)很高效的一種存儲(chǔ)結(jié)構(gòu)樹表。幾種查找的效率依次是：五 總結(jié)數(shù)據(jù)結(jié)構(gòu)總結(jié)：為期一周的數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)已經(jīng)過去了，在這次課程設(shè)計(jì)中我學(xué)習(xí)到了很多知識(shí)，對(duì)編程也有了一定的認(rèn)識(shí)。譬如在結(jié)構(gòu)體的使用在大一下學(xué)期的C語言課程中我學(xué)的不是很清楚，很多問題都沒有搞懂，但在數(shù)據(jù)結(jié)構(gòu)這門課程中我對(duì)結(jié)構(gòu)體這一部分有了新的認(rèn)識(shí)；此外還有函數(shù)的調(diào)用以及函數(shù)的參數(shù)這方面我也彌補(bǔ)了在大一上學(xué)期拉下的課程。當(dāng)然這學(xué)期的數(shù)據(jù)結(jié)構(gòu)主要討論的是算法問題，