數據結構之---C語言實現廣義表頭尾鏈表存儲表示

數據結構之---C語言實現廣義表頭尾鏈表存儲表示

//廣義表的頭尾鏈表存儲表示
//楊鑫
#include 
#include 
#include 
#include 
#define MAXSTRLEN 40 ）
typedef char SString[MAXSTRLEN+1]; 
typedef char AtomType;	                   // 定義原子類型為字符型  
typedef enum{
	ATOM, LIST	                          // ATOM==0:原子 LIST==1:子表                     
} ElemTag; 

typedef struct GLNode
{
	ElemTag tag;				// 公共部分,用於區分原子結點和表結點 
	union								// 原子結點和表結點的聯合部分 
	{
		AtomType atom; 						// atom是原子結點的值域, AtomType由用戶定義 
		struct
		{
			struct GLNode *hp,*tp;
		}ptr;								 // ptr是表結點的指針域,prt.hp和ptr.tp分別指向表頭和表尾 
	}a;
} *GList, GLNode;	


//初始化的廣義表L
int InitGList(GList *L)
{ 
	*L = NULL;
	return 1;
}

//銷毀廣義表L
void DestroyGList(GList *L) 
{ 
	GList q1,q2;
	if(*L)
	{
		if((*L)->tag == ATOM)
		{
			free(*L);								
			*L = NULL;
		}
		else	
		{
			q1 = (*L)->a.ptr.hp;
			q2 = (*L)->a.ptr.tp;
			free(*L);
			*L = NULL;
			DestroyGList(&q1);
			DestroyGList(&q2);						// 遞歸刪除表頭和表尾結點
		
		}
	}
}


// 采用頭尾鏈表存儲結構,由廣義表L復制得到廣義表T。 
int CopyGList(GList *T,GList L)
{
	if(!L)
		*T = NULL;
	else
	{
		*T = (GList)malloc(sizeof(GLNode)); 
		if(!*T)
			exit(0);
		(*T)->tag = L->tag;
		if(L->tag == ATOM)
			(*T)->a.atom = L->a.atom;								// 復制單原子 
		else												// 是表結點，則依次復制表頭和表尾
		{
			CopyGList(&((*T)->a.ptr.hp), L->a.ptr.hp);
			CopyGList(&((*T)->a.ptr.tp), L->a.ptr.tp);
														
			
		}
	}
	return 1;
}

// 返回廣義表的長度,即元素個數
int GListLength(GList L)
{
	int len = 0;
	if(!L)
		return 0;
	if(L->tag == ATOM)
		return 1;
	while(L)
	{
		L = L->a.ptr.tp;	
		len++;
	}
	return len;
}


// 采用頭尾鏈表存儲結構,求廣義表L的深度。
int GListDepth(GList L)
{
	int max, dep;
	GList pp;
	
	if(!L)
		return 1;																	// 空表深度為1
	if(L->tag == ATOM)
		return 0;																			// 原子深度為0
	for(max = 0, pp = L; pp; pp = pp->a.ptr.tp)
	{
																					// 遞歸求以pp->a.ptr.hp為頭指針的子表深度 
		dep = GListDepth(pp->a.ptr.hp);
		if(dep > max)
			max = dep;
	}
	return max+1;															// 非空表的深度是各元素的深度的最大值加1 
}

// 判定廣義表是否為空
int GListEmpty(GList L)
{
	if(!L)
		return 1;
	else
		return 0;
}

// 取廣義表L的頭
GList GetHead(GList L)
{
	GList h,p;

	if(!L)
	{
		printf("空表無表頭!\n");
		exit(0);
	}
	p = L->a.ptr.tp;	
	L->a.ptr.tp = NULL;
	CopyGList(&h,L);
	L->a.ptr.tp = p;
	return h;
}

// 取廣義表L的尾
GList GetTail(GList L)
{
	GList t;
	if(!L)
	{
		printf("空表無表尾!\n");
		exit(0);
	}
	CopyGList(&t, L->a.ptr.tp);
	return t;
}



// 插入元素e作為廣義表L的第一元素(表頭,也可能是子表) 
int InsertFirst_GL(GList *L,GList e)
{
	GList p = (GList)malloc(sizeof(GLNode));
	if(!p)
		exit(0);
	p->tag = LIST;
	p->a.ptr.hp = e;
	p->a.ptr.tp = *L;
	*L = p;
	return 1;
}



// 刪除廣義表L的第一元素,並用e返回其值
int DeleteFirst_GL(GList *L,GList *e)
{ 
	GList p;
	*e = (*L)->a.ptr.hp;	
	p = *L;
	*L = (*L)->a.ptr.tp;	
	free(p);
	return 1;
}



// 利用遞歸算法遍歷廣義表L 
void Traverse_GL(GList L,void(*v)(AtomType))
{
	if(L) 
		if(L->tag == ATOM)
			v(L->a.atom);
		else
		{
			Traverse_GL(L->a.ptr.hp,v);
			Traverse_GL(L->a.ptr.tp,v);
		}
}

// 生成一個其值等於chars的串T
int StrAssign(SString T,char *chars)
{ 
	int i;
	if(strlen(chars) > MAXSTRLEN)
		return 0;
	else
	{
		T[0] = strlen(chars);
		 for(i = 1; i <= T[0]; i++)
			T[i] = *(chars + i - 1);
		return 1;
	}
}

// 由串S復制得串T
int StrCopy(SString T, SString S)
{
	int i;
	for(i = 0; i <= S[0]; i++)
		T[i] = S[i];
	return 1;
}


// 若S為空串,則返回1,否則返回0 
int StrEmpty(SString S)
{
	if(S[0] == 0)
		return 1;
	else
		return 0;
}



// 若S>T,則返回值>0;若S=T,則返回值=0;若SS[0] || len < 0 || len > S[0]-pos+1)
		return 0;
	for(i = 1; i <= len; i++)
		Sub[i]=S[pos+i-1];
	Sub[0] = len;
	return 1;
}


// 將非空串str分割成兩部分:hsub為第一個','之前的子串,str為之後的子串 
void sever(SString str,SString hstr) 
{
	int n,i, k;  
	SString ch,c1,c2,c3;
	n = StrLength(str);
	StrAssign(c1,",");
	StrAssign(c2,"(");
	StrAssign(c3,")");
	SubString(ch,str,1,1);
	for(i = 1,k = 0;i <= n && StrCompare(ch,c1) || k != 0; ++i)
	{ 
		SubString(ch, str, i, 1);
		if(!StrCompare(ch, c2))
			++k;
		else if(!StrCompare(ch,c3))
			--k;
	}
	if(i <= n)
	{
		SubString(hstr, str, 1, i-2);
		SubString(str, str, i, n - i + 1);
	}
	else
	{
		StrCopy(hstr, str);
		ClearString(str);
	}
}


// 廣義表L。設emp="()" 
int CreateGList(GList *L, SString S)
{
	SString sub,hsub,emp;
	GList p,q;
	
	StrAssign(emp,"()");
	if(!StrCompare(S, emp))
		*L = NULL;	// 創建空表 
	else
	{
		*L = (GList)malloc(sizeof(GLNode));
		if(!*L)		// 建表結點 
			exit(0);
		if(StrLength(S) == 1)	// S為單原子 
		{
			(*L)->tag = ATOM;
			(*L)->a.atom = S[1]; // 創建單原子廣義表 
		}
		else
		{
			(*L)->tag = LIST;
			p = *L;
			SubString(sub, S, 2, StrLength(S)-2); // 脫外層括號 
			do
			{	// 重復建n個子表 
				sever(sub, hsub); // 從sub中分離出表頭串hsub 
				CreateGList(&p->a. ptr. hp, hsub);
				q = p;
				if(!StrEmpty(sub))	// 表尾不空 
				{
					p = (GLNode *)malloc(sizeof(GLNode));
					if(!p)
						exit(0);
					p->tag = LIST;
					q->a.ptr.tp = p;
				}
			}while(!StrEmpty(sub));
			q->a.ptr.tp = NULL;
		}
	}
	return 1;
}

// 打印原子 
void visit(AtomType e)
{
	printf("%c ", e);
}

int main()
{
	// 廣義表的表示形式是，空表:(),單原子:a,表:(a,(b),c,(d,(e))) 
	char p[80] = {"(a,(b),c,(d,(e)))"};
	SString t;
	GList L,m;
	
	InitGList(&L);
	InitGList(&m);
	printf("空廣義表L的深度 = %d\nL是否空？%d(1:是 0:否)\n\n",
		GListDepth(L), GListEmpty(L));
	StrAssign(t, p);
	CreateGList(&L, t);											// 創建廣義表 
	printf("\n廣義表L的長度 = %d\n", GListLength(L));
	printf("廣義表L的深度 = %d \nL是否空？%d(1:是 0:否)\n",
		GListDepth(L), GListEmpty(L));
	printf("遍歷廣義表L：\n");
	Traverse_GL(L, visit);
	printf("\n\n復制廣義表m = L\n");
	CopyGList(&m, L);
	printf("廣義表m的長度 = %d\n", GListLength(m));
	printf("廣義表m的深度 = %d\n", GListDepth(m));
	printf("遍歷廣義表m：\n");
	Traverse_GL(m,visit);
	DestroyGList(&m);
	m = GetHead(L);
	printf("\n\nm是L的表頭，遍歷廣義表m：\n");
	Traverse_GL(m, visit);
	DestroyGList(&m);
	m = GetTail(L);
	printf("\n\nm是L的表尾，遍歷廣義表m：\n");
	Traverse_GL(m,visit);
	InsertFirst_GL(&m, L);
	printf("\n\n插入L為m的表頭，遍歷廣義表m：\n");
	Traverse_GL(m,visit);
	printf("\n\n刪除m的表頭，遍歷廣義表m：\n");
	DestroyGList(&L);
	DeleteFirst_GL(&m, &L);
	Traverse_GL(m, visit);
	printf("\n");
	DestroyGList(&m);
	return 0;
}