栈的顺序存储设计与实现(C语言版本)

Dear 丶 2022-05-24 01:53 144阅读 0赞

# Stack基本概念 #

栈是一种  特殊的线性表

栈仅能在线性表的一端进行操作

栈顶(Top)：允许操作的一端

栈底(Bottom)：不允许操作的一端

![70][]

## Stack的常用操作 ##

创建栈

销毁栈

清空栈

进栈

出栈

获取栈顶元素

获取栈的大小

# 栈的顺序存储设计与实现 #

## 1、基本概念 ##

<table> 
 <tbody> 
  <tr> 
   <td><pre><code>//线性表顺序存储设计与实现测试框架
//SeqList.h

#ifndef _SEQLIST_H_
#define _SEQLIST_H_

typedef void SeqList;
typedef void SeqListNode;

//这两句话意思：
//C语言里面的typedef, 字面上理解就是类型的定义, 也就是给内置的或自定义的数据类型重新命名
//SeqList* SeqList_Create(int capacity); //这样一看返回值就知道是返回值是链表
//void * SeqList_Create(int capacity); //如果这样，使用者一看只知道是返回指针，不知道具体的，可读性很差
//所以才会给void起别名，封装好的底层函数，提供给使用者使用，使用者会给容易懂

//创建并且返回一个空的线性表
SeqList* SeqList_Create(int capacity);

//销毁一个线性表list
void SeqList_Destroy(SeqList* list);

//将一个线性表list中的所有元素清空, 线性表回到创建时的初始状态
void SeqList_Clear(SeqList* list);

//返回一个线性表list中的所有元素个数
int SeqList_Length(SeqList* list);

//返回一个线性表list中的容量
int SeqList_Capacity(SeqList* list);

//向一个线性表list的pos位置处插入新元素node
int SeqList_Insert(SeqList* list, SeqListNode* node, int pos);

//获取一个线性表list的pos位置处的元素
SeqListNode* SeqList_Get(SeqList* list, int pos);

//删除一个线性表list的pos位置处的元素  返回值为被删除的元素，NULL表示删除失败
SeqListNode* SeqList_Delete(SeqList* list, int pos);

#endif</code></pre></td> 
  </tr> 
 </tbody> 
</table>

//SeqStack.h
    #ifndef _SEQSTACK_H_
    #define _SEQSTACK_H_
    
    
    //栈的顺序存储设计
    //这句话意思：
    //C语言里面的typedef, 字面上理解就是类型的定义, 也就是给内置的或自定义的数据类型重新命名
    //SeqStack *SeqStack_Creat(int capacity); //这样一看返回值就知道是返回值是栈
    //void SeqStack_Destory(SeqStack *stack); //如果这样，使用者一看只知道是返回指针，不知道具体的，可读性很差
    //所以才会给void起别名，封装好的底层函数，提供给使用者使用，使用者会给容易懂
    typedef void SeqStack;
    
    //栈的创建
    SeqStack *SeqStack_Creat(int capacity);
    
    //栈的销毁
    void SeqStack_Destory(SeqStack *stack);
    
    //栈的清除
    void SeqStack_Clear(SeqStack *stack);
    
    //栈的压栈
    int Seqstack_Push(SeqStack *stack, void *item);//item-压进来的元素地址
    
    //栈的出栈
    void *Seqstack_Pop(SeqStack *stack);
    
    
    //获取栈顶元素
    void *Seqstack_Top(SeqStack *stack);
    
    //获取栈的元素个数
    int Seqstack_Size(SeqStack *stack);
    
    //获取栈的容量
    int Seqstack_Capacity(SeqStack *stack);
    
    
    
    #endif

//SeqList.c
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include "SeqList.h"
    
    
    //在结构体中套一级指针
    typedef struct _tag_SeqList
    {
    	int length;//线性表的长度
    	int capacity;//数组的长度-存放线性表的存储空间的长度
    	unsigned int *node;//链表需要有内存空间存储装元素-根据容量来分配内存空间-需要动态分配内存空间  int node[]
    }TSeqList;
    
    
    //创建并且返回一个空的线性表
    SeqList* SeqList_Create(int capacity)
    {
    	int ret = 0;
    	if (capacity <= 0)
    	{
    		ret = -1;
    		printf("func err (capacity <= 0):%d\t", ret);
    		return NULL;
    	}
    	//1 线性表申请动态内存空间
    	TSeqList *tmp = (TSeqList *)malloc(sizeof(TSeqList));//开辟一片内存空间，大小是TSeqList类这么大
    	if (NULL == tmp)
    	{
    		ret = -2;
    		printf("func err malloc:%d\t", ret);
    		return NULL;
    	}
    	//开辟的内存,完成初始化
    	memset(tmp,0,sizeof(TSeqList));
    
    	//2 根据容量分配内存大小
    	tmp->node = (unsigned int *)malloc(sizeof(unsigned int)*capacity);//创建node结点的内存空间大小-相当于二维数组的行元素个数
    	if (NULL == tmp->node)
    	{
    		ret = -3;
    		printf("func err malloc:%d\t", ret);
    		return NULL;
    	}
    	tmp->capacity = capacity;
    	tmp->length = 0;
    
    	return tmp;
    }
    
    //销毁一个线性表list
    void SeqList_Destroy(SeqList* list)
    {
    	int ret = 0;
    	if (NULL == list)
    	{
    		ret = -1;
    		printf("func err (NULL == list):%d\t", ret);
    	}
    	//1 缓存下来 进行操作
    	TSeqList *tmp = NULL;
    	tmp = (TSeqList *)list;
    	//2 先申请 后释放
    	if (tmp->node != NULL)
    	{
    		free(tmp->node);
    	}
    	if (tmp!=NULL)
    	{
    		free(tmp);
    	}
    }
    
    
    //将一个线性表list中的所有元素清空, 线性表回到创建时的初始状态
    void SeqList_Clear(SeqList* list)
    {
    	int ret = 0;
    	if (NULL == list)
    	{
    		ret = -1;
    		printf("func err (NULL == list):%d\t", ret);
    	}
    	//1 缓存下来 进行操作
    	TSeqList *tmp = NULL;
    	tmp = (TSeqList *)list;
    	//2 线性表中的长度置空
    	tmp->length = 0;
    	//3 重新将线性表中创建的结点初始化
    	memset(list,0,tmp->capacity * sizeof(unsigned int)); // 会把所有的置空
    }
    
    
    //返回一个线性表list中的所有元素个数
    int SeqList_Length(SeqList* list)
    {
    	int ret = 0;
    	if (NULL == list)
    	{
    		ret = -1;
    		printf("func err (NULL == list):%d\t", ret);
    		return ret;
    	}
    	//1 缓存下来 进行操作
    	TSeqList *tmp = NULL;
    	tmp = (TSeqList *)list;
    
    	return tmp->length;
    }
    
    
    //返回一个线性表list中的容量
    int SeqList_Capacity(SeqList* list)
    {
    	int ret = 0;
    	if (NULL == list)
    	{
    		ret = -1;
    		printf("func err (NULL == list):%d\t", ret);
    		return ret;
    	}
    	//1 缓存下来 进行操作
    	TSeqList *tmp = NULL;
    	tmp = (TSeqList *)list;
    	return tmp->capacity;
    }
    
    
    //向一个线性表list的pos位置处插入新元素node
    int SeqList_Insert(SeqList* list, SeqListNode* node, int pos)
    {
    	int ret = 0;
    	if (NULL == list || NULL == node||pos < 0)
    	{
    		ret = -1;
    		printf("func err (NULL == list || NULL == node||pos < 0):%d\t", ret);
    		return ret;
    	}
    	//1 缓存下来 进行操作
    	TSeqList *tmp = NULL;
    	tmp = (TSeqList *)list;
    	//注意1：线性表长度应该小于等于数组的长度
    	if (tmp->length >=tmp->capacity)
    	{
    		ret = -2;
    		printf("func err (tmp->length >=tmp->capacity):%d\t", ret);
    		return ret;
    	}
    	//注意2：容错修正 假设容量为20，此时线性表长度为6,pos却为10,这个时候可以做容错修正,直接修正为尾插法
    	if (pos >tmp->length)
    	{
    		pos = tmp->length;
    	}
    	//2 元素后移
    	int i;
    	for ( i = tmp->length; i > pos; i--)
    	{
    		tmp->node[i] = tmp->node[i - 1];//后移
    		//t[pos+1] = t[pos+1-1]=t[pos]
    	}
    	//3 空出的位置插入新结点
    	tmp->node[i] = (unsigned int )node;//这里装二维数组的行的一个元素,这个行元素指向业务结点teacher这个结构体,所以teacher里面装多少信息,都是可以的
    	//4 线性表长度+1
    	tmp->length++;
    
    	return ret;
    }
    
    
    //获取一个线性表list的pos位置处的元素
    SeqListNode* SeqList_Get(SeqList* list, int pos)
    {
    	int ret = 0;
    	if (NULL == list || pos < 0)
    	{
    		ret = -1;
    		printf("func err (NULL == list || pos < 0):%d\t", ret);
    		return NULL;
    	}
    	//1 缓存下来 进行操作
    	TSeqList *tmp = NULL;
    	tmp = (TSeqList *)list;
    	//获取一个线性表list的pos位置处的元素
    	tmp = (SeqListNode *)tmp->node[pos];
    
    	return tmp;
    }
    
    
    //删除一个线性表list的pos位置处的元素  返回值为被删除的元素，NULL表示删除失败
    SeqListNode* SeqList_Delete(SeqList* list, int pos)
    {
    	int ret = 0;
    	if (NULL == list || pos < 0)
    	{
    		ret = -1;
    		printf("func err (NULL == list || pos < 0):%d\t", ret);
    		return NULL;
    	}
    	//1 缓存下来 进行操作
    	TSeqList *tmp = NULL;
    	tmp = (TSeqList *)list;
    
    	//2 缓存删除元素
    	TSeqList *Deletemp = NULL;
    	Deletemp = (SeqListNode *)tmp->node[pos];
    
    	//3 前移
    	for (int i = pos+1; i < tmp->length; i++)
    	{
    		tmp->node[i-1] = tmp->node[i];
    	}
    	//4 删除元素后 线性表长度减1
    	tmp->length--;
    
    	return Deletemp;
    }

//SeqStack.c
    #include <stdlib.h>
    #include <string.h>
    #include <stdio.h>
    #include "SeqList.h"
    #include "SeqStack.h"
    
    
    //栈的创建--相当于链表的创建
    SeqStack *SeqStack_Creat(int capacity)
    {
    	return SeqList_Create(capacity);
    }
    
    //栈的销毁--相当于链表的销毁
    void SeqStack_Destory(SeqStack *stack)
    {
    	SeqList_Destroy(stack);
    }
    
    
    //栈的清除--相当于链表的清除
    void SeqStack_Clear(SeqStack *stack)
    {
    	SeqList_Clear(stack);
    }
    
    
    //栈的压栈--相当于链表的尾部插入元素
    //item-压进来的元素地址
    int Seqstack_Push(SeqStack *stack, void *item)
    {
    	return SeqList_Insert(stack,item,SeqList_Length(stack));
    }
    
    
    //栈的出栈--相当于 链表的尾部删除元素--注意pos位置
    void *Seqstack_Pop(SeqStack *stack)
    {
    	return SeqList_Delete(stack,SeqList_Length(stack)-1);
    }
    
    
    
    //获取栈顶元素--相当于获取链表的尾部元素
    void *Seqstack_Top(SeqStack *stack)
    {
    	return SeqList_Get(stack, SeqList_Length(stack) - 1);
    }
    
    
    //获取栈的元素个数--相当于链表的长度
    int Seqstack_Size(SeqStack *stack)
    {
    	return SeqList_Length(stack);
    }
    
    //获取栈的容量 相当于链表的容量 是不变的，分配好的
    int Seqstack_Capacity(SeqStack *stack)
    {
    	return SeqList_Capacity(stack);
    }

//栈的顺序存储设计与实现测试框架
    //text.c
    #include <stdlib.h>
    #include <string.h>
    #include <stdio.h>
    #include "SeqList.h"
    #include "SeqStack.h"
    
    
    int main()
    {
    	int ret = 0;
    	int a[10];
    	//1 栈的创建
    	SeqStack *stack = NULL;
    	stack = SeqStack_Creat(10);
    	if (NULL == stack)
    	{
    		ret = -1;
    		printf("func err SeqStack_Creat():%d\n", ret);
    		return ret;
    	}
    	//2 压栈
    	for (int i = 0; i < 5; i++)
    	{
    		a[i] = i + 1;
    		Seqstack_Push(stack,&a[i]);
    	}
    
    	//3 栈的属性
    	printf("Seqstack_Capacity:%d\n", Seqstack_Capacity(stack));
    	printf("Seqstack_Size:%d\n", Seqstack_Size(stack));
    	printf("Seqstack_Top:%d\n", *((int *)Seqstack_Top(stack)));
    
    	//4 出栈
    	while (Seqstack_Size(stack)>0)
    	{
    		printf("%d\n", *((int *)Seqstack_Pop(stack)));
    	}
    
    	//5 销毁栈
    	SeqStack_Destory(stack);
    	system("pause");
    	return 0;
    }

[70]: /images/20220524/6623ebbc0af9449a88f30a20b6c47b28.png