哈希表及其應用-課程設計

1、<p><b>　　課 程 設 計 </b></p><p><b>　　課程設計任務書</b></p><p>　　2010 ～2010 學年第 1 學期</p><p>　　一、課程設計題目 哈希表及其應用</p><p><b>　　二、課程設計內容</b&

2、gt;</p><p>　　建立一個小型信息管理系統(tǒng)（可以是圖書、人事、學生、物資、商品等任何信息管理系統(tǒng)）。要求：</p><p>　　1.使用哈希查找表存儲信息；</p><p>　　2.實現(xiàn)查找、插入、刪除、統(tǒng)計、輸出等功能；</p><p><b>　　三、進度安排</b></p><p>

3、;　　1．初步完成總體設計，搭好框架；</p><p>　　2．完成最低要求：嘗試使用多種哈希函數(shù)和沖突解決方法，并通過實際運行測試給出自己的評價</p><p><b>　　四、基本要求</b></p><p>　　1．界面友好，函數(shù)功能要劃分好</p><p>　　2．程序要加必要的注釋</p><

4、;p>　　3．要提供程序測試方案</p><p>　　教研室主任簽名： </p><p>　　年 月 日</p><p><b>　　目 錄</b></p><p>　　1 概述………………………………………………………………………4</p><p>　　2

5、 設計目的…………………………………………………………………4</p><p>　　3 設計功能說明……………………………………………………………4</p><p>　　4 詳細設計說明……………………………………………………………5</p><p>　　5 流程圖……………………………………………………………………5</p><p>

6、;　　6 程序代碼…………………………………………………………………6</p><p>　　7 程序運行結果……………………………………………………………15</p><p>　　8 總結………………………………………………………………………19</p><p>　　參考文獻 ……………………………………………………………………19</p>&l

7、t;p>　　成績評定表 …………………………………………………………………20</p><p><b>　　1 概述</b></p><p>　　數(shù)據(jù)結構是一門理論性強、思維抽象、難度較大的課程，是基礎課和專業(yè)課之間的橋梁，只有進行實際操作，將理論應用于實際中，才能確實掌握書中的知識點。通過課程設計，不僅可以加深學生對數(shù)據(jù)結構基本概念的了解，鞏固學習成果，還能夠

8、提高實際動手能力。為學生后繼課程的學習打下良好的基礎。</p><p><b>　　2 設計目的</b></p><p>　　《數(shù)據(jù)結構》課程設計是在教學實踐基礎上進行的一次大型實驗，也是對該課程所學理論知識的深化和提高。因此，要求學生能綜合應用所學知識，設計與制造出具有較復雜功能的應用系統(tǒng)，并且在實驗的基本技能方面上進行一次全面的訓練。通過程序的編譯掌握對程序的調試

9、方法及思想，并且讓學生學會使用一些編程技巧。促使學生養(yǎng)成良好的編程習慣。</p><p>　　1.使學生能夠較全面地鞏固和應用課堂中所學的的基本理論和程序設計方法，能夠較熟練地完成程序的設計和調試。</p><p>　　2.培養(yǎng)學生綜合運用所學知識獨立完成程序課題的能力。</p><p>　　3.培養(yǎng)學生勇于探索、嚴謹推理、實事求是、有錯必改，用實踐來檢驗理論，全方

10、位考慮問題等科學技術人員應具有的素質。</p><p>　　4．提高學生對工作認真負責、一絲不茍，對同學團結友愛，協(xié)作攻關的基本素質。</p><p>　　5.培養(yǎng)學生從資料文獻、科學實驗中獲得知識的能力，提高學生從別人經(jīng)驗中找到解決問題的新途徑的悟性，初步培養(yǎng)工程意識和創(chuàng)新能力。</p><p>　　6.對學生掌握知識的深度、運用理論去處理問題的能力、實驗能力、課

11、程設計能力、書面及口頭表達能力進行考核。</p><p><b>　　3 設計功能分析</b></p><p><b>　　本設計的功能如下：</b></p><p>　　1、利用哈希函數(shù)來實現(xiàn)一個小型信息管理系統(tǒng)，其中信息包含用戶名，地址，電話等。</p><p>　　2、能添加用戶信息，并能保存

12、該信息。</p><p>　　3、查詢管理系統(tǒng)中的信息：可通過姓名查找，也可通過電話查找等兩種方式。</p><p>　　4、能散列管理系統(tǒng)中的信息,保存信息等功能。</p><p><b>　　4 詳細設計說明</b></p><p>　　哈希表是一種重要的存儲方式，也是一種常見的檢索方法。其基本思想是將關系碼的值作為

13、自變量，通過一定的函數(shù)關系計算出對應的函數(shù)值，把這個數(shù)值解釋為結點的存儲地址，將結點存入計算得到存儲地址所對應的存儲單元。檢索時采用檢索關鍵碼的方法。</p><p>　　(1) 假定每個記錄有下列數(shù)據(jù)項：用戶名、電話號碼、地址。</p><p>　　(2) 初始記錄為空，通過不斷添加記錄，并保存到數(shù)據(jù)文件telphone.txt</p><p><b>

14、　　中。 </b></p><p>　　(3) 分別采用線性和平方探測解決沖突。</p><p>　　(4) 查找并顯示給定電話號碼的記錄；查找并顯示給定用戶</p><p><b>　　名的記錄。</b></p><p><b>　　5 流程圖</b></p><p

15、><b>　　6 程序代碼</b></p><p>　　#include <stdlib.h></p><p>　　#include <fstream></p><p>　　#include <iostream></p><p>　　#include <cmath>

16、</p><p>　　using namespace std;</p><p>　　#define Maxsize 57 </p><p>　　struct record</p><p>　　{char name[20];</p><p>　　char tel[20];</p><p>　　ch

17、ar add[20];};</p><p>　　typedef record *precord;</p><p>　　struct HashTable</p><p>　　{ int elem[Maxsize]; //存放數(shù)組a[]的下標</p><p>　　int count;};</p><p>　　typedef

18、 HashTable * pHashTable;</p><p>　　int Number; //統(tǒng)計當前數(shù)組a[]中的記錄總數(shù)</p><p>　　void Getdata(precord a) //從文件telphone.txt中讀取數(shù)據(jù)存放到數(shù)組a[]</p><p>　　{ Number=0;</p><p>　　ifstream i

19、nfile("telphone.txt",ios::in|ios::binary);</p><p>　　if(!infile) {cout<<"文件打開失敗!\n"; exit(1);}</p><p>　　while(!infile.eof() && infile.get()!=EOF) //文件不為空并且文件指針沒有

20、指到結束符</p><p>　　{infile.seekg(Number*sizeof(a[Number]),ios::beg); //定位文件指針</p><p>　　infile.read((char *)&a[Number],sizeof(a[Number]));</p><p>　　Number++;}</p><p>　　i

21、nfile.close();}</p><p>　　void Add(precord a) //添加記錄</p><p>　　{ int i,num;</p><p>　　cout<<"當前文件內已有"<<Number<<"條記錄\n";</p><p>　　cout

22、<<"請輸入添加的個數(shù):";</p><p><b>　　cin>>num;</b></p><p>　　ofstream ofile("telphone.txt",ios::app);</p><p>　　if(!ofile) {cout<<"文件打開失敗!

23、"; exit(1);} </p><p>　　for(i=0;i<num;i++)</p><p>　　{cout<<"請輸入第"<<Number+1<<"個人的姓名"<<endl;</p><p>　　cin>>a[Number].name; &l

24、t;/p><p>　　cout<<"請輸入第"<<Number+1<<"個人的電話"<<endl;</p><p>　　cin>>a[Number].tel; </p><p>　　cout<<"請輸入第"<<Number+1&

25、lt;<"個人的地址"<<endl;</p><p>　　cin>>a[Number].add; </p><p>　　ofile.seekp(ios::end);</p><p>　　ofile.write((char *)&a[Number],sizeof(a[Number]));</p>

26、<p>　　Number++;}</p><p>　　ofile.close();}</p><p>　　void Print(precord a) //顯示所有記錄</p><p><b>　　{ int i;</b></p><p>　　for(i=0;i<Number;i++)</p>

27、<p>　　{cout<<" 姓名:"<<a[i].name;</p><p>　　cout<<" 電話:"<<a[i].tel;</p><p>　　cout<<" 地址:"<<a[i].add<<endl;}</p>

28、<p><b>　　}</b></p><p>　　int Hash(char str[]) //除留取余</p><p>　　{ long val=0;char p[20],*p1;</p><p>　　strcpy(p,str);</p><p><b>　　p1=p;</b><

29、/p><p>　　while(*p1!='\0')</p><p>　　val=val+*p1++; //將字符串中的所有字符對應的ASCII值相加</p><p>　　return(val%Maxsize);</p><p><b>　　}</b></p><p>　　int der

30、ter; //線性增量</p><p>　　int Line_Sollution(int address) //采用線性探測解決沖突</p><p><b>　　{ </b></p><p><b>　　derter++;</b></p><p>　　if(derter==Maxsize) retu

31、rn(-1);</p><p>　　else return((address+derter)%Maxsize);</p><p><b>　　}</b></p><p><b>　　int n;</b></p><p>　　int Square_Sollution(int address) //采用

32、平方探測法解決沖突</p><p>　　{ int j;derter++;</p><p>　　if(derter==Maxsize) return -1;</p><p><b>　　n=n*(-1);</b></p><p>　　j=(int(pow((float)derter,2))*n+address)%Maxs

33、ize;</p><p>　　return(j);}</p><p>　　void Init_Hash(pHashTable h) //初始化哈希表</p><p><b>　　{ int i;</b></p><p>　　for(i=0;i<Maxsize;i++)</p><p>　　h

34、->elem[i]=-1;</p><p><b>　　}</b></p><p><b>　　int menu;</b></p><p>　　void Creathash_Name(pHashTable h,precord a)//以員工姓名為關鍵字創(chuàng)建哈希表</p><p>　　{cout

35、<<" ------------------------------------------------------------------------\n";</p><p>　　cout<<" 1----以線性探測建表\n";</p><p>　　cout<<"

36、 2----以平方探測建表\n";</p><p>　　cout<<" ------------------------------------------------------------------------\n";</p><p>　　int i,address;</p>&

37、lt;p>　　cout<<"請選擇:";</p><p>　　cin>>menu;</p><p>　　Init_Hash(h);</p><p>　　for(i=0;i<Number;i++)</p><p>　　{ derter=0;n=-1;</p><p>

38、;　　address=Hash(a[i].name);</p><p>　　while(h->elem[address]!=-1)</p><p>　　{if(menu==1) address=Line_Sollution(address);</p><p>　　else address=Square_Sollution(address);</p>

39、<p>　　if(address==-1) break;}</p><p>　　if(address!=-1) { h->elem[address]=i; h->count++;}</p><p><b>　　}</b></p><p>　　cout<<"姓名哈希表已成功建立!\n";&

40、lt;/p><p><b>　　}</b></p><p>　　void Search_Name(pHashTable h,precord a) //查找并顯示指定姓名的記錄</p><p>　　{ cout<<"請輸入要查找的姓名:";</p><p>　　char nam[20];int

41、address,i=1;</p><p><b>　　cin>>nam;</b></p><p>　　address=Hash(nam);</p><p>　　derter=0;n=-1;</p><p>　　while(h->elem[address]!=-1 && strcmp(na

42、m,a[h->elem[address]].name)!=0)</p><p>　　{ if(menu==1) address=Line_Sollution(address);</p><p>　　else address=Square_Sollution(address);</p><p><b>　　i++;</b></p>

43、;<p>　　if(address==-1) break;}</p><p>　　if(h->elem[address]!=-1 && strcmp(nam,a[h->elem[address]].name)==0)</p><p>　　{ cout<<"你要查找的信息為:\n";</p><p&

44、gt;　　cout<<" 姓名:"<<a[h->elem[address]].name<<endl;</p><p>　　cout<<" 電話:"<<a[h->elem[address]].tel<<endl;</p><p>　　cout<<"

45、 地址:"<<a[h->elem[address]].add<<endl;</p><p>　　cout<<"比較次數(shù)為"<<i<<endl;}</p><p>　　else cout<<"無此姓名,查找失敗!";</p><p><

46、b>　　}</b></p><p>　　void Creathash_tel(pHashTable h,precord a) //以電話號為關鍵字創(chuàng)建哈希表</p><p>　　{cout<<" ---------------------------------------------------------\n";</

47、p><p>　　cout<<" 1----以線性探測建表\n";</p><p>　　cout<<" 2----以平方探測建表\n";</p><p>　　cout<<" ------------

48、---------------------------------------------\n";</p><p>　　int i,address;</p><p>　　cout<<"請選擇:";</p><p>　　cin>>menu;</p><p>　　Init_Hash(h);&l

49、t;/p><p>　　for(i=0;i<Number;i++)</p><p>　　{ derter=0;n=-1;</p><p>　　address=Hash(a[i].tel);</p><p>　　while(h->elem[address]!=-1)</p><p>　　{if(menu==1) a

50、ddress=Line_Sollution(address);</p><p>　　else address=Square_Sollution(address);</p><p>　　if(address==-1) break;}</p><p>　　if(address!=-1) { h->elem[address]=i; h->count++;}&l

51、t;/p><p><b>　　}</b></p><p>　　cout<<"電話號碼哈希表已成功建立!\n";}</p><p>　　void Search_tel(pHashTable h,precord a)//查找并顯示指定電話號的記錄</p><p>　　{ cout<<&

52、quot;請輸入要查找的電話:";</p><p>　　char telphone[20];int address,i=1; //i統(tǒng)計比較次數(shù)</p><p>　　cin>>telphone;</p><p>　　address=Hash(telphone);</p><p>　　derter=0; n=-1; //初

53、始化線性增量</p><p>　　while(h->elem[address]!=-1&& strcmp(telphone,a[h->elem[address]].tel)!=0)</p><p>　　{ if(menu==1) address=Line_Sollution(address);</p><p>　　else address

54、=Square_Sollution(address);</p><p><b>　　i++;</b></p><p>　　if(address==-1) break;}</p><p>　　if(h->elem[address]!=-1 && strcmp(telphone,a[h->elem[address]].t

55、el)==0)</p><p>　　{ cout<<"你要查找的信息為:\n";</p><p>　　cout<<" 姓名:"<<a[h->elem[address]].name<<endl;</p><p>　　cout<<" 電話:"&l

56、t;<a[h->elem[address]].tel<<endl;</p><p>　　cout<<" 地址:"<<a[h->elem[address]].add<<endl;</p><p>　　cout<<"比較次數(shù)為"<<i<<endl;}&l

57、t;/p><p>　　else cout<<"無此電話,查找失敗!";</p><p><b>　　}</b></p><p>　　void Delet(pHashTable h,precord a)</p><p>　　{cout<<" --------

58、-------------------------------------------------\n";</p><p>　　cout<<" 1----按電話號碼刪除\n";</p><p>　　cout<<" 2----按姓名刪除\n"

59、;;</p><p>　　cout<<" ---------------------------------------------------------\n";</p><p><b>　　int m;</b></p><p>　　cout<<"請選擇:";&l

60、t;/p><p><b>　　cin>>m;</b></p><p><b>　　if(m==1)</b></p><p>　　{cout<<"請輸入要刪除的電話:";</p><p>　　char telphone[20];</p><p

61、>　　int address,i,j; </p><p>　　cin>>telphone;</p><p>　　address=Hash(telphone);</p><p>　　derter=0; n=-1; //初始化線性增量</p><p>　　while(h->elem[address]!=-1 &&a

62、mp; strcmp(telphone,a[h->elem[address]].tel)!=0)</p><p>　　{ if(menu==1) address=Line_Sollution(address);</p><p>　　else address=Square_Sollution(address);</p><p>　　if(address==-1)

63、 break;}</p><p>　　if(h->elem[address]!=-1&& strcmp(telphone,a[h->elem[address]].tel)==0)</p><p>　　{j=h->elem[address];</p><p>　　h->elem[address]=-1;</p>&

64、lt;p><b>　　}</b></p><p>　　for (i=j;i<Number-1;i++)</p><p>　　{strcpy(a[i].name,a[i+1].name);</p><p>　　strcpy(a[i].tel,a[i+1].tel);</p><p>　　strcpy(a[i].

65、add,a[i+1].add);}</p><p>　　Number=Number-1;</p><p><b>　　}</b></p><p><b>　　if(m==2)</b></p><p>　　{cout<<"請輸入要刪除的姓名:";</p>

66、<p>　　char nam[20];int address,i,j;</p><p><b>　　cin>>nam;</b></p><p>　　address=Hash(nam);</p><p>　　derter=0;n=-1;</p><p>　　while(h->elem[addre

67、ss]!=-1 && strcmp(nam,a[h->elem[address]].name)!=0)</p><p>　　{ if(menu==1) address=Line_Sollution(address);</p><p>　　else address=Square_Sollution(address);</p><p><b&

68、gt;　　i++;</b></p><p>　　if(address==-1) break;}</p><p>　　if(h->elem[address]!=-1 && strcmp(nam,a[h->elem[address]].name)==0)</p><p>　　{ j=h->elem[address];h-&g

69、t;elem[address]=-1;}</p><p>　　for (i=j;i<Number-1;i++)</p><p>　　{strcpy(a[i].name,a[i+1].name);</p><p>　　strcpy(a[i].tel,a[i+1].tel);</p><p>　　strcpy(a[i].add,a[i+1]

70、.add);}</p><p>　　Number=Number-1;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void Menu() //功能菜單函數(shù)</p><p>　　{cout<<endl;<

71、/p><p>　　cout<<" 員工管理查詢系統(tǒng)\n";</p><p>　　cout<<'\n';</p><p>　　cout<<" ★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆\n";<

72、/p><p>　　cout<<" ★ 1-------添加 ☆\n"; </p><p>　　cout<<" ☆ 2-------顯示所有

73、 ★\n"; </p><p>　　cout<<" ★ 3-------以姓名建立哈希表 ☆\n"; </p><p>　　cout<<" ☆ 4-------以電話

74、號碼建立哈希表 ★\n"; </p><p>　　cout<<" ★ 5-------按員工姓名查找 ☆\n"; </p><p>　　cout<<" ☆

75、6-------按電話號碼查找 ★\n"; </p><p>　　cout<<" ★ 7-------刪除員工信息 ☆\n";</p><p>　　cout<<"

76、 ☆ 0-------退出 ★\n"; </p><p>　　cout<<" ★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆★☆\n";</p><p>　　cout<<" 使用說明:\n";</p>

77、<p>　　cout<<" 1.添加新紀錄后,如要進行查找請先進行3或4操作\n";</p><p>　　cout<<" 2.按員工姓名查找之前,請先進行3操作建立用戶名哈希表\n";</p><p>　　cout<<" 3.按電話號碼查找之前,請

78、先進行4操作建立電話號碼哈希表\n";}</p><p>　　void exit()</p><p><b>　　{ int i;</b></p><p>　　for(i=1;i<=4;i++)</p><p>　　cout<<endl;</p><p>　　cout&

79、lt;<" ◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◇◆◇\n";</p><p>　　cout<<" ◆ ◆\n";</p><p>　　cout<<"

80、◇ 員 工 管 理 查 詢 系 統(tǒng) ◇\n";</p><p>　　cout<<" ◆ ◆\n";</p><p>　　cout<<" ◇

81、 謝 謝 您 的 使 用 ! ◇\n";</p><p>　　cout<<" ◆ ◆\n";</p><p>　　cout<<" ◇◆◇◆

82、◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆◇◆\n";</p><p>　　system("pause");}</p><p>　　int main()</p><p>　　{ record a[Maxsize];</p><p>　　pHashTable H=new HashTable;</p>

83、<p>　　Getdata(a); //將文件中的數(shù)據(jù)讀入到數(shù)組a中</p><p>　　system("color BD");</p><p><b>　　start:</b></p><p><b>　　Menu();</b></p><p>　　cout<

84、<"請選擇:";</p><p>　　int menu1;</p><p>　　cin>>menu1;</p><p>　　switch(menu1)</p><p>　　{ case 0:system("cls");exit();break;</p><p>

85、　　case 1:Add(a);system("pause");system("cls");goto start;break;</p><p>　　case 2:Print(a);system("pause");system("cls");goto start;break;</p><p>　　case3:Cr

86、eathash_Name(H,a);system("pause");system("cls");goto start;break;</p><p>　　case4:Creathash_tel(H,a);system("pause");system("cls");goto start;break;</p><p>

87、;　　case5:Search_Name(H,a);system("pause");system("cls");goto start;break;</p><p>　　case 6:Search_tel(H,a);system("pause");system("cls");goto start;break;</p>&l

88、t;p>　　case 7:Delet(H,a);system("pause");system("cls");goto start;break;</p><p>　　default:cout<<"請輸入正確的操作選項!\n";system("cls");goto start;break;}</p><

89、;p><b>　　return 0;</b></p><p><b>　　}</b></p><p><b>　　7 程序運行結果</b></p><p><b>　　主界面</b></p><p><b>　　添加記錄</b>

90、</p><p><b>　　顯示所有</b></p><p><b>　　建立哈希表</b></p><p><b>　　查找</b></p><p><b>　　刪除</b></p><p><b>　　退出</

91、b></p><p><b>　　8 總結</b></p><p>　　數(shù)據(jù)結構是計算機學科非常重要的一門必修課程，它與計算機其他課程都有密切聯(lián)系，具有獨特的承上啟下的重要位置。同時數(shù)據(jù)結構還是一門實踐性極強的理論技術基礎課。這次數(shù)據(jù)結構課程設計為我們提供了與眾不同的學習方法和學習機會，讓我們從被動授學轉變?yōu)橹鲃忧髮W，從死記硬背的模式中脫離出來，轉變?yōu)樵趯嵺`中

92、學習。 </p><p>　　在實際的上機操作過程中，不僅是讓我們了解數(shù)據(jù)結構的理論知識，更重要的是培養(yǎng)解決實際問題的能力，所以相信通過此次實習可以提高我們分析設計能力和編程能力，為后續(xù)課程的學習及實踐打下良好的基礎。</p><p><b>　　參考文獻</b></p><p>　　[1] 蘇仕民.數(shù)據(jù)結構課程設計 北京：機械工業(yè)出版社.

93、2005</p><p>　　[2] C++面向對象程序設計教程/陳維興，林小茶編著 北京：清華大學出版社，2009.6</p><p>　　[3] C語言版/嚴蔚敏，吳偉民 北京:清華大學出版社，2007</p><p>　　[4] 徐孝凱.數(shù)據(jù)結構實用教程（C/C++描述）[M]. (第一版)北京:清華大學出版社.1999</p><p&