Технологии программирования

Разреженный массив — массив, большинство элементов которого равны между собой, так что хранить в памяти достаточно лишь небольшое число значений, отличных от основного (фонового) значения остальных элементов. Различают два их вида:

• массивы, в которых местоположения элементов со значениями, отличными от фонового значения, могут быть описаны математическими закономерностями;

• массивы со случайным расположением элементов.

В случае работы с разреженными массивами вопросы размещения их в памяти реализуются на логическом уровне с учетом их вида.

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

Отсюда решение. Воспользуемся гибридной динамико-статической структурой хранения клеточной информации с использованием статической матрицы. Применим статическую матрицу записей размером количество строк, умноженное на количество столбцов. Каждый элемент матрицы состоит из записи с двумя полями: поля формата вывода числовых значений (2 байта) и поля указателя на информацию клетки (4 байта).

Структура данных пустой электронной таблицы в виде статической матрицы теперь занимает (2 + 4) * 100 * 100 = 60 000 байт ≈ 59 кбайт. Объем менее 64 кбайт для единой статической структуры соответствует возможностям Turbo Pascal.

Процедура инициализации пустой таблицы будет заключаться в присвоении каждому полю формата значения стандартного формата и указателя значения Nil. Объем памяти, занимаемый статическим массивом, при работе программы никогда не изменяется.

По окончании ввода информации в выбранную клетку, если клетка не пустая (значение указателя на структуру клетки * Nil), то освобождается память, выделенная ранее под прежнюю информацию клетки. Новая информация клетки записывается в участок ДРП, равный по объему только полезной информации клетки. В соответствующее поле указателя выбранной клетки записывается значение указателя выделенного участка ДРП. Для записи только полезной информации в клетки применяем записи с вариантами (union в С, case в Turbo Pascal).

Полезная информация клетки включает постоянное поле атрибута содержимого клетки, а также вариантные поля остальной информации.

Пусть электронная таблица заполнена 300 числовыми значениями, 200 текстовыми строками длиной в 40 символов и 400 формулами с текстом формул по 30 символов. В этом случае для размещения электронной таблицы в оперативной памяти потребуется всего

300 * (2 + 10) + 200 * (2 + 41) + 400 * (2 + 10 + 31) = 29 400 байт ≈ 28,8 кбайт.

Как видно, при работе с электронной таблицей объем информации, занимаемой динамической структурой клеток, растет медленно. Окончательно принимаем данный вариант к реализации, выделив из атрибута случай ошибки при расчете формулы в отдельный атрибут Error.

Ниже приведен пример реализации на языке Turbo Pascal структуры данных электронной таблицы. Начнем описание структуры с глобальных описаний:

Туре

Real = Extended; {Требуется сопроцессор}

Const

{Структура данных электронной таблицы}

MAXCOLS = 100; {Размер таблицы}

MAXROWS = 100;

MAXINPUN = 79; {Длина вводимой строки}

{Значение атрибута вида клетки}

ТХТ = 0; {В клетке текст}

VALUE = 1; {В клетке значение}

FORMULA = 2; {В клетке формула}

{Тип вариантной информации клеток}

Туре

TString = String [MAXINPUT]; {Тип вводимых строк}

TCellRec = record {Тип информации клетки}

Error: Boolean; {Поле ошибки формулы}

case Attrib: Byte of {Attrib — это поле}

TXT: (TextStr: TString); {В клетке текст}

VALUE: (Value: Real); {В клетке значение}

FORMULA: (Fvalue: Real; {В клетке формула}

Formula: TString);

end;

end;

{Тип указателя на тип клетки}

TCellPtr = ^TCellRec;

{Тип элемента таблицы}

TCellTableElement = record

CellFormat: Word: {Формат клетки}

CellPtr: TCellPtr; {Указатель на клетку в ДРП}

end:

{Тип массива информации клеток таблицы}

TCellsTable = array [1..MAXCOLS, 1..MAXROWS] of TCellPtr;

Var {Глобальные переменные}

Cells: TCellsTable; {Статическая матрица всех клеток}