sorting linked list

This is a discussion on sorting linked list within the C Programming forums, part of the General Programming Boards category; Hey guys just wondering how i can sort the linked list by categoryName for the drink type list. Iv done ...

  1. #1
    Musicman - Canora
    Join Date
    Aug 2005
    Location
    Melbourne
    Posts
    252

    sorting linked list

    Hey guys just wondering how i can sort the linked list by categoryName
    for the drink type list. Iv done the linked list in my code but its not sorted?




    Code:
    #ifndef GJC_H
    #define GJC_H
    /* System-wide header files. */
    #include <stdio.h>
    #include <stdlib.h>
    #include <assert.h>
    #include <string.h>
    
    /* System-wide constants. */
    #define ID_LEN 5
    #define MIN_NAME_LEN 1
    #define MAX_NAME_LEN 25
    #define MIN_DESC_LEN 1
    #define MAX_DESC_LEN 250
    #define NUM_PRICES 3
    #define HOT 'H'
    #define COLD 'C'
    #define ERRORCODE 1
    #define BUFFER_SIZE 800
    #define NC_ARRAY_SIZE 500
    #define TRUE 1
    #define FALSE 0
    #define CHAR -----------------------------------------------------------------------
    
    typedef struct category* CategoryTypePtr;
    typedef struct item* ItemTypePtr;
    
    /* Structure definitions. */
    typedef struct price
    {
       unsigned dollars;
       unsigned cents;
    } PriceType;
    
    typedef struct item
    {
       char itemID[ID_LEN + 1];
       char itemName[MAX_NAME_LEN + 1];
       PriceType prices[NUM_PRICES];
       char itemDescription[MAX_DESC_LEN];
       ItemTypePtr nextItem;
    } ItemType;
    
    typedef struct category
    {
       char categoryID[ID_LEN + 1];
       char categoryName[MAX_NAME_LEN + 1];
       char drinkType;      /* (H)ot or (C)old. */
       char categoryDescription[MAX_DESC_LEN];
       CategoryTypePtr nextCategory;
       ItemTypePtr headItem;
       unsigned numItems;
    } drinkType;
    
    typedef struct gjc
    {
       CategoryTypePtr headCategory;
       unsigned numCategories;
    } GJCType;
    
    int commandLineArguments(int argc, char *argv[]);
    #endif
    Code:
    int loadData(GJCType* menu, char* menuFile, char* submenuFile)
    {
    
       drinkType *currentCat, *prevCat, *newCat;
       ItemType *currentItem, *prevItem, *newItem;
       
       FILE *fp1;
       FILE *fp2;
       
       char *token, *line;
       char array[BUFFER_SIZE + 2];
       double d;
       unsigned doll;
       int i;
       char nc_array[NC_ARRAY_SIZE + 1];
       
       /* Open menu file for reading. */
       fp1 = fopen(menuFile, "r");
       
       /* check if fp1 menu file exists*/
       if(fp1 == NULL)
       {
          printf("file %s does not exist \n", menuFile);
          exit(0);
          
       }
       
       /* initialize the previous node to NULL*/
       prevCat = NULL;
       
       while((line = fgets(array, BUFFER_SIZE + 2, fp1)) != NULL)
       {
          /* allocate memory for CategoryType pointer*/
          newCat = malloc(sizeof(drinkType));
          
          /* check if memory allocation succeeded if fails exit*/
          if(newCat == NULL)
          {
              printf("Memory Allocation error for newCat\n");
    	  exit(0);
          }
          
          /* if the prevCat is NULL point the new node to the 
          start of the list*/
          if(prevCat == NULL)
          {
             menu->headCategory = newCat;
          }
          /* if it isnt at the start get the next -1node*/
          else
          {
             prevCat->nextCategory = newCat;
          }
           
          
          /* tokenize the Pipe and copy the field
          pointers into the struct*/
               
          token = strtok(line, "|");
          strcpy(newCat->categoryID, token);
               
          token = strtok(NULL, "|");   
          newCat->drinkType = token[0];
          
          token = strtok(NULL, "|");
          strcpy(newCat->categoryName, token);
            
          token = strtok(NULL, "|");
          strcpy(newCat->categoryDescription, token);
       
          /* initialize everything to a safe state*/
          newCat->nextCategory = NULL;
          newCat->headItem = NULL;
          newCat->numItems = 0;
          prevCat = newCat;
       }
       
       /* the current pointer points to headCategory*/
       currentCat = menu->headCategory;
       
       /* for testing purposes traverse through the list
       and print out linked list*/
       /*
       while(currentCat != NULL)
       {
          printf("\n%s, %c, %s, %s", currentCat->categoryID, 
          currentCat->drinkType,
          currentCat->categoryName, 
          currentCat->categoryDescription);
        */  
          /* get the next row
          currentCat = currentCat->nextCategory;
       }*/
       
       /* close the first pointer to the file*/
       /* check if it can close it otherwise error*/
       if(fclose(fp1)!=0)
       {
           fprintf(stderr, "cannot close file\n");
       }
       
       
       /* Open submenu file for reading. */
       fp2 = fopen(submenuFile, "r");
       
       /* check if sub menu file exists*/
       if(fp2 == NULL)
       {
          printf("file %s does not exist \n", submenuFile);
          exit(0);
          
       }
       /*intialize pointer to the start*/
       prevItem = NULL;
       currentCat = menu->headCategory;
       
       while((line = fgets(array, BUFFER_SIZE + 2, fp2)) != NULL)
       {
          newItem = malloc(sizeof(ItemType));
        
          token = strtok(line, "|");
          strcpy(newItem->itemID, token);
          
          token = strtok(NULL, "|");
          strcpy(nc_array, token);
           
          /* put the current pointer to the head of the list*/
          currentCat = menu->headCategory;
          
          /* while current is pointing to a node*/
          
          while(currentCat != NULL)
          {
             if(strcmp(currentCat->categoryID, nc_array) == 0)
    	 {
    	    break;
    	 }
    	 
    	 currentCat = currentCat->nextCategory;
          }
    	 
    	 if(currentCat == NULL)
    	 {
    	    printf("NULL POINTER Error!!!\n");
    	 } 
    	 else
    	 {
                token = strtok(NULL, "|");
                strcpy(newItem->itemName, token);     
                
    	    /* store dollars into struct array*/
    	    /* convert all prices to float when storing*/
                for(i = 0; i < NUM_PRICES; i++)
                { 
                   token = strtok(NULL, "|");
                   d = atof(token); 
                   doll = (unsigned) d;  
                   newItem->prices[i].dollars = doll;
                   newItem->prices[i].cents = (d - doll) * 100;
                }
          
                token = strtok(NULL, "|");
                strcpy(newItem->itemDescription, token);
          
                /* from the start of the list*/
                newItem->nextItem = currentCat->headItem;
                currentCat->headItem = newItem;
    	    
    	    /* increment the counter*/
    	    currentCat->numItems ++;
    	 }
          
       }
       currentCat = menu->headCategory;
       /*
       while(currentCat!= NULL)
       {
          currentItem = currentCat->headItem;
          printf("Items for category %s\n", currentCat->categoryID);
       
          while(currentItem != NULL)
          {
             printf("\n%s, %s, %s, %d.%d, %d.%d, %d.%d, %s\n", 
             currentItem->itemID, currentCat->categoryID,
             currentItem->itemName, currentItem->prices[0].dollars,currentItem->prices[0].cents,
             currentItem->prices[1].dollars, currentItem->prices[1].cents,
             currentItem->prices[2].dollars, currentItem->prices[2].cents,
             currentItem->itemDescription);
             currentItem = currentItem->nextItem;
          }
          
          currentCat = currentCat->nextCategory;  
       }*/
       /* try to close the file*/
       /* if it wont close provide an error*/
       if(fclose(fp2)!=0)
       {
           fprintf(stderr, "cannot close file\n");
       }
       
       
       return EXIT_SUCCESS;
    
    
    }

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    The easiest way to do it is to sort as you go; that is, sort your data as you build the list. The next easiest way to do it is to "sort it" by moving everything to a new list, popping one off the list, and inserting it into a new one, sorting that as you go. By easiest, I mean easiest to implement.

    You can also do fun things like allocating an array of pointers-to-structs, and assign all of nodes a spot in the array. Then you can sort the array, relink your list.


    Quzah.
    Hope is the first step on the road to disappointment.

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