廣義表的創建與打印

廣義表的創建與打印

廣義表的創建與打印

本文取自《數據結構與算法》(C語言版)(第三版)，出版社是清華大學出版社。

在VS2010中新建C++Win32 控制台應用程序項目，創建結果截圖：

1.廣義表的創建：
廣義表可以通過下面的遞歸方式進行定義。
基本項：(1)廣義表為空表，當s為空時；(2)廣義表為原子結點，當s為單字符串時。
歸納項：假設Subs為S去掉最外層括號對的串，記作“S1，S2，...，Sn”，其中Si(i=1,...,n)為非空字符串。對每個Si建立表結點，並令其hp域的指針為由Si建立的子表的頭指針，除最後建立的表結點的尾指針為NULL外，其余表結點的尾指針均指向在它之後建立的表結點。也就是說，因為Si是一個字符串，首先要為這個字符串建立一個表結點，表結點的指針域指向Si中的元素，它的tp域指向下一次建立的Si+1，而Sn的tp域為空。
因為在廣義表的定義中要用到subs串，因此需要一個函數來求這個串。這裡采用函數Getsubs(str,hstr)來實現。其中，hstr存放的是str中第1個","之前的子串，並且函數將str修改為刪除子串hstr和","之後的剩余串。若串str中沒有","，則hstr即為str，而str修改為空串NULL。

2.廣義表的打印：
打印廣義表的算法思想是：先打印一個左括號"("，若遇到tag=ATOM，則打印該結點的值，如果此結點後面有後繼結點，則再打印一個","；如果tag=LIST，說明是一個子表，則遞歸調用函數，打印這個子表；打印完所有結點以後，最後打印一個“)”。

源程序如下：GeneralList.cpp

// GeneralList.cpp : 定義控制台應用程序的入口點。

#include "stdafx.h"
#include 
#include 
#include 

typedef enum {ATOM, LIST}ElemTag;    //ATOM==0 原子, LIST==1 子表

struct GLNode
{
	ElemTag tag;        //標識域
	union
	{
		char atom;
		struct GLNode *hp;
	};
	struct GLNode *tp;
};

typedef struct GLNode GList;

//求取廣義表的子串Subs
void Getsubs(char str[], char hstr[])
{
	int i=0;
	int j=0;
	int k=0;     //用來記錄沒有匹配的左括號數
	int r=0; 
	char s[100];
	while(str[i]&&(str[i]!=','||k))
	{
		if(str[i]=='(')
			k++;
		else if(str[i]==')')
			k--;

		if(str[i]!=','||str[i]==','&&k)
		{
			hstr[j]=str[i];
			i++;
			j++;
		}
	}
	hstr[j]='\0';
	if(str[i]==',')
		i++;
	while(str[i])
	{
		s[r]=str[i];
		r++;
		i++;
	}
	s[r]='\0';
	strcpy(str,s);

}

//創建廣義表
GList *GListCreate(char str[])
{
  GList *G;
  char subs[100];
  char hstr[100];
  GList *q;
  int len=strlen(str);
  if(len==0||!strcmp(str,"()"))
	  G=NULL;
  else if(len==1)  //原子結點的情況
  {
		  G=(GList *)malloc(sizeof(GList));
		  if(!G)
		  {
			  printf("申請空間失敗！");
			  exit(0);
		  }
		  G->tag = ATOM;
		  G->atom = *str;
		  G->tp = NULL;
  }
  else
  {
	 GList *p;
     G=(GList *)malloc(sizeof(GList));
	 if(!G)
	 {
		printf("申請空間失敗！");
		exit(0);
	  }
	  G->tag = LIST;
	  p=G;
	  str++;
	  strncpy(subs,str,len-2);       //去掉最外面的()
	  subs[len-2]='\0';
	  while(len>0)
	 {
		GList *r;
		Getsubs(subs,hstr);         //將subs分開為表頭hstr和表尾subs
		r=GListCreate(hstr);        //生成表頭的廣義表
		p->hp=r;
		q=p;
		len=strlen(subs);
		if(len>0)
		{
           p=(GList *)malloc(sizeof(GList));
		   if(!G)
		   {
			  printf("申請空間失敗！");
			  exit(0);
		    }
		    p->tag = LIST;
			q->tp=p;
		 }
	}
	q->tp=NULL;
  }
  return G;
}

//打印廣義表
void GListPrint(GList *G)
{
   GList *q,*p;
   printf("(");
   while(G)
   {
	   p=G->hp;
	   q=G->tp;
	   if(p&&q&&!p->tag)       //p為原子結點，並且有後續結點
	   {
         printf("%c,",p->atom);
		 p=q->hp;
	     q=q->tp;
	   }
	   if(p&&!p->tag)           //p為原子結點，並且沒有後續結點
	   {
         printf("%c",p->atom);
		 break;
	   }
	   else
	   {
		   if(!p)
              printf("()");          //p為空表
		   else
			  GListPrint(p);
		   if(q)
              printf(",");          //還存在著後續的結點
		   G=q;
	   }
   }
   printf(")"); 
}

int main()
{
	int n;
	char *s;
	GList *G;
	printf("請輸入廣義表的字符數：\n");
	scanf("%d",&n);
    printf("請輸入廣義表：\n");
	s=(char *)malloc(n*sizeof(char));
	scanf("%s",s);
	G=GListCreate(s);
    printf("所輸入的廣義表為：\n");
	GListPrint(G);
	printf("\n");
	return 0;
}