Энциклопедия Turbo Pascal. Главы 1-4 - Применение массива указателей для организации разреженных массивов

ОГЛАВЛЕНИЕ

Применение массива указателей для организации разреженных массивов

Предположим, что электронная матрица имеет размеры 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; { конец процедуры удаления }

Если вы сравните эту процедуру с версией,  использующей связанный список или дерево, то обнаружите, что она значительно проще и выполняется быстрее.

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