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

1、山西大学课程设计任务书设计题目 算术表达式与二叉树所属课程：数据结构系别 软件学院专业 软件工程班级 软工1408班姓名 霍志斌指导教师 李雪梅设计任务下达日期 2015年12月15日设计时间2016年1月4日至2016年1月8日目录：、需求分析、概要设计1、数据类型的声明：2、表达式的抽象数据类型定义3、整体设计三、详细设计1、二叉树的存储类型2、顺序栈的存储类型3、表达式的基本操作4、主程序和其他伪码算法5、函数的调用关系四、设计和调试分析五、测试六、课程设计的心得和心得以及问题一、需求分析【课程设计要求】【问题的描述】一个表达式和一棵二叉树之间， 存在着自然的对应关系。 写一个程序， 实

2、现 基于二叉树表示的算术表达式 Expression 的操作。【基本要求】假设算术表达式 Expression 内可以含有变量（ a-z ）, 常量（ 0-9 ）和二元 运算符（+, -, *, /, A （乘幕）。实现以下操作：（ 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)构造一个新的复合表达式(

3、 E1) p ( E2)。【测试数据】1) 分别输入 0; a;-91;+a*bc;+*5x2*8x;+*3A*2Ax2x6并输出。2) 每当输入一个表达式后,对其中的变量赋值,然后对表达式求值。二、概要设计1、数据类型的声明：在这个课程设计中, 采用了链表二叉树的存储结构, 以及两个顺序栈的辅助 存储结构/* 头文件以及存储结构 */#include #include #include #include #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW 0 typedef int Stat

4、us;2、表达式的抽象数据类型定义ADT Expression 数据对象D: D是具有数值的常量 C和没有数值的变量 V;数据关系：R=|V,C D, 表示由运算 符 P 结合起来的表达式 E基本操作：Status Input_Expr(&string,flag)操作结果： 以字符序列的形式输入语法正确的前缀表达式, 保存到字符串 string ; 参数flag表示输出的提示信息是什么，输入成功返回 OK否则，返回ERROR void judge_value(&E,&string,i)初始条件：树 E 存在，表达式的前缀字符串 string 存在;操作结果：判断字符 stringi，如果是0-

5、9 常量之间，二叉树结点 E存为整 型;否则，存为字符型。Status ReadExpr(&E,&exprstring) 初始条件：表达式的前缀形式字符串 exprstring 存在; 操作结果：以正确的前缀表示式 exprstring 并构造表达式 E,构造成功，返回OK, 否则返回ERRORStatus Pri_Compare(c1,c2)c1 比 c2 优先，初始条件： c1 和 c2 是字符； 操作结果：如果两个字符是运算符，比较两个运算符的优先级， 返回OK否则返回ERRORvoid WriteExpr(&E) 初始条件：表达式E 存在；操作条件：用带括弧的中缀表达式输入表达式E。v

6、oid 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 存

7、在；操作结果：对算术表达式求值，返回求到的结果。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否则，返回ERRORvoid MergeConst(&E) 操作结果：常数合并操作，合

8、并表达式 E 中所有常数运算。ADT Expression3、整体设计在这个课程设计中，有两个源代码文件： expression.h 和 expression.c 。在 expression.h 文件中，包含了各个存储结构的声明和辅助存储结构的两个栈的基本 操作；在 expression.c 文件中，是实现课程设计要求的各个函数。一 expression.h 文件的整体结构1、各个存储结构的声明；2、两个除了栈名和栈存储的元素不一样的顺序栈的基本操作。其基本操作如下：对于栈 SqStack:Status InitStack(SqStack *S)/*Status StackEmpty(SqSt

9、ack S)/*Status Push(SqStack *S,SElemType e) /* Status Pop(SqStack *S,SElemType *e) /*构造一个空栈 S */若栈S为空栈，则返回 TRUE否则返回FALSE */ 插入元素 e 为新的栈顶元素 */若栈不空，则删除 S的栈顶元素，用e返回其值，并返回OK否则返回ERROR */Status GetTop(SqStack S,SElemType *e) /* 回0K否则返回ERROR */对于栈 SqStack1:Status InitStack1(SqStack1 *S)Status StackEmpty1(S

10、qStack1 S)若栈不空，则用 e 返回 S 的栈顶元素，并返/* 构造一个空栈 S */ /* 若栈Status Push1(SqStack1 *S,SElemType1 e)Status Pop1(SqStack1 *S,SElemType1 *e)回其值，并返回 OK否则返回ERROR */Status GetTop1(SqStack1 S,SElemType1 *e) /* 返回OK否则返回ERROR */顺序栈的基本操作的算法见程序清单。S为空栈，则返回 TRUE否则返回FALSE */ 插入元素 e 为新的栈顶元素 */ 若栈不空，则删除 S 的栈顶元素，用 e 返/*/*若栈

11、不空，则用 e 返回 S 的栈顶元素，并二 expression.c 文件的整体结构1、主程序模块的整体流程menu() 如下：可以从主菜单函数可以明了的了解的程序的整体流程，主菜单函数 char menu()printf(n1 输入正确的前缀表达式 );printf(n2 带括弧的中缀表示式输出 );printf(n3 对变量进行赋值 );printf(n4 对算数表达式求值 );printf(n5 构造一个新的复合表达式 );printf(n6 以表达式的原书写形式输入 printf(n7 合并表达式中所有常数运算 printf(n0 退出);); );char choice;printf

12、(n*);printf(n*);printf(n 请输入你的选择 ); choice=getche();return choice; 在主函数中，采用多分支程序设计语句 switch() 使程序产生不同的流向，从而达到实 现课程设计的各个要求。void main()while(1)清屏；switch( 主菜单 )根据不同的选择，调用不同的操作函数，完成各个操作；2、本程序有四个模块，主程序模块，二叉树模块，两个顺序栈模块。四者的调用关系如下:主程序模块中的对于表达式的存储结构调用了二叉树模块，而在构造表达式的二叉树模块中又调用了顺序栈 SqStack模块，主程序中在将原表达式形式输入表达式转换

13、为前缀表达 式操作中调用了顺序栈 SqStackl模块。三、详细设计1、二叉树的存储类型/*二叉树结点类型*/typedef enumINT,CHARElemTag;/*INT为整型数据 num, CHAF为字符型数据 c*/typedef struct TElemTypeElemTag tag;/*INT,CHAR 指示是整型还是字符型 */unionint num;/*tag=INT 时，为整型 */char c;/*tag=CHAR时，为字符型 */; TElemType;/*二叉树的二叉链表存储表示*/typedef struct BiTNodeTElemType data;struc

14、t BiTNode *lchild,*rchild; /*左右孩子指针 */BiTNode,*BiTree;二叉树的基本操作已经在构造表达式和表达式中的基本操作中根据不同的功能和实际 情况修改了，详细见各个函数操作的算法设计。2、顺序栈的存储类型 /* 栈的顺序存储表示 */ #define STACK_INIT_SIZE 10 /* #define STACKINCREMENT 2 /* /* 两个顺序栈 */ typedef struct SqStackSElemType *base; /* SElemType *top; /* int stacksize; /* SqStack; /*顺

15、序栈typedef struct SqStack1 SElemType1 *base; /* SElemType1 *top; /* int stacksize; /* SqStack1; /* 顺序栈 相关的基本操作见上面的“ 见附录的程序清单。存储空间初始分配量 */ 存储空间分配增量 */在栈构造之前和销毁之后， base 的值为 NULL */ 栈顶指针 */ 当前已分配的存储空间，以元素为单位 SqStack */*/在栈构造之前和销毁之后， base栈顶指针 */ 当前已分配的存储空间，以元素为单位 SqStack1 */的值为 NULL */*/expression.h 文件的整

16、体结构”的说明，详细的算法设计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(

17、BiTree *E,char *exprstring);/* 以正确的前缀表示式并构造表达式 E*/Status Pri_Compare(char c1,char c2);/*如果两个字符是运算符，比较两个运算符的优先级，cl比c2优先，返回0K否则返回 ERROR*/void WriteExpr(BiTree E);/* 用带括弧的中缀表达式输入表达式 */void Assign(BiTree *E,char V,int c,int *flag);/*实现对表达式中的所有变量 V的赋值(V=c)，参数flag为表示是否赋值过的标志*/long 0perate(int opr1,char op

18、r,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 变为字符串

19、/* 以表达式的原书写形式输入，表达式的原书写形式字符串pre_expr ，后调用 reversal_string() 函数反转得到前缀表达式 pre_expr*/ void MergeConst(BiTree *E);/* 常数合并操作函数，合并表达式E 中所有常数运算 */下面列出部分基本操作的伪码算法，未列出的请见程序清单。 其中部分基本操作的伪码算法如下：Status ReadExpr(BiTree *E,char *exprstring)/* 以正确的前缀表示式并构造表达式 E*/ 申请根结点空间 (*E)=(BiTree)malloc(sizeof(BiTNode); 并且左右孩子

20、指针置空； 表达式只有一个字符，二叉树只有根结点；否则 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); 其中要

21、考虑何时带括弧输出：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) ，参数

22、 flag 为表示是否赋值过的标志 */ if(*E)/* 树不空 */if(*E)-data.tag=CHAR&(*E)-data.c=V) 如果找到要赋值的变量，赋值；Assign(&(*E)-lchild),V,c,flag);/*Assign(&(*E)-rchild),V,c,flag);/*long Operate(int opr1,char opr,int opr2)/* 运算符运算求值，参数 opr1,opr2 为常量，同的运算，返回运算结果 */switch(opr)根据不同的运算符，进入不同分支求出后返回 result;*flag=1;递归左子树 */ 递归左子树 */op

23、r 为运算符，根据不同的运算符，实现不result ；Status Check(BiTree E)/* 检查表达式是否还存在没有赋值的变量，以便求算数表达式的值 */ if(E&E-data.tag=CHAR)/* 树不为空 */ 如果找到没有赋值的变量，返回ERRO；Rif(Check(E-lchild)/* 递归左子树 */Check(E-rchild);/* 递归右子树 */long Value(BiTree E);/* 对算术表达式求值 */ if(E)/* 树不为空 */ 如果是叶子结点，返回叶子的结点的值；return Operate(Value(E-lchild),E-data.

24、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);_expr ，/* 以表达式的原书写

25、形式输入， 表达式的原书写形式字符串 string 变为字符串 后调用 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=

26、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(

27、&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(fla

28、g=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=

29、getchar();CompoundExpr(P,&E,E1);else printf(n 复合新的表达式失败！请按任意键返 回主菜单！ ); 5、函数的调用关系除了主函数 main() 外，其他各个函数相对于其它函数来说是独立的，函数的使用都由 主函数 main() 调用使用的，可以简单的说，各个函数都是主函数下的从函数。四、设计和调试分析1、 在起初设计上，针对前缀表达式的要求构造表达式 E,常量的范围限定在 0-9之间， 后在这个构造表达式的架构上逐个逐个实现对表达式上的操作； 后扩展到以表达式的原书写 形式输入， 整体架构是不变的， 只是增加一些细节的处理功能。 这样的设计从开始到最后

30、都 处于可扩展的模块化设计。2、在算法设计中，构造表达式树的时候，本来以为使用递归构造表达式会很难做到出 错处理的， 所以采用了顺序栈辅助构造方法， 并且尽可能地对程序进行完善，出错处理。但 是经过与同学的相互讨论和研究， 发现自己的想法犯了很大的错误， 递归构造表达式对于出 错处理很简单也很完善，这一点让我加深了递归的使用和理解。3、 在对各个功能操作的实现上，时间复杂度大多数是O(n) ，空间上增加了辅助栈，空 间复杂度为 O(n+s) 。而在以原表达式形式输入操作上，实际上是对字符串的操作，将一串 原表达式字符串处理为前缀表达式字符串而已， 算法时间复杂度取决于输入的字符串的长度 n,即

31、0(n)，空间复杂度为 0(2n+s)。整体的算法设计没有什么可取之处，对于减少时间复 杂度和空间复杂度上没有什么细细考虑。4、在调试的过程中,花费时间最为多的是对输入错误表达式的出错处理,更改增加的 代码几乎都是为了出错处理, 但是, 觉得这样的调试才更能锻炼一个人的编程能力。 课程设 计注重的不单单只是基本程序的完成,更多注重的是出错处理和界面的美化！五. 测试一选择 1进入测试输入正确的前缀表达式操作1、输入的前缀表达式为一个不大于9 常量： 8口存人第冲X.杏则口I能矣出普!的印壕表卿勺前窒表密滾 irMKrt-MMSCMHMM 具:1 82 43 4 4为C小瑙造二个新的复苔克达式0

32、退出JIMMLJmKMKMHJIMKKJWKJKKJMJCJCXKWKJCJCMKXiKJIKJgKMJtJOC情输入你的选择 1_W N逋:M梵貝牺胃梵JL梵K : X耳剋岸馭X垃耳從耳就刖/ 扌呈信昌魁基且疋耳算且光溥XJ疑矗梵嬴弼轉弭蕈耳梵屛 输入正确页前缓寒达式的要扎一【变量】a-z A-E f不能輕雹 i諭人IE洛譎礙达和語肆耳 N 沌梵KiflC 怔 JaXlElfifiMXMEXliKJtXJtlCJriOE 英 M 减）：； H 梵：梵 MT 弭 JE E 弭 H 梵 K JX 耳 K ME 靑输入正确的前缀表示式.#2 、输入前缀表达式为一个变量： Z【常昼】中墻表达式SS达式:达式，片按回律旳翊一 u蔻示式输岀IJAI3请输入正砺的刖请输入正确的前壌表示式.土Er Er JTTt PffKJTH JTT* ”!珂itK氧Jt JT耗.*TH* 请输入你的选择”R1输人正确的煎缪妾达式簪轧【艮量】卫-工或p-2： a 9,不能起边犍仔入須中区，