C语言数据结构 | 堆栈顺序、链式存储及表达式求值

简介: 从计算机对表达式求值引入算数表达式在求值时若无优先级,那么从左到右运算就很容易,但算术表达式由两类对象构成一个是一个是+-*/······不同的运算符号优先级也不一样此时运算就比较困难 ,无法判断运算符后一个运算数是否参与这次运算。

目录

前言

表达式

堆栈 (Stack)

栈的顺序存储

栈的链式存储

CreateStack操作

Push操作

pop操作

堆栈应用:表达式求值

步骤

堆栈的其他应用


前言

从计算机对表达式求值引入

算数表达式在求值时若无优先级,那么从左到右运算就很容易,但算术表达式由两类对象构成

一个是运算数:1、2、3、······

一个是运算符号:+-*/······

不同的运算符号优先级也不一样

此时运算就比较困难 ,无法判断运算符后一个运算数是否参与这次运算

image.gif编辑

表达式

中缀表达式:运算符号位于两个运算符之间。如a+b*c-d/e

后缀表达式:运算符号位于两个运算数之后。如abc*+de/-

后缀表达式求值,以下面的式子为例

8 4 / 2 - 4 2 * + = ?

在运算中只需从左往右计算即可

首先出现8 而后4 后面出现 /,即表示8/4=2;紧接着出现了2和-,那么目前出现的数值就是2 2 -=0;此时042*=08,然后最后的+代表0和8相加0+8=8

堆栈:先放进去的后拿出来,后放进去的后拿出来(后入先出 Last In First Out (LIFO))image.gif编辑

堆栈 (Stack)

具有一定操作约束的线性表

只在一端(栈顶,Top)做插入、删除

插入数据:入栈(Push)

删除数据:出栈(Pop)

类型名称:堆栈(Stack)

数据对象集:一个有0个或多个元素的有穷线性表

操作集:长度为MaxSize的堆栈S∈Stack,堆栈元素item ∈ ElementType

Stack CreateStack(int MaxSize)    //生成空堆栈,最大长度为MaxSize
int IsFull(Stack S,int MaxSize)        //判断堆栈S是否已满
void Push(Stack S,ElementType item)    //将元素item压入堆栈
int IsEmpty(Stack S)              //判断堆栈S是否为空
ElementType Pop(Stack S)          //删除并返回栈顶元素

image.gif

栈的顺序存储

栈的顺序存储结构通常由一个一维数组和一个记录栈顶元素位置的变量组成。

#defube NaxSuze //存储数据元素的最大个数
typedef struct SNode *Stack;
struct SNode{
        ElementType Data[MaxSize];
        int Top;
};

image.gif

栈的链式存储

栈的链式存储结构实际上就是一个单链表,叫做链栈。插入和删除操作只能在链栈的栈顶进行

typedef struct SNode *Stack;
struct SNode{
        ElementType Data;
        struct SNode *Next;
};

image.gif

CreateStack操作

Stack CreateStack()
{        /*构建一个堆栈的头节点,返回指针*/
    Stack S;
    S = (Stack)malloc(sizeof(struct SNode));
    S->Next = NULL;
    return S;
}
int IsEmpty(Stack S)
{                /*判断堆栈s是否为空,若为空返回1,否则返回0*/
    return(S->Next == NULL);
}

image.gif

Push操作

void Push(ElementType item, Stack S)
{        /*将元素item压入堆栈s*/
    struct SNode *TmpCell;
    TmpCell=(struct SNode *)malloc(sizeof(struct SNode));
    TmpCell->Element = item;
    TmpCell->Next = S->Next;
    S->Next = TmpCell;
}

image.gif

pop操作

ElementType Pop(stack S)
{        /*删除并返回堆栈S的栈顶元素*/
    struct SNode *FirstCell;
    ElementType TopElem;
    if(IsEmpty(S)){
        printf("堆栈空");
        return NULL;
}else{
    FirstCell = S->Next;
    S->Next = FirstCell->Next;
    TopElem = FirstCell ->Element;
    free(FirstCell);
    return TopElem;
}

image.gif

堆栈应用:表达式求值

中缀表达式求值

基本策略:将中缀表达式转换为后缀表达式求值

转换后的特点:

    1. 运算数相对顺序不变
    2. 运算符号顺序发生改变
      1. 需要存储“等待中”的运算符号
      2. 要将当前运算符号与“等待中”的最后一个运算符号比较

        image.gif编辑

        步骤

        从头到尾读取中缀表达式的每个对象,对不同对象按不同情况处理。

          • 运算数:直接输出
          • 左括号:压入堆栈
          • 右括号:将栈顶的运算符弹出并输出,直到遇到左括号(出栈,不输出);
          • 运算符:
            • 若优先级大于栈顶运算符时,则把它压栈;
            • 若优先级小于等于栈顶运算符时,将栈顶运算符弹出并输出;再比较新的栈顶运算符,直到该运算符大于栈顶运算符优先级为止,然后将该运算符压栈
              • 若各对象处理完毕,则把堆栈中存留的运算符一并输出

              堆栈的其他应用

              函数调用及递归实现

              深度优先搜索

              回溯算法······

              相关文章
              |
              算法 数据可视化 数据建模
              【趣学C语言和数据结构100例】76-80
              本文介绍了五种图论算法的C语言实现,涵盖二叉树的层次遍历及广度优先搜索(BFS)和深度优先搜索(DFS)的邻接表与邻接矩阵实现。层次遍历使用队列按层访问二叉树节点;BFS利用队列从源节点逐层遍历图节点,适用于最短路径等问题;DFS通过递归或栈深入图的分支,适合拓扑排序等场景。这些算法是数据结构和算法学习的基础,对提升编程能力和解决实际问题至关重要。
              547 126
              |
              存储 算法 搜索推荐
              【趣学C语言和数据结构100例】91-95
              本文涵盖多个经典算法问题的C语言实现,包括堆排序、归并排序、从长整型变量中提取偶数位数、工人信息排序及无向图是否为树的判断。通过这些问题,读者可以深入了解排序算法、数据处理方法和图论基础知识,提升编程能力和算法理解。
              376 4
              |
              存储 机器学习/深度学习 搜索推荐
              【趣学C语言和数据结构100例】86-90
              本文介绍并用C语言实现了五种经典排序算法:直接插入排序、折半插入排序、冒泡排序、快速排序和简单选择排序。每种算法都有其特点和适用场景,如直接插入排序适合小规模或基本有序的数据,快速排序则适用于大规模数据集,具有较高的效率。通过学习这些算法,读者可以加深对数据结构和算法设计的理解,提升解决实际问题的能力。
              390 4
              |
              存储 算法 数据处理
              【趣学C语言和数据结构100例】81-85
              本文介绍了五个经典算法问题及其C语言实现,涵盖图论与树结构的基础知识。包括使用BFS求解单源最短路径、统计有向图中入度或出度为0的点数、统计无向无权图各顶点的度、折半查找及二叉排序树的查找。这些算法不仅理论意义重大,且在实际应用中极为广泛,有助于提升编程能力和数据结构理解。
              324 4
              |
              存储 算法 vr&ar
              【趣学C语言和数据结构100例】71-75
              本文介绍了五个C语言数据结构问题及其实现,涵盖链表与二叉树操作,包括按奇偶分解链表、交换二叉树左右子树、查找节点的双亲节点、计算二叉树深度及求最大关键值。通过递归和遍历等方法,解决了理论与实际应用中的常见问题,有助于提升编程能力和数据结构理解。
              448 4
              |
              算法 数据处理 C语言
              C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合
              本文深入解析了C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合,旨在帮助读者掌握这一高效的数据处理方法。
              984 1
              |
              定位技术 C语言
              c语言及数据结构实现简单贪吃蛇小游戏
              c语言及数据结构实现简单贪吃蛇小游戏
              |
              搜索推荐 C语言
              数据结构(C语言)之对归并排序的介绍与理解
              归并排序是一种基于分治策略的排序算法,通过递归将数组不断分割为子数组,直到每个子数组仅剩一个元素,再逐步合并这些有序的子数组以得到最终的有序数组。递归版本中,每次分割区间为[left, mid]和[mid+1, right],确保每两个区间内数据有序后进行合并。非递归版本则通过逐步增加gap值(初始为1),先对单个元素排序,再逐步扩大到更大的区间进行合并,直至整个数组有序。归并排序的时间复杂度为O(n*logn),空间复杂度为O(n),且具有稳定性,适用于普通排序及大文件排序场景。
              |
              存储 缓存 算法
              在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
              在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
              719 5
              |
              并行计算 算法 测试技术
              C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
              C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
              874 1

              热门文章

              最新文章