您的位置: 网站首页 > 程序开发 > 数据结构 > 第2章 线性表 > 【2.4 一元多项式的表示及相加】

2.4 一元多项式的表示及相加

 

2.4  一元多项式的表示及相加

假设一个多项式形式为 ,其中,ei1im)为整数类型的指数,并且没有相同指数的多项式;ci1im)为实数类型的序数。编写求两个多项式相加的程序。

一个多项式由多个(1im)多项式组成,每个多项式采用以下节点存储:

coef

expn

next

其中,coef数据域存放序数ciexpn数据域存放指数einext域是一个链域,指向下一个节点。由此,一个多项式可以表示成由这些节点链接起来的单链表(假设该单链表是带头节点的单链表)。这样的单链表节点的类型定义如下:

typedef struct node

{ 

   float coef;          /*序数*/

   int expn;            /*指数*/

   struct node *next;  /*指向下一个节点的指针*/

} PolyNode;

在该单链表上实现线性表基本运算的原理与2.3.1节描述的完全相同,这些运算的实现算法如下:

void InitList(PolyNode *&L)                  /*初始化多项式单链表*/

{

    L=(PolyNode *)malloc(sizeof(PolyNode));  /*建立头节点*/

    L->next=NULL;

}

int GetLength(PolyNode *L)                    /*求多项式单链表的长度*/

{

    int i=0;

    PolyNode *p=L->next;

    while(p!=NULL)                       /*扫描单链表L,用i累计数据节点个数*/

   {

        i++;                             /*计数增加*/

        p=p->next;                       /*指针后移*/

    }

    return i;

}

PolyNode *GetElem(PolyNode *L,int i)    /*返回多项式单链表中第i个节点的指针*/

{

    int j=1;

    PolyNode *p=L->next;

    if(i<1 || i>GetLength(L))

         return NULL;

    while(j<i)                           /*沿next域找第i个节点*/

    {

       p=p->next;                        /*指针后移*/

       j++;

    }

    return p;

}

PolyNode *Locate(PolyNode *L,float c,int e)/*在多项式单链表中按值查找*/

{

    PolyNode *p=L->next;

    while(p!=NULL && (p->coef!=c ||p->expn!=e))

         p=p->next;                          /*指针后移*/

    return p;

}

int InsElem(PolyNode *L,float c,int e,int i)    /*在多项式单链表中插入一个节点*/

{

    int j=1;

    PolyNode *p=L,*s;

    s=(PolyNode *)malloc(sizeof(PolyNode));

    s->coef=c;s->expn=e;s->next=NULL;

    if(i<1 || i>GetLength(L)+1)

        return 0;

    while (j<i)                  /*查找第i-1个节点*p*/

    {

       p=p->next;                /*指针后移*/

       j++;

    }

    s->next=p->next;

    p->next=s;

    return 1;

}

int DelElem(PolyNode *L,int i)  /*在多项式单链表中删除一个节点*/

{

    int j=1;

    PolyNode *p=L,*q;

    if (i<1 || i>GetLength(L))

       return 0;

    while (j<i)                   /*在单链表中查找第i-1个节点,由p指向它*/

    {

       p=p->next;j++;

    }

    q=p->next;                     /*q指向被删节点*/

    p->next=q->next;              /*删除*q节点*/

    free(q);

    return 1;

}

void DispList(PolyNode *L)      /*输出多项式单链表的元素值*/

{

    PolyNode *p=L->next;

    while (p!=NULL)

    {  

        printf("(%g,%d) ",p->coef,p->expn);

        p=p->next;

    }

    printf("\n");

}

以上述多项式单链表的基本运算为基础,利用多项式序数数组C和指数数组E,创建一个多项式单链表的算法如下:

void CreaPolyList(PolyNode *&L,float C[ ],int E[ ],int n)

{

    int i;

    InitList(L);

    for (i=0;i<n;i++)

        InsElem(L,C[i],E[i],i+1);

}

将一个表示任意次序的多项式的单链表按expn数据域值从小到大顺序排列的算法的基本思路是采用插入排序法;首先分离出头节点*L,将第1个节点链接到其后,这样构成一个新有序单链表,再对原单链表中第2个及以后的节点,根据expn值在新有序单链表中通过比较找到正确的位置后插入。直到原单链表的所有节点插入完毕,算法便结束了。算法程序如下:

void SortPloy(PolyNode *&L)         /*L的多项式单链表按expn域递增排序*/

{

    PolyNode *p=L->next,*q,*pre;

    L->next=NULL;

    while(p!=NULL)

    { 

       if(L->next==NULL)             /*处理第1个节点*/

    {  

       L->next=p;p=p->next;

       L->next->next=NULL;

     }

         else                         /*处理其余节点*/

        {  

           pre=L;q=pre->next;

            while (q!=NULL && p->expn>q->expn)   

/*q->expn刚大于或等于p->expn的节点*q的前驱节点*pre*/

            {

                 pre=q;q=q->next;

              }

              q=p->next;                /**pre节点之后插入*p*/

              p->next=pre->next;

              pre->next=p;

              p=q;

        }

    }

}

将两个按expn数据域值从小到大顺序排列的多项式相加的算法的基本思路如下:首先创建新单链表的头节点*pc(存储相加后的结果),让p1p2分别作为扫描papb的指针,它们先指向papb单链表的第1个节点。比较*p1*p2两个节点的expn值,复制expn值较小的节点*s,将*s链接到pc单链表的尾节点(始终由tc指向它)之后。若*p1*p2两个节点的expn值相等,且它们的coef域值相加后不为零,则以该相加值和expn值作为数据域值创建节点*s,也将*s链接到pc的尾节点之后。如此这样直到papb中有一个扫描完为止,然后将未扫描完的单链表的节点复制并链接到pc的尾节点之后。算法程序如下:

PolyNode *AddPoly(PolyNode *pa,PolyNode *pb)

{

    PolyNode *pc,*p1=pa->next,*p2=pb->next,*p,*tc,*s;

    pc=(PolyNode *)malloc(sizeof(PolyNode));   /*新建头节点*pc*/

    pc->next=NULL;                                /*pc为新建单链表的头节点*/

    tc=pc;                               /*tc始终指向新建单链表的最后节点*/

    while(p1!=NULL && p2!=NULL)

{

        if(p1->expn<p2->expn)             /**p1节点复制到*s并链pc*/

        {

              s=(PolyNode *)malloc(sizeof(PolyNode));

              s->coef=p1->coef;s->expn=p1->expn;s->next=NULL;

              tc->next=s;tc=s;

              p1=p1->next;

        }

        else if(p1->expn>p2->expn)       /**p2节点复制到*s并链pc*/

        {  

             s=(PolyNode *)malloc(sizeof(PolyNode));

             s->coef=p2->coef;s->expn=p2->expn;s->next=NULL;

             tc->next=s;tc=s;

             p2=p2->next;

         }

         else                                /*p1->expn=p2->expn的情况*/

         {

             if (p1->coef+p2->coef!=0)  /*序数相加不为0时新建节点s并链接到pc*/

             {

                  s=(PolyNode *)malloc(sizeof(PolyNode));

                 s->coef=p1->coef+p2->coef;s->expn=p1->expn;

                 s->next=NULL;

                 tc->next=s;tc=s;

             }

             p1=p1->next;p2=p2->next;

         }

}

    if(p1!=NULL) p=p1;       /*将尚未扫描完的余下节点复制并链接到pc单链表之后*/

    else p=p2;

    while(p!=NULL)

    {   

         s=(PolyNode *)malloc(sizeof(PolyNode));

         s->coef=p->coef;s->expn=p->expn;s->next=NULL;

         tc->next=s;tc=s;

         p=p->next;

    }

    tc->next=NULL;         /*新建单链表最后节点的next域置空*/

    return pc;

}

现使用上述算法,实现以下两个多项式相加:

3x+7+5x17+9x8-9x8+8x+22x7

设计的主程序如下:

void main()

{

    PolyNode *L1,*L2,*L3;

    float C1[ ]={3,7,5,9},C2[ ]={-9,8,22};  /*多项式序数数组*/

    int E1[ ]={1,0,17,8},E2[ ]={8,1,7};     /*多项式指数数组*/

    InitList(L1);                          /*初始化多项式单链表L1*/

    InitList(L2);                           /*初始化多项式单链表L2*/

    InitList(L3);                           /*初始化多项式单链表L3*/

    CreaPolyList(L1,C1,E1,4);               /*创建多项式单链表L1*/

    CreaPolyList(L2,C2,E2,3);               /*创建多项式单链表L2*/

    printf("两多项式相加运算\n");

    printf("原多项式A:");DispList(L1);

    printf("原多项式B:");DispList(L2);

    SortPloy(L1);                   /*L1的多项式单链表按expn域递增排序*/

    SortPloy(L2);                   /*L2的多项式单链表按expn域递增排序*/

    printf("排序后的多项式A:");DispList(L1);  /*输出多项式单链表L1的元素值*/

    printf("排序后的多项式B:");DispList(L2);  /*输出多项式单链表L2的元素值*/

    L3=AddPoly(L1,L2); /*将两个按expn数据域值从小到大顺序排列的多项式L1L2相加*/

    printf("多项式相加结果:");DispList(L3);   /*输出结果多项式单链表L3的元素值*/

}

本程序的执行结果如下所示,从中看到上述两个多项式相加的结果为:

7+11x+22x7+5x17

两多项式相加运算   

      原多项式A(3,1)  (7,0)  (5,17)  (9,8)

      原多项式B(-9,8)  (8,1)  (22,7)

排序后的多项式A(7,0)  (3,1)  (9,8)  (5,17)

排序后的多项式B(8,1)  (22,7)  (-9,8)

  多项式相加结果:(7,0)  (11,1)  (22,7)  (5,17)