Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Языки программирования > Lisp
Перезагрузить страницу Удаление элемента из дерева
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
V55 V55 вне форума
Новичок
 
Сообщений: 4
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 14.05.2009
По умолчанию 14.05.2009, 22:16

Помогите пожалуйста кто-нибудь!!!

Дано дерево, представленное цепными списками. Необходимо удалить заданные элементы. при этом дети элемента переопределяются к его родителю. Корень дерева удалять запрещено.

допустим дано дерево:
5
/ \
6 1
/ \ / \
3 7 8 9

представлено оно должно быть так: ((5 6 3)(6 7)(5 1 8)(1 9))
допустим, надо удалить 1. тогда на выходе должно получиться: ((5 6 3)(6 7)(5 8)(5 9))
Ответить с цитированием
  (#2 (permalink)) Старый
Alexey Dejneka Alexey Dejneka вне форума
Member
 
Сообщений: 451
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 23.11.2004
По умолчанию 15.05.2009, 00:36

Опишите, пожалуйста, более подробно процедуру представления деревьев на Лиспе. Например, как будут представлены такие деревья:
Код:
1                 1
|                 |\
1                 1 1
|\                | |
1 1               1 1
  |
  1
(от корня растет левая ветка из двух узлов; вправо либо от корня, либо от следующего узла отходит ветка еще с двумя узлами; во всех узлах проставлена цифра 1).
Ответить с цитированием
  (#3 (permalink)) Старый
V55 V55 вне форума
Новичок
 
Сообщений: 4
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 14.05.2009
По умолчанию 15.05.2009, 17:17

У меня в задачке все элементы разные должны быть)
Ответить с цитированием
  (#4 (permalink)) Старый
Alexey Dejneka Alexey Dejneka вне форума
Member
 
Сообщений: 451
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 23.11.2004
По умолчанию 16.05.2009, 00:18

Код:
(defun find-item-before (item list)
  (loop for (before x) on list
        when (eql x item)
        return before))

(defun remove-from-tree (item tree)
  (let (parent)
    (mapcan (lambda (branch)
              (cond ((eql (first branch) item)
                     (unless (null (cdr branch))
                       (list (cons parent (cdr branch)))))
                    (t
                     (let ((parent-or-nil (find-item-before item branch)))
                       (cond (parent-or-nil
                              (setq parent parent-or-nil)
                              (list (remove item branch)))
                             (t
                              (list branch)))))))
            tree)))

CL-USER> (remove-from-tree 1 '((5 6 3)(6 7)(5 1 8)(1 9) (5 8 7)))
((5 6 3) (6 7) (5 8) (5 9) (5 8 7))
Ответить с цитированием
  (#5 (permalink)) Старый
V55 V55 вне форума
Новичок
 
Сообщений: 4
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 14.05.2009
По умолчанию 20.05.2009, 22:46

Супер. спасибо)
А можно еще сделать так чтоб несколько элементов можно было удалять?
Ответить с цитированием
Ads.
Ads
Ответ

Опции темы
Опции просмотра

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

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Удаление последнего элемента списка [С++] Pblcb С/С++ 0 01.04.2012 17:06
Удаление предпоследнего элемента в списке Samael Lisp 5 09.05.2011 17:24
Удаление элемента из массива alyonka89 Delphi 2 17.08.2009 21:03
Удаление элемента с заданным номером и число вхождений заданного элемента imported_Lisa_D Lisp 21 16.04.2009 15:06
Нужно написать функцию, определяющую величину наибольшего элемента дерева yyyzz Delphi 1 07.04.2009 13:54
Поиск максимального элемента дерева Васька Prolog 3 19.10.2008 17:23
удаление из AVL дерева lexamac Prolog 0 20.05.2008 22:50
Списки: удаление заданного элемента Art4 Prolog 8 28.12.2006 17:04
Удаление элементов тз дерева UIN С/С++ 3 03.01.2006 11:09
Удаление вершин из дерева Mylene Вопросы начинающих программистов 2 20.04.2005 08:29
Удаление элемента дерева Karp Visual C++ 1 07.04.2004 09:46
Удаление к последних уровней из дерева surrender Prolog 21 16.01.2004 19:10



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов