Вопрос 6: «Динамические структуры данных. Стек. Очередь. Дек. Списки»

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

Стек – это частный случай однонаправленного списка, добавление элементов в который и выборка из которого выполняется с одного конца, называемого вершиной стека. Другие операции со стеком не определены. При выборке элемент исключается из стека. Говорят, что стек реализует принцип обслуживания LIFO (Last In – First Out, последним пришел – первым ушел). Стек проще всего представить себе как закрытую с одного конца узкую трубку, в которую бросают мячики. Достать первый брошенный мячик можно только после того, как вынуты все остальные. Стеки широко применяются в системном программном обеспечении, компиляторах, в различных рекурсивных алгоритмах.

Очередь – это частный случай однонаправленного списка, добавление элементов в который выполняется в один конец, а выборка – из другого конца. Другие операции с очередью не определены. При выборке элемент исключается из очереди. Говорят, что очередь реализует принцип обслуживания FIFO (First In – First Out, первым пришел – первым ушел). В программировании очереди применяются в моделировании, диспетчеризации задач операционной системой, буферезированном вводе-выводе.

Дек - особый вид очереди. Дек (от англ. deq - double ended queue,т.е очередь с двумя концами) - это такой последовательный список, в котором как включение, так и исключение элементов может осуществляться с любого из двух концов списка. Частный случай дека - дек с ограниченным входом и дек с ограниченным выходом. Логическая и физическая структуры дека аналогичны логической и физической структуре кольцевой FIFO-очереди. Однако, применительно к деку целесообразно говорить не о начале и конце, а о левом и правом конце.

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

Вопрос 7: «Методы разработки при модульном проектировании. Сверху вниз. Снизу вверх. Конструктивный подход»

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

Недостатки метода:

1. Для ПМ нижнего уровня трудно определить спецификации окончательно.

2. Для отладки ПМ нижнего уровня нужно создавать вызывающие ПМ

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

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

Недостаток метода:

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

Конструктивный подход можно показать графически:

С пецификация ПО

С пецификация ПО (головного модуля)