数据结构
模板类封装(2)——顺序栈和链式栈
c++ 语言，链栈实现 实验内容：
编程实现栈的如下功能：
（1）建立一个长度为 n 的顺序栈，元素类型可自行定义，并输出栈中各元素值。
（2）将数据元素 e 入栈，并输出入栈后的顺序栈中各元素值。
（3）将顺序栈中的栈顶元素出栈，并输出出栈元素的值和出栈后顺序栈中各元素值…
模板类封装(1)——单链表
加入了 ReverseList 函数，逆转单链表操作 改了个 bug，逆转链表时特判一个结点的情况
又改了 N 个 bug，特判空链表的情况
试试模板类加上数据结构
肯定还是会有遗漏的地方的，欢迎指正
不多说，上代码
ps是 c++11 特性，使用时需注意
Copy
templ…
数据结构学习笔记＜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。通常，我们把这种顶点表示活动…
MOOC浙大数据结构课后题记录——PTA数据结构题目集(全)
原博指路：MOOC 浙大数据结构课后题记录 ——PTA 数据结构题目集 (全) 本博客是为了记录学习数据结构时做的题集，若代码有疏漏欢迎指出！
也相当于是一个数据结构的总结了～
ps：因为已经学过 c++ 了所以都用 c++ 写了，但也有很多 c 语言的东西。
MOOC 传送门…
图论——解决最小生成树问题(Kruskal算法&Prim算法)
上周末的蓝桥杯省模拟赛时最后一题是一道最小生成树的题目，因为恰好在慕课上刚看到这个地方，所以现学了 Prim 算法，解决了这个题目 (大概)，赛后就打算多琢磨琢磨这一类题目。题目链接 最小生成树问题，是指给定无向图 G=(V,E)，连接 G 中所有点，且边集是 E 的子集的树称为…
数据结构学习笔记＜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…
数据结构学习笔记＜2＞ 堆栈
一、堆栈的抽象数据类型描述 类型名：堆栈（Stack）
数据对象集：一个有 0 个或多个元素的有穷线性表
操作集：长度为 MaxSize 的堆栈 S∈Stack, 堆栈元素 item∈ElementType
1. 生成空堆栈，其最大长度为 MaxSize;
Stack…
广义表、多重链表初接触
一、广义表 是线性表的推广
对于线性表而言，n 个元素都是基本的单元素
广义表中，这些元素不仅可以使单元素也可以是另一个广义表
Copy
> typedef struct GNode *GList; struct GNode {
> int Tag; //标志域…
数据结构学习笔记＜1＞ 线性表
一、线性表的抽象数据类型描述 类型名：线性表（List）
数据对象集：线性表示 n (>=0) 个元素构成的有序序列 (a1,a2,……,an)
操作集：线性表 L∈List, 整数 i 表示位置，元素 X∈ElementType
二、顺序表
1. 定义
Copy
struct…