Tipos de dados abstractos: utilização de pacotes

Considere o tipo de dados das árvores de pesquisa de registos especificado anteriormente, implementado num pacote trees.m que pode obter através da página da disciplina.  Nos exercícios que se segue, deve utilizar apenas a especificação desse tipo de dados seguindo a informação fornecida pelo pacote.

Apresentação do pacote trees.m

?trees

?treeQ

?void

?join

?voidQ

?root

?left

?right

?searchkey

?findreg

?delreg

?addreg

Nos exemplos seguintes, t denota a árvore addreg[addreg[addreg[addreg[addreg[void,a,5],b,3],c,7],d,1],b,3]

Defina uma função listareg que receba uma árvore de pesquisa de registos e devolva a lista dos conteúdos dos registos que lá ocorrem, ordenada por chave.

listareg[t]

Defina uma função registosQ que recebe uma lista de chaves w e uma árvore de pesquisa de registos t e verifica se todas as chaves em w ocorrem em t.

registosQ[{1, 2, 3}, t]

registosQ[{3, 5, 7}, t]

Defina uma função registos que recebe uma lista de chaves w e uma árvore de pesquisa de registos t e devolve a lista dos conteúdos dos registos correspondentes às chaves em w.

registos[{1, 2, 3}, t]

registos[{3, 5, 7}, t]

Considere o tipo de dados das pilhas de naturais especificado anteriormente, implementado num pacote stacks2.m que pode obter através da página da disciplina.  Nos exercícios que se segue, deve utilizar apenas a especificação desse tipo de dados seguindo a informação fornecida pelo pacote.

Apresentação do pacote stacks2.m

?stacks2

?stackQ

?new

?top

?pop

?push

Defina uma função soma que receba uma pilha de naturais e devolva a soma de todos os seus elementos.

soma[push[3, push[2, push[4, new]]]]

Defina uma função fazarvore que receba uma pilha de pilhas de naturais e devolva a árvore de pesquisa de registos contendo essas mesmas pilhas; a chave associada à pilha p é a soma de todos os elementos de p.

p1 = push[2, push[1, new]];
p2 = push[5, new];
p3 = push[4, push[0, new]];

arv1 = fazarvore[push[p1, push[p2, push[p3, new]]]];

top[findreg[arv1, 3]]

pop[findreg[arv1, 5]] == new

Defina uma função geraarvore que receba como argumentos duas pilhas de naturais com o mesmo tamanho e devolva a árvore de pesquisa de registos que se obtém considerando que cada elemento da primeira pilha é o conteúdo dum registo cuja chave é o elemento correspondente da segunda pilha.  Ignore elementos que sobrem em qualquer das pilhas.

arv2 = 
        geraarvore[push[2, push[3, push[5, new]]], 
          push[4, push[0, push[2, new]]]];

findreg[arv2, 4]

findreg[arv2, 0]

findreg[arv2, 2]

Defina uma função empilha que recebe duas pilhas e coloca a segunda em cima da primeira.

empilha[push[2, push[3, new]], push[4, push[5, new]]] == 
      push[4, push[5, push[2, push[3, new]]]]

Defina uma função lindapilha que receba uma árvore de pesquisa de registos cujos registos são números naturais e devolva a pilha dos conteúdos dos registos que ocorrem na árvore, ordenados pela sua chave (com o registo correspondente à menor chave no fundo).

p = lindapilha[t];

top[p]

top[pop[p]]

top[pop[pop[p]]]

top[pop[pop[pop[p]]]]

top[pop[pop[pop[pop[p]]]]]

pop[pop[pop[pop[pop[p]]]]] == new

E para terminar note que a implementação das pilhas utilizada NÃO é a usual sobre listas.

push[2, push[3, push[4, new]]]

push[39, push[47, push[2, new]]]

p