维基百科

广义表

广义表（英语：Generalized List）是一种非线性的数据结构。但如果广义表的每个元素都是原子，它就变成了线性表。广义表广泛地用于人工智慧等领域的LISP语言。

广义表一般记作 LS = (a1, a2, ···, an), n是它的长度，ai可以是单个元素(原子)，也可以是广义表(子表)，当广义表非空时，称第一个元素a1为LS的表头，称其余元素组成的表为LS的表尾。注意：表头是元素(可以是原子，也可以是广表)，表尾一定是广义表。[1]E=(a, E)是一个递归的表。D=(( ),(e),(a,(b,c,d)))是多层次的广义表，长度为3，深度为3。例：((a),a)的表头是(a)，表尾是(a)，((a))的表头是(a)，表尾是( )。

头尾链表存储表示

存储结构

// 广义表的头尾链表存储表示
typedef enum {ATOM, LIST} ElemTag;
// ATOM==0：原子，LIST==1：子表
typedef struct GLNode {
    ElemTag tag;
    // 公共部分，用于区分原子结点和表结点
    union {
        // 原子结点和表结点的联合部分
        AtomType atom;
        // atom是原子结点的值域，AtomType由用户定义
        struct {
            struct GLNode *hp, *tp;
        } ptr;
        // ptr是表结点的指针域，prt.hp和ptr.tp分别指向表头和表尾
    } a;
} *GList, GLNode; // 广义表类型

基本操作

// 广义表的头尾链表存储的基本操作(11个)
#include"func5-1.c"
void InitGList(GList *L) {
    // 创建空的广义表L
    *L = NULL;
}

void CreateGList(GList *L, SString S) {
    // 采用头尾链表存储结构，由广义表的书写形式串S创建广义表L。设emp="()"
    SString sub, hsub, emp;
    GList p, q;
    StrAssign(emp, "()"); // 空串emp="()"
    if (!StrCompare(S, emp)) // S="()"
        *L = NULL; // 创建空表
    else { // S不是空串
        *L = (GList)malloc(sizeof(GLNode));
        if (!*L) // 建表结点
            exit(OVERFLOW);
        if (StrLength(S) == 1) {
            // S为单原子，只会出现在递归调用中
            (*L)->tag = ATOM;
            (*L)->a.atom = S[1]; // 创建单原子广义表
        } else { // S为表
            (*L)->tag = LIST;
            p = *L;
            SubString(sub, S, 2, StrLength(S) - 2);
            // 脱外层括号(去掉第1个字符和最后1个字符)给串sub
            do {
                // 重复建n个子表
                sever(sub, hsub); // 从sub中分离出表头串hsub
                CreateGList(&p->a.ptr.hp, hsub);
                q = p;
                if (!StrEmpty(sub)) { // 表尾不空
                    p = (GLNode *)malloc(sizeof(GLNode));
                    if (!p)
                        exit(OVERFLOW);
                    p->tag = LIST;
                    q->a.ptr.tp = p;
                }
            } while (!StrEmpty(sub));
            q->a.ptr.tp = NULL;
        }
    }
}
void DestroyGList(GList *L) {
    // 销毁广义表L
    GList q1, q2;
    if (*L) {
        if ((*L)->tag == LIST) { // 删除表结点
            q1 = (*L)->a.ptr.hp; // q1指向表头
            q2 = (*L)->a.ptr.tp; // q2指向表尾
            DestroyGList(&q1); // 销毁表头
            DestroyGList(&q2); // 销毁表尾
        }
        free(*L);
        *L = NULL;
    }
}

void CopyGList(GList *T, GList L) {
    // 采用头尾链表存储结构，由广义表L复制得到广义表T
    if (!L) // 复制空表
        *T = NULL;
    else {
        *T = (GList)malloc(sizeof(GLNode));
        // 建表结点
        if (!*T)
            exit(OVERFLOW);
        (*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);
        }
    }
}

int GListLength(GList L) {
    /* 返回广义表的长度，即元素个数 */
    int len = 0;
    while (L) {
        L = L->a.ptr.tp;
        len++;
    }
    return len;
}

int GListDepth(GList L) {
    /* 采用头尾链表存储结构，求广义表L的深度。*/
    int max, dep;
    GList pp;
    if (!L)
        return 1; /* 空表深度为1 */
    if (L->tag == ATOM)
        return 0; /* 原子深度为0，只会出现在递归调用中 */
    for (max = 0, pp = L; pp; pp = pp->a.ptr.tp) {
        dep = GListDepth(pp->a.ptr.hp); /* 递归求以pp->a.ptr.hp为头指针的子表深度 */
        if (dep > max)
            max = dep;
    }
    return max + 1; /* 非空表的深度是各元素的深度的最大值加1 */
}

Status GListEmpty(GList L) {
    /* 判定广义表是否为空 */
    if (!L)
        return TRUE;
    else
        return FALSE;
}

GList GetHead(GList L) {
    /* 生成广义表L的表头元素，返回指向这个元素的指针 */
    GList h, p;
    if (!L) /* 空表无表头 */
        return NULL;
    p = L->a.ptr.hp; /* p指向L的表头元素 */
    CopyGList(&h, p); /* 将表头元素复制给h */
    return h;
}

GList GetTail(GList L) {
    /* 将广义表L的表尾生成为广义表，返回指向这个新广义表的指针 */
    GList t;
    if (!L) /* 空表无表尾 */
        return NULL;
    CopyGList(&t, L->a.ptr.tp); /* 将L的表尾拷给t */
    return t;
}

void InsertFirst_GL(GList *L, GList e) {
    /* 初始条件：广义表存在。操作结果：插入元素e(也可能是子表)作为广义表L的第1元素(表头) */
    GList p = (GList)malloc(sizeof(GLNode)); /* 生成新结点 */
    if (!p)
        exit(OVERFLOW);
    p->tag = LIST; /* 结点的类型是表 */
    p->a.ptr.hp = e; /* 表头指向e */
    p->a.ptr.tp = *L; /* 表尾指向原表L */
    *L = p; /* L指向新结点 */
}

void DeleteFirst_GL(GList *L, GList *e) {
    // 初始条件：广义表L存在。操作结果：删除广义表L的第一元素，并用e返回其值
    GList p = *L; // p指向第1个结点
    *e = (*L)->a.ptr.hp; // e指向L的表头
    *L = (*L)->a.ptr.tp; // L指向原L的表尾
    free(p); // 释放第1个结点
}

void Traverse_GL(GList L, void(*v)(AtomType)) {
    // 利用递归算法遍历广义表L
    if (L) // L不空
        if (L->tag == ATOM) // L为单原子
            v(L->a.atom);
        else { // L为广义表
            Traverse_GL(L->a.ptr.hp, v);
            // 递归遍历L的表头
            Traverse_GL(L->a.ptr.tp, v);
            // 递归遍历L的表尾
        }
}

扩展线性链表存储表示

存储结构

// 广义表的扩展线性链表存储表示
typedef enum {ATOM, LIST} ElemTag;
// ATOM==0：原子，LIST==1：子表
typedef struct GLNode1 {
    ElemTag tag;
    // 公共部分，用于区分原子结点和表结点
    union {
        // 原子结点和表结点的联合部分
        AtomType atom; // 原子结点的值域
        struct GLNode1 *hp; // 表结点的表头指针
    } a;
    struct GLNode1 *tp;
    // 相当于线性链表的next，指向下一个元素结点
} *GList1, GLNode1;
// 广义表类型GList1是一种扩展的线性链表

基本操作

// 广义表的扩展线性链表存储(的基本操作(13个)
#include"func5-1.c"

void InitGList(GList1 *L) {
    // 创建空的广义表L
    *L = NULL;
}

void CreateGList(GList1 *L, SString S) {
    // 采用扩展线性链表存储结构，由广义表的书写形式串S创建广义表L。设emp="()"
    SString emp, sub, hsub;
    GList1 p;
    StrAssign(emp, "()"); /* 设emp="()" */
    *L = (GList1)malloc(sizeof(GLNode1));
    if (!*L) /* 建表结点不成功 */
        exit(OVERFLOW);
    if (!StrCompare(S, emp)) { /* 创建空表 */
        (*L)->tag = LIST;
        (*L)->a.hp = (*L)->tp = NULL;
    } else if (StrLength(S) == 1) { /* 创建单原子广义表 */
        (*L)->tag = ATOM;
        (*L)->a.atom = S[1];
        (*L)->tp = NULL;
    } else { /* 创建一般表 */
        (*L)->tag = LIST;
        (*L)->tp = NULL;
        SubString(sub, S, 2, StrLength(S) - 2);
        // 脱外层括号(去掉第1个字符和最后1个字符)给串sub
        sever(sub, hsub); // 从sub中分离出表头串hsub
        CreateGList(&(*L)->a.hp, hsub);
        p = (*L)->a.hp;
        while (!StrEmpty(sub)) { // 表尾不空，则重复建n个子表
            sever(sub, hsub); // 从sub中分离出表头串hsub
            CreateGList(&p->tp, hsub);
            p = p->tp;
        };
    }
}

void DestroyGList(GList1 *L) {
    /* 初始条件：广义表L存在。操作结果：销毁广义表L */
    GList1 ph, pt;
    if (*L) { /* L不为空表 */
        /* 由ph和pt接替L的两个指针 */
        if ((*L)->tag) /* 是子表 */
            ph = (*L)->a.hp;
        else /* 是原子 */
            ph = NULL;
        pt = (*L)->tp;
        DestroyGList(&ph); /* 递归销毁表ph */
        DestroyGList(&pt); /* 递归销毁表pt */
        free(*L); /* 释放L所指结点 */
        *L = NULL; /* 令L为空 */
    }
}

void CopyGList(GList1 *T, GList1 L) {
    /* 初始条件：广义表L存在。操作结果：由广义表L复制得到广义表T */
    *T = NULL;
    if (L) { /* L不空 */
        *T = (GList1)malloc(sizeof(GLNode1));
        if (!*T)
            exit(OVERFLOW);
        (*T)->tag = L->tag; /* 复制枚举变量 */
        if (L->tag == ATOM) /* 复制共用体部分 */
            (*T)->a.atom = L->a.atom; /* 复制单原子 */
        else
            CopyGList(&(*T)->a.hp, L->a.hp); /* 复制子表 */
        if (L->tp == NULL) /* 到表尾 */
            (*T)->tp = L->tp;
        else
            CopyGList(&(*T)->tp, L->tp); /* 复制子表 */
    }
}

int GListLength(GList1 L) {
    /* 初始条件：广义表L存在。操作结果：求广义表L的长度，即元素个数 */
    int len = 0;
    GList1 p = L->a.hp; /* p指向第1个元素 */
    while (p) {
        len++;
        p = p->tp;
    };
    return len;
}

int GListDepth(GList1 L) {
    /* 初始条件：广义表L存在。操作结果：求广义表L的深度 */
    int max, dep;
    GList1 pp;
    if (L == NULL || L->tag == LIST && !L->a.hp)
        return 1; /* 空表深度为1 */
    else if (L->tag == ATOM)
        return 0; /* 单原子表深度为0，只会出现在递归调用中 */
    else /* 求一般表的深度 */
        for (max = 0, pp = L->a.hp; pp; pp = pp->tp) {
            dep = GListDepth(pp); /* 求以pp为头指针的子表深度 */
            if (dep > max)
                max = dep;
        }
    return max + 1; /* 非空表的深度是各元素的深度的最大值加1 */
}

Status GListEmpty(GList1 L) {
    /* 初始条件：广义表L存在。操作结果：判定广义表L是否为空 */
    if (!L || L->tag == LIST && !L->a.hp)
        return OK;
    else
        return ERROR;
}

GList1 GetHead(GList1 L) {
    /* 生成广义表L的表头元素，返回指向这个元素的指针 */
    GList1 h, p;
    if (!L || L->tag == LIST && !L->a.hp) /* 空表无表头 */
        return NULL;
    p = L->a.hp->tp; /* p指向L的表尾 */
    L->a.hp->tp = NULL; /* 截去L的表尾部分 */
    CopyGList(&h, L->a.hp); /* 将表头元素复制给h */
    L->a.hp->tp = p; /* 恢复L的表尾(保持原L不变) */
    return h;
}

GList1 GetTail(GList1 L) {
    // 将广义表L的表尾生成为广义表，返回指向这个新广义表的指针
    GList1 t, p;
    if (!L || L->tag == LIST && !L->a.hp) // 空表无表尾
        return NULL;
    p = L->a.hp; // p指向表头
    L->a.hp = p->tp; // 在L中删去表头
    CopyGList(&t, L); // 将L的表尾拷给t
    L->a.hp = p; // 恢复L的表头(保持原L不变)
    return t;
}

void InsertFirst_GL(GList1 *L, GList1 e) {
    // 初始条件：广义表存在。操作结果：插入元素e(也可能是子表)作为广义表L的第1元素(表头)
    GList1 p = (*L)->a.hp;
    (*L)->a.hp = e;
    e->tp = p;
}

void DeleteFirst_GL(GList1 *L, GList1 *e) {
    // 初始条件：广义表L存在。操作结果：删除广义表L的第一元素，并用e返回其值
    if (*L && (*L)->a.hp) {
        *e = (*L)->a.hp;
        (*L)->a.hp = (*e)->tp;
        (*e)->tp = NULL;
    } else
        *e = *L;
}

void Traverse_GL(GList1 L, void(*v)(AtomType)) {
    // 利用递归算法遍历广义表L
    GList1 hp;
    if (L) { // L不空
        if (L->tag == ATOM) { // L为单原子
            v(L->a.atom);
            hp = NULL;
        } else // L为子表
            hp = L->a.hp;
        Traverse_GL(hp, v);
        Traverse_GL(L->tp, v);
    }
}

参考资料

  1. ^ 崔巍; 何玉洁; 郁红英. 数据库技术教程(三级). 清华大学出版社. 2005: P59. ISBN 9787302103769. 
检索自“https://zh.wikipedia.org/w/index.php?title=广义表&oldid=60464910”