# 广义表的基本原理

广义表一般记作LS = (A1,A2,···,An)(1 <= i <= n),
广义表中的元素可以是`原子``子表`
广义表中称第一个元素A1为`表头`,除`表头`外的元素总和`(A2,···,An)`称为表尾,
当广义表中的元素为空时称为空表。

# 广义表的基本创建

Generalized_Table_.h(头文件)
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#define MAX_SPACE 256
#define DEBUG
typedef int EleType;
enum EleTag
{
	HEAD,
	ATOM,
	SUBLIST
};
struct GL_Table_Node
{
	int Tag;
	union
	{
		EleType element;
		struct GL_Table_Node* S_Next;
	};
	struct GL_Table_Node* T_Next;
};
void Init_GL_Table(struct GL_Table_Node* GLT);
void Show_Menu();
void Create_GL_Table(struct GL_Table_Node* GLT, const char* List);
void Print_GL_Table(const struct GL_Table_Node* GLT);
void Copy_GL_Table(struct GL_Table_Node* GLT, const struct GL_Table_Node* Copied_GLT);
int Get_GL_Table_Length(const struct GL_Table_Node* GLT);
int Get_GL_Table_Depth(const struct GL_Table_Node* GLT);
void Get_GL_Table_Head(const struct GL_Table_Node* GLT, struct GL_Table_Node* GLT_Head);
void Get_GL_Table_Tail(const struct GL_Table_Node* GLT, struct GL_Table_Node* GLT_Tail);
void Insert_GL_Table_Head(struct GL_Table_Node* GLT, const char* List);
void Insert_GL_Table_Tail(struct GL_Table_Node* GLT, const char* List);
void Delete_GL_Table_Head(struct GL_Table_Node* GLT);
void Delete_GL_Table_Tail(struct GL_Table_Node* GLT);
void Clean_GL_Table(struct GL_Table_Node* GLT);
void Destroy_GL_Table(struct GL_Table_Node* GLT);
Generalized_Table_functions.c
#include"Generalized_Table_.h"
void Init_GL_Table(struct GL_Table_Node* GLT_N)
{
	GLT_N->Tag = HEAD;
	GLT_N->T_Next = NULL;
	GLT_N->S_Next = NULL;
}
void Show_Menu()
{
	printf("\n******************************************************\n");
	printf(" [1]  Create_GL_Table      [2]  Print_GL_Table       *\n");
	printf(" [3]  Copy_GL_Table        [4]  Get_GL_Table_Length  *\n");
	printf(" [5]  Get_GL_Table_Depth   [6]  Get_GL_Table_Head    *\n");
	printf(" [7]  Get_GL_Table_Tail    [8]  Insert_GL_Table_Head *\n");
	printf(" [9]  Insert_GL_Table_Tail [10] Delete_GL_Table_Head *\n");
	printf(" [11] Delete_GL_Table_Tail [12] Clean_GL_Table       *\n");
	printf(" [13] Destroy_GL_Table                               *\n");
	printf(" [0]  ExitSystem                                     *\n");
	printf("******************************************************\n");
}
static int Strlen(const char* str)
{
	assert(NULL != str);
	int counting = 0;
	while (*str)
	{
		++counting;
		++str;
	}
	return counting;
}
static void Strcopy(char* str1, const char* str2)
{
	assert(NULL != str1 && NULL != str2);
	while (*str2)
	{
		*str1++ = *str2++;
	}
	*str1 = '\0';
}
static char Strcmp(const char* str1, const char* str2)
{
	assert(NULL != str1 && NULL != str2);
	while (*str1)
	{
		if (*str1 < *str2)
			return -1;
		else if (*str1 > *str2)
			return 1;
		++str1;
		++str2;
	}
	return 0;
}
static void Strncopy(char* str1, const char* str2,int length)
{
	assert(NULL != str1 && NULL != str2);
	if (!(length))
		return;
	else
	{
		while (length)
		{
			*str1++ = *str2++;
			--length;
		}
	}
}
static char Split(char* Sub_L, char* H_Sub_L)
{
	assert(NULL != Sub_L && NULL != H_Sub_L);
	int L_SL = Strlen(Sub_L);
	int i = 0;
	int flag = 0;
	char P_char = Sub_L[0];
	if ('\0' == *Sub_L || !(Strcmp(Sub_L, "()")))
	{
		H_Sub_L[0] = '\0';
		return 1;
	}
	while (i < L_SL && (',' != P_char || flag != 0))
	{
		if ('(' == P_char)
			++flag;
		else if (')' == P_char)
			--flag;
		++i;
		P_char = Sub_L[i];
	}
	if (i < L_SL)
	{
		Sub_L[i] = '\0';
		Strcopy(H_Sub_L, Sub_L);
		Strcopy(Sub_L, Sub_L + i + 1);
	}
	else if (0 != flag)
		return 0;
	else
	{
		Strcopy(H_Sub_L, Sub_L);
		Sub_L[0] = '\0';
	}
	return 1;
}
void Create_GL_Table(struct GL_Table_Node* GLT_N, const char* List)
{
	int length_L = Strlen(List);
	struct GL_Table_Node* P_GLT_N = GLT_N;
	char* Sub_L = (char*)malloc(sizeof(char) * (length_L - 2));
	char* H_Sub_L = (char*)malloc(sizeof(char) * (length_L - 2));
	Strncopy(Sub_L, List + 1, length_L - 2);
	Sub_L[length_L - 2] = '\0';
	while (Strlen(Sub_L))
	{
		struct GL_Table_Node* P_Next = (struct GL_Table_Node*)malloc(sizeof(struct GL_Table_Node));
		P_Next->S_Next = NULL;
		P_Next->T_Next = NULL;
		
		P_GLT_N->T_Next = P_Next;
		if (Split(Sub_L, H_Sub_L))
		{
			if ('(' == H_Sub_L[0])
			{
				P_Next->Tag = SUBLIST;
				P_Next->S_Next = (struct GL_Table_Node*)malloc(sizeof(struct GL_Table_Node));
				P_Next->S_Next->Tag = HEAD;
				Create_GL_Table(P_Next->S_Next, H_Sub_L);
			}
			else
			{
				P_Next->Tag = ATOM;
				P_Next->element = atoi(H_Sub_L);
			}
		}
		P_GLT_N = P_GLT_N->T_Next;
	}
}
// 有个逗号问题待修
void Print_GL_Table(const struct GL_Table_Node* GLT_N)
{
	if (NULL == GLT_N)
		return;
	else
	{
		const struct GL_Table_Node* P_GLT_N = GLT_N->T_Next;
		printf("(");
		while (NULL != P_GLT_N)
		{
			if (NULL != P_GLT_N->S_Next && SUBLIST == P_GLT_N->Tag)
				Print_GL_Table(P_GLT_N->S_Next);
			if (ATOM == P_GLT_N->Tag)
			{
				if (NULL == P_GLT_N->T_Next)
					printf("%d", P_GLT_N->element);
				else
					printf("%d,", P_GLT_N->element);
			}
			P_GLT_N = P_GLT_N->T_Next;
		}
		printf(")");
	}
}
void Copy_GL_Table(struct GL_Table_Node* GLT, const struct GL_Table_Node* Copied_GLT)
{
	assert(NULL != Copied_GLT);
	GLT->S_Next = Copied_GLT->S_Next;
	GLT->T_Next = Copied_GLT->T_Next;
	Print_GL_Table(GLT);
}
int Get_GL_Table_Length(const struct GL_Table_Node* GLT)
{
	assert(NULL != GLT);
	int counting = 0;
	const struct GL_Table_Node* P_GLT = GLT->T_Next;
	while (NULL != P_GLT)
	{
		++counting;
		P_GLT = P_GLT->T_Next;
	}
	return counting;
}
int Get_GL_Table_Depth(const struct GL_Table_Node* GLT)
{
	const struct GL_Table_Node* P_GLT = GLT->T_Next;
	int Max_Depth = 0;
	int Sub_Depth = 0;
	if (NULL == GLT)
		return 1;
	while (NULL != P_GLT)
	{
		if (NULL != P_GLT->S_Next && SUBLIST == P_GLT->Tag)
			Sub_Depth = Get_GL_Table_Depth(P_GLT->S_Next);
		if (Sub_Depth > Max_Depth)
			Max_Depth = Sub_Depth;
		P_GLT = P_GLT->T_Next;
	}
	return Max_Depth + 1;
}
void Get_GL_Table_Head(const struct GL_Table_Node* GLT, struct GL_Table_Node* GLT_Head)
{
	assert(NULL != GLT && NULL != GLT_Head);
	struct GL_Table_Node* P_GLT = GLT->T_Next;
	GLT_Head->T_Next = (struct GL_Table_Node*)malloc(sizeof(struct GL_Table_Node));
	GLT_Head->Tag = HEAD;
	GLT_Head->S_Next = NULL;
#ifdef DEBUG
	Print_GL_Table(GLT);
#endif
	if (SUBLIST == GLT->T_Next->Tag)
	{
		GLT_Head->T_Next->Tag = SUBLIST;
		GLT_Head->T_Next->T_Next = NULL;
		GLT_Head->T_Next->S_Next = GLT->T_Next->S_Next;
	}
	else
	{
		GLT_Head->T_Next->Tag = ATOM;
		GLT_Head->T_Next->element = GLT->T_Next->element;
		GLT_Head->T_Next->T_Next = NULL;
	}
}
void Get_GL_Table_Tail(const struct GL_Table_Node* GLT, struct GL_Table_Node* GLT_Tail)
{
	assert(NULL != GLT && NULL != GLT_Tail);
	struct GL_Table_Node* P_GLT = GLT->T_Next;
	GLT_Tail->Tag = HEAD;
	GLT_Tail->S_Next = NULL;
	GLT_Tail->T_Next = NULL;
#ifdef DEBUG
	Print_GL_Table(GLT);
#endif
	while (NULL != P_GLT->T_Next)
		P_GLT = P_GLT->T_Next;
	GLT_Tail->T_Next = P_GLT;
}
void Insert_GL_Table_Head(struct GL_Table_Node* GLT, const char* List)
{
	struct GL_Table_Node* P_Next = (struct GL_Table_Node*)malloc(sizeof(struct GL_Table_Node));
	struct GL_Table_Node* P_GLT_Head = GLT->T_Next;
	if ('(' == List[0])
	{
		P_Next->S_Next = (struct GL_Table_Node*)malloc(sizeof(struct GL_Table_Node));
		P_Next->Tag = SUBLIST;
		P_Next->S_Next->Tag = HEAD;
		P_Next->S_Next->S_Next = NULL;
		P_Next->S_Next->T_Next = NULL;
		Create_GL_Table(P_Next->S_Next, List);
	}
	else
	{
		P_Next->Tag = ATOM;
		P_Next->element = atoi(List);
	}
	P_Next->T_Next = NULL;
	GLT->T_Next = P_Next;
	P_Next->T_Next = P_GLT_Head;
}
void Insert_GL_Table_Tail(struct GL_Table_Node* GLT, const char* List)
{
	struct GL_Table_Node* P_Next = (struct GL_Table_Node*)malloc(sizeof(struct GL_Table_Node));
	struct GL_Table_Node* P_GLT_Tail = GLT->T_Next;
	while (NULL != P_GLT_Tail->T_Next)
		P_GLT_Tail = P_GLT_Tail->T_Next;
	if ('(' == List[0])
	{
		P_Next->S_Next = (struct GL_Table_Node*)malloc(sizeof(struct GL_Table_Node));
		P_Next->Tag = SUBLIST;
		
		P_Next->S_Next->Tag = HEAD;
		P_Next->S_Next->S_Next = NULL;
		P_Next->S_Next->T_Next = NULL;
		Create_GL_Table(P_Next->S_Next, List);
	}
	else
	{
		P_Next->Tag = ATOM;
		P_Next->element = atoi(List);
	}
	P_Next->T_Next = NULL;
	P_GLT_Tail->T_Next = P_Next;
}
void Delete_GL_Table_Head(struct GL_Table_Node* GLT)
{
	struct GL_Table_Node* P_GLT = GLT->T_Next;
	GLT->T_Next = P_GLT->T_Next;
	free(P_GLT);
}
void Delete_GL_Table_Tail(struct GL_Table_Node* GLT)
{
	struct GL_Table_Node* P_GLT = GLT->T_Next;
	struct GL_Table_Node* P_B_GLT = GLT;
	while (NULL != P_GLT->T_Next)
	{
		P_B_GLT = P_GLT;
		P_GLT = P_GLT->T_Next;
	}
	free(P_GLT);
	P_GLT = NULL;
	P_B_GLT->T_Next = NULL;
}
void Clean_GL_Table(struct GL_Table_Node* GLT)
{
	struct GL_Table_Node* P_GLT = GLT;
	while (NULL != P_GLT)
	{
		struct GL_Table_Node* P_B_GLT = P_GLT->T_Next;
		if (SUBLIST == P_GLT->Tag)
			Clean_GL_Table(P_GLT->S_Next);
		
		free(P_GLT);
		P_GLT = P_B_GLT;
	}
	GLT->T_Next = NULL;
}
void Destroy_GL_Table(struct GL_Table_Node* GLT)
{
	Clean_GL_Table(GLT->T_Next);
	GLT->T_Next = NULL;
}
Generalized_Table_main.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"Generalized_Table_.h"
int main()
{
	int option = 0;
	char List[MAX_SPACE] = { '\0'};
	struct GL_Table_Node GLT_N;
	struct GL_Table_Node GLT_S;
	Init_GL_Table(&GLT_N);
	Show_Menu();
	while (printf("\n选项为>"), scanf("%d", &option), option)
	{
		getchar();// 截断字符缓冲区的换行符
		switch (option)
		{
		case 1:
			printf("输入为>");
			scanf("%s", List);
			Create_GL_Table(&GLT_N,List);
			break;
		case 2:
			Print_GL_Table(&GLT_N);
			break;
		case 3:
			printf("需拷贝的输入为>");
			scanf("%s", List);
			Create_GL_Table(&GLT_S, List);
			Copy_GL_Table(&GLT_N, &GLT_S);
			break;
		case 4:
			printf("%d",Get_GL_Table_Length(&GLT_N));
			break;
		case 5:
			printf("%d", Get_GL_Table_Depth(&GLT_N));
			break;
		case 6:
			Get_GL_Table_Head(&GLT_N, &GLT_S);
			Print_GL_Table(&GLT_S);
			break;
		case 7:
			Get_GL_Table_Tail(&GLT_N, &GLT_S);
			Print_GL_Table(&GLT_S);
			break;
		case 8:
			printf("插入元素为>");
			scanf("%s", List);
			Insert_GL_Table_Head(&GLT_N, List);
			break;
		case 9:
			printf("插入元素为>");
			scanf("%s", List);
			Insert_GL_Table_Tail(&GLT_N, List);
			break;
		case 10:
			Delete_GL_Table_Head(&GLT_N);
			break;
		case 11: 
			Delete_GL_Table_Tail(&GLT_N);
			break;
		case 12:
			Clean_GL_Table(GLT_N.T_Next);
			break;
		case 13:
			Destroy_GL_Table(&GLT_N);
			break;
		default: printf("不在选择范围内\n");
		}
		Show_Menu();
	}
	Destroy_GL_Table(&GLT_N);
	printf("已退出\n");
	return 0;
}