putting linked list in order

This is a discussion on putting linked list in order within the C Programming forums, part of the General Programming Boards category; hi people, i made a program that puts 25 random integers into a linked list, and then finds the sum ...

  1. #1
    Registered User
    Join Date
    Sep 2007
    Posts
    29

    putting linked list in order

    hi people, i made a program that puts 25 random integers into a linked list, and then finds the sum and average. everything works fine, one thing im wondering is if i wanted to put these numbers in order from lowest to highest how can i walk through the list to do that? I know the for loop needs to be there walking through num 1-25 but im not sure how to compare them with pointers in a linked list. thanks for the help.

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    
    struct listNode {
       struct listNode *nextPtr;
       int data;
    };
    
    typedef struct listNode ListNode;
    typedef ListNode *ListNodePtr;
    
    void printList( ListNodePtr currentPtr );
    int generateList( ListNodePtr *startPtr );
    
    int main()
    {
              int total;
              ListNodePtr startPtr = NULL;
    
                          generateList( &startPtr );
    
                          total = get_total(startPtr);
    
                          printList( startPtr );
    
                          printf( "\nTotal of all 25 elements is %d", total );
                          printf( "\nAverage of all 25 elements is %.2f\n\n", (float)total / 25 );
       
                           getchar();
                           return 0;
    }
    
    
    int generateList( ListNodePtr *startPtr )
    {
         int randNum, total = 0, i = 0;
         ListNodePtr newPtr, currentPtr;
         srand( time( NULL ) );
    
       
    
                for (i =0; i < 25; i++ ) {
                     randNum = rand() % 100;
                     newPtr = malloc( sizeof( ListNode ) );
                     newPtr->data = randNum;
                     newPtr->nextPtr = NULL;
    
    	                             if(*startPtr == NULL)	{ 
    	                             *startPtr = newPtr; 
    	                             currentPtr=newPtr;
    	                             continue;
    	                                                    }
                                                            currentPtr->nextPtr=newPtr;	
                                                            currentPtr=currentPtr->nextPtr;
              }
       return 0;
    }
    
    
    
    
    void printList( ListNodePtr currentPtr )
    { 
                    if ( currentPtr == NULL )
                       printf( "List is empty.\n\n" );
                                     else { 
                                          printf( "The list is:\n" );
    
                                                  while ( currentPtr != NULL ) { 
                                                        printf( "%d, ", currentPtr->data );
                                                        currentPtr = currentPtr->nextPtr;
                                                  }
    
                                                  printf( "NULL\n\n" );
                                    }
                   }
    
    
    int get_total(ListNodePtr currentPtr)
    {
    
                              if(currentPtr==NULL) return 0;
    
                              return currentPtr->data + get_total(currentPtr->nextPtr);
    
    }

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    You need to do something along the lines of this stupid bubble sort:

    Code:
    void sortList(ListNodePtr list) {
       ListNodePtr *p;
       ListNodePtr *q;
       
       for(p = list; p; p = p->next) {
          for(q = p->next; q; q = q->next) {
             if (q->data < p->data) swap(q, p);
          }
       }
    }
    I'll let you figure out how to do swap (and no cheating of swapping just the data, ok?)

    The other option is of course to insert it sorted in the first place.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  3. #3
    Registered User
    Join Date
    Sep 2007
    Posts
    29
    thanks mats, i kind of get the idea, will post what i did soon.

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Bubble sort on a linked-list isn't nearly as simple as it is for an array.

    Actually, that's not BubbleSort either. Bubble sort always swaps adjacent items, and is hence always stable. You've posted SimpleSort (as I call it) which is not stable. Furthurmore, to swap two arbitrary items in a list requires the previous node pointer for each item, which since this isn't a doubly-linked list you have to track yourself, as well.

    The simplest singly-linked-list sorting algorithm is actually InsertionSort. I suggest using that, since it is only 25 items.

    You could refer to the list-sorting pages from the link in my sig...
    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"

  5. #5
    Registered User
    Join Date
    Sep 2007
    Posts
    29
    yeah i still cant find the right way to do it. I went to your links iMalc but couldn't find the right thing i guess. thanks for anyone that can help me with putting the list in order from lowest to highest, still confused on how to do that. later people.

  6. #6
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    If you need it sorted, why not build it sorted from the start? That saves you the trouble and upfront cost of an explicit sorting operation. I believe in the help by massive information method, so see if this helps you. It covers building a sorted list as well as a great deal of other information you might find helpful.
    My best code is written with the delete key.

  7. #7
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    An insertion-sort looks something like this:
    Code:
    struct node {
       int data;
       struct node *next;
    };
    
    /* Take the list indicated by head, and create a new one, 
     * returning the head of the new list. 
     */
    struct node *insertion_sort_list(struct node *head)
    {
        struct node  *newhead = NULL;
        struct node *p;
        struct node *pNext;
        struct node *q;
        struct node *qPrev;
    
        for ( p = head; p; p = pNext) {
           pNext = p->next;
           // Simplest case - new list is empty, insert current element first. 
           if (newhead == NULL) {
              newhead = p;
              p->next = NULL;
           } else {
             qPrev = NULL;
             for(q = newhead; q->data < p->data; qPrev = q, q = q->next);
             // Is the current value smaller than first item in the list?
             // If so, make this a new head.
             if (qPrev == NULL) {
                p->next = newhead;
                newhead = p;
            } else {
                qPrev->next = p;
                p->next = q;
            }
          }
        }
        return newhead;
    }
    I haven't tested this code, but I beleive it's correct.
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  8. #8
    Registered User
    Join Date
    Sep 2007
    Posts
    29
    this is what i put together but I did something wrong, received some errors and dont know where to begin to fix them.

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    
    struct listNode {
       struct listNode *nextPtr;
       int nums;
    };
    
    typedef struct listNode ListNode;
    typedef ListNode *ListNodePtr;
    
    void printList( ListNodePtr currentPtr );
    int generateList( ListNodePtr *startPtr );
    
    int main()
    {
              int total;
              ListNodePtr startPtr = NULL;
    
                          generateList( &startPtr );
    
                          total = get_total(startPtr);
    
                          printList( startPtr );
    
                          printf( "\n\n\nTotal: &#37;d", total );
                          printf( "\nAverage: %.2f\n\n", (float)total / 25 );
       
                           getchar();
                           return 0;
    }
    
    
    int generateList( ListNodePtr *startPtr )
    {
         int randNum, total = 0, i = 0;
         ListNodePtr newPtr, currentPtr;
         srand( time( NULL ) );
    
       
    
                for (i =0; i < 25; i++ ) {
                     randNum = rand() % 100;
                     newPtr = malloc( sizeof( ListNode ) );
                     newPtr->nums = randNum;
                     newPtr->nextPtr = NULL;
    
    	                             if(*startPtr == NULL)	{ 
    	                             *startPtr = newPtr; 
    	                             currentPtr=newPtr;
    	                             continue;
    	                                                    }
                                                            currentPtr->nextPtr=newPtr;	
                                                            currentPtr=currentPtr->nextPtr;
              }
              insertion_sort_list(&startPtr); 
       return 0;
    }
    
    
    
    
    void printList( ListNodePtr currentPtr )
    { 
                    if ( currentPtr == NULL )
                       printf( "List is empty.\n\n" );
                                     else { 
                                          printf( "The list is:\n" );
    
                                                  while ( currentPtr != NULL ) { 
                                                        printf( "%d ", currentPtr->nums );
                                                        currentPtr = currentPtr->nextPtr;
                                                  }
    
                                                 
                                    }
                   }
    
    
    int get_total(ListNodePtr currentPtr)
    {
    
                              if(currentPtr==NULL) return 0;
    
                              return currentPtr->nums + get_total(currentPtr->nextPtr);
    
    }
    
    
    int insertion_sort_list(ListNodePtr *startPtr)
    {
        struct node  *newStart = NULL;
        struct node *newPtr;
        struct node *newPtrNext;
        struct node *nextPtr;
        struct node *nextPtrPrev;
    
        for ( newPtr = startPtr; newPtr; newPtr = newPtrNext) {
           newPtrNext = newPtr->next;
           // Simplest case - new list is empty, insert current element first. 
           if (newStart == NULL) {
              newStart = newPtr;
              newPtr->next = NULL;
           } else {
             nextPtrPrev = NULL;
             for(nextPtr = newStart; nextPtr->data < newPtr->data; nextPtrPrev = nextPtr, nextPtr = nextPtr->next);
             // Is the current value smaller than first item in the list?
             // If so, make this a new head.
             if (nextPtrPrev == NULL) {
                newPtr->next = newStart;
                newStart = newPtr;
            } else {
                nextPtrPrev->next = newPtr;
                newPtr->next = nextPtr;
            }
          }
        }
        return newStart;
    }

  9. #9
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Then you'd better post the errors!

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  10. #10
    Registered User
    Join Date
    Sep 2007
    Posts
    29
    In function `insertion_sort_list':
    99 [Warning] assignment from incompatible pointer type
    104 [Warning] assignment from incompatible pointer type
    107 [Warning] assignment from incompatible pointer type
    107 [Warning] assignment from incompatible pointer type
    107 [Warning] assignment from incompatible pointer type
    111 [Warning] assignment from incompatible pointer type
    114 [Warning] assignment from incompatible pointer type
    115 [Warning] assignment from incompatible pointer type
    119 [Warning] assignment from incompatible pointer type


    i have no idea how to fix that problem, i understant that its with how i coded the pointers but thats about it.

  11. #11
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    I'm guessing those errors come from the fact that you're trying to use struct node rather than struct listNode. I also get quite a few more errors and warnings than you posted, so you might want to turn up your compiler's ..........y level.
    My best code is written with the delete key.

  12. #12
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    And you may want replace this:
    Code:
              insertion_sort_list(&startPtr);
    with something like:
    Code:
              startPtr = insertion_sort_list(startPtr);
    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  13. #13
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >And you may want replace this:
    >with something like:
    Not when insertion_sort_list returns an int. Do a brain compile on the OP's code, it needs a bit more work than just fixing the errors posted.
    My best code is written with the delete key.

  14. #14
    Registered User
    Join Date
    Sep 2007
    Posts
    29
    thanks for helping guys, i may never get this one but im still trying.

  15. #15
    ggs
    ggs is offline
    C > C++ duders ggs's Avatar
    Join Date
    Aug 2001
    Posts
    435
    Merge sort provides excellent performance and the implementation for linked lists is remarkably elegant.

    The following routine should return a pointer to a linked list.

    If the linked list given to be sorted is only 1 nodes in length or NULL, it is already sorted, so you can just return.

    1. Save a pointer to the first list node.

    2. Walk through your list in a loop with two pointers. Advance one pointer one node at a time, advance the 2nd two nodes at a time.

    3. When the 2nd pointer has hit null, your 1st pointer is at the halfway point of the list. Save a pointer to the node after the 1st pointer, and set the next node of the 1st pointer to null.

    Now the pointer you saved in step 1 points to the first half of the list, and pointer you saved in step 3 points to the second half of the list.

    Recursively call your sort routine on both lists. Since your sort routine returns a linked list, save the return values of each.

    Now you need to merge the 2 lists together. Since each of the lists is sorted, you can just set a pointer to the start of each list and start a loop where you build the larger sorted list.

    From the two pointers, pick the node with the smallest value, and add it to the return list. Advance the pointer which you picked the node from to the next value in its list. When one of the pointers runs out of nodes, append the other list to your sorted list.

    Return the newly constructed sorted list.



    Try running this algorithm on paper with some small (maybe 5 or 6 valued) lists before implementing it, and it will be easy to see how and why it works.



    If my explanation doesn't cut mustard, try searching on the web for it, or using the link below.

    http://en.literateprograms.org/Category:Merge_sort
    .sect signature

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C++ Linked list program need help !!!
    By dcoll025 in forum C++ Programming
    Replies: 1
    Last Post: 04-20-2009, 10:03 AM
  2. single linked list to double linked list (help)
    By Countfog in forum C Programming
    Replies: 8
    Last Post: 04-29-2008, 08:04 PM
  3. Replies: 5
    Last Post: 11-04-2006, 05:39 PM
  4. putting search result into a linked list
    By jetfreggel in forum C Programming
    Replies: 4
    Last Post: 03-03-2003, 12:22 PM
  5. problem with structures and linked list
    By Gkitty in forum C Programming
    Replies: 6
    Last Post: 12-12-2002, 05:40 PM

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