温馨提示：本题为深大OJ原题，深大的同学请勿直接抄袭，以免出现多个代码相同以致评0分的情况，代码和思路仅供参考，希望大家能逐步成长。
题目描述
对于一元多项式p(x)=p0 p1x p2x2 … pnxn，每个项都有系数和指数两部分，例如p2x2的系数为p2,指数为2。
编程实现两个多项式的相加。
例如5 x 2x2 3x3，-5-x 6x2 4x4，两者相加结果：8x2 3x3 4x4
其中系数5和-5都是x的0次方的系数，相加后为0，所以不显示。x的1次方同理不显示。
要求用单链表实现。
输入
第1行：输入t表示有t组测试数据
第2行：输入n表示有第1组的第1个多项式包含n个项
第3行：输入第一项的系数和指数，以此类推输入n行
接着输入m表示第1组的第2个多项式包含m项
同理输入第2个多项式的m个项的系数和指数
参考上面输入第2组数据，以此类推输入t组
假设所有数据都是整数
输出
对于每1组数据，先用两行输出两个原来的多项式，再用一行输出运算结果，不必考虑结果全为0的情况
输出格式参考样本数据，格式要求包括：
1.如果指数或系数是负数，用小括号括起来。
2.如果系数为0，则该项不用输出。
3.如果指数不为0，则用符号^表示，例如x的3次方，表示为x^3。
4.多项式的每个项之间用符号 连接，每个 两边加1个空格隔开。
输入样例1
2 4 5 0 1 1 2 2 3 3 4 -5 0 -1 1 6 2 4 4 3 -3 0 -5 1 2 2 4 9 -1 2 0 3 1 -2 2
输出样例1
5 1x^1 2x^2 3x^3 (-5) (-1)x^1 6x^2 4x^4 8x^2 3x^3 4x^4 (-3) (-5)x^1 2x^2 9x^(-1) 2 3x^1 (-2)x^2 9x^(-1) (-1) (-2)x^1
思路分析
这是一道经典的例题。
我们假设你已经会了链表的插入操作，在这基础上我们讲讲这道题。
首先必须先说的就是输入的问题，这个格式输出本身很讲究技巧，括号配负数这个不难，比较棘手的是加号什么时候输入，如果你的链表里面存了系数为0的项，这里的判断就要很讲究，你可能需要判断当系数为0的时候就直接跳过这个节点不输出，事情有没有那么简单我还不清楚，因为我后来想到了另一种解决方法，那就是在插入的时候，系数为0的项我直接不存@_@，这样我就不用考虑系数为0的情况了。
然后是相加的操作，依旧是新链表来装结果，先记录两个链表的开始节点，然后循环遍历，先找指数相同的加起来，为0的就不用存了，不为0的就插入新链表，同类项合并完之后，比较指数大小，小的先插入，直到其中有一个链表遍历完了跳出循环，再把另一个链表剩下的元素插入。
AC代码
代码语言：javascript复制#include <iostream>
using namespace std;
class Node {
public:
int factor, index;
Node * next;
};
class List {//带头结点的单链表，位置从0到n，0是头结点，1是首结点，n是尾结点
public:
Node * head; //头结点
int size; //表长
List(); //构造函数，创建头结点
~List(); //析构函数，逐个结点回收
int Insert(int factor, int index, int i); //第i位置插入元素，操作成功或失败返回OK或ERROR
void print(); //打印单链表所有数据
int Plus(Node *La, Node *Lb) {
Node*pa = La, *pb = Lb;
while (pa && pb) {
if (pa->index == pb->index) {
Insert(pa->factor pb->factor, pa->index, size 1);
pa = pa->next;
pb = pb->next;
} else if (pa->index < pb->index) {
Insert(pa->factor, pa->index, size 1);
pa = pa->next;
} else {
Insert(pb->factor, pb->index, size 1);
pb = pb->next;
}
}
while (pa) {
Insert(pa->factor, pa->index, size 1);
pa = pa->next;
}
while (pb) {
Insert(pb->factor, pb->index, size 1);
pb = pb->next;
}
return 0;
}
};
List::List(): size(0) {
head = new Node();
}
List::~List() {
Node *p, *q;
p = head->next;
while (p != NULL) {
q = p;
p = p->next;
delete q;
}
size = 0;
head->next = NULL;
}
int List::Insert(int factor, int index, int i) {
if(factor==0)
return 0;
Node*p = head;
int j = 1;
while (j < i) {
p = p->next;
}
Node*q = new Node();
q->factor = factor;
q->index = index;
q->next = p->next;
p->next = q;
size ;
return 0;
}
void List::print() {
Node*p = head->next;
for (int i = 1; i <= size; i ) {
if (p->factor < 0)
cout << '(' << p->factor << ')';
else if (p->factor > 0)
cout << p->factor;
if (p->index < 0 && p->factor)
cout << "x^(" << p->index << ')';
else if (p->index > 0 && p->factor)
cout << "x^" << p->index;
if (i != size)
cout << " ";
p = p->next;
}
cout << endl;
}
int main() {
int t, n, m, factor, index;
cin >> t;
while (t--) {
List a, b, c;
cin >> n;
for (int i = 1; i <= n; i ) {
cin >> factor >> index;
a.Insert(factor, index, i);
}
a.print();
cin >> m;
for (int i = 1; i <= m; i ) {
cin >> factor >> index;
b.Insert(factor, index, i);
}
b.print();
c.Plus(a.head->next, b.head->next);
c.print();
}
}
