3.7　综合案例：一元多项式的表示与相乘

一元多项式的相乘是线性表在生活中一个实际应用，它涵盖了本节所学到的链表的各种操作。通过使用链表实现一元多项式的相乘，巩固大家对链表的理解与掌握。

3.7.1　一元多项式的表示

在数学中，一个一元多项式A _n （x）可以写成降幂的形式，即A _n （x）=a _n x ⁿ +a _n-1 x ^n-1 +…+a ₁ x+a ₀ ，如果a _n ≠0，则A _n （x）称为n阶多项式。一个n阶多项式由n+1个系数构成。一个n阶多项式的系数可以用线性表（a _n ，a _n-1 ，…，a ₁ ，a ₀ ）表示。

线性表的存储可以采用顺序存储结构，这样使多项式的一些操作变得更加简单。可以定义一个维数为n+1的数组a[n+1]，a[n]存放系数a _n ，a[n-1]存放系数a _n-1 ，…，a[0]存放系数a ₀ 。但是，实际情况是可能多项式的阶数（最高的指数项）会很高，多项式的每个项的指数会差别很大，这可能会浪费很多的存储空间。例如一个多项式P（x）=10x ²⁰⁰¹ +x+1，若采用顺序存储，则存放系数需要2002个存储空间，但是存储有用的数据只有3个。若只存储非零系数项，还必须存储相应的指数信息。

一元多项式A _n （x）=a _n x ⁿ +a _n-1 x ^n-1 +…+a ₁ x+a ₀ 的系数和指数同时存放，可以表示成一个线性表，线性表的每一个数据元素由一个二元组构成。因此，多项式A _n （x）可以表示成线性表（（a _n ，n），（a _n-1 ，n-1），…，（a ₁ ，1），（a ₀ ，0））。

多项式P（x）可以表示成（（10，2001），（1，1），（1，0））的形式。

因此，多项式可以采用链式存储方式表示，每一项可以表示成一个结点，结点的结构由存放系数的coef域、存放指数的expn域和指向下一个结点的next指针域3个域组成，如图3-39所示。

结点结构可以用C语言描述如下。

---

typedef struct polyn
{
    float coef;
    int expn;
    struct polyn *next;
}PloyNode,*PLinkList;

---

例如，多项式S（x）=9x ⁸ +5x ⁴ +6x ² +7可以表示成链表，如图3-40所示。

3.7.2　一元多项式相乘

两个一元多项式的相乘运算，需要将一个多项式的每一项的指数与另一个多项式的每一项的指数相加，并将其系数相乘。假设两个多项式A _n （x）=a _n x ⁿ +a _n-1 x ^n-1 +…+a ₁ x+a ₀ 和B _m （x）=b _m x ^m +b _m-1 x ^m-1 +…+b ₁ x+b ₀ ，要将这两个多项式相乘，就是将多项式A _n （x）中的每一项与B _m （x）相乘，相乘的结果用线性表表示为（（a _n *b _m ，n+m），（a _n-1 *b _m ，n+m-1），…，（a ₁ ，1），（a ₀ ，0））。

例如，两个多项式A（x）和B（x）相乘后得到C（x），A（x）=5x ⁴ +3x ² +3x，B（x）=7x ³ +5x ² +6x，C（x）=35x ⁷ +25x ⁶ +51x ⁵ +36x ⁴ +33x ³ +18x ² ，表示成链式存储结构如图3-41所示。

算法思想：设A、B和C分别是多项式A（x）、B（x）和C（x）对应链表的头指针，要计算A（x）和B（x）的乘积，先计算出A（x）和B（x）的最高指数和，即4+3=7，则A（x）和B（x）的乘积C（x）的指数范围在0～7之间。然后将A（x）的各项按照指数降幂排列，将B（x）按照指数升幂排列，分别设两个指针pa和pb，pa用来指向链表A，pb用来指向链表B，从第一个结点开始计算两个链表的expn域的和，并将其与k比较（k为指数和的范围，从7到0递减），使链表的和呈递减排列。若和小于k，则pb=pb->next；若和等于k，则求出两个多项式系数的乘积，并将其存入新结点中。若和大于k，则pa=pa->next。这样就可以得到多项式A（x）和B（x）的乘积C（x）。算法结束后重新将链表B逆置，将链表B恢复原样。

程序代码实现如下。

---

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h> 
/*
一元多项式结点类型定义*/
typedef struct polyn
{
    float coef;         /*
存放一元多项式的系数*/
    int expn;                   /*
存放一元多项式的指数*/
    struct polyn *next;
}PolyNode, *PLinkList; 
void OutPut(PLinkList head)
/*
输出一元多项式*/
{
                PolyNode *p=head->next;
                while(p)
                {
                        printf("%1.1f",p->coef);
                        if(p->expn)
                                printf("*x^%d",p->expn);
                        if(p->next&&p->next->coef>0)
                                printf("+");
                        p=p->next;
                }
}
void main()
{
    PLinkList A,B,C;
    A=CreatePolyn();
    printf("A(x)=");
    OutPut(A);
    printf("\n");
    B=CreatePolyn();
    printf("B(x)=");
    OutPut(B);
    printf("\n");
    C=MultiplyPolyn(A,B);
    printf("C(x)=A(x)*B(x)=");
    OutPut(C);                          /*
输出结果*/
    printf("\n"); 
}
PLinkList CreatePolyn() 
/*
创建一元多项式，使一元多项式呈指数递减*/
{
    PolyNode *p,*q,*s;
                PolyNode *head=NULL;
                int expn2;
                float coef2;
                head=(PLinkList)malloc(sizeof(PolyNode));               /*
动态生成一个头结点*/
                if(!head)
                        return NULL;
                head->coef=0;
                head->expn=0;
                head->next=NULL;
                do 
                {
                        printf("
输入系数coef(
系数和指数都为0
结束)");
                        scanf("%f",&coef2);
                        printf("
输入指数exp(
系数和指数都为0
结束)");
                        scanf("%d",&expn2);
                        if((long)coef2==0&&expn2==0)
                                break;
                        s=(PolyNode*)malloc(sizeof(PolyNode));
                        if(!s)
                                return NULL;
                        s->expn=expn2;
                        s->coef=coef2;
                        q=head->next;                                        /*q
指向链表的第一个结点，即表尾*/
                        p=head;                                         /*p
指向q
的前驱结点*/
                        while(q&&expn2<q->expn)           /*
将新输入的指数与q
指向的结点指数比较*/
                        {
                                p=q;
                                q=q->next;
                        }
                        if(q==NULL||expn2>q->expn)                /*q
指向要插入结点的位置，p
指向要插入结点的前驱*/
                        {
                                p->next=s;                           /*
将s
结点插入到链表中*/
                                s->next=q;
                        }
                        else
                                q->coef+=coef2;                      /*
如果指数与链表中结点指数相同，则将系数相加即可*/
                } while(1);
                return head;
}
PolyNode *Reverse(PLinkList head) 
/*
将生成的链表逆置，使一元多项式呈指数递增形式*/
{
                PolyNode *q,*r,*p=NULL; 
                q=head->next;
                while(q)
                {
                        r=q->next;           /*r
指向链表的待处理结点*/
                        q->next=p;           /*
将链表结点逆置*/
                        p=q;                            /*p
指向刚逆置后链表结点*/
                        q=r;                            /*q
指向下一准备逆置的结点*/
                }
                head->next=p;                        /*
将头结点的指针指向已经逆置后的链表*/
                return head;
}
PolyNode *MultiplyPolyn(PLinkList A,PLinkList B)
/*
多项式的乘积*/
{
                PolyNode *pa,*pb,*pc,*u,*head;
                int k,maxExp;
                float coef;
                head=(PLinkList)malloc(sizeof(PolyNode));       /*
动态生成头结点*/
                if(!head)
                        return NULL;
                head->coef=0.0;
                head->expn=0;
                head->next=NULL;
                if(A->next!=NULL&&B->next!=NULL)
                        maxExp=A->next->expn+B->next->expn; /*maxExp
为两个链表指数的和的最大值*/
                else
                        return head;
                pc=head;
                B=Reverse(B);                                                           /*
使多项式B
（x
）呈指数递增形式*/
                for(k=maxExp;k>=0;k--)                                       /*
多项式的乘积指数范围为0-maxExp*/
                {
                        pa=A->next;
                        while(pa!=NULL&&pa->expn>k)                       /*
找到pa
的位置*/
                                pa=pa->next;
                        pb=B->next;
                        while(pb!=NULL&&pa!=NULL&&pa->expn+pb->expn<k)/*
如果和小于k
，使pb
移到下一个结点*/
                                pb=pb->next;
                        coef=0.0;
                        while(pa!=NULL&&pb!=NULL)
                        {
                                if(pa->expn+pb->expn==k)  /*
如果在链表中找到对应的结点，即和等于k
，求相应的系数*/
                                {
                                        coef+=pa->coef*pb->coef;
                                        pa=pa->next;
                                        pb=pb->next;
                                }
                                else if(pa->expn+pb->expn>k)   /*
如果和大于k
，则使pa
移到下一个结点*/
                                        pa=pa->next;
                                else
                                        pb=pb->next;                         /*
如果和小于k
，则使pb
移到下一个结点*/
                        }
                        if(coef!=0.0)                                           
                                /*
如果系数不为0
，则生成新结点，并将系数和指数分别赋值给新结点。并将结点插入链表中*/
                        {
                                u=(PolyNode*)malloc(sizeof(PolyNode));
                                u->coef=coef;
                                u->expn=k;
                                u->next=pc->next;
                                pc->next=u;
                                pc=u;
                        }
                }
                B=Reverse(B);                   /*
完成多项式乘积后，将B
（x
）呈指数递减形式*/
                return head;
}

---

程序运行结果如图3-42所示。