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

дочены, что позволяет говорить о первом, втором или последнем элементе в списке. Далее, тип списка должен поддерживать такие операции, как добавление элемента в список. Ниже перечислены некоторые полезные операции:

• инициализация списка пустым содержимым;

• добавление элемента в конец списка;

• определение, является ли список пустым;

• определение, является ли список полным;

• определение количества элементов в списке;

• посещение каждого элемента в списке с целью выполнения какого-то действия, такого как отображение элемента.

Для этого проекта дополнительные операции не нужны, но более универсальный перечень операций со списками может включать следующие:

• вставка элемента в любое место списка;

• удаление элемента из списка;

• извлечение элемента из списка (список остается неизмененным);

• замена одного элемента в списке другим;

• поиск элемента в списке.

Тогда неформальное, но абстрактное определение списка выглядит так: список — это объект данных, способный хранить последовательность элементов, к которому можно применять любые из перечисленных ранее операций. В этом определении не заявлен вид элементов, которые могут храниться в списке. В нем не указано, должен ли для хранения элементов использоваться массив, связанный набор структур либо иная форма данных. Определение не диктует, какой метод применять, например, для выяснения количества элементов в списке. Все эти детали оставлены за реализацией.

Для простоты давайте примем в качестве абстрактного типа данных упрощенный список, содержащий только те функциональные возможности, которые требуются для проекта информации о фильмах. Краткое описание этого типа приведено ниже.

Имя типа: Простой список

Свойства типа: Может содержать последовательность элементов

Операции типа: Инициализация списка пустым содержимым Определение, является ли список пустым Определение, является ли список полным Определение количества элементов в списке Добавление элемента в конец списка Обход списка с обработкой каждого элемента Опустошение списка

Следующим этапом является разработка для ADT простого списка интерфейса на языке С.

Построение интерфейса

Интерфейс для простого списка состоит из двух частей. Первая часть описывает способ представления данных, а вторая — функции, реализующие операции ADT. Например, интерфейс будет содержать функции для добавления элемента в список и

732 глава 17 вывода количества элементов в списке. Проектное решение интерфейса должно как можно ближе отражать описание ADT. Следовательно, оно должно быть выражено в терминах некоторого общего типа Item, а не в терминах какого-то конкретного типа вроде int или struct film. Один из способов достижения этого предполагает использование средства typedef языка С для определения Item в качестве требуемого типа:

#define TSIZE 45 /* размер массива для хранения названия */

struct film {

char title[TSIZE]; int rating;

};

typedef struct film Item;

Затем тип Item можно применять в остальных определениях. Если позже потребуется список элементов какой-то другой формы данных, можно будет переопределить тип Item и оставить остальную часть определения интерфейса без изменений.

После того как тип Item определен, необходимо принять решение о способе хранения элементов этого типа. В действительности этот шаг относится к этапу реализации, но принятие решения в настоящий момент упростит понимание примера. Подход с использованием связанных структур достаточно успешно работал в программе films2.с, поэтому применим его, как показано ниже:

typedef struct node {

Item item; struct node * next;

} Node;

typedef Node * List;

В реализации с применением связного списка каждая связь называется узлом. Каждый узел содержит информацию, формирующую содержимое списка, и указатель на следующий узел. Чтобы подчеркнуть используемую терминологию, мы назвали структуру узла избитым именем node (т.е. “узел”) и применили typedef, чтобы сделать Node именем типа для структуры struct node. Наконец, для управления связным списком необходим указатель на его начало, поэтому мы использовали typedef, чтобы превратить List в имя для указателя этого типа. Таким образом, объявление

List movies;

устанавливает movies как указатель, подходящий для ссылки на связный список.

Является ли этот способ определения типа List единственным? Нет. Например, для отслеживания количества записей можно было бы задействовать переменную:

typedef struct list {

Node * head; /* указатель на заголовок списка */