Здравствуйте, Зверёк Харьковский, Вы писали:
ЗХ>Струтура данных "дерево" нужна бывает довольно часто.
Я бы еще добавил: и разная.
Ну т.е. в модели файловой системы узлы уникально именованные.
И операции поиска-обхода сугубо специфические.
То же самое и с XML — имплементация должна быть своя.
Про HTML я вообще молчу. Там лес, лесополоса и посевы мака квадратно-гнездовым способом.
Дерево это как правило некий DOM, а на этом DOMе еще много чего висит.
Например в HTML итераторы есть такие char_visitor, word_visitor, paragraph_vistor, floaters_visitor, text_line_visitor и еще до чертиков всякой визиторской лабуды. А координаты? Вообще полный привет.
Т.е. дерево как конструкция (parent)(children)* это только одна из проекций.
Мне кстати пришлось от iteratora в чистом виде уходить.
Оперции типа move_next (++) move_prev(--) пришлось делегировать самим объектам DOM.
Сам термин "позиция итератора" в лесу, в дереве и на маковом поле оченно разные.
Здравствуйте, Зверёк Харьковский, Вы писали:
ЗХ>в ней. никаких свер-возможностей не надо. ЗХ>просто, есть классы, хранящиеся деревом (каталоги-подкаталоги, и все такое) ЗХ>нужно
ЗХ>
ЗХ>1. возможность обойти дерево (итератор) ЗХ>2. возможность обойти только данную ветку (итератор') ЗХ>3. возможность добавить-удалить потомков к ветке. ЗХ>
ЗХ>неужели никому такое не надо?
Дык несложно...
(Начал писать, и понял, что не столько несложно, сколько чертовски рутинно, если подходить грамотно.
Вот что я нарожал в приступе программизма — посмотрите, может что-то полезное найдёте может, не зря я это делал )
ЗХ>Струтура данных "дерево" нужна бывает довольно часто. ЗХ>Внимание, вопрос: кто какую реализацию использует? такое ощущение, что все уже нашли свой идеал... (Впечатление такое оттого, что в "Исходниках" на деревья реагируют крайне слабенько)
Загляни в boost, там есть Boost Graph Library.
Струтура данных "дерево" нужна бывает довольно часто.
Внимание, вопрос: кто какую реализацию использует? такое ощущение, что все уже нашли свой идеал... (Впечатление такое оттого, что в "Исходниках" на деревья реагируют крайне слабенько)
Здравствуйте, Зверёк Харьковский, Вы писали:
ЗХ>Струтура данных "дерево" нужна бывает довольно часто. ЗХ>Внимание, вопрос: кто какую реализацию использует? такое ощущение, что все уже нашли свой идеал... (Впечатление такое оттого, что в "Исходниках" на деревья реагируют крайне слабенько)
А потому что в STL уже контейнер типа map есть.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Здравствуйте, LaptevVV, Вы писали:
LVV>Здравствуйте, Зверёк Харьковский, Вы писали:
ЗХ>>Струтура данных "дерево" нужна бывает довольно часто. ЗХ>>Внимание, вопрос: кто какую реализацию использует? такое ощущение, что все уже нашли свой идеал... (Впечатление такое оттого, что в "Исходниках" на деревья реагируют крайне слабенько) LVV>А потому что в STL уже контейнер типа map есть.
ну и шо?
например, в STL есть вектор с операциями пуш и поп,
а есть стек (контейнер более высокого логического ур-ня)
если нужно именно дерево, на мэп все равно приходится некую обертку делать, хоть бы и тонкую.
ЗЫ: уточняю: я имел в виду не двоичное дерево, а любых размеров.
Здравствуйте, Зверёк Харьковский, Вы писали:
LVV>>А потому что в STL уже контейнер типа map есть. ЗХ>ну и шо? ЗХ>например, в STL есть вектор с операциями пуш и поп, ЗХ>а есть стек (контейнер более высокого логического ур-ня) ЗХ>если нужно именно дерево, на мэп все равно приходится некую обертку делать, хоть бы и тонкую.
ЗХ>ЗЫ: уточняю: я имел в виду не двоичное дерево, а любых размеров.
В смысле арность?
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Здравствуйте, WolfHound, Вы писали:
WH>Здравствуйте, LaptevVV, Вы писали:
LVV>>В смысле арность? WH>Ему надо чтобы у одного узла было сколько угодно потомков.
угу
виноват. хреново формулирую.
Здравствуйте, Зверёк Харьковский, Вы писали:
LVV>>>В смысле арность? WH>>Ему надо чтобы у одного узла было сколько угодно потомков. ЗХ>угу ЗХ>виноват. хреново формулирую.
Это в памяти или на диске?
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Здравствуйте, LaptevVV, Вы писали:
LVV>Здравствуйте, Зверёк Харьковский, Вы писали:
LVV>>>>В смысле арность? WH>>>Ему надо чтобы у одного узла было сколько угодно потомков. ЗХ>>угу ЗХ>>виноват. хреново формулирую. LVV>Это в памяти или на диске?
вопроса не понял
Здравствуйте, Зверёк Харьковский, Вы писали:
LVV>>>>>В смысле арность? WH>>>>Ему надо чтобы у одного узла было сколько угодно потомков. ЗХ>>>угу ЗХ>>>виноват. хреново формулирую. LVV>>Это в памяти или на диске? ЗХ>вопроса не понял
Если на диске, то там рулят B-деревья в различных модификациях.
А если в памяти, то ни в одной классической книжке не встречал программистского подхода к этому вопросу — все сплошь математика.
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Здравствуйте, LaptevVV, Вы писали:
LVV>Если на диске, то там рулят B-деревья в различных модификациях.
B-деревья и в памяти очень хорошо рулят.
1. Не фрагментируют память.
2. При больших объемах поиск быстрее чем в массиве за счет использования кэша ппроцессора куда попадают данные верхних уровней.
3. Простота и скорость навигации (в Б+ дреревьях)
и солнце б утром не вставало, когда бы не было меня
Здравствуйте, LaptevVV, Вы писали:
LVV>Если на диске, то там рулят B-деревья в различных модификациях. LVV>А если в памяти, то ни в одной классической книжке не встречал программистского подхода к этому вопросу — все сплошь математика.
Не задача гораздо банальнее. Очень часто просто нужна структура для хранения какойто иерархии XML, файловая система...
... << RSDN@Home 1.1.3 beta 1 >>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, LaptevVV, Вы писали:
LVV>А если в памяти, то ни в одной классической книжке не встречал программистского подхода к этому вопросу — все сплошь математика.
в ней. никаких свер-возможностей не надо.
просто, есть классы, хранящиеся деревом (каталоги-подкаталоги, и все такое)
нужно
1. возможность обойти дерево (итератор)
2. возможность обойти только данную ветку (итератор')
3. возможность добавить-удалить потомков к ветке.
Здравствуйте, WolfHound, Вы писали:
WH>Здравствуйте, LaptevVV, Вы писали:
LVV>>Если на диске, то там рулят B-деревья в различных модификациях. LVV>>А если в памяти, то ни в одной классической книжке не встречал программистского подхода к этому вопросу — все сплошь математика. WH>Не задача гораздо банальнее. Очень часто просто нужна структура для хранения какойто иерархии XML, файловая система...
во! и я ж об энтом!!!
внутреннее представление не сильно важно (на данном этапе), важно -- класс с интерфейсом дерева!
ЗХ>1. возможность обойти дерево (итератор) ЗХ>2. возможность обойти только данную ветку (итератор') ЗХ>3. возможность добавить-удалить потомков к ветке. ЗХ>
ЗХ>неужели никому такое не надо?
Прошу прощения за назойливость в http://www.1c.hippo.ru/cgi-bin/predownl.cgi?id=2019
сделал простое иерархическое хранилище.
А все что ты пишешь это не деревья, а связные списки.
и солнце б утром не вставало, когда бы не было меня
Здравствуйте, Serginio1, Вы писали:
S> Прошу прощения за назойливость в http://www.1c.hippo.ru/cgi-bin/predownl.cgi?id=2019 S>сделал простое иерархическое хранилище. S> А все что ты пишешь это не деревья, а связные списки.
Это ж как же? а то. что там иерархия -- это все побоку?
Здравствуйте, Зверёк Харьковский, Вы писали:
ЗХ>Здравствуйте, Serginio1, Вы писали:
S>> Прошу прощения за назойливость в http://www.1c.hippo.ru/cgi-bin/predownl.cgi?id=2019 S>>сделал простое иерархическое хранилище. S>> А все что ты пишешь это не деревья, а связные списки.
ЗХ>Это ж как же? а то. что там иерархия -- это все побоку?
Тогда джагед массивы тоже деревья. Всетаки деревья подчиняются некоторому закону роста и балансировке.
А из связных спиках делай какую угодно иерархию, а классические деревья всего лишь подвид связных списков.
и солнце б утром не вставало, когда бы не было меня
Здравствуйте, Зверёк Харьковский, Вы писали:
ЗХ>Здравствуйте, Serginio1, Вы писали:
S>> Тогда джагед массивы тоже деревья... ЗХ>а это хто за зверь, извиняюсь за невежество?
Это массив массивов.
и солнце б утром не вставало, когда бы не было меня
Здравствуйте, Serginio1, Вы писали:
S>Здравствуйте, Зверёк Харьковский, Вы писали:
ЗХ>>Здравствуйте, Serginio1, Вы писали:
S>>> Тогда джагед массивы тоже деревья... ЗХ>>а это хто за зверь, извиняюсь за невежество? S>Это массив массивов.
К коим также можно отнести и Б деревья.
и солнце б утром не вставало, когда бы не было меня
Существует структура данных, которая определяется таким образом:
у каждого элемента 0..N потомков. Один корень.
Если я еще не все перезабыл, то это, стало быть, ациклический направленный граф с одной корневой вершиной.
Хорошо.
Нужна она для представления иерархически организоанной информации (файлы на диске, XML, да что угодно!)
Внимание, вопрос:
КТО КАКИЕ КЛАССЫ ИСПОЛЬЗУЕТ, когда сталкиваеться с такой структурой. Теоретически, такое бывает надо довольно часто.
Здравствуйте, Зверёк Харьковский, Вы писали: ЗХ>Нужна она для представления иерархически организоанной информации (файлы на диске, XML, да что угодно!)
Вот теперь правильная формулировка. ЗХ>Внимание, вопрос: ЗХ>КТО КАКИЕ КЛАССЫ ИСПОЛЬЗУЕТ, когда сталкиваеться с такой структурой. Теоретически, такое бывает надо довольно часто.
Я лично предполагаю, что для каждой задачи делается своя структура данных, это совсем не сложно.
и солнце б утром не вставало, когда бы не было меня
ЗХ>Струтура данных "дерево" нужна бывает довольно часто. ЗХ>Внимание, вопрос: кто какую реализацию использует? такое ощущение, что все уже нашли свой идеал... (Впечатление такое оттого, что в "Исходниках" на деревья реагируют крайне слабенько)
> Начнем с начала. > > Существует структура данных, которая определяется таким образом: > у каждого элемента 0..N потомков. Один корень. > Если я еще не все перезабыл, то это, стало быть, ациклический направленный граф с одной корневой вершиной. > Хорошо. > Нужна она для представления иерархически организоанной информации (файлы на диске, XML, да что угодно!) > Внимание, вопрос: > КТО КАКИЕ КЛАССЫ ИСПОЛЬЗУЕТ, когда сталкиваеться с такой структурой. Теоретически, такое бывает надо довольно часто.
извини, но не вникал в вопрос, но чтобы не изобретать самокат, вот несколько ссылок уже на готовые деревья: www.damtp.cam.ac.uk/user/kp229/tree/ www.codeproject.com/vcpp/stl/wrk.asp www.lsp.ups-tlse.fr/Chafai/libtree.html www.research.att.com/sw/tools/graphviz/
www-h.eng.cam.ac.uk/help/tpl/talks/C++graphs.html www.cs.queensu.ca/home/dalamb/courses/235/slides/thread.html
Переформулирую вопрос еще раз:
Я не столько просил подарить мне исходник дерева, сколько пытался понять:
насколько часто у людей возникает такой вопрос?
есть ли одно решение, которое удовлетворяет всех?
(почему, скажем, в бусте такого нет? неужто настолько никому не надо? только не надо про буст::граф, использовать его как простое дерево не слишком удобно)
Здравствуйте, Зверёк Харьковский, Вы писали:
ЗХ>Я не столько просил подарить мне исходник дерева, сколько пытался понять: ЗХ>насколько часто у людей возникает такой вопрос?
Я думал, думал... и не придумал, для чего мне может понадобится обобщённый вариант дерева.
В том случае, когда мне нужна была древовидная структура, я быстро сооружал её из подручных средств.
Здравствуйте, ArtDenis, Вы писали:
AD>Здравствуйте, Зверёк Харьковский, Вы писали:
ЗХ>>Я не столько просил подарить мне исходник дерева, сколько пытался понять: ЗХ>>насколько часто у людей возникает такой вопрос?
AD>Я думал, думал... и не придумал, для чего мне может понадобится обобщённый вариант дерева. AD>В том случае, когда мне нужна была древовидная структура, я быстро сооружал её из подручных средств.
я хитрее
посмотри тот вариант, который в моем предыдущем сообщении.
там хранит детей и за их добавление-удаление-сортировку отвечает клиент, а дерево — это тонкая оберька над ним — предоставляет только итераторы для обхода.
Здравствуйте, Павел Кузнецов, Вы писали:
ПК>Здравствуйте, Зверёк, Вы писали:
ЗХ>> Струтура данных "дерево" нужна бывает довольно часто. ЗХ>> Внимание, вопрос: кто какую реализацию использует?
ПК>Реализация большая, а интерфейс более-менее такой:
а реализацию? жалько?
Здравствуйте, Зверёк, Вы писали:
ПК>> Реализация большая, а интерфейс более-менее такой:
ЗХ> а реализацию? жалько?
Не жалко а муторно... Если после всех ранее вываленных в этом топике
деревьев все еще хочется чего-нибудь другого, можно, конечно, и попробовать
изолировать от остальных кусков библиотеки. Оно, действительно, надо?
В смысле, если кто-нибудь будет пользоваться, можно и выложить. Но, чё-то
гложут меня сомнения, что при наличии кучи аналогичных классов, кому-то нужен
еще один
Posted via RSDN NNTP Server 1.7 "Bedlam"
Легче одурачить людей, чем убедить их в том, что они одурачены. — Марк Твен
Однако, в конс-паре нет указателя на этаж выше. Поэтому итерируемое дерево на лиспе будет сделать сложно.
Впрочем, нет ничего невозможного. Итератор сам может содержать список — путь до текущего узла. Инкремент сводится к следующим действиям:
* если есть дети — добавить в путь индекс первого ребёнка
* если нет детей, но есть следующий сосед — заменить в пути последний индекс следующим
* пока нет больше соседей и путь не пуст — отбрасывать последний индекс
Здравствуйте, Зверёк Харьковский, Вы писали:
ЗХ>Переформулирую вопрос еще раз: ЗХ>Я не столько просил подарить мне исходник дерева, сколько пытался понять: ЗХ>насколько часто у людей возникает такой вопрос?
У нас (олимпиадники-программисты) часто.
ЗХ>есть ли одно решение, которое удовлетворяет всех?
Ага. Наш кодер помнит (уже на рефлексах) AVL и декартовы деревья, просто деревья реализуются
им по мере надобности одной рукой с завязанными глазами не приходя в сознаник.
ЗХ>(почему, скажем, в бусте такого нет? неужто настолько никому не надо? только не надо про буст::граф, использовать его как простое дерево не слишком удобно)
Я когда-то кидал в "Исходники" сырой вариант дерева. Его попинали немного и привели в пристойный вид.