Удаление последнего элемента списка

[vladimashev]

Описание однонаправленного списка:

Код: Выделить всё

type
    list = ^node;
    node = record
        elem: integer;
        next: list;
    end;

Пусть у нас есть список, L - ссылка на его голову. Я хочу удалить последний элемент списка. Вообще всегда это делается так:

Код: Выделить всё

if L^.next = nil then begin
   dispose(L);
   L := nil;
end
else begin
   p := L; {p - переменная ссылочного типа, которую необходимо описать в блоке var}
   while p^.next^.next <> nil do
      p := p^.next;
   dispose(p^.next);
   p^.next := nil;
end;

Вопрос вот в чем: почему нельзя просто присвоить p := L и пока p^.next <> nil присваивать p := p^.next; Затем просто dispose(p); p := nil. Так не работает, проверял, но не понимаю, почему. И еще непонятно следующее: почему в таком случае работает рекурсивная процедура по удалению последнего элемента списка:

Код: Выделить всё

procedure DelLast(var p: list);
begin
    if p^.next = nil then
    begin
        dispose(p);
        p := nil;
    end
    else
        DelLast(p^.next);
end;

В эту процедуру же мы передаем список по ссылке, то есть этот способ удаления вроде бы аналогичен способу, описанному выше, который, в свою очередь, не работает. Как так? Буду рад помощи, заранее спасибо!

[iskander]

Вопрос вот в чем: почему нельзя просто присвоить p := L и пока p^.next <> nil присваивать p := p^.next; Затем просто dispose(p); p := nil.

В этом случае поле next предпоследнего(а после удаления уже последнего) элемента будет указывать в никуда.

[vladimashev]

iskander, но после dispose я же присваиваю p := nil, и теперь next последнего элемента (бывшего предпоследнего) указывает как раз на р = nil.

[Дож]

iskander, но после dispose я же присваиваю p := nil, и теперь next последнего элемента (бывшего предпоследнего) указывает как раз на р = nil.

Нет, p := nil записывает значение в переменную p, которая вне списка.

(Можете распечатать PtrUInt(@p) и PtrUInt(@p^.next) чтобы убедиться, что это две разные ячейки памяти).

В эту процедуру же мы передаем список по ссылке, то есть этот способ удаления вроде бы аналогичен способу, описанному выше, который, в свою очередь, не работает. Как так? Буду рад помощи, заранее спасибо!

Модификатор var делает так, что неявно передаётся указатель на соответствующую область памяти. При вызове DelLast(p^.next) будет передан адрес @p^.next, по которому внутри вызванной функции можно записать новое значение в переменную внешней функции оператором присваивания.

(Распечатайте PtrUInt(@p) и PtrUInt(@p^.next), чтобы убедиться в этом.)

[bormant]

На самом деле алгоритм легко переписать единообразно для первого и последующих элементов с использованием указателя на указатель:

Код: Выделить всё

type
  PNode = ^TNode;
  TNode = record
    next: PNode;
    ...
  end;
var
  L: PNode;  // голова списка
  p: ^PNode;
...
  if L<>nil then begin
    p:=@L; while p^^.next<>nil do p:=@(p^^.next);
    Dispose(p^); p^:=nil;
  end;

[DedFrend]

Я понял, фокус в том, что процедуру
procedure DelLast(var p: list);
нельзя вызывать рекурсивно. Чтобы рекурсия работала, надо, чтобы p была локальной.
Попробуй
procedure DelLast( p: list);
Мне кажется, должно получиться

[Дож]

DedFrend, её можно вызвать рекурсивно и она правильно работает, а если убрать var, то работает неправильно (об этом писал и топикстартер).