第三章栈和队列(无答案).ppt

1、第三章 栈和队列,3.1 栈的抽象数据类型定义与实现 3.2 栈的应用举例 3.3 栈的应用-栈与递归 3.4 队列的抽象数据类型定义和实现 3.5 队列应用-离散事件模拟,1、 栈的相关概念 概念: 栈(Stack)是定义在线性结构上的抽象数据类型，其操作类似线性表操作，但元素的插入、删除和访问都必须在表的一端进行,为形象起见,称允许操作端为栈顶(Top),另一端为栈底(base),注意Top指向待插入位置 特性:Last In First Out后进先出/总是访问最近插入的一个/按插入顺序倒着访问,3.1 栈(Stack),栈顶 元素,2、栈的ADT定义,ADT Stack 数据对象：D=

2、ai|aiElemSet,i=1,2,n,n=0 数据关系：R=|ai-1,aiD，约定an为栈顶元素 基本操作： InitStack (/栈元素类型 typedef struct SElemType *base; /栈底指针 SElemType *top; /栈顶指针 int stacksize; /栈容量 SqStack /如何判栈空、求栈长、判栈满？,顺序栈基本操作的实现初始化/销毁/置空,Status InitStack(SqStack /InitStack 复杂度”O(1)”,Status DestroyStack(SqStack /复杂度O(1),Status ClearStack

3、(SqStack /复杂度O(1),Status Push(SqStack /Push ,复杂度O(1),Status Pop(SqStack /复杂度O(1),入栈与出栈,Status StackEmpty(SqStack S) if(S.top=S.base)return TRUE;else return FALSE; int StackLength (SqStack S) return (S.top-S.base); Status GetTop(SqStack S, SElemType /除遍历操作外时间复杂度均O(1),引用型操作,/可据需要适当增加新操作 Status SetTopE

4、lem(SqStack S,ElemType e) /将栈顶元素的值修改为e if(S.top=S.base)return ERROR; *(S.top-1)=e; return OK; /可用pop和push合作实现,4、链栈的定义与实现【补充】,若栈中元素的数目变化范围较大或不清楚栈元素的数目，可考虑使用链式存储结构。用链式存储结构表示的栈称作“链栈”。 链栈常用一个无头结点的单链表表示，栈名指针指向栈顶元素，相当于顺序栈栈顶指针，但有不同,顺序栈栈顶指针指向第一个空位置 栈的链式存储结构定义:,typedef struct SNode SElemType data; struct SNo

5、de *next; SNode, *LinkStack; LinkStack S; /链栈栈名S指向栈顶元素，顺序栈top指向首个空位置,注意最先插入在最底端 链栈链指针向下,基本操作实现,Status InitStack(LinkStack /其余操作自行实现, 遍历/销毁/清空/求表长均O(n)，其余O(1),3.2 栈的应用,1、十进制整数转换为八进制,0,5,2,4,void conversion( ) scanf (“%d”, ,充分利用栈后进先出的特性,比用数组更易读易写抽象层次更高,回顾:,栈的概念:栈 栈底指针 栈顶指针 栈顶元素 栈的两种存储结构定义及各自适用场合，及栈的操作

6、在两种结构下的实现 栈的应用- Last In First Out后进先出/总是访问最近插入的一个/按插入顺序倒着访问,#define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef ? SElemType; typedef struct SElemType *base; /栈底指针 SElemType *top; /栈顶指针 int stacksize; /栈容量 SqStack; SqStack S1,S2; typedef struct SNode datatype data; struct SNode *next; SNode

7、,*LinkStack; LinkStack S3;/栈名S为栈顶元素指针,2、括号匹配检验,正确：() 错误：() ( ) (),Status match( ) initstack(S);hasErr=0; while(c=getchar()!=n ,编译过程中尚需报告出错行数、忽略注释/字符串和字符常量等,思路:依次扫描各符号,每遇一结束符都找最近的开始符来匹配,不匹配或未找到则报错.最后应左右括号完全匹配毕 初始化一个空栈 逐个扫描符号 如果当前符号是开始符则入栈 如果是结束符号则分三种情况 如果栈空则报告出错 /右多 否则,出栈,若弹出元素与当前元素不匹配则报告出错/不匹配 否则无动作

8、，扫描下一符号 扫描结束,若栈不空则出错 /左多,3、行编辑程序,whli#ilr#e(s#*s) /while(*s) outchaputchar(*s=#+) /putchar(*s+);,思路:为提高数据输入效率设置输入缓冲区.对于输入的一行数据,行结束时方将缓冲区的数据存入用户数据区,中间过程允许编辑;若最近的一个字符出错则用退格符#表示删去,若当前行不要则用退行符则将当前行清空. 遇到行结束符前，每遇一个符号，若它不是#或则入栈,若是#则出栈,若是则清空栈，一旦遇到行结束符或全文结束符则将缓冲区中数据保存到用户数据区如此重复直到全文结束,void LineEdit() InitSta

9、ck(S); ch=getchar(); while(ch!=EOF)/全文未结束 while(ch!=n /行尾非EOF ,4、迷宫求解,令curPos指向入口,curStep为1,重复while(TRUE) 若当前位置通,则将其纳入路径(栈).是出口停,非出口重置curPos为右邻，开始下次循环 若当前位置不通,看上一步，若其四周均已访问过，则将其从路径中删除，如此重复直至找到一个曾经访问之位置，其四个方向至少有一个未曾访问过；此时重置curPos为此未访问邻块，开始下次循环。若栈空任然未找到则退出。,typedef int Maze1010;Maze maze;/或int maze101

10、0; typedef struct int x;int y;PosType;/迷宫中的位置类型 typedef structint ord;PosType seat;int di;SElemType;/栈元素类型 typedef structSElemType *base;SElemType *top; int stacksize; Stack;/栈类型,Status PassMaze(MazeType ,令curPos指向入口,curStep为1,重复while(TRUE) 若当前位置通,则将其纳入路径(栈).是出口停,非出口重置curPos为右邻，开始下次循环 若当前位置不通,看上一步，若

11、栈空无路径；若其四周均已访问过，则将其从路径中删除，如此重复直至找到一个曾经访问之位置，其四个方向至少有一个未曾访问过；此时重置curPos为此未访问邻块，开始下次循环。若栈空仍然未找到则退出。,例:计算 4+2*3-10/5# 2+4-3*6# (假设只有二元运算符) 注：拿当前扫描的符号与上一个比较优先级，当前扫描符号低或相等则进行上一个运算(需取最近的两个数据)；否则扫描下个 注:设操作符栈和操作数栈,运算符栈最初压入起始符#,逐个扫描符号: 遇操作数则直接入栈,继续读下一字符；遇运算符则与栈顶运算符比较优先级,当前运算符优先级高(前面的运算还不应执行)则当前运算符入栈,读下一符号;否则

12、栈顶运算符出栈,两操作数出栈,进行运算,所得结果入数栈, 开始下次循环(不扫描新符号，重新比较刚才扫描到的运算符与新栈顶运算符) 。如此重复直到栈顶运算符与当前符号均为(#),5、表达式求值算符优先法,-,*,#,#,#,设操作符栈和操作数栈,运算符栈最初压入#,逐个扫描符号:遇操作数则直接入栈,继续读下一字符；遇运算符则与栈顶运算符比较优先级,当前运算符优先级高(前面的运算还不应执行)则当前运算符入栈,读下一符号;否则栈顶运算符出栈,两操作数出栈,进行运算,所得结果入数栈,不扫描新符号开始下次循环。(重新比较刚才扫描到的运算符与新栈顶运算符)如此重复直到栈顶运算符与当前符号均为(#),Ini

13、tStack(OPTR);InitStack(OPND);Push(OPTR,#); c=getchar( ); while( c!=# | GetTop(OPTR)!=#) if( !In(c,OP) ) Push(OPND,c);c=getchar(); /操作数直接入栈 else switch(Precede(GetTop(OPTR),c)/比较栈顶运算符与c优先级 case : Pop(OPTR,theta); Pop(OPND,b); Pop(OPND,a); Push(OPND,Operate(a,theta,b); break; /switch /else /while; Ret

14、urn(GetTop(OPND)）；,作业:,3.1若按教科书P44中图3.1（b）所示铁道进行车厢调度（注意：两侧铁道均为单向行驶道,栈）,则请回答：,（1）如果进站的车厢序列为123，则可能得到的出站车厢序列是什么？,（2）如果进站车厢序列为123456，能否得到435612和135426的出站序列，并请说明为什么不能得到或者如何得到（既写出以S表示进栈和已X表示出栈的栈操作序列 ）。,3.19表达式已存入字符串中，检查括号匹配,3.3 栈与递归,专题课件,专题课件,1、 相关概念和类型定义 概念: 队列类似线性表和栈,也是定义在线性结构上的ADT,与线性表和栈的区别在于，元素的插入和删除

15、分别在表的两端进行。类似日常生活中排队,允许插入的一端为队尾(rear),允许删除端称队头(front) 特性:First In First Out先进先出，如操作系统中的作业队列和打印任务队列、日常生活中各类排队业务等均可用队列模拟,3.4 队 列(Queue),a2,an,e, ,a1,队头,队尾,入队列,出队列,队列的ADT定义,ADT Queue 数据对象：D=ai|aiElemSet,i=1,2,n,n=0 数据关系：R=|ai-1,aiD，约定a1为队头，an为对尾部 基本操作： InitQueue ( struct QNode *next; QNode, *QueuePtr;,t

16、ypedef struct QueuePtr front;/队头指针 QueuePtr rear; /队尾指针 LinkQueue;/ 链队列,队头元素,队尾元素,设立尾指针有什么好处?,基本操作实现初始化,a1,an,Q.front Q.rear,Status InitQueue (LinkQueue /时间复杂度O(1),Q.front Q.rear,基本操作实现销毁与清空,a1,an,Q.front Q.rear,Status DestroyQueue (LinkQueue /去掉下划线部分为置空操作, 复杂度O(n),基本操作实现入队,a1,an,Q.front Q.rear,Stat

17、us EnQueue (LinkQueue /复杂度O(1),基本操作实现出队,a1,an,Q.front Q.rear,Status DeQueue (LinkQueue /复杂度O(1),3、顺序队列的定义和操作实现,front与rear是int,删除队头不移动数据,直接front+,f,g,h,插入rear=(rear+1)%M 循环队列(臆造),如何判队列空？ 如何判队列“真”满？ 为区分队空和对真满,约定只剩一个元素空间时为队满（假满， (rear+1)%M=front),base,循环队列类型定义：,#define MAXQSIZE 100 /最大队列长度 typedef stru

18、ct QElemType *base;/ 动态分配存储空间 int front; / 头指针,队列不空则指向队列头元素 int rear;/尾指针,队列不空则指向队列尾元素下一位置 SqQueue;,记：注意队满和队空的判定条件，仅当“非空”时访问元素方能成功 可类似顺序表设初始大小与增量, 无统一标准,Status InitQueue (SqQueue /复杂度O(1),基本操作实现初始化,Status DestroyQueue(SqQueue /复杂度O(1)比链队列快,基本操作实现销毁和清空,Status EnQueue (SqQueue /时间复杂度O(1),基本操作实现：插入和删除,

19、Status DeQueue (SqQueue /时间复杂度O(1),int QueueLength(SqQueue Q) return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;/减可能为负 /时间复杂度O(1)，比链队列快，可修改链队列定义,基本操作实现：队长、队空、求首元、遍历,Status GetHead(SqQueue Q,QElemType / O(1)若要修改对头元素的值可新设SetHead( else return FALSE; /O(1),Status QueueTraverse(SqQueue Q, Status (*visit)(ElemType

20、) /从队头元素到队尾元素依次执行函数(*visit) for(int i=Q.front; i!=Q.rear; i=(i+1)%MAXQSIZE ) (*visit)(Q.basei); return OK; /O(n),常用于输出，如语句QueueTraverse(Q,PrintElem),用队列结构表示日常生活中的排队，用入队和出队表示排到队尾和服务完毕撤对，如银行业务模拟.注意课程设计选题。 可根据实际情况对队列的结构加以修改,如定义双端队列(两头均可插入/删除)、输入受限的双端队列(一侧只允许删除、另一侧插入删除均可)、输出受限的双端队列等,3.5 离散事件模拟,3.15假设以静态分配的顺序存储结构实现一个双向栈，既在一维数组的存储空间存在着两个栈，它们的栈底分别设在数组的两个端点。试编写实现这个双向栈的三个操作：初始化IniStack(tws)、入栈Push(tws,i,x)、和出栈Pop(tws,i)的算法，其中i 为0或1，用以分别指示设在数组两端的两个栈，并讨论按过程（正/误状态变量可设为变参）或函数设计这些操作算法各有什么优缺点