第4课--栈结构.ppt

1、2020/8/3,1,第3章 栈结构,教学目的：掌握栈结构的特点,了解栈的应用 教学重点：顺序栈的实现,2020/8/3,2,3.1.1 栈的定义及逻辑特性 栈（stack）是限定仅在表尾进行插入或删除操作的线性表。其中表尾称为栈顶（top），表头则称为栈底（bottom）。 将插入元素的操作称为入栈（push），删除元素的操作称为出栈（pop）。 由于限定插入或删除操作仅在栈顶进行，因此，元素的出栈顺序与入栈顺序相反，最先入栈的元素最后出栈。因此栈又称为后进先出（Last In First Out，简写为LIFO）的线性表.,3.1 栈的定义和基本操作,2020/8/3,3,2020/8/3

2、,4,2栈的基本运算 初始化栈InitStack(S) 设置一个空栈S。 销毁栈 DestroyStack(S); 释放栈s所占的存储空间 入栈Push(S,x) 将元素x插入栈S中，使x成为栈S的栈顶元素。 出栈Pop(S,x) 当栈S不空时，由x返回栈顶元素，并从栈中删除栈顶元素 取栈顶元素GetTop(S,x) 若栈S不空，则由x返回栈顶元素（栈指针不变）。 判栈空Empty(S) 判断栈S是否为空栈。,2020/8/3,5,3.1.2 栈的顺序存储结构及实现 栈结构的实现也可以有两种：顺序结构和链式结构。 由于栈的插入、删除操作限定仅在表尾进行，不需要移动元素，因此，栈结构的实现以顺序

3、结构为主。即利用一组地址连续的存储单元作为栈的存储空间，依次存放自栈底到栈顶的数据元素，同时设两指针分别指示栈顶和栈底的位置。 实际上，顺序栈的实现有两种形式：一种是静态栈，栈空间的大小一经定义不能再改变，可用数组描述；另一种是浮动栈（动态栈），即在初始化时先为栈分配一基本空间，当在应用过程中出现栈空间不足时，再逐渐扩大栈的存储空间。,顺序栈的静态实现： # define StackSize 100 /*栈空间大小 */ /*顺序栈的结构类型定义*/ typedef struct Datatype dataStacksize; /*栈空间 */ int top; /*栈顶“指针” */ Seq

4、Stack; 根据以上定义写出实现基本操作的代码：,约定：top指向新元素要入栈的位置 因此空栈 top=0; /栈底base隐含为0 /初始化空栈: Status InitStack(SeqStack ,/入栈：将元素e插入栈S中 Status Push(SeqStack s,Datatype e) if (s.top=StackSize) /栈满 return(StackOverflow); s.datas.top+=e; return (ok); ,约定：top指向新元素要入栈的位置,/出栈: 当栈S不空时，由x返回栈顶元素 Status Pop(SeqStack s,Datatype

5、,约定：top指向新元素要入栈的位置,/返回栈顶元素的值，栈指针不改变 Status GetTop(SeqStack s,Datatype ,约定：top指向新元素要入栈的位置,2020/8/3,11,所谓动态栈是指先分配一个基本的栈空间，运行中栈空间满时再追加存储空间。因此动态栈的实现需要动态存储分配函数支持 具有动态特点的顺序栈定义如下： # define StackInitSize 100 /* 初始栈空间 */ # define Increment 10/* 存储分配增量值 */ /*栈的结构类型定义*/ typedef struct Datatype *base;/* 栈空间的首地址

6、（基址） */ Datatype *top;/* 栈顶指针 */ int stacksize;/* 当前实际栈空间 */ SqStack;,3.1.2 顺序栈的动态结构,2020/8/3,12,顺序栈示意图图3.2,注意栈指针的约定：栈顶指针Top指向的是新元素将存放的位置； 所以入栈操作是：先存放元素，再移动栈顶指针。, c b a,空栈,a,b,c顺序入栈后,c, b 顺序出栈后,判断栈空的条件：s.top=s.base 判断栈满的条件：s.top-s.base=s.stacksize,2020/8/3,13,算法3.1 动态顺序栈初始化 status InitStack (SqStack

7、 *s) /* 初始化栈空间，成功返回1否则返回0 */ s-base=(Datatype *)malloc(StackInitSize *sizeof(Datatype); if ( s-base=null ) return (overflow); /* 内存空间不足 */ s-top=s-base; s-stacksize=StackInitSize; return (ok); Initstack函数的调用方法: SqStack s; /*声明一个栈结构的变量s*/ Status Result; Result=InitStack( /*调用初始化函数*/,3.1.2 顺序栈的操作实现,20

8、20/8/3,14,算法3.2 入栈操作 status push (SqStack s, Datatype e) /* 将元素e入栈，操作成功返回ok, 否则返回error */ Datatype *p=.base; if (s.top-s.base=s.stacksize) /* 栈满,重新分配栈空间 */ p=(Datatype*)realloc(s-base,(s-stacksize+increment)*sizeof(Datatype); if (!p) return (error); /* 栈空间分配失败 */ s-base=p; /* 栈空间分配成功，修改栈底指针 */ s-top

9、=p+s-StackSize; /*修改栈顶指针 */ s-stacksize +=Increment; /* 修改栈空间值*/ *s-top+=e; /*元素e入栈,并修改栈顶指针*/ return (ok); *s-top+=e; 等价于: *(s-top)=e; (s-top)+; 这里运算符“-”的优先级最高；其次是 * ；最后是+,2020/8/3,15,算法3.3销毁栈操作 status DestroyStack (SqStack *s) /* 释放栈s的空间 */ if (s) /*栈指针有效*/ free (s-base) ; /*先释放栈s所分配的空间*/ free (s)

10、; /*释放变量s所占的空间-黄色部分*/ return (ok); else return (error); , c b a,s,2020/8/3,16,算法3.4 出栈操作 Status Pop(SqStack *s,Datatype *e) /* 将栈顶元素出栈,由变量e返回 若成功返回ok，否则返回error */ if (s-top=s-base) printf(“stack_empty”); return(error); *e=*(-s-top); /*先修改top指针，然后返回栈顶元素*/ return (ok); s-top-; *e=*(s-top); /*先修改top指针，

11、然后返回栈顶元素*/,2020/8/3,17,算法3.5 取栈顶元素 Status GetTop(SqStack *s,Datatype *e) /* 取栈顶元素由变量e返回,但不改变栈指针top */ Datatype *p=s-top; if (p=S-base) return (error); *e=*(-p); return (ok); ,2020/8/3,18,3.1.3 栈的链式存储结构 栈的链式实现是以链表作为栈的存储结构，并在这种存储结构上实现栈的基本运算。栈的链式实现称为链式栈。 栈的操作将用链表的操作实现。,链栈结构示意图,2020/8/3,19,讨论：多个栈共用存储空间问

12、题 1.现以顺序存储结构实现一个双向栈：用一维数组的存储空间实现两个栈，它们的栈顶相对，栈底分别在数组的两个端点。试设计该双向栈的类型定义，并编写以下三个基本操作算法： （1）初始化InitStack(tws)； （2）入栈操作Push(tws,i,e)； （3）出栈操作Pop(tws,i,*e)； 其中变量i为标志，指示对两个栈中的哪个进行操作。（例可用i=0表示正向栈，i=1表示逆向栈）,2020/8/3,20,讨论：多个栈共用存储空间问题 提示：为简化操作，用数组描述（静态栈，栈空间的大小不能再改变） 则可省略栈的base指针。 双向栈类型定义Tws #define MaxSize 10

13、00 /*双向栈的最大空间*/ typedef struct Datatype elemMaxSize; /*栈空间*/ int top1,base1; /*正向栈指针*/ int top2,base2; /*逆向栈指针*/ Tws; /*双向栈类型*/ 在一个数组空间中实现两个栈，从两端向中间增长： 正向栈：入栈时 s.elemtop+=e; 出栈时 e=s.elem-top; 逆向栈：入栈时 s.elemtop-=e; 出栈时 e=s.elem+top;,base1 top1 base2 top2,0 1 2 3 997 998 999,2020/8/3,21,作业：2个栈共用存储空间问题

14、 用长为n的一块内存实现双向栈：栈底分别在两端，栈顶相对，从而每个栈的大小可以n/2，具有1+12的效果。,/*初始化算法*/ /约定：栈顶指针top指向新元素入栈的位置 Void InitStack(Tws *s) s-top1=s-base1=0; s-top2=s-base2=Maxsize-1; ,/入栈 status Push(tws ,/出栈，先判出哪个栈 status Pop(tws ,2020/8/3,24,教学目的：学会使用栈结构解决问题， 初步掌握递归程序设计方法 教学重点：栈的应用 教学难点：利用栈实现表达式求值 递归算法,3.2 栈的应用,2020/8/3,25,本课内

15、容,一、栈的典型应用 1.表达式括号匹配问题 2.表达式求值问题 二、典型递归算法 汉诺塔问题求解,2020/8/3,26,解决问题思路： 假设表达式中允许出现两类括号：( )、 ，且嵌套的顺序随意，例：( )( )，则检验括号是否匹配的算法是： 依次扫描表达式中的字符，遇到左括号就进栈； 遇到右括号则与栈顶元素比较，若匹配则栈顶元素出栈，否则说明出现错误，可指出错误位置及括号并停止扫描； 重复以上过程，直到表达式处理完，若表达式语法正确，则栈应该和初始状态相同，否则一定是表达式中的括号不匹配。 注意：当前需要匹配的左括号总是处在栈顶。,3.2.1 栈的应用括号匹配问题,2020/8/3,27

16、,处理表达式的基本步骤： （1）首先初始化字符栈s为空栈。 （2）依次读入表达式字符，当表达式未结束时重复以下步骤： 遇左括号“( ”或“”则进栈；并继续读下一个字符; 遇其它字符，则跳过； 遇右括号“)”或“”，与栈顶字符比较，看是否匹配（即同为方括号或同为圆括号），相符则栈顶字符出栈并继续读下一个字符； 若栈为空则显示错误并提前结束扫描。（错误信息：少左括号） （3）表达式处理结束后，判栈s是否为空栈： 若是，表示括号匹配成功； 否则表明表达式中括号不匹配。 （错误信息：少右括号）,3.2.1 括号匹配问题,2020/8/3,28,表达式括号匹配的程序实现,一、首先定义字符栈 #defin

17、e maxsize 255 /*最大栈空间*/ typedef struct char *top; /*栈指针*/ char datamaxsize; Stack; /*并声明以下基本操作*/ void InitStack(Stack *s); /*初始化*/ void Push(Stack *s,char e); /*入栈*/ int Pop(Stack *s,char *e); /*出栈*/ char GetTop(Stack *s); /*取栈顶元素*/,2020/8/3,29,主程序如下：,main() char expmaxsize+1; char ch; int error=0,i

18、; /*error为是否出错标记,为1表示括号不匹配*/ Stack s; /*初始化字符栈*/ InitStack(,2020/8/3,30,while (expi!=#) /*表达式为结束*/ swith (expi) case (: /*左括号入栈*/ case : Push( ,2020/8/3,31,/*实现栈的基本操作*/ void InitStack(Stack *s) /*初始化*/ s-top=s-data; void Push(Stack *s,char e) /*入栈*/ *(s-top)=e; s-top+; int Pop(Stack *s,char *e) /*出栈

19、,需要判断栈空否*/ if (s-top=s-data) return (0); else s-top-; *e=*(s-top); return (1); char GetTop(Stack *s) /*取栈顶元素,不成功返回空字符*/ ,2020/8/3,32,1.表达式运算规则分析 假定四则运算表达式中允许出现的运算符有 +、-、*、/、( )，且基本的运算规则是： (1) 先做括号内的运算，即括号的优先级最高； (2) 先乘除、后加减，即 */ 运算高于+、- 运算； (3) 相同级别的运算（同为加减类或乘除类）按从左向右规则进行。,3.2.2 栈的应用表达式求值问题,2020/8/3

20、,33,根据以上运算规则，对表达式进行扫描，遇到一个运算符1时，并不能确定马上就执行计算，需向右扫描到下个运算符2，通过比较它们之间的优先关系，才能决定如何操作。1和2的优先关系只有以下三种： 1）12：2优先级低于1，此时应执行1规定的运算； 2）12：2优先级等于1，此时也应执行1规定的运算； 3）12：2优先级高于1，此时不能执行任何运算，需继续扫描下一运算符。 前两种情况可统一处理，而最后一种情况则需要将尚不能处理的运算符保存起来，待读入下一个运算符后再用以上规则处理。而栈结构的后进先出特点正好可以用于保存未处理的运算符。,3.2.2 栈的应用表达式求值问题,2020/8/3,34,实

21、现运算符优先法需要使用两个栈： 一个运算符栈 OPR，用于存放暂时不能处理的运算符； 一个运算数栈OPD，用于存放运算数和中间结果。 为了使程序能按照优先级对表达式自动求值，我们可为每个运算符定义一个优先数，以反映他们之间的优先关系。（见表3.1) 首先，为了使相同级别的运算1、2能够按从左向右的顺序进行，人为地使12；其次，增设一个表达式界限符“#”，规定其优先级低于所有的运算符和括号 ，以便于程序统一处理。,3.2.2 栈的应用表达式求值问题,2020/8/3,35,“运算符优先法” ： 1.初始化运算数栈OPD和运算符栈OPR，并将界限符“#”压入运算符栈。 2.依次读入表达式中的每一项

22、，是运算数则入运算数栈OPD，是运算符则与OPR栈顶元素比较优先级，并根据以下情况分别处理： (1) 高于栈顶，则当前运算符入栈； (2) 低于栈顶，则OPR出栈-op，且OPD栈弹出两个操作数a、b，执行“a op b”规定的运算，并将运算结果压入运算数栈OPD； (3) 优先级相同，说明是左右括号相遇或两个“#”相遇，将栈顶元素出栈。 重复2的操作，当运算符栈为空时则表达式求值结束，此时求值结果在运算数栈中。,3.3.2 栈的应用表达式求值问题,2020/8/3,36,常量表达式5+12/3- (7-2)*3的求值过程。,2020/8/3,37,递归是一种非常重要的数学概念和解决问题的方法

23、，在计算机科学和数学等领域有着广泛的应用。在计算机科学中，许多数据结构，如广义表、树和二叉树等，由于其自身固有的递归性质，都可通过递归方式加以定义并实现许多其算法设计。而递归算法的实现是以栈结构为基础的，所以递归是栈的一个实际应用。 递归的定义：如果在描述一个事物时又使用了该事物自身，就称为递归。 递归函数：一个函数直接或间接地调用了自己，则称为递归函数。,3.3 栈与递归,2020/8/3,38,采用递归算法求解正整数n的阶乘n! 数学定义,求n的阶乘的递归函数算法如下: long fact(int n) long f; R1: if (n=0) f=1; /*递归终止条件*/ R2: el

24、se f=n*fact(n-1); /*递归调用*/ R3: return f; ,2020/8/3,39,进行fact(4)调用的系统栈的变化情况 需要入栈的包括：参数n、返回地址,4, r3,3, r3 4, r3,2, r3 3, r3 4, r3,1, r3 2, r3 3, r3 4, r3,1, r3 2, r3 3, r3 4, r3,fect(4) fect(3) fect(2) fect(1) fect(0) 1出栈 2出栈 3出栈 4出栈后 执行f=1 执行1*1 执行2*1 执行3*2 执行4*6 返回1 返回1 返回2 返回6 返回24,2, r3 3, r3 4, r3,3, r3 4, r3,4, r3,2020/8/3,40,函数fact(4)的递归调用过程的执行流程,f,=,4,*,fact,(,3,),;,n,:,4,return 24,f,=,3,*,fact,(,2,),;,n,:,3,return 6,;,f,=,2,*,fact,(,1,),;,n,:,2,return 2,;,f,=,1,*,fac