终极版广义表.cpp

采用表头表尾的存储方式

#include <stdio.h>
#include <malloc.h>
#include <string.h>
#include "stdlib.h"

typedef enum{ATOM,LIST} ElemTag;
typedef struct GLNode
{
   ElemTag tag;
   union
   {
	   int atom;
	   struct{ struct GLNode *hp,*tp;}htp;
   }atom_htp; 
}GLNode,*GList;

GList Head(GList L);
GList Tail(GList L);
int Length(GList L);
int Depth(GList L);
int CountAtom(GList L);
void search_replace(char*S,char*hs);

//*************************************************

void create(GList &ls,char *S)
{   
	char hs[30];
    GList p;
	if(strlen(S)==0||strlen(S)==2) {ls=NULL;return;}
	ls=(GList)malloc(sizeof(GLNode));
	if(strlen(S)==1) 
	  {
	   ls->atom_htp.atom=S[0]; /*一开始输入元素和后来遇到元素的处理不一样，
							   若一开始遇到元素则还要对上一层tp赋空值，后来
							  遇到的元素又不能这样处理，所以在给ls动态分配内存后就统一对tp赋空值*/
       ls->tag=ATOM; 
	   return;
	  }           
	if(strlen(S)>2)  
	{ 
	  p=ls;
	  p->tag=LIST;
      search_replace(S,hs);
	  create(p->atom_htp.htp.hp,hs);
	  create(p->atom_htp.htp.tp,S);
	}

}

void search_replace(char *S,char *hs)

{
	int i=0,j,k=0;
	if(S[0]!='(')	exit(0);
	else if(S[1]!=')')
	{
		do
		{
			if(S[i+1]=='(') k++;
			if(S[i+1]==')') k--;
			hs[i]=S[i+1];
			i++;
		}while(k);
		hs[i]='\0';
		i++;
		if(S[i]==',') i++;
		j=1;
		while(S[i]!='\0') S[j++]=S[i++];
		S[j]='\0';
	}
	else
	{
		hs[0]='\0';
		S[0]='\0';  /*一开始遇到（）和S被取走一些子串后遇到（）处理情况是不一样的，
						为了便于递归，把后来遇到（）的情况统一转化为空串来处理*/
	}
	
}

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

//求广义表L的表尾，并返回表尾指针
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 n=0;
	  int k=0;
	  GLNode *s;
	  if(L==NULL) return(1);
	  if(L->atom_htp.htp.hp==NULL) return 0;/*对()的处理,这里需要说明的一点是：
											为了处理的方便，()的存储方式采用扩
	                                        展线性链表处理方式*/
	  if(L->tag==ATOM) 
	  {
		  printf("it is a atom!\n");  
		  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(0);
	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);
}

//统计广义表L中原子节点数目
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);
}


//主函数
void main()
{
      GList ls,head,tail;
	  int m,n,r;
	  char str[30];
	  printf("input string:eg((a,b).c.g):");
	  gets(str);//支持空格输入	 
	  create(ls,str);
	  printf("该广义表的长度，深度，原子数分别为：\n");
      m=Length(ls);
	  n=Depth(ls);
	  r=CountAtom(ls);
	  printf("%d,%d,%d\n",m,n,r);
	  tail=Tail(ls);
	  printf("该广义表的表尾的长度，深度，原子数分别为：\n");
	  m=Length(tail);
	  n=Depth(tail);
	  r=CountAtom(tail);
	  printf("%d,%d,%d\n",m,n,r);
	  head=Head(ls);
	  printf("该广义表的表头的长度，深度，原子数分别为：\n");
	  m=Length(head);
	  n=Depth(head);
	  r=CountAtom(head);
	  printf("%d,%d,%d\n",m,n,r);
	  
	  
	  
}