Структуры данных и модели вычислений
Списки с прямым доступом
Прямой доступ, как правило, реализуется при представлении списка массивом. Элементы кортежа размещаются в идущих подряд ячейках некоторого массива. Для локализации списка в массиве введем целочисленную переменную для хранения номера позиции массива, в которой расположен его первый элемент, и целочисленную переменную , означающую длину списка. Равенство служит признаком того, что массив содержит пустой список. Иногда для переменных, хранящих позицию элемента массива, удобно иметь какое-либо условное значение, выходящее за рамки индексации массива. Будем обозначать его .
Рассмотрим подробнее реализацию списка с прямым доступом, дающую возможность добавлять элементы к списку с любого его конца. Воспользуемся циклической "нумерацией" элементов массива, при которой следующим за последним элементом массива считается его первый элемент, а предыдущим для первого — последний (речь идет об элементах массива, а не об элементах списка). Если элементы массива пронумеровать числами от
до , то переход к следующему (предыдущему) элементу списка осуществляется с помощью прибавления (вычитания) единицы по модулю , где — длина массива. Дескриптор такого списка будет иметь форму
Добавление элемента к началу списка осуществляется его записью в позицию
с последующим присваиванием , а добавление в конец (записью элемента в позицию (
с последующим выполнением оператора . Заметим, что при таком способе начальный фрагмент кортежа может оказаться в конце массива, а конечный фрагмент — в начале. Заметим также, что добавление нового элемента возможно только при условии . Кроме того, нужно иметь в виду, что в системах программирования со статическим распределением памяти под массивы, которое происходит во время компиляции, длину массива следует выбирать достаточной для размещения списков, порождаемых разрабатываемым алгоритмом. Следует помнить, что максимальная длина списка зависит не только от алгоритма, но и от входных данных.
Основные отображения для списка с прямым доступом, имеющего дескриптор , определяются следующим образом:
Приведем несколько процедур для работы со списками с прямым доступом.
Создать пустой список
Добавить элемент к концу списка
Добавить элемент e к началу списка
Заменить элемент с кортежным номером
на элемент
Удалить последний элемент списка
Удалить первый элемент списка
