基本数据结构

绝大多数算法关心的是对数据的操作，组织数据的特殊方法在算法的设计和分析中扮演了一个至关重要的角色。

数据结构定义为对相关的数据项进行组织的特殊方案，数据项的范围可以从基础的数据类型（例如，整数和字符）到数据结构（例如，以一维数组为元素的一堆数组来实现的矩阵）。

线性数据结构

两种最重要的基本数据结构是数组和链表。（一维）数组是n个相同数据类型的元素构成的序列，并且连续存储在计算机的存储器中，通过指定数组的下标来访问其中的元素。

访问数组任何元素的时间都是相等的且为常量。数组中每个元素占据相同的计算机存储空间。

数组可以实现串这个数据结构。串是字符序列，并以一定特殊字符标示串的结束。串的常见操作包括计算串长度，按照字典序比较两个串的优先顺序，以及连接两个串。

链表是0个或者多个称为节点的元素构成的序列，每个节点包含两类信息：一些数据，以及一个或多个称为指针的链接，指向表中其他元素，最后一个节点用null的特殊指针结束。

单链表如下

访问链表特定元素，从链表的第一个元素开始，沿着一系列指针前进，直到访问到该特定元素为止。所以，访问单链表中的元素需要的时间有赖于钙元素在链表中所处的位置。

链表一个有点是插入和删除其中的元素方便，链表不需要事先分配任何存储空间，通过重新链接相关指针来完成。

双链表是链表的扩展结构，除了第一个和最末一个节点，每一个节点都既包含指向前趋的指针又包含指向后继的指针。

线性列表（简称列表）是一种更抽象的数据结构。列表是由数据项构成的有限序列，按照一定的线性顺序，排列而成的数据项的集合。在列表上进行的基本操作包括对元素的查找，插入和删除。

栈和队列是特殊类型的列表。

栈是一种插入和删除操作都只能在尾端进行的列表。这一端被称为栈顶，按照一种“后进先出”（LIFO，last-in-first-out）的方式运转，类似我们对于一叠盘子所做的操作，我们只能移走最顶上的盘子，或者在一叠盘子的顶部再加上一个盘子。栈对于实现递归算法是不可缺少的。

队列也是一种列表，只是删除元素再列表的一头进行，称为队头(这种操作称为出队)；插入元素再表的另一头进行，称为队尾(这种操作叫入队).按照一种“先进先出”（FIFO，first-in-first-out)的方式运行的（就像顾客排队）。队列应用于一些图问题的算法。

有时候要从一个动态改变的候选集合中选择一个优先级最高的元素。满足这类应用的数据结构称为优先队列。优先队列是数据项的集合，数据项来自于一些全序域（最常见的是整数或实数）。对优先队列的主要操作是找到最大元素，删除最大元素和插入一个新元素。后两种操作会产生一个新队列。

实现优先队列一个比较好的方法是基于一种称为堆的构思精巧的数据结构。6.4节中讨论堆（以及一个基于堆的重要排序算法）。

图

按照非正式的定义，图可以认为是平面上的“顶点”或者“节点”构成的集合，顶点被称为“边”或者“弧”的线段连接。按照正式的定义，一个图G=<V, E>由两个集合定义：元素被称为顶点的有限集合V；另一个元素是一对顶点，被称为边的优先集合。若每对顶点之间没有顺序，即顶点对(u, v)和顶点对(v, u)是相同的，则说图G是无向的；否则，边(u, v)的方向是从顶点u到顶点v，图本身为有向的。

为方便期间，通常图或者有向图的顶点标上字母或整数，抑或按照应用的要求标上字符串。图a包含6个顶点和7条边：

V = {a, b, c, d, e, f} E = {(a, c), (a, d), (b, c), (b, f), (c, e), (d, e), (e, f)}.

图b中包含6个顶点和8条有向边：

V = {a, b, c, d, e, f} E = {(a, c), (b, c), (b, f), (c, e), (d, a), (d, e), (e, c), (e, f)}

图的表示

计算机算法中，图用两种方法表示：邻接矩阵和邻接链表。n个顶点的邻接矩阵是一个nxn的布尔矩阵，图中每个顶点用一行和一列来表示，第i个顶点到第j个顶点之间有连接边，则矩阵中第i行第j列的元素等于1，若没有这样的边，则等于0.参见图a

观察图a发现，无向图的邻接矩阵总是对称的，即当i≧0，j≦n-1时，A[i, j]=A[j, i].

邻接链表每一个顶点用一个包含了和这个顶点邻接的所有顶点（所有和该顶点有边相连的顶点）的链表表示。上图b的邻接链表参见图b。

对于一个给定的顶点，它的邻接链表指出了邻接矩阵中值为1的列。

稀疏图的邻接链表占用的空间少于邻接矩阵；稠密图，情况正好相反。一般来说，采用哪种表示法更方便取决于问题的性质，用哪种算法来解决问题，或者输入图是稀疏的还是稠密的。

加权图

加权图是给边赋了值的图。这些值称为边的权重或成本.一些应用需要用到加权图，比如寻找交通网络或者饿通讯网络两点间的最短路径，又比如前面提到过的旅行商问题。

图两种表示方法都可以表示加权图。矩阵元素A[i, j]可以包含这条边的权重；当不存在这样一条边时，会包含一个特殊符号，例如∞。图b展示了这种方法。

加权图的邻接链表在它们的节点不仅包含邻接节点的名字，还必须包含相应的边的权重，如图c。

路径和环

图有两个特性对于大量的应用是非常重要的:连通性和无环性.两者都基于路径de概念。

顶点u到顶点v的路径可以这样定义：它是图G中始于u止于v的邻接顶点序列。一条路径上所有的边都是互不相同的，这条路径是简单路径.路径的长度是定义路径的顶点序列中包含的顶点数目减一，恰好和路径所包含的边的数目一致。

上图中，a, c, b, f是从a到f的长度为3的简单路径(4-1); a, c, e, c, b, f是从a到f的长度为5的路径(6-1)(非简单路径).

有向图有有向路径。图b中，a, c, e, f是a到f的一条有向路径。

非正式来讲，连通性意味着：如果我们把连通图的模型定义为代表边的绳子连接着代表顶点的小球，我们只要抓住任意一个小球就能把所有的东西一手抓住。如果图是非连通的，每一个自我连接的每一部分，称为该图的连通分量.正式来讲，连通分量是给定图的极大连通子图。图1.9有连哥哥连通分量，分别包含顶点{a, b, c, d, e}和{f, g, h, i}

现实应用中常常出现包含若干连通分量的图。

直到所考虑的图是否包含回路是非常重要的。回路是起点和终点都是同一顶点的，长度大于0的简单路径。例如，f, h, i, g, f是图1.9的回路。不包含回路的图称为无环图.

树

树是连通无环图(能一手抓起且无环).参见图a.

无环但不连通的图称为森林：它的每一个连通分量是一棵树，参见图b。

树是特殊的图，特殊之处在于树的边数总是比它的顶点数少一：

这个公式也可以作为检验连通图是否包含回路的简便方法。

有根树

树的另外一个重要特性是：树的任意两点之间总是简单路径，即边是不重复的额。这个性质使得树可以转化为有根树：任选自由树中的额一个顶点，将它作为所谓有根树的根.在对有根树的描述中，根常常放在最顶上（树的第0层），邻接根的顶点放在根的下面（第1层），下面是和根距离两条边的顶点（第2层），然后以此类推。图1.11是自由树到有根树的转变。

有根树远远要比自由树重要。有根树的直接应用是用来描述层次关系，从文件目录到企业的组织结构。还有一些应用，比如字典的实现，超大型数据集合的高效存储（7.4节B树）以及数据编码（9.4节哈夫曼树）。第2章中，树对于分析递归算法也是很有帮助的。

状态空间树强调两种重要的算法设计技术：回溯和分支界限(11.1节和11.2节).

对于树T中的任意顶点v，从根到该顶点的简单路径上的所有顶点都称为v的祖先.真祖先包含顶点本身呵及其所有祖先的顶点集合称为.若(u, v)是从根到顶点v的最后一条边，则u称为v的父母, v称为u的子女；相同父母的顶点称为兄弟.没有子女的顶点称为叶节点;至少有一个子女的顶点称为父节点.所有以顶点v为祖先的顶点为v的子孙.顶点v和它所有子孙称为T中以v为根的子树.

对于上图b中的树来讲，该树的根是a；顶点d, g, f, h, i是叶节点，而顶点a, b, e, c是父节点；b的父母是a；b的子女是c和g；b的兄弟是d和e；以b为根的子树中的顶点是{b, c, g, h, i}.

顶点v的深度从根到v的简单路径的长度。树的高度是从根到节点的最长简单路径的长度。例如，在上图b的树中，顶点c的深度是2，树的高度是3.因此，如果我们约定根的层数是0，从上到下地计算树的层数，顶点的深度就是它在树中的层数，树的高度就是顶点的最大层数。

有序树

有序树所有的子女都是从左到右排列的。

二叉树就为一棵有序树，其中所有顶点子女个数不超过两个，并且每个子女不是父母的左子女就是父母的右子女.一棵子树的根若是某顶点的左（右）子女，该子树称为该顶点的左(右)子树.图1.12a是一棵二叉树的例子。

将一些数字分配到二叉树的顶点的数为二叉查找树，如图b

观察图b发现，分配给父母顶点的数字比它左子树的数字大，比右子树的数字小。

二叉查找树推广为一种更一般的查找树，称为多路查找树, 这种姐哦股对于磁盘上超大型文件的高效存储是必不可少的。

有关二叉查找树的算法效率取决于这些树的高度。对于高度为h，具有n个顶点的二叉树，我们有以下不等式：

出于计算目的，二叉树由一个代表树的顶点的节点集合来表示。每个节点包含一些相关顶点的信息（顶点的值或顶点的名字）和两个分别指向该节点的左子女和右子女的指针。图1.13是上图b中二叉查找树的标准实现。

在计算机中，任意一棵有序树可以简单地表示为一个父节点和与子女相同数量的指针。不同节点的子女数目相差很大，这种表示法将变得很不方便。

为了避免这种不便, 引用先子女后兄弟表示法:左指针指向节点第一个子女，右指针指向节点下一个兄弟。将有序树变成二叉树的样式，所有兄弟都被一个单独的链表（通过节点的右指针）链接起来，该链表的第一个元素被父节点的左指针指着。

上图b中的树应用了这种表示法以后，变成图a的样子。

图a是图b的关联二叉树。

图a的表现形式把指针顺时针“转动”45度，树变成下图b的形式。

集合与字典

在数学中，集合是互不相同的几何元素的无序组合（可以为空）。两种形式表示：直接用元素列表来定义（例如，S＝{2, 3, 5, 7})或指出集合所有元素都满足的特性（例如，S={n:n为质数且n < 10}).

集合的运算包括：检查给定项是不是在集合的元素当中，两个集合的并集，两个集合的交集。

在计算机中，集合用两种方法实现。

第一种方法，只考虑通用集合U的子集。集合U具有n个元素，U的任何子集S能够用一个长度为n的位串来表示，称为位向量;当且仅当U的第i个元素包含在S中时，向量中第i个元素为1。举个例子，如果U={1, 2, 3, 4, 5, 6, 7, 8, 9}, 那么S={2, 3, 5, 7}用位串011010100表示。这种表示法使得非常快速的标准集合运算成为可能。

出于计算目的表示集合，常用的是第二种方法：用线性列表的结构表示集合元素。

集合和列表两个主要差别，第一，集合不能包含相同的元素，而列表可以，可以引进多重集或者包的概念，绕过对唯一性的要求，多重集和包是可重复项的无序组合。第二，集合是元素的无序组合，改变元素的顺序不会改变集合，但是会改变列表。

提醒一点，如果用线性表来表示一个集合，根据手头应用的情况，维护线性表的有序排列是必要的。

在计算领域，对集合或者多重集做的最多的操作，就是从集合中查找一个给定元素，增加新元素和删除一个元素。能够实现这三种操作的数据结构称为字典.

字典处理的是动态内容查找，因此，必须在查找的效率和其他两种操作的效率之间达到一种平衡。实现字典有许多方法，从简单地使用数组到类似散列法和平衡查找树的复杂技术。

计算方面应用要求动态地把n个元素的集合划分为一系列不相交的子集。把集合初始化为n个单元素的子集以后，再对它做一系列合并和查找的操作。这个问题称为集合合并问题.9.2节讨论一个高效算法Kruskal算法。

对于基本数据结构，总是提到对这些数据结构通常所做的特定操作。数据和操作之间有种紧密关系诞生了抽象数据类型(abstract data type, ADT)。抽象数据类型是由一个表示数据项的抽象对象集合和一系列对这些对象所做的操作构成的。优先队列和字典的都是抽象数据类型的重要例子。C++和Java这样的面向对象语言来实现要更为方便，这些语言用类来支持抽象数据类型的表示。