#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define MAXSIZE 10000
int m = 1;
typedef struct record
{
char Number[20]; // 电话
char Name[20]; // 姓名
char Address[20]; // 地址
int flag; // 是否删除
} Record;
typedef struct Hash
{
Record *data;
int t;
int size;
} *HashTable, HashElem;
//定义及初始化
HashElem table;
HashTable nametable;
Record record[10000];
//哈希函数，将电话号码每一位求和 ，以电话号码为关键字构建哈希表
//除留余数法
int GetHashKey1(char a[])
{
int len = strlen(a);
int key1 = 0;
for(int i = 0; i < len; i++)
key1 += a[i] - '0';
return key1 % MAXSIZE; //必须取模，否则下标越界
}
//直接定址法 以用户名为关键字构建哈希表
int GetHashKey2(char b[])
{
int len = strlen(b);
int key2 = 0;
for(int i = 0; i < len; i++)
key2 += b[i] - '0';
return key2 / MAXSIZE;
}
//冲突处理，二次探测再散列
int HandleCollision1(HashTable table, int key1)
{
while(1)
{
m++ ; //从2,3,4,5,.......
if(m % 2 == 0)
{
if(table->data[(key1 + (m / 2) * (m/2))%MAXSIZE].Name[0] == 0)
return (key1 + (m / 2)*(m / 2)) % MAXSIZE;
}
else if(m % 2 != 0)
{
if((key1 - (m / 2)*(m / 2)) < 0)
continue; //由于是减法，要注意负数不能取模
if(table->data[(key1 - (m / 2) * (m / 2)) % MAXSIZE].Name[0] == 0)
return (key1 - (m / 2)*(m / 2)) % MAXSIZE;
}
}
}
//处理冲突，线性探测法
int HandleCollision2(HashTable table, int key2)
{
while(1)
{
m++ ; //从2,3,4,5,.......
if(table->data[(key2 + (m / 2) * (m/2))%MAXSIZE].Name[0] == 0)
return (key2 + (m / 2)*(m / 2)) % MAXSIZE;
}
}
//构建哈希表
void CreateHashTable1(HashTable table, Record *record, int n)
{
int key1;
int i;
for(i = 0; i < n; i++)
{
key1 = GetHashKey1(record[i].Number); // 得到key值
if(table->data[key1].Name[0] != 0) // 需要解决哈希冲突
key1 = HandleCollision1(table, key1);
// 将结构体中的数据存储到哈希表中
strcpy(table->data[key1].Number, record[i].Number);
strcpy(table->data[key1].Name, record[i].Name);
strcpy(table->data[key1].Address, record[i].Address);
}
}
void CreateHashTable2(HashTable table, Record *record, int n)
{
int key2;
int i;
for(i = 0; i < n; i++)
{
key2 = GetHashKey2(record[i].Name); // 得到key值
if(table->data[key2].Name[0] != 0) // 需要解决哈希冲突
key2 = HandleCollision2(table, key2);
// 将结构体中的数据存储到哈希表中
strcpy(table->data[key2].Number, record[i].Number);
strcpy(table->data[key2].Name, record[i].Name);
strcpy(table->data[key2].Address, record[i].Address);
}
}
//按照用户名寻找
int SerchKey(HashTable table, char Name[])
{
int flag = 0;
int key2 = GetHashKey2(Name);
if(strcmp(table->data[key2].Name, Name)) // 如果没有匹配成功，则对其冲突查找
{
for(m = 1; m < MAXSIZE; m++)
{
if(!strcmp(Name, table->data[(key2 + (m / 2) * (m / 2)) % MAXSIZE].Name))
{
key2 = (key2 + (m / 2) * (m / 2)) % MAXSIZE;
break;
}
}
flag = 1;
}
if(!table->data[key2].flag)
printf("搜索到的号码信息为：\n%s %s %s %s\n" ,table->data[key2].Name,table->data[key2].Number,table->data[key2].Address);
else
printf("未找到！请重新输入！\n");
return flag;
}
void add1(HashTable table)
{
FILE *fp = fopen("D:\\test1.txt","w");
if(fp == NULL)
printf("error");
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);
fprintf(fp, "%d %s %s %s\n" ,(i + 1) ,record[i].Number, record[i].Name, record[i].Address);
}
fclose(fp);
fp = NULL;
//创建哈希表
CreateHashTable1(nametable, record, k);
printf("添加成功!\n");
table->size = k;
}
void add2(HashTable table)
{
FILE *fp = fopen("D:\\test1.txt","w");
if(fp == NULL)
printf("error");
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);
fprintf(fp, "%d %s %s %s\n" ,(i + 1) ,record[i].Number, record[i].Name, record[i].Address);
}
fclose(fp);
fp = NULL;
//创建哈希表
CreateHashTable2(nametable, record, k);
printf("添加成功!\n");
table->size = k;
}
void getASL1(HashTable table)
{
double a;
a = (table->size)/10000;
double ASL;
ASL = (1 + 1/(1 - a))/2;
printf("线性探测法ASL：%lf\n",ASL);
}
void getASL2(HashTable table)
{
double a;
a = (table->size)/10000;
double ASL;
ASL = (1/a)*(log(1 - a));
printf("二次探测法ASL：%lf\n",ASL);
}
void find()
{
char Name[20];
printf("请输入要查找的用户名：\n");
scanf("%s", Name);
printf("给定的用户名为：%s\n", Name);
SerchKey(nametable, Name);
}
int main()
{
int f = 0;
int k = 0;
nametable = &table;
nametable->data = (Record*)malloc(sizeof(record[0])*MAXSIZE);
memset(nametable->data, 0, sizeof(record[0])*MAXSIZE);
nametable->size = MAXSIZE;
nametable->t = 0;
while(f != -1)
{
printf("***************************************************\n");
printf("\t\t电话号码查询系统\n");
printf("\t\t1.以电话号码为关键字添加电话\n");
printf("\t\t2.以用户名为关键字添加电话\n");
printf("\t\t3.求出ASL\n");
printf("\t\t4.查询用户\n");
printf("\t\t5.退出系统\n");
printf("***************************************************\n");
printf("\t\t请输入（1、2、3、4、5）：");
scanf("%d",&f);
switch(f)
{
case 1: add1(nametable); break;
case 2: add2(nametable); break;
case 3: getASL1(nametable); getASL2(nametable); break;
case 4: find(); break;
case 5: f = -1; break;
}
}
return 0;
}
多次通过输入用户名，结果查询信息显示不出来；两种方法的ASL也不恰当
一个成功结点的查找长度 = 自身所在层数
一个失败结点的查找长度 = 其父节点所在层数
默认情况下，各种失败情况或成功情况都等概率发生
计算的时候把整形转成浮点再计算