《[工学]数据结构课程设计报告.doc》由会员分享，可在线阅读，更多相关《[工学]数据结构课程设计报告.doc（36页珍藏版）》请在三一办公上搜索。
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求值。 （
2、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*2x2x6并输出。（2）每当输入一个表达式后，对其中的变量赋值，然后
3、对表达式求值二 、【整体算法思想】 一个表达式和一棵二叉树之间存在一一对应的关系。本程序我主要用前缀表达式建树，中序遍历并适当加括号实现中缀输出。具体操作即对树的程序进行处理，再输出。三、【概要设计】1、数据类型的声明：在这个课程设计中，采用了链表二叉树的存储结构，以及两个顺序栈的辅助存储结构/*头文件以及存储结构*/#include#include#include#include#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW 0typedef int Status;2、表达式的抽象数据类型定义A
4、DT 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 Rea
5、dExpr(&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为标志是否有赋值过；操作结果：
6、实现对表达式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存在；操作条件：构
7、造一个新的复合表达式(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.
8、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为新的栈顶元素 */Sta
9、tus 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,SElemTyp
10、e1 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(
11、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
12、()while(1)清屏；switch(主菜单)根据不同的选择，调用不同的操作函数，完成各个操作；2、本程序有四个模块，主程序模块，二叉树模块，两个顺序栈模块。四者的调用关系如下：主程序模块二叉树模块顺序栈SqStack模块顺序栈SqStack1模块主程序模块中的对于表达式的存储结构调用了二叉树模块，而在构造表达式的二叉树模块中又调用了顺序栈SqStack模块，主程序中在将原表达式形式输入表达式转换为前缀表达式操作中调用了顺序栈SqStack1模块。四、【详细设计】1、二叉树的存储类型/*二叉树结点类型*/typedef enumINT,CHARElemTag;/*INT为整型数据num，CH
13、AR为字符型数据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;二叉树的基本操作已经在构造表达式和表达式中的基本操作中根据不同的功能和实际情况修改了，详细见各个
14、函数操作的算法设计。2、顺序栈的存储类型/*栈的顺序存储表示 */#define STACK_INIT_SIZE 10 /* 存储空间初始分配量 */#define STACKINCREMENT 2 /* 存储空间分配增量 */*两个顺序栈*/typedef struct SqStack SElemType *base; /* 在栈构造之前和销毁之后，base的值为NULL */ SElemType *top; /* 栈顶指针 */ int stacksize; /* 当前已分配的存储空间，以元素为单位 */ SqStack; /* 顺序栈SqStack */typedef struct Sq
15、Stack1 SElemType1 *base; /* 在栈构造之前和销毁之后，base的值为NULL */ SElemType1 *top; /* 栈顶指针 */ int stacksize; /* 当前已分配的存储空间，以元素为单位 */ SqStack1; /* 顺序栈SqStack1 */相关的基本操作见上面的“expression.h文件的整体结构”的说明，详细的算法设计见附录的程序清单。3、表达式的基本操作Status Input_Expr(char *string,int flag);/*以字符序列的形式输入语法正确的前缀表达式，保存到字符串string*/*参数flag=0表示
16、输出的提示信息是请输入正确的前缀表示式：*/*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*
17、/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(B
18、iTree 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中所有常数运算*/4、主程序和其他伪码算法void main(
19、)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,
20、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)/*按原表达式形式输入*/r
21、eversal_string(Expr_String);if(ReadExpr(&E1,Expr_String)flag=1;P=getchar();CompoundExpr(P,&E,E1);else printf(n复合新的表达式失败！请按任意键返回主菜单！);case 6:/*以表达式的原书写形式输入*/if(Input_Expr(string,1)if(Read_Inorder_Expr(string,Expr_String)reversal_string(Expr_String);if(ReadExpr(&E,Expr_String)flag=1;printf(n表达式构造成功！);
22、case 7:/*合并表达式中所有常数运算*/if(flag=1) MergeConst(&E);case 8:/三角函数操作printf(nt*三角函数操作(选作)*);printf(n);printf(nt注 请按要求输入其中 代表sin !代表cos 代表tan ); printf(nt角度用弧度表示，例如1 即表示sin 1); printf(nt本操作只可求三角函数值，如需其他操作请将结果带入其它操作中); printf(nt输入一个字符请按回车，确保正确录入); printf(nt*); double opr1,result1;char opr; printf(n请按要求输入);s
23、canf(%c,&opr);getch();scanf(%lf,&opr1);getch(); result1=Operate1(opr,opr1); printf(结果为%f,result1); getch();break;case 0:/*退出*/5、函数的调用关系除了主函数main()外，其他各个函数相对于其它函数来说是独立的，函数的使用都由主函数main()调用使用的，可以简单的说，各个函数都是主函数下的从函数。五、【设计分析】1, 开始设计时我设想建树时可以设定五个域，左右孩子，标志tag, int型值域，char型值域。但是在存储时发现每个字符只需占一个域就可以，所以我又采用共同体
24、这样节约了内存。2. 在算法设计中，构造表达式树的时候，本来以为使用递归构造表达式会很难做到出错处理的，所以采用了顺序栈辅助构造方法，并且尽可能地对程序进行完善，出错处理。但是经过与同学的相互讨论和研究，发现自己的想法犯了很大的错误，递归构造表达式对于出错处理很简单也很完善，这一点让我加深了递归的使用和理解。3.也就是三角函数问题，我最头疼的地方。首先开始运行时会出现错误，无法输出正确结果。通过网上搜索，我发现对于三角函数的定义类型必须是double，这样的话，如果要改的话，差不多改大半程序，所以我就让此功能单独出来，由提示让用户手动完成。4、在调试的过程中，花费时间最为多的是对输入错误表达式
25、的出错处理，更改增加的代码几乎都是为了出错处理，但是，觉得这样的调试才更能锻炼一个人的编程能力。六、【调试分析】1.进入演示程序主界面2.第一次输入，需要选择1功能一选择1进入测试输入正确的前缀表达式操作1、输入的前缀表达式为一个不大于9常量：82、输入前缀表达式为一个变量：Z3、输入前缀表达式为一个简单的运算表达式：-914、输入前缀表达式为一个较为复杂的、带有变量的表达式：+*3x3*2x2x65、输入前缀表达式*-+23a+b*34，输出带括弧的表达式6、输入错误的前缀表达式：+999和+*5x2*8x&二选择3进入测试对变量的赋值1、对前缀表达式3*x3+2*x2+x+6中变量x进行赋
26、值，赋值为52、对前缀表达式a+b*c中的变量b进行赋值，赋值为63、对前缀表达式5*x2+8*x中不存在的变量y进行赋值，赋值为4三选择4进入测试求算数表达式的值1、求算数表达式9+8的值2、求算数表达式（65+98）*（92+(21-96)）的值3、求仍存在变量的表达式3+a*9-6的值四选择5进入构造新的复合表达式1、未构造表达式E时2、已构造了表达式E时五选择6进入以原表达式形式输入构造表达式1、构造表达式6*a+9/b-(a+23)输出的结果少了括弧，这个是程序中的一个BUG，程序的判定带括弧输出表达式时判断两个优先级别时的一个很大的BUG，一个本人自己没法解决的BUG。2、构造表达
27、式(3+2)*9)-(6/3)*9+1)/8+18*3输出的结果简化了多余的括弧，这一点是一个很大的优化。3、构造表达式66+，出错处理4、构造表达式6+-b+9*9，出错处理5、构造表达式9+a+(6+5)*a,出错处理多余输入的括弧6、构造表达式6#9+8*6，出错处理输入非运算符和非变量常量的表达式六选择7进入合并常数操作1、构造表达式(2+3-a)*(b+3*4)，后合并常数操作2、构造表达式（3+3*4）*(1*2+8/2)，经过多次合并，得出最后结果这个合并常数操作唯一的缺点就是要多次操作，但是，这个缺点也不能说为缺点，它可以很清晰的反映出表达式求值的步骤！七选择8，进入三角函数操
28、作经过对各个操作的测试，可以这样总结的说，基本完成了课程设计的要求，虽说其中有一些操作还存在BUG需要去完善改进。七、【实验心得】1 经过这两周的编译，我感觉对二叉树的掌握更牢固了，整体上我都是用的二叉树处理实现各个功能。我感觉对于一个题目中处理函数尽量让他可以多功能中使用，这样编程效率会高一些。2. 我开始设计的时候只考虑一个功能一个功能的实现。这样做很没有全局观念。我认为在以后的编程中一定要有全局意识，整体上构思好，有个好的数据结构，这样事半功倍。3.编程就是要多动手八、【参考文献】严蔚敏，吴伟民著，数据结构（C语言版），北京：清华大学出版社，2007附 源代码 expression.cp
29、p#includeexpression.h #includemath.h #include /#include /*全局变量*/int save_number51;/*在按原表达式输入形式中，输入的常量保存到数组save_number中，常量最多为50个，0单元不用*/char Expr_String50;/*存放表达式的字符串*/*以字符序列的形式输入语法正确的前缀表达式，保存到字符串string*/*参数flag=0表示输出的提示信息是请输入正确的前缀表示式：*/*flag=1表示输出的提示信息为请以表达式的原书写形式输入正确表示式：*/Status Input_Expr(char *st
30、ring,int flag)if(flag=0)printf(n请输入正确的前缀表示式：);else printf(n请以表达式的原书写形式输入正确表示式：);flushall();/*清理缓冲区*/gets(string);/*从键盘输入一串字符串作为表达式*/if(strlen(string)=1)/*输入的表达式字符串长度为1*/if(string0=+|string0=-|string0=*|string0=/|string0=)/*输入的表达式只有一个运算符*/ printf(n表达式只有一个字符，为运算符，错误！);return ERROR;else if(string0=0&st
31、ring0=a&string0=A&string0=0&stringidata.tag=INT;(*E)-data.num=stringi-48;else if(stringi=1&stringidata.tag=INT;(*E)-data.num=save_numberstringi;else/*为变量*/(*E)-data.tag=CHAR;(*E)-data.c=stringi;/*以正确的前缀表示式并构造表达式E*/Status ReadExpr(BiTree *E,char *exprstring)SqStack S;/定义顺序栈Sint i,len;/*len为表达式的长度*/Bi
32、Tree p,q;(*E)=(BiTree)malloc(sizeof(BiTNode);/*申请二叉树的根结点的空间*/(*E)-lchild=NULL;(*E)-rchild=NULL;len=strlen(exprstring);/*len赋值为表达式的长度*/if(len=1)/*表达式长度为1时，二叉树只有根结点*/judge_value(E,exprstring,0);/*将exprstring0存入二叉树的结点中*/else judge_value(E,exprstring,0);/*将exprstring0存入二叉树的结点中*/InitStack(&S);/*初始化栈*/q=(
33、*E);Push(&S,q);/*入栈*/Push(&S,q);/*入栈，根结点入栈两次是为判断先序输入的表达式是不是正确的表达式*/for(i=1;ilchild=NULL;p-rchild=NULL;if(exprstringi=+|exprstringi=-|exprstringi=*|exprstringi=/|exprstringi=)/*为运算符，运算符入栈，左孩子不空，向左孩子走，否则，如果右孩子不空，向右孩子走*/if(!q-lchild)q-lchild=p;Push(&S,p);q=p;elseq-rchild=p;Push(&S,p);q=p;else/*不是运算符，运算
34、符出栈*/if(!q-lchild)q-lchild=p;Pop(&S,&q);elseq-rchild=p;Pop(&S,&q);if(StackEmpty(S)&i=len)return OK;/*栈空且i=len，说明输入的表达式是正确的*/else/*输入的表达式是错误的*/printf(n输入的表达式有误！);return ERROR;/*如果两个字符是运算符，比较两个运算符的优先级，c1比c2优先，返回OK，否则返回ERROR*/Status Pri_Compare(char c1,char c2)if(c1=|c1=*|c1=-|c1=+|c1=/)&(c2=|c2=*|c2=-
35、|c2=+|c2=/)/*c1和c2为运算符*/if(c1=)/*c1为指数运算符，则当c2不为时，c1比c2优先*/if(c2!=) return OK;else return ERROR;else if(c1=*|c1=/)/*c1为乘法或除法运算符，则当c2为+或-，c1比c2优先*/if(c2=|c2=*|c2=/) return ERROR;else return OK;else return ERROR;/*其余，c1不比c2优先*/else return ERROR;/*c1和c2不是运算符*/*用带括弧的中缀表达式输出表达式*/void WriteExpr(BiTree E)i
36、f(E)/*树不为空*/*先递归左子树*/if(E-lchild&E-lchild-data.tag=CHAR)/*E的左孩子不为空，且左孩子为字符*/if(Pri_Compare(E-data.c,E-lchild-data.c)/*E-data.c比E-lchild-data.c优先*/printf(); WriteExpr(E-lchild); printf();/*带括弧输出左子树*/else WriteExpr(E-lchild);/*否则，不带括弧输出左子树*/else WriteExpr(E-lchild);/*否则，输出左子树*/*访问输出根结点的值*/if(E-data.ta
37、g=INT)printf(%d,E-data.num);else printf(%c,E-data.c);/*后递归右子树*/if(E-rchild&E-rchild-data.tag=CHAR)/*E的右孩子不为空，且右孩子为字符*/if(Pri_Compare(E-data.c,E-rchild-data.c)/*E-data.c比E-rchild-data.c优先*/printf();WriteExpr(E-rchild);printf();/*带括弧输出右子树*/else WriteExpr(E-rchild);/*否则，不带括弧输出右子树*/else WriteExpr(E-rchi
38、ld);/*否则，输出右子树*/*实现对表达式中的所有变量V的赋值(V=c)，参数flag为表示是否赋值过的标志*/void Assign(BiTree *E,char V,int c,int *flag)if(*E)if(*E)-data.tag=CHAR&(*E)-data.c=V)/*如果找到要赋值的变量，赋值*/(*E)-data.tag=INT;(*E)-data.num=c;*flag=1;Assign(&(*E)-lchild),V,c,flag);/*递归左子树*/Assign(&(*E)-rchild),V,c,flag);/*递归左子树*/*指数运算函数，底数为x，指数为exp*/long power(int x,int exp)long result;int i;for(i=1,result=1;i=exp;i+)result*=x;return res
