数据结构

1线性表

1.1顺序表

1.2链表

​ 定义链表，定义结点

1.3栈

​ 后进先出。

1.4队列

​ 先进先出、后进后出。队首指针永远指向数据，队尾指针永远指空。

​ 循环队列：首尾相接的队列，一般认为队列中少一个元素为满队列。

2.1串

​ 串就是字符版的线性表，有顺序结构和链式结构。与线性表不同之处在于串可以连续几个元素连接以后再指针。

2.2数组

​ 一维数组是线性结构；

​ 数组压缩：相同元素压缩。***哪些数组可以压缩？***对角矩阵、对称矩阵、稀疏矩阵、三角矩阵。

2.3广义表

​ 相对于线性表中（每一项不能有结构，只能有单纯元素），广义表中每一项元素都可以有自己的结构，意味着广义表中可以有表作为元素。广义表中有表头与表尾，**统一规定：**第一个元素为表头，剩下的元素为表尾。

3树

3.1树的概念

​ 每个结点只有一个父节点、同一层结点不可能相连接。

• **结点的度：**结点拥有的子树数量；

• **树的度：**树上各节点度的最大值；

• 叶子结点：度为0的结点，又称为终端节点；

• 森林：m棵互不相交的树的集合。

3.2二叉树的概念

• 二叉树每个节点至多有两棵子树；

• 二叉树子树有左右之分，次序不能颠倒；

• 二叉树中即使只有一棵子树也要区分左右。

二叉树的性质

​ i层结点数为 $2^{i-1}$;

​ i层结点总数为$2^k-1$;

几个重要公式：

边m与结点n关系：n = m + 1;

m = $n_0$*0+$n_1$*1+$n_2$*2$=$$n_0$+$n_1$+$n_2-1$;

$n_2$=$n_0-1$

3.3完全二叉树

​ 叶子节点优先集中到最左边。

对于有n个节点的完全二叉树，那么深度为**$【log_2n-1】$**;第i个结点：

• i=1，结点就是根；i>1,结点就是$\frac{i}{2}向下取整$；
• 2i >n,结点无孩子；2i=n，结点只有左孩子n；
• 2i+1>n,结点无右孩子；2i+1=n，结点只有右孩子n

3.4二叉树的存储结构

​ 顺序存储：主要用于完全二叉树，如果不是完全二叉树，那么浪费空间较大；

​ 链式存储：每个节点存在至少两个孩子指针

3.5树的遍历：

• 先序遍历：根左右

• 中序遍历：左根右

• 后序遍历：左右根

• 层级遍历：每一层每一层遍历

3.6哈夫曼树（最优树）

​ 权值：叶子节点权重乘以层数求和。

​ 哈夫曼树是一种特殊的二叉树构造哈夫曼树的方法：把权值小的放在底层。（每次选两个）

4图

4.1图的定义与术语

​ G=（V,E),其中V是顶点集，E是边集。图不可能为空，至少有一个顶点。

• 有向图：边有向，改称弧<$v_i,v_j$>。

完全无向图：每个顶点之间有边连接；

完全有向图：每个顶点之间有两个方向相反的弧形连接。

度数：无向图度数之和等于边数的两倍；有向图入度之和等于出度之和等于边数。

连通图：对于无向图，至少存在一条路径使任意两个结点相连接，那么就是连通图；

弱连通图：对于有向图，忽略方向，至少存在一条路径使使任意两个结点相连接；

强连通图：对于有向图，不忽略方向，至少存在一条路径使使任意两个结点相连接。

4.2图的存储结构

• 邻接矩阵
• 邻接表：各个结点以顺序表形式存储，结点连接的其他结点通过链表存储。

4.3图的遍历

• 深度优先遍历：起始点不同，有不同的遍历路径
• 广度优先遍历（使用队列实现遍历）

4.4图的应用

​ 拓扑排序：输出入度为0的结点，然后删去该结点以及连接路径，继续重复。直到所有结点全都输出一次。如果还有节点没有输出，说明该AOV网络存在环，不能构成拓扑排序。

5概念

5.1时间复杂度

当作次数，运行次数之和再取大O。

对于循环，如果没有指定循环的次数n，那么就是循环n次，如果指定了循环次数，那么就是指定的循环次数，为常数。**特别的，如果循环中出现了指数级增长，需要考虑能运行多少次，最后可能会出现对数形式，那么取大O就是O($logn$)。

5.2空间复杂度

​ 衡量占用空间量和输入数据规模之间的关系。

• 定义的一般变量，空间复杂度就是O（1）；
• 定义了长度为n的数组或者链表，空间复杂度就是O（n)；
• 定义了二维数组，那么空间复杂度就是O（$n^2$)。

6哈希表

相当于一个字典，给一个值找出相应的单词。

6.1实现方式

数组+链表（每个数组都指向链表）

6.2原理

附带一个键值对，键用来寻找（遍历）、值用来插。因此同时利用了数组和链表的优点。