Buscar

Pesquisa&Ordenação

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 59 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 6, do total de 59 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 9, do total de 59 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Prévia do material em texto

UNIVERSIDADE NOVE DE JULHO - UNINOVE
Pesquisa e Ordenação
Material disponível para download em: www.profvaniacristina.com
Introdução
1
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Estruturas de Dados
• EMENTA: Recursividade, Quick sort; Divisão e Conquista, Guloso, Backtracking; 
Complexidade; Alocação dinâmica de memória: Listas encadeadas; Árvores..
• OBJETIVOS: Aprofundar os conhecimentos em estruturas de dados no sentido de uma sólida 
formação que os capacitem a construir aplicativos de propósito geral. Levá-los a conhecer os 
fundamentos teóricos da estrutura de dados e como estes fundamentos implicam na definição 
de um sistema.
• METODOLOGIA DE ENSINO: Nas aulas teóricas os conceitos serão expostos por meio de 
utilização de lousa, retroprojetor, datashow, sendo disponibilizado para os alunos o material de 
apoio utilizado. Serão propostas atividades individuais ou em grupo para melhor fixação dos 
conceitos. As aulas práticas serão no laboratório de informática utilizando como ferramenta de 
apoio a linguagem de programação C. Todas as aulas práticas serão duas das quatro aulas no 
período.
• SISTEMA DE AVALIAÇÃO: O critério de avaliação deverá ser composto por 03 notas oficiais 
(AV1, AV2 e AV3), oriundas de instrumentos diversificados de avaliação. Para a composição da 
média serão consideradas as duas maiores notas obtidas entre a AV1, AV2 e AV3, sendo que 
as duas maiores notas serão somadas e divididas por 2, considerando-se aprovado o aluno 
que obtiver média final maior ou igual a 6,0 (seis).
2
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Bibliografia
• BIBLIOGRAFIA BÁSICA: 
• PEREIRA, Silvio do Lago; Estruturas de Dados Fundamentais – Conceitos e Aplicações. 4ª 
ed. São Paulo, Érica, 2000, 264 p.
• ASCENCIO, Ana Fernanda Gomes. Lógica de programação com Pascal. Ed. Makron Books, 
1999, 355 p.
• VILLAS, Marcos Viana. Estruturas de Dados: Conceitos e Técnicas de Implementação. Ed. 
Campus, 1993.
• Schildt, Herbert. C Completo e Total. São Paulo : Pearson : Makron Books, 2006, c1997
• Aho, Alfred V. The design and analysis of computer algorithms Massachussets, 
EUA : Addison- Wesley, c1974.
• BIBLIOGRAFIA COMPLEMENTAR:
• Pereira, Vania C.S. Algorítmos e lógica de programação: 100 exercícios resolvidos em 
pseudocódigo e linguagem C Isbn: 978-85-912397-0-2. São Paulo, 2011
• ZIVIANI, Nivio. Projeto de algoritmos com implementação em Pascal e C. Ed. Thomson, 
2000.
• BUCKNALL, Julian. Algoritmos e Estruturas de dados com Delphi. Ed. Berkeley, 2002
3
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
UNIVERSIDADE NOVE DE JULHO - UNINOVE
Pesquisa e Ordenação
Material disponível para download em: www.profvaniacristina.com
Revisão de Pilhas
4
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Pilhas
• Uma pilha é uma lista linear em que apenas as operações de acesso, inserção e remoção são 
possíveis. 
• Todas estas operações deve ser realizadas num mesmo extremo denominado topo.
• Devido às características das operações da pilha, o último elemento a ser inserido será o 
primeiro a ser retirado. 
• Estruturas desse tipo são conhecidas como "LIFO" (last in, first out).
• Exemplo:
• Em uma rua sem saída, tão estreita que apenas um carro passa por vez, o primeiro carro a 
sair será o último a ter entrado. Observe ainda que não podemos retirar qualquer carro e não 
podemos inserir um carro de tal forma que ele não seja o último. 
5
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Operações com Pilhas
• Operações básicas
• Seja P uma variável do tipo pilha e X um elemento qualquer
• push(p, x) - Procedimento que insere X no topo de P. (Empilha)
• pop(p) - Função que remove o elemento do topo da pilha P devolvendo o valor do topo 
para a rotina que a chamou. (Desempilha)
• top(p) - Função que retorna uma cópia do elemento do topo de P, devolvendo o valor do 
topo da pilha P para a rotina que a chamou. (Copia)
• Operações auxiliares
• init(p) – Procedimento que esvazia a Pilha P. (Inicia / Esvazia)
• isfull(p) – Função que retorna um valor lógico informando se a pilha está cheia. Verdadeiro 
se estiver cheia ou Falso caso contrário. (Pilha cheia)
• isempty(p) – Função que retorna um valor lógico informando se a pilha está vazia. 
Verdadeiro se estiver vazia ou Falso caso contrário. (Pilha vazia)
6
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Exemplo de uso de pilhas
Dado um número inteiro, 
positivo em base decimal, 
convertê-lo para binário.
13 (decimal) = 1101 (binário)
7
13 2
1 6 2
0 3 2
1 1 2
1 0
# include <stdio.h>
# include <stdlib.h>
# include "pilhas.h"
int main() {
int n, r;
tpPilha p;
printf("Digite um inteiro positivo: ");
scanf("%d", &n);
init ( &p );
do {
r = n % 2;
push ( &p, r );
n = n/2;
} while (n != 0);
printf("\n\nCorrespondente ao Binario => ");
while ( isEmpty ( &p ) == 0) {
r = pop ( &p );
printf("%d", r);
}
printf("\n\n\n");
system("pause");
return 0;
}
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Pilhas no Controle de Variáveis e Sub-Rotinas
1 # include <stdio.h>
2 void A( ) {
3 int A1, A2;
4 ...
5 }
6 void B ( ) {
7 float B1, B2;
8 ...
9 A ( );
10 ...
11 }
12 int main( ) {
13 int P1, P2;
14 A ( );
15 ...
16 B( );
17 ...
18 }
8
Pilha 1 Pilha 2
UNIVERSIDADE NOVE DE JULHO - UNINOVE
Pesquisa e Ordenação
Material disponível para download em: www.profvaniacristina.com
Revisão de Ponteiros
9
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Alocação de Memória
• Da área de memória que é reservada ao programa, uma parte é usada para armazenar as 
instruções a serem executadas e a outra é destina ao armazenamento de dados. 
• Quem determina quanto de memória será usado para as instruções é o compilador. 
• Alocar área para armazenamento de dados, entretanto, é responsabilidade do programador.
• Quando a quantidade de memória utilizada pelos dados é previamente conhecida e definida no 
próprio código-fonte do programa, trata-se de alocação estática.
• Quando o programa é capaz de criar novas variáveis durante sua execução, dizemos que a 
alocação é dinâmica.
10
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Ponteiros
• PONTEIRO é ...
• uma variável especial que contém o endereço de memória de outra variável.
• variável que contém endereços de posições de memória alocadas na memória.
11
VARIÁVEL 
PONTEIRO
endereço de memória 
de outra variável
ptr
1FFA
VARIÁVEL 
DINÂMICA
conteúdo do tipo que 
se deseja “acessar”
<sem nome> 
(endereço 1FFA)
5
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Ponteiros – Comandos básicos
< tipo de dado > *< identificador > ;
• Declara uma variável do tipo ponteiro.
• Pode haver um ponteiro (ou apontador) para qualquer tipo de variável.
(void*) malloc(tamanho em bytes);
• Aloca dinamicamente, durante a execução do programa, células de memória.
• Esta função devolve um ponteiro void que deveser ser convertido para o tipo desejado.
• O tamanho em bytes pode ser determinado utilizando a função sizeof() que retorna o tamanh
em bytes que um tipo de dados ocupa. Exemplo:
int *ptr;
ptr = ( int * ) malloc ( sizeof ( int ) ) ;
free (ponteiro)
• Libera as células de memória alocadas dinamicamente. 
• Exemplo free ( ptr );
• Para manipulação de valores utilizando ponteiros temos dois operadores:
• O operador * devolve o valor contido no endereço apontado pela variável ponteiro;
• O operador & devolve o endereço de memória alocado de uma variável.
12
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Estruturas de Dados – TADS
Exemplo 13
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
# include < stdio.h >
# include < stdlib.h >
int main ( ) {
int *x, *y;
int a, b;
a = 27;
b = 43;
x = &a;
y = &b;
printf ( "*x = %d x = %d \n", *x, x ) ;
printf ( "*y = %d y = %d \n\n", *y, y ) ;
*x = *y ;
printf ( "*x = %d x = %d \n", *x, x ) ;
printf ( "*y = %d y = %d \n\n", *y, y ) ;
*x = 27;
y = x ;
printf ( "*x = %d x = %d \n", *x, x ) ;
printf ( "*y = %d y = %d \n\n", *y, y ) ;
system ( "pause" ) ;
return 0 ;
}
Declaração das variáveis ponteiro
Recebe o endereço de memória da variável a. Ex.: 4A9B
Recebe o endereço de memória da variável b. Ex.: 4AAB
atribui a informação que está no
endereço 4AAB para o endereço 4A9B
a variável y está apontada para o endereço de x 4A9B
UNIVERSIDADE NOVE DE JULHO - UNINOVE
Pesquisa e Ordenação
Material disponível para download em: www.profvaniacristina.com
Revisão de Arquivos
14
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Arquivos
• Um arquivo é semelhante a um vetor, exceto por alguns motivos: 
• o vetor fica armazenado na memória RAM; o arquivo fica armazenado em disco; 
• o vetor deve ter um tamanho fixo, definido em sua declaração; o tamanho do arquivo pode 
variar durante a execução do programa.
• Os vetores são manipulados através de um índice de controle, enquanto os arquivos são 
manipulados por um ponteiro de registro. 
• As estruturas de dados tipo arquivo são apropriadas para organizar:
• grande quantidade de dados
• informações processadas por diversas aplicações
• informações que requisitam armazenamento permanente
• Vantagens e desvantagens no uso de arquivos
• Vantagem: 
• Os dados não são perdidos entre uma execução e outra do programa. 
• Desvantagem: 
• O acesso a disco é muito mais lento do que o acesso à memória. 
15
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Arquivos
• Tipos de arquivo
• Tipo Texto 
• Estão capacitados a armazenar palavras, frases e também dados numéricos. Os números, 
entretanto, serão armazenados como um caractere do tipo alfanumérico. Ao serem lidos de 
um arquivo e passados para a memória, os dados numéricos são convertidos para o seu 
formato original. 
• Tipo Binário
• usa o sistema binário para armazenar tanto as informações numéricas, quanto as 
informações literais, através do código ASCII, compostos por uma sequencia de bytes.
• Arquivos textos são legíveis devido a forma que os dados foram gravados, mas consumem 
mais espaço para armazenamento e para acessar uma informação é necessário percorrer 
sequencialmente o arquivo tornando a busca lenta.
• Arquivos binários não são legíveis uma vez que os dados são gravados do mesmo modo que 
estão na memória e consomem menos espaço de memória para o armazenamento. O 
acesso a uma informação em um arquivo binário é pode ser direto tornando a busca mais 
rápida.
16
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Tabela com modos de abertura de arquivos 17
Modo Significado
"r" Abre um arquivo texto para leitura. O arquivo deve existir antes de ser aberto.
"w"
Abrir um arquivo texto para gravação. Se o arquivo não existir, ele será criado. Se já existir, o 
conteúdo anterior será destruído.
"a"
Abrir um arquivo texto para gravação. Os dados serão adicionados no fim do arquivo 
("append"), se ele já existir, ou um novo arquivo será criado, no caso de arquivo não existente 
anteriormente.
"rb" Abre um arquivo binário para leitura. Igual ao modo "r" anterior, só que o arquivo é binário.
"wb" Cria um arquivo binário para escrita, como no modo "w" anterior, só que o arquivo é binário.
"ab" Acrescenta dados binários no fim do arquivo, como no modo "a" anterior, só que o arquivo é binário.
"r+" Abre um arquivo texto para leitura e gravação. O arquivo deve existir e pode ser modificado.
"w+"
Cria um arquivo texto para leitura e gravação. Se o arquivo existir, o conteúdo anterior será 
destruído. Se não existir, será criado.
"a+"
Abre um arquivo texto para gravação e leitura. Os dados serão adicionados no fim do arquivo 
se ele já existir, ou um novo arquivo será criado, no caso de arquivo não existente 
anteriormente.
"r+b" Abre um arquivo binário para leitura e escrita. O mesmo que "r+" acima, só que o arquivo é binário.
"w+b" Cria um arquivo binário para leitura e escrita. O mesmo que "w+" acima, só que o arquivo é binário.
"a+b" Acrescenta dados ou cria uma arquivo binário para leitura e escrita. O mesmo que "a+" acima, 
só que o arquivo é binário
Exemplo de manipulação de Arquivo Binário
# include < stdio.h >
# include < stdlib.h >
# include < string.h >
typedef struct {
char nome [ 51 ] ;
char ra [ 11 ] ;
float nota ;
int falta ;
} tpLista ;
18
int main ( ) {
tpLista regChamada;
FILE *arqChamada;
arqChamada = fopen("alunos.dat", "a+b");
if (arqChamada == NULL)
arqChamada = fopen("alunos.dat", "w+b");
if (arqChamada == NULL) {
printf ( "\nO arquivo não pode ser criado!\n\n" ) ;
system ( "pause" ) ;
exit ( 1 ) ;
}
FILE tipo de dado para uma variável ponteiro para um arquivo
fopen função para abrir um arquivo deve receber os parâmetros nome do arquivo e o 
modo de abertura
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Exemplo de manipulação de Arquivo Binário
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
do {
system ( "cls" ) ;
printf ( "Para encerrar digite '.' no campo Nome\n\n" ) ;
printf ( "Nome.... : " ) ;
fflush ( stdin ) ;
gets ( regChamada.nome ) ;
if ( strcmp ( regChamada.nome, "." ) != 0 ) {
printf ( "Ra...... : " ) ;
fflush ( stdin ) ;
gets ( regChamada.ra ) ;
printf ( "Nota.... : " ) ;
scanf ( "%f", &regChamada.nota ) ;
printf ( "Faltas.. : " ) ;
scanf ( "%d", &regChamada.falta ) ;
if ( fwrite ( &regChamada, sizeof ( tpLista ), 1, arqChamada ) == NULL )
break;
}
} while ( strcmp ( regChamada.nome, "." ) != 0 ) ;
19
fwrite
- Função que grava os dados em um arquivo do tipo binário.
- Deve receber quatro parâmetros:
- variável que contém os dados a serem gravados;
- número de bytes dos dados a serem gravados;
- número de vezes que a gravação será executada; e
- nome do arquivo onde os dados serão gravados.
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Exemplo de manipulação de Arquivo Binário
system ( "cls" ) ;
rewind ( arqChamada ) ;
while ( 1 ) {
fread ( &regChamada, sizeof ( tpLista ), 1, arqChamada ) ;
if ( feof ( arqChamada ) ) break ;
printf ( "Ra....: %s\n", regChamada.ra ) ;
printf ( "Nome..: %s\n", regChamada.nome ) ;
printf ( "Nota..: %.1f\n", regChamada.nota ) ; 
printf ( "Faltas: %d\n\n", regChamada.falta) ;
}
fclose ( arqChamada ) ;
system ( "pause" ) ;
return 0 ;
}
20
rewind recoloca o leitor de posição no início do arquivo.
fread lê os dados de um arquivo do tipo binário. Deve receber 4 parâmetros:
- variável que receberá os dados lidos;
- número de bytes dos dados que serão lidos;
- número de vezes que a leitura será executada; e
- nome do arquivo onde os dados estão gravados.
feof informa se o final do arquivo foi atingido ou não, retornando 0 ou 1 para F ou V
fclose fecha um arquivo aberto com a função fopen
Exemplo de manipulação de Arquivo Texto
#include < stdio.h >
#include < conio.h >
#include < stdlib.h >
#include < string.h >
int main ( ) {
FILE *arq ;
char nome [ 30 ] ;
int idade, cont = 0 ;
float altura ;
arq = fopen ( "dados.txt", "w" ) ;
if ( arq == NULL ) {
printf ( "\nErro na criação do arquivo dados.txt" ) ;
getch ( ) ;
exit ( 1 ) ;
}
21
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Exemplo de manipulação de Arquivo Texto
for ( ; ; ) { 
system ( "cls" ) ;
printf ( "Nome (. para finalizar): " ) ;
fflush ( stdin ) ;
gets ( nome ) ;
if ( strcmp ( nome, "." ) == 0 )
break ;
printf ( "Idade: " ) ;
scanf ( "%i", &idade ) ;
printf ( "Altura: “ ) ;
scanf ( "%f", &altura ) ;
fprintf ( arq, "%s %i %.2f \n", nome, idade, altura ) ;
}
fclose ( arq ) ;
22
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Exemplo de manipulação de Arquivo Texto
printf ( "\nAbertura e leitura do arquivo gravado\n" ) ;
arq = fopen ( "dados.txt", "r" ) ;
if ( arq == NULL ) {
printf ( "\nErro na abertura do arquivo dados.dat" ) ;
getch ( ) ;
exit ( 1 ) ;
}
while ( !feof ( arq ) ) {
fscanf ( arq, "%s %i %f \n", nome, &idade, &altura ) ;
printf ( "\n Nome = %s Idade = %i Altura = %.2f", nome, idade, altura ) ;
++cont ;
}
fclose ( arq ) ;
printf ( "\n\nArquivo com %d registros. Fechando o arquivo.\n", cont ) ;
getch ( ) ;
return 0 ;
}
23
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
UNIVERSIDADE NOVE DE JULHO - UNINOVE
Pesquisa e Ordenação
Material disponível para download em: www.profvaniacristina.com
Recursão
24
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Recursão
• Trata-se de uma subrotina que chama a si mesma, porém, como todo algoritmo deve ser finito, 
isto é, deve terminar após ter executado uma quantidade finita de passos.
• Exemplos:
• Ler um livro:
• (a) Ler uma página
• (b) Ler uma página e Ler o resto do livro.
• Examinar lista:
• (a) Examinar um elemento
• (b) Examinar um elemento e Examinar lista restante. Uma Imagem Recursiva
25
Uma imagem recursiva
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Recursão
• Para garantir que uma chamada recursiva não criará um “looping” que será executado 
infinitamente, é necessário que ela esteja condicionada a uma expressão lógica que, em algum 
instante, torna-se-á falsa e permitirá que a recursão termine.
26
# include <stdio.h>
# include <stdlib.h>
int main ( ) {
int num, fat;
fat = 1;
printf ( "Digite um numero => " ) ;
scanf ( "%d", &num ) ;
while ( num > 0 ) {
fat = fat * num;
num - - ;
}
printf ( "\n\nFatorial = %d.\n\n", fat );
system ( "pause" ) ;
return 0 ;
}
# include <stdio.h>
# include <stdlib.h>
int fat ( int n ) {
if ( n == 0 )
return 1;
else
return ( n * fat ( n-1 ) ) ;
}
int main ( ) {
int num;
printf ( "Digite um numero => " ) ;
scanf ( "%d", &num ) ;
printf ( "\n\nFatorial = %d.\n\n", fat ( num ) );
system ( "pause“ ) ;
return 0;
}
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
• Invocações geradas e valores retornados para o cálculo de fat ( 5 ) .
Fatorial é o produto dos
números naturais desde 1 até
o inteiro N. Por definição 0! = 1.
Exemplo : 5! = 
5 * 4 * 3 * 2 * 1 ⇒ 5! = 120.
5! = 5 * 4!
4! = 4 * 3!
3! = 3 * 2!
2! = 2 * 1!
1! = 1 * 0!
int fat ( int n ) {
if ( n == 0 )
return 1;
else
return ( n * fat ( n-1 ) ) ;
}
Recursão 27
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Fat (5)⇒ 5 * fat (4)⇒ 5 * 24 ⇒ 120
Fat (4)⇒ 4 * fat (3)⇒ 4 * 6 ⇒ 24
Fat (3)⇒ 3 * fat (2)⇒ 3 * 2 ⇒ 6
Fat (2)⇒ 2 * fat (1)⇒ 2 * 1 ⇒ 2
Fat (1)⇒ 1 * fat (0)⇒ 1 * 1 ⇒ 1
Fat (0)⇒ 1
Quando aplicar recursão?
• É preciso analisar o problema e verificar se realmente vale a pena encontrar uma solução 
recursiva.
• A decisão de usá-la ou não deverá ser tomada após a comparação das possíveis soluções 
recursiva e iterativa.
• Se bem utilizada, pode tornar o algoritmo claro, simples e conciso.
• Embora a recursão seja uma ferramenta bastante interessante para resolução de problemas, 
nem sempre ela poderá ser empregada , pois a solução mais eficiente é através do modo 
iterativo.
28
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Exemplo de uso de recursão - MDC
• MDC – Máximo Divisor Comum
• O primeiro tem que ser maior que o segundo;
• Dividir o primeiro pelo segundo;
• O segundo passa a ser o primeiro e o segundo será o resto da divisão;
• Quando o segundo for igual a zero o primeiro será o MDC.
29
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
# include <stdio.h>
# include <stdlib.h>
int mdc ( int p, int s );
int main ( ) {
int x, y ;
printf ( "Digite o 1o. numero => " ) ;
scanf ( "%d", &x ) ;
printf ( "\nDigite o 2o. numero => “ ) ;
scanf ( "%d", &y ) ;
printf ( "\n\nMDC = %d\n\n", mdc ( x, y ) ) ;
system ( "pause" ) ;
return 0;
}
int mdc ( int p, int s ) {
if ( s > p )
return ( mdc ( s, p ) );
else
if ( s == 0 )
return ( p );
else
return ( mdc ( s, p % s ) );
}
Exercícios: Recursão - 1 30
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
1) Escrever uma função recursiva chamada Potencia que receberá os parâmetros X e Y 
(argumentos inteiros e positivos), retornando o resultado, usando a seguinte definição:
Potencia retorna X, se Y=1 ou Potencia retorna X * Potencia(X,Y-1).
2) Qual será o valor impresso após a execução do programa abaixo?
# include <stdio.h>
# include <stdlib.h>
int f_rec ( int x, int y ) {
if (x == 0) return ( y );
else return ( f_rec ( x-1, y+1 ) );
}
int main( ) {
int x, y, k;
x = 7; y = 1;
k = f_rec ( x, y );
printf("Resultado => %d\n\n", k);
system("pause"); return 0;
}
3) Escreva uma função void recursiva que receba um número inteiro positivo n, e exiba na tela os 
números inteiros entre n e 0, inclusive. Exemplo n = 5 será exibido 5 4 3 2 1 0
Exercícios: Recursão - 2
4) Considerando a função a seguir, a chamada p(5) causa:
void p ( int n ) {
if ( n != 0 ) {
p ( n – 2 ) ;
printf("%d", n ) ;
}
} 
a) Apenas a exibição dos números 1, 3 e 5 nessa ordem
b) A exibição dos números 1, 3 e 5 nessa ordem, seguido de erro de estouro de pilha
c) Apenas a exibição dos números 5, 3 e 1 nessa ordem
d) A exibição dos números 5, 3 e 1 nessa ordem, seguido de erro de estouro de pilha
e) Apenas erro de estouro de pilha
5) Faça uma função recursiva para achar um elemento num vetor. A função deve retornar o índice 
do elemento no vetor ou -1 caso ele não exista. 
31
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Exercícios: Recursão - 3
6) Qual será o valor impresso após a execução 
do programa ao lado?
# include<stdio.h>
# include <stdlib.h>
int x = 0, a;
int rec ( int n, int i );
int main( ) {
a = rec (5,2);
printf("Resultado = %d\n\n",a);
system("pause");
return 0;
}
int rec ( int n, int i ) {
if ( i > 9 )
return ( x );
else {
x = n + i ;
return ( rec ( n , i + 1 ) );
}
}
32
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Exercícios: Recursão - 4 33
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
7) O que será impresso após a execução do programa abaixo, sabendo que x = “arara” ?
# include <stdio.h>
# include <stdlib.h>
# include <string.h>
int pal(char a[6], int ini, int fim);
int main( ) {
char x[6];
int i, f, result;
gets(x);
i = 0;
f = strlen(x)-1;
result = pal(x, i, f);
if (result)
printf("Verdadeiro\n\n");
else
printf("Falso\n\n");
system("pause");
return 0;
}
int pal(char a[6], int ini, int fim) {
if (a[ini] == a[fim])
if (ini == fim)
return 1;
else
return pal(a, ++ini, --fim);
else
return 0;
}
UNIVERSIDADE NOVE DE JULHO - UNINOVE
Pesquisa e Ordenação
Material disponível para download em: www.profvaniacristina.com
Quick Sort
34
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Quick Sort
• É um método dos mais utilizados para ordenação de valores e de forma geral um dos mais 
eficientes.
• Trata de um método de ordenação baseado no conceito da Divisão e Conquista e também em 
trocas (como na ordenação “bubble sort”).
• Para a ordenação dos dados primeiramente o vetor deve ser dividido em tres partes onde:
• Uma parte deve conter apenas um elemento identificado como pivô.
• Uma parte deve conter todos os elementos com valores menores ou iguais ao pivo. Todos
estes valores devem estar antes do índice que contém o valor do pivô.
• Uma parte deve conter todos os elementos com valores maiores ao pivô. Todos estes
valores devem estar depois do índice que contém o valor do pivô.
• Atendidos os requisitos acima aplica-se recursivamente a técnica em cada um dos 
subvetores, enquanto a quantidade de elementos for maior ou igual a dois.
35
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Quick Sort
• Escolha do pivô pode feita aleatóriamente ou o elemento do meio do vetor.
• A partir da escolha do pivô inicia-se as comparações entre os valores da seguinte forma:
• Comparar v[0], v[1], ... até encontrar um elemento v[a] > pivô;
• Comparar, a partir do final do vetor, os elementos v[n-1],v[n-2], ... Até encontrar v[b]<=pivô.
• Uma vez encontrados os valores trocar v[a] com v[b]
• Retomar a busca, para cima a partir de v[a+1], e para baixo, a partir de v[b-1];
• Terminar o processo de busca, quando os valores de a e b se inverterem, sendo que o valor do 
pivô estará em sua posição correta em relação aos valores da vetor conforme as regras 
descritas no slide anterior.
36
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Quick Sort 37
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
void quick(int v[MAX], int inicio, int fim) {
int baixo, alto, meio, pivo, k;
baixo = inicio;
alto = fim;
meio = (int) ((baixo + alto) / 2);
pivo = v[meio];
while (baixo <= alto) {
while (v[baixo] < pivo)
baixo++;
while (v[alto] > pivo)
alto--;
if (baixo < alto) {
k = v[baixo];
v[baixo++] = v[alto];
v[alto--] = k;
} 
else
if ( baixo == alto ) {
baixo++;
alto--;
}
}
if(alto > inicio) 
quick(v, inicio, alto);
if(baixo < fim) 
quick(v, baixo, fim);
}
Quick Sort 38
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
baixo alto meio v[0] v[1] v[2] v[3] v[4] v[5] v[6] v[7] v[8] v[9]
0 8 4 41 21 93 95 31 43 45 13 11 85 41 > 31 e 11 < 31, então trocar 41 e 11
2 7 4 11 21 93 95 31 43 45 13 41 85 93 > 31 e 13 < 31, então trocar 93 e 13
3 4 4 11 21 13 95 31 43 45 93 41 85 95 > 31 e 31 = 31, então trocar 95 e 31
1 2 1 11 21 13 31 95 43 45 93 41 85 21 = 21 e 13 < 21, então trocar 21 e 13
0 1 0 11 13 21 31 95 43 45 93 41 85
4 9 6 11 13 21 31 95 43 45 93 41 85 95 > 45 e 41 < 45, então trocar 95 e 41
4 5 4 11 13 21 31 41 43 45 93 95 85
7 9 8 11 13 21 31 41 43 45 93 95 85 95 = 95 e 85 < 95, então trocar 95 e 85
7 8 7 11 13 21 31 41 43 45 93 85 95 95 = 93 e 85 < 93, então trocar 93 e 85
7 8 7 11 13 21 31 41 43 45 85 93 95
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
# include <stdio.h>
# include <stdlib.h>
# define MAX 8
void quick ( int v [ MAX ], int inicio, int fim );
int main ( ) {
int vetor [ MAX ] = { 12, 1, 56, 16, 8, 19, 23, 49 };
int i;
printf ( "Vetor Desordenado:\n" );
for ( i = 0; i < MAX; i++ )
printf ( "%d ", vetor [ i ] );
printf ( "\n\n" );
quick ( vetor, 0, MAX – 1 );
printf ( "\n\nVetor Ordenado:\n" );
for ( i = 0; i < MAX; i++ )
printf ( "%d ", vetor [ i ] );
printf ( "\n\n" );
system ( "pause" );
return 0;
} 
void quick ( int v [ MAX ], int inicio, int fim ) {
int baixo, alto, meio, pivo, k;
baixo = inicio;
alto = fim;
meio = ( int ) ( ( baixo + alto ) / 2 );
pivo = v [ meio ];
while ( baixo <= alto ) {
while ( v [ baixo ] < pivo )
baixo ++;
while ( v [ alto ] > pivo )
alto --;
if ( baixo <= alto ) {
k = v [ baixo ];
v [ baixo ++ ] = v [ alto ];
v [ alto -- ] = k;
}
else
if ( baixo == alto ) {
baixo ++;
alto --;
}
}
if ( alto > inicio )
quick ( v, inicio, alto );
if ( baixo < fim )
quick ( v, baixo, fim );
}
Exemplo 1 39
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
# include <stdio.h>
# include <stdlib.h>
# include <string.h>
# define MAX 8
void quick ( char v[MAX][15], int inicio, int fim );
int main( ){
char vetor[ MAX ] [ 15 ] = {"Lucas", "Mariano", 
"Alberto", "Douglas", "Leonardo", "Mateus", "Flavio", 
"Luiz"};
int i;
printf ( "Vetor Desordenado:\n" );
for ( i = 0; i < MAX; i++ )
printf ( "%s\n", vetor [ i ] );
printf ( "\n\n" );
system ( "pause" );
quick ( vetor, 0, MAX-1 );
system ( "cls" );
printf ( "Vetor Ordenado:\n" );
for ( i = 0; i < MAX; i++ )
printf ( "%s\n", vetor[i] );
printf ( "\n\n" );
system ( "pause" );
return 0;
}
void quick ( char v [ MAX ] [ 15 ], int inicio, int fim ){
int baixo, alto, meio;
char k [ 15 ], pivo [ 15 ];
baixo = inicio;
alto = fim;
meio = ( int ) ( ( baixo + alto ) / 2 );
strcpy ( pivo, v [ meio ] );
while ( baixo <= alto ) {
while ( strcmp ( v [ baixo ], pivo ) < 0 )
baixo ++;
while ( strcmp ( v [ alto ], pivo ) > 0 )
alto --;
if ( baixo <= alto ) {
strcpy ( k, v [ baixo ] );
strcpy ( v [ baixo ++ ], v [ alto ] );
strcpy ( v [ alto -- ], k );
}
else
if ( baixo == alto ) {
baixo ++;
alto --;
}
}
if ( alto > inicio )
quick ( v, inicio, alto );
if ( baixo < fim )
quick ( v, baixo, fim );
}
Exemplo 2 40
UNIVERSIDADE NOVE DE JULHO - UNINOVE
Pesquisa e Ordenação
Material disponível para download em: www.profvaniacristina.com
Listas encadeadas
41
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Alocação de Memória
• Antes de abordarmos listas encadeadas vamos relembrar os conceitos de alocação de 
memória e ponteiros.
• Da área de memória que é reservada ao programa, uma parte é usada para armazenar as 
instruções a serem executadas e a outra é destina ao armazenamento de dados. 
• Quem determina quanto de memória será usado para as instruções é o compilador. 
• Alocar área para armazenamento de dados,entretanto, é responsabilidade do programador.
• Quando a quantidade de memória utilizada pelos dados é previamente conhecida e definida no 
próprio código-fonte do programa, trata-se de alocação estática.
• Quando o programa é capaz de criar novas variáveis durante sua execução, dizemos que a 
alocação é dinâmica.
42
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Ponteiros
• PONTEIRO é ...
• uma variável especial que contém o endereço de memória de outra variável.
• variável que contém endereços de posições de memória alocadas na memória.
43
VARIÁVEL 
PONTEIRO
endereço de memória 
de outra variável
ptr
1FFA
VARIÁVEL 
DINÂMICA
conteúdo do tipo que 
se deseja “acessar”
<sem nome> 
(endereço 1FFA)
5
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Ponteiros – Comandos básicos
< tipo de dado > *< identificador > ;
• Declara uma variável do tipo ponteiro.
• Pode haver um ponteiro (ou apontador) para qualquer tipo de variável.
(void*) malloc(tamanho em bytes);
• Aloca dinamicamente, durante a execução do programa, células de memória.
• Esta função devolve um ponteiro void que deve ser ser convertido para o tipo desejado.
• O tamanho em bytes pode ser determinado utilizando a função sizeof() que retorna o tamanh
em bytes que um tipo de dados ocupa. Exemplo:
int *ptr;
ptr = ( int * ) malloc ( sizeof ( int ) ) ;
free (ponteiro)
• Libera as células de memória alocadas dinamicamente. 
• Exemplo free ( ptr );
• Para manipulação de valores utilizando ponteiros temos dois operadores:
• O operador * devolve o valor contido no endereço apontado pela variável ponteiro;
• O operador & devolve o endereço de memória alocado de uma variável.
44
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Exemplo 45
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
# include <stdio.h>
# include <stdlib.h>
# include <string.h>
int main ( ) {
int *x, *y; 
x = ( int * ) malloc ( sizeof ( int ) ) ;
y = ( int * ) malloc ( sizeof ( int ) ) ;
*x = 27 ;
*y = 43 ;
printf ( "Valor: %d - %d \n\n", *x , *y ) ;
*x = *y ;
printf ( "Valor: %d - %d \n\n", *x , *y ) ;
*x = 27 ;
y = x ;
printf ( "Valor: %d - %d \n\n", *x , *y ) ;
free ( x ) ;
system ( "pause" ) ;
return 0 ;
}
# include <stdio.h>
# include <stdlib.h>
int main ( ) {
int * x, * y ;
int a, b ;
a = 27 ;
b = 43 ;
x = &a ;
y = &b ;
printf ( "Valor: %d - %d \n\n", *x , *y ) ;
*x = *y ;
printf ( "Valor: %d - %d \n\n", *x , *y ) ;
*x = 27 ;
y = x ;
printf ( "Valor: %d - %d \n\n", *x , *y ) ;
system ( "pause") ;
return 0 ;
}
Exemplo 46
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
# include <stdio.h>
# include <stdlib.h>
# include <string.h>
int main ( ) {
char *x, *y;
x = ( char * ) malloc ( 12 * sizeof ( char ) ) ;
y = ( char * ) malloc ( 12 * sizeof ( char ) ) ;
strcpy ( x, "Estruturas" ) ;
strcpy ( y, "de Dados" ) ;
printf ( "%s %s\n\n", x, y ) ;
strcpy ( y, x ) ;
printf ( "%s %s\n\n", x, y ) ;
strcpy ( y, "de Dados" ) ;
printf ( "%s %s\n\n", x, y );
x = y ;
printf ( "%s %s\n\n", x, y ) ;
free( x ) ;
system ( "pause" ) ;
return 0 ;
}
Exercícios: Ponteiros - 1
• Codifique um programa que contenha uma variável ponteiro que aponte para um vetor de 5 
elementos do tipo inteiro, insira dados neste vetor e mostre os mesmos.
• Codifique um programa que contenha um vetor de 5 elementos do tipo ponteiro para um char, 
insira dados neste vetor e mostre os mesmos.
47
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Exercícios: Ponteiros - 2
O que será impresso após a execução do 
programa abaixo?
# include <stdio.h>
# include <stdlib.h>
# include <string.h>
int main ( ) {
int *p1, *p2, p3 ;
char *x1, *x2, x3 [ 7 ] ;
p1 = ( int * ) malloc ( sizeof ( int ) ) ;
p2 = ( int * ) malloc ( sizeof ( int ) ) ;
x1 = ( char * ) malloc ( 7 * sizeof ( char ) ) ;
x2 = ( char * ) malloc ( 7 * sizeof ( char ) ) ;
*p1 = 7 ;
strcpy ( x1,"teste" ) ;
*p2 = 15 ;
strcpy ( x2, "aula" ) ;
p3 = 11 ;
strcpy ( x3, "prova" ) ;
p1 = p2 ;
p2 = &p3 ;
strcpy ( x2, x3 ) ;
strcpy ( x1, x3 ) ;
printf ( "%d \n", *p1 ) ;
printf ( "%d \n", *p2 ) ;
printf ( "%d \n", p3 ) ;
printf ( "%s \n", x1 ) ;
printf ( "%s \n", x2 ) ;
printf ( "%s \n", x3 ) ;
system ( "pause" ) ;
return 0 ;
}
48
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Listas Encadeadas
• Por meio de ponteiros podemos alocar espaço para uma informação na memória e liberar este 
mesmo espaço quando não for mais necessário. 
• Quando precisamos guardar várias informações na memória, independente da quantidade, 
podemos utilizar uma estrutura conhecida como Lista Encadeada.
• Uma lista encadeada é uma sequência de informação armazenadas em algum lugar da 
memória, sendo que as mesmas estão ligadas entre si por um endereço (pointer).
• Um lista encadeada é criada a partir da estrutura de um registro (estrutura STRUCT).
49
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Estrutura de uma lista encadeada
• A estrutura mais básica deste registro conterá dois tipos de campos:
• O primeiro tipo serão os campos utilizados para armazenar as informações propriamente 
ditas e 
• O segundo tipo será um campo do tipo ponteiro que irá armazenar o endereço da próxima 
informação existente na memória.
• Para declarar a estrutura de uma lista encadeada devemos criar um tipo struct como por 
exemplo:
struct reg { 
char nome[51];
int idade;
char sexo;
struct reg *proximo;
} tpLista;
50
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Início
proximosexoidadenome proximosexoidadenome proximosexoidadenome
Exemplo de Lista Encadeada – Declarações iniciais 
#include <stdio.h>
#include <stdlib.h>
typedef char tpElem ;
typedef struct registro {
tpElem dado ;
struct registro *prox ;
} tpLista ;
void insere ( tpLista *noatual, tpElem x ) ;
void mostra ( tpLista *noatual ) ;
tpLista* procura(tpLista *noatual, tpElem x) ;
int retira ( tpLista *noatual, tpElem x ) ;
void esvazia( tpLista *noatual ) ;
tpLista *lista = NULL ;
51
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Exemplo de Lista Encadeada – função main( ) 
int main( ) {
tpElem valor ;
insere( lista, 'b' ) ;
insere( lista, 'd' ) ;
insere( lista, 'c' ) ;
insere( lista, 'a' ) ;
mostra( lista ) ;
printf( "\n\nDado a ser procurado: " ) ;
scanf( "%c", &valor ) ;
if ( procura ( lista , valor ) == NULL )
printf( " Nao achou...\n\n" ) ;
else
printf( " Achou...\n\n" ) ;
fflush( stdin ) ;
printf( "Dado a ser retirado: " ) ;
scanf( "%c", &valor ) ;
if ( retira ( lista , valor ) == 0 )
printf( " Nao encontrado...\n\n\n" ) ;
else
printf( " Valor retirado...\n\n\n" ) ;
mostra( lista ) ;
esvazia( lista ) ;
printf( "\n\n\n" ) ;
system( "pause" ) ;
return 0 ;
}
52
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Exemplo de Lista Encadeada – função insere( ) 
void insere ( tpLista *noatual, tpElem x ){
tpLista *novono ;
if ( noatual == NULL ) {
lista=( tpLista * ) malloc( sizeof( tpLista ));
lista->dado = x ;
lista->prox = NULL ;
}
else {
while( noatual->prox != NULL )
noatual = noatual->prox ;
novono=(tpLista *) malloc(sizeof(tpLista));novono->dado = x ;
novono->prox = NULL ;
noatual->prox = novono ;
}
}
53
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Exemplo de Lista Encadeada – função mostra( ) 
void mostra ( tpLista *noatual ) {
printf( "Valores atuais na lista => " ) ;
while( noatual != NULL ) {
printf( "%c ",noatual->dado ) ;
noatual = noatual->prox ;
}
}
54
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Exemplo de Lista Encadeada – função procura( ) 
tpLista* procura(tpLista *noatual, tpElem x) {
while ( noatual != NULL ) {
if ( x == noatual->dado )
return noatual ;
else
noatual = noatual->prox ;
}
return NULL ;
}
55
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Exemplo de Lista Encadeada – função retira( ) 
int retira ( tpLista *noatual, tpElem x ) {
tpLista *libera ;
if ( noatual == NULL )
return 0 ;
else
if ( x == noatual->dado ) {
libera = noatual ;
lista = noatual->prox ;
free( libera ) ;
return 1 ;
}
else {
while ( noatual->prox != NULL ){
if ( x == noatual->prox->dado ) {
libera = noatual->prox ;
noatual->prox = libera->prox ;
free( libera ) ;
return 1 ;
}
else
noatual = noatual->prox ;
}
}
return 0 ;
}
56
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Exemplo de Lista Encadeada – função esvazia( ) 
void esvazia( tpLista *noatual ) {
while ( noatual != NULL ) {
lista = noatual->prox ;
free( noatual ) ;
noatual = lista ;
}
}
57
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
inicio
anterior nome idade sexo proximo anterior nome idade sexo proximo anterior nome idade sexo proximo
Lista duplamente encadeada
• A lista duplamente encadeada, é baseada em um registro (struct) contendo dois campos do tipo 
ponteiro e os campos que armazenarão os dados.
• Cada nó da lista deve estar ligado a seu antecessor e a seu sucessor, ou seja, cada nó tem um 
ponteiro para o nó anterior e um ponteiro para o próximo nó.
• Assim é possível percorrer a lista do início ao fim e vice-versa.
58
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Lista Duplamente Encadeada – Declarações iniciais 
typedef char tpElem ;
typedef struct registro {
tpElem dado ;
struct registro *ant ;
struct registro *prox ;
} tpLista ;
void insere ( tpLista *noatual, tpElem x ) ;
void mostra ( tpLista *noatual ) ;
tpLista* procura(tpLista *noatual, tpElem x) ;
int retira ( tpLista *noatual, tpElem x ) ;
void esvazia( tpLista *noatual ) ;
tpLista *lista = NULL ;
59
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Lista Duplamente Encadeada – função main() 
int main( ) {
tpElem valor, resposta ;
insere( lista, 'a' ) ;
insere( lista, 'b' ) ;
insere( lista, 'c' ) ;
insere( lista, 'd' ) ;
insere( lista, 'e' ) ;
insere( lista, 'f' ) ;
insere( lista, 'g' ) ;
insere( lista, 'h' ) ;
mostra( lista ) ;
printf( "\n\nDado a ser procurado: " ) ;
fflush(stdin);
scanf( "%c", &valor ) ;
if ( procura ( lista , valor ) == NULL )
printf( "* * * Nao achou * * *\n\n" ) ;
else
printf( "* * * Achou * * *\n\n" ) ;
fflush( stdin ) ;
printf( "Dado a ser retirado: " ) ;
scanf( "%c", &valor ) ;
if ( retira ( lista , valor ) == 0 )
printf( "* * * Nao encontrado * * *\n\n\n" ) ;
else
printf( "* * * Valor retirado * * *\n\n\n" ) ;
mostra( lista ) ;
esvazia( lista ) ;
system( "pause" ) ;
return 0 ;
}
60
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Lista Duplamente Encadeada – função insere()
void insere ( tpLista *noatual, tpElem x ){
tpLista *novono ;
novono=(tpLista *) malloc(sizeof(tpLista));
novono->dado = x ;
if ( noatual == NULL ) {
lista = novono;
lista->ant = NULL ;
lista->prox = NULL;
}
else {
while( noatual->prox != NULL )
noatual = noatual->prox ;
novono->ant = noatual;
novono->prox = NULL ;
noatual->prox = novono ;
}
}
61
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Lista Duplamente Encadeada – função procura()
tpLista* procura(tpLista *noatual, tpElem x){
while ( noatual != NULL ) {
if ( x == noatual->dado )
return noatual ;
else
noatual = noatual->prox ;
}
return NULL ;
}
62
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Lista Duplamente Encadeada – função mostra()
void mostra ( tpLista *noatual ){
tpLista *noant;
printf( "Sequencia normal ====> " ) ;
while( noatual != NULL ){
printf( " %c ",noatual->dado ) ;
noant = noatual->ant;
noatual = noatual->prox ;
}
printf( "\nSequencia invertida => " ) ;
while (noant != NULL) {
printf( " %c ",noant->prox->dado ) ;
noant = noant->ant;
} 
printf( " %c ",lista->dado ) ;
}
63
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Lista Duplamente Encadeada – função retira()
int retira ( tpLista *noatual, tpElem x ){
tpLista *libera ;
if ( noatual == NULL )
return 0 ;
else
if ( x == noatual->dado ){
libera = noatual ;
lista = noatual->prox ;
lista -> ant = NULL;
free( libera ) ;
return 1 ;
}
else{
while ( noatual->prox != NULL ){
if ( x == noatual->prox->dado ) {
libera = noatual->prox ;
noatual->prox = libera->prox ;
if (libera->prox != NULL)
libera->prox->ant = libera->ant;
free( libera ) ;
return 1 ;
}
else
noatual = noatual->prox ;
}
}
return 0 ;
}
64
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Lista Duplamente Encadeada – função esvazia()
void esvazia( tpLista *noatual ){
while ( noatual != NULL ){
lista = noatual->prox ;
free( noatual ) ;
noatual = lista ;
}
}
65
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
UNIVERSIDADE NOVE DE JULHO - UNINOVE
Pesquisa e Ordenação
Material disponível para download em: www.profvaniacristina.com
Árvores
66
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Introdução
• Listas encadeadas, Filas e Pilhas, têm como base as listas lineares, podendo ser estáticas ou 
dinâmicas. Mesmo tendo uma série de aplicações na manipulação de dados alguns problemas 
são observados: 
• A lista sequencial é eficiente para pesquisa de dados, mas não apresenta bom desempenho 
para inserir e remover dados;
• A lista encadeada é eficiente para inserir e remover dinamicamente de dados, mas não 
apresenta bom desempenho para pesquisar dados.
• A estrutura de dados Árvore é uma lista não linear com desempenho mais eficiente para as 
operações de inserção, busca e remoção de dados, pois representam um conceito de 
hierarquias. 
67
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Exemplo de uma árvore de estados brasileiros 68
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Acre
CearáParaná
Bahia
SergipeRoraimaPiauí
Goiás
Amazonas Rondônia
Alagoas
Amapá
Paraíba
Pará
Maranhão
• Uma árvore é composta por um conjunto de nós. Uma árvore contém um nó inicial identificado 
por raiz, podendo ter ou não outros nós, chamados de subárvores.
• Usualmente uma árvore é representada graficamente com a raiz para cima.Raiz e Subárvores 69
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Acre
CearáParaná
Bahia
SergipeRoraimaPiauí
Goiás
Amazonas Rondônia
Alagoas
Amapá
Paraíba
Pará
Maranhão
Subárvores
Raiz
• Uma árvore é um conjunto finito de um ou mais nós de tal modo que os conjuntos de nós 
desdobrados a partir da raiz são chamados de subárvores. 
• Seguindo o conceito acima, uma subárvore também é uma árvore e assim sucessivamente.
Subárvores 70
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Acre
CearáParaná
Bahia
SergipeRoraimaPiauí
Goiás
Amazonas Rondônia
Alagoas
Amapá
Paraíba
Pará
Maranhão
Subárvore
Raiz
Subárvore
Subárvore
• A raiz de uma árvore é chamada de pai dos nós de suas subárvores.
• As raízes das subárvores de um nó pai são chamados de filhos deste nó.
• Os filhos de um mesmo nó pai são denominados irmãos.
• Duas regras a respeito de pais:
• A raiz não tem pai.
• Todos os outros nós têm somente um pai.
• Um nó que não tem filho é chamado de folha.
Nós Pai, Filhos, Irmãos e Folhas 71
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Acre
CearáParaná
Bahia
SergipeRoraimaPiauí
Goiás
Amazonas Rondônia
Alagoas
Amapá
Paraíba
Pará
Maranhão
FILHOS
PAI
IRMÃOS
Nós Pai, Filhos, Irmãos e Folhas 72
Nó Pai Nós Filhos
Paraíba Pará, Bahia, Alagoas
Pará Amapá, Goiás
Bahia -
Alagoas Paraná, Maranhão, Ceará
Amapá Amazonas, Piauí, Roraima, Rondônia
Goiás -
Paraná -
Maranhão Acre, Sergipe
Ceará -
Amazonas -
Piauí -
Roraima -
Rondônia -
Acre -
Sergipe -
Irmãos
Pará, Bahia, Alagoas
Amapá, Goiás
Paraná, Maranhão, Ceará
Amazonas, Piauí, Roraima, Rondônia
Acre, Sergipe
Folhas
Bahia
Goiás, Paraná, Ceará
Amazonas, Piauí, Roraima, Rondônia, Acre, Sergipe
Acre
CearáParaná
Bahia
SergipeRoraimaPiauí
Goiás
Amazonas Rondônia
Alagoas
Amapá
Paraíba
Pará
Maranhão
Grau de um nó e Grau de uma árvore
• Grau de um nó corresponde ao número de subárvores do próprio nó, ou seja a quantidade de 
filhos que este nó tem. 
• Um nó folha tem grau 0, visto que mão tem filhos.
• O grau da árvore é definido pelo nó, de maior grau, que ela possui.
73
GRAU DA ÁRVORE: 4
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Acre
CearáParaná
Bahia
SergipeRoraimaPiauí
Goiás
Amazonas Rondônia
Alagoas
Amapá
Paraíba
Pará
Maranhão
Pará
grau 2
Amapá
grau 4
Acre
grau 0
• Nível ou profundidade de um nó é definido a partir da raiz da árvore que é identificado por 
zero.
• Os níveis seguintes são definidos com base na soma de uma unidade ao nível do seu nó pai.
Nível de um nó 74
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Acre
CearáParaná
Bahia
SergipeRoraimaPiauí
Goiás
Amazonas Rondônia
Alagoas
Amapá
Paraíba
Pará
Maranhão
Nível
3
Nível
2
Nível
1
Nível
0
Altura de um nó e Altura uma árvore
• A altura de um determinado nó em uma árvore é a distância entre o nó e o seu descendente 
mais afastado, ou seja, o caminho desde o nó até o descendente mais distante. Um nó folha, 
consequentemente tem altura 0
• A altura ou profundidade de uma árvore é definida com base no nível máximo entre todos os 
nós da árvore, ou seja, é a altura da raiz 
75
ALTURA DA ÁRVORE: 3
Nó Altura
Paraíba 3
Pará, Alagoas 2
Amapá, Maranhão 1
Bahia, Goiás, Paraná, Ceará, Amazonas, Piauí, Roraima, Rondônia, Acre, Sergipe 0
Acre
CearáParaná
Bahia
SergipeRoraimaPiauí
Goiás
Amazonas Rondônia
Alagoas
Amapá
Paraíba
Pará
Maranhão
Floresta
• Quando eliminamos um nó raiz de uma árvores, as suas subárvores formam duas árvores disjuntas, 
ou sejam árvores separadas. 
• A este conjunto de árvores disjuntas damos o nome de floresta.
• Por exemplo, se eliminarmos o nó raiz da árvore de bandeiras dos estados brasileiros, teremos uma 
Floresta formada por três árvores disjuntas.
76
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Acre
CearáParaná
Bahia
SergipeRoraimaPiauí
Goiás
Amazonas Rondônia
Alagoas
Amapá
Pará
Maranhão
Formas de representação: Hierárquica 77
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Acre
CearáParaná
Bahia
SergipeRoraimaPiauí
Goiás
Amazonas Rondônia
Alagoas
Amapá
Paraíba
Pará
Maranhão
• Também conhecido como Diagrama de Venn ou Conjuntos aninhados
Formas de representação: Diagrama de Inclusão 78
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Paraíba
Bahia Alagoas
Maranhão
Sergipe
Acre
CearáParaná
Pará
Goiás
Amapá
Roraima
Piauí
Amazonas
Rondônia
Formas de representação: Parenteses aninhados 79
( Paraíba ( Pará ( Amapá ) ( Goiás ( Piauí ) ) ) ( Bahia ) ( Alagoas ( Ceará ( Acre ) ( Sergipe ) ) ) )
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Acre SergipePiauí
Amapá
Pará
Goiás
Paraíba
Bahia Alagoas
Ceará
Árvores: Exercícios
• Observe a árvore abaixo, representada na forma hierárquica, e responda:
a) qual a altura da árvore?
b) quantos nós folhas a árvore possui?
c) em qual nível está o nó que contem a letra Q?
d) qual o grau do nó que contém a letra E?
e) os nós que contém as letras H, L, R, Q, S e G são todos irmãos? Justifique sua resposta.
80
A
J P
B
ED
T C
H L S G
I F
R Q
U
MY
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Árvores: Exercícios
• Observe a árvore abaixo, representada na forma de parênteses aninhados, monte a árvore na 
forma de representação hierárquica e responda:
a) quais os nós folha?
b) o grau da árvore?
c) quais os filhos do nó que contém a letra C?
( A (B) ( C (D (G) (H)) (E) (F (I)) ) )
81
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Árvores: Exercícios
• Observe a árvore abaixo, representada na forma hierárquica, e monte o diagrama de inclusão 
82
C E
B
DA H
G I
JG I
F
I
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
• O que caracteriza uma árvore como ÁRVORE BINÁRIA são as suas conexões com os outros 
nós.
• Para cada nó, uma árvore binária é permitido no máximo duas subárvores.
• Alguns nós possuem apenas uma subárvores.
• Em uma árvore binária é necessário sempre distinguir a subárvore esquerda e direita.
• As definições quanto a raiz, pai, filho, irmãos, folhas, grau, nível e altura, são as mesmas já 
vistas.
Árvore Binária 83
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Acre SergipePiauí
Amapá
Pará
Goiás
Paraíba
Alagoas
Ceará
• Consideramos uma árvore binária cheia se todos os nós tiverem duas subárvores, exceto 
os nós folhas, que estarão na mesma altura.
Árvore Binária Cheia 84
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Acre
Ceará
SergipeRoraima PiauíAmazonas Rondônia
Alagoas
Amapá
Paraíba
Pará
Maranhão Bahia
Goiás Paraná
Árvores de Busca Binária
• Árvore binária, é denominada ÁRVORE DE BUSCA BINÁRIA se:
• Todosos elementos armazenados na subárvore esquerda são menores que do que o 
elemento armazenado na raiz;
• Todos os elementos armazenados na subárvore direita são iguais ou maiores que do que o 
elemento armazenado na raiz.
• As subárvores esquerda e direita também são árvores de busca binária.
85
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Acre Bahia Sergipe
Piauí
GoiásAmapá Paraíba
Maranhão
Amazonas Paraná
Alagoas Ceará RoraimaPará
Rondônia
Árvore de Busca Binária - Exercício
• Assinale quais são as árvores de busca binária
86
a) F
J E
G
H I
B
CA
c) F
C E
B
DA H
G I
J
b) I
C
M S
B
DA R
O
d) 5
2 4
2
31
7 9
6
5 8
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
• Analise os dados representados pelo diagrama de inclusão, construa a representação na forma 
hierárquica e para casa árvore responda: a) Qual a altura da árvore?; b) Quantos nós tem cada 
nível?; c) Qual a raiz da árvore? ; d) É uma árvore binária?; e) Se for uma árvore binária: É uma 
árvore cheia?; É uma árvore de busca binária? Obs. Considere a disposição de cada nó na 
representação gráfica como sendo filho esquerdo ou direito.
Árvore de Busca Binária - Exercício 87
Profa. Vânia Cristina de Souza Pereira - 2012 - Material de Apoio ao Aluno - Notas de Aula – Pesquisa e Ordenação
C
F
EB
A
G
Da) A CB
D
F
Eb)
1
2
9
3
4
10
13
5
6
11
7
8
12
1415
c)
Atravessamento em Árvores de Busca Binária
• Uma vez criada uma árvore, como fazer para percorrer todos os seus nós?
• Que critérios usar? Ir inicialmente para a esquerda ou direita? De cima para baixo? 
88
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Acre PiauíGoiásAmapá
Maranhão
Amazonas Paraná
Alagoas Ceará RoraimaPará
Rondônia
Atravessamento em Árvores Binárias
• Significa percorrer de forma sistemática, por cada um de seus nodos, realizando um certo 
processamento.
• Tipos básicos de atravessamento:
• em-ordem
• pré-ordem
• pós-ordem
• Os tipos de atravessamento são facilmente compreendidos se fizermos uma analogia entre 
eles e as notações segundo uma expressão aritmética pode ser escrita: infixa, prefixa e pósfixa.
89
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Operações Básicas - Atravessamento
• Considerando a expressão infixa A + B, podemos usar a seguinte representação na forma de 
árvore binária:
• O atravessamento em-ordem da árvore será o acesso aos dados da seguinte maneira:
• Vai para o nó esquerdo, mostra o valor do nó, vai para o nó direito (ERD). 
• Exemplo: A + B
• O atravessamento pré-ordem da árvore será o acesso aos dados da seguinte maneira:
• Mostra o valor do nó, vai para o nó esquerdo, vai para o nó direito (RED). 
• Exemplo: + A B
• O atravessamento pós-ordem da árvore será o acesso aos dados da seguinte maneira:
• Vai para o nó esquerdo, vai para o nó direito, mostra o valor do nó (EDR). 
• Exemplo: A B +
90
+
A B
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Atravessamento Préordem 91
Maranhão, Amazonas, Alagoas, Acre, Amapá, Ceará, Goiás, Paraná, Pará, Roraima, Piauí, Rondônia
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Acre PiauíGoiásAmapá
Maranhão
Amazonas Paraná
Alagoas Ceará RoraimaPará
Rondônia
1
2
3
4 5
6
7 11
12
109
8
Atravessamento Emordem 92
Acre, Alagoas, Amapá, Amazonas, Ceará, Goiás, Maranhão, Pará, Paraná, Piauí, Rondônia, Roraima
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Acre PiauíGoiásAmapá
Maranhão
Amazonas Paraná
Alagoas Ceará RoraimaPará
Rondônia
7
4
2
1 3
5
6 10
11
128
9
Atravessamento Pósordem 93
Acre, Amapá, Alagoas, Goiás. Ceará, Amazonas, Pará, Rondônia, Piauí, Roraima, Paraná, Maranhão
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Acre PiauíGoiásAmapá
Maranhão
Amazonas Paraná
Alagoas Ceará RoraimaPará
Rondônia
12
6
3
1 2
5
4 9
8
107
11
• Monte as ABB e faça os atravessamentos préordem, emordem e pósordem.
a) 12, 4, 8, 26, 2, 5, 20, 22, 10, 13
b) F, H, I, B, C, A, G, B, E
c) Ivani, Paulo, Marli, Carla, Ester, Alice, Sofia, Denis
d) Percorrendo-se uma ABB foram produzidas as seguintes sequências emordem ( A B C D E F 
G H I J L ) e pósordem ( A B D E C G H L J I F ) . A partir destas informações monte a ABB.
e) Ache as expressões geradas a partir da árvore abaixo desenhada após atravessarmos 
através dos tipos préordem , emordem e pósordem.
Atravessamentos - Exercícios 94
+
a b +f
g h
*
c +
*
*d
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Operações Básicas
typedef char tpElem;
typedef struct registro {
struct registro* esq;
tpElem dado;
struct registro*dir;
} tpArvore;
tpArvore *raiz = NULL;
95
Estrutura básica de Árvore de Busca Binária
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Operações Básicas - Inserção
• É uma operação bastante simples. Basta verificar se a árvore não está vazia.
• Se estiver, a inserção será na própria raiz
• Se a árvore não estiver vazia, deve-se verificar se o novo elemento é menor do que a raiz
• Sendo verdadeiro, a inserção será na sub-árvore esquerda
• Sendo falso, a inserção será na sub-árvore direita.
96
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Operações Básicas - Inserção
void insere ( tpArvore **t, tpElem x ) {
if ( *t == NULL ) {
*t = ( tpArvore * ) malloc ( sizeof ( tpArvore ) );
( *t ) -> esq = NULL;
( *t ) -> dir = NULL;
( *t ) -> dado = x;
}
else
if ( x < ( *t ) -> dado )
insere( & ( ( *t ) -> esq ), x );
else
insere( & ( ( *t ) -> dir ), x ); 
}
97
Inserção de dados em uma Árvore de Busca Binária
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Operações Básicas - Busca
• Considerando uma árvore de busca binária T e um elemento x a ser procurado entre seus nós, 
existem 4 possibilidades:
• Se T é uma árvore vazia, não há o que procurar;
• Se a raiz de T armazena o elemento x, a solução é imediata;
• Se x é menor que o valor da raiz T, a busca prossegue na subárvore esquerda de T;
• Se x é maior que o valor da raiz T, a busca prossegue na subárvore direita de T.
98
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Operações Básicas - Busca
tpArvore* busca ( tpArvore *t, tpElem x ) {
if ( t == NULL )
return NULL;
else
if ( t -> dado == x )
return t;
else
if ( x < t -> dado )
return busca ( t -> esq, x );
else
return busca ( t -> dir, x );
}
99
Inserção de dados em uma Árvore de Busca Binária
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
100Operações Básicas - Atravessamento
void emordem ( tpArvore *t ) {
if (t != NULL) {
emordem ( t -> esq );
printf (" %c ", t -> dado );
emordem ( t -> dir );
}
}
void preordem ( tpArvore *t ) {
if ( t != NULL ) {
printf (" %c ", t -> dado );
preordem ( t -> esq );
preordem ( t -> dir );
}
}
void posordem ( tpArvore *t ) {
if( t != NULL ) {
posordem ( t -> esq );
posordem ( t -> dir );
printf (" %c ", t -> dado );
}
}
Atravessamentos em uma Árvore de Busca Binária
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Operações Básicas - Remoção
• Podemos considerar que a remoção de um nó de uma árvore é a rotina mais trabalhosa para 
ser desenvolvida e compreendida.
• Ainda assim, após analisarmos todos os possíveis casos, a remoção parecerá bastante 
simples.
• Por uma questão de simplificação , vamos admitir que inicialmente o elemento a ser removido 
encontra-se na raiz da árvore de busca binária T, então, as seguintes hipóteses devem ser 
avaliadas:
• A raiz não possui filhos:
• A solução é imediata. Podemos removê-la e anular T;
• Se a raiz possui um único filho:
• Podemos remover o nó raiz e o nó filho toma seu lugar;
• Se a raiz possuir dois filhos, não é possível quem ambos assumam o lugar do pai. Neste 
ponto surgem algumas perguntas:
• Qual das duas subárvores deve assumir o lugar do nó pai removido?
• O que deve ser feito com a subárvore que não foi a escolhida?
• Seu nó ficaria órfão?
101
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Operações básicas - Remoção
• A resposta para as questões anteriores é:
• Devemos buscar o nó que armazena o menor elemento na subárvore direita de T, este nó 
deve ser removido e o elemento armazenado por ele entrará na raiz da árvore T.
• Para entender a solução adotada precisamos lembrar da definição de árvore de busca 
binária. 
• Não podemos ter elementos maiores nem iguais à raiz numa subárvore esquerda;
• Não podemos ter elementos menores que a raiz numa subárvore direita.
• Então, se tomarmos o menor elemento da subárvore direita e o posicionarmos na raiz, então 
continua valendo a definição.
• Sabemos que o maior elemento numa árvore binária ordenada encontra-se no nó que ocupa 
a posição mais à direita possível. 
• Este nó certamente não terá um filho direito, pois se o tivesse não seria o maior da árvore; 
• Pode, entretanto, ter um filho esquerdo (menor).
102
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Operações básicas - Remoção
void remover ( tpArvore **t, tpElem x ) {
tpArvore *aux;
if ( *t != NULL ) {
if ( x < ( *t ) -> dado )
remover ( & ( *t ) -> esq, x );
else {
if ( x > ( *t ) -> dado )
remover ( & ( *t ) -> dir, x );
else {
if ( ( *t ) -> esq != NULL && ( *t ) -> dir != NULL ) {
aux = minimo ( ( *t ) -> dir );
( *t ) -> dado = ( aux -> dado );
remover ( & ( *t ) -> dir, ( *t ) -> dado );
}
else {
aux = *t;
if ( ( *t ) -> esq == NULL )
*t = ( *t ) -> dir;
else
*t = ( *t ) -> esq;
free ( aux );
}
}
}
}
}
103
tpArvore* minimo ( tpArvore *t ) {
if ( t == NULL )
return NULL;
else
if ( t -> esq == NULL )
return t;
else
return minimo ( t -> esq );
}
Remoção de dados em uma 
Árvore de Busca Binária
Função auxiliar para identificar o 
menor valor da sub arvore direita
I
D P
B G L T
A C F H J O R
E M Q S
N
I
D P
B G L T
A C F H J O R
M Q S
N
104
I
D P
B G L T
A C F H J O R
M Q S
N
I
D P
B G L
A C F H J O
M
Q S
N
R
105
J
D P
B G L
A C F H O
M
Q S
N
R
I
D P
B G L
A C F H J O
M
Q S
N
R
106
UNIVERSIDADE NOVE DE JULHO - UNINOVE
Pesquisa e Ordenação
Material disponível para download em: www.profvaniacristina.com
Árvores Balanceadas (AVL)
107
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
• Inserir dados em uma árvore busca binária de forma aleatória pode gerar uma árvore tendendo 
somente para um lado, ou seja, uma das subárvores (direita ou esquerda) terá mais nós que a 
outra.
• Uma árvore de busca binária não balanceada tem um custo alto para acessar os dados, pois a 
probalbilidades de acesso não são identicas entre si.
• Por exemplo:
Árvores Balanceadas - AVL 108
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
E G
J
I L
M
A C
D
B
N P
OF
H
G
F
E H
M
A
C
B
N P
O
D
LI
J
Árvore Balanceada
Árvore Degenerada
• Para procurar o nó contendo, por exemplo, a letra L o percurso na árvore balanceada será 
muito mais rápido que o percurso na árvore desbalanceada.
• Na primeira árvore foram utilizados menos passos que na segunda árvore, portanto árvores 
binárias são mais eficientes quando estão balanceadas.
Árvores Balanceadas - AVL 109
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
E G
J
I L
M
A C
D
B
N P
OF
H
G
F
E H
M
A
C
B
N P
O
D
LI
J
Árvore Balanceada
Árvore Degenerada
Árvores Balanceadas - AVL 110
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
• Uma árvore é considerada uma AVL se para cada nó da árvore, as alturas das subárvores
esquerda e direita sejam iguais ou tenham uma diferença de apenas uma unidade.
Exemplo de uma 
árvore AVL
Exemplo de uma 
não árvore AVL
C
TD
F
J
H
P
C
D
F
J
H
P
1
00
1
0
1
-1
3-2
1-2
0-0
0-0
1-00-0
1-0
1
0
1
0
1
-2
3-2
0-21-0
0-0
0-0
1-0
Árvores Balanceadas - AVL
• A denominação AVL é uma referência aos matemáticos russos , Adelson-Velskii e Landism que 
criaram em 1962 o conceito de árvore balanceada. 
• Uma árvore AVL é uma árvore de busca binária que controla a diferença de altura entre as 
subárvores esquerda e direita. Essa diferença é conhecida como “fator de balanceamento” de 
n e deve constar em cada nó de uma árvore balanceada. Os valores válidos são -1, 0 ou 1.
• Uma árvore de busca binária pode perder o efeito de sua eficiência se os dados forem inseridos 
aleatóriamente, podendo ficar semelhante a uma lista encadeada ou um vetor ordenado.
• A inserção de dados em uma AVL é composta por duas partes:
• Inserir um nó utilizando os mesmos conceitos da inserção em uma ABB, que pode ocasionar 
o aumento da altura da subárvore em que foi inserido.
• Verificar se a árvore resultante é ou não uma AVL, por meio do fator de balanceamento (FB).
• Para cada novo nó inserido o campo fator de balanceamento recebe inicialmente o valor 
zero e os nós ancestrais (anteriores) devem ter seus campos de fator de balanceamento 
atualizados.
• Se a árvore não estiver balanceada será necessário fazer um rebalanceamento por meio 
da movimentação dos nós, chamado de rotação.
111
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Rotações em uma AVL
• A rotação em uma AVL para que ela fique balanceada pode ser: 
• Rotação simples para a esquerda
• Rotação simples para a direita
• Rotação dupla para a esquerda (esquerda + direita)
• Rotação dupla para a direita (direita +esquerda)
• Dicas para identificar uma árvore degenerada, quando a rotação deve ser simples ou dupla e 
se a rotação é para a esquerda ou direita
a) FB precisa ser igual a 2 ou -2
b) Observe o FB do nó pai e do nó filho
• Se os sinais forem iguais ( + + ou - -) então a rotação é simples.
• Se os sinais forem diferentes ( + - ou - +) então a rotação é dupla.
c) Se o FB for positivo a rotação é para a esquerda
d) Se o FB for negativo a rotação é para a direita
112
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Rotação simples paraa direita 113
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
No nó com FB = -2
a) Considerar o nó pai (X) e seu filho esquerdo (Y)
b) Y passa a ser o pai e X passa a ser o filho direito de Y
c) O filho direito de Y passa a ser o filho esquerdo de X
d) Y mantém seu filho esquerdo
X
Y
Lembre-se das dicas:
• FB precisa ser igual a 2 ou -2
• Se os sinais do FB dos nós pai e filho forem iguais ( + + ou - -) então a rotação é simples.
• Se o FB for negativo a rotação é para a direita
E
-2
F
0
C
-1
A
1
B
0
D
0 A
1
B
0
C
0
E
0
D
0
F
0
Rotação simples para a esquerda 114
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
No nó com FB = 2
a) Considerar o nó pai (X) e seu filho direito(Y)
b) Y passa a ser o pai e X passa a ser o filho esquerdo de Y
c) O filho esquerdo de Y passa a ser o filho direito de X
d) Y mantém seu filho direito
Lembre-se das dicas:
• FB precisa ser igual a 2 ou -2
• Se os sinais do FB dos nós pai e filho forem iguais ( + + ou - -) então a rotação é simples.
• Se o FB for positivo rotação é para a esquerda
C
1
G
0
F
-1
B
-1
D
1
A
0
C
1
F
1
X
YD
2
B
-1
G
0
A
0
Rotação dupla para a direita 115
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Lembre-se das dicas:
• FB precisa ser igual a 2 ou -2
• Se os sinais do FB dos nós pai e filho forem diferentes ( + - ou - +) então a rotação é dupla.
• Se o FB for positivo a rotação é para a esquerda
• Se o FB for negativo a rotação é para a direita
No nó com FB = 1 fazer a primeira rotação para a esquerda
Fazer a segunda rotação no nó com FB = -2 para a direita
C
0
F
0
B
0
A
0
D
0
E
1
Y
X E
-2
F
0
D
-1
C
0
A
0
B
1
Y
X
E
-2
F
0
A
0
C
0
D
-2
B
0
Rotação dupla para a esquerda 116
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC
Lembre-se das dicas:
• FB precisa ser igual a 2 ou -2
• Se os sinais do FB dos nós pai e filho forem diferentes ( + - ou - +) então a rotação é dupla.
• Se o FB for positivo a rotação é para a esquerda
• Se o FB for negativo a rotação é para a direita
No nó com FB = -1 fazer a primeira rotação para a direita
Fazer a segunda rotação no nó com FB = 2 para a esquerda
I
0
H
-1
D
0
A
0
E
2
B
-1
G
-1
F
0
C
2
X
Y H
1
I
0
G
0
E
0
F
0
D
0
A
0
B
-1
C
1
E
2
X
Y
I
0
H
1
F
0
D
0
G
1
A
0
B
-1
C
2
AVL - Exercícios
• Com base nos valores 5, 3, 8, 2, 4, 7, 10, 1, 6, 9, 11, desenhe a árvore AVL e determine o FB de 
cada nó.
• Construa uma árvore AVL com os seguintes valores: 10, 20, 30. A cada inserção, atualize o FB
de cada nó, e, se for preciso, faça o balanceamento.
• Insira os valores 25 e 27. A cada inserção, atualize o FB de cada nó, e, se for preciso, faça o 
balanceamento.
117
Profa. Vânia Cristina de Souza Pereira – 2012 – Material de Apoio – Notas de Aula – Pesquisa e Ordenação – CC

Outros materiais