C案例十七数据结构CAI哈希表演示PPT课件

1、案例十七 数据结构CAI哈希表演示本案例知识要点 数组的使用 字符串指针的使用 类的设计和使用 哈希表的概念及构造 文件的使用第1页/共26页一、案例需求 案例描述 哈希表是一种很重要的数据结构，广泛应用于软件编程中。本案例实现哈希表的建立、查找等功能，以直观的方式显示了哈希表这种重要的数据存储及检索方法。 案例效果图 本案例效果如图所示。第2页/共26页哈希表案例运行效果图第3页/共26页 功能说明 从一个文件中读入一系列的字符串建立Hash表。该文件格式为：每行一个字符串，表示一个名字，中间没有空格。 在建立好的Hash表的基础上完成查找、插入、求元素数等任务。第4页/共26页二、案例分析

2、 哈希函数的构造方法 对数字的关键字有很多哈希函数的构造方法，如：直接定址法、数字分析法、平方取中法、折叠法、除留余数法以及随机数法等。如果是非数字关键字，则需先对其进行数字化处理。 本案例中的哈希函数采用了除留余数法，除留余数法的哈希函数构造算法如下： H(key) = key MOD p pm（表长） 其中：key为关键字，m为表长，p为除数。 关键问题是：如何选取p值？ p应为不大于m的质数或20以内的质因子。 例如，当key = 12, 39, 18, 24, 33, 21时，由于所有key值都是含质因子3的关键字，若取p=9, 则会使得所有关键字均映射到地址0, 3, 6上，从而增加

3、了“冲突”的可能性。第5页/共26页 处理冲突的方法 处理冲突的实际含义是：为产生冲突的地址寻找下一个哈希地址。解决冲突的方法有很多，例如开放定址法（其中又分为线性探测再散列、平方探测再散列、随机探测再散列）和链地址法。本案例解决哈希冲突采用了线性探测再散列法，其算法如下。 为产生冲突的地址H(key)求得一个地址序列： H0, H1, H2, , Hs 1sm1 其中：H0 = H(key)。 Hi = ( H(key) + di ) MOD p i=1, 2, , s 在本案例中，增量di按照线性探测再散列的要求取了最简单的整数1。 需要注意的是，随机探测时的m和di没有公因子。第6页/共

4、26页 哈希表的查找 给定K值，根据哈希函数求得哈希地址，若表中此位置上没有记录，则查找不成功；否则比较关键字，若与给定的值相等，则查找成功；否则根据处理冲突方法寻找下一地址，直至某个位置为空或所填记录的关键字等于给定值为止。 查找过程和造表过程一致。假设采用开放定址处理冲突，则查找过程为： 对于给定值K，计算哈希地址 i = H(K)，如果ri = NULL，则查找不成功；如果ri.key = K，则查找成功；否则求下一地址Hi，直至rHi = NULL（查找不成功）或rHi.key = K（查找成功）为止。第7页/共26页 理解了哈希表的概念和相关知识后，理解本案例就很容易了。本案例采用了

5、类机制，将哈希表设计为一个类，封装了有关数据及操作，结构清晰，逻辑通畅。在哈希类成员函数的实现时，增加了一些错误处理机制，包括提示输入错误、警告溢出等。由于类的可扩充性，利用添加成员函数也可以轻易增加程序的功能。案例需要使用一个文本文件，该文件用于长期保存哈希表中的数据。文件内容如图所示。第8页/共26页文件内容 第9页/共26页三、案例设计HashTable类图 第10页/共26页第11页/共26页第12页/共26页主程序调用流程图 insert子功能流程图 第13页/共26页四、案例实现第14页/共26页第15页/共26页第16页/共26页第17页/共26页第18页/共26页第19页/共26页第20页/共26页第21页/共26页第22页/共26页第23页/共26页第24页/共26页五、案例总结与提高 案例总结 本案例采用的数据结构是哈希表，哈希函数的设计是使用哈希表的核心问题，很多