广义表简介

概念

广义表是n个数据元素组成的有限序列

$GL = (d_1,d_2,d_3,...,d_n)$

GL是广义表的名字,n是广义表的长度.

广义表中的元素既可以是单个元素,也可以是广义表.

若d_i为广义表,则可称为是GL的子表.
广义表的表头:d₁是广义表的表头,即广义表的第一个元素

通常，广义表中存储的单个元素称为 “原子”，而存储的广义表称为 “子表”。

广义表的表尾:广义表的GL其余部分组成的表,即(d₂,d₃,…,d_n)为表尾

除非广义表为空表，否则广义表一定具有表头和表尾，且广义表的表尾一定是一个广义表。

广义表是递归定义的.

A = ()：A 表示一个广义表，只不过表是空的。
B = (e)：广义表 B 中只有一个原子 e。
C = (a,(b,c,d)) ：广义表 C 中有两个元素，原子 a 和子表 (b,c,d)。
D = (A,B,C)：广义表 D 中存有 3 个子表，分别是A、B和C。这种表示方式等同于 D = ((),(e),(b,c,d)) 。
E = (a,E)：广义表 E 中有两个元素，原子 a 和它本身。这是一个递归广义表，等同于：E = (a,(a,(a,…)))。

存储结构

由于广义表中既可存储原子（不可再分的数据元素），也可以存储子表，因此很难使用顺序存储结构表示，通常情况下广义表结构采用链表实现.

头尾链表存储结构

表中每个元素用一个结点表示,表中有两类结点:

单个元素结点
子表节点

任何非空的子表都可以分成表头和表尾两部分

元素节点需要值域和标志域,表结点由标志域和指向表头,表尾的指针组成

typedef enum{ATOM,LIST} ElemTag;
typedef struct GLNode{
    ElemTag tag;//标志域
    union{
        AtomType atom;//原子结点的值域
        struct{
            struct GLNode * hp,*tp;//表头结点指针与表尾结点
        }htp;//子表结点的指针域，hp指向表头；tp指向表尾
    }atom_htp;//原子值域与表结点指针域的联合体
}GLNode,*Glist;

广义表同层节点链存储结构

在这种结构中,无论是原子结点还是表结点都由三个域构成

.png)

typedef enum{ATOM,LIST} ElemTag;
typedef struct GLNode{
    ElemTag tag;//标志域
    union{
        AtomType atom;//原子结点的值域
        struct GLNode *hp;//子表结点的指针域，hp指向表头
    };
    struct GLNode * tp;//同层下一个结点的指针域
    //这里的tp相当于链表的next指针，用于指向下一个数据元素
}GLNode,*Glist;

相关操作

#include<stdio.h>
#include<stdlib.h>

typedef struct GLNode
{
    int tag;
    //tag = 0为原子
    //tag =1 为子表
    union
    {
        struct
        {
        struct Node *hp,*tp;
        }htp;
        int data;
    }atom_htp;
}GLNode,*GList;

GList Head(GList L);
GList Tail(GList L);
int Length(GList L);
int Depth(GList L);
int CountAtom(GList L);
int CopyGList(GList,GList*);

int main(void)
{

}

GList Head(GList L)
{
    if(!L)
    return NULL;
    if(L->tag == 0)
    exit(1);
    else
    return Head(L->atom_htp.htp.hp);
}

GList Tail(GList L)
{
    if(!L)
    return NULL;
    if(L->tag == 0)
    exit(0);
    else
    return Tail(L->atom_htp.htp.tp);
}

int Length(GList L)
{
    int k = 0;
    GList s;
    if(L==NULL)
    return 0;
    if(L->tag == 0)
    exit(1);
    s = L;
    while(s!=NULL)
    {
        k++;
        s = s->atom_htp.htp.tp;
    }
    return k;
}
int Depth(GList L)
{
    int d,max;
    GList s;
    if(L==NULL)
    return 1;
    if(L->tag ==0)
    return 0;
    s = L;
    while(s!=NULL)
    {
        d = Depth(s->atom_htp.htp.hp);
        if(d>max)
        max =d;
        s = s->atom_htp.htp.tp;
    }
    return max+1;
}

int CountAtom(GList L)
{
    int n1,n2;
    if(L==NULL)
    return 0;
    if(L->tag == 0)
    return 1;
    n1 = CountAtom(L->atom_htp.htp.hp);
    n2 = CountAtom(L->atom_htp.htp.tp);
    return (n1+n2);
}
int CopyGList(GList S,GList *T)
{
    if(S==NULL)
    {*T == NULL;
    return 0;}
    if(S->tag == 0)
    (*T)->atom_htp.data = S->atom_htp.data;
    else
    {
        CopyGList(S->atom_htp.htp.hp,&((*T)->atom_htp.htp.hp));
        CopyGList(S->atom_htp.htp.tp,&((*T)->atom_htp.htp.tp));
    } 

}