表达式类型的实现

广东工业大学数据结构表达式类型的实现，完美代码、报告，

#include
#include
#include
#include 
#include 

#define ERROR 0
#define OK 1
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100
#define MAXINT	65535
typedef char TElemType;
typedef TElemType EElemType;
typedef enum{OperatorConstantVariable}ElemTag;//Operator==0:运算符constant==1:常量Variable==2:变量
//不带头结点的二叉链表存储表示
typedef struct BiTNode
{
	ElemTag tag;							//用于区别操作数和运算符
	EElemType data;							//数据域
	int value;								//值域若元素类型为常量或变量则用来记录它的值，运算符则用来记录两子树运算后的结果
	struct BiTNode *lchild*rchild;			//孩子结点的指针
}BiTNode*BiTree;

typedef BiTree Expr;
typedef int Status;


void Assign（Expr &EEElemType Vint c）
{
	//实现对变量V的赋值（V=c）变量的初值为0
	//先序遍历整棵树把数据域为V的结点赋值为c
	if（!E）return;
	if（E->data==V）E->value=c;
	Assign（E->lchildVc）;
	Assign（E->rchildVc）;
}


Expr CompoundExpr（EElemType PExpr &E1Expr E2）
{
	//构造一个新的符合表达式（E1）P（E2）
	BiTNode *p;
	if（!（p=（BiTNode*）malloc（sizeof（BiTNode））））return NULL;
	p->lchild=E1;				//运算符的左孩子
	p->rchild=E2;				//运算符的右孩子
	p->tag=Operator;
	p->data=P;
	return p;
}


Status Destroy（Expr &T）
{
	if（!T）return OK;
	Destroy（T->lchild）;
	Destroy（T->rchild）;
	free（T）;
	T=NULL;
	return OK;
}


Status Exist（Expr EEElemType e）
{
	//判断表达式E是否存在变量e存在返回TRUE，否则返回FALSE
	if（!E||e<‘a‘||e>‘z‘）return FALSE;	//不是变量则返回错误
	if（E->data==e）return TRUE;
	return Exist（E->lchilde）||Exist（E->rchilde）; //递归寻找e
}


Status Diff（Expr &EEElemType v）
{
	//先序遍历整个表达式E对变量v进行求导
	BiTNode *p*q;
	if（!E||E->tag!=Operator）return OK;
	p=E;
	if（Exist（Ev））	//如果子孙中有变量v
	{
		if（E->data==‘^‘）					//若当前结点为‘^‘
		{
			
			//交换右子树赋值给左子树
			p=E->lchild;
			E->lchild=E->rchild;
			E->data=‘*‘;		//当前运算符变为*
			//右子树变为原来表达式指数-1的情况				
			if（!（q=（BiTNode*）malloc（sizeof（BiTNode））））return（OVERFLOW）;
			q->tag=Operator;	//右子树根结点
			q->data=‘^‘;
			q->value=MAXINT;
			q->lchild=p;		//右子树的左孩子是当前结点原来的左子树	
			if（!（p=（BiTNode*）malloc（sizeof（BiTNode））））return（OVERFLOW）;
			p->tag=Constant;		//右子树的右孩子
			p->data=E->lchild->data-1;
			p->value=E->lchild->value-1;
			p->lchild=p->rchild=NULL;
			q->rchild=p;
			E->rchild=q;
			p=E->rchild;
		}
		else if（E->data==‘*‘）		////若当前结点为‘*‘
		{
			if（E->rchild->data==v）	//右孩子直接为变量v，则求导后v的指数为0
			{		
				free（E->rchild）;	//删除右结点
				p=E;
				E=E->lchild;	//把左孩子成为根结点
				free（p）;
				p=E;
			}
			//其的情况则最后合并常数则可以
		}
		else 
		{
			if（!Exist（E->lchildv））q=E->lchild;	//若左孩子或右孩子没有变量，则左孩子或右孩子变成常数0
			if（!Exist（E->rchildv））q=E->rchild;
			q->data=‘0‘;
			q->value=0;
			q->lchild=q->rchild=NULL;
		}
	}
	else 	//不存在变量则把整个树删除，留下根结点 
	{
		Destroy（E->lchild）;			//删除左右子树
		Destroy（E->rchild）;
		E->tag=Constant;			//根结点为常数0
		E->data=‘0‘;
		E->value=0;
	}
		Diff（p->lchildv）;				//递归左右子树
		Diff（p->rchildv）;	
	return OK;
}


int Value（Expr &E）
{	
	//后根遍历对表达式求值
	int ab;
	if（E->tag!=Operator）return E->value;
	a=Value（E->lchild）;
	b=Value（E->rchild）;
	if（a==MAXINT||b==MAXINT）

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2015-06-26 21:19  表达式类型的实现\
     文件           8  2015-06-20 23:03  表达式类型的实现\1.txt
     文件       16675  2015-07-10 12:20  表达式类型的实现\expression.cpp
     文件      225323  2015-06-20 22:30  表达式类型的实现\expression.exe
     文件        1131  2015-06-20 23:18  表达式类型的实现\测试数据.txt
     文件      519942  2015-07-10 12:19  表达式类型的实现\表达式类型的实现课程设计报告.doc