Введение

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

В этом лабораторном практикуме подробно рассмотрены структуры данных и алгоритмы, которые являются фундаментом современной методологии разработки программ. Особое внимание посвящено методам анализа и построения алгоритмов.

Учебное пособие состоит из описания восьми лабораторных работ. Описание каждой лабораторной работы включает цели и постановку задачи, необходимые теоретические сведения, индивидуальные варианты заданий. Тематика лабораторных работ соответствует требованиям, определенным государственным образовательным стандартам по данной дисциплине.

Лабораторная работа №1 посвященна изучению встроенным структурам данных языков программирования Pascal и C. Особое внимание уделяется изучению физического уровня представления этих структур.

Тематика лабораторной работы №2 связана с производными структурами данных, то есть такими структурами, которые реализует сам программист. Ему предлагается создать собственную структуру строкового типа, в соответствии с вариантом задания, и, используя ее, решить указанную задачу.

В лабораторной работе №3 изучаются базовые и улучшенные методы сортировки в основной памяти. Для сравнительного анализа алгоритмов сортировки необходимо реализовать вычислительный эксперимент для построения функции временной сложности и уметь сделать выбор для этих алгоритмов вид порядка функции временной сложности.

Лабораторная работа №4 посвящена сравнительному анализу функции временной сложности и ее порядка алгоритмов поиска.

В лабораторной работе №5 изучается производная структура данных «односвязный линейный список». Созданная студентом эта структура данных используется для решения задачи в соответствии с вариантом.

Лабораторная работа №6 посвящена классическим структурам данных «стек» и «очередь». Они реализуются студентом, причем как отображение на массив, либо как отображение на односвязный линейный список, и затем используются для моделирования модельной вычислительной системы согласно варианту.

В лабораторной работе №7 изучается нелинейная структура данных «бинарное дерево». Эта структура реализуется как в последовательной, так и в связной памяти. Затем она используется для решения задачи, которая указана в варианте заданий.

Лабораторная работа №8 посвящена широко используемой структуре данных «таблица». Эта структура данных реализуется как в линейном, так и в нелинейном варианте. С помощью созданной структуры данных также решается конкретная задача.

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

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

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