type
status
date
slug
summary
tags
category
icon
password
这里是为大家整理的数据结构算法模板，如果有错误和不完整的地方，可以在下方评论区提出
408算法题概述
得分要点
1、会写结构定义（没有就自己写上）
2、写清楚解题的算法思想
3、描述清楚算法实现
4、最后写出时间和空间复杂度
关于改卷
1、改卷老师不会上机试
2、老师改的是扫描卷
图文结合帮助改卷老师理解，有利于给分。
考试手写代码注意事项：
1、命名应当规范（变量、函数命名要见文知意）
2、格式要标准（换行、缩进、对齐）
3、注释要写清楚，让阅卷老师快速读懂
算法答题特点：
408中的算法题主要涉及基本的数据结构（线性表和树），但也可能会涉及图。题目形式多样，但通常需要使用常见算法（排序算法、查找算法、双指针技巧、树的遍历、DFS、BFS）来解决问题或情景。
算法题基本都是在现有的算法模板下按照题目的意思进行变形得到的
算法题答题技巧：
题源来自LeetCode，一般是LeetCode的改编，一般相当于LeetCode的中等偏下难度的算法题，需要参加机试的同学可以顺便带掉408算法题，如果目标院校没有机试408算法需要单独准备，如果算法想拿高分题还是要刷题的，如果不想刷题，暴力解（几层for循环）也能拿到一半分，刷题是很耗时间的，复习时间紧的建议放弃，想拿满分或者高分的建议刷题。
目前机试推荐CCF和PAT，一般大院校机试官网会有明确要求，这个题量相比LeetCode少很多，贴近408，如果考浙大及相关院校（安利下杭电，2023考研将PAT或CCF纳入参考）需要PAT，PAT考纲可以参考晴神的算法笔记，过一遍算法笔记大概半个月，练一遍PAT甲级题库大概一个月，如果有浙大复试需要且有钱的也可以在PAT教育超市购买后练习这几年的PAT真题和浙大复试机试题，适合备考时间比较充足的考生。
以上内容仅作为参考，不作为复习建议
数据结构推荐书单
官方推荐教材：
推荐辅导用书：
拓展教材：
复习时应该以王道等辅导书为主，扩展教材只是有利于深入理解408的相关知识点，只推荐学有余力的情况下进行阅读。如果时间紧迫，把王道给吃透就够了！
关注微信公众号【LUCEN】，回复【408】，即可领取上方资料 如果您需要本算法模板的pdf版，在公众号回复【500002】即可
PS：没错，这是一条广告，但是绝对是你看过的最良心的一条广告 ‼️
如果你讨厌广告，可以划拉到下面，但是我真的建议你花几分钟时间去了解一下「知能行考研数学」‼️
如果你基础不好，做题没有思路，同样的题目反复做错，做题能力一直提升不上去，就使用知能行考研数学！
下面就是知能行的官网，你可以上下滑动，看一看这个网站的介绍，没错，就像大家看到的一样，知能行已经帮助40万+考生轻松的突破考研数学
如果你看了知能行官网的介绍，就会了解到，知能行考研数学是通过人工智能算法扫描我们知识体系中的薄弱点，直达病灶，然后循序渐渐的帮助我们吃透知识点，复习效率是传统备考的10倍以上。
知能行在基础复习，计算能力训练以及对抗考研反押题上都有很丰富的经验非常值得一试！
点击下方链接试用👇👇👇，很快就可以测出你的考研数学水平和薄弱点，试一下，只需要几分钟，了解自己真实的考研数学备考水平‼️
数据结构算法模板
以下算法模板主要是帮助大家理解
1.线性表的结构体定义
1.1顺序表的结构体定义
顺序表的结构体类型包含两个成员：一个数组data用于存储顺序表的元素，一个整型变量length用于记录当前顺序表的长度。其中，MAXSIZE是一个预定义的常量，表示顺序表的最大长度。在实际使用中，可以根据需要修改MAXSIZE的值。
1.2单链表的结构体定义
单链表是一种常见的数据结构，用于存储一系列元素。单链表由多个节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。链表的头节点是第一个节点，尾节点是最后一个节点，尾节点的指针指向NULL。
单链表的定义如下：
在这个定义中，我们使用结构体ListNode表示链表节点。这个结构体包含一个整型变量val，表示节点的值，以及一个指向下一个节点的指针next。指针next的类型是struct ListNode*，表示指向另一个ListNode结构体的指针。
使用这个定义，我们可以创建一个链表。例如，以下是一个创建链表的示例：
在这个示例中，我们首先创建了一个头节点，使用malloc函数动态分配内存，创建一个新的节点，并将val赋值为1，将next指针初始化为NULL。然后，创建第一个节点和第二个节点，分别将它们的值设置为2和3，将它们的next指针初始化为NULL。最后，将头节点的next指针指向第一个节点，将第一个节点的next指针指向第二个节点。
这样，我们就创建了一个包含三个节点的链表，节点的值分别为1、2、3。
1.3双链表的结构体定义
双链表是一种常见的数据结构，与单链表不同的是，每个节点包含两个指针，一个指向前一个节点，一个指向后一个节点。双链表的头节点是第一个节点，尾节点是最后一个节点，头节点的前一个节点指针和尾节点的后一个节点指针都指向NULL。
双链表的定义如下：
2.顺序表的基本操作
2.1初始化顺序表：
2.2求指定元素位置：
这个函数接受一个指向顺序表的指针L和一个元素elem作为参数，然后遍历顺序表中的元素，查找是否有与elem相等的元素。如果找到了，则返回该元素在顺序表中的位置，否则返回-1。
2.3插入数据元素：
这个函数接受一个指向顺序表的指针L、一个插入位置pos和一个插入元素elem作为参数，然后判断插入位置是否合法，以及顺序表是否已满。如果插入位置不合法或顺序表已满，则返回0，否则将pos及其后面的元素后移一位，将新元素插入到pos位置，然后将长度加1，最后返回1表示插入成功。
2.4按元素值查找
这个函数接受一个指向顺序表的指针L和一个元素elem作为参数，然后遍历顺序表中的元素，查找是否有与elem相等的元素。如果找到了，则返回该元素在顺序表中的位置，否则返回0。注意，这里返回的位置是从1开始计数的，而不是从0开始计数的。
2.5删除数据元素
这个函数接受一个指向顺序表的指针L和一个删除位置pos作为参数，然后判断删除位置是否合法。如果删除位置不合法，则返回0，否则将pos后面的元素前移一位，然后将长度减1，最后返回1表示删除成功。
2.6顺序表的元素逆置
2.7删除下标i-j的元素
这个函数接受一个指向顺序表的指针L、一个起始下标i和一个结束下标j作为参数，然后判断删除范围是否合法。如果删除范围不合法，则返回0，否则将j+1及其后面的元素前移j-i位，然后将长度减少j-i+1，最后返回1表示删除成功。
2.8Partition操作
顺序表的Partition操作是指将一个顺序表分成两个部分，使得左边的部分都小于等于某个值，右边的部分都大于等于某个值。以下是一种Partition操作的实现：
3.单链表的基本操作
3.1初始化单链表
3.2尾插法建立单链表
3.3头插法建立单链表
3.4合并递增单链表
在这个函数中，我们使用了一个虚拟头节点dummy，以便在合并链表时更方便地处理头节点。我们使用tail指针来追踪新链表的尾节点，然后遍历两个链表，将较小的节点添加到新链表中。最后，如果其中一个链表还有剩余节点，我们将剩余节点添加到新链表的尾部。最后，我们返回新链表的头节点。
需要注意的是，如果两个链表都为空，我们应该返回NULL。另外，如果链表中有重复的节点，我们可以将它们都添加到新链表中。
3.5将2个递增单链表合并成递减单链表
这个代码的作用是将两个递增有序链表合并成一个递减有序链表，并且使用头插法将新节点插入到结果链表的头部。函数的参数是两个指向链表头结点的指针，函数执行后，链表Lb将被释放，而链表La则成为合并后的递减有序链表。
3.6查找元素并删除
这个函数使用了头结点，分别定义了两个指针p和pre，分别指向第一个结点和头结点。然后遍历单链表，如果找到了要删除的结点，则将前驱结点的指针域指向后继结点，释放要删除的结点的内存空间，最后结束函数。如果遍历完整个单链表都没有找到要删除的结点，则输出提示信息。
3.7对于一个递增单链表，删除其重复的元素
这个函数使用了头结点，分别定义了两个指针p和q，分别指向第一个结点和下一个结点。然后遍历单链表，如果下一个结点的值与当前结点的值相同，则释放下一个结点的内存空间，直到找到一个不重复的结点。最后将当前结点的指针域指向下一个不重复的结点，然后指向下一个结点，继续遍历单链表。
3.8删除单链表中的最小值
这个函数使用了头结点，分别定义了四个指针p、pre、min_p和min_pre，分别指向第一个结点、头结点、最小值结点和最小值结点的前驱结点。然后遍历单链表，如果找到了比当前最小值更小的结点，则更新最小值结点和最小值结点的前驱结点。最后将最小值结点的前驱结点的指针域指向最小值结点的后继结点，然后释放最小值结点的内存空间。
3.9单链表的原地逆置
下面是一个可以运行的测试用例：
3.10判断链表是否有环（快指针和慢指针）
算法思想：
- 使用快慢指针fast和slow来遍历链表。
- fast指针每次移动2步,slow指针每次移动1步。
- 在遍历链表的过程中,如果fast和slow指针相遇,说明链表有环。
- 为了避免特殊情况,先判断了链表为空或只有1个节点的边界情况。
- 初始化slow为head,fast为head->next,fast指针领先slow一个节点。
- while循环的条件仅判断fast,因为fast会先到达尾部。
- 如果fast和slow相遇,直接return true表示有环。
- 如果fast遍历完还没与slow相遇,说明无环,return false。
- 这样,通过快慢指针的速度差,可以节省遍历链表的次数,很巧妙地判断链表是否有环。
实际可运行的代码：
3.11逆序打印单链表中的节点
这个函数使用了递归的方法，先判断单链表是否为空，如果不为空，则递归输出单链表中除头结点之外的结点，然后输出当前结点的数据域。
3.12查找链表中倒数第k个节点
这个函数使用了双指针的方法，首先判断单链表是否为空或 k 是否小于等于 0，如果是，则返回 NULL。然后让 q 先走 k - 1 步，然后 p 和 q 同时向后走，直到 q 走到了最后一个结点，此时 p 指向的就是倒数第 k 个结点。如果 q 走到了 NULL，则说明 k 大于单链表的长度，返回 NULL。
3.13单链表的删除结点操作
单链表在某处删除节点的操作需要先找到要删除位置的前一个节点，然后将前一个节点的next指针指向后一个节点，释放要删除的节点的内存。以下是在单链表中间删除节点的操作示例：
4.双链表的基本操作
4.1双链表插入节点
这个算法首先指向双链表中的第一个结点，然后遍历双链表，找到要插入的位置。如果插入位置无效，则输出错误信息并返回。否则，创建一个新结点，将数据存入新结点的数据域，将新结点的前一个节点指针指向前一个节点，将新结点的后一个节点指针指向后一个节点，如果后一个节点存在，则将后一个节点的前一个节点指针指向新节点，最后将前一个节点的后一个节点指针指向新节点。这样就完成了向双链表中插入一个新节点的操作。
4.2双链表删除节点
这个算法首先指向双链表中的第一个结点，然后遍历双链表，查找值为 x 的结点。如果找到了该结点，则将前一个节点的后一个节点指针指向后一个节点，如果后一个节点存在，则将后一个节点的前一个节点指针指向前一个节点，最后释放被删除的结点。如果没找到该结点，则输出错误信息并返回。
5.栈和队列的结构体定义
5.1顺序栈的定义
顺序栈使用静态数组实现，因此结构体中包含一个静态数组和一个栈顶指针。其中，静态数组的大小可以根据实际情况进行调整，这里定义为 MAXSIZE。
5.2链栈节点定义
链栈节点包含一个数据域和一个指向下一个节点的指针。
5.3顺序队列的定义
顺序队列使用静态数组实现，因此结构体中包含一个静态数组、一个队头指针和一个队尾指针。其中，静态数组的大小可以根据实际情况进行调整，这里定义为 MAXSIZE。
5.4链队定义
链队使用链表实现，因此结构体中包含一个队头指针和一个队尾指针。队列中的每个元素都是一个节点，包含一个数据域和一个指向下一个节点的指针。
6.顺序栈的基本操作
6.1顺序栈的初始化
这个函数接受一个指向栈的指针作为参数，将栈顶指针初始化为 -1，表示栈为空。
6.2判断栈空
6.3进栈出栈
这个代码中，push() 函数接受一个指向栈的指针和一个整数作为参数，如果栈已满，则输出错误信息并返回，否则将栈顶指针加 1，将数据存入栈顶指针所指向的位置。pop() 函数接受一个指向栈的指针作为参数，如果栈为空，则输出错误信息并返回，否则取出栈顶元素，栈顶指针减 1，最后返回栈顶元素。
7.链栈的基本操作
7.1链栈的初始化
这个函数接受一个指向栈的指针作为参数，将栈顶指针初始化为空，表示栈为空。
7.2判断栈空
这个函数接受一个指向栈的指针作为参数，如果栈顶指针为空，表示栈为空，返回 1，否则返回 0。
7.3进栈代码
7.4出栈代码
8.顺序队列的基本操作
8.1顺序队列的初始化
这个函数接受一个指向队列的指针作为参数，将队头指针和队尾指针初始化为 0，表示队列为空。
8.2判断队空
8.3进队算法
这个函数接受一个指向队列的指针和一个整数作为参数，如果队列已满，则输出错误信息并返回，否则将数据存入队尾指针所指向的位置，队尾指针加 1。
8.4出队算法
这个函数接受一个指向队列的指针作为参数，如果队列为空，则输出错误信息并返回，否则取出队头元素，队头指针加 1，最后返回队头元素。
9.链队的基本操作
9.1链队的初始化
这个函数接受一个指向队列的指针作为参数，将队头指针和队尾指针初始化为空，表示队列为空。
9.2判断队空算法
这个函数接受一个指向队列的指针作为参数，如果队头指针为空，表示队列为空，返回 1，否则返回 0。
9.3入队算法
这个函数接受一个指向队列的指针和一个整数作为参数，首先创建一个新的节点，将数据存入新节点的数据域，然后判断队列是否为空，如果为空，则将新节点作为队头节点，否则将新节点插入到队尾节点之后，最后更新队尾指针。
9.4出队算法
这个函数接受一个指向队列的指针作为参数，如果队列为空，则输出错误信息并返回，否则保存队头结点，取出队头元素，将头结点指向下一个结点，如果队列中只有一个元素，则更新队尾指针，释放原队头结点的内存，最后返回队头元素。
10.串的结构体定义
10.1定长顺序存储表示
这个结构体包含两个成员，一个是存储串的字符数组，另一个是串的长度。由于是定长顺序存储，所以需要预先定义一个最大长度。
10.2变长分配存储表示
这个结构体包含三个成员，一个是指向存储串的字符数组的指针，另一个是串的长度，还有一个是串的容量。由于是变长分配存储，所以需要记录串的容量。
11.串的模式匹配算法
11.1简单模式匹配算法
简单串的简单模式匹配算法是一种基础的字符串匹配算法，它的思想是从文本串的第一个字符开始匹配，如果当前字符匹配成功，则继续匹配下一个字符，否则回溯到上一个匹配的位置，重新从下一个位置开始匹配。如果模式串已经遍历完，说明匹配成功，返回匹配的起始位置，否则匹配失败，返回 -1。这个算法的时间复杂度为 O(m*n)，其中 m 和 n 分别是文本串和模式串的长度。
这个函数接受两个指向字符数组的指针作为参数，分别表示文本串和模式串。算法从文本串的第一个字符开始匹配，如果当前字符匹配成功，则继续匹配下一个字符，否则回溯到上一个匹配的位置，重新从下一个位置开始匹配。如果模式串已经遍历完，说明匹配成功，返回匹配的起始位置，否则匹配失败，返回 -1。
11.2KMP算法
求next数组的代码
这个函数接受两个参数，一个是指向模式串的指针，另一个是指向next数组的指针。算法从模式串的第一个字符开始遍历，如果当前字符匹配成功，则将next数组的下一个元素的值设为j+1，否则回溯到上一个匹配的位置，继续匹配。如果j等于-1，或者当前字符匹配成功，则将i和j都加1，否则将j更新为next[j]。最后，函数返回next数组。
求nextval数组的代码
在KMP算法中，nextval数组是next数组的改进版，它的作用是在模式串与文本串匹配失败时，尽可能减少回溯的次数，从而提高匹配效率。nextval数组的计算方法与next数组类似，只是在计算过程中，当模式串中的某个字符与文本串中的某个字符匹配失败时，不是直接回溯到next[j]的位置，而是回溯到nextval[j]的位置。nextval数组的计算方法如下：
这个函数接受两个参数，一个是指向模式串的指针，另一个是指向nextval数组的指针。算法从模式串的第一个字符开始遍历，如果当前字符匹配成功，则将nextval数组的下一个元素的值设为j+1，否则回溯到上一个匹配的位置，继续匹配。如果j等于-1，或者当前字符匹配成功，则将i和j都加1，否则将j更新为nextval[j]。如果p[i]等于p[j]，则说明在j位置匹配失败，需要继续回溯，因此将nextval[i]的值设为nextval[j]。最后，函数返回nextval数组。
KMP算法
KMP算法是一种高效的字符串匹配算法，它的核心思想是利用已经匹配过的信息，尽可能减少模式串与文本串的匹配次数。具体来说，KMP算法通过预处理模式串，得到一个next数组，用于指导匹配过程中的回溯操作。next数组的含义是：当模式串中的某个字符与文本串中的某个字符匹配失败时，模式串应该回溯到哪个位置重新开始匹配。KMP算法的时间复杂度为O(m+n)，其中m和n分别是模式串和文本串的长度。
下面是可实际运行的代码和测试用例：
12.二叉树
12.1二叉树的节点定义
二叉树的节点定义通常包含三个部分：节点值、左子节点和右子节点。具体实现时，可以定义一个名为
TreeNode的结构体，包含三个成员变量：val表示节点的值，left表示左子节点的指针，right表示右子节点的指针。以下是一个示例代码：链式存储结构中,每个节点包含:
- val:存储节点的值
- left:指向左子节点
- right:指向右子节点
相比数组存储,链式存储的优点是:
- 不需要预先确定二叉树的最大大小
- 可以充分利用计算机内存,不会有大量空闲内存
- 插入和删除节点时,只需要修改相应指针,操作效率高
链式存储的缺点是:
- 无法按数组下标直接访问节点,需要从根节点遍历
- 存储空间存在碎片,链表指针需要额外空间
需要通过递归或迭代的方式遍历链式存储的二叉树,来访问每个节点。
总体来说,链式存储结构灵活高效,非常适合构建二叉树这种非顺序数据结构,是二叉树最常用的存储方式之一。
12.2线索二叉树的结点定义
其中，
data表示节点的数据，ltag表示左标志，rtag表示右标志，lchild表示左子节点的指针，rchild表示右子节点的指针。ltag和rtag用于标记节点的左右子节点是否为线索，如果为1则表示是线索，否则表示是子节点。线索二叉树是一种利用二叉树的空指针域来存放指向该节点在某种遍历方式下的前驱和后继节点的指针的二叉树。13.二叉树的遍历算法
13.1先序遍历（递归）
递归实现的二叉树先序遍历算法的思想是:
- 如果二叉树为空,直接返回
- 打印根节点值
- 递归遍历左子树
- 递归遍历右子树
递归先序遍历的关键在于对左右子树的递归处理。具体分析:
- 首先检查二叉树是否为空,如果为空直接返回
- 然后打印根节点的值(访问根节点)
- 对根节点的左子树递归调用先序遍历函数,遍历左子树
- 再对根节点的右子树递归调用先序遍历函数,遍历右子树
- 左子树和右子树的遍历仍然按照打印根节点、遍历左子树、遍历右子树的顺序进行
- 这样通过递归不断重复先序遍历的过程,实现了对整个二叉树的先序遍历
递归先序遍历遵循根左右的访问顺序,通过递归调用实现遍历整棵树,是一个非常经典和高效的二叉树遍历算法。
实际可运行的例子：
13.2先序遍历（非递归）
这是一个使用非递归方式实现二叉树的先序遍历的代码实现。在这个算法中，我们使用一个人工栈来模拟递归调用栈，从而实现非递归遍历。具体实现步骤如下：
- 定义一个大小为
maxSize的人工栈Stack，以及一个指针变量p和一个整型变量top，用于记录栈顶位置。
- 判断二叉树是否为空，如果不为空，则将根节点入栈。
- 循环执行以下操作，直到栈为空：
- 出栈一个节点，并完成一次访问。
- 如果该节点的右子树不为空，则将右子树入栈。
- 如果该节点的左子树不为空，则将左子树入栈。
以下是完整的代码实现：
在上面的代码中，我们首先定义了一个大小为
maxSize的人工栈Stack，以及一个指针变量p和一个整型变量top，用于记录栈顶位置。然后，我们判断二叉树是否为空，如果不为空，则将根节点入栈。接着，我们循环执行以下操作，直到栈为空：出栈一个节点，并完成一次访问；如果该节点的右子树不为空，则将右子树入栈；如果该节点的左子树不为空，则将左子树入栈。最后，我们完成了二叉树的先序遍历。实际可运行的例子：
13.3中序遍历（递归）
递归实现二叉树的中序遍历算法思路如下:
- 如果二叉树为空,直接返回
- 递归遍历左子树
- 打印根节点值(访问根节点)
- 递归遍历右子树
递归中序遍历的关键也在于对左右子树的递归处理。具体分析:
- 首先检查二叉树是否为空,如果为空直接返回
- 递归调用中序遍历函数遍历根节点的左子树
- 左子树遍历完成后,打印根节点的值(访问根节点)
- 再递归调用中序遍历函数遍历根节点的右子树
- 左右子树的遍历仍遵循中序遍历的逻辑,打印左子树、根节点、右子树
- 通过递归不断重复中序遍历过程,完成整棵树的中序遍历
递归中序遍历遵循左根右的访问顺序,通过递归调用实现遍历全树,是中序遍历的典型实现。
13.4后序遍历（递归）
递归实现二叉树的后序遍历,算法思想是:
- 如果二叉树为空,直接返回。
- 递归遍历左子树。
- 递归遍历右子树。
- 打印根节点值(访问根节点)。
递归后序遍历的关键也在于对左右子树的递归处理:
- 先检查二叉树是否为空,如果为空直接返回。
- 递归调用后序遍历函数遍历根节点的左子树。
- 再递归调用后序遍历函数遍历根节点的右子树。
- 在左右子树遍历结束后,打印根节点的值(访问根节点)。
- 左右子树的遍历顺序与后序遍历一致,左右子树遍历结束后才访问根节点。
- 通过递归不断重复后序遍历过程,完成整棵树的后序遍历。
递归后序遍历遵循左右根的访问顺序,通过递归调用实现遍历全树,是后序遍历的一种常用实现方式。
13.5后序遍历（非递归）
在这个算法中，我们使用一个人工栈来模拟递归过程。首先将根节点入栈，然后循环执行以下操作：
- 如果当前节点不为空，则将其入栈，并遍历其左子树。
- 如果当前节点为空，则取出栈顶元素，并判断其右子树是否为空或者已经访问过。如果是，则访问当前节点，并将其出栈；否则，遍历其右子树。
这样就可以实现二叉树的非递归后序遍历了。
实际可以运行的代码：
根据上面生成的二叉树，进行非递归后序遍历的结果应该是：
4 2 5 3 1。具体的遍历过程如下：
- 将根节点1入栈。
- 取出栈顶元素1，将其左右子节点2和3入栈。
- 取出栈顶元素3，将其值输出，并将其标记为已访问。
- 取出栈顶元素2，将其左右子节点4和5入栈。
- 取出栈顶元素5，将其值输出，并将其标记为已访问。
- 取出栈顶元素4，将其值输出，并将其标记为已访问。
- 取出栈顶元素1，由于其右子节点3已经访问过，因此将其值输出，并将其标记为已访问。
- 遍历结束。
因此，输出的结果应该是：
4 2 5 3 1。13.6层序遍历
层序遍历是一种广度优先遍历，按照从上到下、从左到右的顺序遍历二叉树的所有节点。具体的实现可以使用队列来实现，遍历过程如下：
- 将根节点入队。
- 当队列不为空时，执行以下操作：
- 取出队头元素，访问该节点。
- 如果该节点有左子节点，将其左子节点入队。
- 如果该节点有右子节点，将其右子节点入队。
- 遍历结束。
具体的实现可以参考以下代码：
下面是可以实际运行的代码：
层序遍历过程如下：
- 将根节点1入队，队列为{1}。
- 取出队头元素1，访问该节点，将其左子节点2和右子节点3入队，队列为{2, 3}。
- 取出队头元素2，访问该节点，将其左子节点4和右子节点5入队，队列为{3, 4, 5}。
- 取出队头元素3，访问该节点，发现其没有子节点，队列为{4, 5}。
- 取出队头元素4，访问该节点，发现其没有子节点，队列为{5}。
- 取出队头元素5，访问该节点，发现其没有子节点，队列为空，遍历结束。
因此，层序遍历的结果为：
1 2 3 4 5。14.二叉树的其他算法
14.1递归求WPL
WPL（Weighted Path Length）是指二叉树中所有叶子节点的带权路径长度之和，其中带权路径长度是指从根节点到该节点的路径长度乘以该节点的权值。递归求WPL的方法是通过遍历二叉树的所有节点，计算每个叶子节点的带权路径长度，然后将它们相加得到WPL。
具体的实现可以参考以下代码：
其中，
root是二叉树的根节点，depth表示当前节点的深度。调用该函数时，初始深度为0。14.2转成中缀表达式
中缀表达式：又称中序表达式,是一种常见的算术表达式表示方式。中缀表达式的特点是:
- 运算符置于两个运算对象的中间。
- 表达式遵循常规的运算顺序,不需要额外的括号来确定运算顺序。
例如:
- A+B
- A*B+C/D
- A+(B*C-(D/E+F)*G)
上述表达式都属于中缀表达式,运算符处于两个运算对象中间,默认运算顺序为先乘除后加减,符合我们通常的运算习惯。相比之下,前缀表达式(Prefix)将运算符置于前面,后缀表达式(Postfix)将运算符置于后面。中缀表达式直观易读,是最常见的表达式表示方式。大多数编程语言都直接支持中缀表达式的解析和求值。
将二叉树转换为中缀表达式的过程可以通过中序遍历来实现。中序遍历的顺序是左子树、根节点、右子树，因此我们可以先递归遍历左子树，然后访问根节点，最后递归遍历右子树。在访问根节点时，我们需要根据根节点的类型（操作符或操作数）来决定输出的内容。
例如将下面的二叉树转换成中缀表达式：
可运行的代码如下：
15.图的存储结构
15.1邻接矩阵的结点定义
这段代码定义了一个邻接矩阵类型
MGraph，包含了图的节点信息和边信息。具体来说，MGraph包含以下几个成员：edges：二维数组，表示图的邻接矩阵，其中edges[i][j]表示节点i和节点j之间的边的权值。
n：整数，表示图的节点数。
e：整数，表示图的边数。
vex：一维数组，表示图的节点信息，其中vex[i]表示节点i的信息，包括节点编号和其他信息。
15.2邻接表的结点定义
这段代码定义了一个邻接表类型
AGraph，包含了图的节点信息和边信息。具体来说，AGraph包含以下几个成员：adjlist：一维数组，表示图的邻接表，其中adjlist[i]表示节点i的信息，包括节点的值和指向第一条边的指针。
n：整数，表示图的节点数。
e：整数，表示图的边数。
16.图的遍历方式
16.1.深度优先搜索算法（DFS）
在图中的深度优先搜索算法思想是:
- 从一个起始节点出发,首先访问该节点,并标记该节点已访问。
- 查找该节点的所有邻接点,将未访问过的邻接点按某种顺序排列到一个栈中。
- 取栈顶元素作为当前访问节点,重复步骤1和2直到栈为空。
- 如果还有未访问的节点,则选择一个未访问节点作为起始节点,重复步骤1、2、3,直至图中所有节点都被访问。
- 通过栈来维护当前节点信息,指导下一步搜索顺序。
其关键思路是:
- 递归访问起始节点的所有未访问邻接点
- 邻接点入栈 Waiting遍历
- 当前节点访问结束后,从栈顶取出下一个节点
- 利用栈来维护节点顺序
- 重复上述步骤直至所有节点访问结束
通过栈保存节点访问顺序,实现系统有序地深度优先遍历图的所有节点。
实际可运行的代码：
这个测试用例中，我们构造了一个有6个节点、7条边的无向图，并从节点0开始进行深度优先搜索。你可以根据需要修改节点数、边数和边的连接关系，来测试不同的情况。
16.2广度优先搜索算法（BFS）
图的广度优先搜索算法思想是:
- 选择一个起点,访问该节点,并标记已访问。
- 遍历该节点的所有邻接点,将未访问的邻接点入队。
- 从队头取出一个节点,作为当前访问节点。
- 对当前访问节点,进行步骤1和2的处理。
- 重复步骤3和4,直到队列为空。
- 如果还有未访问节点,回到步骤1,直至图中所有节点都被访问。
- 通过队列来维护访问顺序。
其关键思路是:
- 起点入队,标记已访问
- 当前节点访问结束后,其邻接点入队
- 从队头取出下一个节点继续处理
- 利用队列来维护和指导节点访问顺序
- 重复上述步骤直到遍历完图中所有节点
广度优先搜索利用队列机制,实现按层次遍历图的所有节点。
相比深度优先搜索的递归思路,广度优先搜索通过队列层次遍历节点
下面是可运行的代码：
17.最小（代价）生成树
17.1Prim算法
最小生成树Prim算法的步骤如下:
- 选取任意一个结点作为起始结点,标记为已访问。
- 从已访问的结点中找到到其它所有未访问结点的距离中最小的一条边,连接这个未访问结点,标记为已访问。
- 重复步骤2,直到所有结点都被标记为已访问。
- 此时得到的边集合构成了最小生成树。
Prim算法的基本思想是从一个结点开始,不断添加与已访问结点集相连的最小权值的边,直到遍历完所有结点,即可得到最小生成树。
Prim算法的时间复杂度为O(n^2),其中n为图中的结点数。常见的优化方法是使用优先队列存储边信息,可以将时间复杂度降低为O(mlogn),其中m为图中的边数。
你可以按照以下格式输入图的数据进行测试：
其中第一行是结点数和边数，接下来的m行是边的信息，每行包含三个整数u、v、w，表示一条从u到v的边，边权为w。这个测试用例的最小生成树的边权和为7。
17.2Kruskal算法
Kruskal算法是一种用于求解最小生成树的贪心算法。它的基本思想是将所有边按照权值从小到大排序，然后依次加入到生成树中，如果加入一条边会形成环，则不加入这条边。直到生成树中有n-1条边为止，此时生成树就是原图的最小生成树。
Kruskal算法的具体实现步骤如下：
- 将所有边按照权值从小到大排序。
- 初始化一个并查集，每个节点的父节点都是它本身。
- 依次遍历所有边，如果这条边的两个端点不在同一个连通块中，则将这条边加入生成树中，并将这两个端点所在的连通块合并。
- 重复步骤3，直到生成树中有n-1条边为止。
你可以按照以下格式输入图的数据进行测试：
其中第一行是结点数和边数，接下来的m行是边的信息，每行包含三个整数u、v、w，表示一条从u到v的边，边权为w。这个测试用例的最小生成树的边权和为7。
18.最短路径算法
18.1Dijkstra算法
Dijkstra算法是一种用于求解单源最短路径的贪心算法。它的基本思想是从源节点开始，依次找到距离源节点最近的节点，并以此更新其他节点的距离。具体实现步骤如下：
- 初始化距离数组dist和标记数组visited，将源节点的距离设为0，其他节点的距离设为无穷大，标记数组visited中所有元素都为0。
- 从未标记的节点中找到距离源节点最近的节点u，将节点u标记为已访问。
- 遍历节点u的所有邻居节点v，如果节点v未被访问过且从源节点到节点v的距离比当前记录的距离更短，则更新节点v的距离。
- 重复步骤2和步骤3，直到所有节点都被访问过或者没有未标记的节点。
在实现过程中，可以使用一个优先队列来存储未标记的节点，每次从队列中取出距离源节点最近的节点进行更新。这样可以减少遍历的节点数，提高算法效率。
Dijkstra算法的时间复杂度为O(n^2)，如果使用优先队列实现，则时间复杂度可以降为O(mlogn)，其中n为节点数，m为边数。
你可以按照以下格式输入图的数据进行测试：
19.排序算法
19.1快速排序
快速排序的核心思想是分治法,其算法思想可以概括为:
- 从数组中选择一个基准值(pivot),通常选择第一个元素或者最后一个元素。
- 通过一趟排序,将数组分成两个部分,左子数组小于基准值,右子数组大于基准值。这个过程称为分割(partition)。
- 对左右两个子数组递归进行快速排序。
- 递归结束条件是子数组大小为1,则直接返回。
- 递归调用完毕后,整个数组排序完成。
其关键在于分割操作,快速找到数组的中间位置pivot,左边都比pivot小,右边都比pivot大。快速排序通过递归进行分治,每次只需要排序子数组,这保证了它的快速性。平均时间复杂度为O(nlogn),最坏为O(n^2),空间复杂度O(logn)。是原地排序算法之一。
两路快排：
两路快排（Dual-Pivot QuickSort）是快速排序算法的一种变体，它使用两个 pivot 元素来将数组分成三部分，分别是小于第一个 pivot 元素、大于第一个 pivot 元素且小于第二个 pivot 元素、大于第二个 pivot 元素的部分。这个算法的时间复杂度为 O(n log n)，空间复杂度为 O(log n)。
三路快排：
三路快排（Three-Way QuickSort）是快速排序算法的一种变体，它使用三个 pivot 元素来将数组分成四部分，分别是小于第一个 pivot 元素、等于第一个 pivot 元素、大于第一个 pivot 元素且小于第二个 pivot 元素、大于第二个 pivot 元素且小于等于第三个 pivot 元素、大于第三个 pivot 元素的部分。这个算法的时间复杂度为 O(n log n)，空间复杂度为 O(log n)。
19.2归并排序
归并排序的算法思想可以归纳为:
- 把长度为n的输入序列分成两个长度为n/2的子序列;
- 对这两个子序列分别采用归并排序;
- 将两个排序好的子序列合并成一个最终的排序序列。
其核心思路是分治法:
- 分解:递归地将当前序列均分为两个子序列,直到不能再分解(子序列大小为1)。
- 解决:通过合并操作将两个排序好的子序列合并成一个排序序列。
- 合并:重复地合并排序好的子序列,直到最终只有一个排序完毕的序列。
归并排序稳定、时间复杂度为O(nlogn),需要额外O(n)的空间复杂度用于merge操作。它把原问题递归分解为相同但更简单的子问题,递归到不能再分解后,合并排序后的子结果得到最终结果。
19.3冒泡排序
冒泡排序的算法思想是:
- 从第一个元素开始,依次与后续元素进行比较。
- 如果当前元素大于后一个元素,则交换两个元素的位置。
- 对每一个相邻元素都进行同样的操作,这一轮下来,最大的元素就会被交换到最后的位置。
- 对数组重新进行步骤1到步骤3的操作,除了最后一个元素,直到没有任何一对元素需要交换位置。
其关键是通过对相邻元素的比较和交换,让较大的元素往后移,较小的元素往前移。
- 每一轮遍历都让一个最大元素冒到最后的位置。
- 重复此过程,直到数组有序。
冒泡排序的时间复杂度为O(n^2),是一种原地比较交换排序算法。
19.4折半插入排序
折半插入排序的算法思想是:
- 从第一个元素开始,该元素可以认为已经被排序。
- 取出下一个元素,在已经排序的元素序列中从后向前扫描。
- 如果该元素(已排序)大于新元素,将该元素移到下一位置。
- 重复步骤3,直到找到已排序元素小于或者等于新元素的位置。
- 将新元素插入到该位置后。
- 重复步骤2~5。
其实质是一种插入排序,与直接插入排序的区别在于:
- 使用折半查找找到要插入的位置,而不是直接顺序查找。
- 时间复杂度可以降低到O(nlogn)。
折半插入排序引入了折半查找的思想,对直接插入排序进行了改进,降低了时间复杂度,是一种改进后的插入排序算法。
19.5直接插入排序
直接插入排序（Insertion Sort）是一种简单的排序算法，它的基本思想是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增加 1 的有序表。具体实现时，我们从第二个元素开始，将其插入到前面已经排好序的子序列中，直到最后一个元素插入完成，整个序列就排好序了。直接插入排序的时间复杂度为 O(n^2)，空间复杂度为 O(1)。
以下是一个 C 语言版本的直接插入排序实现：
19.6希尔排序
希尔排序（Shell Sort）是一种改进的插入排序算法，它的基本思想是将整个序列分成若干个子序列，对每个子序列进行插入排序，然后逐步缩小子序列的长度，最终将整个序列排序。具体实现时，我们先将整个序列分成若干个子序列，对每个子序列进行插入排序，然后逐步缩小子序列的长度，直到子序列长度为 1，此时整个序列就排好序了。希尔排序的时间复杂度为 O(n log n) ~ O(n^2)，空间复杂度为 O(1)。
以下是一个 C 语言版本的希尔排序实现：
19.7简单选择排序
简单选择排序（Selection Sort）是一种简单的排序算法，它的基本思想是每次从未排序的序列中选择最小的元素，将其放到已排序的序列的末尾，直到整个序列都排好序。具体实现时，我们从第一个元素开始，依次找到最小的元素，将其与第一个元素交换位置，然后从第二个元素开始，依次找到最小的元素，将其与第二个元素交换位置，以此类推，直到最后一个元素排好序。简单选择排序的时间复杂度为 O(n^2)，空间复杂度为 O(1)。
以下是一个 C 语言版本的简单选择排序实现：
19.8堆排序
堆排序（Heap Sort）是一种基于堆的排序算法，它的基本思想是将待排序的序列构建成一个大根堆或小根堆，然后依次取出堆顶元素，直到堆为空，得到的序列就是排好序的序列。堆排序的时间复杂度为 O(n log n)，空间复杂度为 O(1)。
以下是一个 C 语言版本的堆排序实现：
Shiftdown 操作是堆排序算法中的一个重要操作，它用于将一个节点下移，以满足堆的性质。具体来说，Shiftdown 操作会将当前节点与其左右子节点中的最大值进行比较，如果当前节点的值小于最大值，则将当前节点与最大值所在的子节点交换位置，并递归地对交换后的子节点进行 Shiftdown 操作，直到当前节点的值大于等于其左右子节点的值，或者当前节点没有子节点为止
20.二分查找
二分查找的基本思想是：将有序数列分成两部分，取中间位置的数与目标数进行比较，如果中间位置的数等于目标数，返回中间位置；如果中间位置的数小于目标数，将左指针移到中间位置的右边；如果中间位置的数大于目标数，将右指针移到中间位置的左边。在实现过程中，可以使用一个循环来控制左右指针的移动，直到找到目标数或者左指针大于右指针为止。
21.二叉排序树
21.1二叉排序树的节点定义
二叉排序树（Binary Search Tree，简称 BST）是一种特殊的二叉树，它的每个节点都包含一个关键字和两个指针，分别指向左子树和右子树。对于任意一个节点，它的左子树中的所有节点的关键字都小于它的关键字，它的右子树中的所有节点的关键字都大于它的关键字。这个特性使得二叉排序树可以快速地进行查找、插入和删除操作。
这个定义使用了一个结构体
TreeNode 来表示二叉排序树的节点。其中，val 变量表示节点的关键字，left 和 right 分别表示指向左子树和右子树的指针。在这个定义中，我们使用了 struct 关键字来定义结构体类型。21.2二叉排序树的查找算法
这个算法接受一个二叉排序树的根节点
root 和一个关键字 val，并返回二叉排序树中关键字等于 val 的节点。在算法的实现中，我们首先判断当前节点是否为空或者关键字等于 val，如果是，则直接返回当前节点；否则，如果当前节点的关键字大于 val，则递归地在左子树中查找；否则，递归地在右子树中查找。21.3二叉排序树的插入算法
这个算法接受一个二叉排序树的根节点
root 和一个关键字 val，并返回插入关键字后的二叉排序树的根节点。在算法的实现中，我们首先判断当前节点是否为空，如果是，则创建一个新节点，并将关键字 val 赋值给它；否则，如果当前节点的关键字大于 val，则递归地在左子树中插入；否则，递归地在右子树中插入。最后，返回根节点。21.4二叉排序树的构造算法
这个算法接受一个整数数组
arr 和数组的长度 n，并返回构造出的二叉排序树的根节点。在算法的实现中，我们首先定义了一个 insertBST 函数，用于向二叉排序树中插入一个关键字。然后，我们定义了一个 constructBST 函数，用于构造二叉排序树。在这个函数中，我们首先将根节点初始化为 NULL，然后依次将数组中的元素插入到二叉排序树中。最后，返回根节点。推荐文章
以下文章为知乎答主【千葉原】整理
408算法题力扣题源
2009：剑指 Offer 22. 链表中倒数第k个节点
难度：简单，考察单链表、同向双指针。
2010：189. 旋转数组
难度：中等，考察数组的原地翻转。
2011：4. 寻找两个正序数组的中位数
难度：困难，考察二分查找、分块。
2012：160. 相交链表
难度：简单，考察分叉链表及双指针
2013：169. 多数元素
难度：简单，考察摩尔投票法。
2014：1376. 通知所有员工所需的时间
难度：中等，考察带权路径长度WPL的概念以及广度优先遍历BFS或深度优先遍历DFS。
2015：83. 删除排序链表中的重复元素
难度：简单，考察单链表遍历。
2016：未找到对应原题
2017：未找到对应原题
2018：41. 缺失的第一个正数
难度：困难，考察数组的原地标记，技巧性极强。
2019：143. 重排链表
难度：中等，考察链表的原地翻转，交叉连接，快慢指针找中间结点。
- 作者:LUCEN
- 链接:https://lucenczz.top/article/af9dbf29-83b5-417a-ac0a-adbb6e721e02
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
