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

蔚落 2024-04-01 13:46 20阅读 0赞

**目录**

前言

表达式

堆栈 （Stack）

栈的顺序存储

栈的链式存储

CreateStack操作

Push操作

pop操作

堆栈应用：表达式求值

步骤

堆栈的其他应用

--------------------

## 前言 ##

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

## ![7483b858394d491790fc49adc795e7a3.jpeg][] ##

## 表达式 ##

**中缀表达式：运算符号位于两个运算符之间。**如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)）![c27ee346b99b4e9dac0311e22a974cf5.jpeg][]

## 堆栈 （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)          //删除并返回栈顶元素

### 栈的顺序存储 ###

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

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

### 栈的链式存储 ###

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

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

#### 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);
    }

#### 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;
    }

#### 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;
    }

#### 堆栈应用：表达式求值 ####

中缀表达式求值

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

转换后的特点：

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

![254ddfa24e2247b7a3a94ffd13d34235.png][]

#### 步骤 ####

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

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

## 堆栈的其他应用 ##

**函数调用及递归实现**

**深度优先搜索**

**回溯算法······**

[7483b858394d491790fc49adc795e7a3.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/e91e9b978ef04b12994b0b4413799645.jpeg
[c27ee346b99b4e9dac0311e22a974cf5.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/092635ac95e84e42be1bf6c1fd8d5eca.jpeg
[254ddfa24e2247b7a3a94ffd13d34235.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/cd0e0b6b546f4b9ab99ee312f06ce5b9.png