静态搜索结构动态搜索结构散列可扩充散列简介

《静态搜索结构动态搜索结构散列可扩充散列简介》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、顺序搜索从头至尾逐个比较最快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个数据折半查找的等概率成功搜索的平均时间复杂性1234567891012233334441+2*2+4*3+3

3、*4=29O(29/10)S=1+2*2+4*3+8*4+······+2k-1*k=1+2*2+3*4+4*8+······+k*2k-1ks=∑j·2j-1其中n=2k-1j=11223333444满二叉树n个数据的总查找次数：44444满二叉树n个数据的总查找次数：ks=∑j·2j-1其中n=2k-1j=1S=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

4、+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个数据的总查找次数：ks=∑j·2j-1其中n=2k-1j=1令s=f(k),

5、k=1,2,3,4,······f(1)=1f(2)=5f(3)=17f(4)=49f(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)·2kkf(k)=s=∑j·2j-1其中n=2k-1j=1f(k)-1=(k-1)2k证明1)f(1)-1=02)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+1S=(k-1

6、)2k+1满二叉树n个数据的总查找次数：ks=∑j·2j-1其中n=2k-1j=1S=(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)-1n个元素的折半搜索2k-1≤n<2k+1-1搜索成功平均概率时间复杂性介于log2(2k)-1和log2(2k+1)-1之间即k-1和k之间k=[log2(n+1)]n个元素的

7、折半搜索成功平均概率时间复杂性log2(n+1)-1/2斐波那契搜索根据斐波那契序列的特点对有序表分割0.618法斐波那契序列1235813213455······f(n)······f(n+2)=f(n)+f(n+1)从20个数的数表中查找一个纪录先找比较第13个，如果小，再比较第8个，····如果大比较后几个数的第5个······每次都比较位于这个数列的黄金分割点0.618处以下序列中查找元素10的过程123456789101112131415平均查找性能优于折半查找O(log2n)最坏情况比折半查找差（3）静态

8、树表的搜索不等概率查找时折半查找不一定好，以每点查找次数（概率）为这点的权wi带权二叉树总路径长度PH=∑wihiiPH最小的二叉树叫静态最优二叉树不同于霍夫曼树：每个结点都有权值，都要查找。ECAGBDHFI545112343ABCDEFGHI112534435PH=3·1+2·2+2·4+1·3+5·3+4·3+3·3+1·4+5·4=78