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

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

Надо вставить в начало односвязного списка элемент с информационным полем D. Для этого необходимо сгенерировать пустой элемент (P=GetNode). Информационному полю этого элемента присвоить значение D (INFO(P)=D), значению указателя на этот элемент присвоить значение указателя на начало списка (Ptr(P) = Lst), значению указателя начала списка присвоить значение указателя P (Lst = P).
Реализация на Паскале:
type
PNode = ^TNode;
TNode = record
Info: Integer;  {тип элементов списка — может быть любым}
Next: PNode;
end;
var
Lst: PNode;  {указатель на начало списка}
P: PNode;
Вставка в начало
New(P);   {создание нового элемента}
P^.Info:=D;
P^.Next:=Lst; {P указывает на начало списка, но Lst не указывает на   P — новое начало}
Lst:=P;  {Lst указывает на новое начало списка}

2) Удаление элемента из начала односвязного списка.
Надо удалить первый элемент списка, но запомнить информацию, содержащуюся в поле Info этого элемента. Для этого введем указатель P, который будет указывать на удаляемый элемент (P = Lst). В переменную X занесем значение информационного поля Info удаляемого элемента (X=Info(P)). Значению указателя на начало списка присвоим значение указателя следующего за удаляемым элемента (Lst = Ptr(P)). Удалим элемент (FreeNode(P)).
Реализация на Паскале:
Удаление из начала
P:=Lst;
X:=P^.Info;
Lst:=P^.Next;
Dispose(P);       {Удаляет элемент из динамической памяти}

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

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

Страницы: 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

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