1、广义的定义和初始化
#include<stdio.h> #include<malloc.h> #include<string.h> #include<assert.h> #include<stdlib.h> #define ATOM_TYPE int typedef enum { HEAD, ATOM, CHILDLIST } ElementType; typedef struct GLNode { ElementType tag; // 标记位, 用于区分原子结点和表节点 union { ATOM_TYPE atom; // 原子节点的值域 struct GLNode *hp; // 表节点的表头指针 }; struct GLNode *tp; // 指向下一个元素节点 } GLNode; typedef GLNode* GenList; // 广义表 类型是一种扩展的线性链表 void InitGenList(GenList* gl){ *gl = NULL; }
2、广义表的创建
// 分离表头和表尾元素 int separate(char* sub, char* hsub) { if (sub[0] == '\0' || strcmp(sub, "()") == 0) { hsub[0] = '\0'; return 1; } int n = strlen(sub); int i = 0, k = 0; // 用于判断首字符为 ( 的情况 while (i < n && (sub[i] != ',' || k != 0)) { if (sub[i] == '(') k++; else if (sub[i] == ')') k--; i++; } if (i < n) { strncpy(hsub, sub, i); hsub[i] = '\0'; strcpy((char*)sub, sub + i + 1); } else if (k != 0) { return 0; } else { strcpy(hsub, sub); sub[0] = '\0'; } return 1; } void CreateGenList(GenList* gl,char* str){ /* 将广义表就看成两部分:表头(广义表第一个元素) 表尾(广义表除第一个元素的其他元素) */ //先去除最外层括号 int n = strlen(str); //用于存储去掉最外层括号的str char* sub = (char*)malloc(sizeof(char) * (n-2)); //用于存储表头元素 char* hsub = (char*)malloc(sizeof(char) * (n-2)); assert(sub != NULL && hsub != NULL); strncpy(sub, str + 1,n - 1); sub[n - 2] = '\0'; if(*gl == NULL){ //说明当前是表头节点 *gl = (GLNode*)malloc(sizeof(GLNode)); assert(*gl != NULL); (*gl)->tag = HEAD; (*gl)->hp = (*gl)->tp = NULL; } //采用尾插法 GLNode *p = *gl; while(strlen(sub) != 0){ p = p->tp = (GLNode*)malloc(sizeof(GLNode)); assert(p != NULL); //填充数据 p->hp = p->tp = NULL; //"1,2,3" ==> hsub="1", sub="2,3" //"(1,2),3,4" ==> hsub="(1,2)" sub="3,4" if(separate(sub,hsub)){ if(hsub[0] == '('){ //说明分离出来的元素是个子表 p->tag = CHILDLIST; CreateGenList(&p->hp,hsub); } else { p->tag = ATOM; p->atom = atoi(hsub); } } } }
3、广义表的其他方法实现
void showGenList(GenList gl) { GLNode* p = gl->tp; printf("("); while (p != NULL) { if (p->tag == ATOM) { printf("%d", p->atom); } else if (p->tag == CHILDLIST) { showGenList(p->hp); } // 检查下一个节点是否存在,如果存在则打印逗号 if (p->tp != NULL) { printf(","); } p = p->tp; } printf(")"); } // 求广义表的长度 int length(GenList gl){ int len = 0; while(gl->tp != NULL){ len++; gl = gl->tp; } return len; } int GenListDepth(GenList gl){ if(gl->tp == NULL) return 1; //指向广义表第一个节点 GLNode *p = gl->tp; int maxDepth = 0; int dep; while(p != NULL){ if(p->tag == CHILDLIST) { // 传入广义表子表的 第一个节点 dep = GenListDepth(p->hp->tp); if(dep > maxDepth){ maxDepth = dep; } } p = p->tp; } return maxDepth + 1; } void freeGenList(GenList gl) { if (gl == NULL) return; GLNode* p = gl->tp; while (p != NULL) { if (p->tag == CHILDLIST) { freeGenList(p->hp); } GLNode* next = p->tp; free(p); p = next; } free(gl); } int main(){ GenList gl; InitGenList(&gl); char* ga = "(1,2,3)"; char* gb = "(1,(2,3))"; char* gc = "(1,(2),3)"; char* gd = "((1,2),3)"; char* ge = "((1,2,3))"; char* gf = "()"; char* gg = "(1,(2,(3,4)),5)"; CreateGenList(&gl,gg); showGenList(gl); printf("\nLength: %d",length(gl)); printf("\nDepth: %d",GenListDepth(gl)); freeGenList(gl); // 释放广义表占用的内存 return 0; }
标签:10,NULL,sub,tp,GLNode,char,广义,gl From: https://www.cnblogs.com/xpp3/p/18434957