Лабораторная работа №4 Работа с линейным односвязным списком

Лабораторная работа №4

РАБОТА С ЛИНЕЙНЫМ ОДНОСВЯЗНЫМ СПИСКОМ

Как уже отмечалось, очередь и стек являются частными случаями общего понятия "линейный список".

Линейный односвязный список может быть двух разновидностей:

1)  прямой линейный односвязный список;

2)  обратный линейный односвязный список.

Очередь является частным случаем прямого линейного односвязного списка. В обратном списке связь устанавливается от i-го к (i-l)-мy элементу.

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

Для работы с линейным односвязным списком требуются такие указатели:

1)указатель на начало списка (возьмем идентификатор BegL);

2)указатель на конец списка (возьмем идентификатор EndL);

3)указатель на k-й элемент списка, где будут производиться действия: после которого (или перед которым) будет вставлен элемент или же который следует удалить (возьмем идентификатор Рk);

4) временный указатель для выделения памяти под добавляемые элементы и для освобождения памяти удаляемых элементов (возьмем идентификатор Р).

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

1. Создание линейных односвязных списков

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

2. Добавление элемента в конец списка

Добавление элемента в конец прямого списка выполняется аналогично добавлению элемента в конец очереди, а добавление элемента в конец обратного списка выполняется аналогично добавлению элемента в вершину стека.

Схема добавления для прямого линейного односвязного списка будет следующей:

3. Добавление элемента в начало списка

Добавление элемента в начало прямого списка выполняется аналогично добавлению элемента в вершину стека, а добавление элемента в начало обратного списка выполняется аналогично добавлению элемента в конец очереди.

Схема добавления элемента для прямого линейного односвязного списка будет следующей:

4. Вставка элемента в середину списка после заданного k-го элемента

Будем считать, что адрес k-го элемента уже известен и хранится в указателе Pk.

5. Вставка элемента в середину списка перед заданным k-м элементом

Естественно, если мы имеем адрес (k-l)-го элемента, то требуемое действие можно выполнить как показано выше. Но, если имеется адрес только k-го элемента, то задача усложняется. Такая ситуация может быть, например в случае, когда указатель устанавливается на k-й элемент, но действия над ним будут определяться дальнейшим ходом алгоритма, то есть предварительно не известно, что нужно будет делать с этим элементом (вставлять после, вставлять до, удалять его или же вообще ничего не делать). В этом случае вместо того, чтобы еще раз от начала списка искать (k-l)-й элемент, значительно лучше выполнить вставку перед k-м элементом следующим образом. Сначала описанным выше способом произвести вставку нового элемента после k-го элемента, затем поменять местами значения информационных полей k-го и нового элементов и, наконец, переставить указатель Pk на новый вставленный элемент, который уже содержит значение k-го элемента. То есть к приведенным выше трем этапам вставки элемента добавляется еще один, четвертый :

4.Обмен местами значений информационных полей k-го и нового элементов и перестановка указателя Pk на новый элемент.

Переменная Tmp должна иметь такой же тип, как и информационное поле элемента списка Inf.

6. Удаление элемента из начала списка

Удаление элемента из начала прямого списка выполняется аналогично удалению элемента из очереди и из стека (обратим внимание, что удаление элемента из очереди и стека выполняется, по сути, одинаково).

Удалению элемента из начала обратного списка (или из конца прямого списка) нет аналога среди действий с очередью и стеком (это будет рассмотрено в следующем подзаголовке).

Схема удаления элемента из начала прямого списка будет следующей:

3. Перестановка указателя начала списка BegL на следующий элемент, используя значение поля Link, которое хранится в первом элементе. После этого освобождается память начального элемента списка, используя дополнительный указатель Р:

7. Удаление элемента из конца списка

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

Схема удаления элемента из конца прямого списка будет следующей:

Обратим внимание, что если просто удалить последний элемент, на который указывает EndL, то разрушится целостность списка, так как мы не сможем пере­ставить EndL на предыдущий элемент, ввиду отсутствия его адреса в какой-либо переменной. Поэтому сначала нужно найти адрес этого предпоследнего элемента списка. Как это можно сделать будет описано в специальном подпункте ниже.

8. Удаление элемента, стоящего после заданного k-го элемента

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

9.Удаление k-го элемента списка

Удаление k-го элемента, конечно, можно выполнить так же, как и следующего за ним (k+1)-го (как описано выше), если мы будем иметь (или найдем) адрес (k-l)-го элемента списка. Однако так же, как и в случае вставки нового элемента перед k-м, можно обойтись и без дополнительного поиска. Для этого необходимо предварительно скопировать значение поля Inf «нужного» (k+1)-го элемента в поле Inf «ненужного» k-го и удалить (k+1)-й элемент вместо k-го.

Соответствующая схема имеет следующий вид:

10. Установка указателя на k-й элемент линейного односвязного списка

Невозможно установить указатель одним оператором непосредственно на какой-либо средний k-й элемент списка, поскольку имеются адреса только первого и последнего элементов.

Поэтому, чтобы выполнить требуемое действие, необходимо отсчитать k элементов от головы списка, последовательно передвигая вспомогательный указатель от элемента к элементу.

В результате получаем:

Итак, в простейшем случае цикл установки указателя на заданный k-й элемент будет иметь такой вид:

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

11. Установка указателя на предпоследний элемент прямого односвязного списка

Напомним, что выполнение такого действия необходимо для удаления последнего элемента прямого односвязного списка.

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

Передвижение по списку выполняется так же, как было рассмотрено выше. Отличие состоит только в условии окончания поиска. Вариантов такого условия может быть два.

Можно выполнять сравнение или с указателем EndL, или же со значением nil, которое также фиксирует конец списка.

Поскольку указатели EndL и P^.Link указывают на один и тот же элемент (т. е. содержат один и тот же адрес), то, следовательно, указатели EndL^.Link и P^.Link^.Link также содержат один и тот же адрес и указывают на nil.

Хотя использование указателя P^.Link^.Link немного более сложно для понимания, однако и более универсально, так как работает даже в случае, если бы у нас не было указателя конца списка EndL.

12. Печать элементов односвязного списка от начала к концу

Такой вариант вывода на печать элементов списка выполняется аналогично описанной выше установке указателя на предпоследний элемент с двумя отличиями:

1)передвижение рабочего указателя производится до последнего элемента;

13. Печать элементов односвязного списка от конца к началу

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

Рассмотрим решение с помощью рекурсии. Поскольку мы используем рекурсию, то действия должны быть оформлены в виде процедуры.

Задания:

1.  Из которого текста читаются поочередно все слова и подсчитывается частота их появления, т. е. составляется частотный словарь. Для этого нужно составить список слов, найденных в тексте. Каждое очередное слово ищется в списке. Если слово найдено, счетчик его частоты увеличивается, в противном случае слово добавляется к списку. Для простоты будем считать, что слова выделены из текста, закодированы целыми положительными числами и находятся во входном файле.

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

3.  Дан линейный однонаправленный список, в информационных полях которого расположены целые числа. Удалить из этого списка все элементы, имеющие четные значения таких полей, собрав их в отдельном линейном однонаправленном списке.