Структуры данных с элементами произвольных типов
Для того, чтобы массив указателей, список или дерево были универсальны, необходимо обеспечить независимость работы с "системной" частью. Тогда не потребуется переписывать функции, работающие со структурой данных, включающей элементы одного типа для работы с элементами другого типа. Эта задача может быть решена двумя способами:
-в первом -"системная" и "прикладная" части структуры данных разделяются на отдельные переменные и связываются через указатель. Поскольку при работе с "системной" частью "прикладная" является неопределенной (произвольной), то такой указатель будет иметь тип void*. Но тогда при работе с "прикладной" частью потребуется преобразовать указатель void* к конкретному типу указателя на "прикладную" часть, и обратно. В "классическом" Си это может производиться по умолчанию, сопровождаясь предупреждением транслятора, в Си++ это должно быть сделано явно;
-во втором -"системная" и "прикладная" части соединены в каждом элементе структуры данных, при этом первая всегда предшествует второй. Функции, работающие с "системной" частью, используют тип элемента, в котором "прикладная" часть отсутствует.
При вызове функций, работающих с "системной" частью, производится явное преобразование типа указателя, по которому передается элемент структуры данных.
В обоих случаях текущий размер "прикладной" части не известен функциям, работающим с "системной" частью, поэтому процедуры создания и уничтожения элементов данных должны быть реализованы вне этих функций.
В качестве примера рассмотрим набор функций для работы с односвязным списком (очередью) элементов произвольного типа и их использование для создания конкретных списков. В первом случае элемент списка содержит указатель типа void* на произвольный элемент данных.
//------------------------------------------------------bk57-02.cpp
struct list
{
struct list *next; // системная часть элемента
void *pdata; // указатель на прикладную часть
};
//----- Включение элемента в конец списка
list *insert (list *p h, void *pd)
{
list *p =new list)); // создать "системную" часть
p->next = NULL; // нового элемента списка
p->pdata = pd; // привязать "прикладную"
if (ph == NULL) // часть к "системной"
return p;
for (list *q=ph; q->next!=NULL; q=q->next);
q->next=p;
return ph;
}
//----- Исключение первого элемента ---------------------
void *exclude( list **ph)
{
list *p = *ph;
if (p==NULL) return NULL;
*ph = p->next;
void *pd = p->pdata;
delete p; // уничтожить системную часть
return pd;
}
//----- Работа с конкретным списком
void main()
{ int *pval, A[ 10] ={3,4,8,32,67,5,7,4,78,45};
list *PH=NULL; // пустой список
for (i=0; i< 10; i++)
{
pval=new int; *pval=A[i]; // создать переменную
PH=insert(PH, (void*) pval); // включение в список
} // с преобразованием типа
for (i=0; i< 10; i++)
{
pval = (int*)exclude( &PH); // исключение элемента
delete pval; // уничтожение элемента
}
}
Во втором случае используется подмена : функция, работающая с элементами списка типа list получает элементы типа list1 с совпадающей " системной" частью :
//------------------------------------------------------bk57-03.cpp
struct list
{
struct list *next; // системная часть элемента
};
// Включение элемента в конец списка ------------------
list *insert(list *ph, list *p)
{
if (ph == NULL) return p;
for (list *q=ph; q->next!=NULL; q=q->next);
q->next=p;
return ph;
}
//----- Исключение первого элемента ----------------------
list *exclude(list * *ph)
{
list *p;
if ( *ph == NULL) return NULL;
p = *ph; *ph=p->next;
return p;
}
//----- Работа с конкретным списком -----------------------
struct list1
{
struct list *next; // системная часть элемента
int value; // прикладная часть
} // элемента
*PH = NULL; // пустой список
void main()
{ list1 *pp;
for ( int i=0; i< 10; i++)
{
pp = new list1; // создание элемента
pp->value = i; // заполнение
PH=(list1*)insert((list*)PH,(list*)pp);
// включение в список -
// преобразование типа list1* - list*
}
for (i=0; i< 10; i++) // исключение элемента -
{ // преобразование типа list* - list1*
pp = (list1*)exclude((list**)PH);
delete pp;
}
}
Аналогичная картина наблюдается при работе с деревьями. В массиве указателей "системная" и "прикладная" части структуры данных связаны естественным образом по указателю, поэтому там возможен только первый вариант реализации.
