数据结构:第九章 - 查找 624次阅读 数据结构 2022-08-02 目录 [TOC] ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/SplitLine/SplitLine-01.gif) # 一、查找 ## (一)平均查找长度(ASL) 在查找过程中,一次查找的长度是指需要比较的关键字次数,而平均查找长度则是所有查找过程中进行关键字比较次数的平均值。 对于具有 n 个数据元素的查找表,查找成功的平均查找长度的计算公式为: ```latex ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ASL=\sum_{i= 1}^{n}P_iC_i ``` ```latex ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~= \frac{1}{n}\sum_{i = 1}^{n}P_iC_i ``` * n:查找表中记录的个数。 * Pi :第 i 个数据元素被查找的概率,所有元素被查找的概率的和为 1。 在考研中 Pi常取 $$\frac{1}{n}$$。 * Ci :找到第 i 个数据元素所需要进行比较的次数,即查找长度。 > 若表中有 n 个数据元素,查找第一个元素时需要比较 n 次;查找最后一个元素时需要比较 1 次, > > 所以 Ci = n-i+1; > > 查找算法 ASL 应该为 查找成功时的 ASL + 查找失败时的 ASL。 ## (二)查找表种类划分 ### 1、静态查找表 查找表的操作无需动态地修改查找表,如 顺序查找、折半查找、分块查找、散列查找等。 ### 2、动态查找表 需要动态地插入或删除的查找表,如 二叉排序树、二叉平衡树、B 树、散列查找等。 ## (三)按存储结构划分 * 线性结构:顺序查找、折半查找、分块查找。 * 树形结构:二叉排序树、二叉平衡树、B 树。 * 散列结构:散列表。 ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/SplitLine/SplitLine-01.gif) # 二、静态表查找算法 ## (一)顺序查找法 顺序查找方法适应于线性表,用顾序表或者链表来表示的线性表它都适应。 ### 1、基本思路 * 从表的一端开始,顺序扫描线性表,一次将扫描到的关键字和给定值 k 比较 * 若当前扫描的关键字与 k 相等,则查找成功。 * 若扫描结束后,仍未发现关键字等于 k 的记录,则查找失败。 * 对于顺序表,通过数组下标递增来顺序扫描数组中各元素。 * 对于链表,通过表结点指针(p),反复执行 p=p->next;来扫描表中各元素。 ### 2、Code ```c /*顺序表*/ int Search(int arr[],int n,int key) { int i; for(i=0; inext; while (p != NULL) { if (p->data == key) return p; p = p->next; } return NULL; } ``` ## (二)折半查找法 - 二分查找 折半查找法要求线性表有序,即表中关键字有序(按递增或递减)。 折半查找是基于随机存储方式的算法,必须用顺序表而不能用链表。 ### 1、基本思路 设 arr[ low , …… , high ]是当前查找区间,待查值为 k: 1. 确定该区间中间位置:mid = ( low + high ) / 2 。 > 一般情况向下取整。 > 2. 将 k 与 arr[ mid ] 比较: 1. 若相等,则查找成功,并返回该位置。 2. 若 arr[ mid ] > k ,则前往左子表 arr[ low , …… , mid-1 ] 进行查找。 3. 若 arr[ mid ] < k ,则前往右子表 arr[ mid+1 , …… , high ] 进行查找。 3. 递归处理新区间,直到子区间长度小于 1 时,查找过程结束。 ### 2、Code ```c int BSearch(int arr[],int low, int high, int key) { while(low <= high)//当子表长度 <= 1时进行循环 { int mid = (low + high)/2;//取当前表中间元素 if(arr[mid] == key)//找到后返回元素的位置 return mid; else if(arr[mid] > key)//未找到,前往左子表查找 high = mid - 1; else//未找到,前往右子表查找 low = mid + 1; } return -1;//查找失败,返回-1 } ``` ### 3、折半查找判定树的建立 折半查找的运行过程可以用二叉树来描述,这棵树通常称为“判定树”,可认为是一棵二叉排序树。 对于具有 n 个结点(查找表中含有 n 个关键字)的判定树,它的层次数至多为:log2n +1(如果 log2n 结果不是整数,则向下取整)。 同时,在查找表中各个关键字被查找概率相同的情况下,折半查找的平均查找长度为:ASL = log2(n +1) - 1。 #### (1)查找排序树 * 折半查找判定树是一颗二叉判定树,也是一棵二叉排序(查找)树。 即,每个结点的值均大于其左子树上所有结点的值,小于其右子树上所有结点的值。 * 元素结点都为非终端结点, 叶子结点(外结点、方框)都表示为查找不成功的位置。 > 即,折半查找判定树中的结点都是查找成功的情况; > > 而将每个结点的空指针指向的一个实际上并不存在的结点,称为外结点,所有外结点即是查找不成功的情况。 > > 如果有序表的长度为 n,则外结点一定有 n+1 个。 > > 在手工求解时,当所有元素都已经落到既定位置后,再给所有左、右为空的结点加上外结点(用方框来表示),代表查找不成功的位置。 > * 在折半查找判定树中, * 查找某结点的比较次数:某结点所在的层数。 * 查找不成功时的比较次数:外结点(方框)所在的层数。 > 或者换一种方式说: > > 成功的折半查找过程,恰好是走了一条从根到被查记录的路径,比较次数恰为该记录在树中的层数。 > > 若查找失败,则其比较过程是一条根到某个外部结点的路径,比较次数是该路径上内部结点的总数。 > #### (2)长度为 n 的折半查找判定树的构造方法 * 当 n = 0 时,折半查找判定树为空。 * 当 n>0 时: * 折半查找判定树的根结点是有序表中序号为 mid = ( n + 1 ) / 2 的记录。 > 一般情况下是向下取整 > * 根结点的左子树是与有序表 r[1] ~ r[mid-1]相对应的折半查找判定树。 * 根结点的右子树是与有序表 r[mid+1] ~ r[n]相对应的折半查找判定树。 #### (3)比较次数 * 从根节点到待查找元素所经过的结点数,其比较次数最多的情况即为一直走到外结点(失败的情况)。 ## (三)分块查找 又称索引顺序查找。 ### 1、数据结构 * 把线性表分成若子表,子表中的元素存储顺序是任意的,但子表与间必须按照关键字大小有序排列。 * 前一子表的最大关键字要小于后一子表中的最小关键字。 * 顺序表需额外建立一个索引表,每个子表对应一个索引,索引中包含中两部分内容:键值分量、链值分量 * 键值分量:存放对应块的最大关键字。 * 链值分量:存放指向本块第一个关键字和最后一个关键字的指针。 > 此处指针可是元素在数组的下标或地址,或帮助找到此元素的信息。 > ```c typedef struct { int key;//假设表内为int元素,键值分量 int low, high;//记录某块中第一个和最后一个元素的位置 }indexElem; indexElem index[maxsize];//定义索引表 int keys[15];//索引元素数组 ``` ### 2、算法执行过程 所有前期准备工作完成后,开始在此基础上进行分块查找。分块查找的过程分为两步进行: 1. 确定要查找的关键字可能存在的具体块(子表),即二分查找。 2. 在具体的块中进行顺序查找。 ## (四)性能比较 对于同一个表, * 如果找的是表中的第一个元素,则用顺序查找方法一定比折半查找快。 * 如果找的是表中的最后一个元素,则用顺序查找方法一定比折半查找方法慢。 ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/SplitLine/SplitLine-01.gif) # 三、二叉排序树、平衡二叉树 ## (一)二叉排序树 - BST ### 1、定义 又称,二叉查找树。 二叉排序树要么是空二叉树,要么具有如下特点: * 结点值大于左子树所有结点的值,小于右子树所有结点的值。 * 左右子树也要求都是二叉排序树。 * 层内一定是从小到大排列的(或相反)。 通过输出二叉排序树的中序遍历序列,可得到一个非递增(非递减)的有序序列。 > * 一般情况下,左小右大。 > * 非递减(非递增)序列:小到大或者允许中间有相等的情形。 ### 2、存储结构 ```c typedef struct BTNode { int key;//此处将data改成key,代表关键字 struct BTNode *lchild; struct BTNode *rchild; }BTNode; ``` ### 3、基本算法 #### (1)查找关键字 算法过程: 1. 先将待查关键字和根结点中的关键字比较,若相等则查找成功,返回关键字所在结点的指针。 1. 若小于,则查找左子树。 2. 若大于,则查找右子树。 2. 若来到当前树的子树根,重复上述过程。 3. 若来到了结点的空指针域,则查找失败,返回 NULL。 Code: ```c BTNode* BSTSearch(BTNode* bt,int key) { if(bt==NULL) return NULL;//来到了结点的空指针域,查找失败,返回NULL else { if(bt->key==key) return bt;//关键字相等,查找成功,返回关键字结点指针 else if(keykey)//进入左子树查找 return BSTSearch(bt->lchild,key);//① else//进入右子树查找 return BSTSearch(bt->rchild,key);//② } } //①②处return的作用是逐层将内部函数的返回值传给上层,最终由最外层函数返回,来告诉用户是否执行成功。 ``` #### (2)插入关键字 算法过程: 1. 查找插入位置(查找失败的位置,即为插入位置)。 2. 若待插入关键字已存在,则插入不成功,返回 0。 3. 若待插入关键字不存在,则插入,返回 1。 > 新插入的关键字均存储在新的叶子结点。 Code: ```c int BSTInsert(BTNode *&bt,int key)//指针bt会改变,所以用引用型 { if(bt==NULL)//当前为空指针时说明找到插入位置,创建结点并插入 { bt=(BTNode*)malloc(sizeof(BTNode));//创建新结点 bt->lchild=bt->rchild=NULL; bt->key=key;//将待插入关键字存入新结点内,插入成功,返回1 return 1; } else//若结点不空,则查找插入位置 { if(key==bt->key)//关键字已存在树中,插入失败,返回0 return 0; else if(keykey)//进入下层子树查找 return BSTInsert(bt->lchild,key); else return BSTInsert(bt->rchild,key); } } ``` #### (3)建立二叉排序树 无序序列可通过此操作,构造出一棵二叉排序树,从而变成有序序列。 算法过程: * 建立一棵空树,将关键字逐个插入到空树中,即可得到一棵二叉排序树。 > 按下标顺序一个一个插入树中。 > Code: ```c void CreateBST(BTNode *&bt,int key[],int n) { int i; bt=NULL;//将树情况 for(i=0;i 同理,可沿着右子树一直向左走,找到最左结点 > 2. 将 p 中的关键字用 r 中的关键字代替。 3. 判断 r 的位置: 1. 若为叶子结点,按照 ① 方法删除。 2. 若为非叶子结点,按照 ② 方法删除。 > 此时 r 不可能有双子树 > ## (二)平衡二叉树 - AVL Tree ### 1、概念 * 平衡二叉树:又称 AVL 树,是一种特殊的二叉排序树。 * 以树中所有结点为根的左右子树高度之差的绝对值不超过 1。 * 每棵子树都是平衡二叉树。 * 平衡因子:每个结点都有其各自的平衡因子,是左子树与右子树的高度(深度)差。 * 平衡二叉树的平衡因子的取值只能是-1、0、1 三个值。 即,平衡因子 = 左子树高度 - 右子树高度。 * 扩展知识: * 设 Nh表示高度为 h 的平衡二叉树中含有的最少结点数,则有 N0 = 0,N1 =1,N2 =2 , … , Nh =Nh-1 +Nh-2 +1 > 通过本公式可以确定一定高度的平衡二叉树的最少结点数。 > * 查找效率: * 二叉排序树的查找效率取决于其高度。 * 对于结点个数相同的二叉排序树,平衡二叉树的高度最小,因此效率最高。 ### 2、平衡二叉树的建立 1. 与二叉排序树相同,都将关键字逐个插入空树。 2. 平衡二叉树在建立的过程中,每插入一个新的关键字都要进行检查,看是否新关键字的插入是否会使平衡二叉树失去平衡(平衡因子绝对值大于 1)。 * 若失去平衡则需要进行平衡调整。 ### 3、平衡调整 #### (1)基本思想 假设平衡二叉树插入新结点后平衡性被破坏: 首先要找出插入新结点后失去平衡的最小子树,然后再调整这棵子树,使之成为平衡子树。 > 当失去平衡的最小子树被调整为平衡子树后,无须调整原有其他所有的不平衡子树,整个二叉排序树会成为一棵平衡二叉树。 > > 失去平衡的最小子树:又称最小不平衡子树,是以距离插入结点最近,且以平衡因子绝对值大于 1 的结点作为跟的子树。 #### (2)类型 平衡调整有四种情况:LL 型、RR 型、LR 型、RL 型 假设距离插入结点最近的“不平衡因子”为 a: * **LL 型 - 单向右旋平衡处理:** 若由于结点 a 的左子树为根结点的左子树上插入结点,导致结点 a 的平衡因子由 1 增至 2,致使以 a 为根结点的子树失去平衡,则只需进行一次向右的顺时针旋转。 * **RR 型 - 单向左旋平衡处理:** 如果由于结点 a 的右子树为根结点的右子树上插入结点,导致结点 a 的平衡因子由 -1 变为 -2,则以 a 为根结点的子树需要进行一次向左的逆时针旋转。 * **LR 型 - 双向旋转(先左后右)平衡处理:** 如果由于结点 a 的左子树为根结点的右子树上插入结点,导致结点 a 平衡因子由 1 增至 2,致使以 a 为根结点的子树失去平衡,则需要进行两次旋转操作。 > 此图中插入结点也可以为结点 C 的右孩子,则(b)中插入结点的位置还是结点 C 右孩子,(c)中插入结点的位置为结点 A 的左孩子。 > * **RL 型 - 双向旋转(先右后左)平衡处理:** 如果由于结点 a 的右子树为根结点的左子树上插入结点,导致结点 a 平衡因子由 -1 变为 -2,致使以 a 为根结点的子树失去平衡,则需要进行两次旋转(先右旋后左旋)操作。 > 此图中插入结点也可以为结点 C 的右孩子,则(b)中插入结点的位置改为结点 B 的左孩子,(c)中插入结点的位置为结点 B 的左孩子。 > > LL、RR、LR、RL 并不是对调整过程的描述,而是对不平衡状态描述。 > > 例如: > > * LL 调整 (Left-Left),即新插入结点落在最小不平衡子树根结点的左(L)孩子的左(L)子树上。 > * LR 调整(Left-Right),即新插入结点落在最小不平衡子树根结点的左(L)孩子的右(R)子树上。 #### (3)补充 **最小失衡子树**:在新插入的结点向上查找,以第一个平衡因子的**绝对值**超过 1 的结点为根的子树称为最小不平衡子树。 > 不包含叶子结点(插入结点)的,但是从此向上寻找到平衡因子绝对值大于 1 的根结点的一条路径。要进行平衡调整的是此条路径,使其上的所有结点都保持平衡。 平衡二叉树的失衡调整主要是通过旋转最小失衡子树来实现的。 根据旋转的方向有两种处理方式,**左旋** 与 **右旋** 。 旋转的目的就是减少高度,通过降低整棵树的高度来平衡。哪边的树高,就把那边的树向上旋转。 1. 左旋操作: * (1)节点的左孩子代表此节点。 * (2)节点的左孩子的右子树变为节点的左子树。 * (3)将此节点作为左孩子节点的右子树。 2. 右旋操作: * (1)节点的左孩子代表此节点。 * (2)节点的左孩子的右子树变为节点的左子树。 * (3)将此节点作为左孩子节点的右子树。 AVL 树插入结点后导致树的不平衡,对最小不平衡树可能会出现的状况: * 对最小不平衡树的任意单子树进行调整,就能使树平衡。 * 当修改最小不平衡的单子树无法使其平衡时,可用根结点的相邻关键字代替它,使树平衡。此时,需要注意子树的结点可能需要更改位置。 ### 4、平衡 m 叉查找树 平衡 m 叉查找树是指每个关健字的左侧子树与右侧子树的高度差的绝对值不超过 1 的查找树,其结点结构与下面提到的 B-树结点结构相同。 ### 5、重新构造问题 直接在平衡二叉树中查找关键字 Key 与在对其进行中序遍历输出的有序序列中查找关键字 Key,其效率是否相同? 按关键字有序序列输入关键字,构造一棵二叉排序树,然后对此树进行查找,其效率如何? 为什么? * 在平衡二叉树上查找关键字 Key,走了一条从根到叶子的路径,时间复杂度可以通过树的高度来反映,是 O(log2n)。在中序遍历输出的序列中查找关键字 Key,如果采用顺序查找,则时间复杂度是 O(n);如果采用折半查找,则时间复杂度是 O(1og2n)。 * 按序输入建立的二叉排序树,因为插入元素是有序的,因此所有的插入操作都会发生在最左边的叶子结点的左指针上,或者最右边的叶子结点的右指针上,这样所形成的二叉排序树蜕变为单枝树,折半查找也蜕变成了顺序查找,其平均查找长度是(n+1)/2,时间复杂度是 O(n)。 ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/SplitLine/SplitLine-01.gif) # 四、B-树(B 树) ## (一)概念 B-树,又称 B 树,有时又写为 B_树(其中的“ - ”或者“ _ ”只是连字符,并不读作“B 减树”)。 B-树中所有结点孩子结点个数的最大值称为 B-树的阶,通常用 m 表示。 一颗 m 阶的 B-树,或者本身是空树,否则必须满足以下特性: 1. 子树个数: * 树中每个结点至多有 m 棵分支(子树)。 * 若根结点不是叶子结点,则至少有两棵分支。 * 非根非叶结点至少有⌈ m/2 ⌉ 个分支。 2. 关键字个数: * 有 n(k <= n <= m)个分支的结点有 n-1 个关键字,它们按递增顺序排列。 即:关键字个数 = 分支树 - 1。 * 阶数为 m 的 B-树,关键字个数的范围:⌈m/2⌉-1 ~ m-1。 > 除了根结点以外,其余结点的分支数为「m/2⌉ ≤ m。 > 3. 各结点的结构: * n:该结点中关键字的个数; * ki(1 <= i <= n):该结点的关键字且满足 ki< ki+1。(左结点关键字小于右结点关键字) * pi(0 <= i <= n):该结点的孩子指针且满足 pi(1 <= i <= n-1)所指结点的关键字大于 ki小于 ki+1。 > p0 所指结点上的关键字 k1,pn 所指结点上的关键字大于 kn 。 4. **结点:** * **根结点至少有两颗子树,且可以是空树,其余结点至少有⌈m/2⌉个分支。** * **叶结点处于同一层,可以用空指针表示,是查找失败到达的位置。** * **结点内是多个关键字互不相等,且从左至右、从小到大排序(即有序)。** **同层内,左边结点内所有关键字均小于右边结点内所有关键字。** 5. **很重要的特性:下层结点内的关键字取值总是落在由上层结点关键字所划分的区间内,具体落在哪个区间内可由指向它的指针看出。** > 注: > > 1. 阶是人为固定的,不随操作而改变。 > 2. B-树是平衡 m 叉查找树,且平衡因子只能为 0。 > 3. 查找不成功的位置:为了方使理解,将其简化为空指针,实际应用中此处指针指向一个结点,结点内设置一个标记代表查找不成功的位置,结点中还包含其他有用信息。 ## (二)查询操作 B-树是二叉排序树的扩展,是多路查找。 1. 先让 key 与根结点中的关键字比较,若 key = k[ i ],则查找成功。 2. 若 key < k[ 1 ],则到 p[ 0 ]所指示的子树中进行继续查找。 3. 若 key > k[ n ],则到 p[ n ]所指示的子树中继续查找。 4. 若 k[ i ] < key < k[ i+1 ],则沿着指针 p[ i ]所指示的子树继续查找。 5. 若最后遇见空指针,则证明查找不成功。 > k[ ]为结点内关键字数组,p[ ]为结点内的指针数组。 > ## (三)插入操作 B-树的创建过程也是将关键字逐个插入到树中的过程,插入操作只会使 B-树逐渐变高而不会改变叶子结点在同一层的特性。 ### 1、算法过程 1. 利用查找算法,找到插入位置(一定出现在终端结点上),直接插入。 2. 检查被插入结点内关键字的个数是否在区间(⌈m/2⌉-1 ~ m-1-1 ,m-1)。 * 若小于等于 m,则无需改变。 * 若大于 m,则需要拆分(分裂)。 ### 2、拆分方法 进行拆分时,结点内的关键字若已有 m 个, 1. 此处取出第 ⌈m/2⌉ 个关键字。 2. 将第 1 ~ ⌈m/2⌉-1 个关键字和第⌈m/2⌉ ~ m 个关键字做成两个结点连接在第⌈m/2⌉个关键字左右的指针上。 3. 将第⌈m/2⌉个关键字插入其父结点相应的位置上。 4. 若其父结点又出现关键字个数超出范围的情况,则继续进行拆分操作。 > 1. 拆分是在插入之后的。 > 2. 拆分出来的值永远是向上走的,不会向左、右、下走。 > 3. 当根结点拆分引起连锁反应,则下层结点不可做合并调整,仍保持在各自的结点内,但可调整其指针的指向。即,分割后不能再合并,“破镜无法重圆”。 ### 3、例 ## (四)删除操作 ### 1、算法分析 1. 若要删除的关键字在终端结点上,有以下三种情况。 1. 结点内关键字个数 < ⌈m/2⌉-1,则直接删除。 2. 结点内关键字个数 < ⌈m/2⌉-1,且左右兄弟结点中存在关键字个数 > ⌈m/2⌉-1 的结点,则从关键字个数 > ⌈m/2⌉-1 的兄弟结点中借关键字。 3. 结点内关键字个数 < ⌈m/2⌉-1,且左右兄弟结点中不存在关键字个数 > ⌈m/2⌉-1 的结点,则进行结点的合并。 * 两结点合并成一个。 > 采用不用的合并方法产生不同的 B-树。 > 2. 若要删除的关键字不在终端结点上,则需先将其转化为终端结点(使用相邻关键字代替),再按 1 方法进行处理。 ### 2、相邻关键字 (1)概念 对于不在终端结点上的关键字 a,它的相邻关键字为其左子树中最大关键字,或其右子树中值最小的关键字。 (2)寻找方法 * 沿着 a 的左指针来到其子树根结点,并沿根结点中最右端关键字的右指针往下走,其终端结点上的最右端关键字,即是。 > 找右边的相邻关键字同理。 > (3)删除关键字 a 删除关键字 a,可用其相邻关键字取代 a,并按照 1.1 中方法,删除终端结点的相邻关键字即可。 ### 3、例 ## (五)AVL-Tree 和 B-Tree 的区别 * B 树是平衡多路查找树,AVL 树是平衡二叉树,两者的平衡方式是不同的。 ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/SplitLine/SplitLine-01.gif) # 五、散列表 - Hash(哈希)表 ## (一)基本概念 散列表(Hash table,也叫哈希表),是根据关键码值,直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。 1、思想:根据给定关键字来计算出关键字在表中的地址。 2、基本概念: * Hash 函数:在 Hash 表中关键字与其地址间的映射函数关系,用 H()来表示。 * 数据的哈希地址 = H(关键字的值)。 > 这里的地址,可以是数组下标、索引、或内存地址等。 > * Hash 地址:只是表示在查找表中的存储位置,而不是实际的物理存储位置。 * 散列表:存放记录的数组,建立了关键字和存储地址间的直接映射关系。 > 即,根据散列函数 H(k)和处理冲突的方法,将一组关键字映射到一个有限的连续的地址集(区间)上,并以关键字在地址集中的“像”作为记录在表中的存储位置。 > * 冲突现象:对不同的关键字可能得到同一散列地址,即 **k1≠k2**,而 **H(k1)=H(k2)**。 * 冲突处理:为冲突关键字的记录找到另一个空的 Hash 地址。 * 同义词:具有相同函数值的关键字对该散列函数来说称做同义词。 > 对于哈希表而言,冲突只能尽可能地少,无法完全避免。 > > 关键字经过散列函数得到一个“随机的地址”,且到表中任何一个地址的概率是相同的。 H(key)是 key 的 Hash 地址;Hi (key)是对 key 解决冲突后的地址,注意区分。 ## (二)Hash 表的建立方法(构造 Hash 函数) 常用的哈希函数的构造方法有 6 种:直接定址法、数字分析法、平方取中法、折叠法、除留余数法和随机数法。 > 考察最多的是除留余数法,折叠法、随机数法直到名字即可。 > > 通常考虑的因素有以下几方面: > > * 关键字的长度。如果长度不等,就选用随机数法。如果关键字位数较多,就选用数字分析法;反之如果位数较短,可以考虑平方取中法; > * 哈希表的大小。如果大小已知,可以选用除留余数法; > * 关键字的分布情况; > * 查找表的查找频率; > * 计算哈希函数所需的时间(包括硬件指令的因素) > > 因此要减少冲突,应当使得函数值以等概率取其值域中的每个值。 ### 1、直接定址法 其哈希函数为一次函数,即以下两种形式: * H(key)= key * H(key)=a * key + b > 其中 H(key)表示关键字为 key 对应的哈希地址,a 和 b 都为常数。 > > 此方法不会产生冲突 ### 2、数字分析法 假设关键字是 r 进制数(如十进制数),且遵循选取原则,则可选取关键字中的若干数位(其中的 2 位或多位)组成 Hash 地址。 选取原则:尽量取冲突较少的位数段,即,所选数位上的数字尽可能是随机的(数据规律性低)。 > 使用于关键字位数较多,且表中可能的关键字都是已知情况 ### 3、平方取中法 取关键字平方后的中间几位作为 Hash 地址,所取位数由表长、需求等决定。 > 一个数平方后的中间几位数和数的每一位都相关,由此得到的 Hash 地址随机性更大。 ### 4、除留余数法 取关键字某个不大于 Hash 表表长 len 的数 p 除后所得的余数位 Hash 地址,即 * H(key)= key mod p (p <= len) * H(key)= key % p p 的选取原则:一般 p 选择小于或等于 len 的最大素数,题中一般会给出。 > 此方法可以对关键字进行直接取余,或折叠、平方取中等运算之后取余 ### 5、随机数法 是取关键字的一个随机函数值作为它的哈希地址,即: * H(key)=random(key) > 此方法适用于关键字长度不等的情况。 ## (三)Hash 表的冲突解决方法 在处理冲突的过程中,可能会得到一个地址序列 Hi ,即:处理冲突中第 i 次探测得到的 Hash 地址。 假设得到的另一个 Hash 地址 H1 仍发生冲突,只得继续求 H2 ,以此类推,直到 Hk 不发生冲突为止,则 Hk 为关键字在表中的地址。 > Hi ∈ [ 0,……,m-1 ] i=1,2,…,n 一般冲突处理的过程是穿插在建表过程中的,即边建表边检测冲突,当发生冲突时立即解决冲突。 所谓堆积问题,即在 Hash 表的建立过程中,某些 Hash 地址是由冲突处理产生的,而不是由 Hash 函数直接产生的,这就可能造成原本 Key 与 Key2 虽然不是同义词,但是最后却得出了相同的 Hash 地址。 ### 1、开放地址法 #### (1)线性探查法 从发生冲突的地址(设为 d)开始,依次探查 d 的下一个地址,直到找到一个空位置为止。记: * Hi(key)=(H(key)+ i)mod len i∈(1~len - 1) > 当到达表尾时,探查地址从表首重新开始探查。 > > 当表长大于关键字个数时,一定能找到一个空位置。 特点:可以探测到表中所有位置,但是易产生堆积问题。 #### (2)平方探查法(二次探测再散列、线性探测再散列) 设发生冲突的地址为 d,则探测到的新地址为: * d+12、d-12、d+22 、d-22、d+32、d-32 …… d:指的是第一次发生碰撞的地址。 特点:不可以探测到表中所有位置(至少可以探测到一半位置)但是不易产生堆积问题。 ### 2、链地址法 链地址法是把所有的同义词用单链表连接起来的方法。 Hash 表每个单元中存放的不再是记录本身,而是相应同义词单链表的表头指针。 * 若用除留余数法构造 Hash 表时,表长可以选取为 P,因为往后都取不到。 若插入规定在链首,则插入操作不需要查找插入位置即可直接进行,因此插入任何一个元素的时间均相同。 若插入规定在链尾,需要找到链表的尾部,因此链表的长度决定了插入元素的执行时间。 链地址法不会产生堆积现象,因为多个同义词只会占用表中的一个地址,因此 ③ 不正确。 > 在考研数据结构的考题中, > > * 如果问链地址法会不会产生堆积现象,答案是不会。 > * 如果问堆积现象可不可以完全避免,答案是不可以。 ## (四)Hash 表的建立过程 Hash 表的建立过程: * key 进行 Hash 函数得到结果地址。 * 检测是否发生冲突: * 若冲突,进行冲突处理。 * 若不冲突,则直接插入。 > Hash 表下标从 0 开始 ## (五)Hash 关键字 key 的查找过程 * 先用 Hash 函数计算出一个地址,然后用 key 和这个地址上的关键字进行比较。 * 如果当前地址上为空,则证明查找失败。 * 如果和当前地址上的关键字相同,则证明查找成功。 * 如果不相同,则根据冲突处理方法到下一个地址继续比较,直到相同为止,证明查找成功;如果按照冲突处理方法寻找新地址的过程中又遇到空位置,则证明查找失败。 ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/SplitLine/SplitLine-01.gif) # 六、性能分析 ## (一)线性结构 ### 1、顺序查找 性能分析 查找方式为从头扫到尾,找到待查找元素即查找成功,若到尾部没有找到,说明查找失败。 * 平均查找长度: $$ASL_{succeed} = {{n+1} \over {2}}$$ $$ASL_{failure} = n+1$$ > (因为 0 位置处还有一个哨兵需要比较,所以 +1) > > * ASL 成功: > > * 当查找 n 个关键字的概率是相等的,因此对于每个关键字的查找概率均为 1/n。 > * 在表中第一个关键字的比较次数为 1,以后的每个关键字的比较次数比前一个多 1,一共 n 个记录,因此由等差数列求和公式可得所有记录比较次数的总和为(1+n)n/2,则平均查找长度为(1/n)×( 1+n)n/2=(n+1)/2。 > * ASL 失败:当待查找元素不在查找表中时,也就是扫描整个表都没有找到,即比较了 n 次,查找失败, > * 时间复杂度:O(n) * 优点:是对数据元素的存储没有需求,顺序存储或链式存储皆可;对表中记录的有序性也没有要求,无论记录是否按关键码有序,均可应用。 * 缺点:是当 n 较大时,平均查找长度较大,效率低。 特点: * 顺序查找下给出的查找序列可以有序,也可以无序。 * 查找算法简单,但时间效率太低时间复杂度为 O(n)。 ### 2、折半查找 查找方式为(找 k),先与树根结点进行比较,若 k 小于根,则转向左子树继续比较,若 k 大于根,则转向右子树,递归进行上述过程,直到查找成功或查找失败。 #### (1)平均查找长度的求法 查找路径实际为树中从根节点到被查结点的一条路径,关键宇的比较次数即为关键字在树中的层数。 若有序表长度为 n,外结点个数为 n+1: ① 平均查找长度 * 查找每个结点的比较次数之和 除以 有序表的长度。 * 即,ASL =(每层结点数 × 比较次数(层数))/n ② 最坏查找长度(查找失败) * 每个外结点的的比较次数之和 除以 外结点的个数。 * 即,ASL =(每层外节点数 × 比较次数(上一层层数))/(n+1) #### (2)性能分析 * 平均查找长度: $$ASL_{succeed}={{n+1}\over{n}log_2(n+1)-1}=log_2(n+1)-1$$ > 根据折半查找法的执行过程可以做出一棵二叉树,即折半查找判定树,如果将这个二叉树的最底层结点去掉,则这棵二叉树是一棵满二叉树,而查找过程就是走了从根结点到树中某一结点的一条路径,路径上结点的个数就是关键字的比较次数。 > > 对于这棵二叉树,其高度为⌊ log2n⌋+1,这是表中关键字的最大比较次数,则折半查找的平均查找长度应该不大于⌊log2n⌋+1。 > * 时间复杂度:O( logn ) * 优点:折半查找的时间复杂度为 O( logn ),远远优于顺序查找的 O(n)。 * 缺点:虽然二分查找的效率高,但是要求表关键字有序。 #### (3)特点 * 折半查找只适用顺序存储结构,链表上无法实现二分查找。 * 折半查找适用于那种一经建立就很少改动但又经常需要查找的线性表。 ### 3、分块查找 性能分析: * 平均查找长度: $$ASL = L_I+L_S$$ > Index 和 Sequence,索引查找和块内查找(块内顺序查找)的平均长度之和。 > 将长度为 n 的查找表均匀地分为 b 块,每块有 s 个记录。 * 索引表中(块间)采用顺序查找,块内采用顺序查找: $$ASL_{succeed}=L_I+L_S={{(b+1)}\over{2}}+{{(s+1)}\over{2}}={{s^2+2s+n}\over{2s}}$$ > 此时,若 $$s=\sqrt{n}$$,则平均查找长度取最小值 $$\sqrt{n}+1$$ > * 索引表中(块间)采用折半查找,块内采用顺序查找: $$ASL_{succeed}=L_I+L_S={{log_2(b+1)+s+1}\over{2}}$$ 为使查找效率最高,每个索引块的大小应是 $$\sqrt{n}$$。(即 索引项*索引块=表长,等分了索引项和索引块) 特点: * 分块查找下给定的序列应该是分块有序的,适用于顺序存储结构和链式存储结构。(如果索引表不强制要求用折半查找的话) * 分块查找下其平均查找长度介于顺序查找和折半查找之间。 * 其平均查找长度有索引表和主表两部分组成。 ## (二)树形结构 ### 二叉排序树 对二叉排序树进行对关键字的查找时,其平均查找长度和二叉排序树的形态有关。 在最坏情况下,n 个结点的二叉排序树是一棵深度为 n 的单支树(树的高度达到最大),其 ASL 和单链表上的顺序查找相同,为(n+1)/2。 最好情况下,n 个结点的二叉树会得到一棵形态与折半查找的判定树相似的二叉树(树的高度达到最小),此时其 ASL 约为 log2n。 ## (三)散列结构(散列表) ### 1、装填因子 表示 Hsah 表中元素的填满的程度,用 a 表示。 * 装填因子 = 关键字个数 / 表长 a = n / len len = ⌈ n / a ⌉ > 加载因子是 0.75 代表: > > 数组中的 16 个位置,其中存入 16*0.75=12 个元素 当装填因子越大,即填满的元素越多: * 好处:空间利用率高 * 缺点:越有可能发生冲突 当装填因子越小,即填满的元素越少。 * 好处:冲突的机会减小 * 缺点:空间浪费多 当存入元素数量 > 哈希表长度 * 装填因子,就要扩容。 ### 2、ASL(等概率情况下) 查找效率:Hash 查找法是由关键字结合 Hash 函数和冲突处理方法直接算出关键字在表中的位置,与表的长度 n 无关,其查找的时间复杂度对于 n 为常级,即 O(1)。 #### (1)ASL 公式 ##### ① 查找成功时 $$ASL = \frac{1}{n}\sum_{i=1}^{n}{C_i}$$ * n :散列表中记录的个数。 > **不是表的长度** > * Ci :查找成功的第 i 个记录所需要的比较次数。 > **表中空的记录意味着不成功,是不算在里面滴** > ###### ② 查找不成功时 $$ASL = \frac{1}{r}\sum_{i=1}^{n}{C_i}$$ * r :散列函数取值的个数(**不是表的长度**)。 * Ci :散列函数取值为 i 时,查找失败时第 i 个记录所需要的比较次数。 > **表中的有些部分,散列函数根本取不到,自然也就不在计算里了** > #### (3)比较次数 查找成功与不成功 ASL 的比较是不同的: * 成功:为关键字所进行的比较。 * 不成功:为地址的比较,空地址的比较次数为 0。 #### (4)Hash 表解决冲突时的 ASL 与关键字的个数 n 无关,与装填因子 a 有关。 ![](https://picture-host-1304031833.cos.ap-beijing.myqcloud.com/SiYuan/SplitLine/SplitLine-01.gif) # 参考资料 > **版权声明**:个人学习记录,本博客所有文章均采用 CC-BY-NC-SA 许可协议。转载请注明出处!若有侵权,请留言联系! > > * 2022 天勤计算机考研高分笔记-数据结构 > * 2022 王道计算机考研复习指导-数据结构 > * 解学武数据结构与算法教程(C 语言版):http://data.biancheng.net/ > * https://www.it610.com/article/1277646050596765696.htm 如果您觉得文章对您有帮助,请点击文章正下方的小**红心**一下。您的鼓励是博主的最大动力! 1 最后一次更新于2022-10-23 数据结构
0 条评论