測試-稀疏多項式C++鏈表的問題

稀疏多項式C++鏈表的問題

 #include<iostream>
using namespace std;

//約定稀疏多項式輸入升冪排列
template<class T>class Polynomial;
template<class T>ostream& operator<<(ostream& out, Polynomial<T>&a);

template<class T>
class Polynomial
{
private:
    class Term
    {
    public:
        T xishu;
        unsigned mi;
    };
    class Node
    {
    public:
        Term data;
        Node* next;
        Node(T x = 0, unsigned y = 0, Node* p = 0)
        {
            data.xishu = x;
            data.mi = y;
            next = p;//修改
        }
    };
public:
    Polynomial();
    void myfree();//釋放鏈表各節點,由於要重載+，所以設置這個函數
    Polynomial<T>& operator=(const Polynomial<T>&);
    Polynomial<T> operator+(const Polynomial<T>&);
    Polynomial<T> operator*(const Polynomial<T>&);
    void initial();
    friend ostream& operator<< <T> (ostream& out, Polynomial<T>& a);

private:
    int highestdigit;
    Node* first;
    int num;//用來判斷多項式有幾項,即鏈表節點數,在乘法運算裡也要用到
};
template<class T>
Polynomial<T>::Polynomial()
{
    first = new Node;
    num = 0;
    highestdigit = 0;
}

template<class T>
void Polynomial<T>::myfree()    //釋放鏈表各節點
{
    Node* p = first, *q;
    while (p)
    {
        q = p->next;
        delete p;
        p = q;
    }
}

template<class T>
Polynomial<T>& Polynomial<T>::operator=(const Polynomial<T>& second)
{
    highestdigit = second.highestdigit;
    num = second.num;
    Node* p1 = first, *p2 = second.first;

    while (p2->next)
    {
        p1->next = new Node();
        p1 = p1->next;
        p2 = p2->next;
        *p1 = *p2;
    }
    return *this;
}

template<class T>
Polynomial<T> Polynomial<T>::operator+(const Polynomial<T>& second)
{
    Polynomial<T> sum;
    Node* pa = first->next, *pb = second.first->next, *pc = sum.first;
    while (pa&&pb)
    {
        if (pa->data.mi == pb->data.mi)  // 指數相等時  
        {
            T x = pa->data.xishu + pb->data.xishu;
            if (x)     // 相加完的系數不為0時  
            {
                pc->next = new Node(x, pa->data.mi);
                pc = pc->next;
                ++sum.num;
                sum.highestdigit = pa->data.mi;
            }
            pa = pa->next;
            pb = pb->next;
        }
        else if (pa->data.mi > pb->data.mi){
            pc->next = new Node(pa->data.xishu, pa->data.mi);
            pc = pc->next;
            pa = pa->next;
            ++sum.num;
            sum.highestdigit = pa->data.mi;
        }
        else{
            pc->next = new Node(pb->data.xishu, pb->data.mi);
            pc = pc->next;
            pb = pb->next;
            ++sum.num;
            sum.highestdigit = pb->data.mi;
        }
    }
    while (pa){
        pc->next = new Node(pa->data.xishu, pa->data.mi);
        pc = pc->next;
        pa = pa->next;
        ++sum.num;
        sum.highestdigit = pa->data.mi;
    }
    while (pb){
        pc->next = new Node(pb->data.xishu, pb->data.mi);
        pc = pc->next;
        pb = pb->next;
        ++sum.num;
        sum.highestdigit = pb->data.mi;
    }
    return sum;
}
template<class T>
Polynomial<T> Polynomial<T>::operator*(const Polynomial<T>& second){
    Polynomial<T> multi;
    Node* pa = first->next, *pb = second.first->next;
    if (num >= second.num){ //拿項數多的那個鏈表乘以項數少的那個
        Polynomial<T> temp; 
        Node* pt;
        while(pb){          //pb是項數少的那個，
        pt = temp.first;
            while (pa){     //項數多的開始遍歷  
                pt->next = new Node(pa->data.xishu*pb->data.xishu, pa->data.mi*pb->data.mi);
                pt = pt->next;
                pa = pa->next;
            }
            multi= temp+multi;
            temp.myfree();
            temp.first = new Node();
            pb = pb->next;
        }
        return multi;
    }
    else{
        Polynomial<T> temp;
        Node* pt;
        while(pa){
            pt = temp.first;
            while (pb){
                pt->next = new Node(pa->data.xishu*pb->data.xishu, pa->data.mi*pb->data.mi);
                pt = pt->next;
                pb = pb->next;
            }
            multi = temp+multi;
            temp.myfree();
            temp.first = new Node();
            pa = pa->next;
        }
        return multi;
    }
}
template<class T>
void Polynomial<T>::initial()
{
    //釋放鏈表，保留頭節點
    Node* p = first->next, *q;
    while (p)
    {
        q = p->next;
        delete p;
        p = q;
    }
    p = first;

    T a;
    int b;
    num = 0; highestdigit = 0;//修改
    while (cin >> a&&a != 0 && cin >> b){   //輸入a=0時結束輸入
        if (b >= highestdigit) highestdigit = b;
        ++num;
        p->next = new Node(a, b);
        p = p->next;
    }
    fflush(stdin);//修改
}

template<class T>
ostream& operator<<(ostream& out, Polynomial<T>& a)
{
    Polynomial<T>::Node *p = a.first->next;

    if (p == NULL) return out;//修改

    if (p->data.xishu == 0)cout << endl;//修改
    else{
        if (p->data.xishu != 1)
            out << p->data.xishu << "x^" << p->data.mi;
        else    out << "x^" << p->data.mi;
    }
    p = p->next;
    while (p)
    {
        out << '+';
        if (p->data.xishu != 1)
            out << p->data.xishu << "x^" << p->data.mi;
        else    out << "x^" << p->data.mi;
        p = p->next;
    }
    return out;
}

測試代碼：

#include "Polynomial.h"
#include
using namespace std;
int main(){
Polynomial a, b, c,d;
a.initial();
cout << "a= " << a << endl;
b.initial();
cout << "b=" << b << endl;
c = a + b;
cout << "c=" << c << endl;
d=a*b;
cout<<"d="<<d<<end;
a.myfree();
b.myfree();
c.myfree();
d.myfree();
return 0;
}

最佳回答：

更正項少+項多時的錯誤：

#include<iostream>
using namespace std;

//約定稀疏多項式輸入升冪排列
template<class T>class Polynomial;
template<class T>ostream& operator<<(ostream& out, Polynomial<T>&a);

template<class T>
class Polynomial
{
private:
    class Term
    {
    public:
        T xishu;
        int mi;
    };
    class Node
    {
    public:
        Term data;
        Node* next;
        Node(T x = 0, unsigned y = 0, Node* p = 0)
        {
            data.xishu = x;
            data.mi = y;
            next = p;//修改
        }
    };
public:
    Polynomial();
    void myfree();//釋放鏈表所有各節點
    Polynomial<T>& operator=(const Polynomial<T>&);
    Polynomial<T> operator+(const Polynomial<T>&);
    Polynomial<T> operator*(const Polynomial<T>&);
    void initial();
    friend ostream& operator<< <T> (ostream& out, Polynomial<T>& a);

private:
    int highestdigit;
    Node* first;
    int num;//用來判斷多項式有幾項,即鏈表節點數,在乘法運算裡也要用到
};
template<class T>
Polynomial<T>::Polynomial()
{
    first = new Node;
    num = 0;
    highestdigit = 0;
}

template<class T>
void Polynomial<T>::myfree()    //釋放鏈表所有節點
{
    Node* p = first, *q;
    while (p)
    {
        q = p->next;
        delete p;
        p = q;
    }
    first=NULL;//修改
    num = 0; highestdigit = 0;//修改
}

template<class T>
Polynomial<T>& Polynomial<T>::operator=(const Polynomial<T>& second)
{
    myfree();
    highestdigit = second.highestdigit;
    num = second.num;
    first = second.first;

    return *this;
}

template<class T>
Polynomial<T> Polynomial<T>::operator+(const Polynomial<T>& second)
{
    Polynomial<T> sum;
    Node* pa = first->next, *pb = second.first->next, *pc = sum.first;
    while (pa&&pb)
    {
        if (pa->data.mi == pb->data.mi)  // 指數相等時  
        {
            T x = pa->data.xishu + pb->data.xishu;
            if (x)     // 相加完的系數不為0時  
            {
                pc->next = new Node(x, pa->data.mi);
                pc = pc->next;
                ++sum.num;
                if(sum.highestdigit<pa->data.mi) sum.highestdigit = pa->data.mi;
            }
            pa = pa->next;
            pb = pb->next;
        }
        else if (pa->data.mi > pb->data.mi){
            pc->next = new Node(pa->data.xishu, pa->data.mi);
            if(sum.highestdigit<pa->data.mi) sum.highestdigit = pa->data.mi;
            ++sum.num;
            pc = pc->next;
            pa = pa->next;
        }
        else{
            pc->next = new Node(pb->data.xishu, pb->data.mi);
            ++sum.num;
            if(sum.highestdigit<pb->data.mi) sum.highestdigit = pb->data.mi;
            pc = pc->next;
            pb = pb->next;
        }
    }
    while (pa){
        pc->next = new Node(pa->data.xishu, pa->data.mi);
        ++sum.num;
        if(sum.highestdigit<pa->data.mi) sum.highestdigit = pa->data.mi;
        pc = pc->next;
        pa = pa->next;
    }
    while (pb){
        pc->next = new Node(pb->data.xishu, pb->data.mi);
        ++sum.num;
        if(sum.highestdigit<pb->data.mi) sum.highestdigit = pb->data.mi;
        pc = pc->next;
        pb = pb->next;
    }
    return sum;
}
template<class T>
Polynomial<T> Polynomial<T>::operator*(const Polynomial<T>& second){
    Polynomial<T> multi, temp;
    Node* pa = first->next, *pb = second.first->next, * pt;

    if (num >= second.num){ //拿項數多的那個鏈表乘以項數少的那個
        while(pb){          //pb是項數少的那個，
            pt = temp.first;
            while (pa){     //項數多的開始遍歷  
                pt->next = new Node(pa->data.xishu*pb->data.xishu, pa->data.mi+pb->data.mi);//修改
                temp.num++;//修改
                if( temp.highestdigit<pt->next->data.mi ) temp.highestdigit=pt->next->data.mi;//修改
                pt = pt->next;
                pa = pa->next;
            }
            multi= temp+multi;
            temp.myfree();
            temp.first = new Node();
            pa = first->next;
            pb = pb->next;
        }
    }
    else{
        while(pa){
            pt = temp.first;
            while (pb){
                pt->next = new Node(pa->data.xishu*pb->data.xishu, pa->data.mi+pb->data.mi);//修改
                temp.num++;//修改
                if( temp.highestdigit<pt->next->data.mi ) temp.highestdigit=pt->next->data.mi;//修改
                pt = pt->next;
                pb = pb->next;
            }
            multi = temp+multi;
            temp.myfree();
            temp.first = new Node();
            pb = second.first->next;//修改
            pa = pa->next;
        }
    }
    return multi;
}
template<class T>
void Polynomial<T>::initial()
{
    //釋放鏈表，保留頭節點
    Node* p = first->next, *q;
    while (p)
    {
        q = p->next;
        delete p;
        p = q;
    }
    first->next=NULL;//修改
    p = first;

    T a;
    int b;
    num = 0; highestdigit = 0;//修改
    while (cin >> a&&a != 0 && cin >> b){   //輸入a=0時結束輸入
        if (b >= highestdigit) highestdigit = b;
        ++num;
        p->next = new Node(a, b);
        p = p->next;
    }
    fflush(stdin);//修改
}

template<class T>
ostream& operator<<(ostream& out, Polynomial<T>& a)
{
    Polynomial<T>::Node *p = a.first->next;

    if (p == NULL) return out;//修改

    if (p->data.xishu == 0)cout << endl;//修改
    else{
        if (p->data.xishu != 1)
            out << p->data.xishu << "x^" << p->data.mi;
        else    out << "x^" << p->data.mi;
    }
    p = p->next;
    while (p)
    {
        out << '+';
        if (p->data.xishu != 1)
            out << p->data.xishu << "x^" << p->data.mi;
        else    out << "x^" << p->data.mi;
        p = p->next;
    }
    return out;
}

int main(){
    Polynomial<int> a, b, c,d;
    a.initial();
    cout << "a= " << a << endl;
    b.initial();
    cout << "b=" << b << endl;
    c = a + b;
    cout << "c=" << c << endl;
    d=a*b;
    cout<<"d="<<d<<endl;
    a.myfree();
    b.myfree();
    c.myfree();
    d.myfree();
    return 0;
} 

運行結果：