Заметки
Связанный список на основе записей

:: Меню ::
:: На главную ::
:: FAQ ::
:: Заметки ::
:: Практика ::
:: Win API ::
:: Проекты ::
:: Скачать ::
:: Секреты ::
:: Ссылки ::

:: Сервис ::
:: Написать ::

:: MVP ::

:: RSS ::

Яндекс.Метрика
Любопытно, каким образом на базе записи в Delphi можно строить связанные списки.

type
  PSomeRec = ^TSomeRec;
  TSomeRec = record
    x, y, z: Integer;
    NextRecord: {packed} record end;
  end;

NextRecord - не что иное, как ссылка на следующий элемент списка (ключевое слово packed не обязательно). Вот как это работает:

{.$DEFINE USE_GLOBAL_VAR}
{$IFNDEF USE_GLOBAL_VAR}
  {$DEFINE USE_LOCAL_VAR}
{$ENDIF}

{$IFDEF USE_GLOBAL_VAR}
var
  h1, h2, h3, h4, h5: TSomeRec;
{$ENDIF}

procedure TForm1.Button1Click(Sender: TObject);
var
  tmp: PSomeRec;
  {$IFDEF USE_LOCAL_VAR}
  h5, h4, h3, h2, h1: TSomeRec;
  {$ENDIF}
begin
   h1.x := 1;
   h1.y := 1;
   h1.z := 1;

   h2.x := 2;
   h2.y := 2;
   h2.z := 2;

   h3.x := 3;
   h3.y := 3;
   h3.z := 3;

   h4.x := 4;
   h4.y := 4;
   h4.z := 4;

   h5.x := 5;
   h5.y := 5;
   h5.z := 5;

   tmp := @h1;

   while Integer(tmp) <= Integer(@h5) do
   begin
      ShowMessage(
         'Адрес записи: $' + IntToHex(Integer(tmp), 8) + #13 +
         'x = ' + tmp^.x.ToString + #13 +
         'y = ' + tmp^.y.ToString + #13 +
         'z = ' + tmp^.z.ToString + #13 +
         'Адрес следующей записи: $' + IntToHex(Integer(@tmp.NextRecord), 8)
      );
      tmp := @tmp.NextRecord;
   end;
end;

Обратите внимание на порядок объявления переменных в случае их глобального или локального размещения. Значение NextRecord, очевидно, вычисляется как @VarSomeRec + SizeOf(TSomeRec). При этом размер поля NextRecord не учитывается, в чем легко убедиться.

procedure TForm1.Button1Click(Sender: TObject);
begin
   ShowMessage(SizeOf(TSomeRec).ToString);
end;

Следовательно, в поле NextRecord хранится адрес, расположенный непосредственно за записью. А так как компилятор располагает переменные в памяти (или на стеке) последовательно, получаем эффект связанного списка. Определить последний элемент списка автоматически (вроде @VarSomeRec.NextRecord = nil) невозможно, так что этот момент придется контролировать вручную.

Особую осторожность следует проявлять с записями, содержащими разные по размеру поля. Нужно либо максимально уменьшить размер выравнивания ({$ALIGN 1}), либо вовсе отключить его ({$ALIGN OFF}), иначе результат может отличаться от ожидаемого.

type
  {$ALIGN OFF}
  TSomeRec = record
    x: Integer;
    y: Word;
    z: Byte;
    NextRecord: {packed} record end;
  end;
  {$ALIGN ON}

Однако нет ничего интересного в том, чтобы работать со статическим списком, динамика наше все!

procedure TForm1.Button1Click(Sender: TObject);
const
  Count = 5;
var
  p: Pointer;
  i: Integer;
  tmp: PSomeRec;
begin
   p := GetMemory(Count * SizeOf(TSomeRec));
   tmp := p;

   i := 0; // Заполняем список
   while i < Count do
   begin
      tmp^.x := i+1;
      tmp^.y := i+1;
      tmp^.z := i+1;

      tmp := @tmp.NextRecord;
      Inc(i);
   end;

   tmp := p;

   i := 0; // Просматриваем список
   while i < Count do
   begin
      ShowMessage(
            'Адрес записи: $' + IntToHex(Integer(tmp), 8) + #13 +
            'x = ' + tmp^.x.ToString + #13 +
            'y = ' + tmp^.y.ToString + #13 +
            'z = ' + tmp^.z.ToString + #13 +
            'Адрес следующей записи: $' + IntToHex(Integer(@tmp.NextRecord), 8)
      );
      tmp := @tmp.NextRecord;
      Inc(i);
   end;

   FreeMemory(p);
end;

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

При использовании материала - ссылка на сайт обязательна