C_char_3栈与队列

1,第三章栈和队列3.1栈3.2栈的应用举例3.3栈与递归的实现3.4队列3.5离散事件模拟,线性表栈队列Insert(L,i,x)Insert(S,n+1,x)Insert(Q,n+1,x)1in+1Delete(L,i)Delete(S,n)Delete(Q,1)1in,栈和队列都属于线性结构,但是是操作受到限制的线性结构。它们的操作集合是线性表操作集合的子集。栈和队列在程序设计中被广泛应用，是两种重要的结构类型。,2,第三章栈和队列3.1栈1.栈的逻辑结构栈：是限定仅在表尾进行插入或删除操作的线性表栈顶：表尾端（允许插入和删除操作的一端）称为栈顶栈底：表头端称为栈底。栈的操作特性：后进先出（LIFO）,3,3.1栈1.抽象数据类型栈的定义,ADTStack数据对象：Dai|aiElemSet,i=1,2,.,n,n0数据关系：R1|ai-1,aiD,i=2,.,n约定an端为栈顶，a1端为栈底。,基本操作：,ADTStack,NOTE:下面的基本操作,无论是定义成函数还是过程,都只是一种形式定义，其实现依赖于栈所采用的存储结构。,4,2.栈的基本操作InitStack(/栈存储空间初始分配量#defineSTACKINCREMENT10;/栈存储空间分配增量typedefstructSElemType*base;/构造之前和销毁之后base=NULLSElemType*top;/栈顶指针intstacksize;/当前已分配的存储空间，以元素为单位。SqStack;,6,下面是顺序存储结构的栈的基本操作的实现:1).InitStack(,7,2).GetTop(S,8,3).Push(/Push,9,4).Pop(/Pop,10,4.栈的链式存储结构链式存储结构的栈在高级语言中可以描述成单链表.把单链表作为栈使用时,把链表的表头位置作为栈的栈顶,并且不设头结点.其结构描述如下:,typedefstructLNodeElemTypedata;/数据域structLnode*next;/指针域LNode,*LinkList;typedefLinkListLstack,下面是链栈操作示意图:,下面是链栈基本操作的实现:,11,1).InitStack(,12,3).Push(/Push,13,4).Pop(/Pop,14,3.2栈的应用举例,例一、数制转换,算法基本原理：N=(Ndivd)d+Nmodd,例如：（1348)10=(2504)8，其运算过程如下：NNdiv8Nmod8134816841682102125202,计算顺序,输出顺序,15,voidconversion()InitStack(S);scanf(%d,N);while(N)Push(S,N%8);N=N/8;while(!StackEmpty(S)Pop(S,e);printf(%d,e);/conversion,16,例二、括号匹配的检验假设在表达式中（）或（）等为正确的格式，（）或（）或()均为不正确的格式。,则检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。,分析可能出现的不匹配的情况:,到来的右括弧非是所“期待”的;,例如：考虑下列括号序列：()12345678,到来的是“不速之客”;,直到结束，也没有到来所“期待”的括弧;,17,算法的设计思想：,1）凡出现左括弧，则进栈；,2）凡出现右括弧，首先检查栈是否空若栈空，则表明该“右括弧”多余否则和栈顶元素比较，若相匹配，则“左括弧出栈”否则表明不匹配,3）表达式检验结束时，若栈空，则表明表达式中匹配正确否则表明“左括弧”有余,18,例2：假设算术表达式中可包括三种括号，(),可按任意次序嵌套使用，判别给定表达式中所含括号是否是配对出现的算法。Statusmatch()InitStack(S);while(c=getchar()!=n)if(In(c,”(”)Push(S,c);elseif(In(c,“)”)if(StackEmpty(S)return(ERROR);elsePop(S,a);if(!comp(a,c)return(ERROR);if(!StackEmpty(S)return(ERROR);elsereturn(OK);/match;,19,例三：表达式求值表达式求值是程序设计语言的编译程序中的一个最基本的问题.表达式求值有多种方法,利用栈对表达式求值是其中的一种,也是栈应用的一个典型例子.例：表达式：4+5*4/(2+5);下面介绍的算符优先法,就是利用栈结构来对表达式求值.其步骤如下:1.确定算符运算的优先顺序,即算符的优先级这里假设只处理下面这些运算符:+-*/()一般地,假设表达式以界限符开始和结束:#,在运算的每一步，任意两个相继出现的运算符1和2之间的关系只有以下三种。121212把运算符和界限符一起称算符,确定算符的优先级如下:,3*(3+4)+56+4-3*25+6/3-4*2,20,2.按照确定的优先级,计算特定表达式的值.计算方法如下:设定操作数栈OPND和运算符栈OPTR,OPND初始化为空,OPTR初始化为只包含起始符#自左至右,依次读入表达式中每个单词,若为操作数则进OPND栈,若为运算符,则转向比较当前读入的运算符(2)和OPTR栈顶运算符(1)的优先级21:栈顶元素优先级低,则将当前读入的运算符进OPTR栈,然后转向,21,表达式计算示例(3*(34-28)+7)/5-3对表达式加上起始符和结束符:#(3*(34-28)+7)/5-3#,步骤OPNDOPTR当前读入的单词w操作,初始化#(进OPTR栈1#(33进OPND栈23#(*进OPTR栈33#(*(（进OPTR栈43#(*(3434进OPND栈5334#(*(-进OPTR栈6334#(*(-2828进OPND栈733428#(*(-)34和28出栈,-出栈34-28=6进OPND栈836#(*()脱括弧936#(*+3和6出栈*出栈3*6=18进OPND栈1018#(+进OPTR栈,1118#(+77进OPND栈,12187#(+)18和7出栈+出栈18+7=25进OPND栈1325#()脱括弧1425#/进OPTR栈1525#/55进OPND栈16255#/-25和5出栈/出栈25/5=5进OPND栈175#-进OPTR栈185#-33进OPND栈1953#-#5和3出栈-出栈5-3=2进OPND栈202#运算结束,22,OperandTypeEvaluateExpression()/算法表达式求值的算符优先算法；设OPTR,OPND为运算符栈/和操作数栈，OP为运算符的集合InitStack(OPTR);Push(OPTR,“#”);InitStack(OPND);c=getitem();while(c!=#|GetTop(OPTR)!=#)if(!In(c,OP)Push(OPND,c);c=getitem();/不是运算符则进栈elseswitch(precede(GetTop(OPTR),c)case:/退栈并将运算结果入栈Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,a);Push(OPND,operate(a,theta,b);break;/switch/whilereturn(GetTop(OPND)/EvaluateExpression,23,3.3栈与递归的实现,将所有的实在参数、返回地址等信息传递给被调用函数保存;为被调用函数的局部变量分配存储区;将控制转移到被调用函数的入口。,当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三项任务：,保存被调函数的计算结果;释放被调函数的数据区;依照被调函数保存的返回地址将控制转移到调用函数。,从被调用函数返回调用函数之前，应该完成下列三项任务：,24,多个函数嵌套调用的规则是:,此时的内存管理实行“栈式管理”,后调用先返回！,例如：voidmain()voida()voidb()a();b();/main/a/b,Main的数据区,函数a的数据区,函数b的数据区,25,递归工作栈：递归执行过程中占用的数据区。递归工作记录：每一层的递归参数合成一个记录。当前活动记录：栈顶记录指示当前层的执行情况。当前环境指针：递归工作栈的栈顶指针。,递归函数执行的过程可视为同一函数进行嵌套调用，例如：,26,voidhanoi(intn,charx,chary,charz)/将塔座x上按直径由小到大且至上而下的1至n/个圆盘按规则搬到塔座z上，y可用作辅助塔座。12if(n=1)3move(x,1,z);/将个圆盘从x移到z4else5hanoi(n-1,x,z,y);/将x上至n-1个/圆盘移到y,z作辅助塔6move(x,n,z);/将第n个圆盘从x移到z7hanoi(n-1,y,x,z);/将y上至n-1个/圆盘移到z,x作辅助塔89,函数的执行过程与递归工作栈,27,3.4队列队列的逻辑结构队列:是限定仅在表的一端进行插入,而在另一端进行删除的线性表.队头:允许删除的一端称为队头队尾:允许插入的一端称为队尾队列的操作特性:先进先出(FIFO),3.4.1抽象数据类型队列的定义ADTQueue数据对象：Dai|aiElemSet,i=1,2,.,n,n0数据关系：R1|ai-1,aiD,i=2,.,n约定其中a1端为队列头，an端为队列尾基本操作：ADTQueue,28,队列的基本操作：,InitQueue(structQNode*next;QNode,*QueuePtr;,typedefstruct/链队列类型QueuePtrfront;/队头指针QueuePtrrear;/队尾指针LinkQueue;,空队列,31,下面是链式存储结构的队列的基本操作的实现:1)InitQueue(,32,StatusEnQueue(LinkQueue,33,StatusDeQueue(LinkQueue,if(Q.rear=p)Q.rear=Q.front;,34,3.4.3循环队列队列的顺序表示与实现,队列的顺序存储结构中，需要附设两个指针front和rear分别指向队列的头与队列的尾，为了在C语言中描述方便，初始化建立队列时，令front=rear=0;每当插入新元素时，尾指针增1，每当删除队列头元素时，头指针增1，因此，队列头指针始终指向队列头元素，而队列尾指针始终指向队列尾元素的下一个位置。,队列的顺序存储实现存在假溢出现象。,35,所谓循环队列,即仍然用一维数组来描述顺序存储结构的队列.只不过假设把数组的第一个单元看作是最后一个单元的后继,使数组首尾相接.下面是循环队列的操作示意图:,顺序存储结构的队列存在假溢出问题,可用循环队列来解决.,A,B,C,为了能够简单地区分队列满和空的两种状态,当队列中仍存在一个空单元时,认为队列已处于满状态.,3.4.3循环队列队列的顺序表示与实现,36,下面是循环队列的结构描述:#defineMAXQSIZE100/最大队列长度typedefstructQElemType*base;/初始化的动态分配存储空间intfront;/头指针，若队列不空，指向队列头元素intrear;/尾指针,若队列不空,指向队列尾元素的下一个位置SqQueu