Inserting to sorted linked list

This is a discussion on Inserting to sorted linked list within the C Programming forums, part of the General Programming Boards category; Hi all. Been a long time since I posted here and I'm a bit rusty with my C. I'm trying ...

  1. #1
    ---
    Join Date
    May 2004
    Posts
    1,379

    Inserting to sorted linked list

    Hi all.

    Been a long time since I posted here and I'm a bit rusty with my C.
    I'm trying to write a function that inserts into a linked list where node->name is in alphabetical order.

    This is what I have so far and it seems logical to me but I just can't understand why they are not sorted.

    Code:
    void insertProductNode(char *brand, char *name, unsigned price, unsigned qty, ProductNodeType **head){
       ProductNodeType *node = malloc( sizeof(ProductNodeType) );
       ProductNodeType *iter = *head;
    
       if( node == NULL ){
          fprintf(stderr, "Error allocating memory. addProductNode()");
          exit(EXIT_FAILURE);
       }
    
       strncpy( node->brand, brand, PRODUCT_BRAND_MAX );
       strncpy( node->name, name, PRODUCT_NAME_MAX );
       node->qty = qty;
       node->price = price;
       node->nextProduct = NULL;
    
       if( iter == NULL ){
          *head = node;
       }
       else{
          while( iter != NULL ){
             if( iter->nextProduct == NULL ){
                iter->nextProduct = node;
                break;
             }
             else if ( strcmp( node->name, iter->name ) < 0){
                node->nextProduct = iter->nextProduct;
                iter->nextProduct = node;
                break;
             }
             iter = iter->nextProduct;
    
          }
    
       }
    }
    Code:
    typedef struct productNode
    {
       char name[PRODUCT_NAME_MAX + 1];
       char brand[PRODUCT_BRAND_MAX + 1];
       unsigned price;
       unsigned qty;
       struct productNode* nextProduct;
    } ProductNodeType;
    Last edited by sand_man; 05-04-2012 at 10:13 PM.

  2. #2
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,762
    Code:
             else if ( strcmp( node->name, iter->name ) < 0){
                node->nextProduct = iter->nextProduct;
                iter->nextProduct = node;
                break;
             }
             iter = iter->nextProduct;
    Your problem is in the comparison. Since you want to add node's after the iter, you have to insert when node->name should appear after iter->name.

    That's a pretty simple fix huh?

    After I fixed it I got a nice sorted list:
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define PRODUCT_NAME_MAX 100
    #define PRODUCT_BRAND_MAX (PRODUCT_NAME_MAX)
    
    typedef struct productNode
    {
       char name[PRODUCT_NAME_MAX + 1];
       char brand[PRODUCT_BRAND_MAX + 1];
       unsigned price;
       unsigned qty;
       struct productNode* nextProduct;
    } ProductNodeType;
    
    void print(ProductNodeType *head)
    {
       while(head != NULL)
       {
          printf("%s %s\n", head->brand, head->name);
          printf("Price:\t$%u.%u\n", head->price / 100, head->price % 100);
          printf("Qty: %u\n", head->qty);
          head = head->nextProduct;
       }
    }
    
    void insertProductNode(char *brand, char *name, unsigned price, unsigned qty, ProductNodeType **head){
       ProductNodeType *node = malloc( sizeof(ProductNodeType) );
       ProductNodeType *iter = *head;
     
       if( node == NULL ){
          fprintf(stderr, "Error allocating memory. addProductNode()");
          exit(EXIT_FAILURE);
       }
     
       /* add data to newly created node */
       strncpy( node->brand, brand, PRODUCT_BRAND_MAX );
       strncpy( node->name, name, PRODUCT_NAME_MAX );
       node->qty = qty;
       node->price = price;
       node->nextProduct = NULL;
     
       if( iter == NULL ){
          *head = node;
       }
       else{
          while( iter != NULL ){
             if( iter->nextProduct == NULL ){
                iter->nextProduct = node;
                break;
             }
             else if ( strcmp( node->name, iter->name ) > 0){
                printf("node->name %s\niter->name %s\n\n", node->name, iter->name);
                node->nextProduct = iter->nextProduct;
                iter->nextProduct = node;
                break;
             }
             iter = iter->nextProduct;
     
          }
     
       }
    }
    
    int main()
    {
       ProductNodeType *head = NULL;
    
       insertProductNode("Wonder", "bread", 129, 10, &head);
       insertProductNode("Uncle Ray's", "potato chips", 99, 12, &head);
       insertProductNode("Prince", "spaghetti", 240, 15, &head);
       insertProductNode("Kellog", "cereal", 129, 10, &head);
    
       print(head);
       
       while (head != NULL)
       {
          ProductNodeType *del = head;
          head = head->nextProduct;
          free(del); 
          del = NULL;
       }  
       return 0;
    }
    
    /*
    node->name spaghetti
    iter->name bread
    
    node->name cereal
    iter->name bread
    
    Wonder bread
    Price:	$1.29
    Qty: 10
    Kellog cereal
    Price:	$1.29
    Qty: 10
    Prince spaghetti
    Price:	$2.40
    Qty: 15
    Uncle Ray's potato chips
    Price:	$0.99
    Qty: 12
    */
    C code - 85 lines - codepad

    Unless this doesn't fit your expectations somehow?

  3. #3
    ---
    Join Date
    May 2004
    Posts
    1,379
    Thanks but I had already tried that and trying again now I still don't get a sorted list. There must be something I'm missing somewhere else in the program.
    I'm loading data from a csv file but I can't see the problem being there either.
    This is starting to do my head in!

    Code:
       FILE *fpStock = NULL;
       char line[LINELENGTH];
       char *name = NULL;
       char *brand = NULL;
       char delim[] = ",";
       unsigned price;
       unsigned qty;
    
       fpStock = fopen("coins.csv", "r");
       if (fpStock == NULL){
          fprintf(stderr, "%s does not exist. Exiting\n", stockFile);
          exit(EXIT_FAILURE);
       }
    
       while( fgets( line, LINELENGTH, fpStock ) != NULL ){
          name = strtok( line, delim );
    
          brand = strtok( NULL, delim );
    
          price = atoi(strtok( NULL, delim ));
    
          qty = atoi(strtok( NULL, delim ));
    
          insertProductNode(brand, name, price, qty, &vm->headProduct);
    
          vm->totalProducts++;
    
       }
       fclose(fpStock);
    Code:
    Twirl,Cadbury,165,5
    Snakes Alive,Allens,300,5
    Minties,Allens,140,10
    Picnic,Cadbury,200,5
    Dairy Milk Chocolate (95g),Cadbury,250,4
    &vm->headProduct is just a ProductNodeType.
    Last edited by sand_man; 05-04-2012 at 10:46 PM.

  4. #4
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,762
    What do you get?

  5. #5
    ---
    Join Date
    May 2004
    Posts
    1,379
    In fact, if I use your function, they are inserted in the same order as the csv file.

  6. #6
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,762
    Perhaps you meant to sort by brand instead? In fact, why are you making me guess as much as possible?

  7. #7
    ---
    Join Date
    May 2004
    Posts
    1,379
    I'm not sure what else to provide! I'm guessing here too.
    Thanks for your help. I'll keep looking

  8. #8
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,762
    OK, I'm going to stop thinking so hard.

    Revert to what you had when you first posted the thread. Now remove the break statements in your insert function. Report back.

  9. #9
    ---
    Join Date
    May 2004
    Posts
    1,379
    If I remove either of the breaks it seems to just hang (or loop infinitely).
    I'm starting to think my logic is off a bit here. I think I've been looking at it for too long.

  10. #10
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    It took me ten seconds to notice that your code does not handle the case of inserting an item at the start of the list when the list is currently non-empty.
    At a guess I'd say that is going to be a problem.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  11. #11
    ---
    Join Date
    May 2004
    Posts
    1,379
    Thanks iMalc. As I thought, I need to go back and start again.

  12. #12
    ---
    Join Date
    May 2004
    Posts
    1,379
    Fixed it for anyone interested
    Code:
    void insertProductNode(char *brand, char *name, unsigned price, unsigned qty, ProductNodeType **head){
       ProductNodeType *node = malloc( sizeof(ProductNodeType) );
       ProductNodeType *current = NULL;
       ProductNodeType *previous = NULL;
    
       if( node == NULL ){
          fprintf(stderr, "Error allocating memory. addProductNode()");
          exit(EXIT_FAILURE);
       }
    
       strncpy( node->brand, brand, PRODUCT_BRAND_MAX );
       strncpy( node->name, name, PRODUCT_NAME_MAX );
       node->qty = qty;
       node->price = price;
       node->nextProduct = NULL;
    
    
       current = *head;
       previous = NULL;
    
       while( current != NULL && strcmp( current->name, node->name ) < 0 ){
          previous = current;
          current = current->nextProduct;
       }
    
       node->nextProduct = current;
    
       if( previous == NULL ){
          *head = node;
       }
       else{
          previous->nextProduct = node;
       }
    
    }

  13. #13
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Looks great to me!

    It really helps when you have all the cases for what it needs to do written down or memorised . If you ever do any TDD then you'll get really good at identifying the different cases for any algorithm.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Creating a Sorted Linked List
    By jeanermand in forum C Programming
    Replies: 2
    Last Post: 12-04-2011, 11:39 PM
  2. sorted linked list
    By budala in forum C Programming
    Replies: 12
    Last Post: 07-29-2009, 09:47 AM
  3. inserting in a sorted list
    By angelscars in forum C++ Programming
    Replies: 16
    Last Post: 11-11-2005, 04:33 PM
  4. Inserting new nodes in a sorted double linked list
    By carrja99 in forum C++ Programming
    Replies: 2
    Last Post: 03-07-2003, 08:34 AM
  5. sorted linked list
    By Unregistered in forum C++ Programming
    Replies: 1
    Last Post: 02-03-2002, 09:11 PM

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