c - 仅使用一个函数(段错误)对链表进行归并排序

Question

我需要实现以下功能:struct listnode * mergesort(struct listnode *data)我的教授提供了 main() 函数测试代码。我只需要提交归并排序函数。他告诉我们用 C 或 C++ 来做，但他给我们的测试代码 main() 是用 C 写的。

这是我现在的代码:我可以编译它，但是当我运行它时，它崩溃了。我检查了调试器，它给了我段错误。我也不确定这个函数是否正确，因为我无法通过 main() 中的测试点。

<小时/>

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

struct listnode { struct listnode * next;
                         long              value; } ;


struct listnode * mergesort(struct listnode *data)
{   int temp, finished = 0;
    struct listnode *tail, *head, *ahead, *bhead, *atail, *btail;
    if ( data == NULL )
        return;
    //Split
    ahead = atail = head = data;       // first item
    btail = head->next;         // second item
    while(btail->next != NULL)  // anything left
    {
    atail = atail->next;
    btail = btail->next;
    if( btail->next != NULL)
        btail = btail->next;
    }
    bhead = atail->next;        // disconnect the parts
    atail->next = NULL;

    //sort
    mergesort(ahead);
    mergesort(bhead);

    //merge
    if(ahead->value <= bhead->value)  // set the head of resulting list
        head = tail = ahead, ahead = ahead->next;
    else
        head = tail = bhead, bhead = bhead->next;

    while(ahead && bhead)
        if(ahead->value <= bhead->value)  // append the next item
            tail = tail->next = ahead, ahead = ahead->next;
        else
            tail = tail->next = bhead, bhead = bhead->next;

    if(ahead != NULL)
        tail->next = ahead;
    else
        tail->next = bhead;
    return(head);
}


int main(void)
{
   long i;
   struct listnode *node, *tmpnode, *space;
   space =  (struct listnode *) malloc( 500000*sizeof(struct listnode));
   for( i=0; i< 500000; i++ )
   {  (space + i)->value = 2*((17*i)%500000);
      (space + i)->next = space + (i+1);
   }
   (space+499999)->next = NULL;
   node = space;
   printf("\n prepared list, now starting sort\n");
   node = mergesort(node);
   printf("\n checking sorted list\n");
   for( i=0; i < 500000; i++)
   {  if( node == NULL )
      {  printf("List ended early\n"); exit(0);
      }
      if( node->value != 2*i )
      {  printf("Node contains wrong value\n"); exit(0);
      }
      node = node->next;
   }
   printf("Sort successful\n");
   exit(0);
}

<小时/>

Answer 1

if ( data == NULL )
    return;

您应该返回 NULL。

<小时/>

btail = head->next;         // second item
while(btail->next != NULL)  // anything left
{

如果 btail 设置为 head->next。如果 head->next 为 NULL，则您正在尝试检查循环 NULL->next != NULL，这不是一个东西。

<小时/>

if( btail->next != NULL)
    btail = btail->next;
}

在检查 ->next 之前，您需要检查 btail 是否为 NULL。就在上面，您正在设置 btail = btail->next;因此可以将其设置为 NULL。

上面的循环也有同样的问题，你需要在执行 next 之前检查 null。

<小时/>

下面的代码可能有问题，但是上面的代码需要更多的错误检查。