Динамические структуры данных, Читаю FAQ и не могу понять... Опции

[Бродяжник]

Бьюсь над созданием списка с возможностью удаления элементов из середины. Вспомнил про FAQ на любимом форуме, полез туда. Читаю:

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

{удаление элемента из середины списка после q^}
Procedure Del (Var q: point);
Var r: point;
Begin
 r:=q^.Next;
 q^.Next:=q^.Next;
 r^.Next:=nil
End;

Как это работает?! :o

[Altair]

опечатка...
вместо

q^.Next:=q^.Next;

надо конечно

 q^.Next:=q^.Next^.next;

если что, вот тебе тест ...

(здесь модуль strlist это из FAQ"a, только с эмулированием шаблонов )

Uses wincrt,strlist;
var
 l:tlist;

Procedure Del (Var q: Tlist);
Var r: Tlist;
Begin
 r:=q^.Next;
 q^.Next:=q^.Next^.next;
 r^.Next:=nil
End;

Function getp(l:tlist):tlist;
begin
 while (l<>nil) and(l^.info<>'3dffg') do l:=l^.next;
 getp:=l;
end;
procedure listprint(l:tlist);
begin
 while (l<>nil) do
  begin
  writeln(l^.info);
  l:=l^.next;
  end;
end;
var
 d:tlist;
begin
 BListinit(l);
 BListAddFirst(l,'1dfg');
 BListAddFirst(l,'2abc');
 BListAddFirst(l,'3dffg');
 BListAddFirst(l,'4dsfdfg');
 writeln('---------1-----------');
 listprint(l);
 d:=getp(l);
 del(d);
  writeln('---------2-----------');
 listprint(l);

end.

UNIT StrList;
INTERFACE
Type
 TElem = string;

 TList = ^TNode;
 TNode = record
	  Info: TElem;
	  Next: TList
	 end;
{$I List.pas}

end.

list.pas - из FAQ'a

{------------------------------------------------------------------|
| процедуры и функции у которых в названии B -без заглавного звена |
| процедуры и функции у которых в названии Z - c заглавным звеном  |
|------------------------------------------------------------------}
{Инициализация}
Procedure BListInit(var L: TList);
{Добавление в голову}
Procedure BListAddFirst(var L: TList; E:TElem);
{del}
Function  BListDelEleml(var L: TList; E: TElem): boolean;
{max}
Function  BListGetMax(A: TList): string;
Function  BListGetFio(A: TList;s:string): string;
{Добавление в хвост}
Procedure BListAddLast(var L: TList; E: TElem);
{переворачивание}
Procedure BListInvert(var L: TList);
{Очистка}
Procedure ListClear ( var L: TList );


{------------------------------------------------------------}
IMPLEMENTATION
{ 1. Инициализация списка }
{Список без заглавного звена}
Procedure BListInit(var L: TList);
begin
 L:= nil
end;
{2. Добавление элемента в начало списка}
Procedure BListAddFirst(var L: TList; E:TElem);
var
 N: TList;
Begin
 new(N);
 N^.Info:=E;
 N^.Next:=L;
 L:=N
end;


{обавление элемента в конец списка }
{ Список без заглавного звена }
procedure  BListAddLast(var L: TList; E: TElem);
var
 N: TList; { добавляемое звено списка }
 { вспомогательный указатель для }
 { поиска последнего элемента списка }
 P: TList;
Begin
 new(N);
 N^.Info :=E;
 N^.Next :=nil;
 if L= nil then L:=N else
 begin
  { поиск последнего элемента списка }
  P:=L;
  while P^.Next <> nil do P:=P^.Next;
  {добавление в список нового звена }
  P^.Next:=N
 end
End;

{ 4. Удаление первого вхождения элемента Е в список L }
{ Результат функции: }
{ true - элемент найден и удален }
{ false - злемент в списке не найден }
{ Список без заглавного звена. Решение 1 }
function BListDelEleml(var L: TList; E: TElem): boolean;
var
 N: TList; { указатель на удаляемое из списка звено }
 { вспомогательный указатель для поиска звена списка.}
 { предшествующего удаляемому }
 P: TList;
 { признак: найден ли элемент Е }
 { в списке ? }
 found: boolean;
begin
 found:=false;
 if L<>nil then
 { если список не пуст }
 if L^.Info =E then { если первое звено является удаляемым }
 begin
  found:=true;
  { запоминаем указатель на }
  { удаляемое звено }
  N:=L;
  L:=L^.Next; { удаляем звено из списщ-}
  dispose(N) { освобождаем память }
 end else
 begin
  { ищем звено. предшествующее удаляемому}
  P:=L;
  while not found and (P^.Next <> nil) do
  if P^.Next^.Info = E then found:=true
  else P := P^.Next;
  if found then
  { если найдено удаляемое звено}
  begin
   { запоминаем указатель }
   { на удаляемое звено }
   N := P^.Next;
   { удаляем звено из списка }
   P^.Next := N^.Next;
   { освобождаем память }
   dispose(N)
  end
 end;
 BListDelEleml:=found
end;

Function  BListGetMax(A: TList): string;
var
 t:telem;
begin
 t:=a^.info; {!!!}
 while A <> nil DO
 begin
   A := A^.Next;
   if a^.info>t then t:=a^.info;
 end;
 BListGetMax:=t;
end;

Function  BListGetFio(A: TList;s:string): string;
begin
 while A <> nil DO
 begin
   A := A^.Next;
   if a^.info=s then blistgetfio:=a^.info;
 end;
end;
{ 5. Переворот списка }
{ Список без заглавного звена }
procedure BListInvert(var L: TList);
var
 H: TList; { вспомогательный указатель }
 P: TList; { указатель на обработанный элемент списка }
begin
 P := nil;
 while L<>nil do
 begin
  {( запоминаем указатель на следующий )}
  H := L^.Next;
  {( теперь следующий за текущим будет звено Р )}
  L^.Next := P;
  {( текущий становится предыдущим )}
  {( для следующего шага )}
  P := L;
  {( переиещаеися к следующеиу элементу списка )}
  L:=H
 end;
 L :=P { самый последний становится первым }
end;

{ 7. Удаление всех элементов списка }
procedure ListClear ( var L: TList );
var
 N: TList; { указатель на удаляемое звено списка }
begin
 while L <> nil do
 begin
  N :=L;
  L:=L^.Next;
  dispose(N)
 end
end;

[hiv]

Лучше так сделать:

{удаление элемента из середины списка после q^}
Procedure Del (Var q: point);
Var r: point;
Begin
 r:=q^.Next;
 if r<>nil then 
 begin
   q^.Next:=r^.Next;
   Dispose( r );
 end;
End;

Сообщение отредактировано: hiv - 7.06.2005 12:53

[volvo]

А можно вопрос? ЗАЧЕМ??? Перебор какой-то получается, "удалить следующий за данным элемент" ... Ну, так удаляйте:

Procedure DeleteAfter(Var q: point);
begin
  DeleteItem(q^.next);
end;

[Бродяжник]

Спасибо! А то я в себе засомневался: вдруг я вижу ошибку там, где ее нет? <_<
2 Volvo
Код для DeleteItem можно глянуть?

Сообщение отредактировано: Бродяжник - 7.06.2005 13:15

[volvo]

Код для DeleteItem можно глянуть?

Можно конечно, только вот для НЕ ООП-списка это не пойдет. Я передаю в DeleteItem указатель на Item, который нужно удалить, и забываю про него, меня не интересует, что с этим указателем будет дальше... Подробности - здесь: ООП - Односвязный список (list.rar)

[Бродяжник]

Спасибо за подсказки... но в конце концов я, наверное, сделаю что-то вроде периодической "сборки мусора", в ходе которой "живые" элементы списка будут объединяться в новый список, а старый будет удаляться.