数据结构第3章栈和队列.ppt

,特殊线性表,栈,队列,串,逻辑结构,逻辑结构,逻辑结构,物理结构,物理结构,物理结构,顺序栈,链式栈,顺序队列,顺序存储,链式队列,链式存储,栈的定义操作特性ADT定义,队列定义操作特性ADT定义,串的定义操作特性ADT定义,基本操作的实现时间性能,基本操作的实现时间性能,模式匹配,第三章栈和队列,栈和队列是两种特殊的线性表，是操作受限的线性表，称限定性DS,“取”操作必须在这端进行,“放”操作必须在同一端进行,3.1栈（stack）定义：限定仅在表尾进行插入或删除操作的线性表。,表尾栈顶表头栈底不含元素的空表称空栈特点：先进后出（FILO）,3.1.1抽象数据类型栈的定义,ADTStack数据对象：Dai|aiElemSet,i=0,1,.,n-1,n0数据关系：R1|ai-1,aiD,i=1,.,n-1约定an-1端为栈顶，a0端为栈底。基本操作：InitStack(ADTStack,3.1.2栈的表示与实现,顺序栈：是利用一块地址连续的存储单元来存放栈中的元素，同时要利用一个指针top来指示栈顶元素的位置。,/-栈的顺序存储表示-#defineSTACK_INIT_SIZE100;#defineSTACKINCREMENT10;typedefstructSElemType*base;SElemType*top;intstacksize;SqStack;,顺序栈示意图,初始空栈,*top=*base;stacksize=STACK_INIT_SIZE,顺序栈,栈的几种状态示意图,栈顶指针top,指向实际栈顶后的空位置，初值为0,进栈,A,出栈,栈满,B,C,D,E,F,设数组维数为Mtop=0,栈空，此时出栈，则下溢（underflow)top=M,栈满，此时入栈，则上溢（overflow),栈空,StatusInitStack(SqStack,在此存储结构下的基本操作实现:,StatusPush(SqStack,StatusPop(SqStack,2.链栈（1）链栈的存储结构链栈是指采用链式存储结构存储的栈。链栈是一种特殊的单链表，即限定仅在表头进行插入和删除操作的单链表，因此链栈的结点结构与单链表的结点结构相同。,top,datanext,栈顶,栈底,3.2栈的应用举例,3.2.1数制转换十进制N和其它进制数的转换是计算机实现计算的基本问题,其中一个简单算法基于下列原理:N=(Ndivd)10d+Nmodd例如:(1348)10=283+582+08+4=(2504)8NNdiv8Nmod8134816841682102125202,结果：2504,计算时从低位到高位顺序产生八进制数的各个数位,显示时按从高位到低位的顺序输出,voidconversion()InitStack(s);/建空栈scanf(“%d”,3.2.2括号匹配的检验假设在表达式中（）或（）等为正确的格式，（）或（）或（）)均为不正确的格式。,则检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。,例如：考虑下列括号序列：()12345678,到来的右括弧并非是所“期待”的；到来的是“不速之客”；直到结束，也没有到来所“期待”的括弧,分析可能出现的不匹配的情况:,算法的设计思想：,1）凡出现左括弧，则进栈；,2）凡出现右括弧，首先检查栈是否空若栈空，则表明该“右括弧”多余，否则和栈顶元素比较，若相匹配，则“左括弧出栈”，否则表明不匹配。,3）表达式检验结束时，若栈空，则表明表达式中匹配正确，否则表明“左括弧”有余。,Statusmatching(SELemType*p)intflag=1;SELemTypec;Stack1S;InitStack1(S);while(*p,3.2.3行编辑程序,行编辑器的功能为：接受用户从终端输入的程序或数据，并存入用户的数据区。由于用户在终端进行输入时，不能保证不出差错，所以在编辑程序中，“每接受一个字符即存入用户数据区”的做法不当。因此，在编辑程序中，设立一个输入缓冲区，用于接受用户输入的一行字符，然后逐行存入用户数据区。允许用户输入错误，并在发现有误时可以及时更正。如果约定为退格符，以表示前一个字符无效，为退行符，表示当前行所有字符均无效。则whli#ilr#e(s#*s)outchaputchar(*s=#+)应为while(*s)putchar(*s+),字符在存入缓冲区时是按“后进先出”的规律进行的，所以用栈表示输入缓冲区最合适。当从终端接受了一个字符后做如下判断：如果它既不是退格符也不是退行符，则将该字符压入栈顶；如果它是一个退格符，则从栈顶删去一个字符；如果它是一个退行符，则将栈清空。,voidLineEdit()InitStack(S);/构造空栈Sch=getchar();/从终端接收第一字符while(ch!=EOF)/EOF为全文结束符while(ch!=EOF,3.2.4迷宫求解入口,出口,迷宫问题：求迷宫中从入口点到出口点所有可能的简单路径,所谓的简单路径是指：在求出的任何一条路径上，不能重现某一通道块，否则总有任意多条路径迷宫问题是许多实际问题的抽象，求解这类问题时，没有现成的数学公式可以套用，只能采用系统化的试探方法。下面规定：通道用空格“”表示墙壁用“#”表示足迹用“0”表示从入口点到当前立足点间，具有足迹标志的相连的通道块构成的简单路径叫当前路径将迷宫模型用二维字符型数组表示：charmazen+1n+1;并假定入口为maze00，出口为mazenn考虑一般情况，设mazeij为当前立足点，并纳入当前路径（即印上足迹标志“0”），则从当前立足点继续试探的算法如下：,ifmazeij是出口then打印刚找到的一条简单路径，并回溯一步；elseif东面的是通道块then前进一步elseif南面的是通道块then前进一步elseif西面的是通道块then前进一步elseif北面的是通道块then前进一步else回溯一步,(i,j),东,南,西,北,前进一步：将下一通道块印上“0”作为当前立足点（切换当前立足点），并保存原立足点的信息以便回溯。回溯一步：去掉当前立足点的足迹“0”;把最近的原立足点重新切换为当前立足点；试探尚未试探过的方向。上述的活动均需要在迷宫中移动，并且具有方向性，这种活动可以使用二维数组下标增量技术来实现：行下标增量dik列下标增量djk方向及其序号k东0南1西2北3intdi4=0,1,0,-1;intdj4=1,0,-1,0;,0,1,1,0,0,1,1,0,在上述的规定下：k=0时，mazei+dikj+djk为立足点的东面下一块；k=1时，mazei+dikj+djk为立足点的南面下一块；k=2时，mazei+dikj+djk为立足点的西面下一块；k=3时，mazei+dikj+djk为立足点的北面下一块；客体的表示方法设计：从上述的用试探法走迷宫的过程可知，其中所管理的信息是立足点的信息。可以用三元组（i,j,k)来表示立足点，其中(i,j)表示立足点的位置信息，k表示立足点的下一个试探方向。可以将三元组定义成一个结构：structitemsinti,j,k;数据的组织方法设计：考察上述用试探法走迷宫的过程：前进一步时，需要保存原立足点的信息；回溯一步时，需要取出最近的原立足点的信息，并且遵循后保存的先取出的原则，即“后进先出”的原则，因此可以用栈来记录立足点的信息。迷宫问题的算法框架：,1Stacks(sz);/栈初始化：创建一个大小为sz的栈，其数据元素类型为items2itemse;intk;3e.i=0;e.j=0;e.k=0;s.Push(e);mazee.ie.j=0;/将入口作为立足点并入栈4while(!s.IsEmpty()/若栈不空则继续循环试探/若空表示已找到所有简单路径，可以结束程序5e=s.Pop();/出栈，准备试探下一方向或实现回溯一步操作6if(e.k=4)mazee.ie.j=;/四个方向均试探完毕/消足迹,当再执行到5时回溯一步elseif(e.i=n,3.2.5表达式求值1）问题的提出设计一个小计算器:对键入的表达式进行求值。,高级语言中的赋值语句：变量=表达式；,2）表达式的构成操作数+运算符+界符（如括号）3）表达式的求值：例5+6(1+2)-4按照四则运算法则，上述表达式的计算过程为：5+6(1+2)-4=5+63-4=5+18-4=23-4=19,1,2,3,4,运算符和界限符统称为算符。根据算术四则运算的规则（即中缀式的运算规则），任两个相继出现的算符1和2之间的优先关系至多是下面三种关系之一：121的优先权高于2,算符间的优先关系,2,1,算法需两个栈。一个是运算符栈(OPTR)；另一个是操作数或运算结果栈(OPND)。算法的基本思想是：（1）首先置操作数栈为空栈；为了使表达式中第一个运算符能够进栈，首先将一个优先权最低的运算符#压入运算符栈中成为其栈底。（2）从左向右依次读出表达式中的每一个字符，若为操作数，则将其压入操作数栈中，接着读出下一个字符；若为运算符，则和运算符栈的栈顶运算符比较优先权：如果读出的运算符的优先权高于运算符栈栈顶运算符的优先权，则将其压入运算符栈中，接着读出下一个字符；,如果读出的运算符的优先权等于运算符栈栈顶运算符的优先权（即左右括号相遇），则从运算符栈中退出一个运算符（即左括号）；如果读出的运算符的优先权低于运算符栈栈顶运算符的优先权，则从操作数栈连续退出两个操作数（先退出的是第二操作数，后退出的是第一操作数），从运算符栈中退出一个运算符，然后作相应的运算，并将运算结果压入操作数栈中。算法中还调用了两个函数。其中Precede()的功能是判断两个运算符1和2的优先关系；Operate()的功能是求两数a和b作运算的结果。,表达式求值示意图：5+6(1+2)-4,#,5,+,6,(,1,+,2,3,18,23,-,4,19,5,读入表达式过程：,+,6,(,1,+,2,),-,4,#,=19,1+2=3,63=18,5+18=23,23-4=19,一个直接调用自己或者通过一系列的调用语句间接地调用自己的函数，称为递归函数。很多数学函数是递归定义的，如阶乘函数若n=0若n02阶Fibonacci数列若n=0若n=1其他情形,3.3栈与递归的实现,递归函数执行过程的信息传递和控制转移可以用栈结构来实现。系统将整个程序运行时所需的空间安排在一个栈中，每当调用一个函数时，就为它在栈顶分配一个存储区，每当退出一个函数时，就释放它所占用的存储区，当前工作的函数的数据区总在栈顶。例如，递归函数fact（4）的执行过程如图所示，,例递归的执行情况分析,voidprint(intw)inti;if(w!=0)print(w-1);for(i=1;i1时，先把上面n-1个圆盘从A移到B,然后将n号盘从A移到C,再将n-1个盘从B移到C。即把求解n个圆盘的Hanoi问题转化为求解n-1个圆盘的Hanoi问题，依次类推，直至转化成只有一个圆盘的Hanoi问题,main()/*Hanoi.txt*/intm;printf(Inputthenumberofdisks:);scanf(%d,voidmove(inth,charc,charf)printf(%d:%c-%cn,h,c,f);,main()intm;printf(Inputnumberofdisks”);scanf(%d,(8)(9),main()intm;printf(Inputthenumberofdisksscanf(%d,(8)(9),main()intm;printf(Inputthenumberofdisksscanf(%d,(8)(9),main()intm;printf(Inputthenumberofdisksscanf(%d,(8)(9),回文游戏：顺读与逆读字符串一样（不含空格）,1.读入字符串2.去掉空格（原串）3.压入栈4.原串字符与出栈字符依次比较若不等，非回文若直到栈空都相等，回文,字符串：“madamimadam”,地图四染色问题,1,2,2,3,4,1,4,3,3,4,2,3,1#紫色2#黄色3#红色4#绿色,“四染色”定理是计算机科学中著名定理之一，即可以用不多于四色对地图着色，使相邻的行政区域不重色。我们应用这个定理的结论，用回溯算法对一幅给定的地图染色。,算法思想：从第一号行政区开始逐一染色，每一个区域逐次用颜色1、2、3、4进行试探。若当前所取的色数与周围已染色的行政区不重色，则用栈记下该行政区的色数，否则依次用下一色数进行试探；若出现用1至4色均与相邻区域发生重色，则需退栈回溯，修改当前栈顶的色数，再进行试探。直至所有行政区域都已分配合适的颜色。,voidmain(void)stack_init();push(0,1);while(!stack_empty()pop(x,c);if(c=5)colorx=0;continue;push(x,c+1);if(check(x,c,next)colorx=c;if(next!=-1)push(next,1);elsegotoend;end:for(x=0;xfront=Q-rear=(QueuPtr)malloc(sizeof(QNode);if(!Q-front)exit(OVERFLOW);Q-front-next=NULL;returnOK;,2）队列入队运算将结点加入到队列Q的尾端,StatusEnQuene(