n-арное двусвязное дерево. Добавление, поиск, удаление., Помогите найти ошибку в удалении. Опции

[kramolnic]

Помогите, пожалуйста, найти ошибку в моей программе.
Сделал добавление и рекурсивный вывод, однако удаление не работает как надо. Если создать дерево, а потом скомандовать удалить элемент, то стираются все его дочерние элементы (освобождается выделенная под них память), однако при распечатке он видит удаленные элементы!
Немного о программе. Дерево реализовано так, что в каждом узле (персона, TPerson) находится информация о человеке (PersonData), ссылка на его родителя (Parent: PPerson) и список (TList) ссылок на дочерние элементы (каждый из которых также TPerson). Добавление производится по номеру элемента в индексном списке (этот список хранится в структуре TTree под именем ItemList). Сначала программа выводит дерево. Для этого сначала очищается ItemList, затем в этот список процедурой IndexTree, производящей рекурсивный обход дерева, упорядоченно заносятся элементы дерева (сверху вниз, как на экране), после чего распечатывается уже список, в котором находится структура дерева. Список ItemList был добавлен для осуществления добавления дочерних элементов по номеру родителя, а также для поиска. Кстати, пытался сначала сделать удаление без рекурсии, используя этот ItemList - результат: Stack Overflow при попытке вывода (вылетает при обходе дерева рекурсией). Видимо, где-то не верно уничтожаются указатели.
В данном файле удаление сделано рекурсивно (процедура Kill), но она работает как я уже описал. Помогите разобраться наконец, а то я уже дня четыре пытаюсь понять, что тут не верно тремя способами удаление делал - два стэк переполняют ПРИ ВЫВОДЕ, а третий работает криво. Кстати, после удаления элементы как надо не добавляются...

Сообщение отредактировано: kramolnic - 15.05.2007 22:08

[volvo]

Сначала программа выводит дерево.

А ничего, что она это делает некорректно?

Первый же PrintList, чему равно CurEl после присваивания

CurEl:= List.Head;

? Переход по нулевому указателю...

[kramolnic]

А ничего, что она это делает некорректно?

Первый же PrintList, чему равно CurEl после присваивания

CurEl:= List.Head;

? Переход по нулевому указателю...

так... а что тут собсно некорректного? PrintList:

Код

procedure PrintList(var List: TList);
var
  CurEl: PListItem;
  i, k, number: integer;
begin
WriteLn('0. Root');
number:= 1;
CurEl:= List.Head;
k:= ABS(CurEl^.Children^.Level);

While CurEl <> nil do
  begin
    Write(' ', number,'.');
      GotoXY(CurEl^.Children^.Level + k + 5, WhereY);
      WriteLn(CurEl^.Children^.PersonData.Name);
    CurEl:= CurEl^.Next;
    inc(number);
  end;
end;

Если лист пустой, то и Head = nil, согласен. Просто цикл While не будет выполнен. А если лист не пустой, то и Head указывает на какой-то элемент. Или имеется в виду k:= ABS(CurEl^.Children^.Level); ? Ну да, это немного некорректно... или это настолько критично? Я чего-то не понимаю? вроде бы вывод ДО удаления работает как надо. Не работает удаление, или я не прав? кстати,в процедуре удаления еще один шаг не сделан - надо удалить ссылку на удаляемый элемент из списка его родителя. Но это все равно не должно вроде повлиять на результат.
Поправьте, если я в чем-то заблуждаюсь...

Сообщение отредактировано: kramolnic - 15.05.2007 22:55

[volvo]

Понимаешь в чем дело... Тот компилятор, которым пользуюсь я завершает выполнение программы (Segmentation Fault) еще в строке

k:= ABS(CurEl^.Children^.Level);

, ибо CurEl указывает в никуда... При таком раскладе проблематично проверить, как работает удаление дерева...

[kramolnic]

Понимаешь в чем дело... Тот компилятор, которым пользуюсь я завершает выполнение программы (Segmentation Fault) еще в строке

k:= ABS(CurEl^.Children^.Level);

, ибо CurEl указывает в никуда... При таком раскладе проблематично проверить, как работает удаление дерева...

Прошу прощения,что не вставил проверку if CurEl <> nil then... мой компилер нормально это переживает, я внимания и не обратил...

[volvo]

Что-то ты там перемудрил по-моему с отображением дерева... Вот, смотри, что я сделал:

{ Немного меняем Kill }
procedure Kill (var tree: TTree; Ref: PPerson);
var curEl: PListItem;
begin
  CurEl:= Ref^.ChildList.Head;
  While CurEl <> nil do begin
    Kill(Tree, CurEl^.Children);
    CurEl:= CurEl^.Next;
  end;
end;

{ и пишем "обертку" к нему для выполнения доп. действий }
procedure Killer (var tree: TTree; var Ref: PPerson);
var p: PListItem;
begin

  p := Ref^.parent^.ChildList.Head;
  while p^.next^.children <> Ref do begin
    p := p^.next;
  end;

  Kill(Tree, Ref);

  p^.next := p^.next^.next;
  dispose(Ref^.ChildList.head);
  dispose(Ref);
  Ref := nil;
end;

Вызываем все это дело так:

var pp: PPerson;

...
WriteLn('What Person do you want to delete? ');
Readln(n);

  pp := FindRef(Tree.ItemList, n); { var-параметр, нельзя напрямую подставлять вызов функции }
  Killer(tree, pp);

  PrintTree(tree);

Понимаешь, в чем идея? при удалении узла просто переходить на его предка, и в Детях предка искать предшествующий удаляемому узел, потом - удаление всех Детей узла твоей процедурой Kill, и то, зачем искали предшествующий удаляемому элемент - просто делаем так, чтобы указатель "перескакивал" его, не замечал, попутно возвращая память...

НО... (опять это вездесущее слово но ) Это срабатывает только тогда, когда удаляется последняя ветка (на приаттаченной картинке - узел №5)... При попытке удалить узел №3, например, возникает ошибка.

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

[kramolnic]

Что-то ты там перемудрил по-моему с отображением дерева...

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

Прошу прощения, но тема все еще актуальна. Долго мучался с компилятором, потом на листике еще раз прорисовал работу каждой процедуры - ошибок вроде нет Программа как и в прошлый раз вываливается при попытке обхода дерева после удаления какого-либо узла. Удаление почему-то работает нормально только если удалять только последнюю ветку.
например в таком дереве:
0. Root
1.-4
2.--3
3.---5
4.----6
5.-----7
6.----8
нормально удалится элемент с номером 3 или с номером 8 и их потомки, но если удалить, например, 4 элемент, то выводится абракадабра или программа завершается без каких-либо предупреждений.
Для проверки ввел процедуру Printer - тупо обходит дерево и распечатывает список элементов. Если удалять "не правильный" элемент, то на месте удаленного элемента выводится какая-то абракадабра. А если элемент "правильный" - все прекрасно удаляется. Теперь вроде ясно, что глючит - удаление из списка. Не ясно, почему. Проверял процедуру удаления элемента из списка - вроде все правильно, хотя я грешу именно на неё:

Код

procedure DeleteElement(var List: TList; ptr: PListItem);
var
  tmp: PListItem;
begin
if List.Head = nil then exit;

if ptr = List.Head then
    List.Head:= ptr^.Next
else
  begin
    tmp:= FindPred(List, ptr);
    tmp^.Next:= ptr^.Next;
  end;

dispose(ptr);
dec(List.Count);
end;

И еще обнаружилась такая странная вещь. Когда я удаляю элемент из дерева (типа TPerson), то список детей, хранящийся в этом элементе, не уничтожается, поэтому пришлось добавить очистку списка дочерних элементов из каждого элемента перед его удалением:

Код

procedure Kill (var tree: TTree; Ref: PPerson);
var curEl: PListItem;
begin
CurEl:= Ref^.ChildList.Head;

While CurEl <> nil do
  begin
    Kill(Tree, CurEl^.PersonRef);
    CurEl:= CurEl^.Next;
  end;

ClearList(Ref^.ChildList);
dispose(Ref);
end;

Не понятно, почему Паскаль не заботится об этом сам?

В приаттаченном файле результаты мучений - максимум, что получилось. Помогите, пожалуйста.. скоро надо сдавать, а у меня уже не осталось вариантов решения проблемы.

Сообщение отредактировано: kramolnic - 20.05.2007 22:45