代码演示
stack.h里面的代码：
代码语言：javascript复制#pragma once
#include<stdlib.h>
#include<memory.h>
#define MAX 1024
//这里的栈已经知道数组的最大长度，因此不需要再用在堆区再次开辟一块内存来用二级指针指向
struct sStack
{
//因为不确定用户数据类型，所以用void*指针来接收用户输入的数据地址
//指针数组----里面存放的是地址或者指针
void* data[MAX];
int size;
};
//隐藏数据，不让用户能够得到操作结构体的接口
//类似c 类中的private属性
typedef void* seqStack;
//初始化栈----返回栈的结构体,为了隐藏数据用万能指针作为返回值
seqStack init_stack();
//入栈
void push_stack(seqStack stack, void* data);
//出栈:尾删
void pop_stack(seqStack stack);
//返回栈顶元素
seqStack top_stack(seqStack stack);
//返回栈的大小
int size_stack(seqStack stack);
//判断栈是否为空
bool empty_stack(seqStack stack);
//销毁栈
void destroy_stack(seqStack stack);stack.cpp
代码语言：javascript复制#include"stack.h"
//初始化栈----返回栈的结构体,为了隐藏数据用万能指针作为返回值
seqStack init_stack()
{
//为栈结构体开辟空间:创建在堆区，防止局部变量直接释放
sStack* stack = (sStack*)malloc(sizeof(sStack));
if (stack == NULL)
{
return NULL;
}
//初始化数组--清空数组，一开数组里面会有随机值
memset(stack->data, NULL, sizeof(void*) * MAX);
//长度初始哈
stack->size = 0;
//返回栈的结构体
return stack;
}
//入栈
void push_stack(seqStack stack, void* data)
{
//尾插
if (stack == NULL)
return;
if (data == NULL)
return;
//把传入的void*数据转为sStack*数据类型
sStack* mystack = (sStack*)stack;
//判断当前栈内元素是否超过最大容量
if (mystack->size == MAX)
{
return;
}
//下面从数组尾部开始插入
mystack->data[mystack->size] = data;
//长度加一
mystack->size ;
}
//出栈:尾删
void pop_stack(seqStack stack)
{
if (stack == NULL)
return;
sStack* mystack = (sStack*)stack;
if (mystack->size == 0)
return;
//尾删:将数组中最后一个元素置空---把指针置空
//这里指针置空后相当于断掉了指针指向用户的数据，相当于做了删除操作
//因为我们这里不清楚用户的数据是开辟在堆区还是栈区
mystack->data[mystack->size - 1] = NULL;
//更新长度
mystack->size--;
}
//返回栈顶元素
seqStack top_stack(seqStack stack)
{
if (stack == NULL)
return NULL;
sStack* mystack = (sStack*)stack;
if (mystack->size == 0)
return NULL;
return mystack->data[mystack->size - 1];
}
//返回栈的大小
int size_stack(seqStack stack)
{
if (stack == NULL)
return -1;
sStack* mystack = (sStack*)stack;
return mystack->size;
}
//判断栈是否为空
bool empty_stack(seqStack stack)
{
if (stack == NULL)
return true;//表示为空
sStack* mystack = (sStack*)stack;
if (mystack->size == 0)
return -1;//为空
return 0;//不为空
}
//销毁栈
void destroy_stack(seqStack stack)
{
if (stack == NULL)
return;
//只有栈结构体分配到堆区
free(stack);
}main.cpp
代码语言：javascript复制#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include"stack.h"
//二叉树的非递归遍历
struct BinaryNode
{
//数据域
char ch;
//指针域
BinaryNode* lchild; //指向左孩子的指针
BinaryNode* rchild; //指向右孩子的指针
//标志
int flag;
};
void noRecursion(BinaryNode* root)
{
//首先初始化栈
seqStack mystack = init_stack();
//根节点入栈
push_stack(mystack, root);
//进入循环，栈中元素大于0，进行循环
while (size_stack(mystack)>0)
{
//弹出栈顶元素
BinaryNode* pTop=(BinaryNode*)top_stack(mystack);
//出栈
pop_stack(mystack);
//如果标志为真，直接输出
if (pTop->flag == 1)
{
printf("%c ", pTop->ch);
continue;//continue下面的代码不执行，直接进入下一次循环
}
//如果标志为假，将标志改为真
pTop->flag = 1;
//将该节点右子树，左子树和根分布压入栈中
//如果右子树为空，就不放入栈中
if (pTop->rchild != NULL)
{
push_stack(mystack, pTop->rchild);
}
//如果左子树为空，就不放入栈中
if (pTop->lchild != NULL)
{
push_stack(mystack, pTop->lchild);
}
//放入根
push_stack(mystack, pTop);
}
//销毁栈
destroy_stack(mystack);
}
void output()
{
BinaryNode Anode = { 'A',NULL,NULL,0 };
BinaryNode Bnode = { 'B',NULL,NULL,0 };
BinaryNode Cnode = { 'C',NULL,NULL ,0};
BinaryNode Dnode = { 'D',NULL,NULL,0 };
BinaryNode Enode = { 'E',NULL,NULL,0 };
BinaryNode Fnode = { 'F',NULL,NULL,0 };
BinaryNode Hnode = { 'H',NULL,NULL,0 };
BinaryNode Gnode = { 'G',NULL,NULL,0 };
//建立关系
Anode.lchild = &Bnode;
Anode.rchild = &Fnode;
Bnode.rchild = &Cnode;
Cnode.lchild = &Dnode;
Cnode.rchild = &Enode;
Fnode.rchild = &Gnode;
Gnode.lchild = &Hnode;
noRecursion(&Anode);
}
int main()
{
output();
return 0;
}
