第九章 查找 9.1 静态查找表 9.2 动态查找表 9.3 哈希表 E查找表(Search Table) 由同一类型的数据元素（或称记录） 构成的集合。 查找表是和线性表不同的数据结构 基本概念 E静态查找表(Static Search Table) E动态查找表(Dynamic Search Table) 不定义插入和删除操作的查找表。 定义了插入和删除操作的查找表。 是记录中某个数据项的值，用它可以 标识一个记录。 E关键字 (Key) 若某关键字可以唯一地标识一个记录 ，则称之为主关键字(Primary Key)。 若某关键字可以标识多个记录，则称 之为次关键字(Secondary Key) 。 E查找(Searching) 在查找表中找出满足指定条件的数据 元素（或称记录）。 例: 1.找出准考证号为05072639的考生记录 2.找出总分在600分以上的考生记录 若查找表中存在一个或多个满足条件 的记录，则称查找成功，此时可根据查 找要求，找出其中一个或全部记录。查 找结果为：给出所找到的记录的全部信 息，或记录地址； E查找的结果 若查找表中不存在满足条件的记录， 则称查找不成功，此时查找的结果可给 出一个空记录或空地址。 为了有效地进行查找操作，必须在查找 表的元素之间人为地附加一些关系，以便 按某种规则进行查找。也就是说，需要用 其他的数据结构来表示查找表，如线性表 、有序表、二叉树等。 F查找表在计算机中的表示 查找表需采用其他数据结构的存储结构 ，如顺序表、二叉链表等。 典型的关键字类型说明可以是： typedef float KeyType; / 实型 typedef int KeyType; / 整型 typedef char* KeyType; / 字符串型 F约定 数据元素类型定义为： typedef struct KeyType key; / 关键字域 / 其他域 ElemType; 对两个关键字的比较约定为如下的宏定义： /- 对数值型关键字 #define EQ(a, b) (a) = (b) #define LT(a, b) (a) data.key ) return SearchBST( T-lchild, key ); else retrun SearchBST( T-rchild, key ); /SearchBST 二叉排序树查找算法 3. 二叉排序树的插入运算 q 插入：在二叉排序树中插入键值 等于key的记录 若二叉排序树为空树，则插入元素 作为树根结点； 若根结点的键值等于key，则插入 失败； 若key小于根结点的键值，则插入 到根的左子树上；否则，插入到根 的右子树上； q 新插入的结点一定是个叶子结点 45 1253 337 100 90 24 61 78 60 /二叉排序树的插入算法 Status InsertBST(BiTree /键值为e.key的结点已经存在 s = new BiTnode; s-data = e; s-lchild = s-rchild = null; if (father=NULL) T = s; else if (e.keyfather-data.key) father-rchild = s; else father-lchild = s; /InsertBST p = T; father = NULL; while (p if (e.keyp-data.key) p = p-rchild; else p = p-lchild; /while （1）被删除的结点是叶子； （2）被删除的结点只有左子树或只有右子树; （3）被删除的结点既有左子树，也有右子树。 删除方法可分三种情况讨论： 二叉排序树中结点的删除操作只能在查找成 功的前提下进行，并且在二叉排序树上删除某 个结点之后，应使其保持二叉排序树的特性。 4二叉排序树的删除 Status DeleteBST(BiTree else if (EQ( key, T-data.key ) return Delete(T); else if (LT( key, T-data.key ) return DeleteBST( T-lchild, key ); else retrun DeleteBST( T-rchild, key ); /DeleteBST 算法9.7 Status Delete( BiTree p = p-lchild; free(q); else if (!p-lchild) / 左子树空则只需重接其右子树 q = p; p = p-rchild; free(q); else / 左右子树均不空，采用删除方案二 算法9.8 5.二叉排序树的查找性能分析 q 若查找成功，则走了一条从根结点到某结点的路径，若 查找失败，则走到一棵空的子树时为止。因此，最坏情 况下，其平均查找长度不会超过树的高度。 45 1253 337 100 90 24 61 78 55 ASL成功=(1+2*2+3*3+4*2+5*2+6*1)/11 =38/11 q 二叉排序树的形态 q关键字序列为(45,24,53,12,37,93)所构造的二叉排 序树如图(a)所示 q关键字序列为(12,24,37,45,53,93)所构造的二叉排序树 如图(b)所示 45 2453 1237 93 (a) 12 24 37 45 53 93 (b) 单枝树 6. 平衡二叉树概念 n 关键字序列为(12,93,24,53,37,45)所构造的二叉排序 树如图(c)所示 12 93 24 53 37 45 (c) 单枝树 q如果根据关键字的输入序列构 造的二叉树为单枝树，则其平 均查找长度与顺序查找相同 平衡二叉树(AVL树)定义 q定义：平衡二叉树或者是一棵空树，或者是具有下列性质的二 叉树：它的左子树和右子树都是平衡二叉树，且左、右子树的 深度之差的绝对值不超过1。 45 2453 1237 93 (a) 平衡二叉树 12 24 37 45 53 93 (b)非平衡二叉树 q平衡因子 定义二叉树中结点的平衡因子bf等于结点左子树的高度减 去右子树的高度 平衡二叉树中结点的平衡因子为0、1或-1。 q需解决的问题： q如何判断二叉树是否为平衡二叉树？ q如何将二叉排序树调整为平衡二叉树？ 9.3 哈希表(Hash) 9.3.1 哈希表的概念 q集合结构-查找表是一种非常灵便的数据结 构，关系松散，给查找带来不便。为此，需 在数据元素之间人为地加上一些关系，以便 按某种规则进行查找，即用某种数据结构来 表示查找表。 q在线性表、树表中，记录在结构中的相对位 置是随机的，查找时需进行一系列的比较， 查找的效率依赖于查找过程中所进行的比较 次数。 q理想情况是不经过任何比较，一次存取便能得 到所查记录，需在记录的存储位置和它的关键 字之间建立一个确定的对应关系。从关键字K 集合到地址集合的对应关系H称为哈希函数或 散列函数（Hashed Function） 。按这个思想 建立的表称为哈希表(hashed table) 。 qH(K)的值称为哈希地址或散列地址。 q哈希查找(Hashed search)是指在哈希表上进行 查找的过程，也称为散列法或杂凑法。 Hash法就是在关键字与记录在表中的 存储位置之间建立一个确定的函数关系 例如： Hash：关键字 地址 李刘王杨 关键字key （学号) 001 020 003 050 地址 12350 hash函数为：H(key)=key 若学号是2006形式，则hash函数可定义为： H(key)=key-2006000 假设有一批关键字序列18,75,60,43,54,90,46，给定哈希函数 H(key )=key % 13 存贮区的内存地址从0到15，则可以得到每个关键字的散列地址为： H(18) = 18%13 = 5 H(75) = 75%13 = 10 H(60) = 60%13 = 8 H(43) = 43%13 = 4 H(54) = 54%13 = 2 H(90) = 90%13 = 12 H(46) = 46%13 = 7 于是，根据散列地址，可以将上述7个关键字序列存贮到一个一维数 组HT（哈希表或散列表）中，具体表示为： HT 012345678910 11 12 54 43 1846 60 75 90 13 14 15 例2： 散列技术中的主要问题 : 表面上看，设置了散列函数后，只需作简单的函数计算 就可以实现元素的定位及查找操作，但事实上没有这么简单 ，因为关键字集合往往较大，而地址集合不能太大。所以概 括起来，主要有以下两个问题： (1)冲突 一般情况下，设计出的散列函数很难是单射的，即不 同的关键字对应到同一个存储位置，这样就造成了冲突( 碰撞)。此时，发生冲突的关键字互为同义词。 (2)散列函数的设计 设计一个简单、均匀、存储空间利用率高、冲突少的 散列函数是关键。 通常，哈希函数是从关键字集合K 到地址集合 L 的一个映象 H : KL; KLH H 的定义域H 的作用域 H 的值域 L 冲突 压缩映象 因此，由于哈希函数是一个压缩 映象，因此，在一般情况下，很容易 产生“冲突”现象，即： key1 key2， 而 H(key1) =H(key2)。 “冲突”有时也 称为“碰撞”，key1与key2称为同义词 。 很难找到一个不产生冲突的哈希函 数。一般情况下，只能选择恰当的哈希 函数，使冲突尽可能少地产生。 因此，在构造这种特殊的“查找表” 时 ，除了需要选择一个“好”(尽可能少产 生冲突)的哈希函数之外；还需要找到 一种“处理冲突” 的方法。 q关于冲突的处理方法 q开放定址法 q拉链法 q再哈希法 q公共溢出区法 q关于哈希函数的选择或构造 哈希函数应满足下列要求： 1)尽量简单 2)计算出的地址尽可能均匀分布在地址空间中，即经 散列函数映像到地址集合中任意一个地址的概率是 相等的， 对数字的关键字，有下列构造方法: 若是非数字关键字，则需先对其进行 数字化处理。 1. 直接定址法 3. 平方取中法 5. 除留余数法 4. 折叠法 6. 随机数法 2. 数字分析法 9.3.2 哈希函数的构造方法 哈希函数为关键字的线性函数 H(key) = key 或 H(key) = a key + b 1. 直接定址法 此方法仅适合于： 地址集合的大小 = 关键字集合的大小 此方法适合于： 数字组成的较长的且有规律的关键字， 如：身份证号码、手机号码等。 2. 数字分析法 若关键字集合中的每个关键字都是由 s 位数字组成 (d1, d2, , ds)，则可对全体关 键字进行分析，从中提取分布均匀的若干 位或它们的组合作为地址。 以关键字平方值的中间几位作为存储 地址。求关键字的平方值是为了“扩大差 别”，同时平方值的中间几位又能受到关 键字中各位的影响。 3. 平方取中法 此方法适合于: 关键字中的每一位都有某些数字重复 出现且关键字位数不多。 例：m=1000 (地址 0999) 可取平方数的中间三位作为哈希地址。 keykey2H(key) 10203104101209101 20304412252416252 30405924464025464 40506 1640739036739 1 0 2 0 3 1 0 2 0 3 3 0 6 0 9 2 0 4 0 6 1 0 2 0 3 1 0 4 1 0 1 2 0 9 平方取中法体现了哈希函数构造的基本思想: 尽可能使哈希地址与关键字的每一位都相关。 问题：若 m=500 (地址 0