广义表的表头和表尾.cpp

广义表是线性表的推广。广义表是n个元素的有限序列

//程序在Visual C++ 6.0下编译通过

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

#define CHAR_MAX_LENGTH 100
#define OVERFLOW 0

enum Status {ERROR=0 ,OK};

typedef char AtomType;
typedef enum { ATOM, LIST } ElemTag;	// ATOM==0：原子；LISt==1：子表

typedef  struct  GLNode  
{
	ElemTag		tag;
    union  
	{
		AtomType  	  	atom;
		struct GLNode	*hp;  //表结点的表头指针
    } ptr;
    struct	GLNode		*tp;  //指向下一个元素的指针
}*GList,GLNode;

typedef  struct  
{
	char	*ch;
	int		length;
}HString;

// 以下为函数声明
Status InitGList(GList *L);
GList  CreatGList (HString S);	
int    StrCompare (HString S,HString T);
Status SubString (HString &Sub,HString S,int pos,int len);
Status StrCopy (HString &T,HString S);
Status ClearString (HString  &S);
Status DelString (HString &Str,HString &HStr);
Status PrintGList(GList GL);
Status CopyGList(GList *T,GList L);
GList GetHead(GList L);
GList GetTail(GList L);


void main()
{
	HString S;
	GList GL;
	GList head,tail;

	printf("*** 程序开始前，首先建立广义表! ***\n\n请输入字符串S, 如 (a,b,(c,d))  :");
	if(!(S.ch = (char *)malloc(sizeof(char)*CHAR_MAX_LENGTH)))
		exit(OVERFLOW);     
	scanf("%s",S.ch);
	S.length = strlen(S.ch);
	
	GL = CreatGList (S);

	printf("\n\n新建的广义表如下: \n");
	PrintGList (GL);
	printf("\n广义表的头如下:\n");
	head=GetHead(GL);
	PrintGList(head);
	printf("\n广义表的尾如下:\n");
	tail=GetTail(GL);
	PrintGList(tail);
	printf("\n");

}//end of main() function


Status InitGList(GList *L)
{                            /* 创建空的广义表L */
   *L=NULL;
   return OK;
}


GList CreatGList (HString S )  
// 采用链式存储结构，由广义表的书写形式串 S 创建广义表 GL。设 Emp = "( )"
{
	GList GL; 

	GList p,q;
	HString Sub,HSub;
	Sub.length = 0;
	HSub.length = 0;

	HString Emp;
	Emp.ch=(char *)malloc(2*sizeof(char));
	Emp.ch[0]='(';
	Emp.ch[1]=')';
	Emp.length=2;
	
	if (S.length == 0)    // 如果S为空串，则返回空
		GL = NULL;

	else if ( S.length == 1 )	// 如果 S ="a"，即长度为 1 的单字符串，则创建原子结点的子表
	{
		if ( ! ( GL = ( GLNode *) malloc ( sizeof ( GLNode ) ) ) )  
			exit ( OVERFLOW );
		GL->tag = ATOM;		//创建原子结点  建立一个新结点，且存储空间分配成功
		GL->ptr.atom = S.ch[0];
		GL->tp = NULL;
	} // else if 结束
	else   // 如果 S = (s1, s2, s3, ……, sn)，即长度大于 1 的字符串，则创建子表
	{
		if ( !(GL = ( GLNode*) malloc (sizeof(GLNode))))  
			exit ( OVERFLOW );	// 建立一个新结点，且存储空间分配成功
		GL->tag = LIST;			//创建子表
		p = GL;
		
		SubString ( Sub, S, 1, S.length-2);	//Sub 为脱去 S 中最外层括弧对的子串，即为 "s1, s2, s3, ……, sn"
		q = p;
		
		DelString ( Sub, HSub );	//Sub为“,”之前的子串; HSub为“,”之后的子串
		GList temp = CreatGList (HSub );
		p->ptr.hp = temp;
		p = p->ptr.hp;

		while( Sub.length > 0 )  // 重复建立后面的子表
		{  	
			DelString ( Sub, HSub );	//Sub为“,”之前的子串; HSub为“,”之后的子串
			GList temp = CreatGList (HSub );
			p->tp = temp;
			p = temp;			
		} 
		q->tp = NULL;
	} // else 结束
	return GL;
} // CreatGList

int StrCompare ( HString S,  HString T )  
// 串 S 和 T 从第一个字符开始比较，直到出现第一个不相等的字符：
// 如果 S[i] > T[i]，则 S > T，返回值 > 0；如果 S[i] < T[i]，则 S < T，返回值 < 0；
// 如果 S.length = T.length，且所有字符相等时，S = T，返回值 = 0
{
	int i;
	for  ( i=0; i<S.length && i<T.length; ++i)
		if ( S.ch[i] != T.ch[i] )  
			return S.ch[i]-T.ch[i];
		return ( S.length-T.length );
} // StrCpmpare

Status SubString ( HString &Sub,  HString S,  int pos,  int len )  
// 用 Sub 返回串 S 的第 pos 个字符起长度为 len 的子串
{
	int i;

	if (pos<0||pos>S.length-1 || len<0 || len>S.length-pos)    
		return ERROR;

	if (Sub.length)  
		free (Sub.ch );		// 释放原有空间

	if ( ! len )			// 若 len 为 0，则置空串 Sub
	{
		Sub.ch = NULL;
		Sub.length = 0;
	} // if 结束
    else    // 若 len 非 0，则求子串 Sub
    {
		if (!(Sub.ch=(char *)malloc(len*sizeof(char))))
			exit (OVERFLOW);		
		for(i=0;i<len;i++)	//Sub.ch[ 0 .. len-1] = S[ pos-1 .. pos+len-2 ];
			Sub.ch[i] = S.ch[pos+i];
		Sub.length = len;
	} // else 结束
	
    return OK;
} // SubString

Status StrCopy ( HString &T, HString S )  // 将字符串 S 赋值得到字符串 T
{
	int i;

	if (T.length)  
		free ( T.ch );			// 释放 T 的原有空间

	if ( S.length == 0 )  			// 如果 S.length = 0，则置空串 T
	{
		T.ch = NULL;
		T.length = 0;
	} // if 结束
    else	// 如果 S.length 1 0，则赋值新串 T
	{
		if ( !( T.ch=(char*) malloc (S.length*sizeof(char))))
			exit (OVERFLOW);				
		T.length = S.length;

		for(i=0;i<T.length;i++)
			T.ch[i]=S.ch[i];    //	T.ch[ 0 .. T.length-1] = S[ 0 .. S.length ];
	} // else 结束
    return OK;
} // StrAssign

Status ClearString ( HString  &S )  // 将 S 清为空串
{ 
	if (S.length)  
	{		
		free ( S.ch );
		S.ch = NULL;
	} // if 结束
    S.length = 0;

    return OK;
} // ClearString

Status DelString (HString &Str,  HString &HStr )  
// 将非空串 Str 分割成两部分：HStr 为第一个","之前的子串，Str 为之后的子串
{
	int i,n,k;
	char ch = ' ';
	n = Str.length;
	k = 0;	  // 令 k 记录尚未配对的左括弧个数，初始时为 0

	for ( i=0; i<n && ch!=',' || k!=0;  i++)  
		// 搜索最外层的第一个逗号
	{
		HString Ch;
		Ch.length = 1;
		Ch.ch = (char *)malloc(sizeof(char)*Ch.length);
		SubString ( Ch, Str, i, 1 );	//Ch为Str.ch[i]
		ch = Ch.ch[0];
		if ( ch =='(')  
			k++;
		else if (ch == ')' )  
			k--;
	} // for 结束
	
	if ( i < n )  
	{
		SubString ( HStr, Str, 0, i-1);
		HString Str1;
		Str1.length = 0;
		SubString ( Str1, Str, i, n-i);
		StrCopy(Str,Str1);
	} // if 结束
	else  
	{
		StrCopy ( HStr, Str );
		ClearString (Str);
	} // else 结束

	return OK;
} // DelString


Status PrintGList ( GList GL )  	// 对于给定的广义表链式存储结构，打印出其表示格式
{
	if(!GL)       // 空表返回
	{
		return OK;
	}

	if(GL->tag == LIST)       // 子表
	{
		printf("(");
		
		GList p = GL->ptr.hp;		  // 令 p 指向表头
		PrintGList(p);
		printf(")");				
	}
	else                     // 原子节点
	{
		printf("%c", GL->ptr.atom);
	}

	GList q = GL->tp;			// 令 q 指向后继结点
	if(q)                       // 如果存在后继节点
	{
		printf(",");            
		PrintGList(q);
	}	

	return OK;
} // PrintGList

GList GetHead(GList L)
 { /* 初始条件: 广义表L存在。操作结果: 取广义表L的头 */
   GList h;
   InitGList(&h);
   if(!L||L->tag==LIST&&!L->ptr.hp)
   {
     printf("\n空表无表头!");
     exit(0);
   }
   h=(GList)malloc(sizeof(GLNode));
   if(!h)
     exit(OVERFLOW);
   h->tag=L->ptr.hp->tag;
   h->tp=NULL;
   if(h->tag==ATOM)
     h->ptr.atom=L->ptr.hp->ptr.atom;
   else
     CopyGList(&h->ptr.hp,L->ptr.hp->ptr.hp);
   return h;
 }
GList GetTail(GList L)
 { /* 初始条件: 广义表L存在。操作结果: 取广义表L的尾 */
   GList T;
   if(!L)
   {
     printf("\n空表无表尾!");
     exit(0);
   }
   T=(GList)malloc(sizeof(GLNode));
   if(!T)
     exit(OVERFLOW);
   T->tag=LIST;
   T->tp=NULL;
   CopyGList(&T->ptr.hp,L->ptr.hp->tp);
   return T;
 }

Status CopyGList(GList *T,GList L)
 { /* 初始条件: 广义表L存在。操作结果: 由广义表L复制得到广义表T */
   if(!L) /* L空 */
   {
     *T=NULL;
     return OK;
   }
   *T=(GList)malloc(sizeof(GLNode));
   if(!*T)
     exit(OVERFLOW);
   (*T)->tag=L->tag; /* 复制枚举变量 */
   if(L->tag==ATOM) /* 复制共用体部分 */
     (*T)->ptr.atom=L->ptr.atom; /* 复制单原子 */
   else
     CopyGList(&(*T)->ptr.hp,L->ptr.hp); /* 复制子表 */
   if(L->tp==NULL) /* 到表尾 */
     (*T)->tp=L->tp;
   else
     CopyGList(&(*T)->tp,L->tp); /* 复制子表 */
   return OK;
 }