C-使用合并对大量数据进行合并时，我如何防止堆栈溢出

Question

i具有以下合并排序算法，该算法在我测试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
  }
}

Answer 2

这个最简单的答案不是使用递归。

但是，如果您使用递归暂停，则可以通过将函数中使用的温度变量移动到函数范围外或声明它们静态的情况下限制堆栈中的内容对于他们来说，每次合并都被称为（如果您在多线程应用程序中很有趣，可能会产生不利影响）。看起来您没有任何变量可以安全地使用。

您还可以用另一个结构将参数封装，因此您不必将三个指针传递到新的堆栈呼叫上，即，一个参数占用的空间少于3。

。

类似：

struct IntList* Merge(struct mergeData* data)

也有调整堆栈尺寸的方法，以便您的应用程序可以处理您期望的数据集。

总的来说，这是递归的限制。如果您处理资源有限的嵌入式系统（像我自己一样），则通常避免使用它。