数据结构第3章.ppt

《数据结构第3章.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第三章栈和队列3.1栈3.2栈的应用举例3.3队列——操作特殊的线性表a1进栈出栈的示意图：a1a1a1a2a2a2a2...anananananana2a2ana2a1a1a1a1ana2......3.1栈一、栈的特点：满足先进后出，后进先出的线性表。二、ADT定义：数据对象：D={ai

2、ai∈ElemsSet,i=1,2,…,n,n≥0}数据关系：R1={

3、ai-1,ai∈D,i=1,2,…,n}an端为栈顶，a1端为栈底。基本操作：Initstack(&S)初始化操作；Destro

4、ystack(&S)销毁栈Stackempty(S)判栈空函数；Push(&S,x)入栈操作；Pop(&S,&e)出栈函数；GetTop(S,&e)取栈顶元素函数；Clearstack(&S)栈置空操作；Stacklength(S)求当前栈中元素个数函数。１、顺序结构：利用地址连续的存储单元依次存放自栈底到栈顶的数据元素。typestruct{SElemType*base;SElemType*top;intstacksize;}SqStack;２、链式结构：与线性表类似。三、栈的存储结构：3.1栈ana1an-1

5、S栈顶栈底思考题1、已知入栈序列为XYZW，以下序列哪些是允许的出栈序列：WZYX，XYZW，ZYXW，ZXYW。2、已知入栈序列为XYZ，现有两个单元的栈空间，问你能调度出多少种出栈序列。数制转换：将十进制转化为任意进制3.2栈的应用举例voidconversion(){Initstack(S);scanf(“%d”,N);while(N){Push(S,N%8);N=N/8;}while(!Stackempty(S)){Pop(S,e);Printf(“%d”,e);}}括号匹配的检验1.只有小括号的表达式2

6、.包含有各种括号的表达式行编辑程序3.2栈的应用举例voidLinedit(){Initstack(S);ch=getchar();while(ch!=EOF){while(ch!=EOF&&ch!=‘’){switch(ch){case‘#’:Pop(S,c);break;case‘@’:Clearstack(S);break;default:Push(S,ch);}ch=getchar();}Clearstack(S);if(ch!=EOF)ch=getchar();}}迷宫求解：这是栈的应用的典型例题。

7、具体算法思想是：3.2栈的应用举例从演示过程可见：1．从入口进入迷宫之后，不管在迷宫的哪一个位置上，都是先往东走，如果走得通就继续往东走，如果在某个位置上往东走不通的话，就依次试探往南、往西和往北方向，从一个走得通的方向继续往前直到出口为止；2．如果在某个位置上四个方向都走不通的话，就退回到前一个位置，换一个方向再试，如果这个位置已经没有方向可试了就再退一步，如果所有已经走过的位置的四个方向都试探过了，一直退到起始点都没有走通，那就说明这个迷宫根本不通；3．所谓"走不通"不单是指遇到"墙挡路"，还有"已经走过的路

8、不能重复走第二次"，它包括"曾经走过而没有走通的路"。　　显然为了保证在任何位置上都能沿原路退回，需要用一个"后进先出"的结构即栈来保存从入口到当前位置的路径。并且在走出出口之后，栈中保存的正是一条从入口到出口的路径。由此，求迷宫中一条路径的算法的基本思想是：　　若当前位置"可通"，则纳入"当前路径"，并继续朝"下一位置"探索；若当前位置"不可通"，则应顺着"来的方向"退回到"前一通道块"，然后朝着除"来向"之外的其他方向继续探索；若该通道块的四周四个方块均"不可通"，则应从"当前路径"上删除该通道块。3.2

9、栈的应用举例——表达式求值1、比较优先级存储取括号运算+-*/（）#+>><<<>>->><<<>>*>>>><>>/>>>><>>(<<<<<=)>>>>>>#<<<<<=3.2栈的应用举例——表达式求值2、算法思想：为实现算符优先法，可以使用两个工作栈。一个称做OPTR，用以寄存运算符；另一个称做OPND，用以寄存操作数或运算结果。基本思想：1）首先置操作数栈为空栈，表达式起始符“#”为运算符栈的栈底元素；2）依次读入表达式中每个字符，若是操作数则进OPND栈，若是运算符，则和OPTR栈的栈顶运算符比较优先权

10、后作相应操作，直至整个表达式求值完毕（即OPTR栈的栈顶元素和当前读入的字符为“#”）。3.2栈的应用举例——表达式求值3、算法实现：例：3*（7-2）#OperandtypeEvaluateExpress(){Initstack(OPTR);Push(OPTR,’#’);Initstack(OPND);c=getchar();while(c!=‘#’

11、

12、Gettop(O