Algoritmos e Estruturas de Dados - Fundação Visconde de Caitu

Prévia do material em texto

FUNDAÇÃO VISCONDE DE CAIRU
CENTRO DE PÓS−GRADUAÇÃO E PESQUISA VISCONDE DE CAIRU
Curso de Pós−graduação em Análise de Sistemas
ALGORITMOS
E
ESTRUTURAS DE DADOS
Roberto Luiz Souza Monteiro
Salvador
2002
FUNDAÇÃO VISCONDE DE CAIRU
CENTRO DE PÓS−GRADUAÇÃO E PESQUISA VISCONDE DE CAIRU
Curso de Pós−graduação em Análise de Sistemas
AGORITMOS
E
ESTRUTURAS DE DADOS
Roberto Luiz Souza Monteiro
Texto utilizado como material didático para a
disciplina Algoritmos e Estruturas de Dados do
curso de Pós−graduação em Análise de Sistemas
do Centro de Pós−graduação e Pesquisa
Visconde de Cairu.
Salvador
2002
a meus pais que sempre apoiaram e patrocinaram
meus estudos
as palavras, para exercerem influência, devem
estar carregadas de substância − apoiadas no
comportamento como a chama no
combustível.
I’CHING − O Livro das Mutações
AGRADECIMENTOS
Agradeço especialmente ao Cósmico por ter me proporcionado esta experiência singular.
SUMÁRIO
1. INTRODUÇÃO, 1
1.1. Dados, 1
1.2. Informação, 1
1.3. Algoritmos, 1
1.4. Representação gráfica, 2
1.4.1. Fluxogramas, 3
1.5. Sistemas numéricos, 5
1.6. Conversão entre bases, 6
1.7. Complemento de 1 e de 2, 10
1.8. Números sinalizados, 11
1.9. Números reais, 11
1.10. Números com ponto flutuante, 12
1.11. Código BCD, 14
1.12. ASCII, 15
2. ARITMÉTICA BINÁRIA, 16
2.1. Adição, 16
2.2. Subtração, 16
2.3. Adição e subtração utilizando complemento de 2, 16
2.4. Multiplicação, 17
2.5. Divisão, 18
3. INTRODUÇÃO À LÓGICA, 19
3.1. Operação E ( AND ), 19
3.2. Operação OU ( OR ), 20
3.3. Operação OU EXCLUSIVO( XOR ), 20
3.4. Operação NÃO ( NOT ), 20
3.5. Diferença entre operação lógica e operação binária, 21
4. VARIÁVEIS, 22
4.1. Definição, 22
4.2. Nomes de variáveis, 22
4.3. Tipos de variáveis, 23
4.4. Atribuição do conteúdo de uma variável, 23
4.5. Tipos de dados, 24
4.6. Constantes, 26
5. OPERADORES, 27
5.1. Operadores matemáticos, 27
5.2. Operadores lógicos, 29
5.3. Precedência dos operadores, 29
6. COMANDOS DE ENTRADA E SAÍDA, 30
6.1. Saída padrão ( stdout ), 31
6.2. Entrada padrão ( stdin ), 31
7. ESTRUTURAS DE CONTROLE, 32
7.1. Estrutura SE... ENTÃO... SENÃO... ( IF... THEN... ELSE... ), 32
7.2. Estrutura CASO... ( CASE... ), 34
8. LAÇOS DE REPETIÇÃO, 36
8.1. Estrutura ENQUANTO... FAÇA... ( WHILE... DO... ), 36
8.2. Estrutura FAÇA... ENQUANTO... ( DO... WHILE... ), 38
8.3. Estrutura PARA... FAÇA... ( FOR... TO... DO... ), 39
9. ESTRUTURAS HOMOGÊNEAS, 41
9.1. Vetores uni−dimensionais, 41
9.1.1. Operações com vetores uni−dimensionais, 44
9.1.1.1. Atribuição de um vetor, 44
9.1.1.2. Leitura de dados de um vetor, 44
9.1.1.3. Escrita de dados em um vetor, 44
9.2. Matrizes ou vetores de mais de uma dimensão, 45
9.2.1. Operações com vetores de mais de uma dimensão, 45
9.2.1.1. Atribuição de uma matriz, 45
9.2.1.2. Leitura de dados de uma matriz, 45
9.2.1.3. Escrita de dados em uma matriz, 45
10. ESTRUTURAS HETEROGÊNEAS, 46
10.1. Registros, 46
10.2. Operações com registros, 47
10.2.1. Atribuição de um registro, 47
10.2.2. Leitura de um registro, 48
10.2.3. Escrita em um registro, 49
10.3. Conjuntos de registros, 49
10.4. Operações com conjuntos de registros, 49
10.4.1. Atribuição de um conjunto de registros, 50
10.4.2. Leitura de um registro de um conjunto, 51
10.4.3. Escrita em um registro de um conjunto, 52
11. PROGRAMAÇÃO ESTRUTURADA OU MODULAR, 56
11.1. Sub−rotimas, 56
11.1.1. Procedimentos, 56
11.1.2. Funções, 59
11.2. Parâmetros formais e reais, 61
11.3. Passagem de parâmetros, 61
11.3.1. Passagem de parâmetros por valor, 61
11.3.2. Passagem de parâmetros por referência, 61
11.4. Variáveis locais e globais, 62
11.4.1. Escopo de variáveis, 62
12. ALGORITMOS DE ORDENAÇÃO, 63
12.1. Ordenação por inserção, 63
12.2. Ordenação por troca, 65
12.2.1. Método da bolha ( bubble sort ), 65
12.2.1. Método de divisão e troca ( quick sort ), 67
12.3. Ordenação por seleção, 70
13. ALGORITMOS DE PESQUISA, 72
13.1. Algoritmos de busca em tabela, 72
13.2. Algoritmo de pesquisa binaria, 74
14. ÁRVORES, 77
14.1. Arvores binarias, 78
14.2. Arvores de busca binária, 79
14.3. Representando um nó em uma árvore binária, 79
14.4. Inserindo um elemento em uma árvore binária, 80
14.5. Pesquisando um elemento em uma árvore binária, 82
14.6. Movendo−se em uma árvore binária, 84
14.7. Removendo um elemento em uma árvore binária, 86
15. PILHAS ( STACKS ), 88
15.1. Operações com pilhas, 89
16. FILAS ( QUEUES ), 90
16.1 Operações com filas, 91
REFERENCIAS BIBLIOGRÁFICAS, 92
RESUMO
Este documento apresenta os principais conceitos e métodos envolvendo algoritmos e
estruturas de dados, dando especial ênfase ao desenvolvimento de aplicações nas linguagens
C e Tcl.
1
1. INTRODUÇÃO
Neste capítulo serão analisados os aspectos mais elementares necessários para que se possa
realizar um estudo eficaz dos algoritmos e técnicas de programação de computadores.
1.1. Dados
Dados são elementos conhecidos de um problema.
Exemplo:
Dados x=2, y=3, obter z, para, x2 + y3 + z = 5.
x e y são dados do problema.
1.2. Informação
Um conjunto estruturado de dados, que transmitem conhecimento.
Exemplo:
A primeira lei da física nos diz: todo corpo em repouso ou em movimento retilíneo e
uniforme permanece assim até que uma força externa ao sistema atui sobre ele modificando
este estado.
1.3. Algoritimos
Algoritmos são regras para resolução de problemas ou obtenção de resultados que podem, ou
não, envolver fórmulas matemáticas.
Algoritmos são utilizados como roteiros ou esquemas, para resolução de problemas
computacionais, tal como se utiliza uma receita para produzir um bolo.
2
Estrutura de um algoritmo:
ALGORITMO <Nome do Algoritmo>
 <Definições>
INÍCIO
 <Comandos>
FIM
Exemplo:
Calcular a soma de dois números:
ALGORITMO Soma_de_dois_numeros
VARIÁVEIS
 A : INTEIRO
 B : INTEIRO
 Z : INTEIRO
INÍCIO
 LEIA A
 LEIA B
 Z ← A + B
 ESCREVA Z
FIM
1.4. Representação gráfica
A forma mais comum de apresentação de algoritmos é a representação gráfica. Esta forma de
representação tem a vantagem de permitir uma visualização global da resolução de um
problema. Veja o exemplo a seguir, do algoritmo da soma de dois números:
3
Figura 1.4.1: Representação gráfica de um algoritmo
1.4.1. Fluxogramas
O diagrama de fluxo, ou fluxograma é a forma mais eficaz para representação de algoritmos
pois permite uma visualização global de um problema e sua solução. O fluxograma apresenta
visualmente, cada etapa de execução do algoritmo, ou seu fluxo de execução, de uma forma
muito mais intuitiva que a forma textual. Contudo, aplica−se apenas à fase prelimimar para
elaboração de um programa de computador, sendo utilizado somente no momento da
definição dos passos que serão dados para o desenvolvimento de uma aplicação: a partir dele,
constroi−se então um algoritmo textual, mais detalhado que será mais tarde convertido em um
programa de computador, escrito em uma linguagem específica.
A seguir são apresentados os principais símbolos utilizados na construção de fluxogramas:
4
Figura 1.4.1.1: Simbologias utilizados em fluxogramas
5
1.5. Sistemas numéricos
Os computadores armazenam dados que quando processados podem dar origem a
informações. Estes dados são normalmente representados por números e textos. A forma
interna de armazenamento de dados dos computadores é o bit, a menor proção de um dados
compreensível por um computador. Os bits podem assumir valores 0 ou 1, e podem ser
agrupados para formar unidades maiores, conjuntos de 8 bits, chamadas de bytes. Um byteé
portanto um conjunto de 8 bits, que pode ser avaliado como se fosse uma única unidade. Este
sistema numérico, constituído por bits, cujos valores variam apenas entre 0 e 1, é chamado de
sistema binário.
Um conjunto de 1024 bytes constituem 1 Kbyte ou 1 kilobyte e 1024 Kbytes constituem 1
Mbyte ou 1 begabyte.
Os computadores entendem apenas bits, e qualquer dado será convertido para bits antes que
seja processado pela máquina. Por outro, lado os seres humanos encontram grande
dificuldade para ler e avaliar dados em sistema binário, assim antes que o resultado de um
processamento seja apresentado por um computador, ele é normalmente convertido para um
sistema numérico mais facilmente assimilável pelos humanos. Os sistemas numéricos mais
comuns são o sistema decimal, constituído por dígitos entre 0 e 9, o sistema octal,
constituído pelos dígitos de 0 a 7 e o sistema hexadecimal, constituído pelos dígitos de 0 a 9
e as letras A, B, C, D, E e F.
6
Sistema Base Símbolos
Binário 2 0, 1
Octal 8 0, 1, 2, 3, 4, 5, 6, 7
Decimal 10 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
Hexadecimal 16 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A,
B, C, D, E, F
Tabela 1.5.1: Sistemas binário, octal, decimal e hexadecimal
Em qualquer sistema numérico, o dígito mais à direita é chamado de dígito menos
significativo( least significant digit ).
1.6. Conversão entre bases
A conversão de um número em qualquer base para a base decimal é feita multiplicando−se
cada dígito pelo seu peso e somando−se os resultados.
Exemplos:
Converter o número binário 1110 para decimal:
Dígito Peso( base posição ) Produto( Dígito x Peso )
1 23 1 x 8 = 8
1 22 1 x 4 = 4
1 21 1 x 2 = 2
0 20 0 x 1 = 0
Soma 0 + 2 + 4 + 8 = 14
Tabela 1.6.1: Conversão de um número binário para decimal
7
Converter o número octal 755 para decimal:
Dígito Peso( base posição ) Produto( Dígito x Peso )
7 82 7 x 64 = 448
5 81 5 x 8 = 40
5 80 5 x 1 = 5
Soma 5 + 40 + 64 = 493
Tabela 1.6.2: Conversão de um número octal para decimal
Converter o número hexadecimal 8000 para decimal:
Dígito Peso( base posição ) Produto( Dígito x Peso )
8 163 8 x 4096 = 32768
0 162 0 x 256 = 0
0 161 0 x 16 = 0
0 160 0 x 1 = 0
Soma 0 + 0 + 0 + 32768 = 32768
Tabela 1.6.3: Conversão de um número hexadecimal para decimal
Para converter um número decimal para qualquer base, divide−se o número pela valor da base
até que se obtenha como resultado da divisão o valor zero. O resultado da conversão será a
aglutinação dos restos de cada divisão, na ordem inversa à obtida.
8
Exemplos:
Converter o número 128 em binário:
128 / 2 = 64, resto 0
64 / 2 = 32, resto 0
32 / 2 = 16, resto 0
16 / 2 = 8, resto 0
8 / 2 = 4, resto 0
4 / 2 = 2, resto 0
2 / 2 = 1, resto 0
1 / 2 = 0, resto 1
Aglutinando−se os valores dos resto das divisões, em ordem inversa: 10000000
Converter o número 128 em octal:
128 / 8 = 16, resto 0
16 / 8 = 2, resto 0
2 / 8 = 0, resto 2
Aglutinando−se os valores dos resto das divisões, em ordem inversa: 200
Converter o número 128 em hexadecimal:
128 / 16 = 8, resto 0
8 / 16 = 0, resto 8
Aglutinando−se os valores dos resto das divisões, em ordem inversa: 80
9
Para converter um número octal ou hexadecimal em binário utilizam−se as tabelas a seguir:
Dígito Octal Dígito Binário
0 000
1 001
2 010
3 011
4 100
5 101
6 110
7 111
Tabela 1.6.4: Conversão de um número octal para binário
Dígito Hexadecimal Dígito Binário
0 0000
1 0001
2 0010
3 0011
4 0100
5 0101
6 0110
7 0111
8 1000
9 1001
A 1010
B 1011
C 1100
D 1101
E 1110
F 1111
Tabela 1.6.5: Conversão de um número hexadecimal para binário
10
Exemplos:
Converter o número hexadecimal 1F2 para binário:
1 = 0001
F = 1111
2 = 0010
Resultado: 0001 1111 0010
Converter o número octal 642 para binário:
6 = 110
4 = 100
2 = 010
Resultado: 110 100 010
1.7. Complemento de 1 e de 2
Obtém−se complemento de 1 de um número binário trocando−se cada dígito 1 do número
pelo dígito 0 e cada dígito 0 pelo dígito 1. Por exemplo o complemento de 1 do número 1010
é o número 0101.
Obtém−se o complemento de 2 de um número binário, calculando−se seu complemento de 1
e somando−se o bit 1 ao resultado.
Os complementos de 1 e de 2 são utilizados para simplificar a operação de subtração com
números binários.
As operações com número binários serão vistas no próximo capítulo.
11
1.8 Número sinalizados
Um número binário sinalizado é um número que pode assumir valores positivos, negativos ou
nulos. O bit mais à esquerda de um número binário sinalizado é o seu sign−magnitude, ou
bit de sinal. Quando o bit mais à esquerda de um número sinalizado for 0, o número será
positivo, quando o bit for 1, o número será negativo. Normalmente, o valor negativo de um
número é representado como o complmento de 2 de seu módulo.
Exemplo:
Obter o número −127 em binário:
127 em binário = 01111111
Complemento de 2 de 127 = 10000001
Um número binário de 8 bits sinalizado pode assumir valores entre −128 e +127.
1.9. Números reais
Um número real é representado em binário, atribuindo−se um peso 2−1 ao bit à direita da
vírgula( ou ponto decimal ), um peso 2−2 ao próximo bit à direita e assim sucessivamente.
12
Exemplo:
Converter o número real binário 10010.101101 em decimal:
Dígito Peso( base posição ) Produto( Dígito x Peso )
1 2+4 1 x 16 = 16
0 2+3 0 x 8 = 0
0 2+2 0 x 4 = 0
1 2+1 1 x 2 = 2
0 20 0 x 1 = 0
1 2−1 1 x 0.5 = 0.5
0 2−2 0 x 0.25 = 0
1 2−3 1 x 0.125 = 0.125
1 2−4 1 x 0.0625 = 0.0625
0 2−5 0 x 0.03125 = 0
1 2−6 1 x 0.015625 = 0.015625
Soma 0.015625 + 0 + 0.0625 +
0.125 + 0 + 0.5 + 0 + 2 + 0 +
0 + 16 = 18.703125
Tabela 1.9.1: Conversão de um número real binário para decimal
1.10. Números com ponto flutuante
Normalmente, os números reais são representados em binário utilizando−se a notação de
ponto flutuante. Nesta notação os números são expressos utilizando um expoente, uma base e
uma fração chamada mantissa:
Numero em ponto flutuante = Mantissa x BaseExpoente
A virgula à esquerda é implícita e não é representada nesta notação.
13
Os números com ponto flutuante são armazenados em binário com três atributos: 1 bit de
sinal, 8 bits de mantissa e 3 bits de expoente.
Exemplo:
0 número 0 01001101 011 é o correspondente binário para o número real 2.40625, pois:
+ 0.01001101 x 2011 =
= 0.01001101 x 23 =
= 0010.01101 =
= + 2 + 0.25 + 0.125 + 0.03125 =
= + 2.40625
14
1.11. Código BCD
O Código Binário Decimal ou BCD é utilizado para compressão de dados númericos a fim
de poupar espaço na memória e registradores dos computadores e agilizar as transferências de
dados. Em BCD cada dígito é representado com 4 bits, de modo que um byte representa dois
dígitos de um número.
Dígito Decimal BCD
0 0000
1 0001
2 0010
3 0011
4 0100
5 0101
6 0110
7 0111
8 1000
9 1001
Tabela 1.11.1: Conversão de um número decimal para BCD
Exemplo:
Representar o número decimal 1024 em BCD:
Resposta: 0001 0000 0010 0100
15
1.12. ASCII
O Código Padrão Americano para Intercâmbio de Informações ou ASCII representa 128
caracteres em 7 bits. Este padrão é largamente utilizado para transferência e armazenamento
de dados.
LSB
MSB
000
0
001
1
010
2
011
3
100
4
101
5
110
6
111
7
0000
0
NUL DLE SPACE 0 @ P ‘ p
0001
1
SOH DC1 ! 1 A Q a q
0010
2
STX DC2 “ 2 B R b r
0011
3
ETX DC3 # 3 C S c s
0100
4
EOT DC4 $ 4 D T d t
0101
5
ENQ NAK % 5 E U e u
0110
6
ACK SYN & 6 F V f v
0111
7
BEL ETB ’ 7 G W g w
1000
8
BS CAN ( 8 H X h x
1001
9
HT EM ) 9 I Y i y
1010
A
LF SUB * : J Z j z
1011
B
VT ESC + ; K [ k {
1100
C
FF FS , < L \ l |1101
D
CR GS + = M ] m }
1110
E
SO RS . > N ^ n ~
1111
F
SI US / ? O _ o DEL
Tabela 1.12.1: Código ASCII em binário e hexadecimal
16
2. ARITMÉTICA BINÁRIA
Neste capítulo serão vistas as técnicas para realização das quatro operações matemática
fundamentais: adição, subtração, multiplicação e divisão.
2.1. Adição
A adição binária é muito simples: dois bits 0 dão como resultado um bit 0, um bit 0 e um bit 1
somados dão como resultado 1 e dois bits 1 somados resultam em um bit 0 e vai um. O bit vai
um é chamado de carry.
Exemplo:
Calcular 1011 + 0110:
 111 ( bits carry )
 1011
 +0110
 _____
 10001
2.2. Subtração
A subtração binária pode ser realizada de modo semelhante à subtração decimal, contudo, os
computadores utilizam uma técnica muito mais eficiente para realizar subtrações: o
complemento de 2.
2.3. Adição e subtração utilizando complemento de 2
Utilizando−se o complemento de dois pode−se somar e subtrair número binários utilizando
somente a técnica de soma de dois números binários. Basta que se converta o subtraendo para
o seu complemento de dois e some os dois números normalmente.
17
Exemplo:
Calcular 7 − 3 em binário :
 7 = 0111
 3 = 0011
−3 = 1101
 111 ( bits carry )
 0111
 +1101
 _____
 0100
0100 = 4
2.4. Multiplicação
Multiplicam−se dois número binários através da técnica de deslocamento e adição através do
seguinte algoritmo:
1. Toma−se o multiplicando e o multiplicador;
2. A partir o bit mais à direita, verifica−se o valor de cada bit do multiplicador;
3. Se o bit for 1, repete−se o multiplicando, deslocando−se os bits para a esquerda, a partir da
segunda interação;
4. Se o bit for 0, zera−se cada bit do multiplicando e procede−se do mesmo modo como se o
bit fosse 1;
Exemplo:
Calcular 13 X 10 em binário :
 13 = 1101 1101 multiplicando
 10 = 1010 X 1010 multiplicador
 __________
 0000 bit 0 do multiplicador = 0
 1101 bit 1 do multiplicador = 1
 0000 bit 2 do multiplicador = 0
 1101 bit 3 do multiplicador = 1
 __________
 10000010 = 130 em decimal.
18
2.5. Divisão
A divisão binária é realizada através do seguinte algoritmo:
1. Faz−se o quociente igual a zero;
2. Subtrai−se o divisor do dividendo e obtem−se um resto parcial;
Se o resto parcial >= 0, incrementa−se o quociente e continua−se;
Se o resto parcial < 0, para−se;
3. Torna−se o resto o dividendo e volta−se para a etapa 2.
Exemplo:
Calcular 100 / 50 em binário :
 100 = 01100100
 50 = 00110010
−50 = 11001110
Quociente = 00000000
 01100100
 +11001110
 _________
 00110010
Resto parcial = 00110010 > 0, incrementa Quociente.
Quociente = 00000001
 00110010
 +11001110
 _________
 00000000
Resto parcial = 00000000 = 0, incrementa Quociente.
Quociente = 00000010
 00000000
 +11001110
 _________
 11001110
Resto parcial = 11001110 < 0, para.
Quociente = 00000010 = 2 decimal.
19
3. INTRODUÇÃO À LÓGICA
Quase todo programa de computador realiza operações lógicas para tomar decisões sobre que
procedimento realizar diante de diferentes condições. Este capítulo introduz as quatro
operações da álgebra booleana suportadas por todas as linguagens de programação existentes:
E, OU, OU EXCLUSIVO e NÃO.
Toda operação lógica pode ter como resultado FALSO (FALSE) ou VERDADEIRO
(TRUE), sendo que para os computadores estes valores são normalmente representados por 1
ou 0. A tabela abaixo apresenta os valores VERDADEIRO e FALSO das várias formas
normalmente aceitas pela maioria das linguagens de computador:
VERDADEIRO true yes 1
FALSO false no 0
Tabela 3.1: Valores possíveis para VERDADEIRO e FALSO
3.1. Operação E ( AND )
A operação E retorna um resultado baseado na tabela verdade abaixo:
Operando 1 Operando 2 Operação AND
1 1 1
1 0 0
0 1 0
0 0 0
Tabela 3.1.1: Tabela verdade da operação AND
20
3.2. Operação OU ( OR )
A operação OU retorna um resultado baseado na tabela verdade abaixo:
Operando 1 Operando 2 Operação OR
1 1 1
1 0 1
0 1 1
0 0 0
Tabela 3.2.1: Tabela verdade da operação OR
3.3. Operação OU EXCLUSIVO ( XOR )
A operação OU EXCLUSIVO retorna um resultado baseado na tabela verdade abaixo:
Operando 1 Operando 2 Operação XOR
1 1 0
1 0 1
0 1 1
0 0 0
Tabela 3.3.1: Tabela verdade da operação XOR
3.4. Operação NÃO ( NOT )
A operação NÃO retorna um resultado baseado na tabela verdade abaixo:
Operando Operação NOT
1 0
0 1
Tabela 3.4.1: Tabela verdade da operação NOT
21
3.5 Diferença entre operação lógica e operação binária
A operação lógica considera o dado como um todo e retorna como resultado um valor lógico
VERDADEIRO ou FALSO, já a operação binária é realizada bit a bit e retorna como
resultado um novo dado não necessariamente verdadeiro ou falso.
Exemplos:
1. Qual o resultado das operações lógicas AND e OR realizada entre X e Y, sendo X = 1 e Y
= 0 ?
X AND Y = 1 AND 0 = 0 ( FALSO )
X OR Y = 1 OR 0 = 1 ( TRUE )
2. Qual o resultado das operações binárias AND e OR realizada entre X e Y, sendo X = 3 e Y
= 7 ?
X = 3 = 0011
Y = 7 = 0111
X AND Y:
0011
0111
____
0011
X AND Y = 0011 = 3
X OR Y:
0011
0111
____
0111
X OR Y = 0111 = 7
22
4. VARIÁVEIS
Os computadores possuem uma área de armazenamento de dados chamada memória. Esta
memória por sua vez dividi−se em memória primária, RAM, e memória secundária,
discos, CD−ROM etc. Na memória primária ficam os dados utilizados com frequência pelo
máquina, enquanto os demais dados são normalmente armazenados na memória secundária.
O computador acessa a memória através de endereços físicos numéricos, normalmente
expressos na base hexadecimal. O tamanho de cada dado na memória no entanto varia de
acordo com a natureza do dado e da própria máquina.
Como endereços hexadecimais são difíceis de trabalhar para os seres humanos é comum
associar a um endereço de memória e ao tipo de dado que ele contém, a um nome facilmente
recordável e imediatamente compreensível ao ser lido em um programa. Este é um endereço
lógico e se ele contem dados que podem ser alterados durante a execução do programa, ele é
chamado de VARIÁVEL, caso contrário será uma CONSTANTE ou um ponteiro para uma
instrução do próprio programa ou de outros programas existentes na memória do computador.
4.1. Definição
Variável é uma posição de memória, representada por um nome, que contém um dado que
pode ser acessado em um dado instante da execução de um programa.
4.2. Nomes de variáveis
Os nomes de variáveis podem ser constituídos de LETRAS, NÚMEROS e dos símbolos (_) e
(−), mas sempre começam com uma letra.. Algumas linguagens de programação, contudo,
suportam outros caracteres na formação de nomes de variáveis, como (.) por exemplo,
23
contudo, esta característica varia de linguagem para linguagem.
4.3. Tipos de variáveis
Variáveis podem ser de dois tipos: variáveis propriamente ditas e constantes. Variáveis
podem ter seus valores alterados a qualquer hora durante a execução do programa enquanto
constantes mantém o mesmo valor durante toda a execução do programa.
4.4. Atribuição do conteúdo de uma variável
O conteúdo de uma variável pode ser atribuído de várias maneira dependendo da linguagem
de programação que se esteja utilizando. Em algorítimos se utiliza o operador de atribuição
seta para a esquerda ( ← ). Para se ler o conteúdo de uma variável, em algoritmos,
simplesmente se faz referência ao nome da variável. Na linguagem C o operador de atribuição
é o caractere ( = ) enquanto em Tcl é utilizado o comando set. Em Tcl o conteúdo de uma
variável é referenciado colocando−se o caractere( $ ) à esquerda do nome da variável.
Exemplos:
Atribuir o valor 1 à varável X em Algoritmo, C e Tcl:
Algoritmo:
X ← 1
C:
X = 1;
Tcl:
set X 1
24
Antes que uma variável possa ser referenciada em um programa ela precisa ser declarada.
Novamente, a maneira de se declarar uma variável varia de linguagem de programação para
linguagem de programação. Em algoritmo, a variável é declarada na seção VARIÁVEIS, do
programa. Na linguagem C, as variáveis são declaradas antes de serem utilizadas. Já em Tcl,
não há necessidade de declarar as variáveis antes de se fazer uso delas.
Exemplos:
Declarar a variável X, do tipo INTEIRO, em Algoritmo, C e Tcl.
Algoritmo:
VARIAVEIS
X : INTEIRO
C:
int X;
Tcl:
set X 0
4.5. Tipos de dados
Na maioria das linguagens de programação é necessário declarar o tipo de dado que uma
variável irá conter, antes que se possa utilizá−la, e uma vez declarado, normalmente, não se
pode alterá−lo. A tabela a seguir mostra os tipos de dados suportados em Algoritmo, C e Tcl:
25
Algoritmo C Tcl
INTEIRO − um valor inteiro
entre −32768 e +32767.
Ocupa 2 bytes.
int − um valor inteiro entre
−32768 e +32767.
Todas as variáveis em Tcl são
consideradas cadeia de
caracteres alfa−numéricos.
REAL − um valor em ponto
fulutuante entre 2.9 x 10−39 e
1.7 x 10−38. Ocupa 6 bytes.
float − um valor em ponto
fulutuante entre ±1.175494E−
38 e ±3.402823E−38.
CARACTERE − um
caractere da tabela ASCII.
Ocupa 1 byte.
char − um valor inteiro entre
−128 e +127.
CADEIA − conjunto de
caracteres. Ocupa 1a 255
bytes na memória.
short − um valor inteiro entre
−32768 e +32767.
LÓGICO − um valor lógico
verdadeiro ou falso. Ocupa 1
byte.
long − um valor inteiro entre
−2147483648 e
+2147483647.
double − um valor em ponto
fulutuante entre 2.9 x 10−39 e
1.7 x 10−38.
Tabela 4.5.1: Tipos de dados em Algoritmos, C e Tcl
Exemplos:
Algoritmo:
VARIAVEIS
X : INTEIRO
Nome : CADEIA
C:
int X;
char nome[20];
26
Tcl:
set X 0
set Nome “”
4.6. Constantes
Constantes são variáveis cujo valor permanece o mesmo durante toda a execução do program
a sendo apenas para leitura. Constantes são declaradas com a palavra chave const ou com a di
retiva #define em C, sendo que cada uma destas formas têm significados diferentes. A palavr
a chave const declara que uma aposição de memória terá um valor fixo e imutável durante to
da a execução do programa, enquanto a diretiva #define especifica uma constante para ser sub
stituída no momento da compilação do programa. Por outro lado, constantes não têm qualque
r significado em Tcl.
Exemplos:
C:
#define PI 3.141592654
27
5. OPERADORES
5.1. Operadores matemáticos
Os operadores matemáticos são basicamente os mesmos na maioria das linguagens,
entretando podem haver diferenças de sintaxe de linguagem para linguagem. A tabela a seguir
ilustra os operadores matemáticos suportados em Algoritmo, C e Tcl:
Algoritmo C Tcl Significado
+ + + Soma
− − − Subtração
* * * Multiplicação
/ / / Divisão
DIV Quociente
MOD % % Resto
** Exponenciação
= == == Igualdade
<> != != Diferença
<= <= <= Menor ou igual
>= >= >= Maior ou igual
< < < Menor que
> > > Maior que
:= ou ← = set variável [valor] Atribuição
& & AND bit a bit
| | OR bit a bit
^ ^ XOR bit a bit
~ ~ NOT bit a bit
Em Tcl operações matemáticas são realizadas pelo comando expr que retorna o resultado da
expressão passada como argumento.
28
Exemplos:
Algoritmo:
X := 3
Y := 7
Z := X + Y
C:
X = 3;
Y = 7;
Z = X + Y;
Tcl:
set X 3
set Y 7
set Z [expr $X + $Y]
29
5.2. Operadores lógicos
Os operadores lógicos foram estudados no capítulo 3. Contudo, existem diferenças de sintaxe
de linguagem para linguagem. A tabela a seguir mostra os operadores lógicos em Algoritmos,
C e Tcl:
Algoritmo C Tcl Significado
AND && && AND lógico
OR || || OR lógico
XOR XOR lógico
NOT ! ! NOT lógico
5.3. Precedência dos operadores
Os operadores matemáticos e lógicos de C obedecem à seguinte ordem de precedência:
Ordem de precedência dos operadores matemáticos e lógicos de C
() [] . −>
! ~ ++ −− + − * & (tipo) sizeof
* / %
+ −
<< >>
== !=
&
^
|
&&
?:
= += −= *= /= %= &= ^= != <<= >>=
30
6. COMANDOS DE ENTRADA E SAÍDA
A maioria dos programas de computador necessitam obter dados do exterior e devolver algum
resultado após ter processado estes dados. Para tanto são utilizados comandos de entrada e
saída.
A tabela a seguir mostra os comandos de entrada e saída mais comuns em Algoritmos, C e
Tcl:
Algoritmo C Tcl Significado
LEIA char gets(char *s) gets canal [variável] Lê uma cadeia de
caracteres da entrada
padrão ( stdin ) até
que seja pressionada a
tecla ENTER.
ESCREVA int puts(const char
*s)
puts [−nonewline]
[canal] string
Escreve uma cadeia
de caracteres na saida
padrão ( stdout ).
Exemplos:
Algoritmo:
ALGORITMO Alo_Mundo
INÏCIO
ESCREVA “Alo Mundo!”
FIM
31
C:
#include <stdio.h>
int main(void)
{
puts(“Alo Mundo!”);
return(0);
}
Tcl:
puts “Alo Mundo!”
6.1. Saída padrão ( stdout )
A saída padrão( stdout ) é o local, canal, padrão, onde os dados serão escritos, sempre que
uma saída não for especificada. Em C e Tcl a saída padrão é chamada de stdout.
6.2. Entrada padrão ( stdin )
A entrada padrão( stdin ) é o local, canal, padrão, onde os dados serão lidos, sempre que uma
entrada não for especificada. Em C e Tcl a entrada padrão é chamada de stdin.
32
7. ESTRUTURAS DE CONTROLE
Estruturas de controle são mecanismos que permitem desviar a linha de execução de um
programa quando determinada condição ocorre. As estruturas de controle mais comuns são
SE... ENTÃO... SENÃO... e CASO..., detalhadas a seguir.
7.1. Estrutura SE... ENTÃO... SENÃO... ( IF... THEN... ELSE... )
A estrutura SE... ENTÃO... SENÃO... tem a seguinte sintaxe:
SE condição1 ENTÃO
 comandos1...
[SENÃO
 comandos2...]
FIMSE
A porção de código comandos1 será executada se a condição condição1 for verdadeira, caso
contrário a porção de código comandos2 será executada.
A estrutura de controle SE... ENTÃO... SENÃO... está disponível em praticamente todas as
linguagens de programação, contudo a forma de implementá−la varia de linguagem para
linguagem. A seguir, são apresentados exemplos de uso desta estrutura de controle nas
linguagens C e Tcl:
33
C:
#include <stdio.h>
#include <ctype.h>
int main(void)
{
 char opcao;
 puts("Continuar S/N ?");
 gets(&opcao);
 if (toupper(opcao) == ’S’) {
 puts("Voce digitou SIM(S) !");
 } else {
 puts("Voce digitou NAO(N) !");
 }
 return(0);
}
Tcl:
puts "Continuar S/N ?"
set opcao [gets stdin]
if {[string toupper $opcao] == {S}} {
 puts "Voce digitou SIM(S) !"
} else {
 puts "Voce digitou NAO(N) !"
}
exit
34
7.2. Estrutura CASO... ( CASE... )
A estrutura CASO... tem a seguinte sintaxe:
CASO valor1
 opção1:
 comandos1...
 opção2:
 comandos2...
 opçãoN:
 comandosN...
[SENÃO
 comandos...]
FIMCASO
A porção de código comandos1 será executada se o valor de valor1 for igual à opção1, a
porção de código comandos2 será executada se o valor de valor1 for igual à opção2, e assim
por diante, caso valor1 não seja igual a nenhuma das opções oferecidas, a porção de código
comandos será executada.
A estrutura de controle CASO... está disponível em praticamente todas as linguagens de
programação, contudo a forma de implementá−la varia de linguagem para linguagem. A
seguir, são apresentados exemplos de uso desta estrutura de controle nas linguagens C e Tcl:
35
C:
#include <stdio.h>
#include <ctype.h>
int main(void)
{
 char opcao;puts("Continuar S/N ?");
 gets(&opcao);
 switch (toupper(opcao)) {
 case ’S’:
 puts("Voce digitou SIM(S) !");
 break;
 case ’N’:
 puts("Voce digitou NAO(N) !");
 break;
 default:
 puts("Opcao invalida !");
 }
 return(0);
}
Tcl:
puts "Continuar S/N ?"
set opcao [gets stdin]
switch [string toupper $opcao] {
 S {
 puts "Voce digitou SIM(S) !"
 }
 N {
 puts "Voce digitou NAO(N) !"
 }
 default {
 puts "Opcao invalida !"
 }
}
exit
36
8. LAÇOS DE REPETIÇÃO
Laços de repetição são mecanismos que permitem que partes de um programa sejam
executadas até que uma determinada condição ocorra. As estruturas de repetição mais comuns
são ENQUANTO... FAÇA..., FAÇA... ENQUANTO... e PARA... FAÇA..., detalhadas a
seguir.
8.1. Estrutura ENQUANTO... FAÇA... ( WHILE... DO... )
A estrutura ENQUANTO... FAÇA... tem a seguinte sintaxe:
ENQUANTO condição1 FAÇA
 comandos1...
FIMENQUANTO
A porção de código comandos1 será executada enquanto a condição condição1 for avaliada
como verdadeira.
A estrutura de controle ENQUANTO... FAÇA... está disponível em praticamente todas as
linguagens de programação, contudo a forma de implementá−la varia de linguagem para
linguagem. A seguir, são apresentados exemplos de uso desta estrutura de controle nas
linguagens C e Tcl:
37
C:
#include <stdio.h>
int main(void)
{
 char n;
 n = ’0’;
 while(n <= ’9’) {
 printf("%c\n", n);
 n++;
 }
 return(0);
}
Tcl:
set n 0
while {$n <= 9} {
 puts $n
 incr n
}
exit
38
8.2. Estrutura FAÇA... ENQUANTO... ( DO... WHILE... )
A estrutura FAÇA... ENQUANTO... tem a seguinte sintaxe:
FAÇA
 comandos1...
ENQUANTO condição1
A porção de código comandos1 será executada uma vez e continuará sendo executada
enquanto a condição condição1 for avaliada como verdadeira.
A estrutura de controle FAÇA... ENQUANTO... está disponível em muitas linguagens de
programação, contudo a forma de implementá−la varia de linguagem para linguagem. A
seguir, é apresentado um exemplos do uso desta estrutura de controle na linguagens C:
C:
#include <stdio.h>
int main(void)
{
 char n;
 n = ’0’;
 do {
 printf("%c\n", n);
 n++;
 } while(n <= ’9’);
 return(0);
}
39
8.3. Estrutura PARA... FAÇA... ( FOR... TO... DO... )
A estrutura PARA... FAÇA... tem a seguinte sintaxe:
PARA variável1 DE início ATÉ fim, PASSO n FAÇA
 comandos1...
FIMPARA
A porção de código comandos1 será executada para cada valor no intervalo de início até fim,
atribuindo o valor correspondente, à variável variável1, a cada interação, e opcionalmente,
saltando os valores no passo n.
A estrutura de controle PARA... FAÇA... está disponível em praticamente todas as
linguagens de programação, contudo a forma de implementá−la varia de linguagem para
linguagem. A seguir, são apresentados exemplos de uso desta estrutura de controle nas
linguagens C e Tcl:
40
C:
#include <stdio.h>
int main(void)
{
 char n;
 for(n = ’0’; n <= ’9’; n++) {
 printf("%c\n", n);
 }
 return(0);
}
Tcl:
for {set n 0} {$n <= 9} {incr n} {
 puts $n
}
exit
41
9. ESTRUTURAS HOMOGÊNEAS
No desenvolvimento de programas de computador, surge com frequência a necessidade de se
trabalhar com dados tabelados, como listas de índices de correção monetária, tabelas de
preços de produtos etc. De um modo geral, os conceitos sobre matrizes estudados na
matemática vista no ensino médio são aplicáveis também à programação de computador.
Neste capítulo veremos como criar matrizes unidimensionais( vetores ) e multi−dimensionais(
matrizes propriamente ditas ).
9.1. Vetores uni−dimensionais
Vetores são matrizes de uma única dimensão e são declarados em Algoritmo como a seguir:
VARIAVEIS
nome : VETOR[início...fim] DE tipo
42
Exemplo:
ALGORITMO media
VARIAVEIS
 nota : VETOR[1...3] DE REAL
 soma : REAL
 media : REAL
INICIO
 soma ← 0
 PARA i DE 1 ATE 3 PASSO 1 FAÇA
 LEIA nota[i]
 soma ← soma + nota[i]
 FIMPARA
 media ← soma / 3
 ESCREVA media
FIM
Os vetores unidimensionais também são suportados pelas linguagens C e Tcl. A seguir, são
apresentadas as versões do algoritmo acima em C e Tcl:
43
C:
#include <stdlib.h>
#include <stdio.h>
int main(void)
{
 char valor = " \0";
 double nota[3];
 double soma;
 double media;
 int i;
 soma = 0;
 for(i = 0; i < 3; i++) {
 printf("Digite a nota %d: ", i + 1);
 gets(&valor);
 nota[i] = atof(&valor);
 printf("Nota %d = %5.2f\n\n", i + 1, nota[i]);
 soma = soma + nota[i];
 }
 media = soma / 3;
 printf("\nMedia = %5.2f\n", media);
 return(0);
}
Tcl:
set soma 0
for {set i 0} {$i < 3} {incr i} {
 puts "Digite a nota $i: "
 set nota($i) [gets stdin]
 puts "Nota $i = [format {%5.2f} $nota($i)]\n"
 set soma [expr $soma + $nota($i)]
}
set media [expr $soma / 3]
puts "\nMedia = [format {%5.2f} $media]\n"
44
9.1.1. Operações com vetores uni−dimensionais
9.1.1.1. Atribuição de um vetor
Vetores são atribuídos como a seguir:
VARIAVEIS
nome : VETOR[início...fim] DE tipo
9.1.1.2. Leitura de dados de um vetor
Um elemento de um vetor pode ser lido fazendo−se referência ao nome do vetor e ao índice
do elemento cujo conteúdo se deseja ler:
variável ← vetor[índice]
9.1.1.3. Escrita de dados em um vetor
Atribui−se um valor a um elemento de um vetor fazendo−se referência ao nome do vetor e ao
índice do elemento ao qual se deseja atribuir um valor:
nome[índice] ← valor
45
9.2. Matrizes ou vetores de mais de uma dimensão
Matrizes são vetores com mais de uma dimensão e são atribuídos e operados de modo similar
aos vetores unidimensionais.
9.2.1. Operações com vetores de mais de uma dimensão
9.2.1.1. Atribuição de uma matriz
Matrizes são atribuídas como a seguir:
VARIAVEIS
nome : MATRIZ[início1...fim1, início2...fim2] DE tipo
9.2.1.2. Leitura de dados de uma matriz
Um elemento de uma matriz pode ser lido fazendo−se referência ao nome da matriz e aos
índices do elemento cujo conteúdo se deseja ler:
variável ← matriz[índice1, indice2]
9.2.1.3. Escrita de dados em uma matriz
Atribui−se um valor a um elemento de uma matriz fazendo−se referência ao nome da matriz e
aos índices do elemento ao qual se deseja atribuir um valor:
nome[índice1, indice2] ← valor
46
10. ESTRUTURAS HETEROGÊNEAS
Muitas vezes precisamos trabalhar com grupos de dados de diferentes tipos, mas que juntos
compõem uma unidade lógica. Esta unidade lógica é chamada de registro. Uma ficha de um
aluno contendo NOME, NOTA DA PRIMEIRA UNIDADE, NOTA DA SEGUNDA
UNIDADE e NOTA DA TERCEIRA UNIDADE, constitui um registro de aluno. O conjunto
de registros de todos os alunos de uma turma constitui uma tabela, ou matriz de alunos.
10.1. Registros
Um conjunto de dados de diferentes tipos que somente fazem sentido quando considerados
juntos é chamado registro. Em geral registros compõem conjuntos maiores chamados tabelas,
que para todos os efeitos práticos podem ser considerados matrizes de dados.
A tabela a seguir representa um conjunto de registros de dados contendo NOME, NOTA DA
PRIMEIRA UNIDADE, NOTA DA SEGUNDA UNIDADE e NOTA DA TERCEIRA
UNIDADE de cada aluno da disciplina ALGORITMOS DE ESTRUTURAS DE DADOS:
NOME NOTA DA PRIMEIRA UNIDADE NOTA DA SEGUNDA UNIDADE NOTA DA TERCEIRA UNIDADE
ALBERTO 10,0 9,0 7,0
CARLOS 8,0 8,0 9,0
FABRÍCIO 7,0 7,0 8,0
KÁTIA 9,0 9,0 8,0
LÚCIA 10,0 10,0 10,0
MARTA 8,0 10,0 9,0
OTÁVIO 10,0 9,0 9,0
PAULO 7,0 8,0 10,0SANDRA 10,0 7,0 8,0
TEREZA 10,0 10,0 10,0
47
Cada linha da tabela anterior constitui um registro e cada coluna constitui um campo do
registro.
10.2. Operações com registros
Os registros são declarados antes das variáveis, pois são utilizados como tipos de dados para
definições de matrizes. Após definida a estrutura de um registro pode−se declarar uma matriz
como do tipo do registro, exatamente como se faria com qualquer estrutura linear.
10.2.1. Atribuição de um registro
Registros são atribuídos, em Algoritmos, da seguinte forma:
TIPO
 identificador = REGISTRO
 campo : tipo
 FIMREGISTRO
VARIÁVEIS
 variável : tipo
48
Exemplo:
TIPO
 NOTA_ALUNO = REGISTRO
 NOME : CADEIA
 NOTA1 : REAL
 NOTA2 : REAL
 NOTA3 : REAL
 FIMREGISTRO
VARIÁVEIS
 ALUNO : NOTA_ALUNO
10.2.2. Leitura de um registro
Registros normalmente são lidos de arquivos utilizando a instrução LEIA.
Exemplo:
INÍCIO
 LEIA ALUNO.NOME
 LEIA ALUNO.NOTA1
 LEIA ALUNO.NOTA2
 LEIA ALUNO.NOTA2
FIM
49
10.2.3. Escrita em um registro
Registros normalmente são escritos em arquivos utilizando a instrução ESCREVA.
Exemplo:
INÍCIO
 ESCREVA ALUNO.NOME
 ESCREVA ALUNO.NOTA1
 ESCREVA ALUNO.NOTA2
 ESCREVA ALUNO.NOTA2
FIM
10.3. Conjuntos de registros
Conforme foi explicado antes, conjuntos de registros compõem tabelas de dados e , para todos
os efeitos práticos, podem ser tratados como matrizes.
10.4. Operações com conjuntos de registros
Escreve−se em um conjunto de registros, do mesmo modo como se escreve em vetores e
matrizes, referenciando cada registro através de índices.
50
10.4.1. Atribuição de um conjunto de registros
Atribui−se um conjunto de registros como a seguir:
VARIÁVEIS
 nome : VETOR[início...fim] DE tipo
Exemplo:
TIPO
 NOTA_ALUNO = REGISTRO
 NOME : CADEIA
 NOTA1 : REAL
 NOTA2 : REAL
 NOTA3 : REAL
 FIMREGISTRO
VARIÁVEIS
 ALUNO : VETOR[1...10] DE NOTA_ALUNO
51
10.4.2. Leitura de um registro de um conjunto
Um registro de um conjunto pode ser lido da seguinte forma:
LEIA conjunto[índice].campo
Exemplo:
ALGORITMO Leitura_de_Registro
TIPO
 NOTA_ALUNO = REGISTRO
 NOME : CADEIA
 NOTA1 : REAL
 NOTA2 : REAL
 NOTA3 : REAL
 FIMREGISTRO
VARIÁVEIS
 ALUNO : VETOR[1...10] DE NOTA_ALUNO
INÍCIO
 PARA i DE 1 ATE 10 PASSO 1 FAÇA
 LEIA ALUNO[i].NOME
 LEIA ALUNO[i].NOTA1
 LEIA ALUNO[i].NOTA2
 LEIA ALUNO[i].NOTA2
 FIMPARA
FIM
52
10.4.3. Escrita em um registro de um conjunto
Um registro de um conjunto pode ser escrito da seguinte forma:
ESCREVA conjunto[índice].campo
Exemplo:
ALGORITMO Escrita_de_Registro
TIPO
 NOTA_ALUNO = REGISTRO
 NOME : CADEIA
 NOTA1 : REAL
 NOTA2 : REAL
 NOTA3 : REAL
 FIMREGISTRO
VARIÁVEIS
 ALUNO : VETOR[1...10] DE NOTA_ALUNO
INÍCIO
 PARA i DE 1 ATE 10 PASSO 1 FAÇA
 ESCREVA ALUNO[i].NOME
 ESCREVA ALUNO[i].NOTA1
 ESCREVA ALUNO[i].NOTA2
 ESCREVA ALUNO[i].NOTA2
 FIMPARA
FIM
53
De modo semelhante, em linguagem C registros são declarados através da palavra chave
struct. Em Tcl porém, registros não são declarados de forma alguma. Utilizam−se vetores
associativos para emular a mesma funcionalidade, de um modo bastante simplificado.
Veja agora alguns exemplos de leitura e escrita de registros em Tcl e C:
Tcl:
for {set i 1} {$i <= 4} {incr i} {
 puts “NOME:”
 set aluno($i,nome) [gets stdin]
 puts “NOTA UNID. 1:”
 set aluno($i,nota1) [gets stdin]
 puts “NOTA UNID. 2:”
 set aluno($i,nota2) [gets stdin]
 puts “NOTA UNID. 3:”
 set aluno($i,nota3) [gets stdin]
 puts “”
}
for {set i 1} {$i <= 4} {incr i} {
 puts “NOME: $aluno($i,nome)”
 puts “NOTA UNID. 1: $aluno($i,nota1)”
 puts “NOTA UNID. 2: $aluno($i,nota2)”
 puts “NOTA UNID. 3: $aluno($i,nota3)”
 puts “”
}
exit
54
C:
#include <stdlib.h>
#include <stdio.h>
struct NOTA_ALUNO {
 char nome[21];
 double nota1;
 double nota2;
 double nota3;
};
struct NOTA_ALUNO aluno[4];
int main(void)
{
 char valor = " \0";
 int i;
 for(i = 0; i <= 3; i++) {
 printf("NOME :");
 gets(&aluno[i].nome);
 printf("NOTA UNID. 1: %d: ", i + 1);
 gets(&valor);
 aluno[i].nota1 = atof(&valor);
 printf("NOTA UNID. 2: %d: ", i + 1);
 gets(&valor);
 aluno[i].nota2 = atof(&valor);
 printf("NOTA UNID. 3: %d: ", i + 1);
 gets(&valor);
 aluno[i].nota3 = atof(&valor);
 }
55
 for(i = 0; i <= 3; i++) {
 printf("−−> Registro %d <−−\n", i + 1);
 printf("NOME : %s\n", aluno[i].nome);
 printf("NOTA UNID. 1: %5.2f\n", aluno[i].nota1);
 printf("NOTA UNID. 2: %5.2f\n", aluno[i].nota2);
 printf("NOTA UNID. 3: %5.2f\n", aluno[i].nota3);
 }
 return(0);
}
56
11. PROGRAMAÇÃO ESTRUTURADA OU MODULAR
À medida que os algoritmos vão se tornando mais e mais complexos, eles crescem em
tamanho e se tornam mais difíceis de ler, entender e depurar. Nestes casos costuma−se dividir
o algoritmo em partes menores, e que normalmente se repetem várias vezes ao longo de todo
o programa. Neste capítulo serão vistas as principais técnicas para divisão de algorítmos em
partes menores e reaproveitáveis.
11.1. Sub−rotimas
Uma sub−rotina é uma porção de um algoritmo chamada várias vezes em um programa e
separada do bloco principal para simplificar o código e torná−lo menor.
11.1.1. Procedimentos
Um procedimento é uma sub−rotina que pode ou não receber argumentos, ou parâmetros, mas
que, embora produza algum tipo de ação, não retorna resultado algum para a porção de
código que o chamou.
A sintaxe para criação de procedimentos é a seguinte:
PROCEDIMENTO <Nome do Procedimento(Parâmetros)>
VARIÁVEIS
 <Variáveis>
INÍCIO
 <Comandos>
FIM
57
Exemplo:
ALGORITMO Alo_Mundo
PROCEDIMENTO Exibe_Alo
INÍCIO
 WRITE “Alo Mundo!”
FIM
INICIO
 Exibe_Alo
FIM
Em Tcl procedimentos são criados através do comando proc. Em C procedimentos são
criados precedendo o nome do procedimento do tipo void.
58
Exemplos:
Tcl:
proc alomundo {} {
 puts “Alo Mundo!”
}
alomundo
exit
C:
#include <stdio.h>
void alomundo (void) {
 puts("Alo Mundo!");
}
int main(void)
{
 alomundo();
 return(0);
}
59
11.1.2. Funções
Uma função é uma sub−rotina que pode ou não receber argumentos, ou parâmetros, e que
sempre retorna algum resultado, de um tipo pré−definido, para a porção de código que a
chamou. Um valor é retornado atribuindo−o ao nome da função, como se fosse uma variável.
A sintaxe para criação de uma função é a seguinte:
FUNÇÃO <Nome da Função(Parâmetros) : Tipo>
VARIÁVEIS
 <Variáveis>
INÍCIO
 <Comandos>
FIM
Em Tcl funções são criadas através do comando proc. Em C funções são criados precedendo
o nome do procedimento do tipo de retorno da função.
60
Exemplos:
Tcl:
proc quadrado {X} {
 return [expr $X * $X]
}
puts “O quadrado de 25 e [quadrado 25]”
exit
C:
#include <stdio.h>
int quadrado (int x) {
 return(x * x);
}
int main(void)
{
 printf(“O quadrado de 25 e %d\n“, quadrado(25));
 return(0);
}
61
11.2. Parâmetros formais e reais
Parâmetros formais são aqueles declarados no cabeçalho da função ou procedimento.
Parâmetros reais são aqueles passados para a função( ou procedimento ) no momento em que
ela é chamada.
No exemplo anterior, a declaração int x no cabeçalho da função quadrado é seu parâmetro
formal, enquanto que 25 na chamadada função, dentro da chamada da função printf, é um
parâmetro real.
11.3. Passagem de parâmetros
11.3.1. Passagem de parâmetros por valor
Parâmetros são passados por valor, quando alterações realizadas neste parâmetro, dentro da
função chamada, não alteram o valor passado ao retornar da função. No exemplo anterior, da
função quadrado, o parâmetro x é passado por valor.
11.3.2. Passagem de parâmetros por referência
Parâmetros são passados por referência, quando alterações realizadas neste parâmetro, dentro
da função chamada, alteram o valor passado ao retornar da função. Na chamada da função
atof(&valor) o parâmetro valor é passado por referência.
62
11.4. Variáveis locais e globais
Variáveis locais são aquelas que têm existência e visibilidade somente dentro da função ou
procedimento em que foram declaradas. Variáveis globais são aquelas que têm existência
durante toda a execução do programa e podem ser acessadas de dentro de qualquer sub−rotina
do mesmo. Em C variáveis globais são declaradas colocado−as fora de qualquer
procedimento, enquanto em Tcl elas são declaradas através do comando global.
11.4.1. Escopo de variáveis
O escopo de uma variável refere−se à sua visibilidade e existência. Quando dizemos que uma
variável é global, queremos dizer que seu escopo é todo o programa, enquanto que variáveis
locais têm seu escopo restrito à função na qual foram declaradas.
63
12. ALGORITMOS DE ORDENAÇÃO
No nosso dia−a−dia, com frequência, nos ocorre de termos de procurar dados em listas ou
tabelas. Quando estes dados nos são apresentados de forma desordenada, nosso trabalho é
muito mais difícil do que se eles estivessem previamente classificados. Neste capítulo
estudaremos os principais algoritmos para ordenação ou classificação de dados.
12.1. Ordenação por inserção
Este é o algoritmo mais simples de ordenação e consiste em inserir os novos elementos de um
vetor em sua posição correta, levando em conta os elementos que já estiverem classificados.
O passos são os seguintes:
1. Temos dois vetores, um ordenado e um desordenado.
2. Um primeiro elemento encontra−se no vetor ordenado, enquanto os demais se encontram
no vetor desordenado.
3. Remove−se um elemento do vetor desordenado e insere−se na posição adequada do vetor
ordenado, realizando−se a devida comparação entre os elementos.
4. Repete−se o processo até que todos os elementos do vetor desordenado tenha sido movidos
para o vetor ordenado.
64
Algoritmo:
VARIÁVEIS
 vetor : VETOR[1...10] DE INTEIRO
 i : INTEIRO
 j : INTEIRO
 chave : INTEIRO
INÍCIO
 PARA i DE 1 ATÉ 10 FAÇA
 LEIA vetor[i]
 FIMPARA
 PARA j DE 2 ATÉ 10 FAÇA
 chave ← vetor[j]
 i ← j − 1
 ENQUANTO (i > 0) E (vetor[i] > chave) FAÇA
 vetor[i + 1] ← vetor[i]
 i ← i − 1
 FIMENQUANTO
 vetor[i + 1] ← chave
 FIMPARA
FIM
65
12.2. Ordenação por troca
No processo de ordenação por troca, o vetor é percorrido, comparando−se seus elementos
dois a dois, e trocando−se suas posições sempre que eles estiverem fora de ordem.
12.2.1. Método da bolha ( bubble sort )
O método da bolha consiste em ordenar os elementos de um vetor seguindo−se os seguintes
passos:
1. Compara−se cada elemento com o próximo a cada interação.
2. Se o elemento estiver fora de ordem, troca−se sua posição com o próximo.
3. Prosseguem−se as interações até que não ocorram mais trocas.
Este algoritmo somente deve ser utilizado para classificar vetores pequenos, pois é muito
ineficiente.
66
Algoritmo:
VARIÁVEIS
 vetor : VETOR[1...10] DE INTEIRO
 i : INTEIRO
PROCEDIMENTO boblesort(vetor : VETOR[] DE INTEIRO, tamanho : INTEIRO)
VARIÁVEIS
 i : INTEIRO
 j : INTEIRO
 temp : INTEIRO
INÍCIO
 PARA i DE 1 ATÉ tamanho FAÇA
 PARA j DE 1 ATÉ tamanho FAÇA
 SE vetor[i] < vetor[j] FAÇA
 temp ← vetor[i]
 vetor[i] ← vetor[j]
 vetor[j] ← temp
 FIMSE
 FIMPARA
 FIMPARA
FIM
INÍCIO
 PARA i DE 1 ATÉ 10 FAÇA
 LEIA vetor[i]
 FIMPARA
 boblesort(vetor, 10)
 PARA i DE 1 ATÉ 10 FAÇA
 ESCREVA vetor[i]
 FIMPARA
FIM
67
12.2.1. Método de divisão e troca ( quick sort )
O método da divisão e troca parte do princípio de que é mais rápido ordenar dois vetores com
a metade do tamanho do vetor original que ordenar o vetor inteiro.
Para ordenar um vetor pelo método quick sort segue−se os seguintes passos:
1. Seleciona−se o valor médio do vetor como separador da lista.
2. Divide−se a lista em duas partes: uma com os valores que são menores que o separador e
outra com os valores que são maiores.
3. A sub−rotina chama então a si mesma recursivamente passando como parâmetros as duas
metades da lista obtidas.
3. A cada chamada a sub−rotina divide as listas em duas metades usando os mesmos critérios
anteriores até que não seja mais possível dividir as porções da lista em partes menores.
68
Algoritmo:
VARIÁVEIS
 vetor : VETOR[1...10] DE INTEIRO
 i : INTEIRO
PROCEDIMENTO quicksort(vetor : VETOR[] DE INTEIRO, primeiro : INTEIRO, último : INTEIRO)
VARIÁVEIS
 menor : INTEIRO
 maior : INTEIRO
 separador : INTEIRO
 temp : INTEIRO
INÍCIO
 menor ← primeiro
 maior ← último
 separador ← vetor[(primeiro + último) / 2]
 FAÇA
 ENQUANTO vetor[menor] < separador FAÇA
 menor ← menor + 1
 FIMENQUANTO
 ENQUANTO vetor[maior] > separador FAÇA
 maior ← maior − 1
 FIMENQUANTO
 SE menor <= maior FAÇA
 temp ← vetor[menor]
 vetor[menor] ← vetor[maior]
 vetor[maior] ← temp
 menor ← menor + 1
 maior ← maior − 1
 FIMSE
 ENQUANTO menor <= maior
 SE primeiro < maior FAÇA
 quicksort(vetor, primeiro, maior)
 FIMSE
 SE menor < último FAÇA
 quicksort(vetor, menor, último)
 FIMSE
FIM
69
INÍCIO
 PARA i DE 1 ATÉ 10 FAÇA
 LEIA vetor[i]
 FIMPARA
 quicksort(vetor, 1, 10)
 PARA i DE 1 ATÉ 10 FAÇA
 ESCREVA vetor[i]
 FIMPARA
FIM
70
12.3. Ordenação por seleção
O método da ordenação por seleção consiste em ordenar os elementos de um vetor seguindo−
se os seguintes passos:
1. Seleciona−se um elemento do vetor( geralmente o primeiro ).
2. Identifica−se o menor elemento dentre os elementos ainda não selecionados.
3. Troca−se o elemento identificado na etapa anterior com o primeiro elemento.
4. Seleciona−se o elemento seguinte e procura−se o menor elemento do vetor, a partir do
novo elemento selecionado.
5. Retornna−se para a etapa 3 até que se selecione o último elemento do vetor.
Este algoritmo somente deve ser utilizado para classificar vetores pequenos, pois é muito
ineficiente.
71
Algoritmo:
VARIÁVEIS
 vetor : VETOR[1...10] DE INTEIRO
 i : INTEIRO
PROCEDIMENTO shell(vetor : VETOR[] DE INTEIRO, tamanho : INTEIRO)
VARIÁVEIS
 i : INTEIRO
 j : INTEIRO
 temp : INTEIRO
INÍCIO
 PARA i DE 1 ATÉ tamanho − 1 FAÇA
 PARA j DE i + 1 ATÉ tamanho FAÇA
 SE vetor[i] > vetor[j] FAÇA
 temp ← vetor[i]
 vetor[i] ← vetor[j]
 vetor[j] ← temp
 FIMSE
 FIMPARA
 FIMPARA
FIM
INÍCIO
 PARA i DE 1 ATÉ 10 FAÇA
 LEIA vetor[i]
 FIMPARA
 shell(vetor, 10)
 PARA i DE 1 ATÉ 10 FAÇA
 ESCREVA vetor[i]
 FIMPARA
FIM
72
13. ALGORITMOS DE PESQUISA
A maioria dos programas de computador realiza boa parte de seu trabalho pesquisandodados
em vetores ou matrizes. Um exemplo típico é um software de cadastro de clientes que
necessita encontrar o nome de um cliente específico em uma base de dados. Neste capítulo
veremos os dois métodos mais utilizados para pesquisa de dados em listas desordenadas e
ordenadas.
13.1. Algoritmos de busca em tabela
O algoritmo de busca mais simples consiste em procurar sequencialmente, item por item, um
dado em uma lista. O algoritmo a seguir mostra como localizar dados em um vetor, esteja ele
ordenado ou não.
73
Algoritmo:
VARIÁVEIS
 vetor : VETOR[1...10] DE INTEIRO
 i : INTEIRO
FUNÇÃO sequencial(vetor : VETOR[] DE INTEIRO, tamanho : INTEIRO, valor : INTEIRO)
VARIÁVEIS
 i : INTEIRO
INÍCIO
 PARA i DE 1 ATÉ tamanho FAÇA
 SE valor = vetor[i] FAÇA
 sequencial ← i
 FIMSE
 FIMPARA
 sequencial ← −1
FIM
INÍCIO
 PARA i DE 1 ATÉ 10 FAÇA
 LEIA vetor[i]
 FIMPARA
 ESCREVA sequencial(vetor, 10, 5)
FIM
74
13.2. Algoritmo de pesquisa binaria
Quando os dados em um vetor se encontram previamente ordenados pode−se realizar uma
busca bastante eficiente através da pesquisa binária. Este método leva esse nome devido ao
fato de a cada interação em busca de um valor, dividir−se a lista em duas partes,
prosseguindo−se até que não seja mais possível dividir a lista ou valor seja encontrado.
A seguir é apresentado o algorítmo de pesquisa binária para números inteiros:
75
Algoritmo:
VARIÁVEIS
 vetor : VETOR[1...100] DE INTEIRO
 i : INTEIRO
FUNÇÃO binária(vetor : VETOR[] DE INTEIRO, tamanho : INTEIRO, valor : INTEIRO)
VARIÁVEIS
 menor : INTEIRO
 médio : INTEIRO
 maior : INTEIRO
 encontrou : INTEIRO
INÍCIO
 menor ← 1
 maior ← tamanho
 médio ← (maior + menor) / 2
 encontrou ← 0
 ENQUANTO (encontrou = 0) E (maior <> menor) FAÇA
 SE valor = vetor[medio] FAÇA
 encontrou ← 1
 SENÃO
 SE valor < vetor[medio] FAÇA
 maior ← médio − 1
 SENÃO
 menor ← médio + 1
 FIMSE
 FIMSE
 médio ← (maior + menor) / 2
 FIMENQUANTO
 SE encontrou = 1 FAÇA
 binária ← médio
 SENÃO
 binária ← −1
 FIMSE
FIM
76
INÍCIO
 PARA i DE 1 ATÉ 100 FAÇA
 vetor[i] ← i
 FIMPARA
 ESCREVA binária(vetor, 100, 75)
FIM
77
14. ÁRVORES
Uma árvore é um conjunto finito de n nós, com n ≥ 0. Se n = 0 tem−se uma árvore nula. Se n
> 0, a árvore terá as seguintes características:
1. O primeiro nó superior é chamado raiz;
2. Os demais nós serão particionados em 1 ou mais estruturas chamadas subarvores.
Nomenclatura:
Grau: número de subarvores de um nó.
Folha: nó que possui grau zero( 0 ), não possuindo subarvores.
Grau da árvore: o maior grau dentre os graus de todos os nós de uma árvore.
Filho: nó de uma subarvore.
Pai: raiz de uma subarvore.
Irmãos: nós de uma mesma subarvore.
Nível: distância de um nó até a raiz da árvore.
Altura: Nível da folha que está à maior distância até a raiz mais um( 1 ).
A ilustração a seguir representa uma árvore:
78
Figura 14.1: Uma árvore binária
14.1. Arvores binarias
Árvore binária é uma árvore que pode ser nula ou apresentar as seguintes características:
1. Um nó raiz;
2. Grau 2;
3. Uma subarvore esquerda e uma subarvore direita, sendo cada uma delas uma subarvore.
A figura 14.1 representa uma árvore binária.
79
14.2. Arvores de busca binária
Uma árvore de busca binária é uma árvore binária que apresenta as seguintes características:
1. Os itens da subarvore esquerda são menores que a raiz;
2. Os itens da subarvore direita são maiores ou iguais à raiz;
3. Cada subarvore também é uma árvore binária.
A figura 14.3.1 representa uma árvore de busca binária.
14.3. Representando um nó em uma árvore binária
Uma forma de representar uma árvore binária é através de uma estrutura que contenha o dado
que se deseja armazenar na árvore, um apontador ou índice para a subarvore esquerda e um
apontador ou índice para a subarvore direita.
Figura 14.3.1: Nós de uma árvore de busca binária
80
A estrutura a seguir representa um nó de uma árvore binária, se estivermos armazenando os
nós da árvore em um vetor de caracteres:
TIPO
 NÓ = REGISTRO
 dado : VETOR[1...255] DE CARACTERE
 esquerdo : VETOR[1...5] DE CARACTERE
 direito : VETOR[1...5] DE CARACTERE
 FIMREGISTRO
Esta estrutura pode ser utilizada para armazenar uma árvore de busca binária em um arquivo
ASCII, de modo que se possa acessar todos os dados sobre um nó com uma única leitura, e
desde que cada registro tenha um tamanho fixo de 255 bytes e o arquivo não possua mais de
100.000 registros,
14.4. Inserindo um elemento em uma árvore binária
Para inserir um elemento em uma árvore binária, devemos determinar qual subarvore
esquerda ou direita receberá o novo elemento como seu nó filho.
Supondo que se deseje inserir os caracteres e, b, d, a, f e c em uma árvore binária, estes
elementos serão inseridos da seguinte forma:
81
Figura 14.4.1: Inserção de elementos em uma árvore de busca binária
82
14.5. Pesquisando um elemento em uma árvore binária
Para se procurar um elemento em uma árvore de busca binária segue−se os seguintes passos:
1. Se a árvore for nula retorna−se imediatamente com um apontador nulo;
2. Se o elemento procurador for igual à raiz retorna−se com um apontador para a raiz;
3. Se o elemento procurado for menor que a raiz prossegue−se com a pesquisa pela subarvore
da esquerda, caso contrário prossegue−se com a pesquisa pela subarvore da direita.
4. Caso atinja−se o último nó da subarvore esquerda ou direita sem encontrar o elemento
procurado retorna−se com um apontador nulo.
Por exemplo, para encontrar o caractere C na árvore binária seguinte seguem−se os passos
indicados pelos número 1, 2, 3 e 4:
1. Compara−se o caractere C com a raiz da árvore. C é lexicograficamente menor que E.
Logo o caractere C só pode estar na subarvore esquerda de E;
2. Compara−se o caractere C com o nó B. C é lexicograficamente maior que B. Logo o
caractere C só pode estar na subarvore direita de B;
3. Compara−se o caractere C com o nó D. C é lexicograficamente menor que D. Logo o
caractere C só pode estar na subarvore esquerda de D;
4. Compara−se o caractere C com o nó C. C é lexicograficamente igual a C. Logo o caractere
C esta na subarvore C e a busca termina.
83
Figura 14.5.1: Processo de busca do caractere C em uma árvore de busca binária
84
14.6. Movendo−se em uma árvore binária
De um modo geral, os algoritmos que permitem mover−se em uma arvore binária utilizam
técnicas recursivas, onde a função de movimentação chama a se mesma recursivamente até
que todos os nós da árvore tenham sido apresentados.
Os algorimos para as técnicas em−ordem, pré−ordem e pós−ordem são os seguintes:
Em−ordem
1. Exibe a subarvore esquerda;
2. Exibe a raiz;
3. Exibe a subarvore direita.
Pré−ordem
1. Exibe a raiz;
2. Exibe a subarvore esquerda;
3. Exibe a subarvore direita.
Pós−ordem
1. Exibe a subarvore esquerda;
2. Exibe a subarvore direita;
3. Exibe a raiz.
A ilustração a seguir mostra os passos para movimentação em−ordem em uma árvore de
busca binária:
85
Figura 14.6.1: Movimentação em−ordem em uma árvore de busca binária
86
14.7. Removendo um elemento em uma árvore binária
Para remover um nó de uma árvore de busca binária devemos seguir os seguintes passos:
1. Se a raiz não possui filhos basta remover a raiz;
2. Se a raiz possui apenas um filho, basta mover o filho para a posição da raiz;
3. Se a raiz possui dois filhos, devemos encontraro maior elemento da subarvore esquerda e
move−lo para a posição do nó que se esta removendo.
Observações:
1. O maior elemento da subarvore esquerda não possuirá um filho à direita;
2. A remoção de um nó de uma árvore é um processo recursivo.
A ilustração a seguir mostra como remover o elemento E de um árvore de busca binária:
87
Figura 14.7.1: Remoção de um elemento em uma árvore de busca binária
88
15. PILHAS
Uma pilha é uma lista linear onde todas as operações de inserção, remoção ou consulta,
ocorrem em apenas uma de suas extremidades chamada topo.
A ilustração a seguir representa uma pilha típica:
Figura 15.1: Uma pilha tipica
89
15.1. Operações com pilhas
As operações em uma pilha seguem a ordem last−in, first−out. Ou seja, o último elemento a
entrar na pilha será o primeiro elemento a ser removido dela.
As operações possíveis de serem realizadas com pilhas de dados são as seguintes:
Operação Descrição
Inicializar Remove todos os elementos da pilha.
Pilha Vazia Verifica se a pilha está vazia.
Pilha Cheia Verifica se a pilha está cheia.
Empilhar Coloca um dado no topo da pilha.
Desempilhar Remove um dado do topo da pilha.
Ler Retorna o valor do dado no topo da pilha,
sem removê−lo.
Pilhas são os elementos básicos em calculadoras do tipo RPN( Reverse Polish Notation, ou
Notação Polonesa Reversa ), como a HP48, ou a HP12C, e da linguagem PostScript utilizada
como linguagem universal de impressão em sistemas UNIX e em impressoras a laser.
90
16. FILAS
Uma fila é uma lista linear onde todas as operações de inserção ocorrem em apenas uma de
suas extremidades chamada final da lista, enquanto todas as operações de remoção ou
consulta, ocorrem em apenas na sua outra extremidade chamada início da lista.
A ilustração a seguir representa uma fila típica:
Figura 16.1: Uma fila tipica
91
16.1. Operações com filas
As operações em uma fila seguem a ordem first−in, first−out. Ou seja, o primeiro elemento a
entrar na fila será o primeiro elemento a ser removido dela.
As operações possíveis de serem realizadas com filas de dados são as seguintes:
Operação Descrição
Inicializar Remove todos os elementos da fila.
Fila Vazia Verifica se a fila está vazia.
Fila Cheia Verifica se a fila está cheia.
Inserir Coloca um dado no final da fila.
Remover Remove um dado do início da fila.
Filas são os elementos básicos para o gerenciamento de processos e solicitações de impressão
em sistemas operacionais.
92
REFERÊNCIAS BIBLIOGRÁFICAS
MANZANO, José Augusto N. G. Algorítimos: Lógica para desenvolvimento de
programação. 10a ed. São Paulo: Érica, 2000.
MORAES, Celso Roberto. Estruturas de dados e algoritmos, uma abordagem didática.
São Paulo: Berkeley Brasil, 2001.
KERMIGHAN, Brian W. C, a linguagem de programação padrão ANSI. 9a ed. Rio de
Janeiro: Campus, 1989.
JAMSA, Kris; KLANDER, Lars. Programando em C/C++ “a biblia”. São Paulo:
MAKRON Books, 1999.
REZENDE, Mauro. C++, guia de consulta rápida. São Paulo: Novatec Editora, 1997.
MONTEIRO, Roberto Luiz Souza. Tcl/Tk − Guia de consulta rápida. São Paulo: Novatec,
2001.
NICOLOSI, Denys Emílio Campion. Microcontrolador 8051 detalhado. São Paulo: Érica,
2000.