数据结构-广义表的基本操作 （C语言代码）

参考代码:

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

#define MAX_STR_LEN 101

typedef char AtomType;

typedef enum {
	ATOM,
	LIST
} ElemTag;

typedef struct GLNode {
	ElemTag tag;
	union {
		AtomType atom;
		struct {
			struct GLNode *hp;
			struct GLNode *tp;
		} ptr;
	};
} GLNode, *GList;

void SubString(char *sub, char *str, int start, int end);

void SplitHeadStr(char *str, char *headstr);

void CreateGList(GList *G, char *str);

int GListDepth(GList G);

int main()
{
	GList G = NULL;
	char str[MAX_STR_LEN];

	scanf("%s", str);
	CreateGList(&G, str);

	int dep = GListDepth(G);
	printf("%d\n", dep);
	return 0;
}

void SubString(char *sub, char *str, int start, int end) {

	for (char *temp = str + start; temp <= str + end; temp++) {

		*sub++ = *temp;
	}

	*sub = '\0';
}

void SplitHeadStr(char *str, char *headstr) {

	int n = strlen(str);
	int i = 0, k = 0;

	do {

		if (str[i] == '(') k++;
		if (str[i] == ')') k--;

		i++;

	} while (i < n && (str[i] != ',' || k != 0));

	if (i < n) {

		SubString(headstr, str, 0, i - 1);
		SubString(str, str, i + 1, n - 1);
	}
	else {

		strcpy(headstr, str);
		*str = '\0';
	}
}

void CreateGList(GList *G, char *str) {

	if (!strcmp(str, "()")) { // 若为空表

		*G = NULL;
	}
	else { // 不为空表

		*G = (GList)malloc(sizeof(GLNode)); // 建立表结点

		if (strlen(str) == 1) { // 若为原子

			(*G)->tag = ATOM;
			(*G)->atom = *str;
		}
		else { // 为子表

			char hstr[MAX_STR_LEN] = { 0 };
			GList p = *G;

			(*G)->tag = LIST;
			SubString(str, str, 1, strlen(str) - 2); // 子表去两边括号()

			do {

				SplitHeadStr(str, hstr); // 获取表头hstr，剩下表尾str
				CreateGList(&p->ptr.hp, hstr); // 递归创建表头

				if (str != NULL && strlen(str) != 0) { // 若表尾不为空

					GList t = (GList)malloc(sizeof(GLNode));
					t->tag = LIST; // 表尾为表
					p->ptr.tp = t;
					p = t;
				}
			} while (str != NULL && strlen(str) != 0);

			p->ptr.tp = NULL;
		}
	}
}

int GListDepth(GList G) {

	if (!G) return 1;

	if (G->tag == ATOM) return 0;

	int max = 0;

	for (GList p = G; p; p = p->ptr.tp) {

		int dep = GListDepth(p->ptr.hp);
		if (max < dep) max = dep;
	}

	return max + 1;
}