广义表的学习

一、广义表的定义

• 先举例说明：中国举办的国际足球邀请赛，参赛队名单表示如下：
• （阿根廷，巴西，德国，法国，（），西班牙，意大利，英国，（国家队，山东鲁能，广州恒大））这个表中，叙利亚队应排在法国队后面，但未能参加，成为空表。国家队，山东鲁能，广州恒大均作为东道主的参赛队参加，构成一个小的线性表，成为原线性表的一个数据元素。这种扩宽了的线性表就是广义表。
• 广义表（又称列表Lists）是n>=0个元素a0，a1,....an-1的有限序列，其中每一个aj或者是原子，或者是一个广义表。 
• 广义表通常记作：LS=（a1,a2,...an）其中：LS为表名，n为表的长度，每一个ai为表的元素。
• 习惯上，一般用大写字母表示广义表，小写字母表示原子。
• 表头：若LS非空（n>=1）则其第一个元素a1就是表头。记作head(LS)=a1。注：表头可以是原子，也可以是子表。
• 表尾：除了表头之外的其它元素组成的表。记作tail(LS)=(a2,....an)。注：表尾不是最后一个元素，而是一个子表

例：
（1）A=( )     空表，长度为0
（2）B=(( ))   有一个元素（该元素为空表），所以长度为1。表头，表尾均为（）
（3）C=(a,(b,c)) 长度为2，由原子a和子表(b,c)构成。表头为a，表尾为((b,c))
注意：(b,c)加括号((b,c))表示的是表尾是一个广义表，广义表里有一个元素是(b,c)
如果不加括号,(b,c)表示的是表尾是一个广义表，广义表里面有b,c两个元素
（4）D=(x,y,z)  长度为3，每一项都是原子。表头是x，表尾为(y,z)
（5）E=(C,D) 长度为2，每一项都是子表。表头为C，表尾为(D)
（6）F=(a,F)  长度为2，每一项为原子，第二项为它本身。表头为a，表尾为(F)。
实际上，F=(a,(a,(a,..)))

二、广义表的性质

1. 广义表中的数据元素由相对次序；一个直接前驱和一个直接后继。
2. 广义表的长度定义为最外层所包含元素的个数；如，C=(a,(b,c))是长度为2的广义表。
3.  广义表的深度定义为该广义表展开后所含括号的重数；
   例如：A=(b,c)的深度为1----只有1层括号
   B=(A,d)的深度为2----因为B=((b,c),d)，有2层括号
   C=(f,B,h)的深度为3----因为C=(f,((b,c),d),h)，有3层括号
   注意：“原子”的深度为0，“空表的深度为1”
4. 广义表可以为其他广义表共享；如：广义表B就共享表A。在B中不必列出A的值，而是通过名称来引用，B=(A)
5. 广义表可以是一个递归的表。如：F=(a,F=(a,(a,(a,..))))注意：递归的深度是无穷值，长度是有限值。
6. 广义表是多层次结构，广义表的元素可以是单元素，也可以是子表，而子表的元素还可以是子表，..。例如：D=(E,F) 其中：E=(a,(b,c))，F=(d,(e)) 
7. 广义表和线性表的区别：
   广义表可以看成是线性表的推广，线性表是广义表的特例。

三、广义表的2种常见的存储结构 

• 广义表中的数据元素可以具有不同的结构（原子或广义表），难以用顺序存储结构表示，通常采用链式存储，将广义表分解为表头和表尾，对表头和表尾再次分解，直到分解到空的广义表或是一个具体的原子，分解结束。 

 头尾表示法：

• 分解后的表头和表尾各用一个结点表示，显然表头可能为原子或列表（表尾肯定是列表），所以需要两种结构的节点：一种是表结点，一种是原子结点。其中变量tag用来区分表结点和原子结点。
• 表结点：包括标志域(tag)，指向表头的指针域(hp),指向表尾的指针域(tp)
• 原子结点：包括标志域(tag)，值域(atom)  

 

 存储结构类型：

typedef int AtomType;
typedef enum
{
	ATOM,LIST
}ELemTag;//ATOM=0原子结点，LIST=1子表
 
typedef struct GLNode
{
	AtomType tag;//区分原子结点和表结点的类型参数
	union
	{
	   AtomType atom;//原子结点的值域
	   struct
	   {
		struct GLNode* hp,* tp;
		}htp;
	}atom_htp;//atom_ptr是原子结点的值域atom，表结点的表头指针hp，表尾指针tp的联合体域
}GLNode,*GList;

 

bool Init(GList &L)//初始化，建立一个空的广义表
{
	L = NULL;
	return true;
}
 
bool CreatGList(GList &L,SString S,char*a)//建立广义表
{
	L = (GList)malloc(sizeof(GList));//建立表结点
	if (StrLen(S) == 1)
	{
		L->tag = ATOM;
		(L->atom_htp).atom = a[1];//S为单原子，创建单原子广义表
	}
	else
	{
		SString sub
		L->tag = LIST;
		GLNode* p = L;
		SubString(S, sub, 2, StrLen(S)-2);//
	}
 
}
 
GList Head(GList L)//求广义表的表头
{
	if (L == NULL)//空表无表头
	{
		return NULL;
	}
	if (L->tag == ATOM)//如果是原子结点则不是表
	{
		exit(0);
	}
	else
	{
		return L->atom_htp.htp.hp; 
	}
}
 
GList Tail(GList L)//求广义表的表尾
{
	if (L == NULL)
	{
		return NULL;
	}
	if (L->tag == ATOM)
	{
		exit(0);
	}
	else
	{
		return L->atom_htp.htp.tp;
	}
}
 
int Length(GList L)//求广义表的长度
{
	if (L == NULL)
	{
		return 0;
	}
	if (L->tag == ATOM)
	{
		exit(0);
	}
	GList p = L;
	int count = 0;
	while (p != NULL)
	{
		count++;
		p = p->atom_htp.htp.hp;//寻找下一个表结点
	}
}
 
int Depth(GList L)//求广义表的深度
{
	if (L == NULL)
	{
		return 1;//空表深度为1
	}
	if (L->tag == ATOM)
	{
		return 0;//原子结点的深度为0
	}
	GLNode* p = L;
	int d, max;
	while (p != NULL)
	{
		p = p->atom_htp.htp.hp;//进入下一个表结点
		d = Depth(p);//寻找下一个表结点的深度
		if (d > max)
		{
			max = d;
		}
		p = p->atom_htp.htp.hp;//继续寻找下下一个表节点
	}
	return max + 1;
 
}
 
int CountAtom(GList L)//统计广义表中原子结点的数目
{
	int n1 = 0, n2 = 0;//分别计算表头，表尾中原子数目个数
	if (L == NULL)
	{
		return 0;
	}
	if (L->tag == ATOM)
	{
		return 1;
	}
	n1 = CountAtom(L->atom_htp.htp.hp);
	n2 = CountAtom(L->atom_htp.htp.tp);
	return (n1 + n2);
}

四、关于广义表的取“表头”“表尾”

#include
#include
#include
#include
#include
using namespace std;
typedef struct {
    char* ch;                  // 先存放非空串的首地址，不分配内存
    int Length;                  // 存放串的当前长度
}SString;         
bool StrInit(SString& S);//初始化
bool StrAssign(SString& S, char* chars);//一个字符串常量赋值给顺序串S
bool StrCopy(SString& S, SString T);//将T串拷贝给S串
bool SubString(SString S, SString& T, int pos, int len);//取子串,此处pos代表元素下标
int StrLen(SString S);//求串长
bool Print(SString S);//打印
bool sever(SString &sub, SString& head);//从串T中分离出头串head
//将非空串T分割成两部分：head为第一个','之前的子串，T为之后的子串
bool StrInit(SString& S)//初始化
{
	S.ch = NULL;
	S.Length = 0;
	return true;
}
bool StrAssign(SString& S, char* chars)//一个字符串常量赋值给顺序串S
{
	int i, j;
	char* c;
	for (i = 0, c = chars; *c; i++, c++);//计算一个字符串常量的长度
	if (i == 0)//说明字符串常量是0，就不用给SString开辟空间
		return false;
	else
	{
		S.ch = (char*)malloc(i * sizeof(char));//申请空间
		if (S.ch == NULL)
		{
			exit(0);
		}
		for (j = 0; j < i; j++)
		{
			S.ch[j] = chars[j];
			S.Length = i;
		}
	}
	return true;
}
 
bool StrCopy(SString& S, SString T)//将T串拷贝给S串
{
	if (S.ch != NULL)//先释放掉原来的空间
	{
		S.ch = NULL;
		free(S.ch);//注意此处虽然free函数进行了动态内存的释放和回收，但实际中未完全释放，S.ch依然会指向
		//动态开辟的空间，而非指向NULL。当第一次使用完空间，如果未退出继续运行代码，再次赋值就会发生错误，
		//只需在free函数前把S.ch进行赋值NULL操作即可
	}
	if (S.Length != 0)
	{
		StrInit(S);
	}
	for (int i = 0; i < T.Length; i++)
	{
		S.ch = (char*)malloc(T.Length * sizeof(char));
		if (S.ch == NULL)
			return false;
		S.ch[i] = T.ch[i];
		S.Length = T.Length;
 
	}
	return true;
}
 
 
bool SubString(SString S, SString& T, int pos, int len)//取子串,此处pos代表元素下标
{
	if (pos<0 || pos>S.Length - 1 || len<0 || len>S.Length - pos)
		return false;
	else
	{
		if (T.ch != NULL)
		{
			T.ch = NULL;
			free(T.ch);
		}
		if (T.Length != 0)
			StrInit(T);
		int i;
		T.ch = (char*)malloc(len * sizeof(char));
		if (T.ch == NULL)
			return false;
		for (i = 0; i < len; i++)
		{
			T.ch[i] = S.ch[pos + i];
			T.Length = len;
		}
		return true;
	}
	return true;
}
 
int StrLen(SString S)//求串长
{
	return S.Length;
}
 
bool Print(SString S)//打印
{
	for (int i = 0; i < S.Length; i++)
	{
		cout << S.ch[i];
	}
	cout << endl;
	return true;
}
 
 
bool sever(SString &sub, SString& head)//从T串中分离出头串head
//注意sever处理的是已经除去最外层括号的串
{
	int n = StrLen(sub);
	int i = 0, k=0 ;//k记尚未配对的左括号个数
	for(i=0;i
	{
		char ch = sub.ch[i];
		if (ch == '(')
		{
			k++;
		}
		else if (ch == ')')
		{
			k--;
		}
		if(ch==','&&k==0)
		{
			break;
		}
	} //找到第一个','之前的子串的的条件的出现1个左括号
	//和第一个','
		if (i < n)
		{
			SubString(sub, head, 0, i);
			SubString(sub, sub, i + 1, n - (i+1));
		}
		else//串中只有一个字符（单原子）的时候
		{
			StrCopy(head, sub);
			free(sub.ch);
			StrInit(sub);
			sub.ch = (char*)malloc(50 * sizeof(char));
		}
		return true;
}
int main()
{
 
	SString S1;
	StrInit(S1);
	S1.ch = (char*)malloc(50 * sizeof(char));
	char a[] = "(a,(b,d,e,f))";
	StrAssign(S1, a);//一个字符串常量赋值给顺序串S1
	cout << StrLen(S1) << endl;
	SString head;//用于保留分割后的表头
	StrInit(head);
	head.ch = (char*)malloc(100 * sizeof(char));
	SubString(S1, S1, 1, StrLen(S1) - 2);//除去串的最外层括号
	sever(S1, head);
	cout << "第一个逗号之前的元素（除了第一个左括号）" << endl;;
	Print(head);
	cout << "第一个逗号之后的元素（除了最后一个右括号）" << endl;
	Print(S1);
	return 0;
}