OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Четверг, 28 Март, 2024 19:42

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 11 ] 
Автор Сообщение
СообщениеДобавлено: Четверг, 14 Февраль, 2008 15:31 

Зарегистрирован: Четверг, 14 Февраль, 2008 15:12
Сообщения: 6
Здравствуйте. Я начинаю изучать программирование и Компонентный Паскаль показался мне очень интересным языком. Но есть трудности организационного характера.
Например, я хочу сделать модуль, реализующий Бинарные деревья. Пишу интерфейс:
Код:
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 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9459
Откуда: Россия, Орёл
Посмотрите здесь книгу Вирта "Алгоритмы и структуры данных", поиском по странице. Там превосходно описана работа с основными динамич. структурами. (По Вашему примеру - хорошая рекурсия с деревьями делается при использовании VAR-параметра - т.е. очередная активация процедуры может менять не только подузлы, но и сам переданный ей узел).


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 14 Февраль, 2008 16:13 

Зарегистрирован: Четверг, 14 Февраль, 2008 15:12
Сообщения: 6
Эта книга у меня есть, надо бы почитать повнимательнее.
Но мне всё равно не ясно. Вот здесь:
Код:
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 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9459
Откуда: Россия, Орёл
Ну так у рекурсии должен быть конец - вот конец и наступает, когда t.left = NIL.
Схема такая - определяем, куда вставлять относительно текущего узла: направо или налево.
Далее проверяем - IF left (right) # NIL THEN делегируем вставку им left (right) .Insert(tree),
а ELSE t.left (right) := tree END.

Если NIL, значит работу рекурсивно делегировать уже некому, выполняем сами :-)

По поводу VAR - это при некоторых рекурсивных алгоритмах на деревьях процедура может таким образом заменять переданный ей узел (указатель). Там у Вирта есть...


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 15 Февраль, 2008 07:41 

Зарегистрирован: Четверг, 14 Февраль, 2008 15:12
Сообщения: 6
Эко ж я под вечер-то наворотил. Всё и правда на самом деле проще. Попробую переписать. Спасибо.
Но есть и положительный момент: практика работы со стеком :D . Когда б ещё сподобился?...


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 15 Февраль, 2008 08:12 

Зарегистрирован: Четверг, 14 Февраль, 2008 15:12
Сообщения: 6
С рекурсией и проще, и писать меньше :)
Код:
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 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9459
Откуда: Россия, Орёл
Ох, не ставьте Вы точку с запятой перед END/ELSE - глаз режет :-)


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Суббота, 16 Февраль, 2008 00:33 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8500
Откуда: Троицк, Москва
Илья Ермаков писал(а):
Ох, не ставьте Вы точку с запятой перед END/ELSE - глаз режет :-)


зато строчки переставлять удобно. мне вот надоело ее стирать-добавлять -- пусть режет....


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Суббота, 16 Февраль, 2008 07:38 

Зарегистрирован: Четверг, 14 Февраль, 2008 15:12
Сообщения: 6
Илья Ермаков писал(а):
Ох, не ставьте Вы точку с запятой перед END/ELSE - глаз режет :-)


Привычка, ничего не поделаешь :)
Что-то где-то читывал про "рак точек с запятой". Эх, память моя, память...


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Суббота, 16 Февраль, 2008 10:20 

Зарегистрирован: Понедельник, 28 Ноябрь, 2005 10:28
Сообщения: 1428
А все делать методами тоже привычка?
Хотя, конечно, дело вкуса, как и ";",


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Суббота, 16 Февраль, 2008 10:27 

Зарегистрирован: Четверг, 14 Февраль, 2008 15:12
Сообщения: 6
Методы - это для меня ново и интересно. Очень хочется поизвращаться:)
Сейчас как раз переделываю, чтоб все было как в книжках Вирта.


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 11 ] 

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 2


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Вся информация, размещаемая участниками на конференции (тексты сообщений, вложения и пр.) © 2005-2024, участники конференции «OberonCore», если специально не оговорено иное.
Администрация не несет ответственности за мнения, стиль и достоверность высказываний участников, равно как и за безопасность материалов, предоставляемых участниками во вложениях.
Без разрешения участников и ссылки на конференцию «OberonCore» любое воспроизведение и/или копирование высказываний полностью и/или по частям запрещено.
Powered by phpBB® Forum Software © phpBB Group
Русская поддержка phpBB