HASH GAME - Online Skill Game GET 300

　　3、系统需求分析 在信息化时代的今天，计算机技术已经是发展到一个很可观的地步了，特别是面向窗口的操作系统的出现，使得程序设计更加的容易了。在过去计算机内存容量小，CPU计算速度慢，关于程序设计中的数据结构也因此提出来很多的关于解决这方面的问题。哈希表就是其中之一，哈希表是一个由关键字与值组成的特殊的一种数据结构。它的出现主要是为了解决在结构中查找记录时需要进行一系列和关键字的比较,这一类查找方法是建立在“比较”的基础上的，在顺序等的查找中，查找的效率是依赖于查找过程中所比较的次数。 理想的情况是希望不经过任何的比较一次存取便能得到所查记录，那就必须在记录的存储位置和它的关键字之间建立一个确定的

　　4、对应关系，使得每个关键字和结构中一个唯一的存储位置相对应。因而在查找时只要根据这个对应关系找到给定的值的像。若结构中存在关键字和该值相等的记录，则所要查找的数就必定就是这个所查找到的记录。 哈希函数是建立哈希表的一个重要的成员，它的构造方法分为以下几种： 直接定址法、数字分析法、平方取中法、折叠法、除留余数法、随机数法。 本程序中主要用的是除余取留法,除留取余法主要是取关键字被某个不大于哈希表表长m的数p出后所得余数为哈希地址即:H(key)=key MOD p, p

　　5、 在哈希表的建立中，很容易出现同义词，这些同义词的出现也导致了建立哈希表时冲突的出现，如果不解决这些冲突那么建立好的哈希表与预料的哈希表不同。关于处理冲突的方法主要有：开放定址法、再哈希法、链地址法。本程序中主要用的就是链地址法莱解决冲突的。 1.1用户需求分析 设计一个程序能够使用哈希表实现电话号码查询系统。该系统能够从键盘输入各记录，分别以电话号码和用户名为关键字建立哈希表，能够从输入记录中查找并显示给定用户的记录，最后并且能够进行清除记录和退出功能。 1.2功能需求分析 （1）设计一个结点使该结点包括电话号码、用户名、地址。 （2）利用用户名和电线、关键字建立哈希表，哈希函数用除留余数法构照。 （3）利用链表法处理冲突问题。 （4）查找并显示给定用户名，地址，电线）显示哈希表中的给定用户的记录。 （6）当完成操作后，可以退出系统。 1.3数据需求分析 由问题分析知，本设计主要要求分别以电话号码和用户名为关键字建立哈希表，并实现查找功能。所以本设计的核心问题是如何解决散列的问题，亦即设计一个良好的哈希表。由于结点的个数无法确认，并且如果采用线性探测法散列算法，删除结点会引起“信息丢失”的问题。所以采用链地址法散列算法。采用链地址法，当出现同义词冲突时，使用链表结构把同义词链接在一起，即同义词的存储地址不

　　7、是散列表中其他的空地址。 首先，解决的是定义链表结点，在链地址法中，每个结点对应一个链表结点，它由三个域组成，而由于该程序需要分别用电话号码和用户名为关键字建立哈希表，所以该链表结点它是由四个域组成8] 、num[11]和address[20]都是char浮点型，输入输出都只能是浮点型的。 采用链地址法，其中的所有同义词构成一个单链表，再由一个表头结点指向这个单链表的第一个结点。这些表头结点组成一个一维数组，即哈希表。数组元素的下标对应由散列函数求出的散列地址。 1.4 小结 通过以上需求分析，知道了设计一个哈希表的目的和能够“实现什么功能”，为接下来的操作明确方向，罗列了

　　8、需要运用到的知识，自己应该在接下来的程序设计和实现应该怎么做。 2系统设计 2.1设计内容及要求 本设计主要要求分别以电话号码和用户名为关键字建立哈希表，并实现查找功能。本程序的要求是设计散列函数，亦即设计一个良好的哈希表。本程序需要设计两个散列函数才能解决问题，程序需要分别为以电话号码和用户名为关键字建立哈希表。所以要分别以用户名、号码为关键字建立两个散列函数，要添加用户信息，即要有实现添加结点的功能的函数，所以要设计一个必须包括一个输入结点信息、添加结点的函数； 要实现查找函数，则必须包括一个查找结点的函数； 另外还有一个必不可少的就是运行之后要有一个主菜单，即要设计一个

　　9、主函数（main()）。 2.2总体设计思路 本设计涉及到的数据结构为：哈希表。要求输入电话号码、用户名、地址三个信息，并要求分别以电话号码和用户名为关键字进行查找，所以本问题要用到两个哈希函数，进行哈希查找。 在链地址法中，每个结点对应一个链表结点，它由三个域组成，而由于该程序需要分别用电话号码和用户名为关键字建立哈希表，所以该链表结点它是由四个域组成，链地址法结点结构如图： name[8] num[11] address[20] next 其中name[8]和num[11]是分别为以电话号码和用户名为关键字域，存放关键字（key）；address[20](data

　　10、)为结点的数据域，用来存储用户的地址。Next指针是用来指向下一个结点的地址。 2.3程序详细设计流程图 2.31以姓名为关键字的Hash()函数流程图 结束 Key2=key%20 name[i]不为空 开始 i从0开始取 取整型name[0]赋给key2 Key2+=name[i] i++ 1-1 姓名为关键字的Hash()函数流程图 2.32添加结点信息流程图: 利用用户名为关键字插入 拉链法处理冲突 调用hash()函数 调用hash()函数 Newname指向

　　20、\t\n); printf(\t\t\t\t 4.清空记录\t\t\t\t\n); printf(\t\t\t\t 5.退出系统\t\t\t\t\n); } 3系统测试 3.1上机调试 1首先键入0,添加结点信息,然后按1进行查找,分别进行号码和姓名查找,最后可在主菜单中，选择号码散列和姓名散列,由此查看程序运行结果。 2语法错误及修改：程序是分块写的,调试时可以使用分步调试的方式进行,以便能查找看程序是在哪出错了。本算法使用了链表结构和链地址法解决冲突的问题，在以姓名为关键字的哈希表中要注意涉及ASCLL码的类型转换，要注意输出不能是“%d”，

　　21、否则不能输出结果。编写程序时要多注意程序中各种指针的使用，还有各类变量的定义，函数的使用。这些问题均可以根据编译器的警告提示，对应的将其解决。 3逻辑问题修改和调整：链表结构方法虽然方便了运行，但是增加了对算法过程的认识难度。在本程序中每一个函数中都需要涉及到指针的操作。所以需要仔细分析函数中的指针指向。在插入结点，查找结点时尤为突出。对于主菜单和主函数的对应，一定要一致，这样才能保证运行时不会出错。 4时间，空间性能分析：散列法本质上是一种通过关键字直接计算存储地址的方法。在理想情况下，散列函数可以把结点均匀地分布到散列表中，不发生冲突，则查找过程无需比较，其时间复杂度O（n）=1。但

　　22、在实际使用过程中，为了将范围广泛的关键字映射到一组连续的存储空间，往往会发生同义词冲突，这时在查找过程中就需要进行关键字比较。因此散列法的查找性能取决于3个因素：散列函数、冲突处理方法和填充因子。采用链地址法，可以从根本上杜绝“二次聚集”的发生，从而提高散列表的均匀度，提高查找性能，不过也会“浪费”一部分散列表的空间。当散列函数和冲突处理办法固定时，散列法的查找性能就取决于散列表的填充因子。填充因子a=表中已有的结点数/表的长度。填充因子a标志表的添满程度。很显然，a越小则发生冲突的机会就越小；反之，a越大冲突的机会就越大，查找的性能也就越低。哈希表链地址法查找成功的平均查找长度SNc=1+a

　　23、/2。链地址法查找不成功的平均查找长度Un满足：Unc=a+e-a.由以上可以看出，散列表的平均查找长度是填充因子的函数，和散列表的长度没有关系，因此在实际应用中，我们应该选择一个适当的填充因子，以便把平均查找长度控制在一个尽量小的范围内。 3.2调试结果与分析 程序主菜单 添加记录: 分别按电话号码和姓名查找: 分别输出按姓名和号码散列的结果: 清空记录: 4总结 经过为期两周的课程设计，此次课程设计时间虽然比较短暂，但是我通过这次实践学到了很多知识，也了解了自己的

　　24、很多的不足之处。我是一名信息工程学院的学生，数据结构对于我来说就显得尤为重要，这也是我必须认真学懂的一门课程。在课程设计之前，我们已经学习C语言这门课程已经一个学期，对其有了一定的了解，但是更多的还是停留在学习了解的范围，对里面的好多东西还是很陌生，并不是很熟练，有着许多欠缺，更多的在运用起来的时候还是感到很不好动手。C语言课堂上许多关于C语言的语法规则，听起来十分枯燥无味，也不容易记住，死记硬背是不可取的。然而要使用C语言这个工具解决实际问题，又必须掌握它。通过多次上机练习，对于语法知识有了感性的认识，加深对它的理解，在理解的基础上就会自然而然地掌握C语言的语法规定。对于一些内容自己认为在课

　　25、堂上听懂了，但上机实践中会发现原来理解的偏差，更加巩固了学过的知识，而且在设计的时候学要系统的知识，也是一个较大的挑战，某一方面知识的欠缺都将影响到整个程序的设计。我从原来的对这门课程的不懂，到目前的能够独立完成一个小型程序。 这次课程设计，重温了和学习了许多有关c语言的知识，还掌握了一些现实中编程的一些小技巧，实际的编程能力也得到了历练，本次课程设计对我帮助很多。 5附录 ************************程序源代码************************** #include