Linked List (reverse and alphebetical order)

[NinjaLink]

Hi, I have two seperate programs below writing a short program for each. My programs run, but sometimes when I rearrange things in my program to try to get it to work, I will receive an error. I am tried to figure it out since last night, but I am unable to. Any help is appreciate. Thank you

I am currently having problems and need help with:

1) Printing the words in reverse order in my printList function

2) Printing the words in alphabetical order in my printList function

Example of reverse order:

Input File:

hi
hello
hey
bye
adios

Example Output

adios
bye
hey
hello
hi

Example of alphabetical order

Input File:

hi
hello
hey
bye
adios

Example Output

adios
bye
hello
hey
hi

Reverse order

#include <fstream>


using namespace std;
struct nodeType
{
string info;
nodeType *link;

};

void createList(nodeType*& first, nodeType*& last);
void printList(nodeType*& first, nodeType*& last);


int main()
{

nodeType *first, *last;
string words;


ifstream inData;
ofstream outData;


createList(first,last);
printList(first,last);


system("PAUSE");
return 0;
}

void createList(nodeType*& first, nodeType*& last)
{

ifstream inData("input.txt");

string words;
int emptyList;
nodeType *newNode;

first = NULL;
last = NULL;

while(inData >> words)
{
newNode = new nodeType; // create new node
newNode->info = words;
newNode->link = NULL;

if (first == NULL)
{
first = newNode;
last = newNode;
}
else
{
last->link = newNode;
last = newNode;
}
} 


}

void printList(nodeType*& first,nodeType*& last) // print words in reverse order
{

ofstream outData("output.txt");

nodeType *current=first;
nodeType *reverse = NULL;

last=current->link;
current->link = reverse;
reverse = current;
current = last;

while (current != NULL)
{

outData << current->info <<endl;
current = current->link;
}
}

Alphabetical Order

#include <fstream>


using namespace std;
struct nodeType
{
    string info;
    nodeType *link;
    
};

void createList(nodeType*& first, nodeType*& last);
void printList(nodeType*& first, nodeType*& last);


int main()
{
    
    nodeType *first, *last;
    string words;
    
    
    ifstream inData;
    ofstream outData;

    
    createList(first,last);
    printList(first,last);
    
    
  system("PAUSE");
   return 0;
}

void createList(nodeType*& first, nodeType*& last)
{
     
    ifstream inData("input.txt");
     
    string words;
    int emptyList;
    nodeType *newNode;
    
    first = NULL;
    last = NULL;
    
    while(inData >> words)
    {
         newNode = new nodeType; // create new node
         newNode->info = words;
         newNode->link = NULL;
    
         if (first == NULL)
         {
            first = newNode;
            last = newNode;
         }
         else
         {
           last->link = newNode;
           last = newNode;
         }
    }   
    
    
}

void printList(nodeType*& first,nodeType*& last) // print words in alphabetical order
{
        
        ofstream outData("output.txt");
        
        nodeType *current=first;
        nodeType *alphab = NULL;
        
          first=current->link;
          current->link = alphab;
          last = current;
          alphab= last;
            
        while (current != NULL)
        {
          
          outData << current->info <<endl;
          current = current->link;
        }
}

[redburn]

What is the error that is generated?

[NinjaLink]

It is a windows error when i run the program that just tells me to close.

Does anyone see what is wrong with my code to figure out how to print out in reverse and alphabetical order?

[sandeepss6s]

just a thought, shouldn't the assignment in line 60 be:

last->link = &newNode;

[NinjaLink]

Does anyone know how to figure it out with me? I am trying to print my word list in reverse order and alphabetical order. My programs are in my first post.

[NinjaLink]

I am still having problems figuring out how to print out the words in reverse order.

Input file:

hi
hey
hello
bye
adios

Update code for:

reverse words

#include <fstream>


using namespace std;
struct nodeType
{
    string info;
    nodeType *link;
    
};

void createList(nodeType*& first, nodeType*& last);
void printList(nodeType*& first, nodeType*& last);


int main()
{
    
    nodeType *first, *last;
    string words;
    
    
    ifstream inData;
    ofstream outData;

    
    createList(first,last);
    printList(first,last);
    
    
  system("PAUSE");
   return 0;
}

void createList(nodeType*& first, nodeType*& last)
{
     
    ifstream inData("input.txt");
     
    string words;
    int emptyList;
    nodeType *newNode;
    
    first = NULL;
    last = NULL;
    
    while(inData >> words)
    {
         newNode = new nodeType; // create new node
         newNode->info = words;
         newNode->link = NULL;
    
         if (first == NULL)
         {
            first = newNode;
            last = newNode;
         }
         else
         {
           last->link = newNode;
           last = newNode;
         }
    }   
    
    
}

void printList(nodeType*& first,nodeType*& last)
{
        
        ofstream outData("output.txt");
        
        nodeType *current = first;
        nodeType *reverse = NULL;
        
          first = current->link;
          current->link = reverse;
          reverse = current;
          current = first;
          first = reverse;
            
        while (current != NULL)
        {

          outData << current->info <<endl;
          current = current->link;
        }
}

[sandeepss6s]

did the assignment change help, did you try that?
since last->link is of type pointer of newNode shouldn't the &newNode be assigned?

[NinjaLink]

No, I received an error when I added the "&" symbol.

Do you know what I am doing wrong in my reverse order code?

[sandeepss6s]

on debug mode does your code prior to printlist function call work as per your requirement (as in are the outputs coming fine)?

[NinjaLink]

My program runs and the print out is fine. It just doesn't print in reverse order. it is printing everything except the first node which is suppose to be "hi"

hey
hello
bye
adios

[sandeepss6s]

Is there some more code to this because I am unable to compile this?

[NinjaLink]

This is the code and I have an input file called input.txt that contains the contents below.

Input File:

hi
hey
hello
bye
adios

#include <fstream>


using namespace std;
struct nodeType
{
    string info;
    nodeType *link;
    
};

void createList(nodeType*& first, nodeType*& last);
void printList(nodeType*& first, nodeType*& last);


int main()
{
    
    nodeType *first, *last;
    string words;
    
    
    ifstream inData;
    ofstream outData;

    
    createList(first,last);
    printList(first,last);
    
    
  system("PAUSE");
   return 0;
}

void createList(nodeType*& first, nodeType*& last)
{
     
    ifstream inData("input.txt");
     
    string words;
    int emptyList;
    nodeType *newNode;
    
    first = NULL;
    last = NULL;
    
    while(inData >> words)
    {
         newNode = new nodeType; // create new node
         newNode->info = words;
         newNode->link = NULL;
    
         if (first == NULL)
         {
            first = newNode;
            last = newNode;
         }
         else
         {
           last->link = newNode;
           last = newNode;
         }
    }   
    
    
}

void printList(nodeType*& first,nodeType*& last)
{
        
        ofstream outData("output.txt");
        
        nodeType *current = first;
        nodeType *reverse = NULL;
        nodeType *link;
        
          first = current;       
          last = current->link;
          current->link = reverse;
          reverse = current;
          current = last;
      
        
            
        while (current != NULL)
        {

          outData << current->info <<endl;
          current = current->link;
        }
}

[NinjaLink]

Are you able to reverse words and sort an alphabetical order using Linked List? I'm starting to think it doesn't exist =/

[NinjaLink]

sandeep, were you able to find something out?

Anyone know how to reverse words in a Linked List? =/

[VernonDozier]

I am currently having problems and need help with:

1) Printing the words in reverse order in my printList function

2) Printing the words in alphabetical order in my printList function

You need a sort function to put something in alphabetical order. printList should do that: print the list. It should have nothing to do with sorting/ordering the list. Do you have a sort function? Any sort that can be implemented on an array can be implemented on a linked list. The O values (i.e. O(n squared)) will often be different than they are for an array based sort due to lack of random access. But you still have to sort if you want to alphabetize. I see no sort function in your code.

[NinjaLink]

What about reverse? Do I need a seperate function for that too?

[NinjaLink]

nevermind, I got reverse to work finally work. I am now working on the alphabet function. Are there any advice to set it up or any principles to follow to sort words in alphabetical order?

[VernonDozier]

nevermind, I got reverse to work finally work. I am now working on the alphabet function. Are there any advice to set it up or any principles to follow to sort words in alphabetical order?

As mentioned, you need a sort function. Bubble Sort works well with a linked list since you're only comparing neighbors. It's just like doing it with an array. Compare neighbors. Swap if they're in the wrong order. When you've gone through the whole list with no swaps, you're done.

[NinjaLink]

I gave a swing at it, but I did some research first because I am unfamiliar with sorting using Linked Lists. Under my alphasort function, I have created a block of code that tries to use "Bubble sort" to sort the words in my input file alphabetically. However, I am receiving an error "struct nodeType has no member named 'words'".

Example of Input file:

Jack
Apple
Corn
Tea
Jacob

Example of Output

Apple
Corn
Jack
Jacob
Tea

#include <fstream>


using namespace std;
struct nodeType
{
    string info;
    nodeType *link;
};

void createList(nodeType*& first, nodeType*& last);
void alphasort (nodeType*& first, nodeType*& last);
void printList(nodeType*& first);


int main()
{
    
    nodeType *first, *last;
    string words;
    
    
    ifstream inData;
    ofstream outData;

    
    createList(first,last);
    alphasort (first,last);
    printList(first);
    
    
  system("PAUSE");
   return 0;
}

void createList(nodeType*& first, nodeType*& last)
{
     
    ifstream inData("input.txt");
     
    string words;
    int emptyList;
    nodeType *newNode;
    
    first = NULL;
    last = NULL;
    
    while(inData >> words)
    {
         newNode = new nodeType; // create new node
         newNode->info = words;
         newNode->link = NULL;
    
         if (first == NULL)
         {
            first = newNode;
            last = newNode;
         }
         else
         {
           last->link = newNode;
           last = newNode;
         }
    }   
}


void alphasort (nodeType*& first, nodeType*& last)
{
     
     
      int i;
      int j;
      int n;
      int hold; 
      string words;
      nodeType *q, *p, *t;  
    
        for  (nodeType *q = first ; q ; q=q->link)  
     
        ++n;   
        
        for   (i=1 , t = first  ; i<=n-1 ;  t = t->link , ++i)
           
        for   ( j=0 , p = first  ; j<n-i ;  p = p->link , ++j)      
          
          if  (p->words > (p->link)->words)       
          
            {	
            hold = p->words;         
            p->words = (p->link)->words;         
            (p->link)->words = hold;       
            }
          

}




void printList(nodeType*& first)
{
        
         ofstream outData("output.txt");
        
        nodeType *current;
        current = new nodeType;
        current = first;    
        while (current != NULL)
        {
          outData << current->info <<endl;
          current = current->link;
        }
}

[NinjaLink]

Anyone available to help me figure out what I am doing wrong in my code? I am trying to print my words in alphabetical order. The alphasort function is where I tried to do bubblesort.

[VernonDozier]

The error message tells you exactly what the problem is. Look at your struct.

struct nodeType
{
    string info;
    nodeType *link;
};

It has no member called words . The string member is info , so that's what you need to use.

[NinjaLink]

After I did all of that, I received 1 error message saying

Line 90: In function `void alphasort(nodeType*&, nodeType*&)': cannot convert `std::string' to `int' in assignment

It is highlighting " hold = p->info; "

Do you know how I can resolve this problem?

void alphasort (nodeType*& first, nodeType*& last)
{
     
     
     int i;
      int j;
      int n;
      int hold;
      nodeType *q, *p, *t;  
    for(nodeType *q = first ; q ; q=q->link)  
     
        ++n;   
        
        for(i=1 , t = first  ; i<=n-1 ;  t = t->link , ++i)
           
         for( j=0 , p = first  ; j<n-i ;  p = p->link , ++j)      
          
          if(p->info > (p->link)->info)       
          {	 hold = p->info;         
          p->info = (p->link)->info;         
          (p->link)->info = hold;       
          }
          

}

[NinjaLink]

Is there anyone online that can assist me on my post above ^^^

[NinjaLink]

I still need help getting the words in my input.txt file to print alphabetically. Right now, my program runs and get a windows error and says I need to close the program. Someone please help me fix my alphasort function, so my program can run.

Example of Input.txt file

Apple
Jack
Smith
Cat

Example of Output

Apple
Cat
Jack
Smith

Updated code:

#include <fstream>

using namespace std;
struct nodeType
{
    string info;
    nodeType *link;
};

void createList(nodeType*& first, nodeType*& last);
void alphasort (nodeType*& first, nodeType*& last);
void printList(nodeType*& first);


int main()
{
    
    nodeType *first, *last;
    string words;
    
    
    ifstream inData;
    ofstream outData;

    
    createList(first,last);
    alphasort (first,last);
    printList(first);
    
    
  system("PAUSE");
   return 0;
}

void createList(nodeType*& first, nodeType*& last)
{
     
    ifstream inData("input.txt");
     
    string words;
    int emptyList;
    nodeType *newNode;
    
    first = NULL;
    last = NULL;
    
    while(inData >> words)
    {
         newNode = new nodeType; // create new node
         newNode->info = words;
         newNode->link = NULL;
    
         if (first == NULL)
         {
            first = newNode;
            last = newNode;
         }
         else
         {
           last->link = newNode;
           last = newNode;
         }
    }   
}


void alphasort (nodeType*& first, nodeType*& last)
{
     
     
     int i;
      int j;
      int n;
      string hold;
      nodeType *q, *p, *t;  
    for(nodeType *q = first ; q ; q=q->link)  
     
        ++n;   
        
        for(i=1 , t = first  ; i<=n-1 ;  t = t->link , ++i)
           
         for( j=0 , p = first  ; j<n-i ;  p = p->link , ++j)      
          
          if(p->info > (p->link)->info)       
          {	 hold = p->info;         
          p->info = (p->link)->info;         
        (p->link)->info = hold;       
          }
          

}




void printList(nodeType*& first)
{
        
         ofstream outData("output.txt");
        
        nodeType *current;
        current = new nodeType;
        current = first;    
        while (current != NULL)
        {
          outData << current->info <<endl;
          current = current->link;
        }
}

[VernonDozier]

You need to find out exactly where the program is failing and how. You need to determine the line number where the program fails. Do this by using a debugger or by sticking debugging statements displaying useful variable information at strategic places in the code. In particular, in line 84, you need to confirm that neither p nor p->link are null. If they are, you cannot dereference them. You cannot solve the problem until you identify it.

Get a nice short manageable linked list set (hell, start with a linked list of one node) and run it through your sorting function. See if it passes the test above. Then try a 2 node list. Then a 3 node list.

[NinjaLink]

I started over my program because I thought I had many problems. Right now, my program runs, but it does not show results to my output.txt. Instead, it shows a blank. I am still doing the program to sort my input.txt file in alphabetical order. Someone please help

Example of Input file

Apple
Smith
Jim
Jack

#include <fstream>
#include <string>


using namespace std;

struct nodeType {
    string info;
    nodeType *link;
};

void createList(nodeType*& first, nodeType*& last);
void alphasort (nodeType*& first, nodeType*& last);
void printList(nodeType*& first);

int main(int argc, char *argv[]) 
{
    nodeType *first, *last;
    string words;

    ifstream inData;
    ofstream outData;

    createList(first,last);
    alphasort (first,last);
    printList(first);

    system ("PAUSE");
    return 0;
}

void createList(nodeType*& first, nodeType*& last) 
{
    ifstream inData("input.txt");
    string words;
    nodeType *newNode;

    first = new nodeType;
    first->info = string("head");
    first->link = NULL;
    last = first;

    while(inData >> words) 
    {
        newNode = new nodeType; // create new node
        newNode->info = words;
        newNode->link = NULL;
        last->link = newNode;
        last = newNode;
    }
}

//
// nodeSwap: exchange p->link and q->link
//
void nodeSwap(struct nodeType *p, struct nodeType *q) 
{
    struct nodeType *t1, *t2, *t3;
    if (p != q) 
    {
        t1 = p->link; t2 = q->link; t3 = q->link->link;
        p->link = q->link;
        q->link = t1;
        t2->link = t1->link;
        t1->link = t3;
    }
}

//
// Selection sort to arrange the elements of
// the given linked list of nodeType structs
// in ascending order.
//
void alphasort (nodeType*& first, nodeType*& last) 
{
    struct nodeType *i,*j,*min;

    for (i = first; i->link != NULL; i = i->link) 
    {
        min = i;
        for (j = i->link; j->link != NULL; j = j->link) 
        {
            if (j->link->info < min->link->info) min = j;
        }
        nodeSwap(i,min);
    }
}

void printList(nodeType*& first) 
{
    ofstream outData("output.txt");

    nodeType *current = first->link;
    
    while (current != NULL) 
    {
        outData << current->info <<endl;
        current = current->link;
    }
}

[NinjaLink]

If possible, can someone please answer my post above. I am wondering what can I do to see the results in my output file. Thanks.

[VernonDozier]

If possible, can someone please answer my post above. I am wondering what can I do to see the results in my output file. Thanks.

Open the output file and view it in a text editor????

Your program runs fine. You have an alphabetized list in the output file. That's what you wanted, right?

If you want the program to display the list to the console screen, you need some cout statements. A program that has no cout statements or other output to stdout or stderr is going to result in a blank screen.

[verence]

Can't you do your homework alone?