数据结构参与命题课件第3章栈

1、 算 法 与 数 据 结 构 Algorithms and Data Structures第3章栈3.1 ADT 栈3.2 ADT栈的实现3.3 ADT栈的应用2011-9-291吴英杰 算 法 与 数 据 结 构 Algorithms and Data Structures3.1 ADT栈（stack）1、栈的定义和特点定义：限定仅在表首进行或删除操作的线性表，表首栈顶，表尾栈底，不含元素的空表称空栈特点：先进后出（FILO）或后进先出（LIFO）进栈栈顶出栈栈S=(a1,a2,an)栈底2011-9-292.ana2a1 算 法 与 数 据 结 构 Algorithms a d Data

2、Structures3.1ADT栈(Stack)2、ADT栈上定义的常用的基本运算：StackEmpty(S): 判断栈空StackFull(S):判断栈满(3) StackTop(S): 返回栈顶元素(4) Push(x, S):将元素入栈(5) Pop(S):出栈，删除并返回栈S的栈顶元素2011-9-293 算 法 与 数 据 结 构 Algorithms a d Data StructuresADT栈(Stack)3.13、栈应用的简单例子：(1)程序编译时的表达式或字符串的括号匹配问题。例如，算术表达式(x*(x+y)-z)，其中位置1和4处有号，而位置8和11处有右括号，满足配对要

3、求。但算术表达式有可与之配对的对的右号。(x+y)*z)(，其中位置8处的右括号没号，而位置9处的号没有可与之配2011-9-294 算 法 与 数 据 结 构 Algorithms and Data Structures表达式括号匹配算法void Parenthesis(char *expr)/ 表达式括号匹配i,n;Stack ss=StackInit(); n=strlen(expr);for(i=1;idataS-top- ;void Push(StackItem x, Stack S)if( StackFull(S) Error(Stack is full); else S-data

4、+ S-top = x; 算 法 与 数 据 结 构 Algorithms and Data Structures(2)栈的数组实现的优缺点优点：所列的7个基本运算都可在O(1)的时间里完成，效率高。缺点：为了使每个栈在算法运行过程中不会溢出，通常要为每个栈预置一个较大的栈空间。另一方面，由于各个栈的实际大小在算法运行过程中不断变化。经常会发生其中一个栈满，而另一个栈空的情形，空间利用率低。2011-9-2910 算 法 与 数 据 结 构 Algorithms and Data Structures(3) 两个栈共用一个数组利用栈底位置不变的特性，可以将2个栈的栈底分别设在数组stack的两

5、端。然后各自向数组stack的中间伸展，如下图所示。好处：提高空间利用率，减少栈发生上溢的可能性。2011-9-2911 算 法 与 数 据 结 构 Algorithms and Data Structures2、链栈用指针实现栈(1)链栈的结点类型定义：2011-9-2912typedef struct snode *slink; typedef struct snode StackItem element; slink next;StackNode; 算 法 与 数 据 结 构 Algorithms and Data Structures2、链栈用指针实现栈(2)用指针实现的链栈定义：20

6、11-9-2913typedef struct lstack *Stack; typedef struct lstackslink top; /栈顶结点指针Lstack; 算 法 与 数 据 结 构 Algorithms and Data Structures(2)入栈、出栈算法实现及演示：入栈算法Push.txttoptop栈底p.出栈算法Pop.txtptop栈底top.2011-9-2914返回章目录 算 法 与 数 据 结 构 Algorithms and Data Structures3.3 栈的应用1、过程的嵌套调用：子过程子过程子过程主程序rst2011-9-2915321rsr

7、rsrtsr 算 法 与 数 据 结 构 Algorithms and Data Structures2、递归过程及其实现：递归：函数直接或间接的调用自身叫递归实现：建立递归工作栈例递归的执行情况分析2011-9-2916运行结果：1，2，2，3，3，3， 算 法 与 数 据 结 构 Algorithms andwData Structuresw递归调用执行情况如下：ww主程序pr(1)pr(2);w=3;pr(w) (1)结束2011-9-2917(2) 输出：3, 3, 3(3) 输出：2, 2返回toptoptoptop(4)0(3)1(3)1(2)2(2)2(2)2(1 )3(1)3(

8、1)3(1)332pr(0);(4)输出：101 算 法 与 数 据 结 构 Algorithms and Data Structures栈的应用算术表达式求值1、算术表达式的定义在计算机中，表达式都是由操作数(operand)、运算符(operator)和界限符(delimiter)组成。只含二元运算符的算术表达式可定义为：表达式:=作数:=作数运算符作数简单变量|表达式常数简单变量:=标识符例1：Exp = 3*5+(6-8/4)*7#2011-9-2919 算 法 与 数 据 结 构 Algorithms and Data Structures栈的应用算术表达式求值2、算术表达式的表示方

9、式假设 Exp = S1OPS2S1 S1OPOP S2S1S2 称为表达式的中缀表示法（简称中缀式）OP 称为表达式的后缀表示法（简称后缀式）S2 称为表达式的前缀表示法（简称前缀式）例2：若Exp= ab+(c-d/e)后缀式为：abcde/-f+前缀式为：+ab-c/def动画演示2011-9-2920 算 法 与 数 据 结 构 Algorithms and Data Structures栈的应用算术表达式求值2011-9-2922 算 法 与 数 据 结 构 Algorithms and Data Structures栈的应用算术表达式求值2011-9-2923 算 法 与 数 据

10、结 构 Algorithms and Data Structures栈的应用算术表达式求值3、后缀表达式求值利用栈进行后缀表达式求值的基本：(1)(2)(3)从左到右读入后缀表达式，若读入的是一个操作数，就将它压入栈；若读入的是一个运算符op，就从栈出两个操作数，设为x和y，计算表达式x op y的值，并将计算结果压入栈；对整个后缀表达式读入结束时，栈顶元素就是计算结果。例4：求后缀表达式 3 56 8 4/-7+#动画演示的值2011-9-2924 算 法 与 数 据 结 构 Algorithms and Data Structures栈的应用算术表达式求值2011-9-2927 算 法 与

11、 数 据 结 构 Algorithms and Data Structures栈的应用算术表达式求值282011-9-29 算 法 与 数 据 结 构 Algorithms and Data Structures4、地图四染色问题7 7 (7)R (3)(4)(2)(1)(6)(5)12345672011-9-2929123 45 673#红色4#蓝色0111110100001010011001010110101101011011000000000 算 法 与 数 据 结 构 Algorithms and Data Structures5、等价类划分问题问题的提出给定集合S及一系列形如“x等价

12、于y”的等价性条件，要求给出S的满足所列等价性条件的等价类划分。其中x和 y是S中的元素。复习:集合上的等价关系和集合关于某一等价关系的等价类划分等概念;举出3个你熟悉的等价关系和等价类划分。2011-9-2930 算 法 与 数 据 结 构 Algorithms and Data Structures(2) 问题的数学化总可以用整数来表示集合中的元素。因此，如果集合S中共有n个元素，则可将集合S表示为，n，而元素i和j的等价性条件可表示为ij，1i，jn。这样，问题可一般地表述为：已知S=，2，n上的个等价性条件itjt, 1it，jtn, t=1,2,3,r一个等价关系由 r来表示。要求该

13、等价关系所确定的等价类划分。2011-9-2931 算 法 与 数 据 结 构 Algorithms and Data Structures(3) 举例给定集合 S =1，2，7，及等价性条件：12， 56，34，14。则集合S的等价类划分如下：首先将S的每一个元素看成一个等价类。然后顺序地处理所给的等价性条件。每处理一个等价性条件，就得到一个相应的等价类划分：12563414，；，；，；，。最终所得到的集合S的等价类划分为：，。2011-9-2932 算 法 与 数 据 结 构 Algorithms and Data Structures6、电路板布线2011-9-2933 算 法 与 数

14、据 结 构 Algorithms a d Data Structures用深度优先搜索的方法解布线问题。从起始位置a开始将它作为第一个搜索方格。依次从与该方格相邻并且可达的方格中选择一个方格成为下一个搜索方格，并将此方格作记后加入到一个栈path中，继续向深度搜索。标一旦不能继续搜索，算法从栈path中取出栈顶方格，搜索其下一个相邻方格。这个过程一直继续到算法搜索到目标方格b或栈为空时为止。2011-9-2934 算 法 与 数 据 结 构 Algorithms a d Data Structuresbool find_path(postart,pofinish)/ 搜索从起点start到终点

15、finish的布线路径/ 找到布线路径则返回true,否则返回falseif(start.row=finish.row)& (start.col=finish.col)return true;/ 无须搜索for(i=0;i=m+1;i+)grid0i=gridm+1i=1;/ 顶部和底部gridi0=gridim+1=1;/和右翼/ 初始化相对位移pooffset4;offset0.row=0;offset0.col=1;/ 右 offset1.row=1;offset1.col=0;/ 下 offset2.row=0;offset2.col=-1;/ 左 offset3.row=-1;off

16、set3.col=0;/ 上2011-9-2935 算 法 与 数 据 结 构 Algorithms ad Data Structurespohere;/ 当前位置here.row=start.row; here.col=start.col; gridhere.rowhere.col=1;/dir=0,dir1=3;/ 开始搜索标记while(here.row!=finish.row | here.col!=finish.col)/ 未达目标/ 找相邻方格r,c; while(dir=dir1)r=here.row+offsetdir.row; c=here.col+offsetdir.col; if(gridrc=0)break; dir+;/ 下一方向2011-9-2936 算 法 与 数 据 结 构 Algorithms ad Data Structures/ 可达相邻方格if(dir=dir1)/ 移至gridrcpath.push(here); here.row=r;here.col=c;gridrc=1;/