资源描述：
《数据结构-c语言版-数据结构题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、一、哈希表的概念及作用一般的线性表，树中，记录在结构中的相对位置是随机的，即和记录的关键字之间不存在确定的关系，因此，在结构中查找记录时需进行一系列和关键字的比较。这一类查找方法建立在“比较“的基础上，查找的效率依赖于查找过程中所进行的比较次数。理想的情况是能直接找到需要的记录，因此必须在记录的存储位置和它的关键字之间建立一个确定的对应关系f,使每个关键字和结构中一个唯一的存储位置相对应。哈希表最常见的例子是以学牛学号为关键字的成绩表，1号学牛的记录位置在第一条，10号学生的记录位置在第10条….如果我们以学牛姓名为关键字，
2、如何建立查找表，使得根据姓名可以直接找到相应记录呢？abcclefgh■1jk1mn0Pqrs12345678910111213141516171819刘丽刘宏英吴军姓名中各字拼音首字母11lhywj用所有首字母编号值相加求和244633最小值可能为3最大值可能为78可放75个学生用上述得到的数值作为对应记录在表中的位置，得到下表:成绩一成绩二.・・3•••24刘丽829525•••26陈伟••••••33吴军••••••42李秋梅••••••46刘宏英••••••72吴小艳••••••78•••上面这张表即哈希表。如果将来
3、要查李秋梅的成绩，可以用上述方法求出该记录所在位置:李秋梅：lqm12+17+13二42取表中第42条记录即可。问题：如果两个同学分别叫刘丽刘兰该如何处理这两条记录？这个问题是哈希表不可避免的，即冲突现彖：对不同的关键字可能得到同一哈希地址。二、哈希表的构造方法1、直接定址法例如：有一个从1到100岁的人口数字统计表，其中，年龄作为关键字，哈希函数取关键字自身。地址0102•••2526年龄12•••2526人数30002000•••1050••••••2、数字分析法有学牛的牛日数据如下:年月•日75.10.0375.11.
4、2376.03.0276.07.1275.04.2176.02.15•••经分析，第一位，第二位，第三位重复的可能性大，取这三位造成冲突的机会增加，所以尽量不取前三位，取后三位比较好。3、平方取中法取关键字平方后的中间几位为哈希地址。4、折叠法将关键字分割成位数相同的几部分(最后一部分的位数可以不同)，然后取这几部分的叠加和(舍去进位)作为哈希地址，这方法称为折叠法。例如：每一种西文图书都有一个国际标准图书编号，它是一个10位的十进制数字,若要以它作关键字建立一个哈希表，当馆藏书种类不到10,000时，可采用此法构造一个四位
5、数的哈希函数。如果一木书的编号为0-442-20586-4,则：58644220+)0410088H(key)=0088(a)移位叠加5、除留余数法取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。H(key)=kcyMODp(p<=m)6、随机数法选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key)二random(key)，其中random为随机函数。通常用于关键字长度不等时采用此法。二、处理冲突的方法成绩一成绩二•…3•••24刘丽829525•••26陈伟••••••33吴军••••••42
6、李秋梅••••••46刘宏英••••••72吴小艳••••••78•••如果两个同学分别叫刘丽刘兰，当加入刘兰时，地址24发生了冲突，我们可以以某种规律使用其它的存储位置，如果选择的一个其它位置仍有冲突，则再选下一个，直到找到没有冲突的位置。选择其它位置的方法有：1、开放定址法Hi=(H(key)+di)MODmi=l,2,...,k(k<=m-l)其中m为表长，di为增量序列如果di值可能为1,2,3,...m-1,称线性探测再散列。如果di取值可能为1,-1,2,-2,4,-4,9,-9,16,-16,...k*k,-k
7、*k(k<=m/2)称二次探测再散列。如果di取值可能为伪随机数列。称伪随机探测再散列。例：在长度为11的哈希表中已填有关键字分别为17,60,29的记录，现有第四个记录，其关键字为38,由哈希函数得到地址为5,若用线性探测再散列，如下：23456789601729(a)插入前2345678960172938(b)线性探测再散列23456789601729(c)二次探测再散列2345678938601729(d)伪随机探测再散列伪随机数列为9,5,3,&1...2、再哈希法当发生冲突吋，使用第二个、第三个、哈希函数计算地址，
8、直到无冲突吋。缺点:计算时间增加。3、链地址法将所有关键字为同义词的记录存储在同一线性链表中。I10II23I人
9、IUIAI
10、19
11、-H-I68
12、人I20IAII79IAlo123456789101112鵰表4、建立一个公共溢岀区假设哈希函数的值域为[o,m-1],则设向量HashTabl
