今天做的一个二叉树的非递归遍历方法,利用到了栈,但是再出栈部分遇到了标题的问题:返回了一个结构体的地址,地址没变,但是结构体中的值发生了变化,以下为原因:
这是声明的结构体:
typedef struct BTNode {
char data;
struct BTNode * lchild;
struct BTNode * rchild;
}BTN;
typedef struct Node {
BTN* node;
struct Node * nextNode;
} tNode;
typedef struct Stack {
tNode* top;
tNode* bottom;
} Stack;
这是主要函数:
void Nodgqx(Stack* s, BTN* p);
void init1(Stack* s);
int push(Stack* s, BTN* d);
BTN* pop(Stack*);
void main() {
BTN* rN = NULL;
//树的创建,不是问题所在,不用看
createTdt(&rN);
Stack s;
//栈的初始化,不是问题所在,不用看
init1(&s);
//这是调用非递归前序遍历
Nodgqx(&s, rN);
}
//以下为前序非递归遍历
void Nodgqx(Stack *s,BTN *p) {
while (!isEmpty(s)||p) {
while (p != NULL) {
printf("%c ", p->data);
push(s,p);
p = p->lchild;
}
if (!isEmpty(s)) {
p = pop(s);
p = p->rchild;
}
}
}
//以下为栈的出栈入栈与初始化方法,不是标题问题所在,不用看
void init1(Stack* s) {
s->top = (Stack*)malloc(sizeof(Stack));
if (!s) {
printf("内存申请失败\n");
exit(-1);
}
s->bottom = s->top;
s->top->nextNode = NULL;
}
//压栈函数,不是标题问题所在,不用看
int push(Stack *s, BTN *d) {
if (d) {
tNode * nT= (tNode*)malloc(sizeof(tNode));
if (!nT) {
printf("动态内存分配失败\n");
return (-1);
}
nT->node = d;
nT->nextNode = s->top;
s->top = nT;
}
return 1;
}
//这里是标题问题所在
BTN * pop(Stack *s) {
if (s) {
tNode *t=s->top;
s->top=t->nextNode;
return t->node;
}
}
以下为关键地方:
typedef struct BTNode {
char data;
struct BTNode * lchild;
struct BTNode * rchild;
}BTN;
typedef struct Node {
BTN* node;
struct Node * nextNode;
} tNode;
typedef struct Stack {
tNode* top;
tNode* bottom;
} Stack;
void Nodgqx(Stack *s,BTN *p) {
while (!isEmpty(s)||p) {
while (p != NULL) {
printf("%c ", p->data);
push(s,p);
p = p->lchild;
}
if (!isEmpty(s)) {
p = pop(s);
p = p->rchild;
}
}
}
BTN * pop(Stack *s) {
if (s) {
tNode *t=s->top;
s->top=t->nextNode;
return t;
}
这里,看到出栈函数将返回的值赋给p了吗?:
if (!isEmpty(s)) {
p = pop(s);
p = p->rchild;
}
}
}
再看这里,返回的t,在本函数中,结构体t的中的字符类型数据没有问题,是正常的,但是返回给上面的p就出现了问题,主要问题就是是值变成一个怪东西,地址没变,所以,哪里出了毛病?结合结构体的声明看。
//这里是标题问题所在,
BTN * pop(Stack *s) {
if (s) {
tNode *t=s->top;
s->top=t->nextNode;
return t;
}
答案是:返回值出了错误:
return t;
首先,t是个Node结构体指针:
tNode *t=s->top;
typedef struct Node {
BTN* node;
struct Node * nextNode;
} tNode
而接受出栈函数所返回的地址的变量p是个BTN结构体指针:
void Nodgqx(Stack *s,BTN *p)
typedef struct BTNode {
char data;
struct BTNode * lchild;
struct BTNode * rchild;
}BTN;
所以,BTN p=tNode t?(就是p=pop(s)变过来的)
屁!驴唇不对马嘴。
正确返回值应为:
return t->node;
总结:好兄弟们,这种结构体套结构体,并且利用函数返回的,一定要注意返回值类型对不对