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.

: 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:

Definition of the structure

typedef struct link_s
 {
 char *s;
 struct link_s *next;
 }
 LINK;

The field "next" is used to link the elements together. When you want to insert element Y after element X, you can do:

Y->next=X->next;
X->next=Y;

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

Steph

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:\n");
if (prev != NULL)
printf(" prec %s\n",(prev)->element);
printf(" curr %s\n",(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\n");//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\n");//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

: 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:\n");
: if (prev != NULL)
: printf(" prec %s\n",(prev)->element);
: printf(" curr %s\n",(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\n");//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\n");//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

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!!!\n");}
}
//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
>

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