數據結構C語言實現：廣義表頭尾鏈表存儲與操作

編輯：關於C語言

數據結構C語言實現：廣義表頭尾鏈表存儲與操作

一、廣義表定義與存儲結構

廣義表是線性表推廣，元素可為原子或子表。頭尾鏈表（Head-Tail Linked List）表示：

表頭指針hp：指向第一個元素（原子或子表）
表尾指針tp：指向剩餘部分（即下一個節點）

節點結構

typedef enum { ATOM, LIST } ElemTag; // 0:原子 1:子表
typedef char AtomType;

typedef struct GLNode {
    ElemTag tag; // 區分原子/表節點
    union {
        AtomType atom;        // 原子值
        struct {              // 表節點指針
            struct GLNode *hp; // 表頭
            struct GLNode *tp; // 表尾
        } ptr;
    } a;
} *GList, GLNode;

二、核心操作實現

1. 初始化與銷毀

int InitGList(GList *L) { *L = NULL; return 1; }

void DestroyGList(Glist *L) {
    if (!*L) return;
    if ((*L)->tag == ATOM) { free(*L); *L = NULL; }
    else {
        GList h = (*L)->a.ptr.hp, t = (*L)->a.ptr.tp;
        free(*L); *L = NULL;
        DestroyGList(&h); DestroyGList(&t); // 遞歸銷毀
    }
}

2. 複製（深拷貝）

int CopyGList(GList *T, GList L) {
    if (!L) { *T = NULL; return 1; }
    *T = (GList)malloc(sizeof(GLNode));
    (*T)->tag = L->tag;
    if (L->tag == ATOM) (*T)->a.atom = L->a.atom;
    else {
        CopyGList(&(*T)->a.ptr.hp, L->a.ptr.hp);
        CopyGList(&(*T)->a.ptr.tp, L->a.ptr.tp);
    }
    return 1;
}

3. 長度與深度

// 長度：頂層元素個數
int GListLength(GList L) {
    int len = 0;
    if (!L) return 0;
    if (L->tag == ATOM) return 1;
    while (L) { L = L->a.ptr.tp; len++; }
    return len;
}

// 深度：最大嵌套層數
int GListDepth(GList L) {
    if (!L) return 1; // 空表深度1
    if (L->tag == ATOM) return 0; // 原子深度0
    int max = 0;
    for (GList p = L; p; p = p->a.ptr.tp) {
        int dep = GListDepth(p->a.ptr.hp);
        if (dep > max) max = dep;
    }
    return max + 1;
}

4. 取表頭/表尾

GList GetHead(GList L) {
    if (!L) exit(ERROR);
    GList p = L->a.ptr.tp; L->a.ptr.tp = NULL;
    GList h; CopyGList(&h, L);
    L->a.ptr.tp = p; return h;
}

GList GetTail(GList L) {
    if (!L) exit(ERROR);
    GList t; CopyGList(&t, L->a.ptr.tp); return t;
}

5. 插入/刪除首元素

int InsertFirst_GL(GList *L, GList e) {
    GList p = (GList)malloc(sizeof(GLNode));
    p->tag = LIST; p->a.ptr.hp = e; p->a.ptr.tp = *L;
    *L = p; return 1;
}

int DeleteFirst_GL(GList *L, GList *e) {
    *e = (*L)->a.ptr.hp;
    GList p = *L; *L = (*L)->a.ptr.tp; free(p); return 1;
}

6. 遍歷

void Traverse_GL(GList L, void(*visit)(AtomType)) {
    if (!L) return;
    if (L->tag == ATOM) visit(L->a.atom);
    else {
        Traverse_GL(L->a.ptr.hp, visit);
        Traverse_GL(L->a.ptr.tp, visit);
    }
}

三、串操作輔助函數

用於解析字符串構建廣義表（如"(a,(b),c,(d,(e)))"）：

StrAssign/StrCopy/StrEmpty/StrCompare/SubString：基本串操作
sever：按逗號分割表頭串與表尾串（處理括號嵌套平衡）

四、從字符串創建廣義表

int CreateGList(GList *L, SString S) {
    SString emp = "()";
    if (StrCompare(S, emp) == 0) { *L = NULL; return 1; } // 空表
    
    *L = (GList)malloc(sizeof(GLNode));
    if (StrLength(S) == 1) { // 單原子
        (*L)->tag = ATOM; (*L)->a.atom = S[1]; return 1;
    }
    
    (*L)->tag = LIST;
    GList p = *L, q;
    SString sub, hsub;
    SubString(sub, S, 2, StrLength(S)-2); // 脫外層括號
    
    do {
        sever(sub, hsub); // 分離表頭串
        CreateGList(&p->a.ptr.hp, hsub); // 遞歸創建表頭
        q = p;
        if (!StrEmpty(sub)) { // 表尾非空，創建表尾節點
            p = (GList)malloc(sizeof(GLNode));
            p->tag = LIST; q->a.ptr.tp = p;
        }
    } while (!StrEmpty(sub));
    q->a.ptr.tp = NULL; return 1;
}

五、主程序測試

int main() {
    char *str = "(a,(b),c,(d,(e)))";
    SString s; StrAssign(s, str);
    GList L, m; InitGList(&L); InitGList(&m);
    
    CreateGList(&L, s);
    printf("長度=%d, 深度=%d\n", GListLength(L), GListDepth(L));
    Traverse_GL(L, visit); // 輸出: a b c d e
    
    CopyGList(&m, L);
    m = GetHead(L); Traverse_GL(m, visit); // a
    m = GetTail(L); Traverse_GL(m, visit); // (b),c,(d,(e))
    
    InsertFirst_GL(&m, L); // L作為m新表頭
    DeleteFirst_GL(&m, &L); // 刪除表頭
    
    DestroyGList(&L); DestroyGList(&m);
    return 0;
}