View
4.109
Download
5
Category
Preview:
Citation preview
Estrutura de DadosListas EncadeadasProf. Adriano Teixeira de Souza
Listas Encadeadas Listas encadeadas ou listas ligadas
representam uma seqüência de objetos na memória do computador.
Exemplo: Lista de afazeres1. Comprar uma lâmpada
2. Trocar uma lâmpada queimada
3. Procurar uma conta no quarto
4. Pagar uma conta na internet
5. Desligar o computador
6. Dormir
Listas Encadeadas
PróximaaçãoAção atual
Na lista de afazeres anterior, uma tarefa dependia da execução da tarefa anterior
Listas Encadeadas
21.
Comprar lâmpada
32. Trocar lâmpada
43.
Procurar conta
54. Pagar conta
65.
Desligar micro
fim6. Dormir
DormirDesligar micro
Pagar conta
Procurar conta
Trocar lâmpad
a
Listas Encadeadas:: Representação por vetores Como representar a lista anterior em um
programa escrito na Linguagem C?◦ Primeira opção: vetores ou matrizes
Comprar
lâmpada
Tarefa:
Índice: 1 2 3 4 5 6
Listas Encadeadas:: Representação por vetores Primeira opção: vetores ou matrizes
◦ Como acrescentar “Ligar micro”?
DormirDesligar micro
Pagar contaLigar micro
Procurar conta
Trocar lâmpad
a
Comprar
lâmpada
Tarefa:
Índice: 1 2 3 4 5 6 7
Listas Encadeadas:: Representação por vetores Primeira opção: vetores ou matrizes
◦ Os itens da lista são armazenados em posições contíguas de memória.
◦ A lista pode ser percorrida em qualquer direção.
◦ A inserção de um novo item pode ser realizada após o último item com custo constante.
◦ A inserção de um novo item no meio da lista requer um deslocamento de todos os itens localizados após o ponto de inserção.
◦ Retirar um item do início da lista requer um deslocamento de itens para preencher o espaço deixado vazio.
Listas Encadeadas:: Representação por ponteiros Segunda opção: ponteiros
◦ Estruturas de dados dinâmicas: estruturas de dados que contém ponteiros para si próprias.
class Lista { String nomeTarefa;float duracao;String
responsavel;...Lista prox;
};
class Lista { String nomeTarefa;float duracao;String
responsavel;...Lista prox;
};
Referência para a própria classe Lista
Representação gráfica de um elemento da lista:
◦ Cada item é encadeado com o seguinte, mediante uma variável do tipo ponteiro.
◦ Permite utilizar posições não contíguas de memória.
◦ É possível inserir e retirar elementos sem necessidade de deslocar os itens seguintes da lista.
campos de informação
Listas Encadeadas:: Representação por ponteiros
próximo nó
Listas Encadeadas:: Representação por ponteiros Cada item em particular de uma lista pode ser
chamado de elemento, nó, célula, ou item.
O apontador para o início da lista também é tratado como se fosse uma célula (cabeça), para simplificar as operações sobre a lista.
O símbolo / representa o ponteiro nulo (null), indicando o fim da lista.
3 5p
2/4
Operações sobre lista encadeada Podemos realizar algumas operações sobre
uma lista encadeadas, tais como:◦Inserir itens;◦Retirar itens;◦Buscar itens.
Para manter a lista ordenada, após realizar alguma dessas operações, será necessário apenas movimentar alguns ponteiros (de um a três elementos).
Operações sobre lista encadeada Outras operações possíveis:
◦Criar uma lista◦Destruir uma lista◦Ordenar uma lista◦Intercalar duas listas◦Concatenar duas listas◦Dividir uma lista em duas◦Copiar uma lista em outra
Prof. Adriano Teixeira de Souza
Criar Lista
class NoLista {
float info;NoLista proximo;
public NoLista(float valor){
this.info = valor;this.proximo = null;
}
}
class NoLista {
float info;NoLista proximo;
public NoLista(float valor){
this.info = valor;this.proximo = null;
}
}
Listas Simplesmente Encadeadas
Para criar a lista propriamente dita, criaremos a classe Lista, que manipula objetos do tipo NoLista
class Lista { NoLista inicio;
public Lista() { this.inicio = null; }
// insere valor no começo da lista
public void inserir(int valor) {...}
// insere valor no fim da lista
public void inserirNoFim(int valor) {...} }
Operações sobre lista encadeada:: Inserção de itens
Podemos inserir itens:◦No início de uma lista◦No final de uma lista◦No meio de uma lista
p 5 2 /4
Operações sobre lista encadeada:: Inserção de itens no início O endereço armazenado no ponteiro p deve
ser alterado para o endereço do item a ser acrescido à lista.
3
Prof. Adriano Teixeira de Souza
Inserção de itens no início
public void inserir(float valor) { if (this.inicio == null) { // lista vazia, então só é preciso criar o nó this.inicio = new NoLista(valor); } else {
// cria-se novo no e atualiza o NoLista inicio NoLista novoNo = new NoLista(valor);
novoNo.proximo = this.inicio;
this.inicio = novoNo; }}
public void inserir(float valor) { if (this.inicio == null) { // lista vazia, então só é preciso criar o nó this.inicio = new NoLista(valor); } else {
// cria-se novo no e atualiza o NoLista inicio NoLista novoNo = new NoLista(valor);
novoNo.proximo = this.inicio;
this.inicio = novoNo; }}
Operações sobre lista encadeada:: Inserção de itens no final
O endereço armazenado em p será alterado caso a lista esteja vazia ou
O campo proximo do último item será alterado.
/3p
/
3 /5p
Prof. Adriano Teixeira de Souza
Inserção de itens no finalpublic void inserirNoFim(int valor) { if (this.inicio == null) { // lista vazia this.inicio = new NoLista(valor); } else { // procura pelo fim da lista NoLista atual = this.inicio; while (atual.proximo != null) atual = atual.proximo; // insere o nó no fim da lista atual.proximo = new NoLista(valor); }}
public void inserirNoFim(int valor) { if (this.inicio == null) { // lista vazia this.inicio = new NoLista(valor); } else { // procura pelo fim da lista NoLista atual = this.inicio; while (atual.proximo != null) atual = atual.proximo; // insere o nó no fim da lista atual.proximo = new NoLista(valor); }}
Operações sobre lista encadeada:: Inserção de itens no meio Campo proximo do item a ser inserido
recebe o campo proximo do item posterior Campo proximo do item antecessor recebe
o endereço do item a ser inserido
2 /4
5
3p
lista[5].proximo ← lista[2]
lista[3].proximo ← 5
lista[5].proximo ← lista[2]
lista[3].proximo ← 5
p 5 2 /4
Operações sobre lista encadeada:: Remoção de itens no início
O endereço armazenado no ponteiro p deve ser alterado para o endereço do item que segue o primeiro item da lista.
Operações sobre lista encadeada:: Remoção de itens no final
O campo proximo do último item será alterado caso a lista contenha mais de um item ou
O endereço armazenado em p será alterado para null caso tenha somente um elemento.
/3p
/
3 /5p
Operações sobre lista encadeada:: Remoção de itens no meio Item antecessor recebe o campo proximo
do item a ser removido
5 2 /43p
lista[3].proximo ← lista[5].proximo
lista[3].proximo ← lista[5].proximo
Função retiravoid retira (float v) {//Em qualquer posicao NoLista ant = null; NoLista p = this.inicio;
while (p != null && p.info != v) { ant = p; p = p.proximo; }
if (p != null){ if (ant == null) {
this.inicio = p.proximo; }else {
ant.proximo = p.proximo; }
};}
void retira (float v) {//Em qualquer posicao NoLista ant = null; NoLista p = this.inicio;
while (p != null && p.info != v) { ant = p; p = p.proximo; }
if (p != null){ if (ant == null) {
this.inicio = p.proximo; }else {
ant.proximo = p.proximo; }
};}
Prof. Adriano Teixeira de Souza
Função de busca
NoLista busca (float v){ int i=0; for (NoLista p = this.inicio; p!=null;
p=p.proximo){ if(p.info == v){ System.out.println("\n\nachou “+i+”\n\n"); return p; } i++; } return null;}
NoLista busca (float v){ int i=0; for (NoLista p = this.inicio; p!=null;
p=p.proximo){ if(p.info == v){ System.out.println("\n\nachou “+i+”\n\n"); return p; } i++; } return null;}
Prof. Adriano Teixeira de Souza
Impressão
void imprime (){ for(NoLista q=this.inicio;q!=null;
q=q.proximo) System.out.println(q.info);
}
void imprime (){ for(NoLista q=this.inicio;q!=null;
q=q.proximo) System.out.println(q.info);
}
Prof. Adriano Teixeira de Souza
Testepublic static void main(String[] args){
Lista l = new Lista();l.inserir(20.0f);l.inserir(44.5f);l.inserir(33.3f);l.inserir(20.9f);l.imprime();NoLista n = l.busca(20.9f);//Buscaif (n != null){
System.out.println("Encontrado:"+n.info); l.retira(n.info);
}System.out.println("Configuracao da lista:");l.imprime();//Libera memorial = null;
}
public static void main(String[] args){
Lista l = new Lista();l.inserir(20.0f);l.inserir(44.5f);l.inserir(33.3f);l.inserir(20.9f);l.imprime();NoLista n = l.busca(20.9f);//Buscaif (n != null){
System.out.println("Encontrado:"+n.info); l.retira(n.info);
}System.out.println("Configuracao da lista:");l.imprime();//Libera memorial = null;
}
Prof. Adriano Teixeira de Souza
Insere ordenadovoid insereOrdenado ( float valor){
NoLista novoNo = new NoLista(valor );
NoLista ant = null; NoLista p = this.inicio;
while (p != null && p.info < valor) { ant = p; p = p.proximo; } if (ant == null) { novoNo.proximo = this.inicio; this.inicio = novoNo; } else { novoNo.proximo = ant.proximo; ant.proximo = novoNo; } }
void insereOrdenado ( float valor){
NoLista novoNo = new NoLista(valor );
NoLista ant = null; NoLista p = this.inicio;
while (p != null && p.info < valor) { ant = p; p = p.proximo; } if (ant == null) { novoNo.proximo = this.inicio; this.inicio = novoNo; } else { novoNo.proximo = ant.proximo; ant.proximo = novoNo; } }
Genéricos Adicionado a C# 2.0 e posteriormente a Java 5 Classes Genéricas, que utilizam o conceito de “parâmetros
tipo”<..> Lista com Genéricos: cada lista armazena um tipo específico, sem
precisar criar código novo para cada tipo
class NoListaI{ int valor; NoLista next;}
class NoListaS{ String nome; NoLista next;}
Sem Genéricos:
Com Genéricos:
class NoLista<E> { E elemento; NoLista<E> next;}
Listas com Genéricosclass Lista<E> { NoLista<E> inicio;
public Lista() { this.inicio = null; }
public void inserir(E elemento) { if (this.inicio == null) { this.inicio = new NoLista<E>(elemento); } else {
NoLista<E> novoNo = new NoLista<E>(elemento);
novoNo.next = this.inicio;
this.inicio = novoNo; } }
}
Recommended