柚子快报app778899分享：栈的链式存储 - API实现
基本概念
其它概念详情參看前一篇博文：栈的顺序存储 - 设计与实现 - API实现
这里也是运用了链表的链式存储API高速实现了栈的API。
代码：
// linkstack.h
// 链式存储栈的API声明
#ifndef _MY_LINKSTACK_H_
#define _MY_LINKSTACK_H_
typedef void LinkStack;
// 创建栈
LinkStack* LinkStack_Create();
// 销毁栈
void LinkStack_Destroy(LinkStack* stack);
// 清空栈
void LinkStack_Clear(LinkStack* stack);
// 将item入栈
int LinkStack_Push(LinkStack* stack, void* item);
// 弹出栈顶元素
void* LinkStack_Pop(LinkStack* stack);
// 获取栈顶元素
void* LinkStack_Top(LinkStack* stack);
// 获取栈的大小
int LinkStack_Size(LinkStack* stack);
#endif //_MY_LINKSTACK_H_
// linkstack.cpp
// 链式存储栈的API实现
#include
#include
#include "linkstack.h"
#include "linklist.h"
typedef void LinkStack;
typedef struct _tag_LinkStack
{
LinkListNode node;
void* item;
}TLinkStack;
// 创建一个栈，相当于创建一个线性表
LinkStack* LinkStack_Create()
{
return LinkList_Create();
}
// 销毁栈
void LinkStack_Destroy(LinkStack* stack)
{
LinkStack_Clear(stack); // 释放栈的结点
LinkList_Destroy(stack); // 释放句柄
return;
}
// 清空栈
void LinkStack_Clear(LinkStack* stack)
{
while (LinkList_Length(stack)) {
LinkStack_Pop(stack);
}
return;
}
// 向栈中加入元素，相当于用头插法向线性表加入结点
int LinkStack_Push(LinkStack* stack, void* item)
{
int ret = 0;
TLinkStack *tStack = NULL;
// 把void* item转化成链表结点
tStack = (TLinkStack *)malloc(sizeof(TLinkStack));
tStack->item = item;
// 头插法插入结点
ret = LinkList_Insert(stack, (LinkListNode *)tStack, 0);
if (ret) {
printf("function LinkStack_Push err: %d.\n", ret);
free(tStack);
return ret;
}
return ret;
}
// 弹出栈顶元素，相当于从线性表中删除0号元素
void* LinkStack_Pop(LinkStack* stack)
{
TLinkStack *tStack = NULL;
void* item = NULL;
tStack = (TLinkStack *)LinkList_Delete(stack, 0);
if (tStack == NULL) {
printf("function LinkStack_Pop err.\n");
return NULL;
}
// 把链表结点转化成栈结点
item = tStack->item;
free(tStack); // 记得释放创建时候malloc的内存
return item;
}
// 获取栈顶元素
void* LinkStack_Top(LinkStack* stack)
{
TLinkStack *tStack = NULL;
void* item = NULL;
tStack = (TLinkStack *)LinkList_Get(stack, 0);
if (tStack == NULL) {
printf("function LinkStack_Top err.\n");
return NULL;
}
item = tStack->item;
return item;
}
// 获取栈的大小
int LinkStack_Size(LinkStack* stack)
{
return LinkList_Length(stack);
}
// main.cpp
// 栈链式存储的測试程序
#include
#include "linkstack.h"
const int maxn = 5;
void play()
{
int a[maxn];
for (int i = 0; i < maxn; ++i) {
a[i] = i + 1;
}
LinkStack *stack = NULL;
stack = LinkStack_Create(); // 创建栈
// 入栈
for (int i = 0; i < maxn; ++i) {
LinkStack_Push(stack, &a[i]);
}
// 栈属性
printf("size: %d\n", LinkStack_Size(stack));
printf("top: %d\n", *((int *)LinkStack_Top(stack)));
LinkStack_Destroy(stack);
}
int main()
{
play();
return 0;
}
// linklist.h
#ifndef _MYLINKLIST_H_
#define _MYLINKLIST_H_
typedef void LinkList;
typedef struct _tag_LinkListNode
{
struct _tag_LinkListNode* next;
}LinkListNode;
LinkList* LinkList_Create();
void LinkList_Destroy(LinkList* list);
void LinkList_Clear(LinkList* list);
int LinkList_Length(LinkList* list);
int LinkList_Insert(LinkList* list, LinkListNode* node, int pos);
LinkListNode* LinkList_Get(LinkList* list, int pos);
LinkListNode* LinkList_Delete(LinkList* list, int pos);
#endif
// linklist.cpp
#include
#include
#include "linklist.h"
using namespace std;
typedef void LinkList;
typedef struct _tag_LinkList
{
LinkListNode header;
int length;
}TLinkList;
LinkList* LinkList_Create()
{
TLinkList *tmp = NULL;
tmp = (TLinkList *)malloc(sizeof(TLinkList));
if (tmp == NULL) {
printf("function LinkList_Create() err.\n");
return NULL;
}
memset(tmp, 0, sizeof(TLinkList)); // 初始化为空链表
return tmp;
}
void LinkList_Destroy(LinkList* list)
{
if (list == NULL) {
return;
}
free(list);
return;
}
void LinkList_Clear(LinkList* list)
{
if (list == NULL) {
return;
}
TLinkList *tList = NULL;
tList = (TLinkList *)list;
tList->header.next = NULL;
tList->length = 0;
return;
}
int LinkList_Length(LinkList* list)
{
if (list == NULL) {
return -1;
}
TLinkList *tList = NULL;
tList = (TLinkList *)list;
return tList->length;
}
int LinkList_Insert(LinkList* list, LinkListNode* node, int pos)
{
if (list == NULL || node == NULL || pos < 0) {
return -1;
}
TLinkList *tList = NULL;
tList = (TLinkList *)list;
LinkListNode *cur = NULL;
cur = &(tList->header);
// 对pos的容错处理。假设pos过大。改为最后面
if (pos > LinkList_Length(list)) {
pos = LinkList_Length(list);
}
// 移动到须要插入的位置
for (int i = 0; i < pos; ++i) {
cur = cur->next;
}
// 插入
node->next = cur->next;
cur->next = node;
++tList->length;
return 0;
}
LinkListNode* LinkList_Get(LinkList* list, int pos)
{
if (list == NULL || pos < 0 || pos >= LinkList_Length(list)) {
return NULL;
}
TLinkList *tList = NULL;
tList = (TLinkList *)list;
LinkListNode *cur = NULL;
cur = &(tList->header);
for (int i = 0; i < pos; ++i) {
cur = cur->next;
}
return cur->next;
}
LinkListNode* LinkList_Delete(LinkList* list, int pos)
{
if (list == NULL || pos < 0 || pos >= LinkList_Length(list)) {
return NULL;
}
TLinkList *tList = NULL;
tList = (TLinkList *)list;
LinkListNode *cur = NULL;
cur = &(tList->header);
for (int i = 0; i < pos; ++i) {
cur = cur->next;
}
LinkListNode *ret = NULL;
ret = cur->next;
// 删除结点
cur->next = ret->next;
--tList->length;
return ret;
}
project代码详情：Github
柚子快报app778899分享：栈的链式存储 - API实现
参考文章
发表评论