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

Листинг 17.4. Программа films3.c

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

Реализация интерфейса

Разумеется, еще предстоит реализовать интерфейс List. Подход, принятый в С, предусматривает сбор определений функций в файле по имени list.с. Тогда полная программа будет состоять из трех файлов: list.h, в котором определены структуры данных и предоставлены прототипы для пользовательского интерфейса, list.с, содержащего код функций для реализации интерфейса, и films3.c, представляющего собой файл исходного кода, где интерфейс списка применяется для решения конкретной задачи. Одна из возможных реализаций файла list.с показана в листинге 17.5. Чтобы запустить программу, необходимо скомпилировать оба файла films3.c и list .с и скомпоновать их. (Компиляция многофайловых программ обсуждалась в главе 9). Вместе файлы list.с, list.с и films3.c образуют завершенную программу (рис. 17.5).

Листинг 17.5. Файл реализации list.с

738 Глава 17

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

Замечания по поводу программы

С файлом list.с связано много интересных особенностей. Скажем, он иллюстрирует ситуацию, когда можно использовать функции с внутренним связыванием. Как описано в главе 12, функции с внутренним связыванием известны только в файле, где они определены. При реализации интерфейса иногда удобно применять вспомогательные функции, которые не являются частью официального интерфейса. Например, в приведенной программе функция CopyToNode() используется для копирования значения типа Item в переменную типа Item. Поскольку эта функция — часть реализации, но не интерфейса, с помощью квалификатора класса хранения static мы скрыли ее в файле list.с. А теперь давайте проанализируем остальные функции.

Функция 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.