06_ListasLinearesEstaticas

Prévia do material em texto

LISTAS LINERAES ESTÁTICASLISTAS LINERAES ESTÁTICAS
.: ESTRUTURA DE DADOS :..: ESTRUTURA DE DADOS :.
André Macedo SantanaAndré Macedo SantanaAndré Macedo SantanaAndré Macedo SantanaAndré Macedo SantanaAndré Macedo SantanaAndré Macedo SantanaAndré Macedo Santana
andremacedo@ufpi.edu.br
• Uma lista linear agrupa informações referentes a um conjunto de elementos que,
de alguma forma, se relacionam entre si;
• Uma lista linear é um conjunto de n>=0 Nós L[1], L[2], ..., L[n] tais que suas
propriedades estruturais decorrem, unicamente, da posição relativa os Nós
dentro da sequencia linear:
• Se n>0, L[i] é o primeiro Nó;
ListasListas LinearesLineares EstáticasEstáticas
ConceitosConceitos
André M. Santana UFPI - CCN - DIEEstruturas de Dados
• Se n>0, L[i] é o primeiro Nó;
• Se 1 < k < L[k], o nó L[k] é precedido por L[k-1]
• As operações mais comuns em listas são a busca, a inclusão e a remoção de um
determinado elemento. Logo, estas implementações devem ser eficientes;
• Outras operações interessantes são: a alteração de um elemento da lista, a
combinação de duas ou mais listas em uma única, ordenação dos nós segundo
um determinado campo, a determinação do primeiro (ou do último) elemento, a
determinação da cardinalidade, dentre outras;
ListasListas LinearesLineares EstáticasEstáticas
• O vetor é a forma mais primitiva de representar diversos elementos agrupados e
o fato de um vetor ocupar um espaço contiguo na memória nos permite acessar
qualquer um dos seus elementos a partir do ponteiro para o primeiro elemento;
• Diz-se que um vetor é uma estrutura que possibilita o acesso randômico aos
elementos, pois podemos acessar qualquer elemento aleatoriamente;
ConceitosConceitos
André M. Santana UFPI - CCN - DIEEstruturas de Dados
Problema: dimensionamento
• Estrutura Lista:
• Operações primitivas:
EstruturaEstrutura e e OperaçõesOperações
ListasListas LinearesLineares EstáticasEstáticas
André M. Santana UFPI - CCN - DIEEstruturas de Dados
• Operações primitivas:
• acessar o k-ésimo nó da lista;
• inserir um novo nó após o k-ésimo elemento;
• inserir im nó no final da lista;
• remover o k-ésimo nó da lista;
• determinar o número de nós da lista;
• localizar o nó que contém um determinado valor;
• gerar uma sub-lista a partir de uma lista;
• concatenar duas listas;
• inverter uma lista;
• ordenar uma lista;
OperaçõesOperações
Iniciar lista
ListasListas LinearesLineares EstáticasEstáticas
André M. Santana UFPI - CCN - DIEEstruturas de Dados
Acessar elemento
Alterar elemento
OperaçõesOperações
ListasListas LinearesLineares EstáticasEstáticas
André M. Santana UFPI - CCN - DIEEstruturas de Dados
Inserir elemento
Inserir elemento no final
OperaçõesOperações
ListasListas LinearesLineares EstáticasEstáticas
André M. Santana UFPI - CCN - DIEEstruturas de Dados
Excluir elemento
Concatenar listas
OperaçõesOperações
Inverter uma lista
ListasListas LinearesLineares EstáticasEstáticas
André M. Santana UFPI - CCN - DIEEstruturas de Dados
Sub-lista
Limpar lista
Inserir em ordem
EXERCÍCIOEXERCÍCIO
ListasListas LinearesLineares EstáticasEstáticas
André M. Santana UFPI - CCN - DIEEstruturas de Dados