Trabalho de Listas Lineares

Prévia do material em texto

Trabalho de Listas Lineares 
	Prof: Diassis Rodrigo
1.Listas Lineares
Dentre as estruturas de dados não primitivas, as listas lineares são as de
manipulação mais simples.
Uma lista linear agrupa informações referentes a um conjunto de elementos
que, de alguma forma, se relacionam entre si. Ela pode se constituir, por exemplo, de
informações sobre os funcionários de uma empresa, sobre notas de compras, itens de
estoque, notas de alunos, etc.
Uma lista linear, ou tabela, é então um conjunto de n ≥ 0 nós L[1], L[2], ...,
L[n] tais que suas propriedades estruturais decorrem, unicamente, da posição relativa
dos nós dentro da seqüência linear. Tem-se:
• se n > 0, L[1] é o primeiro nó;
• para 1 < K ≤ n, o nó L[k] é precedido por L[k-1];
• Operações Mais Freqüentes Em Listas:
• busca;
• inclusão;
• remoção;
São operações básicas, que precisam de algoritmos eficientes.
• Outras Operações:
• alteração;
• combinação de duas listas;
• ordenação;
• determinação do primeiro e do último nó da lista.
• Tipo de armazenamento de uma lista:
• alocação seqüencial;
• alocação encadeada.
• Exemplos de operações possíveis:
– Criar uma lista linear vazia.
– Inserir um novo item imediatamente após o i-ésimo item.
– Retirar o i-ésimo item.
– Localizar o i-ésimo item para examinar e/ou alterar o conteúdo de seus componentes.
– Combinar duas ou mais listas lineares em uma lista única.
– Partir uma lista linear em duas ou mais listas.
– Fazer uma cópia da lista linear.
– Ordenar os itens da lista em ordem ascendente ou 
descendente, de acordo com alguns de seus componentes.
– Pesquisar a ocorrência de um item com um valor particular 
em algum componente.
2.Alocação Sequencial
Maneira mais simples de se manter uma lista na memória. Como a
implementação de alocação seqüencial em linguagens de alto nível é geralmente
realizada com reserva de memória ⇒ alocação estática.
Ex. 1: Considere uma lista L de n elementos.
2.1.Lista com alocação sequencial e estática: 
Vantagens e desvantagens
• Vantagem: economia de memória (os ponteiros 
são implícitos nesta estrutura).
• Desvantagens:
– custo para inserir ou retirar itens da lista, que 
pode causar um deslocamento de todos os itens, 
no pior caso;
– em aplicações em que não existe previsão sobre 
o crescimento da lista, a utilização de arranjos 
em linguagens como o Pascal e o C pode ser 
problemática pois, neste caso, o tamanho 
máximo da lista tem de ser definido em tempo de 
compilação.
2.2.Listas com alocação não sequencial e dinâmica
• 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.
• Há uma célula cabeça para simplificar as operações
sobre a lista
3. Listas Encadeadas
Qualquer estrutura, inclusive listas, que seja armazenada em alocação
encadeada requer o uso de um ponteiro que indique o endereço de seu primeiro nó. O
percurso de uma lista é feito, então, a partir desse ponteiro. A idéia consiste em seguir,
consecutivamente, pelos endereços existentes no campo que indica o próximo nó
(semelhante ao índice da alocação seqüencial). 
Abaixo um algoritimo todo comentado para encadeada simples:
import java.util.Scanner;
 
public class encadeadaSimples {
 
 //Definindo a classe que representará cada elemento da lista
 private static class LISTA {
 
 public int num;
 public LISTA prox;
 }
 
 public static void main(String[] args) {
 Scanner entrada = new Scanner(System.in);
 // a lista está vazia, logo, objeto inicio têm o valor null, o objeto inicio conterá o endereço do primeiro elemento da lista
 LISTA inicio = null;
 // o objeto fim conterá o endereço do último elemento da lista
 LISTA fim = null;
 // o objeto aux é um objeto auxiliar
 LISTA aux;
 // o objeto anterior é um objeto auxiliar
 LISTA anterior;
 // apresenta o menu de opções
 int op, numero, achou;
 do {
 System.out.println("\nMENU DE OPÇÕES\n");
 System.out.println("1 - Inserir no início da lista");
 System.out.println("2 - Inserir no final da lista");
 System.out.println("3 - Consultar toda a lista");
 System.out.println("4 - Remover da lista");
 System.out.println("5 - Esvaziar a lista");
 System.out.println("6 - Sair");
 System.out.print("Digite sua opção: ");
 op = entrada.nextInt();
 if (op < 1 || op > 6) {
 System.out.println("Opção inválida!!");
 } else {
 if (op == 1) {
 System.out.println("Digite o número a ser inserido no início da lista");
 LISTA novo = new LISTA();
 novo.num = entrada.nextInt();
 if (inicio == null) {
 // a lista esta vazia e o elemento inserido será o primeiro e o último da lista
 inicio = novo;
 fim = inicio;
 novo.prox = null;
 } else {
 // a lista já contem elementos e o novo elemento será inserido no início da lista
 novo.prox = inicio;
 inicio = novo;
 }
 System.out.println("Número inserido no início da lista!!");
 }
 if (op == 2) {
 System.out.println("Digite o número a ser inserido no fim da lista: ");
 LISTA novo = new LISTA();
 novo.num = entrada.nextInt();
 if (inicio == null) {
 // a lista estava vazia e o elemento inserido será o primeiro e o último
 inicio = novo;
 fim = novo;
 novo.prox = null;
 } else {
 // a lista já contém elementos e o novo elemento será inserido no fim da lista
 fim.prox = novo;
 fim = novo;
 fim.prox = null;
 }
 System.out.println("Número inserido no fim da lista!!");
 }
 if (op == 3) {
 if (inicio == null) {
 // a lista está vazia
 System.out.println("Lista vazia!!");
 } else {
 // a lista contém elementos e estes serão mostrados do início ao fim
 System.out.println("\nConsultando toda a lista\n");
 aux = inicio;
 while (aux != null) {
 System.out.print(aux.num + " ");
 aux = aux.prox;
 }
 }
 }
 if (op == 4) {
 if (inicio == null) {
 // a lista está vazia
 System.out.println("Lista vazia!!");
 } else {
 // a lista contém elementos e o elemento a ser removido deve ser digitado
 System.out.print("\nDigite o elemento a ser removido: ");
 numero = entrada.nextInt();
 // todos as ocorrências da lista, iguais ao número digitado serão removidas
 aux = inicio;
 anterior = null;
 achou = 0;
 while (aux != null) {
 if (aux.num == numero) {
 // o número digitado foi encontrado na lista e será removido
 achou = achou + 1;
 if (aux == inicio) {
 // o número a ser removido é o primeiro da lista
 inicio = aux.prox;aux = inicio;
 } else if (aux == fim) {
 // o número a ser removido é o último da lista
 anterior.prox = null;
 fim = anterior;
 aux = null;
 } else {
 // o número a ser removido está no meio da lista
 anterior.prox = aux.prox;
 aux = aux.prox;
 }
 } else {
 anterior = aux;
 aux = aux.prox;
 }
 }
 if (achou == 0) {
 System.out.println("Número não encontrado");
 } else if (achou == 1) {
 System.out.println("Número removido 1 vez");
 } else {
 System.out.println("Numero removido " + achou + " vezes");
 }
 }
 }
 if (op == 5) {
 if (inicio == null) {
 // a lista está vazia
 System.out.println("Lista vazia!!");
 } else {
 // a lista será esvaziada
 inicio = null;
 System.out.println("Lista esvaziada");
 }
 }
 
 }
 
 } while (op != 6);
 }
}
3.1.Listas Duplamente Encadeadas
Duplamente encadeada é quando possuem dois ponteiros um para o anterior e o outro para o próximo no primeiro elemento o anterior e apontado para o vazio e o ultimo a elemento aponta para o vazio, uma vantagem de uma lista duplamente encadeada e que pos ser percorrido todos os elementos nos ambos os sentidos, na figura abaixo ilustra uma lista duplamente encadeada.
A lista duplamente encadeada incorpora um novo campo de ponteiro. Os
campos de ponteiros tomam os nomes de ant e post (nó anterior e nó seguinte,
respectivamente).
Abaixo um algoritimo para melhor entender o funcionamento do mesmo:
import java.util.Scanner;
 
public class duplamenteEncadeada {
 
 //Definindo a classe que representará cada elemento da lista
 private static class LISTA {
 
 public int num;
 public LISTA prox;
 public LISTA ant;
 }
 
 public static void main(String[] args) {
 Scanner entrada = new Scanner(System.in);
 // a lista está vazia, logo, objeto inicio têm o valor null, o objeto inicio conterá o endereço do primeiro elemento da lista
 LISTA inicio = null;
 // o objeto fim conterá o endereço do último elemento da lista
 LISTA fim = null;
 // o objeto aux é um objeto auxiliar
 LISTA aux;
 // o objeto anterior é um objeto auxiliar
 LISTA anterior;
 // apresenta o memnu de opções
 int op, numero, achou;
 do {
 System.out.println("\nMENU DE OPÇÕES\n");
 System.out.println("1 - Inserir no início da lista");
 System.out.println("2 - Inserir no fim da lista");
 System.out.println("3 - Consultar a lista do início ao fim");
 System.out.println("4 - Consultar a lista do fim ao início");
 System.out.println("5 - Remover da lista");
 System.out.println("6 - Esvaziar a lista");
 System.out.println("7 - Sair");
 System.out.print("Digite sua opção: ");
 op = entrada.nextInt();
 if (op < 1 || op > 7) {
 System.out.println("Opção inválida!!");
 } else {
 if (op == 1) {
 System.out.println("Digite o número a ser inserido no início da lista");
 LISTA novo = new LISTA();
 novo.num = entrada.nextInt();
 if (inicio == null) {
 // a lista esta vazia e o elemento inserido será o primeiro e o último da lista
 inicio = novo;
 fim = novo;
 novo.prox = null;
 novo.ant = null;
 } else {
 // a lista já contém elementos e o novo elemento será inserido no início da lista
 novo.prox = inicio;
 inicio.ant = novo;
 novo.ant = null;
 inicio = novo;
 }
 System.out.println("Número inserido no início da lista!!");
 }
 if (op == 2) {
 System.out.println("Digite o número a ser inserido no fim da lista: ");
 LISTA novo = new LISTA();
 novo.num = entrada.nextInt();
 if (inicio == null) {
 // a lista estava vazia e o elemento inserido será o primeiro e o último
 inicio = novo;
 fim = novo;
 novo.prox = null;
 novo.ant = null;
 } else {
 // a lista já contém elementos e o novo elemento será inserido no fim da lista
 fim.prox = novo;
 novo.ant = fim;
 novo.prox = null;
 fim = novo;
 }
 System.out.println("Número inserido no fim da lista!!");
 }
 if (op == 3) {
 if (inicio == null) {
 // a lista está vazia
 System.out.println("Lista vazia!!");
 } else {
 // a lista contém elementos e estes serão mostrados do início ao fim
 System.out.println("\nConsultando a lista do início ao fim\n");
 aux = inicio;
 while (aux != null) {
 System.out.print(aux.num + " ");
 aux = aux.prox;
 }
 }
 }
 if (op == 4) {
 if (inicio == null) {
 // a lista está vazia
 System.out.println("Lista vazia!!");
 } else {
 // a lista contém elementos e estes serão mostrados do fim ao início
 System.out.println("\nConsultando a lista do fim ao início\n");
 aux = fim;
 while (aux != null) {
 System.out.print(aux.num + " ");
 aux = aux.ant;
 }
 }
 }
 if (op == 5) {
 if (inicio == null) {
 // a lista está vazia
 System.out.println("Lista vazia!!");
 } else {
 // a lista contém elementos e o elemento a ser removido deve ser digitado
 System.out.print("\nDigite o elemento a ser removido: ");
 numero = entrada.nextInt();
 // todos as ocorrências da lista, iguais ao número digitado serão removidas
 aux = inicio;
 achou = 0;
 while (aux != null) {
 if (aux.num == numero) {
 // o número digitado foi encontrado na lista e será removido
 achou = achou + 1;
 if (aux == inicio) {
 // o número a ser removido é o primeiro da lista
 inicio = aux.prox;
 if(inicio != null) {
 inicio.ant = null;
 }
 aux = inicio;
 } else if (aux == fim) {
 // o número a ser removido é o último da lista
 fim = fim.ant;
 fim.prox = null;
 aux = null;
 } else {
 // o número a ser removido está no meio da lista
 aux.ant.prox = aux.prox;
 aux.prox.ant = aux.ant;
 aux = aux.prox;
 }
 } else {
 aux = aux.prox;
 }
 }
 if (achou == 0) {
 System.out.println("Número não encontrado");
 } else if (achou == 1) {
 System.out.println("Número removido 1 vez");
 } else {
 System.out.println("Numero removido " + achou + " vezes");
 }
 }
 }
 if (op == 6) {
 if (inicio == null) {
 // a lista está vazia
 System.out.println("Lista vazia!!");
 } else {
 // a lista será esvaziada
 inicio = null;
 System.out.println("Lista esvaziada");
 }
 }
 
 }
 
 } while (op != 7);
 }
}
3.2.Listas Circulares
A busca em uma lista ordenada, vista anteriormente, pode ser considerada
pouco eficiente quando comparada às outras buscas anteriormente mencionadas. Uma
pequena modificação na estrutura física da lista pode ser de grande auxílio: obrigar o
último nó da lista a apontar para o nó-cabeça, criando uma lista circular encadeada.
 
Desta forma, o teste de fim de lista nunca é satisfeito. A preocupação passa a
ser um critério de parada que possa ser incorporado ao teste da busca propriamente dita.
A solução é colocar a chave procurada no nó-cabeça, de forma que uma resposta
positiva seja sempre encontrada.
4.Referencias Bibliográficas
[1] http://manfred.com.br/index.php/bsi/estrutura-de-dados-i/132-aula-04-listas-simplesmente-encadeada-duplamente-encadeada-e-circular-em-java
[2] http://www.ebah.com.br/content/ABAAAfL0YAK/aula18-listas-encadeadas-ii-busca-linear-binaria
[3] http://www.uems.br/docentes/rmmuller/listalin.pdf
[4] https://www.youtube.com/watch?v=c42_2KnQNpY
[5] https://www.youtube.com/watch?v=ekMsPHwzzlE
[
6] https://www.youtube.com/watch?v=vqJziTFXrvU
[7] https://www.youtube.com/watch?v=MydQEx9BeK8
[8] http://www.inf.ufes.br/~pdcosta/ensino/2012-1-estruturas-de-dados/slides/Aula9(listas).pdf
				
				
				Índice
1. Listas Lineares
2. Alocação sequencial
2.1. Lista com alocação sequencial e estática
2.2. Listas com alocação não sequencial e dinâmica
3. Listas Encadeadas
3.1. Listas Duplamente Encadeadas
3.2. Listas Circulares
4.Referencias Bibliográficas
		
	Trabalho de Listas Lineares 	
	prof: Diassis Rodrigo
Nome: Renan Longhi Marmo 			RA: 2014016871
Nome: Rinaldo Gama				RA: 2014016781
								Data : 19/11/2014