仅使用一个函数的链表上的合并排序函数

Question

我的编码相当糟糕，我需要编写函数： struct listnode * mergesort(struct listnode *data) 在 C 或 C++ 中，但测试代码在 C 中。

main() 包含测试功能的测试代码。这是教授给的

我可以编译它，但是当我运行它时，它给了我

prepared list, now starting sort

Process returned -1073741571 (0xC00000FD) execution time: 1.034 s

它不会超过那个点，所以我的功能肯定有问题，但我不确定它是什么。

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


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


//This is the function I need to write:
struct listnode * mergesort(struct listnode *data)
{  
    if (data == NULL)
        return NULL;
    ///////Find the location of mid

    struct listnode *pRunToEnd = data;
    struct listnode *pRunToMid = data;
    struct listnode *pPreMid = NULL;
    while (pRunToEnd != NULL)
    {
        pRunToEnd = pRunToEnd->next;
        while (pRunToEnd!=NULL){
            pRunToEnd = pRunToEnd->next;
            if (pRunToEnd!=NULL){
                pRunToEnd = pRunToEnd->next;
        pPreMid = pRunToMid;
        pRunToMid = pRunToMid->next; }
        }
    }
    //////////Cut the list into 2 half
    if (pPreMid != NULL)
        pPreMid->next = NULL;
    /////Recursion
    mergesort(data);
    mergesort(pRunToMid);

    //////////Combine 2 half
    struct listnode *pFirst = data;
    struct listnode *pPreFirst = NULL;
    pPreMid = NULL;
    while (pFirst != NULL && pRunToMid!= NULL)
    {
        if(pFirst->value > pRunToMid->value)
        {
            pPreFirst = pFirst;
            pFirst = pFirst->next;
        }
        else
        {
            /////Chain the element of first list
            pPreFirst->next = pRunToMid;
            pPreMid = pRunToMid;
            pRunToMid = pRunToMid->next;
            pPreMid->next = NULL;
        }
    }

    ///////////////Chain the rest of second list
    if (pFirst == NULL)
    {
        pPreFirst->next = pRunToMid;
    }

    //////if pRunToMid is NULL, we do nothing because we have merged all elements in second list into first
    return(pPreFirst);


}


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;

至

    if (!data || !data->next)   // zero or one element list: already sorted
        return data;

查找mid位置的循环出错；将其更改为

    while (pRunToEnd)
    {
        if (pRunToEnd = pRunToEnd->next)
            pRunToEnd = pRunToEnd->next;
        pPreMid = pRunToMid;
        pRunToMid = pRunToMid->next;
    }

正如 rpattiso 所写，你应该使用 mergesort(data) 和 mergesort(pRunToMid) 的 return 值作为排序列表的新头，所以改变
```
    mergesort(data);
    mergesort(pRunToMid);
```
至
```
    data = mergesort(data);
    pRunToMid = mergesort(pRunToMid);
```

关系运算符倒退-改

        if(pFirst->value > pRunToMid->value)

至

        if (pFirst->value < pRunToMid->value)

在合并循环的else块中，你想将第二个列表的元素插入到第一个列表中，你忘记处理第二个元素的情况列表是要插入到第一个的头部（即成为列表的新头部），以及更新前面的元素指针pPreFirst，而你没有正确设置指针->next 链接到第一个列表。将块更改为

        {
            if (!pPreFirst) // no preceding element
                data = pRunToMid;   // new list head
            else
                pPreFirst->next = pRunToMid;    /////Chain the element of first list
            pPreFirst = pRunToMid;  // update pointer to preceding element
            pRunToMid = pRunToMid->next;
            pPreFirst->next = pFirst;   // chain to first list
        }

您 return 排序列表的尾部而不是其头部。变化
```
    return(pPreFirst);
```
至
```
    return data;
```

仅使用一个函数的链表上的合并排序函数

Mergesort function on linked-list using only one function

c

mergesort

linked-list