1、數據Z構C語言版 廣義表的頭尾鏈表存儲表示.txtcopy （復制）別人的個性簽名，不叫抄襲,不叫沒主見，只不過是感覺對了。遇到過的事一樣罷了。/*數據Z構C語言版廣義表的頭尾鏈表存儲表示P109編譯環境：Dev-C+ 4.9.9.2日期： 2011 年 2 月 13 日*/#include <stdio.h>#include <malloc.h>#include <stdlib.h>#include <string.h>typedef char AtomType; / 定義原子類型為字符型typedef enumATOM, / ATOM=0:

2、原子LIST / LIST=1: 子表 ElemTag;/ 廣義表的頭尾鏈表存儲表示typedef struct GLNode ElemTag tag;/ 公共部分, 用于區分原子結點和表結點union/ 原子結點和表結點的聯合部分AtomType atom; / atom 是原子結點的值域, AtomType 由用戶定義struct struct GLNode *hp,*tp;ptr; / ptr 是表結點的指針域,prt.hp 和 ptr.tp 分別指向表頭和表尾a; *GList, GLNode; / 廣義表類型/ 創建空的廣義表Lint InitGList(GList *L)*L =

3、NULL;return 1;/ 銷毀廣義表Lvoid DestroyGList(GList *L) GList q1,q2;if(*L)if(*L)->tag = ATOM) free(*L); / 刪除原子結點*L = NULL;else / 是表結點，則應該刪除表頭和表尾結點q1 = (*L)->a.ptr.hp;q2 = (*L)->a.ptr.tp;free(*L);*L = NULL;/ 遞歸刪除表頭和表尾結點DestroyGList(&q1);DestroyGList(&q2);/ 算法 5.6 P115/ 采用頭尾鏈表存儲結構, 由廣義表L 復制

4、得到廣義表T。int CopyGList(GList *T,GList L)if(!L) / 為空，復制空表*T = NULL;else*T = (GList)malloc(sizeof(GLNode); /建表結點if(!*T)exit(0);(*T)->tag = L->tag;if(L->tag = ATOM)(*T)->a.atom = L->a.atom; / 復制單原子else / 是表結點，則依次復制表頭和表尾/ 復制廣義表L->ptr.hp的一個副本T->ptr.hpCopyGList(&(*T)->a.ptr.hp),

5、L->a.ptr.hp);/ 復制廣義表L->ptr.tp的一個副本T->ptr.tpCopyGList(&(*T)->a.ptr.tp), L->a.ptr.tp);return 1;/ 返回廣義表的長度, 即元素個數int GListLength(GList L) int len = 0;if(!L)return 0; if(L->tag = ATOM)return 1;while(L) L = L->a.ptr.tp;/ 根據表尾來判斷len+; return len;/ 算法 5.5 P114/ 采用頭尾鏈表存儲結構, 求廣義表L 的深

6、度。int GListDepth(GList L)int max, dep;GList pp;if(!L)return 1;/ 空表深度為1if(L->tag = ATOM)return 0;/ 原子深度為0for(max = 0, pp = L; pp; pp = pp->a.ptr.tp) / 遞歸求以pp->a.ptr.hp 為頭指針的子表深度dep = GListDepth(pp->a.ptr.hp);if(dep > max) max = dep; return max+1; / 非空表的深度是各元素的深度的最大值加1/ 判定廣義表是否為空 int GL

7、istEmpty(GList L)if(!L)return 1;elsereturn 0;/ 取廣義表L 的頭GList GetHead(GList L) GList h,p;if(!L)printf(" 空表無表頭!n");exit(0);p = L->a.ptr.tp;/ 保存表尾L->a.ptr.tp = NULL;CopyGList(&h,L);L->a.ptr.tp = p;/ 歸還表尾return h;/ 取廣義表L 的尾GList GetTail(GList L) GList t;if(!L)printf(" 空表無表尾!n

8、");exit(0);CopyGList(&t, L->a.ptr.tp);return t;/ 插入元素e 作為廣義表L 的第一元素( 表頭 , 也可能是子表)int InsertFirst_GL(GList *L,GList e)GList p = (GList)malloc(sizeof(GLNode);if(!p)exit(0);p->tag = LIST;p->a.ptr.hp = e;p->a.ptr.tp = *L;* L = p;return 1;/ 刪除廣義表L 的第一元素, 并用 e 返回其值int DeleteFirst_GL(G

9、List *L,GList *e)GList p;* e = (*L)->a.ptr.hp;/ 用 *e 返回表頭p = *L;* L = (*L)->a.ptr.tp;/ 將表尾當成表Lfree(p); / 刪除表頭return 1;/ 利用遞歸算法遍歷廣義表Lvoid Traverse_GL(GList L,void(*v)(AtomType)if(L) / L 不空if(L->tag = ATOM) / L 為單原子v(L->a.atom);else / L 為廣義表Traverse_GL(L->a.ptr.hp,v);Traverse_GL(L->a

10、.ptr.tp,v);/ 串的定長順序存儲表示#define MAXSTRLEN 40 / 用戶可在255 以內定義最大串長(1 個字節)typedef char SStringMAXSTRLEN+1; / 0 號單元存放串的當前長度/ 生成一個其值等于chars 的串 Tint StrAssign(SString T,char *chars)int i;if(strlen(chars) > MAXSTRLEN)return 0;elseT0 = strlen(chars);/ 記錄長度/ 一個一個的拷貝, 字符串結束符也拷貝了for(i = 1; i <= T0; i+)Ti =

11、 *(chars + i - 1);return 1;/ 由串 S 復制得串Tint StrCopy(SString T, SString S) int i;/ 一個一個的拷貝for(i = 0; i <= S0; i+)Ti = Si;return 1;/ 若 S 為空串 , 則返回 1, 否則返回0int StrEmpty(SString S)if(S0 = 0)return 1;elsereturn 0;/若S>T,則返回值>0；若S=T,則返回值=0；若S<T,則返回值<0 int StrCompare(SString S,SString T)int i；

12、for(i = 1； i <= S0 && i <= T0； +i)if(Si != Ti)return Si - Ti；return S0-T0；/ 返回串的元素個數int StrLength(SString S)return S0；/ 將 S 清為空串int ClearString(SString S)S0 = 0；return 1；/ 令串長為零/ 算法 4.3 P74/用Sub返回串S的第pos個字符起長度為len的子串。int SubString(SString Sub,SString S,int pos,int len)int i;if(pos <

13、 1 | pos >S0 | len < 0 | len > S0-pos+1)return 0;for(i = 1; i <= len; i+)Subi=Spos+i-1;Sub0 = len;return 1;/ 算法 5.8 P117/ 將非空串str 分割成兩部分:hsub 為第一個',' 之前的子串,str 為之后的子串void sever(SString str,SString hstr)int n,i,k; / k 記尚未配對的左括號個數SString ch,c1,c2,c3;n = StrLength(str);StrAssign(c1,

14、",");StrAssign(c2,"(");StrAssign(c3,")");SubString(ch,str,1,1);/ 搜索最外層的第一個逗號for(i = 1,k = 0;i <= n && StrCompare(ch,c1) | k != 0; +i)SubString(ch, str, i, 1);if(!StrCompare(ch, c2)+k;else if(!StrCompare(ch,c3)-k;if(i <= n)SubString(hstr, str, 1, i-2);SubSt

15、ring(str, str, i, n - i + 1); elseStrCopy(hstr, str);ClearString(str);/ 算法 5.7 P117/采用頭尾鏈表存儲結構，由廣義表的書寫形式串S(即類似(,()創建/ 廣義表L。設emp="()"int CreateGList(GList *L, SString S)SString sub,hsub,emp;GList p,q;StrAssign(emp,"()");if(!StrCompare(S, emp)*L = NULL; / 創建空表else*L = (GList)malloc

16、(sizeof(GLNode);if(!*L)/ 建表結點exit(0);if(StrLength(S) = 1)/ S 為單原子(*L)->tag = ATOM;(*L)->a.atom = S1; / 創建單原子廣義表 else(*L)->tag = LIST;p = *L;SubString(sub, S, 2, StrLength(S)-2); /脫外層括號do/ 重復建 n 個子表sever(sub, hsub); / 從 sub 中分離出表頭串hsubCreateGList(&p->a. ptr. hp, hsub);q = p;if(!StrEmp

17、ty(sub) / 表尾不空p = (GLNode *)malloc(sizeof(GLNode);if(!p)exit(0);p->tag = LIST;q->a.ptr.tp = p;while(!StrEmpty(sub);q->a.ptr.tp = NULL;return 1;/ 打印原子void visit(AtomType e)printf("%c ", e);int main()/ 廣義表的表示形式是，空表:(), 單原子 :a, 表 :(a,(b),c,(d,(e)char p80 = "(a,(b),c,(d,(e)"

18、SString t;GList L,m;InitGList(&L);InitGList(&m);printf(" 空廣義表L的深度=%dnL是否空？ d(1:是0:否)nn", GListDepth(L), GListEmpty(L);StrAssign(t, p);/ 創建廣義表CreateGList(&L, t);printf("n 廣義表 L 的長度 = %dn", GListLength(L);printf(" 廣義表 L 的深度 = %d nL 是否空？%d(1: 是 0: 否 )n",GListDe

19、pth(L), GListEmpty(L);printf(" 遍歷廣義表L： n");Traverse_GL(L, visit);printf("nn 復制廣義表m = Ln");CopyGList(&m, L);printf(" 廣義表 m 的長度=%dn", GListLength(m);printf(" 廣義表 m 的深度=%dn", GListDepth(m);printf(" 遍歷廣義表m： n");Traverse_GL(m,visit);/ 重復用的時候記得銷毀，相當于初始化DestroyGList(&m);m = GetHead(L);printf("nnm 是L的表頭，遍歷廣義表 m： n");Traverse_GL(m, visit