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

实****报告题目:重言式判别班级:计算机学院姓名:卢魏旭学号:完成日期:2012年11月需求分析试写一个程序,通过真值表判断一个逻辑表达式属于哪一类的表达式基本要求:逻辑表达式从终端输入,长度不超过一行,逻辑运算符包括“|”,“&”和“~”,分别表示或,与和非,运算优先程度递增,但可以由括号改变,即括号内的运算符优先。逻辑变元为大写字母,表达式中任意地方都可以含有空格符。若是重言式或者矛盾式,可以只显示“Trueforever”或者“Falseforever”,否者显示“Statisfactible”,与用户交互,若用户对表达式中变元取定一组值,程序就求出并显示逻辑表达式的值。附加要求,可以根据用户要求,列出该逻辑表达式的真值表。测试数据:1)(A|~A)&(B|~B)2)(A&~A)&C3)A|B|C|D|E|~A……概要设计为实现上述程序功能,以二叉树的结构来存储逻辑表达式,通过一个辅助栈来完成建树过程二叉树的抽象数据类型定义为:ADTBitree{数据对象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[]中记录各个变量各种赋值情况(所有赋值情况的真值结果记录)}此外以栈的存储结构做辅助栈的抽象数据类型定义为:ADTBstack{ 数据对象:D={a|ai<-ElemSet,i=1,2,3…n}数据关系:R1={<ai-1,ai>|ai-1,ai<-D,i=1,2,3…n} 基本操作: creatstack(&S) 操作结果:建立一个空栈S Pushstack(&S,&B) 初始条件:栈S存在操作结果:将一个二叉树的结点入栈 Popstack(&S,&B) 初始条件:栈S存在操作结果:从栈中取出一个二叉树的结点 showstack(S) 初始条件:栈S存在操作结果:访问栈内结点,查看元素信息 Gettop(S) 初始条件:栈S存在操作结果:返回栈顶元素}详细设计#include<>#include<>#include<>#include<>typedefstructBiTnode{ chardata; intvalue; structBiTnode*lchild,*rchild;}*Bitree;typedefstructBstack{ Bitree*top; Bitree*base;};voidcreatstack(Bstack&S){ =(Bitree*)malloc(sizeof(BiTnode)); =;}voidPushstack(Bstack&S,Bitree&B){ *=B; ++;}voidPopstack(Bstack&S,Bitree&B){ --; B=*;}BitreeGettop(BstackS){ return*(-1);}intJudge(charc)//判断字符是运算符还是操作符{ if(c>='A'&&c<='Z'||c>='a'&&c<='z'||c=='0'||c=='1') return1; else return0;}pare(charc1,charc2)//比较两个运算符的优先级{ charc='-1'; switch(c1) { case'|':switch(c2) { 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='<';break; case')':c='>';break; case'#':c='>';break; }break; case'~':switch(c2) { case'|':c='>';break; case'&':c='>';break;