数据结构实战

一、广义表深度计算

        广义表的深度计算可以按递归定义：如果当前节点是一个原子节点，则当前节点的深度为0；如果当前节点是一个子表，则当前节点的深度为1；同级多表中找出最大深度则为广义表深度。下面我们在上一节例子的基础上来实现这个递归算法：

typedef struct s_list
{
	//0表示原子，1表示子表
	int tag;
	//指数
	int exp;
	//共用体
	union
	{
		//系数
		int coe;
		//子表
		struct s_list* child;
	};

	//下一个结点
	struct s_list* next;

} s_list;

//求广义表深度
void list_depth(s_list *list, int *depth)
{
	if (list == null)
	{
		return;
	}

	if (depth == null)
	{
		return;
	}

	//如果当前节点是子表
	if (list->tag)
	{
		*depth += 1;
		//递归求子表深度
		list_depth(list->child, depth);
	}

	//如果下一节点不为空
	if (list->next != null)
	{
		//求同级子表最大深度
		int m = 0;
		list_depth(list->next, &m);
		if (*depth < m)
		{
			*depth = m;
		}
	}
}

        写一个main函数来计算广义表深度：

#include <stdlib.h>
#include <stdio.h>
#include "list.h"

int main(int argc, char **args)
{
    //创建广义表部分与上一节相同，代码略

	//显示多项式
	list_display(list6, 'z');
	printf("\n");

	//求广义表list6深度
	int depth = 0;
	list_depth(list6, &depth);
	printf("depth = %d \n", depth);

    //销毁广义表，释放内存
	list_destory(list6);
    
    return 0;
}

        运行结果：

((+1x^10++2x^6)y^3+(+3x^5)y^2)z^2+((+1x^4++6x^3)y^4++2y^1)z^1++15z^0
depth = 2 

        注意深度从0开始，深度为2表示此广义表有3层。

二、复制广义表

        复制广义表与深度计算的原理一致，都是使用递归算法对广义表的每一个节点进制复制操作，如果当前节点是一个原子节点，则复制完成，如果当前节点是一个子表，则对此子表继续复制。

//复制广义表
void list_copy(s_list *target, s_list *source)
{
	if (source == null)
	{
		return;
	}

	memcpy(target, source, sizeof(s_list));

	//如果当前节点是子表
	if (source->tag)
	{
		//递归复制子表
		s_list *clist = (s_list *) malloc(sizeof(s_list));
		list_copy(clist, source->child);
		target->child = clist;
	}

	//如果下一节点不为空
	if (source->next != null)
	{
		//递归复制同级广义表
		s_list *nlist = (s_list *) malloc(sizeof(s_list));
		list_copy(nlist, source->next);
		target->next = nlist;
	}
}

        再来看一下main函数：

#include <stdlib.h>
#include <stdio.h>
#include "list.h"

int main(int argc, char **args)
{
	//创建广义表部分与上一节相同，代码略

	//显示多项式
	list_display(list6, 'z');
	printf("\n");

	//求广义表list6深度
	int depth = 0;
	list_depth(list6, &depth);
	printf("depth = %d \n", depth);

	s_list *list13 = (s_list *) malloc(sizeof(s_list));
	list_copy(list13, list6);
	//显示多项式
	list_display(list13, 'z');
	printf("\n");

	//求广义表list13深度
	depth = 0;
	list_depth(list13, &depth);
	printf("depth = %d \n", depth);

    //销毁广义表，释放内存
	list_destory(list6);
	list_destory(list13);

	return 0;
}

        运行结果：

((+1x^10++2x^6)y^3+(+3x^5)y^2)z^2+((+1x^4++6x^3)y^4++2y^1)z^1++15z^0
depth = 2 
((+1x^10++2x^6)y^3+(+3x^5)y^2)z^2+((+1x^4++6x^3)y^4++2y^1)z^1++15z^0
depth = 2 

        可见，复制后的广义表完全相同。

        本例代码：

code path   chapter.04/e.g.4.4/

https       https://github.com/magicworldos/datastructure.git
git         git@github.com:magicworldos/datastructure.git
subverion   https://github.com/magicworldos/datastructure