数据结构-第九章

1、数 据 结 构第九章 查找引言查找表：由同一类型的数据元素构成的集合。对查找表的操作:查询某个“特定的”数据元素是否在查找表中；检索某个“特定的”数据元素的各种属性；在查找表中插入一个数据元素；从查找表中删去某个数据元素引言静态查找表：仅作查询和检索操作的查找表。动态查找表：在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素,此类表为动态查找表。引言关键字：是数据元素（或记录）中某个数据项的值，用以标识一个数据元素（或记录）。若此关键字可以识别唯一的一个记录，则称之谓“主关键字”。如：学号，身份证。若此关键字能识别若干记录，则称之谓“次关键字”。如：姓名。引言

2、查找： 根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或（记录）。 若查找表中存在这样一个记录，则称“查找成功”，查找结果：给出整个记录的信息，或指示该记录在查找表中的位置；否则称“查找不成功”，查找结果：给出“空记录”或“空指针”。9.1 静态查找表查找的方法取决于查找表的结构。由于查找表中的数据元素之间不存在明显的组织规律，因此不便于查找。为了提高查找的效率，需要在查找表中的元素之间人为地附加某种确定的关系，换句话说，用另外一种结构来表示查找表。9.1 静态查找表ADT StaticSearchTable 数据对象D:是具有相同特性的数据元素的集 合。每个数据元素含有类型

3、相同 的关键字，可唯一标识数据元素。数据关系R：数据元素同属一个集合。基本操作 P： Create(&ST, n); Destroy(&ST); Search(ST, key); Traverse(ST, Visit(); ADT StaticSearchTable9.1.1 顺序表的查找以顺序表或线性表表示静态查找表，则查找可以用顺序的方式进行。我们以线性表的顺序存储为例来学习顺序表的查找。 typedef struct ElemType *elem; int length; SSTable;9.1.1 顺序表的查找在线性表中查找一个元素是非常容易的。为了程序编写简单，我们采用从后往前查找的

4、方式，并且在第一个位置上设置一个“监视哨”。10 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92找6464监视哨5432比较次数=5比较次数：查找第n个元素： 1查找第n-1个元素：2查找第i个元素： n+1-i 查找第1个元素： n查找失败： n+1查找过程：从表的一端开始逐个进行记录的关键字和给定值的比较。例如：9.1.1 顺序表的查找int Search_Seq(SSTable ST, KeyType key) ST.elem0.key = key; for (i=ST.length; ST.elemi.key!=key;

5、-i); return i;9.1.1 顺序表的查找查找算法的平均查找长度ASL( Average Search Length)： 为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值。 9.1.1 顺序表的查找通过分析，我们可以得到顺序表查找成功：9.1.2 有序表的查找顺序表的查找算法简单，但平均查找长度较大，不适用于表长较大的查找表。若以有序表表示静态查找表，则查找过程可以基于“折半”进行。9.1.2 有序表的查找折半查找查找过程：每次将待查记录所在区间缩小一半。适用条件：采用顺序存储结构的有序表。ST.elemST.length例如: key = 64 的查找过程如下lo

6、whighmidlow mid high midlow 指示查找区间的下界;high 指示查找区间的上界;mid = (low+high)/2。ST.elemST.length例如: key = 70 的查找过程如下lowhighmidlow mid high midlow 指示查找区间的下界;high 指示查找区间的上界;mid = (low+high)/2。lowmidhighint Search_Bin ( SSTable ST, KeyType kval ) low = 1; high = ST.length; while (low = high) mid = (low + high)

7、 / 2; if （key = ST.elemmid.key ) return mid; else if ( key ST.elemmid.key) ) high = mid - 1; else low = mid + 1; return 0;先看一个具体的情况，假设查找表：n=11分析折半查找的平均查找长度6391425781011判定树12233334444 查找表: A B C D E F G H I J K log 2 n +1ASL = 33/11最大次数9.1.4 索引顺序表的查找索引顺序表：在建立顺序表的同时，建立一个索引项，包括两项：关键字项（每块中的最大值）和指针项（每块的起

8、始地址）。索引表按关键字有序。表则为分块有序（每块中的元素都要求大于前一块的元素）。01234567891011121317821191431332225405261784621 040 578 10索引顺序表 = 索引 + 顺序表顺序表索引表9.1.4 索引顺序表的查找1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1822 12 13 8 9 20 33 42 44 38 24 48 60 58 74 57 86 5322 48 861 7 13索引表查38例如9.1.4 索引顺序表的查找9.2 动态查找表动态查找表的特点:表结构本身是在查找过程中动态生

9、成。若表中存在其关键字等于给定值key的记录,表明查找成功；否则插入关键字等于key的记录。ADT见P2279.2.1 二叉排序树和二叉平衡树二叉排序树：二叉排序树或者是一棵空树；或者是具有如下特性的二叉树；若它的左子树不空，则左子树上所有结点的值均小于根结点的值；若它的右子树不空，则右子树上所有结点的值均大于根结点的值；它的左、右子树也都分别是二叉排序树。9.2.1 二叉排序树和二叉平衡树503080209010854035252388669.2.1 二叉排序树和二叉平衡树二叉排序树的查找算法若二叉排序树为空，则查找不成功；否则1）若给定值等于根结点的关键字，则查找成功；2）若给定值小于根结

10、点的关键字，则继续在左子树上进行查找；3）若给定值大于根结点的关键字，则继续在右子树上进行查找。注意：因为是动态查找表，则在查找不成的情况下，需要插入该结点。在二叉排序树中查找关键字值等于50,35,90,9550308020908540358832505050304035505080909.2.1 二叉排序树和二叉平衡树二叉排序树的插入算法：根据动态查找表的定义，“插入”操作在查找不成功时才进行；若二叉排序树为空树，则新插入的结点为新的根结点；否则，新插入的结点必为一个新的叶子结点，其插入位置由查找过程得到。9.2.1 二叉排序树和二叉平衡树例如：45，24，53，45，12，37，9345

11、24531237939.2.1 二叉排序树和二叉平衡树二叉排序树查找性能的分析 对于每一棵特定的二叉排序树，均可按照平均查找长度的定义来求它的 ASL 值，显然，由值相同的n个关键字，构造所得的不同形态的各棵二叉排序树的平均查找长度的值不同。由关键字序列 3，1，2，5，4构造而得的二叉排序树由关键字序列 1，2，3，4，5构造而得的二叉排序树，例如：2134535412ASL =（1+2+3+4+5）/ 5 = 3ASL =（1+2+3+2+3）/ 5 = 2.29.2.1 二叉排序树和二叉平衡树平衡二叉树AVL：二叉平衡树是二叉排序树的另一种形式，其特点为：树中每个结点的左、右子树深度之差

12、的绝对值不大于1 。平衡因子BF：某结点的左子树的深度减它的右子树的深度。9.2.1 二叉排序树和二叉平衡树5482548219.2.1 二叉排序树和二叉平衡树平衡二叉树AVL性质：AVL树的深度与logn同数量级，它的平均查找长度ASL也与logn同数量级。9.2.1 二叉排序树和二叉平衡树构建AVL树，需要进行旋转。例如：（13, 24, 37, 90, 53)练习：（5, 4, 3, 8, 19,1,2，25，23）9.2.2 B-树和B+树本节介绍两种特殊的平衡树，只需要了解树的结构，特点。9.2.2 B-树和B+树B -树：一种平衡的多路查找树 一棵m阶的B-树或为空树，或为满足下列

13、特性的m叉树：树中每个节点至多有m棵子树。若根结点不是叶子结点，则至少有两棵子树。除根结点之外的所有非终端结点至少有m/2 棵子树所有的非终端结点中包含下列信息数据(n,A0,K1,A1,K2,A2,Kn,An)。其中n为关键字个数，Ai-1指向子树的指针，且Ai-1指向的子树中所有关键字均小于Ki。Ki(i=1,n)为关键字，且KiKi+1,(i=1,n-1)所有的叶子结点都出现在同一层次上，并且不带信息（空指针）。135118243781111271393475364199t9.2.2 B-树和B+树练习：一棵m阶B-树每个结点最多有（ ）棵子树，（ ）个关键字,最少有（ ）棵子树( )个

14、关键字。B+树 B+树是B-树的变型，m阶的B+树和m阶的B-树的区别是：关键字个数和子树个数一样多所有叶子结点中包含全部关键字信息及指向含这些关键字记录的指针，且叶子节点本身依关键字的大小自小而大顺序链接。所有非终端结点可看成索引，节点中仅含有其子树中的最大（或最小）关键字。9.2.2 B-树和B+树59 97aroot15 44 59b72 97e10 15c21 37 44d51 59f63 72g85 91 97hsqt9.3 哈希表以上两节讨论的表示查找表的各种结构的共同特点：记录在表中的位置和它的关键字之间不存在一个确定的关系。查找的过程为给定值依次和关键字集合中各个关键字进行比较

15、。查找的效率取决于和给定值进行比较的关键字个数。9.3 哈希表 哈希查找：基本思想：在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，不经过比较，一次存取就能得到所查元素的查找方法。9.3 哈希表哈希函数：在记录的关键字与记录的存储地址之间建立的一种对应关系。哈希函数是一种映象，是从关键字空间到存储地址空间的一种映象。可写成，addr(ai)=H(ki)其中：ai是表中的一个元素 addr(ai)是ai的存储地址 ki是ai的关键字9.3 哈希表例如：建立一张全国30个地区的各民族人口统计表。Key BeijingTianjinHebeiShanxiShanghaif1(key)0

16、220081919f2(key)0904172828f3(key)04260213239.3 哈希表哈希函数只是一种映象，所以哈希函数的设定很灵活，只要使任何关键字的哈希函数值都落在表长允许的范围之内即可。冲突：key1key2，但H(key1)=H(key2)的现象9.3 哈希表哈希函数的构造方法:直接定址法数字分析法平方取中法折叠法除留余数法随机数法9.3 哈希表直接定址法：哈希函数为关键字的线性函数 H(key) = key 或者 H(key) = a *key + b此法仅适合于：地址集合的大小 = = 关键字集合的大小例如：按照学号存放记录。 数字分析法假设关键字集合中的每个关键字都

17、是由 s 位数字组成 (u1, u2, , us)，分析关键字集中的全体， 并从中提取分布均匀的若干位或它们的组合作为地址。此法适于能预先估计出全体关键字的每一位上各种数字出现的频度。例 有80个记录，关键字为8位十进制数，哈希地址为2位十进制数8 1 3 4 6 5 3 28 1 3 7 2 2 4 28 1 3 8 7 4 2 28 1 3 0 1 3 6 78 1 3 2 2 8 1 7 8 1 3 3 8 9 6 78 1 3 6 8 5 3 78 1 4 1 9 3 5 5. 分析： 只取8 只取1 只取3、4 只取2、7、5 数字分布近乎随机所以：取任意两位或两位 与另两位的叠加作

18、哈希地址 以关键字的平方值的中间几位作为存储地址。求“关键字的平方值” 的目的是“扩大差别” ，同时平方值的中间各位又能受到整个关键字中各位的影响。此方法适合于: 关键字中的每一位都有某些数字重复出现频度很高的现象。平方取中法 除留余数法 设定哈希函数为: H(key) = key MOD p ( pm ) 其中， m为表长 例如：（28，35，63，77，105） p=3632835012349.3 哈希表“处理冲突” 的实际含义是：为产生冲突的地址寻找下一个哈希地址。开放定址法再哈希法链地址法为产生冲突的地址 H(key) 求得一个地址序列： H0, H1, H2, , Hs 1sm-1Hi = ( H(key) + di ) MOD m 其中： i=1, 2, , sH(key)为哈希函数;m为哈希表长;di为增量序列,有下列三种取法:开放定址法对增量 di 的三种取法：1)线性探测再散列 di = 1,2,3,m-1 2) 二次探测再散列 di = 12, -12, 22, -22, ,3) 随机探测再散列 di 是一组伪随机数列例如: 给定关键字集合构造哈希表 19, 01, 23, 14, 55, 68, 11, 82, 36 设定哈希函数 H(key) = key MOD 11 ( 表长=11 )1901231455681901231468若采用线性探测再