广义表的建立与一般操作

一、广义表的概念         广义表是线性表的推广，但线性表的元素仅限于原子项，原子作为结构上不可分割的成分，它可以是一个数或一个结构，若放松对表元素的这种限制，允许它们具有自身独立类型结构，就产生了广义表的概念。        广义表是n(n>=0)个数据元素a1,a2,......ai,......,an的有序序列，一般记作：                                                                                                                                     ls = (a1,a2 ,........,ai, ...an)       其中：ls是广义表的名称，n是它的长度。 二、广义表的数据结构 A = () B = (e) C = (a,(b,(c,d))) D = ((),B,C) E = (a,E) F = (()) 图中为广义表的头尾表示法

头尾表示法的存储结构：

[cpp] view plain copy typedef enum {ATOM , LIST} Elemtag ; typedef struct node { Elemtag tag ; //用以标记是单个元素或广义表 union { datatype data ; struct { struct node *hp , *tp ; //指向广义表头节点和尾节点的指针 } ptr ; }; } GLNode , *GList ;

孩子兄弟表示法的存储结构：

[cpp] view plain copy typedef enum {ATOM , LIST} ELemtag ; typedef struct GLENode{ Elemtag tag ; union{ datatype data ; struct GLENode *hp ; } struct GLENode *tp ; } *EGList ;

三、广义表的操作 1、广义表的取头、取尾操作 [cpp] view plain copy /* *广义表的取头操作 */ GList GetHead(GList ls) { GList list = NULL ; if(ls->tag == 1) { list = ls->ptr.hp ; } return list ; } /* *广义表的取尾操作 */ GList GetTail(GList ls) { GList list = NULL ; if(ls->tag == 1) { list = ls->ptr.tp ; } return list ; } 2、建立广义表的存储结构 cpp] view plain copy /* *将字符串分为表头和表尾字符串 */ void server(char *hsub , char *s) { int i , k ; for(i = 0 , k = 0 ; i < strlen(s) ; i++) { if(s[i] == '(') { k++; } if(s[i] == ')') { k--; } if(s[i] == ',' && k == 0) { break ; } } if(i < strlen(s)) { substr(s , hsub , 1 , i) ; substr(s , s , i + 2 , strlen(s) - i - 1) ; } else { substr(s , hsub , 1 ,strlen(s)) ; s[0] = '\0' ; } } /* *建立广义表的存储结构 */ int CreateGList(GList *ls , char *s) { GLNode *p , *q ; char hsub[MAXSIZE] ; //字符串为空时，广义表为空 if(s == NULL) { *ls = NULL ; } else { if(!(*ls = (GList)malloc(sizeof(GLNode)))) { return 0 ; } //字符长度为1时，广义表为单个元素 if(strlen(s) == 1) { (*ls)->tag = 0 ; (*ls)->data = *s ; } else { substr(s , s , 2 , strlen(s) - 2) ; //去掉最外层括号; p = (*ls) ; p->tag = 1 ; do { server(hsub , s) ; //获取头节点 CreateGList(&(p->ptr.hp) , hsub) ; q = p ; if(*s != '\0') { p = (GList)malloc(sizeof(GLNode)) ; p->tag = 1 ; q->ptr.tp = p ; } else { p->ptr.tp = NULL ; } }while(*s != '\0') ; } } return 1 ; } 3、以表头、表尾建立广义表 [cpp] view plain copy /* *以表头和表尾建立广义表 */ int Merge(GList l1 , GList l2 , GList *ls) { if(!((*ls) = (GList)malloc(sizeof(GLNode)))) { return 0 ; } (*ls)->tag = 1 ; (*ls)->ptr.hp = l1 ; (*ls)->ptr.tp = l2 ; return 1 ; } 4、求广义表的长度

/* *取得广义表的长度 */ int Depth(GList ls) { GList p ; int max , depth ; if(ls == NULL) { return 1 ; //空表长度为1 } if(ls->tag == 0) { return 0 ; //单元素长度为0 } for(max = 0 , p = ls->ptr.tp; p ; p = p->ptr.tp) { depth = Depth(p) ; if(depth > max) { max = depth ; } } return max + 1 ; } 5、复制广义表 /* *进行广义表的复制 */ int CopyGList(GList ls , GList *ls1) { if(ls == NULL) { (*ls1) = NULL ; } else { if(!((*ls1)=(GList)malloc(sizeof(GLNode)))) { return 0 ; } if(ls->tag == 0) { (*ls1)->tag = 0 ; (*ls1)->data = ls->data ; } else { (*ls1)->tag = 1 ; CopyGList(ls->ptr.hp , &((*ls1)->ptr.hp)) ; CopyGList(ls->ptr.tp , &((*ls1)->ptr.tp)) ; } } } 四、测试的全部代码

/* *操作均是建立在关于建立在头尾指针的广义表上 */ #include<stdio.h> #include<malloc.h> #include<string.h> #define MAXSIZE 100 /* *定义广义表节点的存储结构 */ typedef char datatype ; typedef enum {ATOM , LIST} Elemtag ; typedef struct node { Elemtag tag ; //用以标记是单个元素或广义表 union { datatype data ; struct { struct node *hp , *tp ; //指向广义表头节点和尾节点的指针 } ptr ; }; } GLNode , *GList ; /* *进行字符串的裁剪，s为被裁剪的对象 */ void substr(char *s , char *sub , int startIndex , int len) { int i ; for(i = 1 ; i < startIndex ; s++ , i++) ; for(i = 0 ; i < len ; i++) { sub[i] = s[i] ; } sub[len] = '\0' ; } /* *将字符串分为表头和表尾字符串 */ void server(char *hsub , char *s) { int i , k ; for(i = 0 , k = 0 ; i < strlen(s) ; i++) { if(s[i] == '(') { k++; } if(s[i] == ')') { k--; } if(s[i] == ',' && k == 0) { break ; } } if(i < strlen(s)) { substr(s , hsub , 1 , i) ; substr(s , s , i + 2 , strlen(s) - i - 1) ; } else { substr(s , hsub , 1 ,strlen(s)) ; s[0] = '\0' ; } } /* *建立广义表的存储结构 */ int CreateGList(GList *ls , char *s) { GLNode *p , *q ; char hsub[MAXSIZE] ; //字符串为空时，广义表为空 if(s == NULL) { *ls = NULL ; } else { if(!(*ls = (GList)malloc(sizeof(GLNode)))) { return 0 ; } //字符长度为1时，广义表为单个元素 if(strlen(s) == 1) { (*ls)->tag = 0 ; (*ls)->data = *s ; } else { substr(s , s , 2 , strlen(s) - 2) ; //去掉最外层括号; p = (*ls) ; p->tag = 1 ; do { server(hsub , s) ; //获取头节点 CreateGList(&(p->ptr.hp) , hsub) ; q = p ; if(*s != '\0') { p = (GList)malloc(sizeof(GLNode)) ; p->tag = 1 ; q->ptr.tp = p ; } else { p->ptr.tp = NULL ; } }while(*s != '\0') ; } } return 1 ; } /* *打印广义表 */ void printGList(GList ls) { if(ls != NULL) { if(ls->tag == 0) { printf("%c " , ls->data) ; } else { printGList(ls->ptr.hp) ; printGList(ls->ptr.tp) ; } } } /* *以表头和表尾建立广义表 */ int Merge(GList l1 , GList l2 , GList *ls) { if(!((*ls) = (GList)malloc(sizeof(GLNode)))) { return 0 ; } (*ls)->tag = 1 ; (*ls)->ptr.hp = l1 ; (*ls)->ptr.tp = l2 ; return 1 ; } /* *取得广义表的长度 */ int Depth(GList ls) { GList p ; int max , depth ; if(ls == NULL) { return 1 ; //空表长度为1 } if(ls->tag == 0) { return 0 ; //单元素长度为0 } for(max = 0 , p = ls->ptr.tp; p ; p = p->ptr.tp) { depth = Depth(p) ; if(depth > max) { max = depth ; } } return max + 1 ; } /* *进行广义表的复制 */ int CopyGList(GList ls , GList *ls1) { if(ls == NULL) { (*ls1) = NULL ; } else { if(!((*ls1)=(GList)malloc(sizeof(GLNode)))) { return 0 ; } if(ls->tag == 0) { (*ls1)->tag = 0 ; (*ls1)->data = ls->data ; } else { (*ls1)->tag = 1 ; CopyGList(ls->ptr.hp , &((*ls1)->ptr.hp)) ; CopyGList(ls->ptr.tp , &((*ls1)->ptr.tp)) ; } } } /* *广义表的取头操作 */ GList GetHead(GList ls) { GList list = NULL ; if(ls->tag == 1) { list = ls->ptr.hp ; } return list ; } /* *广义表的取尾操作 */ GList GetTail(GList ls) { GList list = NULL ; if(ls->tag == 1) { list = ls->ptr.tp ; } return list ; } //进行广义表的测试 void main() { GList ls1 , ls2 , ls3 , ls4 ; char s[MAXSIZE] , s1[MAXSIZE]; scanf("%s" , s) ; CreateGList(&ls1 , s) ; scanf("%s" , s1) ; CreateGList(&ls2 , s1) ; printGList(ls1) ; printf("\n") ; printGList(ls2) ; printf("\n") ; printf("the depth of ls1 is %d \n" , Depth(ls1)) ; printf("the depth of ls2 is %d \n" , Depth(ls2)) ; Merge(ls1 , ls2 , &ls3) ; printGList(ls3) ; printf("\n") ; printf("the depth of ls3 is %d \n" , Depth(ls3)) ; CopyGList(ls3 , &ls4) ; printGList(ls4) ; printf("\n") ; printf("the depth of ls4 is %d \n" , Depth(ls4)) ; }