41385d94

Рисунок на предыдущей странице иллюстрирует


Рисунок на предыдущей странице иллюстрирует операцию put(s, x), выполняемую над стеком s и элементом x.

  • Функция remove возвращает новое состояние стека с вытолкнутым верхним элементом, если таковой был. Как и put, эта функция при проектировании и реализации должна превращаться в команду (операцию, изменяющую объект, обычно реализуемую как процедура). Мы увидим далее, как учесть возможность пустого стека, с вершины которого нечего удалять.


  • Функция item возвращает верхний элемент стека, если таковой имеется.


  • Функция empty выявляет пустоту стека, ее результатом является логическое значение (истина или ложь). Предполагается, что АТД BOOLEAN, задающий логические значения, определен отдельно.


  • Функция new создает пустой стек.


  • В разделе ФУНКЦИИ эти функции определяются не полностью, вводятся только их сигнатуры - списки типов их аргументов и результата. Сигнатура функции put

    STACK [G] × G → STACK [G]

    показывает, что put берет в качестве аргумента пару вида <s,x>, в которой s - экземпляр типа STACK [G], а x - экземпляр типа G, и возвращает в качестве результата экземпляр типа STACK [G]. Вообще говоря, множество значений функции (его тип указывается в сигнатуре правее стрелки, здесь это STACK [G]) может само быть декартовым произведением. Это можно использовать при описании операций, возвращающих два или более результатов.

    В сигнатуре функций remove и item вместо обычной стрелки используется перечеркнутая стрелка
    . Это означает, что эти функции применимы не ко всем элементам множества входов. Описание функции new выглядит просто как

    new: STACK

    без всякой стрелки в сигнатуре. Фактически, это сокращение для записи

    new: → STACK,

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


    Начало  Назад  Вперед





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