На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! Друзья, соблюдайте, пожалуйста, правила форума и данного раздела:
Данный раздел не предназначен для вопросов и обсуждений, он содержит FAQ-заготовки для разных языков программирования. Любой желающий может разместить здесь свою статью. Вопросы же задавайте в тематических разделах!
• Если ваша статья может быть перенесена в FAQ соответствующего раздела, при условии, что она будет оформлена в соответствии с Требованиями к оформлению статей.
• Чтобы остальным было проще понять, указывайте в описании темы (подзаголовке) название языка в [квадратных скобках]!
Модераторы: Модераторы
  
> Стек , [Pascal] реализация списком
    Теоретические основы.

    Стек - конструкция, похожая на колодец. Глубина неизвестна, но видно, если он пуст. Виден только верхний его элемент. Используется достаточно часто, в задачах, в которых нужно обрабатывать некоторое множество сгенерированных величин с конца. В англоязычной литературе для обозначения конструкции типа стек используются аббревиатуры LIFO или FILO - Last In First Out, или First In Last Out, т.е. "что последним положили, первым забрали", или наоборот, но смысл от этого не меняется. Стек понимает всего 3 операции: Push, Pop и относительно редко используемую IsEmpty:boolean - проверку на пустоту, которая используется обычно внутри обработки РОР"а.

    Простая реализация.

    Основная списковая реализация является едва ли не простейшей, а именно, для списка-стека достаточно хранить в переменной лишь его голову, для стека она является вЕрхом.

    ExpandedWrap disabled
      type stack=^internal_stack_record;
      internal_stack_record=record
        el:integer;{вообще говоря, что угодно, вплоть до других стеков, принцип не меняется}
        next:stack;
      end;
      Procedure Push(var x:stack;element:integer); {Положить element в стек x}
      var t:stack;
      begin
        new(t); {Создаем новый элемент списка}
        t^.el:=element; {Заполняем значение тем, которое нам подарили в параметре}
        t^.next:=x;  {Связываем новый элемент с остальным списком, даже если он пуст}
        x:=t;  {Сдвигаем голову, теперь она указывает на только что созданный элемент}
      end; {Все...}
      Procedure Pop(var x:stack;var element:integer); {Обратная операция}
      var t:stack;
      begin
        t:=x; {Сохраняем голову, она еще понадобится}
        if t=nil then begin
          writeln('Error in stack operation, stack is empty in POP!');
          exit {Аварийный выход из процедуры}
        end; {Та самая проверка на ошибки. Может быть имеет смысл положить что-либо в результат...
              Сейчас он не определен, точнее не изменен.}
        element:=t^.el; {Возвращаем значение}
        x:=t^.next; {Выкидываем голову из остального списка, мы ее обработали}
        dispose(t); {Чистим за собой память, пока этого не сделали, Паскаль будет считать место занятым, хотя оно уже ни к чему не привязано}
      end;

    Просто и элегантно. Иногда удобнее программировать РОР как функцию, а не как процедуру, например в данном случае, так как вытащенное значение весьма вероятно будет нужно сразу же в вычислениях. К сожалению, если элемент стека - некоторая структура, Паскаль не сможет ее вернуть как результат функции, и тогда нужно явно указывать переменную для хранения результата. Вот код для РОР, реализованной как функция:
    ExpandedWrap disabled
      Function Pop(var x:stack):integer;
      var t:stack;
      begin
        t:=x;
        if t=nil then begin
          writeln('Error in stack operation, stack is empty in POP!');
          Pop:=-1; {Вот здесь без возвращаемого значения не обойтись, в лучшем стиле С++ возвращаем -1. Хехе.}
          exit {Аварийный выход из процедуры}
        end;
        Pop:=t^.el;
        x:=t^.next;
        dispose(t);
      end;


    Защита структуры данных.

    Для того, чтобы такая реализация работала корректно, необходимо, чтобы внутренняя структура данных не изменялась вне операций со стеком, и также необходима начальная инициализация, здесь это присвоение голове (или верху) стека значения NIL до выполнения каких-либо операций. К сожалению, проконтролировать соблюдение этих условий невозможно без какого-либо метода защиты. Голова списка доступна извне, и неумелый программист может нечаянно ее изменить, например переприсвоить ей NIL или указатель на другой стек, в котором может быть другое число элементов. Или какой-нибудь очень хитрый программист будет с ним работать и как со стеком, и как со списком, в результате чего могут появиться трудновылавливаемые ошибки. Следовательно, нужно каким-либо образом перекрыть явный доступ до структуры данных, кроме как из предназначенных для ее обработки подпрограмм. Такую возможность предоставляет ООП.

    Реализация защищенного стека.

    Объект представляет собой связанные между собой данные и подпрограммы для их обработки (методы). В нашем защищенном стеке нужно объявить список как структуру данных и спрятать его от прямого доступа извне, и описать все методы, которые будут работать с этой структурой. Описание выглядит так:
    ExpandedWrap disabled
      type hidden_stack=object
        constructor init;
        procedure push(a:integer); virtual;
        function pop:integer; virtual;
        function IsEmpty:boolean;
        destructor done; virtual;
      private
        kernel:stack;
      end;

    Директива private скрывает от внешнего доступа все описанные ниже поля и методы вплоть до следующей директивы public (открытый) или до конца описания самого объекта.
    Директивы virtual в описании методов нужны для возможного наследования методов объекта в его потомках, например хэш-таблице (хотя вряд ли кому понадобится наследовать такой простой тип), а также для того, чтобы программист сначала вызвал конструктор init перед какими-либо действиями с объектом. Конструктор предназначен для подготовки нашего стека к работе, в нем нужно выполнить инициализацию стека, что мы и делаем:
    ExpandedWrap disabled
      constructor hidden_stack.init;
      begin
        kernel:=nil;
      end;

    Деструктор служит для очистки возможных "хвостов" при уничтожении объекта, например мы можем убрать использованный, но непустой стек. (В принципе, это единственный хвост здесь, соответственно именно очистку оставшегося стека в нем и нужно реализовать.) Делается это вот как:
    ExpandedWrap disabled
      destructor hidden_stack.done;
      var t:stack;
      begin
        while kernel<>nil do begin
          t:=kernel;
          kernel:=t^.next;
          dispose(t);
        end;
      end;

    А собственно имя структуры kernel я выбрал из-за того, что этот уже отлаженный стек есть "ядро ореха", скорлупу которого мы недавно написали. Реализации Push и Pop следующие:
    ExpandedWrap disabled
      Procedure hidden_stack.Push; {заголовок описывать необязательно, так как он описан уже внутри описания объекта}
      var t:stack;
      begin
        new(t);
        t^.el:=element;
        t^.next:=kernel;
        kernel:=t;
      end;
      function hidden_stack.pop;
      var t:stack;
      begin
        if IsEmpty then begin
          pop:=-1;
        exit end;
        t:=kernel;
        pop:=t^.el;
        kernel:=t^.next;
        dispose(t);
      end;

    Ну и на всякий случай функция IsEmpty, которая проверяет стек на пустоту:
    ExpandedWrap disabled
      function hidden_stack.IsEmpty;
      begin
        IsEmpty:=kernel=nil;
      end;

    Используется созданный стек немного по-другому, чем список. Его не нужно в явном виде передавать в методы как параметр, но для обращения к его методам нужно использовать квалификатор ".", такой же, как при обращении к полям записи.
    ExpandedWrap disabled
      var x:hidden_stack;
          i:integer;
      begin
        x.init;
        x.push(2);
        i:=x.pop;
        if x.IsEmpty then writeln('Stack X is empty now.');
        x.done;
      end.

    Вызов деструктора done в конце программы необязателен, так как память все равно будет очищена при выходе, но для соблюдения правил "хорошего кода" его нужно написать.
    Сообщение отредактировано: Jin X -
    0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
    0 пользователей:


    Рейтинг@Mail.ru
    [ Script execution time: 0,0227 ]   [ 15 queries used ]   [ Generated: 30.05.24, 21:28 GMT ]