版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
1、<p><b> 數 據 結 構</b></p><p> 課 程 設 計 說 明 書</p><p> 2011年12月20日</p><p> 設計任務概述(包括系統(tǒng)總體框圖及功能描述)</p><p><b> 系統(tǒng)總體框圖</b></p><p>
2、<b> 問題描述</b></p><p> 散列法中,散列函數構造方法多種多樣,同時對于同一散列函數解決沖突的方法也可以不同。兩者是影響查詢算法性能的關鍵因素。對于幾種典型的散列函數構造方法,做實驗觀察,不同的解決沖突方法對查詢性能的影響。</p><p><b> 概要設計</b></p><p> 散列又稱哈
3、?;螂s湊。散列法(Hashing)在表項的存儲位置與它的關鍵碼之間建立一個確定的對應函數關系Hash(),以使每個關鍵碼與結構中的唯一存儲位置相對應,該關系可用下式表示:</p><p> Address=Hash(Record.key)</p><p> 相應的表稱為哈希表,這種方法的基本思想是:首先在元素的關鍵字k和元素的存儲位置p之間建立一個對應關系H,使得p=H(k),H稱為哈
4、希函數。創(chuàng)建哈希表時,把關鍵字為k的元素直接存入地址為H(k)的單元;以后當查找關鍵字為k的元素時,再利用哈希函數計算出該元素的存儲位置p=H(k),從而達到按關鍵字直接存取元素的目的。 </p><p> 哈希函數是一個映象,哈希函數的設定靈活,只要使得任何關鍵字所得的哈希函數值都落在表長范圍之內即可。 </p><p> 當關鍵字集合很大時,關鍵字值不同的元素可能會映
5、象到哈希表的同一地址上,即 k1≠k2,但H(k1)=H(k2),這種現象稱為沖突,此時稱k1和k2為同義詞。實際中,沖突是不可避免的,只能通過改進哈希函數的性能來減少沖突。</p><p> 綜上所述,哈希法主要包括以下兩方面的內容。</p><p> (1)如何構造哈希函數;</p><p> (2) 如何處理沖突。</p><p>
6、; 2. 本設計所采用的數據結構(如:鏈表、棧、樹、圖等)</p><p><b> 一、散列函數</b></p><p> 通常,構造散列函數應該注意的幾個問題包括:首先,散列函數的定義域必須包括需要存儲的全部關鍵碼,而如果散列表允許有m個地址,其值域必須在1~m-1之間;其次,散列函數計算出來的地址應能均勻分布在整個地址空間中;再次,散列函數應當是盡量簡單的
7、。</p><p><b> 1.直接定址法</b></p><p> 直接定址法藍顏元素關鍵碼的某個線性函數值作為該元素的散列地址(散列地址,即元素最終在字典中的存儲位置)。如下面的函數式:</p><p> Hash(key)=a×key+b</p><p> 式中,a,b為常數。采用該種方法,當向
8、字典中加入某一新元素時算法自動調用此函數,以確定該元素最終的存儲位置。若某元素關鍵碼key為1,上式中,a=2,b=3則該元素最終會存儲在字典第5個位置中。</p><p> 直接定址法的優(yōu)點是實現方法簡單,算法時間復雜度較小,而且不會產生沖突。但是,直接定址法要求散列地址空間的大小與關鍵碼集合的大小一致,而這種要求是苛刻的,一般很難實現。例如當關鍵碼的范圍為1~1000000時,元素散列地址的個數也要達到10
9、00000。這么大的散列地址是不合實際的。</p><p><b> 2.除留余數法</b></p><p> 設散列表中允許的地址數為m,取一個不大于m,但最接近或等于m的質數k,或選取一個不含有小于20的質因子的合數作為除數。利用下面的式子計算元素的散列地址的方法稱為除留余數法。</p><p> Hash(key)=key%k,k≤
10、m</p><p> 其中,“%”是整數除余法取余的運算,要求這時的質數不是接近2的冪。例如,當元素的關鍵碼key為2008,散列地址總數為50,這時取k=47,則散列地址為Hash(2008)=2008%47=34,所以運算將存儲在字典第47個位置中。</p><p> 除留余數法將有效縮減散列地址空間的大小,例如上例散列地址空間中只有50個有效的散列地址。除留余數法的缺點是極易發(fā)生
11、沖突,如關鍵碼為1914的元素經過上述教例函數計算后也將獲得散列地址34。此時出現的兩個不同元素爭用同一存儲地址的情況就稱為沖突。</p><p><b> 3.平方取中法</b></p><p> 平方取中法是一種常用的實現散列函數的方法。</p><p> 平方取中法是一種先放大再集合的構造方法,這種構造模式先通過求關鍵字的平方值擴大
12、相近數的差別,然后根據表長度取中間的幾位數作為散列函數值,這種取中間數的方法是一種類隨機方案,因此也可以認為平方取中法是一種產生偽隨機數的方法。因為一個乘積的中間幾位數和乘數的每一位都相關,所以有此產生的散列地址較為均勻。</p><p> 利用平方取中法實現散列函數的過程:首先,利用一定的編碼規(guī)則把元素的關鍵碼轉換成標識符。然后,求出標識符的內碼表示并計算內碼的平方值。最后,取內碼平方數的中間x位作為元素最終
13、的散列地址。簡而言之,即先計算構成關鍵碼表示符的內碼平方,然后按照散列表的大小取中間的若干位作為散列地址。</p><p> 在平方取中法中,地址空間內散列地址的數目一般為2的k次冪,并在計算出內碼平方的平方后,根據k的大小決定最終散列地址的位數。例如某個地址空間中散列地址的個數為128,則最終取內碼平方中間7位作為元素最終的散列地址。</p><p><b> 4.乘余取整
14、法</b></p><p> 乘余取整法利用下面的式子計算元素的散列地址。</p><p> Hash(key)=[Z×(a×key%1)]</p><p> 其中,a為一個常數且0<a<1,Z為一個整數。式a×key%1表示a×key取小數部分,即a×key%1= a×key
15、-[ a×key] 。例如,當元素關鍵碼為2008, 小數a為0.6180339,整數Z為10000,則散列地址計算為Hash(2008)=[10000×(0.6180339×2008%1)]=120。</p><p> 乘余取整法不但會縮減散列地址空間的大小,還能極大減小沖突情況的發(fā)生幾率。Knuth對常數a的取法做了仔細的研究,發(fā)現雖然a取任何值都可以,但一般取黃金分割數0.6
16、180339比較好。</p><p><b> 5.折疊法</b></p><p> 折疊法的工作方式很有趣,此方法把關鍵嗎從左至右劃分為位數相等的幾部分,每一部分的位數與散列地址數相同。當關鍵碼位數不能被散列地址位數整除時,最后一部分可取得短些。</p><p> 折疊法有兩種,即位移法和分界法。 其中,位移法所采取的具體方式是把各部分
17、的最后一位對齊相加。分界法所采用的具體方式是各部分不折斷,而沿各部分的分界來回折疊,然后對齊相加,并將相加的結果當做散列地址。折疊法適用于關鍵碼位數很多,且每一位上數字分布比較均勻的情況。下面通過實例演示這兩種方法的工作方式。</p><p> 設關鍵碼key=987654321,散列地址為4位。位移法和分界法計算散列地址的算式如圖所示。</p><p><b> 9876&
18、lt;/b></p><p> 5432 2345</p><p> + 1 + 1</p><p> 15309 12222</p><p> 移位法
19、 分界法</p><p> 由式可見,位移法計算結果為15309,由于散列地址為4位,所以舍去最高位數字1,元素最終的散列地址為5309。分界法結算結果為12222,同樣舍去最高位數字1,元素最終的散列地址為2222。</p><p> 二、散列沖突解決方法</p><p> 在構造散列函數的過程中,不可避免地會出現沖突的情況。所謂處理沖突,就是在
20、有沖突發(fā)生時,為產生沖突的關鍵字找到另一個地址存放該關鍵字。在解決沖突的過程中,可能會得到一系列散列地址hi(i=1,2,…,n),也就是發(fā)生第一沖突時,經過處理后得到第一新地址記作h1,如果h1仍然會沖突,則處理后得到第二個地址h2,依此類推,直到hn不產生沖突,將hn作為關鍵字的儲存地址。</p><p> 處理沖突的方法比較常用的主要有開放定址法、再散列法和鏈地址法。</p><p&g
21、t;<b> 開放定址法</b></p><p> 開放定址法是解決沖突比較常用的方法。開放定址法就是利用散列表中的空地址存儲產生沖突的關鍵字。當沖突發(fā)生時,按照下列公式處理沖突:</p><p> hi=(h(key)+di)%m,其中i=1,2,…,m-1</p><p> 其中,h(key)為散列函數,m為散列表長,di為地址增量
22、。地址增量di可以以下三種方法獲得:</p><p> 線性探測再散列:當沖突發(fā)生時,地址增量di依次取1,2,…,m-1自然數列,即di=1,2,…,m-1。</p><p> 二次探測再散列:在沖突發(fā)生時,地址增量di依次取自然數的平方,即di=12,—12,22,—22,…,k2,—k2。</p><p> 偽隨機數再散列:在沖突發(fā)生時,地址增量di依次
23、取隨機數序列。</p><p> 例如,在長度為14的散列表中,在將關鍵字183,123,230,91存放在散列表中的情況如圖所示。</p><p><b> Hash地址</b></p><p> 0 1 2 3 4 5 6 7 8 9 10 11 12 13<
24、;/p><p> 散列表沖突發(fā)生前示意圖</p><p> 當要插入關鍵字149時,有散列函數h(149)=149%13=6,而單元6已經存在關鍵字,產生沖突,利用線性探測再散列法解決沖突,即h1=(6+1)%14=7,將149儲存在單元7中,如圖所示。</p><p><b> Hash地址</b></p><p>
25、 0 1 2 3 4 5 6 7 8 9 10 11 12 13</p><p> 插入關鍵字149后的示意圖</p><p> 當要插入關鍵字227時,由散列函數h(227)=227%13=6,而單元6已經存在關鍵字,產生沖突,利用線性探測再散列法解決沖突,即h1=(6+1)%14=7,仍然沖突,繼續(xù)利用線性
26、探測法,即h2=(6+2)%14=8,單元8空閑,因此將227存儲在單元8中,如圖所示。</p><p><b> Hash地址</b></p><p> 0 1 2 3 4 5 6 7 8 9 10 11 12 13</p><p> 插入關鍵字227后的示意圖&
27、lt;/p><p> 當然,在沖突發(fā)生時,也可以利用二次探測再散列解決沖突。在圖11.33中,如果要插入關鍵字227,因為產生沖突,利用二次探測再散列法解決沖突,即h1=(6+1)%14=7,再次產生沖突時,有h2=(6—1)%14=5,將227儲存在單元5中,如圖所示。</p><p><b> Hash地址</b></p><p> 0
28、 1 2 3 4 5 6 7 8 9 10 11 12 13</p><p> 利用二次探測再散列解決沖突示意圖</p><p><b> 再散列法</b></p><p> 再散列法就是在沖突發(fā)生時,利用另外一個散列函數再次求散列函數的地址,直到沖突不再發(fā)生為止,即
29、</p><p> hi=rehash(key),i=1,2…,n</p><p> 其中,rehash表示不同的散列函數。這種再散列法一般不容易再次發(fā)生沖突,但是需要事先構造多個散列函數,這是一件不太容易的也不現實的事情。</p><p><b> 鏈地址法</b></p><p> 數組的特點是:尋址容易,插
30、入和刪除困難;而鏈表的特點是:尋址困難,插入和刪除容易。那么我們能不能綜合兩者的特性,做出一種尋址容易,插入刪除也容易的數據結構?答案是肯定的,這就是我們要提起的哈希表,哈希表有多種不同的實現方法,我接下來解釋的是最常用的一種方法——鏈地址法,我們可以理解為“鏈表的數組”,如圖:</p><p> 左邊很明顯是個數組,數組的每個成員包括一個指針,指向一個鏈表的頭,當然這個鏈表可能為空,也可能元素很多。我們根據元
31、素的一些特征把元素分配到不同的鏈表中去,也是根據這些特征,找到正確的鏈表,再從鏈表中找出這個元素。三、 哈希法性能分析</p><p> 由于沖突的存在,哈希法仍需進行關鍵字比較,因此仍需用平均查找長度來評價哈希法的查找性能。哈希法中影響關鍵字比較次數的因素有三個:哈希函數、處理沖突的方法以及哈希表的裝填因子。哈希表的裝填因子α的定義如下: </p><p><b> ■線
32、性探測再散列</b></p><p><b> 查找成功時 </b></p><p><b> 查找失敗時 </b></p><p> ■偽隨機探測再散列、 二次探測 </p><p><b> 查找成功時 </b></p><p>
33、<b> 查找失敗時 </b></p><p><b> ■鏈址法</b></p><p><b> 查找成功時</b></p><p><b> 查找失敗時</b></p><p> 從以上討論可知:哈希表的平均查找長度是裝填因子α的函數,而與
34、待散列元素數目n無關。因此,無論元素數目n有多大,都能通過調整α,使哈希表的平均查找長度較小。 </p><p> 3. 功能模塊詳細設計</p><p> 3.1 詳細設計思想</p><p> (1)程序中結構體的定義</p><p> typedef struct</p><p><b> {
35、</b></p><p><b> int key;</b></p><p><b> int si;</b></p><p> }HashTable1;</p><p> typedef struct node</p><p><b> {&
36、lt;/b></p><p><b> int key;</b></p><p><b> int si;</b></p><p> struct node *next;</p><p><b> }Node;</b></p><p>
37、typedef struct</p><p><b> {</b></p><p> Node *link;</p><p> }HashTable2;</p><p> typedef struct </p><p><b> {</b></p>&
38、lt;p> int * elem[HashSize];</p><p> int count;</p><p><b> int size;</b></p><p> }HashTable3;</p><p><b> (2) 主函數模塊</b></p><p&g
39、t; void main()</p><p><b> {</b></p><p><b> int data;</b></p><p> HashTable1 hash1[HashSize];</p><p> HashTable2 * hash2[HashSize];</p>
40、;<p> HashTable3 * ha;</p><p> ha=(HashTable3 *)malloc(sizeof(HashTable3));</p><p> for(int i=0;i<HashSize;i++)</p><p> ha->elem[i]=NULL;</p><p> ha-&
41、gt;count=0;</p><p> ha->size=HashSize;</p><p> int a[MaxSize];</p><p><b> while(1)</b></p><p><b> {</b></p><p> printf(&quo
42、t;\n ┏━━━━━━━━━━━━━━━┓ "); </p><p> printf("\n ┃ 歡迎使用本系統(tǒng) ┃ "); </p><p> printf("\n ┏〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓"); </p><p>
43、; printf("\n ┃★ ★ ★ ★ ★ ★散列法的實驗研究★ ★ ★ ★ ★ ★");</p><p> printf("\n ┃ 【1】. 添加數據信息 【2】 數據的輸出 ┃");</p><p> printf("\n ┃ 【3】. 建立哈希表(線性再散列)
44、 ");</p><p> printf("\n ┃ 【4】. 建立哈希表(二次探測再散列) ");</p><p> printf("\n ┃ 【5】. 建立哈希表(鏈地址法) ");</p><p> printf("\n
45、 ┃ 【6】. 線性再散列法查找 ┃");</p><p> printf("\n ┃ 【7】. 二次探測再散列法查找 ┃");</p><p> printf("\n ┃ 【8】. 鏈地址法查找
46、┃");</p><p> printf("\n ┃ 【0】. 退出程序 ┃");</p><p> printf("\n ┗〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓");</p><p> printf("\n")
47、;</p><p> printf("\n");</p><p> printf("請輸入一個任務選項>>>");</p><p><b> int x;</b></p><p> scanf("%d",&x);</p&g
48、t;<p><b> switch(x)</b></p><p><b> {</b></p><p><b> case 1:</b></p><p> GetIn (a);break;</p><p><b> case 2:</b&
49、gt;</p><p> GetOut(a);break;</p><p><b> case 3:</b></p><p> CreateHashTable1(hash1,a,num);break;</p><p><b> case 4:</b></p><p>
50、 CreateHash3(ha,a,num);break;</p><p><b> case 5:</b></p><p> CreateHashTable2(hash2,a,num);break;</p><p><b> case 6:</b></p><p> printf(&qu
51、ot;請輸入你查找的數據:");</p><p> scanf("%d",&data);</p><p> SearchHash1(hash1,data);break;</p><p><b> case 7:</b></p><p> printf("請輸入你查找
52、的數據:");</p><p> scanf("%d",&data);</p><p> SearchHash3(ha,data);break;</p><p><b> case 8:</b></p><p> printf("請輸入你查找的數據:");
53、</p><p> scanf("%d",&data);</p><p> SearchHash2(hash2,data,num);break;</p><p> case 0:exit(-1);</p><p><b> }</b></p><p><b
54、> } </b></p><p><b> }</b></p><p><b> 3.2 核心代碼</b></p><p> #include<stdio.h></p><p> #include<stdlib.h></p><
55、p> #define HashSize 53</p><p> #define MaxSize 20</p><p> typedef struct</p><p><b> {</b></p><p><b> int key;</b></p><p>&l
56、t;b> int si;</b></p><p> }HashTable1;</p><p> void CreateHashTable1(HashTable1 *H,int *a,int num)//哈希表線性探測在散列;</p><p><b> {</b></p><p> int i,
57、d,cnt;</p><p> for(i=0;i<HashSize;i++)</p><p><b> {</b></p><p> H[i].key=0;</p><p> H[i].si=0;</p><p><b> }</b></p>
58、<p> for(i=0;i<num;i++)</p><p><b> {</b></p><p><b> cnt=1;</b></p><p> d=a[i]%HashSize;</p><p> if(H[d].key==0)</p><p>
59、;<b> {</b></p><p> H[d].key=a[i];</p><p> H[d].si=cnt;</p><p><b> }</b></p><p><b> else</b></p><p><b> {<
60、;/b></p><p><b> do</b></p><p><b> {</b></p><p> d=(d+1)%HashSize;</p><p><b> cnt++;</b></p><p> }while(H[d].key
61、!=0);</p><p> H[d].key=a[i];</p><p> H[d].si=cnt;</p><p><b> }</b></p><p><b> }</b></p><p> printf("\n線性再探索哈希表已建成!")
62、;</p><p><b> }</b></p><p> void SearchHash1(HashTable1 *h,int data)</p><p><b> {</b></p><p><b> int d;</b></p><p>
63、 d=data%HashSize;</p><p> if(h[d].key==data)</p><p> printf("數字%d的探查次數為:%d\n",h[d].key,h[d].si);</p><p><b> else</b></p><p><b> {</b&
64、gt;</p><p><b> do</b></p><p> d=(d+1)%HashSize;</p><p> while(h[d].key!=data && d<HashSize);</p><p> if(d<HashSize)</p><p>
65、printf("數字%d的探查次數為:%d\n",h[d].key,h[d].si);</p><p><b> else</b></p><p> printf("沒有查找到你所輸入的數\n");</p><p><b> }</b></p><p>
66、<b> }</b></p><p> typedef struct node</p><p><b> {</b></p><p><b> int key;</b></p><p><b> int si;</b></p>&l
67、t;p> struct node *next;</p><p><b> }Node;</b></p><p> typedef struct</p><p><b> {</b></p><p> Node *link;</p><p> }HashTab
68、le2;</p><p> void CreateHashTable2(HashTable2 *ht[],int *a,int num)//哈希表鏈地址;</p><p><b> {</b></p><p> int i,d,cnt;</p><p> Node *s,*q;</p><p&
69、gt; for(i=0;i<num; i++)</p><p><b> {</b></p><p> ht[i]=(HashTable2 *)malloc(sizeof(HashTable2));</p><p> ht[i]->link=NULL;</p><p><b> }<
70、/b></p><p> for(i=0;i<num;i++)</p><p><b> {</b></p><p><b> cnt=1;</b></p><p> s=(Node *)malloc(sizeof(Node));</p><p> s-
71、>key=a[i];s->next=NULL;</p><p> d=a[i]%num;</p><p> if(ht[d]->link==NULL)</p><p><b> {</b></p><p> ht[d]->link=s;</p><p> s-&g
72、t;si=cnt;</p><p><b> }</b></p><p><b> else</b></p><p><b> {</b></p><p> q=ht[d]->link;</p><p> while(q->next
73、!=NULL)</p><p><b> {</b></p><p> q=q->next;cnt++;</p><p><b> }</b></p><p><b> cnt++;</b></p><p> s->si=cnt;&
74、lt;/p><p> q->next=s;</p><p><b> }</b></p><p><b> }</b></p><p><b> }</b></p><p> void SearchHash2(HashTable2 * h[]
75、,int data,int num)</p><p><b> {</b></p><p><b> int d;</b></p><p><b> Node *q;</b></p><p> d=data%num;</p><p> q=h[
76、d]->link;</p><p> while(q->key!=data && q->next!=NULL)</p><p> q=q->next;</p><p> if(q->next!=NULL)</p><p> printf("數字%d的查找次數為:%d\n"
77、;,q->key,q->next);</p><p><b> else</b></p><p> printf("沒有找到你要查找的那個數\n");</p><p><b> }</b></p><p> typedef struct </p>
78、<p><b> {</b></p><p> int * elem[HashSize];</p><p> int count;</p><p><b> int size;</b></p><p> }HashTable3;</p><p> in
79、t Collision(int p,int &c)//二次探測再散列法解決沖突</p><p><b> {</b></p><p><b> int i,q;</b></p><p><b> i=c/2+1;</b></p><p> while(i<
80、HashSize)</p><p><b> {</b></p><p> if(c%2==0)</p><p><b> {</b></p><p><b> c++;</b></p><p> q=(p+i*i)%HashSize;<
81、/p><p><b> if(q>=0)</b></p><p><b> return q;</b></p><p><b> else</b></p><p><b> i=c/2+1;</b></p><p><
82、;b> }</b></p><p><b> else</b></p><p><b> {</b></p><p> q=(p-i*i)%HashSize;</p><p><b> c++;</b></p><p> i
83、f(q>=0)return q;</p><p> else i=c/2+1;</p><p><b> }</b></p><p><b> }</b></p><p> return (-1);</p><p><b> }</b>&
84、lt;/p><p> void CreateHash3(HashTable3 *h,int *a,int num)//二次探索表</p><p><b> {</b></p><p> int i,p=-1,c,pp;</p><p> for(i=0;i<num;i++)</p><p&g
85、t;<b> {</b></p><p><b> c=0;</b></p><p> p=a[i]%HashSize;</p><p><b> pp=p;</b></p><p> while(h->elem[pp]!=NULL)</p>&l
86、t;p><b> {</b></p><p> pp=Collision(p,c);</p><p><b> if(pp<0)</b></p><p><b> {</b></p><p> printf("第%d個記錄無法解決沖突\n&quo
87、t;,i+1);</p><p><b> continue;</b></p><p><b> }</b></p><p><b> }</b></p><p> h->elem[pp]=&(a[a[i]]);</p><p>
88、 h->count++;</p><p> printf("第%d個記錄沖突次數為%d\n",i+1,c);</p><p><b> }</b></p><p> printf("\n建表完成!\n此哈希表容量為%d,當前表內存儲的記錄個數%d.\n",HashSize,h->coun
89、t);</p><p><b> }</b></p><p> void SearchHash3(HashTable3 *h,int data)//哈希表二次探索再散列查找</p><p><b> {</b></p><p> int c=0,p,pp;</p><p&
90、gt; p=data%HashSize;</p><p><b> pp=p;</b></p><p> while((h->elem[pp]!=NULL)&&(*(h->elem[pp])!=data))</p><p> pp=Collision(p,c);</p><p> i
91、f((h->elem[pp]!=NULL)&&(*(h->elem[pp])==data))</p><p> printf("\n查找成功!\n查找沖突次數為%d:",c);</p><p><b> else</b></p><p> printf("\n沒有查到此數!\n&q
92、uot;);</p><p><b> }</b></p><p><b> int num;</b></p><p> void GetIn(int *a)</p><p><b> {</b></p><p> printf("輸
93、入添加的個數:");</p><p> scanf("%d",&num);</p><p> for(int i=0;i<num;i++)</p><p> scanf("%d",&a[i]);</p><p> printf("數據已經輸入完畢!\n&
94、quot;);</p><p><b> }</b></p><p> void GetOut(int *a)</p><p><b> {</b></p><p> printf("你所輸入的數據:");</p><p> for(int i=
95、0;i<num;i++)</p><p> printf("%d,",a[i]);</p><p> printf("\n輸出已完畢!");</p><p><b> }</b></p><p> void main()</p><p><
96、;b> {</b></p><p><b> int data;</b></p><p> HashTable1 hash1[HashSize];</p><p> HashTable2 * hash2[HashSize];</p><p> HashTable3 * ha;</p>
97、;<p> ha=(HashTable3 *)malloc(sizeof(HashTable3));</p><p> for(int i=0;i<HashSize;i++)</p><p> ha->elem[i]=NULL;</p><p> ha->count=0;</p><p> ha-&g
98、t;size=HashSize;</p><p> int a[MaxSize];</p><p><b> while(1)</b></p><p><b> {</b></p><p> printf("\n ┏━━━━━━━━━━━━━━━┓ "
99、); </p><p> printf("\n ┃ 歡迎使用本系統(tǒng) ┃ "); </p><p> printf("\n ┏〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓┓"); </p><p> printf("\n ┃★ ★ ★ ★ ★ ★散列法的實驗研
100、究★ ★ ★ ★ ★ ★┃");</p><p> printf("\n ┃ 【1】. 添加數據信息 【2】 數據的輸出 ┃");</p><p> printf("\n ┃ 【3】. 建立哈希表(線性再散列) ┃");</p><p> print
101、f("\n ┃ 【4】. 建立哈希表(二次探測再散列) ┃");</p><p> printf("\n ┃ 【5】. 建立哈希表(鏈地址法) ┃");</p><p> printf("\n ┃ 【6】. 線性再散列法查找
102、 ┃");</p><p> printf("\n ┃ 【7】. 二次探測再散列法查找 ┃");</p><p> printf("\n ┃ 【8】. 鏈地址法查找 ┃");</p><p> print
103、f("\n ┃ 【0】. 退出程序 ┃");</p><p> printf("\n ┗〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓〓┛");</p><p> printf("\n");</p><p> printf("
104、;\n");</p><p> printf("請輸入一個任務選項>>>");</p><p><b> int x;</b></p><p> scanf("%d",&x);</p><p><b> switch(x)<
105、;/b></p><p><b> {</b></p><p><b> case 1:</b></p><p> GetIn (a);break;</p><p><b> case 2:</b></p><p> GetOut(a);
106、break;</p><p><b> case 3:</b></p><p> CreateHashTable1(hash1,a,num);break;</p><p><b> case 4:</b></p><p> CreateHash3(ha,a,num);break;</p
107、><p><b> case 5:</b></p><p> CreateHashTable2(hash2,a,num);break;</p><p><b> case 6:</b></p><p> printf("請輸入你查找的數據:");</p><
108、;p> scanf("%d",&data);</p><p> SearchHash1(hash1,data);break;</p><p><b> case 7:</b></p><p> printf("請輸入你查找的數據:");</p><p> s
109、canf("%d",&data);</p><p> SearchHash3(ha,data);break;</p><p><b> case 8:</b></p><p> printf("請輸入你查找的數據:");</p><p> scanf("%
110、d",&data);</p><p> SearchHash2(hash2,data,num);break;</p><p> case 0:exit(-1);</p><p><b> }</b></p><p><b> } </b></p><p&
111、gt;<b> }</b></p><p> 3.3 程序運行結果(拷屏)</p><p> 利用線性再散列法,二次探查再散列,鏈地址法解決沖突</p><p> 4. 課程設計心得、存在問題及解決方法</p><p><b> (1) 收獲</b></p><p&g
112、t; 通過本次課程設計,使我對計算機語言有了更深一層的了解,也使我對算法的運用有了更多的體會,對算法和生活的聯(lián)系也有了更多的體會。更進一步了解和熟悉了關于哈希表的創(chuàng)建和運用。現在,計算機領域,他只向我展現了冰山一角,以后我會繼續(xù)探索。好的算法源于我們不斷的思考,思考源于我們對夢想的追尋。</p><p><b> (2) 心得體會</b></p><p> 在
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
評論
0/150
提交評論