7-1 一元多项式的乘法与加法运算 （20 分)
设计函数分别求两个一元多项式的乘积与和。
输入格式:
输入分2行，每行分别先给出多项式非零项的个数，再以指数递降方式输入一个多项式非零项系数和指数（绝对值均为不超过1000的整数）。数字间以空格分隔。
输出格式:
输出分2行，分别以指数递降方式输出乘积多项式以及和多项式非零项的系数和指数。数字间以空格分隔，但结尾不能有多余空格。零多项式应输出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
5 20 -4 4 -5 2 9 1 -2 0
这个题我用三种方法写的
第一种链表最后一个测试点没通过，第二种c++数组通过了全部的测试点；
第三种用c语言写的，也通过了全部的测试点
第一种用链表写的，但最后一个从测试点过不去；
#include<stdio.h>
#include<stdlib.h>
struct node
{
long int a,b;//a储存系数，b储存指数；
struct node *next;
};
struct node *creat(int n)
{
int i,num,g;
struct node *ptr=NULL,*head=NULL,*tail=NULL;
for(i=0;i<n;i++)
{
scanf("%d %d",&num,&g);
ptr=(struct node *)malloc(sizeof(struct node));
ptr->a=num;
ptr->b=g;
ptr->next=NULL;
if(head==NULL) head=ptr;
else tail->next=ptr;
tail=ptr;
}
return head;
}
struct node *chengfa(struct node *head1,struct node *head2)
{
int temp;
struct node *ptr=NULL,*head=NULL,*tail=NULL,*ptr1=NULL,*ptr2=NULL;
//两个链表相乘；得到一个新的链表；
for(ptr1=head1;ptr1!=NULL;ptr1=ptr1->next)
{
for(ptr2=head2;ptr2!=NULL;ptr2=ptr2->next)
{
ptr=(struct node *)malloc(sizeof(struct node));
ptr->a=(ptr1->a)*(ptr2->a);
ptr->b=(ptr1->b)+(ptr2->b);
ptr->next=NULL;
if(head==NULL) head=ptr;
else tail->next=ptr;
tail=ptr;
}
}
//对于指数相同的项，系数相加；
//同类项合并；
for(ptr1=head;ptr1!=NULL;ptr1=ptr1->next)
{
for(ptr2=ptr1->next,tail=ptr1;ptr2!=NULL;)
{
if(ptr1->b==ptr2->b)
{
ptr1->a=ptr1->a+ptr2->a;
tail->next=ptr2->next;
free(ptr2);
ptr2=tail->next;
}
else
{
tail=ptr2;
ptr2=ptr2->next;
}
}
}
//用选择排序法；
for(ptr1=head;ptr1->next!=NULL;ptr1=ptr1->next)
{
for(ptr2=ptr1->next;ptr2!=NULL;ptr2=ptr2->next)
{
if(ptr1->b<ptr2->b)
{
temp=ptr1->b;
ptr1->b=ptr2->b;
ptr2->b=temp;
temp=ptr1->a;
ptr1->a=ptr2->a;
ptr2->a=temp;
}
}
}
for(ptr=head;ptr!=NULL;)
{
if(ptr->a==0)
{
if(ptr==head)
{
head=head->next;
free(ptr);
ptr=head;
}
else
{
ptr1->next=ptr->next;
free(ptr);
ptr=ptr1->next;
}
}
else
{
ptr1=ptr;
ptr=ptr->next;
}
}
return head;
}
struct node *add(struct node *head1,struct node *head2)
{
int temp;
struct node *ptr1=NULL,*ptr2=NULL,*head=NULL,*tail=NULL,*ptr=NULL;
//把两个单链表合并成一个链表；
for(ptr=head1;ptr!=NULL;ptr=ptr->next)
{
ptr1=(struct node *)malloc(sizeof(struct node));
ptr1->a=ptr->a;
ptr1->b=ptr->b;
ptr1->next=NULL;
if(head==NULL) head=ptr1;
else tail->next=ptr1;
tail=ptr1;
}
for(ptr=head2;ptr!=NULL;ptr=ptr->next)
{
ptr1=(struct node *)malloc(sizeof(struct node));
ptr1->a=ptr->a;
ptr1->b=ptr->b;
ptr1->next=NULL;
if(head==NULL) head=ptr1;
else tail->next=ptr1;
tail=ptr1;
}
//将结点中指数相同的项合并;
//同类项合并;
for(ptr=head;ptr!=NULL;ptr=ptr->next)
{
for(ptr1=ptr->next,tail=ptr;ptr1!=NULL;)
{
if(ptr->b==ptr1->b)
{
//指数相同，系数相加；
ptr->a=ptr->a+ptr1->a;
tail->next=ptr1->next;
free(ptr1);
ptr1=tail->next;
}
else
{
tail=ptr1;
ptr1=ptr1->next;
}
}
}
//对链表进行选择排序；
for(ptr1=head;ptr1->next!=NULL;ptr1=ptr1->next)
{
for(ptr2=ptr1->next;ptr2!=NULL;ptr2=ptr2->next)
{
if(ptr1->b<ptr2->b)
{
temp=ptr2->b;
ptr2->b=ptr1->b;
ptr1->b=temp;
temp=ptr2->a;
ptr2->a=ptr1->a;
ptr1->a=temp;
}
}
}
for(ptr=head;ptr!=NULL;)
{
if(ptr->a==0)
{
if(ptr==head)
{
head=head->next;
free(ptr);
ptr=head;
}
else
{
ptr1->next=ptr->next;
free(ptr);
ptr=ptr1->next;
}
}
else
{
ptr1=ptr;
ptr=ptr->next;
}
}
return head;
}
int main()
{
int n;
struct node *ptr=NULL,*head=NULL,*tail=NULL,*head1=NULL,*head2=NULL;
scanf("%d",&n);
head1=creat(n);
scanf("%d",&n);
head2=creat(n);
head=chengfa(head1,head2);
if(head!=NULL)
{
for(ptr=head;ptr!=NULL;ptr=ptr->next)
{
printf("%d %d",ptr->a,ptr->b);
if(ptr->next!=NULL) printf(" ");
}
}
else printf("0 0");
printf("\n");
head=add(head1,head2);//加法运算；
if(head!=NULL)
{
for(ptr=head;ptr!=NULL;ptr=ptr->next)
{
printf("%d %d",ptr->a,ptr->b);
if(ptr->next!=NULL) printf(" ");
}
}
else printf("0 0\n");
return 0;
}
第二种是用数组写的，通过了全部的测试点；
/*此题的数组长度应比2000大；
在乘法运算时1000+1000=2000；
指数相加的最大值是2000；
故数组的长度一定要比2000；
*/
#include<iostream>
using namespace std;
int main()
{
//指数相加的最大值为2000；
int j,h[10000]={0},h1[10000]={0},m1[10000]={0},m[10000]={0},k=0,k1=0,t1[2000]={0},t[2000]={0};
int n,m3,a[10000]={0},a1[10000]={0},b[10000]={0},b1[10000]={0},c[10000]={0},c1[10000]={0},d[10000]={0},d1[2000]={0},i;
cin>>n;
for(i=0;i<n;i++)
{
cin>>a[i]>>a1[i];
d[a1[i]]=d[a1[i]]+a[i];
}
cin>>m3;
for(i=0;i<m3;i++)
{
cin>>b[i]>>b1[i];
d[b1[i]]=d[b1[i]]+b[i];
}
k=0;
for(i=0;i<n;i++)
{
for(j=0;j<m3;j++)//不可以此处写k++；
{
c[k]=a[i]*b[j];
c1[k]=a1[i]+b1[j];//多项式相乘，系数相乘，指数相加；
h[c1[k]]=h[c1[k]]+c[k];
k++;//易错点：否则当j取到m3时跳出循环；
//就不再执行k++;就少算了；
}
}
k1=0;
for(i=2000;i>=0;i--)//乘法运算；
{
if(h[i]!=0)
{
m[k1]=h[i];//m数组用来储存乘法运算结果的系数；
m1[k1]=i;//m1来储存乘法运算结果后的指数；
k1++;
}
}
for(i=0;i<k1;i++)
{
cout<<m[i]<<" "<<m1[i];
if(i<k1-1) cout<<" ";
}
if(k1==0)
{
cout<<"0 0";//输出零多项式；
}
cout<<endl;
k=0;
for(i=2000;i>=0;i--)
{
if(d[i]!=0)
{
t[k]=d[i];
t1[k]=i;
k++;
}
}
for(i=0;i<k;i++)
{
cout<<t[i]<<" "<<t1[i];
if(i<k-1) cout<<" ";
}
if(k==0) cout<<"0 0";//有零多项式；
return 0;
}
下面的是用c语言写的；
/*此题的数组长度应比2000大；
在乘法运算时1000+1000=2000；
指数相加的最大值是2000；
故数组的长度一定要比2000；
*/
#include<stdio.h>
int main()
{
//指数相加的最大值为2000；
int j,h[10000]={0},h1[10000]={0},m1[10000]={0},m[10000]={0},k=0,k1=0,t1[2000]={0},t[2000]={0};
int n,m3,a[10000]={0},a1[10000]={0},b[10000]={0},b1[10000]={0},c[10000]={0},c1[10000]={0},d[10000]={0},d1[2000]={0},i;
scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d %d",&a[i],&a1[i]);
d[a1[i]]=d[a1[i]]+a[i];
}
scanf("%d",&m3);
for(i=0;i<m3;i++)
{
scanf("%d %d",&b[i],&b1[i]);
d[b1[i]]=d[b1[i]]+b[i];
}
k=0;
for(i=0;i<n;i++)
{
for(j=0;j<m3;j++)//不可以此处写k++；
{
c[k]=a[i]*b[j];
c1[k]=a1[i]+b1[j];//多项式相乘，系数相乘，指数相加；
h[c1[k]]=h[c1[k]]+c[k];
k++;//易错点：否则当j取到m3时跳出循环；
//就不再执行k++;就少算了；
}
}
k1=0;
for(i=2000;i>=0;i--)//乘法运算；
{
if(h[i]!=0)
{
m[k1]=h[i];//m数组用来储存乘法运算结果的系数；
m1[k1]=i;//m1来储存乘法运算结果后的指数；
k1++;
}
}
for(i=0;i<k1;i++)
{
printf("%d %d",m[i],m1[i]);
if(i<k1-1) printf(" ");
}
if(k1==0)
{
printf("0 0");//输出零多项式；
}
printf("\n");
k=0;
for(i=2000;i>=0;i--)
{
if(d[i]!=0)
{
t[k]=d[i];
t1[k]=i;
k++;
}
}
for(i=0;i<k;i++)## 标题
{
printf("%d %d",t[i],t1[i]);
if(i<k-1) printf(" ");
}
if(k==0) printf("0 0");//有零多项式；
return 0;
}