TP de AEDS II - LISTAS DUPLAMENTE ENCADEADAS

OLÁ AMIGOS, TENHO QUE FAZER UM TRABALHO CUJO ENUNCIADO SE ENCONTRA ABAIXO, O PROBLEMA É QUE NÃO SEI NADA DE JAVA E O LIVRO QUE COMPREI (JAVA COMO PROGRAMAR) NÃO ESTÁ ME AJUDANDO MUITO. SE ALGUÉM PUDER ME AJUDAR NÃO RESOLVENDO O TRABALHO MAS ME ORIENTANDO EU APRECIARIA MUITO:

O tipo abstrato de dados LR de lista linear de itens definido pelas seguintes opera¸c˜oes:

LR()
Opera¸c˜ao tipo construtor para iniciar objetos do tipo LR, criando uma lista vazia.
boolean pesquisa(String c)
z.pesquisa© pesquisa pelo item armazenado em z cuja chave seja c e informa se o encontrou ou n˜ao.
Ap´os a pesquisa, o objeto z identifica o item encontrado como sendo o item corrente do objeto. Se n˜ao
encontrou, a posi¸c˜ao corrente deve ficar inalterada.
void insereAntes(Item x)
z.insereaAntes(x) insere item x na lista armazenada por z antes do item corrente de z. Se a lista
estiver vazia, insere-o no in´ıcio da lista. O item inserido sempre torna-se o item corrente da lista. Esta
opera¸c˜ao deve ter custo O(1) no pior caso.
void insereDepois(Item x)
z.insereDepois(x) insere item x na lista armazenada por z depois do item corrente de z. Se a lista
estiver vazia, insere-o no in´ıcio da lista. O item inserido sempre torna-se o item corrente da lista. Esta
opera¸c˜ao deve ter custo O(1) no pior caso.
Item remove( )
z.remove( ) remove e retorna o item que ocupa a posi¸c˜ao corrente da lista armazenada em z. O item
sucessor do que foi removido torna-se o nodo corrente. Esta opera¸c˜ao deve ter custo O(1) no pior caso.
Item corrente(i:integer)
z.corrente(i) torna o i-´esimo nodo da lista, caso exista, o nodo corrente de z.
boolean vazia( )
z.vazia( ) informa se a lista z ´e vazia.

Pedem-se:

Implementar em Java, o tipo abstrato de dados LR, com pelo menos as opera¸c˜oes descritas acima. O tipo
de dados Item pode ser qualquer um que tenha um campo chave do tipo String…
Considere uma lista circular duplamente encadeada, com a no¸c˜ao de posi¸c˜ao corrente, a partir da qual
os apontadores permitem iniciar um caminhamento em qualquer dire¸c˜ao.
Inventar e implementar um programa de teste que demonstre o bom funcionamento das opera¸c˜oes acima.
Entregar a documenta¸c˜ao do programa, descrevendo sua solu¸c˜ao, apresentando necess´ariamente a fun¸c˜ao
de custo de cada uma das opera¸c˜oes e a listagem do programa, dos dados de entrada e sa´ıda, mostrando
sua execu¸c˜ao.
A descri¸c˜ao da solu¸c˜ao deve permitir seu entendimento sem que o leitor tenha que fazer um escrut´ınio
do c´odigo que vocˆe implementou.

6 Respostas

Dudu_UFMG 15 de jun. de 2003

Fala, Zé, tá osso aí??? Hehehehehehehhe…

pcalais 17 de jun. de 2003

pô Zé, c veio aqui em casa e eu te expliquei tudo jah como que faz!
Capricha na documentação! =P

menezes 17 de jun. de 2003

Ou Dudu, nao é por nada nao mas aqui postam-se ajudas e não mensagens do tipo “hehehe” blz?

Pedrão, obrigado por me ajudar, eu postei aqui antes de falar com vc pois fiquei com medo de vc nao ter tempo para me ajudar e eu me ferrar mais uma vez, valeu mesmo!

Dudu_UFMG 18 de jun. de 2003

Pois é, Zé, aqui se postam msgs de ajuda, não pedidos pros outros fazerem trabalho pra vc… :?

menezes 18 de jun. de 2003

Se vc soubesse ler iria ver escrito ORIENTAÇÕES e não trabalho pronto. Entao pq vc nao fica na sua?

Daniel_Quirino_Olive 18 de jun. de 2003

Trabalhinho de faculdade, hein?
Bom, eu vou só mostrar como se constrói uma lista duplamente encadeada, mas não vou implementar os métodos para você (seu professor iria me odiar por isso, tenho certeza).
Ficaria muito menos assim:

public class No{

    private int valor;
    private No proximo = null;
    private No anterior = null;

    /*constrói uma lista vazia, atribuindo um valor ao nó inicial*/
    public No(int valor){
         this.valor = valor;
    }   
}

Pronto, o resto fica por sua conta.

[]s

6 Respostas

Topicos relacionados