时间戳

首页 > 解决方案 > 由于 C++ 程序末尾的 malloc 导致的 Seg Fault

c++ - 由于 C++ 程序末尾的 malloc 导致的 Seg Fault

问题描述

该程序使用段树来查找给定范围查询的总和。它对输入的输入给出正确的答案。但是，在执行完 main 函数的所有行后，程序结束时会显示分段错误。链接到输出屏幕的图像。

在 GDB 中执行 run 的错误信息是：

程序收到信号 SIGSEGV，分段错误。0x00007ffff71f0532 in __GI___libc_free (mem=0x617c60) at malloc.c:2967 2967 malloc.c: 没有这样的文件或目录。

在使用 GDB 进行回溯时，问题似乎起源于声明向量 nums 的 main 函数开头的那一行。但我看不出我的代码有什么问题。涉及段树的代码似乎很好。我也尝试过使用 Valgrind，但什么都不懂。

代码（在 C++ 中）是：

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

class NumArray
{
    public:
    int* st;
    vector<int> nums;
    NumArray(vector<int> num)
    {
        st = new int[num.size()];
        if(num.size() != 0)
        {
            st = constructST(num);
        }
        nums = num;
    }

    int* constructST(vector<int> nums)
    {
        int height = ceil(log(nums.size())/log(2));
        int stSize = 2*(int)pow(2,height)-1;
        constructSTUtil(nums,0,nums.size()-1,st,0);
        return st;
    }

    int constructSTUtil(vector<int> nums,int ss, int se, int* st,int si)
    {
        if(ss == se)
        {
            st[si] = nums[ss];
            return st[si];
        }
        int mid = ss + (se-ss)/2;
        st[si] = constructSTUtil(nums,ss,mid,st,2*si+1) + constructSTUtil(nums,mid+1,se,st,2*si+2);
        return st[si];
    }

    void update(int i, int val)
    {
        int diff = val - nums[i];
        nums[i] = val;
        int n = nums.size();
        updateUtil(st,0,n-1,i,diff,0);
    }

    void updateUtil(int* st,int ss,int se,int i,int diff,int si)
    {
        if(i < ss || i > se)
        {
            return;
        }
        st[si] = st[si] + diff;
        if(se != ss)
        {
            int mid = ss + (se-ss)/2;
            updateUtil(st,ss,mid,i,diff,2*si+1);
            updateUtil(st,mid+1,se,i,diff,2*si+2);
        }
    }

    int sumRange(int i, int j)
    {
        int n = nums.size();
        if(i < 0 || i > j || j > n)
        {
            cout << "Invalid input";
            return -32768;
        }
        return sumRangeUtil(st,0,n-1,i,j,0);
    }

    int sumRangeUtil(int* st,int ss, int se, int qs, int qe, int si)
    {
        if(qs <= ss && qe >= se)
        {
            return st[si];
        }
        if(qs > se || qe < ss)
        {
            return 0;
        }
        int mid = ss + (se-ss)/2;
        return sumRangeUtil(st,ss,mid,qs,qe,2*si+1) + sumRangeUtil(st,mid+1,se,qs,qe,2*si+2);
    }
};

int main()
{
    vector<int> nums;
    nums.push_back(0);
    nums.push_back(9);
    nums.push_back(5);
    nums.push_back(7);
    nums.push_back(3);
    NumArray obj(nums);
    cout << obj.sumRange(4,4) << "\n";
    cout << obj.sumRange(2,4) << "\n";
    cout << obj.sumRange(3,3) << "\n";
    obj.update(4,5);
    obj.update(1,7);
    obj.update(0,8);
    cout << obj.sumRange(1,2) << "\n";
    obj.update(1,9);
    cout << obj.sumRange(4,4) << "\n";
    cout << obj.sumRange(3,4) << "\n";
    return 0;
}

标签： c++segmentation-faultgdbmallocsegment-tree

解决方案

看看这个功能

int constructSTUtil(vector<int> nums,int ss, int se, int* st,int si)
{
    if(ss == se)
    {
        st[si] = nums[ss];
        return st[si];
    }
    int mid = ss + (se-ss)/2;
    st[si] = constructSTUtil(nums,ss,mid,st,2*si+1) + constructSTUtil(nums,mid+1,se,st,2*si+2);
    return st[si];
}

递归地调用它。

现在cout在函数的开头添加这个，比如：

int constructSTUtil(vector<int> nums,int ss, int se, int* st,int si)
{
    cout << "ss = " << ss << " se = " << se << " si = " << si << endl;

当nums有 5 个元素时，这将为您提供：

ss = 0 se = 4 si = 0
ss = 0 se = 2 si = 1
ss = 0 se = 1 si = 3
ss = 0 se = 0 si = 7
              ^^^^^^
              ups... out of range for `st`

所以当你这样做时：

st[si] = nums[ss];

你写的越界。换句话说，你的算法有问题。

顺便提一句：

int stSize = 2*(int)pow(2,height)-1;
     ^^^^^
     Never used in the code

st此外，您有一个成员和函数参数似乎相当令人困惑st。而且，您分配给使用来自（即）st的返回值也令人困惑。constructsSTst

推荐阅读