I have been working on this for a few days now. I'm just trying to make a deep copy of a template linked list. I have successfully copied the list, but when I enter a new item to the new list, it also adds it to the original list. I'm using the operator= to copy the list and I am having problems getting a copy function to work. I have read many different ways to copy a linked list but have failed every time. Any help would be greatly appreciated. Here is SortedType.h and driver.cpp.

// SortedType.h
#include "ItemType.h"
using std::bad_alloc;
// Header file for Sorted List ADT.
template<class ItemType>
struct NodeType;

template<class ItemType>
class SortedType
{
public:
	SortedType();		// Class constructor
	~SortedType();		// Class destructor

	bool IsFull() const;
	int GetLength() const;
	void MakeEmpty();
	void RetrieveItem(ItemType& item, bool& found);
	void InsertItem(ItemType item);
	void DeleteItem(ItemType item);
	void ResetList();
	void Print();
	//SortedType<ItemType>(const SortedType<ItemType>& newList);
	//friend void Copy(SortedType<ItemType>, SortedType<ItemType>&);
	void operator=(SortedType<ItemType>);
	//Copy constructor.
	void GetNextItem(ItemType&);

private:
	NodeType<ItemType>* listData;
	int length;
	NodeType<ItemType>* topPtr;
	NodeType<ItemType>* currentPos;
};
.
.
.
template<class ItemType>
void SortedType<ItemType>::operator =
	(SortedType<ItemType> anotherList)
{
	if ( listData == NULL)
		listData = NULL;
	else
	{
		NodeType<ItemType>* ptr1;
		NodeType<ItemType>* ptr2;

		topPtr = new NodeType<ItemType>;
		topPtr->info = topPtr->info;
		ptr1 = topPtr->next;
		ptr2 = topPtr;
		while (ptr1 != NULL)
		{
			ptr2->next = new NodeType<ItemType>;
			ptr2 = ptr2->next;
			ptr2->info = ptr1->info;
			ptr1 = ptr1->next;
		}
		ptr2->next = NULL;
	}
}


template<class ItemType>
SortedType<ItemType>::SortedType(const SortedType<ItemType>& newList)
{
	NodeType<ItemType>* ptr1;
	NodeType<ItemType>* ptr2;

	if (anotherList.topPtr == NULL)
		topPtr = NULL;
	else
	{
		topPtr = new NodeType<ItemType>;
		topPtr->info = anotherList.topPtr->info;
		ptr1 = anotherList.topPtr->next;
		ptr2 = topPtr;
		while (ptr1 != NULL)
		{
			ptr2->next = new NodeType<ItemType>;
			ptr2 = ptr2->next;
			ptr2->info = ptr1->info;
			ptr1 = ptr1->next;
		}
		ptr2->next = NULL;
	}
}
// driver.cpp
#include <iostream>
#include <fstream>
#include <string>
#include <iomanip>
#include "SortedType.h"
using namespace std;

int main()
{
	int num;										// Data items in intList.
SortedType<int> intList;
ifstream intFile;
	intFile.open("assignment4int.dat");
	while(intFile >> num)
	{
		intList.InsertItem(num);
	}
	int a = intList.GetLength();					// Stores the length of the list in a.
	cout << "intList contains " << a << " items:" << endl;
	intList.Print(); 
SortedType<int>& newIntList = intList;			// Copies intList to newIntList;
cout << "Copy of intList:" << endl;
	newIntList.Print();
	cout << endl;
	cout << "Enter integer to add to newIntList" << endl;
	cin >> num;
	newIntList.InsertItem(num);
	cout << "newIntList now contains:" << endl;
	newIntList.Print();

	cout << endl;
	cout << "Original intList:" << endl;
	newIntList.Print();								// Displays copied list.

}

Recommended Answers

All 10 Replies

1. Use code tag correctly:
[code=cplusplus] source(s)

[/code]
2. You forgot to initialize listData in operator=()
3. You forgot to delete old list in operator=()
4. You forgot to check if (this != &anotherList) in operator=()
5. Use listDate or topPtr to point to the list head, not both
...
Try to correct the code then come back ;)...

Thanks for the help! I was able to fix 1 and 4. I changed some of my code. Now it is just not copying the original list to the new list. When I debug it, says it can't evaluate "info" and "next". Won't the operator= just make a shallow copy? Don't I need a copy constructor to copy the lists? Here are some updated and cleaned up versions of my files. I tried to get rid of things that I didn't use.

// SortedType.h
#include "ItemType.h"
using std::bad_alloc;
// Header file for Sorted List ADT.
template<class ItemType>
struct NodeType;

template<class ItemType>
class SortedType
{
public:
	SortedType();		// Class constructor
	~SortedType();		// Class destructor

	int GetLength() const;	
	void InsertItem(ItemType item);
	void Print();
	void operator=(const SortedType<ItemType>& newList);
	
private:
	NodeType<ItemType>* listData;
	int length;
	NodeType<ItemType>* topPtr;
	NodeType<ItemType>* currentPos;
};
template<class ItemType>
struct NodeType
{
	ItemType info;
	NodeType<ItemType>* next;
};

template<class ItemType>
SortedType<ItemType>::SortedType()	// Class constructor
{
	length = 0;
	listData = NULL;
}

template<class ItemType>
int SortedType<ItemType>::GetLength() const
{
	return length;
}

template<class ItemType>
void SortedType<ItemType>::InsertItem(ItemType item)
{
	NodeType<ItemType>* newNode;		// pointer to node being inserted
	NodeType<ItemType>* predLoc;		// trailing pointer
	NodeType<ItemType>* location;		// traveling pointer
	bool moreToSearch;

	location = listData;
	predLoc = NULL;
	moreToSearch = (location != NULL);
	// Find insertion point.
	while (moreToSearch == true)
	{
		if (location->info < item)
		{
			predLoc = location;
			location = location->next;
			moreToSearch = (location != NULL);
		}
		else
			moreToSearch = false;
	}

	// Prepare node for insertion
	newNode = new NodeType<ItemType>;
	newNode->info = item;
	// Insert node into list.
	if (predLoc == NULL)		// Insert as first
	{
		newNode->next = listData;
		listData = newNode;
	}
	else
	{
		newNode->next = location;
		predLoc->next = newNode;
	}
	length++;
}

template<class ItemType>
void SortedType<ItemType>::Print()
{
   NodeType<ItemType>* temp = listData;
   while(temp != NULL)
    {
      cout << temp->info << endl;
      temp = temp->next;
    }
}

template<class ItemType>
SortedType<ItemType>::~SortedType()
{
	NodeType<ItemType>* tempPtr;

	while (listData != NULL)
	{
		tempPtr = listData;
		listData = listData->next;
		delete tempPtr;
	}
}

template<class ItemType>
void SortedType<ItemType>::operator=
	(const SortedType<ItemType>& newList)
{

	//NodeType<ItemType>* listData;
	if ( listData == NULL)
		listData = NULL;
	else
	{
		NodeType<ItemType>* ptr1;
		NodeType<ItemType>* ptr2;


		topPtr = new NodeType<ItemType>;
		topPtr->info = newList.topPtr->info;
		ptr1 = topPtr->next;
		ptr2 = topPtr;
		while (ptr1 != NULL)
		{
			ptr2->next = new NodeType<ItemType>;
			ptr2 = ptr2->next;
			ptr2->info = ptr1->info;
			ptr1 = ptr1->next;
		}
		ptr2->next = NULL;
	}
	if (this == &newList)
		cout << "Successful!" << endl;
	else
		cout << "Failed!" << endl;
}
// driver.cpp
#include <iostream>
#include <fstream>
#include <string>
#include "SortedType.h"
using namespace std;

int main()
{
	int num;										// Data items in intList.
	string str;										// Data items in stringList.
	SortedType<int> intList;
	SortedType<string> stringList;
	ifstream intFile;
	ifstream strFile;

// Gets items from files, stores them in lists, and displays the lists.
	intFile.open("assignment4int.dat");
	while(intFile >> num)
	{
		intList.InsertItem(num);
	}
	int a = intList.GetLength();							// Stores the length of the list in a.
	cout << "intList contains " << a << " items:" << endl;
	intList.Print(); 
	strFile.open("assignment4string.dat");
	while(strFile >> str)
	{
		stringList.InsertItem(str);
	}
	cout << endl;
	int b = stringList.GetLength();							// Stores the length of the list in b.
	cout << "strList contains " << b << " items:" << endl;
	stringList.Print();
	cout << endl;

// List are being copied and displays if successful or failed.
	SortedType<int> newIntList;
	SortedType<string> newStrList;
	cout << "Copying intList to newIntList...";
	newIntList.operator=(intList);
	cout << "Copying stringList to newStrList...";
	newStrList.operator=(stringList);

// Display copied lists.
	cout << endl;
	cout << "Copy of intList:" << endl;
	newIntList.Print();
	cout << endl;
	cout << "Copy of strList:" << endl;
	newStrList.Print();
	cout << endl;

// Add items to new lists then displays the new updated lists.
	cout << "Enter integer to add to newIntList" << endl;
	cin >> num;
	newIntList.InsertItem(num);
	cout << "newIntList now contains:" << endl;
	newIntList.Print();
	cout << "Enter string to add to newStrList" << endl;
	cin >> str;
	newStrList.InsertItem(str);
	cout << "newStrList now contains:" << endl;
	newStrList.Print();

// Display the original lists.
	cout << endl;
	cout << "Original intList:" << endl;
	intList.Print();								// Displays original intList.
	cout << endl;
	cout << "Original stringList:" << endl;
	stringList.Print();								// Displays orignal stringList.
}
Member Avatar for jencas

1.

if ( listData == NULL)
    listData = NULL;

Splendid!

2. the first to do in an assignment op is to avoid copying an object to itself, so your assignment op should start with

if (this == &newlist)
   return;

3. an assignment op basically consists of:
a) deleting the current contents of the object
b) fill the object from the object to copy from

Rewrite your code and don't hesitate to come back if further problems arise.

Ok, I understand that I need an operator=, copy constructor, and a destructor. After I use my operator= to make a shallow copy of my list, do I then use the destructor on the original list and then the copy function to make a deep copy of the original list? Everything I have read about making deep copies never actually use a copy constructor, supposedly it does it automatically, unless you are dealing with templates. Anyway, I added a copy constructor back in.

template<class ItemType>
class SortedType
{
public:
	SortedType();		// Class constructor
	~SortedType();		// Class destructor

	int GetLength() const;	
	void InsertItem(ItemType item);
	void Print();
	void operator=(const SortedType<ItemType>& newList);
	SortedType<ItemType>(const SortedType<ItemType>& newList);
	
private:
	NodeType<ItemType>* listData;
	int length;
	NodeType<ItemType>* topPtr;
	NodeType<ItemType>* currentPos;
};
template<class ItemType>
SortedType<ItemType>::SortedType(const SortedType<ItemType>& newList)
{
}

I'm not really sure what to put in there. Would it be similar to my operator=?

Member Avatar for jencas

You are right. The only difference between op= and copy ctor is that you have to dump the old data in op=.

In such a case I nearly always use this sort of "pattern" for my classes:

class A
  {
  public:
    A()
      { Init(); }

    ~A()
       { Free(); }

    A(const A & x)
      { Init(); Assign(x); }

    A & operator=(const A & x)
     {
        if (this != &x) {
          Free(); Assign(x);
        }
        return *this;
      }

  private:
    void Init()
     {
        m_val = 0;
        m_elem = 0;
     }
    
    void Assign(const A & x)
      {
        m_val = x.m_val;
        if (x.m_elem)
          m_elem = new Element(*x.m_elm)
        else
          m_elem = 0;
      }

     void Free()
      {
        delete m_elem;
      }

    int m_val;
    Element * m_elem;
  };

Thanks. I think I see how it all works, just not sure which part is actually wrong. Now it compiles and runs. It shows the two lists that it read in then crashes when it tries to copy them. When I debug it, it stops on the line

topPtr->info = newList.topPtr->info;

in the copy function. Says it can't find intList and newIntList. Any ideas?

I just figured something out. I don't know if it going in the right direction or not but I forgot to put the "&" when I created the new lists. Here is what I put in the drive file to create and copy the lists.

// List are being copied and displays if successful or failed.
	SortedType<int>& newIntList = intList;
	SortedType<string>& newStrList = stringList;
	cout << "Copying intList to newIntList...";
	newIntList = intList;
	cout << "Copying stringList to newStrList...";
	newStrList = stringList;

Now it copies the lists but when I enter a new item and call the original, the original is the same as the copy. Also, I don't think it is even using my copy or operator= function because it doesn't tell me if the copy or successful or not.

Member Avatar for jencas

No, a reference (&) is only an alias for an object, never a copy!!! Your op= has to traverse the lists of the source object an insert a copy of each node into your new destination object.

so that part would be right without the &?

Member Avatar for jencas

so that part would be right without the &?

Yes, if your copy ctor does the right things.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.