zhangas

Pay more attention

0%

关于STL在DFS使用中产生的爆栈问题

Posted on Edited on

在PTA 上 L2-026 小字辈这样一道题中 因为STL 的不当使用，出现了段错误的问题，在仔细与李同学讨论后，发现了如下原因。题目链接

问题一 创建新队列实现清空

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
queue<int> Q;
    void Go(int nodeIndex, int depth)
{
    if (depth > maxDepth)
    {
        maxDepth = depth;
        queue<int> Q2;
        Q = Q2; // 创建一个新的队列来实现清空操作

        Q.push(T[nodeIndex].data);
    }
    else if (depth == maxDepth)
    {
        Q.push(T[nodeIndex].data);
    }
    for (int i = 0; i < T[nodeIndex].childList.size(); i++)
    {
        Go(T[nodeIndex].childList[i], depth + 1);
    }
}

这种清空操作出现了问题，在于当前层的go( ) 函数只有return 后才会释放掉内存，但是一直往深度访问的时候，每一层开辟的新的queue的空间并没有被释放掉，因此造成了内存的堆积，产生爆栈。

问题二 借助deque自带的clear()函数来实现清空

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
deque<int> Q;
    void Go(int nodeIndex, int depth)
{
    if (depth > maxDepth)
    {
        maxDepth = depth;

        Q.clear(); // 会清空元素并不会释放掉内存

        Q.push_back(T[nodeIndex].data);
    }
    else if (depth == maxDepth)
    {
        Q.push_back(T[nodeIndex].data);
    }
    for (int i = 0; i < T[nodeIndex].childList.size(); i++)
    {
        Go(T[nodeIndex].childList[i], depth + 1);
    }
}

自带的clear() 函数会清空元素并不会释放掉内存
而pop_back() 函数会将元素和内存一起释放掉

可以借助以下两个函数来验证

1
2
3
deque<int> Q;
Q.size(); // 元素的个数 相当于length 属性
Q.capacity(); // 最大容量（开辟的空间） 相当于queue_size 属性

以下有两种解决的方法

1. 手写清空函数

1
2
3
4
5
6
7
    void Queue_Clear()
{
    while(!Q.empty()){
        Q.pop();
    }
}

2. 在全局变量中多声明一个Queue 来进行辅助清空

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
queue<int> Q;
queue<int> Q2;
    void Go(int nodeIndex, int depth)
{
    if (depth > maxDepth)
    {
        maxDepth = depth;

        Q = Q2; // 通过赋值来清空队列

        Q.push(T[nodeIndex].data);
    }
    else if (depth == maxDepth)
    {
        Q.push(T[nodeIndex].data);
    }
    for (int i = 0; i < T[nodeIndex].childList.size(); i++)
    {
        Go(T[nodeIndex].childList[i], depth + 1);
    }
}

这样不会产生内存堆积的现象，解决问题。