2

OK making progress here. My question is now related to copy construction and deep-copy. My stack is currently crashing all the time and I have a feeling that it is doing so because the class it is dependent on doesn't allow copy construction and operator overloading. But anyway here is my code (I apologize for the amount of code but it is probably necessary to understand where i am failing):

The dependent class, linked list

#ifndef linkList_H
#define linkList_H


//
// Create an object to represent a Node in the linked list object
// (For now, the objects to be put in the list will be integers)
//
struct Node
{
    int   number;
    Node* next;
    Node* prev;

    // needs copy constructor?
    // needs overloaded assignment operators for copying?
    // needs overloaded operators for incrementing and decrementing?
};


//
// Create an object to keep track of all parts in the list
//
class List
{
public:

    //
    // Contstructor intializes all member data
    //
    List() : m_size(0), m_listHead(0) {}

    //
    // methods to return size of list and list head
    //
    Node*    getListHead() const { return m_listHead; }
    unsigned getListSize() const { return m_size; }

    //
    // methods for adding and inserting a new node to the linked list, 
    // retrieving and deleting a specified node in the list
    //
    void  addNode(int num);
    void  deleteNode(Node* current);
    void  insertHead(Node* current);
    void  insertAfter(Node* current, int newValue);
    void  insertBefore(Node* current, int newValue);

    Node* retrieveNode(unsigned position);

private:

    //
    // member data consists of an unsigned integer representing
    // the list size and a pointer to a Node object representing head
    //
    Node*    m_listHead;
    unsigned m_size;
};

#endif

Implementation of linkedList

#include "linkList.h"
#include <iostream>

using namespace std;


//
// Adds a new node to the linked list
//
void List::addNode(int num)
{
    Node *newNode = new Node;
    newNode->number = num;
    newNode->next = m_listHead;

    if( m_listHead )
        m_listHead->prev = newNode;

    m_listHead = newNode;
    ++m_size;
}


//
// Inserts a node which has already been set to front
// of the list
//
void List::insertHead(Node* current)
{
    int value = current->number;
    deleteNode(current);
    addNode(value);
}


//
// Inserts a node which has already been set before a
// specified location in the list
//
void List::insertBefore(Node* current, int newValue)
{
    current = current->prev;
    current->number = newValue;
}


//
// Inserts a node which has already been set before a
// specified location in the list
//
void List::insertAfter(Node* current, int newValue)
{
    current = current->next;
    current->number = newValue;
}


//
// Deletes a node from a specified position in linked list
//
void List::deleteNode(Node* current)
{
    --m_size;

    if(current == m_listHead) 
        m_listHead = current->next;
    if(current->prev) 
        current->prev->next = current->next;
    if(current->next) 
       current->next->prev = current->prev;
}


//
// Retrieves a specified node from the list
//
Node* List::retrieveNode(unsigned position)
{
    if(position > (m_size-1) || position < 0)
    {
        cout << "Can't access node; out of list bounds";
        cout << endl;
        cout << endl;

        exit(EXIT_FAILURE);
    }

    Node* current = m_listHead;
    unsigned pos = 0;

    while(current != 0 && pos != position)
    {
        current = current->next;
        ++pos;
    }

    return current;
}

Here is the stack class:

#ifndef stack_H
#define stack_H

#include "linkList.h"


class Stack
{
public:

    //
    // Constructor, copy constructor and destructor to initialize stack 
    // data, copy data and clear up memory, respectively
    //
   Stack() : m_top(0), m_stack(new List()) {}
   Stack(const Stack &rhs);

   ~Stack() { delete [] m_stack; }

    //
    // functionality to determine if stack is empty
    //
    bool isEmpty();

    //
    // methods for pushing data on to stack and for
    // popping data from the stack
    //
    void push(int newValue);
    int  pop();

    //
    // accessor functions for retrieving the value on top of stack
    // and for returning the stack size
    //
    int getTop() const { return m_top->number; }
    int getSize() const { return m_stack->getListSize(); }

    //
    // overloaded assignment operator for copying stack
    //
    Stack& operator=(const Stack &rhs);

private:

    //
    // member data which represent the stack, the top
    // of the stack and the size of the stack
    //
    Node* m_top;
    List* m_stack;
};

#endif

And finally, here is the stack implementation

#include "stack.h"
#include <iostream>

using namespace std;

//
// Copy constructor
//
Stack::Stack(const Stack &rhs)
    : m_top(rhs.m_top), m_stack(rhs.m_stack)
{
}

//
// if the Top of stack is zero, return true
//
bool Stack::isEmpty()
{
    if( m_top == 0 ) return true;
    else return false;
}

//
// increment stack pointer, place new value in stack
//
void Stack::push(int newValue)
{
    ++m_top;               
    m_top->number = newValue;   // crashes on this statement
}

//
// if the stack is empty, throw an error message
//
int Stack::pop()
{
    if( isEmpty() )
    {
        cout << "Error: stack underflow" << endl;
        exit(EXIT_FAILURE);
    }

    --m_top;
    return (m_top + 1)->number;

}


Stack& Stack::operator=(const Stack &rhs)
{
    if( this != &rhs )
        delete [] m_stack;

    m_stack = new List();
    m_stack = rhs.m_stack;
    m_top = rhs.m_top;

   return *this;
}

Program crashes after this simple code in the main program:

Stack stack;

stack.push(1);

Again, sorry for the amount of code here. I believe my problem here is that the Node object needs overloaded operators in order to "increment" or "decrement" to create/delete a node when a value is being pushed/popped to the stack. Is this the case? Also, I am not sure if I need a copy constructor or not for the Node object. There could be many more problems here (maybe the algorithms are incorrect? maybe copy construction is incorrect for stack?). Any ideas?

4
  • m_top is initialized to 0, so it is null when you try to push it is null and will fail. Commented Oct 11, 2011 at 2:01
  • You've got ... serious problems in your code. It would appear you really don't understand pointers and how to use them. pop() is also horribly wrong and would crash in an equally spectacular way. Commented Oct 11, 2011 at 2:05
  • Thanks for the constructive criticism, Brian. Commented Oct 11, 2011 at 2:07
  • 1
    Why is this question getting down votes? Dylan may be a novice, but he accurately described his problem, provided all the code, and asked some intelligent questions. I'm usually the a-hole when it comes to questions, but I think this is a better-than-average post! Commented Oct 11, 2011 at 2:17

5 Answers 5

3

Lets take your crashing scenario line-by-line. (good, cause it only has 2 lines!)
First the statement: Stack stack;
This will call the stack-constructor, which will set m_top to what value?

Next, there's the line: stack.push(1);
The two statements of stack.push will both use m_top.
The first statement is ++m_top;
Given what value m_top started with, what value will it have now?

The second statement is m_top->number = newValue;
If you answered the previous questions about m_top correctly, it should be clear why the program is crashing at this point. It should also be relatively clear how to fix it.

Sign up to request clarification or add additional context in comments.

6 Comments

Oops. Sorry. That first statement of m_top should've been ++m_top. But i see what you are saying. The stack is initialized to zero but i moved the pointer to the next value in the stack resulting in the crash. But with ++m_top, it was crashing too. Maybe it is the same problem in both cases?
m_top is declared as a Node* (pointer to Node), and initialized to NULL/0. You cannot do anything to it until you make it point to valid memory, either by allocating memory (new), or assigning it to an existing Node.
m_top is assigned to null when the object is instantiated, but its numerical value should be garbage until the second statement in push(), where i am trying to assign it to a value that i passed in the function call. right?
Its numerical value won't be garbage. It starts at 0, and you call ++, resulting in 1. However, 1->number doesn't make any sense. 1 is not a Node-structure, and does not have a number part.
|
1

m_top is set to 0 in your constructor. But...

Your Stack just needs to decorate your List in a very specific manner. From looking briefly at your List header, it all should be relatively easy to implement, if you understand how a stack works...

Your Stack doesn't need to hold a "top". It should be implemented in terms of your List. Pushing onto the stack should add a new node at the front of your list, and popping from the stack should remove a node from the front of your list.

1 Comment

Hmm. Now that you mention it you are right. m_top is just another name for m_listHead.
1

First of all, you can't use the array delete operator on m_stack (delete [] m_stack) because there is only a single object there not an array (m_stack = new List). This will cause a crash. (Actually I don't see why it's created dynamically.)

Then, you will need to write a proper assignment operator and copy constructor for your List class, which will copy the nodes, and also a destructor which clean up the allocated nodes, but this has nothing to do with your crash (but will easily cause you in the future).

The current cause of the crash, is like the others said, that Stack tries access m_top while it's being null.

But the main problem is bad design which makes you use the List class in an unclear way :/

  • First, if you have a two-way linked list, the List class should also track the tail pointer not just the head pointer. This will free you from a lot a head-aches.
  • Then, addHead, addTail, insertBefore, insertAfter should not rely on the user to create the nodes, but create them inside the functions and return the newly created node.
  • Also it is very unsafe that the next and prev pointers are exposed and can be changed outside the List class. I suggest you the make prev and next private and expose a getter for them, so they could not be changed (List class will need to be friend of the Node struct/class in this case).

I think, these will give you good start how to re-write List and Stack from scratch. Also, keep an eye out for the ownership of the nodes which is not handled now.

1 Comment

Thank you. I indeed had to add a tail object to my List when designing a queue. I managed to take care of most of what you described, although I still need to implement the friend relationship with node and list.
0

You initialize m_top to 0 (null) in the constructor then try and use it in push()

2 Comments

Yes, I see. m_top only points to null so moving the pointer somewhere where memory hasn't been allocated will result in the crash.
Erm, no ... you're trying to dereference m_top and it's null. You're not moving anything.
0

Best approach is to test these classes one at a time. Since Stack depends on List, debug list first. I'm assuming that you have a access to a debugger. If not get one and learn how to use it. You also need to write some test code for the List class.

Good luck.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.