Иерархические структуры данных
Даже беглый обзор структур данных позволяет сделать вывод, что идеальной структуры данных не существует: каждая имеет свои достоинства и недостатки. Попробуем оценить их с точки зрения возможности хранения упорядоченного множества переменных, включения, исключения и ускоренного поиска:
-массивы указателей позволяют производить упорядочение элементов путем сортировки указателей на них, после чего в нем возможен двоичный поиск. Недостатком является необходимость перераспределения памяти под массив указателей при увеличении их количества, а также перемещение указателей при включении и исключении элементов;
-список позволяет поддерживать естественное упорядочение элементов путем соответствующих манипуляций с указателями при произвольном количестве элементов. Недостатком является исключительно линейный поиск;
-двоичное дерево не имеет проблем, связанных с увеличением размерности, имеющих место у массивов указателей. Кроме того, естественным образом организован двоичный поиск. Недостатком является необходимость поддержки сбалансированности.
При возрастании объема хранимых данных затраты на выполнение операций выделения и перемещения отдельных элементов сильно возрастают. Очевидно, что уменьшить их можно, введя в структуру данных иерархию. Для этого можно вложить в элемент одной структуры данных заголовок другой структуры. В этом случае все алгоритмы работы с такой структурой данных содержат соответствующие вложенные один в другой фрагменты (например, циклы) для работы с каждой из них. Рассмотрим некоторые примеры :
-список, элемент которого содержит массив указателей
struct elem // Элемент односвязного списка
{
elem *next;
void *pp[20]; // Массив указателей на элементы данных
};
// Подсчет количества элементов в структуре данных
int count(elem *p)
{
elem *q; int cnt; // Цикл по списку
for (cnt=0, q=p; q!=NULL; q=q->next)
{
int i; // Цикл по массиву указателей
for (i=0; q->pp[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->next)
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
// Двухуровневый массив указателей на целые .
#include <iostream.h>
#include <string.h>
#define 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 << k << " " << i << " " << j << " " << *p[i][j] << endl;
}
// Включение в массив указателей нижнего уровня по номеру.
// Проверка на переполнение
int F3(int *p[], int *q, int n)
{
int i,m=size(p);
for (i=m; i>=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<=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>i;h--) p[h+1]=p[h];
p[i+1]=new int*[N+1];
for(j=0;j<N/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 >> *s >> n;
if (n< 0) break;
F117(p,s,n);
show(p);
}}
