博客

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
typedef char DataType;
typedef struct GListNode
{
	int tag;	
	union
	{
		DataType atom;//原子域 
		struct
		{
			struct GListNode *head;//头指针域 
			struct GListNode *tail;//尾指针域 
		}subList;//子表域 
	}val;
}GLNode;
void DecomposeStr(char str[],char hstr[])//拆分表头表尾 
{
	int i,j,tag,n=strlen(str);
	char ch;
	ch=str[0];tag=0;
	for(i=0;i<=n-1;i++)
	{
		if(str[i]==','&&tag==1)
		{
			break;
		}
		ch=str[i];
		if(ch=='(')
		tag++;
		if(ch==')')
		tag--;
	}
	if(i<=n-1&&str[i]==',')
	{
		for(j=0;j<i-1;j++)
		{
		hstr[j]=str[j+1];
		}
		hstr[j]='\0';
		if(str[i]==',')i++;
		str[0]='(';
		for(j=1;i<=n-2;i++,j++)
		str[j]=str[i];
		str[j]=')';
		str[++j]='\0';
	}
	else
	{
		str++;
		strncpy(hstr,str,n-2);
		hstr[n-2]='\0';
		str--;
		strcpy(str,"()");
	}
}
GLNode *CreatGList(char str[])//创建广义表 
{
	GLNode *h;
	char hstr[200];
	int len=strlen(str);
	if(strcmp(str,"()")==0)
	h=NULL;
	else if(len==1)
	{
		h=(GLNode*)malloc(sizeof(GLNode));
		h->tag=0;
		h->val.atom=str[0];
	}
	else
	{
		h=(GLNode*)malloc(sizeof(GLNode));
		h->tag=1;
		DecomposeStr(str,hstr);	
		h->val.subList.head=CreatGList(hstr);
		if(strcmp(str,"()")!=0)
		{
			h->val.subList.tail=CreatGList(str);
		}
		else
		{
			h->val.subList.tail=NULL;
		}		
	}
	return h;
}
int GListDepth(GLNode *h)
{
	int max,dep;
	GLNode *pre;
	if(h==NULL)return 1;
	if(h->tag==0)return 0;
	pre=h;
	for(max=0;pre!=NULL;pre=pre->val.subList.tail)
	{
		dep=GListDepth(pre->val.subList.head);
		if(dep>max)max=dep;
	}
	return max+1;
}
int GListLength(GLNode *h)
{
	int number=0;
	GLNode *p;
	for(p=h;p!=NULL;p=p->val.subList.tail)
	number++;
	return number;
}
int GListAtomNum(GLNode *h)
{
	if(h==NULL)return 0;
	else
	{
		if(h->tag==0)return 1;
		else
		{
			return GListAtomNum(h->val.subList.head)+GListAtomNum(h->val.subList.tail);
		}
	}
}
GLNode *GListSearch(GLNode *h,DataType x)
{
	GLNode *p;
	if(h==NULL)return NULL;
	if(h->tag==0&&h->val.atom==x)return h;
	if(h->tag==1&&h->val.subList.head!=NULL)
	{
		p=GListSearch(h->val.subList.head,x);
		if(p!=NULL)return p;
	}
	if(h->tag==1&&h->val.subList.tail!=NULL)
	{
		p=GListSearch(h->val.subList.tail,x);
		if(p!=NULL) return p;
	}
	return NULL;
	
}
void DestroyGList(GLNode *h)
{
	if(h==NULL)return;
	if(h->tag==1&&h->val.subList.head!=NULL)
	DestroyGList(h->val.subList.head);
	if(h->tag==1&&h->val.subList.tail!=NULL)
	DestroyGList(h->val.subList.tail);
	free(h);
}
int main()
{
	char str1[]="(((a,b,c),(d)),e)";
	char str2[]="(((a,b,c),(d)),e)";
	char hstr[100];
	GLNode *h,*p;
	int depth,number,length;
	h=CreatGList(str1);
	printf("广义表str1=%s",str2);
	DecomposeStr(str2,hstr);
	printf("\n表头=%s",hstr); 
	printf("     表尾=%s",str2);
	depth=GListDepth(h);
	printf("\n深度depth=%d",depth);
	length=GListLength(h);
	printf("\n长度length=%d",length);
}