一元多项式的乘法与加法运算

glm233

发布于 2022-06-15 19:09:35

7390

发布于 2022-06-15 19:09:35

一道看似很水其实大有文章对初学数据结构的同学大有裨益的好题 题源：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;
 }
 最后附上测试数据：