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
:
В наши намерения на входит демонстрация изощренных методов или алгоритмов, поэтому ни один из них на рисунке не показан. Тем не менее обратите внимание на то, что мы не упоминаем о данных, которые хранятся в узлах (элементах списков). Оглядываясь на функции-члены этой структуры, мы видим, что сделали нечто подобное, определяя пару абстрактных классов
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 */
