Estrutura de Dados Avançados

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Estrutura de Dados Avançados
Prof Diogo Rafael da Silva
ans.diogo@hotmail.com
Introdução
Listas
Declarações
Inserção
Remoção
Duplamente Encadeadas
Circulares
Filas
Pilhas
Arvores
Listas
Listas
Acompanhar página 189
Perguntas?
imprimir o número 1
Estrutura de Dados Avançados
Prof Diogo Rafael da Silva
ans.diogo@hotmail.com
Introdução
Listas
Declarações
Inserção
Remoção
Duplamente Encadeadas
Circulares
Filas
Pilhas
Arvores
Listas
lista ou sequência é uma estrutura de dados abstrata que implementa uma coleção ordenada de valores, onde o mesmo valor pode ocorrer mais de uma vez. Uma instância de uma lista é uma representação computacional do conceito matemático de uma sequência finita, que é, uma tupla. Cada instância de um valor na lista normalmente é chamado de um item, entrada ou elemento da lista. Se o mesmo valor ocorrer várias vezes, cada ocorrência é considerada um item distinto.
Listas
As chamadas estruturas de lista estática' permitem apenas a verificação e enumeração dos valores. Uma lista mutável ou dinâmica pode permitir que itens sejam inseridos, substituídos ou excluídos durante a existência da lista.
Listas
Muitas linguagens de programação fornecem suporte para tipos de dados lista e possuem sintaxe e semântica especial para listas e operações com listas. Uma lista pode frequentemente ser construída escrevendo-se itens em sequência, separados por vírgulas, ponto e vírgulas ou espaços, dentro de um par de delimitadores como parênteses '()', colchetes '[]', chaves '{}' ou chevrons '<>'. Algumas linguagens podem permitir que tipos lista sejam indexados ou cortados como os tipos vetor. Em linguagens de programação orientada a objetos, listas normalmente são fornecidas como instâncias ou subclasses de uma classe "lista" genérica. Tipos de dado lista são frequentemente implementados usando arrays ou listas encadeadas de algum tipo, mas outras estruturas de dados podem ser mais apropriadas para algumas aplicações. Em alguns contextos, como em programação Lisp, o termo lista pode se referir especificamente à lista encadeada em vez de um array.
Listas
Numa lista encadeada existem dois campos. Um campo reservado para colocar o dado a ser armazenado e outro campo para apontar para o próximo elemento da lista. Normalmente a implementação é feita com ponteiros.
Listas
Listas
Uma lista encadeada(ligada) é uma estrutura de dados linear e dinâmica. Ela é composta por células que apontam para o próximo elemento da lista. Para "ter" uma lista ligada/encadeada, basta guardar seu primeiro elemento, e seu último elemento aponta para uma célula nula. 
Listas
O esquema a seguir representa uma lista ligada/encadeada com 5 elementos:
Célula 1 ----> Célula 2 ----> Célula 3 ----> Célula 4 ----> Célula 5 ----> (Nulo)
Listas
Para inserir dados ou remover dados é necessário ter um ponteiro que aponte para o 1º elemento e outro que aponte para o fim, porque se queremos inserir ou apagar dados que estão nessas posições, a operação é rapidamente executada. Caso seja necessário editar um nó que esteja no meio da lista haverá uma busca pela posição desejada.
Listas
Vantagens
Desvantagens
A inserção ou remoção de um elemento na lista não implica a mudança de lugar de outros elementos;
Não é necessário definir, no momento da criação da lista, o número máximo de elementos que esta poderá ter. Ou seja, é possível alocar memória "dinamicamente", apenas para o número de nós necessários.
A manipulação torna-se mais "perigosa" uma vez que, se o encadeamento (ligação) entre elementos da lista for mal feito, toda a lista pode ser perdida
Para aceder ao elemento na posiçãonda lista, deve-se percorrer osn - 1anteriores.
Listas
Exemplo em C
typedefstructNo_st{//métodostruct, mas a inclusão dotypedefsimplifica
intnumero;
structNo *prox;
}No;/*A partir deste momento, a variável do tipo No está disponível, sendo o seu acesso feito como a uma qualquer estrutura de dados.*/
Listas
Exemplo em C
intmain(void){
No exemplo;/*A variável exemplo é do tipo no*/
No *pexemplo;/*A variávelpexemplodo tipo apontador para no*/
exemplo.numero = 1;
pexemplo= &exemplo;
printf("%d\n", exemplo.numero);//imprimir o número 1
printf("%d\n",pexemplo->numero);//imprimir o número 1
return(1);
}
Listas
Perguntas?
Pilhas
Filas
Arvores
Perguntas?