数据结构课程设计----表达式类型的实现

数据结构课程设计----表达式类型的实现 完美程序+完整的报告

	/*头文件*/
	#include
	#include
	#include
	#include
#include
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0

#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
///数据类型定义
typedef int Status;
typedef struct BiTNode//树的存储结构
{
int tdata;//放int数据，当有数字时，data[0]=‘&‘，用‘&‘标志结点放的是数字
char data[10];//放字母字符串或是运算符号字符
struct BiTNode *lchild*rchild;
}BiTNode*BiTree;
///栈的数据类型定义
typedef char SElemType;
typedef struct
{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack; 
/////////////栈函数定义
Status IntiStack（SqStack &S） //初始化栈函数
{S.base=（char *）malloc（STACK_INIT_SIZE*sizeof（char））;
if （!S.base） return ERROR;
S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;}

Status DestroyStack（SqStack &S） //销毁函数
{free（S.base）;S.top=S.base=NULL;return OK;}

int StackLength（SqStack S） //求栈存储的长度函数
{int i=S.top-S.base;return i;}

Status Push（SqStack &S char e） //把e插入到栈顶函数
{
if （S.top-S.base>=S.stacksize）
{
S.base=（SElemType *）realloc（S.base
（S.stacksize+STACKINCREMENT）*sizeof（SElemType））;//当栈满的时候重新分配空间
if （!S.base） return ERROR;
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
*S.top++=e; return OK;}
*S.top++=e; return OK;
}

char Pop（SqStack &S）//删除栈顶并用e返回 函数
{if（S.top==S.base） return ERROR;
char e=*--S.top;return e;}
char gettop（SqStack &Schar &e）//取栈顶元素的函数
{ if （S.top<0）{
	return ERROR; 
}      //栈空，返回空值
         else { 
                   e=*（S.top-1）;
                  	return e; 
               }
        }  // gettop
Status StackEmpty （SqStack &S）
     { if （S.top==S.base）
              return OK;       //栈空，返回OK
         else { 
                   return ERROR;
                 }
        }  // empty

char in[100]in2[100];//假设表达式最多有100个字符，“#”表示输入完毕
SqStack S; //借用该栈来实现阿拉伯数字的输入
int a=0; //定义该全局变量来一个一个地初始化树
int i=0j=0;//定义全局变量
char OP[5]={‘+‘‘-‘‘*‘‘/‘‘^‘};//运算符
///////////////函数定义
Status IntiBiTree（BiTree &T）
{
T=NULL;
return OK;
}
Status DestroyBiTree（BiTree &T）
{ if（T->lchild）
    DestroyBiTree（T->lchild）;
  if（T->rchild）
	  DestroyBiTree（T->rchild）;
free（T）;
T=NULL;
return OK;
}
void input（） { //输入表达式的函数
char d=‘a‘;
for（int b=0;d!=‘#‘;b++）
{ 
scanf（“%c“&d）;
in[b]=d;//附给in[100]数组
}
getchar（）;//接收回车键字符
}
int pow10（int b）///10的b 次方
{int c=1;
for（int q=1;q<=b;q++）c=c*10;
return c;
} 
Status CreateBiTree（BiTree &T）//创建表达式类型的树
{ int y;
while（in[a]!=‘#‘）//以#结束
{
if（in[a]==‘-‘||in[a]==‘+‘||in[a]==‘*‘||in[a]==‘/‘||in[a]==‘^‘）//当字符为运算符时
{
if （!（T=（BiTNode *）malloc（sizeof （BiTNode）））） return ERROR;
T->data[0]=in[a];//字符数组的第一个元素为运算符
T->data[1]=‘@‘;//以‘@‘作为结尾的标志
T->tdata=0;//初始化变量
a++;
CreateBiTree（T->lchild）;//运算符需要建立它的左右孩子
CreateBiTree（T->rchild）;
return OK; 
}
else
{
if（in[a]==‘0‘||in[a]==‘1‘||in[a]==‘2‘||in[a]==‘3‘||in[a]==‘4‘||
in[a]==‘5‘||in[a]==‘6‘||in[a]==‘7‘||in[a]==‘8‘||in[a]==‘9‘）//当字符是阿拉伯数字时
{
Push（S in[a]）;//建一个栈来放阿拉伯数字
if（in[a+1]!=‘0‘&&in[a+1]!=‘1‘&&in[a+1]!=‘2‘&&i

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件      23017  2008-07-04 14:40  数据结构课程设计\2.cpp

     文件      50176  2008-07-31 17:11  数据结构课程设计\2.ncb

     文件        719  2008-07-31 16:45  数据结构课程设计\2.plg

     文件      41984  2008-07-31 16:45  数据结构课程设计\Debug\vc60.idb

     文件      53248  2008-07-31 16:44  数据结构课程设计\Debug\vc60.pdb

     文件     459776  2008-07-31 16:45  数据结构课程设计\Debug\2.pdb

     文件     237666  2008-07-31 16:45  数据结构课程设计\Debug\2.exe

     文件      48091  2008-07-31 16:44  数据结构课程设计\Debug\2.obj

     文件      55808  2008-07-04 15:23  数据结构课程设计\数据结构课程设计的封面.doc

     文件     223744  2008-07-05 23:44  数据结构课程设计\数据结构课程设计实验报告.doc

     文件       3341  2008-07-31 16:44  数据结构课程设计\2.dsp

     文件      48640  2008-07-31 17:11  数据结构课程设计\2.opt

     文件        510  2008-07-31 17:11  数据结构课程设计\2.dsw

     目录          0  2008-07-04 15:19  数据结构课程设计\Debug

     目录          0  2008-07-04 15:19  数据结构课程设计

----------- ---------  ---------- -----  ----

              1246720                    15