Thread: merging linked lists

  1. #1
    Registered User
    Join Date
    Mar 2007
    Posts
    416

    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

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    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.

  3. #3
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    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.

  4. #4
    Registered User
    Join Date
    Mar 2007
    Posts
    416
    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?
    Last edited by scwizzo; 09-14-2008 at 04:29 PM.

  5. #5
    Registered User
    Join Date
    Mar 2007
    Posts
    416
    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);

  6. #6
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    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....

  7. #7
    Registered User
    Join Date
    Mar 2007
    Posts
    416
    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.

  8. #8
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    im confused, is this crashing anymore? is the runtime error solved and this is now a different problem?

  9. #9
    Registered User
    Join Date
    Mar 2007
    Posts
    416
    Quote Originally Posted by nadroj View Post
    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.

  10. #10
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    in post 4 can you update the code or can you just post in reply to the lines i should change

  11. #11
    Registered User
    Join Date
    Mar 2007
    Posts
    416
    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 +

  12. #12
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    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?

  13. #13
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    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.
    Last edited by tabstop; 09-14-2008 at 04:54 PM.

  14. #14
    Registered User
    Join Date
    Mar 2007
    Posts
    416
    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

  15. #15
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Linked Lists 101
    By The Brain in forum C++ Programming
    Replies: 5
    Last Post: 07-24-2004, 04:32 PM
  2. need help w/ linked lists
    By MKashlev in forum C++ Programming
    Replies: 11
    Last Post: 08-05-2002, 08:57 PM
  3. merging two linked lists..
    By Makimura in forum C++ Programming
    Replies: 2
    Last Post: 11-14-2001, 12:34 PM
  4. doubly linked lists
    By qwertiop in forum C++ Programming
    Replies: 3
    Last Post: 10-03-2001, 06:25 PM
  5. Merging Linked Lists
    By Unregistered in forum C++ Programming
    Replies: 3
    Last Post: 09-23-2001, 07:08 PM