第八讲查找表.ppt
《第八讲查找表.ppt》由会员分享,可在线阅读,更多相关《第八讲查找表.ppt(170页珍藏版)》请在三一文库上搜索。
1、何谓查找表 ?,查找表是由同一类型的数据元素(或记录)构成的集合。,由于“集合”中的数据元素之间存在着松散的关系,因此查找表是一种应用灵便的结构。,对查找表经常进行的操作:,1)查询某个“特定的”数据元素是否在查找表中; 2)检索某个“特定的”数据元素的各种属性; 3)在查找表中插入一个数据元素; 4)从查找表中删去某个数据元素。,仅作查询和检索操作的查找表。,静态查找表,有时在查询之后,还需要将“查询”结果为“不在查找表中”的数据元素插入到查找表中;或者,从查找表中删除其“查询”结果为“在查找表中”的数据元素。,动态查找表,查找表可分为两类:,是数据元素(或记录)中某个数据项的值,用以标识(
2、识别)一个数据元素(或记录)。,关键字,若此关键字可以识别唯一的一个记录,则称之谓“主关键字”。,若此关键字能识别若干记录,则称 之谓“次关键字”。,根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素或(记录)。,查找,若查找表中存在这样一个记录,则称“查找成功”。查找结果给出整个记录的信息,或指示该记录在查找表中的位置; 否则称“查找不成功”。查找结果给出 “空记录”或“空指针”。,由于查找表中的数据元素之间不存在明显的组织规律,因此不便于查找。 为了提高查找的效率, 需要在查找表中的元素之间人为地 附加某种确定的关系,换句话说, 用另外一种结构来表示查找表。,如何进行查找?,
3、查找的方法取决于查找表的结构。,9.1 静态查找表,9.2 动态查找树表,9.3 哈希表,9.1 静 态 查 找 表,数据对象D:,数据关系R:,D是具有相同特性的数 据元素的集合。每个数 据元素含有类型相同的 关键字,可唯一标识数 据元素。,数据元素同属一个集合。,ADT StaticSearchTable ,Create(,Destroy(,Search(ST, key);,Traverse(ST, Visit();,基本操作 P:, ADT StaticSearchTable,构造一个含n个数据元素 的静态查找表ST。,Create(,操作结果:,销毁表ST。,Destroy(,初始条件
4、: 操作结果:,静态查找表ST存在;,若 ST 中存在其关键字等于 key 的数据元素,则函数值为该元素的值或在表中的位置,否则为“空”。,Search(ST, key);,初始条件: 操作结果:,静态查找表ST存在,key 为和查找表中元素的关键字类型相同的给定值;,按某种次序对ST的每个元素调用函数Visit()一次且仅一次,一旦Visit()失败,则操作失败。,Traverse(ST, Visit();,初始条件: 操作结果:,静态查找表ST存在,Visit 是对元素操作的应用函数;,typedef struct / 数据元素存储空间基址,建表时 / 按实际长度分配,0号单元留空 int
5、 length; / 表的长度 SSTable;,假设静态查找表的顺序存储结构为,ElemType *elem;,数据元素类型的定义为:,typedef struct keyType key; / 关键字域 / 其它属性域 ElemType ;, TElemType ;,一、顺序查找表,二、有序查找表,三、静态查找树表,四、索引顺序表,以顺序表或线性链表表示静态查找表,一、顺序查找表,ST.elem,回顾顺序表的查找过程:,假设给定值 e=64, 要求 ST.elemk = e, 问: k = ?,k,k,int location( SqList L, ElemType /location,S
6、T.elem,i,ST.elem,i,60,i,key=64,key=60,i,64,int Search_Seq(SSTable ST, KeyType key) / 在顺序表ST中顺序查找其关键字等于 / key的数据元素。若找到,则函数值为 / 该元素在表中的位置,否则为0。 ST.elem0.key = key; / “哨兵” for (i=ST.length; ST.elemi.key!=key; -i); / 从后往前找 return i; / 找不到时,i为0 / Search_Seq,定义: 查找算法的平均查找长度 (Average Search Length) 为确定记录在查
7、找表中的位置,需和给定值 进行比较的关键字个数的期望值 其中: n 为表长,Pi 为查找表中第i个记录的概率, 且 , Ci为找到该记录时,曾和给定 值比较过的关键字的个数。,分析顺序查找的时间性能,在等概率查找的情况下, 顺序表查找的平均查找长度为:,对顺序表而言,Ci = n- i+1,ASL = nP1 +(n-1)P2 + +2Pn-1+Pn,若查找概率无法事先测定,则查找过程采取的改进办法是,在每次查找之后,将刚刚查找到的记录直接移至表尾的位置上。,在不等概率查找的情况下,ASLss 在 PnPn-1P2P1 时取极小值,上述顺序查找表的查找算法简单, 但平均查找长度较大,特别不适用
8、于表长较大的查找表。,二、有序查找表,若以有序表表示静态查找表,则查找过程可以基于“折半”进行。,ST.elem,ST.length,例如: key=64 的查找过程如下:,low,high,mid,low,mid,high,mid,low 指示查找区间的下界 high 指示查找区间的上界 mid = (low+high)/2,int Search_Bin ( SSTable ST, KeyType key ) low = 1; high = ST.length; / 置区间初值 while (low = high) mid = (low + high) / 2; if (EQ (key ,
9、ST.elemmid.key) ) return mid; / 找到待查元素 else if ( LT (key , ST.elemmid.key) ) high = mid - 1; / 继续在前半区间进行查找 else low = mid + 1; / 继续在后半区间进行查找 return 0; / 顺序表中不存在待查元素 / Search_Bin,先看一个具体的情况,假设:n=11,分析折半查找的平均查找长度,6,3,9,1,4,2,5,7,8,10,11,判定树,1,2,2,3,3,3,3,4,4,4,4,假设 n=2h-1 并且查找概率相等 则 在n50时,可得近似结果,一般情况下,
10、表长为 n 的折半查找的判定树的深度和含有 n 个结点的完全二叉树的深度相同。,关键字: A B C D E Pi: 0.2 0.3 0.05 0.3 0.15 Ci: 2 3 1 2 3,三、静态查找树表,在不等概率查找的情况下,折半查找不是有序表最好的查找方法。,例如:,此时 ASL=20.2+30.3+10.05+20.3+30.15=2.4,若改变Ci的值 2 1 3 2 3,则 ASL=20.2+10.3+30.05+20.3+30.15=1.9,使 达最小的判定树称为最优二叉树, 其中:,定义:,为计算方便,令 wi = pi 选择二叉树的根结点, 使 达最小,介绍一种次优二叉树的
11、构造方法:,为便于计算,引入累计权值和 并设 wl-1 = 0 和 swl-1 = 0, 则推导可得,0,2,3,8,11,15,18,23,例如:,l,h,21,18,12,4,3,10,18,h,9,6,0,8,E,C,2,1,A,h,5,3,l,h,G,3,0,1,3,E,C,G,A,B,D,F,所得次优二叉树如下所示:,查找比较“总次数” = 32+41+25+33 +14+33+25 = 52,查找比较“总次数” = 32+21+35+13 +34+23+35 = 59,和折半查找相比较,D,B,A,C,F,E,G,Status SecondOptimal(BiTree / 生成结点
12、,构造次优二叉树的算法,CONTINUE,if (i=low) T-lchild = NULL; / 左子树空 else SecondOptimal(T-lchild, R, sw, low, i-1); / 构造左子树 if (i=high) T-rchild = NULL; / 右子树空 else SecondOptimal(T-rchild, R, sw, i+1, high); / 构造右子树 return OK; / SecondOptimal,次优查找树采用二叉链表的存储结构,Status CreateSOSTre(SOSTree / CreatSOSTree,索引顺序表的查找过程
13、:,1)由索引确定记录所在区间;,2)在顺序表的某个区间内进行查找。,注意:索引可以根据查找表的特点来构造。,可见, 索引顺序查找的过程也是一个 “缩小区间”的查找过程。,索引顺序查找的平均查找长度 = 查找“索引”的平均查找长度 + 查找“顺序表”的平均查找长度,ADT DynamicSearchTable ,抽象数据类型动态查找表的定义如下:,数据对象D: 数据关系R:,数据元素同属一个集合。,D是具有相同特性的数据元素的集合。 每个数据元素含有类型相同的关键字, 可唯一标识数据元素。,InitDSTable(&DT),基本操作P:,DestroyDSTable(&DT),SearchDS
14、Table(DT, key);,InsertDSTable(,DeleteDSTable(,TraverseDSTable(DT, Visit();,ADT DynamicSearchTable,操作结果:,构造一个空的动态查找表DT。,InitDSTable(,销毁动态查找表DT。,DestroyDSTable(,初始条件: 操作结果:,动态查找表DT存在;,若DT中存在其关键字等于 key的数据元素,则函数值为该元素的值或在表中的位置,否则为“空”。,SearchDSTable(DT, key);,初始条件: 操作结果:,动态查找表DT存在,key 为和关键字类型相同的给 定值;,动态查找
15、表DT存在, e 为待插入的数据元素;,InsertDSTable(,初始条件: 操作结果:,若DT中不存在其关键字 等于 e.key 的 数据元素, 则插入 e 到DT。,动态查找表DT存在,key 为和关键字类型相同的给 定值;,DeleteDSTable(,初始条件: 操作结果:,若DT中存在其关键字等于key的数据元素,则删 除之。,动态查找表DT存在,Visit 是对结点操作的应用函数;,TraverseDSTable(DT, Visit();,初始条件: 操作结果:,按某种次序对DT的每个结 点调用函数 Visit() 一次且至 多一次。一旦 Visit() 失败, 则操作失败。,
16、9.2 动 态 查 找 树 表,(n) (1) (n) (1) (nlogn),综合上一节讨论的几种查找表的特性:,查找 插入 删除,无序顺序表 无序线性链表 有序顺序表 有序线性链表 静态查找树表,(n) (n) (logn) (n) (logn),(1) (1) (n) (1) (nlogn),1)从查找性能看,最好情况能达 (logn),此时要求表有序;,2)从插入和删除的性能看,最好 情况能达(1),此时要求存储 结构是链表。,可得如下结论:,一、二叉排序树(二叉查找树),二、二叉平衡树,三、B - 树,四、B+树,五、键 树,一、二叉排序树 (二叉查找树),1定义,2查找算法,3插入
17、算法,4删除算法,5查找性能的分析,(1)若它的左子树不空,则左子树上 所有结点的值均小于根结点的值;,1定义:,二叉排序树或者是一棵空树;或者 是具有如下特性的二叉树:,(3)它的左、右子树也都分别是二叉 排序树。,(2)若它的右子树不空,则右子树上 所有结点的值均大于根结点的值;,50,30,80,20,90,10,85,40,35,25,23,88,例如:,是二叉排序树。,66,不,通常,取二叉链表作为 二叉排序树的存储结构,typedef struct BiTNode / 结点结构 struct BiTNode *lchild, *rchild; / 左右孩子指针 BiTNode, *
18、BiTree;,TElemType data;,2二叉排序树的查找算法:,1)若给定值等于根结点的关键字,则查找成功; 2)若给定值小于根结点的关键字,则继续在左子树上进行查找; 3)若给定值大于根结点的关键字,则继续在右子树上进行查找。,若二叉排序树为空,则查找不成功;否则,50,30,80,20,90,85,40,35,88,32,例如:,二叉排序树,查找关键字,= 50 ,50,50,35 ,50,30,40,35,50,90 ,50,80,90,95 ,从上述查找过程可见,,在查找过程中,生成了一条查找路径:,从根结点出发,沿着左分支或右分支逐层向下直至关键字等于给定值的结点;,或者,
19、从根结点出发,沿着左分支或右分支逐层向下直至指针指向空树为止。,查找成功,查找不成功,算法描述如下:,Status SearchBST (BiTree T, KeyType key, BiTree f, BiTree / SearchBST, ,否则表明查找不成功,返回 / 指针 p 指向查找路径上访问的最后一个结点, / 并返回函数值为FALSE, 指针 f 指向当前访问 / 的结点的双亲,其初始调用值为NULL,if (!T) else if ( EQ(key, T-data.key) ) else if ( LT(key, T-data.key) ) else, p = f; retur
20、n FALSE; / 查找不成功, p = T; return TRUE; / 查找成功,SearchBST (T-lchild, key, T, p ); / 在左子树中继续查找,SearchBST (T-rchild, key, T, p ); / 在右子树中继续查找,30,20,10,40,35,25,23,f,T,设 key = 48,f,T,f,T,22,p,f,T,f,T,T,T,T,f,f,f,p,根据动态查找表的定义,“插入”操作在查找不成功时才进行;,3二叉排序树的插入算法,若二叉排序树为空树,则新插入的结点为新的根结点;否则,新插入的结点必为一个新的叶子结点,其插入位置由查
21、找过程得到。,Status Insert BST(BiTree / Insert BST, ,s = (BiTree) malloc (sizeof (BiTNode); / 为新结点分配空间 s-data = e; s-lchild = s-rchild = NULL;,if ( !p ) T = s; / 插入 s 为新的根结点,else if ( LT(e.key, p-data.key) ) p-lchild = s; / 插入 *s 为 *p 的左孩子 else p-rchild = s; / 插入 *s 为 *p 的右孩子,return TRUE; / 插入成功,(1)被删除的结点
22、是叶子; (2)被删除的结点只有左子树或者只有右子树; (3)被删除的结点既有左子树,也有右子树。,4二叉排序树的删除算法,可分三种情况讨论:,和插入相反,删除在查找成功之后进行,并且要求在删除二叉排序树上某个结点之后,仍然保持二叉排序树的特性。,50,30,80,20,90,85,40,35,88,32,(1)被删除的结点是叶子结点,例如:,被删关键字 = 20,88,其双亲结点中相应指针域的值改为“空”,50,30,80,20,90,85,40,35,88,32,(2)被删除的结点只有左子树 或者只有右子树,其双亲结点的相应指针域的值改为 “指向被删除结点的左子树或右子树”。,被删关键字
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第八 查找
链接地址:https://www.31doc.com/p-2626806.html