第2章 常用数据结构及其运算3(查找和排序)

概述概述图图 查找查找 排序排序 2.62.82.7本章主要内容查找查找2.12.22.32.42.5 树与二叉树树与二叉树数组数组 栈与队栈与队 线性表线性表 2.7 查找查找 （ Searching） 静态查找表 （线性查找、对分查找、分块查找） 动态查找表 （二叉排序树） 哈希表查找表 本节主要内容：一、基本概念一、基本概念查找表：查找表： 用于查找的数据元素的集合称为查找表。用于查找的数据元素的集合称为查找表。查找表由同一类型的数据元素（或记录）构成。查找表由同一类型的数据元素（或记录）构成。2.7 查找查找 查找 表的表的 操作 :(1) 查询某个 “特定的 ”数据元素是否在查找表中 ;(2) 检索某个 “特定的 ”数据元素的各种属性 ;(3) 在查找表中插入一个数据元素 ;(4) 从查找表中删除某个数据元素 . 静态查找表 : 对查找表只作 (1)、 (2)操作； 动态查找表 ：可以对查找表作 (1)-(4)操作。关键字关键字 ：是数据元素（或记录）中的某个数据项的值，：是数据元素（或记录）中的某个数据项的值， 用以标识一个数据元素用以标识一个数据元素 (或记录或记录 ) 。例如例如 ：银行帐户中的帐号。：银行帐户中的帐号。 2.7 查找查找查找查找 ： 根据给定的值根据给定的值 ,在查找表中确定一个关键字等于在查找表中确定一个关键字等于给定值的记录或数据元素给定值的记录或数据元素 的过程。的过程。2.7 查找查找平均查找长度 (average search length， ASL)：衡量查找算法的优劣标准。对于一个含有 n个元素的查找表 ,查找成功时的平均查找长度可表示为： Pi 为查找第 i个元素的概率一般认为查找每个元素的概率相等， Pi=1/n. Ci 为查找第 i个元素所经历的比较次数。2.7 查找查找1、线性查找将查找表作为一个线性表，可以是顺序表，也可以是链将查找表作为一个线性表，可以是顺序表，也可以是链表，表， 依次用给定的值与查找表中数据元素的关键字值进依次用给定的值与查找表中数据元素的关键字值进行比较行比较 ，若某个记录的关键字值与给定值相等，则查找，若某个记录的关键字值与给定值相等，则查找成功，返回该记录的存储位置，反之，若直到最后一个成功，返回该记录的存储位置，反之，若直到最后一个记录，其关键字值与给定值均不相等，则查找失败，返记录，其关键字值与给定值均不相等，则查找失败，返回查找失败标志。回查找失败标志。二、静态查找表二、静态查找表2.7 查找查找/*线性查找：在表 r中查找关键字值为 k的元素 */int seqsearch(node rn+1, elemtype k) r0.key=k;int i=n; /*从表尾开始向前扫描 */while(ri.key!=k) i-;return i; 线性查找法最多查找次数为 n+1,最少查找次数为 1,平均查找次数为 (n+1)/2,时间复杂度为 O(n)。 2.7 查找查找 如果查找表中各记录是按关键字 有序排列 的 ,可以先用表的 中间位置 上记录的关键字与给定值 K比较 ,若相等 ,则查找成功 ;否则 ,根据比较的结果确定下一步在表的 前半部 或 后半部 中继续查找 。2、对分查找1 2 3mid=4key例 : 在顺序表中查找 key = 55 的数组元素。mid = (low+high)/213 17 42 46 55 70 944 5 6 7 8high=8low=55mid=6low=14250时约为： log2(n+1)-1,时间复杂度为 O(log2n)。2.7 查找查找/对分法查找Int binsearch(struct node rn+1 , element k) int low=1, high=n;while (lowk) high=mid-1; /*在左子区间中查找 */else low=mid+1; /*在右子区间中查找 */return 0; /*查找失败 */又称 索引顺序查找 。性能介于顺序查找和对分查找之间。适用于顺序表，也适用于线性链表。分块查找要求查找表 “分块有序 ”，即把查找表分成若干个块 , 每个 块中关键字不一定有序 ，但是前一个块中的最大关键字必须小于后一块中最小关键字。3、分块查找2.7 查找查找2.7 查找查找2.7 查找查找三、动态查找表三、动态查找表 对二叉排序树进行中序遍历可以得到一个关键字对二叉排序树进行中序遍历可以得到一个关键字有序序列。有序序列。 二叉排序树本身可以看作是一个有序结构，插入和删除操作不需要移动元素。122250300110 20099105 230216动态查找表的特点： 表本身是在查找的过程中动态生成的 。 以上讲的静态查找表的三种查找中，对分查找效率最高，根本原因是查找表的数据元素 有序排列， 但是需要 顺序存储 ，对于动态查找表来讲这种结构意味着要频繁地移动数据元素，为了解决这个问题，我们想到了 二叉排序树（二叉查找树） 。2.7 查找查找二叉排序树的建立过程就是动态查找二叉排序树的建立过程就是动态查找 。 查找：查找： 用给定值用给定值 k与根结点关键字值比与根结点关键字值比较，如果较，如果 k小于根结点的值，则要小于根结点的值，则要找的结点只可能在左子树中，所以找的结点只可能在左子树中，所以继续在左子树中查找，否则将继续继续在左子树中查找，否则将继续在右子树中查找，依此方法，查找在右子树中查找，依此方法，查找下去，至直查找成功或查找失败为下去，至直查找成功或查找失败为止。止。122250300110 20099105 230216查找步骤： 122250300110 20099105 2302161. 若根结点的关键字值等于查找的关键字，成功。2. 否则，若小于根结点的关键字值，查其左子树。3. 若大于根结点的关键字值，查其右子树。4. 在左右子树上做以上操作。2.7 查找查找1. 哈希表哈希表前面介绍的静态查找和动态查找的特点是：为了从查前面介绍的静态查找和动态查找的特点是：为了从查找表中找到关键字值等于某个给定值的记录，都要经过一找表中找到关键字值等于某个给定值的记录，都要经过一系列的系列的 关键字比较关键字比较 ，以确定待查记录的存储位置或查找失，以确定待查记录的存储位置或查找失败，查找所需时间总是与比较次数有关。败，查找所需时间总是与比较次数有关。如果将记录的如果将记录的 存储位置存储位置 与它的与它的 关键字关键字 之间建立一种确之间建立一种确定的函数关系定的函数关系 H， 即：即： 存储位置存储位置 H(关键字值关键字值 )在查找时，只需要根据对应关系计算出给定的关键字值在查找时，只需要根据对应关系计算出给定的关键字值key对应的值对应的值 H(key)， 就可以得到记录的存储位置。这就就可以得到记录的存储位置。这就是本节将要介绍的哈希表查找方法的基本思想。是本节将要介绍的哈希表查找方法的基本思想。2.7 查找查找四、哈希表及其查找四、哈希表及其查找n 哈希函数哈希函数 我们将记录的关键字值与记录的存储我们将记录的关键字值与记录的存储位置对应起来的关系位置对应起来的关系 H称为哈希函数，称为哈希函数， H(k)的结的结果称为哈希地址。果称为哈希地址。 哈希表哈希表 是根据哈希函数建立的查找表。是根据哈希函数建立的查找表。哈希表哈希表 即是一种存储形式，又是一种查找方法即是一种存储形式，又是一种查找方法，通常将这种查找方法称为，通常将这种查找方法称为 哈希查找哈希查找 。四、哈希表及其查找四、哈希表及其查找2.7 查找查找n 使用哈希表方法进行查找不必进行多次关键字的比较使用哈希表方法进行查找不必进行多次关键字的比较 ,查找速度比较快。查找速度比较快。 但问题是会产生但问题是会产生 冲突冲突 。示例：有一组表项，其关键字分别是示例：有一组表项，其关键字分别是12361, 07251, 03309, 30976 四、哈希表及其查找2.7 查找查找采用的哈希函数是采用的哈希函数是h(x) = x % 73 + 13420则有：则有：hash(12361) = hash(07250) = hash(03309) = hash(30976) = 13444。 对不同的关键字对不同的关键字 , 通过哈希函数的计算通过哈希函数的计算 , 得到了同一哈得到了同一哈希地址。这种现象称为希地址。这种现象称为 冲突冲突 。 由于关键字集合比地址集合大得多由于关键字集合比地址集合大得多 , 冲突很难避免。所冲突很难避免。所以对于哈希方法以对于哈希方法 , 需要讨论以下两个问题：需要讨论以下两个问题： 四、哈希表及其查找四、哈希表及其查找2.7 查找查找u哈希函数的构造哈希函数的构造u解决冲突解决冲突哈希函数的哈希函数的 定义域定义域 必须包括需要存储的全部关键字必须包括需要存储的全部关键字 , 如果如果 哈希表允许有哈希表允许有 m 个地址时个地址时 , 其其 值域值域 必须在必须在 0 到到 m-1 之间之间。 2.哈希函数哈希函数的构造的构造2.7 查找查找 哈希函数应是简单的，能在较短的时间内计算出结果哈希函数应是简单的，能在较短的时间内计算出结果。三点要求：三点要求：哈希函数计算出来的地址应能哈希函数计算出来的地址应能 均匀分布均匀分布 在整个地址空间中在整个地址空间中 : 若若 key 是从关键字集合中随机抽取的一个关键字是从关键字集合中随机抽取的一个关键字 , 哈希哈希函数应能以函数应能以 等概率等概率 取取 0 到到 m-1 中的每一个值。中的每一个值。四、哈希表及其查找四、哈希表及其查找（ 1）直接定址法）直接定址法取关键字的某个线性变换作为哈希函数：取关键字的某个线性变换作为哈希函数：H(key) a* key+b （ a, b为常数）为常数）这类哈希函数是一对一的映射，一般不会产生冲突。这类哈希函数是一对一的映射，一般不会产生冲突。但是，它要求哈希地址空间的大小与关键字集合的大小但是，它要求哈希地址空间的大小与关键字集合的大小相同。相同。四、哈希表及其查找2.7 查找查找例：有一组关键字如下：例：有一组关键字如下： 942148, 941269, 940527, 941630, 941805, 941558, 942047, 940001 哈希函数为哈希函数为H (key) = key - 940000 H(942148) = 2148 H (941269) = 1269H (940527) = 527 H (941630) = 1630H (941805) = 1805 H (941558) = 1558H (942047) = 2047 H (940001) = 1可以按计算出的地址存放记录。可以按计算出的地址存放记录。2.7 查找查找四、哈希表及其查找（ 2）除留余数法）除留余数法设哈希表中允许地址数为设哈希表中允许地址数为 m, 取一个取一个 不大于不大于 m的最最大的最最大素数素数 p 作为除数作为除数 , 利用以下函数把关键字转换成哈希地址利用以下函数把关键字转换成哈希地址：H ( key ) = key % p p m2.7 查找查找示例示例 : 有一个关键字有一个关键字 key = 962148, 哈希表大小哈希表大小 m = 25 。取取 p= 23， 则哈希地址为：则哈希地址为：h ( 962148 ) = 962148 % 23 = 12 。(3)数字分析法数字分析法 (略略 )(4)平方取中法平方取中法 (略略 )(5)折叠法折叠法 (略略 ) 四、哈希表及其查找3.哈希冲突解决方法哈希冲突解决方法(1) 开放定地址法开放定地址法哈希地址计算式：哈希地址计算式： Hi=(H(key)+di)%m i=1,2,k(k=m-1)其中，增量序列其中，增量序列 di的取值方法有三种：的取值方法有三种：n di=1,2,3,m-1 (线性探测再散列 ) n di=12,-12,22,-22,k 2,-k2 (k=m/2)(二次探测再散列 )n di=随机数序列随机数序列 (随机探测再散列 )2.7 查找查找四、哈希表及其查找开放定地址法线性探测再散列开放定地址法线性探测再散列假设给出一组记录，它们的关键字为：假设给出一组记录，它们的关键字为： Burke, Ekers, Broad, Blum, Attlee, Alton, Hecht, Ederly。 采用的哈希采用的哈希函数是：取其第一个字母在字母表中的位置。函数是：取其第一个字母在字母表中的位置。 Hash (x) = ord (x) - ord (A) /ord ( ) 是求字符内码的函数是求字符内码的函数n 可得可得 Hash (Burke) = 1 Hash (Ekers) = 4Hash (Broad) = 1 Hash (Blum) = 1Hash (Attlee) = 0 Hash (Hecht) = 7Hash (Alton) = 0 Hash (Ederly) = 4n 设哈希表设哈希表 HT26, m = 26。 采用采用 线性探测法线性探测法 处理冲突处理冲突 , 则结果如图所示则结果如图所示。四、哈希表及其查找2.7 查找查找0 1 2 3 4Attlee Burke Broad Blum EkersAlton Ederly Hecht 5 6 7 8 9 (1) (1) (2) (3) (1)(6) (3) (1)Hash (Burke) = 1 Hash (Ekers) = 4Hash (Broad) = 1 Hash (Blum) = 1Hash (Attlee) = 0 Hash (Hecht) = 7Hash (Alton) = 0 Hash (Ederly) = 4四、哈希表及其查找2.7 查找查找n 示例：给出一组记录，关键字为：示例：给出一组记录，关键字为： Burke, Ekers, Broad, Blum, Attlee, Alton, Hecht, Ederly 。n 哈希函数为：哈希函数为：Hash (x) ord (x) ord (A)。n 用它计算可得：用它计算可得：Hash (Burke) = 1 Hash (Ekers) = 4Hash (Broad) = 1 Hash (Blum) = 1Hash (Attlee) = 0 Hash (Hecht)