广义表

存储结构

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

基本操作

1 // 广义表的头尾链表存储的基本操作(11个)  2 #include"func5-1.c"  3 void InitGList(GList *L) {  4     // 创建空的广义表L  5     *L = NULL;  6 }  7   8 void CreateGList(GList *L, SString S) {  9     // 采用头尾链表存储结构，由广义表的书写形式串S创建广义表L。设emp="()" 10     SString sub, hsub, emp; 11     GList p, q; 12     StrAssign(emp, "()"); // 空串emp="()" 13     if (!StrCompare(S, emp)) // S="()" 14         *L = NULL; // 创建空表 15     else { // S不是空串 16         *L = (GList)malloc(sizeof(GLNode)); 17         if (!*L) // 建表结点 18             exit(OVERFLOW); 19         if (StrLength(S) == 1) { 20             // S为单原子，只会出现在递归调用中 21             (*L)->tag = ATOM; 22             (*L)->a.atom = S[1]; // 创建单原子广义表 23         } else { // S为表 24             (*L)->tag = LIST; 25             p = *L; 26             SubString(sub, S, 2, StrLength(S) - 2); 27             // 脱外层括号(去掉第1个字符和最后1个字符)给串sub 28             do { 29                 // 重复建n个子表 30                 sever(sub, hsub); // 从sub中分离出表头串hsub 31                 CreateGList(&p->a.ptr.hp, hsub); 32                 q = p; 33                 if (!StrEmpty(sub)) { // 表尾不空 34                     p = (GLNode *)malloc(sizeof(GLNode)); 35                     if (!p) 36                         exit(OVERFLOW); 37                     p->tag = LIST; 38                     q->a.ptr.tp = p; 39                 } 40             } while (!StrEmpty(sub)); 41             q->a.ptr.tp = NULL; 42         } 43     } 44 } 45 void DestroyGList(GList *L) { 46     // 销毁广义表L 47     GList q1, q2; 48     if (*L) { 49         if ((*L)->tag == LIST) { // 删除表结点 50             q1 = (*L)->a.ptr.hp; // q1指向表头 51             q2 = (*L)->a.ptr.tp; // q2指向表尾 52             DestroyGList(&q1); // 销毁表头 53             DestroyGList(&q2); // 销毁表尾 54         } 55         free(*L); 56         *L = NULL; 57     } 58 } 59  60 void CopyGList(GList *T, GList L) { 61     // 采用头尾链表存储结构，由广义表L复制得到广义表T 62     if (!L) // 复制空表 63         *T = NULL; 64     else { 65         *T = (GList)malloc(sizeof(GLNode)); 66         // 建表结点 67         if (!*T) 68             exit(OVERFLOW); 69         (*T)->tag = L->tag; 70         if (L->tag == ATOM) 71             (*T)->a.atom = L->a.atom; // 复制单原子 72         else { 73             CopyGList(&((*T)->a.ptr.hp), L->a.ptr.hp); 74             // 递归复制子表 75             CopyGList(&((*T)->a.ptr.tp), L->a.ptr.tp); 76         } 77     } 78 } 79  80 int GListLength(GList L) { 81     /* 返回广义表的长度，即元素个数*/ 82     int len = 0; 83     while (L) { 84         L = L->a.ptr.tp; 85         len++; 86     } 87     return len; 88 } 89  90 int GListDepth(GList L) { 91     /* 采用头尾链表存储结构，求广义表L的深度。*/ 92     int max, dep; 93     GList pp; 94     if (!L) 95         return 1; /* 空表深度为1 */ 96     if (L->tag == ATOM) 97         return 0; /* 原子深度为0，只会出现在递归调用中*/ 98     for (max = 0, pp = L; pp; pp = pp->a.ptr.tp) { 99         dep = GListDepth(pp->a.ptr.hp); /* 递归求以pp->a.ptr.hp为头指针的子表深度*/100         if (dep > max)101             max = dep;102     }103     return max + 1; /* 非空表的深度是各元素的深度的最大值加1 */104 }105 106 Status GListEmpty(GList L) {107     /* 判定广义表是否为空*/108     if (!L)109         return TRUE;110     else111         return FALSE;112 }113 114 GList GetHead(GList L) {115     /* 生成广义表L的表头元素，返回指向这个元素的指针*/116     GList h, p;117     if (!L) /* 空表无表头*/118         return NULL;119     p = L->a.ptr.hp; /* p指向L的表头元素*/120     CopyGList(&h, p); /* 将表头元素复制给h */121     return h;122 }123 124 GList GetTail(GList L) {125     /* 将广义表L的表尾生成为广义表，返回指向这个新广义表的指针*/126     GList t;127     if (!L) /* 空表无表尾*/128         return NULL;129     CopyGList(&t, L->a.ptr.tp); /* 将L的表尾拷给t */130     return t;131 }132 133 void InsertFirst_GL(GList *L, GList e) {134     /* 初始条件：广义表存在。操作结果：插入元素e(也可能是子表)作为广义表L的第1元素(表头) */135     GList p = (GList)malloc(sizeof(GLNode)); /* 生成新结点*/136     if (!p)137         exit(OVERFLOW);138     p->tag = LIST; /* 结点的类型是表*/139     p->a.ptr.hp = e; /* 表头指向e */140     p->a.ptr.tp = *L; /* 表尾指向原表L */141     *L = p; /* L指向新结点*/142 }143 144 void DeleteFirst_GL(GList *L, GList *e) {145     // 初始条件：广义表L存在。操作结果：删除广义表L的第一元素，并用e返回其值146     GList p = *L; // p指向第1个结点147     *e = (*L)->a.ptr.hp; // e指向L的表头148     *L = (*L)->a.ptr.tp; // L指向原L的表尾149     free(p); // 释放第1个结点150 }151 152 void Traverse_GL(GList L, void(*v)(AtomType)) {153     // 利用递归算法遍历广义表L154     if (L) // L不空155         if (L->tag == ATOM) // L为单原子156             v(L->a.atom);157         else { // L为广义表158             Traverse_GL(L->a.ptr.hp, v);159             // 递归遍历L的表头160             Traverse_GL(L->a.ptr.tp, v);161             // 递归遍历L的表尾162         }163 }

存储结构

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

基本操作

1 // 广义表的扩展线性链表存储(的基本操作(13个)  2 #include"func5-1.c"  3   4 void InitGList(GList1 *L) {  5     // 创建空的广义表L  6     *L = NULL;  7 }  8   9 void CreateGList(GList1 *L, SString S) { 10     // 采用扩展线性链表存储结构，由广义表的书写形式串S创建广义表L。设emp="()" 11     SString emp, sub, hsub; 12     GList1 p; 13     StrAssign(emp, "()"); /* 设emp="()" */ 14     *L = (GList1)malloc(sizeof(GLNode1)); 15     if (!*L) /* 建表结点不成功*/ 16         exit(OVERFLOW); 17     if (!StrCompare(S, emp)) { /* 创建空表*/ 18         (*L)->tag = LIST; 19         (*L)->a.hp = (*L)->tp = NULL; 20     } else if (StrLength(S) == 1) { /* 创建单原子广义表*/ 21         (*L)->tag = ATOM; 22         (*L)->a.atom = S[1]; 23         (*L)->tp = NULL; 24     } else { /* 创建一般表*/ 25         (*L)->tag = LIST; 26         (*L)->tp = NULL; 27         SubString(sub, S, 2, StrLength(S) - 2); 28         // 脱外层括号(去掉第1个字符和最后1个字符)给串sub 29         sever(sub, hsub); // 从sub中分离出表头串hsub 30         CreateGList(&(*L)->a.hp, hsub); 31         p = (*L)->a.hp; 32         while (!StrEmpty(sub)) { // 表尾不空，则重复建n个子表 33             sever(sub, hsub); // 从sub中分离出表头串hsub 34             CreateGList(&p->tp, hsub); 35             p = p->tp; 36         }; 37     } 38 } 39  40 void DestroyGList(GList1 *L) { 41     /* 初始条件：广义表L存在。操作结果：销毁广义表L */ 42     GList1 ph, pt; 43     if (*L) { /* L不为空表*/ 44         /* 由ph和pt接替L的两个指针*/ 45         if ((*L)->tag) /* 是子表*/ 46             ph = (*L)->a.hp; 47         else /* 是原子*/ 48             ph = NULL; 49         pt = (*L)->tp; 50         DestroyGList(&ph); /* 递归销毁表ph */ 51         DestroyGList(&pt); /* 递归销毁表pt */ 52         free(*L); /* 释放L所指结点*/ 53         *L = NULL; /* 令L为空*/ 54     } 55 } 56  57 void CopyGList(GList1 *T, GList1 L) { 58     /* 初始条件：广义表L存在。操作结果：由广义表L复制得到广义表T */ 59     *T = NULL; 60     if (L) { /* L不空*/ 61         *T = (GList1)malloc(sizeof(GLNode1)); 62         if (!*T) 63             exit(OVERFLOW); 64         (*T)->tag = L->tag; /* 复制枚举变量*/ 65         if (L->tag == ATOM) /* 复制共用体部分*/ 66             (*T)->a.atom = L->a.atom; /* 复制单原子*/ 67         else 68             CopyGList(&(*T)->a.hp, L->a.hp); /* 复制子表*/ 69         if (L->tp == NULL) /* 到表尾*/ 70             (*T)->tp = L->tp; 71         else 72             CopyGList(&(*T)->tp, L->tp); /* 复制子表*/ 73     } 74 } 75  76 int GListLength(GList1 L) { 77     /* 初始条件：广义表L存在。操作结果：求广义表L的长度，即元素个数*/ 78     int len = 0; 79     GList1 p = L->a.hp; /* p指向第1个元素*/ 80     while (p) { 81         len++; 82         p = p->tp; 83     }; 84     return len; 85 } 86  87 int GListDepth(GList1 L) { 88     /* 初始条件：广义表L存在。操作结果：求广义表L的深度*/ 89     int max, dep; 90     GList1 pp; 91     if (L == NULL || L->tag == LIST && !L->a.hp) 92         return 1; /* 空表深度为1 */ 93     else if (L->tag == ATOM) 94         return 0; /* 单原子表深度为0，只会出现在递归调用中*/ 95     else /* 求一般表的深度*/ 96         for (max = 0, pp = L->a.hp; pp; pp = pp->tp) { 97             dep = GListDepth(pp); /* 求以pp为头指针的子表深度*/ 98             if (dep > max) 99                 max = dep;100         }101     return max + 1; /* 非空表的深度是各元素的深度的最大值加1 */102 }103 104 Status GListEmpty(GList1 L) {105     /* 初始条件：广义表L存在。操作结果：判定广义表L是否为空*/106     if (!L || L->tag == LIST && !L->a.hp)107         return OK;108     else109         return ERROR;110 }111 112 GList1 GetHead(GList1 L) {113     /* 生成广义表L的表头元素，返回指向这个元素的指针*/114     GList1 h, p;115     if (!L || L->tag == LIST && !L->a.hp) /* 空表无表头*/116         return NULL;117     p = L->a.hp->tp; /* p指向L的表尾*/118     L->a.hp->tp = NULL; /* 截去L的表尾部分*/119     CopyGList(&h, L->a.hp); /* 将表头元素复制给h */120     L->a.hp->tp = p; /* 恢复L的表尾(保持原L不变) */121     return h;122 }123 124 GList1 GetTail(GList1 L) {125     // 将广义表L的表尾生成为广义表，返回指向这个新广义表的指针126     GList1 t, p;127     if (!L || L->tag == LIST && !L->a.hp) // 空表无表尾128         return NULL;129     p = L->a.hp; // p指向表头130     L->a.hp = p->tp; // 在L中删去表头131     CopyGList(&t, L); // 将L的表尾拷给t132     L->a.hp = p; // 恢复L的表头(保持原L不变)133     return t;134 }135 136 void InsertFirst_GL(GList1 *L, GList1 e) {137     // 初始条件：广义表存在。操作结果：插入元素e(也可能是子表)作为广义表L的第1元素(表头)138     GList1 p = (*L)->a.hp;139     (*L)->a.hp = e;140     e->tp = p;141 }142 143 void DeleteFirst_GL(GList1 *L, GList1 *e) {144     // 初始条件：广义表L存在。操作结果：删除广义表L的第一元素，并用e返回其值145     if (*L && (*L)->a.hp) {146         *e = (*L)->a.hp;147         (*L)->a.hp = (*e)->tp;148         (*e)->tp = NULL;149     } else150         *e = *L;151 }152 153 void Traverse_GL(GList1 L, void(*v)(AtomType)) {154     // 利用递归算法遍历广义表L155     GList1 hp;156     if (L) { // L不空157         if (L->tag == ATOM) { // L为单原子158             v(L->a.atom);159             hp = NULL;160         } else // L为子表161             hp = L->a.hp;162         Traverse_GL(hp, v);163         Traverse_GL(L->tp, v);164     }165 }