如何在没有临时数组的情况下对齐 2 个数组？

Question

我有 2 个数组需要对齐线条。我准备了 'control' 数组，其中包含有关如何对齐数组的信息，然后我在临时数组的帮助下执行此操作。

在图片中查看数组和对齐数组的结果：

这是我作为 MCVE 使用的代码：

    unit Unit1;

    interface

    uses
      Winapi.Windows, Winapi.Messages, System.SysUtils, System.Variants, System.Classes, Vcl.Graphics,
      Vcl.Controls, Vcl.Forms, Vcl.Dialogs, Vcl.StdCtrls,
      System.Math,
      System.Generics.Defaults,
      System.Generics.Collections;

    type
      TForm1 = class(TForm)
        Button1: TButton;
        Button2: TButton;
        procedure Button1Click(Sender: TObject);
        procedure Button2Click(Sender: TObject);
      private
        { Private declarations }
      public
        { Public declarations }
      end;

      TSide = (sLeft, sRight, sBoth);

      TData = record
        DataID: integer;
        DataName: string;
        BlankLine: boolean;
      end;

      TCtrlData = record
        Side: TSide;
        Idx_l: integer;
        Idx_r: integer;
      end;

    var
      Form1: TForm1;
      aLeft, aRight, aLeft_tmp, aRight_tmp: TArray<TData>; // main and temp arrays
      aCtrl: TArray<TCtrlData>; // control array with instructions o nhow to align lines

    implementation

    {$R *.dfm}

    procedure PrepareData;
    begin
      // prepare data
      SetLength(aLeft, 4);
      aLeft[0].DataID := 1; aLeft[0].DataName := 'One';
      aLeft[1].DataID := 2; aLeft[1].DataName := 'Three';
      aLeft[2].DataID := 3; aLeft[2].DataName := 'Six';
      aLeft[3].DataID := 4; aLeft[3].DataName := 'Eight';
      SetLength(aRight, 6);
      aRight[0].DataID := 1; aRight[0].DataName := 'One';
      aRight[1].DataID := 2; aRight[1].DataName := 'Two';
      aRight[2].DataID := 3; aRight[2].DataName := 'Four';
      aRight[3].DataID := 4; aRight[3].DataName := 'Five';
      aRight[4].DataID := 5; aRight[4].DataName := 'Seven';
      aRight[5].DataID := 6; aRight[5].DataName := 'Eight';

      // do the magic - prepare control array
      SetLength(aCtrl, 8);
      aCtrl[0].Side := sBoth; aCtrl[0].Idx_L := 0; aCtrl[0].Idx_R := 0;
      aCtrl[1].Side := sRight; aCtrl[1].Idx_R := 1;
      aCtrl[2].Side := sLeft; aCtrl[2].Idx_L := 1;
      aCtrl[3].Side := sRight; aCtrl[3].Idx_R := 2;
      aCtrl[4].Side := sRight; aCtrl[4].Idx_R := 3;
      aCtrl[5].Side := sLeft; aCtrl[5].Idx_L := 2;
      aCtrl[6].Side := sRight; aCtrl[6].Idx_R := 4;
      aCtrl[7].Side := sBoth; aCtrl[7].Idx_L := 3; aCtrl[7].Idx_R := 5;
    end;

    procedure TForm1.Button1Click(Sender: TObject);
    var
      i, vIndex: integer;
    begin
      PrepareData;


      { prepare arrays based on Control array
      Loop through Control array and fill temp arrays from Left or Right arrays }
      SetLength(aLeft_tmp, 0);
      SetLength(aRight_tmp, 0);
      SetLength(aLeft_tmp, Length(aCtrl));
      SetLength(aRight_tmp, Length(aCtrl));
      vIndex := 0;
      for i := 0 to High(aCtrl) do
      begin
        if aCtrl[i].Side = sBoth then // Data from Both
        begin
          aLeft_tmp[vIndex] := aLeft[aCtrl[i].Idx_L];
          aRight_tmp[vIndex] := aRight[aCtrl[i].Idx_R];
          Inc(vIndex);
        end;
        if aCtrl[i].Side = sLeft then // Data from Left side
        begin
          aLeft_tmp[vIndex] := aLeft[aCtrl[i].Idx_L];
          aRight_tmp[vIndex].BlankLine := true;
          Inc(vIndex);
        end;
        if aCtrl[i].Side = sRight then // Data from Right side
        begin
          aRight_tmp[vIndex] := aRight[aCtrl[i].Idx_R];
          aLeft_tmp[vIndex].BlankLine := true;
          Inc(vIndex);
        end;
      end;

      // Assign aligned data to main arrays
      aLeft := aLeft_tmp;
      aRight := aRight_tmp;
    end;

由于我对很多数组使用相同或相似的代码，因此我尝试使用 AlignArrays 函数重构和简化它：

    procedure AlignArrays(vCtrl: TArray<TCtrlData>; var vLeft, vRight: TArray<TData>);
    var
      i, vIndex: integer;
      vLeft_tmp, vRight_tmp: TArray<TData>;
    begin
      SetLength(vLeft_tmp, Length(vCtrl));
      SetLength(vRight_tmp, Length(vCtrl));
      vIndex := 0;

     { prepare arrays based on Control array
      Loop through Control array and fill temp arrays from Left or Right arrays }
      for i := 0 to High(vCtrl) do
      begin
        if vCtrl[i].Side = sBoth then // Data from Both
        begin
          vLeft_tmp[vIndex] := vLeft[vCtrl[i].Idx_L];
          vRight_tmp[vIndex] := vRight[vCtrl[i].Idx_R];
          Inc(vIndex);
        end;
        if vCtrl[i].Side = sLeft then // Data from Left side
        begin
          vLeft_tmp[vIndex] := vLeft[vCtrl[i].Idx_L];
          vRight_tmp[vIndex].BlankLine := true;
          Inc(vIndex);
        end;
        if vCtrl[i].Side = sRight then // Data from Right side
        begin
          vRight_tmp[vIndex] := vRight[vCtrl[i].Idx_R];
          vLeft_tmp[vIndex].BlankLine := true;
          Inc(vIndex);
        end;
      end;

      vLeft := vLeft_tmp;
      vRight := vRight_tmp;
    end;

    procedure TForm1.Button2Click(Sender: TObject);
    var
      i, vIndex: integer;
    begin
      PrepareData;

      AlignArrays(aCtrl, aLeft, aRight);

    end;

问题：是否可以更好地重构，是否可以在没有临时数组的情况下处理数组？

编辑：

从评论和回答来看，我似乎浪费了太多时间准备MCVE，我应该更好地解释我遇到的问题。但是，从 CleoR 的回答中，我想到了通过从最后一行开始并对齐到顶部来对齐数组的想法。它似乎有效，原因如下：因为控件数组有关于如何对齐行的说明，所以我确切地知道数组的大小是多少。而且由于对齐意味着 'stretchin' array/inserting 在需要的地方新的空白行，如果我从下往上开始，我不需要插入任何东西，只移动需要移动的行。

简单有效 - 没有临时数组：

procedure AlignArraysBackwards(vCtrl: TArray<TCtrlData>; var vLeft, vRight: TArray<TData>);
var
  i: integer;
  vBlankRecord:TData;
begin

  // set blank record to blank out the moved line
  vBlankRecord.DataID:=0;
  vBlankRecord.DataName:='';
  vBlankRecord.BlankLine:=True;

  // set lenght for arrays
  SetLength(vLeft, Length(vCtrl));
  SetLength(vRight, Length(vCtrl));

  // align - starting from the bottom up
  for i := High(vCtrl) downto 0 do
  begin
    if vCtrl[i].Side = sBoth then // Data from Both
    begin
      // move Left line
      vLeft[i] := vLeft[vCtrl[i].Idx_L];
      // blank out the line we just moved
      if vCtrl[i].Idx_L<>i then vLeft[vCtrl[i].Idx_L]:=vBlankRecord;
      // move Rigth line
      vRight[i] := vRight[vCtrl[i].Idx_R];
      // blank out the line we copied from
      if vCtrl[i].Idx_R<>i then vRight[vCtrl[i].Idx_R]:=vBlankRecord;
    end;
    if vCtrl[i].Side = sLeft then // Data from Left side
    begin
      // move Left line
      vLeft[i] := vLeft[vCtrl[i].Idx_L];
      // blank out the line we just moved
      if vCtrl[i].Idx_L<>i then  vLeft[vCtrl[i].Idx_L]:=vBlankRecord;
      // blank Right line
      vRight[i].BlankLine := true;
    end;
    if vCtrl[i].Side = sRight then // Data from Right side
    begin
      // move Left line
      vRight[i] := vRight[vCtrl[i].Idx_R];
      // blank out the line we just moved
      if vCtrl[i].Idx_R<>i then  vRight[vCtrl[i].Idx_R]:=vBlankRecord;
      // blank Left line
      vLeft[i].BlankLine := true;
    end;
  end;
end;

Answer 1

更新：将解决方案更改为伪代码。

您不需要临时数组，您可以就地完成。

假设左右数组足够 space 并且它们的大小相同。

对于每个数组，您需要跟踪数组中的最后一个元素。让我们称之为数据指针。使用名为 endPointer 的计数器对数组进行反向循环。

在循环的每一步检查两个数组的 array[dataPointer] == endPointer + minElement 是否。
如果为真，array[endPointer] = endPointer + minElement 并递减 dataPointer。
如果为假，array[endPointer] = skip_value.

这样做直到 endPointer 越过数组的开头。

skip_value = 0

//Handles our assumptions.
function setup(left,right)
    left.sort()
    right.sort()
    ldPointer = len(left)-1
    rdPointer = len(right)-1
    maxElement = max(left[ldPointer],right[rdPointer])
    //This is 1 in your examples. You can hard code this number.
    minElement = min(left[0],right[0])
    padLength = maxElement - minElement + 1
    pad(left,padLength)
    pad(right,padLength)
    return ldPointer,rdPointer,minElement

//Aligns the arrays.
function align(left,right)
    ldPointer,rdPointer,minElement = setup(left,right)
    for endPointer = len(left)-1; endPointer >= 0; i--
        //Look at the left element.
        if left[ldPointer] == endPointer+minElement
            left[endPointer] = endPointer+minElement
            ldPointer = ldPointer - 1
        else
            left[endPointer] = skip_value
        //Look at the right element.
        if right[rdPointer] == endPointer+minElement
            right[endPointer] = endPointer+minElement
            rdPointer = rdPointer - 1
        else
            right[endPointer] = skip_value

如果你想自己尝试算法，这里是 link 到 repo。 https://github.com/cleor41/Whosebug_AlignArrays.

Delphi我一点也不知道，但我试着用Delphi写出来，也许你能更好地理解它。我也不明白需要控制数组。

procedure AlignArraysBackwards(var vLeft, vRight: TArray<TData>);
var
  endPointer: Integer;
  vBlankRecord: TData;
  // Assumes the arrays have at least 1 element
  ldPointer: Length(vLeft)-1;
  rdPointer: Length(vRight)-1;
  maxElement: Max(vLeft[ldPointer].DataID,vRight[rdPointer].DataID);
  // Set this to 1 if arrays should always be 1 alligned
  // Else it aligns arrays starting from the array with the smallest value.
  minElement: Min(vLeft[0].DataID,vRight[0].DataID);
  padLength: maxElement - minElement + 1;
begin

  // set blank record to blank out the moved line
  vBlankRecord.DataID:=0;
  vBlankRecord.DataName:='';
  vBlankRecord.BlankLine:=True;

  // set length for arrays
  SetLength(vLeft, padLength);
  SetLength(vRight, padLength);

  // align - starting from the bottom up
  for endPointer := High(vLeft) downto 0 do
  begin
    // Start Left array
    if vLeft[ldPointer].DataID = endPointer + minElement
    then
      begin
        vLeft[endPointer] := vLeft[ldPointer];
        ldPointer := ldPointer - 1;
      end
    else
      begin
        vLeft[endPointer] := vBlankRecord;
      end;
    // End Left Array
    // Start Right array
    if vRight[rdPointer].DataID = endPointer + minElement
    then
      begin
        vRight[endPointer] := vRight[rdPointer];
        rdPointer := rdPointer - 1;
      end
    else
      begin
        vRight[endPointer] := vBlankRecord;
      end;
    // End Right Array
  end;
end;

Answer 2

您可以创建一个方法将记录插入数组中，或者（如我的示例中）您可以使用泛型 (TList)。

program Project1;

{$APPTYPE CONSOLE}
{$R *.res}

uses
  System.SysUtils,
  Generics.Collections;

type
  TData = record
    DataID: integer;
    DataName: string;
    BlankLine: boolean;
    // I add this function to make it make the code easier to read
    class function New(const DataID: integer; DataName: string;
      BlankLine: boolean = false): TData; static;
  end;

var
  aLeft, aRight: TList<TData>;

  { TData }

class function TData.New(const DataID: integer; DataName: string;
  BlankLine: boolean = false): TData;
begin
  result.DataID := DataID;
  result.DataName := DataName;
  result.BlankLine := BlankLine;
end;

procedure AllignData;
var
  n: word;
begin
  n := 0;
  repeat
    if (n < aRight.Count) and (n < aLeft.Count) then
    begin
      if aLeft[n].DataID < aRight[n].DataID then
        aRight.Insert(n, TData.New(aLeft[n].DataID, '', true))
      else if aLeft[n].DataID > aRight[n].DataID then
        aLeft.Insert(n, TData.New(aRight[n].DataID, '', true));
      // if they are equlal, we skip the line
      // you wish to use an array instead, write a function inserting data item in it
    end
    else
    begin
      if n < aLeft.Count then
        aRight.Add(TData.New(aRight[n].DataID, '', true));
      if n < aRight.Count then
        aLeft.Add(TData.New(aRight[n].DataID, '', true));
    end;

    inc(n);
  until (n >= aRight.Count) and (n >= aLeft.Count);
end;

procedure OutputData;
var
  n: word;
  sl, sr: string;
begin
  n := 0;
  repeat
    if n < aLeft.Count then
      sl := aLeft[n].DataName
    else
      sl := '';
    if n < aRight.Count then
      sr := aRight[n].DataName
    else
      sr := '';

    writeln(sl: 15, sr: 15);
    inc(n);
  until (n >= aRight.Count) and (n >= aLeft.Count);
end;

begin
  // Initialize the data
  aLeft := TList<TData>.Create;
  aRight := TList<TData>.Create;
  try
    aLeft.Add(TData.New(1, 'One'));
    aLeft.Add(TData.New(3, 'Three'));
    aLeft.Add(TData.New(6, 'Six'));
    aLeft.Add(TData.New(8, 'Eight'));
    aRight.Add(TData.New(1, 'One'));
    aRight.Add(TData.New(2, 'Two'));
    aRight.Add(TData.New(4, 'Four'));
    aRight.Add(TData.New(5, 'Five'));
    aRight.Add(TData.New(7, 'Seven'));
    aRight.Add(TData.New(8, 'Eight'));
    aRight.Add(TData.New(9, 'Nine'));
    aRight.Add(TData.New(10, 'Ten'));
    // Do the output and processing
    OutputData;
    // I assume that the arrays (lists) have been sorted
    AllignData;
    writeln;
    OutputData
  finally
    aLeft.Free;
    aRight.Free;
  end;
  readln;

end.

如何在没有临时数组的情况下对齐 2 个数组？

How to align 2 arrays without temporary arrays?

arrays

delphi

algorithm

delphi-xe7