Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1] 2  Все   Вниз
  Печать  
Автор Тема: Как удалить дерево, созданное динамическl  (Прочитано 19375 раз)
0 Пользователей и 1 Гость смотрят эту тему.
Константин
Гость
« : 01-07-2008 15:55 » 

Здравствуйте всем!
Помогите пожалуйста!
Сам я с вопросом разобраться не сумел, ничего конкретного найти не смог А черт его знает.... программированием занимаюсь не очень давно.
Мне надо организовать данные в веде дерева, новые узлы в него я добавляю динамически. я начал писать класс на подобие этого:
class AAA
{
int data;
AAA *prev,*left,*right;
AddLeft(..);
AddRight(..);
..
};
теперь я пишу AAA *p=new AAA; (это корень дерева), потом добавляю левое и правое поддеревья и тд. а в конце я хочу написать delete(p); и что бы все это дерево удалилось.
теперь проблема: я не догоняю как (конкретно) это сделать. ясно что удалять дерево надо рекурсивно. Помогите пожалуйста прегрузить delete, или быть может надо изначально подругому все делать (?) и еще сделать деструктор к этому слассу.
Спасибо!
« Последнее редактирование: 21-05-2009 03:21 от Алексей1153++ » Записан
Джон
просто
Администратор

de
Offline Offline
Пол: Мужской

« Ответ #1 : 01-07-2008 16:03 » 

Эммм...

Шаг 1
сделай ф-ю, которая бы получала в качестве параметра узел (node) и удаляла в цикле всех детей этого узла (если таковые имеются)

потом сделаем шаг 2
« Последнее редактирование: 01-07-2008 16:05 от Джон » Записан

Я вам что? Дурак? По выходным и праздникам на работе работать. По выходным и праздникам я работаю дома.
"Just because the language allows you to do something does not mean that it’s the correct thing to do." Trey Nash
"Physics is like sex: sure, it may give some practical results, but that's not why we do it." Richard P. Feynman
"All science is either physics or stamp collecting." Ernest Rutherford
"Wer will, findet Wege, wer nicht will, findet Gründe."
Вад
Модератор

ru
Offline Offline
Пол: Мужской

« Ответ #2 : 01-07-2008 16:06 » 

В принципе, как понимаю, тут дерево бинарное - даже цикла не надо Улыбаюсь Или не бинарное, left-right - это только 1й и последний из детей?
Записан
Константин
Гость
« Ответ #3 : 01-07-2008 16:20 » 

с этим проблем возникнуть вроде не должно.
вот как я понимаю ситуацию: эта функция будет использовать delete(), и она же будет находиться внутри перегруженного в моем классе delete()? но разве это не будет зацикливанием, или всмысле бесконечной рекурсией? А черт его знает... или я вообще запутался? что же во 2-м шаге?

я могу сделать что б дерево удалялось так напр: p->mydelete(); но хотелосьбы именно delete(p);
Записан
npak
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #4 : 01-07-2008 17:23 » 

Код:
AAA::~AAA () {
  if (left) delete(left);
  if (right) delete(right);
}

В этом примере есть одна проблема - если вы построили дерево некорректно (например, зациклили), то delete впадет в бесконечный цикл. Это можно обойти так:
Код:
AAA::~AAA () {
  if (left) { AAA* tmp = left; left = 0; delete(tmp); }
  if (right) { AAA* tmp = right; right = 0; delete(tmp); }
}

Даже если в графе есть циклы, присваивания left = 0 и right = 0 их разорвут.
Записан

UniTesK -- индустриальная технология надежного тестирования.

http://www.unitesk.com/ru/
Константин
Гость
« Ответ #5 : 02-07-2008 07:27 » 

2npak: за деструктор благодарю! Улыбаюсь теперь осталось разобраться с перегрузкой delete()
меня только что посетили 3 мысли: 1) деструктор достаточно легкий, я мог бы и сам до него додуматься, в следующий раз так и поступлю. еще раз спасибо!
2)зачем мне деструктор, ведь все созданное динамически лучше удалять руками? Здесь была моя ладья...
3)деструктор лишним никогда не бывает, для общности он должен быть, и пусть будет.
Спс еще раз!
2Вад: да, дерево двоичное
2Джон: вот что у меня получилось с функцией:
Код:
deltree(AAA *p)
{if( !p ) return;
deltree(p->left);
if( !p->left) delete(p->left);
deltree(p->right);
if( !p->right) delete(p->right);
}
смею надеяться, что работать она будет правильно Меня одолевают смутные сомнения
Записан
Алексей++
кот глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #6 : 02-07-2008 08:34 » 

Цитата
зачем мне деструктор, ведь все созданное динамически лучше удалять руками
если  указатель на выделенную память - мембер класса (так или иначе, как например лист дерева - прямо не мембер, но по корню его всё же можно найти) то в деструкторе обязательно надо убедиться и подчистить. Оно, конечно, можно и раньше это сделать в классе, но это не всегда удобно или тупо забудешь это сделать, а деструктор завсегда на стрёме Улыбаюсь
Записан

Константин
Гость
« Ответ #7 : 04-07-2008 14:22 » 

Так а что мне всетаки делать с delete()?  Не понял
Записан
Джон
просто
Администратор

de
Offline Offline
Пол: Мужской

« Ответ #8 : 04-07-2008 15:01 » 

А нафига она тебе нужна? Ты же деструктор сделал. Практически я от тебя ожидал ф-ю, тело которой приведено в коде деструктора от npak. А ты сразу с рекурсивным вызовом сделал. Но тебе и делать-то больше ничего не надо.
Рекурсия будет обеспечена в деструкторе. Поменяй только delete(tmp); на delete tmp; и всё.

И в основной программе:


AAA *p=new AAA;

// заполнение дерева

// удаление в нужный момент

delete p;

зы Ещё раз, на тот случай, если ты этого не видишь. Ты начинаешь удалять root дерева - в деструкторе будут удалены его дети (в твоём случае их 2, в общем их может быть больше), те будут вызваны их деструкторы, они в свою очередь удалют своих детей, те своих и тд. Вот и всё. А откуда ты сей несуразный тезис взял
2)зачем мне деструктор, ведь все созданное динамически лучше удалять руками?
ума не приложу. Автоматически деструктор удалит только сам объект, поэтому ты переписываешь его и дополняешь, что и называется работой ручками.

« Последнее редактирование: 04-07-2008 15:07 от Джон » Записан

Я вам что? Дурак? По выходным и праздникам на работе работать. По выходным и праздникам я работаю дома.
"Just because the language allows you to do something does not mean that it’s the correct thing to do." Trey Nash
"Physics is like sex: sure, it may give some practical results, but that's not why we do it." Richard P. Feynman
"All science is either physics or stamp collecting." Ernest Rutherford
"Wer will, findet Wege, wer nicht will, findet Gründe."
Константин
Гость
« Ответ #9 : 04-07-2008 16:04 » 

теперь кажись понял Улыбаюсь Всем Спасибо Отлично
Записан
Константин
Гость
« Ответ #10 : 04-07-2008 16:20 » 

Цитата
Как и конструкторы, деструкторы могут вызываться явно (при помощи ​оператора С++ delete) или неявно - при выходе объекта из области ​действия
вот какой фразы мне не хватало для понимания картины происходящего. я, тормоз, думал, что delete - это delete, а деструктор - это деструктор. извините А черт его знает... Улыбаюсь
Записан
Джон
просто
Администратор

de
Offline Offline
Пол: Мужской

« Ответ #11 : 04-07-2008 16:46 » 

Ааа те надо было ещё так написать, для пущей наглядности:


{

AAA p;
// заполнение дерева
}

// здесь будет вызван деструктор и всё дерево будет удалено.
Записан

Я вам что? Дурак? По выходным и праздникам на работе работать. По выходным и праздникам я работаю дома.
"Just because the language allows you to do something does not mean that it’s the correct thing to do." Trey Nash
"Physics is like sex: sure, it may give some practical results, but that's not why we do it." Richard P. Feynman
"All science is either physics or stamp collecting." Ernest Rutherford
"Wer will, findet Wege, wer nicht will, findet Gründe."
Антон (LogRus)
Глобальный модератор

ru
Offline Offline
Пол: Мужской
Внимание! Люблю сахар в кубиках!


WWW
« Ответ #12 : 07-07-2008 03:48 » 

я бы детей в умные указатели положил и на деструктор бы забил.
Записан

Странно всё это....
Алексей++
кот глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #13 : 07-07-2008 04:04 » 

а ещё есть вариант: под дерево выделять память одним блоком (а в случае нехватки - перераспределить заново, скопировать уже накопленные данные)
Тогда: удаление делается одним delete [] ... Улыбаюсь
Записан

RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #14 : 07-07-2008 07:43 » 

Алексей1153++, чтобы не перераспределять заново (с копированием данных) можно сделать двухуровневую модель блочного выделения памяти: использовать множество блоков, выделяемых по необходимости; создать каталог (массив) указателей на эти блоки (M указателей); каждый блок содержит N элементов; каждый элемент содержит два индекса: номер блока в каталоге и номер элемента в блоке.
Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
Алексей++
кот глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #15 : 07-07-2008 07:56 » 

Ром, тогда смысл ? Возвращаемся к куче указателей, заместо одного. А память под дерево можно выделять шагами по, скажем 4 метра (зависит от характера данных), это будет не так часто происходить. А ведь в момент начала работы ещё можно прикинуть примерный максимальный размер - тогда пересоздания вообще можно убежать )
А удаляется опять же одним махом
Записан

RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #16 : 07-07-2008 08:06 » 

Леш, не к указателям - к индексам.

pointer = catalog[catalog_idx] + sizeof(element_t) * block_idx;

P.S.: по 4 МБ... Расточителен ты. Сразу видно - программишь для десктопов, а не для серверов. Улыбаюсь
« Последнее редактирование: 07-07-2008 08:12 от RXL » Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
Алексей++
кот глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #17 : 07-07-2008 08:29 » 

ну я , во первых, для примера Улыбаюсь Говорюже - от задачи надо смотреть.
Записан

lapulya
Молодой специалист

ru
Offline Offline

« Ответ #18 : 22-07-2008 10:26 » 

Алексей1153++,
это
Цитата
а ещё есть вариант: под дерево выделять память одним блоком (а в случае нехватки - перераспределить заново, скопировать уже накопленные данные)
Тогда: удаление делается одним delete [] ... Улыбаюсь
не лучшее предложение, поскольку от этого класса дерева могут наследоваться другие классы деревьев и выделять дополнительную память под свои нужды и если программист пишущий эти производные классы не знает как ты чистишь память будут проблемы.

Кстати пушистый если твое предложение (то что я процитировал) вынести в функцию new для данного класса (а можно, если нужно, то и по-выше) получится как раз та самая оптимизация (опускаем замечание RXL с которым я кстати полностью согласен... это я про расточительство... но не важно, поскольку затевалась именно оптимизация) работы с памятью о которой мы как-то с тобой разговаривали, и ты помнится с пеной у рта доказывал что это типа не надо никому )))), а тут сам предложил...
« Последнее редактирование: 22-07-2008 10:38 от lapulya » Записан

С уважением Lapulya
lapulya
Молодой специалист

ru
Offline Offline

« Ответ #19 : 22-07-2008 10:35 » 

Джон,
Цитата
Поменяй только delete(tmp); на delete tmp; и всё
лучше писать так delete(tmp);, почему - не помню, но так говорил или сам Страуструп или автор Effective stl, короче кто-то достаточно мной уважаемый (повторю я не помню его аргументацию, но автор настаивал на таком написании)
Записан

С уважением Lapulya
Джон
просто
Администратор

de
Offline Offline
Пол: Мужской

« Ответ #20 : 22-07-2008 11:04 » 

"Маразм крепчал" (с)
Записан

Я вам что? Дурак? По выходным и праздникам на работе работать. По выходным и праздникам я работаю дома.
"Just because the language allows you to do something does not mean that it’s the correct thing to do." Trey Nash
"Physics is like sex: sure, it may give some practical results, but that's not why we do it." Richard P. Feynman
"All science is either physics or stamp collecting." Ernest Rutherford
"Wer will, findet Wege, wer nicht will, findet Gründe."
lapulya
Молодой специалист

ru
Offline Offline

« Ответ #21 : 22-07-2008 11:09 » 

Джон, если не веришь, могу и поискать...
Записан

С уважением Lapulya
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #22 : 22-07-2008 16:27 » 

Джон, подробнее, пожалуйста...

lapulya, примеры из книг и жизни никогда не помешают.
Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
Алексей++
кот глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #23 : 22-07-2008 16:34 » 

lapulya,
Цитата
если твое предложение  вынести в функцию new для данного класса

йа?? вынести Не понял Никогда в жизни не переписывал new Улыбаюсь Не требовалось ни разу
Записан

lapulya
Молодой специалист

ru
Offline Offline

« Ответ #24 : 23-07-2008 09:26 » 

Алексей1153++,
new как правило переписывается для оптимизации по скорости реже для дефрагментации, ты предлагал сделать именно оптимизацию правда и по скорости и по удобству работы (это я про удаление). Видимо следуя твоему совету нужна была некая функция которая выделяла/перераспределяла память (ну там при добавлении/удалении узлов дерева) и вот если эту функцию назвать new, то мы и придем к тому от чего ты открещиваешься))), хотя предложил то сам!!! у меня пол интернета в свидетелях ))))

Ну а то что ни разу не требовалось... так это погоди... вся жизнь впереди, надейся и жди... ))))
Записан

С уважением Lapulya
Алексей++
кот глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #25 : 23-07-2008 15:16 » 

lapulya, ты неправильно  меня понял Улыбаюсь Я не предлагал некую функцию (и Боже упаси меня трогать new Улыбаюсь) ) я способ предлагал. А функцией это сделать или нет - решать автору
Записан

Константин
Гость
« Ответ #26 : 25-07-2008 09:10 » 

Разрешите задать еще один (уточняющий) вопрос (чтобы покончить (на время) с перегруженным delete'ом): когда я вызываю этот delete (напр. delete ( c )  ) то:
1)выполняется то, что написано в теле delete'а
2)освобождается память под указателем ( с ) ?
да?
И, значит, перегрузить delete так, чтобы он ничего не удалял не получится?
Записан
Джон
просто
Администратор

de
Offline Offline
Пол: Мужской

« Ответ #27 : 25-07-2008 10:45 » 

Константин, у тебя какое-то превратное понятие оператора вызова деструктора. Ты вобще-то теорию читаешь? И если да, то какую?

class A
{
public:
   A() {}

   ~A()
   {
      int i=3;
      // format c: и прочая чепуха
   }
};

   A *pA = new A();

   // delete pA; - здесь вызовется ~A();
   // или ты можешь написать явно:
        pA->~A();

   pA = NULL;
Записан

Я вам что? Дурак? По выходным и праздникам на работе работать. По выходным и праздникам я работаю дома.
"Just because the language allows you to do something does not mean that it’s the correct thing to do." Trey Nash
"Physics is like sex: sure, it may give some practical results, but that's not why we do it." Richard P. Feynman
"All science is either physics or stamp collecting." Ernest Rutherford
"Wer will, findet Wege, wer nicht will, findet Gründe."
Константин
Гость
« Ответ #28 : 25-07-2008 16:52 » 

не, как вызывать деструктор я в курсе, я хотел уточнить что происходит конкретно при этом.
PS пжлста, не надо сравнивать меня с людьми, которые пишут сюда для того чтобы курсовую сдать или еще чего там, я хочу научиться прогать на С++, делаю это не потому что меня кто-то где-то заставляет, я делаю это для собственного удовольствия и полностью добровольно. Я читал кучу всякого, и вообще по алгоритмам, и конкретно про Си. К сожалению примеров прегрузки операторов там немного, delete'а вообще не встречал. как использовать различные средства языка там написано, но что конкретно стоит за каждым из этих средств - нет. это я и пытаюсь сейчас понять, и надеюсь на вашу помощь.
Если посоветуете чего еще почитать - не откажусь.
Записан
Алексей++
кот глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #29 : 25-07-2008 17:57 » 

Константин, деструктор просто вызывается (гарантированно для автоматически созданных объектов или перед освобождением памяти после вызова delete для объектов, созданных через new). В деструкторе нужно проделать операции, необходимые для "чистки", например, а можно и ничего не делать
Записан

Страниц: [1] 2  Все   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines