|
|
#2
hzh5122010-05-25 14:30
指针用法的老问题,
你的程序有两个致命错误: 1.栈元素为什么不是指针,而是一个结构体对象,这浪费了空间,非常不合理。 typedef struct SNode { BiTNode elem; // 极不合理,浪费空间 SNode *next; } SNode; 2.push后,应为地址指针,不然相当于没有链入树根中。 源代码: 程序代码:#include <stdio.h> #include <malloc.h> #define OK 1 #define ERR -1 typedef char ElemType; typedef int status; typedef struct BiTNode { ElemType data; BiTNode *lchild,*rchild; } BiTNode; typedef BiTNode* BiTree; typedef struct SNode { BiTNode* elem; SNode *next; } SNode; typedef struct NodeStack { SNode *top,*bottom; int size; } NodeStack; void initStack(NodeStack &ns); status push(NodeStack &ns,BiTNode* node); status pop(NodeStack &ns,BiTNode *node); void creatTree(BiTree &t,char data[],int len); int main(int argc, char *argv[]) { BiTree t; char* data = "12##3##"; int len = 7; creatTree(t,data,len); return 0; } /* status push(NodeStack &ns,BiTNode* node) { SNode *p = (SNode*)malloc(sizeof(SNode)); p->elem.data = node->data; if(ns.size == 0) { ns.top = ns.bottom = p; p->next = NULL; } else { p->next = ns.top; ns.top = p; } ns.size++; return OK; } */ status push(NodeStack &ns,BiTNode* node) { SNode *p = (SNode*)malloc(sizeof(SNode)); p->elem = node; if(ns.size == 0) { ns.top = ns.bottom = p; p->next = NULL; } else { p->next = ns.top; ns.top = p; } ns.size++; return OK; } status pop(NodeStack &ns,BiTNode *node) { SNode* p; if(ns.size == 0) return ERR; else { node->data = ns.top->elem->data; p = ns.top; ns.top = ns.top->next; free(p); ns.size--; } return OK; } void initStack(NodeStack &ns) { ns.bottom = NULL; ns.top = NULL; ns.size = 0; } void creatTree(BiTree &t,char data[],int len) { NodeStack ns; int i,flag=0; BiTNode* node; BiTNode* popnode = (BiTree)malloc(sizeof(BiTNode)); initStack(ns); t = (BiTree)malloc(sizeof(BiTNode)); t->data = data[0]; t->lchild = NULL; t->rchild = NULL; push(ns,t); for(i=1; i<len; i++) { if(data[i] == '#' && flag == 1) //当前栈顶节点的左右孩子生成结束,应将栈顶节点出栈, //若出栈节点仍是出栈后栈顶节点的右孩子,则栈顶节点继续出栈。 { pop(ns,popnode); while(popnode == ns.top->elem->rchild) pop(ns,popnode); } else if(data[i] == '#' && flag == 0) //当前节点的左孩子生成结束,将flag置为1,转而生成当前节点的右孩子 { flag = 1; } else { node = (BiTree)malloc(sizeof(BiTNode)); node->data = data[i]; node->lchild = NULL; node->rchild = NULL; if(flag == 0) //生成当前节点并将该节点作为栈顶节点的左孩子 //同时将当前节点入栈 { ns.top->elem->lchild = node; push(ns,node); } else //生成当前节点并将该节点作为栈顶节点的右孩子 //同时将当前节点入栈,同时将flag置为0,下次转向左孩子 { ns.top->elem->rchild = node; push(ns,node); flag = 0; } } } } |
#include <stdio.h>
#include <malloc.h>
#define OK 1
#define ERR -1
typedef char ElemType;
typedef int status;
typedef struct BiTNode
{
ElemType data;
BiTNode *lchild,*rchild;
}BiTNode;
typedef BiTNode* BiTree;
typedef struct SNode
{
BiTNode elem;
SNode *next;
}SNode;
typedef struct NodeStack
{
SNode *top,*bottom;
int size;
}NodeStack;
status initStack(NodeStack &ns)
{
ns.top = ns.bottom = 0;
ns.size = 0;
return OK;
}
status push(NodeStack &ns,BiTNode* node)
{
SNode *p = (SNode*)malloc(sizeof(SNode));
p->elem.data = node->data;
if(ns.size == 0)
{
ns.top = ns.bottom = p;
p->next = NULL;
}
else
{
p->next = ns.top;
ns.top = p;
}
ns.size++;
return OK;
}
status pop(NodeStack &ns,BiTNode *node)
{
SNode* p;
if(ns.size == 0)
return ERR;
else
{
node->data = ns.top->elem.data;
p = ns.top;
ns.top = ns.top->next;
free(p);
ns.size--;
}
return OK;
}
status creatTree(BiTree &t,char data[],int len)
{
NodeStack ns;
int i,flag=0;
BiTNode* node;
BiTNode* popnode;
initStack(ns);
t = (BiTree)malloc(sizeof(BiTNode));
t->data = data[0];
t->lchild = NULL;
t->rchild = NULL;
push(ns,t);
for(i=1; i<len; i++)
{
if(data[i] == '#' && flag == 1)
//当前栈顶节点的左右孩子生成结束,应将栈顶节点出栈,
//若出栈节点仍是出栈后栈顶节点的右孩子,则栈顶节点继续出栈。
{
pop(ns,popnode);
while(popnode == ns.top->elem.rchild)
pop(ns,popnode);
}
else if(data[i] == '#' && flag == 0)
//当前节点的左孩子生成结束,将flag置为1,转而生成当前节点的右孩子
{
flag = 1;
}
else
{
node = (BiTree)malloc(sizeof(BiTNode));
node->data = data[i];
node->lchild = NULL;
node->rchild = NULL;
if(flag == 0)
//生成当前节点并将该节点作为栈顶节点的左孩子
//同时将当前节点入栈
{
ns.top->elem.lchild = node;
push(ns,node);
}
else
//生成当前节点并将该节点作为栈顶节点的右孩子
//同时将当前节点入栈,同时将flag置为0,下次转向左孩子
{
ns.top->elem.rchild = node;
push(ns,node);
flag = 0;
}
}
}
}
int main(int argc, char *argv[])
{
BiTree t;
char* data = "12##3##";
int len = 7;
creatTree(t,data,len);
return 0;
}
程序代码: