广义表
列表里面有列表，比如(1,(2,(3,4)),5)
用链表可以实现
结果如图
guangyibiao.h
#ifndef __GUANGYIBIAO__#define __GUANGYIBIAO__#include#include #include #include #include #include #include #define AtomType inttypedef enum{ATOM, LIST}ElemTag;typedef struct GLNode{ ElemTag tag; union{ AtomType atom; struct GLNode* head; }; struct GLNode* tail;}GLNode;typedef GLNode* GenList;void init(GenList* gl);void createGenList(GenList* gl, char* s);void show(GenList gl);#endif
guangyibiao.c
#include "guangyibiao.h"void init(GenList* gl){ *gl = NULL;}//挑出逗号前的一个元素，元素可以是原子也可以是列表bool server1(char* sub, char* hsub){ int n = strlen(sub); int i = 0; char ch = sub[0]; int k = 0; //ｋ的作用是，识别逗号是括号里的，还是括号外的，如果是括号外的逗号就跳出while了，括号内的逗号不跳出循环，继续往下找。 while(i < n && (ch != ',' || k != 0)){ if(ch == '('){ k++; } else if(ch == ')'){ k--; } i++; ch = sub[i]; } //逗号在sub的范围内 if(i < n){ sub[i] = '\0'; strcpy(hsub, sub); strcpy(sub, sub+i+1); } //括号不匹配 else if(k != 0) return false; //sub本身就是表，比如为(1,2)时，i会等于n，所以把sub给hsub，sub就没有以后部分了 else{ strcpy(hsub, sub); sub[0] = '\0'; } return true;}//思路：递归创建节点，如果sub是列表，就递归调用自己void createGenList(GenList* gl, char* s){ int n = strlen(s); //去掉s的外括号，比如s为(1,(2, 3)),处理后sub为1,(2, 3)，并在sub的最后加上'\0' char* sub = (char*)malloc(sizeof(char) * (n - 2)); char* hsub = (char*)malloc(sizeof(char) * (n - 2)); assert(NULL != sub && NULL != hsub); strncpy(sub, s+1, n-2); sub[n-2] = '\0'; GLNode* p = *gl; while(strlen(sub) != 0){ if(NULL == p){ *gl = p = (GLNode*)malloc(sizeof(GLNode)); p->head = p->tail = NULL; }else{ p = p->tail = (GLNode*)malloc(sizeof(GLNode)); p->head = p->tail = NULL; } assert(NULL != p); if(server1(sub, hsub)){ if(hsub[0] == '('){ p->tag = LIST; createGenList(&(p->head), hsub); } else{ p->tag = ATOM; p->atom = atoi(hsub); } } }}//思路：递归void show(GenList gl){ if(gl == NULL) return; if(gl->tag == ATOM){ printf("%d", gl->atom); if(gl->tail != NULL){ printf(","); } //如果gl为ATOM的话，gl就不会有head，所以只需调用show(gl->tail) show(gl->tail); } //如果gl为LIST的话，gl就会有head，也会有tail，所以调用show(gl->head)，show(gl->tail) else if(gl->tag == LIST){ printf("("); show(gl->head); printf(")"); if(gl->tail != NULL){ printf(","); } show(gl->tail); }} guangyibiaomai.c
#include "guangyibiao.h"int main(){ GenList gl; init(&gl); char* a = "(1,2,3)"; char* b = "(1,(2,3))"; char* c = "(1,(2),3)"; char* d = "((1,2),3)"; char* e = "((1,2,3))"; char* f = "((),1)"; char* g = "(1,(2,(3,4)),5)"; char* h = "((),1,(2,(3,(),4)),5)"; char* i = "(())"; createGenList(&gl, i); if(gl != NULL){ printf("("); show(gl); printf(")\n"); } return 0;}