Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Языки программирования > Haskell
Перезагрузить страницу Функции работы с бинарными деревьями поиска.
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
RoseAle RoseAle вне форума
Новичок
 
Сообщений: 3
Сказал(а) спасибо: 1
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 27.01.2014
По умолчанию Функции работы с бинарными деревьями поиска. - 28.01.2014, 19:56

Такое задание:
Функции работы с бинарными деревьями поиска. Определите тип
данных, представляющий бинарные деревья поиска. В отличие от
деревьев, представленных в методических указаниях, в деревьях
поиска данные могут находиться не только в листьях, но и в проме-жуточных узлах дерева. Будем использовать деревья для представ-ления ассоциативного массива, сопоставляющие значения ключей
(представляемых как строки) целым числам. Для каждого узла с
некоторым ключом в левом поддереве должны содержаться элемен-ты с меньшими значениями ключа, а в правом — с б ´ ольшими. При
поиске соответствия между строкой и числом необходимо учиты-вать эту информацию, поскольку она позволяет более эффективно
извлекать информацию из дерева. Определите описанный тип дан-ных и следующие функции:
1) add, добавляющую в дерево заданную пару ключа и значения.
2) find, возвращающую число, соответствующее заданной стро-ке.
3) exists, проверяющую, что элемент с заданным ключом со-держится в дереве.
4) toList, преобразующая заданное дерево поиска в список,
упорядоченный по значениям ключей.

честно попыталась покопаться сама,но увы,нашла на вашем же форуме вариант решения,признаюсь честно
data STree = Tip | Bin (String, Int) STree STree deriving Show

add (k, v) Tip = Bin (k, v) Tip Tip
add (k, v)(Bin (k1, v1) l r) =
if k > k1 then Bin (k1, v1) l (add (k, v) r)
else Bin (k1, v1) (add (k, v) l) r

find' k Tip = Nothing
find' k (Bin (k1, v1) l r)
| k == k1 = Just v1
| otherwise = find' k (if k > k1 then r else l)

exist k = isJust . find k

toList' Tip = []
toList'( Bin (_, v1) l r) = concat [toList' l, [v1], toList' r]

но программа выдает ошибку
1.hs:4:31: lexical error (UTF-8 decoding error)

Очень нужна помощь,буду очень благодарна,особенно если поможите и с вводом
Ответить с цитированием
  (#2 (permalink)) Старый
calabi-yau calabi-yau вне форума
Member
 
Сообщений: 338
Сказал(а) спасибо: 0
Поблагодарили 10 раз(а) в 10 сообщениях
Регистрация: 28.09.2009
По умолчанию 28.01.2014, 21:26

Цитата:
Сообщение от RoseAle Посмотреть сообщение
но программа выдает ошибку
Не в той кодировке сохраняете (можно, например, в UTF-8) и сразу внесем мелкие исправления в код:
haskell Код:
import Data.Maybe

data STree = Tip | Bin (String, Int) STree STree deriving Show

add (k, v) Tip = Bin (k, v) Tip Tip
add (k, v)(Bin (k1, v1) l r) =
  if k > k1 then Bin (k1, v1) l (add (k, v) r)
  else Bin (k1, v1) (add (k, v) l) r

find k Tip = Nothing
find k (Bin (k1, v1) l r)
  | k == k1 = Just v1
  | otherwise = find k (if k > k1 then r else l)

exist k = isJust . find k

toList Tip = []
toList( Bin (_, v1) l r) = concat [toList l, [v1], toList r]


Don't fear the Monad
Ответить с цитированием
Пользователь сказал cпасибо:
RoseAle (29.01.2014)
  (#3 (permalink)) Старый
RoseAle RoseAle вне форума
Новичок
 
Сообщений: 3
Сказал(а) спасибо: 1
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 27.01.2014
По умолчанию 28.01.2014, 23:04

Заработало,спасибо большое,может ещё подскажите как вводить значения?
Ответить с цитированием
  (#4 (permalink)) Старый
beroal beroal вне форума
Member
 
Сообщений: 108
Сказал(а) спасибо: 3
Поблагодарили 4 раз(а) в 4 сообщениях
Регистрация: 13.12.2002
По умолчанию 29.01.2014, 11:42

Слушайте, делайте домашние задания самостоятельно. Достали уже.
Ответить с цитированием
Ads
Ответ

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

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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
помогите написать процедуру бинарными вставками salwator Pascal 0 12.12.2010 13:50
помогите,пожалуйста, написать процедуру бинарными вставками salwator Pascal 0 10.12.2010 22:12
Функции для работы с памятью imported_nina Haskell 2 21.05.2010 18:03
Реализовать итерационную версию функции поиска tree-search пээмчик Lisp 8 27.04.2010 20:15
Cортировка данных на С++ для поиска функции Liliput Вопросы начинающих программистов 0 26.03.2007 18:20
функции работы со строками Pyshkin Delphi 7 28.09.2006 21:18
Как понять принцип работы функции legrandmetre С/С++ 5 27.11.2005 16:28
API-функции для работы с MathCAD Павел Безяев Visual C++ 9 16.02.2005 18:45
Функции работы с таймером Vasis WinAPI 2 18.11.2004 17:32
Написание функции для поиска значения imported_Irinka Lisp 2 25.03.2004 14:38
Функции для работы с com портом Anonymous WinAPI 1 26.11.2003 12:18
Какие функции имеются под MFC или API-функции для работы с Hint Anonymous Visual C++ 1 12.10.2003 00:15



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