文档介绍：线性表的链式存储—链表
链式存储不要求逻辑上相邻的数据元素在物理位置上也相邻,仅通过指针来映射数据元素之间的逻辑关系。
存储结点包含
数据域:所有存元素本身的信息;
指针域:元素之间逻辑关系的信息;包含有后继结点的地址信息。
循环队列:将存储队列的数组头尾相接。
如何解决假溢出?
0 1 2 3 4
入队
出队
a3
a4
front
a5
rear
rear
a6
队列的顺序存储结构及实现(顺序队列)
不存在物理的循环结构,但可用软件方法实现。
求模:(4+1)mod 5=0
如何实现循环队列?
0 1 2 3 4
入队
出队
a3
a4
front
rear
a6
队列的顺序存储结构及实现(顺序队列)
a5
【0】
【1】
【2】
【3】
【4】
【5】
rear
front
空队:front=rear
job1
1
rear
2
job2
3
job3
rear
4
5
job4
front
6
job5
rear
7
front
8
job6
9
job7
10
job8
rear
队满:
front=rear
队列的顺序存储结构及其实现--- 几个问题
1、当rear指向数组的最大下标的时候,如何向下标为0的位置改变?
2、队空和队满的条件都是 front=rear,如何区分?
3、如何表示出队和入队操作?
【0】
【1】
【2】
【3】
【4】
【5】
C
D
E
front
rear
B
MaxSize=6
char data[MaxSize];
rear=5
rear=?
data[rear]=‘F’;
rear=(rear+1)%MaxSize
队列的顺序存储结构及其实现--- 问题一
循环队列首尾相连, 这可以利用除法取余的运算(%)来实现:
队首指针进1:front=(front+1)%MaxSize
队尾指针进1:rear=(rear+1)%MaxSize
循环队列的队头指针和队尾指针初始化时都置0:front=rear=0。在入队元素和出队元素时,指针都按顺时针方向进1。
队空和队满的条件都是 front=rear,如何区分?
rear
0
1
2
3
4
front
(a)
空队
rear
0
1
2
3
4
front
(e)
出队
多
次
,
队空
front==rear
rear
0
1
2
3
4
front
(e)
,
队满
A
B
C
D
E
front==rear
队列的顺序存储结构及其实现--- 问题二