Шаблон иерархической структуры данных в памяти (односвязный список, содержащий статический массив указателей на объекты), страница 2

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

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

Структурное описание

Класс Telem() – предназначен  для работы с одним элементом списком.

Класс ClistArr() – предназначен для работы непосредственно со всем списком, т.к. список состоит из отдельных элементов, в этом классе производится описание методов, предназначенных для одного элемента списка.

Интерфейс класса шаблона имеет вид

#define     MAXN 4                        /* размер статического массива указателей на объекты */

/* интерфейс класса-шаблона */

template <class T>

class CListArr {

      struct TElem {                     /*  структура элемента односвязного списка*/

            T     *data[MAXN+1];          /* статический массив указателей */

            TElem *next;                  /* следующий элемент */

      };

      TElem *top;                         /* голова(вершина) списка */

      int   nelems;                       /* общее количество элементов списка */

public:

      CListArr() { top=NULL; nelems=0; } /* конструктор по умолчанию */

      ~CListArr();                            

      void Add(T elem);                  /* добавление элемента */

      int Insert(T elem, int k);         /* вставка элемента по номеру */

      T *Delete(int k);                  /* исключение элемента по номеру */

      T *Get(int k);                     /* получение элемента по номеру */

      void Sort();                       /* сортировка */

      void InsertKeepOrder(T elem);      /* вставка с сохранением порядка */

      int   LoadFile(char * filename);    /* загрузка из файла */

      void SaveFile(char * filename);    /* сохранение в файле  */

      void Balancing();                  /* балансировка */

private:

      int nElems(TElem *pelem);          /* подсчет количества занятых указателей массива в элементе списка */

      void FreeMemory();                 /* освобождение памяти */

};

Размер статического массива задается макросом MAXN (4).

Опишем каждую из представленных функций

Описание функций

Функция добавления элемента

void Add(T elem);

Входные данные: elem – добавляемый элемент

Выходные данные: нет

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

Функция вставки элемента по номеру

int Insert(T elem, int k);

Входные данные: elem – вставляемый элемент, k –логический номер

Выходные данные: 0 – в случае успеха, -1 – если элемент не вставлен (логический номер больше количества)