Майкл Мейн, Уолтер Савитч

 

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

Предисловие

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

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

Второе издание: новый материал и дополнительная поддержка в Интернет

Типы данных и темы изложены в том же порядке, что и в первом издании. Преподаватели, использовавшие его в своей практике, могут продолжать преподавание в том же стиле, учтя следующие изменения, связанные с введением в 1998 году нового стандарта ANSI/ISO C++ Standard. www.cs.colorado.edu/~main/dsoc.html

• Новые материалы, предоставляемые через Интернет. В течение года будет увеличиваться объем нового материала, предоставляемого читателям через Интернет на Web-странице www.cs.colorado.edu/~main/dcos.html. Здесь будут изложены новые задания по программированию, подсказки, касающиеся отладки, а также темы для дополнительного чтения.
• Пространства имен позволяют программисту гарантировать, что выбранные им имена не будут конфликтовать с именами, выбранными другими программистами. Во втором издании стандартное пространство имен описывается в главе 1, а в главе 2 показано, как создавать свои собственные пространства имен.
• Стандартная библиотека шаблонов. Для нас особенно важно, чтобы студент понимал структуры данных на любом уровне: спецификации, проектирования, реализации, тестирования, анализа. Однако в перспективе студенты, продолжившие изучение компьютерных наук, будут широко применять типы данных из стандартной библиотеки шаблонов (Standard Template Library - STL), являющейся частью стандарта языка С++, введенного в 1998 году. Поэтому в книге используется новый класс string, а также некоторые важные компоненты библиотеки .
• Кроме того, создавая свои собственные классы, программист получит дополнительные преимущества, если будет придерживаться общепринятых соглашений. Это облегчит его работу и позволит применить новые свойства, например, библиотеку . С этой целью в текст внесены следующие изменения, касающиеся описания типов данных, с которыми студенты столкнутся, читая этот учебник.
• Выделение прописных букв. Имена всех типов данных в книге записываются с помощью строчных букв (например, stack, queue и т.д.). Согласно инструкциям, описанным в стандартной библиотеке шаблонов, это позволяет нам использовать первую прописную букву имени для задания шаблонного параметра, выделяя его среди остальных идентификаторов.
• Имена функций-членов. В некоторых примерах имена функций-членов изменены для того, чтобы программа соответствовала правилам стандартной библиотеки шаблонов. Для проверки контейнера используется функция empty, для удаления элемента - функция remove, а для подсчета его количества - функция count.
• Ключевое слово const. Связанные списки (глава 5) реализуются с помощью класса node. Легко догадаться, что такой подход немного сложнее, чем используемый в первом издании, однако он оптимизирует применение константных объектов и позволяет достичь согласованности со стандартной библиотекой шаблонов.
• Новые факультативные темы. В книгу добавлено несколько новых факультативных тем. Они предназначены для небольших групп студентов-отличников, и поэтому могут остаться непонятыми большинством студентов с обычной подготовкой. К ним относятся: задание, связанное с полиномами (раздел 4.6), ключевое слово typename (раздел 6.2), класс multset из стандартной библиотеки шаблонов (раздел 6.3), введение в итераторы (разделы 6.3-6.5), значения, возвращаемые по ссылке (разделы 6.5 и 8.5), функции сортировки из стандартной библиотеки языка С++ (раздел 13.4.) и виртуальные методы (раздел 14.3). (Студентам, изучающим программирование в университетах России и Украины, следует иметь в виду, что авторы этого учебника считают "слишком сложными" темы, которые давно стали обычными в наших курсах преподавания языка С++. Их понимание у наших студентов не должно вызвать никаких проблем. - Прим. ред.)

Этапы описания каждого типа данных

В основном второе издание книги, как и прежде, посвящено типам данных, к которым относятся множество (set), мультимножество (bag, или multiset), последовательный список (sequential list), упорядоченный список, для которого определен оператор "меньше" (ordered list), стек (stack), очередь (queue), таблица (table) и граф (graph). Рассматриваются также такие дополнительные типы данных, как очередь с приоритетами (priority qieue). Все эти типы данных описаны по единой схеме.

Этап 1. Абстрактное описание типа данных. На этом этапе студент должен разбираться в типе данных и операциях над ним на уровне понятий и рисунков. Например, студент может изобразить стек и операции заталкивания и выталкивания элементов стека. Нужно понять и решить простые задачи, например, использование стека для изменения порядка следования букв в слове на противоположный.

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

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

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

Поскольку в книге используются классы на языке С++, при реализации типов данных выбранные структуры становятся закрытыми переменными-членами соответствующего класса. Для каждого реализованного класса подчеркивается необходимость четкого понимания правил, которые связывают закрытые переменные-члены с абстрактным типом данных. Эти правила студенты должны формулировать на естественном языке в виде инварианта абстрактного типа данных. Затем они могут реализовывать разные функции-члены. Инвариант помогает правильно создавать функции, поскольку 1) предполагается, что инвариант каждой функции (за исключением конструкторов) выполняется в начале ее работы; 2) каждая функция (за исключением деструктора) должна гарантировать, что инвариант выполняется после завершения ее работы.

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

Что должны знать студенты по завершении курса

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

Типы данных в этой книге представляют собой упрощенные версии типов из стандартной библиотеки шаблонов

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

Другие основные темы

На протяжении курса освещаются и другие аспекты "настоящего програм-мирования".

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

Другие важные аспекты, связанные с классами, вводятся после того, как студенты научатся использовать динамическую память (глава 4). Здесь нужно объяснить три дополнительных понятия: конструктор копирования, перегруженный оператор присваивания и деструктор. Изучение этих вопросов объектно-ориентированного программирования на примере использования динамической памяти дает студентам конкретное представление о ней как о ресурсе, который можно взять, а затем вернуть.

С концептуальной точки зрения наибольшим достоинством объектно-ориентированного программирования является возможность повторного использования программного обеспечения. Есть много вариантов ввода понятия наследования в начале курса (например, реализация класса set как производного от класса bag). Однако если слишком рано ввести наследование, студенты могут утонуть в море новых понятий и не разобраться в основных структурах данных. По этой причине в нашем курсе наследование представлено в самом конце (разделы 14.1 и 14.2). Однако его можно рассматривать сразу после описания конструкторов копирования. Учитывая это, некоторые преподаватели могут излагать материал, содержащийся в главе 14, после описания стеков и очередей.

Студенты, уже овладевшие основами программирования, могут разрабатывать проект, связанный с наследованием (например, моделирование экосистемы из раздела 14.2 или игрового автомата из раздела 14.3), пока остальные студенты осваивают классы.

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

Итераторы. Итераторы - еще одна важная часть стандартной библиотеки шаблонов, облегчающая программисту перемещение по элементам, которые содержатся в контейнере (например, элементам множества или мультимножества). Такие итераторы могут быть внутренними (т.е. реализовываться как функции-члены контейнерного класса) или внешними (т.е. реализовываться в виде отдельного класса, являющегося дружественным контейнерному классу). В книге вводятся внутренние итераторы для одного из первых контейнерных классов (последовательного списка, описанного в разделе 3.2). Затем внутренний итератор добавляется в класс bag (глава 6). Далее обсуждаются более сложные внешние итераторы. В результате этого обсуждения студенты должны убедиться в преимуществах внешних итераторов. На протяжении текста итераторы дают хорошую возможность создавать программные проекты, например, реализовать внешний итератор для класса bag (глава 6) или использовать стек в реализации внутреннего итератора для бинарного дерева (глава 10).

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

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

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

Поиск и сортировка. В главах 12 и 13 освещаются основные вопросы, связанные с алгоритмами сортировки и поиска. Рассматривается бинарный поиск в упорядоченном списке, с которым многие студенты уже знакомы. В главе, посвященной поиску, вводятся также таблицы хеширования. В главе о сортировке описывается простой квадратичный метод сортировки, однако большая часть главы посвящена быстрым алгоритмам: рекурсивной сортировке вставками (наихудшая оценка времени выполнения которой равна O(n log n)), рекурсивная быстрая сортировка Хаара (со средним временем O(n log n)) и сортировка кучи, представленной в виде дерева (наихудшая оценка времени выполнения которой равна O(n log n)). В этой главе впервые описываются функции сортировки из стандартной библиотеки языка С++.

Проекты повышенной сложности

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

• Класс полиномов с использованием динамической памяти 4.6).
• Введение в стандартные итераторы, завершающееся созданием итератора для класса bag (разделы 6.3-6.5).
• Очереди с приоритетами, реализованные в виде связанного списка (раздел 8.4) или с использованием кучи (раздел 11.1).
• Класс set, реализованный на основе B-деревьев (раздел 11.2). Особое внимание было уделено информации, позволяющей студентам разработать этот класс, не прибегая к другим источникам. В нашем курсе мы рекомендуем подготовленным студентам выполнить этот проект в качестве отдельной работы.
• Проект с использованием наследования, например, моделирование экосистемы в разделе 14.2.
• Проект с использованием наследования и абстрактного базового класса, например, класса game в разделе 14.3 (который позволяет легко реализовать такие двусторонние игры, как "Отелло" или "Составь четверку").
• Класс graph и связанные с ними алгоритмы из главы 15. Этот проект представляет собой еще одно задание для самостоятельной работы отличников.

Особенности языка С++

Язык С++ обладает многими особенностями, которые выходят за рамки второго курса. Однако мы стремились полностью осветить те вопросы, которых касались в ходе преподавания. В первом издании этой книги были описаны две особенности языка С++, являвшиеся новыми в то время: новый тип данных bool (раздел 2.1) и статические константные члены (раздел 3.1). В стандарте 1998 года требования, предъявляемые к статическим константным членам, были изменены. Эти изменения были отражены в тексте (теперь константа должна быть объявлена как внутри, так и вне определения класса). Другое основное изменение, внесенное стандартом 1998 года, - использование пространств имен, которое также было включено во второе издание. Оба этих изменения не поддерживаются старыми компиляторами. В этих случаях мы даем соответствующие рекомендации (см. приложение 5 "Работа со старыми компиляторами"), а также предоставляем помощь по загрузке и установке компилятора Gnu g++ (см. приложение 11).

Очередность изложения материала

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

Мы рекомендуем следующую последовательность изложения.

Обычный курс. Начинаем с глав 1-10, пропуская часть главы 2, если студенты уже знакомы с классами языка С++. Большинство глав можно изложить в течение недели, но можно уделить больше времени главе 5 (связанные списки), главе 6 (рекурсия) или главе 10 (деревья). Обычно весь материал излагается за 13 недель, включая время на экзамены и дополнительное изучение списков и деревьев. Оставшееся время можно посвятить выполнению задания, связанного с деревьями из главы 11, или бинарному поиску (раздел 12.1) и сортировке (глава 13).

Курс объектно-ориентированного программирования. Если студенты когда-либо уже изучали алгоритмы поиска и сортировки, можно уделить особое внимание объектно-ориентированному программированию. Сначала детально изучаются первые четыре главы, а затем вводятся производные классы -членам.

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

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

Изучение рекурсии и сортировки в начале курса. От одной до трех недель можно посвятить рассмотрению рекурсии и ее реализации. В этом случае сначала изучаются главы 1 и 9, сопровождаемые дополнительными заданиями, связанными с рекурсией.

Если рекурсия излагается в начале курса, то бинарный поиск (раздел 12.1) и большинство алгоритмов сортировки (глава 13) можно преподавать до введения классов языка С++.

Поддержка через Интернет

Читатели смогут найти в Интернет следующие материалы.

• Все листинги, приведенные в книге, для которых указана соответствующая Web-страница.
• Дополнительные учебные материалы, включая примеры, экзаменационные вопросы и лекции.

Использование Web-броузера. Для получения информации, касающейся доступа к этим материалам, обращайтесь к Web-странице: http://www.cs.colorado.edu/~main/dsoc.html

Дополнительную информацию можно получить в издательстве Addison Wesley, послав письмо по адресам aw.cse@awl.com или main@colorado.edu.

Благодарности

Мы начали писать эту книгу, когда Уолтер гостил у Майкла на факультете компьютерных наук в университете штата Колорадо (г. Боулдер) (University of Colorado in Boulder). Работа была завершена после того, как Уолтер вернулся на факультет технических и компьютерных наук в университете штата Калифорния (г. Сан-Диего) (University of California, San Diego). Мы благодарны обоим университетам за предоставленные технические средства, за прекрасных студентов и возможность общаться с коллегами, близкими нам по духу.

Наши студенты оказали особенно ценную помощь - около 200 человек работали с первоначальными вариантами книги, вносили предложения, объясняли, как они изучают материал. Мы благодарим преподавателей, использовавших наш материал в своих курсах по структурам данных, за ценные замечания: Кэти Бишоп (Cathy Bishop), Мартина Бутшера (Martin Butscher), Джину Черри (Gina Cherry), Кортни Камсток (Courtny Comstock), Джона Джиллета (John Gillett), Ральфа Холлингсворта (Ralph Hollingsworth), Патрика Линна (Patrick Lynn), Эви Немет (Evi Nemeth), Гарри Ната (Gary Nutt), Рика Осборна (Rick Osborne) и Карла Финкельмана (Karl Winklmann). Книга подробно рецензировалась Вольфгангом Байном (Wolfgang Bein), Биллом Хенкли (Bill Hankley), Майклом Миллиганом (Michael Milligan), Джефом Паркером (Jeff Parker), Эндрю Райтом (Andrew Wright), Джоном Роузом (John Rose) и Эваном Цвайфелем (Evan Zweifel).

Мы очень благодарны рецензентам второго издания: Джорджу Бебису (университет штата Невада, г. Рено) (George Babis (University of Nevada, Reno)), Джеймсу Бохи (колледж Симпсона) (James Bohy (Simpson College)), Девиду Челбергу (университет штата Огайо) (David Chelberg (Ohio University)), Зорану Дуричу (университет Джорджа Мейсона) (Zoran Duric (George Mason University)), Хорсоу Кайка (государственный университет Юго-Западного Техаса) (Khorsow Kaikhah (Southwest Texas State University)) и Рику Вагнеру (университет Южной Калифорнии) (Rick Wagner (University of Southern California)). Они выполнили особенно тяжелую работу, поскольку компиляторы, на которые ориентированы приведенные в книге программы, появились недавно.

Мы выражаем благодарность редакторам и сотрудникам издательства Addison Wesly. Элинор Актипис (Elinor Actipis) ежедневно вдохновляла нас и облегчала нам путь к выпуску книги. Мы благодарны Джойс Кочентино (Joyce Cosentino) за прекрасный выбор цвета и дизайн обложки. Элен Рибенакер (Helen Reebenaker) помогала нам на каждом этапе производства, Джина Хейген (Gina Hagen) разработала элементы внутреннего дизайна книги. Спасибо Адриенне Ребелло (Adrienne Rebello) за переплет редакторской версии книги и Майклу Хиршу (Michael Hirsh) за окончательную подготовку материала к публикации. Особую благодарность мы выражаем нашему редактору Картеру Шанкину (Carter Shankin), который работал над книгой с самого начала и постоянно поддерживал нас. В заключение мы благодарим нашего редактора Сюзан Хартман (Susan Hartman) за постоянную поддержку, поощрение и руководство - без нее эта книга не вышла бы в свет!

Кроме людей, работавших над книгой, мы признательны тем, кто проявлял к нашей работе постоянный интерес. Глубочайшая благодарность Лидии Окойн (Lydia Aucoin), Дэвиду Бенсону (David Benson), Стиву Бруксу (Steve Brookes), Полу Чедвику (Paul Chadwick), Эми Кронин (Amy Cronin), Дэну Дорману (Dan Dorman), Анджею Эренфойту (Andrzej Ehrengeucht), Полу Айсенбри (Paul Eisenbrey), Лойду Фосдику (Lloyd Fosdick), Рику Ловелу (Rick Lowell), Джорджу Мейну (George Main), Джиму Мартину (Jim Martin), Джиму Мартину-младшему (Jim Martin Jr.), Остину Мелтону (Austin Melton), Майклу Миллигану (Michael Milligan), Майклу Миславу (Michael Mislove), Филипу Мальри (Philip Mulry), Эви Немет (Evi Nemeth), Кэти Престон (Cathy Preston), Гарри Престону (Harry Preston), Гжегожу Розенбергу (Grzegorz Rozenberg), Дэвиду Шмидту (David Schmidt), Карлу Финкельману (Karl Winklmann), Эвану Цвайфелю (Evan Zweifel), Анне (Hannah), Тимоти (Timothy) и Джанет (Janet).

Майкл Мейн

main@colorado.edu

Боулдер, Колорадо

Уолтер Савитч

wsavitch@ucsd.edu

Сан-Диего, Калифорния

Вернуться к начальной странице