第一章 数据结构基本概念
数据：计算机程序所加工处理的描述客观事物的符号表示。
数据元素：数据的基本单位，是数据集合中的一个个体, 在计算机程序中通常作为一个整体进行考虑和处理。数据元素可由一个或若干个数据项所组成。
数据项：是具有独立意义的数据的最小单位。
数据对象：性质相同的数据元素的集合, 是数据的一个子集。
数据结构：相互之间存在一种或多种特定关系的数据元素的集合。即数据的组织形式。数据元素相互之间的关系称为结构。
四种基本的数据结构是：集合、线性结构、树形结构、和图形结构。
数据结构包括三个方面的内容：逻辑结构、存储结构、基本操作（运算）
数据类型：一个值的集合和定义在这个值集上的一组操作。程序设计语言中对于给定变量的所有可能取值的集合。
抽象数据类型（ADT ）：一种数据类型及在这种数据类型上定义的一组操作。包括数据类型的定义和这种数据类型的操作集合。
第二章 线性表
线性表是n(n>=0)个数据元素的有限序列，同一线性表中的数据元素必定具有相同特性，即属于同一数据对象，相邻数据元素之间存在序偶关系。n 定义为线性表的长度；n 为0表示该线性表为空表；数据元素可以是一个数、一个符号或由多个数据项所构成的。
线性表中任一数据元素的存储位置为：LOC (a i ) =LOC (a 1) +(i -1) ⨯s
线性链表是一种动态存储结构，所占用的存储空间是在程序的执行过程中得到的，当线性链表要增加一个结点时，向系统申请一个存储空间，删除结点时要将空间释放。
由线性链表的结点定义，每个结点中均只含有一个指针域，用于指向其后继结点，故也称单链表。
循环链表是线性表的另一种形式的链式存储表示。它的特点是表中最后一个结点的指针域指向头结点，整个链表成为一个由链指针相链接的环，并且可将头指针设成指向最后一个结点（尾指针）。空的循环链表由只含一个自成循环的头结点表示。
若双向链表中的两个链均构成回路，则称为双向循环链表。
第三章 栈和队列
栈是限定只能在表的一端（表尾）进行插入和删除操作的线性表；允许插入和删除的一端，称为栈顶(top)；另一端则称为栈底(bottom)；栈又叫做后进先出（LIFO ）的线性表。
为了指示当前的栈顶元素，需设一个指针top 指示当前栈顶的位置，称为栈顶指针。
队列也是受限的线性表。限定只能在队列的一端插入元素，另一端删除元素。插入元素的一端是队尾(rear)，删除元素的一端是队头(front)。队列具有先进先出的特点，因此称为先进先出（FIFO ）线性表。
第四章 串
串是由n(n>=0)个任意字符组成的有限序列。当n 为零时，称为空串。由一个或多个空格符组成的串称为空格串。
子串：串中任意连续的字符组成的子序列称为该串的子串。
主串：包含子串的串。
子串的位置：子串的第一个字符在主串中的序号称为子串的位置。
两个串相等：当且仅当两个串的长度相等且对应位置上的字符都相同。
第五章 数组与广义表
数组是连续的、有限的、有序的、同构的数据元素的集合；LOC(ai)=LOC(a1)+(i-1)*L（一维数组） LOC(aij)=LOC(a11)+[(i-1)*N+j-1]*L（行序为主的存储方式）
特殊矩阵：三角矩阵、对称矩阵或对角矩阵，值相同或零元素的分布在矩阵中有一定的规律。
稀疏矩阵:非零元素个数远小于矩阵元素个数。
压缩存储：为多个值相同的元只分配一个存储空间以节省存储空间；对零元不分配空间。
广义表：LS=(a1,a2,„,an)LS 为广义表的名称，n 为广义表的长度，ai 可以是单个元素，也可以是广义表，称为LS 的原子和子表。当广义表非空时，称第一个元素a1为表头（Head ），称其余元素组成的表（a2,a3„,an ）为表尾（Tail ）。
第六章 树和二叉树
树结点 树中一个独立单元。包含一个数据元素及若干指向其子树的分支。
树根 树中唯一没有前趋的结点。
结点的度(Degree) 结点拥有的子树数，称为结点的度。
树的度 树中各结点的度的最大值。
树叶(Leaf) 度为0的结点。也称叶结点。除根和叶子以外的其他结点称为中间结点。
双亲(Parent)和孩子(Child) 我们把一个树结点的直接前趋称之为该结点的双亲；反之把一个树结点的所有直接后趋称为该结点的孩子。
兄弟(Sibling) ： 同一双亲的孩子之间互称为兄弟。
结点的层次(Level) 从根算起，根为第一层，根的孩子为第二层，树中任一结点的层次等于它的双亲的层次加1。
树的深度(Depth) 树中各结点层次的最大值称为树的深度或高度。
有序树和无序树 如果树中结点的各子树可看成从左至右是有次序的（即不能互换），则称该树为有序树。否则称为无序树。在有序树的最左边的子树的根称为第一孩子。最右边称为最后一个孩子。
森林(Forest) m (m≥0) 棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。由此也可以以森林和树的相互递归定义来描述树。
线索二叉树：为每个结点加上线索的二叉树称为线索二叉树。
线索:指向前驱结点和后继结点的指针称为线索。
线索化：对二叉树进行某种次序遍历使其变为线索二叉树的过程叫做线索化。
结点的带权路径：从根到带权结点之间的路径长度与结点的权值的乘积。
树的带权路径：树中所有带权叶子结点的带权路径长度之和。记做WPL 。
最优二叉树：假设有 n 个权值{w1，w2，„wn }，试构造一棵有 n 个叶子结点的二叉树，每个叶子结点带权为wi 。显然，这样的二叉树可以构造出多棵，其中必存在一棵带权路径长度 WPL 取最小的二叉树，称该二叉树为最优二叉树也称哈夫曼树。(注意：最优二叉树中只有度为0和度为2的结点）
第七章 图
图是一种数据结构，由二个集合V 和E 组成，记做G=(V,E)，其中V 是数据元素的非空有限集合，E 是V 中二元关系（边）的集合。即V 是顶点的集合，E 是顶点的偶对，即边的集合。
有向图：图的每条边都是有序顶点对（即边是有方向的）
无向图：图的每条边都是无序顶点对（即边是无方向的）
在有n 个顶点的无向图中，e 的范围为0－n(n-1)/2。具有n(n-1)/2条边的无向图称为无向完全图。 在有n 个顶点的有向图中，e 的范围为0-n(n-1)，具有n(n-1)条边的有向图称为有向完全图。
度：图的边或弧的数目等于顶点度数之和的一半。
在有向图或无向图中，如果存在首尾相接并且无重复边（弧）的边（弧）序列，则称这个序列是一条从顶点v0到vn-1的一条路径，序列中的边（弧）数称为路径长度。
简单路径：在一条路径中，若除起点和终点以外，所有顶点彼此各不相同，则称该路径为简单路径。 回路：在一条路径中，若起点和终点都是同一顶点，则称该路径为回路。
简单回路：有简单路径组成的回路称为简单回路
连通：在无向图G 中，若任意二个顶点之间都是连通的, 即均存在路径，则称图G 为连通图。否则称为非连通图。
连通分量：在非连通的无向图G 中，极大连通子图称为无向图的连通分量。
强连通：在有向图G 中，若顶点vi 到顶点vj 有路径存在，并且从顶点vj 到顶点vi 也有路径存在，则称vi 到vj 是强连通的。
强连通图：在有向图G 中，若任意二个顶点之间都是强连通的，则称有向图G 为强连通图。
强连通分量：在非强连通的有向图G 中，极大强连通子图称为有向图的强连通分量。
邻接矩阵（Adjacency Matrix）是表示顶点之间相邻关系的矩阵。
图的生成树是不唯一的，从不同的顶点出发得到的生成树是不同的，但是如果图是带权图，则权值之和最小的生成树是称为最小生成树。
一个无回环的有向图称为有向无环图，简称为DAG 图
关键路径：在AOE 网中，从源点到汇点的带权路径长度最长的路径称为关键路径。
关键活动：在关键路径上的弧称为关键活动
单源最短路径－求某源点到其余各顶点的最短路径
第八章 查找
查找表是由具有同一类型（属性）的数据元素（记录）组成的集合。
静态查找表：仅对查找表进行查找操作，而不改变查找表中的数据元素；
动态查找表：对查找表除进行查找操作外，可能还要进行向表中插入数据元素，或删除表中数据元素的表。 关键字：数据元素中某个数据项的值，可以标识一个数据元素。
主关键字：可以唯一标识一个数据元素。
第九章 排序
内部排序：在排序进行的过程中不使用计算机外部存储器的排序过程。
外部排序：在排序进行的过程中需要对外存进行访问的排序过程。
直接插入排序，在有序序列中插入新的记录以达到扩大有序区的长度的目的。
希尔排序又称“缩小增量排序”
冒泡排序：依次比较相邻两个记录的关键字，若和所期望的相反，则互换这两个记录
快速排序：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
简单选择排序：不断从待排序序列中挑选出关键字最小的元素，依次放在已排序子序列的最后，直到待排序序列中所有元素都被选完，从而得到一个有序的序列。
归并排序：直接将一个含有N 个元素的序列，看成N 个含有1个元素的子序列；然后对相邻子序列进行两两合并；最终得到一个有序序列。
基数排序不需要进行关键字值的比较，而是根据关键字的各位值进行排序的方法。
排序方法 时间复杂度 空间复杂性 稳定性 复杂性 平均情况 最坏情况 最好情况
插入排序 O(n2) O(n2) O(n) O(1) 稳定 简单
稳定 简单
简单
较复杂
较复杂 希尔排序 O(nlog2n) O(nlog2n) O(1) 不稳定 较复杂 冒泡排序 O(n2) O(n2) O(n) O(1) 快速排序 O(nlog2n) O(n2) O(nlog2n) 堆排序 O(log2n ) 不稳定 较复杂 不稳定 稳定 选择排序 O(n2) O(n2) O(n) O(1) 稳定 O(nlog2n) O(nlog2n) O(nlog2n) O(1) O(n) 归并排序 O(nlog2n) O(nlog2n) O(nlog2n)
基数排序 O(tn) O(tn) O(tn)
O(n) 稳定 较复杂
第一章 数据结构基本概念
数据：计算机程序所加工处理的描述客观事物的符号表示。
数据元素：数据的基本单位，是数据集合中的一个个体, 在计算机程序中通常作为一个整体进行考虑和处理。数据元素可由一个或若干个数据项所组成。
数据项：是具有独立意义的数据的最小单位。
数据对象：性质相同的数据元素的集合, 是数据的一个子集。
数据结构：相互之间存在一种或多种特定关系的数据元素的集合。即数据的组织形式。数据元素相互之间的关系称为结构。
四种基本的数据结构是：集合、线性结构、树形结构、和图形结构。
数据结构包括三个方面的内容：逻辑结构、存储结构、基本操作（运算）
数据类型：一个值的集合和定义在这个值集上的一组操作。程序设计语言中对于给定变量的所有可能取值的集合。
抽象数据类型（ADT ）：一种数据类型及在这种数据类型上定义的一组操作。包括数据类型的定义和这种数据类型的操作集合。
第二章 线性表
线性表是n(n>=0)个数据元素的有限序列，同一线性表中的数据元素必定具有相同特性，即属于同一数据对象，相邻数据元素之间存在序偶关系。n 定义为线性表的长度；n 为0表示该线性表为空表；数据元素可以是一个数、一个符号或由多个数据项所构成的。
线性表中任一数据元素的存储位置为：LOC (a i ) =LOC (a 1) +(i -1) ⨯s
线性链表是一种动态存储结构，所占用的存储空间是在程序的执行过程中得到的，当线性链表要增加一个结点时，向系统申请一个存储空间，删除结点时要将空间释放。
由线性链表的结点定义，每个结点中均只含有一个指针域，用于指向其后继结点，故也称单链表。
循环链表是线性表的另一种形式的链式存储表示。它的特点是表中最后一个结点的指针域指向头结点，整个链表成为一个由链指针相链接的环，并且可将头指针设成指向最后一个结点（尾指针）。空的循环链表由只含一个自成循环的头结点表示。
若双向链表中的两个链均构成回路，则称为双向循环链表。
第三章 栈和队列
栈是限定只能在表的一端（表尾）进行插入和删除操作的线性表；允许插入和删除的一端，称为栈顶(top)；另一端则称为栈底(bottom)；栈又叫做后进先出（LIFO ）的线性表。
为了指示当前的栈顶元素，需设一个指针top 指示当前栈顶的位置，称为栈顶指针。
队列也是受限的线性表。限定只能在队列的一端插入元素，另一端删除元素。插入元素的一端是队尾(rear)，删除元素的一端是队头(front)。队列具有先进先出的特点，因此称为先进先出（FIFO ）线性表。
第四章 串
串是由n(n>=0)个任意字符组成的有限序列。当n 为零时，称为空串。由一个或多个空格符组成的串称为空格串。
子串：串中任意连续的字符组成的子序列称为该串的子串。
主串：包含子串的串。
子串的位置：子串的第一个字符在主串中的序号称为子串的位置。
两个串相等：当且仅当两个串的长度相等且对应位置上的字符都相同。
第五章 数组与广义表
数组是连续的、有限的、有序的、同构的数据元素的集合；LOC(ai)=LOC(a1)+(i-1)*L（一维数组） LOC(aij)=LOC(a11)+[(i-1)*N+j-1]*L（行序为主的存储方式）
特殊矩阵：三角矩阵、对称矩阵或对角矩阵，值相同或零元素的分布在矩阵中有一定的规律。
稀疏矩阵:非零元素个数远小于矩阵元素个数。
压缩存储：为多个值相同的元只分配一个存储空间以节省存储空间；对零元不分配空间。
广义表：LS=(a1,a2,„,an)LS 为广义表的名称，n 为广义表的长度，ai 可以是单个元素，也可以是广义表，称为LS 的原子和子表。当广义表非空时，称第一个元素a1为表头（Head ），称其余元素组成的表（a2,a3„,an ）为表尾（Tail ）。
第六章 树和二叉树
树结点 树中一个独立单元。包含一个数据元素及若干指向其子树的分支。
树根 树中唯一没有前趋的结点。
结点的度(Degree) 结点拥有的子树数，称为结点的度。
树的度 树中各结点的度的最大值。
树叶(Leaf) 度为0的结点。也称叶结点。除根和叶子以外的其他结点称为中间结点。
双亲(Parent)和孩子(Child) 我们把一个树结点的直接前趋称之为该结点的双亲；反之把一个树结点的所有直接后趋称为该结点的孩子。
兄弟(Sibling) ： 同一双亲的孩子之间互称为兄弟。
结点的层次(Level) 从根算起，根为第一层，根的孩子为第二层，树中任一结点的层次等于它的双亲的层次加1。
树的深度(Depth) 树中各结点层次的最大值称为树的深度或高度。
有序树和无序树 如果树中结点的各子树可看成从左至右是有次序的（即不能互换），则称该树为有序树。否则称为无序树。在有序树的最左边的子树的根称为第一孩子。最右边称为最后一个孩子。
森林(Forest) m (m≥0) 棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。由此也可以以森林和树的相互递归定义来描述树。
线索二叉树：为每个结点加上线索的二叉树称为线索二叉树。
线索:指向前驱结点和后继结点的指针称为线索。
线索化：对二叉树进行某种次序遍历使其变为线索二叉树的过程叫做线索化。
结点的带权路径：从根到带权结点之间的路径长度与结点的权值的乘积。
树的带权路径：树中所有带权叶子结点的带权路径长度之和。记做WPL 。
最优二叉树：假设有 n 个权值{w1，w2，„wn }，试构造一棵有 n 个叶子结点的二叉树，每个叶子结点带权为wi 。显然，这样的二叉树可以构造出多棵，其中必存在一棵带权路径长度 WPL 取最小的二叉树，称该二叉树为最优二叉树也称哈夫曼树。(注意：最优二叉树中只有度为0和度为2的结点）
第七章 图
图是一种数据结构，由二个集合V 和E 组成，记做G=(V,E)，其中V 是数据元素的非空有限集合，E 是V 中二元关系（边）的集合。即V 是顶点的集合，E 是顶点的偶对，即边的集合。
有向图：图的每条边都是有序顶点对（即边是有方向的）
无向图：图的每条边都是无序顶点对（即边是无方向的）
在有n 个顶点的无向图中，e 的范围为0－n(n-1)/2。具有n(n-1)/2条边的无向图称为无向完全图。 在有n 个顶点的有向图中，e 的范围为0-n(n-1)，具有n(n-1)条边的有向图称为有向完全图。
度：图的边或弧的数目等于顶点度数之和的一半。
在有向图或无向图中，如果存在首尾相接并且无重复边（弧）的边（弧）序列，则称这个序列是一条从顶点v0到vn-1的一条路径，序列中的边（弧）数称为路径长度。
简单路径：在一条路径中，若除起点和终点以外，所有顶点彼此各不相同，则称该路径为简单路径。 回路：在一条路径中，若起点和终点都是同一顶点，则称该路径为回路。
简单回路：有简单路径组成的回路称为简单回路
连通：在无向图G 中，若任意二个顶点之间都是连通的, 即均存在路径，则称图G 为连通图。否则称为非连通图。
连通分量：在非连通的无向图G 中，极大连通子图称为无向图的连通分量。
强连通：在有向图G 中，若顶点vi 到顶点vj 有路径存在，并且从顶点vj 到顶点vi 也有路径存在，则称vi 到vj 是强连通的。
强连通图：在有向图G 中，若任意二个顶点之间都是强连通的，则称有向图G 为强连通图。
强连通分量：在非强连通的有向图G 中，极大强连通子图称为有向图的强连通分量。
邻接矩阵（Adjacency Matrix）是表示顶点之间相邻关系的矩阵。
图的生成树是不唯一的，从不同的顶点出发得到的生成树是不同的，但是如果图是带权图，则权值之和最小的生成树是称为最小生成树。
一个无回环的有向图称为有向无环图，简称为DAG 图
关键路径：在AOE 网中，从源点到汇点的带权路径长度最长的路径称为关键路径。
关键活动：在关键路径上的弧称为关键活动
单源最短路径－求某源点到其余各顶点的最短路径
第八章 查找
查找表是由具有同一类型（属性）的数据元素（记录）组成的集合。
静态查找表：仅对查找表进行查找操作，而不改变查找表中的数据元素；
动态查找表：对查找表除进行查找操作外，可能还要进行向表中插入数据元素，或删除表中数据元素的表。 关键字：数据元素中某个数据项的值，可以标识一个数据元素。
主关键字：可以唯一标识一个数据元素。
第九章 排序
内部排序：在排序进行的过程中不使用计算机外部存储器的排序过程。
外部排序：在排序进行的过程中需要对外存进行访问的排序过程。
直接插入排序，在有序序列中插入新的记录以达到扩大有序区的长度的目的。
希尔排序又称“缩小增量排序”
冒泡排序：依次比较相邻两个记录的关键字，若和所期望的相反，则互换这两个记录
快速排序：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
简单选择排序：不断从待排序序列中挑选出关键字最小的元素，依次放在已排序子序列的最后，直到待排序序列中所有元素都被选完，从而得到一个有序的序列。
归并排序：直接将一个含有N 个元素的序列，看成N 个含有1个元素的子序列；然后对相邻子序列进行两两合并；最终得到一个有序序列。
基数排序不需要进行关键字值的比较，而是根据关键字的各位值进行排序的方法。
排序方法 时间复杂度 空间复杂性 稳定性 复杂性 平均情况 最坏情况 最好情况
插入排序 O(n2) O(n2) O(n) O(1) 稳定 简单
稳定 简单
简单
较复杂
较复杂 希尔排序 O(nlog2n) O(nlog2n) O(1) 不稳定 较复杂 冒泡排序 O(n2) O(n2) O(n) O(1) 快速排序 O(nlog2n) O(n2) O(nlog2n) 堆排序 O(log2n ) 不稳定 较复杂 不稳定 稳定 选择排序 O(n2) O(n2) O(n) O(1) 稳定 O(nlog2n) O(nlog2n) O(nlog2n) O(1) O(n) 归并排序 O(nlog2n) O(nlog2n) O(nlog2n)
基数排序 O(tn) O(tn) O(tn)
O(n) 稳定 较复杂