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

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告設(shè)計(jì)題目：查找專業(yè)：計(jì)算機(jī)科技 院系：計(jì)算機(jī)學(xué)院 姓名： XX XX 學(xué)號(hào)： XXXXXXXXX時(shí)間：2013年10月7日目錄一實(shí)踐目的與要求-2 -1.1實(shí)踐目的-2-1.2實(shí)踐要求-2-二 順序查找的分析、程序、及運(yùn)行結(jié)果 -2 -2.1系統(tǒng)簡(jiǎn)介-2-2.2設(shè)計(jì)思路-.2-2.3順序查找算法描述-.3-三 折半查找的分析、程序、及運(yùn)行結(jié)果 -4 -3.1系統(tǒng)簡(jiǎn)介-4-3.2設(shè)計(jì)思路-4-3.3折半查找算法描述-.5-四 二叉排序樹查找的分析、程序、及運(yùn)行結(jié)果 -5 -4.1系統(tǒng)簡(jiǎn)介-5 -4.2設(shè)計(jì)思路-5 -4.3二叉排序樹算法描述 -.6 -五 哈希查找的分析、程序

2、、及運(yùn)行結(jié)果 -8 -5.1系統(tǒng)簡(jiǎn)介-8 -5.2設(shè)計(jì)思路-9 -5.3哈希查找算法描述-.9-六 用戶手冊(cè) 錯(cuò)誤!未定義書簽。七 附件錯(cuò)誤!未定義書簽。八參考文獻(xiàn)-16 -一實(shí)踐目的與要求1.1實(shí)踐目的1) 掌握各種查找算法的思想及其使用條件；2) 掌握上機(jī)實(shí)現(xiàn)各種查找算法的基本思想；3) 熟練掌握二叉排序樹的構(gòu)造和查找方法；4) 掌握散列表存儲(chǔ)結(jié)構(gòu)的思想，能選擇合適的散列表函數(shù)，實(shí)現(xiàn)不同沖突處理方法的散列表的查找與建立；1.2實(shí)踐要求1) 掌握實(shí)踐是算法。2) 上機(jī)運(yùn)行程序，保存和打印運(yùn)行結(jié)果，并結(jié)合程序進(jìn)行分析。3) 注意理解折半查找的適用條件。4) 建立二叉排序樹、散列表是相同元素的處

3、理。5) 比較各種查找算法的各自特點(diǎn)，能夠結(jié)合實(shí)際情況選擇合適的查找方式。二 順序查找的分析、程序、及運(yùn)行結(jié)果2.1系統(tǒng)簡(jiǎn)介一次輸入順序表中的各個(gè)元素，然后進(jìn)行關(guān)鍵字查找。如果存在則返回待查元素的位置。2.2設(shè)計(jì)思路1)順序查找的思想對(duì)于給定的關(guān)鍵字K,從表中的一端開始，逐個(gè)進(jìn)行數(shù)據(jù)元素的關(guān)鍵字和給 定值的比較，若當(dāng)前掃描到的關(guān)鍵字與 K相等則查找成功；若掃描結(jié)束后，仍 未找到關(guān)鍵字等于K的節(jié)點(diǎn)，則查找失敗。建立一個(gè)順序表，數(shù)據(jù)元素從下標(biāo)為1的單元開始放入，下標(biāo)為0的元素起 哨兵作用，將待查的關(guān)鍵字存入下標(biāo)為0的單元，順序表從后向前查找，若直到 下標(biāo)為0時(shí)才找到關(guān)鍵字則說明查找失敗，若不到下標(biāo)

4、為0時(shí)就找到關(guān)鍵字，則 查找成功。2.3順序查找算法描述/*順序表結(jié)構(gòu)體定義*/typedef structkeytype keymaxsize;int len;stable;/*建立線性表*/stable create_s(stable r) _int i,j=0,k=1;printf("請(qǐng)輸入順序表元素，要為整形，用空格分開，-99為結(jié)束標(biāo)志：n");sca nf("%d",&i);while(i!=-99)j+；r.keyk=i;k+;scan f("%d",&i);r.le n=j;return r;/*順序表

5、查找*/int search_s(keytype k,stable *r)int j;j=r->le n;r->keyO=k;while(r->keyj!=k)j_；return j;三 折半查找的分析、程序、及運(yùn)行結(jié)果3.1系統(tǒng)簡(jiǎn)介一次輸入順序表中的各個(gè)元素，然后進(jìn)行關(guān)鍵字查找。如果存在則返回待 查元素的位置，否則顯示不存在。3.2設(shè)計(jì)思路1)折半查找的基本思想設(shè)查找表中的元素存放在數(shù)組 r中，數(shù)據(jù)元素的下標(biāo)范圍為low,high,查找 的關(guān)鍵字值為key，中間元素的下標(biāo)為 mid=(low+high)/2,(向下取整)，令key與 rmid的關(guān)鍵字比較：若key=rmid

6、.key,查找成功，下標(biāo)為 m的記錄即為所求，返回 mid。若key<rmid.key,所要找的記錄只能在左半部分記錄中，在對(duì)左半部分記錄 中，再對(duì)左半部分使用折半查找法繼續(xù)進(jìn)行查找，搜索區(qū)間縮小一半。若key>rmid.key,所要找的記錄只能在右半部分記錄中，在對(duì)右半部分記 錄中，再對(duì)右半部分使用折半查找法繼續(xù)進(jìn)行查找，搜索區(qū)間縮小一半。重復(fù)上述過程，直到找到查找表中某個(gè)數(shù)據(jù)元素的關(guān)鍵字的值等于給定的值 key說明查找成功，若出現(xiàn)low的值大于high的情況，說明查找不成功。建立一個(gè)有序表，數(shù)據(jù)元素從下標(biāo)為1的單元開始放入。實(shí)現(xiàn)查找算法時(shí)， 首先將low賦值為1，high等于最

7、后一個(gè)數(shù)據(jù)元素的下標(biāo)，然后將給定的關(guān)鍵字與查找區(qū)間low,high中間的數(shù)據(jù)元素的關(guān)鍵字比較，實(shí)現(xiàn)查找過程3.3折半查找算法描述/*順序表結(jié)構(gòu)體定義*/typedef structkeytype keymaxsize;int len;stable;/*折半查找*/int search_bi n(keytype k,stable *r)int low,high,mid;low=1;high=r->le n;while(low<=high)mid=(low+high)/2;if(k=r->keymid)return mid;else if(k<r->keymid)hi

8、gh=mid-1;else low=mid+1;return 0;四 二叉排序樹查找的分析、程序、及運(yùn)行結(jié)果4.1系統(tǒng)簡(jiǎn)介依次輸入關(guān)鍵字并建立二叉排序樹，實(shí)現(xiàn)二叉排序樹的插入和查找功能4.2設(shè)計(jì)思路1)二叉排序樹的基本思想二叉排序樹就是將原來的數(shù)據(jù)根據(jù)大小構(gòu)成一棵二叉樹， 二叉樹中的所有節(jié) 點(diǎn)數(shù)據(jù)滿足一定的大小關(guān)系，所有的左自述中的節(jié)點(diǎn)均比根節(jié)點(diǎn)小， 所有的右子 樹的節(jié)點(diǎn)均比根結(jié)點(diǎn)大。二叉排序樹查找是指按照二叉排序樹中結(jié)點(diǎn)的關(guān)系進(jìn)行查找，查找的關(guān)鍵字首先同根結(jié)點(diǎn)比較，如果相等則查找成功；如果比根結(jié)點(diǎn)小，則在左子樹中查找； 如果比根結(jié)點(diǎn)大，則在右子樹中查找。這種查找方法可以快速縮小查找范圍，大大

9、減小查找關(guān)鍵字的比較次數(shù)，從而提高查找效率。2)算法分析算法的關(guān)鍵過程實(shí)際上就是二叉排序樹的創(chuàng)建和查找兩個(gè)步驟。首先創(chuàng)建一個(gè)根結(jié)點(diǎn)，第二步就是將其他結(jié)點(diǎn)不斷插入到二叉樹中的合適位置。二叉排序樹 進(jìn)行結(jié)點(diǎn)插入時(shí)，首先要為結(jié)點(diǎn)尋找合適的位置插入。這個(gè)過程實(shí)際上就是關(guān)鍵 字不斷比較的過程。如果比根結(jié)點(diǎn)小，貝恠左子樹中插入；如果比根結(jié)點(diǎn)大，貝U 在右子樹中插入。然后在二叉排序樹中查找關(guān)鍵字的結(jié)點(diǎn)存在 。4.3二叉排序樹算法描述/*二叉排序樹結(jié)構(gòu)體定義*/typedef struct bsnodekeytype data;struct bsnode *lchild;struct bsnode *rchi

10、ld;bno de;bnode * bsp;bnode bst;/*為關(guān)鍵字key建立一個(gè)二叉排序樹結(jié)點(diǎn)*/bnode * createbst(keytype key)bnode *s;s=(b node *)malloc(sizeof(bst);s->data=key;s->lchild=s->rchild=NULL;return (s);/*將s指向的結(jié)點(diǎn)插入到t指向的二叉樹中*/ bnode * bst in sert(b node * t,b node * s)bnode * q,*p;if(t=NULL)return(s);elsep=t;q=NULL;while(

11、p)q=p;if(s->data=p->data)printf("這個(gè)數(shù)(%d 已存在",s->data); return (t);if(s->data<p->data)p=p->lchild;else p=p->rchild;if(s->data<q->data) q->lchild=s;else q->rchild=s;return (t);/*輸出二叉排序樹*/ void bstpri nt(b node * t)if(t)bstpri nt(t->lchild);prin tf(&q

12、uot;%d->",t->data);bstpri nt(t->rchild);/*在二叉排序樹中查找關(guān)鍵字*/void search(b node * t,keytype x)bnode * p;if(t=NULL)prin tf("error n");return;elsep=t;while(p)if(p->data=x)prin tf("search success!' n"); return;else if(x<p->data) p=p->lchild;else p=p->rchi

13、ld;if(!p)prin tf("%d not exist !n",x);五 哈希查找的分析、程序、及運(yùn)行結(jié)果5.1系統(tǒng)簡(jiǎn)介依次輸入關(guān)鍵字并建立哈希表，進(jìn)行關(guān)鍵字查找。如果存在則返回待查元素 的位置，否則顯示不存在。5.2設(shè)計(jì)思路1) 哈希表查找基本思想它是通過記錄中的關(guān)鍵字值key為自變量，通過，某一個(gè)特定的函數(shù)h計(jì)算 出函數(shù)值h(key)作為存儲(chǔ)地址，而查找時(shí)也用這個(gè)函數(shù)h進(jìn)行計(jì)算，獲得所要查 找關(guān)鍵字所在記錄的存儲(chǔ)位置。除留余數(shù)法是用關(guān)鍵字key除以某個(gè)正整數(shù)M，所得余數(shù)作為哈希地址的方 法。哈希函數(shù)h(key)=key%M，般M的取值為不大于表長(zhǎng)的質(zhì)數(shù)。用開放地址

14、法解決沖突，形成下一個(gè)地址的形式時(shí)Hi=(h(key)+di)%Mi=1,2,.k k(k<=m-1)H(key)為哈希函數(shù)；M為正整數(shù)；di為增量序列；m為表長(zhǎng)。線性探測(cè)再散列是將開放地址法中的增量序列di設(shè)定為從1開始一直到表長(zhǎng)減1的整數(shù)序列：1, 2，3，m-12) 算法分析算法的關(guān)鍵過程實(shí)際上就是Hash表的創(chuàng)建和查找兩個(gè)步驟。其中查找時(shí)利用除留余數(shù)法構(gòu)造哈希函數(shù) h，計(jì)算出函數(shù)值獲得所要查找的 關(guān)鍵字的存儲(chǔ)位置。若存儲(chǔ)位置對(duì)應(yīng)的數(shù)據(jù)元素的值和查找關(guān)鍵字相等，則查找 成功，否則，采用線性探測(cè)法從關(guān)鍵字的哈希地址開始向后掃描，直到找到與關(guān)鍵字相等的數(shù)據(jù)元素，查找成功；若查找到最后還

15、沒找到關(guān)鍵字，則查找失敗， 不存在與關(guān)鍵字相等的數(shù)據(jù)元素。5.3哈希查找算法描述/*哈希表結(jié)構(gòu)體定義*/typedef structkeytype key; int cn;hashtable;/*哈希函數(shù)*/int h(keytype key)return(key%m);/*哈希表查找函數(shù)*/int hashsearch(hashtable ht,keytype key)int d,i;i=0;d=h(key);=O;while(htd.key!=key)&&( htd.key!=0)&&(i<hm) i+;+;d=(d+i)%m;

16、if(i>=hm)printf("哈希表已滿");retur n (un sucess);return (d);/*插入函數(shù) 查找不成功就將key插入哈希表*/int hashi nsert(hashtable ht,keytype key)int d;d=hashsearch(ht,key);if(htd.key=0)htd.key=key;return(sucess);else prin tf(" un success!n");retur n(un sucess);/*建立哈希表函數(shù)*/void hashcreate(hashtable ht)

17、int i,n;keytype keyl;printf(”請(qǐng)輸入元素個(gè)數(shù)要小于表長(zhǎng)d:n",hm);sea nf("%d",&n);printf("請(qǐng)輸入元素關(guān)鍵字：n");for(i=0;i <n ;i+)sea nf("%d",&key1);hashi nsert(ht,key1);六用戶手冊(cè)1.主界面學(xué)號(hào)，_學(xué)進(jìn)人查找算法性能比較系統(tǒng)11忡討嚴(yán)5 退岀»»>»iiiSS功能二2順序查找>»»»請(qǐng)選檜功能:1算評(píng)弭料界料評(píng)耳科:

18、M |p 序查找科弭期XX評(píng)X科貳料請(qǐng)輸入順序表元素，要為整形，用空格分開，為結(jié)朿標(biāo)志:0 1 2 3 4 5 fc 7 S 9 12 23 34 45 56 67 78 89 -99耗時(shí)：52849.600000# 秒!舲薯議羌翳存在3. 折半查找»»»>請(qǐng)喪核功能臨am入jft序表元素，要為整形，用空格分開，-即為結(jié)束標(biāo)志.0 1 2 3 4 5 6 7 8 9 12 23 34 45 56 67 78 89 -99號(hào)時(shí)；50097.0000004®IM.W 81曰霧置毫89位00:素00字元盹鍵查9.關(guān)待購查中S：待叢:入序時(shí)4. 在二叉排序

19、樹中查找»>»»請(qǐng)鏈擇功能舊_二叉甫*序樹 中查找 mxxxx請(qǐng)輸入二叉排序樹中元素以杠結(jié)束1 2 3 4 5 6 7 8 9 12 23 34 45 56 67 78 89 0建立二叉排序樹是1->2->3->4->5->S->7->8->9->12->23->34->45->56->6?->?S->89-> 請(qǐng)輸入待查元素：4seal*匚h success?5. HASH查找>»»» 請(qǐng)選扌峯功能：4科満 Wiffii

20、科清犧|(flS H査枚黑轉(zhuǎn)甘科清愜酬旺建立喰橙裏：請(qǐng)輸犬兀臺(tái)個(gè)數(shù)要M、于克長(zhǎng)2 a:1B請(qǐng)輸入元素關(guān)鍵字；1 33 4 56 7 89 12 34 £5 £：234盤時(shí)：陌42 .00因000毫秒!；3-115c s jtesnui:67£ 擊 sh d衛(wèi)心豪哈藉美中不存6. 退出_歡彗查找彗性能比蟹學(xué)4.HAGH查技乩退岀»»»> 請(qǐng)鏈捧功能=5i*rtss 就ey hey to cont inuc七附件#include<stdio.h>#include<malloc.h>#define keytyp

21、e int#define maxsize 100#define hm 20#define m 19#define free 0#define sucess 1#define unsucess 0void main()system("cls");system("color 1f");printf(”i1n"printf("I®必做題：查找®| n"printf("1姓名：xxxxI n"printf("I學(xué)號(hào)：xxxxxxxxxI n"printf("11n

22、"stable a;bnode *t,*s; hashtable hthm; int i=0,k,n;double cl=clock(); keytype key;int flag=1; t=NULL; while(flag)printf("|一-1n");printf("|歡迎進(jìn)入查找算法性能比較系統(tǒng)| n");printf("| n");printf("|1.順序查找2.折半查找| n");printf("|3.在二叉排序樹中查找| n");printf("|4.HASH

23、查找5.退出| n");printf("1一-1n");prin tf(">>>> >>>n “)； printf(”請(qǐng)選擇功能：");scanf("%d",&n);switch(n)case 1:printf(" *printf("a=create_s(a); while(i!=-1)順序查找*n");n");printf("n輸入待查關(guān)鍵字：");scanf("%d",&i);k=se

24、arch_s(i, &a);if(i=-1) break;if(k=0)printf("順序表中待查元素不存在n");elseprintf("順序表中待查元素位置是：%d",k);printf("n 耗時(shí)：%f 毫秒！ n", (clock()-cl); printf("n");break;case 2:printf("printf("*折半查找*n");n");a=create_s(a);while(i!=-1)printf("n輸入待查關(guān)鍵字："

25、;);scanf("%d",&i);k=search_bin(i, &a);if(i=-1) break;if(k=0)printf(”順序表中待查元素不存在 n");elseprintf("順序表中待查元素位置是：%d",k);printf("n 耗時(shí)：%f 毫秒！ n", (clock()-cl); printf("n");break;case 3:printf("*在二叉排序樹中查找* n");printf("n");printf("請(qǐng)輸入二叉排序樹中元素以0結(jié)束n");scanf("%d",&key