Динамические структуры данных. Алексеев А.Ю - 5 стр.

UptoLike

ВУЗ: 

КамчатГТУ | Петропавловск-Камчатский

Составители: 

Рубрика: 

Info Next
Info Next
а
Рис. 1.2. Изображения: а - отдельного звена списка;
б - пустой ссылки; в - последнего звена в списке
Рис. 1.3. Пример изображения Л1-списка
На Паскале такое цепное представление списка может быть реализовано,
например [xx], с использованием ссылочных переменных. Соответствующие
типы данных можно описать в виде
type
El = ... ; { базовый тип для элементов списка }
Link = ^Node; { ссылка на звено в цепи }
Node = record { звено цепи ( списка ) : }
Info : El; { содержимое (элемент списка) }
Next : Link ; { ссылка на следующее звено }
end {Node} ;
Длина списка в этом случае ограничивается только размерами доступной
динамической памяти, в которой размещаются элементы списка (звенья цепи),
связанные ссылками.
Для работы со списком удобно описать дополнительную переменную типа
Link (например, var s : Link) и использовать ее как указатель на начало списка
(рис. 1.4). Если список пуст, то s = nil.
Рис. 1.4. Пример изображения Л1-списка с указателем на начало
Другим возможным способом реализации цепного представления Л1–
списка на Паскале является ссылочная реализация на базе вектора. В качестве
ссылок в этом случае используются номера элементов вектора, предназначен-
ных для хранения звеньев цепи (элементов списка). Как ссылочная реализация
Л1–списка в динамической памяти, так и реализация на базе вектора подробно
рассмотрены далее в 1.3, 1.4.
б
в
a b c d
s:
a
b c d
5
       Info    Next                                              Info     Next



              а                               б                           в


                      Рис. 1.2. Изображения: а - отдельного звена списка;
                         б - пустой ссылки; в - последнего звена в списке



              a                 b             c             d



                             Рис. 1.3. Пример изображения Л1-списка

   На Паскале такое цепное представление списка может быть реализовано,
например [xx], с использованием ссылочных переменных. Соответствующие
типы данных можно описать в виде
type
El = ... ;                           { базовый тип для элементов списка }
Link = ^Node;                        { ссылка на звено в цепи           }
Node = record                        { звено цепи ( списка ) :          }
       Info : El;                    { содержимое (элемент списка)      }
       Next : Link ;                 { ссылка на следующее звено       }
       end {Node} ;
    Длина списка в этом случае ограничивается только размерами доступной
динамической памяти, в которой размещаются элементы списка (звенья цепи),
связанные ссылками.
    Для работы со списком удобно описать дополнительную переменную типа
Link (например, var s : Link) и использовать ее как указатель на начало списка
(рис. 1.4). Если список пуст, то s = nil.


      s:                 a              b             c               d


              Рис. 1.4. Пример изображения Л1-списка с указателем на начало

   Другим возможным способом реализации цепного представления Л1–
списка на Паскале является ссылочная реализация на базе вектора. В качестве
ссылок в этом случае используются номера элементов вектора, предназначен-
ных для хранения звеньев цепи (элементов списка). Как ссылочная реализация
Л1–списка в динамической памяти, так и реализация на базе вектора подробно
рассмотрены далее в 1.3, 1.4.
                                                  5

Страницы