表

表是所有线性数据结构的统称。其核心有三：

以连续紧凑的方式存储的线性表、
以物理离散而逻辑连续的方式存储的链表、
以逻辑上离散的方式存储的散列表。

基础表结构

线性表

线性表是一个连续的串；任意两个在逻辑意义上相邻节点（即数据存储单元）在物理意义上也是连续的。形象地描述。线性表就如同在书架上的一排书；向其中插入时，需要将其右侧的书全部移开，然后将代插入的书放入；取出时，将书拿走后，还需要将右侧的所有书向左移动，使得整体结构仍然连续。实际上此结构的直接应用并不算广泛；但是其它一些结构都是从它衍伸出来的，比如即将介绍的链表、队列……

散列表

相信大家使用过数组。没错，数组就是最常见的散列表！散列表的特征就是“随机存取”；相当于是说，内存的一个区域被当做了一块“小内存”。大部分数据结构的底层实现都是数组（也就是散列表）。它在使用Hash 的算法中也可以大展身手。

链表

链表的核心思想和散文有些类似：“形散而神不散”。各个节点存储在任意的空间，而通过节点之间的指针进行连接。每一个节点包含两个部分：数据域和连接域。数据域即为实际存储的数据。连接域根据链表的类型，包含当前节点的前驱与后继的指针。它的缺点在于，当需要访问某一节点时，必须得从表头开始、逐个节点判断是否为所需节点。因此可以认为，链表不支持随机存取。它的优点在于，在知道节点位置的前提下，可以快速插入/删除，且可以节省散列表所需要的巨额存储空间。

栈

一种从线性表扩展而得的数据结构。它规定，元素的插入/删除操作只能发生在栈顶，就好像一摞箱子，如果想要去走箱子必须得从最上面顺次搬走、如果要堆上新的箱子也必须要放在顶上一般。虽然名字可能相像，但是千万不要将栈（很多教材中成为堆栈）和堆（一种基于二叉树的数据结构，能够快速提取全局最值）弄混了。

实际上，递归算法中都利用到了栈的思想（即从最近插入的元素扩展状态）；而如果使用计算机程序实现递归算法，操作系统也会使用内置的系统栈完成这一操作。这也告诉我们，我们也可以自己亲手使用堆栈模拟这一行为，这样就可以避免因爆栈导致不必要的RTE。

队列

不知道为什么我也就像思维定式一样把队列放在了栈后面讲。一种从线性表扩展而得的数据结构。它规定，元素的插入操作只能作用于队尾，而删除操作只能作用于队头。实际上，很多动态规划算法都用到了队列的思想：从已有的状态中取出最早（或最优，这里需要用到优先队列（即堆），会在下期介绍）的一个，转移状态，然后将新的节点插入队列。

散列表与哈希

有的时候，我们需要地找出一个字符串中相等的子串；甚至需要回答很多次这样的询问。条件不允许我们对于每一次询问都遍历两次字符串，但是却允许我们这样做一次。

图

除了线性结构以外，数据结构中最值得一提的就是图了。由于图论也是离散数学中的核心部分，因此这里数学味可能会稍微浓一点。

一些基本定义

图是一个二元组 G=(V,E)；其中 V 是节点集合，E 是边集合。当然，对于任何(u,v)∈E，均有 u∈V 且 v∈V 。

如果 E 中的所有边都是没有方向的，则称 G 为无向图；如果 E 中所有的边都指定了方向，则称 G 为有向图；否则称 G 为混合图。

对于无向图，节点的度数是指与该节点关联的边的数目；对于有向图，节点的出度指从其出发的边数目，节点的入度为到达它的边数目。如果从 E 中选取一些边构成一个长度为 k 的序列 s，且满足对于任意i均有v[i]=u[i+1]（首尾相连），则 s 构成一条从 u[1]到 v[k]的长度为k 的路径。如果两个点之间存在路径，则称它们是连通的。极大的连通节点集合构成一个联通块。