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

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

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

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

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