Глава 1. Общие сведения

В самом начале книги у читателей могут возникнуть некоторые вопросы:

• Что такое «структуры данных и алгоритмы»?
• Какую пользу принесет мне их изучение?
• Почему бы не использовать для работы с данными массивы и циклы for?
• Когда следует применять те знания, которые я найду в книге?

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

Зачем нужны структуры данныхи алгоритмы?

Эта книга посвящена структурам данных и алгоритмам. Структурой данных называется способ организации данных в памяти компьютера (или на диске). Примерами структур данных являются массивы, связанные списки, стеки, двоичные деревья, хеш-таблицы и т. д. Алгоритмы обеспечивают выполнение различных операций с этими структурами — например, поиск определенного элемента данных или сортировку данных.

Какие задачи помогает решить хорошее знание структур данных и алгоритмов? Ситуации, в которых они могут пригодиться, можно приблизительно разделить на три категории:

• Хранение реальных данных.
• Инструментарий программиста.
• Моделирование.

Данная классификация не является жесткой и формальной, но она дает пред- ставление о полезности материала. Рассмотрим эти три категории более подробно.

Хранение реальных данных

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

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

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

• Как данные будут храниться в памяти компьютера?
• Подойдет ли ваше решение для сотни карточек? Для тысячи? Миллиона?
• Позволяет ли ваше решение быстро добавлять новые и удалять старые карточки?
• Возможен ли быстрый поиск заданной карточки?
• Допустим, вы хотите отсортировать карточки в алфавитном порядке. Как будетпроисходить сортировка?

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

Инструментарий программиста

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

Моделирование

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

Обзор структур данных

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

Все структуры данных из табл. 1.1, за исключением массивов, могут рассматриваться как абстрактные типы данных (ADT). О том, что это такое, рассказано в главе 5, «Связанные списки».

Алгоритмы

Многие алгоритмы, описанные в книге, предназначены для работы с конкретными структурами данных. Для большинства структур данных необходимо знать, как выполняются операции:

• Вставки нового элемента данных.
• Поиска заданного элемента.
• Удаления заданного элемента.

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

Другую важную категорию алгоритмов составляют алгоритмы сортировки. Существует много различных способов сортировки данных; им посвящены глава 3, «Простая сортировка», и глава 7, «Нетривиальная сортировка». В некоторых алгоритмах важная роль отводится рекурсии, то есть вызову мето- дом самого себя. Рекурсия рассматривается в главе 6, «Рекурсия». (Термин метод используется в Java; в других языках он заменяется терминами «функция», «процедура» или «подпрограмма».)

Определения

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

База данных

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

Запись

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

Поле

Запись обычно делится на несколько полей. Поле содержит данные определенного типа. В адресной картотеке имя человека, его адрес или номер телефона является отдельным полем.

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

В Java (и других объектно-ориентированных языках) записи обычно представ- ляются объектами соответствующих классов. Отдельные переменные в объектах представляют поля данных. Поля в объектах классов в языке Java называются полями (тогда как в других языках — таких, как C++ — используется термин «пере- менные экземпляров»).

Ключ

Для поиска записей в базе данных одно из полей записи назначается ключом. Запись ищется по заданному значению ключа. Например, в программе адресной книги поиск записи может производиться по значению ключевого поля имени «Браун». Если в результате поиска будет найдена запись с заданным ключом, вы можете обращаться ко всем ее полям, не только к ключевому полю. Можно сказать, что ключ «отпирает» всю запись. Для одного файла могут использоваться разные ключи — например, поиск может осуществляться как по номеру телефона, так и по полю адреса. Любое из полей на рис. 1.1 может использоваться в качестве ключа.

Объектно-ориентированное программирование

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

Если даже после чтения этого раздела и просмотра примеров вся эта затея с ООП останется такой же непонятной, как квантовая физика, вам потребуется более серьезный учебник.

Недостатки процедурных языков

Методология ООП была изобретена из-за того, что процедурные языки (C, Pascal, ранние версии BASIC), как выяснилось, плохо подходят для больших и сложных проектов. Почему, спросите вы?

Проблемы можно условно разделить на два типа: отсутствие соответствия меж- ду программой и реальным миром и внутренняя организация самой программы.

Плохое моделирование реального мира

Процедурные языки не позволяли качественно отразить концептуальную модель реальных ситуаций. Методы выполняют операции, данные хранят информацию, но большинство объектов реального мира делает и то и другое. Скажем, термостат на нагревателе выполняет операции (включение и выключение нагревателя), а также хранит информацию (текущая и предпочтительная температура).
Если написать программу управления термостатом на процедурном языке, ско- рее всего, в ней появятся два метода furnace_on() и furnace_off() и две глобальные переменные currentTemp (значение которой определяется показаниями термометра) и desiredTemp (значение задается пользователем). Однако эти методы и переменные
не формируют никакой программной единицы; в программе нет ничего, что можно было бы назвать общим термином thermostat. Такая концепция существует только в уме программиста.
В больших программах, содержащих тысячи подобных сущностей, процедур- ный подход повышал вероятность ошибок, устраивал хаос, а иногда и вовсе делал реализацию невозможной. Необходим был механизм определения более четких соответствий между объектами программы и объектами реального мира.

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

Объекты в двух словах
Концепция объектов возникла в программном сообществе как средство решения проблем процедурных языков.

Объекты

В основу ООП был заложен революционный принцип: объект содержит как методы, так и переменные. Скажем, объект термостата мог содержать не только методы furnace_on() и furnace_off(), но и переменные currentTemp и desiredTemp. В языке Java такие переменные объектов называются полями.
Новая сущность — объект — решает сразу несколько проблем. Программные объекты не только лучше соответствуют объектам реального мира, но и решают проблемы глобальности данных в процедурной модели. Методы furnace_on() и furnace_off() могут обращаться к переменным currentTemp и desiredTemp. Однако эти переменные остаются скрытыми от методов, не входящих в класс термостата, что снижает вероятность их случайного изменения посторонним методом.

Классы

Сама концепция объекта достаточно революционна, но это еще не все. Довольно быстро пришло понимание того, что у программиста может возникнуть потребность в создании нескольких однотипных объектов. Допустим, вы пишете программу управления нагревателями для целого здания, и эта программа требует создания нескольких десятков объектов термостатов. Было бы крайне неудобно возиться с определением каждого объекта по отдельности. Так родилась идея классов. Класс представляет собой спецификацию («чертеж») для создания одного или нескольких объектов. Например, определение класса термостата на языке Java выглядит примерно так:

Ключевое слово Java class объявляет начало спецификации класса; за ним следует имя, которое вы хотите присвоить классу (thermostat в нашем примере). В фигурные скобки заключены определения полей и методов, составляющих класс. Мы опустили тела методов; обычно каждый метод содержит много строк программного кода.
Программист C скажет, что это определение напоминает определение структур, а программист C++ — что оно очень похоже на определение класса C++, разве что в конце нет символа «;» (хотя так ли уж нужны эти символы в C++?).

Создание объектов

Определение класса не создает никаких объектов этого класса (по аналогии с тем, как определение структуры в коде C не создает никаких переменных). Чтобы создать объект в языке Java, необходимо использовать ключевое слово new. В момент создания объекта ссылка на него должна быть сохранена в переменной подходящего типа (то есть класса).
Что такое ссылка? Мы подробно рассмотрим ссылки позднее, а пока считайте, что это своего рода имя объекта. (На самом деле это адрес объекта, но вам пока это знать не обязательно.)

В следующем фрагменте мы определяем две ссылки на тип thermostat, создаем два объекта thermostat и сохраняем ссылки на них в этих переменных:
thermostat therm1, therm2; // Определение двух ссылок
therm1 = new thermostat(); // Создание двух объектов
therm2 = new thermostat(); // Сохранение ссылок на них
Объекты также часто называются экземплярами классов, а процесс создания объекта — созданием экземпляра.

Вызов методов объекта

После того как вы определите класс и создадите объекты этого класса, какая-то другая часть программы будет взаимодействовать с этими объектами. Как это происходит?
Как правило, другие части программы взаимодействуют с методами объекта, а не с его данными (полями). Например, чтобы приказать объекту therm2 включить нагреватель, используйте синтаксис вида
therm2.furnace_on();
Оператор «точка» (.) связывает объект с одним из его методов (или полей данных).
На данный момент мы рассмотрели (более чем поверхностно) некоторые важнейшие особенности ООП. Подведем итог:

• Объекты состоят из методов и полей (данных).
• Класс представляет собой спецификацию для создания любого количества объектов.
• Объект создается ключевым словом new с указанием имени класса.
• Вызов метода для конкретного объекта осуществляется оператором «точка».

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

Пример объектно-ориентированной программы

Ниже приведена объектно-ориентированная программа, которая реально работает и выдает результаты. Класс BankAccount моделирует текущий счет в банке. Программа создает счет, выводит баланс, осуществляет внесение и снятие средств, после чего выводит новый баланс. Код программы bank.java приведен в листинге 1.1.

Программа bank.java состоит из двух классов. Первый — класс BankAccount — со- держит поля и методы банковского счета (он будет подробно рассмотрен ниже). Второй класс — BankApp — играет особую роль.

Класс BankApp

Чтобы выполнить программу из листинга 1.1 в командной строке M-DOS, введите команду java BankApp в приглашении C:
C:\>java BankApp

Эта команда приказывает интерпретатору java найти в классе BankApp метод с именем main(). Каждое приложение Java должно иметь метод main(); выполнение программы начинается с выполнения main(), как видно из листинга 1.1 (на аргумент String[] args метода main() пока не обращайте внимания).

Метод main() создает объект класса BankAccount и инициализирует его значением 100.00; обе операции выполняются следующей командой:
BankAccount ba1 = new BankAccount(100.00); // Создание счета

Метод System.out.print() выводит строку, передаваемую в аргументе (Before transactions:), а объект счета выводит текущий баланс следующей командой: ba1.display();

Затем программа заносит и снимает средства со счета:

ba1.deposit(74.35);
ba1.withdraw(20.00);

Далее программа выводит новый баланс и завершает работу.

Класс BankAccount

Единственное поле данных класса BankAccount содержит текущую сумму на счету; этому полю присвоено имя balance. Класс содержит три метода. Метод deposit() вносит средства на счет, метод withdrawal() снимает средства со счета, а метод dis- play() выводит баланс.

Продолжение следует...