数据结构报告重言式判别Word文件下载.docx
《数据结构报告重言式判别Word文件下载.docx》由会员分享，可在线阅读，更多相关《数据结构报告重言式判别Word文件下载.docx（22页珍藏版）》请在冰点文库上搜索。
先序遍历二叉树，输出每一个节点中的信息（用于检测）
voluation（$B,c,value）
通过先序遍历二叉树，对树中变量为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，&
从栈中取出一个二叉树的结点
showstack（S）
访问栈内结点，查看元素信息
Gettop（S）
返回栈顶元素
}
三、详细设计
#include<
stdio.h>
malloc.h>
windows.h>
math.h>
typedefstructBiTnode
chardata;
intvalue;
structBiTnode*lchild,*rchild;
}*Bitree;
typedefstructBstack
Bitree*top;
Bitree*base;
};
voidcreatstack（Bstack&
S.base=（Bitree*）malloc（sizeof（BiTnode））;
S.top=S.base;
voidPushstack（Bstack&
S,Bitree&
*S.top=B;
S.top++;
voidPopstack（Bstack&
S.top--;
B=*S.top;
BitreeGettop（BstackS）
return*（S.top-1）;
intJudge（charc）//判断字符是运算符还是操作符
if（c>
='
A'
&
c<
Z'
||c>
a'
z'
||c=='
0'
1'
）
return1;
else
return0;
charcompare（charc1,charc2）//比较两个运算符的优先级
charc='
-1'
;
switch（c1）
{
case'
|'
:
switch（c2）
{
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='
value=0;
lchild=NULL;
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;
if（Judge（c））
{
Pushstack（S2,b）;
//若是操作数的结点则进栈
i++;
continue;
}
else
charc1=compare（Gettop（S1）->
data,c）;
if（c1=='
flag=0;
break;
}
switch（c1）
case'
printf（"
执行D“<
”:
\n"
）;
Pushstack（S1,b）;
执行D“=”:
\n"
if（c!
{Popstack（S1,b）;
else
break;
执行D“>
//如果栈顶运算符优先级高，则先建立二叉树
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
if（flag）//表达式输入无误则继续进行
B=Gettop（S2）;
voidcaculate（BitreeB）//采用后序遍历判断逻辑表达式的真值
if（B）
caculate（B->
lchild）;
rchild）;
switch（B->
data）
B->
value=B->
lchild->
value||B->
rchild->
value;
value&
value=!
value=1;
voidshowtree（BitreeB）//先序遍历二叉树
%c"
B->
showtree（B->
voidvoluation（BitreeB,charc,intvalue）//采用先序遍历为二叉树的变量赋值
if（B->
data==c）
B->
value=value;
voluation（B->
lchild,c,value）;
rchild,c,value）;
voidshow（char*a）
inti=0;
if（a[i]=='
}
%c"
a[i]）;
i++;
voidexcel（BitreeB,inti,char*c,intv[],int*x）//采用递归算法为所有的变量赋值，用数组v[]记录下每一种变量复制后逻辑表达式的真值
if（c[i]!
voluation（B,c[i],0）;
excel（B,i,c,v,x）;
i--;
voluation（B,c[i],1）;
caculate（B）;
v[*x]=B->
（*x）--;
intsearch（char*a,char*ch）//查找表达式中的变量，放入ch[]数组中
inti=0,k=0,flag=1;
while（a[i]）
if（a[i]>
a[i]<
intj=0;
while（ch[j]!
if（ch[j]==a[i]）
{
flag=0;
}
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'
if（flag1）
return'
F'
if（flag2）
T'
voidselfvoluation（Bitreeb,charch[],chara[]）//用户自行赋值
printf（"
是否自行为表达式赋值以计算真值?
（Y/N）\n"
c=getchar（）;
if（c=='
Y'
y'
intk=0,x;
while（ch[k]!
printf（"
为%c赋值：
ê
o%c="
ch[k],ch[k]）;
scanf（"
%d"
&
x）;
while（x!
=0&
x!
=1）
printf（"
赋值有误！
！
请重新输入：
"
scanf（"
voluation（b,ch[k],x）;
k++;
caculate（b）;
表达式?
"
show（a）;
的真值为%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）//输出真值表
while（ch[i]!
ch[i]）;
|"
show（a）;
\n"
for（intl=0,m=pow（2,（double）j）-1;
l<
pow（2,（double）j）;
l++,m--）
change（v2,l,j-1）;
for（intk=0;
k<
j;
k++）
if（v2[k]==-1）
0"
else
%d"
v2[k]）;
|%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;
10;
k++）//初始化变量数组
ch[k]='
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））
表达式为永真式\n"
表达式为永假式\n"
表达式为不确定式\n"
selfvoluation（b,ch,a）;
表达式输入有误\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）验收结束。
升级会员 