【数据结构OJ】DS线性表—多项式相加

题目描述

对于一元多项式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个空格隔开。

IO模式

本题IO模式为标准输入/输出(Standard IO)，你需要从标准输入流中读入数据，并将答案输出至标准输出流中。

输入样例：

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
输出样例

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

AC代码

#include <iostream>
using namespace std;

class node {
	public:
		int data;  
		int cs;   
		node *next = nullptr;
};

void disp(node *head) {
	node *p = head->next;
	bool first = true;
	while (p) {
		if (p->data != 0) {
			if (!first) {
				cout << " + ";
			} else {
				first = false;
			}
			if (p->data < 0) {
				cout << "(" << p->data << ")";
			} else {
				cout << p->data;
			}
			if (p->cs != 0) {
				cout << "x^";
				if (p->cs < 0) {
					cout << "(" << p->cs << ")";
				} else {
					cout << p->cs;
				}
			}
		}
		p = p->next;
	}
	cout << endl;
}

void create(int data, int cs, node *head) {
	node *p = head;
	while (p->next) {
		p = p->next;
	}
	node *temp = new node;
	temp->data = data;
	temp->cs = cs;
	temp->next = nullptr;
	p->next = temp;
}
node *LL_merge(node *La, node *Lb) {
	node *Lc = new node;  
	node *p = Lc;        
	node *pa = La->next; 
	node *pb = Lb->next; 

	while (pa != nullptr && pb != nullptr) {
		if (pa->cs == pb->cs) {
			int sum = pa->data + pb->data;
			if (sum != 0) {
				p->next = new node;
				p = p->next;
				p->cs = pa->cs;
				p->data = sum;
				p->next = nullptr;
			}
			pa = pa->next;
			pb = pb->next;
		} else if (pa->cs < pb->cs) {
			p->next = new node;
			p = p->next;
			p->cs = pa->cs;
			p->data = pa->data;
			p->next = nullptr;
			pa = pa->next;
		} else {
			p->next = new node;
			p = p->next;
			p->cs = pb->cs;
			p->data = pb->data;
			p->next = nullptr;
			pb = pb->next;
		}
	}
	while (pa != nullptr) {
		p->next = new node;
		p = p->next;
		p->cs = pa->cs;
		p->data = pa->data;
		p->next = nullptr;
		pa = pa->next;
	}
	while (pb != nullptr) {
		p->next = new node;
		p = p->next;
		p->cs = pb->cs;
		p->data = pb->data;
		p->next = nullptr;
		pb = pb->next;
	}

	return Lc;
}

int main() {
	int t, n, d, cs;
	cin >> t;  
	while (t--) {
		cin >> n;
		node *La = new node;
		for (int i = 0; i < n; i++) {
			cin >> d >> cs;
			create(d, cs, La);
		}
		cin >> n;
		node *Lb = new node;
		for (int i = 0; i < n; i++) {
			cin >> d >> cs;
			create(d, cs, Lb);
		}
		disp(La);
		disp(Lb);
		node *Lc = LL_merge(La, Lb);
		disp(Lc);
	}
	return 0;
}