多项式的表示

例:一元多项式:f(x)=a0+a1x++an1xn1+anxnf(x)=a_0+a_1x+…+a_{n-1}x^{n-1}+a_nx^n

主要运算:多项式相加、相减、相乘等

如何表示多项式?

多项式的关键数据:

  • 多项式项数n
  • 各项系数ai及指数i

多项式问题的启示:

  • 解决同一个问题可以有不同的表示(存储)方法
  • 有一类共性问题:有序线性序列的组织和管理

一元多项式表示方法

如:多项式x+3x2000x+3x^{2000}的表示

  • 顺序存储结构直接表示:容易造成空间的浪费
  • 更好的方法是:数组各分量对应多项式各项,即a[i]表示项xix^i的系数aia_i

方法1: 顺序存储结构各分量对应多项式各项

例如:f(x)=4x53x2+1f(x)=4x^5-3x^2+1
表示成:

下标i 0 1 2 3 4 5
a[i] 1 0 -3 0 0 4
1 0 3x2-3x^2 0 0 4x54x^5

两个多项式相加的方法:两个数组对应分量相加
这种方法仍存在缺陷:以x+3x2000x+3x^{2000}为例
需要分配一个长度为2001(指数从0开始)的数组,并且其中只有两个非0项,在做加法运算时需要遍历整个数组,而+0实际上是在做无用功

方法2: 用顺序存储结构表示非零项

每个非零项aixia_ix^i涉及两个信息:系数aiai和指数ii,可将一个多项式看成一个(ai,i)(a_i,i)二元组的集合
用结构数组表示:数组分量是由系数aiai、指数ii组成的结构,对应一个非零项
按非零项的指数大小有序存储

例:P1(x)=9x12+15x8+3x2P_1(x)=9x^{12}+15x^8+3x^2P2(x)=26x194x813x6+82P_2(x)=26x^{19}-4x^8-13x^6+82

下标i 0 1 2
系数aiai 9 15 3
指数ii 12 8 2
下标j 0 1 2 3
系数ajaj 26 -4 -13 82
指数jj 19 8 6 0

相加过程:从头开始,比较两个多项式当前对应项的指数

例:P1:(9,12),(15,8),(3,2)           +
   P2:(26,19),(-4,8),(-13,6),(82,0) ->
   P3(26,19),(9,12),(11,8),(-13,6),(3,2),(82,0)

结果:P3(x)=26x19+9x12+11x813x6+3x2+82P_3(x)=26x^{19}+9x^{12}+11x^8-13x^6+3x^2+82

方法3: 链表结构存储非零项

链表中每个结点存储多项式中的一个非零项,包括系数和指数两个数据域以及一个指针域:coef,expon,link

例:P1(x)=9x12+15x8+3x2P1(x)=9x^{12}+15x^8+3x^2P2(x)=26x194x813x6+82P2(x)=26x^{19}-4x^8-13x^6+82

多项式链表结点的定义:        
typedef struct PolyNode *Polynomial;  
struct PolyNode
{
    int coef;
    int expon;
    Polynomial link;
};

多项式加法运算

多项式加法运算:不带头结点的单向链表,按照指数递减的顺序排列各项

struct PolyNode
{
    int coef,expon;
    struct PolyNode *link;
};
typedef struct PolyNode *Polynomial;
Polynomial P1,P2;

思路:两个指针P1和P2分别指向两个多项式的第一个结点,不断循环:

  • P1->expon==P2->expon:系数相加,若结果不为0,则作为结果多项式对应项的系数。同时,P1和P2都分别指向下一项;
  • P1->expon>P2->expon:将P1的当前项存入结果多项式,并使P1指向下一项
  • P1->expon <P2->expon:将P2的当前项存入结果多项式,并使P2指向下一项
  • 当某一多项式处理完时,将另一个多项式的所有结点依次复制到结果多项式中(实质上是一种归并排序)

二元多项式的表示:广义表存储

例:给定二元多项式 P(x,y)=9x12y2+4x12+15x8y3x8y+3x2P(x,y)=9x^{12}y^2+4x^{12}+15x^8y^3-x^8y+3x^2

可以将该二元多项式看作关于x的一元多项式

$P(x,y)=(9y2+4)x{12}+(15y3-y)x8+3x^2 (ax{12}+bx8+cx^2)$

广义表(Generalized List):广义表是线性表的推广

  • 对于线性表而言,n个元素都是基本的单元素
  • 但是在广义表中,这些元素不仅可以是单元素也可以是另一个广义表
typedef struct GNode *GList;
struct GNode
{
    int Tag;                                    //Tag表示标志域:0代表结点为单元素,1表示结点是广义表
    union                                       //子表指针域SubList与单元素数据域Data复用,共用存储空间
    {
        ElementType Data;
        GList SubList;
    }URegion;
    GList Next;
};

多项式加法和乘法的实现

问题:设计两个函数分别求两个多项式的乘积与和
已知两个多项式:

  • 3x45x2+6x23x^4-5x^2+6x-2
  • 5x207x4+3x5x^{20}-7x^4+3x
  • 两个多项式和为
    • 5x204x45x2+9x25x^{20}-4x^4-5x^2+9x-2
  • 两个多项式乘积为
    • 15x2425x22+30x2110x2021x8+35x633x5+14x415x3+18x26x15x^{24}-25x^{22}+30x^{21}-10x^{20}-21x^8+35x^6-33x^5+14x^4-15x^3+18x^2-6x
输入样例:
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

求解思路

  • 多项式表示

    • 数组:变成简单、调试容易;需实现分配空间,容易浪费
    • 链表:动态性强;变成略复杂、调试困难
    • 一种比较好的实现方法是动态数组(将数组长度存储为变量)
  • 程序框架

    • 需要设计的函数:
      • 读一个多项式
      • 读两个多项式
      • 两多项式相加
      • 多项式输出
  • 伪代码

int main()
{
    读入多项式1,读入多项式1
    乘法运算并输出
    加法运算并输出
}
读多项式
Polynomial ReadPoly()
{
    Polynomial P,Rear,first;
    int N,c,e;
    P=(List)malloc(sizeof(struct Lnode));
    P->link=NULL;
    Rear=P;
    cin>>N;
    while(N--)
    {
        cin>>c>>e;
        Attach(c,e,&Rear);              //将当前项插入多项式尾部
    }
    first=P;P=P->link;free(first);      //删除临时结点(P原本指向的动态内存)
    return P;
}
4.加法实现:遍历两个链表,各项相加,返回结果即可,略
5.乘法实现:将乘法运算转换为加法运算
    将P1当前项(ci,ei)乘P2多项式,再加到结果多项式里
    t1=P1,t2=P2;
    P=(Polynomial)malloc(sizeof(struct PolyNode));
    P->link=NULL;
    Rear=P;
    while(t2)       //将P2的每一项都与P1当前项相乘
    {
        Attach(t1->coef*t2->coef,t1->expon+t2->expon,&Rear);
        t2=t2->link;
    }
    逐项插入
    将P1当前项(c1i,e1i)乘P2当前项(c2i,e2i),并插入到结果多项式中
    关键是如何找到插入位置
    while(t1)
    {
        t2=P2,Rear=P;
        while(t2)
        {
            e=t1->expon+t2->expon;
            c=t1->coef*t2->coef;
            ……;
            t2=t2->link;
        }
        t1=t1->link;
    }
6.多项式输出:略
演示代码:
#include<cstdlib>
#include<cstdio>
struct PolyNode{
    int coef,expon;
    struct PolyNode *link;
};
typedef struct PolyNode *Polynomial;
int Compare(Polynomial P1,Polynomial P2);
void Attach(int c,int e,Polynomial *prear);
Polynomial PolyAdd(Polynomial P1,Polynomial P2){
    Polynomial front,rear,temp;                     //front用来返回,rear用来添加新的项,输出是从front开始
    front=rear=new PolyNode;
    while(P1&&P2){
        switch (Compare(P1,P2)) {
            case 1:
                Attach(P1->coef,P1->expon,&rear);
                P1=P1->link;
                break;
            case -1:
                Attach(P2->coef,P2->expon,&rear);
                P2=P2->link;
                break;
            case 0:
                int sum=P1->coef+P2->coef;
                if(sum)Attach(sum,P1->expon,&rear);
                P1=P1->link,P2=P2->link;
                break;
        }
    }
    for(;P1;P1=P1->link)Attach(P1->coef,P1->expon,&rear);
    for(;P2;P2=P2->link)Attach(P2->coef,P2->expon,&rear);
    temp=front;
    front=front->link;
    free(temp);
    return front;
}
int Compare(Polynomial P1,Polynomial P2){
    if(P1->expon>P2->expon)return 1;
    if(P1->expon<P2->expon)return -1;
    if(P1->expon==P2->expon)return 0;
    return 0;
}
void Attach(int c,int e,Polynomial * pRear)                //根据Rear初值是否为NULL做不同处理(即构造的链表是否含有头结点)
{                                                          //最开始为空的结点(头结点)在调用结束后再决定是否删除
    Polynomial temp;
    temp=(Polynomial)malloc(sizeof(struct PolyNode));
    temp->coef=c;
    temp->expon=e;
    temp->link=(*pRear)->link;
    (*pRear)->link=temp;
    (*pRear)=temp;
}
Polynomial Mult(Polynomial P1,Polynomial P2)
{
    Polynomial P,Rear,t1,t2,t;
    int c,e;
    if(!P1||!P2)return NULL;
    t1=P1,t2=P2;
    P=(Polynomial)malloc(sizeof(struct PolyNode));
    P->link=NULL;
    Rear=P;
    while(t2)         //先用P1首项与P2各项相乘,构造初始的结果多项式
    {
        Attach(t1->coef*t2->coef,t1->expon+t2->expon,&Rear);
        t2=t2->link;
    }
    t1=t1->link;
    while(t1)         //依次用P1其他项与P2各项相乘,将每个乘积项插入到结果多项式中
    {
        t2=P2;
        Rear=P;
        while(t2)
        {
            e=t1->expon+t2->expon;      //计算各个乘积项的系数和指数
            c=t1->coef*t2->coef;
            while(Rear->link&&Rear->link->expon>e)Rear=Rear->link;//找到结果多项式中系数不大于乘积项系数的位置,插入该乘积项
            if(Rear->link&&Rear->link->expon==e)           //如果与结果多项式原有的项指数相同,则系数相加后插入
            {
                if(Rear->link->coef+c)Rear->link->coef+=c;
                else
                {
                    t=Rear->link;
                    Rear->link=t->link;
                    free(t);
                }
            }
            else                                           //如果与结果多项式原有的项指数不同,直接将该项插入
            {
                t=(Polynomial)malloc(sizeof(struct PolyNode));
                t->coef=c,t->expon=e;
                t->link=Rear->link;
                Rear->link=t;
                Rear=Rear->link;
            }
            t2=t2->link;
        }
        t1=t1->link;
    }
    t2=P,P=P->link;             //删除表头的空结点(头结点)
    free(t2);
    return P;
}
void PrintPoly(Polynomial P)
{
    int flag=0;         //辅助调整输出格式,第一项前不输出空格
    if(!P)printf("0 0\n");
    while(P)
    {
        if(!flag)flag=1;
        else printf(" ");
        printf("%d %d",P->coef,P->expon);
        P=P->link;
    }
    printf("\n");
}