Понедельник, Июль 5th, 2010

Структуры и алгоритмы обработки данных

Просмотр односвязного списка может производиться только последовательно, начиная с головы (с начала) списка. Если необходимо просмотреть предыдущий элемент, то надо снова возвращаться к началу списка. Это — недостаток односвязных списков по сравнению со статическими структурами типа массива. Списковая структура проявляет свои достоинства, когда число элементов списка велико, а вставку или удаление необходимо произвести внутри списка.
Пример:
Необходимо вставить в существующий массив элемент X между 5 и 6 элементами.

Для проведения данной операции в массиве нужно “опустить” все элементы, начиная с X6 — увеличить их индексы на единицу. В результате вставки получаем следующий массив (рис. 3.7, 3.8):

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

3.4.1  Вставка и извлечение элементов  из  списка
Определяем элемент, после которого необходимо вставить элемент в список. Вставка производится с помощью процедуры InsAfter(Q, X), а удаление — DelAfter(Q, X).
При этом рабочий указатель P будет указывать на элемент, после которого необходимо произвести вставку или удаление (рис 29).

Пример:
Пусть необходимо вставить новый элемент с информационным полем X после элемента, на который указывает рабочий указатель P.
Для этого:
1) Необходимо сгенерировать новый элемент.
Q = GetNode
2) Информационному полю этого элемента присвоить значение X.
Info(Q) = X
3) Вставить полученный элемент.
Ptr(Q) = Ptr(P)
Ptr(P) = Q
Это и есть процедура InsAfter(Q, X).
Пусть необходимо удалить элемент списка, который следует после элемента, на который указывает рабочий указатель P.
Для этого:
1) Присваиваем Q значение указателя на удаляемый элемент.
Q = Ptr(P)
2) В переменную  X сохраняем значение информационного поля удаляемого элемента.
X = Info(Q)
3) Меняем значение указателя на удаляемый элемент на значение указателя на следующий элемент и производим удаление .
Ptr(P) = Ptr(Q)
FreeNode(Q)
Это и есть процедура DelAfter(P, X).

На языке Паскаль вышеописанные процедуры будут выглядеть следующим образом:
procedure InsAfter(var Q: PNode; X: Integer);
var
Q: PNode;
begin
New(Q);
Q^.Info:=X;
Q^.Next:=P^.Next;
P^.Next:=Q;
procedure DelAfter(var Q: PNode; var X: Integer);
var
Q: PNode;
begin
Q:=P^.Next;
P^.Next:=Q^.Next;
X:=Q^.Info;
Dispose(Q);
end;

3.4.2   Примеры типичных операций над списками
Задача 1.
Требуется просмотреть список и удалить элементы, у которых информационные поля равны 4.
Обозначим P — рабочий указатель, в начале процедуры P = Lst. Введем также указатель Q, который отстает на один элемент от P. Когда указатель P найдет элемент, последний будет удален относительно указателя Q как последующий элемент.
Q = Nil
P = Lst

Страницы: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84

Категория: Учебники