版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
队列的定义表示实现第一页,共三十页,编辑于2023年,星期五3.2队列只能在表的一端进行插入运算,在表的另一端进行删除运算的线性表。1.定义一、概念:例如:队列Q=(a1,a2,a3,…,an)在队尾插入元素称为入队;在队首删除元素称为出队。队头元素队尾元素允许插入的一端为队尾,允许删除的一端为队头。2第二页,共三十页,编辑于2023年,星期五与线性表相同,仍为一对一关系。顺序队或链队,以循环顺序队更常见。只能在队首和队尾运算,且访问结点时依照先进先出(FIFO)的原则。关键是掌握入队和出队操作,具体实现依顺序队或链队的不同而不同。3.存储结构:4.运算规则:5.实现方式:2.逻辑结构:3第三页,共三十页,编辑于2023年,星期五二、队列的抽象数据类型定义ADTQueue{
数据对象:
D={ai|ai∈ElemSet,i=1,2,...,n,n≥0}
数据关系:
R1={<ai-1,ai>|ai-1,ai∈D,i=2,...,n}
约定a1
端为队列头,an端为队列尾。基本操作:
}ADTStack4第四页,共三十页,编辑于2023年,星期五(1)初始化队列InitQueue(&Q)(2)入队EnQueue(&Q,e)(3)出队DeQueue(&Q,&e)(4)获取队头元素内容GetHead(Q,&e)(5)判断队列是否为空QueueEmpty(Q)基本操作:建队列、判断队列是否为空、入队、出队、读队头元素值,等等。5第五页,共三十页,编辑于2023年,星期五链队列类型定义:
typedefstruct{QueuePtrfront;//队头指针
QueuePtrrear;//队尾指针
}LinkQueue;结点类型定义:
typedefstructQNode
{QElemType
data;//元素
structQNode
*next;
//指向下一结点的指针}
Qnode,*QueuePtr;关于整个链队的总体描述链队中任一结点的结构三、队列的表示和实现1.单链队列//-----队列的链式存储结构-----6第六页,共三十页,编辑于2023年,星期五a1∧an…Q.frontQ.rearQ.frontQ.rear∧空队列为了操作方便,添加一个头结点,令头指针指向头结点。Q.front==Q.rear7第七页,共三十页,编辑于2023年,星期五
StatusInitQueue(LinkQueue&Q){//构造一个空队列
Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
if(!Q.front)exit(OVERFLOW);//存储分配失败
Q.front->next=NULL;
returnOK;}//-----基本操作的算法描述-----建队操作——构造空队列Q8第八页,共三十页,编辑于2023年,星期五Q(队尾)(队首)fronta1a2a3^rearp链队会满吗?一般不会,因为删除时有free动作。除非内存不足!入队(尾部插入):rear->next=S;rear=S;出队(头部删除):p=front->next;
front->next=p->next;free(p);Se^链队列的入队和出队操作9第九页,共三十页,编辑于2023年,星期五
StatusEnQueue(LinkQueue&Q,QElemTypee){
//插入元素e为Q的新的队尾元素
p=(QueuePtr)malloc(sizeof(QNode));if(!p)exit(OVERFLOW);//存储分配失败
p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;returnOK;}10第十页,共三十页,编辑于2023年,星期五
StatusDeQueue(LinkQueue&Q,QElemType&e){
//若队列不空,则删除Q的队头元素,
//用e返回其值,并返回OK;否则返回ERRORif(Q.front==Q.rear)returnERROR;
p=Q.front->next;e=p->data;Q.front->next=p->next;
if(Q.rear==p)Q.rear=Q.front;
//一定要考虑
free(p);returnOK;}11第十一页,共三十页,编辑于2023年,星期五队列的顺序存储结构如下图所示:附设两个指针front和rear分别指示队列头元素的位置和队列尾元素的下一个位置约定:初始化建空队列时,令front=rear=0;2.顺序队列12第十二页,共三十页,编辑于2023年,星期五(2)空队列的特征?约定:front=rear问题:(1)怎样实现入队和出队操作?核心语句如下:入队(尾部插入):Q[rear]=e;rear++;
出队(头部删除):e=Q[front];front++;
(3)队列会满吗?极易装满!因为数组通常有长度限制,而其前端空间无法释放。有假溢出现象。如图:13第十三页,共三十页,编辑于2023年,星期五解决假溢出的途径———采用循环队列在顺序队中,当尾指针已经到了数组的上界,不能再有入队操作,但实际上数组中还有空位置,这就叫“假溢出”。讨论:什么叫“假溢出”?如何解决?将存储队列元素的一维数组首尾相接,形成一个环状。14第十四页,共三十页,编辑于2023年,星期五a3a2a10123N-1rearfront循环队列(臆造)顺序队列a3a2a1frontrear
0123..N-115第十五页,共三十页,编辑于2023年,星期五新问题:在循环队列中,队空时front=rear;队满时也会有front=rear;判决条件将出现二义性!解决方案有二:①使用一个计数器记录队列中元素个数(即队列长度);②人为浪费一个单元,约定:队列头指针在队列尾指针的下一位置上作为队列呈“满”状态的标志。则队满特征可改为front=(rear+1)%N(N为最大队列长度);
实际中常选用方案2(人为浪费一个单元)16第十六页,共三十页,编辑于2023年,星期五建队核心语句:Q.base=(QElemType*)malloc(sizeof(QElemType)*MAXQSIZE);
//分配空间关于整个顺序队的总体描述#defineMAXQSIZE100//最大队列长度
typedefstruct{QElemType*base;//队列的基址
intfront;//队头指针
intrear;//队尾指针
}SqQueue//-----循环队列——队列的顺序存储结构-----17第十七页,共三十页,编辑于2023年,星期五队空条件:front=rear(初始化时:front=rear)队满条件:front=(rear+1)%N(N=MAXQSIZE)队列长度:L=(N+rear-front)%N
J2J3 J1J4
J5frontrear问3:在具有N个单元的循环队列中,队满时共有多少个元素?N-1个6问1:左图中队列MAXQSIZEN=?问2:左图中队列长度L=?518第十八页,共三十页,编辑于2023年,星期五例1.一循环队列如下图所示,若先删除4个元素,接着再插入4个元素,请问队头和队尾指针分别指向哪个位置?J2J3 J1J4
J5front=1rear=0解:由图可知,队头和队尾指针的初态分别为front=1和rear=0。删除4个元素后front=5;再插入4个元素后,rear=(0+4)%6=4
front=5J6J5J7J8J9rear=4rear=0front=519第十九页,共三十页,编辑于2023年,星期五例2.Q[0…10]是一个循环队列,初始状态为front=rear=0,画出做完下列操作后队列的头尾指针的状态变化情况,若不能入队,请指出其元素,并说明理由。d,e,b,g,h入队d,e出队i,j,k,l,m入队b出队n,o,p入队20第二十页,共三十页,编辑于2023年,星期五讨论:循环队列的基本操作如何实现?以建队、入队和出队三种基本操作为例1)初始化一个空队列算法要求:生成一空队列算法操作:为队列分配基本容量空间设置队列为空队列,其特征即:
front=rear=0(也可为任意单元,如1,2,…)21第二十一页,共三十页,编辑于2023年,星期五建队的完整算法:StatusInitQueue(SqQueue&Q){
//初始化空循环队列Q
Q.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType));//分配空间
if(!Q.base)
exit(OVERFLOW);
Q.front=Q.rear=0;
//置空队列
returnOK;}//InitQueue;22第二十二页,共三十页,编辑于2023年,星期五算法说明:向循环队列的队尾插入一个元素分析:(1)插入前应当先判断队列是否满?
if((Q.rear+1)%MAXQSIZE)==Q.front)returnERROR;(2)插入动作
Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXQSIZE;2)入队操作队列尺寸先存放元素,后移动队尾指针23第二十三页,共三十页,编辑于2023年,星期五StatusEnQueue(SqQueue&Q,QElemTypee){//向循环队列q的队尾加入一个元素e
if((Q.rear+1)%MAXQSIZE==Q.
front)returnERROR;
//队满则上溢
Q.
base[Q.
rear]=e;//新元素e入队
Q.rear=(Q.rear+1)%MAXQSIZE;//指针后移returnOK;}//EnQueue;入队操作完整算法24第二十四页,共三十页,编辑于2023年,星期五3)出队操作算法说明:删除队头元素,返回其值e分析:(1)在删除前应当判断队列是否空?
if(Q.front==Q.rear)returnERROR;
(2)删除动作分析:
前面约定指针front指向队首元素的位置,故:
e=Q.base[Q.front];Q.front=(Q.front+1)%MAXQSIZE;队列尺寸先取出元素,后移动队头指针25第二十五页,共三十页,编辑于2023年,星期五StatusDeQueue(SqQueue&Q,QElemType&e){//若队列不空,删除循环队列q的队头元素,//由e返回其值,并返回OKif(Q.
front==Q.
rear)returnERROR;//队列空e=Q.
base[Q.front];
Q.
front=(Q.front+1)%MAXQSIZE;returnOK;}//DeQueue出队操作完整算法26第二十六页,共三十页,编辑于2023年,星期五例3:编写一个算法,利用栈和队列的基本运算将指定队列中的内容进行逆转。分析:假设为循环队列。建立一个临时栈temps,将指定队列Q中的所有元素出队并入栈到tem
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 《红楼梦》菊花诗鉴赏-部编版2019下册语文课件
- 小学班主任资料-数学-教学总结4
- 《孙权劝学》课后习题参考答案
- 农产品追溯与物流智能化管理方案
- 四级筑路工(中级)职业技能鉴定考试题库(含答案)
- AbMole模块化刺激响应水凝胶:开启胃肠道渗漏防治新篇章
- 2024年中国打印机市场探析:数字化浪潮智能引领打印机市场-18正式版
- 七年级英语上册第01讲 be动词和行为动词的一般现在时(原卷版)
- 窗帘采购投标方案(技术方案)
- 2024年重庆市消防设施操作员《基础知识》科目真题冲刺卷下半年A卷
- 中国高血压防治指南(2024年修订版)核心要点解读
- Unit3Timeschange!Understandingideas教学设计2023-2024学年高二英语外研版(2019)选择性必修第二册
- 中国农业银行笔试题库(含答案)
- 5000m3立式拱顶油罐施工方案
- 毛衣织法及中英文名Word版
- 常用溶剂参数表(共11页)
- 访谈提纲与知情同意书
- 正丙硫醇、丁硫醇制法和安全性
- ZLP630型吊篮计算书
- 基金会财务报表审计指引
- 排水沟设计说明44702
评论
0/150
提交评论