哈希表的设计与实现.doc

哈希表的设计与实现一正文： 设计哈希表实现电话号码查询系统。基本要求： 1、设每个记录有下列数据项：电话号码、用户名、地址； 2、从键盘输入各记录，分别以电话号码和用户名为关键字建立哈希表； 3、采用再哈希法解决冲突； 4、查找并显示给定电话号码的记录； 5、查找并显示给定用户名的记录。 二思路：利用哈希表实现电话号码的查询，利用数据链实现对电话记录的增加和删除。三定义函数：Typedef struct Keytype key; InfoType date; Int count;HashTableMaxSize;四概要设计1数据结构：struct Hashint currentSize;struct HashItemint data;int tag;tableTableSize;2基本操作：void Initiate(struct Hash *h);/初始化操作；int FindPos(struct Hash h,int x);/查找一个数据元素的操作；int GetValue(struct Hash h,int i);/获取一个数据元素的操作；int Insert(struct Hash *h,int x);/插入一个数据元素的操作；int Delete(struct Hash *h,int x);/删除一个数据元素的操作；void Print(struct Hash h);/列表显示数据元素的操作；void Clear(struct Hash *h)/置空全部哈希表空间的操作；五流程图： 六、测试数据：1、输入0hu-shandong-136516899522、输入0-xiao-shandong-1234567893、输入1-7-136516899524、输入1-8-hu5、输入26、输入37、输入58、输入49、输入6七程序源代码：#include#include #includeusing namespace std; #define NULL 0 unsigned int key; unsigned int key2; int *p; struct node /建节点 char name8,address20; char num11; node * next; ; typedef node* pnode; typedef node* mingzi; node *phone; node *nam; node *a; void hash(char num11) /哈希函数 int i = 3; key=(int)num2; while(numi!=NULL) key+=(int)numi; i+; key=key%20; void hash2(char name8) /哈希函数 int i = 1; key2=(int)name0; while(namei!=NULL) key2+=(int)namei; i+; key2=key2%20; node* input() /输入节点 node *temp; temp = new node; temp-next=NULL; cout输入姓名：temp-name; cout输入地址：temp-address; cout输入电话：temp-num; return temp; int apend() /添加节点 node *newphone; node *newname; newphone=input(); newname=newphone; newphone-next=NULL; newname-next=NULL; hash(newphone-num); hash2(newname-name); newphone-next = phonekey-next; phonekey-next=newphone; newname-next = namkey2-next; namkey2-next=newname; return 0; void create() /新建节点 int i; phone=new pnode20; for(i=0;inext=NULL; void create2() /新建节点 int i; nam=new mingzi20; for(i=0;inext=NULL; void list() /显示列表 int i; node *p; for(i=0;inext; while(p) coutname_address_numnext; void list2() /显示列表 int i; node *p; for(i=0;inext; while(p) coutname_address_numnext; void find(char num11) /查找用户信息 hash(num); node *q=phonekey-next; while(q!= NULL) if(strcmp(num,q-num)=0) break; q=q-next; if(q) coutname_ address_numendl; else cout无此记录next; while(q!= NULL) if(strcmp(name,q-name)=0) break; q=q-next; if(q) coutname_ address_numendl; else cout无此记录endl; void save() /保存用户信息 int i; node *p; for(i=0;inext; while(p) fstream iiout(out.txt, ios:out); iioutname_address_numnext; void menu() /菜单 cout0.添加记录endl; cout3.查找记录endl; cout2.姓名散列endl; cout4.号码散列endl; cout5.清空记录endl; cout6.保存记录endl; cout7.退出系统sel; if(sel=3) cout9号码查询，8姓名查询b; if(b=9) cout请输入电话号码:num; cout输出查找的信息:endl; find(num); else cout请输入姓名:name; cout输出查找的信息:endl; find2(name); if(sel=2) cout姓名散列结果:endl; list2(); if(sel=0) cout请输入要添加的内容:endl; apend(); if(sel=4) cout号码散列结果:endl; list(); if(sel=5) cout列表已清空:endl; create();create2(); if(sel=6) cout通信录已保存:endl; save(); if(sel=7) return 0; return 0; 参考文献1 严蔚敏，吴伟名.数据结构M. 北京：清华大