Абстрактные типы данных: тип определяют операции

Модуль "Объекты и ссылки" • урок 5 из 7 • ~7 минут

Что такое абстрактные типы данных

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

Ключевой сдвиг - в точке зрения. Что такое стек? Бесполезно отвечать "это массив с переменной-счетчиком": это уже реализация. Стек - это то, над чем определены операции "втолкнуть элемент", "вынуть верхний", "показать верхний", "проверить, пуст ли". Набор операций и есть определение типа. Такой взгляд называют операционным: АТД часто отождествляют с множеством его операций.

Интерфейс снаружи, реализация внутри

Чтобы АТД можно было отдать другому программисту (или продать), его оформляют как автономную программную единицу - модуль. В самой развитой форме определение АТД состоит из четырех частей:

1. интерфейс (видимая часть) - имя типа, имена операций, типы их аргументов и результатов;
2. абстрактное описание операций - что они делают, сформулированное на языке спецификаций, без кода;
3. конкретная реализация - те же операции, написанные на обычном языке программирования;
4. обоснование соответствия - объяснение, почему реализация корректно воплощает абстрактное описание.

Сокрытие внутренних, служебных структур реализации за интерфейсом называется инкапсуляцией. Она защищает данные от случайной порчи (нельзя залезть внутрь стека в обход операций) и дает свободу: внутренности можно переделывать, пока снаружи все выглядит по-прежнему.

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

Пример: стек как АТД на C

В C роль интерфейса играет заголовочный файл. Все, что нужно знать использующей программе, умещается в несколько строк:

/* stack.h - интерфейс АТД: это видят все */
typedef int TValue;

void   push(TValue v);  /* втолкнуть элемент     */
TValue pop(void);       /* вынуть верхний        */
TValue top(void);       /* показать верхний      */
int    empty(void);     /* пуст ли стек?         */

Реализация живет в отдельном файле stack.c. Слово static прячет внутренние данные от остальной программы - это и есть инкапсуляция средствами C:

/* stack.c - реализация: снаружи не видна */
#include "stack.h"

static TValue body[100];  /* сплошное представление */
static int total = 0;     /* static = снаружи не достать */

void push(TValue v) { body[total++] = v; }
TValue pop(void)    { return body[--total]; }
TValue top(void)    { return body[total - 1]; }
int empty(void)     { return total == 0; }

Программа пользуется стеком только через операции из stack.h. Завтра можно переписать stack.c на цепное представление - узлы с указателями и malloc, чтобы снять ограничение в 100 элементов, - и программа этого даже не заметит: достаточно перекомпилировать проект. Сам стек во всех подробностях нас ждет в модуле 3.