Problem with doubly linked lists

Question

drake2212 0 Newbie Poster

17 Years Ago

So this is my first time on here asking for help but I do visit this forum every now and again when I am taking a programming class. I am trying to get my doubly linked list to work correctly. Also I am having issues with parsing an input file. The function for the parsing is checkInputWord, and I wanted to see if you guys could see what I was messing up. Then in the insertWord function I am trying to either add a node to an empty array of pointers or one that already has some pointers. Here is my code and hopefully it is written well enough so you can understand what I am trying to do.

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

using namespace std;

const string WORD_FILE = "listing.txt";
const int MAX_SIZE = 26;


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

void programIntro();
void checkTextFile (ifstream& wordIn);
void initializeArray (wordList *wordArray[], int &index);
void readTextFile (ifstream& wordIn, wordList* wordArray [], int &index, int arrayCount, string &word1);
void checkInputWord (ifstream &wordIn, wordList* wordArray [], string &word1);
void insertWord (wordList *wordArray [], int &index, string &word1);

int main () {
    
    wordList* theWord[MAX_SIZE];
    int arrayCount = 0;
    int indexes = 0;
    int count;
    string words;
    
    ifstream wordIn;

    
    
    programIntro();
    checkTextFile (wordIn);
    initializeArray(theWord, indexes);
    readTextFile (wordIn, theWord, indexes, arrayCount, words); 
    
    
    system ("pause");
    return 0;
}

void programIntro ()

{
     cout << "**************************************************************************" <<endl;
     cout << "This program will search a text file and place the words in the text file" << endl;
     cout << "into a doubly linked list." << endl << endl;
     cout << "**************************************************************************" << endl;
     
     return;
     
     }

void checkTextFile (ifstream& wordIn) 

{
     
     wordIn.open (WORD_FILE.c_str());
     
     if (!wordIn) 
        cout << "Error! Text File did not open!" << endl;
        
     else
         cout << "File opened correctly!" << endl;
         
     return;
}



void initializeArray (wordList *wordArray[], int &index)

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

void readTextFile (ifstream& wordIn, wordList* wordArray [], int &index, int arrayCount, string &word1)

{
     
     char character;
     char letter;
     arrayCount = 0;
     string word;
     
     wordIn >> word1;
     cout << " READ WORD: " << word1 << endl;
     cout << " ARRAY count = " << arrayCount << endl;
     character = word1[0];
     letter = toupper(character);
     index = letter - 'A';
        
     cout << " Index for Word: " << index << endl << endl;
     checkInputWord (wordIn, wordArray, word1);
     insertWord (wordArray, index, word1);
     
     while (wordIn.eof() != true) {
           
           arrayCount++;
           wordIn >> word1;
           checkInputWord (wordIn, wordArray, word1);
           character = word1[0];
           letter = toupper(character);
           index = letter - 'A';
           cout << " READ WORD: " << word1 << endl;
           cout << " ARRAY count = " << arrayCount << endl;
           
           
           cout << " Index for Word: " << index << endl << endl;
          insertWord (wordArray, index, word1);
     
           }
     
     return;
}
 
void checkInputWord (ifstream &wordIn, wordList *wordArray [], string &word1)

{
     int curr_position = 0;
     int next_position;
     string badWord;
     
          next_position = word1.find_first_of(",.;:)(*&^%$#@!1234567890", curr_position);
          badWord = word1.substr(curr_position, next_position - curr_position);
          
          cout <<  " Current position: " << curr_position << endl << endl;
          cout << " Next position: " << next_position << endl ;
          cout << " Bad Word: " << badWord << endl ;
          
          if (next_position != string::npos) {
             curr_position = next_position + 1;
             next_position = word1.find_first_of(" ,.;:)(*&^%$#@!1234567890", curr_position);
             badWord = word1.substr(curr_position, next_position - curr_position);
             
             cout << " Current position: " << curr_position << endl << endl;
             cout << " Next position: " << next_position << endl << endl;
             cout << " Bad Word: " << badWord << endl << endl;
             } 
     return;
     
     }    
     
void insertWord (wordList *wordArray [], int &index, string &word1)

{
     wordList *theList;
     
           if (wordArray[index] == NULL) {
              theList = new wordList;
              theList->newWord = word1;
              theList->next = NULL;
              theList->previous = NULL;
              wordArray[index] = theList;
              cout << wordArray[index]->newWord << endl;
              }
              
           else {
              wordList *newNode = new wordList;
              newNode->newWord = word1;
              newNode->previous = NULL;
              newNode->next = wordArray[index];
              wordArray[index]->previous = newNode;
              wordArray[index]->next = wordArray[index]->previous;
              
              cout << wordArray[index]->previous->newWord << endl;
              cout << wordArray[index]->next->newWord<< endl;
          }
     
     
     return;
}

c++ linked-list

4 Contributors
5 Replies
120 Views
20 Hours Discussion Span
Latest Post 17 Years Ago Latest Post by drake2212

Dani AI

Generated 9 Months Ago

A few clear, practical fixes will stop the crashes and make the lists behave predictably.

The immediate cause of the runtime errors is pointer mis-linking when inserting nodes and then dereferencing null/invalid pointers. pointed at a "scope" issue — that comment is a common misconception: a local pointer variable going out of scope does not delete the heap object; what matters is whether any reachable pointer (for example the slot in wordArray) points at the newly allocated node. If the new node is not stored back into wordArray (or properly linked into the existing list), it becomes unreachable or leaves other pointers in an inconsistent state and dereferencing them will crash the program. and were right to suggest rethinking the insertion strategy (head vs. tail) — each approach requires careful updates to both next and previous and to the array slot that holds the list head.

A safe, simple pattern is insert-at-head: create the node, set node->next = head, node->previous = nullptr, if head set head->previous = node, then assign wordArray[index] = node. Guard every step: check index is 0..25, ensure the cleaned token is non-empty, and only dereference pointers after checking for null. Also prefer the while (wordIn >> token) read loop (avoid while (!eof())), so you only process successfully read tokens; see the behavior of operator>> on cppreference (https://en.cppreference.com/w/cpp/io/basic_istream/operator_gtgt).

Parsing: strip non-letter characters and normalize case before computing the index. A robust cleanToken that keeps only isalpha() characters (cast to unsigned char) will avoid indexing on punctuation or empty strings. Finally, run with AddressSanitizer or valgrind if available to catch invalid reads/writes, and add a short cleanup loop to delete lists when the program ends to avoid leaks. This checklist will quickly reveal the exact line that causes the crash and guide a small, targeted fix.

All 5 Replies

Agni 370 Practically a Master Poster

17 Years Ago

I don't really understand what you are doing. You just have an array of structures of type wordList. So basically you are not using the linked list at all !!! You create a node and insert it into the array. I don't think that's how you would be expected to use linked lists. You can use the list itself as a data-structure. Keep the start of the list with you and traverse it as per your needs.

kvprajapati 1,826 Posting Genius

17 Years Ago

Welcome drake2212,
Please post listing.txt file's content.
I have a suggestion, modify else block of insertWord.

wordList *newNode = new wordList;
              newNode->newWord = word1;
              newNode->previous = NULL;
              newNode->next=NULL;

              theList = wordArray[index];
              while(theList->next!=NULL)
              {
                  theList=theList->next;
              }
              theList->next=newNode;
              theList->next->previous=theList;

Reply to this topic

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

Member #248612 · Answer 1 · 2009-07-14T15:57:48+00:00

The wordList pointer in insertWord() goes out of scope (and therefore is lost) when insertWord returns to the calling function.

drake2212 0 Newbie Poster · Answer 2 · 2009-07-15T00:25:03+00:00

The wordList pointer in insertWord() goes out of scope (and therefore is lost) when insertWord returns to the calling function.

Do you have any suggestions on how to fix this?

drake2212 0 Newbie Poster · Answer 3 · 2009-07-15T00:27:23+00:00

Welcome drake2212,
Please post listing.txt file's content.
I have a suggestion, modify else block of insertWord.

wordList *newNode = new wordList;
              newNode->newWord = word1;
              newNode->previous = NULL;
              newNode->next=NULL;

              theList = wordArray[index];
              while(theList->next!=NULL)
              {
                  theList=theList->next;
              }
              theList->next=newNode;
              theList->next->previous=theList;

Here is what is in the text file.

I like this class. It is much of a challenge. I can't wait to get
some help on this program cuz it is tough!

I tred implementing your suggestion and when I try to output certain indexes I get runtime errors ... any suggestions?

Problem with doubly linked lists

Dani AI

Recommended Answers Collapse Answers

All 5 Replies

Recommended Answers