Программа создания и обработки линейного списка

 

Линейный список – это структура данных, представляющая собой последовательность компонент, связанных между собой адресами, как показано на рис. 1.

PN

 

Информ. Поле1

Адрес 2-го элемента

 

Информ. Поле2

Адрес 3-го элемента

 

………..

 

 

Информ. Поле n-1

Адрес n-го элемента

 

Информ. Поле n

nil

 

	Рис. 10.1.

 

На рис. 10.1 используются следующие обозначения:

PN – адрес первого элемента списка, который запоминается для работы со списком при его создании;

nil - признак последнего элемента списка.

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

- создание пустого списка;

- последовательный просмотр списка и поиск заданного элемента;

- добавление нового элемента в упорядоченный список;

- добавление элемента в конец списка;

- добавление элемента в начало списка;

- удаление заданного элемента из списка.

В программе на языке Паскаль элемент линейного списка объявляется с помощью типа «запись» следующего вида:

Туре TElem = recodrd

Inf: integer; {информационное поле}

Next: TPtr { поле связи (адрес следующего элемента списка) }

End;

TPtr – тип «указатель», который объявляется следующим образом:

Type TPtr=^ TElem;

Указательный тип используется для определения переменных, значением которых являются адреса размещенных в памяти переменных, тип которых совпадает с типом указателя. Для размещения в памяти элементов списка используется стандартная процедура динамического распределения памяти; в языке Паскаль эта процедура имеет имя New. Для удаления элемента из списка служит стандартная процедура освобождения памяти Dispose. Адресное поле последнего элемента списка содержит значение nil, специальный, пустой адрес, который является признаком конца списка.