Aulas Aeds2

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

22-arvores-de-pesquisa-sbb.pdf
Árvores Binárias de Pesquisa 
Com Balanceamento 
 
 
 Árvore completamente balanceada ⇒ nós externos 
aparecem em no máximo dois níveis adjacentes. 
 Minimiza tempo médio de pesquisa para uma 
distribuição uniforme das chaves, onde cada chave é 
igualmente provável de ser usada em uma pesquisa. 
 Contudo, custo para manter a árvore completamente 
balanceada após cada inserção é muito alto. 
Algoritmos e Estrutura de Dados II 
Árvores Binárias de Pesquisa 
Com Balanceamento 
 
 
 Para inserir a chave 1 na árvore do exemplo à esquerda e 
obter a árvore à direita do mesmo exemplo é necessário 
movimentar todos os nós da árvore original. 
Algoritmos e Estrutura de Dados II 
Uma Forma de Contornar este 
Problema 
 
 
 
 Procurar solução intermediária que possa manter árvore 
“quase-balanceada”, em vez de tentar manter a árvore 
completamente balanceada. 
 
 Objetivo: Procurar obter bons tempos de pesquisa, 
próximos do tempo ótimo da árvore completamente 
balanceada, mas sem pagar muito para inserir ou retirar da 
árvore. 
 
 Heurísticas: existem várias heurísticas baseadas no 
princípio acima. 
Algoritmos e Estrutura de Dados II 
Uma Forma de Contornar este 
Problema 
 Gonnet e Baeza-Yates (1991) apresentam algoritmos que 
utilizam vários critérios de balanceamento para árvores de 
pesquisa, tais como restrições impostas: 
• todos os nós externos apareçam no mesmo nível. 
• na diferença das alturas de subárvores de cada nó 
• na redução do comprimento do caminho interno 
corresponde à soma dos comprimentos dos caminhos entre a raiz e 
cada um dos nós internos da árvore. 
Algoritmos e Estrutura de Dados II 
8 = 0 + 1 + 1 + 2 + 2 + 2 
Algoritmos e Estrutura de Dados II 
Árvores SBB 
 
 Árvores B : estrutura para memória secundária 
(Bayer R. e McCreight E. M., 1972) 
 
 
 
 Árvore 2-3 : caso especial de árvore B mais 
apropriada para memória primária 
 Cada nó tem duas ou três subárvores 
 Pode ser representada como uma árvore binária 
Algoritmos e Estrutura de Dados II 
Árvores SBB 
 
 Exemplo: Uma árvore 2-3 e a árvore B binária correspondente 
(Bayer, R. 1971) 
Algoritmos e Estrutura de Dados II 
Árvores SBB 
 Árvore 2-3: árvore B binária (assimetria inerente) 
1 - Apontadores à esquerda apontam para um nó no nível abaixo. 
2 - Apontadores à direita podem ser verticais ou horizontais 
 
 Eliminação da assimetria nas árvores B binárias: árvores B binárias 
simétricas (Symmetric Binary B-trees – SBB) 
 
 Árvore SBB é uma árvore binária com 2 tipos de apontadores: 
 verticais e horizontais, tal que: 
1 – todos os caminhos da raiz até cada nó externo possuem o 
 mesmo número de apontadores verticais , e 
2 – não podem existir dois apontadores horizontais sucessivos. 
Algoritmos e Estrutura de Dados II 
Árvores SBB 
 
A pesquisa em uma árvore SBB é idêntica a uma árvore sem 
balanceamento. A pesquisa ignora se os apontadores são 
horizontais ou verticais 
Algoritmos e Estrutura de Dados II 
Transformações para Manutenção 
da Propriedade SBB 
 O algoritmo para árvores SBB usa transformações locais 
no caminho de inserção ou retirada para preservar o 
balanceamento. 
 A chave a ser inserida ou retirada é sempre inserida ou 
retirada após o apontador vertical mais baixo na árvore 
 Dependendo da situação anterior à inserção ou retirada, 
podem, aparecer dois apontadores horizontais 
sucessivos 
 Neste caso: é necessário realizar uma transformação 
Algoritmos e Estrutura de Dados II 
Transformações para Manutenção 
da Propriedade SBB 
 Transformações propostas por Bayer R. 1972 
Inserção do 1 
Inserção do 2 
Algoritmos e Estrutura de Dados II 
Exemplo 
 Inserção das Chaves 7, 10, 5, 2, 4, 9, 3, 6 
 
 
 
 
 
 
Algoritmos e Estrutura de Dados II 
Exemplo 
 Inserção de uma sequência de chaves em uma árvore SBB 
inicialmente vazia. 
 1 - Árvore à esquerda é obtida após a inserção das chaves 7, 
 10, 5 
 2 - Árvore do meio é obtida após a inserção das chaves 2,4 
 na árvore anterior 
 3 - Árvore à direita é obtida após a inserção das chaves 9, 3, 
 6 na árvore anterior. 
Algoritmos e Estrutura de Dados II 
 
Retirada 
 Mais complexa... 
 Procura sempre fazer modificações locais 
 EsqCurto (DirCurto): chamado quando um nó 
folha é retirado da sub-árvore da esquerda 
(direita) tornando menor a altura 
 Antecessor: chamado quando o nó possui 
dois descendentes 
 Em alguns casos, o procedimento não é 
muito intuitivo 
Algoritmos e Estrutura de Dados II 
Exemplo 
Caso “simples” 1 
 Retirada da chave 7 
 
 
 
 
 
 
Algoritmos e Estrutura de Dados II 
Exemplo 
Caso “simples” 2 
 Retirada da chave 5 (substituição pelo nó 
mais a direita da sub-árvore esquerda) 
 
 
 
 
 
 
Algoritmos e Estrutura de Dados II 
Exemplo 
Caso “simples 3” 
 Retirada da chave 9 
 
 
 
 
 
 
Algoritmos e Estrutura de Dados II 
Casos complexos 
Retirada do 12 
Algoritmos e Estrutura de Dados II 
Casos complexos 
Retirada do 12 
Algoritmos e Estrutura de Dados II 
Casos complexos 
Retirada do 12 
Algoritmos e Estrutura de Dados II 
Casos complexos 
Retirada do 12 
Algoritmos e Estrutura de Dados II 
Análise 
 Nas árvores SBB é necessário distinguir dois tipos de alturas 
 1- altura vertical h : necessária para manter a altura uniforme e 
obtida através da contagem do número de apontadores 
verticais em qualquer caminho entre a raiz e um nó externo 
 2- altura k : representa o número máximo de comparações de 
chaves obtido através da contagem do número total de 
apontadores no maior caminho entre a raiz e um nó externo 
 
 A altura k é maior que a altura h sempre que existirem 
apontadores horizontais na árvore 
 
 Para uma árvore SBB com n nós internos, temos que: 
 h  k  2h 
Algoritmos e Estrutura de Dados II 
Análise 
 De fato, Bayer (1972) mostrou que: 
 
 
 
 Custo para manter a propriedade SBB: custo para percorrer o caminho de 
pesquisa para encontrar a chave, seja para inserí-la ou para retirá-la 
• Logo: o custo e O(log n) 
 Número de comparações em uma pesquisa com sucesso na árvore SBB: 
• Melhor caso: C(n) = O(1) 
• Pior caso: C(n) = O(log n) 
• Caso médio: C(n) = O(log n) 
 Observe: Na prática, o caso médio para C(n) é apenas cerca de 2% pior 
que o C(n) para uma árvore completamente balanceada, conforme 
mostrado em Ziviani e Tompa (1982) 
 
2)2log(2)1log(  nn k 
Algoritmos e Estrutura de Dados II 
Estrutura de Dados Árvore SBB para 
Implementar o TAD Dicionário 
#include <sys/time.h> 
#include<stdlib.h> 
#include<stdio.h> 
 
#define TRUE 1 
#define FALSE 0 
#define max 10 
 
typedef int TipoChave; 
 
typedef struct Registro { 
 /* outros componentes */
TipoChave Chave; 
 } Registro; 
Algoritmos e Estrutura de Dados II 
Estrutura de Dados Árvore SBB para 
Implementar o TAD Dicionário 
 
typedef enum { 
 Vertical, Horizontal 
 } Inclinacao; 
 
typedef struct No* Apontador; 
 
typedef struct No { 
 Registro Reg; 
 Apontador Esq, Dir; 
 Inclinacao BitE, BitD; 
 } No; 
Algoritmos e Estrutura de Dados II 
Procedimentos Auxiliares para 
Árvores SBB 
void EE(Apontador *Ap) 
{ 
 Apontador Ap1; 
 Ap1 = (*Ap)->Esq; (*Ap)->Esq = Ap1->Dir; Ap1->Dir = *Ap; 
 Ap1->BitE = Vertical; (*Ap)->BitE = Vertical; 
 *Ap = Ap1; 
} 
 
void ED(Apontador *Ap) 
{ 
 Apontador Ap1, Ap2; 
 Ap1 = (*Ap)->Esq; Ap2 = Ap1->Dir; 
 Ap1->BitD = Vertical; (*Ap)->BitE = Vertical; 
 Ap1->Dir = Ap2->Esq; Ap2->Esq = Ap1; 
 (*Ap)->Esq = Ap2->Dir; Ap2->Dir = *Ap; *Ap = Ap2; 
} 
Algoritmos e Estrutura de Dados II 
Procedimentos Auxiliares para 
Árvores SBB 
void DD(Apontador *Ap) 
{ 
 Apontador Ap1; 
 Ap1 = (*Ap)->Dir; (*Ap)->Dir = Ap1->Esq; Ap1->Esq = *Ap; 
 Ap1->BitD = Vertical; (*Ap)->BitD = Vertical; 
 *Ap = Ap1; 
 } 
 
void DE(Apontador *Ap) 
{ 
 Apontador Ap1, Ap2; 
 Ap1 = (*Ap)->Dir; Ap2 = Ap1->Esq; 
 Ap1->BitE = Vertical; (*Ap)->BitD = Vertical; 
 Ap1->Esq = Ap2->Dir; Ap2->Dir = Ap1; 
 (*Ap)->Dir = Ap2->Esq; Ap2->Esq = *Ap; *Ap = Ap2; 
} 
Algoritmos e Estrutura de Dados II 
Procedimentos para Inserir na 
Árvores SBB 
 
 
void Insere(Registro x, Apontador *Ap) 
 { 
 short Fim; 
 Inclinacao Iap; 
 IInsere(x, Ap, &IAp, &Fim); 
 } 
Algoritmos e Estrutura de Dados II 
Procedimentos para Inserir na 
Árvores SBB 
void IInsere(Registro x, Apontador *Ap, Inclinacao *IAp, short *Fim) 
{ 
 if (*Ap == NULL) { 
 *Ap = (Apontador)malloc(sizeof(No)); 
 *IAp = Horizontal; 
 (*Ap)->Reg = x; 
 (*Ap)->BitE = Vertical; 
 (*Ap)->BitD = Vertical; 
 (*Ap)->Esq = NULL; 
 (*Ap)->Dir = NULL; 
 *Fim = FALSE; 
 return; 
 } 
 
Algoritmos e Estrutura de Dados II 
Procedimentos para Inserir na 
Árvores SBB 
 if (x.Chave < (*Ap)->Reg.Chave) { 
 IInsere(x, &(*Ap)->Esq, &(*Ap)->BitE, Fim); 
 if (*Fim) return; 
 if ((*Ap)->BitE != Horizontal) { 
 *Fim = TRUE; 
 return; 
 } 
 if ((*Ap)->Esq->BitE == Horizontal) { 
 EE(Ap); *IAp = Horizontal; 
 return; 
 } 
 if ((*Ap)->Esq->BitD == Horizontal) { 
 ED(Ap); *IAp = Horizontal; 
 } 
 return; 
 } 
 
Algoritmos e Estrutura de Dados II 
Procedimentos para Inserir na 
Árvores SBB 
 if (x.Chave <= (*Ap)->Reg.Chave) { 
 printf("Erro: Chave ja esta na arvore\n"); 
 *Fim = TRUE; return; 
 } 
 IInsere(x, &(*Ap)->Dir, &(*Ap)->BitD, Fim); 
 if (*Fim) return; 
 if ((*Ap)->BitD != Horizontal) { 
 *Fim = TRUE; return; 
 } 
 if ((*Ap)->Dir->BitD == Horizontal) { 
 DD(Ap); *IAp = Horizontal; return; 
 } 
 if ((*Ap)->Dir->BitE == Horizontal) { 
 DE(Ap); *IAp = Horizontal; 
 } 
} 
Algoritmos e Estrutura de Dados II 
Procedimento de Inicialização da 
Árvore SBB 
 
 void Inicializa(Apontador *Dicionario) 
 { 
 
 *Dicionario = NULL; 
 } 
Algoritmos e Estrutura de Dados II 
Procedimento de Retirada da 
Árvore SBB 
 Retira contém um outro procedimento interno de nome IRetira. 
 IRetira usa 3 procedimentos internos: 
• EsqCurto, DirCurto e Antecessor 
 EsqCurto (DirCurto): 
• Chamado quando um nó folha que é referenciado por um 
apontador vertical é retirado da subárvore à esquerda (direita) 
tornando-a menor na altura após a retirada; 
 Antecessor: 
• Quando o nó a ser retirado possui dois descendentes, o 
procedimento Antecessor localiza o nó antecessor para ser 
trocado com o nó a ser retirado 
 
 
Algoritmos e Estrutura de Dados II 
Procedimento de Retirada da 
Árvore SBB 
void Retira(Registro x, Apontador *Ap) 
{ 
 short Fim; 
 IRetira(x, Ap, &Fim); 
 } 
 
Algoritmos e Estrutura de Dados II 
Procedimento de Retirada da 
Árvore SBB 
void IRetira(Registro x, Apontador *Ap, short *Fim) 
{ 
 No *Aux; 
 if (*Ap == NULL) { 
 printf("Chave nao esta na arvore\n"); *Fim = TRUE; 
 return; 
 } 
 if (x.Chave < (*Ap)->Reg.Chave) { 
 IRetira(x, &(*Ap)->Esq, Fim); 
 if (!*Fim) EsqCurto(Ap, Fim); 
 return; 
 } 
 if (x.Chave > (*Ap)->Reg.Chave) { 
 IRetira(x, &(*Ap)->Dir, Fim); 
 if (!*Fim) DirCurto(Ap, Fim); 
 return; 
 } 
Algoritmos e Estrutura de Dados II 
Procedimento de Retirada da 
Árvore SBB 
 *Fim = FALSE; 
 Aux = *Ap; 
 if (Aux->Dir == NULL) { 
 *Ap = Aux->Esq; free(Aux); 
 if (*Ap != NULL) *Fim = TRUE; 
 return; 
 } 
 if (Aux->Esq == NULL) { 
 *Ap = Aux->Dir; free(Aux); 
 if (*Ap != NULL) *Fim = TRUE; 
 return; 
 } 
 Antecessor(Aux, &Aux->Esq, Fim); 
 if (!*Fim) EsqCurto(Ap, Fim); /* Encontrou chave */ 
} 
Algoritmos e Estrutura de Dados II 
Procedimento de Retirada da 
Árvore SBB 
 void DirCurto(Apontador *Ap, short *Fim) 
 { /* Folha direita retirada => arvore curta na altura direita */ 
 Apontador Ap1; 
 if ((*Ap)->BitD == Horizontal) { 
 (*Ap)->BitD = Vertical; *Fim = TRUE; 
 return; 
 } 
 if ((*Ap)->BitE == Horizontal) { 
 Ap1 = (*Ap)->Esq; (*Ap)->Esq = Ap1->Dir; 
 Ap1->Dir = *Ap; *Ap = Ap1; 
 if ((*Ap)->Dir->Esq->BitD == Horizontal) { 
 ED(&(*Ap)->Dir); (*Ap)->BitD = Horizontal; 
 } 
 else if ((*Ap)->Dir->Esq->BitE
== Horizontal) { 
 EE(&(*Ap)->Dir); (*Ap)->BitD = Horizontal; 
 } 
 *Fim = TRUE; return; 
 } 
 
Algoritmos e Estrutura de Dados II 
Procedimento de Retirada da 
Árvore SBB 
 
 (*Ap)->BitE = Horizontal; 
 if ((*Ap)->Esq->BitD == Horizontal) { 
 ED(Ap); *Fim = TRUE; 
 return; 
 } 
 if ((*Ap)->Esq->BitE == Horizontal) { 
 EE(Ap); *Fim = TRUE; 
 } 
} 
Algoritmos e Estrutura de Dados II 
Procedimento de Retirada da 
Árvore SBB 
 void EsqCurto(Apontador *Ap, short *Fim) 
{ /* Folha esquerda retirada => arvore curta na altura esquerda */ 
 Apontador Ap1; 
 if ((*Ap)->BitE == Horizontal) { 
 (*Ap)->BitE = Vertical; *Fim = TRUE; 
 return; 
 } 
 if ((*Ap)->BitD == Horizontal) { 
 Ap1 = (*Ap)->Dir; (*Ap)->Dir = Ap1->Esq; 
 Ap1->Esq = *Ap; *Ap = Ap1; 
 if ((*Ap)->Esq->Dir->BitE == Horizontal) { 
 DE(&(*Ap)->Esq); (*Ap)->BitE = Horizontal; 
 } 
 else if ((*Ap)->Esq->Dir->BitD == Horizontal) { 
 DD(&(*Ap)->Esq); (*Ap)->BitE = Horizontal; 
 } 
 *Fim = TRUE; return; 
 } 
Algoritmos e Estrutura de Dados II 
Procedimento de Retirada da 
Árvore SBB 
 (*Ap)->BitD = Horizontal; 
 if ((*Ap)->Dir->BitE == Horizontal) { 
 DE(Ap); *Fim = TRUE; 
 return; 
 } 
 if ((*Ap)->Dir->BitD == Horizontal) { 
 DD(Ap); *Fim = TRUE; 
 } 
} 
Algoritmos e Estrutura de Dados II 
Procedimento de Retirada da 
Árvore SBB 
 void Antecessor(Apontador q, Apontador *r, short *Fim) 
 { 
 if ((*r)->Dir != NULL) { 
 Antecessor(q, &(*r)->Dir, Fim); 
 if (!*Fim) DirCurto(r, Fim); 
 return; 
 } 
 q->Reg = (*r)->Reg; 
 q = *r; 
 *r = (*r)->Esq; 
 free(q); 
 if (*r != NULL) 
 *Fim = TRUE; 
} 
aeds2_aula_001_linguagem_C.pdf
08/09/2015 
1 
Algoritmos e 
Estruturas de Dados II 
 
 
 
Algorithms everywhere! 
Ementa 
• Tipos Abstratos de Dados (TADs) 
• Análise de Algoritmos: 
• O(n), O(n log n), )(n!), ... 
• Estruturas de dados: 
• listas, filas, pilhas e árvores 
• Métodos de ordenação: 
• quick, heap, merge, select, etc 
• Métodos de pesquisa: 
• hash, árvores binárias, árvores digitais 
 
Prova 1 – Definir 
Prova 3 – Definir 
Prova 2 – Definir 
Referências 
• Projeto de Algoritmos Com Implementações Em 
Pascal e C 
– Nivio Ziviani 
• Algoritimos - Teoria e Prática 
– Cormen, Thomas H. 
• Algorithms In C 
– Robert Sedgewick 
• Linguagem C: completa e descomplicada 
– André Backes 
 
• Recomendação: estudem pelo livro! 
 
 
 
Avaliação 
• 3 provas (total 60 pontos) 
• Trabalhos práticos – (total 40 pontos) 
– *Individuais* 
– Deverá ser entregue 
• Implementação 
• Documentação 
• Testes 
• Lista de exercícios 
• Pontos Extras (não haverá arredondamento de 
notas) 
08/09/2015 
2 
Regras Gerais 
• Exame especial 
– Nota >= 40 && frequência >= 75% 
• Prova de reposição 
– Apenas para aqueles que perderam uma prova por 
motivo de força maior. 
• Celulares devem permanecer desligados. 
• Horário de atendimento: 
– A definir 
• Presença: 
– Verificada por meio de chamada 
 
Regras Gerais para os TPs 
• Avaliação dos trabalhos práticos 
– Documentação: 40% 
– Código: 30% 
– Testes: 30% 
• Apenas serão avaliados trabalhos com entrega 
dos três itens 
• Trabalhos iguais receberão nota ZERO 
 
Moddle / Website 
 
• Todas informações relacionadas ao curso, 
incluindo notas de aulas, estarão disponíveis 
no Moodle, fórum 
 
• Sistema de submissão de trabalhos práticos: 
• A definir 
Detalhes 
• Linguagem: C 
• Software Recomendado: 
– CodeBlock, www.codeblocks.org 
• Alta carga extra classe 
• Não utilizar bibliotecas do windows 
– Usar GCC ou MingW 
 
Code::blocks 
 
Code::blocks 
08/09/2015 
3 
Alternativa 
• Sempre pode usar gcc + vi (emacs) + gdb 
Tópicos 
• Indentação 
• Comentários 
• Modularização 
• Compilação e Debug 
• Entrada e saída 
• Vetores e Strings 
• Passagem de parâmetros 
• Structs 
 
 
Boas Práticas 
• Com um pequeno esforço extra, programas 
escritos em C podem se tornar mais legíveis e 
mais facilmente depuráveis 
• No caso de disciplinas de programação, isso 
ainda ajuda no entendimento das ideias e na 
correção de trabalhos 
• O que não pode ser lido não pode ser 
avaliado. 
Indentação 
• É usual empregar TABS para indicar blocos de 
programação 
– Em geral, 1 tab equivale a 4 espaços, MAS NÃO 
USAR ESPAÇOS para alinhar 
• Há vários estilos 
• Quando o bloco é longo, é usual colocar um 
pequeno comentário após o fechamento 
indicando o que está sendo fechado 
Indentação 
• K&R: Kernighan & Ritchie 
Indentação 
• Allman 
08/09/2015 
4 
Comentários 
• Importantes para compreensão do código 
• Mais importantes em código mais complexo 
• Úteis para explicar o conteúdo de variáveis, 
mas não substituem um bom critério de 
atribuição de nomes 
• Não exagerar! 
Comentários 
• No início de cada módulo de código (arquivos .c, .h) 
• Uma linha em cada função, explicando o que ela faz 
 
– Não é necessário explicar COMO ela faz, o código deve ser 
claro o bastante para permitir esse entendimento em uma 
função razoavelmente pequena 
– Se necessário, considerar a quebra em outras funções 
 
• Comentário na linha da declaração, se necessário, para 
esclarecer o significado/o uso de uma variável 
• Comentário na linha do fecha-chave, para ajudar a 
entender blocos e loops 
Comentários 
• No início de um bloco/arquivo fonte 
Comentários 
• Em função (simples) 
Comentários 
• Em funções (arquivo .h) 
Comentários 
• Em 
variáveis 
• Em 
structs 
08/09/2015 
5 
Comentários 
• No fim de 
um bloco 
de 
programa 
• No 
código 
Modularização 
• Planejar a quebra de um programa em módulos 
 
– Um módulo não significa necessariamente um arquivo 
fonte; muitas vezes, é um par de arquivos .c / .h 
– Existe sempre um arquivo fonte para o programa 
principal (main), e outros para funções adicionais ou 
componentes 
Modularização 
• Montar módulos especificamente para tipos 
abstratos de dados 
• Procurar dar independência aos módulos, para 
que possam eventualmente ser reaproveitados 
 
• DRY: Don't repeat yourself 
Modularização 
#include <stdio.h> 
 
float produto_escalar(float x1, float y1, float x2, float y2) { 
 return x1*x2 + y1*y2; 
} 
int main(int argc, char** argv) { 
 float p; 
 
 p = produto_escolar(1, 2, 10, 20);
printf(“Produto escalar: %f”, p); 
} 
main.c 
Modularização 
• Mas o produto escalar é uma função utilizada 
em vários outros problemas 
• Como resolver isso? 
– Sempre copiar e colar no main? 
 
DRY: Don't repeat yourself 
 
Modularização 
#include <stdio.h> 
#include “vetores.h” 
 
int main(int argc, char** argv) { 
 float p; 
 
 p = produto_escolar(1, 2, 10, 20); 
 printf(“Produto escalar: %f”, p); 
} 
main.c 
08/09/2015 
6 
Modularização 
#include “vetores.h” 
 
float produto_escalar(float x1, float y1, float x2, float y2) { 
 return x1*x2 + y1*y2; 
} 
vetores.c 
#ifndef _VETORES_H_ 
#define _VETORES_H_ 
 
float produto_escalar(float x1, float y1, float x2, float y2); 
 
#endif 
vetores.h 
Modularização 
• Declaração da função: 
– Arquivos .h 
• Definição da função: 
– Arquivos .c 
 
• Usar 
#ifndef _VETORES_H_ 
#define _VETORES_H_ 
 
float produto_escalar(...); 
 
#endif 
 
Modularização 
• Criando uma biblioteca no Linux 
– gcc -c vetores.c (isso irá gerar um arquivo chamado 
vetores.o) 
– gcc -c main.c (main.o) 
– gcc -o MeuPrograma main.o vetores.o 
 
– gcc -c vetores.c 
– gcc -c conversao.c 
– ar rs libuteis.a vetores.o conversao.o 
– gcc -o MeuPrograma main.c -L. -luteis 
 
Nomes de variáveis 
• Algumas variáveis merecem nomes significativos: 
MAX_VETOR, numClientes, listaAlunos 
• Variáveis auxiliares em geral recebem nomes curtos: 
i, j, aux, x 
– Cuidado para não fazer confusão 
– Não abusar: i, ii, iii, aux1, aux2, 
aux3... 
– Variáveis inteiras: i, j, k 
– Variáveis reais: x, y, z 
– Strings: s1, s2 
– Booleanas: nome do teste (existe, valido, 
ocorre) 
Nomes de variáveis 
• Estilos variados: 
– Só minúsculas (i, num, conta) 
– Só maiúsculas (constantes: PI, E, MAX) 
– CamelCase (numMat, anguloEntrada) 
– Indicação do tipo no início do nome (iNum, 
iValor, fRaio, fAltura, dVolume) 
• Há quem prefira inserir comentários e usar 
nomes de variáveis em inglês, por ficar mais 
próximo da linguagem de programação 
Organização e limpeza 
• Procurar dar um aspecto organizado ao 
código, ajuda na compreensão 
• Entender o código fonte como um 
instrumento de comunicação 
• Comentar excessivamente código mal escrito 
não ajuda 
• Dar nomes adequados a variáveis ajuda 
bastante 
08/09/2015 
7 
Parênteses e espaçamento 
• Usar espaços antes de parênteses, depois de 
vírgulas, ao redor de operadores binários 
if (10 == x) y = 5; 
for (i = 0; i < 10; i++) { 
 x += a; 
 a = f(b); 
} 
• Cuidado com notações compactas demais, e com 
comandos embutidos em outros: 
if (x++ == b) y = 5; 
Correção e robustez 
• Testes: prever todo tipo de problema e 
variações na entrada de dados 
– Limites de vetores 
– Valores inteiros e de ponto flutuante 
– Contadores e incremento 
 
Correção e robustez 
• Testes: prever todo tipo de problema e 
variações na entrada de dados 
– Testes de fim de arquivo 
– Teste de disponibilidade de memória para 
alocação 
–Todo malloc() deve ter um free()! 
–Memory leak 
–Todo fopen() deve ter um fclose()! 
 
Compilação 
• LER as mensagens de erro e ENTENDER a 
origem do problema 
• Warnings: indicam problemas potenciais, 
devem ser resolvidos 
• Muitas vezes a mensagem de erro não reflete 
o que está ocorrendo 
– Observar a linha em que o erro foi indicado, a 
linha anterior, o bloco de código em que ocorreu, 
e o corpo da função em que ocorreu 
Debugger 
• Ajuda a acompanhar os valores das variáveis 
ao longo da execução 
– Observar o valor de variáveis (watches) 
– Posicionar pontos de interrupção (breakpoints) 
– Executar passo a passo 
• Vide 
http://wiki.codeblocks.org/index.php?title=Debugging_with_Code::Blocks 
• Documentação do CodeBlocks 
http://wiki.codeblocks.org/index.php?title=Main_Page 
aeds2_aula_002_linguagem_C_entrada_e_saida.pdf
08/09/2015 
1 
Entrada e Saída na linguagem C 
Objetivos 
• Entrada e saída formatada 
• Uso de arquivos 
– Escrita e leitura de blocos de dados 
– Movimentação em arquivos 
 
 
I/O em C 
• Formalmente, rotinas de entrada e saída não 
fazem parte da linguagem, e sim de 
bibliotecas que acompanham os compiladores 
– Felizmente, são padronizadas 
– Exige-se a linha #include <stdio.h> para usá-las 
 
I/O em C 
• int printf(const char *format, ...); 
– Retorna o número de caracteres impressos 
– O string contém uma “máscara” (template) com 
lacunas reservadas para os valores que serão 
impressos 
 
printf(“O valor de x eh %d”, x); 
printf(“Area: %f\n”, PI*d*d/4); 
printf(“Nome: %s”, nomeAluno); 
printf 
• Especificadores de formato 
– %c (char) 
– %s (string) 
– %d (int) 
– %ld (long int) 
– %f (float) 
– %lf (double) 
– %e (float notação científica) 
– %g (e ou f, ou seja, notação científica se 
necessário) 
Caracteres de escape 
• Acrescentados à máscara para provocar 
reposicionamento do cursor 
– \n: nova linha 
– \t: tabulação 
– \r: backspace 
– \\: caractere da barra invertida 
08/09/2015 
2 
printf 
#include<stdio.h> 
int main(int argc, char **argv) { 
 int ret = printf("Hello world!\n"); 
 printf("ret: %d\n", ret); 
 
 // imprime 233.123 
 printf("%.3f\n", 233.12312312312); 
 printf("%p\n", &ret); 
 return 0; 
} 
Entrada 
• Com máscara: scanf(string, *var [, *var, ...]); 
– Mesmos especificadores de formato do printf 
– A função precisa receber o endereço da variável à 
qual o valor digitado será atribuído 
scanf(“%d”, &num) 
scanf(“%c%d”, &letra, &num); 
scanf(“%c”, &ch); 
scanf(“%s”, s); // string 
scanf(“%13c”, s); //le 13 caracteres 
scanf(“ %c”, &ch); //pula brancos 
Linha de comando 
• int main(int argc, char **argv) 
– argc contém o número de valores passados na linha de 
comando, incluindo o nome do programa 
– argv é um vetor de strings com os valores passados na 
linha de comando 
 int main(int argc, char **argv){ 
 int i; 
 printf(“Nome do programa: %s\n”, argv[0]); 
 printf(“Numero de parametros %d.\n”, argc-1); 
 
 for(i = 1; i < argc; i++ ) 
 printf(“parametro %d: %s\n”, i, argv[i]); 
 return 0; 
} 
Entrada 
Entrada 
• Observe que scanf interrompe a leitura de um 
string quando encontra um branco, se usado com %s 
• Uso de %[]: 
– %[aeiou]: apenas as vogais são permitidas 
– %[^aeiou]: as vogais não são permitidas 
– %[^\n]: interrompe quando recebe um [enter] 
– %60[^\n]: admite até 60 caracteres, e para quando 
encontra um [enter] 
Entrada 
• Linhas inteiras: 
 char *gets(char *); 
 
– Lê uma linha inteira, excluindo \n, e coloca \0 no 
final 
– Com limite de tamanho: 
• fgets(string, tamMax, stdin) 
08/09/2015 
3 
Entrada 
#include <stdio.h> 
 
const MAX_TAM=30; 
int main(int argc, char **argv) { 
 char str[MAX_TAM]; 
 
 gets(str); 
 printf("str: %s\n", str); 
 
 return 0; 
} 
Entrada 
• Caracteres individuais: 
 int getchar(void); 
 
– O caractere digitado é o valor de retorno da função 
 
ret = getchar(); 
printf("entrada: %c %d\n", ret, ret); 
 
> 1 
> entrada: 1 49
Exemplo (POSCOMP 2009) 
#include<stdio.h> 
#include<string.h> 
 
int main(int argc, char **argv) { 
 char texto[]= "foi muito facil"; 
 int i; 
 
 for (i = 0; i < strlen(texto); i++){ 
 if (texto[i] == ' ') break; 
 } 
 i++; 
 for ( ; i < strlen(texto); i++) 
 printf("%c", texto[i]); 
 return 0; 
} 
O que será impresso quando 
 o programa for executado? 
I/O para arquivos 
• A entrada do teclado e saída para o monitor 
são realizadas internamente considerando três 
dispositivos virtuais: stdin, stdout e stderr 
– Como são dispositivos padrão, referências a stdin 
e stdout eles são omitidas dos comandos 
– fgets(string, tamMax, stdin); 
– stdout vs stderr 
–stderr não é “buferizado”, a mensagem é 
mostrada no console imediatamente 
I/O para arquivos 
• I/O para arquivos é muito semelhante à 
operação com stdin e stdout, mas um handle 
ao arquivo tem que ser fornecido 
• Tipo FILE. 
• FILE *fp = NULL; 
I/O para arquivos 
// abre ou cria um arquivo 
// retorno: handle para arquivo criado 
FILE *fopen(const char *name, const char *type); 
 
// fecha um arquivo 
// retorna 0 se executado com sucesso 
int fclose(FILE *); 
 
// remove dados do buffer e envia para o arquivo 
// retorna 0 se executado com sucesso 
int fflush(FILE *); 
 
// testa final de arquivo 
// Retorna diferente de zero se fim do arquivo foi 
// atingido 
int feof(FILE *); 
 
 
 
 
 
08/09/2015 
4 
I/O para arquivos 
• fopen: modos de abertura 
I/O para arquivos 
FILE *inFile = NULL; 
FILE *outfile = NULL; 
... 
//abre o arquivo para leitura (r) ou gravacao (w) 
inFile = fopen(“arquivo.txt”, “r”); 
outFile = fopen(“saida.txt”, “w”); 
... 
fscanf(inFile, “%d”, &num); 
... 
fprintf(outFile, “O valor lido eh %8.2d\n”, num); 
... 
fclose(inFile); 
fclose(outFile); 
O handle é obtido no momento 
da abertura do arquivo 
I/O para arquivos 
• Se o handle retornar nulo do comando fopen, 
então ocorreu erro 
– arquivo não encontrado 
– arquivo travado contra gravação 
– permissão negada pelo sistema operacional, etc. 
• Sempre teste 
 if (NULL == (inFile = fopen(“arquivo.txt”, “r”))) { 
 printf(“Nao consegui abrir.\n”); 
 exit(1); 
} 
I/O para arquivos 
• Equivalências 
• gets()  fgets(arq, tamMax, string) 
• getchar()  fgetc(arq) 
• putc(ch)  fputc(arq, ch) 
• printf  fprintf(arq, string, valor) 
• scanf  fscanf(arq, string, endereço) 
I/O para arquivos 
• Exemplo 
 
I/O para arquivos 
• Exemplo (variação) 
08/09/2015 
5 
Movimentação em arquivos 
// retorna a posição atual do arquivo 
long ftell(FILE *f); 
 
// seta posição no arquivo, com relação à variável origin 
// retorna 0 se bem sucedido (offset em bytes). 
int fseek(FILE *f, long offset, int origin); 
 
 
origin 
Macro Valor deslocamento relativo 
SEEK_SET 0 Início do arquivo 
SEEK_CUR 1 Posição atual 
SEEK_END 2 Fim do arquivo 
Movimentação em arquivos 
int main(int argc, char **argv) { 
 FILE *f; 
 char str[512]; 
 
 f = fopen(“main.c”,"r"); 
 
 fgets(str, 512, f); 
 printf("%s\n", str); 
 
 fseek(f, 10, SEEK_SET); 
 fgets(str, 512, f); 
 printf("%s\n", str); 
 
 fseek(f, -10, SEEK_END); 
 fgets(str, 512, f); 
 printf("%s\n", str); 
 fclose(f); 
 return 0; 
} 
Outras funções úteis 
// cria um arquivo temporário (removido quando fechado) 
// retorno: handle para arquivo criado 
FILE *tmpfile(void); 
 
// gera um nome único que pode ser usado com nome de 
// arquivo 
char *tmpnam(char *); 
 
Leitura e escrita de blocos de dados 
// lê n objetos com tamanho de size bytes cada 
// retorno: número de objetos lidos 
size_t fread(void *ptr, size_t size, size_t n, FIE *f); 
 
 
// escreve n objetos com tamanho de siz bytes cada 
// retorno: número de objetos escritos 
size_t fwrite(void *ptr, size_t size, size_t n, FILE *f); 
#include <stdlib.h> 
#include <stdio.h> 
 
 
typedef struct { 
 string nome; 
 int matricula; 
 char conceito; 
} TipoAluno; 
 
int main() { 
 TipoAluno al; 
 
 al.nome = “Pedro” 
 al.matricula = 200712; 
 al.conceito = ‘A’; 
} 
 
 
Leitura e escrita de blocos de dados 
 
int main() { 
 TipoAluno al; 
 FILE *f; 
 int c; 
 
 al.nome = “Pedro” 
 al.matricula = 200712; 
 al.conceito = ‘A’; 
 
 f = fopen(“arquivo.dat”, 
 “w”); 
 c = fwrite(&al, 
 sizeof(TipoAluno), 
 1, f); 
 fclose(f); 
 return 0; 
} 
 
aeds2_aula_003_linguagem_C_TAD.pdf
12/09/2015 
1 
Tipo Abstrato de Dados 
3 Pontos Principais 
• Algoritmo e Programa 
 
• Tipo Abstrato de Dados 
– Qual papel do programador e do usuário do TAD 
 
• Conceitos de typedef e struct 
 
 
Programa vs Algoritmo 
• Qual a diferença entre um algoritmo e um 
programa? 
Algoritmos e Estruturas de Dados 
• Algoritmo: 
– Sequência de ações executáveis para a solução de 
um determinado tipo de problema 
– Exemplo: “Receita de Bolo” 
– Em geral, algoritmos trabalham sobre Estruturas 
de Dados 
Algoritmos e Estruturas de Dados 
• Estrutura de Dados 
– Conjunto de dados que representa uma situação 
real 
• Modo eficiente de armazenamento para facilitar seu 
acesso e modificação. 
– Estruturas de Dados e Algoritmos estão 
intimamente ligados 
 
Representação dos Dados 
• Os dados podem estar representados 
(estruturados) de diferentes maneiras 
 
• Normalmente, a escolha da representação é 
determinada pelas operações que serão 
utilizadas sobre eles 
12/09/2015 
2 
Representação dos Dados 
• Exemplo: números inteiros 
– Representação por palitinhos: II + IIII = IIIIII 
• Intuitiva 
• Operação simples 
• Inviável para grandes quantidades 
– Representação decimal: 1278 + 321 = 1599 
• Boa para grandes quantidades 
• Operação complexas são fáceis de serem executadas 
 
Programas 
• Um programa é uma formulação concreta de 
um algoritmo abstrato, baseado em 
representações de dados específicas 
• Os programas são feitos em alguma linguagem 
que pode ser entendida e seguida pelo 
computador 
– Linguagem de máquina 
– Linguagem de alto nível (uso de compilador) 
– Nós vamos utilizar a Linguagem C (nível médio) 
Compiladores, Interpretadores, Sistema Operacional 
9 
Tipos Abstratos de Dados (TADs) 
• Agrupa a estrutura de dados juntamente com 
as operações que podem ser feitas sobre esses 
dados 
• O TAD encapsula a estrutura de dados. Os 
usuários do TAD só tem acesso a algumas 
operações disponibilizadas sobre esses dados 
• Usuário do TAD x Programador do TAD 
– Usuário só “enxerga” a interface, não a 
implementação 
Tipos Abstratos de Dados (TADs) 
• Dessa forma, o usuário pode abstrair da 
implementação específica. 
 
• Qualquer modificação na implementação fica 
restrita ao TAD 
 
• A escolha de uma representação específica é 
fortemente influenciada pelas operações a 
serem executadas 
Tipos Abstratos de Dados (TADs) 
• Agrupa a estrutura de dados
juntamente com 
as operações que podem ser feitas sobre 
esses dados 
• Qualquer modificação na implementação fica 
restrita ao TAD 
 
 
 
12/09/2015 
3 
Tipos Abstratos de Dados (TADs) 
Aplicação 
Especificação 
Implementação 
Usuário do TAD 
Programador do TAD 
Exemplo: Lista de números inteiros 
 • Operações 
– Faz Lista Vazia 
– Insere número no começo da lista 
– Remove de uma posição i 
 
20 13 02 30 Implementação por Vetores: 
void Insere(int x, Lista L) { 
 for(i=0;...) {...} 
 L[0] = x; 
} 
20 13 02 30 
Implementação por Listas Encadeadas 
void Insere(int x, Lista L) { 
 p = CriaNovaCelula(x); 
 L.primeiro = p; 
 ... 
} 
Programa usuário do TAD: 
int main() { 
 Lista L; 
 int x; 
 
 x = 20; 
 FazListaVazia(L); 
 Insere(x,L); 
 ... 
} 
Implementação de TADs 
• Em linguagens orientadas por objeto (C++, Java) a 
implementação é feita através de classes 
• Em linguagens estruturadas (C, pascal) a implementação 
é feita pela definição de tipos juntamente com a 
implementação de funções 
• Vamos utilizar os conceitos em C (typedef e 
structs) 
Estruturas (Structs) em C 
• Uma estrutura é uma coleção de uma ou mais variáveis, 
possivelmente de tipos diferentes, colocadas juntas sob um 
único nome para manipulação conveniente 
• Exemplo: 
– para representar um aluno são necessárias as informações nome, 
matrícula, conceito 
– Ao invés de criar três variáveis, é possível criar uma única variável 
contendo três campos. 
• Em C, usa-se a construção struct para representar esse tipo 
de dado 
Estruturas (Structs) em C 
• Sintaxe: 
struct nome { 
 [tipo nome_da_variável] ; 
 ... 
} [variável] ; 
 struct Aluno { 
 string nome; 
 int matricula; 
 char conceito; 
}; 
Estruturas (Structs) em C 
 
struct Aluno { 
 string nome; 
 int matricula; 
 char conceito; 
}; 
 
main() { 
 struct Aluno al, aux; 
 
 al.nome = “Pedro” 
 al.matricula = 200712; 
 al.conceito = ‘A’; 
 aux = al; 
} 
Pedro 
200712 A 
al: 
Pedro 
200712 A 
aux: 
12/09/2015 
4 
Estruturas (Structs) em C 
struct Aluno { 
 string nome; 
 int matricula; 
 char conceito; 
}; 
 
struct Professor{ 
 string nome; 
 int matricula; 
 string classes[3]; 
}; 
 
main() { 
 struct Aluno al; 
 struct Professor pr; 
 
 al.nome = “Pedro”; 
 pr.nome = “José”; 
} 
main() { 
string alunoNome; 
int alunoMatricula; 
Char alunoConceito; 
string alunoNome2; 
int alunoMatricula2; 
Char alunoConceito2; 
string professorNome; 
int professorMatricula; 
string professoClasses[3]; 
 
 
 alunoNome = “Pedro” 
 alunoMatricula = 200712; 
 alunoConceito = ‘A’; 
 alunoNome2 = alunoNome; 
 alunoMatricula2 = alunoMatricula; 
 alunoConceito2 = alunoConceito; 
} 
Declaração de Tipos 
• Para simplificar, uma estrutura ou mesmo 
outros tipos de dados podem ser definidos 
como um novo tipo 
– Em C você precisa usar: struct tipo variavel 
• Sintaxe: typedef tipo identificador; 
typedef struct { 
 string nome; 
 int matricula; 
 char conceito; 
} TipoAluno; 
 
typedef int Vetor[10]; 
int main() { 
 TipoAluno al; 
 Vetor v; 
 
 ... 
} 
TADs em C 
• Para implementar um Tipo Abstrato de Dados em 
C, usa-se a definição de tipos juntamente com a 
implementação de funções que agem sobre 
aquele tipo 
 
• Como boa regra de programação, evita-se acessar 
o dado diretamente, fazendo o acesso só através 
das funções 
– Mas, diferentemente de C++ e Java, não há uma 
forma de proibir o acesso. 
TADs em C 
• Uma boa técnica de programação é 
implementar os TADs em arquivos separados do 
programa principal 
• Para isso geralmente separa-se a declaração e a 
implementação do TAD em dois arquivos: 
– NomeDoTAD.h : com a declaração 
– NomeDoTAD.c : com a implementação 
• O programa ou outros TADs que utilizam o seu 
TAD devem dar um #include no arquivo .h 
TADs em C 
Aplicação 
Especificação 
Implementação 
Usuário do TAD 
Programador do TAD 
arquivo .c 
arquivo .h 
Exemplo 
• Implemente um TAD de vetores em 3D e as 
seguintes operações: 
– Iniciar um vetor 
– Calcular a norma de um vetor 
– Calcular o produto escalar entre dois vetores 
– Normaliza um vetor 
• Faça um pequeno programa para testar o seu 
TAD 
 
12/09/2015 
5 
vetor.h 
#ifndef _VETOR_H_ 
#define _VETOR_H_ 
 
// definição do tipo 
typedef struct { 
 float x, y, z; 
} TipoVetor; 
 
// cabeçalho das funções 
float norma(TipoVetor v); 
TipoVetor inicializa(float x, float y, float z); 
void normaliza(TipoVetor *v); 
float produto_escalar(TipoVetor v1, TipoVetor v2); 
 
#endif 
vetor.c 
#include “vetor.h“ 
#include <math.h> 
 
TipoVetor Inicializa(float x, float y, float z) { 
 TipoVetor v; 
 v.x = x; v.y = y; v.z = z; 
 return v; 
} 
 
float norma(TipoVetor v) { 
 return sqrt( pow(v.x,2) + pow(v.y,2) + pow(v.z,2)); 
} 
 
void normaliza(TipoVetor *v) { 
 float n = norma(*v); 
 v->x /= n; 
 v->y /= n; 
 v->z /= n; 
} 
float produto_escalar(TipoVetor v1, TipoVetor v2) { 
 return ( v1.x*v2.x + v1.y*v2.y + v1.z*v2.z) 
} 
Main.c 
 #include<stdio.h> 
#include<stdlib.h> 
#include “vetor.h" 
 
int main (void) { 
 TipoVetor v1 = Inicializa(10, 20, 30); 
 TipoVetor v2 = Inicializa(3, 5, 7); 
 
 printf(“Norma v1: %f”, norma(v1)); 
 printf(“Norma v2: %f”, norma(v2)); 
 
 float n1 = norma(v1); 
 float n2 = norma(v2); 
 float theta = acos(produto_escalar(v1,v2)/(n1*n2)); 
 printf(“Angulo v1,v2: %f”, theta); 
 
 return 0; 
} 
vetor.h 
#ifndef _VETOR_H_ 
#define _VETOR_H_ 
 
// definição do tipo 
typedef struct { 
 float v[3]; 
} TipoVetor; 
 
// cabeçalho das funções 
float norma(TipoVetor v); 
TipoVetor inicializa(float x, float y, float z); 
void normaliza(TipoVetor *v); 
float produto_escalar(TipoVetor v1, TipoVetor v2); 
 
#endif 
Main.c 
 #include<stdio.h> 
#include<stdlib.h> 
#include “vetor.h" 
 
int main (void) { 
 TipoVetor v1 = Inicializa(10, 20, 30); 
 TipoVetor v2 = Inicializa(3, 5, 7); 
 
 printf(“Norma v1: %f”, norma(v1)); 
 printf(“Norma v2: %f”, norma(v2)); 
 
 float n1 = norma(v1); 
 float n2 = norma(v2); 
 float theta = acos(produto_escalar(v1,v2)/(n1*n2)); 
 printf(“Angulo v1,v2: %f”, theta); 
 
 return 0; 
} 
TADs em C 
Aplicação 
Especificação 
Implementação 
Usuário do TAD 
Programador do TAD 
Vetor.c 
Vetor.h 
main.c 
12/09/2015 
6 
TADs em C 
• Acesso direto dos dados (errado!) 
20 13 02 30 Implementação por Vetores: 
20 13 02 30 
Implementação por Listas Encadeadas 
Programa usuário do TAD: 
typedef struct { 
 int dado[100]; 
} Lista; 
typedef struct item { 
 int dado; 
 struct item *prox; 
} Item; 
 
typedef struct { 
 Item *inicio; 
} Lista;
int main() { 
 Lista L; 
 
 L.dado[0] = 20; 
} 
aeds2_aula_004_alocacao_dinamica.pdf
1 
Alocação Dinâmica de 
Memória 
Alocação Estática x Dinâmica 
• C: dois tipos de alocação de memória: Estática e 
Dinâmica 
• Na alocação estática, o espaço para as variáveis é 
reservado no início da execução, não podendo 
ser alterado depois 
– int a; int b[20]; 
 
• Na alocação dinâmica, o espaço para as variáveis 
pode ser alocado dinamicamente durante a 
execução do programa 
 
Alocação Dinâmica 
• As variáveis alocadas dinamicamente são 
chamadas de Apontadores (pointers) pois na 
verdade elas armazenam o endereço de 
memória de uma variável 
 
• A memória alocada dinamicamente faz parte 
de uma área de memória chamada heap 
– Basicamente, o programa aloca e desaloca 
porções de memória do heap durante a execução 
Organização da Memória 
Informação sobre funções 
Código compilado 
Memória Dinâmica 
Esquema de Memória 
Memória Estática 
0x016 a 
0x020 b 
10 
0X234 
10 
a é um int 
b é um apontador para um int 
Heap 
0X214 
0X218 
0X222 
0X226 
0X230 
0X234 
0X238 
0X240 
Acesso a partir de Apontadores 
• Acessar o valor da variável: endereço de 
memória armazenado 
• Acessar o conteúdo que associado ao 
endereço de memória armazenado 
2 
Liberação de Memória 
• A memória deve ser liberada após o término 
de seu uso 
• A liberação deve ser feita por quem fez a 
alocação: 
– Estática: compilador 
– Dinâmica: programador 
 
Apontadores – Notação 
• definição de p como um apontador para uma variável do tipo Tipo 
– Tipo *p; 
• Alocação de memória para uma variável apontada por p 
– p = (Tipo*) malloc(sizeof(Tipo)); 
• Liberação de memória 
– free(p); 
• Conteudo da variável apontada por P 
– *p; 
• Valor nulo para um apontador 
– NULL; 
• Endereço de uma variável a 
– &a; 
 
Alocação Dinâmica 
int *a, b; 
... 
b = 10; 
a = (int *) malloc(sizeof(int)); 
*a = 20; 
a = &b; 
a 
20 
b 
Heap Alocação 
Estática 
10 
? 
Erros Comuns 
• Esquecer de alocar memória e tentar acessar o 
conteúdo da variável 
• Copiar o valor do apontador ao invés do valor da 
variável apontada 
• Esquecer de desalocar memória 
– Ela é desalocada ao fim do programa ou 
procedimento função onde a variável está declarada, 
mas pode ser um problema em loops 
• Tentar acessar o conteúdo da variável depois de 
desalocá-la 
Pergunta que não quer calar... 
int *a não é a declaração de um vetor de int? 
 
• Em C, todo vetor é um apontador. 
• Portanto pode-se fazer coisas como: 
int a[10], *b; 
b = a; 
b[5] = 100; 
Printf(“%d\n”, a[5]); 
Printf(“%d\n”, b[5]); 
 
int a[10], *b; 
b = (int *) malloc(10*sizeof(int)); 
b[5] = 100; 
printf(“%d\n”, a[5]); 
Printf(“%d\n”, b[5]); 
100 
100 
42657 
100 
Obs. Não se pode fazer a = b 
 no exemplo acima 
Apontadores para Tipos Estruturados 
• Apontadores são normalmente utilizados com 
tipos estruturados 
typedef struct { 
 int idade; 
 double salario; 
} TRegistro; 
 
TRegistro *a; 
... 
a = (TRegistro *) malloc(sizeof(TRegistro)) 
a->idade = 30; /* *a.idade = 30 */ 
a->salario = 80; 
3 
Passagem de Parâmetros 
• Em pascal, parâmetros para função podem ser passados 
por valor ou por referência 
– Por valor: o parâmetro formal (recebido no procedimento) é 
uma cópia do parâmetro real (passado na chamada) 
– Por referência: o parâmetro formal (recebido no procedimento) 
é uma referência para o parâmetro real (passado na chamada) 
• Usa-se o termo var precedendo o parâmetro formal 
• Em C só existe passagem por valor, logo deve-se 
implementar a passagem por referência utilizando-se 
apontadores 
Passagem de Parâmetros (C) 
void SomaUm(int x, int *y) 
{ 
 x = x + 1; 
 *y = (*y) + 1; 
 printf("Funcao SomaUm: %d %d\n", x, *y); 
} 
 
int main() 
{ 
 int a=0, b=0; 
 SomaUm(a, &b); 
 printf("Programa principal: %d %d\n", a, b); 
} 
1 1 
0 1 
Passagem de Parâmetros 
• E para alocar memória dentro de um procedimento? 
– O ponteiro *a está sendo passando por cópia 
– a e x estão apontando para o mesmo endereço 
void aloca(int *x, int n) 
{ 
 x=(int *)malloc(n*sizeof(int)); 
 x[0] = 20; 
} 
int main() 
{ 
 int *a; 
 aloca(a, 10); 
 a[1] = 40; 
} 
Error! 
Access Violation! 
Passagem de Parâmetros 
• E para alocar memória dentro de um procedimento? 
void aloca(int *x, int n) { 
 x=(int *)malloc(n*sizeof(int)); 
 x[0] = 20; 
} 
 
int main() { 
 int *a; 
 aloca(a, 10); 
 a[1] = 40; 
} 
Error! 
Access Violation! 
void aloca(int **x, int n) { 
 *x=(int *)malloc(n*sizeof(int)); 
 *x[0] = 20; 
} 
 
int main() { 
 int *a; 
 aloca(&a, 10); 
 a[1] = 40; 
} 
OK 
Quantidade não definida de argumentos 
#include <cstdarg.h> 
#include <stdio.h> 
 
double average ( int num, ... ) { 
 va_list arguments; 
 arguments double sum = 0; 
 va_start ( arguments, num ); 
 for ( int x = 0; x < num; x++ ) 
 sum += va_arg ( arguments, double ); 
 va_end ( arguments ); 
 return sum/num; 
} 
 
void main() { 
 printf(“%f”, average ( 3, 12.2, 22.3, 4.5 )); 
} 
aeds2_aula_005_listas_lineares.pdf
23/09/2015 
1 
Listas Lineares 
Livro “Projeto de Algoritmos” – Nívio Ziviani 
Capítulo 3 – Seção 3.1 
http://www2.dcc.ufmg.br/livros/algoritmos/ 
(adaptado) 
 
Agenda 
• Listas lineares 
• TAD para listas lineares 
• Alocação sequencial 
• Alocação encadeada 
Listas Lineares 
• Maneira de representar elementos de um 
conjunto. 
• Itens podem ser acessados, inseridos ou retirados 
de uma lista. 
• Podem crescer ou diminuir de tamanho durante a 
execução. 
• Adequadas quando não é possível prever a 
demanda por memória 
Definição de Listas Lineares 
• Sequência de zero ou mais itens 
– x1 ,x2 ,···,xn , na qual xi é de um determinado tipo e n representa o 
tamanho da lista linear. 
 
• Sua principal propriedade estrutural envolve as posições relativas 
dos itens em uma dimensão. 
– Assumindo n ≥ 1, x1 é o primeiro item da lista e xn é o último item da 
lista. 
– xi precede xi+1 para i = 1,2,···,n – 1 
– xi sucede xi-1 para i = 2,3,···,n 
– o elemento xi é dito estar na i-ésima posição da lista. 
TAD Listas Lineares 
• TAD: Agrupa a estrutura de dados juntamente com as 
operações que podem ser feitas sobre esses dados. 
 
• As duas representações mais utilizadas são as 
implementações 
– Alocação sequencial 
– Alocação encadeada 
 
 
Projetando TAD de Listas Lineares 
• O conjunto de operações a ser definido depende de cada 
aplicação. 
• Um conjunto de operações necessário a uma maioria de 
aplicações é: 
1) Criar uma lista linear vazia. 
2) Inserir um novo item imediatamente após o i-ésimo item. 
3) Retirar o i-ésimo item. 
4) Localizar o i-ésimo item para examinar e/ou alterar o conteúdo de seus 
componentes. 
5) Combinar duas ou mais listas lineares em uma lista única. 
6) Partir uma lista
linear em duas ou mais listas. 
7) Fazer uma cópia da lista linear. 
8) Ordenar os itens da lista em ordem ascendente ou descendente, de acordo 
com alguns de seus componentes. 
9) Pesquisar a ocorrência de um item com um valor particular em algum 
componente. 
23/09/2015 
2 
Projetando TAD de Listas Lineares 
• Exemplo de Conjunto de Operações: 
 
1) FLVazia(Lista). Faz a lista ficar vazia. 
2) Insere(x, Lista). Insere x após o último item da lista. 
3) Retira(p, Lista, x). Retorna o item x que está na posição p da lista, retirando-o 
da lista e deslocando os itens a partir da posição p+1 para as posições 
anteriores. 
4) Vazia(Lista). Esta função retorna true se lista vazia; senão retorna false. 
5) Imprime(Lista). Imprime os itens da lista na ordem de ocorrência. 
Implementação usando alocação sequencial 
• Localização na memória: 
– Posições contíguas. 
 
• Visita: 
– Pode ser percorrida em qualquer direção. 
– Permite acesso aleatório. 
 
• Inserção: 
– Realizada após o último item com custo constante. 
– Um novo item no meio da lista custo não constante. 
 
• Remoção: 
– Final da lista: custo constante 
– Meio ou início: requer deslocamento de itens 
Alocação Sequencial (estrutura) 
• Os itens armazenados em um array. 
• MaxTam define o tamanho máximo permitido 
para a lista. 
• O campo Último aponta para a posição 
seguinte a do último elemento da lista. 
(primeira posição vazia) 
• O i-ésimo item da lista está armazenado na i-
ésima-1 posição do array, 0 ≤ i < Último. 
(Item[i]) 
 
#define InicioArranjo 0 
#define MaxTam 1000 
 
typedef int TipoChave; 
 
typedef int Apontador; 
 
typedef struct { 
 TipoChave Chave; 
 /* outros componentes */ 
} TipoItem; 
 
typedef struct { 
 TipoItem Item[MaxTam]; 
 Apontador Primeiro, Ultimo; 
} TipoLista; 
Item 
Alocação Sequencial (estrutura) 
• Os itens armazenados em um array. 
• MaxTam define o tamanho máximo permitido 
para a lista. 
• O campo Último aponta para a posição 
seguinte a do último elemento da lista. 
(primeira posição vazia) 
• O i-ésimo item da lista está armazenado na i-
ésima-1 posição do array, 0 ≤ i < Último. 
(Item[i]) 
 
#define InicioArranjo 0 
#define MaxTam 1000 
 
typedef int TipoChave; 
 
typedef int Apontador; 
 
typedef struct { 
 TipoChave Chave; 
 /* outros componentes */ 
} TipoItem; 
 
typedef struct { 
 TipoItem Item[MaxTam]; 
 Apontador Primeiro, Ultimo; 
} TipoLista; 
Item 
Alocação Sequencial (estrutura) 
• Os itens armazenados em um array. 
• MaxTam define o tamanho máximo permitido 
para a lista. 
• O campo Último aponta para a posição 
seguinte a do último elemento da lista. 
(primeira posição vazia) 
• O i-ésimo item da lista está armazenado na i-
ésima-1 posição do array, 0 ≤ i < Último. 
(Item[i]) 
 
const InicioArranjo = 0; 
const MaxTam = 1000; 
 
typedef int TipoChave; 
 
typedef int Apontador; 
 
typedef struct { 
 TipoChave Chave; 
 /* outros componentes */ 
} TipoItem; 
 
typedef struct { 
 TipoItem Item[MaxTam]; 
 Apontador Primeiro, Ultimo; 
} TipoLista; 
Item 
Alocação Sequencial (estrutura) 
• Os itens armazenados em um array. 
• MaxTam define o tamanho máximo permitido 
para a lista. 
• O campo Último aponta para a posição 
seguinte a do último elemento da lista. 
(primeira posição vazia) 
• O i-ésimo item da lista está armazenado na i-
ésima-1 posição do array, 0 ≤ i < Último. 
(Item[i]) 
 
const InicioArranjo = 0; 
const MaxTam = 1000; 
 
typedef int TipoChave; 
 
typedef int Apontador; 
 
typedef struct { 
 TipoChave Chave; 
 /* outros componentes */ 
} TipoItem; 
 
typedef struct { 
 TipoItem Item[MaxTam]; 
 Apontador Primeiro, Ultimo; 
} TipoLista; Ultimo 
Primeiro 
MaxTam 
Item[0] 
Item[1] 
Item 
23/09/2015 
3 
/* faz lista ficar vazia */ 
void FLVazia(TipoLista *Lista) 
{ 
 Lista->Primeiro = InicioArranjo; 
 Lista->Ultimo = Lista->Primeiro; 
} /* FLVazia */ 
 
Alocação Sequencial (operações) 
??? 
??? 
??? 
??? 
… 
??? 
MaxTam 
/* faz lista ficar vazia */ 
void FLVazia(TipoLista *Lista) 
{ 
 Lista->Primeiro = InicioArranjo; 
 Lista->Ultimo = Lista->Primeiro; 
} /* FLVazia */ 
 
Alocação Sequencial (operações) 
??? 
??? 
??? 
??? 
… 
??? 
MaxTam 
Ultimo 
Primeiro 
/* faz lista ficar vazia */ 
void FLVazia(TipoLista *Lista) 
{ 
 Lista->Primeiro = InicioArranjo; 
 Lista->Ultimo = Lista->Primeiro; 
} /* FLVazia */ 
 
 
/* testa se a lista está vazia */ 
int Vazia(const TipoLista *Lista) 
{ 
 return (Lista->Primeiro == Lista->Ultimo); 
} /* Vazia */ 
 
 
Alocação Sequencial (operações) 
??? 
??? 
??? 
??? 
… 
??? 
MaxTam 
Ultimo 
Primeiro 
void Insere(TipoItem x, TipoLista *Lista) 
{ 
 if (Lista->Ultimo >= MaxTam) 
 printf("Lista esta cheia\n"); 
 else 
 { 
 Lista->Item[Lista->Ultimo] = x; 
 Lista->Ultimo++; 
 } 
} /* Insere */ 
Alocação Sequencial (operações) 
??? 
??? 
??? 
??? 
… 
??? 
MaxTam 
Ultimo 
Primeiro 
void Insere(TipoItem x, TipoLista *Lista) 
{ 
 if (Lista->Ultimo >= MaxTam) 
 printf("Lista esta cheia\n"); 
 else 
 { 
 Lista->Item[Lista->Ultimo] = x; 
 Lista->Ultimo++; 
 } 
} /* Insere */ 
Alocação Sequencial (operações) 
??? 
??? 
??? 
??? 
… 
??? 
MaxTam 
Ultimo 
Primeiro 
x 
??? 
??? 
??? 
… 
??? 
MaxTam 
Ultimo 
Primeiro 
void Retira(Apontador p, TipoLista *Lista, TipoItem *Item) { 
 Apontador Aux; 
 if (Vazia(Lista) || p >= Lista->Ultimo) { 
 printf("Erro: Posicao nao existe\n"); 
 return; 
 } 
 *Item = Lista->Item[p]; 
 Lista->Ultimo--; 
 for (Aux = p+1; Aux <= Lista->Ultimo; Aux++) 
 Lista->Item[Aux - 1] = Lista->Item[Aux]; 
} 
Alocação Sequencial (operações) 
23/09/2015 
4 
void Retira(Apontador p, TipoLista *Lista, TipoItem *Item) { 
 Apontador Aux; 
 if (Vazia(Lista) || p >= Lista->Ultimo) { 
 printf("Erro: Posicao nao existe\n"); 
 return; 
 } 
 *Item = Lista->Item[p]; 
 Lista->Ultimo--; 
 for (Aux = p+1; Aux <= Lista->Ultimo; Aux++) 
 Lista->Item[Aux - 1] = Lista->Item[Aux]; 
} 
x1 
x2 
x3 
??? 
… 
??? 
Ultimo 
Primeiro 
p 
Alocação Sequencial (operações) 
x1 
x2 
x3 
??? 
… 
??? 
Ultimo 
Primeiro 
p 
x1 
x2 
x3 
??? 
… 
??? 
Ultimo 
Primeiro 
p 
Alocação Sequencial (operações) 
void Retira(Apontador p, TipoLista *Lista, TipoItem *Item) { 
 Apontador Aux; 
 if (Vazia(Lista) || p >= Lista->Ultimo) { 
 printf("Erro: Posicao nao existe\n"); 
 return; 
 } 
 *Item = Lista->Item[p]; 
 Lista->Ultimo--; 
 for (Aux = p+1; Aux <= Lista->Ultimo; Aux++) 
 Lista->Item[Aux - 1] = Lista->Item[Aux]; 
} 
x1 
x2
x3 
??? 
… 
??? 
Ultimo 
Primeiro 
p 
x1 
x2 
x3 
??? 
… 
??? 
Ultimo 
Primeiro 
p 
x1 
x3 
x3 
??? 
… 
??? 
Ultimo 
Primeiro 
Alocação Sequencial (operações) 
void Retira(Apontador p, TipoLista *Lista, TipoItem *Item) { 
 Apontador Aux; 
 if (Vazia(Lista) || p >= Lista->Ultimo) { 
 printf("Erro: Posicao nao existe\n"); 
 return; 
 } 
 *Item = Lista->Item[p]; 
 Lista->Ultimo--; 
 for (Aux = p+1; Aux <= Lista->Ultimo; Aux++) 
 Lista->Item[Aux - 1] = Lista->Item[Aux]; 
} 
void Imprime(const TipoLista *Lista){ 
 Apontador i; 
 
 for (i = Lista->Primeiro; i < Lista->Ultimo; i++) 
 
 printf("%d\n", Lista->Item[i].Chave); 
} 
x1 
x2 
x3 
??? 
… 
??? 
Ultimo 
Primeiro 
Alocação Sequencial (operações) 
Alocação Sequencial 
• Vantagens: 
– economia de memória, pois cada elemento da 
lista armazena apenas os dados. 
– A estrutura da lista é definida implicitamente 
– Acesso a um item qualquer é CONSTANTE 
 
 
 
 
Alocação Sequencial 
• Desvantagens: 
– custo para inserir ou retirar itens da lista, que 
pode causar um deslocamento de todos os itens 
• no pior caso É IGUAL AO TAMANHO DO VETOR: CUSTO 
LINEAR! 
– O tamanho máximo da lista é fixo e definido em 
tempo de compilação! 
• Pouco útil para aplicações em que não existe previsão 
sobre o crescimento da lista. 
 
 
23/09/2015 
5 
Alocação Sequencial 
• Como resolver o problema de tamanho fixo? 
Alocação Encadeada 
• Permite utilizar posições não contíguas de 
memória 
• É possível inserir e retirar elementos sem 
necessidade de deslocar os itens seguintes da 
lista 
 
 
 
 
Sobre os Elementos da Lista 
• Uma célula guarda as informações sobre cada 
elemento. 
• Cada célula possui: 
– campo de informações 
– ponteiro para o próximo elemento 
 
 info 
prox 
Alocação Encadeada 
info 
info 
prox 
info 
NULL 
info 
NULL 
info 
prox 
prox 
prox 
• Características: 
– Tamanho da lista não é pré-definido 
– Cada elemento guarda quem é o próximo 
– Elementos não estão contíguos na memória 
 
Alocação Encadeada 
• Uma lista encadeada pode ser organizada de 
duas maneiras diferentes: 
– Lista sem cabeça: A primeira célula contém 
conteúdo. 
 
Alocação Encadeada 
• Uma lista encadeada pode ser organizada de 
duas maneiras diferentes: 
– Lista com cabeça: O conteúdo da primeira célula é 
irrelevante. Essa célula apenas marcar o início da 
lista. 
 
 
 
 
23/09/2015 
6 
Alocação Encadeada 
• Lista sem cabeça 
– Operações de Inserção e Remoção exigem que 
seja verificado se ponteiro para a primeiro célula é 
igual a NULL 
• Lista com cabeça 
– Evita os testes com a primeira célula e assim 
melhora o desempenho 
Sobre a Lista 
• Uma lista é definida como um apontador para 
a primeira elemento 
• Uma lista pode ter um apontador para o 
última célula 
 
info 
prox prox 
info 
prox 
info 
NULL 
Último 
Primeiro 
Implementação em C 
typedef int TipoChave; 
 
typedef struct { 
 TipoChave Chave; 
 /* outros componentes */ 
} TipoItem; 
 
typedef struct Celula_str *Apontador; 
 
typedef struct Celula_str { 
 TipoItem Item; 
 Apontador Prox; 
} Celula; 
 
typedef struct { 
 Apontador Primeiro, Ultimo; 
} TipoLista; 
Implementação em C 
Último 
Primeiro 
TipoLista 
Prox 
3.14 
Celula 
Prox 
9.8 
Celula 
NULL 
Cria Lista Vazia 
prox 
Cabeça 
Último 
Primeiro 
void FLVazia(TipoLista *Lista) 
{ 
 Lista->Primeiro = (Apontador) malloc(sizeof(Celula)); 
 Lista->Ultimo = Lista->Primeiro; 
 Lista->Primeiro->Prox = NULL; 
} 
 
int Vazia(const TipoLista *Lista) 
{ 
 return (Lista->Primeiro == Lista->Ultimo); 
} 
NULL 
Inserção de Elementos na Lista 
info 
prox prox 
info 
prox 
info 
NULL 
Último 
 3 opções de posição onde pode inserir: 
 1ª. posição 
 última posição 
 Após um elemento qualquer E 
Primeiro 
23/09/2015 
7 
Inserção na Primeira Posição 
info 
prox prox 
info 
prox 
info 
NULL 
Último 
info 
NULL 
Primeiro 
Novo 
prox 
Inserção na Última Posição 
info 
prox prox 
info 
prox 
info 
NULL 
Último 
info 
NULL prox 
Primeiro 
Novo 
NULL 
Inserção na Após o Elemento E 
prox 
info 
prox 
info 
NULL 
Último 
info 
NULL 
Elem E 
info 
prox 
Primeiro 
Novo 
prox 
Inserção de elementos na Lista 
• Na verdade, as 3 opções de inserção são 
equivalentes a inserir após uma célula 
apontada por p 
– 1ª posição: p é a célula cabeça 
– Última posição: p é o último 
– Após um elemento qualquer E: p aponta para 
E 
 
Inserção na Após o Elemento E 
prox 
info 
prox 
info 
NULL Último 
info 
NULL prox 
Elem E 
info 
prox 
Primeiro novo 
void Insere(TipoItem x, TipoLista *lista, Apontador E){ 
 Apontador novo; 
 
 novo = (Apontador) malloc(sizeof(Celula)); 
 novo->Item = x; 
 novo->prox = E->prox; 
 E->prox = novo; 
} 
x 
Retirada de Elementos na Lista 
info 
prox prox 
info 
prox 
info 
NULL 
Último 
 3 opções de posição de onde pode retirar: 
 1ª. posição 
 última posição 
 Um elemento qualquer E 
23/09/2015 
8 
Retirada do Elemento na 
Primeira Posição da Lista 
info 
prox prox 
info 
prox 
info 
NULL 
Último Primeiro 
Temp 
Retirada do Último Elemento da Lista 
info 
prox prox 
info 
prox 
info 
NULL 
Último 
Anterior 
Primeiro 
prox NULL 
Retirada do Elemento E da Lista 
info 
prox prox 
info 
prox 
info 
NULL 
Último 
Elem E 
Anterior 
Primeiro 
Retirada do elemento após E da Lista 
info 
prox prox 
info 
prox 
info 
NULL 
Último E Primeiro 
int RemoveProx(TipoLista *lista, Apontador E, TipoItem 
*item){ 
 Apontador tmp; 
 tmp = E->prox; 
 if (tmp != NULL) { 
 E->prox = tmp->prox; *item = tmp->item; 
 if (e->prox == NULL) lista->ultimo = e; 
 free(tmp); 
 return 1; 
 } else return 0; 
} 
tmp 
Alocação Encadeada 
• Localização na memória: 
– Posições não sequenciais 
• Visita: 
– Apenas na direção xi para xi+1. 
– Permite apenas acesso sequencial. 
• Inserção: 
– Realizada em qualquer posição com custo constante. 
• Remoção: 
– Custo constante em qualquer posição. 
Alocação Encadeada 
• Vantagens 
– Permite inserir ou retirar itens do meio da lista a um custo 
constante (importante quando a lista tem de ser mantida 
em ordem). 
– Bom para aplicações em que não existe previsão sobre o 
crescimento da lista (o tamanho máximo da lista não 
precisa ser definido a priori). 
• Desvantagens 
– Utilização de memória extra para armazenar os 
apontadores. 
– Custo linear para acessar
um item no pior caso 
 
23/09/2015 
9 
Exemplo: Ordenação 
• Problema: Ordenar uma lista com alocação 
encadeada em tempo linear. Esta lista 
apresenta chaves inteiras com valores entre 0 
e 255 
1 
 
dados1 
prox 
0 
 
dados2 
prox 
241 
 
dados3 
prox 
0 
 
dados4 
prox 
31 
 
dados5 
NULL 
. . . 
Último Primeiro 
Exemplo: Ordenação 
 Problema: Ordenar uma lista com alocação encadeada em 
tempo linear. Esta lista apresenta chaves inteiras com valores 
entre 0 e 255. 
1 
 
dados1 
prox 
0 
 
dados2 
prox 
241 
 
dados3 
prox 
0 
 
dados4 
prox 
31 
 
dados5 
NULL 
. . . 
Último Primeiro 
Exemplo: Ordenação 
• Percorra lista original 
– Utilize a chave de cada elemento para indexar o vetor 
– Insira o elemento como último elemento da lista 
correspondente 
• Crie uma nova lista com alocação dinâmica 
• Percorrer cada elemento do vetor em ordem 
sequencial 
– Percorre cada item da lista correspondente 
– Insere item na nova lista 
 
 
Exemplo: Ordenação 
• Solução: Criar um vetor com 256 posições contendo 
ponteiros para listas com alocação dinâmica. 
 
… 
0 
255 
0 
 
dados 
prox 
Lista 0 
Lista 255 
0 
 
dados 
prox 
. . . 
. . . 
0 
 
dados 
NULL 
255 
 
dados 
prox 
255 
 
dados 
prox 
. . . 
255 
 
dados 
NULL 
Exemplo: Crivo de Eratóstenes 
• Crie uma lista com números de 2 até n. 
 
• Encontre o primeiro número da lista. 
 
• Remova da lista todos os múltiplos do 
número primo encontrado. 
 
• O próximo número da lista é primo. 
 
• Repita o procedimento. 
 
• Ao final, a lista contém somente 
números primos. 
Avisos 
• Data das provas: 
– Prova 1: 13/10/2015 
 
– Prova 2: 10/11/2015 
 
– Prova 3: 15/12/2015 
23/09/2015 
10 
Avisos 
• TP0 disponível em: 
– No moodle 
– exemplo_documentacao_aeds2.pdf 
– Entrega no dia 06/10/2015 até 23:55 
• Monitoria 
– Bernardo: Quarta: 15 às 17h (sala 3017) 
– Gabriel: Segunda: 13 às 15h (sala 3017) 
aeds2_aula_006_pilhas_e_filas.pdf
24/09/2015 
1 
Pilhas e Filas 
 
 
TAD Pilhas 
• Tipo Abstrato de dados com a seguinte 
característica: 
– O último elemento a ser inserido é o primeiro a ser 
retirado (LIFO – Last In First Out) 
• Usos: Chamada de subprogramas, 
avaliação de expressões aritméticas, 
etc... 
 
 
 
TAD Pilhas 
M
a
xT
a
m
 
Topo 
Pilha 
Implementação de Pilhas com 
Alocação Sequencial 
• Os itens da pilha são armazenados em 
posições contíguas de memória. 
 
• Inserções e retiradas: apenas no topo 
 
• Variável Topo é utilizada para controlar a 
posição do item no topo da pilha. 
 
Topo 
Pilha 
Empilha(21, Pilha) Desempilha(Pilha) 
21 
Topo 
Pilha 
Empilha(3, Pilha) 
21 
3 
Topo 
Pilha 
21 
Topo 
Pilha 
retorna 3 
. 
Implementação de Pilhas com 
Alocação Sequencial 
Estrutura de Dados de Pilhas com 
alocação Sequencial 
const MaxTam = 1000; 
 
typedef int Apontador; 
typedef int TipoChave; 
 
typedef struct { 
 TipoChave Chave; 
 /* outros componentes */ 
} TipoItem; 
 
typedef struct { 
 TipoItem Item[MaxTam]; 
 Apontador Topo; 
} TipoPilha; 
Item[0] 
Item[1] 
Item[2] 
Item[3] 
... 
Item[MaxTam-1] 
Topo 
Pilha 
MaxTam 
24/09/2015 
2 
void FPVazia(TipoPilha *Pilha){ 
 Pilha->Topo = 0; 
} /* FPVazia */ 
 
 
int Vazia(const TipoPilha *Pilha){ 
 return (0 == Pilha->Topo); 
} /* Vazia */ 
 
Operações sobre Pilhas com 
alocação Sequencial 
void Empilha(TipoItem x, TipoPilha *Pilha){ 
 if (MaxTam == Pilha->Topo) 
 printf(“Erro: pilha está cheia\n"); 
 else { 
 Pilha->Item[Pilha->Topo] = x; 
 Pilha->Topo++; 
 } 
} 
Topo x Topo x 
Topo 
Operações sobre Pilhas com 
alocação Sequencial 
int Desempilha(TipoPilha *Pilha, TipoItem *item){ 
 if (Vazia(Pilha)) { 
 printf(“Erro: a pilha está vazia\n"); 
 return 0; 
 } else { 
 Pilha->Topo--; 
 *item = Pilha->Item[Pilha->Topo]; return 1; 
 } 
} 
x 
Topo 
x Topo Topo 
Operações sobre Pilhas com 
alocação Sequencial 
int Tamanho(const TipoPilha *Pilha){ 
 return Pilha->Topo; 
} 
Operações sobre Pilhas com 
alocação Sequencial 
Implementação de Pilhas por meio de 
Apontadores 
• Há uma célula cabeça no topo para facilitar a implementação 
das operações empilha e desempilha quando a pilha está vazia 
 
 
Fundo 
Topo 
TipoPilha 
Prox 
Celula 
Prox 
Item 
Celula 
Cabeça 
typedef int TipoChave; 
typedef struct { 
 TipoChave Chave; 
 /* --- outros componentes --- */ 
} TipoItem; 
 
typedef struct Celula_str *Apontador; 
 
typedef struct Celula_str { 
 TipoItem Item; 
 Apontador Prox; 
} Celula; 
 
typedef struct { 
 Apontador Fundo, Topo; 
 int Tamanho; 
} TipoPilha; 
. 
TAD de Pilha Usando Apontadores 
24/09/2015 
3 
void FPVazia(TipoPilha *Pilha) { 
 Pilha->Topo = (Apontador) malloc(sizeof(Celula)); 
 Pilha->Fundo = Pilha->Topo; 
 Pilha->Topo->Prox = NULL; 
 Pilha->Tamanho = 0; 
} /* FPVazia */ 
Prox . 
TAD de Pilha Usando Apontadores 
Fundo 
Topo 
NULL 
int Vazia(const TipoPilha *Pilha){ 
 return (Pilha->Topo == Pilha->Fundo); 
} /* Vazia */ 
 
TAD de Pilha Usando Apontadores 
Implementação de Pilhas por meio de 
Apontadores 
• Desempilha: desliga a célula cabeça da lista. 
A próxima célula, que contém o primeiro 
item, passa a ser a célula cabeça. 
 
• Empilha: Cria uma nova célula cabeça e 
adiciona o item a ser empilhado na antiga 
célula cabeça. 
 
void Empilha(TipoItem x, TipoPilha *Pilha) { 
 Apontador Aux; 
 Aux = (Apontador) malloc(sizeof(Celula)); 
 Pilha->Topo->Item = x; 
 Aux->Prox = Pilha->Topo; 
 Pilha->Topo = Aux; 
 Pilha->Tamanho++; 
} 
Aux 
TAD de Pilha Usando Apontadores 
Fundo 
Topo 
NULL 
Prox 
Prox X 
Operações sobre Pilhas Usando 
Apontadores 
int Desempilha(TipoPilha *Pilha, TipoItem *item) { 
 Apontador q; 
 if (Vazia(Pilha)) { 
 printf(“Erro: pilha vazia\n"); return 0; 
 } 
 q = Pilha->Topo; 
 Pilha->Topo = q->Prox; 
 free(q); 
 Pilha->Tamanho--; 
 *item = Topo->Item; return 1; 
} 
Q 
Fundo 
Topo 
NULL 
Prox 
Prox 
X 
 Inverter a string “Exemplo” usando uma pilha. 
1. Empilha cada caractere em uma pilha vazia 
2. Desempilha todos elementos 
 
a 
E 
E X 
E X E 
E X E M 
E X E M P 
E X E M P L 
E X E M P L O 
E X E M P L O 
E X E M P L 
E X E M P 
E X E M 
E X E 
E X 
E 
Exemplos: Inversão de strings 
24/09/2015 
4 
 Infixada: (5 * (((9+8) * (4*6)) + 7)) 
 Pós-fixada: 5 9 8 + 4 6 * * 7 + * (tão logo encontre um 
operador, efetua a operação) 
 Utilizar uma pilha para converter