一元多项式加乘运算

╰+攻爆jí腚メ 2022-06-08 09:48 177阅读 0赞

#include <iostream>
    #include <cstdlib>
    using namespace std;
    
    typedef struct node
    {
        int data;
        int e;
        struct node *next;
    }ListNode;
    
    void createList(ListNode *&L,int n)
    {
        L = (ListNode *)malloc(sizeof(ListNode));
        L->next = NULL;
        ListNode *q;
        q = L;
        for(int i = 0;i<n;i++)
        {
            ListNode *p;
            p = (ListNode *)malloc(sizeof(ListNode));
            cin>>p->data;
            cin>>p->e;
            p->next = q->next;
            q->next = p;
            q = p;
        }
    }
    
    void Print(ListNode *L)
    {
        ListNode *p;
        p = L->next;
        while(p)
        {
            if(L->next == p)
                cout<<p->data<<"*X^"<<p->e;
            else
                cout<<" + "<<p->data<<"*X^"<<p->e;
            p = p->next;
        }
        cout <<endl;
    }
    
    void listAdd(ListNode *L1,ListNode *L2,ListNode *&L)
    {
        L = (ListNode *)malloc(sizeof(ListNode));
        L->next = NULL;
        ListNode *i,*j,*k;
        i = L1->next;
        j = L2->next;
        k = L;
        while(i&&j)
        {
            ListNode *temp;
            temp=(ListNode *)malloc(sizeof(ListNode));
            if(i->e == j->e)
            {
                temp->e = i->e;
                temp->data = i->data + j->data;
                i=i->next;
                j=j->next;
            }
            else if(i->e<j->e)
            {
                temp->e = i->e;
                temp->data = i->data;
                i = i->next;
            }
            else
            {
                temp->e = j->e;
                temp->data = j->data;
                j = j->next;
            }
            temp->next = k->next;
            k->next = temp;
            k = temp;
        }
        if(i)
        {
            while(i)
            {
                ListNode *temp;
                temp=(ListNode *)malloc(sizeof(ListNode));
                temp->data = i->data;
                temp->e = i->e;
                temp->next = k->next;
                k->next = temp;
                k = temp;
                i = i->next;
            }
        }
        else if(j)
        {
            while(j)
            {
                ListNode *temp;
                temp=(ListNode *)malloc(sizeof(ListNode));
                temp->data = j->data;
                temp->e = j->e;
                temp->next = k->next;
                k->next = temp;
                k = temp;
                j = j->next;
            }
        }
    }
    void listInsert(ListNode *&L,int e,int data)
    {
        ListNode *p;
        p = L;
        ListNode *temp = (ListNode *)malloc(sizeof(ListNode));
        temp->data = data;
        temp->e = e;
        if(!p->next)
        {
            temp->next = p->next;
            p->next = temp;
            return ;
        }
        while(p->next)
        {
            if(p->next->e==e)
            {
                p->next->data += data;
                return ;
            }
            else if(p->next->e>e)
            {
                temp->next = p->next;
                p->next = temp;
                return ;
            }
            p = p->next;
        }
        temp->next = NULL;
        p->next = temp;
    }
    void listMul(ListNode *L1,ListNode *L2,ListNode *&L3)
    {
        L3 = (ListNode *)malloc(sizeof(ListNode));
        L3->next = NULL;
        ListNode *i,*j;
        for(i = L1->next;i;i=i->next)
        {
            for(j = L2->next;j;j=j->next)
            {
                listInsert(L3,i->e + j->e,i->data * j->data);
            }
        }
    }
    
    int main()
    {
        ListNode *L1,*L2,*L3,*L4;
        int n,m;
        cin>>n;
        createList(L1,n);
        cin>>m;
        createList(L2,m);
        listAdd(L1,L2,L3);
        listMul(L1,L2,L4);
        cout<<"Summation is "<<endl;
        Print(L3);
        cout<<"The product is"<<endl;
        Print(L4);
        return 0;
    }
    
    /*
    3
    1 2 2 3 3 4
    3
    2 3 3 4 4 5
    
    1*x^2 + 2*x^3 + 3*x^4
    2*x^3 + 3*x^4 + 4*x^5
    
    2*x^5 + 3*x^6 + 4*x^7 + 4*x^6 + 6*x^7 + 8*x^8 + 6*x^7 + 9*x^8 + 12*x^9
    
       1       2       3       2         1
    2*x^5 + 7*x^6
     + 16*x^7 + 17*x^8 + 12*x^9
    */