Métodos de Programação II
Este trabalho deve ser realizado por grupos com um máximo de três alunos. O trabalho deve ser entregue até ao dia 31 de Março na recepção do Departamento de Informática e nele deve constar a listagem do código escrito assim como um pequeno relatório em cuja primeira página deverá constar a identificação dos membros do grupo (número; nome e curso).
Este trabalho prático vem no seguimento do primeiro trabalho realizado na disciplina de Métodos de Programação I. Nesse trabalho foi construído um módulo de árvores binárias na linguagem Haskell. Vamos agora implementar um módulo de árvores só que, desta vez, em C. Apresenta-se o enunciado do trabalho da disciplina de Método de Programação I em apêndice onde são contextualizadas as funções que se pretendem codificar. Uma possível resolução também é apresentada.
O objectivo deste trabalho pode então ser expresso em termos muito simples: pretende-se realizar um módulo C com funcionalidade análoga ao módulo apresentado para Haskell . Por ``funcionalidade análoga'' entende-se uma funcionalidade devidamente ajustada ao paradigma imperativo. A título de exemplo: quando em Haskell tornamos o tipo de árvores instância da classe Show é evidente que não existe correspondente directo em C. No entanto, no módulo realizado deverá existir uma função que permita visualizar o conteúdo de uma árvore (afinal a razão pela qual a referida instância foi requerida).
No relatório pode também referir em que medida foi possível adoptar as codificações fornecidas como ``modelo'' das realizadas (e, quando não foi, que justificação encontra para esse facto).
(COMENTÁRIO: é sabido que a recursividade das funções de travessia de árvores binárias não pode ser transformada (directamente) num ciclo - o padrão dessa recursividade não é linear. O que é necessário, então, é codificar na nossa própria função o mecanismo implementado pela recursividade, i.e. gerir localmente uma Stack).
As árvores binárias são uma estrutura de dados já estudada no decorrer deste curso.
Pretende-se realizar um módulo de árvores binárias em C. Para isso vamos considerar o seguinte fragmento de código.
module ArvBin where import List data ArvBin a = Vazia | Nodo a (ArvBin a) (ArvBin a) deriving Eq vazia :: ArvBin a -> Bool vazia Vazia = True vazia _ = False esq :: ArvBin a -> ArvBin a esq (Nodo x y z) = y dir :: ArvBin a -> ArvBin a dir (Nodo x y z) = z val :: ArvBin a -> a val (Nodo x y z) = x
Pretende-se agora completar código deste módulo por forma a incluir a funcionalidade descrita abaixo.
(Nodo 5 (Nodo 3 (Nodo 1 Vazia Vazia) (Nodo 4 Vazia Vazia)) Vazia)como:
{5:{3:{1:_|_}|{4:_|_}}|_}
Vamos designar por traço de uma árvore um percurso da raiz até uma sub-árvore vazia. Assim, e a título de exemplo, a árvore
(Nodo 5 (Nodo 3 (Nodo 1 Vazia Vazia) (Nodo 4 Vazia Vazia)) Vazia)possui como traços as sequências [5,3,1]; [5,3,4] e [5].
Um das principais motivos para a utilização das árvores binárias é o facto de permitirem uma pesquisa mais eficiente. Para isso devem ser construídas de uma forma particular: em qualquer nodo, os valores armazenados na sub-árvore esquerda devem ser inferiores ao valor desse nodo e os armazenados na sub-árvore direita superiores. Nesse caso, para pesquisar um elemento numa árvore, necessitamos de procurar unicamente uma das sub-árvores o que torna o processo de busca mais eficiente. Em Haskell podemos definir essa função como
elemAB :: (Ord a) => a -> ArvBin a -> Bool
elemAB x Vazia = False
elemAB x (Nodo v e d) = x==v || if x<v
then (elemAB x e)
else (elemAB x d)
Uma árvore que satisfaça o invariante descrito acima designa-se por "árvore binária de procura".
Uma estrutura de dados também implementada em árvores binárias é a "Heap". Uma "Heap" é uma árvore binária onde cada traço está ordenado de forma crescente.
As árvores binárias podem ser generalizadas retirando a restrição de existirem exactamente duas sub-árvores em cada nodo não vazio. Uma árvore genérica é então uma árvore com um número arbitrário de sub-árvores.
data ArvGen a = AGVazia | AGNodo a [ArvGen a]
module ArvBin where
import List
data ArvBin a = Vazia | Nodo a (ArvBin a) (ArvBin a) deriving Eq
vazia :: ArvBin a -> Bool
vazia Vazia = True
vazia _ = False
esq :: ArvBin a -> ArvBin a
esq (Nodo x y z) = y
dir :: ArvBin a -> ArvBin a
dir (Nodo x y z) = z
val :: ArvBin a -> a
val (Nodo x y z) = x
peso :: ArvBin a -> Int
peso Vazia = 0
peso (Nodo _ e d) = max (peso e) (peso d)
instance Show a => Show (ArvBin a) where
showsPrec _ Vazia = showString "_"
showsPrec _ (Nodo x e d) = showString "{" . (shows x) .
showString ":" . (shows e) .
showString "|" . (shows d) .
showString "}"
in_order :: ArvBin a -> [a]
in_order Vazia = []
in_order (Nodo x e d) = (in_order e) ++ [x] ++ (in_order d)
pre_order :: ArvBin a -> [a]
pre_order Vazia = []
pre_order (Nodo x e d) = x:(pre_order e) ++ (pre_order d)
pos_order :: ArvBin a -> [a]
pos_order Vazia = []
pos_order (Nodo x e d) = (pos_order e) ++ (pos_order d) ++ [x]
traces :: ArvBin a -> [[a]]
traces Vazia = [[]]
traces (Nodo x Vazia Vazia) = [[x]]
traces (Nodo x e d) = map (x:) ((traces e)++(traces d))
{- Árvores Binárias de Procura -}
elemAB :: (Ord a) => a -> ArvBin a -> Bool
elemAB x Vazia = False
elemAB x (Nodo v e d) = x==v || if x<v
then (elemAB x e)
else (elemAB x d)
listOrd :: (Ord a) => [a] -> Bool
listOrd [] = True
listOrd l = and (zipWith (<=) l (tail l))
checkAB :: (Ord a) => ArvBin a -> Bool
checkAB = listOrd . in_order
balanAB :: ArvBin a -> Bool
balanAB a = let (min,max) = minmax (map length (traces a))
in max-min < 2
where minmax [x] = (x,x)
minmax (x:xs) = let (min,max) = minmax xs
in (if x<min then x else min,
if x>max then x else max)
{- HEAPs -}
checkHeap :: Ord a => ArvBin a -> Bool
checkHeap = and . (map listOrd) . traces
remHeap :: Ord a => a -> ArvBin a -> ArvBin a
remHeap x Vazia = Vazia
remHeap x (Nodo y e d)
| x<y = Nodo y e d
| x>y = Nodo y (remHeap x e) (remHeap x d)
| True = case e of
Vazia -> d
(Nodo ye _ _) -> case d of
Vazia -> e
(Nodo yd _ _) -> if ye<yd
then (Nodo ye
(remHeap ye e)
d)
else (Nodo yd
e
(remHeap yd d))