Непрерывная реализация структуры данных — такая реализация, в которой элементы структуры располагаются непосредственно друг за другом на непрерывном участке памяти (в массиве), причем порядок их расположения в памяти соответствует порядку в реализуемой структуре.
В ссылочной реализации элементы хранятся в произвольном порядке, а в каждом элементе хранится ссылка на один или два соседних элемента.
Недостаток непрерывной реализации в том, что при вставке или удалении элемента из структуры данных приходится перемещать большие объемы данных.
Недостаток ссылочной реализации в излишнем расходе памяти под хранение ссылок, а также в отсутствии прямого доступа к элементам структуры данных.
Идея реализации состоит в хранении элементов списка в одном векторе (векторе данных), а ссылок на следующий элемент — в другом векторе (векторе ссылок).
Для хранения индекса первого элемента списка будем использовать первый элемент вектора ссылок. Индекс первого элемента можно использовать в качестве ссылки на следующий элемент для последнего элемента списка.
Также нужно хранить информацию о свободных ячейках в векторе данных. Будем хранить эту информацию также в виде L1-списка, используя те же вектор данных и вектор ссылок. Индекс первого элемента в этом списке будем хранить во второй ячейке вектора ссылок.
Указатель на следующий элемент списка будем хранить в паре переменных «указатель.до» и «указатель.за». Первая содержит индекс предыдущего элемента списка (или нил списка, если указатель в начале списка), вторая — индекс элемента за указателем. Хранить индекс предыдущего элемента списка приходится для того, чтобы связывать предыдущий элемент с элементом за указателем в случае добавления или удаления элемента за указателем.
Исполнитель «Ограниченный Л1 список»
! Используемые исполнители:
! информация: вектор элементов типа Е с индексом 3..максинд
! следующий: вектор элементов типа индекс с индексом типа индекс
! Обозначения:
! Нил списка == 1 (индекс элемента вектора «следующий», указывающий на первый элемент списка)
! Нил свободного места == 2 (индекс в векторе «следующий», указ-й на первый элемент списка свободного места)
программа начать работу
информация.начать работу
следующий.начать работу
связать <нил списка, нил списка>
указатель := нил списка
цикл для каждого И из нил свободного места..максинд-1 выполнять
связать <И, И + 1>
конец цикла
связать <максинд, нил свободного места>
конец программы
программа сделать список пустым
установить указатель в начало списка
цикл пока список не пуст выполнять
удалить элемент списка за указателем
конец цикла
конец программы
программа список пуст: да/нет
ответ := (следующий(нил списка) == нил списка)
конец программы
программа передвинуть указатель списка вперед
указатель.до := указатель.за
указатель.за := следующий(указатель.за)
конец программы
программа добавить элемент <вх: Е> за указателем
захватить место <вых: И>
связать <указатель.до, И>
связать <И, указатель.за>
указатель.за := И
информация := Е
конец программы
программа взять элемент списка за указателем в <вых: Е>
Е := элемент списка за указателем
удалить элемент списка за указателем
конец программы
программа элемент списка за указателем: Е
ответ := информация(указатель.за)
конец программы
программа удалить элемент списка за указателем
И := указатель.за
указатель.за = следующий(И)
связать <указатель.до, указатель.за>
освободить место <вх: И>
конец программы
программа связать <вх: И1, И2: индекс>
следующий(И1) := И2
конец программы
программа захватить место <вых: И: индекс>
И := следующий(нил свободного места)
связать <нил свободного места, следующий(И)>
конец программы
программа освободить место <вх: И: индекс>
связать <И, следующий(нил свободного места)>
связать <нил свободного места, И>
конец программы
программа кончить работу
информация.кончить работу
следующий.кончить работу
конец программы
конец исполнителя
Класс L2ListHeader реализует ссылки элементов списка на предыдущий и следующий элемент списка. Метод link() реализует привязку элемента в список за данным элементом.
class L2ListHeader {
L2ListHeader *next;
L2ListHeader *next;
…
void link(L2ListHeader *h) {
next = h;
h→prev = this;
}
};
Предполагается, что элементы L2-списка — это объекты класса, выведенного из L2ListHeader.
Класс L2List реализует L2-список:
class L2List {
L2ListHeader headList;
L2ListHeader* pointer;
…
void moveForward(); // Передвинуть указатель списка вперед
void moveBack(); // Передвинуть указатель списка назад
L2ListHeader& elementAfter(); // Элемент списка за указателем
L2ListHeader& elementBefore(); // Элемент списка до указателя
void addBefore(L2ListHeader *); // Добавить элемент до указателя
void removeBefore(); // Удалить элемент до указателя
void addAfter(L2ListHeader*); // Добавить элемент за указателем
void removeAfter(); // Удалить элемент за указателем
};
Член класса headList содержит ссылки на первый элемент списка (в next) и на последний элемент списка (в prev). Если эти ссылки равны 0, это означает, что список пуст.
Член класса pointer реализует указатель списка: поле next содержит ссылку на элемент за указателем, а prev – ссылку на элемент списка до указателя.
Для добавления элемента в список надо создать этот элемент (оператором new) и вызвать метод addBefore() или addAfter() для добавления его до указателя или за указателем соответственно.
При удалении элемента в методах removeAfter() или removeBefore() захваченная для него память высвобождается автоматически (то есть в этих методах для него вызывается оператор delete).
Работа со структурами данных часто требует применения какой-либо операции ко всем элементам структуры. Для этого используются итераторы.
Итераторы — это объекты с интерфейсом указателей на элементы структуры данных. Итератор можно установить на первый элемент структуры данных, сдвигать на следующий и проверять, не находится ли итератор в конце структуры данных, то есть за последним элементом.
В реализации структуры данных как C++ класса итераторы реализуются как класс внутри этого класса, с переопределенными операторами «*» и «++». Оператор * используется для доступа через итератор к элементу структуры, на который указывает итератор. Оператор ++ используется для сдвига итератора на следующий элемент структуры данных.
Также в классе, реализующем структуру данных, должны присутствовать методы begin() и end(), возвращающие положение итератора соответственно в начале структуры данных и в конце структуры данных (то есть за последним элементом).
Пример 1. Класс L2List включает в себя класс iterator, а также методы begin() и end():
class L2List {
…
class iterator {
…
iterator& operator++();
L2ListHeader& operator*() const;
};
iterator begin();
iterator end();
};
Для прохода по всем элементам структуры данных итератор устанавливается в начало структуры данных, а затем сдвигается вперед до тех пор, пока не достигнет конца структуры данных.
Пример 2. Проход итератором по элементам объекта класса L2List с извлечением содержимого элементов:
L2List list;
L2List::iterator i;
for (I = list.begin(); i != list.end(); i++) {
L2ListHeader h = (*i);
...
}
1. Кушниренко А.Г., Лебедев Г.В. Программирование для математиков: Учеб. пособие для вузов — М.: Наука. Гл.ред.физ.-мат.лит., 1988