实验报告
姓名： 学号：
1． 实验题目
针对某个集体中人名设计一个哈希表，使得平均查找长度不超过R，并完成相应的建表和查表程序。
基本要求：假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用线性探测再散列法或链地址法处理冲突。
2．需求分析
本演示程序用VC编写，完成哈希函数用除留余数法构造，用线性探测再散列法或链地址法处理冲突。
输出形式：地址，关键字，收索长度，H（key），拼音
3.概要设计
typedef struct NAME
typedef struct hterm
void InitNameList()
void CreateHashList()
void FindList()
void Display()
int main()
4．详细设计
#include <stdio.h>
#include<malloc.h>
#include<string.h>
#define HASH_LEN 50
#define M 47
#define NAME_NO 8
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="houxinming";
NameList[1].py="abc";
NameList[2].py="defdgf";
NameList[3].py="zhangrji";
NameList[4].py="jiaxin";
NameList[5].py="xiaokai";
NameList[6].py="liupeng";
NameList[7].py="shenyonghai";
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");
}
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");
}
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");
}
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); }
int main()
{
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 0;
else
{
printf("\n请输入正确的选择!");
goto err;
}
}
}
5．调试分析
(略)
6．使用说明
程序名为hash tablet.exe，运行环境为DOS。程序执行后显示
========================
1. 显示哈希表
2. 查找
3. 退出
=======================
SELECT:
在select后输入数字选择执行不同的功能。要求首先输入足够多的插入元素，才可以进行其他的操作。每执行一次功能，就会显示执行的结果（正确或错误）以及执行后单链表的内容。
选择1：显示哈希表
选择2：显示请输入姓名的拼音，
要求输入要删除元素的位置，执行成功后返回元素的值。
选择3：退出程序
7．测试结果
------------------------哈希表的建立和查找----------------------
1. 显示哈希表
2. 查找
3. 退出
1
地址 关键字 搜索长度 H(key) 拼音
0 0 0 0
1 0 0 0
2 0 0 0
3 0 0 0
4 756 1 4 liupeng
5 0 0 0
6 1181 1 6 shenyonghai
7 0 0 0
8 0 0 0
9 0 0 0
10 0 0 0
11 0 0 0
12 294 1 12 abc
13 1094 1 13 houxinming 14 0 0 0
15 861 1 15 zhangrji 16 0 0 0 17 0 0 0 18 0 0 0 19 0 0 0 20 0 0 0 21 0 0 0 22 0 0 23 0 0 24 0 0 25 0 0 26 0 0 27 0 0 28 0 0 29 0 0 30 0 0 31 0 0 32 643 1 33 0 0 34 0 0 35 0 0 36 0 0 37 742 1 38 0 0 39 0 0 40 0 0 41 0 0 42 0 0 43 0 0 44 608 1 45 0 0 46 0 0 47 0 0 48 0 0 49 0 0
平均查找长度：ASL(8)=1.000000
1. 显示哈希表
0 0 0 0 0 0 0 0 0 0
32 jiaxin 0 0 0 0
37 xiaokai 0 0 0 0 0 0
44 defdgf 0 0 0 0 0
2. 查找
3. 退出
请输入正确的选择!2
请输入姓名的拼音: houxinming
姓名:houxinming 关键字:1094 查找长度为: 1
1. 显示哈希表
2. 查找
3. 退出
请输入正确的选择!