苗火 Nicholas

[Data structures]General list

2019-8-22 萧 写技术

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX 1024

/* General list */
typedef struct _GLNode{
	int tag; //0-atom, 1-node
	union{
		char atom;
		struct{
		       	struct _GLNode *hp;
			struct _GLNode *tp;
		}ptr;
	};
}GList;

int server(char **str, char **hstr)
{
	int n = strlen(*str);
	int k = 0;
	int i = 0;
	char ch;
	do{
		ch = (*str)[i];	
		if(ch == '('){
			k++;	
		}else if(ch == ')'){
			k--;
		}
	}while(++i<n && (ch != ',' || k != 0) );
	if(i<n){
		*hstr = *str; (*hstr)[i-1] = 0;
		*str = *str + i;
	}else{
		*hstr = *str;
		*str = *str + n;
	}
}

int CreateGList(GList **L, char *S)
{
	int n = strlen(S);
	char *sub = S;
	char *hsub;
	GList *p,*q;
	if(strcmp(sub, "()") == 0){
		*L = NULL;
	}else{
		*L = (GList *)malloc(sizeof(GList));

		if(strlen(sub) == 1){
			(*L)->tag = 0;
			(*L)->atom = sub[0];
		}else{
			(*L)->tag = 1;
			if(sub[0] == '('){
				sub[n-1] = 0;
				sub = sub+1;
			}
			p = *L;
			do{
				server(&sub, &hsub);
				CreateGList(&(p->ptr.hp), hsub);
				hsub = NULL;
				if(strlen(sub) != 0){
					q = (GList *)malloc(sizeof(GList));
					q->tag = 1;
					p->ptr.tp = q;

					p = q;
				}
			}while(strlen(sub) != 0);
			p->ptr.tp = NULL;
		}
	}
	return 1;
}

int GListDepth(GList *L)
{
	GList *p;
	int max;
	int dep;

	if(!L){
		return 1;
	}
	if(L->tag == 0){
		return 0;
	}
	for(max = 0, p = L; p; p = p->ptr.tp){
		dep = GListDepth(p->ptr.hp);
		if(dep > max){
			max = dep;
		}
	}
	return max + 1;
}

int CopyGList(GList **T, GList *L)
{
	if(!L){
		*T = NULL;
	}else{
		*T = (GList *)malloc(sizeof(GList));
		(*T)->tag = L->tag;
		if(L->tag == 0){
			(*T)->atom = L->atom;
		}else{
			CopyGList(&(*T)->ptr.hp, L->ptr.hp);
			CopyGList(&(*T)->ptr.tp, L->ptr.tp);
		}
	}
	return 1;
}

/*
 * There may be a bug that some brackets will lost
 * */
int PrintGList(GList *L)
{
	if(!L){
		printf("()");
		return 0;	
	}	
	if(L->tag == 0){
		printf("%c", L->atom);
	}else{
		if(L->ptr.hp && L->ptr.hp->tag == 1){
			printf("(");
		}
		PrintGList(L->ptr.hp);
		if(L->ptr.tp != NULL){
			printf(",");
			PrintGList(L->ptr.tp);
		}
		if(L->ptr.hp && L->ptr.hp->tag == 1){
			printf(")");
		}
	}
}

void main()
{
	GList *L,*T;

	printf("log.anycle.com\n\n");
	printf("Original data:\n");
	char *original = "((a,b,c,d,(b,b,d,e)),a,(b,()))";
	char *str = malloc(strlen(original) + 1);
	char *hstr;
	strcpy(str, original);
	printf("%s\n", str);

	printf("Create general list:\n");
	CreateGList(&L, str);

	printf("General list depth:\n");
	printf(" %d\n", GListDepth(L));

	printf("Copy general list:\n");
	CopyGList(&T, L);

	printf("Print general list:\n");
	PrintGList(L);
	printf("\n");
}

标签: Data Structures data_structures