Свободные массивы

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

Поскольку стандарты языка программирования не допускают такого вида массивов, то создается симбиоз массивов:

1.      одномерный массив указателей, число элементов n которого равно числу строк переменной длины,

2.      и n одномерных массивов различной длины.

Таким образом, массив указателей имеет фиксированную длину, значит, фиксировано и число строк свободного массива. Память под каждую строку свободного массива запрашивается динамически.Следовательно, при создании такого массива требуется (n+1) обращений к ОС для получения динамической памяти. После того как надобность в свободном массиве отпала, необходимо освободить занимаемую им память, что опять-таки потребует (n+1) обращений к ОС.Массив указателей, U имеет n элементов, каждый из которых содержит адреса векторов-строк массива.Для управления свободным массивом может создаваться дескриптор, в простейшем случае - это указатель на массив указателей.Свободные массивы используются для представления других, более сложных структур. С примерами таких массивов мы встретимся ниже.По аналогичной схеме могут быть созданы и двухмерные массивы с одинаковыми длинами строк.

К недостаткам можно отнести потребность в дополнительной памяти под массив указателей и многократное обращение к ОС для получения памяти.

К преимуществам можно отнести следующее:
    1) при работе с очень большими массивами получение больших сплошных областей может стать невозможным; в то же время получение памяти под каждую строку вполне возможно;
    2) появляется возможность обрабатывать большие массивы данных, хранящихся в файлах, размещая в оперативной памяти только те строки, которые совместно обрабатываются в данный момент;
    3) применение свободных массивов позволяет более эффективно использовать память;
    4) при сортировке массива по строкам (не элементов в строке, а самих строк) вместо перестановок строк в некоторых случаях можно переставлять только элементы массива указателей, в то время как сами строки остаются на месте.