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

Страуструп Бьерн

Определим двухсвязный список с девятью операциями.

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

{

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