c - 基于 C 中的 bool 函数对列表重新排序？

Question

给定一个列表和一个 bool 函数 f，如何重新排序该列表，使得 f(element) == 1 等所有元素都位于前面(这些元素的内部顺序无关紧要)以及所有元素f(element) == 0 位于列表的末尾(同样，它们的内部顺序并不重要)。

我尝试过，但它变得非常困惑，有很多指针。我想知道是否有人知道一种“干净”的方法来做到这一点？

感谢您的帮助。

Answer 1

如果你有一个数组，请使用 qsort:

#include <stdlib.h>

void qsort(void *base, size_t nmemb, size_t size,
           int (*compar)(const void *, const void *));

这是一个与 qsort 兼容并使用 f 的示例比较器。

int comp(const void* elem1, const void* elem2) {
    int a = f(*((type*)elem1)) ? 1 : 0;
    int b = f(*((type*)elem2)) ? 1 : 0;
    return a - b;
}

如果你有一个链接列表，那么:

linkedlist* sort(linkedlist* head) {
  linkedlist* newHead = NULL;
  linkedlist* newTail = NULL;
  linkedlist* backHead = NULL;
  linkedlist* backTail = NULL;

  linkedlist* currNode = head;
  while (currNode != NULL) {
    if (f(currNode)) {
      if (newHead == NULL) {
        newHead = newTail = currNode;
      } else {
        newTail.next = currNode;
        newTail = currNode;
      }
    } else {
      if (backHead == NULL) {
        backHead = backTail = currNode;
      } else {
        backTail.next = currNode;
        backTail = currNode;
      }
    }

    currNode = currNode.next;
  }

  if (currTail != NULL) {
     currTail.next = backHead;
  }
  if (backTail != NULL) {
     backTail.next = NULL;
  }
  return currHead != NULL ? currHead : backHead;
}