Глава 23. Разреженные массивы

Содержание

Одна из наиболее интересных задач программирования — реализация разреженных массивов. Разреженный массив, или разреженная матрица (sparse array), — это массив, в котором не все элементы используются, имеются в наличии или нужны в данный момент. Разреженные массивы полезны в тех случаях, когда выполняются два условия: размер массива, который требуется приложению, достаточно большой (возможно, превышает объем доступной памяти), и когда не все элементы массива используются. Таким образом, разреженный массив — это, как правило, большой, но редко заполненный массив. Как будет показано далее, есть несколько способов реализации разреженных массивов. Но перед тем как приступить к их рассмотрению, давайте уделим внимание задачам, которые решаются с помощью разреженных массивов.