欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

c/c++ 广义表

程序员文章站 2022-05-04 13:19:25
广义表 列表里面有列表,比如(1,(2,(3,4)),5) 用链表可以实现 结果如图 guangyibiao.h guangyibiao.c guangyibiaomai.c ......

广义表

列表里面有列表,比如(1,(2,(3,4)),5)

用链表可以实现

结果如图
c/c++ 广义表

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;
}