Стивен Прата - Язык программирования C. Лекции и упражнения (6-е изд.) 2015

Функция InitializeList() инициализирует список пустым содержимым. В нашей реализации это означает установку переменной типа List в NULL. Как упоминалось ранее, это требует передачи в функцию указателя на переменную типа List.

Функция ListEmpty() довольно проста, но она полагается на то, переменная списка установлена в NULL, когда список пуст. Таким образом, важно инициализировать список до первого вызова функции ListEmpty().

740 Глава 17

Puc. 17.5. Три части программ ного пакета

Кроме того, если вы расширите интерфейс, включив в него средство для удаления элементов, то должны удостовериться, что функция удаления сбрасывает список в пустое состояние после удаления последнего элемента. В случае применения связного списка его размер ограничен объемом доступной памяти. Функция ListlsFull() пытается выделить объем памяти, достаточный для нового элемента. Если это ей не удается, значит, список полон. Если попытка была успешной, функция должна освободить только что выделенную память, чтобы она была доступна для реального элемента.

Функция ListltemCount() использует обычный алгоритм обхода связного списка, подсчитывая при этом количество элементов:

unsigned int ListltemCount(const List * plist)

{

unsigned int count = 0;

Node * pnode = *plist; /* установка в начало списка */ while (pnode != NULL)

{

++count;

Расширенное представление данных 741

pnode = pnode->next; /* установка в следующий узел */

}

return count;

}

Функция Addltem() наиболее сложная из всех:

bool Addltem(ltem item, List * plist)

{

Node * pnew;

Node * scan = *plist;

pnew = (Node *) malloc(sizeof(Node));

if (pnew == NULL)

return false; /* выход из функции в случае ошибки */

CopyToNode(item, pnew); pnew->next = NULL;

if (scan = NULL) /* список пуст, поэтому поместить */

*plist = pnew; /* pnew в начало списка */

else

{

while (scan->next != NULL)

scan = scan->next; /* поиск конца списка */

scan->next = pnew; /* добавление pnew в конец */

}

return true;

}

Первым делом функция Addltem() выделяет память для нового узла. Если это ей удается, она применяет функцию CopyToNode() для копирования элемента в узел. Затем она устанавливает член next узла в NULL. Как вы помните, это служит сигналом того, что данный узел является последним в связном списке. И, наконец, после создания узла и присваивания соответствующих значений его членам функция присоединяет узел в конец списка. Если это первый добавленный элемент списка, программа устанавливает указатель на заголовок в первый элемент. (Вспомните, что функция Addltem() вызывается с адресом указателя на заголовок во втором аргументе, поэтому * plist — это значение указателя на заголовок.) В противном случае код выполняет проход по связному списку до тех пор, пока не обнаружит элемент, член next которого установлен в NULL. В текущий момент этот узел является последним в списке, поэтому функция переустанавливает его член next, чтобы он указывал на новый узел.

Принятая практика программирования требует вызова функции ListlsFull() перед попыткой добавления элемента в список. Однако пользователь может упустить этот момент, поэтому функция Addltem() самостоятельно проверяет успешность вызова malloc(). Кроме того, вполне вероятно, что между вызовами функций ListlsFull() и Addltem() пользователь мог выполнить еще какие-то действия по выделению памяти, поэтому лучше на всякий случай проверить, сработала ли функция malloc().

Функция Traverse() аналогична ListltemCount(), но в ней добавлено применение функции к каждому элементу списка:

void Traverse (const List * plist, void (* pfun) (Item item) )

{

Node * pnode = *plist; /* установка в начало списка */

while (pnode != NULL)

{

(*pfun)(pnode->item); /* применение функции к элементу */

pnode = pnode->next; /* переход к следующему элементу */

}

}

742 глава 17

Вспомните, что pnode->item представляет данные, хранящиеся в узле, a pnode-> next идентифицирует следующий узел в связном списке. Например, вызов

Traverse(movies, showmovies);

применяет функцию showmovies() к каждому элементу в списке.

Наконец, функция EmptyTheList() освобождает память, которая ранее была выделена с помощью malloc():

В этой реализации пустой список обозначается путем установки переменной List в NULL. Следовательно, чтобы можно было изменять переменную List, в функцию должен быть передан адрес этой переменной. Так как List уже является указателем, то plist — это указатель на указатель. Таким образом, внутри кода выражение *plist имеет тип указателя на Node. Когда список заканчивается, значение *plist равно NULL, т.е. исходный фактический аргумент теперь установлен в NULL.