数据结构-二叉树类型的实现.doc
文本预览下载声明
实验4 表达式二叉树类型的实现
源代码及每步注解：
文件expression.h
/*头文件以及存储结构*/
#includestdio.h
#includeconio.h
#includestdlib.h
#includestring.h
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW 0
typedef int Status;
/*二叉树结点类型*/
typedef enum{INT,CHAR}ElemTag;/*INT为整型数据num，CHAR为字符型数据c*/
typedef struct TElemType
{
ElemTag tag;/*{INT,CHAR}指示是整型还是字符型*/
union
{
int num;/*tag=INT时，为整型*/
char c;/*tag=CHAR时，为字符型*/
};
} TElemType;
/*二叉树的二叉链表存储表示 */
typedef struct BiTNode
{
TElemType data;
struct BiTNode *lchild,*rchild; /* 左右孩子指针 */
}BiTNode,*BiTree;
typedef BiTree SElemType;/*栈SqStack的元素*/
typedef char SElemType1; /*栈SqStack1的元素*/
/*栈的顺序存储表示 */
#define STACK_INIT_SIZE 10 /* 存储空间初始分配量 */
#define STACKINCREMENT 2 /* 存储空间分配增量 */
/*两个顺序栈*/
typedef struct SqStack
{
SElemType *base; /* 在栈构造之前和销毁之后，base的值为NULL */
SElemType *top; /* 栈顶指针 */
int stacksize; /* 当前已分配的存储空间，以元素为单位 */
}SqStack; /* 顺序栈 */
typedef struct SqStack1
{
SElemType1 *base; /* 在栈构造之前和销毁之后，base的值为NULL */
SElemType1 *top; /* 栈顶指针 */
int stacksize; /* 当前已分配的存储空间，以元素为单位 */
}SqStack1; /* 顺序栈 */
/*顺序栈的基本操作*/
Status InitStack(SqStack *S)
{ /* 构造一个空栈S */
(*S).base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!(*S).base)
exit(OVERFLOW); /* 存储分配失败 */
(*S).top=(*S).base;
(*S).stacksize=STACK_INIT_SIZE;
return OK;
}
Status StackEmpty(SqStack S)
{ /* 若栈S为空栈，则返回TRUE，否则返回FALSE */
if(S.top==S.base) return TRUE;
else return FALSE;
}
Status Push(SqStack *S,SElemType e)
{ /* 插入元素e为新的栈顶元素 */
if((*S).top-(*S).base=(*S).stacksize) /* 栈满，追加存储空间 */
{
(*S).base=(SElemType *)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof(SElemType));
if(!(*S).base) exit(OVERFLOW); /* 存储分配失败 */
(*S).top=(*S).base+(*S).stacksize;
(*S).stacksize+=STACKINCREMENT;
}
*((*S).top)++=e;
return OK;
}
Status Pop(SqStack *S,SElemType *e)
{ /* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回
显示全部