Моделирование списков с последовательным доступом при помощи массивов

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

В одних и тех же массивах и

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

На табл. 2.1 показано возможное заполнение массивов и

для одностороннего списка, представляющего кортеж

(пустые клетки не имеют отношения к этому списку).

Таблица 2.1. Моделирование одностороннего списка при помощи массива

Доступ к списку можно осуществить через его первый элемент, позиция которого в массиве задается значением переменной . Значение говорит о том, что в позиции

расположен элемент, у которого нет преемника, то есть последний элемент кортежа.

На табл. 2.2 показано возможное заполнение массивов , и для представления кортежа () двусторонним списком.

Таблица 2.2. Моделирование двустороннего списка при помощи массивов

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

Чтобы одни и те же массивы , ,

использовать для одновременного хранения нескольких однотипных списков, позиции этих массивов объединяют в один так называемый свободный список . Это можно сделать, например, с помощью операторов

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

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

можно задействовать малоразрядные представления чисел.

Содержание  Назад  Вперед

---

---