题目按照指数递减的顺序给出两个一元多项式，输出两个多项式的乘积，还有 和 ，按照指数递减的顺序。
用链表实现一元多项式的乘法与加法运算。
首先来看加法运算
多项式 poly1 x^4 + 3x^3 + 6x
多项式 poly2 6x^5 + 4x^4 + 6
既然用到链表，自然少不了结构体
struct node{
int coef; //系数
int expn; //指数
node* next;
};
实现这加法，只要新创建一个空链表，用两个“游标” cur1，cur2 分别指向两个多项式的头节点，每次找到指数较大的项加入新链表，相应的cur = cur->next,
如果当前的两个对应项的指数相同，就把他们的系数相加， 如果和不为零，就把它加到新链表中。
乘法，模拟乘法即可，每次用poly1的每一项依次乘以 poly2的每一项，再调用求和函数即可。（因为每次求和都保证了当前序列是递减的）
具体来看代码吧。
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct node{
int coef; //系数
int expn; //指数
node* next;
};
node* creat_list(int n){ //读入链表
node *head, *r;
head = new node;
r = head;
int coef , expn;
while(n--){
scanf("%d%d",&coef,&expn);
node* tmp = new node; //创建临时结点
tmp->coef = coef;
tmp->expn = expn;
r->next = tmp; //临时结点接到链表中
r = tmp;
}
r->next = NULL; //结尾设为 NULL
return head;
}
node* add_list(node* a,node* b){
node *r,*fans, *ans;
node *ha,*hb; //为了防止修改指针本身的值，使用代理指针来完成操作，也就是游标。
fans = new node;
ans = fans; //ans 作为fans 的”游标“
ha = a->next;
hb = b->next;
while(ha && hb){
node* tmp = new node; //建立一次即可
if(ha->expn > hb->expn){ //每次把指数（exponent）较大的加入链表fans
tmp->coef = ha->coef;
tmp->expn = ha->expn;
ans->next = tmp;
ans = tmp;
ha = ha->next;
}
else if(ha->expn < hb->expn){
tmp->coef = hb->coef;
tmp->expn = hb->expn;
ans->next = tmp;
ans = tmp;
hb = hb->next;
}
else{
int mulOfcoef = (ha->coef)+(hb->coef); //如果指数相同， 就把系数求和。
if(mulOfcoef!=0){
tmp->coef = mulOfcoef;
tmp->expn = ha->expn;
ans->next = tmp;
ans = tmp;
}
ha = ha->next; //注意这里 即使和为0 ，也要移动“游标”
hb = hb->next;
}
}
while(ha){
node* tmp = new node;
tmp->coef = ha->coef;
tmp->expn = ha->expn;
ans->next = tmp;
ans = tmp;
ha = ha->next;
}
while(hb){
node* tmp = new node;
tmp->coef = hb->coef;
tmp->expn = hb->expn;
ans->next = tmp;
ans = tmp;
hb = hb->next;
}
ans->next = NULL; //结尾设为 NULL
return fans;
}
node* multi_list(node* a,node* b){
node* ha, *hb;
node* ans,*fans;
ha = a->next;
hb = b->next;
fans = creat_list(0);
if(ha == NULL || hb == NULL){
return fans;
}
node* tmp;
while(ha != NULL){
tmp = new node;
ans = tmp;
hb = b->next; //每次都是从 b 的第一项开始乘；
while(hb != NULL){
node* ltmp = new node;
ltmp->expn = ha->expn + hb->expn; //指数相加，系数相乘
ltmp->coef = ha->coef * hb->coef;
hb = hb->next;
ans->next= ltmp;
ans = ltmp;
}
ans->next = NULL;
fans = add_list(fans,tmp); //将乘法 分解成一次次的加法
ha = ha->next;
}
return fans;
}
void print_list(node* l){
node *hc;
int flag = 0;
hc = l->next; //指针操作常用，用新创立的节点代替源节点操作
if(hc == NULL){ //格式控制 。。 真坑！
printf("0 0");
}
while(hc != NULL){
if(flag)
printf(" ");
else
flag = 1;
printf("%d %d",hc->coef,hc->expn);
hc = hc->next;
}
}
int main(){
int n;
scanf("%d",&n);
node *a = creat_list(n);
int m;
scanf("%d",&m);
node* b = creat_list(m);
node* c = add_list(a,b);
node* d = multi_list(a,b);
print_list(d);
printf("\n");
print_list(c);
printf("\n");
return 0;
}
C语言版本的戳笔者参考的这个网址C语言版本 ，
对于这个题，开始也用了模拟的方法做了，用到了map，写的较乱。。格式错误wa了无数次
给网上的测试数据吧
样例输入与输出：
| 序号 | 输入 | 输出 |
| 1 |
4 3 4 -5 2 6 1 -2 0 3 5 20 -7 4 3 1 |
15 24 -25 22 30 21 -10 20 -21 8 35 6 -33 5 14 4 -15 3 18 2 -6 1 5 20 -4 4 -5 2 9 1 -2 0 |
| 2 |
2 1 2 1 0 2 1 2 -1 0 |
1 4 -1 0 2 2 |
| 3 |
2 -1000 1000 1000 0 2 1000 1000 -1000 0 |
-1000000 2000 2000000 1000 -1000000 0 0 0 |
| 4 |
0 1 999 1000 |
0 0 999 1000 |
【结构体模拟版本】
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
using namespace std;
const int maxn = 100000;
struct node{
int x, sub;
}poly[maxn],poly2[maxn];
int main(){
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d%d",&poly[i].x,&poly[i].sub);
}
int m;
scanf("%d",&m);
for(int i=0;i<m;i++){
scanf("%d%d",&poly2[i].x,&poly2[i].sub);
}
map<int,int>mp;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
int a=poly[i].x*poly2[j].x;
int sub = poly[i].sub+poly2[j].sub;
mp[sub]+=a;
}
}
int sign=0;
if(!mp.empty()){
map<int,int>::iterator it= mp.end();
it--;
for(;it!=mp.begin();it--){
if(it->second!=0){
if(!sign)
sign=1;
else
cout<<" ";
cout<<it->second<<" "<<it->first;
}
}
if(sign && it->second !=0){
cout<<" "<<it->second<<" "<<it->first;
}
else if(!sign && it->second !=0){
sign = 1;
cout<<it->second<<" "<<it->first;
}
}
if(!sign){
cout<<"0 0";
}
cout<<endl;
int beg=0;
int beg2=0;
sign=0;
while(beg!=n && beg!=m){
if(poly[beg].sub>poly2[beg2].sub)
{
if(!sign)
sign=1;
else
cout<<" ";
cout<<poly[beg].x<<" "<<poly[beg].sub;
beg++;
}
else if(poly[beg].sub<poly2[beg2].sub){
if(!sign)
sign=1;
else
cout<<" ";
cout<<poly2[beg2].x<<" "<<poly2[beg2].sub;
beg2++;
}
else{
int tmpadd = poly[beg].x + poly2[beg2].x ;
if( tmpadd == 0){
}
else{
if(!sign)
sign=1;
else
cout<<" ";
cout<<tmpadd<<" "<<poly[beg].sub;
}
beg++;
beg2++;
}
}
while(beg!=n){
if(!sign)
sign=1;
else
cout<<" ";
cout<<poly[beg].x<<" "<<poly[beg].sub;
beg++;
}
while(beg2!=m){
if(!sign)
sign=1;
else
cout<<" ";
cout<<poly2[beg2].x<<" "<<poly2[beg2].sub;
beg2++;
}
if(!sign)
cout<<"0 0";
cout<<endl;
return 0;
}
原文链接: https://www.cnblogs.com/bianchengjun520/p/5321161.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/221719
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
