哈希表的设计与实现

哈希表c语言

哈希表的设计与实现

一．正文：

设计哈希表实现电话号码查询系统。基本要求：

1、设每个记录有下列数据项：电话号码、用户名、地址；

2、从键盘输入各记录，分别以电话号码和用户名为关键字建立哈希表；

3、采用再哈希法解决冲突；

4、查找并显示给定电话号码的记录；

5、查找并显示给定用户名的记录。

二．思路：

利用哈希表实现电话号码的查询，利用数据链实现对电话记录的增加和删除。

三．定义函数：

Typedef struct

{

Keytype key;

InfoType date;

Int count;

}

HashTable[MaxSize];

四．概要设计

1．数据结构：

struct Hash

{

int currentSize;

struct HashItem

{

int data;

int tag;

}

table[TableSize];

};

2．基本操作：

void Initiate(struct Hash *h);

//初始化操作；

int FindPos(struct Hash h,int x);

哈希表c语言

//查找一个数据元素的操作；

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)

//置空全部哈希表空间的操作；

五．流程图：

哈希表c语言

六、测试数据： 1、输入0——>hu--->shandong--->13651689952

2、输入0---->xiao--->shandong--->123456789

3、输入1--->7--->13651689952

4、输入1--->8--->hu

5、输入2

6、输入3

7、输入5

8、输入4

9、输入6

哈希表c语言

七．程序源代码：

#include<iostream>

#include<string>

#include<fstream>

using namespace std;

#define NULL 0

unsigned int key;

unsigned int key2;

int *p;

struct node //建节点

{

char name[8],address[20];

char num[11];

node * next;

};

typedef node* pnode;

typedef node* mingzi;

node **phone;

node **nam;

node *a;

void hash(char num[11]) //哈希函数

{

int i = 3;

key=(int)num[2];

while(num[i]!=NULL)

{

key+=(int)num[i];

i++;

}

key=key%20;

}

void hash2(char name[8]) //哈希函数

{

int i = 1;

key2=(int)name[0];

while(name[i]!=NULL)

哈希表c语言

{

key2+=(int)name[i];

i++;

}

key2=key2%20;

}

node* input() //输入节点

{

node *temp;

temp = new node;

temp->next=NULL;

cout<<"输入姓名："<<endl;

cin>>temp->name;

cout<<"输入地址："<<endl;

cin>>temp->address;

cout<<"输入电话："<<endl;

cin>>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 = phone[key]->next;

phone[key]->next=newphone;

newname->next = nam[key2]->next;

nam[key2]->next=newname;

return 0;

}

void create() //新建节点

{

int i;

phone=new pnode[20];

for(i=0;i<20;i++)

{

哈希表c语言

phone[i]=new node;

phone[i]->next=NULL;

}

}

void create2() //新建节点

{

int i;

nam=new mingzi[20];

for(i=0;i<20;i++)

{

nam[i]=new node;

nam[i]->next=NULL;

}

}

void list() //显示列表

{

int i;

node *p;

for(i=0;i<20;i++)

{

p=phone[i]->next;

while(p)

{

cout<<p->name<<'_'<<p->address<<'_'<<p->num<<endl;

p=p->next;

}

}

}

void list2() //显示列表

{

int i;

node *p;

for(i=0;i<20;i++)

{

p=nam[i]->next;

while(p)

{

cout<<p->name<<'_'<<p->address<<'_'<<p->num<<endl;

哈希表c语言

p=p->next;

}

}

}

void find(char num[11]) //查找用户信息

{

hash(num);

node *q=phone[key]->next;

while(q!= NULL)

{

if(strcmp(num,q->num)==0)

break;

q=q->next;

}

if(q)

cout<<q->name<<"_" <<q->address<<"_"<<q->num<<endl; else cout<<"无此记录"<<endl;

}

void find2(char name[8]) //查找用户信息

{

hash2(name);

node *q=nam[key2]->next;

while(q!= NULL)

{

if(strcmp(name,q->name)==0)

break;

q=q->next;

}

if(q)

cout<<q->name<<"_" <<q->address<<"_"<<q->num<<endl; else cout<<"无此记录"<<endl;

}

void save() //保存用户信息

{

int i;

node *p;

for(i=0;i<20;i++)

{

p=phone[i]->next;

哈希表c语言

while(p)

{

fstream iiout("out.txt", ios::out);

iiout<<p->name<<"_"<<p->address<<"_"<<p->num<<endl; p=p->next;

}

}

}

void menu() //菜单

{

cout<<"0.添加记录"<<endl;

cout<<"3.查找记录"<<endl;

cout<<"2.姓名散列"<<endl;

cout<<"4.号码散列"<<endl;

cout<<"5.清空记录"<<endl;

cout<<"6.保存记录"<<endl;

cout<<"7.退出系统"<<endl;

}

int main()

{

char num[11];

char name[8];

create();

create2() ;

int sel;

while(1)

{

menu();

cin>>sel;

if(sel==3)

{ cout<<"9号码查询，8姓名查询"<<endl;

int b;

cin>>b;

if(b==9)

{cout<<"请输入电话号码:"<<endl;

哈希表c语言

cin >>num;

cout<<"输出查找的信息:"<<endl;

find(num);

}

else

{cout<<"请输入姓名:"<<endl;

cin >>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;

}

哈希表c语言

参考文献

[1] 严蔚敏，吴伟名.《数据结构》[M]. 北京：清华大学出版社.2007年.

[2] 张颖江,胡燕.《C语言程序设计》[M]. 北京：科学出版社.1998年.

[3] 殷人昆.《数据结构》[M].北京：清华大学出版社.2001年.

[4] 徐孝凯.《数据结构实用教程》[M].北京：清华大学出版社.1999年.

[5] Adam Drozdek（美）.《数据结构与算法》[M]，北京：机械工业出版社，2003年.