В то время как управляющие структуры организуют алгоритмы, структуры данных организуют информацию. В частности, структуры данных определяют типы данных, а значит, и операции, которые можно с ними выполнять, избавляя программиста от необходимости отслеживать адреса памяти. К простым структурам данных относятся целые числа, вещественные числа, булевы числа (истина/ложь), а также символы или строки символов. Сложные структуры данных образуются путем объединения одного или нескольких типов данных.
Наиболее важными составными структурами данных являются массив — однородная коллекция данных, и запись — разнородная коллекция. Массив может представлять собой вектор чисел, список строк или коллекцию векторов (массив массивов, или математическую матрицу). В записи может храниться информация о сотруднике — имя, должность и зарплата. Массив записей, например таблица сотрудников, представляет собой набор элементов, каждый из которых неоднороден. И наоборот, запись может содержать вектор — т. е. массив.
Компоненты записи, или поля, выбираются по имени; например, E.SALARY может представлять поле зарплаты в записи E. Элемент массива выбирается по его позиции или индексу; A[10] — это элемент в позиции 10 в массиве A. Таким образом, цикл FOR (определенная итерация) может проходить через массив с ограничениями по индексу (от FIRST до LAST в следующем примере), чтобы суммировать его элементы:
Массивы и записи имеют фиксированный размер. Структуры, которые могут расти, строятся с динамическим распределением, которое предоставляет новое хранилище по мере необходимости. В таких структурах данных есть компоненты, каждый из которых содержит данные и ссылки на другие компоненты (в машинных терминах — их адреса). Такие самореферентные структуры имеют рекурсивные определения. Например, двоичное дерево (bintree) либо пусто, либо содержит корневой компонент с данными и левый и правый двоичные «дети». Такие бинтри эффективно реализуют таблицы информации. Подпрограммы для работы с ними естественно рекурсивны; следующая подпрограмма распечатывает все элементы бинарного дерева (каждый из них является корнем некоторого поддерева):
Абстрактные типы данных (АДТ) важны для крупномасштабного программирования. Они объединяют структуры данных и операции над ними, скрывая внутренние детали. Например, ADT-таблица предоставляет пользователям операции вставки и поиска, оставляя при этом невидимой основную структуру, будь то массив, список или двоичное дерево. В объектно-ориентированных языках классы — это ADT, а объекты — их экземпляры. В следующем примере объектно-ориентированного псевдокода предполагается, что существует ADT bintree и «суперкласс» COMPARABLE, характеризующий данные, для которых существует операция сравнения (например, «<” for integers). It defines a new ADT, TABLE, that hides its data-representation and provides operations appropriate to tables. This class is polymorphic—defined in terms of an element-type parameter of the COMPARABLE class. Any instance of it must specify that type, here a class with employee data (the COMPARABLE declaration means that PERS_REC must provide a comparison operation to sort records). Implementation details are omitted.
TABLE делает общедоступными только свои собственные операции; таким образом, если его модифицировать, чтобы он использовал массив или список, а не bintree, программы, использующие его, не смогут обнаружить это изменение. Такое сокрытие информации необходимо для управления сложностью больших программ. Он делит их на небольшие части, заключая между ними «контракты»; здесь класс TABLE заключает контракт на предоставление операций поиска и вставки, а его пользователи — на использование только тех операций, которые опубликованы.
