这是一篇数据结构的学习笔记，记录一下一些常见数据结构的概念。

1. 什么是数据结构

数据结构是以某种形式将数据组织在一起的集合，它不仅存储数据，还支持访问和处理数据的操作。
即：数据结构 = 数据存储 + 数据操作

2. 什么是算法

数据结构是数据存储的方式，而算法就是处理数据的方法，数据结构是数据存储的方式，而算法就是处理数据的方法。

3. 时间复杂度和空间复杂度

3.1 时间复杂度

算法的基本操作重复执行的次数是模块 n 的某一个函数 f(n)，用 大O时间复杂度表示法 记做：T(n)=O(f(n))

计算时间复杂度：

1. 先找出算法的基本操作
2. 然后根据相应的各语句确定它的执行次数
3. 再找出 T(n) 的同数量级
4. 找出后，f(n) = 该数量级
5. 若 T(n)/f(n) 求极限可得到一常数c
6. 则时间复杂度 T(n) = O(f(n))

计算时间复杂度的原则：

• 只关注循环执行次数最多的一段代码
• 加法法则：总复杂度等于量级最大的那段代码的复杂度。即便这段代码循环 10000 次、100000 次，只要是一个已知的数，跟 n 无关，照样也是常量级的执行时间。当 n 无限大的时候，就可以忽略。
• 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

常见的时间复杂度：
常见的时间复杂度有： O(1)、O(n)、O(logn)、O(nlogn)、O(n²)、O(n³)、O(n^k)、O(2ⁿ)、O(n!)

• O(1)

  O(1) 只是常量级时间复杂度的一种表示方法，并不是指只执行了一行

• O(logn)、O(nlogn)

  在对数阶时间复杂度的表示方法里，我们忽略对数的“底”，统一表示为 O(logn)。

• O(m+n)、O(m*n)

  m 和 n 是表示两个数据规模。我们无法事先评估 m 和 n 谁的量级大，所以我们在表示复杂度的时候，就不能简单地利用加法法则，省略掉其中一个。
  我们需要将加法规则改为：T1(m) + T2(n) = O(f(m) + g(n))。但是乘法法则继续有效：T1(m)*T2(n) = O(f(m) * f(n))。

3.2 空间复杂度

一个程序的空间复杂度是指运行完一个程序所需内存的大小。

一个算法所需的存储空间用f(n)表示。
S(n)=O(f(n))
其中n为问题的规模，S(n)表示空间复杂度。

4. 线性结构

线性结构是n个数据元素的有序（次序）集合，它有下列几个特征：

1. 集合中必存在唯一的一个"第一个元素"；
2. 集合中必存在唯一的一个"最后的元素"；
3. 除最后元素之外，其它数据元素均有唯一的"后继"；
4. 除第一元素之外，其它数据元素均有唯一的"前驱"。

4.1 线性表

线性表是一个含有n≥0个结点的有限序列，对于其中的结点，有且仅有一个开始结点没有前驱但有一个后继结点，有且仅有一个终端结点没有后继但有一个前驱结点，其它的结点都有且仅有一个前驱和一个后继结点。

一般地，一个线性表可以表示成一个线性序列：k1，k2，…，kn，其中k1是开始结点，kn是终端结点。

4.1.1 线性表的顺序表示和实现

如果第一个元素的在内存上的地址为a1，每个元素占用的空间是l，那么第n个元素的地址就是a1+(n-1) x l。

只要确定了第一个元素的地址，那么我们可以对线性表中的任一元素随机存取。

4.1.2 线性表的顺序表示和实现（链表）

线性表的顺序存储结构是逻辑位置和物理位置都相邻，而链式存储结构是逻辑位置相邻，但物理位置不一定相邻，相比顺序存储结构，它不能随机存取，但在插入和删除操作时不需要移动元素，大大提高了增加和删除元素的效率。

线性链表/单链表

通常链式存储结构会有一个个结点组成，结点中包含两个域一个是数据域，一个是指针域，数据域中存储数据，指针域中存储下一个后继元素的地址，如下图所示，这一个个结点组成链表，也称线性链表或单链表。

单链表的逻辑结构图：

循环链表

循环链表的特点是最后一个结点的指针指向头结点，形成一个环。

双向链表

双向链表的特点是结点中多了一个指向前驱元素的指针。

4.2 栈和队列

其实栈和队列也是线性表，只是它们是操作受限的线性表。

4.2.1 栈

栈是只能在表尾进行插入或删除操作的线性表，通常我们称表尾端为栈顶，表头端为栈底。

它是一种先进后出的线性表，既只能在表尾端插入元素，称为入栈，也只能在表尾端删除元素，称为退栈。

栈既然也是线性表，那么它也有顺序存储结构和链式存储结构两种表示方法。

4.2.2 队列

队列刚好和栈相反，它是一种先进先出的线性表，只能在一端插入元素，在另一端删除元素。

允许插入元素的一端称为队尾，允许删除元素的一端称为队头。

队列也一样有顺序和链式存储结构两种表示方法。

5. 非线性结构

5.1 树

树是由n（n>=1）个有限节点组成一个具有层次关系的集合。

一种树形结构：

树的结构：

• 节点的度：一个节点含有的子树的个数称为该节点的度；
• 叶节点或终端节点：度为0的节点称为叶节点；
• 非终端节点或分支节点：度不为0的节点；
• 双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；
• 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；
• 兄弟节点：具有相同父节点的节点互称为兄弟节点；
• 树的度：一棵树中，最大的节点的度称为树的度；
• 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
• 树的高度或深度：树中节点的最大层次；
• 堂兄弟节点：双亲在同一层的节点互为堂兄弟；
• 节点的祖先：从根到该节点所经分支上的所有节点；
• 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。
• 森林：由m（m>=0）棵互不相交的树的集合称为森林；

5.1.1 二叉树

二叉树的特点是一个结点的直接子节点最多只能有两个，并且有左右之分。

二叉树中有种常见的称为完全二叉树的结构，它的特点是除最后一层外每一层的结点数为 $$2i-1$$：

最后一层的结点数若不满足 $$2^i-1$$，那么最后一层的结点是自左向右排列的：

堆

堆是一种经过排序的完全二叉树，其中任一非叶子节点的值均不大于（或不小于）其左孩子和右孩子节点的值。

最大堆和最小堆是二叉堆的两种形式。
最大堆：根结点的键值是所有堆结点键值中最大者。

最小堆：根结点的键值是所有堆结点键值中最小者。

二叉排序树

叉排序树又称二叉查找树，亦称二叉搜索树。

它或者是一棵空树；或者是具有下列性质的二叉树：

1. 若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
2. 若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
3. 左、右子树也分别为二叉排序树；

平衡二叉树

平衡二叉树又被称为AVL树。

它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

哈夫曼树

哈夫曼树也称最优二叉树，它是带权路径长度最小的二叉树。

哈夫曼树的构造步骤如下：
假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：

1. 将w1、w2、…、wn看成是有n 棵树的集合(每棵树仅有一个结点)；
2. 在集合中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
3. 从集合中删除选取的两棵树，并将新树加入集合；
4. 重复第2、第3步，直到集合中只剩一棵树为止，该树即为所求得的哈夫曼树。

5.2 图

5.1 什么是图

5.2 图的表示和实现

表示图通常有四种方法–数组表示法、邻接表、十字链表和邻接多重表。

5.3 图的表示和实现

通常图的遍历有两种：深度优先搜索和广度优先搜索。

深度优先搜索是树的先根遍历的推广，它的基本思想是：从图G的某个顶点v0出发，访问v0，然后选择一个与v0相邻且没被访问过的顶点vi访问，再从vi出发选择一个与vi相邻且未被访问的顶点vj进行访问，依次继续。如果当前被访问过的顶点的所有邻接顶点都已被访问，则退回到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点w，从w出发按同样的方法向前遍历，直到图中所有顶点都被访问。

广度优先搜索是树的按层次遍历的推广，它的基本思想是：首先访问初始点vi，并将其标记为已访问过，接着访问vi的所有未被访问过的邻接点vi1,vi2,…, vin，并均标记已访问过，然后再按照vi1,vi2,…, vin的次序，访问每一个顶点的所有未被访问过的邻接点，并均标记为已访问过，依次类推，直到图中所有和初始点vi有路径相通的顶点都被访问过为止。

5.4 最小生成树

一个有n个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有n个结点，并且有保持图连通的最少的边。最小生成树可以用kruskal（克鲁斯卡尔）算法或Prim（普里姆）算法求出。

5.5 拓扑排序

拓扑排序简单地说，就是在有向图中，想访问一个顶点需要先访问它的所有前驱顶点。它的执行步骤为：

1. 在有向图中选一个没有前驱的顶点输出。
2. 从图中删除该顶点和所有以它为尾的弧。 重复上述步骤直到所有顶点都输出或者图中不存在无前驱的顶点为止，后者说明图中有环。

5.6 最短路径问题

寻找图（由结点和路径组成的）中两结点之间的最短路径。