Динамические структуры данных

Наибольшее распространение среди динамических структур данных получили списки. Списком называется структура данных, каждый элемен которой содержит ссылку, указывающую на следующий элемент списка. Последний элемент указывает на Nil.

Для организации списков используются записи, состоящие из двух частей: информационной, которая и содержит всю информацию, подлежащую обраюотке, и адресной – указателя на следующий элемент списка.

Организации списков

Описание отдельного элемента списка целых чисел имеет вид:

Обратите внимание на то, что в данном случае допустимо использование типа List до его непосредственного описания. Такое исключение в Турбо-Паскале сделано только для описания динамических структур данных.

Рассмотрим общую схему формирования списка. Допустим, в программе с использованием приведенного выше типа были объявлены два указателя u1 и u2.

Размещаем в памяти динамическую переменную u1^ типа запись, являющуюся первым элементом списка.

New(u1);      {размещение 1-го элемента списка}
Read(u1^.x);  {ввод значения 1-го элемента списка}
u1^.adr:=Nil; {следующий элемент пока отсутствует}
u2:=u1;       {адрес 1-го элемента списка используется для формирования ссылки на 2-й элемент}

Размещаем второй элемент списка, все следующие элементы размещаются аналогично второму.

New(u2^.adr); {размещение 2-го (следующего) элемента списка и помещение его адреса в адресную часть 1-го (предыдущего) элемента}
u2:=u2^.adr;  {переход ко 2-му (следующему) элементу списка}
Read(u2^.x);  {ввод значения 2-го элемента списка}
u2^.adr:=Nil; {следующий элемент пока отсутствует}

Теперь каждый элемент списка содержит ссылку на следующий элемент. Последний элемент не содержит никакой ссылки – на нем список заканчивается.

Ниже приведена процедура вставки в описанный ранее список нового элемента с информационной частью, равной Inf, после элемента u0.

Пример 24

Процедура удаления элемента, следующего за элементом u0, из списка.

Пример 25

Вчера у меня наконец закончился ремонт. И не сказать, чтобы долго он шёл, но всё таки. Фирма не соврала, что выполняет качественный ремонт квартир. Так ещё и получил семилетнюю гарантию на проведённые работы. Доволен как слон!

Оставить комментарий

Лучшие статьи