一教学内容栈和队列的定义及特点栈的顺序存储.ppt

《一教学内容栈和队列的定义及特点栈的顺序存储.ppt》由会员分享，可在线阅读，更多相关《一教学内容栈和队列的定义及特点栈的顺序存储.ppt（59页珍藏版）》请在三一办公上搜索。

1、一、教学内容：1、栈和队列的定义及特点；2、栈的顺序存储表示和链接存储表示；3、队列的顺序存储表示；队列的链接存储表示；4、栈和队列的应用举例。,第3章 栈和队列,二、教学要求：了解递归的概念和递归过程的实现；掌握栈和队列的定义、表示、实现和应用；掌握栈的顺序存储结构和链式存储结构以及相应操作的实现；掌握队列的顺序存储结构（循环队列）和链式存储结构的实现；熟练掌握链式栈和顺序队列的操作算法。,目录,3.1 栈 3.1.1 栈的定义 3.1.2 顺序栈的表示与实现 3.1.3 链式栈的表示与实现 3.2 栈的应用举例 3.2.1 数制转换 3.2.4 迷宫求解 3.2.5 表达式求值*3.3 栈

2、和递归的实现 3.4 队列 3.4.1抽象数据类型队列的定义 3.4.2 链队列-队列的链式表示与实现 3.4.3 循环队列-队列的顺序表示与实现本章小结,3.1 栈（stack）3.1.1 栈的定义：限定仅在表尾进行插入或删除操作的线性表.栈顶（top）:线性表的表尾端，即可操作端。栈底（base）:线性表的表头。特点：先进后出（FILO）或后进先出（LIFO）,3.1.2 栈的顺序存储结构顺序栈实现：一维数组sM,base=0,栈空,栈顶指针top,指向实际栈顶后的空位置，初值为0,进栈,A,出栈,栈满,B,C,D,E,F,设数组维数为Mtop=0,栈空，此时出栈，则下溢（underflo

3、w)top=M,栈满，此时入栈，则上溢（overflow),栈空,top=0,base=0,base=0,栈的抽象数据类型定义,ADT Stack 数据对象：D=ai|ai属于ElemSet,(i=1,2,n,n0)数据关系：R1=ai-1,ai|ai-1,ai属于D,(i=2,3,n)约定an为栈顶,a1为栈底。基本操作：InitStack(/出栈 StackTraverse(S,visit()ADT Stack,栈的顺序存储结构(顺序栈)表示:,#define STACK_INIT_SIZE 100；#define STACKINCREMENT 10；typedef char SElemT

4、ype;typedef struct/顺序栈定义 SElemType*base;/栈底指针 SElemType*top;/栈顶指针int stacksize；/当前已分配的全部存储空间 SqStack；,顺序栈的基本运算:,顺序栈的基本操作,初始化压栈出栈清空栈判栈是否为空判栈是否为满取栈顶元素多个栈的共享空间,分析：初始化就是建立一个空栈，栈中不含任何元素，此时栈顶指针top为0，表示栈空。,示意图,void InitStack(SqStack,实现算法,算法：InitStack（S）初始化：,分析：进栈需要判断是否会出现“溢出”，若栈不满，则元素进栈时，栈顶指针做加一操作，元素进栈。实现算

5、法：void Push(SqStack,算法：Push(&S，e）压栈,元素入栈示意图,分析：如果顺序栈不为空，此时执行出栈操作，栈顶指针做减一操作，指向原栈顶的后继元素。如果对空栈执行出栈操作，应提示错误信息并终止程序运行。实现算法：Status Pop(SqStack,算法：Pop（&S，&e）出栈,栈空,下溢,分析：清空栈，就是把一个栈置成空栈。即不论数组中是否存有数据，只要将栈顶指针top指向栈底处，就表示栈空。实现算法：void ClearStack(SqStack,算法：ClearStack(&S)清空栈,分析：通过判断栈顶指针来判断栈是否为空。栈顶指针top与栈底指针base指向

6、相同，表示栈为空，返回TRUE；否则返回FALSE。实现算法：Status StackEmpty(SqStack S)/若栈S为空栈，则返回TRUE，否则返回FALSE if(S.top=S.base)return TRUE;else return FALSE;,算法：StackEmpty（&s)判栈是否为空,分析：通过判断栈顶指针与栈底指针之间的元素个数是否达到了最大容量判断栈是否为满。栈为满，返回TRUE；否则返回FALSE。实现算法：Status StackFull(SqStack S)if(S.top-S.base=S.StackSize)return TRUE;/判栈满else re

7、turn FALSE;,算法：StackFull（s)判栈是否为满,分析：栈顶指针直接指向栈顶元素。需要注意空栈的情况。实现算法：Status GetTop(SqStack S,SElemType,算法：GetTop（s,&e)取栈顶元素,结论：顺序栈的入栈和出栈操作，实际上对应的是顺序表的表尾插入和表尾删除操作。所以入栈和出栈操作的时间复杂度都为O（1）。,顺序栈的操作演示,实例：栈使用的完整C程序实例,Q1:对于一个栈，给出输入项A、B、C，如果输入项序列由ABC组成，试给出所有可能的输出序列,能否产生CAB输出序列。,Q2:如果一个栈的输入序列为123456，能否得到435612和135

8、426的出栈序列？,栈的共享存储单元(可选)问题:有时，在一个程序设计中，需要使用多个同一类型的栈,这时候，可能会产生一个栈空间过小，容量发生溢出，而另一个栈空间过大，造成大量存储单元浪费的现象。解决方法:为了充分利用各个栈的存储空间，这时可以采用多个栈共享存储单元，即给多个栈分配一个足够大的存储空间，让多个栈实现存储空间优势互补。,两个共享存储单元顺序栈的操作演示,实例:在程序中定义两个栈,（1）定义共享栈数据结构#define MAX 100int stackMAX;int top1=base1=0,top2=base2=MAX-1;,栈1的操作:入栈top1执行加1的操作;出栈top1执

9、行减1的操作;栈2的操作:入栈top2执行减1的操作;出栈top2执行加1的操作;栈满条件:top1top2,(2)共享进栈算法 void push1(int x)if(top1top2)printf(“overflow”);else stacktop1=x;top1+;void push2(int x)if(top1top2)printf(“overflow”);else stacktop2=x;top2-;,(3)共享出栈算法 int pop1()if top1=0)printf(“underflow”);return(NULL);top1-;return(stacktop1);int p

10、op2()if(top2=MAX-1)printf(“underflow”);return(NULL):top2+;return(stacktop2);,3.1.3 链栈(可选）,定义：栈的链式存储通常用单链表实现，此时链表的头指针为栈顶指针，定义为top，链表第一个结点为栈顶结点。当头指针为NULL时，表示当前栈为空栈。,链栈示意图：,特点：链式栈无栈满问题，空间可扩充 插入与删除仅在栈顶处执行 链式栈的栈顶在链头 适合于多栈操作,栈的链接存储结构定义：,typedef struct node ElemType data;struct node*next;LNode,*LinkStack;,

11、分析：链式存储时，空栈即为空单链表，其栈顶指针值为NULL。实现算法：void InitStack(LinkStack 注意：空单链表是带表头结点的空单链表。,算法：InitStack(S)初始化,分析：链栈的入栈操作就是单链表的表头插入。实现算法：LinkStack*PushLStack(LinkStack*top,ElemType x)LinkStack*p;p(LinkStack*)malloc(sizeof(LinkStack);p-datax;p-nexttop;return p;,算法：PushLStack(S)链栈的进栈算法,分析：如果是空栈，提示出错信息并退出；否则，栈顶元素出

12、栈，即删除单链表的第一个结点。实现算法：linkstack*PopLStack(LinkStack*top,ElemType*datap)LinkStack*p;if(top=NULL)printf(“under flown”);return NULL;else*dataptop-data;ptop;toptop-next;free(p);return top;,算法：PopLStack（S）链栈的出栈算法,分析：如果是空栈，提示出错信息并退出；否则，返回单链表的第一个结点的值。实现算法：（略）,算法：GetTop(S)取栈顶的元素,算法：StackEmpty(S)判栈是否为空,分析：通过判断

13、top的值来判断链栈的状态实现算法：（略）,分析：清空链栈，要释放链表中的所有结点。实现算法：（略）,算法：ClearStack(S)清空栈,3.2 栈的应用举例 由于栈结构具有的后进先出的固有特性，致使栈成为程序设计中常用的工具。以下是几个栈应用的例子。,数制转换(*)行编辑程序迷宫求解表达式求值 Hanoi塔问题,例1：栈的应用举例-数制转换(讲述)十进制N和其它进制数的转换是计算机实现计算的基本问题,其解决方法很多,其中一个简单算法基于下列原理:N=(n div d)*d+n mod d(其中:div为整除运算,mod为求余运算)例如(1348)10=(2504)8，其运算过程如下：n

14、n div 8 n mod 8 1348 168 4 168 21 0 21 2 5 2 0 2,void conversion()/算法3.1/对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数 ElemType e;SqStack s;int n;InitStack(s);scanf(“%d”,算法：10进制-8进制转换,.while(n)Push(s,n%16);n=n/16;,算法：10进制-16进制转换,十进制转化为任意进制的实例,例2：行编辑程序在用户输入一行的过程中，允许 用户输入出差错，并在发现有误时可以及时更正。设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐

15、行存入用户数据区;并假设“#”为退格符，“”为退行符。假设从终端接受两行字符：whli#ilr#e（s#*s)outchaputchar(*s=#+);实际有效行为：while(*s)putchar(*s+);,void LineEdit()InitStack(s);ch=getchar();while(ch!=EOF)/EOF为全文结束符while(ch!=EOF,算法：,例3：迷宫求解,例4：表达式求值,例5：hanoi塔问题(讲述),问题描述：传说在创世纪时，在一个叫Brahma的寺庙里，有三个柱子，其中一柱上有64个盘子从小到大依次叠放，僧侣的工作是将这64个盘子从一根柱子移到另一个柱

16、子上。移动时的规则：每次只能移动一个盘子；只能小盘子在大盘子上面；可以使用任一柱子。当工作做完之后，就标志着世界末日到来。,解决方法：n=1时，直接把圆盘从A移到Cn1时，先把上面n-1个圆盘从A移到B,然后将n号盘从A移到C,再将n-1个盘从B移到C。即把求解n个圆盘的Hanoi问题转化为求解n-1个圆盘的Hanoi问题，依次类推，直至转化成只有一个圆盘的Hanoi问题 hanoi塔的递归算法,void hanoi(int n,char a,char b,char c)/将 n 个 编号从上到下为 1n 的盘子从 a 柱，借助 b 柱移到 c 柱 if(n=1)move(a,1,c);/将编

17、号为 1 的盘子从 a 柱移到 c 柱 else/将 n-1个 编号从上到下为1n-1的盘子从 a 柱，借助 b 柱移到 c 柱 hanoi(n-1,a,c,b);move(a,n,c);/将编号为 n 的盘子从 a 柱移到 c 柱/将 n-1个 编号从上到下为 1n-1的盘子从 b 柱，借助 a 柱移到 c 柱 hanoi(n-1,b,a,c);/hanoi,算法：hanoi塔,3.4 队列,队列定义队列的特点队列的ADT表示链式队列链式队列的基本操作循环队列（顺序队列）,队列的定义：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表队尾(rear)允许插入的一端队头(front

18、)允许删除的一端队列的特点：先进先出(FIFO),双端队列,队列的抽象数据类型定义：,ADT Queue 数据对象：D=ai|ai属于Elemset,(i=1,2,n,n0)数据关系：R1=ai-1,ai|ai-1,ai属于D,(i=2,3,n)约定an为队尾,a1为队头。基本操作：InitQueue(QueueTraverse(Q,visit()ADT Queue,链队列 队列的链式存储结构简称为链队列，它是限制仅在表头删除和表尾插入的单链表。显然仅有单链表的头指针不便于在表尾做插入操作，为此再增加一个尾指针，指向链表的最后一个结点。于是，一个链队列由头指针和尾指针唯一确定。,typedef

19、 struct QueuePtr front;QueuePtr rear;LinkQueue;,链队列的存储结构定义：,typedef struct QNode ElemType data;struct QNode*next;QNode,*QueuePtr;,非空队列,空队列,链队列示意图：,链队列中，有两个分别指示队头和队尾的指针。链式队列在进队时无队满问题，但有队空问题。,链式队列的基本操作,构造一个空队列判队列是否为空取队头元素入队出队,算法实现：Status InitQueue(LinkQueue,算法：构造一个空队列,置队空示意图,算法实现：Status QueueEmpty(Lin

20、kQueue Q)/若Q为空队列，则返回TRUE，否则返回FALSE if(Q.front-next=NULL)return TRUE;else return FALSE;,算法：判队列是否为空,算法实现：Status GetHead(LinkQueue Q,QElemType,算法：取队头元素,算法实现：void EnQueue(LinkQueue,算法：入队,算法实现：Status DeQueue(LinkQueue,算法：出队,非循环队列和循环队列,顺序队列队列的顺序存储表示。用一组地址连续的存储单元依次存放从队列头到队列尾的元素，指针front和rear分别指示队头元素和队尾元素的位置

21、。插入新的队尾元素，尾指针增1，rear=rear+1，删除队头元素，头指针增1，front=front+1，因此，在非空队列中，头指针始终指向队列头元素，而尾指针始终指向队列尾元素的下一个位置。队满时再进队将溢出 解决办法：将顺序队列臆造为一个环状的空间，形成循环(环形)队列,队列的顺序存储结构定义：,#define MAXQSIZE 100typedef struct/ElemType dataMAXQSIZE;/静态分配 ElemType*base;/动态分配 int front;int rear;SqQueue;,顺序队列的操作演示,队列的进队和出队示例：,front,rear,空队列

22、,front,rear,A,B,C,D进队,A B C D,front,rear,E,F,G进队,C D E F G,C D E F G,front,rear,H进队,溢出,队空：Q.front=Q.rear队满：Q.rear=maxsize（假溢出）求队的长度：Q.rear-Q.front 入队：新元素按 rear 指示位置加入，再将队尾指针加一，即 rear=rear+1 出队：将front指示的元素取出，再将队头指针加一，即front=front+1,非循环队列,设数组维数为M，则：当front=0,rear=M时，再有元素入队发生溢出真溢出当front0,rear=M时，再有元素入队发

23、生溢出假溢出,存在问题:,解决方法:循环队列(Circular Queue),基本思想：把队列设想成环形队头、队尾指针加1，可用取模(余数)运算实现。队头指针进1:front=(front+1)%maxsize;队尾指针进1:rear=(rear+1)%maxsize;队列初始化：front=rear=0;队空条件：front=rear;队满条件：(rear+1)%maxsize=front;,#define MAXSIZE 100Typedef structQElemType*base;int front;int rear;SqQueue;,循环队列的类型定义,算法实现：Status EnQ

24、ueue(SqQueue,算法：入队,分析:（1）检查队列是否已满，若队满，则进行溢出错误处理；（2）将新元素赋给队尾指针所指单元；（3）将队尾指针后移一个位置（即加1），指向下一单元。,算法实现：Status DeQueue(SqQueue,算法：出队,分析:（1）检查队列是否为空，若队空，则进行下溢错误处理；（2）取队首元素的值。（3）将队首指针后移一个位置（即加1）；,本章小结,线性表、栈与队的异同点相同点：逻辑结构相同，都是线性的；都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表（只是对插入、删除运算加以限制）。不同点：运算规则不同，线性表为随机存取，而栈是只允许在一端进行插入和删除运算，因而是后进先出表LIFO；队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。用途不同，线性表比较通用；堆栈用于函数调用、递归和简化设计等；队列用于离散事件模拟、多道作业处理和简化设计等。,实验3：栈和队列的定义及基本操作(必做2学时）,实验4：栈和队列的综合应用(选做2学时）,