哈希造表: 为某个集体"人名"设计一个哈希表,平均查找长度不超过2,假设30个待填入的人名为拼音形式.

Question

哈希函数用初留余数法构造,用伪随机探测再散列法处理冲突. 编写代码实现表的构造及实现查询.
(用数据结构,C语言编写)

Answer 1

这个是我们的作业 ^^根据自己的需要改一下就行了
#include <stdio.h>
#include<malloc.h>
#include<string.h>
//#include
#define HASH_LEN 50 //哈希表的长度
#define M 47
#define NAME_NO 30 //人名的个数
typedef struct NAME
{
char *py; //名字的拼音
int k; //拼音所对应的整数
}NAME;
NAME NameList[HASH_LEN];

typedef struct hterm //哈希表
{
char *py; //名字的拼音
int k; //拼音所对应的整数
int si; //查找长度
}HASH;
HASH HashList[HASH_LEN];
/*-----------------------姓名（结构体数组）初始化---------------------------------*/
void InitNameList()
{
NameList[0].py="chenghongxiu";
NameList[1].py="yuanhao";
NameList[2].py="yangyang";
NameList[3].py="zhanghen";
NameList[4].py="chenghongxiu";
NameList[5].py="xiaokai";
NameList[6].py="liupeng";
NameList[7].py="shenyonghai";
NameList[8].py="chengdaoquan";
NameList[9].py="ludaoqing";
NameList[10].py="gongyunxiang";
NameList[11].py="sunzhenxing";
NameList[12].py="sunrongfei";
NameList[13].py="sunminglong";
NameList[14].py="zhanghao";
NameList[15].py="tianmiao";
NameList[16].py="yaojianzhong";
NameList[17].py="yaojianqing";
NameList[18].py="yaojianhua";
NameList[19].py="yaohaifeng";
NameList[20].py="chengyanhao";
NameList[21].py="yaoqiufeng";
NameList[22].py="qianpengcheng";
NameList[23].py="yaohaifeng";
NameList[24].py="bianyan";
NameList[25].py="linglei";
NameList[26].py="fuzhonghui";
NameList[27].py="huanhaiyan";
NameList[28].py="liudianqin";
NameList[29].py="wangbinnian";

char *f;
int r,s0;

for (int i=0;i<NAME_NO;i++)// 求出各个姓名的拼音所对应的整数
{
s0=0;
f=NameList[i].py;

for (r=0;*(f+r) != '\0';r++) //方法：将字符串的各个字符所对应的ASCII码相加，所得的整数做为哈希表的关键字
s0=*(f+r)+s0;

NameList[i].k=s0;
}
}
/*-----------------------建立哈希表---------------------------------*/
void CreateHashList()
{
for (int i=0; i<HASH_LEN;i++)//哈希表的初始化
{
HashList[i].py="";
HashList[i].k=0;
HashList[i].si=0;
}

for (i=0; i<NAME_NO;)
{
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 //冲突
{
do
{
d=(d+((NameList[i].k))%10+1)%M; //伪散列
sum=sum+1; //查找次数加1
}while (HashList[d].k!=0);

HashList[d].k=NameList[i].k;
HashList[d].py=NameList[i].py;
HashList[d].si=sum+1;
}i++;
}
}

/*-------------------------------------查找------------------------------------*/
void FindList()
{
printf("\n\n请输入姓名的拼音: "); //输入姓名
char name[20]={0};
scanf("%s",name);

int s0=0;
for (int r=0;r<20;r++) //求出姓名的拼音所对应的整数(关键字)
s0+=name[r];

int sum=1;
int adr=s0 % M; //使用哈希函数
int d=adr;

if(HashList[adr].k==s0) //分3种情况进行判断
printf("\n姓名:%s 关键字:%d 查找长度为: 1",HashList[d].py,s0);
else if (HashList[adr].k==0)
printf("无该记录!");
else
{
int g=0;
do
{
d=(d+s0%10+1)%M; //伪散列
sum=sum+1;
if (HashList[d].k==0)
{
printf("无记录! ");
g=1;
}
if (HashList[d].k==s0)
{
printf("\n姓名:%s 关键字:%d 查找长度为:%d",HashList[d].py,s0,sum);
g=1;
}
}while(g==0);
}
}

/*--------------------------------显示哈希表----------------------------*/
void Display()
{
printf("\n\n地址\t关键字\t\t搜索长度\tH(key)\t\t拼音 \n"); //显示的格式
for(int i=0; i<15; i++)
{
printf("%d ",i);
printf("\t%d ",HashList[i].k);
printf("\t\t%d ",HashList[i].si);
printf("\t\t%d ",(HashList[i].k)%M);
printf("\t %s ",HashList[i].py);
printf("\n");
}
// printf("按任意键继续显示...\n"); //由于数据比较多，所以分屏显示（以便在Win9x／DOS下能看到所有的数据）
// getch();
for( i=15; i<30; i++)
{
printf("%d ",i);
printf("\t%d ",HashList[i].k);
printf("\t\t%d ",HashList[i].si);
printf("\t\t%d ",(HashList[i].k)%M);
printf("\t %s ",HashList[i].py);
printf("\n");
}
// printf("按任意键继续显示...\n");
// getch();
for( i=30; i<40; i++)
{
printf("%d ",i);
printf("\t%d ",HashList[i].k);
printf("\t\t%d ",HashList[i].si);
printf("\t\t%d ",(HashList[i].k)%M);
printf("\t %s ",HashList[i].py);
printf("\n");
}
//printf("按任意键继续显示...\n");
//getch();
for( i=40; i<50; i++)
{
printf("%d ",i);
printf("\t%d ",HashList[i].k);
printf("\t\t%d ",HashList[i].si);
printf("\t\t%d ",(HashList[i].k)%M);
printf("\t %s ",HashList[i].py);
printf("\n");
}

float average=0;
for (i=0;i<HASH_LEN;i++)
average+=HashList[i].si;
average/=NAME_NO;
printf("\n\n平均查找长度：ASL(%d)=%f \n\n",NAME_NO,average);
}

/*--------------------------------主函数----------------------------*/
void main()
{
/* ::SetConsoleTitle("哈希表操作"); //Windows API函数,设置控制台窗口的标题
HANDLE hCon = ::GetStdHandle(STD_OUTPUT_HANDLE); //获得标准输出设备的句柄
::SetConsoleTextAttribute(hCon, 10|0); //设置文本颜色
*/
printf("\n------------------------哈希表的建立和查找----------------------");
InitNameList();
CreateHashList ();

while(1)
{
printf("\n\n");
printf(" 1. 显示哈希表\n");
printf(" 2. 查找\n");
printf(" 3. 退出\n");

err:
char ch1;
scanf("%c",&ch1);
if (ch1=='1')
Display();
else if (ch1=='2')
FindList();
else if (ch1=='3')
return;
else
{
printf("\n请输入正确的选择!");
goto err;
}
}
}

Answer 2

下面只是参考
#include <stdio.h>
#include <conio.h>
#include <ctype.h>
#define L 50 /*定义哈希表长*/
#define M 47 /*定义p值*/
#define N 30 /*定义名单长*/
char z[22];
struct old{char *name;char *py;int k;};
struct old oldlist[L];/*原始表*/
struct hterm
{ char *name;char *py;
struct hterm hlist[L];/*哈希表*/
int i,adr,sum,d;
char ch1;
float average;
/**********************************/
void chash()
{for (i=0;i<L;i++)
{hlist[i].name="";
hlist[i].py="";
hlist[i].k=0;
hlist[i].si=0;
for (i=0;i<N;i++)
adr=(oldlist[i].k)%M;
d=adr;
if(hlist[adr].si==0)
{hlist[adr].k=oldlist[i].k;
hlist[adr].name=oldlist[i].name;
hlist[adr].py=oldlist[i].py;
hlist[adr].si=1;
{do
{d=(d+((oldlist[i].k))%10+1)%M;/*伪随机*/
sum=sum+1;
while (hlist[d].k!=0);
hlist[d].k=oldlist[i].k;
hlist[d].name=oldlist[i].name;
hlist[d].py=oldlist[i].py;
hlist[d].si=sum+1;
/***************************************/
void findhlist()
{ int s0;char r,g;
clrscr();/*清屏*/
for (r=0;r<20;r++){z[r]=0;};
gotoxy(1,1);printf("RESEARCH.....");
gotoxy(5,10);printf("input the spell of name: ");
gotoxy(5,12);scanf("%s",z);
s0=0;
for (r=0;r<20;r++){s0=z[r]+s0;};
gotoxy(5,13); printf("%d",s0);
/*for (i=0;i<L;i++)*/
sum=1;
adr=s0%M;
d=adr;
if(hlist[adr].k==s0)
gotoxy(18,18);printf(" ");
gotoxy(18,18);printf(" %s",hlist[d].name);
gotoxy(18,19);printf(" %s",hlist[d].py);
gotoxy(18,20);
printf(" find %d times",sum);
getch();
else
{if (hlist[adr].k==0)
{gotoxy (18,18);
printf("nothing about it!");
getch();
else
{g=0;
for (i=0;g==0;i++)
{d=(d+s0%10+1)%M; /*伪随机*/
sum=sum+1;
if (hlist[d].k==0)
{gotoxy (18,18);
printf("nothing about it!");
g=1;getch();
gotoxy(18,18);
printf("%s",hlist[d].name);
gotoxy(18,19);
printf("%s",hlist[d].py);
gotoxy(18,20);
printf("find %d times",sum);
getch();
if (hlist[d].k==s0)
gotoxy(18,21);
printf("find %d times until success!",sum);
getch();
/***************************************/
void inp() /*输入表*/
char *f;
int r,s0;
oldlist[0].name="A";oldlist[0].py="apple";
oldlist[1].name="B";oldlist[1].py="bus";
oldlist[2].name="C";oldlist[2].py="cat";
oldlist[3].name="D";oldlist[3].py="dog";
oldlist[5].name="E";oldlist[5].py="egg";
oldlist[6].name="F";oldlist[6].py="fly";
oldlist[7].name="G";oldlist[7].py="good";
oldlist[8].name="H";oldlist[8].py="hurt";
oldlist[9].name="I";oldlist[9].py="int";
oldlist[10].name="J";oldlist[10].py="joy";
oldlist[11].name="K";oldlist[11].py="keep";
oldlist[12].name="L";oldlist[12].py="long";
oldlist[13].name="M";oldlist[13].py="make";
oldlist[14].name="N";oldlist[14].py="net";
oldlist[15].name="O";oldlist[15].py="out";
oldlist[16].name="P";oldlist[16].py="pour";
oldlist[17].name="Q";oldlist[17].py="queen";
oldlist[18].name="R";oldlist[18].py="run";
oldlist[19].name="S";oldlist[19].py="sun";
oldlist[20].name="T";oldlist[20].py="tea";
oldlist[21].name="U";oldlist[21].py="until";
oldlist[22].name="V";oldlist[22].py="vection";
oldlist[23].name="W";oldlist[23].py="water";
oldlist[24].name="X";oldlist[24].py="xray";
oldlist[25].name="Y";oldlist[25].py="you";
oldlist[26].name="Z";oldlist[26].py="zoo";
oldlist[27].name="AA";oldlist[27].py="aah";
oldlist[28].name="BB";oldlist[28].py="bbc";
oldlist[29].name="CC";oldlist[29].py="cch";
/*请在此输入数据,同时修改程序开头的 M L N*/
for (i=0;i<N;i++)
{
s0=0;
f=oldlist[i].py;
for (r=0;*(f+r) != '\0';r++){s0=*(f+r)+s0;};
oldlist[i].k=s0;
/****************************************/
void dhash() /*显示哈希表*/
{ char LON=17;

Answer 3

b