第3章栈和队列链队列.ppt
《第3章栈和队列链队列.ppt》由会员分享,可在线阅读,更多相关《第3章栈和队列链队列.ppt(34页珍藏版)》请在三一文库上搜索。
1、第3章 栈和队列,教学目标 3.1 栈 3.1.1 栈的定义 3.1.2 栈的顺序存储结构及其基本实现 3.1.3 栈的链式存储结构及其基本实现 3.2 队列 3.2.1 队列的定义 3.2.2 队列的顺序存储结构及其基本实现 3.2.3 队列的链式存储结构及其基本实现 本章小结,3.2 队列 3.2.1 队列的定义 3.2.2 队列的顺序存储结构及其基本实现,温故知新环节,特殊线性表队列,队列的逻辑结构 队列:只允许在一端进行插入操作,而另一端进行删除操作的线性表。,a1,a2,a3,入队,出队,队列的操作特性:,先进先出,循环队列:将存储队列的数组头尾相接。,如何解决假溢出?,0 1 2
2、3 4,入队,出队,a3,a4,a5,a6,队列的顺序存储结构及实现(顺序队列),不存在物理的循环结构,但可用软件方法实现。 求模:(41)mod 50,MaxSize=6 char dataMaxSize; rear=5 rear=? datarear=F;,rear=(rear+1)%MaxSize,3.2.2 队列的顺序存储结构及其实现- 问题一,循环队列首尾相连, 这可以利用除法取余的运算()来实现: 队首指针进1:front=(front+1)MaxSize 队尾指针进1:rear=(rear+1)MaxSize,队空和队满的条件都是 front=rear,如何区分?,front=r
3、ear,front=rear,3.2.2 队列的顺序存储结构及其实现- 问题二,怎样区分队空与队满之间的差别呢?在入队时少用一个数据元素空间,以队尾指针加1等于队首指针判断队满,即队满条件为: (q-rear+1) % MaxSize=q-front 队空条件仍为: q-rear=q-front,温故知新环节,栈和队列都是()(南京理工) 顺序存取的线性结构 链式存储的非线性结构 限制存取点的线性结构 限制存取点的非线性结构,温故知新环节,若用一个大小为6的数组来实现循环队列,且当前rear和front的值分别为0和3,当从队列中删除一个元素,再加入2个元素后,rear和front的值分别为多
4、少? (浙大) a)1和5 b)2和4 c)4和2 d)5和1,温故知新环节,设栈S和队列Q的初始状态为空, 元素e1,e2,e3,e4,e5,e6依次通过栈S, 一个元素出栈后即进入队列Q, 若6个元素出队的序列是 e2,e4,e3,e6,e5,e1,则栈的 容量至少应该是() (南京理工) 6 b)4 c)3 d)2,温故知新环节,循环队列存储在数组A0m中,则入队时的操作为() A.rear=rear+1 B.rear=(rear+1)mod(m-1) C.rear=(rear+1)mod m D.rear=(rear+1)mod(m+1),温故知新环节,3.2 队列 3.2.3 队列的
5、链式存储结构及其基本实现 循环队列:必须预先确定一个固定的长 度,所以有存储元素个数的限制和空间 浪费的问题。还有队满的情况发生。,新语新知环节,链队列:队列的链接存储结构,队头指针即为链表的头指针,如何改造单链表实现队列的链接存储?,队列的链式存储结构及实现(链队列),非空链队列,q,rear,空链队列,front,rear,队列的链式存储结构及实现(链队列),q,链列的入队和出队操作示意图,front,rear,q,(a),链队初态,front,rear,(c),出队,1,个元素,b,c,3.2.3 队列的链式存储结构及其基本运算的实现,q,(1) 存储队列元素的结点数据类型,单链表中数据
6、结点类型QNode定义如下: typedef struct qnode ElemType data; /*数据元素*/ struct qnode *next; QNode;,3.2.3 队列的链式存储结构及其基本运算的实现,(2) 指向队头和队尾指针的链队头结点,链队中头结点类型LiQueue定义如下: typedef struct QNode *front; /*指向单链表队头结点*/ QNode *rear; /*指向单链表队尾结点*/ LiQueue;,3.2.3 队列的链式存储结构及其基本运算的实现,(1) 存储队列元素的单链表,(2) 指向队头和队尾指针的链队头结点,单链表中数据结点
7、类型QNode定义如下: typedef struct qnode ElemType data; /*数据元素*/ struct qnode *next; QNode;,链队中头结点类型LiQueue定义如下: typedef struct QNode *front; /*指向单链表队头结点*/ QNode *rear; /*指向单链表队尾结点*/ LiQueue;,front,rear,q,(b),入队,3,个元素,a,b,c,front,rear,q-front=s,q- rear=s,S-next=NULL,S-next=NULL,q-rear-next=s,q-rear=s,q,3.2
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 队列
链接地址:https://www.31doc.com/p-2549615.html