电话号码查找系统.doc

目录问题提出1目的1问题描述1基本要求1问题分析1功能2输出形式2数据结构设计2算法设计2主要函数3伪随机探测再散列处理冲突3再哈希法处理冲突3以姓名为关键字建立哈希表3以电话号码为关键字建立哈希表3测试分析3总结4参考文献4附录4问题提出目的巩固和加深对线性表、栈、队列、字符串、树、图、查找、排序等理论知识的理解;掌握现实复杂问题的分析建模和解决方法(包括问题描述、系统分析、设计建模、代码实现、结果分析);提高利用计算机分析解决综合性实际问题的基本能力。问题描述设计哈希表实现电话号码查找系统。基本要求每个记录有下列数据项:电话号码、用户名、地址。从键盘输入各记录,分别以电话号码和用户名为关键字设计哈希表;采用不同的哈希函数,比较冲突率。采用适当的方法解决冲突;在哈希函数确定的前提下,尝试不同类型处理冲突的方法,考察平均查找长度的变化。查找并显示给定号码的记录。查找并显示给定用户名的记录。每个单词仅由大写的英文字符组成长度不超过63个字符。对算法要分析,要说明正确性或近似性能。问题分析利用哈希表记录:电话号码、用户名、地址。通过判断来进行相关的增加记录、查询记录、姓名号码排序、清空、退出等操作。功能:读取数据:读取电话本存储的电话信息;读取系统随机新建电话本存储的电话信息查找信息 根据电话号码查询用户信息。根据姓名查询用户信息。存储信息 查询无记录的结果存入记录文档。输出形式数据文件“”存放原始电话号码数据。数据文件“”存放有系统随机生成的电话号码文件。数据文件“”存放未查找到的电话信息。查找到相关信息室显示姓名、地址、电话号码。。系统以菜单界面工作,运行界面友好。数据结构设计算法设计主要函数:IntCollision_Random(intkey,inti)//伪随机数探量观测再散列法处理冲突VoidInint_HashTable_by_name(stringname,string,phone,stringaddress)//以姓名为关键字建立哈希表intCollision_Rehash(intkey,stringstr)//再哈希法处理冲突voidInit_HashTable_by_phone(stringname,stringphone,stringaddress)//以电话号码为关键字建立哈希表voidOutfile(stringname,intkey)//在没有找到时输出未找到的记录,(intkey)//输出哈希表中的记录VoidRafile()//随机生成数据,(char*fname,intn)//根据姓名查找哈希表在的记录伪随机探测再散列处理冲突若对应位置已经存在其他数据,则新的关键字=(原关键字+伪关键字)%哈希表的长若新位置上也存在其他数据,则用伪随序列的下一个数求新的关键字,直到找到合适的位置。再哈希法处理冲突用“折叠法”将电话号码的ASCII码值定义为关键字,分别为前四位、中间四位、后四位。再用“除留余数法”求的新关键字=原关键字%哈希表长。以姓名为关键字建立哈希表用“除留余数法”将姓名的ASCII码值定义为关键字。若对应位置上也存在其他数据,则调用伪随机处理冲突。然后将数据存入哈希表。以电话号码为关键字建立哈希表用“除留余数法”将电话号码的ASCII码值定义为关键字。若对应位置上也存在其他数据,则调用再哈希处理冲突。然后将数据存入哈希表。测试分析程序的关键是掌握文件的相关操作、哈希函数的创建和运用、伪随机法处理冲突、再哈希法处理冲突等。创建“”用子函数来实现,但是原数据是从“”文件中读取的。调试出现了很多bug解决他们还是花了大量时间的。姓名查找:哈希表根据电话号码查询选择数据来源选择查找方式选择功能显示结果