ОАП 11 класс

Тема 1: «Структуры данных» (4 часа)

Урок 1. Понятие структур данных. Простая переменная, массив, стек, очередь.

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

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

Их принято делить на 3 категории: простые, указатели и сложные. К настоящему моменту мы знакомы со многими простыми типами и некоторыми сложными. Какими? 

Чем разнятся простые типы от сложных? Тем ли, что сложные сложнее изучать? Отчасти, да, но суть не в этом.

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

Так, например, можно выделить отдельные символы в строке. Простые же типы данных не "раскалываются" на мелкие детали.

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

 Перед вами секции описаний: укажите среди представленных вам переменных простые переменные и сложные.

Ниже приведёны примеры процедур занесения и извлечения для линейной очереди на языках Паскаль

Очереди и стеки 

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

Вовочка в потоке событий 

Переживайте неприятности по мере их поступления — эта житейская мудрость касается любого из нас. Жизнь — это поток событий, барахтаясь в котором, мы поминутно решаем: прервать ли начатое дело и хвататься за другую проблему? Или отложить эту новую проблему «на потом»? Смотрите: вот компьютер и Вовочка, мирно играющий в «звездные войны». Входит мама: «Вова, ты уроки сделал?». Вова неохотно откладывает игру и приступает к урокам. Через полчаса мама снова беспокоит его: «Вовочка, я не могу отойти от плиты. Сгоняй-ка быстро за луком». Уроки откладываются, и Вова отправляется в магазин. По пути он видит гоняющих мяч приятелей, — им не хватает вратаря. Как не помочь друзьям? Поход в магазин откладывается, и Вовочка на страже ворот. Делу время, а потехе час. Закончилась игра, и можно выполнить мамино поручение. Купив луку, Вова доделывает отложенные уроки и возвращается к первому занятию — «звездным войнам». Вовочка обрабатывал события по принципу стека, — скажет об этом системный программист. Другое название стека — дисциплина обслуживания LIFO, что значит «Last-In, First-Out», или по-русски: «последним пришел — первым ушел». Что такое стек и как он работает? Случалось ли вам паковать рюкзак или глубокую сумку? Тогда вы знакомы со стеком. Всё, что уложено в рюкзак, будет извлекаться из него в обратном порядке. А вот пример: магазин для патронов. Патрон, вставленный в магазин последним, выстрелит первым, и наоборот. Итак, пример с Вовочкой показал, что важные события мы обслуживаем по принципу стека. А очередь? Какое отношение к нам имеет этот символ потерянного времени? Заметив, как «тормозит» порой ваш компьютер, вспомните о ней. Иногда компьютер реагирует на мышку и клавиатуру с заметным опозданием, но не забывает о нажатиях и щелчках. Они накапливаются в очереди, а затем извлекаются оттуда и обрабатываются. Или другой пример — печатание документов на сетевом принтере. Когда принтер занят, операционная система ставит запросы на печать в очередь. А затем — по мере готовности принтера — выбирает файлы из этой очереди и отправляет принтеру. За очередью тоже закрепилось свое сокращение — FIFO, что значит «First-In, First-Out» — «первым пришел, первым ушел». В отличие от стека, в очередь попадают маловажные события. Обратите внимание, что элементами очередей и стеков может быть что угодно: события, предметы и даже люди. Рассмотрим два примера: запись в танцевальный кружок и сортировочную горку. 

Танцевальный кружок 

В городе набирали детей в кружок бального танца. Запись в кружок вела преподающая в нём дама. Приходящих мальчишек и девчонок она стремилась объединять в пары при первой возможности с тем, чтобы они сразу приступали к занятиям. Однако на запись дети приходили поодиночке в разное время и в случайном порядке, — то несколько мальчиков подряд, то несколько девочек. Дама не слыхала о системном программировании, а потому прибегла к здравому смыслу. Взяв пару записных книжек, она поступала так. Если к ней являлось больше мальчиков, дама заносила их в мальчишечью записную книжку, то есть, ставила в очередь. Приняв девочку, она выбирала из этой очереди первого мальчика и составляла пару. Если же являлось больше девочек, то дама ставила их в девчоночью очередь (в другой записной книжке), а с приходом очередного мальчика составляла новую пару. Так, в порядке поступления, составлялись пары мальчиков и девочек. Пусть наша новая программа повторит действия танцевального тренера, — инженеры называют это моделированием. Работать будем, конечно, не с живыми детьми, мы представим их как-то иначе. Условимся обозначать их латинскими буквами: девочек — строчными, а мальчиков — заглавными (только потому, что они выше ростом). 

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

означает, что первым явится мальчик по имени Z, а последней — девочка по имени f. Первая пара составится из мальчика Z и девочки q. Это упрощение не меняет сути нашей модели, но избавляет её от второстепенных деталей. 

Итак, с учетом всех договоренностей, явим задачу в окончательном виде. Дана строка, состоящая из заглавных и строчных букв латинского алфавита — «мальчиков» и «девочек». Мы должны сформировать другую строку, состоящую из тех же символов, но следующих попарно: сначала заглавная буква — «мальчик», затем строчная — «девочка». Пары разделяются пробелом. Например, для указанной выше строки, пары должны быть составлены так.

А напоследок программа должна напечатать имена тех, кто временно остался без пары. Здесь это будут пришедшие в числе последних мальчики I, O и P. 

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

Сделаем так. Элементы очереди — символы — будем хранить в строковых переменных. К ним добавим ещё две процедуры: одну — для установки элемента в очередь, другую (это будет функция) — для извлечения из очереди первого элемента. Назовем их соответственно PutInQue — «поставить в очередь» и GetFromQue — «извлечь из очереди» (Queue — «очередь» или «хвост»). Всё это представлено в программе P_45_1.

Какой механизм был использован в данной задаче: очередь или стек?

Итоги · 

• Очереди и стеки – это механизмы, применяемые в системных программах. 
• Элементами очередей и стеков могут быть любые объекты. · 
• Очередь обслуживает элементы по принципу «первый пришел – первый ушел» или сокращенно FIFO (First-In, First-Out). · 
• Стек обслуживает элементы по принципу «последний пришел – первый ушел» или сокращенно LIFO (Last-In, First-Out). 
• В стеке доступна единственная позиция – та, в которой находится последний введённый элемент – вершина. Иногда позицию, от которой стек начал заполняться данными, называют дном стека (хотя особого применения этот термин не имеет, поскольку дно стека, в котором содержится хотя бы один элемент данных, недоступно. Одно из немногих рациональных применений термина "дно" – признак пустого стека, когда дно и вершина совпадают
• Для стека, как и для очереди, характерны две операции – сохранение и извлечение, но применяются они к одной и той же позиции. Операция извлечения удаляет элемент из списка и уничтожает его содержимое. Произвольный доступ к элементам стека не допускается.


В общем случае, очередь – это линейный список, доступ к элементам которого происходит по принципу F I F O (First In and First Out – первым пришел и первым ушел).


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


Области применения очередей


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

 К применению очередей в системных целях относятся:


• диспетчеризация задач операционной системой;
• буферизация ввода/вывода;

Прикладное применение:

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


Области применения стеков такие же, как и у очередей:
Системные –
передача процедурам и функциям аргументов по значению;
сохранение и восстановление содержимого регистров общего назначения процессора при вызове процедур (прологи и эпилоги функций).
Прикладные –
стековая (магазинная) память, например в языке программирования Forth;
вспомогательные структуры данных (например, при поиске в графе).

Урок 2. Работа со стеками

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