Вставка элемента перед заданным (но не первым) элементом A
| Исходный список |
|
Вставить элемент после заданного (см. выше), затем поменять местами значения полей inf заданного и нового элементов.
Удаление заданного (но не первого) элемента
| Исходный список | Список после удаления элемента |
| 
|
Выполнить проход (c) по списку с двумя указателями в поисках заданного элемента А.
Если элемент найден, выполнить:
pred^.next:=p^.next;//Изменение поля ссылки в предшествующем элементе для обхода удаляемого
Dispose(p); //Освобождение памяти, которую занимал удаляемый элемент
p:=nil
Вставка элемента в конец списка
| Исходный список | Список после вставки |
| 
|
Выполнить проход (b) по списку с проверкой наличия элемента, следующего за текущим, затем:
new(q);
q^.inf:=x;
q^.next:=nil;//Новый элемент никуда не ссылается
p^.next:=q; //Установка ссылки бывшего последнего элемента на новый элемент
Вставка элемента перед последним
| Исходный список | Список после вставки |
| 
|
Вставить элемент в конец списка (см. выше), затем поменять местами значения полей inf последнего и нового элементов.
Удаление последнего элемента
| Исходный список | Список после удаления |
| 
|
Выполнить проход (d) по списку с двумя указателями и с проверкой
наличия элемента, следующего за текущим, затем:
pred^.next:=nil;{Предпоследний элемент становится последним}
Dispose(p); {Освобождение памяти, которую занимал последний элемент}
p:=nil;
Операции над каждым элементом односвязного линейного списка
Cумма элементов списка
p :=Head;
Sum:=0;
while p<>nil do
begin
Sum:=Sum+p^.inf;
p:=p^.next
end;
Поиск максимального элемента списка
p :=Head;
pmax:=p; //Первый элемент полагаем максимальным
while p<>nil do
begin
if (p^.inf > pmax^.inf) then pmax:=p;
p := p^.next
end; //На выходе указатель pmax ссылается на элемент с максимальной информационной частью
Вывод элементов списка в прямом порядке
procedure PrintList(p: ref);{Параметр p указывает на начало списка}
const str=' -> '; //Стрелка для отделения элементов списка при выводе
begin
while (p <> Nil) do
begin
write(str, p^.inf); //Вывод поля inf текущего элемента
p := p^.next
end;
writeln
end;
Вывод списка на экран в строку в обратном порядке рекурсивно
procedure RevPrintList(p:ref);{Параметр p указывает на начало списка}
const str=' <- '; //Стрелка для отделения элементов списка при выводе
begin
if (p <> nil) then
begin
RevPrintList(p^.next);
write(p^.inf, str) //Вывод поля inf текущего элемента на рекурсивном возврате
end;
Пример.
Создать односвязный линейный список с включением новых элементов в начало списка, вывести элементы списка в прямом и в обратном порядке
function NewElem(p: ref; x: integer): ref; {Создание нового элемента.
Параметр p указывает на начало списка}
var q: ref;
begin
new(q); {Выделение в динамической памяти места для нового элемента}
q^.inf:=x; {Заполнение поля данных}
q^.next:=p; {Заполнение поля ссылки}
Result:=q; {Результат функции – ссылка на новый элемент}
end;
begin
Head:= nil; {Создание пустого списка}
repeat
write('Элемент='); readln(x); {Ввод очередного числа}
if (x<>0) then
Head:=NewElem(Head, x);{Создание элемента и присоединение к голове списка}
until (x=0);
PrintList(Head); {Вывод списка от начала к концу}
RevPrintList(Head); {Рекурсивный вывод списка от конца к началу}
writeln;
end.
Стеки
Стек – динамическая структура данных, представляющая из себя упорядоченный набор элементов, в которой добавление новых элементов и удаление существующих производится с одного конца, называемого вершиной стека.
По определению, элементы извлекаются из стека в порядке, обратном их добавлению, т.е. действует принцип «последним пришёл – первым вышёл» (LIFO – Last In First Out).
Основные операции над стеком:
• Занесение в стек (принято называть Push);
• Выборка из стека (принято называть Pop);
Дополнительные операции:
• Создание пустого стека (DoTop);
• Проверка, пуст ли стек (IsEmpty);
• Просмотр элемента в вершине стека без удаления (InTop);
• Перемена местами двух элементов в вершине стека (Swap).