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

实习报告 题目：重言式判别 班级：计算机学姓名：卢魏旭 学号完成日期：2012年11月 需求分析 试写一个程序，通过真值表判断一个逻辑表达式属于哪一类的表达式 基本要求： 逻辑表达式从终端输入，长度不超过一行，逻辑运算符包括“|”，“”和“~”，分别表示或，与和非，运算优先程度递增，但可以由括号改变，即括号内的运算符优先。逻辑变元为大写字母，表达式中任意地方都可以含有空格符。 若是重言式或者矛盾式，可以只显示“True forever”或者“False forever”，否者显示“Statisfactible”，与用户交互，若用户对表达式中变元取定一组值，程序就求出并显示逻辑表达式的值。 附加要求，可以根据用户要求，列出该逻辑表达式的真值表。 测试数据： 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存在 操作结果：返回栈顶元素 } 详细设计 #includestdio.h #includemalloc.h #includewindows.h #includemath.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=Ac=Z||c=ac=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=;bre