Шаблон иерархической структуры данных в памяти (односвязный список, содержащий статический массив указателей на объекты), страница 3

Нумерация элементов в структуре начинается с 0-ля, и идет последовательно по каждому элементу списка, а внутри него по каждому элементу массива. Если список пуст, то вначале создается 1-й элемент, так же как при добавлении. Далее производится поиск потенциального элемента списка, в который будет вставлен элемент, т.е. логический номер элемента должен  находиться в пределах этого элемента. В процессе поиска после просмотра каждого нового элемента списка требуемый логический номер уменьшается на количество занятых указателей в этом списке. В итоге после просмотра списка  получаем, указатель на элемент списка и требуемый номер внутри этого элемента, т.е. номер внутри статического массива. Если элемент списка не найден, то в конце списка создается новый элемент, в который может быть вставлен элемент, при этом номер внутри массива должен быть равен 0, иначе будет возвращено значение –1, потому как в противном случае логический не может быть достигнут. Далее, если оказывается, что элемент списка полон, тогда для получения свободных указателей, половина указателей из текущего элемента переписывается в новый,  который вставляется сразу же после текущего. Внутри массива элементы «раздвигаются» так что бы освободить место в требуемой позиции, в которой элемент (elem) и сохраняется.

Функция исключения элемента по номеру

T *Delete(int k);

Входные данные: логический номер (k)

Выходные данные: указатель на исключенный элемент

Сначала, как и в функции вставки, производится поиска элемента списка, в пределах которого может располагаться указанный логический номер. После цикла по списку получаем указатель на элемент списка и номер позиции внутри массива. Если элемент списка не найден значит номер больше максимально допустимого – ничего не удаляется, и возвращается NULL. В противном случае сохраняется указатель на исключаемый элемент, который впоследствии будет возвращен функцией, при этом сам исключаемый элемент не удаляется. При необходимости он может быть удален вне данной функции. После сохранения указателя, массив «сжимается». Далее массив проверяется на наличие в нем элементов, если он пуст, т.е. исключаемый элемент был последним, то соответствующий элемент списка удаляется.

Функция получения элемента по номеру

T *Get(int k); 

Входные данные: логический номер (k)

Выходные данные: указатель на полученный элемент

Данная функция аналогична предыдущей, отличается только тем, что элемент не исключается и структуры данных.

Функция сортировки

void Sort();

Входные данные: нет

Выходные данные: нет

Сортировка осуществляется следующим образом. Есть внешний цикл по всем элементам структуры (цикл по i).  На каждой i-й итерации пытаемся установить вместо i-го элемента минимальный из элементов с номером большим i. Для этого выполняем внутренний цикл (по j, j>=i), в котором определяем минимальный элемент. После чего меняем местами указатели минимального элемента и i-го. В результате полного прохода цикла по i получаем отсортированный массив. Важно отметить, что реально в программе позиция внутри структуры определяется не номером элемента (i или j), а двумя параметрами: указатель на элемент списка, и номер внутри элемента списка (массива). В силу чего усложняется шаг итерации, т.е. либо номер внутри массива увеличивается на 1-цу, либо, если массив целиком пройден, происходит перемещение к следующему элементу списка и номер устанавливается в 0. Важно, что при сортировке элементов, происходит только работа только с указателями, а не с самими объектами. 

Функция вставки с сохранением порядка

void InsertKeepOrder(T elem);                    

Входные данные: вставляемый элемент (elem)

Выходные данные: нет

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