Как инициализировать указатель на указатель на ошибку сегментации NULL 11

Question

Я пытаюсь реализовать дерево ударов Ван Эмде, но я получаю Сегментацию 11, когда я вызываю свои функции вставки более двух раз. Когда я попытался напечатать значения в моей функции вставки, я понял, что проблема заключается в том, что я инициализирую свои кластеры в NULL. Я не понимаю, почему это будет так, когда я использую цикл for. Я также пытался использовать calloc, но он дал мне ту же ошибку. Мой код выглядит так:

class vEB
{
    int u;
    int *m;
    int *M;
    vEB *summary;
    vEB **cluster;
public:
    vEB(int);
    bool member(int);
    void insert(int);
    void Delete(int);
    int min();
    int max();
    int* pred(int);
    int* succ(int);
};

vEB::vEB(int u){
    this -> u = u;
    this -> m = NULL;
    this -> M = NULL;

    if (u == 2){
        this -> summary = NULL;
        this -> cluster = NULL;
    } else {
        int subSize = (int)sqrt(u);
        this -> summary = new vEB(subSize);
        this -> cluster = new vEB*[subSize];
        for (int i=0;i<=subSize;i++){
            cluster[i]=NULL;
        }

    }
}

bool vEB::member(int x){
    if (u == 2){
        if (m == NULL){
            return false;
        } 
        if (x == 0){
            return ((*m) == 0);
        } else if (x == 1){
            return ((*M) == 1);
        } 
        return false;
    }else{
        if (m == NULL) {
            return false;
        }
        if (x < (*m) || x > (*M)){
            return false;
        }else if (x == (*m) || (x == (*M))){
            return true;
        }else{
            int subSize = (int)sqrt(u);
            int hi = x / subSize;
            int lo = x % subSize;
            if (cluster[hi] == NULL){
                return false;
            } else{
                return cluster[hi] -> member(lo);
            } 
        }

    }
}

void vEB::insert(int x) {
    if (u == 2) {
        if (x == 0) {
            if (m == NULL){
                m = new int;
                M = new int;
                (*m) = (*M) = x;
            } else {
                (*m) = x;
            }
        } else if (x == 1) {
            if (M == NULL){
                m = new int;
                M = new int;
                (*m) = (*M) = x;
            } else{
                (*M) = x;
            } 
        }
    } else {
        if (m == NULL) {
            m = new int;
            M = new int;
            (*m) = (*M) = x;
        } else {
            if (x < (*m)) {
                int currMin = (*m);
                (*m) = x;
                this -> insert(currMin);
            }else {
                int subSize = (int)sqrt(u);
                int hi = x / subSize;
                printf("%d - %d\n",x, hi);
                int lo = x % subSize;
                printf("%d - %d\n",x, hi);
                if (cluster[hi] == NULL){
                    cluster[hi] = new vEB(subSize);
                    cluster[hi] -> insert(lo);
                    summary -> insert(hi);
                }else {
                    cluster[hi] -> insert(lo);
                }
                if (x > (*M)){
                    (*M) = x;
                } 
            }
        }
    }
}

void vEB::Delete(int x){
    if (u == 2) {
        if (x == 0) {
            if ((*M) == 0){
                m = M = NULL;
            } else{
                (*m) = 1;
            } 
        } else if (x == 1) {
            if ((*m) == 1) {
                m = M = NULL;
            }
            else {
                (*M) = 0;
            }
        }
    }else{
        int subSize = (int)sqrt(u);
        int hi = x / subSize;
        int lo = x % subSize;

        if (x == (*m)){
            if (x == (*M)){
                m = M = NULL;
            } else {
                int nextMinHi = summary -> min();
                int nextMinLo = cluster[summary -> min()] -> min();
                int nextMin = nextMinHi * subSize + nextMinLo;
                this -> Delete(nextMin);
                (*m) = nextMin;
            }
        } else {
            cluster[hi] -> Delete(lo);
            if (cluster[hi] -> m == NULL){
                summary -> Delete(hi);
                delete cluster[hi];
                cluster[hi] = NULL;
            }
            if (x == (*M)){
                if (summary -> m == NULL) {
                    (*M) = (*m);
                } else{
                    int nextMaxHi = summary -> max();
                    int nextMaxLo = cluster[summary -> max()] -> max();
                    (*M) = nextMaxHi * subSize + nextMaxLo;
                }
            }
        }
    }
}

int vEB::min() {
    return (*m);
}

int vEB::max() {
    return (*M);
}

int* vEB::pred(int x){
    if (u == 2){
        if (x == 0) {
            return NULL;
        } else if (x == 1){
            if (m == NULL){
                return NULL;
            } 
            if ((*m) == 1){
                return NULL;
            } 
            return m;
        }
        else {
            return NULL;
        }
    } else {
        if (m == NULL) {
            return NULL;
        }
        if (x <= (*m)) {
            return NULL;
        }
        if (x > (*M)) {
            return M;
        }
        int subSize = (int)sqrt(u);
        int hi = x / subSize;
        int lo = x % subSize;
        if (cluster[hi] == NULL){
            int* prev = summary -> pred(hi);
            int* ret = new int;
            (*ret) = (*prev) * subSize + cluster[(*prev)] -> max();
            return ret;
        } else {
            int *newLo, *newHi;
            newHi = new int;
            newLo = new int;
            (*newHi) = hi;
            int minInCluster = cluster[hi] -> min();
            if (lo > minInCluster){
                 newLo = cluster[hi] -> pred(lo);
            }else {
                newHi = summary -> pred(hi);
                (*newLo) = cluster[(*newHi)] -> max();
            }
            int *ret = new int;
            (*ret) = (*newHi) * subSize + (*newLo);
            return ret;
        }
    }
}

int* vEB::succ(int x) {
    if (u == 2) {
        if (x == 1) {
            return NULL;
        }else if (x == 0) {
            if (M == NULL) {
                return NULL;
            }
            if ((*M) == 0) {
                return NULL;
            }
            return M;
        }else {
            return NULL;
        }
    }else{
        if (m == NULL) {
            return NULL;
        }
        if (x >= (*M)) {
            return NULL;
        }
        if (x < (*m)) {
            return m;
        }
        int subSize = (int)sqrt(u);
        int hi = x / subSize;
        int lo = x % subSize;
        if (cluster[hi] == NULL) {
            int* next = summary -> succ(hi);
            int* ret = new int;
            (*ret) = (*next) * subSize + cluster[(*next)] -> min();
            return ret;
        } else {
            int *newLo, *newHi;
            newHi = new int;
            newLo = new int;
            (*newHi) = hi;
            int maxInCluster = cluster[hi] -> max();
            if (lo < maxInCluster){
                newLo = cluster[hi] -> succ(lo);
            }else {
                newHi = summary -> succ(hi);
                (*newLo) = cluster[(*newHi)] -> min();
            }
            int *ret = new int;
            (*ret) = (*newHi) * subSize + (*newLo);
            return ret;
        }
    }
}

int main(){

    vEB *vEB = new class vEB(8);
    vEB -> insert(1);
    vEB -> insert(2);
    vEB -> insert(5);
    vEB -> insert(6);
    vEB -> insert(7);
    printf("%d\n", (*vEB -> pred(2)));
    printf("%d\n", (*vEB -> succ(2)));

    vEB -> Delete(2);

    return 0;
}

Есть ли правильный способ инициализации указателей на указатель, о котором я не знаю? Любые предложения будут высоко ценится. Спасибо.

Answer 1

Мой вывод такой же, как у Бруно.Вот живой тест вашего кода .Вы можете исправить это и протестировать снова.

=========== Начало # 0 сообщения времени выполнения stensal ===========

Ошибка времени выполнения: [out-of-bounds write]
Продолжение выполнения может привести к неопределенному поведению, прервать!

-
- Writing 4 bytes to 0x8aaa078 will corrupt the adjacent data.
- 
- The memory-space-to-be-written (start:0x8aaa070, size:8 bytes) is allocated at
-     file:/src/new.cpp::54, 17
- 
-  0x8aaa070               0x8aaa077
-  +------------------------------+
-  |the memory-space-to-be-written|......
-  +------------------------------+
-                                  ^~~~~~~~~~
-        the write starts at 0x8aaa078 that is right after the memory end.
- 
- Stack trace (most recent call first) of the write.
- [1]  file:/prog.cc::35, 13
- [2]  file:/prog.cc::290, 10

- [3]  [libc-start-main]
-

============ Конечное # 0 сообщение времени выполнения stensal ============

Answer 2

Несмотря на то, что ошибка «off-by-one» плохая, у вас есть еще худшая ошибка: возможна бесконечная рекурсия.

В вашем конструкторе VEC есть проверка на u == 2, но что произойдет, если u, например, 3? Затем вы перейдете к делу else и получите квадратный корень из 3, который будет усечен до целого числа 1. Затем вы делаете new VEC(1), который вызывает конструктор со значением 1 (который не равен 2), идете в ветку else и получаете квадратный корень из 1, который равен 1 , Затем вы делаете new VEC(1) (снова!) И так далее и так далее.

Вам нужно проверить, если u <= 2, чтобы избежать этого.

Answer 3

Это не решение вашей проблемы, но я надеюсь, что это поможет.С некоторой отладкой я обнаружил, что ваша проблема в том, что вы вызываете insert (5).Код, который создает segfault:

                if (cluster[hi] == NULL) {
                cluster[hi] = new vEB(subSize);
                cluster[hi]->insert(lo);
                summary->insert(hi);
            }
            else {
                cluster[hi]->insert(lo);  //here something is wrong with cluster[hi]
            }

Я не мог найти ответ, но если вы поместите свой код в IDE и отладите его, у вас больше шансов решить проблему, потому что выпонимаю твой код лучше меня.

Answer 4

In vEB::vEB(int u)

for (int i=0;i<=subSize;i++){
       cluster[i]=NULL;
   }

должно быть

for (int i=0;i<subSize;i++){
       cluster[i]=NULL;
   }

, потому что this -> cluster = new vEB*[subSize]; вместо this -> cluster = new vEB*[subSize+1];

Я получаю ошибку сегментации 11, когда я вызываю функции вставки более двух раз.

Когда вы делаете vEB -> insert(5);, значение hi равнослишком высоко и cluster[hi] выходит за пределы кластера .