1. 线性数据结构

1.1 线性列表

线性列表是由元素构成的有限序列，即按照一定的线性顺序排列的元素集合。这种数据结构的基本操作包括对元素的查找、插入和删除。

1.2 数组

数组是n个相同类型的元素构成的序列，连续存储在计算机的存储器中，只要指定数组的下标就能访问数组元素。数组属于线性列表的一种。

1.2.1 数组的重要特点

1、元素是连续存储的。
2、无论位于数组的什么位置，都能用相等的常量时间访问数组的任何元素。

1.3 链表

链表是0个或多个称为节点的元素构成的序列，每个节点包含两类信息：一类是数据；另一类是一个或多个称为指针的链接，指向链表中其他元素。链表属于线性列表的一种。

1.3.1 链表的特点

1、访问链表元素所需要的时间依赖于该元素所在的位置。
2、不需要事先分配任何存储空间。
3、插入和删除的效率非常高，只要对相关指针进行重新连接即可。

1.4 栈

栈是一种插入和删除操作都只能在端部进行的线性列表，这一端称为栈顶。

1.4.1 栈的特点

1、后进先出。
2、有助于理解递归算法。

1.5 队列

队列是一种只在一头删除元素，只在另一头插入元素的线性列表，负责删除的一头称为队头，负责插入的一头称为队尾，删除操作又称为出队，插入操作又称为入队。

1.5.1 队列的特点

1、先进先出。

1.5.2 优先队列

优先队列是数据项的一个集合，这些数据项都来自一个全序域，即这些数据项都可以排序的。对优先队列的主要操作包括查找最大元素、删除最大元素和插入新元素（插入新元素的时候要对元素进行排序）。

2. 图

图G是一个有序二元组(V,E)，其中V称为顶集(Vertices Set)，E称为边集(Edges set)，E的元素都是二元组，用(x,y)表示，其中x,y∈V。如果(x,y)等同于(y,x)，则这条边是无向的，否则就是有向的，并且称x为尾，y为头。

2.1 无向图

如果图G所有边都是无向的，称之为无向图。

2.1.1 无向图的特点

1、用|V|表示顶点的数量，用|E|表示边的数量，那么 0 <= |E| <= |V|(|V|-1)/2，原理是：如果每个顶点|V|和其他|V|-1个顶点之间都有边相连，图的数量就达到最大，除以2是因为每条边都包含了两次，对于无向图来说，(x,y)=(y,x)。

2.2 有向图

如果图G所有边都是有向的，称之为有向图。

2.3 完全图

任意两个顶点之间都有边相连的图称为完全图。

2.4 非完全图

如果图中所缺的边数量相对较少，称之为稠密图；如果图中的边相对于顶点来说数量较少，称之为稀疏图。处理的图是稀疏图还是稠密图可能会影响到图的表示方法，从而影响设计和使用的算法的效率。

2.5 图的表示方法

2.5.1 邻接矩阵

2.5.2 邻接链表