課程設(shè)計報告--數(shù)據(jù)哈希表應(yīng)用

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數(shù)：14 大?。?.11MB 人氣指數(shù)：12 舉報 版權(quán)申訴

已閱讀1頁，還剩13頁未讀，繼續(xù)免費閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進行舉報或認領(lǐng)

文檔簡介

1、　　工學系課程設(shè)計報告　　設(shè) 計題目：數(shù)據(jù)哈希表應(yīng)用 　　系別：工學系 　　專業(yè) (方向)：網(wǎng)絡(luò)工程班

2、;　　年級、班：2012級計算機科學與技術(shù) 　　學生姓名： 　　學生學號： 　　指導(dǎo) 教師： &l

3、t;p>　　2013年 12 月 24 日　　目錄　　二、需求分析：1　　三、算法思想：1　　四、概要設(shè)計：2</b&g

4、t;　　五．系統(tǒng)的設(shè)計與實現(xiàn)2　　六、總結(jié)3　　七、附件（代碼、部分圖表）4　　哈希表應(yīng)用　　一、問題描述&l

5、t;/p>　　哈希表應(yīng)用設(shè)計：設(shè)哈希表長為13，用除留余數(shù)法構(gòu)造一個哈希函數(shù)，以開放定址法中的線性探測再散列法作為解決沖突的方法，編程實現(xiàn)哈希表的查找、插入、刪除、顯示和退出系統(tǒng)的算法。　　二、需求分析：　　1、功能需求<

6、p>　?、伲脩裟軌蜃远x輸入數(shù)據(jù)，存入哈希表里；　?、冢脩裟軌?qū)Ξ斍肮１磉M行管理。操作內(nèi)容包括：顯示當前哈希表、查詢某個數(shù)據(jù)、插入某個數(shù)據(jù)、刪除表中某個數(shù)據(jù)、退出該系統(tǒng)。　　③．程序有良好的交互界面，有操作提示和出錯提示，方便用戶使用和進出入程序。　　2、程序約束

7、　?、伲１淼纳⒘蟹椒槌粲鄶?shù)法，處理沖突的辦法為線性探測在散列。　　②．使用C/C++語言編寫，程序模塊化設(shè)計。程序可實現(xiàn)用戶與計算機的交互過程。在計算機顯示提示信息后，可由用戶鍵入運算命令以實現(xiàn)對應(yīng)的功能，包含表的建立、數(shù)據(jù)的查找、插入、刪除、顯示、退出等功能。　　本程序旨在實現(xiàn)哈希函數(shù)的構(gòu)造與處理存儲沖

8、突，因而指定哈希表存儲的數(shù)據(jù)類型為簡單的整型數(shù)字，在實用性上還有所欠缺。但根據(jù)用戶需求的變化，可以對程序的基本數(shù)據(jù)類型進行改造，以實現(xiàn)更為豐富的功能，進而體現(xiàn)哈希表在查找數(shù)據(jù)時的優(yōu)越性。　　三、算法思想：　　在設(shè)定哈希表的抽象數(shù)據(jù)類型時，要有查找數(shù)據(jù)元素的操作。另外，插入操作和刪除操作也要用到查找數(shù)據(jù)元素操作，以查看

9、該數(shù)據(jù)元素是否存在，因此可以設(shè)計查找元素操作包括插入和刪除操作的查找。　　因此，查找操作就有兩種情況：一種情況是插入操作時尋找空閑單元的查找；另一種情況是在查找和刪除操作時尋找該元素是否在哈希表中已存在的查找。插入操作時尋找空閑單元查找的特征是哈希表中不存在該對象，設(shè)計此時查找函數(shù)返回該空閑單元位置的“正”值；查找和刪除操作時尋找該元素是否在哈希表中已存在的特征是哈希表中已存在該數(shù)據(jù)元素，設(shè)計此

10、時查找函數(shù)返回該數(shù)據(jù)單元位置的“負”值。進而執(zhí)行后續(xù)操作。　　為了區(qū)分哈希表中每一個表元素的當前狀態(tài)，為每一個表元素設(shè)置一個“標志”定為tag。tag=0表示該元素為空；tag=1表示該元素以存放有數(shù)據(jù)元素；tag=-1表示該元素中存放的數(shù)據(jù)元素已被刪除。判斷當tag為0或-1時都可以進行插入操作。　　四、概要設(shè)計：

11、　　哈希表抽象數(shù)據(jù)類型的定義：　　ADT HashTable{　　數(shù)據(jù)對象：D={ai|ai∈ElemSet, i=1,2,...n, n≥0}　　數(shù)據(jù)關(guān)系：R1={<ai-1,ai>|ai-1∈D, i=1,2,...n}<p&

12、gt;　　基本操作：　　Initiate( &h )　　操作結(jié)果：構(gòu)造一個空的哈希表h。　　SearchHash( h, x, p )　　初始條件：哈希表h已存在；p為除留余數(shù)法中除數(shù)，由用戶指定。&l

13、t;p>　　操作結(jié)果：查找表中元素與指定數(shù)據(jù)x比較。元素已存在時返回其所在位置的負數(shù)下標、不存在時返回其位置的正數(shù)下標、遍歷哈希表后未查找到時返回表長。　　Insert( &h, x, p )　　初始條件：哈希表h已存在。　　操作結(jié)果：查找操作后插入元素x至哈希表。若元素已存在或哈希表已滿時插入操作

14、失敗，返回值為0。　　Delete(&h, x, p )　　初始條件：哈希表h已存在。　　操作結(jié)果：查找操作后從哈希表中刪除元素x。若元素不在表中時刪除操作失敗，返回值為0。　　Print( h )　　初始條件：哈希表h已

15、存在。　　操作結(jié)果：顯示哈希表中元素及存儲狀態(tài)。　　五．系統(tǒng)的設(shè)計與實現(xiàn)　　int Hash(T key); //計算哈希地址　　void Collision(int &s);//沖突,計算下一個地址　　int Searc

16、h(T key,int &s);//哈希查找　　int Insert(ElemType<T> e);//元素插入　　int Delete(ElemType<T> e); //元素刪除　　void Display(); //顯示哈希表　　te

17、mplate <class T>　　int LHSearch<T>::Insert(ElemType<T> e)　　{//插入元素　　int s;　　if(co

18、unt==size)　　{　　printf("表滿，不能插入!\n");　　return UNSUCCESS;　　}

19、　　else　　{　　s=Hash(e.key);　　int f;　　f=Search(e.key,s);　　if(f) //表中

20、已有和e的關(guān)鍵字相同的元素,不進行插入操作　　{　　printf("該元素已存在，不能插入!\n");　　return UNSUCCESS; }　　else

21、　　{　　HT[s].key=e.key;　　printf("插入成功!\n");　　count++;　　return SUCCESS; }</p&

22、gt;　　}　　}　　1、本次課程設(shè)計采用的是除留余數(shù)法構(gòu)造了哈希表，除數(shù)的選擇很重要。如果選得不好，會造成很多沖突，浪費時間和空間代價。例如，本次設(shè)計的哈希表最大長度為11，余數(shù)如果取得較小，會使得一部分元素容易形成堆積，平均搜索長度變大，而且取余的時間也

23、會更長。　　2、本次設(shè)計處理沖突采用了線性探測再散列的辦法。相比起同時閉散列方法的二次探測再散列來說，優(yōu)點在于功能簡單易操作性；缺點是當數(shù)據(jù)量逐漸加大時，前者的平均查找長度會逐漸比后者大。　　六、總結(jié)　　哈希表作為一種存儲與查找的優(yōu)化方式，通過把關(guān)鍵碼值映射到數(shù)表中一個位置來

24、訪問數(shù)據(jù)，以加快查找速度。在日常生活中，哈希函數(shù)的應(yīng)用也是隨處可見。當今十分流行的P2P數(shù)據(jù)傳輸技術(shù)中一系列的壓縮、打包以及積分標準都應(yīng)用到了hash算法設(shè)置?？梢娎霉：瘮?shù)用途之廣。　　本次程序設(shè)計中利用“除留余數(shù)法”構(gòu)造哈希函數(shù)，并用“開放定址法”中的“線性探測再散列”方式處理沖突，選取較為簡單的整型數(shù)字作為存儲數(shù)據(jù)。通過此次實驗，我對哈希表抽象數(shù)據(jù)類型的定義以及構(gòu)造方法有了初步的認識和了

25、解，也為今后編寫更復(fù)雜的應(yīng)用程序提供了新的思想方法與實現(xiàn)基礎(chǔ)。　　七、附件（代碼、部分圖表）　　#include<stdio.h>　　#define SUCCESS 1;　　#define UNSUCCESS 0;

26、#define NULLKEY -1;　　#define TableLength 13;　　#define p 13; // H(key)=key % p　　typedef int T;　　template <class T><p

27、>　　struct ElemType　　{　　T key;//關(guān)鍵字　　};　　template <class T>　　class LH

28、Search　　{　　private:　　ElemType<T> *HT; //開放定址哈希表　　int count; //當前數(shù)據(jù)元素個數(shù)

29、　int size; //哈希表長度　　public:　　LHSearch(); //　　~LHSearch(); //　　void InitHashTable(int n);//　　int

30、Hash(T key); //計算哈希地址　　void Collision(int &s);//沖突,計算下一個地址　　int Search(T key,int &s);//哈希查找　　int Insert(ElemType<T> e);//元素插入<p&

31、gt;　　int Delete(ElemType<T> e); //元素刪除　　void Display(); //顯示哈希表　　};　　template <class T>　　LHSearch<T>

32、;::LHSearch()　　{　　HT=NULL;　　size=0;　　count=0;<

33、;p>　　}　　template <class T>　　LHSearch<T>::~LHSearch()　　{ delete [] HT;　　count=0;<

34、/p>　　}　　template <class T>　　int LHSearch<T>::Hash(T key) 　　{//由哈希函數(shù)求哈希地址　　return key%p;<

35、/p>　　}　　template <class T>　　void LHSearch<T>::Collision(int &s)　　{//開放定址法解決沖突

36、　s=s++;　　}　　template <class T>　　int LHSearch<T>::Search(T key,int &s)　　{//查找，找到返回

37、　　//int s;　　s=Hash(key);　　while((HT[s].key!=-1) && (key!=HT[s].key))　　Collision(s);　　if(HT[s].key=

38、=key)　　return 1;　　else 　　return 0;　　}

39、template <class T>　　int LHSearch<T>::Insert(ElemType<T> e)　　{//插入元素　　int s;　　if(

40、count==size)　　{　　printf("表滿，不能插入!\n");　　return UNSUCCESS;　　}<b&g

41、t;　　else　　{　　s=Hash(e.key);　　int f;　　f=Search(e.key,s);　　if(f) //

42、表中已有和e的關(guān)鍵字相同的元素,不進行插入操作　　{　　printf("該元素已存在，不能插入!\n");　　return UNSUCCESS; }　　else</p&g

43、t;　　{　　HT[s].key=e.key;　　printf("插入成功!\n");　　count++;　　return SUCCESS; }</

44、p>　　}　　}　　template <class T>　　int LHSearch<T>::Delete(ElemType<T> e)<p&g

45、t;　　{//刪除元素　　int s;　　if(count==NULL)　　{　　printf("表空，不能刪除!\n");</p&

46、gt;　　return UNSUCCESS;　　}　　else　　{　　s=Hash(e.key);<p&

47、gt;　　int f;　　if(f)　　{　　HT[s].key=e.key;　　printf("刪除成功!\n");

48、　　count--;　　return SUCCESS; }//表中已有和e的關(guān)鍵字相同的元素,不進行插入操作　　else　　{　　pri

49、ntf("該元素不存在，不能刪除!\n");　　return UNSUCCESS; }　　}　　}　　template<class T>&l

50、t;p>　　void LHSearch<T>::InitHashTable(int n)　　{　　size=n;　　HT=new ElemType<T>[size];

51、　　for(int i=0;i<size;i++) //初始化，把哈希表置空　　HT[i].key=NULLKEY;　　}　　template<class T>　　void LHSearch<T>::Di

52、splay()　　{　　for(int i=0;i<size;i++)　　{　　printf("%d\n",i);　　if(HT

53、[i].key!=-1)　　printf("%d\n",HT[i].key);　　else　　printf("\t");　　printf("\n");

54、　　}　　}　　void main()　　{　　int m;

55、　　T key;　　int s=0;　　ElemType<int> e;　　LHSearch<int> a;　　printf("輸入相應(yīng)代碼，必須先創(chuàng)建哈希表\n

56、");　　do { 　　printf ("\t|===========================================================|\t\n");　　printf ("\t|

57、 |\t\n");　　printf ("\t| 哈希表應(yīng)用 |\t\n");　　printf ("\t|

58、 |\t\n");　　printf ("\t|===========================================================|\t\n");　　printf ("\n\t\t【1】--&g

59、t;建立!\t【2】-->插入!\t【3】-->刪除!\n");　　printf ("\n\t\t【4】-->查找!\t【5】-->顯示!\t【6】-->退出!\n");　　printf ("請選擇操作:");　　scanf(&quo

60、t;%d",&m); 　　switch(m)　　{　　case 1://創(chuàng)建查找表　　printf("請輸入表容量：\n");<

61、p>　　scanf("%d",&m); 　　a.InitHashTable(m);　　printf("依次輸入表元素，-1結(jié)束:\n");　　for(scanf("%d",&e.key) ;e.key!=-1;scanf("

62、;%d",&e.key))　　a.Insert(e);　　break;　　case 2: //插入元素　　printf("輸入要插入的元素:\n");

63、scanf("%d",&e.key); 　　a.Insert(e);　　break;　　case 3: //刪除元素　　printf("輸入要刪除的元素:\n");

64、　　scanf("%d",&e.key); 　　a.Delete(e);　　break;　　case 4: //查找　　printf("請輸入查找關(guān)鍵字：\n");&

65、lt;/p>　　scanf("%d",&key); 　　if(a.Search(key,s))　　printf("找到!\n");　　else　　printf

66、("不存在，末找到!\n");　　break;　　case 5://顯示哈希表　　a.Display();　　break;<b&

67、gt;　　case 6://　　printf("結(jié)束!\n");　　break;　　}　　}while(m!=6);

眾賞文庫> 全部分類> 畢業(yè)設(shè)計

溫馨提示

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

課程設(shè)計報告--數(shù)據(jù)哈希表應(yīng)用

文檔簡介

溫馨提示

最新文檔

評論

課程設(shè)計報告--數(shù)據(jù)哈希表應(yīng)用

文檔簡介

溫馨提示

最新文檔

評論

免費下載