合工大数据结构 09-查找资料

1、1数 据 结 构（第九章 查找） Data Structures张晶计算机与信息(xnx)学院 2022/7/25共六十页2第九章 查 找 第九章 查 找 9.1 概述 9.2 顺序表的查找(ch zho) 9.3 树表的查找 9.4 散列表的查找 共六十页39.1 概述(i sh)查找是现实生活和软件设计中最常用的运算，例如，查字典、辞典、电话号码(din hu ho m)，高考成绩查询 ，考试成绩查询因此，查找方法的性能会影响到软件系统的性能。对此，涉及到几个相关的问题：如何设计查找方法？如何评价查找性能？如何组织数据，以便能更好地提高查找的性能？本章主要内容：介绍查找的相关概念，围绕几种

2、常见的数据表， 讨论查找的方法，并分析其性能。 共六十页49.1 概述(i sh)查找： 在数据集（表）中找出一个特定元素（的位置）。这一概念中涉及到以下几个相关的问题：（1）数据表：什么样数据表？ 也就是数据表的组织形式？例如：汉语字典、英语辞典；一个城市的电话号码簿。高考成绩表。查找表： 同类型的数据元素（记录）所构成的集合。 顺序表：数据元素构成一个序列。 树表：以树结构的形式组织。 散列表：以某种函数的方式来确定(qudng)元素的地址，实现数据表的组织。 索引表：为元素建立索引，以提高查找的速度。显然，查找的方法取决于数据表的组织形式。例如：在汉语字典和英语辞典中的查找就有明显差异。

3、因此，需要注意：如何确定查表结构？如何实现对给定数据表的查找？共六十页59.1 概述(i sh)（2）关于其中的特定元素 如何标识所需要(xyo)查找的元素？以高考成绩为例，显然是以准考证号标识的。更一般地说，涉及到字段 字段：如第一章所述，一个元素通常包括多个字段， 查找表中的元素也由多个字段（项）组成。例如，高考成绩信息中，包括姓名、准考证号、各单科成绩和总分等字段。 称其中可以标识元素的字段关键字，分两种情况： 主关键字：唯一标识一个元素的字段例如，高考成绩信息中的“准考证号”字段。次关键字：可能标识到多个元素的字段例如，高考成绩信息中的“考生姓名”字段， 因为现实中有太多同名同姓的人。

4、共六十页69.1 概述(i sh)（3）如何查找？取决于查找表的组织方式。例如：汉语字典的查找方法；英语词典的查找方法；某单位通信录中查找特定单位的方法等。（4）查找成功和查找失败：若找到指定的元素，则称为查找成功；否则称为查找失败 （5）如何评价查找方法的性能？以查找长度来描述(mio sh)查找长度： 查找过程中所做的元素或关键字的比较次数。 涉及到: 平均查找长度ASL， 最大查找长度 失败查找长度共六十页79.2 顺序(shnx)表的查找问题描述： 查找表以顺序结构来存储，典型(dinxng)地是一维数组；也可能是链表，或顺序文件本章更多地讨论是面向一维数组要求在此表中找出关键字的值为

5、x的元素的位置，若查找成功，则返回其位置（即下标），否则，返回一个表示元素不存在的下标（如0或-1）。按照查找表中数据的特性，以及对应的查找方法，可分为以下几种：简单顺序查找-没有任何关于数据元素分布的特性有序表查找-二分查找（折半查找）索引表查找-数据表分块有序共六十页89.2 顺序(shnx)表的查找9.2.1 简单顺序查找 问题描述:在数组An中查找元素关键字为x的元素，若查找成功，则返回(fnhu)元素的下标，否则返回(fnhu)-1。分析：显然只能依次搜索（比较元素）。按照什么样的查找顺序？即从前往后还是从后往前？A01234in-1a1a2a3a4a5ai-1anX共六十页99.2

6、.1简单顺序(shnx)表的查找简单顺序(shnx)查找 从左向右int search ( elementtype A， keytype x) int i; for(i=0;in;i+) if (Ai.key=x) return(i); return(-1);i=0i=0;i-) if (Ai.key=x) return(i); return(-1);分析：比较操作的次数i=n-1;i=0Ai.key=xi-;NY未找到找到了A01234in-1a1a2a3a4a5ai-1aniY返回-1返回iN共六十页119.2.1简单顺序(shnx)表的查找简单(jindn)顺序查找 从右向左+监视哨in

7、t search ( elementtype A， keytype x) int i; A0.key=x; while (Ai.key != x) i-; return(i);i=n-1;A0.key=x;Ai.key=xi-;NY未找到找到了A01234in-1a1a2a3a4a5ai-1aniY返回-1返回iNi=0共六十页129.2.1简单(jindn)顺序表的查找算法分析 各元素(yun s)的查找长度： 1,2,3,n (或n-1: 设置监视哨时)等概率情况下的平均查找长度： ASL=(1+2+n)/n=(n+1)/2 失败查找长度=n+1A01234in-1a1a2a3a4a5ai

8、-1ani共六十页139.2.2 有序表的查找(ch zho)二分查找问题描述:在递增有序（或递减有序，在此不妨采用递增）数组An中查找元素关键字为x的元素，若查找成功，则返回元素的下标，否则(fuz)返回-1。典型实例：英语词典中查单词。按照什么样的方式查找更好？简单顺序查找二分查找A01234in-1a1a2a3a4a5ai-1an共六十页149.2.2 有序表的查找(ch zho)二分查找查找方法描述：设查找区域的首尾下标分别为low和high（初值分别为0和n-1，取待查关键字x和区域的中间元素 (其下标mid=(low+high)/2) 的关键字进行比较，并根据比较的结果(ji gu

9、)分别作相应的处理：(1) x=Amid.key: 查找成功，返回mid的值。(2) xAmid.key: 说明待查元素只可能在右边区域 下标：mid+1high) 。因此，应在此区域继续查找。若表中存在所要查找的元素，则经上述若干次后，即可找到。问题是：如果不存在指定的元素，如何能判断出来？ A01234in-1a1a2a3a4a5ai-1anhighlowmid共六十页159.2.2 有序表的查找(ch zho)二分查找有序查找二分(r fn)查找（折半查找）例：在09号元素中查找元素值为47的元素2391530424753861000123456789lowhighmidhighlowm

10、idhighlowmidhighlowmid239153042475386100239153042475386100239153042475386100成功！问题：如果不存在所要搜索的元素，如何判断出来？共六十页169.2.2 有序表的查找(ch zho)二分查找算法(sun f)流程图二分查找算法如下:int bin_search(elementtype A ,int n, keytype x) int mid,low=0,high=n-1; /初始化查找区域 while ( low=high) mid=(low+high)/2; if (x=Amid.key) return mid; el

11、se if (xAmid.key) high=mid-1; else low=mid+1; return -1; /返回查找失败的标志XAmid.keyhigh=mid-1low=mid+1查找成功return midlowhigh) return -1; else mid=(low+high)/2; if (Amid.key= =x) return mid; else if(xAmid.key) return binsearch( A ,x,low,mid-1); else return binsearch( A ,x,mid+1,high); 递归算法(sun f)：参数？XAmid.ke

12、yhigh=mid-1low=mid+1查找成功return midlow=highmid=(low+high)/2low=0;high=n-1;Yreturn-1;N共六十页189.2.2 有序表的查找(ch zho)二分查找算法分析：借助二分查找判定(pndng)树来描述A01234in-1a1a2a3a4a5ai-1an5160231315109168017917079121417024746771211111214161717例：有序表A18 最坏查找长度=log2n+1共六十页199.2.2 有序表的查找(ch zho)二分查找练习：采用二分查找法查找018号元素(yun s)，其中

13、查找长度为5的元素是 哪些？ 则查找长度为5的元素有3，8，13，18。共六十页209.2 顺序(shnx)表的查找9.2.3 索引表的查找(ch zho) 一些数据表具有这样的特性：分块有序块间有序，块内无序。如下图所示：为便于查找， 可这样处理：为每一块设立一个块首指针，并标注对应块中的最大（小）关键字（可能是潜在的，不一定出现）将这两项内容合并为一个索引项各索引项合在一起构成索引表。9092959185888678707762656390807060索引项索引表lchild;XT-data.keyT=T-rchild ;找到5040473020354549709065556780100T

14、二叉排序树的查找 如何在二叉排序树中查找给定关键字的结点？ 以在下图所示树中分别查找45、55、66为例来说明。 由此可得到(d do)查找的判定过程。 判定过程类似于二分查找的判定过程。失败！共六十页269.3.1 二叉排序(pi x)树二分查找(ch zho)算法的流程图XP-data.keyP=P-lchild;P=P-rchild;查找成功return PP!=NULLP=TYreturn NULL;N查找的非递归算法： bnode *bstsearch(bnode *T， elementtype x) p=T; while ( p != NULL ) if ( p - data =

15、= x ) return p; if ( x data ) p = p - lchild; else p = p - rchild; return NULL; 共六十页279.3.1 二叉排序(pi x)树 查找(ch zho)的递归算法： bnode *bstsearch(bnode *T, elementtype x) if ( T = NULL ) return T; if (T - data = x ) return T; if (x data) return bstsearch(T-lchild,x); else return bstsearch(T-rchild,x); XP-da

16、ta.keyP=P-lchild;P=P-rchild;查找成功return PP!=NULLP=TYreturn NULL;N共六十页289.3.1 二叉排序(pi x)树二叉排序树的构造：从空树出发，依次(yc)插入各结点（作为叶子结点）。二叉排序树中插入结点：(1)若结点的值小于根结点的值， 则往左子树中插入 -通过递归调用插入算法来实现。(2)若结点的值大于等于根结点的值， 则往右子树中插入（递归调用）。按此方式递归调用若干次后， 可以搜索到一个空子树位置，即要插入的位置。共六十页299.3.1 二叉排序(pi x)树构造过程：依次(yc)将结点作为叶结点插入到二叉排序树中例：以下列数

17、据序列作为输入构造一棵二叉排序树。100，65，88，93，145，118，138，112，188，173，42，78，20, 197100654220789388118112138173197188145共六十页309.3.1 二叉排序(pi x)树二叉排序树的插入算法(sun f)逐个插入元素来实现构造，插入的元素作为叶子结点。 void insert(bnode *& T, bnode *s) / 将s所指结点插入到以T为根指针的二叉排序树中 if ( T = = NULL ) / T 为空时 T = = s; / 新结点作为根结点 else if ( s-data data ) ins

18、ert( T - lchild, s ); else insert( T - rchild, s ); 共六十页319.3.1 二叉排序(pi x)树二叉排序树的构造算法void creat(bnode *&T) / 接受(jishu)读入数据，从空树开始构造二叉排序树 T= =NULL; cinx; while (x!=结束符) s=new bnode; s - data=x; s - lchild=NULL; s - rchild=NULL; insert(T,s); cinx; 共六十页329.3.1 二叉排序(pi x)树二叉排序树构造分析： 以下列数据序列作为输入(shr)构造一棵二

19、叉排序树。 100，65，88，93，145，118，138，112，188，173，42，78，20，197平均查找长度： （1223447）/14 = 45/14100654220789388118112138173197188145共六十页339.3.1 二叉排序(pi x)树二叉排序树构造分析： 再看以下列数据序列作为输入(shr)构造一棵二叉排序树。20，42，65，78，88，93，100，112，118，138，145，173，188,197平均查找长度： （1214）/14 = 105/1420426578.由此而提出平衡二叉树共六十页349.3.1 二叉排序(pi x)树二叉

20、排序树删除结点：删除二叉排序树中的结点可分几种(j zhn)情况来实现 ：叶子结点 直接删除即可非叶子结点顶替法重新连接法100654220789388118112138173197188145删除叶子781006542209388118112138173197188145删除非叶子4220100654220789388118112138173197188145删除非叶子145173共六十页359.3 树表的查找(ch zho) 9.3.2 平衡二叉树 定义：平衡二叉树是一棵二叉排序树，或者为空， 或者满足以下(yxi)条件： 1)左右子树高度差的绝对值不大于1； 2)左右子树都是平衡二叉树。

21、 平衡因子： 左子树的高度减去右子树的高度，显然，在平衡二叉树中， 每个结点的平衡因子的值为-1，0或1。 共六十页369.3 树表的查找(ch zho) 平衡二叉树如何构造平衡二叉树（树） 在平衡的二叉排序树中插入一个结点，当出现不平衡时，根据不平衡情况分四种调整方法 假设最低不平衡结点为A，根据新插入结点与A的位置关系来命名(mng mng)调整方法： LL型：新插入结点在A的左孩子(L)的左子树(L)中； LR型：新插入结点在A的左孩子(L)的右子树(R)中； RL型：新插入结点在A的右孩子(R)的左子树(L)中； RR型：新插入结点在A的右孩子(R)的右子树(R)中。共六十页379.3

22、 树表的查找(ch zho) 平衡二叉树LL型（图示）：ABCLL型BCAABBLBRARh+2hLL型ABBLBRAR共六十页389.3 树表的查找(ch zho) 平衡二叉树LR型（图示）：ABCLR型CBAABBLCLARh+2hLR型ACCRARCCRBBRCL共六十页399.3 树表的查找(ch zho) 平衡二叉树RL型（图示）：ABCRL型CABABALCLBRhh+2RL型BCCRBRCCRAARCL共六十页409.3 树表的查找(ch zho) 平衡二叉树RR型（图示）：ABCRR型BACABBLBRARh+2hRR型ABBLARBR共六十页419.3 树表的查找(ch zh

23、o) 平衡二叉树构造练习：依次输入(shr)下列数据构造一棵平衡二叉树： 100，90，80，60，70，50，120，110，150，87。1009080LL型90801006070LR型9070100608050LL型9070100608050120110共六十页429.3 树表的查找 平衡(pnghng)二叉树构造(续1)练习：依次输入(shr)下列数据构造一棵平衡二叉树： 100，90，80，60，70，50，120，110，150，87。9070100608050120110RL型9070110608050100120150RR型7060501109080100120150共六十页4

24、39.3 树表的查找(ch zho) 平衡二叉树构造(续2)练习(linx)：依次输入下列数据构造一棵平衡二叉树： 100，90，80，60，70，50，120，110，150，87。706050110908010012015087RL型706050110908010012015087共六十页449.3 树表的查找(ch zho) 平衡二叉树思考：至少要用7个数作为输入序列，构造一棵平衡二叉树， 构造过程中同时包含4种调整方法。请给出这样的序列。在构造平衡二叉树的过程中， 若A的平衡因子变为-2，A的左孩子的平衡因子为0， 右孩子的平衡因子为1，则进行何种调整？ 求高度(god)为n的平衡二叉

25、树至少需要的结点个数。 一棵平衡二叉树中的叶子结点高度之差能不能超过2？共六十页459.3 树表的查找(ch zho)9.3.3 B-树定义：m阶B-树(m3)满足如下条件： 1) 每一个结点分支数m; 2) 根结点分支数2(要求此根结点不为叶子结点)； 3) 其余分支结点的分支数 m/2 ； 4) 所有叶子结点在同一层； 5) 每一个结点的结构如下： 满足： k1 kn 其中 表示Ai中的所有关键字，并且在结点中定义 keynum：记录结点中的关键字个数， keysm：存储(cn ch)结点中的各关键字， ptrsm+1：存储结点中各指针。Ai k1k2.Kn A0A1A2AnA0A1An共

26、六十页469.3.3 B-树3阶B-树：例如(lr)：10060150 20020 4070 90120 140180210 260B-树的查找：以上(yshng)图为例，分别查找40、150、210、230等，由此，可得到查找算法共六十页479.3.3 B-树B-树（插入）插入关键字插入方法：首先，插入到叶子(y zi)结点中，此时，若不溢出，则结束否则，分解结点（一分为二） 并且可能要执行多次10060150 20020 4070 90120 140180210 260180 190插入(ch r)190共六十页489.3.3 B-树插入(ch r)关键字10060150 20020 40

27、70 90120 140180 190210 260插入(ch r)160160 180 190160190150 180 2001006020 4070 90120 140210 260共六十页499.3.3 B-树插入(ch r)关键字插入(ch r)160160190150 180 2001006020 4070 90120 140210 260160190200100 1806020 4070 90120 140210 260150共六十页509.3.3 B-树删除关键字若删除的关键字不在叶子结点中，用其前驱或后继来替换删除叶子结点中的关键字 删除关键字后依然能满足B-树的条件，则结束 否则，若左右兄弟(xingd)中有多余的关键字，则调整一下，否则合三为一。10060150 20020 4070 90120 1401