Тема: Видалення елементу.

Вибиває помилку

"Вызвано исключение: нарушение доступа для чтения. lefttree было 0xDDDDDDDD."

Не розумію в чому проблема. Якщо хтось знає допоможіть будь ласка.
В коді написав де саме помилка.

void deleteleaf(leaf** root) {
    cout << "Введіть індекс листя, яке ви хочите видалити: ";
    int num;
    cin >> num;
    leaf* deleteroot = (*root);
    leaf* oldroot = (*root);
    leaf* lefttree= (*root)->left;
    leaf* righttree = (*root)->right;
    leaf* find = (*root)->left;
    if ((*root)->index == num) {
        if ((*root)->left == nullptr && (*root)->right == nullptr) {
            delete (*root);
            
        }
        if ((*root)->right != nullptr && (*root)->left == nullptr) {
            (*root) = righttree;
            delete oldroot;
        }
        if ((*root)->left != nullptr && (*root)->right== nullptr) {
            (*root) = lefttree;
            delete oldroot;
        }
        if ((*root)->right != nullptr && (*root)->left != nullptr) {
            if (find->right == nullptr) {
                oldroot = find;
                oldroot->right = righttree;
                delete deleteroot;
            }
            else {
                if (find->right != nullptr) {
                    while (find->right != nullptr) {
                        find = find->right;
                    }
                    if (find->left == nullptr) {   ----> тут вибиває помилку  Вызвано исключение: нарушение доступа
для чтения.
lefttree было 0xDDDDDDDD.
                        oldroot->index = find->index;
                        delete find;
                        if (lefttree->right) {
                            while (lefttree->right) {
                                lefttree = lefttree->right;
                            }
                            lefttree->right = nullptr;
                        }
                    
                    }
                    else {
                        if (find->left != nullptr) {
                            leaf* save = find->left;
                            oldroot->index = find->index;
                
                            delete find;
                            while (lefttree->right) {
                                lefttree = lefttree->right;
                            }
                            lefttree->right = save;
                        }
                    }
                }
            }
        }
    }
    if ((*root)->index != num) {
        leaf* begin = nullptr;
        while (oldroot) {
            begin = oldroot;
            if (oldroot->index > num && oldroot->left !=nullptr) {
                oldroot = oldroot->left;
                if (oldroot->index == num) {
                    break;
                }
            }
            else {
                cout << "Індексу " << num << " не знайдено у дереві." << endl;
                return;
            }
            if (oldroot->index < num && oldroot->right != nullptr) {
                oldroot = oldroot->right;
                if (oldroot->index == num) {
                    break;
                }
            }
            else {
                cout << "Індексу " << num << " не знайдено у дереві." << endl;
                return;
            }
        }
        if (oldroot->left == nullptr) {
            begin->right = oldroot->right;
            delete oldroot;
        }
        else {
            if (oldroot->left != nullptr) {
                leaf* seveoldrootright = oldroot->right;
                leaf* clean = oldroot;
                oldroot = oldroot->left;
                if (oldroot->right == nullptr) {
                    begin->right = oldroot;
                    begin->right->right = seveoldrootright;
                    delete clean;
                }
                else {
                    if (oldroot->right != nullptr) {
                        while (oldroot->right != nullptr) {
                            oldroot = oldroot->right;
                        }
                        leaf* clean = oldroot;
                        if (clean->left == nullptr) {
                            begin->right->index = oldroot->index;
                            delete clean;
                        }
                        else {
                            if (clean->left != nullptr) {
                                leaf* savecleanleft = clean->left;
                                delete clean;
                                leaf* search = righttree->left;
                                while (search->right) {
                                    search = search->right;
                                }
                                search->right = savecleanleft;
                            }
                        }
                    }
                }
            }
        }
    }
}

2

Re: Видалення елементу.

Вибиває помилку  "Вызвано исключение: нарушение доступа для чтения. lefttree было 0xDDDDDDDD." Не розумію в чому проблема.

Проблема в мові - пєєєєєєрвоє, піііііво, ісключєєєєєєніє. Фубля якась, а не мова.

3

Re: Видалення елементу.

Принаймні, питання містить код та інформацію про помилку (чого багато хто не робить) — пропонуєте інформацію про помилку не писати? (Чому російська локалізація студії, а не українська — важко сказати, але встановлення іншої локалізації пропрієтарного ПЗ, ймовірно, грошей коштує). Ще б можна було код обрамити тегом code... Ви помуштрувати аби помуштрувати?

4

Re: Видалення елементу.

Помилка не тут. Помилка ввиділені пам'яті під дерево.

Re: Видалення елементу.

Vo_Vik написав:

Помилка не тут. Помилка ввиділені пам'яті під дерево.

Можна я Вам скину цілий код? Бо я не можу зрозуміти що не так...

Re: Видалення елементу.

Arete написав:

Вибиває помилку  "Вызвано исключение: нарушение доступа для чтения. lefttree было 0xDDDDDDDD." Не розумію в чому проблема.

Проблема в мові - пєєєєєєрвоє, піііііво, ісключєєєєєєніє. Фубля якась, а не мова.

У Вас дуже багато часу? Не маєте що робити? Зараз б докопатися до помилки в коді на російській мові... Якщо Ви не розумієте помилку, нічого страшного, я вам перекладу. Напишіть в ПП.

7 Востаннє редагувалося koala (31.10.2020 10:38:01)

Re: Видалення елементу.

Ну, оскільки додали тег code...

void deleteleaf(leaf** root) { //де перевірка, що root не nullptr? припустимо, це гарантується, але хоча б ASSERT додали
...
        leaf* find = (*root)->left; //find вказує на ліве піддерево початкового root
...
        delete (*root);//delete не змінює операнд на nullptr, root усе ще можна використовувати, але на що він тепер вказує - хз
        if ((*root)->left == nullptr && (*root)->right == nullptr) { //ці чотири гілки, мабуть, малося на увазі зробити 
        if ((*root)->right != nullptr && (*root)->left == nullptr) { //взаємовиключними, але зараз вони можуть усі спрацювати
        if ((*root)->left != nullptr && (*root)->right== nullptr) { //послідовно. На що тепер вказує root - взагалі невідомо
        if ((*root)->right != nullptr && (*root)->left != nullptr) {
            if (find->right == nullptr) { //у цьому місці на що саме вказує find - біс його зна, root міг бути видалений кілька разів
                    if (find->left == nullptr) { //а тут тим більше

Дуже наполегливо раджу розбити операцію на кілька примітивних функцій, які будуть виконувати базові операції ("знайти лист", "додати лист", "видалити лист", "пересадити лист" і т.д.) і працювати з вказівниками виключно в тих функціях, а в цій функції оперувати лише базовими функціями, а не вказівниками. Незначна втрата швидкості багаторазово покриється виграшем від надійності.

Re: Видалення елементу.

koala написав:

Ну, оскільки додали тег code...

void deleteleaf(leaf** root) { //де перевірка, що root не nullptr? припустимо, це гарантується, але хоча б ASSERT додали
...
        leaf* find = (*root)->left; //find вказує на ліве піддерево початкового root
...
        delete (*root);//delete не змінює операнд на nullptr, root усе ще можна використовувати, але на що він тепер вказує - хз
        if ((*root)->left == nullptr && (*root)->right == nullptr) { //ці чотири гілки, мабуть, малося на увазі зробити 
        if ((*root)->right != nullptr && (*root)->left == nullptr) { //взаємовиключними, але зараз вони можуть усі спрацювати
        if ((*root)->left != nullptr && (*root)->right== nullptr) { //послідовно. На що тепер вказує root - взагалі невідомо
        if ((*root)->right != nullptr && (*root)->left != nullptr) {
            if (find->right == nullptr) { //у цьому місці на що саме вказує find - біс його зна, root міг бути видалений кілька разів
                    if (find->left == nullptr) { //а тут тим більше

Дуже наполегливо раджу розбити операцію на кілька примітивних функцій, які будуть виконувати базові операції ("знайти лист", "додати лист", "видалити лист", "пересадити лист" і т.д.) і працювати з вказівниками виключно в тих функціях, а в цій функції оперувати лише базовими функціями, а не вказівниками. Незначна втрата швидкості багаторазово покриється виграшем від надійності.

Попробую. Дякую.

9

Re: Видалення елементу.

Принаймні, питання містить код та інформацію про помилку (чого багато хто не робить) — пропонуєте інформацію про помилку не писати? (Чому російська локалізація студії, а не українська — важко сказати, але встановлення іншої локалізації пропрієтарного ПЗ, ймовірно, грошей коштує). Ще б можна було код обрамити тегом code... Ви помуштрувати аби помуштрувати?

Так, мабуть трохи перегнув палку, приношу вибачення.


if (find->left == nullptr) {   ----> тут вибиває помилку

Скоріше за все помилка в тому що find == nullptr, а з nullptr брати left, як і будь що інше, так собі ідея.

10

Re: Видалення елементу.

Arete написав:

Принаймні, питання містить код та інформацію про помилку (чого багато хто не робить) — пропонуєте інформацію про помилку не писати? (Чому російська локалізація студії, а не українська — важко сказати, але встановлення іншої локалізації пропрієтарного ПЗ, ймовірно, грошей коштує). Ще б можна було код обрамити тегом code... Ви помуштрувати аби помуштрувати?

Так, мабуть трохи перегнув палку, приношу вибачення.


if (find->left == nullptr) {   ----> тут вибиває помилку

Скоріше за все помилка в тому що find == nullptr, а з nullptr брати left, як і будь що інше, так собі ідея.

Я теж так спочатку подумав, але 2 рядки вище він бере від нього райт і нічого. Там де в конструкторі проблема коли при створені об'єкту райт створили, а лефт ні.

Подякували: Arete1

11

Re: Видалення елементу.

Vo_Vik написав:
Arete написав:

Принаймні, питання містить код та інформацію про помилку (чого багато хто не робить) — пропонуєте інформацію про помилку не писати? (Чому російська локалізація студії, а не українська — важко сказати, але встановлення іншої локалізації пропрієтарного ПЗ, ймовірно, грошей коштує). Ще б можна було код обрамити тегом code... Ви помуштрувати аби помуштрувати?

Так, мабуть трохи перегнув палку, приношу вибачення.


if (find->left == nullptr) {   ----> тут вибиває помилку

Скоріше за все помилка в тому що find == nullptr, а з nullptr брати left, як і будь що інше, так собі ідея.

Я теж так спочатку подумав, але 2 рядки вище він бере від нього райт і нічого. Там де в конструкторі проблема коли при створені об'єкту райт створили, а лефт ні.

Дійсно, судячи по циклу while на 2 рядки вище find повинен бути не nullptr. А те що лефт не створили не проблема, умова if якраз і перевіряє його наявніть.
_________________
UPD. Пан koala як завжди більш уважний і правий - find може вказувати на лівий вузел рута, якого вже нема, а це UB.

12

Re: Видалення елементу.

Швидше за все, місце вказане не зовсім точно (це буває при оптимізації), а проблема може бути не лише в тій функції, а й в структурі, що її передано в функцію (лається на lefttree, але leaf* lefttree= (*root)->left, і я не бачу, як могло lefttree стати 0xDDDDDDDD).
У будь-якому разі проблема в тому, що код заскладний для імперативного, треба хоча б процедурний писати.

13

Re: Видалення елементу.

Arete написав:

UPD. Пан koala як завжди більш уважний і правий - find може вказувати на лівий вузел рута, якого вже нема, а це UB.

Насправді саме це, хоча й UB, але не має призводити до падіння - new в коді немає, отже, всі delete, швидше за все, лишають дані на місці. Але, звісно, так робити не можна.

Re: Видалення елементу.

А що залишається на місці вказівника пілся delete?

15

Re: Видалення елементу.

Вказівник

Подякували: leofun011

Re: Видалення елементу.

З якимось адресом? Чи там буде 00000000?

17

Re: Видалення елементу.

int *a = new int; //десь було виділено кілька байтів під int, їхня адреса записана в a
*a = 50; //записуємо туди якесь число
delete a; //ті байти позначені як вільні; можливо, їх віддали системі, можливо, їх візьме якийсь інший new, але найімовірніше - вони найближчим часом лишатимуться як були
cout << *a; //це UB: a продовжує вказувати за адресою, де нічого не виділено, але найімовірніше, тут буде виведено 50

delete не змінює вказівник, він позначає, що байти, на які вказує той вказівник, є вільними для подальшого використання. Хто саме ними скористається - невідомо, тому брати значення за таким вказівником не варто.

Була поширена практика одразу після delete прирівнювати вказівник NULL:

delete a;
a = NULL; //щоб не забути

але з розвитком "розумних" вказівників std::shared_ptr та std::unique_ptr частіше використовуються саме вони.

Re: Видалення елементу.

#include <iostream>
#include <conio.h>
using namespace std;
struct leaf {
    int index;
    struct leaf* left;
    struct leaf* right;
};
void addroot(leaf** root) {
    if ((*root) == nullptr) {
        (*root) = new leaf;
        cout << "Корінь дерева відсутній." << endl;
        cout << "Введіть індекс кореня дерева: " << endl;
        int num;
        cin >> num;
        (*root)->index = num;
        (*root)->left = nullptr;
        (*root)->right = nullptr;

    }
}

void tree(leaf** root, int i) {
    leaf* add = (*root);
    int num;
    cout << "Введіть індекс " << i << " листя дерева: ";
    cin >> num;
    while (add) {
        if (add->index < num && add->right != nullptr) {
            add = add->right;
        }
        else {
            if (add->index < num && add->right == nullptr) {

                break;
            }
            else {
                if (add->index > num && add->left != nullptr) {
                    add = add->left;
                }
                else {
                    if (add->index > num && add->left == nullptr) {
                        add = add;
                        break;
                    }
                }

            }
        }

    }
    if (add->index > num) {
        leaf* New;
        add->left = new leaf;
        New = add->left;
        New->index = num;
        New->left = nullptr;
        New->right = nullptr;

    }
    else {
        if (add->index < num) {
            leaf* New = new leaf;
            add->right = new leaf;
            New = add->right;
            New->index = num;
            New->left = nullptr;
            New->right = nullptr;

        }

    }
}
void deleteleaf(leaf** root) {
    leaf* first = (*root);
    cout << "Введіть індекс елементу: ";
    int num;
    cin >> num;
    leaf* beginsearch = *root;
    leaf* search = *root;
    while (search) {


        if (search->index > num && search->left != nullptr) {
            beginsearch = search;
            search = search->left;
            if (search->index == num) {

                break;
            }
        }
        else {
            if (search->index < num && search->right != nullptr) {
                beginsearch = search;
                search = search->right;
                if (search->index == num) {

                    break;
                }
            }
        }
    }
    while (beginsearch) {


        if (beginsearch->index > num && beginsearch->left != nullptr) {
            if (beginsearch->left->index == num) {
                break;
            }
            else {
                beginsearch = beginsearch->left;
            }

        }
        else {
            if (beginsearch->index < num && beginsearch->right != nullptr) {
                if (beginsearch->right->index == num) {
                    break;
                }
                else {
                    beginsearch = beginsearch->right;
                }

            }
        }

    }
    
    if (beginsearch->index < search->index) {
        leaf* saverightsearch = search->right;
        leaf* saveleftsearch = search->left;
        leaf* find = search;
        if (search->left == nullptr) {
            beginsearch->right = saverightsearch;

        }
        else {
            if (search->right == nullptr) {
                beginsearch->right = saveleftsearch;

            }
        }

        if (search->left != nullptr) {
            search = search->left;
            if (search->right == nullptr) {
                find->index = search->index;

                beginsearch->right = search;

            }
            else {
                if (search->right != nullptr) {
                    while (search->right != nullptr) {
                        search = search->right;
                    }
                    if (search->left == nullptr) {
                        find->index = search->index;
                        beginsearch->right = find;
                        search = nullptr;

                    }
                    else {
                        if (search->left != nullptr) {
                            leaf* saveleft = search->left;
                            find->index = search->index;
                            beginsearch->right = find;

                            search->index = saveleft->index;
                            search->right = saveleft->right;
                            search->left = saveleft->left;
                        }
                    }
                }
            }
        }
    }
    else {
        if (beginsearch->index > search->index) {
            leaf* saverightsearch = search->right;
            leaf* saveleftsearch = search->left;
            leaf* find = search;
            if (search->left == nullptr) {
                beginsearch->left = saverightsearch;
            }
            else {
                if (search->right == nullptr) {
                    beginsearch->left = saveleftsearch;
                }
            }
                    if (search->right != nullptr) {
                        while (search->right != nullptr) {
                            search = search->right;
                        }
                        if (search->left == nullptr) {
                            find->index = search->index;
                            beginsearch->left = find;
                            search = nullptr;

                        }
                        else {
                            if (search->left != nullptr) {
                                leaf* saveleft = search->left;
                                find->index = search->index;
                                beginsearch->left = find;

                                search->index = saveleft->index;
                                search->right =saveleft->right;
                                search->left = saveleft->left;
                            }
                        }
                    }
        }
    }
    if (first->index == num) {
        if (first->left == nullptr) {
            first = first->right;
        }
        else {
            if (first->right == nullptr) {
                first = first->left;
            }
        }
        if (first->left != nullptr && first->right != nullptr) {
            leaf* newroot = first->left;
            leaf* savenewrootleft = newroot->left;
            leaf* savelefttree = first->left;
            leaf* saverighttree = first->right;
            if (newroot->right == nullptr) {
                first->index = newroot->index;
                first->left = savenewrootleft;
            }
            else { 
                if (newroot->right != nullptr) {
                    while (newroot->right != nullptr) {
                        newroot = newroot->right;
                    }
                    if (newroot->left == nullptr) {
                        first->index = newroot->index;
                        newroot = nullptr;

                    }
                    else {
                        if (newroot->left != nullptr) {
                            leaf* saveleft = newroot->left;
                            first->index = newroot->index;
                            newroot->index = saveleft->index;
                            newroot->left = saveleft->left;
                            newroot->right = saveleft->right;

                        }
                    }
                }
            }
        }

            

    }
}

void printtree(leaf* root, int level = 1) {
    if (root) {
        printtree(root->right, level + 1);
        for (int i = 0; i < level; i++) {
            cout << "-";
        }
        cout << "-";
        cout << root->index << endl;
        printtree(root->left, level + 1);
    }
    else {
        for (int i = 0; i < level; i++) {
            cout << "-";
        }
        cout << "-X" << endl;
    }
}

int main(void) {
    setlocale(LC_ALL, "Ukr");

    leaf* root = nullptr;
    
    

    addroot(&root);

    for (int i = 1; i <= 10; i++) {

        tree(&root, i);
    }
    printtree(root, 0);
    deleteleaf(&root);
    printtree(root, 0);
    



    _getch();
    return 0;

}


Чисто якесь збочення а не програма... Але працює. Не знаю чи так можна (без delete) але, по  суті, працює)

Re: Видалення елементу.

koala написав:
int *a = new int; //десь було виділено кілька байтів під int, їхня адреса записана в a
*a = 50; //записуємо туди якесь число
delete a; //ті байти позначені як вільні; можливо, їх віддали системі, можливо, їх візьме якийсь інший new, але найімовірніше - вони найближчим часом лишатимуться як були
cout << *a; //це UB: a продовжує вказувати за адресою, де нічого не виділено, але найімовірніше, тут буде виведено 50

delete не змінює вказівник, він позначає, що байти, на які вказує той вказівник, є вільними для подальшого використання. Хто саме ними скористається - невідомо, тому брати значення за таким вказівником не варто.

Була поширена практика одразу після delete прирівнювати вказівник NULL:

delete a;
a = NULL; //щоб не забути

але з розвитком "розумних" вказівників std::shared_ptr та std::unique_ptr частіше використовуються саме вони.

Ну таке я ще не вчив, але дякую за відповідь.

20

Re: Видалення елементу.

Без delete пам'ять не звільняється, і якщо програма працюватиме певний час, матимете із цим проблеми.
Крім того, ви в одній функції вводите дані і змінюєте внутрішні структури, це погано. Але якщо це влаштовує вас і викладача, то чого б я обурювався.