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

Вопросы программирования на Free Pascal, использования компилятора и утилит.

Модератор: Модераторы

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

Сообщение vladimashev » 03.02.2019 21:47:09

Описание однонаправленного списка:
Код: Выделить всё
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;

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

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

Сообщение iskander » 03.02.2019 22:51:50

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

В этом случае поле next предпоследнего(а после удаления уже последнего) элемента будет указывать в никуда.
iskander
энтузиаст
 
Сообщения: 590
Зарегистрирован: 08.01.2012 18:43:34

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

Сообщение vladimashev » 03.02.2019 22:55:18

iskander, но после dispose я же присваиваю p := nil, и теперь next последнего элемента (бывшего предпоследнего) указывает как раз на р = nil.
vladimashev
незнакомец
 
Сообщения: 3
Зарегистрирован: 16.12.2018 18:08:31

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

Сообщение Дож » 04.02.2019 00:15:32

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), чтобы убедиться в этом.)
Аватара пользователя
Дож
энтузиаст
 
Сообщения: 899
Зарегистрирован: 12.10.2008 16:14:47

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

Сообщение bormant » 05.02.2019 17:27:59

На самом деле алгоритм легко переписать единообразно для первого и последующих элементов с использованием указателя на указатель:
Код: Выделить всё
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;
Аватара пользователя
bormant
постоялец
 
Сообщения: 407
Зарегистрирован: 21.03.2012 11:26:01

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

Сообщение DedFrend » 07.02.2019 19:50:23

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

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

Сообщение Дож » 07.02.2019 21:03:32

DedFrend, её можно вызвать рекурсивно и она правильно работает, а если убрать var, то работает неправильно (об этом писал и топикстартер).
Аватара пользователя
Дож
энтузиаст
 
Сообщения: 899
Зарегистрирован: 12.10.2008 16:14:47


Вернуться в Free Pascal Compiler

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 18

Рейтинг@Mail.ru