Наброски и зарисовки растений, плодов, цветов: Освоить конструктивное построение структуры дерева через зарисовки отдельных деревьев, группы деревьев...
Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...
Топ:
Эволюция кровеносной системы позвоночных животных: Биологическая эволюция – необратимый процесс исторического развития живой природы...
Генеалогическое древо Султанов Османской империи: Османские правители, вначале, будучи еще бейлербеями Анатолии, женились на дочерях византийских императоров...
Комплексной системы оценки состояния охраны труда на производственном объекте (КСОТ-П): Цели и задачи Комплексной системы оценки состояния охраны труда и определению факторов рисков по охране труда...
Интересное:
Лечение прогрессирующих форм рака: Одним из наиболее важных достижений экспериментальной химиотерапии опухолей, начатой в 60-х и реализованной в 70-х годах, является...
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Средства для ингаляционного наркоза: Наркоз наступает в результате вдыхания (ингаляции) средств, которое осуществляют или с помощью маски...
Дисциплины:
2021-04-18 | 80 |
5.00
из
|
Заказать работу |
|
|
Структуры и алгоритмы обработки данных. Часть 1: Учеб. пособие. - Вологда: ВоГТУ, 2005. – 232 с.
ISBN 5-87851-152-5
Учебное пособие предназначено для студентов специальности 230105 – программное обеспечение вычислительной техники и автоматизированных систем, но может быть полезно студентам всех специальностей, связанных с компьютерными технологиями. Первая часть содержит определение основных понятий, анализ и реализацию линейных и иерархических структур данных и алгоритмов сортировки и поиска.
УДК 681.3.06
ББК Р23
©Вологодский государственный
технический университет, 2005
ISBN 5-87851-152-5 ©Ржеуцкая С.Ю.,
Андрианов И.А.
Введение
Пособие предназначено для студентов специальности 230105 — «Программное обеспечение вычислительной техники и автоматизированных систем», но может использоваться студентами других специальностей, связанных с компьютерными технологиями, в качестве дополнительного материала.
Исследование структур данных и алгоритмов их обработки — это основа, на которой держатся все остальные компьютерные науки. Грамотное решение задач в любой области программирования невозможно без обширных и прочных знаний типовых структур данных и алгоритмов.
Несмотря на динамичное развитие различных направлений информационных технологий, в этой области положение довольно стабильно. Конечно, новые задачи часто требуют нестандартных решений, поэтому набор востребованных структур данных и алгоритмов постоянно пополняется. Тем не менее, основные способы организации данных и алгоритмы их обработки хорошо проработаны, имеется несколько фундаментальных учебников и монографий по этому вопросу, например [7,9,2,13].
|
При изложении авторы в основном ориентируются на известные, много раз переиздававшиеся фундаментальные работы. Мы старались изложить лаконично и систематизированно материал, почерпнутый из большого количества источников, дополнить его собственными примерами и сведениями о современном состоянии некоторых проблем. Иногда в различных источниках встречается несогласованность терминологии. В этом случае употребляются наиболее распространенные термины, а остальные все-таки упоминаются со ссылкой на авторов.
Все примеры в пособии написаны на языке С++, при этом авторы старались сделать тексты программ понятными, поэтому использовали такие конструкции языка, которые не затрудняют чтение исходных текстов. Мы стремились показать различные подходы к программированию алгоритмов обработки данных, поэтому там, где это уместно, использовался объектно-ориентированный подход и шаблоны. Сделано и небольшое введение в функциональное программирование в разделах, посвященных рекурсивной обработке линейных и иерархических списков.
Пособие содержит десять глав. В первой из них определяются основные понятия и дается первое введение в анализ алгоритмов. Вторая и третья главы содержат довольно подробное описание линейных и иерархических структур данных с примерами реализации. Три следующих главы посвящены практически важным задачам сортировки и поиска данных, причем в шестой главе рассматриваются способы сортировки и поиска данных во внешней памяти. Затем разбирается обширная группа методов и алгоритмов для решения задач дискретной оптимизации под общим названием «исчерпывающий поиск». Восьмая глава посвящена классическим алгоритмам на графах. В следующей главе разбираются алгоритмы поиска в текстовых последовательностях, которые в последнее время приобретают повышенную актуальность в связи с массовым распространением поисковых систем. Наконец, последняя глава содержит введение в NP-полные задачи и способы их приближенного решения.
|
Представленный материал полностью охватывает программу курса «Структуры данных и алгоритмы обработки» и может использоваться в качестве учебника по данной дисциплине.
В качестве дополнения к пособию следует использовать методические указания по структурам и алгоритмам обработки данных, в которых содержатся практические задания.
1. Основные понятия и определения
Первая глава является вводной и посвящена определению основных понятий.
Разумеется, способы организации данных и алгоритмы их обработки нельзя рассматривать отдельно друг от друга. Однако в рамках данной главы полезно сначала сосредоточиться на терминологии, которая относится к определению данных, а затем разобрать наиболее фундаментальные понятия, касающиеся алгоритмов. Здесь уместно привести высказывание Фредерика П.Брукса. «Покажите мне ваши блок-схемы и спрячьте таблицы, и я ничего не пойму. Покажите мне таблицы, и блок-схемы мне не понадобятся — все будет очевидно и так.» Таблицы (дословный перевод английского tables) — это структуры данных, а блок-схемы — способ записи алгоритмов. Иными словами, выбор структур данных определяет используемые алгоритмы. Возможно, это чересчур упрощенный подход, но важность грамотного выбора способов организации данных нельзя оспорить[14].
Существует несколько фундаментальных понятий, которые относятся к определению данных. Это типы данных, абстрактные типы данных и структуры данных. Разберем данные понятия по порядку.
1.1. Типы данных
Понятие типа данных
Понятие типа данных хорошо проработано в начальном курсе программирования, поэтому кратко остановимся только на тех моментах (и терминологии), которые важны для дальнейшего изложения.
Любая переменная, константа, а также значение выражения или функции относятся к определенному типу данных.
Тип данных о пределяет множество допустимых значений данных и множество операций над этими значениями.
Все типы данных, используемые в языках высокого уровня, можно разделить на две большие группы:
· скалярные (простые);
· структурированные (составные, конструируемые).
Скалярные типы, в свою очередь, делятся на несколько групп:
· базовые (встроенные в язык), т. е. типы, предопределенные в языке программирования;
|
· производные от базовых (например, перечисляемый тип или диапазон в языке Pascal);
· ссылочные типы (указатели), обеспечивающие возможность работы с множеством абстрактных адресов памяти.
Структурированные (конструируемые) типы имеют в своей основе скалярные типы данных и используются для определения совокупностей данных. В языке программирования предопределены средства спецификации таких типов и некоторый набор операций, дающих возможность доступа к отдельным элементам составных значений.
Большинство языков программирования представляет стандартный набор структурированных типов:
· массивы (в том числе строки — массивы символов);
· записи (в языке С они называются структурами, аналоги записей с вариантами — объединения);
· в некоторых языках, например в Pascal, есть множества.
Важно отметить, что в языке высокого уровня внутреннее представление типа данных скрыто от программиста, а доступ к значениям типа осуществляется через предопределенный набор операций, реализация которых также скрыта. Такой принцип называется инкапсуляцией, и это обозначает, что внутреннее представление данных как бы заключено в непроницаемую капсулу, а доступным является лишь внешнее представление типа, содержащееся в описании языка.
Внутреннее представление данных, размер выделяемой памяти и реализация операций предоставляются на усмотрение разработчиков компиляторов. Единственное, что предоставляют практически все языки программирования, — операция sizeof(тип) для определения размера области памяти, отводимой под переменную заданного типа.
Все же полное незнание внутренего представления стандартных типов в языках высокого уровня может привести к многочисленным ошибкам при реализации алгоритмов. Поэтому очень кратко остановимся на этом вопросе.
|
|
Опора деревянной одностоечной и способы укрепление угловых опор: Опоры ВЛ - конструкции, предназначенные для поддерживания проводов на необходимой высоте над землей, водой...
Типы оградительных сооружений в морском порту: По расположению оградительных сооружений в плане различают волноломы, обе оконечности...
Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...
Археология об основании Рима: Новые раскопки проясняют и такой острый дискуссионный вопрос, как дата самого возникновения Рима...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!