Реализация динамических структур массивами в С++
Операции выделения и освобождения памяти — дорогое удовольствие, по-этому если максимальный размер данных можно определить до начала ис-пользования и в процессе работы он не изменяется (например, при сортировке содержимого файла), более эффективным может оказаться однократное выделение непрерывной области памяти. Связи элементов при этом реализуются не через указатели, а через вспомогательные переменные или массивы, в которых хранятся номера элементов.
Проще всего реализовать таким образом стек. Кроме массива элементов, соответствующих типу данных стека, достаточно иметь одну переменную целого типа для хранения индекса элемента массива, являющегося вершиной стека. При помещении в стек индекс увеличивается на единицу, а при выборке — уменьшается. Для реализации очереди требуются две переменных целого типа — для хранения индекса элементов массива, являющихся началом и концом очереди.
Для реализации линейного списка требуется вспомогательный массив целых чисел и еще одна переменная, например:
Отрицательное число используется как признак конца списка. Тот же массив после сортировки:
Для создания бинарного дерева можно использовать два вспомогательных массива (индексы вершин его правого и левого поддерева). Отрицательное число используется как признак пустой ссылки. Память под такие структуры можно выделить либо на этапе компиляции, если размер можно задать константой, либо во время выполнения программы, например:
Важно. При работе с подобными структурами необходимо контролировать возможный выход индексов за границу массива.
Приведенный способ реализации позволяет использовать преимущества динамических структур (например, сортировать структуры из громоздких эле-ментов данных без их физического перемещения в памяти), и при этом не расходовать время на выделение и освобождение памяти для каждого эле-мента данных.
Проще всего реализовать таким образом стек. Кроме массива элементов, соответствующих типу данных стека, достаточно иметь одну переменную целого типа для хранения индекса элемента массива, являющегося вершиной стека. При помещении в стек индекс увеличивается на единицу, а при выборке — уменьшается. Для реализации очереди требуются две переменных целого типа — для хранения индекса элементов массива, являющихся началом и концом очереди.
Для реализации линейного списка требуется вспомогательный массив целых чисел и еще одна переменная, например:
10 25 20 6 21 8 1 30 - массив данных 1 2 3 4 5 6 7 - 1 - вспомогательный массив0 - индекс первого элемента в списке, 1-й элемент вспомогательного массива содержит для каждого i-ro элемента массива данных индекс следующего за ним элемента.
Отрицательное число используется как признак конца списка. Тот же массив после сортировки:
10 25 20 6 21 8 1 30 - массив данных 2 7 4 5 1 0 3 - 1 - вспомогательный массив6 - индекс первого элемента в списке
Для создания бинарного дерева можно использовать два вспомогательных массива (индексы вершин его правого и левого поддерева). Отрицательное число используется как признак пустой ссылки. Память под такие структуры можно выделить либо на этапе компиляции, если размер можно задать константой, либо во время выполнения программы, например:
struct Node{
Data d; // тип данных Data должен быть определен ранее
int i;
};
Node spisok1[1000]; // на этапе компиляции
Node *pspisok2 = new Node[m]; // на этапе выполнения
