学号 2017-2018-2 《程序设计与数据结构》课堂测试补充报告
课程：《程序设计与数据结构》
班级： 1723
姓名： 刘辰
学号：20172306
实验教师：王志强
必修/选修： 必修
1.测试内容
- 三种算法查找练习
- 给定关键字序列11,78,10,1,3, 2,4,21，试分别用线性查找、折半查找、散列查找（用线性探查法和链地址法）来实现查找。试画出它们的对应存储形式（顺序查找的顺序表，二分查找的判定树，两种散列查找的散列表），并求出每一种查找的成功平均查找长度。其中，散列函数H(K) = K % 11。
- 测试过程及结果
- 线性查找：这个比较简单，就是从表头开始，一次又一次的将数组中的元素与目标元素进行比较，然后找到元素。
解题：不用排序，一个一个找
- 折半查找：首先一定要将数组中的数字进行排序，然后从中间开始查找，然后看大于还是小于中间值，然后在相应的一侧再次进行中间查找。
解题：中间开始找
- 散列查找
- 线性探查法：在存储地址和放的东西之间建立一个确定的对应关系；不通过比较，一次存取就能得到所查元素。
解题：利用 K%11
首先将联系表示出来，然后对应上
然后在1时，发现和78有冲突，所以就取下一个，下一个为空，所以放进去
之后就继续放
最后的21是有冲突的，往后就到0处的索引，然后继续寻找空闲处，ASL为 (1 + 1 + 2 + 1 + 3 + 2 + 8 + 1 )/8 = 2.375
- 链地址法：用链表进行查找，在冲突时，形成一个链表，链在后面。
ASL为ASL= (1 x 6 + 2 x 2)/8 = 1.25
其他（感悟、思考等）
在测试过程中，在散列查找用线性探查法中，我做错了，将21放错了位置，经过老师讲解之后才知道错误之处，是自己之前就没理解那个地方。