广义表

顾名思义，广义表是线性表的推广。也有人称其为列表（list）。广泛的用于人工智能等领域的表处理语言LISP语言，把广义表作为基本的数据结构，就连程序也表示为一系列的广义表。
github源码

广义表一般记作LS = [a1,a2,…,an],其中LS是广义表的名称，n是它的长度。在线性表的定义中，ai只限于是单个元素，而在广义表的定义中，ai可以是单个元素，也可以是广义表，分别称为广义表LS的原子和子表。

由于广义表中的数据元素可以具有不同的结构（或是原子，或是列表），因此难以用顺序存储结构表示，通常采用链式存储结构，每个数据元素可用一个结点表示。

我设计的广义表的结点元素定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
typedef enum GLNodeElemTag{
    ATOM,  //原子结点
    LIST   //表结点
}GLNodeElemTag;

typedef struct GLNode{
    GLNodeElemTag tag;   //tag用于区分原子结点和表结点
    union content{              //原子结点和表结点的联合
        GLNodeElemType *elem;  //原子结点的指针
        struct GLNode *hp; //表结点的表头指针
    }content;
    struct GLNode *prior; //指向前一个元素的结点 
    struct GLNode *next; //指向下一个元素的结点 
}GLNode;

如果一个结点的元素为原子，那么结点的tag设置为ATOM，联合体中的elem指向该原子元素的地址；如果一个结点的元素为列表，那么结点的tag设置为LIST，联合体中的hp指向该子表的表头。

其中GLNodeElemType定义为MyString，以方便处理。

MyString是前面文章中用C封装的一个字符串的对象:C封装字符串、字符串数组对象

广义表对象GList定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
typedef struct GList{
    GLNode *root;
    GLNode *tear;
    int (*isEmpty)(struct GList *This);
    int (*length)(struct GList *This);
    void (*print)(struct GList *This);
    int (*getDepth)(struct GList *This);
    int (*getHead)(struct GList *This,GLNode **n);
    int (*getTear)(struct GList *This,GLNode **n);
    int (*getGLNode)(struct GList *This,int index,GLNode **n);
    int (*insertGLNode)(struct GList *This, int index, GLNode *n);
    int (*insertGLNodeFront)(struct GList *This, GLNode *n);
    int (*deleteGLNodeFront)(struct GList *This);
    int (*insertGLNodeTear)(struct GList *This, GLNode *n);
    int (*deleteGLNodeTear)(struct GList *This);
    void (*traversal)(struct GList *This,int (*visit)(GLNodeElemType **elem));
}GList;

此外对于GList的操作函数有：

1
2
3
4
GList *initGListFromString(char *listStr);
GList *initGListFromGLNode(GLNode *n);
GList *copyGList(GList *L);
void DestroyGList(GList *L);

可以单独操作结点GLNode的函数有：

1
2
3
4
5
void printGLNode(GLNode *n);
int getGLNodeDepth(GLNode *n);
GLNode *copyGLNode(GLNode *n);
void traversalGLNode(GLNode *n,int (*visit)(GLNodeElemType **elem));
void destroyGLNode(GLNode *n);

因为广义表的支持表嵌套的特性，大部分底层操作函数均用递归实现。
例如，以一个字符串创建一个GList对象：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
static GLNode *createGListFromString(GLNode **p,MyString *gListStr){
    int i;
    GLNode **create_temp = p;
    GLNode *glnode_temp = NULL;
    GLNode *glnode_root = NULL;
    MyString *elemstr = NULL;
    MyString *leftstr = NULL;
    MyString *substr = substrMyString(gListStr,1,gListStr->length-1);//脱去括号
    destroyMyString(gListStr);
    if(!substr){ //括号内是一个空表
        *create_temp = (GLNode*)malloc(sizeof(GLNode)); //添加原子结点
        if(*create_temp){
            (*create_temp)->tag = ATOM;
            (*create_temp)->content.elem = elemstr;
            (*create_temp)->prior = NULL;
            (*create_temp)->next = NULL;
        }
        glnode_root = *create_temp;
    }else{
        do{
            if(substr){
                if(*(substr->str) != '['){
                    i = myStringIndexChar(substr,',',0);
                    if(i != -1){
                        elemstr = substrMyString(substr,0,i);//提取表头
                        leftstr = substrMyString(substr,i+1,substr->length);//提取剩余部分
                        destroyMyString(substr);
                        substr = leftstr;
                    }else{
                        elemstr = substrMyString(substr,0,substr->length);
                        destroyMyString(substr);
                    }
                    glnode_temp = *create_temp;
                    *create_temp = (GLNode*)malloc(sizeof(GLNode)); //添加原子结点
                    if(*create_temp){
                        (*create_temp)->tag = ATOM;
                        (*create_temp)->content.elem = elemstr;
                        if(glnode_temp){
                            (*create_temp)->prior = glnode_temp;
                            glnode_temp->next = *create_temp;
                        }else{
                            (*create_temp)->prior = NULL;
                            glnode_root = *create_temp;
                        }
                        (*create_temp)->next = NULL;
                    }
                }else{
                    i = getMatchingBracketIndex(substr,'[',0);
                    if(i != -1){
                        elemstr = substrMyString(substr,0,i+1);//提取表头,完整的一个Glist
                        leftstr = substrMyString(substr,i+2,substr->length);//提取剩余部分
                        destroyMyString(substr);
                        substr = leftstr;
                    }
                    glnode_temp = *create_temp;
                    *create_temp = (GLNode*)malloc(sizeof(GLNode)); //添加列表结点
                    if(*create_temp){
                        (*create_temp)->tag = LIST;
                        if(glnode_temp){
                            (*create_temp)->prior = glnode_temp;
                            glnode_temp->next = *create_temp;
                        }else{
                            (*create_temp)->prior = NULL;
                            glnode_root = *create_temp;
                        }
                        (*create_temp)->next = NULL;
                        (*create_temp)->content.hp = NULL;
                        (*create_temp)->content.hp = createGListFromString(&((*create_temp)->content.hp),elemstr);
                    }
                }
            }else{
                break;
            }
        }while(i != -1);
    }
    return glnode_root;
}

GList *initGListFromString(char *listStr){
    MyString *gListStr = NULL;
    GLNode *p = NULL;
    GList *L = (GList *)malloc(sizeof(GList));
    if(!L) return NULL;
    gListStr = myStringAssign(listStr);
    if(!gListStr){
        free(L);
        return NULL;
    }
    if(*(gListStr->str) != '['){
        printf("ListStr format error\n");
        destroyMyString(gListStr);
        free(L);
        return NULL;
    }
    if(isBracketMatching(gListStr,'[') == 0){
        printf("ListStr Bracke not match\n");
        destroyMyString(gListStr);
        free(L);
        return NULL;
    }
    L->root = NULL;
    L->root = createGListFromString(&(L->root),gListStr);
    p = L->root;
    while(p->next){
        p = p->next;
    }
    L->tear = p;
    L->isEmpty = isEmpty;
    L->length = length;
    L->print = print;
    L->getDepth = getDepth;
    L->getHead = getHead;
    L->getTear = getTear;
    L->getGLNode = getGLNode;
    L->insertGLNode = insertGLNode;
    L->insertGLNodeFront = insertGLNodeFront;
    L->deleteGLNodeFront = deleteGLNodeFront;
    L->insertGLNodeTear = insertGLNodeTear;
    L->deleteGLNodeTear = deleteGLNodeTear;
    L->traversal = traversal;
    return L;
}

完整代码请见github的DataStructure_C项目中Glist文件夹内。github源码
使用示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
GLNode *node1 = NULL;
GList *L = initGListFromString("[1D,2AD,[3SFDS,[4FEF,[5GRG,[6HJJY,[]]],7TKU],8GRGRH],9YJRDFB]");

printf("list L:\n");
L->print(L);
printf("is list L empty:%d\n",L->isEmpty(L));
printf("list L length:%d\n",L->length(L));
printf("list L depth:%d\n",L->getDepth(L));

printf("the index 3 of list L is : ");
L->getGLNode(L,3,&node1);
printGLNode(node1);
printf("\n");

printf("get glnode of index 2 of L:\n");
L->getGLNode(L,2,&node1);
printGLNode(node1);
printf("\n");

DestroyGList(L);

显示结果：

1
2
3
4
5
6
7
8
9
list L:
[1D,2AD,[3SFDS,[4FEF,[5GRG,[6HJJY,[]]],7TKU],8GRGRH],9YJRDFB]
is list L empty:0
list L length:4
list L depth:6
the index 3 of list L is : 9YJRDFB

get glnode of index 2 of L:
[3SFDS,[4FEF,[5GRG,[6HJJY,[]]],7TKU],8GRGRH]

测试DEMO

testGlist.c文件：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#include <stdio.h>
#include <malloc.h>
#include "Glist.h"

int visitGLNode(GLNodeElemType **elem){
    printMyString(*elem);
    return 0;
}

int main(void){
    GLNode *node1 = NULL;
    GLNode *node2 = NULL;
    GList *L = initGListFromString("[1D,2AD,[3SFDS,[4FEF,[5GRG,[6HJJY,[]]],7TKU],8GRGRH],9YJRDFB]");
    GList *L2 = NULL;
    GList *L3 = NULL;
    
    printf("list L:\n");
    L->print(L);
    printf("is list L empty:%d\n",L->isEmpty(L));
    printf("list L length:%d\n",L->length(L));
    printf("list L depth:%d\n",L->getDepth(L));
    
    printf("the index 3 of list L is : ");
    L->getGLNode(L,3,&node1);
    printGLNode(node1);
    printf("\n");
    
    printf("get glnode of index 2 of L:\n");
    L->getGLNode(L,2,&node1);
    printGLNode(node1);
    printf("\n");
    
    L2 = initGListFromGLNode(node1);
    printf("list L2:\n");
    L2->print(L2);
    printf("is list L2 empty:%d\n",L2->isEmpty(L2));
    printf("list L2 length:%d\n",L2->length(L2));
    printf("list L2 depth:%d\n",L2->getDepth(L2));
    printf("the index 0 of list L2 is : ");
    L2->getGLNode(L2,0,&node2);
    printGLNode(node2);
    printf("\n");
    
    L2->insertGLNodeFront(L2,node1);
    printf("insertGLNodeFront list L2:\n");
    L2->print(L2);
    printf("\n");
    
    L2->insertGLNodeTear(L2,node1);
    printf("insertGLNodeTear list L2:\n");
    L2->print(L2);
    printf("\n");
    
    printf("get glnode of index 0 of L2:\n");
    L2->getGLNode(L2,0,&node2);
    printGLNode(node2);
    printf("\n");
    
    printf("get glnode of index 1 of L2:\n");
    L2->getGLNode(L2,1,&node2);
    printGLNode(node2);
    printf("\n");
    
    printf("get head of L2:\n");
    L2->getHead(L2,&node2);
    printGLNode(node2);
    printf("\n");
    
    printf("get tear of L2:\n");
    L2->getTear(L2,&node2);
    printGLNode(node2);
    printf("\n");
    
    L2->deleteGLNodeTear(L2);
    printf("list L2:\n");
    L2->print(L2);
    printf("get tear of L2:\n");
    L2->getTear(L2,&node2);
    printGLNode(node2);
    printf("\n");
    
    L2->deleteGLNodeFront(L2);
    L2->deleteGLNodeFront(L2);
    printf("list L2:\n");
    L2->print(L2);
    printf("get head of L2:\n");
    L2->getHead(L2,&node2);
    printGLNode(node2);
    printf("\n");
    
    L3 = copyGList(L2);
    printf("list L3:\n");
    L3->print(L3);
    
    L3->insertGLNodeTear(L3,node1);
    printf("insertGLNodeTear list L3:\n");
    L3->print(L3);
    printf("\n");
    
    L3->insertGLNodeFront(L3,node2);
    printf("insertGLNodeFront list L3:\n");
    L3->print(L3);
    printf("\n");
    
    while(L3->length(L3)){
        printf("get tear of L3:\n");
        L3->getTear(L3,&node2);
        printGLNode(node2);
        printf("\n");
        
        L3->deleteGLNodeTear(L3);
        printf("list L3:\n");
        L3->print(L3);
        printf("\n");
    }
    
    printf("is list L3 empty:%d\n",L3->isEmpty(L3));
    printf("\n");
    
    printf("list L2:\n");
    L2->print(L2);
    printf("\n");
    
    while(L2->length(L2)){
        printf("get head of L2:\n");
        L2->getHead(L2,&node2);
        printGLNode(node2);
        printf("\n");
        
        L2->deleteGLNodeFront(L2);
        printf("list L2:\n");
        L2->print(L2);
        printf("\n");
    }
    
    printf("is list L2 empty:%d\n",L2->isEmpty(L2));
    printf("\n");
    
    printf("node1 traversal\n");
    traversalGLNode(node1,visitGLNode);
    printf("\n");
    
    printf("list L traversal\n");
    L->traversal(L,visitGLNode);
    printf("\n");
    
    DestroyGList(L);
    DestroyGList(L2);
    DestroyGList(L3);
    return 0;
}

编译：

1
gcc MyString.c MyStringArray.c Glist.c testGlist.c -o testGlist

运行testGlist：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
list L:
[1D,2AD,[3SFDS,[4FEF,[5GRG,[6HJJY,[]]],7TKU],8GRGRH],9YJRDFB]
is list L empty:0
list L length:4
list L depth:6
the index 3 of list L is : 9YJRDFB

get glnode of index 2 of L:
[3SFDS,[4FEF,[5GRG,[6HJJY,[]]],7TKU],8GRGRH]

list L2:
[3SFDS,[4FEF,[5GRG,[6HJJY,[]]],7TKU],8GRGRH]
is list L2 empty:0
list L2 length:3
list L2 depth:5
the index 0 of list L2 is : 3SFDS

insertGLNodeFront list L2:
[[3SFDS,[4FEF,[5GRG,[6HJJY,[]]],7TKU],8GRGRH],3SFDS,[4FEF,[5GRG,[6HJJY,[]]],7TKU],8GRGRH]

insertGLNodeTear list L2:
[[3SFDS,[4FEF,[5GRG,[6HJJY,[]]],7TKU],8GRGRH],3SFDS,[4FEF,[5GRG,[6HJJY,[]]],7TKU],8GRGRH,[3SFDS,[4FEF,[5GRG,[6HJJY,[]]],7TKU],8GRGRH]]

get glnode of index 0 of L2:
[3SFDS,[4FEF,[5GRG,[6HJJY,[]]],7TKU],8GRGRH]

get glnode of index 1 of L2:
3SFDS

get head of L2:
[3SFDS,[4FEF,[5GRG,[6HJJY,[]]],7TKU],8GRGRH]

get tear of L2:
[3SFDS,[4FEF,[5GRG,[6HJJY,[]]],7TKU],8GRGRH]

list L2:
[[3SFDS,[4FEF,[5GRG,[6HJJY,[]]],7TKU],8GRGRH],3SFDS,[4FEF,[5GRG,[6HJJY,[]]],7TKU],8GRGRH]
get tear of L2:
8GRGRH

list L2:
[[4FEF,[5GRG,[6HJJY,[]]],7TKU],8GRGRH]
get head of L2:
[4FEF,[5GRG,[6HJJY,[]]],7TKU]

list L3:
[[4FEF,[5GRG,[6HJJY,[]]],7TKU],8GRGRH]
insertGLNodeTear list L3:
[[4FEF,[5GRG,[6HJJY,[]]],7TKU],8GRGRH,[3SFDS,[4FEF,[5GRG,[6HJJY,[]]],7TKU],8GRGRH]]

insertGLNodeFront list L3:
[[4FEF,[5GRG,[6HJJY,[]]],7TKU],[4FEF,[5GRG,[6HJJY,[]]],7TKU],8GRGRH,[3SFDS,[4FEF,[5GRG,[6HJJY,[]]],7TKU],8GRGRH]]

get tear of L3:
[3SFDS,[4FEF,[5GRG,[6HJJY,[]]],7TKU],8GRGRH]

list L3:
[[4FEF,[5GRG,[6HJJY,[]]],7TKU],[4FEF,[5GRG,[6HJJY,[]]],7TKU],8GRGRH]

get tear of L3:
8GRGRH

list L3:
[[4FEF,[5GRG,[6HJJY,[]]],7TKU],[4FEF,[5GRG,[6HJJY,[]]],7TKU]]

get tear of L3:
[4FEF,[5GRG,[6HJJY,[]]],7TKU]

list L3:
[[4FEF,[5GRG,[6HJJY,[]]],7TKU]]

get tear of L3:
[4FEF,[5GRG,[6HJJY,[]]],7TKU]

list L3:

is list L3 empty:1

list L2:
[[4FEF,[5GRG,[6HJJY,[]]],7TKU],8GRGRH]

get head of L2:
[4FEF,[5GRG,[6HJJY,[]]],7TKU]

list L2:
[8GRGRH]

get head of L2:
8GRGRH

list L2:

is list L2 empty:1

node1 traversal
3SFDS, length :5
4FEF, length :4
5GRG, length :4
6HJJY, length :5
7TKU, length :4
8GRGRH, length :6

list L traversal
1D, length :2
2AD, length :3
3SFDS, length :5
4FEF, length :4
5GRG, length :4
6HJJY, length :5
7TKU, length :4
8GRGRH, length :6
9YJRDFB, length :7