Динамические структуры и абстракции данных, страница 8

     L:= nil;

  end

end;

end.

Рассмотрим подробнее реализацию операции добавить элемент данных к списку справа. Текст программы, реализующей операцию приведён ниже.

Реализацию операции начнём с анализа зависимости её выполнения от состояния списка. Под состоянием будем понимать число элементов в списке. С точки зрения этой операции в списке можно выделить два состояния:

список пуст и список не пуст.

Если список пуст, то операция выполняет следующие действия:

создаётся узел списка, в поле данных которого заносится элемент данных полученный операцией через параметр. Указатель на созданный узел заносится в поля first и last дескриптора списка, поскольку этот элемент в списке единственный и является одновременно и первым и последним. Поле size дескриптора списка  увеличивается на 1.

Если список не пуст (в не зависимости от числа элементов в нём), то операция выполняет следующие действия: создаётся узел списка, в поле данных которого заносится элемент данных полученный операцией через параметр. Указатель на созданный узел заносится в поля last дескриптора списка. Поле size дескриптора списка  увеличивается на 1.

//------------------------------------------------------------------------------

procedure AddRight(L: PList; E: T);

//Добавляет элемент к списку справа

begin

  if (L <> nil)

    then

      with L^ do

        case size of

          0: begin            // список пуст

               first:= CreateE(E);

               last:= first;

               inc(size)

             end;

          else       //список не пуст

            Last^.next:= CreateE(E);

            Last:= Last^.next;

            inc(size)

        end

end;

Рассмотрим подробнее реализацию операции взять голову списка, рассматривая список справа налево. Текст программы, реализующей операцию приведён ниже.

Реализацию операции начнём с анализа зависимости её выполнения от состояния списка. Под состоянием будем понимать число элементов в списке. С точки зрения этой операции в списке можно выделить два состояния: список пуст и список не пуст.

Если список пуст, то операция не определена. Поэтому эта операция не применима к пустому списку.

Если список не пуст (в не зависимости от числа элементов в нём), то операция выполняет следующие действия: возвращает значение элемента данных последнего узла списка, отыскивает адрес предпоследнего узла, удаляет последний узел, в поле last дескриптора заносит найденный адрес предпоследнего узла,  в поле next вновь образовавшегося последнего узла заносит значение nil, поле size дескриптора списка  уменьшает на единицу (изменяем размер списка).

//------------------------------------------------------------------------------

function Head_(L: PList): T;

//Выделяет из списка L элемент списка, который является его головой (справа),

//и возвращает указатель на него

var

  p: PNode;

begin

  if L = nil then //Список не существует

    exit;

  if Size(L) > 0

    then //Список не пуст

      with L^ do

      begin

        Result:= last^.key;

        last:= PredLast(L,p);

        dispose(last);

        last:= p;

        last^.next:= nil;

        size:= size - 1;

        if size = 0

          then

            begin last:= nil; first:= nil end

      end

    else

      raise EListEmpty.Create('Список пуст');

end;

Таблица 2. Тестовый набор для тестирования списка целых чисел.

Тестовый набор для тестирования операции ГоловаСправа
Номер теста	Исходные данные		Ожидаемый результат
	Вход	Состояние списка	Возвращаемое значение	Состояние списка
1	Нет	()	Не определено.	()
2	Нет	(3)	3	()
3	Нет	(3 5 2)	2	(3 5)

Стек

Стек - это абстрактный тип данных, который обеспечивает доступ к данным по принципу LIFO (поступивший последним обслуживается первым).