我的代码中的分段错误 C++ 中的 SLL 自然合并排序

Question

这是我的 C++ 代码 SLL 自然归并排序：

#include <stdio.h>
#include <stdlib.h>
typedef struct Node{
    int data;
    Node* link;
}NODE;
typedef struct List{
    NODE* first;
    NODE* last;
}LIST;
void Init(LIST &l){
    l.first = l.last = NULL;
}
NODE* GetNode(int x){
    NODE* p;
    p = (NODE*)malloc(sizeof(NODE));
    if (p==NULL){
        printf("Khong du bo nho!"); return NULL;
    }
    p->data = x;
    p->link = NULL;
    return p;
}

void AddLast(LIST &l, NODE* new_ele){
    if (l.first==NULL){
        l.first = new_ele;
        l.last = l.first;
    }
    else {
        l.last->link = new_ele;
        l.last = new_ele;
    }
}
NODE* InsertLast(LIST &l, int x){
    NODE* new_ele = GetNode(x);    
    if (new_ele == NULL){
        return NULL;
    }
    AddLast(l,new_ele);
    return new_ele;
}
void AddNumber(LIST &l, int a[], int n){
    NODE *p;
    for (int i=0; i<n; i++){
        InsertLast(l,a[i]);
    }
}
void ShowNumber(LIST l){
    NODE* p = l.first;
    printf("Day so: ");
    while (p!=NULL){
        printf("%d ",p->data);
        p = p->link;
    }
    printf("\n");
}
void DistributeList(LIST &l, LIST &l1, LIST &l2){
    NODE *p;
    do{
        p = l.first;
        l.first = p->link; p->link = NULL;

        AddLast(l1,p);
    }while((l.first)&&(p->data<=l.first->data));
    if (l.first)
        DistributeList(l,l2,l1);
    else
        l.last = NULL;
}
void MergeList(LIST &l, LIST &l1, LIST &l2){
    NODE* p;
    while ((l1.first)&&(l2.first)){
        if (l1.first->data<=l2.first->data){
            p = l1.first;
            l1.first = p->link;
        }
        else{
            p = l2.first;
            l2.first = p->link;
        }
        p->link = NULL;
        AddLast(l,p);
    };
    if (l1.first){
        l.last->link = l1.first;
        l.last = l1.last;
    }
    else if (l2.first){
        l.last->link = l2.first;
        l.last = l2.last;
    }
}
void NaturalMergeSort(LIST &l){
    LIST l1, l2;
    if (l.first == l.last) return;
    Init(l1);
    Init(l2);
    DistributeList(l,l1,l2);
    NaturalMergeSort(l1);
    NaturalMergeSort(l2);
    MergeList(l,l1,l2);    
}
int main(){
    LIST l;
    Init(l);
    int a[] = {12,2,8,5,1,6,4,15};
    int n = sizeof(a)/sizeof(a[0]);
    AddNumber(l,a,n);
    ShowNumber(l);
    NaturalMergeSort(l);
    ShowNumber(l);
}

当我运行它时，代码就在这一行报告错误 此处细分 当我调试时代码仍然正常运行，但是当我进入

NaturalMergeSort

函数时，在

DistributeList

函数中，我在

AddLast(l1,p)

行遇到了分段错误。 这就是我尝试运行时在终端中得到的结果： 我的终端 我尝试修复它，但多次出现此错误，请帮我修复它。

Answer 1

此实施存在问题。 DistributeList 是递归的，这可能会导致短期运行的大型数组上的堆栈溢出。这可以通过迭代（在 L1 和 L2 之间交替）来解决。我还遇到了创建循环的数据模式（小循环子列表），当我用已知的工作代码替换合并函数时，这似乎得到了修复。

问题代码不是自然的合并排序。自然的合并排序是自下而上的，进行一次扫描以查找已经排序的子列表，然后将它们合并。问题代码不必要地一遍又一遍地重复扫描相同的值。例如，如果数组为 {14,15,12,13,10,11,8,9,6,7,4,5,2,3,0,1}，则 L1 最终为 {14,15, 10,11,6,7,2,3}，重复扫描，使 L1 最终得到 {14,15,6,7}，然后再次得到 {14,15}。 L1 也进行同样的过程，最终得到 {12,13}，然后才开始第一次合并。

以下是自底向上自然合并排序的示例。一个小数组用于保存指向已排序子列表的第一个节点的指针。 aPnode[i] 指向具有 2^i 个已排序子列表的列表，否则为 NULL。这是旧代码，但它可以工作。

NODE * Merge(NODE *pNode0, NODE *pNode1)
{
NODE *pMrg;
NODE **ppMrg = &pMrg;
    if(pNode0 == NULL)                  /* if either list empty, */
        return pNode1;                  /*  return the other */
    if(pNode1 == NULL)
        return pNode0;
    while(1){                           /* merge the lists */
        if(pNode0->data <= pNode1->data){
            *ppMrg = pNode0;
            ppMrg = &(pNode0->next);
            pNode0 = *ppMrg;
            if(pNode0 == NULL){
                *ppMrg = pNode1;
                break;}}
        else{
            *ppMrg = pNode1;
            ppMrg = &(pNode1->next);
            pNode1 = *ppMrg;
            if(pNode1 == NULL){
                *ppMrg = pNode0;
                break;}}}
    return pMrg;
}

/* size of internal array */
#define ASZ 32
NODE *MergeSort(NODE * pNode)
{
NODE *apNode[ASZ] = {NULL};             /* array of lists */
NODE *pNext;
NODE *pLast;
size_t i;
    if(pNode == NULL || pNode->next == NULL)
        return pNode;
    /* merge nodes into array */
    while(pNode){
        /* set pLast to end of already sorted sub-list */
        pLast = pNode;
        while((pNext = pLast->next) != NULL && pNext->data >= pLast->data)
            pLast = pNext;
        pLast->next = NULL;
        /* merge sorted sub-list into array */
        for(i = 0; i < ASZ && apNode[i] != NULL; i++){
            pNode = Merge(apNode[i], pNode);
            apNode[i] = NULL;}
        if(i == ASZ)                    /* don't go past end array */
            i--;
        apNode[i] = pNode;
        pNode = pNext;}
    /* merge array into a single list */
    pNode = NULL;
    for(i = 0; i < ASZ; i++)
        pNode = Merge(apNode[i], pNode);
    return pNode;
}