廣義表，也被稱作列表（Lists），是一種遞歸的數據結構。它就像一個神秘的盒子，既可以裝著單個元素（原子），也可以嵌套著其他的盒子（子列表）。比如廣義表?(a (b c) d)，其中?a?和?d?是原子，而?(b c)?則是一個子列表。這種嵌套結構使得廣義表能夠輕松表示各種復雜的關系，就像一位萬能的畫家，能描繪出樹形結構、圖結構等多樣的 “畫作”。

與普通的線性表相比，廣義表的元素類型更加豐富多樣，不僅可以是相同類型的元素，還能包含不同類型的元素，甚至可以嵌套其他的廣義表。這種靈活性讓廣義表在處理復雜數據時游刃有余，成為了數據結構中的 “多面手”。

先上代碼：

#include <stdio.h>
#include <stdlib.h>// 定義原子類型為字符型
typedef char AtomType;// 定義元素標簽類型，用于區分原子和列表
typedef enum { ATOM, LIST } ElemTag;// 定義廣義表節點結構體
typedef struct GLNode 
{ElemTag tag;  // 標記該節點是原子還是列表union {AtomType atom;  // 如果是原子，存儲原子的值struct GLNode *child;  // 如果是列表，指向子列表} UNION;struct GLNode *next;  // 指向下一個節點
} GLNODE;// 定義元素標志類型，用于讀取字符串時識別不同元素
typedef enum { LP = 1, RP = 2, Atom = 3, End = 4 } ElemFlag;// 從 str[*pi] 開始讀入一個元素
ElemFlag GetElem(char str[], int *pi, AtomType *pe)
{while (str[*pi] == ' ') (*pi)++;// 跳過空格if (str[*pi] == '\0') return End;// 如果到達字符串末尾，返回 End 標志if (str[*pi] == '(')// 如果遇到左括號，返回 LP 標志，并將指針后移{		(*pi)++;return LP;}if (str[*pi] == ')') // 如果遇到右括號，返回 RP 標志，并將指針后移{(*pi)++;return RP;}// 如果是原子，將字符賦值給 pe，并將指針后移，返回 Atom 標志*pe = str[*pi];(*pi)++;return Atom;
}// 建廣義表
GLNODE *Glist_Create(char str[], int *pi) 
{GLNODE *p;AtomType e;// 根據讀取的元素類型進行不同處理switch (GetElem(str, pi, &e)) {case Atom:// 為原子節點分配內存p = (GLNODE *)malloc(sizeof(GLNODE));if (p == NULL) {fprintf(stderr, "內存分配失敗\n");exit(EXIT_FAILURE);}p->tag = ATOM;p->UNION.atom = e;p->next = Glist_Create(str, pi);// 遞歸創建下一個節點return p;case LP:// 為列表節點分配內存p = (GLNODE *)malloc(sizeof(GLNODE));if (p == NULL) {fprintf(stderr, "內存分配失敗\n");exit(EXIT_FAILURE);}p->tag = LIST;p->UNION.child = Glist_Create(str, pi);// 遞歸創建子列表p->next = Glist_Create(str, pi);// 遞歸創建下一個節點return p;case RP:return NULL;case End:return NULL;}return NULL;
}// 求表深度
int GList_Depth(GLNODE *L) 
{GLNODE *p;int depth1, max = 0;if (L == NULL || L->tag == ATOM) return 0;// 如果是原子節點，深度為 0for (p = L->UNION.child; p; p = p->next) // 遍歷子列表{depth1 = GList_Depth(p);// 遞歸計算子列表的深度if (depth1 > max) max = depth1;}return max + 1;// 列表深度為子列表最大深度加 1
}// 遍歷廣義表，打印層次括號
void GList_Traverse(GLNODE *L) 
{GLNODE *p;for (p = L; p != NULL; p = p->next) {if (p->tag == ATOM) {printf("%c ", p->UNION.atom);// 打印原子節點的值} else {printf("(");// 遇到列表節點，打印左括號GList_Traverse(p->UNION.child);// 遞歸遍歷子列表printf(")");// 打印右括號}}
}// 復制廣義表
GLNODE *GList_Copy(GLNODE *L) 
{GLNODE *head = NULL, *p, *newNode, *tail = NULL;if (!L) return NULL;for (p = L; p != NULL; p = p->next) {// 為新節點分配內存newNode = (GLNODE *)malloc(sizeof(GLNODE));if (newNode == NULL) {fprintf(stderr, "內存分配失敗\n");exit(EXIT_FAILURE);}if (head == NULL) {head = tail = newNode;} else {tail->next = newNode;tail = newNode;}if (p->tag == ATOM) {newNode->tag = ATOM;// 復制原子節點newNode->UNION.atom = p->UNION.atom;} else {newNode->tag = LIST;// 復制列表節點，遞歸復制子列表newNode->UNION.child = GList_Copy(p->UNION.child);}}if (tail) {tail->next = NULL;}return head;
}int main() 
{char str[30] = "(a (b c) d)";  // 廣義表的字符串表示int i = 0;GLNODE *L1, *L2;L1 = Glist_Create(str, &i);		// 創建廣義表 L1GList_Traverse(L1);				// 遍歷并打印廣義表 L1printf("%d\n", GList_Depth(L1));// 計算并打印廣義表 L1 的深度L2 = GList_Copy(L1);			// 復制廣義表 L1 到 L2GList_Traverse(L2);				// 遍歷并打印廣義表 L2printf("%d\n", GList_Depth(L2));// 計算并打印廣義表 L2 的深度return 0;
}

（一）數據結構定義：搭建廣義表的基石

typedef struct GLNode 
{ElemTag tag;  // 標記該節點是原子還是列表union {AtomType atom;  // 如果是原子，存儲原子的值struct GLNode *child;  // 如果是列表，指向子列表} UNION;struct GLNode *next;  // 指向下一個節點
} GLNODE;

這段代碼定義了廣義表的節點結構?GLNODE。tag?字段就像一個神奇的標簽，能夠區分節點是原子還是列表。UNION?聯合體則根據?tag?的值，巧妙地存儲原子或指向子列表的指針。next?指針則負責將各個節點連接起來，形成一個有序的鏈條。這種設計讓廣義表能夠靈活地表示不同類型的元素和復雜的嵌套結構，為后續的操作奠定了堅實的基礎。

（二）廣義表的創建：從字符串到數據結構的神奇轉變

GLNODE *Glist_Create(char str[], int *pi) 
{// ...
}

Glist_Create?函數是廣義表創建的核心。它通過?GetElem?函數從輸入的字符串中逐個讀取元素，就像一位細心的工匠，根據元素的類型（原子、左括號、右括號、字符串結束）進行不同的處理。遇到原子時，為其創建一個原子節點；遇到左括號時，創建一個列表節點，并遞歸地創建子列表。遞歸的方式讓代碼簡潔而高效，能夠輕松應對廣義表的嵌套結構，就像一位技藝高超的魔術師，將字符串神奇地轉化為廣義表的數據結構。

（三）廣義表的深度計算：探索廣義表的 “深度” 秘密

int GList_Depth(GLNODE *L) 
{// ...
}

GList_Depth?函數用于計算廣義表的深度。對于原子節點，其深度為 0；對于列表節點，則遞歸地計算子列表的深度，并取子列表最大深度加 1 作為當前列表的深度。遞歸的思想在這里再次發揮了重要作用，讓我們能夠輕松地探索廣義表的 “深度” 秘密，就像一位勇敢的探險家，深入廣義表的內部，測量其嵌套的層次。

（四）廣義表的遍歷：揭開廣義表的 “廬山真面目”

void GList_Traverse(GLNODE *L) 
{// ...
}

GList_Traverse?函數就像一位導游，帶領我們遍歷廣義表并打印其層次括號表示。遇到原子節點時，直接打印原子的值；遇到列表節點時，先打印左括號，遞歸地遍歷子列表，再打印右括號。通過遞歸遍歷，我們能夠清晰地看到廣義表的層次結構，揭開它的 “廬山真面目”，仿佛置身于一個神秘的迷宮中，一步步揭開它的神秘面紗。

（五）廣義表的復制：克隆一個一模一樣的廣義表

GLNODE *GList_Copy(GLNODE *L) 
{// ...
}

GList_Copy?函數用于復制廣義表。它遍歷原廣義表的每個節點，為新節點分配內存，并根據節點類型復制原子或遞歸地復制子列表。這樣，我們就可以得到一個與原廣義表結構完全相同的新廣義表，就像克隆技術一樣，復制出一個一模一樣的 “雙胞胎”。

運行：

四、廣義表的應用場景：無處不在的 “魔法工具”

（一）編譯器設計：解析代碼的得力助手

在編譯器中，廣義表可以用于表示語法樹。語法樹是源代碼的一種抽象表示，它反映了代碼的語法結構。廣義表的嵌套結構正好可以用來表示語法樹的層次關系，方便編譯器進行語法分析和代碼生成。就像一位聰明的翻譯官，將源代碼翻譯成計算機能夠理解的機器語言。

（二）人工智能：構建知識圖譜的強大武器

在人工智能領域，廣義表可以用于表示知識圖譜。知識圖譜是一種語義網絡，用于表示實體之間的關系。廣義表可以將實體和關系表示為節點和子列表，從而方便進行知識的存儲和推理。就像一位智慧的導師，幫助人工智能系統更好地理解和處理知識。

（三）圖形處理：繪制復雜圖形的神奇畫筆

在圖形處理中，廣義表可以用于表示復雜的圖形結構。例如，一個三維模型可以由多個子模型組成，每個子模型又可以由多個基本圖形組成。廣義表可以很好地表示這種層次結構，方便進行圖形的渲染和處理。就像一位天才的畫家，用神奇的畫筆繪制出絢麗多彩的圖形世界。

五、總結與展望

通過遞歸的方式，我們可以方便地實現廣義表的創建、深度計算、遍歷和復制等操作。