数据结构与算法基础(青岛大学-王卓)(8)

2023-10-02 23:42

本文主要是介绍数据结构与算法基础(青岛大学-王卓)(8),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

哎呀呀,sorry艾瑞波地,这次真的断更一个月了,又发生了很多很多事情,秋风开始瑟瑟了,老父亲身体查出肿瘤了,有病请及时就医,愿每一个人都有一个健康的身体,God bless U and FAMILY.
直接上货了 😃


文章目录

    • 查找
      • 概念
      • 线性表的查找
        • 顺序查找(线性)
          • 应用范围:
          • 表示方法:
          • 算法:
          • 算法7.2时间效率分析:
          • 讨论
          • 优缺点:
        • 折半查找(对半/二分)
          • 算法思路
          • 二分查找效率分析 - 判定树
          • 平均查找长度ASL(成功时)
          • 优缺点
        • 分块查找(索引顺序查找)
          • 条件
          • 性能分析
          • 优缺点
      • 树表的查找
        • 二叉排序树 (Binary Sort Tree)
          • 二叉排序树定义
          • 二叉排序树的性质
          • 二叉排序树查找
          • 二叉排序树的插入
          • 二叉排序树的生成
          • 二叉排序树的删除
          • 平衡二叉树
      • 散列表的查找
        • 散列表术语
        • 散列函数构造方法
          • 直接定址法
          • 除留余数法
        • 处理冲突的方法
          • 开放地址法
          • 链地址法
        • 散列表查找

查找

内容回顾:
在这里插入图片描述

概念

  • 查找表是由同一类型的数据元素(或记录)构成的集合。由于"集合"中的数据元素之间存在着松散的关系,因此查找表是一种应用灵便的结构。

  • 查找 – 根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素或(记录),查找成功返回该记录信息或者位置,查找不成功则给出空记录或者空指针。

  • 关键字:用来标识一个数据元素(或记录)的某个数据项的值。分为 主关键字(可唯一地标识一个记录的关键字) 和 次关键字(用以识别若干记录的关腱字)。

  • 对查找表的操作:查询记录, 检索属性, 插入数据元素, 删除数据元素。

  • 查找表分类:

    • 静态(仅查询)
    • 动态(可插入,删除)
  • 查找算法的评价指标 – 平均查找长度(关键字的平均比较次数) – ASL(Average Search Length)

    在这里插入图片描述

  • 查找的方法取决于查找表的结构,即表中数据元素是依何种关系组织在一起的。为提高查找效率,一个办法就是在构造查找表时,在集合中的数据元素之间人为地加上某种确定的约束关系

线性表的查找

顺序查找(线性)
应用范围:
  • 顺序表或线性链表表示的静态查找表
  • 表内元素之间无序
表示方法:
// 数据元素的类型定义
typedef struct {KeyType key; //关键字域......       //其他域
} ElemType;// 顺序表结构类型定义
typedef struct {ElemType *R; // 表基址int length; //表长
} SSTable; //Sequential Search Table//定义一个顺序表ST
SSTable ST;
算法:

在这里插入图片描述

// 算法7.1
int Search_Seq(SSTable ST, KeyType key) {// 如成功则返回位置信息,不成功返回0for(i=ST.length; i>=1; --i) {if (ST.R[i].key == key) return i;return 0;}
}
// 算法改1
int Search_Seq(SStable ST, KeyType key) {for(i=ST.length; ST.R[i].key != key; --i)if (i<=0) break;if (i>0) return i;else return 0;
}// 算法改2
inti Search_Seq(SStabl ST, KeyType key) {for(i=ST.length; ST.R[i].key != key&&i>0; --i);if (i>0) return i;else return 0;
}

上面的算法的每一次循序都需要进行两次比较,能否改进?

  • 查找的值是否相等
  • i的值是否越界

改进:

把待查关键字 key 存入表头("哨兵、“监视哨”) 从后往前个比较,可免去查找过程中每一步都要检测是否查找完毕,加快速度。(如果找不到在表头[0]位置也一定会找到)。

当ST.length较大时,此改进能使进行一次查找所需的平均时间几乎减少一半。

在这里插入图片描述

// 改进算法7.2
int Search_Seq(SSTable ST, KeyType key) {ST.R[0].key = key;for (i=ST.length; ST.R[i].key != key; --i);return i;}
}
算法7.2时间效率分析:

在这里插入图片描述

时间复杂度:O(n)

查找成功时的平均查找长度,设表中各记录查找概率相等(注意这里是指的是查找成功时所以不算哨兵位置)

ASLs(n)=(1 + 2 +…+ n)/n = (n+1)/2

空间复杂度:O(1) — 辅助空间用于哨兵位置

讨论

1 、记录的查找概率不相等时如何提高查找效率?

查找表存储记录原则按照查找概率高低存储:1 )查找概率越高,比较次数越少;2 )查找概率越低,比较次数较多。

2 、记录的查找概率无法测定日日何提高查找效率?

方法 – 按查找概率动态调整记录顺序.1 )在每个记录中设一个访问频度域;2 )始终保持记录按非递增有序的次序排列;3 )每次查找后均将刚查到的记录直接移至表头。

优缺点:

优点:算法简单,逻辑次序无要求,且不同存储结构均适用。

缺点:ASL 太长,时间效率太低。

折半查找(对半/二分)

折半查找:每次将待查记录所在区间缩小一半。

在这里插入图片描述

算法思路

非递归算法

  • 设表长为n,low、high 和 mid 分别指向待查元素所在区间的上界、下界和中点, key 为给定的要查找的值.

  • 初始时,令low = 1,high=n, mid=$\lfloor(low+high)/2\rfloor $

  • 让 k 与 mid 指向的记录比较

    • 若key == R[mid].key 查找成功
    • 若key < R[mid].key, 则 high=mid-1
    • 若 key > R[mid].key, 则 low=mid+1
  • 重复上述操作,直至 low>high 时,查找失败

// 二分查找(非递归)
int Search_Bin(SSTabl ST, KeyType key) {low = 1;high = ST.length; // 初始化置区间值while (low <= high) { mid = (low + high) / 2;if (ST.R[mid].key == key) return mid; // 找到元素else if (ST.R[mid].key < key) {  // 缩小区间low = mid + 1; // 继续在后半区查找} else high = mid -1; // 继续在前半区查找}return 0; // 表中不存在待查元素
} // Search_Bin// 二分查找(递归)
int Search_Bin(SSTable ST, KeyType key, int low, int high) {if (low > high) return 0; // 查找不到时返回0mid = (low + high)/2if (ST.R[mid].key == key) return mid;else if (ST.R[mid].key > key) {Search_Bin(ST, key, low, mid-1);} else {Search_Bin(ST, key, mid+1, high);}
}
二分查找效率分析 - 判定树

在这里插入图片描述

在这里插入图片描述

平均查找长度ASL(成功时)

在这里插入图片描述

优缺点

折半查找优点:效率比顺序查找高

折半查找缺点:只适用于有序表,且限于顺序存储结构(对线性链表无效)。

分块查找(索引顺序查找)
条件
  1. 将表分成几块,且表或者有序,或者分块有序;若i < j,则第 j 块中所有记录的关键字均大于第 i 块中的最大关键字。

  2. 建立"索引表"(每个结点含有最大关键字域和指向本块第一个结点的指针,且按关键字有序)。

    查找过程:找38 --> 目标在索引48的块中 --> 顺序/折半在块内查找–> 找到38

    在这里插入图片描述

性能分析

在这里插入图片描述

优缺点

优点:插入和删除比较容易,无需进行大量移动。

缺点:要增加一个索引表的存储空间并对初始索引表进行排序运算。

适用情况如果线性表既要快速查找又经常动态变化,则可采用分块查找。

在这里插入图片描述

树表的查找

动态查找表 – 几种特殊的树, 用来解决插入,删除频繁操作但需要维护表的有序性情况。

表结构在查找过程中动态生成对于给定值 key若表中存在,则成功返回;否则,插入关字等于 key 的记录

分类

  • 二叉排序树
  • 平衡二叉树
  • 红黑树
  • B- 树
  • B+ 树
  • 键树
二叉排序树 (Binary Sort Tree)

又称为二叉搜索树、二叉查找树

二叉排序树定义

二叉排序树或是空树,或是满足如下性质的二叉树:

  1. 若其左子树非空,则左子树上所有结点的值均小于根结点的值;

  2. 若其右子树非空,则右子树上所有结点的值均大于等于根结点的值;

  3. 其左右子树本身又各是一棵二叉排序树

    在这里插入图片描述

二叉排序树的性质

中序遍历非空的二叉排序树所得到的数据元素序列是一个按关键字排列的递增有序序列。

如上图就是 3 12 24 37 45 53 61 78 90 100

二叉排序树查找

算法

在这里插入图片描述

typedef struct {KeyType key;  //关键字项infoType otherinfo;  //其他数据域
}ElemType;typedef stuct BSTNode {ElemType data;  //数据域struct BSTNode *lchild, *rchild;  //左右孩子指针
}BSTNode, *BSTree;BSTree T;  //定义二叉排序树T

在这里插入图片描述

BSTree SearchBST(BSTree T, KeyType key) {if (!T) || (key == T->data.key) return T; //表为空或者表不为空且找到了都返回一个指针T(BSTree类型)else if (key < T->data.key)   // 判断key在左右子树的位置return SearchBST(T->lchild, key); //继续在左子树上找else return SearchBST(T->rchild, key);  //继续在右子树上找
}//SearchBST

平均查找长度

在这里插入图片描述

二叉排序树上查找某关键字等于给定值的结点过程,其实就是走了一条从根到该结点的路径。

在这里插入图片描述

总结:含有 n 个结点的二叉排序树的平均查找长度和树的形态有关

在这里插入图片描述

二叉排序树的插入
  • 若二叉排序树为空,则插入结点作为根结点插入到空树中

  • 否则,继续在其左、右子树上查找

    • 树中已有,不再插入

    • 树中没有

      • 查找直至某个叶子结点的左子树或右子树为空为止,则插入结点应为该叶子结点的左孩子或右孩子
  • 插入的元素一定在叶结点

在这里插入图片描述

二叉排序树的生成
  • 从空树出发,经过一系列的查找、插入操作之后,可生成一棵二叉排序树。

  • 一个无序序列可通过构造二叉排序树而变成一个有序序列。构造树的过程就是对无序序列进行排序的过程。(插入的结点均为叶子结点,故无需移动其他结点)

  • 关键字的输入顺序不同,建立的不同二叉排序树。

    在这里插入图片描述

二叉排序树的删除

从二叉排序树中删除一个结点,不能把以该结点为根的子树都删掉,只能删掉该结点,并且还应保证删除后所得的二叉树仍然满足二叉排序树的性质不变。在二叉排序树中删去一个结点相当于删去有序序列中的一个结点。(中序遍历二叉树得到递增有序的序列)

  1. 被删除的结点是叶子结点:直接删去该结点。

  2. 被删除的结点只有左子树或者只有右子树,用其左子树或者右子树替换它(结点替换)。

    其双亲结点的相应指针域的值改为“指向被删除结点的左子树或者右子树”

    在这里插入图片描述

  3. 被删除的结点既有左子树,也有右子树

    以其中序前趋值替换之(值替换),然后再删除该前趋结点。前趋是左子树中最大的结点。

    也可以用其后继替换之,然后再除该后继结点。后继是右子树中最小的结点。

    在这里插入图片描述

  4. 总结图:

    在这里插入图片描述

平衡二叉树

平衡二叉树 (balanced binary tree)又称 AVL (Adelson VeIskii and Landis)

一棵平衡二叉树或者是空树,或者是具有下列性质的二叉排序树.

  • 左子树与右子树的高度之差的绝对值小于等于 1
  • 左子树和右子树也是平衡二叉排序树。

结点的平衡因子 (BF)

  • 给每个结点附加一个数字,给出该结点左子树右子树的高度差。值范围(-1, 0 ,1)

  • 平衡因子=结点左子树的高度-结点右子树的高度

  • 对于一棵有 n 个结点的 AVL 树,其高度保持在 O(log2n )数量级,ASL也保持在 O(log2n )量级

在这里插入图片描述

失衡二叉排序树的调整

四种类型

在这里插入图片描述

调整原则

  • 降低高度
  • 保持二叉排序树的性质

在这里插入图片描述

  1. LL型调整

    在这里插入图片描述

    在这里插入图片描述

  2. RR型

    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述

  3. LR型

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

  4. RL型
    在这里插入图片描述
    在这里插入图片描述

构造案例

输入关键字序列(16,3,7,11,9,26,18,14,15), 给出构造AVL 树的步骤。

在这里插入图片描述

散列表的查找

基本思想:记录的存储位置与关键字之间存在对应关系

对应关系-- hash 函数 Loc(i)= H(keyi)

散列表术语

散列方法(杂凑法):

选取某个函数,依该函数按关键字计算元素的存储位置,并按此存放;查找时,由同一个函数对给定值 k 计算地址,将 k 与地址单元中元素关键码进行比,确定查找是否成功。

散列函数(杂凑函数):散列方法中使用的转换函数

散列表(杂凑表):按上述思想构造的表

散列存储:选取某个函数,依该函数按关键字计算元素的存储位置 Loc(i)=H(keyi)

冲突:不同的关键码映射到同一个散列地址,当key1 != key2 我们的 H(key1)=H(key2)

在这里插入图片描述

散列函数构造方法

在散列查找方法中,冲突是不可能避免的,只能尽可能减少。

构造散列函数考虑的因素:

  • 执行速度(即计算散列函数所需时间)
  • 关键字的长度;
  • 散列表的大小;
  • 关键字的分布情况;
  • 查找频率。

根据元素集合的特性构造

  • 要求一:n 个数据原仅占用 n 个地址。虽然散列查找是以空间换时间,但仍希望散列的地址空间尽量小。

  • 要求二:无论用什么方法存储,目的都是尽量均匀地存放元素,以避免冲突。

有以下方法

  • 直接定址法
  • 数字分析法
  • 平方取中法
  • 折叠法
  • 除留余数法(最常用)
  • 随机数法
直接定址法

Hash(key) = a*key + b (a 、b为常数)

优点:以关键码 key 的某个线性函数值为散列地址,不会产生冲突。

缺点:要占用连续地址空间,空间效率低。

在这里插入图片描述

除留余数法

Hash(key)= key mod p( p 是一个整数)

如何取p: 设表长为 m ,取 p <= m 且为质数

在这里插入图片描述

处理冲突的方法

方法:

  • 开放定址法(开地址法)
  • 链地址法(拉链法)
  • 再散列法(双散列函数法)
  • 建立一个公共溢出区
开放地址法

基本思想:有冲突时就去寻找下空的散列地址,只要散列表足够大,空的散列地址总能找到,并将数据元素存入。

例如:除留余数法Hi=(Hash(key)+di) mod m (di 为增量序列)

常用方法:线性探测法;二次探测法;伪随机法

在这里插入图片描述

线性探测法

在这里插入图片描述

例:关键码集为{47,7,29,11,16,92,22,8,3}, 散列表长为 m = 11 ;散列函数为 Hash(key)=key mod 11 ;拟用线性探测冲突。建散列表如下:

在这里插入图片描述

二次探测法

在这里插入图片描述

伪随机探测法:

在这里插入图片描述

链地址法

基本思想:相同散列地址的记录链成一单链表

m个散列地址就设 m个单链表,然后用一个数组将m个单链表的表头指针存储起来,形成一个动态的结构。

在这里插入图片描述

链地址法建立散列表步骤

Step1: 取数据元素的关键字 key ,计算其散列函数值(地址)。若该地址对应的链表为空,则将该元素插入此链表;否则执行 Step2 解决冲突。

Step2: 根据选择的冲突处理方法,计算关键字 key 的下一个存储地址。若该地址对应的链表为不为空,则利用链表的前插法后插法将该元素插入此链表。

优点

  • 非同义词不会冲突,无"聚集"现象

  • 链表上结点空间动态申请,更适合表长不确定的情况

散列表查找

在这里插入图片描述

例题:

已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79)散列函数为: H(key) = key MOD 13,散列表长为 m = 16 ,设每个记录的查找概率相等

在这里插入图片描述

在这里插入图片描述

使用平均查找长度 ASL 来衡量查找算法, ASL 取决于:

  • 散列函数

  • 处理冲突的方法

  • 散列表的装填因子α(α=表中填入记录数/哈希表的长度, α越大,表中记录数越多,说明表装得越满,发生冲突的可能性就越大,查找时比较次数就越多。)

    在这里插入图片描述

结论

  • 散列表技术具有很好的平均性能,优于一些传统的技术
  • 链地址法优于开地址法
  • 除留余数法作散列函数优于其它类型函数

TO BE CONTINUED…

这篇关于数据结构与算法基础(青岛大学-王卓)(8)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/121

相关文章

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

零基础学习Redis(10) -- zset类型命令使用

zset是有序集合,内部除了存储元素外,还会存储一个score,存储在zset中的元素会按照score的大小升序排列,不同元素的score可以重复,score相同的元素会按照元素的字典序排列。 1. zset常用命令 1.1 zadd  zadd key [NX | XX] [GT | LT]   [CH] [INCR] score member [score member ...]

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

秋招最新大模型算法面试,熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候,不知道面试完会不会复盘、总结,做笔记的习惯,这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助,都附有完整答案,熬夜也要看完,祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN,还有完整版的大模型 AI 学习资料,朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)

dp算法练习题【8】

不同二叉搜索树 96. 不同的二叉搜索树 给你一个整数 n ,求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。 示例 1: 输入:n = 3输出:5 示例 2: 输入:n = 1输出:1 class Solution {public int numTrees(int n) {int[] dp = new int