/*有一个问题,一直没有解决,单步调试发现已正常入栈的元素,为什么Pop出来的栈元素为1,打印到屏幕上就是一个笑脸?*/
#include <iostream> #include "bitree.h" using namespace std; #define STACK_INIT_SIZE 100
typedef struct BiTNode { char data; struct BiTNode *lchid, *rchild; }BiTNode, *BiTree;//二叉树结构体 typedef struct { struct BiTNode *base; struct BiTNode *top; int stacksize; }SqStack; void InitStack(SqStack &S)
{ S.base=new BiTNode[STACK_INIT_SIZE]; if(!S.base) { cout<<"\n执行中序存储分配失败!"; return; } S.top=S.base; S.stacksize=STACK_INIT_SIZE; } bool Push(SqStack &S,BiTree e) { /*if(S.top-S.base>=S.stacksize) { S.base=(BiTNode *)realloc(S.base,STACKINCREMENT); if(!S.base) { cout<<"\n栈为空,无法进行插入操作"; return false; } S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; }*/ S.top++; S.top=e; return true; } bool Pop(SqStack &S,BiTree &e) { if(S.top==S.base) { cout<<"\n被使用栈为空栈,无法删除其中的任何元素!"; return false; } e=(--S.top); return true; } bool IsEmptyStack(SqStack S) { if(S.top==S.base) return true; else return false; } bool GetTop(SqStack S,BiTree &e) { if(S.top==S.base) { cout<<"\n此栈为空,无法取其栈顶元素!"; return false; } e=S.top; return true; }
/*执行先序非递归遍历时出现内存冲突,原因为p为空,单步调试发现问题就在Pop之后,栈顶top所指值为1,与先前存入的值不相等*/ void RePreOrderTraverse(BiTree T) //先序非递归遍历二叉树 { SqStack S; InitStack(S); Push(S,T); BiTree p=T; while(p||!IsEmptyStack(S)) { if(p) { cout<<p->data; Push(S,p); p=p->lchid; } else { BiTree q; GetTop(S,p); Pop(S,q); p=p->rchild; } } }
//输入ABk##Y#a##CF###(“#”代表空树)
//单步调试发现栈S中存入元素一切正常,如图:
//运行到Pop后出现错误,原先的top指针所存放的值为空,单步调试结果如图: