哈希表《数据结构》课程设计

需求分析（1）输入的形式和输入值的范围：数据的输入在屏幕中进行，所输入的数据的格式为：姓名，住址，电话号码。用户使用时显示菜单，用户输入菜单选项完成操作。（2）输出的形式：查找的结果显示在屏幕上，未被查找到的内容输出相应的提示信息。用户需要时，将哈希表显示在屏幕上。（3）程序所能达到的功能：根据用户的要求，输入联系人的姓名，电话号码。住址，分别以姓名和电话号码作为关键字生成哈希表。生成哈希表后用户可以根据相应的关键字进行数据的查找，若查找到对应的数据则将数据输出屏幕，若没有查找到对应的数据则将输出提示信息表示未找到联系人。在用户选择哈希表时，显示完整的哈希表。程序使用文字菜单的友好界面，在数据输入时对输入内容进行范围控制。（4）测试数据：在电脑屏幕中输入记录，令程序读入并分别以姓名和电话号码做为关键字生成哈希表，查找记录中原有的记录，查看输出数据，查找记录中没有的记录输出提示信息，查看整个哈希表的数据。清除所有的记录后再次输入信息查询，屏幕输出未查找到的提示信息，若录入新的信息后，可保存信息，查询，散列联系人信息。

2开发及运行平台硬件：微型计算机。软件：VC++6.0。具体操作如下：新建……工程，添加相应的源文件，再编译，链接，执行！3概要设计1.数据类型定义结构体类型存储每条记录。structnode//建节点{charname[8];//用于存放姓名charaddress[20];//用于存放地址charnum[11];//用于存放电话号码node*next;};2.主程序流程创建存放记录的结构体数组查找记录，分别可选择姓名查询和电话号码查询姓名散列号码散列清空记录保存记录选择退出系统3.各函数功能intapend()；//添加节点voidcreate()；//新建电话号码的节点voidcreate2()；//新建姓名的节点voidfind(charnum[11])；//通过电话号码查找用户信息voidfind2(charname[8])；//通过姓名查找用户信息voidhash(charnum[11])；//哈希函数，号码散列voidhash2(charname[8])；//哈希函数，姓名散列node*input()；//输入用户信息voidlist()；//通过姓名查找显示用户信息voidlist2()//通过电话号码查找显示列表

4详细设计4.1数据类型定义structnode//建节点{charname[8],address[20];charnum[11];};node*next;//定义结构体主要算法//实现添加姓名，电话号码，住址的新的内存空间模块儿intapend(){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;return0;}//新建电话号码节点函数voidcreate(){inti;phone=newpnode[20];for(i=0;i<20;i++){phone[i]=newnode;phone[i]->next=NULL;}}//新建名字节点函数voidcreate2(){inti;nam=newmingzi[20];for(i=0;i<20;i++){nam[i]=newnode;nam[i]->next=NULL;}}//通过电话号码查找用户信息函数voidfind(charnum[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;elsecout<<"无此记录"<<endl;}//通过姓名查找用户信息函数voidfind2(charname[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;}//哈希函数，用于电话号码的散列功能voidhash(charnum[11]){inti=3;key=(int)num[2];while(num[i]!=NULL){key+=(int)num[i];i++;}key=key%20;}//哈希函数，用于姓名的散列功能voidhash2(charname[8]){inti=1;key2=(int)name[0];while(name[i]!=NULL){key2+=(int)name[i];i++;}key2=key2%20;}//输入函数，用于输入用户的姓名，电话号码，住址node*input()//输入节点{node*temp;temp=newnode;temp->next=NULL;cout<<"请输入姓名："<<endl;cin>>temp->name;cout<<"请输入地址："<<endl;cin>>temp->address;cout<<"请输入电话："<<endl;cin>>temp->num;returntemp;}//显示列表函数，用于显示通过电话号码查找到的用户信息voidlist(){inti;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; }}}//显示列表函数，用于显示通过姓名查找到的用户信息voidlist2(){inti;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; }}}//菜单函数，实现客户选择菜单进行系统操作voidmenu(){cout<<"========欢迎进入设计哈希表查询电话号码系统========"<<endl;cout<<endl;cout<<"0.添加记录"<<endl;cout<<"1.查找记录"<<endl;cout<<"2.姓名散列"<<endl;cout<<"3.号码散列"<<endl;cout<<"4.清空记录"<<endl;cout<<"5.保存记录"<<endl;cout<<"6.退出系统"<<endl;cout<<endl;cout<<"请输入你的选择（0，1，2，3，4，5，6）"<<endl;}函数流程图图一哈希函数实现姓名散列图二哈希函数实现电话号码散列图三输入函数图四电话号码节点创建函数图五姓名节点创建函数图六通过电话查找显示函数图七通过姓名查找显示函数图八姓名查找函数图九电话号码查找函数图十保存用户信息函数图十一主函数

5调试分析内容包括：1.测试环境在Windows7环境下的MicrosoftVisualC++6.02.模块调试写入数据时，对数据的内容的控制需要特别注意。要注意其字符组合模式，比如生成名字是应该只有字幕，生成电话号码是应该只有数字，还要注意生成字符组合的长度限制，比如电话号码应该是11位，这可以在循环语句中进行控制。在哈希含查找时要注意取余的除数的一致，这是哈希表成立的关键点。3.复杂度分析使用哈希表存储记录，在执行查找是可以快捷的进行查找。选用在哈希法和为随机探测再散列法。程序设定的哈希标长为50，文件数据长度为30，则哈希表的填装因子α为0.6，则查找成功时的平均查找长度为Snr≈-In（1-0.6）6测试结果1.添加记录2.查找记录查找记录姓名散列电话号码散列清空记录保存记录退出系统

7结论数据结构课程设计和现代计算机技术的实际应用相结合，是我们在本阶段学完理论课程之后对自己该方面的能力的一次很好的检验，从开始的算法思路到运行调试后的美观的用户界面以及可用程序，都是一个很好的学习和锻炼的过程。使我们巩固了原有的理论知识，培养了我们灵活运用和组合集成所学过知识及技能来分析、解决实际问题的能力。但是在编写程序的过程中遇到了很多的困难，先是设计整个程序的思路，算法，以及模块儿，由于对课程以及相关知识的一定欠缺，不能很顺利的完成这项工作，再有就是写代码的过程中出现很多语法错误和逻辑错误，通过编译调试找到错误并修改。这次数据结构课程设计的时间