Иерархические структуры данных

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

-список позволяет поддерживать естественное упорядочение элементов путем соответствующих манипуляций с указателями при произвольном количестве элементов. Недостатком является исключительно линейный поиск;

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

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

-список, элемент которого содержит массив указателей

struct elem // Элемент односвязного списка

{
elem *next;
void *pp[20]; // Массив указателей на элементы данных

};

// Подсчет количества элементов в структуре данных

int count(elem *p)
{
elem *q; int cnt; // Цикл по списку

for (cnt=0, q=p; q!=NULL; q=q-&#62next)
{
int i; // Цикл по массиву указателей

for (i=0; q-&#62pp[i]!=NULL; i++)
cnt++;
}
return cnt; }

-массив, каждый элемент которого является заголовком списка