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

Структуры данных и алгоритмы служат теми материалами, из ко-

торых строятся программы. Более того, сам компьютер состоит из

структур данных и алгоритмов. Встроенные структуры данных предс-

тавлены теми регистрами и словами памяти, где хранятся двоичные

величины. Заложенные в конструкцию аппаратуры алгоритмы - это

воплощенные в электронных логических цепях жесткие правила, по

которым занесенные в память данные интерпретируются как команды,

подлежащие исполнению. Поэтому в основе работы всякого компьютера

лежит умение оперировать только с одним видом данных - с отдель-

ными битами, или двоичными цифрами. Работает же с этими данными

компьютер только в соответствии с неизменным набором алгоритмов,

которые определяются системой команд центрального процессора.

Задачи, которые решаются с помощью компьютера, редко выража-

ются на языке битов. Как правило данные имеют форму чисел, литер,

текстов, символов и более сложных структур типа последовательнос-

тей, списков и деревьев. Еще разнообразнее алгоритмы, применяемые

для решения различных задач; фактически алгоритмов не меньше чем

вычислительных задач.

Для точного описания абстрактных структур данных и алгорит-

мов программ используются такие системы формальных обозначений,

называемые языками программирования, когда смысл всякого предло-

жения определялся точно и однозначно. Среди средств, представляе-

мых почти всеми языками программирования, имеется возможность

ссылаться на элемент данных, пользуясь присвоенным ему именем,

или, иначе, идентификатором. Одни именованные величины являются

константами, которые сохраняют постоянное значение в той части

программы, где они определены, другие - переменными, которым с

помощью оператора в программе может быть присвоено любое новое

значение. Но до тех пор, пока программа не начала выполняться, их

значение не определено.

Имя константы или переменной помогает программисту, но

компьютеру оно ни о чем не говорит. Компилятор же, транслирующий

текст программы в двоичный код, связывает каждый идентификатор с

определенным адресом памяти. Но для того чтобы компилятор смог

это выполнить, нужно сообщить о "типе" каждой именованной величи-

ны. Человек, решающий какую-нибудь задачу "вручную", обладает ин-

туитивной способностью быстро разобраться в типах данных и тех

операциях, которые для каждого типа справедливы. Так, например,

нельзя извлечь квадратный корень из слова или написать число с

заглавной буквы. Одна из причин, позволяющих легко провести такое

распознавание, состоит в том, что слова, числа и другие обозначе-

ния выглядят по-разному. Однако для компьютера все типы данных

сводятся в конечном счете к последовательности битов, поэтому

различие в типах следует делать явным.

Типы данных, принятые в языках программирования, включают

натуральные и целые числа, вещественные (действительные) числа (в

виде приближенных десятичных дробей), литеры, строки и т.п.

В некоторых языках программирования тип каждой константы или

переменной определяется компилятором по записи присваиваемого

значения; наличие десятичной точки, например, может служить приз-

наком действительного числа. В других языках требуется, чтобы

программист явно задал тип каждой переменной и это дает одно важ-

ное преимущество. Хотя при выполнении программы значение перемен-

ной может многократно меняться, тип ее меняться не должен никог-

да; это значит, что компилятор может проверить операции, выполня-

емые над этой переменной, и убедиться в том, что все они согласу-

ются с описанием типа переменной. Такая проверка может быть про-

ведена путем анализа всего текста программы, и в этом случае она

охватит все возможные действия, определяемые данной программой.

В зависимости от предназначения языка программирования защи-

та типов, осуществляемая на этапе компиляции может быть более или

менее жесткой. Так, например, язык PASCAL, изначально являвшийся

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

алгоритмов, сохраняет от своего первоначального назначения весьма

строгую защиту типов. PASCAL-компилятор в большинстве случаев

расценивает смешение в одном выражении данных разных типов или

применение к типу данных несвойственных ему операций как фаталь-

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

системного программирования, является языком с весьма слабой за-

щитой типов. C-компиляторы в таких случаях лишь выдают предупреж-

дения. Отсутствие жесткой защиты типов дает системному програм-

мисту, разрабатывающуему программу на языке C, дополнительные

возможности, но такой программист сам отвечает за свои действия.

Структура данных относится, по существу, к "пространствен-

ным" понятиям: ее можно свести к схеме организации информации в

памяти компьютера. Алгоритм же является соответствующим процедур-

ным элементом в структуре программы - он служит рецептом расчета.

Первые алгоритмы были придуманы для решения численных задач

типа умножения чисел, нахождения наибольшего общего делителя, вы-

числения тригонометрических функций и других. Сегодня в равной

степени важны и нечисленные алгоритмы; они разработаны для таких

задач, как, например, поиск в тексте заданного слова, планирова-

ние событий, сортировка данных в указанном порядке и т.п. Нечис-

ленные алгоритмы оперируют с данными, которые не обязательно яв-

ляются числами; более того, не нужны никакие глубокие математи-

ческие понятия, чтобы их конструировать или понимать. Из этого,

однако, вовсе не следует, что в изучении таких алгоритмов матема-

тике нет места; напротив, точные, математические методы необходи-

мы при поиске наилучших решений нечисленных задач при доказатель-

стве правильности этих решений.

Структуры данных, применяемые в алгоритмах, могут быть чрез-

вычайно сложными. В результате выбор правильного представления

данных часто служит ключом к удачному программированию и может в

большей степени сказываться на производительности программы, чем

детали используемого алгоритма. Вряд ли когда-нибудь появится об-

щая теория выбора структур данных. Самое лучшее, что можно сде-

лать,- это разобраться во всех базовых "кирпичиках" и собранных

из них структурах. Способность приложить эти знания к конструиро-

ванию больших систем - это прежде всего дело инженерного мастерс-

тва и практики.

1.2. Информация и её представление в памяти

Начиная изучение структур данных, или информационных струк-

тур, необходимо ясно установить, что понимается под информацией,

как информация передается и как она физически размещается в памя-

ти вычислительной машины, с несколько упрощенной точки зрения для

того, чтобы изучающий информационные структуры мог понять, что

такое информация и какова ее физическая природа.