栈和上机作业PPT学习教案

1、会计学1 栈和上机作业栈和上机作业 栈栈是一种只能在一端进行插入或删除操是一种只能在一端进行插入或删除操 作的线性表。作的线性表。 表中允许进行插入、删除操作的一端称表中允许进行插入、删除操作的一端称 为为栈顶栈顶。 栈顶的当前位置是动态的栈顶的当前位置是动态的,栈顶的当前位栈顶的当前位 置由一个称为栈顶指针的位置指示器指示。置由一个称为栈顶指针的位置指示器指示。 表的另一端称为表的另一端称为栈底栈底。 当栈中没有数据元素时当栈中没有数据元素时,称为称为空栈空栈。 栈的插入操作通常称为栈的插入操作通常称为进栈进栈或或入栈入栈,栈的栈的 删除操作通常称为删除操作通常称为退栈退栈或或出栈出栈。 3

2、.1.1 栈的定义栈的定义 第1页/共52页 图图3-1 顺序栈示意图顺序栈示意图 a1 a2 ai an bottom top 进栈（进栈（push）出栈出栈(pop) 第2页/共52页 顺序栈进栈和出栈示意图顺序栈进栈和出栈示意图 第3页/共52页 栈的几种基本运算如下栈的几种基本运算如下: (1) 初始化栈初始化栈InitStack( s-top=-1; 第7页/共52页 顺序栈进栈和出栈示意图顺序栈进栈和出栈示意图 第8页/共52页 (2) 销毁栈销毁栈ClearStack( 第9页/共52页 (3) 求栈的长度求栈的长度StackLength(s) 返回栈返回栈s中的元素个数中的元素

3、个数,即栈指针加即栈指针加1的的 结果。对应算法如下结果。对应算法如下: int StackLength(SqStack *s) return(s-top+1); 第10页/共52页 (4) 判断栈是否为空判断栈是否为空StackEmpty(s) 栈栈S为空的条件是为空的条件是s-top=-1。对应。对应 算法如下算法如下: int StackEmpty(SqStack *s) return(s-top=-1); 第11页/共52页 (5) 进栈进栈Push( /*栈满的情况栈满的情况,即栈上溢出即栈上溢出*/ s-top+; s-datas-top=e; return 1; 第12页/共52

4、页 (6) 出栈出栈Pop( /*栈为空的情况栈为空的情况,即栈下溢出即栈下溢出 */ e=s-datas-top; s-top-; return 1; 第13页/共52页 (7) 取栈顶元素取栈顶元素GetTop(s) 在栈不为空的条件下在栈不为空的条件下,将栈顶元素赋给将栈顶元素赋给 e。对应算法如下。对应算法如下: int GetTop(SqStack *s,ElemType /*栈为空的情况栈为空的情况,即栈下溢出即栈下溢出*/ e=s-datas-top; return 1; 第14页/共52页 (8) 显示栈中元素显示栈中元素DispStack(s) 从栈顶到栈底顺序显示栈中所有元

5、素从栈顶到栈底顺序显示栈中所有元素 。对应算法如下。对应算法如下: void DispStack(SqStack *s) int i; for(i=s-top;i=0;i-) printf(%c ,s-datai); printf(n); 第15页/共52页 Return(1); Return(1); 第16页/共52页 3.1.3 栈的链式存储结构及其基本运算的栈的链式存储结构及其基本运算的 实现实现 采用链式存储的栈称为链栈采用链式存储的栈称为链栈,这里采用这里采用 单链表实现。单链表实现。 链栈的优点是不存在栈满上溢的情况链栈的优点是不存在栈满上溢的情况 。我们规定栈的所有操作都是在单链

6、表的。我们规定栈的所有操作都是在单链表的 表头进行的表头进行的,下图是头结点为下图是头结点为*lhead的链的链 栈栈,第一个数据结点是栈顶结点第一个数据结点是栈顶结点,最后一个最后一个 结点是栈底结点。栈中元素自栈顶到栈底结点是栈底结点。栈中元素自栈顶到栈底 依次是依次是a1、a2、an。 第17页/共52页 链栈示意图链栈示意图 第18页/共52页 链栈中数据结点的类型链栈中数据结点的类型LiStack定义定义 如下如下: typedef struct linknode ElemType data; /*数据域数据域*/ struct linknode *next; /*指针域指针域*/

7、LiStack; 第19页/共52页 在链栈中在链栈中,栈的基本运算算法如下栈的基本运算算法如下: (1) 初始化栈初始化栈initStack( s-next=NULL; s 第20页/共52页 (2) 销毁栈销毁栈ClearStack(*q=s-next; while (q!=NULL) free(p); p=q; q=p-next; free(p); 第21页/共52页 (3) 求栈的长度求栈的长度StackLength(s) 从第一个数据结点开始扫描单链表从第一个数据结点开始扫描单链表,用用 n记录访问的数据结点个数记录访问的数据结点个数,最后返回最后返回n值值 。对应算法如下。对应算法

8、如下: int StackLength(LiStack *s) int n=0; LiStack *p; p=s-next; while(p!=NULL) n+;p=p-next; return(n); 第22页/共52页 (4) 判断栈是否为空判断栈是否为空StackEmpty(s) 栈栈S为空的条件是为空的条件是s-next=NULL,即即 单链表中没有数据结点。对应算法如下单链表中没有数据结点。对应算法如下: int StackEmpty(LiStack *s) return(s-next=NULL); s 第23页/共52页 (5) 进栈进栈Push( p=(LiStack *)mal

9、loc(sizeof(LiStack); p-data=e; p-next=s-next; /*插入插入*p结点作为第一个数据结点结点作为第一个数据结点*/ s-next=p; 第24页/共52页 (6) 出栈出栈Pop( if (s-next=NULL) return 0; /*栈空的情况栈空的情况*/ p=s-next; /*p指向第一个数据结点指向第一个数据结点*/ e=p-data; s-next=p-next; free(p); return 1; 第25页/共52页 (7) 取栈顶元素取栈顶元素GetTop(s) 在栈不为空的条件下在栈不为空的条件下,将头结点后继数将头结点后继数

10、据结点的数据域赋给据结点的数据域赋给e。对应算法如下。对应算法如下: int GetTop(LiStack *s,ElemType /*栈空的情况栈空的情况*/ e=s-next-data; return 1; 第26页/共52页 (8) 显示栈中元素显示栈中元素DispStack(s) 从第一个数据结点开始扫描单链表从第一个数据结点开始扫描单链表,并输出并输出 当前访问结点的数据域值。对应算法如下当前访问结点的数据域值。对应算法如下: void DispStack(LiStack *s) LiStack *p=s-next; while (p!=NULL) printf(%c ,p-data

11、); p=p-next; printf(n); 第27页/共52页 第28页/共52页 3.1.4 栈的应用例子栈的应用例子 1. 表达式求值表达式求值 这里限定的表达式求值问题是这里限定的表达式求值问题是:用户输用户输 入一个包含入一个包含“+”、“-”、“*”、“/”、 正整数和圆括号的合法数学表达式正整数和圆括号的合法数学表达式,计算计算 该表达式的运算结果。该表达式的运算结果。 第29页/共52页 在程序语言中在程序语言中,运算符位于两个操作数运算符位于两个操作数 中间的表达式称为中缀表达式。例如：中间的表达式称为中缀表达式。例如： 1+2*3 就是一个中缀表达式就是一个中缀表达式,中

12、缀表达式是最中缀表达式是最 常用的一种表达式方式。对中缀表达式常用的一种表达式方式。对中缀表达式 的运算一般遵循的运算一般遵循“先乘除先乘除,后加减后加减,从左从左 到右计算到右计算,先括号内先括号内,后括号外后括号外”的规则的规则 。因此。因此,中缀表达式不仅要依赖运算符优中缀表达式不仅要依赖运算符优 先级先级,而且还要处理括号。而且还要处理括号。 第30页/共52页 所谓所谓后缀表达式后缀表达式,就是运算符在操作数的后就是运算符在操作数的后 面面,如如1+2*3的后缀表达式为的后缀表达式为123*+。在后缀表。在后缀表 达式中已考虑了运算符的优先级达式中已考虑了运算符的优先级,没有括号没有

13、括号,只只 有操作数和运算符。有操作数和运算符。 对后缀表达式求值过程是对后缀表达式求值过程是:从左到右读入后从左到右读入后 缀表达式缀表达式,若读入的是一个操作数若读入的是一个操作数,就将它入数就将它入数 值栈值栈,若读入的是一个运算符若读入的是一个运算符op,就从数值栈中就从数值栈中 连续出栈两个元素连续出栈两个元素(两个操作数两个操作数),假设为假设为x和和y, 计算计算x op y之值之值,并将计算结果入数值栈；对并将计算结果入数值栈；对 整个后缀表达式读入结束时整个后缀表达式读入结束时,栈顶元素就是计栈顶元素就是计 算结果。算结果。 第31页/共52页 算术表达式求值过程是算术表达式

14、求值过程是:先将算术表达式转先将算术表达式转 换成后缀表达式换成后缀表达式,然后对该后缀表达式求值。然后对该后缀表达式求值。 假设算术表达式中的符号以字符形式由键盘假设算术表达式中的符号以字符形式由键盘 输入输入,并存放在字符型数组并存放在字符型数组exp中中,其后缀表达式其后缀表达式 存放在字符型数组存放在字符型数组postexp中中.在将算术表达式在将算术表达式 转换成后缀表达式的过程中用一个字符型数组转换成后缀表达式的过程中用一个字符型数组 op作为栈。将算术表达式转换成后缀表示的方作为栈。将算术表达式转换成后缀表示的方 法如下法如下: 第32页/共52页 while (从从exp读取字

15、符读取字符ch,ch!=0) 若若ch为为数字数字,将后续的所有数字均依次存放到将后续的所有数字均依次存放到 postexp中中,并以字符并以字符“#”标志数值串结束。标志数值串结束。 若若ch为左括号为左括号“(”,则将此括号进栈到运算符则将此括号进栈到运算符 栈栈op中。中。 若若ch为右括号为右括号“ “)”,则将运算符栈则将运算符栈op中左括号中左括号 “(”以前的运算符依次出栈并存放到以前的运算符依次出栈并存放到postexp中中 ,然后将左括号然后将左括号“(”删除。删除。 若若ch运算符优先级小于或等于运算符优先级小于或等于op栈顶运算符 栈顶运算符 的优先级的优先级(除栈顶运算

16、符为除栈顶运算符为“(”外外),则依次出栈并则依次出栈并 存入到存入到postexp中中,然后将然后将ch进栈。进栈。 中缀表达式中缀表达式后缀后缀表达式表达式 第33页/共52页 若字符串若字符串exp扫描完毕扫描完毕,则将运算则将运算 栈栈op中的所有运算符依次出栈并存中的所有运算符依次出栈并存 放到放到postexp中。最后得到后缀表达中。最后得到后缀表达 式式postexp。 第34页/共52页 对于表达式对于表达式“(56-20)/(4+2)”,其转换成后缀表达其转换成后缀表达 式的过程式的过程 如下如下： expexp操作过程操作过程opoppostexppostexp (56-2

17、0)/(4+2)(56-20)/(4+2)遇到遇到chch为为“(”,(”,将此括号将此括号 进栈进栈opop。 ( ( 56-20)/(4+2)56-20)/(4+2) 遇到遇到chch为数字为数字, ,将将5656存入存入 postexppostexp中中, ,并插入一个字并插入一个字 符符“#”#”。 ( (56#56# -20)/(4+2)-20)/(4+2)遇到遇到chch为为“-”,-”,由于由于opop中中 “(”(”以前没有字符以前没有字符, ,则直则直 接将接将chch进栈进栈opop中。中。 (-(-56#56# 20)/(4+2)20)/(4+2)遇到遇到chch为数字为

18、数字, ,将将20#20#存入存入 数组数组expexp中。中。 (-(-56#20#56#20# 第35页/共52页 expexp操作过程操作过程opop postexppostexp )/(4+2)/(4+2) 遇到遇到chch为为“)”,)”,则将栈则将栈 opop中中“(”(”以前的字符依以前的字符依 次出栈并存入次出栈并存入postexppostexp中中, , 然后将然后将“(”(”删除。删除。 56#20#-56#20#- /(4+2)/(4+2)遇到遇到chch为为“/”,/”,将将将将chch 进栈进栈opop中。中。 / /56#20#-56#20#- (4+2)(4+2)

19、遇到遇到chch为为“(”,(”,将此括将此括 号进栈号进栈opop中。中。 /(/(56#20#-56#20#- 4+2)4+2)遇到遇到chch为数字为数字, ,将将4#4#存入存入 数组数组postexppostexp中。中。 /(/(56#20#-56#20#- 4#4# 第36页/共52页 expexp操作过程操作过程opoppostexppostexp +2)+2)遇到遇到chch为为“+”,+”,由于由于opop栈顶栈顶 运算符为运算符为“(”,(”,则直接将则直接将chch 进栈进栈opop中。中。 /(+/(+ 56#20#-56#20#- 4#4# 2)2)遇到遇到chch

20、为数字为数字, ,将将2#2#存入存入 postexppostexp中。中。 /(+/(+ 56#20#-56#20#- 4#2#4#2# ) )遇到遇到chch为为“)”,)”,则将栈则将栈opop中中 “(”(”以前的字符依次出栈以前的字符依次出栈 并存放到并存放到postexppostexp中中, ,然后将然后将 “(”(”出栈。出栈。 / /56#20#-56#20#- 4#2#+4#2#+ expexp扫描完毕扫描完毕, ,则将栈则将栈opop中的中的 所有运算符依次弹出并存放到所有运算符依次弹出并存放到 postexppostexp中中, ,得到后缀表达式。得到后缀表达式。 56#20#-56#20#- 4#2#+/4#2#+/ 第37页/共52页 将算术表达式将算术表达式exp转换成后缀表达式转换成后缀表达式postexp void trans(char exp, char postexp) struct char dataMaxSize;/*存放运算符存放运算符*/ int top;/*栈指针栈指针*/ op;/*定义运算符栈定义运算符栈*/ char ch; int i=0,t=0;/*i作为作为exp的下标的