kk.cpp

主要是实现广义表相关操作的算法

#include "stdafx.h"
#include "stdio.h"
#include "malloc.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指针批指向P，*(*S)即*P指向数组的首地址。如(A,B)见则指向“(”
  (*s)++;//p 指针移动，直接指向数据则指向A
   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;//前部分例如(A
ch=*(*s);//后面部分的实现接上,B)，ch这时指向“，”
(*s)++;//B
 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)//如果标志变量为1则表明有子表则会递归调用否则即为0的话只用把其当前原子结点复制过去
     q->dd.sublist =copy_GL(p->dd.sublist );
  else
     q->dd.data =p->dd.data;
 q->link=copy_GL(p->link);//递归调用下一个结点指针
 return(q);
}
NODE *tail(NODE *p) /*求表尾函数 */
{   
 NODE *GL;
	if(p!=NULL && p->tag!=0)
	{//表不为空表并且有表尾
		GL=p->dd.sublist;
		GL=GL->link;//GL指向第二个元素
		p->dd.sublist=GL;//删除广义表第一个元素
	 
	}
	
    return(p->dd.sublist);
} 
NODE *head(NODE *p) /*求表头函数 */
{  NODE *GL;
  	if (!p) //当P为NULL
		return(NULL);// 空表无表头* ／
    else if(!p->tag)
	   return(NULL);// 原子无表头* ／
    else 
	{GL=p->dd.sublist;
	    GL->link=NULL;
		return(GL); 
	}
   
 }

int sum(NODE *p) //求原子结点的数据域之和函数 a为49其后面的字母以此类推，A为17其后面的字母以此类推；
{
  int m,n;//m存储下一个结点的数据域，n存储子表的数据域
  if(p==NULL) //当P为NULL
	  return(0);
  else
 {
  if(p->tag==0)
	 n=p->dd.data-'0';//求当前原子的数据域
  else 
    n=sum(p->dd.sublist);//子表的递归调用
    if(p->link!=NULL)
     m=sum(p->link);//下一个结点的递归调用

   else m=0;//没有下一个结点

    return(n+m);
 }
}
int count(NODE *p)   /*求原子结点的个数函数   */
{
	int m,n;//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);
	}
}

int depth(NODE *p) /*求表的深度函数 */
{
 int h,maxdh;//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

	    	h=0;
        else//否则递归调用然后把值给h
		{
	    q=p->dd.sublist;
        h=depth(q);
		}
       if(h>maxdh)
		   maxdh=h;//求出最后的深度
       p=p->link;
	}
   return(maxdh+1);//因为最少的深度也会有1，maxdh的初值为0；
   }
	
}
void  main()
{
  NODE *hd,*hc,*h,*t,*gllst;
  char s[100],*p;
  printf("请输入广义表\n");
  p=gets(s);
  hd=creat_GL(&p);
  printf("\n广义表:");
  prn_GL(hd);
  printf("\ncount:%d",count(hd));
  printf("\nsum:%d\n",sum(hd));
  printf("depth:%d",depth(hd));
  hc=copy_GL(hd);
  printf("\ncopy after:  ");
  prn_GL(hc);
  int xz;
	do
	{   printf("\n请选择\n1：输出表头\n2：输出表尾\n");
		scanf("%d",&xz);
		switch(xz)
		{
		case 1 :h=head(hd);
         printf("\nhead:");//／* 为原子的情况，要进行特殊处理* ／
       if(h->tag==0) 
	   printf("%c",h->dd.data);
      else 
	  prn_GL(h);
	  break;
		case 2 :t=tail(hd);
         printf("\ntail：");
         prn_GL(hd);
			break;
		}

	}while(0);
  
  
  
}