题目描述

对于一元多项式 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 <-复制

输出样例1

语言: 编译选项

主题:

!!!!这是原版，但是不知道什么原因无法通过

#include
using namespace std;
#define ok 0
#define error -1class ListNode
{
public:int data1; int data2;ListNode* next;ListNode(){next = NULL;}
};class LinkList
{
public:ListNode* head;int len;LinkList();~LinkList();ListNode* LL_index(int i);int LL_insert(int i, int item1, int item2);int LL_del(int i);int getlen();int assign(LinkList& f, string n);int fanhui(LinkList& f, int number);void display_free();void display_used();void add(LinkList& l);void display();
};
LinkList::LinkList()
{head = new ListNode();len = 0;
}
LinkList::~LinkList()
{ListNode* p, * q;p = head;while (p != NULL){q = p;p = p->next;delete q;}len = 0;head = NULL;
}
ListNode* LinkList::LL_index(int i)
{if (i < 0 || i > len){return NULL;}ListNode* p = head;for (int j = 0; j < i; j++){p = p->next;}return p;
}
int LinkList::LL_insert(int i, int item1,int item2)
{if (i <= 0 || i > len + 1){return error;}else{ListNode* p = LL_index(i - 1);ListNode* s = new ListNode();s->data1 = item1;s->data2 = item2;s->next = p->next;p->next = s;len += 1;return ok;}
}
int LinkList::LL_del(int i)
{if (i <= 0 || i > len){return error;}else{ListNode* p = LL_index(i - 1);ListNode* s = p->next;p->next = s->next->next;delete s;len -= 1;return ok;}
}
int LinkList::getlen()
{return len;
}
void LinkList::add(LinkList &q)
{ListNode* pre = head;ListNode* s = pre->next;ListNode* r = q.head->next;while (s != NULL && r != NULL){if (s->data2 < r->data2){s = s->next;pre = pre->next;}else if (s->data2 == r->data2){s->data1 += r->data1;s = s->next;pre = pre->next;r = r->next;q.len--;}else{ListNode* m = new ListNode();m->data1 = r->data1;m->data2 = r->data2;m->next = s;pre->next = m;r = r->next;pre = pre->next;q.len--;}}//如果r有剩余if (r){pre->next = r;len += q.len;}display();
}
void LinkList::display()
{int i;ListNode* p = head->next;for (i = 0; i < len; i++){if (p->data1 == 0){p = p->next;continue;}else if (p->data2 == 0){if (p->data1 < 0)cout << "(" << p->data1 << ")";elsecout << p->data1;p = p->next;}else{if (p->data1 < 0)cout << "(" << p->data1 << ")x^";elsecout << p->data1 << "x^";if (p->data2 < 0)cout << "(" << p->data2 << ")";elsecout << p->data2;p = p->next;}if (i != len - 1)cout << " + ";}cout << endl;
}
int main()
{int t;cin >> t;while (t--){int n;cin >> n;int number, zhishu;LinkList p;LinkList q;ListNode* l = p.head;for (int i = 0; i < n; i++){cin >> number >> zhishu;ListNode* n2 = new ListNode();n2->data1 = number;n2->data2 = zhishu;l->next = n2;n2->next = NULL;l = n2;}p.len = n;p.display();cin >> n;ListNode* l1 = q.head;for (int i = 0; i < n; i++){cin >> number >> zhishu;ListNode *n1 = new ListNode();n1->data1 = number;n1->data2 = zhishu;l1->next = n1;n1->next = NULL;l1 = n1;}q.len = n;q.display();p.add(q);}cout << endl;return 0;
}

!!!这是网上合法的版本

#include 
using namespace std;
class ListNode
{
public:int data1, data2;ListNode *next;ListNode(){next = NULL;}
};
class linklist
{
public:ListNode *head;int len;linklist(){head = new ListNode;len = 0;}~linklist(){ListNode *p, *q;p = head;while(p){q = p;p = p->next;delete q;}len = 0;head = NULL;}void createlist(int n){int i;ListNode *q = head;int d1, d2;for(i = 0; i < n; i++){cin >> d1 >> d2;ListNode *p = new ListNode;p->data1 = d1;p->data2 = d2;q->next = p;p->next = NULL;q = p;}len = n;}void display(){int i;ListNode *p = head->next;for(i = 0; i < len; i++){if(p->data1 == 0){p = p->next;continue;}else if(p->data2 == 0){if(p->data1 < 0)cout << "(" << p->data1 << ")";elsecout << p->data1;p = p->next;}else{if(p->data1 < 0)cout << "(" << p->data1 << ")x^";elsecout << p->data1 << "x^";if(p->data2 < 0)cout << "(" << p->data2 << ")";elsecout << p->data2;p = p->next;}if(i != len-1)cout << " + ";}cout << endl;}void add(linklist *q){ListNode *pre = head;ListNode *s = pre->next;ListNode *r = q->head->next;while(s != NULL && r != NULL){if(s->data2 < r->data2){s = s->next;pre = pre->next;}else if(s->data2 == r->data2){s->data1 = s->data1+r->data1;s = s->next;pre = pre->next;r = r->next;q->len--;}else{ListNode *m = new ListNode;m->data1 = r->data1;m->data2 = r->data2;m->next = s;pre->next = m;r = r->next;pre = pre->next;//len++;q->len--;}}if(r){pre->next = r;len = len+q->len;}}ListNode *index(int i){int k;ListNode *p = head;if(i != 0){for(k = 1; k < i; k++){p = p->next;}return p->next;}else{return head;}}
};
int main()
{int T, n, m;cin >> T;while(T--){linklist *l1 = new linklist,*l2 = new linklist;cin >> n;l1->createlist(n);cin >> m;l2->createlist(m);l1->display();l2->display();l1->add(l2);l1->display();delete l1, l2;}return 0;
}