仅使用一个函数分段错误对链表进行合并排序

Question

我需要实现的功能：struct listnode * mergesort(struct listnode *data) 我的教授提供了 main() 函数测试代码。我只需要提交 mergesort 功能。他告诉我们用 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;

你应该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。

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

Answer 2

使用指向指针的指针合并两个已排序列表的示例函数。由于您只允许一个函数，因此您必须将此逻辑合并到您的 mergesort() 函数中。如果这是家庭作业，那么您似乎得到了太多帮助，但我不确定如何解释此示例中显示的想法。

NODE * MergeLists(NODE *pSrc1, NODE *pSrc2)
{
NODE *pDst = NULL;                      /* destination head ptr */
NODE **ppDst = &pDst;                   /* ptr to head or prev->next */
    while(1){
        if(pSrc1 == NULL){
            *ppDst = pSrc2;
            break;
        }
        if(pSrc2 == NULL){
            *ppDst = pSrc1;
            break;
        }
        if(pSrc2->data < pSrc1->data){  /* if src2 < src1 */
            *ppDst = pSrc2;
            pSrc2 = *(ppDst = &(pSrc2->next));
            continue;
        } else {                        /* src1 <= src2 */
            *ppDst = pSrc1;
            pSrc1 = *(ppDst = &(pSrc1->next));
            continue;
        }
    }
    return pDst;
}

仅使用一个函数分段错误对链表进行合并排序

Mergesort on a linked-list using only one function, segmentation fault

c

sorting

linked-list

mergesort