数据结构：一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。

数据：数据是信息的载体，是描述客观事物属性的数、字符以及所有能输入到计算机中并被计算机程序处理的符号的集合。

数据元素：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据类型：是一个值的集合和定义在此集合上一组操作的总称。包括

原子类型：其值不可在分的数据类型

结构类型：其值可以在分解为若干成分的数据类型

抽象数据类型：ADT，指一个数学模型以及定义在该模型上的一组操作。通常用数据对象、数据关系、基本操作集这样的三元组来表示。有数据抽象和数据封装两个重要特性。

数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。包括（逻辑结构、存储结构和数据的运算）。

数据的逻辑结构：指数据元素之间的逻辑关系。包括集合、线性结构、树形结构、图状结构或网状结构。

数据的存储结构：指数据结构在计算机中的表示，也成物理结构。主要有顺序存储、连接存储、索引存储、散列存储。

数据的运算：施加在数据上的运算包括运算的定义和实现。定义是针对逻辑结构，指出运算的功能。实现是针对存储结构的，指出运算的具体操作步骤。

算法：对特定问题求解步骤的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。有5个重要特性（有穷性、确定性、可行性、输入、输出）

算法设计的要求：正确性、可读性、健壮性、效率与低存储量需求。

时间复杂度：一般情况下，算法中基本操作的重复次数是问题规模n的某个函数f（n），算法的时间度量记作T（n）=O（f（n）），表示随着问题规模n的增大，算法执行时间增长率和f（n）的增长率相同，称为时间复杂度。

空间复杂度：S（n）定义为该算法所耗费的村粗空间，是问题规模n的函数。

第二章：线性表

线性表：具有相同数据类型的n（n>=0）个数据元素的有限序列。

线性表的顺序存储又称顺序表；链式存储又称单链表。

静态链表：借助数组来描述线性表的链式存储结构，结点也有数据域和指针域。但指针是结点的相对地址（数组下标）。需要预先分配连续的内存空间。

栈：限定在表尾进行插入或删除操作的线性表。操作端称为栈顶，后进先出

队列：一种先进先出的线性表，只允许在表的一段插入元素，另一端删除元素，在队列中允许插入的一端为队尾，允许删除的一端为队头。

串：由零个或者多个字符组成的有限序列。串中任意个连续的字符组成的子序列称为该串的子串。字符在序列中的序号为该字符的位置。

树的结点包括一个数据元素以及若干指向其子树的分支。结点拥有的子树称为结点的度。度为0的结点称为叶子或终端结点。树的度是树内个结点的度的最大值。结点的子树的根称为该结点的孩子，相应的该节点为孩子的双亲。同一个双亲的孩子之间互称兄弟。结点的祖先是从根到该结点的所经分支上的所有结点。反之，以某结点为根的子树中任一结点都称为该结点的子孙。

结点的层次：从树根开始定义，根结点为第1层，它的子结点为第2层，以此类推。 树的高度或深度：树中结点的最大层数。

有序树和无序树：树中结点的子树从左到右是有次序的，不能交换，叫做有序树。反之为无序树。



路径和路径长度：树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的。路径长度是路径上经过的边的个数。

树的路径长度：树根到每一个结点的路径长度之和

树的带权路径长度（WPL）：树中所有叶子结点的带权路径长度之和。

哈夫曼树：在含有N个带权叶子结点的二叉树中，其中带权路径长度（WPL）最小的二叉树称为哈夫曼树或最优二叉树。

哈夫曼编码：一种广泛应用而且非常有效的数据压缩编码。

森林：m（m>=0）棵互不相交的树的集合。

二叉树：是另一种树形结构，每个结点至多有两棵子树，并且，二叉树的子树有左右之分，其次序不能任意颠倒。

满二叉树：一棵高度为h，并且含有2^h -1个结点的二叉树称为满二叉树。即每层都有最多的结点，叶子集中在二叉树的最下一层且除叶子之外的每个结点度为2.

完全二叉树：设一个高度为h，有n个结点的二叉树，当且仅当其每一个结点都与高度为h的满二叉树中编号为1-n的结点一一对应时，称为完全二叉树。

二叉排序树：一棵二叉树或是空二叉树或是具有以下性质的二叉树：左子树上所有关键字均小于根结点的关键字，右子树所有结点关键字大于根结点的关键字。左子树和右子树又各是一棵二叉排序树。

平衡二叉树：树上任一结点的左子树和右子树的深度之差不超过1.

平衡因子：该结点的左子树深度减去它的右子树深度。

二叉树的遍历：指按某条搜索路径访问树中的每个结点，使得每个结点均被访问一次且仅被访问一次。

线索二叉树：若结点有左（右）子树，则其lchild（rchild）域指向其左（右）孩子，否则令lchild（rchild）域指向其前驱（后继），这种结点构成的二叉链表作为二叉树的存储结构称为二叉链表。其中指向结点前驱和后继的指针叫做线索。加上线索的二叉树称为线索二叉树。对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化。

判定树：树中每个结点表示表中的一个记录，结点里的值为该记录在表中的位置，通常称这个查找过程的二叉树为判定树。

树的先根遍历：若树非空，则先访问根结点，再按从左到右的顺序遍历根节点的每一颗子树。其访问顺序与这棵树对应的二叉树的线序遍历顺序相同。

树的后跟遍历：若树非空，则按从左到右的顺序遍历根结点的每一棵子树，之后再访问根结点。其访问顺序与其对应的二叉树的中序遍历相同。

先序遍历森林：若森林非空，则按如下规则遍历：

·访问森林第一棵树的根结点

·选序遍历第一棵树中根结点的子树森林

·线序遍历除去第一棵树之后剩余的树构成的森林

中序遍历森林：若森林非空，则按如下规则进行遍历：

·中序遍历森林中第一棵树的根结点的子树森林

·访问第一棵树的根结点

·中序遍历除去第一棵树之后剩余的树构成的森林

图：由顶点集V和边集E组成，记作G=(V,E)

有向图：E为有向边的有限集合时，图G为有向图

无向图：E为无向边的有限集合时，图G为无向图

简单图：不存在重复边，不存在定点到自身的边称图G为简单图。与多重图相对 完全图：在无向图中，若任意两个顶点之间都存在边，则称该图为无向完全图。具有

n*（n-1）/2条边。有向图中，若任意两个顶点之间存在方向相反的两条弧，称为有向完全图，含有n（n-1）条有向边。

连通：若从顶点v到顶点w存在路径，则v和w是联通的。若图G中任意两个顶点都是联通的，则称图G为连通图，否则非连通图。无向图中的极大连通子图称为连通分量。

在有向图中，若从V到顶点W和从顶点W到顶点V都存在路径，则称两个顶点是强连通的，若图中任一对顶点都是强连通的，则称为强连通图。有向图中的极大强连通子图称为有向图的强连通分量。

生成树和生成森林：连通图的生成树是包含图中所有顶点的一个极小连通子图。若顶点为n则含有n-1条边。非连通图中，连通分量的生成树构成生成森林

最小生成树：一个带权连通无向图的生成树中边的权值之和最小的那个叫做此图的最小生成树。

有向树：如果一个有向图恰有一个顶点的入度为0，其余顶点的入度为1，则是一棵有向树。 路径、路径长度和回路：顶点V到顶点Q之间的一条路径是指之间的一个顶点序列。路径的长度是路径上边的数目。第一个顶点和最后一个顶点相同的路径称为回路或环。

最短路径：带权图中，从一个顶点V0到另一个顶点V1的一条路径上所经过边的权值之和定义为该路径的带权路径长度，其中最短的那条称作最短路径。此路径的长度称为从v到u的距离。

图的遍历：从图中某一顶点出发，按照某种搜索方法沿着图中的边对图中所有顶点访问一次且仅访问一次。

深度优先搜索：类似于树的先序遍历，假设从图中某顶点V出发，在访问了V之后一次从V的未被访问的邻接点出发做深度优先遍历，知道图中所有和v有路径相同的顶点都被访问到。若图中还有顶点未访问，则另选图中一个未曾被方位的顶点作为起始点，重复上述过程，直至图中所有顶点都被访问。

广度优先搜索：类似于树的层次遍历，从顶点v出发，访问了V之后依次访问v的各个未被访问过的邻接顶点。再依次访问它们的邻接点，并使先被访问的顶点的的邻接点先于后访问的顶点的邻接点。直到图中所有已被访问顶点的邻接点都被访问到。如果图中还有顶点未被访问，则另选一个未被访问的顶点作为起始点，重复上述过程，直到图中所有顶点都被访问。 AOV网，用有向无环图表示一个工程，顶点表示活动，有向边<Vi，Vj>表示Vi必须先于Vj进行的关系。则称为AOV网。

AOE网，在带权有向图中，以顶点表示事件，有向边表示活动，边上的权值表示完成该活动的开销（如时间），则称这个网络为AOE网。

关键路径：在AOE网中，路径长度最长的路径叫做关键路径，关键路径上的所有活动都是关键活动。

拓扑排序：由一个有向无环图的顶点组成的序列，当且仅当满足下列条件，称为该图的一个拓扑排序——1，每个顶点出现且仅出现一次。2若顶点a在b之前，不存在b到a的路径。 查找：在数据集合中寻找满足某种条件的数据元素的过程称为查找。

查找表（查找结构）：用于查找的数据集合称为查找表。

静态查找表：如果一个查找表的操作仅涉及查询某个特定的数据元素是否在查找表中和检索满足条件的某个特定的数据元素的各种属性，则称为静态查找表。

动态查找表：需要动态的插入或删除的查找表称为动态查找表。

关键字：数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找结果应该是唯一的。

平均查找长度（ASL）：在查找的过程中，一次查找的长度指需要比较的关键字次数，而平均查找长度则是所有查找过程中进行关键字的比较次数的平均值。

折半查找：仅适用于有序的顺序表。将给定的值key与表中间位置元素的关键字比较，相等则查找成功返回位置。若不等则缩小查找范围，重复查找直到找到或者确定表中没有需查找的元素。

散列函数：一个把查找表中的关键字映射成该关键字对应的地址的函数，

冲突：散列函数可能会把两个或以上的不同关键字映射到同一地址，这种情况为冲突

散列表：是根据关键字而直接进行访问的数据结构。散列表建立了关键字和存储地址指间的一种直接映射关系。

开放定址法：指的是可存放新表项的空闲地址既向它的同义词表项开放，又向它的非同义词表项开放。

拉链法（链地址法）：把所有的同义词存储在一个线性链表中，这个线性链表由其散列地址唯一标识。

装填因子：是哈希表中填入的记录数和哈希表的长度之商，哈希表的平均查找长度是装填因子的函数，不是规模的函数。（散列表的查找效率取决于三个因素：散列函数/处理冲突的方法和装填因子）

二次聚集：指在处理冲突过程中发生的两个第一个哈希地址不同的记录争夺同一个后继哈希地址的现象。

第十章：内部排序

排序：重新排列表中的元素，使表中的元素满足按关键字递增或递减的过程。

算法的稳定性：假设Ri=Rj，且在排序之前Ri领先于Rj，若在排序后的序列中Ri仍然领先于Rj，则称所用的排序算法是稳定的，反之则称所用的算法是不稳定的。

内部排序：排序期间元素全部存放在内存中的排序；外部排序是指在排序期间元素无法全部同时存放在内存中，必须在排序的过程中根据要求不断的在内外存指间移动的排序。

插入排序：每次将一个待排序的记录，按关键字大小插入到前面已经排好序的子序列中，直至全部记录插入完成。

希尔排序：又称缩小增量排序，先将整个记录序列分割成若干子序列分别进行直接插入排序，待整个序列中记录基本有序时，再对全体进行一次直接插入排序。

冒泡排序：从前往后（或从后往前）两两比较相邻元素的值，若为逆序则交换，知道序列比较完，既完成一趟冒泡排序。这一趟确定的最小元素不再参与比较，重复上述过程直到一趟排序没有记录交换。

快速排序：通过一趟排序将带排记录分割成独立两部分，其中一部分的关键字均比另一部分小，分别对两部分再进行快速排序直至整个序列有序

选择排序：每一趟在未排序的记录中选择最小的记录作为有序序列部分的下一个记录。 归并排序：将两个或两个以上的有序表组合成一个新的有序表。二路归并排序的核心操作是将一维数组中前后相邻的两个有序序列归并为一个有序序列。

基数排序：采用多关键字排序思想，借助“分配/收集”两种操作对但逻辑关键字进行排序。 堆排序：一种树形选择排序方法。在排序过程中把L[1...N]堪称一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲和孩子之间的关系，在当前无序区选择最大或最小的元素。 堆：n个关键字序列L[1...n]称为堆，当却仅当该序列满足：1，L（i）<=L(2i)且L（i）<=L(2i)或者2，L（i）>=L(2i)且L(i)<=L(2i)。