数据结构课程设计报告

--1一、需求分析【课程设计要求】【问题的描述】一个表达式和一棵二叉树之间，存在着自然的对应关系。写一个程序，实现基于二叉树表示的算术表达式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的正整数常量；（2）增加常数合并操作MergeConst(E)——合并表达式E中所有常数运算。例如，对表达式E=(2+3-a)*(b+3*4)进行合并常数的操作后，求得E=(5-a)*(b+12)(3)增加对求偏导数的运算Diff（E，V）——求表达式E对V的导数(4)在表达式内增加对三角函数等初等函数的操作。【测试数据】(1)分别输入0；a;-91;+a*bc;+*5x2*8x;+++*3^*2^x2x6并输出。（2）每当输入一个表达式后，对其中的变量赋值，然后对表达式求值二、【整体算法思想】一个表达式和一棵二叉树之间存在一一对应的关系。本程序我主要用前缀表达式建树，中序遍历并适当加括号实现中缀输出。具体操作即对树的程序进行处理，再输出。三、【概要设计】1、数据类型的声明：在这个课程设计中，采用了链表二叉树的存储结构，以及两个顺序栈的辅助存储结构/*头文件以及存储结构*/#includestdio.h--2#includeconio.h#includestdlib.h#includestring.h#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineOVERFLOW0typedefintStatus;2、表达式的抽象数据类型定义ADTExpression{数据对象D：D是具有数值的常量C和没有数值的变量V；数据关系：R={(V或者C)P(V或者C)|V,C∈D,(V或者C)P(V或者C)表示由运算符P结合起来的表达式E}基本操作：StatusInput_Expr(&string,flag)操作结果：以字符序列的形式输入语法正确的前缀表达式，保存到字符串string；参数flag表示输出的提示信息是什么，输入成功返回OK，否则，返回ERROR。voidjudge_value(&E,&string,i)初始条件：树E存在，表达式的前缀字符串string存在；操作结果：判断字符string[i]，如果是'0'-'9'常量之间，二叉树结点E存为整型；否则，存为字符型。StatusReadExpr(&E,&exprstring)初始条件：表达式的前缀形式字符串exprstring存在；操作结果：以正确的前缀表示式exprstring并构造表达式E，构造成功，返回OK，否则返回ERROR。StatusPri_Compare(c1,c2)初始条件：c1和c2是字符；操作结果：如果两个字符是运算符，比较两个运算符的优先级，c1比c2优先，返回OK，否则返回ERROR。voidWriteExpr(&E)初始条件：表达式E存在；操作条件：用带括弧的中缀表达式输入表达式E。voidAssign(&E,V,c,&flag)初始条件：表达式E存在，flag为标志是否有赋值过；操作结果：实现对表达式E中的所有变量V的赋值(V=c)。longOperate(opr1,opr,opr2)初始条件：操作数opr1和操作数opr2以及操作运算符opr;操作结果：运算符运算求值，参数opr1,opr2为常量，opr为运算符，根据不同的运算符，实现不同的运算，返回运算结果。StatusCheck(E)初始条件：表达式E存在；--3操作结果：检查表达式E是否还存在没有赋值的变量，以便求算数表达式E的值。longValue(E)初始条件：表达式E存在；操作结果：对算术表达式求值，返回求到的结果。voidCompoundExpr(P,&E1,E2)初始条件：表达式E1和E2存在；操作条件：构造一个新的复合表达式(E1)P(E2)。StatusRead_Inorder_Expr(&string,&pre_expr)操作结果：以表达式的原书写形式输入，表达式的原书写形式字符串string变为字符串pre_expr，后调用reversal_string()函数反转得到前缀表达式pre_expr。得到正确的前缀表达式返回OK，否则，返回ERROR。voidMergeConst(&E)操作结果：常数合并操作，合并表达式E中所有常数运算。}ADTExpression3、整体设计在这个课程设计中，有两个源代码文件：expression.h和expression.c。在expression.h文件中，包含了各个存储结构的声明和辅助存储结构的两个栈的基本操作；在expression.c文件中，是实现课程设计要求的各个函数。《一》expression.h文件的整体结构1、各个存储结构的声明；2、两个除了栈名和栈存储的元素不一样的顺序栈的基本操作。其基本操作如下：对于栈SqStack:StatusInitStack(SqStack*S)/*构造一个空栈S*/StatusStackEmpty(SqStackS)/*若栈S为空栈，则返回TRUE，否则返回FALSE*/StatusPush(SqStack*S,SElemTypee)/*插入元素e为新的栈顶元素*/StatusPop(SqStack*S,SElemType*e)/*若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR*/StatusGetTop(SqStackS,SElemType*e)/*若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR*/对于栈SqStack1:StatusInitStack1(SqStack1*S)/*构造一个空栈S*/StatusStackEmpty1(SqStack1S)/*若栈S为空栈，则返回TRUE，否则返回FALSE*/StatusPush1(SqStack1*S,SElemType1e)/*插入元素e为新的栈顶元素*/StatusPop1(SqStack1*S,SElemType1*e)/*若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR*/StatusGetTop1(SqStack1S,SElemType1*e)/*若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR*/顺序栈的基本操作的算法见程序清单。《二》expression.c文件的整体结构1、主程序模块的整体流程可以从主菜单函数可以明了的了解的程序的整体流程，主菜单函数menu()如下：--4charmenu(){charchoice;printf(\n****************************************);printf(\n1输入正确的前缀表达式);printf(\n2带括弧的中缀表示式输出);printf(\n3对变量进行赋值);printf(\n4对算数表达式求值);printf(\n5构造一个新的复合表达式);printf(\n6以表达式的原书写形式输入);printf(\n7合并表达式中所有常数运算);printf(\n0退出);printf(\n****************************************);printf(\n请输入你的选择);choice=getche();returnchoice;}在主函数中，采用多分支程序设计语句switch()使程序产生不同的流向，从而达到实现课程设计的各个要求。voidmain(){while(1){清屏；switch(主菜单){根据不同的选择，调用不同的操作函数，完成各个操作；}}}2、本程序有四个模块，主程序模块，二叉树模块，两个顺序栈模块。四者的调用关系如下：主程序模块二叉树模块顺序栈SqStack模块顺序栈SqStack1模块--5主程序模块中的对于表达式的存储结构调用了二叉树模块，而在构造表达式的二叉树模块中又调用了顺序栈SqStack模块，主程序中在将原表达式形式输入表达式转换为前缀表达式操作中调用了顺序栈SqStack1模块。四、【详细设计】1、二叉树的存储类型/*二叉树结点类型*/typedefenum{INT,CHAR}ElemTag;/*INT为整型数据num，CHAR为字符型数据c*/typedefstructTElemType{ElemTagtag;/*{INT,CHAR}指示是整型还是字符型*/union{intnum;/*tag=INT时，为整型*/charc;/*tag=CHAR时，为字符型*/};}TElemType;/*二叉树的二叉链表存储表示*/typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;/*左右孩子指针*/}BiTNode,*BiTree;二叉树的基本操作已经在构造表达式和表达式中的基本操作中根据不同的功能和实际情况修改了，详细见各个函数操作的算法设计。2、顺序栈的存储类型/*栈的顺序存储表示*/#defineSTACK_INIT_SIZE10/*存储空间初始分配量*/#defineSTACKINCREMENT2/*存储空间分配增量*//*两个顺序栈*/typedefstructSqStack{SElemType*base;/*在栈构造之前和销毁之后，base的值为NULL*/SElemType*top;/*栈顶指针*/intstacksize;/*当前已分配的存储空间，以元素为单位*/}SqStack;/*顺序栈SqStack*/typedefstructSqStack1{SElemType1*base;/*在栈构造之前和销毁之后，base的值为NULL*/SElemType1*top;/*栈顶指针*/intstacksize;/*当前已分配的存储空间，以元素为单位*/--6}SqStack1;/*顺序栈SqStack1*/相关的基本操作见上面的“expression.h文件的整体结构”的说明，详细的算法设计见附录的程序清单。3、表达式的基本操作StatusInput_Expr(char*string,intflag);/*以字符序列的形式输入语法正确的前缀表达式，保存到字符串string*//*参数flag=0表示输出的提示信息是请输入正确的前缀表示式：*//*flag=1表示输出的提示信息为请以表达式的原书写形式输入正确表示式：*/voidjudge_value(BiTree*E,char*string,inti);/*判断字符string[i]，如果是'0'-'9'常量之间，二叉树结点存为整型；否则，存为字符型*/StatusReadExpr(BiTree*E,char*exprstring);/*以正确的前缀表示式并构造表达式E*/StatusPri_Compare(charc1,charc2);/*如果两个字符是运算符，比较两个运算符的优先级，c1比c2优先，返回OK，否则返回ERROR*/voidWriteExpr(BiTreeE);/*用带括弧的中缀表达式输入表达式*/voidAssign(BiTree*E,charV,intc,int*flag);/*实现对表达式中的所有变量V的赋值(V=c)，参数flag为表示是否赋值