如何实现链表的多项式相加？

Question

请问怎么修改代码让其能实现链表的多项式相加

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;
typedef int ElemType;
typedef int Status;


typedef struct PNode
{
    float coef;
    int expn;
    struct PNode *next;
}PNode,*Polynomial;

void Init(Polynomial &p)
{
    p=new PNode;
    p->next=NULL;
}

void CreatePolyn(Polynomial &p,int n)
{
    PNode *l=p;
    for(int i=0;i<n;i++)
    {
        PNode *q=new PNode;
        q->next=NULL;
        cout<<"请输入多项式系数：";
        cin>>q->coef;
        cout<<"请输入多项式指数：";
        cin>>q->expn;
        l->next=q;
        l=q;
    }
}

void AddPolyn(Polynomial &Pa,Polynomial &Pb)
{
     Polynomial p1=Pa->next;
     Polynomial p2=Pb->next;
     Polynomial p3=Pa;
     while(p1&&p2)
     {
         if(p1->expn==p2->expn)
         {
             sum= p1->coef+ p2->coef;
             if(sum!=0)
             {
                 p1->coef=sum;
                 p3->next=p1;
                 p3=p1;
                 p1=p1->next;
                 r=p2;
                 p2=p2->next;
                 delete r;
             }
             else
             {
                 r=p1;
                 p1=p1->next;
                 delete r;
                 r=p2;
                 p2=p2->next;
                 delete r;
             }

         }
             else if(p1->expn<p2->expn)
             {
                 p3->next=p1;
                 p3=p1;
                 p1=p1->next;
             }
             else
             {
                 p3->next=p2;
                 p3=p2;
                 p2=p2->next;
             }
     }
         p3->next=p1?p1:p2;
         delete Pb;
}

int main()
{
    Polynomial Pa,Pb;
    Init(Pa);
    CreatePolyn(Pa,3);
    Init(Pb);
    CreatePolyn(Pb,4);
    AddPolyn(Pa,Pb);
}

Answer 1

相加的时候以Pa为基准进行遍历每个元素，然后找Pb中是否有跟Pa中同级的，如果有就相加到Pa，并把该元素从Pb中删除。最后把Pb中剩余的合并到Pa中。我加了一些打印，运行结果如下：

代码：

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;
typedef int ElemType;
typedef int Status;


typedef struct PNode
{
    float coef;
    int expn;
    struct PNode *next;
}PNode,*Polynomial;

void Init(Polynomial &p)
{
    p=new PNode;
    p->next=NULL;
}

void CreatePolyn(Polynomial &p,int n)
{
    PNode *l=p;
    for(int i=0;i<n;i++)
    {
        PNode *q=new PNode;
        q->next=NULL;
        cout<<"请输入多项式系数：";
        cin>>q->coef;
        cout<<"请输入多项式指数：";
        cin>>q->expn;
        l->next=q;
        l=q;
    }
}

//显示多项式，假设是x的多项式
void show(Polynomial p)
{
    PNode* l = p->next;
    while(l)
    {
        if(l != p->next)
            cout << "+"<< l->coef<<"x"<<l->expn ;
        else
            cout << l->coef<<"x"<<l->expn ;
        l = l->next;
    }
    
}


void AddPolyn(Polynomial &Pa,Polynomial &Pb)
{
    Polynomial p1=Pa;
    Polynomial p2=Pb;
    Polynomial p3=Pa;

    //遍历Pa，找到所有Pb中能累加到Pa上的因子
    while(p1->next)
    {
        p2 = Pb; 
        while(p2->next)
        {
            if(p2->next->expn == p1->next->expn)
            {
                p1->next->coef += p2->next->coef;
                //将p2->next从pb中删除
                PNode* t = p2->next;
                p2->next = t->next;
                delete t;
            }
            p2 = p2->next;
        }
        p1 = p1->next;
    }

    //遍历Pb，将Pb中的指数不跟Pa中的指数相同的项添加到Pa中
    p1->next = Pb->next;

    delete Pb;
    Pb = 0;//释放Pb

    //如果多项式的和为0，就把该多项式从链表中删除
    while(p3->next)
    {
        if(p3->next->coef == 0)
        {
            PNode* t = p3->next;
            p3->next = t->next;
            delete t;
        }
        p3 = p3->next;
    }

}

//释放链表
void release(Polynomial &p)
{
    PNode* L = p;
    while(p)
    {
        L = p->next;
        delete p;
        p = L;
    }
    p = 0;
}

int main()
{
    Polynomial Pa,Pb;
    cout <<"PA:"<<endl;
    Init(Pa);
    CreatePolyn(Pa,3);
    
    cout <<"PB:"<<endl;
    Init(Pb);
    CreatePolyn(Pb,4);

    show(Pa);
    cout <<"+";
    show(Pb);
    AddPolyn(Pa,Pb);
    cout <<"=" ;
    show(Pa);

    release(Pa);
    return 0;
}