Работа с линейным односвязным списком
 |
Как уже отмечалось, очередь и стек являются частными случаями общего понятия "линейный список".
В списке, в отличие от очереди и стека, разрешено производить действия над любыми элементами, а не только крайними: менять местами элементы, удалять любой элемент, вставлять элемент в любую точку списка.
Линейный односвязный список может быть двух разновидностей:
1) прямой линейный односвязный список;
2) обратный линейный односвязный список.
Очередь является частным случаем прямого линейного односвязного списка.
Стек является частным случает обратного линейного односвязного списка.
Нетрудно заметить, что разделение на прямой и обратный список, является чисто условным и зависит от того, какую стоpону списка считать началом, а какую - концом.
Для работы с линейным односвязным списком требуются такие указатели:
1.Указатель на начало списка (возьмем идентификатор begp );
2. Указатель на конец списка (возьмем идентификатор endp );
3. Указатель на k-й элемент списка, где будут производиться действия: после которого (или перед которыми) будет вставлен элемент или же который следует удалить (возьмем идентификатор pk);
4. Временный указатель для выделения памяти под добавляемые элементы и для освобождения памяти удаляемых элементов (возьмем идентификатор Р).
Рассмотрим основные операции над линейными односвязными списками.
Создание линейных односвязных списков
Создание (т.е. внесение первого элемента) линейного односвязного списка выполняется точно так же, как и создание очереди. Причем это касается как прямого, так и обратного линейного односвязного списка, невзирая на то, что обратный линейный односвязный список является обобщенным случаем стека, а не очереди. Так получается именно из-за того, что обратный линейный односвязный список - это обобщенный вид стека, у которого есть начало и конец, как у очереди, а не только вершина, как у стека.
Поскольку, как уже отмечалось выше, разделение линейных односвязных списков на прямые и обратные является достаточно условным, все действия будем рассматривать на примере прямого линейного односвязного списка.
1.Исходное состояние:
begp:=nil;
endp:=nil;
2.Выделение памяти под первый элемент очереди:
new(p);
3.Занесение информации в первый элемент очереди:
p^.inf:=x;
p^.link:=nil
4.Установка указателей begp и endp на созданный первый элемент:
begp:=p;
endp:=p;
Добавление элемента в конец списка
Добавление элемента в конец прямого списка выполняется аналогично добавлению элемента в конец очереди, а добавление элемента в конец обратного списка выполняется аналогично добавлению элемента в вершину стека.
Схема добавления для прямого линейного односвязного списка будет следующей:
1.Исходное состояние.
2.Выделение памяти под новый элемент и занесение в него информации:
new(p);
p^.inf:=x;
p^.link:=nil;
3.Установка связи между последним элементом очереди и новым, а также перемещение указателя конца очереди endp на новый элемент:
endp^.link:=p;
endp:=p;
Добавление элемента в начало списка
Добавление элемента в начало прямого списка выполняется аналогично добавлению элемента в вершину стека, а добавление элемента в начало обратного списка выполняется аналогично добавлению элемента в конец очереди.
Схема добавления элемента для прямого линейного односвязного списка будет следующей:
1. Исходное состояние.
2. Выделение памяти под новый элемент стека:
new(p);
3. Внесение значения в информационное поле нового элемента и установка связи между ним и "старой" вершиной стека begp:
p^.inf:=x;
p^.link:=begp;
4. Перемещение вершины стека begp на новый элемент:
begp:=p;
Вставка элемента в середину списка после заданного k-го элемента
Будем считать, что адрес k-го элемента уже известен и хранится в указателе pk.
1.Исходное состояние.
2. Выделение памяти под новый элемент и занесение в него информации.
new(p);
p^.inf:=x;
3. Установка связи между новым и следующим элементом ,а также перестановка связи pk элемента на новый элемент p.
p^.link:=pk^.link;
pk^.link:=p;
Вставка элемента в середину списка перед заданным (k-1) элементом
Удаление элемента из начала списка
Удаление элемента из начала прямого списка выполняется аналогично удалению элемента из очереди и из стека (обратим внимание, что удаление элемента из очереди и стека выполняется по сути одинаково).
Удалению элемента из начала обратного списка (или из конца прямого списка) нет аналога среди действий с очередью и стеком (это будет рассмотрено в следующем подзаголовке).
Схема удаления элемента из начала прямого списка будет следующей:
1. Исходное состояние.
2. Извлечение информации из удаляемого элемента в переменную x и установке на него вспомогательного указателя Р:
x:=begp^.inf;
p:=begp;
3. Перестановка указателя начала списка begp на следующий элемент, используя значение поля p^.link, которое хранится в первом элементе. После этого освобождается память начального элемента списка, используя дополнительный указатель Р:
begp:=p^.link;
dispose(p);
Удаление элемента из конца списка
Удаление элемента из конца прямого списка не имеет аналогов среди действий с очередью и стеком, а удаление элемента из конца обратного списка выполняется аналогично удалению из очереди или из стека, как показано выше.
Схема удаления элемента из конца прямого списка будет следующей:
1. Исходное состояние.
Обратим внимание, что если просто удалить последний элемент, на который указывает endp то разрушится целостность списка, так как мы не сможем переставить endp на предыдущий элемент, ввиду отсутствия его адреса в какой-либо переменной. Поэтому сначала нужно найти адрес этого предпоследнего элемента списка. Как это можно сделать будет описано в специальном подпункте ниже.
2.Нахождение адреса предпоследнего элемента и занесение его в указатель Р.
3. Извлечение информации из последнего элемента в переменную x и освобождение его памяти.
x:=endp^.inf;
dispose(p);
4. Установка указателя конца списка endp на предпоследний элемент (теперь уже последний) и установка связи этого элемента в nil (то есть фиксация конца списка).
endp:=p;
endp^.link:=nil;
Удаление элемента, стоящего после заданного pk элемента
Такое действие можно выполнить без предварительного поиска, так как доступ ко всем адресам, необходимым для перестановки связей можно получить с помощью поля link k и (k+1) элементов.
1. Исходное состояние.
2. Установка дополнительного указателя Р на удаляемый элемент списка и извлечение из него информации.
p:=pk^.link;
x:=p^.inf;
3. Установка связи между k и (k+2) элементами и освобождение памяти удаляемого (k+1) элемента.
pk^.link:=p^.link;
dispose(p);
Установка указателя на k- элемент линейного односвязного списка
Невозможно установить указатель одним оператором непосредственно на какой-либо средний k- элемент списка, поскольку имеются адреса только первого и последнего элементов.
Поэтому, чтобы выполнить требуемое действие, необходимо пропустить некоторое количество элементов от головы списка (в соответствии с критерием поиска), последовательно передвигая вспомогательный указатель от элемента к элементу.
p:=begp;
while (p^.inf>0) and (p^.link<>nil) do
p:=p^.link;
Установка указателя на предпоследний
элемент прямого односвязного списка
p:=begp;
while p^.link^.link<>nil do
p:=p^.link;