数据结构一元多项式相加

梦里梦外; 2022-05-29 11:39 240阅读 0赞

做一个豁达而努力的自己。

相加的部分也就是用一个新的链表存储，，，和单链表尾插的方法差不多，，，也就是分了3种情况，，，

代码：

#include <iostream>
    using namespace std;
    
    //一元多项式的存储结构
    typedef struct Node
    {
        int coe;    //系数
        int exp;    //指数
        Node *next;
    }*polynomial;
    //一元多项式的初始化
    bool InitPoly(polynomial &L)
    {
        L = new Node;
        if(!L)
            return false;
        L->next = NULL;
        return true;
    }
    //一元多项式的创建
    void CreatePoly(polynomial &L, int n)
    {
        polynomial s, r;
        r = L;
        while(n--)
        {
            int i = 1;
            s = new Node;
            cout << "输入第" << i << "项的系数和指数:";
            i++;
            cin >> s->coe;
            cin >> s->exp;
            s->next = NULL;
            r->next = s;
            r = s;
        }
    }
    //一元多项式相加
    polynomial AddPoly(polynomial pa, polynomial pb)
    {
        polynomial s;   //创建和指针
        polynomial r;   //创建尾指针
        s = new Node;   //为和节点创建一个头结点
        s->next = NULL;
        r = s;
        pa = pa->next;  //指向首元结点
        pb = pb->next;
        while(pa && pb)
        {
            if(pa->exp > pb->exp)
            {
                r->next = pb;
                r = pb;
                pb = pb->next;
            }
            else if(pa->exp < pb->exp)
            {
                r->next = pa;
                r = pa;
                pa = pa->next;
            }
            else
            {
                int sum = pa->coe + pb->coe;
                if(0 != sum)
                {
                    pa->coe = pa->coe + pb->coe;
                    r->next = pa;
                    r = pa;
                }
                pa = pa->next;
                pb = pb->next;
            }
        }
        if(NULL != pa)
            r->next = pa;
        if(NULL != pb)
            r->next = pb;
        return s;
    }
    //一元多项式的输出
    void PutPoly(polynomial L)
    {
        polynomial p;
        p = L->next;
        while(p)
        {
            cout << "(" << p->coe << "," << p->exp << ")" << '\t';
            p = p->next;
        }
        cout << endl;
    }
    int main()
    {
        polynomial pa, pb;
        InitPoly(pa);
        InitPoly(pb);
        cout << "输入多项式a的项数:";
        int n;
        cin >> n;
        CreatePoly(pa, n);
        cout << "输入多项式b的项数:";
        cin >> n;
        CreatePoly(pb, n);
        cout << "a+b的多项式为:";
        PutPoly(AddPoly(pa, pb));
        return 0;
    }