1、 “数据结构”课程设计 报告 系系 （院） ：院） ： 信息工程学院信息工程学院 设计题目：设计题目： 表达式求值表达式求值 专业班级：专业班级： 计算机科学计算机科学与技术与技术 1301B1301B 小组成员：小组成员： 指导教师：指导教师： 完成时间：完成时间： 20142015 学年第二学期学年第二学期 数据结构课程设计报告 - 1 - 课程设计目的课程设计目的 1、能够灵活地应用所学数据结构知识，根据加工数据对象的特征，选择适当的数据结构、存贮结构及 相应算法，独立完成问题分析，结合数据结构理论知识，编写程序求解指定问题。 2. 初步掌握各种算法在时间和空间的分析技巧；初步掌握软件开
2、发过程的问题分析、系统设计、程序 编码、测试等基本方法和技能； 3. 能够进行算法设计和程序设计，并且使所设计的程序结构清楚，正确易读，并上机调试通过；提高 综合运用所学的理论知识和方法独立分析和解决问题的能力。 4.用系统的观点和软件开发一般规范进行软件开发，巩固、深化学生的理论知识，提高编程水平，并在 此过程中培养他们严谨的科学态度和良好的工作作风。 5. 培养较强的实习和实践能力；较强的分析问题和解决问题的能力。 课程设计任务与要求：课程设计任务与要求： 问题描述问题描述 为了解决人们生活中经常遇到的表达式求值问题。免去人们复杂的计算，输入算式即得出结果。 基本要求基本要求 算式中无错误
3、，否则将程序会直接退出。输入中缀式可以输出前缀式和后缀式。 测试数据测试数据 1.2*2-2.1+5.12*3.1*(1+23)/2.4+3.32= 9.1212+121/21+49*20.13/(3*6.9)-2.12.1= 45-(12.65+12)/12+32*12= 实现提示实现提示 这个需要用栈，利用，其实用二叉树也可以做的出来。按照顺序把二叉树建立了，直接按照遍历的顺序 计算就行了。 一一 需求分析需求分析 1 1问题描述：问题描述： 在计算机中，算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同 的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进
4、行。因而在 程序 设计时，借助栈实现。 2 2实现功能：实现功能： 算法输入算法输入：表达式，由常量、变量、运算符和括号组成（以字符串形式输入） 。为了增加难度，我加入了 幂运算符，操作符为“+、-、*、/、” ，操作数为实数范围。 算法运行：算法运行：将输入的中缀表达式改为后缀表达式或者后缀式，并进行运算。 算法输出：算法输出：输出后缀表达式和表达式运算结果。 数据结构课程设计报告 - 2 - 二二 概要设计概要设计 总体分为两大块，一个是求值函数，一个是二叉树建立函数，二叉树建立之后就可以按照不 同的遍历顺序求出前缀式或者后缀式。 三三 详细设计详细设计 先说说求值部分，这个需要用到优先级
5、的比较，所以需要用到一个比较函数，返回运算符 的优先级。 数据结构课程设计报告 - 3 - 算法是分离数字和运算符，分别设立运算符栈和操作数栈。具体参见程序。 在变换式子形式的方法上需要用二叉树，所有有个结构体 typedef struct Tree double n; char c; char s20; Tree *leftchild,*rightchild; tree; 下面详细说这些成员的作用。 n 是存储字符串转换后的数。C 是存储操作符。S 数组是存储未转化成数字的字符 串，leftchild 和 rightchild 分别指向左孩子和右孩子。 四四 设计与调试分析设计与调试分析 程序分块设计，便于维护和调整。有五个主要的函数， （一）、double work(char *); 计算表达式的值。 （二）、tree* creat_tree(char *);根据字符串建立二叉树。 （三）、void visit(tree *);从根结点开始后序遍历。 （四）、void _visit(tree *);从根结点开始先序遍历。 （五）、double calculata(double num1,char op,double num2);计算。 五五 用户手册用户手册 注：注：任意输入一个数据后进入系统，然后根据系统提示操作即可。 六六 测试测试成果成果 1.2*2-2
