Как проверить, не имеет ли указатель записи значения в Object Pascal / Delphi?

Question

Я пытаюсь создать реализацию связанного списка в Delphi, но не могу создать узел, потому что мне нужно проверить, пуст ли указатель заголовка или нет. Код, который я использую сейчас, выглядит следующим образом:

procedure LinkedList.addNode(newNode: Node);
var lastNode: Node;
begin
if pHead = nil then
  pHead := @newNode
else
   lastNode := peekLastNode(pHead^);
   lastNode.pNext := @newNode;
end;

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

Вот весь программа:

program LinkedListImplementation;

{$APPTYPE CONSOLE}

{$R *.res}

uses
  System.SysUtils;
type
  Node = record
    data: string;
    pNext: ^Node;
  end;
type
  LinkedList = class
    pHead: ^Node;
    function peekLastNode (currentNode: Node) : Node;
    function listToString(currentNode: Node) : String;
    procedure addNode (newNode: Node);
  end;

//the initial parameter for this function is LinkedList.pHead^
function LinkedList.peekLastNode (currentNode: Node) : Node;
begin
  if currentNode.pNext = nil then
    result := currentNode
  else
    result := peekLastNode(currentNode.pNext^);
end;

//produces string in form 'abc -> def -> ghi' from linked list
function LinkedList.listToString(currentNode: Node) : String;
begin
  if currentNode.pNext = nil then
    result := currentNode.data
  else
    result := currentNode.data + ' -> ' + listToString(currentNode.pNext^)
end;

//this uses helper method 'peekLastNode'
procedure LinkedList.addNode(newNode: Node);
var lastNode: Node;
begin
if pHead = nil then
  pHead := @newNode
else
   lastNode := peekLastNode(pHead^);
   lastNode.pNext := @newNode;
end;

var
  Strings: LinkedList;
  String1: Node;
  String2: Node;
begin
  try
    String1.data := 'abc';
    String2.data := 'def';
    Strings.Create();
    Strings.addNode(String1);
    Strings.addNode(String2);

    WriteLn(Strings.listToString(Strings.pHead^));
    ReadLn;
  except
    on E: Exception do
      Writeln(E.ClassName, ': ', E.Message);
  end;
end.

Answer 1

В addNode(), если pHead равно nil, тогда вы устанавливаете его так, чтобы он указывал на локальную переменную, а если это не nil, тогда вы устанавливаете lastNode.pNext вместо того, чтобы указывать на другую локальную переменную. Эти локальные переменные go выходят за пределы области видимости при выходе addNode(), в результате чего pHead / pNext остается висящим, поэтому они указывают на недопустимую память в следующий раз, когда вы попытаетесь их использовать.

Вам нужно чтобы использовать выделение кучи при добавлении Node экземпляров в ваш список, и вам нужно передавать ^Node указатели, а не Node экземпляры напрямую.

Кроме того, addNode() имеет ошибку logi c в том, что он устанавливает lastNode.pNext безоговорочно, является ли pHead nil или нет. Если pHead равен nil, то lastNode ничего не назначается. В блоке else отсутствуют операторы begin..end, связанные с его операциями.

Кроме того, вы даже неправильно конструируете объект LinkedList. Вместо Strings.Create(); должно быть Strings := LinkedList.Create();.

С учетом сказанного, попробуйте что-то вроде этого:

program LinkedListImplementation;

{$APPTYPE CONSOLE}

{$R *.res}

uses
  System.SysUtils;

type
  PNode = ^Node;
  Node = record
    data: string;
    pNext: PNode;
  end;

type
  LinkedList = class
  private
    pHead: PNode;
  public
    destructor Destroy; override;
    function peekLastNode(currentNode: PNode = nil): PNode;
    function listToString(currentNode: PNode = nil): String;
    function addNode(const data: String): PNode;
    procedure clear;
  end;

destructor LinkedList.Destroy;
begin
  clear;
end;

//the initial parameter for this function is LinkedList.pHead
function LinkedList.peekLastNode(currentNode: PNode) : PNode;
begin
  if currentNode = nil then currentNode := pHead;
  if (currentNode = nil) or (currentNode.pNext = nil) then
    Result := currentNode
  else
    Result := peekLastNode(currentNode.pNext);
end;

{ Alternatively:

function LinkedList.peekLastNode(currentNode: PNode): PNode;
begin
  if currentNode = nil then currentNode := pHead;
  Result := currentNode;
  if Result <> nil then
  begin
    while Result.pNext <> nil do
      Result := Result.pNext;
  end;
end;
}

//produces string in form 'abc -> def -> ghi' from linked list
function LinkedList.listToString(currentNode: PNode): String;
begin
  if currentNode = nil then currentNode := pHead;
  if currentNode = nil then
    Result := ''
  else if currentNode.pNext = nil then
    Result := currentNode.data
  else
    Result := currentNode.data + ' -> ' + listToString(currentNode.pNext);
end;

{ Alternatively:

function LinkedList.listToString(currentNode: PNode): String;
begin
  Result := '';
  if currentNode = nil then currentNode := pHead;
  if currentNode <> nil then
  begin
    Result := currentNode.data;
    while currentNode.pNext <> nil do
    begin
      currentNode := currentNode.pNext;
      Result := Result + ' -> ' + currentNode.data;
    end;
  end;
end;
}

//this uses helper method 'peekLastNode'
function LinkedList.addNode(const data: String): PNode;
begin
  New(Result);
  Result.data := data;
  Result.pNext := nil;
  if pHead = nil then
    pHead := Result
  else
    peekLastNode(pHead).pNext := Result;
end;

{ Alternatively:

function LinkedList.addNode(const data: String): PNode;
var
  currentNode: ^PNode;
begin
  currentNode := @pHead;
  while currentNode^ <> nil do
    currentNode := @((currentNode^).pNext);
  New(currentNode^);
  (currentNode^).data := data;
  (currentNode^).pNext := nil;
  Result := currentNode^;
end;
}

procedure LinkedList.clear;
var
  currentNode, nextNode: PNode;
begin
  currentNode := pHead;
  while currentNode <> nil do
  begin
    nextNode := currentNode.pNext;
    Dispose(currentNode);
    currentNode := nextNode;
  end;
end;

var
  Strings: LinkedList;
begin
  try
    Strings := LinkedList.Create();
    try
      Strings.addNode('abc');
      Strings.addNode('def');

      WriteLn(Strings.listToString());
    finally
      Strings.Free();
    end;
  except
    on E: Exception do
      Writeln(E.ClassName, ': ', E.Message);
  end;
  ReadLn;
end.