Estrutura de Dados em C

Prévia do material em texto

Kesede Rodrigues Julio
Suzete Freitas da Silva
Apostila de
Estrutura de
Dados em
C
versão: 20080909
Sumário
1 Introdução......................................................................................................................................3
1.1 Construindo Estruturas Heterogêneas....................................................................................3
2 Recursão........................................................................................................................................4
2.1 Introdução...............................................................................................................................4
2.2 – Exercícios............................................................................................................................7
3 Ponteiro e Alocação dinâmica.......................................................................................................8
3.1 Vetores de Ponteiros.............................................................................................................10
3.2 Matrizes de Ponteiro.............................................................................................................11
1. Indireção Simples...............................................................................................................11
2. Indireção Múltipla..............................................................................................................12
3.3 Exercícios.............................................................................................................................14
4 Listas............................................................................................................................................15
4.1 Listas Através de Vetores.....................................................................................................15
4.2 Listas através de Ponteiros...................................................................................................18
4.3 Exercícios.............................................................................................................................19
5 Pilha.............................................................................................................................................20
5.1 Pilha através de Vetores.......................................................................................................20
5.2 Pilha através de Ponteiros.....................................................................................................23
5.3 Exercícios.............................................................................................................................23
6 Fila...............................................................................................................................................25
6.1 Fila através de Vetores.........................................................................................................25
6.2 Fila através de Ponteiros.......................................................................................................27
6.3 Exercícios.............................................................................................................................28
7 Métodos de Classificação............................................................................................................29
7.1 Seleção Estrita......................................................................................................................29
7.2 Troca - Bolha........................................................................................................................29
7.3 Troca – Quick Sort...............................................................................................................30
7.4 Intercalação...........................................................................................................................32
7.5 Inserção – Direta...................................................................................................................33
7.6 Inserção - Shell.....................................................................................................................34
7.7 Distribuição – classificação por caixas.................................................................................35
7.8 Distribuição – classificação por radicais (raízes, Radix)......................................................36
7.9 Cálculo de Endereço (hashing).............................................................................................37
8 Métodos de Busca........................................................................................................................39
8.1 Definição..............................................................................................................................39
8.2 Método de Busca Linear ou Seqüencial...............................................................................39
8.3 Método de Busca Binária.....................................................................................................39
8.4 Método de Busca Hashing....................................................................................................40
9 Grafo............................................................................................................................................41
9.1 Definições.............................................................................................................................41
10 Árvores......................................................................................................................................43
10.1 Definições...........................................................................................................................43
10.2 Árvores Binárias.................................................................................................................44
10.3 Percursos em Árvores Binárias...........................................................................................46
10.4 Árvores Binárias de Busca (ABB)......................................................................................47
10.5 Exercícios...........................................................................................................................53
1 Introdução
Nesta apostila, discutiremos algumas das muitas formas de alocar 
informações na memória, a fim de facilitar pesquisas. Cada aplicação tem sua 
estrutura mais apropriada e portanto é responsabilidade do programador 
entender o funcionamento de cada uma delas para melhor aplicá-las. Para 
melhor trabalhar com estas estruturas devemos construir “Tipos Abstratos de 
Dados”, que nada mais são do que uma generalização dos “Tipos Simples de 
Dados”, estes podem ser entendidos como a menor parte tratável que um 
componente na memória (Ex.: int, float, char etc). Os TAD's são, portanto, 
agregações destes tipos juntamente com suas funcionalidades, ou seja, 
operações que podem ser executadas sobre eles.
1.1 Construindo Estruturas Heterogêneas
Antes de começarmos a falar de TAD's, precisamos saber como 
trabalhar com estruturas na memória. Em uma estrutura simples de 
vetor/matriz não temos a possibilidade de alocar valores de diferentes tipos, 
uma vez que declaramos apenas uma variável para ser o vetor/matriz, e em 
C, cada variável está vinculada a um único tipo. Para podermos alocar 
estruturas com valores de tipos diferentes precisamos de uma estrutura de 
variável, que nada mais é que o agrupamento destas variáveis. 
Definição: Permite vincular, na memória, variáveis de tipos 
diferentes.
Sintaxe: 
struct <nome da estrutura>{
 <tipo> <variável>;
 <tipo> <variável>;
.};
Temos a opção de deslocarmos também o nome da estrutura para o 
final. Desta forma, retiraríamos o nome de onde ele se encontra e 
colocaríamos após o “}”e o “;”. Podemos também declarar a nossa estrutura 
com um tipo, assim colocamos a palavra “typedef” antes da palavra “struct” 
e tratamos, a partir daí, nossa estrutura como um tipo. Para utilizarmos uma 
estrutura em nossos programas, devemos declarar uma variável do tipo 
estrutura. Assim, a linha de definição abaixo nos permite usar a estrutura em 
nosso programa através do nome da variável.
<nome da estrutura> <variável>;
Exemplo :
struct{
 int ra;
 char nome[30];
 float nota; 
}aluno;
aluno alu;
Algumas considerações devem ser relevadas, assim como:
1. Variável estrutura pode receber, de uma só vez, todo o conteúdo de 
outra variável estrutura. 
2. Uma estrutura pode conter outras estruturas, ou seja, podemos ter 
estruturas aninhadas.
3. Podem ser passadas como parâmetro, por valor ou por referência. 
4. Variável do tipo estrutura pode ser retornada de funções. 
5. Podemos declarar matrizes do tipo estrutura.
2 Recursão
2.1 Introdução
A técnica de recursão é aplicável quando a solução de um 
problema envolve sub-soluções de mesmo procedimento, ou seja, a aplicação 
da mesma lógica repetidamente para cada parte do problema, resolve o 
problema como um todo. Um procedimento recursivo terá pelo menos, dois 
passos fundamentais:
1. Um passo onde o resultado é imediatamente conhecido
2. Outro passo onde teremos a chamada do mesmo procedimento.
Na prática, em C, teremos uma função chamando ela mesma, 
mudando apenas os valores dos parâmetros. 
Um caso clássico é o calculo do fatorial, onde o fatorial de um 
numero será a multiplicação dele pelo fatorial do seu antecessor. Para 
resolver o fatorial de 1, não precisaremos da recursão, no entanto, valores 
de fatorial acima de 1 sempre precisará de, pelo menos, uma chamada à 
própria função. Para resolvermos o fatorial de 5 temos que, primeiro, 
resolver o fatorial de 4. Para resolvermos o fatorial de 4, temos que, primeiro 
resolver o fatorial de 3, e assim por diante. As chamadas recursivas sempre 
são chamadas com argumentos diferentes, caso contrário, teremos 
chamadas recursivas infinitas.
Digite o Exemplo 2.1:- Faca um programa que receba um 
numero qualquer do usuário, e que contenha uma função que 
calcule e retorne o fatorial deste numero, recebido como 
parâmetro pela função. Mostre o resultado para o usuário.
1 #include <stdio.h> Permite inclusão de funções de i/o
2 #include <conio.h> Permite inclusão da função getch()
3 int fat(int valor); Declara o protótipo da função
4 int main(){ Abre função principal
5 int val; Declara variável val
6 scanf(“%d”,&val); Recebe o valor de val do usuário
7 printf("Fatorial = " %d”, fat(val)); Chama a função fat() e imprime o 
seu retorno. O valor de “val” é 
enviado à função fat() como 
parâmetro
8 getch(); Pára a execução do programa
9 } Fecha a função principal
10 int fat(int valor){ Abre a função fat() e recebe o valor 
enviado “val” (linha 7) na variável 
“valor”
11 if (valor==1){ Verifica se o “valor” é 1
12 return 1; Caso seja, retorna 1 para a função 
chamadora
13 } Fecha o if
14 else{ Verifica se “valor” é diferente de 1
15 return valor * fat(valor-1); Caso seja, chama novamente a 
função fat(), envia o resultado da 
subtração (valor – 1). A 
multiplicação de fat() por “valor” só 
será realizada quando o if da função 
for verdadeiro. Isto é melhor 
explicado no DE (Diagrama de 
Execução) 
16 } Fecha o else
17 } Fecha a função fat()
Portanto, uma solução recursiva consiste na resolução sucessiva 
de sub-problemas menores até chegarmos ao problema mais simples, o qual 
tem solução imediata.
Uma forma de mostrar a execução do programa passo-a-passo, 
principalmente quando temos função envolvida na solução do problema, é 
através do DE - “Diagrama de Execução”. Este diagrama permite fazer uma 
“teste-de-mesa” no programa mostrando os retorno de cada função 
envolvida na solução. Vamos demostrar o diagrama utilizando o Exemplo 2.1 
que resolve o fatorial de um número digitado pelo usuário.
Cada retângulo refere-se a chamada de uma função, sendo que o 
primeiro refere-se à função “main()”. Nele nós declaramos as variáveis, seus 
valores e executamos o programa até que cheguemos na função printf(). 
Aqui temos uma chamada da função “fat()”. Supondo que o valor digitado 
em “val” seja “5” (val=5), desenhamos outro retângulo, interno ao primeiro, 
referente a chamada da função “fat()”. Aqui declaramos as variáveis locais, 
neste caso apenas “valor”, e atribuímos à ela o valor enviado “5”, como 
supomos. Neste caso então, o if é negado, pois valor é igual a 5 e não igual a 
1. Entramos, portanto no else e encontramos um return com a chamada da 
função fat(), só que agora com o parâmetro valor-1. Repare que o 
argumento agora vale “4” (5-1), pois isto foi resultado de uma subtração. 
Acompanhamos novamente a execução da função (o if é negado e entramos 
no else) e novamente chegamos a chamada recursiva de “fat()”. 
Desenhamos outro retângulo referente a nova chamada e definimos o novo 
valor do parâmetro. Seguimos desta forma até chegarmos no momento em 
que o argumento (“valor”) valerá 1. Neste caso, a chamada recursiva não 
acontece, pois a condição do “if” será verdadeira. Logo, o retorno será 1. 
Este valor é retornado para a última chamada recursiva (return 2 * fat(1)) e 
então a multiplicação é executada (“2 * 1”). O produto é retornado para a 
chamada recursiva anterior e então é executada a multiplicação (“3 * 2”). 
Isto se repete até que o último resultado (5 * fat(4)) seja retornado para a 
main(), e assim temos o valor do fatorial de 5, pronto para ser impresso 
(120). Um bom exercício é mudar o valor para 7 e refazer DE (o resultado 
terá que ser 5040).
val=5
fat(5) 120
valor=5
5*fat(4) 24
valor=4
4*fat(3) 6
valor=3
3*fat(2) 2
valor=2
2*fat(1) 1
valor=1
2.2 – Exercícios
1. Efetue, recursivamente, a soma dos 10 primeiros números 
inteiros. Faça o diagrama de execução.
2. Mostre, recursivamente, os números de 1 a 10. Faça o diagrama 
de execução.
3. Mostre, recursivamente, os números de 10 a 1. Faça o diagrama 
de execução.
4. Conte, recursivamente, quantos caracteres existem em um 
string, sabendo que um string finaliza com ’\0´. A string será digitada pelo usuário. 
Faça o diagrama de execução.
5. Mostre, na tela, os 10 primeiros termos da seqüência de 
fibonacci, recursivamente. A regra da seqüência diz que um termo é sempre 
resultado da soma dos dois anteriores, e os dois primeiros termos são iguais a 1 
(um).
3 Ponteiro e Alocação dinâmica
São variáveis que permitem a alocação de endereços de outras variáveis. 
Uma variável ponteiro não contem um valor comum (tipo int, char, float etc), apenas 
aponta para ela, ou seja, guarda o endereço da variável que contém o valor. Exemplo.:
Digite o Exemplo 3.1 :- Faça um programa que declare uma variável 
inteira (incializada com 10) e através de um ponteiro, imprima seu 
conteúdo.
1 int main(){ Abre main()
2 int a=10; Declara variavel inteira
3 int *pa; Declara variavel ponteiro para int
4 pa=&a; Atribui endereço de “a” para a vairavel ponteiro 
“pa”, logo, “pa” passa a ser uma referencia de “a”
5 printf(“Conteudo de a = %d”, *pa); Imprime o conteudo de “a” através de “pa”
6 system(“pause”); Pára o programa
7 } Fecha main()
Neste caso, “*pa” é o mesmo que “a”, pois pa aponta para a.
Operadores de ponteiros:
& :- associado a uma variável devolve seu endereço.
* :- associado a uma variável ponteiro devolve o conteúdo da 
variável que está sendo apontada. 
Quando atribuímos um ponteiro para outro, estamos atribuindo o 
endereço nele contido. Para fazer com que o ponteiro aponte para a próxima 
posição devemos somar 1 na variável ponteiro, isto faz com que seja 
acrescido uma unidade de tipo ao valor do endereço. Exemplos:
Digite o Exemplo 3.2: A função deste programa é para avaliação das 
posições e conteúdos da memória em função de modificações feitas 
pelo programa. Faça um minucioso estudo do resultado.
1 #include <stdio.h>
#include<stdlib.h>
Inclui protótipos
2 int main(){ Abre main()
3 int x=5,y=6; Declara variaveis inteiras
4 int *px, *py; Declara variaveis ponteiro para int
5 px=&x; Atribui endereço de “x” para variavel 
ponteiro “px”. Portanto, “px” passa a 
apontar para “x”
6 py=&y; Atribui endereço de “y” para variavel 
ponteiro “py”. Portanto, “py” passa a 
apontar para “y”
7 if (px<py){
 printf("py-px = %u\n",py-px);
} 
else{
 printf("px-py = %u\n", px-py);
}
Verifica se o conteudo (endereço de 
“x”) de “px” é menor que o conteúdo 
(endereço de “y”)de “py”. Imprime a 
subtração do maior pelo menor
8 printf("px = %u, *px = %d, &px = %u\n", px,*px,&px); Imprime: conteúdo de “px” (endereço 
de “x”), o conteudo de onde “px” 
aponta (conteúdo de “x”) e o endereço 
da variável ponteiro “px” 
9 printf("py = %u, *py = %d, &py = %u\n", py,*py,&py); Imprime: conteúdo de “py” (endereço 
de “y”), o conteudo de onde “py” 
aponta (conteúdo de “y”) e o endereço 
da variável ponteiro “py” 
10 px++; Soma uma unidade de inteiro na 
variavel ponteiro “px”. Com isso “px” 
não aponta mais para “x”. Caso “px” 
seja 100, valerá 102 após a soma. Caso 
fosse ponteiro para float, valeria 104.
11 printf("px = %u, *px = %d, &px = %u\n", px,*px,&px); Imprime: conteúdo de “px” (endereço 
de “x”), o conteudo de onde “px” 
aponta (conteúdo de “x”) e o endereço 
da variável ponteiro “px” 
12 py=px+3; Atribui para “py” a soma de 3 unidades 
de tipo mais o conteúdo de “px”. Com 
isso “py” não aponta mais para “y”.
13 printf("py = %u, *py = %d, &py = %u\n", py,*py,&py); Imprime: conteúdo de “py” (endereço 
de “y”), o conteudo de onde “py” 
aponta (conteúdo de “y”) e o endereço 
da variável ponteiro “py” 
14 printf("py-px = %u\n",py-px); Imprime a subração do endereço 
contido em “py” pelo endereço contido 
em “px”
15 system(“pause”); Pára o programa
16 } Fecha main()
3.1 Vetores de Ponteiros
Todo vetor, na realidade, é um ponteiro. Sendo assim, podemos 
declará-las e manipulá-las como tal. A grande vantagem é a velocidade de 
execução, muito mais rápida através de ponteiros do que com índices, porém 
o seu uso desordenado torna o programa incompreensível.
Digite o Exemplo 3.3:- Faça um programa que receba as notas de 5 
alunos através de ponteiros e mostre a media. 
1 #include <stdio.h>
#include <stdlib.h>
Inclui protótipos
2 int main(){ Abre main()
3 float *notas; Declara variavel ponteiro
4 notas=(float *) malloc(5*sizeof(float)); Aloca 20 (5*4) bytes na memória e atribui o 
endereço do primeiro byte alocado para a variável 
ponteiro “notas”
5 for (int i=0;i<5;i++){
scanf("%f", notas+i);
}
Carrega vetor a partir do usuário. (notas + i) é o 
endereço onde será alocado o que o usuário 
digitar
6 for (i=0;i<5;i++){
printf("%f\n", *(notas+i));
}
Imprime todas as notas. 
*(notas+i) é o conteúdo do endereço (notas+i)
7 12. free(notas); Libera o espaço para outras tarefas usarem
8 system(“pause”); Pára o programa
9 } Fecha main()
Aqui temos duas novas funções: malloc() e free(). Malloc() é 
utilizada para alocar espaço na memória e retornar o endereço do primeiro 
byte. A função free() libera o espaço que foi reservado por malloc(). A este 
recurso chamamos de "Alocação Dinâmica", pois o espaço na memória é 
criado em tempo de execução.
3.2 Matrizes de Ponteiro
1. Indireção Simples
Da mesma forma que o vetor, podemos manipular matrizes, 
através de ponteiros, linearmente. Assim, para que todas as posições sejam 
acessadas utilizamos uma aritmética simples de endereços.
Digite o Exemplo 3.4:- Faça um programa que carregue, a partir do 
usuário, uma matriz 3x3 alocada dinamicamente por indireção simples, 
e mostre em seguida todos os valores carregados.
1 #include <stdio.h>
#include <stdlib.h>
Inclui protótipos
2 #define L 3
#define C 3
Define macros L e C
3 int main(){ Abre main()
4 int *mat,i,j; Declara variaveis
5 mat=(int *) malloc(L*C*sizeof(int)); Aloca 18 bytes (3*3*2) na memoria e atribui o 
endereço do primeiro byte para a variavel mat
6 for (i=0;i<L;i++){
 for (j=0;j<C;j++){
 scanf ("%d",mat+(i*C) +j);
 }
}
Carrega a matriz a partir do usuário. 
mat+(i*C)+j é o endereço onde será alocado cada 
valor digitado. A matriz é linear.
7 for (i=0;i<L;i++){
 for (j=0;j<C;j++){
 printf(“%d\n”,*(mat+(i*C)+j));
 }
}
Mostra os valores alocados na matriz.
*(mat+(i*C)+j) é o proprio valor que o usuário 
digitou
8 system(“pause”); Pára o programa
9 free(mat); Libera memoria
10 } Fecha main()
2. Indireção Múltipla
Outra forma de construirmos matrizes é através da declaração de 
ponteiro para ponteiro. Isso faz com que nosso programa fique mais flexível, 
pois poderemos classificar as linhas através de uma simples troca de 
ponteiros.
Digite o Exemplo 3.5:- Faça um programa que carregue, a partir do 
usuário, uma matriz 3x3 alocada dinamicamente por indireção múltipla, 
e mostre em seguida todos os valores carregados.
1
#include <stdlib.h> 
#include <stdio.h>
Inclui protótipos
2 #define LIN 3
#define COL 3
Define macros LIN e COL
3 int main(){ Abre main()
4 int **mat, i, j; Declara variavel ponteiro de ponteiro 
para int
5 mat = (int **) malloc(LIN*sizeof(int *)); Aloca 6 bytes na memoria e atribui o 
endereço do primeiro byte para a 
variavel mat. Este ponteiro irá apontar 
para um vetor de ponteiros
6 for (i=0;i<LIN;i++){
 *(mat+i)= (int *) malloc(COL*sizeof(int));
}
Aloca 6 bytes para cada posição do 
vetor de ponteiros, ou seja, cada 
posição alocada anteriormente irá 
apontar para um vetor de inteiros.
7 for (i=0;i<LIN;i++){
 for (j=0;j<COL;j++){
 scanf("%d",*(mat+i)+j);
 }
}
Carrega os valores a partir do usuário. 
Percorre todas as colunas que cada 
posicao que o vetor ponteiro aponta, 
carregando assim toda a matriz.
8 for (i=0;i<LIN;i++){
 for (j=0;j<COL;j++){ 
Imprime os conteúdos de toda matriz
 printf("%d\n",*(*(mat+i)+j));
 } 
}
9 system(“pause”); Pára o programa
10 for (i=0;i<LIN;i++){
 free(*(mat+i));
}
Libera os vetores coluna
11 free(mat); Libera o vetor linha 
12 } Fecha main()
3.3 Exercícios
1. Faça um programa que mostre se um determinado valor foi 
encontrado ou não em um vetor de inteiros. O usuário deve digitar: o valor a ser 
encontrado, o tamanho do vetor (a ser criado dinamicamente) e os valores de cada 
posição do vetor.
2. Faça uma função que aloque e preencha um vetor com tamanho 
escolhido pelo usuário. O preenchimento deve ser feito com números aleatórios 
(função rand()) e não deve conter números repetidos.
3. Considerando que a variação de tensão foi percebida em várias 
residências de um determinado bairro, desenvolva um programa capaz de receber a 
média destes valores referentes a cada residência em uma matriz com tamanho 
determinado pelo usuário, sendo que cada linha da matriz representará uma rua e a 
quantidade de casas será a mesma em todas as ruas. O programa deverá mostrar 
qual a rua de tensão mais estável (desvio padrão). Utilize indireção simples para 
alocação da matriz.
4. Escreva um programa que gere uma matriz em cada posição 
guarde a soma de suas coordenadas. As dimensões da matriz deverão ser digitadas 
pelo usuário e o programa deverá informar os valores gerados.
5. Escreva um programa que leia uma matriz, a partir do 
usuário, troque a posição de duas linhas escolhidas pelo usuário e mostre a 
matriz resultante. Utilize indireção múltipla para alocação da matriz.
4 Listas
Uma lista linear é uma seqüência de informações organizadas 
seqüencialmente (lógica ou fisicamente). Uma lista pode ser organizada 
estática ou dinamicamente na memória. Na forma estática utilizamos a 
estrutura de vetor para armazenarmos as informações e as ligações e na 
dinâmica utilizamos uma estrutura que será alocada na memória sempre que 
precisarmos de um novo espaço. Podemos atribuir várias operações para 
uma lista, por exemplo: 
1. Inicializar (esvaziar) a lista 
2. Inserir um elemento na lista
3. Retirar um elemento da lista4. Verificar se a lista está vazia
5. Imprimir a lista
Nós veremos duas formas de implementação: através de vetores e 
através de ponteiros. 
4.1 Listas Através de Vetores
Neste caso, teremos a declaração de um vetor de um determinado 
tamanho. Este tamanho deve ser suficiente para alocar toda a lista, prevendo 
aumentos futuros, pois neste tipo de alocação (estática), não podemos 
alterar este tamanho em tempo de execução. Assim, nossa lista estará 
alocada em posições contíguas na memória. A lista sempre terá um início no 
índice 0 (zero) e um fim que nem sempre coincidirá com o final do vetor. 
Podemos alocar elementos em qualquer posição da lista, e quando isso 
acontecer no meio da lista, devemos deslocar todos os elementos que 
estarão à direita dele, afim de “abrir” espaço para alocação. Da mesma forma 
teremos que deslocar elementos sempre que retirarmos elementos do meio 
da lista. Este procedimento de deslocamento evita a existência de “espaços 
vazios” no meio da lista.
a1 a2 a3 ... an ...
0 1 2
... n-
1
... Tam_Vet
O primeiro elemento da nossa lista na figura acima é “a1”, o último é 
“an” alocados em um vetor de tamanho Tam_Vet. Teremos sempre uma 
variável para controlar o inicio da lista e o fim da lista, sempre que 
acrescentarmos uma elemento a lista, a variável que controla o final da lista 
será incrementado, e será decrementado sempre que for retirado um 
elemento. Quando o final da lista for maior que Tam_Vet consideramos a 
lista cheia, ou seja, não podemos inserir mais nenhum elemento e quando o 
final da lista for igual ao início, consideramos a lista vazia, e portanto, não 
podemos retirar nenhum elemento.
primeir
o
últim
o
Digite o Exemplo 2.1:- Faça um TAD de uma lista capaz de controlar 
a inserção, retirada e impressão dos elementos da lista. Faça também 
um programa capaz de testar o TAD. Este exemplo deve ser dividido 
em dois arquivos: um para o TAD (terá extensão .h) e outro com o 
programa principal(terá a extensão .cpp). Inclua o arquivo “.h” no 
arquivo “.cpp” e execute o .cpp. Esta é uma maneira simples de 
implementação de um TAD.
// arquivo .h
// Lista atraves de Vetor
#include <iostream.h>
#include <conio.h>
#define INICIO_VET 0
#define TAM_VET 10
Struct TipoLista{
int item[TAM_VET];
int primeiro, ultimo;
};
void Inicializa(TipoLista *lista){
lista->primeiro=INICIO_VET;
lista->ultimo=lista->primeiro;
}
int Vazia(TipoLista lista){
return (lista.primeiro==lista.ultimo);
}
void Insere(int elem, TipoLista *lista){
if (lista->ultimo+1 > TAM_VET){
cout << "Lista cheia.";
}
else{
lista->item[lista->ultimo]=elem;
lista->ultimo++;
}
}
void Retira_Pos(int p, TipoLista *lista, int *item){
int aux;
if (Vazia(*lista) || p >= lista->ultimo){
cout << "Erro: Posicao nao existe";
return;
}
*item=lista->item[p-1];
for (aux=p; aux<lista->ultimo;aux++){
lista->item[aux-1]=lista->item[aux];
}
lista->ultimo--;
}
void Imprime(TipoLista lista){
int aux;
for (aux=lista.primeiro;aux<(lista.ultimo);aux++){
cout << lista.item[aux] << endl;
}
}
// arquivo .cpp
#include “Tlista.h”
int main(){
TipoLista l;
int elem;
clrscr();
Inicializa(&l);
elem=10;
Insere(elem,&l);
elem=20;
Insere(elem,&l);
elem=30;
Insere(elem,&l);
elem=40;
Insere(elem,&l);
elem=50;
Insere(elem,&l);
Retira_Pos(1,&l,&elem);
Imprime(l);
getch();
}
4.2 Listas através de Ponteiros
Desta forma, podemos ter elementos na memória sempre que 
precisarmos dele, pois sua alocação é criada em tempo de execução através 
da função malloc(). Cada elemento deve ter informação do próximo e do 
anterior. 
O exemplo acima define uma estrutura que contém um valor inteiro e 
dois ponteiros para a mesma estrutura. Estes ponteiros servirão para “ligar” 
a lista, a variável “ant” apontará sempre para a estrutura anteriormente 
alocada e a variável “prox” apontará para a próxima estrutura da seqüência 
ou para NULL (nulo), caso seja a última estrutura da lista.
struct no{
 no *ant;
 int valor;
 no *prox;
};
ant Valor prox
 
Digite o Exemplo 10.2 :- Faça um programa que carregue uma 
lista ligada na memória de valores inteiros. Após o carregamento 
da lista, mostre-a.
#include <stdio.h>
#include <stdlib.h>
struct no{
 no *ant;
 int valor;
 no *prox;
};
int main(){
 no *inicio, *fim, *novo, *aux, *proximo, *anterior;
 int aux_valor, cont, achou; // inicializado em zero 
para forcar entrada no looping
 // Inclusao na lista
 scanf("%i",&aux_valor);
 if (aux_valor!=-1){
 inicio = (no *) malloc(sizeof(no));
 inicio->valor=aux_valor;
 inicio->prox=inicio->ant=NULL;
 fim=novo=aux=inicio;
 }
 while (aux_valor != -1){
 scanf("%i",&aux_valor);
 if (aux_valor!=-1){
 novo = (no *) malloc(sizeof(no));
 novo->valor=aux_valor;
 aux->prox=novo;
 novo->ant=aux;
 fim=aux=novo;
 novo->prox=NULL;
 }
 }
 
// Consulta geral da lista
 aux=inicio;
 while (aux->prox!=NULL){
 printf("\n%i",aux->valor);
 aux=aux->prox;
 }
 printf("\n%i",aux->valor);
 
// Remoção do 7o. elemento de uma 
 // lista com N elementos
 aux=proximo=anterior=inicio;
 cont=1;
 achou=0;
 while (aux->prox!=NULL){
 if (cont==7){
 printf("vai remover");
 anterior->prox=proximo;
 proximo->ant=anterior;
 free(aux);
 achou=1;
 break;
 }
 cont++;
 anterior=aux;
 aux=aux->prox;
 proximo=aux->prox;
 }
 if (achou==0){
 printf("Não existe o setimo elemento");
 }
 else{
 // Consulta geral da lista
 aux=inicio;
 while (aux->prox!=NULL){
 printf("\n%i",aux->valor);
 aux=aux->prox;
 }
 printf("\n%i",aux->valor);
 }
}
A maneira mais simples de se trabalhar com lista é através de 
vetores (lista seqüencial). Podemos ter dois tipos de listas de acesso restrito 
(Pilha e Fila), ou seja, com posição definida para colocar e para retirar 
elementos da lista.
4.3 Exercícios
Lista através de Vetores
1. Acrescente a função de inserir um elemento em uma posição específica no 
TAD lista através de vetores.
void Insere_Pos(int p, TipoLista *lista, TipoItem *item){
2. Acrescente a função de retirar um elemento qualquer no TAD lista através de 
vetores.
void Retira_Elem(TipoLista *lista, TipoItem *item){
3. Acrescente a função de listar a lista em ordem contrária, ou seja, do último 
para o primeiro elemento.
void Mostra_Invertido(TipoLista *lista){
Lista através de Ponteiros
4. Crie um TAD lista, agora utilizando ponteiros. A TAD deve conter a função 
Inserir um elemento, Retirar um elemento, Listar todos os elementos em 
ordem contrária.
5. Acrescente ao TAD lista através de ponteiros para Retirar um elemento da 
lista e para consultar um elemento na lista.
21
5 Pilha
Uma pilha, nada mais é que uma lista linear, porém com restrição de 
acesso (inserção e retirada), por isso ela é também chamada de lista restrita. 
Uma pilha funciona como uma pilha de pratos: acrescenta-se sempre o 
próximo prato no topo da pilha e ao fazermos a retirada, retiramos o último 
prato que colocamos (lifo: last in first out). Veremos dois modos de 
implementação: Seqüencial e ligada com ponteiros. As operações básicas do 
TAD Pilha, são: inserção (empilha), remoção (desempilha), verifica se vazia, 
verifica se cheia e retorna topo.
5.1 Pilha através de Vetores
Para alocar uma pilha utilizando vetores, devemos construir uma 
estrutura que contenha as informações dos elementos da pilha, como 
também o índice do topo. Assim,
typedef struct{
int info[TamMax];
int topo;
}Pilha;
22
Digite o Exemplo 3.1:- Faça uma TAD pilha implementada com vetor 
e que contenha funções para empilhar, desempilhar, mostrar o 
conteúdo da pilha e retornar o elemento do topo. O TAD deve ter 
extensão .h.
// TAD Pilha com Vetor
#include <iostream.h>
#include <conio.h>
#define TamMax 10
typedef struct{
int info[TamMax];
int Topo;
}Pilha;
void Inicializa(Pilha *p){
p->Topo=0;
}
int Vazia(Pilha p){
if (p.Topo==0){
return 1;
}
else{
return 0;
}
}
int Cheia(Pilha p){
if (p.Topo==TamMax){return 1;
}
else{
return 0;
}
}
int Empilha(Pilha *p, int elem){
if (Cheia(*p)){
return 0;
}
else{
p->info[p->Topo]=elem;
p->Topo++;
return 1;
}
}
int Desempilha(Pilha *p){
if (Vazia(*p)){
return 0;
}
else{
return p->info[p->Topo--];
}
}
int RetTopo(Pilha p){
return p.info[p.Topo-1];
}
int MostraPilha(Pilha p){
int i;
if (Vazia(p)){
return 0;
}
else{
for (i=0;i<p.Topo;i++){
cout << p.info[i] << endl;
}
getch();
return 1;
}
}
23
Digite o Exemplo 3.2:- Faça um programa que, usando a TAD 
Pilhav.h, empilhe os valores 10, 20, 30, 40 e 50 e desempilhe dois 
elementos, logo em seguida. Após todos os empilhamentos e a cada 
desempilhamento mostre o valor do topo e o conteudo atual de toda 
pilha.
// Este programa testa a TAD Pilha com Vetor
// Empilha-se 5 elementos e desempilha-se 2 elementos
#include "d:\aulas\aposti~1\lingua~1\pilhav.h"
void main(){
Pilha p;
Inicializa(&p);
Empilha(&p,10);
Empilha(&p,20);
Empilha(&p,30);
Empilha(&p,40);
Empilha(&p,50);
clrscr();
cout << endl << "Topo = " << RetTopo(p) << endl;
MostraPilha(p);
Desempilha(&p);
cout << endl << "Topo = " << RetTopo(p) << endl;
MostraPilha(p);
Desempilha(&p);
cout << endl << "Topo = " << RetTopo(p) << endl;
MostraPilha(p);
}
24
5.2 Pilha através de Ponteiros
Digite o Exemplo 3.3:- Faça um programa que mostre um menu de 
escolha para o usuário com as opcoes de inclusão, consulta e retirada 
de elementos em uma pilha alocada dinamicamente. Construa um TAD 
Pilha para isso.
//Inclusao e consulta em uma Pilha
#include <iostream.h>
#include <conio.h>
#include <stdlib.h>
struct no{
no *prox;
int val;
};
void insere(no **t, int elem);
void consulta(no *t);
int retira(no **t);
int menu();
void main(){
no *topo=NULL;
int opcao=0, elem;
while (opcao!=4){
opcao=menu();
switch (opcao){
case 1: cout << "Digite o valor a ser inserido: ";
cin >> elem;
insere(&topo, elem);
break;
case 2: consulta(topo);
break;
case 3: elem=retira(&topo);
if (elem!=-1){
cout << elem;
}
getch();
break;
case 4: exit(1);
}
}
}
void consulta(no *t){
if (t==NULL){
cout << "Pilha vazia";
}
else{
do{
cout << t->val << endl;
t=t->prox;
}while (t!=NULL);
}
getch();
}
int menu(){
int op;
clrscr();
cout << "Pilha" << endl;
cout << "1. Insere" << endl;
cout << "2. Consulta" << endl;
cout << "3. Retira" << endl;
cout << "4. Sai" << endl;
cin >> op;
return op;
}
void insere(no **t, int elem){
no *novo;
novo=(no *) malloc(sizeof(no));
novo->val=elem;
if ((*t)==NULL){
(*t)=novo;
(*t)->prox=NULL;
}
else{
novo->prox=*t;
(*t)=novo;
}
}
int retira(no **t){
int elem;
no *aux;
if ((*t)==NULL){
cout << "Pilha vazia";
}
else{
elem=(*t)->val;
aux=(*t);
(*t)=(*t)->prox;
free(aux);
return elem;
}
return -1;
}
5.3 Exercícios
Implementação de Pilha por Vetores
1. Ofereça um serviço que retorne o tamanho da pilha.
25
2. Ofereça um serviço que mostre os 3 próximos elementos a serem 
desempilhados, se houverem.
Pilha através de Ponteiros
3. Faça um programa que controle o “morto” do baralho (monte de cartas 
onde os jogadores podem comprar cartas durante um jogo). Esta 
seqüência obedece uma pilha onde a carta sempre será retirada do topo da 
pilha. A estrutura deverá conter o naipe e o valor de cada carta. Faça um 
TAD que construa o morto e retire carta dele.
26
6 Fila
A fila funciona como uma fila de banco, sempre que alguém chega, 
ocupa o último lugar e quando alguém sai, sai do começo da fila (fifo: first in 
first out).
6.1 Fila através de Vetores
A implementação de fila por vetor requer uma variável de controle 
para o inicio e uma para o fim da fila. Sempre que inserirmos um elemento, 
inseriremos no índice “fim”, e sempre que retirarmos um elemento, 
retiraremos no índice “início”.
Digite o Exemplo 4.1: Faça um TAD fila, contendo a estrutura da fila 
(vetor fila, inicio e fim) e funções para: Inserir, Retirar e Listar 
elementos.
// TAD de Fila atraves de Vetor
#include <iostream.h>
#include <conio.h>
#define TAM_VET 10
typedef struct{
int item[TAM_VET];
int inicio, fim;
}TipoFila;
void Inicializa(TipoFila *fila){
fila->inicio=0;
fila->fim=fila->inicio;
}
int Vazia(TipoFila fila){
return (fila.inicio==fila.fim);
}
int Insere(int elem, TipoFila *fila){
if (fila->fim == TAM_VET){
cout << "Fila cheia.";
return 0;
}
else{
fila->item[fila->fim]=elem;
fila->fim++;
return 1;
}
}
int Retira(TipoFila *fila, int *item){
if (Vazia(*fila)){
cout << "Fila Vazia.";
return 0;
}
*item=fila->item[fila->inicio];
fila->inicio++;
return 1;
}
int Imprime(TipoFila fila){
int aux;
if (Vazia(fila)){
cout << "Fila Vazia.";
return 0;
}
for (aux=fila.inicio;aux<fila.fim;aux++){
cout << fila.item[aux] << endl;
}
return 1;
}
27
Digite o Exemplo 4.2: Faça um programa que teste o TAD fila, 
inserindo os elementos 10, 20, 30, 40 e 50 e depois retirando um 
elemento para, logo em seguida, mostrar a listagem da fila.
// Programa para testar a TAD Fila atraves de Vetores
#include <conio.h>
#include "d:\aulas\aposti~1\lingua~1\fila.h"
int main(){
TipoFila f;
int elem;
clrscr();
Inicializa(&f);
elem=10;
Insere(elem,&f);
elem=20;
Insere(elem,&f);
elem=30;
Insere(elem,&f);
elem=40;
Insere(elem,&f);
elem=50;
Insere(elem,&f);
Retira(&f,&elem);
cout << "Elem. retirado = " << elem << endl;
Imprime(f);
getch();
}
28
6.2 Fila através de Ponteiros
Digite o Exemplo 4.3:- Faça um programa que mostre um menu de 
escolha para o usuário com as opções de inclusão, consulta e retirada 
de elementos em uma fila alocada dinamicamente
//Inclusao e consulta em uma lista
#include <iostream.h>
#include <conio.h>
#include <stdlib.h>
struct no{
no *prox;
int val;
};
void insere(no **i,no **f, int elem);
void consulta(no *i);
int retira(no **i);
int menu();
void main(){
no *inicio=NULL, *fim=NULL;
int opcao=0, elem;
while (opcao!=4){
opcao=menu();
switch (opcao){
case 1: cout << "Digite o valor a ser inserido: ";
cin >> elem;
insere(&inicio,&fim, elem);
break;
case 2: consulta(inicio);
break;
case 3: elem=retira(&inicio,&elem);
if (elem!=-1){
cout << elem;
}
getch();
break;
case 4: exit(1);
}
}
}
void consulta(no *i){
if (i==NULL){
cout << "Fila vazia";
}
else{
do{
cout << i->val << endl;
i=i->prox;
}while (i!=NULL);
}
getch();
}
void insere(no **i,no **f, int elem){
no *novo;
novo=(no *) malloc(sizeof(no));
novo->val=elem;
if ((*f)==NULL){
(*f)=(*i)=novo;
(*f)->prox=NULL;
}
else{
(*f)->prox=novo;
(*f)=novo;
(*f)->prox=NULL;
}
}
int retira(no **i, int *elem){
int elem;
if ((*i)==NULL){
return 0;
}
else{
*elem=(*i)->val;
(*i)=(*i)->prox;
return 1;
}
}
int menu(){
int op;
clrscr();
cout << "Fila" << endl;
cout << "1. Insere" << endl;
cout << "2. Consulta" << endl;
cout << "3. Retira" << endl;
cout << "4. Sai"<< endl;
cin >> op;
29
return op;
}
6.3 Exercícios
Fila através de Ponteiros
1. Faça um programa que controle o atendimento aos clientes em uma 
farmácia. O atendimento obedece uma fila organizada por ordem de 
chegada. O programa deve permitir a inclusão, consulta e atendimento de 
clientes na fila. As informações do cliente deve ser cic, nome e telefone.
30
7 Métodos de Classificação
7.1 Seleção Estrita
O método de seleção estrita compara o primeiro elemento com todos 
os demais, colocando em uma variável auxiliar o índice do valor menor. 
Terminando as comparações, o primeiro elemento deve ficar no lugar daquele 
de menor valor encontrado e vice-versa. O mesmo deve ser feito com o 
segundo elemento. O vetor só estará classificado quando o processo chegar 
ao último elemento do vetor. A tabela abaixo exemplifica o processo acima 
descrito.
Passo
Elementos do Vetor Índice do 
elemento 
selecionado (i)
Índice do 
menor 
(im)
0 1 2 3
Original 44 55 12 42 25 0 2
1 12 55 44 42 25 1 4
2 12 25 44 42 55 2 3
3 12 25 42 44 55 3 3
Fim 12 25 42 44 55
Veja abaixo a implementação da função do método de seleção direta.
void seleção_direta(int *v, int t)
{
 int im,aux, i, j;
 for(i=0;i<t-1;i++)
 {
 im=i;
 for(j=i+1;j<t;j++)
 {
 if(v[j]<v[im])
 {
 im=j;
 } // fim do if
 } // fim do for j
 aux=v[i];
 v[i]=v[im];v[im]=aux;
 } // fim do for i
} // fim da funcao seleção_direta
7.2 Troca - Bolha
31
O método de seleção por troca chamado Bolha compara dois 
elementos realizando a troca de suas posições caso o elemento da esquerda 
seja maior que o da direita. A verificação acontece em todo o vetor 
obedecendo a seqüência (0,1), (1,2), (2,3) …., (n-1,n). Esse processo ou 
interação deve se repetir até que nenhuma troca aconteça.
Interações Passo
Elementos do Vetor Índice do 
elemento da 
esquerda
Índice do 
elemento da 
direita
0 1 2
1
Original 44 55 12 42 25 0 1
1 44 55 12 42 25 1
2 44 12 55 42 25 2 3
3 44 12 42 55 25 3
4 44 12 42 25 55 0 1
2
1 12 44 42 25 55 1 2
2 12 42 44 25 55 2
3 12 42 25 44 55 3 4
4 12 42 25 44 55 0
3
1 12 42 25 44 55 1 2
2 12 25 42 44 55 2
3 12 25 42 44 55 3 4
4 12 25 42 44 55 0
4
1 12 25 42 44 55 1 2
2 12 25 42 44 55 2
3 12 25 42 44 55 3 4
4 12 25 42 44 55 Nenhuma 
troca - fim
Veja abaixo a implementação da função do método de troca “Bolha”.
void troca_bolha(int *v, int t)
{
 int i, aux, trocou=1;
 while(trocou==1)
 {
 trocou=0;
 for(i=0;i<t-1;i++)
 {
 if(v[i]<v[i+1])
 {
 aux=v[i];
 v[i]=v[i+1];
 v[i+1]=aux;
 trocou=1;
 } // fim do if
 } // fim do for i
 } // fim do while
} // fim da funcao troca_bolha
7.3 Troca – Quick Sort
Um grande número de aplicações se utiliza deste algorítmo devido a 
sua rapidez de execução. O algorítmo foi inventado por Hoare em 1960. Seu 
procedimento se baseia na máxima: “dividir para conquistar”. Assumindo que 
queiramos ordenar crescentemente uma lista, escolhemos um elemento 
qualquer para ser o “pivô”. Ele deve ser colocado na posição correta 
32
utilizando-se um algoritmo qualquer. Uma sugestão é contar o número de 
elementos que são menores que o pivô. Por exemplo, se há 5 elementos 
menores que o pivô, seu lugar será no índice 5 do vetor, sendo necessário 
realizar uma troca entre o pivô e o elemento que estiver na posição 5. Assim, 
a lista fica dividida em duas partes: direita e esquerda. Percorremos a parte 
esquerda comparando cada elemento com o elemento pivô, interrompendo a 
comparação quando encontrarmos um elemento maior que o pivô, o qual 
deveria estar do lado direito do pivô. Então percorremos o lado direito e 
executamos o mesmo procedimento, agora interrompendo a comparação 
quando o elemento for menor que o pivô, devendo estar do lado esquerdo do 
pivô. Com estes dois elementos em mãos, trocamos suas posições. 
Continuamos com este procedimento até que todos os elementos a esquerda 
do pivô sejam menores que ele e os elementos da direita sejam maiores que 
ele. Desta forma, podemos aplicar o mesmo procedimento para o vetor da 
esquerda e da direita, escolhendo um pivô para cada um deles, até que toda 
a lista esteja ordenada.
Veja o exemplo em que a lista que se quer classificar é composta dos 
elementos (44, 55, 12, 42, 25, 60, 20). O elemento escolhido para ser pivô é 
o primeiro (44). Há 4 elementos menores, portanto sua posição no vetor é a 
quinta, ou no índice 4.
Divisões
Elementos do Vetor
Índice do 
pivô
Índice da 
esquerda
Índice da 
direita0 1 2 3 4 5
Original 44 55 12 42 25 60 20 Valor do pivô escolhido = 44
Troca do pivô
Divisão 1
25 55 12 42 44 60 20 4 0 6
1
25 20 12 42 44 60 55 Lado esquerdo. Valor do novo pivô 
= 25
Troca do pivô
Divisão 2
12 20 25 42 44 60 55 2 0 3
2
12 20 25 42 44 60 55 Nenhuma troca. Valor do novo pivô 
= 12
Troca do pivô
Divisão 3
12 20 25 42 44 60 55 Com 2 elementos, na troca do pivô 
o lado já estará classificado.
3
12 20 25 42 44 60 55 Lado direito. Valor do novo pivô = 
60
Troca do pivô
Divisão 4
12 20 25 42 44 55 60 Com 2 elementos, na troca do pivô 
o lado já estará classificado.
Veja abaixo a implementação da função do método de troca 
“QuickSort”, retirada do livro de Niklaus Wirth.
#include <stdio.h> 
#include <stdlib.h>
#include <iostream.h>
#include <conio.h>
#define TAM 10
void sort(int L, int R)
{
 int i,j,w,x;
 i=L;
 j=R;
33
int a[TAM];
int k;
void sort(int L, int R); 
int main()
{ 
 for (k=0;k<TAM;k++) // digitacao dos elementos
 { 
 cout << "\n elemento " << k << " = ";
 cin >> a[k];
 }
 cout << "\n vetor = ";
 for (k=0;k<TAM;k++) // mostra o vetor digitado
 { 
 cout << a[k] << ",";
 } 
 getch();
 sort(0, TAM-1); // chama a classificacao
 cout << "\nVetor Classificado \n";
 for (k=0;k<TAM;k++) // mostra o vetor classificado
 { 
 cout << a[k] << ",";
 } 
 getch();
}
 x=a[(L+R)/2];
 
 do{
 while(a[i]<x){
 i++;
 } 
 while(x<a[j]){
 j--;
 }
 if(i<=j){
 w=a[i];
 a[i]=a[j];
 a[j]=w;
 i++;
 j--;
 }
 }while(i<=j);
 
 if(L<j){
 sort(L,j);
 }
 if(i<R){
 sort(i,R);
 }
}
7.4 Intercalação
Trata-se de intercalar dois vetores já classificados, formando um 
terceiro também classificado. A classificação dos dois vetores menores pode 
ser feita utilizando qualquer método.
A tabela abaixo demonstra o método de intercalação e, em seguida a 
implementação do mesmo.
Segmentos Elementos do Vetor
Vetor 1 12 55 57 63 71
Vetor 2 5 15 30 57
Vetor resultado 5 12 15 30 55 57 57 63 71
intercala(int *v1, int tv1, int *v2, int tv2, int *resultado)
{
 // tv1 e tv2 sao os tamanhos dos vetores
 int i, j, k, fim;
 i = j = k = fim = 0;
 while(k<tv1+tv2)
 { 
 if((i<tv1) && (j<tv2))
 {
 if(v1[i]<v2[j])
 else
 {
 if(i<tv1)
 {
 for(;i<tv1;i++)
 {
 resultado[k]=v1[i];
 k++;
 } // fim do for i
 } // fim do if
34
 {
 resultado[k]=v1[i];
 k++;
 resultado[k]=v2[j];
 k++;
 i++;
 j++;
 }
 else
 {
 resultado[k]=v2[j];
 k++;
 resultado[k]=v1[i];
 k++;
 j++;
 i++;
 } 
 }
 else
 {
 for(;j<tv2;j++)
 {
 resultado[k]=v2[j];
 k++;
 } // fim do for j
 } // fim do else
 } // fim do else
 } // fim do while
} // fim da funcao intercala
7.5 Inserção – Direta
Esse método considera 2 segmentos dentro do mesmo vetor, sendo o 
primeiro segmento formado apenas pelo primeiro elemento. Os demais elementos 
passam a fazer parte do primeiro segmento, quando, um a um são inseridos nele 
respeitando a ordem desejada. 
Na tabela abaixo, os números em azul pertencem ao primeiro segmento.
380 260 340 220 200 420 280 320 300
260 380 340 220 200 420 280 320 300
260 340 380 220 200 420 280 320 300
220 260 340 380 200 420 280 320 300
200 220 260 340 380 420 280 320 300
200 220 260 340 380 420 280 320 300
200 220 260 280 340 380 420 320 300
200 220 260 280 320 340 380 420 300
200 220 260 280 300 320 340 380 420
void insercao_direta(int *vet, int t)
{
 int i, j, k, aux; // i trabalha com o primeiro
 // segmento
 j=1; // j e o inicio do segundo segmento
 while(j<t)
 {
 for(i=0;i<j;i++)
 aux=vet[j];
 for(k=j;k>i;k--) // desloca elementos
 // para insercao
 {
 vet[k]=vet[k-1];
 }
 vet[i]=aux;
 }
35
 {
 if(vet[i]>vet[j]) // encontrou posição
 // para insercao
 {
 }
 j++;
 }
} // fim da funcao insercao_direta
7.6 Inserção - Shell
Também conhecido como classificação de incremento decrescente, 
esse método utiliza um incremento. Por exemplo, se tivermos um vetor com 
10 elementos e usarmos o incremento 4, as posições que serão ordenadas 
são (0,4,8), (1,5,9), (2,6), (3,7). Cada um desses conjuntos será classificado 
por inserção direta. Em seguida, o incremento a ser usado será o 2. Os 
conjuntos serão os seguintes: (0,2,4,6,8), (1,3,5,7,9). Após classificados, o 
incremento 1 deve ser usado, tratando todo o vetor como um único conjunto.
Uma sugestão para a escolha dos incrementosé f(x)=2x. Nessa 
função x deve variar de 0 até o número de incrementos que se deseja. Para 4 
incrementos temos (1,2,4,8).
A tabela abaixo exemplifica o método.
Incremento Vetor
4 25 57 48 12 3 10 5 20 40 30
2 3 10 5 12 25 30 48 20 40 57
1(inserção 
direta)
3 10 5 12 25 20 40 30 48 57
3 5 10 12 20 25 30 40 48 57
 
O programa do quadro abaixo implementa o método de classificação 
Shell usando a inserção direta para organizar os sub-vetores.
#include <stdio.h> 
#include <stdlib.h>
#include <conio.h>
#include <iostream.h>
#include <math.h>
void insercao_shell(int *vet, int t, int nincr);
#define TAM 13
#define X 2
int main()
void insercao_shell(int *vet, int t, int nincr)
{
 int i, j, k, aux, incr; // i trabalha com o
 // primeiro segmento
 do{
 incr=pow(2,nincr); // base 2 e expoente
 // nincr
 j=incr; // j e o inicio do segundo
 // segmento
36
{
 int vet[TAM];
 int i;
 clrscr();
 cout << "\n Digite 13 numeros";
 for (i=0;i<TAM;i++)
 { 
 cout << "\n Elemento " << i << " = ";
 cin >> vet[i];
 }
 cout << "\n O vetor digitado foi:";
 for (i=0;i<TAM;i++)
 { 
 cout << "\n Elemento " << i << " = " << 
vet[i]; 
 } 
 cout << "\n Tecle enter para continuar";
 getch();
 insercao_shell(vet,TAM,X);
 cout << "\n O vetor classificado e:";
 for (i=0;i<TAM;i++)
 { 
 cout << "\n Elemento " << i << " = " << 
vet[i]; 
 } 
 cout << "\n Tecle enter para continuar";
 getch();
}
 nincr--;
 while(j<t)
 {
 for(i=0;i<j;i=i+incr)
 {
 if(vet[i]>vet[j]) // encontrou posição
 // para insercao
 {
 aux=vet[j];
 for(k=j;k>i;k=k-incr) // desloca
 // elementos 
 {
 vet[k]=vet[k-incr];
 }
 vet[i]=aux;
 }
 }
 j=j+incr;
 }
 }while(nincr>=0);
} // fim da funcao insercao_shell
 
7.7 Distribuição – classificação por caixas
Esse método assume o índice de um vetor como sendo o valor do 
dado enquanto que o conteúdo do vetor deve conter o número de vezes que 
o dado ocorre. Para intervalos muito grandes, grandes espaços podem ser 
desperdiçados. Veja o exemplo abaixo classificando os valores 
(5,3,1,2,3,10,3,5,8,1):
Vetor com os valores de entrada.
5 3 1 2 3 10 3 5 8 1
Vetor de contadores. O índice representa os valores de entrada.
0 2 1 3 0 2 0 0 1 0 1
0 1 2 3 4 5 6 7 8 9 10
37
void distribuicao_caixa(int *vet, int t)
{
 int cont[50];
 int i,j;
 
 for(j=0;j<50;j++) // zerando contadores
 {
 cont[j]=0;
 }
 
 for(i=0;i<t;i++) // contando os valores
 // de entrada
 {
 cont[vet[i]]++;
 }
 i=0;
 for(j=0;j<50;j++) // remontando o vetor
 // classificado
 {
 while(cont[j]>0) 
 {
 vet[i]=j;
 cont[j]--;
 i++;
 }
 }
} // fim da funcao distribuicao_caixa
7.8 Distribuição – classificação por radicais (raízes, Radix)
O Radix sort permite a classificação de números e de textos, sendo 
que para a primeira o processo é iniciado pelo dígito menos significativo 
(unidade). Vamos trabalhar um exemplo de classificação numérica.
Para cada dígito utilizado na notação decimal (0 – 9), é gerada uma 
fila. Estas são alimentadas com base no resultado da análise dos números da 
lista a ser classificada.
Para a lista de valores (30, 125, 9, 23, 15, 18), analise o processo 
demonstrado na tabela abaixo.
Após a análise da unidade a lista de valores fica assim:
30, 23, 125, 15, 18, 9
Após a análise da dezena a lista de valores fica assim:
9, 15, 18, 23, 125, 30
Após a análise da centena a lista de valores fica assim:
9, 15, 18, 23, 30, 125
O processo termina porque o maior valor possui seu dígito mais 
significativo na casa da centena.
Dígito
Filas
0 1 2 3 4 5 6 7 8
Unidade
30 23 125 18 9
1
5
38
Dezena
09 15 23 30
18 12
5
Centena
009 125
015
018
023
030
Para implementação do processo demonstrado acima, é aconselhável 
o uso de fila com alocação dinâmica de memória.
7.9 Cálculo de Endereço (hashing)
Trata-se do cálculo do endereço de um elemento a partir do próprio 
valor da chave. A função que calcula esse endereço é chamada função de 
espalhamento. Quando duas chaves diferentes produzem o mesmo endereço, 
diz-se que aconteceu uma “colisão”. Como dois valores não podem ser 
guardados no mesmo espaço de memória, é preciso resolver esse problema 
produzindo outro endereço que esteja livre. Quem monta a função de 
espalhamento deve conhecer os dados com que vai trabalhar. A melhor 
função é a que mais espalha os dados, gerando menos colisão. Divisão, 
enlaçamento, extração, transformação de raiz e função meio-quadrado são 
alguns tipos de função de hashing. Alguns métodos de tratamento de colisão 
são: endereçamento em balde, encadeamento e endereçamento aberto.
O exemplo a seguir é bastante simples e pertence ao tipo “extração”, 
que trabalha com parte da chave. As colisões são tratadas usando o método 
de encadeamento.
Considere os seguintes dados de entrada: 20, 5, 3, 41, 23. O cálculo 
do endereço considera a casa da dezena do número digitado. Esse número é 
o endereço em um vetor de 0 a 9. As colisões são tratadas com uma lista 
ligada usando o método de inserção direta. No exemplo, acontecem duas 
colisões nos números 3 e 23. Cada um deve ser colocado no índice calculado, 
porém, em ordem crescente na lista gerada. Na verdade, o vetor é formado 
por 10 ponteiros para início de listas. Dependendo do volume de dados e da 
quantidade de dígitos que abrange, essa função não gera um bom 
espalhamento.
índice 0 1 2 3 4 5 6 7 8 9
valores 3 20 41
39
5 2
3
Observe o trecho de programa abaixo que implementa o exemplo de 
hashing demonstrado acima.
struct lista {
 int elem;
 lista* prox;
 };
lista* primeiros[10];
void insere(int num, lista *prim[])
{
 lista *novo, *anterior, *proximo;
 int i, achei;
 i=num%100;
 i=i/10; 
 novo=(lista*) malloc(sizeof(lista));
 novo->elem=num;
 if(prim[i]==NULL)
 {
 prim[i]=novo;
 prim[i]->prox=NULL;
 }
 else
 {
 if(num < prim[i]->elem)
 {
 novo->prox=prim[i];
 prim[i]=novo;
 }
 else
 { 
 achei=0;
 anterior=prim[i];
 proximo=prim[i]->prox;
 while(achei==0)
 {
 if(proximo==NULL)
 {
 anterior->prox=novo;
 novo->prox=NULL;
 achei=1;
 }
 else
 { 
 if(num<proximo->elem) 
 {
 novo->prox=proximo; 
 anterior->prox=novo;
 achei=1;
 }
 else 
 {
 anterior=proximo;
 proximo=proximo->prox; 
 }
 } 
 } // fim do while
 } 
 } 
} // fim do insere
40
8 Métodos de Busca
8.1 Definição
Só faz sentido guardar aquilo que se deseja usar. Tão importante 
quanto guardar uma informação é poder recuperá-la. Imagine aquela gaveta 
em que você guarda papéis com recados e telefones, recibos, 
correspondência bancária, cartinhas apaixonadas e só você sabe o que mais. 
Um dia, a vida de alguém depende de uma ligação sua e o número do 
telefone dessa pessoa está nessa gaveta. É bem provável que você encontre 
o papel desejado, mas não há garantias de que isso acontecerá antes do 
velório.
8.2 Método de Busca Linear ou Seqüencial
É o mais simples dos métodos de busca e é usado principalmente 
quando os dados não estão classificados. O algoritmo desse método é 
finalizado quando o que se deseja é encontrado ou quando se chega ao final 
da lista.
8.3 Método de Busca Binária
Esse método é aplicado em fontes de dados classificados. Consiste em 
dividir a lista de dados ao meio. Casoo que se busca não seja o elemento 
central, verifica-se se está antes ou depois dele. O procedimento deve ser 
repetido na metade escolhida. Veja o exemplo abaixo:
Valor procurado: 35
5 7 15 30 35 37 39 46 Valor é maior que o central
metade esquerda centro metade direita
5 7 15 30 35 37 39 46 Valor é menor que o central
descartados metade 
esquerda
centro metade 
direita
5 7 15 30 35 37 39 46 Só sobrou o próprio valor 
procurado
descartados achei descartados
Segue abaixo a implementação referente à pesquisa binária.
41
void pesquisa_binaria(int *v, int e, int t)
{
 int inicio,fim,meio;
 int achou=0;
 inicio=0;
 fim=t;
 while(achou==0)
 {
 meio=(fim-inicio)/2+inicio;
 if(v[meio]==e)
 {
 cout << "O elemento " << e << 
"esta na posicao " << meio;
 getch();
 achou=1;
 }
 
else
 {
 if(e<v[meio]) 
 {
 fim=meio-1;
 }
 else
 {
 inicio=meio+1;
 }
 }
 if(inicio>fim)
 {
 cout << "Elemento nao encontrado";
 getch();
 achou=1;
 } 
 } // fim do while 
}
8.4 Método de Busca Hashing
O método de busca hashing faz uso do cálculo de endereço através do 
qual a chave foi armazenada. Um exemplo desse método é discutido e 
exemplificado na seção 5.9.
42
9 Grafo
9.1 Definições
 Grafos são estruturas de dados versáteis que abrangem grande 
número de situações que as estruturas vistas até agora não conseguem 
representar. Para compreendermos o grafo é necessário que estejam claras 
as seguintes definições:
Vértice: também conhecido como nó, é graficamente representado 
por um círculo e em uma expressão pela letra V. 
Aresta: liga dois nós ou vértices. Graficamente é representada por 
uma reta e em uma expressão pela letra E (edges).
Grafo simples: é um conjunto não vazio de vértices e um conjunto 
que pode ser vazio de arestas.
Grafo completo: cada vértice deve estar ligado a todos os outros 
vértices por arestas. EG = V(2)G (conjunto de arestas do grafo G é igual ao 
conjunto dos pares não ordenados dos vértices do grafo G). G é um KN (G é 
um grafo completo).
Vértices adjacentes: são ligados pela mesma aresta.
43
Aresta incidente: é aquela que liga dois vértices adjacentes.
Grau de um vértice: o grau de um vértice V é o número de arestas 
incidentes com V. No exemplo abaixo, V tem grau 2.
Vértice isolado: é o vértice de grau zero ou sem arestas.
Caminho: o caminho de v1 a vn é uma sequência de arestas (v1,v2),
(v3,v4),...,(vn-1,vn). Pode ser escrito v1,v2,v3,v4,...,vn-1,vn.
Circuito: é quando o caminho tem início e fim no mesmo vértice.
Ciclo: é um circuito onde todos os vértices são diferentes.
(V,E): é o conjunto de vértices e de arestas de um grafo.
VG: é o conjunto de vértices do grafo G.
EG: é o conjunto de arestas do grafo G.
n(G): é número de vértices do grafo G.
m(G): é o número de arestas do grafo G.
n(G )≡∣VG∣ 
m(G )≡∣EG∣
VG
(2) : é o conjunto de todos os pares não ordenados do grafo G.
EG=φ : indica que o grafo G é vazio.
G é um Kn : indica que G é um grafo completo.
G é um K n : indica que G é um grafo vazio com n vértices.
 
A B
V
44
10 Árvores
10.1 Definições
Uma estrutura de dados em árvores tem sua organização semelhante 
a uma árvore (como seu próprio nome já diz), com sua raiz e folhas. A cada 
informação guardada na árvore chamamos de nó. Portanto, temos um único 
nó o qual podemos denominar “raiz”, sendo que, a partir dele podemos ter 
várias sub-árvores. Os nós de nivel inferior são chamados de nós filhos. 
Então, nós do mesmo pai são chamados de irmãos.
Na árvore acima, temos 15 nós, sendo que o nó A é a “raiz”, tendo o 
nó B, C e D como “filhos”. Chamamos os nós K, L, F, G, H, M e O de “folhas” 
ou “nós terminais” pois não tem filhos, e os nós com filhos chamamos de “nós 
não terminais”. O nó A tem “nível” 1, os nós B, C e D são de nível 2, e assim 
por diante. 
A
B C D
E F G H I J
K L M N
O
45
A implementação de uma árvore não é trivial, devido a sua 
flexibilidade na quantidade de filhos de um determinado nó. No entanto, 
podemos converter uma árvore em árvore binária.
10.2 Árvores Binárias
Uma Árvore Binária é uma árvore restrita. Nela, cada nó, não pode ter 
mais que dois filhos. Para converter uma Árvore em Árvore Binária, todos os 
irmãos de um respectivo nó estarão a sua direita e todos os seus filhos a 
esquerda. Assim,
A árvore binária acima é a conversão da árvore apresentada na na 
Ilustração 10.1. Para que possamos implementar esta árvore devemos criar 
um TAD contendo uma estrutura para nó: filho esquerdo, filho direito e 
informação. Algumas operações para manipular seus nós poderiam ser: 
Insere nó, Cria árvore e consulta nós.
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
46
Digite o exemplo 5.1:- Faça um TAD de uma arvore Binária com 
funções para Inserir e Consultar a árvore, assim como um programa 
que teste a TAD.
// TAD - Arvore Binaria
#include <iostream.h>
#include <stdlib.h>
#include <conio.h>
typedef struct No{
int info;
No *esq, *dir, *pai;
};
No *raiz;
No *CriaArv(int x){
No *p;
p=(No*) malloc(sizeof(No));
p->info=x;
p->esq=p->dir=p->pai=NULL;
return p;
}
void InsereDir(No *p, int x){
if (p==NULL){
cout << "Arvore Vazia";
}
else{
if (p->dir != NULL){
cout << "Insercao Incorreta";
}
else{
p->dir=CriaArv(x);
}
}
}
int Info(No *p){
if (p!=NULL){
return p->info;
}
}
No *FilhoEsq(No *p){
if (p!=NULL){
return p->esq;
}
}
No *FilhoDir(No *p){
if (p!=NULL){
return p->dir;
}
}
No *Pai(No *p){
if (p!=NULL){
return p->pai;
}
}
No *Irmao(No *p){
No *aux;
if (p!=NULL){
aux=p->pai;
if (aux==NULL){
return NULL; // p eh raiz
}
if (aux->esq==p){
return p->dir;
}
else{
return aux->esq;
}
}
}
void InsereEsq(No *p, int x){
if (p==NULL){
cout << "Arvore Vazia";
}
else{
if (p->esq != NULL){
cout << "Insercao Incorreta";
}
else{
p->esq=CriaArv(x);
}
}
}
void main(){
No *filho_esq,*filho_dir;
raiz=CriaArv(5);
InsereEsq(raiz,3);
InsereDir(raiz,7);
filho_esq=FilhoEsq(raiz);
filho_dir=FilhoDir(raiz);
InsereEsq(filho_esq,2);
InsereDir(filho_esq,4);
InsereEsq(filho_dir,6);
InsereDir(filho_dir,8);
clrscr();
cout << raiz->info << endl;
// filho_esq=raiz->esq;
// filho_dir=raiz->dir;
cout << filho_esq->info << endl;
cout << filho_dir->info << endl;
getch();
}
Toda organização e armazenamento tem um único objetivo: pesquisa. 
Estudaremos a seguir alguns métodos clássicos de percursos em árvore.
47
10.3 Percursos em Árvores Binárias
Existem alguns algoritmos clássicos para percorrer uma árvore. Todas 
elas se utilizam da técnica recursiva. A fim de estabelecer as regras dos 
percursos, assumiremos algumas convenções:
 E :- significa que percorreremos o galho esquerdo do nó 
em questão.
 P :- significa acessar (mostrar, consultar ou alterar) o nó.
 D :- significa que percorreremos o galho direito do nó em 
questão.
Através destas três convenções temos 6 combinações possíveis, no 
entanto, descreveremos as possibilidades quando a busca se iniciar pelo 
galho esquerdo (3 combinações).
 PED :- pre order
 EPD :- in order
 EDP :- pos order
Exemplo de percurso:
 PED :- A, B, E, K, L, C, F, G, D, H 
 EPD :- K, L, E, B, F, G, C, H, D, A
 EDP :- L, K, E, G, F, H, D, C, B, A
A
B
C
D
E
F
G
H
K
L
48
Abaixo nós apresentamos os algoritmos que permitem estes 
resultados.
void PreOrder(No *p){
if (p != NULL){
cout << p->elem;
PreOrder(p->esq);
PreOrder(p->dir);
} 
}
Digite o Exemplo 5.4:- Faça 
uma função que mostre os 
elementos de uma árvore 
binária pelo método pre order.
void InOrder(No *p){
if (p != NULL){
InOrder(p->esq);
cout << p->elem;
InOrder(p->dir);
} 
}
Digite o Exemplo 5.3:- Faça 
uma função que mostre os 
elementos de uma árvore 
binária pelo método pre order.
void PosOrder(No *p){
if (p != NULL){
PosOrder(p->esq);
PosOrder(p->dir);
cout << p->elem;
} 
}
Digite o Exemplo 5.5:-Faça 
uma função que mostre os 
elementos de uma árvorebinária pelo método pre order.
10.4 Árvores Binárias de Busca (ABB)
Este tipo de estrutura obedece as mesmas propriedades das Árvores 
Binárias. Porém, mais três propriedades devem ser observadas.
1. A informação do nó esquerdo deve ser menor que a informação 
do seu nó pai.
2. A informação do nó direito deve ser maior que a informação do 
seu nó pai.
3. Não existem informações repetidas.
Assim, se percorremos a ABB através do método in order, teremos 
uma lista ordenada das informações da árvore.
Exemplo de ABB.
49
A ABB é bastante apropriada para fazermos inserção, remoção e 
pesquisa, sempre tendo o cuidado de manter a ordenação da árvore.
Na inserção, basta verificar se o elemento a ser inserido é maior ou 
menor que o nó em questão, quando for maior percorre a sub-arvore direita, 
e quando for menor percorre a sub-arvore esquerda. O elemento é inserido 
quando não houver mais sub-arvore a percorrer, e caso seja igual, o 
elemento não pode ser inserido, pois não podemos inserir elementos 
repetidos em ABB.
Na busca também percorremos a sub-arvore direita e esquerda, 
dependendo do resultado da comparação, assim como na inserção, até 
encontrar o elemento procurado.
A remoção tem três casos a serem ponderados: nó sem filhos, nó com 
um filho (esquerdo ou direito) e nó com dois filhos. No primeiro caso, 
simplesmente removemos o nó (seu pai aponta para NULL). No segundo 
caso, fazemos o pai do nó a ser removido apontar para o filho do nó a ser 
removido, em seguida, removemos o nó. No terceiro caso, fazemos uma 
substituição do nó a ser removido pelo seu nó sucessor (nó mais a esquerda 
da sub-arvore direita do nó a ser removido) ou antecessor (nó mais a direita 
da sub-arvore esquerda do nó a ser removido). Ao substituirmos o nó, é 
A
D
F
I
J
E
G
H
B
C
K
50
preciso verificar em qual dos dois primeiros casos recaímos, pois o nó que irá 
substituir o nó removido pode ou não ter filhos (no caso, zero ou um filho).
Exemplo de inserção: na árvore do exemplo acima, os elementos 
foram inseridos na seguinte ordem: D, F, B, A, C, I, E, H, G, J, K. Agora 
iremos inserir o elemento L.
Exemplo de remoção de nó sem filhos (nó G), considerando a árvore 
acima.
Exemplo de remoção de nó com um filho (nó K), considerando a 
árvore acima.
A
D
F
I
J
E
G
H
B
C
K
L
A
D
F
I
J
E
H
B
C
K
L
51
Exemplo de remoção de nó com dois filhos (nó D), considerando a 
árvore acima.
A
D
F
I
J
E
H
B
C
L
A
E
F
I
J
H
B
C
L
52
#include <stdio.h>
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
struct No{
int info;
struct No *dir, *esq;
};
struct No *raiz;
void InsereABB(struct No **p, int elem){
if ((*p)==NULL){
(*p)= (struct No *) malloc(sizeof(struct No));
(*p)->info=elem;
(*p)->dir=(*p)->esq=NULL;
}
else{
if (elem > (*p)->info){
InsereABB(&(*p)->dir,elem);
}
else{
if (elem < (*p)->info){
InsereABB(&(*p)->esq,elem);
}
else{
printf("Elemento ja existe");
}
}
}
}
struct No *BuscaABB(struct No *p, int elem){
if (p!=NULL){
if (elem > p->info){
return BuscaABB(p->dir,elem);
}
else{
if (elem < p->info){
return BuscaABB(p->esq,elem);
}
else{
return p;
}
}
}
else{
return NULL;
}
}
Digite o exemplo 10.13:- 
Faça uma TAD de uma Arvore 
Binária de Busca (ABB). A 
informação de cada nó será um 
número inteiro. Deverá conter 
funções para inserir, remover e 
pesquisar cada nó, além de 
uma consulta geral mostrando 
as informações em ordem 
crescente.
struct No *Troca(struct No **p, struct No *sucessor)
{
struct No *aux;
if (sucessor->esq == NULL){
(*p)->info=sucessor->info;
aux=sucessor;
sucessor=sucessor->dir;
free(aux);
}
else{
Troca(&(*p),(*p)->esq);
}
}
void RemoveABB(struct No **p, int elem){
struct No *aux;
if ((*p)!=NULL){
if (elem > (*p)->info){
RemoveABB(&(*p)->dir,elem);
}
else{
if (elem < (*p)->info){
RemoveABB(&(*p)->esq,elem);
}
else{
if ((*p)->esq==NULL){
aux=(*p);
(*p)=(*p)->dir;
free(aux);
}
else{
if ((*p)->dir==NULL){
aux=(*p);
(*p)=(*p)->esq;
free(aux);
}
else{
Troca(&(*p),(*p)->dir);
}
}
}
}
}
53
else{
printf("Elemento nao existe");
}
}
void InOrder(struct No *p){
if (p!=NULL){
InOrder(p->esq);
printf("\n%d",p->info);
InOrder(p->dir);
}
}
#include "d:\aulas\aposti~1\lingua~1\abb.h"
int main(){
int op=1;
int inf;
struct No *p;
raiz=NULL;
while(op!=5){
printf("\nARVORE ABB\n\n");
printf("1. Insere na AB\n");
printf("2. Pesquisa na ABB\n");
printf("3. Remove na ABB\n");
printf("4. Lista ABB\n");
printf("5. Sai do programa\n");
scanf("%d",&op);
switch(op){
case 1:
printf("\nDigite inf. p/ insercao: ");
scanf("%d",&inf);
InsereABB(&raiz,inf);
break;
case 2:
printf("\nDigite inf. p/ pesquisa: ");
scanf("%d",&inf);
p = BuscaABB(raiz,inf);
if (p){
printf("\nElemento encontrado");
}
else{
printf("\nElemento nao encontrado");
}
break;
case 3:
printf("\nDigite inf. p/ remocao: ");
scanf("%d",&inf);
RemoveABB(&raiz,inf);
break;
case 4:
printf("\nLista ABB");
InOrder(raiz);
getch();
break;
}
}
} 
54
Digite o exemplo 10.14:- 
Faça um programa que inclua 
a TAD “ABB.h” e construa um 
menu de opções para testá-la.
10.5 Exercícios
Árvores Binárias
1. Faça uma função recursiva que devolva a quantidade de nós de uma Árvore Binária.
2. Faça uma função recursiva que devolva a quantidade de folhas de uma Árvore Binária.
3. Faça uma função recursiva que devolva o irmão de um elemento passado como 
parâmetro.
Árvores Binárias de Busca
4. Graficamente, construa uma ABB inserindo os seguintes nós.
a) 57, 39, 69, 90, 30, 15, 14, 70, 78, 81, 93,12
b) 5, 40, 52, 57, 89, 30, 51, 70, 2, 31
c) 27, 3, 0, 34, 23, 45, -8, 40, 76, 90, 13, 1
5. Remova os nós 39, 14, 93, 69 da ABB do exercício 4a
6. Remova os nós 30, 2, 5 do exercício 4b
7. Remova os nós 1, 0, 76, 27 do exercício 4c
8. Faça um programa que controle sua agenda de amigos. A agenda guarda as seguintes 
informações: nome e email. Permita, através de um menu de opções, que o usuário 
insira amigos, consulte por nome, remova amigos e liste todos eles. Utilize ABB para a 
implementação e uma TAD Agenda.h contendo a estrutura e as funções para 
manipulação das informações. 
	1 Introdução
	1.1 Construindo Estruturas Heterogêneas
	2 Recursão
	2.1 Introdução
	2.2 – Exercícios
	3 Ponteiro e Alocação dinâmica
	3.1 Vetores de Ponteiros
	3.2 Matrizes de Ponteiro
	1. Indireção Simples
	2. Indireção Múltipla
	3.3 Exercícios
	4 Listas
	4.1 Listas Através de Vetores
	4.2 Listas através de Ponteiros
	4.3 Exercícios
	5 Pilha
	5.1 Pilha através de Vetores
	5.2 Pilha através de Ponteiros
	5.3 Exercícios
	6 Fila
	6.1 Fila através de Vetores
	6.2 Fila através de Ponteiros
	6.3 Exercícios
	7 Métodos de Classificação
	7.1 Seleção Estrita
	7.2 Troca - Bolha
	7.3 Troca – Quick Sort
	7.4 Intercalação
	7.5 Inserção – Direta
	7.6 Inserção - Shell
	7.7 Distribuição – classificação por caixas
	7.8 Distribuição – classificação por radicais (raízes, Radix)
	7.9 Cálculo de Endereço (hashing)
	8 Métodos de Busca
	8.1 Definição
	8.2 Método de Busca Linear ou Seqüencial
	8.3 Método de Busca Binária
	8.4 Método de Busca Hashing
	9 Grafo
	9.1 Definições
	10 Árvores
	10.1 Definições
	10.2 Árvores Binárias
	10.3 Percursos em Árvores Binárias
	10.4 Árvores Binárias de Busca (ABB)
	10.5 Exercícios