Реализация динамических структур на массиве. Задача реализации одних динамических структур на базе других

Министерство образования Российской Федерации

Нижегородский государственный технический

университет

Кафедра информационных радиосистем

Реализация динамических структур на массиве

Методические указания к лабораторной работе

по дисциплине "Информатика"

для студентов специальностей 200700, 200800

Часть 2

Нижний Новгород 2003

Составили: Е.Н., С.Б.Сидоров, М.В.

УДК 621.325.5-181.4

Реализация динамических структур на массиве: Метод. указания к лабораторной работе по дисциплине "Информатика" (Часть 2) для студентов специальностей 200700, 200800 / НГТУ; Сост.: Е.Н., С.Б.Сидоров, М.В.. Н.Новгород, 2003. 11 с.

Изложены краткие сведения о динамических структурах данных, способах их реализации на массиве. Сформулировано задание к лабораторной работе и порядок ее выполнения.

Научный редактор А.Г.Рындык

Редактор

Подп. к печ.           . Формат 60х84¹/₁₆. Бумага писчая № 1. Печать офсетная.

Нижегородский государственный технический университет.

Типография НГТУ. 603600, Н.Новгород, ул. Минина, 24.
Цель работы и подготовка к работе

Целью работы является практическое изучение методики непрерывной реализации динамической структуры на массиве.

Подготовка к работе осуществляется до прихода в лабораторию и включает в себя изучение данных методических указаний и (если студенту этого не достаточно для прояснения изучаемого материала) рекомендованной в них литературы, подготовку ответов на приводимые контрольные вопросы.

Краткие сведения

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

Будем рассматривать структуры данных (некие сложноорганизованные типы данных), которые представляют собой конечную совокупность некоторых объектов (элементов) одного и того же типа E. Между собой структуры различаются тем, как именно они работают с элементами, т.е. отличаются набором операций над элементами и способом упорядоченности элементов, или, говоря иначе, заданным отношением следования между элементами.

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

Наиболее часто используемыми динамическими структурами являются: стек, динамический вектор, очередь, дек, список, последовательность, множество, дерево, двоичное дерево.

Для каждой динамической структуры кроме отношения следования между элементами определен и набор операций, выполняемых над структурой (не над элементами, а именно над структурой).

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

Для представления динамической структуры может использоваться непрерывная реализация. В этом случае, объекты типа E, входящие в динамическую структуру, будут располагаться последовательно, в соответствующих элементах массива. Элементы массива также будут иметь тип E. Поскольку массив является статической структурой данных, у которой количество элементов должно задаваться при ее описании, то реализованная таким способом динамическая структура может иметь ограниченное количество элементов. Оно определяется количеством элементов массива.

Для непрерывной реализации динамической структуры характерно наличие переменных (целочисленных), значения которых определяют положение структуры данных в массиве. Эти переменные содержат индексы элементов массива, в которых располагаются первый и последний элементы структуры. На рис. 1 приведена графическая иллюстрация общей схемы непрерывной реализации динамической структуры на массиве. Переменная First содержит индекс элемента массива, предшествующего первому элементу структуры, а Last - индекс последнего элемента. Индексы First и Last могут принимать значения от -1 до N-1. Если First = Last = -1, то динамическая структура не содержит элементов.

Рис 1

Рассмотрим некоторые динамические структуры, в частности:

-  стек;

-  очередь;

-  дек.

Основные отличия приведенных динамических структур состоят