На практике (например, при работе с конечными графами) встречаются массивы, которые в силу определенных причин могут записываться в память не полностью, а частично. Это особенно актуально для массивов настолько больших размеров, что для их хранения в полном объеме памяти может быть недостаточно. К таким массивам относят симметричные и разреженные массивы.
Например, квадратная матрица, у которой элементы, расположенные симметрично относительно главной диагонали, попарно равны друг другу, называют симметричной. Если матрица порядка n симметрична, то в ее физической структуре достаточно отобразить не n2, а лишь n(n + 1)/2 ее элементов. Доступ к треугольному массиву организуется таким образом, чтобы можно было обращаться к любому элементу исходной логической структуры, в том числе и к элементам, значения которых, хотя и не представлены в памяти, могут быть определены на основе значений симметричных им элементов. На практике для работы с симметричной матрицей разрабатываются следующие процедуры:
• формирование вектора;
• преобразование индексов матрицы в индекс вектора;
• записи в вектор элементов верхнего треугольника элементов исходной матрицы;
• получение значения элементов матрицы из ее упакованного представления.
В данном проектном случае нет особой симметрии значений элементов.
Разреженный массив — массив, большинство элементов которого равны между собой, так что хранить в памяти достаточно лишь небольшое число значений, отличных от основного (фонового) значения остальных элементов. Различают два их вида:
• массивы, в которых местоположения элементов со значениями, отличными от фонового значения, могут быть описаны математическими закономерностями;
• массивы со случайным расположением элементов.
В случае работы с разреженными массивами вопросы размещения их в памяти реализуются на логическом уровне с учетом их вида.
Помня об этом, классифицируем случай электронной таблицы как структуру данных в виде двухмерного массива со случайным расположением редких элементов на фоне пустых значений.
Отсюда решение. Воспользуемся гибридной динамико-статической структурой хранения клеточной информации с использованием статической матрицы. Применим статическую матрицу записей размером количество строк, умноженное на количество столбцов. Каждый элемент матрицы состоит из записи с двумя полями: поля формата вывода числовых значений (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; {Статическая матрица всех клеток}
CurCelclass="underline" TCellPtr; {Указатель на текущую клетку}
CurCol, {Колонка текущей клетки}
CurRow: Word; {Строка текущей клетки}
Как видно, с целью краткости вызовов большинства процедур программы было принято решение об использовании весьма небольшого набора глобальных переменных. При именовании констант использованы только строчные буквы. Имена типов имеют префикс "Т". Имена, используемые часто в паре, выровнены по длине, например: MAXCOLS, MAXROWS, CurCol, CurRow. Два последних имени, используемых парно, были выровнены по длине. При выравнивании сокращено слово column — колонка. Используемые во многих процедурах глобальные имена сделаны краткими.
Помимо описанного в гл. 1 рефакторинга имен можно производить рефакторинг структуры данных программы. При рефакторинге структуры данных вместо нескольких самостоятельных массивов возможно использование таблицы и т. д. Особое внимание при рефакторинге следует уделять комментированию логической структуры данных.
4.6. ФАЙЛОВЫЕ СТРУКТУРЫ
Файл — упорядоченный набор информации на внешнем носителе (наиболее часто на дисковом носителе).
Физическая информация файла на внешнем носителе соотносится с логической структурой данных оперативной памяти методами доступа операционных систем.
Обычно файловая система операционной системы компьютера содержит следующие средства:
• управление файлами: хранение файлов, обращение к ним, их коллективное использование и защита;
• обеспечение целостности файлов — гарантирование того, что файл содержит только то, что требовалось;