针指向队尾, front 指针指向队头。
队列是“先进行出”( FIFO)或“后进后出”( LILO )的线性表。
队列运算包括 (1)入队运算: 从队尾插入一个元素; ( 2)退队运算: 从队头删除一个元素。
循环队列: s=0 表示队列空, s=1 且 front=rear 表示队列满
1.5 线性链表
数据结构中的每一个结点对应于一个存储单元,这种存储单元称为存储结点,简称结点。
结点由两部分组成: (1)用于存储数据元素值,称为数据域; ( 2)用于存放指针,称为指
针域,用于指向前一个或后一个结点。
在链式存储结构中, 存储数据结构的存储空间可以不连续, 各数据结点的存储顺序与数据元
素之间的逻辑关系可以不一致,而数据元素之间的逻辑关系是由指针域来确定的。
链式存储方式即可用于表示线性结构,也可用于表示非线性结构。
线性链表, HEAD称为头指针, HEAD=NULL(或 0)称为空表,如果是两指针:左指针( Llin
k)指向前件结点,右指针( Rlink )指向后件结点。
线性链表的基本运算:查找、插入、删除。
1.6 树与二 *树
树是一种简单的非线性结构,所有元素之间具有明显的层次特性。
在树结构中,每一个结点只有一个前件, 称为父结点,没有前件的结点只有一个, 称为树的
根结点,简称树的根。每一个结点可以有多个后件,称为该结点的子结点。 没有后件的结点
称为叶子结点。
在树结构中, 一个结点所拥有的后件的个数称为该结点的度, 所有结点中最大的度称为树的
度。树的最大层次称为树的深度。
二* 树的特点: (1)非空二 *树只有一个根结点; (2)每一个结点最多有两棵子树,且分别
称为该结点的左子树与右子树。
二* 树的基本性质:
(1)在二 *树的第 k 层上,最多有 2k- 1(k ≥1) 个结点;
(2)深度为 m的二 *树最多有 2m-1 个结点;
(3)度为 0 的结点(即叶子结点)总是比度为 2 的结点多一个;
(4)具有 n 个结点的二 * 树,其深度至少为 [log2n]+1, 其中 [log2n] 表示取 log2n 的整数部
分;
评论0
最新资源