线性结构 -- 一元多项式的乘法与加法运算

题目

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

输入格式:
输入分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

总的来说，这道题虽说是数据结构的题，不过我更感觉它像模拟题（坑点巨多）。这道题有两种做法，一种是用数组的方式进行对数据的存储，另一种是链表的方式来写的（不过我还没写，打算先把剩下的知识点过一遍先，前面在搞链表的时候拖延症都有了）。

总结：这道题应该用程序框架去写的，显得规范些，这个还是要改进一波。程序框架大致是：读入多项式1 -> 读入多项式2 -> 进行多项式的乘法运算并输出 -> 进行多项式的加法运算并输出。

多项式乘法的精髓：首先拿一个一维数组mul[n] = a，n表示多项式的指数，a表示多项式的系数，因为数组不可能的开那么大，这么操作的原因是乘法后可能，按照题目范围，n与a的绝对值都不可能超过1000，那也就是说，假设两个多项式都为1000x ^ 1000时，可以发现相乘后指数为2000，而系数却为1e6，开数组就有些困难，这也就是为什么数组下标是指数的原因。接下来分三种情况，第一种是假设第一个多项式为2x^2，另一个多项式为1，相乘后多项式系数变为2 * 1 = 1，指数仍是第一个多项式的指数。第二种是假如前者为0就颠倒过来。第三种是当两者都不为0的时候，我们要把二者指数相加，系数相乘即可。输出就要遍历一下，看看是否为零多项式，也就是计算完之后多项式结果都为0 或者起初就有一个多项式为0多项式的，那么就要输出（0 0），其次还有就是输出格式的控制。

多项式加法的精髓：这个可以用一个结构数组来对系数和指数进行存储，当第一项的多项式的指数与第二项多项式的指数相同时，那么直接进行系数相加。而当第一项的指数大于第二项指数时，第一项直接放入add这个结构数组中，并且第一项多项式往下遍历，反之类似。

Code：

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<stdlib.h>
#include<string.h>
#include<math.h>
using namespace std;
typedef long long LL;
const int maxn = 1e4 + 7;
const int maxm = 2e5 + 7;
const long long inf = 0x3f3f3f3f;
const long long mod = 1e9 + 7;
int n, m, cnt = 0, temp = 0;
struct Node
{
	int coef; //系数 
	int expon; //指数 
}p1[maxn], p2[maxn], add[maxn];
int mul[maxn]; //mul[n] = a, n是指数, a是系数 

void printfMul()
{
	int flag = 0;
	for(int i = maxn; i >= 0; i--)
	{
		if(mul[i] && flag)
			printf(" %d %d", mul[i], i);
		if(mul[i] && !flag) //如果系数不为0且是第一个输出 
		{
			printf("%d %d", mul[i], i);
			flag = 1;
		}		 
	}
	if(!flag) //为零表达式 
		printf("0 0");
	printf("\n");
}

void printfAdd()
{
	int flag = 0; 
	for(int i = 1; i <= cnt; i++)
	{
		if(add[i].coef && flag)
			 printf(" %d %d", add[i].coef, add[i].expon);
		if(add[i].coef && !flag) //判断系数是否为0 且第一个输出控制格式 
		{
			printf("%d %d", add[i].coef, add[i].expon);
			flag = 1;
		}
	}
	if(!flag) //为零多项式 
		printf("0 0");
}

int main()
{
	scanf("%d", &n);
	for(int i = 0; i < n; i++)
		scanf("%d%d", &p1[i].coef, &p1[i].expon);
	scanf("%d", &m);
	for(int i = 0; i < m; i++)
		scanf("%d%d", &p2[i].coef, &p2[i].expon);
	//多项式乘法 
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < m; j++)
		{
			if(p1[i].expon == 0)
			{
				temp = p2[j].expon; //指数 
				mul[temp] += p1[i].coef * p2[j].coef;
			}
			else if(p2[i].expon == 0)
			{
				temp = p1[i].expon;
				mul[temp] += p1[i].coef * p2[j].coef;
			}
			else
			{
				temp = p1[i].expon + p2[j].expon;
				mul[temp] += p1[i].coef * p2[j].coef;
			}
		}
	}
	printfMul();
	//多项式加法 
	for(int i = 0, j = 0; i < n || j < m; )
	{
		//比较两个多项式的指数大小 
		if(p1[i].expon == p2[j].expon)
		{
			add[++cnt].coef = p1[i].coef + p2[j].coef;
			add[cnt].expon = p1[i].expon;
			i++;
			j++;
		}
		if(p1[i].expon > p2[j].expon)
		{
			add[++cnt].coef = p1[i].coef;
			add[cnt].expon = p1[i].expon;
			i++;
		}
		if(p1[i].expon < p2[j].expon)
		{
			add[++cnt].coef = p2[j].coef;
			add[cnt].expon = p2[j].expon;
			j++;
		}
	}
	printfAdd();
	return 0;
} 

/*
注意： 
1.两个多项式都为0项
2.一个多项式的指数为0 另一个指数不为0的情况，此时应系数相乘，指数取不为0的那一项
3. 存在相同指数的项要合并 

hack:
	
2 -1 1 1 0
2 1 1 -1 0
-1 2 2 1 -1 0
0 0

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

0
1 999 1000
0 0
999 1000

*/

线性结构 -- 一元多项式的乘法与加法运算

原文：https://www.cnblogs.com/K2MnO4/p/12724288.html