Doesn't qsort() C library function work on linked lists?
I am trying to sort a singly linked list which has been created and all its items,pointers initialized. I am trying to use qsort() C library function as shown below. It doesn't seem to sort the list. It is giving me compiler error saying: left of 'item' specifies undefined struct/union 'LINKED_LIST_S' at line shown below in the code.
struct LINKED_LIST_S
{
int item;
struct LINKED_LIST_S * next;
} ;
typedef int (*cmpfn)(const void *ptr1, const void *ptr2);
int mylistsort(my_list_t list, cmpfn f1)
{
qsort ( list , 100, sizeof (struct LINKED_LIST_S), (fn) );
return -1;
}
int sort_fn_ascend(const void *ptr1, const void *ptr2)
{
int a = (*(LINKED_LIST_S *)ptr1).item; //Compiler error
int b = (*(LINKED_LIST_S *)ptr2).item; //Compiler error
return b - a;
}
int sort_fn_descend(const void *ptr1, const void *ptr2)
{
int a = ((struct LINKED_LIST_S *)ptr1)->item; //Compiler error
int b = ((struct LINKED_LIST_S *)ptr2)->item; //Compiler error
return a - b;
}
this is how the function mylistsort() is called at 2 places:
mylistsort(list, sort_fn_descend);//where list a properly initialized linked list pointer.
mylistsort(list, sort_fn_ascend);//where list a properly initialized linked list pointer.
1] Doesn't qsort() work on linked list if the head node poitner is passed as base array(first argument) to qsort.
2] How do I achieve the sorting of this linked list using qsort() in above code?
EDIT: Thanks for the answers. Now I have implemented a way to sort a list as mentioned by @muksie approach 1] he suggested, as code below. Still qsort() does not return a sorted array of ints. First I want to sort an array of 100 elements, in descending order, but passed array is exact reverse, i.e. the elements are in ascending order of from 1,2,...100. What am I doing wrong? How can I fix it?
int linkedListSort(LINKED_LIST_T list, newCompareFunction fn, void *usr_info)
{
LINKED_LIST_T tmpptr = list;
int newitems[N_ITEMS];
int i=0;
//Logic to get all the items in the list in a array
while(tmpptr != NULL)
{
newitems[i] = tmpptr->item;
tmpptr = tmpptr->next;
i++;
}
tmpptr = list;
i = 0;
//Sort that array
//qsort ( list , 100, sizeof (struct LINKED_LIST_S), (fn) );
qsort ( newitems , 100, sizeof(list->item), (fn) );
//store the sorted items back into the list.
while(tmpptr != NULL)
{
tmpptr->item = newitems[i];
tmpptr = tmpptr->next;
i++;
}
return -1;
}
int sort_fn_descend(void *ptr1,void *ptr2)
{
int a = *((int*)(ptr1));
int b = *((int*) (ptr2));
return a - b;
}
int sort_fn_ascend(const void *ptr1, const void *ptr2)
{
int a = *((int*)(ptr1));
int b = *((int*) (ptr2));
return b - a;
}
开发者_开发百科
qsort
works on plain arrays of equally sized data, not linked lists.
To sort your linked list you can consider the following options:
- Create a plain array with all values of the linked list, sort this, and transform back into a linked list.
- Implement the quicksort algorithm for your linked list data structure.
Since I was able to solve the problem, using approach 2] suggested by @muskie in his answer, I am posting the answer here. A bug fix in functions sort_fn_descend/ascend, mentioned in the edited OP was needed , and the code is sorting the list jsut fine. Bug fix FYI - the descend function above should return b - a and ascend fn should return a - b.
精彩评论