IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> n-арное двусвязное дерево. Добавление, поиск, удаление., Помогите найти ошибку в удалении.
сообщение
Сообщение #1


Новичок
*

Группа: Пользователи
Сообщений: 24
Пол: Мужской
Реальное имя: Алексей

Репутация: -  0  +


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

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


Прикрепленные файлы
Прикрепленный файл  GENEO.PAS ( 5.94 килобайт ) Кол-во скачиваний: 175
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Гость






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

Первый же PrintList, чему равно CurEl после присваивания
CurEl:= List.Head;
? Переход по нулевому указателю...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Новичок
*

Группа: Пользователи
Сообщений: 24
Пол: Мужской
Реальное имя: Алексей

Репутация: -  0  +


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

Сообщение отредактировано: kramolnic -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Гость






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


Новичок
*

Группа: Пользователи
Сообщений: 24
Пол: Мужской
Реальное имя: Алексей

Репутация: -  0  +


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

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


Прошу прощения,что не вставил проверку if CurEl <> nil then... мой компилер нормально это переживает, я внимания и не обратил...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Гость






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

{ Немного меняем 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, например, возникает ошибка.

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


Эскизы прикрепленных изображений
Прикрепленное изображение
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Новичок
*

Группа: Пользователи
Сообщений: 24
Пол: Мужской
Реальное имя: Алексей

Репутация: -  0  +


Цитата(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;

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

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

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


Прикрепленные файлы
Прикрепленный файл  GENEO1.PAS ( 6.66 килобайт ) Кол-во скачиваний: 155
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 23.09.2020 9:40
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name