Иерархические структуры данных - часть 3
// Двухуровневый массив указателей на целые .
#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);
}}