Глава 1 Фундаментальные структуры данных

На этой странице:

1.1. Введение............................ 18
1.2. Понятие типа данных..........20
1.3. Стандартные

примитивные типы.....................22

1.4. Массивы.............................26
1.5. Записи ...............................29
1.6. Представление массивов,

записей и множеств...................31

1.7. Файлы или

последовательности..................35

1.8. Поиск.................................49
1.9. Поиск образца в тексте
(string search).............................54

Упражнения...............................65

Литература................................67

Введение

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

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

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

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

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

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

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

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

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

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

Эти соображения определили выбор нотации для описания алгоритмов и соответствующих данных в настоящей книге. Разумеется, нам хотелось бы использовать знакомые понятия математики, такие как числа, множества, последовательности и т. д., а не машинно зависимые сущности вроде строк битов. Но нам также хотелось бы использовать нотацию, для которой существуют эффективные компиляторы. Неразумно использовать язык, в сильной степени машинно зависимый, но также недостаточно и описывать программы в абстрактной нотации, в которой проблемы представления остаются нерешенными. Язык программирования Паскаль был спроектирован в попытке найти компромисс между этими двумя крайностями, а его наследники Модула-2 и Оберон учитывают опыт, накопленный за десятилетия [1.3]. Оберон сохраняет базовые понятия Паскаля с некоторыми усовершенствованиями и добавлениями; он используется на протяжении этой книги [1.5]. Оберон был успешно реализован для ряда компьютеров, при этом было продемонстрировано, что его нотация достаточно близка к реальному «железу», чтобы выбранные средства и их представления можно было объяснить с полной ясностью. Язык также близок к другим языкам, так что уроки, усвоенные здесь, могут быть с равным успехом применены и при их использовании.