数据结构教案第八章.

H(k)=k 顺序查找的顺序表（一维数组）如图8-19所示 从图8-19可以得到顺序查找的成功平均查找长度为： ASL=(1+2+3+4+5+6+7+8)/8=4.5； 0 1 2 3 4 5 6 7 8 9 10 11 78 10 1 3 2 4 21 图 8-19顺序存储的顺序表 从图8-19可以得到顺序查找的成功平均查找长度为： ASL=(1+2+3+4+5+6+7+8)/8=4.5； 二分查找的判定树（中序序列为从小到大排列的有序序列）如图8-20所示， 4 2 11 1 3 10 21 图8-20 二分查找的判定树 78 从图8-20可以得到二分查找的成功平均查找长度为： ASL=(1+2*2+3*4+4)/8=2.625； 二叉排序树（关键字顺序已确定，该二叉排序树应唯一）如图 8-21(a)所示，平衡二叉树（关键字顺序已确定，该平衡二叉树也应该是唯一的），如图8-21(b)所示， 11 3 1 3 10 78 1 11 21 2 10 78 2 4 4 (a)二叉排序树 (b)平衡二叉树 图 8-21 二叉排序树及平衡二叉树 21 从图8-21(a)可以得到二叉排序树查找的成功平均查找长度为： ASL=(1+2*2+3*2+4+5*2)=3.125； 从图8-21(b)可以得到平衡二叉树的成功平均查找长度为： ASL=(1+2*2+3*3+4*2)/8=2.75； 线性探查法解决冲突的哈希表如图8-22所示， 0 1 2 3 4 5 6 7 8 9 10 11 78 1 3 2 4 21 10 图8-22线性探查的散列表 从图8-22可以得到线性探查法的成功平均查找长度为： ASL=（1+1+2+1+3+2+1+8）/8=2.375； 拉链法解决冲突的哈希表如图8-23所示。 0 1 2 3 4 5 6 7 8 9 10 ^ ^ ^ ^ ^ 11 ^ 78 2 ^ 3 ^ 4 ^ 1 ^ 78 1 ^ 图8-23 拉链法的哈希表 从图8-23可以得到拉链法的成功平均查找长度为： ASL=(1*6+2*2)/8=1.25。

复习思考题 案例分析： 作 业 学生表查询 上机任务 参考文献 课后记 总结一下今天所上的内容，然后结合上两一次所上的内容就（或归纳小可以所学知识连贯一下，最后要求学生课后把所上内容好好看一结） 下，再预习下一次所上的内容，并告知下一次所上的课堂内容。