数据结构。。。怎么计算平均查找长度?

数据结构。。。怎么计算平均查找长度?
因为是初学的
所以就算看书也不一定会
然后希望某些个专业人士列出例题以及详细解答及结果
谢谢。。。。
成琴 1年前 已收到1个回答 举报

温柔地笑 幼苗

共回答了23个问题采纳率:95.7% 举报

不知道你说的是什么平均查找长度,一般考试会考哈希表的,因为其他的更简单。
对于含有n个数据元素的查找表,查找成功的平均查找长度为:ASL=∑PiCi (i=1,2,3,…,n)。其中:Pi 为查找表中第i个数据元素的概率,Ci为找到第i个数据元素时已经比较过的次数。
已知一个待散列存储的线性表为(38,25,74,63,52,48),散列函数为H(k)=k mod 7,若采用线性探测的开放地址法处理冲突,则平均查找长度为:
ASL=p1c1+p2c2+p3c3+.......
也可以表示为
ASL=1/n(c1+c2+c3+....)
其中c是每个数查询的次数
按照H(K)=k mod 7得:
38----1
25----1
74----2
63----1
52----4
48----3
所以ASL=1/6(1+1+2+1+4+3)=2

1年前

1
可能相似的问题
Copyright © 2024 YULUCN.COM - 雨露学习互助 - 18 q. 0.500 s. - webmaster@yulucn.com