C ++ удаление первого элемента в массиве указателей воздействует на последующие элементы - PullRequest
Новая
       31

C ++ удаление первого элемента в массиве указателей воздействует на последующие элементы

2 голосов
/ 17 мая 2019

Для лабораторного задания я работаю над реализацией массива кучи. У меня есть массив типа PrintJob *. Проблема, с которой я сталкиваюсь, заключается в том, что первый элемент arr[0], который я пытаюсь удалить с помощью delete, странным образом изменяет второй элемент массива. В конце концов этот элемент попадает в начало кучи, и удаление его вызывает SIGABRT.

Я изначально думал, что, возможно, удалив его из массива напрямую, delete arr[0] выдавал какой-то тип ошибки, так как я неоднократно вызывал delete arr[0]; несмотря на то, что я обновляю arr[0] следующим его лучшим потомком сразу после его удаления. Итак, я попытался сохранить его во временной переменной, а затем удалить: 

void dequeue() {
    PrintJob *temp = arr[0];
////    delete arr[0];
    trickleUp(0);
    delete temp;
}

Но вскоре я понял, что мои усилия не имеют никакого смысла. Я знаю, что SIGABRT происходит, когда программа пытается удалить динамически размещенную сущность дважды, но я никогда не касаюсь каких-либо других элементов, кроме первого. Поэтому я не понимаю, почему второй элемент заполняется ненужными значениями, а затем выдает SIGABRT.

Вот другой код, который я использую:

Эта функция вызывается вышеуказанной функцией и управляет процессом смещения наибольшего потомка текущего индекса (n) в его положение. Он делает это рекурсивно согласно требованию. 

void trickleUp(int n) {

    int c = getChild(n, true);  // get the greater child

    if (c >= MAX_HEAP_SIZE) {   // if the
        PrintJob *temp = arr[n];
////        delete arr[n];
        arr[n] = nullptr;
        delete temp;
        return;
    }

    arr[n] = arr[c];    // update the old node
    trickleUp(c); // move to the next element in the tree;
}

getChild () - это функция, вызываемая предыдущей функцией, предназначенная для возврата наибольшего дочернего индекса (ln: левый узел, rn: правый узел) текущего индекса n. 

int getChild(int n, bool g) {

    int ln = (2 * n) + 1, rn = (2 * n) + 2, lp = -1, rp = -1;

    if (ln < MAX_HEAP_SIZE && arr[ln]) {
        lp = arr[ln]->getPriority();
    }

    if (rn < MAX_HEAP_SIZE && arr[rn]) {
        rp = arr[rn]->getPriority();
    }

    return  ( !((lp > rp) ^ g) ? ln:rn );
}

Я проверял код несколько раз, и я не видел никаких других логических ошибок, конечно, я не смогу точно сказать, пока эта проблема не будет решена, и я не смогу протестировать с дополнительными примерами , Вот ссылка на весь остальной код, если вы хотите скомпилировать его самостоятельно. Я тоже приложил make-файл. https://drive.google.com/drive/folders/18idHtRO0Kuh_AftJgWj3K-4OGhbw4H7T?usp=sharing

1 Ответ

0 голосов
/ 17 мая 2019

Обработка вашего кода несколькими отпечатками приводит к следующему выводу: 

set 0
set 1
set 2
set 3
set 4
swap 1, 4
swap 0, 1
copy 1 to 0
copy 4 to 1
delete 4
copy 2 to 0
copy 6 to 2
delete 6
copy 2 to 0
copy 6 to 2
delete 6
copy 2 to 0
copy 6 to 2
delete 6
copy 2 to 0
copy 6 to 2
delete 6

Числа являются индексами в arr.Если мы добавим некоторые имена к этим объектам, станет ясно, что происходит не так: 

set 0 - A
set 1 - B
set 2 - C
set 3 - D
set 4 - E
swap 1, 4 - 1 == E, 4 == B
swap 0, 1 - 0 == E, 1 == A
copy 1 to 0 0 == A, 1 == A, pointer to E is lost
copy 4 to 1 1 == B, 4 == B
delete 4    delete B, 4 == 0, 1 still points to B
copy 2 to 0 0 == C, 2 == C, pointer to A is lost
copy 6 to 2 2 == 0
delete 6    delete null pointer, has no effect
copy 2 to 0 0 == 0, 2 == 0, pointer to C is lost
copy 6 to 2 2 == 0
delete 6    delete null pointer, has no effect
the rest just further copies around null pointers

В данном конкретном примере это не приводит к сбою (по крайней мере, для меня), поскольку ничего не удаляется дважды, но, надеюсь, его очиститькак это может случиться с разными данными.

Предположительно: 

    arr[n] = arr[c];    // update the old node

должно быть: 

    arr[c] = arr[n];    // update the old node

Это затем делает ваш код сбой еще быстрее, хотя, вероятно, естьможно найти дополнительные логические проблемы.

...