Операции. Create = proc() returns(TQueue)

Create = proc() returns(TQueue)

effects Возвращает новую очередь без элементов в ней.

Empty = proc(q: TQueue) returns(bool)

effects Возвращает значение true, если в очереди q нет
элементов, и значение false в противном случае.

Insert = proc(q: TQueue; NewValue: int)

modifies q

effects Добавляет элемент со значением NewValue в конец
очереди q.

Remove = proc(q:TQueue) returns(int)

requires Очередь q не пуста.

modifies q

effects Возвращает элемент из начала очереди q и удаляет этот элемент из очереди.

Destroy = proc(q:TQueue)

modifies q

effects Удаляет из памяти очередь q.

end TQueue

3.3.3. Реализация абстракции данных

Для реализации типа данных мы выбираем представление для объектов и реализуем операции в терминах этого представления. Например, возможные представления для типа TQueue – массив целых чисел и последовательность динамических элементов. Таким образом, при реализации абстракции данных мы можем говорить о двух разных типах: о новом типе TQueue, который мы реализуем (абстрактный тип), и, например, о последовательности динамических элементов, которая используется для представления (тип представления). Тип представления может быть изменен, если понадобится изменить свойства реализации процедурной абстракции (повысить скорость обращения к данным типа или экономнее использовать память). При этом спецификация абстрактного типа данных не изменится.

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

Обсуждение реализации абстракции данных.

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

2. Классы операций:

а) примитивные конструкторы – создают объекты соответствующего типа, не используя никаких объектов в качестве аргументов (операция Create очереди);

б) конструкторы – используют в качестве аргументов объекты соответствующего им типа и создают другие объекты того же типа, например операция копирования очереди:

Copy = proc(q: TQueue) returns(TQueue)

effects Возвращает копию очереди q.

в) модификаторы – модифицируют объекты соответствующего им типа (операции Insert, Remove для очереди); только изменяемые типы могут иметь модификаторы;

г) наблюдатели используются для получения информации об объекте; в качестве аргумента они используют объект соответствующего им типа, а возвращают аргумент другого типа, например операцииEmpty или Size для очереди.

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

3.4. Исключительные ситуации (ИсС)

3.4.1. Общие положения

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

Оповещение подпрограммы о возникшей проблеме.

1. Определение специфического результата, возвращаемого в случае ошибки, например

Fact =proc(n: int) returns (int)

effects Если n>0, то возвращает n!, иначе возвращает 0.

Не очень хорошее решение, так как может не быть значения, с помощью которого можно было бы оповестить об ошибке.

2. Обобщение процедуры. Область определения D делится на несколько подмножеств, объединение которых дает D: D=D₀ È D₁ È ... È D_n. В каждом из подмножеств процедура ведет себя по-разному. Назовем подмножество D₀ «обычным» (это допустимое подмножество области определения). Остальные подмножества могут получать любые имена (по усмотрению программиста), но все они относятся к исключительным ситуациям и в этих случаях должно обеспечиваться оповещение пользователя. Таким образом, процедура определена на следующем наборе данных:

p: D₀ ® обычный (R₀)

D₁ ® имя₁ (R₁)

… исключительные ситуации

D_n ® имя_n (R_n)

где имя₁, ..., имя_n – имена ИсС, соответствующих аргументам, принадлежащим D₁, ..., D_n; R₁, ..., R_n – описание возвращаемых результатов в каждой ИсС (может быть пустым).

3.4.2. Спецификации процедур, вызывающих исключительные ситуации

За предложением returns в заголовок процедуры добавляется предложение: signals список имен и результатов ИсС. Например

Search =proc(a: array[real], x: real) returns(ind: int) signals (duplicate(ind1:int), not_in)

Это предложение говорит о том, что процедура Search может вызывать две ИсС: duplicate (результат – целое число) и not_in (без результата). Имя ind1 вводится для ссылок на дополнительный результат в остальной части спецификации. Как и раньше секция effects должна определять поведение процедуры для всех фактических аргументов, отвечающих предложению requires. Это поведение включает в себя и ИсС (что приводит к их вызову, и как реагирует процедура).

Спецификация процедуры Search:

Search =proc(a: array[real], x: real) returns(ind: int)
signals (duplicate(ind1:int), not_in)

requires массив a упорядочен по возрастанию

effects Если xÎa один раз, то возвратить ind, такой, что a[ind]=x. Если xÎa более чем 1 раз, то сигнализировать об исключительной ситуации duplicate (ind1), где ind1 – индекс для одного из x. Иначе сигнализировать об исключительной ситуации not_in.

Заметим, что в секции effects предполагается, что все требования предложения requires удовлетворены.

Область определения процедуры Search:

D₀={<a, x>|xÎa ровно один раз};

D₁={<a, x>|xÎa более чем один раз};

D₂={<a, x>|xÏa};

Здесь <a, x> – пара, состоящая из массива и вещественного числа.

Существует еще одна ИсС, кроме перечисленных в строке signals. Она имеет имя failure и один аргумент – строку (failure – неудача, неуспех). Каждая ИсС, возникшая в вызванной процедуре и не обрабатывающаяся явно в вызывающей процедуре, автоматически преобразуется в ситуацию failure. В процедуре Search failure(s) – ситуация, при которой входной аргумент a не отсортирован, либо программная или системная ошибка, s – имя ИсС и информация для программиста.

3.4.3. Использование исключительных ситуаций в программах

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

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

2. Маскирование ИсС вызывающей подпрограммой – полная обработка исключительной ситуации.

ИсС следует использовать для устранения большинства ограничений предложения requires. Эти ограничения следует оставлять только из соображений эффективности (с внесением риска) или если контекст использования ограничен (ограничения удовлетворяются). Например, в процедуре Search, возможно, стоит затратить некоторые усилия и выявить ИсС «массив не отсортирован», чтобы затем сигнализировать об исключительной ситуации процедуре failure.

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

Урок 19.

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

Тема : Структура и формат данных. Статические, полустатические и динамические структуры.

Цели:

Образовательная

Ознакомление со структурой и форматами данных.

Развивающая:

Развивать умение слушать других, делать выводы и обобщать полученные знания

Воспитательная:

Воспитывать чувство значимости предмета в профессиональной деятельности, аккуратности в работе

Межпредметные связи:

- Английский язык

- Операционные системы

- Информационные технологии

- Основы алгоритмизации и программирования

Оборудование: доска, мел, письменные принадлежности, проектор, ПК

Тип урока: комбинированный

Метод обучения: Объяснительно иллюстративный

Ход урока:

1.Организационный момент

- Проверка готовности кабинета

- Объявление темы

2. Постановка цели урока

3.Повторение пройденного материала

Технология разработки ПО

Требования к современным технологиям разработки ПО

Этапы проектирования сложных программных средств

Использование абстракций и спецификаций при разработке программ

4.Сообщение новых знаний

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

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

Простые структуры данных

Статические структуры данных

Динамические структуры данных

Полу статические структуры данных

5. Восприятие и осознание учащимися нового материала

6. Осмысление обобщение и систематизация знаний

7. Подведение итогов урока и постановка домашнего задания

Выучить содержимое темы

Гагарина Л.Г. стр. С.85-94

Ответить на вопросы: