多项式相加

【题目描述】给出两个多项式，求它们的和

【输入】分别给出两个多项式，每个多项式给出的方式为多组输入。每行给出两个整数a，b表示ax^b，直至输入0 0结束。（可以直接参照样例）

【输出】编写提示信息，每个多项式输入完成后立即输出该多项式的表示，两个多项式都输入完成后，输出两个多项式的和。(描述不够细致可直接参照样例)

【样例】 

输入：

8 5
-2 3
0 0

1 2
3 4
4 3
-3 3
3 0
0 0

输出：

请输入第一个多项式的系数和指数，以（0,0）结束：
请输入系数和指数（如："2 3"表示2x^3):8 5
请输入系数和指数:-2 3
请输入系数和指数:0 0
第一个多项式输出如下：
8x^5-2x^3
请输入第二个多项式的系数和指数，以（0,0）结束：
请输入系数和指数（如："2 3"表示2x^3):
1 2
请输入系数和指数:3 4
请输入系数和指数:4 3
请输入系数和指数:-3 3
请输入系数和指数:3 0
请输入系数和指数:0 0
第二个多项式输出如下：
3x^4+x^3+x^2+3
8x^5+3x^4-x^3+x^2+3

【分析】题目难度不大，主要是坑比较多，思考量比较多。主要的难度点在于多项式的表示以及多项式相加的combine()函数的编写（本质是链表的合并）。链表的基本操作是基础，因为多项式的指数可以是不连续的而且可以很大。理论上开个较大的数组用计数排序的思想也是可行的，但是指数一大就太耗费空间了，而且还要考虑到用二维数组存储系数，所以选择用链表。

思维量集中在多项式的表示，所以在做这道题之前，我先去过了下noi的1.13的第39题，题目如下：​​​​

描述

一元 n 次多项式可用如下的表达式表示：

f(x)=anxn+an-1xn-1+...+a1x+a0，an≠0

其中，aixi称为i次项，ai称为i次项的系数。给出一个一元多项式各项的次数和系数，请按照如下规定的格式要求输出该多项式：

1. 多项式中自变量为x，从左到右按照次数递减顺序给出多项式。

2. 多项式中只包含系数不为0的项。

3. 如果多项式n次项系数为正，则多项式开头不出现“+”号，如果多项式n次项系数为负，则多项式以“-”号开头。

4. 对于不是最高次的项，以“+”号或者“-”号连接此项与前一项，分别表示此项系数为正或者系数为负。紧跟一个正整数，表示此项系数的绝对值（如果一个高于0次的项，其系数的绝对值为1，则无需输出1）。如果x的指数大于1，则接下来紧跟的指数部分的形式为“x^b”，其中b为x的指数；如果x的指数为1，则接下来紧跟的指数部分形式为“x”； 如果x的指数为0，则仅需输出系数即可。

5. 多项式中，多项式的开头、结尾不含多余的空格。

输入

共有2 行：
第一行 1 个整数 n，表示一元多项式的次数。
第二行有 n+1 个整数，其中第 i 个整数表示第 n-i+1 次项的系数，每两个整数之间用空格隔开。

1 ≤ n ≤ 100，多项式各次项系数的绝对值均不超过100。

输出

共1行，按题目所述格式输出多项式。

样例输入

样例 #1：
5
100 -1 1 -3 0 10

样例 #2：
3
-50 0 0 1

样例输出

样例 #1：
100x^5-x^4+x^3-3x^2+10

样例 #2：
-50x^3+1

链接在这：http://noi.openjudge.cn/ch0113/solution/35197972/

下面是我通过的代码：

#include <stdio.h>

int main() {
	int n,m;
	scanf("%d",&n);
	int flag = 1; 
	for(int i=n;i>=0;i--) {
		scanf("%d",&m);
		if(m==0) continue; //系数为0直接跳过 
		if(i==n) { //多项式的最高项 
			if(m==-1) printf("-"); //系数是-1的输出负号 
			else if(m!=1) printf("%d",m); //其他情况只要不是1都原样输出 
		}else if(i==0) { //多项式的最低项 
			if(m==1) printf("+1");
			else if(m==-1) printf("-1");
			else if(m>0 && !flag) printf("+%d",m);
			else if(m>0 && flag) printf("%d",m);
			else if(m<0) printf("%d",m);
			break; //直接跳出循环
		}else {
			if(m==-1) printf("-"); //系数是-1的输出负号 
			else if(m==1) printf("+"); //系数是1的输出正号
			else if(m<0) printf("%d",m); //其他情况是负数就原样输出 
			else if(m>0) printf("+%d",m); //是正数数就加正号后输出  
		}
		if(i==1) printf("x"); //特判指数为1输出x
		else if(i!=0) printf("x^%d",i);//指数不为0就原样输出 
		flag = 0;
	}
	return 0;
}

我认为这道题有个地方出的不好，我第一遍提交的代码当输入为1 0 2是输出结果为+2是可以accepted的。上面的代码是处理过后第二次提交的代码，输出为2，也是可以通过的。

最后直接上多项式相加的代码，细节都在代码里啦：

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

typedef struct polynomial {
	int coefficient;
	int exp;
	struct polynomial * next;
}NODE, *PNODE;

void insert(PNODE L, int coefficient, int exp) {
	PNODE s = (NODE*)malloc(sizeof(NODE));
	s->coefficient = coefficient;
	s->exp = exp;
	s->next = NULL;
	PNODE p = L->next, q = L;
	while(p && p->exp > exp) { //找到第一个指数不大于插入节点的指数的位置并用p指向它 
		q = p;
		p = p->next;
	}
	if(!p) {	//特判p是否为空，即插入在最后的情况 
		q->next = s;
		return;
	}
	if(p->exp == exp) {	 //讨论指数等于p指向节点的指数还是小于p指向节点的指数分别处理 
		p->coefficient += coefficient;
		free(s);
	} else {
		s->next = q->next;
		q->next = s;
	}
}

void input(PNODE &L) {
	L = (NODE*)malloc(sizeof(NODE));
	L->next = NULL;
	int coefficient, exp;
	printf("请输入系数和指数（如：\"2 3\"表示2x^3):");
	scanf("%d%d",&coefficient, &exp);
	insert(L,coefficient,exp);
	while(coefficient || exp) {
		printf("请输入系数和指数:");
		scanf("%d%d",&coefficient, &exp);
		insert(L,coefficient,exp);
	}
}

void print(PNODE L) {
	PNODE p = L;
	int flag = 1;
	while(p) {
		if(p->coefficient==0) {
			p = p->next;
			continue;	
		}
		if(p==L) { //多项式的最高项
			p = L->next;
			if(p->coefficient==-1) printf("-"); //系数是-1的输出负号 
			else if(p->coefficient!=1) printf("%d",p->coefficient); //其他情况只要不是1都原样输出 
		}else if(p->exp==0) { //多项式的最低项 
			if(p->coefficient==1) printf("+1");
			else if(p->coefficient==-1) printf("-1");
			else if(p->coefficient>0 && !flag) printf("+%d",p->coefficient);
			else if(p->coefficient>0 && flag) printf("%d",p->coefficient);
			else if(p->coefficient<0) printf("%d",p->coefficient);
			break; //直接跳出循环
		}else {
			if(p->coefficient==-1) printf("-"); //系数是-1的输出负号 
			else if(p->coefficient==1) printf("+"); //系数是1的输出正号
			else if(p->coefficient<0) printf("%d",p->coefficient); //其他情况是负数就原样输出 
			else if(p->coefficient>0) printf("+%d",p->coefficient); //是正数数就加正号后输出  
		}
		if(p->exp==1) printf("x");
		else if(p->exp) printf("x^%d",p->exp); //指数只要不是0就原样输出
		flag = 0;
		p = p->next;
	}	
	printf("\n");
}

void combine(PNODE &L3, PNODE L1, PNODE L2) {
	L3 = (NODE*)malloc(sizeof(NODE));
	L3->next = NULL;
	PNODE p = L1->next, q = L2->next, r = L3;
	while(p && q) {
		if(p->exp > q->exp) {
			r->next = p;
			p = p->next;
		} else if(q->exp > p->exp) {
			r->next = q;
			q = q->next;
		}else {
			q->coefficient = q->coefficient + p->coefficient;	
			r->next = q;
			q = q->next;
			p = p->next;
		}
		r = r->next;
	}
	r->next = p ? p : q; 
} 

int main() {
	PNODE L1,L2,L3;
	printf("请输入第一个多项式的系数和指数，以（0,0）结束：\n");
	input(L1);
	printf("第一个多项式输出如下：\n");
	print(L1);
	printf("请输入第二个多项式的系数和指数，以（0,0）结束：\n");
	input(L2);
	printf("第二个多项式输出如下：\n");
	print(L2);
	combine(L3,L1,L2);
	print(L3);
	return 0;
}