单链表应用------一元多项式

忘是亡心i 2023-07-15 09:13 3阅读 0赞

## 单链表应用------一元多项式 ##

单链表应用------一元多项式

【问题描述】编写一个程序用单链表存储多项式，并实现两个一元多项式A与B相加的函数。A，B刚开始是升序的，A与B之和按降序排列。例如：  
多项式A: 1.2X^0 2.5X^1 3.2X^3 -2.5X^5  
多项式B: -1.2X^0 2.5X^1 3.2X^3 2.5X^5 5.4X^10  
多项式A与B之和：5.4X^10 6.4X^3 5X^1

【输入形式】任意两个多项式A和B

【输出形式】多项式中某一项的系数与指数，系数保留一位小数。

【样例输入】1.2 0 2.5 1 3.2 3 －2.5 5  
－1.2 0 2.5 1 3.2 3 2.5 5 5.4 10  
2

【样例输出】6.4 3

【样例说明】  
第一个多项式的系数与指数对，以空格隔开  
第二个多项式的系数与指数对，以空格隔开  
输出第２项的系数与指数，系数与指数间用空格隔开，系数保留一位小数

【评分标准】必须用链表实现。

#include <iostream>
    #include"stdio.h"
    using namespace std;
    struct Node
    {
        
        float coef;
        int	exp; //coef表示系数，exp表示指数
        Node*next;
    };
    class Polynomial
    {
        
    public:
        Polynomial();//构造函数
        Polynomial(const Polynomial &B);
        Polynomial operator+(Polynomial &B); //重载加号 多项式相加
        void Print();
        void Printk(int);
    private:
        Node*first; //一元多项式单链表的头指针
    };
    Polynomial::Polynomial()
    {
        
        Node*r=NULL,*s=NULL;
        //int coef,exp;
        first=new Node; //申请头结点
        r=first;
        char c;
         do
        {
        
            s=new Node;
            scanf("%f%d",&s->coef,&s->exp);
            r->next=s;
            r=s;
            c=getchar();
        }while(c != EOF && c != '\n');
    r->next=NULL;
    }
    Polynomial:: Polynomial(const Polynomial &B)
    {
        
        first=B.first;
    }
    Polynomial Polynomial::operator+(Polynomial &B)
    {
        
        Node*pre=first,*p=pre->next;
        Node*qre=B.first,*q=qre->next;
        Node*qtemp=NULL;
        while(p!=NULL&&q!=NULL)
        {
        
            if(p->exp<q->exp){
        
                pre=p;p=p->next;
            }
            else if(p->exp>q->exp){
        
                    qtemp=q->next;
                    pre->next=q;
                    q->next=p;
                    pre=q;
                    q=qtemp;
                    qre->next=q;
                    }
                    else{
        
                         p->coef=p->coef+q->coef;
                         if(p->coef==0){
        
                            pre->next=p->next;
                            delete p;
                            p=pre->next;
                         }
                         else{
        
                            pre=p;p=p->next;
                         }
                         qre->next=q->next;
                         delete q;
                         q=qre->next;
        }
    }
    if(q)
    pre->next=q;
    return *this;
    
    }
     void Polynomial::Print()
    {
        Node *p=first->next;
    if(p)
        cout<<p->coef<<"x"<<p->exp;
        p=p->next;
        while(p)
        {
        if(p->coef>0)
        cout<<"+"<<p->coef<<'x'<<p->exp;
        else
            cout<<p->coef<<'x'<<p->exp;
        p=p->next;
    
        }
        cout<<endl;
    
    }
    void Polynomial::Printk(int k)
    {
        Node *p=first;
    int cnt=0;
    while(p&&cnt<k)
    {
        p=p->next;
    cnt++;
    }
    Node *prek=first;
    while(p){
        
        p=p->next;
        prek=prek->next;
    }
     printf("%.1f %d",prek->coef,prek->exp);
    }
    
    int main()
    {
        Polynomial A;
    Polynomial B;
    A=A+B;
    int k;
    cin>>k;
    A.Printk(k);
    return 0;
    }