Информатика и технология программирования


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


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



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



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



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

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



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


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; }



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




Начало  Назад  Вперед