09第9章 查找.ppt
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《09第9章 查找.ppt》由会员分享,可在线阅读,更多相关《09第9章 查找.ppt(94页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、第第9 9章章 查找查找 基本概念基本概念 静态查找表静态查找表 动态查找表动态查找表 哈希表哈希表基本概念基本概念查找表:查找表:由同一类型的数据元素(或记录)构成的由同一类型的数据元素(或记录)构成的集合。集合。对查找表进行的操作有以下四种:对查找表进行的操作有以下四种:查询查询某个某个特定的特定的数据元素是否在查找表中。数据元素是否在查找表中。检索检索某个某个特定的特定的数据元素的各种属性。数据元素的各种属性。在查找表中在查找表中插入插入一个数据元素。一个数据元素。从查找表中从查找表中删除删除某个数据元素。某个数据元素。静态查找表:静态查找表:对查找表只作前两种操作对查找表只作前两种操作
2、 。动态查找表:动态查找表:在查找过程中同时插入查找表中不存在查找过程中同时插入查找表中不存在的数据元素,或者从查找表中删除已存在的某个在的数据元素,或者从查找表中删除已存在的某个数据元素。数据元素。关键字:关键字:标志数据元素(或记录)中某个数据项的值,用它可以标标志数据元素(或记录)中某个数据项的值,用它可以标识一个数据元素识一个数据元素 。查找:查找:根据给定的某个值,在查找表中确定是否存在一个数据元素根据给定的某个值,在查找表中确定是否存在一个数据元素其关键字等于给定值的记录或数据元素其关键字等于给定值的记录或数据元素 。平均查找长度平均查找长度ASL ASL(Average Sear
3、ch Length)为:为:为确定记录在查找表中的位置,需和给定值进行比较的关键字个数的期望值其中:n 为表长 Pi 为查找表中第i个记录的概率 Ci为找到该记录时,曾和给定比较过的关键字的个数。静态查找表静态查找表顺序表的查找顺序表的查找有序表的查找有序表的查找索引顺序表的查找索引顺序表的查找顺序表的查找顺序表的查找基本思想:基本思想:从表的一端开始,顺序扫描线性表,依次用从表的一端开始,顺序扫描线性表,依次用待查找的关键字值与线性表里各结点的关键字值逐个比待查找的关键字值与线性表里各结点的关键字值逐个比较,若在表中找到了某个记录的关键字与待查找的关键较,若在表中找到了某个记录的关键字与待查
4、找的关键字值相等,表明查找成功;如果找遍所有结点也没有找字值相等,表明查找成功;如果找遍所有结点也没有找到与待查找的关键字值相等,则表明查找失败到与待查找的关键字值相等,则表明查找失败 。0 1 2 3 4 5 6 7(a)初态初态40803060102025(b)K=80(return i=4)80408030601020250 1 2 3 4 5 6 7(c)K=90(return i=0)0 1 2 3 4 5 6 79040803060102025 顺序查找的算法:顺序查找的算法:int Search_seq(SSTable ST,int n,int key)int i=n;ST0.k
5、ey=key;while(STi.key!=key)i-;/*从表尾往前查从表尾往前查*/return i;监视哨监视哨使使用用了了监监视视哨哨,在在查查找找过过程程中中,不不用用每每一一步步都都去去判判断断是是否否查查找找结结束。束。找找到到:返返回回元元素素在在线线性性表表中中的的存存储位置;储位置;未找到:返回未找到:返回0。根据上述算法可知:根据上述算法可知:查找成功时的平均查找成功时的平均查找次数查找次数为:为:ASL=(1+2+3+4+n)/n=(n+1)/2查找不成功时的查找不成功时的比较次数比较次数为:为:n+1则顺序查找的平均查找长度为:则顺序查找的平均查找长度为:ASL=(
6、n+1)/2+n+1)/2=(n+1)3/4顺序查找的优点:顺序查找的优点:算法简单,无需排序,采用顺序算法简单,无需排序,采用顺序和链式存储均可。和链式存储均可。缺点缺点:平均查找长度较大。:平均查找长度较大。因此,当因此,当n较大时,不宜采用顺序查找。较大时,不宜采用顺序查找。等概率查找的情况下折半查找折半查找基本思想:基本思想:首先用要查找的关键字值与中间位置结点的关键字值相比首先用要查找的关键字值与中间位置结点的关键字值相比较;比较结果如果相等,则查找完成;若不相等,再根据较;比较结果如果相等,则查找完成;若不相等,再根据要查找的关键字值与该中间结点关键码值的大小来确定下要查找的关键字
7、值与该中间结点关键码值的大小来确定下一步查找在哪个子表中进行:如果待查关键字大于中间结一步查找在哪个子表中进行:如果待查关键字大于中间结点的关键字值,则应查找中间结点以后的子表,否则,查点的关键字值,则应查找中间结点以后的子表,否则,查找中间结点以前的子表。找中间结点以前的子表。ST.elemST.length例如例如:key=64 的查找过程如下:lowhighmidlow mid high midlow 指示查找区间的下界high 指示查找区间的上界mid=(low+high)/2int Search_Bin(SSTable ST,KeyType key)low=1;high=ST.len
8、gth;/置区间初值 while(low data.key)else if(LT(key,T-data.key)else p=f;return FALSE;/查找不成功 p=T;return TRUE;/查找成功SearchBST(T-lchild,key,T,p);/在左子树中继续查找SearchBST(T-rchild,key,T,p);/在右子树中继续查找30201040352523fT设 key=48fTfT22pfTfTTTTfffp根据动态查找表的定义根据动态查找表的定义,“插入”操作在查找不成功时才进行;3二叉排序树的插入算法若二叉排序树为若二叉排序树为空树,则新插入的结点,则新
9、插入的结点为为新的根结点;否则,新插入的结点必;否则,新插入的结点必为一个为一个新的叶子结点,其,其插入位置由查由查找过程得到。找过程得到。Status Insert BST(BiTree&T,ElemType e)/当二叉排序树中不存在关键字等于当二叉排序树中不存在关键字等于 e.key 的的 /数据元素时,插入元素值为数据元素时,插入元素值为 e 的结点,并返的结点,并返 /回回 TRUE;否则,不进行插入并返回否则,不进行插入并返回FALSE if(!SearchBST(T,e.key,NULL,p)else return FALSE;/Insert BST s=(BiTree)mall
10、oc(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)被删除的结点)被删除的结点是叶子是叶子;(2)被删除的结点)被删除的结点只有左子树只有左子树或者或者只有右子只有右子树树;(3)被删除的结点)被删除的结点既有左子树,也有右子树既有左子树,也有右子树。4二叉排序树的删除算法二叉排
11、序树的删除算法可分三种情况讨论:和插入相反,删除在查找成功查找成功之后进行,并且要求在删除二叉排序树上某个结点之后,仍仍然保持二叉排序树的特性然保持二叉排序树的特性。50308020908540358832(1)被删除的结点是叶子结点叶子结点例如例如:被删关键字被删关键字=2088其双亲结点中相应指针域的值改为其双亲结点中相应指针域的值改为“空空”50308020908540358832(2)被删除的结点只有左子树只有左子树或者只有右子树只有右子树 其双亲结点的相应指针域的值改为其双亲结点的相应指针域的值改为“指向被删除结点的左子树或右子树指向被删除结点的左子树或右子树”。被删关键字被删关键字
12、=408050308020908540358832(3)被删除的结点既有左子树,也有右子树既有左子树,也有右子树4040以其前驱替代之,然以其前驱替代之,然后再删除该前驱结点后再删除该前驱结点被删结点前驱结点被删关键字被删关键字=505查找性能的分析查找性能的分析 对于每一棵特定的二叉排序树,均可按照平均查找长度的定义来求它的 ASL 值,显然,由值相同的 n 个关键字,构造所得的不同形态的各棵二叉排序树的平均查找长 度的值不同,甚至可能差别很大。由关键字序列 3,1,2,5,4构造而得的二叉排序树,由关键字序列 1,2,3,4,5构造而得的二叉排序树,例如:例如:2134535412ASL=
13、(1+2+3+4+5)/5 =3ASL=(1+2+3+2+3)/5 =2.2二二 平衡二叉树平衡二叉树(AVL(AVL树)树)概念:概念:或者是一棵空树,或者是具有下列性质的二叉树:或者是一棵空树,或者是具有下列性质的二叉树:它的左子树和右子树都是平衡二叉树。它的左子树和右子树都是平衡二叉树。左子树和右子树的深度之差的绝对值不超过左子树和右子树的深度之差的绝对值不超过1 1。实例:实例:不平衡的二叉树不平衡的二叉树 二叉平衡树二叉平衡树是二叉查找树的另一种形式实例:实例:构造关键字的序列为(构造关键字的序列为(1 1,2 2,3 3,9 9,5 5)的平衡)的平衡二叉树二叉树。构造二叉平衡(查
14、找)树的方法是:在插入过程中,采用平衡旋转技术。在插入过程中,采用平衡旋转技术。平衡处理的方法平衡处理的方法 :LLLL型调整:型调整:RRRR型调整:型调整:LRLR型调整:型调整:RLRL型调整型调整 :在平衡树上进行查找的过程和二叉排序树相同,因此,查找过程中和给定值进行比较的关键字的个数进行比较的关键字的个数不超过平衡 树的深度。平衡树的查找性能分析:平衡树的查找性能分析:在二叉平衡树二叉平衡树上进行查找时,查找过程中和给定值进行比较的关键字的个进行比较的关键字的个数和数和 log(n)相当。三三 B-树树1定义定义2查找过程查找过程3插入操作插入操作4删除操作删除操作5查找性能的分析
15、查找性能的分析1B-树的定义树的定义B-树是一种 平衡平衡 的 多路多路 查找查找 树:在 m 阶的B-树上,每个非终端结点可能含有:n 个关键字关键字 Ki(1 in)nm n 个指向记录的指针指向记录的指针 Di(1in)n+1 个指向子树的指针指向子树的指针 Ai(0in)多叉树的特性非终端结点(n,A0,K1,A1,K2,A2,,Kn,An)typedef struct BTNode int keynum;/结点中关键字个数,结点大小 struct BTNode *parent;/指向双亲结点的指针 KeyType keym+1;/关键字(0号单元不用)struct BTNode *p
16、trm+1;/子树指针向量 Record *recptrm+1;/记录指针向量 BTNode,*BTree;/B树结点和B树的类型B-树结构的树结构的C语言描述如下语言描述如下:非叶结点中的非叶结点中的多个关键字均均自小至大有序排有序排列,即:列,即:K1 K2 keynum;i=Search(p,K);/在p-key1.keynum中查找 i,p-keyi=Kkeyi+1 if(i0&p-keyi=K)found=TRUE;else q=p;p=p-ptri;/q 指示 p 的双亲 if(found)return(p,i,1);/查找成功 else return(q,i,0);/查找不成功在
17、查找不成功之后,需进行插入。显然,关键字插入插入的位置位置必定在最下最下层的非叶结点层的非叶结点,有下列几种情况:3插入插入1)插入后,该结点的关键字个数nm,不修改指针;例如2)插入后,该结点的关键字个数 n=m,则需进行“结点分裂”,令 s=m/2,在原结点中保留 (A0,K1,Ks-1,As-1);建新结点 (As,Ks+1,Kn,An);将(Ks,p)插入双亲结点;例如3)若双亲为空,则建新的根结点。例如例如:下列为 3 阶B-树50 20 40 80 插入关键字=60,60 80 90,60 80 90 90 50 80 60 30,40 20 30 50 808030 50 和插入
18、的考虑相反,首先必须找到待删关键字所在结点,并且要求删除之后,结点中关键字的个数不能小于m/2-1,否则,要从其左(或右)兄弟结点“借调”关键字,若其左和右兄弟结点均无关键字可借(结点中只有最少量的关键字),则必须进行结点的“合并”。4删除删除 在B-树中进行查找时,其查找时间主要花费在搜索结点(访问外存)上,即主要取决于B-树的深度树的深度。5查找性能的分析查找性能的分析结论:结论:在含在含 N 个关键字的个关键字的 B-树上进行一次查树上进行一次查找,需访问的结点个数不超过找,需访问的结点个数不超过 log m/2(N+1)/2)+1四、数字查找树四、数字查找树(键树)键树)1.数字查找树
19、(键树)的结构特点键树)的结构特点2.二路二路Trie(双链)树(双链)树3.多路多路Trie树树1.键树的结构特点:键树的结构特点:关键字中的各个符号分布在从根结点到叶的路径上,叶结点内的符号为“结束”的标志符。因此,键树的深度和关键字键树的深度和关键字集合的大小无关集合的大小无关;键树被约定为是一棵有序树,即同一层中兄弟结点之间依所含符号自左至右有序,并约定结束符$小于任何其它符号。HAD$S$VE$E$R$E$IGH$S$例如例如:表示关键字集合HAD,HAS,HAVE,HE,HER,HERE,HIGH,HIS 2.二路二路Trie(双链)树双链)树 以二叉链表作存储结构实现的键树typ
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 09第9章 查找 09
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内