数据结构报告—重言式判别.doc

(完整word版)数据结构报告重言式判别实习报告题目：重言式判别班级：计算机学院12052313 姓名：卢魏旭 学号：12051521 完成日期：2012年11月一、 需求分析试写一个程序，通过真值表判断一个逻辑表达式属于哪一类的表达式基本要求：1） 逻辑表达式从终端输入，长度不超过一行，逻辑运算符包括“|”，“&”和“”，分别表示或，与和非，运算优先程度递增，但可以由括号改变，即括号内的运算符优先。逻辑变元为大写字母，表达式中任意地方都可以含有空格符。2） 若是重言式或者矛盾式，可以只显示“True forever”或者“False forever”，否者显示“Statisfactible”，与用户交互，若用户对表达式中变元取定一组值，程序就求出并显示逻辑表达式的值。3） 附加要求，可以根据用户要求，列出该逻辑表达式的真值表。测试数据：1) (A|A)&(B|B)2) (A&A)&C3) A|B|C|D|E|A二、 概要设计为实现上述程序功能，以二叉树的结构来存储逻辑表达式，通过一个辅助栈来完成建树过程二叉树的抽象数据类型定义为：ADT Bitree数据对象 D：D是具有相同特性的数据元素的集合数据关系 R：基本操作:creatbitree(&B,&S1,&S2,*a)初始条件：树B，栈S1，S2存在操作结果:通过两个辅助的栈S1，S2将元素a值建在二叉树内showtree(B)初始条件：二叉树B存在操作结果：先序遍历二叉树，输出每一个节点中的信息（用于检测）voluation($B,c,value)初始条件：二叉树B存在操作结果：通过先序遍历二叉树，对树中变量为c的结点赋值value excel(B,i,c,v,*x)初始条件：二叉树存在操作结果：通过递归的算法在一维数组v中记录各个变量各种赋值情况（所有赋值情况的真值结果记录）此外以栈的存储结构做辅助栈的抽象数据类型定义为：ADT Bstack数据对象:D=a|ai-ElemSet,i=1,2,3n数据关系:R1=|ai-1,ai -D,i=1,2,3n基本操作：creatstack(&S)操作结果：建立一个空栈SPushstack(&S,&B)初始条件：栈S存在操作结果：将一个二叉树的结点入栈Popstack(&S，&B)初始条件：栈S存在操作结果：从栈中取出一个二叉树的结点showstack(S)初始条件：栈S存在操作结果：访问栈内结点，查看元素信息Gettop(S)初始条件：栈S存在操作结果：返回栈顶元素三、 详细设计#include#include#include#includetypedef struct BiTnodechar data;int value;struct BiTnode *lchild,*rchild;*Bitree;typedef struct BstackBitree *top;Bitree *base;void creatstack(Bstack &S)S.base=(Bitree*)malloc(sizeof(BiTnode);S.top=S.base;void Pushstack(Bstack &S,Bitree &B)*S.top=B;S.top+;void Popstack(Bstack &S,Bitree &B)S.top-;B=*S.top;Bitree Gettop(Bstack S)return *(S.top-1);int Judge(char c) /判断字符是运算符还是操作符if(c=A&c=a&c;break;case &:c=;break;case :c=;break;case (:c=;break;case #:c=;break; break;case &:switch(c2) case |:c=;break;case &:c=;break;case :c=;break;case (:c=;break;case #:c=;break; break;case :switch(c2) case |:c=;break;case &:c=;break;case :c=;break;case (:c=;break;case #:c=;break; break;case (:switch(c2) case |:c=;break;case &:c=;break;case :c=;break;case (:c=;break;case &:c=;break;case :c=;break;case (:c=;break;case ):c=;break;case #:c=;break; break;case #:switch(c2) case |:c=;break;case &:c=;break;case :c=;break;case (:c=data);int creatBiTree(Bitree &B,Bstack &S1,Bstack &S2,char *a) /S1为a操作符栈，为运算数栈 建立二叉树过程类似于算术表达式求值int i=0,len=0,flag=1; char c;Bitree b1;b1=(Bitree)malloc(sizeof(BiTnode);b1-data=#;b1-value=0;b1-lchild=NULL;b1-rchild=NULL;Pushstack(S1,b1); /先在运算符栈里存放一个data值为“#”的结点做标记while(ai)len+;i+;i=0;c=a0;while(c!=#|Gettop(S1)-data!=#)c=ai;if(c= ) /若有空格，直接忽略掉i+;continue;if(i=len)c=#;Bitree b;b=(Bitree)malloc(sizeof(BiTnode); 建立一个树的结点b-data=c;b-value=0;b-lchild=NULL;b-rchild=NULL;if(Judge(c)Pushstack(S2,b); /若是操作数的结点则进栈i+;continue;elsechar c1=compare(Gettop(S1)-data,c);if(c1=-1)flag=0;break;switch(c1)case :printf(执行D“:printf(执行D“”: n); /如果栈顶运算符优先级高，则先建立二叉树char c2=Gettop(S1)-data;Bitree a0,a1; /先取一个运算符和一个操作数，将操作数连接在运算符的右孩子上Popstack(S1,a0);Popstack(S2,a1);a0-rchild=a1;if(c2!=) /如果不是“”运算符，再取一个结点连接在运算符结点的左孩子上Bitree a2;Popstack(S2,a2);a0-lchild=a2;Pushstack(S2,a0);elsePushstack(S2,a0);if(flag) /表达式输入无误则继续进行B=Gettop(S2);return 1;elsereturn 0;void caculate(Bitree B) /采用后序遍历判断逻辑表达式的真值if(B)caculate(B-lchild);caculate(B-rchild);switch(B-data)case |:B-value=B-lchild-value|B-rchild-value;break;case &:B-value=B-lchild-value&B-rchild-value;break;case :B-value=!B-rchild-value;break;case 0:B-value=0;break;case 1:B-value=1;break;void showtree(Bitree B) /先序遍历二叉树if(B)printf(%c ,B-data);showtree(B-lchild);showtree(B-rchild);void voluation(Bitree B,char c,int value)/采用先序遍历为二叉树的变量赋值if(B)if(B-data=c)B-value=value;voluation(B-lchild,c,value);voluation(B-rchild,c,value);void show(char *a)int i=0;while(ai)if(ai= )i+;continue;printf(%c,ai);i+;void excel(Bitree B,int i,char *c,int v,int *x) /采用递归算法为所有的变量赋值，用数组v记录下每一种变量复制后逻辑表达式的真值if(ci!=0)voluation(B,ci,0);i+;excel(B,i,c,v,x);i-;voluation(B,ci,1);i+;excel(B,i,c,v,x);elsecaculate(B);v*x=B-value;(*x)-;int search(char *a,char *ch) /查找表达式中的变量，放入ch数组中int i=0,k=0,flag=1;while(ai) if(ai=A&aivalue);void change(int *b,int x,int sum) /将十进制转换为二进制while(x!=0)bsum=(x%2);x=x/2;sum-;void TrueExcel(char *a,char *ch,int j,int *v2,int *v1) /输出真值表int i=0;while(chi!=0)printf(%c ,chi);i+;printf(|);show(a);printf(n);for(int l=0,m=pow(2,(double)j)-1;lpow(2,(double)j);l+,m-)change(v2,l,j-1);for(int k=0;kj;k+)if(v2k=-1)printf(0 );elseprintf(%d ,v2k);printf(| %dn,v1m);void main()int j=0,i=0,n,v1200,v2200,flag=0;Bitree b;Bstack S1,S2;creatstack(S1);creatstack(S2);char a100,ch10;/a记录表达式,ch记录变量值for(int k=0;k10;k+)/初始化变量数组chk=0;for(int m=0;m200;m+)/初始化真值表数组v2m=-1;v1m=-1;gets(a);/输入表达式j=search(a,ch);/获取所有变量的个数yn=pow(2,(double)j)-1;/要赋值的次数flag=creatBiTree(b,S1,S2,a);/根据表达式建立二叉树if(flag)excel(b,0,ch,v1,&n);/计算所有变量赋值的真值switch(Judge2(v1)case T:printf(表达式为永真式n);break;case F:printf(表达式为永假式n);break;case O:printf(表达式为不确定式n);selfvoluation(b,ch,a);break;elseprintf(表达式输入有误n);TrueExcel(a,ch,j,v2,v1);system(PAUSE);四、 调试分析1、 本程序实现了逻辑表达式的求值，判断，以及真值表的输出，程序的难点在于逻辑表达式的二叉树建立，以及其判断，二叉树的建立creatbitree()依靠两个工作栈实现的，形式类似于算术表达式的求值，不过这里是建树，存放变量的结点作为叶子结点，存放运算符的结点作为根结点，这是自底向上的算符优先法，第二个难点在于对所有的变量的所有情况赋值，这里采用了简单的递归算法，这个算法我自己做的时候花了很长时间来想，excel()递归时候，对每个变量有0和1两种赋值情况，每当递归到最顶层时，调用caculate()算法计算一次真值，然后将值存放到函数携带的一维数组中去。2、 本程序中最核心的算法应该是caculate()算法，采用的是后序遍历的方法，通过根节点的运算符结合左右孩子结点中变量所携带的value值计算真值，并将结果写入到根结点里去，最终一棵树的真值将会存放在树的根结点里（最顶层的那个结点里）。3、 本程序中另一个亮点就是真值表的输出，根据excel()函数中得到的真值数组v，然后将对应的变量值输出来，这里巧妙的采用将十进制转二进制的方法把各种赋值情况列出来，比较新颖，详情见测试结果。4、 讨论时间复杂度，这里面涉及到递归的算法，无论是先序还是后序遍历，时间复杂度都是O(n),5、 本程序中，采用二叉树的形式记录逻辑表达式，便于管理和赋值，充分利用了递归的思想以及先序遍历，后序遍历的优点。程序的思路清晰，不过就是代码有点冗余，算法可能有点复杂了。6、 经验与体会：在本次程序实习中，起步最难，建立二叉树比较陌生，刚开始，对树的概念不是很清晰，不知道以何种方式建树，后面是参照算术表达式求值的方法来建的，总算是学会了一些方法，调试过程很长，花了很多时间在上面，尤其是那个递归求值，和真值表输出，是自己不断探索与尝试想出来的，也算是一种进步与收获。五、 用户手册1、 本程序的运行环境为DOS操作系统，执行文件为：重言式判别.exe。2、 进入演示程序后即显示文本方式的界面3、 键入逻辑表达式，要求变量均为大写，可以输入0和1，输入时确保逻辑表达式是正确的，若像这种（A|B）表达式也是不允许的，因为外面的括号是多余的，本程序没有此判断功能，所以输入的表达式不能有多余的符号。4、 输入表达式后，程序会给出判断类型，如果是不确定行，则与询问用户是否自行赋值，待用户决定后作出相应判断，最后会输出该逻辑表达式的真值表以供用户参考。六、 测试结果如图所示七、 附录源程序文件名清单：重言式判别.c+ /主程序八、 验收过程1、 验收时间：周一晚上机时间，6：009：00；2、 验收地点：一教115机房；3、 验收教师：王立波；4、 流程概要：1） 这次验收中，老师没有怎么询问，基本上就是我在按照程序运行的流程讲了每一个算法的功能，同时强化了自己的理解，期间，老师对我的真值表的输出算法比较感兴趣，向其解释了为什么用到了十进制转二进制的办法，个人觉得这是一个取巧的算法，老师比较满意。2） 解答完毕后，老师给出了相应的打分。3） 验收结束。