linked list

[sfrider0]

I have an assignment to use templates for a linked sorted list. The SortedType.h file is in our book and that is what we have to change. I understand how to do all of that and it compiles and everything. When I create a driver to test it, I just get errors. I created a .dat file with a list of integers to test. I'm simply trying to copy those numbers into my intList display them. If I put a cout num at the end, the last item it my list just displays as many times at the length of the list is. I have done similar assignments but never had this problem. Something is required in the GetNextItems() but not really sure what it is. This should be something real simple and I am making this way to difficult. If you need to see ItemType.h, I can post that up too. Thanks in advance!

#include <iostream>
#include <fstream>
#include <string>
#include <iomanip>
#include "SortedType.h"
using namespace std;

int main()
{
	int num = 0;

	SortedType<int> intList;
	SortedType<string> stringList;

	ifstream inFile;
	inFile.open("assignment4int.dat");

	while(!inFile.eof()){
			inFile >> num;
			intList.InsertItem(num);
		}

	intList.ResetList();

	for(int i=0; i<intList.GetLength(); i++)
                     cout << intList.GetNextItem() << endl;
}

[jencas]

Please show us this SortedType stuff. And btw:

while(!inFile.eof()){
			inFile >> num;
			intList.InsertItem(num);
		}

is a potential endless loop. Try to figure out what happens if your input files contains a character different from a digit.

[sfrider0]

Here is 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 GetNextItem(ItemType&);

private:
	NodeType<ItemType>* listData;
	int length;
	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>
bool SortedType<ItemType>::IsFull() const
{
	NodeType* location;
	try
	{
		location = new NodeType;
		delete location;
		return false;
	}
	catch(bad_alloc exception)
	{
		return true;
	}
}

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

template<class ItemType>
void SortedType<ItemType>::MakeEmpty()
{
	NodeType* tempPtr;
	while (listData != NULL)
	{
		tempPtr = listData;
		listData = listData->next;
		delete tempPtr;
	}
	length = 0;
}

template<class ItemType>
void SortedType<ItemType>::RetrieveItem(ItemType& item, bool& found)
{
	bool moreToSearch;
	NodeType* location;

	location = listData;
	found = false;
	moreToSearch = (location != NULL);

	while (moreToSearch && !found)
	{
		switch(item.ComparedTo(location->info))
		{
		case GREATER:	location = location->next;
						moreToSearch = (location != NULL);
						break;
		case EQUAL:		found = true;
						item = location->info;
						break;
		case LESS:		moreToSearch = false;
						break;
		}
	}
}

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 = false;
	// Find insertion point.
	while (location != NULL && !moreToSearch)
	{
		if (location->info<item)
		{
			predLoc = location;
			location = location->next;
		}
		else
			moreToSearch = true;
	}

		/*switch(item.ComparedTo(location->info))
		{
		case GREATER:	predLoc = location;
			location = location->next;
						moreToSearch = (location != NULL);
						break;
		case LESS:		moreToSearch = false;
						break;*/
		
	

	// 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>::DeleteItem(ItemType item)
{
	NodeType* location = listData;
	NodeType* tempLocation;

	// Locate node to be deleted.
	if (item.ComparedTo(listData->info) == EQUAL)
	{
		tempLocation = location;
		listData = listData->next;	// Delete first node.
	}
	else
	{
		//while ((item.ComparedTo(location->next)->info) != EQUAL)
		//	location = location->next;

		//// Delete node at location-> next
		//tempLocation = location->next;
		//location->next = (location->next)->next;
	}
	delete tempLocation;
	length--;
}

template<class ItemType>
void SortedType<ItemType>::ResetList()
{
	currentPos = NULL;
}

template<class ItemType>
void SortedType<ItemType>::GetNextItem(ItemType& item)
{
	if (currentPos == NULL)
		currentPos = listData;
	item = currentPos->info;
	currentPos = currentPos->next;
}

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

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

As for the infinite loop and non-ints, I'll fix that later. Right now I'm just trying to get something in the list and display it.

[Lerner]

I find your problem description difficult to read/decifer. I would start by putting the following lines:

cout << "num is " << num << endl;
cin.get();

between these two lines:

inFile >> num;
intList.InsertItem(num);

to be sure you are reading in what you think you are. I suspect the reason num doesn't appear correctly when you output the value of num at the end of the code you initially posted is that you are running the body of the file reading loop one to many times by using the return value of eof() to control when to stop reading. I would change the reading loop to this:

while(inFile >> num)
{
   intList.InsertItem(num);
}

Also: here's the prototype for GetNextItem():

void GetNextItem(ItemType&);

meaning that GetNextItem() doesn't return anything, so trying to ouptut the value of the return value here:

cout << intList.GetNextItem() << endl;

doesn't make any sense. There is no output statement within GetNextItem(), so dropping the cout and just calling GetNextItem() repeatedly wouldn't output anything, either. If you want to print the contents of the list, then I'd declare a member function called something like print() which could be defined something like this:

void printList()
{
   NodeType * temp = intlist.listData;
   while(temp !== NULL)
    {
      cout << temp->info << endl;
      temp = temp->next;
    }
}

and call it like this;

intList.print();

[sfrider0]

Thank You! That helped so much. Problem solved