Estrutura de

Dados
Prof. Heberht Dias
Ementa do
Curso
1 Ordenaçã
o
2

Lista
3 Pilh
a
4 Fila

5 Espalhamen
to

6 Árvore
7 Complexida
de

Estrutura de Dados 2 / 40
Ementa do
Curso
1 Ordenaçã
o
2

Lista
3 Pilh
a
4 Fila

5 Espalhamen
to

6 Árvore
7 Complexida
de

Estrutura de Dados 3 / 40
Ordenaçã
o

Definição
Uma ordenação consiste em colocar os elementos de um
conjunto de dados de forma organizada (ascendente ou
descendente) de acordo seus valores.

Ordenação por inserção (Insert

Sort); Ordenação por seleção
(Select Sort); Ordenação por
flutuação (Bubble Sort);
Ordenação por mistura (Merge
Sort); e Ordenação rápida (Quick
Sort).
Estrutura de Dados 4 / 40
Ordenação por
Inserção

Eficiente quando aplicado a um pequeno número de

elementos; Percorre um vetor de elementos da
esquerda para a direita;
À medida que avança vai deixando os elementos mais à
esquerda ordenados; e
Assemelha-se a ordenação de cartas de um jogo de
baralho.

Estrutura de Dados 5 / 40
Ordenação por
Seleção

Baseado em passar sempre o menor valor do vetor para

a primeira posição;
Depois o de segundo menor valor para a segunda
posição; e Assim é feito sucessivamente com os (n − 1)
elementos restantes.

Estrutura de Dados 6 / 40
Ordenação por
Flutuação

A ideia é percorrer o vector diversas vezes;

A cada passagem fazendo flutuar para o topo o maior
elemento da sequência; e
Essa movimentação lembra a forma como as bolhas em um
tanque de água procuram seu próprio nível.

Estrutura de Dados 7 / 40
Ordenação por
Mistura

Do tipo dividir-para-conquistar;
Dividir: Dividir os dados em subsequências pequenas; e
Conquistar: Classificar as metades recursivamente
aplicando o merge sort.

Estrutura de Dados 8 / 40
Ordenação
Rápida

Escolha um elemento da lista, denominado pivô;

Rearranje a lista de forma que todos os elementos
anteriores ao pivô sejam menores que ele;
Ao fim do processo o pivô estará em sua posição final e
haverá duas sublistas não ordenadas; e
Recursivamente ordena as sublistas de elementos menor
e a maior. sort.

Estrutura de Dados 9 / 40
Ementa do
Curso
1 Ordenaçã
o
2

Lista
3 Pilh
a
4 Fila

5 Espalhamen
to

6 Árvore
7 Complexida
de

Estrutura de Dados 10 / 40
List
a

Lista ligada;
Lista duplamente
ligada; e Lista circular.

Estrutura de Dados 11 / 40
Lista
Ligada

Definição
É uma estrutura de dados que implementa uma coleção de
dados ligados (encadeados) de forma dinâmica em um único
sentido.

Ilustraçã
o

Estrutura de Dados 12 / 40
Lista Duplamente
Ligada

Definição
É uma estrutura de dados que implementa uma coleção de
dados ligados de forma dinâmica em sentido duplo.

Ilustraçã
o

Estrutura de Dados 13 / 40
Lista
Circular

Definição
É uma estrutura de dados que implementa uma coleção de
dados ligados de forma dinâmica em um único sendito, no qual
o final da lista corresponde o início da própria lista.

Ilustraçã
o

Estrutura de Dados 14 / 40
Ementa do
Curso
1 Ordenaçã
o
2

Lista
3 Pilh
a
4 Fila

5 Espalhamen
to

6 Árvore
7 Complexida
de

Estrutura de Dados 15 / 40
Pilh
a
Definição
É uma estrutura de dados baseada no princípio LIFO (Last In,
First Out), na qual os dados que foram inseridos primeiro na
pilha serão os últimos a serem removidos.

Ilustração

Estrutura de Dados 16 / 40
Ementa do
Curso
1 Ordenaçã
o
2

Lista
3 Pilh
a
4 Fila

5 Espalhamen
to

6 Árvore
7 Complexida
de

Estrutura de Dados 17 / 40
Fil
a

Fila simples; e
Fila com
prioridade.

Estrutura de Dados 18 / 40
Fil
a
Definição
É uma estrutura de dados baseada no princípio FIFO (First In,
First Out), em que os elementos inseridos no início são os
primeiros a serem removidos.

Ilustração

Estrutura de Dados 19 / 40
Fila com
Prioridade
Definição
É uma estrutura de dados em que os elementos são inseridos
em ordem de prioridade.

Ilustração

Estrutura de Dados 20 / 40
Ementa do
Curso
1 Ordenaçã
o
2

Lista
3 Pilh
a
4 Fila

5 Espalhamen
to

6 Árvore
7 Complexida
de

Estrutura de Dados 21 / 40
Tabela de
Espalhamento
Definição
É uma estrutura de dados especial, que associa chaves de
pesquisa a valores.

Ilustração

Estrutura de Dados 22 / 40
Ementa do
Curso
1 Ordenaçã
o
2

Lista
3 Pilh
a
4 Fila

5 Espalhamen
to

6 Árvore
7 Complexida
de

Estrutura de Dados 23 / 40
Árvor
e
Definição
É uma estrutura de dados em que cada elemento tem
um ou mais elementos associados.

Ilustraçã
o

Estrutura de Dados 24 / 40
Inserir um
Nó

Ilustraçã
o

Estrutura de Dados 25 / 40
Excluir um Nó
Folha

Ilustraçã
o

Estrutura de Dados 26 / 40
Excluir um Nó com uma
Subárvore

Ilustraçã
o

Estrutura de Dados 27 / 40
Excluir um Nó com duas
Subárvores

Ilustração: Caso 1

Ilustração:
Caso 2

Estrutura de Dados 28 / 40
Árvores
Balanceadas

Árvore AVL; e
Árvore Rubro
Negra.

Estrutura de Dados 29 / 40
Ementa do
Curso
1 Ordenaçã
o
2

Lista
3 Pilh
a
4 Fila

5 Espalhamen
to

6 Árvore
7 Complexida
de

Estrutura de Dados 30 / 40
Análise de
Algoritmos

Definição
É um mecanismo para entender e avaliar um algoritmo em
relação aos critérios desempenho, bem como saber aplica-los
à problemas práticos.

Empírica;
ou
Matemátic
a.

Estrutura de Dados 31 / 40
Análise
Assintótica

Definição
É um método de descrever o comportamento de limites de
algoritmos quando aplicados a um volume muito grande de
dados de entrada.

Big O (Pior dos casos);

Big Ω (Melhor dos
casos); e Big Θ (Caso
médio).

Estrutura de Dados 32 / 40
Crescimento de Função no
Big O

O(1)
O(log N)
O(N)
O(N log
N)
O(N2 )
O(2N )
O(N!)

Estrutura de Dados 33 / 40
Função
O(1)

Descrição
Maior parte das instruções são executadas apenas uma ou
algumas vezes, independente de N – tempo de execução
constante.

Exempl
odef c ons t ant e
( n) :
pr i nt ( n)

Estrutura de Dados 34 / 40
Função O(log
N)
Descrição
Ocorre em programas que resolve um problema maior
transformado-o em uma série de subproblemas menores, assim
reduzindo o tamanho do problema por uma certa constante
fracionária a cada passo – tempo de execução logarítmico.
Sempre que N dobra, log N aumenta de uma certa constante,
mas log N não dobra até que N tenha sido aumentado para N2.

Exempl
o
def bus c a_bi nar i a ( n, ar r ay ) :
met ade = l en
( ar r ay ) //2 i f ( n ==
ar r ay [ met ade ] )
re t u r n metade
el i f ( n > ar r ay [ met ade ] ) :
re t u r n b u s c a _ b i n a r i a ( n , a r r a y
[ metade : ] ) el i f ( n < ar r ay [ met ade ] ) :
re t u r n b u s c a _ b i n a r i a ( n , a r r a y [ :
metade - 1 ] )

Estrutura de Dados 35 / 40
Função O(N
)

Descrição
Acontece quando uma pequena quantidade de processamento
deve ser feito para cada elemento da entrada – tempo de
execução linear. Esta é a situação ótima para um algoritmo que
deve processar N entradas (ou gerar N saídas).

Exempl
o
def l i near ( n) ;
f or i r ang e
( n) :
pr i nt ( i )

Estrutura de Dados 36 / 40
Função O(N log
N)

Definição
Ocorre em algoritmos que quebra o problema principal em
subproblemas menores, resolvendo-os e combinando as soluções
– tempo de execução “linearítmico” ou N log N. Quando N
dobra o tempo de execução torna-se um pouco mais do que o
dobro.

Exemplo
Algoritmo de ordenação por mistura
(Merge Sort)

Estrutura de Dados 37 / 40
Função O(N
2)

Definição
Tipicamente representa algoritmos que processa todos os pares
de itens de dados – tempo de execução quadrático. Este tipo de
complexidade é aceitável apenas para problemas relativamente
pequenos. Quando N dobra o tempo de execução aumenta 4
vezes.

Exempl
o def quandr at i c o
( n) ;
f or i r ang e ( n) :
f or j r ang e
( n) :
print(i, j)

Estrutura de Dados 38 / 40
Função O(2N
)

Definição
Corresponde a algoritmos que utilizam força-bruta na solução de
problemas
– tempo de execução exponencial. Algoritmos com esta
performance são impraticáveis. Sempre que N dobra o tempo
de execuçãoo é elevado ao quadrado.

Exemplo
Encontrar a solução exata para o Problema do cacheiro
viajante usando programação dinâmica.

Estrutura de Dados 39 / 40
Função
O(N !)

Descrição
Corresponde a algoritmos que utilizam força-bruta na solução de
problemas
– tempo de execução fatorial. Algoritmos com esta
performance são impraticáveis.

Exemplo
Encontrar a solução exata para o Problema do caixeiro
viajante usando busca por força bruta.

Estrutura de Dados 40 / 40