Задачи на замену элементов в линейном однонаправленном списке без головного элемента

Операция замены элемента в списке практически представляет собой комбинацию удаления и вставки элемента.

Читателю дается возможность, используя представленные ранее графические приемы и примеры программ, самому написать процедуры замены элементов.

Перед выполнением операции замены элемента желательно запрашивать у пользователя подтверждение замены.

Действуя аналогично, можно построить графические схемы и программы задач действий с двунаправленными списками.

Работа с головным элементом

Назначение головного элемента.

Головной элемент содержит основные характеристики списка – адрес первого элемента, адрес последнего элемента, текущее количество элементов списка. Это даёт возможность не создавать и не применять постоянно подпрограммы определения текущего количества элементов списка, поиска адреса последнего элемента списка. Особенно наличие головного элемента облегчает работу с симметричным списком. Кроме того, при работе со списком циклы WHILE … DO и REPEAT…UNTIL могут быть заменены циклами FOR.

Структура головного элемента (приведен минимальный набор полей, последовательность их расположения произвольна)

где:

- First – адрес первого элемента списка;

- Last - адрес последнего элемента списка;

- N - текущее количество элементов списка;

Описание и использование головного элеме hd : hd_el;нта

type

head_element=record

First : el; {адрес первого элемента списка }

last : el ; { адрес последнего элемента

списка }

{ el – адресный тип, связанный

с элементом списка }

n : integer; { текущее количество

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

end;

Var

hd : head_element;

Begin

…

hd.first := nil;

hd.last := nil;

hd.n := 0;

{ инициализация полей головного элемента }

{ состояние - список пуст}

…

{ дальше – действия с полями hd.first и hd.last –

как с переменными first и last }

if hd.first = nil

then { список пуст}

Begin

…

End

End.

Использование динамической памяти:

{ рекомендуемый вариант }

Type

head_element=record

First : el; {адрес первого элемента списка }

last : el ; { адрес последнего элемента

списка }

n : integer; { текущее количество

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

end;

head_el = ^ head_element;

Var

hd : head_el;

Begin

hd := nil; { состояние: список не существует }

…

new ( hd ); { выделение памяти под головной элемент }

hd^.first := nil;

hd^.last := nil;

hd^.n := 0;

{ инициализация полей головного элемента }

{ состояние - список существует, но ОН пуст}

…

{ дальше – действия с полями hd^.first и hd^.last –

как с переменными first и last }

…

{ ТИПИЧНОЕ НАЧАЛО РАБОТЫ СО СПИСКОМ, ИМЕЮЩИМ

инамический ГОЛОВНОЙ ЭЛЕМЕНТ : }

if hd = nil

then { список НЕ СУЩЕСТВУЕТ}

Begin

…

End

ELSE if hd^.first = nil

then { список СУЩЕСТВУЕТ, но пуст}

Begin

…

End

ELSE { список СУЩЕСТВУЕТ }

Begin

…

End

…

{ работа со списком}

…

dispose ( hd ); { освобождение памяти

От головного элемента.

Перед этим список должен

Быть уничтожен

с освобождением памяти}

…

End.

фрагмент программы:

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

В начало линейного однонаправленного списка

…

if hd = nil

then { список НЕ СУЩЕСТВУЕТ}

Begin

…

End

ELSE if hd^.first = nil

then { список пуст}

Begin

hd^.first:= p;

hd^.last := p;

hd^.n := 1;

End

else { список не пуст}

Begin

p^.next := hd^.first;

hd^.first := p;

hd^.n := hd^.n + 1;

end;

фрагмент программы:

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

В КОНЕЦ линейного однонаправленного списка

…

if hd = nil

then { список НЕ СУЩЕСТВУЕТ}

Begin

…

End

ELSE if hd^.first = nil

then { список пуст}

Begin

hd^.first:= p;

hd^.last := p;

hd^.n := 1;

End

else { список не пуст}

Begin

hd^.LAST := p;

p^.next := NIL;

hd^.n := hd^.n + 1;

end;

ПРОВЕРКА КОРРЕКТНОСТИ НОМЕРА

ОБРАБАТЫВАЕМОГО ЭЛЕМЕНТА СПИСКА

…

if ( I < 1 ) OR ( I > hd^. n )

Then begin

Writeln ( ' I = ' , I , ' ЗАДАНО НЕВЕРНО ' );

…

End

Стеки, деки, очереди.

Одной из важных концепций в программировании является концепция стека.

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

Бытовой иллюстрацией стека может служить стопка книг.

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

Просматривать книги можно только по одной, получая их из стека (снимая их с вершины). Чтобы получить книгу из середины стека, надо задать критерий поиска и удалять элементы-книги из стека до тех пор, пока не будет найдена нужная книга. Удаляемые элементы утрачиваются.

Иногда бывает полезно создать новый стек, куда помещаются элементы, удаляемые из исходного стека

Элементы из стека могут удаляться, пока он не станет пустым. Таким образом, над стеком выполняются следующие операции:

1) определение пуст ли стек;

2) добавление в стек нового элемента;

3) доступ к последнему включенному элементу, вершине стека;

4) исключение из стека последнего включенного элемента.

Принцип работы со стеком: «пришел последним - ушел первым» (last in - first out, LIFO).

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

Другим специальным видом использования списка являетсяочередь.

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

Поиск по сайту: