access violation error

[samuelm33]

Hi I am getting an access violation reading error in my linked list header file. The project takes a binary tree and turns it into an ordered linked list. the binary tree header:

#ifndef BINARY_SEARCH_TREE_H
#define BINARY_SEARCH_TREE_H

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

template <typename Comparable>
class BinarySearchTree
{
  public:
    BinarySearchTree( ) :root( NULL )
    {  }

    BinarySearchTree(const BinarySearchTree & rhs) : root(NULL)
    { *this = rhs; }

    ~BinarySearchTree( )
    { makeEmpty( ); }

    const Comparable & findMin( ) const
    {
        if (isEmpty( ))
            throw UnderflowException( );
        return findMin(root)->element;
    }

    const Comparable & findMax( ) const
    {
        if(isEmpty( ))
            throw UnderflowException( );
        return findMax( root )->element;
    }

    bool contains(const Comparable & x) const
    { return contains(x, root); }

    bool isEmpty( ) const
    { return root == NULL; }

    void printTree(ostream & out = cout)
    {
        if (isEmpty( ))
            out << "Empty tree" << endl;
        else
            printTree(root, out);
	}

    void makeEmpty( )
    { makeEmpty(root); }

    void insert(const Comparable & x)
    { insert(x, root); }

    void remove(const Comparable & x)
    { remove(x, root); }

    const BinarySearchTree & operator=(const BinarySearchTree & rhs)
    {
        if (this != &rhs)
        {
            makeEmpty( );
            root = clone(rhs.root);
        }
        return *this;
    }

	void toList(linkedlist l)
	{ toList(l, root); }

  private:
    struct BinaryNode
    {
        Comparable element;
        BinaryNode *left;
        BinaryNode *right;

        BinaryNode(const Comparable & theElement, BinaryNode *lt, BinaryNode *rt)
            : element(theElement), left(lt), right(rt) { }
    };

    BinaryNode *root;
	void toList(linkedlist l, BinaryNode *&t)
	{ 
		if(t==NULL)
		{ return; }
		toList(l,t->left);
		l.add(t->element);
		toList(l,t->right);
	}

	void printTree(BinaryNode *&t, ostream & out = cout)
	{
		if(t==NULL)
		{ return; }
		printTree(t->left,out);
		cout << t->element << endl;
		printTree(t->right,out);
	}

    void insert(const Comparable & x, BinaryNode * & t)
    {
        if (t == NULL)
            t = new BinaryNode(x, NULL, NULL);
        else if (x < t->element)
            insert(x, t->left);
        else if (t->element < x)
            insert(x, t->right);
        else;  // Duplicate; do nothing
    }

    void remove(const Comparable & x, BinaryNode * & t)
    {
        if (t == NULL)
            return;   // Item not found; do nothing
        if (x < t->element)
            remove(x, t->left);
        else if (t->element < x)
            remove(x, t->right);
        else if (t->left != NULL && t->right != NULL) // Two children
        {
            t->element = findMin(t->right)->element;
            remove(t->element, t->right);
        }
        else
        {
            BinaryNode *oldNode = t;
            t = (t->left != NULL) ? t->left : t->right;
            delete oldNode;
        }
    }

    BinaryNode * findMin(BinaryNode *t) const
    {
        if (t == NULL)
            return NULL;
        if (t->left == NULL)
            return t;
        return findMin(t->left);
    }

    BinaryNode * findMax(BinaryNode *t) const
    {
        if (t != NULL)
            while (t->right != NULL)
                t = t->right;
        return t;
    }

    bool contains(const Comparable & x, BinaryNode *t) const
    {
        if (t == NULL)
            return false;
        else if (x < t->element)
            return contains(x, t->left);
        else if (t->element < x)
            return contains(x, t->right);
        else
            return true;    // Match
    }

    void makeEmpty(BinaryNode * & t)
    {
        if (t != NULL)
        {
            makeEmpty(t->left);
            makeEmpty(t->right);
            delete t;
        }
        t = NULL;
    }

    BinaryNode * clone(BinaryNode *t) const
    {
        if (t == NULL)
            return NULL;
        else
            return new BinaryNode(t->element, clone(t->left), clone(t->right));
    }
};

#endif 

the linked list header:

#ifndef LINKED_LIST_H
#define LINKED_LIST_H
#include <iostream>
using namespace std;

class linkedlist
{
private:

struct lNode{ 
	int data;
	lNode *next;
};

struct lNode *head;

public:

	linkedlist()
	{ struct lNode *head = new lNode;
	  head->next = NULL; 
	}

void add(int n) {
	lNode *newlNode = new lNode; 
	newlNode->data = n;          
	newlNode->next = NULL;       

	lNode *cur = head;           
	while(true) {
		if(cur->next == NULL)
		{
			cur->next = newlNode;
			break;
		}
		cur = cur->next;
	}
}

void display() { 
	lNode *list = head;              
					                         
	while(true)
	{
		if (list->next == NULL)
		{
			cout << list->data << endl;
			break;
		}
		cout << list->data << endl;
		list = list->next;
	}
	cout << "done" << endl;
}

};

#endif 

the main cpp file:

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

int main( )
{
    BinarySearchTree<int> t;
	linkedlist l;
    int i;

    cout << "inserting nodes into tree" << endl;
    t.insert(50);
    t.insert(60);
    t.insert(30);
    t.insert(20);
    t.insert(40);
    t.insert(70);
    t.insert(55);
    t.insert(65);
    t.insert(25);
    t.insert(35);
    t.insert(85);
    t.insert(100);
    t.insert(15);
    t.insert(45);
    t.insert(95);
    t.insert(105);
    t.insert(10);
    t.insert(75);
    t.insert(110);
    t.insert(12);
    t.insert(92);
    t.insert(32);
    t.insert(82);
    t.insert(22);
    t.insert(32);

    t.printTree( );
	t.toList(l);

    cout << "Finished processing" << endl;
	l.display();

    return 0;
}

The location of the error is in the linked list header file here: if(cur->next == NULL). I do not see how it could be an access error as everything is contained inside that class.

[D80DSL3A]

Not sure what's causing the crash, but I see a couple of details for comment:

Two things of note.
1) Your linkedlist constructor allocates a node to head right away, but no value is assigned to data. The value of data in the 1st node won't have the desired value. That needs to come from a tree value. If you eliminate the node allocation, then you will need to rewrite add() so t can cope with head = NULL and add the 1st node properly;

2) Your add() function is adding to the end of the list. This process would be much more efficient if you were maintaining a node* tail; for the list as well.
As it is you must iterate all the way through the list on ever add() call.

With a tail* the add operation is just:

tail->next = new lNode;// no need to iterate through the list. We're already there.
newlNode->data = n;          
newlNode->next = NULL;
tail = newlNode;

[anmol2701]

access violation error usually occurs when you are trying to access memory location that does not exist. Kindly check your code where you accessing linked lists nodes