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

       

Структуры данных с элементами произвольных типов


Рассмотренные выше массивы указателей, деревья и списки представляют собой средства для хранения и упорядочения в памяти множеств различных объектов, представленных как самостоятельными переменными, так и частями структурированных переменных. При этом следует различать "системную" и "прикладную" части структуры данных. Первая обеспечивает связность и функционирование структуры данных, как таковой. Например, в списке "системной" частью является заголовок списка и указатели на соседние элементы. Хранимые в определенном порядке компоненты структуры данных, относящиеся к конкретной задаче, являются ее "прикладной" частью. Для обычного списка это будут все остальные элементы структуры ( struct ), представляющей элементы списка.

Для того, чтобы массив указателей, список или дерево были универсальны, необходимо обеспечить независимость работы с "системной" частью. Тогда не потребуется переписывать функции, работающие со структурой данных, включающей элементы одного типа для работы с элементами другого типа. Эта задача может быть решена двумя способами:



-в первом -"системная" и "прикладная" части структуры данных разделяются на отдельные переменные и связываются через указатель. Поскольку при работе с "системной" частью "прикладная" является неопределенной (произвольной), то такой указатель будет иметь тип 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-&#62next = NULL; // нового элемента списка

p-&#62pdata = pd; // привязать "прикладную"

if (ph == NULL) // часть к "системной"

return p;
for (list *q=ph; q-&#62next!=NULL; q=q-&#62next);
q-&#62next=p;
return ph;
}
//----- Исключение первого элемента ---------------------

void *exclude( list **ph)
{
list *p = *ph;
if (p==NULL) return NULL;
*ph = p-&#62next;
void *pd = p-&#62pdata;
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&#60 10; i++)
{
pval=new int; *pval=A[i]; // создать переменную

PH=insert(PH, (void*) pval); // включение в список

} // с преобразованием типа

for (i=0; i&#60 10; i++)
{
pval = (int*)exclude( &#38PH); // исключение элемента

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-&#62next!=NULL; q=q-&#62next);
q-&#62next=p;
return ph;
}
//----- Исключение первого элемента ----------------------

list *exclude(list * *ph)
{
list *p;
if ( *ph == NULL) return NULL;
p = *ph; *ph=p-&#62next;
return p;
}
//----- Работа с конкретным списком -----------------------

struct list1
{
struct list *next; // системная часть элемента

int value; // прикладная часть

} // элемента

*PH = NULL; // пустой список

void main()
{ list1 *pp;
for ( int i=0; i&#60 10; i++)
{
pp = new list1; // создание элемента

pp-&#62value = i; // заполнение

PH=(list1*)insert((list*)PH,(list*)pp);
// включение в список -

// преобразование типа list1* - list*

}
for (i=0; i&#60 10; i++) // исключение элемента -

{ // преобразование типа list* - list1*

pp = (list1*)exclude((list**)PH);
delete pp;
}
}

Аналогичная картина наблюдается при работе с деревьями. В массиве указателей "системная" и "прикладная" части структуры данных связаны естественным образом по указателю, поэтому там возможен только первый вариант реализации.


Содержание раздела