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

(完整word版)数据结构报告—重言式判别
实习报告
题目：重言式判别
班级：计算机学院12052313 姓名：卢魏旭 学号：12051521 完成日期：2012年11月

一、 需求分析
试写一个程序，通过真值表判断一个逻辑表达式属于哪一类的表达式
基本要求：
1） 逻辑表达式从终端输入，长度不超过一行，逻辑运算符包括“|”，“&”和“~”，分别表示或，与和非，运算优先程度递增，但可以由括号改变，即括号内的运算符优先。逻辑变元为大写字母，表达式中任意地方都可以含有空格符。
2） 若是重言式或者矛盾式，可以只显示“True forever”或者“False forever”，否者显示“Statisfactible”，与用户交互，若用户对表达式中变元取定一组值，程序就求出并显示逻辑表达式的值。
3） 附加要求，可以根据用户要求，列出该逻辑表达式的真值表。
测试数据：
1) (A|~A)&(B|~B)
2) (A&~A)&C
3) 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,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<stdio.h>
#include<malloc.h>
#include<windows.h>
#include<math.h>
typedef struct BiTnode
{
char data;
int value;
struct BiTnode *lchild,*rchild;
}*Bitree;
typedef struct Bstack
{
Bitree *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<='Z'||c>='a'&&c<='z'||c=='0'||c=='1')
return 1;
else
return 0;
}
char compare(char c1,char c2) //比较两个运算符的优先级
{
char c='-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;
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;
}break;
case '#':switch(c2)
{
case '|':c='<';break;
case '&':c='<';break;
case '~':c='<';break;
case '(':c='<';break;
case '#':c='=';break;
}break;
}
return c;
}
void showstack(Bstack S)
{
while(S.base!=S.top)
{
S.top--;
printf("%c\n",(*S.top)->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(a[i])
{len++;i++;}
i=0;
c=a[0];
while(c!='#'||Gettop(S1)->data!='#')
{
c=a[i];
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;
}
else
{
char c1=compare(Gettop(S1)->data,c);
if(c1=='-1')
{
flag=0;
break;
}
switch(c1)
{
case '<':printf("执行D“<”:\n ");Pushstack(S1,b);i++;break;
case '=':printf("执行D“=”: \n");
if(c!='#')
{Popstack(S1,b);i++;break;}
else
break;
case '>':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);
}
else
Pushstack(S2,a0);
}
}
}
if(flag) //表达式输入无误则继续进行
{
B=Gettop(S2);
return 1;
}
else
return 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(a[i])
{
if(a[i]==' ')
{i++;continue;}
printf("%c",a[i]);
i++;
}
}

void excel(Bitree B,int i,char *c,int v[],int *x) //采用递归算法为所有的变量赋值，用数组v[]记录下每一种变量复制后逻辑表达式的真值
{
if(c[i]!='0')
{
voluation(B,c[i],0);
i++;
excel(B,i,c,v,x);
i--;
voluation(B,c[i],1);
i++;
excel(B,i,c,v,x);
}
else
{
caculate(B);
v[*x]=B->value;
(*x)--;
}
}

int search(char *a,char *ch) //查找表达式中的变量，放入ch[]数组中
{
int i=0,k=0,flag=1;
while(a[i])
{
if(a[i]>='A'&&a[i]<='Z')
{
int j=0;
while(ch[j]!='0')
{
if(ch[j]==a[i])
{
flag=0;
break;
}
j++;
}
if(flag)
{
ch[k]=a[i];
k++;
}
}i++;flag=1;
}
// printf("%d \n",k);
return k;
}

char Judge2(int *v) //根据所有赋值情况，判断逻辑表达式是哪种类型的
{
int i=0,flag1=0,flag2=0,flag3=0;
while(v[i]!=-1)
{
if(v[i]==0)
flag1=1;
if(v[i]==1)
flag2=1;
if(flag1&&flag2)
return 'O';
i++;
}
if(flag1)
return 'F';
if(flag2)
return 'T';
}

void selfvoluation(Bitree b,char ch[],char a[]) //用户自行赋值
{
printf("是否自行为表达式赋值以计算真值?(Y/N)\n");
char c;
c=getchar();
if(c=='Y'||c=='y')
{
int k=0,x;
while(ch[k]!='0')
{
printf("为%c赋值：êo%c=",ch[k],ch[k]);
scanf("%d",&x);
while(x!=0&&x!=1)
{
printf("赋值有误！！请重新输入：");
scanf("%d",&x);
}
voluation(b,ch[k],x);
k++;
}
caculate(b);
printf("表达式? ");
show(a);
printf(" 的真值为%d\n",b->value);
}
}

void change(int *b,int x,int sum) //将十进制转换为二进制
{
while(x!=0)
{
b[sum]=(x%2);
x=x/2;
sum--;
}
}

void TrueExcel(char *a,char *ch,int j,int *v2,int *v1) //输出真值表
{
int i=0;
while(ch[i]!='0')
{
printf("%c ",ch[i]);
i++;
}
printf("|");
show(a);
printf("\n");
for(int l=0,m=pow(2,(double)j)-1;l<pow(2,(double)j);l++,m--)
{
change(v2,l,j-1);
for(int k=0;k<j;k++)
{
if(v2[k]==-1)
printf("0 ");
else
printf("%d ",v2[k]);
}
printf("| %d\n",v1[m]);
}
}

void main()
{
int j=0,i=0,n,v1[200],v2[200],flag=0;
Bitree b;
Bstack S1,S2;
creatstack(S1);
creatstack(S2);
char a[100],ch[10]; //a[]记录表达式,ch[]记录变量值
for(int k=0;k<10;k++) //初始化变量数组
ch[k]='0';
for(int m=0;m<200;m++) //初始化真值表数组
{
v2[m]=-1;
v1[m]=-1;
}
gets(a); //输入表达式
j=search(a,ch); //获取所有变量的个数y
n=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;
}
}
else
printf("表达式输入有误\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：00—9：00；
2、 验收地点：一教115机房；
3、 验收教师：王立波；
4、 流程概要：
1） 这次验收中，老师没有怎么询问，基本上就是我在按照程序运行的流程讲了每一个算法的功能，同时强化了自己的理解，期间，老师对我的真值表的输出算法比较感兴趣，向其解释了为什么用到了十进制转二进制的办法，个人觉得这是一个取巧的算法，老师比较满意。
2） 解答完毕后，老师给出了相应的打分。
3） 验收结束。