Алгоритмы и структуры данныхНовая версия для Оберона cdмосква, 2010Никлаус ВиртПеревод с английского под редакцией
 Скачать 2.67 Mb.
|
|
Глава 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 Фундаментальные структуры данных 18 1.1. Введение Современные цифровые компьютеры были изобретены для выполнения сложных и длинных вычислений. Однако в большинстве приложений предоставляемая та% ким устройством возможность хранить и обеспечивать доступ к большим масси% вам информации играет основную роль и рассматривается как его главная характеристика, а возможность призводить вычисления, то есть выполнять арифметические действия, во многих случаях стала почти несущественной. В таких приложениях большой массив обрабатываемой информации является в определенном смысле абстрактным представлением некоторой части реального мира. Информация, доступная компьютеру, представляет собой специально подобранный набор данных, относящихся к решаемой задаче, причем предпо% лагается, что этот набор достаточен для получения нужных результатов. Данные являются абстрактным представлением реальности в том смысле, что некоторые свойства реальных объектов игнорируются, так как они несущественны для этой задачи. Поэтому абстракция – это еще и упрощение реальности. В качестве примера можно взять файл с данными о служащих некоторой ком% пании. Каждый служащий (абстрактно) представлен в этом файле набором дан% ных, который нужен либо для руководства компании, либо для бухгалтерских расчетов. Такой набор может содержать некоторую идентификацию служащего, например имя и зарплату. Но в нем почти наверняка не будет несущественной информации о цвете волос, весе или росте. Решая задачу с использованием компьютера или без него, необходимо выбрать абстрактное представление реальности, то есть определить набор данных, кото% рый будет представлять реальную ситуацию. Этот выбор можно сделать, руко% водствуясь решаемой задачей. Затем нужно определиться с представлением ин% формации. Здесь выбор определяется средствами вычислительной установки. В большинстве случаев эти два шага не могут быть полностью разделены. Выбор представления данных часто довольно сложен и не полностью определя% ется имеющимися вычислительными средствами. Делать такой выбор всегда нужно с учетом операций, которые нужно выполнять с данными. Хороший пример – пред% ставление чисел, которые сами суть абстракции свойств некоторых объектов. Если единственное (или основное) действие, которое нужно выполнять, – сложение, то хорошим представлением числа n может быть n черточек. Правило сложения при та% ком представлении – очевидное и очень простое. Римская нотация основана на этом принципе простоты, и правила сложения просты для маленьких чисел. С другой сто% роны, представление арабскими цифрами требует неочевидных правил сложения (для маленьких чисел), и их нужно запоминать. Однако ситуация меняется на проти% воположную, если нужно складывать большие числа или выполнять умножение и деление. Разбиение этих операций на более простые шаги гораздо проще в случае арабской нотации благодаря ее систематической позиционной структуре. Хорошо известно, что компьютеры используют внутреннее представление, основанное на двоичных цифрах (битах). Это представление непригодно для использования людьми, так как здесь обычно приходится иметь дело с большим 19 числом цифр, но весьма удобно для электронных схем, так как два значения 0 и 1 можно легко и надежно представить посредством наличия или отсутствия элект% рических токов, зарядов или магнитных полей. Из этого примера также видно, что вопрос представления часто требует рассма% тривать несколько уровней детализации. Например, в задаче представления по% ложения объекта первое решение может касаться выбора пары чисел в, скажем, декартовых или полярных координатах. Второе решение может привести к пред% ставлению с плавающей точкой, где каждое вещественное число x состоит из пары целых, обозначающих дробную часть f и показатель e по некоторому основанию (например, x = f × 2 e ). Третье решение, основанное на знании, что данные будут храниться в компьютере, может привести к двоичному позиционному представ% лению целых чисел. Наконец, последнее решение может состоять в том, чтобы представлять двоичные цифры электрическими зарядами в полупроводниковом устройстве памяти. Очевидно, первое решение в этой цепочке зависит главным образом от решаемой задачи, а дальнейшие все больше зависят от используемого инструмента и применяемых в нем технологий. Вряд ли можно требовать, чтобы программист решал, какое представление чисел использовать или даже какими должны быть характеристики устройства хранения данных. Такие решения низ% кого уровня можно оставить проектировщикам вычислительного оборудования, у которых заведомо больше информации о существующих технологиях, чтобы сделать разумный выбор, приемлемый для всех (или почти всех) приложений, где играют роль числа. В таком контексте выявляется важность языков программирования. Язык программирования представляет абстрактный компьютер, допускающий интер% претацию в терминах данного языка, что может подразумевать определенный уровень абстракции по сравнению с объектами, используемыми в реальном вычислительном устройстве. Тогда программист, использующий такой язык вы% сокого уровня, будет освобожден от заботы о представлении чисел (и лишен воз% можности что%то сделать в этом отношении), если числа являются элементар% ными объектами в данном языке. Использование языка, предоставляющего удобный набор базовых абстракций, общих для большинства задач обработки данных, влияет главным образом на на% дежность получающихся программ. Легче спроектировать программу, опираясь в рассуждениях на знакомые понятия чисел, множеств, последовательностей и циклов, чем иметь дело с битами, единицами хранения и переходами управления. Конечно, реальный компьютер представляет любые данные – числа, множества или последовательности – как огромную массу битов. Но программист может за% быть об этом, если ему не нужно беспокоиться о деталях представления выбран% ных абстракций и если он может считать, что выбор представления, сделанный компьютером (или компилятором), разумен для решаемых задач. Чем ближе абстракции к конкретному компьютеру, тем легче сделать выбор представления инженеру или автору компилятора и тем выше вероятность, что единственный выбор будет подходить для всех (или почти всех) мыслимых при% ложений. Это обстоятельство устанавливает определенные пределы на «высоту» Введение Фундаментальные структуры данных 20 используемых абстракций по сравнению с уровнем реального «железа». Напри% мер, неразумно включать в язык общего назначения геометрические фигуры, так как из%за внутренне присущей им сложности их подходящее представление будет сильно зависеть от действий, выполняемых с ними. Однако природа и частота та% ких действий неизвестна проектировщику языка программирования общего на% значения и соответствующего компилятора, и любой выбор проектировщика мо% жет оказаться плохим для некоторого класса приложений. Эти соображения определили выбор нотации для описания алгоритмов и соот% ветствующих данных в настоящей книге. Разумеется, нам хотелось бы использо% вать знакомые понятия математики, такие как числа, множества, последователь% ности и т. д., а не машинно зависимые сущности вроде строк битов. Но нам также хотелось бы использовать нотацию, для которой существуют эффективные компиляторы. Неразумно использовать язык, в сильной степени машинно зави% симый, но также недостаточно и описывать программы в абстрактной нотации, в которой проблемы представления остаются нерешенными. Язык программи% рования Паскаль был спроектирован в попытке найти компромисс между этими двумя крайностями, а его наследники Модула%2 и Оберон учитывают опыт, накопленный за десятилетия [1.3]. Оберон сохраняет базовые понятия Паскаля с некоторыми усовершенствованиями и добавлениями; он используется на протя% жении этой книги [1.5]. Оберон был успешно реализован для ряда компьютеров, при этом было продемонстрировано, что его нотация достаточно близка к реально% му «железу», чтобы выбранные средства и их представления можно было объяс% нить с полной ясностью. Язык также близок к другим языкам, так что уроки, усво% енные здесь, могут быть с равным успехом применены и при их использовании. 1.2. Понятие типа данных В математике переменные обычно классифицируются по некоторым важным ха% рактеристикам. Проводится четкое различие между вещественными, комплекс% ными и логическими переменными, или между переменными, представляющими отдельные значения, множества значений, множества множеств, или между фун% кциями, функционалами, множествами функций и т. д. Такая классификация не менее, если не более, важна в обработке данных. Мы будем придерживаться того принципа, что каждая константа, выражение или функция имеет определенный тип. В сущности, тип характеризует множество значений, к которому принад% лежит константа, или которые может принимать переменная или выражение, или которые могут порождаться функцией. В математических текстах тип переменной обычно можно определить просто по шрифту, без учета контекста; но это невозможно в компьютерных программах. На вычислительной установке обычно доступен только один шрифт (латинские буквы). Поэтому часто следуют правилу явно вводить соответствующий тип в объявлении константы, переменной или функции, причем такое объявление должно предшествовать использованию этой константы, переменной или функ% ции. Это правило тем более разумно, что компилятор должен выбрать пред% 21 ставление объекта в памяти компьютера. Очевидно, что объем памяти, отведен% ной под переменную, должен быть выбран в соответствии с диапазоном значений, которые может принимать переменная. Если эта информация доступна компиля% тору, то можно избежать так называемого динамического размещения. Очень час% то этот пункт оказывается ключевым для эффективной реализации алгоритма. Сущность понятия типа, как оно используется в данном тексте и реализуется в языке программирования Оберон, выражается в следующих утверждениях [1.2]: 1. Тип данных определяет множество значений, которому принадлежит зна% чение константы, или в котором принимает значения переменная или выра% жение, или которому принадлежат значения, порождаемые операцией или функцией. 2. Тип значения, обозначенного константой, переменной или выражением, может быть выведен из их объявлений и вида выражения без выполнения вычислений. 3. Каждая операция или функция требует аргументов определенных типов и дает результат некоторого, тоже определенного типа. Если операция допус% кает аргументы нескольких типов (например, + используется для сложения как целых, так и вещественных чисел), то тип результата может быть опре% делен на основе особых правил языка программирования. Компилятор может использовать такую информацию о типах для проверки законности различных конструкций. Например, ошибочное присваивание булев% ского (логического) значения арифметической переменной может быть обнару% жено без выполнения программы. Подобная избыточность текста программы весьма полезна при ее разработке и может рассматриваться как главное преиму% щество хороших языков высокого уровня по сравнению с машинным кодом (или кодом символического ассемблера). Очевидно, в конечном итоге данные будут представлены огромным количест% вом двоичных цифр независимо от того, была ли написана исходная программа на языке высокого уровня, использующего понятие типа, или на ассемблере, где ти% пов нет. Для компьютера память представляется однородной массой битов без явной структуры. Но именно абстрактная структура позволяет человеку%програм% мисту видеть смысл в монотонном пейзаже компьютерной памяти. Теория, о которой идет речь в данной книге, и язык программирования Оберон дают некоторые способы определения типов данных. В большинстве случаев но% вый тип данных строится из других типов, уже определенных (назовем их состав ляющими). Значения такого типа – это обычно агрегаты значений%компонент, принадлежащих ранее определенным составляющим типам, и такие значения на% зываются составными,или структурированными. Если используется только один составляющий тип, то естьвсе компоненты принадлежат одному типу, то этот тип называют базовым. Число различных значений типа называют его мощ ностью. Мощность позволяет определить объем памяти для представления пере% менной x , имеющей тип T , что обозначается как x: T Поскольку составляющие типы, в свою очередь, могут быть составными, то могут выстраиваться целые иерархии структур. Впрочем, очевидно, что наимень% Понятие типа данных Фундаментальные структуры данных 22 шие компоненты структуры должны быть неделимыми. Поэтому нужны некие стандартные, заранее определенные типы. Обычно здесь речь идет о числах и ло% гических значениях. Если значения типа могут быть упорядочены, то такой тип называют упорядоченным. В Обероне все бесструктурные типы упорядочены. Имея такие средства, из примитивных типов можно строить агрегаты, состав% ные типы любого уровня вложенности. На практике недостаточно иметь только один общий способ построения структуры из составляющих типов. Должным об% разом учитывая практические проблемы представления и использования, язык программирования общего назначения должен предлагать несколько методов структурирования данных. В математическом смысле они эквивалентны, но отличаются операциями для доступа к компонентам структур. Базовые методы структурирования, которые будут представлены ниже, суть массив, запись и последовательность. Более сложные структуры обычно не определяются как ста% тические типы, а порождаются динамически во время выполнения программы, когда могут меняться их размер и состав. Таким структурам посвящена глава 4; сюда относятся списки, кольца, деревья и вообще конечные графы. Переменные и типы данных вводятся в программу для использования в вычис% лениях. Для вычислений нужно иметь набор операций. Поэтому для каждого стандартного типа данных язык программирования предлагает некий набор прими% тивных, стандартных операций, а для каждого метода структурирования – специ% альные операции для доступа к компонентам вместе с соответствующей нотацией. Нередко считают, что суть искусства программирования – в комбинировании операций. Однако мы увидим, что хорошее структурирование данных – задача не менее фундаментальная и важная. Важнейшие основные операции – сравнение и присваивание, то есть проверка равенства (или порядка в случае упорядоченных типов) и команда, так сказать, обеспечивающая равенство. Принципиальное различие между ними подчерки% вается обозначениями, которые используются на протяжении всей книги: Проверка равенства: x = y (выражение, дающее значение TRUE или FALSE ) Присваивание переменной x : x := y (оператор, делающий x равным y ) Эти основополагающие действия определены для большинства типов данных, но следует заметить, что их выполнение может требовать серьезных вычислений, если данные велики по объему и имеют сложную структуру. Для стандартных примитивных типов данных мы постулируем не только воз% можность присваивания и сравнения, но еще и набор операций для создания (вы% числения) новых значений. А именно: для числовых типов мы вводим стандартные арифметические операции, а для логических значений – элементарные операции логики высказываний. 1.3. Стандартные примитивные типы Стандартные примитивные типы суть те, которые доступны в большинстве ком% пьютеров «на уровне железа». Сюда включаются целые числа, логические значе% ния, а также некоторый набор литер для печати. На многих компьютерах еще име% 23 ются дробные числа вместе со стандартными арифметическими операциями. Мы обозначаем эти типы следующими идентификаторами: INTEGER, REAL, BOOLEAN, CHAR, SET 1.3.1. Тип INTEGER Тип INTEGER представляет подмножество целых чисел, диапазон значений кото% рых может меняться от одной вычислительной системы к другой. Если компью% тер использует n битов для представления целых чисел в дополнительном коде, то допустимые значения x должны удовлетворять условию –2 n–1 ≤ x < 2 n–1 . Предпо% лагается, что все операции с данными этого типа являются точными и соответ% ствуют обычным законам арифметики и что вычисление будет прервано, если ре% зультат лежит за пределами указанного диапазона. Такое событие называют переполнением. Стандартные операции – четыре основные арифметические опе% рации: сложение ( + ), вычитание ( – ), умножение ( * ) и деление ( / , DIV ). Косая черта будет обозначать деление, имеющее результатом значение типа REAL , а операция DIV будет обозначать целочисленное деление, имеющее результатом зна% чение типа INTEGER . Если мы определим частное q = m DIV n и остаток r = m MOD n , то должны выполняться следующие соотношения (предполагается, что n > 0 ): q*n + r = m и 0 ≤ r < n Примеры – 31 DIV 10 = – 3 – 31 MOD 10 = 1 –31 DIV 10 = –4 –31 MOD 10 = 9 Известно, что деление на 10 n может быть осуществлено простым сдвигом десятичных знаков на n позиций вправо с отбрасыванием избыточных цифр спра% ва. Аналогичный метод применим, если числа представлены в двоичной, а не десятичной нотации. Если используется дополнительный код (как это имеет мес% то практически во всех современных компьютерах), то сдвиги обеспечивают деле% ние в соответствии с данным выше определением операции DIV . Поэтому в компи% ляторе нетрудно реализовать операцию вида m DIV 2 n (или m MOD 2 n ) с помощью быстрой операции сдвига (или с помощью маски). |