c语言实现栈(顺序栈,链栈)

2023-11-27 10:14| 来源: 网络整理| 查看: 265

在这里插入图片描述

🎈个人主页:🎈 :✨✨✨初阶牛✨✨✨ 🐻推荐专栏: 🍔🍟🌯C语言进阶 🔑个人信条: 🌵知行合一 🍉本篇简介:>:讲解用c语言实现:“数据结构之"栈”,分别从"顺序栈"和"链栈"的接口讲解. 金句分享: ✨不是每一场雨后都有彩虹,但是晴天总是会到来!✨

前言

目录前言栈"栈"的常见接口实现一、顺序栈"顺序栈"的类型定义1.1 初始化栈1.2 入栈(压栈,向"栈"中插入数据)1.3 "出栈",删除"栈"中的数据1.4 判空(判断"栈"是否为空)1.5 打印"栈顶"元素1.6 返回"栈顶"元素1.7 "栈"的销毁二、链栈"链栈"的类型定义2.1 初始化"链栈"2.2 入栈(压栈,向"栈"中插入数据)2.3 "出栈",删除"栈"中的数据2.4 判空(判断"栈"是否为空)2.5 打印"栈顶"元素2.6 返回"栈顶"元素2.7 返回"链栈"的长度(有效数据的个数)2.8 "链栈"的销毁总结:总代码"顺序栈"总代码声明区(stack.h)接口实现区( stack.c)测试区(test.c) "链栈"总代码:声明区(SLStack.h)接口实现区(SLStack.c)测试区(test.c)

栈

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据也在栈顶

在这里插入图片描述

"栈"的常见接口实现 InitST:初始化栈STPush:入栈STPop:出栈STEmpty:判空(判断是否为空栈)PrintSTTop:打印栈顶元素STTop:返回栈顶元素(返回值类型:stacktype) 一、顺序栈 "顺序栈"的类型定义

如果友友们学过顺序表,这种类型可以随便拿捏.😄😄

代码:

typedef struct stack { stacktype* data;//一个指向连续内存空间的指针 int top;//记录栈顶元素的下标 int capacaity; }ST;

在这里插入图片描述

1.1 初始化栈

top指针: 由于数组的下标是从0开始,所以我们初始化"栈"时,可以将top指针(栈顶指针)初始化为-1,这样即可代表"栈"中无数据.

capacaity : 同顺序表一样,我们可以设置初始最大容量,后续不够可以扩容.

void InitST(ST* ps) { assert(ps); ps->top = -1;//此时栈中无数据 ps->capacaity = 4;//设置初始最大容量 ps->data = (stacktype*)malloc(ps->capacaity * sizeof(stacktype)); }

此处初始化后: 在这里插入图片描述

1.2 入栈(压栈,向"栈"中插入数据)

学到这里(顺序表和链表),对于"栈"的压栈操作很简单.

由于是顺序表实现栈,所以在进行插入操作之前要先进行"判满"操作,如果栈满了,要进行扩容.top是指向栈顶下标,需要将其往后移动一位,使其指向待插入位置.将新元素插入.此时刚好top为新的栈顶的下标.

图解: 在这里插入图片描述

代码:

void STPush(ST* ps, stacktype x)//压栈 { assert(ps); if (ps->top+1 == ps->capacaity)//检查"栈"满 { ps->capacaity *= 2;//扩容 stacktype* tmp = (stacktype*)realloc(ps->data, ps->capacaity * sizeof(stacktype)); if(tmp == NULL) { printf("增容失败\n"); } ps->data = tmp; } //将"栈顶指针"指向待插入位置 ps->top++; //将元素压栈 ps->data[ps->top] = x; } 1.3 “出栈”,删除"栈"中的数据

步骤:

删除数据时,需要判断"栈"是否为空.将top向前(下)移动一位,即表示有效数据位减1.

代码:

void STPop(ST* ps) { assert(ps); assert(!STEmpty(ps)); ps->top--; } 1.4 判空(判断"栈"是否为空)

当栈为空时,top为初始状态-1.

bool STEmpty(ST* ps)//判断是否为空栈,是空返回真 { assert(ps); if (ps->top == -1) { return true; } return false; } 1.5 打印"栈顶"元素 void PrintSTTop(ST* ps) { assert(ps); printf("%d", ps->data[ps->top]); } 1.6 返回"栈顶"元素 stacktype STTop(ST* ps)//返回栈顶元素 { assert(ps); return ps->data[ps->top]; } 1.7 "栈"的销毁

栈的销毁操作,因为malloc开辟出来的是连续的空间,所以只需要释放一次即可.

void STDestory(ST* ps) { assert(ps); free(ps->data); ps->data = NULL; ps->top = -1; ps->capacaity = 0; } 二、链栈 "链栈"的类型定义 typedef int stacktype; // 链栈的类型 typedef struct SLStackNode { stacktype data; struct SLStackNode* next; }SLStackNode;

其实我们不难发现,"链栈"的类型与单链表很相似,通过对"栈"的基本知识了解,"栈"只在一端进行"插入"和"删除"操作,为了用单链表实现这一要求.

同时为了提高效率:

链表分析尾插，尾删效率低，因为需要找尾巴头插，头插效率高,只需要改变头指针的指向

综上:我们利用不带头单链表的"头插(入栈)和头删(出栈)"来完成栈的各项基本操作.并且"栈"不需要进行随机访问其中的元素,只能从栈顶访问,链表是可以完成的.

2.1 初始化"链栈"

对于链表实现的栈,如果不带头结点: 我们不需要特意去写一个初始化函数.只需要创建一个栈顶指针,将其初始化指向NULL即可.(下面的代码是采用这种形式)

//创建一个栈顶指针,并完成初始化 SLStackNode* SLStack = NULL;

如果是带头结点的单链表: 我们可以定义一个初始化函数,申请一个头结点(头结点的数据域不存数据),将头结点返回.

//stack.c SLStackNode* InitStack() { SLStackNode* newnode = (SLStackNode*)malloc(sizeof(SLStackNode)); if (newnode == NULL) { perror("newnode malloc fail"); } return newnode; } //test.c SLStackNode* SLStack = InitStack(); 2.2 入栈(压栈,向"栈"中插入数据)

步骤:(与单链表的头插类似)

创建一个新节点.将新节点的next指针指向原"栈"的顶点更新栈顶指针(将栈顶指针指向新节点)

图解: 在这里插入图片描述

代码:

//入栈 void STPush(SLStackNode** pps, stacktype x)//压栈.相当于链表的头插 { assert(pps); //获取新的结点 SLStackNode* newnode = BuyNode(x); newnode->next = *pps;//将新节点的next指针指向原"栈"的顶点 *pps = newnode;//更新栈顶 } 2.3 “出栈”,删除"栈"中的数据

步骤:(与链表的头删操作类似)

判空,防止空链栈的删除操作记录原栈顶元素的地址.更新栈顶.(将栈顶指针指向原栈顶的下一个结点↓).释放原栈顶空间

图解: 在这里插入图片描述

void STPop(SLStackNode** pps)//出栈 { assert(pps);//二级指针不可能为空,如果为空就一定是传错了 assert(*pps);//防止空链栈的删除操作 SLStackNode* head = *pps;//记录栈顶元素的地址 *pps = (*pps)->next;//更新栈顶,即原来栈顶的下一个结点 free(head);//释放原栈顶空间 } 2.4 判空(判断"栈"是否为空)

链栈(不带头版本的)的初始状态是栈顶指针指向NULL.

bool STEmpty(SLStackNode* ps)//判断是否为空栈 { if (ps == NULL) { return true; } else return false; } 2.5 打印"栈顶"元素

栈顶元素即,栈顶指针指向的结点的数据域.

void PrintSTTop(SLStackNode* ps)//打印栈顶元素 { assert(ps); printf("%d ", ps->data); } 2.6 返回"栈顶"元素 stacktype STTop(SLStackNode* ps)//返回栈顶元素 { assert(ps); return ps->data; } 2.7 返回"链栈"的长度(有效数据的个数)

遍历这个栈即可求出栈的长度.(但其实一般情况下,栈是不允许遍历的,栈顶元素不出去,我们原则上不能访问栈顶下面的元素).

代码:

int LengthStack(SLStackNode* ps) { int count = 0; if (ps == NULL)//如果栈顶指针指向NULL,表示栈中没有元素 { return 0; } SLStackNode* tail = ps;//代替头指针遍历 while (ps) { count++;//如果该结点不为空,则有效数据个数+1 ps = ps->next; } return count;//返回有效数据的个数 } 2.8 "链栈"的销毁

与"链表"销毁类似.

void STDestory(SLStackNode* ps)//栈的销毁 { SLStackNode* del = ps; SLStackNode* next = ps;//用于记录下一个结点 while (next) { next = next->next; free(del); del = next; } //保持习惯置空 next == NULL; del = NULL; } 总结:

虽然链表和顺序表可以实现"栈",并且效率上,二者差距不大.

但是如果了解过寄存器的小伙伴,应该知道,如果数据在物理上是连续存储的,更加有利于数据的读取.

寄存器:

寄存器是CPU内部用来存放数据的一些小型存储区域，用来暂时存放参与运算的数据和运算结果。

因为cpu不是直接从硬盘读取数据的(嫌弃硬盘太慢了),而是通过寄存器(访问速度很快).

数据先被加载到缓存,此时如果数据在物理上是连续存储的,则在加载数据到缓存时,刚好将后面要读的数据也读走了,这样再读下一个数据时,就不需要再去硬盘读了.

🌰栗子: 在这里插入图片描述

综上,还是稍微建议使用顺序栈有一点点优势.

希望这篇文章对大家有帮助。欢迎小伙伴们私信提意见和提问哦！最后，小伙伴们的点赞就是给牛牛最大的支持，能不能给牛牛来一个一键三连呢？谢谢支持。在这里插入图片描述

总代码 "顺序栈"总代码声明区(stack.h) #include #include #include #include typedef int stacktype; typedef struct stack { stacktype* data; int top; int capacaity; }ST; void InitST(ST* ps); void STPush(ST* ps, stacktype x);//压栈 void STPop(ST* ps);//出栈 void PrintSTTop(ST* ps);//打印栈顶元素 bool STEmpty(ST* ps);//判断是否为空栈 stacktype STTop(ST* ps);//返回栈顶元素 void STDestory(ST* ps);//栈的销毁接口实现区( stack.c) #include "stack.h" //初始化栈 void InitST(ST* ps) { assert(ps); ps->top = -1; ps->capacaity = 4; ps->data = (stacktype*)malloc(ps->capacaity * sizeof(stacktype)); } //压栈 void STPush(ST* ps, stacktype x) { assert(ps); if (ps->top+1 == ps->capacaity) { ps->capacaity *= 2; stacktype* tmp = (stacktype*)realloc(ps->data, ps->capacaity * sizeof(stacktype)); if(tmp == NULL) { printf("增容失败\n"); } ps->data = tmp; } ps->top++; ps->data[ps->top] = x; } //出栈 void STPop(ST* ps) { assert(ps); assert(!STEmpty(ps)); ps->top--; } //打印栈顶元素 void PrintSTTop(ST* ps) { assert(ps); printf("%d", ps->data[ps->top]); } //判断是否为空栈,是空返回真 bool STEmpty(ST* ps) { assert(ps); if (ps->top == -1)//如果"栈"为空,则栈顶的下标为-1; { return true; } return false; } //返回栈顶元素 stacktype STTop(ST* ps) { assert(ps); return ps->data[ps->top];//反追栈顶元素 } //栈的销毁 void STDestory(ST* ps) { assert(ps); free(ps->data);//释放栈空间 ps->data = NULL; ps->top = -1; ps->capacaity = 0; } 测试区(test.c) #include "stack.h" void test1() { ST st1; InitST(&st1); STPush(&st1, 1);//压栈 STPush(&st1, 2);//压栈 STPush(&st1, 3);//压栈 STPush(&st1, 4);//压栈 int a=STTop(&st1); printf("栈顶元素为%d\n", a); while (!STEmpty(&st1)) { PrintSTTop(&st1);//打印栈顶元素 STPop(&st1); } STDestory(&st1); } int main() { test1(); return 0; } "链栈"总代码: 声明区(SLStack.h) #pragma once #include #include #include #include typedef int stacktype; // 链栈的类型 typedef struct SLStackNode { stacktype data; struct SLStackNode* next; }SLStackNode; //SLStackNode* InitStack(); void STPush(SLStackNode** pps, stacktype x);//压栈 void STPop(SLStackNode** pps);//出栈 void PrintSTTop(SLStackNode* ps);//打印栈顶元素 bool STEmpty(SLStackNode* ps);//判断是否为空栈 stacktype STTop(SLStackNode* ps);//返回栈顶元素 int LengthStack(SLStackNode* ps);//返回栈的长度 void STDestory(SLStackNode* ps);//栈的销毁接口实现区(SLStack.c) #include "SLStack.h" //SLStackNode* InitStack() //{ // SLStackNode* newnode = (SLStackNode*)malloc(sizeof(SLStackNode)); // if (newnode == NULL) // { // perror("newnode malloc fail"); // } // return newnode; //} SLStackNode* BuyNode(stacktype x)//创建新结点 { SLStackNode* newnode = (SLStackNode*)malloc(sizeof(SLStackNode)); assert(newnode);//防止申请结点失败 newnode->data = x; newnode->next = NULL; return newnode; } //入栈 void STPush(SLStackNode** pps, stacktype x)//压栈.相当于链表的头插 { assert(pps); //获取新的结点 SLStackNode* newnode = BuyNode(x); newnode->next = *pps; *pps = newnode; } void STPop(SLStackNode** pps)//出栈 { assert(pps);//二级指针不可能为空,如果为空就一定是传错了 assert(*pps);//防止空链栈的删除操作 SLStackNode* head = *pps;//记录栈顶元素的地址 *pps = (*pps)->next;//将栈顶向下移动一位 free(head);//释放栈顶空间 } void PrintSTTop(SLStackNode* ps)//打印栈顶元素 { assert(ps); printf("%d ", ps->data); } bool STEmpty(SLStackNode* ps)//判断是否为空栈 { if (ps == NULL) { return true; } else return false; } stacktype STTop(SLStackNode* ps)//返回栈顶元素 { assert(ps); return ps->data; } int LengthStack(SLStackNode* ps) { int count = 0; if (ps == NULL) { return 0; } SLStackNode* tail = ps; while (ps) { count++; ps = ps->next; } return count; } void STDestory(SLStackNode* ps)//栈的销毁 { SLStackNode* del = ps; SLStackNode* next = ps;//用于记录下一个结点 while (next) { next = next->next; free(del); del = next; } //保持习惯置空 next == NULL; del = NULL; } 测试区(test.c) #include "SLStack.h" void test1() { SLStackNode* SLStack = NULL; //SLStackNode* SLStack = InitStack(); STPush(&SLStack, 1);//压栈 STPush(&SLStack, 2);//压栈 STPush(&SLStack, 3);//压栈 STPush(&SLStack, 4);//压栈 STPush(&SLStack, 5);//压栈 STPush(&SLStack, -1);//压栈 STPush(&SLStack, -2);//压栈 int a = STTop(SLStack); printf("栈顶元素为%d\n", a); int length = LengthStack(SLStack); printf("链表的长度为:%d\n", length); while (!STEmpty(SLStack)) { PrintSTTop(SLStack);//打印栈顶元素 STPop(&SLStack); } STDestory(SLStack); } int main() { test1(); return 0; }

【本文地址】

c语言实现栈(顺序栈,链栈)

c语言实现栈(顺序栈,链栈)

今日新闻

推荐新闻