linked list & sorting - Programmers Heaven

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

linked list & sorting

ednorednor Posts: 3Member
hi,
i'm a newbie
my problem
is the implementation of insertion sort method using the linked list of string elements ;
it's easy do it using arrays and i did it
but with pointer it's really hard
anyone can help me or just tell me where i can find any help
thx a lot
ed.nor.

Comments

  • stephlstephl Posts: 422Member
    : hi,
    : i'm a newbie
    : my problem
    : is the implementation of insertion sort method using the linked list of string elements ;
    : it's easy do it using arrays and i did it
    : but with pointer it's really hard
    : anyone can help me or just tell me where i can find any help
    : thx a lot
    : ed.nor.
    :
    Some tips:

    [b]Definition of the structure[/b]
    [code]
    typedef struct link_s
    {
    char *s;
    struct link_s *next;
    }
    LINK;
    [/code]

    The field "next" is used to link the elements together. When you want to insert element Y after element X, you can do:
    [code]
    Y->next=X->next;
    X->next=Y;
    [/code]

    These are the basics. Now you should try to write some code and post it if you encounter any problem.

    Steph
  • bilderbikkelbilderbikkel Posts: 754Member
    Check
    http://www.codepedia.com/1/CppInsertionSort
    http://www.codepedia.com/1/LinkedList

    Feel free to translate the insertionsort routine to C and put them at the CodePedia (e.g. with the name http://www.codepedia.com/1/CInsertionSort).

    See ya,

    bilderbikkel

  • ednorednor Posts: 3Member
    i use this definition

    typedef struct node* stringlist;

    struct node
    {
    char *element;
    stringlist next;
    };

    //my method insertion sort at this point,( i will work to make it
    ok),is :

    void insertionSort(stringlist *list)
    {
    struct node *curr, *prev, *toinsert, *end, *temp;
    prev = NULL;
    curr = *list;
    end = curr;
    char tasto;
    toinsert = (end)->next;

    while (toinsert != NULL)// while you aren't at the end (and the list is sorted)
    {

    printf("list before while is:");//printf used for debug
    printListIt(*list);

    while ( (curr != toinsert) && ( (strcmp((curr)->element,(toinsert)->element)) < 0) )
    {
    //printf used for debug
    printf("while interno:
    ");
    if (prev != NULL)
    printf(" prec %s
    ",(prev)->element);
    printf(" curr %s
    ",(curr)->element);
    // end printf used for debug

    //move to find position of insertion
    prev = curr;
    curr = (curr)->next;
    }//end internal while

    if ( curr != toinsert)
    {
    if (prev!= NULL)
    {
    printf("prev!=NULL
    ");//printf used for debug
    (prev)->next = toinsert;
    //(end)->next = (toinsert)->next;
    (toinsert)->next = curr;
    }
    else //prev==NULL means insert in head of list
    {
    printf("prev==NULL
    ");//printf used for debug
    prev = toinsert;
    (curr)->next = (toinsert)->next;
    (toinsert)->next = curr;
    *list = prev;

    }

    toinsert = (end)->next;
    }
    else //if curr == toinsert means toinsert is already sorted
    {
    // prev = NULL;
    //curr = *list;
    end =(end)->next;//move the end of list partially sorted

    toinsert = (end)->next;

    }
    prev = NULL;
    curr = *list;
    printf("list after while e':");//printf used for debug
    printListIt(*list);
    }//end external while

    }//END insertion sort


  • stephlstephl Posts: 422Member
    : i use this definition
    :
    : typedef struct node* stringlist;
    :
    : struct node
    : {
    : char *element;
    : stringlist next;
    : };
    :
    : //my method insertion sort at this point,( i will work to make it
    : ok),is :
    :
    : void insertionSort(stringlist *list)
    : {
    : struct node *curr, *prev, *toinsert, *end, *temp;
    : prev = NULL;
    : curr = *list;
    : end = curr;
    : char tasto;
    : toinsert = (end)->next;
    :
    : while (toinsert != NULL)// while you aren't at the end (and the list is sorted)
    : {
    :
    : printf("list before while is:");//printf used for debug
    : printListIt(*list);
    :
    : while ( (curr != toinsert) && ( (strcmp((curr)->element,(toinsert)->element)) < 0) )
    : {
    : //printf used for debug
    : printf("while interno:
    ");
    : if (prev != NULL)
    : printf(" prec %s
    ",(prev)->element);
    : printf(" curr %s
    ",(curr)->element);
    : // end printf used for debug
    :
    : //move to find position of insertion
    : prev = curr;
    : curr = (curr)->next;
    : }//end internal while
    :
    : if ( curr != toinsert)
    : {
    : if (prev!= NULL)
    : {
    : printf("prev!=NULL
    ");//printf used for debug
    : (prev)->next = toinsert;
    : //(end)->next = (toinsert)->next;
    : (toinsert)->next = curr;
    : }
    : else //prev==NULL means insert in head of list
    : {
    : printf("prev==NULL
    ");//printf used for debug
    : prev = toinsert;
    : (curr)->next = (toinsert)->next;
    : (toinsert)->next = curr;
    : *list = prev;
    :
    : }
    :
    : toinsert = (end)->next;
    : }
    : else //if curr == toinsert means toinsert is already sorted
    : {
    : // prev = NULL;
    : //curr = *list;
    : end =(end)->next;//move the end of list partially sorted
    :
    : toinsert = (end)->next;
    :
    : }
    : prev = NULL;
    : curr = *list;
    : printf("list after while e':");//printf used for debug
    : printListIt(*list);
    : }//end external while
    :
    : }//END insertion sort
    :
    :
    :
    You did not mention whether your algorithm works or not. If there's a problem with it, please explain what it is so that we may have an idea of where to look for a mistake.

    Steph
  • ednorednor Posts: 3Member
    EUREKA! i do it!
    THX for tips Steph & bilderbikkel
    i don't know if it is optimized but it work correctly:
    //START CODE
    /**
    insertionSort
    */
    /*
    Name: ednor
    Copyright:
    Author: ednor @
    Date: 26/11/06 14.28
    Description: implementation of insertionSort
    using linked list of string implemented as:

    typedef struct node* stringlist;

    struct node
    {
    char *element;
    stringlist next;
    };



    */

    void insertionSort(stringlist *list)
    {
    struct node *curr, *prev, *toinsert, *end, *temp;

    if (*list != NULL)
    {


    end = *list;
    temp = end;
    toinsert = (end)->next;

    while (toinsert != NULL)// while you aren't at the end (and the list is sorted)
    {
    prev = NULL;
    curr = *list;
    while ( (curr != toinsert) && ( (strcmp((curr)->element,(toinsert)->element)) < 0) )
    {//move to find position of insertion
    prev = curr;
    curr = (curr)->next;
    }//end internal while

    if ( curr != toinsert)
    {
    if (prev!= NULL)
    {
    (prev)->next = toinsert;
    if ( (toinsert)->next != NULL )
    (temp)->next = (toinsert)->next;
    else
    (temp)->next = NULL;
    (toinsert)->next = curr;
    }
    else //prev==NULL means insert in head of list
    {
    if ( (toinsert)->next != NULL )
    (temp)->next = (toinsert)->next;
    else
    (temp)->next = NULL;
    (toinsert)->next = *list;
    *list = toinsert;
    }

    }
    else //if curr == toinsert means toinsert is already sorted
    {
    end =(end)->next;
    temp = end;
    }
    if (end != NULL) //
    toinsert = (end)->next;
    }//end external while


    }
    else
    {printf("empty LIST!!!
    ");}
    }
    //END CODE



    > You did not mention whether your algorithm works or not. If there's a >problem with it, please explain what it is so that we may have an idea of >where to look for a mistake.
    >
    > Steph
    >
Sign In or Register to comment.