《数据结构》-桟和队列

教学进度教学进度计算机科学与工程系第三章栈和队列教学进度教学进度计算机科学与工程系L栈和队列是限定插入和删除只能在表的“端点”进行的线性表。L栈和队列是两种特殊的线性表，是操作受限的线性表，称限定性DS教学进度教学进度计算机科学与工程系31栈（STACK）栈的定义和特点定义限定仅在表尾进行插入或删除操作的线性表，表尾栈顶，表头栈底，不含元素的空表称空栈特点先进后出（FILO）或后进先出（LIFO）ANA1A2栈底栈顶出栈进栈栈SA1,A2,AN教学进度教学进度计算机科学与工程系教学进度教学进度计算机科学与工程系栈的类型定义ADTSTACK数据对象DAI|AIELEMSET,I1,2,N,N0数据关系R1|AI1,AID,I2,N约定AN端为栈顶，A1端为栈底。基本操作ADTSTACK教学进度教学进度计算机科学与工程系INITSTACK/栈元素存储空间INTTOP/栈顶指针SQSTACK；栈的数组存储表示顺序栈TOP栈空栈空0123456789MAX1ELEMENTS教学进度教学进度计算机科学与工程系栈顶指针TOP,指向实际栈顶后的空位置，初值为TOPBASETOP进栈ATOP出栈栈满BCDEFTOPBASE,栈空，此时出栈，则下溢（UNDERFLOWTOPBASESTACKSIZE,栈满，此时入栈，需重新分配空间，如空间分配失败则上溢（OVERFLOWTOPTOPTOPTOPTOPTOPTOPTOPTOPTOPTOP栈空BASE0123450栈空TOP0123450BASE123450ABCDEFBASE教学进度教学进度计算机科学与工程系TYPEDEFSTRUCTSELEMTYPEBASE/栈元素数组的首地址SELEMTYPETOP/栈顶指针INTSTACKSIZE/栈最大容量SQSTACK；栈的数组存储表示顺序栈TOP栈空栈空0123456789STACKSIZE1ELEMENTSDEFINESTACK_INIT_SIZE100DEFINESTACKINCREMENT10教学进度教学进度计算机科学与工程系TOP空栈TOPTOPTOPTOPTOPA进栈B进栈AABABCDEE进栈ABCDEF进栈溢出ABDEE退栈C教学进度教学进度计算机科学与工程系TOPC退栈B退栈ABAA退栈空栈TOPABDD退栈CTOPABCTOPTOP教学进度教学进度计算机科学与工程系STATUSINITSTACK（SQSTACKIFSBASEEXITOVERFLOW/存储失败存储失败STOPSBASESSTACKSIZESTACK_INIT_SIZERETURNOK/INITSTACK教学进度教学进度计算机科学与工程系STATUSGETTOPSQSTACK否则返回ERRORIFSTOPSBASERETURNERRORESTOP1RETURNOK/GETTOP教学进度教学进度计算机科学与工程系STATUSPUSHSQSTACKIFSBASEEXITOVERFLOW/存储分配失败存储分配失败STOPSBASESSTACKSIZESSTACKSIZESTACKINCREMENT/ENDIFSTOPERETURNOK/PUSH教学进度教学进度计算机科学与工程系STATUSPOPSQSTACK/否则返回否则返回ERRORIFSTOPSBASE/栈空栈空RETURNERRORESTOP/POP教学进度教学进度计算机科学与工程系DEFINESTACK_INIT_SIZE100DEFINESTACKINCREAMENT10TYPEDEFSTRUCTSELEMTYPEBASESELEMTYPETOPINTSTACKSIZESQSTACK栈的存储结构V顺序栈L实现动态教学进度教学进度计算机科学与工程系算法V构造空栈SV返回栈顶元素IFSTOPSBASERETURNERRORESTOP1V进栈IFSTOPSBASESSTACKSIZESBASEELEMTYPEREALLOCSBASE,SSTACKSIZESTACKINCREAMENTSIZEOFELEMTYPEIFSBASEEXITOVERFLOWSTOPSBASESSTACKSIZESSTACKSIZESTACKINCREAMENTSTOPE教学进度教学进度计算机科学与工程系V出栈IFSTOPSBASERETUENERRORESTOP教学进度教学进度计算机科学与工程系入栈算法L出栈算法教学进度教学进度计算机科学与工程系链栈栈顶TOPDATALINK栈底L结点定义L入栈算法L出栈算法TYPEDEFSTRUCTNODEINTDATASTRUCTNODENEXTJD栈底TOPTOPXPTOP栈底TOPQ教学进度教学进度计算机科学与工程系栈的链接存储表示链式栈N链式栈无栈满问题，空间可扩充链式栈无栈满问题，空间可扩充N插入与删除仅在栈顶处执行插入与删除仅在栈顶处执行N链式栈的栈顶在链头链式栈的栈顶在链头TOP教学进度教学进度计算机科学与工程系QUIZ一个栈的入栈序列是（A,B,C,D,E），不可能得到的输出序列有AEDCBABDECBACDCEABDABCDEC教学进度教学进度计算机科学与工程系栈的应用举例例一、数制转换例二、括号匹配的检验例三、行编辑程序问题例四、迷宫求解例五、表达式求值例六、实现递归教学进度教学进度计算机科学与工程系例一、数制转换算法基于原理NNDIVDDNMODD教学进度教学进度计算机科学与工程系V数制转换1591023781598198280237余7余3余2TOPTOP7TOP73TOP732栈的应用例把十进制数159转换成八进制数求解的时候从低位到高位输出的时候从高位到低位教学进度教学进度计算机科学与工程系VOIDCONVERSIONINITSTACKSSCANF“D“,NWHILENPUSHS,N8NN/8WHILESTACKEMPTYSPOPS,EPRINTF“D“,E/CONVERSION教学进度教学进度计算机科学与工程系例二、括号匹配的检验假设在表达式中（）或（）等为正确的格式，（）或（）或均为不正确的格式。则检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。教学进度教学进度计算机科学与工程系分析可能出现的不匹配的情况到来的右括弧非所“期待”的例如考虑下列括号序列12345678到来的是“不速之客”直到结束，也没有到来所“期待”的括弧教学进度教学进度计算机科学与工程系算法的设计思想1）凡出现左括弧，则进栈；2）凡出现右括弧，首先检查栈是否空若栈空，则表明该“右括弧”多余否则和栈顶元素比较，若相匹配，则“左括弧出栈”否则表明不匹配3）表达式检验结束时，若栈空，则表明表达式中匹配正确否则表明“左括弧”有余教学进度教学进度计算机科学与工程系TOPTOPTOPTOPTOPTOPTOP例如考虑下列括号序列（）123456教学进度教学进度计算机科学与工程系STATUSMATCHINGSTRINGWHILEI，则连续从栈中退出两个操作数Y和X，形成运算指令XY，并将计算结果重新压栈。N当表达式的所有项都扫描并处理完后，栈顶存放的就是最后的计算结果。教学进度教学进度计算机科学与工程系L如何从原表达式求得后缀式每个运算符的运算次序要由它之后的一个运算符来定，在后缀式中,优先数高的运算符领先于优先数低的运算符。分析“原表达式”和“后缀式”中的运算符原表达式ABCD/EF后缀式ABCDE/F教学进度教学进度计算机科学与工程系V表达式求值优先关系表教学进度教学进度计算机科学与工程系从原表达式求得后缀式的规律为1设立暂存运算符的栈2设表达式的结束符为“”,设运算符栈的栈底为“”3若当前字符是操作数，则直接发送给后缀式教学进度教学进度计算机科学与工程系4若当前运算符的优先数高于栈顶运算符，则进栈5否则，退出栈顶运算符发送给后缀式6“”对它之前后的运算符起隔离作用，“”可视为自相应左括弧开始的表达式的结束符。从原表达式求得后缀式的规律为VOIDTRANSFORMCHARSUFFIX,CHAREXPINITSTACKSPUSHS,PEXPCHPWHILESTACKEMPTYSIFINCH,OPPASSSUFFIX,CHELSEIFCHPCHPELSEPOPS,CHPASSSUFFIX,CH/WHILE/CRTEXPTREE教学进度教学进度计算机科学与工程系SWITCHCHCASEPUSHS,CHBREAKCASEPOPS,CWHILECPASSSUFFIX,CPOPS,CBREAKDEFULTWHILEGETTOPS,CPOPS,CIFCHPUSHS,CHBREAK/SWITCH教学进度教学进度计算机科学与工程系3（736/25）例将以下中缀表达式转为后缀表达式37362/5教学进度教学进度计算机科学与工程系3（736/25）/3（718/25）3（795）3（165）311中缀表达式求值教学进度教学进度计算机科学与工程系V表达式求值L后缀表达式3152270L中缀表达式3152270L中缀表达式到后缀表达式的转换基本思想顺序扫描中缀表达式，当读入一个运算分量时就立即输出，而在读入一个运算符时，首先把它压入一个运算符栈中，一直等到它的两个运算分量都读到后，才能把它输出，当扫描遇到一个左括号时立即把它推入栈中，继续扫描直到右括号出现，括号内的表达式也按如上规则进行压栈和输出。注意括号不必输出。L后缀表达式求值使用一个存放运算分量的栈，求值过程顺序扫描后缀表达式，每次遇到运算分量就把它推如栈中，遇到运算符，就从栈中弹出两个运算分量进行运算，再打运算结果推入栈中。扫描结束，留在栈定的即为表达式的值输入3（736/25运算对象栈运算符栈373618/291651133教学进度教学进度计算机科学与工程系中缀算术表达式求值中缀算术表达式求值N对中缀表达式求值的一般规则对中缀表达式求值的一般规则1建立并初始化建立并初始化OPTR栈和栈和OPND栈，栈，然后然后在在OPTR栈中压入一个栈中压入一个“”2从头扫描中缀表达式，取一字符送入从头扫描中缀表达式，取一字符送入CH。3当当CH或或OPTR栈的栈顶栈的栈顶时时,执行以下工作执行以下工作,否则结束算法。此时否则结束算法。此时在在OPND栈栈的栈顶得到运算结果。的栈顶得到运算结果。教学进度教学进度计算机科学与工程系若若CH是是操作数操作数，进，进OPND栈栈，从中缀表达，从中缀表达式取下一字符送入式取下一字符送入CH；若若CH是是操作符操作符，比较，比较ICPCH的优先级和的优先级和ISPOPTR的优先级的优先级U若若ICPCHISPOPTR，则，则CH进进OPTR栈栈，从中缀表达式取下一字符送入，从中缀表达式取下一字符送入CH；U若若ICPCH1时，先把上面N1个圆盘从A移到B,然后将N号盘从A移到C,再将N1个盘从B移到C。即把求解N个圆盘的HANOI问题转化为求解N1个圆盘的HANOI问题，依次类推，直至转化成只有一个圆盘的HANOI问题L执行情况U递归工作栈保存内容形参N,X,Y,Z和返回地址U返回地址用行编号表示NXYZ返回地址教学进度教学进度计算机科学与工程系MAININTMPRINTF“INPUTNUMBEROFDISKS”SCANF“D“,PRINTF”STEPS3DDISKS”,MHANOIM,A,B,C0VOIDHANOIINTN,CHARX,CHARY,CHARZ12IFN13MOVE1,X,Z4ELSE5HANOIN1,X,Z,Y6MOVEN,X,Z7HANOIN1,Y,X,Z89ABC1233ABC03ABC02ACB63ABC02ACB61ABC6ABC3ABC02ACB6教学进度教学进度计算机科学与工程系MAININTMPRINTF“INPUTTHENUMBEROFDISKSSCANF“D“,PRINTF“THESTEPSTOMOVING3DHANOIM,A,B,C0VOIDHANOIINTN,CHARX,CHARY,CHARZ12IFN13MOVE1,X,Z4ELSE5HANOIN1,X,Z,Y6MOVEN,X,Z7HANOIN1,Y,X,Z89ABC3ABC02ACB61CAB8ABC3ABC02ACB63ABC03ABC02ACB6教学进度教学进度计算机科学与工程系MAININTMPRINTF“INPUTTHENUMBEROFDISKSSCANF“D“,PRINTF“THESTEPSTOMOVING3DHANOIM,A,B,C0VOIDHANOIINTN,CHARX,CHARY,CHARZ12IFN13MOVE1,X,Z4ELSE5HANOIN1,X,Z,Y6MOVEN,X,Z7HANOIN1,Y,X,Z89ABC3ABC02ACB61CAB8ABC3ABC02ACB63ABC03ABC02ACB6教学进度教学进度计算机科学与工程系MAININTMPRINTF“INPUTTHENUMBEROFDISKSSCANF“D“,PRINTF“THESTEPSTOMOVING3DHANOIM,A,B,C0VOIDHANOIINTN,CHARX,CHARY,CHARZ12IFN13MOVE1,X,Z4ELSE5HANOIN1,X,Z,Y6MOVEN,X,Z7HANOIN1,Y,X,Z89ABC3ABC02BAC81ABC8ABC3ABC02BAC83ABC0栈空3ABC02BAC8教学进度教学进度计算机科学与工程系作业1编写顺序栈的进栈和出栈操作的算法2编写链栈的进栈和出栈操作的算法3利用栈实现括号匹配上机实现教学进度教学进度计算机科学与工程系QUEUE（队列）教学进度教学进度计算机科学与工程系32队列队列的定义及特点定义队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表队尾REAR允许插入的一端队头FRONT允许删除的一端队列特点先进先出FIFOA1A2A3AN入队出队FRONTREAR队列QA1,A2,ANV双端队列A1A2A3AN端1端2入队出队入队出队教学进度教学进度计算机科学与工程系队列的基本操作INITQUEUESTRUCTQNODENEXTQNODE,QUEUEPTR头结点FRONT队头队尾REAR设队首、队尾指针FRONT和REAR,FRONT指向头结点，REAR指向队尾TYPEDEFSTRUCTQUEUEPTRFRONTQUEUEPTRREARLINKQUEUEV链表定义教学进度教学进度计算机科学与工程系FRONTREARX入队XFRONTREARY入队XYFRONTREARX出队XYFRONTREAR空队FRONTREARY出队教学进度教学进度计算机科学与工程系V入队算法V出队算法V构造空队列算法V销毁队列算法队列的顺序存储结构V实现FRONT0REAR0123450队空123450FRONTJ1,J1,J3入队J1J2J3REARJ4J5J6REAR123450J4,J5,J6入队FRONT设两个游标FRONT,REAR,约定REAR指示队尾元素后一个下标；FRONT指示队头元素初值FRONTREAR0空队列条件FRONTREAR入队列QBASEREARX出队列XQBASEFRONTREARREARREARJ1J2123450J1,J2,J3出队J3FRONTFRONTFRONTFRONT约定每当插入新的队列尾元素,“尾游标增1”每当删除队列头元素,“头游标增1”V存在问题设数组大小为M，则L当FRONT0,REARM时，再有元素入队发生溢出真溢出L当FRONT0,REARM时，再有元素入队发生溢出假溢出V解决方案L队首固定，每次出队剩余元素向下移动浪费时间L循环队列U基本思想把队列设想成环形，让Q0接在QM1之后，若REAR1M,则令REAR00M11FRONTREARU实现利用“模”运算U入队QBASEREARXREARREAR1MU出队XQBASEFRONTFRONTFRONT1MU队满、队空判定条件012345REARFRONTJ5J6J7012345REARFRONTJ4J9J8J4J5J6012345REARFRONT初始状态J4,J5,J6出队J7,J8,J9入队队空FRONTREAR队满FRONTREAR解决方案1另外设一个标志以区别队空、队满2少用一个元素空间队空FRONTREAR队满REAR1MFRONT教学进度教学进度计算机科学与工程系POJ3278CATCHTHATCOWFARMERJ