目录

多项式的单向链表表示

参考代码

图解存储方式

 多项式加法

图解算法原理

新结点的生成

参考代码

多项式加法参考代码

---

多项式的单向链表表示

通常情况下，要存储的多项式为：

其中， 是非零系数， 是非负整形指数，。把每一项表示为一个结点，该结点包含系数域，指针域和指向下一项的指针。假设系数为整数，则结点可由下方所示：

---

参考代码

---

typedef struct poly_node *poly_pointer
typedef struct poly_node {
	int coef;
	int expon;
	poly_pointer link;
}; 

---

图解存储方式

---

我们来看看这两个多项式的存储方式：

 多项式加法

图解算法原理

---

为了将两个多项式相加，从 a 和 b 所指向的结点开始比较两个多项式的各个项。如果这两项的指数相同，那么把它们的系数相加，并生成一个新的结果项，然后移动这两个指针，分别指向多项式 a 和 b 的下一个结点。如果 a 的当前项指数小于 b 的当前项指数，那么生成 b 的副本项，加入到结果 d 中，并移动指针指向 b 的下一项。如果 a−>exp⁡on>b−>exp⁡on,那么对 a 采取同样的操作。

多项式的处理过程如下所示：

第一步：a−>exp⁡on==b−>exp⁡on

第二步：a−>exp⁡on<b−>exp⁡on

第三步：a−>exp⁡on>b−>exp⁡on

后面的情况处理方法相同，这里就不一一展开说明了

---

新结点的生成

---

每次生成一个新结点，设置它的 coef 域和 expon 域，并将它添加到 d 的尾部，为了避免每次加入新结点时都搜索 d 的最后结点，使用函数 rear 指向 d 中最后的结点。

参考代码

void attach(float coefficient,int exponent,poly_pointer *ptr)
{
	poly_pointer temp;
	temp=(poly_pointer)	malloc(sizeof(poly_node));
	temp->coef=coefficient;
	temp->expon=exponent;
	(*ptr)->link=temp;
	*ptr=temp;
} 

---

多项式加法参考代码

poly_pointer padd(poly_pointer a,poly_pointer b)
{
	poly_pointer front, rear, temp;
	int sum;
	rear=(poly_pointer) malloc(sizeof(poly_node));
	front=rear;
	while(a&&b)
		switch(COMPARE(a->expon,b->expon)){
			case-1://a->expon<b->expon
				attach(b->coef,b->expon,&rear);
				b=b->link;
				break;
			case 0://a->expon=b->expon
				sum=a->coef+b->coef;
				if(sum) attach(sum,a->expon,&rear);
				a=a->link;b=b->link;
				break;
			case 1://a->expon>b->expon
				attach(a->coef,a->expon,&rear);
				a=a->link;
		}
	//复制链表 a 的其余部分，然后复制链表 b
	for(;a;a=a->link) attach(a->coef,a->expon,&rear);
		for(;b;b=b->link) attach(b->coef,b->expon,&rear);
			rear->link=NULL;
	//删除额外的初始节点
	temp=front;front=front->link;free(temp);
	return front;
}

多项式结点的删除

链表非常适合用于多项式的操作，利用链表作为链表存储表示，可以更方便的写出多项式的输入，输出，加法，减法和乘法等操作函数。如果需要操作更多的多项式，那么回收用于表示多项式的结点是很有必要的。通过回收结点，还可以利用它来保存其他的多项式。

---

参考代码

---

void erase(poly_pointer *ptr)
{
	poly_pointer temp;
	while(*ptr)
	{
		temp=*ptr;
		*ptr=(*ptr)->link;
		free(temp);
	}	
}