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

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

While P <> Nil do
If Info(P) = 4 then
If Q = Nil then
Pop(Lst)
FreeNode(P)
P = Lst
Else
DelAfter(Q, X)
EndIf
Else
Q = P
P = Ptr(P)
EndIf
EndWhile

Задача 2.
Дан упорядоченный по возрастанию Info — полей список. Необходимо вставить в этот список элемент со значением X, не нарушив упорядоченности списка.

Пусть X = 16. Начальное условие: Q = Nil, P = Lst. Вставка элемента должна произойти между 3 и 4 элементом (рис.3.10).
Q =Nil
P = Lst
While (P <> Nil) and (X > Info(P)) do
Q = P
P = Ptr(P)
EndWhile
if Q = Nil then
Push(Lst, X)
EndIf
InsAfter(Q, X)

Реализация примеров на языке Паскаль:

Задача 1:
Q:=nil;
P:=Lst;
While P <> nil do
If P^.Info = 4 then
begin
If Q = nil then
begin
Pop(Lst);
P:=Lst;
end
Else Delafter(Q,X);
End;
Else
begin
Q:=P;
P:=P^.Next;
end;
end;

Задача 2:
Q:=nil;
P:=Lst;
While (P <> nil) and (X > P^.Info) do
begin
Q:=P;
P:=P^.Next;
end;
{В эту точку производится вставка}
If Q = nil then Push(Lst, X);
InsAfter(Q, X);
End;

3.4.3  Элементы заголовков в списках
Для создания списка с заголовком в начало списка вводится дополнительный элемент, который может содержать информацию о списке (рис. 3.11).

В заголовок списка часто помещают динамическую переменную, содержащую количество элементов  в списке (не считая самого заголовка).
Если список пуст, то остается только заголовок списка (рис. 3.12).

Также удобно занести в информационное поле заголовка значение указателя конца списка. Тогда, если список используется как очередь, то Fr = Lst, а    Re = Info(Lst).
Информационное поле заголовка можно использовать для хранения рабочего указателя при просмотре списка P = Info(Lst). То есть заголовок — это дескриптор структуры данных.

3.5 Нелинейные связанные структуры

Двусвязный список может быть нелинейной структурой данных, если вторые указатели задают произвольный порядок следования элементов (рис.3.13).

LST1 — указатель на начало 1 — ого списка (ориентированного указателем P1). Он линейный и состоит из 5-и элементов.
2-ой список образован из этих же самых элементов, но в произвольной последовательности. Началом 2-ого списка является 3-ий элемент, а концом 2-ой элемент.
В общем случае элемент списочной структуры может содержать сколь угодно много указателей, то есть может указывать на любое количество элементов.
Можно выделить 3 признака отличия нелинейной структуры:
1)  Любой элемент структуры может ссылаться на любое число других элементов структуры, то есть может иметь любое число полей-указателей.
2)  На данный элемент структуры может ссылаться любое число других элементов этой структуры.
3)  Ссылки могут иметь вес, то есть подразумевается иерархия ссылок.
Представим, что имеется дискретная система, в графе состояния которой узлы — это состояния, а ребра — переходы из состояния в состояние (рис. 3.14).

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

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