HELP Linked List and operation overloading
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 6 of 6

Thread: HELP Linked List and operation overloading

  1. #1
    Join Date
    Mar 2013
    Posts
    2

    HELP Linked List and operation overloading

    Hello. I am having a bit of difficulty with implementing an object oriented program that uses both linked lists and operator overloading and would like some help. The program calls for adding and multiplying polynomials together, with each single polynomial being represented as a node of a linked list (which is further a data member of an object of a class I have defined to implement this program). For example:

    polynomial A will be: 3x^4 // 1 node of a linked list
    polynomial B will be: 5x^2 // 1 node of a linked list
    polynomial C will be blank for the time being. // empty list

    Now, I need to use operator overloading so that this following line of code can be implemented:

    C = A + B;

    C should now be: 3x^4 + 5x^2.

    The checklist of which parts of my code that work:

    constructor works;
    copy constructor works;
    destructor works;
    operator= works;
    print function needs work but i can worry about that later;
    operator+ HELP: HIGHLIGHTED IN RED
    operator* work on later

    Here is my code:

    Code:
    #include <iostream>
    using namespace std;
    
    struct termNode
    {
        int exp;     // exponent
        int coef;    // coefficient
        termNode * next;
        termNode(int e = 0, int c = 0, termNode * link = NULL)
        {
            coef = c;
            exp = e;
            next = link;
        }
    };
    
    class polyType
    {
    public:
        polyType();                     // default constructor
        polyType(int, int);             // constructor makes a 1 node polynomial
        polyType(const polyType &);     // copy constructor
        ~polyType();                    // destructor
        void print();                   // prints out the polynomial in descending order
    
        polyType  operator=(const polyType &);              // equals
        polyType  operator+(const polyType &) const;        // returns sum of the parameter + self
        polyType  operator*(const polyType &) const;        // return the product of the parameter + self
    
    private:
        termNode  *polyPtr;
    };
    
    polyType::polyType ()
    {
        polyPtr = new termNode();
    }
    
    polyType::polyType (int e, int c)
    {
        polyPtr = new termNode(e, c);
    }
    
    polyType::polyType(const polyType &rhs)
    {
        termNode * orig = rhs.polyPtr;
        termNode * newP = NULL;
    
        polyPtr = NULL;
    
        while(orig != NULL)
        {
            if(newP == NULL)
            {
                polyPtr = new termNode;
                polyPtr->exp  = orig->exp;
                polyPtr->coef = orig->coef;
                polyPtr->next = NULL;
                newP = polyPtr;
            }
            else
            {
                newP->next = new termNode;
                newP = newP->next;
                newP->exp = orig->exp;
                newP->coef = orig->coef;
                newP->next = NULL;
            }
            orig = orig->next;
        }
    }
    polyType::~polyType()
    {
        delete polyPtr;
        polyPtr = NULL;
    }
    void polyType::print()
    {
        termNode * header = new termNode;
        header = polyPtr;
    
        while(header != NULL)
        {
            cout << header->coef << "x^" << header->exp << " + ";
            header = header->next;
        }
    }
    
    polyType polyType::operator=(const polyType &rhs)
    {
        delete polyPtr;
    
        termNode * orig = rhs.polyPtr;
        termNode * newP = NULL;
    
        polyPtr = NULL;
    
        while(orig != NULL)
        {
            if(newP == NULL)
            {
                polyPtr = new termNode;
                polyPtr->exp  = orig->exp;
                polyPtr->coef = orig->coef;
                polyPtr->next = NULL;
                newP = polyPtr;
            }
            else
            {
                newP->next = new termNode;
                newP = newP->next;
                newP->exp = orig->exp;
                newP->coef = orig->coef;
                newP->next = NULL;
            }
            orig = orig->next;
        }
    
        return *this;
    }
    polyType polyType::operator+(const polyType &rhs) const
    {
        polyType re = *this;
        re.polyPtr->next = new termNode(rhs.polyPtr->exp, rhs.polyPtr->coef);
    
        return re;
    }
    polyType polyType::operator*(const polyType &rhs) const
    {
        polyType re;
        termNode * ptr = polyPtr;
        while(ptr != NULL)
        {
        re.polyPtr->exp = ptr->exp * rhs.polyPtr->exp;
        re.polyPtr->coef = ptr->coef * rhs.polyPtr->coef;
        ptr = ptr->next;
        }
        return re;
    }
    
    int main()  // DRIVER TESTING
    {
        polyType a(2,2);
        polyType b(7,1);
        polyType d(5,3);
        polyType c;
        polyType e;
        cout << "A: ";
        a.print();
        cout << endl << "C: ";
        c = a + b;
        c.print();
        cout << endl << "E: ";
        e.print();
        cout << endl << "E: ";
        e = a * c;
        e.print();
        cout << endl << "A: ";
        a.print();
        cout << endl << "D: ";
        d.print();
        return 0;
    }
    For the time being I need help with adding multiple nodes together (with the result being in descending order). So for example:

    polyType a(2,3), b(4,5), c(6,7), d;
    d = a + b + c;
    d.print(); // should print out 7x^6 + 5x^4 + 3x^2, but it will only print out: 3x^2 + 7x^6

    Thanks for the help

  2. #2
    Join Date
    Apr 1999
    Posts
    27,423

    Re: HELP Linked List and operation overloading

    Quote Originally Posted by aces237 View Post
    Hello. I am having a bit of difficulty with implementing an object oriented program that uses both linked lists and operator overloading and would like some help.
    First, have you debugged your program using the debugger, or just running your program and hoping it works?

    Second, you say your copy constructor "works" -- you need to convince me of that.
    Code:
    polyType::polyType(const polyType &rhs)
    {
        termNode * orig = rhs.polyPtr;
        termNode * newP = NULL;
    
        polyPtr = NULL;
    
        while(orig != NULL)
        {
            if(newP == NULL)
            {
                polyPtr = new termNode;
                polyPtr->exp  = orig->exp;
                polyPtr->coef = orig->coef;
                polyPtr->next = NULL;
                newP = polyPtr;
            }
            else
            {
                newP->next = new termNode;
                newP = newP->next;
                newP->exp = orig->exp;
                newP->coef = orig->coef;
                newP->next = NULL;
            }
            orig = orig->next;
        }
    }
    The purpose of the copy constructor is to make an exact copy of the object that is passed in. Semi-copies, fake copies, bogus copies, are not to be made by the copy constructor. The reason is that the compiler itself can call the copy constructor for various reasons. If your copy constructor has side-effects where the copy is not a real copy, then all bets are off as to how the program will behave.

    Your copy constructor (and your assignment operator) uses an if() statement that checks the condition of local variables. This to me gives off all sorts of red flags.

    What you're supposed to do is simply take the object that is passed in to the function, and blindly (yes, blindly) just copy the members of that object into this. No if() statements, no checking if the object passed in has a certain characteristic, nothing. Just take the object passed in, and assign this the value of the passed-in object's members. If you want to have a function that takes an object and does something that falls outside of these limitation, then write a separate function and call it by a different name, but don't use/abuse the copy-assignment operations for this purpose.

    If you don't do that you end up with the fake or semi-copies, and code like this now becomes suspect:
    Code:
    polyType polyType::operator+(const polyType &rhs) const
    Your copy constructor better make a valid copy, or else all of this is trash. You are returning a copy, and the copy constructor needs to be coded correctly.

    Edit: If your class is supposed to be a linked list, then you should have had a simple "addNode" function that simply adds a node to the end of the list. I don't see one coded. If you coded it, and also a simple "clear" function that removes all the nodes, the copy constructor and assignment operator become trivial functions that just start from the head of rhs and calls "add" for each node in rhs.

    Regards,

    Paul McKenzie
    Last edited by Paul McKenzie; March 3rd, 2013 at 08:04 PM.

  3. #3
    Join Date
    Apr 1999
    Posts
    27,423

    Re: HELP Linked List and operation overloading

    You also have memory leak issues:
    Code:
    void polyType::print()
    {
        termNode * header = new termNode;
        header = polyPtr;
    Why are you allocating memory, and then immediately replacing the pointer with another? You now have no way to issue a delete on the memory that was allocated on the first line.

    Second, your driver program doesn't test the simplest of conditions, and that is copying that I mentioned earlier:
    Code:
    int main()  // DRIVER TESTING
    {
        polyType a(2,2);
        polyType b(7,1);
        a = b;
    }
    This simple program better not leak memory, corrupt memory, and it has to truly reflect that "a" is indeed now equal to "b" after the assignment occurs.

    Also:
    Code:
     while(ptr != NULL)
        {
        re.polyPtr->exp = ptr->exp * rhs.polyPtr->exp;
        re.polyPtr->coef = ptr->coef * rhs.polyPtr->coef;
        ptr = ptr->next;
        }
    What is the purpose of the loop? More to the point, why are you just assigning re.polyPtr->exp and re.polyPtr->coef in a loop, overwriting the previous values assigned to it? You might as well just looped to the end and assign the last known values to re.polyPtr->exp and re.polyPtr->coef.

    Regards,

    Paul McKenzie
    Last edited by Paul McKenzie; March 3rd, 2013 at 08:10 PM.

  4. #4
    Join Date
    Mar 2013
    Posts
    2

    Re: HELP Linked List and operation overloading

    First, have you debugged your program using the debugger, or just running your program and hoping it works?
    Yes, I have used the debugger.

    Second, you say your copy constructor "works" -- you need to convince me of that.
    Looks like it is working here: http://puu.sh/2bKda

    Second, your driver program doesn't test the simplest of conditions, and that is copying that I mentioned earlier:
    See the link I have provided, 4th from the bottom.

  5. #5
    Join Date
    Apr 1999
    Posts
    27,423

    Re: HELP Linked List and operation overloading

    Quote Originally Posted by aces237 View Post
    Yes, I have used the debugger.
    And where does the program goes counter to what you expect? If you used the debugger, what variable(s) are not set correctly, program flow doesn't flow correctly, functions, are not being called or called incorrectly, etc.?
    Looks like it is working here: http://puu.sh/2bKda
    A URL link doesn't mean a program is working. I can show you a thousand programs that seem to produce the right output, but internally are causing all sorts of problems.
    Code:
    else
            {
                newP->next = new termNode;
                newP = newP->next;
                newP->exp = orig->exp;
                newP->coef = orig->coef;
                newP->next = NULL;
            }
    Going back to your copy constructor, where exactly do you delete "newP->next"? I don't see where newP is assigned to anything, and you just exit the function with this memory allocated, causing a leak. As a matter of fact, your destructor for polyton is supposed to go through the nodes and delete them, but I don't see this coded anywhere. Your destructor just simply deletes that single pointer.
    d.print(); // should print out 7x^6 + 5x^4 + 3x^2, but it will only print out: 3x^2 + 7x^6
    So did you fix the print() function so that it doesn't allocate a pointer to memory and then immediately overwrites it?

    Regards,

    Paul McKenzie
    Last edited by Paul McKenzie; March 4th, 2013 at 04:45 AM.

  6. #6
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,265

    Re: HELP Linked List and operation overloading

    Going back to your original question and assuming you're sorted out the issues raised by Paul above. You can't just do an 'add' of linked lists by a single statement as you are trying. You need to create a new list with individual nodes for each of the different exponents in the two lists and where the two lists have an exponent in common then you need to add the coefficients for the exponent in the new list.

    Also your operator= method is also leaking memory as again you are just deleting the memory pointed to by polyPtr and not the memory used for all of its links. To delete a linked list, you need to walk the links and delete each node. Adding and removing nodes and deleting the linked list should be methods of the list class. Your polyType class should not have and not need any knowledge of the internal workings of list class. So rather than just have a struct trying to act like a poor class with a constructor, make this a proper class with add, remove, delete, copy methods etc. These methods are then used by the polyType class so polyType doesn't deal with memory as it does now.
    All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Azure Activities Information Page

Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center