网站界面,微商城是什么意思,台州工程建设信息网站,江桥网站建设题目二 #xff1a;散列表的设计与实现
2.1问题描述
设计散列表实现电话号码查找系统#xff0c;使得平均查找长度不超过2基本要求 #xff08;1#xff09;设每个记录有下列数据项#xff1a;电话号码、用户名、地址#xff1b; #xff08;2#xff09;从键盘输入各…题目二 散列表的设计与实现
2.1问题描述
设计散列表实现电话号码查找系统使得平均查找长度不超过2基本要求 1设每个记录有下列数据项电话号码、用户名、地址 2从键盘输入各记录以电话号码为关键字建立散列表 3采用一定的方法解决冲突 4查找并显示给定电话号码的记录
2.2.算法设计与分析
2.2.1设计思路分析 基本思路 1构建哈希表需要构造一个哈希函数确定一个合适的处理冲突的方法 2按照电话号码查找并输出 3将哈希表按序存进文件中 基本思想 1 哈希表是根据关键码而直接进行访问的数据结构也就是说它通过把关键码值映射到表中一个位置来访问记录以加快查找的速度。这个映射函数叫做散列函数存放记录的数组叫做散列表 2给定表M存在函数fkey对任意给定的关键子值key代入函数后能得到包含该关键字的记录在表中的地址则称表M为哈希表函数fkey为哈希函数。 3 二次探测再散列法:若发生冲突则按照1²-1²2²-2²……方式进行探测再散列的方法。
2.2.2设计程序流程图 进入程序进行功能选择选择1进行存入电话号码构建哈希表如果存在冲突解决冲突再录入不存在直接录入信息。选择0查找电话号码怎么解决冲突就按相应的方法查找。所有功能执行完后返回选择0退出程序程序结束。 2.2.3数据结构定义
typedef struct record //定义一条记录的结构体
{char Number[20]; char Name[20];char Address[20];
}Record;typedef struct Hash //定义一个散列表
{Record *data; //存访多条记录的数组int cnt; int size; //数组大小
}*HashTable, HashElem;2.2.4算法的时间复杂度分析 整个程序的时间复杂度看哈希表在解决冲突时的时间复杂度 解决冲突 最差的时间复杂度O(n),当所有数据被填满时 最好的时间复杂度O(1)没有冲突的时候.
2.3源程序清单
hash.h文件
#define _CRT_SECURE_NO_WARNINGS
#includeiostream
#includecstdio
#includecstdlib
#includecstring#define MAXSIZE 50using namespace std; typedef struct record //定义一条记录的结构体
{char Number[20]; char Name[20];char Address[20];
}Record;typedef struct Hash //定义一个散列表
{Record *data; //存访多条记录的数组int cnt; int size; //数组大小
}*HashTable, HashElem;void savenumb(HashTable numbertable, Record record[]); //存访函数
void findnumb(HashTable numbertable); //查询函数function.cpp文件
#define _CRT_SECURE_NO_WARNINGS
#includehash.hint Czy 1;
//哈希函数将电话号码每一位求和
int GetHashKey(char ar[])
{int len strlen(ar); //计算电话号码的长度int key 0;for (int i 0; ilen; i){ key ar[i] - 0; //key总和数字字符减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;for (int i 0; in; i){key GetHashKey(record[i].Number); //接受每个电话返回来的地址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 key GetHashKey(PhoneNumber); //得到该元素的最初地址位置if (strcmp(table-data[key].Number, PhoneNumber)){ //如果该位置上的数与给定的数不相等则考虑冲突寻址for (Czy 1; Czy MAXSIZE; Czy){if (Czy % 2 0) {//strcmpstr1str2//当str1的字典序大于str2时返回一个一个正数 小于负数等于0if (!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;//由于是减法要注意负数不能取模 //如果取差后为负数则不做处理Czy1//不是负数判断值是否与当前地址值相等if (!strcmp(PhoneNumber, table-data[(key - (Czy / 2)*(Czy / 2)) % MAXSIZE].Number)){key (key - (Czy / 2)*(Czy / 2)) % MAXSIZE;break;}}}}return key;
}
//将哈希表存入文件中 void GoToFile(HashTable table)
{FILE *fp fopen(Output.txt, w); //打开文件Output.txtfor (int i 0; i MAXSIZE; i) //遍历整个散列表if (table-data[i].Name[0] ! 0) //如果名字不为空则写入文件fprintf(fp, %s %s %s\n, table-data[i].Name, table-data[i].Number, table-data[i].Address);//printf(%s %s %s\n,table-data[i].Name,table-data[i].Number,table-data[i].Address); fclose(fp); //关闭文件
}void findnumb(HashTable numbertable){ //查询函数int key 0;//输入并寻找PhoneNumber必须存在表中 char PhoneNumber[20];printf(请输入你想找的电话:\n);cin PhoneNumber;cout 给定电话号码为 endl PhoneNumber endl;key SerchKey(numbertable, PhoneNumber);if (!strcmp(numbertable-data[key].Number, PhoneNumber)){printf(找到的电话信息为:\n);}else{printf(\n没有该电话号码\n);return;}cout numbertable-data[key].Name numbertable-data[key].Number numbertable-data[key].Address endl;}void savenumb(HashTable numbertable,Record record[]){ //保存函数int k;//输入数据 组数及 各个数据 //freopen(Data.txt,r,stdin);printf(你想要存入几个人的电话\n);cin k;while(k 10){printf(一次至多只能存放10人\n);printf(请重新输入:\n);cin k;}for (int i 0; i k; i){printf(请输入电话\n);cin record[i].Number;printf(请输入姓名\n);cin record[i].Name;printf(请输入住址\n);cin record[i].Address;}//创建哈希表 CreateHashTable(numbertable, record, k);//存入文件中 GoToFile(numbertable);printf(保存成功\n);}Main.cpp文件
#includehash.h
void menu2(){printf(****************************\n);printf(*欢迎使用电话簿(散列表版本)*\n);printf(****** 1存入电话号码 *******\n);printf(****** 2查找电话号码 *******\n);printf(****** 0 退出程序 *******\n);printf(****************************\n);
}void menu(){//定义及初始化 Record record[50]; //定义结构体数组可以存放50个元素的信息HashElem table; //散列表结构体变量HashTable numbertable; //散列表结构体指针numbertable table; //给结构体指针赋初值numbertable-data (Record*)malloc(sizeof(record[0])*MAXSIZE);memset(numbertable-data, 0, sizeof(record[0])*MAXSIZE);numbertable-size MAXSIZE;numbertable-cnt 0;int input;do{menu2();printf(请输入你想要执行的操作\n);scanf(%d, input);switch (input){case 1:savenumb(numbertable, record);break;case 2:findnumb(numbertable);break;case 0:printf(再见\n);break;default:printf(你的输入有误请重新输入\n);break;}} while (input);}int main(){menu();system(pause);return 0;
}2.4执行结果
1存入电话号码 2查找电话号码 0退出程序
2.5存在问题分析
电话簿中无法分辨电话相同的情况。 2 电话簿没有一个图形化界面用户需要手动输入相关命令无法实现鼠标点击
2.6结论
基本实现了电话簿的添加和查找功能
