Day25 栈 队列 二叉树

day25 栈 队列 二叉树

---

使用栈计算表达式的值

概述

通过两个栈（数值栈和符号栈）实现中缀表达式求值。算法核心是：

• 遇到数字时，累加并入数值栈；
• 遇到运算符时，比较其与符号栈顶运算符的优先级：
  • 若当前运算符优先级更高，则直接入栈；
  • 否则，不断弹出符号栈顶运算符与两个数值进行计算，结果重新压入数值栈，直到满足入栈条件。
• 表达式结束后，处理剩余符号栈中的运算符。

目标表达式示例：20*3+5，预期结果为 65。

---

栈结构定义（链式栈）

#ifndef _LINKSTACK_H_
#define _LINKSTACK_H_// 定义栈中存储的数据类型，可存放数字或字符（运算符）
typedef struct 
{int num;     // 用于存储操作数char sym;    // 用于存储运算符
} DATATYPE;// 链栈节点结构
typedef struct _linkstacknode
{DATATYPE data;                    // 当前节点数据struct _linkstacknode *next;      // 指向下一个节点
} LinkStackNode;// 链栈整体结构
typedef struct 
{LinkStackNode* top;   // 栈顶指针int clen;             // 当前栈中元素个数
} LinkStack;// 函数声明
LinkStack* CreateLinkStack();                    // 创建空栈
int PushLinkStack(LinkStack* ls, DATATYPE* data); // 元素入栈
int PopLinkStack(LinkStack* ls);                 // 栈顶元素出栈
DATATYPE* GetTopLinkStack(LinkStack* ls);        // 获取栈顶元素（不弹出）
int IsEmptyLinkStack(LinkStack* ls);             // 判断栈是否为空
int GetSizeLinkStack(LinkStack* ls);             // 获取栈中元素个数
int DestroyLinkStack(LinkStack*);                // 销毁整个栈（释放内存）#endif // !_LINKSTACK_H_

说明：该头文件定义了一个通用链式栈，支持存储整数和字符类型数据，适用于数值栈和符号栈。

---

链栈实现（LinkStack.c）

#include "LinkStack.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>/*** 创建一个新的链栈* @return 成功返回栈指针，失败返回 NULL*/
LinkStack* CreateLinkStack()
{LinkStack* ls = malloc(sizeof(LinkStack));  // 分配栈控制块内存if (NULL == ls){perror("CreateLinkStack malloc error\n");return NULL;}ls->top = NULL;   // 初始化栈顶为空ls->clen = 0;     // 初始元素个数为 0return ls;
}/*** 元素入栈（头插法）* @param ls 待操作的栈* @param data 要入栈的数据（指针）* @return 0 成功，非 0 失败*/
int PushLinkStack(LinkStack* ls, DATATYPE* data)
{LinkStackNode* newnode = malloc(sizeof(LinkStackNode));if (NULL == newnode){perror("PushLinkStack malloc error\n");return 1;}memcpy(&newnode->data, data, sizeof(DATATYPE));  // 复制数据newnode->next = ls->top;                         // 新节点指向原栈顶ls->top = newnode;                               // 更新栈顶ls->clen++;                                      // 元素个数加一return 0;
}/*** 出栈操作（头删法）* @param ls 待操作的栈* @return 0 成功，非 0 失败（栈空）*/
int PopLinkStack(LinkStack* ls)
{if (IsEmptyLinkStack(ls)){printf("linkstack is empty\n");return 1;}LinkStackNode* tmp = ls->top;         // 临时保存栈顶节点ls->top = ls->top->next;              // 栈顶下移free(tmp);                            // 释放原栈顶节点ls->clen--;                           // 元素个数减一return 0;
}/*** 获取栈顶元素（不弹出）* @param ls 待操作的栈* @return 指向栈顶数据的指针，栈空时返回 NULL*/
DATATYPE* GetTopLinkStack(LinkStack* ls)
{if (IsEmptyLinkStack(ls)){return NULL;}return &ls->top->data;  // 返回栈顶数据地址
}/*** 判断栈是否为空* @param ls 待检查的栈* @return 1 表示空，0 表示非空*/
int IsEmptyLinkStack(LinkStack* ls)
{return 0 == ls->clen;
}/*** 获取栈中元素个数* @param ls 待查询的栈* @return 元素个数*/
int GetSizeLinkStack(LinkStack* ls)
{return ls->clen;
}/*** 销毁整个链栈（释放所有节点及控制块）* @param ls 要销毁的栈* @return 0（固定返回值）*/
int DestroyLinkStack(LinkStack* ls)
{while (!IsEmptyLinkStack(ls)){PopLinkStack(ls);  // 循环出栈，自动释放节点}free(ls);  // 释放栈控制块return 0;
}

---

表达式求值主程序（main.c）

#include <stdio.h>
#include <string.h>
#include "LinkStack.h"int num = 0;  // 用于临时存储正在解析的数字/*** 将字符数字累加到全局变量 num 中* @param c 当前字符（'0'-'9'）*/
void get_num(char c)
{num = num * 10 + c - '0';  // 构造多位整数
}/*** 获取运算符优先级* @param c 运算符字符* @return 优先级：+,- 为 1；*,/ 为 2；其他为 0*/
int get_priority(char c)
{switch (c){case '+':case '-':return 1;case '*':case '/':return 2;default:return 0;}
}/*** 执行两个数之间的基本运算* @param num1 第一个操作数* @param num2 第二个操作数* @param c 运算符* @return 计算结果*/
int get_result(int num1, int num2, char c)
{switch (c){case '+':return num1 + num2;case '-':return num1 - num2;case '*':return num1 * num2;case '/':return num1 / num2;}return 0;  // 默认返回值（理论上不会执行）
}/*** 主函数：计算中缀表达式 "20*3+5"*/
int main(int argc, char** argv)
{char* express = "20*3+5";                    // 输入表达式LinkStack* ls_num = CreateLinkStack();       // 数值栈LinkStack* ls_sym = CreateLinkStack();       // 符号栈char* tmp = express;                         // 遍历指针DATATYPE* top;                               // 临时指针DATATYPE data;                               // 临时数据变量while (*tmp){bzero(&data, sizeof(data));  // 清空临时数据// 处理数字字符if (*tmp >= '0' && *tmp <= '9'){get_num(*tmp);tmp++;continue;}// 遇到运算符前，将已解析的数字压入数值栈data.num = num;num = 0;PushLinkStack(ls_num, &data);// 处理当前运算符，与符号栈顶比较优先级while (1){top = GetTopLinkStack(ls_sym);// 条件1：符号栈为空，直接入栈// 条件2：当前运算符优先级高于栈顶，直接入栈if (IsEmptyLinkStack(ls_sym) ||(top != NULL && get_priority(top->sym) < get_priority(*tmp))){bzero(&data, sizeof(data));data.sym = *tmp;PushLinkStack(ls_sym, &data);break;}else{// 否则：弹出两个数值和一个运算符进行计算top = GetTopLinkStack(ls_num);int num2 = top->num;PopLinkStack(ls_num);top = GetTopLinkStack(ls_num);int num1 = top->num;PopLinkStack(ls_num);top = GetTopLinkStack(ls_sym);char op = top->sym;PopLinkStack(ls_sym);int result = get_result(num1, num2, op);bzero(&data, sizeof(data));data.num = result;PushLinkStack(ls_num, &data);  // 结果压回数值栈}}tmp++;}// 处理最后一个数字（循环外）data.num = num;num = 0;PushLinkStack(ls_num, &data);// 处理剩余符号栈中的运算符（从左到右）while (!IsEmptyLinkStack(ls_sym)){top = GetTopLinkStack(ls_num);int num2 = top->num;PopLinkStack(ls_num);top = GetTopLinkStack(ls_num);int num1 = top->num;PopLinkStack(ls_num);top = GetTopLinkStack(ls_sym);char op = top->sym;PopLinkStack(ls_sym);int result = get_result(num1, num2, op);bzero(&data, sizeof(data));data.num = result;PushLinkStack(ls_num, &data);}// 最终结果在数值栈顶top = GetTopLinkStack(ls_num);int result = top->num;PopLinkStack(ls_num);printf("result %d\n", result);  // 输出结果// 释放资源DestroyLinkStack(ls_num);DestroyLinkStack(ls_sym);return 0;
}

理想运行结果：

result 65

说明：表达式 20*3+5 按照优先级先算乘法 20*3=60，再加 5，最终得 65。

---

队列

概念与特性

• 定义：只允许在一端（队尾）插入，另一端（队头）删除的线性表。
• 核心特性：先进先出（FIFO）。
• 应用场景：缓冲区（解决生产者与消费者速度不匹配问题）。
• 主要类型：
  • 顺序队列
  • 循环队列（避免假溢出）

常用操作

• 入队（EnterSeqQue）：队尾插入
• 出队（QuitSeqQue）：队头删除
• 获取队头元素（GetHeadSeqQue）
• 判空（IsEmptySeqQue）、判满（IsFullSeqQue）

---

循环队列结构定义（seqque.h）

#ifndef __SEQQUE__H__
#define __SEQQUE__H__typedef int DATATYPE;  // 数据类型别名/*** 循环队列结构体* array: 存储数据的数组* head:  队头索引（指向第一个元素）* tail:  队尾“下一个空位”索引* tlen:  数组总长度*/
typedef struct
{DATATYPE* array;int head;int tail;int tlen;
} SeqQue;// 函数声明
SeqQue* CreateSeqQue(int len);               // 创建队列
int EnterSeqQue(SeqQue* sq, DATATYPE* data); // 入队
int QuitSeqQue(SeqQue* sq);                  // 出队
DATATYPE* GetHeadSeqQue(SeqQue* sq);         // 获取队头元素
int IsEmptySeqQue(SeqQue* sq);               // 判断空
int IsFullSeqQue(SeqQue* sq);                // 判断满
int DestroySeqQue(SeqQue* sq);               // 销毁队列#endif  // !__SEQQUE__H__

---

循环队列实现（seqque.c）

#include "seqque.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>/*** 创建长度为 len 的循环队列* @param len 队列容量（实际可存 len-1 个元素）* @return 成功返回队列指针，失败返回 NULL*/
SeqQue* CreateSeqQue(int len)
{SeqQue* sq = malloc(sizeof(SeqQue));if (NULL == sq){perror("CreateSeqQue malloc");return NULL;}sq->array = malloc(sizeof(DATATYPE) * len);if (NULL == sq->array){perror("CreateSeqQue malloc2");free(sq);return NULL;}sq->head = 0;sq->tail = 0;sq->tlen = len;return sq;
}/*** 元素入队（队尾）* @param sq 队列* @param data 要插入的数据* @return 0 成功，1 失败（队满）*/
int EnterSeqQue(SeqQue* sq, DATATYPE* data)
{if (IsFullSeqQue(sq)){printf("queue is full\n");return 1;}memcpy(&sq->array[sq->tail], data, sizeof(DATATYPE));sq->tail = (sq->tail + 1) % sq->tlen;  // 循环移动return 0;
}/*** 元素出队（队头）* @param sq 队列* @return 0 成功，1 失败（队空）*/
int QuitSeqQue(SeqQue* sq)
{if (IsEmptySeqQue(sq)){printf("queue is empty\n");return 1;}sq->head = (sq->head + 1) % sq->tlen;  // 循环移动return 0;
}/*** 获取队头元素地址（不删除）* @param sq 队列* @return 指向队头元素的指针*/
DATATYPE* GetHeadSeqQue(SeqQue* sq)
{return &sq->array[sq->head];
}/*** 判断队列是否为空* @param sq 队列* @return 1 为空，0 非空*/
int IsEmptySeqQue(SeqQue* sq)
{return sq->head == sq->tail;
}/*** 判断队列是否为满* @param sq 队列* @return 1 为满，0 非满*/
int IsFullSeqQue(SeqQue* sq)
{return (sq->tail + 1) % sq->tlen == sq->head;
}/*** 销毁队列（释放内存）* @param sq 队列* @return 0*/
int DestroySeqQue(SeqQue* sq)
{free(sq->array);free(sq);return 0;
}

---

队列测试程序（main.c）

#include <stdio.h>
#include "seqque.h"int main(int argc, char** argv)
{SeqQue* sq = CreateSeqQue(10);  // 创建容量为 10 的队列（最多存 9 个）int i = 0;for (i = 0; i < 10; i++){EnterSeqQue(sq, &i);  // 0~9 依次入队}// 第10次入队会失败，打印 "queue is full"i = 0;while (!IsEmptySeqQue(sq)){DATATYPE* tmp = GetHeadSeqQue(sq);printf("%d %d\n", i++, *tmp);  // 打印序号和值QuitSeqQue(sq);                // 出队}// 实际输出 0~8，共 9 个数（因队列满，最后一个未入）DestroySeqQue(sq);return 0;
}

理想运行结果：

0 0
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8

说明：循环队列容量为 10，但最多只能存 9 个元素（tail+1 == head 判满），因此 i=9 时入队失败。

---

树与二叉树核心要点总结

一、树的基本概念

• 定义：由 n（n ≥ 0）个结点组成的有限集合。n = 0 时为空树。
• 根结点：有且仅有一个根结点（无前驱）。
• 子树：n > 1 时，其余结点可划分为 m 个互不相交的子树，每棵子树也是树。
• 结点度数：
  • 度：结点拥有的子树个数。
  • 叶结点（终端结点）：度为 0。
  • 分支结点（非终端结点）：度不为 0。
• 树的度：树中所有结点的最大度数。
• 深度/高度：从根开始定义，根为第 1 层，逐层递增。
• 存储结构：顺序存储、链式存储。

二、二叉树的基本概念

• 定义：n 个结点的有限集合，为空树或由根结点 + 左子树 + 右子树（互不相交）组成。
• 特点：
  • 每个结点最多有两个子树。
  • 左右子树有序，不可颠倒。
  • 单子树必须明确是左或右。

三、特殊二叉树

• 斜树：
  • 左斜树：所有结点仅有左子树。
  • 右斜树：所有结点仅有右子树。
• 满二叉树：所有分支结点都有左右子树，且所有叶子在同一层。
• 完全二叉树：按层序编号后，与同深度满二叉树对应位置完全一致。

四、二叉树重要性质

1. 第 i 层最多有 $2^{i-1}$ 个结点（i ≥ 1）。
2. 深度为 k 的二叉树最多有 $2^k-1$ 个结点（k ≥ 1）。
3. 任意二叉树中，叶子结点数 $n_0=n_2+1$（$n_2$ 为度为 2 的结点数）。
4. n 个结点的完全二叉树深度为 $\lfloor {\log }_{2}n\rfloor +1$。

五、二叉树遍历方式

• 前序遍历：根 → 左 → 右
• 中序遍历：左 → 根 → 右
• 后序遍历：左 → 右 → 根
• 层序遍历：按层次从上到下、从左到右（广度优先）

---

二叉树构建与遍历代码实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>typedef char DATATYPE;  // 数据类型为字符// 二叉树结点结构
typedef struct _treenode
{DATATYPE data;                    // 存储数据struct _treenode* left;           // 左孩子指针struct _treenode* right;          // 右孩子指针
} Treenode;// 先序扩展序列（# 表示空节点），用于重建树
char data[] = "abd##eh###cf#i##g##";
int idx = 0;  // 全局索引，用于遍历 data 数组/*** 根据扩展先序序列构建二叉树* @param root 当前子树根节点的双重指针*/
void CreateTree(Treenode** root)
{char c = data[idx++];  // 读取当前字符if ('#' == c){*root = NULL;  // 空节点}else{*root = malloc(sizeof(Treenode));if (NULL == *root){perror("CreateTree malloc error\n");return;}(*root)->data = c;                   // 填充数据CreateTree(&(*root)->left);          // 递归构建左子树CreateTree(&(*root)->right);         // 递归构建右子树}
}/*** 前序遍历：根 → 左 → 右*/
void PreOrrderTravel(Treenode* root)
{if (NULL == root) return;printf("%c", root->data);PreOrrderTravel(root->left);PreOrrderTravel(root->right);
}/*** 中序遍历：左 → 根 → 右*/
void MidOrrderTravel(Treenode* root)
{if (NULL == root) return;MidOrrderTravel(root->left);printf("%c", root->data);MidOrrderTravel(root->right);
}/*** 后序遍历：左 → 右 → 根*/
void PosOrderTravel(Treenode* root)
{if (NULL == root) return;PosOrderTravel(root->left);PosOrderTravel(root->right);printf("%c", root->data);
}/*** 销毁二叉树（后序释放）*/
void DestroyTree(Treenode* root)
{if (NULL == root) return;DestroyTree(root->left);DestroyTree(root->right);free(root);
}

理想运行结果（调用三种遍历）：

• PreOrrderTravel: abdehcfgi
• MidOrrderTravel: dbehafcig
• PosOrderTravel: dhebfigca

---

赫夫曼树与赫夫曼编码

赫夫曼算法构造步骤

1. 给定 n 个权值 {w1,w2,...,wn}\{w_1, w_2, ..., w_n\}{w1​,w2​,...,wn​}，构造 n 棵仅含一个根结点的二叉树，形成集合 $F$。
2. 从 F 中选出两棵根结点权值最小的树作为左右子树，构造新二叉树，新根权值为两子树根权值之和。
3. 将这两棵树从 F 中删除，新树加入 F。
4. 重复 2~3，直到 F 中只剩一棵树，即为赫夫曼树。

赫夫曼编码规则

• 以字符集 {d1,d2,...,dn}\{d_1, d_2, ..., d_n\}{d1​,d2​,...,dn​} 为叶子结点，频率 {w1,w2,...,wn}\{w_1, w_2, ..., w_n\}{w1​,w2​,...,wn​} 为权值构造赫夫曼树。
• 规定：左分支为 0，右分支为 1。
• 从根到叶子的路径上 0/1 序列即为该字符的赫夫曼编码（前缀编码，无歧义）。

特点：带权路径长度最短，实现最优编码。

---

回顾总结

• 队列：受限线性表，一端插入（队尾），一端删除（队头），遵循 FIFO 原则；常用于缓冲。
  • 循环队列判空：head == tail
  • 判满：(tail + 1) % len == head
• 树：n 个结点的有限集合，有唯一根，其余为子树；包含根、叶、分支结点。
• 二叉树：度不超过 2 的有序树。
  • 遍历方式：
    • 前序：根左右
    • 中序：左根右
    • 后序：左右根
    • 层序：广度优先

---