數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)--哈希表設(shè)計(jì)問(wèn)題_第1頁(yè)
已閱讀1頁(yè),還剩15頁(yè)未讀 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、<p><b>  目 錄</b></p><p><b>  1 前言1</b></p><p><b>  2 需求分析1</b></p><p>  2.1 任務(wù)和要求1</p><p>  2.2 運(yùn)行環(huán)境1</p><p> 

2、 2.3 開(kāi)發(fā)工具2</p><p><b>  3 分析和設(shè)計(jì)2</b></p><p>  3.1 系統(tǒng)分析及設(shè)計(jì)思路2</p><p>  3.2 主要數(shù)據(jù)結(jié)構(gòu)及算法2</p><p>  3.3 函數(shù)流程圖3</p><p>  4 具體代碼實(shí)現(xiàn)6</p><

3、;p>  5 課程設(shè)計(jì)總結(jié)15</p><p>  5.1 程序運(yùn)行結(jié)果或預(yù)期運(yùn)行結(jié)果15</p><p>  5.2 設(shè)計(jì)結(jié)論17</p><p><b>  參考文獻(xiàn)17</b></p><p><b>  致 謝17</b></p><p><b

4、>  1 前言</b></p><p>  從C語(yǔ)言產(chǎn)生到現(xiàn)在,它已經(jīng)成為最重要和最流行的編程語(yǔ)言之一。在各種流行編程語(yǔ)言中,都能看到C語(yǔ)言的影子,如Java的語(yǔ)法與C語(yǔ)言基本相同。學(xué)習(xí)、掌握C語(yǔ)言是每一個(gè)計(jì)算機(jī)技術(shù)人員的基本功之一。 </p><p>  根據(jù)本次課程設(shè)計(jì)的要求,我設(shè)計(jì)小組將編寫一個(gè)C語(yǔ)言程序來(lái)處理哈希表問(wèn)題,通過(guò)這個(gè)程序,將針對(duì)自己的班集體中的“人名

5、”設(shè)計(jì)一個(gè)哈希表,使得平均查找長(zhǎng)度不超過(guò)R,完成相應(yīng)的建表和查表程序。</p><p><b>  2 需求分析</b></p><p><b>  2.1 任務(wù)和要求</b></p><p>  針對(duì)自己的班集體中的“人名”設(shè)計(jì)一個(gè)哈希表,使得平均查找長(zhǎng)度不超過(guò)R,完成相應(yīng)的建表和查表程序。</p><

6、;p>  要求:假設(shè)人名為中國(guó)姓名的漢語(yǔ)拼音形式。待填入哈希表的人名共有30個(gè),取平均查找長(zhǎng)度的上限為2。哈希函數(shù)用除留余數(shù)法構(gòu)造,用鏈表法處理沖突。</p><p><b>  2.2 運(yùn)行環(huán)境</b></p><p> ?。?)WINDOWS2000/XP系統(tǒng)</p><p> ?。?)Visual C++ 6.0編譯環(huán)境或TC編譯環(huán)

7、境</p><p><b>  2.3 開(kāi)發(fā)工具</b></p><p><b>  C語(yǔ)言</b></p><p><b>  3 分析和設(shè)計(jì)</b></p><p>  3.1 系統(tǒng)分析及設(shè)計(jì)思路</p><p><b> ?。?)創(chuàng)建哈希

8、表</b></p><p> ?。?)姓名(結(jié)構(gòu)體數(shù)組)初始化 </p><p> ?。?) 用除留余數(shù)法構(gòu)建哈希函數(shù)</p><p> ?。?) 用鏈表法處理沖突</p><p><b>  (3)查找哈希表</b></p><p>  在哈希表中進(jìn)行查找,輸出查找的結(jié)果和關(guān)鍵字,并

9、計(jì)算和輸出查找成功的平均查找長(zhǎng)度</p><p><b>  (4) 顯示哈希表</b></p><p>  顯示哈希表的的格式:</p><p>  3.2 主要數(shù)據(jù)結(jié)構(gòu)及算法</p><p>  定義結(jié)構(gòu)體typedef struct hashtable創(chuàng)建哈希表</p><p>  定義函數(shù)

10、Hash_Init(HashTable ht)來(lái)對(duì)哈希表初始化</p><p>  定義函數(shù)Hash_Insert(HashTable ht, Node *node)來(lái)為哈希表分配地址</p><p>  定義函數(shù)Hash_Init(ht)輸入30個(gè)名字</p><p>  定義函數(shù)Hash_Create(HashTable ht)來(lái)求哈希表長(zhǎng)度</p>

11、<p>  定義函數(shù)hash_output(HashTable h)來(lái)輸出哈希表</p><p>  定義函數(shù)Hash_Link()構(gòu)造鏈表函數(shù)</p><p>  定義函數(shù)int hash_search(int h[],int key)查找輸入的名字</p><p><b>  3.3 函數(shù)流程圖</b></p>

12、<p> ?。?)哈希表的創(chuàng)建及初始化流程圖 </p><p>  圖3.1 哈希表的創(chuàng)造及初始化流程圖</p><p> ?。?)創(chuàng)建哈希表鏈表的流程圖</p><p>  圖3.2 創(chuàng)造哈希表鏈表的流程圖</p><p> ?。?)查找輸入數(shù)據(jù)的流程圖</p><p&g

13、t;  圖3.3 查找輸入數(shù)據(jù)的流程圖</p><p><b>  4 具體代碼實(shí)現(xiàn)</b></p><p>  #include <stdio.h></p><p>  #include <string.h></p><p>  #include <stdlib.h></p&

14、gt;<p>  #include <conio.h></p><p>  #define P 30 /*除數(shù)余留法中的除數(shù)*/</p><p>  #define NULLKEY 0 </p><p>  #define MAX 30 /*人名個(gè)數(shù)*/</p><p>  #de

15、fine hashlen 30 /*哈希表長(zhǎng)度*/</p><p>  int sum=0,k=0;</p><p>  typedef struct Node /*哈希表結(jié)構(gòu)體*/</p><p><b>  {</b></p><p>  char key_code[10]; /*哈希表地址*/</p&g

16、t;<p>  struct Node *next;</p><p><b>  }Node;</b></p><p>  typedef struct hashtable /*創(chuàng)建哈希表*/ </p><p><b>  {</b></p><p><b>  

17、int key;</b></p><p>  struct Node *next;</p><p>  }HashTable[MAX];</p><p>  int Hash(int key) </p><p><b>  {</b></p><p>  

18、int mode = key % P; /*除留余數(shù)法得到的余數(shù)*/</p><p>  return mode;</p><p><b>  }</b></p><p>  void Hash_Init(HashTable ht) /*哈希表初始化*/ </p><p><b>  {<

19、/b></p><p><b>  int i;</b></p><p>  for(i = 0; i < MAX; i++)</p><p><b>  {</b></p><p>  ht[i].key = NULLKEY;</p><p>  ht[i].n

20、ext = NULL;</p><p><b>  }</b></p><p><b>  }</b></p><p>  int CharToInt(char str[]){</p><p>  return str[0]+str[1]+str[2];</p><p>&

21、lt;b>  }</b></p><p>  int Hash_Insert(HashTable ht, Node *node) /*為哈希表分配地址*/</p><p><b>  {</b></p><p>  int key = Hash(CharToInt(node->key_code));</p>

22、<p><b>  Node *p;</b></p><p>  p=(Node*)malloc(sizeof(Node));</p><p>  if(ht[key].key == NULLKEY)</p><p><b>  {</b></p><p>  ht[key].key =

23、 key;</p><p>  ht[key].next = node;</p><p><b>  k++;</b></p><p><b>  }</b></p><p>  else if(ht[key].key == key) </p><p><

24、b>  {</b></p><p>  p = ht[key].next;</p><p><b>  k++;</b></p><p>  while(p->next!= NULL) </p><p><b>  {</b></p><

25、;p>  p = p->next;</p><p><b>  k++;</b></p><p><b>  }</b></p><p>  p->next = node;</p><p><b>  k++;</b></p><p>

26、<b>  }</b></p><p><b>  return 1;</b></p><p><b>  }</b></p><p>  Node* Hash_Search(HashTable ht, int key) /*查找函數(shù)*/</p><p><b>  

27、{</b></p><p>  int p0 = Hash(key);</p><p>  if(ht[p0].key == NULLKEY) </p><p>  {sum++;return NULL;} </p><p>  else if(ht[p0].key == p0) </p>

28、<p><b>  {</b></p><p>  Node *p = ht[p0].next;</p><p>  while(p != NULL)</p><p><b>  {</b></p><p>  if(CharToInt(p->key_code) == key)&

29、lt;/p><p>  { sum++;</p><p><b>  return p;</b></p><p><b>  }</b></p><p>  p = p->next;</p><p><b>  sum++;</b></p&

30、gt;<p><b>  }</b></p><p><b>  }</b></p><p>  return NULL;</p><p><b>  }</b></p><p>  int Hash_Create(HashTable ht) /*哈希表長(zhǎng)度*/&

31、lt;/p><p><b>  { </b></p><p><b>  int i;</b></p><p>  Node *node;</p><p>  Hash_Init(ht);</p><p>  printf("請(qǐng)輸入姓名:"); /*輸入30個(gè)

32、姓名*/</p><p>  for(i=0;i<30;i++)</p><p><b>  {</b></p><p>  node = (Node *)malloc(sizeof(Node));</p><p>  scanf("%s",node->key_code);</p&g

33、t;<p>  node->next = NULL;</p><p>  Hash_Insert(ht, node);</p><p><b>  } </b></p><p>  printf("\nCreate Successfully!\n");</p><p><b&

34、gt;  return 1;</b></p><p><b>  }</b></p><p>  int hash_output(HashTable h) /*哈希表的輸出部分*/</p><p><b>  { </b></p><p><b>  Node *a;<

35、/b></p><p>  int i,j,count2=0;</p><p>  a=(Node*)malloc(sizeof(Node));</p><p><b>  j=0;</b></p><p>  for(i=0;i<hashlen;i++)</p><p><b&

36、gt;  { </b></p><p>  printf("%4d",i);</p><p>  printf("%4d",h[i].key);</p><p>  if(h[i].next!=0)</p><p><b>  count2++;</b></p&

37、gt;<p><b>  j=1;</b></p><p>  a=h[i].next;</p><p><b>  while(a)</b></p><p><b>  {</b></p><p>  printf("->%s",(*a

38、).key_code);</p><p>  a=(*a).next;</p><p><b>  j++;</b></p><p>  count2+=j;</p><p><b>  }</b></p><p>  printf("\n");</

39、p><p><b>  }</b></p><p>  return count2;</p><p><b>  }</b></p><p>  void Hash_Link() /*鏈表法構(gòu)造函數(shù)*/</p><p><b>  {&

40、lt;/b></p><p><b>  int key;</b></p><p><b>  int i;</b></p><p>  Node *node;</p><p>  HashTable ht;</p><p>  Hash_Create(ht);<

41、/p><p>  hash_output( ht);</p><p>  printf("count=%d\n",k); /*查找總長(zhǎng)度*/</p><p>  printf("ASL=%d/8\n",k); /*平均查找長(zhǎng)度*/</p><p>  printf("請(qǐng)輸入要

42、查找的數(shù)據(jù):"); /*輸入查找的姓名*/</p><p>  scanf("%s",&key);</p><p>  node = Hash_Search(ht, key);</p><p>  printf("查找次數(shù):%d\n",sum);</p><p>  if(node !

43、= NULL)</p><p>  printf("查找成功!");</p><p><b>  else</b></p><p>  printf("查找不成功!");</p><p><b>  }</b></p><p>  vo

44、id hash_create(int h[],int status[],int data)</p><p><b>  {</b></p><p>  int address;</p><p><b>  int di;</b></p><p>  address=data%P;</p>

45、<p>  if(status[address]==0)</p><p><b>  {</b></p><p>  h[address]=data;</p><p>  status[address]=1;</p><p><b>  }</b></p><p&g

46、t;<b>  else</b></p><p><b>  {</b></p><p>  for(di=1;di<=hashlen-1;di++)</p><p><b>  {</b></p><p>  address=((data%P)+di)%hashlen;

47、</p><p>  if(status[address]==0)</p><p><b>  {</b></p><p>  h[address]=data;</p><p>  status[address]=1;</p><p><b>  break;</b><

48、/p><p><b>  }</b></p><p><b>  }</b></p><p><b>  }</b></p><p><b>  return ;</b></p><p><b>  }</b>&l

49、t;/p><p>  int hash_search(int h[],int key)</p><p>  {int address, di;</p><p>  address=key % P;</p><p>  if(h[address]==key) /*哈希表中元素與查找元素是否相等*/</p><p&g

50、t;<b>  return 1;</b></p><p><b>  else </b></p><p><b>  {</b></p><p>  for(di=1;di<=hashlen-1;di++)/*哈希表中元素與查找元素不相等,查找下一元素*/</p><p&g

51、t;<b>  {</b></p><p>  address=((key%P)+di)%hashlen;</p><p>  if(h[address]==key)</p><p><b>  {</b></p><p>  return di+1;</p><p>&l

52、t;b>  break;</b></p><p><b>  }</b></p><p><b>  }</b></p><p><b>  }</b></p><p>  if(di>=hashlen)</p><p><

53、b>  return 0;</b></p><p><b>  }</b></p><p>  int main() /*主函數(shù)*/</p><p><b>  { </b></p><p>  printf("\t\t\t***

54、*********************\n");</p><p>  printf("\t\t\t 哈希表設(shè)計(jì)\n");</p><p>  printf("\n");</p><p>  printf("\t\t\t************************\n");</p&

55、gt;<p>  printf("\n");</p><p>  Hash_Link();</p><p><b>  }</b></p><p><b>  5 課程設(shè)計(jì)總結(jié)</b></p><p>  5.1 程序運(yùn)行結(jié)果或預(yù)期運(yùn)行結(jié)果</p>&

56、lt;p>  圖5.1程序運(yùn)行結(jié)果1</p><p>  圖5.2程序運(yùn)行結(jié)果2</p><p>  說(shuō)明:輸入的數(shù)為30個(gè)姓的拼音,查找的為“pan”,輸出的如上圖所示。</p><p><b>  5.2 設(shè)計(jì)結(jié)論</b></p><p>  通過(guò)這次課程設(shè)計(jì),我了解到了許多自身的不足,有很多學(xué)習(xí)過(guò)的知識(shí),在學(xué)

57、過(guò)之后并沒(méi)有反復(fù)的操作和復(fù)習(xí),以為課堂上聽(tīng)懂就行了,在這課程設(shè)計(jì)中,這些不足就顯現(xiàn)了出來(lái),導(dǎo)致經(jīng)常要翻書,查找一些以為弄懂的問(wèn)題,這次我了解到了,學(xué)習(xí)不僅僅是課堂上聽(tīng)講,還要課后復(fù)習(xí)和操作。</p><p>  課程設(shè)計(jì)是對(duì)我們這學(xué)期的學(xué)習(xí)成果的試金石,對(duì)我們來(lái)說(shuō)是一個(gè)不小的考驗(yàn),它是我們專業(yè)課程知識(shí)綜合應(yīng)用的實(shí)踐訓(xùn)練?!白约簞?dòng)手,豐衣足食”,通過(guò)這次課程設(shè)計(jì),我深深體會(huì)到這句千古名言的真正含義,只有理論知識(shí)是遠(yuǎn)

58、遠(yuǎn)不夠的,只有把所學(xué)的理論知識(shí)與實(shí)踐相結(jié)合起來(lái),從理論中得出結(jié)論,才能真正為社會(huì)服務(wù),從而提高自己的實(shí)際動(dòng)手能力和獨(dú)立思考的能力。</p><p>  實(shí)驗(yàn)過(guò)程中,也對(duì)團(tuán)隊(duì)精神的進(jìn)行了考察,讓我們?cè)诤献髌饋?lái)更加默契,在成功后一起體會(huì)喜悅的心情。果然是團(tuán)結(jié)就是力量,只有互相之間默契融洽的配合才能換來(lái)最終完美的結(jié)果。</p><p><b>  參考文獻(xiàn)</b></

59、p><p>  [1]張福祥. C語(yǔ)言程序設(shè)計(jì)[M]. 遼寧大學(xué)出版社,2008.1</p><p>  [2] 張福祥,王萌.C語(yǔ)言程序設(shè)計(jì)習(xí)題解答與實(shí)驗(yàn)實(shí)訓(xùn)[M].沈陽(yáng):遼寧大學(xué)出版社,2008.</p><p>  [3] 牛莉,劉遠(yuǎn)軍等.計(jì)算機(jī)等級(jí)考試輔導(dǎo)教程[M].北京:中國(guó)鐵道出版社,2008.</p><p><b>  

60、致 謝</b></p><p>  本次課程設(shè)計(jì)在選題及進(jìn)行過(guò)程中得到xx老師的悉心指導(dǎo),xx老師嚴(yán)謹(jǐn)求實(shí)的治學(xué)態(tài)度,熱情洋溢的工作激情,將使我終生受益,在老師的影響下我學(xué)到了很多在書本上學(xué)不到的東西,我非常感謝她。謹(jǐn)再一次向xx老師致以誠(chéng)摯的謝意和崇高的敬意。此外我還要感謝組內(nèi)的成員們,因?yàn)樗麄円矌臀医鉀Q了不少難題,正是在大家的共同努力下,本次課程設(shè)計(jì)將隨著論文的完成劃上圓滿的句號(hào)!</p&

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 眾賞文庫(kù)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

最新文檔

評(píng)論

0/150

提交評(píng)論