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 個結點的完全二叉樹深度為 $?{\log }_{2}n?+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 的有序樹。
  • 遍歷方式：
    • 前序：根左右
    • 中序：左根右
    • 后序：左右根
    • 層序：廣度優先

---