数据结构课程设计-表达式类型的实现(难度系数-1.2).doc

数据结构课程设计报告
题目：表达式类型的实现（难度系数：1.2）

学 院 计算机
专 业 计算机科学与技术
年级班别 2015级8班
学 号 3115005210
学生姓名 杨嘉慧
指导教师 李杨
编 号
成 绩

2017 年 1 月
报告：
报告内容： □详细　 □完整　 □基本完整 □不完整
设计方案： □非常合理　 □合理　 □基本合理 □较差
算法实现： □全部实现　 □基本实现　 □部分实现 □实现较差
测试样例： □完备　 □比较完备　 □基本完备 □不完备
文档格式： □规范　 □比较规范　 □基本规范 □不规范

答辩：
□理解题目透彻，问题回答流利
□理解题目较透彻，回答问题基本正确
□部分理解题目，部分问题回答正确
□未能完全理解题目，答辩情况较差

总评成绩：
□优　　　□良　　　□中　　　□及格　　　□不及格

运行环境：CodeBlocks
完成的题目：表达式类型的实现（难度系数：1.2）
选做的内容：(4)在表达式内增加对三角函数等初等函数的操作。
一、 需求分析【课程设计要求】
【问题的描述】
一个表达式和一棵二叉树之间，存在着自然的对应关系。写一个程序，实现 基于二叉树表示的算术表达式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
typedef int Status;
2、表达式的抽象数据类型定义
基本操作：
void judge_str(&E,&string1)
初始条件：树E存在，表达式的前缀字符串string存在；
操作结果：判断字符string[i]，如果是'0'-'9'常量之间，二叉树结点E存为整型；否则，存为字符型。
Status ReadExpr(&E,&string1)
初始条件：表达式的前缀形式字符串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)
初始条件：表达式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)。
3、整体设计
在这个课程设计中，有一个源代码文件：expression.c。
在expression.c文件中，是实现课程设计要求的各个函数。
主程序的流程以及各程序模块之间的调用关系：
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 */
顺序栈SqStack模块
二叉树模块
主程序模块
3、本程序有三个模块，主程序模块，二叉树模块，一个个顺序栈模块。三者者的调用关系如下：

三、【详细设计】
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 */
3、表达式的基本操作
Status Input_Expr(char *string,int flag);
/*以字符序列的形式输入语法正确的前缀表达式，保存到字符串string*/ /*参数flag=0表示输出的提示信息是"请输入正确的前缀表示式："*/ /*flag=1表示输出的提示信息为"请以表达式的原书写形式输入正确表示式："*/
void judge_str(BiTree *E,char *string,int i);
/*判断字符string[i]，如果是'0'-'9'常量之间，二叉树结点存为整型；否则，存为字符型*/
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);
/*构造一个新的复合表达式*/
4、主程序和其他伪码算法
void main(){
BiTree E1,E2;
char V,P;
int c;
ReadExpr(&E1);
printf("\nE1带括弧的中缀表示式为：");
WriteExpr(E1);
while(Check(E1)==TRUE){
printf("\n请输入要赋值的字符：");
V=getchar();
printf("请输入要将赋值为：");
scanf("%d",&c);
Assign(&E1,V,c);
getchar();
WriteExpr(E1);
printf("\n输入未知数后E1表达式为：");
WriteExpr(E1);
}
printf("\nE1表达式的值为: %d",Value(E1));
ReadExpr(&E2);
printf("\nE2带括弧的中缀表示式为：");
WriteExpr(E2);
Assign(&E2,V,c);
CompoundExpr(P,&E1,E2);
}
5、函数的调用关系

除了主函数main()外，其他各个函数相对于其它函数来说是独立的，函数的使用都由主函数main()调用使用的，可以简单的说，各个函数都是主函数下的从函数。
四、【调试分析】
1. 开始设计时我设想建树时可以设定五个域，左右孩子，标志tag, int型值域，char型值域。但是在存储时发现每个字符只需占一个域就可以，所以我又采用共同体这样节约了内存。
2. 在算法设计中，构造表达式树的时候，本来以为使用递归构造表达式会很难做到出错处理的，所以采用了顺序栈辅助构造方法，并且尽可能地对程序进行完善，出错处理。但是经过与同学的相互讨论和研究，发现自己的想法犯了很大的错误，递归构造表达式对于出错处理很简单也很完善，这一点让我加深了递归的使用和理解。
3.也就是三角函数问题，我最头疼的地方。首先开始运行时会出现错误，无法输出正确结果。通过网上搜索，我发现对于三角函数的定义类型必须是double，这样的话，如果要改的话，差不多改大半程序，所以我就让此功能单独出来，由提示让用户手动完成。
4.在调试的过程中，花费时间最为多的是对输入错误表达式的出错处理，更改增加的代码几乎都是为了出错处理，但是，觉得这样的调试才更能锻炼一个人的编程能力。
五、【用户使用说明】
打开程序，按屏幕上的提示输入数据，随后就可以看到结果了。
六、【测试结果】
1.输入0

2.输入a

3.输入-91

4.输入+a*bc

5.输入+*5x2*8x

6.输入+++*3^x3*2^x2x6

7. CompoundExpr(P,&E1,E2)合并操作

七、【附录】
#include<stdio.h>
#include<math.h>
#include<conio.h>
#include<stdlib.h>
#include<string.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
typedef int Status;
typedef enum{INT,CHAR}ElemTag;
typedef struct TElemType {
ElemTag tag;
union {
int num;
char c;
};
}TElemType;
typedef struct BiTNode {
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
typedef BiTree SElemType;
#define STACK_INIT_SIZE 10
#define STACKINCREMENT 2
typedef struct SqStack {
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
Status InitStack(SqStack *S) {
(*S).base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!(*S).base)exit(OVERFLOW);
(*S).top=(*S).base;
(*S).stacksize=STACK_INIT_SIZE;
return OK;
}
Status StackEmpty(SqStack S) {
if(S.top==S.base)
return TRUE;
else
return FALSE;
}
Status Push(SqStack *S,SElemType e) {
if((*S).top-(*S).base>=(*S).stacksize){
(*S).base=(SElemType *)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof(SElemType)); if(!(*S).base)exit(OVERFLOW);
(*S).top=(*S).base+(*S).stacksize;
(*S).stacksize+=STACKINCREMENT;
}
*((*S).top)++=e;
return OK;
}
Status Pop(SqStack *S,SElemType *e) {
if((*S).top==(*S).base)return ERROR;
*e=*--(*S).top;
return OK;
}
Status GetTop(SqStack S,SElemType *e){
if(S.top>S.base) {
*e=*(S.top-1);
return OK;
}
else return ERROR; }
void judge_str(BiTree *E,char *string,int i){
if(string[i]>='0'&&string[i]<='9'){
(*E)->data.tag=INT;
(*E)->data.num=string[i]-48;
}
else{
(*E)->data.tag=CHAR;
(*E)->data.c=string[i];
}
}
Status ReadExpr(BiTree *E){
SqStack S;
int i,len;
BiTree p,q;
(*E)=(BiTree)malloc(sizeof(BiTNode));
(*E)->lchild=NULL;
(*E)->rchild=NULL;
char string1[50];
printf("\n请输入语法正确的前缀表示式：");
gets(string1);
len=strlen(string1);
if(len==1)
judge_str(E,string1,0);
else {
judge_str(E,string1,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_str(&p,string1,i);
p->lchild=NULL;
p->rchild=NULL;
if(string1[i]=='+'||string1[i]=='-'||string1[i]=='*'||string1[i]=='/'||string1[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;
else{
printf("\n输入的表达式有误！");
return ERROR;
}}}
Status Pri_Compare(char c1,char c2) {
if((c1=='^'||c1=='*'||c1=='-'||c1=='+'||c1=='/')&&(c2=='^'||c2=='*'||c2=='-'||c2=='+'||c2=='/')) {
if(c1=='^'){
if(c2!='^') return OK;
else return ERROR;
}
else if(c1=='*'||c1=='/'){
if(c2=='^'||c2=='*'||c2=='/') return ERROR;
else return OK;
}
else return ERROR;
}
else return ERROR;
}
void WriteExpr(BiTree E) {
if(E){
if(E->lchild&&E->lchild->data.tag==CHAR){
if(Pri_Compare(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){
if(Pri_Compare(E->data.c,E->rchild->data.c)){
printf("(");WriteExpr(E->rchild);printf(")");
}
else WriteExpr(E->rchild);
}
else WriteExpr(E->rchild);
}}
Status Check(BiTree E){
if(E&&E->data.tag==CHAR){
if(E->data.c!='*'&&E->data.c!='^'&&E->data.c!='-'&&E->data.c!='+'&&E->data.c!='/'){
printf("\n表达式中仍存在变量没有赋值！没法求出表达式的值！");
return TRUE;}
if(!Check(E->lchild))Check(E->rchild);
}
}
void Assign(BiTree *E,char V,int c){
if(*E){
if((*E)->data.tag==CHAR&&(*E)->data.c==V){
(*E)->data.tag=INT;
(*E)->data.num=c;;
}
Assign(&((*E)->lchild),V,c);
Assign(&((*E)->rchild),V,c);
}
}
long power(int x,int exp){
long result;
int i;
for(i=1,result=1;i<=exp;i++)
result*=x;
return result;
}
long Operate(int opr1,char opr,int opr2) {
long result;
switch(opr){
case '+':result=opr1+opr2;return result;break;
case '-':result=opr1-opr2;return result;break;
case '*':result=opr1*opr2;return result;break;
case '/':result=opr1/opr2;return result;break;
case '^':result=power(opr1,opr2);return result;break;
default:break;
}}
double Operate1(char opr,double opr1) {
double result1;
switch(opr){
case '~':/*正玄sin*/result1=sin(opr1);return result1;break;
case '!':/*余弦*/result1=cos(opr1);return result1;break;
case '@':/*正切*/ result1=tan(opr1);return result1;break;
default:break;
}}
long Value(BiTree E) {
if(E){
if(!E->lchild&&!E->rchild&&E->data.tag==INT)return(E->data.num);
return Operate(Value(E->lchild),E->data.c,Value(E->rchild));
}}
void CompoundExpr(char P,BiTree *E1,BiTree E2){
BiTree E;
printf("\n请输入根结点的值：");
P=getchar();
E=(BiTree)malloc(sizeof(BiTNode));
E->data.tag=CHAR;
E->data.c=P;
E->lchild=(*E1);
E->rchild=E2;
(*E1)=E;
printf("\n表达式E复合成功！其表达式变为：\n");
WriteExpr(E);
}
void main(){
BiTree E1,E2;
char V,P;
int c;
ReadExpr(&E1);
printf("\nE1带括弧的中缀表示式为：");
WriteExpr(E1);
while(Check(E1)==TRUE){
printf("\n请输入要赋值的字符：");
V=getchar();
printf("请输入要将赋值为：");
scanf("%d",&c);
Assign(&E1,V,c);
getchar();
WriteExpr(E1);
printf("\n输入未知数后E1表达式为：");
WriteExpr(E1);
}
printf("\nE1表达式的值为: %d",Value(E1));
ReadExpr(&E2);
printf("\nE2带括弧的中缀表示式为：");
WriteExpr(E2);
Assign(&E2,V,c);
CompoundExpr(P,&E1,E2);
}
八、【心得体会】
1  经过这两周的编译，我感觉对二叉树的掌握更牢固了，整体上我都是用的二叉树处理实现各个功能。我感觉对于一个题目中处理函数尽量让他可以多功能中使用，这样编程效率会高一些。 
2. 我开始设计的时候只考虑一个功能一个功能的实现。这
样做很没有全局观念。我认为在以后的编程中一定要有全局
意识，整体上构思好，有个好的数据结构，这样事半功倍。
3.编程就是要多动手。