24李后浪课程设计报告

编号：B04900083课程设计学号：201240420224教学院计算机学院课程名称数据结构与算法课程设计题目算术表达式求值专业网络工程班级2012级网络工程2班姓名李后浪同组人员梅锟、刘小虎、丁兵武指导教师邓丹君2013年12月28日课程设计（论文）1课程设计任务书2013～2014学年第1学期学生姓名：李后浪专业班级：网络工程（2）班指导教师：邓丹君工作部门：计算机学院一、课程设计题目算术表达式求值二、课程设计内容输入一个算术表达式，其中操作数必须为实数，运算符包括加、减、乘、除、小（圆）括号，试编写程序实现：(1)生成表达式二叉树；(2)根据表达式二叉树求表达式的值；(3)先序遍历表达式二叉树；根据先序遍历序列（波兰式）求表达式的值；(4)中序遍历表达式二叉树，要求恢复必要的括号；(5)后序遍历表达式二叉树，根据后序遍历序列（逆波兰式）求表达式的值；三、进度安排1.系统设计，确定函数功能及其实现过程；2.根据前面的结果，编写程序清单，进行调试；3.经过反复的编译，调试，测试，程序运行成功；4.撰写课程设计报告，完成整个论文报告的工作，并打印；课题答辩。四、基本要求1．界面友好，函数功能要划分好2．总体设计应画一流程图3．程序要加必要的注释4．要提供程序测试方案5．程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的课程设计（论文）2目录目录.........................................................................................................2一概述.......................................................................................................3二总体方案设计.......................................................................................4三详细设计...............................................................................................5四程序的调试与运行结果说明..............................................................5五课程设计总结.....................................................................................30参考文献...................................................................................................32课程设计（论文）3一概述1.课程设计的目的1．理解和掌握该课程中的有关基本概念，程序设计思想和方法。2．培养综合运用所学知识独立完成课题的能力。3．培养勇于探索、严谨推理、实事求是、有错必改，用实践来检验理论，全方位考虑问题等科学技术人员应具有的素质。4．掌握从资料文献、科学实验中获得知识的能力，提高学生从别人经验中找到解决问题的新途径的悟性，初步培养工程意识和创新能力。2.课程设计的要求1）需要的基本知识与技能：入栈、出栈操作；二叉树的先序、中序、后序遍历；根据表达式求值；2）尚未掌握的知识点，需要查阅相关资料：（1）根据中缀表达式构造树；（2）根据算术表达式生成表达式二叉树；（3）根据波兰式求表达式的值；（4）根据逆波兰式求表达式的值；5）教师对本题目所提出的要求等。（1）．界面友好，函数功能要划分好；（2）．总体设计应画一流程图；（3）．程序要加必要的注释；（4）．要提供程序测试方案；（5）．程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。3．课程设计的内容输入一个算术表达式，其中操作数必须为实数，运算符包括加、减、乘、除、小（圆）括号，试编写程序实现：课程设计（论文）4(1)生成表达式二叉树；(2)根据表达式二叉树求表达式的值；(3)先序遍历表达式二叉树；根据先序遍历序列（波兰式）求表达式的值；(4)中序遍历表达式二叉树，要求恢复必要的括号；(5)后序遍历表达式二叉树，根据后序遍历序列（逆波兰式）求表达式的值；二总体方案设计（本次设计在具体设计过程中的整体设计思路，算法的整体思路、主要特点，具备功能。你所承担部分的设计工作，主要解决的关键性问题）1.整体设计思路：（1）输入一个算术表达式生成一颗二叉树；（2）根据这个表达式二叉树求表达式的值；（3）先序遍历表达式二叉树；根据先序遍历序列（波兰式）求表达式的值；（4）中序遍历表达式二叉树，要求恢复必要的括号；（5）后序遍历表达式二叉树，根据后序遍历序列（逆波兰式）求表达式的值。2.算法的整体思路：实现栈与树的结合，将字符入栈，设置两个栈，一个栈装操作数，一个装操作符。装操作树的栈设置一个函数判断操作符的优先级。设置结点类，结点类是操作符，且具有结点的左子树也是操作符，比较操作符的优先级再进行算术运算，求表达式的值。3.主要特点：栈与树结合，程序里包括结点、树类、栈。4.具备功能：（1）程序能够生成一颗表达式二叉树；（2）根据这个表达式二叉树求表达式的值。（3）先序遍历表达式二叉树；根据先序遍历序列（波兰式）求表达式的值；（4）中序遍历表达式二叉树，要求恢复必要的括号；（5）后序遍历表达式二叉树，根据后序遍历序列（逆波兰式）求表达式的值。5.我所承担部分的设计工作：生成表达式二叉树，根据先序遍历序列求表达式的值。6.主要解决的关键性问题：课程设计（论文）5根据一个算术表达式生成一颗二叉树，根据它的先序遍历序列求表达式的值三详细设计（所完成的具体功能及用到的算法（详细分析）。程序流程图主要部分的详细流程图）1.所完成的具体功能：输入一个算术表达式，能够求出它的值，并能够将其转化为二叉树，能够输出该二叉树的先序、中序、后序遍历序列。2.用到的算法：用到的算法有创建栈、创建二叉树、将操作符压入存放字符的栈、将操作数压入存放操作数的栈。创建一颗二叉树，先序、中序、后序遍历二叉树。通过调用函数求表达式二叉树的值。先序生成表达式二叉树、中序生成表达式二叉树、后序生成表达式二叉树。通过先序遍历序列计算表达式的值、通过中序遍历序列计算表达式的值、通过后序遍历序列计算表达式的值。3.程序流程图：四程序的调试与运行结果说明1.程序的调试：#includeiostream#includestack#includequeue#includestringmainIn2treeTobitreePre2treeIn2treeEvaluate课程设计（论文）6#includemath.husingnamespacestd;#includestdio.h//#includestring.h#includemalloc.h#includestdlib.h//#defineSTACK_INIT_SIZE100//#defineSTACKINCREMENT10#defineOK1#defineTRUE1#defineFALSE0#defineERROR0#defineOVER-2typedeffloatSElemtype;typedefintStatus;typedefstruct{SElemtype*base;SElemtype*top;intstacksize;}SqStack;StatusInitStack(SqStack&S){S.base=(SElemtype*)malloc(STACK_INIT_SIZE*sizeof(SElemtype));if(!S.base)exit(OVER);S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}intStackLength(SqStackS){returnS.top-S.base;课程设计（论文）7}StatusPush(SqStack&S,SElemtypee){*S.top++=e;returnOK;}StatusPop(SqStack&S,SElemtype&e){if(S.top==S.base)returnERROR;e=*--S.top;returnOK;}StatusIsDigital(charch){if(ch='0'&&ch='9'){return1;//是数字字母}return0;//不是数字字母}intEvalValue(char*ch,SqStack&S){inti=0;SElemtyperesult=0;chara;a=ch[i];课程设计（论文）8while(IsDigital(a)){result=10*result+(int)(a-48);a=ch[++i];}Push(S,result);returni;}voidEvalExpr(charch,SqStack&S){SElemtypeoper1,oper2;/*if(StackLength(S)2){printf(\n表达式错误\n);exit(0);}*/switch(ch){case'+':Pop(S,oper1);Pop(S,oper2);Push(S,oper1+oper2);break;case'-':Pop(S,oper1);Pop(S,oper2);Push(S,oper2-oper1);break;case'*':Pop(S,oper1);Pop(S,oper2);Push(S,oper1*oper2);break;case'/':课程设计（论文）9Pop(S,oper1);Pop(S,oper2);Push(S,oper2/oper1);break;/*case'%':oper1=Stack_Pop(pStk);oper2=Stack_Pop(pStk);Stack_Push(pStk,oper2%oper1);break;*//*default:printf(error);*/}}Statusevaluate(charch[],float&result){SqStackS;StatusSt;inti;i=0;St=InitStack(S);while(ch[i]!='#'&&i100){if(IsDigital(ch[i])){i+=EvalValue(&ch[i],S);}elseif(ch[i]=='')i++;else{课程设计（论文）10EvalExpr(ch[i],S);i++;}}if(StackLength(S)==1)Pop(S,result);else{//printf(表达式错误);//returnERROR;}returnOK;}//classTNode//节点类{public:charoper;//数据域，为简便起见，操作数用单个字符代替TNode*left;TNode*right;ints;intt;//计算树的层数使用TNode()//缺省构造函数{left=right=NULL;oper=0;}TNode(charop)//赋值构造函数{left=right=NULL;oper=op;}};#definemax100//课程设计（论文）11typedefstruct{char*data;inttop;intstacksize;}seqstack1;typedefstructTree{chardata1[max];floatdata2;structTree*lchild,*rchild;}*BiTree,Bnode;typedefstruct{BiTree*data;in