数据结构顺序栈实验报告
一、 设计人员相关信息
1. 设计者姓名、学号和班号：12地信李晓婧 12012242983
2. 设计日期：2014.
3. 上机环境：VC++6.0
二、 程序设计相关信息
1. 实验题目：编写一个程序，实现顺序栈（假设栈中元素类型为char）的各种基本运算，并在此基础上设计一个程序，完成如下功能：
（1）初始化栈
（2）判断栈是否为空
（3）依次进栈元素a,b,c,d,e
（4）判断栈是否为空
（5）输出栈长度
（6）输出从栈顶到栈底元素
（7）输出出栈序列
（8）判断栈是否为空
（9）释放栈
2. 实验项目组成：栈的初始化、销毁、判断是否为空、进栈、出栈、取栈顶元素。
3. 实验项目的程序结构（程序中的函数调用关系图）：
4. 实验项目包含的各个文件中的函数的功能描述：
（1）初始化栈InitStack：建立一个新的空栈，实际上将栈顶指针指向-1即可。
（2）销毁栈DestroyStack：释放栈占用的存储空间
（3）判断栈是否为空StackEmpty：栈为空的条件是s->op==-1。
（4）进栈Push：在栈不满的条件下，先将栈顶指针增1，然后在栈顶指针指向位置插入元素e。
（5）出栈Pop：在栈不为空的条件下，先将栈顶元素赋给e，然后将栈顶指针减1.
（6）取栈顶元素GetTop：在栈不为空的条件下，将栈顶元素赋给e。
5. 算法描述或流程图：
#include "stdio.h"
#include "malloc.h"
#include<stdlib.h>
#define MaxSize 50
typedef char ElemType;
typedef struct
{ElemType data[MaxSize];
int top; /*栈顶指针*/
}SqStack; //定义顺序栈类型
void InitStack(SqStack*&s)/*初始化*/
{
s=(SqStack*)malloc(sizeof(SqStack));
s->top=-1; //栈顶指针置为-1
}
void DestroyStack(SqStack *&s)/*销毁*/
{
free(s);
}
int StackEmpty(SqStack*s)/*判断是否为空*/
{
return(s->top==-1);
}
int push(SqStack *&s,ElemType a[],int n)
{
int i; if(s->top==MaxSize-1) //栈满的情况，即栈上溢出 return 0; for(i=0;i<n;i++) { s->top++; //栈顶指针增1
s->data[s->top]=a[i]; //元素e放在栈顶指针处
}
int Pop(SqStack*&s,ElemType &e)/*出栈一个元素*/ {
if(s->top==-1) //栈为空的情况，即栈下溢出 return 0;
e=s->data[s->top]; //取栈顶元素
s->top--; //栈顶指针减1
return 1;
}
} return 1;
int GetTop(SqStack *s,ElemType &e)/*取栈顶元素*/ {
if(s->top==-1) //栈为空的情况，即栈下溢出 return 0;
e=s->data[s->top]; //取栈顶元素
return 1;
}
int StackLength(SqStack *s)/*求栈长度*/
{
return(s->top+1);
}
void DispStack(SqStack *s)
{
}
void main()
{
int i,j;
ElemType str[5]={'a','b','c','d','e'}; //定义字符数组 SqStack *st; //定义栈
InitStack(st);/*初始化*/
i=StackEmpty(st); //判断栈是否为空
if(i==0) int i; for(i=s->top;i>=0;i--) printf("%c",s->data[i]); printf("\n");
printf("顺序栈非空\n"); else printf("顺序栈为空\n");
push(st,str,5); //进栈
j=StackEmpty(st);
if(j==0)
printf("顺序栈非空\n"); else printf("顺序栈为空\n");
printf("栈长度为：%d\n",StackLength(st)); //输出栈长度
printf("出栈序列:\n");
DispStack(st); //输出栈
StackEmpty(st);
DestroyStack(st);
}
6. 实验数据和实验结果：
7. 出现的问题及解决方案：
(1)
(2)
(3)
解决方案：(1)添加typedef char ElemType;
(2)
(3)
三、 程序盘
提交的程序盘应包含全部的源程序清单和可执行文件。
第二篇：数据结构 顺序栈
《数据结构》实验报告二
实验二 用顺序栈计算表达式
一【实验内容与要求】
问题描述：利用栈的基本操作实现一个算术表达式的求值的程序。
基本要求：
（1） 定义栈的顺序存取结构。
（2） 分别定义顺序栈的基本操作（初始化栈、判栈空否、入栈、出栈等）。
（3） 定义一个函数用来计算表达式结果，并且可以显示表达式的后缀表示。
（4） 设计一个测试主函数进行测试。
【测试数据】
输入：4+5*2+9+（-5）^2=
输出：4+5*2+9+（-5）^2=48.00
二、程序设计的基本思想，原理和算法描述：
1）：符号说明
Functor 算符栈结构体
NUM 运算对象栈
ch 存放输入的字符
fun 算符
grade 算符的等级
value 临时用来存放数据
result 表示最终运算结果
2）算法描述： 先通过键盘键入中缀表达式，然后将其中的运算对象和算符依次分开，分别存入运算栈和算符栈内，初始化算符栈等级。按照中缀表达式的方法，计算结果。
三、源程序及注释：
typedef struct //定义算符栈结构体
{
char fun;// 算符
int grade//算符的等级
}Functor;
Functor FUNCTOR[20];
float NUM[20]; //定义算符栈和对象栈
char ch[100]; //存放输入流的字符串
int sub=0;//定义全局变量来一次取字符
float Char_To_Num(){//将表示数据的
int flag=0, i=-1;
float value=0.0;//用来表示字符串转化成数据后的数据
while((ch[sub]>=48 && ch[sub]<=57) || ch[sub]=='.'){//48表示0的asc值，57表示9的，用于判断取的字符是否在0到9之间
if(ch[sub]=='.')
flag=1; //取的字是.号时 flag为1
else{
if(flag==0) value=value*10+ch[sub]-48;//计算整数部分
else{
value=value+( ch[sub]-48 )*pow(10,i);//计算小数部分
i--;//表示计算下一位小数做好准备
}}
sub++;//自加表示为取下一个字符做好准备
}
return value;//返回数字
}
int In_Grade(char c)
{ //算符在栈内时的级别
int g;
switch(c)
{
case '^': g=3;break;// 表示^的等级为3
case '*': 表示*的等级为3
case '/': 表示*的等级为3
case '%': g=2;break; 表示%的等级为2
case '+':
case '-': g=1;break; 表示+- 的等级为1
case '(': g=0;break; 表示(等级为0
case ')': g=-1;break; 表示(等级为0
}
return g; 返回所得的算符的等级
}
int Out_Grade()
{ //算符在栈外时的级别
int g;
switch(ch[sub])
{
case '^': g=4;break; //表示^的等级为4
case '*':
case '/': 表示* / % 的等级为2
case '%': g=2;break;
case '+':
case '-': g=1;break; 表示+- 的等级为1
case '(': g=4;break; 表示(等级为4
case ')': g=-1;break; 表示)等级为-1
}
return g; 返回算符的栈外等级
}
void Error()
{
printf("输入的表达式有误！\n");
printf("\n按任意键退出");
getch();
exit(1);
}
void Calculate(int i, int j)//计算子程序
{
if(i>=2)
{ //判断对象栈中元素个数
switch(FUNCTOR[j-1].fun)//
{
case '^': NUM[i-2]=pow(NUM[i-2],NUM[i-1]); break//具体计算过程表示;+-*/^%
case '*': NUM[i-2]=NUM[i-2]*NUM[i-1]; break;
case '/': NUM[i-2]=NUM[i-2]/NUM[i-1]; break;
case '%': NUM[i-2]=int(NUM[i-2])%int(NUM[i-1]); break;
case '+': NUM[i-2]=NUM[i-2]+NUM[i-1]; break;
case '-': NUM[i-2]=NUM[i-2]-NUM[i-1]; break;
}
NUM[i-1]=0;//计算完之后 num清零
FUNCTOR[j-1].fun=0;//计算完之后 算符清零
}
else Error();
//若对象栈若只剩一个数据，则输入的表达式有误
}
float Char_Transform(){
int i=0, j=0, grade, flag=0;
while( ch[sub]!='=' || j!=0 ){//用来控制字符是否取完
if(ch[sub]=='='){
//输入的字符是否取完
Calculate(i, j);计算最后两个运算对像
i--;
j--;}
else{
if(ch[sub]>=48 && ch[sub]<=57){
//判断是否为运算对象
NUM[i++]=Char_To_Num();//将离散的字符转换成连续数字
if(flag){
NUM[i-1]=-NUM[i-1];//如果flag=1，即前面有-，将运算对象取反
FUNCTOR[j-1].fun=0;
j--;
flag=0;
}}
else{
if(ch[sub]=='%' ||
(ch[sub]>=40 && ch[sub]<=43) ||
ch[sub]=='-' ||ch[sub]=='^' ||
ch[sub]=='/'){
//判断是否为算符
if( FUNCTOR[j-1].fun=='-' &&
FUNCTOR[j-2].fun=='(' &&
ch[sub]==')'){
//判断是否为负数
NUM[i-1]=-NUM[i-1];
FUNCTOR[j-1].fun=0;
FUNCTOR[j-2].fun=0;
j=j-2;
sub++;}
else{
if( FUNCTOR[j-1].fun== '(' && ch[sub]== ')' ){
//括号内表达式计算完后则将左括号从栈中去除
FUNCTOR[j-1].fun=0;//清零
j--;
sub++;}
else{
grade=Out_Grade(); //栈外算符的级别
if(j==0 || grade>FUNCTOR[j-1].grade){
//第一个或级别比栈内算符高的进栈
FUNCTOR[j].fun=ch[sub];
FUNCTOR[j].grade=In_Grade(ch[sub]);
if(j==0 && FUNCTOR[j].fun=='-') flag=1;
j++;
sub++;}
else{
Calculate(i, j);如果第一个或级别比栈内算符低，直接将栈内的算符取出计算
i--;
j--;
}}}}
else Error();
//表达式中有非算术字符，则表达式有误
}}}
return NUM[i-1];
}
int main()
{
float result;
printf("****************************************\n");
printf("请输入要求解的表达式,并以等号“=”结束:\n");
printf("****************************************\n");
gets(ch);//输入要计算的表达式
result=Char_Transform();//调用函数Char_Transform()将结果送到result
printf("%s%.2f\n", ch, result);
printf("\n按任意键退出");
getch();
}
四、运行输出结果
五、调试和运行程序过程中产生的问题及采取的措施：
由于这个程序不是自己写的，没有比较具体的调试过程，所以对整个理解不是那么深。拿到程序后，在具体的运行中发现一些小问题，比如说输入格式问题，例如输入：3-5时求解
答案为-5，明显不对，经过师兄执指教后发现，在这个程序中当数字前有“-”时，应将其当成一个负数来计算（加括号），例如3-5应为3+（-5）才可以。。。。
六、对算法的程序的讨论、分析，改进设想，其它经验教训：
在我们具体着手写这个程序时，应该对逆波兰表达式有一定的了解，逆波兰表达式是一种十分有用的表达式，它将复杂表达式转换为可以依靠简单的操作得到计算结果的表达式。例如(a+b)*(c+d)转换为ab+cd+*
它的优势在于只用两种简单操作，入栈和出栈就可以搞定任何普通表达式的运算。其运算方式如下：
如果当前字符为变量或者为数字，则压栈，如果是运算符，则将栈顶两个元素弹出作相应运算，结果再入栈，最后当表达式扫描完后，栈里的就是结果。
下面是程序化算法流程：
1、建立运算符栈 用于运算符的存储，压入'\0'。
2、预处理表达式，正、负号前加0(如果一个加号（减号）出现在最前面或左括号后面，则该加号（减号）为正负号) 。
3、顺序扫描表达式，如果当前字符是数字（优先级为0的符号），则直接输出该数字；如果当前字符为运算符或括号（优先级不为0的符号），则判断第4点 。
4、若当前运算符为'('，直接入栈；
若为')'，出栈并顺序输出运算符直到遇到第一个'('，遇到的第一个'('出栈但不输出；
若为其它，比较栈顶元素与当前元素的优先级：
如果 栈顶元素 >= 当前元素，出栈并顺序输出运算符直到 栈顶元素 < 当前元素，然后当前元素入栈；
如果 栈顶元素 < 当前元素，直接入栈。
5、重复第3点直到表达式扫描完毕。
- 数据结构栈和队列实验报告
-
数据结构顺序栈实验报告
一设计人员相关信息1设计者姓名学号和班号12地信李晓婧120xx2429832设计日期20xx3上机环境VC60二程序设计相关信息…
-
数据结构出栈、入栈实验报告
数据结构实验报告院系应用科技学院专业电子信息工程姓名学号班1实验目的123熟悉栈的定义和栈的基本操作掌握顺序存储栈和链接存储栈的基…
-
数据结构实验报告(栈的应用)
实习报告题目编制一个演示表达式求值的操作的程序班级计算机信息安全姓名学号完成日期需求分析本演示程序中元素限定为int整型和char…
-
数据结构实验报告二栈的应用
数据结构实验指导书姓名修凌云姓名李赛赛信息与计算科学教研室实验一栈及其应用实验目的熟悉栈的基本概念熟练掌握并实现栈的基本操作以及两…
-
云南大学软件学院数据结构实验六实验报告——赫夫曼编码译码器
云南大学软件学院数据结构实验报告本实验项目方案受教育部人才培养模式创新实验区X3108005项目资助实验难度ABC学期任课教师实验…
-
数据结构实验报告(C语言)(强力推荐)
数据结构实验实验内容和目的掌握几种基本的数据结构集合线性结构树形结构等在求解实际问题中的应用以及培养书写规范文档的技巧学习基本的查…
-
算法与数据结构栈与队列实验报告
实验二栈和队列实现四则运算实验二栈和队列实现四则运算一实验目的及要求1掌握栈和队列的基本操作建立插入删除查找合并2掌握用栈和队列的…
-
数据结构实验报告 栈和队列
20xx级数据结构实验报告实验名称实验二栈和队列日期20xx年11月15日1实验要求实验目的通过选择下面五个题目之一进行实现掌握如…
- 数据结构栈和队列实验报告