ch5_glist.c

本人讲授数据结构课程时的所写的示例程序

/*
广义表的实现
author: kk.h
date: 2006.10
http://www.cocoon.org.cn
*/

#include "stdio.h"
typedef struct node
{
  int tag;
  union{struct node *sublist;
             char data;
            }dd;
  struct node *link;
}NODE;

/* 递归创建广义表，注意参数比较复杂，指针的指针 */
NODE *creat_GL(char **s)
{
  NODE *h;
  char ch;
  ch=*(*s);
  (*s)++;
  if(ch!='\0')
  {
    h=(NODE*)malloc(sizeof(NODE));
    if(ch=='(')
    {
      h->tag=1;
      h->dd.sublist=creat_GL(s);
    }
    else
    {
      h->tag=0;
      h->dd.data=ch;
    }
  }
  else
    h=NULL;

  ch=*(*s);
  (*s)++;
  if(h!=NULL)
    if(ch==',')
      h->link =creat_GL(s);
    else
      h->link=NULL;
  return(h);
}


/* 递归打印广义表 */
void prn_GL(NODE *p)
{
  if(p!=NULL)
  {
    if(p->tag==1)
    {
      printf("(");
      if(p->dd.sublist ==NULL)
        printf(" ");
      else
        prn_GL(p->dd.sublist );
    }
    else
      printf("%c",p->dd.data);

    if(p->tag==1)
      printf(")");
    if(p->link!=NULL)
    {
      printf(",");
      prn_GL(p->link);
    }
  }
}

/* 递归复制广义表 */
NODE *copy_GL(NODE *p)
{
  NODE *q;
  if(p==NULL) return(NULL);

  q=(NODE *)malloc(sizeof(NODE));
  q->tag=p->tag;
  if(p->tag)
    q->dd.sublist =copy_GL(p->dd.sublist );
  else
    q->dd.data =p->dd.data;

  q->link=copy_GL(p->link);
  return(q);
}

/* 求表的深度函数（有错误？） */
int depth(NODE *p)
{
  int h,maxdh;
  NODE *q;
  if(p->tag==0) return(0);
  else 
    if(p->tag==1&&p->dd.sublist==NULL) return 1;
    else
    {
      maxdh=0;
      while(p!=NULL)
      {  
        if(p->tag==0) h=0;
        else
        {q=p->dd.sublist;
         h=depth(q);
        }

        if(h>maxdh)
           maxdh=h;

        p=p->link;
      }
      return(maxdh+1);
    }
}

 /* 求原子结点的个数函数 */
int count(NODE *p)
{
  int m,n;
  if(p==NULL) return(0);
  else
  {
    if(p->tag==0) n=1;
    else 
      n=count(p->dd.sublist);
    if(p->link!=NULL)
      m=count(p->link);
    else m=0;
    return(n+m);
  }
}

main()
{
  NODE *hd,*hc;
  char s[100]="(a,(b,(c,d)))",*p;

  /*p=gets(s);*/

  p=s;

  hd=creat_GL(&p);
  hc=copy_GL(hd);
  printf("\ncopy after:");
  prn_GL(hc);

  printf("\ndepth=%d  (wrong?)",depth(hc));
  printf("\ncount=%d",count(hc));

  getch();
}