开发者

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:

  1. Create a plain array with all values of the linked list, sort this, and transform back into a linked list.
  2. 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.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜