Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

КУРСОВАЯ РАБОТА

Реализация динамических структур данных: стек, очередь

Введение

Для решения многих практических задач используются структуры данных - массив, запись, множество и так далее. Цель описания типов данных и последующего описания переменных, как относящихся к этому типу, состоит в том, чтобы зафиксировать на время выполнения программы размер значений, которые присваиваются этим переменным и, соответственно, фиксировать размер выделяемой области памяти для них. Такие переменные называются статическими. Вследствие фиксирования размера выделенной памяти возникают определенные трудности: неэффективное использование оперативной памяти. Нам, во многих случаях, заранее не известны значения той или иной переменной, и даже факт существования этого значения. Для решения задач мы можем использовать только статические переменные, но мы не знаем значения результата и его размеры, поэтому нам бы пришлось выделять место в памяти для максимально возможного итогового значения, что приводит к нерациональному использованию памяти машины.

Цель моей работы дать реальное осознание того, что использование динамических величин имеет немалое значение, так как предоставляет программисту ряд дополнительных возможностей. В процессе работы программы специальной процедурой программист может запросить у системы некоторый объ?м памяти, а после использования (также специальной процедурой) возвратить е? системе, т.е. динамическое управление памятью - это выделение памяти во время выполнения программы. Эффективное исполнение задач реализуется в некоторых случаях при использовании стеков, в других деревьев и т.д. В этой работе представлен обзор стеков и очередей. Рассматриваются способы их реализации в различных задачах при определенных условиях. Наглядно представлены схемы и практические примеры реализации стека и очереди.

1. Структуры данных

1.1 Информация и данные

динамический массив стек очередь

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

Виды форм представления информации:

- по способу отображения: символьная (знаки, цифры, буквы); графическая (изображения); текстовая (набор букв, цифр) и звуковая;

- по месту появления: внутренняя (выходная) и внешняя (входная);

- по стабильности: постоянная и переменная;

- по стадии обработки: первичная и вторичная.

Независимо от содержания и сложности любые данные в памяти ЭВМ представляются последовательностью двоичных разрядов, или битов, а их значениями являются соответствующие двоичные числа. Для человека описывать и исследовать сколько-нибудь сложные данные в терминах последовательностей битов весьма неудобно. Более крупные и содержательные, нежели бит, «строительные блоки» для организации произвольных данных получаются на основе понятия «структуры данного».

1.2 Понятие структуры данных. Динамические структуры данных

Структура данных - программная единица, позволяющая хранить и обрабатывать множество однотипных и / или логически связанных данных в вычислительной технике. Для добавления, поиска, изменения и удаления данных структура данных предоставляет некоторый набор функций, составляющих ее интерфейс. Одним из простых примеров структуры данных может служить пример структуры данных бинарное дерево: Рисунок 1.2 - Бинарное дерево, простой пример ветвящейся связной структуры данных.

Рисунок 1.2 - Бинарное дерево, простой пример ветвящейся связной структуры данных

Итак, структура данных:

- это форма хранения и представления информации

- работает с однотипными и / или логически связанными данными

- поддерживает определенный порядок доступа к данным

Примеры структур данных:

- линейные: массив, список, связанный список, стек, очередь, хэш-таблица;

- иерархические: двоичные деревья, n-арные деревья, иерархический список;

- сетевые: простой граф, ориентированный граф;

- табличные: таблица реляционной базы данных, двумерный массив;

- другие.

Структуры данных характеризуются:

- временем: добавления, поиска и удаления элемента;

- памятью: общая занимаемая память («полезная» память).

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

Динамическая структура данных характеризуется тем что:

- она не имеет имени;

- ей выделяется память в процессе выполнения программы;

- количество элементов структуры может не фиксироваться;

- размерность структуры может меняться в процессе выполнения программы;

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

Порядок работы с динамическими структурами данных следующий:

- создать (отвести место в динамической памяти);

- работать при помощи указателя;

- удалить (освободить занятое структурой место).

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

1.3 Классификация динамических структур данных

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

- однонаправленные (односвязные) списки;

- двунаправленные (двусвязные) списки;

- циклические списки;

- стек;

- дек;

- очередь;

- бинарные деревья.

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

Каждая компонента любой динамической структуры представляет собой запись, содержащую, по крайней мере, два поля: одно поле типа указатель, а второе - для размещения данных. В общем случае запись может содержать не один, а несколько указателей и несколько полей данных. Поле данных может быть переменной, массивом или структурой.

Элемент динамической структуры состоит из двух полей:

- информационного поля (поля данных), в котором содержатся те данные, ради которых и создается структура;

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

Объявление элемента динамической структуры данных выглядит следующим образом:

struct имя_типа {

информационное поле;

адресное поле;

};

Например:

struct TNode {

int Data; // информационное поле

TNode *Next; // адресное поле

};

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

Рисунок 1.4 - Схематичное представление динамической структуры

Данная структура состоит из 4 элементов. Ее первый элемент имеет поле Data, равное 73, и связан с помощью своего поля Next со вторым элементом, поле Data которого равно 28, и так далее до последнего, четвертого элемента, поле Data которого равно 85, а поле Next равно NULL, то есть нулевому адресу, что является признаком завершения структуры. Здесь P - указатель, который указывает на первый элемент структуры.

Элемент динамической структуры в каждый момент может либо существовать, либо отсутствовать в памяти, поэтому его называют динамическим. Поскольку элементами динамической структуры являются динамические переменные, то единственным средством доступа к динамическим структурам и их элементам является указатель (адрес) на место их текущего расположения в памяти. Таким образом, доступ к динамическим данным выполняется специальным образом с помощью указателей. Указатель содержит адрес определенного объекта в динамической памяти. Адрес формируется из двух слов: адрес сегмента и смещение. Сам указатель является статическим объектом и расположен в сегменте данных: Рисунок 1.5 - Связь указателя с адресуемым объектом.

Рисунок 1.5 - Связь указателя с адресуемым объектом

Для обращения к динамической структуре достаточно хранить в памяти адрес первого элемента структуры. Поскольку каждый элемент динамической структуры хранит адрес следующего за ним элемента, можно, двигаясь от начального элемента по адресам, получить доступ к любому элементу данной структуры. Доступ к данным в динамических структурах осуществляется с помощью операции «стрелка» (->), которую называют операцией косвенного выбора элемента структурного объекта, адресуемого указателем. Она обеспечивает доступ к элементу структуры через адресующий ее указатель того же структурного типа. Формат применения данной операции следующий: УказательНаСтруктуру -> ИмяЭлемента

Имея возможность явного манипулирования с указателями, которые могут располагаться как вне структуры, так и «внутри» отдельных ее элементов, можно создавать в памяти различные структуры. В программах, в которых необходимо использовать динамические структуры данных, работа с памятью происходит стандартным образом. Выделение динамической памяти производится с помощью операции new или с помощью библиотечной функции malloc (calloc). Освобождение динамической памяти осуществляется операцией delete или функцией free.

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

2.1 Массив как базовая структура

Оперативная память с точки зрения программиста - это массив элементов. Любой элемент массива можно прочитать или записать сразу, за одно элементарное действие. Массив можно рассматривать как простейшую структуру данных. Структуры данных, в которых возможен непосредственный доступ к произвольным их элементам, называют структурами данных с прямым, или с произвольным доступом (по-английски random access). В других структурах данных непосредственный доступ возможен лишь к одному или нескольким элементам, для доступа к остальным элементам надо выполнить дополнительные действия. Такие структуры данных называются структурами последовательного доступа. Примером структуры последовательного доступа является магнитофон, на которым записаны песни. В любой момент можно прослушать лишь очередную песню. Чтобы добраться до других музыкальных фрагментов, надо перемотать ленту вперед или назад. Кстати, такие магнитофоны, или накопители на магнитной ленте, очень долго использовались на ЭВМ, хотя, сейчас уступили свое место более надежным и компактным системам (съемным магнитным и оптическим дискам, флэш-памяти и т.п.). Устройство компьютерного магнитофона было аналогично устройству обычного бытового магнитофона. С логической точки зрения, массивом является также важнейшая составляющая компьютера - магнитный диск. Элементарной единицей чтения и записи для магнитного диска служит блок. Размер блока зависит от конструкции конкретного диска, обычно он кратен 512. За одну элементарную операцию можно прочесть или записать один блок с заданным адресом.

Итак, наиболее важные запоминающие устройства компьютера - оперативная память и магнитный диск - представляют собой массивы. Массив как бы дан программисту свыше, так же как математику целые числа. Работа с элементами массива осуществляется исключительно быстро, все элементы массива доступны без всяких предварительных действий. Тем не менее, массивов недостаточно для написания эффективных программ. Например, поиск элемента в массиве, если его элементы не упорядочены, невозможно реализовать эффективно: нельзя изобрести ничего лучшего, кроме последовательного перебора элементов. В случае упорядоченного хранения элементов можно использовать эффективный бинарный поиск, но затруднения возникают при добавлении или удалении элементов в середине массива и приводят к массовым операциям, т.е. операциям, время выполнения которых зависит от числа элементов структуры. От этих недостатков удается избавиться, реализуя множество элементов на базе сбалансированных деревьев или хеш-функции. Есть и другие причины, по которым необходимо использовать более сложные, чем массивы, структуры данных. Логика многих задач требует организации определенного порядка доступа к данным. Наконец, массив имеет ограниченный размер. Увеличение размера массива в случае необходимости приводит к переписыванию его содержимого в захваченную область памяти большего размера, т.е. опять же к массовой операции. От этого недостатка свободны ссылочные реализации структур данных: реализации на основе линейных списков или на основе деревьев.

2.2 Реализация динамической структуры данных - стек

Стек - частный случай линейного односвязного списка (ЛОС), для которого определены две фундаментальные операции:

- добавление элемента в вершину стека;

- удаление элемента из вершины стека,

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

Для корректной обработки стека вводят понятия: указатель на вершину стека. Как правило, именуется в программе подобный указатель словом top (в переводе с английского означает вершина, верхушка). Данный указатель обязан указывать (или ссылаться) только на самый верхний элемент стека, иначе стек будет находиться в несогласованном состоянии.

Опишем операции, проводимые над стеком.

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

Для правильной организации связей между элементами динамической структуры данных требуется, чтобы каждый элемент содержал кроме информационных значений как минимум один указатель. Абсолютно во всех операциях, производимых над стеком, требуется вспомогательный указатель (помимо указателя top, ссылающего на вершину стека). Во всех программах и фрагментах программного кода, представленных ниже, идентификатор p - обозначение вспомогательного указателя NIL - специальный зарезервированный участок памяти, служащий «бухтой» для динамических переменных - указателей. Чтобы указатели «не болтались» в памяти, их обычно «привязывают» к NIL.

Операция добавление элемента в вершину стека имеет две разновидности:

- добавление элемента в стек, когда нет ни одного элемента;

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

Рассмотрим ситуацию, когда в стеке не содержится ни одного элемента. В этом случае указатель на вершину стека top ссылается в NIL. NIL - специальный зарезервированный участок памяти, служащий «бухтой» для динамических переменных - указателей. Чтобы указатели «не болтались» в памяти, их обычно «привязывают» к NIL.

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

Разберем схему добавления первого элемента в вершину «нулевого» стека. Исходное состояние стека, когда нет ни одного элемента

где p - указатель на добавляемый элемент



Первой операцией производим установку ссылочного поля добавляемого элемента на то место в памяти, куда указывает указатель на вершину стека top. Поскольку в стеке нет элементов, то ссылочное поле link добавляемого элемента начинает ссылаться на NIL.

Второй операцией производим перенос указателя на вершину стека (обозначен как top) на только что добавленный элемент. То есть стек принимает окончательное согласованное состояние.

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

Как видно из схемы, стек содержит 3 элемента. Ссылочное поле нижнего элемента указывает в NIL. Указатель на вершину стека top ссылается на самый верхний элемент.



где p - указатель на добавляемый элемент

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

Второй операцией производим перенос указателя на вершину стека (обозначен как top) на только что добавленный элемент. В итоге в стеке становится 4 элемента. Вывод: добавление элемента в стек является универсальной операцией, ее можно запрограммировать.

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



Как видно из схемы, стек содержит 3 элемента. Ссылочное поле нижнего элемента указывает в NIL. Указатель на вершину стека top ссылается на самый верхний элемент. То есть стек находится в согласованном состоянии. Для реализации удаления элемента из стека потребуется вспомогательный указатель p.

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

Вторым действием необходимо «перебросить» указатель на вершину стека top на второй элемент (второго элемента может и не быть, если стек состоял только из единственного элемента, тогда top мигрирует в NIL).

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

Производим удаление самого верхнего элемента стека. На данный момент операция удаления производится абсолютно безболезненно и не происходит абсолютно никаких нарушений в стеке (особенно на уровне связей). В результате удаления самого верхнего элемента количество элементов уменьшилось на один и составляет на данный момент 2 штуки. Стек находится в согласованном состоянии.

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

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

Подвергнем анализу далее схему печати всех элементов стека. Печать элементов стека будет физически возможной, если в стеке имеется хотя бы один элемент. Ниже представлен полный процесс всех итераций по печати элементов стека с указателем p на экран пользователя. Распечатка всех элементов на экран - итерационный процесс, следовательно, при программировании используют циклы. После окончания печати всех элементов стека, сам стек остается в согласованном состоянии.

Для работы со стеком существуют и нестандартные операции:

- расщепление структуры исходного стека на два различных подстека по какому-либо признаку;

- слияние элементов из двух или более однородных стековых структур в консолидирующий стек по какому-либо признаку;

- сортировка стека по заданному «ключу»;

- поиск элемента стека по заданному критерию;

- переворот элементов стека;

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

2.3 Реализация динамической структуры данных - очередь

Представим понятие «очередь» и разберем принцип ее реализации.

Очередь - частный случай линейного односвязного списка (ЛОС), для которого определены две фундаментальные операции:

- добавление элемента в конец очереди;

- удаление элемента из начала очереди.

также, еще существует обязательная вспомогательная операция - печать элементов очереди на экран, так как в любом случае потребуется печать очереди на экран пользователя, чтобы просмотреть, насколько корректно реализованы операции добавления и удаления элементов. Для корректной обработки очереди вводят понятие - указатель на начало очереди. Как правило, именуется в программе подобный указатель словом begQ (в переводе с английского означает begin queue - начало очереди). Данный указатель обязан ссылаться только на самый первый элемент очереди.

Для проведения операций над очередью существуют вспомогательные инструменты. Абсолютно во всех операциях, производимых над очередью, требуется вспомогательный указатель (помимо указателя begQ, ссылающего на первый элемент очереди). Во всех программах и фрагментах программного кода, представленных ниже, идентификатор p - обозначение вспомогательного указателя NIL - специальный зарезервированный участок памяти, служащий «бухтой» для динамических переменных - указателей. Чтобы указатели «не болтались» в памяти, их обычно «привязывают» к NIL.



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

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

где, add - указатель на добавляемый элемент

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

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

где p - указатель на добавляемый элемент

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

Устанавливаем вспомогательный указатель p на первый элемент очереди и циклически передвигаем указатель p на последний элемент очереди.

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



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

Удаление физически возможно только тогда, когда в очереди присутствуют элементы. Разберем удаление элемента из непустой очереди.

Как видно из представленной схемы, очередь содержит три элемента и находится в согласованном состоянии (указатель begQ ссылается на первый элемент). Удаление элемента осуществляется из начала очереди, то есть уничтожается первый элемент очереди. Технология операции удаления первого элемента из очереди не зависит от количества элементов во всей очереди.

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

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

Производим собственно удаление первого элемента из очереди. После операции удаления очередь находится в согласованном состоянии: begQ - ссылается на первый элемент, а линковочное поле последнего элемента указывает в NIL. Вывод: удаление элемента из очереди (непустой очереди) является универсальной операцией, ее можно запрограммировать.

Теперь проведем анализ схемы печати всех элементов очереди. Печать элементов очереди будет физически возможной, если в очереди имеется хотя бы один элемент. Вообще, печать элементов очереди нельзя относить к фундаментальным операциям, а лишь к вспомогательным операциям. Предположим, что начальная очередь содержит 3 элемента. Введем идентификатор p. Распечатка всех элементов на экран - итерационный процесс, следовательно, при программировании используют циклы (как правило, цикл с предусловием, то есть цикл while-do). Как только вспомогательный указатель p достигнет NIL, операция вывода будет официально завершена. После окончания печати всех элементов очереди, сама очередь остается в согласованном состоянии.

3. Практика реализации динамических структур данных стека и очереди

3.1 Практика реализации стека

В повседневной жизни часто приходится иметь дело с хранилищами различных объектов. Хранилище может быть пустым, если в данный момент никаких объектов в нём нет. Независимо от того, как устроено хранилище, и какие объекты в нём хранятся, можно выделить два основных действия для работы с ним: добавить объект и взять объект. Если потребовать, чтобы операции добавления и изъятия объектов удовлетворяли некоторым условиям, можно обозначить стек одним из типов этих хранилищ.

Реализация стека на базе массива является классикой программирования. Базой реализации является массив размера N, таким образом, реализуется стек ограниченного размера, максимальная глубина которого не может превышать N. Индексы ячеек массива изменяются от 0 до N - 1. Элементы стека хранятся в массиве следующим образом: элемент на дне стека располагается в начале массива, т.е. в ячейке с индексом 0. Элемент, расположенный над самым нижним элементом стека, хранится в ячейке с индексом 1, и так далее. Вершина стека хранится где-то в середине массива. Индекс элемента на вершине стека хранится в специальной переменной - указатель стека.

Реализуем стек с помощью массива практически. Опишем тип данных stack и две процедуры: push (S, x) - положить в стек S элемент x и pop (S, x) - взять с вершины стека S элемент, присвоив его параметру x.

const

stacksize = … {максимальное число элементов, которые могут одновременно находиться в стеке};

type

elemtype = … {подходящий для задачи тип элементов стека};

stack = record

elems: array [1..stacksize] of elemtype;

top: integer {индекс вершины стека}

end;

var S: stack; {стек}

procedure push (var S: stack; x:elemtype);

{положить x в стек S}

begin S.top:=S.top+1;

S.elems [S.top]:=x

end; {push}

procedure pop (var S: stack; var x:elemtype);

{взять из стека S верхний элемент и присвоить его x}

begin x:=S.elems [S.top];

S.top:=S.top-1;

end; {pop}

Перед началом работы со стеком нужно сделать его пустым. Для этого опишем процедуру init_stack(S):

procedure init_stack (var S: stack);

{начальная установка стека}

begin S.top:=0;

end; {init_stack}

К пустому стеку нельзя применять операцию pop, а к полному стеку нельзя применять операцию push. Опишем функции full_stack(S) и empty_stack(S), проверяющие стек на переполнение и пустоту.

function full_stack (var S: stack):boolean;

{возвращает истину, если стек полон, иначе - ложь}

begin

full_stack:=L.top=stacksize

end; {full_stack}

function empty_stack (var S: stack):boolean;

{возвращает истину, если стек пуст, иначе - ложь}

begin

empty_stack:=L.top=0

end; {empty_stack}

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

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

procedure push (var S: stack; x:elemtype);

{положить x в стек S с контролем переполнения}

begin

if S.top=stacksize then error ('стек полон')

else begin

S.top:=S.top+1;

S.elems [S.top]:=x

end; {push}

procedure pop (var S: stack; var x:elemtype);

{если стек не пуст, взять из стека S верхний элемент и присвоить его x, иначе сообщить об ошибке}

begin

if S.top=0 then error ('стекпуст ')

else begin

x:=S.elems [S.top];

S.top:=S.top-1;

end

end; {pop}

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

Приведем несколько практических примеров наглядного использования стека.

Практический пример 1

Стек заполнен однозначными и двухзначными числами. Поместить однозначные числа в один стек, двухзначные - в другой.

randomize;

init;

init;

init;

for i:=1 to n do

begin

y:=random;

push;

end;

list; Writeln;

while not emptydo

if stacktopdiv 10=0 then push)

else push);

list; Writeln;

list; Writeln;

Практический пример 2

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

randomize;

init;

init;

for i:=1 to n do begin

y:=random-random;

push; end;

list;

y:=0;

while not empty do begin

if <0) and then begin pop; y:=1; end;

push);

end;

list;

while not empty do

push);

list;

Практический пример 3

Дан стек, заполненный случайным образом целыми числами. Отыскать в данном стеке максимальный и минимальный элементы. Переместить максимальный элемент в дно стека, минимальный - в вершину.

randomize;

init;

init;

init;

for i:=1 to n-1 do

begin

y:=random-random;

push;

end;

list; Writeln;

push);

while not emptydo

if stacktop<=stacktop then begin push); push) end

else push);

while not emptydo

push);

push);

push);

while not emptydo

if stacktop>=stacktop then begin push); push) end

else push);

push);

while not emptydo

push);

writeln;

list;

3.2 Практика реализации очереди

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

Очередь отличается от стека тем, что последний пришедший в неё элемент будет извлечён последним, а первый первым («FIFO»). С помощью списков ее можно организовать следующим образом: будем хранить не только указатель на «голову» списка, но и на «хвост»; добавлять будем в «хвост», а извлекать из «головы».

Любая реализация очереди (не обязательно с помощью списков) должна «уметь» выполнять такие действия:

- procedure InitQueue - инициализация очереди;

- procedure AddQueue (d: tData) - поставить элемент в очередь;

- procedure SubQueue (var d: tData) - извлечь элемент из очереди;

- function NotEmpty: boolean - проверка очереди на пустоту.

Для работы с очередью в основном используют операторы:

- MAKENULL(Q) - создать пустую очередь;

- BACK (x, Q) - поместить элемент x в конец очереди Q;

- ELEM(Q) - возвратить значение элемента из начала очереди Q;

- FRONT(Q) - выбрать элемент из начала очереди Q;

- EMPTY(Q) - проверить, является ли очередь Q пустой.

В отличие от стека реализация очереди в динамической памяти с помощью типа данных «список» не отличается высокой эффективностью. Существует еще один вариант построения очереди в виде однонаправленного списка в динамической памяти. Выделяют 2 специальные ячейки для определения позиций начала и конца очереди.

First - начало очереди. Last - конец очереди. Тип элемента очереди определяется как указатель на ячейку, состоящий из 2 полей: информационного и указателя на следующий элемент. Очередь определяется как запись, состоящая из 2 ячеек.

type

QUEUE=record;

first, last:^cell;

end;

Для первой ячейки очереди, на которую указывает First, информационное поле никогда не используется. Для последней ячейки, на которую указывает Last поле NEXT всегда определяет пустой указатель.

Покажем примеры реализации операторов:

- Создать пустую очередь:

Procedure MAKENULL (var Q:QUEUE);

Begin

New (Q.first);

Q.first^.next:=NIL;

Q.last:=Q.first;

end;

- Добавить элемент в конец очереди:

Procedure BACK (x:el_type; var Q:QUEUE);

NEW (Q. Last^.next);

Q. Last:=Q. Last^.next;

Q. Last^.element:=x;

Q. Last^.next:=NIL;

End;

Приведем дополнительные описания.

type link =^node; {ссылка на звено}

elemtype = … {подходящий тип элементов очереди};

node= record

elem: elemtype; {элемент}

next: link {ссылка на следующее звено}

end;

queue = record

front: link {ссылка на заглавное звено};

rear: link {ссылка на последнее звено}

end;

var Q: queue; {очередь}

procedure init_queue (var Q: queue);

{начальная установка очереди}

begin new (Q.front); {создание заглавного звена}

Q.front^.next:=nil;

Q.rear:= Q.front;

end; {init_queue}

function empty_queue (Q: queue):boolean;

{возвращает истину, если очередь пуста, иначе - ложь}

begin

empty_queue:=Q.rear=Q.front

end; {empty_queue}

procedure enqueue (var Q: queue; x:elemtype);

{поставить в очередь Q элемент х}

begin

new (Q.rear^.next);

Q.rear:=Q.rear^.next;

Q.rear^.elem:=x;

Q.rear^.next:=nil

end; {enqueue}

procedure dequeue (var Q: queue; var x:elemtype);

{взять из очереди Q элемент и присвоить х}

var p:link;

begin

x:=Q.front^.next^.elem;

p:=Q.front;

Q.front:=Q.front^.next;

dispose(p)

end; {dequeue}

Пусть в основной программе описаны переменные: Z - очередь целых чисел, y - целое. После исключения из очереди единица оказалась в поле elem заглавного звена, перестав быть частью очереди. При необходимости контролировать корректность использования очереди во время отладки программы, в процедуру dequeue можно добавить обращение к процедуре error при попытке взять элемент из пустой очереди.

Представим практические примеры в виде конкретного условия наглядного использования очереди.

Практический пример 1

Статистическая реализация очереди на основе массива

unit Queue; {Очередь FIFO - кольцевая}

Interface

const SIZE=…; {предельный размер очереди}

type data =…; {эл-ты могут иметь любой тип}

Procesure QInit;

Procedure Qclr;

Function QWrite (a: data): boolean;

Function QRead (var a: data): boolean;

Function Qsize: integer;

Implementation {Очередь на кольце}

var QueueA: array [1..SIZE] of data; {данные очереди}

top, bottom: integer; {начало и конец}

Procedure QInit; {** инициализация - начало=конец=1}

begin top:=1; bottom:=1; end;

Procedure Qclr; {**очистка - начало=конец}

begin top:=bottom; end;

Function QWrite (a: data): boolean; {** запись в конец}

begin

if bottom mod SIZE+1=top then {очередь полна} QWrite:=false

else begin

{запись, модификация указ. конца с переходом по кольцу}

Queue[bottom]:=a; bottom:=bottom mod SIZE+1; QWrite:=true;

end; end; {QWrite}

Function QRead (var a: data): boolean; {** выборка из начала}

begin

if top=bottom then QRead:=false else

{запись, модификация указ. начала с переходом по кольцу}

begin a:=Queue[top]; top:=top mod SIZE + 1; QRead:=true;

end; end; {QRead}

Function QSize: integer; {** определение размера}

begin

if top <= bottom then QSize:=bottom-top else QSize:=bottom+SIZE-top;

end; {QSize}

END.

Практический пример 2

Динамическая реализация очереди

interface

uses item; {Описание самого элемента списка}

type

pttype = ^ttype;

tqueue = object

{Инициализация}

constructor init;

{Удаление}

destructor done;

{Занесение элемента в очередь}

procedure put (x: ttype);

{Извлечение элемента из очереди}

function get (var x: ttype): boolean;

{Проверка пустоты очереди}

function empty: boolean;

{Распечатка содержимого очереди}

procedure print;

private

head, tail: ptitem;

end;

uses item, queue;

var

ist: tqueue;

i: integer;

x: ttype;

begin

ist.init;

for i:= 1 to 15 do

ist.put (12*i);

ist.print;

for i:= 1 to 5 do

if ist.get(x) then writeln(x);

ist.print;

ist.done

end.

Практический пример 3

Составить программу, которая формирует очередь, добавляет в нее произвольное количество компонент, а затем читает все компоненты и выводит их на экран дисплея. Данные - строка символов. Ввод данных - с клавиатуры, признак конца ввода строка символов END.

Program QUEUE;

uses Crt;

type Alfa= String[10];

PComp= ^Comp;

Comp= record

sD: Alfa;

pNext:PComp

end;

var

pBegin, pEnd: PComp;

sC: Alfa;

Procedure CreateQueue (var pBegin, pEnd: PComp; var sC: Alfa);

begin

New(pBegin);

pBegin^.pNext:=NIL;

pBegin^.sD:=sC;

pEnd:=pBegin

end;

Procedure AddQueue (var pEnd:PComp; var sC: Alfa);

var pAux: PComp;

begin

New(pAux);

pAux^.pNext:=NIL;

pEnd^.pNext:=pAux;

pEnd:=pAux;

pEnd^.sD:=sC

end;

Procedure DelQueue (var pBegin: PComp; var sC: Alfa);

begin

sC:=pBegin^.sD;

pBegin:=pBegin^.pNext

end;

begin

Clrscr;

writeln (' ВВЕДИ СТРОКУ '); readln(sC);

CreateQueue (pBegin, pEnd, sC);

repeat writeln (' ВВЕДИ СТРОКУ '); readln(sC);

AddQueue (pEnd, sC)

until sC='END';

writeln (' ***** ВЫВОД РЕЗУЛЬТАТОВ *****');

repeat DelQueue (pBegin, sC);

writeln(sC);

until pBegin=NIL;

end.

Заключение

В ходе работы были закреплены навыки работы с динамическими структурами данных в объектно-ориентированном программировании. Были представлены практические примеры программ работы с динамическими структурами данных: стеком и очередью.

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

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

Подведем итоги в инициализации понятия рассматриваемых в работе динамических структур данных:

- динамическими структурами данных называются блоки в динамической памяти, связанные друг с другом с помощью указателей;

- динамические структуры различаются способами связи отдельных элементов и допустимыми операциями над ними;

- элемент любой динамической структуры данных состоит из информационных полей и полей указателей;

- стек и очередь являются наиболее распространенными структурами;

- для стека определены операции помещения элемента в вершину и выборки элемента из вершины;

- для очереди определены операции помещения элемента в конец очереди и выборка элемента из ее начала;

- динамические структуры более эффективно реализовывать с помощью массивов.

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

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

Итак, в работе выявлены случаи, когда возникает необходимость в динамических структурах данных:

- используются переменные, имеющие довольно большой размер (например, массивы большой размерности), необходимые в одних частях программы и совершенно не нужные в других;

- в процессе работы программы нужен массив, список или иная структура, размер которой изменяется в широких пределах и трудно предсказуем;

- когда размер данных, обрабатываемых в программе, превышает объем сегмента данных.

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

- размер структуры ограничивается только доступным объемом машинной памяти;

- при изменении логической последовательности элементов структуры требуется не

- перемещение данных в памяти, а только коррекция указателей;

- большая гибкость структуры.

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

Вместе с тем, связное представление не лишено и недостатков, основными из которых являются следующие:

- на поля, содержащие указатели для связывания элементов друг с другом, расходуется дополнительная память;

- доступ к элементам связной структуры может быть менее эффективным по времени.

Последний недостаток является наиболее серьезным и именно им ограничивается применимость связного представления данных.

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

Библиография

1. Гагарина Л.Г., Колдаев В.Д. Алгоритмы и структуры данных. - М.: Финансы и статистика, 2009.

2. Туник. Е.Е. Анализ и интерпретация данных. - Санкт-Петербург: Речь, 2009.

3. Альфред В. Ахо, Джон Э. Хопкрофт, Джеффри Д. Ульман. Структуры данных и алгоритмы. - М.: Вильямс, 2010.

4. Арлазаров В.Л., Емельянов Н.Е. Технологии программирования и хранения данных. - Санкт-Петербург: Питер, 2009.

5. Анцыпа В.А., В.В. Вдовин. Практикум по программированию в Турбо Паскале. - М.: Образование и Информатика, 2008.

6. Алексеев В.Е., Таланов В.А. Графы и алгоритмы. Структуры данных. Модели вычислений. - М.: Бином, 2009.

7. Вирт Н. Алгоритмы и структуры данных. - Санкт-Петербург Невский диалект, 2008.

8. Павловская Т.А. Паскаль. Программирование на языке высокого уровня. Учебник для вузов. - Санкт-Петербург: Питер, 2010

9. Берзтисс А.Т. Структуры данных. Переработанное издание. - М: ЁЁ Медиа, 2012.

10. Бабичев А.В. Распознавание и спецификация структур данных. - Санкт-Петербург, Ленанд, 2009.

11. Споров А.Е. Информатика. - М.: Полиграфиздат, 2010.

12. Окулов С. Основы программирования. - Санкт-Петербург: Бином, 2010.

13. Фаронов В.В. Turbo Pascal 7.0. Практика программирования. - Санкт-Петербург: КноРус, 2011.

14. Сатунина А.Е. Информатика. Методические материалы к лабораторным работам. - М.: РГГУ, 2008.

Размещено на Allbest.ru

...