设计函数分别求两个一元多项式的乘积与和。

输入格式:

输入分2行，每行分别先给出多项式非零项的个数，再以指数递降方式输入一个多项式非零项系数和指数（绝对值均为不超过1000的整数）。数字间以空格分隔。

输出格式:

输出分2行，分别以指数递降方式输出乘积多项式以及和多项式非零项的系数和指数。数字间以空格分隔，但结尾不能有多余空格。零多项式应输出0 0。

输入样例:

4 3 4 -5 2  6 1  -2 0
3 5 20  -7 4  3 1

输出样例:

15 24 -25 22 30 21 -10 20 -21 8 35 6 -33 5 14 4 -15 3 18 2 -6 1
5 20 -4 4 -5 2 9 1 -2 0

代码： 

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

struct Node {
	int coef;
	int expn;
	struct Node * next;
};

struct Node * createList(int n)
{
	struct Node * L = (struct Node *)malloc(sizeof(struct Node));
	struct Node * p = L;
	L->next = NULL;
	while (n--)
	{
		int coef, expn;
		scanf("%d%d", &coef, &expn);
		p->next = (struct Node *)malloc(sizeof(struct Node));
		p = p->next;
		p->coef = coef;
		p->expn = expn;
		p->next = NULL;
	}
	return L;
}

void print(struct Node * L)
{
	for (struct Node * p = L; p->next != NULL; p = p->next)
		printf("%d %d%s", p->next->coef, p->next->expn, p->next->next == NULL ? "\n" : " ");
	return;
}

// 把A加到B中
void addAtoB(struct Node * A, struct Node * B)
{
	struct Node *preb = B;
	while (A->next != NULL && preb->next != NULL)
	{
		if (A->next->expn > preb->next->expn)
		{
			// preb后面插入A->next节点
			struct Node * tmp = A->next;
			A->next = tmp->next;
			tmp->next = preb->next;
			preb->next = tmp;
		}
		else if (A->next->expn < preb->next->expn)
		{
			preb = preb->next;
		}
		else
		{
			if (A->next->coef + preb->next->coef == 0)
			{
				struct Node * tmp = A->next;
				A->next = tmp->next;
				free(tmp);
				tmp = preb->next;
				preb->next = tmp->next;
				free(tmp);
			}
			else
			{
				preb->next->coef += A->next->coef;
				struct Node * tmp = A->next;
				A->next = tmp->next;
				free(tmp);
			}
		}
	}
	if (A->next != NULL)
	{
		preb->next = A->next;
		A->next = NULL;
	}
	if (B->next == NULL)
	{
		B->next = (struct Node *)malloc(sizeof(struct Node));
		B->next->next = NULL;
		B->next->coef = B->next->expn = 0;
	}
	return;
}

struct Node * multi(struct Node * A, struct Node * B)
{
	struct Node * L = (struct Node *)malloc(sizeof(struct Node));
	L->next = NULL;
	
	for (struct Node * pa = A->next; pa != NULL; pa = pa->next)
	{
		struct Node * prel = L;
		for (struct Node * pb = B->next; pb != NULL; pb = pb->next)
		{
			int newCoef = pa->coef * pb->coef;
			int newExpn = pa->expn + pb->expn;
			if (newCoef == 0) continue;
			struct Node * prel = L;
			if (prel->next == NULL)
			{
				int b = 1;
			}
			for (;prel->next != NULL && prel->next->expn > newExpn ; prel = prel->next)
			{
				int a = 1;
			}

			if (prel->next == NULL || prel->next->expn < newExpn)
			{
				struct Node * tmp = (struct Node *)malloc(sizeof(struct Node));
				tmp->coef = newCoef;
				tmp->expn = newExpn;
				tmp->next = prel->next;
				prel->next = tmp;
			}
			else
			{
				prel->next->coef += newCoef;
				if (prel->next->coef == 0)
				{
					struct Node * tmp = prel->next;
					prel->next = tmp->next;
					free(tmp);
				}
			}

		}
	}

	if (L->next == NULL)
	{
		L->next = (struct Node *)malloc(sizeof(struct Node));
		L->next->next = NULL;
		L->next->coef = L->next->expn = 0;
	}

	return L;
}


int main(void)
{
	int la, lb;
	scanf("%d", &la);
	struct Node * A = createList(la);
	scanf("%d", &lb);
	struct Node * B = createList(lb);

	// 乘法
	struct Node * D = multi(A, B);
	print(D);

	// 加法
	addAtoB(A, B);
	print(B);
	return 0;
}