Estruturas de Dados - Funções e Passagem de Parâmetros

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

Estruturas de Dados 
 
Slides da Disciplina 
Prof. Rômulo Alencar 
romulo.alencar@live.estacio.br 
Prof. Rômulo Alencar Estruturas de Dados 2 
Conteúdo 
❑  Funções 
➥ Passagem de Parâmetros 
➥ Escopo 
➥ Recursividade 
❑  Complexidade Algorítmica 
❑  Tipo Abstrato de Dados 
❑  Estruturas de Dados 
➥ Classificação 
❑  Listas 
❑  Listas Sequenciais 
❑  Métodos de Ordenação 
❑  Busca binária 
❑  Pilhas 
❑  Filas 
❑  Ponteiros 
❑  Alocação Dinâmica 
❑  Listas Encadeadas 
➥ Listas Simplesmente 
Encadeadas 
➥ Listas Duplamente 
Encadeadas 
➥ Listas Circulares 
Prof. Rômulo Alencar Estruturas de Dados 3 
Funções 
❑  É possível dividir seu programa em blocos de código 
menores chamados funções 
➥ Funcionam como sub-programas 
➥ Permitem o conceito de encapsulamento 
➫ Escondem detalhes de implementação do usuário 
➥ Tornam seu código-fonte mais organizado 
➫ Evitam retrabalho 
➫ Facilitam manutenção 
➫ Reduzem pontos de falha 
Prof. Rômulo Alencar Estruturas de Dados 4 
Funções 
❑  Assim como as funções na matemática, as funções em 
linguagens de programação possuem 
➥ Argumentos/Parâmetros 
➫ Entrada 
➥ Valor de retorno 
➫ Saída 
❑  Uma função recebe dados de entrada dos argumentos 
(parâmetros), realiza um processamento e retorna um 
resultado como saída 
➥ Sub-programa! 
Processamento Entrada Saída 
Prof. Rômulo Alencar Estruturas de Dados 5 
Funções 
❑  Sintaxe de funções na linguagem de programação C++ 
 
 
tipo_de_dados nome_da_função(lista_de_parâmetros) 
{ 
 … //Lista de comandos 
 
 return valor_de_retorno; 
} 
Entrada 
Saída 
Tipo de dados da saída 
Processamento 
Prof. Rômulo Alencar Estruturas de Dados 6 
Funções 
❑  Exemplo 
➥ Função para calcular a soma de dois números inteiros 
➫ Entrada: dois números inteiros 
➫ Processamento: realizar a soma dos dois numeros 
➫ Saída: o resultado da soma 
 int soma(int x, int y) 
 { 
 int s; 
 s = x + y; 
 
 return s; 
 } 
Prof. Rômulo Alencar Estruturas de Dados 7 
Funções 
❑  Uma vez que a função está criada, ela pode ser 
chamada dentro do programa, inclusive dentro de outras 
funções 
 int subtrai(int x, int y) 
 { 
 int s; 
 s = soma(x, -y); 
 
 return s; 
 } 
Chamada de função 
Prof. Rômulo Alencar Estruturas de Dados 8 
Funções 
❑  Na linguagem de programação C++, todo programa é 
visto como uma função 
➥ Função main 
➥ SO “chama” o programa, passando parâmetros como 
entrada. Ao final da execução do programa, um valor é 
retornado ao SO. 
int main(int argc, const char * argv[]) 
{ 
 ... 
 
 return 0; 
} 
Entrada vinda do SO 
Saída retornada ao SO 
Prof. Rômulo Alencar Estruturas de Dados 9 
Passagem de Parâmetros 
❑  Funções podem receber parâmetros como entrada de 
dados 
❑  Parâmetros podem ser passados 
➥ Por valor 
➫ Apenas os valores das variáveis são passados para a 
função 
➥ Por referência 
➫ Os endereços das variáveis são passados para a 
função 
Prof. Rômulo Alencar Estruturas de Dados 10 
Passagem de Parâmetros 
❑  Passagem de parâmetros por valor 
➥ Funcionamento 
➫ Valores dos parâmetros são copiados para as variáveis da 
função que serão manipuladas 
➥ Exemplo 
➫ Admita a função 
➱ int f(int x, int y) 
➫ Uma chamada a ela da forma 
➱ a = f(b, c); 
➫ Acarretaria na cópia dos valores e b e c para as variáveis x 
e y. 
➱ A partir daí, a execução ocorre normalmente com x e y isoladas 
de b e c. 
➫ Efeito prático: caso os valores de x e y sejam alterados pela 
função, nada acontece com b e c, pois elas estão 
completamente isoladas! 
Prof. Rômulo Alencar Estruturas de Dados 11 
Passagem de Parâmetros 
❑  Passagem de parâmetros por referência 
➥ Funcionamento 
➫ Endereços dos parâmetros são copiados para as variáveis 
da função que serão manipuladas 
➥ Exemplo 
➫ Precisamos escrever uma função que inverta os valores de 
duas variáveis 
➫ Primeira ideia 
void inverte(int x, int y) 
{ 
 int aux = x; 
 x = y; 
 y = aux; 
} 
➫ Admitindo a chamada 
inverte(a, b); 
Prof. Rômulo Alencar Estruturas de Dados 12 
Passagem de Parâmetros 
❑  Passagem de parâmetros por referência 
➥ Exemplo 
➫ Caso executemos a função do jeito que está, o efeito 
esperado não acontecerá! 
➱ A passagem de parâmetros está sendo realizada por valor 
➱ As variáveis originais estarão isoladas do processamento da 
função 
➱ Ocorrerá a inversão dos valores de x e y, mas a e b continuam 
como estavam antes da execução 
➫ Precisamos reescrever a função utilizando passagem 
de parâmetros por referência! 
Prof. Rômulo Alencar Estruturas de Dados 13 
Passagem de Parâmetros 
❑  Passagem de parâmetros por referência 
➥ Exemplo 
➫ Segunda implementação 
void inverte(int &x, int &y) 
{ 
 int aux = x; 
 x = y; 
 y = aux; 
} 
➫ Admitindo a chamada 
inverte(a, b); 
Prof. Rômulo Alencar Estruturas de Dados 14 
Passagem de Parâmetros 
❑  Passagem de parâmetros por referência 
➥ Exemplo 
➫ Agora a execução será exatamente o esperado! 
➱ Os endereços de a e b serão passados como endereços de x e 
y 
➱ No final, a e b, referenciados por x e y, terão seus valores 
realmente invertidos! 
Prof. Rômulo Alencar Estruturas de Dados 15 
Passagem de Parâmetros 
❑  Passagem de parâmetros por referência 
➥ Sempre que for necessário alterar os valores dos 
parâmetros dentro de uma função 
➫ Deverá ser utilizada a passagem de parâmetros por 
referência! 
➥ Operador da passagem de parâmetros por referência 
➫ & 
➱ Na declaração do parâmetro da função 
Prof. Rômulo Alencar Estruturas de Dados 16 
Passagem de Parâmetros 
❑  Passagem de parâmetros por referência 
➥ Curiosidade 
➫ Na linguagem C, não existe formalmente passagem de 
parâmetros por referência 
➱ Tal recurso deve ser simulado com o uso de ponteiros 
➧  Parâmetros devem ser ponteiros 
➧  Chamadas de função devem passar endereços 
➱ Não confundir com C++, que usa o símbolo & para passagem 
de parâmetros por referência! 
➧  Chamadas de função são idênticas, independente do tipo 
de passagem de parâmetros 
Prof. Rômulo Alencar Estruturas de Dados 17 
Passagem de Parâmetros 
❑  Passagem de parâmetros por referência 
➥ Importante 
➫ Tanto C quanto C++ são linguagens com alta 
ortogonalidade, ou seja, usam poucos símbolos em sua 
representação 
➱ * 
➧  Declarar um ponteiro 
➧  Acessar o valor apontado por um ponteiro 
➧  Além do uso clássico de multiplicação 
➱ & 
➧  Acessar o endereço de uma variável 
➧  Passagem de parâmetros por referência 
➧  Além do uso clássico do “e” bit a bit 
Prof. Rômulo Alencar Estruturas de Dados 18 
Escopo 
❑  O escopo de uma variável é o local dentro do programa 
onde a variável 
➥ É considerada válida 
➥ “Existe” 
➥ Pode ser acessada 
❑  Fora de seu escopo, uma variável é inacessível 
➥ Ainda que continue alocada na memória 
Prof. Rômulo Alencar Estruturas de Dados 19 
Escopo 
❑  Na linguagem C++, temos variáveis com escopo 
➥ Global 
➫ São válidas no programa inteiro 
➫ Devem ser declaradas fora de qualquer função 
➥ Local 
➫ São válidas em locais específicos do programa 
➫ Estão declaradas dentro de uma função ou bloco de 
código 
➱ São válidas a partir de sua declaração até o final da função ou 
bloco de código 
Prof. Rômulo Alencar Estruturas de Dados 20 
Escopo 
❑  Exemplo 
int x; 
 
int main() 
{ 
 int y; 
 cin >> y; 
 if (y > 0) 
 { 
 int z; 
 x = 2 * y; 
 z = x + y; 
 } 
 return 0; 
} 
Prof. Rômulo Alencar Estruturas de Dados 21 
Escopo 
❑  No exemplo anterior 
➥ x é uma variável global 
➫ Seu escopo é o programa inteiro 
➥ y é uma variável local 
➫ Seu escopo
é a função main 
➱ A partir do ponto em que foi declarada até o final da função 
➥ z é uma variável local 
➫ Seu escopo é o bloco de código if 
➱ A partir do ponto em que foi declarada até o final do bloco de 
código 
Prof. Rômulo Alencar Estruturas de Dados 22 
Escopo 
❑  Não podemos ter duas variáveis com mesmo nome dentro de 
um escopo 
➥ Mas podemos declarar variáveis com nomes iguais em 
escopos diferentes 
➥ Exemplo 
int x; 
x = 10; 
if (x > 0) 
{ 
 int x; 
 x = 20; 
 cout << x << endl; 
} 
cout << x << endl; 
Prof. Rômulo Alencar Estruturas de Dados 23 
Escopo 
❑  O primeiro comando cout imprimirá 20, enquanto o 
segundo imprimirá 10 
➥ As duas variáveis de nome x são diferentes 
➫ Pois possuem escopos diferentes! 
➫ A segunda atribuição não impacta no valor da primeira 
variável 
➥ Cuidado com a definição do escopo de suas variáveis! 
➫ Erros de lógica de difícil detecção podem acontecer 
Prof. Rômulo Alencar Estruturas de Dados 24 
Recursividade 
❑  Uma função é dita recursiva quando faz referência a ela 
própria em sua definição 
➥ Casos básicos: “raízes” da solução 
➥ Passo recursivo: permite que outros casos sejam 
deduzidos a partir dos casos básicos 
❑  Uma solução recursiva sempre poderá ser reescrita 
como uma solução iterativa 
Prof. Rômulo Alencar Estruturas de Dados 25 
Recursividade 
❑  Exemplo base: Cálculo do Fatorial 
➥ Regra 
 
➥ Problema: encontrar o valor do fatorial de um número 
➥ Solução: criar uma função que receba o número desejado 
e retorne seu fatorial devidamente calculado 
➫ Implementações podem ser construídas de várias formas 
diferentes! 
n! = 1 , se n = 0 
n * (n – 1)! , nos demais casos 
Prof. Rômulo Alencar Estruturas de Dados 26 
Recursividade 
❑  Exemplo em C++ utilizando iteração 
int fatorial(int n) 
{ 
 int f = 1; 
 
 for (int i = 1; i <= n; i++) 
 f = f * i; 
 
 return f; 
} 
Prof. Rômulo Alencar Estruturas de Dados 27 
Recursividade 
❑  Exemplo em C++ utilizando recursão 
int fatorial(int n) 
{ 
 if (n == 0) return 1; 
 
 return n * fatorial(n – 1); 
} 
Prof. Rômulo Alencar Estruturas de Dados 28 
Recursividade 
❑  Vantagens 
➥ Geralmente fácil de ler 
➥ Geralmente fácil de implementar 
➥ Soluções “elegantes” 
➫ Fazer mais com menos 
❑  Desvantagens 
➥ Pode sobrecarregar a pilha de execução 
➫ Muitas chamadas internas a si mesmo 
➥ Geralmente mais lento 
Prof. Rômulo Alencar Estruturas de Dados 29 
Recursividade 
❑  Cuidado! 
➥ Casos básicos devem sempre ser alcançados pela 
execução da recursão 
➫ Caso contrário, um loop infinito ocorrerá! 
➱ Provavelmente haverá um overflow da pilha de execução e seu 
programa será encerrado com erro 
int fatorial(int n) 
{ 
 return n * fatorial(n –1); 
} 
Prof. Rômulo Alencar Estruturas de Dados 30 
Complexidade Algorítmica 
❑  Motivação 
➥ Necessidade de medição do tempo de execução de 
algoritmos 
➫ Predição de seus comportamentos 
➫ Preparação de ambiente de execução 
➥ Medição deve ser independente de hardware 
➫ Simples medição de tempo é inadequada 
➫ Necessário o uso de métodos analíticos 
Prof. Rômulo Alencar Estruturas de Dados 31 
Complexidade Algorítmica 
❑  Motivação 
➥ Análise de algoritmos 
➫ Baseada no tamanho da entrada 
➫ Instruções passam a ter o mesmo peso 
➱ Passos 
➫ É computada a quantidade de passos para se executar 
o algoritmo em relação ao tamanho de sua entrada 
Prof. Rômulo Alencar Estruturas de Dados 32 
Complexidade Algorítmica 
❑  Função matemática que representa o comportamento do 
algoritmo 
➥ Quantos passos realizará em função de sua entrada 
❑  Pode ser definida para o melhor caso, caso médio ou 
pior caso 
❑  Pior caso é a situação adotada como padrão 
➥ Melhor caso e caso médio requerem conhecimento prévio 
da distribuição da entrada 
➥ Algoritmos podem ser analisados em situações extremas 
Prof. Rômulo Alencar Estruturas de Dados 33 
Complexidade Algorítmica 
❑  Três notações 
➥ Θ 
➫ Limite superior justo 
➥ O 
➫ Limite superior assintótico 
➥ Ω 
➫ Limite inferior assintótico 
❑  Notação adotada 
➥ O 
Prof. Rômulo Alencar Estruturas de Dados 34 
Complexidade Algorítmica 
❑  Notação O 
➥ Limite superior assintótico 
➥ São computados apenas os passos diretamente 
dependentes da entrada 
➥ Constantes aditivas ou multiplicativas são descartadas 
Prof. Rômulo Alencar Estruturas de Dados 35 
Complexidade Algorítmica 
❑  Padrões de complexidade típicos 
➥ O(1) 
➫ Complexidade constante 
➥ O(n) 
➫ Complexidade linear 
➥ O(n2) 
➫ Complexidade quadrática 
➥ O(2n) 
➫ Complexidade exponencial 
➥ O(log2n) 
➫ Complexidade logarítimica 
Prof. Rômulo Alencar Estruturas de Dados 36 
Complexidade Algorítmica 
❑  Padrões de complexidade típicos 
Prof. Rômulo Alencar Estruturas de Dados 37 
Complexidade Algorítmica 
❑  Exemplo 
➥ Cálculo do fatorial de um número 
função fatorial(n) 
 f := 1 
 para i := 1,…,n faça 
 f := f * i 
 fatorial := f 
➥ Complexidade 
➫ O(n) → Complexidade linear! 
Prof. Rômulo Alencar Estruturas de Dados 38 
Complexidade Algorítmica 
❑  Exemplo 
➥ Cálculo da soma de duas matrizes 
para i := 1,…,n faça 
 para j := 1,…,n faça 
 cij := aij + bij 
➥ Complexidade 
➫ O(n2) → Complexidade quadrática! 
Prof. Rômulo Alencar Estruturas de Dados 39 
Complexidade Algorítmica 
❑  Os problemas com complexidade exponencial não 
podem ser representados como polinômios 
➥ São problemas Não-Polinomiais (NP) 
➥ Entre eles estão os problemas NP-Completos 
➫ Os problemas mais difíceis da Ciência da Computação! 
➫ Um problema é dito NP-Completo se todo problema NP 
puder ser reduzido a ele 
➫ A solução de um problema NP-Completo pode ser 
extendida a todos os problemas NP! 
Prof. Rômulo Alencar Estruturas de Dados 40 
Complexidade Algorítmica 
❑  Exemplo de problema NP-Completo 
➥ Problema do Caixeiro Viajante 
➫ Como, a partir de qualquer cidade, encontrar o menor 
caminho para percorrer todas as outras cidades apenas 
uma vez e regressar à cidade original? 
Prof. Rômulo Alencar Estruturas de Dados 41 
Registro 
❑  Recurso das linguagens de programação que permitem 
agrupar dados heterogêneos (de diferentes tipos de 
dados) como uma única unidade lógica 
➥ Também conhecido como tipo agregado de dados 
➥ Dados que compõem o registro são chamados de 
membros 
❑  A grande vantagem do uso de registros, quando 
adequados, é tornar o programa mais fácil de ler, 
entender e manter 
➥ Ou seja, o programa torna-se mais gerenciável 
❑  Registros são fundamentais para Estruturas de Dados 
➥ São utilizados para representar modelos de dados 
Prof. Rômulo Alencar Estruturas de Dados 42 
Registro 
❑  Por exemplo, um aluno possui vários dados diferentes 
sobre si, como nome, matrícula, CPF, endereço, etc 
➥ Cada um destes dados poderia ser controlado 
separadamente, tornando o programa mais complexo e 
difícil de gerenciar 
➫ Especialmente se vários alunos tiverem que ser 
controlados pelo programa! 
➥ Com o uso de um registro de aluno, todas as informações 
de um aluno poderiam ser agrupadas como uma única 
entidade, facilitando o gerenciamento de dados 
➫ Vários alunos poderiam ser controlados como um vetor 
de registros de aluno! 
Prof. Rômulo Alencar Estruturas de Dados 43 
Registro 
❑  Na linguagem C++, um registro é definido com a palavra 
reservada struct 
 
struct aluno 
{ 
 string nome; 
 int matricula; 
 string endereco; 
 … 
}; 
Este ponto e vírgula é obrigatório! 
Os componentes internos do 
registro são conhecidos 
como membros 
Nome do registro 
Prof. Rômulo Alencar Estruturas de Dados
44 
Registro 
❑  Uma vez declarado o registro, ele assume o papel de um 
tipo de dados 
 
aluno a; 
❑  Cada membro do registro pode ser acessado com o uso 
do operador ponto (.) 
 
a.matricula = 12345; 
a.nome = "João da Silva"; 
cout << a.endereco; 
 
Variável do tipo registro de aluno 
Prof. Rômulo Alencar Estruturas de Dados 45 
Registro 
❑  Registros podem ser utilizados como parâmetros de 
funções 
void imprimir_aluno(aluno a) 
{ 
 cout << a.matricula; 
 cout << a.nome; 
} 
❑  Inclusive podem ser passados por referência 
void atribuir_endereco_aluno(aluno &a, string e) 
{ 
 a.endereco = e; 
} 
Prof. Rômulo Alencar Estruturas de Dados 46 
Registro 
❑  Registros também podem ser utilizados como tipos de 
retorno de funções 
aluno criar_novo_aluno() 
{ 
 aluno a; 
 a.matricula = 0; 
 a.nome = ""; 
 a.endereco = ""; 
 return a; 
} 
Prof. Rômulo Alencar Estruturas de Dados 47 
Registro 
❑  Registros podem ser compostos por arrays 
struct aluno 
{ 
 string nome; 
 int matricula; 
 … 
 float notas[10]; 
}; 
 
❑  E, como acontece com qualquer tipo de dados, podem 
ser usados como tipos de dados de arrays 
aluno turma[50]; Vetor de 50 registros de aluno 
Prof. Rômulo Alencar Estruturas de Dados 48 
Registro 
❑  Registros podem ser compostos por outros registros 
struct curso 
{ 
 int codigo; 
 string nome; 
}; 
 
struct aluno 
{ 
 string nome; 
 int matricula; 
 … 
 curso curso_matriculado; 
}; 
Prof. Rômulo Alencar Estruturas de Dados 49 
Tipo Abstrato de Dados – TAD 
❑  Conceito 
➥ É uma coleção bem definida de dados a serem 
armazenados, e um grupo de operadores que podem ser 
aplicados para a manipulação desses dados 
❑  Características Fundamentais 
➥ Os operadores do TAD implementam regras bem 
definidas para manipulação dos valores armazenados 
➥ Os valores armazenados devem ser manipulados 
exclusivamente pelos operadores do TAD 
Prof. Rômulo Alencar Estruturas de Dados 50 
Tipo Abstrato de Dados – TAD 
❑  Um TAD descreve: 
➥ Quais dados podem ser armazenados 
➥ O que é possível fazer com esses dados através dos 
operadores 
❑  Um TAD não descreve: 
➥ Como as operações serão efetivamente implementadas 
❑  TAD é um modelo abstrato! 
Prof. Rômulo Alencar Estruturas de Dados 51 
Tipo Abstrato de Dados – TAD 
❑  Exemplos 
Mundo Real Coleção de Dados Operadores 
 
 
 
 
Pessoa 
- Idade da pessoa - Nascer (idade recebe valor 
zero) 
- Fazer aniversário (idade é 
incrementada em 1) 
 
 
 
 
 
Fila de Espera 
- Nome de cada pessoa na 
fila 
- Posição de cada pessoa 
na fila 
- Sair da fila (o primeiro) 
- Entrar na fila (na última 
posição) 
 
 
 
 
 
Cadastro de Funcionários 
- Nome de cada funcionário 
- Cargo de cada funcionário 
- Salário de cada funcionário 
- Entrar no cadastro 
- Sair do cadastro 
- Alterar o cargo 
- Alterar o salário 
Prof. Rômulo Alencar Estruturas de Dados 52 
Tipo Abstrato de Dados – TAD 
❑  Para que um TAD possa ser implementado 
➥ Sua coleção de dados deve ser representada utilizando os 
recursos da linguagem de programação 
➫ Geralmente utilizando o conceito de registro 
➥ Seus operadores devem implementar algoritmos que 
resolvam os problemas propostos 
➫ Diversos algoritmos podem existir para a resolução de 
cada problema 
➱ Aquele com menor complexidade deve ser utilizado sempre 
que possível! 
Prof. Rômulo Alencar Estruturas de Dados 53 
Tipo Abstrato de Dados – TAD 
❑  Devemos sempre considerar as diferenças entre: 
Existência no mundo real 
 
 
 
 
Representação abstrata 
Funcionalidade 
Fila.Inserir(Pessoa p) 
Fila.Retirar(Pessoa p) 
Implementação 
void inserir(struct pessoa p) 
{ 
… 
… 
} 
Prof. Rômulo Alencar Estruturas de Dados 54 
Estruturas de Dados 
❑  Algoritmo 
➥ Processo sistemático para a resolução de um problema 
➥ Um algoritmo computa uma saída 
➫ A partir de uma entrada 
➥ Durante a computação da saída (processamento) 
➫ O algoritmo manipula dados 
➥ Quando os dados são manipulados de forma homogênea 
➫ Constituem um Tipo Abstrato de Dados 
Prof. Rômulo Alencar Estruturas de Dados 55 
Estruturas de Dados 
❑  Tipo Abstrato de Dados 
➥ É composto por 
➫ Representação matemática dos dados 
➫ Conjunto de operações que manipulam os dados 
➥ Implementação de um TAD 
➫ É necessário representá-lo na linguagem de 
programação escolhida 
➱ Utilizando tipos de dados e operações suportados 
➫ A representação do modelo matemático é realizada 
utilizando uma estrutura de dados 
Prof. Rômulo Alencar Estruturas de Dados 56 
Estruturas de Dados 
❑  Estrutura de Dados 
➥ Modo particular de armazenamento e organização de 
dados em um computador de modo que possam ser 
usados eficientemente 
➥ É fundamental propor 
➫ Um conjunto eficiente de algoritmos para manipulá-las 
Prof. Rômulo Alencar Estruturas de Dados 57 
Estruturas de Dados 
❑  Classificação 
➥ Estruturas Lineares 
➫ Listas 
➱ Nós (dados) relacionados linearmente 
➱ Casos especiais 
➧  Filas 
➧  Pilhas 
➱ Quanto à ordenação 
➧  Listas desordenadas 
➧  Listas ordenadas 
Prof. Rômulo Alencar Estruturas de Dados 58 
Estruturas de Dados 
❑  Classificação 
➥ Estruturas Lineares 
➫ Listas 
➱ Quanto à alocação de memória 
➧  Listas sequenciais 
➧  Listas encadeadas 
➱ Quanto à navegabilidade 
➧  Listas simplesmente encadeadas 
➧  Listas duplamente encadeadas 
➧  Listas circulares 
➧  Listas com célula cabeça 
➧  Listas com célula cauda 
Prof. Rômulo Alencar Estruturas de Dados 59 
Estruturas de Dados 
❑  Classificação 
➥ Estruturas Lineares 
➫ Listas 
➱ Exemplo 
Prof. Rômulo Alencar Estruturas de Dados 60 
Estruturas de Dados 
❑  Classificação 
➥ Estruturas Lineares 
➫ Listas 
➱ Operações típicas 
➧  Criar a lista 
➧  Inserir um elemento na lista 
➧  Remover um elemento da lista 
➧  Buscar um elemento na lista 
➧  Busca sequencial 
➧  Busca binária 
➧  Ordenar a lista 
➧  Algoritmos de ordenação 
➧  Imprimir os elementos da lista 
Prof. Rômulo Alencar Estruturas de Dados 61 
Estruturas de Dados 
❑  Classificação 
➥ Estruturas Não-Lineares 
➫ Árvores 
➱ Hierarquia de nós 
➱ Quanto à ordem 
➧  Árvores binárias 
➧  Árvores ternárias 
➧  Árvores n-árias 
➱ Quanto ao balanceamento 
➧  Árvores desbalanceadas 
➧  Árvores balanceadas 
Prof. Rômulo Alencar Estruturas de Dados 62 
Estruturas de Dados 
❑  Classificação 
➥ Estruturas Não-Lineares 
➫ Árvores 
➱ Implementações importantes 
➧  Árvores AVL 
➧  Árvores rubro-negras 
➧  Árvores-B 
➧  Árvores-B+ 
➧  Árvores-quadrante 
➧  Árvores-kd 
➧  Árvores-R 
Prof. Rômulo Alencar Estruturas de Dados 63 
Estruturas de Dados 
❑  Classificação 
➥ Estruturas Não-Lineares 
➫ Árvores 
➱ Exemplo 
Prof. Rômulo Alencar Estruturas de Dados 64 
Estruturas de Dados 
❑  Classificação 
➥ Estruturas Não-Lineares 
➫ Árvores 
➱ Operações típicas 
➧  Criar a árvore 
➧  Inserir um elemento na árvore 
➧  Remover um elemento da árvore 
➧  Buscar um elemento na árvore 
➧  Iteração 
➧  Recursividade 
➧  Balancear a árvore 
➧  Imprimir os elementos da árvore 
Prof. Rômulo Alencar Estruturas de Dados 65 
Estruturas de Dados 
❑  Classificação 
➥ Estruturas Não-Lineares 
➫ Grafos 
➱ Composto por 
➧  Vértices 
➧  Arestas 
➱ Quanto ao direcionamento 
➧  Grafos direcionados 
➧  Grafos não direcionados 
➱ Certas operações em grafos possuem complexidade 
exponencial! 
➧  Achar o melhor caminho entre dois vértices 
Prof. Rômulo Alencar Estruturas de Dados 66 
Estruturas de Dados 
❑  Classificação 
➥ Estruturas Não-Lineares
➫ Grafos 
➱ Exemplo 
Prof. Rômulo Alencar Estruturas de Dados 67 
Estruturas de Dados 
❑  Classificação 
➥ Estruturas Não-Lineares 
➫ Grafos 
➱ Operações típicas 
➧  Criar o grafo 
➧  Inserir um elemento no grafo 
➧  Remover um elemento do grafo 
➧  Buscar um elemento no grafo 
➧  Imprimir os elementos do grafo 
➧  Direcionar o grafo 
➧  Fusão de dois elementos do grafo 
➧  Inverter o grafo (direcionado) 
Prof. Rômulo Alencar Estruturas de Dados 68 
Estruturas de Dados 
❑  Qual estrutura de dados escolher para implementar meu 
algoritmo? 
➥ Análise de adequação da estrutura à abstração do 
algoritmo 
➥ Análise da complexidade algorítmica das operações 
utilizadas com mais frequência 
➥ Análise dos requerimentos de custo/benefício 
➫ Tempo/custo financeiro de desenvolvimento 
➫ Vantagem computacional da implementação 
Prof. Rômulo Alencar Estruturas de Dados 69 
Estruturas de Dados 
❑  Exemplo 
➥ Complexidade algorítmica 
➫ Lista desordenada 
➱ Inserção: O(1) 
➱ Busca: O(n) 
➫ Árvore binária balanceada 
➱ Inserção: O(n * log2n) 
➱ Busca: O(log2n) 
➥ Qual a “melhor”? 
➫ Depende do que é mais importante em cada caso! 
Prof. Rômulo Alencar Estruturas de Dados 70 
Listas 
❑  Estrutura de dados linear 
❑  Agrupa informações referentes a um conjunto de 
elementos que se relacionam entre si 
➥ Funcionários de uma empresa 
➥ Notas de alunos 
➥ Produtos em estoque 
➥ Etc 
Prof. Rômulo Alencar Estruturas de Dados 71 
Listas 
❑  Formalmente 
➥ Lista de n ≥ 0 nós L[1], L[2], …, L[n] 
➫ Tais que suas propriedades decorrem exclusivamente 
de sua posição na lista 
➥ Se n > 0 
➫ L[1] é o primeiro nó da lista 
➥ Para 1 < k ≤ n 
➫ O nó L[k] é precedido por L[k – 1] 
Ao menos 2 elementos! 
Prof. Rômulo Alencar Estruturas de Dados 72 
Listas 
❑ Operações básicas 
➥ Busca 
➥ Inserção 
➥ Remoção 
❑ É importante que tenhamos algoritmos eficientes 
para a implementação das operações básicas 
➥ Algoritmos eficientes → Baixa complexidade 
algorítmica 
Prof. Rômulo Alencar Estruturas de Dados 73 
Listas 
❑  Armazenamento na memória 
➥ Alocação estática → Lista sequencial 
➫ Realizada com o uso de vetores 
➫ Vantagens 
➱ Facilidade de implementação 
➱ Desempenho 
➧  Alocação contígua 
➫ Desvantagens 
➱ Conhecimento a priori do tamanho máximo da lista 
➧  Lista com tamanho limitado 
➧  Pode levar a overflows! 
➱ Alocação inicial de uma grande área de memória 
➧  Nem sempre totalmente utilizada! 
Prof. Rômulo Alencar Estruturas de Dados 74 
Listas 
❑  Armazenamento na memória 
➥ Alocação dinâmica → Lista encadeada 
➫ Realizada com o uso de ponteiros 
➫ Vantagens 
➱ Lista pode crescer sob-demanda 
➱ Uso da memória mais “racional” 
➫ Desvantagens 
➱ Implementação mais “complexa” 
➱ Desempenho menor 
➧  Alocação não-contígua 
Prof. Rômulo Alencar Estruturas de Dados 75 
Listas Sequenciais 
❑  Definição da lista 
➥ Nós 
➫ Registros formados por campos 
➱ Armazenam os dados da lista 
➫ Um dos campos será a chave 
➱ Identificador do nó 
➱ Chaves não podem se repetir 
➥ Listas 
➫ Registros que possuem 
➱ Uma quantidade n de nós 
➱ Um vetor de nós 
➧  Sem “buracos”! 
Prof. Rômulo Alencar Estruturas de Dados 76 
Listas Sequenciais 
❑  Inicialização da Lista 
➥ Antes de poder ser manipulada, a lista precisa ser 
inicializada 
➥ De acordo com nosso modelo 
➫ A quantidade de elementos n deve ser inicializada 
➱ Receber zero (0) 
➥ Em outros modelos, outras ações de inicialização serão 
necessárias 
Prof. Rômulo Alencar Estruturas de Dados 77 
Listas Sequenciais 
❑  Operação de Busca 
➥ Busca Sequencial 
➫ Ideia 
➱ Percorrer a lista sequencialmente, elemento a elemento, até 
encontrar o valor de chave de busca desejado 
➧  Ou não encontrar! 
➫ A busca será sempre feita pelas chaves de busca 
➱ Se a chave de busca existir 
➧  Retornar sua posição na lista 
➱ Caso contrário 
➧  Retornar o valor zero (0) 
Prof. Rômulo Alencar Estruturas de Dados 78 
Listas Sequenciais 
❑  Operação de Busca 
➥ Algoritmo (pseudocódigo) 
função busca(x) 
 i := 1 
 busca := 0 
 enquanto i ≤ n faça 
 se L[i].chave = x então 
 busca := i 
 i := n + 1 
 senão 
 i := i + 1 
➥ Complexidade: O(n) → Linear! 
Prof. Rômulo Alencar Estruturas de Dados 79 
Listas Sequenciais 
❑  Operação de Inserção 
➥ Admitindo uma lista desordenada! 
➥ Ideia 
➫ Procurar pela chave de busca do elemento a ser 
inserido 
➱ Se já existir um elemento com mesma chave de busca 
➧  Informar mensagem de erro, pois cada chave é única! 
➱ Caso contrário 
➧  Inserir o novo elemento no final da lista 
➧  Primeira posição vaga! 
➧  Ajustar o tamanho da lista 
Prof. Rômulo Alencar Estruturas de Dados 80 
Listas Sequenciais 
❑  Operação de Inserção 
➥ Algoritmo (pseudocódigo) 
 se n < TAMANHO_MÁXIMO então 
 se busca(x) = 0 então 
 L[n + 1] := novo_valor 
 n := n + 1 
 senão “elemento já existe na lista!” 
 senão overflow 
➥ Complexidade: 
➫ Se não houvesse a busca: O(1) → Constante! 
➫ Com a busca: O(1) + complexidade da busca 
➱ Se a busca for sequencial: O(1) + O(n) = O(n) 
Prof. Rômulo Alencar Estruturas de Dados 81 
Listas Sequenciais 
❑  Operação de Remoção 
➥ Ideia 
➫ Procurar pela chave de busca do elemento a ser 
removido 
➱ Caso o elemento não seja encontrado 
➧  Informar mensagem de erro, o elemento não existe na lista! 
➱ Caso contrário 
➧  Retornar os dados do elemento ao usuário 
➧  Remover o elemento da lista 
➧  Ajustar os elementos subsequentes para não termos um 
“buraco” na lista 
➧  Mover cada elemento posterior para a posição 
imediatamente anterior 
➧  Ajustar o tamanho da lista 
Prof. Rômulo Alencar Estruturas de Dados 82 
Listas Sequenciais 
❑  Operação de Remoção 
➥ Algoritmo (pseudocódigo) 
 se n > 0 então 
 indice := busca(x) 
 se indice > 0 então 
 valor_recuperado := L[i] 
 para i := indice até n – 1 faça 
 L[i] := L[i + 1] 
 n := n – 1 
 senão “elemento não existe na lista!” 
 senão underflow 
➥ Complexidade: O(n) → Linear! 
➫ Mesmo sem a busca! 
Prof. Rômulo Alencar Estruturas de Dados 83 
Listas Sequenciais 
❑  Operação de Impressão 
➥ Ideia 
➫ Imprimir todos os elementos da lista, de forma 
sequencial 
➫ Se a lista estiver vazia 
➱ Imprimir mensagem de erro 
Prof. Rômulo Alencar Estruturas de Dados 84 
Listas Sequenciais 
❑  Operação de Impressão 
➥ Algoritmo (pseudocódigo) 
 
 se n > 0 então 
 para i := 1 até n faça 
 imprima L[i] 
 senão “lista sem elementos!” 
 
➥ Complexidade: O(n) → Linear! 
Prof. Rômulo Alencar Estruturas de Dados 85 
Métodos de Ordenação 
❑  Às vezes precisamos ordenar os elementos de uma lista 
➥ Como fazer isso eficientemente? 
❑  Uma vez que a lista está ordenada, podemos aplicar 
métodos otimizados para executar outras operações 
➥ Por exemplo, podemos realizar buscas utilizando busca 
binária 
Prof. Rômulo Alencar Estruturas de Dados 86 
Métodos de Ordenação 
❑  Bubble Sort 
➥ Ordenação por bolha 
➥ O mais básico de todos os algoritmos de ordenação 
➥ Abstração: bolhas em um líquido qualquer sobem até 
romper a superfície do líquido. 
➥ Na ordenação por bolha, cada elemento de menor (ou 
maior) valor deve “subir” na lista até que encontre seu 
local adequado de acordo com a ordenação pretendida 
➫ Ao final, a lista estará ordenada 
Prof. Rômulo Alencar Estruturas de Dados 87 
Métodos de Ordenação 
❑  Bubble Sort 
➥ Ideia do algoritmo 
➫ Percorrer todos os itens da lista 
➱ A cada item, compará-lo a seus itens anteriores 
➱ Se ele for maior (ou menor), deslocá-lo sucessivamente em 
direção ao início da lista, até que se encontre um elemento 
menor
(ou maior) 
➧  Neste momento, a lista até o elemento em questão estará 
ordenada 
➱ Ao final do laço, a lista inteira estará ordenada 
➥ Complexidade: O(n2) 
Prof. Rômulo Alencar Estruturas de Dados 88 
Métodos de Ordenação 
❑  Bubble Sort 
➥ Algoritmo (pseudocódigo) 
➫ Admitindo que a lista será ordenada de forma 
ascendente 
 função bubble_sort() 
 para i := 2 até n faça 
 k := i 
 para j := i – 1 até 1 faça 
 se L[j].chave > L[k].chave então 
 inverte(L[j], L[k]) 
 k := j 
Prof. Rômulo Alencar Estruturas de Dados 89 
Métodos de Ordenação 
❑  Insertion Sort 
➥ Ordenação por inserção 
➥ Método eficiente quando o número de elementos é 
pequeno 
➥ Fácil implementação 
➥ Extremamente similar ao processo de ordenação de uma 
mão de cartas de baralho 
Prof. Rômulo Alencar Estruturas de Dados 90 
Métodos de Ordenação 
❑  Insertion Sort 
➥ Ideia do algoritmo 
➫ Percorrer a lista da esquerda para a direita 
➫ A cada iteração 
➱ Admite-se que os elementos à esquerda estão ordenados 
➱ Retira-se momentaneamente o elemento atual da lista 
➱ Os elementos à esquerda são percorridos, até que se ache o 
“buraco” onde o elemento retirado deve ser inserido 
 
➥ Complexidade: O(n2) 
Prof. Rômulo Alencar Estruturas de Dados 91 
Métodos de Ordenação 
❑  Insertion Sort 
➥ Algoritmo (pseudocódigo) 
➫ Admitindo que a lista será ordenada de forma 
ascendente 
 função insertion_sort() 
 para i := 2 até n faça 
 item := L[i] 
 buraco := i 
 
 enquanto buraco > 1 e L[buraco-1] > item faça 
 L[buraco] := L[buraco-1] 
 buraco := buraco-1 
 
 L[buraco] := item 
Prof. Rômulo Alencar Estruturas de Dados 92 
Métodos de Ordenação 
❑  Selection Sort 
➥ Ordenação por seleção 
➥ Fácil implementação 
➥ Geralmente mais lento que o Insertion Sort 
➥ Grande vantagem: usa pouca memória 
➫ Em cenários com escassez de memória, consegue ser 
mais rápido que algoritmos mais sofisticados 
Prof. Rômulo Alencar Estruturas de Dados 93 
Métodos de Ordenação 
❑  Selection Sort 
➥ Ideia do algoritmo 
➫ Encontrar o menor (ou maior) elemento da lista 
➫ Substituí-lo pelo primeiro elemento da lista 
➫ Repetir o processo para o restante da lista 
➥ Complexidade: O(n2) 
Prof. Rômulo Alencar Estruturas de Dados 94 
Métodos de Ordenação 
❑  Selection Sort 
➥ Algoritmo (pseudocódigo) 
➫ Admitindo que a lista será ordenada de forma 
ascendente 
 função selection_sort() 
 para i := 1 até n-1 faça 
 minimo := i 
 para j := i+1 até n faça 
 se L[j] < L[minimo] então 
 minimo := j 
 
 inverte(L[i], L[minimo]) 
Prof. Rômulo Alencar Estruturas de Dados 95 
Métodos de Ordenação 
❑  Merge Sort 
➥ Algoritmo criado por Von Neumann em 1945 
➥ Ideia 
➫ Dividir uma lista desordenada em n sub-listas, cada 
uma com apenas 1 elemento 
➱ Se possui apenas 1 elemento, a lista está ordenada! 
➫ Repetidamente combinar as sub-listas ordenadas para 
produzir novas sub-listas, até que 1 única lista seja 
produzida 
➱ Totalmente ordenada! 
➥ Complexidade: O(n*log2n) 
Prof. Rômulo Alencar Estruturas de Dados 96 
Métodos de Ordenação 
❑  Merge Sort 
➥ Divisão e Conquista 
➫ Divisão 
➱ Dividir o vetor original de n elementos em dois sub-vetores 
com n/2 elementos cada 
➫ Conquista 
➱ Ordenar os dois sub-vetores recursivamente utilizando o 
próprio Merge Sort 
➫ Combinação 
➱ Combinar os dois vetores para produzir a solução unificada 
(operação “merge”) 
 
 
Prof. Rômulo Alencar Estruturas de Dados 97 
Métodos de Ordenação 
❑  Merge Sort 
➥ Algoritmo (pseudocódigo) 
 
função merge_sort(p, r) 
 se p < r 
 então 
 q := ⎣(p + r)/2⎦ 
 merge_sort(p, q) 
 merge_sort(q + 1, r) 
 merge(p, q, r) 
 
Prof. Rômulo Alencar Estruturas de Dados 98 
Métodos de Ordenação 
❑  Merge Sort 
➥ Algoritmo (pseudocódigo) 
 
função merge(p, q, r) 
 n1 := q – p + 1 
 n2 := r – q 
 criar vetores E[1...n1] e D[1...n2] 
 para i := 1 até n1 faça 
 E[i] := L [p + i – 1] 
 para j := 1 até n2 faça 
 D[j] := L [q + j] 
 
Prof. Rômulo Alencar Estruturas de Dados 99 
Métodos de Ordenação 
❑  Merge Sort 
➥ Algoritmo (pseudocódigo) 
 i := j := 1 
 para k := p até r faça 
 se E[i] ≤ D[j] então 
 L [k] := E[i] 
 i := i + 1 
 senão 
 L [k] := D[j] 
 j := j + 1 
 
Prof. Rômulo Alencar Estruturas de Dados 100 
Métodos de Ordenação 
❑  Merge Sort 
➥ Exemplo 
 
3 1 4 2 
3 1 4 2 
3 1 4 2 
Prof. Rômulo Alencar Estruturas de Dados 101 
Métodos de Ordenação 
1 2 3 4 
1 3 2 4 
3 1 4 2 
❑  Merge Sort 
➥ Exemplo 
Prof. Rômulo Alencar Estruturas de Dados 102 
Busca Binária 
❑  Ideia 
➥ Admitindo que a lista está ordenada, podemos começar a 
busca pelo elemento que está exatamente no meio da lista 
➫ Caso ele seja o elemento que estamos procurando, a 
busca termina 
➫ Caso contrário, avaliamos se o elemento que estamos 
procurando está à esquerda ou à direita do elemento 
do meio 
➱ Facilmente decidível, já que a lista está ordenada! 
➱ Uma vez que decidimos onde ele deve estar, repetimos o 
processo de busca até encontrar o elemento procurado ou até 
que não haja mais elementos onde buscar 
Prof. Rômulo Alencar Estruturas de Dados 103 
Busca Binária 
❑  Característica principal 
➥ A cada passo da busca, metade do conjunto de dados é 
descartada 
➫ Complexidade da busca binária: O(log2n) 
➱ Comportamento logarítmico, crescimento suave 
❑  A busca binária é geralmente bem mais rápida que a 
busca sequencial 
➥ Mas só pode ser utilizada quando a lista está ordenada 
Prof. Rômulo Alencar Estruturas de Dados 104 
Busca Binária 
❑  Algoritmo (pseudocódigo) 
➥ Admitindo que a lista está ordenada de forma ascendente 
 função busca_binaria(x) 
 inicio := 1 
 fim := n 
 busca_binaria := 0 
 enquanto inicio ≤ fim faça 
 meio := (inicio + fim) / 2 
 se x = L[meio].chave então 
 busca_binaria := meio 
 senão se x < L[meio].chave então 
 fim := meio - 1 
 senão 
 inicio := meio + 1 
Prof. Rômulo Alencar Estruturas de Dados 105 
Pilha 
❑  Tipo especial de lista 
❑  Implementa o conceito LIFO 
➥ Last In First Out 
➫ O último a entrar é o primeiro a sair 
❑  Utilizada sempre que a funcionalidade de 
pilha do mundo real é necessária 
➥ Toda pilha possui um topo 
❑  Operações básicas 
➥ Empilhar (push) 
➫ Insere um novo elemento no topo da pilha 
➥ Desempilhar (pop) 
➫ Remove o elemento que se encontra no topo da pilha 
Prof. Rômulo Alencar Estruturas de Dados 106 
Fila 
❑  Tipo especial de lista 
❑  Implementa o conceito FIFO 
➥ First In First Out 
➫ O primeiro a entrar é o primeiro a sair 
❑  Utilizada sempre que a funcionalidade 
de fila do mundo real é necessária 
➥ Toda fila possui um início e um final 
❑  Operações básicas 
➥ Entrar na fila 
➫ Insere um novo elemento no final da fila 
➥ Sair da fila 
➫ Remove o elemento que se encontra no início da fila 
Prof. Rômulo Alencar Estruturas de Dados 107 
Ponteiros 
❑  Um ponteiro é uma variável que armazena um endereço 
de memória 
➥ Funciona exatamente como qualquer outra variável 
➫ Mas seu valor é um endereço de memória! 
➥ Permite a manipulação de 
➫ Endereços de outras variáveis 
➫ Endereços de memória livres 
Prof. Rômulo Alencar Estruturas de Dados 108 
Ponteiros 
❑  Exemplo: 
➥ Sendo
o seguinte vetor uma representação de memória: 
 
➥ Cada região específica da memória possui um valor e um 
endereço. 
➥ Se uma variável X for alocada no endereço 2 
➫ Valor de X → 5 
➫ Endereço de X → 2 
0 1 2 3 4 5 6 
10 1000 5 -2 A 12,50 Z 
Prof. Rômulo Alencar Estruturas de Dados 109 
Ponteiros 
❑  Ponteiros são especialmente importantes para a 
implementação de Estruturas de Dados! 
➥ Pois nos permitem manipular diretamente a memória 
➫ Possibilitam alocação dinâmica! 
Prof. Rômulo Alencar Estruturas de Dados 110 
Ponteiros 
❑  Representação na Linguagem de Programação C++ 
➥ Definição de uma variável ponteiro x 
➫ int *px; 
➱ px é um ponteiro para um número inteiro 
➥ Atribuição de um endereço a px 
➫ px = &y; 
➱ px recebe o endereço de y 
➥ Acesso ao valor apontado por px 
➫ z = *px; 
➱ z recebe o valor apontado por px, que por sua vez é o valor de 
y 
Prof. Rômulo Alencar Estruturas de Dados 111 
Ponteiros 
❑  Representação na Linguagem de Programação C++ 
➥ Declarando que o ponteiro px não aponta para nada 
➫ No padrão C++11: 
➱ px = nullptr; 
➫ Em padrões mais antigos: 
➱ px = NULL; 
➧  px não aponta qualquer endereço! 
➥ É comum declarar ponteiros já fazendo sua inicialização 
como nullptr 
➫ int *px = nullptr; 
➱ Por que esta é uma boa prática? 
Prof. Rômulo Alencar Estruturas de Dados 112 
Ponteiros 
❑  Ponteiros para registros (struct) 
➥ Similar a um ponteiro para um tipo escalar 
➫ aluno *pa; 
➱ pa é um ponteiro para um registro de aluno! 
➥ Um ponteiro para registro armazena o endereço de um 
registro 
➫ aluno a; 
➫ a.matricula = 12345; 
➫ a.nome = "João da Silva"; 
➫ pa = &a; 
➱ pa armazena o endereço de a, ou seja, pa aponta para a! 
Prof. Rômulo Alencar Estruturas de Dados 113 
Ponteiros 
❑  Ponteiros para registros (struct) 
➥ Os componentes do registro são acessados normalmente 
com o uso do operador ponto 
➫ Considerando que o registro é apontado pelo ponteiro! 
➱ int m = (*pa).matricula; 
➧  Primeiro acessamos o registro apontado por pa para, em 
seguida, acessarmos sua matricula 
➧  A matricula acessada é a mesma do registro a (slide 
anterior) 
➫ Existe uma sintaxe simplificada para acessar 
componentes de um ponteiro para registro 
➱ int m = pa->matricula; 
➧  Operador seta! 
Prof. Rômulo Alencar Estruturas de Dados 114 
Alocação Dinâmica 
❑  Com o uso de ponteiros, podemos reservar áreas de 
memória sempre que necessário 
➥ É o que chamamos de alocação dinâmica 
➥ Extremamente útil para estruturas de dados, pois 
poderemos precisar de mais memória do que o reservado 
no início do programa (alocação estática) 
❑  Sempre que seu programa alocar uma área de memória, 
ele é responsável por liberá-la quando não precisar mais 
dela 
➥ Caso a memória alocada não seja liberada, ela ficará 
indisponível para outros programas, mesmo quando seu 
programa terminar sua execução 
Prof. Rômulo Alencar Estruturas de Dados 115 
Alocação Dinâmica 
❑  Em C++ 
➥ Alocação é realizada com o comando new 
➫ Retorna um ponteiro para a área de memória alocada 
➫ Por isso precisamos de ponteiros para realizar 
alocação dinâmica! 
➥ Liberação é realizada com o comando delete 
❑  Não confundir com C, que utiliza malloc e free, 
respectivamente 
❑  Exemplo 
 int *px = new int; 
 delete px; Libera o espaço alocado anteriormente 
Aloca na memória espaço 
suficiente para armazenar 
um “int” 
Prof. Rômulo Alencar Estruturas de Dados 116 
Alocação Dinâmica 
❑  Cuidado! 
➥ O comando delete libera a memória apontada pelo 
ponteiro, mas não desfaz o apontamento 
➫ Ou seja, se o ponteiro for utilizado posteriormente, 
estará apontando para um endereço de memória que 
não possui mais dados 
➱ Neste caso é comum que, após o comando delete, seja feita 
uma atribuição de nullptr ao ponteiro 
❑  Exemplo 
 delete px; 
 px = nullptr; 
Prof. Rômulo Alencar Estruturas de Dados 117 
Alocação Dinâmica 
❑  Observação 
➥ O comando delete executado sobre um ponteiro que 
aponta para nullptr não possui efeito 
➫ O que significa que não há necessidade de se testar se 
o ponteiro realmente aponta para algo antes de liberar 
a memória 
➱ Caso não aponte, nada acontece 
❑  Exemplo 
 if (px != nullptr) 
 delete px; 
Teste desnecessário 
Prof. Rômulo Alencar Estruturas de Dados 118 
Alocação Dinâmica 
❑  Comandos new e delete podem ser utilizados para 
manipular dinamicamente memória para armazenar 
arrays 
➥ Neste caso, devem ser utilizados colchetes 
❑  Exemplo 
 int *pv = new int[10]; 
 delete [] pv; 
Libera o espaço alocado para 
todas as posições do vetor 
Aloca na memória espaço 
suficiente para armazenar 
um vetor de 10 inteiros 
Prof. Rômulo Alencar Estruturas de Dados 119 
Alocação Dinâmica 
❑  Comandos new e delete podem ser utilizados 
normalmente para alocar/desalocar registros 
❑  Exemplo 
 aluno *pa = new aluno; 
 delete pa; 
Libera o espaço alocado para 
o registro de aluno 
Aloca na memória espaço 
suficiente para armazenar 
um registro de aluno 
Prof. Rômulo Alencar Estruturas de Dados 120 
Listas Encadeadas 
❑  Lista implementada com o uso de alocação dinâmica 
❑  Nós não ficam mais alocados estaticamente na memória 
➥ São alocados dinamicamente de acordo com a demanda 
❑  Vantagem 
➥ Economia de memória 
❑  Desvantagem 
➥ Menor desempenho 
❑  Na prática, quando não se sabe a priori a quantidade de 
nós, deve-se utilizar listas encadeadas 
Prof. Rômulo Alencar Estruturas de Dados 121 
Listas Encadeadas 
❑  Classificação 
➥ Lista Simplesmente Encadeada 
➫ Cada nó aponta para seu próximo 
➥ Lista Duplamente Encadeada 
➫ Cada nó aponta para seu próximo e para seu anterior 
➥ Lista Circular 
➫ O último nó aponta para o primeiro 
Prof. Rômulo Alencar Estruturas de Dados 122 
Listas Encadeadas 
❑  Lista Simplesmente Encadeada 
➥ Nó 
➫ Registro formado por 
➱ Chave 
➱ Ponteiro para o próximo nó 
❑  Lista Duplamente Encadeada 
➥ Nó 
➫ Registro formado por 
➱ Chave 
➱ Ponteiro para o nó anterior 
➱ Ponteiro para o próximo nó 
Prof. Rômulo Alencar Estruturas de Dados 123 
Listas Encadeadas 
❑  Toda Lista Encadeada, independente de seu tipo, possui 
um ponteiro que aponta para o primeiro elemento da 
lista 
➥ Os outros elementos são acessados pelo encadeamento 
de ponteiros a partir do primeiro 
❑  Por exemplo, a operação de impressão em uma Lista 
Simplesmente Encadeada 
➥ Algoritmo (pseudocódigo) 
 no := L; 
 enquanto no ≠ NULO faça 
 imprima no.chave 
 no := no.proximo 
Prof. Rômulo Alencar Estruturas de Dados 124 
Listas Encadeadas 
❑  Operação de Busca na Lista Simplesmente Encadeada 
➥ Algoritmo (pseudocódigo) 
função busca(x) 
 busca := NULO 
 no := L 
 enquanto no ≠ NULO faça 
 se no.chave = x então 
 busca := no 
 no := NULO 
 senão 
 no := no.proximo 
Prof. Rômulo Alencar Estruturas de Dados 125 
Listas Encadeadas 
❑  Operação de Inserção na Lista Simplesmente Encadeada 
➥ Algoritmo (pseudocódigo) 
se há memória suficiente para alocar novo nó então 
 se busca(x) = NULO então 
 alocar(novo_no) 
 novo_no.chave := x 
 novo_no.proximo := NULO 
 
 ultimo_no := L 
 enquanto ultimo_no ≠ NULO faça 
 ultimo_no := ultimo_no.proximo 
 
 ultimo_no.proximo = novo_no 
 senão “elemento já existe na lista!” 
senão overflow 
Prof. Rômulo Alencar Estruturas de Dados 126 
Listas Encadeadas 
❑  Operação de Remoção na Lista Simplesmente Encadeada 
➥ Algoritmo (pseudocódigo) 
se L ≠ NULO então 
 se L.chave = x então 
 desalocar(L) 
 senão 
 no := L 
 enquanto no.proximo ≠ NULO faça 
 se no.proximo.chave = x
então 
 removido := no.proximo 
 no.proximo := removido.proximo 
 desalocar(removido) 
 no := NULO 
 senão 
 no := no.proximo 
senão underflow 
Prof. Rômulo Alencar Estruturas de Dados 127 
Listas Encadeadas 
❑  Como ficariam os algoritmos para os casos das Listas 
Duplamente Encadeadas e Listas Circulares? 
➥ Implemente-os para todos os casos!