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

Костерин В В

Конкретные организации структур данных и алгоритмы реализации операций с ними рассмотрены в [21, 23, 25].

4.5. ПРОЕКТИРОВАНИЕ И ДОКУМЕНТИРОВАНИЕ ОПЕРАТИВНЫХ СТРУКТУР ДАННЫХ

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

Однако

длительное сохранение информации возможно лишь во внешней памяти, поэтому проектирование оперативных структур данных программы должно вестись в неотрывной связи (параллельно) с проектированием структуры файлов программы. Данные многих оперативных структур должны сохраняться в файлах и восстанавливаться по информации, записанной ранее в файл.

Пусть требуется спроектировать программу электронной таблицы. Такой проект выполнила фирма "Borland Inc", когда ей понадобилась демонстрационная программа. Обоснование потребности и цели разработки этого проекта были рассмотрены в гл. 2.

Что видит пользователь при работе с электронной таблицей? — Огромный двухмерный массив клеток.

Что пользователь может записать в клетки? — Числовые значения, строки текстов и формулы. Каждая клетка также должна хранить информацию о формате вывода числовых значений (форматы: целый, денежный, научный и т. д.). Значит, каждая клетка должна содержать атрибут того, что находится в клетке: пустая клетка, числовое значение в клетке, строка текста, корректная формула, некорректная формула. Пусть информация о значении числа имеет тип расширенный, вещественный (10 байт); строки текста содержат до 79 символов; информация формулы состоит из поля со значением, рассчитанного по формуле (10 байт), а также поля текста формулы (79 байт). Самая длинная информация у клетки с формулой: информация формата (2 байта), значение, рассчитанное по формуле (10 байт), поле текста формулы (79 байт). Итого длина информации клетки составляет 91 байт.

Пусть программа будет работать с электронной таблицей размером 100 × 100 клеток. Тогда информация электронной таблицы в случае использования структуры данных в виде статической матрицы занимает 91 × 100 × 100 байт = 910 000 байт ≈ 889 кбайт.

Требуемый объем для размещения структуры превышает стандартную память компьютера класса IBM PC XT — 640 кбайт, поэтому надо отказаться от использования структуры данных в виде статической матрицы.

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

На практике (например, при работе с конечными графами) встречаются массивы, которые в силу определенных причин могут записываться в память не полностью, а частично. Это особенно актуально для массивов настолько больших размеров, что для их хранения в полном объеме памяти может быть недостаточно. К таким массивам относят симметричные и разреженные массивы.

Например, квадратная матрица, у которой элементы, расположенные симметрично относительно главной диагонали, попарно равны друг другу, называют симметричной. Если матрица порядка n симметрична, то в ее физической структуре достаточно отобразить не n², а лишь 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.