1.3 Пример — Set

Так как же реализовать абстрактный тип данных? В качестве примера рассмотрим набор элементов с операциями add, find, и drop (* К сожалению, remove это функция библиотеки ANSI-C для удаления файла. Если использовать это имя для функции работы с набором, станет невозможным подключение stdio.h). Все они применяются к набору и элементу и возвращают элемент, который добавлен к набору, найден в нём или удалён из него. find можно использовать для реализации условия contains, которое сообщает, есть ли уже элемент в наборе.

С этой точки зрения набор является абстрактным типом данных. Для объявления того, что можно делать с набором, начнём с заголовочного файла Set.h:

#ifndef SET_H

#define SET_H

extern const void * Set;

void * add (void * set, const void * element);

void * find (const void * set, const void * element);

void * drop (void * set, const void * element);

int contains (const void * set, const void * element);

#endif

Операторы препроцессора защищают эти объявления: независимо от того, сколько раз подключён Set.h, компилятор C увидит эти декларации только один раз. Этот метод защиты заголовочных файлов настолько стандартный, что препроцессор GNU C распознаёт его и даже не обращается к тому файл, защитный символ которого определён.

Set.h завершён, но чем это полезно? Едва ли можно показать или предложить меньше: Set должен будет каким-то образом отразить тот факт, что мы работаем с множествами; add() принимает элемент, добавляет его к набору, и возвращает то, что было добавлено или уже присутствует в наборе; find() ищет элемент в наборе и возвращает либо его, если он присутствует в наборе, либо пустой указатель; drop() находит элемент, удаляет его из набора, и возвращает то, что было удалено; contains() преобразует результат работы find() в значение истинности.

Везде используется указатель на неопределённый тип void *. С одной стороны это делает невозможным узнать как выглядит набор, но с другой стороны он позволяет передавать в add() и другие функции практически всё что угодно. Не всё будет вести себя как набор или элемент — мы жертвуем безопасностью типа в интересах сокрытия информации. Тем не менее, в главе 8 мы увидим, что этот подход может быть сделан полностью безопасным.