《数据结构 第3章 栈.ppt》由会员分享，可在线阅读，更多相关《数据结构 第3章 栈.ppt（45页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、实用数据结构基础实用数据结构基础第第3 3章章 栈栈第 3 3 章 栈 知识点栈的定义和特点栈的定义和特点栈的基本运算和算法栈的基本运算和算法栈的典型应用栈的典型应用难难点点后缀表达式的算法后缀表达式的算法数制的换算数制的换算利用本章的基本知识设计相关的应用问题利用本章的基本知识设计相关的应用问题要求掌握栈的特点掌握栈的特点掌握栈的基本运算掌握栈的基本运算熟悉栈的各种实际应用熟悉栈的各种实际应用能设计栈应用的典型算法能设计栈应用的典型算法了解栈的运算时间复杂度分析了解栈的运算时间复杂度分析第3 3章 目录3-1栈的定义与运算栈的定义与运算3-2栈的存储和实现栈的存储和实现3-3栈的应用举例栈的
2、应用举例小小结结验证性实验验证性实验3:栈子系统栈子系统自主设计实验自主设计实验3：后缀表达式求值：后缀表达式求值单元练习单元练习33-1 栈的定义和运算3-1-1栈（栈（Stack）的定义的定义1.栈的定义栈的定义栈是限制在表尾进行插入和删除的线性表。栈是限制在表尾进行插入和删除的线性表。a1a2a3an进栈进栈出栈出栈图图3-1栈的栈的示意图示意图2.栈的特性栈的特性（1）栈的主要特点是）栈的主要特点是“后进先出后进先出”（2）允允许许插插入入、删删除除的的这这一一端端称称为为栈栈顶顶（Top），另另一一端端称为栈底（称为栈底（Bottom）。）。3.应用实例应用实例（1）分币筒）分币筒（
3、2）铁路调度站）铁路调度站3-1-2栈的运算栈的运算1进栈：进栈：Push（&s，x）初始条件：栈初始条件：栈s已存在且非满。已存在且非满。操操作作结结果果：在在栈栈顶顶插插入入一一个个元元素素x，栈栈中中多多了了一个元素。一个元素。2出栈：出栈：Pop（&s）初始条件：栈初始条件：栈s存在且非空。存在且非空。操作结果：删除栈顶元素，栈中少了一个元素。操作结果：删除栈顶元素，栈中少了一个元素。3读栈顶元素：读栈顶元素：ReadTop（s，&e）初始条件：栈初始条件：栈s已存在且非空。已存在且非空。操作结果：输出栈顶元素，但栈中元素不变。操作结果：输出栈顶元素，但栈中元素不变。4.判栈空判栈空：
4、SEmpty（s）初始条件：栈初始条件：栈s已存在。已存在。操作结果：若栈空则返回为操作结果：若栈空则返回为0，否则返回为，否则返回为1。5.判栈满：判栈满：SFull（s）初始条件：栈初始条件：栈s已存在。已存在。操作结果：若栈满则返回为操作结果：若栈满则返回为0，否则返回为，否则返回为1。6.显示栈元素：显示栈元素：ShowStack(s)初始条件：栈初始条件：栈s已存在已存在，且非空。，且非空。操作结果：显示栈中所有元素。操作结果：显示栈中所有元素。3-2栈的存储和实现3-2-1顺序栈顺序栈1顺序栈的实现顺序栈的实现（1）用一维数组实现顺序栈用一维数组实现顺序栈设设栈栈中中的的数数据据元
5、元素素的的类类型型是是字字符符型型，用用一一个个足足够够长长度度的的一一维维数数组组s来来存存放放元元素素，数数组组的的最最大大容容量量为为MAXLEN，栈顶指针为栈顶指针为top，则顺序栈可以用则顺序栈可以用C（或或C+）语言描述：语言描述：#defineMAXLEN10/分配最大的栈空间分配最大的栈空间charsMAXLEN；/数据类型为字符型数据类型为字符型inttop；/定义栈顶指针定义栈顶指针（2）用结构体数组实现顺序栈用结构体数组实现顺序栈顺序栈的结构体描述顺序栈的结构体描述：#defineMAXLEN10/分配最大的栈空间分配最大的栈空间typedefstruct/定义结构体定义
6、结构体datatypedataMAXLEN;/datatype可根据用需要定义类型可根据用需要定义类型inttop；/定义栈顶指针定义栈顶指针SeqStack；再定义一个指向顺序栈的指针再定义一个指向顺序栈的指针：SeqStack*S；/定义定义S为结构体类型的指针变量为结构体类型的指针变量（3）栈操作的示意图如图）栈操作的示意图如图3-3所示所示。AFEDCBAFEDCBAJIHGFEDCBAtop=-1top=0top=5top=3top=9(a)(b)(c)(d)(e)当当top=-1时，表示栈空，如图时，表示栈空，如图3-3（a）；）；当当top=0时时，表表示示栈栈中中有有一一个个元
7、元素素，如如图图3-3（b）表表示示栈中已输入一个元素栈中已输入一个元素A；入入栈栈时时，栈栈顶顶指指针针上上移移，指指针针top加加1，如如图图3-3（c）是是6个元素入栈后的状况个元素入栈后的状况；出出栈栈时时，栈栈顶顶指指针针下下移移，指指针针top减减1，如如图图3-3（d）是是在在F、E相相继继出出栈栈后后的的情情况况。此此时时栈栈中中还还有有A、B、C、D4个个元元素素，top=3，指指针针已已经经指指向向了了新新的的栈栈顶顶。但但是是出出栈栈的的元元素素F、E仍仍然然在在原原先先的的存存储储单单元元，只只是是不不在在栈栈中中了了，因因为为栈栈是是只只能能在栈顶进行操作的线性表。在
8、栈顶进行操作的线性表。当当top=9时时，即即top=MAXLEN1，表表示示栈栈满满，如如图图3-3（e）。）。2顺序栈运算的基本算法顺序栈运算的基本算法（1）置空栈）置空栈首先建立栈空间首先建立栈空间，然后初始化栈顶指针。，然后初始化栈顶指针。SeqStack*Snull()SeqStack*s；s=new(SeqStack)；/在在C语言中用语言中用s=malloc（sizeof（SeqStack）；s-top=1；/置栈空置栈空returns；（2）进栈进栈进栈运算是在栈顶位置插入一个新元素进栈运算是在栈顶位置插入一个新元素x，其算法步骤为：其算法步骤为：(a)判判栈栈是是否否为为满满
9、，若若栈栈满满，作作溢溢出出处处理理，并并返返回回0；(b)若栈未满，栈顶指针若栈未满，栈顶指针top加加1；(c)将新元素将新元素x送入栈顶，并返回送入栈顶，并返回1。intPush(SeqStack*s，datatypex)if（s-top=MAXLEN1）return0；/栈栈满满不不能能入入栈栈，且且返返回回0elses-top+；s-datas-top=x；/栈不满，则压入元素栈不满，则压入元素xreturn1；/进栈成功，返回进栈成功，返回1（3）出栈）出栈出出栈栈运运算算是是指指取取出出栈栈顶顶元元素素，赋赋给给某某一一个个指指定定变变量量x，其算法步骤为：其算法步骤为：(a)判
10、栈是否为空，若栈空，作下溢处理，并返回判栈是否为空，若栈空，作下溢处理，并返回0；(b)若栈非空，将栈顶元素赋给变量若栈非空，将栈顶元素赋给变量x；(c)指针指针top减减1，并返回，并返回1。intPop（SeqStack*s，datatype*x）if(SEmpty(s)return0；/若栈空不能出栈若栈空不能出栈，且返回，且返回0else*x=s-datas-top；/先出栈，数据存入先出栈，数据存入*xs-top-；/后修改指针后修改指针return1；/出栈成功，返回出栈成功，返回1（4）读栈顶元素）读栈顶元素datatypeReadTop（SeqStack*s）if(SEmpty
11、(s)return0；/若栈空，则返回若栈空，则返回0elsereturn(s-datas-top)；/读栈顶元素，但指针未动读栈顶元素，但指针未动（5）判栈空）判栈空intSEmpty（SeqStack*s）if（s-top=1）return1；/若栈空，则返回若栈空，则返回1elsereturn0；/否则返回否则返回0（6）判栈满）判栈满intSFull（SeqStack*s）if（s-top=MAXLEN1）return1；/若栈满，则返回若栈满，则返回1elsereturn0；/否则返回否则返回03-2-2链栈链栈1链栈的链栈的实现实现用用链链式式存存储储结结构构实实现现的的栈栈称称为
12、为链链栈栈。因因为为链链栈栈的的结结点点结结构构与与单单链链表表的的结结构构相相同同，通通常常就就用用单单链链表表来来实实现现，在在此此用用LinkStack表示表示，即有：，即有：typedefstructstacknode/栈的栈的存储存储结构结构datatypedata;/定义数据类型定义数据类型 structstacknode*next;/定义一个定义一个结构体的链结构体的链指针指针stacknode，*Linkstack；Linkstacktop；/top/top为栈顶为栈顶指针指针由由于于栈栈的的操操作作只只能能在在栈栈顶顶进进行行的的，所所以以用用链链表表的的头头部部做做栈顶是最
13、栈顶是最合适合适的。链栈结构如图的。链栈结构如图3-4所示所示。图图3-4链栈链栈示意图示意图top43212链栈链栈基本操作基本操作：（1）入栈）入栈voidPush(linkstack*s,intx)stacknode*p=newstacknode;p-data=x;p-next=s-top;s-top=p;top3214top（2）出栈出栈intPop(linkstack*s)intx;/定义一个变量定义一个变量x x，用以存放用以存放出栈的出栈的元素元素stacknode*p=s-top;/栈顶栈顶指针指向指针指向p p x=p-data;/栈顶栈顶元素元素送送x xs-top=p-n
14、ext;/修改修改栈顶栈顶指针指针deletep;/回收回收结点结点p preturnx;/返回返回栈顶栈顶元素元素（3）显示显示voidShowStack(linkstack*s)stacknode*p=s-top;if(p=NULL)/若栈空，作若栈空，作“栈空栈空”显示显示printf(栈为空栈为空);elseprintf(栈栈元素元素为：为：);while(p!=NULL)/栈非空，则显示栈中所有栈非空，则显示栈中所有元素元素printf(%6d,p-data);/输出一个元素输出一个元素p=p-next;/修改修改栈顶栈顶指针指针printf(n);3-3.栈的应用举例3-3-1数制
15、转换数制转换数数值值进进位位制制的的换换算算是是计计算算机机实实现现计计算算和和处处理理的的基基本本问问题题。比比如如将将十十进进制制数数N转转换换为为j进进制制的的数数，其其解解决决的的方方法法很很多多，其其中中一一个个常常用用的的算算法法是是除除j取取余余法法。将将十十进进制制数数每每次次除除以以j，所所得得的的余余数数依依次次入入栈栈，然然后后按按“后进先出后进先出”的次序出栈便得到转换的结果。的次序出栈便得到转换的结果。其算法原理是：其算法原理是：N=（N/j）*j+N%j其中：其中：/为整除，为整除，%为求余为求余【例【例3-1】将十进制数将十进制数138转换为二进制转换为二进制数数
16、NN/2（整除）整除）N%2（求余）求余）138690693413417进进0出出178栈栈1栈栈84次次0次次42序序0序序210101（138）10=（10001010）21算法思想如下：算法思想如下：（1）若若N0，则则将将N%j取取得得的的余余数数压压入入栈栈s中中，执行（，执行（2）；）；若若N=0，将栈将栈s的内容依次出栈，算法结束。的内容依次出栈，算法结束。（2）用用N/j代替代替N（3）当当N0，则重复步骤（则重复步骤（1）、（）、（2）。）。2.算法的实现：算法的实现：voidConversion(intn)/将十进制数将十进制数n转换为二进制数转换为二进制数linkstac
17、ks;intx;s.top=NULL;dox=n%2;/除除2取余取余n=n/2;stacknode*p=newstacknode;/申请一个新结点申请一个新结点p-next=s.top;/修改栈顶指针修改栈顶指针s.top=p;s.top-data=x;/入栈入栈while(n);printf(转换后的二进制数值为：转换后的二进制数值为：);while(s.top)/余数出栈处理余数出栈处理printf(%d,s.top-data);/输出栈顶的余数输出栈顶的余数stacknode*p=s.top;/修改栈顶指针修改栈顶指针s.top=s.top-next;deletep;/回收一个结点，回
18、收一个结点，C语言中用语言中用freep3-3-2表达式求值表达式求值表达式是由运算对象、运算符、括号等组成的有意义式子。表达式是由运算对象、运算符、括号等组成的有意义式子。1 1中缀表达式中缀表达式（Infix NotationInfix Notation）一一般般我我们们所所用用表表达达式式是是将将运运算算符符号号放放在在两两运运算算对对象象的的中中间，比如：间，比如：a+ba+b，我们把这样的式子称为中缀表达式。我们把这样的式子称为中缀表达式。2 2后缀表达式（后缀表达式（Postfix NotationPostfix Notation）后缀表达式规定把运算符放在两个运算对象（操作数）后
19、缀表达式规定把运算符放在两个运算对象（操作数）的后面。在后缀表达式中，不存在运算符的优先级问题，也的后面。在后缀表达式中，不存在运算符的优先级问题，也不存在任何括号，计算的顺序完全按照运算符出现的先后次不存在任何括号，计算的顺序完全按照运算符出现的先后次次序进行。次序进行。3 3中缀表达式转换为后缀表达式中缀表达式转换为后缀表达式其其转转换换方方法法采采用用运运算算符符优优先先算算法法。转转换换过过程程需需要要两两个个栈栈：一个运算符号栈和一个后缀表达式输出符号栈。一个运算符号栈和一个后缀表达式输出符号栈。（1）读入操作数，直接送输出符号栈。）读入操作数，直接送输出符号栈。（2）读入运算符，压
20、入运算符号栈。）读入运算符，压入运算符号栈。(a)a)若后进的运算符优先级高于先进的，则继续进栈；若后进的运算符优先级高于先进的，则继续进栈；(b)b)若若后后进进的的运运算算符符优优先先级级不不高高于于先先进进的的，则则将将运运算算符符号号栈内高于或等于后进运算符级别的运算符依次弹出后进栈。栈内高于或等于后进运算符级别的运算符依次弹出后进栈。（3）括号处理：）括号处理：(a)a)遇到开括号遇到开括号“（”，进运算符号栈；，进运算符号栈；(b)b)遇遇到到闭闭括括号号“）”，则则把把最最靠靠近近的的开开括括号号“（”，以以及及其其后后进进栈栈的的运运算算符符依依次次弹弹出出到到符符号号栈栈，而
21、而括括号号不不压压入入符符号号栈。栈。（4）遇遇到到结结束束符符“#”，则则把把运运算算符符号号栈栈内内的的所所有有运运算算符符号依次弹出，并压入输出符号栈。号依次弹出，并压入输出符号栈。（5）若若输输入入为为+、单单目目运运算算符符，改改为为0 0与与运运算算对对象象在在前前，运算符在后。运算符在后。例如：例如：A A，转换为：转换为：0 0AA。【例【例3-23-2】A/B C+D*E A*C A/B C+D*E A*C输入符号输入符号运算符栈运算符栈输出结果输出结果操作说明操作说明AA输出输出A/A/进栈进栈B/A,B输出输出B/,A,B优先级高于优先级高于/，继续进栈，继续进栈C/,A
22、,B,C输出输出C+A,B,C,/，/依次弹出依次弹出D+A,B,C,/,D输出输出D*+,*A,B,C,/,D*优先级高于优先级高于+，继续进栈，继续进栈E+,*A,B,C,/,D,E输出输出E-A,B,C,/,D,E,*,+*，+依次弹出，依次弹出，-进栈进栈A-A,B,C,/,D,E,*,+,A输出输出A*-,*A,B,C,/,D,E,*,+,A*优先级高于优先级高于-，继续进，继续进栈栈C-,*A,B,C,/,D,E,*,+,A,C输出输出C#A,B,C,/,D,E,*,+,A,C,*,-遇到结束符遇到结束符#，依次弹出，依次弹出*，-【例【例3-33-3】3+4/3+4/（2525（
23、6+156+15）*8 8 输入符号输入符号运算符栈运算符栈输出结果输出结果操作说明操作说明33输出输出3+3+进栈进栈4+3,4输出输出4/+,/3,4/继续进栈继续进栈(+,/,(3,4（进栈（进栈25+,/,(3,4,25输出输出25-+,/,(,-3,4,25-进栈进栈(+,/,(,-,(3,4,25（再进栈（再进栈6+,/,(,-,(3,4,25,6输出输出6+,/,(,-,(,+3,4,25,6+进栈进栈15+,/,(,-,(,+3,4,25,6,15输出输出15)+,/,(,-3,4,25,6,15,+遇），依次弹出第遇），依次弹出第2个（后的符号个（后的符号)+,/3,4,25
24、,6,15,+,-遇），依次弹出第遇），依次弹出第1个（后的符号个（后的符号*+,*3,4,25,6,15,+,-,/弹出弹出/，但，但*高于高于+，继续进栈，继续进栈8+.*3,4,25,6,15,+,-,/,8输出输出8#3,4,25,6,15,+,-,/,8,*,+遇到结束符遇到结束符#，依次弹出，依次弹出*，+得到后缀表达式为：得到后缀表达式为：3 4 25 6 15 +/8 *+3 4 25 6 15 +/8 *+4 4后缀表达式求值后缀表达式求值后后缀缀表表达达式式求求值值的的运运算算要要用用到到一一个个数数栈栈stackstack和和一一个个存存放放后后缀缀表表达达式式的的字字符
25、符型型数数组组expexp。其其实实现现过过程程就就是是从从头头至尾扫描数组中的后缀表达式：至尾扫描数组中的后缀表达式：（1 1）当遇到运算对象时，就把它插入到数栈）当遇到运算对象时，就把它插入到数栈stackstack中；中；（2 2）当当遇遇到到运运算算符符时时，就就执执行行两两次次出出栈栈的的操操作作，对对出出栈栈的的数数进进行行该该运运算算符符指指定定的的运运算算，并并把把计计算算的的结结果果压压入入到到数数栈栈stackstack。把它插入到数栈把它插入到数栈stackstack中；中；（3 3）重重复复（1 1）、（2 2），直直至至扫扫描描到到表表达达式式的的终终止止符符“#”，
26、在数栈的栈顶得到表达式的值。，在数栈的栈顶得到表达式的值。动画演示动画演示 以例以例【例【例3-33-3】的结果看后缀表达式的计算过程：的结果看后缀表达式的计算过程：3 4 25 6 15+-/8*+3 4 25 6 15+-/8*+第第1 1次次计计算算结结果果为为：2121 第第2 2次计算结果为：次计算结果为：4 4 第第3 3次计算结果为：次计算结果为：1 1 第第4 4次计算结果为：次计算结果为：8 8 第第5 5次计算结果为：次计算结果为：1111动画演示3-3-3 3-3-3 子程序调用子程序调用（Subroutine CallSubroutine Call）在在计计算算机机程程
27、序序设设计计中中，子子程程序序的的调调用用及及返返回回地地址址就就是是利利用堆栈来完成的。用堆栈来完成的。在在C(C(或或C+)C+)语语言言的的主主函函数数对对无无参参子子函函数数的的嵌嵌套套调调用用过过程程中中，在在调调用用子子程程序序前前，先先将将返返回回地地址址保保存存到到堆堆栈栈中中，然然后后才才转转去去执执行行子子程程序序。当当子子函函数数执执行行到到returnreturn语语句句（或或函函数数结结束束）时时，便便从从栈栈中中弹弹出出返返回回地地址址，从从该该地地址址处处继继续续执执行程序。行程序。例例如如：主主函函数数调调用用子子函函数数a()a()时时，则则在在调调用用之之前
28、前先先将将a a函函数数返返回回地地址址压压入入栈栈中中；在在子子函函数数a()a()中中调调用用子子函函数数b()b()时时，又又将将b b函函数数返返回回地地址址压压人人栈栈中中；同同样样，在在子子函函数数b()b()中中调调用用子子函函数数c()c()时时，又又将将c c函函数数返返回回地地址址压压人人栈栈中中。其其调调用用返返回回地址进栈示意图如图地址进栈示意图如图3-53-5所示。所示。图图3-5无参函数嵌套调用返回地址进栈示意图无参函数嵌套调用返回地址进栈示意图当当执执行行完完子子函函数数c c()()以以后后，就就从从栈栈顶顶弹弹出出c c()()函函数数返返回回地地址址，回回到
29、到子子函函数数b b()()；子子函函数数b b()()执执行行完完毕毕返返回回时时，又又从从栈栈顶顶弹弹出出b b函函数数返返回回地地址址，回回到到子子函函数数a a()()；子子函函数数a a()()返返回回时时，再再在在栈栈顶顶弹弹出出a a函函数数返返回回地地址址，回回到到主主函函数数，继继续续执执行行主主函函数数程程序序。无参函数嵌调用返回示意图如图无参函数嵌调用返回示意图如图3-63-6所示。所示。c函数返回地址函数返回地址b函数返回地址函数返回地址a函数返回地址函数返回地址返回地址栈：返回地址栈：图图3-6无参函数嵌套调用返回示意图无参函数嵌套调用返回示意图3-3-4 3-3-4
30、 递归调用递归调用1 1递归递归一一个个直直接接调调用用自自己己，或或者者通通过过一一系系列列调调用用语语句句间间接接地地调调用用自自己己的的函函数数称称为为递递归归函函数数。在在程程序序设设计计中中，有有许许多多实实际际问问题题是是递递归归定定义义的的，使使用用递递归归的的方方法法编编写写程程序序将将使使许许多多复复杂杂的的问问题题大大大大简简化化。所所以以，递递归归是是程程序序设设计计中中的的一一个个强强有有力的工具。力的工具。2 2典型例子典型例子（1 1）2 2阶斐波那契（阶斐波那契（FibonacciFibonacci）数列数列0n=01n=1Fib(n1)+Fib(n2)其它情况F
31、ib(n)=（2）阶乘函数）阶乘函数n!的定义为：的定义为：Fac(n)=1n=0/递归终止条件递归终止条件n*Fac(n-1)n0/递归步骤递归步骤根据定义不难写出相应的递归函数：根据定义不难写出相应的递归函数：intfac(intn)if(n=0)return1；elsereturn(n*fac(n1)；3-3-5 3-3-5 中断处理和现场保护中断处理和现场保护1.1.中断处理中断处理（Interrupt ProcessingInterrupt Processing）在在C+语语言言中中，系系统统调调用用是是通通过过中中断断来来进进行行，中中断断调调用示意图用示意图如图如图3-8所示。所
32、示。图图3-8中断调用示意图中断调用示意图如如如如果把果把中断处理想象中断处理想象成成函数调用函数调用，则，则中断处理程中断处理程序可以序可以看成被看成被调用调用的的函数函数。2.2.现场保护现场保护和和恢复恢复执执行行中中断断时时，微微处处理理机机有有时时必必须须对对状状态态寄寄存存器器，累累加加器器，以以及及相相关关的的寄寄存存器器对对进进行行现现场场保保护护（压压栈栈）；中中断断处处理理完完毕毕，则则必必须须按按后后进进先先出出的的原原则则恢恢复复现现场场（出出栈栈）。下下面面，我我们们以以汇编语言汇编语言来来说明现场保护说明现场保护和和恢复恢复的的原理原理：；接受中断处理接受中断处理
33、PUSH AX PUSH AX ；保护现场保护现场 PUSH BXPUSH BX PUSH CX PUSH CX PUSH BP PUSH BP PUSHF PUSHF ；F F状态状态寄存器寄存器进栈进栈 ；中断处理中断处理 POPF POPF ；恢复现场恢复现场，后进后进栈的先出栈栈的先出栈 POP BPPOP BP POP CX POP CX POP BX POP BX POP AX POP AX（1）栈栈是是一一种种运运算算受受限限制制的的线线性性表表，它它只只允允许许在在栈栈顶顶进行插入和删除等操作。进行插入和删除等操作。（2）栈栈的的逻逻辑辑结结构构和和线线性性表表相相同同，数数据
34、据元元素素之之间间存存在在一对一的关系，其主要特点是一对一的关系，其主要特点是“后进先出后进先出”。（3）栈栈的的存存储储结结构构有有顺顺序序栈栈和和链链栈栈之之分分，要要求求掌掌握握栈栈的的C C语言描述方法。语言描述方法。（4）重重点点掌掌握握在在顺顺序序栈栈和和链链栈栈上上实实现现：进进栈栈、出出栈栈、读栈顶元素、判栈空和判栈满等基本操作。读栈顶元素、判栈空和判栈满等基本操作。（5）熟熟悉悉栈栈在在计计算算机机的的软软件件设设计计中中的的各各种种应应用用，能能灵灵活应用栈的基本原理解决一些综合性的应用问题。活应用栈的基本原理解决一些综合性的应用问题。小 结 验证性实验3 3 栈子系统 1
35、实验目的实验目的（1）掌握栈的特点及其描述方法。掌握栈的特点及其描述方法。（2）用链式存储结构实现一个栈。用链式存储结构实现一个栈。（3）掌握建栈的各种等基本操作。掌握建栈的各种等基本操作。（4）掌握栈的几个典型应用的算法。掌握栈的几个典型应用的算法。2.实验内容实验内容3.（1）设计一个字符型的链栈；）设计一个字符型的链栈；（2）编写进栈、出栈、显示栈中全部元素的程序；）编写进栈、出栈、显示栈中全部元素的程序；（3）编写一个把十进制整数转换成二进制数的应用程序；）编写一个把十进制整数转换成二进制数的应用程序；（4）编写一个把中缀表达式转换成后缀表达式的应用程序；）编写一个把中缀表达式转换成后
36、缀表达式的应用程序；（5）设计一个选择式菜单，以菜单方式选择上述操作。）设计一个选择式菜单，以菜单方式选择上述操作。栈栈 子子 系系 统统*1-1-进进 栈栈 *2-2-出出 栈栈 *3-3-显显 示示 *4-4-数制转换数制转换 *5-5-逆波兰式逆波兰式 *0-0-返返 回回 *请选择菜单号：请选择菜单号：自主性实验3 后缀表达式求值1实验目的实验目的（1）掌握栈）掌握栈“后进先出后进先出”的特点。的特点。（2）掌握栈的典型应用）掌握栈的典型应用后缀表达式求值。后缀表达式求值。2实验内容实验内容（1）用键盘输入一个整数后缀表达式（操作数的范围是）用键盘输入一个整数后缀表达式（操作数的范围是
37、09，运算符只含，运算符只含、*、/，而且中间不可以有空格），使，而且中间不可以有空格），使用循环程序从左向右读入表达式。用循环程序从左向右读入表达式。（2）如果读入的是操作数，直接进入操作数栈。）如果读入的是操作数，直接进入操作数栈。（3）如果读入的是运算符，立即从操作数栈取出所需的操作）如果读入的是运算符，立即从操作数栈取出所需的操作数，计算操作数运算的值，并将计算结果存回操作数栈。数，计算操作数运算的值，并将计算结果存回操作数栈。（4）检验程序运行结果。）检验程序运行结果。3实验要求实验要求（1）分析后缀表达式求值的算法思想，用）分析后缀表达式求值的算法思想，用C（或或C+）语言设计程序。语言设计程序。（2）上机调试通过实验程序。）上机调试通过实验程序。（3）给出具体的算法分析，包括时间复杂度和空间复杂）给出具体的算法分析，包括时间复杂度和空间复杂度等。度等。（4）撰写实验报告。）撰写实验报告。（5）本程序调试通过以后，添加到原教材验证性实验）本程序调试通过以后，添加到原教材验证性实验3的菜单中去。的菜单中去。单元练习3