我得到SIGABRT错误在我的C++递归代码

anhgbhbe  于 2023-02-26  发布在  其他
关注(0)|答案(2)|浏览(203)

我正在运行此代码,并收到此错误

Fatal glibc error: malloc.c:2593 (sysmalloc): assertion failed: (old_top == initial_top (av) && old_size == 0) || ((unsigned long) (old_size) >= MINSIZE && prev_inuse (old_top) && ((unsigned long) old_end & (pagesize - 1)) == 0)
Aborted (core dumped)

当我使用gdb运行它时,它是这样的:

Fatal glibc error: malloc.c:2593 (sysmalloc): assertion failed: (old_top == initial_top (av) && old_size == 0) || ((unsigned long) (old_size) >= MINSIZE && prev_inuse (old_top) && ((unsigned long) old_end & (pagesize - 1)) == 0)

Program received signal SIGABRT, Aborted.
__pthread_kill_implementation (threadid=<optimized out>, signo=signo@entry=6, no_tid=no_tid@entry=0) at pthread_kill.c:44
44            return INTERNAL_SYSCALL_ERROR_P (ret) ? INTERNAL_SYSCALL_ERRNO (ret) : 0;

我不知道为什么。请帮帮我。
代码:

#include <bits/stdc++.h>
using namespace std;

bool cancolor(vector<vector<int>> &mat, int m, vector<int> colors, int idx)
{
    if (idx == mat.size())
    {
        return true;
    }
    else
    {
        int color = 1;
        while (color <= m)
        {
            int edges = 0;
            int i = 0;
            while (i < mat.size())
            {
                if (mat[idx][i] == 1)
                {
                    edges++;
                    if (colors[i] != color)
                    {
                        colors[idx] = color;
                        if (cancolor(mat, m, colors, idx + 1))
                        {
                            return true;
                        }
                        colors[idx] = 0;
                    }
                    else
                    {
                        i = mat.size();
                    }
                }
                i++;
            }
            if (edges == 0)
            {
                colors[idx] = color;
                if (cancolor(mat, m, colors, idx + 1))
                {
                    return true;
                }
                return false;
            }
            color++;
        }
        return false;
    }
}

string graphColoring(vector<vector<int>> &mat, int m)
{
    vector<int> colors;
    for (int i = 0; i <= m; i++)
    {
        colors.push_back(0);
    }
    if (cancolor(mat, m, colors, 0))
    {
        return "YES";
    }
    return "NO";
}

int main()
{
    vector<vector<int>> mat = {{0, 0, 0, 1, 0, 0, 0},
                               {0, 0, 1, 0, 1, 0, 0},
                               {0, 1, 0, 0, 1, 0, 1},
                               {1, 0, 0, 0, 0, 0, 0},
                               {0, 1, 1, 0, 0, 0, 0},
                               {0, 0, 0, 0, 0, 0, 0},
                               {0, 0, 1, 0, 0, 0, 0}};
    cout << graphColoring(mat, 5) << endl;
    return 0;
}

如果你想知道我想达到什么目的,这里有链接:https://www.codingninjas.com/codestudio/problems/981273
我试着用pythontutor运行它,但它在174步左右后结束了,在第5个节点后。

xlpyo6sf

xlpyo6sf1#

问题出在graphColoring;m是颜色的数量,但是colors矢量应该包含mat.size()元素。
在这个向量之外写入(如您所做的)具有未定义的行为,并且可能导致某种类型的内存崩溃。

w8biq8rn

w8biq8rn2#

while (color <= m) {
  // ...
   while (i < mat.size()) {
     // ...
     if (cancolor(mat, m, colors, idx + 1))

你所得到的是一个指数级的爆炸,对于每个idx,你会快速地调用cancolor()很多次,对于每个调用,又会进行很多次递归调用,如此类推。
您通常会遇到堆栈溢出,但是您对动态分配内存的使用(可能来自std::vector<int> colors)使我认为空闲存储区首先爆炸。
你应该重新考虑你的算法如果这是不可能,尝试和线性化,以减少您的内存需求。
另外,using namsepace std#include <bits/stdc++.h>被认为是有害的。我让你搜索一下。

相关问题