广义表的创建与打印

水深无声 2022-08-21 04:59 130阅读 0赞

**广义表的创建与打印**

本文取自《数据结构与算法》(C语言版)(第三版)，出版社是清华大学出版社。

本博文作为学习资料整理。源代码是VC++ 6.0上可执行程序，我挪到了VS2010中执行。

在VS2010中新建C++ Win32 控制台应用程序项目，创建结果截图：

![Center][]

**1.广义表的创建：**

广义表的存储结构示意图：示例：C(x, y, (a, b))

![SouthEast][]

广义表可以通过下面的递归方式进行定义。  
基本项：(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 <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    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;
    }

Ctrl+F5执行GeneralList.cpp的运行结果：如下截图：

![Center 1][]

[Center]: /images/20220731/97227d345a75467eb616f336d5a21b70.png
[SouthEast]: /images/20220731/02500b3229294c68a171c6c5ccad71bd.png
[Center 1]: /images/20220731/929b312a006b42218d4c7d89b69c106a.png