数据结构的四种基本逻辑
分类1：线性结构与 非线性结构
线性结构：链表，队列，对，堆栈...
非线性结构：树，图
分类2：四种基本逻辑结构
集合
线性表
树
图
存储结构种类
顺序存储结构
链式...
索引...
散列...
顺序存储结构
用一组连续存储单元按照顺序存储
比如数组
链接存储结构
类似于链表，数据元素之间通过指针链接
索引存储方式
存储节点信息的时候附加建立存储表，相当于目录
散列存储方式
根据节点关键字计算出该节点存储地址
线性表
首先，有一类共性问题：有线性序列的组织和管理，我们用线性表来存储线性结构数据
线性表的关键信息：
同种数据类型构成的有序序列
元素个数称为表长度
没有元素称为空表
始末称为表头、表尾
主要含有
数据对象集：n个元素构成的有序序列
操作集：假设 线性表L属于list类型，i表示位置，元素属于数据类型elementtype。
对表的主要操作：
一、线性表的存储实现（利用数组）
思路：定义一个结构体指针，自定义数据类型。内部元素有数组和一个末尾元素的地址。（这就跟上面的衔接起来，这跟链表的节点好像）那个数组是用来存储个数组。
栈的顺序存储实现
一维数组单方向堆栈
栈的顺序存储通常由一个一维数组和一个记录栈顶的位置变量组成。
在这里一维数组代表栈内元素，top代表栈顶元素位置。
注意：top=-1的时候代表空栈，top=0代表栈内有一个元素。
（1）入栈：检验知否堆栈满，如果没满就把元素堆入栈，top值+1。
（1）入栈：先判断堆栈满了没。如果没满，要往第一个堆栈里添加元素，就top1++。要往第二个堆栈添加元素就top2--。
（2）出栈： 先判断是否空栈。再分别进行操作。
表达式在程序中的存储
我们常见的表达式一般是中缀表达式，儿在程序中一般转换为后缀表达式进行存储。
如何把中缀表达式转换为后缀表达式： 数字读下来，遇到运算符号就存储在堆栈中，每一次比较堆栈中运算符的优先级，读入整个表达式之后按运算级最高的进行计算。
不同部分转换方式：
运算数直接输出
左括号压入堆栈
右括号：将栈顶的运算符弹出并输出，直到遇到左括号（出战，不输出）
运算符：若优先级大于栈顶运算符，则压栈；否则将栈顶运算符弹出并输出。再比较新的栈顶运算符，直到该运算符大于栈顶运算符优先级为止，然后将该运算符压栈。
全部处理完毕后把栈中运算符一并输出。
注意：
单独的括号优先级其实比加号低，双括号的运算级是最高的。
读到完整的双括号之后，双括号联通中间的内容都被运用并且取出。之后再继续读入
整个式子就像俄罗斯方块一样从上到下消去。
广义表
广义表是线性表的推广
对于线性表而言，n个元素都是基本的氮元素
广义表中，这些元素不急可以是单元素也可以是另一个广义表。
如图，这是广义表的形象图
树的初识
树：n（n>=0）个节点构成的有限集合；当n=0时称为空树；树有一个称为“根”的特殊节点，其余节点可以分为m个互不相交的有限集，其中每一个集合本身又是一棵树，称为原来的“子树”。
树的一些基本定义
节点的度：节点的子树个数
树的度：树的所有节点中最大的度数
叶节点：度为0的节点
父节点：有子树的节点是其子树的根节点的父节点
兄弟节点：具有统一父节点的节点彼此称为兄弟节点。
路径和路径长度：路径所包含边的个数。
祖先节点：沿着树根到某一节点路径上的所有节点都是这个节点的祖先节点。
树的深度：树中所有节点最大层次是这颗树的深度。
树的表示
二叉树：一个节点有三个东西，一个内容，两个指针。
一些特殊的二叉树
斜二叉树（相当于链表，只有左/右支）
完美二叉树（满二叉树）：每个节点的子节点都满2
完全二叉树：每一行从左往右没有空的，但是不一定是完美二叉树。（如下图1是2不是)
树的遍历
一般有四种方法：
先序遍历：根 - 左子树 - 右子树
中序遍历：左子树 - 根 - 右子树
后序遍历：左子树 - 右子树 - 根
层序遍历：从上到下，从左到右
先序遍历
利用一种递归的思想实现遍历
先检验是否为空（即BT）
然后访问左侧，再访问右侧
先序遍历过程图解
中序遍历
中序遍历过程图解
后序遍历
后序遍历过程图解
遍历总结
所有遍历方法都是使用递归的方法
只有先序遍历是从上往下的，其他遍历方法都是从下往上的
如图，×代表先序遍历路径，⭐代表中序遍历，▲代表后序遍历。
二叉树的遍历（非递归）
递归的是指其实还是用堆栈，每一次把数据存储在堆栈中，等判断条件达到终止之后再倒着输出。这样一来，如果需要处理的数据非常庞大，仍然存在空间占用过大的问题，就像前面讲的一样，递归虽然是个效率高的方法，但是存储空间消耗很大，就像飞机一样，虽然速度快但是代价昂贵，而且每次运输数量有限。
中序遍历
遇到一个节点把这个节点压栈，然后沿着这个节点便利左支。
左支遍历结束之后从栈顶弹出这个节点病情访问他。
再按照这个方法遍历右支。
层序遍历
大概原理：（必须遵从这个）
非空左子树的所有值小于根节点值
非空右子树的所有值大于根节点值
左右子树都是二叉搜索树
搜索二叉树
搜索效率可以通过计算平均查找长度（ASL）来判断，其中完全二叉搜索树查找效率最搞，斜二叉树查找效率最低。
（ASL计算方法：就是查找每个元素需要遍历的长度相加，除以结点个数。）
为了提高二叉树查找效率，需要平衡二叉树。
（平衡二叉树（AVL树）：平衡因子=|左子树高度-右子树高度|）
调整方法
1.
2.
调整模式主要有四种：rr，ll，rl，lr。（right，left）
一个核心方法就是找到破患者和被破坏这区域附近的大约3个结点（这三个节点的asl指数都不是0），把asl数剧中的系欸但作为根，把asl小的放左侧，大的放右侧。
概述/引入
又名最优二叉树，树的总路径长度最短
可以说是从堆引入的。堆的作用是构造最大堆和最小堆实现挑选最值删除的东西。
原理：出现频率较高的数占空间小，出现频率较低的数占空间更大。从而实现不压缩数据且节省空间的一种存储方式。
哈夫曼树
引：堆的构造是在所有数字中挑选两个最大/最小的数字合并，再继续挑选继续合并。而哈夫曼树是在数据中挑选两个出现频率最低的数进行合并。
在数据中挑选两个出现频率最低的数进行合并
接着选频率最低的数和上一个父结点进行合并得到新的父结点（父结点的值是两个子结点的和）
一直合并完成所有元素
所有元素必须是叶子结点，保证没有歧义（二义性）
这棵哈夫曼树左侧路径都标0，右侧都标1
哈夫曼编码特点
字符只在叶结点上。（作用是避免二义性。保证每一个参数都没有后缀只有前缀（路径上的数就代表前/后缀)
左支是0，右支是1
如此一来，路径所组成的数就是该字符对应的编码。
在数据中挑选两个出现频率最低的数进行合并
注意我们需要的字符都放在叶结点上。
这样编码可以很大几率让频率高的字符编码更短。
计算路径长度
要想计算最优二叉树中某个结点权重的路径长度，方法是每个叶子结点的（该结点权重*到根节点路径数量）相加总和。因为哈夫曼树我们认为叶子结点的值本身就是一种频率，所以结点值就是权重，所以哈夫曼树总路径长度一般是每个（叶子结点值*到根节点长度）相加总和。
因哈夫曼树构建方法就是从第频率到高频率进行合并，所以最长的路径总是对应最低的频率，得到的总路径长度总是最短的，也就是最优的。
集合
并查集：“并”把两个集合并在一起；“查”查某个元素属于哪个集合。
具体作用：现在有很多个集合，每个集合又有很多个元素。我们想查一个元素，需要找这个元素在哪个集合的什么位置，或者想把两个集合合并为一个集合。
（该图只是形象的比喻一下，真正的存储方式并不是这样）
子结点指向父结点，这种方法与二叉树有所不同，这个叫做双亲表示法。
我们把一个集合看作一个树状结构，一个根节点何以被大于两个元素指向，根节点和叶结点都是集合中的元素。
这个并查集存储的就是各个集合的根节点的指针。
集合的表示
每个元素可以用一个结构体类型数组进行表示。
每个结构体内有两个东西：数据域；整型数字（这个元素的父节点在数组中的位置，相当于指针）
具体如何存储呢
data是元素内容；parent是每个元素对应的集合的根节点（如果该元素本身就是根节点，其根节点就用-1表示）；下标是各个元素的标签（就是数组下标），因为元素不一定是数字，我们经常用元素下标来查找对应内容。
某几个数组下标代表的元素是根节点，这些根节点的根节点值是-1。而非根节点的元素的根节点值是对应根节点的数组下标。
查找某个元素所在的集合
（每个元素都有一个数组下标，根节点本身也拥有一个数组下标。）
第一遍循环，按照数组下标挨个寻找对应的元素。如果找到了就退出循环并返回数组下标，如果没找到就返回-1（结束这个函数）。
第二次循环，判断条件是相应数组下标的根节点值是否大于0，如果大于0，就让数组下标等于这个根节点值，这个根节点值代表的就是其根节点的数组下标。
集合的并运算
干啥的：告诉你两个元素，你要把这两个元素对应的集合并起来。
程序框架：找到两个元素各自的根节点；判断根节点是否相等；如果相等就不管；如果不相等就把其中一个根节点并入另一个根节点（把一个根节点的parent值改成另一个根节点对应的数组下标数）
这样一来“树”会长高一层，随着合并的进行，这个数可能会越来越高。为了尽可能提高效率，我们尽量把小的集合并入大的集合中。
这样一来，还要判断需合并的两个集合的大小。
为了记录集合中元素个数，我们可以使用一个非常巧妙的方法，把根节点parent值记为其中元素个数的负数。
图
一些基本概念
无向图/有向图：即途中路径是否有方向。
网络：图的路径上有数字，这些数字称为权重。当图上由权重的时候就叫做网络。
顶点集和边集，一般由二元组表示，和离散一样，但是这里的图不考虑自回路和平行边。
稀疏图：点多边少，矩阵中有大量的0
路径：两点之间结点的集合。路径长度就是路径中边的数量（如果是网络就是所有路上的权重之和）。
简单路径：两点之间路径上所有顶点都不同。
回路：起点等于终点的路径。
连通图：图中任意两点均连通
连通分量：无向图的极大连通子图
强连通：有向图中顶点v和w之间存在双向路径，则称v和w是强连通。
不一定是平行边（事实上程序中不存在平行边），可以通过不同路径，如下图A可以到B，B可以到A
图在程序中表示(邻接矩阵，邻接表）
使用二维数组，两个下标初始化都是结点数-1，接着用两个下标分别表示两个顶点，如果两顶点之间由边则赋值为1，无边则赋值为0。
（假如有9个结点）
邻接矩阵
阐述：邻接矩阵是图的一种存储方式，一般用数组进行存储。有向图一般用二维数组，无向图可以用一维数组。
特点：
左上到右下的数字全是0，因为不允许自回路。
以上面那个对角线为对称轴，如果是无向图，其两侧情况一致，因为两节点之间肯定是情况一致的。这样一来就发现矩阵有一般空间都浪费了，下方进行优化
无向图优化
用一维数组存储。
直接在红色框里从第一行从左到右存储，数组下标是序号，数组值是0/1。
这个方法虽然节省了空间，但是让寻找哪两个点变难了，没办法嘛。
如果是网络的话，把数组值定义为权重就行了。
邻接表
阐述：是图的一种存储方式，利用链表实现。用邻接矩阵存储稀疏图会造成空间浪费，链表的方式解决了这个弊端。
其实不止这两种表示图的方式，用什么方式取决于要解决什么问题。
图的遍历
主要有两种方法：
深度优先搜索DFS，广度优先搜索BFS
深度优先搜索：在一个结点处，望向所有边，优先前往未经过的结点。如果所有邻接点都经过了，就优先原路返回，不会直接去出口。一直返回，指导退回入口。
这个程序很像堆栈。使用递归的方式点亮邻接点，如果这样一来，经过的结点就会按照顺序被压入，如果没有为点亮的邻接点就返回（弹出）上一个。
广度优先搜索BFS：类似于队列的方式实现。把一个起始结点压入队列，弹出这个起始结点，压入这个起始节点的所有邻接点，再挨个弹出这些邻接点，暗处每个邻接点的时候，压入这个邻接点的邻接点（已经压入过队列的不再重复压入），直到压入过所有结点。（下图是伪码描述）
*Enqueue入队
*V算是起始结点的载体，后面会被赋值为弹出结点
*Dequeue出队
*Q队列
