云南大学软件学院
实 验 报 告
姓名： 王道红 学号： 20061120052 班级： 2 日期： 2007 — 10 — 25 成绩：
课程名称 数据结构实验 实验项目 树及其应用
实验目的
熟练掌握二叉树的存储结构及其基本操作（包括二叉树的建立、遍历等）。掌握建树的基本
方法，以及树在编程时的应用，并学会合理利用树的优点，在编写程序时，使程序代码达到
最优。
实验内容
（算法、
程序、步
骤和方
法）
一． 实验内容
实现一个重言式的判别程序。逻辑表达式从键盘输入，长度不超过一行；逻辑运算符
包括“|”、“ &”、“ ~”，分别表示或、与、非，运算优先程度递增，括号内的运算优先。
二、算法
本试验中的难点就是怎样建立重言式二叉树，和怎样使用 1 和 0 来进行重言式的判别运
算。
1、 重言式二叉树的建立，其实重言式二叉树的建立是一个逆过程，即倒着来建立。在
这里用到了两个栈，一个是操作符栈，另一个是操作数栈，分别用来保存操作符和
操作数。在读取表达式的时候如果是操作数则进栈。如果是操作符则把栈顶元素取
出来和它比较。如果栈顶的优先级小，则入栈。如果等于则去括号。小于的话则把
栈顶元素弹出来。在把操作数栈的元素弹出两个构建一棵小字树，再把建好的小字
树的根压入到操作数栈里。重复操作，直到表达式结束，就建立了一棵重言式二叉
树了。
2、 重言式二叉树的判别，在这里用到了一个数组来保存每一种组合下的各变元的取
值。
在从二叉树里读到相应的变元时就用对应的值 (1 或 0)进行判断。用一个记数器来记
录。
最后用计数器的值和变元组合情况的总数来相比。如果计数器为 0，那么表明是永假
式。如果相等则是永真式。否则既不真也不假。
3、至于其它的我觉得不是太难。本程序由 2 个头文件 001.h 和 002.h，以及 1 个 cpp 文件
23.cpp 组成。
4、具体原代码如下：
代码：
23.cpp
#include<stdlib.h>
#include<stdio.h>
#include<math.h>
#include "002.h"
void main()
{
char str2[20],*p;
int i=0,N=0,sum,loop;
int SUM=0;
评论0