数据结构实战

        首先来描述一下我们要解决的问题：现有两个一元多项式A和B，计算A+B的结果。例如：

        这两个多项式用链表的表示如下：

        链表中，用两个变量分别来存放x的指数和系数，下面来看一下这个链表的数据结构：

//多项式每一项节点
typedef struct s_node
{
	//指数
	int exp;
	//系数
	int coe;
	//下一节点指针
	struct s_node *next;
} s_node;

//表数据结构
typedef struct
{
	//头节点
	s_node *header;
} s_list;

        下面来实现多项式链表的功能函数：

//构建一个顺序线性表
bool init_list(s_list *list)
{
	if (list == null)
	{
		return false;
	}
	list->header = null;
	return true;
}

//销毁表
bool destroy_list(s_list *list)
{
	if (list == null)
	{
		return false;
	}

	if (list->header == null)
	{
		return true;
	}

	//从头节点开始释放
	s_node *p = list->header;
	while (p != null)
	{
		s_node *t = p;
		p = p->next;
		free(t);
	}
	list->header = null;

	return true;
}

//插入一个新元素
bool list_insert(s_list *list, int e, int c)
{
	if (list == null)
	{
		return false;
	}

	//申请新节点内存
	s_node *p_new = (s_node *) malloc(sizeof(s_node));
	p_new->exp = e;
	p_new->coe = c;
	p_new->next = null;

	//如果头节点为空
	if (list->header == null)
	{
		//设置头节点为插入元素
		list->header = p_new;
		return true;
	}
	else
	{
		s_node *p = list->header;
		while (p->next != null)
		{
			p = p->next;
		}
		p->next = p_new;
	}

	return false;
}

//多项式相加
bool list_add(s_list *list_one, s_list *list_two, s_list *list_out)
{
	if (list_one == null || list_two == null || list_out == null)
	{
		return false;
	}

	//取得等等相加的多项式头节点
	s_node *p1 = list_one->header;
	s_node *p2 = list_two->header;

	//循环相加
	while (!(p1 == null && p2 == null))
	{
		//如果p1为空，则处理剩余的p2项
		if (p1 == null && p2 != null)
		{
			list_insert(list_out, p2->exp, p2->coe);
			p2 = p2->next;
		}
		//如果p2为空，则处理剩余的p1项
		else if (p1 != null && p2 == null)
		{
			list_insert(list_out, p1->exp, p1->coe);
			p1 = p1->next;
		}
		//如果p1的指数小，则处理p1
		else if (p1->exp < p2->exp)
		{
			list_insert(list_out, p1->exp, p1->coe);
			p1 = p1->next;
		}
		//如果p2的指数小，则处理p2
		else if (p1->exp > p2->exp)
		{
			list_insert(list_out, p2->exp, p2->coe);
			p2 = p2->next;
		}
		//如果指数相同
		else if (p1->exp == p2->exp)
		{
			//如果计算系数结果不为0，则处理
			if (p1->coe + p2->coe != 0)
			{
				list_insert(list_out, p1->exp, p1->coe + p2->coe);
			}
			p1 = p1->next;
			p2 = p2->next;
		}
	}

	return true;
}

//显示多项式
bool list_display(s_list *list)
{
	if (list == null || list->header == null)
	{
		return false;
	}

	//顺序访问每一个元素
	s_node *p = list->header;
	while (p != null)
	{
		if (p == list->header)
		{
			printf("%d", p->coe);
		}
		else
		{
			printf("%+d", p->coe);
		}
		if (p->exp != 0)
		{
			if (p->exp == 1)
			{
				printf("x", p->exp);
			}
			else
			{
				printf("x^%d", p->exp);
			}
		}
		p = p->next;
	}
	return true;
}

        最后写一个main函数来测试，多项式的项按指数升序（由低到高）的顺序插入链表，这里不考虑链表排序的问题：

int main(int argc, char **args)
{
	//构建多项式A
	s_list listA;
	init_list(&listA);
	list_insert(&listA, 0, 4);
	list_insert(&listA, 1, 5);
	list_insert(&listA, 2, 6);
	list_insert(&listA, 4, -8);
	list_insert(&listA, 5, 3);
	list_insert(&listA, 7, -7);
	list_display(&listA);

	printf("\n");

	//构建多项式B
	s_list listB;
	init_list(&listB);
	list_insert(&listB, 0, 9);
	list_insert(&listB, 1, -3);
	list_insert(&listB, 2, -1);
	list_insert(&listB, 3, 3);
	list_insert(&listB, 5, -7);
	list_insert(&listB, 8, 3);
	list_display(&listB);

	printf("\n");

	s_list listC;
	init_list(&listC);
	list_add(&listA, &listB, &listC);
	list_display(&listC);

	//销毁list
	destroy_list(&listA);
	destroy_list(&listB);
	destroy_list(&listC);

	return 0;
}

        运行结果：

4+5x+6x^2-8x^4+3x^5-7x^7
9-3x-1x^2+3x^3-7x^5+3x^8
13+2x+5x^2+3x^3-8x^4-4x^5-7x^7+3x^8

        本例代码：

code path   chapter.01/e.g.1.5/

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