課程設計報告--數據哈希表應用

1、. 蘭州商學院隴橋學院 工學系課程設計報告設 計 題 目：數據哈希表應用 系 別：工學系 專 業(yè) (方 向)：網絡工程班 年 級、 班：2012級計算機科學與技術 學 生 姓 名：李妮 學 生 學 號：20120661116 指 導 教 師：王萬玉 2013年 12 月 24 日目錄二、需求分析：1三、算法思想：1四、概要設計：2五系統(tǒng)的設計與實現2六、總結3七、附件（代碼、部分圖表）4；哈希表應用一、問題描述哈希表應用設計：設哈希表長為13，用除留余數法構造一個哈希函數，以開放定址法中的線性探測再散列法作為解決沖突的方法，編程實現哈希表的查找、插入、刪除、顯示和退出系統(tǒng)的算法。二、需求分析：

2、1、功能需求用戶能夠自定義輸入數據，存入哈希表里；用戶能夠對當前哈希表進行管理。操作內容包括：顯示當前哈希表、查詢某個數據、插入某個數據、刪除表中某個數據、退出該系統(tǒng)。程序有良好的交互界面，有操作提示和出錯提示，方便用戶使用和進出入程序。2、程序約束哈希表的散列方法為除留余數法，處理沖突的辦法為線性探測在散列。使用C/C+語言編寫，程序模塊化設計。程序可實現用戶與計算機的交互過程。在計算機顯示提示信息后，可由用戶鍵入運算命令以實現對應的功能，包含表的建立、數據的查找、插入、刪除、顯示、退出等功能。本程序旨在實現哈希函數的構造與處理存儲沖突，因而指定哈希表存儲的數據類型為簡單的整型數字，在實用性

3、上還有所欠缺。但根據用戶需求的變化，可以對程序的基本數據類型進行改造，以實現更為豐富的功能，進而體現哈希表在查找數據時的優(yōu)越性。三、算法思想：在設定哈希表的抽象數據類型時，要有查找數據元素的操作。另外，插入操作和刪除操作也要用到查找數據元素操作，以查看該數據元素是否存在，因此可以設計查找元素操作包括插入和刪除操作的查找。因此，查找操作就有兩種情況：一種情況是插入操作時尋找空閑單元的查找；另一種情況是在查找和刪除操作時尋找該元素是否在哈希表中已存在的查找。插入操作時尋找空閑單元查找的特征是哈希表中不存在該對象，設計此時查找函數返回該空閑單元位置的“正”值；查找和刪除操作時尋找該元素是否在哈希表中

4、已存在的特征是哈希表中已存在該數據元素，設計此時查找函數返回該數據單元位置的“負”值。進而執(zhí)行后續(xù)操作。為了區(qū)分哈希表中每一個表元素的當前狀態(tài)，為每一個表元素設置一個“標志”定為tag。tag=0表示該元素為空；tag=1表示該元素以存放有數據元素；tag=-1表示該元素中存放的數據元素已被刪除。判斷當tag為0或-1時都可以進行插入操作。四、概要設計：哈希表抽象數據類型的定義：ADT HashTable 數據對象：D=ai|aiElemSet, i=1,2,.n, n0 數據關系：R1=|ai-1D, i=1,2,.n 基本操作：Initiate( &h ) 操作結果：構造一個空的哈希表h。

5、SearchHash( h, x, p ) 初始條件：哈希表h已存在；p為除留余數法中除數，由用戶指定。 操作結果：查找表中元素與指定數據x比較。元素已存在時返回其所在位置的負數下標、不存在時返回其位置的正數下標、遍歷哈希表后未查找到時返回表長。Insert( &h, x, p ) 初始條件：哈希表h已存在。 操作結果：查找操作后插入元素x至哈希表。若元素已存在或哈希表已滿時插入操作失敗，返回值為0。Delete(&h, x, p ) 初始條件：哈希表h已存在。 操作結果：查找操作后從哈希表中刪除元素x。若元素不在表中時刪除操作失敗，返回值為0。Print( h ) 初始條件：哈希表h已存在。

6、 操作結果：顯示哈希表中元素及存儲狀態(tài)。五系統(tǒng)的設計與實現int Hash(T key); /計算哈希地址void Collision(int &s);/沖突,計算下一個地址int Search(T key,int &s);/哈希查找int Insert(ElemType e);/元素插入int Delete(ElemType e); /元素刪除void Display(); /顯示哈希表template int LHSearch:Insert(ElemType e)/插入元素int s;if(count=size) printf(表滿，不能插入!n); return UNSUCCESS;el

7、se s=Hash(e.key); int f; f=Search(e.key,s); if(f) /表中已有和e的關鍵字相同的元素,不進行插入操作 printf(該元素已存在，不能插入!n); return UNSUCCESS; else HTs.key=e.key; printf(插入成功!n); count+; return SUCCESS; 1、本次課程設計采用的是除留余數法構造了哈希表，除數的選擇很重要。如果選得不好，會造成很多沖突，浪費時間和空間代價。例如，本次設計的哈希表最大長度為11，余數如果取得較小，會使得一部分元素容易形成堆積，平均搜索長度變大，而且取余的時間也會更長。2、

8、本次設計處理沖突采用了線性探測再散列的辦法。相比起同時閉散列方法的二次探測再散列來說，優(yōu)點在于功能簡單易操作性；缺點是當數據量逐漸加大時，前者的平均查找長度會逐漸比后者大。六、總結哈希表作為一種存儲與查找的優(yōu)化方式，通過把關鍵碼值映射到數表中一個位置來訪問數據，以加快查找速度。在日常生活中，哈希函數的應用也是隨處可見。當今十分流行的P2P數據傳輸技術中一系列的壓縮、打包以及積分標準都應用到了hash算法設置。可見利用哈希函數用途之廣。本次程序設計中利用“除留余數法”構造哈希函數，并用“開放定址法”中的“線性探測再散列”方式處理沖突，選取較為簡單的整型數字作為存儲數據。通過此次實驗，我對哈希表抽

9、象數據類型的定義以及構造方法有了初步的認識和了解，也為今后編寫更復雜的應用程序提供了新的思想方法與實現基礎。七、附件（代碼、部分圖表）#include#define SUCCESS 1;#define UNSUCCESS 0;#define NULLKEY -1;#define TableLength 13;#define p 13; / H(key)=key % p typedef int T;template struct ElemTypeT key;/關鍵字;template class LHSearchprivate:ElemType *HT; /開放定址哈希表int count; /

10、當前數據元素個數int size; /哈希表長度public:LHSearch(); / LHSearch(); / void InitHashTable(int n);/ int Hash(T key); /計算哈希地址void Collision(int &s);/沖突,計算下一個地址int Search(T key,int &s);/哈希查找int Insert(ElemType e);/元素插入int Delete(ElemType e); /元素刪除void Display(); /顯示哈希表;template LHSearch:LHSearch()HT=NULL;size=0;co

11、unt=0;template LHSearch:LHSearch() delete HT;count=0;template int LHSearch:Hash(T key) /由哈希函數求哈希地址return key%p;template void LHSearch:Collision(int &s)/開放定址法解決沖突s=s+;template int LHSearch:Search(T key,int &s)/查找，找到返回/int s;s=Hash(key);while(HTs.key!=-1) & (key!=HTs.key) Collision(s);if(HTs.key=key)

12、return 1;else return 0;template int LHSearch:Insert(ElemType e)/插入元素int s;if(count=size) printf(表滿，不能插入!n); return UNSUCCESS;else s=Hash(e.key); int f; f=Search(e.key,s); if(f) /表中已有和e的關鍵字相同的元素,不進行插入操作 printf(該元素已存在，不能插入!n); return UNSUCCESS; else HTs.key=e.key; printf(插入成功!n); count+; return SUCCES

13、S; template int LHSearch:Delete(ElemType e)/刪除元素int s;if(count=NULL) printf(表空，不能刪除!n); return UNSUCCESS;else s=Hash(e.key); int f; if(f) HTs.key=e.key; printf(刪除成功!n); count-; return SUCCESS; /表中已有和e的關鍵字相同的元素,不進行插入操作 else printf(該元素不存在，不能刪除!n); return UNSUCCESS; templatevoid LHSearch:InitHashTable(

14、int n)size=n;HT=new ElemTypesize;for(int i=0;isize;i+) /初始化，把哈希表置空 HTi.key=NULLKEY;templatevoid LHSearch:Display()for(int i=0;isize;i+) printf(%dn,i); if(HTi.key!=-1) printf(%dn,HTi.key); else printf(t); printf(n);void main()int m;T key;int s=0;ElemType e;LHSearch a;printf(輸入相應代碼，必須先創(chuàng)建哈希表n);do print

15、f (t|=|tn); printf (t| |tn); printf (t| 哈希表應用 |tn); printf (t| |tn); printf (t|=|tn); printf (ntt【1】-建立!t【2】-插入!t【3】-刪除!n);printf (ntt【4】-查找!t【5】-顯示!t【6】-退出!n); printf (請選擇操作:); scanf(%d,&m); switch(m) case 1:/創(chuàng)建查找表 printf(請輸入表容量：n); scanf(%d,&m); a.InitHashTable(m); printf(依次輸入表元素，-1結束:n); for(scanf(%d,&e.key) ;e.key!=-1;scanf(%d,&e.key) a.Insert(e); break; case 2: /插入元素 printf(輸入要插入的元素:n); scanf(%d,&e.key); a.Insert(e); break; case 3: /刪除元素 prin