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

end List

Реализация

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

Рисунок 1.Односвязный список с дескриптором из трёх элементов.

2.  На уровне языка программирования для описания элементов списка будем использовать следующие типы данных (Пример 1): T, Node, PNode, List, PList.

• T – тип элементов списка – простой тип, например T = integer;
• Node =  record

                                    key: T;

                                    next: PNode;

                        end;

- тип узлов списка. Узел списка содержит элемент данных в поле key типа T и указатель на следующий узел списка в поле Next типа PNode;

• PNode = ^Node;

- ссылочный тип, тип указателей (адресов) на узлы списка;

•   дескриптор списка List

                  List = record

                                    first: PNode;//указатель на первый элемент списка

                                    last : PNode;//указатель на последний элемент списка

                                    size : integer;//число элементов в списке

                        end;

• PList = ^List

- ссылочный тип список. Переменная типа PList содержит указатель на дескриптор списка или значение nil, если список не определён.

Таким образом, список мы реализуем как динамическую информационную структуру – список узлов, в которой узлы и дескриптор списка будут динамическими переменными.

3.  В качестве типа T для элементов списка (Пример 1) использован тип integer. В этом случае мы получаем список целых чисел.

4.  Приведённые выше типы данных, необходимые для реализации списка целых чисел и подпрограммы поместим в отдельный модуль UList. Ниже приводится (Пример 1), в котором даны описания типов, заголовков подпрограмм, реализующих операции на списке целых чисел и вспомогательных подпрограмм, необходимых для реализации операций на списке.

Пример 1. Реализация списка односвязного списка с дескриптором .

unit UList;

interface

uses SysUtils;

type

//---------------------Исключительные ситуации----------------------------------

  EListEmpty = class(Exception)

  end;

//---------------------Тип элементов списка-------------------------------------

  T = integer;

//---------------------Узел списка----------------------------------------------

  PNode = ^Node;

  Node = record

           key  : T;

           next : PNode;

         end;

// --------------------Дескриптор списка----------------------------------------

  PList = ^List;

  List = record

           first: PNode;//указатель на первый элемент списка

           last : PNode;//указатель на последний элемент списка

           size : integer;//число элементов в списке

         end;

// --Операции на списке---------------------------------------------------------

// --------------------Создать пустой список------------------------------------

  function  CreateL: PList;

// --------------------Число элементов списка-----------------------------------

  function  Size(L: PList): integer;

// --------------------Список пуст----------------------------------------------

  function  IsEmpty(L: PList): Boolean;

// --------------------Взять голову списка (слева)------------------------------

  function  Head(L: PList): T;

// --------------------Взять голову списка (справа)-----------------------------

  function  Head_(L: PList): T;

// --------------------Выделить хвост списка (слева)----------------------------

  function  Tail(var L: PList): PList;

// --------------------Выделить хвост списка (справа)---------------------------

  function  Tail_(var L: PList): PList;

// --------------------Добавить элемент к списку (справа)-----------------------