数据结构算术表达式求值课程设计
- 格式:doc
- 大小:375.88 KB
- 文档页数:27
目录
1.前言 (2)
2.问题描述 (3)
3.总体设计··········································································错误!未定义书签。
3.1 概要设计 ······································································错误!未定义书签。
3.1.1 数据结构的选择 (3)
3.1.2 相关功能函数 (3)
3.1.3 函数模块调用关系 (4)
3.2详细设计和编码 (5)
4.运行与测试 (9)
4.1 上机调试 (9)
4.2 算法时间和空间性能分析 (10)
4.3程序运行测试结果 (11)
5. 总结与心得 (13)
5.1设计中难点的总结以及其它解决方案 (13)
5.2 实验心得 (14)
6. 用户使用说明 (16)
7. 参考文献 (16)
8. 附录1(源代码清单) (16)
9. 附录2(成绩评定表) (25)
1.前言
课程设计是实践性教学中的一个重要环节,它以某一课程为基础,它可以涉及和课程相关的各个方面,是一门独立于课程之外的特殊课程。课程设计是让同学们对所学的课程更全面的学习和应用,理解和掌握课程的相关知识。《数据结构》是一门重要的专业基础课,是计算机理论和应用的核心基础课程。
在数据结构的学习和课程设计过程中,我发现它要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面,都必须加深对课程基本内容的理解。同时,在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。对于我们专业来说,虽然说对技术要求不是特别高,但是在实际操作过程中,没有足够的专业知识对于编程来说是远远不可以达到要求的,所以对于这次的课程设计,我们必须要通过自己额外补充知识来完成它。
在这次的课程设计中我选择的题目是表达式的求值演示。它的基本要求是:以字符序列的形式从终端输入语法正确的,不含变量的表达式。利用算符优先关系,实现对算术四则混合运算表达式的求值,并演示在求值中运算符栈、运算数栈、输入字符和主要操作的变化过程。表达式计算是实现程序设计语言的基本问题之一,也是栈的应用的一个典型例子。设计一个程序,演示用算符优先法对算术表达式求值的过程。深入了解栈和队列的特性,以便在解决实际问题中灵活运用它们,同时加深对这种结构的理解和认识。对于表示出栈在每执行一个过程中都要输出它的变化,这点我认为在编程中是比较困难的,以我自身的能力,是不可能在规定的时间内完成任务的,所以我参考了很多有价值的书籍来帮助我完成我的程序设计。
2.问题描述(问题分析和任务定义)
在计算机中,算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同的优先级,又要考虑括号,因此,算术表达式的求值不可能严格地从左到右进行。因此,要求设计一个程序,利用栈演示运算符优先法对算术表达式求值的过程,利用算符有限关系,实现对算数混合四则运算表达式的求值。
程序输入:一个算术表达式,由常量、运算符和括号组成(以字符串
形式输入,不含变量)。为了简化,操作数只能为浮点数,操作
符为“+”、“-”、“*”、“/”、“(”、“)”,用“#”
表示结束。
程序输出:表达式运算结果,运算符栈、运算数栈、输入字符和主要操作变化过程。
测试数据:1024/(4*8) 、(20+2)*(6/2)(用于正确性检测的合法输入数据)9/0 (用于健壮性检测的非法输入数据)
3.总体设计
3.1概要设计
3.1.1数据结构的选择
任何一个表达式都是由操作符,运算符和界限符组成的。我们分别用顺序栈来寄存表达式的操作数和运算符。栈是限定于紧仅在表尾进行插入或删除操作的线性表。
为了实现算符优先算法,可以使用两个工作栈。一个称做OPTR,用以寄存运算符;另一个称做OPND,用以寄存操作数或运算结果。首先置操作数栈为空栈,表达式起始符“#”作为运算符栈的栈底元素,然后依次读入表达式的每个字符,若是操作数则进入OPND栈,若是运算符,则和OPTR栈的栈顶运算符比较优先权后做相应操作,直至整个表达式求值完毕。
栈的抽象数据类型定义
ADT SqStack{
数据对象:D={ai| ai ∈ElemSet,i=1,2,3……,n,n≥0}
数据关系:R1={
约定其中ai端为栈底,an端为栈顶。
操作集合:见如下相关功能函数
}ADT SqStack
3.1.2相关功能函数
3.1.3函数模块调用关系
主程序模块
栈的建立及初始化模块
判断输入是否结束模块
判断字符类型模块输入结束输出结果
运算数进栈模块运算符优先级比较模块
运算符进栈模块运算符运算数出栈模块
运算模块
3.2详细设计和编码
首先本程序定义两个顺序栈:运算符栈(OPTR)和运算数栈(OPND);
OPTR栈定义如下:
typedef struct{
char * base; //算符栈的栈底
char * top; //算符栈的栈顶
int stacksize; //算符栈的最大长度
}Optr_Stack;
OPND栈定义如下:
typedef struct{
float * base; //操作数栈的栈底
float * top; //操作数栈的栈顶
int stacksize; //操作数栈的最大长度
}Opnd_Stack;
然后是主要功能函数的详细设计:
(1)char Precede(char m,char n) 判断运算符优先权,返回优先权高的算符间的优先关系如下: