Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 5.00
emilen
10 / 10 / 0
Регистрация: 25.05.2010
Сообщений: 52
#1

Рекурсия и статические переменные. - C++

17.09.2011, 10:46. Просмотров 1164. Ответов 11
Метки нет (Все метки)

Что - то я запутался. Пытаюсь написать деструктор для своего бинарного дерева поиска, но мне не понятно поведение статических переменных. У меня не заходит в левую ветвь дерева, удаление происходит только правых элементов. Отсюда утечки памяти. Если убрать static у переменных то все правильно удаляется (выводиться, в моем примере). Я правильно понимаю то, что это не хорошо использовать в рекурсивных функциях «обычные» переменные, так как выделяется слишком много памяти под них? Помогите, пожалуйста, разобраться.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
template <class Item>
void delete_tree(Node<Item> item[])
{
    if (item != 0) {
        static Node<Item> *right, *left;
        right = item->right;
        left = item->left;
        cout << item->item << " ";
    //  delete item;
        delete_tree(right);
        delete_tree(left);
    }
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Thinker
Эксперт C++
4220 / 2194 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
17.09.2011, 11:06     Рекурсия и статические переменные. #2
Удалять надо правильно (с нижних уровней):

delete_tree(right);
delete_tree(left);
delete item;

либо

delete_tree(left);
delete_tree(right);
delete item;
emilen
10 / 10 / 0
Регистрация: 25.05.2010
Сообщений: 52
17.09.2011, 11:11  [ТС]     Рекурсия и статические переменные. #3
Цитата Сообщение от Thinker Посмотреть сообщение
Удалять надо правильно
С чего вы взяли, что у вас правильно, а у меня не правильно? Вы сначала проверяйте, что пишете, перед тем как выкладывать.
Thinker
Эксперт C++
4220 / 2194 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
17.09.2011, 11:15     Рекурсия и статические переменные. #4
Цитата Сообщение от emilen Посмотреть сообщение
С чего вы взяли, что у вас правильно, а у меня не правильно? Вы сначала проверяйте, что пишете, перед тем как выкладывать.

Не по теме:

Вообще то давно уже проверено временем...

emilen
10 / 10 / 0
Регистрация: 25.05.2010
Сообщений: 52
17.09.2011, 11:24  [ТС]     Рекурсия и статические переменные. #5
Thinker, ваш вариант, такой же как и мой, только дерево выводиться(удаляется) немного иначе и он так же не работоспособен со статическими переменными.
easybudda
Эксперт С++
9412 / 5435 / 917
Регистрация: 25.07.2009
Сообщений: 10,428
17.09.2011, 11:39     Рекурсия и статические переменные. #6
emilen, просто из любопытства: а зачем в рекурсивно вызываемой функции удаления узлов дерева статические переменные?
emilen
10 / 10 / 0
Регистрация: 25.05.2010
Сообщений: 52
17.09.2011, 11:51  [ТС]     Рекурсия и статические переменные. #7
easybudda, потому что используя не статические переменные при большой глубине рекурсии будет выделено много памяти и возможно переполнение стека, статические переменные должны исправить эту проблему, я правильно понимаю?
Net_Wanderer
235 / 208 / 19
Регистрация: 08.06.2011
Сообщений: 467
17.09.2011, 12:01     Рекурсия и статические переменные. #8
При первом вызове delete_tree (на верхнем уровне рекурсии), right и left присваиваются значения и после того как выполнится строка delete_tree(right); т.е. будет удаленно правое поддрево, переменная left уже не будет содержать прежнего значения и здесь: delete_tree(left); left будет указывать не на левое поддрево, а на что-то другое.
emilen
10 / 10 / 0
Регистрация: 25.05.2010
Сообщений: 52
17.09.2011, 12:08  [ТС]     Рекурсия и статические переменные. #9
Цитата Сообщение от Net_Wanderer Посмотреть сообщение
переменная left уже не будет содержать прежнего значения
Вот, а почему оно не будет содержать значения? Это мне и не понятно.
Net_Wanderer
235 / 208 / 19
Регистрация: 08.06.2011
Сообщений: 467
17.09.2011, 12:11     Рекурсия и статические переменные. #10
Цитата Сообщение от emilen Посмотреть сообщение
Вот, а почему оно не будет содержать значения? Это мне и не понятно.
Потому что переменные статические, и все рекурсивные вызовы delete_tree работают с одними и теми же переменными.
emilen
10 / 10 / 0
Регистрация: 25.05.2010
Сообщений: 52
17.09.2011, 12:15  [ТС]     Рекурсия и статические переменные. #11
Net_Wanderer, большое спасибо, наконец то до меня дошло. А можете предложить свой вариант решения проблемы? Использовать локальные переменные?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.09.2011, 12:39     Рекурсия и статические переменные.
Еще ссылки по теме:

Статические переменные и функции C++
C++ Создать бинарное дерево, по правой ветке - переменные типа инт, по левой - 2 переменные типа чар
C++ В каких случаях нужно создавать динамические переменные, а в каких статические?
C++ Создать программу обработки массивов структур используя структурные переменные и переменные типа объеденения
Статические переменные C++

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

Или воспользуйтесь поиском по форуму:
Net_Wanderer
235 / 208 / 19
Регистрация: 08.06.2011
Сообщений: 467
17.09.2011, 12:39     Рекурсия и статические переменные. #12
Цитата Сообщение от emilen Посмотреть сообщение
Net_Wanderer, большое спасибо, наконец то до меня дошло. А можете предложить свой вариант решения проблемы? Использовать локальные переменные?
Да, вот ещё не плохая статья про деревья http://algolist.manual.ru/ds/btree.php.
Yandex
Объявления
17.09.2011, 12:39     Рекурсия и статические переменные.
Ответ Создать тему
Опции темы

Текущее время: 09:56. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru