estrutura de dados
3270 palavras
14 páginas
ESTRUTURA DE DADOSLISTAS LINEARES
ORDENADAS
Prof. Dr. Daniel Caetano
2014 - 2
Objetivos
• Entender o que é uma lista ordenada
• Compreender o que muda com relação às listas não ordenadas
• Implementar o método Bubble-Sort
Material de Estudo
Material
Acesso ao Material
Apresentação
http://www.caetano.eng.br/
(Aula 4)
Material Didático
Estruturas de Dados – Capítulo 3, páginas 50 a 79
RECORDANDO...
Recordando...
• O que é uma lista linear sequencial?
• Para que servem/como funcionam:
– Inicializar
– Inserir
– Remover
– Listar
– Buscar
LISTA LINEAR SEQUENCIAL
ORDENADA
Listas Ordenadas
• O que muda da lista que vimos para a ordenada? • Como gerar uma lista ordenada?
• Princípio do Quarto Arrumado:
– Se colocarmos tudo no lugar....
– ...ele estará sempre “arrumado”!
• Ordem... Qual ordem?
– Crescente
– Descrescente
OPERAÇÕES EM LISTA
SEQUENCIAL
ORDENADA
Listas Ordenadas - Inicializar
• Uma lista ordenada sequencial é uma lista:
0
1
2
3
4
5
6
7
8
9 nota: ? ? ? ? ? ? ? ? ? ? n: ???
• Como inicializar esta lista? nota: 0 1 2 3 4 5
?
?
?
?
?
?
6
7
8
9
?
?
?
?
n: 0
• A inicialização é igual em qualquer lista!
Listas Ordenadas - Inicializar
• Exercício 1
– Crie um programa com uma lista de até 50 notas: float notas[50]; int n;
– Inicialize a lista...
– Como era mesmo?
• Podemos criar uma função que imprime os valores? listar(float v[], int n)
Listas Ordenadas - Inserir
• A lista inicial vazia...
0
1
2
3 nota: ? ? ? ?
4
5
6
7
8
9
?
?
?
?
?
?
n: 0
• Como inserir um elemento nela? Ex.: 11
• Crescente: procurar qual o primeiro elemento MAIOR que o atual...
• ...Se não achar, inserir no fim da lista
0
1
2
3
4
5
6
7
8
9 nota: 11 ? ? ? ? ? ? ? ? ? n: 1
Listas Ordenadas - Inserir
• Resultado:
0
1 nota: 11 ?
2
3
4
5
6
7
8
9
?
?