博客

1. 带头结点和不带头结点的链栈实现方式不同，我这里是不带头结点的链栈。

2. 头指针(Lhead)：不是头结点的指针，是指向头结点（首元结点）的指针，无论链栈是否为空，头指针均存在。

3. 二级指针：指向指针变量的指针。

4. 存储结构如图


5. 编译环境：vc6.0。

代码如下：

#include <stdio.h>
#include <stdlib.h>

//存储类型结构
typedef struct StackNode
{
	int data;								 //结点数据
	struct StackNode* next;					//结点指针
}StackNode, * LinkStack;

//***********************销毁链栈****************************
int DestoryLinkStack(LinkStack* Lhead)						//形参接收头指针地址（二级指针）                           
{
	StackNode* p, * q;										//结点指针
	p = (*Lhead)->next;										//指向第二个结点
	q = *Lhead;												//q指向首元结点
	while (p)											  //第二个结点不为空
	{
		free(q);                                        //释放首元结点
		q = p;											//q指向新首元结点
		p = p->next;									//p->指向新的第二结点
	}
	free(q);										 //释放首元结点
	*Lhead = NULL;									 //头指针指向空，头指针是指向首元结点的指针
	return 1;
}

//**********************判断链栈是否为空*********************
int LinkStackEmpty(StackNode* Lhead)			 //判断链栈是否非空
{
	if (Lhead == NULL)
		return 1;
	else return 0;
}

//*************************入栈**************************
int Push(LinkStack* Lhead, int e)									//形参Lhead接收头指针地址(二级指针)，e接收入队元素值
{
	LinkStack s = (LinkStack)malloc(sizeof(StackNode));				 //动态申请内存
	if (s == NULL)													//申请失败
	{
		printf("动态内存申请失败\n");
		return 0;
	}
	s->data = e;
	s->next = *Lhead;										 //插入新结点
	*Lhead = s;												//头指针指向新首元结点
	return 1;
}

//****************************出栈***************************
int Pop(LinkStack* Lhead, int* e)                           //形参Lhead接收头指针地址(二级指针)，e接收入队元素值       
{
	StackNode* p = *Lhead;									//p指向首元结点
	if (LinkStackEmpty(p))                               //若空                
		return 0;
	*e = p->data;                                          //获取返回值
	*Lhead = p->next;                                       //出栈，Lhead指针下移
	free(p);												//释放首元结点
	return 1;
}

//************************************遍历输出*******************************
int StackTraverse(StackNode* Lhead)							//形参Lhead接收头指针
{
	StackNode* p = Lhead;									//头指针赋值给p
	if (p == NULL)											//栈空,头指针指向空
		return 0;
	while (p != NULL)											//头指针不指向NULL
	{
		printf("%-5d", p->data);							//打印数据
		p = p->next;
	}
	return 1;
}

int main()
{
	int i, e, n;                                  //e结点元素,n元素个数
	LinkStack Lhead = NULL;                    //头指针,初始化为空
	if (LinkStackEmpty(Lhead))
		printf("链表为空\n");
	else printf("链表不为空\n");

	printf("输入插入元素个数\n");                    //插入测试
	scanf("%d", &n);
	for (i = 0; i < n; i++)
	{
		printf("输入元素第%d个元素e的值\n", i + 1);
		scanf("%d", &e);
		if (Push(&Lhead, e))
			printf("进栈成功\n");
		else printf("进栈失败\n");
	}
	if (!StackTraverse(Lhead))                         //遍历输出测试
		printf("链栈为空\n");

	if (Pop(&Lhead, &e))								//出栈测试
		printf("\n\n元素%d出栈\n", e);
	else printf("\n出栈失败\n");
	printf("出栈后\n");
	if (!StackTraverse(Lhead))							 //遍历输出测试
		printf("链栈为空\n");

	if (LinkStackEmpty(Lhead))                         //判空测试
		printf("链表为空\n");
	else printf("链表不为空\n");

	DestoryLinkStack(&Lhead);								//销毁测试
	printf("销毁后\n");
	if (!StackTraverse(Lhead))
		printf("链栈为空\n");

	return 0;
}

测试结果


：