Реализация иерархических списков

В разделе 2.6. приводилась рекурсивная реализация линейных списков. Для иерархических списков можно выполнить аналогичную реализацию, но для этого потребуется несколько усложнить внутреннюю структуру данных. Поскольку каждый элемент может быть или значением базового типа, или указателем на список, наилучшим решением для языка С++ является использование типа union (объединение), которое позволяет использовать одну и ту же область памяти для хранения данных разных типов (в нашем случае базовый тип и тип указатель). Для того, чтобы отличать атомы от указателей на список, для каждого элемента вводим дополнительное поле логического типа, в котором будем хранить признак, является ли данное поле атомом (без него не обойтись).

Таким образом, каждый элемент будет являться структурой (struct), состоящей из двух частей — признака атомарности (тип bool) и непосредственно определения элемента (тип union).

struct list

{ bool atomic; // признак атомомарности

union // определение списка (атом или пара «голова-хвост»)

{ type_of_data atm;

struct head_tail

{ list *list_h, *list_t;

} pair;

};

~list()//деструктор, введен для освобождения памяти

{ if (!atomic)

{ delete pair.list_h;

delete pair.list_t;

}

}

};

Выделение памяти под элемент списка будет выполняться в функции makeatom.

Заметим, что в языке Pascal для реализации иерархического списка удобно использовать записи с вариантами (case внутри определения record - аналог union).

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

bool isnull(list *l) //возвращает true, если список пустой

{ return (l==NULL);

}

bool isatom(list *l) //возвращает true, если список атомарный

{ if (isnull(l)) return false;

return l->atomic;

}

list *head(list *l) // возвращает указатель на голову

{ if (isnull(l)) { cerr<<"пустое S-выражение"; exit(1); }

if (isatom(l)) { cerr<<"атомарное S-выражение"; exit(2); }

return l->pair.list_h;

}

list *tail(list *l) // возвращает указатель на хвост

{ if (isnull(l)) { cerr<<"пустое S-выражение"; exit(3); }

if (isatom(l)) { cerr<<"атомарное S-выражение "; exit(4); }

return l->pair.list_t;

}

list *makeatom(type_of_data x) //создает атомарный список

{ list *temp=new list;

temp->atomic=true; temp->atm=x;

return temp;

}

type_of_data getatom(list *l) //возвращает значение атома

{ if (!isatom(l)) {cerr<<"неатомарное S-выражение"; exit(5);}

return l->atm;

}

list *cons(list *l_head, list *l_tail) //создает список

{ if (isatom(l_tail)) { cerr<<"хвост - атом";exit(6);}

list *temp=new list; temp->atomic=false;

temp->pair.list_h=l_head; temp->pair.list_t=l_tail;

return temp;

}

В качестве примера применения базовых функций приведем дополнительные полезные функции для работы с иерархическими списками — соединение двух списков и вывод в сокращенной скобочной записи.

list *concat(list *l1, list *l2) // присоединение l2 к l1

{ if (isnull(l1)) return l2;

if (isatom(l1)) return cons(l1,l2);

return cons(head(l1),concat(tail(l1),l2));

}

void print(list *l) // вывод списка l

{ if (isnull(l)) {cout << endl; return;}

if (isatom(l)) cout<<getatom(l)<<" ";

else

{ if (isatom(head(l))) print(head(l));

else

{ cout<<"("; print(head(l)); cout<<") ";

}

print(tail(l));

}

}

Небольшая демонстрационная программа показывает работу с иерархическим списком, состоящим из целых чисел (при определении списка использовался оператор typedef int type_of_data).

main()

{ // для примера создаем список (1 (2 3) 4 5):

list *l=cons(makeatom(1), // голова

      cons(cons(makeatom(2),cons(makeatom(3),NULL)),//хвост

      cons(makeatom(4),cons(makeatom(5),NULL))));

print(l);

// соединяем исходный список со списком ((6 7)):

l=concat(l,cons(cons(makeatom(6),cons(makeatom(7),NULL)),NULL));

// образуется список (1 (2 3) 4 5 (6 7))

print(l); return 0;

}

Деревья и леса

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

В данной главе сосредоточим максимум внимания на общих свойствах деревьев и лесов как структур данных, которые будут использоваться при изучении следующих разделов. Для этого сначала рассмотрим их как абстрактные математические объекты, а затем перейдем к формальной функциональной спецификации и различным формам реализации.

Особый вид деревьев — бинарные — будут рассмотрены отдельно.

Определения

Когда речь идет об иерархических структурах, то под термином «дерево» обычно понимают дерево с корнем (корневое дерево). Однако заметим, что корневое дерево — это частный случай более общего определения дерева, называемого иначе свободным деревом. Свободные деревья, в свою очередь, являются частным случаем графов и определяются в терминах теории графов. Они будут рассмотрены позже. В данной главе будем рассматривать только корневые деревья, называя их просто деревьями.

Формально дерево можно рекурсивно определить следующим образом [8].

Дерево (tree) — конечное множество T одного или более узлов (nodes) со следующими свойствами:

1. Существует один выделенный узел, называемый корнем (root) этого дерева T. Дерево может состоять и из одного корня.

2. Остальные узлы (если они есть) распределены среди k непересекающихся множеств T1, Т2,..., Tk, и каждое их этих множеств, в свою очередь, является деревом. Деревья T1, Т2,..., Tk называются поддеревьями (subtrees) этого корня.

Из этого определения следует, что каждый узел дерева является корнем некоторого другого дерева (поддерева).

Совокупность нескольких непересекающихся деревьев называется лесом (forest —иногда переводится как бор). Например, все потомки одного узла дерева образуют лес. Лес всегда можно преобразовать в дерево, добавив один единственный корневой элемент и связав его с корнями всех деревьев, из которых состоит лес. Поэтому лес и дерево — это два неразрывно сязанных понятия. Для того, чтобы подчеркнуть общность этих понятий, лес из n деревьев иногда называют деревом с n-кратным корнем.

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