【数据结构】第2章线性表单链表稀疏多项式的运算

淡淡的烟草味﹌ 2022-11-27 01:54 157阅读 0赞

【单链表多项式的遍历、有序创建、相加】算法分析+完整代码

--------------------

【算法分析】  
和顺序存储结构相比，利用链式存储结构更加灵活，更适合表示一般的多项式，合并过程的 空间复杂度为0(1), 所以较为常用。本节将给出如何利用单链表的基本操作来实现多项式的相加 运算。 例如，图2.22 所示两个链表分别表示多项式`A(x)=7 + 3x + 9x^8 + 5x^17` 和多项式 `B(x) = 8x + 22x^7 - 9x^8`。从图中可见，每个结点表示多项式中的一项。  
![在这里插入图片描述][20200813085233514.png_pic_center]  
根据多项式相加的运算规则：对于两个多项式中所有指数相同的项，对应系数相加，若其和 不为零，则作为 ＂和多项式” 中的一项插入到 “和多项式＂ 链表中去；对千两个多项式中指数不相同的项，则将指数值较小的项插入到 “和多项式＂ 链表中去。”和多项式” 链表中的结点无需生成，而应该从两个多项式的链表中摘取。图2.22所示的两个多项式相加的结果如图2.23所示，图中的长方框表示已被释放的结点。  
![在这里插入图片描述][2020081308532353.png_pic_center]

【完整代码】

#include<bits/stdc++.h>
    using namespace std;
    typedef int Status;
    typedef int ElemType;
    #define OVERFLOW -1
    #define ERROR 0
    #define OK 1
    
    //-----多项式的存储结构-----
    typedef struct PNode
    {
        
        float coef;             //系数
        int expn;               //指数
        struct PNode *next;     //指针域
    }PNode, *Polynomial;
    
    Polynomial Pa, Pb;
    
    //12、单链表遍历_多项式 O(n)
    Status TraverseList(Polynomial L)
    {
        
        PNode *p = L->next;             //p指向首元结点
        if(p->expn == 0)
            cout<<p->coef;
        else if(p->expn == 1)
            cout<<p->coef<<"x";
        else
            cout<<p->coef<<"x^"<<p->expn;
        p = p->next;
        while(p)
        {
        
            cout<<' ';
            if(p->coef > 0)
                cout<<"+ ";
            else
            {
        
                cout<<"- ";
                p->coef = abs(p->coef);
            }
            if(p->expn == 1)
                cout<<p->coef<<"x";
            else
                cout<<p->coef<<"x^"<<p->expn;
            p = p->next;
        }
        cout<<'\n';
        return OK;
    }
    
    //17、有序单链表创建_多项式_递增 O(n^2)        										
    void CreatePolyn(Polynomial &P, int n)
    {
        //输入m项的系数和指数，建立表示多项式的有序链表P
        P = new PNode;
        P->next = NULL;                     //先建立一个带头结点的单链表
        for(int i = 1; i <= n; i++)         //依次输入n个非零项
        {
        
            PNode *s = new PNode;           //生成新结点
            cin>>s->coef>>s->expn;          //输入系数和指数
            PNode *pre = P;                 //pre保存P的前驱，初值为头结点
            PNode *q = P->next;             //q初始化，指向首元结点
            while(q && q->expn < s->expn)   //通过比较指数找到第一个大于输入项指数的项*q
            {
        
                pre = q;
                q = q->next;
            }
            s->next = q;
            pre->next = s;                  //将输入项s插入到q和其他前驱结点pre之间
        }
    }
    //18、有序单链表并集_多项式_递增 时间O(m + n) 空间O(1)
    void AddPolyn(Polynomial &Pa, Polynomial &Pb)
    {
        //多项式加法：Pa = Pa + Pb，利用两个多项式的结点构成“和多项式”
        PNode *p1 = Pa->next;
        PNode *p2 = Pb->next;
        PNode *p3 = Pa;
        PNode *r;
        while(p1 && p2)
        {
        
            if(p1->expn == p2->expn)
            {
        
                float 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()
    {
        
        int n;
        cout<<"请输入多项式A的项数：";
        cin>>n;
        cout<<"请输入多项式A的各项的系数和指数：";
        CreatePolyn(Pa, n);
        cout<<"请输入多项式B的项数：";
        cin>>n;
        cout<<"请输入多项式B的各项的系数和指数：";
        CreatePolyn(Pb, n);
        cout<<'\n';
        cout<<"A(x) = ";
        TraverseList(Pa);
        cout<<"B(x) = ";
        TraverseList(Pb);
        AddPolyn(Pa, Pb);
        cout<<"A(x) + B(x) = ";
        TraverseList(Pa);
        return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODc4Mjky_size_16_color_FFFFFF_t_70_pic_center]

[20200813085233514.png_pic_center]: /images/20221124/0fce48420e0f4e7c87ed9609cf4531dc.png
[2020081308532353.png_pic_center]: /images/20221124/ed31510cab7f4593bf93b33f6d03a2aa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODc4Mjky_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/f48533d8c8b74ba897615a037c434757.png