Howdy, Stranger!

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

Categories

Welcome to the new platform of Programmer's Heaven! We apologize for the inconvenience caused, if you visited us from a broken link of the previous version. The main reason to move to a new platform is to provide more effective and collaborative experience to you all. Please feel free to experience the new platform and use its exciting features. Contact us for any issue that you need to get clarified. We are more than happy to help you.

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.