栈和队列——数据结构实验报告教程.doc
文本预览下载声明
实习报告
题目：设计一个演示用运算优先法对算数表达式求职过程的程序。
班级： 姓名： 学号： 完成日期：
需求分析
1建立运算数栈SqStack1和运算符栈SqStack2辅助分析算符有限关系.
2用户输入以“#”结尾的算数表达式，本程序需要用户自行输入表达式（运算符可以是加（+）；减（-）；乘（*）；除（/）；括号（（））），以字符形式读入，在读入的同时，完成运算符和运算数的识别处理，在识别出运算数的同时，要将其字符序列形式转换成整数形式。
3在程序的适当位置输出运算符栈、运算数栈、输入字符和主要操作的内容，即演示运算操作。
4测试数据见原题。
5程序执行的命令包括：
建立算数表达式；
得到运算表达式的值；
演示运算过程。
概要设计
设定栈的抽象数据类型定义：
ADT Stack{
数据对象
D＝{ ai | ai ∈charSet, i=1,2,...,n, n≥0 }
数据关系：
R1＝{ ai-1, ai | ai-1, ai∈D, i=2,...,n }
（约定an 端为栈顶，a1 端为栈底）
基本操作：
InitStack（S）
操作结果：构造一个空栈S。
Gettop(S,e)
初始条件：栈S已存在。
操作结果：若栈S不空，则以e返回栈顶元素。
Push(S,e)
初始条件：栈 S 已存在。 操作结果：插入元素 e 为新的栈顶元素。
Pop(S,e)
初始条件：栈 S 已存在且非空。 操作结果：删除 S 的栈顶元素，并用 e 返回其值。
}ADT Stack
本程序包括三个模块
（1）主程序模块：
Void main( )
{
初始化；
函数；
}
（2）栈模块——实现栈抽象数据类型
（3）运算模块——实现运算并演示其过程模块
各模块之间调用关系如下：
主程序模块
运算模块
栈模块
三、详细设计
元素类型、结点类型
typedef struct{
int *base;
int *top;
int stacksize;
}SqStack1; //操作数栈
typedef struct{
char *base;
char *top;
int stacksize;
}SqStack2; //操作符栈
栈类型 typedef struct{
char *base;
char *top;
int stacksize;
}Stack;????????????//栈类型 栈的基本操作设置如下： void InitStack(Stack S) ????//初始化，设S为空栈（S.top=NULL） Status GetTop(Stack S,ElemType e) ???//若栈S不空，则以e带回栈顶元素并返回TRUE，否则返回FALSE Status Push(StackS,ElemType e) ??//若分配空间成功，则在S的栈顶插入新的栈顶元素e，并返回TRUE， ??//否则返回FALSE其中部分操作的算法：
Status Push(Stack S,ElemType e)
{
???//若分配空间成功，则在S的栈顶插入新的栈顶元素e，并返回TRUE； ???//否则栈不变，并返回FALSE ??if(MakeNode(p,e)){ P.next=S.top;S.top=p;
S.size++; Return TRUE;
}
else return FALSE; } Status Pop(Stack S,ElemType e) { ???//若栈不空，则删除S的栈顶元素并以e带回其值，且返回TRUE， ???//否则返回FALSE，且e无意义 ??if(StackEmpty(S)) return FALSE; ??else{ ??p=S.top;S.top=S.top-next; e=p-:data;S.size--; return TRUE; } }
3、运算代码
int Operate(int a,char theta,int b) //计算表达式值：主要是将大的表达式转化成小的表达式进行逐步求值
{
int c;
if(theta==+) c=a+b;
else if(theta==-) c=a-b;
else if(theta==*) c=a*b;
else c=a/b;
return c;
}//Operate
int result(SqStack1 *OPND,SqStack2 *OPTR) //求值
{
char a=0;
char theta;
int b,c,number=0;
IntInitStack(OPND);
CharInit
显示全部