Вход

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

Реферат по компьютерным сетям
Дата создания: 08.02.2012
Автор: qivo
Язык реферата: Русский
Word, docx, 27 кб
Реферат можно скачать бесплатно
Скачать

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), тоже возможно только из вершины стека, при этом второй сверху элемент становится верхним.

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

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

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

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

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

© Рефератбанк, 2002 - 2017