c++
链式前向星存图、二分图匹配之匈牙利算法 模板&分析（存用）
参考博客：链式前向星 -- 最通俗易懂的讲解、算法讲解：二分图匹配【图论】、趣写算法系列之 -- 匈牙利算法、匈牙利算法与增广路径 暑假整的忘了发 2333
@TOC
1. 是什么
如果说邻接表是不好写但效率好，邻接矩阵是好写但效率低的话，前向星就是一个相对中庸的数据结构…
模板类封装(2)——顺序栈和链式栈
c++ 语言，链栈实现 实验内容：
编程实现栈的如下功能：
（1）建立一个长度为 n 的顺序栈，元素类型可自行定义，并输出栈中各元素值。
（2）将数据元素 e 入栈，并输出入栈后的顺序栈中各元素值。
（3）将顺序栈中的栈顶元素出栈，并输出出栈元素的值和出栈后顺序栈中各元素值…
模板类封装(1)——单链表
加入了 ReverseList 函数，逆转单链表操作 改了个 bug，逆转链表时特判一个结点的情况
又改了 N 个 bug，特判空链表的情况
试试模板类加上数据结构
肯定还是会有遗漏的地方的，欢迎指正
不多说，上代码
ps是 c++11 特性，使用时需注意
Copy
templ…
状压dp——模板&分析&例题（存用）
状压讲解部分参考博客状压 DP 详解（位运算） 这里是引用
状压 dp，即将状态压缩成 2 进制来保存，如矩阵中将一行的状态压缩成一个二进制串，如 dp [S][v] 中，S 可以代表已经访问过的顶点的集合，v 可以代表当前所在的顶点为 v。S 代表的就是一种状态…
数据结构学习笔记＜9＞ 散列查找
1. 概念引出 编译处理中对变量的管理：动态查找问题
利用查找树进行？—— 两个变量名（字符串）比较效率不高
将字符串转换为数字，再处理？—— 即为散列查找的思想
已知的几种查找方法：
顺序查找 O (N)
二分查找（静态查找） O (log~2~N)
二叉搜索树 O…
归并排序循环实现（存用）
递归的归并排序是很占空间和时间的，而非递归算法就不一样了，额外空间复杂度最少为 O (N)。 陈越姥姥的慕课里就讲得很清楚～戳这儿
这里就直接上代码 + 注释了
Copy
#include <iostream>
#include <cstdio>
#include <queue…
数据结构学习笔记＜8＞ 排序
1. 概念定义 AOV 网络
例如，假定一个计算机专业的学生必须完成图 3-4 所列出的全部课程。从图中可以清楚地看出各课程之间的先修和后续的关系。如课程 C5 的先修课为 C2，后续课程为 C4 和 C6。通常，我们把这种顶点表示活动…
博弈论——模板&分析（存用）
描述 基本的斐波那契博弈（Fibonacci Game）描述如下：
有一堆石子，两个顶尖聪明的人玩游戏，先取者可以取走任意多个，但不能全取完，之后每次可以取的石子数至少为 1，至多为对手刚取的石子数的 2 倍。约定取走最后一个石子的人为赢家，求必败态。
结论
当且仅当总石子…
MOOC浙大数据结构课后题记录——PTA数据结构题目集(全)
原博指路：MOOC 浙大数据结构课后题记录 ——PTA 数据结构题目集 (全) 本博客是为了记录学习数据结构时做的题集，若代码有疏漏欢迎指出！
也相当于是一个数据结构的总结了～
ps：因为已经学过 c++ 了所以都用 c++ 写了，但也有很多 c 语言的东西。
MOOC 传送门…
图论——解决最小生成树问题(Kruskal算法&Prim算法)
上周末的蓝桥杯省模拟赛时最后一题是一道最小生成树的题目，因为恰好在慕课上刚看到这个地方，所以现学了 Prim 算法，解决了这个题目 (大概)，赛后就打算多琢磨琢磨这一类题目。题目链接 最小生成树问题，是指给定无向图 G=(V,E)，连接 G 中所有点，且边集是 E 的子集的树称为…
动态规划学习笔记（1）
记录一下慕课学习的笔记，以及例题代码 一。递归到动规的一般转化方法
递归函数有 n 个参数就定义一个 n 维的数组， 数组的下标是递归函数参数的取值范围。
这样就可以从边界值开始逐步填充数组，相当于计算递归函数值的逆过程。eg：例题 1 数字三角形
二。动规解题的一般思路
1…
数据结构学习笔记＜7＞ 图
1. 什么是图 表示 “多对多” 的关系，包含了：
一组顶点：通常用 V (Vertex) 表示顶点集合
一组边：通常用 E (Edge) 表示边的集合
无向边是顶点对：(v，w) ∈ E，其中 v，w∈V
有向边 <v,w> 表示从 v 指向 w 的边 (单行线)
不考虑重…
数据结构学习笔记＜6＞ 堆与哈夫曼树与并查集
1. 堆是什么 堆（Heap), 是一个可以被看做一棵完全二叉树的数组对象，有以下性质：
任意节点的值是其子树所有结点中的最大值 / 最小值（有序性）
堆总是一棵用数组表示的完全二叉树。
2. 最大堆的操作函数
定义
Copy
typedef struct…
RMQ问题——线段树
上篇说到 RMQ 问题可以用 ST 表算法处理，但需要在线修改的时候，线段树是更好的选择。 如图，很明显线段树是个二叉搜索树
要注意的点如下：
线段树用数组存储，数组空间简单的就一般开到原数组的 4*n 倍（准确的说是将 n 向上扩充到 2 的幂次方然后乘 2，如 5->8-…
数据结构学习笔记＜5＞ 二叉搜索树与平衡二叉树
1. 二叉搜索树是什么 二叉搜索树（BST，Binary Search Tree), 又称二叉排序树或二叉查找树，是一棵二叉树，可以为空，当不为空时满足以下性质：
非空左子树的所有键值小于其根结点的键值
非空右子树的所有键值大于其根结点的键值
左、右子树都为二叉搜索树
2…
RMQ问题——ST表算法
ST 表是什么 ST 表是一个用来解决区间最值问题查询的算法
它用O (nlogn) 复杂度预处理，可以实现 O (1) 复杂度的查询。
缺点：无法支持在线修改
模板题：ST 表 - 洛谷
1. 预处理
用一个二维数组 dp [i][j] 表示下标为 i ~ i + 2^j^ -…
数据结构学习笔记＜4＞ 二叉树
一、什么是树 1. 树的定义
树（Tree）：n（n≥0）个结点构成的有限集合。
当 n=0 时，称为空树；
对于任一棵非空树（n>0）, 它具备以下性质：
树中有一个称为 “根（Root）” 的特殊结点，用 r 表示。
其余结点可分为 m（m>0）个互不相交的有限集 T1…
数据结构学习笔记＜3＞ 队列
一、队列的抽象数据类型描述 类型名：队列（Queue）
数据对象集：一个有 0 个或多个元素的有穷线性表
操作集：长度为 MaxSize 的堆栈 Q∈Queue, 队列元素 item∈ElementType
1. 生成长度为 MaxSize 的空队列
Queue…