文档介绍：静态搜索结构
动态搜索结构
散列
可扩充散列
第十章搜索
查找搜索
搜索结构同一数据类型(纪录)的元素
构成的数据集合。
搜索在数据集合中寻找满足条件的对
象(数据元素)。
关键字数据元素中某个字段(数据项)
的值。
主关键字唯一地表示一个纪录。
次关键字标识若干纪录
搜索成功找到满足条件的数据对象
报告该对象在结构中的位置
给出整个纪录的信息
搜索失败搜索不成功
静态搜索搜索结构在搜索前后不发生变化
动态搜索搜索的同时执行插入或删除
结构自行调整
提高效率先排序,分类,编目,索引
优化结构
一、静态搜索结构
基于数组的数据表类
顺序表——线性表、数组、链表。
(1) 顺序搜索从头至尾逐个比较
最快O(1) 最慢O(n)
搜索成功的等概率平均时间复杂性 O((n+1)/2)
(1+2+3+······+n) /n=(n+1)/2
搜索失败O(n+1)
搜索的等概率平均时间复杂性 O(3(n+1)/4)
搜索成功失败各半
((1+2+······+n)+n(n+1)) /2n =3(n+1)/4
(2)有序表的搜索
折半搜索
对已排序的搜索结构先确定中点,比较待查关键字与中点关键字的大小,反复直到成功。
求n个数据折半查找的等概率成功搜索的平均时间复杂性
1 2 3 4 5 6 7 8 9 10
1
2
2
3
3
3
3
4
4
4
1+2*2+4*3+3*4=29 O(29/10)
S=1+2*2+4*3+8*4+······+2k-1*k
= 1+2*2+3*4+4*8+······+k*2k-1
k
s =∑j·2j-1 其中 n=2k-1
j=1
1
2
2
3
3
3
3
4
4
4
满二叉树n个数据的总查找次数:
4
4
4
4
4
满二叉树n个数据的总查找次数: k s =∑j·2j-1 其中 n=2k-1 j=1
S=1+2·2+3·4+4*8+5*16+·····+k·2k-1
= 1+2+4+8+16+···+2k-1+
2+2·4+3·8+4·16+····+(k-1)·2k-1
= 1+2+4+8+16+···+2k-1+
2·(1+2·2+3·4+4*8+5*16+·····+(k-1)·2k-2)
= 1+2+4+···+2k-1+2·(1+2+4+···+2k-2)+
22·(1+2+4+···+2k-3)+·····+2k-2·(1+2)+2k-1
=2k-1+2·(2k-1-1)+22·(2k-2-1)+·····+2k-2·(22-1)+ 2k-1(2-1)
=k·2k-(1+2+4+···+2k-1)=k·2k-(2k-1)=(k-1)·2k+1
满二叉树n个数据的总查找次数: k s =∑j·2j-1 其中 n=2k-1 j=1
令s=f(k), k=1,2,3,4,······
f(1)=1 f(2)=5 f(3)=17 f(4)=49
f(5)=129 ·······
f(k)-1= 0, 22, 24, 3·24,27,······
= 0·21, 1·22, 2·23, 3·24,4·25·····
猜想 f(k)-1=(k-1)·2k
k f(k)= s =∑j·2j-1 其中 n=2k-1 j=1
f(k)-1=(k-1)2k
证明
1) f(1)-1=0
2) f(k+1)-1=f(k)+(k+1)·2k –1
= (k-1)2k+ (k+1)·2k
=2·k·2k=k·2k+1
=(k+1-1)·2k+1
S=(k-1)2k+1
满二叉树n个数据的总查找次数: k s =∑j·2j-1 其中 n=2k-1 j=1
S= (k-1)·2k+1
由 n=2k-1 得 k=log2(n+1)
S=(n+1)(log2(n+1)-1)+1
= (n+1)log2(n+1)-n
满二叉树n个数据的搜索成功平均概率时间复杂性
((n+1)/n) log2(n+1)-1
当n>50时近似于
log2(n+1)-1