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

void init(struct List* lst); /* инициализирует lst пустым */

struct List* create();       /* создает новый пустой список

                                в свободной памяти */

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

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

                                   а затем удаляет сам lst */

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

                                  элемент p в конец списка lst */

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

                                  в начало списка lst */

/* вставляет элемент q перед элементом p in lst: */

void insert(struct List* lst, struct Link* p, struct Link* q);

struct Link* erase(struct List* lst, struct Link* p); /* удаляет

                                         элемент p из списка lst */

/* возвращает элемент, находящийся за n до или через n узлов

   после узла p:*/

struct Link* advance(struct Link* p, int n);

Мы хотим определить эти операции так, чтобы их пользователям было достаточно использовать только указатели

List*
и
Link*
. Это значит, что реализации этих функций можно кардинально изменять, не влияя на работу их пользователей. Очевидно, что выбор имен был сделан под влиянием библиотеки STL. Структуры
List
и
Link
можно определить очевидным и тривиальным образом.

struct List {

  struct Link* first;

  struct Link* last;

};

struct Link { /* узел двухсвязного списка */

  struct Link* pre;

  struct Link* suc;

};

Приведем графическое представление контейнера

List
:

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

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

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

Для реализации функций структуры

List
сначала включаем некоторые стандартные библиотечные заголовки.

#include<stdio.h>

#include<stdlib.h>

#include<assert.h>

В языке C нет пространств имен, поэтому можно не беспокоиться о декларациях или директивах

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

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

assert()
.

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

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

{

  assert(lst);

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

}

Мы решили не связываться с обработкой ошибок, связанных с некорректными указателями на списки, во время выполнения программы. Используя макрос

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

Функция

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 */