数据结构--广义表_广义表取出原子的操作

一场游戏一场空，最终 最初都由我掌控，好像一身从容，不曾有狼狈伤痛，可深夜一个人该如何相拥？

广义表的节点类型：

typedef struct lnode
{  int tag;				//结点类型标识
   union 
   {	ElemType data;			//存放原子值
	struct lnode *sublist;	//指向子表的指针
   } val;
   struct lnode *link;		//指向下一个元素
} GLNode;

广义表算法设计方法：

（1）算法一

void fun1(GLNode *g)			//g为广义表头结点指针
{  GLNode *g1=g->val.sublist;		//g1指向第一个元素
   while (g1!=NULL)			//元素未处理完循环
   {  if (g1->tag==1)			//为子表时
 	  fun1(g1);			//递归处理子表
      else				//为原子时
	  原子处理语句;			//实现原子操作
      gl=g1->link;			//处理兄弟
   }
}

（2）算法二

void fun2(GLNode *g)			//g为广义表结点指针
{  if (g!=NULL)
   {	if (g->tag==1)			//为子表时
           fun2(g->val.sublist);	//递归处理其元素
	else				//为原子时 
	    原子处理语句;		//实现原子操作
 	fun2(g->link);			//递归处理其兄弟
   }
}

广义表的基本算法设计：

（1）求广义表的长度

 在广义表中，同一层次的每个结点是通过link域链接起来的，所以可把它看做是由link域链接起来的单链表。这样,求广义表的长度就是求单链表的长度。

int GLLength(GLNode *g)	//求广义表g的长度
{  int n=0;			//累计元素个数，初始值为0
   GLNode *g1;
   g1=g->val.sublist;		//g1指向广义表的第一个元素
   while (g1!=NULL)		//扫描所有元素结点
   {	n++;			//元素个数增1
	g1=g1->link;
   }
   return n;			//返回元素个数
}

（2）求广义表的深度

    对于带头结点的广义表g，广义表深度的递归定义是它等于所有子表中表的最大深度加1。若g为原子，其深度为0。

    求广义表深度的递归模型f()如下：

int GLDepth(GLNode *g)		//求广义表g的深度
{  GLNode *g1;  int maxd=0，dep;
   if (g->tag==0) return 0;		//为原子时返回0
   g1=g->val.sublist;			//g1指向第一个元素
   if (g1==NULL)  return 1;		//为空表时返回1
   while (g1!=NULL)			//遍历表中的每一个元素
   {  if (g1->tag==1)			//元素为子表的情况
      {  dep=GLDepth(g1);		//递归调用求出子表的深度
	  if (dep>maxd)		//maxd为同层子表深度的最大值
	     maxd=dep;
      }
      g1=g1->link;			//使g1指向下一个元素
   }
   return(maxd+1);			//返回表的深度
}