哈希表的设计与实现(24页).doc

-哈希表的设计与实现-第 24 页令胆 嗲 院计算机科 嗲 b 练 水 系课程设计报告20072008 学年第2学期课程数据结构与算法课 程 设 计 名 称哈希表的设计与实现学生姓名学号0604011026专业班级06 计科（1)指导教师2008年9月课程设计题目：（哈希表的设计与实现的问题 设计哈希表实现电话号码查询系统。设计程序完成以下 要求 ：(1） 设每个记录有下列数据项：电话号码、用户名、地址：（2） 从键盘输入各记录 ， 分别以电话号码和用户名为关键字建立晗希表 ；(3） 采用再哈希法解决冲突；（4） 查找并 显示给定电话号码的记录 ：（5） 查找并显示给定用户的记录。一、 问题分析和任务定义1、问题分析要完成如下要求 ：设计晗希表实现电话号码查询系统。 实现本程序需要解决以下几个问题：(1)如何设计一个结点使该结点包括电话号码、用户名、地址。(2)如何分别以 电话号码和用户名为关键字建立哈希表 。(3)如何利用再晗希法解决冲突。(4)如何实现用晗希法查找并显示给定电话号码的记录 。(5)如何查找并显示给定用户的记录 。2、任务定义由问题分析知，本设计主要要求分别以电话号码和用户名为关键字建立晗希表 ，并实现 查找功能 。所以本设计的核心问题是如何解决散列的问题，亦即设计一个良好的哈希表。由 于结点的个数无法确认，并且如果采用线性探测法散列算法 ，删除结点会引起 “信息丢失” 的问题。所以采用链地址法散列算法 。采用链地址法 ，当出现同义词冲突时，使用链表结构 把同义词链接在一起，即同义词的存储地址不是散列表中其他的空地址 。首先，解决的是定义链表结点，在链地址法中，每个结点对应一个链表结点，它由三个 域组成，而由于该程序需要分别用电话号码和用户名为关键字建立晗希表 ，所以该链表结点 它是由四个域组成.name8 、num ll 和 address20 都是 char 浮点型，输入输出都只能 是浮点型的。采用链地址法，其中的所有同义词构成一个单链表，再由一个表头结点指向这个单链表 的第一个结点。这些表头结点组成一个一维数组，即哈希表。数组元素的下标对应由散列函 数求出的散列地址。拉链法处理冲突 的散列表结构：3、主程序分析本题目最主要的要求是设计散列 函数，本程序需要设计两个散列函数才能解决问题，程序需 要分别为以 电话号码和用户名为关键字建立哈希表 。所以要分别以用户名、号码为关键字建 立两个散列画数，具体思路为 ：对于以号码为关键字的散列函数，是将十一个数字全部相加，然后对 20 求余。得到的 数作为地址 。对于以用户名为关键字的散列函 数，是将所有字母的ASCLL 码值相加 ，然后对 20 求余。要添加用户信息，即要有实现添加结点的功能的函数，所以要设计一个必须包括一个输 入结点信息、添加结点的函数：要实现查找函数 ，则必须包括一个查找结点的函数； 另外还有一个必不可少的就是运 行之后要有一个主菜单 ，即要设计一个主函数(main（） ）。4、测试数据的选择最后，程序完成后要对程序进行 编译调试，执行后要选择数据进行测试，这里选择的测试数 据为：l、姓名：张三 电话号码： 地址：合肥2、姓名：Jack 电话号码： 地址：Shanghai三、概要设计和数据结构选择本设计涉及到的数据结构为 ：哈希表。要求输入电话号码、用户名、地址三个信息，并 要求分别以电话号码和用户名为关键字进行查找，所以本问题要用到两个晗希函数，进行哈 希查找。在链地址法中，每个结点对应一个链表结点，它由三个域组成，而由于该程序需要分别 用电话号码和用户名为关键字建立哈希表 ，所以该链表结点它是由 四个域组成 ，链地址法结 点结构如图： 阳e8 I 川口J l a抽出s 20 I next其中 name8和 numll 是分别为以电话号码和用户名为关键字域 ，存放关键字 （key ) ; address20(data）为结点的数据域，用来存储用户的地址。Next 指针是用来指 向下一个结点 的地址。主要算法的流程 图如下：以号码为关键字的 Hash（）函数流程图开始取整型 num2赋给 keyi从 3 开始取Key=key+(int) numii+Key=key%20结束以姓名为关键字的 HashO函数流程图开始取整型nameO赋给 key2i从 0 开始取Key2+=nameii+Key2:key%20结束添加结点信息流程图：开始申请新的结点 newphone,newname 即新的号码和名字Newphone=input()Newname 指向 newphone调用 hash（）函数调用 hash（）函数拉链法处理冲突利用用户名为关键字插入结束按姓名查找流程图：开始调用 hash（）函数中新结点 q 指向phonekey->nextq=q->next输 出无 记 录q 不为 空输 出相 应记录结束按号码查找流程图：开始调用 bash2（）函数中新结点 q 指向pbonekey->nextq=q->next输 出无 记 录q 不为空输 出相 应 记录结束初始化散列链表 (1） 并为其动态分配内存空 间初始化散列链表 （ 2） 并为其动态分配内存空 间主程序流程图Menu （） 主 菜单进行姓名散1 list2()添加记录 apend()进行号码散列 list()号码散列结果清空 creat();creat2()列表己清空退出系统 return O结束四、详细设计和编码首先定义结点结构体类型，在链地址法 中，每个结点对应一个链表结点，它由三个域组 成，而由于该程序需要分别用电话号码和用户名为关键字建立哈希表 ，所以该链表结点它是 由四个域组成 ，链地址法结点结构如图：I n棚e s I 川其中 name8和 num ll是分别为以电话号码和用户名为关键 字域 （key） ，存放关键字： address20为结点的数据域（data），用来存储用户的地址信息。next 指针是用来指向下一个结 点的地址。unsigned int key 和 unsigned int key2 分别被定义为电话号码和用户名关键字。程序的主要模 块如下：串程序部分源代码中串串串串串丰1、建立节点struct node H建节点char name8,address20矿节点中要包含用户名，用户地址，电话号码以及指向下一个结点的指针char num(ll; node * next;typedef node* pnode; /typedef 可以为一个己有的数据类型声明多个别名，这里为该类型声明了两 个指针typedef node* mingzi; node *phone ;node 肺nam; node *a;2、对哈希函数的定义本程序要设计两个 hash O 函数，分别对应电话号码和用户名。本设计中对散列函数 选择的是除留余数法，即对关键字进行模运算，将运算结果所得的余数作为关键字（或 结点 的存储地址，即 H (key) =key mod p，本设计中p 取 20，然后将计算出来的数作为该结 点的地 址赋给 key。具体方法如下：以电话号码为关键字建立哈希函数 hash(char num11） 。以用户 名为关键字建立哈希 函数bash2(char name8） 。利用强制类型转换，将用户名的每一个字母 的ASCLL 码值相加并且除以20 后的余数。将计算出来的数作为该结 点的地址赋给 key2 。程序部分源代码牢牢牢牢牢牢牢牢牢牢串串串串串串串 串本本中a),oid hash(char numll) II以电话号码为关键字建立哈希函数key=(int)num 2;while(numi!=NULL)key+=(int)numi;1+;key=key %20;b)void bash2(char name8) II以用户名为关键字建立晗希函数int i = 1; key2=(int)nameO;while(namei!=NULL)key2+=(int)namei;key2=key2%20;然后，建立结点 ，并添加结点 ，利用链地址法解决冲突 。建立结点应包括动态申请内 存空间。向结点中输入信息。同时将结点中的 next 指针等于 null 。添加结点，首先需要利用 晗希函数计算出地址即关键字，其次将该结点插入以关键字为地址的链表后 ，当然由于分别 以用户名和电话号码为关键字 ，所以分两种情况 ，如果以用户名为关键字则调用 void hash2(char name8）函数，并且将结点插入对应的散列链表中，如果以电话号码为关键字则 调用 void hash(char numll）函数，并且将结点插入对应的散列链表中 。并且，需要两个建立散列链表的函数 ，分别动态申请一定的空间 ，用于动态申请散列 链表。void creat（）用来动态创建以电话号码为关键字的链表数组，void create2（）用来动态创 建以用户名为关键字的链表数组。串串程序部分源代码串串丰void create() II新建号码节点phonei=new node; phonei->next=NULL;int i;phone=new pnode20; fl动态创建对象数组for(i=O;i<20;i+)void create2() II新建姓名节点nami=new node;int i;nami->next=NULL ;nam=new mingzi20; for(i=O;i<20;i叫同样，需要两个显示链表的函数，利用 for 循环和 while 语句将表中信息按要求输出来 。3. 哈希查找想要实现查找功能，同样需要两个查找函数，无论以用户名还是以电话号码为关键字 ， 首先，都需要利用 hash 函数来计算出地址。再通过比对 ，如果是以电话号码为关键字 ，比 较其电话号码是否相同，如果相同则输出该结点的所有信息，如果以用户名为关键字，则比 较用户名是否相同，如果相同则输出该结点的所有信息。如果找不到与之对应相同的，则输 出 “无此记录，。程序部分源代码串串a）、void find(char numll） 施以电话号码为关键字的哈希表中查 找用户信息hash(num);node *q=phonekey->next; while(q!= NULL)if(strcmp(num,q->num)=O) break;q=q->next;if(q)printf（”%s_%s_%sn",q->name,q->addre邸 q->num); else printf （ 无J1t记录飞n");b）、void fmd2(char nameS) II 在以用户名为关键字的哈希表中查找用户信息hash2(name);node *q=namkey2->next; while(q!= NULL)if(strcmp(name,q->name)=O) break;q=q->next;if(q)printf（”%s_%s_%s恼”，q->name,q->address,q->nUJD); else printf （ 无此记录飞n");3、主函数本程序需要创建一个主菜单和一个主函 数，主菜单便于用户的使用，主函数中，包括所有 功能对应的数值，使之和主菜单相对应 。主函数界面设计如下0.添加记录1.查找记录2.姓名散列3.号码散列4.清空记录5.退出系统4、程序数据测试当程序设计出来后的测试数据为 ：1、姓名：张三 电话号码： 地址：合肥2、姓名：Jack 电话号码： 地址：Shanghai首先键入 0，添加结点信息，然后按 1 进行查找，分别进行号码和姓名查找，最后可在主菜单 中，选择号码散列和姓名散列，由此查看程序运行结果 。至此，就解决了哈希表的设计与实现算法可能出现的各种问 题，那么根据以上思路以及对问 题的分析和对出现情况的解决则可以写出源程序 。五、上机调试1、语法错误及修改 ：程序是分块写的，调试时可以使用分步调试的方式进行，以便能查 找看程序是在哪出错了。本算法使用了链表结构和链地址法解决冲突的问题，在以姓名为关 键字的哈希表中要注意涉及 ASCLL 码的类型转换，要注意输出不能是%d ”，否则不能输出 结果。编写程序时要多注意程序中各种指针的使用，还有各类变量的定义，函数的使用。这 些问题均可以根据编译器的警告提示，对应的将其解决。2、逻辑问题修改和调整：链表结构方法虽然方便了运行，但是增加了对算法过程的认 识难度。在本程序中每一个函数中都需要涉及到指针的操作。所以需要仔细分析函数中的指 针指向。在插入结点，查找结点时尤为突出。对于主菜单和主函数的对应，一定要一致，这 样才能保证运行时不会出错。3、时间，空间性能分析：散列法本质上是一种通过关键字直接计算存储地址的方法 。 在理想情况下，散列函数可以把结点均匀地分布到散列表 中，不发生冲突，则查找过程无需 比较，其时间复杂度 0 (n) =1。但在实际使用过程中，为了将范围广泛的关键宇映射到一 组连续的存储空间 ，往往会发生同义词冲突，这时在查找过程中就需要进行关键字比较 。因 此散列法的查找性能取决于 3 个因素：散列函数、冲突处理方法和填充因子。采用链地址法 ，可以从根本上杜绝 “二次聚集” 的发生，从而提高散列表的均匀度，提高查找性能，不过也 会 “浪费” 一部分散列表的空间 。当散列函数和冲突处理办法固定时，散列法的查找性能就 取决于散列表的填充因子。填充因子 a 表中已有的结点数表的长度。填充困子 a 标志表的 添满程度。很显然，a 越小则发生冲突的机会就越小 ；反之，a 越大冲突的机会就越大，查 找的性能也就越低。哈希表链地址法查找成功的平均查找长度 SNc= l+a/2 。链地址法查找不 成功的平均查找长度 Un 满足：Un =a 由以上可以看出，散列表的平均查找长度是填充困 子的函数，和散列表的长度没有关系，因此在实际应用 中，我们应该选择一个适当的填充因 子，以便把平均查找长度控制在一个尽 量小的范围内。4、经验和体会 ：本设计用到的数据结构是哈希表，并且要实现查找功能，在刚拿到本 问题时，我首先想到的查找方法是顺序查找，这就没有用到哈希表 ，而本设计要求必需使用 晗希表这一存储结构，另外本设计也可以用 C中的类来解决，可以用类来设计晗希表 。六、用户使用说明本程序运行过程时带有提示性语句，由于 address20 、name8和 numll可以看出地址 可输入的最大字符数是 20，姓名可输入的最大字符数是 8，电话号码都为 11 位。在输入的 时候，用户特别注意 电话号码的位数。实现添加结点 ，将信息从键盘输入 ，然后根据屏幕的提示进行操作，由此，本设计的要 求就可以被用户实现了。七、测试结果程序主菜单：添加记录：E 圃C:Userstige叭Desktop飞课程酣咱希褒酣吃酒 hxb飞Debughxb剧理分别按电话号码和姓名查找：国C:Users飞回ge叭Des战op课程齿，鸭精装源代码飞hxb飞' Debughxb.exeA坦J到分别输出按姓名和号码散列的结果：国C飞U”“飞liger飞Desktop课程酶，叭晗帮褒漂代码飞hxb飞Debug飞hxb剧e国C:Users句e叭Desktop飞漂穰副科始每蒙漂代码，hxbDebughxb刷e清空记录：广me:飞Userstige 飞Des阳op幌程设 t'飞始帮亵漂代码hxbDebug飞hxb刷e八、参考书 目i草浩强，C 语言程序设计，北京：清华大学出版社 ，2005 年 7 月第 3 版。 王昆仑，李红，数据结构与算法，中国铁道出版社 ，2007 年 6 月第 1版。 李春碟，数据结构题集，北京：清华大学出版社 ，1992 年 2 月第一版。九、附录程序源代码牢牢牢牢牢牢牢牢牢牢牢牢牢牢牢牢牢 本本本本#include<s tdio. h>#include<s tring. h>#def ine M儿L 0unsigned int key ；定义两个关键字unsigned int key2;int *P ,struct node 建节点 每个结点包括用户姓名、地址、电话号码、以及指向下一个结点的指针char name 町，address 20 , char numll ;node * next ;typedef node* pnode; / typedef 可以为一个已有的数据类型声明多个别名，这里为该类型声明了两个指针typedef node* mingz i; node *phone;node *n创o; node 乱，void hash(char num ll) 哈希函数 ，以电话号码为关键字建立哈希函数晗希函数的主旨是将电话号码的十一位数字全部加起来int i = 3;key= (int) num 2 ;while (numi ！阳LL)key+= (int) num i ; 1+;key=key%20;void hash2 (char name 8) 哈希函数 以用户名为关键字建立哈希函数除以 20 后的余数int i = l ;key2= (int) n棚eO ; while (name i！阳LL)key2+= (int) name i; 1+ ;key2=key2%20 ;利用强制类型转换，将用户名的每一个字母的ASCLL 码值相加并且node* input () 输入节点信息 ，建立结点，并将结点的 next 指针指空node *temp ;temp = new node; /new 的功能是动态分配内存，语法形式 ：new 类型，名 T （初借列表temp->next=NU LL ;printf （请输入姓名：n勺 ， scanf （%sH, temp->name) , printf （输入地址：nH) ; scanf （%s，temp->address) ; printf （输入电话：n") ; scanf （飞s，temp->num) ,return temp ；对于指针类型，返回的是地址int apend O II添加节点node *newphone ; node *newname ; newphone=inpu t () ; newname=newphone;newphone->next 肌儿L ;newname->next=NULL ;hash (newphone->num) ;利用哈希函数计算出对应关键字的存储地址hash2 (newname->name) ;newphone->next = phone key) ->next ; II利用电话号码为关键字插入phone key) ->next=newphone; 是采用链地址法，拉链法处理冲突的散列表结构newname->next = namkey2) ->next ; 利用用户名为关键字插入nam key2 next=newn 划1e; return 0:void create () 新建节点mt i .phone-1ew pnode 20 ；动态创建对象数纽 for(i=O; i<20 ; i÷）phone i=new node; phone i->next=NULL;void create20 新建节点int i ;nam=new mingzi20 ；for (i=O; i<20; i+)na叫i=new node; nam (i->next=NULL ;void list （） 显示列表int 1,node *p;for (i=O; i<20; i+)p=phone i->next; while (p)printf （如 %s_%sn，p->name, p->address, p->num) ; p=p-)next ;void list2 0 显示列表mt i .node *p;for (i=O; i<20; i+)p=nami->next ; while (p)printf （如 %s_%sn，p->name, p->address, p->num) ; p=p-)nex t ;void f ind (char num ll) 在以电话号码为关键字的哈希袋中查找用户信息hash (num) ;node *q=phone key ->nex t ; while (q != Nl儿L)if (strcmp (num, q-)num) =O) break;q=q-)nex t ;if (q)printf （飞s_%s_%sn，q->name, q->address, q-)num) ; else pr intf （无此记录n勺 ，void f ind2 (char name 8) II 在以用户名为关键字的哈希表中查找用户信息hash2 (mune) ;node *q习1am key2->next , while (q != Nl儿L)if (strcmp (name, q-)name)=O) break ;q=q-)nex t ;if (q)printf （飞s_%s_%snn, q-)n棚e, q-)address, q-)num) ; else pr intf （无此记录n勺 ，void menu () 菜单printf （0. 添加记录n勺 ， printf (nl. 查找记录n勺 ， printf C2. 姓名散列nH) ; printf （3. 号码散JUn") ; printf （4. 清空记录n") ;pr intf （5. 退出系统n） ，int main()char num ll ; char name 8 ;create () , create2 0int sel; while (1)menu O ,scanf （飞d，sel) ; if (sel=l)printf （6 号码查询，7 姓名查询n） ；int b ,scanf （%d，b) ;if (b=6)printf （请输入电话号码 ：nH) ; scanf （如，num) ;printf （输出查找的信息：nH) ; f ind (num) ;elsepr intf （请输入姓名 ：n勺 ，scan: （如，name) ;printf （输出查找的信息：nH) ; f ind2 (name) ;if (sel=2)printf （姓名散列结果 ：n") ; list2 0 ;if (sel=O)printf （请输入要添加的内容：怡） ；apend () ; if (sel=3)pr intf （号码散列结果 ：nn ) ;list () ,if (sel=4)printf （列表己消空：n勺 ，巳reate O ;create2 () ; if (sel=6) return O;return O ;