0 1 2 3 C 4 D ? MaxSize-1 不可用存储空间 front↑ rear↑
图3.7.3 队列“爬过”存储空间
0 rear↑ 1 2 3 4 D front↑ ? X MaxSize-1 Y 图3.7.4 队列指针转向
0 1 2 3 4 MaxSize-1 rear↑ front↑ 图3.7.5 队列为空
0 Z 1 AA 2 BB 3 CC 4 DD ? X MaxSize-1 Y rear↑ front↑ 图3.7.6 队列为满
0 front↑ 1 A 2 B 3 C 4 D rear↑ 图3.7.7 循环队列
0 1 front↑ 2 B 3 C 4 D rear↑ 图3.7.8 循环队列
0 1 2 3 4 ? MaxSize ? MaxSize ? MaxSize front↑ ↑rear 图3.7.9 循环队列为空状态
1 2 3 4 MaxSize 0
Z B C D ? F J
rear↑ front↑
图3.7.10 循环队列
2. 队列运算
1) 判断队列是否为空
所谓队列为空，是指队列中没有数据元素，即队列队头指针和队尾指针指在同一个位置，即front=rear。
2) 判断队列是否为满
所谓队列为满，是指队列的所有数据空间已经全部用完，即队列队头指针和队尾指针的关系是：front= rear+1或1。
3) 进队运算
进队列运算是将一新元素x存储到当前rear所指空间的“下一个”位置。进队时，首先要判断队列中是否存在元素存放的空间，即先判断队列是否满，不满时，x可以进队列，否则出错。
4) 出队运算
出队运算是将队列中队头指针所指的“下一个”位置的元素取出。做法是：首先将队列队头指针front先向“下一个” 位置移动，然后，取出移动后front所指的数据元素。出队时，首先要判断队列中是否存在元素可取，即先判断队列是否空，不空时，可以出队，否则出错。
1.5 线性链表
线性表的顺序存储方式，它有着逻辑关系上相邻的两个数据元素在物理位置上也相邻的特征。因此，只要知道第一个元素的位置（即下标），则可以利用寻址公式高效地存取一个元素。但是，通过其插入，删除算法的分析也可以看出，它存在着一些缺点：
其一，在插入或删除的过程中有着大量元素的移动，运算时间较长。
其二，在为长度可变化的线性表预先分配空间时，必须按最大表长空间分配，因而造成存储空间得不到充分利用。
第三，表的空间不容易扩充。
为此，在有着频繁插入、删除运算时，不宜采用顺序存储结构。
线性链式存储结构时，物理存储空间的分配可以是静态存储空间分配，也可以是动态存储空间分配。
1. 简单线性链表
在动态链式结构中，数据元素是由两部分构成的，一是数据元素的数据域；二是数据元素的链接域。链接域指向下一个数据元素存储空间的起始地址，数据元素又被称为结点。
k
L
? ∧
e0 e1 e2 en-2 e n-1
图2.3.2 简单链表
*first *link
data Hdata
数据元素结点结构 表头结点结构
图2.3.1 数据元素及表头结点结构
当某个结点后面没有结点时（无后继结点），该结点的link值为空（用NULL，或0，或用符号∧表示）。
一个链表除了数据元素结点外，通常将这个特殊结点称为“表头结点”，表头结点的链接域的类型是指向数据结点的指针类型，表头结点的数据域可以与数据结点的数据域的类型不同，用于存放线性表的有关“综合”信息。
2. 双向链表的存储
Rlink指向直接后继结点，Llink指向直接前驱结点。链表中最后一个结点的Rlink域为NULL，第一个结点的Llink域为NULL。
这样定义后，某结点直接前驱结点地址由该结点的Llink指出，不须从表头开始追踪，提高了运算效率。由这样定义的结点组成的链表称为双向链表，因为它的每个结点均有向前、向后的指针。双向链表结点的连接如图2.4.1和图2.4.2所示。
L ∧ A ? Z ∧ B Y Llink A Rlink
图2.4.2双向链表 图2.4.1双向链表结点结构
3. 链式栈
给出了一个链式栈S的结构，表头链接域top始终指向栈顶结点，即链表的第一个结点。对链式栈，一般不存在栈满问题，除非存储空间全部被耗尽；链式栈空表现为链式栈的表头结点链接域top的值为空，即链表为空。
? top ∧ S en-1 en-2 en-3 e1 e 0
图3.3.2 链式栈
4. 链式队列
给出了一个链式队列q的结构，表头链接域front始终指向队列顶结点，即链表的第一个结点。对链式队列，一般不存在队列满问题，除非存储空间全部被耗尽；链式队列空表现为链式队列的表头结点链接域front的值为空，即链表为空。
? ∧ q头指针 front e0 e1 en-1 rear 图3.8.1 链式队列
1.5.2 线性表的基本运算
1. 简单链表L中查找元素值为X的结点
设定一个指针p，用于指向链表中的一个数据结点，当p所指的结点值等于x值时，表示已经找到了数据元素。
当p为空时，说明指针已经指到了链表的最后一个结点的后面，说明不存在这个数据结点，查找失败。
p
L ? ∧ e0 e1 e2 en-2 e n-1 图2.3.2 简单链表
2. 简单链表L中数据元素x之前插入元素b 1) 在表中找x结点的前一个结点（q指向） 2) 当找到后，在q后面插入一个新的元素p
3) 插入一个新的元素p时，将新结点数据值b填入其中，然后分别修改结点p和新结点q的链接域即可。
q
L
∧ ?
ek-1 x en-2 e n-1
p
b (b) 插入后
图2.3.3 简单链表插入
3. 从简单链表中删除一个数据元素
只要将x的直接前驱元素q找到，然后对q的链接域作下述修改，即执行： q->link=current->link
的操作就可以删除结点p。实际上，它是将p的直接前驱结点q的链接指针直指p的直接后继元素结点。链表中的被删除结点从链表中断开后，还要将结点空间释放。
q p L ? ? ∧ ek-2 x ek en-2 e n-1 (b) 删除后 图2.3.4 删除链表中结点
1.5.3 单向循环链表的存储及其运算
若将最后一个结点的链接域值定义为指向开头（表头结点或第一个数据结点）。则形成一个环，称为单向循环链表或称为循环链表。如图2.5.1所示。
p L L ? e0 e1 e2 en-2 e n-1 图2.5.1 单向循环链表（循环至表头）及空表
特点：
表头指针指向第一结点，最后一个结点的指针不为空，指向表头结点。所有结点指针构成一个环。链表为空时，表头指针指向自身。
1.6 树与二叉树
1.6.1 树的基本概念
定义：一棵树是非空的有限元素的集合T，其中： ? 有一个元素称为该树的根（root）。
? 除根以外，其余元素（如果存在）分成k≥0个不相交的集合T1，T2，?，Tk 。而每一个集合Ti又都是树。树 T1，T2，……，Tk 称为根的子树。
树是一种简单的非线性结构 学院
工信金人会财法商息融文计税 学学学学学学学院 院院院院院院
计信统 算息计机 系系系
图5.1.1 一棵学院信息的
结点的度：一个结点的子树的个数称为该结点的度。即一个结点的分枝数。 树的度：树中各结点的度的最大值称为该树的度。 终端结点（叶子结点）：度为零的结点称为终端结点或叶结点。 分支结点：度不为零的结点称为分枝结点。
孩子和双亲：某结点的子树的根结点为该结点的孩子，反之该结点为孩子的双亲（也称