Допустим, что электронная таблица имеет размер 26×100 (от А1 до Z100), то есть состоит из 2`600 элементов. Теоретически можно хранить элементы таблицы в следующем массиве структур:
struct cell {
char cell_name[9];
char formula[128];
} list_entry[2600]; /* 2600 ячеек */
Ho 2`600, умноженное на 137 байтов (размер этой структуры в байтах), равняется 356`200 байтов памяти. Это слишком большой объем памяти, чтобы тратить его на не полностью используемый массив. Тем не менее, можно создать массив указателей (pointer array) на структуры типа cell. Для хранения массива указателей требуется намного меньше памяти, чем для массива структур. При каждом присвоении ячейке логического массива данных под эти данные выделяется память, а соответствующему указателю в массиве указателей присваивается адрес выделенного фрагмента. Такая схема позволяет добиться более высокой производительности, чем при связанном списке или двоичном дереве. Описание массива указателей выглядит следующим образом:
struct cell {
char cell_name[9];
char formula[128];
} list_entry;
struct cell *sheet[2600]; /* массив из 2600 указателей */
Этот меньший по объему занимаемой памяти массив используется для хранения указателей на вводимые в электронную таблицу данные. При вводе очередной записи в соответствующую ячейку массива заносится указатель на введенные данные. На рис. 23.2 показано, как выглядит в памяти разреженный массив, представленный в виде массива указателей.
+-+-+-+-+-+-+-+-+-+-+-+-+
|.|.|0|0|.|0|0|0|.|0|0|0|
+|+|+-+-+|+-+-+-+|+-+-+-+
| | | | +----+
| | | '->|A[8]|
| | | +----+
| | | +----+
| | '->|A[4]|
| | +----+
| | +----+
| '->|A[1]|
| +----+
| +----+
'->|A[0]|
+----+
Рис. 23.2. Представление разреженного массива в виде массива указателей
Перед использованием массива указателей каждый его элемент необходимо проинициализировать нулем (NULL), что означает отсутствие данной записи. Ниже показана функция инициализации массива:
void init_sheet(void)
{
register int t;
for(t=0; t < 2600; ++t) sheet[t] = NULL;
}
Когда пользователь вводит формулу в ячейку, занимающую определенное положение в электронной таблице (а положение ячейки, как известно, определяется ее именем), вычисляется индекс в массиве указателей sheet. Этот индекс получается путем преобразования строкового представления имени ячейки в число, как показано в следующем листинге:
void store(struct cell *i)
{
int loc;
char *p;
/* вычисление индекса по заданному имени */
loc = *(i->cell_name) - 'A'; /* столбец */
p = &(i->cell_name[1]);
loc += (atoi(p)-1) * 26; /* количество строк * ширина строки +
столбец */
if(loc >= 2600) {
printf("Ячейка за пределами массива.\n");
return;
}
sheet[loc] = i; /* поместить указатель в массив */
}
При вычислении индекса в функции store() предполагается, что все имена ячеек начинаются с прописной буквы, за которой следует целое число, например, В34, С19 и т.д. Поэтому в результате вычислений по формуле, запрограммированной в функции store(), имя ячейки А1 соответствует индексу 0, имя В1 соответствует индексу 1, А2 — 26 и т.д. Поскольку имена ячеек уникальны, индексы также уникальны и указатель на каждую запись хранится в соответствующей позиции массива. Если сравнить эту процедуру с версиями, использующими связанный список или двоичное дерево, становится понятно, насколько она проще и короче.
Функция удаления ячейки deletecell() также становится очень короткой. При вызове она просто обнуляет указатель на элемент и возвращает системе память.
void deletecell(struct cell *i)
{
int loc;
char *p;
/* вычисление индекса по заданному имени ячейки */
loc = *(i->cell_name) - 'A'; /* столбец */
p = &(i->cell_name[1]);
loc += (atoi(p)-1) * 26; /* количества строк * ширина строки +
столбец */
if(loc >= 2600) {
printf("Ячейка за пределами массива.\n");
return;
}
if(!sheet[loc]) return; /* не освобождать, если указатель нулевой
(null) */
free(sheet[loc]); /* освободить системную память */
sheet[loc] = NULL;
}
Этот код также намного быстрее и проще, чем в версии со связанным списком.
Процесс поиска ячейки по имени прост, поскольку имя ячейки однозначно определяет индекс в массиве указателей. Поэтому функция поиска принимает следующий вид:
struct cell *find(char *cell_name)
{
int loc;
char *p;
/* вычисление индекса по заданному имени ячейки */
loc = *(cell_name) - 'A'; /* столбец */
p = &(cell_name[1]);
loc += (atoi(p)-1) * 26; /* количества строк * ширина строки +
столбец */
if(loc>=2600 || !sheet[loc]) { /* эта ячейка пустая */
printf("Ячейка не найдена.\n");
return NULL; /* поиск неуспешный */
}
else return sheet[loc];
}
Анализ метода представления разреженного массива в виде массива указателей
Метод реализации разреженного массива на основе массива указателей обеспечивает намного более быстрый доступ к элементам, чем методы на основе связанного списка и двоичного дерева. Если массив не очень большой, выделение памяти для массива указателей лишь незначительно уменьшает объем свободной памяти системы. Тем не менее, в массиве указателей для каждой ячейки выделяется некоторый объем памяти независимо от того, используется она или нет. В некоторых приложениях это может быть ограничением, хотя в общем случае это не является проблемой.