Thread: learning how to do sorted linked lists

  1. #1
    Registered User
    Join Date
    Oct 2008
    Posts
    51

    learning how to do sorted linked lists

    is there a good guide someone can point me to?

    I'm trying to learn from my lecture notes, but they aren't very descriptive.

    my books don't mention them neither.

  2. #2
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    You should be able to google "C linked list tutorial" and find a ton. Sorting may or may not be included; sometimes sorting is discussed in terms of an algorithm in pseudo code rather than a particular language (there are about half a dozen common algorithms).

    Sorting is easiest with integers, so give your nodes some kind of number to work with
    Code:
    typedef struct _node {
            char name[32];
            int number;
            struct _node *next;
    } node;
    You can try sorting strings once you get numbers to work. Of the sorts I've implimented I would say the order of difficulty is something like
    • bubblesort (easiest)
    • insertion sort
    • selection sort
    • merge sort
    • quick sort (trickiest)


    Write each sort as a single function that calls a separate simple comparison routine (then you can swap a different routine in later for dealing with strings). The comparison for ints can be this simple:
    Code:
    int compare_numbers (int a, int b) {
    	if (a==b) return 0;
    	if (a>b) return 2;
    	else return 1;
    }
    which could be a macro -- but some of the sort algorithms are recursive and using a macro there can cause a problem. The recursive sorts (merge and quick) require two separate functions.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  3. #3
    apprentiCe
    Join Date
    Oct 2008
    Location
    Hyderabad,India
    Posts
    136
    how about

    Linked list - Wikipedia, the free encyclopedia

    while inserting an element into the link list, check where it would belong according to the element's magnitude,compared to the rest of the elements already present in the LL

    then you got yourself a sorted linked list.
    Last edited by creeping death; 03-29-2009 at 03:37 AM.
    Code:
    printf("%c%c%c%c%c%c%c",0x68,0x68^0xd,0x68|0x4,0x68|0x4,0x68|0xf,0x68^0x49,0x68^0x62);

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Creating a Sorted Linked List, Help Please!
    By larry_2k4 in forum C Programming
    Replies: 4
    Last Post: 04-28-2009, 01:12 AM
  2. Linked Lists 101
    By The Brain in forum C++ Programming
    Replies: 5
    Last Post: 07-24-2004, 04:32 PM
  3. Linked List of Linked lists Revisited.
    By Qui in forum C++ Programming
    Replies: 11
    Last Post: 04-11-2004, 09:45 PM
  4. need help w/ linked lists
    By MKashlev in forum C++ Programming
    Replies: 11
    Last Post: 08-05-2002, 08:57 PM
  5. Linked lists
    By sballew in forum C Programming
    Replies: 6
    Last Post: 10-24-2001, 08:52 PM