数据结构--查表找PPT课件.ppt
《数据结构--查表找PPT课件.ppt》由会员分享,可在线阅读,更多相关《数据结构--查表找PPT课件.ppt(150页珍藏版)》请在三一文库上搜索。
1、1,第九章 查找表,2,何谓查找表 ?,查找表是由同一类型的数据元素(或记录)构成的集合。,由于“集合”中的数据元素之间存在着松散的关系,因此查找表是一种应用灵便的结构。,3,对查找表经常进行的操作:,查询某个“特定的”数据元素是否在查找表中; 检索某个“特定的”数据元素的各种属性; 在查找表中插入一个数据元素; 从查找表中删去某个数据元素。,4,仅作 前两种即查询和检索操作的查找表。 即检索的前后不会改变查找表的内容。,静态查找表,在查找过程中同时插入查找表中不存在的数据元素,或者从查找表中删除已存在的某个数据元素,此类表为动态查找表。即检索过程中可能会改变数据元素的存储位置。,动态查找表,
2、查找表可分为两类:,5,检索是确定数据元素集合中是否存在数据元素等于特定元素或是否存在元素满足某种给定特征的过程。,要进行检索,必须知道待检索对象的特征,也就是要知道待检索数据元素的关键字。,我们将能唯一标识一个数据元素的关键字称为主关键字,而其它关键字称为辅助关键字或从关键字。,6,是数据元素(或记录)中某个数据项的值,用以标识(识别)一个数据元素(或记录)。,关键字,若此关键字可以识别唯一的一个记录,则称之谓“主关键字”。,若此关键字能识别若干记录,则称 之谓“次关键字”。,7,根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素或(记录),查找,若查找表中存在这样一个记录,则
3、称“查找成功”,查找结果:给出整个记录的信息,或指示该记录在查找表中的位置; 否则称“查找不成功”,查找结果:给出 “空记录”或“空指针”。,8,如果查找表中的数据元素之间不存在明显的组织规律,则不便于查找。 例:查阅英文单词时,由于字典是按单词的字母在字母表中的次序编排的,因此查找时不需要从字典中第一个单词比较起,而只要根据待查单词的每个字母在字母表中的位置查到该单词。,如何进行查找?,查找的方法取决于查找表的结构。即取决于数据元素依何种关系组织在一起。,9,线性结构是数据元素间最常见的数据结构,基于线性表的检索运算在各类程序中应用非常广泛,我们介绍三种在线性表上进行检索的方法,它们分别是顺
4、序检索、二分法检索与分块检索。为简化问题,本节所介绍的检索方法均视为是基于静态查找表上的操作。,10,9.1 静 态 查 找 表,11,数据对象D:,数据关系R:,D是具有相同特性的数 据元素的集合。每个数 据元素含有类型相同的 关键字,可唯一标识数 据元素。,数据元素同属一个集合。,ADT StaticSearchTable /P216,12,Create(,Destroy(,Search(ST, key);,Traverse(ST, Visit();,基本操作 P:,next, ADT StaticSearchTable,13,构造一个含n个数据元素 的静态查找表ST。,Create(,操
5、作结果:,14,销毁表ST。,Destroy(,初始条件: 操作结果:,静态查找表ST存在;,15,若 ST 中存在其关键字等于 key 的数据元素,则函数值为该元素的值或在表中的位置,否则为“空”。,Search(ST, key);,初始条件: 操作结果:,静态查找表ST存在,key 为和查找表中元素的关键字类型相同的给定值;,16,按某种次序对ST的每个元素调用函数Visit()一次且仅一次,一旦Visit()失败,则操作失败。,Traverse(ST, Visit();,初始条件: 操作结果:,静态查找表ST存在,Visit 是对元素操作的应用函数;,17,typedef struct
6、/ 数据元素存储空间基址,建表时 / 按实际长度分配,0号单元留空 int length; / 表的长度 SSTable;,假设静态查找表的顺序存储结构为,ElemType *elem;,18,数据元素类型的定义为:,typedef struct keyType key; / 关键字域 / 其它属性域 ElemType ;, TElemType ;,19,一、顺序查找表,二、有序查找表,三、索引顺序表,20,以顺序表或线性链表表示静态查找表。 从表的一端开始,顺序(逐个)扫描线性表,依次将扫描到的结点关键字和给定值Key相比较,若当前扫描到的结点关键字与Key相等,则检索成功;若扫描结束后,仍
7、未找到关键字等于Key的结点,则检索失败。,一、顺序查找表,21,0 1 2 3 4 5 6 7 8 9 10 11,5 13 19 21 37 56 64 75 80 88 92,找64,64,监视哨,比较次数=5,比较次数: 查找第n个元素: 1 查找第n-1个元素:2 . 查找第1个元素: n 查找第i个元素: n+1-i 查找失败: n+1,查找过程:从表的一端开始逐个进行记录的关键字和给定值的比较。 例如:,22,ST.elem,i,ST.elem,i,60,i,key=64,key=60,i,64,23,int Search_Seq(SSTable ST, KeyType key)
8、 / 在顺序表ST中顺序查找其关键字等于 / key的数据元素。若找到,则函数值为 / 该元素在表中的位置,否则为0。 ST.elem0.key = key; / “哨兵” for (i=ST.length; ST.elemi.key!=key; -i); / 从后往前找 return i; / 找不到时,i为0 / Search_Seq,24,定义: 查找算法的平均查找长度 (Average Search Length) 也就是为确定某一结点在数据集合中的位置,给定值 与集合中的结点关键字所需进行的比较次数。 其中: n 为表长,Pi 为查找表中第i个记录的概率, 且 Ci为找到该记录时,曾
9、和给定值 比较过的关键字的个数,分析顺序查找的时间性能。,25,在等概率查找的情况下, 顺序表查找的平均查找长度为:,对顺序表而言,Ci = n-i+1,ASL = nP1 +(n-1)P2 + +2Pn-1+Pn,26,若查找概率无法事先测定,则查找过程采取的改进办法是,可以在记录中附设一个访问频度域,使查找概率大的记录在查找过程中不断后移,以便在以后的查找过程中减少比较次数,在不等概率查找的情况下,ASLss 在 PnPn-1P2P1 时取极小值,ASL = nP1 +(n-1)P2 + +2Pn-1+Pn,27,上述顺序查找表的查找算法简单, 但平均查找长度较大,特别不适用于表长较大的查
10、找表。,二、有序查找表,若以有序表表示静态查找表,则查找过程可以基于“折半”进行。,28,1.设表长为n,low、high和mid分别指向待查元素所在区间的上界、下界和中点,k为给定值。 2.初始时,令 low=1,high=n,mid=(low+high)/2 让k与mid指向的记录比较 若k=rmid.key,查找成功 若krmid.key,则low=mid+1 3.重复上述操作,直至lowhigh时,查找失败。,折半查找算法实现,29,ST.elem,ST.length,例如: key=64 的查找过程如下,low,high,mid,low,mid,high,mid,low 指示查找区间
11、的下界; high 指示查找区间的上界; mid = (low+high)/2。,30,int Search_Bin ( SSTable ST, KeyType key ) low = 1; high = ST.length; / 置区间初值 while (low = high) mid = (low + high) / 2; if (EQ (key , ST.elemmid.key) ) return mid; / 找到待查元素 else if ( LT (key , ST.elemmid.key) ) high = mid - 1; / 继续在前半区间进行查找 else low = mid
12、 + 1; / 继续在后半区间进行查找 return 0; / 顺序表中不存在待查元素 / Search_Bin,31,先看一个具体的情况,假设:n=11,分析折半查找的平均查找长度,6,3,9,1,4,2,5,7,8,10,11,判定树,1,2,2,3,3,3,3,4,4,4,4,32,在n50时,可得近似结果,一般情况下,表长为 n 的折半查找的判定树的深度和含有 n 个结点的完全二叉树的深度相同。因此具有n个结点的判定树的深度为 +1。为了方便起见,以满二叉树为例,树中层次为1的结点有1个,层次为2的结点有2个,层次为h的结点有2h1个.,33,在 n50 时,可得近似结果,可见, 折半
13、查找的效率比顺序查找高。 折半查找只能适用于有序表,并且以顺序存储结构存储。,34,顺序表和有序表的比较,35,三、索引顺序表,以索引顺序表表示静态查找表,search操作可用分块查找来实现。 分块查找又称索引顺序查找,这是顺序查找的一种改进方法。在此查找方法中,除表本身以外,尚需建立一个“索引表”。,36,例如,表中含有18个元素,可分成三个子表。对每个子表(或称块)建立一个索引项,其中包括两项内容:关键字项(其值为该子表内的最大关键字)和项指针(指示该子表的第一个元素在表中位置)。,索 引 表,最大关键字,起始地址,37,索引表按关键字有序,故表或者有序,或者分块有序。所谓“分块有序” 是
14、指一个子表中所有元素的关键字均大于前一个子表的最大关键字。,38,索引顺序表的查找过程:,1)由索引确定记录所在区间;,2)在顺序表的某个区间内进行查找。,注意:索引可以根据查找表的特点来构造。,可见, 索引顺序查找的过程也是一个 “缩小区间”的查找过程。,39,1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18,22 12 13 8 9 20 33 42 44 38 24 48 60 58 74 57 86 53,22 48 86,1 7 13,索引表,查38,例如,40,索引顺序查找的平均查找长度 = 查找“索引”的平均查找长度 + 查找“顺序表”的平
15、均查找长度,41,分块查找方法评价,当 时,ASL取最小值 +1,42,查找方法比较,顺序查找,折半查找,分块查找,43,9.2 动 态 查 找 表,44,动态查找表的特点:表结构本身是在查找过程中动态生成。若表中存在其关键字等于给定值key的记录,表明查找成功;否则插入关键字等于key的记录。,45,ADT DynamicSearchTable ,抽象数据类型动态查找表的定义如下:,数据对象D: 数据关系R:,数据元素同属一个集合。,D是具有相同特性的数据元素的集合。 每个数据元素含有类型相同的关键字, 可唯一标识数据元素。,46,InitDSTable(/按某种次序对DT的每个结点调用函数
16、 Visit() 一次且至多一次。,基本操作:,next,ADT DynamicSearchTable,47,一、二叉排序树(二叉查找树),二、二叉平衡树,三、B - 树,四、B+树,48,一、二叉排序树 (二叉查找树),1定义,2查找算法,3插入算法,4删除算法,5查找性能的分析,49,(1)若它的左子树不空,则左子树上 所有结点的值均小于根结点的值;,1定义:,二叉排序树或者是一棵空树;或者 是具有如下特性的二叉树:,(3)它的左、右子树也都分别是二叉 排序树。,(2)若它的右子树不空,则右子树上 所有结点的值均大于根结点的值;,50,50,30,80,20,90,10,85,40,35,
17、25,23,88,例如:,是二叉排序树,66,不,51,通常,取二叉链表作为 二叉排序树的存储结构,typedef struct BiTNode / 结点结构 struct BiTNode *lchild, *rchild; / 左右孩子指针 BiTNode, *BiTree;,TElemType data;,52,2二叉排序树的查找算法:,1)若给定值等于根结点的关键字,则查找成功; 2)若给定值小于根结点的关键字,则继续在左子树上进行查找; 3)若给定值大于根结点的关键字,则继续在右子树上进行查找。,否则,若二叉排序树为空,则查找不成功;,53,50,30,80,20,90,85,40,3
18、5,88,32,例如:,二叉排序树,查找关键字,= 50 ,50,50,35 ,50,30,40,35,50,90 ,50,80,90,95,54,从上述查找过程可见,,在查找过程中,生成了一条查找路径:,从根结点出发,沿着左分支或右分支逐层向下直至关键字等于给定值的结点;,或者,从根结点出发,沿着左分支或右分支逐层向下直至指针指向空树为止。,查找成功,查找不成功,55,BiTree SearchBST( BiTree T, KeyType key) /在根指针T所指二叉排序树中递归地查找某关键字 /等于Key的数据元素,若查找成功,则返回指向 /该数据元素的指针,否则返回空指针 if (!T
19、)| EQ(key, T-data.key) return (T);/查找结束 else if LT(key, T-data.key) return(SearchBST(T-lchild, key) else return (SearchBST(T-rchild, key); /SearchBST,56,二叉排序树是一种动态树表,其特点是,树的结构通常不是一次生成的,而是在查找的过程中,当树中不存在关键字等于给定值的结点时进行插入。 新插入的结点一定是一个新添加的叶子结点,并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。为此将二叉树的查找算法改为如下算法,57,算法描述如下
20、:,Status SearchBST (BiTree T, KeyType key, BiTree f, BiTree / SearchBST, ,否则表明查找不成功,返回 / 指针 p 指向查找路径上访问的最后一个结点, / 并返回函数值为FALSE, 指针 f 指向当前访问 / 的结点的双亲,其初始调用值为NULL,58,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,59,if (!T) else if ( EQ(key, T-data.key) ) else if ( LT(key, T-da
21、ta.key) ) else, p = f; return FALSE; / 查找不成功, p = T; return TRUE; / 查找成功,SearchBST (T-lchild, key, T, p ); / 在左子树中继续查找,SearchBST (T-rchild, key, T, p ); / 在右子树中继续查找,Status SearchBST (BiTree T, KeyType key, BiTree f, BiTree &p ) , / SearchBST,60,根据动态查找表的定义,“插入”操作在查找不成功时才进行;,3二叉排序树的插入算法,若二叉排序树为空树,则新插入
22、的结点为新的根结点;否则,新插入的结点必为一个新的叶子结点,其插入位置由查找过程得到。,61,对于输入实例(30,20,40,10,25,45),创建二叉排序树的过程如下:,按照(30,20,10,25,40,45)或(30,40,45,20,10,25)的输入次序同样可生成图(g)所示的二叉排序树。,但若按照(10,20,25,30,40,45)或(45,40,30,25,20,10)的次序输入,将分别生成只具有单个右分支和单个左分支的两棵二叉排序树。,62,结论: 二叉排序树的形态与数据的输入次序相关;,63,Status Insert BST(BiTree / Insert BST,64
23、,(1)被删除的结点是叶子; (2)被删除的结点只有左子树或者只有右子树; (3)被删除的结点既有左子树,也有右子树。,4二叉排序树的删除算法,可分三种情况讨论:,和插入相反,删除在查找成功之后进行,并且要求在删除二叉排序树上某个结点之后,仍然保持二叉排序树的特性。,65,50,30,80,20,90,85,40,35,88,32,(1)被删除的结点是叶子结点,例如:,被删关键字 = 20,88,其双亲结点中相应指针域的值改为“空”,66,50,30,80,20,90,85,40,35,88,32,(2)被删的结点只有左子树或只有右子树,其双亲结点的相应指针域的值改为 “指向被删除结点的左子树
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 查表找 PPT 课件
链接地址:https://www.31doc.com/p-2803761.html