多项式的表示

例：一元多项式： $f(x)=a_0+a_1x+…+a_{n-1}x^{n-1}+a_nx^n$

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

如何表示多项式？

多项式的关键数据：

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

多项式问题的启示：

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

一元多项式表示方法

如：多项式 $x+3x^{2000}$ 的表示

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

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

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

下标i	0	1	2	3	4	5
a[i]	1	0	-3	0	0	4
项	1	0	$-3x^2$	0	0	$4x^5$

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

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

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

例： $P_1(x)=9x^{12}+15x^8+3x^2$ 和 $P_2(x)=26x^{19}-4x^8-13x^6+82$

下标i	0	1	2
系数 $ai$	9	15	3
指数 $i$	12	8	2

下标j	0	1	2	3
系数 $aj$	26	-4	-13	82
指数 $j$	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)

结果： $P_3(x)=26x^{19}+9x^{12}+11x^8-13x^6+3x^2+82$

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

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

例： $P1(x)=9x^{12}+15x^8+3x^2$ 和 $P2(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)=9x^{12}y^2+4x^{12}+15x^8y^3-x^8y+3x^2$

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

$P(x,y)=(9y^2+4)x{12}+(15y^3-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;
};

多项式加法和乘法的实现

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

$3x^4-5x^2+6x-2$
$5x^{20}-7x^4+3x$
两个多项式和为
- $5x^{20}-4x^4-5x^2+9x-2$
两个多项式乘积为
- $15x^{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");
}