УДК 004.65+ 004.43
ББК 32.973
Н 19
Рекомендовано к изданию методическим советом ПГУТИ,
протокол № от . .2015 г.
Рецензент:
профессор кафедры ИВТ ПГУТИ,
к. т. н., доцент Алексеев А. П.
Назаренко, П. А.
Н Алгоритмы и структуры данных: учебное пособие / П. А. Назаренко – Самара :
ПГУТИ, 2015. – 196 с.
Учебное пособие «Алгоритмы и структуры данных» содержит теоретический материал
по основным структурам данных и их практической реализации в языках программирования
Си/Си++ и Паскаль. Приведена классификация структур данных. Рассмотрены основные
алгоритмы обработки структур данных, включая создание и удаление элементов, прохождение,
сортировку и поиск, с их реализациями на языках программирования Си/Си++ и Паскаль.
Учебное
пособие разработано в соответствии с Федеральным государственным образовательным
стандартом высшего профессионального образования по направлению подготовки
02.03.03 – «Математическое обеспечение и администрирование информационных систем»
и предназначено для студентов третьего курса факультета информационных систем и
технологий, а также для студентов других специальностей, изучающих и использующих
структуры данных и алгоритмы их обработки, преподавателей, магистрантов и аспирантов.
ISBN
Назаренко П. А., 2015
3
Стр.3
Введение
Структуры данных – необходимые компоненты любой программы или программного
комплекса. Поэтому знание теории структур данных и, в частности, методов представления
данных на логическом и машинном уровнях, а также допустимых операций над различными
структурами, необходимо для глубокого изучения и уяснения таких разделов, как автоматизированные
системы управления, компиляторы языков программирования, операционные
системы, а также системы программного имитационного моделирования, управления базами
данных, искусственного интеллекта и т.д.
Выбор структур данных является одним из важных этапов разработки программ и от
правильности этого выбора зависит эффективность программы, трудоѐмкость еѐ написания и
время решения программой тех задач, ради которых она создавалась. Это же справедливо и
для алгоритмов обработки данных и их структур. Появление в составе современных языков
программирования библиотек и классов структур данных, например, векторов, списков, различных
видов деревьев, карт и т.п. не отменяет необходимости знания высококвалифицированными
специалистами тонкостей использования этих структур данных и алгоритмов их
обработки. Учебное пособие по дисциплине «Алгоритмы и структуры данных» предназначено
для того, чтобы помочь студентам полнее усвоить соответствующий лекционный курс,
подготовиться к выполнению лабораторных работ по этой дисциплине и заложить основы
дальнейшего более глубокого изучения конкретных алгоритмов обработки данных и вопросов
практического применения специфических структур данных.
Настоящее учебное пособие предназначено для студентов специальностей «Технология
программирования», «Информационные системы и технологии», «Разработка программно-информационных
систем», «Управление и информатика в технических системах» и других.
Предполагается, что студенты, в зависимости от специальности, изучили дисциплины
«Программирование», «Дискретная математика», «Вычислительная математика», «Технология
программирования». Отдельные разделы пособия имеют связь с курсом «Базы данных».
В процессе изучения курса студенты познакомятся с основными типами структур
данных – списковыми, древовидными, сетевыми, файловыми; основными алгоритмами обработки
структур данных – пополнением, удалением, поиском, прохождением, упорядочением;
будут получены навыки разработки алгоритмов обработки структур данных. Текст
учебного пособия разбит на 13 разделов, каждый из которых посвящѐн отдельной группе
структур данных с операциями их обработки, или группе алгоритмов, например, поиску или
сортировке. К сожалению, ограниченный объѐм издания не позволяет подробно рассмотреть
все алгоритмы обработки данных и их структур в их огромном многообразии, но базовые алгоритмы,
составляющие основу этой дисциплины, рассматриваются в обязательном порядке.
Структуры данных и алгоритмы обработки данных и их структур рассматриваются в
большом количество книг и других источников, перечисленных в библиографическом указателе,
все из которых в той или иной степени были использованы при составлении учебного
пособия. Несмотря на то, что отдельные книги были изданы около 40 лет назад, изложенная
в них теория структур данных или алгоритмов их обработки до сих пор не потеряла своего
значения. Некоторые из авторов этих книг являются лауреатами премии Алана Тьюринга,
так же как и создатели отдельных рассматриваемых в пособии алгоритмов.
Библиографический список не претендует на абсолютную полноту, да это и невозможно,
учитывая, что книги по алгоритмам и структурам данных публикуются или переиздаются
практически каждый год. Для углублѐнного изучения структур данных и алгоритмов
предлагается использовать какие-либо из этих источников. Можно, например, порекомендовать
книги Томаса Кормена с соавторами [1], Роберта Седжвика [14 – 18] и подобные [12,
20]. Из многочисленных Интернет-источников выбраны наиболее заслуживающие доверия.
При составлении учебного пособия его автор опирался на требования федерального
государственного образовательного стандарта по дисциплине «Структуры и алгоритмы компьютерной
обработки данных» для специальности «Технология программирования».
6
Стр.6