当前位置:   article > 正文

7-1顺序查找(数据结构)_r7-1 数据结构 顺序查找pta

r7-1 数据结构 顺序查找pta

一.基础知识
1.查找——线性结构——顺序查找
2.查找方式:从头至尾(或从尾至头)依次查找
3.查找长度:比较次数

eg.找到43需要比较9次
在这里插入图片描述
4.平均查找长度ASL
①等概率(通常情况)
②不等概率(见后文)

(1)查找成功
找到26,查找长度2
找到30,查找长度3
查找每个是等概率的,即1/8
在这里插入图片描述
ASL=1×1/8+2×1/8+2×1/8+3×1/8+3×1/8+3×1/8+3×1/8+4×1/8
=(1+2×2+3×4+4×1)/8=2.625

一个成功结点的查找长度=自身所在层数

(2)查找失败
在这里插入图片描述
如插入22,需要比较3次,放到21的右子树
在全过程中,失败共有9个位置可放(紫色)
ASL失败=3×1/9+3×1/9+3×1/9+3×1/9+3×1/9+3×1/9+3×1/9+4×1/9+4×1/9=(3×7+4×2)/9=3.22

一个失败结点的查找长度=其父节点所在层数

求ASL:
在这里插入图片描述
二.实现

(一)方法一

TableLen表示表的长度(并非数组)
图中TableLen为11(蓝色部分)
标号从0开始,到10
在这里插入图片描述
可以用for循环来依次对比

for(i=0;i<ST.TableLen//小于11,从0到10
&&ST.elem[i]!=key;i++)//elem为动态分配数组,如果当前未找到,i++
  • 1
  • 2

查找成功返回当前i,失败返回-1

return i==ST.TableLen?-1:i;//i=11说明查找失败,返回-1
  • 1

(二)方法二(哨兵法)

将待查找的数据放在0号位
表中数据从1开始,即数组下标从1开始
TableLen=11(11个数据)
注:法一和法二的TableLen均为11

逆向对比,即0号位的16和11号位的37对比
在这里插入图片描述
同样可以用for循环表示

for(i=ST.TableLen;//i=11,数组下标从1到11
ST.elem[i]!=key;i--)
  • 1
  • 2

查找成功返回i,查找失败返回0

return i;
  • 1

优点:哨兵法进行循环时无需判断下标是否越界
在这里插入图片描述
总结:
ASL成功=(1+2+3+…+n)/n=(1+n)/2
ASL失败=n+1

(1)对于成功,右侧第一个为1×1/n,右侧第二个为2×1/n…1号位为n×1/n
(2)对于失败,待查找元素不在n个元素中,即比较n次没有匹配上,在0号位的第n+1次匹配成功

三.对于有序表(递增/递减排序)
在这里插入图片描述
升序表查找21,找到29仍失败,后面的无需再次比较,对于查找失败情况的效率提高
在这里插入图片描述
ASL成功=(1+2+3+4+5+6)/6=3.5
ASL失败=(1+2+3+4+5+6+6)/7=3.857
即:
ASL成功=(1+2+3+…+n)/n=(n+1)/2
ASL失败=(1+2+3+…+n+n)/(n+1)=n/2+n/(n+1)

四.对于概率不相等

同样计算方式
给出概率
7: 15%
13: 5%
19: 10%
29: 40%
37: 28%
43: 2%
在这里插入图片描述
将概率大的放到前面,对于查找成功情况的效率提高,对于查找失败情况可能不如有序表
在这里插入图片描述
五.总结

1.ASL 的数量级反应了查找算法时间复杂度,上述时间复杂度均为O(n)
2.哨兵法无需判断下标是否越界;
递增或递减排序可以提高失败查找效率;
概率不同时,按概率递减排序可以提高成功查找效率
3.评价⼀个查找算法的效率时,通常考虑查找成功/查找失败两种情况的ASL,ASL通常越小越好

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/运维做开发/article/detail/807540
推荐阅读
相关标签
  

闽ICP备14008679号