数据结构第4章队列.ppt
《数据结构第4章队列.ppt》由会员分享,可在线阅读,更多相关《数据结构第4章队列.ppt(40页珍藏版)》请在三一文库上搜索。
1、第4章 队列, 本章要点 队列的定义及基本运算 队列的存储结构及运算实现 队列的应用举例 本章难点 循环队列、队列的链式存储结构及其运算的实现,4.1.1 队列的定义及运算,定义 相关概念 特征 常用基本运算,队列的定义,队列是允许在一端进行插入,而在另一端进行删除的线性表。,相关概念,队头:允许进行删除操作的一端。 队尾:允许进行插入操作的一端。 入队:队列的插入操作。 出队:队列的删除操作。,入队,出队,a,1,a,2,a,3,a,4,a,5,队尾,队头,队列示意图,队列的特征,在队列中,第一个入队的元素也是第一个出队的元素,因此队列也称为先进先出(First In First Out,F
2、IFO)的线性表。,构造空队列 入队列 出队列 取队头元素 队列空判断 队列满判断,队列的运算,队列的存储结构,队列的顺序存储 队列的链式存储,4.1.2 队列顺序存储结构,队列的顺序存储是指用一组连续的存储单元依次存放队列中的元素。,队列的顺序存储,队列顺序存储示意图,队列的队头和队尾的位置是变化的,所以需设两个指针: 头指针(front):指向队头元素的前一位置,存放该位置的下标。 尾指针(rear):指向队尾元素,存放其下标。,顺序队的类型定义 #define MAXSIZE 100 typedef struct Elemtype dataMAXSIZE; int rear, front
3、; SeqQueue; SeqQueue * Sq; /*定义一个指向队列的指针变量*/,Sq-front,Sq-front,front=rear= -1 空队,入队,队尾指针+1,front=4 rear=7,出队,队头指针+1,sq-data,sq-data,sq-data,sq-data,(-1),(5),(5),(2),此时,若有元素入队,发生假溢出。,假溢出:队列有空闲空间,但却不能插入新的元素。 解决办法:循环使用队列空间循环队列。,sq-data,(4),(7),MAXSIZE=8,练习,设有一空循环队列,占用了1000H1003H的空间,当前队头指针为1000H。现有输入序列1
4、、2、3、4、5、6,(每个数据占用一个存储单元)经过以下操作后: 进队、进队、出队、进队、进队、出队、进队 1出队的第一个数据元素是? 2第五次操作后队头指针为?队尾指针为?, 4.1. 3 循环队列,rear,0,1,2,3,4,5,6,7,front,a8,a7,a6,rear,0,1,2,3,4,5,6,7,front,a8,a7,a6,a9,a9入队,MAXSIZE=8,将队列的存储空间看成是一个首尾相连的环,即将队列的数组元素sq-data0与sq-dataMAXSIZE-1连接起来,形成的一个环。,循环队列,如何修改rear,在入队时,循环队列的尾指针 if(Sq-rear+1
5、=MAXSIZE) Sq-rear=0; else Sq-rear+; 或者,运用“模运算” Sq-rear=(Sq-rear+1)%MAXSIZE; 在出队时,循环队列的头指针 Sq-front=(Sq-front+1)%MAXSIZE;,取模运算的目的是为了将指针的取值从队尾下标MAXSIZE-1返到0。,B,C,D,Sq-rear,Sq-front,A,B,C,D,A,E,G,F,一般情况,队列满时,空队列,Sq-rear,Sq-front,Sq-rear,Sq-front,Sq-front=sq-rear,Sq-front=sq-rear,如何区分队列空和队列满?,区分循环队列是空还是
6、满的方法,方法一:设定一个标志变量flag。,当执行入队操作后,出现front=rear,则置flag=1,表明队列满。 当执行出队操作后,出现front=rear,则置flag=0,表明队列空。,区分循环队列是空还是满的方法,当队列头指针在队列尾指针的下一位置时,队列满。即: 循环队列满的条件:front=(rear+1)%MAXSIZE 循环队列空的条件:front=rear,方法二:在循环队列中少用一个元素的空间, 这样队列最多只能存放 MAXSIZE-1 个数据。,rear,0,1,2,3,4,5,6,7,B,A,C,D,E,X,Y,front,循环队列满的示意图,rear,0,1,2
7、,5,6,7,B,A,C,D,E,X,front,3,4,Y,练习,设有一空循环队列,占用了1000H1003H的空间,当前队头指针为1000H。现有输入序列1、2、3、4、5、6,(每个数据占用一个存储单元)经过以下操作后: 进队、进队、出队、进队、进队、出队、进队、进队 1执行最后一个进队操作时,会发生?,循环队列小结1,循环队列的数据结构定义 #define MAXSIZE 100 typedef struct Elemtype dataMAXSIZE; int fron t, rear; CirQueue ;,CirQueue * sq; /*定义一个指向该结构的指针sq*/,循环队列
8、小结2,定义: 将队列的存储空间看成是一个首尾相连的环,即将队列的数组元素sq-data0与sq-dataMAXSIZE-1连接起来,形成的一个环。,实现方法: 入队:Sq-rear = (Sq-rear+1) % MAXSIZE; 出队:Sq-front = (Sq- front +1) % MAXSIZE;,循环队列小结3,注意: 为了便于区分队满和队空,放弃一个存储单元。 即,队列最多只能存放 MAXSIZE-1 个数据。,判断方法: 队满: sq-front =(sq-rear+1)% MAXSIZE 队空: sq-front = sq-rear,循环队列小结4 图示1,rear,0,
9、1,2,3,4,5,6,7,front,MAXSIZE=8,初始队列 sq-front = 0 sq-rear = 0,rear,0,1,2,3,4,5,6,7,front,a8,a7,a6,某中间状态 队头元素:sq-data 队尾元素:sq-datasq-rear,rear,0,1,2,3,4,5,6,7,front,a9,a10,a11,(sq-front+1) % MAXSIZE,循环队列小结4 图示2,rear,0,1,2,3,4,5,6,7,front,MAXSIZE=8,rear,0,1,2,3,4,5,6,7,B,A,C,D,E,X,Y,front,循环队列满的示意图,循环队列
10、空的示意图, 初始化循环队列 为队列结构申请空间,建立一个空队列。 CirQueue * init_Cirqueue( ) Cirqueue * q; q=(Cirqueue *) malloc (sizeof(Cirqueue); q-front = q-rear = 0; return (q); , 4.1.4 循环队列的基本运算, 判断队空 判断队列是否为空,即判断头、尾指针是否相等。 int isEmpty_Cirqueue (Cirqueue * q) if (q-front = = q-rear) return(1); else return(0); , 判断队满 判断队列是否满,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 队列
链接地址:https://www.31doc.com/p-3406039.html