《第02章 线性数据结构2-栈和队列.ppt》由会员分享，可在线阅读，更多相关《第02章 线性数据结构2-栈和队列.ppt（25页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第第2 2章章线性数据结构及其运算线性数据结构及其运算2.1 2.1 线性表线性表2.2 2.2 栈和队列栈和队列2.3 2.3 数组数组2栈的定义栈的定义栈（栈（stackstack）是限定在一端进行是限定在一端进行插入与删除的线性表插入与删除的线性表栈顶（栈顶（toptop）是允许插入与删除是允许插入与删除的一端的一端栈底（栈底（bottombottom）是表中固定的是表中固定的一端，是栈顶的另一端一端，是栈顶的另一端FILOFILO（First In Last OutFirst In Last Out）进栈进栈出栈出栈3栈操作示例栈操作示例 有有三三个个元元素素的的进进栈栈序序列列是是1
2、 1，2 2，3 3，举举出出此此三三个个元元素素可可能能的的出出栈栈序序列列，并并写写出出相相应应的的进进栈栈和和出出栈栈操操作序列作序列 (假设以假设以I I和和O O表示进栈和出栈操作表示进栈和出栈操作)。4栈的栈的顺序存储顺序栈顺序存储顺序栈用用一维数组作为栈的存储空间一维数组作为栈的存储空间S S（1:m1:m）toptop指针始终指向栈顶元素的当前位置指针始终指向栈顶元素的当前位置 toptop-1-1表示栈空表示栈空toptopm m1 1表示栈满表示栈满(a)(a)空栈空栈 (b)(b)元素元素A A入栈入栈 (c)(c)栈满栈满 (d)(d)元素元素Y Y出栈出栈5建立顺序栈
3、的建立顺序栈的C C语言描述语言描述#define MAXSIZE m#define MAXSIZE m /*m /*m为栈中数据元素个数的最大可能值为栈中数据元素个数的最大可能值*/intint stackMAXSIZEstackMAXSIZE;intint top=-1;top=-1;6进栈运算算法进栈运算算法#define MAXSIZE m#define MAXSIZE m intint stackMAXSIZEstackMAXSIZE;intint top=-1;top=-1;void void push(intpush(int x)x)if(topif(top=MAXSIZE-1)
4、=MAXSIZE-1)printfprintf(栈满溢出栈满溢出 n);n);exit(1);exit(1);else else top+;top+;stacktopstacktop=x;=x;判断栈是否已满，若判断栈是否已满，若满则输出栈溢出信息，满则输出栈溢出信息，并停止执行；否则，继并停止执行；否则，继续执行；续执行；栈顶指针栈顶指针toptop后移；后移；在栈顶指针所指当前在栈顶指针所指当前位置插入元素位置插入元素x x。7退栈运算算法退栈运算算法#define MAXSIZE m#define MAXSIZE m intint stackMAXSIZEstackMAXSIZE;int
5、int top;top;intint pop()pop()intint x;x;if(topif(top=-1)=-1)printfprintf(栈空溢出栈空溢出 n);n);exit(1);exit(1);else else x=x=stacktopstacktop;top-;top-;return x;return x;判断栈是否为空栈，若判断栈是否为空栈，若为空则输出栈下溢信息，为空则输出栈下溢信息，并停止执行；否则，继续并停止执行；否则，继续执行；执行；弹出弹出(删除删除)栈顶元素；栈顶元素；栈顶指针栈顶指针toptop下移。下移。8读栈顶元素算法读栈顶元素算法#define MAXS
6、IZE m#define MAXSIZE m intint stackMAXSIZEstackMAXSIZE;intint top;top;intint pop()pop()intint x;x;if(topif(top=-1)=-1)printfprintf(栈空溢出栈空溢出 n);n);exit(1);exit(1);else else x=x=stacktopstacktop;return x;return x;判断栈是否为空栈，判断栈是否为空栈，若为空则输出栈下溢信若为空则输出栈下溢信息，并停止执行；否则，息，并停止执行；否则，继续执行；继续执行；读出栈顶元素。读出栈顶元素。9栈的链式
7、存储链栈栈的链式存储链栈链栈的链栈的C C语言描述如下：语言描述如下：structstruct snodesnode intint data;data;structstruct snodesnode*link;*link;typedeftypedef structstruct snodesnode SNODESNODE;栈顶指针仍是栈顶指针仍是toptop，其类型为，其类型为SNODE*SNODE*，相当于单链，相当于单链表的头指针，可惟一确定一个链栈；表的头指针，可惟一确定一个链栈；当当top=NULLtop=NULL，表示一个空链栈。，表示一个空链栈。10链栈的插入运算（入栈）链栈的插入运
8、算（入栈）申请一链栈结点，若无申请一链栈结点，若无可用内存空间，则表示可用内存空间，则表示栈满，否则继续执行；栈满，否则继续执行；在在toptop所指结点之前插入所指结点之前插入新结点，并将新结点，并将toptop指向新指向新申请的结点。申请的结点。#include#include“stdlibstdlib.h.h”void void push(SNODEpush(SNODE*top,*top,intint x)x)SNODE*p;SNODE*p;p=(SNODE*)p=(SNODE*)malloc(sizeof(SNODEmalloc(sizeof(SNODE););if(pif(p=NUL
9、L)=NULL)printfprintf(内存中无可用空间，栈溢内存中无可用空间，栈溢出出!n);!n);exit(1);exit(1);else else p-data=x;p-data=x;p-link=top;p-link=top;top=p;top=p;11链栈的删除运算（退栈）链栈的删除运算（退栈）若若链链栈栈为为空空，则则输输出出栈栈溢溢出出信信息息；否否则继续执行；则继续执行；删删除除toptop所所指指结结点点，并并使使toptop指指向向被被删删结结点的后继结点。点的后继结点。#include#include“stdlibstdlib.h.h”void void pop(SN
10、ODEpop(SNODE*top)*top)intint x;x;SNODE*p;SNODE*p;if(topif(top=NULL)=NULL)printfprintf(栈空溢出栈空溢出(下溢下溢)n);)n);exit(1);exit(1);else else p=top;p=top;top=top=toptop-link;-link;x=p-data;x=p-data;free(pfree(p););12队列的定义队列的定义队列队列（QueueQueue）是指允许在一端进行插入，而在另一是指允许在一端进行插入，而在另一端进行删除的线性表端进行删除的线性表队尾队尾：允许插入的一端；用尾指针
11、：允许插入的一端；用尾指针rearrear指向队尾元素，指向队尾元素，即最后被插入的元素即最后被插入的元素队头队头：允许删除的一端；用头指针：允许删除的一端；用头指针frontfront指向队头元指向队头元素的位置素的位置FIFOFIFO结构的线性表结构的线性表具有具有n n个元素的队列示意图个元素的队列示意图13队列的顺序存储结构队列的顺序存储结构用用一维数组作为队列的存储空间一维数组作为队列的存储空间Q Q（1:m1:m）队头指针队头指针frontfront指向队列中队头元素的指向队列中队头元素的前前一个位置一个位置队尾指针队尾指针rearrear指向队尾元素在队列中的当前位置指向队尾元素
12、在队列中的当前位置(a)(a)空队列空队列 (b)A,B,C,Db)A,B,C,D相继入队相继入队 (c)A,B,C,Dc)A,B,C,D相继出队相继出队 (d)E,Fd)E,F入队入队14入队和出队运算入队和出队运算入队时的相关操作：入队时的相关操作：rear+rear+；/*/*修改尾指针修改尾指针*/queuerearqueuerear=x=x；/*x/*x入队列入队列*/出队时需修改头指针：出队时需修改头指针：front+front+；15循环队列循环队列 循环队列循环队列，就是将队列存储空间的最后一，就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空个位置绕到第一个位
13、置，形成逻辑上的环状空间，供队列循环使用。间，供队列循环使用。16循环队列运算循环队列运算队列为空队列为空：rear=frontrear=front入队入队：rear+1rear+1，如果如果rear=mrear=m，则，则rear=0rear=0或或rear=(rear+1)%mrear=(rear+1)%m出队出队：front+1front+1，如果如果front=mfront=m，则，则front=0front=0或或front=(front+1)%mfront=(front+1)%m队满判定队满判定1 1：front=(rear+1)%mfront=(rear+1)%m队满判定队满判定
14、2 2：front=rearfront=rear？不能确定不能确定 单独设立一个单独设立一个标志标志：tag=tag=0 0 队空队空1 1 队非空队非空17循环队列运算循环队列运算例例1 设循环队列容量为设循环队列容量为70（序号为（序号为170），经过），经过若干入队和出队后有：若干入队和出队后有：front=14,rear=21。front=23,rear=12。求这两种情况下，循环队列中各有多少个元素？求这两种情况下，循环队列中各有多少个元素？759例例2 设栈设栈S和队列和队列Q的初始状态为空，元素的初始状态为空，元素e1,e2,e3,e4,e5,e6依次通过栈依次通过栈S，一个元素
15、出栈后即进入队列，一个元素出栈后即进入队列Q，若出队的顺序为，若出队的顺序为e2,e4,e3,e6,e5,e1，则栈，则栈S的容的容量至少应为多少？量至少应为多少？318循环队列入队算法循环队列入队算法判判定定循循环环队队列列是是否否已已满满，若若满满，则则给给出出队队列溢出出错信息列溢出出错信息；队队尾尾指指针针后后移移，将将入入队队元元素素放放入入队队尾尾指指针针所指的存储位置。所指的存储位置。算法的算法的C C语言描述语言描述:#define MAXSIZE m#define MAXSIZE mintint queueMAXSIZEqueueMAXSIZE；intint front=-1
16、,rear=-1 front=-1,rear=-1；void void addqueue(intaddqueue(int x)x)if(frontif(front=(rear+1)%MAXSIZE)=(rear+1)%MAXSIZE)printfprintf(循环队列已满，上溢循环队列已满，上溢!n);!n);exit(1);exit(1);else else rear=(rear+1)%MAXSIZE;rear=(rear+1)%MAXSIZE;queuerearqueuerear=x;=x;19循环队列出队算法循环队列出队算法判判定定循循环环队队列列是是否否为为空空，若若空空，则则给给出出
17、队队列列溢溢出出（下下溢溢）信息；信息；队队头头指指针针后后移移一一个个位置。位置。算法的算法的C C语言描述语言描述:#define MAXSIZE m#define MAXSIZE mintint queueMAXSIZEqueueMAXSIZE；intint front=-1,rear=-1 front=-1,rear=-1intint delqueuedelqueue()()intint x;x;if(frontif(front=rear)=rear)printfprintf(循环队列已空，下溢！循环队列已空，下溢！n);n);x=-1;x=-1;else else front=(fr
18、ont+1)%MAXSIZE;front=(front+1)%MAXSIZE;x=x=queuefrontqueuefront;return x;return x;20队列的链式存储结构队列的链式存储结构链队列满的条件是仅当内存中无可利用内存；链队列满的条件是仅当内存中无可利用内存；链队列空的条件是：链队列空的条件是：front=rearfront=rear(a)(a)空链队列空链队列(b)(b)非空链队列非空链队列21链队列的运算链队列的运算(a)(a)空链队列空链队列 (b)(b)元素元素x x入队列入队列 (c)(c)元素元素y y入列入列 (d)(d)元素元素x x出列出列22链队列的
19、入队算法链队列的入队算法#include#include“stdlibstdlib.h.h”structstruct qnodeqnode intint data;data;structstruct qnodeqnode*next;*next;typedeftypedef structstruct qnodeqnode QNODEQNODE;QNODE*front,*rear;QNODE*front,*rear;void void addqueue(intaddqueue(int x)x)QNODE*p;QNODE*p;p=(QNODE*)p=(QNODE*)malloc(sizeof(QNO
20、DEmalloc(sizeof(QNODE););if(pif(p=NULL)=NULL)printfprintf(内存中无可用空间。内存中无可用空间。链队列已满，即上溢。链队列已满，即上溢。n);n);exit(1);exit(1);else else p-data=x;p-data=x;p-next=NULL;p-next=NULL;rear-next=p;rear-next=p;rear=p;rear=p;23链队列的出队算法链队列的出队算法 if(frontif(front=rear)=rear)printfprintf(链队列已空，即下链队列已空，即下溢。溢。n);n);exit(1
21、);exit(1);else else p=front-next;p=front-next;front-next=p-next;front-next=p-next;x=p-data;x=p-data;if(pif(p-next=NULL)-next=NULL)rear=front;rear=front;free(pfree(p););#include#include“stdlibstdlib.h.h”structstruct qnodeqnode intint data;data;structstruct qnodeqnode*next;*next;typedeftypedef structstruct qnodeqnode QNODEQNODE;QNODE*front,*rear;QNODE*front,*rear;void void delqueuedelqueue()()intint x;x;QNODE*p;QNODE*p;24第四次作业第四次作业P44P44：4 4，5 5，6 6P44P44：1010，111125