Энциклопедия Turbo Pascal. Главы 1-4 - Обработка разреженных массивов

Обработка разреженных массивов

Обработка разреженных массивов является основной областью применения динамического распределения памяти. В разреженных массивах фактически имеются не все элементы. Такой массив может потребоваться в тех случаях,  когда размеры массива значительно превышают размер памяти вашей машины и когда не все элементы массива будут использоваться. Массивы большой размерности требуют большого расхода памяти,  поскольку ее объем растет по экспоненте в зависимости от размера массива. Например, для символьной матрицы 10 х10 требуется только 100 байт памяти,  а для матрицы 100х100 требуется 10 000 байт и для матрицы 1000х1000 требуется уже  1  000 000 байт памяти.

Электронная таблица является хорошим примером разреженной матрицы.  Даже если матрица будет большой,  например,  999х999, в каждый конкретный момент времени будет использована только некоторая ее часть.  Каждому элементу электронной матрицы ставится в соответствие формула,  значение или символьные строки. Память под каждый элемент разреженной матрицы выделяется по мере необходимости.  Хотя использоваться может лишь небольшая часть элементов, вся матрица может быть очень большой - больше чем обычные размеры памяти ЭВМ.

Имеется три различных метода создания разреженных массивов: связанный список,  двоичное дерево и массив указателей. Каждый из этих методов предполагает,  что электронная матрица имеет форму, представленную на следующей странице.

В этом примере Х располагается в ячейке В2.

     ----А---- ----В---- ----С---- ...
     1
     2                 Х
     3
     4
     5
              . . .