文章参考：http://c.biancheng.net/data_structure/
文章目录
1. 什么是数据结构
数据结构，直白地理解，就是研究数据的存储方式
数据存储的目的是为了方便后期对数据的再利用，比如我们使用数组存储 {1,2,3,4,5} 是为了后期取得它们的加和值，无缘由的数据存储行为是对存储空间的不负责任。
因此，数据在计算机存储空间的存放，决不是胡乱的，这就要求我们选择一种好的方式来存储数据，而这也是数据结构的核心内容。
数据结构教会我们的绝不仅仅是如何存储 1、2、{a,b,c} 这样简单的数据，而是解决具有复杂关系的大量数据的存储问题。
数据结构是一门学科，它教会我们“如何存储具有复杂关系的数据更有助于后期对数据的再利用”。
2. 数据结构到底学什么
数据结构是学习数据存储方式的一门学科，数据结构大致包含以下几种存储结构：
- 线性表，还可细分为顺序表、链表、栈和队列；
- 树结构，包括普通树，二叉树，线索二叉树等；
- 图存储结构；
2.1. 线性表
线性表结构存储的数据往往是可以依次排列的，就像小朋友手拉手，每位学生的前面和后面都仅有一个小朋友和他拉手，具备这种“一对一”关系的数据就可以使用线性表来存储。
线性表并不是一种具体的存储结构，它包含顺序存储结构和链式存储结构，是顺序表和链表的统称。
2.1.1. 顺序表
顺序表，简单地理解，就是常用的数组，只是换了个名字而已，例如使用顺序表存储 {1,3,5,7,9}
2.1.2. 链表
使用顺序表时，需要提前申请一定大小的存储空间，这块存储空间的物理地址是连续的。
链表则完全不同，使用链表存储数据时，是随用随申请，因此数据的存储位置是相互分离的，换句话说，数据的存储位置是随机的。
为了给各个数据块建立“依次排列”的关系，链表给各数据块增设一个指针，每个数据块的指针都指向下一个数据块（最后一个数据块的指针指向 NULL），就如同一个个小学生都伸手去拉住下一个小学生的手，这样，看似毫无关系的数据块就建立了“依次排列”的关系，也就形成了链表:
2.1.3. 栈和队列
栈和队列隶属于线性表，是特殊的线性表，因为它们对线性表中元素的进出做了明确的要求。
栈中的元素只能从线性表的一端进出（另一端封死），且要遵循“先入后出”的原则，即先进栈的元素后出栈。
栈中含有 3 个元素，分别是 A、B 和 C，从栈中的状态可以看出 A 最先进的栈，然后 B 进栈，最后 C 进栈。根据“先进后出”的原则，3 个元素出栈的顺序应该是：C 最先出栈，然后 B 出栈，最后才是 A 出栈。
队列中的元素只能从线性表的一端进，从另一端出，且要遵循“先入先出”的特点，即先进队列的元素也要先出队列。
队列中有 3 个元素，分别是 A、B 和 C，从在队列中的状态可以看出是 A 先进队列，然后 B 进，最后 C 进。根据“先进先出”的原则，3 个元素出队列的顺序应该是 A 最先出队列，然后 B 出，最后 C 出。
2.3. 树存储结构
树存储结构适合存储具有“一对多”关系的数据。
如图所示，张平只有一个父亲，但他却有两（多）个孩子，这就是“一对多”的关系，满足这种关系的数据可以使用树存储结构。
2.4. 图存储结构
图存储结构适合存储具有“多对多”关系的数据。
如图所示，从 V1 可以到达 V2、V3、V4，同样，从 V2、V3、V4 也可以到达 V1，这就是“多对多”的关系，满足这种关系的数据可以使用图存储结构。
3. 数据的逻辑结构和物理结构
3.1. 逻辑结构
数据的逻辑结构，简单地理解，就是指的数据之间的逻辑关系。
如上图显示是一张家庭的成员关系图，从图中可以看到，张平、张华和张群是兄弟，他们的父亲是张亮，其中张平有两个儿子，分别是张晶和张磊。
以上所说，父子、兄弟等这些关系都指的是数据间的逻辑关系，假设我们要存储这样一张家庭成员关系图，不仅要存储张平、张华等数据，还要存储它们之间的逻辑关系，两者缺一不可。
一组数据成功存储到计算机的衡量标准是要能将其完整的复原。例如上图所示的成员关系图，如果所存储的数据能将此成员关系图彻底复原，则说明数据存储成功。
数据之间的逻辑关系可细分为三类：“一对一”、“一对多”、“多对多”
3.1.1. 线性结构
线性结构中的数据元素是一对一的关系
3.1.2. 树形结构
树形结构中的数据元素之间存在一种一对多的层次关系
3.1.3 图形结构
图形结构中的数据元素是多对多的关系
3.2. 物理结构（存储结构）
数据的存储结构，也就是物理结构，指的是数据在物理存储空间上选择集中存放(顺序存储结构)还是分散存放(链式存储结构)
假设要存储大小为 10G 的数据，则集中存放就如图 3a) 所示，分散存放就如图 3b）所示。
如果选择集中存储，就使用顺序存储结构；如果选择分散存储，就使用链式存储。
将数据进行集中存储有利于后期对数据进行遍历操作，而分散存储更有利于后期增加或删除数据。因此，如果后期需要对数据进行大量的遍历，就选择集中存储；若后期需要对数据频繁做增加或删除，则选择分散存储。
4. 时间复杂度
如何预估一个算法所编程序的运行时间呢？很简单，先分别计算程序中每条语句的执行次数，然后用总的执行次数间接表示程序的运行时间。
以一段简单的 C 语言程序为例，预估出此段程序的运行时间：
for(int i = 0 ; i < n ; i++) // n+1
{
for(int j = 0 ; j < m ; j++) // n*(m+1)
{
num++; // n*m
}
}
计算此段程序的频度为：(n+1)+n*(m+1)+n*m，简化后得 2*n*m+2*n+1。值得一提的是，不同程序的运行时间，更多场景中比较的是在最坏条件下程序的运行时间。以上面这段程序为例，最坏条件即指的是当 n、m 都为无限大时此段程序的运行时间。
要知道，当 n、m 都无限大时，我们完全就可以认为 n==m。在此基础上，2*n*m+2*n+1又可以简化为 2*n^2+2*n+1，这就是此段程序在最坏情况下的运行次数。
以无限大的思想来简化 2*n^2+2*n+1。当 n 无限大的：
- 首先，常数 1 是可以忽略不计的；
- 其次，对于指数级的 2n^2 来说，是否在其基础上加 2n，并无关紧要；
- 甚至于，对于是否给 n^2 乘 2，也可以忽略。
因此，最终频度2*n^2+2*n+1可以简化为 n^2 。
在数据结构中，“使用无限大的思想”简化频度表达式可以这样简化：
- 去掉频度表达式中，所有的加法常数式子。例如 2n^2+2n+1 简化为
2n^2+2n； - 如果表达式有多项含有无限大变量的式子，只保留一个拥有指数最高的变量的式子。例如
2n^2+2n简化为 2n^2； - 如果最高项存在系数，且不为 1，直接去掉系数。例如
2n^2系数为 2，直接简化为n^2；
数据结构使用大 O 法来表示算法的运行时间复杂度。大 O 记法的表示方法也很简单，格式如下：
O(频度)
如下列举了常用的几种时间复杂度，以及它们之间的大小关系：