Poly output error - linked list

Question

My current output is giving me an error and I do not understand why. If someone could guide me as to why it does it would be greatly appreciated. I am able to add two polynomials together but when I get the output I get a segmentation fault after removing a space from the output operator. I do not know why this is. I am also using codeblocks if that helps.

main.cpp

#include <iostream>
#include "poly.h"
using namespace std;
int main ()
{

int x1[] = {1 , 0 , 3 , 4 , 5};
int x2[] = {3 , 2};

polynomial p1(x1 , 4);
polynomial p2(x2 , 1);
polynomial p3(5);
polynomial p4;
polynomial result;

result = 6;


cout << " p1 = " << p1 << endl ;
cout << " p2 = " << p2 << endl ;
cout << " p3 = " << p3 << endl ;
cout << " p4 = " << p4 << endl ;
cout << " result = " << result << endl << endl ;

result = p1 + p2 ;
cout << " p1 + p2 = " << result << endl ;

poly.h

#include <iostream>
using namespace std;

class polynomial
{

    struct node
    {
        int coefficient ;
        node * link ;
    };

public:
polynomial();
polynomial(const polynomial&);
polynomial(int* ,int);
polynomial(int);
~polynomial();


polynomial operator+(const polynomial&) const;
polynomial operator+(int) const;
const polynomial& operator=(const polynomial &);
const polynomial& operator=(int);

friend ostream& operator<<(ostream& outfile , const polynomial&);
friend polynomial operator+(int ,const polynomial&);

private:
node* head;
int degree;
};

poly.cpp

#include <iostream>
#include "poly.h"
using namespace std;

polynomial::polynomial()
{
    head = new node;
    head->coefficient = 0;
    head->link = NULL;
    degree = -1;
};

polynomial::polynomial(const polynomial& copy)
{
    if(this != &copy)
    {
        delete[] head;
        head = copy.head;
    }
};

polynomial::polynomial(int * p, int degree)
{
    this->degree = degree;
    head = new node;
    head->coefficient = p[0];
    head->link = NULL;

    for(int x=1;x<degree;x++)
    {
        node* temp;
        temp = new node;
        temp->coefficient = p[x];
        temp->link = head;
        head = temp;
    }

    node* temp;
    temp = new node;
    temp->coefficient = p[degree];
    temp->link = head;
    head = temp;
};

polynomial::polynomial(int s)
{
    degree = 0;
    head = new node;
    head->coefficient = s;
    head->link = NULL;
};

polynomial::~polynomial()
{
    node* temp = head;
    node* current = head;
    while(current != NULL)
    {
        current = current->link;
        delete temp;
        temp = current;
        if (current == NULL || current == NULL)
            break;
    }
};

polynomial polynomial::operator+(const polynomial& rhs) const
{
    polynomial hold;
    polynomial tempLhs;
    polynomial tempRhs = rhs;

    tempLhs.degree = degree;
    tempRhs.degree = rhs.degree;
    hold.degree;
    int tempDegree;

    tempLhs.head = new node;
    tempRhs.head = new node;
    hold.head = new node;

    for(int x=0;x<tempDegree+1;x++)
    {
        node* temp;
        temp = new node;
        temp->coefficient = 0;
        temp->link = hold.head;
        hold.head = temp;
    }

    tempLhs.head = head;
    tempRhs.head = rhs.head;

    if(tempLhs.degree < tempRhs.degree)
    {
        tempDegree = tempLhs.degree;
        hold.degree = tempDegree;
        for(int x = (tempDegree-tempLhs.degree-1);x<tempDegree+1;x++)
        {
            node* temp;
            temp = new node;
            temp->coefficient = 0;
            temp->link = tempLhs.head;
            tempLhs.head = temp;
        }

    }
    else if(tempLhs.degree > tempRhs.degree)
    {
        tempDegree = tempLhs.degree;
        hold.degree = tempDegree;
        for(int x = (tempDegree-tempRhs.degree-1);x<tempDegree+1;x++)
        {
            node* temp;
            temp = new node;
            temp->coefficient = 0;
            temp->link = tempRhs.head;
            tempRhs.head = temp;
        }
    }
    else
    {
        tempDegree = tempRhs.degree = tempLhs.degree;
        hold.degree = tempDegree;
    }


    node* lhsCurrent = tempLhs.head;
    node* rhsCurrent = tempRhs.head;
    int tempArr[tempDegree];

    while(lhsCurrent != NULL && rhsCurrent != NULL)
    {
        for(int x=tempDegree;x>-1;x--)
        {
            tempArr[x]= lhsCurrent->coefficient + rhsCurrent->coefficient;
            lhsCurrent = lhsCurrent->link;
            rhsCurrent = rhsCurrent->link;
        }
    }

    polynomial use(tempArr, tempDegree);
    return use;
};

polynomial polynomial::operator+(int rhs) const
{
    polynomial temp = *this;

    return rhs+temp;
};

const polynomial& polynomial::operator=(const polynomial& rhs)
{
    cout << "doing = operator" << endl;
    degree = rhs.degree;

    if(this != &rhs)
    {
        delete[] head;
        head = rhs.head;
    }

    return *this;
};

const polynomial& polynomial::operator=(int rhs)
{
    degree = 0;
    head = new node;
    head->coefficient = rhs;
    head->link = NULL;
};

ostream& operator<<(ostream& out, const polynomial& rhs)
{
    out << "operator ";

    polynomial::node* temp = new polynomial::node;
    temp = rhs.head;

    while(temp != NULL)
    {
        out << temp->coefficient << " ";
        temp = temp->link;
        if(temp == NULL)
            break;
    }
    out << " ";
};

The output should be this

p1 = 5 x ^4 + x ^2 + 5 x + 4
p2 = 3 x + 2
p3 = 5
p4 = 0
result = 6
p1 + p2 = 5 x ^4 + x ^2 + 8 x + 6

I am getting this result but I just have to format it so that the degrees are represented correctly but my addition it coming out correctly I just need to adjust the output operator which is not the issue.

Whenever I run the program without

out << " ";

which is the second to last line of poly.cpp I get an error.

It says I have segmentation fault after line 215 which happens to be the last line of poly.cpp when the out<< is deleted from the code.

Answer 1

result = p1 + p2 ; 

invokes operator+ which is way too long to reproduce in full here, but

polynomial tempRhs = rhs;

invokes the copy constructor to create an Automatic variable that will go out of scope and die at the end of the function. Let's take a look at the copy constructor.

polynomial::polynomial(const polynomial& copy)
{
    if(this != &copy)
    {
        delete[] head;
        head = copy.head;
    }
};

This is almost completely wrong. Good on the Asker to realize they needed one, but this isn't helping. Let's break it down:

if(this != &copy) 

is hard to avoid. The copy constructor is invoked to make a new polynomial out of an existing polynomial. You have to work at copy-constructing yourself, so it's probably not worth testing for.

delete[] head;

head should be a single node, so delete[] is the wrong operator to use or you have a weird bug elsewhere I haven't reached yet. To delete a single item use delete. To delete an array of items, use delete[]

Next, this is a new object and head hasn't been assigned anything yet making this both unnecessary and fatal: this is trying to delete storage the program probably doesn't own and if it does own the block of storage, some other pointer is getting a very nasty surprise when it finds its memory gone.

head = copy.head; 

defeats the point of making a copy constructor because you are right back to the default behaviour of a copy constructor: Blindly copy all of the members without giving a thought to what is being copied. This doesn't copy the nodes, it copies the pointer to the head node, so now you have two objects pointing to the same node, and this is very bad. Modifying one copy modifies the other. Destroying one copy leave the other pointing at garbage memory, leaving you with a timebomb.

So getting back to

polynomial tempRhs = rhs;

tempRhs and rhs both point to the same list. tempRhs is going to reach the end of its scope, be destoyed, and take the shared list of nodes with it. When rhs is later destroyed it will also attempt to destroy the list of nodes. This is probably the crash the Asker is seeing since there isn't much program left to access the invalid memory in rhs and crash or go completely weird.

Let's fix the copy constructor

Recommendation 1: You need to iterate through the existing polynomial's nodes, make copies of them, and place the copies on head. If the linked list implementation has an insert function, this is the perfect time to use it. This leads to

Recommendation 2: Separate the linked list logic from the polynomial logic. Two reasons: 1) Why should a polynomial class no about more than just polynomials? The less class knows generally the more robust it is going to be. 2) This way you can test and debug them separately. When you know the linked list works, because you've tested the smurf out of it, polynomial contains an instance of the linked list class and trusts that the linked list works as advertised.

polynomial::polynomial(const polynomial& copy)
{
    node * from = copy.head; // copying from
    node ** to = &head; // pointer to where we want to copy to
    while (from != nullptr) // keep going until end of list. You did mark 
                            // the end of the list, didn't you?
    {
        *to = new node(*from); copy from into a new node and store it at to
        to = &(*to)->next; // advance to
        from = from.next; // advance from
    }
    *to = nullptr; // all done. Terminate list.
    degree = copy.degree; // update the degree
};

To unravel the secret of node ** to = &head; read Using pointers to remove item from singly-linked list We aren't removing an item, but the logic is exactly the same. As mentioned above, the superior way to do this is to build it into a linked list class and keep polynomial managing polynomials, not lists.

Alright! We can copy a polynomial now! All done, right?

Wrong.

Which brings us to recommendation 3: Don't write much code between testing. At most write a function. Then test the function until you are absolutely certain it works before writing any code that depends on that function. Do not write more code while you know you have a bug. Bugs feed off of and conceal one another. Bugs are bad. You never want any, but you especially don't want more than one.

polynomial operator+(const polynomial&) const;

returns by value. As it should. but

result = p1 + p2 ;

invokes the assignment operator, so now we have to go fix operator=. We'll fast forward through it because it has he same core problem as the copy constructor and can be fixed by applying the Copy and Swap Idiom. What is the copy-and-swap idiom? There's no point trying to re-explain something upvoted 1500 times, so click the link, read, and implement.

What we have been painstakingly exploring is known as the The Rule of Three. Now that The Rule of Three is implemented correctly we can start to address any other bugs in the code. It's freaking late where I am, so I'm stopping here.