首页 > 代码库 > 链式栈
链式栈
1.编写头文件
#definedatatypeint
structstatcknode
{
intnum; //编号
datatypedata; //数据
structstatcknode *pNext;//指针域
};
typedefstructstatcknodeStackNode;
//初始化
StackNode *init(StackNode *pHead);
//进栈
StackNode *push(StackNode *pHead,intnum,datatypedata);
//出栈
StackNode *pop(StackNode * pHead,StackNode *poutdata);
//清空
StackNode *freeall(StackNode *pHead);
//打印
StackNode *printfAll(StackNode *pHead);
2.编写链表的实现代码
#include"stacklinknode.h"
#include"stdio.h" //NULL在stdio.h中
#include"stdlib.h" //malloc在stdlib.h中
//初始化
StackNode *init(StackNode *pHead)
{
returnNULL;
}
//进栈
StackNode *push(StackNode *pHead,intnum,datatypedata)
{
StackNode *pNewNode = (StackNode *)malloc(sizeof(StackNode));
pNewNode->num = num;
pNewNode->data = data;
pNewNode->pNext = NULL;
//如果是空的链式栈
if (pHead == NULL)
{
pHead =pNewNode;
}
else
{
//备份一个头指针
StackNode *p = pHead;
while (p->pNext != NULL)
{
//一直向前
p =p->pNext;
}
//插入
p->pNext = pNewNode;
}
//返回头结点
returnpHead;
}
//出栈
StackNode *pop(StackNode * pHead,StackNode *poutdata)
{
if (pHead == NULL)
{
//已经没有元素
returnNULL;
}
//表示只有一个元素的时候
elseif (pHead->pNext == NULL)
{
poutdata->num = pHead->num;
poutdata->data = pHead->data; //取出数据
free(pHead);//释放内存
pHead =NULL;
returnpHead;
}
else
{
StackNode *p = pHead;
//表示栈顶的倒数第二个节点
while (p->pNext->pNext != NULL)
{
//循环到倒数第二个节点
p =p->pNext;
}
poutdata->num = p->pNext->num;
//取出数据
poutdata->data = p->pNext->data;
p->pNext = NULL;
returnpHead;
}
}
//清空
StackNode *freeall(StackNode *pHead)
{
if (pHead == NULL)
{
returnNULL;
}
else
{
StackNode *p1 = NULL, *p2 = NULL;
//头结点
p1 =pHead;
while (p1->pNext != NULL)
{
//保存下一个节点
p2 =p1->pNext;
//跳过p2
p1->pNext = p2->pNext;
//释放节点
free(p2);
}
free(pHead);
returnNULL;
}
}
//打印
StackNode *printfAll(StackNode *pHead)
{
if (pHead == NULL)
{
returnNULL;
}
else
{
printf("%d,%d,%p,%p\n",pHead->num,pHead->data,pHead,pHead->pNext);
//通过递归的方式进行打印
printfAll(pHead->pNext);
}
}
3.实现代码main.c
#pragma warning(disable:4996)
//#define_CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include"stacklinknode.h"
voidmain1()
{
intnum;
scanf("%d", &num);
//打印数据
printf("num = %d\n",num);
//创建一个链式栈的头节点
StackNode *pHead = NULL;
printf("\n\n");
//通过这种方式实现打印打印十进制的二进制的表现形式
while (num)
{
printf("%d\n",num % 2);
pHead =push(pHead,num % 2, 0);
num /= 2;
}
while (pHead != NULL)
{
StackNode *pOut = (StackNode *)malloc(sizeof(StackNode));
pHead =pop(pHead,pOut);
printf("%d",pOut->num);
}
system("pause");
}
voidmain()
{
StackNode *pHead = NULL;//创建一个链式栈的头节点
pHead =init(pHead); //设置栈为NULL
pHead =push(pHead, 1, 1);
pHead =push(pHead, 2, 11);
pHead =push(pHead, 3, 111);
pHead =push(pHead, 4, 1111);
pHead =push(pHead, 5, 11111);
printfAll(pHead);
/* pHead =freeall(pHead);
printf("\n释放以后");
printfAll(pHead);*/
while (pHead != NULL)
{
//保存出栈的数据
printf("出栈\n");
StackNode *pOut = (StackNode *)malloc(sizeof(StackNode));
pHead =pop(pHead,pOut);
printf("出栈之后\n");
printfAll(pHead);
printf("\n出栈之后的数据%d,%d",pOut->num,pOut->num);
}
system("pause");
}