链表实现一元多项式相乘

Question

【问题描述】
编写一个程序实现两个一元多项式相乘。
【输入形式】
首先输入第一个多项式中系数不为0的项的系数和指数，以一个空格分隔。且该多项式中各项的系数均为0或正整数，系数和最高幂次不会超过int类型的表示范围。对于多项式 anxn +a n-1 x n-1 + … + a1x1 + a0x0 的输入方法如下：
an n a n-1 n-1 … a1 1 a0 0
即相邻两个整数分别表示表达式中一项的系数和指数。在输入中只出现系数不为0的项。最后一项的指数后没有空格，只有一个回车换行符。
按照上述方式再输入第二个多项式。
【输出形式】
将运算结果输出到屏幕。将系数不为0的项按指数从高到低的顺序输出，每次输出其系数和指数，均以一个空格分隔，最后一项的指数后也可以有一个空格。
【样例输入】
10 80000 2 6000 7 300 5 10 18 0
3 6000 5 20 8 10 6 0
【样例输出】
30 86000 50 80020 80 80010 60 80000 6 12000 21 6300 10 6020 31 6010 66 6000 35 320 56 310 42 300 25 30 130 20 174 10 108 0
【样例说明】
输入的两行分别代表如下表达式：
10x80000 + 2x6000 + 7x300 + 5x10 + 18
3x6000 + 5x20 + 8x10 + 6
相乘结果为：
30x86000 + 50x80020 + 80x80010 + 60x80000 + 6x12000 + 21x6300 + 10x6020 + 31x6010 + 66x6000 + 35x320 + 56x310 + 42x300 + 25x30 + 130x20 + 174x10 + 108
提示：利用链表存储多项式的系数和指数。
【评分标准】
该题要求输出相乘后多项式中系数不为0的系数和指数，共有5个测试点。
【编程语言】
C/C++

Answer 1

yright © 1999-2020, CSDN.NET, All Rights Reserved



Matlab精品一篇就够
  
1

暗中观察|.･｀)
关注
BUAA(2021春)多项式相乘 原创
2021-04-29 17:24:14
 2点赞

暗中观察|.･｀)  

码龄1年

关注
BUAA数据结构第三次编程题——多项式相乘
看前须知
第三次上机题汇总
题目内容
问题描述
输入形式
输出形式
样例
样例说明
题解
易错点和难点
参考代码
补充测试的数据
看前须知
要点介绍和简要声明.

第三次上机题汇总
连续线段——结构体多级排序.

猴子选大王(约瑟夫问题)+3种解决约瑟夫问题的方法.

多项式相乘.

文件加密（环）——要求循环链表熟练的删除操作.

词频统计（数组或链表实现）.

题目内容
问题描述
编写一个程序实现两个一元多项式相乘。

输入形式
首先输入第一个多项式中系数不为0的项的系数和指数，以一个空格分隔。且该多项式中各项的指数均为0或正整数，系数和最高幂次不会超过int类型的表示范围。对于多项式 anxn +a n-1 x n-1+…+ a1x1+ a0x0 的输入方法如下：
an n a n-1 n-1 … a1 1 a0 0
即相邻两个整数分别表示表达式中一项的系数和指数。在输入中只出现系数不为0的项。最后一项的指数后没有空格，只有一个回车换行符。
按照上述方式再输入第二个多项式。

输出形式
将运算结果输出到屏幕。将系数不为0的项按指数从高到低的顺序输出，每次输出其系数和指数，均以一个空格分隔，最后一项的指数后也可以有一个空格。

样例
【样例输入】

10 80000 2 6000 7 300 5 10 18 0
3 6000 5 20 8 10 6 0
1
2
1
2
【样例输出】

30 86000 50 80020 80 80010 60 80000 6 12000 21 6300 10 6020 31 6010 66 6000 35 320 56 310 42 300 25 30 130 20 174 10 108 0
1
1
样例说明
输入的两行分别代表如下表达式：
10x80000+ 2x6000 + 7x300 + 5x10 + 18
3x6000 + 5x20 + 8x10 + 6
相乘结果为：
30x86000 + 50x80020 + 80x80010 + 60x80000 + 6x12000 + 21x6300 + 10x6020 + 31x6010 + 66x6000+ 35x320 + 56x310 + 42x300 + 25x30 + 130x20 + 174x10 + 108

题解
易错点和难点
本题不难，主要一个是读入，一个是计算。

对于读入，我们需要用do while来进行读入，在读入的过程中，顺便记录多项式的项数。

对于计算，有一个需要注意的一点，就是可能会出现很多的指数相同的项，所以我们计算（系数相乘，指数相加）完后，我们需要进行去重操作。但是此处有技巧，如果有指数相同的项，我们只需要保留第一项即可，如果不是，可能会造成不必要的麻烦。

参考代码
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<ctype.h>
struct expression{            //多项式结构体 
    int coe;                //系数 
    int pow;                //指数 
};
typedef struct expression ex;
ex a[2000],b[2000],c[2000];//a是第一个多项式，b是第二个多项式 ,c是最后相乘的多项式 
int cmp(const void*p1,const void*p2);
int main()
{    
    int i,j,k=0;
    int n=0,nn=0;//n是第一个多项式的项数 ，nn是第二个多项式的项数  
    char ch;
    do   //读入第一个多项式 
    {
        scanf("%d%d%c",&a[n].coe,&a[n].pow,&ch);
        n++;
    }while(ch!='\n');
    do    //读入第二个多项式
    {
        scanf("%d%d%c",&b[nn].coe,&b[nn].pow,&ch);
        nn++;
    }while(ch!='\n');
    qsort(a,n,sizeof(ex),cmp); //按指数排序 
    qsort(b,nn,sizeof(ex),cmp);    //按指数排序 
    for(i=0;i<n;i++)
    {
        for(j=0;j<nn;j++)
        {
            c[k].coe=a[i].coe*b[j].coe;//系数相乘 
            c[k].pow=a[i].pow+b[j].pow;//指数相加 
            k++;
        }
    }
    qsort(c,k,sizeof(ex),cmp);//根据指数排序 
    for(i=0;i<k;i++)
    {
        if(c[i].pow == c[i+1].pow && c[i].pow!=0)//指数一样的进行去重操作 
        {
            c[i+1].coe+=c[i].coe;//指数一样的进行去重操作 
            c[i].coe=0;//去重项系数设为零 
        }
    }
    qsort(c,k,sizeof(ex),cmp);//根据指数排序 
    for(i=0;i<k;i++)
    {
        if(c[i].coe==0)//去重项不输出 
        {
            continue;
        }
        else
        {
            printf("%d %d ",c[i].coe,c[i].pow);//输出 
        }
    }
    return 0;
}
int cmp(const void*p1,const void*p2)
{
    struct expression *a=(struct expression*)p1;
    struct expression *b=(struct expression*)p2;
    return b->pow-a->pow;
}