广义表

 1 typedef char AtomType;  2 enum ElemTag { ATOM, LIST };  3   4 typedef struct GLNode  5 {  6     ElemTag tag;  7   8     union  9     { 10         AtomType atom; 11         struct GLNode* head; 12     }value; 13  14     struct GLNode* next; 15 }GLNode;

 1 GLNode* CreateGList(GLNode* A)  2 {//带头结点  3     //假定广义表中元素类型为ElemType为char类型，每个原子的值被限定为单个字符。  4     //并假设广义表是一个正确的表达式，其格式为：  5     //元素之间用一个逗号分隔，表元素的起止符号为左、右括号，空表在元括号内包含#。  6     char ch = '';  7   8     scanf("%c", &ch);  9     if (ch != '') 10     {//表达式未结束 11         A = (GLNode*)calloc(1, sizeof(GLNode)); 12         if (ch == '(') 13         { 14             A->tag = LIST; 15             A->value.head = CreateGList(A->value.head); 16         } 17         else if (ch == '#' || ch == ')') 18         { 19             A = NULL; 20         } 21         else 22         {//原子结点 23             A->tag = ATOM; 24             A->value.atom = ch; 25         } 26     } 27     else 28     { 29         A = NULL; 30     } 31  32     scanf("%c", &ch); 33     if (A != NULL) 34     { 35         if (ch == ',') 36         { 37             A->next = CreateGList(A->next); 38         } 39         else 40         { 41             A->next = NULL; 42         } 43     } 44     return A; 45 }

 1 void PrintGList(GLNode* A)  2 {  3     if (A)  4     {  5         if (A->tag == LIST)  6         {  7             printf("(");  8             if (A->value.head)  9             { 10                 PrintGList(A->value.head); 11             } 12         } 13         else 14         {//原子结点 15             printf("%c", A->value.atom); 16         } 17          18         if (A->tag == LIST) 19         { 20             printf(")"); 21         } 22         if (A->next) 23         { 24             printf(","); 25             PrintGList(A->next); 26         } 27     }//广义表非空 28 }

 1 GLNode* GetHead(GLNode* A)  2 {  3     if (A->tag != LIST)  4     {//带头结点的广义表  5         exit(-1);  6     }  7   8     A = A->value.head;  9     if (A == NULL) 10     { 11         return NULL; 12     } 13     else if (A->tag == ATOM) 14     { 15         exit(-1); 16     } 17     else 18     { 19         return A->value.head; 20     } 21 }

View Code