OberonCore https://forum.oberoncore.ru/ |
|
нужна помощь: Реализация модуля Бинарное дерево https://forum.oberoncore.ru/viewtopic.php?f=35&t=871 |
Страница 1 из 1 |
Автор: | Fedor [ Четверг, 14 Февраль, 2008 15:31 ] |
Заголовок сообщения: | нужна помощь: Реализация модуля Бинарное дерево |
Здравствуйте. Я начинаю изучать программирование и Компонентный Паскаль показался мне очень интересным языком. Но есть трудности организационного характера. Например, я хочу сделать модуль, реализующий Бинарные деревья. Пишу интерфейс: Код: MODULE TyumsuAbsTree; TYPE Key* = ABSTRACT RECORD END; Tree* = POINTER TO Node; Node* = ABSTRACT RECORD END; OpNode* = PROCEDURE (t: Tree); PROCEDURE (t:Tree) New*(), NEW, ABSTRACT; PROCEDURE (t:Tree) Insert* (new: Tree), NEW, ABSTRACT; PROCEDURE (t:Tree) Delete* (rem: Tree), NEW, ABSTRACT; PROCEDURE (t:Tree) TraverseTree* (Op: OpNode), NEW, ABSTRACT; PROCEDURE (t:Tree) HeigthRec* (): INTEGER, NEW, ABSTRACT; END TyumsuAbsTree. И делаю реализацию в виде бинарного дерева. Вопрос возник тогда, когда пришлось делать рекурсивные процедуры для работы с этим деревом, например пришлось делать нерекурсивную процедуру вставки элемента в дерево: Код: PROCEDURE (t:BTree) Insert*(new: TyumsuAbsTree.Tree); VAR st1, st: Stack;a: INTEGER; t1: BTree; BEGIN NEW(st); NEW(st1); st.StackInit(); st1.StackInit(); a:=0; WITH new: BTree DO (*Проход по дереву с сохранением узлов в стеке*) WHILE t # NIL DO st1.node :=t; IF new.key.id < t.key.id THEN st1.parent := 1; st.Push(st1(Stack)); st1.StackInit(); t := t.right; ELSE st1.parent := 0; st.Push(st1(Stack)); st1.StackInit(); t := t.left; END; END; t := new; (*Раскручивание стека*) WHILE ~st.pEmpty() DO st1 := st.Pop()(Stack); t1 := st1.node; IF st1.parent = 0 THEN st1.StackInit(); t1.left := t; t := t1;(*HALT(2);*) ELSIF st1.parent = 1 THEN st1.StackInit(); INC(a); t1.right := t; t := t1; END; END; END; END Insert; потому, что не получалось сделать t.left.Insert(new), когда t.left = NIL. Я понимаю, что наступаю на грабли, но можно ли все-таки сделать здесь рекурсию? |
Автор: | Илья Ермаков [ Четверг, 14 Февраль, 2008 15:47 ] |
Заголовок сообщения: | Re: нужна помощь: Реализация модуля Бинарное дерево |
Посмотрите здесь книгу Вирта "Алгоритмы и структуры данных", поиском по странице. Там превосходно описана работа с основными динамич. структурами. (По Вашему примеру - хорошая рекурсия с деревьями делается при использовании VAR-параметра - т.е. очередная активация процедуры может менять не только подузлы, но и сам переданный ей узел). |
Автор: | Fedor [ Четверг, 14 Февраль, 2008 16:13 ] |
Заголовок сообщения: | Re: нужна помощь: Реализация модуля Бинарное дерево |
Эта книга у меня есть, надо бы почитать повнимательнее. Но мне всё равно не ясно. Вот здесь: Код: PROCEDURE (t: BTree)Insert(new: TyumsuAbsTree.Tree); BEGIN WHILE t # NIL DO WITH new: BTree DO IF new.key < t.key THEN t.left.Insert(new); ................................. END; END; END; END Insert; Когда мы дойдем до последней вершины t.left будет NIL, и, соответственно, у него не будет метода Insert. При попытке обратиться к t.left.Insert() будет вызвано исключение. Как делается рекурсия в случае объектов? Про VAR параметр, к сожалению, не совсем понял... |
Автор: | Илья Ермаков [ Четверг, 14 Февраль, 2008 18:03 ] |
Заголовок сообщения: | Re: нужна помощь: Реализация модуля Бинарное дерево |
Ну так у рекурсии должен быть конец - вот конец и наступает, когда t.left = NIL. Схема такая - определяем, куда вставлять относительно текущего узла: направо или налево. Далее проверяем - IF left (right) # NIL THEN делегируем вставку им left (right) .Insert(tree), а ELSE t.left (right) := tree END. Если NIL, значит работу рекурсивно делегировать уже некому, выполняем сами По поводу VAR - это при некоторых рекурсивных алгоритмах на деревьях процедура может таким образом заменять переданный ей узел (указатель). Там у Вирта есть... |
Автор: | Fedor [ Пятница, 15 Февраль, 2008 07:41 ] |
Заголовок сообщения: | Re: нужна помощь: Реализация модуля Бинарное дерево |
Эко ж я под вечер-то наворотил. Всё и правда на самом деле проще. Попробую переписать. Спасибо. Но есть и положительный момент: практика работы со стеком . Когда б ещё сподобился?... |
Автор: | Fedor [ Пятница, 15 Февраль, 2008 08:12 ] |
Заголовок сообщения: | Re: нужна помощь: Реализация модуля Бинарное дерево |
С рекурсией и проще, и писать меньше Код: PROCEDURE (t:BTree) Insert*(new: TyumsuAbsTree.Tree);
BEGIN WITH new: BTree DO IF new.key.id < t.key.id THEN IF t.left # NIL THEN t.left.Insert(new); ELSE t.left := new END; ELSIF new.key.id > t.key.id THEN IF t.right # NIL THEN t.right.Insert(new); ELSE t.right := new END; END; END; END Insert; |
Автор: | Илья Ермаков [ Пятница, 15 Февраль, 2008 12:13 ] |
Заголовок сообщения: | Re: нужна помощь: Реализация модуля Бинарное дерево |
Ох, не ставьте Вы точку с запятой перед END/ELSE - глаз режет |
Автор: | Info21 [ Суббота, 16 Февраль, 2008 00:33 ] |
Заголовок сообщения: | Re: нужна помощь: Реализация модуля Бинарное дерево |
Илья Ермаков писал(а): Ох, не ставьте Вы точку с запятой перед END/ELSE - глаз режет зато строчки переставлять удобно. мне вот надоело ее стирать-добавлять -- пусть режет.... |
Автор: | Fedor [ Суббота, 16 Февраль, 2008 07:38 ] |
Заголовок сообщения: | Re: нужна помощь: Реализация модуля Бинарное дерево |
Илья Ермаков писал(а): Ох, не ставьте Вы точку с запятой перед END/ELSE - глаз режет Привычка, ничего не поделаешь Что-то где-то читывал про "рак точек с запятой". Эх, память моя, память... |
Автор: | Trurl [ Суббота, 16 Февраль, 2008 10:20 ] |
Заголовок сообщения: | Re: нужна помощь: Реализация модуля Бинарное дерево |
А все делать методами тоже привычка? Хотя, конечно, дело вкуса, как и ";", |
Автор: | Fedor [ Суббота, 16 Февраль, 2008 10:27 ] |
Заголовок сообщения: | Re: нужна помощь: Реализация модуля Бинарное дерево |
Методы - это для меня ново и интересно. Очень хочется поизвращаться:) Сейчас как раз переделываю, чтоб все было как в книжках Вирта. |
Страница 1 из 1 | Часовой пояс: UTC + 3 часа |
Powered by phpBB® Forum Software © phpBB Group https://www.phpbb.com/ |