最终的广义表.cpp

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

//今天是4月13日晚11点半：工作记录：
//存在一个问题：如果输入的广义表形式是：((a,b),(c,d))，则输出结果的头结点是向上的一个箭头。可见此创建方法只
//适用于头结点为原子的情况。若想让上面的情况也使用，必须修改创建算法。
//本程序花费了我很长的时间，主要原因在于对递归的用法不熟练，联合（union）开始也忘了。
//本程序采用的是广义表的头位链表存储方式，没有用老师程序中的扩展存储方式。
//另外，还没有写打印广义表的子函数。抽时间再写。还要把主函数完善一下，用上复制等函数，做得像二叉树程序一样。
//现在是4月14日下午，我添加了打印函数。
#include"stdio.h"
#include"stdlib.h"
#include"string.h"
#include"malloc.h"//这个头文件可以不要
	/*typedef union
	{
		char atom;
		struct
		{
			 struct GLNode *hp,*tp;
		}htp;
	}atomhtp;*///不知道为什么如果不这样写，编译器就无法识别出htp的内容hp和tp来，但是却没有错误，也可以运行。
typedef struct GLNode
{
    int tag;
	union
	{
		char atom;
		struct
		{
			 struct GLNode *hp,*tp;
		}htp;
	}atom_htp;
	//atomhtp atom_htp;
}GLNode,*GList;

//功能：从字符串s2中下标为pos起，把len个字符取出来赋给字符串s1
void SubString(char s1[],char s2[],int pos,int len)
{
	int i;
	int length=strlen(s2);
    if(pos<0||pos>=length||len<1||len>length-pos)
		//s1="";
		s1[0]='\0';
	else
	{
		for(i=0;i<len;i++)
			s1[i]=s2[i+pos];
		s1[i]='\0';
	}
}

//功能：将字符串s1的第一个逗号之前的部分赋给s2，s1为除去这部分和这个逗号剩下的部分。
//如果s1中没有逗号或者s1的最外层是一对括号，则s2为s1，s1变为空串。
void SeverString(char s1[],char s2[])
{
	char ch[2];
	int len=strlen(s1);
	int i=0,k=0;
	do
	{
		SubString(ch,s1,i,1);
		i++;
		if(ch[0]=='(')k++;
		else if(ch[0]==')')k--;
	}while(i<len && (ch[0]!=','||k!=0));
	if(i<len)
	{
		SubString(s2,s1,0,i-1);
		SubString(s1,s1,i,len-i);
	}
	else
	{
		strcpy(s2,s1);
		//s1="";
		s1[0]='\0';
	}
}
	
//传递字符串s，创建广义表，用指针L带回。
void CreateGList(GList *L,char s[])
{
	GList p,q;
	char s1[40],s2[40];
	if(s=="( )")L=NULL;
	else
	{
		(*L)=(GList)malloc(sizeof(GLNode));
		if(strlen(s)==1)
		{
			(*L)->tag=0;
			(*L)->atom_htp.atom=s[0];
		}
		else
		{
			(*L)->tag=1;
			p=(*L);
			SubString(s1,s,1,strlen(s)-2);
			do
			{
				SeverString(s1,s2);
				CreateGList(&(p->atom_htp.htp.hp),s2);
				q=p;
				if(s1[0]!='\0')
				{
					p=(GList)malloc(sizeof(GLNode));
					p->tag=1;
					q->atom_htp.htp.tp=p;
				}
			}while(s1[0]!='\0');
			q->atom_htp.htp.tp=NULL;
		}
	}
}

//求广义表的表头，并返回表头指针
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 Print_GList(GList g)
{
	
	if(g==NULL)printf("( )");
	if(g->tag==0)printf("%c",g->atom_htp.atom);
	else
	{
		if(g->atom_htp.htp.tp==NULL)
		{
			Print_GList(g->atom_htp.htp.hp);
			printf(")");
		}
		else
		{
			Print_GList(g->atom_htp.htp.hp);
			printf(",");
			if(((g->atom_htp.htp.tp)->atom_htp.htp.hp)->tag==1)printf("(");
            Print_GList(g->atom_htp.htp.tp);
		}
	}
}

//这就是上面所说的那个函数，它通过单独打印一个左括号和调用Print_GList()函数，实现了完整的打印广义表的目的。
void PrintGList(GList g)
{
	printf("(");
	Print_GList(g);
}



void main()
{
	GList g;
	char s[40];
	printf("请输入要创建的广义表的形式，例如：(a,(b,c))\n");
	gets(s);
	CreateGList(&g,s);
	printf("头结点是%c\n",Head(g)->atom_htp.atom);
	printf("原子个数是：%d\n",CountAtom(g));
	printf("长度是：%d\n",Length(g));
	printf("深度是:%d\n",Depth(g));
	printf("打印广义表为：");
	PrintGList(g);
}