【数据结构与算法（C 语言）】栈的基本操作函数（动图演示） 及 栈的实际应用之一：进制转换

2024-06-01 20:12
文章标签 基本操作 动图 数据结构 进制 演示 算法 函数 转换 语言 应用 实际

本文主要是介绍【数据结构与算法（C 语言）】栈的基本操作函数（动图演示） 及 栈的实际应用之一：进制转换，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

  • 1. 前言
  • 2. 结构及基本操作函数：
    • 2.1 栈的结构类型 Stack
    • 2.2 初始化栈 InitStack
    • 2.3 销毁栈 DestroyStack
    • 2.4 清空栈 ClearStack
    • 2.5 判断栈是否为空 StackEmpty
    • 2.6 获取stack的长度 StackLength
    • 2.7 获取栈顶元素 GetTop
    • 2.8 入栈 Push
    • 2.9 出栈 Pop
    • 2.10 访问元素
    • 2.11 遍历栈的所有元素
  • 3. 严蔚敏版完整测试代码:
    • 3.1 代码
    • 3.2 运行结果:
  • 4. 简易版完整测试代码
    • 4.1 完整代码
    • 4.2 运行结果
  • 5. 栈的应用 ：进制转化
    • 5.1 转化函数
    • 5.2 进制转化完整代码
    • 5.3 运行结果

1. 前言

栈的操作思想：先进后出
本文的基本操作函数使用 严蔚敏版的《数据结构与算法》中的实现方式。此方式可以实现动态的分配栈空间内存。
本文还有一个更为简单的栈操作方式，虽简单，但是就失去了动态分配栈空间内存的优势。栈空间的最大值会被限制。
对比之下，严教授的编程思想还是比一般人厉害。

入栈和出栈的示意图：
在这里插入图片描述

在这里插入图片描述

2. 结构及基本操作函数：

2.1 栈的结构类型 Stack

typedef struct Stack{SElemType * base; //栈底指针SElemType * top; //栈顶指针int stacksize;   //当前已分配的存储空间
} SqStack;

2.2 初始化栈 InitStack

功能： 初始化栈 ，分配栈底内存空间，栈空间大小设置初始值

/*初始化栈*/
Status InitStack(SqStack * stack)
{stack->base =(SElemType * )malloc(STACK_INIT_SIZE* sizeof(SElemType));if(!stack->base)exit(EXIT_FAILURE);stack->top=stack->base;	// 栈顶指针初始 指向栈底;stack->stacksize=STACK_INIT_SIZE;return TRUE;
}

2.3 销毁栈 DestroyStack

功能：销毁栈，释放内存空间

/*销毁栈 */
Status DestroyStack(SqStack * stack)
{free(stack->base);stack->top=stack->base=NULL;stack->stacksize=0;return TRUE;
}

2.4 清空栈 ClearStack

功能： 清空栈内数据，区别于销毁栈的释放内存。只需要将栈顶指针等于栈底指针

/* 清理stack,只需要将top指针指向base*/
Status ClearStack(SqStack * stack)
{stack->top=stack->base;return TRUE;
}

2.5 判断栈是否为空 StackEmpty

功能： 判断栈是否为空，在实际应用中，这个函数经常要用到

/* 判断栈是否为空 */
Status StackEmpty(SqStack stack)
{if(stack.base == stack.top)return TRUE;else return FALSE;
}

2.6 获取stack的长度 StackLength

/* 获取stack的长度 */
int StackLength(SqStack stack)
{return stack.top - stack.base;
}

2.7 获取栈顶元素 GetTop

功能 ：获取栈顶元素，并将值传递给 e，注意区别于下面的pop函数,GetTop是不改变栈的元素。

/* 获取栈顶元素，并将值传递给 e*/
Status GetTop(SqStack stack, SElemType * e)
{if(StackEmpty(stack))return FALSE;*e = *--stack.top;
}

2.8 入栈 Push

功能： 入栈, 将元素e压入栈中。这里面就涉及到一个扩容问题，如果栈的空间不够，可以增加栈的内存空间。

/*入栈, 将元素e压入栈中 */
Status Push(SqStack * stack,SElemType e)
{if(stack->top - stack->base >= stack->stacksize)//如果空间不够的话，扩容{stack->base =(SElemType *) realloc(stack->base,(stack->stacksize+STACKINCREMENT)* sizeof(SElemType));if(!stack->base)exit(EXIT_FAILURE);stack->stacksize += STACKINCREMENT;}*stack->top++ = e;return TRUE;
}

示意图 :

2.9 出栈 Pop

/*出栈， 从栈顶弹出元素，并将元素值传递给e*/
Status Pop(SqStack * stack ,SElemType * e)  
{if(!stack->base)return FALSE;if(stack->base == stack->top) //空栈return FALSE;*e = *(--stack->top);return TRUE;
}

示意图 ：

以上的函数在各类实际应用中基本都不用修改，可以直接使用。下面还有两个函数，栈元素的访问，一般在实际应用中，根据需要自行的灵活修改。

2.10 访问元素

功能 ：访问元素，因为是测试用的，所以打印就行了

/* 访问元素 */
void Visit(SElemType e)
{printf("%d\t", e);
}

2.11 遍历栈的所有元素

功能：遍历stack,对stack的每一个元素调用visit函数。

/* 遍历stack,对stack的每一个元素调用visit函数 */
Status StackTraverse(SqStack stack,void (*visit)(SElemType e))
{SElemType * curElem=stack.base;if(StackEmpty(stack))return FALSE;while(curElem!=stack.top)visit(*curElem++);return TRUE;
}

3. 严蔚敏版完整测试代码:

3.1 代码

/*此版本为严蔚敏老师版本此版本，栈的空间大小可以*/#include <stdio.h>
#include <stdlib.h>#define STACK_INIT_SIZE 100  //初始内存空间
#define STACKINCREMENT  10   // 内存空间增量#define TRUE 1
#define FALSE 0typedef int SElemType;typedef struct Stack{SElemType *base; //栈底指针SElemType * top; //栈顶指针int stacksize;   //当前已分配的存储空间
} SqStack;typedef int Status;Status InitStack(SqStack * stack);
Status DestroyStack(SqStack * stack);
Status ClearStack(SqStack * stack);
Status StackEmpty(SqStack stack);
int StackLength(SqStack stack);
Status GetTop(SqStack stack, SElemType * e);
Status Push(SqStack * stack,SElemType e);
Status Pop(SqStack * stack, SElemType *e);
void Visit(SElemType e);
Status StackTraverse(SqStack stack,void (*visit)(SElemType));/*初始化栈*/
Status InitStack(SqStack * stack)
{stack->base =(SElemType * )malloc(STACK_INIT_SIZE* sizeof(SElemType));if(!stack->base)exit(EXIT_FAILURE);stack->top=stack->base;	// 栈顶指针初始 指向栈底;stack->stacksize=STACK_INIT_SIZE;return TRUE;
}/*销毁栈 */
Status DestroyStack(SqStack * stack)
{free(stack->base);stack->top=stack->base=NULL;stack->stacksize=0;return TRUE;
}
/* 清理stack,只需要将top指针指向base*/
Status ClearStack(SqStack * stack)
{stack->top=stack->base;return TRUE;
}/* 判断栈是否为空 */
Status StackEmpty(SqStack stack)
{if(stack.base == stack.top)return TRUE;else return FALSE;
}/* 获取stack的长度 */
int StackLength(SqStack stack)
{return stack.top - stack.base;
}/* 获取栈顶元素，并将值传递给 e*/
Status GetTop(SqStack stack, SElemType * e)
{if(StackEmpty(stack))return FALSE;*e = *--stack.top;
}/*入栈, 将元素e压入栈中 */
Status Push(SqStack * stack,SElemType e)
{if(stack->top - stack->base >= stack->stacksize)//如果空间不够的话，扩容{stack->base =(SElemType *) realloc(stack->base,(stack->stacksize+STACKINCREMENT)* sizeof(SElemType));if(!stack->base)exit(EXIT_FAILURE);stack->stacksize += STACKINCREMENT;}*stack->top++ = e;return TRUE;
}
/*出栈， 从栈顶弹出元素，并将元素值传递给e*/
Status Pop(SqStack * stack ,SElemType * e)  
{if(!stack->base)return FALSE;if(stack->base == stack->top) //空栈return FALSE;*e = *(--stack->top);return TRUE;
}/* 访问元素 */
void Visit(SElemType e)
{printf("%d\t", e);
}/* 遍历stack,对stack的每一个元素调用visit函数 */
Status StackTraverse(SqStack stack,void (*visit)(SElemType e))
{SElemType * curElem=stack.base;if(StackEmpty(stack))return FALSE;while(curElem!=stack.top)visit(*curElem++);return TRUE;}int main()
{SqStack stack;SElemType  elem;InitStack(&stack);printf("压入数字1、2、3\n");Push(&stack,1);Push(&stack,2);Push(&stack,3);printf("当前栈的容量:%d\n",StackLength(stack));GetTop(stack,&elem);printf("栈顶元素为:%d\n",elem);printf("将4、5压入栈中\n");Push(&stack,4);Push(&stack,5);Pop(&stack,&elem);printf("弹出栈顶元素为:%d\n",elem);printf("当前栈的容量:%d\n",StackLength(stack));printf("遍历栈:");StackTraverse(stack,Visit);printf("\n");DestroyStack(&stack);getchar();return 0;
}

3.2 运行结果:

在这里插入图片描述

4. 简易版完整测试代码

简易版，无法动态的给栈扩容

4.1 完整代码

/*此版本为简易版本*/#include <stdio.h>
#include <stdlib.h>#define TRUE  1
#define FALSE 0
#define MAXSIZE 30typedef  int Status;typedef  int ElemType; //定义元素类型为整型
typedef struct{ElemType * base; //在栈构造之前和销毁之后，base的值均为NULLint top;
}SqStack;/*初始化栈，为栈分配空间*/
Status InitStack(SqStack * stack)
{stack->base=(ElemType*) malloc(sizeof(ElemType)*MAXSIZE);if(stack->base==NULL)return FALSE;stack->top= -1; //初始值可以是-1,也可以设置为0。//如果设置为-1，那么当栈不为空时， 栈顶元素为 stack->base[top]//如果设置为0， 那么当栈不为空时， 栈顶元素为 stack->base[top-1]return TRUE;
}/*销毁栈，释放栈的数据空间*/
void DestroyStack(SqStack *stack)
{free(stack->base);stack->base=NULL;stack->top= -1;
}/* 获取栈顶元素 */
Status GetTop(SqStack stack, ElemType * elem)
{if(stack.top<0)return FALSE;*elem=stack.base[stack.top];return TRUE;
}/* 压栈，将元素elem 插入栈顶 */
Status Push(SqStack * stack,ElemType elem)
{if(stack->top == MAXSIZE-1) /*栈已经满了，实际应用中，可以动态扩展栈的空间*/return FALSE;stack->base[++stack->top]=elem;return TRUE;
}/*出栈，将栈顶元素elem出栈，相当于删除栈顶元素 */
Status Pop(SqStack * stack,ElemType * elem)
{if(stack->top<0)return FALSE;*elem=stack->base[stack->top--];return TRUE;
}int main ()
{SqStack stack;ElemType * elem=(ElemType*)malloc(sizeof(ElemType));InitStack(&stack);printf("压入数字1、2、3\n");Push(&stack,1);Push(&stack,2);Push(&stack,3);printf("当前栈的容量:%d\n",stack.top+1);GetTop(stack,elem);printf("栈顶元素为:%d\n",*elem);printf("将4、5压入栈中\n");Push(&stack,4);Push(&stack,5);Pop(&stack,elem);printf("弹出栈顶元素为:%d\n",*elem);printf("当前栈的容量:%d\n",stack.top+1);printf("\n");DestroyStack(&stack);free(elem);getchar();return 0;
}

4.2 运行结果

在这里插入图片描述

5. 栈的应用 ：进制转化

5.1 转化函数

此函数是将10进制的数据 转化为2进制或者8进制 。

/* 十进制制转换成8进制或2进制* 参数radix  进制数，如果要转换成2进制，则输入2，如果转换成8进制，则radix=8* 参数n      待转换的十进制数 */
void conversion(int radix,int n)
{SqStack stack;int elem;InitStack(&stack);while(n){Push(&stack,n%radix);   // 将余数入栈n=n/radix;				// 商做为被除数，进行下一个循环（只要商不为0，就继续除下去)}while(!StackEmpty(stack)){  //从栈中，将余数依次取出。Pop(&stack ,&elem);printf("%d",elem);}printf("\n");
}

5.2 进制转化完整代码

#include <stdio.h>
#include <stdlib.h>#define STACK_INIT_SIZE 100  //初始内存空间
#define STACKINCREMENT  10   // 内存空间增量#define TRUE 1
#define FALSE 0typedef int Status;typedef int SElemType;typedef struct Stack{SElemType *base; //栈底指针SElemType * top; //栈顶指针int stacksize;   //当前已分配的存储空间
} SqStack;Status InitStack(SqStack * stack);
Status DestroyStack(SqStack * stack);
Status ClearStack(SqStack * stack);
Status StackEmpty(SqStack stack);
int StackLength(SqStack stack);
Status GetTop(SqStack stack, SElemType * e);
Status Push(SqStack * stack,SElemType e);
Status Pop(SqStack * stack, SElemType *e);
void Visit(SElemType e);
Status StackTraverse(SqStack stack,void (*visit)(SElemType));/*初始化栈*/
Status InitStack(SqStack * stack)
{stack->base =(SElemType * )malloc(STACK_INIT_SIZE* sizeof(SElemType));if(!stack->base)exit(EXIT_FAILURE);stack->top=stack->base;	// 栈顶指针初始 指向栈底;stack->stacksize=STACK_INIT_SIZE;return TRUE;
}/*销毁栈 */
Status DestroyStack(SqStack * stack)
{free(stack->base);stack->top=stack->base=NULL;stack->stacksize=0;return TRUE;
}
/* 清理stack,只需要将top指针指向base*/
Status ClearStack(SqStack * stack)
{stack->top=stack->base;return TRUE;
}/* 判断栈是否为空 */
Status StackEmpty(SqStack stack)
{if(stack.base == stack.top)return TRUE;else return FALSE;
}/* 获取stack的长度 */
int StackLength(SqStack stack)
{return stack.top - stack.base;
}/* 获取栈顶元素，并将值传递给 e*/
Status GetTop(SqStack stack, SElemType * e)
{if(StackEmpty(stack))return FALSE;*e = *--stack.top;
}/*入栈, 将元素e压入栈中 */
Status Push(SqStack * stack,SElemType e)
{if(stack->top - stack->base >= stack->stacksize)//如果空间不够的话，扩容{stack->base =(SElemType *) realloc(stack->base,(stack->stacksize+STACKINCREMENT)* sizeof(SElemType));if(!stack->base)exit(EXIT_FAILURE);stack->stacksize += STACKINCREMENT;}*stack->top++ = e;return TRUE;
}
/*出栈， 从栈顶弹出元素，并将元素值传递给e*/
Status Pop(SqStack * stack ,SElemType * e)  
{if(!stack->base)return FALSE;if(stack->base == stack->top) //空栈return FALSE;*e = *(--stack->top);return TRUE;
}/* 十进制制转换成8进制或2进制* 参数radix  进制数，如果要转换成2进制，则输入2，如果转换成8进制，则radix=8* 参数n      待转换的十进制数 */
void conversion(int radix,int n)
{SqStack stack;int elem;InitStack(&stack);while(n){Push(&stack,n%radix);   // 将余数入栈n=n/radix;				// 商做为被除数，进行下一个循环（只要商不为0，就继续除下去)}while(!StackEmpty(stack)){Pop(&stack ,&elem);printf("%d",elem);}printf("\n");}int main ()
{printf("将4转换为2进制：");conversion(2,4);printf("将20转换为8进制：");conversion(8,20);getchar();return 0;
}

5.3 运行结果

在这里插入图片描述

这篇关于【数据结构与算法（C 语言）】栈的基本操作函数（动图演示） 及 栈的实际应用之一：进制转换的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1022009。

相关文章

C语言中联合体union的使用

C语言中联合体union的使用

本文编辑整理自： http://bbs.chinaunix.net/forum.php?mod=viewthread&tid=179471 一、前言 “联合体”(union）与“结构体”(struct)有一些相似之处。但两者有本质上的不同。在结构体中,各成员有各自的内存空间, 一个结构变量的总长度是各成员长度之和。而在“联合”中,各成员共享一段内存空间, 一个联合变量
阅读更多...
LangChain转换链：让数据处理更精准

LangChain转换链：让数据处理更精准

1. 转换链的概念 在开发AI Agent（智能体）时，我们经常需要对输入数据进行预处理，这样可以更好地利用LLM。LangChain提供了一个强大的工具——转换链（TransformChain），它可以帮我们轻松实现这一任务。 转换链（TransformChain）主要是将 给定的数据 按照某个函数进行转换，再将 转换后的结果 输出给LLM。 所以转换链的核心是：根据业务逻辑编写合适的转换函
阅读更多...
大语言模型（LLMs）能够进行推理和规划吗？

大语言模型（LLMs）能够进行推理和规划吗？

大语言模型（LLMs），基本上是经过强化训练的 n-gram 模型，它们在网络规模的语言语料库（实际上，可以说是我们文明的知识库）上进行了训练，展现出了一种超乎预期的语言行为，引发了我们的广泛关注。从训练和操作的角度来看，LLMs 可以被认为是一种巨大的、非真实的记忆库，相当于为我们所有人提供了一个外部的系统 1（见图 1）。然而，它们表面上的多功能性让许多研究者好奇，这些模型是否也能在通常需要系
阅读更多...
【操作系统】信号Signal超详解|捕捉函数

【操作系统】信号Signal超详解|捕捉函数

🔥博客主页： 我要成为C++领域大神🎥系列专栏：【C++核心编程】 【计算机网络】 【Linux编程】 【操作系统】 ❤️感谢大家点赞👍收藏⭐评论✍️ 本博客致力于知识分享，与更多的人进行学习交流 ​ 如何触发信号 信号是Linux下的经典技术，一般操作系统利用信号杀死违规进程，典型进程干预手段，信号除了杀死进程外也可以挂起进程 kill -l 查看系统支持的信号
阅读更多...
亮相WOT全球技术创新大会，揭秘火山引擎边缘容器技术在泛CDN场景的应用与实践

亮相WOT全球技术创新大会，揭秘火山引擎边缘容器技术在泛CDN场景的应用与实践

2024年6月21日-22日，51CTO“WOT全球技术创新大会2024”在北京举办。火山引擎边缘计算架构师李志明受邀参与，以“边缘容器技术在泛CDN场景的应用和实践”为主题，与多位行业资深专家，共同探讨泛CDN行业技术架构以及云原生与边缘计算的发展和展望。 火山引擎边缘计算架构师李志明表示：为更好地解决传统泛CDN类业务运行中的问题，火山引擎边缘容器团队参考行业做法，结合实践经验，打造火山
阅读更多...
java中查看函数运行时间和cpu运行时间

java中查看函数运行时间和cpu运行时间

android开发调查性能问题中有一个现象，函数的运行时间远低于cpu执行时间，因为函数运行期间线程可能包含等待操作。native层可以查看实际的cpu执行时间和函数执行时间。在java中如何实现？ 借助AI得到了答案 import java.lang.management.ManagementFactory;import java.lang.management.Threa
阅读更多...
代码随想录算法训练营：12/60

代码随想录算法训练营：12/60

非科班学习算法day12 | LeetCode150:逆波兰表达式 ，Leetcode239: 滑动窗口最大值  目录 介绍 一、基础概念补充： 1.c++字符串转为数字 1. std::stoi, std::stol, std::stoll, std::stoul, std::stoull（最常用） 2. std::stringstream 3. std::atoi, std
阅读更多...
人工智能机器学习算法总结神经网络算法(前向及反向传播)

人工智能机器学习算法总结神经网络算法(前向及反向传播)

1.定义，意义和优缺点 定义: 神经网络算法是一种模仿人类大脑神经元之间连接方式的机器学习算法。通过多层神经元的组合和激活函数的非线性转换，神经网络能够学习数据的特征和模式，实现对复杂数据的建模和预测。(我们可以借助人类的神经元模型来更好的帮助我们理解该算法的本质，不过这里需要说明的是，虽然名字是神经网络，并且结构等等也是借鉴了神经网络，但其原型以及算法本质上还和生物层面的神经网络运行原理存在
阅读更多...
自制的浏览器主页，可以是最简单的桌面应用，可以把它当成备忘录桌面应用

自制的浏览器主页，可以是最简单的桌面应用，可以把它当成备忘录桌面应用

自制的浏览器主页，可以是最简单的桌面应用，可以把它当成备忘录桌面应用。如果你看不懂，请留言。 完整代码： <!DOCTYPE html><html lang="zh-CN"><head><meta charset="UTF-8"><meta name="viewport" content="width=device-width, initial-scale=1.0"><ti
阅读更多...
Python应用开发——30天学习Streamlit Python包进行APP的构建（9）

Python应用开发——30天学习Streamlit Python包进行APP的构建（9）

st.area_chart 显示区域图。 这是围绕 st.altair_chart 的语法糖。主要区别在于该命令使用数据自身的列和指数来计算图表的 Altair 规格。因此，在许多 "只需绘制此图 "的情况下，该命令更易于使用，但可定制性较差。 如果 st.area_chart 无法正确猜测数据规格，请尝试使用 st.altair_chart 指定所需的图表。 Function signa
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2