用C编程 设计一哈希表

为班级30个人的姓名设计一个哈希表,假设姓名用汉语拼音表示。(关键字可视为拼音首字母的序号)要求用除留余数法构造哈希函数,用线性探测再散列法处理冲突,平均查找长度的上限是2。
大家帮帮忙,怎么设计程序?

以下是我用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=0;i<q;i++)
{
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=0;i<n;i++)
{
hashlist[i].py="";
hashlist[i].k=0;
hashlist[i].si=0;
}
for(i=0;i<M;i++)
{
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=0;r<20;r++)
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=0;i<30;i++)
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;
}
温馨提示:答案为网友推荐,仅供参考
第1个回答  2016-01-06
用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=0;i<q;i++)
{
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=0;i<n;i++)
{
hashlist[i].py="";
hashlist[i].k=0;
hashlist[i].si=0;
}
for(i=0;i<M;i++)
{
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=0;r<20;r++)
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=0;i<30;i++)
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;
}
第2个回答  2010-06-01
Aɑ ㄚ
Bb ㄅㄝ
Cc ㄘㄝ
Dd ㄉㄝ
Ee ㄜ
Ff ㄝㄈ
Gɡ ㄍㄝ
Hh ㄏㄚ
Ii ㄧ
Jj ㄐㄧㄝ
Kk ㄎㄝ
Ll ㄝㄌ
Mm ㄝㄇ
字母 名称
Nn ㄋㄝ
Oo ㄛ
Pp ㄆㄝ
Qq ㄑㄧㄡ
Rr ㄚㄦ
Ss ㄝㄙ
Tt ㄊㄝ
Uu ㄨ
Vv ㄞㄝ
Ww ㄨㄚ
Xx ㄒㄧ
Yy ㄧㄚ
Zz ㄗㄝ

二、声母表

b p m f d t n l
ㄅ玻 ㄆ坡 ㄇ摸 ㄈ佛 ㄉ得 ㄊ特 ㄋ讷 ㄌ勒
ɡ k h j q x
ㄍ哥 ㄎ科 ㄏ喝 ㄐ基 ㄑ欺 ㄒ希
zh ch sh r z c s
ㄓ知 ㄔ蚩 ㄕ诗 ㄖ日 ㄗ资 ㄘ雌 ㄙ思

三、韵母表

i
ㄧ 衣 u
ㄨ 乌 ü
ㄩ 迂
ɑ
ㄚ 啊 iɑ
ㄧㄚ 呀 uɑ
ㄨㄚ 蛙
o
ㄛ 喔 uo
ㄨㄛ 窝
e
ㄜ 鹅 ie
ㄧㄝ 耶 eü
ㄩㄝ约
ɑi
ㄞ 哀 uɑi
ㄨㄞ 歪
ei
ㄟ 诶 uei
ㄨㄟ 威
ɑo
ㄠ 熬 iɑo
ㄧㄠ 腰
ou
ㄡ 欧 iou
ㄡ 忧
ɑn
ㄢ 安 iɑn
ㄧㄢ 烟 uɑn
ㄨㄢ 弯 üɑn
ㄩㄢ 冤
en
ㄣ 恩 in
ㄧㄣ 因 uen
ㄨㄣ 温 ün
ㄩㄣ 晕
ɑnɡ
ㄤ 昂 iɑnɡ
ㄧㄤ 央 uɑnɡ
ㄨㄤ 汪
enɡ
ㄥ 亨的韵母 inɡ
ㄧㄥ 英 uenɡ
ㄨㄥ 翁
onɡ
ㄨㄙ轰的韵母 ionɡ
ㄩㄥ 雍

(1)"知、蚩、诗、日、资、雌、思”等字的韵母用i。

(2)韵母ㄦ写成er,用做韵尾的时候写成r。

(3)韵母ㄝ单用的时候写成ê。

(4)i 行的韵母,前面没有声母的时候,写成yi(衣), yɑ(呀), ye(耶), yɑo(腰),you(忧),yɑn(烟),yin(因),yɑnɡ(央),yinɡ(英),yonɡ(雍)。u 行的韵母,前面没有声母的时候,写成wu(乌), wɑ(蛙), wo(窝), wɑi(歪),wei(威),wɑn(弯),wen(温),wɑnɡ(汪),wenɡ(翁)ü 行的韵母跟声母j,q,x拼的时候,写成ju(居),qu(区),xu(虚),ü上两点也省略;但是跟声母l,n拼的时候,仍然写成lü(吕),nü(女)。

(5)iou,uei,uen前面加声母的时候,写成iu,ui,un,例如niu(牛),ɡui(归),lun(论)。

四、声调符号

阴平 阳平 上声 去声
� � ∨ �

声调符号标在音节的主要母音上。轻声不标。

例如:

妈 mā 麻 má 马 mǎ 骂 mà 吗 mɑ
阴平 阳平 上声 去声 轻声

五、隔音符号

ɑ,o,e开头的音节连接在其它音节后面的时候,如果音节的界限发生混淆,用隔音符号(')隔开,例如pi'ɑo(皮袄)。