Типы данных, определяемые пользователем: динамические структуры данных.
Стек — динамическая структура данных, представляющая из себя упорядоченный набор элементов, в которой добавление новых элементов и удаление существующих производится с одного конца, называемого вершиной стека. По определению, элементы извлекаются из стека в порядке, обратном их добавлению в эту структуру, т.е. действует принцип "последний пришёл — первый ушёл".
Наиболее наглядным примером организации стека служит детская пирамидка, где добавление и снятие колец осуществляется как раз согласно определению стека. Стек можно организовать на базе любой структуры данных, где возможно хранение нескольких однотипных элементов и где можно реализовать определение стека: линейный массив, типизированный файл, однонаправленный или двунаправленный список. В нашем случае наиболее подходящим для реализации стека является однонаправленный список, причём в качестве вершины стека выберем начало этого списка.
Выделим типовые операции над стеком и его элементами:
добавление элемента в стек;
удаление элемента из стека;
проверка, пуст ли стек;
просмотр элемента в вершине стека без удаления;
очистка стека.
Очередью FIFO (First - In - First- Out - "первым пришел - первым исключается") - называется такой последовательный список с переменной длиной, в котором включение элементов выполняется только с одной стороны списка (эту сторону часто называют концом или хвостом очереди), а исключение - с другой стороны (называемой началом или головой очереди). Те самые очереди к прилавкам и к кассам, которые мы так не любим, являются типичным бытовым примером очереди FIFO. Основные операции над очередью - те же, что и над стеком - включение, исключение, определение размера, очистка, неразрушающее чтение. Динамическая реализация очереди аналогична реализации стека.
Дек (от англ. deq - double ended queue,т.е очередь с двумя концами) - это такой последовательный список, в котором как включение, так и исключение элементов может осуществляться с любого из двух концов списка. Частный случай дека - дек с ограниченным входом и дек с ограниченным выходом. Логическая и физическая структуры дека аналогичны логической и физической структуре кольцевой FIFO-очереди. Однако, применительно к деку целесообразно говорить не о начале и конце, а о левом и правом конце.
Операции над деком:
включение элемента справа;
включение элемента слева;
исключение элемента справа;
исключение элемента слева;
определение размера;
очистка.
Динамическая реализация является очевидным объединением стека и очереди.
Как правило, вся организация дека выполняется программистом без каких-либо специальных средств системной поддержки. Примером дека может быть, например, некий терминал, в который вводятся команды, каждая из которых выполняется какое-то время. Если ввести следующую команду, не дождавшись, пока закончится выполнение предыдущей, то она встанет в очередь и начнет выполняться, как только освободится терминал. Это FIFO очередь. Если же дополнительно ввести операцию отмены последней введенной команды, то получается дек.
Стек, очередь и дек могут быть организованы на базе
массива: выделяется место под N элементов разом, а затем описываются операции над данным типом данных в терминах операций над элементами массива.
списка: память выделяется и освобождается по мере необходимости.
Первый вариант быстрее, но лишь второй истинно динамический. Соответственно, в различных приложениях может быть предпочтителен первый или второй.
Списком называется упорядоченное множество, состоящее из переменного числа элементов, к которым применимы операции включения, исключения. Список, отражающий отношения соседства между элементами, называется линейным. Длина списка равна числу элементов, содержащихся в списке, список нулевой длины называется пустым списком. Линейные связные списки являются простейшими динамическими структурами данных. Графически связи в списках удобно изображать с помощью стрелок. Если компонента не связана ни с какой другой, то в поле указателя записывают значение, не указывающее ни на какой элемент. Такая ссылка обозначается специальным именем - nil.
Односвязный список. На нем поле INF - информационное поле, данные, NEXT - указатель на следующий элемент списка. Каждый список должен иметь особый элемент, называемый указателем начала списка или головой списка, который обычно по формату отличен от остальных элементов. В поле указателя последнего элемента списка находится специальный признак nil, свидетельствующий о конце списка.
Двусвязный список характеризуется наличием пары указателей в каждом элементе: на предыдущий элемент и на следующий. Разновидностью рассмотренных видов линейных списков является кольцевой список, который может быть организован на основе как односвязного, так и двухсвязного списков. При этом в односвязном списке указатель последнего элемента должен указывать на первый элемент; в двухсвязном списке в первом и последнем элементах соответствующие указатели переопределяются.
P-технология (R-технология).
R-язык описывает входные данные и программу с помощью нагруженных по дугам ориентированных графов.
На дуге сверху пишется условие прохождения по дуге.
На дуге снизу – выполняемые при этом действия.
Стандарты:
-ГОСТ 19.005-85
-международный стандарт ISO 8631H
R-структура Следование Ветвление While Повторение
Условие A ~P
Оператор S1 S2 S1 R S S2
~A P
S2 S
Вертикальные линии – вспомогательные, без стрелок и нагрузок и служат для соединения основных дуг с вершинами.
Обход выходящих дуг надо начинать сверху- вниз, слева- направо.
Процесс продолжения двигается по первой дуге
Этапы R-технологии:
Описывается структура данных
Структура данных определяется линейными операторами
Структура записывается на языке программирования.