数据结构之---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;
}