Последовательное представление. Применение последовательно-распределенного представления на примере работы со стеком

Пусть элементами списка являются записи типа struct MY_BOOKS. В качестве абстрактного представления списка применим следующую запись:

struct BASE {

unsigned maxlen;

unsigned curlen;

struct MY_BOOKS list [baseListRange];

};

typedef struct BASE T_LIST;

где baseListRange – константа, определяющая число элементов массива, используемого для размещения элементов списка, maxlen – предельное максимальное число элементов (должно быть равно baseListRange), сurlen – текущее число элементов в списке, list – собственно массив, используемый для размещения элементов списка. Приведенное выше абстрактное представление списка хорошо тем, что позволяет совместно разместить все необходимые для реализации элементы, сокращая тем самым число параметров для функций, которые разрабатываются для реализации операций над списком. Аналогичное представление можно применить для очередей и стеков.

Рассмотрим как может быть реализована функция-конструктор списка в heap-памяти.

T_LIST * mk_list (void)

{

T_LIST * listptr;

if ((listptr = (T_LIST *) malloc (sizeof(T_LIST))) != NULL)

{

listptr -> maxlen = baseListRange;

listptr -> curlen = 0;

}

return listptr;

}

Функция возвращает NULL, если не удается разместить данные типа T_LIST в heap-памяти.

Рассмотрим каким образом может быть представлена функция получения доступа к i-му элементу списка. Реализация такой функции очевидна.

struct MY_BOOKS * getElFrom(T_LIST * listptr, unsigned i)

{

if (listptr -> curlen >= i)

return &listptr -> list[i];

else

return NULL;

}

Последовательное представление может быть реализовано применением более гибкой организации структурных связей. В этом случае можно говорить о последовательно-распределенном представлении сложных структур данных. Вместо непосредственного хранения элементов в массиве, в массиве размещаются указатели на них. Реализация такой операции как удаление элемента из середины списка, или добавление элемента в начало списка и ряда других становится более эффективной, поскольку реорганизация массива требует перемещения указателей, но не самих элементов, содержащихся в списке. Описываемый подход, также, необходим в том случае, если элементы списка или очереди должны размещаться еще и в других списках или очередях.

Рассмотрим применение последовательно-распределенного представления на примере работы со стеком. В рассматриваемых ниже примерах стек размещается в heap-памяти. В процессе добавления элементов в стек, если происходит переполнение массива хранения указателей на элементы, происходит реорганизация массива – число его ячеек увеличивается в 2 раза.

struct distrBase {

unsigned maxlen;

unsigned curlen;

MY_BOOKS ** lptr;

};

typedef struct distrBase T_HSTACK;

Здесь maxlen – максимальное число элементов в массиве хранения, curlen – текущее число элементов (позволяет точно адресоваться к верхушке стека), lptr – указатель на массив указателей.

Функцию-конструктор стека в heap-памяти можно представить следующим образом:

T_HSTACK * mk_stack(void)

{

T_HSTACK * ptr1 = NULL;

MY_BOOKS ** ptr2;

if ((ptr2 = (MY_BOOKS **) malloc(sizeof(struct MY_BOOKS *)*baseListRange))!= NULL)

{

if ((ptr1 = (T_HSTACK *) malloc(sizeof(T_HSTACK)) != NULL)

{

ptr1 -> maxlen = baseListRange;

ptr1 -> curlen = 0;

ptr1 -> lptr = ptr2;

}

else

free(ptr2);

};

return ptr1;

}

baseListRange является константой, которая должна быть определена в программе с помощью утверждения препроцессора #define. Из определения функции mk_stack() видно, что массив ссылок не встроен в структуру данных T_HSTACK, - в ней содержится ссылка на этот массив.

Рассмотрим операцию записи элемента данных в стек. Функция pushInto возвращает NULL, если выполнение операции невозможно или возвращает ссылку на стек, если операция была выполнена.

T_HSTACK * pushInto(T_HSTACK *stack, MY_BOOKS *el)

{

MY_BOOKS ** ptr;

unsigned size, enum;

size = stack -> maxlen;

enum = stack -> curlen;

if (size > enum)

stack -> lptr [enum] = el;

else

{ // динамич. увеличение стека

if((ptr = (MY_BOOKS **) calloc(2*size, sizeof(MY_BOOKS *))) != NULL)

{

//копирование указателей

copy(ptr, stack -> lptr, size);

ptr[size] = el;

stack -> maxlen = 2*size;

free(stack -> lptr);

stack -> lptr = ptr;

}

else

return NULL;

}

stack -> curlen++;

return stack;

}

Функция copy выполняет копирование указателей числом size из массива указанного вторым аргументом в массив указанный первым аргументом. Эту функцию запрограммируйте в качестве упражнения.