Hello everybody!
This is a quite good exercise for training with pointers: so good that I'm getting crazy!
In linux, a doubly-linked list is implemented by means of a list_head structure defined as follows:
Code:
struct list_head{
struct list_head *next;
struct list_head *prev;
};
The head of the list is a struct list_head head which is initialized as follows:
Code:
head.next=&head;
head.prev=&head
We can use this data structure to define lists of every type, simple as
Code:
struct node{
struct list_head lh;
int value;
}
or more complex like:
Code:
struct node{
struct list_head lh;
int age;
char firstname[25];
char lastname[25];
};
My problem is understanding how a sort algorithm could be implemented in a "general" way. For example, I had to sort the 1st kind of nodes according to their values and I did this in a "dirty" way, by swapping the values (I omit some obvious typedefs) :
Code:
void swap (int *a, int *b)
{
int tmp = *a;
*a=*b;
*b=tmp;
}
void sort (ListHeadPtr head)
{
ListHeadPtr aPtr,bPtr;
for (aPtr=head->next; aPtr!=head; aPtr=aPtr->next)
{
for (bPtr=head->next;bPtr!=head;bPtr=bPtr->next)
{
if ( (aPtr!=bPtr)&&( ((NodePtr)aPtr)->value < ((NodePtr)bPtr)->value) )
{
swap (&(((NodePtr)aPtr)->value),&(((NodePtr)bPtr)->value));
}
}
}
}
But I don't like this solution.. I'd like to swap the whole node...
I tried swapping the lh fields but didn't work and I surrended since my brain got really messed-up.. How could I solve this?
Thanks a lot!
Bye