栈及其应用.docx
《栈及其应用.docx》由会员分享，可在线阅读，更多相关《栈及其应用.docx（9页珍藏版）》请在冰点文库上搜索。
栈及其应用
贵州大学计算机科学与技术学院
计算机科学与技术系上机实验报告
课程名称：
数据结构
班级：
实验日期：
2013-4-22
姓名：
学号：
指导教师：
实验序号：
二
实验成绩：
一、实验名称
栈及其应用
二、实验目的及要求
1、熟悉栈的原理和实现方式；
2、理解使用栈消除函数递归调用的原理；
3、掌握后缀表达式计算的方法。
三、实验环境
VisualStudio2010
四、实验内容
1、栈实现阶乘函数；
2、栈实现后缀表达式的计算。
五、算法描述及实验步骤
函数调用栈的结构如下：
第n层调用
（当前函数局部变量空间）
第n-1层调用
（当前函数的主调函数变量空间）
…
第1层调用
主函数局部变量空间
函数调用的栈空间
使用栈消去递归的算法框架如下：
初始化栈；
将完整问题参数压栈；
while（栈非空）
{
取出栈顶元素所描述的问题
如果可以直接解决，则直接解决
否则分解为子问题压栈
}
后缀表达式是运算符在运算数之后的一种表达式存储的数据结构，不需要比较运算符优先级别，只需要每次读到运算数时压栈，读到运算符时将运算数出栈，将结果压栈即可。
最后的运算结果存放在栈底。
实验步骤
1、创建结构体栈Stack：
其中有栈顶指针，栈底指针。
2、创建顺序栈SqStack:
其中有数据域data，next指针。
3、从程序中写出所要求的阶乘值（用栈求阶乘函数）。
4、在程序中用数组表示后缀表达式，从控制面板输出结果（用栈实现后缀表达式的计算）。
5、调试运行。
六、调试过程及实验结果
1、用栈实现阶乘函数结果如下：
2、用栈实现后缀表达式计算结果如下：
七、总结
本次试验是用栈来完成阶乘函数与后缀表达式的计算，从中加深了对栈原理的理解并懂得如何用栈来解决一些实际问题，利用栈是一种递归的思想，学会怎样使用栈，如何将其运用到编程实践中去是一件值得非常重视的问题，希望在以后的学习中不断将其运用到实处。
八、附录
1、用栈实现阶乘函数代码如下：
#include"iostream"
#include
usingnamespacestd;
typedefstructSqStack
{
chardata;
structSqStack*next;
}SqStack;//链元素
typedefstructStack
{
structSqStack*base;//栈底指针
structSqStack*top;//栈顶指针
}Stack;//栈
StackS;//栈的全局对象S
intAj;
voidcreatstack（）
{
S.top=S.base=NULL;
}//建立初始化链栈
voidpush（Stack&S,inte）
{
SqStack*Q;
Q=（SqStack*）malloc（sizeof（SqStack））;
if（!
Q）exit（0）;
Q->next=S.top;//前一结点置在新建结点之后
S.top=Q;//栈顶指针往上移动
S.top->data=e;
++Aj;//记录字符的个数
}//左括号入栈
charPop（Stack&S）
{
chare;
SqStack*q;//辅助指针
e=S.top->data;
q=S.top->next;
free（S.top）;
S.top=q;//栈顶指针下移
returne;
}//括号出栈
intcheck（）
{
intn=5;//表示求多少数的阶乘
intNum=1;
for（inti=n;i>=1;i--）
{
push（S,i）;
}
for（Aj;Aj>0;Aj--）
{
Num=Num*Pop（S）;
}
returnNum;
}
voidmain（）//主函数
{
intReturn;
creatstack（）;//调用初始化栈
Return=check（）;
cout<<"输出5的阶乘为：
"<cout<}
2、用栈实现后缀表达式计算代码如下：
//输出运算结果为：
15
#include"iostream"
#include
usingnamespacestd;
typedefstructSqStack
{
intdata;
structSqStack*next;
}SqStack;//链元素
typedefstructStack
{
structSqStack*base;//栈底指针
structSqStack*top;//栈顶指针
}Stack;//栈
StackS;//栈的全局对象S
voidcreatstack（）
{
S.top=S.base=NULL;
}//建立初始化链栈
voidpush（Stack&S,inte）
{
SqStack*Q;
Q=（SqStack*）malloc（sizeof（SqStack））;
if（!
Q）exit（0）;
Q->next=S.top;//前一结点置在新建结点之后
S.top=Q;//栈顶指针往上移动
S.top->data=e;
}
intPop（Stack&S）
{
inte;
SqStack*q;//辅助指针
e=S.top->data;
q=S.top->next;
free（S.top）;
S.top=q;//栈顶指针下移
returne;
}//括号出栈
intcheck（）
{
intReturn;
inta=0;
intRet;
charstring[]={'1','_','0','5','1','_','0','1','_','5','5','2','^','+','-','*','/','='};
charch,sh,*st,*stt;//ch表示前一个字符，sh表示后一个字符
cout<<"后缀表达式为：
"<st=stt=string;//分别将st,stt指向输入字符串的首地址
ch=*st;//将字符串的第一个字符赋给字符变量ch
sh=*（++stt）;
while（ch!
='='）//判断字符是否为结束标志
{//"_"即下划线表示：
当输入为2位数或2位数以上时，中间用下划线隔开。
if（ch!
='+'||ch!
='-'||ch!
='*'||ch!
='/'||ch!
='^'）//判断是否满足入栈和出栈条件
{
if（（ch>='0'&&ch<='9'）||sh=='_'）
{
if（ch>='0'&&ch<='9'&&sh=='_'）//将字符型转化为整型，之后压栈
a=（a+ch-48）*10;//1的ACSII码为48；
else
{
a=（a+ch-48）;
push（S,a）;
a=0;
}
}
}
if（ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='^'）//判断遇到运算符就从栈中出来2个数进行相应的运算
{
intfirst=Pop（S）;
intsecond=Pop（S）;
switch（ch）
{
case'+':
{Ret=first+second;push（S,Ret）;}break;
case'-':
{Ret=first-second;push（S,Ret）;}break;
case'*':
{Ret=first*second;push（S,Ret）;}break;
case'/':
{Ret=first/second;push（S,Ret）;}break;
case'^':
{
inttemp=1;
for（first;first>=1;first--）
{
temp=temp*second;
}
push（S,temp）;
}break;
}
}
ch=*（++st）;//字符往后移动
sh=*（++stt）;
}
if（ch=='='）
Return=Pop（S）;
returnReturn;
}
voidmain（）//主函数
{
intResult;
creatstack（）;//调用初始化栈
Result=check（）;
cout<<"此表达式的结果为：
"<}
升级会员 