数据结构课程设计-表达式类型的实现.doc

软 件 学 院课程设计报告书课程名称 数据结构 设计题目 表达式类型的实现 专业班级 学 号 姓 名 指导教师 指导教师 刘腊梅 2012年1月目录1 设计时间12 设计目的13设计任务14 设计内容14.1需求分析14.2总体设计24.3详细设计44.4测试与分析114.5 附录135 总结与展望19参考文献20成绩评定211 设计时间2012年1月3日2012年1月5日2 设计目的1、通过这次设计，要求在数据结构的逻辑结构和存储结构、数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能方面受到比较系统的训练。2、学生必须按照课程设计要求，以学生为主、指导教师指导为辅，认真、独立地完成课程设计的任务，有问题及时主动与指导教师沟通。3、本次课程设计按照教学要求需要在一周时间内独立完成，学生要发挥自主学习的能力，充分利用时间，按时完成设计内容。3设计任务一个表达式与一棵二叉树之间，存在着自然的对应关系。写一个程序，实现基于二叉树表示的算术表达式Expression的操作。4 设计内容 4.1需求分析 4.1.1程序所能达到的功能实现基于二叉树表示的算术表达式Expression的操作。4.1.2输入的形式和输入值的范围将算术表达式按照表达式的前缀表示形式输入，输入制的范围包括：变量（az）、常量（09）和二元运算符（+，-，*，/，）。4.1.3输出的形式算术表达式的输出将按照表达式的中缀表示形式输出，之后在将表达式中的变量赋值（例如“a ”）后输出计算结果。4.1.4测试数据正确输入及输出结果：-+a*b-cd/ef a=1,b=2,c=3,d=4,e=6,f=5。 输出：a+b*(c-d)-e/f计算结果为-2.2 （如图1所示） 图1：正确输入截图演示错误输入及输出结果：*12ab a=1/6,b=2。输出：(12*a)b 结算结果为144（如图2所示）图2：错误输入截图演示4.2总体设计4.2.1本程序中用到的所有抽象数据类型的定义typedef char TElemType;typedef double Status;二叉树结构体的定义typedef struct nodeTElemType OPTR;Status OPND;int data;struct node *lchild,*rchild;BinTNode;typedef BinTNode *BiTree;栈结构体的定义typedef struct ITdouble data;IT;创建栈结构体指针的定义typedef struct IT *base; IT *top; int stacksize; SqStack;4.2.2主程序的流程 Main( ) ReadExpr( ) WriteExpr( ) Assign( )4.2.3各程序模块之间的层次（调用）关系第一步，主函数main先调用函数ReadExpr( )，之后函数ReadExpr( )进行递归自调用实现算术表达式的输入；第二步，主函数main调用函数WriteExpr( )，之后函数WriteExpr( )进行递归自调用实现对算术表达式中的变量的赋值;第三步, 主函数main调用函数Assign( ), 函数Assign( )再调用函数Assign2( ), 函数Assign2( )进行自递归调用对算术表达式进行计算.4.3详细设计栈的初始化函数Status InitStack(SqStack *S)取栈顶函数Status GetTop(SqStack *S,IT *e)栈的数据压入函数 Status Push(SqStack *S,IT *e)栈的删除栈顶函数Status Pop(SqStack *S,IT *e)创建二叉树函数(递归先序输入)Status ReadExpr(BiTree *T)表达式输出函数（递归中序遍历二叉树）Status WriteExpr(BiTree *T)变量赋值函数（对二叉树进行先序递归遍历）Status Assign2(BiTree T,char a,double b)变量赋值函数（调用变量赋值函数进行）void Assign(BiTree T)表达式计算函数double Value(BiTree T,SqStack *S)#define OK 1#define ERROR 0#define OVERFLOW -2#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef char TElemType;typedef double Status;/*-创建二叉树结构体-*/typedef struct nodeTElemType OPTR;/运算符Status OPND;/运算数int data;/识别控制变量，0为运算符，1为运算数，2为变量struct node *lchild,*rchild;BinTNode;typedef BinTNode *BiTree;/*-创建栈结构体-*/typedef struct ITdouble data;IT;/*-创建栈结构体指针-*/typedef struct IT *base; IT *top; int stacksize; SqStack;/*-栈的初始化函数-*/ Status InitStack(SqStack *S) S-base=(IT *)malloc(STACK_INIT_SIZE*sizeof(IT); if(!S-base)exit(OVERFLOW); /检验栈是否创建成功 S-top=S-base; S-stacksize=STACK_INIT_SIZE; return OK;/*-取栈顶函数-*/Status GetTop(SqStack *S,IT *e) if(S-top=S-base)return ERROR; /检验栈是否为空 *e=*(S-top-1); return OK; /*-栈的数据压入函数-*/ Status Push(SqStack *S,IT *e)SqStack A; if(S-top-S-base=S-stacksize) /检验栈是否为空 A.base=(IT *)realloc(S-base,(S-stacksize+STACKINCREMENT)*sizeof(IT); if(!A.base)exit(OVERFLOW); /检验再次分配空间是否成功 S-base=A.base; S-top=S-base+S-stacksize; S-stacksize+=STACKINCREMENT; *S-top+=*e;return OK;/*-栈的删除栈顶函数-*/Status Pop(SqStack *S,IT *e) if(S-top=S-base)return ERROR; *e=*(-S-top); return OK;/*-创建二叉树(递归先序输入)-*/Status ReadExpr(BiTree *T)scanf(%c,&ch);if (ch= ) *T=NULL;else if(!(*T=(BinTNode*)malloc(sizeof(BinTNode) exit(OVERFLOW); if(ch=0&ch=0&chOPND=ah; (*T)-data=1; else if(ch=a&chOPTR=ch; (*T)-data=2; else (*T)-OPTR=ch; (*T)-data=0; ReadExpr(&(*T)-lchild); ReadExpr(&(*T)-rchild); return OK;/*-递归中序遍历二叉树（表达式输出）-*/Status WriteExpr(BiTree *T) if(*T) /检验二叉树是否为空p=(*T)-lchild;if(*T)-data=0&p-data=0&(*T)-OPTR=42|(*T)-OPTR=47)&(p-OPTR=43|p-OPTR=45)|(*T)-OPTR=94)/判断中序输出时是否需要添加括号（左孩子）printf(); WriteExpr(&(*T)-lchild);printf();else WriteExpr(&(*T)-lchild);if(*T)-data=2|(*T)-data=0)printf(%c,(*T)-OPTR);else printf(%lf,(*T)-OPND);p=(*T)-rchild;if(*T)-data=0&p-data=0&(*T)-OPTR=42|(*T)-OPTR=47)&(p-OPTR=43|p-OPTR=45)|(*T)-OPTR=45&p-OPTR=43|(*T)-OPTR=47&p-OPTR=42|(*T)-OPTR=94|(*T)-OPTR=42&p-OPTR=47) /判断中序输出时是否需要添加括号（右孩子）printf(); WriteExpr(&(*T)-rchild);printf();else WriteExpr(&(*T)-rchild);return OK; elsereturn OK;/*-变量赋值-*/Status Assign2(BiTree T,char a,double b) if(T) /检验二叉树是否为空if(T-data=2&a=T-OPTR) /判别data识控变量是否为2，同时检验变量名T-OPND=b;/递归先序遍历二叉树return OK; elseAssign2(T-lchild,a,b);Assign2(T-rchild,a,b);return OK;else return OK;/*-调用变量赋值函数进行变量赋值-*/void Assign(BiTree T)getchar();scanf(%c,&a);while(a!=#)/输入“”时，变量赋值结束scanf(=%lf,&b);getchar();Assign2(T,a,b);/调用函Status Assign2( )scanf(%c,&a);/*-计算表达式-*/double Value(BiTree T,SqStack *S)if(T) /检验二叉树是否为空Value(T-lchild,S);/递归后序遍历表达式Value(T-rchild,S);e=T-data;if(e=1|e=2)/检验识控变量，寻找运算数入栈p.data=T-OPND;Push(S,&p);else /遇到运算符，开始进行计算操作Pop(S,&m); Pop(S,&n);switch(T-OPTR) /检验运算符类型并计算case +:OUT.data=n.data+m.data; Push(S,&OUT);break;case -:OUT.data=n.data-m.data; Push(S,&OUT);break;case *:OUT.data=n.data*m.data; Push(S,&OUT);break;case /:OUT.data=n.data/m.data; Push(S,&OUT);break;case :OUT.data=pow(n.data,m.data); Push(S,&OUT);break;default: return ERROR;GetTop(S,&a);return a.data;void main() BiTree T; SqStack S; InitStack(&S); printf(请按输入表达式的前缀表示 :n); if(ReadExpr(&T) printf(表达式正确!n); WriteExpr(&T); printf(n请为变量赋值 :n); Assign(T); printf(表达式的结果是 :n); printf(%lf,Value(T,&S); getchar(); 3.函数的调用关系图 Main( ) ReadExpr( ) WriteExpr( ) Assign( ) Value( ) Assign2( )4.4测试与分析4.4.1测试正确结果：如图3所示图3：正确输入截图演示错误结果：如图4所示图4：错误输入截图演示4.4.2分析1.调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析：在本次数据结构的课程设计上级实践中，由于大量在函数中使用递归算法，因而使程序规模得到了有效控制，但是递归算法也存在算法逻辑错误不易察觉，程序运行差错不易检验的弊端。而且在函数ReadExpr( )和函数WriteExpr( )中我使用了二级指针传递，这更加使我的程序调试难度增加不少。因而在程序调试过程中，一旦发现错误，我首先检查是否为一般语法错误，比如字符或符号书写错误，书写格式错误；之后，再检查语句是否有算法设计错误，纠正错误语句，尤其是在指针传递过程中，对于指针和二级指针的传递是否符合函数传递要求的问题格外注意；最后，在排除这些非递归错误后，再分析是否是在函数的递归调用过程中出现了逻辑错误，在这里，我用到了编译工具VC+6.0的程序调试功能，再确保输入正确的前提下，逐步查看递归过程中数据是否按照要求进入了相应变量所在的内存地址，逐步查看函数的调用过程，以此来确定问题发生的位置，确定错误发生在第几次递归调用过程中。最后再解决这些问题后，我的程序终于可以满足课程设计的题目要求，实现了题目中要求的功能。通过这次程序分析，我发现递归调用的确是一种简便的算法，不仅对于程序的时间以及空间复杂度有很好的控制作用，而且算法思想也比较简单易懂。但是，表面的简单带来的是一旦出现错误就很难检验的弊端。递归中的错误需要我们能在头脑中想象模拟出函数递归调用的全过程，尤其是明晰当前层次于当前位置，准确判定数据传递流程。所以在今后的程序设计中，我们应对此有充分的认识，预先将可能出现的问题罗列并提出解决预案。在算法设计中，时刻保持注意，在编写时提高代码书写准确度，避免因低级错误造成的规错误。但对于递归算法的使用，最重要的一点就是：慎重使用递归算法，假如对于自己的递归算法熟练度没有足够的把握，还是不要轻易使用递归算法，而是寻求其它替代算法。2.算法的时间复杂度和空间复杂度的分析，改进设想：时间复杂度：由于大量使用递归算法，我的程序时间复杂度主要表现在函数的递归调用次数，而这又取决于输入的数据规模。所以从总体来看，我的程序时间复杂度为O（n），而且酒就我个人而言我还算满意。空间复杂度：由于输入数据的规模不可预计，而且属于不可缩减部分，因而因此所产生的空间复杂度可以不予考虑。而对于程序储存所需的空间按照以往的要求也是可以忽略不计的。在这里我主要分析讨论程序运行所需的辅助空间。在二叉树中由于需要能具备储存运算数和运算符（即double型数据，int型数据和char型数据），所以在构建二叉树结构体时我在其中设立了三个数据项。但在实际运行时，由于其中设立了识别控制变量（int型）来标识结构体中的数据类型，因而运算数和运算符不会同时储存在一个结构体中，必将会造成空间的浪费。现在想来，假如将char型数据和int型数据和double型数据统一转化为一种数据格式进行储存，并用识别控制变量进行标记，在以后的程序数据读取和计算中，先对识别控制变量进行判断，再将数据域中的数据转化为相应类型，如此一来程序的空降利用率必将会有很大提高。4.5 附录#include #include #include math.h#define OK 1#define ERROR 0#define OVERFLOW -2#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef char TElemType;typedef double Status;/*-创建二叉树结构体-*/typedef struct nodeTElemType OPTR;/运算符Status OPND;/运算数int data;/识别控制变量，0为运算符，1为运算数，2为变量struct node *lchild,*rchild;BinTNode;typedef BinTNode *BiTree;/*-创建栈结构体-*/typedef struct ITdouble data;IT;/*-创建栈结构体指针-*/typedef struct IT *base; IT *top; int stacksize; SqStack;/*-栈的初始化-*/ Status InitStack(SqStack *S) S-base=(IT *)malloc(STACK_INIT_SIZE*sizeof(IT); if(!S-base)exit(OVERFLOW); /检验栈是否创建成功 S-top=S-base; S-stacksize=STACK_INIT_SIZE; return OK;/*-取栈顶-*/Status GetTop(SqStack *S,IT *e) if(S-top=S-base)return ERROR; /检验栈是否为空 *e=*(S-top-1); return OK; /*-压入数据-*/ Status Push(SqStack *S,IT *e)SqStack A; if(S-top-S-base=S-stacksize) /检验栈是否为空 A.base=(IT *)realloc(S-base,(S-stacksize+STACKINCREMENT)*sizeof(IT); if(!A.base)exit(OVERFLOW); /检验再次分配空间是否成功 S-base=A.base; S-top=S-base+S-stacksize; S-stacksize+=STACKINCREMENT; *S-top+=*e;return OK;/*-删除栈顶-*/Status Pop(SqStack *S,IT *e) if(S-top=S-base)return ERROR; *e=*(-S-top); return OK;/*-创建二叉树(递归先序输入)-*/Status ReadExpr(BiTree *T)char ch;double ah=0;scanf(%c,&ch);if (ch= ) *T=NULL;else if(!(*T=(BinTNode*)malloc(sizeof(BinTNode) exit(OVERFLOW); if(ch=0&ch=0&chOPND=ah; (*T)-data=1; else if(ch=a&chOPTR=ch; (*T)-data=2; else (*T)-OPTR=ch; (*T)-data=0; ReadExpr(&(*T)-lchild); ReadExpr(&(*T)-rchild); return OK;/*-递归中序遍历二叉树（表达式输出）-*/Status WriteExpr(BiTree *T)BiTree p; if(*T) /检验二叉树是否为空p=(*T)-lchild;if(*T)-data=0&p-data=0&(*T)-OPTR=42|(*T)-OPTR=47)&(p-OPTR=43|p-OPTR=45)|(*T)-OPTR=94)/判断中序输出时是否需要添加括号（左子树）printf(); WriteExpr(&(*T)-lchild);printf();else WriteExpr(&(*T)-lchild);if(*T)-data=2|(*T)-data=0)printf(%c,(*T)-OPTR);else printf(%lf,(*T)-OPND);p=(*T)-rchild;if(*T)-data=0&p-data=0&(*T)-OPTR=42|(*T)-OPTR=47)&(p-OPTR=43|p-OPTR=45)|(*T)-OPTR=45&p-OPTR=43|(*T)-OPTR=47&p-OPTR=42|(*T)-OPTR=94|(*T)-OPTR=42&p-OPTR=47) /判断中序输出时是否需要添加括号（右子树）printf(); WriteExpr(&(*T)-rchild);printf();else WriteExpr(&(*T)-rchild);return OK; elsereturn OK;/*-变量赋值-*/Status Assign2(BiTree T,char a,double b) if(T) /检验二叉树是否为空if(T-data=2&a=T-OPTR) /判别data识控变量是否为2，同时检验变量名T-OPND=b;/递归先序遍历二叉树return OK; elseAssign2(T-lchild,a,b);Assign2(T-rchild,a,b);return OK;else return OK;/*-调用变量赋值函数进行变量赋值-*/void Assign(BiTree T)char a;double b;getchar();scanf(%c,&a);while(a!=#)/输入“”时，变量赋值结束scanf(=%lf,&b);getchar();Assign2(T,a,b);/调用函Status Assign2( )scanf(%c,&a);/*-计算表达式-*/double Value(BiTree T,SqStack *S)IT p,m,n,OUT,a;int e;if(T) /检验二叉树是否为空Value(T-lchild,S);/递归后序遍历表达式Value(T-rchild,S);e=T-data;if(e=1|e=2)/检验识控变量，寻找运算数入栈p.data=T-OPND;Push(S,&p);else /遇到运算符，开始进行计算操作Pop(S,&m); Pop(S,&n);switch(T-OPTR) /检验运算符类型并计算case +:OUT.data=n.data+m.data; Push(S,&OUT);break;case -:OUT.data=n.data-m.data; Push(S,&OUT);break;case *:OUT.data=n.data*m.data; Push(S,&OUT);break;case /:OUT.data=n.data/m.data; Push(S,&OUT);break;case :OUT.data=pow(n.data,m.data); Push(S,&OUT);break;default: return ERROR;GetTop(S,&a);return a.data;void main() BiTree T; SqStack S; InitStack(&S); printf(请按输入表达式的前缀表示 :n); if(ReadExpr(&T) printf(表达式正确!n); WriteExpr(&T); printf(n请为变量赋值 :n); Assign(T); printf(表达式的结果是 :n); printf(%lf,Value(T,&S); getchar(); 5 总结与展望对于这次数据结构课程设计，我可以说感慨良多，首先，通