栈的顺序存储

时间：2022-03-07 03:40:31

Stack基本概念
栈是一种 特殊的线性表
栈仅能在线性表的一端进行操作
栈顶(Top)：同意操作的一端
栈底(Bottom)：不同意操作的一端

栈的顺序存储

Stack的经常使用操作
创建栈
销毁栈
清空栈
进栈
出栈
获取栈顶元素
获取栈的大小 

栈模型和链表模型关系分析

栈的顺序存储



栈的顺序存储设计与实现

栈的顺序存储



// seqlist.h // 顺序存储结构线性表的API声明 #ifndef __MY_SEQLIST_H__ #define __MY_SEQLIST_H__ typedef void SeqList; typedef void SeqListNode; //链表 创建 SeqList* SeqList_Create(int capacity); //链表 销毁 void SeqList_Destroy(SeqList* list); ////链表 清空 void SeqList_Clear(SeqList* list); //链表 长度 int SeqList_Length(SeqList* list); //链表 容量 int SeqList_Capacity(SeqList* list); //链表 在某一个位置 插入元素 int SeqList_Insert(SeqList* list, SeqListNode* node, int pos); //获取某一个位置的链表结点 SeqListNode* SeqList_Get(SeqList* list, int pos); //删除某一个位置的结点 SeqListNode* SeqList_Delete(SeqList* list, int pos); #endif //__MY_SEQLIST_H__
// seqList.cpp // 顺序存储结构的栈API实现 #include <iostream> #include <cstdio> #include "seqlist.h" using namespace std; typedef struct _tag_SeqList { int capacity; int length; int **node; }TSeqList; //链表 创建 SeqList* SeqList_Create(int capacity) { int ret = -1; TSeqList *tmp = NULL; tmp = (TSeqList *)malloc(sizeof(TSeqList)); if (tmp == NULL) { ret = 1; printf("function SeqList_Create() err:%d\n", ret); return NULL; } memset(tmp, 0, sizeof(TSeqList)); tmp->capacity = capacity; tmp->length = 0; tmp->node = (int **)malloc(sizeof(void *) * capacity); if (tmp->node == NULL) { ret = 2; printf("function SeqList_Create() err:%d\n", ret); return NULL; } memset(tmp->node, 0, sizeof(void *) * capacity); return tmp; } //链表 创建 int SeqList_Create2(int capacity, SeqList**handle) { int ret = 0; TSeqList *tmp = NULL; tmp = (TSeqList *)malloc(sizeof(TSeqList)); if (tmp == NULL) { ret = 1; printf("func SeqList_Create2() err :%d \n", ret); return ret; } memset(tmp, 0, sizeof(TSeqList)); tmp->capacity = capacity; tmp->length = 0; tmp->node = (int **)malloc(sizeof(void *) * capacity); if (tmp->node == NULL) { ret = 2; printf("func SeqList_Create2() malloc err :%d \n", ret); return ret; } *handle = tmp; return ret; } //链表 销毁 void SeqList_Destroy(SeqList* list) { if (list == NULL) { return; } TSeqList *tmp = (TSeqList *)list; if (tmp->node != NULL) { free(tmp->node); } free(tmp); return; } ////链表 清空 void SeqList_Clear(SeqList* list) { if (list == NULL) { return; } TSeqList *tmp = (TSeqList *)list; tmp->length = 0; memset(tmp->node, 0, sizeof(tmp->node)); return; } //链表 长度 int SeqList_Length(SeqList* list) { if (list == NULL) { return -1; } TSeqList *tmp = (TSeqList *)list; return tmp->length; } //链表 容量 int SeqList_Capacity(SeqList* list) { if (list == NULL) { return -1; } TSeqList *tmp = (TSeqList *)list; return tmp->capacity; } //链表 在某一个位置 插入元素 int SeqList_Insert(SeqList* list, SeqListNode* node, int pos) { if (list == NULL || node == NULL || pos < 0) { return -1; } TSeqList *tList = (TSeqList *)list; // 假设满了 if (tList->length >= tList->capacity) { return -2; } // 假设pos的位置超出了length。即中间空了一些位置 if (pos > tList->length) { pos = tList->length; } for (int i = tList->length; i > pos; --i) { tList->node[i] = tList->node[i - 1]; } tList->node[pos] = (int *)node; ++tList->length; return 0; } //获取某一个位置的链表结点 SeqListNode* SeqList_Get(SeqList* list, int pos) { TSeqList *tList = (TSeqList *)list; if (list == NULL || pos < 0 || pos >= tList->length) { return NULL; } SeqListNode *tListNode = NULL; tListNode = (int *)tList->node[pos]; return tListNode; } //删除某一个位置的结点 SeqListNode* SeqList_Delete(SeqList* list, int pos) { TSeqList *tList = (TSeqList *)list; SeqListNode *tListNode = NULL; if (list == NULL || pos < 0 || pos >= tList->length) { return NULL; } tListNode = tList->node[pos]; for (int i = pos + 1; i < tList->length; ++i) { tList->node[i - 1] = tList->node[i]; } --tList->length; // 别忘了长度减一 return tListNode; }
// seqstack.h // 顺序存储结构的栈API声明 #ifndef __SEQSTACK_H__ #define __SEQSTACK_H__ typedef void SeqStack; // 创建栈 SeqStack* SeqStack_Create(int capacity); // 销毁栈 void* SeqStack_Destroy(SeqStack* stack); // 清空栈 void* SeqStack_Clear(SeqStack* stack); // 元素入栈 int SeqStack_Push(SeqStack* stack, void* item); // 弹出栈顶元素 void* SeqStack_Pop(SeqStack* stack); // 获取栈顶元素 void* SeqStack_Top(SeqStack* stack); // 获取栈的大小 int SeqStack_Size(SeqStack* stack); // 获取栈的容量 int SeqStack_Capacity(SeqStack* stack); #endif
// seqstack.cpp // 顺序存储结构栈的API实现 // 调用了之前写好的顺序链表API #include <cstdio> #include "seqlist.h" #include "seqstack.h" // 创建栈，相当于创建一个线性表 SeqStack* SeqStack_Create(int capacity) { return SeqList_Create(capacity); } // 销毁栈。相当于销毁链表 void* SeqStack_Destroy(SeqStack* stack) { SeqList_Destroy(stack); return NULL; } // 清空栈，相当于清空链表 void* SeqStack_Clear(SeqStack* stack) { SeqList_Clear(stack); return NULL; } // 元素入栈，，相当于在线性表（数组）的尾部加入元素 int SeqStack_Push(SeqStack* stack, void* item) { return SeqList_Insert(stack, item, SeqList_Length(stack)); } // 弹出栈顶元素，相当于从线性表的尾部删除元素 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); }
// main.cpp // 顺序结构栈的測试程序 #include <stdio.h> #include "seqstack.h" void play() { int i = 0; SeqStack *stack = NULL; int a[10]; for (i = 0; i < 10; ++i) { a[i] = i + 1; } stack = SeqStack_Create(20); // 入栈 for (int i = 0; i < 5; ++i) { SeqStack_Push(stack, &a[i]); } printf("len:%d \n", SeqStack_Size(stack)); printf("capacity:%d \n", SeqStack_Capacity(stack)); printf("top:%d \n", *((int *)SeqStack_Top(stack))); // 元素出栈 while (SeqStack_Size(stack)) { printf("%d ", *((int *)SeqStack_Pop(stack))); } SeqStack_Destroy(stack); return; } int main() { play(); return 0; }

project代码详情：Github

相关文章