структуры и алгоритмы обработки данных учебное пособие
AlgStr / Библиотека / Разные источники / Структуры и алг-мы обработки данных Пособие (С-П-г)
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Государственное образовательное учреждение высшего профессионального образования
САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
А. А. Ключарев, В. А. Матьяш, С. В. Щекин
СТРУКТУРЫ И АЛГОРИТМЫ ОБРАБОТКИ ДАННЫХ
УДК 681.3.01 ББК 32.98
Ключарев А. А., Матьяш В. А., Щекин С. В.
К52 Структуры и алгоритмы обработки данных: Учеб. пособие/ СПбГУАП. СПб., 2003. 172 с.: ил. ISBN 5-8088-0120-6
Приводятся описания различных форм организации данных в программах, методов обработки данных в различных классах задач и осуществляется их сравнительный анализ.
Учебное пособие предназначено для изучения теоретического материала дисциплин «Структуры и алгоритмы и обработки данных» и «Структуры и алгоритмы компьютерной обработки данных» студентами
различных форм обучения, проходящих подготовку по специальностям
220400 и 351500 и полностью соответствует требованиям Государ-
ствееных образовательных стандартов по этим специальностям.
кафедра математики и информатики Санкт-Петербургского ин-та Государственной противопожарной службы МЧС России; доктор военных наук профессор В. Ф. Волков
(нач-к каф. автоматизированных систем управления войсками Военно-космической акад. им. А. Ф. Можайского)
Утверждено редакционно-издательским советом университета
в качестве учебного пособия
© ГОУ ВПО «Санкт-Петербургский
В учебном пособии описаны структуры данных и алгоритмы, которые являются основой современного компьютерного программирования. Знание этих структур и алгоритмов позволяет осуществлять выбор наиболее оптимальных способов решения задач, возникающих при создании программного обеспечения различного назначения.
Учебное пособие состоит из трех разделов.
В первом разделе рассматриваются основные понятия алгоритмов и структур данных, а также основные подходы к анализу их сложности.
Во втором разделе приводятся описания различных структур данных
и основных операций над ними. Рассмотрены элементарные типы данных, линейные и нелинейные структуры, а также файлы.
Третий раздел посвящен основным алгоритмам обработки рассмотренных ранее структур данных и анализу сложности этих алгоритмов. Приводятся различные алгоритмы поиска, сортировки, сжатия данных
и алгоритмы на графах, а также обсуждаются методы разработки алгоритмов.
Материал учебного пособия базируется на следующих дисциплинах: «Программирование на языках высокого уровня», «Математическая логика и теория алгоритмов», «Дискретная математика», «Математическое обеспечение программных систем».
Понятия алгоритма и структуры данных
Алгоритм – это точное предписание, определяющее вычислительный процесс, ведущий от варьируемых начальных данных к искомому результату.
ЭВМ в настоящее время приходится не только считывать и выполнять определенные алгоритмы, но и хранить значительные объемы информации, к которой нужно быстро обращаться. Эта информация в некотором смысле представляет собой абстракцию тогог или иного фрагмента реального мира и состоит из определенного множества данных, относящихся к какой-либо проблеме.
Независимо от содержания и сложности любые данные в памяти ЭВМ представляются последовательностью двоичных разрядов, или битов, а их значениями являются соответствующие двоичные числа. Данные, рассматриваемые в виде последовательности битов, имеют очень простую организацию или, другими словами, слабо структурированы. Для человека описывать и исследовать сколько-нибудь сложные данные в терминах последовательностей битов весьма неудобно. Более крупные и содержательные, чем бит, «строительные блоки» для организации произвольных данных получаются на основе понятия «структуры данного».
Под структурой данных в общем случае понимают множество элементов данных и множество связей между ними. Такое определение охватывает все возможные подходы к структуризации данных, но в каждой конкретной задаче используются те или иные его аспекты. Поэтому вводится дополнительная классификация структур данных, которая соответствует различным аспектам их рассмотрения. Прежде чем приступать к изучению конкретных структур данных, дадим их общую классификацию по нескольким признакам (рис. 1).
Понятие «физическая структура данных» отражает способ физического представления данных в памяти машины и называется еще структурой хранения, внутренней структурой или структурой памяти.
Рассмотрение структуры данных без учета ее представления в машинной памяти называется а б с т р а к т н о й или л о г и ч е с к о й структурой. В общем случае между логической и соответствующей ей физической структурами существует различие, степень которого зависит от самой структуры и особенностей той среды, в которой она должна быть отражена. Вследствие этого различия существуют процедуры, осуществляющие отображение логической структуры в физическую и, наоборот, физической структуры в логическую. Эти процедуры обеспечивают, кроме того, доступ к физическим структурам и выполнение над ними различных операций, причем каждая операция рассматривается применительно к логической или физической структуре данных. Кроме того, в зависимости от размещения физических структур, а соответственно, и доступа к ним, различают внутренние (находятся в оперативной памяти) и внешние (на внешних устройствах) структуры данных.
Различаются элементарные (простые, базовые, примитивные) структуры данных и составные (интегрированные, композитные, сложные). Э л е м е н т а р н ы м и называются такие структуры данных, которые не могут быть расчленены на составные части, большие, чем биты. С точки зрения физической структуры важным является то обстоятельство, что в конкретной машинной архитектуре, в конкретной системе программирования всегда можно заранее сказать, каков будет размер элементарного данного и каково его размещение в памяти. С логической точки зрения элементарные данные являются неделимыми единицами.
С о с т а в н ы м и называются такие структуры данных, составными частями которых являются другие структуры данных – элементарные или в свою очередь составные. Составные структуры данных конструируются программистом с использованием средств интеграции данных, предоставляемых языками программирования.
Важный признак составной структуры данных – характер упорядоченности ее частей. По этому признаку структуры можно делить на линейные и нелинейные структуры.
Весьма важный признак структуры данных – ее изменчивость, т. е. изменение числа элементов и/или связей между составными частями структуры. В определении изменчивости структуры не отражен факт изменения значений элементов данных, поскольку в этом случае все структуры данных имели бы свойство изменчивости. По
Лекции Технопарка. 1 семестр. Алгоритмы и структуры данных
Очередной пост в рамках нашего цикла лекций Технопарка. В этот раз мы предлагаем вашему вниманию курс, посвящённый алгоритмам и структурам данных. Автор курса — Степан Мацкевич, сотрудник компании ABBYY.
Лекция 1. Основы
Начало первой лекции посвящено обсуждению основных понятий, на которых строится вся дальнейшая программа курса: что такое алгоритм и структура данных. Описаны базовые виды алгоритмов, их характеристики и методы анализа. Далее рассматриваются примеры создания алгоритмов для вычисления чисел Фибоначчи, проверки числа на простоту, быстрого возведения числа в целую степень. В конце лекции рассказывается об особенностях использования алгоритмов для работы с массивами: создание однопроходных алгоритмов, поиск минимального элемента, бинарный поиск.
Лекция 2. Элементарные структуры данных
Вторая лекция посвящена изучению элементарных структур данных. В начале даётся определение понятия «абстрактного типа данных». Далее лектор рассказывает о том, что такое амортизационный анализ и каковы его особенности.
Лекция 3. Сортировки (часть 1)
Лекция 4. Сортировки (часть 2)
Лекция 5. Хеш-таблицы
Из этой лекции вы сначала узнаете, что такое метод поиска хешированием, какие бывают хеш-функции (в том числе хеш-функции строк). Затем идёт подробное рассмотрение хеш-таблиц и способов их применения: что они собой представляют, каковы основные методы разрешения коллизий (метод цепочек и метод открытой адресации), а также методы вставки, удаления и поиска элементов. Напоследок проводится сравнение хеш-таблиц по затратам времени и памяти.
Лекция 6. Деревья
Последняя лекция в рамках курса АиСД посвящена таким структурам данных, как деревья. Разумеется, в начале лекции дается определение понятия «деревья», рассматриваются их характеристики и приводятся примеры. Затем вы узнаете, как деревья представлены в памяти, какие есть способы обхода дерева. Далее рассматриваются так называемые двоичные деревья поиска и группа самобалансирующихся деревьев: декартовы и АВЛ-деревья. И в завершение лекции рассказывается об абстрактном типе данных «ассоциативный массив».
Структуры и алгоритмы обработки данных. Часть I. Учебное пособие А.Н. БАУШЕВ
Настоящее пособие представляет собой первую часть планируемого кафедрой «Информационные и вычислительные системы» трёхчастного учебного пособия по изучению дисциплины «Структуры и алгоритмы обработки данных» для различных направлений подготовки бакалавров.
Первая часть пособия посвящена традиционным для этой дисциплины разделам – сортировкам массивов и элементарным структурам данных. Сортировки играют важную фундаментальную роль в современных информационных технологиях. Поэтому практически во всех системах программирования имеются встроенные функции сортировки, которые написаны на машинно-ориентированных языках программирования для того, чтобы минимизировать количество машинных тактов, совершаемых процессором во время работы программы сортировки, т.е., для уменьшения времени сортировки.
Однако с педагогической точки зрения задача сортировки массива по-прежнему остаётся чрезвычайно полезной и важной для закладывания у обучающегося основ культуры разработки алгоритмов. Эта задача просто формулируется и, в то же время, существует множество «естественных» алгоритмов для её решения. что позволяет сравнивать между собой различные алгоритмы по основным критериям – времени, затрачиваемым на сортировку, и используемой памятью. Кроме того, задача сортировки массива – одна из немногих задач, для которых известна точная (с точностью до константы) нижняя (по всем возможным алгоритмам) оценка времени работы алгоритма.
Из множества структур данных, встречающихся на практике, автор включил в класс «элементарных» наиболее простые: стек, очередь и список. Более сложные структуры данных и алгоритмы для работы с ними будут рассмотрены во второй части пособия. С неформальной точки зрения, структура данных – это множество (данных), элементы которого снабжены множеством ссылок либо на другие данные (элементы множества), либо (и) на элементы некоторого другого множества – множества признаков (или характеристик) рассматриваемого элемента, либо (и) на другие структуры данных или их элементы. Простота или сложность структуры данных определяется, по существу, простотой или сложностью ссылочной модели, описывающей структуру ссылок для каждого элемента данных. Чем проще ссылочная модель, тем проще решается задача поддержания структуры данных при выполнении основных операций на этих структурах, каковыми являются добавление элемента, поиск элемента, удаление элемента, замена элемента.
Однако простота структуры данных и алгоритмов работы с ними не означает, что основные операции будут выполняться с достаточной (для практики) быстротой. Наоборот, часто исходные простые структуры данных искусственно усложняются для того, чтобы основные операции выполнялись быстрее. Яркой иллюстрацией последнего тезиса является, так называемая, пирамидальная сортировка. Эта сортировка осуществляется в два этапа. На первом этапе из исходной структуры данных – массива – строится более сложная структура – пирамида (или куча), а на втором этапе реализуется алгоритм поддержания этой структуры при удалении вершины из кучи, позволяющий быстро получить отсортированный массив. Оказывается, что время, затрачиваемое на построение кучи и последующее считывание из неё отсортированного массива, существенно меньше (для больших массивов), чем время многих «естественных» сортировок, основанных на попарных сравнениях и обменах местами элементов массива, нарушающих порядок.
В современных научных статьях и монографиях, посвящённых алгоритмам ([1], [2]), алгоритмы описываются в псевдокодах. Использование псевдокодов вызвано желанием авторов подчеркнуть независимость изучаемых объектов (алгоритмов и структур данных) от языков программирования. Однако в учебной практике такой подход неудобен, поскольку для реализации алгоритмов так или иначе приходится использовать какой-либо язык программирования. Поэтому в данном пособии для описания алгоритмов используется язык программирования системы MATLAB, на котором студенты выполняют лабораторные задания. Этот язык прост и прозрачен и, кроме того, не требует объявления типов переменных. Поэтому программы, написанные на нём и не использующие специфических возможностей системы MATLAB, можно, при желании, рассматривать как псевдокоды алгоритмов.
Настоящее пособие написано на основании многолетнего опыта преподавания дисциплины «Структуры и алгоритмы обработки данных» преподавателями кафедры «Информационные и вычислительные системы» ПГУПС. Автор выражаeт благодарность проф. А.Д. Хомоненко, который является инициатором написания данного пособия, и который предоставил автору презентации своих лекций по этой дисциплине.
Структуры и алгоритмы обработки данных Методическое пособие
Ктн е. В. Курапова, кф-мн е. П. Мачикина
Структуры и алгоритмы обработки данных: Учебное пособие. / Сиб. гос. ун-т телекоммуникаций и информатики. – Новосибирск, 2006. – 105 с.
Учебное пособие предназначено для студентов технических специальностей, обучающихся по направлению 210400 «Телекоммуникации» и изучающих дисциплину «Структуры и алгоритмы обработки данных». Пособие содержит необходимый теоретический минимум по данному предмету и варианты заданий для самостоятельного выполнения.
Рисунков 69, таблиц 13. Список лит. –5 назв.
Кафедра прикладной математики и кибернетики.
Рецензент: Зайцев М.Г., Венедиктов М.Д.
Утверждено редакционно-издательским советом СибГУТИ в качестве учебного пособия.
Сибирский государственный университет
телекоммуникаций и информатики, 2006 г.
Оглавление
1.Необходимые понятия и определения 7
1.1Основные структуры данных 7
1.2 Задача сортировки массивов 8
1.3 Трудоемкость методов сортировки массивов 9
1.4 Задача сортировки последовательностей 10
1.5Теорема о сложности сортировки 10
1.6 Задача поиска элементов с заданным ключом 11
2.Методы сортировки с квадратичной трудоемкостью 12
2.1Метод прямого выбора 12
2.2 Пузырьковая сортировка 13
2.3 Шейкерная сортировка 15
2.4 Варианты заданий 17
3.1 Метод прямого включения 18
3.3Варианты заданий 21
4.Быстрые методы сортировки массивов 22
4.1Пирамидальная сортировка 22
4.3Проблема глубины рекурсии. 27
4.4Варианты заданий 28
5.Работа с линейными списками 29
5.1Указатели. Основные операции с указателями 29
5.2Основные операции с линейными списками 30
6.Методы сортировки последовательностей 32
6.1Метод прямого слияния 32
6.2Цифровая сортировка 36
6.3Варианты заданий 37
7.Двоичный поиск в упорядоченном массиве 38
7.1Алгоритм двоичного поиска 38
7.2Варианты заданий 40
8.Сортировка данных с произвольной структурой 40
8.1Сравнение данных произвольной структуры 40
8.2Сортировка по множеству ключей. Индексация 41
8.3Индексация через массив указателей 42
8.4Варианты заданий 42
9.Двоичные деревья 42
9.1Основные определения и понятия 42
9.2Различные обходы двоичных деревьев 43
9.3Вычисление основных характеристик дерева 44
9.4Варианты заданий 45
10.Деревья поиска 45
10.1Поиск в дереве 45
10.2Идеально сбалансированное дерево поиска 46
10.3Варианты заданий 48
11.Случайное дерево поиска 48
11.1Определение случайного дерева поиска 48
11.2Добавление вершины в дерево 49
11.3Удаление вершины из дерева 50
11.4Варианты заданий 52
12.сбалансированные по высоте деревья (АВЛ-ДЕРЕВЬЯ) 52
12.1Определение и свойства АВЛ-дерева 52
12.2Повороты при балансировке 54
12.3Добавление вершины в дерево 56
12.4Удаление вершины из дерева 58
12.5Варианты заданий 62
13.1Определение Б-дерева порядка m 63
13.2Поиск в Б-дереве 64
13.3Построение Б-дерева 65
13.4Определение двоичного Б-дерева 68
13.5Добавление вершины в дерево 69
13.6Варианты заданий 72
14.Деревья оптимального поиска (ДОП) 73
14.1Определение дерева оптимального поиска 73
14.2Точный алгоритм построения ДОП 74
14.3Приближенные алгоритмы построения ДОП 77
14.4Варианты заданий 80
15.Хэширование и поиск 81
15.1Понятие хэш-функции 81
15.2Метод прямого связывания 83
15.3Метод открытой адресации 84
15.4Варианты заданий 86
16.Элементы теории кодирования информации 87
16.1Необходимые понятия 87
16.2Кодирование целых чисел 89
16.3Алфавитное кодирование 92
16.4Оптимальное алфавитное кодирование 95
16.5Почти оптимальное алфавитное кодирование 98
16.6Варианты заданий 102
РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА 103
Рисунок 1 Дерево решений для 6 элементов 10
Рисунок 2 Метод прямого выбора 12
Рисунок 3 Пузырьковая сортировка 15
Рисунок 4 Шейкерная сортировка 16
Рисунок 5 Метод прямого включения 18
Рисунок 6 Метод Шелла 21
Рисунок 7 Добавление в пирамиду нового элемента 22
Рисунок 8 Пирамидальная сортировка 24
Рисунок 9 Метод Хоара 26
Рисунок 10 Схема вызовов при вычислении 4! 27
Рисунок 11 Структура фрейма 28
Рисунок 12 Равенство указателей 29
Рисунок 13 Указатель на элемент списка 30
Рисунок 14 Добавление в стек 31
Рисунок 15 Удаление из стека 31
Рисунок 16 Добавление в очередь 31
Рисунок 17 Структура очереди 32
Рисунок 18 Добавление в очередь 32
Рисунок 19 Перемещение элемента 32
Рисунок 20 Слияние серий 33
Рисунок 21 Метод прямого слияния 34
Рисунок 22 Начальное расщепление 34
Рисунок 23 Цифровая сортировка 36
Рисунок 24 Первая версия поиска 38
Рисунок 25 Вторая версия поиска 39
Рисунок 26 Список абонентов 40
Рисунок 27 Пример двоичного дерева 43
Рисунок 29 Дерево поиска 45
Рисунок 30 Примеры ИСД и неИСД 46
Рисунок 31 Построение ИСДП 47
Рисунок 32 Случайное дерево поиска 49
Рисунок 33 Плохие СДП 49
Рисунок 34 Добавление вершины В 50
Рисунок 35 Добавление вершины 9 50
Рисунок 36 Варианты удаления вершин 51
Рисунок 37 Удаляемая вершина с двумя поддеревьями 51
Рисунок 38 Порядок изменения указателей при удалении вершины 51
Рисунок 39 Пример АВЛ-дерева и не АВЛ-дерева 53
Рисунок 40 Деревья Фибоначчи 53
Рисунок 42 LR – поворот 55
Рисунок 43 RR – поворот 56
Рисунок 44 RL – поворот 56
Рисунок 45 Построение АВЛ-дерева 58
Рисунок 46 Три случая при удалении вершины из левого (для BL) поддерева 59
Рисунок 47 Три случая при удалении вершины правого (для BR) поддерева 60
Рисунок 48 Удаление из АВЛ-дерева 62
Рисунок 49 Страница Б-дерева 64
Рисунок 50 Пример Б-дерева 64
Рисунок 51 Структура страницы Б-дерева 65
Рисунок 52 Построение Б-дерева 66
Рисунок 53 Виды вершин ДБД 68
Рисунок 54 Вершины двоичного Б-дерева 68
Рисунок 55 Четыре ситуации, возникающих при росте левых или правых поддеревьев 70
Рисунок 56 Построение двоичного Б-дерева 72
Рисунок 57 Различные деревья поиска с вершинами V1=1, V2=2, V3=3 74
Рисунок 58 ДОП для w1=60, w2=30, w3=10 76
Рисунок 59 Дерево, построенное приближенным алгоритмом А1 79
Рисунок 60 Дерево, построенное приближенным алгоритмом А2 80
Рисунок 61. Отображение H: K→A 81
Рисунок 62. Хэш-таблица, построенная методом прямого связывания 84
Рисунок 63. Использование квадратичных проб 86
Рисунок 64 Полное двоичное дерево с помеченными вершинами 93
Рисунок 65 Построение префиксного кода с заданными длинами 94
Рисунок 66 Процесс построения кода Хаффмена 97
Рисунок 67 Кодовое дерево для кода Хаффмена 97
Рисунок 68 Кодовое дерево для кода Фано 100
Таблица 1 Различные типы данных 7
Таблица 2 Основные операции с указателями 29
Таблица 3 Частоты вхождения символов в строку 78
Таблица 4 Упорядоченный набор вершин 79
Таблица 5. Номера символов строки 86
Таблица 6 Код класса Fixed + Variable 89
Таблица 7 Код класса Variable + Variable 90
Таблица 8 γ-код Элиаса 90
Таблица 9 ω-код Элиаса 91
Таблица 10 Код Хаффмена 97
Таблица 11 Код Шеннона 99
Таблица 12 Код Фано 100
Таблица 13 Код Гилберта-Мура 101
Тут вы можете оставить комментарий к выбранному абзацу или сообщить об ошибке.
Структуры данных и алгоритмы их обработки на языке программирования Паскаль. Учебное пособие
Скачать книгу
О книге «Структуры данных и алгоритмы их обработки на языке программирования Паскаль. Учебное пособие»
Учебное пособие предназначено для изучения теоретического материала и выполнения лабораторных работ при изучении дисциплин «Алгоритмы и алгоритмические языки», «Структуры и алгоритмы обработки данных». Материал книги условно разбит на две части: язык программирования Паскаль и структуры данных. Описание языка включает: алфавит, структуру программ, типизацию данных, операторы, ввод/вывод данных, алгоритмические структуры, подпрограммы, процедуры и функции, типы данных, массивы, работу с файлами. При рассмотрении структур данных описываются структуры прямого и последовательного доступа, сортировка массивов, линейные списки и двоичные деревья, включая операции с ними. Рассмотрение типов данных и управляющих структур сопровождается графическими схемами и диаграммами, способствующими лучшему пониманию изучаемого материала. Вопросы и задания лабораторных работ также могут использоваться для организации практических и самостоятельных работ. Материалы книги будут полезны учителям информатики средних и специальных учебных заведений, готовящих специалистов в области информатики и вычислительной техники. На сайте издательства находится электронный архив с исходными кодами примеров программ. Для студентов и преподавателей профильных вузов.
На нашем сайте вы можете скачать книгу «Структуры данных и алгоритмы их обработки на языке программирования Паскаль. Учебное пособие» В. А. Касторнова бесплатно и без регистрации в формате pdf, читать книгу онлайн или купить книгу в интернет-магазине.