C #中链表的合并排序

Question

合并排序通常是对链表排序的首选方式。链表缓慢的随机访问性能使得一些其他算法(如quicksort)表现不佳，而另一些算法(如heapsort)则完全不可能。我一直在努力在链表上做归并排序。它不断返回一个错误。我正在提供我试图执行的代码。请一定要帮我。它不断给出运行时错误。

#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

代码有几个问题，我不能说是哪一个触发了您看到的错误，但我将在下面指出其中的一些。采取创建（）：

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

老实说，我不知道它应该做什么。也许可以在列表中添加一个新节点，用头部链接表示？它不会那样做。创建新节点

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

我建议你写成

   newnode = malloc(sizeof *newnode);

您不需要强制转换空*，因此您不需要强制转换malloc（）的结果，并且使用sizeof*new节点而不是sizeof（结构节点）更安全。但是代码以您拥有的形式正常工作，因此没有问题。但是，该节点发生的情况取决于head。如果head为NULL，则将其指向新节点，并通过temp将新节点的Next分配给NULL。所以现在您将返回一个更新的head，它由新节点作为单个元素列表组成。这符合我对函数应该做什么的猜测。

但是，如果head不是NULL，则将新节点放在tem-

因此，虽然我的猜测是创建（）应该添加一个新的列表，由head表示，或者类似的东西，但它实际上是创建一个单元素列表，如果第一个参数是NULL，并泄漏sizeof（结构节点）内存，而如果head！=NULL则什么也不做。

也就是说，代码当然可能完全靠运气工作。当我用zero optimisation的< code>clang进行尝试时，我设法正确地构建了一个列表。不过，这是运气。一般是行不通的。我怀疑发生的情况是，在< code>main()的循环中重复调用< code>Create(),恰好将您创建的最后一个节点(并写入< code>temp)留在下一次调用中未初始化的< code>temp所在的堆栈位置。因此，纯属运气，将新节点放在< code>temp的< code>next中会将新节点附加到您创建的最后一个节点上。解决这个问题真的很有趣:)但是当然不要依赖这个。这是几种幸运情况的结合。添加优化标志，编译器会改变堆栈布局，代码会中断。在连续调用< code>Create()之间调用其他函数，堆栈将会改变，然后您不再拥有堆栈上的最后一个链接。密码就会被破解。如果这真的有效的话，那将会是一个非常不稳定的局面。

如果您只想将新节点添加到列表中，请使用prepend函数。有点像

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

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

< code>display()没有任何问题，只是我不明白为什么它是小写的，而其他函数都是大写的。不需要< code>temp，可以在< code > while -循环中使用< code>head，但那是一种风格选择。该功能按预期工作。

然而，使用MergeSort（），我们还有另一个问题。我很惊讶你的编译器没有在这里对你发出警告。它应该真的给你一个错误，带有正确的标志，但至少是一个错误。当你测试列表是否为空或单例时，你返回，但不是用节点。该函数应该返回一个结构节点*，所以仅仅使用返回不会给你任何有用的东西。

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

如果递归的基本情况返回垃圾，显然整个递归会翻滚。否则，假设ForetBackSplit（）和sortedMerge（）工作，该函数看起来没问题。您不需要额外的head ref变量，它只是head的同义词，但拥有它并没有错。编译器会为您摆脱它。没有任何必要将合并列表分配给head，然后返回head。您可以只返回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（hearef，

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

你应该让main（）成为int main（void）或int main（int， char**）。应返回 0 表示成功。

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

我可能忽略了更多，但至少这三个问题足以破坏代码，每个问题都有自己的问题，所以这是一个从调试开始的好地方。