C语言哈希表

/#include "iostream.h"

#include <iostream>

#include "string.h"

#include "fstream"

#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

using namespace std//使用名称空间

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)

{

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=0i<20i++)

{

phone[i]=new node

phone[i]->next=NULL

}

}

void create2() //新建节点

{

int i

nam=new mingzi[20]

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

{

nam[i]=new node

nam[i]->next=NULL

}

}

void list() //显示列表

{

int i

node *p

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

{

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=0i<20i++)

{

p=nam[i]->next

while(p)

{

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

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=0i<20i++)

{

p=phone[i]->next

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

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

}

#define MaxSize 100 //定义最大哈希表长度

#define NULLKEY -1 //定义空关键字值

#define DELKEY -2 //定义被删关键字值

typedef int KeyType //关键字类型

typedef char * InfoType //其他数据类型

typedef struct

{

KeyType key //关键字域

InfoType data //其他数据域

int count //探查次数域

} HashData

typedef HashData HashTable[MaxSize] //哈希表类型

void InsertHT(HashTable ha,int &n,KeyType k,int p) //将关键字k插入到哈希表中

{

int i,adr

adr=k % p

if (ha[adr].key==NULLKEY || ha[adr].key==DELKEY)//x[j]可以直接放在哈希表中

{

ha[adr].key=k

ha[adr].count=1

}

else//发生冲突时采用线性探查法解决冲突

{

i=1 //i记录x[j]发生冲突的次数

do

{

adr=(adr+1) % p

i++

}

while (ha[adr].key!=NULLKEY &&ha[adr].key!=DELKEY)

ha[adr].key=k

ha[adr].count=i

}

n++

}

void CreateHT(HashTable ha,KeyType x[],int n,

以下是我用C++编的一个程序，仅供参考！

#include<iostream>

#include<string>

using namespace std

#define M 47 //随机数

#define n 50 //哈希表长

#define q 30 //人数

struct name{

char *py

int k

}

name NameList[n]

struct hash{

char *py

int k

int si

}

hash hashlist[n]

void listname()

{

char *f

int s0,r,i

NameList[0].py="baojie"

NameList[1].py="chengaoyang"

NameList[2].py="chenguangzhong"

NameList[3].py="chenliangliang"

NameList[4].py="chenyongzhou"

NameList[5].py="fengchao"

NameList[6].py="gexiangfeng"

NameList[7].py="huting"

NameList[8].py="huangpinjin"

NameList[9].py="jiangxiaojia"

NameList[10].py="laidongjie"

NameList[11].py="liyexiao"

NameList[12].py="lidaohui"

NameList[13].py="lijue"

NameList[14].py="lizhuoqun"

NameList[15].py="linfujun"

NameList[16].py="luobin"

NameList[17].py="luokeqing"

NameList[18].py="nichao"

NameList[19].py="panhuafeng"

NameList[20].py="sijun"

NameList[21].py="songzhanhui"

NameList[22].py="sunzhengqing"

NameList[23].py="wanghaofeng"

NameList[24].py="wangjunshuai"

NameList[25].py="wangqinde"

NameList[26].py="wangzejun"

NameList[27].py="wangkeke"

NameList[28].py="weixing"

NameList[29].py="wurenke"

for(i=0i<qi++)

{

s0=0

f=NameList[i].py

for(r=0*(f+r)!='\0'r++)

s0+=*(f+r)

NameList[i].k=s0

}

}

void creathash()

{

int i

for(i=0i<ni++)

{

hashlist[i].py=""

hashlist[i].k=0

hashlist[i].si=0

}

for(i=0i<Mi++)

{

int sum=0

int adr=(NameList[i].k)%M

int d=adr

if(hashlist[adr].si==0)

{

hashlist[adr].k=NameList[i].k

hashlist[adr].py=NameList[i].py

hashlist[adr].si=1

}

else

{

while(hashlist[d].k!=0)

{

d=(d+NameList[i].k%10+1)%M

sum=sum+1

}

hashlist[d].k=NameList[i].k

hashlist[d].py=NameList[i].py

hashlist[d].si=sum+1

}

}

}

void findlist()

{

string nam

int s0=0,r,sum=1

cout<<"请输入姓名的拼音："<<endl

cin>>nam

for(r=0r<20r++)

s0+=nam[r]

int adr=s0%M

int d=adr

if(hashlist[adr].k==s0)

cout<<"姓名："<<hashlist[adr].py<<" "<<"关键字："<<s0<<" "<<"查找长度为：1"<<endl

else if(hashlist[adr].k==0)

cout<<"无此记录！"<<endl

else

{

int g=0

while(g==0)

{

d=(d+s0%10+1)%M

sum=sum+1

if(hashlist[d].k==0)

{cout<<"无此记录！"<<endl

g=1

}

if(hashlist[d].k==s0)

{

cout<<"姓名："<<hashlist[adr].py<<" "<<"关键字："<<s0<<" "<<"查找长度为：1"<<endl

g=1

}

}

}

}

void display()

{

int i

for(i=0i<30i++)

cout<<NameList[i].py<<" "<<NameList[i].k<<endl

}

int main()

{

char x

listname()

creathash()

cout<<"d. 显示哈希表 f.查找 任意键退出 请选择"<<endl

while(cin>>x)

{

if(x=='d'){display()cout<<endl}

else if(x=='f'){findlist()cout<<endl}

else break

}

return 0

}

---