Введение. Основные понятия и определения. 8

Оглавление

Введение………………………………………………………………………………………..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 посвящена широко используемой структуре данных «таблица». Эта структура данных реализуется как в линейном, так и в нелинейном варианте. С помощью созданной структуры данных также решается конкретная задача.

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

Алгоритм = метод + структуры данных

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