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;
}