Структуры и алгоритмы обработки данных


Линейные списки


Наиболее простой способ связать некоторое множество элементов - это организовать линейный список. При такой организации элементы некоторого типа образуют цепочку. Для связывания элементов в списке используют систему указателей. В рассматриваемом случае любой элемент линейного списка имеет один указатель, который указывает на следующий элемент в списке или является пустым указателем, что означает конец списка.

pic1_1.jpg (5129 bytes)

Рис. 1.1. Линейный список (связанный список)

В языке Turbo Pascal предусмотрены два типа указателей v типизированные и не типизированные указатели. В случае линейного списка описание данных может выглядеть следующим образом.

type

element = record

                   data:string;

                   next: pointer;

       end;

var

       head: pointer;

       current, last : ^element;

В данном примере элемент списка описан как запись, содержащая два поля. Поле data строкового типа служит для размещения данных в элементе списка. Другое поле next представляет собой не типизированный указатель, который служит для организации списковой структуры.

В описании переменных описаны три указателя head, last и current. Head является не типизированным указателем. Указатель current является типизированным указателем, что позволяет через него организовать доступ к полям внутри элемента, имеющего тип element. Для объявления типизированного указателя обычно используется символ ^, размещаемый непосредственно перед соответствующим типом данных. Однако описание типизированного указателя еще не означает создание элемента списка. Рассмотрим, как можно осуществить создание элементов и их объединение в список.

В системе программирования Turbo Pascal для размещения динамических переменных используется специальная область памяти heap-область¦.


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



Книжный магазин