23-4-13--链表--一元多项式的乘法与加法运算-526互联

设计函数分别求两个一元多项式的乘积与和。

输入格式:

输入分2行，每行分别先给出多项式非零项的个数，再以指数递降方式输入一个多项式非零项系数和指数（绝对值均为不超过1000的整数）。数字间以空格分隔。

输出格式:

输出分2行，分别以指数递降方式输出乘积多项式以及和多项式非零项的系数和指数。数字间以空格分隔，但结尾不能有多余空格。零多项式应输出0 0。

输入样例:

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

思路：

1、加法多项式

题目给出的输入已经按照降幂顺序排列好，相加时不需要考虑顺序的问题，同时加法也不需要考虑同类项合并，但加法需要考虑系数互为相反数的项相加为0的情况。

运算思路：

分别令p和q指向list1和list2（即两个多项式）的第一项数据

当p的指数大于q的指数，将节点p复制给新节点newNode，将newNode移动到result的末尾，p往后移动，q不动

当p的指数小于q的指数，将节点q复制给新节点newNode，将newNode移动到result的末尾，q往后移动，p不动

当p的指数等于q的指数，若p和q的系数相加不为0，则复制到结果多项式，为0则舍弃。之后p和q都要向后移动

如果p或q还有剩余的节点，直接接到结果多项式的末尾

如果给出的输入，所以项全部抵消了，或本身给出的输入就是零多项式，此时结果多项式为空表，输出0 0

2、乘法多项式

乘法不用考虑相乘系数为0的情况，但需要考虑顺序和同类项合并的问题。

二重循环，遍历第一个链表的元素，用其乘以第二个所有元素存到临时链表里，再把临时链表与目标链表用写好的多项式加法相加，重复整个过程直至遍历完第一个链表

上代码

#include <iostream>

using namespace std;

typedef struct node {
    int c;
    int e;
    struct node *next;
}linklist;
typedef struct node* plink;

plink h1,h2,h3,h4;

plink addnode(plink end,int c,int e)
{
    plink t= new linklist;
    t->c =c;
    t->e =e;
    t->next =NULL;
    end->next =t;
    return t;
}
plink clearlist(plink head)
{
    plink t,p;
    t=head->next ;
    while(t)
    {
        p=t;
        t=t->next ;
        delete p;
    }
    return head;
}

plink createlink(int n){
    plink head,end;
    head=new linklist;
    head->next =NULL;
    end=head;
    plink node;
    
    for(int i=0;i<n;i++)
    {
        node = new linklist;
        scanf("%d %d",&node->c,&node->e);
        end->next = node;
        end=node;
        end->next = NULL;
    }
    return head;
}

plink listadd(plink a,plink b)
{
    plink p=a->next ,q=b->next ;
    plink head = new linklist;
    plink end;
    head->next =NULL;
    end=head;
    plink t;
    
    while(p&&q)
    {
        if(p->e >q->e )
        {
            end= addnode(end,p->c ,p->e );
            
            p=p->next ;
        }else if(p->e < q->e )
        {
            end=addnode(end,q->c ,q->e );
            q=q->next ;
        }else
        {
            if(q->c +p->c !=0)
            {
                end=addnode(end,q->c + p->c ,p->e );
            }
            q=q->next ;
            p=p->next ;
        }
    }
    while(p)
    {
        end=addnode(end,p->c ,p->e );
        p=p->next ;
        
    }
    while (q){
        end=addnode(end,q->c ,q->e );
        q=q->next ;
    }
    end->next =NULL;
    return head;
}




plink listmulti(plink a,plink b)
{
    plink head=new linklist;
    head->next =NULL;
    plink p=a->next ,q=b->next ;
    plink end=head;
    plink node;
    plink thead=new linklist,tend;
    tend=thead;
    thead->next =NULL;
    
    int c,e;
    while(p&&q)
    {
        while(q)
        {
            c=p->c *q->c ;
            e=p->e +q->e ;
            if(c!=0)
            {
                tend = addnode(tend,c,e);
            }
            q=q->next ;
        }
        head=listadd(head,thead);
        thead=clearlist(thead);
        tend=thead;
        p=p->next;
        q=b->next ;
    }
    delete thead;
    end->next =NULL;
    return head;
}


void printnode(plink head)
{
    plink t=new linklist;
    t=head->next ;
    if(t)
    {
        printf("%d %d",t->c ,t->e );
        t=t->next ;
        while(t)
        {
            printf(" %d %d",t->c ,t->e );
            t=t->next ;
        }
    }else{
        printf("0 0");
    }
}




int main()
{
    int n;
    cin>>n;
    h1=createlink(n);
    cin>>n;
    
    h2=createlink(n);
    h4=listmulti(h1,h2);
    printnode(h4);
    printf("\n");
    h3=listadd(h1,h2);
    printnode(h3);
    clearlist(h3);
    clearlist(h4);
    delete h3;
    delete h4;
    
    return 0;
}