【数据结构】广义表

  1 #include <stdio.h>  
  2 #include <malloc.h>  
  3 #include <stdlib.h>  
  4 #include <string.h>  
  5 #define MAXSTRLEN 40 ）  
  6 typedef char SString[MAXSTRLEN+1];   
  7 typedef char AtomType;                     // 定义原子类型为字符型    
  8 typedef enum{  
  9     ATOM, LIST                            // ATOM==0:原子 LIST==1:子表                       
 10 } ElemTag;   
 11   
 12 typedef struct GLNode  
 13 {  
 14     ElemTag tag;                // 公共部分,用于区分原子结点和表结点   
 15     union                               // 原子结点和表结点的联合部分   
 16     {  
 17         AtomType atom;                      // atom是原子结点的值域, AtomType由用户定义   
 18         struct  
 19         {  
 20             struct GLNode *hp,*tp;  
 21         }ptr;                                // ptr是表结点的指针域,prt.hp和ptr.tp分别指向表头和表尾   
 22     }a;  
 23 } *GList, GLNode;     
 24   
 25   
 26 //初始化的广义表L  
 27 int InitGList(GList *L)  
 28 {   
 29     *L = NULL;  
 30     return 1;  
 31 }  
 32   
 33 //销毁广义表L  
 34 void DestroyGList(GList *L)   
 35 {   
 36     GList q1,q2;  
 37     if(*L)  
 38     {  
 39         if((*L)->tag == ATOM)  
 40         {  
 41             free(*L);                                 
 42             *L = NULL;  
 43         }  
 44         else      
 45         {  
 46             q1 = (*L)->a.ptr.hp;  
 47             q2 = (*L)->a.ptr.tp;  
 48             free(*L);  
 49             *L = NULL;  
 50             DestroyGList(&q1);  
 51             DestroyGList(&q2);                      // 递归删除表头和表尾结点  
 52           
 53         }  
 54     }  
 55 }  
 56   
 57   
 58 // 采用头尾链表存储结构,由广义表L复制得到广义表T。   
 59 int CopyGList(GList *T,GList L)  
 60 {  
 61     if(!L)  
 62         *T = NULL;  
 63     else  
 64     {  
 65         *T = (GList)malloc(sizeof(GLNode));   
 66         if(!*T)  
 67             exit(0);  
 68         (*T)->tag = L->tag;  
 69         if(L->tag == ATOM)  
 70             (*T)->a.atom = L->a.atom;                             // 复制单原子   
 71         else                                                // 是表结点，则依次复制表头和表尾  
 72         {  
 73             CopyGList(&((*T)->a.ptr.hp), L->a.ptr.hp);  
 74             CopyGList(&((*T)->a.ptr.tp), L->a.ptr.tp);  
 75                                                           
 76               
 77         }  
 78     }  
 79     return 1;  
 80 }  
 81   
 82 // 返回广义表的长度,即元素个数  
 83 int GListLength(GList L)  
 84 {  
 85     int len = 0;  
 86     if(!L)  
 87         return 0;  
 88     if(L->tag == ATOM)  
 89         return 1;  
 90     while(L)  
 91     {  
 92         L = L->a.ptr.tp;   
 93         len++;  
 94     }  
 95     return len;  
 96 }  
 97   
 98   
 99 // 采用头尾链表存储结构,求广义表L的深度。  
100 int GListDepth(GList L)  
101 {  
102     int max, dep;  
103     GList pp;  
104       
105     if(!L)  
106         return 1;                                                                   // 空表深度为1  
107     if(L->tag == ATOM)  
108         return 0;                                                                           // 原子深度为0  
109     for(max = 0, pp = L; pp; pp = pp->a.ptr.tp)  
110     {  
111                                                                                     // 递归求以pp->a.ptr.hp为头指针的子表深度   
112         dep = GListDepth(pp->a.ptr.hp);  
113         if(dep > max)  
114             max = dep;  
115     }  
116     return max+1;                                                           // 非空表的深度是各元素的深度的最大值加1   
117 }  
118   
119 // 判定广义表是否为空  
120 int GListEmpty(GList L)  
121 {  
122     if(!L)  
123         return 1;  
124     else  
125         return 0;  
126 }  
127   
128 // 取广义表L的头  
129 GList GetHead(GList L)  
130 {  
131     GList h,p;  
132   
133     if(!L)  
134     {  
135         printf("空表无表头!
");  
136         exit(0);  
137     }  
138     p = L->a.ptr.tp;   
139     L->a.ptr.tp = NULL;  
140     CopyGList(&h,L);  
141     L->a.ptr.tp = p;  
142     return h;  
143 }  
144   
145 // 取广义表L的尾  
146 GList GetTail(GList L)  
147 {  
148     GList t;  
149     if(!L)  
150     {  
151         printf("空表无表尾!
");  
152         exit(0);  
153     }  
154     CopyGList(&t, L->a.ptr.tp);  
155     return t;  
156 }  
157   
158   
159   
160 // 插入元素e作为广义表L的第一元素(表头,也可能是子表)   
161 int InsertFirst_GL(GList *L,GList e)  
162 {  
163     GList p = (GList)malloc(sizeof(GLNode));  
164     if(!p)  
165         exit(0);  
166     p->tag = LIST;  
167     p->a.ptr.hp = e;  
168     p->a.ptr.tp = *L;  
169     *L = p;  
170     return 1;  
171 }  
172   
173   
174   
175 // 删除广义表L的第一元素,并用e返回其值  
176 int DeleteFirst_GL(GList *L,GList *e)  
177 {   
178     GList p;  
179     *e = (*L)->a.ptr.hp;   
180     p = *L;  
181     *L = (*L)->a.ptr.tp;   
182     free(p);  
183     return 1;  
184 }  
185   
186   
187   
188 // 利用递归算法遍历广义表L   
189 void Traverse_GL(GList L,void(*v)(AtomType))  
190 {  
191     if(L)   
192         if(L->tag == ATOM)  
193             v(L->a.atom);  
194         else  
195         {  
196             Traverse_GL(L->a.ptr.hp,v);  
197             Traverse_GL(L->a.ptr.tp,v);  
198         }  
199 }  
200   
201 // 生成一个其值等于chars的串T  
202 int StrAssign(SString T,char *chars)  
203 {   
204     int i;  
205     if(strlen(chars) > MAXSTRLEN)  
206         return 0;  
207     else  
208     {  
209         T[0] = strlen(chars);  
210          for(i = 1; i <= T[0]; i++)  
211             T[i] = *(chars + i - 1);  
212         return 1;  
213     }  
214 }  
215   
216 // 由串S复制得串T  
217 int StrCopy(SString T, SString S)  
218 {  
219     int i;  
220     for(i = 0; i <= S[0]; i++)  
221         T[i] = S[i];  
222     return 1;  
223 }  
224   
225   
226 // 若S为空串,则返回1,否则返回0   
227 int StrEmpty(SString S)  
228 {  
229     if(S[0] == 0)  
230         return 1;  
231     else  
232         return 0;  
233 }  
234   
235   
236   
237 // 若S>T,则返回值>0;若S=T,则返回值=0;若S<T,则返回值<0   
238 int StrCompare(SString S,SString T)  
239 {  
240     int i;  
241     for(i = 1; i <= S[0] && i <= T[0]; ++i)  
242         if(S[i] != T[i])  
243             return S[i] - T[i];  
244     return S[0]-T[0];  
245 }  
246   
247 // 返回串的元素个数  
248 int StrLength(SString S)  
249 {  
250     return S[0];  
251 }  
252   
253 // 将S清为空串  
254 int ClearString(SString S)  
255 {  
256     S[0] = 0;   // 令串长为零  
257     return 1;  
258 }  
259   
260   
261 // 用Sub返回串S的第pos个字符起长度为len的子串。  
262 int SubString(SString Sub,SString S,int pos,int len)  
263 {   
264     int i;  
265     if(pos < 1 || pos >S[0] || len < 0 || len > S[0]-pos+1)  
266         return 0;  
267     for(i = 1; i <= len; i++)  
268         Sub[i]=S[pos+i-1];  
269     Sub[0] = len;  
270     return 1;  
271 }  
272   
273   
274 // 将非空串str分割成两部分:hsub为第一个','之前的子串,str为之后的子串   
275 void sever(SString str,SString hstr)   
276 {  
277     int n,i, k;    
278     SString ch,c1,c2,c3;  
279     n = StrLength(str);  
280     StrAssign(c1,",");  
281     StrAssign(c2,"(");  
282     StrAssign(c3,")");  
283     SubString(ch,str,1,1);  
284     for(i = 1,k = 0;i <= n && StrCompare(ch,c1) || k != 0; ++i)  
285     {   
286         SubString(ch, str, i, 1);  
287         if(!StrCompare(ch, c2))  
288             ++k;  
289         else if(!StrCompare(ch,c3))  
290             --k;  
291     }  
292     if(i <= n)  
293     {  
294         SubString(hstr, str, 1, i-2);  
295         SubString(str, str, i, n - i + 1);  
296     }  
297     else  
298     {  
299         StrCopy(hstr, str);  
300         ClearString(str);  
301     }  
302 }  
303   
304   
305 // 广义表L。设emp="()"   
306 int CreateGList(GList *L, SString S)  
307 {  
308     SString sub,hsub,emp;  
309     GList p,q;  
310       
311     StrAssign(emp,"()");  
312     if(!StrCompare(S, emp))  
313         *L = NULL;  // 创建空表   
314     else  
315     {  
316         *L = (GList)malloc(sizeof(GLNode));  
317         if(!*L)     // 建表结点   
318             exit(0);  
319         if(StrLength(S) == 1)   // S为单原子   
320         {  
321             (*L)->tag = ATOM;  
322             (*L)->a.atom = S[1]; // 创建单原子广义表   
323         }  
324         else  
325         {  
326             (*L)->tag = LIST;  
327             p = *L;  
328             SubString(sub, S, 2, StrLength(S)-2); // 脱外层括号   
329             do  
330             {   // 重复建n个子表   
331                 sever(sub, hsub); // 从sub中分离出表头串hsub   
332                 CreateGList(&p->a. ptr. hp, hsub);  
333                 q = p;  
334                 if(!StrEmpty(sub))  // 表尾不空   
335                 {  
336                     p = (GLNode *)malloc(sizeof(GLNode));  
337                     if(!p)  
338                         exit(0);  
339                     p->tag = LIST;  
340                     q->a.ptr.tp = p;  
341                 }  
342             }while(!StrEmpty(sub));  
343             q->a.ptr.tp = NULL;  
344         }  
345     }  
346     return 1;  
347 }  
348   
349 // 打印原子   
350 void visit(AtomType e)  
351 {  
352     printf("%c ", e);  
353 }  
354   
355 int main()  
356 {  
357     // 广义表的表示形式是，空表:(),单原子:a,表:(a,(b),c,(d,(e)))   
358     char p[80] = {"(a,(b),c,(d,(e)))"};  
359     SString t;  
360     GList L,m;  
361       
362     InitGList(&L);  
363     InitGList(&m);  
364     printf("空广义表L的深度 = %d
L是否空？%d(1:是 0:否)

",  
365         GListDepth(L), GListEmpty(L));  
366     StrAssign(t, p);  
367     CreateGList(&L, t);                                         // 创建广义表   
368     printf("
广义表L的长度 = %d
", GListLength(L));  
369     printf("广义表L的深度 = %d 
L是否空？%d(1:是 0:否)
",  
370         GListDepth(L), GListEmpty(L));  
371     printf("遍历广义表L：
");  
372     Traverse_GL(L, visit);  
373     printf("

复制广义表m = L
");  
374     CopyGList(&m, L);  
375     printf("广义表m的长度 = %d
", GListLength(m));  
376     printf("广义表m的深度 = %d
", GListDepth(m));  
377     printf("遍历广义表m：
");  
378     Traverse_GL(m,visit);  
379     DestroyGList(&m);  
380     m = GetHead(L);  
381     printf("

m是L的表头，遍历广义表m：
");  
382     Traverse_GL(m, visit);  
383     DestroyGList(&m);  
384     m = GetTail(L);  
385     printf("

m是L的表尾，遍历广义表m：
");  
386     Traverse_GL(m,visit);  
387     InsertFirst_GL(&m, L);  
388     printf("

插入L为m的表头，遍历广义表m：
");  
389     Traverse_GL(m,visit);  
390     printf("

删除m的表头，遍历广义表m：
");  
391     DestroyGList(&L);  
392     DeleteFirst_GL(&m, &L);  
393     Traverse_GL(m, visit);  
394     printf("
");  
395     DestroyGList(&m);  
396     return 0;  
397 }