c/c++ 广义表
程序员文章站
2022-05-04 13:19:25
广义表 列表里面有列表,比如(1,(2,(3,4)),5) 用链表可以实现 结果如图 guangyibiao.h guangyibiao.c guangyibiaomai.c ......
广义表
列表里面有列表,比如(1,(2,(3,4)),5)
用链表可以实现
结果如图
guangyibiao.h
#ifndef __GUANGYIBIAO__ #define __GUANGYIBIAO__ #include <stdio.h> #include <string.h> #include <memory.h> #include <malloc.h> #include <assert.h> #include <stdbool.h> #include <stdlib.h> #define AtomType int typedef 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; //k的作用是,识别逗号是括号里的,还是括号外的,如果是括号外的逗号就跳出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; }
上一篇: php实现读取手机客户端浏览器的类
下一篇: 高速上手C++11 14 笔记2