Использование ссылочных данных

Списки

Лекция 15. Создание списков

Мы будем под списком понимать связанный список. Термин "список" в программировании может означать также линейный список - конечную последовательность элементов.

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

Рис. 15.1. Составные части списка

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

В виде списка можно хранить разнообразную информацию. Например, на рис. 15.2. показан список, содержащий в качестве информации идентификаторы (длиной до 8 символов).

TEXT

SIMV

SL

A1

Указатель

списка

Рис. 15.2. Пример списка идентификаторов

К элементам списка возможен только последовательный доступ с помощью указателя списка, ссылающегося на его первый элемент. Чтобы обработать, например, десятый элемент, требуется просмотреть предыдущие девять элементов. Другим недостатком списка является затрата памяти для указателей.

На рис. 14.3 показано представление в памяти списка, показанного на рис. 14.2. Элемент списка занимает 10 байтов (8 байтов выделяется под поле идентификатора, 2 байта – под указатель на следующий элемент).

Адрес Память

...
SL
TEXT
SIMV
A1
...

...

Указатель списка

...

Рис. 15.3. Пример расположения списка в памяти

Основное достоинство списка - возможность размещать его элементы в памяти в любом порядке и не обязательно подряд. Это позволяет легко добавлять и удалять элементы в любом месте списка без физического перемещения данных только за счет изменения значений указателей.

На рис. 15.4 показан список после включения в него элемента, содержащего идентификатор “COUNT”, на рис. 15.5 - представление этого списка в памяти.

TEXT

SIMV

SL

A1

Указатель

COUNT COUNT

списка

новый элемент

Рис. 15.4. Включение нового элемента в список после элемента с идентификатором A1

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

1) в свободном месте памяти создается новый элемент;

2) в новый элемент из предшествующего ему элемента переносится ссылка на следующий за ним в списке элемент;

3) в предшествующий элемент помещается ссылка на новый элемент.

Чтобы удалить элемент из списка, достаточно изменить ссылку у предшествующего элемента: перенести ссылку из удаляемого элемента в предшествующий. Если удаляется первый элемент, то изменить нужно указатель списка: присвоить ему адрес второго элемента (из поля ссылки первого). Кроме того, необходимо еще освободить память, занимаемую исключенным из списка элементом.

Адрес Память

...
SL
COUNT
TEXT
SIMV
A1	2030
...

...

Указатель списка

...

Рис. 15.5. Пример включения элемента COUNT в список в памяти

Существуют несколько разновидностей списков. В двунаправленном списке каждый элемент содержит ссылку не только на следующий, но и на предыдущий элемент (рис. 15.6).

Рис. 15.6. Двунаправленный (симметричный) список

В циклическом списке последний элемент содержит ссылку на первый элемент списка (рис. 15.7).

Рис. 15.7. Циклический (кольцевой) список

В списковой структуре значениями элементов являются указатели списков (рис. 15.8). Списковая структура может иметь сложное разветвленное строение.

Рис. 15.8. Списковая структура (список списков)

Списки удобны в следующих случаях.

1. Для хранения динамических структур данных, строение и размеры которых меняются во время выполнения программы: создаются и уничтожаются структуры данных, добавляются и удаляются элементы и т.п.

2. Для упорядочивания данных без их физического перемещения в памяти. При этом элементы данных могут входить одновременно в разные списки, что позволяет упорядочить одни и те же данные несколькими разными способами, "прошивая" их несколькими списками.

Для организации списков требуются языковые средства описания данных, состоящих из разнотипных полей (структуры, записи), и ссылочный (адресный) тип данных.

При отсутствии в языке специальных средств, списки можно организовать с помощью параллельных массивов. В этом случае роль указателя играет индекс. Такие средства есть в любом языке высокого уровня, в том числе в языке C.

Для примера предположим, что значением элемента списка является идентификатор длиной до 8 символов (рис. 15.2).

Организацию таких списков обеспечивают, например, описания на языке C из примера 15.1.

Пример 15.1. Описание данных для списков с использованием ссылочных данных.

struct el_sp /* Тип элемента списка */

{ char id[8]; /* Значение элемента (идентификатор) */

struct el_sp *uk; /* Указатель следующего элемента */

};

struct el_sp *p; /* Указатель списка */

struct el_sp *i, *j; /* Указатели элементов списка */

char nov_id; /* Новый идентификатор */

Вместо el_sp, id, uk, p и т. д. можно использовать и другие имена.

Эти описания позволяют использовать в программе обозначения, показанные в таблице 15.1.

Таблица 15.1.

Пример обозначений для списков

Обозначения	Обозначаемые величины
Ссылочные данные	Параллельные массивы
NULL	NOL	Пустой указатель
i, j, p	i, j, p	Указатели элементов (ссылки на элементы)
*i	-	Элемент, на который указывает i
(*i).id i->id	id[i]	Значение (поле id) элемента *i
(*i).uk i->uk	uk[i]	Ссылка на преемник элемента *i (адрес элемента, следующего в списке за *i)
i->uk->id	id[uk[i]]	Значение преемника элемента *i
i->uk->uk	uk[uk[i]]	Ссылка на преемник преемника элемента *i