merging linked lists

I'm trying to merge two linked lists, and I can get it to compile but there are run time errors where my program crashes. I don't get what is happening to where my program dies. I thought I looked over everything, but it might help to have someone else look over it too. I even commented everything out of the function Sum() so it was completely empty except for the return ret; (in hopes or narrowing the source down) and i still got a run time error, i have to be missing something simple. I did some searching but I only found mergesort() functions for things containing one element, and not multiple, or even containing a structure within the class. Anyone see something wrong? If you want to see the member functions just ask.

Code:

//add two linked classes POLY
POLY Sum(POLY one, POLY two)
{
    POLY ret;
    int deg1, deg2, high;
    double co1,co2;
    
    deg1 = one.degree();
    deg2 = two.degree();
    
    if(deg1 >= deg2){
        high = deg1;
        ret.ChangeDegree(deg1,0);
        ret.changecoefficient(one.coefficient(one.degree()),deg1);
    }
    else{
        high = deg2;
        ret.ChangeDegree(deg2,0);
        ret.changecoefficient(two.coefficient(two.degree()),deg2);
    }
    high--;
    
    for(high; high >= 0; high--){
        ret.append(one.coefficient(high)+two.coefficient(high),high);
    }
    return ret;  
}



class POLY //begin class POLY
{   
    private:
        struct node //begin struct node
        {
            int pow; //power
            double coeff; //coefficient
            node *link; //link
        }*t; //end struct node, node t
    public:
        POLY(); //default constructor
        POLY(const POLY&); //copy constructor
        ~POLY(); //destructor
        int degree(); //get highest degree
        void print(); //print polynomial
        double coefficient(int); //get coefficient of specified term
        void changecoefficient(double, int);
        void mult(double); //multiply polynomial by a constant
        
        void ChangeDegree(int,int); //change an exponent degree from one to another
        void append(double,int); //add another link to the list
}; //end class POLY

This isn't nearly enough information, but I like guessing: your ChangeDegree tries to access *t, but the default constructor doesn't provide any nodes in *t to access.

you can almost be certain that the problem has to do with some pointer arithmetic or something else related to dynamic memory allocation and use.

if you said the problem occurs even with the (single) function above commented out and just having a return statement in it, then all of the above code does no help in debugging for us. (as there is actually no real code in it).

if the program is not overly long, you should post all of your driver/user/main code as well as the implementation of the POLY class.

for a much quicker result in narrowing down your problem, you should debug it yourself. i will give an example. say i have the following (pseudocode) program:

Code:

function1
(
  statement1;
  statement2;
  statement3;
)

function2
(
  statement1a;
  statement2a;
  statement3a;
)

main
(
  statement1;
  statement2;
  function1();
  statement 3;
  function(2);
)

of course this isnt really anything. but lets pretend there is a bug in it that causes a runtime error. this is how i would debug it:

Code:

function1
(
  print "in function1";
  print "before statement1";
  statement1;
  print "after statement1";
  print "before statement2";
  statement2;
  print "after statement2";
  print "before statement3";
  statement3;
  print "after statement3";
  print "done function1";
)

function2
(
  print "in function2";
  print "before statement1a";
  statement1a;
  // etc...
  statement2a;
  statement3a;
  print "done function2";
)

main
(
  print "in main";
  statement1;
  statement2;
  print "calling function1";
  function1();
  print "done calling function1";
  // etc
  statement 3;
  function(2);
  print "done main";
)

i certainly dont want to type it all but i hope you get the idea. follow through your 'int main' function code putting print statements that give a visual check on what is and what isnt being reached. for example, if i get an error when running my code above and "done calling function1" is never printed, i know the problem is narrowed down to that single function (of course it can call others still). then debug that function more deeper and you will eventually find a line such as:

Code:

  print "before statementX";
  statementX;
  print "after statementX";

which at this point you know the single line that causes the problem. this algorithm is very efficient and is O(log n), where n is the number of statements in your code :P.

start with your 'main' function and put a print function halfway through. if it prints, then move the print statement half way between the print line and end of main function, etc.

Here is the entire code, the header and implementation file.

Code:

//HEADER class.h
#include <iostream>
using namespace std;

class POLY;

class POLY //begin class POLY
{   
    private:
        struct node //begin struct node
        {
            int pow; //power
            double coeff; //coefficient
            node *link; //link
        }*t; //end struct node, node t
    public:
    //PROJECT REQUIRE FUNCTIONS
        POLY(); //default constructor
        POLY(const POLY&); //copy constructor
        ~POLY(); //destructor
        int degree(); //get degree
        void print(); //print polynomial
        double coefficient(int); //get coefficient of specified term
        void changecoefficient(double, int);
        void mult(double); //multiply polynomial by a constant
        
    //EXTRA FUNCTIONS (NOT PROJECT REQUIRED)
        void ChangeDegree(int,int);
        void append(double,int);
}; //end class POLY

POLY::POLY() //being default constructor
{
    t = new node;
    t->pow = 0;
    t->coeff = 0.0;
    t->link = NULL;
} //end default constructor

POLY::~POLY() //destructor, delete all objects
{
    node *temp;
    if(t == NULL)
        return;
    while(t != NULL){
        temp = t->link;
        delete t;
        t = temp;
    }
} //end destructor

POLY::POLY(const POLY& copy) //being copy constructor
{
    POLY NewNode;
    NewNode = copy;
} //end copy constructor

int POLY::degree() //get degree
{
    return t->pow;
}

void POLY::print()
{
    node *temp;
    
    temp = t;
    do{
        if(temp->coeff != 0){
            cout<< temp->coeff <<"x^"<< temp->pow;
            if(temp->link != NULL) cout<<" + ";
        }
        temp = temp->link;
    }while(temp != NULL);
    
    return;
}

void POLY::ChangeDegree(int New, int old)
{
    node *temp;
    if(t->pow == old){
        t->pow = New;
    }
    temp = t;
    while(temp->link != NULL){
        if(temp->link->pow == old)
            temp->link->pow = New;
        temp->link = temp->link->link;
    }
}

//add new polynomial to list
void POLY::append(double co, int power)
{
    node *temp = new node;
    temp = t;
    while(temp->link != NULL)
        temp = temp->link;
    
    node *temp2 = new node;
    temp2->coeff = co;
    temp2->pow = power;
    temp2->link = NULL;
    temp->link = temp2;
}
    
double POLY::coefficient(int power)
{
    node *temp;
    temp = t;
    if(t->pow == power)
        return t->coeff;
        
    else if(t->link != NULL){
        do{
            temp = temp->link;
            if(temp->pow == power) return temp->coeff;
        }while(temp->link != NULL);
    }
    return 0.0;//return of 0.0 means function failed to find power
}

void POLY::changecoefficient(double newcoeff, int power)
{
    node *temp;
    temp = t;
    if(temp->pow == power){
        temp->coeff = newcoeff;
    }
        
    else if(t->link != NULL){
        do{
            temp = temp->link;
            if(temp->pow == power) temp->coeff = newcoeff;
        }while(temp->link != NULL);
    }
    else cout<<"Changing coefficient failed!";
}
    
void POLY::mult(double real_const)
{
    node* temp;
    temp = t;
    if(temp->link == NULL)
        temp->coeff = temp->coeff*real_const;
    else if(temp->link != NULL)
        do{
            temp->coeff = temp->coeff*real_const;
            temp = temp->link;
        }while(temp->link != NULL);
}
    

//IMPLEMENTATION main.cpp
#include <iostream>
#include <conio.h>
#include "class.h"

POLY Sum(POLY &one, POLY &two);

int main()
{
    POLY poly, poly2, ret;
    //ret = new POLY;
    
    poly.ChangeDegree(4,0);
    poly.changecoefficient(4,4);
    poly.append(3,3);
    poly.append(2,2);
    poly.append(1,1);
    cout<<endl<<endl;
    poly.print();

    poly2.ChangeDegree(5,0);
    poly2.changecoefficient(5,5);
    poly2.append(4,4);
    poly2.append(3,3);
    poly2.append(2,2);
    cout<<endl<<endl;
    poly2.print();
    
    ret = Sum(poly,poly2);
    
    cout<<endl<<endl;
    while(!_kbhit());
}


POLY Sum(POLY &one, POLY &two)
{
    cout<<"checkpoint 0\n";
    POLY ret;
    int deg1, deg2, high;
    double co1,co2;
    
    deg1 = one.degree();
    deg2 = two.degree();
    
    if(deg1 >= deg2){
        cout<<"checkpoint 1\n";
        high = deg1;
        ret.ChangeDegree(deg1,0);
        ret.changecoefficient(one.coefficient(one.degree()),deg1);
    }
    else{
        cout<<"checkpoint 2\n";
        high = deg2;
        ret.ChangeDegree(deg2,0);
        ret.changecoefficient(two.coefficient(two.degree()),deg2);
    }
    cout<<"\nchecking high value...\n"<<ret.coefficient(high)<<"\n\n";
    high--;
    
    cout<<"checkpoint 3\n";
    while(high >= 0){
        ret.append(one.coefficient(high)+two.coefficient(high),high);
        high--;        
    }
    cout<<"checkpoint 4\n";

    cout<<"checkpoint 5\n";
    return ret;
}

nadroj, I debug my programs in a similar, or same way. I narrow things down by either cout, printing, or some form of message saying it got to some point. By doing that I found it got to the comment in blue. Somehow my append function is messing up. I changed the functions that are inside the first argument to a constant number. It then compiled but it went through an infinite loop. Then I checked the value of one.degree() and two.degree(). These are returning false numbers, and I'm not sure why. They work find outside of the function Sum(), but inside the function they don't. What's going on there?

Alright... I think I might have it. The degree function is using a pointer of the struct inside the class POLY. I changed the Sum() arguments as below and it seems to return a true value of degree.

Code:

POLY Sum(POLY &one, POLY &two);

What kind of a copy constructor is that? It doesn't do anything for the actual poly being constructed.

And since using straight poly's in your function prototypes calls the copy constructor....

To be honest I've never used copy constructors, and that's the way the professor said to have it (yes this is homework). I will look at that later once I get this sum function to work completely right. So far it combines the coeff variables correctly, but it does not correctly set up the pow variable. They always come out to nonsensical values. I think this is again part of a pointer value, but again the append function works fine outside of sum, but not inside it.

im confused, is this crashing anymore? is the runtime error solved and this is now a different problem?

Originally Posted by nadroj

im confused, is this crashing anymore? is the runtime error solved and this is now a different problem?

Yes the runtime error is solved. The new problem is getting the pow variable to display correctly. The append function is not taking the 'high' variable correctly. The way it is set up it should display something like

Code:

5x^5 + 8x^4 + 6x^3 + 4x^2 + 1x^1

but it comes up with powers like 3435, 14, 6, 987783 and so on. I even put a constant there where high is and it didnt change anything.

in post 4 can you update the code or can you just post in reply to the lines i should change

Done, updated stuff is in blue.

I'm getting something weird... on the part below in sum, if I comment on the line I said there, the function doesn't actually print the entire polynomial, and all it should be doing is getting the value of the coefficient and not changing anything...

Code:

    if(deg1 >= deg2){
        cout<<"checkpoint 1\n";
        high = deg1;
        ret.ChangeDegree(deg1,0);
        ret.changecoefficient(one.coefficient(one.degree()),deg1);
    }
    else{
        cout<<"checkpoint 2\n";
        high = deg2;
        ret.ChangeDegree(deg2,0);
        ret.changecoefficient(two.coefficient(two.degree()),deg2);
    }
    cout<<"\n\n"<<ret.coefficient(high)<<"\n\n"; //COMMENT OUT THIS LINE
    high--;

output without it commented

Code:

4x^4 + 3x^3 + 2x^2 + 1x^1

5x^5 + 4x^4 + 3x^3 + 2x^2
checkpoint 0
checkpoint 2


5

checkpoint 3
checkpoint 4
checkpoint 5

5x^3173704 + 8x^3150224 + 6x^34 + 4x^6 + 1x^14 +

output with it commented

Code:

4x^4 + 3x^3 + 2x^2 + 1x^1

5x^5 + 4x^4 + 3x^3 + 2x^2
checkpoint 0
checkpoint 2
checkpoint 3
checkpoint 4
checkpoint 5

5x^2495376 +

that line that you said to comment out doesnt exist in the updated code. however im assuming you meant the line with 'checking high value...'.

also the code you updated is what im running and this is the (exact) output after commenting out the line mentioned above:

4x^4 + 3x^3 + 2x^2 + 1x^1

5x^5 + 4x^4 + 3x^3 + 2x^2checkpoint 0
checkpoint 2
checkpoint 3
checkpoint 4
checkpoint 5

which doesnt match up to your output above. what is the code your running?

The problem is the assignment operator in ret = Sum(poly1, poly2), I'm guessing. I say that because (1) I fixed your copy ctor and (2) changed the line to POLY ret(Sum(poly1, poly2)) -- after removing the declaration at the top, of course -- and everything magically worked.

Oh, and in POLY::append, this line

Code:

node *temp = new node;

is just a memory leak, since you immediately set temp = t on the next line. (So just do node *temp = t; and be done with it.)

Edit: And if the assignment didn't prohibit the use of std::list, we're going to come find you and your kneecaps.

Wow... just wow... I'm learning so much it's not even funny (at least I hope i'm learning otherwise this is all pointless). Ok so I changed my ret = Sum() to what you have tabstop, and then i also changed it to POLY ret = Sum() and it worked that way too... so... my question now is, what the difference between these...

Code:

POLY ret;
ret = Sum(poly1, poly2); //THIS DOES NOT WORK

POLY ret = Sum(poly1, poly2); //THIS WORKS

POLY ret(Sum(poly1, poly2)); //THIS ALSO WORKS

//I know the difference between the bottom two, I mean the top one compared to the bottom two

The bottom two are copy constructors, and the first is an assignment operator.

If I'm not mistaken (and if I am, we'll hear about it), the assignment operator would just do a shallow copy -- namely just copy the value of the pointer t -- and then destroy the temporary right hand side, which would cheerfully delete the linked list we just built.