Lista Linear
Base para outras estruturas
• Conceito de Lista
A estrutura que permite representar um
conjunto de dados de forma a preservar
a relação de ordem linear (ou total) entre
eles é a lista linear. Uma lista linear é
composta de nós, os quais podem
conter, cada um deles, um dado
primitivo ou um dado composto.
(VELOSO,P.,SANTOS,C.,
AZEREDO,P.,
FURTADO, A., 1983,79)
Nó ou nodo– é um item da lista.
Comprimento ou tamanho de uma lista
Lista vazia é lista sem nó
Formas de agrupar elementos de uma Lista Linear na MP
Sequencial
Encadeada
O armazenamento
é estático ou
dinâmico?
Processando informações
Estática
- reservada durante a programação.
Dinâmica
- reservada durante a execução.
Sequencial - elementos alocados de forma
contígua.
Encadeada - os elementos não são alocados de
forma contígua.
Indexado - para lista sequencial.
Sequencial - para lista encadeada
Dizemos que uma Lista é linear porque
cada nodo tem somente um sucessor.
Assim como o vetor, tem somente uma
dimensão. Entretanto, a Lista pode ser
implementada de forma encadeada e a
inserção e remoção de seus elementos
dependerá da forma de acesso.
Pilha - A inserção e a remoção é sempre
realizada em um extremo da lista.
Fila – A inserção é feita em um extremo e a
remoção em outro.
Fila Dupla – DEQUE( Double-Ended QUEue),
significando fila de extremidade dupla
Fila Dupla – FDER( Fila De Entrada Restrita),
significando que o elemento pode ser
recuperado de
qualquer extremidade, mas
inserido só em uma.
Fila Dupla – FDSR( Fila De Saída Restrita),
significando que o elemento pode ser inserido
em qualquer extremidade, mas recuperado só
em uma.
Operações realizadas com Listas Lineares
Criar uma Lista;
Verificar se a Lista esta vazia;
Verificar se a Lista esta cheia;
Inserir elemento na Lista;
Remover elemento da Lista;
Exibir o tamanho da lista;
Retornar a posição de um elemento da
Lista;
Operações realizadas com Listas Lineares
Exibir a Lista;
Exibir frequencia;
Pesquisar um elemento na Lista;
Alterar um elemento da Lista;
Ordenar a Lista;
Inserir ordenado na Lista;
Concatenar Lista;
Dividir Lista;
Exemplo
Este exercício terá uma LISTA com 5 nós. Os
elementos desta LISTA serão inteiros e códigos
de produtos. Foram colocados, no menu, 4
trechos: Inserir elementos na Lista, Exibir os
elementos da Lista, Exibir um elemento da Lista
e Exibir o tamanho da Lista. Para os três
primeiros, foram criadas funções, mas, para o
último, por ser extremamente simples, não.
As
Funções
O
Código
TODAS
AS
FUNÇÕES
VISTAS
ANTERIORMENTE,
DEVERÃO
SE
COLOCADAS DEPOIS DA CHAVE QUE
FECHA O PROGRAMA.
Mais
Funções