Программирование. Принципы и практика использования C++ Исправленное издание

В наши намерения на входит демонстрация изощренных методов или алгоритмов, поэтому ни один из них на рисунке не показан. Тем не менее обратите внимание на то, что мы не упоминаем о данных, которые хранятся в узлах (элементах списков). Оглядываясь на функции-члены этой структуры, мы видим, что сделали нечто подобное, определяя пару абстрактных классов Link и List. Данные для хранения в узлах будут предоставлены позднее. Указатели Link* и List* иногда называют непрозрачными типами (opaque types); иначе говоря, передавая указатели Link* и List* своим функциям, мы получаем возможность манипулировать элементами контейнера List, ничего не зная о внутреннем устройстве структур Link и List.

Для реализации функций структуры List сначала включаем некоторые стандартные библиотечные заголовки.

#include

#include

#include

В языке C нет пространств имен, поэтому можно не беспокоиться о декларациях или директивах using. С другой стороны, мы должны были бы побеспокоиться о слишком коротких и слишком популярных именах (Link, insert, init и т.д.), поэтому такой набор функций нельзя использовать в реальных программах.

Инициализация тривиальна, но обратите внимание на использование функции assert.

void init(struct List* lst) /* инициализируем *lst

                               пустым списком */

{

  assert(lst);

  lst–>first = lst–>last = 0;

}

Мы решили не связываться с обработкой ошибок, связанных с некорректными указателями на списки, во время выполнения программы. Используя макрос assert, мы просто получим сообщение о системной ошибке (во время выполнения программы), если указатель на список окажется нулевым. Эта системная ошибка просто выдаст нам имя файла и номер строки, если будет нарушено условие, указанное как аргумент макроса assert; assert — это макрос, определенный в заголовочном файле , а проверка доступна только в режиме отладки. В отсутствие исключений нелегко понять, что делать с некорректными указателями.

Функция create просто создает список List свободной памяти. Она напоминает комбинацию конструктора (функция init выполняет инициализацию) и оператора new (функция malloc выделяет память).

struct List* create /* создает пустой список */

{

  struct List* lst =

         (struct List*)malloc(sizeof(struct List));

  init(lst);

  return lst;

}

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

void clear(struct List* lst) /* удаляет все элементы списка lst */

{

  assert(lst);

  {

  struct Link* curr = lst–>first;

  while(curr) {

    struct Link* next = curr–>suc;

    free(curr);

    curr = next;

  }

  lst–>first = lst–>last = 0;

  }

}

Обратите внимание на способ, с помощью которого мы обходим список, используя член suc класса Link. Мы не можем получить безопасный доступ к члену объекта после его удаления с помощью функции free, поэтому ввели переменную next, с помощью которой храним информацию о своей позиции в контейнере List, одновременно удаляя объекты класса Link с помощью функции free.

Если не все объекты структуры Link находятся в свободной памяти, лучше не вызывать функцию clear, иначе она вызовет разрушение памяти.

Функция destroy, по существу, противоположна функции create, т.е. она представляет собой сочетание деструктора и оператора delete.

void destroy(struct List* lst) /* удаляет все элементы списка lst;

                                  затем удаляет сам список lst */

{

  assert(lst);

  clear(lst);

  free(lst);

}

Обратите внимание на то, что перед вызовом функции очистки памяти (деструктора) мы не делаем никаких предположений об элементах, представленных в виде узлов списка. Эта схема не является полноценной имитацией методов языка С++ — она для этого не предназначена.

Функция push_back — добавление узла Link в конец списка — вполне очевидна.

void push_back(struct List* lst, struct Link* p) /* добавляет элемент p

                                                    в конец списка lst */

{

  assert(lst);

  {

    struct Link* last = lst–>last;

    if (last) {

      last–>suc = p;  /* добавляет узел p после узла last */

      p–>pre = last;

    }

    else {

      lst–>first = p; /* p — первый элемент */

      p–>pre = 0;

    }