1、數據結構課 程 設 計 報 告 書題 目：哈希表存儲的電話號碼查詢專 業： 學 號： 學生姓名： 指導教師： 完成日期： 目錄1. 實訓題目1.1實訓要求. 1.2需求分析.2. 系統設計2.1總體設計.2.2詳細設計.2.2.1程序頭文件.2.2.2學生信息類及哈希表類.2.2.3主函數流程.3.系統實現.3.1編碼.3.2測試.4.歸納總結. 4.1實訓中遇到的問題以及解決辦法. 4.2感想和心得體會.5.參考資料1. 實訓題目1.1實訓要求n 設每個記錄有以下數據項：用戶名、電話、地址；n 從鍵盤輸入各記錄，以電話號碼為關鍵字建立哈希表；n 采用鏈地址法方法解決沖突；n 能夠查找并顯示給

2、定電話號碼的相關記錄。1.2需求分析 本次實驗要求采用哈希表完成信息的查找和儲存，哈希表即為散列表。本程序采用學生信息管理為例，設每個學生有電話號碼，學生姓名，家庭住址三個信息。通過建立哈希表儲存信息，信息儲存在節點中，并通過以電話號碼為關鍵字完成查找，并顯示出該學生的姓名，電話號碼以及家庭住址。當哈希表中的數據與輸入的數據發生沖突時，使用節點向后移一位的方法來解決沖突。2. 系統設計2.1 總體設計本系統通過設計學生信息類和哈希表類來完成整個系統。通過學生信息類實現從鍵盤輸入學生的姓名，電話號碼以及家庭地址。將學生的信息儲存在建立的哈希節點內，通過多個鏈表保存，相同信息的保存在同一個節點內。

3、然后通過以電話號碼為關鍵字建立哈希表。當輸入的信息與表內儲存的信息發生沖突時，通過建立新的節點并向后移一位的方法來解決沖突。系統界面2.2 詳細設計首先初始化哈希表，并建立新的節點（哈希表的容量不能大于1001，否則哈希表初始化失?。?，從鍵盤輸入學生的姓名，電話號碼以及家庭住址，所輸入的變量無法被改變。然后將建立的節點插入哈希表里。2.2.1程序頭文件#include <iostream.h>#include <stdlib.h>#include <cstdio>#include <sstream>#define MAX_LEN 602.2.2學

4、生信息類及哈希表類學生信息類（其中輸入的信息無法改變）class Studentprivate:char _nameMAX_LEN;/ 姓名char _phoneMAX_LEN;/ 電話char _addrMAX_LEN;/ 地址public:Student();const char* getName() ; /變量不允許被改變const char* getPhone();const char* getAddr();void setName(const char* name);void setPhone(const char* phone);void setAddr(const char* a

5、ddr);哈希表類其中含有初始化哈希表函數，清空函數，插入節點函數，獲取節點位置函數組成。class CHashTableManageprivate:HASHTABLE *_hashTable;/ 哈希首地址public:CHashTableManage();bool hashtable_init( int table_size);/初始化void hashtable_clear ();/清理/拿到這個字符串存在的節點LISTNODE * hashtable_find( char *phone);/ 插入一個結點int hashtable_insert (LISTNODE * pNode);p

6、rotected:LISTNODE * CHashTableManage:hashtable_newnode( LISTNODE* str);/哈希函數/得到字符串在哈希表中的位置int hashtable_hash (char* str, int tablesize);哈希節點結構體為：struct LISTNODEint n_value ;/ int count;/ 保存的個數char _phoneMAX_LEN ;/ keyStudent _info;/ 學生信息LISTNODE * p_next ;/ 下一個結點的地址;哈希表結構體為：struct HASHTABLEint n_tab

7、lesize ;LISTNODE * p_node ;2.2.3主函數流程主函數main()初始化哈希表插入學生信息檢測沖突，如果沖突則將插入信息的節點向后移一位查詢關鍵字并顯示查詢結果結束3. 系統實現3.1編碼頭文件#include <iostream.h>#include <stdlib.h>#include <cstdio>#include <sstream>#define MAX_LEN 60學生信息類class Studentprivate:char _nameMAX_LEN;/ 姓名char _phoneMAX_LEN;/ 電話ch

8、ar _addrMAX_LEN;/ 地址public:Student();const char* getName() ; /變量不允許被改變const char* getPhone();const char* getAddr();void setName(const char* name);void setPhone(const char* phone);void setAddr(const char* addr);學生信息表Student:Student()memset(_name,0,MAX_LEN);memset(_phone,0,MAX_LEN);memset(_addr,0,MAX_

9、LEN);const char* Student:getName()return _name;const char* Student:getPhone()return _phone;const char* Student:getAddr()return _addr;void Student:setName(const char* name)strcpy(this->_name,name);void Student:setPhone(const char* phone)strcpy(this->_phone,phone);void Student:setAddr(const char

10、* addr)strcpy(this->_addr,addr);/哈希節點，建立數據存儲的節點struct LISTNODEint n_value ;/ int count;/ 保存的個數char _phoneMAX_LEN ;/ keyStudent _info;/ 學生信息LISTNODE * p_next ;/ 下一個結點的地址;/哈希表結構定義struct HASHTABLEint n_tablesize ;LISTNODE * p_node ; 哈希表管理類class CHashTableManageprivate:HASHTABLE *_hashTable;/ 哈希首地址pu

11、blic:CHashTableManage();bool hashtable_init( int table_size);/初始化void hashtable_clear ();/清理拿到字符串存在的節點LISTNODE * hashtable_find( char *phone);/ 插入一個結點int hashtable_insert (LISTNODE * pNode);protected:LISTNODE * CHashTableManage:hashtable_newnode( LISTNODE* str);/哈希函數/得到字符串在哈希表中的位置int hashtable_hash

12、(char* str, int tablesize);/CHashTableManage:CHashTableManage(): _hashTable(0)初始化哈希表，建立一個散列表bool CHashTableManage:hashtable_init( int table_size)/表頭HASHTABLE * head_ht ;head_ht = (HASHTABLE *)new( HASHTABLE );if(head_ht = NULL)return false ;/元素總數盡量素數保證mod盡可能均勻head_ht->n_tablesize = table_size;/鏈表

13、隊列一條鏈為一個散列位置head_ht->p_node = (LISTNODE *) new inttable_size;/每一個散列鏈初始化for(int i=0; i<head_ht ->n_tablesize; i+)head_ht->p_nodei = NULL;_hashTable = head_ht;return true ;/清理void CHashTableManage:hashtable_clear () /0if(_hashTable = NULL)return;/每一個散列鏈freefor(int i=0; i<_hashTable ->

14、;n_tablesize; i+)if(_hashTable ->p_node i)LISTNODE *list = _hashTable->p_nodei;/當前鏈表不空while(list != NULL)/取得下一個LISTNODE *tempnode = list-> p_next;/free當前位置if(list )delete list ;/指向下一個list = tempnode ;鏈表隊列freeif(_hashTable ->p_node)delete(_hashTable ->p_node);_hashTable->p_node = NU

15、LL;哈希頭節點freeif(_hashTable )delete(_hashTable );_hashTable = NULL ;/拿到這個字符串存在的節點LISTNODE * CHashTableManage:hashtable_find( char *phone) /2/哪一條鏈表LISTNODE * list = NULL;if(_hashTable = NULL)return NULL ;int pos = hashtable_hash(phone,_hashTable-> n_tablesize);list = _hashTable ->p_nodepos;/鏈表查找w

16、hile(list != NULL)if(strcmp(phone, list->_phone) = 0) /比較break;list = list ->p_next;return list ;/插入一個新的結點int CHashTableManage:hashtable_insert (LISTNODE * pNode) /1int pos = hashtable_hash( pNode->_phone,_hashTable ->n_tablesize);LISTNODE *list_pos = _hashTable-> p_nodepos;將插入的節點與哈希表

17、內的節點比較，如有沖突則將插入的節點向表后移一位for(;list_pos!=NULL;list_pos=list_pos->p_next)if(strcmp(list_pos->_phone,pNode->_phone) = 0&& strcmp(pNode->_info.getPhone(),list_pos->_info.getPhone() = 0&& strcmp(pNode->_info.getAddr(),list_pos->_info.getAddr() = 0&& strcmp(pNod

18、e->_info.getName(),list_pos->_info.getName() = 0)list_pos->count+;return pos;/不存在LISTNODE *node = hashtable_newnode(pNode);node->p_next = _hashTable-> p_nodepos;_hashTable-> p_nodepos = node;return pos ;/哈希函數/得到字符串在哈希表中的位置int CHashTableManage:hashtable_hash (char* str, int tablesiz

19、e)unsigned int hash_val = 0;while(*str != '0')hash_val += (hash_val << 5) + *str+;int pos = hash_val % tablesize;return pos ;/得到新一個新節點LISTNODE * CHashTableManage:hashtable_newnode( LISTNODE* str)/插入節點初始化LISTNODE *insert_node =(LISTNODE*) malloc(sizeof (LISTNODE);insert_node->p_next

20、= NULL;insert_node->count = 1;strcpy(insert_node ->_phone, str->_info.getPhone();memcpy(&insert_node->_info,&str->_info,sizeof(str->_info);return insert_node ;/主函數int main (void)CHashTableManage _manage;/初始一個個鏈表的哈希表 size最好為素數/head = hashtable_init (1001);if(!_manage.hashtab

21、le_init(1001)cout << "哈希初始化失敗"<< endl;return 1;cout << "* " << endl;cout << "<<<<<<<<<< 學生信息管理（哈希表實現） >>>>>>>>>>" << endl; cout << " <<<<<<<&l

22、t;<< >>>>>>>>>> " << endl;cout << " <<<<<<<<<< >>>>>>>>>> " << endl;cout << " <<<<<<<<<< >>>>>>>>>>

23、" << endl;cout << " 按任意鍵開始 " << endl;cout << "*" << endl;getchar();while(1)system("cls");cout << "." <<endl;cout << ". <1> 添加學生信息 ." <<endl;cout << ". <2> 查詢學生信息 ."

24、; << endl; cout << ". <0> 退出 ." <<endl; cout << "." <<endl;char key = getchar();switch(key)case '1':LISTNODE info;char bufMAX_LEN;memset(&info,0,sizeof(info);cout << "- 請輸入學生信息姓名" << endl;cin >> buf;info.

25、_info.setName(buf);cout << "- 請輸入學生信息電話" << endl;cin >> buf;info._info.setPhone(buf);cout << "- 請輸入學生信息地址" << endl;cin >> buf;info._info.setAddr(buf);strcpy(info._phone,info._info.getPhone();_manage.hashtable_insert(&info);cout << &qu

26、ot;- 恭喜 寫入成功！ 按任意鍵確認" <<endl;getchar();break;case '2':cout << "- 請輸入查詢條件電話" << endl;char bufMAX_LEN;cin >> buf;/找到這個字符串具體位置LISTNODE * node = _manage.hashtable_find(buf);if(node = 0)cout << "- 沒有查詢到相關數據！ 按任意鍵確認" << endl;elsecout <

27、;< "- 查詢到以下數據 -" << endl;while(node != NULL)cout << "-" << endl;cout << "- 相同信息數："<<node->count << endl;cout << "- 學生姓名 ："<< node->_info.getName() << endl;cout << "- 電話號碼 ："<< node->_info.getPhone() << endl;cout << "- 學生地址 ："<<