广义表.txt

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

#include"stdio.h"
#include"stdlib.h"
#include"string.h"
typedef char AtomType;
typedef enum{ATOM,LIST}ElemTag;
typedef struct GLNode
{
	ElemTag tag;
	union
	{
		AtomType atom;
		struct
		{
			 struct GLNode *hp,*tp;
		}htp;
	}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);
		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==ATOM)exit(0);
	else return(L->atom_htp.htp.hp);
}

//求广义表的表尾，并返回表尾指针
GList Tail(GList L)
{
	if(L==NULL)return(NULL);
	if(L->tag==ATOM)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==ATOM)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==ATOM)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==ATOM)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==ATOM)(*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[])
{
	*g=(GList)malloc(sizeof(GLNode));
	if(!strcmp(s,"()"))
	{
		(*g)->tag=LIST;
		(*g)->atom_htp.htp.hp=NULL;
		(*g)->atom_htp.htp.tp=NULL;
	}
	else if(strlen(s)==1)
	{
		(*g)->tag=ATOM;
		(*g)->atom_htp.atom=s[0];
	}
	else
	{
		QuKuoHao(s);
		char s2[40];
		SeverString(s,s2);
		CreateGList(&((*g)->atom_htp.htp.hp),s2);
		CreateGList(&((*g)->atom_htp.htp.tp),s);
	}
}

void main()
{
	GList glist;
	//SString string;
	char s[40];
	printf("请输入广义表，例如：(a,(b,c))");
	gets(s);
	/*int flag=1;
	char ch;
	int i=0;
	while(flag)
	{
		scanf("%c",&ch);
		if(ch!='\n')
		{
			string.ch[i++]=ch;
		    string.len=i;
		}
		else flag=0;
	}*/
	//gets(string.ch);
	//string.len=strlen(string.ch);
	//CreateGList(&glist,string);
	//printf("原子个数是：%d",CountAtom(glist));
	CreateGList(&glist,s);
	printf("\n创建成功\n");
	printf("原子个数是：%d",CountAtom(glist));
	printf("\n长度%d",Length(glist));

}




/*typedef struct
{
	char ch[40];
	int len;
}SString;

void StrCopy(SString *s,SString t)
{
	int i;
	for(i=0;i<t.len;i++)s->ch[i]=t.ch[i];
	s->len=t.len;
}

int StrEmpty(SString s)
{
	if(s.len==0)return(1);
	else return(0);
}

int StrCompare(SString s,SString t)
{
	int i;
	for(i=0;i<s.len&&i<t.len;i++)
		if(s.ch[i]!=t.ch[i])return(s.ch[i]-t.ch[i]);
	return(s.len-t.len);
}

int StrLength(SString s)
{
	return(s.len);
}

void StrClear(SString *s)
{
	s->len=0;
}

int SubString(SString *sub,SString s,int pos,int len)
{
	int i;
	if(pos<0||pos>s.len||len<1||len>s.len-pos)
	{
		sub->len=0;
		return(0);
	}
	else
	{
		for(i=0;i<len;i++)
			sub->ch[i]=s.ch[i+pos];
		sub->len=len;
		return(1);
	}
}

void ClearString(SString *s)
{
	s->len=0;
}

void sever(SString *str,SString *hstr)
{
	SString ch;
	int n,i,k;
	n=StrLength(*str);
	i=0;k=0;
	do
	{
		++i;
		SubString(&ch,*str,i,1);
		if(ch.ch=="(")++k;
		else if(ch.ch==")")--k;
	}while(i<n&&(ch.ch!=","||k!=0));
	if(i<n)
	{
		SubString(hstr,*str,1,i-1);
		SubString(str,*str,i+1,n-i);
	}
	else
	{
		StrCopy(hstr,*str);
		ClearString(str);
	}
}*/


//GList p,q;
//SString hsub;
//SString sub;

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                         
//创建广义表,广义表字符串存在S中
//int CreateGList(GList *L,SString S)
//{
	/*SString emp;
	emp.len=2;
	emp.ch[0]='(';
	emp.ch[1]=')';
	emp.ch[2]='\0';*/
	/*if(!strcmp(S.ch,"()")){printf("正在给L赋值为空\n");*L=NULL;}
	else
	{
		L=(GList *)malloc(sizeof(GLNode));
		printf("分配空间了已经\n");
		if(StrLength(S)==1)
		{
			(*L)->tag=ATOM;
			(*L)->atom_htp.atom=S.ch[0];
		}
		else
		{
			//(*L)->tag=LIST;
			printf("进入else");
			p=*L;    //p没有定义,定义一个全局变量
			SubString(&sub,S,1,strlen(S.ch)-2);//sub没有定义
			do
			{printf("进入do");
				sever(&sub,&hsub);   //hsub没有定义
				printf("准备进入递归创建\n");
				CreateGList(&(p->atom_htp.htp.hp),hsub);
				q=p;
				if(!StrEmpty(sub))
				{
					free(p);
					p=(GLNode *)malloc(sizeof(GLNode));
					p->tag=LIST;
					q->atom_htp.htp.tp=p;
				}
			}while(!StrEmpty(sub));
			q->atom_htp.htp.tp=NULL;
		}
	}
	return(1);
}*/
//GList q;