提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

前言

记录下上学期的数据结构实验
本电话号码查询系统基于两种散列方法和两种解决冲突的方法实现

---

提示：以下是本篇文章正文内容，下面案例可供参考

一、问题描述

设计散列表，实现电话号码查找系统。设电话号码簿长度为n（0≤n≤10000），系统应该实现如下工作：
⑴ 电话号码簿保存在磁盘文件中，每一条电话号码记录包含数据项：编号（唯一），用户名，通信地址，电话号码（手机号）
⑵ 创建散列表：系统运行时，读取磁盘文件的电话号码，构建散列表，用于查询。要求：自选散列函数(至少2种)，自选解决冲突的方法(至少2种)，分别以电话号码和用户名为关键字，建立散列表。
⑶ 查询：根据输入的用户名，查找并显示给定用户的信息。
⑷ 性能分析：
① 计算并输出不同散列函数、不同解决冲突方法的平均查找长度。
② 通过改变散列因子、改变哈希函数等方式，改善平均查找长度：通过数据表、柱形图、折线图等方式，记录实验数据的变化情况，对影响平均查找长度变化的原因进行分析。

---

二、问题描述

（1）选用的散列函数

①除留余数法
分析：
ⅰ.以电话号码为关键字时，将字符串类型的电话号码转换成long型数据，除以表长，剩下的余数作为其在散列表中的地址，即pos值。
ⅱ.以姓名为关键字时，将字符串类型的姓名的每一位上的字母转换成ascii码，此时还是内容为数字的字符串，再将字符串转换成long型数据，除以表长，剩下的余数作为其在散列表中的地址，即pos值。
②折叠法
分析：
ⅰ.以电话号码为关键字时，将字符串类型的电话号码，切割成四组数据，每组数据的个数为3 3 3 2，转化成int型数据，取第一组数据和第三组数据、第二组和第四组的逆置数相加，得到的数据取后四位数，作为其在散列表中的地址，即pos值。
ⅱ.以姓名为关键字时，将字符串类型的姓名的每一位上的字母转换成ascii码，此时还是内容为数字的字符串，再切割成四组数据，每组数据的个数为3 3 3 2，转化成int型数据，取第一组数据和第三组数据、第二组和第四组的逆置数相加，得到的数据取后四位数，作为其在散列表中的地址，即pos值。

（2）散列因子

散列表的散列因子定义为：α= 填入表中的元素个数/散列表的长度。α是散列表装满程度的标志因子。由于表长是定值，α与元素个数成正比，所以，α越大，填入表中的元素较多，产生冲突的可能性就越大；α越小，填入表中的元素较少，产生冲突的可能性就越小。
为了探究不同散列因子对平均查找长度ASL的影响，在利用线性探测法解决冲突时，本实验中
拟取用 α 的值为 0.85、0.75、0.65、0.55；利用拉链法解决冲突时，本实验中 α 拟选用 1、1.2、
1.4、1.6。

（3）解决冲突的方法

①线性探测法
该方法的基本思想是，当关键字key的哈希地址p出现冲突时，顺序查看表中下一单元，以p为基础产生另一个哈希地址p1,如果p1仍然冲突，再以p为基础产生p2，……，直到找到一个不冲突的哈希地址pi，将相应元素存入其中。冲突发生时，顺序查看表中下一单元，，直到找出一个空单元或者查遍全表。
缺点：容易造成元素聚集，降低查找效率
②拉链法
该方法基本思想是将所有的哈希地址为i的元素构成一个同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中。
优点：避免了动态调整的开销

---

三、实验结果及分析

（1）实验数据描述

1.数据集规模
本实验拟采用 10000 组联系人记录。每一行记录一位联系人的编号、姓名、地址、电话号码。
文件存储于FinalDataSet_10000.txt。文件存储格式如图 1 所示：

图1 实验数据集内容

2.数据集来源
本次实验的数据全部随机生成。
数据内容：
编号：1-10000，按顺序输出即可；
姓名：三个英文字母，字符串。随机生成0-25的int型数据，再通过循环从char型字母表数组中利用下标读出并存储到data数组的姓名域中去；
地址：长度不等，字符串。这里使用的城市数据仅为20组，每组城市数据存储在Country结构体中，结构体中有city[]，用于存放每组城市名称，所有的城市数据存储在Country类型的数组中。随机生成0-20的int型数据，再通过循环从Country类型的数组中利用下标读出并存储到data数组的地址域中去。
电话号码：11位0-9的数据，字符串。根据一般电话号码的规律，首位都是1，因此其他10位是随机生成的。随机生成0-9的int型数据，再通过循环从char型数字表数组中利用下标读出并存储到data数组的电话号码域中去；
3.磁盘文件存储格式：.txt格式。

（2）实验结果

1.以电话号码为关键字
①哈希函数为除留余数法，解决冲突的方法为线性探测法，查找成功，实验结果如图2、3所示。

图2 以电话号码为关键字查找成功的实验结果

图3 对应在磁盘文件中的数据

②哈希函数为除留余数法，解决冲突的方法为拉链法，查找失败，实验结果如图4所示。

图4 以电话号码为关键字查找失败的实验结果

2.以姓名为关键字
①哈希函数为除留余数法，解决冲突的方法为线性探测法，查找成功，实验结果如图5、6所示。

图5 以姓名为关键字查找成功的实验结果

图6对应在磁盘文件中的数据

②哈希函数为除留余数法，解决冲突的方法为拉链法，查找失败，实验结果如图7所示。

图7 以电话号码为关键字查找失败的实验结果

（3）性能分析

①分析填充因子和冲突方法与 ASL 的关系

表1 在不同的散列因子和解决冲突方法下，查找成功和查找失败的ASL

图8 在不同的散列因子和解决冲突的方法下，查找成功的ASL折线图

图9 在不同的散列因子和解决冲突的方法下，查找失败的ASL折线图

图10 在线性检测法下，不同的散列因子，查找成功和查找失败的ASL折线图

图11 在拉链法下，不同的散列因子，查找成功和查找失败的ASL折线图

由表1和图8-11可见，在采用相同的解决冲突的方法时，ASL随散列因子增大而变大。当解决冲突方法为线性探测法时，查找失败比查找成功的ASL大，且增幅也随散列因子增大而变大。但当解决冲突方法为拉链法时，查找成功比查找失败的ASL大，且增幅并不随散列因子增大而改变。
②分析数据规模与 ASL 的关系

图12 在散列因子为0.75时，不同的数据规模与ASL之间的折线图

在散列因子α为0.75的情况下，进行了实验，实验数据如图12所示。显然由图可知，在相同的散列因子的情况下，随着数据规模的增大，ASL并没有明显的变化，数据基本都浮动在2.5上下。我认为数据规模与ASL之间没有直接的关系。

---

四、实验总结

在测试了不同的解决冲突办法、不同的散列因子和不同的数据规模对ASL的影响后，我得到了以下的结论：
a．当散列因子小于1时，解决冲突的方法可以选择线性探测法。ASL随着散列因子α的增大而增大，且增幅随之变大。因此，当解决冲突方法为线性探测法时，要慎重选择散列因子α。散列因子α过大，平均查找长度ASL过大，查找效果差；散列因子α过小，平均查找长度ASL虽然会较小，但是需要的存储空间随之变大了，因此在设计解决冲突方法为线性探测法的散列表时，要选择合适的散列因子α。
b．当散列因子大于1时，解决冲突的方法可以选择拉链法法。ASL随着散列因子α的增大而增大，但增幅并不随散列因子α的增大而改变，而是几乎不变。因此，适当选择拉链法的散列因子，可以表现出良好的查找性能。
c．由图表分析可得，解决冲突方式为拉链法受散列因子α的影响较小，解决冲突方式为线性探测法受散列因子α的影响较大。因此，拉链法更为稳定，性能更好。
d．数据规模较小时，解决冲突方式采用线性探测法、拉链法，性能差别都不是很大，均能表现出良好的查找性能，但是当数据规模变大的时候，采用线性探测法解决冲突的方法会使冲突增多，此时采用拉链法可以表现出更好的查找性能。
e．在实际操作的过程中，特别是在处理以姓名为关键字的时候，我发现有很多人的名字是重复的，这种情况在现实生活中也会存在，这也是冲突的其中一种方式，因此针对这种情况，我分不同的解决冲突方法进行讨论。
①线性探测法。当发现关键字重复时，再次通过线性探测，在与之重复的关键字周围寻找一个空表，将其填入，即可解决冲突，但要注意，要使用一个标志flag来记录某关键字重复的次数，借助该标志flag在查询关键字时方便找到所有重复的元素。
②拉链法。当发现关键字重复时，直接将该节点插入散列表的与重复关键字相同的位置后的头结点，即可解决冲突，但这个方法也需要使用一个标志flag来记录某关键字重复的次数，用来方便找到所有重复的元素。

---

五、源代码

（1）随机生成电话号码系统代码

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <string.h>#define N 10000 //元素最大个数
typedef struct {int no;  //编号char name[3];//名字char address[10];//地址char tel[12];//电话号码
} NODE;
typedef struct {char data[10];
} Country;
Country country[10];void creatfile(NODE data[], int *n);//创建磁盘文件f:\resource.dat
int isTelRepeated(char tel[]);void initCountry();int main() {NODE DATA[N];int n;creatfile(DATA, &n);return 0;
}void creatfile(NODE data[], int *n) {FILE *fp;int i, key, flag;int temp_n;char temp_tel[11];unsigned seed;*n = N;char num[10] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};char alphabet[26] = {'a', 'b', 'c', 'd', 'e', 'f', 'g','h', 'i', 'j', 'k', 'l', 'm', 'n','o', 'p', 'q', 'r', 's', 't','u', 'v', 'w', 'x', 'y', 'z'};//字母表/*char ALPHABET[26] = {'A', 'B', 'C', 'D', 'E', 'F', 'G','H', 'I', 'J', 'K', 'L', 'M', 'N','O', 'P', 'Q', 'R', 'S', 'T','U', 'V', 'W', 'X', 'Y', 'Z'};//字母表*/initCountry();if ((fp = fopen("/Users/xiaoyee/Desktop/数据结构实验作业/实验报告/电话号码查询系统/1/TelDataSet_10000.txt", "w")) == NULL) {printf("can't open the file!\n");exit(0);}seed = time(NULL);srand(seed);  //设置随机种子for (i = 0; i < *n;i++) {for (int k = 0; k < 3; k++) {key = rand() % 26;data[i].name[k] = alphabet[key];}data[i].name[3] = '\0';}for (i = 0; i < *n;i++) {key = rand() % 20;for (int k = 0; k < 10; k++) {data[i].address[k] = country[key].data[k];}}for (i = 0; i < *n;) {temp_tel[0] = '1';for (int k = 1; k < 11; k++) {key = rand() % 10;temp_tel[k] = num[key];}temp_tel[11] = '\0';//写一个整数到磁盘文件flag = 1;if (isTelRepeated(temp_tel)) {flag = 0;break;}if (flag) {for (int k = 0; k < 11; k++) {data[i].tel[k] = temp_tel[k];}i++;}}for (i = 0; i < *n; i++) {fprintf(fp, "%d ", i + 1);  //写一个整数到磁盘文件fprintf(fp, "%s ", data[i].name);  //写一个整数到磁盘文件fprintf(fp, "%s ", data[i].address);  //写一个整数到磁盘文件fprintf(fp, "%s\n", data[i].tel);  //写一个整数到磁盘文件}fclose(fp);
}void initCountry() {FILE *fp;char temp[10];if ((fp = fopen("/Users/xiaoyee/Desktop/数据结构实验作业/实验报告/电话号码查询系统/1/Country_data.txt", "r")) == NULL) {printf("can't open the file!\n");exit(0);}for (int i = 0; i < 20; i++) {fscanf(fp, "%s", temp);for (int j = 0; j < 10; j++) {country[i].data[j] = temp[j];}}
}int isTelRepeated(char tel[]) {FILE *fp;char temp_tel[11];if ((fp = fopen("/Users/xiaoyee/Desktop/数据结构实验作业/实验报告/电话号码查询系统/1/TelDataSet_10000.txt", "r")) == NULL) {printf("can't open the file!\n");exit(0);}for (int i = 1; i <= N; i++) {fscanf(fp, "%s", temp_tel);if (strcmp(tel, temp_tel) == 0) {return 1;}}return 0;
}

（2）电话号码查询系统代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define NIL -1   //定义初始值
#define M 13333    //表长
#define N 10000     //关键字个数
// α=0.75typedef long keytype;
//散列表结点类型
typedef struct {int no;  //编号char *name;//名字char *address;//地址char *tel;//电话号码
} NODE;typedef struct pos {keytype pos;int flag;struct pos *next;
} POS;//初始化哈希表，将姓名和电话号码初始化！
void init(POS *table);int increment(int i);//某种探测方法int HASH_1(keytype key, int i);//将某键值转换成位置
//在散列表中搜索指定的键值
int search_tel(POS *table, char *tel, int *pos);//在散列表中搜索指定的键值
int search_name(POS *table, char *name, int *pos);//pos返回键值的位置
//将一个关键字添加到哈希表中（以电话号码为关键字）
void insert_tel(POS *table_tel, int no, char *name);//将一个关键字添加到哈希表中（以姓名为关键字）
void insert_name(POS *table_name, int no, char *tel);//void insert_pos(POS *table_name, int i, int pos);//创建哈希表（以电话号码为关键字）
void creat(NODE *htable);//将姓名转化为数字
long converse_name(char *name);//输出想要搜索的关键字的相关信息
void prn(NODE *htable, int no);//输出哈希表
void prnnn(NODE *htable, POS *table_name, int pos);//成功查找的ASL
float success_ASL();//失败查找的ASL
float fail_ASL();
//*******************************************************
//除留余数法作为散列函数，线性探测法解决冲突
//*******************************************************void menu();//********************************************************
//主函数
//********************************************************
NODE htable[N];//定义结点表
POS table_tel[M];//定义哈希表(以电话号码为关键字)
POS table_name[M];//定义哈希表(以姓名为关键字)
int main() {int op;//菜单选择int i;int pos;char *tel;char *name;init(table_tel);    //哈希表初始化init(table_name);    //哈希表初始化creat(htable);menu();scanf("%d", &op);printf("----------------------------------------------\n");while (op != 3) {switch (op) {case 1: {tel = (char *) malloc(sizeof(char));printf("请输入你想要查询的电话号码:");scanf("%s", tel);i = search_tel(table_tel, tel, &pos);if (i) {  //搜索指定键值printf("找到该电话号码！！！\n");printf("成功查找的平均查找长度ASL:%f\n", success_ASL());prn(htable, table_tel[pos].pos);//table_tel[pos].pos=no} else {printf("未找到该电话号码！！！\n");printf("失败查找的平均查找长度ASL:%f\n", fail_ASL());}}break;case 2: {//?name = (char *) malloc(sizeof(char));printf("请输入你想要查询的姓名:");scanf("%s", name);i = search_name(table_name, name, &pos);//在散列表中查找被插入的键值if (i) {  //搜索指定键值printf("找到该姓名！！！\n");printf("成功查找的平均查找长度ASL:%f\n", success_ASL());if (table_name[pos].flag != 1)prnnn(htable, table_name, pos);elseprn(htable, table_name[pos].pos);//table_name[pos].pos=no} else {printf("未找到该姓名！！！\n");printf("失败查找的平均查找长度ASL:%f\n", fail_ASL());}}break;case 3:exit(0);default: {printf("您输入的操作不合法，请重新输入！\n");fflush(stdin);//防止不断从缓冲区取数，造成循环break;}}printf("\n");menu();scanf("%d", &op);}return 0;
}//********************************************************
//初始化哈希表
//********************************************************
void init(POS *table) {POS *p = table;for (; p < table + M; p++) {p->pos = NIL;//初始化表元素的键值p->flag = 0;p->next = NULL;}
}
//********************************************************
//开放定址的哈希函数:折叠法
//构造哈希函数
//********************************************************//********************************************************
//开放定址的哈希函数:除留余数法
//构造哈希函数
//********************************************************
int increment(int i)  //某种探测方法
{return i;  //增量为i
}int HASH_1(keytype key, int i)  //将某键值转换成位置
{return ((int) (key % M) + increment(i)) % M;   //线性探测
}//********************************************************
//在散列表中搜索指定的键值
//pos返回键值的位置
//********************************************************
int search_tel(POS *table_tel, char *tel, int *pos) {int i = 0;long s;do {s = atol(tel);//字符串电话号码转换为long型数据*pos = HASH_1(s, i);//开放定址的散列函数if (table_tel[*pos].pos == NIL)return 0;   //表未满，没找到if (strcmp(htable[table_tel[*pos].pos].tel, tel) == 0) return *pos; //找到} while (++i < M);return -1; //表满，没找到
}//将姓名转化为数字
long converse_name(char *name) {long temp = 0;int i = 10000;while (*name != '\0') {temp += ((*name - 'a') * i);i /= 100;name++;}return temp;
}int search_name(POS *table_name, char *name, int *pos) {int i = 0;long k;k = converse_name(name);do {*pos = HASH_1(k, i);//开放定址的散列函数if (table_name[*pos].pos == NIL)return 0;   //表未满，没找到if (strcmp(htable[table_name[*pos].pos].name, name) == 0) return *pos; //找到} while (++i < M);return -1; //表满，没找到
}//********************************************************
//将一个关键字添加到哈希表中
//********************************************************
void insert_tel(POS *table_tel, int no, char *tel) {//将一个关键字添加到哈希表中int i;int pos;i = search_tel(table_tel, tel, &pos);  //在散列表中查找被插入的键值if (i == 0) {  //表不满，该结点不存在table_tel[pos].pos = no;} else if (i == -1)printf("表满,无法插入!\n");else printf("关键字重复，无法插入!\n");
}void insert_name(POS *table_name, int no, char *name) {int i, pos;int t = 1;long k;i = search_name(table_name, name, &pos);  //在散列表中查找被插入的键值if (i == 0) {  //表不满，该结点不存在table_name[pos].pos = no;table_name[pos].flag = 1;} else if (i == -1)printf("表满,无法插入!\n");else {k = converse_name(name);table_name[i].flag++;//重复的次数+1do {pos = HASH_1(k, t);//开放定址的散列函数if (table_name[pos].flag == 0) {table_name[pos].pos = no;table_name[pos].flag = 1;//insert_pos(table_name, i, pos);break;}} while (++t < M);// printf("关键字重复，无法插入!\n");}
}
/*
void insert_pos(POS *table_name, int i, int position) {Pos p;p = table_name[i].next;while (p != NULL)p = p->next;p->next = &table_name[position];printf(p->next->flag);
}*///********************************************************
//从磁盘文件中读入数据，并存入结点表中
//********************************************************
void creat(NODE *htable) {FILE *fp;int no;char *name;char *address;char *tel;if (M < N) {printf("散列因子>1,结点个数超过表长,无法创建!\n");return;}if ((fp = fopen("/Users/xiaoyee/Desktop/数据结构实验作业/实验报告/电话号码查询系统/1/FinalDataSet_10000.txt", "r")) == NULL) {printf("can't open the file!!");exit(0);}while (!(feof(fp))) {name = (char *) malloc(sizeof(char));address = (char *) malloc(sizeof(char));tel = (char *) malloc(sizeof(char));//非常重要！！！fscanf(fp, "%d", &no);fscanf(fp, "%s", name);fscanf(fp, "%s", address);fscanf(fp, "%s", tel);htable[no].no = no;htable[no].name = name;htable[no].address = address;htable[no].tel = tel;  //找到开放位置,将键值加入insert_tel(table_tel, no, tel);insert_name(table_name, no, name);}fclose(fp);
}//********************************************************
//输出哈希表
//********************************************************
void prn(NODE *htable, int no) {printf("编号：%d\t", htable[no].no);printf("姓名：%s\t", htable[no].name);printf("城市：%s\t", htable[no].address);printf("城市：%s\n", htable[no].tel);printf("\n");
}//输出哈希表
void prnnn(NODE *htable, POS *table_name, int pos) {int no = 0;int i = pos;POS *p;p = (POS *) malloc(sizeof(POS));//令p为table_name[i],即重复元素值相同的第一个元素p->pos = table_name[pos].pos;p->flag = table_name[pos].flag;p->next = table_name[pos].next;printf("查询到该姓名在该电话号码查询系统中重复!\n");printf("现将所有是该姓名的人查询如下：\n");for (int k = 0; k < table_name[pos].flag;) {if (strcmp(htable[table_name[pos].pos].name, htable[table_name[i].pos].name) == 0) {no = table_name[i].pos;printf("编号：%d\t", htable[no].no);printf("姓名：%s\t", htable[no].name);printf("城市：%s\t", htable[no].address);printf("城市：%s\n", htable[no].tel);k++;}i++;}
}//成功查找的ASL
float success_ASL() {float i = 1 - (1.0 * N) / M;return (1 + 1 / i) / 2;
}//失败查找的ASL
float fail_ASL() {float a = (1.0 * N) / M;float i = 1 - a;return (1 + 1 / (i * i)) / 2;
}/*void prnnn(NODE *htable) {NODE *p = htable;for (; p < htable + M; p++)if (p->tel != NIL) {printf("编号：%d\t", p->no);printf("姓名：%s\t", p->name);printf("城市：%s\t", p->address);printf("电话号码：%ld\t", p->tel);//如果某地址不开放,则输出相应的键值}printf("\n");
}*/void menu() {printf("----------------------------------------------\n");printf("*************欢迎使用电话号码查询系统*************\n");printf("----------------------------------------------\n");printf("请选择你想要进行的查询：");printf(" 1.以电话号码为关键字进行查询\n");printf("\t\t\t\t    2.以姓名为关键字进行查询\n");printf("\t\t\t\t    3.退出\n");printf("----------------------------------------------\n");printf("请选择你想要进行的操作：");