3． 顺序队的队空、队满 ① 队空条件：q.front=q.rear ② 队满条件：q.rear=maxsize-1 队真满：q.front＝-1;
q.rear＝maxsize-1
队假满：q.front≠ -1;
q.rear＝maxsize-1
4．顺序队的插入、删除操作
① 插入新元素：rear后移而front不变 q.rear=q.rear+1; q.data[q.rear]=x;
② 删除元素：front后移而rear不变
q.front=q.front+1; 三、循环队
1．为充分利用存储空间，克服“假满”，可以把数组看作首尾相接的圆环，形成“循环队”。 2．循环队的性质
① 存储单元的编号从0开始，按顺时针方向，编号逐渐增大，最后一个存储单元的编号为maxsize-1。
② 在循环队中，当q.rear=maxsize-1时，只要数组有两个以上的存储单元为空，就可以把新元素插入到空单元中。
③ 当队列中元素的个数为maxsize-1时，就认为队满。 3．循环队的插入、删除操作
① 插入新元素：rear顺时针移动而front不变 q.rear=(q.rear+1)% maxsize;
q.data[q.rear]=x;
② 删除元素：front顺时针移动而rear不变
q.front=(q.front+1)%maxsize; 4．循环队的队空、队满
队空条件：q.front=q.rear
队满条件：(q.rear+1)% maxsize=q.front 四、队列的链式存储结构 1．链队的类型定义
① 链队是一个含有队头指针front和队尾指针rear的单链表； ② front指向队头结点的前一个结点，rear指向队尾结点；
11
③ 链队由包含front和rear的结构变量lq标识。 typedef struct node_st { 类型 data; struct node_st *next; } node; typedef struct { node *front; node * rear; } linkqueue;
linkqueue lq;
2．链队的建立（尾插入法）
例：为Q=（'a'，'b'，'c'，'d'，??）创建一个链队。#include \#include \typedef struct node_st { char data;
struct node_st *next; } node; typedef struct { node *front; node * rear; } linkqueue; void main() { char ch; linkqueue lq; node *p;
p=malloc(sizeof(node)); p->next=NULL; lq.front=p; lq.rear=p; ch=getchar(); while(ch!='\\n')
{ p=malloc(sizeof(node)); p->data=ch;
12
p->next=NULL; lq.rear->next=p; lq.rear=p; ch=getchar();
}
//输出队列中的元素 p=lq.front->next; while(p!=NULL) { printf(\ p=p->next; }
printf(\}
3．链队的队空条件
lq.front=lq.rear
4． 各式链式存储结构比较表 链表 链栈 链队
第6章 树和二叉树 6．1 树的定义和基本操作
一、树型结构和线性结构
树型结构：每个结点可以有多个直接后继 线性结构：每个结点只有一个直接后继 二、树的定义
树是n（n≥0）个结点的有限集合，任意一棵非空树满足： ① 有且只有一个根结点；
② 其余结点被分成若干个互不相交的集合，每个集合又是一棵树。 三、树的特点
① 除根结点外，每个结点有且只有一个直接前趋； ② 除最底层的结点外，每个结点可以有多个直接后继；
③ 若某棵树有多个结点，则每个结点可以看作根结点，要么是整棵树的根结点，要么是某
有无头结点 有 无 有 用何指针标识 头指针head 栈顶指针top 由包含front和rear的结构变量lq标识。 创建办法 尾插入法 头插入法 尾插入法 13
棵子树的根结点。 四、基本术语 ① 结点的度、树的度 ② 叶子结点、分支结点
度为0的结点称为叶子结点；度大于0的结点称为分支结点。 ③ 孩子结点、双亲结点、兄弟结点
具有同一双亲的结点互为兄弟 ④ 结点的子孙、结点的祖先 ⑤ 结点的层数、树的高度
结点的层数：从树根开始算起，根的层数为1； 树的高度：树中所有结点层数的最大值。
6．2 二叉树
一、二叉树的定义：参考P73 二、二叉树的性质
（1）二叉树的第i层上最多有2i?1个结点。
（2）深度为k的二叉树最多有2k?1个结点。
（3）满二叉树：除最底层的结点外，其余结点的度均为2的二叉树。
（4）完全二叉树：如果对一棵满二叉树的最底层从最右边开始，连续删去若干个结点，就得到完全二叉树。
（5）对一棵完全二叉树的结点进行编号，则对编号为i的结点，其左孩子的编号为2i，右孩子的编号为2i+1，双亲结点的编号为三、二叉树的存储结构 1．顺序存储结构：
◆先将二叉树的结点依次编号，再将结点存入一维数组中，数组元素的序号对应结点的编号。
◆对二叉树的结点进行编号，编号原则是： ① 根结点的编号为1。
② 对于编号为i的结点，其左孩子的编号为2i，右孩子的编号为2i+1。
◆ 满二叉树、完全二叉树一般采用顺序存储结构，一般二叉树则采用链式存储结构。 2．链式存储结构：
① 二叉链表：每个结点包括三个域： 数据域data，左指针域lchild，右指针域rchild
② 对二叉树的访问只能从根指针root开始，二叉树为空的条件：root=NULL。
14
?i2?
四、二叉树的遍历 1．什么叫二叉树的遍历？
按照一定规律访问二叉树的所有结点，使得每个结点均被访问一次且仅被访问一次。 2．二叉树由三部分组成：
根结点、左子树、右子树 3．三种遍历次序
① 先根遍历：根结点、左子树、右子树 ② 中根遍历：左子树、根结点、右子树 ③ 后根遍历：左子树、右子树、根结点
6．3 树和森林
一、对树中各结点编号
从根结点开始，按层依次编号，且根结点的编号为0。 二、树的存储结构 双亲链表 孩子链表 孩子兄弟链表 1．双亲链表
（1）每个结点包含两个域名：
数据域：存放该结点的数据元素 指针域：存放该结点之双亲的编号
（2）将所有结点组织成一维数组，并以各结点的编号作为数组元素的序号。 2．孩子链表
（1）为每个结点建立一个“孩子链表”。
（2）结点x的孩子链表是一个带头结点的单链表，用于存储该结点的所有孩子的编号。 （3）将所有头结点组织成一维数组。 3．孩子兄弟链表
（1）每个结点含有三个域：
数据域：存放该结点的数据元素 孩子域：用于指向该结点的第一个孩子 兄弟域：用于指向该结点的第一个兄弟
（2）二叉树的二叉链表与树的孩子兄弟链表在组织结构完全相同。 二叉链表 数据域 孩子兄弟链表 数据域 15