please give me logic of how to sort link list of string

Discussion in 'C Programming' started by incredible, Nov 20, 2006.

  1. incredible

    incredible Guest

    how to sort link list of string
     
    incredible, Nov 20, 2006
    #1
    1. Advertising

  2. incredible said:

    > how to sort link list of string


    Presumably you know that sorting consists of putting items into a particular
    order, which implies that you need to be able to compare them and decide
    which of them belongs earlier in the order. You also need to be able to
    swap strings round if they're not in the right order. Presumably you know
    how to compare two strings. So your immediate problem is: "how do I
    exchange two items in a linked list?"

    Assuming your nodes are defined like this:

    struct node
    {
    struct node *prev;
    struct node *next;
    void *data;
    };

    (with the data pointer pointing to some kind of aggregate containing the key
    data and perhaps a payload), it's very easy to swap two nodes:

    if(p1 != NULL && p2 != NULL)
    {
    void *tmp = p1->data;
    p1->data = p2->data;
    p2->data = tmp;
    }

    If the data is *only* a string, s/void/char/

    If you're using ordinary arrays in your nodes, though, it's slightly more
    annoying, in that you'll have to get an array big enough to hold the
    largest string in the list, and use that as your tmp, using strcpy rather
    than assignment.

    Once you've got that in place, it's just a matter of doing the right
    compares and the right swaps in the right order.

    --
    Richard Heathfield
    "Usenet is a strange place" - dmr 29/7/1999
    http://www.cpax.org.uk
    email: normal service will be restored as soon as possible. Please do not
    adjust your email clients.
     
    Richard Heathfield, Nov 20, 2006
    #2
    1. Advertising

  3. incredible

    Ben Pfaff Guest

    "incredible" <> writes:

    > how to sort link list of string


    There's a pair of fairly complete and fairly portable linked list
    libraries here:
    http://cvs.savannah.gnu.org/viewcvs/pspp/src/libpspp/?root=pspp
    Look at ll.[ch] and llx.[ch].
    --
    int main(void){char p[]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz.\
    \n",*q="kl BIcNBFr.NKEzjwCIxNJC";int i=sizeof p/2;char *strchr();int putchar(\
    );while(*q){i+=strchr(p,*q++)-p;if(i>=(int)sizeof p)i-=sizeof p-1;putchar(p\
    );}return 0;}
     
    Ben Pfaff, Nov 20, 2006
    #3
  4. incredible

    Eric Sosman Guest

    incredible wrote On 11/20/06 12:05,:
    > how to sort link list of string


    /* Usage instructions: Declare a `struct node' type containing a
    * `struct node*' field named `next' as its forward link, along with
    * whatever other elements are desired. Define a precedes() function
    * that takes two `const struct node*' pointers and returns nonzero
    * if the first struct must precede the second in the sorted output,
    * or zero if the first follows the second or if they compare equal.
    * Build a linked list of `struct node' instances, with the `next'
    * field of the last node equal to NULL. Call the listsort() function,
    * passing a pointer to the first node as the argument. listsort()
    * will rearrange the list's links to sort the list in accordance with
    * the precedes() function, and will return a pointer to the first
    * `struct node' of the sorted list.
    *
    * Note: This code uses an OO style.
    */

    #include <limits.h>
    static struct node*O(struct node*o,struct node*O){struct node*Oo,**oO;
    oO=&Oo;for(;;){if(precedes(O,o)){*oO=O;oO=&O->next;if(0==(O=O->next)){
    *oO=o;break;}}else{*oO=o;oO=&o->next;if(!(o=o->next)){*oO=O;break;}}}\
    return Oo;}struct node*listsort(struct node*oO){struct node*o,*o0[siz\
    eof(void*)*CHAR_BIT-sizeof(char)],*Oo;int oo,O0;o0[O0=0]=0;while((o=o\
    O)){if((Oo=o->next)==0)break;oO=Oo->next;if(precedes(Oo,o)){Oo->next=o
    ;o->next=0;o=Oo;}else{Oo->next=0;}for(oo=0;(Oo=o0[oo]);){o0[oo]=0;o=O(
    Oo,o);if(++oo>O0){O0=oo;break;}}o0[oo]=o;}for(oo=0;oo<=O0;++oo){if((o=
    o0[oo]))oO=oO?O(o,oO):eek:;}return oO;}

    --
     
    Eric Sosman, Nov 20, 2006
    #4
  5. incredible

    Tor Rustad Guest

    Eric Sosman skrev:

    > * Note: This code uses an OO style.


    ROFL!

    --
    Tor
     
    Tor Rustad, Nov 20, 2006
    #5
  6. incredible

    CBFalconer Guest

    Eric Sosman wrote:
    > incredible wrote On 11/20/06 12:05,:
    >
    >> how to sort link list of string

    >
    > /* Usage instructions: Declare a `struct node' type containing a
    > * `struct node*' field named `next' as its forward link, along with
    > * whatever other elements are desired. Define a precedes() function
    > * that takes two `const struct node*' pointers and returns nonzero
    > * if the first struct must precede the second in the sorted output,
    > * or zero if the first follows the second or if they compare equal.
    > * Build a linked list of `struct node' instances, with the `next'
    > * field of the last node equal to NULL. Call the listsort() function,
    > * passing a pointer to the first node as the argument. listsort()
    > * will rearrange the list's links to sort the list in accordance with
    > * the precedes() function, and will return a pointer to the first
    > * `struct node' of the sorted list.
    > *
    > * Note: This code uses an OO style.
    > */
    >
    > #include <limits.h>
    > static struct node*O(struct node*o,struct node*O){struct node*Oo,**oO;
    > oO=&Oo;for(;;){if(precedes(O,o)){*oO=O;oO=&O->next;if(0==(O=O->next)){
    > *oO=o;break;}}else{*oO=o;oO=&o->next;if(!(o=o->next)){*oO=O;break;}}}\
    > return Oo;}struct node*listsort(struct node*oO){struct node*o,*o0[siz\
    > eof(void*)*CHAR_BIT-sizeof(char)],*Oo;int oo,O0;o0[O0=0]=0;while((o=o\
    > O)){if((Oo=o->next)==0)break;oO=Oo->next;if(precedes(Oo,o)){Oo->next=o
    > ;o->next=0;o=Oo;}else{Oo->next=0;}for(oo=0;(Oo=o0[oo]);){o0[oo]=0;o=O(
    > Oo,o);if(++oo>O0){O0=oo;break;}}o0[oo]=o;}for(oo=0;oo<=O0;++oo){if((o=
    > o0[oo]))oO=oO?O(o,oO):eek:;}return oO;}


    [1] c:\c\junk>cc junk.c
    junk.c: In function `O':
    junk.c:3: warning: implicit declaration of function `precedes'
    junk.c:3: dereferencing pointer to incomplete type
    junk.c:3: dereferencing pointer to incomplete type
    junk.c:4: dereferencing pointer to incomplete type
    junk.c:4: dereferencing pointer to incomplete type
    junk.c: In function `listsort':
    junk.c:4: dereferencing pointer to incomplete type
    junk.c:4: dereferencing pointer to incomplete type
    junk.c:4: dereferencing pointer to incomplete type
    junk.c:8: dereferencing pointer to incomplete type
    junk.c:8: dereferencing pointer to incomplete type

    --
    Chuck F (cbfalconer at maineline dot net)
    Available for consulting/temporary embedded and systems.
    <http://cbfalconer.home.att.net>
     
    CBFalconer, Nov 20, 2006
    #6
  7. incredible

    Eric Sosman Guest

    CBFalconer wrote On 11/20/06 16:06,:
    > Eric Sosman wrote:
    >
    >>incredible wrote On 11/20/06 12:05,:
    >>
    >>
    >>>how to sort link list of string

    >>
    >>/* Usage instructions: Declare a `struct node' type containing a
    >> * `struct node*' field named `next' as its forward link, along with
    >> * whatever other elements are desired. Define a precedes() function
    >> * that takes two `const struct node*' pointers and returns nonzero
    >> * if the first struct must precede the second in the sorted output,
    >> * or zero if the first follows the second or if they compare equal.
    >> * Build a linked list of `struct node' instances, with the `next'
    >> * field of the last node equal to NULL. Call the listsort() function,
    >> * passing a pointer to the first node as the argument. listsort()
    >> * will rearrange the list's links to sort the list in accordance with
    >> * the precedes() function, and will return a pointer to the first
    >> * `struct node' of the sorted list.
    >> *
    >> * Note: This code uses an OO style.
    >> */
    >>
    >>#include <limits.h>
    >>static struct node*O(struct node*o,struct node*O){struct node*Oo,**oO;
    >>oO=&Oo;for(;;){if(precedes(O,o)){*oO=O;oO=&O->next;if(0==(O=O->next)){
    >>*oO=o;break;}}else{*oO=o;oO=&o->next;if(!(o=o->next)){*oO=O;break;}}}\
    >>return Oo;}struct node*listsort(struct node*oO){struct node*o,*o0[siz\
    >>eof(void*)*CHAR_BIT-sizeof(char)],*Oo;int oo,O0;o0[O0=0]=0;while((o=o\
    >>O)){if((Oo=o->next)==0)break;oO=Oo->next;if(precedes(Oo,o)){Oo->next=o
    >>;o->next=0;o=Oo;}else{Oo->next=0;}for(oo=0;(Oo=o0[oo]);){o0[oo]=0;o=O(
    >>Oo,o);if(++oo>O0){O0=oo;break;}}o0[oo]=o;}for(oo=0;oo<=O0;++oo){if((o=
    >>o0[oo]))oO=oO?O(o,oO):eek:;}return oO;}

    >
    >
    > [1] c:\c\junk>cc junk.c
    > junk.c: In function `O':
    > junk.c:3: warning: implicit declaration of function `precedes'
    > junk.c:3: dereferencing pointer to incomplete type
    > junk.c:3: dereferencing pointer to incomplete type
    > junk.c:4: dereferencing pointer to incomplete type
    > junk.c:4: dereferencing pointer to incomplete type
    > junk.c: In function `listsort':
    > junk.c:4: dereferencing pointer to incomplete type
    > junk.c:4: dereferencing pointer to incomplete type
    > junk.c:4: dereferencing pointer to incomplete type
    > junk.c:8: dereferencing pointer to incomplete type
    > junk.c:8: dereferencing pointer to incomplete type


    Looks like you failed to heed the usage instructions.

    --
     
    Eric Sosman, Nov 20, 2006
    #7
  8. incredible

    pete Guest

    incredible wrote:
    >
    > how to sort link list of string


    /* BEGIN new.c output */

    Original order of list:
    one
    two
    three
    four
    five
    six
    seven
    eight
    nine
    ten

    List after stable mergesort by string length:
    one
    two
    six
    ten
    four
    five
    nine
    three
    seven
    eight

    The list has been freed.

    /* END new.c output */


    /* BEGIN new.c */

    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>

    #define NMEMB(A) (sizeof (A) / sizeof *(A))

    struct list_node {
    struct list_node *next;
    void *data;
    };

    typedef struct list_node list_type;

    void list_free(list_type *node, void (*free_data)(void *));
    void list_fputs(FILE *stream, list_type *node);
    list_type *string_node(list_type **head,
    list_type *tail,
    char *data);
    int lencomp(const void *a, const void *b);
    list_type *list_sort(list_type *head,
    int (*compar)(const list_type *, const list_type *));
    static int list_sorted(list_type *list,
    int (*compar)(const list_type *, const list_type *));
    static long unsigned node_count(list_type *head);
    static list_type *node_sort(list_type *head, long unsigned count,
    int (*compar)(const list_type *, const list_type *));
    static list_type *list_split(list_type *head, long unsigned count);
    static list_type *list_merge(list_type *head, list_type *tail,
    int (*compar)(const list_type *, const list_type *));

    int main(void)
    {
    char *string[] = {
    "one","two","three","four","five",
    "six","seven","eight","nine","ten"
    };
    list_type *head, *tail;
    unsigned index;

    tail = head = NULL;
    index = 0;
    do {
    tail = string_node(&head, tail, string[index]);
    } while (tail != NULL && ++index != NMEMB(string));
    if (tail == NULL) {
    list_free(head, free);
    puts("malloc trouble!");
    exit(EXIT_FAILURE);
    }
    puts("/* BEGIN new.c output */\n");
    puts("Original order of list:");
    list_fputs(stdout, head);
    head = list_sort(head, lencomp);
    puts("\nList after stable mergesort by string length:");
    list_fputs(stdout, head);
    list_free(head, free);
    puts("\nThe list has been freed.\n");
    puts("/* END new.c output */");
    return 0;
    }

    void list_free(list_type *node, void (*free_data)(void *))
    {
    list_type *next_node;

    while (node != NULL) {
    next_node = node -> next;
    free_data(node -> data);
    free(node);
    node = next_node;
    }
    }

    void list_fputs(FILE *stream, list_type *node)
    {
    while (node != NULL) {
    fputs(node -> data, stream);
    putc('\n', stream);
    node = node -> next;
    }
    }

    list_type *string_node(list_type **head,
    list_type *tail,
    char *data)
    {
    list_type *node;

    node = malloc(sizeof *node);
    if (node != NULL) {
    node -> next = NULL;
    node -> data = malloc(strlen(data) + 1);
    if (node -> data != NULL) {
    if (*head == NULL) {
    *head = node;
    } else {
    tail -> next = node;
    }
    strcpy(node -> data, data);
    } else {
    free(node);
    node = NULL;
    }
    }
    return node;
    }

    int lencomp(const void *a, const void *b)
    {
    const size_t a_len = strlen(((const list_type *)a) -> data);
    const size_t b_len = strlen(((const list_type *)b) -> data);

    return b_len > a_len ? -1 : a_len != b_len;
    }

    list_type *list_sort(list_type *head,
    int (*compar)(const list_type *, const list_type *))
    {
    return
    !list_sorted(head, compar)
    ? node_sort(head, node_count(head), compar)
    : head;
    }

    static int list_sorted(list_type *list,
    int (*compar)(const list_type *, const list_type *))
    {
    if (list != NULL) {
    while (list -> next != NULL) {
    if (compar(list, list -> next) > 0) {
    break;
    }
    list = list -> next;
    }
    }
    return list == NULL || list -> next == NULL;
    }

    static long unsigned node_count(list_type *head)
    {
    long unsigned count;

    for (count = 0; head != NULL; head = head -> next) {
    ++count;
    }
    return count;
    }

    static list_type *node_sort(list_type *head, long unsigned count,
    int (*compar)(const list_type *, const list_type *))
    {
    long unsigned half;
    list_type *tail;

    if (count > 1) {
    half = count / 2;
    tail = list_split(head, half);
    tail = node_sort(tail, count - half, compar);
    head = node_sort(head, half, compar);
    head = list_merge(head, tail, compar);
    }
    return head;
    }

    static list_type *list_split(list_type *head, long unsigned count)
    {
    list_type *tail;

    while (--count != 0) {
    head = head -> next;
    }
    tail = head -> next;
    head -> next = NULL;
    return tail;
    }

    static list_type *list_merge(list_type *head, list_type *tail,
    int (*compar)(const list_type *, const list_type *))
    {
    list_type *list, *sorted, **node;

    node = compar(head, tail) > 0 ? &tail : &head;
    sorted = list = *node;
    *node = sorted -> next;
    while (*node != NULL) {
    node = compar(head, tail) > 0 ? &tail : &head;
    sorted -> next = *node;
    sorted = *node;
    *node = sorted -> next;
    }
    sorted -> next = head != NULL ? head : tail;
    return list;
    }

    /* END new.c */


    --
    pete
     
    pete, Nov 21, 2006
    #8
  9. incredible

    CBFalconer Guest

    incredible wrote:
    >
    > how to sort link list of string


    /* Sort file stdin. By C.B. Falconer, 20 Nov. 2006 */
    /* Released to public domain. Attribution appreciated */
    /* Run with "sortfile < whatever" */

    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>

    typedef struct line {
    char *ln;
    struct line *next;
    } line, *lineptr;

    /* ------------------------- */

    #define INITSIZE 112
    #define DELTASIZE (INITSIZE + 16)

    enum {OK = 0, NOMEM};

    /* See published ggets.zip */
    int ggets(char* *ln)
    {
    int cursize, ch, ix;
    char *buffer, *temp;

    *ln = NULL; /* default */
    if (NULL == (buffer = malloc(INITSIZE))) return NOMEM;
    cursize = INITSIZE;

    ix = 0;
    while ((EOF != (ch = getc(stdin))) && ('\n' != ch)) {
    if (ix >= (cursize - 1)) { /* extend buffer */
    cursize += DELTASIZE;
    if (NULL == (temp = realloc(buffer, (size_t)cursize))) {
    /* ran out of memory, return partial line */
    buffer[ix] = '\0';
    *ln = buffer;
    return NOMEM;
    }
    buffer = temp;
    }
    buffer[ix++] = ch;
    }
    if ((EOF == ch) && (0 == ix)) {
    free(buffer);
    return EOF;
    }

    buffer[ix] = '\0';
    if (NULL == (temp = realloc(buffer, (size_t)ix + 1))) {
    *ln = buffer; /* without reducing it */
    }
    else *ln = temp;
    return OK;
    } /* ggets */

    /* ------------------------- */

    /* split list p into 2 nearly equal lists, return 2nd part */
    static lineptr splitlist(lineptr p)
    {
    lineptr p1, p2, p3;

    p1 = p2 = p3 = p;
    if (!p) return NULL;
    do {
    p3 = p2;
    p2 = p2->next; /* advance 1 */
    p1 = p1->next;
    if (p1) p1 = p1->next; /* advance 2 */
    } while (p1);

    /* now form new list after p2 */
    p3->next = NULL; /* terminate 1st half */
    return p2;
    } /* splitlist */

    /* ------------------------- */

    /* Merge two ordered lists into one */
    static lineptr mergelists(lineptr p1, lineptr p2)
    {
    line n;
    lineptr p;

    p = &n;
    n.next = p;

    while (p1 && p2) {
    if (strcmp(p1->ln, p2->ln) <= 0) {
    p->next = p1; p = p1; p1 = p1->next;
    }
    else {
    p->next = p2; p = p2; p2 = p2->next;
    }
    }
    /* at least one list now empty, copy other */
    /* one or both of these operations is null */
    if (p1) p->next = p1;
    if (p2) p->next = p2;

    /* check for empty lists */
    if (n.next == &n) return NULL;
    return n.next;
    } /* mergelists */

    /* ------------------------- */

    /* Recursively sort a linked list. The sort is stable */
    /* This is an O(NlogN) process for all lists. */
    static lineptr mergesort(lineptr root)
    {
    lineptr p;

    if (root && root->next) { /* 2 up items in list */
    p = splitlist(root); /* alters list root */
    root = mergelists(mergesort(root),
    mergesort( p));
    }
    /* else the unit or empty list is already sorted */

    return root;
    } /* mergesort */

    /* ------------------------- */

    /* Load, sort, and print file, which fits in memory. */
    int main(void)
    {
    lineptr p, last;
    char *nextln;

    p = NULL;
    while (0 == ggets(&nextln))
    if ((last = malloc(sizeof *last))) {
    last->ln = nextln;
    last->next = p;
    p = last;
    }
    else break; /* out of memory or i/o error */

    p = mergesort(p);

    while (p) {
    puts(p->ln);
    last = p;
    p = p->next;
    free(last->ln);
    free(last);
    }
    return 0;
    } /* sortfile main */

    --
    Chuck F (cbfalconer at maineline dot net)
    Available for consulting/temporary embedded and systems.
    <http://cbfalconer.home.att.net>
     
    CBFalconer, Nov 21, 2006
    #9
  10. incredible

    pete Guest

    pete wrote:

    > list_type *list_sort(list_type *head,
    > int (*compar)(const list_type *, const list_type *));


    > head = list_sort(head, lencomp);


    > int lencomp(const void *a, const void *b)
    > {
    > const size_t a_len = strlen(((const list_type *)a) -> data);
    > const size_t b_len = strlen(((const list_type *)b) -> data);
    >
    > return b_len > a_len ? -1 : a_len != b_len;
    > }


    That function's prototype should be
    int lencomp(const list_type *a, const list_type *b);
    and the definition should be:

    int lencomp(const list_type *a, const list_type *b)
    {
    const size_t a_len = strlen(a -> data);
    const size_t b_len = strlen(b -> data);

    return b_len > a_len ? -1 : a_len != b_len;
    }

    instead.

    --
    pete
     
    pete, Nov 21, 2006
    #10
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. grocery_stocker
    Replies:
    10
    Views:
    632
    Keith Thompson
    May 25, 2005
  2. incredible
    Replies:
    2
    Views:
    530
    jacob navia
    Nov 20, 2006
  3. spike
    Replies:
    8
    Views:
    1,479
    Steve Holden
    Feb 9, 2010
  4. Navin
    Replies:
    1
    Views:
    705
    Ken Schaefer
    Sep 9, 2003
  5. Ravi Prabakaran
    Replies:
    8
    Views:
    115
    Terry Reedy
    Dec 16, 2013
Loading...

Share This Page