#include <stdio.h>
#include <time.h> //time用到的头文件
#include <stdlib.h> //随机数srand用到的头文件
#include <ctype.h> //toascii()用到的头文件
#include <string.h> //查找姓名时比较字符串用的头文件
#include <windows.h>
#define HASH_LEN 50 //哈希表的长度
#define P 47 //小于哈希表长度的P
#define NAME_LEN 30 //姓名表的长度
typedef struct //姓名表
{
char *name; //名字的拼音
int hashCode; //拼音所对应的ASCII和
} NAME;
typedef struct HashNode //哈希表
{
char *name; //名字的拼音
int key; //拼音所对应的ASCII总和，即关键字
int si; //查找长度
struct HashNode *next; // 指向下一节点的指针
} HashNode;
NAME nameTable[NAME_LEN]; //全局定义姓名表,最大长度为30
HashNode hashTable[HASH_LEN]; //全局定义哈希表，最大长度为50
int i, j; //全局定义随机数,循环用的i、j
/**
* 获取姓名的 ASCII 之和
*/
int gethashCode(char *name)
{
int s = 0;
for (j = 0; *(name + j) != '\0'; j++)
{
s += toascii(*(name + j));
}
return s;
}
void InitName()
{ //姓名表的初始化
nameTable[0].name = "lvsongxian";
nameTable[1].name = "yuanlei";
nameTable[2].name = "daiziwen";
nameTable[3].name = "chenyonghui";
nameTable[4].name = "zhangliang";
nameTable[5].name = "liubei";
nameTable[6].name = "sunshangxiang";
nameTable[7].name = "liyuanfang";
nameTable[8].name = "huge";
nameTable[9].name = "liuyifei";
nameTable[10].name = "anyixuan";
nameTable[11].name = "wangbaoqiang";
nameTable[12].name = "yangyiming";
nameTable[13].name = "hujing";
nameTable[14].name = "guowen";
nameTable[15].name = "xuyang";
nameTable[16].name = "lilu";
nameTable[17].name = "shenjinfeng";
nameTable[18].name = "xuhui";
nameTable[19].name = "huangjing";
nameTable[20].name = "guanyu";
nameTable[21].name = "chenlong";
nameTable[22].name = "huangliang";
nameTable[23].name = "liyan";
nameTable[24].name = "haojian";
nameTable[25].name = "zhangfei";
nameTable[26].name = "shuxiang";
nameTable[27].name = "sunyingjie";
nameTable[28].name = "wangbo";
nameTable[29].name = "zhaoqing";
for (i = 0; i < NAME_LEN; i++) //将字符串的各个字符所对应的ASCII码相加，所得的整数做为哈希表的关键字
{
nameTable[i].hashCode = gethashCode(nameTable[i].name);
}
}
void CreateHash()
{ //建立哈希表
for (i = 0; i < HASH_LEN; i++) //清空哈希表，未经此操作将储存空数据
{
HashNode *node = &hashTable[i];
node->name = "\0";
node->key = 0;
node->si = 0;
node->next = NULL;
}
for (i = 0; i < NAME_LEN; i++)
{
int si = 1; // 查找长度默认为1
int adr = (nameTable[i].hashCode) % P; //除留余数法H(name)=name%P，除数为P=47
HashNode *p = &hashTable[adr]; //将指针指向当前节点
if (p->si != 0) //如果当前节点不为空，说明冲突了，使用「链地址法」处理冲突
{
si++;
while (p->next != NULL) //找到当前地址的最后一个节点
{
p = p->next;
si++;
}
p->next = (HashNode *)malloc(sizeof(HashNode)); // 在最后一个节点的下一个追加节点
p = p->next; // 再将指针指向追加的这个节点
}
// 将姓名表当前的节点存进p指针指向的hash表的节点中
p->key = nameTable[i].hashCode;
p->name = nameTable[i].name;
p->si = si;
p->next = NULL;
}
}
void menu() //交互界面
{
system("cls");
printf("=======================================================\n");
printf("= =\n");
printf("= 人名哈希表 =\n");
printf("= =\n");
printf("= A: 打印姓名表 B: 打印哈希表 =\n");
printf("= =\n");
printf("= C: 查找 D: 退出程序 =\n");
printf("= =\n");
printf("=======================================================\n");
}
// 从屏幕读取字符，确保只读取一个字符
char inputChar()
{
char c = getchar();
while (getchar() != '\n')
;
return c;
}
void DisplayName() //显示姓名表
{
printf("\n地址 \t\t 姓名 \t\t 关键字\n");
for (i = 0; i < NAME_LEN; i++)
{
printf("%2d %18s \t\t %d \n", i, nameTable[i].name, nameTable[i].hashCode);
}
}
void DisplayHash() // 显示哈希表
{
float asl = 0.0;
printf("\n==========================================================");
printf("\n 地址 \t\t 姓名 \t\t 关键字 \t 搜索长度\n"); //显示的格式
printf("==========================================================\n");
for (i = 0; i < HASH_LEN; i++)
{
HashNode *p = &hashTable[i];
while (p != NULL)
{
asl += p->si;
printf("%2d %18s \t\t %d \t\t %d\n", i, p->name, p->key, p->si);
p = p->next;
}
}
asl /= NAME_LEN; //求得ASL
printf("\n\n平均查找长度：ASL(%d)=%f \n", NAME_LEN, asl);
}
// 查询
void FindName()
{
char name[20] = {0};
int hashCode = 0, si = 1;
printf("\n请输入想要查找的姓名的拼音:");
scanf("%s", name);
getchar();
hashCode = gethashCode(name); //求出姓名的拼音所对应的ASCII作为关键字
int adr = hashCode % P; //除留余数法去地址
int j = 0;
// 如果hash地址为空，则直接认为不存在
if (hashTable[adr].key == 0)
{
printf("\n没有想要查找的人!\n");
return;
}
// 如果hashCode和name都相等
if (hashTable[adr].key == hashCode && 0 == strcmp(hashTable[adr].name, name))
{
printf("\n姓名:%s 关键字:%d 地址:%d 查找长度为: 1\n", hashTable[adr].name, hashCode, adr);
}
// 如果不相等，则进行从当前地址遍历链表
else
{
int currAddr = adr;
HashNode *p = &hashTable[adr];
boolean hasFind = FALSE; // 标志：标记是否查到
// 遍历当前地址的链表
do
{
si++; // 查找长度+1
if (p->next != NULL)
{
p = p->next;
}
// 如果找到，直接break跳出循环
if (p->key == hashCode && 0 == strcmp(p->name, name))
{
hasFind = TRUE;
printf("\n姓名:%s 关键字:%d 地址:%d 查找长度为:%d\n", p->name, hashCode, adr, si);
break;
}
} while (p->next != NULL);
if (!hasFind)
{
printf("\n没有想要查找的人!\n");
return;
}
}
}
int main() //主函数
{
char c;
InitName(); //调用初始化姓名表函数
CreateHash(); //调用创建哈希表函数
menu(); //调用交互界面函数
while (1)
{
printf("\n输入选项:");
c = inputChar();
menu();
switch (c) //根据选择进行判断，直到选择退出时才可以退出
{
case 'A':
case 'a':
DisplayName();
break; //打印姓名表
case 'B':
case 'b':
DisplayHash();
break; //打印哈希表
case 'C':
case 'c':
FindName();
break; //调用查找函数
case 'D':
case
- 1
- 2
- 3
- 4
前往页