Понятие структур данных и алгоритмов

Структуры данных и алгоритмы являются строительным материалом программного обеспечения. В основе работы вычислительной машины лежит возможность оперировать только с одним видом данных – отдельными битами. Встроенные структуры данных представлены регистрами и словами памяти, в которых хранятся двоичные величины. Однако подлежащие решению задачи редко выражаются на языке битов.

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

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

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

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

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

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

Напротив, язык C, предназначенный, прежде всего, для системного программирования, обладает весьма слабой защитой типов. C-компиляторы в таких случаях лишь выдадут предупреждения. Отсутствие жесткой защиты типов дает дополнительные возможности, но за правильностью действий приходится следить самостоятельно.

Структура данных относится, по существу, к «пространственным» понятиям: ее можно свести к схеме организации информации в памяти машины, в то время как алгоритмы является соответствующим процедурным элементом в структуре программы.

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

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