【数据结构】C++单链表实现多项式加法（直接输入多项式）

题目描述：
计算两个多项式的和。

输入：
输入有两行，每行为一个每项按照指数从大到小顺序的多项式，多项式的每一项用mx^n表示，其中系数m为非0整数，指数n是非负整数。

输出：
输出两个多项式相加的结果，要求按照每项的指数，从大到小顺序输出每项。如果某个指数的项在求和运算中系数为0，则不输出。如果和的每项系数均为0，则这两个多项式求和为0，结果输出0。

样例1输入：
15x^4+4x^3+7x^1
-7x^1-6x^0

样例1输出：
15x^4+4x^3-6x^0

样例2输入：
-1x^2-1x^1
1x^2+1x^1

样例2输出：
0

（题目来源：njucs.程设实验.第四周，禁止作业抄袭，转载请注明出处）

---

分析：本题重点在于多项式的输入，这里我采用的是cin.peek()的方式，也就是让编译器看一眼缓冲区下一个输入是否是换行符；然后分别用int和char类型存放数据。多项式加法采取常规算法，用p1,p2两个指针分别遍历两个多项式，分类讨论三种情况后放到结果多项式中去，详见注释。

代码如下：

---

#include<iostream> using namespace std;//定义多项式结构体 struct Poly {int m;//系数int n;//指数Poly* next; };Poly* scanf() {char a, b, c, d, e;Poly* head = NULL;Poly* start = new Poly;//从字符串中读取多项式系数和指数，对负号做特判if (cin.peek() == '-'){char f;//f='-',a='x',b='^'cin >> f >> start->m >> a >> b >> start->n;start->m = -start->m;}else{//a='x',b='^'cin >> start->m >> a >> b >> start->n;}start->next = head;head = start;Poly* tail = start;if (cin.peek() != '\n'){while (cin >> c){Poly* p = new Poly;cin >> p->m >> d >> e >> p->n;//输入有负号时将系数置为相反数if (c == '-')p->m = -p->m;//尾插法创建多项式链表p->next = tail->next;tail->next = p;tail = p;//采用cin.peek()的方法判断换行if (cin.peek() == '\n')break;}}return head; }void printf(Poly* head) {//输出结果为零时做特判if (head == NULL)cout << 0 << endl;else {//第一项要单独输出Poly* cur = head;cout << cur->m << "x^" << cur->n;cur = cur->next;while (cur != NULL){//第二项之后系数为负直接输出，系数为正则要先输出一个＋号if (cur->m < 0)cout << cur->m << "x^" << cur->n;elsecout << "+" << cur->m << "x^" << cur->n;cur = cur->next;}cout << endl;} }Poly* Add_Poly(Poly* head1, Poly* head2) {Poly* head = NULL;Poly* p1 = head1;Poly* p2 = head2;Poly* tail = head;//使用p1,p2两个指针分别遍历两个多项式链表，有三种情况：//p1所在项指数大于p2，直接尾插入结果多项式链表中//p2所在项指数大于p1，同理//所在项指数相等时，系数相加，插入结果链表中(若系数等于零不输出)while (p1 != NULL || p2 != NULL){if (p1->n > p2->n){Poly* p = new Poly;p->n = p1->n;p->m = p1->m;if (tail == NULL){p->next = NULL;head = p;tail = p;}else{p->next = tail->next;tail->next = p;tail = p;}p1 = p1->next;}if (p2->n > p1->n){Poly* p = new Poly;p->n = p2->n;p->m = p2->m;if (tail == NULL){p->next = NULL;head = p;tail = p;}else{p->next = tail->next;tail->next = p;tail = p;}p2 = p2->next;}if (p1->n == p2->n){Poly* p = new Poly;p->n = p1->n;p->m = p1->m+p2->m;if (p->m != 0){if (tail == NULL){p->next = NULL;head = p;tail = p;}else{p->next = tail->next;tail->next = p;tail = p;}}p1 = p1->next;p2 = p2->next;}//其中一个多项式遍历完之后，将另一个多项式剩余项放入结果中if (p1 == NULL){while (p2 != NULL){Poly* p = new Poly;p->n = p2->n;p->m = p2->m;if (tail == NULL){p->next = NULL;head = p;tail = p;}else{p->next = tail->next;tail->next = p;tail = p;}p2 = p2->next;}}if (p2 == NULL){while (p1 != NULL){Poly* p = new Poly;p->n = p1->n;p->m = p1->m;if (tail == NULL){p->next = NULL;head = p;tail = p;}else{p->next = tail->next;tail->next = p;tail = p;}p1 = p1->next;}}}return head; }int main() {Poly* head1 = scanf();Poly* head2 = scanf();printf(head1);printf(head2);printf(Add_Poly(head1, head2));return 0; }

---

程序运行结果如下：

---

总结：多项式问题是数据结构绕不开的问题，但本题和以往问题的不同之处在于多项式是直接从键盘上输入的，需要一个解析字符串并转换到链表的过程，也可以用string类来完成。能力有限，不足之处请指正！

总结

以上是生活随笔为你收集整理的【数据结构】C++单链表实现多项式加法（直接输入多项式）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。