c - qsort 指向链表的指针数组，按结构成员值

Question

我正在尝试使用 qsort 函数按 id 对指向链表的指针数组进行排序。我如何根据 id 而不是内存地址来比较数组？我可以简单地通过取消引用从数组中获取值，但 id 在比较函数中不起作用。

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

struct node {
  int id;
  struct node *next;
};

int sort_items(const void *item, const void *item2) {
  struct node *a = (struct node *) item;
  struct node *b = (struct node *) item2;

  return (a->id) - (a->id);
}

void sort_linked_list(struct node *pntr) {
  const int size = 1024;
  int i = 0, j;
  struct node *current_node = pntr;
  struct node **sorted_array = malloc(sizeof(struct node*) * size);

  while(current_node != NULL) {
    sorted_array[i] = current_node;
    current_node = current_node -> next;
    i++;
  }

  qsort(sorted_array, size, sizeof(struct node *), sort_items);

  for (j = 0; j < 6; j++) {
    printf("%d\n", sorted_array[j]); 
  }

}

void print_list(struct node *start) {
  while(start != NULL) {
    printf("Node id in linked list: %d\n", start->id);
    start = start->next;
  }
}

int main (void) {
  struct node *node1, *node2, *node3, *node4, *node5, *node6, *node7;

  node1 = (struct node*) malloc(sizeof(struct node));
  node2 = (struct node*) malloc(sizeof(struct node));
  node3 = (struct node*) malloc(sizeof(struct node));
  node4 = (struct node*) malloc(sizeof(struct node));
  node5 = (struct node*) malloc(sizeof(struct node));
  node6 = (struct node*) malloc(sizeof(struct node));
  node7 = (struct node*) malloc(sizeof(struct node));

  node1->id = 2;
  node1->next = node2;
  node2->id = 1;
  node2->next = node3;
  node3->id = 3;
  node3->next = node4;
  node4->id = 6;
  node4->next = node5;
  node5->id = 5;
  node5->next = node6;
  node6->id = 4;
  node6->next = NULL;

  sort_linked_list(node1);

  print_list(node1);

  return 0;

}

Answer 1

代码有几处错误(除了 Michael 评论的打字错误)。我将帮助您解决您可能无法自行解决的细微错误。

qsort 将两个指针传递给您提供的比较函数。每个指针指向正在排序的项数组中的一项。如果数组是一个指针数组(这是您所拥有的)，那么比较函数的参数是 pointer-to-pointer 类型。因此，代码需要两次取消引用指针以获取 id。

比较函数的一种可能实现方式是

int compare( const void *item1, const void *item2 )
{
    struct node *a = *(struct node **)item1;   // first dereference gets the pointer to the struct
    struct node *b = *(struct node **)item2;    

    return( a->id - b->id );   // second dereference using -> notation gets the id
}

为了完整起见，代码中的其他问题是

• 传递给 qsort 的第二个参数应该是项目的数量在数组中，而不是为数组分配的内存大小
• 代码需要从排序数组重新创建链表，或者print_list 函数将简单地打印未排序的列表
• sort_linked_list 函数应该计算中的项目数分配内存之前的列表。要么，要么它应该抛出如果列表中的项目太多，则会出错。