C语言项目 电话查询系统 哈希表实现(项目要求 + 运行界面 + 代码分析 + 完整代码)
关注博主不迷路,博主带你码代码!
1. 项目要求
- 设每个记录有以下数据项:用户名、电话、地址
- 从键盘输入各个记录,以电话号码为关键字建立哈希表
- 能够增加、修改、删除给定电话号码的相关记录
2. 数据样例
7
17718881666 chen hunan
12837192867 yuan hubei
18998239899 duan loudi
13689721388 qian hefei
19999999999 zhang beijing
12673678523 liu liuan
13876352729 luo fujian
3. 运行界面
-
菜单页面
-
添加电话
-
查询电话
-
修改信息
-
删除电话
-
退出系统
4. 代码分析
- 哈希函数
key 值的确定是按照电话号码的求和 % MAXSIZE所得的
% MAXSIZE 的原因是因为放置下标越界
int GetHashKey(char ar[])
{
int len = strlen(ar);
int key = 0;
int i;
for(i = 0; i < len; i ++ )
{
key += ar[i] - '0';
}
return key % MAXSIZE;
}
- 冲突处理
哈希冲突处理,这里采用的是二次探测法,将 Cay 分为两种情况,当 Cay 为奇数的时候,我们向后探测,当 Cay 为偶数的时候,我们向前探测,不管在向前还是向后探测,我们都要对其取模,防止下标越界,但是在向后探测的时候,可能是负数,为了方便取模,我们对于负数的时候就直接跳过就好了。
//冲突处理,二次探测再散列
int HandleCollision(HashTable table, int key)
{
Czy = 1; //从2,3,4,5,.......
while(1)
{
Czy ++ ; //从2,3,4,5,.......
if(Czy % 2 == 0)
{
if(table->data[(key + (Czy / 2) * (Czy / 2)) % MAXSIZE].Name[0] == 0)
return (key + (Czy / 2) * (Czy / 2)) % MAXSIZE;
}
else if(Czy % 2 != 0) {
if((key - (Czy / 2) * (Czy / 2)) < 0) continue;//由于是减法,要注意负数不能取模
if(table->data[(key - (Czy / 2) * (Czy / 2)) % MAXSIZE].Name[0] == 0)
return (key - (Czy / 2) * (Czy / 2)) % MAXSIZE;
}
}
//return -1;
}
- 构建哈希表
构建哈希表的时候,我们先要得到哈希函数的 key 值,然后判断是否产生哈希冲突
由于我们的电话、姓名、地址都是使用的字符串结构,所以在讲结构体中的数据存入到哈希表的时候,直接使用 strcpy 赋值函数就可以了
//构建哈希表
void CreateHashTable(HashTable table, Record *record, int n)
{
int key;
int i;
for(i = 0; i < n; i ++ )
{
key = GetHashKey(record[i].Number); // 得到key值
if(table->data[key].Name[0] != 0) // 需要解决哈希冲突
key=HandleCollision(table, key);
// 将结构体中的数据存储到哈希表中
strcpy(table->data[key].Number, record[i].Number);
strcpy(table->data[key].Name, record[i].Name);
strcpy(table->data[key].Address, record[i].Address);
}
}
- 按电话号查找
在得到 key 值,先判断是否可以查找到,如果可以找到,判断一下该数据是否被删除过;如果没有找到,进行冲突查找,查找到后也进行判断一下是否被删除过
//按照电话号码寻找
int SerchKey(HashTable table, char PhoneNumber[])
{
int flag = 0;
int key = GetHashKey(PhoneNumber);
if(strcmp(table->data[key].Number, PhoneNumber)) // 如果没有匹配成功,则对其尽心冲突查找
{
for(Czy = 1; Czy < MAXSIZE; Czy ++ )
{
if(Czy % 2 == 0)
{
if(!strcmp(PhoneNumber, table->data[(key + (Czy / 2) * (Czy / 2)) % MAXSIZE].Number))
{
key = (key + (Czy / 2) * (Czy / 2)) % MAXSIZE;
break;
}
}
else if(Czy % 2 != 0)
{
if((key - (Czy / 2) * (Czy / 2)) < 0) continue;//由于是减法,要注意负数不能取模
if(!strcmp(PhoneNumber, table->data[(key - (Czy / 2) * (Czy / 2)) % MAXSIZE].Number))
{
key = (key - (Czy / 2) * (Czy / 2)) % MAXSIZE;
break;
}
}
}
flag = 1;
}
if(flag) printf("未找到!请重新输入!n");
else
{
if(!table->data[key].flag) printf("搜索到的号码信息为:n%s %s %sn",table->data[key].Name,table->data[key].Number,table->data[key].Address);
else printf("未找到!请重新输入!n");
}
return flag;
}
- 添加电话
添加电话就很简单了,在读入数据后,就直接添加到哈希表中就可以了
void add()
{
int k = 0;
int i;
printf("请输入要添加的数量:n");
scanf("%d", &k);
printf("请输入添加的信息(电话、姓名、地址):n");
for(i = 0; i < k; i ++ )
scanf("%s %s %s", &record[i].Number, &record[i].Name, &record[i].Address);
//创建哈希表
CreateHashTable(numbertable, record, k);
printf("添加成功!n");
}
- 查询电话
根据输入的电话,直接调用查找函数就行了
void find()
{
char PhoneNumber[20];
printf("请输入要查找的电话:n");
scanf("%s", PhoneNumber);
printf("给定的电话号码为:%sn", PhoneNumber);
SerchKey(numbertable, PhoneNumber);
}
- 修改信息
修改信息函数,内置了一个 key 的查找函数,根据输入的手机号,查看 key 是否有对应的数据,如果有数据但不相等,则进行冲突查找,查找到后,判断该数据是否被删除过,如果被删除过就不能进行修改,若没有删除过则可以进行修改,修改信息的时候,和添加信息一样,同样采用 strcpy 赋值函数
void revise(HashTable table)
{
char PhoneNumber[20];
char Name[20];
char Address[20];
int key;
int flag = 0;
printf("请输入要修改的电话:n");
scanf("%s", PhoneNumber);
key = GetHashKey(PhoneNumber);
if(strcmp(table->data[key].Number, PhoneNumber)){
for(Czy = 1; Czy < MAXSIZE; Czy ++ ){
if(Czy % 2 == 0) {
if(!strcmp(PhoneNumber, table->data[(key + (Czy / 2) * (Czy / 2)) % MAXSIZE].Number)){
key = (key + (Czy / 2) * (Czy / 2)) % MAXSIZE;
break;
}
}
else if(Czy % 2 != 0) {
if((key - (Czy / 2) * (Czy / 2)) < 0) continue;//由于是减法,要注意负数不能取模
if(!strcmp(PhoneNumber, table->data[(key - (Czy / 2) * (Czy / 2)) % MAXSIZE].Number)){
key = (key - (Czy / 2) * (Czy / 2)) % MAXSIZE;
break;
}
}
}
flag = 1;
}
if(flag) printf("未找到!请重新输入!n");
else
{
if(!table->data[key].flag)
{
printf("搜索到的号码信息为:n%s %s %sn", table->data[key].Name, table->data[key].Number, table->data[key].Address);
printf("请输入你要修改的名字:n");
scanf("%s", &Name);
printf("请输入你要修改的地址:n");
scanf("%s", &Address);
strcpy(table->data[key].Name, Name);
strcpy(table->data[key].Address, Address);
printf("修改成功!n");
}
else printf("未找到!请重新输入!n");
}
}
- 删除电话
删除操作我们只需要对于每个数据添加一个是否删除的标记,当被删除后,就将标记置为 1 ,当我们需要进行修改或者查询的时候,只需要对标记进行判断一下就行了
void del(HashTable table)
{
char PhoneNumber[20];
int key;
int flag = 0;
printf("请输入要删除的电话:n");
scanf("%s",PhoneNumber);
key = GetHashKey(PhoneNumber);
flag = SerchKey(numbertable,PhoneNumber);
if(!flag)
{
table->data[key].flag = 1;
printf("删除成功!n");
}
}
- 主页面
主页面主要包括菜单选项,使用 switch 结构实现
int main(){
int p = 0;
int k = 0;
numbertable = &table;
numbertable->data = (Record*)malloc(sizeof(record[0])*MAXSIZE);
memset(numbertable->data, 0, sizeof(record[0])*MAXSIZE);
numbertable->size = MAXSIZE;
numbertable->cnt = 0;
while(p != -1)
{
puts("");
puts("");
puts("");
printf("tt电话号码查询系统n");
printf("tt1.添加电话n");
printf("tt2.查询电话n");
printf("tt3.修改信息n");
printf("tt4.删除电话n");
printf("tt5.退出系统n");
puts("");
printf("tt请输入(1、2、3、4):n");
scanf("%d",&p);
switch(p){
case 1: add(); break;
case 2: find(); break;
case 3: revise(numbertable); break;
case 4: del(numbertable); break;
case 5: p = -1; break;
}
}
return 0;
}
5. 完整代码
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAXSIZE 50
int Czy = 1;
typedef struct record
{
char Number[20]; // 电话
char Name[20]; // 姓名
char Address[20]; // 地址
int flag; // 是否删除
}Record;
typedef struct Hash
{
Record *data;
int cnt;
int size;
}*HashTable,HashElem;
//定义及初始化
HashElem table;
HashTable numbertable;
Record record[50];
//哈希函数,将电话号码每一位求和
int GetHashKey(char ar[])
{
int len = strlen(ar);
int key = 0;
int i;
for(i = 0; i < len; i ++ )
{
key += ar[i] - '0';
}
return key % MAXSIZE;//必须取模,否则下标越界
}
//冲突处理,二次探测再散列
int HandleCollision(HashTable table, int key)
{
Czy = 1; //从2,3,4,5,.......
while(1)
{
Czy ++ ; //从2,3,4,5,.......
if(Czy % 2 == 0)
{
if(table->data[(key + (Czy / 2) * (Czy / 2)) % MAXSIZE].Name[0] == 0)
return (key + (Czy / 2) * (Czy / 2)) % MAXSIZE;
}
else if(Czy % 2 != 0) {
if((key - (Czy / 2) * (Czy / 2)) < 0) continue;//由于是减法,要注意负数不能取模
if(table->data[(key - (Czy / 2) * (Czy / 2)) % MAXSIZE].Name[0] == 0)
return (key - (Czy / 2) * (Czy / 2)) % MAXSIZE;
}
}
//return -1;
}
//构建哈希表
void CreateHashTable(HashTable table, Record *record, int n)
{
int key;
int i;
for(i = 0; i < n; i ++ )
{
key = GetHashKey(record[i].Number); // 得到key值
if(table->data[key].Name[0] != 0) // 需要解决哈希冲突
key=HandleCollision(table, key);
// 将结构体中的数据存储到哈希表中
strcpy(table->data[key].Number, record[i].Number);
strcpy(table->data[key].Name, record[i].Name);
strcpy(table->data[key].Address, record[i].Address);
}
}
//按照电话号码寻找
int SerchKey(HashTable table, char PhoneNumber[])
{
int flag = 0;
int key = GetHashKey(PhoneNumber);
if(strcmp(table->data[key].Number, PhoneNumber)) // 如果没有匹配成功,则对其尽心冲突查找
{
for(Czy = 1; Czy < MAXSIZE; Czy ++ )
{
if(Czy % 2 == 0)
{
if(!strcmp(PhoneNumber, table->data[(key + (Czy / 2) * (Czy / 2)) % MAXSIZE].Number))
{
key = (key + (Czy / 2) * (Czy / 2)) % MAXSIZE;
break;
}
}
else if(Czy % 2 != 0)
{
if((key - (Czy / 2) * (Czy / 2)) < 0) continue;//由于是减法,要注意负数不能取模
if(!strcmp(PhoneNumber, table->data[(key - (Czy / 2) * (Czy / 2)) % MAXSIZE].Number))
{
key = (key - (Czy / 2) * (Czy / 2)) % MAXSIZE;
break;
}
}
}
flag = 1;
}
if(flag) printf("未找到!请重新输入!n");
else
{
if(!table->data[key].flag) printf("搜索到的号码信息为:n%s %s %sn",table->data[key].Name,table->data[key].Number,table->data[key].Address);
else printf("未找到!请重新输入!n");
}
return flag;
}
void add()
{
int k = 0;
int i;
printf("请输入要添加的数量:n");
scanf("%d", &k);
printf("请输入添加的信息(电话、姓名、地址):n");
for(i = 0; i < k; i ++ )
scanf("%s %s %s", &record[i].Number, &record[i].Name, &record[i].Address);
//创建哈希表
CreateHashTable(numbertable, record, k);
printf("添加成功!n");
}
void find()
{
char PhoneNumber[20];
printf("请输入要查找的电话:n");
scanf("%s", PhoneNumber);
printf("给定的电话号码为:%sn", PhoneNumber);
SerchKey(numbertable, PhoneNumber);
}
void revise(HashTable table)
{
char PhoneNumber[20];
char Name[20];
char Address[20];
int key;
int flag = 0;
printf("请输入要修改的电话:n");
scanf("%s", PhoneNumber);
key = GetHashKey(PhoneNumber);
if(strcmp(table->data[key].Number, PhoneNumber)){
for(Czy = 1; Czy < MAXSIZE; Czy ++ ){
if(Czy % 2 == 0) {
if(!strcmp(PhoneNumber, table->data[(key + (Czy / 2) * (Czy / 2)) % MAXSIZE].Number)){
key = (key + (Czy / 2) * (Czy / 2)) % MAXSIZE;
break;
}
}
else if(Czy % 2 != 0) {
if((key - (Czy / 2) * (Czy / 2)) < 0) continue;//由于是减法,要注意负数不能取模
if(!strcmp(PhoneNumber, table->data[(key - (Czy / 2) * (Czy / 2)) % MAXSIZE].Number)){
key = (key - (Czy / 2) * (Czy / 2)) % MAXSIZE;
break;
}
}
}
flag = 1;
}
if(flag) printf("未找到!请重新输入!n");
else
{
if(!table->data[key].flag)
{
printf("搜索到的号码信息为:n%s %s %sn", table->data[key].Name, table->data[key].Number, table->data[key].Address);
printf("请输入你要修改的名字:n");
scanf("%s", &Name);
printf("请输入你要修改的地址:n");
scanf("%s", &Address);
strcpy(table->data[key].Name, Name);
strcpy(table->data[key].Address, Address);
printf("修改成功!n");
}
else printf("未找到!请重新输入!n");
}
}
void del(HashTable table)
{
char PhoneNumber[20];
int key;
int flag = 0;
printf("请输入要删除的电话:n");
scanf("%s",PhoneNumber);
key = GetHashKey(PhoneNumber);
flag = SerchKey(numbertable,PhoneNumber);
if(!flag)
{
table->data[key].flag = 1;
printf("删除成功!n");
}
}
int main(){
int p = 0;
int k = 0;
numbertable = &table;
numbertable->data = (Record*)malloc(sizeof(record[0])*MAXSIZE);
memset(numbertable->data, 0, sizeof(record[0])*MAXSIZE);
numbertable->size = MAXSIZE;
numbertable->cnt = 0;
while(p != -1)
{
puts("");
puts("");
puts("");
printf("tt电话号码查询系统n");
printf("tt1.添加电话n");
printf("tt2.查询电话n");
printf("tt3.修改信息n");
printf("tt4.删除电话n");
printf("tt5.退出系统n");
puts("");
printf("tt请输入(1、2、3、4):n");
scanf("%d",&p);
switch(p){
case 1: add(); break;
case 2: find(); break;
case 3: revise(numbertable); break;
case 4: del(numbertable); break;
case 5: p = -1; break;
}
}
return 0;
}
6. 项目报告
项目优点:
使用的哈希表存储信息,并采用了二次探测的方法解决哈希冲突的问题
并采用手机号作为唯一标识
运行二次添加的时候,不进行覆盖操作,紧接着在表后面进行添加
项目缺点:
手机号的正确与错误输入没有限制
姓名的正确与错误输入没有限制
地址的正确与错误输入没有限制
关注博主不迷路,博主带你码代码!
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
二维码