栈的链式存储结构设计与实现

柔情只为你懂 2022-05-29 10:53 185阅读 0赞

与栈的顺序存储相同，栈的链式存储也是基于线性表的链式存储的基础之上完成对栈的设计。其中栈的链式存储部分参考[点击打开链接][Link 1]

栈的链式存储头文件：

//LinkStack.h
    #ifndef _LINKSTACK_H_
    #define _LINKSTACK_H_
    
    typedef void LinkStack;//栈的句柄
    
    //创建链式栈相当于创建一个链式线性表
    LinkStack* LinkStack_Create();
    
    //销毁链式栈涉及到链表节点的生命周期管理
    //首先，清空栈中所有元素，然后再销毁栈
    void LinkStack_Destroy(LinkStack *stack);
    
    //清空一个栈 相当于 清空一个线性表
    //清空栈的时候 涉及到 栈元素生命周期的管理
    //清空链式栈：当栈的长度不为0时，一直Pop出栈中的元素。直到栈中不存在任何元素
    
    //所有入栈的结点都是malloc
    //若要清空栈 把栈中元素弹出 并且释放结点内存
    void LinkStack_Clear(LinkStack *stack);
    
    //入栈 == 向链表头插入元素  
    int LinkStack_Push(LinkStack* stack, void* item);
    
    //出栈
    //栈中弹出元素 相当于 从线性表的头部删除元素
    //把线性表的业务结点 转化成 栈的业务结点
    void* LinkStack_Pop(LinkStack *stack);
    
    //获取栈顶元素 相当于 获取线性表的0号位置
    void* LinkStack_Top(LinkStack *stack);
    
    //求栈的大小 相当于 求线性表的len
    int LinkStack_Size(LinkStack *stack);
    
    #endif

栈的.c文件：

//LinkStack.c
    #include "LinkStack.h"  
    #include "LinkList.h"  
    #include <stdio.h>  
    #include <stdlib.h> 
    #include <string.h>
    
    //链式栈的存储节点定义
    //包含链表的指针域节点和用户数据域指针
    //定义一个抽象的栈节点模型   
    //也就是用链式链表的抽象模型来存储item 以便插入元素
    /*
    typedef struct _Teacher//链表的业务结点
    {
    	LinkListNode node;//包含指针域节点 相当于是把栈顶指针 与 链表的头指针合二为一
    	//下面是栈的业务节点
    	void *item;//用来放元素
    }Teacher;
    */
    typedef struct _LinkStack//链表的业务结点
    {
    	LinkListNode node;//包含指针域节点 相当于是把栈顶指针 与 链表的头指针合二为一
    	//下面是栈的业务节点
    	void *item;//用来放元素
    }LinkStackNode;
    //创建链式栈相当于创建一个链式线性表
    LinkStack* LinkStack_Create()
    {
    
    	return LinkList_Create();
    }
    
    //销毁链式栈涉及到链表节点的生命周期管理
    //首先，清空栈中所有元素，然后再销毁栈
    void LinkStack_Destroy(LinkStack *stack)
    {
    	//1 首先要删除栈的所有元素
    	LinkStack_Clear(stack);//释放栈中的节点
    	LinkList_Destroy(stack);//释放句柄
    
    }
    
    //清空一个栈 相当于 清空一个线性表
    //清空栈的时候 涉及到 栈元素生命周期的管理
    //清空链式栈：当栈的长度不为0时，一直Pop出栈中的元素。直到栈中不存在任何元素
    
    //所有入栈的结点都是malloc
    //若要清空栈 把栈中元素弹出 并且释放结点内存
    void LinkStack_Clear(LinkStack *stack)
    {
    	if (NULL == stack)
    	{
    		return;
    	}
    	while (LinkList_Length(stack) > 0)
    	{
    		LinkStack_Pop(stack);//在这个函数中释放结点的内存
    	}
    }
    
    //入栈 == 向链表头插入元素  
    //向栈中压入元素相当于链式表的头插法
    // void *item栈的业务节点===>链表的业务节点
    /*
    int LinkStack_Push(LinkStack* stack, void *item)
    {
    	int ret = 0;
    	Teacher *tmp = NULL;
    	tmp = (Teacher *)malloc(sizeof(Teacher));//为了防止函数结束时temp被析构必须分配内存  		
    	//异常处理
    	if (NULL == tmp)
    	{
    		ret = -1;
    		printf("func err LinkStack_Push tmp malloc:%d\n",ret);
    		return ret;
    	}
    	memset(tmp,0,sizeof(Teacher));//初始化
    	tmp->item = item;	//将item 也就是所需要存储的信息传递给temp->item  
    	ret = LinkList_Insert(stack,(LinkListNode *)tmp,0);//栈中压入元素 相当于 向链表中0号位置插入元素
    	if (ret!=0)
    	{
    		ret = -2;
    		printf("func err LinkStack_Push tmp LinkList_Insert():%d\n", ret);
    		if (tmp != NULL)//为了防止内存插入失败而导致内存泄漏  
    		{
    			free(tmp);
    		}
    		return ret;
    	}
    	return ret;
    }
    */
    
    int LinkStack_Push(LinkStack* stack, void *item)
    {
    	int ret = 0;
    	LinkStackNode *tmp = NULL;
    	tmp = (LinkStackNode *)malloc(sizeof(LinkStackNode));//为了防止函数结束时temp被析构必须分配内存  		
    	//异常处理
    	if (NULL == tmp)
    	{
    		ret = -1;
    		printf("func err LinkStack_Push tmp malloc:%d\n", ret);
    		return ret;
    	}
    	memset(tmp, 0, sizeof(LinkStackNode));//初始化
    	tmp->item = item;	//将item 也就是所需要存储的信息传递给temp->item  
    	ret = LinkList_Insert(stack, (LinkListNode *)tmp, 0);//栈中压入元素 相当于 向链表中0号位置插入元素
    	if (ret != 0)
    	{
    		ret = -2;
    		printf("func err LinkStack_Push tmp LinkList_Insert():%d\n", ret);
    		if (tmp != NULL)//为了防止内存插入失败而导致内存泄漏  
    		{
    			free(tmp);
    		}
    		return ret;
    	}
    	return ret;
    }
    //出栈
    //栈中弹出元素 相当于 从线性表的头部删除元素
    //把线性表的业务结点 转化成 栈的业务结点
    void* LinkStack_Pop(LinkStack *stack)
    {
    	void *item = NULL;//中间缓存要出栈的元素
    	LinkStackNode *tmp = NULL;
    	tmp = (LinkStackNode *)LinkList_Delete(stack,0);
    	if (NULL == tmp)
    	{
    		return NULL;
    	}
    	item = tmp->item;
    	//因为LinkList_Insert的时候，分配了内存， 所以LinkList_Delete释放内存
    	free(tmp);
    	return item;
    }
    
    //获取栈顶元素 相当于 获取线性表的0号位置
    void* LinkStack_Top(LinkStack *stack)
    {
    	LinkStackNode *temp = NULL;
    	temp = (LinkStackNode *)LinkList_Get(stack, 0);
    	if (temp == NULL)
    	{
    		return NULL;
    	}
    	return temp->item;
    }
    //求栈的大小 相当于 求线性表的len
    int LinkStack_Size(LinkStack *stack)
    {
    	return LinkList_Length(stack);
    }
    
    
    栈的链式存储测试框架

#include "LinkStack.h"  
    #include "LinkList.h"  
    #include <stdio.h>  
    #include <stdlib.h> 
    /*
    基础知识：
    但是，平时使用的时候建议加上#include<string.h>（尤其在以下情况下）
    1、使用string类型
    2、使用cin、cout语句来输入输出string类型变量（注意，同时还需要 #include<iostream>）
    3、使用memset()、strlen()、strcpy()等函数时
    
    只要用到stdio里面定义的库函数，就要包含它
    这些库函数包括scanf，printf等等
    
    是引用stdlib.h头文件，即#include <stdlib.h>。这里的.h是不可缺少的。
    stdlib.h中，包含了C语言的一些常用库函数。如
    动态内存相关的malloc, realloc,zalloc,calloc,free等。
    随机数相关的rand,srand等。
    系统相关的system, getenv,setenv等。
    字符串转数值函数，atoi, atof,strtoul等。
    如果在代码中，调用了这个头文件中的函数或者宏定义，则需要引用该头文件。
    */
    
    int main()
    {
    	int ret = 0;
    	LinkStack *stack = NULL;
    	int a[5];
    	stack = LinkStack_Create();
    	if (NULL == stack)
    	{
    		ret = -1;
    		printf("func err LinkStack_Create():%d\n", ret);
    		return ret;
    	}
    
    	//压栈
    	for (int i = 0; i < 5; i++)
    	{
    		a[i] = i + 1;
    		LinkStack_Push(stack,&a[i]);
    	}
    
    	//显示大小和 栈顶元素
    	printf("Size:%d\n", LinkStack_Size(stack));
    
    	printf("Top:%d\n", *((int *)LinkStack_Top(stack)));
    
    	//出栈
    	while (LinkStack_Size(stack) > 0)
    	{
    		int tmp = *((int *)LinkStack_Pop(stack));
    		printf("%d ",tmp);
    
    	}
    	//销毁栈
    	LinkList_Destroy(stack);
    	 
    	system("pause");
    	return ret;
    }

[Link 1]: http://blog.csdn.net/weixin_40807247/article/details/79636295