Читайте также:
|
Структуры данных и алгоритмы служат теми материалами, из ко-
торых строятся программы. Более того, сам компьютер состоит из
структур данных и алгоритмов. Встроенные структуры данных предс-
тавлены теми регистрами и словами памяти, где хранятся двоичные
величины. Заложенные в конструкцию аппаратуры алгоритмы - это
воплощенные в электронных логических цепях жесткие правила, по
которым занесенные в память данные интерпретируются как команды,
подлежащие исполнению. Поэтому в основе работы всякого компьютера
лежит умение оперировать только с одним видом данных - с отдель-
ными битами, или двоичными цифрами. Работает же с этими данными
компьютер только в соответствии с неизменным набором алгоритмов,
которые определяются системой команд центрального процессора.
Задачи, которые решаются с помощью компьютера, редко выража-
ются на языке битов. Как правило данные имеют форму чисел, литер,
текстов, символов и более сложных структур типа последовательнос-
тей, списков и деревьев. Еще разнообразнее алгоритмы, применяемые
для решения различных задач; фактически алгоритмов не меньше чем
вычислительных задач.
Для точного описания абстрактных структур данных и алгорит-
мов программ используются такие системы формальных обозначений,
называемые языками программирования, когда смысл всякого предло-
жения определялся точно и однозначно. Среди средств, представляе-
мых почти всеми языками программирования, имеется возможность
ссылаться на элемент данных, пользуясь присвоенным ему именем,
или, иначе, идентификатором. Одни именованные величины являются
константами, которые сохраняют постоянное значение в той части
программы, где они определены, другие - переменными, которым с
помощью оператора в программе может быть присвоено любое новое
значение. Но до тех пор, пока программа не начала выполняться, их
значение не определено.
Имя константы или переменной помогает программисту, но
компьютеру оно ни о чем не говорит. Компилятор же, транслирующий
текст программы в двоичный код, связывает каждый идентификатор с
определенным адресом памяти. Но для того чтобы компилятор смог
это выполнить, нужно сообщить о "типе" каждой именованной величи-
ны. Человек, решающий какую-нибудь задачу "вручную", обладает ин-
туитивной способностью быстро разобраться в типах данных и тех
операциях, которые для каждого типа справедливы. Так, например,
нельзя извлечь квадратный корень из слова или написать число с
заглавной буквы. Одна из причин, позволяющих легко провести такое
распознавание, состоит в том, что слова, числа и другие обозначе-
ния выглядят по-разному. Однако для компьютера все типы данных
сводятся в конечном счете к последовательности битов, поэтому
различие в типах следует делать явным.
Типы данных, принятые в языках программирования, включают
натуральные и целые числа, вещественные (действительные) числа (в
виде приближенных десятичных дробей), литеры, строки и т.п.
В некоторых языках программирования тип каждой константы или
переменной определяется компилятором по записи присваиваемого
значения; наличие десятичной точки, например, может служить приз-
наком действительного числа. В других языках требуется, чтобы
программист явно задал тип каждой переменной и это дает одно важ-
ное преимущество. Хотя при выполнении программы значение перемен-
ной может многократно меняться, тип ее меняться не должен никог-
да; это значит, что компилятор может проверить операции, выполня-
емые над этой переменной, и убедиться в том, что все они согласу-
ются с описанием типа переменной. Такая проверка может быть про-
ведена путем анализа всего текста программы, и в этом случае она
охватит все возможные действия, определяемые данной программой.
В зависимости от предназначения языка программирования защи-
та типов, осуществляемая на этапе компиляции может быть более или
менее жесткой. Так, например, язык PASCAL, изначально являвшийся
прежде всего инструментом для иллюстрирования структур данных и
алгоритмов, сохраняет от своего первоначального назначения весьма
строгую защиту типов. PASCAL-компилятор в большинстве случаев
расценивает смешение в одном выражении данных разных типов или
применение к типу данных несвойственных ему операций как фаталь-
ную ошибку. Напротив, язык C, предназначенный прежде всего для
системного программирования, является языком с весьма слабой за-
щитой типов. C-компиляторы в таких случаях лишь выдают предупреж-
дения. Отсутствие жесткой защиты типов дает системному програм-
мисту, разрабатывающуему программу на языке C, дополнительные
возможности, но такой программист сам отвечает за свои действия.
Структура данных относится, по существу, к "пространствен-
ным" понятиям: ее можно свести к схеме организации информации в
памяти компьютера. Алгоритм же является соответствующим процедур-
ным элементом в структуре программы - он служит рецептом расчета.
Первые алгоритмы были придуманы для решения численных задач
типа умножения чисел, нахождения наибольшего общего делителя, вы-
числения тригонометрических функций и других. Сегодня в равной
степени важны и нечисленные алгоритмы; они разработаны для таких
задач, как, например, поиск в тексте заданного слова, планирова-
ние событий, сортировка данных в указанном порядке и т.п. Нечис-
ленные алгоритмы оперируют с данными, которые не обязательно яв-
ляются числами; более того, не нужны никакие глубокие математи-
ческие понятия, чтобы их конструировать или понимать. Из этого,
однако, вовсе не следует, что в изучении таких алгоритмов матема-
тике нет места; напротив, точные, математические методы необходи-
мы при поиске наилучших решений нечисленных задач при доказатель-
стве правильности этих решений.
Структуры данных, применяемые в алгоритмах, могут быть чрез-
вычайно сложными. В результате выбор правильного представления
данных часто служит ключом к удачному программированию и может в
большей степени сказываться на производительности программы, чем
детали используемого алгоритма. Вряд ли когда-нибудь появится об-
щая теория выбора структур данных. Самое лучшее, что можно сде-
лать,- это разобраться во всех базовых "кирпичиках" и собранных
из них структурах. Способность приложить эти знания к конструиро-
ванию больших систем - это прежде всего дело инженерного мастерс-
тва и практики.
1.2. Информация и её представление в памяти
Начиная изучение структур данных, или информационных струк-
тур, необходимо ясно установить, что понимается под информацией,
как информация передается и как она физически размещается в памя-
ти вычислительной машины, с несколько упрощенной точки зрения для
того, чтобы изучающий информационные структуры мог понять, что
такое информация и какова ее физическая природа.
Дата добавления: 2014-12-18; просмотров: 55 | Поможем написать вашу работу | Нарушение авторских прав |