?
Solved

HELP wit linked list insert

Posted on 2003-03-31
4
Medium Priority
?
246 Views
Last Modified: 2013-12-14
I can't fugure this out.  When I insert a second item this program crashes.  Any help would be useful.

What it is supposed to do is have a user enter a word.
1.) If the word exists add one to the count
2.) If the word does not exist, add the word and add one to the count.


#include <iostream>
#include <cstddef> // FOR NULL USE
#include <string>

using namespace std;

struct WordList
{     int count;
     WordList *link;
     char item[];
};
typedef WordList* NodePtr;

void head_insert(NodePtr& head, char inWord[]);
void add_word (NodePtr& head);
void show_list(NodePtr& head);
void delete_list(NodePtr& head);

char inWord[20];
int aNumber=0;

int main()
{     NodePtr head=NULL;

     cout<<"Enter a word in lower case "<<endl;
     cout<<"Enter done when finished"<<endl;
     cin>>inWord;
     if(strcmp(inWord,"done")!=0)
          head_insert(head, inWord);
         
     add_word(head);
     show_list(head);
     delete_list     (head);

     return 0;
}
//*******************************************************
void add_word (NodePtr& head)
{     NodePtr currPtr=head;
     NodePtr prevPtr;
     NodePtr newNodePtr;
     
     
     cout<<"Enter a word in lower case "<<endl;
     cout<<"Enter done when finished"<<endl;
     cin>>inWord;
     if(strcmp(inWord,"done")!=0)
          {     if (strcmp(inWord,currPtr->item),0)
                    currPtr->count+1;
               else
                    {newNodePtr=new WordList;
                    strcpy(newNodePtr->item,inWord);
                    prevPtr=NULL;
                    currPtr=head;
                    while (currPtr!=NULL&&inWord>currPtr->item)
                    {     prevPtr=currPtr;
                         currPtr=currPtr->link;
                    }
     
                    newNodePtr->link=currPtr;
                    if(prevPtr==NULL)
                         head-newNodePtr;
               else
                    prevPtr->link=newNodePtr;
          }
          }
}
//*******************************************************
void head_insert(NodePtr& head, char inWord[])
// INITIALIZES LINK LIST, SETS HEAD TO NULL
{     NodePtr temp_ptr;
     temp_ptr=new WordList;

     strcpy(temp_ptr->item,inWord);
     temp_ptr->count=1;
     
     temp_ptr->link=head;
     head=temp_ptr;
}
//*******************************************************
void show_list(NodePtr& head)
// DISPLAYS LIST TO SCREEN
{     NodePtr here=head;
     char tmpout;
         
     while (here!=NULL)
     {    
          if (tmpout!=here->item[0])
               tmpout=here->item[0];
          else
               {cout<<"Letter "<<tmpout<<" words"<<endl;
               cout<<here->item<<" - "<<endl;
               cout<<here->count<<endl;
               here=here->link;
               }
     }
}
//*******************************************************
void delete_list(NodePtr& head)
// DELETES LIST TO RESTORE MEMORY
{     NodePtr here=head;
     NodePtr current=head;
     
     while (current !=NULL)
     {     current=current->link;
          delete here;
          here=current;
     }
}
//*******************************************************
0
Comment
Question by:hwg193
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 2
4 Comments
 
LVL 12

Accepted Solution

by:
Salte earned 80 total points
ID: 8237726
I didn't understand your code....

int main()
{     NodePtr head=NULL;

    cout<<"Enter a word in lower case "<<endl;
    cout<<"Enter done when finished"<<endl;
    cin>>inWord;
    if(strcmp(inWord,"done")!=0)
         head_insert(head, inWord);
         
This isn't a loop, you compare the word with 'done' and if it is not 'done' you call head_insert which has two pointers, one to head and one to the inWord.


    add_word(head);

Then after you inserted the word in the list with head_insert you call 'add_word()' to do what?

    show_list(head);
    delete_list     (head);

    return 0;
}


Now, there are obviously two functions that is of interest here, it is 'head_insert()' and 'add_word()' and what each of them do is of interest to us. Note that if word is 'done' the head_insert is not called but you nevertheless call add_word(). I believe that is also very possibly a mistake.

One other crucial point of problem is your declaration of the struct WordList:

struct WordList
{     int count;
    WordList *link;
    char item[];
};

This declares a struct without space for the word, it is a so-called incomplete struct and any use of such a struct must be used with caution. In particular 'new WordList' do NOT allocate space for the char.

void head_insert(NodePtr& head, char inWord[])
// INITIALIZES LINK LIST, SETS HEAD TO NULL
{     NodePtr temp_ptr;
    temp_ptr=new WordList;

WARNING WARNING!!!!!
     you allocate space for the wordlist element but have no room for the character buffer item.


    strcpy(temp_ptr->item,inWord);

As indicated by the warning above you here do a copy from the word to non-existent memory space. This is NOT correct and your program is likely to crash and wreck havoc.

    temp_ptr->count=1;
   
    temp_ptr->link=head;
    head=temp_ptr;
}

It appears that head_insert is supposed to take a string and a reference to a pointer and create a node holding that word. It also insert the element into the list at the front.

Now, let's see what add_word does:

void add_word (NodePtr& head)
{     NodePtr currPtr=head;
    NodePtr prevPtr;
    NodePtr newNodePtr;
   
   
    cout<<"Enter a word in lower case "<<endl;
    cout<<"Enter done when finished"<<endl;
    cin>>inWord;

    ok, so add_word write a prompt to enter more words into the list?

    Again, I see no loop here but a test for the word 'done'.

    if(strcmp(inWord,"done")!=0)

// Enter the if test if word is not 'done'.

         {     if (strcmp(inWord,currPtr->item),0)

And this syntax is supposed to mean?????

strcmp(a,b) is a function and it takes to strings as input
if they are equal it returns 0 as result, if a < b then a negative result is returned and if a > b then a positive value is returned.

if (strcmp(inWord,currPtr->item) <= 0)

might be a reasonable if test, actually any relation <, <=, >, >=, !=, ==, might make sense depending on circumstance and what you want. However, the , operator isn't a relational operator and so it doesn't make sense here. It actually make very little sense since the comma operator ignores the result from strcmp and return 0 so the test above is always false and never true.
This means that currPtr->count+1 is never executed. It doesn't make sense either so it doesn't really matter you might say but I believe your intention was that that statement should be executed under some condition.

                   currPtr->count+1;
As already said, this statement doesn't make sense either, you take currPtr -> count, adds 1 and then throws away the result. It is possible you meant currPtr -> count++ that would make sense if you want currPtr -> count to indicate how many occurences of a currPtr -> item is found in the list and you actually just have one entry for each of those. If so the test above should absolutely be something like:

if (strcmp(inWord,currPtr->item) == 0)
   currPtr -> count++;

However, that makes us wonder about other parts of the code.

              else

You enter here if the test is false, as the test is originally written you always come here since the test is false but if the test is correct to == 0 you will come here whenever the two strings are different. There is then a question of what to do if they are different. in one case you might want to advance further to the next list element and in another case you will consider that the element isn't in the list and so you will create a new element. This calls for another if test but you don't have that and so the function is most likely very wrong. I don't know if you plan to keep the list sorted in ascending order or in descending order and which one of the cases should do what depends on that choice. If the list is to be kept in ascending order you probably should have a test like:

if (strcmp(inWord,currPtr -> item) < 0)
   // here inWord is smaller than currPtr so it should be before currPtr, so you should insert the element.

else
   // Here inWord comes after currPtr and so you should advance currPtr to next pointer and examine that element.

   I.e. we need a loop, I see no loop in your code so this won't happen either.

Another thing is that it is silly to call strcmp() twice with the same strings, you will get the same result both times so a better way is to save the return value in a temporary variable and then use that, so instead of

if (strcmp(a,b) == 0)
   blah blah blah;
else if (strcmp(a,b) < 0)
   blah blah blah;
else
   blah blah blah;

it is better to write:

int cmpres = strcmp(a,b);
if (cmpres == 0)
   blah blah blah;
else if (cmpres < 0)
   blah blah blah;
else
   blah blah blah;

                   {newNodePtr=new WordList;

Again, we have the same WARNING WARNING!!!!!
you allocate room for the node but NOT room for the item in the node. The following strcpy will therefore most likely crash your program.

                   strcpy(newNodePtr->item,inWord);

                   prevPtr=NULL;
                   currPtr=head;

Here you have a while loop, I believe this is because you want to insert the element in the list and you always insert the element at the end of the list. If this is your intention then that is fine, but beware that if you want to keep a count etc it is easier if you keep the list sorted and in particular since you already have the correct place to insert the list (if you had the while loop outside the if test) there would be no need for any while loop at this point since the element should be inserted just before currPtr since strcmp(inWord,currPtr->item) > 0 (or < 0 if you sort the list the other way).

                   while (currPtr!=NULL&&inWord>currPtr->item)
                   {     prevPtr=currPtr;
                        currPtr=currPtr->link;
                   }
   
                   newNodePtr->link=currPtr;
                   if(prevPtr==NULL)
                        head-newNodePtr;
              else
                   prevPtr->link=newNodePtr;
         }
         }
}

So yes, your program crash but there are also numerous other errors in your program logic, you have a lot of work before you get this program in shape.

To allcoate room for the item you also need to allcoate room for the word, this can be done this way:

size_t wlen = strlen(inWord); // length of the word.

NodePtr p = NodePtr(new char[sizeof(WordList) + wlen + 1]);

A few notes about this is required:

1. The size of space allocated in that array is sizeof(WordList) - the size of the node except the item plus wlen - the size of the word plus 1 char for the null byte.

2. The struct WordList cannot have a constructor or destructor, if it does you need to do something more to get this to work properly. In your case it is a simple struct without constructors and destructors so it should be fine.

3. When you delete the node you need to cast it back to a char pointer since that was what you allocated, so to delete the WordList item you need to do this:

char * cp = (char *)(NodePtrValue);
delete [] cp;

So the delete_list function is also wrong, it should cast the variable 'here' to a char * variable as I indicated above before it deletes it.

Using structs with unspecified number of characters at the end is possible and useful at times but it does require some discipline when coding. You do not follow that discipline and so your program will crash. You should leave such programming to 'experts' and since you have inWord defined as 20 bytes long why not declare:

struct WordList
{     int count;
    WordList *link;
    char item[20];
};

and get rid of the problem. This struct can be used as you use it above. when you say new WordList with this definition you will allocate room for 20 bytes for item and everything's fine (provided each word is no more than 19 characters). True if a word is only 3 characters you will waste 16 bytes but I think it is safer to waste 16 bytes per node than to use advanced programming features you do not understand.

Alf
0
 
LVL 3

Expert Comment

by:jcgd
ID: 8239595
#include <iostream>
#include <cstddef> // FOR NULL USE
#include <string.h>

//using namespace std;

struct WordList
{     int count;
    WordList *link;
    char *item;
};
typedef WordList* NodePtr;

void head_insert(NodePtr* head, char inWord[]);
void add_word (NodePtr* head);
void show_list(NodePtr& head);
void delete_list(NodePtr* head);

char inWord[20];
int aNumber=0;

int main()
{     NodePtr head=NULL;

    cout<<"Enter a word in lower case "<<endl;
    cout<<"Enter done when finished"<<endl;
    cin>>inWord;
    if(strcmp(inWord,"done")!=0)
         head_insert(&head, inWord);
         
    add_word(&head);
    show_list(head);
    delete_list     (&head);

    return 0;
}
//*******************************************************
void add_word (NodePtr *head)
{    
      NodePtr currPtr=NULL;
    NodePtr prevPtr;
    NodePtr newNodePtr;
      while(1)
           {
           currPtr=*head;
           cout<<"Enter a word in lower case "<<endl;
           cout<<"Enter done when finished"<<endl;
           cin>>inWord;
           if(strcmp(inWord,"done")!=0)
                    {
                    while (currPtr)
                         {
                              if (strcmp(inWord,currPtr->item)==0)
                                   {
                                   currPtr->count++;
                                   break;
                                   }
                              else
                                   {
                                   currPtr = currPtr->link;
                                   }
                         }
                    if (currPtr==NULL)
                         {
                         newNodePtr=new WordList;
                      newNodePtr->item = new char[strlen(inWord) + 1];
                      newNodePtr->count = 1;
                      newNodePtr->link = NULL;
                      strcpy(newNodePtr->item,inWord);
                          currPtr  = newNodePtr;
                         currPtr->link = *head;
                         *head=currPtr;
                      //(*head)->link = currPtr;
                    }
                }
           else
                break;
           }
}
//*******************************************************
void head_insert(NodePtr *head, char inWord[])
// INITIALIZES LINK LIST, SETS HEAD TO NULL
     {    
      if (*head==NULL)
           {
           *head=new WordList;
               (*head)->item = new char[strlen(inWord) + 1];
               strcpy((*head)->item,inWord);
               (*head)->count=1;
               (*head)->link =NULL;
           }
     }

//*******************************************************
void show_list(NodePtr& head)
// DISPLAYS LIST TO SCREEN
{     NodePtr here=head;
    char tmpout;
         
    while (here!=NULL)
    {    
         if (tmpout!=here->item[0])
              tmpout=here->item[0];
         else
              {cout<<"Letter "<<tmpout<<" words"<<endl;
              cout<<here->item<<" - "<<endl;
              cout<<here->count<<endl;
              here=here->link;
              }
    }
}
//*******************************************************
void delete_list(NodePtr* head)
// DELETES LIST TO RESTORE MEMORY

     {
          NodePtr here=*head;
          NodePtr current=*head;
   
    while (current !=NULL)
    {     current=current->link;
         delete here;
         here=current;
    }
}
//*******************************************************
0
 
LVL 12

Expert Comment

by:Salte
ID: 8239667
jcgd,

I believe what hwg needs is not just a dump of a program that works, he had so many problems that what I think is more valuable to him is some explanation why his code has problems and what your code does to address those problems.

Please post some comments and/or notes here and there along with your code.

Alf
0
 

Author Comment

by:hwg193
ID: 8244931
Thanks for the quick response Alf.

After making the change, char item[20], and fixing those typos I had in the program, I was able to get it to work without crashing.

I know I didnt have the loop working in the add_word function, and with it crashing on the sedond word entry, it was hard to work on the logic of the rest of the problem, such as making sure the insert was being sorted correctly.

The C++ class that I am in is just lecture with no lab time. So when i have a problem, I e-mail the instructor and it takes a day or two for him to e-mail me back.

0

Featured Post

Free Tool: Site Down Detector

Helpful to verify reports of your own downtime, or to double check a downed website you are trying to access.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Many modern programming languages support the concept of a property -- a class member that combines characteristics of both a data member and a method.  These are sometimes called "smart fields" because you can add logic that is applied automaticall…
Update (December 2011): Since this article was published, the things have changed for good for Android native developers. The Sequoyah Project (http://www.eclipse.org/sequoyah/) automates most of the tasks discussed in this article. You can even fin…
This tutorial covers a step-by-step guide to install VisualVM launcher in eclipse.
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
Suggested Courses

765 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question