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

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