Ошибка Seg из-за malloc в конце программы C ++ - PullRequest
Новая
       59

Ошибка Seg из-за malloc в конце программы C ++

0 голосов
/ 03 июня 2018

Программа использует деревья сегментов, чтобы найти сумму заданного диапазона запроса.Это дает правильные ответы на введенные данные.Однако в конце программы после выполнения всех строк из главной функции отображается ошибка сегментации. Ссылка на изображение экрана вывода.

Сообщение об ошибке при выполнении прогона в GDB:

Программный полученный сигнал SIGSEGV, Ошибка сегментации.0x00007ffff71f0532 в __GI___libc_free (mem = 0x617c60) на malloc.c: 2967 2967 malloc.c: нет такого файла или каталога.

При возврате с помощью GDB проблема, похоже, возникает в начале строкиосновной функции, объявляющей векторные числа.Но я не вижу, что не так с моим кодом.Код, включающий деревья сегментов, кажется хорошим.Я тоже пытался использовать 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;
}

1 Ответ

0 голосов
/ 03 июня 2018

Посмотрите на эту функцию 

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, используя возвращаемое значение из constructsST (то есть st).

...