欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

数据结构之---C语言实现广义表头尾链表存储表示

程序员文章站 2022-03-26 19:27:04
//广义表的头尾链表存储表示 //杨鑫 #include #include #include #include #define maxstrlen 40 ) typedef...
//广义表的头尾链表存储表示
//杨鑫
#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;
}