Реферат: Упорядоченный массив динамических стеков

1.1. Цель курсовой работы

Получение навыков разработки объектных программ, включая создание набора собственных взаимосвязанных классов для объектной реализации специализированного контейнера. Контейнер предназначен для хранения и обработки данных некоторой информационной задачи (содержание задачи уточняется преподавателем при утверждении темы работы). Контейнер представляет собой двухуровневую структуру данных, в которой уровни реализуются разными способами – один статически на базе массива (непрерывная реализация), другой – динамически с использованием адресных связей (связная реализация).

1.2. Требования к реализации

• Полная объектная реализация с определением классов для всех элементов реализуемой структуры: информационные объекты (обязательно!), объекты-элементы списка (динамическая реализация), объекты-списки, объект-контейнер.

• Соблюдение принципа инкапсуляции – использование в классах только закрытых свойств и реализация необходимого набора методов доступа.

• Реализация в классах всех необходимых методов: конструкторы, методы доступа к свойствам, методы добавления и удаления на каждом из двух уровней, метод поиска (при необходимости).

• Возможность сохранения всей структуры во внешнем файле с обратной загрузкой.

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

• Язык и среда разработки – по выбору: Delphi, Java, C++, С#.

2. Описание алгоритма решения задачи

Массив – это однородная совокупность элементов. Самой распространенной структурой, реализованной практически во всех языках программирования, является массив. Массивы состоят из ограниченного числа компонент, причем все компоненты массива имеют один и тот же тип, называемый базовым. Структура массива всегда однородна. Массив может состоять из элементов типа integer , real или char , либо других однотипных элементов. Из этого, правда, не следует делать вывод, что компоненты массива могут иметь только скалярный тип.

Номер элемента массива называется индексом. Индекс – это значение порядкового типа, определенного, как тип индекса данного массива. Очень часто это целочисленный тип ( integer , word или byte ), но может быть и логический и символьный.

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

Номер элемента массива называется индексом. Индекс – это значение порядкового типа, определенного, как тип индекса данного массива. Очень часто это целочисленный тип ( integer , word или byte ), но может быть и логический и символьный.

Часто бывает необходимо вставлять новые элементы в упорядоченный массив, а также удалять элементы из массива. Такие задачи часто возникают в системах управления базами данных, где пользователи вводят большое количество данных. "Приличная" система должна давать пользователям возможность корректирования введенных данных, т.е. вставки новых данных, изменения уже введенных данных и удаления данных. Задача эта не столь тривиальна, как может показаться на первый взгляд. Пусть необходимо вставить новый элемент x в упорядоченный по возрастанию массив a[1..n] в место с номером k, где k<n. Если просто присвоить a[k]:= x; то элемент с индексом k, который находился там ранее, будет потерян. Следовательно, предварительно необходимо сдвинуть все элементы a[k], a[k+1], …, a[n] на одну позицию вправо. То же самое при удалении элемента из массива. Если удаляется элемент a[k], то все оставшиеся элементы a[k+1], …, a[n] надо сдвинуть на одну позицию влево, чтобы закрыть возникшую "дыру" в k-й позиции массива.

Стек – это структура данных, в которой новый элемент всегда записывается в её начало (вершину) и очередной читаемый элемент также берётся из его начала. Здесь используется принцип “последним пришёл – первым вышел” (LIFO).

Простым примером использования стека может служить ситуация, когда мы просматриваем множество данных и составляем список особых данных, которые должны обрабатываться позднее.

Стек предполагает вставку и удаление элементов, поэтому он является динамической, постоянно меняющейся структурой.

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

Занесение элемента в стек производится аналогично вставке нового элемента в начало списка. Процедура занесения элемента в стек должна содержать два параметра: первый задает вершину стека, в который нужно занести элемент, второй – заносимое значение элемента стека.

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

Стеки довольно часто встречаются в практической жизни. Простой пример: детская пирамидка. Процесс ее сборки и разборки подобен процессу функционирования стека.

Итак, стек – это такой список, добавление или извлечение элементов которого происходит с начала и только с начала (или, возможно, с конца и только с конца) списка.

Значением указателя, представляющего стек, является ссылка на вершину стека, и каждый элемент стека содержит поле ссылки на соседний, "нижний" элемент.