20172303 2018-2019-1 《程序设计与数据结构》第6周课堂实践报告

• 课程：《程序设计与数据结构》
• 班级： 1723
• 姓名： 范雯琪
• 学号：20172303
• 实验教师：王志强
• 助教：张师瑜/张之睿
• 实验日期：2018年10月19日
• 必修/选修： 必修

测试内容

测试原理

• ASL的算法和二分查找见上次的

哈希查找法

• 哈希查找是通过计算数据元素的存储地址进行查找的一种方法。O(1)的查找，即所谓的秒杀。哈希查找的本质是先将数据映射成它的哈希值。哈希查找的核心是构造一个哈希函数，它将原来直观、整洁的数据映射为看上去似乎是随机的一些整数。
• 哈希查找的操作步骤：
  • (1)用给定的哈希函数构造哈希表；
  • (2)根据选择的冲突处理方法解决地址冲突；
  • (3)在哈希表的基础上执行哈希查找。

解题过程

顺序查找

• 顺序查找实际上就是把要查找的所有元素放入数组中，按照线性的方式依次比较即可。
  

二分查找

• 本次使用二分查找的难点在于它是偶数个的，根据书上的说法，当存在两个“中间”值时，所采取的中点可以是两个中间值中的任何一个。
  

哈希查找（散列查找）

• 线性探查法
• 依据所给的散列函数H(k)=k%11可以计算出每个数字在数组中的位置。
  • 11%11 = 0 —— 11放到索引为0的位置
  • 78%11 = 1 —— 78放到索引为1的位置
  • 10%11 = 10 —— 10放到索引为10的位置
  • 1%11 = 1 —— 产生冲突，所以使用开放定值法中的线性探测再散列
    • （1+1）%11 = 2 —— 1放到索引为2的位置上
  • 以次类推直至最后......
    
• 链地址法
• 该方法将发生冲突的元素放到一个单链表中，数组中只存储地址。
  

错误分析

• 总共有两处错误，第一处错误在二分查找那里，错误原因是计算错误。第二处错误在哈希查找的第一个线性探查法那里，我错误的以为只要每个元素的地址不同，找到它们就只需要一次查找，但是后来感觉不对，在改完拍好照准备上传的时候发现已经结束了o(╥﹏╥)o

参考资料