附件2
哈希表的创建源程序
咸海#include<stdio.h>
#include<time.h> //time用到的头文件
#include<stdlib.h> //随机数用到的头文件
#include<ctype.h> //toascii()用到的头文件
#include<string.h> //查姓名时比较用的头文件 #define HASH_LEN 50 //哈希表的长度 #define P 47 //小于哈希表长度的P
大型超市管理
#define NAME_LEN 30 //姓名表的长度
typedef struct //姓名表
文献综述的格式
{
int m; //拼音所对应的ASCII码
}NAME;
NAME NameTable[HASH_LEN]; //全局定义姓名表 typedef struct //哈希表
{
char *py; //名字的拼音
int m; //拼音所对应的ASCII总和
int si; //查长度
}HASH;
HASH HashTable[HASH_LEN]; //全局定义哈希表
int d[30],i,j; //全局定义随机数,循环用的i、j
//****************************************初始化函数******************************
void InitNameTable() //姓名表的初始化
{
NameTable[0].py="zhangyihao";
NameTable[1].py="qiujiaxing";
NameTable[2].py="zhoulei";
NameTable[3].py="xuweiying";
NameTable[4].py="zhanshengping";
NameTable[5].py="wangwenkai";
NameTable[6].py="gaodan";
NameTable[7].py="renkung";
NameTable[8].py="duixintong";av
NameTable[9].py="mazhe";
NameTable[10].py="wangyongjie";
NameTable[11].py="kangwenhui";
NameTable[12].py="tianhuanhuan";
NameTable[13].py="zhouyuncheng";
NameTable[14].py="liangzhuang";
NameTable[15].py="zhangfan";
NameTable[16].py="wangpengfei";
NameTable[17].py="shafangfang";
NameTable[18].py="yanghuan";
NameTable[19].py="wangzhe";
NameTable[20].py="shirui";
NameTable[21].py="wangwenjuan";
NameTable[22].py="wangqian";
NameTable[23].py="chenyuhan";
NameTable[24].py="wangxin";
NameTable[25].py="guojing";
NameTable[26].py="tanqining";
NameTable[27].py="kangwenhui";
NameTable[28].py="songyangyang";
NameTable[29].py="yanfanglei";
for (i=0;i<NAME_LEN;i++) //将字符串的各个字符所对应的ASCII码相加，所得的整数做为哈希表的关键字
{
int s=0;
char *p=NameTable[i].py;//定义字符指针接受哈希结构体的拼音值
for (j=0;*(p+j)!='\0';j++)
s+=toascii(*(p+j));//对p指针接受的拼音值进行转化，转化成相应的ASICC码数值
NameTable[i].m=s;
}
}
//****************************************创建函数******************************
void CreateHashTable() //建立哈希表
{
for(i=0;i<HASH_LEN;i++)//初始化哈希表
{
HashTable[i].py="\0";
HashTable[i].m =0;
HashTable[i].si=0;
}
for(i=0;i<NAME_LEN;i++) //循环遍历姓名表，利用除留取余法为创建的哈希表填值
{
int sum=1,j=0;
int adr=(NameTable[i].m)%P; //除留余数法 H(key)=key MOD p,p<=m
if(HashTable[adr].si==0) //如果不冲突，将姓名表赋值给哈希表
{
书目文献出版社
HashTable[adr].m =NameTable[i].m;//填入码值
HashTable[adr].py=NameTable[i].py;//填入姓名拼音值
HashTable[adr].si=1; //不冲突的条件下，查长度定义为1
}
else //如果冲突
{
while(HashTable[adr].si!=0)
{
adr=(adr+d[j++])%HASH_LEN; //伪随机探测再散列法处理冲突
sum=sum+1; //查次数加1
}
HashTable[adr].m =NameTable[i].m; //将姓名表复制给哈希表对应的位置上
HashTable[adr].py=NameTable[i].py;
HashTable[adr].si=sum; //根据实际情况赋查长度
西陵网校 }
}
}
//****************************************显示函数******************************
void DisplayNameTable() //显示姓名表
{
printf("\n地址 \t\t 姓名 \t\t 关键字\n");
for (i=0;i<NAME_LEN;i++)//循环遍历姓名表
printf("%2d %18s \t\t %d \n",i,NameTable[i].py,NameTable[i].m); //输出姓名值及ASCII码
}
void DisplayHashTable() // 显示哈希表
{
float ASL=0.0;//定义平均查长度为浮点型
printf("\n\n 地址 \t\t 姓名 \t\t 关键字 \t 搜索长度\n"); //显示的格式
for (i=0;i<HASH_LEN;i++)
{
printf("%2d %18s \t\t %d \t\t %d\n",i,HashTable[i].py,HashTable[i].m,HashTable[i].si);
ASL+=HashTable[i].si;
}
ASL/=NAME_LEN; //求得ASL
printf("\n\n平均查长度：ASL(%d)=%f \n",NAME_LEN,ASL);
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议