Estruturas de Dados em C

Prévia do material em texto

Estruturas de Dados
Filippe jabour
IF Sudeste MG - Campus Juiz de Fora
Bacharelado em Sistemas de Informação
22 de novembro de 2011
http://www.jabour.com.br
Este material pode ser usado livremente, copiado ou distribuído, desde que citada a autoria.
Sumário
Lista de programas vi
Lista de figuras viii
1 Introdução 1
2 Matrizes 2
2.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2.2 Exemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2.3 Exercícios propostos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.3.1 Multiplicação de matriz por escalar . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.3.2 Multiplicação de matrizes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.3.3 Busca em vetor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
3 Funções 5
3.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3.2 Exemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
3.3 Exercícios propostos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.3.1 Aplicações de funções . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
4 Ponteiros 10
4.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
ii
SUMÁRIO iii
4.2 Exemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4.3 Exercícios propostos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4.3.1 Operações com números usando ponteiros . . . . . . . . . . . . . . . . . . . . . . 12
5 Alocação dinâmica de memória 13
5.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
5.2 Exemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
6 Estruturas 16
6.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
6.2 Exemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
6.3 Exercícios propostos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
6.3.1 Distância entre dois pontos, com estruturas . . . . . . . . . . . . . . . . . . . . . 17
6.3.2 Distância entre dois pontos, com estruturas e ponteiros . . . . . . . . . . . . . . . 18
6.3.3 Distância do ponto à reta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
6.3.4 Distância entre retas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
6.3.5 Representação de uma figura plana . . . . . . . . . . . . . . . . . . . . . . . . . . 18
7 Listas Encadeadas 19
7.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
7.2 Exemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
7.3 Exercícios propostos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
7.3.1 Inserção seletiva na lista encadeada . . . . . . . . . . . . . . . . . . . . . . . . . 21
7.3.2 Média dos elementos da lista encadeada . . . . . . . . . . . . . . . . . . . . . . . 21
7.3.3 Transferência de dados de uma lista para outra . . . . . . . . . . . . . . . . . . . 21
7.3.4 Criar e depois percorrer uma lista encadeada, inserindo dados em outra lista se-
gundo um escopo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
7.3.5 Mostrar valores de variáveis e ponteiros durante uma operação e descrever a operação 21
SUMÁRIO iv
7.3.6 Mostrar graficamente, passo a passo, o que ocorre na execução do programa . . . . 22
7.3.7 O que faz a função? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
7.3.8 Produto do primeiro elemento pelo último . . . . . . . . . . . . . . . . . . . . . . 23
7.3.9 Mostrar valores de variáveis e ponteiros durante uma operação . . . . . . . . . . . 24
7.3.10 Mostrar graficamente, passo a passo, o que ocorre na execução do programa . . . . 24
7.3.11 Busca e exclusão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
7.3.12 Média na lista . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
7.3.13 Mostrar valores de variáveis e ponteiros durante uma operação . . . . . . . . . . . 25
7.3.14 Concatenar listas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
7.3.15 Exibir os elementos das posições ímpares . . . . . . . . . . . . . . . . . . . . . . 26
7.3.16 Retirar e inserir segundo um escopo . . . . . . . . . . . . . . . . . . . . . . . . . 26
8 Pilhas 27
8.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
8.2 Exemplo gráfico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
8.3 Exemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
9 Filas 32
9.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
9.2 Exemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
9.3 Exercícios propostos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
9.3.1 Retira dois elementos da fila . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
9.3.2 Produto do 2o pelo último elemento da fila . . . . . . . . . . . . . . . . . . . . . 37
9.3.3 Concatenação de filas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
9.3.4 Roteador com 4 filas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
10 Recursividade 38
10.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
SUMÁRIO v
10.2 Exemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
10.3 Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
10.3.1 Soma dos números de 0 a n com recursividade . . . . . . . . . . . . . . . . . . . 44
10.3.2 Divisão com recursividade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
10.3.3 Soma dos elementos do vetor usando recursividade . . . . . . . . . . . . . . . . . 44
10.3.4 Contar números ímpares da lista encadeada usando recursividade . . . . . . . . . 44
10.4 Resposta dos Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
11 Árvores 49
11.1 Definições e representações básicas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
12 Árvores Binárias 51
12.1 Definições . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
12.2 Exemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
12.3 Percursos na árvore binária . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
12.3.1 Percurso em pré-ordem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
12.3.2 Percurso em ordem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
12.3.3 Percurso em pós-ordem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
12.3.4 Exemplo e implementação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
12.4 Árvores binárias de busca . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
13 Árvores AVL 66
13.1 Definições . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
13.2 Exemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . 67
Referências Bibliográficas 68
Lista de Programas
2.1 Soma de matrizes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
3.1 Função simples, sem argumento e sem retorno . . . . . . . . . . . . . . . . . . . . . . . . 5
3.2 Função que recebe e retorna valores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.3 Raízes da equação do segundo grau . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.4 Insere, busca e mostra dados de um vetor . . . . . . . . . . . . . . . . . . . . . . . . . . 8
4.1 Ponteiro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4.2 Ponteiro e ponteiro para ponteiro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
5.1 Alocação de memória, sizeof(), free() . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
6.1 Estrutura definindo um ponto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
6.2 Estrutura definindo uma reta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
7.1 Lista encadeada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
7.2 Lista encadeada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
7.3 Fragmento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
7.4 Código . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
8.1 Pilha . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
9.1 Fila01 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
10.1 Cálculo do fatorial com recursividade . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
10.2 Cálculo do fatorial com recursividade com mensagens . . . . . . . . . . . . . . . . . . . . 40
10.3 Lista encadeada com recursividade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
vi
LISTA DE PROGRAMAS vii
10.4 Soma recursiva . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
10.5 Divisão recursiva . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
10.6 Soma recursiva dos elementos do vetor . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
10.7 Conta os ímpares da lista encadeada com recursividade . . . . . . . . . . . . . . . . . . . 46
12.1 Criação e impressão de uma árvore binária . . . . . . . . . . . . . . . . . . . . . . . . . . 52
12.2 Árvore binária - inserção ordenada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
12.3 Percursos em árvores binárias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
12.4 Inserção na árvore binária, sem repetição . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
12.5 Árvore binária de busca . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
Lista de Figuras
11.1 Representação hierárquica de uma árvore . . . . . . . . . . . . . . . . . . . . . . . . . . 49
11.2 Análise de uma árvore . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
12.1 Árvore estritamente binária . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
12.2 Árvore binária completa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
12.3 Árvore binária cheia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
12.4 Percursos em árvores binárias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
13.1 Árvore AVL e não AVL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
viii
Capítulo 1
Introdução
N
otas de aula do professor Filippe Jabour para a disciplina Estrutura de Dados, do segundo período
do curso de Bacharelado em Sistemas de Informação do IF Sudeste MG - Campus Juiz de Fora.
Os exemplos são todos na linguagem C padrão e foram testados com o compilador gcc no sistema
operacional Linux.
Feito com o LATEX.
Alguns conceitos e técnicas que servem de embasamento para o estudo de estruturas de dados são
apresentados nos primeiros capítulos. No capítulo 2 mostramos brevemente este assunto. No capítulo 3 é
apresentada uma pequena revisão de funções. O capítulo 4 faz uma breve apresentação de ponteiros. A
alocação dinâmica de memória é vista no capítulo 5 e as estruturas no 6.
Após os conceitos preliminares, as estruturas de dados propriamente ditas são estudadas. No capítulo 7
vemos as listas encadeadas. No 8 as Pilhas. As filas são estudadas no capítulo 9.
A técnica de recursividade é apresentada no capítulo 10.
Capítulo 2
Matrizes
A gregados homogêneos de dados, com n dimensões.
2.1 Introdução
<tipo> <nome>[m][n];
Exemplo:
float matriz[4][4];
Matriz 4 x 4, de números reais.
matriz[0][0] refere-se ao elemento a11 da matriz.
matriz[2][3] refere-se quarto elemento da terceira linha (a34) da matriz.
2.2 Exemplos
Programa 2.1.
Programa 2.1: Soma de matrizes
1 /∗ s o m a m a t r i z e s . c − F i l i p p e Jabour − 2 6 / 2 / 2 0 0 7
2 Soma de m a t r i z e s
3 ∗ /
4
5 i n t main ( ) {
6
7 i n t i , j , k , ordem , m a t r i z 1 [ 1 0 ] [ 1 0 ] , m a t r i z 2 [ 1 0 ] [ 1 0 ] , ma t r i z soma [ 1 0 ] [ 1 0 ] ;
8
2.3 Exercícios propostos 3
9 p r i n t f ("\nPROGRAMA: LE DUAS MATRIZES BIDIMENSIONAIS E EFETUA A SOMA" ) ;
10 p r i n t f ("\nInforme a Ordem das Matrizes (de 1 a 10): " ) ;
11
12 s c a n f ("%i" , &ordem ) ;
13 i f ( ordem < 1 | ordem > 10 ) {
14 p r i n t f ("\n Erro na entrada de dados.\n" ) ;
15 re turn 2 ;
16 }
17
18 f o r ( i = 0 ; i < ordem ; i ++ ) {
19 p r i n t f ("\n\nMatriz 1" ) ;
20 p r i n t f ("\nLinha %i: " , i +1) ;
21 f o r ( j = 0 ; j <ordem ; j ++ )
22 s c a n f ("\t%i" ,& m a t r i z 1 [ i ] [ j ] ) ;
23 }
24
25 f o r ( i = 0 ; i < ordem ; i ++ ) {
26 p r i n t f ("\n\nMatriz 2" ) ;
27 p r i n t f ("\nLinha %i: " , i +1) ;
28 f o r ( j = 0 ; j <ordem ; j ++ )
29 s c a n f ("\t%i" ,& m a t r i z 2 [ i ] [ j ] ) ;
30 }
31
32 f o r ( i = 0 ; i < ordem ; i ++ ) {
33 f o r ( j = 0 ; j < ordem ; j ++ )
34 mat r i z soma [ i ] [ j ] = m a t r i z 1 [ i ] [ j ] + m a t r i z 2 [ i ] [ j ] ;
35 }
36
37 p r i n t f ("\n\n Matriz soma" ) ;
38 f o r ( i = 0 ; i < ordem ; i ++ ) {
39 p r i n t f ("\n" ) ;
40 f o r ( j = 0 ; j < ordem ; j ++ )
41 p r i n t f ("\t%d" , ma t r i z soma [ i ] [ j ] ) ;
42 }
43 p r i n t f ("\n" ) ;
44
45 }
2.3 Exercícios propostos
2.3.1 Multiplicação de matriz por escalar
Fazer um programa que multiplique uma matriz por um escalar.
2.3 Exercícios propostos 4
2.3.2 Multiplicação de matrizes
Fazer um programa de multiplicação de matrizes.
2.3.3 Busca em vetor
Fazer um programa que procure e exiba o valor e a posição do maior e do menor elemento de um vetor.
Capítulo 3
Funções
M uitas linguagens de programação permitem a chamada a funções e procedimentos.
3.1 Introdução
A função é como um apelido de um trecho de código. No ponto onde está a chamada à função, o fluxo
de execução do programa se desvia para a função invocada e ela é executada. Em algum momento, em
condições normais, o fluxo de execução retorna à função que a chamou. Vendo por outro ângulo, podemos
pensar como se o código da função fosse inserido no lugar da linha que a chama.
Uma vantagem interessante é que, depois de criada, uma função pode ser usada, ou chamada, inúmeras
vezes. Outra vantagem é que, se for preciso dar manutenção no código, basta modificar a função que esta
melhoria ou correção se refletirá em todos os pontos onde a mesma é chamada.
3.2 Exemplos
No programa 3.1, a função criada é muito simples. Não recebenada como argumento. Por isto, não tem
nada nos parênteses em frente ao seu nome (nem na chamada nem na declaração da função). A função não
retorna ou não devolve nenhum valor. Por isto o tipo de retorno é void (palavra que fica antes do nome da
função na declaração). Assim temos a seguinte regra sintática no C:
Tipo_que_a_função_retorna Nome_da_Função ( argumentos_que_a_função_recebe )
Programa 3.1: Função simples, sem argumento e sem retorno
3.2 Exemplos 6
1 /∗ f uncao1 . c − F i l i p p e Jabour − 7 / 8 / 2 0 0 6
2 Chamada de fu nçã o sem r e t o r n o e sem passagem de p a r â m e t r o s
3 ∗ /
4
5 void imprimemsglernum ( ) {
6 p r i n t f ("\n===============================" ) ;
7 p r i n t f ("\nDigite um número" ) ;
8 p r i n t f ("\n===============================> " ) ;
9 }
10
11 i n t main ( ) {
12 f l o a t a , b , c , media ;
13 imprimemsglernum ( ) ;
14 s c a n f ("%f" ,&a ) ;
15 imprimemsglernum ( ) ;
16 s c a n f ("%f" ,&b ) ;
17 imprimemsglernum ( ) ;
18 s c a n f ("%f" ,&c ) ;
19 p r i n t f ("Você digitou %f, %f e %f.\n" , a , b , c ) ;
20 }
No programa 3.2, a função calculaMedia recebe 3 argumentos do tipo float e retorna um valor deste
mesmo tipo.
Programa 3.2: Função que recebe e retorna valores
1 /∗ f uncao2 . c − F i l i p p e Jabour − 7 / 8 / 2 0 0 6
2 Chamada de fu nçã o com r e t o r n o e com passagem de p a r â m e t r o s
3 ∗ /
4
5 void imprimemsglernum ( ) {
6 p r i n t f ("\n===============================" ) ;
7 p r i n t f ("\nDigite um número" ) ;
8 p r i n t f ("\n===============================> " ) ;
9 }
10
11 f l o a t c a l c u l a M e d i a ( f l o a t arg_a , f l o a t arg_b , f l o a t a r g _ c ) {
12 f l o a t r e s u l t a d o = ( a r g _ a + arg_b + a r g _ c ) / 3 ;
13 re turn ( r e s u l t a d o ) ;
14 }
15
16 i n t main ( ) {
17 f l o a t a , b , c , media ;
18 imprimemsglernum ( ) ;
19 s c a n f ("%f" ,&a ) ;
20 imprimemsglernum ( ) ;
21 s c a n f ("%f" ,&b ) ;
22 imprimemsglernum ( ) ;
3.2 Exemplos 7
23 s c a n f ("%f" ,&c ) ;
24 media = c a l c u l a M e d i a ( a , b , c ) ;
25 p r i n t f ("A média entre %f, %f e %f é %f.\n" , a , b , c , media ) ;
26 }
No programa 3.3 temos mais exemplos de chamada de funções.
Programa 3.3: Raízes da equação do segundo grau
1 /∗ f uncao3 . c − F i l i p p e Jabour − 8 / 8 / 2 0 0 6
2 Chamada de fu nçã o
3 C á l c u l o das r a í z e s da equação do segundo grau
4 Compi lar com gcc funcao3 . c −lm
5 ∗ /
6
7 # i n c l u d e <math . h>
8
9 f l o a t c a l c u l a D e l t a ( f l o a t a , f l o a t b , f l o a t c ) {
10 f l o a t d e l t a = b ∗ b − 4 ∗ a ∗ c ;
11 re turn ( d e l t a ) ;
12 }
13
14 f l o a t c a l c u l a R 1 ( f l o a t a , f l o a t b , f l o a t d e l t a ) {
15 f l o a t r1 = ( −1 ∗ b + s q r t f ( d e l t a ) ) / (2 ∗ a ) ;
16 re turn ( r1 ) ;
17 }
18
19 f l o a t c a l c u l a R 2 ( f l o a t a , f l o a t b , f l o a t d e l t a ) {
20 f l o a t r2 = ( −1 ∗ b − s q r t f ( d e l t a ) ) / (2 ∗ a ) ;
21 re turn ( r2 ) ;
22 }
23
24 i n t v a l i d a D e l t a ( f l o a t a , f l o a t b , f l o a t c ) {
25 f l o a t d e l t a = b ∗ b − 4 ∗ a ∗ c ;
26 i f ( d e l t a >= 0 )
27 re turn ( 1 ) ;
28 e l s e
29 re turn ( 0 ) ;
30 }
31
32 i n t main ( ) {
33 f l o a t a , b , c , d e l t a , r1 , r2 ;
34 p r i n t f ("Digite os coeficientes da equação do segundo grau.\n" ) ;
35 p r i n t f ("a X2 + b X + c\n" ) ;
36 p r i n t f ("a = " ) ;
37 s c a n f ("%f" ,&a ) ;
38 p r i n t f ("b = " ) ;
39 s c a n f ("%f" ,&b ) ;
3.2 Exemplos 8
40 p r i n t f ("c = " ) ;
41 s c a n f ("%f" ,&c ) ;
42 i f ( a == 0) {
43 p r i n t f ("Coeficiente \"a\" nao pode ser nulo.\n" ) ;
44 re turn ( 0 ) ;
45 }
46 i f ( v a l i d a D e l t a ( a , b , c ) ) {
47 d e l t a = c a l c u l a D e l t a ( a , b , c ) ;
48 p r i n t f ("Delta = %f.\n" , d e l t a ) ;
49 r1 = c a l c u l a R 1 ( a , b , d e l t a ) ;
50 p r i n t f ("R1 = %f.\n" , r 1 ) ;
51 r2 = c a l c u l a R 2 ( a , b , d e l t a ) ;
52 p r i n t f ("R2 = %f.\n" , r 2 ) ;
53 }
54 e l s e
55 p r i n t f ("A equação não possui raízes reais\n" ) ;
56 }
No programa 3.4 temos mais exemplos de chamada de funções, manipulando dados em um vetor.
Programa 3.4: Insere, busca e mostra dados de um vetor
1 /∗ f u n c a o c o m v e t o r . c − F i l i p p e Jabour − 8 / 8 / 2 0 0 6
2 Chamada de fu nçã o com uso de v e t o r
3 ∗ /
4
5 i n t v e t o r [ 1 0 2 4 ] ;
6
7 void i n s e r e ( i n t e lemento , i n t p o s i c a o ) {
8 v e t o r [ p o s i c a o ] = e l e m e n t o ;
9 }
10
11 void menu ( ) {
12 p r i n t f ("\n+-----------------------------------------------+\n" ) ;
13 p r i n t f ("| 1-Inclui 2-Procura 3-Mostra Todos 4-Sai |\n" ) ;
14 p r i n t f ("+-----------------------------------------------+\n" ) ;
15 p r i n t f (" Digite a sua opcao: " ) ;
16 }
17
18 i n t busca ( i n t e lemento , i n t p o s i c a o ) {
19 i n t i ;
20 f o r ( i = 0 ; i < p o s i c a o ; i ++ ) {
21 i f ( v e t o r [ i ] == e l e m e n t o )
22 re turn ( i ) ;
23 }
24 re turn (−1) ;
25 }
26
3.3 Exercícios propostos 9
27 void m o s t r a t o d o s ( i n t p o s i c a o ) {
28 i n t i ;
29 f o r ( i = 0 ; i < p o s i c a o ; i ++ )
30 p r i n t f (" vetor[%d] = %d\n" , i , v e t o r [ i ] ) ;
31 }
32
33
34 i n t main ( ) {
35 i n t e lemento , p o s i c a o = 0 , i , opcao = 0 , r e s u l t a d o ;
36 whi le ( opcao != 4 ) {
37 menu ( ) ;
38 s c a n f ("%d" ,& opcao ) ;
39 sw i t ch ( opcao ) {
40 case 1 :
41 p r i n t f ("\n Digite o numero a ser incluido: " ) ;
42 s c a n f ("%d" ,& e l e m e n t o ) ;
43 i n s e r e ( e lemento , p o s i c a o ++) ;
44 break ;
45 case 2 :
46 p r i n t f ("\n Digite o numero a ser procurado: " ) ;
47 s c a n f ("%d" ,& e l e m e n t o ) ;
48 r e s u l t a d o = busca ( e lemento , p o s i c a o ) ;
49 i f ( r e s u l t a d o != −1 )
50 p r i n t f ("\n Elemento encontrado na posicao %d do
vetor." , r e s u l t a d o ) ;
51 e l s e
52 p r i n t f ("\n Elemento nao encontrado." ) ;
53 break ;
54 case 3 :
55 m o s t r a t o d o s ( p o s i c a o ) ;
56 }
57 }
58 }
3.3 Exercícios propostos
3.3.1 Aplicações de funções
Refaça os exercícios 2.3.1, 2.3.2 e 2.3.3 usando funções sempre que necessário.
Capítulo 4
Ponteiros
4.1 Introdução
V
a riáveis têm endereços de memória. Variáveis têm tipo como int, float, char etc. A definição do tipo
da variável existe para que o compilador “saiba” o tamanho de memória a ser alocada (ou reservada)
para gravar os valores que esta variável assumirá durante a execução do programa.
A sentença int x = 10; carrega as seguintes informações:
• x é inteiro
• x retorna o que está no endereço de x, ou seja, em int y = x; , y receberá 10.
• &x retorna o endereço de x, que é um endereço de memória. Em scanf(“%f”,&a); , a função scanf
receberá um valor digitado e gravará no endereço de a.
Muitas linguagens de programação possuem o tipo ponteiro. Uma variável do tipo ponteiro, como
toda variável, armazena um valor. No caso do ponteiro, o valor armazenado é um endereço de memória.
Em C, usa-se o caracter * para informar que a variável é um ponteiro.
A sentença int *p; carrega as seguintes informações:
• p é um ponteiro para inteiro
• p retorna um endereço de memória onde está gravado um inteiro
• *p retorna o que está no endereço para o qual p aponta, que é um inteiro
4.2 Exemplos 11
4.2 Exemplos
Antes que você se desespere e vá para a cantina, vamos aos exemplos.
Programa 4.1: Ponteiro
1 /∗ p o n t e i r o 1 . c − F i l i p p e Jabour − 1 3 /8 / 2 0 0 6
2 P o n t e i r o s
3 ∗ /
4
5 i n t main ( ) {
6 i n t x , y , z , k , ∗p , ∗q ;
7 x = 1 0 ;
8 y = 2 0 ;
9 p r i n t f ("\np = &x , ou seja, p aponta para x\n" ) ;
10 p = &x ;
11 p r i n t f ("q = &y , ou seja, q aponta para y\n" ) ;
12 q = &y ;
13 p r i n t f ("z = *p + *q\n" ) ;
14 z = ∗p + ∗q ;
15 p r i n t f ("z = %d\n" , z ) ;
16 p r i n t f ("k = x + y\n" ) ;
17 k = x + y ;
18 p r i n t f ("k = %d\n" , k ) ;
19 }
Outro exemplo do professor Jabour.
Programa 4.2: Ponteiro e ponteiro para ponteiro
1 /∗ p o n t e i r o 2 . c − F i l i p p e Jabour − 1 3 / 8 / 2 0 0 6
2 P o n t e i r o s
3 ∗ /
4
5 # i n c l u d e < s t d i o . h>
6
7 i n t main ( ) {
8 i n t x , ∗p , ∗∗q ;
9 x = 1 0 ;
10 p = &x ;
11 q = &p ;
12 p r i n t f ("Codigo:\nint x, *p, **q;\nx = 10;\np = &x;\nq = &p;\n\n" ) ;
13 p r i n t f ("q = %p \n" , q ) ;
14 p r i n t f ("**q = %d \n\n" ,∗∗q ) ;
15 p r i n t f ("&p = %p \n" ,&p ) ;
16 p r i n t f ("p = %p \n" , p ) ;
17 p r i n t f ("*p = %d \n\n" ,∗ p ) ;
18 p r i n t f ("x = %d \n" , x ) ;
19 p r i n t f ("&x = %p \n\n" ,&x ) ;
4.3 Exercícios propostos 12
20 p r i n t f ("x é inteiro, assim x retorna o que está no endereço de x, que é um
inteiro.\n&x retorna o endereço de x, que é um endereço de memória\n" ) ;
21 p r i n t f ("p é ponteiro, assim p retorna o que está no endereço de p, que é um
endereço, e é o endereço de x;\n *p retorna o que está no endereço para o
qual p aponta, que é o que está no endereço de x, que é 10;\n &x é o
endereço de x, que é o que está em p.\nObserve que:\nq = &p ; p = &x ; **q =
*p = x.\nPonteiro é um endereço e variável TEM um endereço.\n\n" ) ;
22 }
4.3 Exercícios propostos
4.3.1 Operações com números usando ponteiros
Faça um programa que calcula e exibe a média entre 3 números. Use apenas ponteiros, ou seja, não
pode usar diretamente (a+ b+ c)/3.
Capítulo 5
Alocação dinâmica de memória
5.1 Introdução
E
m C é possível solicitar, requisitar ou alocar memória durante a execução do programa. A aplicação
está nas situações em que não sabemos a dimensão ou quantidade de memória que serão necessários
durante a execução do programa. A partir do capítulo 7, na parte de Estruturas de Dados propriamente dita,
ficará clara a motivação do uso de alocação dinâmica.
Esta alocação em tempo de execução se chama alocação dinâmica. Ela é feita através da função mal-
loc da biblioteca stdlib.h.
void* malloc (unsigned int num);
A função malloc recebe o número de bytes a serem alocados (num) e retorna um ponteiro para void que
aponta para o primeiro byte desta área de memória ou retorna NULL se a alocação não teve sucesso.
A função free() libera a memória alocada. free(v) libera a área para onde v aponta.
A função sizeof retorna o tamanho de uma variável, ou seja, quanta memória um tipo (int, float, double,
etc) ocupa na memória. Ela é útil para ser usada como argumento da função malloc. Assim, alocaremos
exatamente o espaço necessário para gravar o valor da variável. Veja como se faz:
ponteiro = malloc(sizeof(float));
Como vimos, a função malloc retorna ou devolve um ponteiro para void. Para gravar e manipular
outros tipos no endereço alocado, temos que converter o tipo retornado. Em C, podemos fazer a chamada
conversão explícita de tipo, ou type cast. Para isto, devemos colocar antes da expressão a ser convertida,
o novo tipo entre parênteses.
5.2 Exemplos 14
int *ponteiro;
ponteiro = (int*)malloc(sizeof(int));
Em caso de falha na alocação de memória, a função malloc retornará NULL. Deste modo, basta com-
parar o ponteiro com NULL após a tentativa de alocação e verificar se houve sucesso:
if (ponteiro) { . . . }
ou
if (ponteiro != NULL) { . . . }
Os dois trechos acima têm o mesmo efeito.
5.2 Exemplos
Programa 5.1: Alocação de memória, sizeof(), free()
1 /∗ AlocaMemoria . c − F i l i p p e Jabour − 1 0 / 0 9 / 2 0 0 6
2 Alocação de Memória , mal loc , s i z e o f , f r e e , t y p e c a s t
3 ∗ /
4
5 i n t main ( ) {
6 void ∗pontParaVoidUm , ∗ p o n t P a r a V o i d D o i s ;
7 f l o a t ∗ p o n t P a r a F l o a t ;
8 double ∗ p o n t P a r a D o u b l e ;
9
10 pontParaVoidUm = ma l l oc ( 4 ) ;
11 i f ( ! pontParaVoidUm )
12 p r i n t f ("\nFalha ao alocar memória para pontParaVoidUm.\n\n" ) ;
13 e l s e
14 p r i n t f ("\n\npontParaVoidUm aponta para 4 bytes alocados.\nEsta area de
memoria comeca no endereco %p\n\n" , pontParaVoidUm ) ;
15
16 p o n t P a r a V o i d D o i s = ma l lo c ( 4 0 ) ;
17 i f ( ! p o n t P a r a V o i d D o i s )
18 p r i n t f ("\nFalha ao alocar memoria para pontParaVoidDois.\n\n" ) ;
19 e l s e
20 p r i n t f ("\n\npontParaVoidDois aponta para 40 bytes alocados.\nEsta area
de memoria comeca no endereco %p\n\n" , p o n t P a r a V o i d D o i s ) ;
21
22 p r i n t f ("\n\n\tA funcao sizeof()" ) ;
23 p r i n t f ("\nUm real (float) ocupa %u bytes na memoria." , s i z e o f ( f l o a t ) ) ;
24 p r i n t f ("\nUm real de dupla precisao (double) ocupa %u bytes na memoria." , s i z e o f (
double ) ) ;
25 p r i n t f ("\nUm caracter (char) ocupa %u byte na memoria." , s i z e o f ( char ) ) ;
5.2 Exemplos 15
26
27 p o n t P a r a F l o a t = ( f l o a t ∗ ) m a l lo c ( s i z e o f ( f l o a t ) ) ;
28 i f ( ! p o n t P a r a F l o a t )
29 p r i n t f ("\nFalha ao alocar memoria para pontParaFloat.\n\n" ) ;
30 e l s e {
31 p r i n t f ("\n\npontParaFloat aponta para %u bytes alocados.\nEsta area de
memoria comeca no endereco %p\n\n" , s i z e o f ( f l o a t ) , p o n t P a r a F l o a t ) ;
32 ∗ p o n t P a r a F l o a t = 3 . 1 4 ;
33 p r i n t f ("\nGravamos o valor %f no endereco para onde pontParaFloat aponta
" ,∗ p o n t P a r a F l o a t ) ;
34 }
35
36 p o n t P a r a D o u b l e = ( double ∗ ) m a l lo c ( s i z e o f ( double ) ) ;
37 i f ( ! p o n t P a r a D o u b l e )
38 p r i n t f ("\nFalha ao alocar memoria para pontParaDouble.\n\n" ) ;
39 e l s e {
40 p r i n t f ("\n\npontParaDouble aponta para %u bytes alocados.\nEsta area de
memoria comeca no endereco %p\n\n" , s i z e o f ( double ) , p o n t P a r a D o u b l e ) ;
41 ∗ p o n t P a r a D o u b l e = ∗ p o n t P a r a F l o a t ∗ 2 ;
42 p r i n t f ("\nO endereco para onde pontParaDouble aponta recebeu o dobro do
valor\nque esta\’ no endereco para onde *pontParaFloat aponta. Seu
valor e\’: %lf\n\n" ,∗ p o n t P a r a D o u b l e ) ;
43 }
44
45 f r e e ( pontParaVoidUm ) ;
46 f r e e ( p o n t P a r a V o i d D o i s ) ;
47 f r e e ( p o n t P a r a F l o a t ) ;
48 f r e e ( p o n t P a r a D o u b l e ) ;
49
50 }
Capítulo 6
Estruturas
6.1 Introdução
E
s truturas são objetos que contém dados mais simples em seu interior. Quando definimos uma estru-
tura, criamos um novo tipo de dado (como uma classe de coisas). Podemos então ter várias variáveis
deste tipo (que seriam vários objetos desta classe de dados).
6.2 Exemplos
Programa 6.1: Estrutura definindo um ponto
1 # i n c l u d e < s t d i o . h>
2
3 /∗ e s t r u t u r a s 1 . c − F i l i p p e Jabour − 2 1 / 8 / 2 0 0 6
4 E s t r u t u r a s
5 ∗ /
6
7 i n t main ( ) {
8
9 s t r u c t PontoNoPlano {
10 f l o a t x ;
11 f l o a t y ;
12 } ;
13
14 s t r u c t PontoNoPlano ponto_A ;
15
16 p r i n t f ("Informe as coordenadas: \n" ) ;
17 p r i n t f ("\tx = " ) ;
18 s c a n f ("%f" ,& ponto_A . x ) ;
6.3 Exercícios propostos 17
19 p r i n t f ("\ty = " ) ;
20 s c a n f ("%f" ,& ponto_A . y ) ;
21 p r i n t f ("As coordenadas são %f , %f \n" , ponto_A . x , ponto_A . y ) ;
22 }
Programa 6.2: Estrutura definindo uma reta
1 # i n c l u d e < s t d i o . h>
2
3 /∗ e s t r u t u r a s 2 . c − F i l i p p eJabour − 2 1 / 8 / 2 0 0 6
4 E s t r u t u r a s
5 ∗ /
6
7 i n t main ( ) {
8
9 s t r u c t PontoNoPlano {
10 f l o a t x ;
11 f l o a t y ;
12 } ;
13
14 s t r u c t Reta {
15 s t r u c t PontoNoPlano a , b ;
16 } retaUm ;
17
18 p r i n t f ("Informe as coordenadas do primeiro ponto: \n" ) ;
19 p r i n t f ("\tx = " ) ;
20 s c a n f ("%f" ,& retaUm . a . x ) ;
21 p r i n t f ("\ty = " ) ;
22 s c a n f ("%f" ,& retaUm . a . y ) ;
23
24 p r i n t f ("Informe as coordenadas do segundo ponto: \n" ) ;
25 p r i n t f ("\tx = " ) ;
26 s c a n f ("%f" ,& retaUm . b . x ) ;
27 p r i n t f ("\ty = " ) ;
28 s c a n f ("%f" ,& retaUm . b . y ) ;
29
30 p r i n t f ("A reta é definida pelos pontos A (%.2f,%.2f) e B (%.2f,%.2f) \n" , retaUm .
a . x , retaUm . a . y , retaUm . b . x , retaUm . b . y ) ;
31 }
6.3 Exercícios propostos
6.3.1 Distância entre dois pontos, com estruturas
Faça um programa que calcule a distância entre dois pontos. Represente cada ponto como uma estrutura.
6.3 Exercícios propostos 18
6.3.2 Distância entre dois pontos, com estruturas e ponteiros
Faça um programa que calcule a distância entre dois pontos. Represente cada ponto como uma estrutura.
Referencie as estruturas com ponteiros para estruturas.
6.3.3 Distância do ponto à reta
Faça um programa que calcule a distância de um ponto a uma reta. Represente cada ponto como uma
estrutura. Represente a reta como uma estrutura formada por duas estruturas do tipo ponto.
6.3.4 Distância entre retas
Faça um programa que calcule a distância entre duas retas. Represente cada ponto como uma estrutura.
Represente a reta como uma estrutura formada por duas estruturas do tipo ponto.
6.3.5 Representação de uma figura plana
Faça um programa que represente uma figura plana da seguinte forma: os vértices são pontos represen-
tados por estruturas; as arestas são representadas por ponteiros de um ponto (vértice (estrutura)) para outro
(o próximo).
Capítulo 7
Listas Encadeadas
7.1 Introdução
E
s truturas como vetores tem sua dimensão, ou tamanho, definida em tempo de compilação, ou seja,
definida quando criamos o programa. Existe uma forma mais flexível para criar estruturas de dados
que cresçam conforme precisamos armazenar mais elementos e diminuam quando liberamos ou retiramos
estes elementos. Isto é feito com o uso de ponteiros (capítulo 4), alocação dinâmica de memória (capítulo
5) e estruturas (capítulo 6). São as chamadas Listas Encadeadas.
7.2 Exemplos
Programa 7.1: Lista encadeada
1 /∗ l i s t a E n c a d e a d a 1 − F i l i p p e Jabour − 2 3 / 8 / 2 0 0 6
2 L i s t a Encadeada , sem f u n ç õ e s , i n s e r ç ã o e e x i b i ç ã o de dados
3 ∗ /
4
5 # i n c l u d e < s t d i o . h>
6 # i n c l u d e < s t d l i b . h>
7
8 s t r u c t TipoNota {
9 f l o a t n o t a ;
10 i n t numChamada ;
11 s t r u c t TipoNota ∗proximo ;
12 } ;
13
14 t y p e d e f s t r u c t TipoNota Nota ;
15
16 i n t main ( ) {
7.2 Exemplos 20
17
18 f l o a t auxNota = 0 ;
19 i n t auxNumChamada = 0 ;
20 Nota ∗ b o l e t i m , ∗novoNo ;
21 b o l e t i m = NULL;
22
23 p r i n t f ("Digite o numero de chamada (-999 para encerrar) e em seguida a nota" ) ;
24
25 whi le ( auxNumChamada != −999) {
26 p r i n t f ("\nNumero de chamada: " ) ;
27 s c a n f ("%d" ,&auxNumChamada ) ;
28 i f ( auxNumChamada != −999) {
29 p r i n t f (" Nota: " ) ;
30 s c a n f ("%f" ,& auxNota ) ;
31 novoNo = ( Nota ∗ ) ( m a l loc ( s i z e o f ( Nota ) ) ) ;
32 i f ( ! novoNo )
33 p r i n t f ("\nFalha de alocação de memória." ) ;
34 e l s e {
35 novoNo−>n o t a = auxNota ;
36 novoNo−>numChamada = auxNumChamada ;
37 novoNo−>proximo = b o l e t i m ;
38 b o l e t i m = novoNo ;
39 p r i n t f ("Nota inserida com sucesso.\n" ) ;
40 }
41 }
42 }
43
44 p r i n t f ("\nDigitação de notas encerrada. Tecle algo . . ." ) ;
45 g e t c h a r ( ) ; g e t c h a r ( ) ;
46
47 p r i n t f ("\nNotas serão exibidas.\n" ) ;
48 Nota ∗p ;
49 i f ( b o l e t i m == NULL)
50 p r i n t f ("\nNão há notas (lista vazia)\n" ) ;
51 e l s e {
52 f o r ( p = b o l e t i m ; p != NULL ; p = p−>proximo ) {
53 p r i n t f ("Aluno: %d" , p−>numChamada ) ;
54 p r i n t f ("\t Nota: %.1f\n" , p−>n o t a ) ;
55 }
56 }
57
58 p r i n t f ("\nVamos ver os endereços . . ." ) ;
59 g e t c h a r ( ) ;
60
61 i f ( b o l e t i m == NULL)
62 p r i n t f ("\nNão há notas (lista vazia)\n" ) ;
63 e l s e {
64 f o r ( p = b o l e t i m ; p != NULL ; p = p−>proximo )
7.3 Exercícios propostos 21
65 p r i n t f ("%p\n" , p ) ;
66 p r i n t f ("%p\n" , p ) ;
67 }
68
69 p r i n t f ("\n\n" ) ;
70
71 }
7.3 Exercícios propostos
7.3.1 Inserção seletiva na lista encadeada
Receber numeros digitados pelo usuário e inserir os números pares em uma lista encadeada e os números
ímpares em outra.
7.3.2 Média dos elementos da lista encadeada
No exemplo das notas, após digitadas todas as notas, calcular a média da turma.
Não iniciar o cálculo ou acúmulo de somatórios durante a leitura dos dados, inicie os cálculos após receber
todas as notas.
7.3.3 Transferência de dados de uma lista para outra
Fazer um programa que crie uma lista e depois transfira seus dados para outra lista.
7.3.4 Criar e depois percorrer uma lista encadeada, inserindo dados em outra lista
segundo um escopo
Faça um programa que receba (leia) alguns números inteiros, inserindo-os em uma lista encadeada. Em
seguida, o programa percorre esta lista e insere os números maiores que 100 em outra lista encadeada.
7.3.5 Mostrar valores de variáveis e ponteiros durante uma operação e descrever a
operação
Na lista encadeada abaixo, a inserção é feita em ordem crescente. Mostre, passo a passo, os valores que
as variáveis abaixo recebem, desde a digitação até o fim da inclusão, quando é inserido o valor 11 na lista.
7.3 Exercícios propostos 22
q e ant→ ponteiros usados para percorrer a lista.
p.
auxInfo→ variável onde será armazenado o valor 11 quando digitado pelo usuário.
info e prox→ campos da estrutura nó da lista. (Mostrar apenas para o novo nó criado).
p→ 5 ∗ → 9 ∗ → 13 ∗ → 14 ∗ → 18 ∗ → NULL
Além dos valores das variáveis e ponteiros, explique passo a passo como é feita esta inserção.
7.3.6 Mostrar graficamente, passo a passo, o que ocorre na execução do programa
Considere o código a seguir.
Programa 7.2: Lista encadeada
1 # i n c l u d e < s t d l i b . h>
2 s t r u c t TipoNo {
3 i n t v a l o r ;
4 s t r u c t TipoNo ∗proximo ;
5 } ;
6 t y p e d e f s t r u c t TipoNo No ;
7 i n t main ( ) {
8 i n t i = 1 ;
9 No ∗ l i s t a , ∗novoNo , ∗p ;
10 l i s t a = NULL;
11 whi le ( i < 4 ) {
12 novoNo = ( No∗ ) ( m a l loc ( s i z e o f ( No ) ) ) ; / / 1
13 novoNo−>v a l o r = i ; / / 2
14 novoNo−>proximo = l i s t a ; / / 3
15 l i s t a = novoNo ; / / 4
16 i ++; / / 5
17 }
18 p r i n t f ("\nA_lista_criada.\n" ) ;
19 p r i n t f ("->" ) ;
20 f o r ( p = l i s t a ; p != NULL ; p = p−>proximo )
21 p r i n t f ("%d->" , p−>v a l o r ) ;
22 p r i n t f ("NULL" ) ;
23 g e t c h a r ( ) ;
24 }
Mostre graficamente, passo a passo, o que ocorre na execução do programa. Nos seus desenhos, mostre as
estruturas e os ponteiros e relacione os passos com os rótulos de 1 a 5 (//1, //2, etc), existentes no programa.
Ao final deve ser mostrada a estrutura de dados que o programa cria (ainda graficamente).
7.3 Exercícios propostos 23
7.3.7 O que faz a função?
Considere o fragmento de código a seguir:
Programa 7.3: Fragmento
1 Est ru tu raEmUso ∗ t r e c h o F u l a n o ( Es t ru tu raEmUso ∗pont , i n t v ) {
2 Est ru tu raEmUso ∗ a n t = NULL, ∗p = pon t ;
3 whi le ( p != NULL && p−>i n fo != v ) {
4 a n t = p ;
5 p = p−>prox ;
6 }
7 i f ( p == NULL)
8 re turn pon t ;
9
10 i f ( a n t == NULL)
11 pon t = p−>prox ;
12 e l s e
13 an t−>prox = p−>prox ;
14 f r e e ( p ) ;
15 re turn pon t ;
16 }
1. O que ele é?
2. O que ele faz?
3. O que o trecho do while faz?
4. O que o trecho do primeiro if faz e quando é executado?
5. O que o trecho do segundo if faz e quando é executado?
6. O que o trecho do else faz e quando é executado?
7. O que o trecho free faz?
8. O que o return faz?
9. Explique as partes e funções da primeira linha do código?
7.3.8 Produto do primeiro elemento pelo último
Faça um programa que receba (leia) alguns números inteiros, inserindo-os em uma lista encadeada. Em
seguida, o programa acessa a lista, calcula e exibe o produto do primeiro elemento pelo último.
7.3 Exercícios propostos 24
7.3.9 Mostrar valores de variáveis e ponteiros durante uma operação
Na lista encadeada abaixo, mostre, passo a passo, os valores que as variáveis e ponteiros assumem,
desde a digitação até o fim da execução, quando o usuário pede a remoção (exclusão) do elemento 13.
q e ant→ ponteiros usados para percorrer a lista.
p.
auxInfo→ variável onde será armazenado o valor 13 quando digitado pelo usuário.
Obs.: info e prox são os campos da estrutura nó da lista.
p→ 5 ∗ → 9 ∗ → 13 ∗ → 14 ∗ → 18 ∗ → NULL
Além dos valores das variáveis e ponteiros, explique passo a passo como é feita esta exclusão.
7.3.10 Mostrar graficamente, passo a passo, o que ocorre na execução do programa
Considere o código a seguir.
Programa 7.4: Código
1 # i n c l u d e < s t d l i b . h>
2 s t r u c t TipoNo {
3 i n t v a l o r ;
4 s t r u c t TipoNo ∗proximo ;
5 } ;
6 t y p e d e f s t r u c t TipoNo No ;
7 i n t main ( ) {
8 i n t i = 1 ;
9 No ∗ l i s t a , ∗novoUm , ∗novoDois , ∗p ;
10 l i s t a = NULL;
11 whi le ( i < 4 ) {
12
13 novoUm = ( No∗ ) ( m a l lo c ( s i z e o f ( No ) ) ) ; / / 1
14 novoUm−>v a l o r = i ; / / 2
15 novoUm−>proximo = l i s t a ; / / 3
16 l i s t a = novoUm ; / / 4
17
18 novoDois = ( No∗ ) ( m a l lo c ( s i z e o f ( No ) ) ) ; / / 5
19 novoDois−>v a l o r = i ∗ i ; / / 6
20 novoDois−>proximo = l i s t a ; / / 7
21 l i s t a = novoDois ; / / 8
22
23 i ++; / / 9
24 }
25 p r i n t f ("\nA_lista_criada.\n" ) ;
7.3 Exercícios propostos 25
26 p r i n t f ("->" ) ;
27 f o r ( p = l i s t a ; p != NULL ; p = p−>proximo )
28 p r i n t f ("%d->" , p−>v a l o r ) ;
29 p r i n t f ("NULL" ) ;
30 g e t c h a r ( ) ;
31 }
Mostre graficamente (com desenhos), passo a passo, o que ocorre na execução do programa. Nos seus
desenhos, mostre as estruturas e os ponteiros e relacione os passos com os rótulos de 1 a 9 (//1, //9, etc),
existentes no programa. Ao final deve ser mostrada a estrutura de dados que o programa cria (ainda grafi-
camente).
7.3.11 Busca e exclusão
Com relação às listas encadeadas, responda:
1. Na busca, quando se constata que o valor buscado (procurado) não existe na lista?
2. Por que usamos o ponteiro ant ou anterior na exclusão?
7.3.12 Média na lista
Faça um programa que receba (leia) alguns números inteiros, inserindo-os em uma lista encadeada. Em
seguida, o programa acessa a lista, calcula e exibe a média aritmética dos números armazenados na lista.
7.3.13 Mostrar valores de variáveis e ponteiros durante uma operação
Mostre, passo a passo, os valores que as variáveis abaixo recebem, desde a digitação até o fim da exe-
cução, quando o usuário pede a busca do elemento 13.
q→ ponteiro usado para percorrer a lista.
p.
auxInfo→ variável onde será armazenado o valor 13 quando digitado pelo usuário.
Obs.: info e prox são os campos da estrutura nó da lista.
p→ 5 ∗ → 2 ∗ → 13 ∗ → 10 ∗ → 1 ∗ → NULL
Além dos valores das variáveis e ponteiros, explique passo a passo como é feita (ou como funciona) a busca.
7.3 Exercícios propostos 26
7.3.14 Concatenar listas
Dadas duas listas encadeadas independentes, o que seria necessário para concatená-las, ou seja, para
colocar a segunda no final da primeira?
7.3.15 Exibir os elementos das posições ímpares
Faça um programa que receba (leia) alguns números inteiros, inserindo-os em uma lista encadeada. Em
seguida, o programa percorre esta lista e mostra (exibe) os elementos das posições ímpares.
Exemplo: Dada a lista X,Y, Z,K,L,M,P,A,B serão exibidos os valores X,Z,L, P,B
7.3.16 Retirar e inserir segundo um escopo
Faça um programa que receba (leia) alguns números inteiros, inserindo-os em uma lista encadeada.
Em seguida, o programa percorre esta lista, retira os números maiores que 50 e os insere em outra lista
encadeada
Capítulo 8
Pilhas
8.1 Introdução
N
as pilhas os dados são sempre inseridos e retirados do topo. É comum dizer que as pilhas seguem o
princípio LIFO (Last In, First Out) (último a entrar, primeiro a sair).
É comum o uso dos nomes push para a função que insere dados na pilha (empilhar) e pop para a que
retira (desempilhar).
8.2 Exemplo gráfico
push(15) topo→ 15
↓
NULL
Empilhou o 15
push(10) topo→ 10
↓
15
↓
NULL
Empilhou o 10
8.2 Exemplo gráfico 28
push(23) topo→ 23
↓
10
↓
15
↓
NULL
Empilhou o 23
push(6) topo→ 6
↓
23
↓
10
↓
15
↓
NULL
Empilhou o 6
pop( ) topo→ 23
↓
10
↓
15
↓
NULL
Desempilhou o 6
A função pop( ) não recebe argumento (pois sempre retira do topo). Ela retorna o valor que está no topo da
lista
pop( ) topo→ 10
↓
15
↓
NULL
Desempilhou o 23
8.3 Exemplos 29
push(45) topo→ 45
↓
10
↓
15
↓
NULL
Empilhou o 45
8.3 Exemplos
Programa 8.1: Pilha
1 /∗ P i l h a 0 1 . c − F i l i p p e Jabour − 2 0 / 0 9 / 2 0 1 1
2 P i l h a
3 ∗ /
4
5 # i n c l u d e < s t d i o . h>
6 # i n c l u d e < s t d l i b . h>
7
8 /∗ Nó ( e l e m e n t o ) da p i l h a ( e s t r u t u r a ) ∗ /
9 s t r u c t TipoElemento {
10 i n t i n f o r m a c a o ;
11 s t r u c t TipoElemento ∗proximo ;
12 } ;
13 t y p e d e f s t r u c t TipoElemento Elemento ;
14
15 /∗ A e s t r u t u r a P i l h a ∗ /
16 s t r u c t T i p o P i l h a {
17 Elemento ∗ t opo ;
18 } ;
19 t y p e d e f s t r u c t T i p o P i l h a P i l h a ;
20
21 /∗ I n s e r ç ã o de e l e m e n t o ( sempre no topo da p i l h a ) ∗ /
22 void push ( P i l h a ∗p , i n t dado ) {
23 Elemento ∗novo = ( Elemento ∗ ) m a l lo c ( s i z e o f ( Elemento ) ) ;
24 i f ( ! novo ) {
25 p r i n t f ("Erro criando novo elemento." ) ;
26 re turn ;
27 }
28 novo−>i n f o r m a c a o = dado ;
29 novo−>proximo = p−>topo ;
30 p−>topo = novo ;
31 }
8.3 Exemplos 30
32
33 /∗ remoção de e l e m e n t o ( sempre do i n i c i o da p i l h a ) ∗ /
34 i n t pop ( P i l h a ∗p ) {
35 Elemento ∗aux ;
36 i n t dado ;
37 i f ( ! p−>topo ) {
38 p r i n t f ("\nPilha vazia. Programa será encerrado.\n" ) ;
39 g e t c h a r ( ) ;
40 e x i t ( 1 ) ;
41 }
42 aux = p−>topo ;
43 dado = p−>topo−>i n f o r m a c a o ;
44 p−>topo = p−>topo−>proximo ;
45 f r e e ( aux ) ;
46 re turn ( dado ) ;
47 }
48
49 void m o s t r a P i l h a ( P i l h a ∗p ) {
50 Elemento ∗aux = p−>topo ;
51 p r i n t f ("\nA pilha\n" ) ;
52 f o r ( aux ; aux ; aux = aux−>proximo )
53 p r i n t f ("%d\n" , aux−>i n f o r m a c a o ) ;
54 p r i n t f ("\n" ) ;
55 }
56
57 i n t main ( void ) {
58 i n t numero = 0 , opcao = 0 ;
59 P i l h a ∗ p i l h a = ( P i l h a ∗ ) m a l loc ( s i z e o f ( P i l h a ) ) ;
60 i f ( ! p i l h a ) {
61 p r i n t f ("\nErro ao alocar memória.\n" ) ;
62 g e t c h a r ( ) ;
63 e x i t ( 1 ) ;
64 }
65 p i l h a −>topo = NULL;
66
67 whi le ( opcao ! = 4 ) {
68 p r i n t f ("\n1-Push.\n2-Pop.\n3-Mostra.\n4-Sai.\n" ) ;
69 p r i n t f ("Opcao: " ) ;
70s c a n f ("%d" ,& opcao ) ;
71 sw i t ch ( opcao ) {
72 case 1 :
73 p r i n t f ("\nInformacao: " ) ;
74 s c a n f ("%d" ,&numero ) ;
75 push ( p i l h a , numero ) ;
76 break ;
77 case 2 :
78 numero = pop ( p i l h a ) ;
79 p r i n t f ("\nRetirado %d\n" , numero ) ;
8.3 Exemplos 31
80 break ;
81 case 3 :
82 m o s t r a P i l h a ( p i l h a ) ;
83 break ;
84 }
85 }
86 }
A implementação proposta tem uma pequena diferença do que vínhamos fazendo. Existe um estrutura
Pilha que contém apenas um ponteiro para uma estrutura do tipo Elemento.
Algumas consequências interessantes podem ser notadas. Quando o ponteiro para a pilha é passado
como argumento para uma função, não é necessário que ele seja retornado pela função após serem feitas as
modificações (push e pop). Isto ocorre porque as modificações são feitas a partir do segundo ponteiro, ou
seja, o único campo da estrutura Pilha, que aponta para o topo da pilha.
Vamos discutir mais o funcionamento:
Pilha *pilha = (Pilha *) malloc( sizeof(Pilha) );
pilha aponta para uma estrutura do tipo Pilha. Esta estrutura contém um campo chamado topo que é
um ponteiro para uma estrutura do tipo Elemento. Quando o ponteiro pilha é passado como argumento
para a função push, por exemplo, um elemento é empilhado. O ponteiro topo passa a apontar para este
novo elemento e o novo elemento passa a pontar para o antigo topo da pilha. O tempo todo (antes e depois
da chamada da função push), o ponteiro pilha permanece apontando para a estrutura Pilha e, consequente-
mente, para o ponteiro topo. Assim, após a execução da função, a pilha já está atualizada no programa
principal.
O mesmo ocorre com a função pop, permitindo ainda que seja retorna um int, o número desempilhado,
sem a necessidade de se retornar um ponteiro atualizado, como fazíamos nas listas encadeadas (Capítulo 7).
Capítulo 9
Filas
9.1 Introdução
F ila é uma lista linear em que a inserção é feita numa extremidade e a eliminação na outra. Deste modo,dizemos que funciona no esquema FIFO: first in, first out ou PCPS: primeiro a chegar, primeiro a sair.
Para lembrar, pense nas filas que vemos no dia a dia: filas de banco, de supermercado, etc.
9.2 Exemplos
Programa 9.1: Fila01
1 # i n c l u d e < s t d i o . h>
2 # i n c l u d e < s t d l i b . h>
3
4 /∗ Nó ( e l e m e n t o ) da f i l a ( e s t r u t u r a ) ∗ /
5 s t r u c t TipoElemento {
6 i n t i n f o r m a c a o ;
7 s t r u c t TipoElemento ∗proximo ;
8 } ;
9
10 t y p e d e f s t r u c t TipoElemento Elemento ;
11
12 /∗ A e s t r u t u r a F i l a ∗ /
13 s t r u c t T i p o F i l a {
14 Elemento ∗ i n i c i o , ∗ f im ;
15 } ;
16
17 t y p e d e f s t r u c t T i p o F i l a F i l a ;
18
9.2 Exemplos 33
19 /∗ I n s e r ç ã o de e l e m e n t o ( sempre no f i m da f i l a ) ∗ /
20 void f i l a I n s e r e ( F i l a ∗ f , i n t dado ) {
21
22 Elemento ∗novo = ( Elemento ∗ ) m a l lo c ( s i z e o f ( Elemento ) ) ;
23
24 i f ( ! novo ) {
25 p r i n t f ("\nErro criando novo elemento." ) ;
26 re turn ;
27 }
28
29 novo−>i n f o r m a c a o = dado ;
30 novo−>proximo = NULL;
31
32 i f ( f−>fim ) / / o mesmo que ( p−>f i m != NULL) , i n d i c a F i l a não v a z i a
33 f−>fim−>proximo = novo ;
34 e l s e / / F i l a v a z i a
35 f−> i n i c i o = novo ;
36
37 f−>fim = novo ;
38 }
39
40 /∗ Remoção de e l e m e n t o ( sempre do i n i c i o da f i l a ) ∗ /
41 i n t f i l a R e t i r a ( F i l a ∗ f ) {
42
43 Elemento ∗p ;
44 i n t dado ;
45
46 p = f−> i n i c i o ;
47 dado = p−>i n f o r m a c a o ;
48 f−> i n i c i o = p−>proximo ;
49
50 i f ( ! f−> i n i c i o ) / / F i l a f i c o u v a z i a
51 f−>fim = NULL;
52
53 f r e e ( p ) ;
54
55 re turn ( dado ) ;
56 }
57
58 /∗ Ex ibe o menu e r e t o r n a a opção e s c o l h i d a ∗ /
59 i n t menu ( ) {
60
61 i n t opcao ;
62 p r i n t f ("\n" ) ;
63 p r i n t f ("\n +-------------------------+" ) ;
64 p r i n t f ("\n | Fila |" ) ;
65 p r i n t f ("\n |-------------------------|" ) ;
66 p r i n t f ("\n | 1 - Insere |" ) ;
9.2 Exemplos 34
67 p r i n t f ("\n | 2 - Retira |" ) ;
68 p r i n t f ("\n | 3 - Exibe a fila |" ) ;
69 p r i n t f ("\n | 4 - Limpa a fila |" ) ;
70 p r i n t f ("\n | 5 - Sai do programa |" ) ;
71 p r i n t f ("\n +-------------------------+" ) ;
72 p r i n t f ("\n\n Digite sua opcao: " ) ;
73
74
75 s c a n f ("%d" , &opcao ) ;
76
77 re turn ( opcao ) ;
78 }
79
80 /∗ Lê e r e t o r n a um número i n t e i r o ∗ /
81 i n t l e I n t e i r o ( ) {
82
83 i n t numero ;
84
85 p r i n t f ("\nDigite um numero: " ) ;
86 s c a n f ("%d" ,&numero ) ;
87
88 re turn ( numero ) ;
89 }
90
91 /∗ Exibe a F i l a ( p o s i ç ã o c o r r e t a do " f i m da f i l a " só f u n c i o n a se a f i l a c o n t i v e r apenas
92 ∗ números p o s i t i v o s e n t r e 0 e 999) e se não houver quebra de l i n h a ∗ /
93 void m o s t r a F i l a ( F i l a ∗ f ) {
94
95 Elemento ∗p ;
96
97 /∗ p o s i c i o n a a p a l a v r a f i m ∗ /
98 p r i n t f ("\n " ) ;
99 f o r ( p = f−> i n i c i o ; p ; p = p−>proximo ) {
100 i f ( p−>i n f o r m a c a o < 10 )
101 p r i n t f (" " ) ;
102 e l s e {
103 i f ( p−>i n f o r m a c a o < 100)
104 p r i n t f (" " ) ;
105 e l s e
106 p r i n t f (" " ) ;
107 }
108 }
109 p r i n t f ("fim" ) ;
110
111 /∗ p o s i c i o n a o " p i p e " ∗ /
112 p = f−> i n i c i o ;
113 p r i n t f ("\n " ) ;
114 f o r ( p = f−> i n i c i o ; p ; p = p−>proximo ) {
9.2 Exemplos 35
115 i f ( p−>i n f o r m a c a o < 10 )
116 p r i n t f (" " ) ;
117 e l s e {
118 i f ( p−>i n f o r m a c a o < 100)
119 p r i n t f (" " ) ;
120 e l s e
121 p r i n t f (" " ) ;
122 }
123 }
124 p r i n t f ("|" ) ;
125
126 /∗ p o s i c i o n a o V ( " pon ta da s e t a pra b a i x o " ) ∗ /
127 p r i n t f ("\n " ) ;
128 f o r ( p = f−> i n i c i o ; p ; p = p−>proximo ) {
129 i f ( p−>i n f o r m a c a o < 10 )
130 p r i n t f (" " ) ;
131 e l s e {
132 i f ( p−>i n f o r m a c a o < 100)
133 p r i n t f (" " ) ;
134 e l s e
135 p r i n t f (" " ) ;
136 }
137 }
138 p r i n t f ("V" ) ;
139
140 p r i n t f ("\ninicio->" ) ;
141 f o r ( p = f−> i n i c i o ; p ; p = p−>proximo )
142 p r i n t f ("%d->" , p−>i n f o r m a c a o ) ;
143 p r i n t f ("NULL\n" ) ;
144
145 } / / f i m m o s t r a F i l a
146
147 /∗ Limpa a f i l a ∗ /
148 void l i m p a F i l a ( F i l a ∗ f ) {
149
150 Elemento ∗p = f−>i n i c i o , ∗ a n t ;
151
152 f−> i n i c i o = f−>fim = NULL;
153
154 do {
155 a n t = p ;
156 p = p−>proximo ;
157 f r e e ( a n t ) ;
158 } whi le ( p ) ;
159
160 }
161
162 /∗ Programa p r i n c i p a l ∗ /
9.2 Exemplos 36
163 i n t main ( void ) {
164
165 i n t numero = 0 , opcao = 0 ;
166
167 F i l a ∗ f i l a = ( F i l a ∗ ) m a l loc ( s i z e o f ( F i l a ) ) ;
168
169 i f ( ! f i l a ) {
170 p r i n t f ("\nErro inicializando a fila.\n" ) ;
171 re turn ( 0 ) ;
172 }
173
174 f i l a −> i n i c i o = f i l a −>fim = NULL;
175
176 whi le ( opcao ! = 5 ) {
177
178 opcao = menu ( ) ;
179
180 sw i t ch ( opcao ) {
181
182 case 1 :
183 numero = l e I n t e i r o ( ) ;
184 f i l a I n s e r e ( f i l a , numero ) ;
185 break ;
186
187 case 2 :
188 i f ( ! f i l a −> i n i c i o ) / / o mesmo que ( f−>i n i c i o ==
NULL) , i n d i c a F i l a v a z i a
189 p r i n t f ("\nFila vazia." ) ;
190 e l s e
191 p r i n t f ("\n Elemento retirado da fila: %d" ,
f i l a R e t i r a ( f i l a ) ) ;
192 break ;
193
194 case 3 :
195 m o s t r a F i l a ( f i l a ) ;
196 break ;
197
198case 4 :
199 i f ( f i l a −> i n i c i o )
200 l i m p a F i l a ( f i l a ) ;
201 break ;
202
203 case 5 :
204 p r i n t f ("\n" ) ;
205 break ;
206
207 d e f a u l t :
208 p r i n t f ("\n Opcao invalida." ) ;
9.3 Exercícios propostos 37
209 }
210 }
211 }
9.3 Exercícios propostos
9.3.1 Retira dois elementos da fila
Faça um programa que receba números inteiros e os insira em uma fila. Deve haver uma função apara
que retira dois elementos da fila de cada vez (o primeiro e o último), e retorna a soma deles. Mostre no
programa o uso da referida função.
Exemplo: Inseridos X, Y, Z, K, M, L, P. Ao se chamar a função apara, ela retira X e P, e retorna (X+P).
9.3.2 Produto do 2o pelo último elemento da fila
Faça um programa que receba (leia) alguns números inteiros, inserindo-os em uma Fila. Em seguida, o
programa calcula e exibe o produto do segundo elemento da fila pelo último elemento da fila.
9.3.3 Concatenação de filas
Faça um programa que insira os números 9, 6, 3 em uma fila filaC, insira os números 8, 6, 4 na fila filaB e
os números 0, 11, 121 na fila filaA. Nenhum número deve ser pedido ao usuário ou digitado via teclado.
Depois de criadas as 3 filas, as filas filaB e filaA devem ser colocadas no final da filaC, gerando a fila 9, 6,
3, 8, 6, 4, 0, 11, 121.
9.3.4 Roteador com 4 filas
Simule um roteador de rede que receba pacotes por uma interface de entrada e envie por uma de três
interfaces de saída que ele possui segundo algum critério. Use estruturas de dados dinâmicas para gerenciar
o processo.
http://www.jabour.com.br
Capítulo 10
Recursividade
10.1 Introdução
N
este capítulo estudaremos o conceito e aplicações da recursividade.
No Capítulo 3 estudamos as funções. Para relembrar, no programa 3.2, tínhamos a situação em que
a função principal main chamava outra função, a função calculaMedia. Esta era executada e quando
terminava, retornava o fluxo de execução para a main.
Agora imagine a situação em que um função chama a si mesma dentro do seu código. Isto é permitido,
muito usado e se chama Recursividade.
Assim, podemos ter a seguinte situação:
Função main em execução
⇒ main chama a funçãoXYZ
⇒ instância 1 da funçãoXYZ em execução
⇒ instância 1 da funçãoXYZ chama a si mesma
⇒ instância 2 da funçãoXYZ em execução
⇒ instância 2 da funçãoXYZ chama a si mesma
⇒ instância 3 da funçãoXYZ em execução
⇒ instância 3 da funçãoXYZ termina
⇒ fluxo de execução retorna para a instância 2 de execução da funçãoXYZ
⇒ instância 2 da funçãoXYZ termina
⇒ fluxo de execução retorna para a instância 1 da funçãoXYZ
⇒ instância 1 da funçãoXYZ termina
⇒ fluxo de execução volta para a função principal main.
10.1 Introdução 39
A seguir, apresentaremos o “Hello World” dos programas recursivos (Programa 10.1).
Programa 10.1: Cálculo do fatorial com recursividade
1 /∗ f a t o r i a l − F i l i p p e Jabour − 5 / 1 1 / 2 0 0 6
2 C a l c u l a o f a t o r i a l de forma r e c u r s i v a
3 ∗ /
4
5 # i n c l u d e < s t d i o . h>
6
7 f l o a t f a t o r i a l ( i n t argumento ) {
8
9 f l o a t r e s u l t a d o L o c a l = 1 ;
10
11 i f ( a rgumento > 1)
12 r e s u l t a d o L o c a l = argumento ∗ f a t o r i a l (−−argumento ) ;
13
14 re turn ( r e s u l t a d o L o c a l ) ;
15 }
16
17 i n t main ( ) {
18
19 f l o a t r e s u l t a d o = 1 ;
20 i n t numero ;
21
22 p r i n t f ("\nCalculo do Fatorial" ) ;
23 p r i n t f ("\nDigite o numero: " ) ;
24 s c a n f ("%d" , &numero ) ;
25
26 i f ( numero == 0 ) {
27 p r i n t f ("O fatorial de %d eh %.0f\n" , numero , r e s u l t a d o ) ;
28 re turn ;
29 }
30
31 i f ( numero < 1 )
32 re turn ;
33
34 r e s u l t a d o = f a t o r i a l ( numero ) ;
35
36 p r i n t f ("O fatorial de %d eh %.0f\n\n" , numero , r e s u l t a d o ) ;
37 }
Observe que a função main faz a primeira chamada à função fatorial, passando como argumento o
número digitado pelo usuário. A função fatorial, sempre que recebe um argumento maior que 1, chama a si
mesma novamente, passando como argumento o número que recebeu, decrementado em uma unidade. Isto
acontece tantas vezes quantas forem necessárias (em função do número cujo fatorial desejamos calcular).
Quando a função fatorial recebe 1 como argumento, ela não entra do if e retorna o valor 1. A função
10.1 Introdução 40
que chamou esta última instância que retornou 1, estava parada dentro do if, aguardando o retorno da
chamada recursiva. Quando recebe o valor 1, faz a multiplicação do argumento que havia recebido (2)
pelo 1 que recebeu, retorna o resultado (2) para quem a chamou, terminando a sua execução. A instância
imediatamente anterior, recebe o 2, multiplica por 3 e retorna o 6. Este processo se repete, até o fluxo de
execução voltar à função main, que exibe o fatorial calculado. Neste retorno das diversas instâncias das
chamadas recursivas, dizemos que as funções estão sendo desempilhadas.
O Programa 10.2) imprime mensagens a cada chamada recursiva e a cada término de função. Talvez ele
esclareça o funcionamento da recursividade.
Programa 10.2: Cálculo do fatorial com recursividade com mensagens
1 # i n c l u d e < s t d i o . h>
2
3 i n t i n s t a n c i a ;
4
5 f l o a t f a t o r i a l ( i n t argumento ) {
6
7 i n t j ;
8 p r i n t f ("\n\n" ) ;
9 f o r ( j =1 ; j <= i n s t a n c i a ; j ++) p r i n t f ("\t" ) ;
10 p r i n t f ("Instancia %d da funcao fatorial em execucao." ,++ i n s t a n c i a ) ;
11
12 f l o a t r e s u l t a d o L o c a l = 1 ;
13
14 i f ( a rgumento > 1) {
15
16 p r i n t f ("\n" ) ;
17 f o r ( j =1 ; j <= i n s t a n c i a ; j ++) p r i n t f ("\t" ) ;
18 p r i n t f ("Argumento maior que 1, instancia %d da funcao fatorial farah uma
chamada recursiva." , i n s t a n c i a ) ;
19
20 r e s u l t a d o L o c a l = argumento ∗ f a t o r i a l (−−argumento ) ;
21
22 p r i n t f ("\n\n" ) ;
23 f o r ( j =1 ; j <= i n s t a n c i a −1; j ++) p r i n t f ("\t" ) ;
24 p r i n t f ("Instancia %d da funcao fatorial recebeu retorno, multiplicacao
deu %.0f.\n" , i n s t a n c i a , r e s u l t a d o L o c a l ) ;
25 f o r ( j =1 ; j <= i n s t a n c i a −1; j ++) p r i n t f ("\t" ) ;
26 p r i n t f ("Este valor serah retornado para a instancia %d" , i n s t a n c i a −1) ;
27 }
28 e l s e {
29 p r i n t f ("\n" ) ;
30 f o r ( j =1 ; j <= i n s t a n c i a ; j ++) p r i n t f ("\t" ) ;
31 p r i n t f ("Argumento igual a 1" ) ;
32 }
33
10.2 Exemplos 41
34 p r i n t f ("\n" ) ;
35 f o r ( j =1 ; j <= i n s t a n c i a −1; j ++) p r i n t f ("\t" ) ;
36 p r i n t f ("Instancia %d da funcao fatorial irah terminar." , i n s t a n c i a −−) ;
37
38 re turn ( r e s u l t a d o L o c a l ) ;
39 }
40
41 i n t main ( ) {
42
43 p r i n t f ("\nFuncao main em execucao." ) ;
44
45 f l o a t r e s u l t a d o = 1 ;
46 i n t numero ;
47
48 p r i n t f ("\nCalculo do Fatorial" ) ;
49 p r i n t f ("\nDigite o numero: " ) ;
50 s c a n f ("%d" , &numero ) ;
51
52 i f ( numero == 0 ) {
53 p r i n t f ("\n\nO fatorial de %d eh %.0f\n" , numero , r e s u l t a d o ) ;
54 re turn ;
55 }
56
57 i f ( numero < 1 )
58 re turn ;
59
60 r e s u l t a d o = f a t o r i a l ( numero ) ;
61
62 p r i n t f ("\n\nO fatorial de %d eh %.0f\n\n" , numero , r e s u l t a d o ) ;
63 }
10.2 Exemplos
No Programa 10.3 temos um exemplo de uso da lista encadeada com as funções implementadas com
recursividade.
A variável i conta as chamadas recursivas à função busca. A função limpa mostra a lista após a remoção
de cada elemento.
Programa 10.3: Lista encadeada com recursividade
1 # i n c l u d e < s t d i o . h>
2 # i n c l u d e < s t d l i b . h>3
4 i n t i =0 ;
5
10.2 Exemplos 42
6 s t r u c t no {
7 i n t i n f o ;
8 s t r u c t no∗ prox ;
9 } ;
10 t y p e d e f s t r u c t no No ;
11
12 No∗ i n s e r e ( No∗ l i s t a , i n t i ) {
13 No∗ novo = ( No∗ ) m a l lo c ( s i z e o f ( No ) ) ;
14 novo−>i n f o = i ;
15 novo−>prox = l i s t a ;
16 re turn novo ;
17 }
18
19 void imprime ( No∗ l i s t a ) {
20 i f ( l i s t a ) {
21 p r i n t f ("%d->" , l i s t a −>i n f o ) ;
22 imprime ( l i s t a −>prox ) ;
23 }
24 e l s e
25 p r i n t f ("NULL\n" ) ;
26 }
27
28 No∗ busca ( No∗ l i s t a , i n t v ) {
29 p r i n t f ("\n\t%d" ,++ i ) ;
30 No∗ achou = NULL;
31 i f ( l i s t a ) {
32 i f ( l i s t a −>i n f o == v ) {
33 p r i n t f ("\n\t%d" , i−−) ;
34 re turn ( l i s t a ) ;
35 }
36 e l s e {
37 i f ( l i s t a −>prox ) {
38 achou = busca ( l i s t a −>prox , v ) ;
39 p r i n t f ("\n\t%d" , i−−) ;
40 re turn ( achou ) ;
41 }
42 e l s e {
43 p r i n t f ("\n\t%d" , i−−) ;
44 re turn (NULL) ;
45 }
46 }
47 }
48 e l s e
49 re turn (NULL) ;
50 }
51
52 No∗ l impa ( No∗ l i s t a ) {
53 No∗ temp ;
10.2 Exemplos 43
54 i f ( l i s t a ) {
55 temp = l i s t a −>prox ;
56 f r e e ( l i s t a ) ;
57 p r i n t f ("\n" ) ;
58 imprime ( temp ) ;
59 l impa ( temp ) ;
60 }
61 re turn (NULL) ;
62 }
63
64 i n t main ( void ) {
65
66 No ∗ l i s t a , ∗ p r o c u r a d o = NULL;
67 l i s t a = NULL;
68 i n t numero , opcao = 0 ;
69
70 whi le ( opcao != 5 ) {
71 p r i n t f ("\n1-Insere.\n2-Imprime.\n3-Limpa.\n4-Busca\n5-Sai.\n" ) ;
72 p r i n t f ("Opcao: " ) ;
73 s c a n f ("%d" ,& opcao ) ;
74 sw i t ch ( opcao ) {
75 case 1 :
76 p r i n t f ("\nDigite um número: " ) ;
77 s c a n f ("%d" ,&numero ) ;
78 l i s t a = i n s e r e ( l i s t a , numero ) ;
79 break ;
80 case 2 :
81 p r i n t f ("Lista->" ) ;
82 imprime ( l i s t a ) ;
83 p r i n t f ("\n" ) ;
84 break ;
85 case 3 :
86 l i s t a = l impa ( l i s t a ) ;
87 break ;
88 case 4 :
89 i =0 ;
90 p r i n t f ("\nDigite um número: " ) ;
91 s c a n f ("%d" ,&numero ) ;
92 p r o c u r a d o = busca ( l i s t a , numero ) ;
93 i f ( p r o c u r a d o )
94 p r i n t f ("\nAchou o número %d.\n" , p rocu rado−>i n f o )
;
95 e l s e
96 p r i n t f ("\nNão Achou.\n" ) ;
97 break ;
98 case 5 :
99 l i s t a = l impa ( l i s t a ) ;
100 }
10.3 Exercícios 44
101 }
102 }
10.3 Exercícios
10.3.1 Soma dos números de 0 a n com recursividade
Faça um programa recursivo que calcula a soma dos números de 0 a n.
Resposta: Programa 10.4.
10.3.2 Divisão com recursividade
Faça um programa que calcula x÷ y usando recursividade.
Resposta: Programa 10.5.
10.3.3 Soma dos elementos do vetor usando recursividade
Faça um programa recursivo que calcula a soma dos elementos de um vetor.
Resposta: Programa 10.6.
10.3.4 Contar números ímpares da lista encadeada usando recursividade
Faça um programa recursivo que conta quantos números ímpares existem em uma lista encadeada.
Resposta: Programa 10.7.
10.4 Resposta dos Exercícios
Resposta do exercício 10.3.1
Programa 10.4: Soma recursiva
1 # i n c l u d e < s t d i o . h>
2
3 i n t somaRecurs iva ( i n t n ) {
4 i f ( n > 0)
10.4 Resposta dos Exercícios 45
5 re turn ( n + somaRecur s iva ( n − 1) ) ;
6 e l s e
7 re turn 0 ;
8 }
9
10 i n t main ( ) {
11 i n t n , soma ;
12
13 p r i n t f ("\n n (positivo) = " ) ;
14 s c a n f ("%d" ,&n ) ;
15
16 i f ( n < 0 )
17 n = −1 ∗ n ;
18
19 p r i n t f ("\n\tSoma dos números de 0 a %d = %d\n\n" , n , somaRecur s iva ( n ) ) ;
20 }
Resposta do exercício 10.3.2
Programa 10.5: Divisão recursiva
1 # i n c l u d e < s t d i o . h>
2
3 i n t d i v i s a o R e c u r s i v a ( i n t numerador , i n t denominador ) {
4 i f ( numerador < denominador )
5 re turn 0 ;
6 e l s e
7 re turn ( d i v i s a o R e c u r s i v a ( numerador − denominador , denominador ) + 1 ) ;
8 }
9
10 i n t main ( ) {
11 i n t numerador , denominador , q u o c i e n t e ;
12
13 p r i n t f ("\n numerador = " ) ;
14 s c a n f ("%d" ,& numerador ) ;
15
16 p r i n t f ("\n denominador (positivo) = " ) ;
17 s c a n f ("%d" ,& denominador ) ;
18
19 i f ( denominador <= 0 ) {
20 p r i n t f ("\n\tDenominador deve ser positivo.\n\n" ) ;
21 re turn 0 ;
22 }
23
24 q u o c i e n t e = d i v i s a o R e c u r s i v a ( numerador , denominador ) ;
25
26 p r i n t f ("\n\t%d / %d = %d (resto %d)\n\n" , numerador , denominador , q u o c i e n t e ,
numerador − denominador ∗ q u o c i e n t e ) ;
10.4 Resposta dos Exercícios 46
27 }
Resposta do exercício 10.3.3
Programa 10.6: Soma recursiva dos elementos do vetor
1 # i n c l u d e < s t d i o . h>
2
3 i n t s o m a V e t o r R e c u r s i v a ( i n t v e t o r [ ] , i n t p o s i c a o ) {
4 i f ( p o s i c a o >= 0 )
5 re turn ( v e t o r [ p o s i c a o ] + s o m a V e t o r R e c u r s i v a ( v e t o r , −−p o s i c a o ) ) ;
6 e l s e
7 re turn 0 ;
8 }
9
10 i n t main ( ) {
11 i n t p o s i c a o ;
12
13 i n t vetorUm [ 1 0 ] = {1 , 3 , 5 , 7 , 9 , 0 , 2 , 4 , 6 , 8 } ;
14 p r i n t f ("\nSoma dos elementos do vetor = %d\n" , s o m a V e t o r R e c u r s i v a ( vetorUm , 9 ) ) ;
15
16 i n t v e t o r D o i s [ 1 ] = { 2 0 } ;
17 p r i n t f ("\nSoma dos elementos do vetor = %d\n" , s o m a V e t o r R e c u r s i v a ( v e t o r D o i s , 0 ) ) ;
18
19 i n t v e t o r T r e s [ 2 ] = {67 , −67};
20 p r i n t f ("\nSoma dos elementos do vetor = %d\n" , s o m a V e t o r R e c u r s i v a ( v e t o r T r e s , 1 ) ) ;
21 }
Resposta do exercício 10.3.4
Programa 10.7: Conta os ímpares da lista encadeada com recursividade
1 # i n c l u d e < s t d i o . h>
2 # i n c l u d e < s t d l i b . h>
3
4 s t r u c t t i p o L i s t a {
5 i n t numero ;
6 s t r u c t t i p o L i s t a ∗proximo ;
7 } ;
8
9 t y p e d e f s t r u c t t i p o L i s t a L i s t a ;
10
11 i n t c o n t a I m p a r e s ( L i s t a ∗ l i s t a ) {
12 i f ( ! l i s t a )
13 re turn 0 ;
14 e l s e {
15 i f ( l i s t a −>numero % 2 == 1 )
16 re turn ( c o n t a I m p a r e s ( l i s t a −>proximo ) + 1) ;
17 e l s e
10.4 Resposta dos Exercícios 47
18 re turn ( c o n t a I m p a r e s ( l i s t a −>proximo ) ) ;
19 }
20 }
21
22 i n t main ( ) {
23 i n t i ;
24 L i s t a ∗ l i s t a = NULL, ∗novo , ∗ p e r c o r r e , ∗aux ;
25
26 / / T e s t e um
27 f o r ( i = 0 ; i < 5 ; i ++ ) {
28 novo = ( L i s t a ∗ ) ( m a l lo c ( s i z e o f ( L i s t a ) ) ) ;
29 i f ( novo ) {
30 novo−>numero = i ;
31 novo−>proximo = l i s t a ;
32 l i s t a = novo ;
33 }
34 }
35 p e r c o r r e = l i s t a ;
36 p r i n t f ("\n\nLista => " ) ;
37 f o r ( ; p e r c o r r e ; p e r c o r r e = p e r c o r r e −>proximo )
38 p r i n t f ("\t%d" , p e r c o r r e −>numero ) ;
39 p r i n t f ("\nQuantidade de ímpares = %d\n" , c o n t a I m p a r e s ( l i s t a ) ) ;
40 whi le ( l i s t a ) {
41 p e r c o r r e = l i s t a −>proximo ;
42 f r e e ( l i s t a ) ;
43 l i s t a = p e r c o r r e ;
44 }
45 / / Fim t e s t e Um
46
47 / / T e s t e Dois
48 f o r ( i = 0 ; i < 10 ; i = i + 2 ) {
49 novo = ( L i s t a ∗ ) ( m a l loc ( s i z e o f ( L i s t a ) ) ) ;
50 i f ( novo ) {
51 novo−>numero = i ;
52 novo−>proximo = l i s t a ;
53 l i s t a = novo ;
54 }
55 }
56 p e r c o r r e = l i s t a ;
57 p r i n t f ("\n\nLista => " ) ;
58 f o r ( ; p e r c o r r e ; p e r c o r r e = p e r c o r r e −>proximo )
59 p r i n t f ("\t%d" , p e r c o r r e −>numero ) ;
60 p r i n t f ("\nQuantidade de ímpares = %d\n" , c o n ta I m p a r e s ( l i s t a ) ) ;
61 whi le ( l i s t a ) {
62 p e r c o r r e = l i s t a −>proximo ;
63 f r e e ( l i s t a ) ;
64 l i s t a = p e r c o r r e ;
65 }
10.4 Resposta dos Exercícios 48
66 / / Fim t e s t e Dois
67
68 / / T e s t e Três
69 l i s t a = ( L i s t a ∗ ) ( m a l lo c ( s i z e o f ( L i s t a ) ) ) ;
70 i f ( l i s t a ) {
71 l i s t a −>numero = 3 ;
72 l i s t a −>proximo = NULL;
73 }
74 p e r c o r r e = l i s t a ;
75 p r i n t f ("\n\nLista => " ) ;
76 f o r ( ; p e r c o r r e ; p e r c o r r e = p e r c o r r e −>proximo )
77 p r i n t f ("\t%d" , p e r c o r r e −>numero ) ;
78 p r i n t f ("\nQuantidade de ímpares = %d\n" , c o n t a I m p a r e s ( l i s t a ) ) ;
79 whi le ( l i s t a ) {
80 p e r c o r r e = l i s t a −>proximo ;
81 f r e e ( l i s t a ) ;
82 l i s t a = p e r c o r r e ;
83 }
84 / / Fim t e s t e Três
85
86 / / T e s t e Quatro
87 l i s t a = ( L i s t a ∗ ) ( m a l lo c ( s i z e o f ( L i s t a ) ) ) ;
88 i f ( l i s t a ) {
89 l i s t a −>numero = 4 ;
90 l i s t a −>proximo = NULL;
91 }
92 p e r c o r r e = l i s t a ;
93 p r i n t f ("\n\nLista => " ) ;
94 f o r ( ; p e r c o r r e ; p e r c o r r e = p e r c o r r e −>proximo )
95 p r i n t f ("\t%d" , p e r c o r r e −>numero ) ;
96 p r i n t f ("\nQuantidade de ímpares = %d\n" , c o n t a I m p a r e s ( l i s t a ) ) ;
97 whi le ( l i s t a ) {
98 p e r c o r r e = l i s t a −>proximo ;
99 f r e e ( l i s t a ) ;
100 l i s t a = p e r c o r r e ;
101 }
102 / / Fim t e s t e Quatro
103
104 / / T e s t e Cinco
105 p r i n t f ("\n\nLista => " ) ;
106 p r i n t f ("\nQuantidade de ímpares = %d\n" , c o n t a I m p a r e s ( l i s t a ) ) ;
107 / / Fim t e s t e Cinco
108
109 p r i n t f ("\n\n" ) ;
110 }
Capítulo 11
Árvores
E
m diversas aplicações, necessita-se de estruturas mais complexas do que as puramente sequenciais.
Entre essas, destacam-se as árvores, por existirem inúmeros problemas práticos que podem ser mod-
elados através delas. Além disso, as árvores, em geral, admitem um tratamento computacional simples e
eficiente.
11.1 Definições e representações básicas
A forma mais comum de representar graficamente uma árvore é através de sua representação hierárquica.
A representação da Figura 11.1, com a raiz no topo (nó A), é a mais empregada na literatura da computação.
A
C
ED
B
Figura 11.1: Representação hierárquica de uma árvore
Seja v o nó raiz da subárvore Tv de T . Os nós raízes w1, w2, . . . , wj das subárvores de Tv são chama-
dos filhos de v; v é chamado pai de w1, w2, . . . , wj . Os nós w1, w2, . . . , wj são irmãos. Se z é filho de
w1, então w2 é tio de z e v é avô de z. O número de filhos de um nó é chamado grau de saída desse nó.
x ∈ Tv → x é descendente de v ∧ v é ancestral de x. Nesse caso, sendo x 6= v, x é descendente próprio
de v, e v é ancestral próprio de x. Um nó que não possui descendentes próprios é chamado folha.
Um sequência de nós distintos v1, v2, . . . , vk | ∃ sempre entre nós consecutivos (v1 e v2, v2 e v3, . . . ,
vk−1 e vk) a relação “é filho de” ou “é pai de”, é denominado um caminho da árvore. Diz-se que v1
11.1 Definições e representações básicas 50
alcança vk e vice-versa. Um caminho de k vértices (nós) é obtido pela sequência de k − 1 pares da relação
citada acima. O valor k−1 é o comprimento do caminho. Nível de um nó v é o número de nós do caminho
da raiz até o nó v. O nível da raiz é 1. A altura de um nó v é o número de nós do maior caminho de v até
um de seus descendentes. As folhas têm altura 1. A altura da árvore T é igual ao nível máximo de seus nós.
Representa-se a altura de T por h(T ), enquanto h(v) é a altura da subárvore de raiz v.
Observe a árvore T da Figura 11.2. O vértice C é ancestral próprio de G, de H e de F , entre outros. O
nó D é descendente próprio de A. O nível do vértice F é 3 e sua altura é 2; o nível do vértice A é 1 e sua
altura é 4. A altura da árvore é 4.
A
C
F
I
ED
HG
B
Figura 11.2: Análise de uma árvore
Uma árvore ordenada é aquela na qual os filhos de cada nó estão ordenados. Assume-se que tal orde-
nação se desenvolva da esquerda para a direita.
Capítulo 12
Árvores Binárias
D
entre as árvores, as binárias são, sem dúvida, as mais comuns em computação.
12.1 Definições
Uma árvore binária T é um conjunto finito de elementos denominados nós ou vértices, tal que:

T = ∅ (Árvore vazia), ou
∃ r (nó raiz de T) e os demais nós podem ser divididos em dois subconjuntos disjuntos TEr e TDr
TEr e T
D
r são, respectivamente, a subárvore esquerda e direita de r
TEr e T
D
r são também árvores binárias
O nó raiz da subárvore esquerda (direita) de v, se existir, é denominado filho esquerdo (direito) de v.
Pode existir apenas o filho esquerdo, apenas o direito, ou ambos.
Uma árvore estritamente binária é uma árvore binária em que cada nós possui 0 ou 2 filhos. Uma
árvore binária completa é aquela que possui a seguinte propriedade: se v é um nó tal que alguma subárvore
de v é vazia, então v se localiza ou no último (maior) ou no penúltimo nível da árvore. Uma árvore
binária cheia é aquela em que, se v é um nó com alguma de suas subárvores vazias, então v se localiza no
último nível. Toda árvore binária cheia é completa e estritamente binária. Como exemplo, a Figura 12.1
é estritamente binária, mas não completa. A árvore da Figura 12.2 é completa, mas não cheia e a da
Figura 12.3 é cheia.
12.2 Exemplos 52
A
C
GD
FE
B
Figura 12.1: Árvore estritamente binária
A
E
IF
HG
B
DC
Figura 12.2: Árvore binária completa
12.2 Exemplos
O Programa 12.1 cria a estrutura do nó da árvore binária com a informação a ser armazenada no nó
(info) e com os ponteiros para os filhos esquerdo e direito. Na função main, a árvore é criada de forma
estática no código fonte. Em seguida, a árvore é impressa na tela de duas formas. Na primeira, é feita uma
formatação manual da impressão e na segunda é usada uma função recursiva mostra_arvore que imprime
a árvore “deitada”.
Programa 12.1: Criação e impressão de uma árvore binária
A
I
M
ON
J
LK
B
F
HG
C
ED
Figura 12.3: Árvore binária cheia
12.2 Exemplos 53
1 # i n c l u d e < s t d l i b . h>
2 # i n c l u d e < s t d i o . h>
3
4 s t r u c t t i poNo {
5 char i n f o ;
6 s t r u c t t i poNo ∗ e s q u e r d a ;
7 s t r u c t t i poNo ∗ d i r e i t a ;
8 } ;
9
10 t y p e d e f s t r u c t t i poNo no ;
11
12 void m o s t r a _ a r v o r e ( no ∗ r , i n t l ) {
13 i n t i ;
14
15 i f ( ! r )
16 re turn ;
17
18 m o s t r a _ a r v o r e ( r−> d i r e i t a , l +1) ;
19 f o r ( i =0 ; i < l ; ++ i )
20 p r i n t f ("\t" ) ;
21 p r i n t f ("%c\n" , r−>i n f o ) ;
22 m o s t r a _ a r v o r e ( r−>esque rda , l +1) ;
23 }
24
25 i n t main ( void ) {
26 char a u x I n f o ;
27
28 no ∗ r a i z , ∗ temp = NULL;
29
30 r a i z = ( no ∗ ) m a l lo c ( s i z e o f ( no ) ) ;
31 r a i z −>i n f o = ’A’ ;
32 r a i z −>e s q u e r d a = NULL;
33 r a i z −> d i r e i t a = NULL;
34
35 temp = ( no ∗ ) m a l lo c ( s i z e o f ( no ) ) ;
36 temp−>i n f o = ’B’ ;
37 temp−>e s q u e r d a = NULL;
38 temp−> d i r e i t a = NULL;
39
40 r a i z −>e s q u e r d a = temp ;
41
42 temp = ( no ∗ ) m a l lo c ( s i z e o f ( no ) ) ;
43 temp−>i n f o = ’C’ ;
44 temp−>e s q u e r d a = NULL;
45 temp−> d i r e i t a = NULL;
46
47 r a i z −> d i r e i t a = temp ;
48
12.2 Exemplos 54
49 temp = ( no ∗ ) m a l lo c ( s i z e o f ( no ) ) ;
50 temp−>i n f o = ’D’ ;
51 temp−>e s q u e r d a = NULL;
52 temp−> d i r e i t a = NULL;
53
54 r a i z −>esque rda−>e s q u e r d a = temp ;
55
56 temp = (