《数据结构教程》第八章查找.ppt

《《数据结构教程》第八章查找.ppt》由会员分享，可在线阅读，更多相关《《数据结构教程》第八章查找.ppt（24页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构数据结构第一章第一章 绪论绪论第二章第二章 线性表线性表第三章第三章 稀疏矩阵和广义表稀疏矩阵和广义表第四章第四章 栈和队列栈和队列第五章第五章 树和二叉树树和二叉树第六章第六章 二叉树的应用二叉树的应用第七章第七章 图图第八章第八章 查找查找第九章第九章 排序排序第八章 查找 8.1 对查找的操作：l l1 1）查询(检索)某个“特定的”数 据元素是否在查找表中及各 种属性；l l2 2）在查找表中在查找表中插入一个数据元素；一个数据元素；l l3 3）从查找表中）从查找表中删去某个数据元素。某个数据元素。1.顺序查找顺序查找2.二分查找二分查找3.索引顺序索引顺序8.2 8.2 静

2、态查找表静态查找表顺序搜索的平均搜索长度顺序搜索的平均搜索长度 设搜索第设搜索第 i 个元素的概率为个元素的概率为 pi，搜索到第，搜索到第 i 个元素个元素所需比较次数为所需比较次数为 ci，则搜索成功的平均搜索长度，则搜索成功的平均搜索长度:在顺序搜索情形，在顺序搜索情形，ci=i+1,i=0,1,n-1，因此，因此在等概率情形，在等概率情形，pi=1/n,i=0,1,n-1。1.顺序查找顺序查找顺序查找算法Struc elemtypeeneytype data;keytype key;Int seqserch(elemtype a,int n,keytype k)an.key=k;for

3、(int i=0;i+)if(ai.key=k)break;If(in)return IElse return-1;2.二分查找条件：表已排序思想：第一步把表一分为二；判定查找的元素落在哪部分；依据上述步骤重复直到最后找到（或对半结束查找不成功）算法下一页Int binserch(elemtype a,int low,int hiht,keytype k)if(low=high)int mid=(low+high)/2;if(k=amid.key)return mid;else if(kamid.key)return binserch(a,low,mid-1,k);else return bi

4、nserch(a,mid,high-1,k)return-1;下一页图示搜索成功的例子搜索成功的例子 搜索失败的例子搜索失败的例子下一页判定树搜索成功的情形搜索成功的情形 搜索不成功的情形搜索不成功的情形从有序表构造出的二叉搜索树从有序表构造出的二叉搜索树(判定树判定树)n n 若设若设 n=2h-1，2h=n+1,h=log2(n+1)。n n 第第0层结点有层结点有1个，搜索第个，搜索第0层结点要比较层结点要比较1次；次；第第1层结点有层结点有2个，搜索第个，搜索第1层结点要比较层结点要比较2次；次；，顺序查找表的查找算法简单，顺序查找表的查找算法简单，但但 平均查找长度较大，特别不适用于

5、平均查找长度较大，特别不适用于 表长较大的查找表。表长较大的查找表。总结：总结：有序查找表有序查找表 若以若以有序表有序表表示静态查找表，则表示静态查找表，则查找过程可以基于查找过程可以基于“折半折半”进行。进行。5.3 索引顺序表的查找过程：索引顺序表的查找过程：1）由索引确定记录所在区间；）由索引确定记录所在区间；2）在顺序表的某个区间内进行查找。）在顺序表的某个区间内进行查找。索引可以根据查找表的特点来构造。索引可以根据查找表的特点来构造。索引顺序查找索引顺序查找的过程也是一个的过程也是一个“缩小区间缩小区间”的查找过程。的查找过程。一、索引顺序查找的数据结构：一、索引顺序查找的数据结构

6、：Struct indexitemindexkeytype index;int start;int length;职工号职工号 姓名姓名JS001JS002JS003JS004DZ001DZ002DZ003JJ001JJ002HG001HG002HG003主表主表Js04Dz43Jj72hg930123Index start lengh索引表索引表二、分块查找：二、分块查找：在索引表为稀疏索引在索引表为稀疏索引15261834367240574386939834 72 9805104530 1 20 1 2 3 4 5 6 7 8 9 10 11 12 13 14IndexStartlengh

7、索引表索引表主表主表注：同一块中的数据没有排序注：同一块中的数据没有排序8.4 散散 列列 查查 找找动态查找表动态查找表一、散列的概念一、散列的概念散列：通过对表中的每个元素关健字散列：通过对表中的每个元素关健字K为自变量的为自变量的H()计算出一值作为一连续存储空间的位置计算出一值作为一连续存储空间的位置,并将并将该元素存储到这个单元中该元素存储到这个单元中.此函数称散列函数或此函数称散列函数或哈希函数哈希函数.()称散列地址或哈希地址称散列地址或哈希地址,上述的存储上述的存储空间称散列表或哈希表空间称散列表或哈希表.例例:A=(18,75,60,43,54,90,46)h(k)=k%m

8、:m为散列表的长度为散列表的长度=1343 1860750 1 2 3 4 5 6 7 8 9 10 11 12549046同义词冲突同义词冲突:70下一页冲突引起冲突的三个原因引起冲突的三个原因:一、装填因子一、装填因子:=n/m 二、与散函数有关二、与散函数有关三、与解决的方法有关三、与解决的方法有关1.直接定址法直接定址法3.数字分析法数字分析法5.折叠法折叠法4.平方取中法平方取中法2.除留余数法除留余数法二、对数字的关键字可有下列构造方法：二、对数字的关键字可有下列构造方法：若是非数字关键字，则需先对其进若是非数字关键字，则需先对其进行数字化处理。行数字化处理。1.直接定址法直接定址

9、法:h(k)=k+c3.数字分析法数字分析法:(92326875,92343634,92774638,92381262,92394220)5.折叠法：折叠法：k=68242324,散列分三散列分三段段682，423，240，叠加和：，叠加和：1345，其散列地址为：其散列地址为：3454.平方取中法平方取中法:322 取中三位取中三位10242.除留余数法除留余数法:h(k)=k%m三、处理冲突的方法三、处理冲突的方法 “处理冲突处理冲突”的实际含义是：的实际含义是：为产生冲突的地址寻找下一个哈希地址。为产生冲突的地址寻找下一个哈希地址。1.开放定址法开放定址法181 2 3 4 5 6 7

10、82627非同义词冲突非同义词冲突线性探查法线性探查法2.链接法链接法 0 1 2 3 4 5 6 7 8 9 10 11 12B(18,75,60,43,54,90,46,31,58,73,15,34)H(k)=k%13155443315846347518736090 8.5 B-树查找树查找1定义定义2查找过程查找过程3插入操作插入操作4查找性能的分析查找性能的分析 在在 m 阶的阶的B-树上，每个非终端结点树上，每个非终端结点 可能含有：可能含有：n 个个关键字关键字 Ki（1 in）nm 或或 n 个个指向记录的指针指向记录的指针 Di（1in）n+1 个个指向子树的指针指向子树的指针

11、 Ai（0in）多叉树的特性多叉树的特性162amt215381621 8 2 21 26 1 45bcdefgh 非叶结点中的多个关键字均自小至大有序排列，即：K1 K2 Kn；Ai-1 所指子树上所有关键字均小于Ki；Ai 所指子树上所有关键字均大于Ki；查找树的特性查找树的特性平衡树的特性平衡树的特性l l树中所有叶子结点均不带信息，且在树中的同一层次上；l l根结点或为叶子结点，或至少含有两棵子树；l l其余所有非叶结点均至少含有m/2棵子树，至多含有 m 棵子树；B-树的定义树的定义B-树是一种树是一种 平衡平衡 的的 多路多路 查找查找 树：树：root50 15 71 84 3 8 20 26 43 56 62 78 89 96