廣義表

廣義表是一種非線性的資料結構。但如果廣義表的每個元素都是原子，它就變成了線性表。廣義表廣泛地用於人工智慧等領域的LISP語言。廣義表一般記作 LS = (a1, a2, ···, an), n是它的長度，ai可以是單個元素(原子)，也可以是廣義表(子表)，當廣義表非空時，稱第一個元素a1為LS的表頭，稱其餘元素組成的表為LS的表尾。注意：表頭是元素(可以是原子，也可以是廣表)，表尾一定是廣義表。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個)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)-&gt;tag = ATOM;(*L)-&gt;a.atom = S[1]; // 建立單原子廣義表} else { // S為表(*L)-&gt;tag = LIST;p = *L;SubString(sub, S, 2, StrLength(S) - 2);// 脫外層括號(去掉第1個字元和最後1個字元)給串subdo {// 重複建n個子表sever(sub, hsub); // 從sub中分離出表頭串hsubCreateGList(&amp;p-&gt;a.ptr.hp, hsub);q = p;if (!StrEmpty(sub)) { // 表尾不空p = (GLNode *)malloc(sizeof(GLNode));if (!p)exit(OVERFLOW);p-&gt;tag = LIST;q-&gt;a.ptr.tp = p;} while (!StrEmpty(sub));q-&gt;a.ptr.tp = NULL;void DestroyGList(GList *L) {// 銷燬廣義表LGList q1, q2;if (*L) {if ((*L)-&gt;tag == LIST) { // 刪除表結點q1 = (*L)-&gt;a.ptr.hp; // q1指向表頭q2 = (*L)-&gt;a.ptr.tp; // q2指向表尾DestroyGList(&amp;q1); // 銷燬表頭DestroyGList(&amp;q2); // 銷燬表尾free(*L);*L = NULL;void CopyGList(GList *T, GList L) {// 採用頭尾連結串列儲存結構，由廣義表L複製得到廣義表Tif (!L) // 複製空表*T = NULL;else {*T = (GList)malloc(sizeof(GLNode));// 建表結點if (!*T)exit(OVERFLOW);(*T)-&gt;tag = L-&gt;tag;if (L-&gt;tag == ATOM)(*T)-&gt;a.atom = L-&gt;a.atom; // 複製單原子else {CopyGList(&amp;((*T)-&gt;a.ptr.hp), L-&gt;a.ptr.hp);// 遞迴複製子表CopyGList(&amp;((*T)-&gt;a.ptr.tp), L-&gt;a.ptr.tp);int GListLength(GList L) {/* 返回廣義表的長度，即元素個數 */int len = 0;while (L) {L = L-&gt;a.ptr.tp;len++;return len;int GListDepth(GList L) {/* 採用頭尾連結串列儲存結構，求廣義表L的深度。*/int max, dep;GList pp;if (!L)return 1; /* 空表深度為1 */if (L-&gt;tag == ATOM)return 0; /* 原子深度為0，只會出現在遞迴呼叫中 */for (max = 0, pp = L; pp; pp = pp-&gt;a.ptr.tp) {dep = GListDepth(pp-&gt;a.ptr.hp); /* 遞迴求以pp-&gt;a.ptr.hp為頭指標的子表深度 */if (dep &gt; max)max = dep;return max + 1; /* 非空表的深度是各元素的深度的最大值加1 */Status GListEmpty(GList L) {/* 判定廣義表是否為空 */if (!L)return TRUE;elsereturn FALSE;GList GetHead(GList L) {/* 生成廣義表L的表頭元素，返回指向這個元素的指標 */GList h, p;if (!L) /* 空表無表頭 */return NULL;p = L-&gt;a.ptr.hp; /* p指向L的表頭元素 */CopyGList(&amp;h, p); /* 將表頭元素複製給h */return h;GList GetTail(GList L) {/* 將廣義表L的表尾生成為廣義表，返回指向這個新廣義表的指標 */GList t;if (!L) /* 空表無表尾 */return NULL;CopyGList(&amp;t, L-&gt;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-&gt;tag = LIST; /* 結點的型別是表 */p-&gt;a.ptr.hp = e; /* 表頭指向e */p-&gt;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)-&gt;a.ptr.hp; // e指向L的表頭*L = (*L)-&gt;a.ptr.tp; // L指向原L的表尾free(p); // 釋放第1個結點void Traverse_GL(GList L, void(*v)(AtomType)) {// 利用遞迴演算法遍歷廣義表Lif (L) // L不空if (L-&gt;tag == ATOM) // L為單原子v(L-&gt;a.atom);else { // L為廣義表Traverse_GL(L-&gt;a.ptr.hp, v);// 遞迴遍歷L的表頭Traverse_GL(L-&gt;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個)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)-&gt;tag = LIST;(*L)-&gt;a.hp = (*L)-&gt;tp = NULL;} else if (StrLength(S) == 1) { /* 建立單原子廣義表 */(*L)-&gt;tag = ATOM;(*L)-&gt;a.atom = S[1];(*L)-&gt;tp = NULL;} else { /* 建立一般表 */(*L)-&gt;tag = LIST;(*L)-&gt;tp = NULL;SubString(sub, S, 2, StrLength(S) - 2);// 脫外層括號(去掉第1個字元和最後1個字元)給串subsever(sub, hsub); // 從sub中分離出表頭串hsubCreateGList(&amp;(*L)-&gt;a.hp, hsub);p = (*L)-&gt;a.hp;while (!StrEmpty(sub)) { // 表尾不空，則重複建n個子表sever(sub, hsub); // 從sub中分離出表頭串hsubCreateGList(&amp;p-&gt;tp, hsub);p = p-&gt;tp;void DestroyGList(GList1 *L) {/* 初始條件：廣義表L存在。操作結果：銷燬廣義表L */GList1 ph, pt;if (*L) { /* L不為空表 *//* 由ph和pt接替L的兩個指標 */if ((*L)-&gt;tag) /* 是子表 */ph = (*L)-&gt;a.hp;else /* 是原子 */ph = NULL;pt = (*L)-&gt;tp;DestroyGList(&amp;ph); /* 遞迴銷燬表ph */DestroyGList(&amp;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)-&gt;tag = L-&gt;tag; /* 複製列舉變數 */if (L-&gt;tag == ATOM) /* 複製共用體部分 */(*T)-&gt;a.atom = L-&gt;a.atom; /* 複製單原子 */elseCopyGList(&amp;(*T)-&gt;a.hp, L-&gt;a.hp); /* 複製子表 */if (L-&gt;tp == NULL) /* 到表尾 */(*T)-&gt;tp = L-&gt;tp;elseCopyGList(&amp;(*T)-&gt;tp, L-&gt;tp); /* 複製子表 */int GListLength(GList1 L) {/* 初始條件：廣義表L存在。操作結果：求廣義表L的長度，即元素個數 */int len = 0;GList1 p = L-&gt;a.hp; /* p指向第1個元素 */while (p) {len++;p = p-&gt;tp;return len;int GListDepth(GList1 L) {/* 初始條件：廣義表L存在。操作結果：求廣義表L的深度 */int max, dep;GList1 pp;if (L == NULL || L-&gt;tag == LIST &amp;&amp; !L-&gt;a.hp)return 1; /* 空表深度為1 */else if (L-&gt;tag == ATOM)return 0; /* 單原子表深度為0，只會出現在遞迴呼叫中 */else /* 求一般表的深度 */for (max = 0, pp = L-&gt;a.hp; pp; pp = pp-&gt;tp) {dep = GListDepth(pp); /* 求以pp為頭指標的子表深度 */if (dep &gt; max)max = dep;return max + 1; /* 非空表的深度是各元素的深度的最大值加1 */Status GListEmpty(GList1 L) {/* 初始條件：廣義表L存在。操作結果：判定廣義表L是否為空 */if (!L || L-&gt;tag == LIST &amp;&amp; !L-&gt;a.hp)return OK;elsereturn ERROR;GList1 GetHead(GList1 L) {/* 生成廣義表L的表頭元素，返回指向這個元素的指標 */GList1 h, p;if (!L || L-&gt;tag == LIST &amp;&amp; !L-&gt;a.hp) /* 空表無表頭 */return NULL;p = L-&gt;a.hp-&gt;tp; /* p指向L的表尾 */L-&gt;a.hp-&gt;tp = NULL; /* 截去L的表尾部分 */CopyGList(&amp;h, L-&gt;a.hp); /* 將表頭元素複製給h */L-&gt;a.hp-&gt;tp = p; /* 恢復L的表尾(保持原L不變) */return h;GList1 GetTail(GList1 L) {// 將廣義表L的表尾生成為廣義表，返回指向這個新廣義表的指標GList1 t, p;if (!L || L-&gt;tag == LIST &amp;&amp; !L-&gt;a.hp) // 空表無表尾return NULL;p = L-&gt;a.hp; // p指向表頭L-&gt;a.hp = p-&gt;tp; // 在L中刪去表頭CopyGList(&amp;t, L); // 將L的表尾拷給tL-&gt;a.hp = p; // 恢復L的表頭(保持原L不變)return t;void InsertFirst_GL(GList1 *L, GList1 e) {// 初始條件：廣義表存在。操作結果：插入元素e(也可能是子表)作為廣義表L的第1元素(表頭)GList1 p = (*L)-&gt;a.hp;(*L)-&gt;a.hp = e;e-&gt;tp = p;void DeleteFirst_GL(GList1 *L, GList1 *e) {// 初始條件：廣義表L存在。操作結果：刪除廣義表L的第一元素，並用e返回其值if (*L &amp;&amp; (*L)-&gt;a.hp) {*e = (*L)-&gt;a.hp;(*L)-&gt;a.hp = (*e)-&gt;tp;(*e)-&gt;tp = NULL;} else*e = *L;void Traverse_GL(GList1 L, void(*v)(AtomType)) {// 利用遞迴演算法遍歷廣義表LGList1 hp;if (L) { // L不空if (L-&gt;tag == ATOM) { // L為單原子v(L-&gt;a.atom);hp = NULL;} else // L為子表hp = L-&gt;a.hp;Traverse_GL(hp, v);Traverse_GL(L-&gt;tp, v);