承接上文，这次增加了多项式的乘法功能以及输出多项式的化简（系数为1省略，系数为-1保留负号，指数为1省略，指数为0只显示系数），多项式表达由mx^n变为mxn。
#includeusing 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() == 'x') { start->m = 1; cin >> a >> start->n; } else if (cin.peek() == '-') { char f; if (cin.peek() == 'x') { start->m = 1; cin >>f>> a >> start->n; } else cin >> f >> start->m >> a >> start->n; start->m = -start->m; } else { cin >> start->m >> a >> start->n; } start->next = head; head = start; Poly* tail = start; if (cin.peek() != 'n') { while (cin >> c) { Poly* p = new Poly; if (cin.peek() == 'x') { p->m = 1; cin >> d >> p->n; } else cin >> p->m >> d >> p->n; if (c == '-') p->m = -p->m; p->next = tail->next; tail->next = p; tail = p; if (cin.peek() == 'n') break; } } return head; } void printf(Poly* head) { //输出结果为零时做特判 if (head == NULL) cout << 0 << endl; else { //第一项要单独输出 Poly* cur = head; if (cur->m == 1) { if (cur->n == 0) cout << "1"; else if (cur->n == 1) cout << "x"; else cout << "x" << cur->n; } if (cur->m == -1) { if (cur->n == 0) cout << "-1"; else if (cur->n == 1) cout << "-x"; else cout << "-x" << cur->n; } else { if (cur->n == 0) cout << cur->m; else if (cur->n == 1) cout << cur->m << "x"; else cout << cur->m << "x" << cur->n; } cur = cur->next; while (cur != NULL) { if (cur->m < 0) { if (cur->m == -1) { if (cur->n == 0) cout << "-1"; else if (cur->n == 1) cout << "-x"; else cout << "-x" << cur->n; } else { if (cur->n == 0) cout << cur->m; else if (cur->n == 1) cout << cur->m << "x"; else cout << cur->m << "x" << cur->n; } } else if(cur->m>0) { if (cur->m == 1) { if (cur->n == 0) cout << "1"; else if (cur->n == 1) cout << "+x"; else cout << "+x" << cur->n; } else { if (cur->n == 0) cout <<"+"< m; else if (cur->n == 1) cout <<"+"<< cur->m << "x"; else cout <<"+"<< cur->m << "xlog2" << 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 && p2 && 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 (p1 && p2 && 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 && p2 && 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; } Poly* Copy_Poly(Poly* head) { Poly* head_copy = NULL; Poly* copy = head; Poly* tail = head_copy; while (copy != NULL) { Poly* p = new Poly; p->m = copy->m; p->n = copy->n; if (tail == NULL) { p->next = NULL; head_copy = p; tail = p; } else { p->next = tail->next; tail->next = p; tail = p; } copy = copy->next; } return head_copy; } Poly* Multipy_Poly(Poly* head1, Poly* head2) { Poly* head = NULL; Poly* cur = head2; Poly* head1_s = Copy_Poly(head1); Poly* p = head1_s; while (p != NULL) { p->m *= cur->m; p->n += cur->n; p = p->next; } head = head1_s; cur = cur->next; while (cur != NULL) { Poly* head1_copy = Copy_Poly(head1); //用head2的各项分别乘以head1_s，累加求和 Poly* p = new Poly; p = head1_copy; while (p != NULL) { p->m *= cur->m; p->n += cur->n; p = p->next; } head = Add_Poly(head, head1_copy); cur = cur->next; } return head; } int main() { Poly* head1 = scanf(); Poly* head2 = scanf(); printf(head1); printf(head2); printf(Add_Poly(head1, head2)); printf(Multipy_Poly(head1, head2)); return 0; }
