哈希表实现电话号码查询 源程序

1、哈希表存储的电话号码查询设每个记录有以下数据项：用户名、电话、地址；从键盘输入各记录，以电话号码为关键字建立哈希表；采用链地址法方法解决冲突；能够查找并显示给定电话号码的相关记录。#include #include #include #include #define MAX_LEN 60/ 学生信息类class Studentprivate:char _nameMAX_LEN;/ 姓名char _phoneMAX_LEN;/ 电话char _addrMAX_LEN;/ 地址public:Student();const char* getName() ; /变量不允许被改变const char*

2、 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_LEN);const char* Student:getName()return _name;const char* Student:getPhone()return _p

3、hone;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* addr)strcpy(this-_addr,addr);/哈希节点struct LISTNODEint n_value ;/ int count;/ 保存的个数char _phone

4、MAX_LEN ;/ keyStudent _info;/ 学生信息LISTNODE * p_next ;/ 下一个结点的地址;/哈希表结构定义struct HASHTABLEint n_tablesize ;LISTNODE * p_node ;/ 哈希表管理类class CHashTableManageprivate:HASHTABLE *_hashTable;/ 哈希首地址public:CHashTableManage();bool hashtable_init( int table_size);/初始化void hashtable_clear ();/清理/拿到这个字符串存在的节点LI

5、STNODE * hashtable_find( char *phone);/ 插入一个结点int hashtable_insert (LISTNODE * pNode);protected:LISTNODE * CHashTableManage:hashtable_newnode( LISTNODE* str);/哈希函数/得到字符串在哈希表中的位置int hashtable_hash (char* str, int tablesize);/CHashTableManage:CHashTableManage(): _hashTable(0)/初始化bool CHashTableManage:

6、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;/链表队列一条链为一个散列位置head_ht-p_node = (LISTNODE *) new inttable_size;/每一个散列链初始化for(int i=0; in_tablesize; i+)head_ht-p_nodei =

7、NULL;_hashTable = head_ht;return true ;/清理void CHashTableManage:hashtable_clear () /0if(_hashTable = NULL)return;/每一个散列链freefor(int i=0; in_tablesize; i+)if(_hashTable -p_node i)LISTNODE *list = _hashTable-p_nodei;/当前链表不空while(list != NULL)/取得下一个LISTNODE *tempnode = list- p_next;/free当前位置if(list )de

8、lete list ;/指向下一个list = tempnode ;/链表队列freeif(_hashTable -p_node)delete(_hashTable -p_node);_hashTable-p_node = NULL;/哈希头节点freeif(_hashTable )delete(_hashTable );_hashTable = NULL ;/拿到这个字符串存在的节点LISTNODE * CHashTableManage:hashtable_find( char *phone) /2/哪一条链表LISTNODE * list = NULL;if(_hashTable = NU

9、LL)return NULL ;int pos = hashtable_hash(phone,_hashTable- n_tablesize);list = _hashTable -p_nodepos;/链表查找while(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

10、-_phone,_hashTable -n_tablesize);LISTNODE *list_pos = _hashTable- p_nodepos;/假如存在 计数器+1for(;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& str

11、cmp(pNode-_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 tablesize)unsigned int h

12、ash_val = 0;while(*str != 0)hash_val += (hash_val p_next = 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

13、(1001);if(!_manage.hashtable_init(1001)cout 哈希初始化失败 endl;return 1;cout * endl;cout endl; cout endl;cout endl;cout endl;cout 按任意键开始 endl;cout * endl;getchar();while(1)system(cls);cout . endl;cout . 添加学生信息 . endl;cout . 查询学生信息 . endl; cout . 退出 . endl; cout . endl;char key = getchar();switch(key)case

14、1:LISTNODE info;char bufMAX_LEN;memset(&info,0,sizeof(info);cout - 请输入学生信息姓名 buf;info._info.setName(buf);cout - 请输入学生信息电话 buf;info._info.setPhone(buf);cout - 请输入学生信息地址 buf;info._info.setAddr(buf);strcpy(info._phone,info._info.getPhone();_manage.hashtable_insert(&info);cout - 恭喜 写入成功！ 按任意键确认 endl;getchar();break;case 2:cout - 请输入查询条件电话 buf;/找到这个字符串具体位置LISTNODE * node = _manage.hashtable_find(buf);if(node = 0)cout - 没有查询到相关数据！ 按任意键确认 endl;elsecout - 查询到以下数据 - endl;while(node != NULL)cout - endl;cout - 相同信息数：count endl;cout - 学生姓名 ：_info.getName() endl;cout - 电话号码 ：_info.get