C语言深入刨析数据结构之栈与链栈的设计与应用

目录
  • 一.栈的定义
  • 二.栈的特点
  • 三.栈的理解
  • 四.链栈引入
  • 五.链栈定义
  • 六.链栈的结构体设计
  • 七.链栈的基本操作
    • 7.1链栈的初始化
    • 7.2链栈判空
    • 7.3链栈入栈
    • 7.4链栈出栈
    • 7.5取栈顶元素
  • 八.总结

一.栈的定义

栈是限定仅在表尾进行插入和删除操作的数据结构（受到限制的线性表）。

我们把允许插入和删除的一端称为栈顶，另一端称为栈底，不含任何元素为空栈。

二.栈的特点

后进先出

比如word，浏览器网页等一系列软件中，都有撤销的操作，就是利用栈的这种方式来实现的，可能不同软件的代码不同，但是他们的原理是一样的均为：后进先出。

三.栈的理解

  • 栈是一个线性表，有前驱后继关系，只不过这里的表尾指的是栈顶。
  • 栈限制了线性表的插入和删除位置，这也导致栈底是固定的。
  • 栈的插入操作，叫做进栈；可以理解为子弹入弹夹。
  • 栈的删除操作，叫做出栈；可以理解为子弹出弹夹。

四.链栈引入

既然栈是属于线性表的一种，那么存储结构也就分为顺序存储和链式存储，这里我们着重讲解链式存储结构。

五.链栈定义

栈的链式存储结构，简称链栈。

对于栈来说，只在栈顶做插入和删除操作，由于单链表有头指针，栈顶指针也是必须的，那我们干脆就将头指针和栈顶指针合二为一，将栈顶放在单链表的头部。通常对于链栈是不需要头结点的。

对于链栈来说，一般不会存在栈满的情况，如果这种事情真的发生，那么此时的计算机操作系统也将会面临死机崩溃的情况，那就不单单是这个链栈是否溢出的问题了。对于链表来说，链表为空的表示是头结点指向空，那么对于链栈来讲，链栈为空就是栈顶指针指向空（top = NULL）。

六.链栈的结构体设计

代码如下：

// 链栈的存储结构
typedef struct StackNode
{
    int data;
    struct StackNode *next;
}StackNode,*LinkStack;

七.链栈的基本操作

对于链栈来说作为线性表的一种，操作也就那么几种，这里我们对以下几种操作进行详解：初始化，判断是否为空，入栈，出栈，取栈顶元素等。

7.1链栈的初始化

链栈的初始化可以理解为构造一个空栈，将栈顶指针top所指头结点的指针域置为NULL，因为此时栈中还没有数据元素。

代码如下：

LinkedStack Init_LinkedStack()
{
	LinkedStack top = (LinkedStackNode *)malloc(sizeof(LinkedStackNode));
	                              //栈顶指针变量
	if(top != NULL)
	{
		top->next = NULL;
	}
	return top;
}

7.2链栈判空

判断链栈是否为空，只需要判断栈顶的指针域是否指向空，如果指向空则栈空，相反亦然。

bool LinkedStack_Empty(LinkedStack top)
{
	if(top->next == NULL)//如果栈顶的指针域指向空，则栈空
	{
		return True;
	}
	else
	{
		return False;
	}

7.3链栈入栈

入栈就是：

  • 先对数据域进行赋值；
  • 然后让新结点指向栈顶指针；
  • 最后将栈顶指针交给新节点。

假设元素值为e的新节点是s，top为栈顶指针：

代码如下：

int Push(LinkedStack *s  ,elemtype e)
{
	LinkedStackNode s= (LinkedStackNode )malloc(sizeof(LinkedStackNode));
 s->data=e;
 s->next=s->top;//把当前的栈顶元素赋值给新结点的直接后继.
 s->top=s;//把新节点s赋值给栈顶指针
 s->cout++;
 return 1;
}

7.4链栈出栈

出栈就是：

  • 将要删除的元素的值交给临时变量，将栈顶指针交给临时节点；
  • 将栈顶指针下移；最后释放临时节点（即完成删除）。
  • 假设变量p用来存储要删除的栈顶结点，将栈顶指针向下移一位，最后释放p即可：

代码如下：

int Pop_LinkedStack(LinkedStack *s,elemtype *e)
{
	LinkedStackNode *p;
	if(stackempty(*s))
		return error;
	*e=s->top->data;
	p=s->top;   //将栈顶结点赋值给p
	s->top=s->top->next;//使得栈顶结点指针下移一位，指向后一结点
	free(p);//释放结点
	s->count--;
	return 1;
	}
}

7.5取栈顶元素

读取栈顶元素，并返回其值，该操作与出栈的区别是栈顶元素并不删除，所以不用修改头结点的指针域即可。

int Get_LinkedStack(LinkedStack top,elemtype *x)
{
	if(top->next == NULL)
	{
		return 0;
	}
	else
	{
		*x = top->next->data;
		return 1;
	}
}

八.总结

对比顺序栈和链栈，如果栈的使用过程中元素变化不可预料，有时小，有时大，那么最好用链栈；反之，如果他的变化在可控范围之内建议使用顺序栈会更好点。

（小白一位，如有错误欢迎指正）

到此这篇关于C语言深入刨析数据结构之栈与链栈的设计与应用的文章就介绍到这了,更多相关C语言栈与链栈内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C语言数据结构之算法的时间复杂度

    C语言数据结构之算法的时间复杂度

    目录 1.算法的复杂度 2.时间复杂度 2.1 时间复杂度的定义 2.2 大O的渐进表示法 3.常见时间复杂度计算举例 3.1 冒泡排序的时间复杂度 3.2 二分查找的时间复杂度 3.3 阶乘(递归)的时间复杂度 3.4菲波那切数列的时间复杂度 1.算法的复杂度 算法在编写成可执行程序后,运行时需要耗费时间资源和空间(内存)资源 .因此衡量一个算法的好坏,一般是从时间和空间两个维度来衡量的,即时间复杂度和空间复杂度. 时间复杂度主要衡量一个算法的运行快慢,而空间复杂度主要衡量一个算法运行所需要的

  • C语言数据结构图的创建与遍历实验示例

    C语言数据结构图的创建与遍历实验示例

    目录 一. 实验目的 二. 实验内容 三. 实验工具 四. 实验代码 五. 实验结果 六.总结与思考 一. 实验目的 理解图的基本概念,掌握图的存储结构,实现图的深度优先搜索遍历算法与广度优先搜索遍历算法. 二. 实验内容 利用邻接矩阵描述示例图,编写程序输出示例图的深度优先搜索和广度优先搜索的遍历序列. 具体步骤如下: 将图的邻接矩阵描述为一个二维数组,并将该数组定义为全局变量,以便数据的传递: 定义一个队列,在广度优先搜索时,该队列存储已被访问的路径长度为1,2,…的顶点: 定义访问函数vi

  • C语言数据结构与算法之图的遍历

    C语言数据结构与算法之图的遍历

    目录 引入  深度优先搜索 代码实现  完整代码   引入  在数据结构中常见的有深度优先搜索和广度优先搜索.为什么叫深度和广度呢?其实是针对图的遍历而言的,请看下面这个图: 图是由一些小圆点(称为顶点) 和 连接这些点的直线 (称为边)组成的. 例如上图就是由5个顶点(编号为 1,2,3,4,5) 和5条边(1-2,1-3,1-4,2-4)组成. 现在我们从1号顶点开始遍历这个图,遍历就是把图的每一个顶点都访问一次.使用深度优先搜索将会得到如下的结果. 图中每个顶点旁边的数表示这个顶点是第几个

  • C语言算法积累图的遍历邻接表简单路径

    目录 题目: 思路: 代码: 题目: 假设图用邻接表表示,设计一个算法,输出从顶点Vi到Vj的所有简单路径 关键字: 图,邻接表,简单路径 思路: Vi=u,Vj=v 本题采用基于递归的深度优先遍历算法,从结点u出发,递归深度优先遍历图中各个结点,若访问到结点v,则输出该搜索路径上的结点. 为此,设置:一个path数组来存放路径上的结点(初始为空),d表示路径长度(初始为-1). 查找从顶点u到v 的简单路径过程说明如下 (假设查找函数名为FindPath()): 1)FindPath(G,u,

  • C语言数据结构详细解析二叉树的操作

    C语言数据结构详细解析二叉树的操作

    目录 二叉树分类 二叉树性质 性质的使用 二叉树的遍历 前序遍历 中序遍历 后序遍历 层序遍历 求二叉树的节点数 求二叉树叶子结点个数 求二叉树的最大深度 二叉树的销毁 二叉树分类 满二叉树 除最后一层无任何子节点外,每一层上的所有结点都有两个子结点的二叉树.也可以理解为每一层的结点数都达到最大值的二叉树. 完全二叉树 一棵深度为k的有n个结点的二叉树,对树中的结点按从上至下.从左到右的顺序进行编号,如果编号为i(1≤i≤n)的结点与满二叉树中编号为i的结点在二叉树中的位置相同,则这棵二叉树称为

  • C语言超详细讲解数据结构中的线性表

    C语言超详细讲解数据结构中的线性表

    目录 前言 一.分文件编写 1.分文件编写概念 2.代码展示 二.动态分布内存malloc 1.初识malloc 2.使用方法 三.创建链表并进行增删操作 1.初始化链表 2.在链表中增加数据 3.删除链表中指定位置数据 四.代码展示与运行效果 1.代码展示 2.运行效果 总结 前言 计算机专业都逃不了数据结构这门课,而这门课无疑比较难理解,所以结合我所学知识,我准备对顺序表做一个详细的解答,为了避免代码过长,采用分文件编写的形式,不仅可以让代码干净利落还能提高代码可读性,先解释部分代码的含义,

  • C语言数据结构与算法之图的遍历(二)

    C语言数据结构与算法之图的遍历(二)

    目录 前言  广度优先搜索过程 主要思想  代码实现   前言  在上一章的内容中我们使用了深度优先搜索来进行遍历,这一章我们选择使用广度优先搜索来完成这个图的遍历 --> 结果如下: 广度优先搜索过程 使用广度优先搜索来遍历这个图的过程如下. 首先以一个未被访问过的顶点作为起始顶点,比如以1号点作为起始顶点. 将1号点放到队列中,然后将与1号点相邻的未访问过的顶点 即 2,3,5号顶点依次放入队列中,如下图: 接下来将2号顶点相邻的未访问过的顶点4号放入到队列中.到此所有的顶点都访问过了,遍历

  • C语言深入刨析数据结构之栈与链栈的设计与应用

    C语言深入刨析数据结构之栈与链栈的设计与应用

    目录 一.栈的定义 二.栈的特点 三.栈的理解 四.链栈引入 五.链栈定义 六.链栈的结构体设计 七.链栈的基本操作 7.1链栈的初始化 7.2链栈判空 7.3链栈入栈 7.4链栈出栈 7.5取栈顶元素 八.总结 一.栈的定义 栈是限定仅在表尾进行插入和删除操作的数据结构(受到限制的线性表). 我们把允许插入和删除的一端称为栈顶,另一端称为栈底,不含任何元素为空栈. 二.栈的特点 后进先出 比如word,浏览器网页等一系列软件中,都有撤销的操作,就是利用栈的这种方式来实现的,可能不同软件的代码不

  • C#实现顺序栈和链栈的代码实例

    自己定义的栈的接口,完全是按照栈的常用方法以及命名方式实现: 注意以下类,接口都是在一个命名空间下 栈的接口:包括了常用的方法 namespace 栈 { interface IStackDS<T> { int Count { get; } int GetLength(); bool IsEmpty(); void Clear(); void Push(T item); T Pop(); T Peek(); } } 顺序栈的实现,参照顺序表实现 namespace 栈 { class SeqS

  • C#数据结构与算法揭秘五 栈和队列

    C#数据结构与算法揭秘五 栈和队列

    这节我们讨论了两种好玩的数据结构,栈和队列. 老样子,什么是栈, 所谓的栈是栈(Stack)是操作限定在表的尾端进行的线性表.表尾由于要进行插入.删除等操作,所以,它具有特殊的含义,把表尾称为栈顶(Top) ,另一端是固定的,叫栈底(Bottom) .当栈中没有数据元素时叫空栈(Empty Stack).这个类似于送饭的饭盒子,上层放的是红烧肉,中层放的水煮鱼,下层放的鸡腿.你要把这些菜取出来,这就引出来了栈的特点先进后出(First in last out).   具体叙述,加下图. 栈通常记

  • C语言实现链栈的步骤

    C语言实现链栈的步骤

    链栈图解 链栈的常规操作 /********************* 链栈的常规操作 ****************************/ LinkStack InitLinkStack(); // 初始化链栈 int StackEmpty(); // 判断链栈空 int StackLength(); // 求链栈长(链栈元素个数) int Push(); // 入栈 压栈 ElemType Pop(); // 出栈 弹栈 void DestroyStack(); // 销毁链栈 /**

  • Python数据结构与算法中的栈详解

    Python数据结构与算法中的栈详解

    目录 0.学习目标 1.栈的基本概念 1.1栈的基本概念 1.2栈抽象数据类型 1.3栈的应用场景 2.栈的实现 2.1顺序栈的实现 2.1.1栈的初始化 2.1.2求栈长 2.1.3判栈空 2.1.4判栈满 2.1.5入栈 2.1.6出栈 2.1.7求栈顶元素 2.2链栈的实现 2.2.1栈结点 2.2.2栈的初始化 2.2.3求栈长 2.2.4判栈空 2.2.5入栈 2.2.6出栈 2.3栈的不同实现对比 3.栈应用 3.1顺序栈的应用 3.2链栈的应用 3.3利用栈基本操作实现复杂算法 总

  • C语言数据结构经典10大排序算法刨析

    C语言数据结构经典10大排序算法刨析

    1.冒泡排序 // 冒泡排序 #include <stdlib.h> #include <stdio.h> // 采用两层循环实现的方法. // 参数arr是待排序数组的首地址,len是数组元素的个数. void bubblesort1(int *arr,unsigned int len) { if (len<2) return; // 数组小于2个元素不需要排序. int ii; // 排序的趟数的计数器. int jj; // 每趟排序的元素位置计数器. int itmp

  • C语言树与二叉树基础全刨析

    C语言树与二叉树基础全刨析

    目录 一.树的概念和结构 1.1 树的概念 1.2 树的结构 & 相关名词解释 1.3 树的表示 1.4 树的应用 二.二叉树的概念 & 存储结构(重要) 2.1 二叉树的概念 2.2 特殊的二叉树 2.3 二叉树的性质 2.4 二叉树的存储结构 一.树的概念和结构 1.1 树的概念 树是一种非线性的数据结构,它是由 n(n>=0)个有限结点组成一个具有层次关系的集合.把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的. 有一个特殊的结点,称为根结点,根节点没有前

  • C语言数据结构之使用链表模拟栈的实例

    C语言数据结构之使用链表模拟栈的实例

    C语言数据结构之使用链表模拟栈的实例 以下是"使用链表模拟栈"的简单示例: 1. 用C语言实现的版本 #include<stdio.h> #include<stdlib.h> typedef char datatype; typedef struct node{ datatype data; struct node *next; } stack; stack* m_stack = NULL; /* 创建链表,从表头插入新元素 */ void creat(void

  • C语言形参和实参传值和传址详解刨析

    C语言形参和实参传值和传址详解刨析

    目录 例题 分析 实参与形参 实际参数(实参): 形式参数(形参): 修改 分析 传值和传址 传值调用 传址调用 讲解知识点之前,我们先来做一道题! 例题 写一个函数可以交换两个整形变量的内容 例如: 交换前:20 30 交换后:30 20 题目让我们用函数的方式写 #include <stdio.h> void Swap1(int x, int y) { int z = 0; z = x; x = y; y = z; } int main() { int a = 0; int b = 0;

  • C语言循环结构深入刨析

    C语言循环结构深入刨析

    目录 总述 while循环 语法结构 while循环中break和continue break continue for循环 语法结构 for循环中break和continue break continue for循环中省略表达式的问题 for循环嵌套 do-while循环 goto语句 总结 总述 生活中不止处处是选择,还时常面临着重复做某事,比如呢,我们日复一日的学习.敲代码. C语言中提供了 —while循环—for循环—do-while循环来表达循环 接下来,对三种循环进行分别介绍 wh

随机推荐