首页 > 编程语言 >五、数据结构与算法

五、数据结构与算法

时间：2024-11-03 19:45:37浏览次数：5  
标签：结点 排序 递归 复杂度 算法 二叉树 数据结构 节点

五、数据结构与算法

注意：

本文章学习了zst_2001大佬的视频。本人亲自写的笔记。
其中部分图片是结合了给位大佬的笔记图片整理的。目的是为了帮助速记。
不喜勿喷

1、时间空间复杂度排序

1、时间复杂度

O(1)<O(log2n)<O(n)<O(nlog2n)<O(n²)<O(n^3)

  • 加法：相加，保留最高项系数化为1 4n^3+2n²+4n+2 =n^3

  • 乘法：相乘，系数化为1

  • 规则：先括号在乘在加

  • log2n 常见是while循环 x=x*2

  • n 常见的for循环 x++

1、非递归

1、主要还是看循环

2、递归

1、递归的次数 × 每次递归的时间复杂度（适用于每次递归时间复杂度不变的情况）

2、时间复杂度不变

3、时间复杂度变

2、空间复杂度

1、非递归

1、是对一个算法在运行过程中临时占用存储空间大小的一个量度

2、空间复杂度比较常用的有：

  • O(1)：只有简单变量

  • O(n)：会随着处理数据量变化（例如new 一个数组）

  • O(n²)

2、递归

1、递归的次数 × 每次递归的空间复杂度（适用于每次递归空间复杂度不变的情况）

2、没有定义变量，即时递归n次，空间复杂度都是O(1)

3、考试题目说明

4、递归式时间空间复杂度

2、线性表

1、顺序表

1、采用顺序存储，优点是可以随机存取表中的元素；

2、缺点是插入和删除操作需要移动大量的元素。

3、时间复杂度

  • 插入、删除操作最好时间复杂度为 O(1)，平均和最坏时间复杂度都为 O(n)

  • 查找最好、最坏、平均情况都为 O(1)

2、单链表

1、单链表：采用链式存储，优点是插入和删除操作不需要移动大量的元素，只需要修改指针；

2、缺点是不能随机访问表中的元素。

3、时间复杂度

  • 查找、插入、删除操作最好时间复杂度为 O(1)，

  • 平均和最坏时间复杂度都为 O(n)

3、栈

1、栈是一种先进后出（后进先出）的线性结构，只能在栈的一端（栈顶）进行

插入和删除。递归使用栈

2、实现函数或过程的递归调用及返回处理时

3、出栈跟入栈是不需要遍历的

4、队列

1、队列是一种先进先出(First In First Out， FIFO)的线性表，它

只允许在表的一端插入元素,而在表的另一端删除元素。在队列中,允许插入元素

的一端称为队尾( Rear)，允许删除元素的一端称为队头(Front)。

2、队列的基本运算。

①初始化队列InitQueue(Q):创建一个空的队列Q。

②判队空isEmpty(Q):当队列为空时返回“真”，否则返回“假”。

③入队EnterQueue(Q,x):将元素x加入到队列Q的队尾，并更新队尾指针。

④出队DeleteQueue(Q):将队头元素从队列Q中删除，并更新队头指针。

⑤读队头元素FrontQue(Q):返回队头元素的值，但不更新队头指针

3、队列是否已满

  • 如果 (rear +1)%maxSize = front 表示队列已满

4、队列有效数据个数

5、栈与队列的关系

  • 两个栈可以模拟一个队列

  • 两个队列可以模拟一个栈

5、串

1、字符串是线性结构，空格也是字符串

子串是指由主串中任意长度连续的字符构成的序列

2、例如：

主串：abc

字串：a、b、c、ab、bc

ac不是字串，因为它不是主串中连续的字符

3、

1、串的匹配模式

1、朴素匹配模式

2、KMP next数组❗

1、前缀: 包含首位字符但不包含末位字符的字串

2、后缀: 包含末位字符但不包含首位字符的字串

3、next数组定义: 当主串与模式串的某一位字符不匹配时，模式串要回退的位置

4、next[ j ]: 其值 = 第 j 位字符前面 j-1 位字符组成的字串的前后缀重合字符数+1

5、特殊情况next[1]=0

6、时间复杂度O(n+m)

、例子

6、数组

1、一维数组

1、如图

2、如图理解

2、二维数组

1、如图

2、如图理解

3、求首地址

  • 首地址 = LOC + (i x M + j) x L

  • 首先，知道前面有多少行（假设 i 行）

  • 每行有多少列（假设 M 列）

  • 则前面行数共有 i x M 个元素。

  • 例如 a1，可以知道前面有 1 行，每行3列, 则 前面共有 1 x 3 个元素

7、矩阵

1、对称矩阵

1、Aij = Aji

2、对称矩阵三角区域

3、存储

4、可以看到这是个等差数列，等差数列求和公式: 总数 = (a1+an)n/2

1、求Ai,j前共有多少个元素

1、如图

2、三角矩阵

1、只有中间存储数据，下三角和上三角的值都是0

2、如图理解

3、公式

3、稀疏矩阵

1、三元组顺序表和十字链表是对稀疏矩阵进行压缩存储的方式

2、稀疏矩阵的三元组表的顺序存储结构称为三元组顺序表，常用的三元组表的链式存储结构是十字链表。

3、如图理解

4、一般做题，就直接带。

8、树

1、概念

1、节点的度： 一个节点的子树的个数。例如 A 节点有2个子树，度为2。

2、树的高度（深度）： 一棵树的最大层数。当前树的最大层数是4，所以树的高度是4

3、树的度：树中节点的度的最大值

2、性质

1、性质一

2、性质二

3、性质三

4、性质四

  • 这里是向上取整

9、二叉树

1、性质

1、如图

10、二叉树存储结构

1、顺序存储

1、需要维护结点和左、右孩子的关系:

  • 结点编号为n,

  • 则左孩子为2n,

  • 右孩子为 2n+1。

2、最坏情况，深度k且只有k个结点，需要2的k次方-1个存储单元

2、链式存储

1、有二叉链表和三叉链表。

2、对于n个结点的二叉树

  • 二叉链表的空指针为n + 1

  • 三叉链表的空指针为n + 2。

3、二叉树结点包含有数据元素、左子树的根、右子树的根及双亲

11、二叉树遍历

1、先序遍历：根左右

2、中序遍历：左根右

3、后序遍历：左右根

4、层序遍历：从上到下、从左往右依次遍历

5、通过序列构造二叉树必须有中序序列

12、平衡二叉树与二叉排序树

1、平衡二叉树

1、二叉树的任意一个结点的左右子树高度之差的绝对值不超过1

2、如果是完全二叉树就一定是平衡二叉树，叶子结点一定满足

2、二叉排序树（二叉查找树）

1、特性

  • 根节点大于左子树的所有结点

  • 小于右节点所有的关键结点

  • 左右子树也是一颗二叉排序树

2、 中序遍历得到的序列是有序序列

13、最优二叉树（哈夫曼树）

1、概念

1、哈夫曼树中权值越大的结点离根结点越近，权值越小的结点离根结点越远。

2、哈夫曼树只有度为0和度为2的结点，没有度为1的结点。

3、n个权值构造的哈夫曼树具有2n-1个结点（总结点）。

2、wpl最小的二叉树

1、给定n个权值作为n个叶子节点，构造一棵二叉树，若该树的带权

路径长度(wpl)达到最小，称这样的二叉树为最优二叉树，也称赫夫

曼树。

2、赫夫曼树是带权路径长度最短的树，权值较大的节点离根较近。

3、例子

路径在一棵树中，从一个节点往下可以达到的孩子或孙子节点之间的路径
路径长度通路中分支的数目。若规定根节点的层数为1，则从根节点到第L层节点的路径长度为 L-1
节点的权若将树中节点赋给一个有某种意义的数值，则这个数值称为该节点的权
节点带权路径长度节点的带权路径长度为从根节点到该节点之间的路径长度与该节点的权的乘积

3、构造最优二叉树（不唯一但是wpl是一样的）

1、从前往后找两个权值最小的，

2、小左大右算（求和，然后构造新的树）完加入末尾

3、权值相同，从前往后

4、只有度为0跟2的结点，总个数为:2n-1

4、哈夫曼编码

1、定长编码

  • i like like like java do you like a java // 共40个字符（包括空格）

2、不定长编码

  • 统计每个字符出现的次数。

  • 按照各个字符出现的次数进行规定编码，原则是出现的次数越多时，则编码越小。 例如:空格出现了9次，编码为0 （空格出现最多次，所以编码最小），其它依次类推。

i like like like java do you like a java

  • 次数统计

dyujvolkeia空格
111222444559
1、构造哈夫曼编码

1、我们直接构造哈夫曼树

2、然后我们左子节点为0,右子节点为1

3、使用的是贪心策略

2、压缩比

1、（等长编码-哈夫曼编码）/等长编码

2、等长编码x ： 2^x>几个字符，就是几位

3、哈夫曼编码：几位*出现频率

3、例子

14、线索二叉树

1、为了保存结点在任一序列中的前驱和后继信息，利用空指针域来存储

15、图

1、基本术语

1、补充

  • n个顶点

  • 路径：到达经过了几条边，就是几个路径

  • 带权图：就是边上带有权值

  • <v1,v2,v3>：这个是有向图

  • (v1,v2,v3)：这个是无向图

16、邻接矩阵和链接表

1、邻接矩阵

1、邻接矩阵更适合存储稠密图（边数很多的图）

2、完全图（每个顶点都和剩余的顶点有一条边）更适合采用邻接矩阵存储

3、有向图是不对称的，行是出度，列是入度 e个非零个数

4、无向图的是对称的，第i行(列)就是顶点的度 2e非零个数

5、如图

2、邻接表（邻接链表）

1、邻接表更适合存储稀疏图（边数很少的图）

2、无向图采用邻接表存储有2e个表结点（e为边数）

3、有向图采用邻接表存储有n+e个表结点（n为结点数，e为边数）

4、如图

5、方便理解

17、图的遍历

1、从某个顶点出发，访问所有顶点，只访问一次的过程

2、公式

1、深度优先遍历

1、首先都会走邻接的结点，就一直往下走

2、如果走到最后一个邻接结点，就会回溯，往回找，邻接结点，直到所有结点都走完

3、可以理解为栈（因为递归是栈实现的）

4、序列不唯一

5、一条路都到黑

6、例子

2、广度优先遍历

1、使用队列对图进行广度优先遍历

2、例子

18、拓扑排序

1、AVO网（有向无环图）

1、顶点Vi到顶点Vj有一条有向路径，则顶点Vi是Vj的前驱

2、<Vi,Vj>则Vi是Vj的直接前驱，Vj是Vi的直接后继

可能存在Vi到Vj的路径，一定不存在Vj到Vi的路径

3、如图

2、拓扑排序

1、在网中选择一个入度为0的顶点且输出它

2、从网中删除该顶点及与该顶点有关的弧

3、重复上两步，直到网中不存在入度为0 的顶点为止

4、例子

19、查找

1、查找表示有同一类型的数据元素构成的集合。

2、关键字是数据元素的某个数据项的值，一个就是主关键字，多个是次关键字。给关键字，找到就是查找成功，失败就是空指针

3、静态查找：顺序查找、折半（二分查找）、分块查找

4、动态查找：二叉排序树、平衡二叉树、B_树、哈希表

5、顺序查找成功的平均查找长度：n+1/2

6、二分查找法

  • 要求序列有顺序（递增或递减）要求顺序存储

  • 平均查找长度:log2(n+1)-1

  • 最多是[log2n]+1 向下取整

1、哈希表

1、哈希函数，将关键字映射到空间去，这一过程叫哈希造表或散列，存储的地址为哈希地址或散列地址

2、冲突就是不同关键字具有相同哈希函数值，映射同一个地址了，它们两个为同义词

3、冲突是不可避免的，只能尽量的避免

1、哈希表构造方法

  • 除留取余法，H(key)=key%m=地址

  • m一般取接近n(n个元素)但不大于n的质数

  • 尽可能使用关键字的所有组成部分都能起作用

2、哈希key冲突处理

1、开放地址法

  • Hi=(H(key)%di)%m(表长) 线性探测法

2、二次探测法

  • 1、-1、4、-4、9、-9…k²、-k²

3、哈希表的查询

1、取决因素:哈希函数、处理冲突的方法、哈希表的装填因子a

2、a=表中装入的记录数/哈希表的长度

3、a越小，冲突可能性就越小，反之同理。

2、堆

1、大顶堆 ki>=k2i和k2i+1

2、小顶堆 ki<=k2i和k2i+1

3、可以根据二叉树的顺序存储来画图 学会如何构造大(小)顶堆

3、排序

1、将相应的关键字。经过排序满足了递增(递减)关系

2、内部排序：排序记录全部存放在内存中

3、外部排序

4、归位的排序（交换一次位置就不变的）：简单选择排序，堆排序， 快速排序(分治算法)

5、不归位的排序：直接插入排序，归并(分治)

6、计数排序适合于序列中只有0-9的数字，统计每个数的个数

标签：结点,排序,递归,复杂度,算法,二叉树,数据结构,节点
From： https://blog.csdn.net/m0_57809109/article/details/143455417

相关文章

  • BFS和DFS算法全面解析【算法入门】
    1.前言和树的遍历类似，图的遍历也是从图中某点出发，然后按照某种方法对图中所有顶点进行访问，且仅访问一次。但是图的遍历相对树而言要更为复杂。因为图中的任意顶点都可能与其他顶点相邻，所以在图的遍历中必须记录已被访问的顶点，避免重复访问。根据搜索路径的不同，我们可以将遍......
  • Redis的ZSet底层数据结构，ZSet类型全面解析
    文章目录一、ZSet有序集合类型1.1简介1.2应用场景1.3底层结构1.4ZSet常用命令二、ZSet底层结构详解2.1数据结构2.2压缩列表ZipList2.3跳表详解2.3.1跳表是什么（what）2.3.2跳表怎么做的（how）2.3.3为什么需要跳表（WHY）/跳表高效的动态插入和删除2.3.4ZSet中的跳表2.4什么时候采......
  • Matlab 基于贝叶斯算法优化Transformer结合支持向量机回归(Bayes-Transformer-SVM)
    基于Bayes-Transformer-SVM多变量回归预测（多输入单输出）贝叶斯算法(BO/Bayes)优化参数为自注意力机制头数、正则化系数、学习率！你先用你就是创新！！！1.程序已经调试好，无需更改代码替换数据集即可运行！！！数据格式为excel！2.评价指标包含：RMSE、R2、MSE、MAE、MBE、MAPE、RPD。3.Tran......
  • 数据结构模拟题[十]
    数据结构试卷（十）一、选择题(24分)1．下列程序段的时间复杂度为（）。i=0，s=0；while(s<n){s=s+i；i++；}(A)O(n1/2)(B)O(n1/3)(C)O(n)(D)O(n2)2．设某链表中最常用的操作是在链表的尾部插入或删除元素，则选用下列（）存储方式最节省运算时间。(A)单向链表(B)单向循......
  • 代码随想录算法训练营第十一天|leetcode150. 逆波兰表达式求值、leetcode239. 滑动窗
    1leetcode150.逆波兰表达式求值题目链接：150.逆波兰表达式求值-力扣（LeetCode）文章链接：代码随想录视频链接：栈的最后表演！|LeetCode：150.逆波兰表达式求值哔哩哔哩bilibili自己的思路：这是一道有思路，但是思路并不多的题目，就是我会觉得是先将数据进行添加，然后对于符号通过......
  • 代码随想录算法训练营第十五天|leetcode110. 平衡二叉树、leetcode257.二叉树的所有路
    1leetcode110.平衡二叉树题目链接：110.平衡二叉树-力扣（LeetCode）文章链接：代码随想录视频链接：后序遍历求高度，高度判断是否平衡|LeetCode：110.平衡二叉树_哔哩哔哩_bilibili1.1视频看后的思路1.1.1完整的代码就是不断判断，对其数据存储，其实突然发现每道题思路真的都很像，就......
  • 雪花算法生成唯一id的工具类
    maven依赖包<dependency><groupId>org.apache.commons</groupId><artifactId>commons-lang3</artifactId><version>3.9</version></dependency>&......
  • 【算法】记忆化搜索
    [!TIP]一种剪枝算法，优化运算效率，减少冗余计算基本内容入门例子[P1028[NOIP2001普及组]数的计算]([P1028NOIP2001普及组]数的计算-洛谷|计算机科学教育新生态)题目要求：输入n，输出一共可以构造多少个数列，要求数列的第i不能超过第i-1个数的一半示例：输入6，只能输......
  • 机器学习算法在金融信贷风控模型中的应用毕业论文【附数据】
    ......
  • 【笔记/模板】A*算法
    A*算法定义A*搜索算法（\(\text{A*searchalgorithm}\)）是一种在图形平面上，对于有多个节点的路径求出最低通过成本的算法。它属于图遍历（英文：\(\text{Graphtraversal}\)）和最佳优先搜索算法（英文：\(\text{Best-firstsearch}\)），亦是BFS的优化，用到了启发式搜索的思维。启发式搜索（......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99