栈的利用

实验二栈的应用(数制转换)一、实验目的掌握栈的基本操作：初始化栈、判栈为空、出栈、入栈等运算。

二、实验要求1．认真阅读和掌握本实验的算法。

2．上机将本算法实现。

3．保存程序的运行结果，并结合程序进行分析。

三、实验内容利用栈的基本操作实现将任意一个十进制整数转化为R进制整数算法为：1、定义栈的顺序存取结构2、分别定义栈的基本操作（初始化栈、判栈为空、出栈、入栈等）3、定义一个函数用来实现上面问题：(1)十进制整数X和R作为形参(2)初始化栈(3)只要X不为0重复做下列动作将X % R入栈, X=X/R(4)只要栈不为空重复做下列动作栈顶出栈 , 输出栈顶元素四、实验报告要求：1、十进制整数转化为R进制整数算法的代码；2、程序运行结果及分析；3、实验总结。

1.实验源码：#include"stdio.h"#include"stdlib.h"#include"malloc.h"#define maxsize 100typedef struct{int data[maxsize];int top;}seqstack,*pseqstack;pseqstack setstack(){pseqstack s;s=(pseqstack)malloc(sizeof(seqstack));if(s)s->top=-1;return s;}int empty(pseqstack s){if(s->top==-1）return 1;elsereturn 0;}pseqstack pushin(pseqstack s,int m,int r) {if(s->top==maxsize-1)printf("此栈已满，无法入栈！\n");else{while(m!=0){s->top++;s->data[s->top]=m%r;m=(m-(m%r))/r;}}return s;}int popout(pseqstack s){if(empty(s))return 0;else{printf("转化后的数是：");while(s->top!=-1){printf("%d",s->data[s->top]);s->top--;}putchar('\n');return 1;}}void main(){int m,r;pseqstack p;p=(pseqstack)malloc(sizeof(seqstack));printf("请输入一个十进制的正整数：");scanf("%d",&m);printf("请输入你想转化的进制位：");scanf("%d",&r);p=setstack();p=pushin(p,m,r);popout(p);}2.程序截图：3.实验总结：友情提示：本资料代表个人观点，如有帮助请下载，谢谢您的浏览！。

（二）过程与方法
在学习“3.3.2栈的应用”过程中，学生将通过以下方法和过程来达成学习目标：
1.探究学习：通过小组讨论、自主探究，发现并理解栈的特性及其在解决实际问题中的应用。
-教师组织课堂活动，引导学生主动探索，培养其发现问题和解决问题的能力。
2.案例分析：分析栈在解决实际问题中的典型应用，提炼出算法设计的通用方法和步骤。
（二）讲授新知
在讲授新知环节，教师按照以下步骤进行：
1.理论讲解：详细讲解பைடு நூலகம்的基本概念、特性以及在实际问题中的应用场景，如括号匹配、路径问题等。
2.算法分析：通过分析表达式求值、括号匹配等案例，讲解栈在算法设计中的关键作用，引导学生理解算法的步骤和原理。
3.代码演示：以编程语言为例，现场演示栈的实现及在表达式求值中的应用，让学生了解栈的具体操作过程。
在总结归纳环节，教师引导学生进行以下总结：
1.栈的基本概念和特性：回顾栈的定义、特点以及在实际问题中的应用。
2.栈的算法设计：总结栈在解决实际问题中的关键步骤和方法。
3.编程实践：强调编程实践中的注意事项，如代码规范、调试技巧等。
4.团队协作：强调团队协作在解决问题中的重要性，鼓励学生在今后的学习中积极参与合作。
-此作业旨在激发学生的探究兴趣，培养其创新思维和解决实际问题的能力。
4.小组合作项目：以小组为单位，共同完成一个基于栈的应用项目。项目主题自选，可以是游戏、工具软件或任何能够体现栈特性的应用。
-通过小组合作，学生可以锻炼团队协作能力，同时在实际项目中进一步掌握栈的使用。
5.课后反思：请学生结合课堂学习和作业完成情况，撰写一份课后反思，内容包括自己在学习栈的过程中遇到的困难、解决问题的方法、对栈的理解和感受，以及对未来学习的规划。

栈的应用场景栈是一种常见的数据结构，它的特点是后进先出（Last In First Out，LIFO）。

栈的应用场景非常广泛，从计算机科学到日常生活都可以见到其身影。

本文将介绍栈在不同领域的应用场景。

1.计算机算法在计算机算法中，栈经常被用于实现递归函数、表达式求值、括号匹配等操作。

递归函数的调用过程实际上是一个栈的过程，每当一个函数调用另一个函数时，系统会将当前函数的状态信息压入栈中，待调用的函数执行完毕后再从栈中弹出上一个函数的状态信息继续执行。

表达式求值中，栈可以用于存储操作数和运算符，通过弹出栈中的元素进行计算，最终得到表达式的结果。

括号匹配中，栈可以用于判断左右括号是否匹配。

2.编译器和操作系统编译器和操作系统也是栈的常用应用场景。

在编译器中，栈用于存储函数调用的参数、局部变量和返回地址等信息。

每当函数调用时，编译器会将相关信息压入栈中，函数执行结束后再从栈中弹出相关信息。

操作系统中的函数调用、中断处理等过程也经常使用栈来保存现场信息，保证程序的正确执行。

3.网络协议在网络协议中，栈被广泛应用于网络数据的传输和处理。

TCP/IP协议栈是一个典型的例子，它将网络层、传输层、应用层等不同的协议通过栈的形式依次封装，完成数据的传输和处理。

数据包从应用层一直传输到网络层，以栈的形式不断压入和弹出，确保数据的准确传递和处理。

4.浏览器的前进后退功能在浏览器中，前进和后退功能是栈应用的典型场景。

当我们浏览网页时，每当点击一个链接或者输入一个网址，浏览器会将当前的URL 压入栈中。

当我们点击“后退”按钮时，浏览器会从栈中弹出上一个URL，完成页面的后退操作。

同样地，当我们点击“前进”按钮时，浏览器会从栈中弹出下一个URL，完成页面的前进操作。

5.撤销和恢复操作在各种应用程序中，栈可用于实现撤销和恢复操作。

例如，在文字编辑器中，当我们对文字进行修改后，可以将修改前的状态信息压入栈中，以备将来的撤销操作。

出”。

四、栈的应用举例任何一个表达式都是由操作数、运算符和界限符组成的。

后两项统称为算符，算符集合命名为OP。

引入问题：如何用堆栈实现表达式求值？表达式求值有三种形式。

中缀表示：<操作数><运算符><操作数>前缀表示：<运算符><操作数><操作数>后缀表示：<操作数><操作数><运算符>以中缀表达式为例，进行重点讲解。

例2、用栈求解表达式21+44-3*6的值。

# 21+44-3*6#实现方法：设置一个运算符栈和一个操作数栈。

算符间的优先关系求值规则：1）先乘除,后加减；2）先括号内,后括号外；3）同类运算,从左至右。

约定：q1---栈顶的运算符q2---当前的运算符当q1=#，为开始符当q2=#，为结束符根据上述优先关系表，可见21+44-3*6#中‘-’ <‘*’，‘*’ >‘#’。

2、算法基本思想1）首先置‘#’为运算符栈的栈底元素, 操作数栈为空栈；2) 依次读入表达式中各个字符，如果判断为操作数则OPND栈，如21，44，进操作数栈；若为运算符θ2，则和OPTR的栈顶元素θ1比较优先级，θ1和θ2进行比较。

当θ1 < θ2 ，θ2 进栈；表达式21+44-3*6的算法编程实现。

[动画演示]1.5分钟结合算法演示系统，讲解用栈求解表达式21+44-3*6的算法执行过程。

[小结]2分钟栈的定义，栈的“先进后出”的特性；栈的顺序存储的实现；栈的应用。

当θ1 = θ2 ，θ1 出栈；若θ1 > θ2 ，θ1 出栈，先进行操作数求值；然后运算结果再进栈。

3、算法编程实现OperandType EvaluateExpression ( ){ InitStack(OPTR);push(OPTR,`#`);InitStack(OPND);read(w);Whi le NOT ((w=’#’)AND (GetTop(OPTR)= `#`) )[IF w NOT IN op THEN[ push(OPND,w); read(w);ELSE CASEPrecede(GetTop(OPTR),w)OF`<`:[ push(OPTR,c); read(w);]`=`: [pop(OPTR,x);if x=FUNCTION thenPUSH(OPND,x(POP(OPNE)));read(w);]`>`: [b:= pop(OPND);a:= pop(OPND);theta:= pop(OPTR);push(OPND,Operate(a,theta,b));]ENDC; ]RETURN(POP(OPND))ENDF;4、算法执行过程# 21+44-3*6#1）“#”先压入到运算符栈，即push(OPTR,`#`);OPTR OPND2）push(OPND,`21`)2）‘#’ <‘+’，push(OPTR, `+` );3）push(OPND,`44`)。