数据结构报告重言式判别.docx
- 文档编号:18015406
- 上传时间:2023-08-05
- 格式:DOCX
- 页数:22
- 大小:56.53KB
数据结构报告重言式判别.docx
《数据结构报告重言式判别.docx》由会员分享,可在线阅读,更多相关《数据结构报告重言式判别.docx(22页珍藏版)》请在冰点文库上搜索。
数据结构报告重言式判别
实习报告
题目:
重言式判别
班级:
计算机学院12052313姓名:
卢魏旭学号:
12051521完成日期:
2012年11月
一、需求分析
试写一个程序,通过真值表判断一个逻辑表达式属于哪一类的表达式
基本要求:
1)逻辑表达式从终端输入,长度不超过一行,逻辑运算符包括“|”,“&”和“~”,分别表示或,与和非,运算优先程度递增,但可以由括号改变,即括号内的运算符优先。
逻辑变元为大写字母,表达式中任意地方都可以含有空格符。
2)若是重言式或者矛盾式,可以只显示“Trueforever”或者“Falseforever”,否者显示“Statisfactible”,与用户交互,若用户对表达式中变元取定一组值,程序就求出并显示逻辑表达式的值。
3)附加要求,可以根据用户要求,列出该逻辑表达式的真值表。
测试数据:
1)(A|~A)&(B|~B)
2)(A&~A)&C
3)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={
基本操作:
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)
{
S.base=(Bitree*)malloc(sizeof(BiTnode));
S.top=S.base;
}
voidPushstack(Bstack&S,Bitree&B)
{
*S.top=B;
S.top++;
}
voidPopstack(Bstack&S,Bitree&B)
{
S.top--;
B=*S.top;
}
BitreeGettop(BstackS)
{
return*(S.top-1);
}
intJudge(charc)//判断字符是运算符还是操作符
{
if(c>='A'&&c<='Z'||c>='a'&&c<='z'||c=='0'||c=='1')
return1;
else
return0;
}
charcompare(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;
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;
}
returnc;
}
voidshowstack(BstackS)
{
while(S.base!
=S.top)
{
S.top--;
printf("%c\n",(*S.top)->data);
}
}
intcreatBiTree(Bitree&B,Bstack&S1,Bstack&S2,char*a)//S1为a操作符栈,为运算数栈建立二叉树过程类似于算术表达式求值
{
inti=0,len=0,flag=1;
charc;
Bitreeb1;
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='#';}
Bitreeb;
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
{
charc1=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");//如果栈顶运算符优先级高,则先建立二叉树
charc2=Gettop(S1)->data;
Bitreea0,a1;//先取一个运算符和一个操作数,将操作数连接在运算符的右孩子上
Popstack(S1,a0);
Popstack(S2,a1);
a0->rchild=a1;
if(c2!
='~')//如果不是“~”运算符,再取一个结点连接在运算符结点的左孩子上
{
Bitreea2;
Popstack(S2,a2);
a0->lchild=a2;
Pushstack(S2,a0);
}
else
Pushstack(S2,a0);
}
}
}
if(flag)//表达式输入无误则继续进行
{
B=Gettop(S2);
return1;
}
else
return0;
}
voidcaculate(BitreeB)//采用后序遍历判断逻辑表达式的真值
{
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;
}
}
}
voidshowtree(BitreeB)//先序遍历二叉树
{
if(B)
{
printf("%c",B->data);
showtree(B->lchild);
showtree(B->rchild);
}
}
voidvoluation(BitreeB,charc,intvalue)//采用先序遍历为二叉树的变量赋值
{
if(B)
{
if(B->data==c)
B->value=value;
voluation(B->lchild,c,value);
voluation(B->rchild,c,value);
}
}
voidshow(char*a)
{
inti=0;
while(a[i])
{
if(a[i]=='')
{i++;continue;}
printf("%c",a[i]);
i++;
}
}
voidexcel(BitreeB,inti,char*c,intv[],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)--;
}
}
intsearch(char*a,char*ch)//查找表达式中的变量,放入ch[]数组中
{
inti=0,k=0,flag=1;
while(a[i])
{
if(a[i]>='A'&&a[i]<='Z')
{
intj=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);
returnk;
}
charJudge2(int*v)//根据所有赋值情况,判断逻辑表达式是哪种类型的
{
inti=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';
}
voidselfvoluation(Bitreeb,charch[],chara[])//用户自行赋值
{
printf("是否自行为表达式赋值以计算真值?
(Y/N)\n");
charc;
c=getchar();
if(c=='Y'||c=='y')
{
intk=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);
}
}
voidchange(int*b,intx,intsum)//将十进制转换为二进制
{
while(x!
=0)
{
b[sum]=(x%2);
x=x/2;
sum--;
}
}
voidTrueExcel(char*a,char*ch,intj,int*v2,int*v1)//输出真值表
{
inti=0;
while(ch[i]!
='0')
{
printf("%c",ch[i]);
i++;
}
printf("|");
show(a);
printf("\n");
for(intl=0,m=pow(2,(double)j)-1;l { change(v2,l,j-1); for(intk=0;k { if(v2[k]==-1) printf("0"); else printf("%d",v2[k]); } printf("|%d\n",v1[m]); } } voidmain() { intj=0,i=0,n,v1[200],v2[200],flag=0; Bitreeb; BstackS1,S2; creatstack(S1); creatstack(S2); chara[100],ch[10];//a[]记录表达式,ch[]记录变量值 for(intk=0;k<10;k++)//初始化变量数组 ch[k]='0'; for(intm=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)验收结束。 WelcomeTo Download! ! ! 欢迎您的下载,资料仅供参考! 4)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 报告 重言式 判别