c++-稀疏多项式C++链表的问题

问题描述

稀疏多项式C++链表的问题 
 #include<iostream>

using namespace std;
#ifndef POLYNOMIAL_H
#define POLYNOMIAL_H
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;
            Node* next = p;
        }
    };
public:
    Polynomial();
    ~Polynomial();
    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();
    first->next = new Node();
    num = 0;
    highestdigit = 0;
}
template<class T>
Polynomial<T>::~Polynomial(){
    Node* p = first;
    while (p){
        Node* q = p->next;
        delete p;
        p = q;
    }
}

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;
    int digit = 0, num = 0;
    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;
                ++num;
                digit = 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;
            ++num;
            digit = pa->data.mi;
        }
        else{
            pc->next = new Node(pb->data.xishu, pb->data.mi);
            pc = pc->next;
            pb = pb->next;
            ++num;
            digit = pb->data.mi;
        }
    }
    while (pa){
        pc->next = new Node(pa->data.xishu, pa->data.mi);
        pc = pc->next;
        pa = pa->next;
        ++num;
        digit = pa->data.mi;
    }
    while (pb){
        pc->next = new Node(pb->data.xishu, pb->data.mi);
        pc = pc->next;
        pb = pb->next;
        ++num;
        digit = pb->data.mi;
    }
    sum.num = num;
    sum.highestdigit = digit;
    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>* p1 = new Polynomial<T>[second.num];
        Node **p2 = new Node*[second.num];
        for (int i = 0; i < second.num; ++i){
            while (pa){
                if (pa->next == 0){
                    p1[i].highestdigit = pa->data.mi*pb->data.mi;
                    p1[i].num = num;
                }
                p2[i] = p1[i].first;
                p2[i]->next = new Node(pa->data.xishu*pb->data.xishu, pa->data.mi*pb->data.mi);
                p2[i] = p2[i]->next;
                pa = pa->next;
            }
            pb = pb->next;
            multi = multi + p1[i];
        }
        return multi;
    }
    else{
        Polynomial<T>* p1 = new Polynomial<T>[num];
        Node **p2 = new Node*[num];
        for (int i = 0; i < num; ++i){
            while (pb){
                if(pb->next == 0){
                    p1[i].highestdigit = pa->data.mi*pb->data.mi;
                    p1[i].num = num;
                }
                p2[i] = p1[i].first;
                p2[i]->next = new Node(pb->data.xishu*pa->data.xishu, pb->data.mi*pa->data.mi);
                p2[i] = p2[i]->next;
                pb = pb->next;
            }
            pa = pa->next;
            multi = multi + p1[i];
        }
        return multi;
    }
}

template<class T>
void Polynomial<T>::initial(){
    T a;
    Node* p = first;
    unsigned b, high=0;
    while (cin >> a&&a!=0&&cin>>b){   //输入a=0时结束输入
        if (b >= high)high= b;
        ++num;
        p->next = new Node(a, b);
        p = p->next;
    }
    highestdigit = high;
}
template<class T>
ostream& operator<<(ostream& out, Polynomial<T>& a){
        Polynomial<T>::Node *p = a.first->next;
        if (p->data.xishu == 0)cout << 0 << 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;
    }
    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>* p1 = new Polynomial<T>[second.num];
        Node **p2 = new Node*[second.num];
        for (int i = 0; i < second.num; ++i){
            while (pa){
                if (pa->next == 0){
                    p1[i].highestdigit = pa->data.mi*pb->data.mi;
                    p1[i].num = num;
                }
                p2[i] = p1[i].first;
                p2[i]->next = new Node(pa->data.xishu*pb->data.xishu, pa->data.mi*pb->data.mi);
                p2[i] = p2[i]->next;
                pa = pa->next;
            }
            pb = pb->next;
            multi = multi + p1[i];
        }
        return multi;
    }
    else{
        Polynomial<T>* p1 = new Polynomial<T>[num];
        Node **p2 = new Node*[num];
        for (int i = 0; i < num; ++i){
            while (pb){
                if(pb->next == 0){
                    p1[i].highestdigit = pa->data.mi*pb->data.mi;
                    p1[i].num = num;
                }
                p2[i] = p1[i].first;
                p2[i]->next = new Node(pb->data.xishu*pa->data.xishu, pb->data.mi*pa->data.mi);
                p2[i] = p2[i]->next;
                pb = pb->next;
            }
            pa = pa->next;
            multi = multi + p1[i];
        }
        return multi;
    }
}
#endif

测试代码如下：
#include "Polynomial.h"
#include<iostream>
using namespace std;
int main(){
    Polynomial<int> a, b, c;
    a.initial();
    cout << a <<endl;
    b.initial();
    cout << b << endl;
    cout << a + b << endl;
    return 0;
}
看了好久好久了啊，每次输出a+b都是0

解决方案

删除了你的类析构函数，链表节点的释放改为成员函数myfree()来实现。
这样在+重载函数返回时不会自动释放链表。

 #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>& second);
    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>
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;
}

int main(){
    Polynomial<int> a,b, c;

    a.initial();
    cout <<"a= "<< a <<endl;

    b.initial();
    cout <<"b="<< b << endl;

    c=a+b;
    cout << "c="<< c << endl;

    a.myfree();
    b.myfree();
    c.myfree();

    return 0;
}

运行结果：

解决方案二：

多项式相加链表

解决方案三：

是不是拷贝不全？编译就没通过。
T xishu;
T是哪来的？

解决方案四：

#include
using namespace std;
#ifndef POLYNOMIAL_H
#define POLYNOMIAL_H
templateclass Polynomial;
templateostream& operator<<(ostream& out, Polynomial&a );

template
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;
Node* next = p;
}
};
public:
Polynomial();
~Polynomial();
Polynomial operator+(const Polynomial&);
Polynomial operator*(const Polynomial&);
void initial();
friend ostream& operator<< (ostream& out, Polynomial& a);

private:
int highestdigit;
Node* first;
int num;//用来判断多项式有几项,即链表节点数,在乘法运算里也要用到
};
template
Polynomial::Polynomial(){
first = new Node();
first->next = new Node();
num = 0;
highestdigit = 0;
}
template
Polynomial::~Polynomial(){
Node* p = first;
while (p){
Node* q = p->next;
delete p;
p = q;
}
}

template
Polynomial Polynomial::operator+(const Polynomial& second){
Polynomial sum;
Node* pa = first->next, *pb = second.first->next, *pc = sum.first;
int digit = 0, num = 0;
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;
++num;
digit = 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;
++num;
digit = pa->data.mi;
}
else{
pc->next = new Node(pb->data.xishu, pb->data.mi);
pc = pc->next;
pb = pb->next;
++num;
digit = pb->data.mi;
}
}
while (pa){
pc->next = new Node(pa->data.xishu, pa->data.mi);
pc = pc->next;
pa = pa->next;
++num;
digit = pa->data.mi;
}
while (pb){
pc->next = new Node(pb->data.xishu, pb->data.mi);
pc = pc->next;
pb = pb->next;
++num;
digit = pb->data.mi;
}

sum.num = num;
sum.highestdigit = digit;
return sum;

}

template
Polynomial Polynomial::operator*(const Polynomial& second){
Polynomial multi;
Node* pa = first->next, pb = second.first->next;
if (num >=second.num){
Polynomial p1 = new Polynomial[second.num];

Node **p2 = new Node*[second.num];
for (int i = 0; i < second.num; ++i){
while (pa){
if (pa->next == 0){
p1[i].highestdigit = pa->data.mi*pb->data.mi;
p1[i].num = num;
}
p2[i] = p1[i].first;
p2[i]->next = new Node(pa->data.xishu*pb->data.xishu, pa->data.mi*pb->data.mi);
p2[i] = p2[i]->next;
pa = pa->next;
}
pb = pb->next;
multi = multi + p1[i];
}
return multi;
}
else{
Polynomial* p1 = new Polynomial[num];
Node **p2 = new Node*[num];
for (int i = 0; i < num; ++i){
while (pb){
if(pb->next == 0){
p1[i].highestdigit = pa->data.mi*pb->data.mi;
p1[i].num = num;
}
p2[i] = p1[i].first;
p2[i]->next = new Node(pb->data.xishu*pa->data.xishu, pb->data.mi*pa->data.mi);
p2[i] = p2[i]->next;
pb = pb->next;
}
pa = pa->next;
multi = multi + p1[i];
}
return multi;
}
}

template
void Polynomial::initial(){
T a;
Node* p = first;
unsigned b, high=0;
while (cin >> a&&a!=0&&cin>>b){ //输入a=0时结束输入
if (b >= high)high= b;
++num;
p->next = new Node(a, b);
p = p->next;
}
highestdigit = high;
}
template
ostream& operator<<(ostream& out, Polynomial& a){
Polynomial::Node p = a.first->next;
if (p->data.xishu == 0)cout << 0 << 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;
}
template
Polynomial Polynomial::operator=(const Polynomial&second){
Node p = first->next;
while (p){
Node* q = p->next;
delete p;
p = q;
}
Node* p2 = second.first->next;
p = first;
while (p2){
p->next = new Node(p2->data.xishu, p2->data.mi);
p = p->next;
p2 = p2->next;
}
return *this;
}

#endif

解决方案五：

#include
using namespace std;
#ifndef POLYNOMIAL_H
#define POLYNOMIAL_H
templateclass Polynomial;
templateostream& operator<<(ostream& out, Polynomial&a );

template
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;
Node* next = p;
}
};
public:
Polynomial();
~Polynomial();
Polynomial operator+(const Polynomial&);
Polynomial operator*(const Polynomial&);
void initial();
friend ostream& operator<< (ostream& out, Polynomial& a);

private:
int highestdigit;
Node* first;
int num;//用来判断多项式有几项,即链表节点数,在乘法运算里也要用到
};
template
Polynomial::Polynomial(){
first = new Node();
first->next = new Node();
num = 0;
highestdigit = 0;
}
template
Polynomial::~Polynomial(){
Node* p = first;
while (p){
Node* q = p->next;
delete p;
p = q;
}
}

template
Polynomial Polynomial::operator+(const Polynomial& second){
Polynomial sum;
Node* pa = first->next, *pb = second.first->next, *pc = sum.first;
int digit = 0, num = 0;
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;
++num;
digit = 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;
++num;
digit = pa->data.mi;
}
else{
pc->next = new Node(pb->data.xishu, pb->data.mi);
pc = pc->next;
pb = pb->next;
++num;
digit = pb->data.mi;
}
}
while (pa){
pc->next = new Node(pa->data.xishu, pa->data.mi);
pc = pc->next;
pa = pa->next;
++num;
digit = pa->data.mi;
}
while (pb){
pc->next = new Node(pb->data.xishu, pb->data.mi);
pc = pc->next;
pb = pb->next;
++num;
digit = pb->data.mi;
}

sum.num = num;
sum.highestdigit = digit;
return sum;

}

template
Polynomial Polynomial::operator*(const Polynomial& second){
Polynomial multi;
Node* pa = first->next, pb = second.first->next;
if (num >=second.num){
Polynomial p1 = new Polynomial[second.num];

Node **p2 = new Node*[second.num];
for (int i = 0; i < second.num; ++i){
while (pa){
if (pa->next == 0){
p1[i].highestdigit = pa->data.mi*pb->data.mi;
p1[i].num = num;
}
p2[i] = p1[i].first;
p2[i]->next = new Node(pa->data.xishu*pb->data.xishu, pa->data.mi*pb->data.mi);
p2[i] = p2[i]->next;
pa = pa->next;
}
pb = pb->next;
multi = multi + p1[i];
}
return multi;
}
else{
Polynomial* p1 = new Polynomial[num];
Node **p2 = new Node*[num];
for (int i = 0; i < num; ++i){
while (pb){
if(pb->next == 0){
p1[i].highestdigit = pa->data.mi*pb->data.mi;
p1[i].num = num;
}
p2[i] = p1[i].first;
p2[i]->next = new Node(pb->data.xishu*pa->data.xishu, pb->data.mi*pa->data.mi);
p2[i] = p2[i]->next;
pb = pb->next;
}
pa = pa->next;
multi = multi + p1[i];
}
return multi;
}
}

template
void Polynomial::initial(){
T a;
Node* p = first;
unsigned b, high=0;
while (cin >> a&&a!=0&&cin>>b){ //输入a=0时结束输入
if (b >= high)high= b;
++num;
p->next = new Node(a, b);
p = p->next;
}
highestdigit = high;
}
template
ostream& operator<<(ostream& out, Polynomial& a){
Polynomial::Node p = a.first->next;
if (p->data.xishu == 0)cout << 0 << 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;
}
template
Polynomial Polynomial::operator=(const Polynomial&second){
Node p = first->next;
while (p){
Node* q = p->next;
delete p;
p = q;
}
Node* p2 = second.first->next;
p = first;
while (p2){
p->next = new Node(p2->data.xishu, p2->data.mi);
p = p->next;
p2 = p2->next;
}
return *this;
}

#endif

解决方案六：

我这个事模板类，但是复制粘贴代码的时候template粘贴不出来

解决方案七：

把代码放到代码片里。工具栏里有插入代码片。
就像下面这样：

 void Polynomial::initial(){
T a;
Node* p = first;
unsigned b, high=0;
while (cin >> a&&a!=0&&cin>>b){ //输入a=0时结束输入
if (b >= high)high= b;
++num;
p->next = new Node(a, b);
p = p->next;
}
highestdigit = high;
}

解决方案八：

#include
using namespace std;
#ifndef POLYNOMIAL_H
#define POLYNOMIAL_H
templateclass Polynomial;
templateostream& operator<<(ostream& out, Polynomial&a );

template
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;
Node* next = p;
}
};
public:
Polynomial();
~Polynomial();
Polynomial operator+(const Polynomial&);
Polynomial operator*(const Polynomial&);
void initial();
friend ostream& operator<< (ostream& out, Polynomial& a);

private:
int highestdigit;
Node* first;
int num;//用来判断多项式有几项,即链表节点数,在乘法运算里也要用到
};
template
Polynomial::Polynomial(){
first = new Node();
first->next = new Node();
num = 0;
highestdigit = 0;
}
template
Polynomial::~Polynomial(){
Node* p = first;
while (p){
Node* q = p->next;
delete p;
p = q;
}
}

template
Polynomial Polynomial::operator+(const Polynomial& second){
Polynomial sum;
Node* pa = first->next, *pb = second.first->next, *pc = sum.first;
int digit = 0, num = 0;
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;
++num;
digit = 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;
++num;
digit = pa->data.mi;
}
else{
pc->next = new Node(pb->data.xishu, pb->data.mi);
pc = pc->next;
pb = pb->next;
++num;
digit = pb->data.mi;
}
}
while (pa){
pc->next = new Node(pa->data.xishu, pa->data.mi);
pc = pc->next;
pa = pa->next;
++num;
digit = pa->data.mi;
}
while (pb){
pc->next = new Node(pb->data.xishu, pb->data.mi);
pc = pc->next;
pb = pb->next;
++num;
digit = pb->data.mi;
}

sum.num = num;
sum.highestdigit = digit;
return sum;

}

template
Polynomial Polynomial::operator*(const Polynomial& second){
Polynomial multi;
Node* pa = first->next, pb = second.first->next;
if (num >=second.num){
Polynomial p1 = new Polynomial[second.num];

Node **p2 = new Node*[second.num];
for (int i = 0; i < second.num; ++i){
while (pa){
if (pa->next == 0){
p1[i].highestdigit = pa->data.mi*pb->data.mi;
p1[i].num = num;
}
p2[i] = p1[i].first;
p2[i]->next = new Node(pa->data.xishu*pb->data.xishu, pa->data.mi*pb->data.mi);
p2[i] = p2[i]->next;
pa = pa->next;
}
pb = pb->next;
multi = multi + p1[i];
}
return multi;
}
else{
Polynomial* p1 = new Polynomial[num];
Node **p2 = new Node*[num];
for (int i = 0; i < num; ++i){
while (pb){
if(pb->next == 0){
p1[i].highestdigit = pa->data.mi*pb->data.mi;
p1[i].num = num;
}
p2[i] = p1[i].first;
p2[i]->next = new Node(pb->data.xishu*pa->data.xishu, pb->data.mi*pa->data.mi);
p2[i] = p2[i]->next;
pb = pb->next;
}
pa = pa->next;
multi = multi + p1[i];
}
return multi;
}
}

template
void Polynomial::initial(){
T a;
Node* p = first;
unsigned b, high=0;
while (cin >> a&&a!=0&&cin>>b){ //输入a=0时结束输入
if (b >= high)high= b;
++num;
p->next = new Node(a, b);
p = p->next;
}
highestdigit = high;
}
template
ostream& operator<<(ostream& out, Polynomial& a){
Polynomial::Node p = a.first->next;
if (p->data.xishu == 0)cout << 0 << 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;
}
template
Polynomial Polynomial::operator=(const Polynomial&second){
Node p = first->next;
while (p){
Node* q = p->next;
delete p;
p = q;
}
Node* p2 = second.first->next;
p = first;
while (p2){
p->next = new Node(p2->data.xishu, p2->data.mi);
p = p->next;
p2 = p2->next;
}
return *this;
}

#endif

 #include "Polynomial.h"
#include<iostream>
using namespace std;
int main(){
    Polynomial<int> a, b, c;
    a.initial();
    cout << a <<endl;
    b.initial();
    cout << b << endl;
    cout << a + b << endl;
    return 0;
}

解决方案九：

1、实现了a.initial()、<<重载、=重载
2、由于Polynomial模板类含有链表，则对象a、b的大小不同，a+b函数重载在返回sum时，sum被释放，无法得到和的返回值。
即含链表的类无法实现加法重载。因为和无法返回。
采用成员函数方法来实现的。

 #include<iostream>
using namespace std;
#ifndef POLYNOMIAL_H
#define POLYNOMIAL_H
//约定多项式输入降幂排列
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();
    ~Polynomial();
    void add(const Polynomial<T>& c1,const Polynomial<T>& c2);
    Polynomial<T>& operator=(const Polynomial<T>& second);
    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();
    //first->next = new Node();
    num = 0;
    highestdigit = 0;
}
template<class T>
Polynomial<T>::~Polynomial(){
    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;
}

//sum=c1+c2
template<class T>
void Polynomial<T>::add(const Polynomial<T>& c1,const Polynomial<T>& c2)
{
    Node* pa = c1.first->next, *pb = c2.first->next, *pc = first;
    highestdigit = 0, num = 0;
    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;
                ++num;
                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;
            ++num;
            highestdigit = pa->data.mi;
        }
        else{
            pc->next = new Node(pb->data.xishu, pb->data.mi);
            pc = pc->next;
            pb = pb->next;
            ++num;
            highestdigit = pb->data.mi;
        }
    }
    while (pa){
        pc->next = new Node(pa->data.xishu, pa->data.mi);
        pc = pc->next;
        pa = pa->next;
        ++num;
        highestdigit = pa->data.mi;
    }
    while (pb){
        pc->next = new Node(pb->data.xishu, pb->data.mi);
        pc = pc->next;
        pb = pb->next;
        ++num;
        highestdigit = pb->data.mi;
    }
}

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>* p1 = new Polynomial<T>[second.num];
        Node **p2 = new Node*[second.num];
        for (int i = 0; i < second.num; ++i){
            while (pa){
                if (pa->next == 0){
                    p1[i].highestdigit = pa->data.mi*pb->data.mi;
                    p1[i].num = num;
                }
                p2[i] = p1[i].first;
                p2[i]->next = new Node(pa->data.xishu*pb->data.xishu, pa->data.mi*pb->data.mi);
                p2[i] = p2[i]->next;
                pa = pa->next;
            }
            pb = pb->next;
            multi = multi + p1[i];
        }
        return multi;
    }
    else{
        Polynomial<T>* p1 = new Polynomial<T>[num];
        Node **p2 = new Node*[num];
        for (int i = 0; i < num; ++i){
            while (pb){
                if(pb->next == 0){
                    p1[i].highestdigit = pa->data.mi*pb->data.mi;
                    p1[i].num = num;
                }
                p2[i] = p1[i].first;
                p2[i]->next = new Node(pb->data.xishu*pa->data.xishu, pb->data.mi*pa->data.mi);
                p2[i] = p2[i]->next;
                pb = pb->next;
            }
            pa = pa->next;
            multi = multi + p1[i];
        }
        return multi;
    }
}

template<class T>
void Polynomial<T>::initial()
{
    T a;
    Node* p = first;
    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;
}

#endif

int main(){
    Polynomial<int> a,b, c;

    a.initial();
    cout <<"a= "<< a <<endl;

    b.initial();
    cout <<"b="<< b << endl;

    c=a;
    cout << "c="<< c << endl;

    c.add(a,b);
    cout << "c="<< c << endl;
    return 0;
}

解决方案十：

运行结果：

时间： 2024-10-29 19:46:01

c++-稀疏多项式C++链表的问题的相关文章

测试-稀疏多项式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 Poly

数据结构 单链表-关于稀疏多项式的创建

问题描述 关于稀疏多项式的创建 算法描述如图,但是不知道这个q的作用,求大神详细解答一下. 解决方案 i=0时: pre=P;//此时pre指针指向头结点 q=P->next;//q被赋值成NULL while(....)//不满足 s->next=q;//将新插入的节点的next指针指向q,也就是被赋值成NULL了 pre->next=s;//让头结点的next指针指向了新插入的节点s i=1时: pre=P;//此时pre指针还是指向头结点 q=P->next;//q指向了第一

c语言-一元稀疏多项式计算器

问题描述 一元稀疏多项式计算器 用c语言写一个一元稀疏多项式的计算器,加减乘除,怎么写?还要用到节点什么的,是数据结构的题目 解决方案 http://wenku.baidu.com/link?url=AM6e0AkKQSuxfiL02xfKyEc-_PHhbKzn8Bo9ltCbZgk0E92ShNgAq-Al1Dvc1QzELF1zuVp5IRWaZqXB1Y5grxcGmgeBU3vW6nMlKLVX4aahttp://download.csdn.net/detail/ganshaolong

数据结构实践项目——链表

本组项目针对<数据结构基础系列(2):线性表>课程第8-15节 8. 线性表的链式存储 9. 建立单链表 10. 单链表基本操作的实现 11. 单链表应用举例 12. 双链表 13. 循环链表 14. 线性表的应用 15. 有序表 [项目1 - 建立单链表] 定义单链表存储结构,用头插法和尾插法建立单链表,并显示建立好以后的结果. 请在下面代码的基础上开展工作: #include <stdio.h> #include <malloc.h> typedef int Ele

java类的问题-java数据结构，线性表操作，C(X)=A(X)+B(X)多项式想加

问题描述 java数据结构,线性表操作,C(X)=A(X)+B(X)多项式想加 C(X)=A(X)+B(X)多项式想加.PolySLinkedList类增加C(X)=A(X)+B(X)多项式想加功能,算法实现不依赖于深拷贝,将A和B两条多项式单链表中的所以结点相加合并到新建的C多项式单链表,不改变A和B多项式单链表

《数据结构与算法 C语言版》—— 2.3线性表的链式表示与实现

2.3线性表的链式表示与实现 线性表的顺序存储结构的特点是逻辑关系上相邻的两个元素在物理位置上也相邻,因此可以随机存取表中任一元素,它的存储位置可用一个简单.直观的公式来表示.然而,从另一方面来看,这个特点也造成了这种存储结构的弱点:在作插入或删除操作时,需移动大量元素.本节我们将讨论线性表的另一种表示方法--链式存储结构,其特点是用一组地址任意的存储单元存储线性表中的数据元素.由于它不要求逻辑上相邻的元素在物理位置上也相邻,因此它没有顺序存储结构所具有的弱点,但同时也失去了顺序表随机存取的特点

虚拟键盘-JavaScript怎样实现咋键盘上按下不同的键，页面上不同的div调用同一个css样式

问题描述 JavaScript怎样实现咋键盘上按下不同的键,页面上不同的div调用同一个css样式 这是页面上的一个虚拟键盘,我想实现的是当我在电脑的键盘上按键后,虚拟键盘上的相对应的键会有不同的显示效果(调用一个css)(虚拟键盘上的每一个小键都是一个图片),就是当我按下不同的按键,页面上相对的键所在的div就会调用同一个css 解决方案 虚拟键盘上的每个控件都增加keycode属性,然后document.onkeydown获取时间的keycode属性后获取控件添加个样式,过100ms再移除什

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

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

[单链表]多项式乘法

<数据结构与算法分析 C语言描述>表,栈与队列部分课后习题 //Code by Pnig0s1992 //Date:2012,3,22 #include <stdio.h> #include "Header.h" void MultPolynomial(LinkList Py1,LinkList Py2,LinkList LinkRc); void PrintfPolynomial(LinkList LinkRs); int main(int argc,char