《静态搜索结构动态搜索结构散列可扩充散列》由会员分享，可在线阅读，更多相关《静态搜索结构动态搜索结构散列可扩充散列（93页珍藏版）》请在金锄头文库上搜索。
1、n n静态搜索结构静态搜索结构n n动态搜索结构动态搜索结构n n散列散列n n可扩充散列可扩充散列查找 搜索搜索结构 同一数据类型（纪录）的元素构成的数据集合。 搜索 在数据集合中寻找满足条件的 对象（数据元素）。 关键字 数据元素中某个字段（数据项 ）的值。 主关键字 唯一地表示一个纪录 。 次关键字 标识若干纪录 搜索成功 找到满足条件的数据对象报告该对象在结构中的位置给出整个纪录的信息 搜索失败 搜索不成功静态搜索 搜索结构在搜索前后不发生变 化 动态搜索 搜索的同时执行插入或删除结构自行调整提高效率 先排序，分类，编目，索引优化结构一、静态搜索结构基于数组的数据表类顺序表线性表、数组
2、、链表。(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 10122 3333 4441+2*2+4*3+3*4=29 O(29/10)S=1+2*2+4*3
3、+8*4+2k-1*k= 1+2*2+3*4+4*8+k*2k-1k s =j2j-1 其中 n=2k-1j=1122 3333 444满二叉树n个数据的总查找次数：44444满二叉树n个数据的总查找次数：k s =j2j-1 其中 n=2k-1j=1S=1+22+34+4*8+5*16+k2k-1= 1+2+4+8+16+2k-1+2+24+38+416+(k-1)2k-1= 1+2+4+8+16+2k-1+2(1+22+34+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(
4、2k-1-1)+22(2k-2-1)+2k-2(22-1)+ 2k-1(2-1)=k2k-(1+2+4+2k-1)=k2k-(2k-1)=(k-1)2k+1满二叉树n个数据的总查找次数：k s =j2j-1 其中 n=2k-1j=1令s=f(k), k=1,2,3,4,f(1)=1 f(2)=5 f(3)=17 f(4)=49f(5)=129 f(k)-1= 0, 22, 24, 324，27，= 021, 122, 223, 324，425猜想 f(k)-1=(k-1)2kk f(k)= s =j2j-1 其中 n=2k-1j=1f(k)-1=(k-1)2k 证明1) f(1)-1=02)
5、f(k+1)-1=f(k)+(k+1)2k 1= (k-1)2k+ (k+1)2k =2k2k=k2k+1=(k+1-1)2k+1S=(k-1)2k+1满二叉树n个数据的总查找次数：k s =j2j-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当n50时 近似于log2(n+1)-1n个元素的折半搜索2k-1n=11; /右移11位，去掉末尾11位return key%1024
6、;/去掉前面11位 处理冲突的方法冲突collision: 不同的关键字得到同一个地址1.开放定址法线性探查法23 35 48 17 60 29 38 4023 35 486017 293840开放定址法查找成功平均查找次数 (1+1+1+1+1+4+3)/8=12/8=3/223 35 486017 2938 40哈希表的装填因子表中填入的纪录数=哈希表的长度开放定址法的查找成功的平均查找次数(1+1/(1-)/2查找不成功的平均查找次数(1+1/(1-)2)/2开放定址法的缺点容易引起“二次聚集”发生冲突的点引起再一次冲突的可能性增加 使冲突点聚集可以用再哈希法改进 即定义一个哈希函数序列 发生冲突的关键字用下一个哈希函数确定位置 避免聚集链地址法19 14 23 01 68 20 27 55 11 10 790123456789101112 01142779 5568 1984 20 1023 11 查找成功的平均查找次数（1+2+3+4+1+2+1+2+1+1+2+1）/12=21/12=12/12=11+1/2=1.5链地址法查找成功的平均查找次数1+/2查找不成功的平均查找次数+e-
