线性表应用：多项式的加法，乘法，微分运算（1）

利用链表存储多项式

例如：多项式
A(x) =x + 2x³

链表中的数据域有两个成员：coef 存放多项式的系数；exp 存放指数

• 多项式的数据结构

typedef struct PolyNode
{
	int coef;	//系数
	int exp;	//指数
	struct PolyNode * next;
}PolyNode,* PolyList;

• 多项式加法实现：Add(PolyList l_a, PolyList l_b)
  例如：两个多项式
  a(x)=x² + 2x³ 和 b(x)=x
  算法思想： a和b的单项式指数作比较；a的指数>b的指数，a加入到和多项式，反之，将b加入和多项式；a的指数=b的指数，如果a和b的系数和为零，跳过此项，反之，将a和b单项式相加加入到和多项式。

• 多项式乘法实现：Mcl(PolyList l_a, PolyList l_b)
  算法思想： 1. a的单项式乘b的每一项 2. 对获得的乘积多项式求和

• 多项式微分实现：DCPolyList(PolyList L)
  算法思想： 1. 跳过多项式中的常数项 2. 每一项的系数乘于指数，同时指数减一

遇到问题

对多项式a和b的和进行微分操作，会改变多项式a的链表中的成员值（具体表现为多项式a的系数和指数发生改变）
将微分操作放在多项式乘积操作前，会导致多项式乘积出错，或者程序意外终止。

解决过程

首先我想过是不是指针传递问题，导致多项式a的链表指针list_a被误传递给了微分方法，导致链表list_a的成员被修改。然而我仔细找了一遍任然没有发现直接对链表list_a进行更改的证据。
由于我不会使用VC++6.0进行调试，于是我就疯狂的在整个程序执行过程中涉及到list_a和其他链表指针的地方输出它们的地址（printf("%x",指针)），将所有的指针梳理了一遍。


在微分函数运行的过程中，我发现了其中的两个指针指向的地址竟然就是list_a中的地址，那就说明是后来的指向修改了表list_a。

解决问题

查看了一下我的微分函数，修改之前，我直接对指针L的链表进行操作（包括删除），然后我发现在地址中指向了list_a的结点；修改之后，我重新建立一个链表来存储微分结果，对L只执行遍历操作，问题得到了解决。（至于为什么L会指向链表list_a中的结点，我也不太清楚，可以帮忙指出一下，这个问题可是卡了我好几天）

正确的截图

全部代码

#include<stdio.h>
#include<stdlib.h>
typedef struct PolyNode
{
	int coef;	//系数
	int exp;	//指数
	struct PolyNode * next;
}PolyNode,* PolyList;

PolyList InitPolyList(PolyList L)
{
	///初始化链表
	L = (PolyList)malloc(sizeof(PolyNode));
	L->next = NULL;
	return L;
}

void CreatePolyList(PolyList L)
{
	///建立多项式
	PolyNode * node;
	int lceof, lexp;
	printf("请输入多项式的系数和指数（指数从小到大依次输入）\n");
	while(true)
	{
		scanf("%d%d",&lceof,&lexp);
		if(lceof == 0)		break;
		node = (PolyNode *)malloc(sizeof(PolyNode));
		node->next = NULL;
		node->coef = lceof;
		node->exp = lexp;
		L->next = node;
		L = L->next;
	}
	printf("创建成功！！\n\n");
}

void PrintPolyList(PolyList L)
{
	///打印多项式
	printf("====打印结果====\nA(x)=");
	while(L->next != NULL)
	{
		L = L->next;
		printf("%d",L->coef);
		if(L->exp != 0)		printf("x^%d",L->exp);
		if(L->next == NULL)		printf(";\n\n");
		else	printf("+");
	}
}

PolyList Add(PolyList l_a, PolyList l_b)
{
	///多项式相加
	PolyList L;
	L = InitPolyList(L);
	PolyList head = L;
	PolyNode *node;
	PolyList a, b;
	a = l_a->next;
	b = l_b->next;
	
	printf("执行多项式加法操作\n");
	while(a != NULL && b != NULL)
	{
		if(a->exp < b->exp)
		{
			//若多项式a的第一项指数小于多项式b第一项的指数,将第一项加入到和多项式
			node = (PolyNode*)malloc(sizeof(PolyNode));
			node->next = NULL;
			node->exp = a->exp;
			node->coef = a->coef;
			L->next = node;
			L = L->next;
			a = a->next;
		}
		else if(a->exp == b->exp)
		{
			if(a->coef + b->coef != 0)
			{
				//两个系数相加不为零才有意义
				node = (PolyNode*)malloc(sizeof(PolyNode));
				node->next = NULL;
				node->exp = a->exp;
				node->coef = a->coef + b->coef;
				L->next = node;
				L = L->next;
				a = a->next;
				b = b->next;
			}
		}
		else
		{
			node = (PolyNode*)malloc(sizeof(PolyNode));
			node->next = NULL;
			node->exp = b->exp;
			node->coef = b->coef;
			L->next = node;
			L = L->next;
			b = b->next;
		}
	}
	if(a == NULL || b == NULL)
	{
		while(b != NULL)
		{
			L->next = b;
			L = L->next;
			b = b->next;
		}
		while(a != NULL)
			{
			L->next = a;
			L = L->next;
			a = a->next;
		}
	}
	printf("多项式求和操作成功！！\n");
	return head;
}

PolyList Mcl(PolyList l_a, PolyList l_b)
{
	///多项式乘法
	PolyList mult;
	mult = InitPolyList(mult);
	PolyNode *node;
	PolyList ax[100];
	int i = 0;

	PolyList a, b;
	a = l_a->next;

	printf("执行多项式乘法操作\n");
	while(a != NULL)
	{
		b = l_b->next;
		PolyList L = (PolyList)malloc(sizeof(PolyNode));
		ax[i] = L;
		while(b != NULL)
		{
			//结点插入失败
			node = (PolyNode *)malloc(sizeof(PolyNode));
			node->next = NULL;
			node->coef = a->coef * b->coef;
			node->exp = a->exp + b->exp;
			L->next = node;
			L = L->next;
			b = b->next;
		}
		i++;
		a = a->next;
	}
	i--;
	PolyList m = ax[0];
	mult = ax[0];
	while(i > 0)
	{
		mult = Add(m, ax[i]);
		m = mult;
		i--;
	}
	return mult;
}

PolyList DCPolyList(PolyList L)
{
	///多项式微分运算
	PolyList head;
	head = (PolyList)malloc(sizeof(PolyNode));
	PolyList list = head;
	printf("多项式微分操作\n");
	while(L->next != NULL)
	{
		L = L->next;
		PolyNode * node;
		node = (PolyNode *)malloc(sizeof(PolyNode));
		node->next = NULL;
		if(L->exp == 0)
			continue;
		node->coef = L->coef * L->exp;
		node->exp = L->exp - 1;
		head->next = node;
		head = head->next;
		/*if(L->next->exp == 0)
		{
			//如果多项式的指数为零，则删除这一项
			PolyNode * node = L->next;
			L->next = L->next->next;
			free(node);
			node = NULL;
			continue;
		}
		else
		{
			L->next->coef = L->next->coef * L->next->exp;
			L->next->exp -= 1;
			L = L->next;
		}*/
	}
	printf("微分操作执行成功！！\n");
	return list;
}
int main()
{
	PolyList list_a, list_b;
	list_a = InitPolyList(list_a);
	list_b = InitPolyList(list_b);
	
	CreatePolyList(list_a);
	PrintPolyList(list_a);

	CreatePolyList(list_b);
	PrintPolyList(list_b);

	PolyList list_sum;	//多项式和
	list_sum = InitPolyList(list_sum);

	list_sum = Add(list_a, list_b);
	PrintPolyList(list_sum);

	PolyList list_dc;	//多项式微分
	list_dc = InitPolyList(list_dc);

	list_dc = DCPolyList(list_sum);
	PrintPolyList(list_dc);

	PolyList list_mult;	//多项式乘积
	list_mult = InitPolyList(list_mult);

	list_mult = Mcl(list_a, list_b);
	PrintPolyList(list_mult);

	return 0;
}