Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Задачи _ n-арное двусвязное дерево. Добавление, поиск, удаление.

Автор: kramolnic 16.05.2007 2:05

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


Прикрепленные файлы
Прикрепленный файл  GENEO.PAS ( 5.94 килобайт ) Кол-во скачиваний: 284

Автор: volvo 16.05.2007 2:40

Цитата
Сначала программа выводит дерево.
А ничего, что она это делает некорректно?

Первый же PrintList, чему равно CurEl после присваивания
CurEl:= List.Head;
? Переход по нулевому указателю...

Автор: kramolnic 16.05.2007 2:52

Цитата(volvo @ 15.05.2007 23:40) *

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

Первый же 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); ? Ну да, это немного некорректно... или это настолько критично? Я чего-то не понимаю? вроде бы вывод ДО удаления работает как надо. Не работает удаление, или я не прав? кстати,в процедуре удаления еще один шаг не сделан - надо удалить ссылку на удаляемый элемент из списка его родителя. Но это все равно не должно вроде повлиять на результат.
Поправьте, если я в чем-то заблуждаюсь...

Автор: volvo 16.05.2007 3:00

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

k:= ABS(CurEl^.Children^.Level);
, ибо CurEl указывает в никуда... При таком раскладе проблематично проверить, как работает удаление дерева...

Автор: kramolnic 16.05.2007 3:02

Цитата(volvo @ 16.05.2007 0:00) *

Понимаешь в чем дело... Тот компилятор, которым пользуюсь я завершает выполнение программы (Segmentation Fault) еще в строке
k:= ABS(CurEl^.Children^.Level);
, ибо CurEl указывает в никуда... При таком раскладе проблематично проверить, как работает удаление дерева...


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

Автор: volvo 16.05.2007 4:51

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

{ Немного меняем 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, и то, зачем искали предшествующий удаляемому элемент - просто делаем так, чтобы указатель "перескакивал" его, не замечал, попутно возвращая память...

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

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


Эскизы прикрепленных изображений
Прикрепленное изображение

Автор: kramolnic 21.05.2007 2:39

Цитата(volvo @ 16.05.2007 1:51) *

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

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


Прошу прощения, но тема все еще актуальна. Долго мучался с компилятором, потом на листике еще раз прорисовал работу каждой процедуры - ошибок вроде нет mega_chok.gif Программа как и в прошлый раз вываливается при попытке обхода дерева после удаления какого-либо узла. Удаление почему-то работает нормально только если удалять только последнюю ветку.
например в таком дереве:
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;

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

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


Прикрепленные файлы
Прикрепленный файл  GENEO1.PAS ( 6.66 килобайт ) Кол-во скачиваний: 247