Связное распределение памяти.

Все вышерассмотренные структуры, реализовавшиеся как отображение на массив, обладают определенными недостатками, т.е. они малоэффективны при решении некоторых задач. К таким недостаткам можно отнести следующее:

1. Определенно неизвестно, сколько элементов будет иметь данная структура, т.е. нельзя сделать оценку.

2. Если мы рассматриваем некую последовательность элементов в последовательной памяти x₁, x₂, …, x_n и необходимо включить какой-либо новый элемент x в эту последовательность, то мы должны осуществить массовую операцию сдвига всех элементов, находящихся за тем элементом последовательности, после которого мы хотим включить новый элемент. После вставим этот новый элемент x на освободившееся место. Таким образом, здесь проявляется свойство физической смежности.

X1

X2

Xn

X1

X2

Xn

X

X

Избавиться от физической смежности можно, если элементы будут иметь не только данные, но и указатели. В этом случае элементы могут быть хаотически разбросаны по ОП, а логическая последовательность будет обеспечиваться одним или несколькими указателями.

Сд типа линейный односвязный список.

Связный список – СД элементами которой являются записи, связанные друг с другом с помощью указателей, хранящихся в самих элементах.

Связный список
линейный			нелинейный
односвязный		двухсвязный	двухсвязный	многосвязный
циклический	нециклический

Простейшим связным списком является линейный односвязный список. Каждый элемент в этом списке состоит из различных по назначению полей: содержательного и поля-указателя. В поле-указателе находится адрес следующего элемента. Поле последнего указателя имеет указание на конец списка – признак nil.

Start

Ptr

Данные

указатель

Данные

указатель

Данные

Операции, определяющие структуру типа линейный односвязный список:

1. Инициализация.

2. Включить элемент за рабочий указатель списка.

3. Исключить элемент, находящийся за рабочим указателем списка.

4. Передвинуть рабочий указатель на один шаг.

5. Проверка: список пуст / список не пуст.

6. Поместить рабочий указатель в начало списка (производная операция).

7. Поместить рабочий указатель в конец списка (производная операция).

8. Сделать список пустым.

При инициализации списка эффективно использовать реализацию следующей структуры:

Start

Ptr

Фиктивный элемент

Реализацию списка можно осуществить с помощью отображения на массив.

Рассмотрим операции включения и исключения элементов в общем случае. Введем следующие обозначения полей: Data – поле, куда записываются данные; Link – поле, где находится указатель на следующий элемент списка; Start – указатель на начало списка; Free – указатель указывающий на первый элемент свободного (рабочего) списка.

Для реализации необходимо иметь функциональный список, в котором находится поле данных, а также свободный список, являющийся источником данных для функционального. Поле Data в свободном списке не имеет содержательной информации. Data (Ptr) указывает на поле Data того элемента, на который указывает Ptr. Link (Ptr) – указатель того элемента, на который указывает Ptr.

Операции включения и исключения от размерности списка не зависят.

Включение элемента в список:

1. Pntr = Free;

2. Free – Link(Pntr);

3. Data(Pntr) = { };

4. Link(Pntr) – Link(Ptr) {формируем указатель в новом элементе};

5. Link(Pntr) = Pntr {модификация указателя}.

Реализация списка в последовательной памяти.

В последовательной памяти список реализуется с помощью двух согласованных массивов, первый из которых используется для записи элементов, а второй – для записи указателей.

Например:

A B C D:	1	2 A	3 C	4 B	…...	N-1	N
L:	1	2 4	3 0	4 3	…...	N-1	N

D – массив, используемый для записи элементов, L – массив, используемый для записи указателей, 0 – указатель конца списка.

D:	1	2	3	4	…...	N-1	N
L:	1 1	2 3	3 4	4 5	…...	N-1 N	N 2

Будем считать, что: L [1] будет указывать на первый элемент функционального списка, L [2] – на первый элемент свободного списка.

После инициализации (приведения структуры в начальное состояние) функциональный список – пустой, и мы сделаем его циклическим, а свободный список будут занимать все остальные элементы (его также сделаем циклическим).

Кроме реализации списка в последовательной памяти, связный список можно реализовать также и в динамической памяти (с использованием указательного типа).