Sorting a linked list

This is a discussion on Sorting a linked list within the C Programming forums, part of the General Programming Boards category; Nearly there with getting this program finished but I've run into another problem - my program keeps crashing after trying ...

  1. #1
    Registered User
    Join Date
    Nov 2006
    Posts
    12

    Sorting a linked list

    Nearly there with getting this program finished but I've run into another problem - my program keeps crashing after trying to implement a merge sort. It all compiles OK but crashes as soon as I run it.
    I'm thinking the fault lies with my method of checking the words being added to the list - I'm reading in words from a text file, storing the unique ones in the list, and counting how many of them appear in the text. If I just read in every word (without counting etc), the program appears to work OK.

    Anyway, here's my code - I would be extremely grateful if someone could highlight where I'm going wrong.

    Code:
    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    #include <ctype.h>
    
    typedef struct wordList
    {
      int entries;
      char words[50];
      struct wordList *next;
    } wordList_t;
    
    wordList_t *MergeSort (wordList_t *head);
    wordList_t *Merge (wordList_t *ptr1, wordList_t *ptr2);
    
    wordList_t *talloc (void)
    {
      return (wordList_t *)malloc(sizeof(wordList_t));
    }
    
    wordList_t *AddToList (wordList_t *head, char word[])
    {
      wordList_t *current = NULL;
      wordList_t *ptr = head;
      int found = 0;
    
      while (ptr != NULL){ 
         if (strcmp(ptr->words, word) == 0){
            ptr->entries++;
            found = 1;
         }
         ptr = ptr->next;
      }
      
      if ((head != NULL) && (found == 0)){
         current = talloc();
         strcpy (current->words, word);
         current->entries = 1;
         current->next = head;
         head = current;
      }
      if (head == NULL) {
        head = talloc();       
        head->next = NULL;
        strcpy (head->words, word);
        head->entries = 1;
      }
    
      return head;
    }
    
    wordList_t *MergeSort (wordList_t *head)
    {
      wordList_t *ptr1, *ptr2;
      if ((head == NULL) || (head->next == NULL))
         return head;
      ptr1 = head;
      ptr2 = head->next;
      while ((ptr2 != NULL) && (ptr2->next != NULL)){
            head = head->next;
            ptr2 = ptr2->next->next;
      }   
      ptr2 = head->next;
      head->next = NULL;
      return Merge(MergeSort(ptr1), MergeSort(ptr2));  
    }
    
    wordList_t *Merge (wordList_t *ptr1, wordList_t *ptr2)
    {
      wordList_t *ptr3;
      if (ptr1 == NULL)
         return ptr2;
      if (ptr2 = NULL)
         return ptr1;
      if (ptr1->entries < ptr2->entries){
         ptr3 = ptr1;
         ptr3->next = Merge(ptr1->next, ptr2);
      }
      else{
         ptr3 = ptr2;
         ptr3->next = Merge(ptr1, ptr2->next);
      }
      return ptr3;
    }      
    
    void PrintList (wordList_t *head)
    {
      FILE *newhtml = fopen("new.html", "w");
      fprintf(newhtml,"<html><body>\n<ul>");
      while (head != NULL){
            fprintf(newhtml, "<li>%i - %s</li>", head->entries, head->words);
            head = head->next;
      }
      fprintf(newhtml,"</ul></body></html>");
      fclose(newhtml);
    }
    
    int main (int argc, char *argv[])
    {
      char c;
      int i, j = 0;
      char word[50];
      FILE *src;         
      wordList_t *list = NULL;
      if ((src = fopen (argv[1], "r")) == NULL)
         printf("You did not specify a document or the document cannot be found!");
      else {   
           for (i = 0; (c = fgetc(src)) != EOF; ++i){
               if (isalpha(c))
                  word[j++] = tolower(c);
               else if ((!isalpha(c)) && (j != 0)){
                  word[j++] = '\0';
                  list = AddToList (list, word);
                  j = 0;
               }
           }
           fclose(src);
           PrintList(MergeSort(list));
           free(list);       
      }
      return 0;
    }
    Last edited by thoseion; 11-13-2006 at 04:49 AM.

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,296
    This bit of code does NOT split the list in half, as you are intending:
    Code:
      ptr1 = head;
      ptr2 = head->next;
      while (ptr2 != NULL){// && (ptr2->next != NULL)){
            head = head->next;
            ptr2 = head->next->next;
      }   
      ptr2 = head->next;
      head->next = NULL;
    You are going to end up with just the last item chopped off. You probably meant to write this for the second line in the loop:
    Code:
            ptr2 = ptr2->next->next;
    Also, you do need that extra continuation condition that you have commented out of your while loop. It may crash without it, depending on whether the list length is odd or even.

  3. #3
    Registered User
    Join Date
    Nov 2006
    Posts
    12
    Hi mate, I've edited it as per your suggestions but it still crashes as soon as I run the program

  4. #4
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,473
    if ptr2 is not null, ptr2->next still can be null, you cannot dereference it without checking
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

  5. #5
    Registered User
    Join Date
    Nov 2006
    Posts
    12
    Quote Originally Posted by vart
    if ptr2 is not null, ptr2->next still can be null, you cannot dereference it without checking
    Yeah, I had it commented out while I was error checking (pretty much clutching at straws trying to find out what was going wrong!) , I didn't mean to leave it in the code I posted.

    I've edited my code above to show how it currently looks, taking iMalc's comments into consideration.
    The program still crashes though when I run it. I've actually got it working using a bubble sort but I'd like it to use a merge.

  6. #6
    CSharpener vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,473
    Code:
    if (ptr2 = NULL)
         return ptr1;
    its not a comparison, but an assignment...
    If its just a copy/past error - maybe better to post your code once again as it is now
    The first 90% of a project takes 90% of the time,
    the last 10% takes the other 90% of the time.

  7. #7
    Registered User
    Join Date
    Nov 2006
    Posts
    12
    Quote Originally Posted by vart
    its not a comparison, but an assignment...
    If its just a copy/past error - maybe better to post your code once again as it is now
    OMG!! That missing '=' was the problem all along! Can't believe I've spent the best part of a whole day trying to get that working and it was because I missed out an operator!

    Thanks a lot for your help!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. single linked list to double linked list (help)
    By Countfog in forum C Programming
    Replies: 8
    Last Post: 04-29-2008, 08:04 PM
  2. singly linked to doubly linked
    By jsbeckton in forum C Programming
    Replies: 10
    Last Post: 11-06-2005, 06:47 PM
  3. Please Help - Problem with Compilers
    By toonlover in forum C++ Programming
    Replies: 5
    Last Post: 07-23-2005, 10:03 AM
  4. Linked list with two class types within template.
    By SilasP in forum C++ Programming
    Replies: 3
    Last Post: 02-09-2002, 05:13 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21