[数据结构与算法]数据结构C语言—线性表【栈】动态链栈（malloc动态分配实现）【2021-07-08】

LinkStackMalloc.h

#define NOEXIST -1 
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE 1
#define OVERFLOW 1

typedef int Status;
typedef int DataType;
typedef int *Pt;
typedef struct LNode 
{
	DataType data;//该结点的数据域，保存入栈的元素 
	struct LNode* next;//指向下一个结点的指针 
}LNode,*LinkList;//默认带头结点
typedef struct LinkStack
{
	LinkList base;//指向链栈底的指针,指向链表头节点，不存放元素 
	LinkList top;//指向链栈顶元素,即链表的最后一个结点 
	DataType LinkStackLength;//链栈长度,即元素个数 
}LinkStack,*LinkStackElem;

Status InitStack(LinkStackElem S);//初始化一个空动态链序栈S，成功返回OK，否则返回ERROR
Status ClearStack(LinkStackElem S);//清空一个动态链栈S，成功返回OK，否则返回ERROR，栈不存在（NOEXIST） ；栈顶指针等于栈底指针——空状态标志
Status DestoryStack(LinkStackElem S);//销毁一个动态链栈S，将动态分配的所有结点释放掉，成功返回OK，栈不存在（NOEXIST） 

Status IsEmptyStack(LinkStackElem S);//判断一个栈是否为空，是空（TRUE），不是空（FALSE），栈不存在（NOEXIST） 
DataType StackLength(LinkStackElem S);//返回栈S的元素个数，即栈长度，栈不存在（NOEXIST）

Status GetTop_Stack(LinkStackElem S,Pt e);//若栈不空，用*e返回栈S顶的元素，返回OK；若栈空（ERROR）；栈不存在（NOEXIST） 
Status Push_Stack(LinkStackElem S,DataType e);//若栈存在，将e入栈，返回OK；入栈失败，返回ERROR；栈不存在（NOEXIST） 
Status Pop_Stack(LinkStackElem S,Pt e);//若栈不空，将栈顶元素出栈，即删除栈顶元素，用*e返回其值，返回OK；若栈空（ERROR）；栈不存在（NOEXIST）
Status StackTraverse(LinkStackElem S,Status (*Visit)(LinkStackElem,LinkList,DataType,DataType,DataType));//栈不空，对每个元素调用Visist()，返回OK；若栈空（ERROR）；栈不存在（NOEXIST）
 
Status Visit(LinkStackElem S,LinkList p,DataType i,DataType j,DataType len);//遍历调用函数

LinkStackMalloc.c

#include <stdio.h>
#include <stdlib.h>
#include "LinkStackMalloc.h" 
Status InitStack(LinkStackElem S)//初始化一个空动态链栈S，成功返回OK，否则返回ERROR
{
	S->base=(LinkList)malloc(sizeof(LNode));//初始化时，只分配一个头结点，不存放栈元素 
	if(S->base!=NULL)
	{
		puts("==========开始【初始化栈】操作！==========");
		S->top=S->base;//空栈标志,因为此时只有头结点
		S->base->next=NULL;//将头结点的指针域赋NULL，因为此时只有头结点
		S->base->data=0;//头结点的数据域不存元素，只是给定义的变量赋个初始值
		S->LinkStackLength=0;//同时把动态链栈长度LinkStackLength置0
		puts("==========完成【初始化栈】操作！==========");
		return OK;
	}
	puts("==========开始【初始化栈】操作！==========");
	S->base=NULL;//若分配不成功，则让栈底指向NULL，作为栈不存在标志! 
	puts("==========失败【初始化栈】操作！==========");
	return ERROR;
}
Status ClearStack(LinkStackElem S)//清空一个动态链栈S，成功返回OK，否则返回ERROR，栈不存在（NOEXIST） ；栈顶指针等于栈底指针——空状态标志
{//清空时，只保留头节点，释放其他结点，长度归0 
	if(S->base==NULL)//栈不存在标志 
	{
		puts("\n==========栈不存在！不能执行【清空】操作！==========");
		return  NOEXIST;
	}
	
	S->top=S->base; //空栈标志 
	if(S->LinkStackLength==0)
	{
		puts("\n==========开始【清空】动态链栈S！==========");
		puts("\n==========【清空】动态链序栈S完成！==========");
		return OK;
	}
	else
	{
		puts("\n==========开始【清空】动态链栈S！==========");
		LinkList p=S->base->next; //让p指向首元结点，链表的第一个元素; 
		LinkList q=p;//让q也指向p的所指
		while(p!=NULL)
		{
			q=p->next;//让q保存p位置所指的下一个结点 
			free(p);//释放p所指的结点
			p=q;//让p又指向q的所指 
		} 
		S->LinkStackLength=0;//让链栈长归0
		S->top=S->base;//空栈标志,因为此时只有头结点
		S->base->next=NULL;//将头结点的指针域赋NULL,因为此时只有头结点
		puts("\n==========【清空】动态链栈S完成！==========");
		return OK; 
	} 
}
Status DestoryStack(LinkStackElem S)//销毁一个动态链栈S，将动态分配的所有结点释放掉，成功返回OK，栈不存在（NOEXIST） 
{
	if(S->base==NULL)//栈不存在标志 
	{
		puts("\n==========栈不存在！不能执行【销毁】操作！==========");
		return  NOEXIST;
	}
	
	S->top=S->base; //空栈标志 
	if(S->LinkStackLength==0)
	{
		puts("\n==========开始【销毁】动态链栈S！==========");
		puts("\n==========【销毁】动态链序栈S完成！==========");
		return OK;
	}
	else
	{
		puts("\n==========开始【销毁】动态链栈S！==========");
		LinkList p=S->base->next; //让p指向首元结点，链表的第一个元素; 
		LinkList q=p;//让q也指向p的所指
		while(p!=NULL)
		{
			q=p->next;//让q保存p位置所指的下一个结点 
			free(p);//释放p所指的结点
			p=q;//让p又指向q的所指 
		} 
		S->LinkStackLength=0;//让链栈长归0
		S->top=S->base;//空栈标志,因为此时只有头结点
		S->base->next=NULL;//将头结点的指针域赋NULL,因为此时只有头结点
		free(S->base); //释放头结点，比清空操作多了一个这步骤 
		S->base=NULL;//将S->base指向NULL，防止——（尽管释放了其所指链表，但依然根据这个指针还能访问数据 ） 
		puts("\n==========【销毁】动态链栈S完成！==========");
		return OK;
	} 
}
Status IsEmptyStack(LinkStackElem S)//判断一个栈是否为空，是空（TRUE），不是空（FALSE），栈不存在（NOEXIST） 
{
	if(S->base==NULL)//栈不存在标志 
	{
		puts("==========栈不存在！不能执行【判空】操作！==========");
		return  NOEXIST;
	}
	if(S->base==S->top)
	{
		return TRUE;	
	} 
	else
	{
		return FALSE;
	}
}
DataType StackLength(LinkStackElem S)//返回栈S的元素个数，即栈长度，栈不存在（NOEXIST）
{
	if(S->base==NULL)//栈不存在标志
	{
		puts("==========栈不存在！不能执行【返回当前栈中存放元素个数】操作！==========");
		return  NOEXIST;
	}
	return S->LinkStackLength; 
}
Status GetTop_Stack(LinkStackElem S,Pt e)//若栈不空，用*e返回栈S顶的元素，返回OK；若栈空（ERROR）；栈不存在（NOEXIST） 
{
	if(S->base==NULL)//栈不存在标志
	{
		*e=-6699;
		puts("==========栈不存在！不能执行【返回栈顶元素】操作！==========");
		return  NOEXIST;
	}
	if(S->base==S->top)
	{
		*e=-6699;
		puts("==========栈S为空！不能执行【返回栈顶元素】操作！==========");
		return ERROR;
	} 
	else
	{
		*e=S->top->data; //或*e=*(S->top-1); 
		printf("当前动态链栈S中，栈顶元素是：%d\n",*e);
		return OK;
	}
}
Status Push_Stack(LinkStackElem S,DataType e)//若栈存在，将e入栈，返回OK；入栈失败，返回ERROR；栈不存在（NOEXIST） 
{
	if(S->base==NULL)//栈不存在标志
	{
		puts("==========栈不存在！不能执行【入栈】操作！==========");
		return  NOEXIST;
	}
	else
	{
		LinkList p;
		p=(LinkList)malloc(sizeof(LNode));//p指向新分配的待尾插入栈的元素结点; 
		if(p!=NULL)
		{//始终采用尾插法入栈 
			p->data=e;
			p->next=S->top->next;
			S->top->next=p;
			S->top=p;//让S->top指向新的栈顶元素，即始终指向链表最后一个元素结点
			S->LinkStackLength++;//新入栈一个元素结点，长度加一
			return OK;
		}
		else
		{
			puts("待入栈元素申请结点失败！");
			return ERROR;
		}
	} 
}
Status Pop_Stack(LinkStackElem S,Pt e)//若栈不空，将栈顶元素出栈，即删除栈顶元素，用*e返回其值，返回OK；若栈空（ERROR）；栈不存在（NOEXIST）
{
	if(S->base==NULL)//栈不存在标志
	{
		*e=-6699;
		puts("==========栈不存在！不能执行【出栈】操作！==========");
		return  NOEXIST;
	}
	if(S->base==S->top)
	{
		*e=-6699;
		puts("==========栈空！不能执行【出栈】操作！==========");
		return ERROR;
	} 
	else
	{
		LinkList p=S->base;
		DataType i=0,len=StackLength(S);
		while(i!=len-1)
		{
			p=p->next;
			i++;
		}//找到栈顶指针S->top所指元素的前驱，将其指针保存在p 
		free(S->top);//释放栈顶元素，即出栈 
		S->top=p; //让栈顶指针S->top指向新的栈顶元素，即新的链表最后一个结点 
		S->LinkStackLength--;//新出栈一个元素结点，长度减一 
		return OK;
	}	
} 
Status StackTraverse(LinkStackElem S,Status (*Visit)(LinkStackElem,LinkList,DataType,DataType,DataType))//栈不空，对每个元素调用Visist()，返回OK；若栈空（ERROR）；栈不存在（NOEXIST） 
{
	if(S->base==NULL)//栈不存在标志
	{
		puts("\n==========栈不存在！不能执行【遍历】操作！==========");
		return  NOEXIST;
	}
	if(S->base==S->top)
	{
		puts("\n==========开始遍历检查动态链栈S==========");
		printf("栈顶指针----->头节点0：空<-----栈底指针"); 
		puts("\n==========遍历检查动态链栈S完成==========");
		return ERROR;
	} 
	else
	{
		puts("==========开始遍历检查动态链栈S==========");
		LinkList p=S->base;
		DataType i,j,len=StackLength(S);
		for(i=len,j=0;i>=0;p=S->base,j=0,i--)
		{
			Visit(S,p,i,j,len);
		}
		puts("==========遍历检查动态链栈S完成==========");
		return OK;
	}
}
Status Visit(LinkStackElem S,LinkList p,DataType i,DataType j,DataType len)//遍历调用函数
{
	while(p!=NULL)
	{
		if(j==i)
		{
			break;
		}
		p=p->next;
		j++;
	}
	if(i==len)
	{
		printf("栈顶指针----->%d:%d\n",len,S->top->data); 
		printf("              A\n              |\n"); 
	}
	if(i<len&&i>0)
	{
		printf("              %d:%d\n",j,p->data); 
		printf("              A\n              |\n"); 
	}
	if(i==0)
	{
		printf("栈底指针----->%d:\n",i); 

	}
	return OK;
}

main.c

#include <stdio.h>
#include <stdlib.h>
#include "LinkStackMalloc.h" 
/* 线性表——链栈（动态分配）【自编代码】 */
int main() 
{
	LinkStack S;
	DataType e; 
	InitStack(&S);
	puts("请按先后顺序，输入要入栈的元素（空格分隔，f结束）：");
	while(1)
	{
		int n,k;
		k=scanf("%d",&n);
		if(k==0)
		{
			break;
		}
		Push_Stack(&S,n);
	}
	StackTraverse(&S,Visit); 
	if(IsEmptyStack(&S))
	{
		puts("\n==========动态链栈S【是空栈】==========");
	}
	else
	{
		puts("\n==========动态链栈S【不是空栈】==========");
	} 
	if(StackLength(&S)!=NOEXIST)
	{
		printf("当前动态链栈S中已存在元素个数是：%d!\n",StackLength(&S));	
	} 
	GetTop_Stack(&S,&e);
	Pop_Stack(&S,&e);
	if(e!=-6699)
	{
		printf("已经弹出栈顶元素：%d!\n",e);	
	}
	StackTraverse(&S,Visit); 
	ClearStack(&S);
	StackTraverse(&S,Visit); 
	if(IsEmptyStack(&S))
	{
		puts("\n==========动态链栈S【是空栈】==========");
	}
	else
	{
		puts("\n==========动态链栈S【不是空栈】==========");
	} 
	fflush(stdin);
	puts("请按先后顺序，输入要入栈的元素（空格分隔，f结束）：");
	while(1)
	{
		int n,k;
		k=scanf("%d",&n);
		if(k==0)
		{
			break;
		}
		Push_Stack(&S,n);
	}
	StackTraverse(&S,Visit); 
	DestoryStack(&S);
	StackTraverse(&S,Visit); 
	IsEmptyStack(&S);
	return 0;
}

运行结果示例

------------------------------------------------------第七次发文章有点激动啊！-----------------------------------------------------
-----------------------------------------------------【数据结构代码自编练习】------------------------------------------------------
----------------------------------------------------------------【TDTX】-----------------------------------------------------------------