Дерево

[Dvach]

Доброго времени суток, есть такая проблема: нужно реализовать дерево на паскале, в котором будут звенья с разным количеством указателей в зависимости от количества потомков. Элемент дерева должен иметь тип записи (Record) . Мне не понятно как сделать так чтобы количество полей в записи было не фиксированным(замечу что тут иметься ввиду не нулевые указатели а именно отсутствие указателя). В голову пришла только одна идея это динамический массив внутри записи. Как то так:

Type
  NodePointer = ^Node;
  Node = record
    data : byte;
    count : integer;
    parent : NodePointer;
    child : array of NodePointer;
  end;

Но при попытке выделить память для типизированного указателя типа NodePointer вылазит ошибка:
Ошибка времени выполнения: Невозможно упаковать тип "ByProCoder.Node" как неуправляемую структуру; невозможно вычислить размер или смещение, имеющие смысл.
Я так полагаю это потому что неизвестно какой объем памяти выделить на динамический массив. Как решить эту проблему?

[Stilet]

звенья с разным количеством указателей в зависимости от количества потомков.

А для чего? Зачем такая динамика? Что там такого хранить будут неожиданного?

[Dvach]

Сообщение от Stilet

А для чего? Зачем такая динамика? Что там такого хранить будут неожиданного?

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

http://pixs.ru/showimage/shemapng_2013252_14653489.png
вот схема такого дерева для примера

[Stilet]

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

Type
  NodePointer = ^Node;
  Node = record
    data : pointer;
    count : integer;
    TypeOfData:byte;
    parent, //Это указатель на родителя
    children, // Это указатель на список детей
    Sibling :NodePointer; //Это указатель на следующий элемент в этом списке
  end;

Т.е. NodePointer это не просто указатель а голова списка.
И так получится список списков с данными неопределенного типа

[Dvach]

Не совсем понятно что имееться ввиду , но насколько я понял вы добавили указатель еще на следующий элемент на этом же уровне дерева (брат) , это противоречит варианту задания. Вот условие более подробно:
Каждая вершина содержит следующие поля:
- поле данных;
- поле, в котором указано число координирующих вспомагательных полей;
- вспомагательное поле, содержащее указатель на вершину более высокого уровня (предыдущую вершину). Для корневой вершины в него заносится значение NIL;
- вспомагательные поля, содержащие указатели на вершины нижнего уровня (у листьев - отсутствуют).
Если с текущей вершиной не связаны вершины нижнего уровня, то соответствующие вспомогательные поля отсутствуют

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

[Stilet]

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

Пичальная какашка...
Ладно. Пусть будет array of NodePointer.
Смысл собственно в описании данных. Вот я и предлагаю их представить нетипированно, но с указанием как именно их понимать.

[Utkin]

Самый простой вариант - уйти от ссылок. Все узлы элементы динамического массива. Начинается от глобального корневого узла, который недоступен конечному пользователю. Его потомки будут считаться корневыми узлами. Такое проектирование дерева поможет избежать многих проблем, главная из которых утечка памяти при работе с указателями.
В случае использования только динамических массивов в Вашем рекорде count становится не нужным...

вот схема такого дерева для примера

Примитивизм. Отделите реализацию от модели. Иначе долго будете искать баги.

[Dvach]

Вот мне тоже нравиться идея с динамачиным массивом, но как выделить память для указателя на record если в нем есть динамический массив размер которого на данном этапе еще неизвестен, я ведь не могу выделить память под массив до того как выделю память для записи.
"Ошибка времени выполнения: Невозможно упаковать тип "ByProCoder.Node" как неуправляемую структуру; невозможно вычислить размер или смещение, имеющие смысл. "

[Utkin]

Вот мне тоже нравиться идея с динамачиным массивом, но как выделить память для указателя на record если в нем есть динамический массив размер которого на данном этапе еще неизвестен, я ведь не могу выделить память под массив до того как выделю память для записи.

Значит надо выделить после. Если такая вещь называется инициализация. Просто подготовите функцию, которая и будет выполнять работу с выделением памяти под динамический массив нужного размера. Для примера:
1. Начальная инициализация
SetLength(массив, размер) - установите размер в нуль, уничтожите все данные.
2. Добавить элемент в конец:

count:=Length(массив);
Inc(count);
SetLength(Массив, count);

3. Удаление элемента
а) Копируете последний элемент в тот который должен быть удален
б) Уменьшаете динамический массив на единицу

Dec(count);
SetLength(Массив, count);

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

[Dvach]

Сообщение от Utkin

Значит надо выделить после. .

1) Нельзя после, так ошибка при выделении памяти под типизированный указатель (размер динамического массива внутри не опеределен)
2) Ну про SetLength я знаю , вот только где мне выделять память под массив? в отдельной функции? и как мне передать указатель в record. Это ведь не экземпляр класса и я не могу вызвать конструктор при выделении памяти под узел.
Я конечно могу описать узел как объект а не запись но это уже не совсем то что требуется в задании.