Structures and linked lists

[michaelhart]

The program compiles with zero errors but will obviously not do what I intend. I am trying to implement a Radix Sort using 100 strings of length 10 with each character being randomly drawn from the range of A-Z.

I have a an array of structures that are supposed to hold addresses to the linked lists with a pointer to the first and last elements of the list. Everything looks right to me but it's not working. Something tells me I am mismanaging the pointers. Any help would be appreciated.

#include <iostream>
#include <fstream>
#include <ctime>
#include <cmath>
#include <iomanip>
#include <string>

using namespace std;

struct wordNode;
typedef wordNode* wordPtr;

struct bucket 
{
	wordPtr firstWord, lastWord;
};

struct wordNode
{
	string word;
	wordPtr nextWord;
};

int main() 
{
	int i, j, idx;
	bucket table[26];
	string words[100];

	// Randomize strings
	for (i=0; i<100; i++) {
		words[i] = "AAAAAAAAAA";
		for (j=0; j<10; j++)
			words[i][j] += rand() % 26;
	}

	// Initialize pointers to NULL
	for (int i = 0; i < 26; i++) {
		table[i].firstWord = NULL;
		table[i].lastWord = NULL;
	}
	
	// Special case for first iteration of Radix Sort
	for (i=0; i<100; i++) {
	
		idx = words[i][0] - 'A';
		
		wordPtr tmp = new wordNode;
		tmp->word = words[i];
		tmp->nextWord = NULL;

		if (table[idx].firstWord == NULL)
			table[idx].lastWord = tmp;

		else
			table[idx].lastWord->nextWord = tmp;

		table[idx].lastWord = tmp;	
	}
	
    for (i=1; i<10; i++) 
	{
		for (j=0; j<26; j++) 
		{
			wordPtr curr = table[j].firstWord;
			wordPtr last = NULL;
			
			while (curr != NULL)
			{
				idx = curr->word[i] - 'A';
				
				// Move
				if (idx != j)
				{
					// Move to new structure index
					if (table[idx].firstWord == NULL)
						table[idx].firstWord = curr;
					else				
						table[idx].lastWord->nextWord = curr;

					table[idx].lastWord = curr;
					
					// Remove from linked list
					if (last == NULL) // First word in the list
					{
						if (curr->nextWord == NULL)  // and last word in the list
							table[j].firstWord = NULL;
							
						else // Not last word in the list
							table[j].firstWord = curr->nextWord;
					}

					else if (curr->nextWord == NULL) // Last word in the list
					{
						table[j].lastWord = last;
						last->nextWord = NULL;					
					}

					else // Somewhere in the middle
						last->nextWord = curr->nextWord;					

					curr = last->nextWord;
				}
	
				// In palce, don't move
				else
				{
					last = curr;
					curr = curr->nextWord;				
				}
			}
		}
	}
	
	// Display sorted structured linked list
	for (i=0; i<26; i++)
	{
		wordPtr curr = table[i].firstWord;
		while (curr != NULL)
		{
			cout << curr->word << endl;
			curr = curr->nextWord;		
		}
	}
	
	return 0;
}

[GCDEF]

Kudos for using code tags and nicely formatted code for your first post. Have you drive walking through the code with the debugger?

[michaelhart]

Thanks. I have not walked through with a debugger as I am not that experienced with them. If the program would crash I could probably step through it and see what's going on, but it executes fine. The pointer addressing would probably confuse the heck out of me even I did step through it.

given the code here:

struct wordNode;
typedef wordNode* wordPtr;

struct bucket 
{
	wordPtr firstWord, lastWord;
};

struct wordNode
{
	string word;
	wordPtr nextWord;
};

What would be the proper way of assigning and moving new nodes? Something is definitely failing in my pointer/addressing statements, I just can't figure out what.

[michaelhart]

Okay, I found an error, but there are still more apparently because now the program crashes.

line 52:

if (table[idx].firstWord == NULL) table[idx].lastWord = tmp;

should be

if (table[idx].firstWord == NULL) table[idx].firstWord = tmp;

[joe_stoll]

the program is most likely crashing because one of your pointers is null trying to access something which causes an access violation
debug your code using break points

[michaelhart]

I believe the problem is somewhere in here. How would you do this without destroying the data your pointers point to? I guess that is the problem that I am having trouble wrapping my head around.

		
			curr = table[j].firstWord;
			last = NULL;
		
			while (curr != NULL)
			{
				idx = curr->word[i] - 'A';
								
				if (idx != j) 								// Move
				{
					// Move to new correct list
					if (table[idx].firstWord == NULL)
						table[idx].firstWord = curr;
	
					else
						table[idx].lastWord->nextWord = curr;
						
					table[idx].lastWord = curr;

					
					
					// Remove from current list
					if (last == NULL) 						// First word in the list
					{
						if (curr->nextWord == NULL)			// and last word in the list
						{
							table[j].firstWord = NULL;
							curr               = NULL;
						}
							
						else 								// Not last word in the list
						{
							table[j].firstWord = curr->nextWord;
							last = curr;
							curr = curr->nextWord;
						}
					}
					
					else if (curr->nextWord == NULL) 		// Last word in the list
					{
						table[j].lastWord 	= last;
						curr           		= NULL;
						last->nextWord 		= NULL;	
						
					}

					else 									// Somewhere in the middle
					{
						last->nextWord	= curr->nextWord;	
						last 			= curr;
						curr 			= curr->nextWord;
					}
				}
	
				
				else 										// In palce, don't move
				{
					last = curr;
					curr = curr->nextWord;				
				}
			}

[Paul McKenzie]

Thanks. I have not walked through with a debugger as I am not that experienced with them.

A few things you have to know before you write a program:

1) It is imperative that you use the debugger. Using tools such as a debugger is mandatory if you want to write a non-trivial program successfully. No one is going to just eyeball your code and somehow run the computer in their heads -- anyone helping you would use the debugger.

Hit the F10 key and at least start the debugger. You won't know if it will confuse you or not if you don't at least get it going.

The pointer addressing would probably confuse the heck out of me even I did step through it.

2) When you write a program, it's expected that you know what each and every line of code you write is doing. If you don't know what each line does, then what you do is write a tiny program that lets you practice what you are trying to do. This is what every programmer from beginner to professional does -- they write smaller programs to familiarize themselves with a new function, syntax, whatever. Once they understand it, then they incorporate it into the larger, main program they are ultimately trying to write.

Given that, did you draw a diagram of what needs to be done, so that you know have an idea of what should be assigned where?

What would be the proper way of assigning and moving new nodes?
Something is definitely failing in my pointer/addressing statements, I just can't figure out what.

You point pointers to valid objects. That's all there really is to it. You have to manage the pointing of the pointers to these valid objects. The debugger would be used to see if the pointers are pointing to a valid object, and wherever you are accessing an object using a pointer.

Whether the object being pointed to is the one you want, or the one you expect, that is where logic comes into play, and you use the debugger to see if your logic is wrong.

headnode -> nextnode -> nextnode -> nextnode -> nextnode -> terminal

That is what you are striving for. So when you debug your code, you identify the head node and use the program to look at what its "next" pointer is pointing to. Then you look at that node and see what its "nextnode" is pointing to, etc.

And lastly, your program has memory leaks. You are using "new" and nowhere do you clean up the memory. If this is a school exercise, then this program is not complete unless you can go through that list and "delete" all of that memory allocated.

Regards,

Paul McKenzie

[Paul McKenzie]

I believe the problem is somewhere in here. How would you do this without destroying the data your pointers point to? I guess that is the problem that I am having trouble wrapping my head around.

OK, so place a breakpoint in this code, and starting at the breakpoint, step through the code a line at a time and observe each pointer and how they are changed and assigned.

If what is being done doesn't fit your design, then you know what you are doing wrong. Given that, what did you observe?

Regards,

Paul McKenzie

[michaelhart]

Thanks for the suggestion. I ran it through a debugger (never used one before) and found out that:

table[idx].lastWord = curr;
table[idx].lastWord->nextWord = NULL;

the last statement was unintentionally modifying curr->nextWord. So, I smacked myself in the forehead and am trying to figure out a work around without allocating more memory or throwing away the linked list altogether.

Any suggestions?

[ovidiucucu]

[ Moved thread ]