2.3 常见的数据结构
常见的数据结构包括线性表（Linear List）、栈、队列、树及图。
2.3.1 线性表
1.定义
线性表是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。数据元素是一个抽象的符号，其具体含义在不同的情况下一般不同。
在稍复杂的线性表中一个数据元素可由多个数据项（Item）组成，此种情况下常把数据元素称为“记录”（Record），含有大量记录的线性表又称为“文件”（File）。
线性表中的个数n定义为线性表的长度，n=0时称为“空表”。在非空表中每个数据元素都有一个确定的位置，如用ai表示数据元素，则i为数据元素ai在线性表中的位序。
线性表的相邻元素之间存在序偶关系，如用（a1，…，ai-1，ai，ai+1，…，an）表示一个顺序表，则表中ai-1领先于ai。ai领先于ai+1，则ai-1是ai的直接前驱元素，ai+1是ai的直接后继元素。当i=1，2，…，n-1时，ai有且仅有一个直接后继元素；当i=2，3，…，n时，ai有且仅有一个直接前驱元素。
2.分类
我们说线性和非线性只在逻辑层次上讨论，而不考虑存储层次，所以双向链表和循环链表依旧是线性表。
在数据结构的逻辑层次上细分，线性表可分为一般线性表和受限线性表。一般线性表也就是我们通常所说的线性表，可以自由删除或添加节点；受限线性表主要包括栈和队列，受限表示对节点的操作受限制。
3.特征
线性表有如下基本特征。
（1）集合中必存在唯一的一个第1元素。
（2）集合中必存在唯一的一个最后元素。
（3）除最后一个元素之外均有唯一的后继（后件）。
（4）除第1个元素之外均有唯一的前驱（前件）。
4.存储结构
线性表主要由顺序表示或链式表示，在实际应用中常以栈、队列、字符串等特殊形式使用。
顺序表示只用一组地址连续的存储单元依次存储线性表中的数据元素，称为“线性表的顺序存储结构”或“顺序映像”（Sequential Mapping）。它以物理位置相邻来表示线性表中数据元素间的逻辑关系，可随机存取表中任一元素。
链式表示指用一组任意的存储单元存储线性表中的数据元素，称为“线性表的链式存储结构”，其存储单元可以是连续的或不连续的。在表示数据元素之间的逻辑关系时，除了存储其本身的信息之外还需存储一个指示其直接后继的信息（即直接后继的存储位置），这两部分信息组成数据元素的存储映像称为“节点”（Node）。它包括两个域，其中存储数据元素信息的域称为“数据域”；存储直接后继存储位置的域称为“指针域”，指针域中存储的信息称为“指针”或“链”。
2.3.2 栈
栈是限定仅在表头执行插入和删除操作的线性表，如图2.1所示。
图2-1 栈
栈原意指存储货物或供旅客住宿的地方，可引申为仓库和中转站。引入到计算机领域中指数据暂时存储之处，所以才有入栈和出栈的说法。首先系统或者数据结构栈中数据的压入（Push）是增加数据，弹出（Pop）是删除数据。这些操作只能从栈顶，即最低地址作为约束的接口界面开始，但读取栈中的数据没有接口约束之说。系统栈在计算机体系结构中起到一个跨部件交互媒介区域的作用，即CPU与内存的交流通道。CPU只从系统应用程序所规定的栈入口线性地读取并执行指令，用一个形象的词来形容它就是“pipeline”（管道线或流水线）。
栈作为一种数据结构，是一种只能在一端执行压入和弹出操作的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底；最后进入的数据被压入栈顶，需要读数据时从栈顶开始弹出数据（最后一个数据被第1个读出）。栈具有记忆作用，栈的压入与弹出操作不需要改变栈底的指针。
栈可以用来在函数调用时存储断点，执行递归时要用到栈。
在计算机系统中栈则是一个具有以上属性的动态内存区域，程序可以将数据压入栈中，也可以将数据从栈顶弹出。在i386机器中栈顶由esp寄存器定位，压栈的操作使得栈顶的地址减小；弹出的操作使得栈顶的地址增大。
栈在程序的运行中有举足轻重的作用，最重要的是它保存了一个函数调用时所需要的维护信息。这常常称之为“堆栈帧”或者“活动记录”，其中一般包含如下信息。
（1）函数的返回地址和参数。
（2）函数的非静态局部变量及编译器自动生成的其他临时变量。
2.3.3 队列
队列是一种特殊的线性表，它只允许在表的前端（Front）执行删除操作，而在表的后端（Rear）执行插入操作。和栈一样，队列是一种操作受限制的线性表。执行插入操作的端称为“队尾”，执行删除操作的端称为“队头”。队列中没有元素时，称为“空队列”。
队列的数据元素又称为“队列元素”。在队列中插入一个队列元素称为“入队”，从队列中删除一个队列元素称为“出队”。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为“先进先出（First In First Out，FIFO）线性表”。
1.顺序队列
建立顺序队列结构必须为其静态分配或动态申请一片连续的存储空间，并设置两个指针进行管理。一个是队头指针front，指向队头元素；另一个是队尾指针rear，指向下一个入队元素的存储位置，如图2-2所示。
图2-2 顺序队列
每次在队尾插入一个元素时rear增1，每次在队头删除一个元素时front增1。随着插入和删除操作的进行，队列元素的个数不断变化，队列所占的存储空间也在为队列结构所分配的连续空间中移动。当front=rear时，队列中没有任何元素，即空队列。当rear增加到指向分配的连续空间之外时，队列无法再插入新元素。但这时往往还有大量可用空间未被占用，这些空间是已经出队的队列元素曾经占用过的存储单元。
顺序队列中的溢出现象如下。
（1）“下溢”现象：当队列为空时，执行出队运算产生的溢出现象。这是正常现象，常作为程序控制转移的条件。
（2）“真上溢”现象：当队列满时执行进栈运算产生空间溢出的现象，这是一种出错状态，应设法避免。
（3）“假上溢”现象：由于入队和出队操作中头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能执行入队操作，该现象即假上溢现象。
2.循环队列
在实际使用队列时，为了使队列空间能重复使用，往往稍加改进队列的使用方法。即无论插入或删除，一旦rear或front指针增1时超出了所分配的队列空间，则使其指向这个连续空间的起始位置。指针从MaxSize-1增1变到0，可用取余运算rear%MaxSize和front%MaxSize来实现。这实际上是把队列空间想象成一个环形空间，其中的存储单元循环使用，用这种方法管理的队列也称为“循环队列”。除了一些简单应用之外，真正实用的队列是循环队列。
在循环队列中当队列为空时，有front=rear。而当所有队列空间全占满时，也有front=rear。为了区别这两种情况，规定循环队列最多只能有MaxSize-1个队列元素，当循环队列中只剩下一个空存储单元时队列已满。因此队列判空的条件为front=rear，而队列判满的条件为front=(rear+1)%MaxSize。
2.3.4 树
1.树（tree）的定义
树是包含n（n>=0）个节点的有穷集，说明如下。
（1）每个元素称为“节点”。
（2）有一个特定的节点称为“根节点”或“树根”（root）。
（3）除根节点之外的其余数据元素被分为m（m≥0）个互不相交的集合T1，T2，…，Tm-1，其中每一个集合Ti（1≤i≤m）本身也是一棵树，被称为原树的“子树”（subtree）。
树也可以定为由根节点和若干棵子树构成，也可以说树由一个集合及在该集合上定义的一种关系构成。集合中定义的关系为父子关系，父子关系在树的节点之间建立了一个层次结构。在这种层次结构中有一个根节点具有特殊的地位，如图2-3所示。
图2-3 树
我们可以形式地给出树的递归定义为单个节点是一棵树，树根就是该节点本身。
设T1，T2，…，Tk是树，它们的根节点分别为n1，n2，…，nk。用一个新节点n作为n1，n2，…，nk的父亲，则得到一棵新树，节点n就是新树的根。n1，n2，…，nk为一组兄弟节点，它们都是节点n的子节点，而T1，T2，…，Tk为节点n的子树。
空集合也是树，即空树，其中没有节点。
2.相关术语
（1）节点的度：一个节点含有的子树的个数称为该节点的“度”。
（2）叶节点或终端节点：度为0的节点称为“叶节点”。
（3）非终端节点或分支节点：度不为0的节点。
（4）双亲节点或父节点：若一个节点有子节点，则这个节点即其子节点的父节点。
（5）孩子节点或子节点：一个节点含有的子树的根节点即该节点的子节点。
（6）兄弟节点：具有相同父节点的节点互称为“兄弟节点”。
（7）树的度：一棵树中，最大节点的度称为“树的度”。
（8）节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，依此类推。
（9）树的高度或深度：树中节点的最大层次。
（10）堂兄弟节点：双亲在同一层的节点互为堂兄弟节点。
（11）节点的祖先：从根到该节点所经分支上的所有节点。
（12）子孙：以某节点为根的子树中任一节点都为该节点的子孙。
（13）森林：由m（m≥0）棵互不相交的树的集合称为“森林”。
3.树的种类
（1）无序树：树中任意节点的子节点之间没有顺序关系也称为“自由树”。
（2）有序树：树中任意节点的子节点之间有顺序关系。
（3）二叉树：每个节点最多含有两棵子树的树。
（4）满二叉树：一棵二叉树的节点要么是叶节点，要么有两个子节点为满二叉树，如图2-4（a）所示。
（5）完全二叉树：若设二叉树的深度为h，除第h层外，其他各层（1～h-1）的节点数都达到最大个数。第h层所有的节点都连续集中在最左边，如图2-4（b）所示。
图2-4 满二叉树和完全二叉树
（6）哈夫曼树：带权路径长度最短（即代价最小）的二叉树也称为“最优二叉树”。
2.3.5 图
1.定义
图（Graph）由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为G(V,E)。其中G表示一个图，V是图G中顶点的集合，E是图G中边的集合。
说明如下。
（1）图中的数据元素即顶点（Vertext）。
（2）在图中不允许没有顶点，若V是图的顶点的集合，那么它是非空有穷集合。
（3）图的任意两个顶点之间可能有关系，关系用边来表示，边集可以是空的。
2.常用概念
（1）无向边。
若顶点 $V_i$ 到 $V_j$ 之间的边没有方向，这条边为无向边（Edge），用无序偶对($V_iV_j$)来表示。
（2）无向图。
如果图中任意两个顶点之间的边都是无向边，则该图为无向图（Undirected Graphs）。
（3）有向边。
若从顶点 $V_i$ 到 $V_j$ 的边有方向，则这条边为有向边，也称为“弧”（Arc）。这条有向边用有序偶 $<V_i,V_j>来表示，$V_j是弧尾（Tail），$V_j$是弧头（Head）。
（4）有向图。
如果图中任意两个顶点之间的边都是有向边，这个图就是有向图。无向边用圆括号()表示，有向边用角括号<>表示。
无向图和有向图如图2-5所示。
图2-5 无向图和有向图
（5）简单图。
在图中若不存在顶点到其自身的边且同一条边不重复出现，这样的图就是简单图。