数据结构是指数据对象及其相互关系和构造方法，一个数据结构S可以用一个二元组表示为：S=(D,R).其中，D是数据结构中数据的非空有限集合，R是定义在D上的关系的非空有限集合。更详细一点也可以表示成ADT（Abstract data type，抽象数据类型）。ADT定义了数据对象，数据关系，以及数据操作。在数据结构中，结点及结点之间的关系成为数据的逻辑结构，数据在计算机中的存储形式成为数据的存储结构。
按逻辑结构划分：线性结构（表、栈、队列）、非线性结构（树形结构、图结构）。
概念：线性表是最简单、最常用的一种数据结构，由相同类型的结点组成的有限序列。
线性表的存储：
1.顺序存储：最简单的存储方式。将线性表的结点依次存储在一个数组中。该方法的优点是能随机存取线性表中的任何一个结点，缺点主要有两个：一个是数组的大小通常是固定的，不利于任意增加或减少线性表的结点个数；二是插入和删除线性表的结点时，要移动数组中的其他元素，操作复杂。
2.链接存储：用链表来存储线性表。最简单的是单向链表。链表的每个结点不但要存储线性表结点信息，还要用一个域存储其后继结点指针。单向链表用指针来体现线性表中结点的先后次序。该方法的优点是线性表中每个结点的实际位置是任意的，给插入和删除操作带来了方便。缺点主要有两个：一是每个结点增加了一个后继指针成分，要花费更多的空间。二是不便随机访问线性表的任一节点。
概念：栈是一种特殊的线性表，只允许在同一端进行插入和删除操作。允许插入和删除的一端称为栈顶，另一端称为栈底。具有后进先出的特点。
栈的存储：
1.顺序存储：为了指明栈顶位置，需要一个地址变量TOP指出栈顶结点在数组中的下标。
2.链接存储：用链表来实现的栈称为链接栈。链表的首结点就是栈顶指针TOP，TOP为NULL的链表是空栈。
概念：队列是一种特殊的线性表，只允许在一端进行插入，另一端进行删除操作。允许删除的操作的一端称为队首，另一端称为队尾。具有先进先出的特征。
队列的存储：
1.顺序存储：可以用顺序存储线性表来表示队列，为了指明当前执行出队运算的队首位置，需要一个指针变量HEAD，为了指明入队操作的队尾，需要一个指针变量TAIL。为了解决多次进行入队和出队操作后队列数组前端空着，后端空间用完的问题，一种方法是把队列中的结点移到数组的前段，修改头指针和尾指针。另一种更好的解决办法是采用循环队列。
循环队列就是将实现队列的数组的a[n]的第一个元素a[0]和最后一个元素a[n-1]连接起来。队列空的判断条件是head=tail（head赶上tail），对队满的判断条件是head=tail+1（tail赶上head）.
2.链接存储：用链表实现的队列称为链接队列。队列头指针head指向队首结点，尾指针tail指向队尾结点，队尾结点的链接指针指向null。当head为null时，队列为空。
概念：
结点的度：一个结点的子树的数目称为该结点的度（次数）。
树的度：树中各结点的度得最大值称为树的度。
叶子结点：度为0的结点称为叶子结点。
树的深度：根的层数为1，树中最深结点的层数为树的深度，或称为树的次数。
树的存储：
1.标准存储：在树的标准存储结构中，树中的结点内容分为两部分，分别为结点的数据和指向子结点的指针数组。对于N度数，在标准存储结构中指针数组有N个元素。假如树的次数为5，用C语言描述树结点的标准存储结构的数据类。
#define N 5 typedef struct tnode { char data;//树的结点的数据信息 struct tnode*child[n];//树结点的子结点指针 }TNODE;//树结点的数据类型
2.带逆存储结构
在标准存储结构基础上增加一个指向其父结点的指针，用C语言描述树结点的带逆存储结构的数据类型如下：
#define N 5 typedef struct rtnode { char data;//树的结点的数据信息 struct rtnode*child[n];//树结点的子结点指针 struct rtnode*parent;//父结点指针 }RTNODE;//树结点的数据类型
树的遍历：
前序遍历，中序遍历，后序遍历。
概念：二叉树的结点最多有两个子树。
二叉树的存储：
采用类似树的标准存储结构：
typedef struct btnode { char data;//树的结点的数据信息 struct btnode*lchild;//树结点的左子结点指针 struct btnode*rchild;//树结点的右子结点指针 }BTNODE;//树结点的数据类型
二叉树的基本性质:
性质一：在二叉树的第i层上至多有2(i-1)个结点（i>=1，根结点为第一层）。
性质二：深度为k的二叉树至多有2k-1个结点（k>=1）.
性质三：对任何一棵二叉树，如果其叶子结点数为n0，度为2的结点数为n2，则n0=n2+1。
满二叉树：一棵深度为k且有2^k-1个结点的二叉树称为满二叉树。
二叉排序树又称为二叉查找树。
二叉排序树性质：
1.若它的左子树非空，则左子树上所有结点的值均小于根结点。
2.若它的右子树非空，则右子树上所有结点的值均大于跟结点。
3.左右子树本身又是一棵二叉排序树。
平衡二叉树又称为AVL树，是指树中任一结点的左右子树高度大致相同，相差对多为1.二叉排序树的高度为log2n.
增加了线索的二叉树。在结点上增加两个标志域ltag，rtag。
typedef struct btnode { char data;//树的结点的数据信息 struct btnode*lchild;//树结点的左子结点指针 struct btnode*rchild;//树结点的右子结点指针 int ltag,rtag; }BTNODE;//树结点的数据类型
当ltag=0时，表示lchild指针指向其做孩子结点；当ltag=1时，表示lchild指针指向其前驱结点。当rtag=0时，表示rchild指针指向其右孩子结点；当rtag=1时，表示rchild指向其后继结点。
概念：
树的路径长度是从树根到树中每个结点的路径长度之和。
结点的带权路径长度：结点到树根之间的路径长度与该结点上权的乘积。
树的带权路径长度：树中所有结点的带权路径长度之和。
树的带权路径长度最小的二叉树称为最优二叉树或哈夫曼树。
概念：
图G由两个集合V和E组成，记为G=(V,E)，其中V是定点的有穷非空集合，E是V中顶点偶对（称为边）的有穷集合。
图分为有向图和无向图两种。有向图中，一条有向边是由两个顶点组成的有序对，有序对通常用尖括号表示。<Vi,Vj>表示一条有向边，<Vj,Vi>是不同于<Vi,Vj>的另一条边。有向边也称为弧，边的始点称为弧尾，边的终点称为弧头（PS:貌似和一般的想法有点不同）。无向图中，边都是顶点的无序对，无序对通常用圆括号表示。
如果限定任何一条边或者一条弧的两个顶点不同，则有N个顶点的无向图至多有N(N-1)/2条边，这样的无向图称为完全无向图。一个有向图至多有N(N-1)条弧，这样的有向图称为完全有向图。
无向图中，一个顶点的度等于与其邻接的顶点个数。有向图中，一个顶点的入度等于邻接到该顶点的顶点个数，其出度等于邻接于该顶点的顶点个数。
在有向图中，若对于V(G)（表示顶点的集合）中任意两个不同的顶点Vi和Vj，都存在从Vi到Vj及从Vj到Vi的路径，则称G是强连通图。
有向图的极大强连通子图称为图的强连通分量。强连通图只有一个强连通分量，即自身。非强连通图的有向图有多个强连通分量。
图的存储结构：
1.邻接矩阵：反映顶点间的邻接关系。
设G=(V,E)是具有n(n>=1)个顶点的图，G的邻接矩阵M是一个n行n列的矩阵，并有若(i,j)或<i,j>∈E，则M[i][j]=1，否则M[i][j]=0。
由邻接矩阵的定义，无向图的邻接矩阵是对称的，有向图的邻接矩阵不一定对称。对于无向图，其邻接矩阵第i行元素的和即为顶点i的度。对于有向图，其邻接矩阵的第i行元素之和为顶点i的出度，第j列的元素之和为顶点j的入度。
若将图的每一条边都赋予一个权值，则称这种带权图为网（络）。如果G=(V,E)是具有n(n>=1)个顶点的网，若(i,j)或<i,j>∈E，则M[i][j]为(i,j)或<i,j>上的权。若(i,j)或<i,j>∉E，则M[i][j]为无穷大或者为大于图中任何权值的实数。
2.邻接表：
在图的邻接表中，为图的每一个顶点建立一个链表，且第i个链表中的结点代表与顶点i相关联的一条边或者由顶点i出发的一条弧。有n个顶点的图需要用n个链表来表示。
3.图的遍历
a.深度优先遍历
b.广度优先遍历
概念：
如果连通图G的一个子图是一棵包含G的所有顶点的树，则该子图称为G的生成树。生成树是连通图的包含图中的所有顶点的极小连通子图。图的生成树并不唯一。从不同的顶点出发进行遍历，可以得到不同的生成树。含有n个顶点的连通图的生成树有n个顶点，n-1条边。在一棵生成树中，各条边的权值之和称为这棵生成树的代价，代价最小的生成树称为最小代价生成树（简称最小生成树）。
MST（最小生成树，Minimum Spannirng Tree）性质：
设G=(V，E)是一个连通网络，U是顶点集V的一个真子集。若(u，v)是G中一条“一个端点在U中(例如：u∈U)，另一个端点不在U中的边(例如：v∈V-U)，且(u，v)具有最小权值，则一定存在G的一棵最小生成树包括此边(u，v)。
求连通的带权无向图的最小生成树的算法有普利姆（Prim）算法和克鲁斯卡尔（Kruskal）算法。在Kruskal算法中，集合A（A是E的一个子集）是一个森林，假如集合A中的安全边总是图中链接两个不同分支的最小权边。在Prim算法中，集合A仅形成单棵树，添加入集合A的安全边总是连接树与一个不在树中的顶点的最小权边。
普利姆算法：
Prim算法的特点是集合A（集合A是逐渐形成最小生成树的顶点的集合）中的边总是形成单棵树。树从任意顶点r开始形成，并逐渐生成，直至该树覆盖了V中的所有顶点。在每一步，一条连接了树A与GA=(V,A)中某孤立顶点的轻边（权值最小的安全边）被加入到树A中。当算法终止时，A中的边就形成了一棵最小生成树。
算法时间复杂度是O(n2)，与图中的边数无关，所以适合于稠密图。
克鲁斯卡尔算法:
设T的初始状态只有n个顶点而无边的森林T=(V,∅)，按边长递增的顺序选择E中的n-1安全边(u,v)并加入T，生成最小生成树。
特点是当前形成的集合T除最后结果外，始终是一个森林。时间复杂度为O(elog2e)，与图中顶点数无关，所以较适合稀疏图。
带权图的最短路径问题即求两个顶点之间长度最短的路径。其中路径长度是指路径上各边的权值之和。
1.单源最短路径
已知有向带权图（简称有向网）G=(V,E)，找出从某个源点s∈V到V中其余各顶点的最短路径，称为单源最短路径。
所用算法：迪捷克斯特拉（Dijkstra）算法。
算法基本思想：设S为最短距离已确定的顶点集（看做红点集），V-S是最短距离尚未确定的顶点集（看做蓝点集）。
初始化：初始化时，只有源点s的最短距离是已知的（SD(s)=0），故红点集S={s},蓝点集为空。
重复以下工作，按路径长度递增次序产生个顶点最短路径：在当前蓝点集中选择一个最短距离最小的蓝点来扩充红点集，以保证算法按路径长度递增的次序产生各顶点的最短路径。当蓝点集中仅剩下最短距离为∞的蓝点，或者所有蓝点已扩充到红点集时，s到所有顶点的最短路径就求出来了。
需要注意的是：
若从源点到蓝点的路径不存在，则可假设该蓝点的最短路径是一条长度为无穷大的虚拟路径。
从源点s到终点v的最短路径简称为v的最短路径；s到v的最短路径长度简称为v的最短距离，并记为SD(v)。
2.每一对顶点之间的最短路径
所用算法：弗洛伊德（Floyd）算法（ps:有点复杂，待解决）
对一个有向无环图G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u,v，若<u,v>∈E(G)，则u 在线性序列中出现在v之前。这样的线性序列称为满足拓扑排序次序的序列。简称拓扑序列。
需要注意的是：
若将图中顶点按拓扑次序排成一行，则图中所有的有向边均是从左指向右的；
若图中存在有向环，则不可能使顶点满足拓扑次序，不存在拓扑序列。
一个有向无环图可能有多个拓扑序列。
有向图的顶点表示活动，有向边表示活动之间开始的先后关系，这种有向图称为用表活动网络，简称为AOV网络。
在AOV网络中，如果边上的权表示完成活动所需的时间，则称这样的AOV为AOE网络（Activity On Edge）。因为AOE网络中的某些活动可以并行进行，所以完成工程的最少时间是从开始顶点到结束顶点的最长路径长度，称从开始顶点到结束顶点的最长路径为关键路径（临界路径），关键路径上的活动称为关键活动。
