多项式运算线性链表的应用

最忙的时候迎来了我们数据结构的大实验周一的时候编好了一个 线性链表的都是什么什么系统的 一点意思都没有啊 看到了一个多项式的 于是我就试了一下 说是要先判断稀疏度 在确定用线性存储的还是顺序存储的 顺序存储的我没写 觉得还是链表的好 因为顺序存储的的开两个数组 一个是指数是正的 一个指数是负的 觉得可能很不好写 于是还是写了个链表的 双向链表的 用的C++写的 觉得可以运算符重载挺好的

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
class Xiang   //此乃线性链表 下面还要开数组再做 我真是蒙了
{
public:
    double coefficient;//多项式系数
    int power; //多项式的幂
    Xiang* next;
    Xiang* last;
};
class polynomial//多项式
{
public:
    int num;//项数
    Xiang *head;
    Xiang *tail;
    polynomial();//初始化
    void input();//从键盘输入多项式
    void displayup();//按指数升序输出多项式
    void displaydown();//按指数降序输出多项式
    void sort();//合并同类项并将多项式排序并删除系数为0的项
    bool addXiang();//从键盘输入增加项 构建多项式
    bool addXiang(double co,int po);//按照参数增加项
    polynomial qiuhe(polynomial p1,polynomial p2);//求和函数
    polynomial qiucha(polynomial p1,polynomial p2);//求差函数
    polynomial chengji(polynomial p1,polynomial p2);//求乘积
    polynomial operator +(polynomial p2);//重载运算符
    polynomial operator -(polynomial p2);
    polynomial operator *(polynomial p2);
};

polynomial::polynomial()//初始化
{
    num=0;
    head=new Xiang;
    head->next=NULL;
    head->last=NULL;
    tail=NULL;
}

void polynomial::input()
{
    do
    {
        cout<<"please input the num of polynomial(num>=0)"<<endl;
        cin>>num;
    }
    while(num<0);
    for(int i=0; i<num; i++)
        cout<<"num "<<i+1<<": ",addXiang();
    sort();
}

void polynomial::displayup()
{
    if(num==0)
    {
        cout<<0<<endl;
        return ;
    }
    Xiang *p=head->next;
    for(int i=0; i<num; i++)
    {
        if(p->coefficient<0)
            cout<<p->coefficient<<"X^"<<p->power;
        else if(i)
            cout<<"+"<<p->coefficient<<"X^"<<p->power;
        else
            cout<<p->coefficient<<"X^"<<p->power;
        p=p->next;
    }
    cout<<endl;
}

void polynomial::displaydown()
{
    if(num==0)
    {
        cout<<0<<endl;
        return ;
    }
    Xiang *p=tail;
    for(int i=0; i<num; i++)
    {
        if(p->coefficient<0)
            cout<<p->coefficient<<"X^"<<p->power;
        else if(i)
            cout<<"+"<<p->coefficient<<"X^"<<p->power;
        else
            cout<<p->coefficient<<"X^"<<p->power;
        p=p->last;
    }
    cout<<endl;
}

bool polynomial::addXiang()
{
    Xiang *p=new Xiang;
    Xiang *q=tail;
    double c=0;
    int po=0;
    cin>>c>>po;
    if(head->next==NULL)
    {
        head->next=p;
        p->coefficient=c;
        p->power=po;
        p->next=NULL;
        p->last=head;
        tail=p;
    }
    else
    {
        q->next=p;
        p->last=q;
        p->coefficient=c;
        p->power=po;
        p->next=NULL;
        tail=p;
    }
    return 1;
}

bool polynomial::addXiang(double co,int po)
{
    Xiang *p=new Xiang;
    Xiang *q=tail;
    if(head->next==NULL)
    {
        head->next=p;
        p->coefficient=co;
        p->power=po;
        p->next=NULL;
        p->last=head;
        tail=p;
    }
    else
    {
        q->next=p;
        p->last=q;
        p->coefficient=co;
        p->power=po;
        p->next=NULL;
        tail=p;
    }
    num++;
    sort();
    return 1;
}

void polynomial::sort()//先排序 再合并同类项 再删除系数是0的项 是的= = 这就是这个作业的核心啊 无论加减乘除都少不了= =
{
    Xiang *a=head->next;
    Xiang *b;
    for(int i=0; i<num; i++) //排序的时间复杂度为 n^2 没有操作指针直接用swap函数交换值 这样也可以吧。。
    {
        b=a;
        for(int j=i; j<num; j++)
        {
            if(b->power<a->power)
                swap(a->coefficient,b->coefficient),swap(a->power,b->power);
            b=b->next;
        }
        a=a->next;
    }
    a=head->next;
    for(int i=0; i<num; i++) //合并同类项
    {
        if(a->coefficient==0)
        {
            a=a->next;
            continue;
        }
        b=a->next;
        for(int j=i+1; j<num; j++)
        {
            if(b->power!=a->power)
                break;
            a->coefficient+=b->coefficient;
            b->coefficient=0;
            b=b->next;
        }
        a=a->next;
    }
    int newnum=0;
    a=head->next;
    tail=a;
    Xiang *p=head->next;
    for(int i=0; i<num; i++)//去0 把利用已有的结构 还是改数非零的前移最后尾结点提前
    {
        if(a->coefficient!=0)
        {
            p->coefficient=a->coefficient;
            p->power=a->power;
            tail=p;
            p=p->next;
            newnum++;
        }
        a=a->next;
    }
    tail->next=NULL;
    num=newnum;
}

polynomial polynomial::qiuhe(polynomial p1,polynomial p2)
{
    polynomial ans;
    Xiang *p;
    p=p1.head->next;
    for(int i=0; i<p1.num; i++)
        ans.addXiang(p->coefficient,p->power),p=p->next;
    p=p2.head->next;
    for(int i=0; i<p2.num; i++)
        ans.addXiang(p->coefficient,p->power),p=p->next;
    ans.sort();
    return ans;
}

polynomial polynomial::qiucha(polynomial p1,polynomial p2)
{
    polynomial ans;
    Xiang *p;
    p=p1.head->next;
    for(int i=0; i<p1.num; i++)
        ans.addXiang(p->coefficient,p->power),p=p->next;
    p=p2.head->next;
    for(int i=0; i<p2.num; i++)
        ans.addXiang(-p->coefficient,p->power),p=p->next;
    ans.sort();
    return ans;
}

polynomial polynomial::chengji(polynomial p1,polynomial p2)
{
    polynomial ans;
    Xiang *p,*q;
    q=p2.head->next;
    for(int i=0; i<p2.num; i++)
    {
        p=p1.head->next;
        for(int j=0; j<p1.num; j++)
        {
            ans.addXiang(p->coefficient*q->coefficient,p->power+q->power);
            p=p->next;
        }
        q=q->next;
        ans.sort();
    }
    return ans;
}

polynomial polynomial:: operator+(polynomial p2)
{
    polynomial p1;
    return p1.qiuhe(*this,p2);
}

polynomial polynomial:: operator-(polynomial p2)
{
    polynomial p1;
    return p1.qiucha(*this,p2);
}

polynomial polynomial:: operator*(polynomial p2)
{
    polynomial p1;
    return p1.chengji(*this,p2);
}
int main()
{
    polynomial p,ans,q;
    p.input();
    p.displayup();
    p.displaydown();
    p.addXiang(1,5);
    p.displayup();
    q.input();
    q.displayup();
    ans=p+q;
    ans.displayup();
    ans=p-q;
    ans.displayup();
    ans=p*q;
    ans.displayup();
    return 0;
}