文档介绍：静态搜索结构
动态搜索结构
散列
可扩充散列
第十章 搜索
静态搜索结构动态搜索结构散列可扩充散列
查找 搜索
搜索结构 同一数据类型（纪录）的元素
构成的数据集合。
搜索 在数据集合中寻找满足条件的对
象（数据元素）。
关键字 数据元素中某个字段（数据项）
的值。
主关键字 唯一地表示一个纪录 。
次关键字 标识若干纪录
静态搜索结构动态搜索结构散列可扩充散列
搜索成功 找到满足条件的数据对象
报告该对象在结构中的位置
给出整个纪录的信息
搜索失败 搜索不成功
静态搜索 搜索结构在搜索前后不发生变化
动态搜索 搜索的同时执行插入或删除
结构自行调整
提高效率 先排序，分类，编目，索引
优化结构
静态搜索结构动态搜索结构散列可扩充散列
一、静态搜索结构
基于数组的数据表类
顺序表——线性表、数组、链表。
(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