一元多项式的乘法与加法运算
一道看似很水其实大有文章
对初学数据结构的同学大有裨益的好题
题源：pta数据结构自测第二题
题目描述
7-2 一元多项式的乘法与加法运算 （20 分）
设计函数分别求两个一元多项式的乘积与和。
输入格式:
输入分2行，每行分别先给出多项式非零项的个数，再以指数递降方式输入一个多项式非零项系数和指数（绝对值均为不超过1000的整数）。数字间以空格分隔。
输出格式:
输出分2行，分别以指数递降方式输出乘积多项式以及和多项式非零项的系数和指数。数字间以空格分隔，但结尾不能有多余空格。零多项式应输出0 0。
给出两种做法
(题目不难，坑点很多)正常做一开始只能过25%的数据
法一：常规思路用数组
乘法： a1 x^m * a2 x^n = (a1*a2) x^(m+n) (m>=0,n>=0)
加法： a1 x^n + a2 x^n = (a1+a2) x^n (n>=0)
a[i][0]表示存放第i项的系数，a[i][1]表示存放第i项的指数
不解释看代码自然懂
#include<bits/stdc++.h>
using namespace std;
int a[1005][2],b[1005][2],c[3005];
int n,m;
void mutiply()//乘法部分
{
int maxx=-1,flag=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
c[a[i][1]+b[j][1]]+=a[i][0]*b[j][0];
maxx=max(a[i][1]+b[j][1],maxx);
}
}
for(int i=maxx;i>=0;i--)
{
if(i==maxx&&c[i])
{
printf("%d %d",c[i],i);
flag=1;
}
else if(c[i])
{
printf(" %d %d",c[i],i);
flag=1;
}
}
if(!flag)
{
printf("0 0");
}
printf("%c",10);
}
void pluss()//加法部分
{
int maxx=-1,flag=0;
for(int i=1;i<=n;i++)
{
c[a[i][1]]+=a[i][0];
maxx=max(a[i][1],maxx);
}
for(int i=1;i<=m;i++)
{
c[b[i][1]]+=b[i][0];
maxx=max(b[i][1],maxx);
}
for(int i=maxx;i>=0;i--)
{
if(i==maxx&&c[i])
{
printf("%d %d",c[i],i);
flag=1;
}
else if(c[i])
{
printf(" %d %d",c[i],i);
flag=1;
}
}
if(!flag)
{
printf("0 0");
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d %d",&a[i][0],&a[i][1]); //a[i][0]表示存放第i项的系数，a[i][1]表示存放第i项的指数
}
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
scanf("%d %d",&b[i][0],&b[i][1]);
}
mutiply();
memset(c,0,sizeof(c));
pluss();
return 0;
}法二 两个有序表的读入，删除，合并 代码会较数组复杂很多 但基本思想不变 我在做的时候遇到了很多平时难以见到的情况 被这卡那卡的很是难受 说一下从0分到14分、16分、18分，最后ac的历程 首先建立大框架 1.读入输出(read，print函数） 2.核心处理(加法，乘法） { 加法 按指数大小排序， 大的优先读入新链表 然后后移继续比较 如果相等 看系数coef { 如果a->coef+b->coef=0两个链表指针后移 } 否则新结点的系数为a->coef+b->coef 指数与两结点指数相同 } 乘法 任选一张链表 对每一个元素进行Mutiply操作 Mutiply意为： 例如目前要处理的链表有a,b我每次通过控制b结点指针移动让b链表里每一个元素与a链表每个元素进行相乘操作 对新链表c结点有： c->coef=a->coef*b->coef; c->expon=a->expon+b->expon; 那我就来边回顾代码边写注释吧
#include<bits/stdc++.h>
using namespace std;
typedef struct node* List;
struct node//定义结构体，coef为系数，expon为指数
{
int coef;
int expon;
List next;
};
List read()//读入函数
{
int n;
List rear=new struct node;
List head=new struct node;
rear->next=NULL;
head=rear;
scanf("%d",&n);
while(n--)
{
List setin=new struct node;
scanf("%d%d",&(setin->coef),&(setin->expon));
setin->next=NULL;
rear->next=setin;
rear=setin;//rear为尾部指针
}
return head;
}
void print(List L)//输出带头结点的链表
{
List p = L->next;
if (!p)
{
printf("0 0\n");
}
else
{
while (p)
{
if (p->next != NULL)//第一个头结点的输出格式细节
{
printf("%d %d ", p->coef, p->expon);
}
else
{
printf("%d %d\n", p->coef, p->expon);
}
p = p->next;
}
}
}
List pluss(List a,List b)//加法运算
{
List L,head,a1,b1;
L=new struct node;
L->next=NULL;
head=L;
a1=a->next;
b1=b->next;
if(!a1)//这里是一个玄学点，对于第四个测试数据，如果在pluss函数最后没加这段过不了，个人认为只要前面有就行了，这个作用是判断空链表直接将新链表的接在另一个非空链表
{
L->next=b1;
return head;
}
if(!b1)
{
L->next=a1;
return head;
}
while(a1&&b1)
{
if(a1->expon>b1->expon)
{
List temp=new struct node;
temp->coef=a1->coef;//在这里我只前曾经的代码是temp=a1;temp->next=null;但是这样会计算错误，也不懂为什么，不过现在的这种写法最稳，肯定错不了
temp->expon=a1->expon;
// cout<<temp->coef<<" "<<temp->expon<<endl;
temp->next=NULL;
L->next=temp;
L=temp;
a1=a1->next;
}
else if(a1->expon<b1->expon)
{
List temp=new struct node;
temp->coef=b1->coef;
temp->expon=b1->expon;
//cout<<temp->coef<<" "<<temp->expon<<endl;
temp->next=NULL;
L->next=temp;
L=temp;
b1=b1->next;
}
else if(a1->expon==b1->expon)
{
if(a1->coef+b1->coef==0)
{
a1=a1->next;
b1=b1->next;
}
else
{
List temp=new struct node;
temp->expon=a1->expon;
temp->coef=a1->coef+b1->coef;
temp->next=NULL;
L->next=temp;
L=temp;
a1=a1->next;
b1=b1->next;
}
}
}
if(!a1)
{
L->next=b1;
return head;
}
if(!b1)
{
L->next=a1;
return head;
}
return head;
}
List Mutiply(List a,struct node b)
{
List L,head;
L=new struct node;
L->next=NULL;
head=L;
while(a)
{
List temp=new struct node;
temp->coef=a->coef*b.coef;
temp->expon=a->expon+b.expon;
temp->next=NULL;
L->next=temp;
L=temp;
a=a->next;
}
return head;
}
List mutiply(List a,List b)
{
List L,head;
L=new struct node;
L->next=NULL;
head=L;
a=a->next;
b=b->next;
if(a&&b)
{
List temp=Mutiply(a,*b);
b=b->next;
while(b)
{
List temp1=Mutiply(a,*b);
temp=pluss(temp,temp1);
b=b->next;
}
L->next=temp->next;
}
return head;
}
int main()
{ List a,b,c,d;
a=read();
b=read();
c=pluss(a,b);
d=mutiply(a,b);
print(d);
print(c);
return 0;
}
最后附上测试数据：
总的来说，做出这题，用数组法很简单，但是要用数据结构的知识做不简单，要考虑很多细节，坑点，找出bug的过程总是那么艰辛，那么漫长，但是最后解决的时候确实那么美好。