数据结构（一）数据结构概述

---

数据结构大致包含以下几种存储结构：

• 线性表，还可以细分为顺序表、链表、栈、队列；
• 树结构，包括普通树，二叉树，线索二叉树等；
• 图存储结构；

---

线性表

线性表结构存储的数据是可以依次排列的,每个数据前后只有一个数据排列，具备这种“一对一”关系的数据就可以使用线性表来存储。

例如，存储类似于{1,3,5,7,9}这样的数据时，各元素依次排列，每个元素前后有且仅有一个元素与之相邻（除首尾元素）,因此可以使用线性表存储。

线性表并不是一种具体的存储结构，它包含顺序存储结构和链式存储结构，是顺序表和链表的统称。

1.顺序表

顺序表简单的理解，就是常用的数组，例如：

图1：顺序表结构

由于顺序表结构的底层实现借助的就是数组，对于初学者来说，可以把顺序表等价为数组，但实则并不是这样。

2.链表

使用顺序表（底层靠数组实现）时，需要提前申请一定大小的存储空间，这块存储空间的物理地址是连续的 图1所示。

链表则完全不同，使用链表存储数据时，是随用随申请，因此数据的存储位置是分离的，换句话说，数据的存储位置是随机的。

为了给各个数据块建立“依次排列”的关系，链表给各数据块增设一个指针，每个数据块的指针都指向下一个数据块（最后一个数据块指向null），这样数据块就建立了“依次排序”的关系，也就形成了链表。如图2

图2:链表结构

3.栈和队列

栈和队列隶属于线性表，是特殊的线性表，因为他们对线性表中元素的进出做了明确的要求。

栈中的元素只能从线性表的一端进出（另一端封死），且要遵循“先入后出”的原则，即先进栈的元素后出栈。

图3：栈结构

队列中的元素只能从线性表的一端进入，从另一端出，且要遵循“先入先出”的特点，即先进队列的元素也要先出队列。如图4

图4：队列结构

---

树

树存储结构适合存储具有“一对多”关系的数据

图5：树结构

如图5所示，其中张平只有一个父亲，但他却有两个孩子，这就是“一对多”的关系，满足这种关系的数据可以使用树存储结构。

---

图

图存储结构适合存储具有“多对多”关系的数据。

图6：图结构

如图6所示，从V1可以到达V2、V3、V4，同样从V2、V3、V4也可以到达V1，这就是“多对多”的关系，满足这种关系的数据可以使用图存储结构。

---

算法的时间复杂度和空间复杂度

1.好算法的标准

• 对于一个问题的算法来说，首先必须能够解决这个问题（准确性）
• 通过这个算法编写的程序要求在任何情况下不能崩溃（健壮性）
• 准确性和健壮性都满足之后，要考虑算法运行时间（时间复杂度）和算法所需的内存空间大小（空间复杂度）

人们对于软件或者 APP 的运行效率有极高的要求，例如对于网页打开的忍耐极限是 6 秒甚至更短，如果你设计的网页打开的时间超过 6 秒，多数人会在 4 秒甚至 3 秒的时候毫不犹豫地关掉而去浏览其他网页。在这个大背景下，一个好的“算法”更注重的是时间复杂度，而空间复杂度只要在一个合理的范围内就可以。

2.时间复杂度的计算

算法的时间复杂度，主要看算法中使用到的循环结构中代码循环的次数（称为频度），次数越少，时间复杂度越低。

时间复杂度的表示

O(频度) 这种表示方式称为大“O”记法。

例如：
a) ++x; s=0;
b) for (int i=1; i<=n; i++) { ++x; s+=x; }
c) for (int i=1; i<=n; i++) { for (int j=1; i<=n; j++) { ++x; s+=x; } }
对上述例子而言，a的时间复杂度为O(1),b的时间复杂度为O(n),c的时间复杂度为O(n²)

如果a、b、c组成一断程序，name算法的时间复杂度为O(n²+n+1)
但这么表示是不对的，还需要对n²+n+1进行简化
简化过程分为3步：

• 去掉运行时间中的所有加法常数 （例如n²+n+1 直接变为n²+n）
• 只保留最高项（n²+n变为n²）
• 如果最高项的系数不是1 去掉系数（例如2n²变为n²）

所以最终a、b、c合并而成的代码的时间复杂度为O(n²)

3.常用时间复杂度的排序

O(1)常数阶 < O(logn)对数阶 < O(n)线性阶 < O(n²)平方阶 < O(n³)立方阶< O(2ⁿ)指数阶

4.算法复杂度速查表

图7：颜色描述提示 图8：数据结构操作复杂度
图9：数组排序算法复杂度
图10：图操作复杂度
图11：堆操作复杂度
图12：大O复杂度图表

5.时间换空间与空间换时间

算法的时间复杂度和空间复杂度可以相互转化。

谷歌浏览器相比于其他的浏览器，运行速度要快。是因为它占用了更多的内存空间，以空间换取了时间。

算法中，例如判断某个年份是否为闰年时，如果想以时间换取空间，算法思路就是：当给定一个年份时，判断该年份是否能被4或者400整除，如果可以，就是闰年。

如果想以空间换时间的话，判断闰年的思路就是：把所有的年份先判断出来，存储在数组中（年份和数组下标对应），如果是闰年，数组值是1，否则是0；当需要判断某年是否为闰年时，直接看对应的数组值是1还是0，不用计算就可以马上知道。

---

数据的逻辑结构和物理结构

逻辑结构

数据的逻辑结构，简单的理解，就是指数据间的逻辑关系
数据之间的逻辑关系可细分为三类

• “一对一”：类似集合{1,2,3,4,…,n}这类的数据，每个数据的左侧有且仅有一个数据与其相邻（除1外）;同样，每个数据的右侧也只有一个数据与其相邻（除n外），所有的数据都是如此，就说数据之间是“一对一”关系

• “一对多”：一个节点下面有多个节点，就是”一对多”关系 （树）

• “多对多”：多个节点对多个节点 且互相可达，他们就是“多对多”关系（图）

三种存储结构分别存储这三类逻辑关系的数据，换句话说：
1.线性表用于存储具有“一对一”逻辑关系的数据
2.树结构用于存储具有“一对多”关系的数据
3.图结构用于存储具有“多对多”关系的数据

物理结构

数据的存储结构，也就是物理结构，指的是数据在物理存储空间上选择集中存放还是分散存放。

图13：数据的物理存储方式
如果选择集中存储，就使用顺序存储结构；反之，就使用链式存储。至于如何选择，主要取决于存储设备的状态以及数据的用途。

集中存储（底层实现使用的是数组）需要使用一大块连续的物理空间，假设要存储大小为 1G 的数据，若存储设备上没有整块大小超过 1G 的空间，就无法使用顺序存储，此时就要选择链式存储，因为链式存储是随机存储数据，占用的都是存储设备中比较小的存储空间，因此有一定几率可以存储成功。

并且，数据的用途不同，选择的存储结构也不同。将数据进行集中存储有利于后期对数据进行遍历操作，而分散存储更有利于后期增加或删除数据。因此，如果后期需要对数据进行大量的检索（遍历），就选择集中存储；反之，若后期需要对数据做进一步更新（增加或删除），则选择分散存储。