队列是只允许在一端进行删除,在另一端进行插入的顺序表,通常将允许删除的
这一端称为队头,允许插入的这一端称为队尾。当表中没有元素时称为空队列。
队列的修改是依照先进先出的原则进行的,因此队列也称为先进先出的线性表,
或者后进后出的线性表。例如:火车进遂道,最先进遂道的是火车头,最后是火
车尾,而火车出遂道的时候也是火车头先出,最后出的是火车尾。若有队列:
Q =(q1,q2,…,qn)
那么,
q1
为队头元素(排头元素),
qn
为队尾元素。队列中的元素是按照
q1
,
q2
,…,
qn
的顺序进入的,退出队列也只能按照这个次序依次退出,即只有在
q1
,
q2
,…,
qn-1
都退队之后,
qn
才能退出队列。因最先进入队列的元素将最
先出队,所以队列具有先进先出的特性,体现“先来先服务”的原则。
队头元素
q1
是最先被插入的元素,也是最先被删除的元素。队尾元素
qn
是最后
被插入的元素,也是最后被删除的元素。因此,与栈相反,队列又称为“先进先
出”(
First In First Out
,简称
FIFO
) 或“后进后出”(
Last In Last Out
,简称
LILO
)
的线性表。
2.
队列运算
入队运算是往队列队尾插入一个数据元素;退队运算是从队列的队头删除一个数
据元素。
队列的顺序存储结构一般采用队列循环的形式。循环队列
s=0
表示队列空;
s=1
且
front=rear
表示队列满。计算循环队列的元素个数:“尾指针减头指针”,
若为负数,再加其容量即可。
1.5
链表
在链式存储方式中,要求每个结点由两部分组成:一部分用于存放数据元素值,
称为数据域;另一部分用于存放指针,称为指针域。其中指针用于指向该结点的
前一个或后一个结点(即前件或后件)。
链式存储方式既可用于表示线性结构,也可用于表示非线性结构。
(
1
)线性链表
线性表的链式存储结构称为线性链表。
在某些应用中,对线性链表中的每个结点设置两个指针,一个称为左指针,用以
指向其前件结点;另一个称为右指针,用以指向其后件结点。这样的表称为双向
链表。
在线性链表中,各数据元素结点的存储空间可以是不连续的,且各数据元素的存
储顺序与逻辑顺序可以不一致。在线性链表中进行插入与删除,不需要移动链表
中的元素。
线性单链表中,
HEAD
称为头指针,
HEAD=NULL
(或
0
)称为空表。
如果是双项链表的两指针:左指针(
Llink
)指向前件结点,右指针(
Rlink
)指
向后件结点。
线性链表的基本运算:查找、插入、删除。
(
2
)带链的栈
栈也是线性表,也可以采用链式存储结构。带链的栈可以用来收集计算机存储空
间中所有空闲的存储结点,这种带链的栈称为可利用栈。
1.6
二叉树
1.6.1
二叉树概念及其基本性质
1.
二叉树及其基本概念
二叉树是一种很有用的非线性结构,具有以下两个特点: