В начале программы необходимо описать элемент и его тип:
Type tpel=^element; {тип «указатель на элемент»}
element=record
num: integer; {число}
p:tpel; {указатель на следующий элемент}
end;
В статистической памяти описываем переменную-указатель списка и несколько пе-ременных-указателей, используемых при выполнении операций со списком:
Var first, {указатель списка – адрес первого элемента списка}
n,f,q:tpel; {вспомогательные указатели}
исходное состояние «список пуст»:
first:=nil;
Добавление нового элемента к списку. Добавление элемента к списку включает запрос памяти для размещения элемента и заполнение его информационной части. По-строенный таким образом элемент добавляется к уже существующей части списка.
В общем случае при добавлении элемента к списку возможны следующие варианты:
• Список пуст, добавляемый элемент станет единственным элементом списка.
• Элемент необходимо вставить перед первым элементом списка.
• Элемент необходимо вставить перед заданным элементом списка.
• Элемент необходимо дописать в конец списка.
Добавление к пустому списку состоит из записи адреса элемента в указатель списка, причем в поле «адрес следующего» добавляемого элемента необходимо поместить nil;
new(first); {запрашиваем память под элемент}
first^.num:=5; {заносим число в информационное поле}
first^.p:=nil; {записываем nil в поле «адрес следующего»}
Добавление элемента перед первым элементом списка. При выполнении этой операции необходимо в поле «адрес следующего» переписать адрес первого элемента списка, а в указатель списка занести адрес добавляемого элемента:
new(q); {запрашиваем память под элемент}
q^.num:=4; {заносим число в информационное поле}
q^.p:=first; {в поле «адрес следующего» переписываем адрес первого элемента}
first:=q; … {в указатель списка заносим адрес нового элемента}
Добавление элемента перед заданным. Для выполнения операции необходимо знать адреса элементов, между которыми вставляется элемент, так как адресные части этих элементов при выполнении операции будут корректироваться. Пусть f – адрес предыдущего элемента, а n – адрес следующего элемента, тогда:
new(q); {запрашиваем память под элемент}
q^.num:=3; {заносим число в информационное поле}
q^.p:=n; {в поле «адрес следующего» нового элемента переписываем адрес следующего элемента}
f^.p:=q; …{в поле «адрес следующего» предыдущего элемента заносим адрес ново-го элемента}
Минимально для вставки элемента в линейный односвязный список необходимо знать только адрес предыдущего элемента, так как тогда адрес следующего элемента известен – n f^.p;
new(q); {запрашиваем память под элемент}
q^.num:=3; {заносим число в информационное поле}
q^.p:=f^.p; {в поле «адрес следующего» нового элемента переписываем адрес следующего элемента}
f^.p:=q; … {в поле «адрес следующего» предыдущего элемента заносим адрес нового элемента}
Добавление элемента в конец списка. В этом случае должен быть известен адрес элемента, после которого добавляется новый элемент.
new(q); {запрашиваем память под элемент}
q^.num:=7; {заносим число в информационное поле}
q^.p:=nil; {в поле «адрес следующего» нового элемента записываем nil}
f^.p:=q; …{в поле «адрес следующего» предыдущего элемента заносим адрес ново-го элемента}
Просмотр и обработка элементов списка. Просмотр и обработка элементов списка выполняется последовательно с использованием дополнительного указателя:
f:=first;
while f<>nil do
begin
<обработка элемента по адресу f>
f:=f^.p;
end;…
В качестве примера рассмотрим вывод на экран элементов списка:
f:=first;
while f<>nil do
begin
writeln (f^.num,’ ‘);
f:=f^.p;
end;…
Поиск элемента в списке. Поиск элементов в списке также выполняется последовательно, но при этом, как это и положено в поисковом цикле, обычно организуют выход из цикла, если нужный элемент найден, и осуществляют проверку после цикла, был ли найден элемент:
f:=first;
flag:=false;
while (f<>nil) and (not flag) do
begin
if f^.num=k then flag:=not flag
else f:=f^.p;
end;
if flag then <элемент найден>
else<элемент не найден>; …
Удаление элемента из списка. При выполнении операции удаления также возможны четыре случая:
• Удаление единственного элемента.
• Удаление первого (не единственного) элемента списка.
• Удаление элемента, следующего за данным.
• Удаление последнего элемента.
Удаление единственного элемента.После удаления единственного элемента спи-сок становиться пустым, следовательно при выполнении этой операции необходимо не только освободить память, выделенную для размещения элемента, но и занести nil в указатель списка first:
Dispose(first);
first:=nil; …
Удаление первого (неединственного) элемента списка. Удаление первого элемента состоит из сохранения адреса следующего в рабочей переменной f, освобождения памяти элемента и записи в указатель списка сохраненного адреса следующего элемента:
f:=first^.p; {сохраняем адрес следующего элемента}
dispose(first); {освобождаем память}
first:=f; … {заносим в указатель списка адрес следующего элемента}
Удаление элемента, следующего за данным (не последнего). Удаление элемента, следующего за данным, требует запоминания адреса удаляемого элемента, изменения адресной части данного элемента и освобождения памяти.
n:=f^.p; {сохраняем адрес удаляемого элемента}
f^.p:=n^.p; {заносим в адресное поле предыдущего элемента адрес следующего}
dispose(n); … {освобождаем память}
Удаление последнего элемента. Удаление последнего элемента отличается только тем, что в поле «адрес следующего» заданного элемента записывается константа nil:
n:=f^.p;
f^.p:=nil;
dispose(n); …
Удаление последнего элемента можно свести к удалению элемента, следующего за данным, так как адресная часть удаляемого элемента равна nil. Комбинируя приемы удаления, мы можем организовать любую дисциплину удаления.
