哈希表实现电话号码查询系统

实验目的：1．训练与培养解决实际问题的能力2．学会面对一个问题时应该如何分析问题，设计解决方法，实际编码及结果测试。

3．熟悉哈希表的使用4．设计哈希表实现电话号码查询系统。

5．设计程序完成以下要求：（1）设每个记录有下列数据项：电话号码、用户名、地址；（2）从键盘输入各记录，以电话号码为关键字建立哈希表（至少要有12个以上的记录，哈希表的长度为8）；（3）采用链地址法解决冲突；（4）显示建立好的哈希表，对于学有余力的同学可以实现哈希表的查找。

实验仪器与设备：计算机实验内容：（1）采用除留余数法进行哈希表的散列，即以电话号码作为主关键字，将电话号码的11位相加，按照模7取余；（2）解决冲突用链地址法。

、（3）实现哈希表的显示与号码的查询实验方法与步骤：1.根据问题进行分析，明确要解决的问题是什么，怎样解决2.根据分析设计问题求解算法3.用特定语言对设计进行编码4.对程序进行测试实验原理：1．对于哈希电话本问题的分析：哈希表问题实际上和图问题一样，先创建一个数组。

在号码存入时，如果数组中哈希关键字位置没有写入号码，则在该处写入，并把该处设置为已写入。

如果该处已写入号码，则在该处建立新的结点，并写入号码。

2．号码显示用for和while两个循环，具体实现过程可看附录代码。

3．号码查询按号码显示的函数书写，只是实现函数不同。

实验心得：通过这次的实验，我更加熟练了分析问题的方法。

深刻题解算法的重要性。

本次的算法实现中，对算法的时间空间复杂度进行了优化处理。

这是一个以前没做过的地方。

在哈希表的显示与查询中，出了一个错误，在纸上模拟了很久也没看出问题。

后来睡觉时才突然想到写少了一个函数，这提示我，写程序要细心，不能大意。

实验具体代码如下：// 哈希表问题.cpp : 定义控制台应用程序的入口点。

#include"stdafx.h"#include<iostream>usingnamespace std;class PNQS{private:char num[11];char name[8],address[18];int numwrited;PNQS *p;public :void setname(char cname[8],int n){int i;for (i=0;i<n;i++)name[i]=cname[i];name[i] = 0;}void setnum(char cnum[11],int n){int j;numwrited=1;for (j=0;j<n;j++)num[j]=cnum[j];num[n] = 0;}void setaddress(char cadd[18]){int i;for ( i=0;i<18;i++)address[i]=cadd[i];address[i] = 0;}void displaynpa(){cout<<"姓名：";cout<<name<<endl;cout<<"号码：";cout<<num<<endl;cout<<"地址：";cout<<address<<endl;}void displaynum(){cout<<num<<" ";}bool Isnumwrited(){if (numwrited==0)return 0;elsereturn 1;}bool Ispemp(){if (p==NULL)return 1;elsereturn 0;}void find(char Fnum[11],int n,int& ftrue){int b=0;for (int i=0;i<n;i++)if (num[i]!=Fnum[i])b++;if (b==0 && strlen(num)==strlen(Fnum)){displaynpa();ftrue=1;}}void movenext(PNQS *&mp){mp=p;}PNQS(){for(int i=0;i<16;i++)num[i]='0';num[16]=0;p=NULL;numwrited=0;}PNQS(char num2[4],int n){numwrited=0;p=NULL;for(int i=0;i<n;i++)num[i]=num2[i];num[n]=0;cout<<"请输入姓名："<<endl;cin>>name;cout<<"请输入地址："<<endl;cin>>address;}void CreatNewP(char num3[4],int n){p=new PNQS(num3,n);}};int keyword(char nums[16],int n){int count=0;for(int i=0;i<n;i++){count=count+nums[i]-48;}nums[n]=0;return count%7;}void main(){PNQS *p=new PNQS[8];bool exit=1;do{cout<<"输入存储，输入显示表，输入查找电话，输入退出"<<endl;int slect;cin>>slect;if (slect==1){staticint counts=0;counts++;cout<<"输入你要存入的号码："<<counts<<endl;char num[16];cin>>num;if ( (p+keyword(num,strlen(num)))->Isnumwrited()==0){(p+keyword(num,strlen(num)))->setnum(num,strlen(num));cout<<"输入此主号码的姓名："<<endl;char name[8];cin>>name;(p+keyword(num,strlen(num)))->setname (name,strlen(name));cout<<"输入此主号码的地址："<<endl;char add[18];cin>>add;(p+keyword(num,strlen(num)))->setaddress (add);}else{PNQS *nextp=(p+keyword(num,strlen(num)));while(!nextp->Ispemp ()){nextp->movenext(nextp);}nextp->CreatNewP(num,strlen(num));}}PNQS *q;if(slect==2){cout<<"存入的表为："<<endl;for(int ii=0;ii<8;ii++){cout<<endl;cout<<"第"<<ii<<"个位置：";if((p+ii)->Isnumwrited()==1 &&(p+ii)->Ispemp ()==1)(p+ii)->displaynum ();if ((p+ii)->Isnumwrited()==1 &&(p+ii)->Ispemp ()==0){q=(p+ii);q->displaynum ();do{q->movenext (q);q->displaynum ();}while(!q->Ispemp());}}}int findrigt;if(slect==3){findrigt=0;cout<<"输入要查的号码："<<endl;char f[16];cin>>f;if((p+keyword(f,strlen(f)))->Isnumwrited()==1 &&(p+keyword(f,strlen(f)))->Ispemp ()==1){(p+keyword(f,strlen(f)))->find (f,strlen(f), findrigt);}if ((p+keyword(f,strlen(f)))->Isnumwrited()==1 &&(p+keyword(f,strlen(f)))->Ispemp ()==0){q=(p+keyword(f,strlen(f)));q->find (f,strlen(f), findrigt);do{q->movenext (q);q->find (f,strlen(f), findrigt);}while(!q->Ispemp());}if ( findrigt==0)cout<<"无此号码"<<endl;}if(slect==4)exit=0;}while(exit);system("pause"); }结果图附表：。

哈希表实现电话号码查询系统一目的利用《数据结构》课程的相关知识完成一个具有一定难度的综合设计题目，利用C/C++语言进行程序设计，并规范地完成课程设计报告。

通过课程设计，巩固和加深对线性表、栈、队列、字符串、树、图、查找、排序等理论知识的理解；掌握现实复杂问题的分析建模和解决方法（包括问题描述、系统分析、设计建模、代码实现、结果分析等）；提高利用计算机分析解决综合性实际问题的基本能力。

二需求分析1、程序的功能1)读取数据①读取原电话本存储的电话信息。

②读取系统随机新建电话本存储的电话信息。

2)查找信息①根据电话号码查询用户信息。

②根据姓名查询用户信息。

3)存储信息查询无记录的结果存入记录文档。

2、输出形式1)数据文件“old.txt”存放原始电话号码数据。

2)数据文件“new.txt”存放有系统随机生成的电话号码文件。

3)数据文件“out.txt”存放未查找到的电话信息。

4)查找到相关信息时显示姓名、地址、电话号码。

3、初步测试计划1)从数据文件“old.txt”中读入各项记录，或由系统随机产生各记录，并且把记录保存到“new.txt”中。

2)分别采用伪随机探测再散列法和再哈希法解决冲突。

3)根据姓名查找时显示给定姓名用户的记录。

4)根据电话号码查找时显示给定电话号码的用户记录。

5)将没有查找的结果保存到结果文件Out.txt中。

6)系统以菜单界面工作，运行界面友好，演示程序以用户和计算机的对话方式进行。

三概要设计1、子函数功能int Collision_Random(int key,int i)//伪随机数探量观测再散列法处理冲突void Init_HashTable_by_name(string name,string phone,string address) //以姓名为关键字建立哈希表int Collision_Rehash(int key,string str)//再哈希法处理冲突void Init_HashTable_by_phone(string name,string phone,string address) //以电话号码为关键字建立哈希表void Outfile(string name,int key)//在没有找到时输出未找到的记录，打开文件out.txt并将记录储存在文档中void Outhash(int key)//输出哈希表中的记录void Rafile()//随机生成数据，并将数据保存在new.txtvoid Init_HashTable(char*fname,int n)//建立哈希表int Search_by_name(string name)//根据姓名查找哈希表中的记录int Search_by_phone(string phone)//根据电话号码查找哈希表中的记录2、函数调用图四详细设计1、主函数流程图2、“伪随机探测再散列处理冲突”伪代码若对应位置上已经存在其他数据，则新的关键字=（原关键字+伪随机数）%哈希表长。

哈希表的设置与实现课程设计任务书设计题目：哈希表的设置与实现_________________________________________________________ 设计内容与要求：1.【问题描述】设计哈希表实现电话号码查询系统。

2.【基本要求】1、设每个记录有下列数据项：电话号码、用户名、地址；2、从键盘输入各记录，分别以电话号码和用户名为关键字建立哈希表；3、采用再哈希法解决冲突；4、查找并显示给定电话号码的记录；5、查找并显示给定用户名的记录。

6、在哈希函数确定的前提下，尝试各种不同类型处理冲突的方法（至少两种），考察平均查找长度的变化。

指导教师：2018年12月27日课程设计评语成绩：指导教师：年月日目录第1章需求分析 (3)1.1设计内容 (3)1.2数据需求 (3)1.3数据结构描述 (3)第2章概要设计 (4)2.1系统结构与模块功能 (4)2.2系统模块 (4)第3章详细设计与实现 (5)3.1模块流程图 (5)3.2界面效果图及代码 (7)3.3源代码 (11)第4章总结 (18)第1章需求分析1.1设计内容设计哈希表实现电话号码查询系统。

通过对姓名和电话号码构造哈希函数，接着根据姓名和号码进行查询，并计算它的平均查找长度。

并且尝试多种方法解决冲突，但至少使用两种方法来解决。

1.2数据需求1、设每个记录有下列数据项：电话号码、用户名、地址；2、从键盘输入各记录，分别以电话号码和用户名为关键字建立哈希表；3、采用再哈希法解决冲突；4、查找并显示给定电话号码的记录；5、查找并显示给定用户名的记录。

6、在哈希函数确定的前提下，尝试各种不同类型处理冲突的方法（至少两种），考察平均查找长度的变化。

1.3数据结构描述typedef struct Node{ char phone_num[12]; //电话号码char name[12]; //姓名char address[12]; //家庭住址struct Node *next, *next_; //后继指针}Node, *LinkNode;phone_num,name,address分别表示电话号码、姓名和家庭住址，next是name哈希链表的后继指针，next_是num哈希链表的后记指针。

郑州轻工业学院课程设计任务书题目电话号码查询系统专业、班级计科10-01学号41姓名王平记录。

指导设计题目：电话号码查询系统学生姓名：王平系别：计算机科学与通信工程学院专业：计算机科学与技术班级：10-01学号：41指导教师：卢冰、李晔2012年6月21日设计题目题目：电话号码查询系统每个记录有下列数据项：电话号码、用户名、地址；从键盘输入各记录，分别以电话号码和用户名为关键字设计哈希表；采用不同的哈希函数，比较冲突率；采用适当的方法解决冲突；在哈希1取关2数字分析法，解释如上。

主菜单的设计在设计效果上已经显示，不过多说明。

算法的流程inti=3;while(s.num[i]!='\0')//关键字{key+=(s.num[i]-'0');//关键字求和i++;}key=key%21;线性探测再散列处理冲突{//}}查找代码;{}key=key%21;if(!strcmp(W.t[key].num,xnum))//第一次查找，如果值相等直接赋值printf("%s%s%s\n",W.t[key].name,W.t[key].address,W.t[key].num);else{//第一次没找到，继续查找intj=1;while(strcmp(W.t[(key+j)%21].num,xnum))j++;if(j==20)printf("查找元素不存在！");elseprintf("%s%s%s\n",W.t[(key+j)%21].name,W.t[(key+j)%21].address,W.t[(key+j)%21].num);//输出查找到得元素}主界面：printf("********电话号码查询系统********\n");printf("{{printf("while(y<3){switch(y){case1:chuliu();break;//调用除留取余函数case2:shuzi();break;//调用数字分析函数default:printf("输入指令不存在！\n");}printf("********电话号码查询********\n");printf("除留取余法1\n");printf("数字分析法2\n");printf("****************************\n");printf("请输入您要的选项：\n");scanf("%d",&y);}}{}}}sunxuepingzhoukou258369收获及体会本次试验电话号码查询系统，看起来也不是想我想象中的那么难，他比较具有针对性，要求我们用哈希函数解决这倒比较实用的题目，但是这道题目用到的哈希函数仅仅是哈希中的九牛一毛，虽然写了大程序，但是对哈希表的了解还是一无所知，数据结构这门课程我认为有点难，也许是我c语言基础不够强吧，好多代码都不是很理解，以至于不能够灵活运用，其实通过每次实验我们都可以发现，数据结构的知识好像就是草原的草，密密麻麻的等待我们去拔掉，这是一项浩大的工程等待我们去建设，与此同时，也要求我们要踏实的完成每一次作业，认真的去分析重要的代码，只有端正自己的态度，才能不断地学到新的知识，提高自己。

哈希表存储的电话号码查询设每个记录有以下数据项：用户名、电话、地址；从键盘输入各记录，以电话号码为关键字建立哈希表；采用链地址法方法解决冲突；能够查找并显示给定电话号码的相关记录。

#include <iostream.h>#include <stdlib.h>#include <cstdio>#include <sstream>#define MAX_LEN 60// 学生信息类class Student{private:char _name[MAX_LEN]; // 姓名char _phone[MAX_LEN]; // 电话char _addr[MAX_LEN]; // 地址public:Student();const char* getName() ; //变量不允许被改变const char* getPhone();const char* getAddr();void setName(const char* name);void setPhone(const char* phone);void setAddr(const char* addr);};Student::Student(){memset(_name,0,MAX_LEN);memset(_phone,0,MAX_LEN);memset(_addr,0,MAX_LEN);}const char* Student::getName(){return _name;}const char* Student::getPhone(){return _phone;}const char* Student::getAddr(){return _addr;}void Student::setName(const char* name){strcpy(this->_name,name);}void Student::setPhone(const char* phone){strcpy(this->_phone,phone);}void Student::setAddr(const char* addr){strcpy(this->_addr,addr);}////////////////////////////////////////////////////////////////////////// //哈希节点struct LISTNODE{int n_value ; //int count; // 保存的个数char _phone[MAX_LEN] ; // keyStudent _info; // 学生信息LISTNODE * p_next ; // 下一个结点的地址};////////////////////////////////////////////////////////////////////////////哈希表结构定义struct HASHTABLE{int n_tablesize ;LISTNODE ** p_node ;};// 哈希表管理类class CHashTableManage{private:HASHTABLE *_hashTable;// 哈希首地址public:CHashTableManage();bool hashtable_init( int table_size);//初始化void hashtable_clear (); //清理//拿到这个字符串存在的节点LISTNODE * hashtable_find( char *phone);// 插入一个结点int hashtable_insert (LISTNODE * pNode);protected:LISTNODE * CHashTableManage::hashtable_newnode( LISTNODE* str);//哈希函数//得到字符串在哈希表中的位置int hashtable_hash (char* str, int tablesize);};////////////////////////////////////////////////////////////////////////// CHashTableManage::CHashTableManage(): _hashTable(0){}//初始化bool CHashTableManage::hashtable_init( int table_size){//表头HASHTABLE * head_ht ;head_ht = (HASHTABLE *)new( HASHTABLE );if(head_ht == NULL)return false ;//元素总数尽量素数保证mod尽可能均匀head_ht->n_tablesize = table_size;//链表队列一条链为一个散列位置head_ht->p_node = (LISTNODE **) new int[table_size];//每一个散列链初始化for(int i=0; i<head_ht ->n_tablesize; i++){head_ht->p_node[i] = NULL;}_hashTable = head_ht;return true ;}//清理void CHashTableManage::hashtable_clear () //0{if(_hashTable == NULL)return;//每一个散列链freefor(int i=0; i<_hashTable ->n_tablesize; i++){{LISTNODE *list = _hashTable->p_node[i];//当前链表不空while(list != NULL){//取得下一个LISTNODE *tempnode = list-> p_next;//free当前位置if(list )delete list ;//指向下一个list = tempnode ;}}}//链表队列freeif(_hashTable ->p_node){delete(_hashTable ->p_node);_hashTable->p_node = NULL;}//哈希头节点freeif(_hashTable ){delete(_hashTable );_hashTable = NULL ;}}//拿到这个字符串存在的节点LISTNODE * CHashTableManage::hashtable_find( char *phone) //2 {//哪一条链表LISTNODE * list = NULL;if(_hashTable == NULL)return NULL ;int pos = hashtable_hash(phone,_hashTable-> n_tablesize);//链表查找while(list != NULL){if(strcmp(phone, list->_phone) == 0) //比较break;list = list ->p_next;}return list ;}// 插入一个结点int CHashTableManage::hashtable_insert (LISTNODE * pNode) //1{int pos = hashtable_hash( pNode->_phone,_hashTable ->n_tablesize);LISTNODE *list_pos = _hashTable-> p_node[pos];//假如存在计数器+1for(;list_pos!=NULL;list_pos=list_pos->p_next){if(strcmp(list_pos->_phone,pNode->_phone) == 0&& strcmp(pNode->_info.getPhone(),list_pos->_info.getPhone()) == 0&& strcmp(pNode->_info.getAddr(),list_pos->_info.getAddr()) == 0&& strcmp(pNode->_info.getName(),list_pos->_info.getName()) == 0) {list_pos->count++;return pos;}}//不存在LISTNODE *node = hashtable_newnode(pNode);node->p_next = _hashTable-> p_node[pos];_hashTable-> p_node[pos] = node;return pos ;}//哈希函数//得到字符串在哈希表中的位置int CHashTableManage::hashtable_hash (char* str, int tablesize){unsigned int hash_val = 0;while(*str != '\0')hash_val += (hash_val << 5) + *str++;int pos = hash_val % tablesize;return pos ;}//得到新一个新节点LISTNODE * CHashTableManage::hashtable_newnode( LISTNODE* str){//插入节点初始化LISTNODE *insert_node =(LISTNODE*) malloc(sizeof (LISTNODE));insert_node->p_next = NULL;insert_node->count = 1;strcpy(insert_node ->_phone, str->_info.getPhone());memcpy(&insert_node->_info,&str->_info,sizeof(str->_info));return insert_node ;}//////////////////////////////////////////////////////////////////////////// 主函数int main (void){CHashTableManage _manage;//初始一个个链表的哈希表size最好为素数//head = hashtable_init (1001);if(!_manage.hashtable_init(1001)){cout <<"哈希初始化失败"<< endl;return 1;}cout<<"**************************************************************************** ****** "<< endl;cout <<"<<<<<<<<<< 学生信息管理（哈希表实现）>>>>>>>>>>"<< endl;cout <<"<<<<<<<<<<>>>>>>>>>>"<< endl;cout <<"<<<<<<<<<<>>>>>>>>>>"<< endl;cout <<"<<<<<<<<<<>>>>>>>>>>"<< endl;cout <<" 按任意键开始"<< endl;cout<<"**************************************************************************** ******"<< endl;getchar();while(1){system("cls");cout <<"......................."<<endl;cout <<". <1> 添加学生信息."<<endl;cout <<". <2> 查询学生信息."<< endl;cout <<". <0> 退出."<<endl;cout <<"......................."<<endl;char key = getchar();switch(key){case '1':{LISTNODE info;char buf[MAX_LEN];memset(&info,0,sizeof(info));cout <<"---- 请输入学生信息[姓名]"<< endl;cin >> buf;info._info.setName(buf);cout <<"---- 请输入学生信息[电话]"<< endl;cin >> buf;info._info.setPhone(buf);cout <<"---- 请输入学生信息[地址]"<< endl;cin >> buf;info._info.setAddr(buf);strcpy(info._phone,info._info.getPhone());_manage.hashtable_insert(&info);cout <<"---- 恭喜写入成功！！！按任意键确认"<<endl;getchar();}break;case '2':{cout <<"---- 请输入查询条件[电话]"<< endl;char buf[MAX_LEN];cin >> buf;//找到这个字符串具体位置LISTNODE * node = _manage.hashtable_find(buf);if(node == 0){cout <<"---- 没有查询到相关数据！！！按任意键确认"<< endl;}else{cout <<"---- 查询到以下数据----"<< endl;while(node != NULL){cout <<"---------------------------------------------------------------"<< endl;cout <<"---- 相同信息数："<<node->count << endl;cout <<"---- 学生姓名："<< node->_info.getName() << endl;cout <<"---- 电话号码："<< node->_info.getPhone() << endl;cout <<"---- 学生地址："<< node->_info.getAddr() << endl;node = node->p_next;}cout <<"---------------------------------------------------------------"<< endl;cout <<"---- 查询完毕！！！按任意键确认"<<endl;}getchar();getchar();}break;case '0':{_manage.hashtable_clear();return 0;}break;default:{cout <<"---- 输入错误，请确认！！按任意键重新开始..."<< endl;getchar();getchar();}break;}}return 0;}。

数据结构方式号码查询系统数据结构方式号码查询系统1、系统概述在现代社会中，方式号码被广泛使用，人们需要通过方式号码进行通信和联系。

为了方便用户快速查询和管理方式号码，我们设计了一个方式号码查询系统，可实现以下功能：- 添加方式号码信息- 查询方式号码信息- 修改方式号码信息- 删除方式号码信息2、系统架构2.1 数据结构设计系统中使用以下数据结构来存储方式号码信息：- 链表：用于存储不同用户的方式号码信息，每个节点代表一个用户的信息，包括姓名、方式号码、地质等。

- 哈希表：用于快速查询方式号码，通过方式号码可以直接找到对应的用户信息。

2.2 模块设计系统分为以下几个模块：- 添加模块：用于用户添加新的方式号码信息，并将其存储到链表和哈希表中。

- 查询模块：提供根据方式号码查询用户信息的功能。

- 修改模块：允许用户修改已有的方式号码信息。

- 删除模块：用户可以删除不再需要的方式号码信息。

3、功能实现3.1 添加方式号码信息用户可以通过输入姓名、方式号码、地质等信息将新的方式号码添加到系统中。

3.2 查询方式号码信息用户可以通过输入方式号码进行查询，系统将返回对应的用户信息。

3.3 修改方式号码信息用户可以选择要修改的方式号码，并输入新的信息进行修改。

3.4 删除方式号码信息用户可以选择要删除的方式号码进行删除操作。

4、附件本文档附带的附件为系统的源代码和使用说明书。

5、法律名词及注释5.1 方式号码：指由数字组成的方式号码，用于流动通信。

5.2 链表：是一个线性数据结构，由一系列节点组成，节点之间通过指针连接。

5.3 哈希表：是根据关键码值（Key-value）进行访问的数据结构，通过将关键码值映射到表中的一个位置来访问数据。

数据结构课程设计报告一、需求分析1问题描述：根据需要设计出合理的函数，并由此建立相应的表。

要求：1)每个电话用户信息包括（姓名，电话，住址）信息。

2)可以使用姓名与地址查找相应的用户信息。

3)使用表实现。

使用开放定址法解决冲突。

2 基本要求：1）记录每个用户的姓名、地址和电话。

2）从键盘输入，以姓名和地址为关键字分别建立表。

3）用开放地址法解决冲突。

4）分别按姓名和地址查找并显示电话号码。

二、概要设计三、详细设计定义结构表{定义表内的所有成员}[];( x[])关键字转换为数值{求字符数组x每个字符对应的值的绝对值之和，并返回最后结果}( )创建表{创建表，并初始化它}( d) 按姓名插入{以姓名为关键字，调用关键字转换函数将对应的电话号码存储到相应的存储空间。

若该位置已经被存储，则向后移一位（当移到最后一位，就移到头部继续）。

若还有冲突重复上一步。

当所有空间都查过一遍，发现没有空位，则输出“没有存储空间”。

}( d)按地址插入{以地址为关键字，调用关键字转换函数将对应的电话号码存储到相应的存储空间。

若该位置已经被存储，则向后移一位（当移到最后一位，就移到头部继续）。

若还有冲突重复上一步。

当所有空间都查过一遍，发现没有空位，则输出“没有存储空间”。

}( )表插入{输入用户姓名、地址和电话，分别调用按姓名插入和按地址插入函数进行插入。

重复上面的步骤，直到你不想继续或空间已满。

}( )按姓名查找{输入你想要查询的姓名，对它进行转换，再查找。

若该位置不空或求得的关键字所对应的数值与该位置的数值不相等，则向后移一位（当移到最后一位，就移到头部继续）。

若还有冲突重复上一步。

当所有空间都查过一遍，发现没有找到，则输出“不存在”。

若该位置空，则输出“不存在”。

若查找到，则输出电话号码。

}( )按地址查找{输入你想要查询的地址，对它进行转换，再查找。

若该位置不空或求得的关键字所对应的数值与该位置的数值不相等，则向后移一位（当移到最后一位，就移到头部继续）。

数据结构课程设计实验名称班级学号姓名指导教师时间：成绩指导教师签字年月日《数据结构》课程设计一.题目：散列表的实现与电话查询系统二.算法思想描述：1.课程设计的主要研究内容:(1) 设每个记录有下列数据项：电话号码、用户名、地址；(2) 从键盘输入各记录，分别以电话号码和用户名为关键字建立散列表；(3) 采用一定的方法解决冲突；(4) 查找并显示给定电话号码的记录；(5) 查找并显示给定用户名的记录。

2.设计概要：设定该事件的抽象数据类型三．程序结构三.数据结构和功能设计四.程序结构分析1、程序模块●哈希函数1●哈希函数2●输入函数●添加节点函数●新建节点函数1●新建节点函数2●显示列表函数1●显示列表函数2●查找用户信息函数●保存用户信息函数●菜单函数●2、程序主要结构●流程的名称解释如下——main()是主函数，负责调用其他所有的函数，hash1()号码哈希函数，hash2()名字哈希函数，node* input()函数用于输入节点，apend()函数用于添加节点，creat()函数用于新建电话号码节点，creat2()函数用于新建名字节点，list()用于显示按电话号码排列的列表，list2()用于显示按姓名排列的列表，find()按号码查询，infd()按姓名查询，save()保存用户信息，menu()是菜单函数。

五、程序运行结果1、源程序#include "iostream.h"#include "string.h"#include "fstream"#define NULL 0unsigned int key;unsigned int key2;int *p;struct node //建节点{char name[8],address[20];char num[11];node * next;};typedef node* pnode;typedef node* mingzi;node **phone;node **nam;node *a;using namespace std; //使用名称空间void hash(char num[11]) //哈希函数{int i = 3;key=(int)num[2];while(num[i]!=NULL){key+=(int)num[i];i++;}key=key%20;}void hash2(char name[8]) //哈希函数{int i = 1;key2=(int)name[0];while(name[i]!=NULL){key2+=(int)name[i];i++;}key2=key2%20;}node* input() //输入节点{node *temp;temp = new node;temp->next=NULL;cout<<"输入姓名："<<endl; cin>>temp->name;cout<<"输入地址："<<endl; cin>>temp->address;cout<<"输入电话："<<endl; cin>>temp->num;return temp;}int apend() //添加节点{node *newphone;node *newname;newphone=input();newname=newphone;newphone->next=NULL;newname->next=NULL;hash(newphone->num);hash2(newname->name); newphone->next = phone[key]->next;phone[key]->next=newphone;newname->next = nam[key2]->next;nam[key2]->next=newname;return 0;}void create() //新建节点{int i;phone=new pnode[20];for(i=0;i<20;i++){phone[i]=new node;phone[i]->next=NULL;}}void create2() //新建节点{int i;nam=new mingzi[20];for(i=0;i<20;i++){nam[i]=new node;nam[i]->next=NULL;}}void list() //显示列表{int i;node *p;for(i=0;i<20;i++){p=phone[i]->next;while(p){cout<<p->name<<'_'<<p->address<<'_'<<p->num<<endl; p=p->next;}}}void list2() //显示列表{int i;node *p;for(i=0;i<20;i++){p=nam[i]->next;while(p){cout<<p->name<<'_'<<p->address<<'_'<<p->num<<endl; p=p->next;}}}void find(char num[11]) //查找用户信息{hash(num);node *q=phone[key]->next;while(q!= NULL){if(strcmp(num,q->num)==0)break;q=q->next;}if(q)cout<<q->name<<"_" <<q->address<<"_"<<q->num<<endl; else cout<<"无此记录"<<endl;}void find2(char name[8]) //查找用户信息{hash2(name);node *q=nam[key2]->next;while(q!= NULL){if(strcmp(name,q->name)==0)break;q=q->next;}if(q)cout<<q->name<<"_" <<q->address<<"_"<<q->num<<endl; else cout<<"无此记录"<<endl;}void save() //保存用户信息{int i;node *p;for(i=0;i<20;i++){p=phone[i]->next;while(p){fstream iiout("out.txt", ios::out);iiout<<p->name<<"_"<<p->address<<"_"<<p->num<<endl; p=p->next;}}}void menu() //菜单{cout<<"1.添加记录"<<endl;cout<<"2.查找记录"<<endl;cout<<"3.姓名散列"<<endl;cout<<"4.号码散列"<<endl;cout<<"5.清空记录"<<endl;cout<<"6.保存记录"<<endl;cout<<"7.退出系统"<<endl;}int main(){char num[11];char name[8];create();create2() ;int sel;while(1){menu();cin>>sel;if(sel==2){ cout<<"9号码查询，8姓名查询"<<endl;int b;cin>>b;if(b==9){ cout<<"请输入电话号码:"<<endl;cin >>num;cout<<"输出查找的信息:"<<endl;find(num);}else{ cout<<"请输入姓名:"<<endl;cin >>name;cout<<"输出查找的信息:"<<endl;find2(name);}}if(sel==3){ cout<<"姓名散列结果:"<<endl;list2();}if(sel==1){ cout<<"请输入要添加的内容:"<<endl;apend();}if(sel==4){ cout<<"号码散列结果:"<<endl;list();}if(sel==5){ cout<<"列表已清空:"<<endl;create();create2();}if(sel==6){ cout<<"通信录已保存:"<<endl;save();}if(sel==7) return 0;}return 0;}2、本程序在VC++环境下实现的，下面将演示该软件的使用方法主菜单添加记录输入姓名，地址，电话通信记录保存查询记录按号码查询按用户名查询五．体会通过这次课程设计，我有很深的体会，具体如下：1.巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。

合肥学院计算机科学与技术系课程设计报告2009～2010学年第二学期课程数据结构与算法课程设计名称哈希表实现通讯录题目：（哈希表的设计与实现的问题）设计哈希表实现电话号码查询系统。

设计程序完成以下要求：（1）设每个记录有下列数据项：电话号码、用户名、地址；（2）从键盘输入各记录，分别以电话号码和用户名为关键字建立哈希表；（3）采用再哈希法解决冲突；（4）查找并显示给定电话号码的记录；（5）查找并显示给定用户的记录。

一、问题分析和任务定义此程序需要完成如下要求：设计哈希表实现电话号码查询系统。

实现本程序需要解决以下几个问题：（1）设计结点使该结点包括电话号码、用户名、地址。

（2）利用再哈希法解决冲突。

（3）分别以电话号码和用户名为关键字建立哈希表。

（4）实现查找并显示给定电话号码的记录。

（5）查找并显示给定用户的记录。

本问题的关键和难点在于如何解决散列的问题。

由于结点的个数无法的知，并且如果采用线性探测法散列算法，删除结点会引起“信息丢失”的问题。

所以采用链地址法散列算法。

采用拉链法，当出现同义词冲突时，使用链表结构把同义词链接在一起，即同义词的存储地址不是散列表中其他的空地址。

首先，解决的是定义链表结点，在拉链法中，每个结点对应一个链表结点，它由三个域组成，而由于该程序需要分别用电话号码和用户名为关键字建立哈希表，所以该链表结点它是由四个域组成.name[8] 、num[11]和address[20]都是char浮点型，输入输出都只能是浮点型的。

采用拉链法，其中的所有同义词构成一个单链表，再由一个表头结点指向这个单链表的第一个结点。

这些表头结点组成一个一维数组，即哈希表。

数组元素的下标对应由散列函数求出的散列地址。

其次，设计散列函数，本程序需要设计两个散列函数才能解决问题，程序需要分别为以电话号码和用户名为关键字建立哈希表。

所以要分别以用户名、号码为关键字建立两个散列函数，对于以号码为关键字的散列函数，是将十一个数字全部相加，然后对20求余。

《数据结构》课程设计课程名称数据结构课题名称电话号码查找系统专业电子信息科学与技术班级姓名(学号)姓名(学号)2017年 6 月 3 日电话号码查找系统摘要：电话号码的查找系统软件是现在很实用工具，随着时代的发展，信息化得发展，手机是人们的必备工具，基于目前的现况，有必要开发出一款具有含量的电话号码管理系统，满足人们的需求，需要包含添加、删除、查找、显示、存储、修改等操作，并具备存储文件功能。

该篇基于C++语言在VC6.0平台用散列表设计实现电话号码的查找系统，根据数据结构设计算法并实现算法，程序多次运用了函数的调用，自定义个操作的函数，包括添加操作、查找操作、查询操作、显示操作、清除操作、保存操作由主函数调用每次操作均有主函数依次调用，从基本上实现姓名电话地址的存储和应用。

关键词：电话号码查找系统； C++； VC6.0; 数据结构1、引言（绪论）1.1、C++语言简介在C的基础上，一九八三年又由贝尔实验室的Bjarne Strou-strup推出了C++。

C++进一步扩充和完善了C语言，成为一种面向对象的程序设计语言。

C++目前流行的最新版本是Borland C++4.5,Symantec C++6.1,和Microsoft VisualC++ 2.0。

C++提出了一些更为深入的概念，它所支持的这些面向对象的概念容易将问题空间直接地映射到程序空间，为程序员提供了一种与传统结构程序设计不同的思维方式和编程方法。

因而也增加了整个语言的复杂性，掌握起来有一定难度。

1.2、开发背景随着科学技术的不断发展，计算机科学日渐成熟，电话号码使用的广泛性、简洁性日易为人们所接受采用。

电话号码管理系统已是人们必不可少的系统软件工具，用于满足人们对电话的各种操作，包括添加、删除、修改、查询、保存使电话号系统更加简洁方便，基于这种市况需求，我们有必要开发一款能满足人们这种操作需求的管理系统。

1.3、开发环境本文所采用的开发环境主要是基于C++环境的信息技术极大地扩展了全人类教育的时空界限,空前地提高了人们学习的兴趣、效率和主动性,已经成为开发人类能力的创造性工具。

哈希表实现电话号码查询系统一目的利用《数据结构》课程的相关知识完成一个具有一定难度的综合设计题目，利用C/C++语言进行程序设计，并规范地完成课程设计报告。

通过课程设计，巩固和加深对线性表、栈、队列、字符串、树、图、查找、排序等理论知识的理解；掌握现实复杂问题的分析建模和解决方法（包括问题描述、系统分析、设计建模、代码实现、结果分析等）；提高利用计算机分析解决综合性实际问题的基本能力。

二需求分析1、程序的功能1)读取数据①读取原电话本存储的电话信息。

②读取系统随机新建电话本存储的电话信息。

2)查找信息①根据电话号码查询用户信息。

②根据姓名查询用户信息。

3)存储信息查询无记录的结果存入记录文档。

2、输出形式1)数据文件“old.txt”存放原始电话号码数据。

2)数据文件“new.txt”存放有系统随机生成的电话号码文件。

3)数据文件“out.txt”存放未查找到的电话信息。

4)查找到相关信息时显示姓名、地址、电话号码。

3、初步测试计划1)从数据文件“old.txt”中读入各项记录，或由系统随机产生各记录，并且把记录保存到“new.txt”中。

2)分别采用伪随机探测再散列法和再哈希法解决冲突。

3)根据姓名查找时显示给定姓名用户的记录。

4)根据电话号码查找时显示给定电话号码的用户记录。

5)将没有查找的结果保存到结果文件Out.txt中。

6)系统以菜单界面工作，运行界面友好，演示程序以用户和计算机的对话方式进行。

三概要设计1、子函数功能intCollision_Random(intkey,inti)//伪随机数探量观测再散列法处理冲突voidInit_HashTable_by_name(stringname,stringphone,stringaddress)//以姓名为关键字建立哈希表intCollision_Rehash(intkey,stringstr)//再哈希法处理冲突voidInit_HashTable_by_phone(stringname,stringphone,stringaddress)//以电话号码为关键字建立哈希表voidOutfile(stringname,intkey)//在没有找到时输出未找到的记录，打开文件out.txt并将记录储存在文档中voidOuthash(intkey)//输出哈希表中的记录voidRafile()//随机生成数据，并将数据保存在new.txtvoidInit_HashTable(char*fname,intn)//建立哈希表intSearch_by_name(stringname)//根据姓名查找哈希表中的记录intSearch_by_phone(stringphone)//根据电话号码查找哈希表中的记录2、函数调用图四详细设计1、主函数流程图2、“伪随机探测再散列处理冲突”伪代码若对应位置上已经存在其他数据，则新的关键字=（原关键字+伪随机数）%哈希表长。

报告编号：第5组综合课程设计报告手机号码查询系统指导教师：所在系：电子工程系所学专业：计算机科学与技术年级：2012级2014 年 6 月目录1、课程设计目的和要求 (1)1.1 设计目的 (1)1.2 设计要求 (1)2、课程设计的主要工作 (2)2.1 需求分析 (2)3、课程基本设计说明 (2)3.1 概要设计和数据结构选择 (2)3.2程序具体设计 (3)3.3 程序流程图 (4)4、程序详细设计 (6)4.1 创建 (6)4.2 对哈希函数的定义 (7)4.3 哈希查找 (8)4.4 主函数 (10)5、程序运行结果界面 (11)6、课程设计总结 (16)7、参考文献 (18)8、附录 (18)摘要本文主要介绍了手机号码查询系统，实现对用户手机号码、用户名以及地址的添加、查询、存储。

程序主要以手机号码和姓名为关键字建立哈希表，并实现查找功能。

其中，以手机号为关键字建立哈希表时采用线性探测法解决冲突、以姓名为关键字建立哈希表时用拉链法解决冲突，成功通过设计哈希表实现对用户的手机号码、姓名、地址显示、查询等功能。

通过课程设计,巩固和加深对结构体、哈希表等理论知识的理解，掌握现实复杂的分析建模和解决方法,掌握包括问题描述、系统分析、设计建模、代码实现、结果分析等的方法；提高利用计算机分析解决综合性实际问题的基本能力；锻炼个人的动手能力，历练自身素质；提高大家的合作能力。

关键字：哈希表线性探测法链地址法1、课程设计目的和要求1.1 设计目的本题目最主要的的是设计散列函数，本程序需要设计两个散列函数才能解决问题，程序需要分别为以号码和用户名为关键字建立哈希表。

所以要分别以用户名、号码为关键字建立两个散列函数。

1.2 设计要求（1）每个记录有下列数据项：手机号码、用户名、地址；（2）从键盘输入各记录，分别以手机号码和用户名为关键字建立哈希表（哈希函数自选）；（3）以手机号为关键字建立哈希表时采用线性探测法解决冲突、以姓名为关键字建立哈希表时用拉链法解决冲突；（4）查找并显示给定手机号码的记录；（5）查找并显示给定用户名的记录。