You are here:

C++/Insertion sort on linked list

Advertisement


Question
How would you sort a linked list alphabetically using strcmpi to compare the new word with each word in the list?

My code is attached below.  It is a little messy because I haven't advanced to classes yet.  Currently it reads a text file and each unique word to the list with a count.  The list is then written to a new file.  I need to do an insertion sort as each word is found so that the list is in alphabetical order.  I am being told that it should be done in the same loop as my count comparision with strcmpi but am unsure as of how to accomplish this.  Thanks for your help.

//----------------------------------------------------------#include <vcl\condefs.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <conio.h>

#pragma hdrstop
//----------------------------------------------------------
USERES("sort_list.res");
//----------------------------------------------------------
typedef struct TWord{
  char * m_word;
   int count;
   TWord * next;
}TWord;

//----------------------------------------------------------int main()
{
  FILE * stream;
   FILE * output;
   char ch = 0;
   char prevChar = 0;
   int length=0;
   char newWord[1024];
   int newWord_len = 0;

   //------------------------------------------------------
   // initialize beginning pointer to NULL
  TWord * start_ptr = NULL;
   TWord * end_ptr;
   TWord * temp;

   //------------------------------------------------------
   // hold count information
   int numWords = 0;

   //------------------------------------------------------
   // open file
   stream = fopen("c:\\Paragraph.txt", "r");
   if (stream == NULL)
   {
      printf("Error opening file...\n");
   }
   else {printf("File opened.\n");}

   //------------------------------------------------------
   // open output file
   output = fopen("c:\\output.txt", "wt");
   if (output == NULL)
   {
      printf("Error opening file...\n");
   }
   else {printf("File opened.\n");}

   //------------------------------------------------------
   // obtain file size
   fseek (stream, 0, SEEK_END);
   length = ftell (stream);
   fseek (stream, 0L, SEEK_SET);
   printf ("Length: %d\n\n", length);

   //------------------------------------------------------
   // determine number of characters and words
   for (int i = 0; i < length; i++)
   {
       // convert to lowercase and assign to variable
     ch = fgetc(stream);

       // append characters to string
       if (!(ispunct(ch) || isspace(ch)))
       {
         newWord[newWord_len++] = ch;
       }

       // keep count of words
       if ((isalnum(prevChar)) && (isspace(ch) || ispunct(ch)) && ch != '\'' && ch != '-')
       {
         // ensure null terminator is included in the string
         newWord[newWord_len++] = '\0';

         // check list to see if it already exists
         for (temp = start_ptr; temp != NULL; temp = temp->next)
         {
         if(strcmpi(newWord, temp->m_word)==0)
         {
         temp->count++;
         break;
         }
         }
         
         if (temp == NULL)
         {
         // reserve block of memory for structure and initialize variables
         temp = new TWord;
         temp->count = 1;
         temp->next = NULL;
         temp->m_word = new char[newWord_len];

         // copy the word to the structure instance
         strcpy(temp->m_word, newWord);

         // head has no value - assign word to head
         if (start_ptr == NULL)
         {
         start_ptr = temp;
         end_ptr = temp;
         }
         // head has value - assign word to next node
         else
         {
         end_ptr->next = temp;
         end_ptr = temp;
         }
         }

         // increase word count
         numWords++;

         // set new word length back to zero for next word
         newWord_len = 0;
       }
       // assign character to a variable for comparison in the loop
       prevChar = ch;
   }

   //------------------------------------------------------
   // display values on screen
   fprintf(output, "\nTotal Number of Words: " "%d\n", numWords);

   fprintf(output, "\nList: \n");
   for(temp = start_ptr; temp != NULL; temp = temp->next)
   {
      fprintf(output, "\"%s\"\t\t%d\n", temp->m_word, temp->count);
   }

   getch();

   // cleanup
   delete temp;

   //------------------------------------------------------
   // close file
   fclose(stream);
   fclose(output);
  return 0;
}
//----------------------------------------------------------


Answer
If you want to create a linked list in sorted order, you simply traverse from the first element and insert the item before the first item which is greater than the item. Here's how to insert into a list.  The compare would be up to you - you insert when the item is greater than the next one in the list.  Note that this covers 4 cases: empty list, item needs to be first, item is in the middle, item is last.

void Insert( myclass *item )
{
 if( listHead == NULL )
   listHead = item;
 else if( compare( listHead, item ) > 0 )
   {
   item->next = listHead;
   listHead = item;
   }
 else
   {
   for( myclass *ptr = listHead; ptr->next != NULL; ptr = ptr->next )
     {
     if( compare( ptr->next, item ) > 0 ) // Item is > than ptr
       {
       item->next = ptr->next;  // Insert item after ptr
       ptr->next = item;
       break;
       }
     if( ptr->next == NULL )    // Reached end without inserting
       {
       ptr->next = item;       // Insert at end
       item->next = NULL;
       }
   }
}

Bill

C++

All Answers


Answers by Expert:


Ask Experts

Volunteer


Bill A

Expertise

I can answer questions about C++, programming algorithms, Windows programming in MFC (which is C++). I cannot answer questions about STL (templates) and I have no experience with Linux. I do enjoy reviewing code and critiquing it or finding problems in it. I will also gladly show better algorithms or methods if you want to take advantage of that.

Experience

I've developed a commercial embedded C compiler/assembler and IDE with debugger toolset, of which the IDE and debugger are written in C++. I work in the industry writing high tech embedded programs and Windows programs to communicate with the embedded devices.

Publications
Book: Embedded Systems Design using the Rabbit 3000 Microprocessor Authored Chapter 10 in its entirety.

Education/Credentials
BS Computer Engineering

©2016 About.com. All rights reserved.