The method you're using to sort your linked list is to utilize an intermediate pointer-bed. i.e. a sequence holding all the node pointers, then using a canned sorting operation like qsort
, then rebuilding the list.
The most fundamental problem is your comparator. It's wrong. The qsort
comparator should expect the address of each element being sorted as arguments. Since you're sorting a sequence of pointers, the address of an element is therefore the address of a pointer. E.g. a pointer to pointer.
int cmpfunc(const void *a, const void* b)
{
const struct Node * const * pp1 = a;
const struct Node * const * pp2 = b;
return ((*pp1)->task->burst - (*pp2)->task->burst);
}
In addition to that, but not related to your sorting issue, your build loop for your pointer bed leaks memory. This line:
ordered_list[i] = malloc(sizeof(struct Node));
is pointless. get rid of it.
Working Example
The following is a trivial working example you can adapt as needed.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
struct Node
{
int data;
struct Node *next;
};
int cmpfunc(const void *arg1, const void *arg2)
{
const struct Node * const * lhs = arg1;
const struct Node * const * rhs = arg2;
return (*lhs)->data < (*rhs)->data ? -1 : (*rhs)->data < (*lhs)->data;
}
struct Node *schedule(struct Node *head)
{
struct Node **arr = NULL;
size_t capacity = 0;
size_t size = 0;
while (head)
{
if (size == capacity)
{
size_t new_capacity = capacity ? 2 * capacity : 1;
void *tmp = realloc(arr, new_capacity * sizeof *arr);
if (!tmp)
{
perror("Failed to expand sorting array");
exit(EXIT_FAILURE);
}
arr = tmp;
capacity = new_capacity;
}
arr[size++] = head;
head = head->next;
}
if (size > 0)
{
qsort(arr, size, sizeof *arr, cmpfunc);
struct Node **pp = &head;
for (size_t i=0; i<size; ++i)
{
*pp = arr[i];
pp = &(*pp)->next;
}
*pp = NULL;
// don't need this anymore
free(arr);
}
return head;
}
int main()
{
srand((unsigned)time(NULL));
// build a random linked list
struct Node *head = NULL, **pp = &head;
for (int i=0; i<20; ++i)
{
*pp = malloc( sizeof **pp );
(*pp)->data = 1 + rand() % 99;
printf("%d ", (*pp)->data);
pp = &(*pp)->next;
}
*pp = NULL;
fputc('
', stdout);
head = schedule(head);
for (const struct Node *p = head; p;p = p->next)
{
printf("%d ", p->data);
}
fputc('
', stdout);
// free the list
while (head)
{
void *p = head;
head = head->next;
free(p);
}
return EXIT_SUCCESS;
}
Output (varies)
54 85 69 83 13 69 74 64 90 19 83 80 92 25 95 93 49 38 6 83
6 13 19 25 38 49 54 64 69 69 74 80 83 83 83 85 90 92 93 95
与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…