Hello, I am having some trouble traversing backwards through a double linked list. Basically this program pulls words from a text file (I have attached the file I am using), corrects the words and stores them in an array of pointers (one pointer per letter of alphabet) of double linked lists. We have to traverse forward through each double linked list and count the words, then traverse backwards to display the words. My count is working fine, but I can't seem to traverse backwards to display the words. Below is my program so far. The problem lies between lines 512 and 527. The program compiles as it is now because my loop is never entered on line 520. If I change the code so the loop runs, my program crashes. Any tips on how to fix this problem?? Thanks in advance! Terri

//*****************************************************************************
//  CODE FILENAME:	
//  DESCRIPTION:	Program analyzes words in a text file. 
//  DATE:		    
//  DESIGNER:	    
//  FUNCTIONS:	    1) Main: Calls functions, closes files, closes program
//                  2) 
//*****************************************************************************


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

using namespace std;
// Global constants:

const int SIZE_ALPHABET = 26; // number of letters in alphabet

struct word{
    string newWord;
    word *next;
    word *back;
};
 
word *letter[SIZE_ALPHABET];

// Function Prototypes 
bool Verify_Command_Line(int argc);
bool Open_Verify_Data_File(char *argv[], ifstream &inFile, string &filename);
word* Initialize_Linked_Lists();
void Read_File(string &getWord, ifstream &inFile);
void Initialize_Array();
bool Discard_Word(string getWord);
void Correct_Word(string &getWord);
void To_Upper(string &getWord);
//bool Find_In_List(wordList *letter[], string getWord);
word* Add_To_List(string getWord, int &wordCount);
void Display_Results(int wordCount, string filename, int &count);
int Count_Words(word *&pWalker, int &count);
void Display_Words (word *pWalker, int &count);


//*****************************************************************************
//  FUNCTION: Main
//  DESCRIPTION: Calls other functions and closes input and output files
//  INPUT: 
//      Parameters: N/A
//      Keyboard: N/A
//      File: N/A
//  OUTPUT: 
//      Return Val: N/A
//      Parameters: N/A
//      Display: N/A
//      File: N/A
//  CALLS TO: Read_File, Sort_Arrays, Output_To_File, User_Choice,
//            Search_For_Id, Final_Output
//*****************************************************************************
int main(int argc, char *argv[])
{
    
    ifstream inFile;        // variable to read data in from file
    ofstream outFile;       // variable to output data to file
    bool endProg;
    word *newWord;
    string getWord;
    bool discardWord;
    string correctWord;
    word *nextNewWord;
    int wordCount = 0;
    string filename;
    int count;


    endProg = Verify_Command_Line(argc);
    
    if(!endProg)
    {
    
      endProg = Open_Verify_Data_File(argv, inFile, filename);
    
      if (!endProg)
      {
        
        newWord = Initialize_Linked_Lists();       
        Initialize_Array();
        
        while (!inFile.eof())
        {
             Read_File(getWord, inFile); 
             discardWord = Discard_Word(getWord);
     
                   if(discardWord == false)
                   {
                       Correct_Word(getWord);
                       To_Upper(getWord);
                       nextNewWord = Add_To_List(getWord, wordCount); 
                       
                   }
                   
        }
        
        Display_Results(wordCount, filename, count);           
    }
}

    inFile.close();     // closes input file

    cout << endl << endl;
    
    system ("PAUSE");
    
    return 0;

}

//*****************************************************************************
//  FUNCTION: Verify_Command_Line
//  DESCRIPTION: Verifies that a command was given on the command line.
//  INPUT: 
//      Parameters: argc
//      Keyboard: N/A
//      File: N/A
//  OUTPUT: 
//      Return Val: 1, if command line argument not given
//      Parameters: N/A
//      Display: Error message if filename not listed as a command line
//               argument.
//      File: N/A
//  CALLS TO: N/A
//*****************************************************************************
bool Verify_Command_Line(int argc)
{
    bool endProg = true;
     
    if (argc <= 1)
    {
      
      cout << endl << "The data file name was not given as an argument"
           << " on the command line." << endl << "Please give the name of"
           << " your data file as a command line argument, and " << endl
           << "run the program again." << endl << endl;
      return endProg;
    }
    
    else
    {
        endProg = false;
        return endProg;
    }
     
} // End of function

//*****************************************************************************
//  FUNCTION: Open_Verify_Data_File
//  DESCRIPTION: Verifies that the given file name exists. If so, then opens
//               file.
//  INPUT: 
//      Parameters: argv
//      Keyboard: N/A
//      File: N/A
//  OUTPUT: 
//      Return Val: 2, if data file does not exist
//      Parameters: N/A
//      Display: Error message if data file does not exist.
//      File: N/A
//  CALLS TO: N/A
//*****************************************************************************

bool Open_Verify_Data_File(char *argv[], ifstream &inFile, string &filename)
{

    bool endProg = true;
    
    //ifstream inFile;  // file input stream
    //string filename;  // name of file given as command line argument
    
    filename = argv[1];

    inFile.open(filename.c_str());
    
    if(!inFile)
    {
      cout << "I'm sorry, that filename does not exist. Please re-enter"
           << endl << "the file name as a command line argument and run the"
           << endl << "program again." << endl << endl;
      return endProg;

    }
    
    else
    {
      endProg = false;
      return endProg;
    }
    
}

//*****************************************************************************
//  FUNCTION: Initialize_Linked_Lists
//  DESCRIPTION: Initializes double linked list.
//  INPUT: 
//      Parameters: argv
//      Keyboard: N/A
//      File: N/A
//  OUTPUT: 
//      Return Val: 2, if data file does not exist
//      Parameters: N/A
//      Display: Error message if data file does not exist.
//      File: N/A
//  CALLS TO: N/A
//*****************************************************************************

word* Initialize_Linked_Lists()
{

// function to create list

  char ch;
    
  // attempt to allocate list structure
  word *newWord = new (nothrow) word;
 
  // check if allocation successful
  if (newWord == NULL) {
     cout << "Error - out of heap space!!" << endl;
     cout << "Press C to continue: ";
     cin >> ch;
  }
  else
  {
     // initialize to empty list
     newWord = NULL;
     //newWord->next = NULL;
     //newWord->back = NULL;

  }
 
  return newWord;

 }

//*****************************************************************************
//  FUNCTION: Initialize_Array
//  DESCRIPTION: Initializes the array of pointers.
//  INPUT: 
//      Parameters: N/A
//      Keyboard: N/A
//      File: N/A
//  OUTPUT: 
//      Return Val: N/A
//      Parameters: N/A
//      Display: N/A
//      File: N/A
//  CALLS TO: Initialize_Linked_Lists
//***************************************************************************** 
void Initialize_Array()
{
     
     for (int count = 0; count < SIZE_ALPHABET; count++)
     {    
         //currentWord = Initialize_Linked_Lists();
        // cout << currentWord << endl;
         letter[count] = NULL;
         //cout << letter[count] << endl;
         
     }   
}

//*****************************************************************************
//  FUNCTION: Read_File
//  DESCRIPTION: Gets word from data file and passes back to main.          
//  INPUT: 
//      Parameters: N/A
//      Keyboard: N/A
//      File: N/A
//  OUTPUT: 
//      Return Val: N/A
//      Parameters: getWord, inFile
//      Display: N/A
//      File: N/A
//  CALLS TO: N/A
//*****************************************************************************
void Read_File(string &getWord, ifstream &inFile)
{
     inFile >> getWord;

}

//*****************************************************************************
//  FUNCTION: Discard_Word
//  DESCRIPTION: Determines whether a word should be discarded or not. Words are
//               discarded when a number is present.       
//  INPUT: 
//      Parameters: N/A
//      Keyboard: N/A
//      File: N/A
//  OUTPUT: 
//      Return Val: discardWord (true or false)
//      Parameters: getWord
//      Display: N/A
//      File: N/A
//  CALLS TO: N/A
//*****************************************************************************  
bool Discard_Word(string getWord)
{
     
     int len;
     bool discardWord = false;
     int num;
     
     len = getWord.length();
     
     for (int count = 0; count < len; count++)
     {
         if (getWord[count] < '9' && getWord[count] > '0')
         {          
            discardWord = true;
            count = 100;
         }
     }
     
     return discardWord;
}
     
//*****************************************************************************
//  FUNCTION: Correct_Word
//  DESCRIPTION: Removes non-letter characters from words except for ' and -.         
//  INPUT: 
//      Parameters: getWord
//      Keyboard: N/A
//      File: N/A
//  OUTPUT: 
//      Return Val: N/A
//      Parameters: getWord
//      Display: N/A
//      File: N/A
//  CALLS TO: N/A
//*****************************************************************************
void Correct_Word(string &getWord)
{
     
     int len;
     
     len = getWord.length();
     
     for (int count = 0; count < len; count++)
     {
         if((getWord[count] >= '!' && getWord[count] <= '&') ||
            (getWord[count] >= '(' && getWord[count] <= ',') ||
            (getWord[count] >= '.' && getWord[count] <= '/'))
                getWord.erase(count, 1);
     } 
     
} 
   
//*****************************************************************************
//  FUNCTION: To_Upper
//  DESCRIPTION: Capitalizes all letters.          
//  INPUT: 
//      Parameters: getWord
//      Keyboard: N/A
//      File: N/A
//  OUTPUT: 
//      Return Val: N/A
//      Parameters: getWord
//      Display: N/A
//      File: N/A
//  CALLS TO: N/A
//*****************************************************************************
void To_Upper(string &getWord)
{
    std::transform(getWord.begin(), getWord.end(), getWord.begin(), ::toupper);    
}

//*****************************************************************************
//  FUNCTION: Add_To_List
//  DESCRIPTION: Adds word to array of pointers. Determines which pointer to 
//               use and also whether word is added to an empty list or to the
//               top of the double linked list.        
//  INPUT: 
//      Parameters: getWord, letter[], currentWord
//      Keyboard: N/A
//      File: N/A
//  OUTPUT: 
//      Return Val: N/A
//      Parameters: letter[]
//      Display: N/A
//      File: N/A
//  CALLS TO: N/A
//*****************************************************************************    
word* Add_To_List(string getWord, int &wordCount)
{

     bool wordFound;
     char firstChar = getWord[0];
     int index = firstChar - 'A';
     
  
     word *nextNewWord = new (nothrow) word;
     //wordFound = Find_In_List(letter, getWord);
     //if (!(wordFound))
    
    nextNewWord->newWord = getWord;
    //cout << nextNewWord->newWord << endl;
    nextNewWord->next = NULL;
    nextNewWord->back = NULL;
       
    if(letter[index] == NULL)
    { 
      letter[index] = nextNewWord;                               
    }

    else
    {              
        nextNewWord->next = letter[index];
        letter[index]->back = nextNewWord->next;
        letter[index] = nextNewWord;
    }
    
    wordCount++;
    
    return nextNewWord;
}      

/*
//*****************************************************************************
//  FUNCTION: Find_In_List
//  DESCRIPTION: Searches the appropriate linked list   
//  INPUT: 
//      Parameters: getWord, letter[], currentWord
//      Keyboard: N/A
//      File: N/A
//  OUTPUT: 
//      Return Val: N/A
//      Parameters: letter[]
//      Display: N/A
//      File: N/A
//  CALLS TO: N/A
//*****************************************************************************
bool Find_In_List(wordList *letter[], string getWord)
{
     
     bool wordFound = false;
     
     int firstLetter = getWord[0];
     
     for (int count = 0; count < SIZE_ALPHABET; count++)
     {    
         if (strcmp(letter[firstLetter], getWord) ) 
            wordFound = true;
         
     }   
     
    return wordFound;
} 

*/
//*****************************************************************************
//  FUNCTION: Count_Words
//  DESCRIPTION: Counts number of words in each linked list. 
//  INPUT: 
//      Parameters: getWord
//      Keyboard: N/A
//      File: N/A
//  OUTPUT: 
//      Return Val: N/A
//      Parameters: letter[]
//      Display: N/A
//      File: N/A
//  CALLS TO: N/A
//*****************************************************************************

int Count_Words(word *&pWalker, int &count)
{
    int numWords = 0;
       
    pWalker = new (nothrow) word;
    

    pWalker = letter[count];
    
    while (pWalker != NULL)
    {
        letter[count]->back = pWalker->next;
        pWalker = pWalker->next;
        numWords++;
    }
     
    return numWords;     
}     
     
//*****************************************************************************
//  FUNCTION: Display_Words
//  DESCRIPTION: Displays the words in each linked list.
//  INPUT: 
//      Parameters: 
//      Keyboard: N/A
//      File: N/A
//  OUTPUT: 
//      Return Val: N/A
//      Parameters: 
//      Display: N/A
//      File: N/A
//  CALLS TO: N/A
//*****************************************************************************

void Display_Words (word *pWalker, int &count)
{
    
    
    word *pCurrent = new (nothrow) word;

    pCurrent = pWalker;
    
    while (pCurrent != NULL)
    { 
        cout << pCurrent->newWord << " ";
        pCurrent = pCurrent->back;

    }     

}
//*****************************************************************************
//  FUNCTION: Display_Results
//  DESCRIPTION: Displays final results to screen.  
//  INPUT: 
//      Parameters: getWord
//      Keyboard: N/A
//      File: N/A
//  OUTPUT: 
//      Return Val: N/A
//      Parameters: letter[]
//      Display: N/A
//      File: N/A
//  CALLS TO: N/A
//*****************************************************************************

void Display_Results(int wordCount, string filename, int &count)
{
     int numWords;
     word *pWalker;
     char let;
     
     cout << endl << "Results for file " << filename << ": " 
          << wordCount << " total words processed." << endl << endl;
          
     // runs thru array to count words:
             
             for (count = 0; count < SIZE_ALPHABET; count++)
             {
                 if(letter[count] != NULL)
                 {
                   numWords = Count_Words(pWalker, count);
                   let = 'A' + count;
                   cout << numWords << " word(s) beginning with '" << let
                        << "':" << endl;
                   Display_Words (pWalker, count);
                   
                 }
             }
}
Attachments
She'&s/ going to go w/o me.

you can start by deleting line 516 because it is nothing more than a huge memory leak.

When walking backwards you can't check for pCurrent == NULL because what you want to check for is while pCurrent != the head of the linked list, and the head is never NULL unless its an empty list. I assume pWalker is the point at which you want to start walking backwards, but what is the head of the linked list? If it isn't a gobal variable then you will have to pass it to the display function.

Ok, would I just need to make a new pointer like:

word *pCurrent;

?

Ok, I was trying that, but still couldn't get it right. The head pointer is letter[count].

Here is what I tried that causes a crash:

word *pCurrent;

    pCurrent = pWalker;
    
    while (pCurrent != letter[count])
    { 
        cout << pCurrent->newWord << " ";
        pCurrent = pCurrent->back;

    }

When I add cout << "test" to see where the crash occurs, it occurs during this line: cout << pCurrent->newWord << " ";

I'm starting to step through you program now. So far it is full of memory leaks. First place I see is in the function Initialize_Linked_Lists(). First you allocate a word object then turn around and set the pointer to NULL and return a NULL pointer. Huge mistake.

Correct_Word(). When you erase a letter out of the word you have to adjust variable len in the loop because you changed the length of the string. Also reset count to -1 so that it starts that loop all over again.

Hmm, I will have to re-read my material then. I thought you had to allocate memory. :-(

you do have to allocate memory, the problem is that you tossed it into the bit bucket by setting it to NULL in the else statement. You should not have commented out the two lines that set the next and previous variables to NULL -- that was correct.

Display_words() -- you do have to test pWalker for NUL because I see where a NULL pointer is being passed to that function (Display_Results()). Just a simple test will do it.

void Display_Words (word *pWalker, int &count)
{
    word *pCurrent;
    if(pWalker != NULL)
    {
        pCurrent = pWalker;
    
        while (pCurrent != letter[count])
        { 
            cout << pCurrent->newWord << " ";
            pCurrent = pCurrent->back;
        }

    }     

}

After making the above corrections I get this output, using the file that you posted

Results for file ..\TextFile1.txt: 6 total words processed.

2 word(s) beginning with 'G':
1 word(s) beginning with 'M':
1 word(s) beginning with 'S':
1 word(s) beginning with 'T':
1 word(s) beginning with 'W':


Press any key to continue . . .

Hi Ancient Dragon...I appreciate your help. I have to run now, but I will check back in tomorrow and continue working on this. Thank you!

hmm, it should actually display the word after it prints out the number of words from that list. Well, I will have to keep playing with it tomorrow. Thanks again.

Ok, when I traverse the list forward, I stop when pWalker = NULL. The last line of code that does this is: pWalker = pWalker->next . pWalker->next is null, so pWalker is set to NULL. So, in order for me to pass pWalker not as NULL, I will have to back up again in the list before I pass pWalker to the next function to traverse backwards. Is this correct so far in my thinking?

That's not right. Look at function Display_Results(). pWalker is declared in that function and never set to anything. Its just a pointer that points to some random memory location, unless of course you changed the program since the last post.

Well, I use pWalker in the Count_Words() function to traverse the linked list forward (and count the number of words in the lists). So at the end of that function, pWalker is Null because that is when my loop terminates. Then I was passing pWalker out of that function and into Display_Words. Then I created another pointer, pCurrent, in Display_Words and assigned that pointer value the value from pWalker (which is NULL). Then I wanted to use pCurrent to walk backwards through the linked list. Well, that was the plan anyways.

The line where pWalker gets its value is 490.

you know, shouldn't walking backwards in a double linked list be just as easy as walking forward?? arrgh

you need to keep track of the last valid pointer as the loop is iterating through the linked list. Then after the loop terminates reset pWalker to the value of the last known good value. Something like this will probably work.

int Count_Words(word *&pWalker, int &count)
{
    int numWords = 0;
       
    pWalker = letter[count];
    word* pTail = pWalker;    
    while (pWalker != NULL)
    {
        letter[count]->back = pWalker->next;
        pTail = pWalker;
        pWalker = pWalker->next;
        numWords++;
    }
    pWalker = pTail;     
    return numWords;     
}

>>shouldn't walking backwards in a double linked list be just as easy as walking forward
Yes, but you have to start out with the last node in the linked list (or tail) -- NULL is not a valid pointer. Then when iterating backwards you can check for NULL because it need to check for the head of the linked list. So there are some differences in how you have to code it.

Well, I never was able to 100% walk backwards through my double-linked list, but I do appreciate all your help. I submitted my code as is and my professor sent me his solution. I don't want to post his code, but if anybody has a similar problem, a do_while loop also works to walk backwards thru linked list. Thanks again!

This question has already been answered. Start a new discussion instead.