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

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

В программировании двусвязные списки часто обобщают следующим образом: в качестве значения поля Rptr последнего звена принимают ссылку на заглавное звено, а в качестве значения поля Lptr заглавного звена- ссылку на последнее звено. Список замыкается в своеобразное кольцо: двигаясь по ссылкам, можно от последнего звена переходить к заглавному и наоборот.

Операции над двусвязными списками:
— cоздание элемента списка;
— поиск элемента в списке;
— вставка элемента в указанное место списка;
— удаление из списка заданного элемента.

3.2  Реализация  стеков  с  помощью   односвязных  списков

Любой односвязный список может рассматриваться в виде стека. Однако список по сравнению со стеком в виде одномерного массива имеет преимущество, так как заранее не задан его размер.

Стековые операции, применимые к спискам
1). Чтобы добавить элемент в стек, надо в алгоритме заменить указатель Lst на указатель Stack (операция Push(S, X)).

P = GetNode
Info(P) = X
Ptr(P) = Stack
Stack = P

2) Проверка стека на пустоту (Empty(S))

If Stack = Nil then Print “Стек пуст”
Stop

3) Выборка элемента из стека (POP(S))

P = Stack
X = Info(P)
Stack = Ptr(P)
FreeNode(P)

Реализация на Паскале:
Стек

Вместо указателя Lst используется указатель Stack
Процедура Push (S, X)

procedure Push(var Stack: PNode; X: Integer);
var
P: PNode;
begin
New(P);
P^.Info:=X;
P^.Next:=Stack;
Stack:=P;
end;

Проверка на пустоту (Empty)

function Empty(Stack: PNode): Boolean;
begin
If Stack = nil then Empty:=True Else Empty:=False;
end;

Процедура Pop

procedure Pop(var X: Integer; var Stack: PNode);
var
P: PNode;
begin
P:=Stack;
X:=P^.Info;
Stack:=P^.Next;
Dispose(P);
end;

Операции с очередью, применимые к спискам.

Указатель начала списка принимаем за указатель начала очереди F, а указатель R, указывающий на последний элемент списка — за указатель конца очереди.
1) Операция удаления из очереди (Remove(Q, X)).
Операция удаления из очереди должна проходить из ее начала.
P = F
F = Ptr(P)
X = Info(P)
FreeNode(P)
2) Проверка очереди на пустоту. (Empty(Q))
If F = Nil then Print “Очередь пуста”
Stop
3) Операция вставки в очередь. (Insert(Q, X))
Операция вставки в очередь должна осуществляться к ее концу.
P = GetNode
Info(P) = X
Ptr(P) = Nil
Ptr(R)= P
R = P

Реализация на Паскале:
procedure Remove(var X: Integer; Fr: PNode);
var
P: PNode;
begin
New(P);
P:=Fr;
X:=P^.Info;
Fr:=P^.Next;
Dispose(P);
end;

function Empty(Fr: PNode): Boolean;
begin
If Fr = nil then Empty:=True Else Empty:=False;
end;

procedure Insert(X: Insert; var Re: PNode);
var
P: PNode;
begin
New(P);
P^.Info:=X;
P^.Next:=nil;
Re^.Next:=P;
end;

3.3 Организация операций  Getnode, Freenode и утилизация освободившихся элементов

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

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