Оглавление
Введение………………………………………………………………………………………..6
Основные понятия и определения……………………...……………………………………..8
Лабораторная работа №1. Встроенные структуры данных (Pascal/С)...……………….…..11
Задание……………………………………………………………………………….......11
Содержание отчета……………………………….……………………………..……....15
Теоретические сведения…………………………………….……………………...…...15
Простые типы данных в Pascal……..…………………………...…………….…….15
Целые типы…………………………………………………...…..……...…….15
Символьный тип (char) …..……………………..………………………...…..15
Логический тип (boolean)…………………………….…………………...…..16
Перечисляемый тип…………………………….………………………...…...16
Тип-диапазон…………………………………….………………………...…..16
Вещественные типы………………………….………………………..……...16
Сложный тип…………………………………………………………...……..18
Простые типы данных в C…………………………………………………………..18
Целые типы………………….………………………………………......…….18
|
|
Символьный тип ………………………………………………………...……19
Перечисляемый тип..…..………………………………………………...…...19
Вещественные типы………………………………………………...………..20
Структурированные типы данных в Pascal………….……………………………..21
Массив…………………………………………………….…………...………21
Структура данных типа «запись»……………………….…………...………21
Структура данных типа «множество»……………………….……..……….22
Структурированные типы данных в C…………..…………………………..……..23
Структура данных типа «массив»…………………….………………..……23
Структура данных типа «структура»…….……………………………...…..24
Контрольные вопросы..………………………………………………………………………25
Лабораторная работа № 2. Производные структуры данных. Структура данных
«строка» (Pascal/С)……….……………………………………………………..………….……...26
Задание………………………………………….………………………………….…….26
Содержание отчета……………………………………………………...………….…....42
Теоретические сведения…………………………………………………...……….…...42
Контрольные вопросы..……………………………………………………………………...47
Лабораторная работа № 3. Сравнительный анализ методов сортировки
(Pascal / С)…………………………….…………...…………………….….…………………….....47
Задание………………………………………..…………………………………………...47
Содержание отчета………………………………………..……………………...……….49
Теоретические сведения……………………………………….…………...………….....49
Сортировка включением.…………………………………...……………….…….50
Анализ сортировки включением………………………….………….……………51
|
|
Сортировка выбором ……………………………………………………………....51
Анализ сортировки простым выбором…….……………………………….……..52
Сортировка обменом ………………………………………………………….…...53
Анализ сортировки обменом………………………………………………….…..53
Улучшенная сортировка обменом 1………………………………………….…..54
Анализ улучшенной сортировки обменом 1………………………….…….……54
Улучшенная сортировка обменом 2…………………………………….………..54
Анализ улучшенной сортировки обменом 2…………………………….……...54
Сортировка Шелла………………………………………………………….……..54
Анализ сортировки Шелла……………………………………………….……….55
Сортировка Хоара………………………………………………………….……...56
Анализ сортировки Хоара………………………………………………….……..56
Пирамидальная сортировка..……………………......………………….…….…...57
Анализ пирамидальной сортировки.……………...……………………………...60
Примеры программной реализации алгоритмов сортировки на
языке Pascal………………………………………………………………………………………...60
Примеры программной реализации алгоритмов сортировки на
языке C……………………………………………………………………………………………...65
Контрольные вопросы..………………………………….…….…………………………….…69
Лабораторная работа № 4. Сравнительный анализ алгоритмов поиска
(Pascal / С)……..…….….….………………..………………….……………………………..………70
Задание……………………………………………………..………...…………………....70
Содержание отчета………………………………………………………..…………........70
Теоретические сведения……………………………………………………...…………..72
Алгоритмы поиска в неупорядоченных массивах…………………….…………..72
Алгоритм линейного поиска……………………………….….……………….72
Алгоритм быстрого линейного поиска…………………………….……….…72
Анализ алгоритмов линейного поиска.……………………………………….72
Алгоритмы поиска в упорядоченных массивах……………………………..…….73
Алгоритм быстрого линейного поиска………………………………………73
Алгоритм бинарного поиска…………………………………………..……...73
Анализ алгоритма бинарного поиска…………………………………….…..74
Алгоритм блочного поиска…………………………………………………...74
Анализ алгоритма блочного поиска………………………………………….74
Контрольные вопросы..………………………………………………………………………75
Лабораторная работа №5. Структуры данных «линейные списки»
(Pascal/С)….….………...…….……………………………….………………….…………..……....76
Задание………………………………………………..…………………………...…...…76
Содержание отчета..…………………………...…………………………………..…....93
Теоретические сведения ………………….……………………………………..….…...93
Контрольные вопросы..….……….…….………………………………………………………97
Лабораторная работа №6. Структуры данных «стек» и «очередь»
(Pascal/С)…..…………..….…………………….……..…………..……………………….…….…..98
Задание…………………………………………………………………………..….…...98
Содержание отчета…………………………………….…………………….…..…….137
Теоретические сведения……………………………………….………………..…….137
Стек………………………………………………………………………………….137
Очередь……………………………………………………………………………...140
Контрольные вопросы..………………………………………………………………….……143
Лабораторная работа №7. Структуры данных «дерево»
(Pascal/С)………………..……………………………………………..…………………….….…..144
Задание…………………………………………………………………..…….….…….144
Содержание отчета…………………………..…………………………..……………..161
Теоретические сведения…………………………..……………………..………….....161
Принципы размещения бинарного дерева в памяти ЭВМ…………………........163
Алгоритмы обхода бинарного дерева………….……………………...……….....165
Обход бинарного дерева «в глубину» (в прямом порядке)..………………165
|
|
Обход бинарного дерева «в ширину» (по уровням)………………………..166
Обход бинарного дерева в симметричном порядке …………………….….166
Обход бинарного дерева в обратном порядке………………………….…...167
Алгоритмы формирования бинарного дерева……………………………..…..…167
Рекурсивный алгоритм формирования бинарного дерева
«в глубину»…...…………………...………………………………………………………………..168
Итеративный алгоритм формирования бинарного дерева
«в глубину»……..……….….……………….………………………………………………….…..168
Алгоритм формирования бинарного дерева «в ширину»..………………..169
Алгоритм формирования бинарного дерева «снизу вверх»..……………..169
Рекурсивный алгоритм формирования бинарного дерева..………………170
Итеративный алгоритм формирования бинарного дерева..………………170
Алгоритм формирования бинарного дерева минимальной
высоты…………………………………………………………………………..…….….…...…….171
Итеративнй алгоритм формирования сбалансированного
бинарного дерева…………………………..………………………………………...………….…172
Представление алгебраических выражений бинарными
деревьями……………………………………………………………………………………...……172
Алгоритм формирования бинарного дерева по прямой
польской записи…………………………………………………..………………………….…….173
Алгоритм формирования бинарного дерева по обратной
польской записи………….…….….………………...………………………………………….….173
Контрольные вопросы..…………………………………………………………………….…173
Лабораторная работа №8. Структуры данных «таблица» (Pascal/С)….....……....…..174
Задание..………………………………………………………...…………...………….174
Содержание отчета ………………………………….………………………………….197
Теоретические сведения …………………………………….………………...……….198
Контрольные вопросы..…………………………………………………………………….…202
Библиографический список...……………………………………..…………………..…..….203
Введение
Структуры данных являются неотъемлемой частью любого программного продукта. При разработке программы необходимо определить множество данных, описывающих конкретную задачу и составить алгоритм решения задачи. В зависимости от назначения программы данные могут иметь разный уровень сложности или организованности, начиная с простых типов, представляющих собой числа или символы, и заканчивая файлами и системами файлов достаточно сложной структуры. Изучение структур данных, правильный выбор их в зависимости от выполняемых операций, размера требуемой для структур памяти, частоты использования структур при выполнении программы позволяет повысить эффективность разрабатываемых программ, уменьшить время и стоимость программной разработки. Знание теории структур данных и методов представления данных на логическом и физическом уровне необходимо для изучения таких дисциплин направления «Программная инженерия», как «Операционные системы и сети», «Базы данных», «Конструирование программного обеспечения».
|
|
В этом лабораторном практикуме подробно рассмотрены структуры данных и алгоритмы, которые являются фундаментом современной методологии разработки программ. Особое внимание посвящено методам анализа и построения алгоритмов.
Учебное пособие состоит из описания восьми лабораторных работ. Описание каждой лабораторной работы включает цели и постановку задачи, необходимые теоретические сведения, индивидуальные варианты заданий. Тематика лабораторных работ соответствует требованиям, определенным государственным образовательным стандартам по данной дисциплине.
Лабораторная работа №1 посвященна изучению встроенным структурам данных языков программирования Pascal и C. Особое внимание уделяется изучению физического уровня представления этих структур.
Тематика лабораторной работы №2 связана с производными структурами данных, то есть такими структурами, которые реализует сам программист. Ему предлагается создать собственную структуру строкового типа, в соответствии с вариантом задания, и, используя ее, решить указанную задачу.
В лабораторной работе №3 изучаются базовые и улучшенные методы сортировки в основной памяти. Для сравнительного анализа алгоритмов сортировки необходимо реализовать вычислительный эксперимент для построения функции временной сложности и уметь сделать выбор для этих алгоритмов вид порядка функции временной сложности.
Лабораторная работа №4 посвящена сравнительному анализу функции временной сложности и ее порядка алгоритмов поиска.
В лабораторной работе №5 изучается производная структура данных «односвязный линейный список». Созданная студентом эта структура данных используется для решения задачи в соответствии с вариантом.
Лабораторная работа №6 посвящена классическим структурам данных «стек» и «очередь». Они реализуются студентом, причем как отображение на массив, либо как отображение на односвязный линейный список, и затем используются для моделирования модельной вычислительной системы согласно варианту.
В лабораторной работе №7 изучается нелинейная структура данных «бинарное дерево». Эта структура реализуется как в последовательной, так и в связной памяти. Затем она используется для решения задачи, которая указана в варианте заданий.
Лабораторная работа №8 посвящена широко используемой структуре данных «таблица». Эта структура данных реализуется как в линейном, так и в нелинейном варианте. С помощью созданной структуры данных также решается конкретная задача.
Чтобы еще раз подчеркнуть важность правильного выбора структуры данных можно воспользоваться следующей формулой:
Алгоритм = метод + структуры данных
Термин «метод» будет обозначать множество алгоритмов, объединенных главной идеей. Появление нового метода – это событие и событие крайне редкое, ведущее обычно к радикальному ускорению обработки данных. Внедрение новых композиций структур данных, напротив, ярким событием не является, но зачастую в несколько раз уменьшает время обработки данных без изменения метода.