|
Страница 36 из 60
Применение массива указателей для организации разреженных массивов Предположим, что электронная матрица имеет размеры 26х100 /с
А1 по Z100/ и состоит всего из 2 600 элементов. Теоретически мож-
но использовать следующий массив записей:
str9 = string[9];
str128 = string[128];
CellPointer = CellPointer;
cell = record
CellName:str9;
formula:str128;
end;
var
pa:array[1..2600] of cell;
Однако, 2 600 ячеек, помноженные на 128 (размер одного поля
для формулы), потребует 332 800 байт памяти под довольно неболь-
шую электронную таблицу. Такой подход, очевидно, нельзя использо-
вать на практике. В качестве альтернативы можно использовать мас-
сив указателей записей. В этом случае потребуется значительно
меньше памяти, чем при создании всего массива. Кроме того, произ-
водительность будет значительно выше, чем при использовании свя-
занного списка или дерева. Для этого метода данные описываются
следующим образом:
type
str9 = string[9];
str128 = string[128];
cell = record
CellName:str9;
formula:str128;
end;
var
sheettarray[1..10000] of CellPointer;
Этот массив меньшего размера можно использовать для содержа-
ния указателей на информацию, введенную пользователем в электрон-
ную матрицу. При вводе каждого элемента указатель на информацион-
ную ячейку помещается в соответствующее место массива. Рис.16
иллюстрирует структуру памяти, когда разреженный массив строится
на основе массива указателей.
a
----T----T---T----T-----------T----T---¬
¦ ¦1nil¦ ¦1nil¦ ¦1nil¦ ¦
L-+-+----+-+-+----+-----------+----+-+--
¦ ¦ ¦ ---------------¬
¦ ¦ L---¦2info for A[n]¦
¦ ¦ L---------------
¦ ¦
¦ ¦ ----------------¬
¦ L-- ¦2 info for A[a]¦
¦ L----------------
¦ ----------------¬
L---¦2 info for A[l]¦
L----------------
Рис.16. Использование массива указателей для организации раз-
реженного массива:
1 - нулевое значение указателя; 2 - информационные поля соответс-
твующего элемента.
Перед первым использованием массива указателей необходимо
каждый элемент установить в нулевое значение, что означает от-
сутствие элемента в этой позиции. Используйте следующую функцию:
procedure InitSheet;
var
t:integer;
begin
for t := 1 to 10000 do sheet[t] := nil;
end; { конец блока инициализации }
Перед написанием процедуры вставки следует запрограммировать
функцию поиска индекса. Эта функция находит соответствующий ин-
декс массива указателей по заданному названию ячейки. При поиске
индекса предполагается, что все названия начинаются с большой
буквы, за которой идет некоторое число, например, В34, С19 и т.д.
Эта функция приводится ниже на следующей странице.
Эта функция позволяет при реализации процедуры вставки
{ эта функция определяет индекс указанной ячейки }
function FindIndex(i: CellPointer): integer;
var
loc,temp,code:integer;
t:str9;
begin
loc := ord(i^.CellName[1]);
t := copy(i^.CellName,2,9);
val(t,temp,code);
loc := loc+(temp*20);
find := loc;
end; { конец функции поиска индекса }
соответствующую позицию массива указателей для каждой ячейки. Как
видно, поиск нужного индекса выполняется просто и быстро, так как
нет необходимости выполнять последовательный просмотр. Этот метод
иногда называют прямым хешированием, поскольку индекс ячейки па-
мяти определяется непосредственно по заданному элементу. Когда
пользователь вводит формулу для ячейки, то эта ячейка /которая
задается своим обозначением/ задает индекс массива указателей
"sheet". Индекс определяется по обозначению ячейки путем его пре-
образования в число с помощью функции FindIndex. Вставка осущест-
вляется с помощью следующей процедуры:
procedure Store(New: CellPointer);
var
loc:integer;
begin
loc := FindIndex(New);
if loc>10000 then WriteLn('Location out of bounds')
else sheet[loc] := New;
end; { конец процедуры вставки }
Поскольку каждая ячейка имеет уникальное обозначение, она
будет иметь также уникальный индекс. Поскольку используется стан-
дартная кодировка символов, указатель каждого элемента будет пра-
вильно помещен в массив. Если вы сравните эту процедуру с вариан-
том для связанного списка, то вы обнаружите, что она значительно
короче и проще.
Функция удаления также выглядит короче. При вызове этой
функции задается индекс ячейки и возвращается указатель элемента.
Кроме того, освобождаемая память возвращается системе:
{ удаление ячейки из массива }
procedure Delete(r_cell: CellPointer);
var
loc:integer;
begin
loc := FindIndex(r_cell);
if loc>10000 then WriteLn('Cell out of bounds')
else
begin
Dispose(r_cell);
sheet[loc]:=nil;
end;
end; { конец процедуры удаления }
Если вы сравните эту процедуру с версией, использующей свя-
занный список или дерево, то обнаружите, что она значительно про-
ще и выполняется быстрее.
Следует помнить, что сам массив указателей требует некоторо-
го дополнительного расхода памяти под каждую ячейку. В некоторых
случаях это является серьезным ограничением.
|