算术表达式与二叉树课程设计.docx

山西大学课程设计任务书设计题目 算术表达式与二叉树所属课程： 数据结构系 别 软件学院专 业 软件工程班 级 软工1408班姓 名 霍志斌指导教师 李雪梅 设计任务下达日期 2015年 12 月15 日设计时间2016年1月4日 至 2016年1月8日 目录：一、需求分析二、概要设计1、数据类型的声明：2、表达式的抽象数据类型定义3、整体设计三、详细设计1、二叉树的存储类型2、顺序栈的存储类型3、表达式的基本操作4、主程序和其他伪码算法5、函数的调用关系四、设计和调试分析五、测试六、课程设计的心得和心得以及问题 一、需求分析【课程设计要求】【问题的描述】 一个表达式和一棵二叉树之间，存在着自然的对应关系。写一个程序，实现基于二叉树表示的算术表达式expression的操作。【基本要求】 假设算术表达式expression内可以含有变量（a-z）,常量（0-9）和二元运算符（+，-，*，/，（乘幂）。实现以下操作： （1）readexpr(e)以字符序列的形式输入语法正确的前缀表达式并构造表达式e。 （2）writeexpr(e)用带括号的中缀表达式输出表达式e。 （3）assign(v，c)实现对变量v的赋值（v=c），变量的初值为0。 （4）value(e)对算术表达式e求值。 （5）compoundexpr(p,e1,e2)构造一个新的复合表达式（e1）p（e2）。【测试数据】1) 分别输入0；a;-91;+a*bc;+*5x2*8x;+*3*2x2x6并输出。2) 每当输入一个表达式后，对其中的变量赋值，然后对表达式求值。二、概要设计1、数据类型的声明：在这个课程设计中，采用了链表二叉树的存储结构，以及两个顺序栈的辅助存储结构/*头文件以及存储结构*/#include#include#include#include#define true 1#define false 0#define ok 1#define error 0#define overflow 0typedef int status;2、表达式的抽象数据类型定义adt expression数据对象d：d是具有数值的常量c和没有数值的变量v；数据关系：r=|v,cd, 表示由运算符p结合起来的表达式e基本操作：status input_expr(&string,flag)操作结果：以字符序列的形式输入语法正确的前缀表达式，保存到字符串string； 参数flag表示输出的提示信息是什么，输入成功返回ok，否则，返回error。void judge_value(&e,&string,i)初始条件：树e存在，表达式的前缀字符串string存在；操作结果：判断字符stringi，如果是0-9常量之间，二叉树结点e存为整型；否则，存为字符型。status readexpr(&e,&exprstring)初始条件：表达式的前缀形式字符串exprstring存在；操作结果：以正确的前缀表示式exprstring并构造表达式e，构造成功，返回ok，否则返回error。status pri_compare(c1,c2)初始条件：c1和c2是字符；操作结果：如果两个字符是运算符，比较两个运算符的优先级，c1比c2优先，返回ok，否则返回error。void writeexpr(&e)初始条件：表达式e存在；操作条件：用带括弧的中缀表达式输入表达式e。void assign(&e,v,c,&flag)初始条件：表达式e存在，flag为标志是否有赋值过；操作结果：实现对表达式e中的所有变量v的赋值(v=c)。long operate(opr1,opr,opr2)初始条件：操作数opr1和操作数opr2以及操作运算符opr;操作结果：运算符运算求值，参数opr1,opr2为常量，opr为运算符，根据不同的运算符，实现不同的运算，返回运算结果。status check(e)初始条件：表达式e存在；操作结果：检查表达式e是否还存在没有赋值的变量，以便求算数表达式e的值。long value(e)初始条件：表达式e存在；操作结果：对算术表达式求值，返回求到的结果。void compoundexpr(p,&e1,e2)初始条件：表达式e1和e2存在；操作条件：构造一个新的复合表达式(e1)p(e2)。status read_inorder_expr(&string,&pre_expr)操作结果：以表达式的原书写形式输入，表达式的原书写形式字符串string变为字符串pre_expr，后调用reversal_string()函数反转得到前缀表达式pre_expr。得到正确的前缀表达式返回ok，否则，返回error。void mergeconst(&e)操作结果：常数合并操作，合并表达式e中所有常数运算。adt expression3、整体设计在这个课程设计中，有两个源代码文件：expression.h和expression.c。在expression.h文件中，包含了各个存储结构的声明和辅助存储结构的两个栈的基本操作；在expression.c文件中，是实现课程设计要求的各个函数。一expression.h文件的整体结构1、各个存储结构的声明；2、两个除了栈名和栈存储的元素不一样的顺序栈的基本操作。其基本操作如下：对于栈sqstack:status initstack(sqstack *s)/* 构造一个空栈s */status stackempty(sqstack s)/* 若栈s为空栈，则返回true，否则返回false */status push(sqstack *s,selemtype e)/* 插入元素e为新的栈顶元素 */status pop(sqstack *s,selemtype *e) /* 若栈不空，则删除s的栈顶元素，用e返回其值，并返回ok；否则返回error */status gettop(sqstack s,selemtype *e) /* 若栈不空，则用e返回s的栈顶元素，并返回ok；否则返回error */对于栈sqstack1:status initstack1(sqstack1 *s)/* 构造一个空栈s */status stackempty1(sqstack1 s)/* 若栈s为空栈，则返回true，否则返回false */status push1(sqstack1 *s,selemtype1 e)/* 插入元素e为新的栈顶元素 */status pop1(sqstack1 *s,selemtype1 *e)/* 若栈不空，则删除s的栈顶元素，用e返回其值，并返回ok；否则返回error */status gettop1(sqstack1 s,selemtype1 *e) /* 若栈不空，则用e返回s的栈顶元素，并返回ok；否则返回error */顺序栈的基本操作的算法见程序清单。二expression.c文件的整体结构1、主程序模块的整体流程可以从主菜单函数可以明了的了解的程序的整体流程，主菜单函数menu()如下：char menu()char choice;printf(n*);printf(n 1 输入正确的前缀表达式);printf(n 2 带括弧的中缀表示式输出);printf(n 3 对变量进行赋值);printf(n 4 对算数表达式求值);printf(n 5 构造一个新的复合表达式);printf(n 6 以表达式的原书写形式输入);printf(n 7 合并表达式中所有常数运算);printf(n 0 退出);printf(n*);printf(n请输入你的选择);choice=getche();return choice;在主函数中，采用多分支程序设计语句switch()使程序产生不同的流向，从而达到实现课程设计的各个要求。void main()while(1)清屏；switch(主菜单)根据不同的选择，调用不同的操作函数，完成各个操作；2、本程序有四个模块，主程序模块，二叉树模块，两个顺序栈模块。四者的调用关系如下：主程序模块中的对于表达式的存储结构调用了二叉树模块，而在构造表达式的二叉树模块中又调用了顺序栈sqstack模块，主程序中在将原表达式形式输入表达式转换为前缀表达式操作中调用了顺序栈sqstack1模块。三、详细设计1、二叉树的存储类型/*二叉树结点类型*/typedef enumint,charelemtag;/*int为整型数据num，char为字符型数据c*/typedef struct telemtypeelemtag tag;/*int,char指示是整型还是字符型*/unionint num;/*tag=int时，为整型*/char c;/*tag=char时，为字符型*/; telemtype;/*二叉树的二叉链表存储表示 */typedef struct bitnode telemtype data; struct bitnode *lchild,*rchild; /* 左右孩子指针 */ bitnode,*bitree;二叉树的基本操作已经在构造表达式和表达式中的基本操作中根据不同的功能和实际情况修改了，详细见各个函数操作的算法设计。2、顺序栈的存储类型/*栈的顺序存储表示 */#define stack_init_size 10 /* 存储空间初始分配量 */#define stackincrement 2 /* 存储空间分配增量 */*两个顺序栈*/typedef struct sqstack selemtype *base; /* 在栈构造之前和销毁之后，base的值为null */ selemtype *top; /* 栈顶指针 */ int stacksize; /* 当前已分配的存储空间，以元素为单位 */ sqstack; /* 顺序栈sqstack */typedef struct sqstack1 selemtype1 *base; /* 在栈构造之前和销毁之后，base的值为null */ selemtype1 *top; /* 栈顶指针 */ int stacksize; /* 当前已分配的存储空间，以元素为单位 */ sqstack1; /* 顺序栈sqstack1 */相关的基本操作见上面的“expression.h文件的整体结构”的说明，详细的算法设计见附录的程序清单。3、表达式的基本操作status input_expr(char *string,int flag);/*以字符序列的形式输入语法正确的前缀表达式，保存到字符串string*/*参数flag=0表示输出的提示信息是请输入正确的前缀表示式：*/*flag=1表示输出的提示信息为请以表达式的原书写形式输入正确表示式：*/void judge_value(bitree *e,char *string,int i);/*判断字符stringi，如果是0-9常量之间，二叉树结点存为整型；否则，存为字符型*/status readexpr(bitree *e,char *exprstring);/*以正确的前缀表示式并构造表达式e*/status pri_compare(char c1,char c2);/*如果两个字符是运算符，比较两个运算符的优先级，c1比c2优先，返回ok，否则返回error*/void writeexpr(bitree e);/*用带括弧的中缀表达式输入表达式*/void assign(bitree *e,char v,int c,int *flag);/*实现对表达式中的所有变量v的赋值(v=c)，参数flag为表示是否赋值过的标志*/long operate(int opr1,char opr,int opr2);/*运算符运算求值，参数opr1,opr2为常量，opr为运算符，根据不同的运算符，实现不同的运算，返回运算结果*/status check(bitree e);/*检查表达式是否还存在没有赋值的变量，以便求算数表达式的值*/long value(bitree e);/*对算术表达式求值*/void compoundexpr(char p,bitree *e1,bitree e2);/*构造一个新的复合表达式*/status read_inorder_expr(char *string,char *pre_expr);/*以表达式的原书写形式输入，表达式的原书写形式字符串string变为字符串pre_expr，后调用reversal_string()函数反转得到前缀表达式pre_expr*/void mergeconst(bitree *e);/*常数合并操作函数，合并表达式e中所有常数运算*/下面列出部分基本操作的伪码算法，未列出的请见程序清单。其中部分基本操作的伪码算法如下： status readexpr(bitree *e,char *exprstring)/*以正确的前缀表示式并构造表达式e*/申请根结点空间(*e)=(bitree)malloc(sizeof(bitnode);并且左右孩子指针置空；表达式只有一个字符，二叉树只有根结点；否则judge_value(e,exprstring,0);将exprstring0存入二叉树的结点中initstack(&s);/*初始化栈*/push(&s,q); push(&s,q);入栈，根结点入栈两次是为判断先序输入的表达式是不是正确的表达式for(i=1;i=len判断输入的表达式是正确的；正确返回ok，错误返回error;void writeexpr(bitree e)/*用带括弧的中缀表达式输入表达式*/if(e)/*树不为空*/先递归左子树; writeexpr(e-lchild);其中要考虑何时带括弧输出：if(pri_compare(e-data.c,e-lchild-data.c)e-data.c比e-lchild-data.c优先,带括弧输出左子树;访问输出根结点的值;后递归右子树; writeexpr(e-lchild);其中要考虑何时带括弧输出：if(pri_compare(e-data.c,e-lchild-data.c)e-data.c比e-lchild-data.c优先,带括弧输出右子树;oid assign(bitree *e,char v,int c,int *flag)/*实现对表达式中的所有变量v的赋值(v=c)，参数flag为表示是否赋值过的标志*/if(*e)/*树不空*/if(*e)-data.tag=char&(*e)-data.c=v)如果找到要赋值的变量，赋值；*flag=1;assign(&(*e)-lchild),v,c,flag);/*递归左子树*/assign(&(*e)-rchild),v,c,flag);/*递归左子树*/long operate(int opr1,char opr,int opr2)/*运算符运算求值，参数opr1,opr2为常量，opr为运算符，根据不同的运算符，实现不同的运算，返回运算结果*/switch(opr)根据不同的运算符，进入不同分支求出result；后返回result;status check(bitree e)/*检查表达式是否还存在没有赋值的变量，以便求算数表达式的值*/if(e&e-data.tag=char)/*树不为空*/如果找到没有赋值的变量，返回error；if(check(e-lchild)/*递归左子树*/check(e-rchild);/*递归右子树*/long value(bitree e);/*对算术表达式求值*/if(e)/*树不为空*/如果是叶子结点，返回叶子的结点的值；return operate(value(e-lchild),e-data.c,value(e-rchild);后根遍历的次序对表达式求值；void compoundexpr(char p,bitree *e1,bitree e2);/*构造一个新的复合表达式*/e=(bitree)malloc(sizeof(bitnode);/*申请一个结点存放运算符p*/e-lchild=(*e1);/*结点的左孩子为e1*/e-rchild=e2;/*结点的右孩子为e2*/(*e1)=e;/*(*e1)为根结点*/status read_inorder_expr(char *string,char *pre_expr);/*以表达式的原书写形式输入，表达式的原书写形式字符串string变为字符串pre_expr，后调用reversal_string()函数反转得到前缀表达式pre_expr*/initstack1(&s);/*初始栈*/c=stringlen-1;从字符串的最后一个字符开始向前扫描, len=strlen(string);while(!stackempty1(s)&i=0)/*栈不为空且i大于等于0*/if(c=()字符为(, pop1(&s,&c);while(c!=)假如c不为),出栈;else if(c=)字符为)，入栈, push1(&s,c);else if(c=0&c=a&c=a&clchild&(*e)-rchild)左右孩子不为空if(*e)-lchild-data.tag=int&(*e)-rchild-data.tag=int)假如左右孩子为常量，合并,并且删除常量的结点；else mergeconst(&(*e)-lchild);/*递归左孩子*/mergeconst(&(*e)-rchild);/*递归右孩子*/4、主程序和其他伪码算法void main()while(1)switch(menu()case 1:/*输入正确的前缀表达式*/if(input_expr(expr_string,0)输入正确的前缀表达式if(readexpr(&e,expr_string)构造表达式flag=1;printf(n表达式构造成功！);case 2:/*带括弧的中缀表示式输出*/if(flag=1) writeexpr(e);else printf(n表达式未构造成功！请构造成功的表达式！);case 3:/*对变量进行赋值*/if(flag=1)flushall();/*清理缓冲区*/v=getchar();scanf(&c);assign(&e,v,c,&assign_flag);else printf(n表达式未构造成功！请构造成功的表达式！);case 4:/*对算数表达式求值*/if(flag=1)if(check(e) result=value(e); writeexpr(e);printf(result);else printf(n表达式未构造成功！请构造成功的表达式！);case 5:/*构造一个新的复合表达式*/if(flag=1)flushall();/*清理缓冲区*/if(input_expr(string,1) if(read_inorder_expr(string,expr_string)/*按原表达式形式输入*/reversal_string(expr_string);if(readexpr(&e1,expr_string)flag=1;p=getchar();compoundexpr(p,&e,e1);else printf(n复合新的表达式失败！请按任意键返回主菜单！);5、函数的调用关系除了主函数main()外，其他各个函数相对于其它函数来说是独立的，函数的使用都由主函数main()调用使用的，可以简单的说，各个函数都是主函数下的从函数。四、设计和调试分析1、在起初设计上，针对前缀表达式的要求构造表达式e，常量的范围限定在0-9之间，后在这个构造表达式的架构上逐个逐个实现对表达式上的操作；后扩展到以表达式的原书写形式输入，整体架构是不变的，只是增加一些细节的处理功能。这样的设计从开始到最后都处于可扩展的模块化设计。2、在算法设计中，构造表达式树的时候，本来以为使用递归构造表达式会很难做到出错处理的，所以采用了顺序栈辅助构造方法，并且尽可能地对程序进行完善，出错处理。但是经过与同学的相互讨论和研究，发现自己的想法犯了很大的错误，递归构造表达式对于出错处理很简单也很完善，这一点让我加深了递归的使用和理解。3、在对各个功能操作的实现上，时间复杂度大多数是o(n)，空间上增加了辅助栈，空间复杂度为o(n+s)。而在以原表达式形式输入操作上，实际上是对字符串的操作，将一串原表达式字符串处理为前缀表达式