Динамические структуры характеризуются непостоянством и непредсказуемостью размера (числа элементов) структуры в процессе ее обработки, отсутствием физической смежности элементов структуры в памяти. Часто динамические структуры представляются в виде связных списков.
Связный список – структура, элементы которой имеют один и тот же формат и связаны друг с другом с помощью указателей, хранящихся в самих элементах.
В односвязном списке каждый элемент состоит из двух различных по назначению полей: содержательного поля (поле данных) и служебного поля (поля указателя), где хранится адрес следующего элемента списка (рис.1). Поле указателя последнего элемента списка содержит нулевой указатель, свидетельствующий о конце списка.
Рис.1. Односвязный список. Логическая структура.
Линейность односвязного списка вытекает из линейной логической упорядоченности его элементов: для каждого элемента, за исключением первого и последнего, имеются единственный предыдущий и единственный последующий элементы. Односвязные списки всегда линейны, поэтому особое внимание следует уделить проблеме перестройки списка при его повреждении.
Логическая структура линейного односвязного списка:
Имя списка (идентификатор), тип элементов списка, указатель начала списка, указатель текущего элемента списка.
Логическая структура элемента линейного односвязного списка:
Данные или указатель на данные, указатель на следующий элемент списка.
Основные операции над линейным односвязным списком:
- перемещение по списку;
- включение элемента в линейный односвязный список (рис.2);
- исключение элемента из линейного односвязного списка (рис.3);
- извлечение содержательного поля любого элемента;
- изменение содержательного поля любого элемента;
- подсчет количества элементов списка;
- слияние линейных односвязных списков (частный случай операции включения линейного односвязного списка);
- выделение линейного односвязного подсписка.
Продвижение в линейном односвязном списке возможно только в одном направлении. Результаты выполнения операций включения элемента в линейный односвязный список и исключения элемента из линейного односвязного списка – линейный односвязный список.
Рис.2. Выполнение операции включения элемента в линейный односвязный список.
Рис.3.
Выполнение операции исключения элемента из линейного односвязного
списка.
Физическая структура линейного односвязного списка:
Физическая структура линейного односвязного списка состоит из дескриптора списка и одинаковых по размеру и формату записей (рис.4), размещенных произвольно в памяти компьютера и связанных друг с другом в линейно упорядоченную цепочку с помощью указателей.
Рис.4. Линейный односвязный список. Физическая структура.
Для ускорения операции доступа к элементам односвязного списка поле указателя последнего элемента односвязного списка содержит указатель на начало списка. Такая разновидность линейного односвязного списка называется кольцевой односвязный список (рис.5), причем первым элементом такого списка может быть любой из его элементов.
Рис.5. Кольцевой односвязный список. Логическая структура.
В линейном двусвязном списке продвижение возможно в любом из двух направлений по цепочке элементов. Каждый элемент двусвязного списка содержит два указателя: указатель на следующий элемент, или прямой указатель, и указатель на предыдущий элемент, или обратный указатель (рис.6). У первого элемента двусвязного списка обратный указатель пустой, а у последнего элемента двусвязного списка – прямой указатель.
Рис.6. Линейный двусвязный список. Логическая структура.
Линейность такого списка обеспечивается тем, что каждый из двух указателей в любом элементе списка, кроме крайних, задает линейный порядок элементов, обратный по отношению к порядку, устанавливаемому другим указателем (рис.7).
Рис.7. Линейность двусвязного списка.
Логическая структура линейного двусвязного списка:
Имя списка (идентификатор), тип элементов списка, указатель начала списка, указатель конца списка, указатель текущего элемента списка.
Логическая структура элемента линейного двусвязного списка:
Данные или указатель на данные, указатель на следующий элемент списка, указатель на предыдущий элемент списка.
Основные операции над линейным двусвязным списком:
- перемещение по списку;
- включение элемента в линейный двусвязный список;
- исключение элемента из линейного двусвязного списка;
- извлечение содержательного поля любого элемента;
- изменение содержательного поля любого элемента;
- подсчет количества элементов списка;
- слияние линейных двусвязных списков (частный случай операции включения линейного двусвязного списка);
- выделение линейного двусвязного подсписка.
Продвижение в линейном двусвязном списке возможно в любом направлении. Операции включения элемента в линейный двусвязный список и исключения элемента из линейного двусвязного списка реализуются аналогично соответствующим операциям над линейным односвязным списком. Результат выполнения операций включения элемента в линейный двусвязный список и исключения элемента из линейного двусвязного списка – линейный двусвязный список.
Физическая структура линейного двусвязного списка:
Физическая структура линейного двусвязного списка состоит из дескриптора списка и одинаковых по размеру и формату записей (рис.8), размещенных произвольно в памяти компьютера и связанных друг с другом с помощью указателей.
Рис.8. Линейный двусвязный список. Физическая структура.
Для получения из линейного двусвязного списка кольцевого двусвязного списка необходимо два пустых указателя заменить указателями противоположных концов списка (рис.9).
Рис.9. Кольцевой двусвязный список. Логическая структура.
