Вставка элемента перед заданным (но не первым) элементом A

Исходный список
Вставка элемента перед заданным (но не первым) элементом A - student2.ru

Вставить элемент после заданного (см. выше), затем поменять местами значения полей inf заданного и нового элементов.

Удаление заданного (но не первого) элемента

Исходный список Список после удаления элемента
Вставка элемента перед заданным (но не первым) элементом A - student2.ru Вставка элемента перед заданным (но не первым) элементом A - student2.ru

Выполнить проход (c) по списку с двумя указателями в поисках заданного элемента А.

Если элемент найден, выполнить:

pred^.next:=p^.next;//Изменение поля ссылки в предшествующем элементе для обхода удаляемого

Dispose(p); //Освобождение памяти, которую занимал удаляемый элемент

p:=nil

Вставка элемента в конец списка

Исходный список Список после вставки
Вставка элемента перед заданным (но не первым) элементом A - student2.ru Вставка элемента перед заданным (но не первым) элементом A - student2.ru

Выполнить проход (b) по списку с проверкой наличия элемента, следующего за текущим, затем:

new(q);

q^.inf:=x;

q^.next:=nil;//Новый элемент никуда не ссылается

p^.next:=q; //Установка ссылки бывшего последнего элемента на новый элемент

Вставка элемента перед последним

Исходный список Список после вставки
Вставка элемента перед заданным (но не первым) элементом A - student2.ru Вставка элемента перед заданным (но не первым) элементом A - student2.ru

Вставить элемент в конец списка (см. выше), затем поменять местами значения полей inf последнего и нового элементов.

Удаление последнего элемента

Исходный список Список после удаления
Вставка элемента перед заданным (но не первым) элементом A - student2.ru Вставка элемента перед заданным (но не первым) элементом A - student2.ru

Выполнить проход (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.

Стеки

Вставка элемента перед заданным (но не первым) элементом A - student2.ru Стек – динамическая структура данных, представляющая из себя упорядоченный набор элементов, в которой добавление новых элементов и удаление существующих производится с одного конца, называемого вершиной стека.

По определению, элементы извлекаются из стека в порядке, обратном их добавлению, т.е. действует принцип «последним пришёл – первым вышёл» (LIFO – Last In First Out).

Основные операции над стеком:

• Занесение в стек (принято называть Push);

• Выборка из стека (принято называть Pop);

Дополнительные операции:

• Создание пустого стека (DoTop);

• Проверка, пуст ли стек (IsEmpty);

• Просмотр элемента в вершине стека без удаления (InTop);

• Перемена местами двух элементов в вершине стека (Swap).

Наши рекомендации