Double Linked List Issue

[drake2212]

I am having an issue inserting the word into the correct list. Whenever I place a loop that loops while the file isn't at the end I get an infinite loop. Can I get some pointers on how to fix this?

Here is the text file I am using:

I am excited to be taking this class. Programming isn't
easy but I feel I am getting better. One day when I am
out of the military I hope to work for some IT business.
The job can't be part-time either!
67dd a09dd.

Here is the program file:

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

using namespace std;

const int MAX_SIZE = 26;

struct wordRec {
       string newWord;
       wordRec *previous;
       wordRec *next;
       };

void programIntro();
wordRec* initializeList ();
void initializeArray (wordRec *[], int& index);
void readTextFile (ifstream& wordIn, wordRec *letters[], int& index, int& wrdIndex);
void checkInputWord (ifstream& wordIn, string& word);
void insertWord (ifstream& wordIn, wordRec* [], int& index, string& word, int& wrdIndex);
void wordListPlacement (ifstream& wordIn, wordRec *letters[], int& index, int& wrdIndex);

int main (int argc, char* argv[]) {

    wordRec* letters[MAX_SIZE];
    wordRec *head = NULL;

    int count;
    int indexes;
    int wordCount;
    string words;
    int wordIndex;

    ifstream wordIn;

    programIntro();

    wordIn.open (argv[1]);

    if (!wordIn) {
       cout << "Error! Text File did not open!" << endl;
       system ("pause");
       return 1;
    }
    else 
       initializeArray (letters, indexes);
       readTextFile (wordIn, letters, indexes, wordIndex);
    wordIn.close ();

    system ("pause");
    return 0;
}

void programIntro ()

{
     cout << " ****************************************************************************" << endl;
     cout << "  This program will analyze words in a text file. This program creates an   "<< endl;
     cout << "  array of pointers which is used to store info about each letter in the " << endl;
     cout << "  alphabet. The array of pointers points to 26 doubly linked lists.  The text" << endl;
     cout << "  file will then be read into the program by a command line argument and after" << endl;
     cout << "  the file is validated,the array is initialized to NULL to represent 26 empty" << endl;
     cout << "  lists. Next, all the words in the text file will be read into the program."   << endl;
     cout << "  The words will be checked for correct format. No numbers all allowed and" << endl;
     cout << "  extra puntuation will be stipped off the word. After a word is deemed correct" << endl;
     cout << "  the word will be all capitalized. Then I will determine where each word in" << endl;
     cout << "  the file will be placed. The first letter determines this, and each letter " << endl;
     cout << "  (A-Z) represents the indexes in the array. No duplicate words will be stored" << endl; 
     cout << "  in the lists, and words will be added to the top of the lists. After ALL of" << endl;
     cout << "  the words in the file have been read, processed, and inserted into the proper" << endl;
     cout << "  list, all the words are counted, including duplicates. Then the words in each" << endl; 
     cout << "  list will be counted. After all this, the count in each list with words is" << endl;
     cout << "  output to the screen, along with words in that list, and the total number of" << endl;
     cout << "  words. Finally, the list with the most words in it will be displayed." << endl;
     cout << " *****************************************************************************" << endl << endl;

     system ("pause");     
     return;
}         


void initializeArray (wordRec *letters[], int& index)

{
     for (index = 0; index < MAX_SIZE; index++) {
         letters[index] = NULL;
     }

     return;
}

void readTextFile (ifstream& wordIn, wordRec *letters[], int& index, int& wrdIndex)

{    wordRec *head = letters[index];
     string word;
     char character;
     char letter;

      while (wordIn) {     
        wordIn >> word;    

        // calculates the specific list each word will go into
        character = word[0];
        letter = toupper(character);
        wrdIndex = letter - 'A';       

        // checks the word format for errors
        checkInputWord (wordIn, word);

        // uppercases all the words in the file
        for (int indx = 0; indx < word.size(); indx++) {
            word[indx] = static_cast<char>(toupper(word[indx]));
        }

     insertWord (wordIn, letters, index, word, wrdIndex);
     }
     return;
}

void checkInputWord (ifstream& wordIn, string& word)

{
     // strips off any punctuation if there is any
      for (int index = 0; index < word.length(); index++) {
         if ((ispunct(word[index])) && (word[index] != '\'') && (word[index] != '-')) {
            word.erase(index);
         }
      }

      // ignores the word if it contains any digits and does not add it to the list!
      for (int index = 0; index < word.size(); index++) {
         if (isdigit (word[index])) {
            wordIn.ignore (word[index], word.length() );
         }
      }

     return;
}    

void insertWord (ifstream& wordIn, wordRec *letters [], int& index, string& word, int& wrdIndex)

{
     wordRec *head = NULL;
     wordRec *newNode = NULL;

      if (head == NULL) {
           newNode = new (nothrow) wordRec;
           newNode->newWord = word;
           newNode->previous = NULL;
           newNode->next = newNode;

           if (head != NULL) 
              head->previous = newNode;

           head = newNode;
           letters[index] = head;
           letters[index]->next = head;
           letters[index]->previous = head;

           wordListPlacement (wordIn, letters, index, wrdIndex);    
      }
     return;
}

void wordListPlacement (ifstream& wordIn, wordRec *letters[], int& index, int& wrdIndex)

{
     wordRec *head = letters[index];
     int count = 0;

     if (wrdIndex == 0) {
        count++;
        letters[0] = head;
        cout << count << " A words: " << letters[0]->newWord << endl;
     }

     if (wrdIndex == 1) {
        count++;
        head = letters[index]; 
        letters[1] = head ;
        cout << count << " B Words: " << letters[1]->newWord << endl;
     }

     if (wrdIndex == 2) {
        count++;
        letters[2] = head;
        cout << count << " C Words: " << letters[2]->newWord << endl;
     }

     if (wrdIndex == 3) {
        count++;
        letters[3] = head;
        cout << count << " D Words: " << letters[3]->newWord << endl;
     }

     if (wrdIndex == 4) {
        count++;
        letters[4] = head;
        cout << count << " E Words: " << letters[4]->newWord << endl;
     }

     if (wrdIndex == 5) {
        count++;
        letters[5] = head;
        cout << count << " F Words: " << letters[5]->newWord << endl;
     }

     if (wrdIndex == 6) {
        count++;
        letters[6] = head;
        cout << count << " G Words: " << letters[6]->newWord << endl;
     }

     if (wrdIndex == 7) {
        count++;
        letters[7] = head;
        cout << count << " H Words: " << letters[7]->newWord << endl;
     }

     if (wrdIndex == 8) {
        count++;
        letters[8] = head;
        cout << count << " I Words: " << letters[8]->newWord << endl;
     }

     if (wrdIndex == 9) {
        count++;
        letters[9] = head;
        cout << count << " J Words: " << letters[9]->newWord << endl;
     }

     if (wrdIndex == 10) {
        count++;
        letters[10] = head;
        cout << count << " K Words: " << letters[10]->newWord << endl;
     }

     if (wrdIndex == 11) {
        count++;
        letters[11] = head;
        cout << count << " L Words: " << letters[11]->newWord << endl;
     }

     if (wrdIndex == 12) {
        count++;
        letters[12] = head;
        cout << count << " M Words: " << letters[12]->newWord << endl;
     }

     if (wrdIndex == 13) {
        count++;
        letters[13] = head;
        cout << count << " N Words: " << letters[13]->newWord << endl;
     }

     if (wrdIndex == 14) {
        count++;
        letters[14] = head;
        cout << count << " O Words: " << letters[14]->newWord << endl;
     }

     if (wrdIndex == 15) {
        count++;
        letters[15] = head;
        cout << count << " P Words: " << letters[15]->newWord << endl;
     }

     if (wrdIndex == 16) {
        count++;
        letters[16] = head;
        cout << count << " Q Words: " << letters[16]->newWord << endl;
     }

     if (wrdIndex == 17) {
        count++;
        letters[17] = head;
        cout << count << " R Words: " << letters[17]->newWord << endl;
     }

     if (wrdIndex == 18) {
        count++;
        letters[18] = head;
        cout << count << " S Words: " << letters[18]->newWord << endl;
     }

     if (wrdIndex == 19) {
        count++;
        letters[19] = head;
        cout << count << " T Words: " << letters[19]->newWord << endl;
     }

     if (wrdIndex == 20) {
        count++;
        letters[20] = head;
        cout << count << " U Words: " << letters[20]->newWord << endl;
     }

     if (wrdIndex == 21) {
        count++;
        letters[21] = head;
        cout << count << " V Words: " << letters[21]->newWord << endl;
     }

     if (wrdIndex == 22) {
        count++;
        letters[22] = head;
        cout << count << " W Words: " << letters[22]->newWord << endl;
     }

     if (wrdIndex == 23) {
        count++;
        letters[23] = head;
        cout << count << " X Words: " << letters[23]->newWord << endl;
     }

     if (wrdIndex == 24) {
        count++;
        letters[24] = head;
        cout << count << " Y Words: " << letters[24]->newWord << endl;
     }

     if (wrdIndex == 25) {
        count++;
        letters[25] = head;
        cout << count << " Z Words: " << letters[25]->newWord << endl;
     }

     return;
}

Any help will be greatly appreciated. Thanks for anyones help in advance.

Gerry

[Clinton Portis]

Here is your insert node function:

void insertWord (ifstream& wordIn, wordRec *letters [], int& index, string& word, int& wrdIndex)
{
     wordRec *head = NULL;     
     wordRec *newNode = NULL;
     
     if (head == NULL) 
     {
          newNode = new (nothrow) wordRec;
          newNode->newWord = word;
          newNode->previous = NULL;
          newNode->next = newNode;

     if (head != NULL)

          head->previous = newNode;

     head = newNode;
     letters[index] = head;
     letters[index]->next = head;
     letters[index]->previous = head;

wordListPlacement (wordIn, letters, index, wrdIndex); 
}

the code in red (above) I have a problem with, because you initialize a 'head' pointer to NULL at the beginning of your function, and then immediately perform a test to see if head == NULL, which will always be the case.

In your wordlist placement function, you have a bunch of the same stuff over and over... why not put it in a loop:

for(int i=0; i<26; i++)
{
     if (wrdIndex == [B]i[/B]) 
     {
          count++;
          letters[[B]i[/B]] = head;
          cout << count << " A words: " << letters[[B]i[/B]]->newWord << endl;
     }
}

Other than that, let me offer some simple pseudo code for node insertion into a double linked list:

*In a double-linked list, always keep a dedicated head pointer and tail pointer.

1. create a new node
2. populate the node with stuff
3. perform a list traversal to see where to put the new node. In this case, we traverse the list until we find a spot prior to where we want to insert:

//start from the beginning
node *temp = head_ptr;

//perform a basic list traversal until you find the right spot to add ye' node:
while(temp != NULL || temp->item < what_you_are_inserting)
{
     temp = temp->next;
}

//Now you either have the node prior to the spot you are looking for, or you have NULL.  If NULL, you can assume the item will go at the front of the list, back of the list, or the list has not been created.  We will test specifically for all these conditions.  If temp != NULL, insert the node [u]after[/u] the node contained in 'temp.'  Perform list insert:
{
     node *next_node;

     if(head_ptr == NULL)
     //The list has not been created.  Assign a head_ptr to the new node.  Make sure node->previous and node->next are assigned to NULL.

       if(temp == NULL && temp->next != NULL)
     //Perform a begining-of-list insert (make sure to assign node->previous = NULL.  Also make sure you assign this to your dedicated head_ptr)

     else if(temp == NULL && temp->previous != NULL)
     //Perform end-of-list insert (node->next will be assigned NULL, make sure you have a dedicated tail_ptr to this node)
   
     else //Perform middle of list insert:
     
     next_node = temp->next;        
     node_to_be_inserted->previous = temp;
     node_to_be_inserted->next = next_node;

All this is untested. If anyone sees an error in my logic or if anyone knows better pseudo code for node insertion please let me know.

[SriHanuman]

I am having an issue inserting the word into the correct list. Whenever I place a loop that loops while the file isn't at the end I get an infinite loop. Can I get some pointers on how to fix this?

Here is the text file I am using:

I am excited to be taking this class. Programming isn't
easy but I feel I am getting better. One day when I am
out of the military I hope to work for some IT business.
The job can't be part-time either!
67dd a09dd.

Here is the program file:

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

using namespace std;

const int MAX_SIZE = 26;

struct wordRec {
       string newWord;
       wordRec *previous;
       wordRec *next;
       };

void programIntro();
wordRec* initializeList ();
void initializeArray (wordRec *[], int& index);
void readTextFile (ifstream& wordIn, wordRec *letters[], int& index, int& wrdIndex);
void checkInputWord (ifstream& wordIn, string& word);
void insertWord (ifstream& wordIn, wordRec* [], int& index, string& word, int& wrdIndex);
void wordListPlacement (ifstream& wordIn, wordRec *letters[], int& index, int& wrdIndex);

int main (int argc, char* argv[]) {

    wordRec* letters[MAX_SIZE];
    wordRec *head = NULL;

    int count;
    int indexes;
    int wordCount;
    string words;
    int wordIndex;

    ifstream wordIn;

    programIntro();

    wordIn.open (argv[1]);

    if (!wordIn) {
       cout << "Error! Text File did not open!" << endl;
       system ("pause");
       return 1;
    }
    else 
       initializeArray (letters, indexes);
       readTextFile (wordIn, letters, indexes, wordIndex);
    wordIn.close ();

    system ("pause");
    return 0;
}

void programIntro ()

{
     cout << " ****************************************************************************" << endl;
     cout << "  This program will analyze words in a text file. This program creates an   "<< endl;
     cout << "  array of pointers which is used to store info about each letter in the " << endl;
     cout << "  alphabet. The array of pointers points to 26 doubly linked lists.  The text" << endl;
     cout << "  file will then be read into the program by a command line argument and after" << endl;
     cout << "  the file is validated,the array is initialized to NULL to represent 26 empty" << endl;
     cout << "  lists. Next, all the words in the text file will be read into the program."   << endl;
     cout << "  The words will be checked for correct format. No numbers all allowed and" << endl;
     cout << "  extra puntuation will be stipped off the word. After a word is deemed correct" << endl;
     cout << "  the word will be all capitalized. Then I will determine where each word in" << endl;
     cout << "  the file will be placed. The first letter determines this, and each letter " << endl;
     cout << "  (A-Z) represents the indexes in the array. No duplicate words will be stored" << endl; 
     cout << "  in the lists, and words will be added to the top of the lists. After ALL of" << endl;
     cout << "  the words in the file have been read, processed, and inserted into the proper" << endl;
     cout << "  list, all the words are counted, including duplicates. Then the words in each" << endl; 
     cout << "  list will be counted. After all this, the count in each list with words is" << endl;
     cout << "  output to the screen, along with words in that list, and the total number of" << endl;
     cout << "  words. Finally, the list with the most words in it will be displayed." << endl;
     cout << " *****************************************************************************" << endl << endl;

     system ("pause");     
     return;
}         


void initializeArray (wordRec *letters[], int& index)

{
     for (index = 0; index < MAX_SIZE; index++) {
         letters[index] = NULL;
     }

     return;
}

void readTextFile (ifstream& wordIn, wordRec *letters[], int& index, int& wrdIndex)

{    wordRec *head = letters[index];
     string word;
     char character;
     char letter;

      while (wordIn) {     
        wordIn >> word;    

        // calculates the specific list each word will go into
        character = word[0];
        letter = toupper(character);
        wrdIndex = letter - 'A';       

        // checks the word format for errors
        checkInputWord (wordIn, word);

        // uppercases all the words in the file
        for (int indx = 0; indx < word.size(); indx++) {
            word[indx] = static_cast<char>(toupper(word[indx]));
        }

     insertWord (wordIn, letters, index, word, wrdIndex);
     }
     return;
}

void checkInputWord (ifstream& wordIn, string& word)

{
     // strips off any punctuation if there is any
      for (int index = 0; index < word.length(); index++) {
         if ((ispunct(word[index])) && (word[index] != '\'') && (word[index] != '-')) {
            word.erase(index);
         }
      }

      // ignores the word if it contains any digits and does not add it to the list!
      for (int index = 0; index < word.size(); index++) {
         if (isdigit (word[index])) {
            wordIn.ignore (word[index], word.length() );
         }
      }

     return;
}    

void insertWord (ifstream& wordIn, wordRec *letters [], int& index, string& word, int& wrdIndex)

{
     wordRec *head = NULL;
     wordRec *newNode = NULL;

      if (head == NULL) {
           newNode = new (nothrow) wordRec;
           newNode->newWord = word;
           newNode->previous = NULL;
           newNode->next = newNode;

           if (head != NULL) 
              head->previous = newNode;

           head = newNode;
           letters[index] = head;
           letters[index]->next = head;
           letters[index]->previous = head;

           wordListPlacement (wordIn, letters, index, wrdIndex);    
      }
     return;
}

void wordListPlacement (ifstream& wordIn, wordRec *letters[], int& index, int& wrdIndex)

{
     wordRec *head = letters[index];
     int count = 0;

     if (wrdIndex == 0) {
        count++;
        letters[0] = head;
        cout << count << " A words: " << letters[0]->newWord << endl;
     }

     if (wrdIndex == 1) {
        count++;
        head = letters[index]; 
        letters[1] = head ;
        cout << count << " B Words: " << letters[1]->newWord << endl;
     }

     if (wrdIndex == 2) {
        count++;
        letters[2] = head;
        cout << count << " C Words: " << letters[2]->newWord << endl;
     }

     if (wrdIndex == 3) {
        count++;
        letters[3] = head;
        cout << count << " D Words: " << letters[3]->newWord << endl;
     }

     if (wrdIndex == 4) {
        count++;
        letters[4] = head;
        cout << count << " E Words: " << letters[4]->newWord << endl;
     }

     if (wrdIndex == 5) {
        count++;
        letters[5] = head;
        cout << count << " F Words: " << letters[5]->newWord << endl;
     }

     if (wrdIndex == 6) {
        count++;
        letters[6] = head;
        cout << count << " G Words: " << letters[6]->newWord << endl;
     }

     if (wrdIndex == 7) {
        count++;
        letters[7] = head;
        cout << count << " H Words: " << letters[7]->newWord << endl;
     }

     if (wrdIndex == 8) {
        count++;
        letters[8] = head;
        cout << count << " I Words: " << letters[8]->newWord << endl;
     }

     if (wrdIndex == 9) {
        count++;
        letters[9] = head;
        cout << count << " J Words: " << letters[9]->newWord << endl;
     }

     if (wrdIndex == 10) {
        count++;
        letters[10] = head;
        cout << count << " K Words: " << letters[10]->newWord << endl;
     }

     if (wrdIndex == 11) {
        count++;
        letters[11] = head;
        cout << count << " L Words: " << letters[11]->newWord << endl;
     }

     if (wrdIndex == 12) {
        count++;
        letters[12] = head;
        cout << count << " M Words: " << letters[12]->newWord << endl;
     }

     if (wrdIndex == 13) {
        count++;
        letters[13] = head;
        cout << count << " N Words: " << letters[13]->newWord << endl;
     }

     if (wrdIndex == 14) {
        count++;
        letters[14] = head;
        cout << count << " O Words: " << letters[14]->newWord << endl;
     }

     if (wrdIndex == 15) {
        count++;
        letters[15] = head;
        cout << count << " P Words: " << letters[15]->newWord << endl;
     }

     if (wrdIndex == 16) {
        count++;
        letters[16] = head;
        cout << count << " Q Words: " << letters[16]->newWord << endl;
     }

     if (wrdIndex == 17) {
        count++;
        letters[17] = head;
        cout << count << " R Words: " << letters[17]->newWord << endl;
     }

     if (wrdIndex == 18) {
        count++;
        letters[18] = head;
        cout << count << " S Words: " << letters[18]->newWord << endl;
     }

     if (wrdIndex == 19) {
        count++;
        letters[19] = head;
        cout << count << " T Words: " << letters[19]->newWord << endl;
     }

     if (wrdIndex == 20) {
        count++;
        letters[20] = head;
        cout << count << " U Words: " << letters[20]->newWord << endl;
     }

     if (wrdIndex == 21) {
        count++;
        letters[21] = head;
        cout << count << " V Words: " << letters[21]->newWord << endl;
     }

     if (wrdIndex == 22) {
        count++;
        letters[22] = head;
        cout << count << " W Words: " << letters[22]->newWord << endl;
     }

     if (wrdIndex == 23) {
        count++;
        letters[23] = head;
        cout << count << " X Words: " << letters[23]->newWord << endl;
     }

     if (wrdIndex == 24) {
        count++;
        letters[24] = head;
        cout << count << " Y Words: " << letters[24]->newWord << endl;
     }

     if (wrdIndex == 25) {
        count++;
        letters[25] = head;
        cout << count << " Z Words: " << letters[25]->newWord << endl;
     }

     return;
}

Any help will be greatly appreciated. Thanks for anyones help in advance.

Gerry

You really need to rewrite method insertWord() and think it through again.