guangyibiao.cpp

广义表的创建以及相关操作。

#include"stdio.h"
#include"stdlib.h"
#include"string.h"
typedef char AtomType;
//typedef enum{ATOM,LIST}ElemTag;
typedef 	union
	{
		AtomType atom;
		struct
		{
			 struct GLNode *hp,*tp;
		}htp;
	}atomhtp;
typedef struct GLNode
{
	//ElemTag tag;
	int tag;
    atomhtp atom_htp;
}GLNode,*GList;

//分离字符串
void SeverString(char s1[],char s2[])
{
	int len=strlen(s1);
	int i=0;
	while(s1[i]!=',' && i<len )//i为第一个逗号的下标
	{
		i++;
	}
	if(i==len)//没有逗号
	{
		strcpy(s2,s1);
		strcpy(s1,"()");
		//s1[0]='\0';
	}
	else//找到了逗号
	{
		for(int j=0;j<i;j++)s2[j]=s1[j];
		s2[j]='\0';
		s1[0]='(';
		for(j=1;j<len-i;j++)s1[j]=s1[j+i];
		s1[len-i]=')';
		s1[len-i+1]='\0';
	}
}

//去外层括号
void QuKuoHao(char s[])
{
	int len=strlen(s);
	for(int i=0;i<len-2;i++)s[i]=s[i+1];
	s[i]='\0';
}

//求广义表的表头，并返回表头指针
GList Head(GList L)
{
	if(L==NULL)return(NULL);
	if(L->tag==0)exit(0);
	else return(L->atom_htp.htp.hp);
}

//求广义表的表尾，并返回表尾指针
GList Tail(GList L)
{
	if(L==NULL)return(NULL);
	if(L->tag==0)exit(0);
	else return(L->atom_htp.htp.tp);
}

//求广义表的长度，并返回长度
int Length(GList L)
{
	int k=0;
	GLNode *s;
	if(L==NULL)return(0);
	if(L->tag==0)exit(0);
	s=L;
	while(s!=NULL)
	{
		k++;
		s=s->atom_htp.htp.tp;//遍历广义表,遍历次数即广义表的长度
	}
	return(k);
}

//求广义表的深度
int Depth(GList L)
{
	int d,max;
	GLNode *s;
	if(L==NULL)return(1);
	if(L->tag==0)return(0);
	s=L;
	max=0;
	while(s!=NULL)            //求每个广义表的深度的最大值
	{
		d=Depth(s->atom_htp.htp.hp);
		if(d>max) max=d;
		s=s->atom_htp.htp.tp;
	}
	return(max+1); 
}

//统计广义表中原子数目
int CountAtom(GList L)
{
	int n1,n2;
	if(L==NULL)return(0);
	if(L->tag==0)return(1);
	n1=CountAtom(L->atom_htp.htp.hp);
    n2=CountAtom(L->atom_htp.htp.tp);
	return(n1+n2);
}

//复制广义表
int CopyGList(GList S,GList *T)
{
	if(S==NULL)
	{
		*T=NULL;
		return(1);
	}
	*T=(GLNode *)malloc(sizeof(GLNode));
	if(*T==NULL)return(0);
	(*T)->tag=S->tag;
	if(S->tag==0)(*T)->atom_htp.atom=S->atom_htp.atom;//课本此处错了！
	else
	{
		CopyGList(S->atom_htp.htp.hp,&((*T)->atom_htp.htp.hp));
		CopyGList(S->atom_htp.htp.tp,&((*T)->atom_htp.htp.tp));
	}
	return(1);
}     
 
//创建广义表
/*void CreateGList(GList *g,char s[])
{
	//puts(s);
	if(!strcmp(s,"()"))*g=NULL;
	else
	{
		*g=(GList)malloc(sizeof(GLNode));printf("分配一次内存成功");	//&(q->atom_htp.htp.hp)
	    //puts(s);
		
		if(strlen(s)==1)
		{
			(*g)->tag=0;
			(*g)->atom_htp.atom=s[0];
		}
		else
		{
			(*g)->tag=1;
            GList q=(*g)->atom_htp.htp.hp;
			GList w=(*g)->atom_htp.htp.tp;
			QuKuoHao(s);
			//if(s[0]!='(')
			//{
				char s2[40];
				SeverString(s,s2);
				//printf("%s",s);
				CreateGList(&q,s2);
				CreateGList(&w,s);*/
			//}
			/*else
			{
				w->tag=1;
				CreateGList(&(w->atom_htp.htp.hp),s);
			}*/
		/*}
	}
}*/
char ch1;
GList CreateGList()
{
	GList g;char ch,ch2;
	scanf("%c",&ch);
	ch2=ch;	
	if(ch==' ')g=NULL;
	else if(ch=='(')
	{
		scanf("%c",&ch);ch1=ch;
		if(ch==' ')g=NULL;
		else
		{
			g=(GList)malloc(sizeof(GLNode));
			g->tag=1;
			g->atom_htp.htp.hp=CreateGList();
			if(ch2==',')
			{
				GList g1;
				g1=(GList)malloc(sizeof(GLNode));
				g1->tag=1;
				g1->atom_htp.htp.hp=CreateGList();
				g->atom_htp.htp.tp=g1;
			}
			else g->atom_htp.htp.tp=NULL;
		}


	}
	else 
	{
		g=(GList)malloc(sizeof(GLNode));;
		g->tag=0;
		g->atom_htp.atom=ch1;g->atom_htp.htp.tp=NULL;
	}
	return(g);
}



void main()
{
	GList glist;
	//SString string;
	//char s[40];
	printf("请输入广义表，例如：(a,(b,c))");
	glist=CreateGList();
	//gets(s);
	//printf("原子个数是：%d",CountAtom(glist));
	//CreateGList(&glist,s);
	//printf("\n创建成功\n");
	printf("原子个数是：%d",CountAtom(glist));
	//printf("\n度%d",Depth(glist));
}