电话号码查询系统（数据结构之哈希表）_电话号码查询数据结构哈希表-程序员宅基地
哈希表
哈希表（Hash Table）是一种根据关键字直接访问内存存储位置的数据结构。通过哈希表，数据元素的存放位置和数据元素的关键字之间建立起某种对应关系，建立这种对应关系的函数称为哈希函数。
1.哈希函数的构造方法
假设要存储的数据元素个数为n，设置一个长度为m（m≥n）的连续存储单元，分别以每个数据元素的关键字 Ki(0<= i <=n-1) 为自变量，通过哈希函数 hash(Ki) 把 Ki 映射为内存单元的某个地址 hash(ki)，并将该数据元素存储在该内存单元中。
从数学的角度来看，哈希函数实际上是关键字到内存单元的映射，因此我们希望用哈希函数通过尽量简单的运算，使得通过哈希函数计算出的哈希地址尽量均匀地被映射到一系列的内存单元中。
构造哈希函数有三个要点：
第一，运算过程要尽量简单高效，以提高哈希表的插入和检索效率；
第二，哈希函数应该具有较好的散列性，以降低哈希冲突的概率；
第三，哈希函数应具有较大的压缩性，以节省内存。
2.什么是冲突？怎么解决冲突？
在构造哈希表时，存在这样的问题，对于两个不同的关键字，通过我们的哈希函数计算哈希地址时却得到了相同的哈希地址
1）开放定址法
它是一类以发生哈希冲突的哈希地址为自变量，通过某种哈希函数得到一个新的空闲内存单元地址的方法（如图），开放定址法的哈希冲突函数通常是一组；
2）链表法
当未发生冲突时，则直接存放该数据元素；当冲突产生时，把产生冲突的数据元素另外存放在单链表中。
电话号码查询系统（哈希表结构）
1.数据类型定义
typedef struct Imfo{
char name[20];
char num[20];
Imfo* nextData;
}Imfo;
typedef struct node{
Imfo* nextData;//利用链表法处理冲突
}HashTable[Max_num];
2.哈希函数
int HashFunction(Imfo Data){
//哈希函数，构造储存地址
int s=0;
s=(Data.num[3]-'0')+(Data.num[4]-'0')+(Data.num[5]-'0')+(Data.num[6]-'0')+(Data.num[7]-'0');
return s%47;
}
3.初始化空哈希表
int InitHash(HashTable &s){
//初始化一个空的哈希表
for(int i=0;i<50;i++){
s[i].nextData=NULL;//给nextData赋初值，方便设置条件
}
flag=1;//标志哈希表的建立
printf("创建成功！\n");
return OK;
}
4.初步储存5个联系人信息
int CreatHash(HashTable &s){
//初始化建立一个五位的哈希表
if(flag==0){
printf("未建立电话簿，请先建立！\n");
return ERROR;
}
printf("请输入~\n");
for(int i=0;i<5;i){
Imfo*p=(Imfo*)malloc(sizeof(Imfo));
scanf("%s",p->name);
scanf("%s",p->num);
if(addHash(s,p)==-1);
else i++;
}
printf("保存成功！\n");
return 1;
}
5.用头插法中插入元素
int addHash(HashTable &s,Imfo* Data){
//向哈希表中插入元素
int k=HashFunction(*Data);
Imfo*p=s[k].nextData;
while(p){
if(!strcmp(p->num,Data->num)){
printf("%s %s 该号码已存在！不能录入系统！\n",Data->name,Data->num);
return -1;
}
p=p->nextData;
}
Data->nextData=s[k].nextData;
s[k].nextData=Data;//利用头接法将新节点链如哈希表
return OK;
}
6.向哈希表中增加一个元素
int addOneHash(HashTable &s){
//向电话簿中添加一个联系人
if(flag==0){
printf("未建立电话簿，请先建立！\n");
return ERROR;
}
Imfo*q=(Imfo*)malloc(sizeof(Imfo));
printf("输入联系人姓名：");
scanf("%s",q->name);
printf("输入联系人电话：");
scanf("%s",q->num);
int k=HashFunction(*q);
Imfo*p=s[k].nextData;
while(p){
if(!strcmp(p->num,q->num)){
printf("%s %s 该号码已存在！不能录入系统！\n",q->name,q->num);
return -1;
}
p=p->nextData;
}
q->nextData=s[k].nextData;
s[k].nextData=q;
printf("添加成功！\n");
return OK;
}
7.删除一个元素
int delOneHash(HashTable &s){
//删除电话簿中一个联系人
if(flag==0){
printf("未建立电话簿，请先建立！\n");
return ERROR;
}
Imfo*q=(Imfo*)malloc(sizeof(Imfo));
Imfo*t=(Imfo*)malloc(sizeof(Imfo));;
printf("输入联系人姓名：");
scanf("%s",q->name);
printf("输入联系人电话：");
scanf("%s",q->num);
int k=HashFunction(*q);
Imfo*p=s[k].nextData;
t=s[k].nextData;
if(!t)printf("电话簿没有该联系人！\n");
if(!s[k].nextData->nextData&&!strcmp(s[k].nextData->num,q->num)){
s[k].nextData=NULL;
printf("删除成功！\n");
return OK;
}//该地址只有一个节点，s[k].nextData->nextData=null，且该节点就是需要删除的节点
else if(!s[k].nextData->nextData&&strcmp(s[k].nextData->num,q->num)){
printf("电话簿没有该联系人！\n");
return ERROR;
}//该地址只有一个节点，s[k].nextData->nextData=null，但该节点不是需要删除的节点
if(s[k].nextData->nextData&&!strcmp(s[k].nextData->num,q->num)){
s[k].nextData=s[k].nextData->nextData;
printf("删除成功！\n");
return OK;
}//该地址不只有一个节点，s[k].nextData->nextData！=null，且该节点就是需要删除的节点
while(p){
if(!strcmp(p->num,q->num)){
break;
}
t=p;
p=p->nextData;
}//p为移动节点，用来做判断条件，t为p的前驱节点，用来删除p所用
if(!p){
printf("电话簿没有该联系人！\n");
return ERROR;
}
else{
if(!p->nextData)t->nextData=NULL;//如果需要查找的节点是该链最后一个，直接使t->nextData=NULL
else t->nextData=p->nextData;
free(p);//释放p
printf("删除成功！\n");
}
return OK;
}
8.查询哈希表中的元素
int SearchHash(HashTable s){
//根据输入的关键字，查询联系人信息，并打印
if(flag==0){
printf("未建立电话簿，请先建立！\n");
return ERROR;
}
Imfo T;
printf("输入查询的电话号码：");
scanf("%s",T.num);
int k=HashFunction(T);
Imfo*p=s[k].nextData;
while(p){
if(!strcmp(p->num,T.num)){
printf("查找完毕！该联系人信息为：姓名：%s 电话号码：%s \n",p->name,p->num);
return OK;
}
p=p->nextData;
}
printf("没有找到该联系人\n");
return ERROR;
}
完整的代码：
#include <iostream>
#include<stdio.h>
#define OK 1
#define ERROR 0
#include<malloc.h>
#include<string.h>
using namespace std;
#define Max_num 50
typedef struct Imfo{
char name[20];
char num[20];
Imfo* nextData;
}Imfo;
typedef struct node{
Imfo* nextData;
}HashTable[Max_num];
int flag=0;//标记电话薄已经建立
int HashFunction(Imfo Data);//哈希函数，构造储存地址
int InitHash(HashTable &s);//初始化一个空的哈希表
int CreatHash(HashTable &s);//初始化建立一个五位的哈希表
int addHash(HashTable &s,Imfo* Data);//向哈希表中插入元素
int addOneHash(HashTable &s);//向电话簿中添加一个联系人
int delOneHash(HashTable &s);//删除电话簿中一个联系人
int SearchHash(HashTable s);//根据输入的关键字，查询联系人信息，并打印
int ModifyHash(HashTable &s);//改变联系人信息(需要先删除旧的信息在添加新的信息)
int showHash(HashTable s);//打印哈希表
int OperateMenu();//建立菜单，提示操作代码
int main()
{
HashTable s;
int i=1;
while(i){
switch(OperateMenu()){
case 1:
InitHash(s);
break;
case 2:
CreatHash(s);
break;
case 3:
showHash(s);
break;
case 4:
SearchHash(s);
break;
case 5:
addOneHash(s);
break;
case 6:
delOneHash(s);
break;
case 7:
ModifyHash(s);
break;
case 0:
i=0;
}
}
}
int InitHash(HashTable &s){
//初始化一个空的哈希表
for(int i=0;i<50;i++){
s[i].nextData=NULL;//给nextData赋初值，方便设置条件
}
flag=1;//标志哈希表的建立
printf("创建成功！\n");
return OK;
}
int HashFunction(Imfo Data){
//哈希函数，构造储存地址
int s=0;
s=(Data.num[3]-'0')+(Data.num[4]-'0')+(Data.num[5]-'0')+(Data.num[6]-'0')+(Data.num[7]-'0');
return s%47;
}
int CreatHash(HashTable &s){
//初始化建立一个五位的哈希表
if(flag==0){
printf("未建立电话簿，请先建立！\n");
return ERROR;
}
printf("请输入~\n");
for(int i=0;i<5;i){
Imfo*p=(Imfo*)malloc(sizeof(Imfo));
scanf("%s",p->name);
scanf("%s",p->num);
if(addHash(s,p)==-1);
else i++;
}
printf("保存成功！\n");
return 1;
}
int addHash(HashTable &s,Imfo* Data){
//向哈希表中插入元素
int k=HashFunction(*Data);
Imfo*p=s[k].nextData;
while(p){
if(!strcmp(p->num,Data->num)){
printf("%s %s 该号码已存在！不能录入系统！\n",Data->name,Data->num);
return -1;
}
p=p->nextData;
}
Data->nextData=s[k].nextData;
s[k].nextData=Data;//利用头接法将新节点链如哈希表
return OK;
}
int SearchHash(HashTable s){
//根据输入的关键字，查询联系人信息，并打印
if(flag==0){
printf("未建立电话簿，请先建立！\n");
return ERROR;
}
Imfo T;
printf("输入查询的电话号码：");
scanf("%s",T.num);
int k=HashFunction(T);
Imfo*p=s[k].nextData;
while(p){
if(!strcmp(p->num,T.num)){
printf("查找完毕！该联系人信息为：姓名：%s 电话号码：%s \n",p->name,p->num);
return OK;
}
p=p->nextData;
}
printf("没有找到该联系人\n");
return ERROR;
}
int addOneHash(HashTable &s){
//向电话簿中添加一个联系人
if(flag==0){
printf("未建立电话簿，请先建立！\n");
return ERROR;
}
Imfo*q=(Imfo*)malloc(sizeof(Imfo));
printf("输入联系人姓名：");
scanf("%s",q->name);
printf("输入联系人电话：");
scanf("%s",q->num);
int k=HashFunction(*q);
Imfo*p=s[k].nextData;
while(p){
if(!strcmp(p->num,q->num)){
printf("%s %s 该号码已存在！不能录入系统！\n",q->name,q->num);
return -1;
}
p=p->nextData;
}
q->nextData=s[k].nextData;
s[k].nextData=q;
printf("添加成功！\n");
return OK;
}
int delOneHash(HashTable &s){
//删除电话簿中一个联系人
if(flag==0){
printf("未建立电话簿，请先建立！\n");
return ERROR;
}
Imfo*q=(Imfo*)malloc(sizeof(Imfo));
Imfo*t=(Imfo*)malloc(sizeof(Imfo));;
printf("输入联系人姓名：");
scanf("%s",q->name);
printf("输入联系人电话：");
scanf("%s",q->num);
int k=HashFunction(*q);
Imfo*p=s[k].nextData;
t=s[k].nextData;
if(!t)printf("电话簿没有该联系人！\n");
if(!s[k].nextData->nextData&&!strcmp(s[k].nextData->num,q->num)){
s[k].nextData=NULL;
printf("删除成功！\n");
return OK;
}//该地址只有一个节点，s[k].nextData->nextData=null，且该节点就是需要删除的节点
else if(!s[k].nextData->nextData&&strcmp(s[k].nextData->num,q->num)){
printf("电话簿没有该联系人！\n");
return ERROR;
}//该地址只有一个节点，s[k].nextData->nextData=null，但该节点不是需要删除的节点
if(s[k].nextData->nextData&&!strcmp(s[k].nextData->num,q->num)){
s[k].nextData=s[k].nextData->nextData;
printf("删除成功！\n");
return OK;
}//该地址不只有一个节点，s[k].nextData->nextData！=null，且该节点就是需要删除的节点
while(p){
if(!strcmp(p->num,q->num)){
break;
}
t=p;
p=p->nextData;
}//p为移动节点，用来做判断条件，t为p的前驱节点，用来删除p所用
if(!p){
printf("电话簿没有该联系人！\n");
return ERROR;
}
else{
if(!p->nextData)t->nextData=NULL;//如果需要查找的节点是该链最后一个，直接使t->nextData=NULL
else t->nextData=p->nextData;
free(p);//释放p
printf("删除成功！\n");
}
return OK;
}
int ModifyHash(HashTable &s){
//改变联系人信息(需要先删除旧的信息在添加新的信息)
if(flag==0){
printf("未建立电话簿，请先建立！\n");
return ERROR;
}
if(!delOneHash(s))return ERROR;
addOneHash(s);
return OK;
}
int showHash(HashTable s){
//打印哈希表
if(flag==0){
printf("未建立电话簿，请先建立！\n");
return ERROR;
}
int c=1;
printf("电话号码全部信息为：\n");
for(int i=0;i<50;i++){
if(s[i].nextData!=NULL){
printf("%d:姓名：%s 电话号码：%s\n",c++,s[i].nextData->name,s[i].nextData->num);
Imfo*p=s[i].nextData->nextData;
while(p){
printf("%d:姓名：%s 电话号码：%s\n",c++,p->name,p->num);
p=p->nextData;
}
}
}
return OK;
}
int OperateMenu(){
//建立菜单，提示操作代码
int num;
printf(" *---------------------------------------*\n");
printf(" 1：创建一个空的电话薄！\n");
printf(" 2：初始化输入5个信息！\n");
printf(" 3：打印电话薄的全部信息！\n");
printf(" 4：查询联系人信息！\n");
printf(" 5：添加一个联系人信息！\n");
printf(" 6：删除一个联系人信息！\n");
printf(" 7：修改联系人的电话信息！\n");
printf(" 0:选择其他指令退出系统！\n");
printf(" *---------------------------------------*\n");
scanf("%d",&num);
for(int i=0;;i++){
if(num<0||num>7){
printf("指令错误！请输入正确的指令~\n");return -1;}
else if(num==0){
return num;break;}
else if(num==1){
return num;break;}
else if(num==2){
return num;break;}
else if(num==3){
return num;break;}
else if(num==4){
return num;break;}
else if(num==5){
return num;break;}
else if(num==6){
return num;break;}
else if(num==7){
return num;break;}
}
}
智能推荐
Python爬虫网页解析神器Xpath快速入门教学！！！_python xpath 等于class的标签-程序员宅基地
文章浏览阅读2.2k次，点赞2次，收藏18次。文章目录1、Xpath介绍2、Xpath路径表达式3、结合实例讲解1、Xpath介绍 XPath 是一门在 XML 文档中查找信息的语言。XPath 可用来在 XML 文档中对元素和属性进行遍历。2、Xpath路径表达式表达式描述nodename选取此节点的所有子节点。/从根节点选取。//从匹配选择的当前节点选择文档中的节点，而不考虑它们的位置。.选取当前节点…选取当前节点的父节点_python xpath 等于class的标签
快手上热门的小技巧，抖音快手直播5个上热门技巧_快手作品上了小热门后应该怎么做-程序员宅基地
文章浏览阅读2.1k次。2020下半年，随着直播带货行业发展势头越来越猛，各大电商平台纷纷涉足直播电商，普通人也跃跃欲试想要加入直播带货，那么普通人该如何选择直播平台呢，这要根据每个人的自身条件，不管做抖音还是快手，初始最重要的就是涨粉，今天小编分享的是新人做抖音快手直播如何快速涨粉的技巧。说到抖音快手涨粉，最暴力的莫过于上热门，一个视频上热门，涨粉可能就有好几万，比如之前有个直播睡觉，一夜爆红的主播，一天时间涨粉几百万，一晚收入70多万，不知道羡煞多少旁人。了解抖音快手上热门的机制是怎样的！抖音快手热门视频推荐机制，或者_快手作品上了小热门后应该怎么做
html输入哪种table好,如何将html转换为Handsontable哪个表还有html输入字段<table> </table>...-程序员宅基地
文章浏览阅读94次。我想显示一个动态表，其中包含来自自定义搜索的记录。现在我想将表格行设为内联可编辑行。我还需要对表进行分页，因为我需要在同一个表上显示30到40个表列(滚动列)。我使用Handsontable来实现这一点，如下图所示，但是，图像不会像我在表格单元格中输入一样。Scroll - HandsontableActionIDNameAddress1testtest2test2test23test3test3..._html版 handsontable
如何用python生成带图片名称和标签的.txt文件（代码）_将标注信息按指定格式制作图片对应的txt标签数据。-程序员宅基地
文章浏览阅读1.6w次，点赞23次，收藏147次。我们之前实现了如何用python批量修改图片的名称，不清楚的同学可以看一下这一篇：python批量修改一个文件夹下含多个文件夹中的所有图片名称（代码）接下来我们来看一下如何生成带图片名称和标签的txt文件因为我们在用caffe进行分类训练时，不管是生成imdb还是直接拿图片训练，都是需要标签文件的话不多说，直接上代码：#!/usr/bin/python# -*- co..._将标注信息按指定格式制作图片对应的txt标签数据。
如何设置EXCEL表格单元格的内容可以换行显示_电脑里面的文本控制自动换行在哪里-程序员宅基地
文章浏览阅读1.6k次。点击单元格，选择“设置单元格格式”，然后选择“对齐”，在“文本控制”中勾选“自动换行”就可以了，当然你也可以选择水平对齐和垂直对齐的“居中”哦。..._电脑里面的文本控制自动换行在哪里
虚拟机安装Mac Ox 10.6 之后的驱动安装vmware tool 安装_苹果笔记本装虚拟机后设备驱动也是虚拟吗-程序员宅基地
文章浏览阅读2.3k次。在虚拟机上成功安装Mac OX 10.6 系统之后，还有一些的需要的驱动。在安装vmare tool , 在启动界面，将setting->CD/DVD(IDE)选项中drawin.iso, 将上面的对话框connect 选中，之后会在系统的桌面上看到VMware Tool( Drawin) , 双击进去，直接双击Install VMware tools, 之后就可以的，重新启动,如下图所示_苹果笔记本装虚拟机后设备驱动也是虚拟吗
随便推点
园区网络IP地址规划_园区私有地址-程序员宅基地
文章浏览阅读6.9k次，点赞11次，收藏89次。笔者当年先后考取了CCNA、CCNP、CCIE；经过这些年工作，接触从几万、几十万到上亿的项目都有；我简单总结了接触的大部分的项目，将园区网核心技术进行了归纳，如下：IP地址规划1.IP地址基础在IP网络中，通信节点需要有一个唯一的IP地址，IP地址用于IP报文的寻址以及标识一个节点；IP地址中最重要的是子网划分 VLSM，可参照NA。2.特殊IP地址a.受限广播（用于IP地址请求阶段）所有位全为1，255.255.255.255b.直接广播（子网广播） 主机位全为1，如192.168.1_园区私有地址
java Swing弹出式提示框_javaswing setlocation-程序员宅基地
文章浏览阅读5.7k次。package com.sanguo.test;import java.awt.BorderLayout;import java.awt.Color;import java.awt.Dimension;import java.awt.FlowLayout;import java.awt.Toolkit;import java.awt.event.MouseEvent;import _javaswing setlocation
Docker容器与虚拟化技术：OpenEuler 部署 ES 与 Kibana-程序员宅基地
文章浏览阅读441次，点赞21次，收藏15次。使用镜像elasticsearch:7.8.0，以后台模式启动一个容器,将容器的 9200 端口映射到主机的 19200 端口,主机的配置文件/data/elasticsearch/config/elasticsearch.yml映射到容器的配置文件/usr/share/elasticsearch/config/elasticsearch.yml，主机的相关目录映射到容器的相关目录。进入容器中找到/usr/share/kibana/config/kibana.yml。(2) 点击插件 (Edge浏览器)
Multi-Instrument中 VT XLR-to-USB使用探头的选择_vtxlr-程序员宅基地
文章浏览阅读320次。就是探头看到说明书上说1,2,3分别对应VTXLR-to-USB的hi,med,lo.我看到当我软件中探头和硬件VTXLR-to-USB开关没对应的时候,也是有输入的,这种情况下测试是对的吗1.探头看到说明书上说1,2,3分别对应VTXLR-to-USB的hi,med,lo.我看到当我软件中探头和硬件VTXLR-to-USB开关没对应的时候,也是有输入的,这种情况..._vtxlr
Django搜索功能的实现_django做搜索功能-程序员宅基地
文章浏览阅读9.1k次，点赞4次，收藏44次。在用Django搭建网站的时候，要实现一个搜索功能，实现对数据库的检索功能，这里用到了网上的几个标准库： django-haystack, whoosh, jieba。其中这里有详细的haystack中文教程1 首先是在相应的环境中安装，pip install 上面这三个。这个是默认安装anaconda的环境里，当然你也可以安装到自己的虚拟环境中。2 进行配置，首先是在Django的se..._django做搜索功能
基于Vue前端UI框架比较_antdesignvue和vue的区别-程序员宅基地
文章浏览阅读2.1k次，点赞2次，收藏7次。基于Vue前端UI框架比较Vue3相对于vue2的优缺点优点:性能提升，主要体现在打包体积（减少了40%左右），渲染速度（快了55%），更新速度（100%）及内存使用（减少了50%）几方面。 由于增加了composition api，更加支持Ts，使得代码相对于Vue2更利于维护。缺点：就目前来说用户数量和社区活跃度没有vue2高，有一定的学习成本（包括学习ts）各个UI框架的比较根据目前市场常用的框架进行初步筛选，入选了4款框架，分别为element-ui, ant-desi_antdesignvue和vue的区别