С Новым годом! Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.50/4: Рейтинг темы: голосов - 4, средняя оценка - 4.50
0 / 0 / 0
Регистрация: 06.10.2020
Сообщений: 27

Очистка памяти, выделенной под небинарное дерево

24.10.2022, 14:23. Показов 840. Ответов 6
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Здравствуйте, реализовал небинарное дерево. Проблема с очисткой памяти. По отладчику пробегался, функция clear вроде как удаляет каждый узел дерева и указатель на узел приравнивает к нулю. Очищаю сверху вниз: от корня и дальше по листьям рекурсивно. Но тем не менее выделенная память не очищается


Заголовочный файл с классом Node

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Node {
public:
    int index_from; //индекс клетки, откуда ходили
    int index_to; //индекс клетки, куда сходили
    MatrixXd table; //новая доска
    vector<Node*> next_move; //возможные ходы из этой клетки
    Node* last_move; //предыдущий ход
    bool eating; //был ли сделан съедобный ход
 
    //начальный ход
    Node(int ind_from, int ind_to, MatrixXd tab, bool eat = false) {
        table = MatrixXd::Constant(1, 32, 0);
        this->index_from = ind_from;
        this->index_to = ind_to;
        this->table = tab;
        this->last_move = nullptr;
        this->eating = eat;
    }
    //промежуточный ход
    Node(int ind_from, int ind_to, MatrixXd tab, Node* last) {
        MatrixXd::Constant(1, 32, 0);
        this->index_from = ind_from;
        this->index_to = ind_to;
        this->table = tab;
        last_move = last;
    }
    //для каждого дочернего узла указать родительский
    void add_parent(vector<Node*>& children) {
        for (int i = 0; i < children.size(); i++) {
            (*children[i]).last_move = this;
        }
        next_move = children;
    }
    //найти родителя
    Node* find_parent() {
        if (this->last_move == nullptr) return nullptr;
        else {
            Node* parent = this->last_move;
            if (parent->last_move == nullptr) return parent;
            else return parent->find_parent();
        }
    }
    
    
};
 
void clear(Node*& node);







Функция очистки clear и в конце функции model_make_move произвожу очистку. Нахожу все начала деревьев и запускаю очистку

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
void clear(Node* &node) {
    //if (node->last_move != NULL) clear(node->last_move);
    for (int i = 0; i < node->next_move.size(); i++) {
        if(node->next_move[i] != NULL) clear(node->next_move[i]);
    }
    delete node;
    node = nullptr;
}
 
//модель делает ход
int model_make_move(MatrixXd& table, Model* model, bool& eating) {
    //модель находит все ходы
    vector<Node*> all_moves = find_moves(table);
    //модель оценивает каждый последний ход
    if (all_moves.size()== 0) return -1;
    int ind = 0;
    double max = 0;
    for (int i = 0; i < all_moves.size(); i++) {
        double score = ((*model).forward((*all_moves[i]).table))(0, 0);
        //если этот ход самый лучший, запомним
        if (score > max) {
            ind = i;
            max = score;
        }
    }
    //находим родителя
    
    Node* parent = (*all_moves[ind]).find_parent();
    //модель делает ход
    table = (*parent).table;
    //запоминаем, был ли ход съедобным
    eating = (*parent).eating;
    //номер шашки, которой ходила модель
    int out = parent->index_to;
    vector<Node*> parents;
    //очистка памяти
    for (int i = 0; i < all_moves.size(); i++) {
        //if (all_moves[i] != NULL)clear(all_moves[i]);
        Node* parent = all_moves[i]->find_parent();
        if (find(parents.begin(), parents.end(), parent) == parents.end()) 
            parents.push_back(parent);
    }
    for (int i = 0; i < parents.size(); i++) {
        if (parents[i] != NULL) clear(parents[i]);
    }
 
    return out;
}
0
Лучшие ответы (1)
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
24.10.2022, 14:23
Ответы с готовыми решениями:

Как построить небинарное дерево?
(дерево двоичное, но не бинарное) Надеюсь, меня поняли) числа могут повторяться)

Небинарное дерево с использованием <map>
Здравствуйте, есть такая задача: реализовать дерево, где у узла может быть несколько детей (т.е. может быть недвоичное дерево)....

Очистка памяти. Бинарное дерево.
Как очистить память если не удалось выделить её,очистить то что удлось выделить ,и как удалить память если удалось выделить, ...

6
 Аватар для Tanya2007
593 / 230 / 72
Регистрация: 13.05.2020
Сообщений: 412
24.10.2022, 20:05
Сложно понять, что у вас не так, не видя что происходит в функции main. Например мне не понятна эта строка
Цитата Сообщение от Nikis0715 Посмотреть сообщение
delete node;
. delete применяется, если вы выделяли память с помощью new. У вас так выделяется память? Через new? Выложите весь код.
0
0 / 0 / 0
Регистрация: 06.10.2020
Сообщений: 27
24.10.2022, 20:56  [ТС]
У меня файлы из архивы подключены к mfc. Там выполняется следующий код ниже. Выделение памяти под Node происходит в функции vector<Node*> avaliable_model_move. То есть, я выделяю память через new.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
vector<double> sizes = { 32, 40, 10, 1 };
population.new_population(population_size, sizes);
 
fstream fout("evolution_info.txt", ios_base::app);
 
    map<int, double> index_score;
    int i = 0;
    auto begin = chrono::steady_clock::now(); //начало отсчета
    auto end = chrono::steady_clock::now(); // конец отсчета
    auto duration = chrono::duration_cast<chrono::milliseconds>(end - begin); //время в заданной степени секунд
    double max = 0;
    int ind = 0;
    BeginWaitCursor();
        do {
                        
            index_score = population.evolution(0,0);
            bool update = false;
 
            for (int j = 0; j < population_size; j++) {
 
                if (index_score[j] > max)
                {
                    max = index_score[j];
                    ind = j;
                    update = true;
                }
            }
            
            fout << "Поколение №" << i << " Прошло " << duration.count() / 1000. << " секунд" << endl;
            fout << "Лучший рейтинг " << max << " Средний рейтинг " << population.fitness[population.fitness.size() - 1] << endl;
            end = chrono::steady_clock::now(); // конец отсчета
            duration = chrono::duration_cast<chrono::milliseconds>(end - begin); //время в заданной степени секунд
            population.save_model(ind);
            i++;
 
        } while (duration.count() / 1000 < evolve_time);
 
            //evolve_time - время в секундах
 
        EndWaitCursor();
        end = chrono::steady_clock::now(); // конец отсчета
        duration = chrono::duration_cast<chrono::milliseconds>(end - begin); //время в заданной степени секунд
        fout << "Эволюция закончена за " << duration.count() / 1000. << " секунд" << endl << endl;
        fout.close();
Вложения
Тип файла: rar checkers.rar (10.2 Кб, 5 просмотров)
0
0 / 0 / 0
Регистрация: 06.10.2020
Сообщений: 27
24.10.2022, 21:03  [ТС]
По факту, я храню только последние элементы дерева. Как с деревом поработал, я нахожу его начало и начинаю очищать от начала вниз. Указатели зануляются, но оперативная память забивается. Если нужно, могу скинуть вообще весь проект. Через отладку заглядывал в кучу, больше всего весит Node*
0
 Аватар для Tanya2007
593 / 230 / 72
Регистрация: 13.05.2020
Сообщений: 412
25.10.2022, 10:41
Лучший ответ Сообщение было отмечено Nikis0715 как решение

Решение

Просмотрела ваш код. Первое что заметила в функции
C++
1
vector<Node*> avaliable_model_move(MatrixXd& table, bool& eating)
, которая вызывается у вас довольно во многих других функциях, есть такой цикл
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<Node*> tree_moves;
........
if(eating == can_eat_all){
                //добавим новую вершину дерева
                //для каждой позиции сохраним следующий ход
                for (int j = 0; j < moves_2d.size(); j++) {
                    vector<vector<int>> board_new = make_move(board, row, col, moves_2d[j][0], moves_2d[j][1]);
                    MatrixXd table_new = make_board_for_model(board_new);
                    Node* node_next = new Node(i, moves_2d[j][0]*4+ moves_2d[j][1]/2, table_new, can_eat_all);
                    tree_moves.push_back(node_next);
                }
                
            }
.......
return tree_moves;
. Полагаю, что при определенных условиях цикл отрабатывает. Затем, например, в функции
C++
1
vector<Node*> eat_while_can_eat(MatrixXd& table)
выполняется такой код:
C++
1
2
3
4
5
vector<Node*> moves = avaliable_model_move(table, can_eat); 
if (!can_eat) {
        moves.clear();
        return moves;
    }
. Вы очищаете вектор, в который помещали указатели на память, выделенную с помощью new. Но если вам вектор больше не нужен, то память вы не очищаете. Надо добавить условие, что если вектор не пуст, то пройтись по элементам вектора и очистить память с помощью delete.

Возможно, где-то еще будет подобное, потому что на функцию
C++
1
vector<Node*> avaliable_model_move(MatrixXd& table, bool& eating)
вы ссылаетесь довольно часто в коде.
1
0 / 0 / 0
Регистрация: 06.10.2020
Сообщений: 27
25.10.2022, 21:05  [ТС]
Спасибо большое, это было самое проблемное место программы. Где-то еще не до конца очищаю память, буду дальше искать
0
 Аватар для Tanya2007
593 / 230 / 72
Регистрация: 13.05.2020
Сообщений: 412
25.10.2022, 21:34
Рада помочь)
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
25.10.2022, 21:34
Помогаю со студенческими работами здесь

Освобождение памяти, выделенной под массив
Выделяю память под массив: int (*array_1) = new int; как освободить то, что выделил? И еще вопрос: как указателю...

Размер памяти, выделенной под массив записей
Здравствуйте, дорогие форумчане! Сейчас выполняю лабораторную работу по C++ с оценкой эффективности алгоритмов и застрял на одном...

Распределение оперативной памяти выделенной под программу
Здравствуйте. Помогите с объяснением некоторых тем, нигде не могу найти. №1 Целый тип данных. Даже не знаю, о чем там можно...

Обнулить кусок памяти (выделенной под указатели) по быстрому
Есть хеш-таблица и есть кусок памяти под неё, нужно занулить изначально весь кусок памяти, но как можно быстрее, те хорошо бы использовать...

Функция не видит выделенной памяти под глобальные переменные
При решении задачи с алгоритмом поиска в глубину возникла проблема: описание переменных происходит над п/п алгоритма, выделение памяти под...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
7
Ответ Создать тему
Новые блоги и статьи
Новый CodeBlocs. Версия 25.03
palva 04.01.2026
Оказывается, недавно вышла новая версия CodeBlocks за номером 25. 03. Когда-то давно я возился с только что вышедшей тогда версией 20. 03. С тех пор я давно снёс всё с компьютера и забыл. Теперь. . .
Модель микоризы: классовый агентный подход
anaschu 02.01.2026
Раньше это было два гриба и бактерия. Теперь три гриба, растение. И на уровне агентов добавится между грибами или бактериями взаимодействий. До того я пробовал подход через многомерные массивы,. . .
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост.
Programma_Boinc 28.12.2025
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / **********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / **********/ gallery/ bKBkQFf Пост отсюда. . .
Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США.
Programma_Boinc 26.12.2025
Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .
Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка.
Programma_Boinc 23.12.2025
Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .
PhpStorm 2025.3: WSL Terminal всегда стартует в ~
and_y87 14.12.2025
PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .
Как объединить две одинаковые БД Access с разными данными
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук
volvo 07.12.2025
Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru