Sign in to follow this  
toogreat4u

Sorted list problem

Recommended Posts

I am doing an exercise out of a book for my own personal understanding and I have run into a problem. My program is aborting immediately every time I try and run it and I am lost as to where it would be getting a fatal error. This may seem like remaking the wheel and it probably is but I am doing it to better myself, and for a solid understanding of how sorted lists work. I believe the problem is located in the function locatePosition(ListItemType anItem, int& index, bool& isPresent). Thanks for any help.
#include "SortedList.h"

SortedList::SortedList(): size(0)
{}

bool SortedList::isEmpty() const
{
	return (size == 0);
}

int SortedList::getLength() const
{
	return size;
}

void SortedList::insert(ListItemType newItem, bool &success)
{
	int index;
	bool isPresent;

	success = (index >= 1) && (index <= size + 1) && (size < MAX_LIST);

	if(success)
	{
		// make room for new item by shifting all items at
		// positions >= index toward the end of the
		// list (no shift if index == size + 1)

		// locating the index for the item to be placed in
		locatePosition(newItem, index, isPresent);

		// as long as it isn't present in the list then
		// it is ok to shift everything
		if(!isPresent)
		{
			for(int pos = size; pos >= index; --pos)
			{
				items[translate(pos + 1)] = items[translate(pos)];
			}

			// insert new item
			items[translate(index)] = newItem;
			++size; // increase the size of the list by one
		} // end if
		else
			success = false;
	} // end if
} // end insert

void SortedList::remove(int index, bool &success)
{
	success = (index >= 1) && (index <= size);

	if(success)
	{
		// delete item by shifting all items at positions >
		// index toward the beginning of the list
		// (no shift if index == size)
		for(int fromPosition = index + 1; fromPosition <= size; ++fromPosition)
		{
			items[translate(fromPosition - 1)] = items[translate(fromPosition)];
			--size; // decrease the size of the list by one
		} // end for
	} // end if
} // end remove

void SortedList::retrieve(int index, ListItemType &dataItem, bool &success) const
{
	success = (index >= 1) && (index <= size);

	if(success)
		dataItem = items[translate(index)];
}

void SortedList::printList()
{
	cout << "List contains: ";
	for(int i = 0; i < size; i++)
	{
		cout << items[i] << ' ';
	}
	cout << endl;
}

void SortedList::locatePosition(ListItemType anItem, int &index, bool &isPresent)
{
	ListItemType dataItem;
	bool success;

	if(isEmpty())
	{
		index = 1;
		isPresent = false;
		cout << "Empty List.\n";
		cout << anItem << " is to be placed at position " << index << endl;
	}
	else
	{
		// list is not empty therefore need to find where anItem should
		// be placed
		for(index = 1; index <= size; index++)
		{
			// compare item by item
			retrieve(index, dataItem, success);

			if(dataItem == anItem)
			{
				cout << anItem << " is a duplicate, no insertion.\n";
				isPresent = true;
			}
			else if(anItem < dataItem)
			{
				// this is where anItem should be placed
				cout << anItem << " is to be placed at position " << index << endl;
				isPresent = false;
			}
		}
		isPresent = false;
	}
}

int SortedList::translate(int index) const
{
	return (index - 1);
}

Here is my driver program that is testing it.
/* Define a class for an array-based implementation of the ADT sorted
 * list. Consider a recursive implementation for locatePostion.
 * Should sortedInsert and sortedRemove call locatePosition?
 */

#include "SortedList.h"

int main()
{
	SortedList l;
	bool success;

	l.insert(1, success);
	
	l.insert(5, success);

	l.insert(3, success);

	l.printList();

	return 0;
}

Share this post


Link to post
Share on other sites
Finding the exact location of the error is certainly the highest priority. There are myriad debugging techniques. Very low in the list is to scan all the code, hoping to spot an error. You're familiar with the code and you haven't found it. It's unlikely someone else would.

I don't know what programming interface you're using, but, if whatever you're using allows it, set breakpoints and follow the execution until you get an error.

If you can't set breakpoints, output debug messages at each function call.

It appears that you're familiar with writing code. Output messages to yourself and narrow down the location of the problem.

Share this post


Link to post
Share on other sites
Thanks EAX, I didn't even notice I had done that! You were correct once I fixed that error I stopped getting the fatal error that crashed the program. FYI I also found another mistake and fixed it, that mistake was not returned whenever I found the index that was either the index of a duplicate or the index if the array had items already inside of it. Thanks for your help.

Share this post


Link to post
Share on other sites
[code]void SortedList::insert(ListItemType newItem, bool &success)[/quote]

Ugh. No. Stop that.

The natural way to get information back from a function is via its return value. Don't explicitly refuse to return something, and then take an extra parameter that is used only to return something.

Also, "single-entry, single-exit" is a pretty outdated way of thinking now. Guard clauses help keep things organized, and in well-organized code certainly do not cause problems with comprehension or debugging.


// return whether successful
bool SortedList::insert(ListItemType newItem)
{
// By the way, why not leave this checking logic up to locatePosition()?
if ((index < 1) || (index > size + 1) || (size >= MAX_LIST)) return false;

// Figure out where the item will be placed (returns -1 if it's already present)
int index = locatePosition(newItem);
if (index == -1) { return false; }

// OK, we will place the item. First shift everything over...
for (int pos = size; pos >= index; --pos)
{
items[translate(pos + 1)] = items[translate(pos)];
}
// insert new item
items[translate(index)] = newItem;
++size;
return true;
} // end insert

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this