Основные концепции структур данных и реализация в С++

Кен Браунси

 

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

Тип издания: Научно-популярное издание Место издания: С.П. Издатель: Компьютерное изд-во "Вильямс" Срок выхода в свет: 2002, 3 кв. Количество страниц: 320, с ил. Сопровод. материалы: Web-сервер ISBN (русск): 5-8459-0313-0 ISBN (англ): 0-1394-8886-3 УДК: 681.3.07 Формат: 60x88/16

Предисловие

Учебные курсы и материал книги

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

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

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

На мой взгляд, предмет структур данных выходит за рамки "традиционного" построения систем на языках программирования общего назначения. Например, когда перед студентами ставится задача проектирования и реализации Web-узлов, то те из них, кто смог овладеть принципами работы со структурами данных, гораздо быстрее понимают возможности нелинейных структур. Их воображение изначально не сковано, и они могут найти выгодные решения. Даже работая над динамическим связыванием страниц средствами Java, они понимают, что задача разрешима, и видят пути к достижению результата.

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

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

На кого рассчитана эта книга

Студенты

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

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

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

Данная книга пригодится обеим категориям, а также тем студентам, которых нельзя причислить ни к одной из них.

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

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

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

Прочие читатели

Для того чтобы получить пользу от чтения данной книги, не обязательно быть студентом. Для этого достаточно иметь компьютер с установленным компилятором C++ и возможность хотя бы один раз обратиться к World Wide Web, чтобы скопировать коды, которые иллюстрируют материал, изложенный в книге. Однако помните, что данная книга не является введением в программирование. Это скорее пособие по курсу структурного программирования. Если же вы начинаете изучение программ "с нуля", обратитесь к пособиям по C++, ориентированным на начинающих.

Для чего написана эта книга

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

Как аргумент против изучения структур данных мне приводят тот факт, что в библиотеках классов для новых языков программирования уже реализованы основные структуры; примером может служить класс Vector в языке Java. Что можно на это возразить? Я сам использую класс Vector, если пишу программу на Java. Но это не значит, что я не должен знать принципы построения динамических последовательных структур данных. Более того, не исключено, что в очередном проекте мне понадобится построить сложнейшую структуру данных, которая наверняка не предусмотрена ни в одной из библиотек классов и не описана ни в одной из книг. Я знаю, как, используя понятие абстрактного типа данных, строить из простых структур более сложные, и благодаря этому могу решать самые различные задачи.

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

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

Выбор языка

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

Среди языков программирования C++ пользуется большой популярностью, но это не значит, что он лучше всех других. На мой взгляд, поддержка объектно-ориентированного подхода гораздо лучше реализована в Eiffel, но, тем не менее, все больше программистов ориентируются на C++. Разрабатывая учебный курс, я старался добиться того, чтобы инструменты и подходы, изучаемые в нем, были наилучшим образом усвоены студентами и, насколько это возможно, помогли им преодолеть недостатки, присущие тому или иному языку программирования. Учитывая, что большинство читателей уже знакомы с C++ и будут использовать его в своей работе, было принято решение иллюстрировать материал книги примерами на этом языке.

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

И, наконец...

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

Кен Браунси

Оксфордский университет Брукса

kwb@brookes.ac.uk

Благодарности и посвящение

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

Я также благодарен редакторам Джеки Харбору (Jackie Harbor) и Кейт Бревин (Kate Brewin) за помощь и большую работу, проделанную ими при подготовке данной книги.

Эта книга посвящается Джейн, Люси и Вильяму. Спасибо вам!

Введение

Шелковая нить

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

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

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

План книги

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

Материал книги иллюстрируется примерами. Примеры представляют собой неотъемлемую часть данной книги и расположены в каталогах по главам. Приступая к чтению книги, необходимо скопировать примеры, обратившись к серверу www.williamspublishing.com. (Если вы хотите получить примеры в том виде, в котором их подготовил автор данной книги, обратитесь по адресу www.booksites.net/brownsey.)

В главе 1 рассматриваются типы данных, вводятся понятие записи (структуры), массива и указателя - трех основных "строительных блоков", из которых создаются структуры данных. В главе 2 вы познакомитесь с абстрактными типами данных, которые объясняются на примере программирования некоторых действий, выполняемых при игре в шашки. Абстрактный тип данных Sequence_T определяется и реализуется на базе массива в главе 3. В главе 4 рассказано о связных списках и показано, как последовательность Sequence_T может быть реализована на их основе. В главе 5 вводится новая линейная структура данных - Stack_T. В этой главе показано, как можно реализовать Stack_T, наложив некоторые ограничения на структуру Sequence_T. Здесь вы также узнаете о применении стеков и познакомитесь со структурой данных Queue_T, реализующей очередь. О рекурсии, ее роли в решении многих практических задач и о переходе от рекурсии к итерации рассказано в главе 6. В главе 7 введено понятие бинарного дерева поиска и показано, как структура BST_T может

Упражнения

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

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