Apostila
ESTRUTURAS DE DADOS ESTÁTICAS
Utiliza os Comandos CIN e COUT da Linguagem C++ Para Entrada e Saída de Dados
Apresenta Exemplos de Manipulação das Estruturas de Dados Básicas
( Com Exercícios Adicionais )
Prof. Antônio Carlos Guimarães Salgado
Laboratório Nacional de Computação Científica – LNCC
&
Prof. Reginaldo S. Figueiredo – M.C.
Instituto Militar de Engenharia – IME
Janeiro.2007
APRESENTAÇÃO
O objetivo deste material é mostrar os fundamentos das estruturas de dados estáticas,
utilizadas em sistemas computacionais, assim como alguns algoritmos para suas manipulações.
Para tanto foi assumido que seria mais eficaz apresentá-las utilizando-se a linguagem de
programação C. Mais ainda; para otimizar a facilidade de compreenssão foram adotados os
comandos de entrada e saída da linguagem C++ “cin” e ”cout”.
Em função disso, a primeira parte do mateiral apresenta as principais características e
facilidades da linguagem C – incluindo os comandos de I/O printf, scanf, getchar, putchar), gets e
puts - mais as explicações necessárias à utilização dos comandos de entrada e saída de dados “cin” e
”cout” do ambiente C++.
Já as segunda parte concentra-se em mostrar os conceitos das estruturas de dados básicas,
incluidos aí alguns algoritmos tradicionais – codificados em linguagem C.
Também foram incluídas explanações simplificadas sobre técnicas para Ordenções de
“arrays” unidimensionais - Vetores – e Busca de dados, além de um resumo sobre Recursividade.
PARTE I
1. Introdução
2
1.1. Características
 linguagem de médio nível;
 linguagem estruturada;
 versátil (aplicação em várias áreas);
 portável;
 código eficiente;
 compilação condicional;
 compilação separada (funções em vários arquivos);
 linguagem para o programador.
1.2. Histórico da Linguagem C
 BCPL  B  C  C++
 C - 1971 - Kernighan e Ritchie (K & R)
 C ANSI (American National Standards Institute) - 1989
1.3. Características de um programa
 Um programa em C é composto por pelo menos uma função, a função "main";
 Todo programa em C começa a sua execução a partir da função "main";
 Normalmente, um programa em C é uma coleção de funções de pequeno tamanho;
 Toda função tem um tipo;
 Palavras reservadas e funções da biblioteca do C são sempre escritas com letras minúsculas.
1.4. Pré-processador e Diretivas
O pré-processador é um programa que age antes do compilador da linguagem C aumentando sua
capacidade e auxiliando a portabilidade. Ele se orienta por diretivas (que iniciam sempre pelo sinal #),
que só valem no arquivo onde estão definidas ou nos arquivos incluídos abaixo delas.
As principais diretivas são o #include e o #define.
1.4.1.
# include
Permite incluir o conteúdo de um arquivo no programa.
Exemplos: #include <stdio.h>
#include "stdio.h"
#include <iostream>

procura stdio.h no diretório de arquivos header
 procura stdio.h no diretório corrente
 procura iostream no diretório de arquivos header
Observação: em alguns compiladores o serviço system (“pause”); se encontra na biblioteca cstdl. Ele
permite uma pausa no programa até que o usuário digite qualquer tecla, ib.
O comando #include <iostream> é usada para incluir o acesso a biblioteca padrão de entrada e
saída de dados do C++. A <iostream> é uma biblioteca usada para entrada e saída de dados. Ela
3
fornece o objeto std::cout, que serve para enviar uma mensagem para a tela e utiliza o operador <<,
que indica: envie estes caracteres para saída (cout = C out) e, também, objeto std::cin, que é usado para
entrada de dados. Observe o uso do operador >> que indica: armazene a entrada do usuário neste objeto
e do operador << que indica: armazene o dado digitado na varável especificada logo após ele.
Obs.: Em ambiente DOS, system (“cls”) proporciona a limpeza da tela (enche a tela de espaços em
branco) e system (“pause”), exibe uma mensagem na tela indicando que haverá uma pausa até que seja
digitada uma tecla. No entanto, esta segunda chamada necessita a inclusão da biblioteca cstdlib
(#include <cstdlib>) no início do programa.
1.4.2.
# define
Serve para definir uma constante simbólica. Por exemplo:
#define TRUE 1
#define FALSE 0
#define MENS_ERRO "Erro. Divisão por zero.\n"
#define MAX_TAM 100
As constantes assim definidas podem ser usadas para atribuir valores a variáveis, passadas como
parâmetros e para comparações dentro do programa. Ex.:
int erro;
...
erro = FALSE;
if (a == 0)
flag = TRUE;
...
if (erro) cout << MENS_ERRO;
Outra finalidade do #define é criar macro funções. Por exemplo:
# define MIN(a, b) ((a) < (b) ? (a) : (b))
então: se: a = MIN(x, 3);  a = ((x) < (3) ? (x) : (3));
#define streq (x, y) (strcmp((x), (y)) == 0)
#define strlt (x, y) (strcmp((x), (y)) < 0)
#define strgt (x, y) (strcmp((x), (y)) > 0)
/* iguais */
/* x < y */
/* x > y */
Para que se possa reutilizar uma constante devemos torná-la antes indefinida, usando a diretiva #undef
a seguir redefini-la novamente usando outro #define. Por exemplo:
a) # define NOME "teste"
...
# undef NOME
# define NOME "testando"
b) #define TAM 100
#define COMP 100
4
char vetor_a [ TAM ][ COMP ]
#undef COMP
#define COMP 200
char vetor_b [TAM][COMP]
1.4.3.
namespace
O que é um namespace ?
Como o próprio nome diz, signifca espaço para nomes.
Quando você monta seu programa utilizando bibliotecas externas, podem ocorrer duplicações de
nomes, isto é; um objeto defnido em uma das bibliotecas tem o mesmo nome de um objeto defnido por
você.
Por exemplo: você criou as funções min ( ) e max ( ), que retornam o menor e maior valor de um
vetor. Mas a STL – biblioteca padrão para tratamento de vetores em C++  já tem estas funçõese , por
isso, o compilador não “saberá” que função min( ) e max ( ) você quer chamar.
Solucionar o problema da duplicação de nomes pode ser complexo, pois se estes nomes pertencerem
a bibliotecas externas, você precisaria contatar os desenvolvedores destas bibliotecas para resolver os
confitos, ou renomear seus objetos e funções. O namespace veio para resolver este problema.
Para usar os objetos standart de C++ é preciso incluir a palavra std e a seguir o operador de
resolução de escopo, isto é: std::nomeObjeto;
std::cout < < “ Entre com x : “;
std::cin > > x ;
Mas é possível utilizr os objetos standarts de C++ diretamente, isto é, sem o uso de std::. Para tal
basta colocar a declaração using namespace std no início do programa.
// Exemplo: Declara que vai usar os objetos standart de C++
…
using namespace std;
int x = 3 ;
cout < < “ Entre com x : “;
cin > > x ;
1.5. Formato de um programa em C
5
"definições"
função_1
função_2
...
função_n
funcão_main /* A ordem das funções dentro de um programa pode ser qualquer. */
1.5.1. Exemplo de um programa
#include <iostream>
using namespace std;
void main ( )
{
int i;
i = 10;
cout << "\n i = “ << i;
}
/* instrução para o pré-processador incluir a biblioteca “iostream” */
/* início da função main */
/* início de bloco */
/* define “i” como uma variável do tipo inteiro */
/* inicia “i” */
/* chama função de impressão */
/* fim de bloco */
/* toda instrução termina por ” ; “ e o protótipo de printf está em stdio.h (standard IO)
2. Identificadores
São usados em nomes de funções e variáveis.
A maioria dos compiladores reconhece 31 caracteres tanto para variáveis quanto para funções, e:




Devem começar por letra ou '_';
Normalmente se usam letras minúsculas;
Não podem ser iguais às palavras reservadas;
Minúsculas são compredidas como diferentes de maiúsculas (e.g.: ABC Abc  ABc  abc).
3. Tipos de Dados para Variáveis e Funções
3.1. Standard (já definidos na linguagem)
caracter
inteiro
inteiro duplo
real
real duplo
nada
char
int
long int
float
double
void
(1 caractere)
(2 bytes)
(4 bytes)
(4 bytes)
(8 bytes)
(0 bytes)
6
O tipo inteiro possui o tamanho da palavra da CPU.
Tipo
Tamanho em Bits
Faixa
Char
8
0 a 255
int
16
-32768 a 32767
long int
32
–2,147,483,648 a 2,147,483,647
Float
32
6 dígitos
Doublé
64
12 dígitos
Void
0
Sem valor
3.2. Modificadores de tipo
Alteram o significado do tipo standard.
 signed (com sinal)
 unsigned (sem sinal)
 long (passa inteiro de 2 bytes para 4 bytes)
 short (passa inteiro de 4 bytes para 2 bytes)
Se tipo int: long int = long 
short int = int

Exemplos: signed char
unsigned int
4 bytes
2 bytes


128 a 127
0 a 65535
4. Declaração de Variáveis
Variáveis devem ser declaradas antes de serem usadas.
Formato:
<tipo> <lista de variáveis);
Exemplos: int
float
double
char
a, b, c;
soma;
somatorio, raiz_quadrada;
sim, nao;
As variáveis podem ser definidas dentro de qualquer bloco:
{
int x, y;
< bloco de comandos >;
}
4.1. Variáveis locais
7
São as declaradas dentro de blocos e só são reconhecidas dentro do bloco de declaração.
// Exemplo:
#include <iostream>
using namespace std;
void main ( )
{
int i, j;
i = 2;
j = 2 * i;
cout << "O dobro de “, i , “ = \n" << j;
}
/* No exemplo acima, “ i “ e “ j “ são variáveis locais da função “main” . */
// Exemplo:
void f1 ( )
{
int x;
x = 5;
...
if (a > 10)
{
int x, y;
x = 20;
y = 40;
...
}
}
No exemplo, a variável x tem o valor 5 quando sair do bloco mais interno.
4.2. Parâmetros formais – são os parâmetros das funções.
Quando parâmetros são passados por valor a função só recebe cópia do conteúdo da variável.
Exemplo: int soma (int a, int b)
{
return (a + b);
}
No exemplo, a e b são parâmetros formais e a função soma poderia ser chamadadas seguintes formas:
j = soma (2, 3);
ou x = soma (a, b);
8
4.3. Variáveis globais
São reconhecidas por todas as funções de um programa ou de um arquivo.
// Exemplo:
#include <iostream>
using namespace std;
void F ( void );
int cont;
void main ( )
{
cont = 100;
cout << “Cont em main = “ << cont;
cont = cont + 1;
f ( );
}
void F ( )
{
cout << "Cont em F = " << cont << “\n”;
}
4.4. Modificadores de classe de armazenamento
Indicam como as variáveis devem ser armazenadas.
Exemplo de mapa da memória de um programa em C em um equipamento genérico:
Stack
Heap
Variáveis Estáticas e
Globais
Área de Código
9
4.4.1. Variáveis automáticas – auto – são as variáveis definidas normalmente.
Exemplo: int x; <=> auto int x;
A palavra auto não é necessária.
4.4.2. Variáveis externas – extern – são variáveis globais definidas em arquivos diferentes.
// Exemplo: arquivo 1:
void main ( )
{
int x, y;
y = 30;
x = 10;
f ( );
...
}
// arquivo 2:
extern int x, y;
void f ( )
{
...
cout << X = " << x << “\nY = “ << y;
...
}
4.4.3. Variáveis estáticas - static
A variável não perde o seu valor dentro da função ou arquivo.
Este tipo de variável é mais empregado para definição de strings.
Quando uma função é definida como static, ela só pode ser ativada por uma função que esteja no
mesmo arquivo.
4.4.4. Variáveis register
A variável é colocada em um dos registradores da CPU e, por isso, dve ser bem escolhida
Ex.: register int i, j;
Este tipo de variável é mais usada em casos nos quais a velocidade é importante, como, por exemplo,
em variáveis que controlam laços.
10
5. Operadores
Um operador é um caracter ou grupo de caracteres que causará uma manipulação matemática ou lógica.
Em C, os operadores podem ser aritméticos, relacionais e lógicos e entre bits.
5.1. Aritméticos
+

*
/
%

++
+ =
=
*=
/=











adição
subtração e menos unário
multiplicação
divisão
resto divisão
decremento
incremento
soma
subtração
multiplicação
divisão
5.2. Lógicos ou “Booleanos”
&&  e
| |  ou
!  não
5.3. Relacionais
>

<

==

!=

>=

<=

maior
menor
igual
diferente
maior ou igual
menor ou igual
5.4. Entre Bits
&

|

^

~

>>

<<

e
ou
ou exclusivo
complemento (NOT)
deslocamento para direita
deslocamento para esquerda
11
RSF
5.5. Outros Operadores
*

retorna o valor contido em um endereço
&

retorna o endereço de uma variável
sizeof

retorna o tamanho de uma variável ou tipo
?

avalia expressão verdadeira
,

equivalente a "faça isto e isto e isto ..."
.

membro de estrutura ou união


ponteiro para membro de estrutura ou união
(type)

cast (altera tipo do dado)
5.6. Precedência (da maior para a menor)
( )[ ] 
!
~
++   ( type ) * &
sizeof
*
/
%
+

<< >>
<
<=>
>=
== !=
&
^
|
&&
||
?
=
+ = = * = / =
,
5.7. Outras Diretivas do Pré-processador
Além das diretivas #define e #include existem diretivas para compilação condicional (#if, #else, #elif,
#endif, #ifdef e #ifndef) e outras utilizadas apenas por determinados compiladores como por exemplo
para montagem de trechos de programa em linguagem Assembly (#asm e #endasm). Entretanto, estas
últimas não são portáveis, pois não são encontradas em todos os compiladores C.
5.7.1. Ccompilação condicional
Comandos para compilação condicional: #if, #else, #elif, #ifdef, #ifndef e #endif #if, #else, #elif e
#endif
São do tipo if then else e indicão ao compilador os trechos do programa que serão ou não compilados.
Exemplo de formatos possíveis:
#if expressão constante
seqüência de comandos
12
#endif
#if expressão constante
seqüência de comandos 1
#else
seqüência de comandos 2
#endif
#if expressão constante 1
seqüência de comandos 1
#elif expressão constante 2
seqüência de comandos 2
#else
sequência de comandos 3
#endif
Exemplos de uso:
a)
#define MAX 100
...
void func ( ) {
#if
}
b)
MAX > 99
cout << "Compilado Para Array > 99.\n";
#endif
...
#if PC == 1
#define COMP 1
#else
#define COMP 2
#endif
 Comandos # ifdef e # ifndef
Usados para testar a existência ou não do símbolo que tem como parâmetro.
Exemplo de formatos possíveis:
#ifdef
#endif
#ifdef
#else
#endif
símbolo
sequência de comandos
símbolo
sequência de comandos 1
sequência de comandos 2
13
#ifndef símbolo
sequência de comandos
#endif
#ifndef símbolo
sequência de comandos 1
#else
sequência de comandos 2
#endif
Exemplos de uso:
a)
#ifdef DEBUG
cout << "Valor de x = " << x;
#endif
b)
#ifndef DEBUG
cout << “ Sem debug \n";
#endif
6. Entrada e Saída de Dados Pela Console – Funções printf ( ... ) , scanf ( ... ), cout << e cin >>
Ao contrário de outras linguagens, no C as operações de leitura e impressão, tanto na tela quanto em
arquivos, é totalmente feita por funções. Os protótipos destas funções se encontram no arquivo stdio.h,
o qual deve sempre ser incluído quando forem usadas funções de IO (entrada e saída).
6.1. printf
Principal função de impressão no vídeo e retorna o número de caracteres impressos.
Formato: int printf (formato, argumentos);
Obs1.: Em C, o valor de retorno de uma função pode ser ignorado.
Obs2.: Em C, as funções podem ter um número variável de parâmetros.
Ex.: printf (" \n FIM \n" ) ;

%d

inteiro

%c

caracter

%f

float

%ld

long int

%lf

double

%s

string

%e

notação científica
// A saída pode ser formatada através do tamanho do campo:
 %3d

inteiro com 3 dígitos.
14
%7.2f
6.2. scanf


float com dois dígitos após o ponto decimal.
Principal função de leitura do teclado.
Formato: int scanf (formato, parâmetros);
Retorna o número de variáveis lidas corretamente ou EOF em caso de erro grave.
Principais formatos:
 %d – inteiro
 %c – caracter
 %f – float
 %ld – long int
 %lf – double
 %s – string
Para a função scanf, o branco é considerado delimitador. Por exemplo: se você digitar os números 1 e
3, scanf ("%d %d", &a, &b); mostrará 1 3 ou 1 3 (depende dos espaços entre os %d). Já scanf
("%d ,%d", &a, &b); mostrará 1,3 (um, vírgula e três).
// Exemplo: Ler dois números e imprimir a soma.
#include <iostream>
using namespace std;
void main ( )
{
int a, b, c;
printf (“\n\t\t\t Entre Com 2 Números: ");
scanf (“%d %d”, &a, &b);
c = a + b;
printf (“\n\t\t\tSoma = %d\n", c”);
6.3.
cout << ...
Função de visuallização em C++. Deve ser precedida pelas declarações “<iostream>” e “using
namespace std” antes de sua utilização.
Formato: cout << “texto” << variável << etc ...
Ex.: int a = 22; cout << “\n Com Idade Igual ou Maior a" << a << “ É Considerado Emancipado !!!”;
6.4. cin >> ...
Função de recepção de dados a partir do teclado em C++. Deve ser precedida pelas declarações
“<iostream>” e “using namespace std” antes de sua utilização.
Formato: cin << variável;
Ex.: int a; cin >> a; // “a “ recebe o que for digitado no teclado
7. Instuções de Controle
7.1. if { } ; if { … } else { … } ; if { … } else { if { … }} ; etc …
// Exemplo 1
15
if ( teste ) < um só comando; >
// Exemplo 2
if ( teste )
{
< bloco de comandos; >
}
else
{
bloco de comandos;
}
// Exemplo 3: ler 2 números e indicar o maior
#include <iostream>
using namespace std;
void main ( )
{
int a, b;
cout << “\n Entre Com 2 Numeros: ");
cin >> a >> b;
if (a == b)
/* todo teste de igualdade utiliza == */
cout << ” \n Os Números Sao Iguais !!!\n”;
else if (a > b)
cout << ” \n O Primeiro Número é o Maior !!! \n”;
else
cout << “ \n O Segundo Número é o Maior !!! \n”;
}
// Exemplo 5: ler uma série de números reais e indicar o maior e o menor.
#include <iostream>
using namespace std;
void main ( )
{
float min, max, x;
cout << “\n\t\t\t Entre os Numeros: \n”;
cin >> x;
min = max = x;
/* atribuição múltipla */
while (cin << x) == 1) if (min > x) min = x;
else if (max < x)
max = x;
cout << “\n O maior é “ << max << “\n O menor é " << min << “\n\n”;
}
16
7.2. if com ?
É uma outra forma de utilização do comando if (útil para pequenos comandos do tipo if).
if (a == 10)
{
b = 20;
}
else
{
b = 30;
}

b = (a == 10) ? 20 : 30;
V
F
7.3. switch – substitui grandes if's.
switch (exp)
// A expressão exp deve fornecer um resultado inteiro.
{
case cte1: bloco1;
break;
case cte2: bloco2;
break;
case cte3: bloco3;
break;
...
}
case cten:
locon;
break;
default:
bloco;
break;
/* não é necessário break aqui */
Exercícios de Fixação
1) Implemente um programa que receba 3 (três) números inteiros, através do teclado, e visualize qual o
maior e qual o menor deles.
2) Implemente um programa que receba 3 (três) números inteiros, através do teclado, e verifique se eles
podem formar um triângulo eqüilátero, um triângulo retângulo, ou se não permitem a formação de
um triângulo.
Obs.: Relação Triangular: cada lado de um triângulo tem de ser menor que a soma dos outros dois
lados ;
17
7.4. for ( . . . ) { . . . }
Formato:
for (inicialização; condição; incremento)
{
< bloco de comandos; >
}
// Exemplo: Imprimir os números de 1 a 10
#include <iostream>
using namespace std;
void main ( )
{
int i;
for (i = 1; i <= 10; i++) cout << "\n", i << \n”;
}
// Obs.: Todos os campos do for são opcionais:
#include <iostream>
using namespace std;
void main ( )
{
int i = 1;
for ( ; i <= 10; ) cout << “\n" << i++;
}
7.5. while
Formato:
while (condição)
{
< bloco de comandos ; >
}
// Executa o bloco enquanto
//
a condição for verdadeira.
// Em C, verdadeiro = não zero.
// Exemplo: Seja fazer um programa que imprima a soma dos números de 1 a 5 com um laço
while.
// Solução 1:
#include <iostream>
using namespace std;
void main ( )
{
int i=1, soma=0;
while (i <= 5)
{
soma = soma + i;
i = i + 1;
}
18
cout << “\nSoma = " << soma << “\n\n”;
}
// Solução 2:
#include <iostream>
using namespace std;
void main()
{
int i = 1, soma = 0;
while (i <= 5)
{
soma += i;
i++;
}
cout << “\nSoma = " << soma << “\n”;
}
// Obs.: i ++;  ++ i;
se a = 1: para b = ++ a;
para b = a ++;
var = var op exp;
x = x + 5;
x = x / (a + b);


b=2ea=2
b=1ea=2

var op = exp;
x + = 5;
x / = a + b;
7.6. do while
Formato:
do
{
// Executa o bloco de comandos enquanto a condição for verdadeira.
< bloco de comandos; >:
}
while (condição);
// Exemplo: Imprimir os números de 1 a 10
#include <iostream>
using namespace std;
void main ( )
{
int i = 1;
do {
cout << "\n" << i;
i++;
}
while (i <= 10);
19
}
// Exemplo: Calcular o fatorial de um número lido usando for.
// Solução 1:
#include <iostream>
using namespace std;
void main ( )
{
int n, i, f = 1;
cout << "\n\t\t\t\t Entre Com o Número: ";
cin >> n;
for (i = 1; i <= n; i++) f *= i;
cout << " \n\n\t\t\t Fatorial de “ << n << “ = “ << f ;
}
// Solução 2:
#include <iostream>
using namespace std;
void main ( )
{
int n, i, fat;
cout <<”Entre o Numero: ";
cin >> n;
i = n;
for (fat = 1; n > 1; n– –) fat *= n;
cout << “\n Fatorial de “ << i << “ = “ << fat ;
}
7.7. continue
Passa para o próximo incremento em um for ignorando as instruções restantes dentro do bloco do for.
...
for (i = 0; i < 10; i++)
{
if (i == 0)
continue;
/* evita divisão por zero */
cout << “\n" << (float) 10 / i;
}
20
7.8.
break
Interrompe a execução de um for, while, do ... while ou switch. O fluxo de execução do programa é
desviado para primeira instrução fora do bloco que possui o break.
Ex.: while (1)
/* loop infinito */
{
cin >> a;
if (a != 0) processa ( );
else break;
}
7.9.
goto label
Desvia o fluxo de execução do programa para um label em outro ponto do programa.
goto Label_1;
processa ( );
Label_1:
// Para label sem instruções deve-se usar um “;” no final: Ex.: Erro_Fatal: ;
...
Exemplo: Fazer um programa que simule uma calculadora, com as quatro operações, teste a divisão
por zero e sinal inválido.
#include <iostream>
// Inclui biblioteca
# define FALSE 0
// Define
# define TRUE 1
//
Constantes
using namespace std;
void main ( )
{
float v1, v2, res;
char op;
int erro = FALSE;
/* usa int como variável lógica */
cout <<” \n\n\t\tEntre Com Sua Expressão: " ;
cint >> v1 >> op >> v2;
/* lê a expressão */
switch ( op )
{
case '+' : res = v1 + v2;
break;
case '' : res = v1  v2:
break;
case '*' : res = v1 * v2;
break;
case '/' : if (v2 == 0.0)
{
cout << " \n Erro: Divisão Por Zero \n";
erro = TRUE;
}
else res = v1 / v2;
break;
default: erro = TRUE;
cout << "\n Operador Inválido !!! \n" ;
break;
}
if (!erro) /* não precisa fazer erro == TRUE */
21
}
cout << “\n\t\t\t\tResultado = “ << “ << res;
// Exemplo: Fazer um programa que leia um valor n e leia e imprima o quadrado de n números.
#include <iostream>
using namespace std;
void main ( )
{
float x;
int n;
cout << “\n Informe Número de Valores a Serem Lidos: ";
cin >> n;
while (n – );
{
cout << “\nValor: ";
cin >> x;
cout << “\n Quadrado de “ << x << “ = “ << x * x ;
}
}
Obs.: Outras funções de entrada e saída de dados
int getchar ( void ); // Erro = EOF
int putchar ( int ); // Erro = EOF; OK = caractere impresso
22
Exercícios de Fixação
A seguir são apresentados vários exercícios. Quando algum deles necessitar utilizar comandos de
repetição, resolva-os: (a) utilizando somente o comando do { ... } while ; (b) utilizando somente o
comando while{ . . . }; e (c) utilizando somente o comando for { . . . }.
3) Implemente um programa que receba, através do teclado, um número inteiro maior que 0 (zero) e
menor que 101 (cento e um), e que, após, visualize a soma de todos os números ímpares
compreendidos entre 1 (um) o número digitado, inclusive.
4) É sabido que a série de Fibonacci é: 1 1 2 3 5 8 13 . . . , que pode ser definida assim:
a1 = 1 ; a2 = 1 ; e
an = (an – 1) + (an – 2) para n  3
4.1) Implemente um programa que visualize um certo termo da série de Fibonacci cuja posição na
série deve ser informada através do teclado e deve pertencer ao intervalo [ 0 , 20 ].
4.2) Implemente um programa que visualize a soma dos N primeiros termos da série de Fibonacci,
sendo N informado através do teclado e devendo pertencer ao intervalo [1, 25 ].
4.3) Implemente um programa que exteriorize todos os quadrados perfeitos pertencentes aos 25
primeiros termos da série de Fibonacci.
5) Implemente um programa que receba dois números inteiros, através do teclado, maiores que 0 (zero)
e menores que 1000 (mil), e visualize todos os cubos perfeitos compreendidos entre eles, inclusive.
6) Implemente um programa que receba 3 (três) números inteiros, através do
teclado, cujos
significados são, respectivamente: o primeiro termo de uma Progressão Aritmética – P. A. ; a razão
desta P.A.; e sua quantidade de termos.
7) Implemente um programa que calcule e visualize a soma dos 15 (quinze) primeiros termos da
Progressão Geométrica 3, 9, 27, ... .
8) Implemente um programa que receba, através do teclado, um número inteiro maior que 0 (zero) e
menor que 10 (dez), e que, após, visualize seu valor por extenso (e.g. : se o número digitado foi sete
o algoritmo deve mostrar sete).
9) Implemente um programa que receba, através do teclado, um número inteiro maior que 0 (zero) e
menor que 501 (quinhentos e um), e que, após, visualize se o número é par e múltiplo de 3 (três); ou
se é par e múltiplo de 5 (cinco) ; ou se não satisfaz nenhuma das condição anteriores.
23
10) Implemente um programa que receba, através do teclado, um número inteiro maior que – 1 e menor
que 16 (dezesseis), e que, após, visualize seu fatorial.
8. Arrays Unidimensionais (Vetores)
Definição de vetores unidimensionais:
<tipo> <nome>[<tam>];
Ex.: int vet[5];
 define vet como um vetor inteiro de 5 posições
A posição do primeiro elemento é vet [ 0 ] e do último vet [ 4 ].
Exemplos de acesso:
int vet [ 5 ];
vet[ 0 ] = 10;
vet[ 1 ] = 20;
vet[2]
= 40;
for (i = 0; i < 5; i++)
vet [ i ] = 0;
/* zera o vetor */
Iniciação na definição:
 Para vetor local:
static int vet[ ] = {1, 3, 5}; // assume que o vetor vet possui 3 elementos
static float vet[10];
// assume vet com 10 elementos, que são iniciados com 0.
static int vet[5] = {1, 2, 3};
// assume vet com 5 elementos; o 4º e o 5º são iniciados com 0.
 Para vetor global:
int vet[ ] = {10, 20, 40, 50}; // assume vet com 4 elementos
Quando um vetor extern ou static for iniciado sem dimensão, ela será igual ao número de valores da
iniciação.
Caso seja fornecida a dimensão e faltem elementos na iniciação, os elementos não iniciados valem zero.
24
// Exemplo: Fazer uma função que retorne o maior número de um vetor double.
# include <stdio.h>
double maxval (double [ ], int);
void levet
(double [ ], int);
void main ( )
{
double vet [ 100 ];
int i, n;
printf (" Número de elementos do vetor: " ) ;
scanf (" %d ", &n);
levet (vet, n);
}
printf (" \n Maior valor = %lf ", maxval (vet, n) );
void levet (double v[ ], int n )
{
int i;
double aux;
}
/* double v[ ]; não precisa dar a dimensão */
printf("Entre os elementos do vetor:");
for (i = 0; i < n; i++)
{
scanf (" %lf ", &aux );
v [ i ] = aux;
}
double maxval (double v[ ], int n )
{
int i;
double maior;
maior = v[ 0 ]; /* maior começa como sendo o primeiro */
for (i = 1; i < n; i++)
if (v [ i ] > maior) maior = v [ i ];
}
return (maior);
25
Exercícios de Fixação
11) Escreva um algoritmo que preencha um vetor com valores inteiros maiores que 0 (zero) e menores
que 101 (cento e um), informados através do teclado, e que, após, visualize somente os valores
múltiplos de 5, sem utilizar o comando que forneça o resto de divisão automaticamente.
12) Escreva um algoritmo que preencha um vetor com valores inteiros, informados através do teclado,
mas de tal modo que nunca sejam armazenados 2 (dois) valores iguais nele. Mais ainda; após
terminar o preenchimento o algoritmo dever visualizar todo conteúdo do vetor.
13) Escreva um algoritmo que preencha 2 (dois) vetores com valores inteiros maiores que 0 (zero) e
menores que 101 (cento e um) , informados através do teclado, e que, após, processe a geração de
um terceiro vetor que contenha todos os elementos dos dois primeiros vetores, porém sem que
ocorra repetição de valores.
14) Escreva um algoritmo que preencha um vetor com valores inteiros maiores que 0 (zero) e menores
que 101 (cento e um), informados através do teclado, e que, após, visualize todos os valores
presentes no vetor que façam parte dos primeiros 10 (dez) termos da série de Fibonacci.
15) Escreva um algoritmo que preencha um vetor com valores inteiros maiores que –10 (menos dez) e
menores que 10 (dez), informados através do teclado, e que, após, visualize, sem repetições, todos
os valores ímpares presentes no vetor que façam parte dos 15 (quinze) primeiros termos da série de
Fibonacci.
16) Resolva os exercícios a seguir de 3 modos diferentes, ou seja: utilizando os comandos while { ... };
do { . . . }, while { . . .} e for { . . .}. Mais ainda: as visualizações deverão ocorrer: percorrendo o(s)
vetor(es) em ordem crescente e, após, em uma outra versão do exercício, percorrendo o(s) vetor(es)
ordem decrescente.
a) Escreva um programa que preencha, a partir do teclado, duas estruturas distintas do tipo vetor
com os nomes e as notas (as notas têm de estar contidas no intervalo 0  nota  10) dos
alunos, respectivamente, de uma turma de 100 alunos e, após, exteriorize somente os nomes
dos alunos que obtiveram notas iguais ou maiores que 5 (cinco).
b) Escreva um programa que preencha, a partir do teclado, duas estruturas distintas do tipo vetor
com as idades de 100 pessoas. A primeira estrutura do tipo vetor deverá receber somente as
idades das pessoas do sexo masculino, enquanto a segunda deverá armazenar as idades das
pessoas do sexo feminino. Após, o programa deverá exteriorizar os nomes, o sexo e as idades
das pessoas que possuem idade compreendida entre 20 (vinte) e 40 (quarenta) anos, inclusive.
26
17) Escreva um algoritmo que calcule e visualize a soma S conforme a representação abaixo.
S  ( a1 – an ) 2  ( a2 - an 1 ) 2  ( a3 - an 2 ) 2  ...  ( an - a1 ) 2
Os valores de a1 a2 , ... , an deverão ser naturais consecutivos e o valor n deverá ser informado
através do teclado, e estar compreendido no intervalo fechado [ 1 , 100 ] .
8.1. Vetores de Caracteres – Strings

1.
2.
3.
4.
Considerações Gerais:
São arrays de caracteres.
Em C, toda string acaba com o caracter '\0'.
Exemplo da definição de um vetor de caracteres: char str [ 7 ];
A consideração 3 define str como vetor de 6 caracteres mais o caractere de final de string.
Exemplo:
char str [ 7 ];
str[0] = 'C';
str[1] = 'a';
str[2] = 'r';
str[3] = 'l';
str[4] = 'o';
str[5] = 's';
str[6] = '\0';
Na memória teríamos:
C
a
r
l
o
s
\0
0
1
2
3
4
5
6
Podemos iniciar uma string de duas formas:
1. Como um vetor:
static char str [ ] = {'C', 'a', 'r', 'l', 'o', 's', '\0'}; /* assume 6 caracteres mais '\0' = 7 */
2. Deixar que o compilador inicie:
static char str[ ]="Carlos"; /* assume 6 caracteres mais '\0' = 7 */
27
Obs.: Não é possível a atribuição direta:
char str[ 7 ];
str = "Carlos"; /* Erro: não vale a atribuição */
// Exemplo: Fazer um programa para ler um nome e dar um bom dia para o dono do nome.
// Solução 1:
#include <stdio.h>
#define TAM 100
void main()
{
char linha [ TAM ];
int c, i;
printf ( " \n Qual é o seu nome ? " ) ;
for (i = 0; (c = getchar ( ) ) != '\n'; i++) linha [ i ] = c;
linha [ i ] = '\0';
}
printf (" \n Tenha um bom dia " ) ;
for (i = 0; linha [ i ] != '\0'; i++) putchar ( linha [ i ] );
putchar('\n');
A função getchar retorna um caractere do teclado e a função putchar coloca um caractere no vídeo.
Estas funções, bem como as outras de IO podem ser redirecionadas. Em caso de erro, a função getchar
retorna EOF.
// Solução 2:
#include <stdio.h>
#define TAM 100
void main()
{
char linha [ TAM ];
printf (" \n Qual é o seu nome ? " );
gets ( linha );
printf (" \n Tenha um bom dia !!!" );
puts (linha);
}
A função gets tem por finalidade ler uma string e a puts imprimir uma string. A função puts fornece
automaticamente uma mudança de linha após a impressão.
28
Formatos:
(Ponteiros serão abordados com detalhes mais adiante)
char *gets ( char *buf );
retorna ponteiro para a string lida ou NULL em caso de erro.
int puts ( char *buf );
retorna '\n' se imprimiu bem ou EOF em caso de erro.
Para atribuição de strings, usa-se a função strcpy, que possui o formato:
char *strcpy (char *destino, char *origem);
Exemplo: strcpy (str, "casa");
/* str passa a ter "casa" */
Para se saber o tamanho de uma função, usa-se a função strlen, que possui o formato:
int strlen (char *st);
// Exercício: Construir a função strlen.
// Solução 1:
int strlen (char cadeia [ ])
{
int len = 0, I = 0;
while (cadeia [ I ] != '\0')
{
++len ;
++ i;
}
return ( len );
}
// Solução 2:
int strlen (char cadeia [ ])
{
int i;
for (i = 0; cadeia [ i ] != '\0'; i++) ;
return ( i );
}
/* bloco nulo */
// Exercício: Construir uma função que copia uma string para um vetor de caracteres
// Solução 1:
void stringcpy (char[ ], char[ ]);
void stringcpy (char s1[ ], char s2[ ])
{
int i;
for (i = 0; s2 [ i ] != '\0'; i++)
s1[ i ] = s2 [ i ];
s1[ i ] = '\0';
}
// Solução 2:
29
void stringcpy(char s1[ ], char s2[ ])
{
int i = 0;
while ( ( s1[ i ] = s2 [ i ]) != '\0' )
i++;
}
9. Arrays Bidimensionais (Matrizes Bidimensionais)
Formato:
Onde:
<tipo> <nome> [ <d1> <d2> ];
d1
d2


número de linhas (varia entre 0 e d1  1)
número de colunas (varia entre 0 e d2 - 1)
Exemplo:
int b[3][5];  3 linhas e 5 colunas
Inicialização na declaração:
static int b[ ][ 3 ] =
|
{
|
1, 1, 1,
|
2, 2, 2,
|
3, 3, 3
|
};
|
static int b[ ][3] =
{
{1, 1, 1},
{2, 2, 2},
{3, 3, 3}
};
A iniciação também pode ser feita de forma esparsa. Por exemplo:
static int b[ 3 ][ 3 ] =
{
{1, 1},
{1}
};
A matriz gerada pela inicialização acima será:
110
100
000
Obs.: (1) Para este tipo de iniciação é necessário que se forneça o número de linhas e de colunas; (2) o
armazenamento em C é feito por linhas; e (3) ao se passar uma matriz bidimensional, a única dimensão
fixa é o número de colunas (ao contrário do Fortran que fixa o número de linhas).
// Ex.:
void main ( )
{
int mat[ 10 ][ 20 ];
...
30
}
f (mat, 10, 20);
A função f ( ) poderia receber a matriz de duas formas:
void f (int mat[ 10 ][ 20 ], int lin, int col) ou
void f (int mat[ ][ 20 ], int lin, int col)
{
comandos;
}
// Exemplo de como zerar uma matriz:
void zera (float mat[ ][ 20 ], int, int); /* protótipo */
void main ( )
{
float mat [ 10 ][ 20 ];
zera (mat, 10, 20);
}
void zera (float mat[ ][ 20 ], int lin, int col)
{
register int i, j;
for (i = 0; i < lin; i++)
for (j = 0; j < col; j++) mat[ i ][ j ] = 0.0;
}
Exercícios de Fixação
18) Escreva um algoritmo que preencha uma certa matriz quadrada de ordem 4 (quatro) com
números inteiros, informados através do teclado, e que, após:
a) Visualize todos números pertencentes a Diagonal Principal – DP ;
b) Visualize todos números pertencentes a Diagonal Secundário – DS ;
c) Visualize todos números que estejam acima da Diagonal Principal ; e
d) Visualize a soma de todos os números que estejam abaixo da Diagonal Secundária.
19) Escreva um algoritmo que preencha automaticamente uma certa matriz quadrada de ordem 8 (oito)
conforme a representação gráfica abaixo:
linhas
1
2
3
4
5
6
7
8
1
A
A
A
A
A
A
A
A
A
B
B
B
B
B
B
A
2
A
B
C
C
C
C
B
A
colunas
3
4
A
A
B
B
C
C
D
D
D
D
C
C
B
B
A
A
5
A
B
C
C
C
C
B
A
6
A
B
B
B
B
B
B
A
A
A
A
A
A
A
A
A
7
8
20) Escreva um algoritmo que preencha duas matrizes quadradas de ordem 3 com valores inteiros
maiores que 0 (zero) e menores que 101 (cento e um), informados através do teclado, sem permitir
31
que sejam armazenados valores repetidos em cada matriz. Após, o algoritmo deverá visualizar
todos os valores ímpares e múltiplos de 11 sem, no entanto, utilizar o comando mod.
Mais: Após, o algoritmo deverá executar a geração automática de uma terceira matriz que
represente a soma das outras duas matrizes, também sem permitir a ocorrência de repetição de
valores. Quando ocorrer repetição o valor repetido deverá ser substituído por 0 (Zero) na matriz
soma. Finalmente, o algoritmo deverá visualizar os valores presentes na terceira matriz – matriz
soma – que façam parte dos 10 (dez) primeiros termos da série de Fibonacci.
21) Escreva um algoritmo que preencha duas matrizes de dimensões 5x3 e 3x2, respectivamente, e
que, após, calcule e visualize a matriz produto delas.
10.
Funções
Formato:
< tipo > < nome da função > ( < parâmetros > )
{
declaração de variáveis locais;
corpo da função;
}

< tipo > é o tipo do valor a ser retornado pela função;

se uma função não retorna nada, o seu tipo é void;

os parâmetros são sempre passados por valor, isto é, uma cópia do valor da variável é passado para a
função;

para arrays (vetores e matrizes) é passado como valor o endereço da primeira posição;

deve-se sempre usar o protótipo da função;

variáveis 'char' são transformadas em 'int' e variáveis 'float' são transformadas em 'double'.
O formato da função varia entre o padrão K & R e o ANSI. O padrão K & R pode ser usado no ANSI.
formato K & R
int soma (a, b)
int a, b;
{
return (a+b);
}
|
|
|
|
|
|
formato ANSI
int soma (int a, int b)
{
return ( a + b );
}
O valor retornado por uma função pode ou não ser utilizado (e.g.: a função printf ( ) ).
Mais: pode-se retornar de qualquer ponto da função, bastando usar a instrução return ( ).
// Exemplo: Fazer um programa para ler um número e imprimir o seu fatorial utilizando uma
32
//
função para ler o número, uma para cálculo do fatorial e uma para mostrá-lo.
# include <stdio.h>
long factorial (long);
long leval
(void);
void printfat (long);
void main ( )
{
long fat, val;
val = leval ( );
fat = factorial (val);
printfat (fat);
}
long leval ( )
{
long x;
printf (" \nEntre o valor a ser calculado: ");
scanf("%ld", &x);
return ( x );
}
void printfat (long y)
{
printf (" \nFatorial = %ld\n", y);
}
long fatorial (long a)
{
long fator = 1;
long i;
for (i = 1; i <= a; i++) fator *= i;
return ( fator );
}
11.
Ponteiros – Variáveis do Tipo Pointers
11.1. Definição
Um ponteiro é uma variável que contem como valor um endereço.
Para definirmos uma variável como ponteiro, devemos fornecer o tipo da variável para qual apontará e
um nome.
Embora os endereços de variáveis de um tipo (e.g.: int), sejam semelhantes aos de outros tipos como
float, char ou double, é importante não misturá-los. Para a declaração de um ponteiro tem-se que
indicar o tipo de variável para o qual ele irá apontar, pois ao serem feitas operações aritméticas com os
ponteiros, eles irão variar em função de seu tipo.
Principais vantagens do uso:
33



superar as restrições de passagem de argumento, por valor, para funções;
acessar elementos de arrays de modo alternativo ao uso de índices;
permitir a criar estruturas dinâmicas (árvores e listas encadeadas) bem como suas manipulações.
Forma de definição:
<tipo> *<nome>;
Exemplos:
int *p;
float *pf;
int i, *pt;
pt = &i;




p é um ponteiro para inteiro
pf é um ponteiro para float
pt é um ponteiro para inteiro
pt recebe oendereço de i
34
i
pt
5
1002
1002
2000
*pt

void *pvoid; 
5 (conteúdo do endereço dado por pt)
ponteiro para qualquer tipo
Dado: float x, y, *p, *q;
Temos como operações possíveis:
p = &x;
 p aponta para x
y = *p;
 y recebe o valor que está no endereço dado por p
q = p;  q e p apontam para o mesmo endereço
Erros comuns:
int *p;
*p = 10;
// não apontou para nenhuma variável
float val;
int *p;
p = &val;
// tipos incompatíveis
11.2. Iniciação de ponteiros na definição
int i = 7, p = &i; /* a inicialização é de p' e não de *p
*/
11.3. Passagem de parâmetros por endereço (referência)
Para que se possa passar uma variável por referência, devemos passar um ponteiro para esta variável ou,
em outras palavras, o seu endereço.
35
/*
** Exemplo: ler dois valores e trocá-los de ordem
*/
#include <stdio.h>
void swap(int *, int *); /* protótipo de swap */
void main()
{
int a, b;
}
scanf (" %d %d", &a, &b); /* le os dados */
swap (&a, &b);
/* chama a função swap */
printf ("%d : %d\n", a, b); /* imprime resultado */
void swap(int *x, int *y)
{
int tmp;
tmp = *x;
*x = *y;
*y = tmp;
}
// Exemplo: fazer uma função que tenha o seguinte protótipo:
void soma (int *r, int a, int b);
# include <stdio.h>
void soma( int *r, int a, int b);
void main ( )
{
int x, y, z;
printf ( " \n Entre dois números: \n");
scanf ("%d %d", &x, &y);
soma (&z, x, y);
printf (" \n A soma é: %d\n", z);
}
void soma (int *r, int a, int b)
{
*r = a + b;
36
}
12.
A Relação Entre Ponteiros e Arrays
Um nome de array é um endereço ou ponteiro, que é fixo.
Exemplo:
int k, a[100], *p;
// p possui o endereço do primeiro elemento de a
// ou
p = &a[ 0 ]; // p possui o endereço do primeiro elemento de a
p = a;
Para que p aponte para o elemento seguinte, basta incrementar o endereço de 1.
p = a + 1;
p++;
k = *p++;
// p = &a [ 1 ];
// p aponta para o próximo elemento.
// k  valor do elemento apontado por p e p aponta para o próximo elemento
Exemplos para zerar um vetor:
for (i = 0; i < 100; i++)
a[ i ] = 0;
ou
for (i = 0, p = a; i < 100; i++)
*p++ = 0;
// com índice
// com ponteiro
// Exemplo: Criar uma função que retorne o tamanho em bytes de uma cadeia de caracteres
// usando ponteiro.
// Solução 1:
# include <stdio.h>
int strlen (char* str);
void main ( )
{
static char str [ ] = "Esta string tem 30 caracteres.";
printf (" \nTamanho da string: %d caracteres.\n", strlen (str) );
}
int strlen (register char *s)
{
register int n;
for (n = 0; *s != '\0'; s++) ++n;
37
return (n );
}
// Solução 2:
# include <stdio.h>
int strlen (char *str);
void main ( )
{
static char str[ ] = "Esta string tem 30 caracteres.";
}
printf ("\nTamanho da string : %d caracteres.\n", strlen (str) );
int strlen(register char *s)
{
register int n=0;
while (*s++)
++n;
}
return(n);
// Solução 3:
#include <stdio.h>
int strlen (char *str);
void main ( )
{
static char str[ ] = "Esta string tem 30 caracteres.";
}
printf (" \n Tamanho da string : %d caracteres.\n", strlen (str) );
int strlen (register char *s)
{
register char *ps;
ps = s;
while (*ps)
ps++;
return(ps - s);
// ps aponta para o inicio da string
38
}
// Exemplo: Criar a função strcpy, que copie o conteúdo de uma string em outra.
# include <stdio.h>
char *strcpy (char *d, char *o);
void main()
{
static char orig[ ] = "teste", dest [ 20 ];
strcpy (dest, orig);
printf("origem = %s ; destino = %s\n", dest, orig);
}
char *strcpy (char *dest, char *origem)
{
char *d = dest;
// O while a seguir faz a copia e incrementa os ponteiros de cada string, até aparecer um
// caractere nulo significando fim de string.
// Alguns compiladores darão um aviso (warning), achando que se deseja fazer um teste ao
// invés de atribuição com teste, que é o que se pretende fazer realmente.
while (*d++ = *origem++); /* sem bloco */
return (dest );
}
// Exemplo: Criar a função strcmp que tem como finalidade comparar o conteúdo de uma
// string com o de outra. A função tem o seguinte formato: int strcmp (char *s, char *t);
// Esta função retorna: (a) 0 se as strings forem iguais; (b) < 0 se s < t; e (c) > 0 se s > t
# include <stdio.h>
int strcmp (char *s, char *d);
void main ( )
{
char s1 [ 20 ], s2 [ 20 ];
printf (" \nEntre a primeira string: ");
gets ( s1 );
printf (" \nEntre a segunda string: ");
gets ( s2 );
if ( strcmp (s1, s2) )
printf (" \n Diferentes.\n");
/* <> de zero */
else
printf (" \n Iguais.\n");
}
int strcmp (char *s1, char *s2)
{
while (*s1 == *s2)
if (*s1++)
s2++;
39
}
else
return(0);
return(*s1 - *s2);
Para definição e iniciação de strings, também é possível o seguinte tipo de instrução:
char *mens = "Divisão por zero";
A definição acima define mens como sendo um ponteiro para a string "Divisão por zero".
13.
Ponteiros e Arrays Bidimensionais
Como para vetores unidimensionais, o nome de um array é um ponteiro fixo. Assim, as seguintes
instruções são equivalentes e geram o mesmo código:
b[ i ][ j ]
*(*(b + i) + j)
*(b + i * ncolun + j)
O esquema abaixo representa o acesso à vetores bidimensionais.
b
b[1]
b[i]
b+i
*(b + i)
b[i][j] =
*(*(b + i) + j)
Como para vetores unidimensionais, existem formas de se acessar matrizes de uma forma mais
eficiente, como veremos a seguir.
Definição de ponteiros para matrizes.
int mat[10][20], (*plin)[20];
plin = mat;
Nas instruções acima, definimos plin como sendo um ponteiro para uma linha de um array com 20
colunas e mandamos que ele aponte para o primeiro elemento.
Forma de armazenamento na memória:
40
...
...
20 elementos
20 elementos
...
20 elementos
Para acessar um elemento da matriz via ponteiro:
(*plin)[j] ou *(*(plin) + j)
Para se passar para a próxima linha:
plin++;
plin
plin + 1
plin + 9
Nota: ( * plim) [ 20 ] define um ponteiro para linha de um vetor com 20 colunas, enquanto que
*plin[20] define um vetor de 20 elementos do tipo ponteiro.
// Exemplo: Calcular a média dos elementos de uma coluna de uma matriz de 3 colunas.
// Solução:
# include <stdio.h>
double test_avg (int [ ][ 3 ], int, int);
void main ( )
{
double res;
static int board [ ][ 3 ] =
{
1,
2,
3,
4,
5,
6,
7,
8,
9,
10, 11, 12
};
res = test_avg ( board, 4, 2 );
printf (" %lf\n", res);
}
double test_avg (int tab[ ][3], int maxlin, int col)
{
long sum = 0;
int i, (*ptr)[3] = tab;
for (i = 0; i < maxlin; i++)
sum += (*ptr++) [col ];
41
}
return ( (double) sum / maxlin );
// Exemplo: calcular a média dos elementos de uma linha de uma matriz de 3 colunas.
// Solução:
# include <stdio.h>
double test2_avg (int[ ][ 3 ], int);
void main( )
{
static int board[][3] =
{
1,
2,
3,
4,
5,
6,
7,
8,
9,
10, 11, 12
};
}
double res;
res = test2_avg (board, 1);
printf (" %lf\n", res);
/* calcular para linha 1. */
double test2_avg(int tab[][3], int linha)
{
long soma = 0;
int i;
int *p = &tab[linha][0];
}
for (i = 0; i < 3; i++)
soma += *p++;
return ( (double) soma / 3 );
Notas:
&tab[n][0] - endereço do elemento (n, 0) em tab
tab[n] - linha n de tab

O nome de um array bidimensional quando usado com um único índice é um ponteiro para o
primeiro elemento de uma determinada linha.
42

Arrays tridimensionais:
Seguem as mesmas regras do bidimensional. Exemplo:
int v [ 3 ][ 4 ][ 5 ]
define um array v com dimensões 3 x 4 x 5.
Definição de um vetor 3D em funções:
int vet[ ][ 4 ][ 5 ]
ou
int (*vet)[ 4 ][ 5 ]
13.1. Arrays de ponteiros (ragged arrays)
São arrays com linhas de tamanho variável. Um array deste tipo é composto por ponteiros para outras
variáveis e o seu uso mais comum é para acessar tabelas de strings.
Exemplo: definir um vetor de ponteiros para uma tabela de dias da semana.
static char *dias[ ] =
{
"segunda", "terça", "quarta",
"quinta", "sexta", "sábado", "domingo"
};
Para esta definição, dias é um array de 7 ponteiros para caracteres.
O esquema a seguir apresenta a organização interna da tabela de dias da semana.
dias
0
1
..
.
6
s
e g u n d a \0
t
e r
ç
d o m i
a \0
n g o \0
Os elementos de 'dias' podem ser acessados de duas maneira:
1. dias [ i ]
printf ("%s\n", dias[2]);
// será impresso "quarta"
2. dias [i ][ j ]
printf ("%c\n", dias[ 1 ][ 2 ]);
// será impresso ' r '
// dias [ 1 ]  "terça"
e
dias [ 1 ][ 2 ]  r (de "terça")
// Exemplo: Fazer uma função para imprimir 'dias'.
43
#i nclude <stdio.h>
void printab (char *[ ], int);
void printab (char *tab[ ], int n)
{
int i;
for (i = 0; i <= n; i++)
printf(" %s\n ",tab [ i ]);
}
Nota: Um elemento em um array de pointers pode ser usado como se ele fosse um pointer para o
primeiro elemento de uma linha de um array bidimensional (tab [ i ]).
14. Alocação Dinâmica de Memória
A linguagem C possui uma série de funções que permitem alocar e liberar áreas de memória,
fazendo com que se possa usar a memória gasta por variáveis, vetores, matrizes, listas, pilhas, etc. de
uma forma mais eficiente.
Quando necessário, o usuário pede uma área e a utiliza e, quando esta área não for mais necessária,
ela é devolvida ao sistema operacional, de forma a poder ser utilizada em outra etapa do programa.
O esquema abaixo apresenta o mapa da memória de um programa em C.
Área de Código
Área de Variáveis
Estáticas e Globais
Stack
Heap
A área disponível para alocação dinâmica se encontra na Heap.
As principais funções para manipulação de memória estão definidas no header stdlib.h e são:
 malloc
 calloc
 realloc
 free
void *malloc(unsigned int);
ptr = malloc(tam);
Aloca uma área de tam bytes. Se alocou corretamente, retorna um pointer para o primeiro byte da
área alocada e em caso de erro retorna NULL.
// Exemplo 1:
int *ptr;
...
44
ptr = malloc(sizeof(int));
if (ptr == NULL)
{
printf(" \nErro de alocação");
exit ( 1 );
}
*ptr = 10;
...
// Exemplo 2:
int *ptr, *ptraux, i;
...
ptr = malloc(sizeof(int) * 100);
if (ptr == NULL)
{
printf("Erro de alocação");
exit(1);
}
ptraux = ptr;
for (i = 0; i < 100; i++) *ptr++ = i;
ptr = ptraux;
...
// Exemplo 3:
// Obtém área para um vetor do tipo float. O número de elementos é pedido pelo programa.
// Após a obtenção da área necessária são pedidos dados para o seu preenchimento.
# include <stdio.h>
# include <stdlib.h>
void prtvet (float*, int);
void main ( )
{
int num, i;
float *pvet, *pinic;
printf ("\nEntre com número de elementos:\n");
scanf ("%d", &num);
pvet = (float*) malloc(num * sizeof(float));
if (!pvet)
{
printf (" \nErro. Falta de memória.\n");
exit ( 1 );
}
pinic = pvet;
for (i = 0; i < num; i++)
{
printf (" \n%d -> ", i + 1);
scanf ("%f", pvet++); /* não funciona no Turbo C */
}
45
pvet = pinic;
prtvet(pvet, num);
free(pvet);
/* imprime o vetor */
}
void prtvet (float *p, int n)
{
int i;
for (i = 0; i < n; i++)
printf("\n\%d -> %f", i + 1, *pv++);
}
void *calloc (unsigned int, unsigned int);
ptr = calloc(num, size);
Aloca uma área de 'tam' * 'num' bytes. Se alocou corretamente, retorna um pointer para o primeiro byte
da área alocada e em caso de erro retorna NULL. A área alocada é automaticamente zerada.
// Exemplo 1:
int *ptr;
...
ptr = calloc(1, sizeof(int));
if (ptr == NULL)
{
printf ("Erro de alocação");
exit (1);
}
*ptr = 10;
...
// Exemplo 2:
int *ptr, *ptraux, i;
...
ptr = calloc(100, sizeof(int));
if (ptr == NULL)
{
printf (" \nErro de alocação");
exit ( 1 );
}
ptraux = ptr;
for (i = 0; i < 100; i++) *ptr++ = i;
ptr = ptraux;
...
void free ( void *);
free (ptr);
// Exemplo: Libera a área alocada por malloc, calloc ou realloc.
int *ptr, *ptraux, i;
...
46
ptr = malloc(sizeof(int) * 100);
if (ptr == NULL)
{
printf (" \nErro de alocação");
exit ( 1 );
}
ptraux = ptr;
for (i = 0; i < 100; i++) *ptr++ = i;
ptr = ptraux;
...
free (ptr);
...
void *realloc (void *, unsigned int)
nptr = realloc(old, tam);
A função realloc altera o tamanho da área alocada por malloc ou calloc. O novo tamanho pode ser
maior ou menor do que o tamanho original. Quando chamada, retorna um pointer para a nova área
alocada, sendo old um pointer para a área antiga e tam' o novo tamanho em bytes. Em caso de erro, a
função retorna NULL e o programa deve ser interrompido, já que a área original poderá estar
comprometida.
Exemplo:
#include <stdio.h>
#include <stdlib.h>
void prtvet(float*, int);
void main()
{
int num, i;
char *p;
p = (char*) malloc(23);
strcpy (p, "AQUI TEM 22 CARACTERES");
printf ("\n%s\n", p);
p = realloc (p, 24);
strcat(p, ".");
printf(" \n%s\n", p);
free ( p );
}
15.
Definição de Novos Tipos
Para definição de novos tipos, é utilizada a instrução typedef.
Formato:
typedef <tipo existente> <novo tipo>;
47
Exemplos:
para se definir o tipo 'contador':
typedef
int contador;
contador i, j;
// É o mesmo que int i, j
Para se definir o tipo string:
typedef char string [ 81 ];
string text;
// É o mesmo que char text[81]
Para se definir o tipo 'boolean':
typedef int boolean;
# define FALSE 0
# define TRUE 1
...
boolean ok = TRUE;
if (ok) . . .
Para se definir o tipo ptrchar (pointer para caractere):
typedef char *ptrchar;
ptrchar pchar;
// É o mesmo que char *pchar
16.
Estruturas
Estruturas – structs – são usadas quando há necessidade de se combinar dados de um mesmo tipo ou de
tipos diferentes em um único objeto ou registro.
Forma de definição:
struct <nome>
{
<tipo 1> < campo 1 , campo 2 , . . . , campo n>;
<tipo 2> < campo 1 , campo 2 , . . . , campo n>;
.....
.....
<tipo m> < campo 1 , campo 2 , . . . , campo n>;
};
Exemplos:
struct s1
{
int a;
// Define estrutura chamada s1 contendo os seguintes campos
// inteiro a
48
char nome [ 81 ];
char ender [ 100 ];
};
// array de caracteres nome
// array de caracteres endereço
// A struct s1 passa a ser um tipo.
// Agora utilizaremos utiliza a struct s1 para definir duas variáveis estruturadas: info1 e info2
struct s1 info1, info2;
// Uma outra forma de definirmos este tipo de variáveis é:
struct
{
}
int x;
int y;
v1, v2;
// No exemplo acima, não foi criado um tipo, e sim duas variáveis (v1 e v2) do tipo struct.
// Também é possível o uso do typedef em conjunto com as estruturas:
typedef struct s1 t_s1;
t_s1 info1, info2; // Foram criadas duas variáveis info1 e info2 do tipo struct t_s1
Acesso aos membros de uma estrutura:
<variável>.<campo>;
Exemplos:
info1.a = 10;
strcpy(info1.nome, "teste");
struct s2
{
int a;
char *nome;
};
/* nome é um ponteiro */
struct s2 info3;
info3.a = 10;
info3.nome = "José da Silva";
/* nome é um ponteiro */
Operações possíveis entre estruturas:
49
A partir da definição: struct s1 v1, v2; temos:
1) atribuição:
v1 = v2;
2) comparação: (somente igualdade e desigualdade)
if (v1 == v2)
{
...
}
É possível perguntarmos se duas estruturas são iguais ou diferentes, mas não se uma é maior ou menor
do que a outra. No entanto, os campos (membros) de uma estrutura podem ser comparados com os de
outra.
Apesar de na versão ANSI podermos passar estruturas por valor para as funções, isto deve ser evitado,
já que torna a chamada da função mais lenta e aumenta a área ocupada no stack. A forma mais indicada
para se passar estruturas é utilizar pointers, como será visto mais adiante.
16.1 Iniciação de estruturas
Para alguns compiladores, é necessário que as variáveis locais sejam estáticas.
struct s_carta
{
int carta;
char naipe;
};
struct s_carta c =
{
12,
'O'
};
/* Ouro, Copas, Paus e Espadas */
/* inicializa como dama de ouros */
16.2 Campos de bits
Os campos de bits ou bitfields tem como principal finalidade a economia de memória, porém em alguns
casos o código gerado para a sua manipulação pode ser grande, gastando mais memória do que
economizando.
Forma de definição:
50
struct <nome>
{
<tipo1> <nome1> : <tamanho em bits>;
<tipo2> <nome2> : <tamnaho em bits>;
...
<tipon> <nomen> : <tamanho em bits>;
};
<tipo> pode ser: int, unsigned int e signed int.
Exemplo:
struct baralho
{
unsigned carta : 4;
unsigned nipe : 2;
};
struct baralho x;
x.carta = 9;
x.nipe = 2;
/* 0 a 15 */
/* 0,
1,
/* ouros, copas,
2,
espadas,
3
*/
paus */
/* 9 de espadas */
Ao contrário de estruturas normais, os bitfields não podem ser usados com pointers.
16.3 Uniões
Permitem armazenar em uma mesma região valores de tipos diferentes.
Forma de definição:
union <nome>
{
<tipo1> <campo1>;
<tipo2> <campo2>;
...
<tipon> <campon>;
};
// Exemplo:
51
union mixed
{
char c;
float f;
int i;
};
union mixed x;
x.c = 'A';
...
x.f = 10.0;
...
x.i = 1;
A área reservada para uma variável deste tipo é calculada pelo tamanho do maior campo. No
exemplo acima, a área reservada teria o tamanho de um float.
Devemos notar que uma variável deste tipo guarda apenas um valor de cada vez, isto é, ao
armazenar o dado de um novo tipo apaga o do tipo anterior.
A seguir é apresentado um exemplo no qual se monta em array de estruturas que guarda elementos
de "tipos" diferentes.
/* Exemplo do uso combinado de estrutura e união:
Cria um array denominado tabela e dimensão TAMANHO.
Cada elemento do array contem uma estrutura que consiste de um ponteiro para caractere (nome),
um inteiro (tipo) e um membro do tipo union chamado "dados".
Cada membro dados do array pode conter int, float ou char. */
# include <stdio.h>
# define INTEGER 0
# define FLOATING 1
# define CHAR 2
# define TAMANHO 6
void main ( )
{
struct
{
char *nome;
int tipo;
union
{
52
int i;
float f;
char c;
} dados;
} tabela [TAMANHO]; // Cria uma um vetor de estruturas denominado tabela
int j;
// Inicia os elementos da estrutura
tabela[ 0 ].nome
= "Cesar";
tabela[ 0 ].tipo
= CHARACTER;
tabela[ 0 ].dados.c
= 'A';
tabela[ 1 ].nome
= "do Vale ";
tabela[ 1 ].tipo
= CHARACTER;
tabela[ 1 ].dados.c
= 'A';
tabela[ 2 ].nome
= "Ferrari ";
tabela[ 2 ].tipo
= CHARACTER;
tabela[ 2 ].dados.c = 'A';
tabela[ 3 ].nome
tabela[ 3 ].tipo
tabela[ 3 ].dados.i
= "Idade ";
= INTEGER;
= 42;
tabela[ 4 ].nome
tabela[ 4 ].tipo
tabela[ 4 ].dados.f
= "Salário ";
= FLOATING;
= 7200.56;
tabela[ 5 ].nome
tabela[ 5 ].tipo
tabela[ 5 ].dados.f
= "Imposto ";
= FLOATING;
= 2785.89;
for (j = 0; j < TAMANHO; j++)
{
printf (" %s ", tabela[ j ].nome);
switch (tabela[ j ].tipo)
{
case INTEGER:
printf (" %d\n", tabela[ j ].dados.i);
break;
case FLOATING:
printf (" %.2f\n", tabela[ j ].dados.f);
break;
case CHARACTER:
53
}
}
}
printf ("%c\n", tabela[ j ].dados.c);
break;
default:
printf ("Tipo desconhecido %d - elemento %d.\n", tabela[ j ].tipo, j);
break;
16.4 Pointers para Estruturas
Como vimos anteriormente, devemos passar as estruturas através de pointers e não por valor. Isto
deve ser feito mesmo que não alteremos nenhum dos campos da estrutura.
/* Exemplo - Pointer para estruturas */
#include <stdio.h>
struct s_data
{
int dia, mes, ano;
};
typedef struct s_data sdata;
void prtdata (sdata *);
void main ( )
{
sdata data;
data.dia
= 15;
data.mes = 3;
data.ano = 1988;
prtdata ( &data);
/* passa o endereço da estrutura data */
}
void prtdata(sdata *data)
{
printf(" %d/% d/ %d \n", (*data).dia, (*data).mes, (*data). ano);
}
Existem duas formas de se acessar os valores de uma estrutura através de pointers:
54
(* < pointer >).< componente > ou
Exemplo:
sdata data, *pdata;
pdata = &data;
(*pdata).dia = 31;
(*pdata).mes = 12;
(*pdata).ano = 1989;
< pointer >  < componente >;
// ou pdatadia = 31;
// ou pdatames = 12;
// ou pdataano = 1989;
16.5 Ponteiro para percorrer array de ponteiros.
Como para os outros arrays, o nome de um array de ponteiros é um ponteiro para o primeiro
elemento do array. Quando se passa um array de ponteiros como parâmetro, o que realmente se passa é
um pointeiro para o primeiro elemento do array.
// Exemplo: Imprimir tabela 'dias'.
typedef char *CHARPTR;
/* define tipo pointer para char */
void print_tab(CHARPTR *tab_ptr, int n)
{
CHARPTR *end_ptr = tab_ptr + (n - 1);
while (tab_ptr <= end_ptr)
printf (" %s\n", *tab_ptr++);
}
Esquema dos ponteiros:
tab_ptr
0
1
.
.
.
end_ptr
6
s
e g u n d a \0
t
e r
ç
d o m i
a \0
n g o \0
17. Ponteiros para Funções
55
Permitem passar funções como argumentos.
Forma de definição:
< tipo > (* func_ptr ) ( < tipos dos argumentos > );
Nota: se não forem colocados os parênteses, estará sendo defininda uma função que retorna um pointer
para <tipo>.
// Exemplo:
int soma (int, int);
void main ( )
{
int (*ptr_soma) (int, int);
ptr_soma = soma;
x = (*ptr_soma) (3,5);
}
// pointer para função soma
//  x = soma (3, 5);
// Exemplo: Fazer um programa que leia duas cadeias de caracteres numéricos ou alfanuméricos e as
compare conforme o seu tipo.
# include <stdio.h>
# include <stdlib.h>
# include <string.h>
int numcmp (char *, char *);
void check (char *, char *, int (*cmp) (char *, char *));
void main ( )
{
char s1[ 80 ], s2[ 80 ];
gets (s1);
gets (s2);
if (isalpha (*s1) )
else
}
// obtém a primeira cadeia
// obtém a segunda cadeia
// isalpha devolve um valor  de zero se no endereço apontado por s1
// haver um caractere alfabético ou zero em caso contrário
check (s1 ,s2, strcmp);
// computa como caracteres
check (s1, s2, numcmp); // comp. como números
void check (char *a, char *b, int (*cmp)(char *, char *))
56
{
if ( ! ( *cmp) (a, b) )
printf(" \n Iguais.\n");
else
printf ("\n Diferentes.\n");
}
int numcmp(char *a, char *b)
{
if (atoi ( a ) == atoi ( b ) )
return ( 0 );
else
return ( 1 );
}
Observações sobre o exemplo:
 a função strcmp compara strings
 a função isalpha retorna <> 0 para letra do alfabeto
 a função atoi transforma uma string em número inteiro
57
18.
Tipos Construídos
18.1. Tipo enumerado
Faz com que uma variável possa ter somente um valor dentre um conjunto determinado de valores.
Forma de definição:
enum <nome> {<conjunto de valores separados por vírgulas>};
Exemplo:
enum dia
{segunda, terça, quarta, quinta, sexta, sábado, domingo};
0
1
2
3
4
5
6
Este exemplo define o tipo dia. Uma variável deste tipo somente poderá receber um dos valores dados
entre parênteses.
enum dia, dia1, dia2, todos[7]; /* define variáveis */
dia1 = segunda;
todos[6] = domingo;
Note que os valores entre parênteses não são strings.
Uma outra forma de definição possível é:
enum {segunda, ..., domingo} dia1, dia2;
Se usarmos as definições acima, a cada valor do tipo enumerado será associado um valor inteiro, a
partir de zero (0). Entretanto, podemos indicar os valores inteiros que desejamos associar:
enum frutas {laranja = 7, lim,o = 6, jaca = 0};
enum frutas {pera = 2, laranja, abacate, lim,o = 7};
Apesar das definições acima, os valores dos tipos enumerados não são inteiros.
Erros:
dia1 = 1.0;
dia2 = 2;
Para usarmos o valor inteiro associado, devemos usar um "cast" para inteiro:
i = (int) dia1;
58
19. Arquivos
A linguagem C possui alguns arquivos pré-definidos e que são automaticamente abertos quando um
programa começa a ser executado.
Eles são:
stdin
stdout
stderr
stdprn
standard
standard
standard
standard
input
output
error
printer
(default = teclado)
(default = vídeo)
(default = vídeo)
(somente alguns compiladores)
Os arquivos pré-definidos stdin, stdout e stderr podem ser redirecionados pelo usuário.
O arquivo stdprn é dependente do compilador, podendo existir ou não.
Para estes arquivo pré-definidos, a leitura e impressão se passam como se estivéssemos utilizando um
arquivo texto (leitura e gravação seqüenciais).
O conceito de arquivos em C é um pouco diferente do de outras linguagens. Na maioria das linguagens,
o tipo de acesso (direto ou seqüencial) está diretamente ligado à forma de abertura do arquivo, o que
não acontece em C.
Em C, o acesso a um arquivo pode ser direto ou seqüencial, sendo que esta escolha é feita conforme as
necessidades do usuário.
O C possui funções que permitem o acesso tanto direto quanto seqüencial e permitem um acesso
bastante eficiente à arquivos.
Forma de definição:
FILE *fp;
Para que esta definição esteja correta, é necessário que o arquivo stdio.h tenha sido incluído.
19.1. Funções para abertura e fechamento de arquivos
 Abertura de arquivos:
FILE *fopen(char *, char *);
fp = fopen (nome, modo);
Esta função abre o arquivo de nome "nome" com o modo "modo"."nome" e "modo" são strings de
caracteres.
59
Os modos de abertura possíveis são apresentados na tabela abaixo:
Modo
Tipo
Read
Write
Cria
Append
r
t
s
n
n
n
r+
t
s
s
n
n
rb
b
s
n
n
n
rb+
b
s
s
n
n
w
t
n
s
s
n
w+
t
s
s
s
n
wb
b
n
s
s
n
wb+
b
s
s
s
n
a
t
n
s
s
s
a+
t
s
s
s
s
ab
b
n
s
s
s
ab+
b
s
s
s
s
Onde:
 r read
 w write
 a append
 t texto
 b binário
 s sim
 n não
Em caso de sucesso na abertura, a função fopen retorna um ponteiro para o arquivo, o qual será
utilizado como nome lógico do arquivo dentro do programa e, em caso de erro, retorna NULL.
É responsabilidade do usuário verificar se o arquivo foi aberto ou não.
Exemplo:
fp = fopen ("teste.dat", "r");
if (fp == NULL)
/* ou if (!fp) */
{
printf(" \n Erro: abertura de arquivo para leitura");
exit ( 1 ); /* retorna para o sistema operacional */
}
O nome do arquivo pode indicar um nome simples ou um nome com path (caminho).
60
Exemplos de nomes:
"teste.dat"
"C:\programas\testes\teste.dat"
A diferença básica entre os modos texto e binário reside no fato de que quando os arquivos são abertos
no modo texto para gravação, o caractere NL (New Line) é convertido em dois: CR (Carriage Return)
e LF (LineFeed) e quando são abertos no modo texto para leitura, ocorre o inverso. Para arquivos
abertos no modo binário, esta conversão não existe, havendo, portanto, uma correspondência de 1 para
1.
 Fechamento de arquivos:
int fclose(FILE *);
fclose(fp);
Em caso de sucesso a função fclose ( ) retorna NULL, e em caso de erro um valor diferente de zero
(0).
Exemplo:
if ((fp = fopen ("teste.dat", "r")) == NULL)
{
printf (" \n Erro de abertura para leitura");
exit(1);
}
...
...
fclose(fp);
19.2. Principais funções para leitura e gravação seqüenciais
Leitura:
char *fgets(char *, int, FILE *);
pchar = fgets(buffer, num, fp);
Lê caracteres do arquivo dado por fp. A leitura termina quando forem lidos num – 1 caracteres, ou
quando encontrar o caractere NL (New Line) ou EOF (End Of File).
Os caracteres lidos são colocados em um buffer. Se a leitura foi correta, a função retorna um pointer
para o buffer e em caso de erro retorna NULL.
O buffer deve ser grande o suficiente para que sejam colocados os caracteres '\0' e NL.
61
Exemplo:
char *pchar, buffer[ 100 ];
FILE *fp;
...
pchar = fgets(buffer, 98, fp);
...
int fgetc (FILE *);
v_int = fgetc ( fp );
Lê um caractere do arquivo dado por fp e retorna o seu código ASCII. Se a leitura chegar ao final do
arquivo ou houver erro de leitura, é retornado EOF. Entretanto, deve-se usar esta função com certo
cuidado, já que EOF pode ser um caractere válido em arquivos abertos no modo binário.
int fscanf (FILE *, char *, ...);
fscanf(fp, fmt, args);
Funciona de forma semelhante à função scanf. Le as variáveis em args com o formato fmt do
arquivo dado por fp. Em caso de sucesso, retorna o número de variáveis que foram lidas. Caso se
chegue ao final do arquivo, é retornado EOF.
Gravação:
int fputs (char *, FILE *);
fputs (str, fp);
Grava a string str no arquivo dado por fp. A função retorna zero (0) se gravou bem e outro valor em
caso de erro.
int fputc (int, FILE *);
fputc (carac, fp);
Grava o caractere que está na variável carac no arquivo dado por fp. Em caso de erro, retorna EOF,
porém se o arquivo for aberto em modo binário, EOF poderá ser um caractere válido.
int fprintf (FILE *, char *, . . . );
fprintf (fp, fmt, args);
Funciona de forma semelhante à função printf. Grava as variáveis em args com o formato fmt no
arquivo dado por fp. Em caso de sucesso, retorna o número de caracteres que foram gravados e em caso
de erro, retorna um número negativo.
62
// Exemplo: fazer um programa que copie um arquivo em disco para outro. Os nomes dos
// arquivos são fornecidos como parâmetros na linha de comando, sendo o primeiro o
/ nome do arquivo origem e segundo o nome do arquivo destino.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void main (int argc, char *argv[])
{
char buffer [ 512 ];
char arqorg [ 150 ], arqdst [ 150 ];
FILE *nome1, *nome2;
if (argc < 3)
{
printf(" \n Erro: Número de parâmetros incorreto");
exit ( 1 );
}
}
strcpy (arqorg, argv [ 1 ] );
strcpy (arqdst, argv [ 2 ] );
nome1 = fopen ( arqorg, "rb");
nome2 = fopen ( arqdst,"wb");
if (nome1 == NULL | | nome2 == NULL)
{
printf(" \nErro na abertura dos arquivos.\n");
exit ( 1 );
}
while (fgets (buffer, 512, nome1) )
fprintf (nome2, buffer);
fclose (nome1);
fclose(nome2);
63
19.3. Principais funções para leitura e gravação direta (binário)
Normalmente, para acesso direto se abre o arquivo como binário, para que a correspondência de
caracteres seja de 1 para 1.
19.3.1. Funções para posicionamento:
 rewind: coloca o ponteiro interno de IO no início do arquivo dado por fp.
void rewind (FILE *);
rewind ( fp );
 fseek – move o ponteiro interno de IO do arquivo dado por fp conforme offset e origem. O
parâmetro offset indica o número de bytes, a partir da origem origem, que o ponteiro deve se
deslocar. Os valores possíveis para origem são:
0 ou SEEK_SET 
1 ou SEEK_CUR 
2 ou SEEK_END 
início do arquivo
posição atual do ponteiro
final do arquivo
int fseek (FILE *, long int, int);
x = fseek (fp, offset, origem);
// Note que a variável offset é do tipo long int.
// Por exemplo, a instrução fseek (fp, 0l, 0) é equivalente a rewind (fp).
// A função fseek retorna zero (0) para sucesso e um valor diferente de zero (0) para erro.
 fread : lê para buf nblocos de tam bytes do arquivo dado por fp.
int fread (void *, int, int, FILE *);
x = fread (buf, tam, nblocos, fp);
// A função fread retorna o número de blocos lidos.
 fwrite: funciona como fread, só que para gravação. A função retorna o número de blocos que foram
gravados.
int fwrite (void *, int, int, FILE *);
x = int fwrite (buf, tam, nblocos, fp);
// Exemplo: gravar e ler a variável double x de um arquivo.
...
double x;
64
...
fwrite (&x, sizeof (double), 1, fp);
...
fread (&x, sizeof (double), 1, fp);
 ftell: retorna a posição atual (em bytes) do ponteiro do arquivo em relação à origem.
long ftell ( FILE *);
y = ftell ( fp );
// Exemplo: Fazer um programa inicie um vetor de 100 elementos com os números de 0 a 99,
// o grave em um arquivo e o leia para outro vetor.
# include <stdio.h>
# include <stdlib.h>
void main ( )
{
FILE *fp;
int i;
float v1[100], v2[100], *pv;
for (pv = v1, i = 0; i < 100; i++)
*pv++ = (float) i; /* inicializa o vetor */
/* abre o arquivo */
if ((fp = fopen("teste.dat", "wb")) == NULL)
{
printf("\nErro de abertura: gravação");
exit ( 1 );
}
fwrite(v1, sizeof(float), 100, fp);
/* grava vetor */
fclose(fp);
/* fecha o arquivo */
/* reabre o arquivo teste */
if ( ( fp = fopen ("teste.dat", "rb")) == NULL)
{
printf(" \n Erro de abertura: leitura");
exit ( 2 );
}
fread ( v2, sizeof (float), 100, fp);
fclose ( fp );
for (pv = v2, i = 0; i < 100; i++)
/* lê para novo vetor*/
/* fecha o arquivo */
65
printf (" %.2f\n", *pv++);
/* imprime vetor lido */
}
/* Exemplo: Fazer um programa que grave em um arquivo três vetores de 100 elementos cada, sendo o
primeiro formado pelos números de 0 a 99, o segundo os 100 primeiros números pares e o terceiro os
100 primeiros múltiplos de 3. A seguir fechar o arquivo e reabri-lo lendo e imprimindo cada um dos
vetores. */
# include <stdio.h>
#i nclude <stdlib.h>
# define TAM 100
void main ( )
{
FILE *fp;
int i;
float v1[TAM], *pv;
// Abre arquivo testando se houve erro.
if ((fp = fopen ("teste.vet", "wb")) == NULL)
{
printf(" \n Erro ao abrir arquivo inicial.\n");
exit(1);
}
for (pv = v1, i = 0; i < TAM; i++) *pv++ = (float) i;
/* gera num. de 0 a 99 */
// Grava apenas um bloco de tamanho v1, o que equivale a gravar sizeof (float) x TAM
// Testa se gravou tudo.
if (fwrite(v1, sizeof(v1), 1, fp) != 1)
{
printf (" \n Erro ao gravar vetor 1.\n");
exit ( 2 );
}
for (pv = v1, i = 0; i < TAM; i++)
*pv++ = (float) i * 2; /* vet: 0,2,4,...,198 */
// Grava TAM blocos com dimensão float, o que equivale a gravar sizeof (float) x TAM
// Testa se gravou tudo.
if (fwrite(v1, sizeof(float), TAM, fp) != TAM)
{
printf (" \n Erro ao gravar vetor 2.\n");
exit ( 3 );
}
for (pv = v1, i = 0; i < TAM; i++) *pv++ = (float) i * 3; /* vet: 0,3,6,...,297 */
// Grava TAM blocos com dimensão float, o que equivale a gravar sizeof (float) x TAM
// Testa se gravou tudo.
if (fwrite(v1, sizeof(float), TAM, fp) != TAM ){
printf ("\nErro ao gravar vetor 3.\n");
exit ( 4 );
66
}
fclose ( fp );
/* fecha o arquivo */
// Reabre arquivo testando se houve erro.
if ((fp = fopen("teste.vet", "rb")) == NULL)
{
printf(" \n Erro ao reabrir o arquivo.\n");
exit ( 5 );
}
fread(v1, sizeof(v1), 1, fp);
for (pv = v1, i = 0; i < TAM; i++)
printf("%f ", *pv++);
printf ("\n\n");
rewind (fp);
/* lê o primeiro vetor */
/* imprime primeiro vetor */
/* pula 2 linhas */
/* volta ao início arquivo */
// A partir do inicio e com deslocamento v1, aponta para o segundo vetor.
fseek (fp, (long) sizeof (v1), 0);
fread (v1, sizeof (float), TAM, fp);
for (pv = v1, i = 0; i < TAM; i++) printf("%f ", *pv++);
printf ("\n\n");
rewind (fp);
// lê o segundo vetor
// imprime segundo vetor
// pula 2 linhas
// volta ao início arquivo
// A partir do início e com deslocamento de 2 x v1, aponta para o terceiro vetor.
fseek (fp, (long) sizeof (v1) * 2,0);
fread (v1, sizeof (v1), 1, fp);
/* lê o terceiro vetor */
for (pv=v1, i=0; i<TAM; i++)
printf("%f ", *pv++);
/* imprime o terceiro vetor */
printf ("\n\n");
/* pula duas linhas */
fclose (fp);
/* fecha arquivo */
}
// Exemplo do uso de estruturas em arquivos:
struct s_prop
{
char nome[20];
double mod;
double coef;
};
typedef struct s_prop sprop;
sprop prop;
sprop variasprops[100];
...
/* grava uma propriedade */
67
fwrite (&prop, sizeof(sprop), 1, fp);
/* grava um elemento da estrutura */
/* grava vetor com várias propriedades */
fwrite(variasprops, sizeof(sprop), 100, fp);
PARTE II
Estruturas de Dados Básicas
1. Introdução
Esta parte da apostila apresenta os principais conceitos das estruturas de dados computacionais mais
básicas, com exemplificação através de alguns algoritmos para manipulação das mesmas.
Registra-se ainda que, por razões didáticas, os programas que ilustram a manipulação das estruturas aqui
estudadas estão propositalmente incompletos. Eles são destinados a compor exercícios práticos de
manipulação das respectivas estruturas.
Mais: estes exemplos foram confeccionados na tentativa de permitir aos ineteressados um estudo sobre
várias modalidades de tratamento das estruturas de dados aqui tratadas, tais como armazenamento ordenado
não, segundo alguma chave especificada. E isto vale tanto para as estruturas estáticas como para as estruturas
dinâmicas.
2. Listas Linearaes - Definição:
Uma lista linear, ou tabela, é um conjunto de n  0 nós, ou elementos, N[1], N[2], … , N[n] tais que as suas
propriedades estruturais decorrem, unicamente, da posição relativa dos nós dentro da seqüência linear.
Tem-se:
se n > 0, N[1] é o primeiro nó, ou se 1 < k  n, o nó N[k] é precedido por N[k-1] nós.
Onde cada nó é formado por “campos”, que armazenam as características distintas dos elementos da lista.
Além disso, cada nó da lista possui, geralmente, um campo que opera como identificador, denominado chave, e
que pressupõem-se sejam diferentes para cada nó [MARKENSON,1994].
3. Alocação Estática:
Os elementos são armazenados seqüencialmente na memória. O (w+1)-ésimo elemento se encontra “k”
elementos adiante daquele correspondente ao w-ésimo, onde “k” é o número de células de memória que cada
nó ocupa.
4. Listas Lineares com Alocação Estática:
Seja uma lista linear N formada por n elementos. Cada elemento é formado por campos que armazenam
suas características individuais. Além disso, cada elemento da lista possui, geralmente, um identificador,
denominado chave de acesso, ou simplesmente chave.
Para evitar ambigüidades, supõe-se que todas as chaves são distintas. A chave, quando presente, se
constitui em um dos campos do elemento.
68
Abaixo é apresentada uma representação gráfica de uma possível lista linear estática com n nós:
o
Nó 1
matrícula do 1 aluno
o
nome do 1 aluno
o
idade do 1 aluno
Nó 2
Nó 3
Nó n
matrícula do n-ésimo aluno
nome do n-ésimo aluno
idade do n-ésimo aluno
A seguir, são apresentados os algoritmos para buscar em uma lista estática N, considerando-se:
x = chave de busca;
i = índice do nó na Lista;
n = quantidade atual de elementos na Lista;
m = quantidade máxima possível de elementos na Lista; e
chave = campo chave no elemento.
No caso da busca, são apresentados dois algoritmos em forma de função: a busca linear e a busca binária.
Em ambos os casos é retornado, ao final, o índice i do nó procurado na lista, ou 0 (zero) caso este não tenha
sido encontrado.
No caso da busca seqüencial, com a finalidade de otimizar a busca do elemento na lista, sua chave é
sempre inserida no (n+1) - ésimo elemento da lista. Assim, é sempre garantido que o algoritmo encontrará o
elemento desejado. No entanto quando o elemento procurado estiver nseta posição (n+1), isto significará que
ele não faz parte da lista.
É óbvio que para utilização desta facilidade é necessário que a lista tenha sido declara com elemento a mais
do que o considerado necessário.
O segundo algoritmo (mais eficiente na maioria dos casos) é conhecido como busca binária. Nele, procurase o elemento de chave "x" dividindo-se a lista em duas partes e testando em qual das duas ele deve estar.
Repete-se este procedimento para a parte provável, e assim por diante, até encontrar o elemento procurado ou
exaurir a pesquisa da lista. A variável início deve ser iniciada com o índice do primeiro elemento da parte da
Lista a considerar, e a variável fim deve ser iniciada com o índice do último elemento da parte da Lista a
considerar.
Enquanto o primeiro algoritmo de busca – Busca Seqüencial – funciona para qualquer tipo de lista estática,
o segundo – Busca Binária – só funciona corretamente se a Lista estiver ordenada.
A seguir são apresentados vários algoritmos, em linguagem C++, que ordenam Listas Estáticas, desde que
adequados às mesmas, sendo que um deles – Bubble Sort – é utilizado no programa exempplo de manipulação
69
de Lista Estática. Logo após, são apresentados os códigos de outras duas funções que pesquisam Listas
Estáticas Ordenadas, utilizando as técnicas de Busca Seqüencial e de Busca Binária.
5. Ordenações
5.1.
Ordenação de uma Lista L de Inteiros Pelo Método da Inserção Direta – Insert Sort
void
{
}
5.2.
5.3.
// Assuma que a lista L e a quantidade de
//
nodos a ordenar estão em variáveis Globais
int i, j aux ;
// Ordena o Vetor Pelo Método da Inserção Direta
for ( i = 1; I <dim; i++)
{
aux = L[ i ];
for ( j = i1; j >= 0 && aux < L[ j]; j) L[ j+1 ] = L[ j ];
L[ j+1 ] = aux;
}
Ordenação de uma Lista L de Números Pelo Método da Seleção Direta – Select Sort
void
{
}
insercao ( )
seleção_direta ( )
// Assuma que a lista L e a quantidade de
//
nodos a ordenar estão em variáveis Globais
int i , j , indx , aux ;
// Ordena o Vetor pelo Método da Seleção Direta
for ( i = dim1; i > 0; i  )
{
aux = L[ 0 ];
indx = 0;
for (j=1; j<=i; j++)
if (L[ j ] > aux)
{
aux = L[ j ];
indx = j;
}
L[ indx ] = L[ i ];
L[ i ]
= aux;
Ordenação de uma Lista L de Inteiros Pelo Método da Bolha – Bubble Sort
void
{
bolha ( )
int i , j , aux;
for ( i = 0; i < dim1; i++)
for ( j = i+1; j < dim; j++)
if (L[ i ] > L[ j ])
{
aux = L[ i ];
L[ i ] = L[ j ];
L[ j ] = aux;
}
// Assuma que a lista L e a quantidade dim
//
de nodos a ordenar estão em variáveis Globais
// Ordena o Vetor
70
}
5.4.
Ordenação de uma Lista L de Inteiros Pelo Método de Ordenação Rápida – Quick Sort
Este método foi proposto por Hoare, C.A. R. [HOARE,62] e seu desempenho é tão espetacular, que seu
inventor denominou-o “Quick Sort”, ou seja, Ordenação Rápida.
De fato, comparado os demais métodos, é o que apresenta, em média, o menor tempo de classificação. Isto
porque, embora tenha um desempenho logarítmico como muitos outros, é o que apresenta menor número de
operações elementares por iteração o que significa que, mesmo que se tenha de efetuar uma quantidade de
iterações proporcional a nlog2 n, cada uma delas será mais rápida.
A implementação do método exigirá, portanto, a definição de duas funções: uma para executar os
particionamentos, e outro para efetuar todos os particionamentos necessários.
A primeira função, denominada particao é apresentada a seguir:
// Obs.: os argumentos de entrada devem ser passados por referência.
// vet = vetor de números inteiros; e k = posição da chave particionadora após particionamento
void
{
}
particao ( int vet [ ], int i, int f, int k )
int
i1 , f1 , cp , esq;// esq faz o papel de variável lógica: esq = 1 = verdade .:. esq = 1 = falso
i1 = i ;
f =f
cp = vet [ i1 ]
esq = 0 ;
while ( i1 < f1)
if (esq)
if (cp >= vet [ f1 ])
// esquerda vaga
{
vet [ i1 ] = vet [ f1 ];
// transfere para S1
i1 = i1 + 1;
esq = 0;
// faz esq = falso
}
else f1 – – ;
else if (cp < vet [ i1 ])
// direita vaga
{
vet [ f1 ] = vet [ i1 ]
// transfere para S3 }
f1 – – ;
esq
=1
// faz esq = verdadeiro
}
else i1++;
k = i1;
vet [ k ] = cp;
// ou k = f1 já que neste ponto i1 = f1
Uma alternativa de implementação da operação de particionamento, adequada quando a chave
particionadora escolhida ocupar uma posição intermediária do vetor a ser particionado e possuir um valor
mediano, foi proposta por [WIRTH,89], e funciona da seguinte forma: uma vez escolhida a chave particionadora
(denominada cp), percorre-se o vetor a ser particionado da esquerda para a direita, até que seja encontrada
uma chave vet [ i ]>cp.
71
A seguir percorre-se o vetor da direita para a esquerda, até que seja encontrada uma chave vet [ j ] < cp.
Nesta ocasião as duas chaves vet [ i ] e vet [ j ] são permutadas de posição. As varreduras prosseguem a
partir destes pontos, até que os dois deslocamentos se encontrem em uma posição intermediária do segmento.
Á esquerda ficarão as chaves menores ou iguais á particionadora e a direita as maiores.
Observe que este processo divide o segmento em dois outros, já que a particionadora é usada apenas como
referência e irá estar sempre contida no segmento da esquerda.
Independentemente da implementação usada para efetuar os particionamentos, deve-se implementar o
procedimento que irá efetuar todos os particionamentos necessários para ordenar o vetor. Essa operação
(particionamento sucessivo) é claramente recursiva, uma vez que, obtido o primeiro particionamento, a
operação é reaplicada sobre os segmentos resultantes, até que todas as partições fiquem reduzidas a um único
elemento.
Assim, o procedimento que implementa a operação refletirá esta natureza recursiva sendo recursivo também
(e, também, todos os argumentos devem ser passados por referência) :
void
{
quick_sort ( int vet [ ] , int i, int f )
if (f > i)
{
partição
( vet , i , f , 1 )
quick_sort ( vet , i , k –1 )
quick_sort ( vet , k +1, f )
//
//
//
//
}
testa se segmento não é unitário
particiona forçando a chave no elemento 1
ordena segmento da esquerda
ordena segmento da direita
}
Obs.: Em linguagens de programação que não suportam a recursividade, a implementação da função
quick_sort deve manipular explicitamente a pilha de pedidos pendentes de particionamento.
5.5.
Ordenação de uma Lista L de Inteiros Pelo Método de Ordenação por Intercalação – Merg Sort
A classificação por intercalação consiste em dividir o vetor de chaves a ser classificado, em dois ou mais
vetores, ordená-los separadamente e, depois, intercalá-los dois a dois, formando, cada par intercalado, novos
segmentos ordenados, os quais serão intercalados entre si, reiterando-se o processo até que resulte apenas um
único segmento ordenado.
void
{
simple_merge (int c [ ], int, int is1, int fs1, int is2, int fs2,int c1, int r )
int
k, is11 , is22 ;
is11 = is1;
is22 = is2;
k = r;
while ( is11 <= fs1 ) && (is22 <= fs2 )
// enquanto não atingir o final de
{
//
nenhum dos dois segmentos compara
if (c [ is11 ] < c [ is22 ]
//
os 1os. elementos de cada segmento
{
c1 [ k ] = c [ is11 ];
// faz cópia do 1º. segmento
is11++;
}
else { c1 [ k ] = c [ is22 ];
is22++;
}
k = k+1
}
if ( is11 > fs1 )
// verifica saldo dos segmentos
for ( i = is22; i <= fs2; i++)
// copia resto do 2 segmento
{
c1 [ k ] = c [ 1 ];
k++;
}
else for (i = is11; i <=fs1; i++)
{
c1 [ k ] = c [ i ] ;
// copia resto do 1 segmento
k++;
72
}
void
{
}
}
merge_pass ( int c [ ], int c1 [ ], int n, int m )
int p , q , r;
p = 1;
q : = p + n;
r:=1
while (q <= n)
{
simple_merge (c,p,(q–1),q,min(q+m–1,n),c1,r )
r = r + (2*m);
p=q+m;
q = p + m;
}
if ( p <=n )
for (i = p; i <=n; i++)
c1 [ i ] = c [ i ];
// m = comprimento dos segmentos
// p = início do segmento 1
// q = início do segmento 2
// r = início do segmento resultante
// enquanto houver pares de segmentos
// min = f devolve o menor dos 2 parâmetros
// intercala 1 par de segmentos
// próximo segmento resultante
// próximo segmento 1
// próximo segmento 2
// verifica se o último segmento possui par
// se não m transcreve para c1 {p..n }
5.6. Ordenação de uma Lista L de Inteiros Pelo Método de Ordenação por Inserção Direta Otimizada –
Shell Sort
Este método, proposto em 1959 por Donald L. Shell [SELL,59], explora o fato de que o método da inserção
direta apresenta desempenho aceitável quando o número de chaves é pqueno e / ou estas já possuem uma
ordenação parcial.
void shell_sort ( int vet [ ], int size )
// vet = vetor a ordenar e size = dimensão a ordenar
{
int i , j , value;
int gap = 1;
do
{
gap = 3*gap+1;
}
while ( gap < size );
do
{
gap /= 3;
for ( i = gap; i < size; i++ )
{
value =vet [ i ];
j = i  gap;
while ( j >= 0 && value < vet[ j ] )
{
vet [ j + gap ] = vet[ j ];
j = j – gap;
}
vet [ j + gap] = value;
}
}
while ( gap > 1);
}
73
6. Busca Nodos de Chave x em Listas L de Tamanho Fim ( Quantidade de Elementos na Lista )
A seguir são apresentados os dois algoritmos mais usais – Busca Sequencial e Busca Binária – para se
pesquisar se uma certa chave (um identificador), está ou não presente em uma lista estática.
No entanto, observe que o segundo algoritmo apresentado – Busca Binária – só funciona corretamente
quando a lista sobre a qual irá operar, está ordenada (crescente ou decrescentemente) pelos campos das
chaves.
6.1.
Busca Seqüencial
int busca_sequencial (
{
}
6.2.
int
{
< tipo da variável chave > x ,
< tipo da variável com tamanho da lista > fim,
< tipo do array lista > L)
i=0;
while (L[ i ] <> x &&
i <=fim ) i ++;
// Pesquisa na lista
if (i <> (fim)
return ( i ) ;
// Achou: retorna a posição do elemento na lista
else
return ( dim + 1 ) ;
// Não Achou: retorna a dimensão máxima da lista + 1
Busca Binária
busca_binaria (
int
do
{
< tipo da variável chave > x,
< tipo da variável com tamanho da lista > fim,
< tipo do array lista > L)
inicio = 0, meio;
meio = ((inicio + fim) / 2) ;
if (x < L[ meio ] )
fim = meio  1
else
inicio = meio + 1 ;
}
while ( L[ meio ] != x ) && ( inicio <= fim ) ;
}
if ( L [ meio ] <> x)
return ( 1 ) ;
else
return ( meio ) ;
/* 1 = chave pesquisad não está na lista
*/
/* meio = índice para o nó com a chave buscada */
74
7. Recursividade
Há um tipo especial de procedimento utilizado na resolução de problemas que, em sua descrição, contém
uma ou mais chamadas a si mesmo.
Um procedimento dessa natureza é denominado recursivo, e a chamada a si mesma é dita recursiva.
Naturalmente, todo procedimento, recursivo ou não , deve possuir pelo menos uma chamada proveniente de
um local exterior a ele. Essa chamada é denominada externa. Um procedimento não recursivo é, pois, aquele
em que todas as chamadas são externas.
De modo geral, a todo procedimento recursivo corresponde de outro não recursivo que executa, exatamente,
a mesma computação. Contudo, a recursividade pode apresenta vantagens concretas. Freqüentemente,os
procedimentos recursivos são mais concisos do que um não recursivo correspondente. Além disso, muitas
vezes é aparente a relação direta entre um procedimento recursivo e uma prova por indução matemática.
Nesses casos, a verificação da correção pode se tornar mais simples. Entretanto, muitas vezes há
desvantagens no emprego prático da recursividade. Um algoritmo não recursivo equivalente pode ser mais
eficaz.
O exemplo clássico mais simples de recursividade é o cálculo do fatorial de um inteiro n  0. Um algoritmo
recursivo para efetuar esse cálculo encontra-se descrito em seguida. A idéia do algoritmo é muito simples.
Basta observar que o fatorial de n é n vezes o fatorial de n – 1, para n  0. deve-se sempre considerar Não
que, por convenção, 0! = 1.
No algoritmo a seguir, as chamadas recursivas são representadas pelo procedimento fatorial, e a chamada
externa deverá ser codificada como Fatorial ( N ).
/ Algoritmo 1: cálculo recursvo do fatorial de N
int
Fat ( int N )
{
if ( N = 0 )
return ( 1 );
else return ( N * Fat ( N  1) );
}
(N  Z , N  0) com a função Fat
Para efeito de comparação, o algoritmo 2 – abaixo – descreve o cálculo do fatorial de N de forma não
recursiva. A variável fatorial conterá, ao final, o valor do fatorial do número N.
// Algoritmo 2: cálculo não recursivo do fatorial de N ( N  Z , N  0)
...
fatorial = 1
para x = 1 até N passo 1 faça fatorial = fatorial * x
...
Um exemplo conhecido, onde a solução recursiva é natural e intuitiva, é o do Problema da Torre de Hanói.
Este consiste de três pinos, A, B e C, denominados origem, destino e trabalho, respectivamente, e n discos de
diâmetros diferentes.
Inicialmente, todos os discos se encontram empilhados no pino-origem, em ordem decrescente de tamanho,
de baixo para cima. O objetivo é empilhar todos os discos no pino-destino, atendendo às seguintes restrições: (i)
apenas um disco pode ser movido de cada vez; e (ii) qualquer disco não pode ser jamais colocado sobre outro
de tamanho menor.
75
A solução do problema é descrita a seguir. Naturalmente, para n > 1, o pino-trabalho deverá ser utilizado
como área de armazenamento temporário. O raciocínio utilizado para resolver o problema é semelhante ao de
uma prova matemática por indução. Suponha que se saiba como resolver o problema até n  1 discos, n > 1, de
forma recursiva. A extensão para n discos pode ser obtida pela realização dos seguintes passos.
 Resolver o problema da Torre de Hanói para os n  1 discos do topo do pino-origem A, supondo que o
pino-destino seja B e o de trabalho seja C.
 Mover o n-ésimo pino ( maior de todos) de A para B.
 Resolver o problema da Torre de Hanói para os n  1 discos localizados no pino C, suposto origem,
considerando os pinos A e B como trabalho e destino, respectivamente.
Ao final desses passos, todos os discos se encontram empilhados no pino B e as duas restrições (i) e (ii)
foram satisfeitas. O algoritmo 3 implementa o processo. O procedimento recursivo hanoi é utilizado com
quatro parâmetros n, A, B e C, representando, respectivamente, o número de discos, o pino-origem, o destino e
o trabalho, onde os pinos devem ser considerados como arrays unidimensionais. .
 Chamada:
Hanoi ( N , A , B , C)
 Onde:
=
=
=
=
N
A
B
C
{
A = B = C = arrays unidimensionais
}
Número de discos;
Pino origem
Pino destino
Pino de trabalho
void Hanoi ( n: int; <array unidimensional> A , <array unidimensional> B , <array unidimensional> C)
{
if (N > 1)
{
Hanoi ( N  1 , A , C , B ) ;
B[ N ] = A [ N ] ;
Hanoi ( N  1, C, B, A ) ;
}
}
A seguir, a título de ilustração, são apresentados dois programas que manipulam listas estáticas.
76
// Manipulação De Listas Estáticas Simples Com Pesquisa Seqüencial
#include <iostream>
#define dim 10
using namespace std;
void
void
void
void
void
void
menu
pausa
mensagem
inserir
retirar
mostrar
( );
( );
( );
( );
( );
( );
int lista[dim], i_lista = 1, aux, i;
char d;
int
{
}
void
{
main ( )
menu ( );
menu ( )
do
{
}
mensagem ( );
do
{
cout << " \n\n\n\t\t\t
ESCOLHA SUA OPCAO: \n";
cout << " \n\t\t\t [ I ] nserir Nos na Lista\n";
cout << " \n\t\t\t [ R ] etirar Nos da Lista \n";
cout << " \n\t\t\t [ M ] ostrar a Lista \n";
cout << " \n\t\t\t [ T ] erminar o Programa\n\n";
cout << " \n\t\t\t
DIGITE SUA OPCAO: ";
cin >> d; d = toupper (d);
while (d != 'I' && d != 'R' && d != 'M' && d != 'T');
switch
{
(d)
case 'I':
case 'R':
case 'M':
}
void
}
}
while (d != 'T');
inserir ( );
break;
retirar ( );
break;
mostrar ( );
break;
pausa ( )
77
{
cout << "\n\n\n\t\t
cin >> d;
}
void
{
}
void
{
Digite Uma Letra e <Enter> Para Continuar ";
mensagem ( )
system ("cls");
cout << "\n\n\n\n\t\t
MANIPULACAO DE LISTAS ESTATICAS SIMPLES";
inserir ( )
d = 'S';
if (i_lista == dim)
{
cout << "\n\n\t\t\tA LISTA ESTA CHEIA !!!";
pausa ( );
}
else // Ha Lugar na Lista ==> Insere Elemento
{
while (d == 'S' && i_lista < dim)
{
mensagem ( );
cout << "\n\n\n\t\t\t
INSERE NOS NA L.E.S.\n\n";
}
}
void
{
}
void
}
// Recebe e Armazena Dado na Lista
cout << "\n\n\t\t\t Digite Valor a Armazenar: ";
cin >> lista[++i_lista];
if (i_lista < dim)
do
{
cout << "\n\n\t\tDeseja Inserir Outro No na Lista: [S]im ou [N]ao ? ";
cin >> d;
d = toupper (d);
}
while (d != 'S' && d != 'N');
mostrar ( )
mensagem ( );
cout << "\n\n\n\n\n\t\t\t
i = 0;
MOSTRA OS VALORES NA L.E.S.\n\n";
if (i_lista != 1)
while (i <= i_lista)
cout << "\n\t\t\t
Valor no No " << i+1 << " = " << lista[i++];
else
cout << "\n\t\t\t
A LISTA ESTA VAZIA !!!";
pausa ( );
retirar ( )
78
{
d = 'S';
mensagem ( );
if (i_lista == 1)
{
cout << "\n\n\t\t\t A LISTA ESTA VAZIA !!!";
pausa ( );
}
else // Há Elementos na Lista --> Procura Elemento a Ser Retirado
{
while (d == 'S' && i_lista >= 0)
{
system ("cls");
cout << "\n\n\n\n\n\t\t\t\tRETIRA NOS DA L.S.E.\n\n";
// Solicita e Recebe o Número no Nó a Ser Retirado
cout << "\n\n\n\t\t Digite Valor (Chave) no Nodo a Ser Retirado: ";
cin >> aux;
// Pesquisa e Informa que Vai Retirar Nó da Lista
i = 0;
do
{
if (aux != lista[i]) i++;
}
while (i < dim && aux != lista[i]);
if (i < dim)
{
cout << "\n\n\t\t\tNo " << i+1 << " Com Valor " << lista[i] << " Saiu da Lista ";
i_lista ;
if (i_lista == 1)
{
cout <<"\n\n\t\t\t\tA Lista Ficou Vazia !!!";
pausa ( );
}
// Retira Nó da Lista
for (i=i; i < dim-1; i++) lista[i] = lista[i+1];
}
else
}
}
}
cout << "\n\n\t\t\tNo Com Valor " << aux << " Nao Esta na Lista !!!";
if (i_lista >= 0)
do
{
cout << "\n\n\n\n\t\t Deseja Retirar Outro No da Lista: [S]im ou [N]ao ? ";
cin >> d;
d = toupper (d);
}
while (d != 'S' && d != 'N');
// Manipulação De Listas Estáticas Simples – L.E.S.s
// Com Ordenação Através Da Técnica da Bolha, Pesquisa Com Busca Binária, e
79
// Uso de Recursividade Para Mostrar a Lista Invertidamente
#include <iostream>
#define dim 10
using namespace std;
void menu
( );
void pausa
( );
void mensagem( );
void inserir
( );
void retirar
( );
void mostrar
( );
void ordenar
(int);
int visualizar
(int);
int buscar
(int , int);
int lista[dim], i_lista = 1, aux, i, j;
char d;
int main ( )
{
menu ( );
}
void menu ( )
{
do
{
mensagem ( );
do
{
cout << "\n\n\n\n\t\t\t
ESCOLHA SUA OPCAO: \n\n";
cout << "\t\t\t[ I ] nserir Nodos na Lista\n";
cout << "\t\t\t[ R ] etirar Nodos da Lista \n";
cout << "\t\t\t[ M ] ostrar Lista do Inicio Para o Fim\n";
cout << "\t\t\t[ V ] isualizar Lista do Fim Para o Inicio\n";
cout << "\t\t\t[ T ] erminar o Programa\n\n";
cout << "\t\t\t
DIGITE SUA OPCAO: ";
cin >> d; d = toupper(d);
}
while(d!='I' && d!='R' && d!='M' && d !='V' && d!='T');
switch (d) { case 'I': inserir ( );
break;
case 'R': retirar ( );
break;
case 'M': mostrar ( );
break;
case 'V': mensagem( );
cout << "\n\n\n\n\n\t\t\tMOSTRA A L.E.S. INVERTIDA\n\n";
visualizar (i_lista);
pausa ( );
break;
}
}
while (d != 'T');
}
void pausa ( )
{
80
}
void
{
}
int
{
cout << "\n\n\n\n\n\t\t Digite Uma Letra e <Enter> Para Continuar ";
cin >> d;
mensagem ( )
system ("cls");
cout << "\n\n\n\n\t\t
MANIPULACAO DE LISTAS ESTATICAS SIMPLES";
buscar (int x, int fim)
int
do
{
// Efetua a Busca Binaria
inicio = 0, meio;
meio = (int)((inicio + fim)/2);
if (x < lista[meio])
{
fim = meio  1;
}
else
{
inicio = meio + 1;
}
}
while (lista[meio] != x && inicio <= fim);
}
if (lista[meio] != x)
return (1) ;
else
return (meio);
/* 1 = Nao encontrou a chave pesquisada */
/* meio = índice para o nó pesquisado
void ordenar ( )
{
for (i=0; i<dim-1; i++)
for (j=i+1; j<dim; j++)
if (L[ i ] > L[ j ])
{
aux = L[ i ];
L[ i ] = L[ j ];
L[ j ] = aux;
}
}
void
{
inserir ( )
81
*/
d = 'S';
if (i_lista == dim)
{
cout << "\n\n\t\t\t
pausa ( );
}
A LISTA ESTA CHEIA !!!";
else // Ha Lugar na Lista --> Insere Elemento
{
while (d == 'S' && i_lista < dim)
{
mensagem ( );
cout << "\n\n\n\t\t\t
INSERE NODOS NA LISTA\n\n";
// Recebe e Armazena Dado na Lista
cout << "\n\n\t\t\t Digite Valor a Armazenar: ";
cin >> lista[++i_lista];
// Verifica Se Deseja Inserir Outro Elemento na Lista
if (i_lista < dim)
do
{
cout << "\n\n\n\n\n\n\t
Deseja Inserir Outro Nodo na Lista:[S]im ou [N]ao ? ";
cin >> d;
d = toupper(d);
}
while (d != 'S' && d != 'N');
}
}
void
{
}
void
{
}
// Ordena a Lista Crescentementepelo Campo N
ordenar (i_lista); // Parametro = Numeros de Nodos na L.S.E.
mostrar ( )
mensagem ( );
cout << "\n\n\n\n\n\t\t\t MOSTRA OS VALORES NA L.E.S.\n\n";
if (i_lista >  1)
for (i = 0; i <= i_lista; i++)
{
cout <<"\n\t\t\t
Valor no No " << i+1 << " = " << lista[i];
}
else cout << "\n\t\t\tA LISTA ESTÁ VAZIA !!!";
pausa ( );
retirar ( )
d = 'S';
82
mensagem ( );
if (i_lista ==  1)
{
cout << "\n\n\t\t\t A LISTA ESTÁ VAZIA !!!";
pausa ( );
}
else // Há Elementos na Lista --> Procura Elemento a Ser Retirado
{
while (d == 'S' && i_lista >= 0)
{
cout <<"\n\n\n\n\n\t\t\t\tRETIRA NOS DA L.S.E.\n\n";
// Solicita e Recebe Numero no Nodo a Ser Retirado
cout << "\n\n\n\t\t Digite o Numero no Nodo a Ser Retirado: ";
cin >> aux;
// Pesquisa e Informa que Vai Retirar No da Lista
i = buscar (aux , i_lista);
// Verifica se Achou Nodo a ser Retirado
if (i > 1)
{ // Informa Saída do No da Lista
cout << "\t\t\t Retira No " << i+1 << " Com Valor " << lista[i];
pausa ( );
// Retira Elemento da Lista
for (i=i; i < i_lista; i++) lista[i] = lista[i+1];
i_lista   ;
// Força Saída do Laço While
d = 'N';
}
else cout <<"\n\n\t\t\tO Nodo Com valor " << aux << " Nao Esta na Lista !!!";
}
int
{
}
}
}
if (i_lista >= 0)
do
{
cout <<"\n\n\n\n\n\n\t\tDeseja Retirar Outro No da Lista: [S]im ou [N]ao ? ";
cin >> d;
d = toupper(d);
}
while (d != 'S' && d != 'N');
else pausa ( );
visualizar (int i)
if (i >  1)
{
cout << "\n\t\t\t Valor no Nodo " << i+1 << " = " << lista[i];
visualizar (i1);
}
return (0);
8. Pilhas em Ambientes de Alocação Estática
83
Utiliza apenas um índice – uma variável do tipo int, normalmente denominada topo – que aponta para o
último elemento colocado na pilha. Quando a pilha está vazia o topo deve ser igual a 1 (menos um)  em C
ou C++, por exemplo  ou 0 (zero)  em Pascal, por exemplo.
A seguir é apresentada uma representação gráfica de possíveis operações em uma pilha estática:
pilha vazia:
m
topo
2
1

m
inserir informação A
topo

A
2
1
m
inserir informação B
topo

B
A
2
1
m
retirar informação B
topo

A
2
1
m
retirar informação A
Topo

2
1
A seguir é apresentado um programa exemplo para a inserção, remoção e visualização de elementos em
uma pilha denominada “pilha”, de valores inteiros.
// Manipulação de Pilhas Estáticas
#include <iostream>
#define dim 10
84
using namespace std;
void menu
( );
void pausa
( );
void mensagem( );
void inserir
( );
void retirar
( );
void mostrar
( );
int pilha[dim] , topo = 1, aux , i;
char d;
int
{
}
main ( )
menu ( );
void menu ( )
{
do
{
system ("cls");
mensagem ( );
do
{
cout << "\n\n\n\n\t\t\t
ESCOLHA SUA OPCAO: \n\n";
cout << "\t\t\t[ I ] nserir Nodos na Pilha\n";
cout << "\t\t\t[ R ] etirar Nodos da Pilha \n";
cout << "\t\t\t[ M ] ostrar a Pilha \n";
cout << "\t\t\t[ T ] erminar o Programa\n\n";
cout << "\t\t\t
DIGITE SUA OPCAO: ";
cin >> d;
d = toupper(d);
}
while (d != 'I' && d != 'R' && d != 'M' && d != 'T');
switch (d)
{
case 'I': inserir ( );
break;
case 'R': retirar ( );
break;
case 'M': mostrar ( );
break;
}
}
}
while (d != 'T');
void pausa ( )
{
cout << "\n\n\n\n\n\t\t
cin >> d;
}
Digite Uma Letra e <Enter> Para Continuar ";
85
void mensagem ( )
{
system ("cls");
cout << "\n\n\n\n\t\t\tMANIPULACAO DE PILHAS ESTATICAS";
}
void
{
inserir ( )
d = 'S';
if (topo == dim)
{
cout << "\n\n\t\t\tA PILHA ESTA CHEIA !!!";
pausa ( );
}
else
{ // Há Lugar na Pilha --> Insere Elemento
while (d == 'S' && topo < dim)
{
mensagem ( );
cout << "\n\n\n\t\t\t
INSERE NODOS NA PILHA\n\n";
}
}
}
// Recebe e Armazena Dado na Pilha
cout << "\n\n\t\t\t Digite Valor a Armazenar: ";
cin >> pilha[++topo];
if (topo < dim)
do
{ cout << "\n\n\n\n\n\n\t
Deseja Inserir Outro No na Pilha: [S]im ou [N]ao ? ";
cin >> d;
d = toupper (d);
}
while (d != 'S' && d != 'N');
void mostrar ( )
{
system ("cls"); mensagem ( );
cout << "\n\n\t\t\t MOSTRA OS VALORES NA PILHA\n\n";
i = topo;
if (i >= 0)
{
cout << "\t Topo ==> ";
while (i >= 0)
{
cout <<" Valor no Nodo = " << i+1 << " = " << pilha[i--];
cout << "\n\t\t\t";
}
}
else cout << "\n\t\t\t A PILHA ESTA VAZIA !!!";
pausa ( );
}
void retirar ( )
{
d = 'S';
while (d == 'S')
{
system ("cls");
86
mensagem ( );
if (topo == 1)
{
cout << "\n\n\t\t\tA PILHA ESTÁ VAZIA !!!";
pausa ( );
}
else
{ // Há Elementos na Pilha ==> Retira Elemento
cout << "\n\n\n\n\n\t\t\t\tRETIRA NODOS DA PILHA\n\n";
cout << "\n\t\t\t ";
cout <<"Retirou Nodo " << topo+1 << " Com Valor " << pilha[topo];
topo--;
// Força Saída do Laço While
d = 'N';
}
}
}
// Verifica Se Pode e Se Deseja Retirar Outro Elemento da Pilha
if (topo >= 0)
do
{
cout << "\n\n\n\n\n\n\t\t";
cout << "Deseja Retirar Outro Nodo da Pilha: [S]im ou [N]ao ? ";
cin >> d;
d = toupper(d);
}
while (d != 'S' && d != 'N');
else
{
cout << "\n\n\n\t\t\t
A PILHA FICOU VAZIA !!!";
pausa ( );
}
9. Filas em Ambientes de Alocação Estática
São necessários dois índices para manipular tais estruturas. Para o início da Fila: inicio e para retaguarda
(final) da Fila: fim. Elementos são acrescentados utilizando-se o índice fim, e são retirados utilizando-se o índice
inicio, e quando i = f = 0, isto significa que a fila está vazia.
A seguir é apresentada uma representação gráfica de possíveis operações em uma fila estática:
87
fila vazia:
n
3
2
1
inicio 
insere informação A
 fim
n
inicio 
insere informação B
3
2
1
 fim
B
A
 fim
C
B
A
 fim
C
B
 fim
C
 fim
n
3
2
inicio  1
insere informação C
n
3
retira informação A
A
inicio 
2
1
n
3
inicio  2
1
retira informação B
n
inicio  3
2
1
retira informação C
n
3
2
1
fila vazia
inicio 
 fim
A seguir é apresentado um programa exemplo para a inserção, remoção e visualização de elementos em
uma fila F de valores inteiros.
#include <iostream>
#define dim 10
using namespace std;
void
void
void
menu
( );
pausa
( );
mensagem ( );
88
void
void
void
inserir
retirar
mostrar
( );
( );
( );
int
fila[dim], inicio = 1, fim = 1, aux , i;
char d;
int
{
main ( )
menu ( );
}
void
{
{
menu ( )
do
mensagem ( );
do
{
cout << "\n\n\n\n\t\t\t
ESCOLHA SUA OPCAO: \n\n";
cout << "\t\t\t[ I ] nserir Nodos na Fila\n";
cout << "\t\t\t[ R ] etirar Nodos da Fila \n";
cout << "\t\t\t[ M ] ostrar a Fila \n";
cout << "\t\t\t[ T ] erminar o Programa\n\n";
cout << "\t\t\t
DIGITE SUA OPCAO: ";
cin >> d;
d = toupper(d);
}
while (d != 'I' && d != 'R' && d != 'M' && d != 'T');
switch (d)
{
case 'I': inserir ();
break;
case 'R': retirar ();
break;
case 'M': mostrar ();
break;
}
}
}
while (d != 'T');
void pausa ( )
{
cout <<"\n\n\n\n\n\t\t ";
cout << "Digite Uma Letra e <Enter> Para Continuar ";
cin >> d;
}
void mensagem ( )
{
system ("cls");
89
}
cout << "\n\n\n\n\t\t\tMANIPULACAO DE FILAS ESTATICAS";
void inserir ( )
{
d = 'S';
// Verifica se Usuario Deseja Inserir Elemento na Fila
while (d == 'S')
{
aux = 0 ;
if ( fim != (dim+1) )
aux = ( fim % (dim 1 ) ) + 1;
if (aux != inicio)
{
// Há Lugar na Fila --> Insere Elemento
mensagem ( );
cout << "\n\n\n\t\t\t\t INSERE NOS\n\n";
// Recebe e Armazena Dado na Fila
fim = aux;
cout << "\n\n\t\t\t Digite Valor a Armazenar: ";
cin >> fila[fim];
// Acerta Indices de Controle da Fila
if (inicio == 1) inicio = 0;
if (inicio != 1)
}
else
{
}
}
void
{
}
// Pergunta se Usuario Deseja Inserir Mais Elementos na Fila
do
{
cout << "\n\n\n\n\n\n\t\tDeseja Inserir Outro Nodo na Fila: [S]im ou [N]ao ? " ;
cin >> d;
d = toupper(d);
}
while (d!='S' && d!='N');
cout << "\n\n\t\t\tA FILA ESTA CHEIA !!!";
d = 'N';
// Força o Fim do Loop
pausa ( );
retirar ( )
d = 'S';
mensagem ( );
while (d == 'S')
{
if (inicio != 1)
{
// A Fila Nao Esta Vazia
system ("cls");
cout << "\n\n\n\n\n\t\t\t
RETIRA NODOS DA FILA\n\n";
90
// Retira Nodo da Fila
cout << "\n\t\t Nodo Com Valor = " << fila[inicio] << " Foi Retirado da Fila\n\n ";
// Verifica Se a Fila Ficou Vazia
if (inicio == fim)
{
// A Fila Ficou Vazia ==> Acerta Indices de Controle
inicio = 1;
fim
= 1;
}
else
{
// A Fila Nao Ficou Vazia ==> Acerta Indices de Controle
if ( inicio != ( dim  1) )
inicio = (inicio % (dim  1)) + 1;
else
inicio = 0;
}
}
}
void
{
}
// Verifica se Pode e se Deseja Retirar Outro Elemento da Fila
if (inicio != 1)
do
{
cout <<"\n\n\n\n\n\n\t\tDeseja Retirar Outro No da Fila: "[S]im ou [N]ao ? ";
cin >> d;
d = toupper (d);
}
while (d != 'S' && d != 'N');
if (inicio == 1)
{
// A Fila Esta Vazia ==> Forca Saída da Funcao
cout << "\n\n\t\t\t
A FILA ESTA VAZIA !!!";
pausa ( );
d = 'N';
// Força Saida do Loop While
}
mostrar ( )
mensagem ( );
cout <<"\n\n\t\t\t MOSTRA OS ELEMENTOS NA FILA\n\n";
i = 0;
aux = inicio;
if (aux != 1)
while (aux != 1)
{
// Mostra Nó da Fila
cout << "\n\t\t\tNodo " << ++i " na Fila Com Valor = " << fila[aux];
91
// Verifica Se Mostrou o Ultimo Elemento na Fila
if (aux == fim)
{
aux = 1;
// A Fila Ficou Vazia
d = 'N';
// Força Saida do Loop While
}
else
aux = (aux%dim)+1;
}
}
else cout << "\n\t\t\t
pausa ( );
A FILA ESTA VAZIA !!!";
REFERÊNCIAIS BIBLIOGRÁFICAS
1. ZWARCFITER J.M. & MARKENZON L.. Estruturas de Dados e seus Algoritmos. Ed. LTC,
Rio de Janeiro, 1994.
2. TENENBAUM A.M. & AUGENSTEIN M.J.. Estruturas de Dados Usando C. Ed. Makron Books,
São Paulo, 1995.
3. TENENBAUM A.M. & AUGENSTEIN M.J.. Data Structures Using Pascal. Ed. Prentice-Hall International,
Inc.. Englewood Cliffs, New Jersey, 1986.
92
4. AZEREDO P.A.. Métodos de Classificação de Dados. Ed. Campus. Rio de Janeiro, 1996.
5. SWAN T.. Programando em Pascal 7.0 para Windows. Ed. Berkeley Brasil, Rio de Janeiro, 1993.
6. O'BRIEN S.. TURBO PASCAL 6 - Completo e Total. Makron Books do Brasil, São Paulo 1992.
7. MANZANO J. A. N. G. & YAMATUMI W.Y.. TURBO PASCAL - Estudo Dirigido. Érica, são Paulo 1997.
8. MECLER I. & MAIA L. P.. Programação e Lógica com Turbo Pascal. Campus, Rio de Janeiro, 1989.
9. GUIMARÃES A.M. & LAGES N.A.C.. Algoritmos e Estruturas de Dados. Ed. LTC. Rio de Janeiro, 1985.
93
EXERCÍCIOS ADICIONAIS
94
Cadeias de Caracteres - Strings
1) Escreva um programa que receba, através do teclado, 5 (cinco) cadeias de até 20 caracteres e as armazene
em um array unidimensional – vetor – de dimensão 5 (cinco). Após o programa deverá pesquisar os
caracteres de cada elemento do vetor e, onde encontrar uma consoante b substituí-la pelo caracter 0
(zero), e onde encontrar um caractere consoante diferente de b substituí-la pelo caractere 1 (um).
As substituições devem ocorrer na própria cadeia, na posição original onde as respectivas consoantes
porventura forem encontradas. Neste estágio do algoritmo as vogais não devem ser manipuladas.
Após, o programa deverá pesquisar novamente o vetor e, para cada elemento do vetor:
a) Visualizar a quantidade de vogais a , e , i , o e u que forem encontradas ;
b) Visualizar a quantidade de conjunto de vogais ae , ai, ao e au que forem encontradas ;
c) Apagar todas as ocorrências consecutivas da cadeia ua ;
d) Substituir todas ocorrências de duas vogais consecutivas pela cadeia xx ;
e) Indicar todas as posições relativas das possíveis ocorrências da cadeia ea ; e
f) Inserir seu nome, em formato minúsculo, a partir da quarta posição de cada cadeia ;
g) Visualizar, em formato maiúsculo, todas as vogais presentes nas cadeias do vetor ;
h) Sempre que possível, concatenar seu primeiro sobrenome em cada cadeia do vetor ; e
i ) Visualizar a quantidade de caracter em cada cadeia do vetor.
2) Escreva um programa que receba 1 (um) valor inteiro, 1 (um) caracter alfabético – forçosamente em formato
minúsculo – e 3 (três) cadeias de 10 (dez) caracteres – também forçosamente em formato minúsculo –
através do teclado e, após:
a) Transforme o valor inteiro digitado em uma cadeia e o visualize ;
b) Visualize o caracter alfabético em sua forma maiúscula ;
c) Concatene as 2 primeiras cadeias em uma única cadeia de 20 caracteres, e a visualize ;
d) Visualize a cadeia resultante do processado no item 3 (três) em formato maiúsculo ;
a
e) Execute a geração de uma 4 cadeia que deve ser resultante da extração de 5 caracteres da cadeia
o
gerada no item 4, a partir de seu 12 (décimo segundo) caracter ;
o
f) Extraia 4 (quatro) caracteres da cadeia gerada no item 5 (cinco), a partir de seu 8 (oitavo), e a visualize
após a extração ;
a
a
g) Execute a inserção da 3 (terceira) cadeia digitada, na 2 (segunda) cadeia digitada, a partir de seu 5
(quinto) caracter;
95
o
h) Visualize a quantidade atual de caracteres das cadeias geradas até o momento ; e
i) Informe, se for o caso, a posição do primeiro caracter da subcadeia aba na cadeia 1.
5
Registros - Structures
3) Escreva um programa que preencha, a partir do teclado, duas estruturas distintas do tipo vetor com os
nomes e as notas (as notas têm de estar contidas no intervalo 0  nota  10) dos alunos, respectivamente,
de uma turma de 100 alunos.
Após, exteriorize somente os nomes dos alunos que obtiveram notas iguais ou maiores que 5 (cinco).
4) Escreva um programa que preencha, a partir do teclado, duas estruturas distintas do tipo vetor com as
idades de 100 pessoas.
A primeira estrutura do tipo vetor deverá receber somente as idades das pessoas do sexo masculino,
enquanto a segunda deverá armazenar as idades das pessoas do sexo feminino.
Após, o programa deverá exteriorizar os nomes, o sexo e as idades das pessoas que possuem idade
compreendida entre 20 (vinte) e 40 (quarenta) anos, inclusive.
5) Escreva um algoritmo que preencha 3 (três) estruturas do tipo registro com os nomes e as idades de 3
(três) pessoas – cada conjunto de informações sobre uma pessoa deverá ser conteúdo de um registro – e,
após, visualize o nome da(s) pessoa(s) de mais idade.
6) Escreva um algoritmo que preencha uma estrutura do tipo vetor de registros, de dimensão igual a 100
(cem), onde cada registro deve conter o nome e a idade de uma pessoa, informados através do teclado e
que, após, visualize o nome da pessoa de menor idade e o nome da pessoa de mais idade.
7) Escreva um algoritmo que preencha uma estrutura do tipo vetor de registros, onde cada elemento deverá
armazenar o nome, a idade e os 5 graus (notas) obtidos em 5 (cinco) verificações de aprendizagem, de uma
turma de 90 (noventa) alunos.
Após o programa deverá visualizar os nomes de todos os alunos da turma acompanhados de sua situação
acadêmica – aprovado ou reprovado.
A situação de aprovado somente pode ser computada se o aluno obtiver todos os seus graus maiores ou
iguais a 5 (cinco). Caso contrário, ele deverá ser assinalado como reprovado.
8) Escreva um algoritmo que preencha uma estrutura do tipo vetor de registros, de dimensão100 (cem), onde
cada registro deve armazenar o nome e a idade de uma pessoa e que, após, os nomes dos alunos de menor
e maior idades, respectivamente.
9) Escreva um algoritmo que preencha duas estruturas homogêneas de dados, a saber:
a) Um vetor de registros, onde cada elemento deve armazenar código e nome de uma disciplina ; e
b) Uma certa matriz de registros, onde cada linha representa uma disciplina, dentre aquelas explicitadas no
vetor, e onde deverão ser armazenadas (em cada elemento da linha) a matrícula, o nome e os 3 (três)
graus (notas) obtidos em suas verificações de aprendizagem.
A turma possui 10 (dez) alunos que cursam, cada um, obrigatoriamente, 5 (cinco) disciplinas.
Após, o algoritmo deverá visualizar os nomes de todos os alunos da turma, acompanhados de sua situação
acadêmica – aprovado ou reprovado – e, se o aluno estiver reprovado, qual(is) a(s) disciplina(s) que o
colocaram em tal situação.
A situação de aprovado somente pode ser computada se o aluno obtiver todos os seus graus maiores ou
iguais a 5 (cinco). Caso contrário, ele deverá ser assinalado como reprovado.
96
10) Escreva um programa que preencha, com dados fornecidos através do teclado:
a)
Dois vetores de dimensão 50 com valores inteiros na faixa de 1 a 50, que servirão como índices para
as linhas e colunas, respectivamente, de uma certa matriz; e
b)
Uma matriz quadrada supramencionada, de ordem 50, com valores reais maiores que Zero;
No entanto, o programa só deverá preencher as posições da matriz (linha x coluna) que tiverem como
o
o
índices os conteúdos do 1 vetor (índices para as linhas) e do 2 vetor (índices para as colunas). Todas as
outras posições da matriz deverão estar preenchidas com Zeros
Abaixo é apresentada uma representação gráfica do quanto solicitado:
vet_col 1
2
1
vet_lin
1 2
2 4
3 5
4 37
5 45
6 50
7 0
48
49
50
0
0
0
3
3
4
22
4
5
40
6
46
7
0
49
0
50
0
1
2
3
4
22
40
46
50
5
0
x
0
0
0
0
0
0
0
0
0
0
0
x
0
0
0
0
0
x
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
37
0
0
0
0
x
0
0
0
45
0
0
0
0
0
x
0
0
50
0
0
0
0
0
0
x
0
1
2
3
4
11) Escreva um algoritmo que execute o empilhamento de valores inteiros em uma fila estática, de dimensão
estabelecida por parâmetro, e, após, retire, um por um, os valores da pilha e coloque cada valor par e
múltiplo de sete em uma estrutura do tipo fila estática. Finalmente, após a geração da fila, o algoritmo
deverá ser capaz de visualizar todo o seu conteúdo.
12) Escreva um algoritmo em português estruturado que execute o enfileiramento de valores inteiros em uma
fila estática, de dimensão estabelecida por parâmetro, e, APÓS, retire todos os valores pares da fila e deixe
armazenados somente os valores ímpares, na ordem em que foram originalmente inseridos na fila.
97
13) Imagine que exista um programa que executa a geração de uma Lista Simplesmente Encadeada, com
elementos (nós), cuja configuração é apresentada a seguir:
Formato dos Nós da Lista
Número
(Int)
Cadeia
Char [21]
Ponteiro Para o Próximo
Nó ou Aterramento
Imagine, também, que o programa permite escolher todas as facilidades de manipulação da Lista através
de menu.
Observações Gerais:
a) A Lista é denominada "Lista" e Não possui Nó Cabeça;
b)
Os Elementos na Lista (Nós) não estão ordenados;
c)
Não são aceitos Nós com mesma chave;
d)
Cada elemento na Lista é composto por três campos, a saber:
d.1) Um campo num‚rico denominado chave, que servir como sua chave identificadora, e que,
obrigatoriamente, deve ser um número inteiro maior que zero;
d.2) Um campo alfanumérico onde poder ser armazenada qualquer cadeia de dados, cujo tamanho ‚
definido por constante;
d.3) Um campo tipo ponteiro cujo conteúdo‚ o endereço do próximo Nó ou Aterramento () se for o
último Nó; e
e)
Todas as variáveis são Globais.
Para padronizar as soluções são elencadas abaixo as declarações dos tipos e variáveis necessárias.
Tipo tp_pt_no =
struct no
{
int
char
struct no
};
^no ;
chave;
cadeia [ 21 ] ;
*pt_prox ;
typedef struct no *tp_pt_no
tp_pt_no pt_ant, pt_aux, pt_pont, pt_corr, pt_lista : tp_pt_no;
Escreva procedimentos independentes que executem:
i)
A visualização de todos os elementos da Lista;
ii)
O esvaziamento da Lista; e
iii)
A retirada de todos os elementos da Lista cuja chave seja ímpar, deixando na Lista, e no mesmo
endereço físico da memória, os elementos de chave par.
98
14) Imagine que exista um programa que executa a geração de uma Lista Simplesmente Encadeada, com
elementos (nós), cuja configuração é apresentada a seguir:
Formato dos Nós da Lista e da Pilha
Número
(Int)
Cadeia
(Char [ 21])
Ponteiro Para o Próximo
Nó ou Aterramento
Imagine, também, que o programa permite escolher todas as facilidades de manipulação da Lista através
de menu.
Observações Gerais:
a) A Lista é denominada "Lista" e a Pilha deverá ser denominada "Pilha";
b) A Lista não possui Nó Cabeça;
c) Os Elementos na Lista (nós) não estão ordenados;
d) Não são aceitos Nós com mesma chave;
e) Cada elemento na Lista e na Pilha é composto por 3 campos, a saber:
e.1) Um campo numérico denominado chave, que servirá como sua chave identificadora, e que,
obrigatoriamente, deverá ser um número inteiro maior que zero;
e.2) Um campo alfanumérico onde poderá ser armazenada qualquer cadeia de dados, cujo tamanho é
definido por constante; e
e.3) Um campo tipo ponteiro cujo conteúdo é o endereço do próximo Nó, ou Aterramento () se for o
último Nó; e
f) Todas as variáveis são ser Globais.
Para padronizar as soluções são elencadas abaixo as declarações dos tipos e variáveis necessárias.
Struct no
{
int
chave;
char
cadeia;
struct no *tpt_prox;
}
typedef
struct
no
tp_pt_no pt_topo, pt_ant,
*tp_pt_no
pt_aux, pt_pont, pt_corr, pt_lista;
Escreva procedimentos independentes que executem:
i) A visualização de todos os elementos da Lista;
ii) A visualização de todos os elementos da Pilha;
iii) O esvaziamento da Lista;
iv) O esvaziamento da Pilha; e
v) A geração de uma Pilha Dinâmica com todos os elementos (nós) da Lista que contiverem "chave" par,
armazenados nela na mesma ordem em que estiverem armazenados na Lista.
99
15) Imagine que exista um programa que executa a geração de uma Lista Simplesmente Encadeada, com
elementos (nós), cuja configuração é apresentada a seguir:
Formato dos Nós da Lista e da Fila
Número
(Int)
Cadeia
(Char)
Ponteiro Para o Próximo
Nó ou Aterramento
Imagine, também, que o programa permite escolher todas as facilidades de manipulação da Lista através
de menu.
Observações Gerais:
a) A Lista é denominada "Lista", não possui Nó Cabeça e a Fila é denominada "Fila";
b) Os Elementos na Lista (nós) não estão ordenados;
c) Não são aceitos Nós com mesma chave;
d) Cada elemento na Lista e na Fila é composto por 3 campos, a saber:
d.1) Um campo numérico denominado chave, que servirá como sua chave identificadora, e que,
obrigatoriamente, deverá ser um número inteiro maior que zero;
d.2) Um campo alfanumérico onde poderá ser armazenada qualquer cadeia de dados, cujo tamanho é
definido por constante; e
d.3) Um campo tipo ponteiro cujo conteúdo é o endereço do próximo Nó, ou Aterramento () se for o
último Nó; e
e) Todas as variáveis são ser Globais.
Para padronizar as soluções são elencadas abaixo as declarações dos tipos e variáveis necessárias.
Struct no
{
int
chave;
char
cadeia;
struct no *tpt_prox;
}
typedef
struct
no
tp_pt_no pt_topo, pt_ant,
*tp_pt_no
pt_aux, pt_pont, pt_corr, pt_lista;
Escreva procedimentos independentes que executem:
i) A visualização de todos os elementos da Lista;
ii) A visualização de todos os elementos da Fila;
iii) O esvaziamento da Lista;
iv) O esvaziamento da Fila; e
v) A geração de uma Fila Dinâmica com todos os elementos (nós) da Lista que contiverem "chave" par,
armazenados nela na mesma ordem em que estiverem armazenados na Lista.
100
16) A seguir você vai encontrar um programa escrito em Português Estruturado que executa a inserção de
elementos (nós) em uma Lista Simplesmente Encadeada com Nó Descritor.
Estudando-o você perceberá que existem duas declarações de procedimentos que estão vazios (sem
código).
Escreva os algoritmos necessários para que os dois procedimentos possam funcionar corretamente.
Considere ainda que: o primeiro algoritmo deverá processar a visualização de todo o conteúdo da Lista; e o
segundo deverá ser capaz de retirar elementos da lista, sendo que a chave de busca (identificador do
elemento a ser retirado) é o campo do nó denominado ”Valor”.
Mais ainda: O procedimento para a retirada não deverá se valer de qualquer função explícita (a parte) de
busca.
Observações Gerais:
a) A Lista ser denominada "Lista" e Não possui Nó Cabeça;
b) Os Elementos (Nós) da Lista Não Estão Ordenados;
c) Cada elemento na Lista é composto por três campos, a saber:
c.1) Um campo numérico denominado Valor, que servirá como sua Chave Identificadora, e que,
obrigatoriamente, deverá ser um número inteiro maior que zero; e
c.2) Um campo alfanumérico onde poderá ser armazenada qualquer cadeia de dados, cujo tamanho‚
é definido por constante;
d) O Nó Descritor contém três campos, a saber: um campo do tipo ponteiro que aponta, sempre, para
o primeiro elemento (nó) da Lista, um campo tipo inteiro que contém, sempre, a quantidade atual de
elementos (nós) na Lista, e um segundo campo tipo ponteiro que aponta, sempre, para o último
elemento (nó) da Lista;
e) No caso de retirada de elementos da Lista, em havendo elementos de mesma chave, o elemento a ser
retirado será o primeiro a ser encontrado ; e
f)
Todas as variáveis são Globais.
Formato do Nó Descritor
Ponteiro Para
o Primeiro Nó
Quantidade Atual
de Nós na Lista
Ponteiro Para
Último Nó
Formato dos Nós da Lista
Valor
(Int)
Nome
(Char)
Ponteiro Para Próximo
ou Aterramento
Representação Gráfica da Lista
pt_lista
Nó Descritor
Nó1
Nó2
Nó3
101
Nó n
102