数据结构优秀课程设计优质报告.doc

资源描述

一、需求分析【课程设计要求】【问题描述】一个表示式和一棵二叉树之间，存在着自然对应关系。写一个程序，实现基于二叉树表示算术表示式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、数据类型申明：在这个课程设计中，采取了链表二叉树存放结构，和两个次序栈辅助存放结构 /*头文件和存放结构*/ #include<stdio.h> #include<conio.h> #include<stdlib.h> #include<string.h> #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define OVERFLOW 0 typedef int Status; 2、表示式抽象数据类型定义 ADT Expression{ 数据对象D：D是含有数值常量C和没有数值变量V；数据关系：R={<(V或C)P(V或C)>|V,C∈D, <(V或C)P(V或C)>表示由运算符P结合起来表示式E} 基础操作： Status Input_Expr(&string,flag) 操作结果：以字符序列形式输入语法正确前缀表示式，保留到字符串string；参数flag表示输出提醒信息是什么，输入成功返回OK，不然，返回ERROR。 void judge_value(&E,&string,i) 初始条件：树E存在，表示式前缀字符串string存在；操作结果：判定字符string[i]，假如是'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 Expression 3、整体设计在这个课程设计中，有两个源代码文件：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模块主程序模块中对于表示式存放结构调用了二叉树模块，而在结构表示式二叉树模块中又调用了次序栈SqStack模块，主程序中在将原表示式形式输入表示式转换为前缀表示式操作中调用了次序栈SqStack1模块。四、【具体设计】 1、二叉树存放类型 /*二叉树结点类型*/ typedef enum{INT,CHAR}ElemTag;/*INT为整型数据num，CHAR为字符型数据c*/ typedef struct TElemType { ElemTag tag;/*{INT,CHAR}指示是整型还是字符型*/ union { int 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); /*判定字符string[i]，假如是'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中全部常数运算*/ 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复合新表示式失败！请按任意键返回主菜单！"); } } } 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表示式结组成功！");} } case '7':/*合并表示式中全部常数运算*/ if(flag==1) MergeConst(&E); case '8'://三角函数操作 printf("\n\t***************************三角函数操作(选作)***************************"); printf("\n"); printf("\n\t[注] 请按要求输入其中 ~代表sin !代表cos @代表tan "); printf("\n\t角度用弧度表示，比如~1 即表示sin 1"); printf("\n\t本操作只可求三角函数值，如需其它操作请将结果带入其它操作中"); printf("\n\t输入一个字符请按回车，确保正确录入"); printf("\n\t************************************************************************"); double opr1,result1; char opr; printf("\n请按要求输入"); scanf("%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型值域。不过在存放时发觉每个字符只需占一个域就能够，所以我又采取共同体这么节省了内存。 2. 在算法设计中，结构表示式树时候，原来认为使用递归结构表示式会极难做到犯错处理，所以采取了次序栈辅助结构方法，而且尽可能地对程序进行完善，犯错处理。不过经过和同学相互讨论和研究，发觉自己想法犯了很大错误，递归结构表示式对于犯错处理很简单也很完善，这一点让我加深了递归使用和了解。 3.也就是三角函数问题，我最头疼地方。首先开始运行时会出现错误，无法输出正确结果。经过网上搜索，我发觉对于三角函数定义类型必需是double，这么话，假如要改话，差不多改大半程序，所以我就让此功效单独出来，由提醒让用户手动完成。 4、在调试过程中，花费时间最为多是对输入错误表示式犯错处理，更改增加代码几乎全部是为了犯错处理，不过，认为这么调试才更能锻炼一个人编程能力。六、【调试分析】 1.进入演示程序主界面 2.第一次输入，需要选择1功效《一》选择‘1’进入测试输入正确前缀表示式操作 1、输入前缀表示式为一个小于9常量：‘8’ 2、输入前缀表示式为一个变量：‘Z’ 3、输入前缀表示式为一个简单运算表示式：‘-91’ 4、输入前缀表示式为一个较为复杂、带有变量表示式：‘+++*3^x3*2^x2x6’ 5、输入前缀表示式‘*-+23a+b*34’，输出带括弧表示式 6、输入错误前缀表示式：‘+999’和‘+*5^x2*8x&’ 《二》选择‘3’进入测试对变量赋值 1、对前缀表示式‘3*x^3+2*x^2+x+6’中变量x进行赋值，赋值为5 2、对前缀表示式‘a+b*c’中变量b进行赋值，赋值为6 3、对前缀表示式‘5*x^2+8*x’中不存在变量y进行赋值，赋值为4 《三》选择‘4’进入测试求算数表示式值 1、求算数表示式‘9+8’值 2、求算数表示式‘（65+98）*（9^2+(21-96)）’值 3、求仍存在变量表示式‘3+a*9-6’值《四》选择‘5’进入结构新复合表示式 1、未结构表示式E时 2、已结构了表示式E时《五》选择‘6’进入以原表示式形式输入结构表示式 1、结构表示式‘6*a+9/b-(a+2^3)’ 输出结果少了括弧，这个是程序中一个BUG，程序判定带括弧输出表示式时判定两个优先等级时一个很大BUG，一个本人自己没法处理BUG。 2、结构表示式‘(((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’，进入三角函数操作经过对各个操作测试，能够这么总结说，基础完成了课程设计要求，虽说其中有部分操作还存在BUG需要去完善改善。七、【试验心得】 1 经过这两周编译，我感觉对二叉树掌握更牢靠了，整体上我全部是用二叉树处理实现各个功效。我感觉对于一个题目中处理函数尽可能让她能够多功效中使用，这么编程效率会高部分。 2. 我开始设计时候只考虑一个功效一个功效实现。这么做很没有全局观念。我认为在以后编程中一定要有全局意识，整体上构思好，有个好数据结构，这么事半功倍。 3.编程就是要多动手八、【参考文件】严蔚敏，吴伟民著，数据结构（C语言版），北京：清华大学出版社，附源代码 expression.cpp #include"expression.h" #include"math.h" #include <stdio.h> //#include <stdlib.h> /*全局变量*/ int save_number[51];/*在按原表示式输入形式中，输入常量保留到数组save_number中，常量最多为50个，0单元不用*/ char Expr_String[50];/*存放表示式字符串*/ /*以字符序列形式输入语法正确前缀表示式，保留到字符串string*/ /*参数flag=0表示输出提醒信息是"请输入正确前缀表示式："*/ /*flag=1表示输出提醒信息为"请以表示式原书写形式输入正确表示式："*/ Status Input_Expr(char *string,int flag) { if(flag==0)printf("\n请输入正确前缀表示式："); else printf("\n请以表示式原书写形式输入正确表示式："); flushall();/*清理缓冲区*/ gets(string);/*从键盘输入一串字符串作为表示式*/ if(strlen(string)==1)/*输入表示式字符串长度为1*/ if(string[0]=='+'||string[0]=='-'||string[0]=='*'||string[0]=='/'||string[0]=='^')/*输入表示式只有一个运算符*/ { printf("\n表示式只有一个字符，为运算符，错误！");return ERROR;} else if((string[0]>='0'&&string[0]<'9')||(string[0]>='a'&&string[0]<='z')||(string[0]>='A'&&string[0]<='Z')) /*输入表示式只有一个数字或字符*/ { printf("\n表示式只有一个字符！");return OK;} else {printf("\n输入字符不是运算符也不是变量常量，错误！");return ERROR;} return OK; } /*判定字符string[i]，假如是'0'-'9'常量之间，二叉树结点存为整型；不然，存为字符型*/ void judge_value(BiTree *E,char *string,int i) { if(string[i]>='0'&&string[i]<='9')/*为常量*/ {(*E)->data.tag=INT;(*E)->data.num=string[i]-48;} else if(string[i]>=1&&string[i]<=20)/*为常量，常量存于数组save_number中*/ {(*E)->data.tag=INT;(*E)->data.num=save_number[string[i]];} else/*为变量*/ {(*E)->data.tag=CHAR;(*E)->data.c=string[i];} } /*以正确前缀表示式并结构表示式E*/ Status ReadExpr(BiTree *E,char *exprstring) { SqStack S;//定义次序栈S int i,len;/*len为表示式长度*/ BiTree 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);/*将exprstring[0]存入二叉树结点中*/ else { judge_value(E,exprstring,0);/*将exprstring[0]存入二叉树结点中*/ InitStack(&S);/*初始化栈*/ q=(*E); Push(&S,q);/*入栈*/ Push(&S,q);/*入栈，根结点入栈两次是为判定先序输入表示式是不是正确表示式*/ for(i=1;i<len&&!StackEmpty(S);i++)// { p=(BiTree)malloc(sizeof(BiTNode)); judge_value(&p,exprstring,i);/*将exprstring[i]存入二叉树结点中*/ p->lchild=NULL; p->rchild=NULL; if(exprstring[i]=='+'||exprstring[i]=='-'||exprstring[i]=='*'||exprstring[i]=='/'||exprstring[i]=='^') {/*为运算符，运算符入栈，左孩子不空，向左孩子走，不然，假如右孩子不空，向右孩子走*/ if(!q->lchild) {q->lchild=p;Push(&S,p);q=p;} else {q->rchild=p;Push(&S,p);q=p;} } else/*不是运算符，运算符出栈*/ { if(!q->lchild) {q->lchild=p;Pop(&S,&q);} else {q->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=='-'||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) { if(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.tag==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->rchild);/*不然，输出右子树*/ } } /*实现对表示式中全部变量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 result; } /*运算符运算求值，参数opr1,opr2为常量，opr为运算符，依据不一样运算符，实现不一样运算，返回运算结果*/ long Operate(int opr1,char opr,int opr2) { long result; switch(opr) { case '+':/*加法*/ result=opr1+opr2; return result;break;

展开阅读全文