课程设计报告表达式类型的实现方锐洲Word文档下载推荐.docx
《课程设计报告表达式类型的实现方锐洲Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《课程设计报告表达式类型的实现方锐洲Word文档下载推荐.docx（52页珍藏版）》请在冰点文库上搜索。
2）每当输入一个表达式后，对其中的变量赋值，然后对表达式求值。
3）还有很多测试的数据，详细请见附上的文件Test.txt。
二、概要设计
1、数据类型的声明：
在这个课程设计中，采用了链表二叉树的存储结构，以及两个顺序栈的辅助存储结构
/*头文件以及存储结构*/
#include<
stdio.h>
conio.h>
stdlib.h>
string.h>
#defineTRUE1
#defineFALSE0
#defineOK1
#defineERROR0
#defineOVERFLOW0
typedefintStatus;
2、表达式的抽象数据类型定义
ADTExpression{
数据对象D：
D是具有数值的常量C和没有数值的变量V；
数据关系：
R={<
（V或者C）P（V或者C）>
|V,C∈D,<
表示由运算符P结合起来的表达式E}
基本操作：
StatusInput_Expr（&
string,flag）
操作结果：
以字符序列的形式输入语法正确的前缀表达式，保存到字符串string；
参数flag表示输出的提示信息是什么，输入成功返回OK，否则，返回ERROR。
voidjudge_value（&
E,&
string,i）
初始条件：
树E存在，表达式的前缀字符串string存在；
判断字符string[i]，如果是'
0'
-'
9'
常量之间，二叉树结点E存为整型；
否则，存为字符型。
StatusReadExpr（&
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是否还存在没有赋值的变量，以便求算数表达式E的值。
longValue（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中所有常数运算。
}ADTExpression
3、整体设计
在这个课程设计中，有两个源代码文件：
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；
对于栈SqStack1:
StatusInitStack1（SqStack1*S）/*构造一个空栈S*/
StatusStackEmpty1（SqStack1S）/*若栈S为空栈，则返回TRUE，否则返回FALSE*/
StatusPush1（SqStack1*S,SElemType1e）/*插入元素e为新的栈顶元素*/
StatusPop1（SqStack1*S,SElemType1*e）/*若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；
StatusGetTop1（SqStack1S,SElemType1*e）/*若栈不空，则用e返回S的栈顶元素，并返回OK；
顺序栈的基本操作的算法见程序清单。
《二》expression.c文件的整体结构
1、主程序模块的整体流程
可以从主菜单函数可以明了的了解的程序的整体流程，主菜单函数menu（）如下：
charmenu（）
{
charchoice;
printf（"
\n****************************************"
）;
\n1>
输入正确的前缀表达式"
\n2>
带括弧的中缀表示式输出"
\n3>
对变量进行赋值"
\n4>
对算数表达式求值"
\n5>
构造一个新的复合表达式"
\n6>
以表达式的原书写形式输入"
\n7>
合并表达式中所有常数运算"
\n0>
退出"
\n请输入你的选择>
"
choice=getche（）;
returnchoice;
}
在主函数中，采用多分支程序设计语句switch（）使程序产生不同的流向，从而达到实现课程设计的各个要求。
voidmain（）
{
while
（1）
清屏；
switch（主菜单）
{
根据不同的选择，调用不同的操作函数，完成各个操作；
}
}
2、本程序有四个模块，主程序模块，二叉树模块，两个顺序栈模块。
四者的调用关系如下：
主程序模块中的对于表达式的存储结构调用了二叉树模块，而在构造表达式的二叉树模块中又调用了顺序栈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;
SElemType1*top;
}SqStack1;
/*顺序栈SqStack1*/
相关的基本操作见上面的“expression.h文件的整体结构”的说明，详细的算法设计见附录的程序清单。
3、表达式的基本操作
StatusInput_Expr（char*string,intflag）;
/*以字符序列的形式输入语法正确的前缀表达式，保存到字符串string*/
/*参数flag=0表示输出的提示信息是"
请输入正确的前缀表示式：
*/
/*flag=1表示输出的提示信息为"
请以表达式的原书写形式输入正确表示式：
voidjudge_value（BiTree*E,char*string,inti）;
/*判断字符string[i]，如果是'
常量之间，二叉树结点存为整型；
否则，存为字符型*/
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为表示是否赋值过的标志*/
longOperate（intopr1,charopr,intopr2）;
/*运算符运算求值，参数opr1,opr2为常量，opr为运算符，根据不同的运算符，实现不同的运算，返回运算结果*/
StatusCheck（BiTreeE）;
/*检查表达式是否还存在没有赋值的变量，以便求算数表达式的值*/
longValue（BiTreeE）;
/*对算术表达式求值*/
voidCompoundExpr（charP,BiTree*E1,BiTreeE2）;
/*构造一个新的复合表达式*/
StatusRead_Inorder_Expr（char*string,char*pre_expr）;
/*以表达式的原书写形式输入，表达式的原书写形式字符串string变为字符串pre_expr，后调用reversal_string（）函数反转得到前缀表达式pre_expr*/
voidMergeConst（BiTree*E）;
/*常数合并操作函数，合并表达式E中所有常数运算*/
下面列出部分基本操作的伪码算法，未列出的请见程序清单。
其中部分基本操作的伪码算法如下：
4、主程序和其他伪码算法
switch（menu（））
case'
1'
:
/*输入正确的前缀表达式*/
if（Input_Expr（Expr_String,0））输入正确的前缀表达式
if（ReadExpr（&
E,Expr_String））构造表达式
{flag=1;
printf（"
\n表达式构造成功！
2'
/*带括弧的中缀表示式输出*/
if（flag==1）WriteExpr（E）;
elseprintf（"
\n表达式未构造成功！
请构造成功的表达式！
3'
/*对变量进行赋值*/
if（flag==1）
{
flushall（）;
/*清理缓冲区*/
V=getchar（）;
scanf（&
c）;
Assign（&
Assign_flag）;
}
elseprintf（"
4'
/*对算数表达式求值*/
{
if（Check（E））
{result=Value（E）;
WriteExpr（E）;
printf（result）;
}
5'
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）;
}
elseprintf（"
\n复合新的表达式失败！
请按任意键返回主菜单！
6'
/*以表达式的原书写形式输入*/
if（Input_Expr（string,1））
if（Read_Inorder_Expr（string,Expr_String））
reversal_string（Expr_String）;
if（ReadExpr（&
E,Expr_String））
7'
/*合并表达式中所有常数运算*/
if（flag==1）MergeConst（&
E）;
/*退出*/
5、函数的调用关系
除了主函数main（）外，其他各个函数相对于其它函数来说是独立的，函数的使用都由主函数main（）调用使用的，可以简单的说，各个函数都是主函数下的从函数。
四、设计和调试分析
1、在起初设计上，针对前缀表达式的要求构造表达式E，常量的范围限定在0-9之间，后在这个构造表达式的架构上逐个逐个实现对表达式上的操作；
后扩展到以表达式的原书写形式输入，整体架构是不变的，只是增加一些细节的处理功能。
这样的设计从开始到最后都处于可扩展的模块化设计。
2、在算法设计中，构造表达式树的时候，本来以为使用递归构造表达式会很难做到出错处理的，所以采用了顺序栈辅助构造方法，并且尽可能地对程序进行完善，出错处理。
但是经过与同学的相互讨论和研究，发现自己的想法犯了很大的错误，递归构造表达式对于出错处理很简单也很完善，这一点让我加深了递归的使用和理解。
3、在对各个功能操作的实现上，时间复杂度大多数是O（n），空间上增加了辅助栈，空间复杂度为O（n+s）。
而在以原表达式形式输入操作上，实际上是对字符串的操作，将一串原表达式字符串处理为前缀表达式字符串而已，算法时间复杂度取决于输入的字符串的长度n，即O（n），空间复杂度为O（2n+s）。
整体的算法设计没有什么可取之处，对于减少时间复杂度和空间复杂度上没有什么细细考虑。
4、在调试的过程中，花费时间最为多的是对输入错误表达式的出错处理，更改增加的代码几乎都是为了出错处理，但是，觉得这样的调试才更能锻炼一个人的编程能力。
课程设计注重的不单单只是基本程序的完成，更多注重的是出错处理和界面的美化！
五、用户手册
1、本程序的运行环境为DOS操作系统，执行文件为：
expression.exe；
2、进入演示程序后首先出现一个主菜单，主菜单界面如下：
3、之后输入你的选择，进入你所要进行的操作中。
六、测试
《一》选择‘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）’，经过多次合并，得出最后结果
这个合并常数操作唯一的缺点就是要多次操作，但是，这个缺点也不能说为缺点，它可以很清晰的反映出表达式求值的步骤！
经过对各个操作的测试，可以这样总结的说，基本完成了课程设计的要求，虽说其中有一些操作还存在BUG需要去完善改进。
七、课程设计的心得和体会以及问题
此次课程设计相对于我来说，难度适中，相对于这个学期写的那些小算法来说，这个课程设计能充分发挥出学习数据结构后的能力；
而相对于之前做的设计性实验，又有了实际的应用，现实应用度增加。
从接触C语言编程到现在，我就觉得：
编程不是简简单单的写出程序，更多的是出错处理和界面设计。
这次课程设计中，更让我深刻体会到这个道理。
编出大体的程序架构，花费了我的时间不多，而花费了我很多时间的是在调试和测试数据上！
这次课程设计，不仅训练了我对VisualC++6.0的调试器的操作的熟练度；
而且，让我在发现问题解决问题中深刻地理解到完善程序的重要性。
这次课程设计在技术上的学习上，我觉得，让我更懂得递归！
递归的使用更加熟练，递归的分析更加清晰，递归的思想更加深化！
做课程设计，我觉得，第一点是架构，一个好的架构，可以让细节更完善；
在这次课程设计中，我首先确定的是一个架构——前缀表达式构造表达式为架构——其余的操作都是在这个架构上
升级会员 