班级计科三班
学号 191123
姓名。指导老师郭艳
日期 2023年6月19日。
1、需求分析。
所谓命题演算公式是指由逻辑变量（其值为true 或false）和逻辑运算符∧（and）、
（or）和┐（not）按一定规则所组成的公式（蕴含之类的运算可以用∧、∨和┐来表。
示）。公式运算的先后顺序为┐、∧而括号（）可以改变优先次序。已知一个命题演。
算公式及各变量的值，要求设计一个程序来计算公式的真值。
要求：1）利用二叉树来计算公式的真值。首先利用堆栈将中缀形式的公式变为后缀形式；
然后根据后缀形式，从叶结点开始构造相应的二叉树；最后按后序遍历该树，求各子树之值，即每到达一个结点，其子树之值已经计算出来，当到达根结点时，求得的值就是公式之真值。
2）逻辑变元的标识符不限于单字母，而可以是任意长的字母数字串。
3）根据用户的要求显示表达式的真值表。
2、设计。1、设计思想。
(1) 数据结构设计。
(1) 线性堆栈1的数据结构定义。
typedef char datatype ；
typedef struct
seqstack1;
用线性堆栈主要是用来存储输入的字符，它的作用就是将中缀表达式变成后缀表达式。
(2) 线性堆栈2的数据结构定义。
typedef struct snode
lsnode;
用于检测表达式的括号匹配。
(3) 定义二叉树的结点bitreenode
typedef struct node
bitreenode;
（3）算法设计。
首先实现将中缀表达式变成后缀表达式：
在将中缀表达式变成后缀表达式的时候会用到堆栈，因此首先需要初始化一个堆栈。又由于逻辑变元可能是字符也可能是字符串，所以它又不同于将单字符的逻辑变元的中缀表达式变成后缀表达式。我的设计是这样的，我将中缀表达式变成后缀表达式的过程分成了两部：
化简（将一维的复杂的中缀表达式变成一维的简单的中缀表达式，并将字符串逻辑变元存放在二维数组中），转化（将化简后的中缀表达式变成后缀表达式）。
然后用后缀表达式构造出二叉树：
在这个过程中，我用到了之前所定义的存放树的堆栈。具体实现为：扫描后缀表达式，如果遇到逻辑变元然后将这个变元变成一个树节点，它的实现就是将该逻辑变元赋给树的data域，然后将它的左右子树赋为null，然后将这个树节点压入相应的堆栈；接着继续扫描，如果遇到的是单目运算符（非号“！
”也将它构造成一个树节点然后从堆栈里面弹出一个树形节点，将弹出的元素的作为它的左子树，右子树设置为null，然后将这个树节点压入相应的堆栈；如果扫描到的是双目运算符（与号“&”或者或号“|”将它也构造成一棵树，然后将这个树节点压入相应的堆栈，然后从栈中弹出两个元素，一个作为它的左子树，一个作为它的右子树，如此重复n（n为后缀表达式的长度）次。
最后打印真值表：
打印真值表也用到了前面的简单的后缀表达式，其实现的基本思想为和构造二叉树差不多，它实现了每到一个根节点就计算一个运算的值。在打印之前需要统计字符的个数，有m个字符则要打印2^m行，因为他有这么多情况。具体实现为：
用一个字符型的数组来存放每个元素的一次取值，然后扫描后缀表达式，如果遇到逻辑变元就通过这个标识将相应的取值赋给它，然后它压入堆栈；接着继续扫描，如果遇到的是单目运算符（非号“！”则从堆栈里面弹出一个元素，并对它进行非运算，然后又将这个运算后的值压入堆栈；如果扫描到的是双目运算符（与号“&”或者或号“|”则从栈中弹出两个元素，并对这两个元素进行相应的运算，然后将这个运算后的值压入堆栈，如此重复n（n为后缀表达式的长度）次。
2、设计表示。
1>, 函数调用关系及函数说明：
change()函数原型为：
void change(char prefixstr1,char prefixstr,int length,char store[10],int* row,int* k )
该函数含有有六个参数，其中 prefixstr1为用户输入的中缀表达式，prefixstr为即将转化成为的简单中缀表达式，length为二维数组中存放的各个字符串的的长度store[10]用来存放中缀表达式中的逻辑变元，row就是逻辑变元的个数，k简化后的中缀表达式的长度。该函数的功能就是将复杂的中缀表达式变成简单的中缀表达式。
intopost()函数原型为：
void intopost(char prefixstr,char postfixstr,seqstack* mystack,int* n,int k)
该函数函数有五个参数 prefixstr为中缀表达式，postfixstr为简化后的后缀表达式，mystack为在转化过程中用到的堆栈，n为后缀表达式的字符长度，k为中缀表达式的字符长度。该函数的功能就是将简单的中缀表达式变成简单的后缀表达式。
maketree()函数原型为：
void maketree(bitreenode *root,treestack* mytree,char postfixstr,int n)
该函数共有四个参数，其中root为所建立的树的根节点，mytree是在构造树时所用到的堆栈，另外两个参数和前面的同名参数具有相同意义。这个函数的功能就是将简单的中缀表达式变成简单的后缀表达式。
precede()函数原型为：
datatype precede(datatype x1,datatype x2)
该函数有两个参数，返回值类型为datatype型，其中x1和x2就是要进行优先级比较的两个两个字符。x1为栈顶元素，x2为扫描到的元素。该函数的功能就是比较x1和x2的优先级并将比较结果返回给调用函数。
print()函数原型为：
void print(char postfixstr,char store[10],int length,int row,int n,seqstack* mystack)
该函数有六个参数，其中mystack是在输出真值表过程中要用到的堆栈，其余的参数和前面介绍的函数中的同名参数具有相同的意义。该函数的功能就是打印真值表。
<2> 函数接口说明：
函数的调用关系在上面的图中已经显示出来了，整个程序就是由一些子函数的集合，他们之间按所要实现的功能不同而调用不同的函数。在这些函数中除主函数外，其它函数的级别相同。
3、详细设计。
1），定义所需要的结构体，前面已经介绍了；
2），将中缀表达式变成后缀表达式的过程分成了两部：化简（将一维的复杂的中缀表达式变成一维的简单的中缀表达式，并将字符串逻辑变元存放在二维数组中），转化（将化简后的中缀表达式变成后缀表达式）。其中化简部分将要用伪**描述为。
while(prefixstr1[m]!=#
扫描到运算符后。
转化部分用伪**描述为：
循环扫描中缀表达式
（3），构造二叉树，其思想就是将逻辑变元作为叶子节点，运算符作为根节点，用堆栈实现，用伪**简单描述为：
循环扫描后缀表达式。
elsestackpop1(mytree,&x1);
将x1作为它的左子树，又子树为空；
stackpush1(mytree,p);
stackpop1(mytree,&x1);
root->leftchild=x1;}
（4），打印二叉树，其基本思想就是每到一个根节点就计算一个值，如此重复，直到总根节点，用伪**简单描述为：
循环赋值{if(扫描到逻辑变元')
数据结构课程设计报告
东莞理工学院城市学院。题目 二叉排序树 专业 计算机科学与技术 本 年级 2010级计算机科学与技术专业 1 班。个人姓名 何振江。指导教师 张娟老师 时间 2010至2011第二学期第18周 地点 实验楼615机房 东莞理工学院城市学院计算机与信息科学系制。2011年 6月。实习报告的内容。一 问...
数据结构课程设计报告
设计一个校园导游程序，为来访的客人提供信息查询服务。1 设计学校的校园平面图。选取若干个有代表性的景点抽象成一个无向带权图 无向网 以图中顶点表示校内各景点，边上的权值表示两景点之间的距离。2 存放景点代号 名称 简介等信息供用户查询。3 为来访客人提供图中任意景点相关信息的查询。4 为来访客人提供...
数据结构课程设计报告
河北科技大学。课程设计报告。学生姓名学号。专业班级。课程名称数据结构。学年学期 2 012 2 013学年第 2 学期指导教师 黄春茹。2 0 13年 6 月。课程设计成绩评定表。一 数据结构课程设计目标。二 问题描述。三 需求分析。四 概要设计。五 详细设计。六 软件说明书 给出软件如何使用，使用...