在 C 中对链表进行归并排序

Question

合并排序通常是排序链表的首选。链表缓慢的随机访问性能使得其他一些算法（例如快速排序）性能不佳，而其他算法（例如堆排序）则完全不可能。我一直在努力对链表进行合并排序。它不断抛出一个错误。我正在提供我试图执行的代码。请帮帮我。它一直给出运行时错误。

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

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

struct node *SortedMerge(struct node *a, struct node *b); 
void FrontBackSplit(struct node *source, struct node *frontref, struct node *backref); 

struct node *Create(struct node *head, int num) {
    struct node *newnode, *temp;
    newnode = (struct node *)malloc(sizeof(struct node));
    newnode->data = num;
    newnode->next = NULL;
    if (head == NULL) {
        head = newnode;
        temp = newnode;
    } else {
        temp->next = newnode;
        temp = temp->next;
    }
    temp->next = NULL; 
    return head;
}

struct node *display(struct node *head) {
    struct node *temp;
    temp = head;
    while (temp != NULL) {
        printf("%d->", temp->data);
        temp = temp->next;
    }
    printf("NULL");
    return head;
}

struct node *MergeSort(struct node *head) {
    struct node *headref, *a, *b;
    headref = head;
    if ((head == NULL) || (head->next) == NULL) {
        return;
    }

    FrontBackSplit(headref, a, b);

    MergeSort(a);
    MergeSort(b);

    head = SortedMerge(a, b);
    return head;
}

void FrontBackSplit(struct node *source, struct node *frontref, struct node *backref) {
    struct node *fast, *slow;
    slow = source;
    fast = source->next;
    while (fast != NULL) {
        fast = fast->next;
        if (fast != NULL) {
            slow = slow->next;
            fast = fast->next;
        }
    }
    frontref = source;
    backref = slow->next;
    slow->next = NULL;
}

struct node *SortedMerge(struct node *a, struct node *b) {
    struct node *result;
    result = NULL;
    if (a == NULL) {
        return (b);
    }
    else if (b == NULL) {
        return (a);
    }

    if (a->data <= b->data) {
        result = a;
        result->next = SortedMerge(a->next, b);
    } else {
        result = b;
        result->next = SortedMerge(a, b->next);
    }
    return result;
}

int main() {
    struct node *head = NULL;
    int i, n, num;
    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        scanf("%d", &num);
        head = Create(head, num);
    }
    head = MergeSort(head);
    display(head);
}

Answer 1

代码有几个问题，我不能说是哪一个触发了您看到的错误，但我会在下面指出其中的几个。取Create():

struct node *Create(struct node *head, int num)
{
    struct node *newnode, *temp;
    newnode=(struct node *)malloc(sizeof(struct node));
    newnode->data=num;
    newnode->next=NULL;
    if(head==NULL) {
      head=newnode;
      temp=newnode;
    } else {
      temp->next=newnode;
      temp=temp->next;
    }
    temp->next=NULL; 
    return head;
}

老实说，我不知道它到底应该做什么。也许向列表中添加一个新节点，由头 link 表示？它不会那样做。您创建一个新节点

   newnode=(struct node *)malloc(sizeof(struct node));

我建议你写成

   newnode = malloc(sizeof *newnode);

你不需要转换void *，所以你不需要转换malloc()的结果，使用sizeof *newnode而不是sizeof(struct node)是更安全。但是代码以您所拥有的形式正常工作，因此那里没有问题。但是，该节点发生的情况取决于 head。如果 head 为 NULL，则将其指向新节点，并通过 temp 将新节点的 next（重新）分配给 NULL。因此，现在您将 return 更新后的 head 由作为单个元素列表的新节点组成。这符合我对函数应该做什么的猜测。

但是，如果 head 不是 NULL，您将新节点放入 temp->next，这是一个问题，因为 temp 未初始化。您在 if(head==NULL) 分支中写入 temp，但在 else 分支中取消引用它，它可以指向任何地方。如果您不时在这里遇到分段错误，我会感到很惊讶。不过，没有必要将新节点分配给 temp->next，因为之后您立即将 temp 更改为指向 temp->next，也就是您刚刚放置 newnode 的位置，所以 temp = newnode 可以解决问题，没有段错误。但如果我们这样做，并非一切都好。我们现在将在 temp 中拥有新节点（使用 next 指针，再次重新分配给 NULL）然后我们 return head。如果我们选择 else 分支，我们就不会在任何地方连接 head 和 newnode。因此，使用非 NULL 头调用 Create() 创建一个新节点，将其丢弃（并泄漏内存），这就是全部。

所以虽然我的猜测是 Create() 应该在列表中添加一个新的，由 head 表示，或者类似的东西，但 实际上 做的是如果第一个参数是 NULL 就创建一个单元素列表，如果 head != NULL.

则什么也不做就泄漏 sizeof(struct node) 内存

话虽这么说，当然，代码可能完全靠运气。当我尝试使用 clang 进行零优化时，我以某种方式设法正确地构建了一个列表。不过，这是幸运的。一般是行不通的。我怀疑发生的事情是在 main() 的循环中重复调用 Create() 恰好将您创建的最后一个节点（并写入 temp）留在与在下一次调用中未初始化 temp。因此，纯属幸运，将新节点放入 temp 的 next 会将新节点附加到您创建的最后一个节点。解决这个问题真的很有趣 :) 但是当然不要依赖于此。这是几种幸运情况的结合。添加优化标志，编译器将更改堆栈布局，代码将中断。在对 Create() 的连续调用之间调用其他函数，堆栈将发生变化，然后堆栈中的最后一个 link 不再存在。并且代码会被破坏。如果这有效的话，这是一个非常不稳定的情况。

如果你只是想添加一个新节点到列表中，做一个前置函数。像

struct node *prepend(int val, struct node *list)
{
  struct node *n = malloc(sizeof *n);
  if (n) {
    n->data = val;
    n->next = list;
  }
  return n;
}

（我还没有测试过，所以可能会有语法错误，但它会是这样的......你需要弄清楚如果 malloc() 失败了该怎么办，但你可以abort()如果你不想处理它）。

display()没有什么问题，只是我不明白为什么其他函数是驼峰式的而它是小写的。您不需要 temp，您可以在 while 循环中使用 head，但这是一种样式选择。该功能按预期工作。

然而，对于MergeSort()，我们还有另一个问题。我很惊讶你的编译器没有在这里对你发出警告。它确实应该给你一个错误，带有正确的标志，但至少是一个错误。当您测试列表是空的还是单例时，您 return，但 不是节点 。该函数应该 return 和 struct node *，所以只使用 return 不会给你任何有用的东西。

  if((head==NULL) || (head->next)==NULL){
    return;
  }

如果递归的基本情况return是垃圾，显然整个递归都会失败。否则，假设 FrontBackSplit() 和 SortedMerge() 有效，函数看起来没问题。您不需要额外的 headref 变量，它只是 head 的同义词，但拥有它也没有错。编译器会帮你去掉它。也不需要将合并列表分配给 head 然后 return head。你可以 return SortedMerge(a,b)。但同样，一旦您打开优化，您的编译器就会为您处理。除了基本情况外，我认为该功能应该有效。

在 FrontBackSplit() 中，我的印象是您想将 frontref 和 backref 值返回给调用者。否则，该函数不执行任何操作。但是当你修改函数参数时，你并没有改变调用者范围内的变量。您需要通过引用传递这两个指针，这意味着您需要使用指向指针的指针。把它改成这样：

void FrontBackSplit(struct node *source,
                    struct node **frontref,
                    struct node **backref)
{
  struct node *fast, *slow;
  slow=source;
  fast=source->next;
  while(fast!=NULL) {
    fast=fast->next;
    if(fast!=NULL) {
        slow=slow->next;
        fast=fast->next;
    }
  }
  *frontref=source;
  *backref=slow->next;
  slow->next=NULL;
}

当你调用函数时，第二个和第三个参数使用参数的地址，所以使用FrontBackSplit(headref,&a,&b);而不是FrontBackSplit(headref,a,b);。

据我所知，SortedMerge() 应该可以工作（修改后的 FrontBackSplit()）。它是递归的，但不是尾递归的，因此您可能会遇到长列表溢出堆栈的问题。不过，迭代并不难。

您应该 main() int main(void) 或 int main(int, char**)。你应该 return 0 才算成功。

我的猜测是三件事中的一件正在破坏您的代码。当您 Create() 您的列表时，您得不到想要的列表。然而，在正确的情况下，使用正确的编译器和函数调用配置，您可能会很幸运（也许这就是您所看到的）。在那种情况下，它可能是 MergeSort() 中的 return。 Return head 相反，这可能就是您想要的。如果您有一个空列表或一个长度为 1 的列表，您应该 return 该列表。所以把return;改成return head;。如果不是那样，那可能是因为你递归了 MergeSort() 中的随机数据，因为 a 和 b 没有在递归中初始化。当您调用 FrontBackSplit() 并且调用不会更改它们时，它们未初始化，因为它们是按值而不是引用传递的。我上面列出的更改将解决这个问题。

我可能忽略了更多，但至少这三个问题足以破坏代码，每个问题都是独立的，因此它是开始调试的好地方。

在 C 中对链表进行归并排序

Merge Sort On Linked List in C

c

sorting

mergesort

linked-list

data-structures