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

Предположим, что вы хотите определить новый тип данных. Во-первых, вы должны предоставить способ для хранения данных — возможно, за счет проектирования структуры. Во-вторых, понадобится обеспечить методы для манипулирования данными. В качестве примера рассмотрим программу films2.c (листинг 17.2). Она содержит связанный набор структур для хранения информации, а также код для добавления и отображения информации. Тем не менее, программа не решает эти задачи так, чтобы сделать очевидным создание нового типа данных. Как же следовало пос тупить?

Науки о вычислениях предлагают очень эффективный способ определения новых типов данных. Он является трехэтапным процессом перехода от абстрактного к конкретному.

1. Предоставьте абстрактное описание свойств типа и операций, которые можно выполнять над этим типом. Такое описание не должно быть привязано ни к какой конкретной реализации. Оно даже не должно быть привязано к конкретному языку программирования. Формальное абстрактное описание подобного рода называют абстрактным типом данных (abstract data type — ADT).

2. Разработайте программный интерфейс, реализующий этот тип ADT. То есть укажите, как следует хранить данные, и опишите набор функций, которые выполняют желаемые операции. Например, в С вы можете предоставить определение структуры наряду с прототипами функций для манипулирования структурами. Эти функции играют для определенного пользователем типа ту же самую роль, которую встроенные операции С исполняют для фундаментальных типов С. Любой, кто захочет воспользоваться новым типом, будет применять этот интер фейс в своих профаммах.

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

Чтобы посмотреть, как работает этот процесс, давайте рассмотрим конкретный пример. Поскольку мы уже приложили кое-какие усилия к примеру с созданием списка фильмов, переделаем его с применением нового подхода.

Получение абстракции

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Следующим этапом является разработка для 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 в имя для указателя этого типа. Таким образом, объявление