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

       

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


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



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



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



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

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



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


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



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



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




// Двухуровневый массив указателей на целые .

&#35include &#60iostream.h&#62
&#35include &#60string.h&#62
&#35define N 4
int **p[20]={NULL}; // Двухуровневый массив указателей на целые

// Исходное состояние массивов нижнего уровня нет

int size(int *p[]) // Количество элементов в массиве указателей

{ for (int i=0; p[i]!=NULL; i++); return i; }

void show(int **p[]) // Обход структуры данных со сквозной нумерацией

{ int i,j,k;
for (i=0,k=0; p[i] != NULL; i++)
for (j =0; p[i][j] != NULL; j++,k++)
cout &#60&#60 k &#60&#60 " " &#60&#60 i &#60&#60 " " &#60&#60 j &#60&#60 " " &#60&#60 *p[i][j] &#60&#60 endl;
}

// Включение в массив указателей нижнего уровня по номеру.

// Проверка на переполнение

int F3(int *p[], int *q, int n)
{
int i,m=size(p);
for (i=m; i&#62=n; i--) p[i+1] = p[i];
p[n] = q;
return m+1==N;
}

// Включение по логическому номеру. Для каждого массива указателей

// нижнего уровня из логического номера вычитается количество

// указателей в текущем массиве, пока не будет найден тот,

// в который попадает новый указатель.

void F117(int **p[],int *q, int n)
{ int i,j,l,sz;
if (p[0]==NULL) // Отдельная ветка для пустой структуры данных

{
p[0]=new int*[N+1];
p[0][0]=q;
p[0][1]=NULL;
return;
} // Поиск места включения

for (i =0; p[i] != NULL; i++,n-=sz)
{
sz=size(p[i]); // Количество указателей в массиве

if (n&#60=sz) break; // Номер попадает в текущий массив

} // Не найден включить последним

if (p[i]==NULL) { i--; n=size(p[i]); }
if (F3(p[i],q,n)) // Вызов функции включения для нижнего уровня

{ // Переполнение создание нового массива

// Раздвижка в массиве указателей верхнего уровня

// Создание нового массива нижнего уровня

// Перенос указателей

for (int ii=0; p[ii] != NULL; ii++);
for(int h=ii;h&#62i;h--) p[h+1]=p[h];
p[i+1]=new int*[N+1];
for(j=0;j&#60N/2;j++) p[i+1][j]=p[i][j+N/2];
p[i][N/2]=NULL;
p[i+1][N/2]=NULL;
}
}

void main()
{while(1)
{
int n, *s=new int;
cin &#62&#62 *s &#62&#62 n;
if (n&#60 0) break;
F117(p,s,n);
show(p);
}}


Содержание раздела