黄淮学院
“数据结构”课程设计
报告
系 （院）： 信息工程学院 设计题目： 表达式求值 专业班级： 计算机科学与技术1301B 小组成员：
指导教师： 完成时间： 2014~2015学年第二学期 数据结构课程设计报告
课程设计目的 1、能够灵活地应用所学数据结构知识，根据加工数据对象的特征，选择适当的数据结构、存贮结构及相应算法，独立完成问题分析，结合数据结构理论知识，编写程序求解指定问题。 2. 初步掌握各种算法在时间和空间的分析技巧；初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 3. 能够进行算法设计和程序设计，并且使所设计的程序结构清楚，正确易读，并上机调试通过；提高综合运用所学的理论知识和方法独立分析和解决问题的能力。 4.用系统的观点和软件开发一般规范进行软件开发，巩固、深化学生的理论知识，提高编程水平，并在此过程中培养他们严谨的科学态度和良好的工作作风。 5. 培养较强的实习和实践能力；较强的分析问题和解决问题的能力。 - 1 -
数据结构课程设计报告
课程设计任务与要求： [问题描述] 为了解决人们生活中经常遇到的表达式求值问题。免去人们复杂的计算，输入算式即得出结果。 [基本要求] 算式中无错误，否则将程序会直接退出。输入中缀式可以输出前缀式和后缀式。 [测试数据] 1.2*2-2.1+5.12*3.1*(1+23)/2.4+3.3^2= 9.1212+121/21+49*20.13/(3*6.9)-2.1^2.1= 4^5-(12.65+12)/12+32*12= [实现提示] 这个需要用栈，利用，其实用二叉树也可以做的出来。按照顺序把二叉树建立了，直接按照遍历的顺序计算就行了。 一 需求分析 1．问题描述： 在计算机中，算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同 的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进行。因而在程序 设计时，借助栈实现。 2．实现功能： 算法输入：表达式，由常量、变量、运算符和括号组成（以字符串形式输入）。为了增加难度，我加入了幂运算符，操作符为“+、-、*、/、^”，操作数为实数范围。 算法运行：将输入的中缀表达式改为后缀表达式或者后缀式，并进行运算。 算法输出：输出后缀表达式和表达式运算结果。 二 概要设计 - 2 -
数据结构课程设计报告
总体分为两大块，一个是求值函数，一个是二叉树建立函数，二叉树建立之后就可以按照不同的遍历顺序求出前缀式或者后缀式。 三 详细设计 先说说求值部分，这个需要用到优先级的比较，所以需要用到一个比较函数，返回运算符的优先级。 算法是分离数字和运算符，分别设立运算符栈和操作数栈。具体参见程序。 - 3 -
数据结构课程设计报告
在变换式子形式的方法上需要用二叉树，所有有个结构体 typedef struct Tree { double n; char c; char s[20]; 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.1+5.12*3.1*(1+23)/2.4+3.3^2= - 4 -
数据结构课程设计报告
- 5 -
数据结构课程设计报告
输入前缀 输入前缀和后缀 - 6 -
数据结构课程设计报告
更换表达式 - 7 -
数据结构课程设计报告
七 附录（源程序清单） #include 数据结构课程设计报告 void clear(){ s_top=0; } bool empty(){ return s_top==0; } int size(){ return s_top; } void printstack(){ int i; for(i=1;i<=s_top;i++) cout< printf(\"请输入中缀表达式(式子以\\\"=\\\"结束):\");scanf(\"%s\ do{ printf(\"\\n+++++++++++++++请选择你的操作++++++++++++\\n\"); printf(\"1、表达式求值\2、输出前缀式\3、输出后缀式\\n\"); printf(\"4、更换表达式\5、清屏\\6、退出\\n\\n\\n请输入你的选择:\"); scanf(\"%d\ switch(n) { case 1:printf(\"\\n\\n%s%.2lf\ case 2:printf(\"前缀式是: \");_visit(creat_tree(s));printf(\"=\\n\");break; case 3:printf(\"后缀式是: \");visit(creat_tree(s));printf(\"=\\n\");break; case 4:printf(\"请输入中缀表达式(式子以\\\"=\\\"结束):\");scanf(\"%s\ case 5:system(\"cls\");break; case 6:printf(\"确定要退出？(1/0):\");scanf(\"%d\exit(0); else break; } }while(1); return 0; } mystack 数据结构课程设计报告 tree *build(char ch) { tree *root=new tree; root->c=ch; root->liftchild=NULL; root->rightchild=NULL; return root; } void visit(tree * r) { if(r!=NULL) { visit(r->liftchild); visit(r->rightchild); if(r->liftchild==NULL && r->rightchild==NULL) { printf(\"%s \叶节点必定是数字 else { printf(\"%c \r->n=calculate(r->liftchild->n,r->c,r->rightchild->n);}//遍历的时候计算。 } } void _visit(tree * r) { if(r!=NULL) { if(r->liftchild==NULL && r->rightchild==NULL) printf(\"%s \ else printf(\"%c \ _visit(r->liftchild); _visit(r->rightchild); } } - 11 - 数据结构课程设计报告 tree* creat_tree(char *s) { tree *Root; int i,j; char w[20]; for(i=0;s[i]!='=';) { if(s[i]>='0' && s[i]<='9') { j=0; while((s[i]>='0' && s[i]<='9') || s[i]=='.') { w[j++]=s[i++]; } w[j]='\\0'; //printf(\"[%lf]\ ovs1.push(_build(w)); } else { if(ops1.empty() || s[i]=='(' || comp(ops1.top()->c) 数据结构课程设计报告 } while(ovs1.size()!=1) { ops1.top()->rightchild=ovs1.top();ovs1.pop(); ops1.top()->liftchild=ovs1.top();ovs1.pop(); Root=ops1.top();ops1.pop(); ovs1.push(Root); } Root=ovs1.top(); ovs1.clear(); ops1.clear(); return Root; } mystack 数据结构课程设计报告 w[j]='\\0'; printf(\"%s\\n\ ovs.push(atof(w)); } else//运算符 { if(s[i]=='(' || comp(ops.top()) } while(ovs.size()!=1)//最后只剩下同级运算 { printf(\"当前处理:\"); num2=ovs.top(); ovs.pop(); num1=ovs.top(); ovs.pop(); op=ops.top(); ops.pop(); //printf(\"%lf%c%lf\\n\ cout< case '#':t=0;break; default :printf(\"%c_error!\\n\ } return t; } double calculate(double num1,char op,double num2) { double ans; switch(op) { case '^':ans=pow(num1,num2);break; case '*':ans=num1*num2;break; case '/':ans=num1/num2;break; case '+':ans=num1+num2;break; case '-':ans=num1-num2;break; default :printf(\"%c_error!\\n\ } return ans; } 八.课程设计心得 经过了这次的课题设计，我们熟练掌握了数据结构的相关知识，将有关数据结构的相关知识融为了一体，使用更加灵活。与此同时，在课程设计的过程中，我们也进一步学会了团队协作。 - 16 - 因篇幅问题不能全部显示，请点此查看更多更全内容