数据结构实战

一、广义表的表示

        广义表可以看成是属性表的一种扩充。在线性表中，每一个节点都是一个数据节点，而广义表中每一个节点可以是数据节点，也可以是另一张广义表。我们通常把用于存放数据的节点称作原子节点，而把用于存放另一张广义表的节点称作子表。可见广义表的定义是递归的。下面来看一下广义表的数据结构：

//数据节点，原子节点
typedef struct s_node
{
	//用于存放数据的通用指针
	void *data;
} s_node;

//广义表
typedef struct s_list
{
	/*
	 * 标志用于区分当前节点是原子节点还是子表
	 * 0原子节点，1子表
	 */
	int tag;
	//共用体用于存放原子数据或子表地址
	union
	{
		//原子节点
		struct s_node* data;
		//子表节点
		struct s_list* child;
	};
} s_list;

        广义表的数据结构相对简单，但对其的相关操作却比较复杂。下面我们就来编写一个广义表的应用例子。

二、M元多项式

        现有一个M元多项式：

        我们知道任何一个M元多项式都可以转化成一元系数形式：

        于是我们就可以认为多项式中每一个变元的一项就是一个子表，每一个子表都是另一个变元的子表。我们来看一下M元多项式的数据结构：

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_destory(s_list *list)
{
	if (list == null)
	{
		return;
	}

	//如果下一节点不为空
	if (list->next != null)
	{
		//递归销毁下一节点
		list_destory(list->next);
	}

	//如果当前节点是子表
	if (list->tag)
	{
		//递归销毁子表
		list_destory(list->child);
	}

	free(list);
}

//追加节点
bool list_append(s_list *list, s_list* nlist)
{
	if (list == null)
	{
		return false;
	}
	if (nlist == null)
	{
		return false;
	}

	while (list->next != null)
	{
		list = list->next;
	}
	list->next = nlist;

	return true;
}

//初始化表节点
bool list_init(s_list *list)
{
	list->tag = 0;
	list->coe = 0;
	list->child = null;
	list->next = null;

	return true;
}

//插入原子节点或子表
bool list_insert_value(s_list *list, int tag, int exp, int val)
{
	if (list == null)
	{
		return false;
	}

	list->tag = tag;
	list->exp = exp;
	list->coe = val;

	return true;
}

//显示多项式
void list_display(s_list *list, char ch)
{
	if (list == null)
	{
		return;
	}

	//如果当前节点是子表
	if (list->tag)
	{
		printf("(");
		//递归显示子表
		list_display(list->child, ch - 1);
		printf(")%c^%d", ch, list->exp);
	}
	//如果当前节点是原子节点
	else
	{
		//显示原子内容
		printf("%+d%c^%d", list->coe, ch, list->exp);
	}

	//如果下一节点不为空
	if (list->next != null)
	{
		printf("+");
		//递归显示下一节点
		list_display(list->next, ch);
	}
}

        其中需要注意的是void list_display(s_list *list, char ch)函数，它是一个递归函数，用于显示广义表中所有节点的数据内容。如果当前节点是一个子表则递归调用显示子表；如果当前结节是一个原子结节则显示原子内容数据；最后判断下一节点是不是也是一个广义表节点，如果是则递归调用显示其内容。

        最后来写一个冗长的main函数构建上述的M元多项式：

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

int main(int argc, char **args)
{
	//list1 x^10
	s_list *list1 = (s_list *) malloc(sizeof(s_list));
	list_init(list1);
	list_insert_value(list1, 0, 10, 1);

	//list2 2x^6
	s_list *list2 = (s_list *) malloc(sizeof(s_list));
	list_init(list2);
	list_insert_value(list2, 0, 6, 2);

	//list1 (x^10 + 2x^6)
	list_append(list1, list2);

	//list3 (x^10 + 2x^6)y^3
	s_list *list3 = (s_list *) malloc(sizeof(s_list));
	list_init(list3);
	list_insert_value(list3, 1, 3, (int) list1);

	//list4 3x^5
	s_list *list4 = (s_list *) malloc(sizeof(s_list));
	list_init(list4);
	list_insert_value(list4, 0, 5, 3);

	//list5 (3x^5)y^2
	s_list *list5 = (s_list *) malloc(sizeof(s_list));
	list_init(list5);
	list_insert_value(list5, 1, 2, (int) list4);

	//list3 ((x^10 + 2x^6)y^3 + (3x^5)y^2)
	list_append(list3, list5);

	//list6 ((x^10 + 2x^6)y^3 + (3x^5)y^2)z^2
	s_list *list6 = (s_list *) malloc(sizeof(s_list));
	list_init(list6);
	list_insert_value(list6, 1, 2, (int) list3);

	//list7 x^4
	s_list *list7 = (s_list *) malloc(sizeof(s_list));
	list_init(list7);
	list_insert_value(list7, 0, 4, 1);

	//list8 6x^3
	s_list *list8 = (s_list *) malloc(sizeof(s_list));
	list_init(list8);
	list_insert_value(list8, 0, 3, 6);

	//list8 (x^4 + 6x^3)
	list_append(list7, list8);

	//list9 (x^4 + 6x^3)y^4
	s_list *list9 = (s_list *) malloc(sizeof(s_list));
	list_init(list9);
	list_insert_value(list9, 1, 4, (int) list7);

	//list10 2y
	s_list *list10 = (s_list *) malloc(sizeof(s_list));
	list_init(list10);
	list_insert_value(list10, 0, 1, 2);

	//list9 ((x^4 + 6x^3)y^4 + 2y)
	list_append(list9, list10);

	//list11 ((x^4 + 6x^3)y^4 + 2y)z
	s_list *list11 = (s_list *) malloc(sizeof(s_list));
	list_init(list11);
	list_insert_value(list11, 1, 1, (int) list9);

	//list6 ((x^10 + 2x^6)y^3 + (3x^5)y^2)z^2 + ((x^4 + 6x^3)y^4 + 2y)z
	list_append(list6, list11);

	//list12 15
	s_list *list12 = (s_list *) malloc(sizeof(s_list));
	list_init(list12);
	list_insert_value(list12, 0, 0, 15);

	//list6 ((x^10 + 2x^6)y^3 + (3x^5)y^2)z^2 + ((x^4 + 6x^3)y^4 + 2y)z + 15
	list_append(list6, list12);

	list_display(list6, 'z');

    //销毁广义表，释放内存
	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

        显示内容格式上不是很友好，但结果是正确的。也说明这个数据结构可以表示任意多元的多项式。

        本例代码：

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

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