C++一元多项式的乘法运算(单链表实现)

多项式的乘法运算(单链表实现)"/>

C++一元多项式的乘法运算(单链表实现)

        数据结构的课后作业，乍一看把我给难住了，得亏网友给力嘛（百度一下就是香）！这题细节很多，我当笔记写了。

题目描述:

给你两个一元多项式，输出这两个一元多项式的乘积。

输入格式：输入包含两行，每行一个一元多项式。每行开头一个数字n,表示该多项式非零项项数，后面有n组数字，每组数字包含两个数字，按顺序分别为该项的系数和指数。

输出格式：输出包含一行，按指数从大到小的顺序输出乘积的非0项的系数与指数，以空格分隔开。如果最终结果为0，直接输出0 0。

输入样例：
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

解题思路：

        多项式乘法，就是每项展开分别相乘后再相加。我们可以把系数a和指数exp放在一起存起来，作为一个节点node。那为啥会想到用单链表实现呢？（因为这是单链表的习题bushi）~~~其实我一开始都想用两个数组暴力操作呢，只能说有些思路很适合特定的题，多见则不怪。

        言归正传，我们先解决相乘问题：两重循环让两条链表各自的节点进行相乘操作，即系数相乘、指数相加。这时我们会有疑惑了，那该怎么保留运算之后的节点呢？别急，因为这要两步完成，乘法之中包含加法运算~~~假如，第一个多项式有n项，第二个多项式有m项，展开相乘后最多有n*m项。我们自己手算的时候接下来该怎么办？显然是合并同类项。那对链表进行操作时，就是依次将n*m个节点按降幂顺序添加至链表中，遇到指数相同的就相加后添加，遇到系数为0的不用添加（这里想清楚哦）。再解决相加问题：其实看到这，你就会发现我的加法思路了：即在链表添加节点的时候进行加法操作（同时进行），因为添加节点时就能设置我上面所说的条件。结果为0的处理：这是我认为这道题最妙的细节点，按照我的上述思路实现代码时，我们会发现从一开始初始化链表时遇到 0 系数的情况并没有添加至链表，比如来个恶心的样例 ：

4 4 3 -2 2 0 1 10 0 等价于4x^3-2x^2+0x^1+10x^0;这样就会节省空间，也会减少运算时间（任何数与0相乘都为0故省略，多提一句常数项为0也可以省喔）。其次，假如相乘再相加系数为0呢？那也会在添加的时候省略呀！想一下~~soga了是吧。最后，怎么输出“0 0”呢？我们只需判断头节点是否为空就行了！！！

        拓展思考：那多项式的减法呢：将加法部分的逻辑代码抽取出来单独写成一个函数，但并不影响add添加节点的操作（可以思索一下o）。多项式除以单项式：展开相除再合并（相加）的过程。

        废话不多说，直接上代码了：

#include<bits/stdc++.h>
using namespace std;
struct node{int a;int exp;node *next;
};
typedef node* List;
//初始化
void init(List &list){list=(List)malloc(sizeof(node));list->next=NULL;
}
//添加节点并实现加法操作
void add(List &list,int a,int e){if(a==0)return;//系数为0的直接退出，不加进链表node*p=list;//p表示插入位置的前一个节点，代码更简洁while(p->next!=NULL&&p->next->exp>e)p=p->next;if(p->next!=NULL&&p->next->exp==e)p->next->a+=a;else{node* t=(List)malloc(sizeof(node));t->a=a;t->exp=e;t->next=p->next;p->next=t;}
}
//相乘
List multi(List &li1,List &li2){node*p=li1->next,*q;List l;init(l);
//这里两重循环while(p!=NULL){q=li2->next;//内循环结束后更新q的指向while(q!=NULL){add(l,p->a*q->a,p->exp+q->exp);q=q->next;}p=p->next;}return l;
}
//遍历输出
void show(List &list){node* p=list->next;if(p==NULL)cout<<"0 0";while(p!=NULL){cout<<p->a<<' '<<p->exp<<' ';p=p->next;}
}
int main(){int n;cin>>n;int a,e;List li1,li2;init(li1);init(li2);for(int i=0;i<n;i++){cin>>a>>e;add(li1,a,e);}cin>>n;for(int i=0;i<n;i++){cin>>a>>e;add(li2,a,e);}List l=multi(li1,li2);show(l);return 0;
}

写在最后：

        文笔有限，表述得不清楚的地方也请多多包涵。若有不懂的地方，或者有更好的方法，欢迎大家与我分享交流！！！