Técnico Infomatico

Estrutura de Dados e
Algoritmos I

Bem Vindo, Estudantes!

Adilson Gomes & Darmite
Denessechandra

5ª SEMANA
Lista
- Lista Simplesmente Ligada
- Lista Duplamente Ligada
- Lista Circular
- Manipulação de Listas

Objectivos
• Listas Conceito
• Lista Simplesmente Ligada
• Manuseamento de Listas Simplesmente Ligadas
• Listas Duplamente Ligadas
• Manuseamento de Listas Duplamente Ligadas
• Listas Circulares

Conceitos
• Lista ligada ou Lista encadeada é uma estrutura de dados linear e dinâmica. Ela é composta por uma sequência de nodos ou células que contém seus dados e também uma ou duas referências ("links") que apontam para o nodo anterior ou posterior.
• Há diversos modelos de lista ligadas como lista lista--encadeada simples,, listas duplamente ligadas e listas encadeadas simples circulares.. circulares • Para se "ter" uma lista ligada, basta guardar seu primeiro elemento, e seu último elemento aponta para uma célula nula. Conceitos - Exemplos
• Uma fila de uma ATM cujas pessoas não estão perfiladas Lista Simplesmente ligada

Manipulação da Lista
Simplesmente ligada
• criação da lista – Criar uma variável para conter a referencia para o primeiro objecto objecto/elemento /elemento da lista /* função de inicialização: retorna uma lista vazia */
Lista* inicializa (void)
{
return NULL;
}

Manipulação da Lista
Simplesmente ligada
• Criar um elemento de uma lista – é um objecto com uma posição para os dados e uma posição para a referência do próximo elemento da lista

Referência para o próximo elemento Valor

struct lista { int info; struct lista* prox;
};

Manipulação da Lista
Simplesmente ligada
• Inserir um elemento na lista – criar um elemento, passar a referencia do próximo a apontar para o próximo elemento que lhe vai seguir e, o elemento que apontava para este, passa a apontar para o novo elemento
/* inserção no início: retorna a lista actualizada */
Lista* insere