Lista Simplesmente Encadeada na "unha" - ajuda

25 de novembro de 2011 5 respostas

mkarnazes 25 de novembro de 2011

Pessoal, como podem ver no meu nr. de posts, sou novo no fórum.
Na facul estavamos aprendendo Simply linked lists (não duplamente) e chegou 1 hora que o professor pede pra implementar um método com uma assinatura parecida com essa:

public int removeALL(int item);
Lembrando que nosso nodo é dividido em 2 partes (uma para dados (usamos inteiro para simplicidade)) e outra o ponteiro que aponta pro proximo nodo da lista.

Ou seja, esse método deverá remover todos os nodos contendo o elemento ‘item’ como dado no nodo, e retornar o total de nodos removidos, que continham(match “positivo”) esse valor dentro.

Bem, eu criei um método public int contains(int element); que retorna a quantidade de nodos com aquele elemento na lista.
Aqui está o código do contains: http://paste.ideaslabs.com/show/byQMo0ExnF

O máximo que consegui fazer do código do removeALL foi isto: [url]http://paste.ideaslabs.com/show/LnN8yBpEPe/url]
O que eu realmente preciso, é aprender a remover todas as ocorrências de nodos, seja no middle, ou no final da lista.
Já pensei em algo como um loop while percorrendo com aux = aux.next; mas nao tive sucesso.
Estou a dias nesse problema e nada, o professor não conseguiu ajudar, to realmente pensando em pedir ajuda pra um outro professor, pois os colegas também não quiseram/conseguiram.

Ah sim, muito importante: Eu uso uma classe só pra implementar a lista encadeada, nada de duas classes com 1 interna privada
Aqui vc consegue ter 1 boa idéia da classe:

public class ListaEncadeada {

    int item, count;
   
    ListaEncadeada head, tail, next;

    public ListaEncadeada() {
        head = null;
        tail = null;
        count = 0;
        
                                               }

    public void add_final(int valor) {

        ListaEncadeada newnode = new ListaEncadeada();
        newnode.item = valor;

        
         if (head == null) {
            head = newnode;
        }
        else {
            tail.next = newnode;
        }
        tail = newnode;
        count++;
    }

}

Valeu

5 Respostas

Lucas_Abbatepaolo 25 de nov. de 2011

Pq vc tem um head e um tail…se sua lista fosse simplesmente encadeado vc nao deveria ter so o tail…
tendo os 2 vc não passa a ter uma lista duplamente encadeada???

davidbuzatto 25 de nov. de 2011

Você quer remover todos os elementos que casem com o parâmetro passado?
É isso?

Olha o algoritmo:

1 - Enquanto a cabeça tiver o valor passado, reaponte a cabeça para o próximo da cabeça antiga.
2 - “Itere” pela lista, usando os próximos elementos até a cauda. Se o próximo elemento tiver o valor passado refaça os reapontamentos para que o próximo seja o atual. Você precisa usar o próximo e não o atual, se não você não consegue voltar um elemento da lista para reapontar.

Chegando na calda, o elemento desejado vai ter sido removido.

[]'s

davidbuzatto 25 de nov. de 2011

Lucas Abbatepaolo:
Pq vc tem um head e um tail…se sua lista fosse simplesmente encadeado vc nao deveria ter so o tail…
tendo os 2 vc não passa a ter uma lista duplamente encadeada???

Para ter uma lista duplamente encadeada ele precisaria ter um “next” e um “previous”, ou seja, cada nó sabe qual é o seu próximo e qual o seu anterior.
A cabeça dele indica o primeiro elemento da lista, enquanto o tail indica o último da lista.
O tail dele é desnecessário, visto que um nó com null no next seria a cauda, mas se o professor ensinou assim é melhor deixar assim mesmo.

[]'s

yhhik 25 de nov. de 2011

da uma olhada nesse exemplo cara…fiz quando estudava estrutura…
ta fácil de entender, bem comentado…não é java mas da pra ter uma ideia.
tem tds as funções básicas

#include <stdio.h>
#include <string.h>
#include <conio.h>
#include <stdlib.h>

struct lista {
   int info; //armazena informação (número inteiro)
   struct lista* prox; //ponteiro que aponta para uma próxima estrutura do mesmo tipo
};
typedef struct lista Lista;

Lista* inicializa (void) //função que inicializa a lista vazia com return null
{
   return NULL;
}

Lista* insere (Lista* l, int i) //função para inserir elemento
{
   Lista* novo = (Lista*) malloc(sizeof(Lista)); //aloca um novo elemento que caiba uma lista
   novo->info = i; //insere um valor int
   novo->prox = l; //quarda o valor da posição de memória
   return novo;
}
void imprime (Lista* l)
{
   Lista* aux; //variável auxiliar para percorrer a lista 
   for (aux = l; aux != NULL; aux = aux->prox) //aux recebe lista principal e enquanto aux não apontar para null há elementos na lista
      printf("info = %d\n", aux->info); //mostra os valores (info) da lista 
      
}


void pesquisa(Lista* l, int num){ //função para pesquisar elemento na lista
      if (l == NULL){ //verifica se a lista está vazia
       printf("LISTA VAZIA!!"); 
       getch();
       return; //se a lista estiver vazia sai da função
      }
     Lista* aux; //cria lista auxiliar
     for(aux = l; aux != NULL; aux = aux->prox){
        if(num == aux->info){ //compara elemento da lista com o elemento pesquisado
         printf("Numero Encontrado!"); //se o elemento, se encontrar na lista mostra mensagem que o número foi encontrado
         getch();
         return; //sai da função
     }

}
       printf("Numero Nao Encontrado!"); //se o elemento não está na lista, mostra mensagem que o número não foi encontrado
       getch();
     }
void apresentarLista(Lista* l){ //mostra todos elementos da lista
      if (l == NULL){ //verifica se a lista está vazia
       printf("LISTA VAZIA!!"); 
       getch();
       return; //se a lista estiver vazia sai da função
      }
     Lista* aux; //cria lista auxiliar
     for(aux = l; aux != NULL; aux = aux->prox){
         printf("%d,",aux->info); //imprime elemento da lista, ao final da execução do "for" todos os elementos serão impressos
      }
       getch();
     }
     
void alterar(Lista*l, int num){ //alterar elemento da lista
      if (l == NULL){ //verifica se a lista está vazia
       printf("LISTA VAZIA!!"); 
       getch();
       return; //se a lista estiver vazia sai da função
     }
       Lista* aux; //cria lista auxiliar
       int num2 = 0; //cria variável para receber novo valor
     for(aux = l; aux != NULL; aux = aux->prox){
        if(num == aux->info){ //verifica se o número existe para depois alterá-lo
         printf("Numero Encontrado!");
         printf("\nQual o novo valor?");
         scanf("%d",&num2); //se o número existe é informado o novo valor
         aux->info = num2; //substitui o valor
         return;
 }  
    }
       printf("Numero Nao Encontrado!");
       getch();
    }  
    
Lista* remover (Lista* l, int num) { //função para deletar elemento da lista
   if (l == NULL){ //verifica se a lista está vazia
       printf("LISTA VAZIA!!"); 
       getch();
       return; //se a lista estiver vazia sai da função
   }
   Lista* ant = NULL; //ponteiro para elemento anterior 
   Lista* aux = l; //ponteiro para percorrer a lista
   //procura elemento na lista, guardando anterior 
   while ((aux != NULL) && (aux->info != num)) {
      ant = aux;
      aux = aux->prox;
   }
   
   if (aux == NULL) //verifica se elemento existe
      return l; //se não existe, retorna lista original 
   
   if (ant == NULL) {
     
      l = aux->prox; //retira elemento do início 
   }
   else {
      
      ant->prox = aux->prox; //retira elemento do meio da lista 
   }
   free(aux);
   return l;
} 
void esvaziar (Lista* l)
        {
    Lista* aux = l;
    while (aux != NULL) {
       Lista* t = aux->prox; //guarda referência para o próximo elemento
       free(aux); //libera a memória apontada por p
      aux = t; //faz p apontar para o próximo
   }
}

     void ordenar(Lista* l){ //função para ordenar
     //usa algorítmo de ordenação
     Lista* aux; //cria lista auxiliar para algoritmo de ordenação
     Lista* aux2; //cria lista auxiliar para algoritmo de ordenação
     int tmp = 0; //cria variável para auxiliar na troca de valores
     for(aux = l; aux != NULL; aux = aux->prox){ //aux recebe lista principal e enquanto aux não apontar para null, há elementos na lista 
         for(aux2 = l; aux2 != NULL; aux2 = aux2->prox){ //aux2 recebe lista principal e enquanto aux não apontar para null, há elementos na lista
             if((aux2->info) > (aux->info)){ //compara elementos da lista (se elemento de aux2 maior que elemento de aux é feito uma troca)
               tmp = aux2->info;            
               aux2->info = aux->info;
               aux->info = tmp;
             }
         }
     }
    free(aux); //libera aux
    free(aux2); //libera aux2
    }
     void menu(Lista* l){ //função menu que recebe a lista inicializada
     
          int opcao = 0, num = 0;
          while(opcao != 7){
          system("cls");
          printf("\n\n\n ======================= M E N U =======================\n\n");
          printf("\n\t (1) Inserir um elemento na lista\n");
          printf("\n\t (2) Buscar um elemento na lista\n");
          printf("\n\t (3) Remover um elemento da lista\n");
          printf("\n\t (4) Esvaziar lista por completo\n");
          printf("\n\t (5) Apresentar lista existente\n");
          printf("\n\t (6) Alterar o valor de um elemento da lista\n");
          printf("\n\t (7) Sair do programa.\n");
          
          printf("\n\n Digite a opcao desejada: ");
          fflush(stdin);
          scanf("%d",&opcao);
          fflush(stdin);
                    
          switch (opcao){
               case 1: 
                printf("\nDigite um Numero: ");
                scanf("%d",&num);
                l = insere(l,num); //chama função para inserir novo elemento na lista  
               break;
               case 2:
                printf("\nDigite um Numero: ");  
                scanf("%d",&num);  
                pesquisa(l,num); //chama função para buscar elemento na lista  
               break;
               case 3:
                printf("\nDigite um Numero a ser Removido: ");  
                scanf("%d",&num);
                remover(l,num); //chama função para remover elemento na lista  
               break;
               case 4:
                esvaziar(l); //chama função para esvaziar a lista
               break;
               case 5:
                apresentarLista(l); //chama função para mostrar todos elementos da lista
               break;
               case 6:
                printf("\nDigite um Numero a ser Alterado: ");  
                scanf("%d",&num);
                alterar(l,num); //chama função para alterar elemento na lista  
               break;
               case 7:
               printf("\n\n Tchau ! \n\n Pressione qualquer tecla para finalizar");
               break;
               default:
                 printf("Opcao Invalida!");  
                 getch();
              break;
          }
        
          }
     }


int main (void) //função principal
{
   Lista* l; //cria lista vazia
   l = inicializa(); //inicializa a lista
   menu(l);
   getch();
   return 0;
}

Lucas_Abbatepaolo 25 de nov. de 2011

davidbuzatto:
Lucas Abbatepaolo:
Pq vc tem um head e um tail…se sua lista fosse simplesmente encadeado vc nao deveria ter so o tail…
tendo os 2 vc não passa a ter uma lista duplamente encadeada???

Para ter uma lista duplamente encadeada ele precisaria ter um “next” e um “previous”, ou seja, cada nó sabe qual é o seu próximo e qual o seu anterior.
A cabeça dele indica o primeiro elemento da lista, enquanto o tail indica o último da lista.
O tail dele é desnecessário, visto que um nó com null no next seria a cauda, mas se o professor ensinou assim é melhor deixar assim mesmo.

[]'s

Obrigado pela explicação…

O q achei diferente é ele criar uma lista com seus elementos sendo outras lista. Quando implementei isto (a algum tempo atras na faculdade) eu utilizava um objeto "lista’ que possuia o “tail” , e os elementos eu criava um outro objeto “no” que possuia como um de seus atributos o “next”.

Basicamente assim:

public class ListaEncadeada {
    
    private No tail;
    private int size;

  }

  public class No {

    private String desc;
    private No next;

  }

Sei que pode se implementar um lista contendo outras lista, porem acho q didaticamente fica mais dificil de se entender.
Obrigado

Criado 25 de novembro de 2011

Ultima resposta 25 de nov. de 2011

Respostas 5

Participantes 4

5 Respostas

Topicos relacionados