{"id":1376,"date":"2021-01-17T16:42:07","date_gmt":"2021-01-17T18:42:07","guid":{"rendered":"http:\/\/web.inf.ufpr.br\/didonet\/?page_id=1376"},"modified":"2021-10-01T10:52:25","modified_gmt":"2021-10-01T13:52:25","slug":"ci1057-ere-trabalho-2","status":"publish","type":"page","link":"https:\/\/web.inf.ufpr.br\/didonet\/ci1057-ere-trabalho-2\/","title":{"rendered":"CI1057 – ERE – Trabalho 2"},"content":{"rendered":"\n

TRABALHO CI1057<\/span><\/h2>\n

IMPLEMENTA\u00c7\u00c3O DE \u00c1RVORE BIN\u00c1RIA A, com chave definida por uma \u00c1RVORE BIN\u00c1RIA B<\/span><\/h2>\n

O objetivo do trabalho \u00e9 a implementa\u00e7\u00e3o das rotinas de manipula\u00e7\u00e3o de uma \u00e1rvore bin\u00e1ria A, com chave definida por uma \u00e1rvore bin\u00e1ria B. A chave da \u00e1rvore bin\u00e1ria A ser\u00e1 uma outra \u00e1rvore bin\u00e1ria secund\u00e1ria B. Isto \u00e9, dever\u00e1 suportar 1 \u00e1rvore bin\u00e1rias principal, e N \u00e1rvores bin\u00e1rias B, sendo N igual ao n\u00famero de n\u00f3s da \u00e1rvore A. A ordena\u00e7\u00e3o da \u00e1rvore principal ser\u00e1 dada atrav\u00e9s da soma dos valores dos n\u00f3s da \u00e1rvore secund\u00e1ria.<\/span><\/p>\n

ESPECIFICA\u00c7\u00c3O DETALHADA:<\/span><\/h2>\n

\u00c1RVORE A (PRINCIPAL)<\/span><\/h3>\n

ESTRUTURA DE DADOS<\/span><\/h4>\n

Dever\u00e1 conter 1 ponteiro para esquerda, 1 para direita, 1 ponteiro para o pai, e um ponteiro para a chave. Este ponteiro ser\u00e1 do tipo da \u00e1rvore B (secund\u00e1ria).<\/span><\/p>\n

FUNCIONALIDADES<\/span><\/h4>\n

Dever\u00e1 conter fun\u00e7\u00f5es de manipula\u00e7\u00e3o: 1-busca, 2-inclus\u00e3o, 3-exclus\u00e3o e 4-impress\u00e3o em ordem, em formato de sa\u00edda especificado abaixo. A chave de busca, inclus\u00e3o e exclus\u00e3o ser\u00e1 dada atrav\u00e9s de uma \u00e1rvore B passada como par\u00e2metro (secund\u00e1ria).<\/span><\/p>\n

Uma aplica\u00e7\u00e3o dever\u00e1 ser implementada para usar as fun\u00e7\u00f5es de manipula\u00e7\u00e3o da \u00e1rvore. Esta aplica\u00e7\u00e3o ser\u00e1 um programa que recebe instru\u00e7\u00f5es textuais e as executa, gerando uma resposta. Neste programa a \u00e1rvore inicialmente est\u00e1 vazia, a cada comando a \u00e1rvore \u00e9 modificada, e ao final do arquivo (ou comandos) de entrada o programa termina.<\/span><\/p>\n

\u00c1RVORE B (SECUND\u00c1RIA)<\/span><\/h3>\n

ESTRUTURA DE DADOS<\/span><\/h4>\n

Dever\u00e1 conter 1 ponteiro para esquerda, 1 para direita e um inteiro armazenando a chave (o ponteiro para o pai \u00e9 opcional).<\/span><\/p>\n

FUNCIONALIDADES<\/span><\/h4>\n

Esta \u00e1rvore dever\u00e1 ter uma fun\u00e7\u00e3o de 1-cria\u00e7\u00e3o atrav\u00e9s de entrada especificada, 2-impress\u00e3o em ordem.<\/span><\/p>\n

ENTRADA:<\/span><\/h2>\n

A entrada deve conter comandos. Os comandos s\u00e3o i (inser\u00e7\u00e3o), b, (busca) e r, (remo\u00e7\u00e3o). Todos os comando tem um par\u00e2metro, que aparece separado do comando por um espa\u00e7o. Os comandos aparecem um por linha. O par\u00e2metero ser\u00e1 no formato de par\u00eanteses aninhados, representando a \u00e1rvore secund\u00e1ria B.<\/span><\/p>\n

i (1)\u00a0\u00a0Obs:\u00a0<\/strong>o valor de indexa\u00e7\u00e3o desta sub-\u00e1rvore \u00e9 1<\/span>
i (10(8)(30))\u00a0Obs:\u00a0<\/strong>o valor de indexa\u00e7\u00e3o desta sub-\u00e1rvore \u00e9 48<\/span>
i (11(10)(17))\u00a0Obs:\u00a0<\/strong>o valor de indexa\u00e7\u00e3o desta sub-\u00e1rvore \u00e9 38<\/span>
i (15)\u00a0Obs:\u00a0<\/strong>o valor de indexa\u00e7\u00e3o desta sub-\u00e1rvore \u00e9 15<\/span>
i (25(10(5)())())\u00a0Obs:\u00a0<\/strong>o valor de indexa\u00e7\u00e3o desta sub-\u00e1rvore \u00e9 40<\/span>
b (25(10(5)())())\u00a0Obs:\u00a0<\/strong>o valor de indexa\u00e7\u00e3o desta sub-\u00e1rvore \u00e9 40<\/span>
b (25(10(5)())())\u00a0Obs:\u00a0<\/strong>o valor de indexa\u00e7\u00e3o desta sub-\u00e1rvore \u00e9 40<\/span>
b (10(7)(23))\u00a0Obs:\u00a0<\/strong>o valor de indexa\u00e7\u00e3o desta sub-\u00e1rvore \u00e9 40<\/span>
r (11(10)(17))\u00a0Obs:\u00a0<\/strong>o valor de indexa\u00e7\u00e3o desta sub-\u00e1rvore \u00e9 38<\/span>
r (15)<\/span><\/p>\n

Sa\u00edda:<\/strong><\/span><\/p>\n

A cada comando executado uma sa\u00edda deve ser gerada (execu\u00e7\u00e3o da fun\u00e7\u00e3o 4). A sa\u00edda deve representar o estado das \u00e1rvores ap\u00f3s a execu\u00e7\u00e3o do comando. Para o comando de busca, a sa\u00edda deve tamb\u00e9m indicar se o n\u00famero total procurado est\u00e1 ou n\u00e3o na \u00e1rvore e os n\u00f3s percorridas (impress\u00e3o das \u00e1rvores secund\u00e1rias). O formato da descri\u00e7\u00e3o da \u00e1rvore \u00e9 de colchetes aninhados, com separador de linhas entre os n\u00f3s para a \u00e1rvore principal A, e par\u00eanteses aninhados em uma \u00fanica linha para as \u00e1rvores secund\u00e1rias B.<\/span><\/p>\n

Exemplos:<\/span><\/p>\n

A sa\u00edda, para cada comando de altera\u00e7\u00e3o (\u201ci\u201d ou \u201cr\u201d), ser\u00e1 a descri\u00e7\u00e3o da \u00e1rvore resultante. Os comandos de inclus\u00e3o acima resultar\u00e3o na \u00e1rvore abaixo:<\/span><\/p>\n

[[(1) : 1<\/span>
[<\/span>
]<\/span>
[(10(8)(30)) : 48<\/span>
[(11(10)(17)) : 38<\/span>
[15 : 15<\/span>
]<\/span>
[(25(10(5)())()) : 40<\/span>
]<\/span>
][<\/span>
]<\/span>
]<\/span>
]<\/span>
]<\/span><\/p>\n

O comando de exclus\u00e3o resultar\u00e1 na \u00e1rvore abaixo<\/span><\/p>\n

[[(1) : 1<\/span>
[<\/span>
]<\/span>
[(10(8)(30)) : 48<\/span>
[(11(10)(17)) : 38<\/span>
[\u00a0\u00a0\u00a0 \/\/O n\u00f3 (15)<\/strong>\u00a0 estava nesta posi\u00e7\u00e3o<\/span>
]<\/span>
[(25(10(5)())()) : 40<\/span>
]<\/span>
][<\/span>
]<\/span>
]<\/span>
]<\/span>
]<\/span><\/p>\n

A entrada para os comandos de busca ser\u00e1 uma sub-\u00e1rvore B. Note que mais de uma \u00e1rvore de entrada pode retornar a mesma sub-\u00e1rvore. A sa\u00edda para o comando de busca ser\u00e1 a seq\u00fc\u00eancia de n\u00f3s visitados. O comando de busca resultar\u00e1 na impress\u00e3o abaixo:<\/span><\/p>\n

(1) : 1<\/span>
(10(8)(30) : 48<\/span>
(11(10)(17)) : 38<\/span>
(25(10(5)())()) : 40<\/span><\/p>\n

Requisitos:<\/strong><\/span><\/p>\n

O nome do execut\u00e1vel deve ser\u00a0busca<\/strong>.<\/span><\/p>\n

N\u00e3o deve ter nenhuma op\u00e7\u00e3o de linha comando. O resultado deve sempre lido e escrito na sa\u00edda padr\u00e3o.<\/span>
O que deve ser entregue:<\/span><\/p>\n

Al\u00e9m dos arquivos fonte, deve acompanhar um makefile e um arquivo README explicando o que foi feito e com o nome dos autores.<\/span><\/p>\n

Para testar:<\/span><\/p>\n

busca < teste.in > teste_stdin.out<\/span>
ou<\/span>
busca teste.in > teste_arq.out<\/span>

<\/p>\n

ENTREGA<\/span><\/h3>\n

Entregar os arquivos fontes e o Makefile. Este deve ser compilado facilmente nos servidores do Dinf, atrav\u00e9s de comando make.<\/span><\/p>\n

MODO DE ENTREGA :\u00a0<\/b>enviar os arquivos por email para marcos.ddf _at_ inf.ufpr.br (at\u00e9 as 24h).<\/span>
O trabalho deve ser em grupos com 2 ou 3 alunos. No assunto, preencher com \u201cEntrega trabalho 057\u201d.<\/span><\/p>\n","protected":false},"excerpt":{"rendered":"","protected":false},"author":21,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-1376","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/web.inf.ufpr.br\/didonet\/wp-json\/wp\/v2\/pages\/1376","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/web.inf.ufpr.br\/didonet\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/web.inf.ufpr.br\/didonet\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/web.inf.ufpr.br\/didonet\/wp-json\/wp\/v2\/users\/21"}],"replies":[{"embeddable":true,"href":"https:\/\/web.inf.ufpr.br\/didonet\/wp-json\/wp\/v2\/comments?post=1376"}],"version-history":[{"count":5,"href":"https:\/\/web.inf.ufpr.br\/didonet\/wp-json\/wp\/v2\/pages\/1376\/revisions"}],"predecessor-version":[{"id":1600,"href":"https:\/\/web.inf.ufpr.br\/didonet\/wp-json\/wp\/v2\/pages\/1376\/revisions\/1600"}],"wp:attachment":[{"href":"https:\/\/web.inf.ufpr.br\/didonet\/wp-json\/wp\/v2\/media?parent=1376"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}