Estrutura de Dados - Aula 05

Prévia do material em texto

ESTRUTURA DE DADOS
Aula 5 – Listas Lineares
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
Atenção aos Temas Principais dessa Aula
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
Conteúdo Programático desta aula
Compreender o conceito da Estruturas de Dados
Lista Linear;
 Identificar as diferenas entre Lista Sequencial e
Encadeada;
Compreender e usar vrias operaões realizadas com
Lista Linear Sequencial;
Aplicar os conceitos de ordenaão e pesquisa com
Lista Linear Sequencial;
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
Direto ao Assunto
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
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).
Conceito de Lista Linear
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
PILHA(Last In First Out) - A inserção e a remoção são sempre
realizadas na mesma extremidade.
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
FILA(First In First Out) – A inserção é feita em uma
extremidade e a remoção, em outra.
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
Fila Dupla – DEQUE( Double-Ended QUEue), significando fila de
extremidade dupla
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
Fila Dupla – FDER( Fila De Entrada Restrita), significando que
o elemento pode ser recuperado de qualquer extremidade,
mas inserido só em uma..
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
Fila Dupla – FDSR( Fila De Saída Restrita), significando que o
elemento pode ser inserido em qualquer extremidade, mas
recuperado só em uma.
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
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)
Conceito de Lista Linear
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
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)
Conceito de Lista Linear
Cada Nó, ou nodo, só tem um sucessor
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
Nó ou nodo – é um item da lista
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
Nó ou nodo – é um item da lista
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
Comprimento de uma lista – número de nós
Nó ou nodo – é um item da lista
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
Comprimento de uma lista – número de nós
Nó ou nodo – é um item da lista
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
Comprimento de uma lista – número de nós
Lista vazia - sem nós
Nó ou nodo – é um item da lista
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
No momento da compilação
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
Durante a execução
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
Alocação contígua
Facilidade para calcular o endereço do próximo
Desvantagem: inserir, ou remover elemento, implica
em deslocamento
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
Alocação não contígua
Facilidade para inserir, ou remover elemento
Desvantagem: percorrer toda a lista pra encontrar o
elemento
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
DESENVOLVEDOR DECIDE!
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
 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;
Operações realizadas com Listas Lineares
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
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
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
Vamos praticar!
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
Este exercício terá uma com 5 nós. Os elementos dessa
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.
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
Função insere
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
Função exibe
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
Função elemento
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
LISTAS LINEARES – Aula5
Função ordena
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
Chama a função ordena
Coloque no case
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
Função busca Sequencial
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
Chama a função busca Sequencial
Coloque no case
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
Código
#include <iostream>
#include <cstdlib>
using namespace std;
void insere(int codigo[], int &t, int tamanho);
void exibe(int codigo[], int t);
void elemento(int codigo[],int t);
void ordena(int codigo[],int t);
int buscaSequencial(int codigo[], int cod, int t);
int main()
{
int tam, codigoProduto[5],op, cod, posicao;
//Inicialização
tam = 0;
do
{
system("cls");
cout<<"\nMenu - LISTA \n";
cout<<"\n0- Reinicar a LISTA";
cout<<"\n1- Inserir codigo na LISTA";
cout<<"\n2- Exibir LISTA";
cout<<"\n3- Exibe tamanho da LISTA";
cout<<"\n4- Exibe um elemento da
lista";
cout<<"\n5-Ordena lista";
cout<<"\n6- Procura elemento na lista";
cout<<"\n7- Sair";
cout<<"\nOpcao: ";
cin>>op;
system("cls");
1 2
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
Código
switch(op)
{
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";
}
3
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
Código
cout<<"\n\n"; system("pause");
}while(op !=7);
}
void insere(int codigo[], int &t, int tamanho)
{
int prod;
if (tamanho == t)
cout << "\nAtencao! Lista cheia\n";
else
{
cout << "\nDigite codigo do produto a ser inserido: ";
cin >> prod;
codigo[t] = prod;
t++;
}
}
void exibe(int codigo[], int t)
{
int x;
if (t == 0)
cout << "\nAtencao! Lista vazia\n";
else
cout<<"\nRelacao dos Codigos\n";
for(x = 0; x < t; x++)
cout << "\n" <<x+1<<" - " << codigo[x];
}
4
5
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
Código
void elemento(int codigo[], int t)
{
int prod,posicao;
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";
}
6
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
Código
int buscaSequencial(int codigo[], int cod, int t)
{
int x;
if (t == 0)
return -1; // testa lista vazia
for (x = 0; x < t; x++)
if( codigo[x] == cod) return x;
//retorna O deslocamento do endereco base
return -2; //percorreu toda a lista e nÃo achou
}
void ordena(int codigo[], int t)
{
int x,y, aux, temp;
if(t == 0)
cout << "\nAtencao! Lista vazia\n";
else
{ for(x=0; x<t-1; x++)
{ aux=x;
for(y=x+1; y<t; y++)
if(codigo[aux]>codigo[y]) aux=y;
temp=codigo[aux];
codigo[aux]=codigo[x];
codigo[x]=temp;
} cout<<"\nLista Ordenada\n";
}
}
7
8
ESTRUTURA DE DADOS
LISTAS LINEARES – Aula5
Resumindo