一元多项式的表示及相加：

我们定义P(x)=p0+p1*x+p2*x^2...pn*x^n简写为P=(p0, p1, p2...pn)

再定义Q=(q0, q1, 12...qm)

现在要求R = P(X) + q(X)，显然，实际上R=(p0+q0, p1+q1, p2+q2 .. pm+1, pn) 假设m<n。

这种应用场景，用顺序存储不合适，它虽然运算简单，但因为很有可能从1~1000次幂都是0，是稀疏的。因此，链表类似的存储更合适。

首先考虑加法，其实算法很简单:
我们假设多项式是按照幂次递增的，例如7+3x+9x^8+5x^17。
假设指针pa和pb分别指向多项式A和B的某个结点，pc指向结果。
(0)while pa!=NULL && pb!=NULL
(1)若pa的幂次<pb的幂次，将pa复制到pc新结点，pa后移动；
(2)若pb的幂次<pa的幂次，pb复制到pc新结点，pb后移动；
(3)若pa幂次和pb幂次相等，则结点的系数相加；pa、pb后移。如果和不为零，则将pa和pb的系数相加，放到pc新结点中，继续操作；
(4)如果退出while后，pa或者pb依然不是0，把他们复制到pc中。

注意：一元多项式相加这种不涉及到进位，退位！

算法如下：

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

struct Node
{
	struct Node* next;
	int exp;
	double conf;
};

void poly_make(struct Node* head, float* confs, int n)
{
	int i = 0;
	int first = 1;
	if(n<=0)
	{
		head->next = NULL;
		head->conf = 0;
		head->exp = 0;
		return ;
	}
	while(i<n)
	{
		if(confs[i]!=0)
		{
			if(first)
			{
				first = 0;
			}
			else
			{
				head->next = (void*)malloc(sizeof(struct Node));
				head = head->next;
			}
			head->conf = confs[i];
			head->exp = i;
			head->next = NULL;
		}
		i++;
	}
}

void poly_free(struct Node* head)
{
	struct Node* ptr = NULL;
	head = head->next;
	while(head!=NULL)
	{
		ptr = head->next;
		free(head);
		head = ptr;
	}
}

void poly_print(struct Node* head)
{
	while(head!=NULL)
	{
		if(head->conf!=-1)
		{
			printf("%f*x^%d ", head->conf, head->exp);
		}
		head = head->next;
	}
	printf("\n");
}

// Add p and q to r
void poly_add(struct Node* p, struct Node* q, struct Node* r)
{
	int first = 1;
	while(p!=NULL && q!=NULL)
	{
		if(p->exp<q->exp)
		{
			r->next = (void*)malloc(sizeof(struct Node));
			r = r->next;
			r->exp = p->exp;
			r->conf = p->conf;
			r->next = NULL;
			p = p->next;
		}else if(p->exp>q->exp)
		{
			r->next = (void*)malloc(sizeof(struct Node));
			r = r->next;
			r->exp = q->exp;
			r->conf = q->conf;
			r->next = NULL;
			q = q->next;
		}else
		{
			if(p->conf+q->conf!=0)
			{
				r->next = (void*)malloc(sizeof(struct Node));
				r = r->next;
				r->exp = q->exp;
				r->conf = q->conf+p->conf;
				r->next = NULL;
			}
			p = p->next;
			q = q->next;
		}
	}
	while(p!=NULL)
	{
		r->next = (void*)malloc(sizeof(struct Node));
		r = r->next;
		r->exp = p->exp;
		r->conf = p->conf;
		r->next = NULL;
		p = p->next;
	}
	while(q!=NULL)
	{
		r->next = (void*)malloc(sizeof(struct Node));
		r = r->next;
		r->exp = q->exp;
		r->conf = q->conf;
		r->next = NULL;
		q->next = q;
	}
}

int main()
{
	struct Node p, q, r;
	float conf1[5] = {1.0, 0, 2.0, 0, 3.0};
	float conf2[3] = {0, 2.0, 4.5};
	// Make
	poly_make(&p, conf1, 5);
	poly_make(&q, conf2, 3);
	// Print p
	printf("p:\n");
	poly_print(&p);
	// Print q
	printf("q:\n");
	poly_print(&q);
	// Add & Print r
	r.exp = -1;
	r.conf = -1;
	poly_add(&p, &q, &r);
	poly_print(&r);
	// Free
	poly_free(&p);
	poly_free(&q);
	poly_free(&r);
	return 0;
}