Программирование. Принципы и практика использования C++ Исправленное издание - Бьёрн Страуструп
Шрифт:
Интервал:
Закладка:
Для реализации функций структуры 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 */
{
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;
}
lst–>last = p; /* p — новый последний элемент */
p–>suc = 0;
}
}
Весь этот код было бы трудно написать, не нарисовав схему, состоящую из нескольких прямоугольников и стрелок. Обратите внимание на то, что мы забыли рассмотреть вариант, в котором аргумент p равен нулю. Передайте нуль вместо указателя на узел, и ваша программа даст сбой. Этот код нельзя назвать совершенно неправильным, но он не соответствует промышленным стандартам. Его цель — проиллюстрировать общепринятые и полезные методы (а также обычные недостатки и ошибки).
Функцию erase() можно было бы написать следующим образом:
struct Link* erase(struct List* lst, struct Link* p)
/* удаляет узел p из списка lst;
возвращает указатель на узел, расположенный после узла p
*/
{
assert(lst);
if (p==0) return 0; /* OK для вызова erase(0) */
if (p == lst–>first) {
if (p–>suc) {
lst–>first = p–>suc; /* последователь становится первым */
p–>suc–>pre = 0;
return p–>suc;
}
else {
lst–>first = lst–>last = 0; /* список становится пустым */
return 0;
}
}
else if (p == lst–>last) {
if (p–>pre) {
lst–>last = p–>pre; /* предшественник становится последним */
p–>pre–>suc = 0;
}
else {
lst–>first = lst–>last = 0; /* список становится пустым */
return 0;
}
}
else {
p–>suc–>pre = p–>pre;
p–>pre–>suc = p–>suc;
return p–>suc;
}
}
Остальные функции читатели могут написать в качестве упражнения, поскольку для нашего (очень простого) теста они не
