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


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



struct list
{
list *next;
void *data;
};
int count(list *p[])
{
int k,cnt; // Цикл по массиву заголовков списков


for (cnt=0, k=0; p[k]!=NULL; k++)
{
list *q; // Цикл по списку


for (q=p[k]; q!=NULL; q=q-&#62next)
cnt++;
}
return cnt; }



-двухуровневый массив указателей


void **p[20]; // массив указателей


// на массивы указателей


int count(void **p[])
{
int k,cnt; // Цикл по массиву верхнего уровня


for (cnt=0, k=0; p[k]!=NULL; k++)
{
int i; // Цикл по массиву нижнего уровня


for (i=0; p[k][i]!=NULL; i++)
cnt++;
}
return cnt; }

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

Особенности работы с иерархическими структурами данных рассмотрим на примере двухуровневого массива указателей :



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



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



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




//------------------------------------------------------bk57-01.cpp




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



Книжный магазин