散列表的設計與實現(xiàn)

一、需求分析

本系統(tǒng)為電話號碼查找系統(tǒng)，本系統(tǒng)最頻繁的操作為查詢功能，查詢速度的快慢對此系統(tǒng)有至關(guān)重要的影響，因此應該選擇合適的數(shù)據(jù)結(jié)構(gòu)來進行設計。散列表可以實現(xiàn) O(1)的快速查找，用 Hash 數(shù)據(jù)結(jié)構(gòu)作為底層存儲結(jié)構(gòu)較為合適。本系統(tǒng)應首先實現(xiàn)Hash表的基本結(jié)構(gòu)和操作，在此基礎上構(gòu)建電話號碼查找系統(tǒng)。電話號碼查找系統(tǒng)包括若干數(shù)據(jù)項：電話號碼、用戶名、地址，可以鍵盤輸入或文件批量導入記錄，既可以使用電話號碼作為索引建立Hash表，也可以使用姓名作為索引建立Hash表，并通過電話號碼和姓名進行查找記錄。更進一步，在設計Hash數(shù)據(jù)結(jié)構(gòu)時，可設計不同的Hash函數(shù)及采用不同的沖突解決算法，來比較性能的差異。具體功能如下：

1.1 Hash表設計
設計 Hash 表的 ADT，設計 Hash 表的存儲結(jié)構(gòu)以及基本操作，設計不同的 Hash函數(shù)對字符串進行散列，設計不同的沖突解決策略，如鏈地址法、線性探測法等。Hash表的結(jié)構(gòu)由key-value組成，基本操作有添加元素、查找元素、刪除元素、遍歷元素、建表、銷毀表等，并且設計可以計算平均查找長度（ASL）的函數(shù)，以此來比較不同的Hash函數(shù)使用相同的沖突解決算法，以及相同的Hash 函數(shù)使用不同的沖突解決算法的優(yōu)劣。為方便Hash表的使用，Hash表可自動擴容。

1.2 添加與導入記錄
系統(tǒng)可采用兩種方式導入信息：手動添加與文件批量導入。手動添加方式用戶通過交互性界面一步一步輸入待添加記錄的電話號碼、姓名、地址，可連續(xù)進行添加。文件批量導入方式，預先將記錄以指定格式寫入文件，系統(tǒng)再從指定文件中批量導入。

1.3 查詢記錄
查詢記錄功能為此系統(tǒng)主要功能，可采用兩種查詢方式：按電話號碼查詢與按姓名查詢。如果是按照電話號碼建立索引，按電話號碼查詢將迅速完成，如果是按照姓名建立索引，按姓名查詢將迅速完成。

1.4 不同Hash函數(shù)比較
設計多種 Hash 函數(shù)，使用同一沖突解決方法比較其 ASL，研究不同 Hash 函數(shù)對于沖突率的影響。

1.5 不同沖突解決方法比較
設計多種沖突解決方法，使用同一 Hash 函數(shù)比較其 ASL，研究不同的沖突解決方法對于 ASL 的影響。

二、概要設計

2.1 數(shù)據(jù)類型的定義
使用鏈地址法的 Hash ADT 設計

#define MAXCAPACITY 1 << 30 #define LOADFACTOR 0.75f?

#define MAXKEYLEN 255?

typedef AddList ElemType;s

truct Node { char key[MAXKEYLEN]; ElemType value; Node *next;};

struct HashTable { int capacity; int size; Node *table;};i

nt NextPrime(int n);

void InitHashTable(HashTable &hash_table, int init_capacity);

unsigned int SumHash(const char *key, int table_size);

unsigned int ShiftHash(const char *key, int table_size);

unsigned int ELFHash(const char *key, int table_size);

bool Put(HashTable &hash_table, const char *key, ElemType value, ElemType &old_value, unsigned int (*Hash)(const char *key, int table_size));

bool Get(HashTable &hash_table, const char *key, ?ElemType &value, unsigned int (*Hash)(const char *key, int table_size));

bool Remove(HashTable &hash_table, const char *key, ElemType &value, unsigned int (*Hash)(const char *key, int table_size));

void DelHashTable(HashTable &hash_table);

void TraverseHashTable(HashTable &hash_table, void (*visit)(ElemType v));

double GetASL(HashTable &hash_table, unsigned int (*Hash)(const char *key, int table_size));

使用線性探測法的 Hash ADT 設計

typedef AddList ArrElemType;// 散列單元狀態(tài)類型，分別對應：有合法元素、空單元、有已刪除元素 ?

typedef enum { Legitimate, Empty, Deleted}NodeType;

struct HashNode { char key[MAXKEYLEN]; ArrElemType value;??NodeType type;};

struct ArrayHashTable { int size; int capacity; HashNode *table;};

void InitArrayHashTable(ArrayHashTable &hash_table, int init_capacity);

void DelArrayHashTable(ArrayHashTable &hash_table);

bool IsFull(ArrayHashTable &hash_table);

bool LinearDelete(ArrayHashTable &hash_table, const char *key);

bool LinearGet(ArrayHashTable &hash_table, const char *key, ArrElemType &value);

bool LinearGetNum(ArrayHashTable &hash_table, const char *key, ArrElemType &value, int &num);

int LinearPut(ArrayHashTable &hash_table, const char *key, ArrElemType value, ArrElemType &old_value);

//電話查找系統(tǒng)數(shù)據(jù)類型定義

struct AddList { char phone_num[MAXPHONENUM]; char name[MAXNAME]; char address[MAXADDRESS];

AddList() { } AddList(const char *phone_num, const char *name, const char *address) { strcpy(this->phone_num, phone_num);?

strcpy(this->name, name); strcpy(this->address, address); }};

2.2 功能模塊結(jié)構(gòu)圖
根據(jù)需求分析，為了滿足用戶的功能需求，將系統(tǒng)劃分為以下幾個模塊：Hash 表模塊、查詢記錄模塊、添加記錄模塊、導入記錄模塊、Hash 函數(shù)比較模塊、沖突解決辦法比較模塊。其中 Hash 表模塊包括鏈表實現(xiàn)的 Hash 表子模塊和線性探測法實現(xiàn)的 Hash 表子模塊，查詢記錄模塊包括電話號碼查詢子模塊和姓名查詢子模塊。

圖 1 模塊結(jié)構(gòu)圖

三、運行環(huán)境

硬件環(huán)境：
cpu：Intel? Core? i7-6500U CPU @ 2.50GHz × 4
內(nèi)存：8G
軟件環(huán)境：
OS：Ubuntu 18.04.1 LTS 64位
Linux內(nèi)核：Linux version 4.4.0-17134-Microsoft

完整的源碼和詳細的文檔，上傳到了 【W(wǎng)RITE-BUG數(shù)字空間】，需要的請自?。?br>https://www.writebug.com/code/0c804e39-c792-11ed-a4d9-6479f0e5e323/#