Примеры кода

Dim77 wrote:Как лучше это дерево хранить, и как обход этих поддеревьев лучше делать ?

- Давайте же начнем! - сказал Морж,
усаживаясь на прибрежном камне.
- Пришло время потолковать о многих вещах:
о башмаках, о кораблях, о сургучных
печатях, о капусте и о королях.

О'Генри, "Короли и капуста".

Деревья (trees) - это такие графы особого типа, бывают бинарными и не очень :wink:
Можно рекурсивно определить дерево как узел, называемый корнем (node) дерева, связанный с нулем или более поддеревьев (subtrees).
Терминология деревьев представляет собой смесь терминов, позаимствованных из ботаники и генеалогии. Из ботаники пришли термины, такие как узел (node), определяемый как точка, в которой может начинаться ветвление, ветвь (branch), определяемая как связь между двумя узлами, и лист (leaf) — узел, из которого не выходят другие ветви.
Из генеалогии пришли термины, которые описывают родство. Если один узел находится непосредственно над другим, верхний узел называется родителем (parent), а нижний дочерним узлом (child). Узлы на пути вверх от узла до корня называются предками (ancestors) узла. Узлы, которые находятся ниже какого либо узла дерева, называются потомками (descendants) этого узла. Иногда узлы, имеющие одного родителя, называются узлами братьями или узлами сестрами (sibling nodes).
Существует еще несколько терминов, которые не пришли из ботаники или генеалогии. Внутренним узлом (internal node) называется узел, который не является листом. Порядком узла (node degree) называется число его дочерних узлов. Порядок дерева — это наибольший порядок его узлов. Дерево конспиративной сети, приведенное в примере к задаче, — третьего порядка, потому что узлы с наибольшим порядком, узлы 2 и 6, имеют по 3 дочерних узла. Глубиной (depth) или высотой (height) дерева называется наибольшая глубина его узлов. Глубина (depth) поддерева равна числу его предков плюс 1.
Дерево 2 порядка называется двоичным деревом (binary tree). Деревья третьего порядка иногда называются троичными (ternary) деревьями. Более того, деревья порядка N обычно называются N-арными (N ary) деревьями.
Если с терминологией разобрались, то можно двигать дальше...

Приведу сначала простой пример реализации троичного дерева, скажем, на языке Visual Basic (2Dim77, перевод на Visual C++ тебе в качестве домашнего задания

). Один из способов — создать отдельный класс для каждого типа узлов дерева. Например, можно определить структуры данных для узлов, которые имеют ноль, один, два или три дочерних узла. Этот подход был бы довольно неудобным. Кроме того, что нужно было бы управлять четырьмя различными классами, в классах потребовались бы какие то флаги, которые бы указывали тип дочерних узлов. Алгоритмы, которые оперировали бы этими деревьями, должны были бы уметь работать со всем различными типами деревьев.
В качестве простого решения можно определить один тип узлов, который содержит достаточное число указателей на потомков для представления всех нужных узлов. Я называю это методом полных узлов, так как некоторые узлы могут быть большего размера, чем необходимо на самом деле.
Дерево в нашем примере имеет 3 порядок. Для построения этого дерева с использованием метода полных узлов (fat nodes), требуется определить единственный класс, который содержит указатели на три дочерних узла. Следующий код демонстрирует, как эти указатели могут быть определены в классе TernaryNode.

Public LeftChild As TernaryNode
Public MiddleChild As TernaryNode
Public RightChild As TernaryNode

При помощи этого класса можно построить дерево, используя записи Child узлов, для связи их друг с другом. Следующий фрагмент кода строит два верхних уровня дерева, корневой узел A которого связан с тремя поддеревьями, начинающимися в узлах B, C и D.

Dim A As New TernaryNode
Dim B As New TernaryNode
Dim C As New TernaryNode
Dim D As New TernaryNode
:

Set A.LeftChild = B
Set A.MiddleChild = C
Set A.RightChild = D
:

Однако, если порядки узлов в дереве сильно различаются, метод полных узлов приводит к напрасному расходованию большого количества памяти.

Динамически изменяющиеся деревья удобно представить, поместив дочерние узлы в списки. Есть несколько подходов, которые можно использовать для создания списков дочерних узлов. Наиболее очевидный подход заключается в создании в классе узла открытого (public) массива дочерних узлов, как показано в следующем коде. Тогда для оперирования дочерними узлами можно использовать методы работы со списками на основе массивов.

Public Children() As TreeNode
Public NumChildren As Integer

К сожалению, Visual Basic не позволяет определять открытые массивы в классах. Это ограничение можно обойти, определив массив как закрытый (private), и оперируя элементами массива при помощи процедур свойств.

Private m_Chirdren() As TreeNode
Private m_NumChildren As Integer

Property Get Children(Index As Integer) As TreeNode
Set Children = m_Children(Index)
End Property

Property Get NumChildren() As Integer
NumChildren = m_NumChildren()
End Property

Второй подход состоит в том, чтобы сохранять ссылки на дочерние узлы в связных списках. Каждый узел содержит ссылку на первого потомка. Он также содержит ссылку на следующего потомка на том же уровне дерева. Эти связи образуют связный список узлов одного уровня, поэтому я называю этот метод представлением в виде связного списка узлов одного уровня (linked sibling).
Третий подход заключается в том, чтобы определить в классе узла открытую коллекцию, которая будет содержать дочерние узлы:

Public Children As New Collection

Это решение позволяет использовать все преимущества коллекций. Программа может при этом легко добавлять и удалять элементы из коллекции, присваивать дочерним узлам ключи, и использовать оператор For Each для выполнения циклов со ссылками на дочерние узлы.

Представление нумерацией связей (forward star) позволяет компактно представить деревья, графы и сети при помощи массива. Для представления дерева нумерацией связей, в массиве FirstLink записывается индекс для первых ветвей, выходящих из каждого узла. В другой массив, ToNode, заносятся узлы, к которым ведет ветвь.
Сигнальная метка в конце массива FirstLink указывает на точку сразу после последнего элемента массива ToNode. Это позволяет легко определить, какие ветви выходят из каждого узла. Ветви, выходящие из узла I, находятся под номерами от FirstLink(I) до FirstLink(I+1)-1. Для вывода связей, выходящих из узла I, можно использовать следующий код:

For link = FirstLink(I) To FirstLink(I + 1) - 1
Print Format$(I) & " -> " & Format$(ToNode(link))
Next link

Представление дерева нумерацией связей компактно и основано на массиве, поэтому деревья, представленные таким образом, можно легко считывать из файлов и записывать в файл. Операции для работы с массивами, которые используются при таком представлении, также могут быть быстрее, чем операции, нужные для использования узлов, содержащих коллекции дочерних узлов.
По этим причинам большая часть литературы по сетевым алгоритмам использует представление нумерацией связей. Например, многие статьи, касающиеся вычисления кратчайшего пути, предполагают, что данные находятся в подобном формате. Если вам когда-либо придется изучать эти алгоритмы в журналах, таких как "Management Science" или "Operations Research", вам необходимо разобраться в этом представлении.

Используя представление нумерацией связей, можно быстро найти связи, выходящие из определенного узла. С другой стороны, очень сложно изменять структуру данных, представленных в таком виде. Чтобы добавить к узлу A из примера выше еще одного потомка, придется изменить почти все элементы в обоих массивах FirstLink и ToNode. Во первых, каждый элемент в массиве ToNode нужно сдвинуть на одну позицию вправо, чтобы освободить место под новый элемент. Затем, нужно вставить новую запись в массив ToNode, которая указывает на новый узел. И, наконец, нужно обойти массив ToNode, обновив каждый элемент, чтобы он указывал на новое положение соответствующей записи ToNode. Поскольку все записи в массиве ToNode сдвинулись на одну позицию вправо, чтобы освободить место для новой связи, потребуется добавить единицу ко всем затронутым записям FirstLink.
Удаление узла из начала представления нумерацией связей так же сложно, как и вставка узла. Если удаляемый узел имеет потомков, процесс занимает еще больше времени, поскольку придется удалять и все дочерние узлы.
Относительно простой класс с открытой коллекцией дочерних узлов лучше подходит, если нужно часто модифицировать дерево. Обычно проще понимать и отлаживать процедуры, которые оперируют деревьями в этом представлении. С другой стороны, представление нумерацией связей иногда обеспечивает более высокую производительность для сложных алгоритмов работы с деревьями. Оно также являются стандартной структурой данных, обсуждаемой в литературе, поэтому вам следует ознакомиться с ним, если вы хотите продолжить изучение алгоритмов работы с сетями и деревьями.

Следующий код демонстрирует удаление узла из дерева с использованием представления на основе массива, а не коллекций:

Sub FreeNodeAndChildren(ByVal parent As Integer, _
ByVal link As Integer, ByVal node As Integer)

' Recursively remove the node's children.
Do While FirstLink(node) < FirstLink(node + 1)
FreeNodeAndChildren node, FirstLink(node), _
ToNode(FirstLink(node))
Loop

' Удалить связь.
RemoveLink parent, link

' Удалить сам узел.
RemoveNode node
End Sub

Sub RemoveLink(node As Integer, link As Integer)
Dim i As Integer

' Обновить записи массива FirstLink.
For i = node + 1 To NumNodes
FirstLink(i) = FirstLink(i) - 1
Next i

' Сдвинуть массив ToNode чтобы заполнить пустую ячейку.
For i = link + 1 To NumLinks - 1
ToNode(i - 1) = ToNode(i)
Next i

' Удалить лишний элемент из ToNode.
NumLinks = NumLinks - 1
If NumLinks > 0 Then ReDim Preserve ToNode(0 To NumLinks - 1)
End Sub

Sub RemoveNode(node As Integer)
Dim i As Integer

' Сдвинуть элементы массива FirstLink, чтобы заполнить
' пустую ячейку.
For i = node + 1 To NumNodes
FirstLink(i - 1) = FirstLink(i)
Next i

' Сдвинуть элементы массива NodeCaption.
For i = node + 1 To NumNodes - 1
NodeCaption(i - 1) = NodeCaption(i)
Next i

' Обновить записи массива ToNode.
For i = 0 To NumLinks - 1
If ToNode(i) >= node Then ToNode(i) = ToNode(i) - 1
Next i

' Удалить лишнюю запись массива FirstLink.
NumNodes = NumNodes - 1
ReDim Preserve FirstLink(0 To NumNodes)

ReDim Preserve NodeCaption(0 To NumNodes - 1)
Unload FStarForm.NodeLabel(NumNodes)
End Sub

Гораздо проще, но требовательней к ресурсам, будет так:

Public Function DeleteDescendant(target As NAryNode) As Boolean
Dim i As Integer
Dim child As NAryNode

' Является ли узел дочерним узлом.
For i = 1 To Children.Count
If Children.Item(i) Is target Then
Children.Remove i
DeleteDescendant = True
Exit Function
End If
Next i

' Если это не дочерний узел, рекурсивно
' проверить остальных потомков.
For Each child In Children
If child.DeleteDescendant(target) Then
DeleteDescendant = True
Exit Function
End If
Next child
End Function

Таким образом, существует множество способов представления деревьев. Наиболее эффективным и компактным из них является запись полных деревьев в массивах. Представление деревьев в виде коллекций дочерних узлов упрощает работу с ними, но при этом программа выполняется медленнее и использует больше памяти. Представление нумерацией связей позволяет быстро выполнять обход дерева и использует меньше памяти, чем коллекции потомков, но его сложно модифицировать. Тем не менее, его важно представлять, потому что оно часто используется в сетевых алгоритмах.
На сегодня, пожалуй, хватит, если хотите продолжения - спрашивайте...

OraCool, ты все интересно пишешь... может сразу весь трехтомник Кнута сюда запостишь?!

Уж очень много инфы, которую преподают в универе и в литературе найти можно не напрягаясь.

SpotteR wrote:Уж очень много инфы, которую преподают в универе и в литературе найти можно не напрягаясь.

Пусть первый бросит в меня камень тот, кто скажет, что это были не Примеры кода. Раз не хотите теории, нечего было задавать провокационных вопросов! Учите матчасть сами

Только что-то не одного решения поставленной задачи не наблюдается...

OraCool wrote:
Пусть первый бросит в меня камень тот, кто скажет, что это были не Примеры кода. Раз не хотите теории, нечего было задавать провокационных вопросов! Учите матчасть сами

Только что-то не одного решения поставленной задачи не наблюдается...

Нет, бросать не будем. Но задача серьезная. Ее кодить надо не один час. А этих часов то и нету совсем

Ты сам то представляешь объем кода, который получится при решении этой "задачки", это не единицы и нули корректировать

SpotteR wrote:... может сразу весь трехтомник Кнута сюда запостишь?! Уж очень много инфы, которую преподают в универе и в литературе найти можно не напрягаясь.

Отличные примеры реализации различных алгоритмов есть

ЗДЕСЬ
Пожалуй, этот ресурс более понятен, чем Кнут, будет :wink:

Skok wrote:Щаз еще сяду и про города накатаю!.. Как время будет.

Привожу одно из возможных решений задачи про города. Мне понравилось, красиво написано

{ Бэк-трекинг: Города                                                      }
{--------------------------------------------------------------------------}
{                                                                          }
{    Входные данные: файл TOWN.IN в 1-й строке содержит  количество слов в }
{ наборе. Начиная  со второй строки  (по одному в строке) следуют названия }
{ городов (все буквы в названиях - заглавные).                             }
{                                                                          }
{    Выходные данные: 1-я строка TOWN.OUT содержит  длину максимальной це- }
{ почки. Начиная со второй строки идет вариант цепочки,  т.е. названия (по }
{ одному в строке) городов в порядке, который требуют условия игры.        }
{                                                                          }
{    Примечание: Список городов во входном файле не превышает 20.          }
{--------------------------------------------------------------------------}

program towns;          { "Города". Решение А.Никитина, Самара  }
const mnt         = 20; { максимальное количество слов на входе }
var   list,chain,store :array [1..mnt] of string; { для списка и цепочек }
      numin       :integer; { реальное количество слов на входе }
      pc          :integer; { Указатель на хвост цепочки }
      ml          :integer; { Длина наибольшей цепочки }
      sym         :char;    { Первичная буква для перебора }

procedure read_data; { Начальные установки и чтение данных }
var i : integer;
begin
     pc:=0; ml:=0; numin:=0;
     assign(input,'TOWN.IN'); reset(input);
     fillchar(chain,sizeof(chain),0);
     readln(numin);
     if (numin>mnt) then numin:=mnt;
     for i:=1 to numin do readln(list[i]);
     close(input);
end;
procedure write_results; { Запись результатов в файл }
var i : integer;
begin
     assign(output,'TOWN.OUT'); rewrite(output);
     writeln(ml);
     if (ml>0) then begin
        for i:=1 to ml do writeln(store[i]);
     end;
     close(output);
end;
procedure store_chain; { Запоминаем только более длинную цепочку }
var i:integer;
begin
     if (pc>ml) then begin
        store:=chain;
        ml:=pc;
     end;
end;
{ Возвращает указатель названия по 1-й букве, 0 - такого элемента нет }
function find_next_item( c:char; n:integer ):integer;
var i:integer;
begin
    i:=1; find_next_item:=0;
    while (i<=numin) and (n>0) do begin
       if (list[i][1]=c) then dec(n);
       inc(i);
    end;
    if (n=0) then find_next_item:=pred(i);
end;
{ Алгоритм построения цепочек. }
procedure build_chain( c:char; n:integer ); { Метод: перебор с возвратом.  }
var i:integer;                              { Известен как "back-tracking" }
begin
    i:=find_next_item(c,n);
    if (i>0) then begin
       inc(pc); chain[pc]:=list[i]; list[i][1]:='X'; { вычеркиваем }
       build_chain(list[i][length(list[i])], 1);
       dec(pc); list[i][1]:=c; { возвращаем }
       build_chain(c, n+1);
    end else store_chain;
end;

begin
     read_data;
     for sym:='А' to 'Я' do build_chain(sym,1);
     write_results;
end.

Кому был должен пиво, всем прощаю

SpotteR wrote:Но задача серьезная. Ее кодить надо не один час. А этих часов то и нету совсем
Ты сам то представляешь объем кода, который получится при решении этой "задачки", это не единицы и нули корректировать

Мне все-же кажется, что кода здесь много не будет. Если, конечно, не разводить теорию, как OraCool, и не модифицировать дерево, чего вовсе не требуется...

Нужно просто подниматься по дереву от листьев к корню и оставлять вершины, пока это возможно, а иначе выкидывать. Почему этот жадный алгоритм всегда дает оптимальное решение здесь уже объяснили. Единственная проблема может возникнуть с выбором структуры данных для хранения дерева — при существующих ограничениях алгоритм над этой структурой должен работать за линейное время. Если использовать коллекции, то решения можно и не дождаться даже на самом быстром компе...

SpotteR wrote:Ты сам то представляешь объем кода, который получится при решении этой "задачки", это не единицы и нули корректировать

Ну, имея под рукой "быстрый" Интернет, :wink: найти необходимые шаблоны классов на C++ и примеры реализации N-арного дерева сегодня не проблема. Например, реализация контейнера для дерева есть

ЗДЕСЬ, ЗДЕСЬ или ЗДЕСЬ, а вот и

ПРИМЕР ЕГО ИСПОЛЬЗОВАНИЯ. Почему именно STL-like, смотрите в интервью А.Степанова на страницах

сайта Кембриджского Университета

Кстати, в

boost есть Boost Graph Library, где дерево - просто частный случай графа.

Ну мы Кембриджей то не кончали, нам бы чего по-проще

ВОТ пример реализации трёх классов в стиле STL от HongKong-ского товарища по имени Jack Hui:

Он за пару дней научился не только красиво обходить N-арное дерево, начиная как с корня, так и с листьев, но и удалять из него поддеревья функцией DelSubTree(), что нам и было нужно. При этом велосипед можно не изобретать

Admin wrote:...при существующих ограничениях алгоритм над этой структурой должен работать за линейное время. Если использовать коллекции, то решения можно и не дождаться даже на самом быстром компе...

Чтобы существенно сэкономить память, можно предложить вместо классических алгоритмов обхода дерева с использованием стека (который, как известно, не резиновый

) использовать автоматный подход. Про SWITCH-технологии я уже писал

ЗДЕСЬ, на сон грядущий можно полистать также 1 том Д.Кнута "Искусство программирования". Дерево представляем в следующем виде:

где K — константа, c — массив, хранящий указатели на детей.

Обход K-арного дерева на основе автомата с четырьмя состояниями при произвольном значении K может выглядеть примерно так:

Подробнее читайте на сайте

САНКТ-ПЕТЕРБУРГСКОГО ГОСУДАРСТВЕННОГО УНИВЕРСИТЕТА ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ, где опубликована прекрасная статья "Обход деревьев на основе автоматного подхода".

"Воистину, тщеславие — мой самый любимый из грехов... он так фундаментален..." (с) "Адвокат дьявола"

Может все-таки без лишних академических наворотов решим поставленную практически школьную задачу на любом языке программирования и продемонстрируем откомпилированный код?

Мне кажется что "примеры кода" сильно общая тема у нас получилась
Давайте разделим ее на две
1 "Интересные задачки " здесь будут задачки и красывые решения
2 "Алгаритмы" где будем говорить о деревьях, графах и тп
Если все за , то давайте рассортируем, чтоб не путаться

Dim77 wrote:Давайте разделим ее на две

Проблема в том, что любая "интересная задачка" должна сначала получить алгоритмическое решение. Как их делить, кодировать без описания алгоритма что-ли?

Admin wrote:"Воистину, тщеславие — мой самый любимый из грехов... он так фундаментален..." (с) "Адвокат дьявола"

Раз никто простого решения до сих пор не предложил, можно еще повыпендриваться

Dim77 wrote:Как лучше это дерево хранить, и как обход этих поддеревьев лучше делать ?

Почему бы нам не хранить это M-клятое дерево в обычной базе данных?

Заведем две таблицы: вершин и связей. Таблица вершин будет состоять из следующих четырех полей:

Номер дерева. Числовое поле, в котором для каждой вершины хранится номер дерева, к которому она принадлежит.

Номер вершины. Автоматически присваивается каждой вновь добавляемой записи таблицы самой СУБД. В MS Access этому полю соответствует тип Счетчик, а в MS SQL Server — тип IDENTITY с начальным значением 1 и приращением 1.

Числовое поле тип может принимать следующие значения: 1 — корневой элемент, 0 — ветка, 2 — листовой элемент.

Информационное поле. Одно или несколько полей представляют содержимое каждой отдельной вершины. Типы этих полей соответствуют информации, которую в них собираются хранить.

Таблица связей пусть состоит из трех полей: номер предка; номер потомка и номер связи - уникальный номер, присваиваемый каждой вновь добавляемой связи самой СУБД, который необходим для связей с другими таблицами. Присутствие последнего поля сокращает размер SQL-запроса: вместо «t1.НомерПредка = t2.НомерПредка AND t1.НомерПотомка = t2.НомерПотомка» нужно будет написать «t1.НомерСвязи = t2.НомерСвязи».
В таблице связей будет ограничение: в поле номер потомка не бывает повторяющихся номеров.
Реляционная модель для хранения деревьев готова!

Если вспомнить

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

Главному оппозиционеру задаем тип 1 (корень дерева) и информационное поле 0, ни в чем неповинным новичкам без подчиненных - тип 2 (лист), а руководящим членам партии - тип 0 (ветка). Заполнить остальные информационные поля в таблице узлов из строки с номерами непосредственных руководителей, надеюсь, для вас не проблема :wink:

Далее можно выбирать связанные по полю данные за один SQL-запрос, например, оракловым CONNECT BY. Подробнее читайте

ЗДЕСЬ

Наверно сколько программистов столько и решений задачке

Я удивляюсь как это люди до таких интересных методов решений доходят.
Вот мне тяжело выйти за граници того решения, которое мне уже сказали :-/, и придумать что то свое сильно отличающееся

Dim77 wrote:Я удивляюсь как это люди до таких интересных методов решений доходят

"Чтобы найти истину, каждый должен хоть раз в жизни освободиться от усвоенных им представлений и заново построить систему своих взглядов." (c) Рене Декарт

Зашел на сайт :
http://firststeps.narod.ru/theory/c/i1.html
И просто был удивлен там набор статей "Идиомы и стили С++", аж душа радуется , замечательные подходы описаны коротко и понятно , так что любители С++ и действительно изящных подходов не пропускайте !

ЗЫ Сейчас читаю оторватся немогу

Чего то тут так все затихло ...

OraCool давай еще задачку !!! Только не сильно сложную , чтоб своими мозгами можно было додуматся на часа 2-3 !
Ато желание есть решить чего нибудь , а задачек нету

Dim77 wrote:...давай еще задачку !!! Только не сильно сложную , чтоб своими мозгами можно было додуматся на часа 2-3 !

Главное здесь IMHO решать не быстро "на коленке", а сделать красиво

Ну попробуй, к примеру, pазбить исходный текст в виде одной длинной стpоки на массив стpок фиксиpованной максимальной шиpины с пеpеносом pусских слов по пpавилам оpфогpафии (я не садист, не обязательно на 100% пpавильно

). Язык программирования по-прежнему любой. Посмотрим, у кого лучше получится