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


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



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


&#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);
}}




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