对链表节点数组进行排序

Question

我正在用 C 编写一个任务调度程序。我设法将包含任务的链表的节点复制到一个数组中。我是。尝试实现最短作业优先调度算法，代码如下：

void schedule (struct Node* head){
    struct  Node* temp = head;
    struct Node** ordered_list = malloc(sizeof(struct Node*) * count);
        
    for (int i =0 ; i <count-1; i++) {
        ordered_list[i] = malloc(sizeof(struct Node));
        ordered_list[i] = temp;
        temp = temp-> next;
    }
    
    
    ordered_list[count-1] = temp;

    

    qsort(ordered_list, count, sizeof(struct Node ), cmpfunc);

比较函数是

    int cmpfunc(const void *a, const void* b){
        struct Node *node1 = (struct Node*) a;
        struct Node *node2 = (struct Node*) b;
        return (node1->task->burst - node2->task->burst);
    
    }

我被分段错误困住了。我发现它在 qsort 函数中。然而，我不知道它有什么问题。

Answer 1

在 schedule 的循环中，您分配 space 并将其分配给 ordered_list[i]，然后立即覆盖该分配。并且由于您从未将任何内容分配给任何内容的 next，因此 link 将是有问题的。

Answer 2

您用来对链表进行排序的方法是使用中间指针床。即一个包含所有节点指针的序列，然后使用像 qsort 这样的固定排序操作，然后重建列表。

最根本的问题是你的比较器。这是错的。 qsort 比较器应该期望每个被排序的元素的地址作为参数。由于您正在对一系列指针进行排序，因此元素的地址就是指针的地址。例如。 指向指针的指针。

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);
}

除此之外，与您的排序问题无关的是，指针床的构建循环泄漏了内存。这一行：

ordered_list[i] = malloc(sizeof(struct Node));

毫无意义。摆脱它。

工作示例

以下是一个简单的工作示例，您可以根据需要进行调整。

#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('\n', stdout);

    head = schedule(head);
    for (const struct Node *p = head; p;p = p->next)
    {
        printf("%d ", p->data);
    }
    fputc('\n', stdout);

    // free the list
    while (head)
    {
        void *p = head;
        head = head->next;
        free(p);
    }
    
    return EXIT_SUCCESS;
}

输出（变化）

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

对链表节点数组进行排序

Sorting an array of linked list nodes

c

qsort