Списочные структуры

Статическая реализация графов. Проблема фрагментации памяти.

До сих пор в реализации абстрактных типов мы старались жёстко зафиксировать некоторую нумерацию компонентов этого типа, связав её с естественной нумерацией самого массива. Такой подход не позволяет эффективно реализовать характерные для динамических типов операции вставки и удаления компонентов. Это хронический дефект массивов даже в их основной роли – хранение последовательностей.

Упражнение. Написать процедуры вставки и удаления символа и слова в тексте.

Дилемма: Либо тратить на не имеющие логического смысла технические сдвиги – дефрагментацию памяти, либо мириться с дырками фрагментированной памяти.

Начальная идея проста – ставить новые компоненты не в конец или начало памяти (массива), а на первое попавшее свободное место.

a5

a4

a1

a2

a3

a6

Проблема. Теперь порядок компонентов-хранителей последовательности не будет совпадать с естественным порядком, следовательно, его нужно запоминать отдельно. Самый популярный способ сделать это – использовать списковую структуру, в которой вместе с каждым значением компоненты (члена последовательности) хранится индекс (указатель – имя) – следующая компонента.

1 2 3 4 5 6 7 8

‘а’

‘н’

‘б’

‘а’

‘н’

2 7 1 8 Æ

5 – индекс 1-й буквы

Æ - специальное значение – признак конца списка.

Второй вариант – функция предшествования. Получаем понятия прямого, обратного и двукратного списков.

succ succ

последовательность одна, но автоматы разные.

pred pred

Общая схема реализации автомата как списка.

Атрибуты вершин графа.

На каждую стрелку отдельное поле, хранящее указатель на вершину, к которой ведёт эта стрелка.

Светофор

1 2 3 4 5 6 7 8

К

З

Ж

5 7 3

7 5

type tIndex=1..nMax;

tList=record

content:array[tIndex] of tNode;

head:tIndex;

end;

tNode=record

info:tInfo; {Атрибуты вершины}

next:tIndex;

end;

tGraphNode=record

info:tInfo[tIndex] of tNode;

left,right:tIndex;

end;

Варианты – перечень полей-указателей. Например, для бинарного дерева – left,right:tIndex. Либо массив-указатель, либо список.

Новый способ требует больше памяти. Окупится ли «жертва» эффективной вставки и удаления? Убедимся в этом (оставим на время проблемы, связанные с обработкой кучи).

Задача. Включить в список List компоненту x после компоненты.

procedure Include(var List:tList;x:tInfo;AfterPtr:tIndex);

var NewPtr:tIndex;

begin

{Взять первый свободный индекс NewPtr из кучи}

GetHeap(List,NewPtr); After NewPtr

with List do ¯ ¯

ai

x

begin

content[NewPtr].next:=content[AfterPtr].next;

content[AfterPtr].next:=NewPtr;

content[NewPtr].info:=x;

end;

end;

Замечание: процедура Include корректно работает, если известна ссылка на предыдущую компоненту, после которой надо вставлять.

Техническая проблема: она не может включать в пустой список. Не хочется писать отдельную процедуру для включения в пустой список. Проверять же непустоту списка в процедуре Include неэффективно.

Решение: расширить тип Index до 0..nMax и при инициализации списка поставить в него фиктивную нулевую компоненту («болванчик» или «фантом»).

procedure Init(List:tList);

begin

with list do

begin

content[0].next:=0;

head:=0;

end;

{Инициализировать кучу}

end;

{Удаление элемента из списка, стоящего после компоненты AfterPtr}

procedure Exclude(var list:tList;AfterPtr:tIndex);

AfterPtr

¯ j

a_i+2

a_i+1   j₂

a_i

a_i   j₁

­ (удаление)

{Работает в предположении, что удалённая компонента существует}

var ThisPtr:tIndex;

begin

with list do

begin

ThisPtr:=content[AfterPtr].next;

content[AfterPtr].next:=content[ThisPtr].next;

{Сборка мусора – возвратить освободившуюся компоненту в кучу}

PutHeap(List,ThisPtr);

end;

end;

Дата добавления: 2014-01-05