Apostila programação em C - Estrutura de dados

Prévia do material em texto

Pontifícia Universidade Católica de Minas Gerais
Instituto de Ciências Exatas e Informática / Instituto Politécnico
PROF. JOÃO LEONARDO RIBEIRO NETO
www.icei.pucminas.br/professores/joaoneto
joaoneto@pucminas.br
NOTAS DE AULA
BELO HORIZONTE
2009
Sumário
1 Revisão - Estruturas de dados homogêneas 6
1.1 Ordenação de vetores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.1.1 Ordenação por seleção direta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.1.2 Ordenação por permutação - Bubblesort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2 Intercalação de vetores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.3 Manipulação de matrizes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.4 Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2 Revisão - Modularização de programas 16
2.1 Passagem de parâmetros para funções . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.2 Tipos de retorno da função . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.3 Funções recursivas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.4 Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3 Ponteiros em C 30
3.1 Passagem de parâmetro para função utilizando ponteiros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.2 Alocação dinâmica de memória . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.3 Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4 Estruturas Encadeadas 43
4.1 Lista simplesmente encadeada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.2 Lista duplamente encadeada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.3 Pilha . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
4.4 Fila . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
4.5 Árvore Binária . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.6 Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
5 Arquivos em C 73
5.1 Abertura e fechamento de arquivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
5.1.1 Abertura de arquivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
5.1.2 Fechamento de arquivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
1
SUMÁRIO 2
5.2 Escrevendo e lendo caracteres no arquivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
5.2.1 Escrevendo caracter no arquivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
5.2.2 Lendo caracter no arquivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
5.2.3 Contando caracteres no arquivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
5.2.4 Gravando linha a linha no arquivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
5.2.5 Lendo linha a linha . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
Referências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
Lista de Figuras
1.1 Esquema da estrutura de dados homogênea de uma dimensão(vetor) . . . . . . . . . . . . . . . . . . . . . . . 6
1.2 Esquema da estrutura de dados homogênea com 2 dimensões(matriz) . . . . . . . . . . . . . . . . . . . . . . 7
1.3 Exemplo de ordenação por seleção direta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.4 Exemplo de ordenação Bubblesort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.5 Exemplo de intercalação de dois vetores ordenados gerando um terceiro ordenado . . . . . . . . . . . . . . . 11
2.1 Ilustração da passagem de parâmetro por valor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2 Ilustração da passagem de parâmetro por referência . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3 Ilustração da passagem de parâmetro por referência utilizando vetor . . . . . . . . . . . . . . . . . . . . . . . 19
2.4 Ilustração das chamadas recursivas para o cálculo do terceiro termo de fibonacci . . . . . . . . . . . . . . . . 28
4.1 Ilustração de uma lista simplesmente encadeada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.2 Ilustração de uma lista duplamente encadeada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.3 Ilustração de um ’pilha’ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
4.4 Ilustração de uma ’fila’ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
4.5 Ilustração de uma árvore binária . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.6 Ilustração de uma árvore binária ordenada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
3
Lista de Códigos
1.1 Ordenação por seleção direta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2 Ordenação por permutação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3 Intercalação de dois vetores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.4 Multiplicação de matrizes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.1 Passagem de parâmetro por valor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2 Passagem de parâmetro por referência . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3 Passagem de parâmetro por referência utilizando vetor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.4 Passagem de parâmetro por referência utilizando matriz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.5 Retorno de tipo float . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.6 Retorno de tipo nulo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.7 Cálculo do fatorial com recursividade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.8 Cálculo do somatório da série com recursividade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.9 Cálculo do termo de fibonacci com recursividade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.1 Primeiro exemplo - utilizando ponteiros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.2 Segundo exemplo - utilizando ponteiros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.3 Terceiro exemplo - utilizando ponteiros. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.4 Primeiro exemplo - passagem de parâmetro por referência com ponteiros . . . . . . . . . . . . . . . . . . . . 35
3.5 Segundo exemplo - passagem de parâmetro por referência com ponteiros . . . . . . . . . . . . . . . . . . . . 36
3.6 Primeiro exemplo - alocação dinâmica de memória . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.7 Segundo exemplo - alocação dinâmica de memória . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.8 Terceiro exemplo - alocação dinâmica de memória com struct . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.9 Quarto exemplo - alocação dinâmica de memória com struct . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.1 Exemplo da definição de um tipo de dado para uma lista simplesmente encadeada . . . . . . . . . . . . . . . 43
4.2 Inserção no final de uma lista simplesmente encadeada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.3 Inserção ordenada em uma lista simplesmente encadeada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.4 Consulta a um elemento em uma lista simplesmente encadeada . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.5 Exclui um elemento de uma lista simplesmente encadeada . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.6 Imprime todos os elementos de uma lista simplesmente encadeada . . . . . . . . . . . . . . . . . . . . . . . . 51
4.7 Exemplo da definição de um tipo de dado para uma lista duplamente encadeada . . . . . . . . . . . . . . . . 52
4.8 Inclusão de elementos no final de uma lista duplamente encadeada . . . . . . . . . . . . . . . . . . . . . . . 54
4
LISTA DE CÓDIGOS 5
4.9 Exclui elementos em uma lista duplamente encadeada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.10 Imprime os elementos lista duplamente encadeada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
4.11 Insere ordenado em uma lista duplamente encadeada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
4.12 Estrutura de dados para uma ’pilha’ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
4.13 Função para empilhar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.14 Função para ’desempilhar’ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
4.15 Estrutura de dados para uma ’fila’ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
4.16 Funçãp para ’enfileirar’ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
4.17 Função para ’desenfileirar’ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
4.18 Estrutura de dados para uma árvore binária . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.19 Inserção de dados em uma árvore binária ordenada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.20 Impressão inordem, preordem e posordem em uma árvore binária ordenada . . . . . . . . . . . . . . . . . . 70
4.21 Exclusão de um elemento em uma árvore binária ordenada . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
5.1 Definição da struct FILE do arquivo stdio.h . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
5.2 Exemplo da utilização da função fopen e da função putc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
5.3 Exemplo da utilização da função getc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
5.4 Contando caracter em um arquivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
5.5 Gravando linha a linha . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
5.6 Lendo linha a linha . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
Capítulo 1
Revisão - Estruturas de dados homogêneas
Uma estrutura de dados homogêneaestrutura de dados homogênea consiste de componentes do mesmo tipo, o tipo
base. Assim uma estrutura composta de uma dimensão (vetor) pode ser classificado como uma estrutura homogênea.
Pode também ser chamada de estrutura aleatória, já que todos os seus componentes são igualmente acessíveis a qualquer
momento, podendo ser escolhidos aleatóriamente. Para o acesso a um componente individual, a estrutura completa é
constituída de um argumento chamado índice(s), que obtém o componente (WIRTH, N., 1989).
A primeira estrutura de dados homogêneaestrutura de dados homogênea que revisaremos é o vetor. Das estruturas
compostas homogêneasestruturas compostas homogêneas, esta é a estrutura mais simples, composta por uma única dimen-
são (Vide ilustração FIG. 1.1).
Dentre as possibilidades de implementação de estruturas compostas de mais de uma dimensão temos as matrizes, com
duas dimensões (Vide ilustração FIG. 1.2). Observar que a referência de início do índice em estruturas desta natureza, na
linguagem C, é 0(zero).
Figura 1.1: Esquema da estrutura de dados homogênea de uma dimensão(vetor)
6
CAPÍTULO 1. REVISÃO - ESTRUTURAS DE DADOS HOMOGÊNEAS 7
Figura 1.2: Esquema da estrutura de dados homogênea com 2 dimensões(matriz)
1.1 Ordenação de vetores
É importante ressaltar, que a questão mais importante em relação aos métodos de ordenação de vetores, corresponde
ao uso econômico de memória disponível. Isto implica que a permutação de elementos, responsável por levar o elemento
à ordem desejada, deve ser in situ, e que portanto são de menor interesse os métodos que efetuam o transporte físico dos
elementos de um vetor origem para um vetor resultante (WIRTH, N., 1989).
1.1.1 Ordenação por seleção direta
Segundo Wirth em (WIRTH, N., 1989), este método se baseia no seguinte princípio (Vide FIG. 1.3):
• Selecionar o elemento que representa a chave de menor valor;
• Trocá-lo com o primeiro elemento da seqüência a1;
• Repetir estas operações, envolvendo agora apenas os n−1 elementos restantes, depois os n−2 elementos, etc., até
restar um só elemento, o maior deles.
Figura 1.3: Exemplo de ordenação por seleção direta
O código 1.1, ilustra em linguagem C, o algoritmo de ordenação por seleção direta
CAPÍTULO 1. REVISÃO - ESTRUTURAS DE DADOS HOMOGÊNEAS 8
código 1.1: Ordenação por seleção direta
1 #include <stdio .h>
2 #include < stdlib .h>
3 int main()
4 {
5 int a [10], i , j ,aux;
6 for ( i=0;i<10;i++)
7 {
8 printf (" \ nDigite o %do. valor :" , i +1);
9 scanf ("%d",&a[i]);
10 }
11 //−−−−−−−−inicio da ordenação do vetor−−−−−−−−−−−−−−
12 for ( i=0;i<9;i++)
13 for ( j=i+1;j<10;j++)
14 if (a[ i]>a[ j ])
15 {
16 aux=a[i ];
17 a[ i]=a[ j ];
18 a[ j]=aux;
19 }
20 //−−−−−−−−fim da ordenação do vetor−−−−−−−−−−−−−−−−−
21 printf (" \n" );
22 for ( i=0;i<10;i++)
23 printf ("%d\t",a[ i ]);
24 printf (" \n" );
25 system("PAUSE");
26 return 0;
27 }
CAPÍTULO 1. REVISÃO - ESTRUTURAS DE DADOS HOMOGÊNEAS 9
1.1.2 Ordenação por permutação - Bubblesort
Efetuam-se varreduras repetidas sobre o vetor, deslocando-se a cada passo para a sua extremidade esquerda, o menor
dos elementos do conjunto que restou. Se, para uma troca, o vetor for visualizado na posição vertical ao invés da horizontal,
e com o auxílio da imaginação - os elementos forem bolhas em um tanque de água, com densidades proporcionais ao valor
das respectivas chaves, então cada varredura efetuada sobre o vetor resultaria na ascenção de uma bolha para o nível
apropriado, de acordo com sua densidade (WIRTH, N., 1989)(Vide FIG. 1.4).
Figura 1.4: Exemplo de ordenaçãoBubblesort
O código 1.2, ilustra em linguagem C, o algoritmo de ordenação por permutação(bubblesort)
CAPÍTULO 1. REVISÃO - ESTRUTURAS DE DADOS HOMOGÊNEAS 10
código 1.2: Ordenação por permutação
1 #include <stdio .h>
2 #include < stdlib .h>
3 int main()
4 {
5 int a [10], i , j ,aux;
6 for ( i=0;i<10;i++)
7 {
8 printf (" \ nDigite o %do. valor :" , i +1);
9 scanf ("%d",&a[i]);
10 }
11 //−−−−−−−−inicio da ordenação do vetor−−−−−−−−−−−−−−
12 for ( i=1;i<9;i++)
13 for ( j=9;j>=i; j−−)
14 if (a[ j−1]>a[j ])
15 {
16 aux=a[j−1];
17 a[ j−1]=a[j ];
18 a[ j]=aux;
19 }
20 //−−−−−−−−fim da ordenação do vetor−−−−−−−−−−−−−−−−−
21 printf (" \n" );
22 for ( i=0;i<10;i++)
23 printf ("%d\t",a[ i ]);
24 printf (" \n" );
25 system("PAUSE");
26 return 0;
27 }
CAPÍTULO 1. REVISÃO - ESTRUTURAS DE DADOS HOMOGÊNEAS 11
1.2 Intercalação de vetores
O trecho de código 1.3, exemplifica em linguagem C, o algoritmo de intercalação de dois vetores ordenados gerando
um terceiro vetor também ordenado (Vide também FIG. 1.5).
Figura 1.5: Exemplo de intercalação de dois vetores ordenados gerando um terceiro ordenado
CAPÍTULO 1. REVISÃO - ESTRUTURAS DE DADOS HOMOGÊNEAS 12
código 1.3: Intercalação de dois vetores
1 .
2 .
3 .
4 ix=0,iy=0, iz=0;
5 // intercala dois vetores ordenados(x,y) gerando um terceiro ordenado(z)
6 // enquanto houver elementos no vetor (x) ou no vetor (y)
7 do{
8 if (x[ix]<y[iy ])
9 {
10 z[ iz]=x[ix ];
11 ix++;
12 }
13 else{
14 z[ iz]=y[iy ];
15 iy++;
16 }
17 iz++;
18 }while(ix<n&&iy<m);
19 // armazena no terceiro vetor (z) os valores do vetor (x)
20 // se o vetor (y) terminou
21 while( ix<n)
22 {
23 z[ iz]=x[ix ];
24 ix++;
25 iz++;
26 }
27 // armazena no terceiro vetor (z) os valores do vetor (y)
28 // se o vetor (x) terminou
29 while( iy<m)
30 {
31 z[ iz]=y[iy ];
32 iy++;
33 iz++;
34 }
35 cout<<"\n";
36 .
37 .
38 .
CAPÍTULO 1. REVISÃO - ESTRUTURAS DE DADOS HOMOGÊNEAS 13
1.3 Manipulação de matrizes
Matrizes são estruturas compostas homogêneas com duas dimensões (linha,coluna). Para acessar um endereço na ma-
triz é necessário instanciar os índices relativos à linha e coluna (Vide FIG. 1.2 na seção 1). A seguir é descrito um código
em linguagem C de um algoritmo de multiplicação matricial de duas matrizes (CÓDIGO 1.4).
CAPÍTULO 1. REVISÃO - ESTRUTURAS DE DADOS HOMOGÊNEAS 14
código 1.4: Multiplicação de matrizes
1 #include <stdio .h>
2 #include < stdlib .h>
3 #include <time.h>
4 int main()
5 {
6 float x [10][20], y [20][10], z [10][10], prod;
7 int i , j ,k;
8 srand(time(NULL));
9 //−−−geração aleatória dos valores das matrizes−−−−−−−−
10 for ( i=0;i<10;i++)
11 for ( j=0;j<10;j++)
12 x[ i ][ j]=rand()%10;
13
14 for ( i=0;i<20;i++)
15 for ( j=0;j<20;j++)
16 y[ i ][ j]=rand()%10;
17 //−−−−−−−−−−−−−multiplicação das matrizes−−−−−−−−−−−−−−
18 for ( i=0;i<10;i++)
19 for ( j=0;j<20;j++)
20 {
21 prod=0;
22 for (k=0;k<10;k++)
23 prod+=x[i ][k]*y[k][ j ];
24 z[ i ][ j]=prod;
25 }
26 //−−−−−impressão da matriz resultante−−−−−−−−−−−−−−−−−−
27 printf (" \n" );
28 for ( i=0;i<10;i++)
29 {
30 printf (" \n" );
31 for ( j=0;j<10;j++)
32 printf ("%.2f\ t" ,z[ i ][ j ]);
33 }
34 printf (" \n" );
35 system("PAUSE");
36 return 0;
37 }
CAPÍTULO 1. REVISÃO - ESTRUTURAS DE DADOS HOMOGÊNEAS 15
1.4 Exercícios
1. Desenvolver um programa em linguagem C que leia n notas referentes à disciplina de PC I I (n ≤ 20). O valor
das notas são inteiros que variam variam de 0 a 10. Calcule a freqüência absoluta e freqüência relativa das notas.
Freqüência absoluta é a quantidade de vezes que uma determinada nota ocorre no conjunto e freqüência relativa é a
razão entre a freqüência absoluta e a quantidade de notas (FARRER, H. et al., 1999).
2. Desenvolva um programa em linguagem C que leia uma matriz n×m (n ≤ 50 e m ≤ 60), gerando e escrevendo o
vetor resultante da soma das colunas da matriz.
3. Desenvolva um programa em linguagem C que leia uma matriz 5×5. Gere e escreva a matriz transposta.
4. Desenvolver um programa em linguagem C que leia uma matriz 4×4, calcule e escreva a soma dos elementos acima
da diagonal principal.
5. Desenvolva um programa em linguagem C que leia uma matriz 3×3, calcule e escreva o elemento de menor valor
abaixo da diagonal secundária.
Capítulo 2
Revisão - Modularização de programas
A modularização de programas permite a criação de programas estruturados e modulares. Na linguagem C, a imple-
mentação destes módulos e feita através da criação de funções, que podem receber ou não parâmetros de entrada e retornar
ou não valores após a sua execução.
2.1 Passagem de parâmetros para funções
Na linguagem C, os parâmetros podem ser passados de duas maneiras:
• Por valor: quando uma cópia da(s) variável(is) é(são) passada(s) para a função (Vide ilustração FIG. 2.1);
• Por referência: quando o(s) endereço(s) da variável(is) é(são) passado(s) para a função (Vide ilustração FIG. 2.2);
Obs: no caso de estruturas de dados, a passagem de parâmetro na linguagem C só é possível por referência(Vide
ilustração FIG. 2.3).
16
CAPÍTULO 2. REVISÃO - MODULARIZAÇÃO DE PROGRAMAS 17
código 2.1: Passagem de parâmetro por valor
1 #include <stdio .h>
2 #include < stdlib .h>
3 int exemplo(int A,int B, int C)
4 {
5 int D;
6 D=A+B+C;
7 return D;
8 }
9 int main()
10 {
11 int X,Y,Z;
12 X=10;
13 Y=15;
14 Z=50;
15 printf (" \nSoma = %d",exemplo(X,Y,Z));
16 printf (" \n" );
17 system("PAUSE");
18 return 0;
19 }
O código 2.1 exemplifica, em linguagem C, passagem de parâmetro por valor(Vide também FIG. 2.1):
Figura 2.1: Ilustração da passagem de parâmetro por valor
CAPÍTULO 2. REVISÃO - MODULARIZAÇÃO DE PROGRAMAS 18
código 2.2: Passagem de parâmetro por referência
1 #include <stdio .h>
2 #include < stdlib .h>
3 // Função com passagem de parâmetro por referência
4 int exemplo(int& A,int& B, int& C)
5 {
6 int D;
7 D=A+B+C;
8 return D;
9 }
10 // Módulo principal
11 int main( )
12 {
13 int X,Y,Z;
14 X=10;
15 Y=15;
16 Z=50;
17 printf (" \nSoma = %d",exemplo(X,Y,Z));
18 printf (" \n" );
19 system("PAUSE");
20 return 0;
21 }
O código 2.2 exemplifica, em linguagem C, passagem de parâmetro por referência(Vide também FIG. 2.2):
Figura 2.2: Ilustração da passagem de parâmetro por referência
Os códigos 2.3 e 2.4 exemplificam, em linguagem C, passagem de parâmetro por referência utilizando estruturas de
dados homogêneas(Vide também FIG. 2.3):
CAPÍTULO 2. REVISÃO - MODULARIZAÇÃO DE PROGRAMAS 19
Figura 2.3: Ilustração da passagem de parâmetro por referência utilizando vetor
CAPÍTULO 2. REVISÃO - MODULARIZAÇÃO DE PROGRAMAS 20
código 2.3: Passagem de parâmetro por referência utilizando vetor
1 #include <stdio .h>
2 #include < stdlib .h>
3 // Função com passagem de parâmetro por referência ( vetor X[])
4 void exemplov(int X[], int N)
5 {
6 int I ;
7 for ( I=0;I<N;I++)
8 X[I]=X[I]+2;
9 }
10 // Módulo principal
11 int main()
12 {
13 int A[10],I ,NUM;
14 printf (" \ nDigite o numero de elementos :" );
15 scanf ("%d",&NUM);
16 while(NUM<=0||NUM>10)
17 {
18 printf (" \nErro ......... " );
19 printf (" \ nDigite o numero de elementos :" );
20 scanf ("%d",&NUM);
21 }
22 for ( I=0;I<NUM;I++)
23 {
24 printf (" \ nDigite o %d o. valor :" ,( I +1));
25 scanf ("%d",&A[I]);
26 }
27 exemplov(A,NUM);
28 printf (" \nO vetor modificado .\ n" );
29 for ( I=0;I<NUM;I++)
30 printf ("%d\t",A[I ]);
31 printf (" \n" );
32 system("PAUSE");
33 return 0;
34 }
CAPÍTULO 2. REVISÃO - MODULARIZAÇÃO DE PROGRAMAS21
código 2.4: Passagem de parâmetro por referência utilizando matriz
1 //−−−−−−Imprime a matriz−−−−−−−−−−−−−−
2 void imprime(int M[][10], int m,int n)
3 {
4 int i , j ;
5 for ( i=0;i<m;i++)
6 {
7 printf (" \n" );
8 for ( j=0;j<n;j++)
9 printf ("%d\t",M[i][ j ]);
10 }
11 }
12 //−−−−−−−Soma uma linha da matriz−−−−−
13 int somalin( int M[][10], int n, int l )
14 {
15 int j , soma=0;
16 for ( j=0;j<n;j++)
17 soma+=M[l][j];
18 return soma;
19 }
20 //−−−−−Troca linhas da matriz−−−−−−−−−
21 void troca ( int M[][10], int l1 , int l2 , int n)
22 {
23 int j ,aux;
24 for ( j=0;j<n;j++)
25 {
26 aux=M[l1][j ];
27 M[l1][ j]=M[l2][ j ];
28 M[l2][ j]=aux;
29 }
30 }
CAPÍTULO 2. REVISÃO - MODULARIZAÇÃO DE PROGRAMAS 22
2.2 Tipos de retorno da função
Em C os tipos de retorno possiveis para as funções são: int, float, double e char. Os exemplos dos códigos 2.5 e 2.6,
exemplificam o uso de retorno na função. Observar que a variável de retorno tem que ser do mesmo tipo declarado no
protótipo da função.
CAPÍTULO 2. REVISÃO - MODULARIZAÇÃO DE PROGRAMAS 23
código 2.5: Retorno de tipo float
1 #include <stdio .h>
2 #include < stdlib .h>
3 //−−−−−−função com retorno do tipo float−−−−−−
4 float calcula ( float a, float b)
5 {
6 float c=a*b;
7 return c;
8 }
9 //−−−−−−−−−−−−−−módulo principal−−−−−−−−−−−−−−
10 int main()
11 {
12 float x=5.45,y=8.7;
13 printf (" \nResultado : %f", calcula (x,y ));
14 printf (" \n" );
15 system("PAUSE");
16 return 0;
17 }
No código 2.6, a função retorna nulo (tipo void).
CAPÍTULO 2. REVISÃO - MODULARIZAÇÃO DE PROGRAMAS 24
código 2.6: Retorno de tipo nulo
1 #include <stdio .h>
2 #include < stdlib .h>
3 //−−−−−−Função com retorno tipo nulo −−−−−−−−−−−
4 int calcula ( float a, float b, float & c)
5 {
6 c=a*b;
7 return 0;
8 }
9 //−−−−−−−−−−−−−−módulo principal−−−−−−−−−−−−−−−−
10 int main()
11 {
12 float x=5.45,y=8.7,z;
13 calcula (x,y,z );
14 printf (" \nResultado : %f",z );
15 printf (" \n" );
16 system("PAUSE");
17 return 0;
18 }
2.3 Funções recursivas
Um objeto é dito recursivo se ele consistir parcialmente ou for definido em termos de si próprio (WIRTH, N., 1989).
Como exemplo, o código 2.7 calcula o fatorial de um numero utilizando recursão.
CAPÍTULO 2. REVISÃO - MODULARIZAÇÃO DE PROGRAMAS 25
código 2.7: Cálculo do fatorial com recursividade
1 #include <stdio .h>
2 #include < stdlib .h>
3 // Função recursiva
4 int fatorial ( int n)
5 {
6 if (n==0) return 1;
7 else return n* fatorial (n−1); // chamada recursiva
8 }
9 // Módulo principal
10 int main()
11 {
12 int num;
13 printf (" \ nDigite um valor :" );
14 scanf ("%d",&num);
15 printf (" \ nFatorial de %d = %d\n",num, fatorial (num));
16 system("PAUSE");
17 return 0;
18 }
No código 2.8, o somatório da série S = 11 + 32 + 53 + . . ., com o número de termos n passado como parâmetro para a
função, é calculado utilizando recursão.
CAPÍTULO 2. REVISÃO - MODULARIZAÇÃO DE PROGRAMAS 26
código 2.8: Cálculo do somatório da série com recursividade
1 #include <stdio .h>
2 #include < stdlib .h>
3 // Função recursiva
4 float somatorio( float num,int termos)
5 {
6 if (num>termos)
7 return 0;
8 else return ((2*num−1)/num) + somatorio(num+1,termos);
9 }
10 // Módulo principal
11 int main()
12 {
13 int quant ;
14 printf (" \ nDigite a quantidade de termos :" );
15 scanf ("%d",&quant);
16 printf (" \nResultado do somatorio = %f\n",somatorio (1, quant ));
17 system("PAUSE");
18 return 0;
19 }
CAPÍTULO 2. REVISÃO - MODULARIZAÇÃO DE PROGRAMAS 27
O exemplo do código 2.9, mostra uma função recursiva com duas chamadas, para o cálculo do termo da série de
fibonacci. A Figura 2.4, ilustra o processo de chamada da função recursiva para o cálculo do terceiro termo da série de
fibonacci (DEITEL, H.M. & DEITEL, P.J., 1999).
CAPÍTULO 2. REVISÃO - MODULARIZAÇÃO DE PROGRAMAS 28
código 2.9: Cálculo do termo de fibonacci com recursividade
1 #include < stdlib .h>
2 #include <stdio .h>
3 // Função recursiva
4 int fibonacci ( int n)
5 {
6 if (n==0||n==1) return n;
7 return fibonacci (n−1)+fibonacci(n−2); // chamada recursiva
8 }
9 // Módulo principal
10 int main()
11 {
12 int num;
13 printf (" \ nDigite um valor :" );
14 scanf ("%d",&num);
15 printf (" \nO %do. termo de fibonacci = %d\n",num,fibonacci(num));
16 system("PAUSE");
17 return 0;
18 }
Figura 2.4: Ilustração das chamadas recursivas para o cálculo do terceiro termo de fibonacci
2.4 Exercícios
1. Escrever uma função em C que: receba dois strings como parâmetro, bem como um valor inteiro representando uma
posição; insira o segundo string no primeiro, na posição indicada pelo valor. No programa principal leia os dois
strings, o valor da posição, passe para a função descrita acima e escreva o resultado na tela.
CAPÍTULO 2. REVISÃO - MODULARIZAÇÃO DE PROGRAMAS 29
2. Desenvolva uma função em C , que transforme um número num vetor correspondente à sua representação binária.
3. Desenvolva uma função em C , que recebe como parâmetros um inteiro n e duas matrizes quadradas reais X e Y de
ordem n, sendo a dimensão n lida do teclado. Esta função calcula soma das matrizes X e Y . Escreva no módulo
principal, a matriz gerada na função.
4. Desenvolver uma função recursiva em C para calcular o valor de S da seguinte série: S = 11 − 24 + 39 − 416 + 525 − 636 +
. . .− 10100 (FARRER, H. et al., 1999).
5. O maior divisor comum dos inteiros x e y é o maior inteiro que divide precisamente x e y . Escreva uma função
recursiva mdc que retorne o maior divisor comum de x e y . O maior divisor comum de x e y é definido recursi-
vamente como se segue: Se y for igual a 0(zero), então o mdc(x, y) é x; de outra forma, mdc(x, y) é mdc(y,x%y)
onde %é o operador resto(modulus) (DEITEL, H.M. & DEITEL, P.J., 1999).
Capítulo 3
Ponteiros em C
As variáveis do tipo ponteiro nada mais são do que apontamentos para um endereço de memória. Quando cria-se
uma variável de memória é reservado um espaço para a alocação desta de acordo com o seu tipo. Este espaço passa a ter
um endereço. A variável do tipo ponteiro pode apontar para este endereço, permitindo o acesso ao conteúdo da variável
apontada de maneira indireta (Vide códigos 3.1, 3.2 e 3.3).
30
CAPÍTULO 3. PONTEIROS EM C 31
código 3.1: Primeiro exemplo - utilizando ponteiros
1 #include <stdio .h>
2 #include< stdlib .h>
3 int main()
4 {
5 int a, b, soma, *aptr , *bptr ;
6 printf (" \n Digite um numero inteiro :" );
7 scanf ("%d",&a);
8 printf (" \n Digite um numero inteiro :" );
9 scanf ("%d",&b);
10 aptr = &a ;
11 bptr = &b ;
12 printf (" \n Endereco de %d (&)= %d",a, &a);
13 printf (" \n Endereco da variavel que aponta para %d= %p",a,aptr);
14 printf (" \n Endereco de %d (&)= %d",b,&b);
15 printf (" \n Endereco da variavel que aponta para %d= %p",b,bptr);
16 printf (" \n Fim do programa.\n" );
17 system("PAUSE");
18 return 1;
19 }
CAPÍTULO 3. PONTEIROS EM C 32
código 3.2: Segundo exemplo - utilizando ponteiros
1 #include <stdio .h>
2 #include < stdlib .h>
3 int main()
4 {
5 int a=2, b=3, c=4, i ;
6 int v[10] = {0, 10, 20, 30, 40, 50, 60, 70, 80, 90 } ;
7 int *pt1 , *pt2 , *pt3 , *vaux ;
8 pt1 = &a ; // pt1 recebe o endereco de a
9 pt2 = &b ; // pt2 recebe o endereco de b
10 pt3 = &c ; // pt3 recebe o endereco de c
11 printf (" Endereco de %d e’ %d\n",a,&a);
12 printf (" O valor da variavel que aponta para %d e’ %d\n",a,pt1 );
13 *pt1 = *pt1 + *pt2 + *pt3 ;
14 printf (" O valor da variavel apontada por pt1(*pt1) e’ %d\n",*pt1 );
15 vaux = &v[1] ; // vaux recebe o endereco de v[1]
16printf (" O valor da variavel apontada por vaux (v [1]) e’ %d\n",*vaux);
17 for ( i = 1; i<10; i=i + 2)
18 {
19 *vaux = *vaux + 10 ;
20 printf (" Conteudo de v[ i ] = %d\n" ,*vaux);
21 vaux = vaux + 2 ;
22 }
23 printf (" Fim do programa\n");
24 system("PAUSE");
25 return 1;
26 }
CAPÍTULO 3. PONTEIROS EM C 33
código 3.3: Terceiro exemplo - utilizando ponteiros
1 #include <stdio .h>
2 #include < stdlib .h>
3 int main()
4 {
5 int a, *aptr ;
6 a = 4 ;
7 aptr = &a ; // aptr recebe o endereco de a
8 printf (" \n O endereco de a e’ %d.",&a);
9 printf (" \n O valor de *aptr e’ %p: ", aptr );
10 printf (" \n O valor de a e’ %d: ",a );
11 printf (" \n O valor da variavel apontada por aptr (* aptr ) e’ %d",*aptr );
12 printf (" \n Endereco da variavel apontada por aptr e’ = %p",&*aptr);
13 printf (" \n Conteudo de aptr = %p",aptr );
14 printf (" \n Conteudo do endereco de aptr e’ %p",*&aptr);
15 printf (" \n Fim do programa\n");
16 system("PAUSE");
17 return 1;
18 }
CAPÍTULO 3. PONTEIROS EM C 34
Os ponteiros podem ser utilizados para manipular matrizes, paa passar argumentos por referência para funções, alocar
memória dinâmicamente e para criar estruturas de dados encadeadas como listas, pilhas, filas e árvores binárias.
3.1 Passagem de parâmetro para função utilizando ponteiros
Os Códigos 3.4 e 3.5 ilustram a passagem por referência utilizando ponteiros.
CAPÍTULO 3. PONTEIROS EM C 35
código 3.4: Primeiro exemplo - passagem de parâmetro por referência com ponteiros
1 #include <stdio .h>
2 #include < stdlib .h>
3 // Função simulando passagem de parâmetro
4 // com variável ponteiro
5 int exemplo(int *A,int *B,int *C)
6 {
7 int D;
8 D=*A+*B+*C;
9 return D;
10 }
11 // Função principal
12 int main( )
13 {
14 int X=10,Y=15,Z=50;
15 printf (" \nSoma = %d\n",exemplo(&X,&Y,&Z));
16 system("PAUSE");
17 return 0;
18 }
CAPÍTULO 3. PONTEIROS EM C 36
código 3.5: Segundo exemplo - passagem de parâmetro por referência com ponteiros
1 #include <stdio .h>
2 #include < stdlib .h>
3 // Função simulando passagem de parâmetro
4 // utilizando variável ponteiro
5 void copia(char *s1,char *s2)
6 {
7 for (;* s2!=’ \0 ’ ;s2++,s1++)
8 *s1=*s2;
9 *s1=’\0’ ;
10 }
11 // Função principal
12 int main()
13 {
14 char *frase1 , frase2 [100];
15 gets ( frase2 );
16 copia( frase1 , frase2 );
17 printf ("%s\n", frase1 );
18 system("PAUSE");
19 return 0;
20 }
CAPÍTULO 3. PONTEIROS EM C 37
3.2 Alocação dinâmica de memória
Os códigos 3.6 , 3.7 , 3.8 e 3.9, ilustram códigos em C utilizando ponteiros e alocação dinâmica de memória.
CAPÍTULO 3. PONTEIROS EM C 38
código 3.6: Primeiro exemplo - alocação dinâmica de memória
1 #include <stdio .h>
2 #include < stdlib .h>
3 int main()
4 {
5 int *p,n=10;
6 p=(int *)malloc(n*sizeof ( int ));
7 for ( int i=0;i<n;i++)
8 p[ i]=i*2;
9 for ( int i=0;i<n;i++)
10 printf (" \n%d\t",p[ i ]);
11 system("PAUSE");
12 return 0;
13 }
CAPÍTULO 3. PONTEIROS EM C 39
código 3.7: Segundo exemplo - alocação dinâmica de memória
1 #include <stdio .h>
2 #include < stdlib .h>
3 int main()
4 {
5 int **p;
6 int lin =4,col=5, i , j ;
7 p= ( int **)malloc( lin * sizeof ( int ));
8 for ( i=0;i<lin ; i++)
9 p[ i ]=( int *)malloc(col* sizeof ( int ));
10 for ( i=0;i<lin ; i++)
11 for ( j=0;j<col; j++)
12 p[ i ][ j]=i*j+2;
13 printf (" \n" );
14 for ( i=0;i<lin ; i++)
15 {
16 printf (" \n" );
17 for ( j=0;j<col; j++)
18 printf ("%d\t",p[ i ][ j ]);
19 }
20 printf (" \n" );
21 for ( i=0;i<lin ; i++)
22 free (p[ i ]);
23 free (p );
24 system("PAUSE");
25 return 0;
26 }
CAPÍTULO 3. PONTEIROS EM C 40
código 3.8: Terceiro exemplo - alocação dinâmica de memória com struct
1 #include < stdlib .h>
2 #include<stdio .h>
3 struct dados{
4 int cod;
5 char des [50];
6 };
7 int main()
8 {
9 dados *vet ;
10 int i ,n;
11 printf (" \nEntre com o numero de itens a serem cadastrados :" );
12 scanf ("%d",&n);
13 vet=(dados *)malloc(n*sizeof (dados ));
14 for ( i=0;i<n;i++)
15 {
16 printf (" \ nDigite o codigo :" );
17 scanf ("%d",&vet[i ]. cod);
18 printf (" \ nDigite a descricao :" );
19 scanf ("%d"); // para não saltar o campo descrição
20 gets ( vet [ i ]. des );
21 }
22 printf (" \n" );
23 for ( i=0;i<n;i++)
24 printf (" \n%d\t%s\n",vet[ i ]. cod,vet [ i ]. des );
25 printf (" \n" );
26 system("PAUSE");
27 return 0;
28 }
CAPÍTULO 3. PONTEIROS EM C 41
código 3.9: Quarto exemplo - alocação dinâmica de memória com struct
1 #include < stdlib .h>
2 #include <stdio .h>
3 #include < string .h>
4 struct dados{
5 int cod;
6 char *des;
7 };
8 int main()
9 {
10 dados *vet ;
11 char desc [100];
12 int i ,n;
13 printf (" \nEntre com o numero de itens a serem cadastrados :" );
14 scanf ("%d",&n);
15 vet=(dados *)malloc(n*sizeof (dados ));
16 for ( i=0;i<n;i++)
17 {
18 printf (" \ nDigite o codigo :" );
19 scanf ("%d",&vet[i ]. cod);
20 printf (" \ nDigite a descricao :" );
21 scanf ("%d"); // para não saltar o campo descrição
22 gets (desc );
23 int num=strlen(desc );
24 vet [ i ]. des=(char *)malloc(num*sizeof(char ));
25 strcpy ( vet [ i ]. des ,desc );
26 }
27 printf (" \n" );
28 for ( i=0;i<n;i++)
29 printf (" \n%d\t%s\n",vet[ i ]. cod,vet [ i ]. des );
30 system("PAUSE");
31 return 0;
32 }
CAPÍTULO 3. PONTEIROS EM C 42
3.3 Exercícios
1. Escreva uma função que inverta a ordem dos caracteres de uma cadeia de caracteres que ela recebe como argumento.
Use ponteiro.
Exemplo: ’Saudações’ resulta ’seõçaduaS’ (MIZARAHI, V.V., 2006b).
2. Escreva um programa que solicite ao usuário o número de notas a serem digitadas, crie uma matriz, com a dimensão
especificada, para armazenar as entradas, solicite as notas e chame um função que retorne a média aritmética das
notas. Após imprimir a média, o programa libera a memória alocada para a matriz (MIZARAHI, V.V., 2006b).
3. Desenvolva uma função que receba uma string como argumento e retorne o número de caracteres desta string. Use
ponteiro.
4. Desenvolva uma função que receba duas strings e copie uma string para a outra. Use ponteiro.
5. Desenvolva uma função que receba um vetor de inteiros e ordene-o de maneira crescente. Use ponteiro e alocação
dinâmica de memória.
Capítulo 4
Estruturas Encadeadas
As estruturas encadeadas representam uma seqüência de objetos (células) na memória de um computador e são criadas
a partir de um tipo definido. As estruturas encadeadas que discutiremos neste capítulo são: as listas encadeadas, pilha, fila
e árvore binária.
4.1 Lista simplesmente encadeada
As listas simplesmente encadeadas apontam o endereço da próxima célula em uma única direção, como mostra a
definição da Figura 4.1. A inserção de elementos na lista pode ser feita em qualquer ponto da estrutura. No exemplo do
código 4.2 os elementos são inseridos no final da lista.
Em linguagem C , as listas encadeadas são criadas a partir da definição de um novo tipo de dado definido como o
exemplo a seguir no código 4.1.
código 4.1: Exemplo da definição de um tipo de dado para uma lista simplesmente encadeada
1 struct celula {
2 int elemento;
3 celula *prox;
4 }
5 typedef celula *cel ;
43
CAPÍTULO 4. ESTRUTURAS ENCADEADAS 44
Figura 4.1: Ilustração de uma lista simplesmente encadeada
CAPÍTULO 4. ESTRUTURAS ENCADEADAS 45
código 4.2: Inserção no final de uma lista simplesmente encadeada
1 struct celula {
2 int elemento;
3 celula *prox;
4 };
5 typedef celula *cel ;
6
7 void insere ( int x, cel& ini )
8 {
9 cel nova, atual;
10 if ( ini ==NULL)
11 {
12 ini = new celula ;
13 ini−>elemento=x;
14 ini−>prox=NULL;
15 }
16 else
17 {
18 atual =ini ;
19 while( atual−>prox!=NULL)
20 atual =atual−>prox;
21 nova= new celula ;
22 nova−>elemento=x;
23 nova−>prox=atual−>prox;
24 atual−>prox=nova;
25 }
26 }
CAPÍTULO 4. ESTRUTURAS ENCADEADAS 46
No exemplo do código 4.3 os elementos são inseridos na lista de maneira ordenada.
CAPÍTULO 4. ESTRUTURAS ENCADEADAS 47
código 4.3: Inserção ordenada em uma lista simplesmente encadeada
1 struct celula {
2 int x;
3 celula *prox;
4 };
5 typedef celula *cel ;
6 void insere ( cel &ini, int n)
7 {
8 cel nova, atual ;
9
10 if ( ini ==NULL)
11 {
12 ini =new celula;
13 ini−>x=n;
14 ini−>prox=NULL;
15 }
16 if ( ini−>x>=n)
17 {
18 nova=new celula;
19 nova−>x=n;
20 nova−>prox=ini;
21 ini =nova;
22 }
23 else {
24 atual =ini ;
25 while( atual−>prox!=NULL&&atual−>prox−>x<=n)
26 atual =atual−>prox;
27 nova=new celula;
28 nova−>x=n;
29 nova−>prox=atual−>prox;
30 atual−>prox=nova;
31 }
32 }
CAPÍTULO 4. ESTRUTURAS ENCADEADAS 48
Os elementos da lista também podem ser consultados. O código 4.4, ilustra a consulta de um elemento em uma lista
simplesmente encadeada.
CAPÍTULO 4. ESTRUTURAS ENCADEADAS 49
código 4.4: Consulta a um elemento em uma lista simplesmente encadeada
1 struct celula {
2 int x;
3 celula *prox;
4 };
5 typedef celula *cel ;
6 void consultat ( cel &ini, int n)
7 {
8 cel p;
9 p=ini ;
10 while(p!=NULL)
11 {
12 if (p−>x==n)
13 cout<<p−>x<<"\t";
14 p=p−>prox;
15 }
16 }
Os códigos 4.5 e 4.6, ilustram a exclusão de um elemento da lista e a listagem de todos os elementos de uma lista
encadeada.
CAPÍTULO 4. ESTRUTURAS ENCADEADAS 50
código 4.5: Exclui um elemento de uma lista simplesmente encadeada
1 struct celula {
2 int x;
3 celula *prox;
4 };
5 typedef celula *cel ;
6 void exclui ( cel &ini, int n) // exclui um elemento da lista
7 {
8 cel p,q;
9 q=ini ;
10 while(q−>prox!=NULL&&q−>x!=n)
11 {
12 p=q;
13 q=q−>prox;
14 }
15 if (q−>x==n)
16 {
17 p−>prox=q−>prox;
18 delete q;
19 }
20 else cout<<"\nNao existe . " ;
21 }
CAPÍTULO 4. ESTRUTURAS ENCADEADAS 51
código 4.6: Imprime todos os elementos de uma lista simplesmente encadeada
1 struct celula {
2 int x;
3 celula *prox;
4 };
5 typedef celula *cel ;
6 void lista ( cel &ini)
7 {
8 cel p;
9 p=ini ;
10 while(p!=NULL)
11 {
12 cout<<p−>x<<"\t";
13 p=p−>prox;
14 }
15 }
CAPÍTULO 4. ESTRUTURAS ENCADEADAS 52
4.2 Lista duplamente encadeada
Na lista duplamente encadeada é utilizado dois apontadores, permitindo que se percorra a lista nos dois sentidos. A
Figura 4.2 ilustra esta estrutura.
Figura 4.2: Ilustração de uma lista duplamente encadeada
No código 4.7 é mostrado a definição de uma estrutura tipo lista duplamente encadeada.
código 4.7: Exemplo da definição de um tipo de dado para uma lista duplamente encadeada
1 struct celula {
2 int elemento;
3 celula *dir ,*esq;
4 };
5 typedef celula *cel ;
CAPÍTULO 4. ESTRUTURAS ENCADEADAS 53
O exemplo do código 4.8 demonstra código para inclusão de uma nova célula no final de uma lista duplamente enca-
deada.
CAPÍTULO 4. ESTRUTURAS ENCADEADAS 54
código 4.8: Inclusão de elementos no final de uma lista duplamente encadeada
1 struct celula {
2 int elemento;
3 celula *dir ,*esq;
4 };
5 typedef celula *cel ;
6
7 void insere ( int x, cel &ini)
8 {
9 cel nova, atual ;
10 if ( ini ==NULL)
11 {
12 ini =new celula;
13 ini−>elemento=x;
14 ini−>dir=NULL;
15 ini−>esq=NULL;
16 }
17 else
18 {
19 atual =ini ;
20 while( atual−>dir!=NULL)
21 atual =atual−>dir;
22
23 nova=new celula;
24 nova−>elemento=x;
25 nova−>dir=atual−>dir;
26 atual−>dir=nova;
27 nova−>esq=atual;
28 }
29 }
CAPÍTULO 4. ESTRUTURAS ENCADEADAS 55
No código 4.9 é exemplificado uma função para excluir uma célula de uma lista duplamente encadeada.
CAPÍTULO 4. ESTRUTURAS ENCADEADAS 56
código 4.9: Exclui elementos em uma lista duplamente encadeada
1 struct celula {
2 int elemento;
3 celula *dir ,*esq;
4 };
5 typedef celula *cel ;
6
7 void exclui ( int x, cel &ini)
8 {
9 cel p,q;
10 p=ini ;
11 if ( ini−>elemento==x)
12 {
13 ini =ini−>dir;
14 delete p;
15 ini−>esq=NULL;
16 }
17 else{
18 p=ini ;
19 while(p−>dir−>dir!=NULL)
20 {
21 q=p;
22 p=p−>dir;
23 if (p−>elemento==x)
24 {
25 q−>dir=p−>dir;
26 p−>dir−>esq=q;
27 delete p;
28 }}}
29 if (p−>dir−>elemento==x)
30 {
31 p−>dir=NULL;
32 delete p−>dir;
33 }
34 else cout<<"\nNao existe .\ n";
35 }
CAPÍTULO 4. ESTRUTURAS ENCADEADAS 57
O código 4.10 ilustra a impressão de todos os elementos de uma lista duplamente encadeada nos dois sentidos.
CAPÍTULO 4. ESTRUTURAS ENCADEADAS 58
código 4.10: Imprime os elementos lista duplamente encadeada
1 struct celula {
2 int elemento;
3 celula *dir ,*esq;
4 };
5 typedef celula *cel ;
6 void lista ( cel &ini)
7 {
8 cel p;
9 p=ini ;
10 while(p−>dir!=NULL)
11 {
12 cout<<p−>elemento<<"\t";
13 p=p−>dir;
14 }
15 cout<<p−>elemento<<"\n";
16
17 while(p−>esq!=NULL)
18 {
19
20 cout<<p−>elemento<<"\t";
21 p=p−>esq;
22 }
23 cout<<p−>elemento;
24 }
CAPÍTULO 4. ESTRUTURAS ENCADEADAS 59
No código 4.11 é apresentado código em linguagem C para inserção de elementos de maneira ordenada(crescente) em
uma lista duplamente encadeada.
CAPÍTULO 4. ESTRUTURAS ENCADEADAS 60
código 4.11: Insere ordenado em uma lista duplamente encadeada
1 struct celula {
2 int elemento;
3 celula *dir ,*esq;
4 };
5 typedef celula *cel ;
6
7 void insere ( int x, cel &ini) // insere ordenado
8 {
9 cel nova, atual ;
10 if ( ini ==NULL)
11 {
12 ini =new celula;
13 ini−>elemento=x;
14 ini−>dir=NULL;
15 ini−>esq=NULL;
16 }
17 else if ( ini−>elemento>=x)
18 {
19 nova=new celula;
20 nova−>elemento=x;
21 nova−>dir=ini;
22 nova−>esq=ini−>esq;
23 ini−>esq=nova;
24 ini =nova;
25 }
26 else {
27 atual =ini ;
28 while( atual−>dir!=NULL&&atual−>dir−>elemento<=x)
29 atual =atual−>dir;
30 nova=new celula;
31 nova−>elemento=x;
32 nova−>dir=atual−>dir;
33 atual−>dir=nova;
34 atual−>dir−>esq=nova;
35 nova−>esq=atual;
36 }
37 }
CAPÍTULO 4. ESTRUTURAS ENCADEADAS 61
4.3 Pilha
Uma lista encadeada com a restrição de só permitir a inclusão de um novo elemento no inicio da estrutura e como regra
para a saida "último elemento que entra é o primeiro que sai", é chamada de uma pilha. Sua estrutura pode ser definida
como no Código 4.12. Vide também a representação de um pilha na Figura 4.3.
Figura 4.3: Ilustração de um ’pilha’
código 4.12: Estrutura de dados para uma ’pilha’
1 struct celula {
2 char x;
3 celula *prox;
4 };
5 typedef celula *pilha ;
CAPÍTULO 4. ESTRUTURAS ENCADEADAS 62
O código 4.13 ilustra uma função que insere elementos em uma pilha.
CAPÍTULO 4. ESTRUTURAS ENCADEADAS 63
código 4.13: Função para empilhar
1 struct celula {
2 char x;
3 celula *prox;
4 };
5 typedef celula *pilha ;
6 //−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−
7 void empilha( pilha &topo,char n){
8 pilha nova;
9 if (topo==NULL){
10 topo=new celula;
11 topo−>x=n;
12 topo−>prox=NULL; }
13 else{
14 nova=new celula;
15 nova−>x=n;
16 nova−>prox=topo;
17 topo=nova;}}
A função para retirar elementos da pilha, é mostrada na função no código 4.14.
CAPÍTULO 4. ESTRUTURAS ENCADEADAS 64
código 4.14: Função para ’desempilhar’
1 struct celula {
2 char x;
3 celula *prox;
4 };
5 typedef celula *pilha ;
6 void desempilha( pilha &topo)
7 {
8 pilha p=topo;
9 cout<<"\n";10 while(p!=NULL) {
11 cout<<topo−>x<<"\t";
12 topo=topo−>prox;
13 delete p;
14 p=topo; }
15 }
4.4 Fila
Uma lista encadeada com a restrição de só permitir a inclusão de um novo elemento no fim da estrutura e como regra
para a saida "primeiro elemento que entra é o primeiro que sai", é chamada de uma fila. Vide códigos 4.15, 4.16 e 4.17 e
Figura 4.4.
Figura 4.4: Ilustração de uma ’fila’
CAPÍTULO 4. ESTRUTURAS ENCADEADAS 65
código 4.15: Estrutura de dados para uma ’fila’
1 struct celula {
2 int elemento;
3 celula *prox;
4 };
5 typedef celula * fila ;
código 4.16: Funçãp para ’enfileirar’
1 struct celula {
2 int elemento;
3 celula *prox;
4 };
5 typedef celula * fila ;
6
7 void enfileira ( fila &ini, fila &final , int y)
8 {
9 fila nova;
10 if ( ini ==NULL)
11 {
12 ini =new celula;
13 ini−>elemento=y;
14 ini−>prox=NULL;
15 final =ini ;
16 }
17
18 else{
19 nova= new celula ;
20 nova−>elemento=y;
21 nova−>prox=NULL;
22 final −>prox=nova;
23 final =nova;
24 }
25 }
CAPÍTULO 4. ESTRUTURAS ENCADEADAS 66
código 4.17: Função para ’desenfileirar’
1 struct celula {
2 int elemento;
3 celula *prox;
4 };
5 typedef celula * fila ;
6 void desenfileira ( fila &ini)
7 {
8 fila atual ;
9 cout<<"\n";
10 while(1)
11 {
12 atual =ini ;
13 if ( atual ==NULL) break;
14 cout<<atual−>elemento<<"\t";
15 ini =ini−>prox;
16 delete atual ;
17 }
18 }
CAPÍTULO 4. ESTRUTURAS ENCADEADAS 67
4.5 Árvore Binária
A Figura 4.5 ilustra a estrutura de uma árvore binária.
Figura 4.5: Ilustração de uma árvore binária
Os códigos 4.19, 4.20 e 4.21 foram propostos por (ZIVIANI, N., 2004).
código 4.18: Estrutura de dados para uma árvore binária
1 struct celula {
2 float elemento;
3 celula *esq,* dir ;
4 };
5 typedef celula *arvore ;
CAPÍTULO 4. ESTRUTURAS ENCADEADAS 68
código 4.19: Inserção de dados em uma árvore binária ordenada
1 struct celula {
2 float elemento;
3 celula *esq,* dir ;
4 };
5 typedef celula *arvore ;
6 void insere ( float x, arvore &raiz)
7 {
8 if ( raiz ==NULL)
9 {
10 raiz =new celula;
11 raiz−>elemento=x;
12 raiz−>esq=NULL;
13 raiz−>dir=NULL;
14 return;
15 }
16 else{
17 if (x<raiz−>elemento)
18 insere (x, raiz−>esq);
19 else insere (x, raiz−>dir);
20 }
21 }
CAPÍTULO 4. ESTRUTURAS ENCADEADAS 69
Figura 4.6: Ilustração de uma árvore binária ordenada
O código 4.20 imprime os dados da árvore binária da Figura 4.6 da seguinte maneira (confira o código 4.20):
• inordem : 10 20 30 50 60 70 80
• preordem: 50 20 10 30 70 60 80
• posordem: 10 30 20 60 80 70 50
CAPÍTULO 4. ESTRUTURAS ENCADEADAS 70
código 4.20: Impressão inordem, preordem e posordem em uma árvore binária ordenada
1 struct celula {
2 float elemento;
3 celula *esq,* dir ;
4 };
5 typedef celula *arvore ;
6 void inordem(arvore &raiz)
7 {
8 if ( raiz ==NULL)
9 return;
10 else{
11 inordem(raiz−>esq);
12 cout<<"\n"<<raiz−>elemento;
13 inordem(raiz−>dir);
14 }
15 }
16 void preordem(arvore &raiz)
17 {
18 if ( raiz ==NULL)
19 return;
20 else{
21 cout<<"\n"<<raiz−>elemento;
22 preordem(raiz−>esq);
23 preordem(raiz−>dir);
24 }
25 }
26 void posordem(arvore &raiz)
27 {
28 if ( raiz ==NULL)
29 return;
30 else{
31 posordem(raiz−>esq);
32 posordem(raiz−>dir);
33 cout<<"\n"<<raiz−>elemento;
34 }
35 }
CAPÍTULO 4. ESTRUTURAS ENCADEADAS 71
código 4.21: Exclusão de um elemento em uma árvore binária ordenada
1 void antecessor ( arvore p, arvore &r)
2 {
3 if ( r−>dir!=NULL)
4 {
5 antecessor (p, r−>dir);
6 return;
7 }
8 p−>elemento=r−>elemento;
9 p=r;
10 r=r−>esq;
11 delete p;
12 }
13 void retira ( float x, arvore &raiz)
14 {
15 if ( raiz ==NULL)
16 {
17 cout<<"\nRegistro inexistente . " ;
18 return;
19 }
20 if (x<raiz−>elemento)
21 {
22 retira (x, raiz−>esq);
23 return;
24 }
25 if (x>raiz−>elemento)
26 {
27 retira (x, raiz−>dir);
28 return;
29 }
30 if ( raiz−>dir==NULL)
31 {
32 arvore aux=raiz ;
33 raiz =raiz−>esq;
34 delete aux;
35 return;
36 }
37 if ( raiz−>esq!=NULL)
38 {
39 antecessor ( raiz , raiz−>esq);
40 return;
41 }
42 arvore aux=raiz ;
43 raiz =raiz−>dir;
44 delete aux;
45 }
CAPÍTULO 4. ESTRUTURAS ENCADEADAS 72
4.6 Exercícios
1. Desenvolva uma função que copie um vetor de inteiros para uma lista simplesmente encadeada.
2. Desenvolva uma função que remova a k-ésima célula de uma lista encadeada.
3. Desenvolva uma função que insira na lista uma nova célula com conteúdo de inteiro x entre a k-ésima e a k+1-ésima
células.
4. Desenvolva uma função que remova de uma lista duplamente encadeada todos os elementos que contêm y .
5. Desenvolva uma função que desempilhe(Pilha1) e empilhe(Pilha2), todos os elementos que estão originalmente em
Pilha1.
Capítulo 5
Arquivos em C
Neste capítulo vamos tratar dos objetos persistentes(memória secundária, arquivos em disco rígido) em comparação
com os objetos temporários(memória principal) vistos até o momento.
Na linguagem C, podemos tratar com arquivos de duas maneiras: alto nível (’bufferizada’) e baixo nível, onde os ’buf-
fers’ são mantidos pelo programador da aplicação. Aqui iremos tratar da operação com arquivos em alto nível utilizando
as funções da biblioteca stdio.h(vide código 5.1).
73
CAPÍTULO 5. ARQUIVOS EM C 74
código 5.1: Definição da struct FILE do arquivo stdio.h
1 #define OPEN_MAX 20
2 typedef struct {
3 int level ;
4 unsigned flags ; /* File status flags */
5 charfd ; /* File descriptor */
6 unsignedcharhold ;
7 int bsize ; /* Buffersize */
8 unsignedchar _FAR *buffer;
9 unsignedchar _FAR *curp; /*Current active pointer */
10 unsigned istemp; /*Temporary file indicator */
11 shorttoken ; /*Used for validity checking*/
12 } FILE;
13 extern FILE _streams[ OPEN_MAX ];
Algumas funções disponíveis(stdio.h):
• fopen, fclose, fseek, ftell
• getc,putc
• fgets,fputs
• fscanf,fprintf
• fread,fwrite
5.1 Abertura e fechamento de arquivo
5.1.1 Abertura de arquivo
Função fopen( ): preenche inicialmente a estrutura FILE retornando um apontador para a mesma(vide exemplo de
utilização no código 5.2).
CAPÍTULO 5. ARQUIVOS EM C 75
código 5.2: Exemplo da utilização da função fopen e da função putc
1 #include <stdio .h>
2 int main( )
3 {
4 FILE *ptr ; int ch;
5 ptr =fopen(" arqtext . txt " , "w");
6 while( (ch=getche( ) ) != ’ \ r ’ )
7 putc(ch, ptr );
8 fclose ( ptr );
9 return 0;
10 }
Protótipo da função fopen ⇒ FILE *fopen(const char *filename,const char *mode);
Modos de operação(argumento const char *mode):
• r abre para leitura apenas;
• w cria para escrita. Se o arquivo existir será sobrescrito;
• a adicionar; abre para escrita no final do arquivo; cria um novo caso não exista;
• adicionando ’+’ implica em poder também atualizar;
• t indica texto; b binário.
5.1.2 Fechamento de arquivo
Protótipo da função fclose ⇒ int fclose(FILE *stream);
• fclose fecha o arquivo
• todos os buffers são descarregados;
• todas as áreas de comunicação alocados pelo sistema são liberados (FILE,buffers);
• valor de retorno(0 se sucesso, EOF caso contrário).(Vide exemplo de utilização no código 5.2).
5.2 Escrevendo e lendo caracteres no arquivo
5.2.1 Escrevendo caracter no arquivo
Protótipo da função putc ⇒ int putc(int c, FILE *stream);
• grava um caracter no arquivo;
CAPÍTULO 5. ARQUIVOS EM C 76
código 5.3: Exemplo da utilização da função getc
1 #include <stdio .h>
2 int main( )
3 {
4 FILE *ptr ;
5 int ch;
6 ptr =fopen(" arqtext . txt " , "r" );
7 while( (ch=getc( ptr )) != EOF )
8 putchar (ch );
9 fclose (ptr );
10 return 0;
11 }
• valor retornado(se sucesso, retorna o caracter gravado, caso contrário, EOF)(Vide exemplo de utilização no Có-
digo 5.2).
5.2.2 Lendo caracter no arquivo
Protótipo da função putc ⇒ int getc(FILE *stream);
• complemento de putc;
• lê um caracter do arquivo;
• retorna o próximo caracter, incrementando o apontador (aponta para próximo caracter);
• valor retornado(se sucesso, retorna o caracter lido, EOF caso contrário)(Vide exemplo de utilização no código 5.3).
5.2.3 Contando caracteres no arquivo
CAPÍTULO 5. ARQUIVOS EM C 77
código 5.4: Contando caracter em um arquivo
1 #include<stdio .h>
2 #include< stdlib .h>
3 int main()
4 {
5 FILE *ptr ;
6 char Path [30], ch;
7 int conta = 0;
8 puts ("Digite o nome do arquivo: " );
9 gets (Path );
10 ptr=fopen(Path , "rb" );
11 if ( ptr==NULL)
12 printf (" \nErro na abertura do arquivo . " );
13 while(getc ( ptr )!=EOF) conta++;
14 fclose ( ptr );
15 printf (" \n O arquivo tem %d caracteres " , conta );
16 system("PAUSE");
17 return 0;
18 }
Por que o número de caracteres é menor do que o indicado pelo Windows Explorer?
Texto x Binário
• caracter - 1 byte
• números (int - 4 bytes, float - 4 bytes e etc)
• modo texto (um número é gravado como um string; 1204347.20 - 4 bytes de memória principal, 10 bytes em disco;
ineficiente se lidamos com números e dados estruturados
• modo binário (incompatibilidade entre C e Ms-Dos, difere na interpretação de nova linha e na forma de representação
de fim de arquivo
5.2.4 Gravando linha a linha no arquivo
CAPÍTULO 5. ARQUIVOS EM C 78
código 5.5: Gravando linha a linha
1 #include <stdio .h>
2 #include < stdlib .h>
3 #include < string .h>
4 int main()
5 {
6 FILE *ptr ;
7 char string [81];
8 ptr=fopen(" arqtext . txt " , "w");
9 while( strlen ( gets ( string ) ) > 0 )
10 {
11 fputs ( string , ptr );
12 fputs ( " \n", ptr );
13 }
14 fclose ( ptr );
15 system("PAUSE");
16 return 0;
17 }
Protótipo da função fputs ⇒ int fputs(const char *s, FILE *stream);
• copia string terminado em null para um arquivo
• não acrescenta caractere de nova linha
• não copia ’\0’
• valor de retorno( se sucesso retorna um valor não negativo, EOF caso contrário)
5.2.5 Lendo linha a linha
Referências 79
código 5.6: Lendo linha a linha
1 #include <stdio .h>
2 #include < stdlib .h>
3 int main()
4 {
5 FILE *ptr ;
6 char string [81];
7 ptr=fopen(" arqtext . txt " , "r" );
8 while( fgets ( string , 80, ptr ) != NULL)
9 puts ( string );
10 system("PAUSE");
11 fclose ( ptr );
12 return 0;
13 }
Protótipo da função fgets ⇒ char *fgets(char *s,int n, FILE *stream);
• lê caracteres do arquivo para o string s
• para após a leitura de n -1 caracteres ou do caractere de nova linha (o que vier primeiro)
• fgets retém o valor do caracter de nova linha
• adicionando um byte (caracter)null marcando o final do string
• valor de retorno ( se sucesso retorna um ponteiro para s, NULL, caso contrário)
Referências
DEITEL, H.M., & DEITEL, P.J. (1999). Como programar em C. LTC editora. (Tradução Amir Kurban, Msc. IME)
FARRER, H., BECKER, C.G., FARIA, E.C., MATOS, H.F., SANTOS, M.A., & MAIA, M.L. (1999). Algoritmos Estru-
turados. LTC - editora - 3a. edição.
HOLLOWAY, J.P. (2006). Introdução à Programação para Engenharia. LTC editora. (Tradução de Sueli Cunha - Depar-
tamento de Matemática da Universidade Gama Filho)
LANGSAM, Y., AUGENSTEIN, M. J., & TENENBAUM, A. M. (1996). Data Structures Using C and C++. Prentice-Hall,
Inc.
MIZARAHI, V.V. (2006a). Treinamento em Linguagem C++ módulo 1. Pearson Prentice Hall - 2a. edição.
Referências 80
MIZARAHI, V.V. (2006b). Treinamento em Linguagem C++ módulo 2. Pearson Prentice Hall - 2a. edição.
TENENBAUM, A. M., LANGSAM, Y., & AUGENSTEIN, M. J. (1995). Estruturas de Dados Usando C. Makron Books.
WIRTH, N. (1989). Algoritmos e Estruturas de Dados. Prentice-Hall do Brasil.
ZIVIANI, N. (2004). Projetos de Algoritmos: com implementações em Pascal e C. Pioneira Thomson Learning - 2a.
edição.
Referências 81
Índice Remissivo
Índice Remissivo
bubblesort, 9
estrutura de dados homogênea, 6
estruturas compostas homogêneas, 6
linguagem C, 6, 16, 18
ordenação de vetores, 7
ordenação por permutação, 9
passagem de parâmetro por referência, 18
passagem de parâmetro por valor, 17
Por referência, 16
Por valor, 16
82
	Revisão - Estruturas de dados homogêneas
	Ordenação de vetores
	Ordenação por seleção direta
	Ordenação por permutação - Bubblesort
	Intercalação de vetores
	Manipulação de matrizes
	Exercícios
	Revisão - Modularização de programas
	Passagem de parâmetros para funções
	Tipos de retorno da função
	Funções recursivas
	Exercícios
	Ponteiros em C
	Passagem de parâmetro para função utilizando ponteiros
	Alocação dinâmica de memória
	Exercícios
	Estruturas Encadeadas
	Lista simplesmente encadeada
	Lista duplamente encadeada
	Pilha
	Fila
	Árvore Binária
	Exercícios
	Arquivos em C
	Abertura e fechamento de arquivo
	Abertura de arquivo
	Fechamento de arquivo
	Escrevendo e lendo caracteres no arquivo
	Escrevendo caracter no arquivo
	Lendo caracter no arquivo
	Contando caracteres no arquivo
	Gravando linha a linha no arquivo
	Lendo linha a linha
	Referências