《程序设计综合设计》课程设计 |
您所在的位置:网站首页 › 进京电话咨询电话号码查询系统官网首页 › 《程序设计综合设计》课程设计 |
2.问题描述
1、设每个记录有下列数据项:电话号码、用户名、地址; 2、从键盘输入各记录,分别以电话号码和用户名为关键字建立哈希表; 3、查找并显示给定电话号码的记录; 4、查找并显示给定用户名的记录。 5、在哈希函数确定的前提下,使用各种不同类型处理冲突的方法(开放定址法、 拉链法),讨论平均查找长度的变化。 3.需求分析 3.1 数据需求电话号码查询系统需要存储的数据项有电话号码、用户名、地址三个字段。 3.2 基本功能需求1.需要使用两个解决冲突的方式来进行hash存储 2.分别使用姓名和电话号两个属性进行hash存储。 3.可以插入新的用户记录,包括电话号码、用户名、地址三个字段。 4.可以查询用户记录: 可以通过电话号码或姓名来查询用户记录。 5.开放定址法: 使用数组存储数据,当发生冲突时,通过查找下一个空闲单元来解决冲突。 6.链地址法: 使用链表存储数据,当发生冲突时,将新数据插入链表中,通过链表来解决冲突。 3.3 非功能性需求 用户界面需求:简洁、易用、易懂、友好的用户界面。 硬件要求:装有Visual Studio 2019的计算机。 可靠性需求:保证用户在正常使用本系统时,用户的操作或误操作不会产生数据的丢失。 4.概要设计 4.1 数据结构开放定址法: 使用 HashNode 类型的数组来存储数据,每个元素包含一个Record_1类型的data字段和一个int类型的is_empty字段。 链地址法: 使用结构体Record_2存储数据,每个结构体包含电话号码、用户名、地址三个字段和一个指向下一个结构体的指针next。 4.2 系统包含的函数 hash_func_1: 使用简单的哈希函数计算给定字符串的哈希值search_by_phone_1: 通过电话号码在哈希表中搜索记录,并打印该记录的姓名和地址search_by_name_1: 通过姓名在哈希表中搜索记录,并打印该记录的电话号码和地址insert_data_by_phone_1: 在哈希表中插入一条新记录,根据电话号码计算哈希值print_avg_lengths_phone_1: 打印哈希表中每个桶的平均长度,根据电话号码计算哈希值print_avg_lengths_name_1: 打印哈希表中每个桶的平均长度,根据姓名计算哈希值insert_data_by_name_1: 在哈希表中插入一条新记录,根据姓名计算哈希值init_hash_table_2: 初始化哈希表,将所有元素的next指针设为NULLhash_by_phone_2: 计算电话号码的哈希值hash_by_name_2: 计算姓名的哈希值display_record_2: 打印一条记录的电话号码,姓名和地址insert_by_phone_2: 插入一条新记录,根据电话号码计算哈希值insert_by_name_2: 插入一条新记录,根据姓名计算哈希值search_by_phone_2: 通过电话号码在哈希表中搜索记录,并打印该记录的电话号码,姓名和地址search_by_name_2: 通过姓名在哈希表中搜索记录,并打印该记录的电话号码,姓名和地址print_avg_lengths_by_name_2: 打印哈希表中每个桶的平均长度,根据姓名计算哈希值print_avg_lengths_by_phone_2: 打印哈希表中每个桶的平均长度,根据电话号码计算哈希值main2(): 主函数,用于测试哈希表2main1(): 主函数,用于测试哈希表1 4.3 函数间的关系 hash_func_1, hash_by_phone_2, hash_by_name_2 这三个函数都是用于计算哈希值的,hash_func_1是用来计算第一个哈希表中哈希值的,hash_by_phone_2和hash_by_name_2是用来计算第二个哈希表中哈希值的。insert_by_phone_2和insert_by_name_2这两个函数是用来在第二个哈希表中插入记录的,它们使用了hash_by_phone_2和hash_by_name_2函数来计算哈希值search_by_phone_1,search_by_name_1,search_by_phone_2, search_by_name_2这四个函数都是用来在哈希表中搜索记录的,它们分别对应第一个哈希表和第二个哈希表中搜索电话号码和姓名。display_record_2函数是用来打印第二个哈希表中搜索到的记录的电话号码,姓名和地址。init_hash_table_2函数是用来初始化第二个哈希表的,它会将所有的链表指针都设置为NULL。main2()和main1()是程序的主入口,它们分别调用了第一个哈希表和第二个哈希表的插入,查询和显示函数来测试哈希表的功能。 4.4 系统功能模块图 5.详细设计 5.1 结构体的详细定义typedef struct { char phone[20];//电话号码 char name[20];//姓名 char address[100];//地址 } Record_1; typedef struct {//结构体定义 Record_1 data; int is_empty; } HashNode; struct Record_2 { char phone[20]; char name[20]; char address[100]; struct Record_2* next; } 5.2 系统函数详细介绍 hash_func_1: 使用简单的哈希函数计算给定字符串的哈希值search_by_phone_1: 通过电话号码在哈希表中搜索记录,并打印该记录的姓名和地址search_by_name_1: 通过姓名在哈希表中搜索记录,并打印该记录的电话号码和地址insert_data_by_phone_1: 在哈希表中插入一条新记录,根据电话号码计算哈希值print_avg_lengths_phone_1: 打印哈希表中每个桶的平均长度,根据电话号码计算哈希值print_avg_lengths_name_1: 打印哈希表中每个桶的平均长度,根据姓名计算哈希值insert_data_by_name_1: 在哈希表中插入一条新记录,根据姓名计算哈希值init_hash_table_2: 初始化哈希表,将所有元素的next指针设为NULLhash_by_phone_2: 计算电话号码的哈希值hash_by_name_2: 计算姓名的哈希值display_record_2: 打印一条记录的电话号码,姓名和地址insert_by_phone_2: 插入一条新记录,根据电话号码计算哈希值insert_by_name_2: 插入一条新记录,根据姓名计算哈希值search_by_phone_2: 通过电话号码在哈希表中搜索记录,并打印该记录的电话号码,姓名和地址search_by_name_2: 通过姓名在哈希表中搜索记录,并打印该记录的电话号码,姓名和地址print_avg_lengths_by_name_2: 打印哈希表中每个桶的平均长度,根据姓名计算哈希值print_avg_lengths_by_phone_2: 打印哈希表中每个桶的平均长度,根据电话号码计算哈希值main2(): 主函数,用于测试哈希表2main1(): 主函数,用于测试哈希表1 5.3 系统功能模块介绍本系统包括两个模块: 一个是线性探测模块(如图5-3-1),一个是拉链法模块(如图5-3-2)。 图5-3-1线性探测法模块流程图
图5-3-2 拉链法模块流程图 5.4 各相关数据结构、算法间的对比 search_by_phone_1: 根据电话号码在第一个哈希表中查找记录。首先使用hash_func_1函数计算电话号码的哈希值,然后在哈希表中循环查找,直到找到对应的记录或者遍历完整个哈希表。如果找到,则输出记录的姓名和地址,如果没有找到,则输出没有找到该人员信息。search_by_name_1: 根据姓名在第一个哈希表中查找记录。首先使用hash_func_1函数计算姓名的哈希值,然后在哈希表中循环查找,直到找到对应的记录或者遍历完整个哈希表。如果找到,则输出记录的电话号码和地址,如果没有找到,则输出没有找到该人员信息。insert_data_by_phone_1: 根据电话号码在第一个哈希表中插入记录。首先使用hash_func_1函数计算电话号码的哈希值,然后在哈希表中循环查找空闲位置插入记录。如果遍历了整个哈希表都没有空闲位置,则输出错误信息。insert_data_by_name_1: 根据姓名在第一个哈希表中插入记录。首先使用hash_func_1函数计算姓名的哈希值,然后在哈希表中循环查找空闲位置插入记录。如果遍历了整个哈希表都没有空闲位置,则输出错误信息。print_avg_lengths_phone_1:计算第一个哈希表中电话号码的平均查找长度。这个函数会遍历整个哈希表,查找每个记录对应的电话号码的查找长度,然后计算总长度的平均值。print_avg_lengths_name_1: 与print_avg_lengths_phone_1类似,计算第一个哈希表中姓名的平均查找长度。insert_by_phone_2: 根据电话号码在第二个哈希表中插入记录。首先hash_by_phone_2函数计算电话号码的哈希值,然后在对应的哈希值位置插入新节点。search_by_phone_2根据电话号码在第二个哈希表中查找记录:首先使用hash_by_phone_2函数计算电话号码的哈希值。根据哈希值找到相应的链表在链表中遍历每一个节点,如果找到匹配的电话号码输出信息,否则输出没有找到。insert_by_name_2: 根据姓名在第二个哈希表中插入记录。首先hash_by_name_2函数计算姓名的哈希值,然后在对应的哈希值位置插入新节点。search_by_name_2根据姓名在第二个哈希表中查找记录:首先使用hash_by_name_2函数计算姓名的哈希值。根据哈希值找到相应的链表在链表中遍历每一个节点,如果找到匹配的姓名输出信息,否则输出没有找到。数据结构对比: 线性探测法(Open Addressing):当发生冲突时,在哈希表中往后探测一个单位(如+1或+2),直到找到一个空位置。优点是在哈希表中使用空间更紧凑,缺点是当哈希表较满时,查询性能会受到影响。 拉链法(Chaining):当发生冲突时,将哈希值相同的记录放入一个链表中。优点是当哈希表较满时,查询性能依然较好,缺点是需要额外的空间来存储改进思路:开放定址法中可以使用双重散列函数,以减少冲突的可能。界面应该设计更加人性化,方便非专业人员使用,以及提高代码的健壮性,对程序进行不断的测试,测试出程序中,不严谨问题。 6.调试分析本软件是基于Windows的编程开发,所以,软件调试必须在Windows环境下进行。调试前须做好准备工作: 1.需要安装Visual Studio 2019的计算机一台;配置好之后,在Visual Studio 2019环境下进行软件的调试。 2.测试数据:冲突选择输入: 在“main”模块中,根据控制台主界面提示,选择解决冲突的方式,键入数字1,会选择线性探测法(开放定址法),键入2会选择拉链法。 在“查询数据”模块中,根据主界面提示,键入数字2,确定,再按提示进行操作测试,键入姓名如小黑,确定,程序显示该姓名相关记录的所有信息,如果没有找到该姓名的记录,程序提示“该人员没有找到”。 3.算法改进设想:开放定址法中可以使用双重散列函数,以减少冲突的可能。界面应该设计更加人性化,方便非专业人员使用,以及提高代码的健壮性,对程序进行不断的测试,测试出程序中,不严谨问题。 4.使用说明 1.电话号码为关键字建立的哈希表,按电话号码查询,线性探测法解决冲突,成功找到该人员并打印该人员信息和平均查找成功和失败长度。(如图7-1)图7-1 2.电话号码为关键字建立的哈希表,按电话号码查询,拉链法解决冲突,成功找到该人员并打印该人员信息和平均查找成功和失败长度。(如图7-2)如图7-2 3.姓名为关键字建立的哈希表,按姓名查询,线性探测法解决冲突,成功找到该人员并打印该人员信息和平均查找成功和失败长度。(如图7-3)如图7-3 4.姓名为关键字建立的哈希表,按姓名查询,拉链法解决冲突,成功找到该人员并打印该人员信息和平均查找成功和失败长度。(如图7-4)如图7-4 5.电话号码为关键字建立的哈希表,按电话号码查询,线性探测法解决冲突,没有找到该人员,打印平均查找成功和失败长度。(如图7-5)(如图7-5) 6.电话号码为关键字建立的哈希表,按电话号码查询,拉链法解决冲突,没有找到该人员,打印平均查找成功和失败长度(如图7-6)
(如图7-6) 7.源代码(首尾一小部分,中间部分略)#include #include #include #define SIZE 7 typedef struct { char phone[20];//电话号码 char name[20];//姓名 char address[100];//地址 } Record_1; typedef struct {//结构体定义 Record_1 data; int is_empty; } HashNode; struct Record_2 { char phone[20]; char name[20]; char address[100]; struct Record_2* next; }; unsigned int hash_func_1(const char* str) {//使用简单的哈希函数计算给定字符串的哈希值 unsigned int hash = 0; while (*str) { hash = hash * 31 + *str++; } return hash % SIZE; } void insert_data_by_phone_1(HashNode table[], Record_1 record_1) {//在哈希表中插入一条新记录,根据电话号码计算哈希值(第一个哈希表) unsigned int index = hash_func_1(record_1.phone); int cnt = 1; while (1) { if (table[index].is_empty == 0) { table[index].data = record_1; table[index].is_empty = 1; return; } if (strcmp(table[index].data.phone, record_1.phone) == 0) { printf("该电话 %s 已经存在\n", record_1.phone); return; } index = (index + 1) % SIZE; cnt++; if (cnt == SIZE) { printf("hash表已满!\n"); return; } } } int search_by_phone_1(HashNode table[], const char* phone) {//通过电话号码在哈希表中搜索记录,并打印该记录的姓名和地址(第一个哈希表) unsigned int index = hash_func_1(phone); int cnt = 0; while (1) { if (table[index].is_empty == 0) { printf("没有找到该人员信息!\n"); return cnt; } if (strcmp(table[index].data.phone, phone) == 0) { printf("姓名: %s, 地址: %s\n", table[index].data.name, table[index].data.address); return cnt; } index = (index + 1) % SIZE; cnt++; if (cnt == SIZE) { printf("没有找到该人员信息!\n"); return cnt; } } } int search_by_phone_11(HashNode table[], const char* phone) { unsigned int index = hash_func_1(phone); int cnt = 0; while (1) { if (table[index].is_empty == 0) { //printf("没有找到该人员信息!\n"); return cnt; } if (strcmp(table[index].data.phone, phone) == 0) { //printf("姓名: %s, 地址: %s\n", table[index].data.name, table[index].data.address); return cnt; } index = (index + 1) % SIZE; cnt++; if (cnt == SIZE) { //printf("没有找到该人员信息!\n"); return cnt; } } } void print_avg_lengths_phone_1(HashNode table[]) {//打印哈希表中每个桶的平均长度,根据电话号码计算哈希值(第一个哈希表) char phone[20] = "qwer"; int total_count = 0; int total_length = 0; int fail_count = 0; int fail_length = 0; for (int i = 0; i < SIZE; i++) { if (table[i].is_empty == 1) { total_count++; total_length += search_by_phone_11(table, table[i].data.phone); fail_length += search_by_phone_11(table, phone); } } printf("平均查找成功长度: %f\n", (float)total_length / total_count);//计算第一个哈希表中电话号码的平均查找长度(第一个哈希表) printf("平均查找失败长度: %f\n", (float)fail_length / SIZE); } (中间部分略)。。。。。。 int main() { int choice; while (1) { printf("\n-------------------------------------------------------------\n"); printf("*****************欢迎使用电话号码查询系统********************\n"); printf("-------------------------------------------------------------\n"); printf("请选择解决冲突的方法:\n"); printf("\t\t\t\t\t\t1.开放定址法\n"); printf("\t\t\t\t\t\t2.拉链法\n"); printf("\t\t\t\t\t\t请选择!\n"); printf("请输入:"); scanf("%d", &choice); if (choice == 1) { main1(); } else if (choice = 2) { main2(); } else { printf("输入错误!"); } } } 8.设计总结在进行本次实验时,我学会了使用哈希表的相关算法,包括线性探测法和拉链法,并对比了这两种算法在实现上的不同。我还学会了在 C 语言中使用结构体来存储数据,以及如何使用链表来实现拉链法。 在实验过程中,我首先使用了线性探测法实现哈希表,并在该算法的基础上改进了拉链法的实现。通过对比两种算法的实现,我发现拉链法更加灵活,能够解决线性探测法中的冲突问题。 在实验中我还学会了如何对哈希表中的数据进行插入、查找等操作。通过实验,我们深刻地理解了哈希表在实际应用中的重要性,并增强了对算法实现的理解。 在实验过程中遇到了许多问题,包括: 计算姓名和电话号码的哈希值:使用hash_by_phone_2函数计算电话号码的哈希值,使用hash_by_name_2函数计算姓名的哈希值。int hash_by_phone_2(char* phone) {//计算电话号码的哈希值 int hash = 0; for (int i = 0; i < strlen(phone); i++) { hash = (hash * 10 + phone[i] - '0') % SIZE; } return hash; } int hash_by_name_2(char* name) {//计算姓名的哈希值 int hash = 0; for (int i = 0; i < strlen(name); i++) { hash = (hash * 26 + name[i] - 'A') % SIZE; } return hash; } 平均查找成功和失败长度的计算:如用print_avg_lengths_phone_1函数计算第一个哈希表中电话号码的平均查找长度。这个函数会遍历整个哈希表,查找每个记录对应的电话号码的查找长度,然后计算总长度的平均值,其中平均查找成功长度=对应的电话号码的查找成功总长度/哈希表元素个数;平均查找失败长度=对应的电话号码的查找失败总长度/哈希表表长。调试过程中,出现返回值scanf被忽略,取消NULL指针对new_node的引用等警告,通过关闭配置属性里的SDL检查解决等等。不足之处:没有实现用txt文件来读出与写入,保存学生信息,还有不熟练怎么向他人讲述清楚自己的代码等等,这些还需要自己下去更多的查阅资料和练习。比较好的部分是,实现了不同冲突解决办法的平均长度比较。总之,本次实验让我深入理解了哈希表的算法原理,并且提高了我的编程能力,为以后的算法学习打下了坚实的基础。 9.参考文献[1]Robert L. Kruse,Data Structures And Program Design in C++,高等教育出版社,2001.5. [2]严蔚敏等编著,数据结构(C 语言版),清华大学出版社,1997.4; [3]赵文静等编著,数据结构与算法,科学出版社,2005.08; [4]Clifford,A.Shaffer编著,数决结构与算法分析(C++版),电子工业出版社,2005.7 [5] 赵文静编著,数据结构-C++语言描述,西安交通大学出版社,1999.01 [6] 孙鑫,于安萍编著,VC++深入详解,电子工业出版社,2007.7 [7] COHOON & DAVIDSON编著,C++程序设计,清华大学出版社,2005.8 |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |