Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
⚡️ Для новых пользователей первый месяц бесплатно. А далее 290 руб/мес, это в 3 раза дешевле аналогов. За эту цену доступен весь функционал: напоминание о визитах, чаевые, предоплаты, общение с клиентами, переносы записей и так далее.
✅ Уйма гибких настроек, которые помогут вам зарабатывать больше и забыть про чувство «что-то мне нужно было сделать».
Сомневаетесь? нажмите на текст, запустите чат-бота и убедитесь во всем сами!
Двусвязные списки
|
|
В двусвязных списках базовый комбинированный тип S для указателей типа P будет иметь два адресных поля: поле ls ссылки на следующую запись списка и поле lp ссылки на предыдущую запись списка. Описание двусвязных списков аналогично приведенному выше (для односвязных списков) с отличием в структуре S:
P=^S; {тип указатель записи базового типа S}
S=Record {базовый тип для указателей типа Р}
ls: P; {поле типа Р ссылки на следующую запись}
lp: P; {поле типа Р ссылки на предыдущую запись}
Dt: Z {поле типа Z записи данных}
end;
 |
При работе с одно- и двусвязными списками нужно уметь добавлять элементы в любое место списка, удалять заказанный элемент из списка и перемещаться по списку с целью поиска или выбора информации из списка. Необходимо определять, пуст ли список в данный момент.
Обычно считается, что список пуст, если в нем имеется только звено заголовка и нет ни одного звена с данными. При работе с такими списками в начале необходимо создать заголовок (процедурой New), а в конце программы этот заголовок должен быть удален процедурой Dispose. Добавление звена в список и удаление из списка обычно оформляется в виде процедур. Перемещение по списку чаще всего выполняется с помощью итеративного цикла (" …Пока не достигнем звена с нужными данными или не просмотрим весь список…"). Ниже приведены некоторые примеры процедур для разных видов списков. Проверка " пуст ли список" обычно нужна для того, чтобы упростить процедуры работы со списками, так как с пустыми списками не все операции возможны.
Для линейных и кольцевых списков с заголовком вне кольца, проверяется ссылка из заголовка на следующее звено. Если Uz^.ls=nil, то список пуст. Для кольцевых с заголовком в кольце – если Uz^.ls=Uz, то список пуст.
Пример процедуры добавления элемента в линейный односвязный список (определяемый указателем Uz) после звена, заданного текущим указателем (U).
procedure PutS1(Var U: P; E: Z);
var
q: P1; { Завели рабочий указатель }
begin
new(q); { Создаем новое звено, пока вне списка }
q^.Dt: =E; { заполняем его информацией }
q^.ls: =U^.ls; {подцепляем к новому звену конец списка за U }
U^.ls: =q {подцепляем к началу списка (до U) новое звено}
end;
Если добавлять элемент нужно в начало списка (на которое ссылается заголовок списка), при вызове процедуры в качестве первого параметра приводится указатель заголовка списка.
Пример процедуры удаления элемента, заданного текущим указателем (U) из линейного двусвязного списка.
procedure DelS2(Var U: P);
var
q: P; { Завели рабочий указатель }
begin
q: =U^.lp; {q указывает звено перед тем, на которое указывает U }
q^.ls: =U^.ls; {в звене q^ меняем ссылку на следующее звено – за U^}
if U^.ls< > nil then {если удаляемое звено – не последнее, то }
begin
q: =U^.ls; { в звене за удаляемым }
q^.lp: =U^.lp { меняем ссылку на предыдущее звено }
end;
dispose(U); { собственно удаление звена }
U: =nil { очистка указателя на удаленное звено }
end;
После срабатывания этой процедуры текущий указатель перестает указывать на что-либо (равен nil).
Пример процедуры удаления элемента, заданного текущим указателем (U) из кольцевого двусвязного списка.
procedure DelS2K(Var U: P);
var
q: P;
begin
q: =U^.lp;
q^.ls: =U^.ls;
q: =U^.ls;
q^.lp: =U^.lp;
dispose(U);
U: =nil;
end;
Выбор данных из списка производится без изменения списка, путем ссылки на информационную часть нужного звена: U^.Dt. Чтобы добраться до нужного звена списка, по нему приходится последовательно перемещаться (в цикле, начиная от начала или от текущего звена). Так же как при работе с массивом, для перехода от элемента A[i] к следующему элементу необходимо выполнить i: =i+1.
При работе со списком следует использовать оператор U: =U^ls.
Создав список (в цикле, используя процедуру добавления звена) и поработав с ним, необходимо в конце программы удалить его (также, в цикле, используя процедуру удаления элемента списка, пока он не станет пустым). После этого не забыть удалить заголовок списка.
|
|