Массив указателей
Объект - массив указателей - должен содержать динамический массив указателей на элементы данных, его размерность может задаваться при конструировании объекта и должна автоматически увеличиваться при переполнении. Массив указателей содержит "плотную" (без "дырок") последовательность указателей, ограниченную NULL.
class MU
{
int sz; // Текущая размерность МУ
void **p; // Динамический МУ на элементы
// данных произвольного вида
int extend(); // Увеличить размерность МУ
public:
MU(int); // Конструктор - создание МУ
~MU(); // Деструктор
int size(); // Количество элементов данных
void *operator[](int); // Извлечение по логическому номеру
int operator()( void*,int);
// Включение по логическому номеру
void *remove(int); // Удалить по логическому номеру
void *min( int(*)(void*.void*));
// Итератор поиска минимального
};
Конструктор создает динамический массив указателей размерности, заданной параметром и "очищает" его. Деструктор, естественно, разрушает динамический массив указателей . С элементами данных при этом ничего не происходит, поскольку структура данных осуществляет только их хранение и не отвечает за процессы их создания и уничтожения. Метод extend() создает новый массив указателей, размерностью в два раза больше и переписывает в него указатели из "старого".
MU::MU(int n=20)
{ sz=n; p=new void*[n]; p[0]=0; }
MU::~MU()
{ delete p; }
int MU::extend()
{
void **q=new void*[sz*2];
if (q==NULL) return 0;
for (int i=0; i<sz; i++) q[i]=p[i];
delete p;
sz*=2;
return 1;
}
Остальные операции представляют собой классическую реализацию алгоритмов работы с массивом указателей, выполненную в виде методов класса - переопределенных операций.
int MU::size()
{ int i; for (i=0; p[i]!=NULL; i++); return i; }
void *MU::operator[](int n=-1)
{ // Извлечение по логическому номеру
int k=size(); // По умолчанию - последний
if (n==-1) n=k-1;
if (n< 0 || n>=k) return NULL; // Недопустимый номер
return p[n];
}
int MU::operator()(void *q, int n=-1)
{ // Включение по логическому номеру
int k=size();
if (n==-1) n=k; // По умолчанию - последним
if (n< 0 || n>k) return 0; // Недопустимый номер
if (k==sz-1) extend(); // При переполнении - увеличить размерность
for (int i=k; i>=n; i--) p[i+1]=p[i];
p[n]=q;
return 1;
}
void *MU::remove(int n=-1) // Удалить по логическому номеру
{
int k=size();
if (n==-1) n=k-1; // По умолчанию - удалить последний
if (n< 0 || n>=k) return NULL;
void *q=p[n];
for (;p[n]!=NULL; n++) // "Уплотнить" массив указателей
p[n]=p[n+1];
return q;
}
void *MU::min( int (*cmp)(void*,void*))
{ // Итератор поиска минимального
void *pmin;
int i;
for (i=0, pmin=p[0]; p[i]!=NULL; i++)
if ( (*cmp)(pmin,p[i]) > 0) pmin=p[i];
return pmin;
}
