c - 对大量数据使用合并排序时如何防止堆栈溢出？

Question

当我测试 100、1000 或 10000 个长链接列表时，我有以下合并排序算法。但是，当使用 100000 或 1000000 长链表时，它会在包含 Node->Next=Merge(Front,Back->Next,Type); 的行上返回段错误。这让我相信这是堆栈溢出而不是段错误。根据错误发生时的 gdb，堆栈非常满。我无法找到一种方法来准确检查调用堆栈中有多少项以给出确切的数字。非常感谢任何有关重新处理合并排序以处理大量数据的帮助。

struct IntList
{
int Value;
int Frequency;
struct IntList* Next;
struct IntList* Prev;
};//Struct for Integer Linked List
void SortList(struct IntList** Values,enum SortBy Type)
{
    struct IntList* Head = *Values;
    if(Head==NULL||Head->Next==NULL)
    {
        return;
    }//If Base Case
    struct IntList* Front;
    struct IntList* Back;
    Split(Head,&Front,&Back);//Splits Linked List
    SortList(&Front,Type);
    SortList(&Back,Type);//Recursively Sorts
    *Values=Merge(Front,Back,Type);//Merges Halves
    return;
}

void Split(struct IntList* Head,struct IntList** Front,struct IntList** Back)
{
    struct IntList* Fast;
    struct IntList* Slow;
    if (Head==NULL||Head->Next==NULL)
    {
        *Front=Head;
        *Back=NULL;
    }//If Length <2
    else
    {
        Slow=Head;
        Fast=Head->Next;
    }
    while(Fast!=NULL)
    {
        Fast=Fast->Next;
        if(Fast!=NULL)
        {
            Fast=Fast->Next;
            Slow=Slow->Next;
        }
    }//Find Midpoint
    *Front=Head;
    *Back=Slow->Next;
    Slow->Next=NULL;//Breaks Link
    return;
}


struct IntList* Merge(struct IntList* Front,struct IntList* Back,enum SortBy Type)
{
    if(Front==NULL)
    {
        return Back;
    }
    if (Back==NULL)
    {
        return Front;
    }//Base Cases

    struct IntList* Node;
    if(Type==DATA)
    {
        if(Front->Value <= Back->Value)
        {
           Node=Front;
           Node->Next=Merge(Front->Next,Back,Type);
        }
        else
        {
            Node=Back;
            Node->Next=Merge(Front,Back->Next,Type);
        }//Takes Greatest Value for Sorted List
    }//If Sorting by Data
    if(Type==FREQUENCY)
    {
        if(Front->Frequency < Back->Frequency)
        {
           Node=Front;
           Node->Next=Merge(Front->Next,Back,Type);
        }
        else
        {
            Node=Back;
            Node->Next=Merge(Front,Back->Next,Type);
        }//Takes Greatest Frequency for Sorted List
    }//If Sorting by Frequency
    return(Node);

Answer 1

如果要使用递归，最好尝试用尾调用的形式来表达(这样递归调用返回后除了返回什么都不做)。这样，大多数编译器会将尾调用优化为简单的跳转，而不使用任何堆栈空间。对于你的 Merge 功能，它变成了这样的:

void Merge(struct IntList **merged, struct IntList* Front,struct IntList* Back,enum SortBy Type)
{
    if(Front==NULL) {
        *merged = Back;
    } else if (Back==NULL) {
        *merged = Front;
    } else if(Type==DATA) {
        if(Front->Value <= Back->Value) {
            *merged = Front;
            Merge(&Front->Next, Front->Next, Back, Type);
        } else {
            *merged = Back;
            Merge(&Back->Next, Front, Back->Next,Type);
        }//Takes Greatest Value for Sorted List if Sorting by Value
    } else if(Type==FREQUENCY) {
        if(Front->Frequency < Back->Frequency) {
            *merged = Front;
            Merge(&Front->next, Front->Next, Back, Type);
        } else {
            *merged = Back;
            Merge(&Back->Next, Front, Back->Next, Type);
        }//Takes Greatest Frequency for Sorted List
    }//If Sorting by Frequency
}

如果你的编译器不支持尾递归优化，你可以通过将函数体做成一个循环来自己做:

void Merge(struct IntList **merged, struct IntList* Front,struct IntList* Back,enum SortBy Type)
{
  while(Front || Back) {
    if(Front==NULL) {
        *merged = Back;
        Back = NULL;
    } else if (Back==NULL) {
        *merged = Front;
        Front = NULL
    } else if(Type==DATA) {
        if(Front->Value <= Back->Value) {
            *merged = Front;
            merged = &Front->Next;
            Front = Front->Next;
        } else {
            *merged = Back;
            merged = &Back->Next;
            Back = Back->Next;
        }//Takes Greatest Value for Sorted List if Sorting by Value
    } else if(Type==FREQUENCY) {
        if(Front->Frequency < Back->Frequency) {
            *merged = Front;
            merged = &Front->Next;
            Front = Front->Next;
        } else {
            *merged = Back;
            merged = &Back->Next;
            Back = Back->Next;
        }//Takes Greatest Frequency for Sorted List
    }//If Sorting by Frequency
  }
}