ESTRUTURA DE DADOS
Aula 5 – Listas Lineares
ESTRUTURA DE DADOS
Atenção aos Temas Principais
dessa Aula
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
Conteúdo Programático
desta aula
Compreender o conceito da Estruturas de Dados –
Lista Linear;
Identificar as diferenças entre Lista Sequencial e
Encadeada;
Compreender e usar várias operações realizadas
com Lista Linear Sequencial;
Aplicar os conceitos de ordenação e pesquisa com
Lista Linear Sequencial;
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
Direto ao
Assunto
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
Conceito de Lista
Linear
Uma lista é uma forma de agrupar itens com a
finalidade de melhorar sua manipulação.
… É a propriedade sequencial de uma lista
linear que dá a base para sua definição e seu
uso.
De acordo como os dados são inseridos, ou
removidos, da lista é que é sugerida uma
classificação(MORAES, C.R. 2011, p27-28).
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
PILHA(Last In First Out) - A inserção e a remoção
são sempre realizadas na mesma extremidade.
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
FILA(First In First Out) – A inserção é feita em uma
extremidade e a remoção, em outra.
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
Fila Dupla – DEQUE( Double-Ended QUEue),
significando fila de extremidade dupla .
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
Fila Dupla – FDER( Fila De Entrada Restrita),
significando que o elemento pode ser recuperado
de qualquer extremidade, mas inserido só em
uma.. LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
Fila Dupla – FDSR( Fila De Saída Restrita),
significando que o elemento pode ser inserido em
qualquer extremidade, mas recuperado só em
uma. LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
Conceito de Lista
Linear
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)
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
Conceito de Lista
Linear
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)
Cada Nó, ou nodo, só tem um
sucessor
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
Nó ou nodo – é um item
da lista
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
Nó ou nodo – é um item
da lista
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
Nó ou nodo – é um item
da lista
Comprimento de uma lista –
número de nós
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
Nó ou nodo – é um item
da lista
Comprimento de uma lista –
número de nós
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
Nó ou nodo – é um item
da lista
Comprimento de uma lista –
número de nós
Lista vazia - sem
nós
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
No momento da
compilação
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
Durante a
execução
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
• Alocação contígua
• Facilidade para calcular o endereço do
próximo
• Desvantagem: inserir, ou remover elemento,
implica em deslocamento
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
• Alocação não contígua
• Facilidade para inserir, ou remover elemento
• Desvantagem: percorrer toda a lista pra
encontrar o elemento
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
DESENVOLVEDOR
DECIDE!
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
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 frequência; LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
Operações realizadas com Listas
Lineares
Pesquisar um elemento na Lista;
Alterar um elemento da Lista;
Ordenar a Lista;
Inserir ordenado na Lista;
Concatenar Lista;
Dividir Lista;
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
Vamos
praticar!
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
Este exercício terá uma LISTA com 5 nós. Os
elementos dessa 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.
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
Função
insere
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
Função
exibe
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
Função
elemento
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
Função
ordena
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
Chama a função
ordena
Coloque no
case
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
Função busca
Sequencial
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
Chama a função busca
Sequencial
Coloque no
case
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
Códig
o do
#include <iostream>
#include <cstdlib> 1 { 2
using namespace std; system("cls");
void insere(int codigo[], int &t, int cout<<"\nMenu - LISTA \n";
tamanho); cout<<"\n0- Reinicar a LISTA";
void exibe(int codigo[], int t); cout<<"\n1- Inserir codigo na
void elemento(int codigo[],int t); LISTA";
void ordena(int codigo[],int t); cout<<"\n2- Exibir LISTA";
int buscaSequencial(int codigo[], int cout<<"\n3- Exibe tamanho da
cod, int t); LISTA";
int main() cout<<"\n4- Exibe um elemento
{ da lista";
int tam, codigoProduto[5],op, cod, cout<<"\n5- Ordena lista";
posicao; cout<<"\n6- Procura elemento
//Inicialização na lista";
tam = 0; cout<<"\n7- Sair";
cout<<"\nOpcao: ";
cin>>op;
system("cls");
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
Códig
o switch(op)
3
{
case 0: //reinicialiação
tam = 0; break;
case 1: insere(codigoProduto,tam, 5); break;
case 2: exibe(codigoProduto,tam); break;
case 3: cout<<"\nTamanho da Lista: "<<tam;break;
case 4: elemento(codigoProduto, tam);break;
case 5: ordena(codigoProduto, tam); break;
case 6: cout << "\nQual codigo a ser procurado? "; cin >> cod;
posicao = buscaSequencial(codigoProduto,cod,tam);
if(posicao == -1) cout << "\nAtencao! Lista vazia\n";
else if (posicao == -2)cout << "\nAtencao! Codigo nao
encontrado\n";
else cout << "\nCodigo encontrado na posicao: " <<
posicao+1<<"\n";
break;
case 7: cout<<"\nFinalizando o programa da LISTA\n";break;
default: cout<<"\nOpcao invalida\n";
}
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
Códig
o
cout<<"\n\n"; system("pause"); void exibe(int codigo[], int t)
4
}while(op !=7); { 5
} int x;
void insere(int codigo[], int &t, int tamanho) if (t == 0)
{
cout << "\nAtencao! Lista vazia\
int prod; n";
if (tamanho == t) else
cout << "\nAtencao! Lista cheia\n";
cout<<"\nRelacao dos Codigos\
else n";
{ for(x = 0; x < t; x++)
cout << "\nDigite codigo do produto a ser
cout << "\n" <<x+1<<" - " <<
inserido: ";
codigo[x];
cin >> prod;
}
codigo[t] = prod;
t++;
}
}
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
Códig
o
void elemento(int codigo[], int t)
{
int prod,posicao;
6
if(t == 0)
{ cout << "\nAtencao! Lista vazia\n";return;}
cout << "\nQual a posicao que deseja? ";
cin >> posicao;posicao=abs(posicao);
posicao--;
if (posicao >= t )
cout << "\nAtencao! Nenhum codigo armazenado ou posicao
inexistente\n";
else
cout << "\nCodigo na posicao: " << codigo[posicao]<<"\n";
}
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
Códig
o
void ordena(int codigo[], int t)
{ 7 int buscaSequencial(int codigo[], int cod,
int t)
int x,y, aux, temp;
{
if(t == 0) 8
int x;
cout << "\nAtencao! Lista vazia\n";
if (t == 0)
else
return -1; // testa lista vazia
{ for(x=0; x<t-1; x++)
for (x = 0; x < t; x++)
{ aux=x;
if( codigo[x] == cod) return x;
for(y=x+1; y<t; y++)
//retorna O deslocamento do endereco
if(codigo[aux]>codigo[y]) base
aux=y;
return -2; //percorreu toda a lista e nÃo
temp=codigo[aux]; achou
codigo[aux]=codigo[x]; }
codigo[x]=temp;
} cout<<"\nLista Ordenada\
n";
}
}
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
Resumindo
LISTAS LINEARES – Aula5
