课程设计报告 - 重言式的判别

合肥学院 计算机科学与技术系

课程设计报告

目录

1、题目 ???????????????????????????????? 3 2、问题分析和任务定义 ????????????????????????? 4 3、数据结构的选择和概要设计 ?????????????????????? 5 4、详细设计和编码 ??????????????????????????? 8 5、上机调试过程 ???????????????????????????? 17 6、测试结果及其分析 ?????????????????????????? 19 7、用户使用说明 ???????????????????????????? 20 8、参考文献 ?????????????????????????????? 20 9、附录（完整程序代码）????????????????????????? 21

1

第一章 题目

“数据结构与算法课程设计”是计算机科学与技术专业学生的集中实践性环节之一，是学习“数据结构与算法”理论和实验课程后进行的一次全面的综合练习。其目的是要达到理论与实际应用相结合，提高学生组织数据及编写程序的能力，使学生能够根据问题要求和数据对象的特性，学会数据组织的方法，把现实世界中的实际问题在计算机内部表示出来并用软件解决问题，培养良好的程序设计技能。 内容：【问题描述】

一个逻辑表达式如果对于其变元的任一种取值都为真，则称为重言式；反之，如果对于其变元的任一种取值都为假，则称为矛盾式；然而，更多的情况下，既非重言式，也非矛盾式。试写一个程序，通过真值表判别一个逻辑表达式属于上述哪一类。 【基本要求】

(1) 逻辑表达式从终端输入，长度不超过一行。逻辑运算符包括 \，\和 \，分别表示或、与和非，运算优先程度递增，但可由括号改变，即括号内的运算优先。逻辑变元 为大写字母。表达式中任何地方都可以含有多个空格符。

(2) 若是重言式或矛盾式，可以只显示\，或\，否则显示 \以及变量名序列，与用户交互。若用户对表达式中变元取定一组值，程序就求出并显示逻辑表达式的值。 【测试数据】 (1) (A|~A)&(B|~B) (2) (A&~A)&C (3) A|B|C|D|E|~A (4) A&B&C&~B (5) (A|B)&(A|~B) (6) A&~B|~A&B

第二章 问题分析和任务定义

1、 一个逻辑表达式如果对于其变元的任一种取值均为真，则称为重言式；反之，如果对于其变元的任一种取值都为假，则称为矛盾式，然而，更多的情况下，既非重言式，也非矛盾式，写一个程序通过真值表判别一个逻辑表达式属于上述哪一类。基本要求如下： 2、 逻辑表达式从终端输入，长度不超过一行。逻辑运算符包括“|”、“&”、“~”，分别表示或、与、非，运算优先程度递增，但可有括号改变，即括号内的运算优先。逻辑变元为大写字母。表达式中任何地方都可以含有多个空格符。

3、 若是重言式或矛盾式，可以只显示“True Forever”或“False Forever”，否则显示运算中每种赋值和与其相对应的表达式的值。

4、 本程序先使用栈将逻辑表达式的变量进行存储，然后将栈中的元素作为二叉树的结点结构，然后根据优先级读取表达式建立二叉树，并通过逐个判断实现对重言式的判别。 5、程序执行的命令： 输入逻辑表达式。

判断表达式是重言式还是矛盾式。 退出程序。

2

6、细节设置

为实现用户更好的操作，程序应允许在表达式中插入多个空格，对大小写没有特殊要求，并含有较多的提示信息，一方便用户操作。 第三章 数据结构的选择和概要设计 流程图

开始 main meun 3 1 输入表达式 1. 2. 3. 计算机 用户 3.返回 建树 结束 2 建树 计算机穷举 Y 用户输入变量值 本章主要介绍 1、数据结构的设计

//根据表达式建立的二叉树的结点定义，由于表达式的求值类似二叉树的中序遍历，故我们可以ijiang表达式构造为一个二叉树; typedef struct btdnode{}*bitree;

//识别表达式使用的堆栈定义,它存放的都是树的结构，鉴于逻辑符号的优先不同，我们需要用到堆栈;

typedef struct lnode_optr{}sqstack;

2、算法的设计

本设计从总体上划分可分为四个模块， 第一个模块为树与堆栈的创建。

void create(bitree &zigen,bitree l,bitree r){}； void creatstack(sqstack &st){}；

void creattree(char s[],bitree &tree){}；

第二个模块为对树与堆栈的操作，包括对树的取值以及堆栈的入栈，出栈操作。

3

输出结果 N 继续 int value_tree(bitree tree){}； void push(sqstack &st,bitree e){}； void pop(sqstack &st,bitree &e){} 第三个模块为对表达式的逻辑运算符的判别。 char youxianji(char lie,char hang){}； void gettop(sqstack &st,bitree &e){}； 第四个模块为于用户的交互。 void user(){}；

3、抽象数据类型的 设计

根据所设计的数据结构和 函数接口，设计抽象数据类型。 ADT Binary Tree{

数据对象：D是具有相同特性的数据元素的集合。 二叉树数据关系：

若D为空集，称BinaryTree 为空二叉树； 否则 关系 R={H}；

在D中存在唯一的成为根的数据元素root，它在关系H下无前驱；

D中其余元素必可分为两个互不相交的子集L和R，每一个子集都是一棵符合本定义的二叉树，并分别为root的左子树和右子树。如果左子树L不空，则必存在一个根结点，它是root的“左后继”（∈H）,如果右子树R不空，则必存在一个根结点为root的“右后继”（∈H）。 基本操作P： {结构初始化}

initBiTree（&T）； 操作结果：构造二叉树T。

CreateBiTree（&T，definition）；

初始条件：definition给出二叉树T的定义。 操作结果：按definition构造二叉树T。 DestroyBiTree（&T）； 初始条件：二叉树T存在。 操作结果：销毁二叉树T。

{销毁结构}

{引用型操作} BiTreeEmpty（T）；

初始条件：二叉树T存在。

操作结果：若二叉树为空二叉树，则返回TRUE，否则返回FALSE。

和数相同，创建二叉树的算法取决于它的数据元素之间关系的输入方式。

Root（T）

初始条件：二叉树T存在。 操作结果：返回T的根。

4

Value（T，e） 初始条件：二叉树T存在，e是T中某个结点。

操作结果：返回e的值。

Parent（T,e）；

初始条件：二叉树T存在，e是T中某个结点。

操作结果：若e是T的非根结点，则返回它的双亲，否则返回“空”。 LeftChild（T,e）；

初始条件：二叉树T存在，e是T中某个结点。

操作结果：返回T的左孩子，若e无左孩子，则返回“空”。 RightChild（T,e）；

初始条件：二叉树T存在，e是T中某个结点。

操作结果：返回T的右孩子，若e无左孩子，则返回“空”。

}

堆栈数据关系： ADT Stack{ InitStack(&S) 操作结果：构造一个空栈。 DestroyStack(&S)

初始条件：栈S存在。

操作结果：栈S被销毁。

GetTop（S,&e）

初始条件：栈S已存在且非空。

操作结果：用e返回S的栈顶元素。

Push（&S，e）

初始条件：栈S已存在。

操作结果：插入结点为e的新的栈顶元素。

Pop（&S，&e）

初始条件：栈S已存在且非空。

操作结果：删除S的栈顶元素，并用e返回其值。

}

5

第四章 详细设计和编码 一、设计结构体

typedef struct node //根据表达式建立的二叉树的结点定义 {

char data;

struct node *lchild; struct node *rchild; }BiTNode,*bitree;

typedef struct stack //识别表达式使用的堆栈定义,它存放的都是树的结构{ //栈中的元素都是树的结点结构 bitree *base; //栈底指针 bitree *top; //栈顶指针 int stacksize; //栈容量 }seqstack;

二、设计功能子函数

//用于产生变量的各种取值组合 void creatzuhe(int n) { int i,num=0,j=0,e; int temp[maxsize]; for(i=0;i=0) {

e=temp[j]; j--; zuhe[num]=e;

num++;

}

6

}

//自底向上地根据运算符地优先级来建立分子树函数

void create(bitree &f,bitree l,bitree r) //当逻辑表达式读完后-子根f就是一棵完整的二叉树 {

f->lchild=l; //分树的链接 f->rchild=r; //分树的链接 if(l&&r) { if(int(l->data)>=65&&int(l->data)<=90) //左子树

{

l->lchild=NULL; l->rchild=NULL; } if(int(r->data)>=65&&int(r->data)<=90) //右子树

{

r->lchild=NULL; r->rchild=NULL; } }

}

//逻辑运算符的优先级判别 char youxianji(char m,char n) {

int i,j;

char bijiao[7][7]={' ','|','&','~','(',')','#', //二维数组比较优先级先后 '|','>','<','<','<','>','>', '&','>','>','<','<','>','>',

'~','>','>','>','<','>','>', '(','<','<','<','<','=',' ', ')','>','>','>',' ','>','>', '#','<','<','<','<',' ','='}; for(i=0;i<7;i++)

if(bijiao[0][i]==m) //找到m运算符的列号 break;

for(j=0;j<7;j++) //找到n运算符的行号 if(bijiao[j][0]==n) break;

7

return bijiao[j][i]; //返回优先级的符号:>、<、= }

//初始化栈

void setstack(seqstack &st) {

st.base=(bitree *)malloc(maxsize*sizeof(node));//分配结构node的size大小的内存,强制转换为bitree类型 st.top=st.base;

st.stacksize=maxsize; //栈容量 } //入栈

void push(seqstack &st,bitree e) {

if(st.top-st.base

*st.top=e; st.top++; }

else cout<<\不符合输出ERROR!!! } //出栈

void pop(seqstack &st,bitree &e) {

if(st.top==st.base) cout<<\不符合条件输出ERROR!!! st.top--; //符合条件 e=*st.top; }

//取栈顶元素

void gettop(seqstack &st,bitree &e) {

if(st.top==st.base) cout<<\不符合条件输出ERROR!!! e=*(st.top-1); //符合取栈顶元素 }

//根据逻辑表达式将数据存入二叉树中，定义两个栈 void creattree(char s[],bitree &tree) {

seqstack variable; //变量栈 seqstack logic; //逻辑运算符栈 setstack(variable); //变量栈初始化

8

setstack(logic); //逻辑运算符栈初始化

bitree logic1,variables,logics,e,a,b,g,kuohao;//定义栈中的元素,g为最后的二叉树的根

logic1=(bitree)malloc(sizeof(node));//分配结构node的size大小的内存,强制转换为bitree类型

logic1->data='#'; //将逻辑运算符栈的栈底元素设为'#' push(logic,logic1); //入逻辑运算符栈 while(*s!=NULL)

{

{

variables=(bitree)malloc(sizeof(node));//分配结构node的size大小的

if(int(*s)>=65&&int(*s)<=90) //读取的是变量

内存,强制转换为bitree类型 variables->data=*s;

push(variable,variables); //入变量栈

} {

else if(int(*s)>90||int(*s)<65) //读取的逻辑运算符

gettop(logic,e); //取运算符栈的栈顶元素进行优先级比较 switch(youxianji(*s,e->data))

{

logics=(bitree)malloc(sizeof(node));//分配结构node的size大小

case '<': //栈顶的运算符优先级低,逻辑运算符进栈 的内存,强制转换为bitree类型 logics->data=*s; push(logic,logics); break;

case '=':

pop(logic,kuohao); //脱括号并接受下一个字符

break;

case '>': //栈顶的运算符优先级高,变量出栈运算

pop(logic,g); //弹出逻辑运算符

pop(variable,a); //弹出变量 b=NULL; //'~'只有右子树 if(g->data!='~') pop(variable,b);

create(g,b,a); //建树的函数调用

push(variable,g);//将临时的根作为新的变量压入变量栈中 if(*s!='#'&&*s!=')')

{

9

logics=(bitree)malloc(sizeof(node));//分配结构node的size

大小的内存,强制转换为bitree类型 logics->data=*s;

push(logic,logics); //逻辑运算符入栈

}

else s=s-1; break; }

//根据变量的取值组合并利用逻辑表达式的性质对树进行求值 int valuetree(bitree tree) {

if(!tree) return 0; //遇到空的结点 else if(tree->data!='|'&&tree->data!='&'&&tree->data!='~') //找到的是变量 return zuhe[int(tree->data)-65]; //返回值 else if(int(tree->data)<65||int(tree->data)>90) //找到的是运算符

switch(tree->data) }

//用户输入变量的一组取值情况 void user() {

int i;

cout<<\请依次输入你的变量取值(0或1)\

10

}

}

}

s++; tree=g;

{ }

else return 0;

return(valuetree(tree->lchild)||valuetree(tree->rchild)); //递归调用 break;

return(valuetree(tree->lchild)&&valuetree(tree->rchild)); //递归调用 break;

return(!valuetree(tree->rchild)); //递归调用 break;

case '|':

case '&':

case '~':

default: return 0;

for(i=65;i<65+N;i++)

{

cout<>zuhe[i-65]; }

//界面设计 void print() {

cout<<\■■■■■■■■■■■■■■■■■■■■■■■■■\标识信息 cout<<\■■ 信息学院 数学系 11 应用数学 ■■\}

cout<<\■■ 数据结构课程设计 ■■\ cout<<\■■ ------重言式的判别 ■■\ cout<<\■■ 曹红强 2013.12.25 ■■\ cout<<\■■■■■■■■■■■■■■■■■■■■■■■■■\}

//菜单函数， void meun() {

system(\ print();

char str[maxsize],stri[maxsize],*pstr,q; int j,i=0,choose=1,sum,n=0; bitree Tree;

int SUM=0,l; //用于累加变量的每种组合的逻辑表达式的结果;可以作为逻辑表达式类别判别的根据

cout<<\■■请输入逻辑表达式的变量的个数: ■■\提示输入表达式的变量个数 cout<<\■■\ cin>>N;

sum=int(pow(2,N)); //变量组合的总数;

cout<<\■■■■请输入逻辑表达式的表达式:例如(~A|B&C) ■■\ scanf(\读取包含多个空格的逻辑表达式 pstr=str;

for(;*pstr!=NULL;pstr++,n++){ //逻辑表达式的正确读取,去除表达式中的空格 if(str[n]>=97&&str[n]<=122) str[n]=str[n]-32; //将小写转换成大写 if(str[n]!=' ') stri[i++]=*pstr; }

stri[i]='#'; //最后一字符后加入'#',与运算符栈的栈底元素'#'对应 stri[i+1]='\\0'; //结束标志'\\0'

11

//system(\系统清屏函数

cout<<\■■■请选择你要的操作■■■■■■■■■■■■■■\ cout<<\■■ 1 计算机自动穷举 ■■\ cout<<\■■ 2 用户自定义设置 ■■\ cout<<\■■ 3 重新开始 ■■\ cout<<\■■ 0 退出 ■■\ cout<<\请选择你要的操作: \提示信息 cin>>choose;

while(choose!=1&&choose!=2&&choose!=3&&choose!=0) {

cout<<\您输入的有误,请您重新输入:\提示信息

cin>>choose; }

switch(choose) {

case 1: //对变量的不同组合依次调用重言式二叉树的求值函数;并判别重言式的类别

// system(\

creattree(stri,Tree); //建立重言式的二叉树

{

for(j=0;j

creatzuhe(j); //产生变量取值组合 SUM+=valuetree(Tree); //SUM累加

}

stri[i]='\\0'; //加入结束标志以便输出逻辑表达式 if(SUM==0) //矛盾式

{

cout<<\逻辑表达式:\ cout<<\} {

cout<<\} {

cout<<\逻辑表达式:\ cout<<\

if(SUM==sum) //重言式 cout<<\逻辑表达式:\

if(SUM>0&&SUM

cout<<\逻辑表达式的真值表 \

12

输出真值表

cout<<\ for(l=65;l<65+N;l++)

cout<

cout<<\ for(j=0;j

{

creatzuhe(j); //产生变量取值组合 //SUM=valuetree(Tree); cout<<\ for(int h=0;h

cout<

cout<<\

} }

//stri[i]='\\0'; //加入结束标志以便输出逻辑表达式

cout<<\是否继续?(Y继续，其它退出)\提示信息 if(q=='y'||q=='Y')

{

getchar();

meun(); //调用菜单函数 } {

system(\系统清屏函数 }

cin>>q;

else

cout<<\■程序结束，谢谢!!!■\ break;

//system(\系统清屏函数 creattree(stri,Tree); //调用 cout<<\逻辑表达式:\ user(); //调用

case 2:

stri[i]='\\0'; //加入结束标志以便输出逻辑表达式

cout<<\逻辑表达式的值为：\

13

cout<<\是否继续?(Y继续，其它字母退出)\ cin>>q; if(q=='y'||q=='Y') {

getchar();

meun(); //调用菜单函数 } else

{

system(\系统清屏函数 cout<<\■程序结束，谢谢!!!■\

}

break; case 3: getchar();

meun(); //调用菜单函数 break;

case 0:

system(\系统清屏函数

cout<<\■您已退出，谢谢使用!!!■\退出提示信息 break;

} } //主函数 void main() {

system(\对界面调颜色 meun(); //调用菜单函数 }

第五章 上机调试过程

问题与解决方法：

在调试过程中出现以下问题：

①error C2065: 'malloc' : undeclared identifier error C2065: 'exit' : undeclared identifier 原因是因为缺少了头文件#include ②在运行过程中，不能有效地解决（）的优先级问题

解决方法：在对树的遍历函数value_tree(bitree tree){}中添加以下语句即

14

if(tree->data=='('){ while(tree->data!='(') value_tree(tree);

}

③不能结局大小写随意输入

在读取表达式时加入

if(str[n]>=97&&str[n]<=122) str[n]=str[n]-32; 第六章 参考文献:

[1] 王昆仑，李红. 数据结构与算法. 北京：中国铁道出版社，2006年5月。 [2] 其它。

15

16

本文来源：https://www.bwwdw.com/article/my3x.html