C 語言範例學習（三）：棧、隊列、字符串與廣義表

一、棧與隊列

兩者均為線性結構，區別在於出入策略：

• 棧：後進先出（LIFO），如單口水管，最靠近出口者先出。
• 隊列：先進先出（FIFO），如單向車道，先入者先出。

實例 90：棧實現進制轉換

邏輯：不斷取余、求商，入棧；出棧輸出即得結果。
關鍵操作：初始化、判空/判滿、入棧（先壓後加）、出棧（先減後彈）、取棧頂。代碼採用「向上增長」的順序棧。

void conversion(int N, int B) {
    SeqStack S; Initial(&S);
    while (N) { Push(&S, N % B); N /= B; }
    while (!IsEmpty(&S)) { printf("%d", Pop(&S)); }
}

反思：掌握六個核心函數即可靈活應用棧。

實例 95：鏈隊列菜單驅動程序

結構：節點 quenode 存數據與 next；隊列頭 quefr 存 front/rear 指針。
操作：創建（帶頭節點）、入隊（尾插）、出隊（頭刪）、顯示（遍歷）。主函數實現菜單交互。

void enqueue(struct quefr *q, int x) {
    quenode *s = malloc(sizeof(quenode));
    s->data = x; s->next = NULL;
    q->rear->next = s; q->rear = s;
}
ElemType dequeue(struct quefr *q) {
    if (q->front == q->rear) return 0;
    quenode *p = q->front->next;
    q->front->next = p->next;
    if (!p->next) q->rear = q->front;  // 最後一個元素
    ElemType x = p->data; free(p); return x;
}

實例 96：循環緩衝區（循環隊列）

解決順序隊列「假溢出」問題，首尾相連形成邏輯環。代碼結構與鏈隊列相似，此處略過。

二、串與廣義表

非數值處理核心為字符串。串的存儲：靜態數組、動態鏈表/堆。本節採用塊鏈結構：每節點存固定長度（如 50）字符，節省空間。

實例 98：簡易文本編輯器

功能：指定行輸入、刪除指定行、顯示所有內容。
數據結構：strnode（數據域 50 字符 + next）、headnode（行號、長度、首節點指針），共 100 行 Head[MAX]。
關鍵邏輯：

• 輸入：超過 50 字符自動分配新節點，j % 50 定位數組下標。
• 刪除：遍歷釋放該行所有節點，重置 length/number。
• 顯示：雙層循環，m 追蹤塊編號，j % 50 取字符。

void input() {
    while (1) {
        scanf("%d", &LineNum); if (LineNum < 0 || LineNum >= MAX) return;
        Head[LineNum].next = malloc(sizeof(strnode));
        p = Head[LineNum].next;
        while ((ch = getchar()) != '#') {
            if (j++ >= 50) { p->next = malloc(sizeof(strnode)); p = p->next; }
            p->data[j % 50] = ch;
        }
        Head[LineNum].length = j + 1;
    }
}

反思：塊鏈結構思想可廣泛應用於大對象分塊存儲場景。

實例 99/100：廣義表存儲與操作

廣義表為非線性列表，元素可以是原子或子表。廣泛用於 AI 領域（如 Lisp）。

節點結構：tag 標識類型（0=原子，1=子表），union 存 data 或 sublist 指針，next 指向同層後繼。

typedef struct lnode {
    int tag;
    union { ElemType data; struct lnode *sublist; } val;
    struct lnode *next;
} GLNode;

核心函數（均採用遞歸）：

• creatGList：讀字符構建，# 為空，( 遞歸建子表，, 遞歸建後繼。
• printGList：遞歸輸出，子表加括號。
• GLLength：遍歷頂層 next 計數。
• GLDepth：遞歸求最大子表深度 +1。
• GLCopy：遞歸深拷貝。
• head/tail：取表頭/表尾（子表或原子）。

關於 union：所有成員共用一塊內存，大小等於最大成員。同一時刻只能存一個值，節省空間。

總結

棧/隊列是特殊線性表，操作思想一致，體現模塊化設計；串採用塊鏈優化空間；廣義表以 tag+union 統一異構節點，遞歸處理天然契合其定義。下章進入樹與圖。