coefficient、exponent
链表写法（太正了））用数组下标映射指数，用指数映射系数（可以加个常数映射，解决指数为负的情况用map容器，用指数映射系数（指数可以为负）coefficient、exponent
链表写法（太正了））用数组下标映射指数，用指数映射系数（可以加个常数映射，解决指数为负的情况用map容器，用指数映射系数（指数可以为负） 下标为负数，为下标加个常数映射链表写法（太正了））
再也不想用链表了，这么长，老是要用打印语句去纠错，还wa了TT
//#include<iostream>//#include<stdio.h>//#include <stdlib.h>//#include <math.h>//#include<algorithm>//#include <bits/stdc++.h>//----------------不许写万能头#include <iostream>#include <stdlib.h>using namespace std;struct node{int coefficient;//系数 int exponent;//指数 node*next;node(int x,int y,node*p):coefficient(x),exponent(y),next(p){};};typedef struct node node;typedef node* Linklist;//struct node才是节点类型 结构体内部可以用node代替 外面必须要用struct node//除非用typedef struct node{}node;声明了（单独或定义结构体时声明都可 Linklist create(){Linklist L=(Linklist)malloc(sizeof(node)*1);L->next=NULL;//设置一个空头节点 Linklist rear=L;int coef;int expon;int n;//节点个数cin>>n;while(n--){cin>>coef>>expon;//创建一个新的节点添加进去,newnode是指向新节点的指针 Linklist newnode=(node*)malloc(sizeof(node));newnode->coefficient=coef;newnode->exponent=expon;newnode->next=NULL;rear->next=newnode;rear=newnode;} node*t=L;L=L->next;free(t);//释放掉方便创建链表的头节点(避免分别讨论插入节点位置 return L; //结构体自定义数据类型的数组是只创造节点，不涉及指针//这时候在结构体内部定义构造方式就相当nice }void attach(int coef,int expon,Linklist*prear){Linklist p=(node*)malloc(sizeof(node));p->coefficient=coef;p->exponent=expon;p->next=NULL;(*prear)->next=p;//一定要打括号啦 *prear=p;}Linklist Add(Linklist L1,Linklist L2){Linklist L=(node*)malloc(sizeof(node));L->next=NULL;Linklist p=L;//指向被插入节点 Linklist p1=L1;Linklist p2=L2;//分别指向头节点准备遍历while(p1&&p2){if(p1->exponent==p2->exponent){//Linklist newnode=(node*)malloc(sizeof(node));//newnode->coefficient=p1->coefficient+p2->coefficient;//newnode->exponent=p1->exponent;//newnode->next=NULL;//p1=p1->next; p2=p2->next;//p->next=newnode;//p=newnode;attach(p1->coefficient+p2->coefficient,p1->exponent,&p);p1=p1->next; p2=p2->next;}else if(p1->exponent>p2->exponent){//Linklist newnode=(node*)malloc(sizeof(node));//newnode->coefficient=p1->coefficient;//newnode->exponent=p1->exponent;//newnode->next=NULL;//p1=p1->next; //p->next=newnode;//p=newnode;attach(p1->coefficient,p1->exponent,&p);p1=p1->next; }else {//Linklist newnode=(node*)malloc(sizeof(node));//newnode->coefficient=p2->coefficient;//newnode->exponent=p2->exponent;//newnode->next=NULL;// p2=p2->next;// p->next=newnode;// p=newnode;attach(p2->coefficient,p2->exponent,&p);p2=p2->next;}} while(p1){//p->next=p1;attach(p1->coefficient,p1->exponent,&p);p1=p1->next;}while(p2){//p->next=p2;attach(p2->coefficient,p2->exponent,&p);p2=p2->next;}Linklist t=L;L=L->next;free(t);return L;}Linklist Mult(Linklist L1,Linklist L2){if(!L1||!L2)return NULL; //先用L1第一项乘L2得到一个多项式 继续乘并将得到的项插入先得好的多项式 Linklist L=(node*)malloc(sizeof(node));L->next=NULL;Linklist p=L;//指向被插入节点 Linklist p1=L1;Linklist p2=L2;//分别指向头节点准备遍历while(p2){attach(p1->coefficient*p2->coefficient,p1->exponent+p2->exponent,&p);//要插到p指针后面，p指针是要要改变指向的值并移动位置 &p p2=p2->next;} //得到第一个多项式，后续得到的插入这里就好了p1=p1->next;while(p1){p2=L2;p=L;//指向第一个准备好的多项式的(空)头节点while(p2) {//得到的项的插入或合并项 过程 int coef=p1->coefficient * p2->coefficient;int expon=p1->exponent + p2->exponent;while(p->next&&p->next->exponent>expon){p=p->next;}//返回的指针指向最后一个指数大于该项的项 //因为插入要在找到的节点后面，所有判断的是p->next 5 8 6 4 if(p->next&&p->next->exponent==expon){//合并项 if(p->next->coefficient+coef){p->next->coefficient+=coef;}else{//指数相等，系数相加为0 Linklist t=p->next;p->next=t->next;free(t);}} else{//该项是要插入的新指数项 ，attach只适合尾插 Linklist newnode=(node*)malloc(sizeof(node));newnode->coefficient=coef;newnode->exponent=expon;newnode->next=p->next;p->next=newnode; p=p->next; }//对于这一项的处理结束啦 p2=p2->next;}p1=p1->next;}Linklist t=L;L=L->next;free(t);return L;}void print(Linklist L){Linklist p=L;int flag=1;while(p){if(p->coefficient){flag=0;break;}p=p->next;}if(!p||flag){cout<<"0 0";return;}flag=1;while(p){if(flag)flag=0;//第一次前面不输出空格 else cout<<" ";cout<<p->coefficient<<" "<<p->exponent;p=p->next;}}int main(){ios::sync_with_stdio(false);cin.tie(0);Linklist L1,L2,lm,la;L1=create();L2=create();//print(L1); //print(L2);lm=Mult(L1,L2);la=Add(L1,L2);print(lm);cout<<endl;print(la);return 0;}
避免了零多项式又过了一个点
Linklist p=L;int flag=1;while(p){if(p->coefficient){flag=0;break;}p=p->next;}if(!p||flag){cout<<"0 0";return;}flag=1;
用数组下标映射指数，用指数映射系数（可以加个常数映射，解决指数为负的情况
//#include<iostream>//#include<stdio.h>//#include <stdlib.h>//#include <math.h>//#include<algorithm>//#include <bits/stdc++.h>//----------------不许写万能头#include <iostream>#include <stdlib.h>using namespace std;int mult[2002];//指数绝对值不超过1000,相乘不会超过2000 int add[2001];int p1[2002];int p2[2002]; int main(){ios::sync_with_stdio(false);cin.tie(0);//用数组下标映射指数，用指数映射系数int m,n;cin>>m;int c,e;while(m--){cin>>c>>e;p1[e]=c;add[e]+=c;} cin>>n;while(n--){cin>>c>>e;p2[e]=c;add[e]+=c;}for(int i=0;i<2002;i++){if(p1[i])for(int j=0;j<2002;j++){if(p2[j])mult[i+j]+=p1[i]*p2[j];}}int f1=1;int f2=1;//判别是否是全0系数多项式 for(int i=0;i<2002;i++){if(add[i])f1=0;if(mult[i])f2=0;} if(f2)cout<<"0 0";else{int cnt=0;for(int i=2002;i>=0;i--){if(mult[i]){if(!cnt)cout<<mult[i]<<" "<<i;else cout<<" "<<mult[i]<<" "<<i;cnt++;}}}cout<<endl;if(f1)cout<<"0 0";else{int cnt=0;for(int i=2002;i>=0;i--){if(add[i]){if(!cnt)cout<<add[i]<<" "<<i;else cout<<" "<<add[i]<<" "<<i;cnt++;}}}return 0;}
用map容器，用指数映射系数（指数可以为负）
//#include<iostream>//#include<stdio.h>//#include <stdlib.h>//#include <math.h>//#include<algorithm>//#include <bits/stdc++.h>//----------------不许写万能头#include <iostream>#include <map>using namespace std;map<int,int> mp1,mp2,mult,add;int main(){ios::sync_with_stdio(false);cin.tie(0);//用map容器，用指数映射系数int m,n;cin>>m;int coef;int expon;while(m--){cin>>coef>>expon;mp1[expon]=coef;add[expon]+=coef;}cin>>n;while(n--){cin>>coef>>expon;mp2[expon]=coef;add[expon]+=coef;} for(int i=-1e3-5;i<1e3+5;i++){if(mp1[i]){for(int j=-1e3-5;j<1e3+5;j++){if(mp2[j]){//mult[mp1[i]+mp2[j]]=i*j;mult[i+j]=mp1[i]*mp2[j];}}}}int f1=1;int f2=1;for(int i=2e3+5;i>=-2e3-5;i--){if(mult[i])f1=0;if(add[i])f2=0;}int flag=1;if(f1)cout<<"0 0";else{for(int i=2e3+5;i>=-2e3-5;i--){if(mult[i]){if(flag){cout<<mult[i]<<" "<<i;flag=0;}else cout<<" "<<mult[i]<<" "<<i;}}}cout<<endl;flag=1;if(f2)cout<<"0 0";else{for(int i=2e3+5;i>=-2e3-5;i--){if(add[i]){if(flag){cout<<add[i]<<" "<<i;flag=0;}else cout<<" "<<add[i]<<" "<<i;}}}return 0;}
