C++单链表自然归并排序代码出现Segmentation fault，求助修复

问题描述 #

运行以下单链表自然归并排序的C++代码时，在NaturalMergeSort调用的DistributeList函数中，AddLast(l1,p)行触发Segmentation fault，错误反复出现。

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

错误原因分析 #

1. 无限递归导致栈溢出：
   当处理一个已经有序的子链表（如2->8）时，NaturalMergeSort仅判断链表是否只有一个节点，未检查链表是否整体有序。此时会反复调用DistributeList将整个有序链表拆入新的子链表，再递归处理该子链表，形成无限递归，最终栈溢出触发Segmentation fault。

2. MergeList中的空指针访问：
   当其中一个子链表为空时，MergeList的while循环不会执行，目标链表l仍为空（l.last为NULL），此时直接访问l.last->link会触发空指针解引用错误。

修复方案 #

1. 添加有序链表判断 #

新增辅助函数IsSorted判断链表是否有序，在NaturalMergeSort中若链表已有序则直接返回，避免不必要的递归。

2. 修复MergeList的空指针问题 #

在合并剩余子链表时，先判断目标链表l是否为空，为空则直接赋值，否则再追加节点。

修改后的完整代码 #

#include <stdio.h>
#include <stdlib.h>
typedef struct Node{
    int data;
    struct Node* link; // 修正：C++中结构体内部引用自身需用struct Node
}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");
}

// 新增：判断链表是否有序
bool IsSorted(LIST &l) {
    if (l.first == NULL || l.first == l.last) return true;
    NODE* p = l.first;
    while (p->link != NULL) {
        if (p->data > p->link->data) {
            return false;
        }
        p = p->link;
    }
    return true;
}

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){
        if (l.first == NULL) {
            l.first = l1.first;
            l.last = l1.last;
        } else {
            l.last->link = l1.first;
            l.last = l1.last;
        }
        // 清空l1，避免野指针
        l1.first = l1.last = NULL;
    }
    else if (l2.first){
        if (l.first == NULL) {
            l.first = l2.first;
            l.last = l2.last;
        } else {
            l.last->link = l2.first;
            l.last = l2.last;
        }
        l2.first = l2.last = NULL;
    }
}

void NaturalMergeSort(LIST &l){
    LIST l1, l2;
    // 新增判断：链表只有一个节点或已有序则直接返回
    if (l.first == l.last || IsSorted(l)) 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);
    return 0;
}

额外说明 #

• 修正了Node结构体内部的指针声明：C++中结构体内部引用自身类型时，需使用struct Node* link而非Node* link（或可提前typedef）。
• 在MergeList中清空已合并的子链表指针，避免野指针问题。

内容的提问来源于stack exchange，提问作者Huy Trần Ngọc