广义表

// 广义表的头尾链表存储表示 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);     } }