Estruturas de Dados - Lista Linear

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

*
*
ESTRUTURAS DE DADOS – AULA 5
ANITA MACIEL
Rio de Janeiro, 2011
*
*
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ó
*
*
A alocação é contígua ou não contígua?
*
*
Formas de agrupar elementos de uma Lista Linear na MP
Sequencial
Encadeada
*
*
A alocação é estática ou dinâmica?
*
*
*
*
Processando informações
Estática - definida durante a programação
 (reservada no início da execuçã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.
*
*
Dizemos que uma Lista é linear porque cada nodo tem somente um sucessor.
Entretanto, a Lista pode ser implementada de forma encadeada e a inserção, ou 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;
*
*
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; 
Operações realizadas com Listas Lineares
*
*
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. 
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
TODAS AS FUNÇÕES VISTAS ANTERIORMENTE, DEVERÃO SER COLOCADAS DEPOIS DA CHAVE QUE FECHA A FUNÇÃO main().
*
*
*
*
*
*
*
*
*
*
*
*
Reveja todos os conceitos desta aula.
Aprimore seus conhecimentos pesquisando no material didático e na bibliografia recomendada (procure na Biblioteca do campus ou na Biblioteca Virtual/ SIA).
Faça todos os exercícios.
*
*
Esteja sempre em contato com seu professor.
Não durma com dúvidas.
Assista a esta aula quantas vezes for necessário.
*
*
*