{"id":68,"date":"2017-06-22T17:03:00","date_gmt":"2017-06-22T20:03:00","guid":{"rendered":"http:\/\/web.inf.ufpr.br\/didonet2\/?page_id=68"},"modified":"2017-06-22T17:03:00","modified_gmt":"2017-06-22T20:03:00","slug":"trabalho-ci057-2017-1","status":"publish","type":"page","link":"https:\/\/web.inf.ufpr.br\/didonet\/teaching-disciplinas\/ci057-2017-1\/trabalho-ci057-2017-1\/","title":{"rendered":"Trabalho CI057 2017 1"},"content":{"rendered":"

Implementa\u00e7\u00e3o da \u00c1rvore AVL<\/h2>\n

\n

O objetivo do trabalho \u00e9 a implementa\u00e7\u00e3o das rotinas de manipula\u00e7\u00e3o de uma \u00e1rvore AVL.<\/p>\n

O trabalho deve ter as defini\u00e7\u00f5es de uma \u00e1rvore AVL que armazene n\u00fameros inteiros e as fun\u00e7\u00f5es de busca, inser\u00e7\u00e3o e remo\u00e7\u00e3o.<\/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 de entrada o programa termina.<\/p>\n

Entrada:<\/h2>\n

 <\/p>\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, um n\u00famero inteiro, que aparece separado do comando por um espa\u00e7o. Os comandos aparecem um por linha.<\/p>\n

i 1
\ni 2
\ni 3
\ni 4
\nb 5
\nr 4<\/p>\n

\nSa\u00edda:<\/strong><\/p>\n

A cada comando executado uma sa\u00edda deve ser gerada. A sa\u00edda deve representar o estado da \u00e1rvore ap\u00f3s a execu\u00e7\u00e3o do comando. Para o comando de busca, a sa\u00edda deve tamb\u00e9m indicar se o n\u00famero procurado est\u00e1 ou n\u00e3o na \u00e1rvore, e apresentar a lista de n\u00f3s consultados. O formato da descri\u00e7\u00e3o da \u00e1rvore \u00e9 “(R,E,D)”, onde R \u00e9 o valor guardado no n\u00f3 ra\u00edz, E e D s\u00e3o as sub-\u00e1rvores esquerda e direita (recursivamente). A \u00e1rvore vazia \u00e9 representada por “()”. Um exemplo pode ser visto abaixo.<\/p>\n

Para representar uma \u00e1rvore onde a ra\u00edz \u00e9 o “a”, “a” tem fihos “b” e “c”. “b” n\u00e3o tem filhos e “c” s\u00f3 tem o filho esquerdo “d”, usamos a seguinte linha:<\/p>\n

(a,(b,(),()),(c,(d,(),()),()))<\/p>\n

A sa\u00edda, para cada comando de altera\u00e7\u00e3o (“i” ou “r”), ser\u00e1 a repeti\u00e7\u00e3o do comando em uma linha (tal como foi lido da entrada) e na linha seguinte a descri\u00e7\u00e3o da \u00e1rvore resultante.<\/p>\n

A sa\u00edda para o comando de busca ser\u00e1 a repeti\u00e7\u00e3o do comando em uma linha e na linha seguinte a seq\u00fc\u00eancia de n\u00f3s visitados, separados por v\u00edrgulas (“,”). Caso o n\u00f3 procurado tenha sido encontrado ele ser\u00e1 o \u00faltimo da seq\u00fc\u00eancia.<\/p>\n

Exemplo de sa\u00edda (para a entrada acima):<\/p>\n

i 1
\n(1,(),())
\ni 2
\n(1,(),(2,(),()))
\ni 3
\n(2,(1,(),()),(3,(),()))
\ni 4
\n(2,(1,(),()),(3,(),(4,(),())))
\nb 5
\n2,3,4
\nr 4
\n(2,(1,(),()),(3,(),()))<\/p>\n

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

O nome do execut\u00e1vel deve ser busca<\/strong>.<\/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.
\nO que deve ser entregue:<\/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.<\/p>\n

Para testar:<\/p>\n

busca < teste.in > teste_stdin.out
\nou
\nbusca teste.in > teste_arq.out
\n
<\/p>\n

ENTREGA<\/h3>\n

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

IMPORTANTE! DATA DE ENTREGA : <\/b>09 de junho. (alterado para dia 14 de junho)<\/strong><\/div>\n
<\/div>\n

MODO DE ENTREGA : <\/b> enviar os arquivos por email para marcos.ddf _at_ inf.ufpr.br (at\u00e9 as 24h) ou eduardo _at_ inf.ufpr.br, dependendo da turma. N\u00e3o poder\u00e3o haver grupos com integrantes de turmas diferentes.
\nO trabalho pode ser individual ou em duplas. No assunto, preencher com “Entrega trabalho 057”.<\/p>\n","protected":false},"excerpt":{"rendered":"

Implementa\u00e7\u00e3o da \u00c1rvore AVL O objetivo do trabalho \u00e9 a implementa\u00e7\u00e3o das rotinas de manipula\u00e7\u00e3o de uma \u00e1rvore AVL. O trabalho deve ter as defini\u00e7\u00f5es de uma \u00e1rvore AVL que armazene n\u00fameros inteiros e as fun\u00e7\u00f5es de busca, inser\u00e7\u00e3o e remo\u00e7\u00e3o. Uma aplica\u00e7\u00e3o dever\u00e1 ser implementada para usar as fun\u00e7\u00f5es de manipula\u00e7\u00e3o da \u00e1rvore. Esta…<\/p>\n","protected":false},"author":21,"featured_media":0,"parent":62,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-68","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/web.inf.ufpr.br\/didonet\/wp-json\/wp\/v2\/pages\/68","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=68"}],"version-history":[{"count":1,"href":"https:\/\/web.inf.ufpr.br\/didonet\/wp-json\/wp\/v2\/pages\/68\/revisions"}],"predecessor-version":[{"id":69,"href":"https:\/\/web.inf.ufpr.br\/didonet\/wp-json\/wp\/v2\/pages\/68\/revisions\/69"}],"up":[{"embeddable":true,"href":"https:\/\/web.inf.ufpr.br\/didonet\/wp-json\/wp\/v2\/pages\/62"}],"wp:attachment":[{"href":"https:\/\/web.inf.ufpr.br\/didonet\/wp-json\/wp\/v2\/media?parent=68"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}