Universidade Federal de Minas Gerais
Instituto de Ciências Exatas
Departamento de Ciência da Computação

Algoritmos e Estruturas de Dados I

Nomes

Os nomes (identificadores) em C consistem de seqüências de caracteres iniciadas com letras. Os caracteres válidos são letras e dígitos e o sublinhado. Vários elementos da linguagem podem ter nomes. Os nomes podem ser definidos no escopo de elementos que também podem ter nomes.

No decorrer  da disciplina serão apresentados diversos espaços de nomes ou “escopos”.

Expressões

Uma expressão corresponde a um trecho de programa que calcula um certo valor e ainda pode produzir efeitos colaterais. As expressões podem ser utilizadas em vários pontos de um programa. O valor produzido por uma expressão tem associado a ele um certo tipo. As expressões mais simples correspondem a um literal (ou constante) ou uma variável e neste caso o tipo da expressão (ou tipo do valor retornado) corresponde ao tipo do literal ou ao tipo da variável. Quando as expressões envolvem operadores o tipo da expressão corresponde à uma combinação razoavelmente complexa de regras.

Exemplos:
Uma expressão pode ser usada no lado direito de um comando de atribuição: <variavel = <expressao>; O tipo da variável e o tipo da expressão têm que ser "compatíveis".
int a;
a=3; /* a expressão corresponde a uma constante representada por um literal */
double b;
b=3.1415;
double c=2.;
double d;
d=c; /* a expressão corresponde a uma variável */

Conforme dito acima uma expressão pode corresponder a um literal ou uma variável; uma expressão pode correponder ainda a uma chamada de função ou ainda a uma combinação de literais, variáveis e chamadas de funções; A combinação é feita através de "operadores". Existem ainda várias outras maneiras de definir expressões que serão vistas mais à frente na disciplina.

Uma chamada de funcão corresponde a um desvio do fluxo de execução para um trecho de código que irá calcular um valor (de um certo tipo) e retorná-lo no ponto em que o fluxo de controle também retorna. Cada função tem 0, 1 ou mais argumentos (ou parâmetros) na sua definição. O compilador verifica se existe uma expressão para cada argumento do método invocado. A sintaxe para o conjunto de argumentos consiste em uma lista de expressões separadas por vírgula e delimitada por abre e fecha parênteses.

Exemplos de expressões correspondentes a chamadas de funções:
int a;
a=max(v1,v2); /* retorna v1 caso v1>=v2 ou retorna v2 caso v2>=v1 */
int b;
b=max(max(v1,v2), max(v3,v4));

Na expressão
max(max(v1,v2), max(v3,v4))
temos duas chamadas de uma função aninhadas dentro de uma outra chamada de função. A função max(), definida para dois argumentos, retorna o maior destes argumentos.

---

(A linguagem C permite a definição de “macros” e a “função” max poderia não ser uma função e sim uma macro:
 #define max(A, B) ((A) > (B) ? (A) : (B))

As macros são tratadas antes da compilação e consistem em substituir um trecho de texto do arquivo de entrada pelo texto definido na macro. Veremos como que se define e “expande” as macros mais à frente na disciplina.

---

Quando o fluxo de controle atinge uma chamada de função (o código fonte da função correspondente foi compilado e o código executável da função está disponível):

· primeiro são avaliadas as expressões correspondentes aos argumentos da função,

· é registrado ou salvo o ponto de retorno do fluxo de controle e feito o desvio para o código da função.

· A execução normal de uma função termina com a função retornando o fluxo de controle para o ponto de retorno salvo juntamente com o retorno do valor calculado.

Na linguagem C as expressões correspondentes aos argumentos são calculadas da esquerda para a direita ou da direita para a esquerda?.

Descreva o valor impresso pelo seguinte trecho de programa:
int i=2;
int j=3;
printf(“%d %d\n”, i=3,i+j);

considere o seguinte trecho de programa

int i=3;
int ai[5];
ai[i]=i++;

Qual elemento do arranjo recebe a atribuição? ai[3] ou ai[4]?

ai[i]=++i;

Conforme já discutido, a sintaxe de um comando de atribuição corresponde a (i)uma variável seguida do (ii)símbolo "=" (denominado operador de atribuição), seguido de (iii)uma expressão; Quando o fluxo de controle atinge um comando de atribuição o valor da expressão é calculado e atribuído à variável, além disso o comando de atribuição tem associado a ele um valor que é exatamente o valor da expressão, é isso que permite aparecer em um programa expressões do tipo: v1=v2=3;

Operadores

Constantes, variáveis e chamadas de função podem ser combinadas através de operadores para construir expressões mais complexas. Alguns operadores são bastante intuitivos. Considere o seguinte trecho de programa:

int i=2;
int j=3;
int k;
k=i+j;
O operador "+" na expressão acima corresponde a uma soma de valores do tipo int.

Operadores aritméticos

+ - * / %

O operador  % corresponde ao resto da divisão entre os operandos correspondentes. A avaliação da expressão 11 % 3 resulta no valor 2.

---

Operadores de incremento e decremento

++ (incremento)  --  (decremento)

Exemplos:
int i=3;  /* é atribuido o valor 3 para a variável i,  a expressão vale 3*/
i++; /* é atribuido o valor 4 para a variável i,  a expressão vale 3 */
++i; /* é atribuido o valor 5 para a variável i, a expressão vale 5 */
i--; /* é atribuido o valor 4 para a variável i, a expressão vale 5 */
--i;  /* é atribuido o valor 3 para avariável i, a expressão vale 3 */

int a=0;
int b=0;
int c=a++ + b++;
printf("%d",c); // imprime 0

O operador de incremento (decremento) as vezes é distinguido como operador de incremento prefixado ou ainda pré-incremento (decremento prefixado ou pré-decremento) ou operador de incremento posfixado ou pós-incremento (pós-decremento). O operador prefixado ou posfixado incrementa (decrementa) o operando de forma indistinta, mas o resultado da operação é (i) o valor do operando no caso posfixado ou (ii) o valor do operando incrementado ou decrementado no caso prefixado.

---

Operadores relacionais

== (igual) != (diferente) <  (menor) > (maior)   <= (menor ou igual)  >=  (maior ou igual)

Em alguns casos as expressões podem não ser intuitivas. Esperamos que X==X retorne verdadeiro e X!=X retorne falso, mas quando X corresponde a um double NaN, X!=X retorna verdadeiro! Deve ser ressaltado que a maior parte das especificações da linguagem C prescreve que estes operadores retornem valores do tipo int. Quando a relação especificada não é atendida (FALSO) o valor retornado corresponde a todos os bits em zero (valor ZERO) e quando a relação é atendida (VERDADEIRO) qualquer valor diferente de zero poderá ser retornado. Desta maneira, principalmente quando existem mais de um operador, as expressões não são “intuitivas”; A expressão 10<20<5 poderia ser interpretada como sendo “20 é maior  do que 10 e menor do que 5?”;  na verdade a interpretação corresponde a “O valor diferente de zero retornado pela subexpressão ‘10<20’ é menor do que o valor 5?” O valor mais comum para expressar o valor VERDADEIRO é 1(um) e portanto 10<20<5 corresponde a VERDADEIRO ( o que não é intuitivo!).

---

Operadores Lógicos

Adotamos aqui uma terminologia mais aderente ao livro de Kernighan&Ritchie (K&R). Os operadores lógicos correspondentes a “e” (and), “ou” (or) e “não ou negação” (not/negation) são &&, || e ! de forma tabular

operador lógico	C
e (and)	&&
ou (or)	||
não (not)	!

:

Observe que existem 16 funções binárias. Podemos identificar uma função binária pela sequência de bits. Considere a seguinte tabela, onde 0op0 ->a, 0op1->b, 1op0->c e 1op1->d

	0	1
0	a	b
1	c	d

A linguagem C tem operadores para 2 das 16 funções de duas variáveis lógicas:

abcd	Operador em C
0000
0001	Operador && and
0010
0011
0100
0101
0110
0111	Operador || or
1000
1001
1010
1011
1100
1101
1111

Operadores “Bitzentos”

Os operadores & e | são operadores de bits (A <op> B corresponde a bit 0 de A  <op>  bit 0 de B, bit 1 de A <op> bit 1 de B, ... e assim sucessivamente, e no caso de operandos de 32 bits: bit 31 de A <op> bit 31 de B). São denominados em K&R como “bitwise operators”. De uma maneira “jocosa”poderiamos traduzir “operadores bitentos, bitizeiros ou bitizentos”, estes operadores devem ser aplicados a operandos “integrais” ((all sizes(short/long/etc), signed/unsigned int char), enumeration). Exemplos
Se quisermos saber valor de bits

int estaLigadoBit0, estaLigadoBit1, estaLigadoBit7;
estaLigadoBit0=ii&0x01;
estaLigadoBit1=jj&0x02;
estaLigadoBit7=kk&0x08;

---

Os operadores && e || são operadores no domínio lógico ou no nível das representações convencionais de “verdadeiro(true)” e “falso(false)”...

Deve haver cuidado se houver mistura de operadores de bits e operadores lógicos, pois existem vários possíveis problemas.
X & Y, X | Y -> a expressão X e a expressão Y são avaliadas
X && Y ->Se a expressão X for “false” então a expressão Y não é avaliada
X || Y ->Se a expressão X for “true” então a expressão Y não é avaliada

Se o programador não ficar alerta então ele pode se colocar na posição onde
 “valor diferente de zero” & “valor diferente de zero”
 avalia como “false” sendo que nossa intuição é que deveria ser avaliado como “true”. Problema similar pode ocorrer com os outros operadores.

---

Operador condicional

?:  <exp1>?<exp2>:<exp3>

Exemplos

int i;
int v1=3, v2=4;
i=v1>v2?v1:v2; /* atribui o maior valor à variável i */
---

Operadores de atribuição

=  +=   -= *= /=  %= &=  !=  |= &&= ||=

Toda expressão da forma geral <var1>=<var1><operador><expressão> pode ser escrita na forma
<var1><operador>=<expressão>;

Assim
ii+=jj; equivale a ii=ii+jj;
terminou||=bloqueio; equivale a terminou=terminou || bloqueio;

---

Operador de elencamento (cast)

A linguagem C define várias conversões aritméticas implícitas, e elas funcionam, em geral, de maneira bastante intuitiva. Os operadores em geral são polimórficos (aceitam diferentes tipos). Um operador como o + (mais) pode receber operandos de diferentes tipos e antes da execução da operação o operando “inferior” será promovido (promoted) para o tipo superior. Abaixo um conjunto INFORMAL de regras

Se um dos operados é long double então o outro é convertido para long double
senão se um é double então o outro é convertido para double
senão se um é float então o outro é convertido para float
senão converter char e short para int
então se um dos operandos é long então o outro é convertido para long.

As regras de conversão ficam mais complicadas quando envolvem operandos de tipos  modificados por unsigned. Quando double é convertido para float pode haver truncagem ou arredondamento (depende da plataforma).

---

Conversões explícitas podem ser forçadas através do operador de elencamento (cast)

(nome do tipo ) <expressão>
()  - abre e fecha parênteses

char *p;
p=(char *) malloc(strlen(s)+1); // a função malloc retorna “pointer to void”

int N=25;
double raizN=sqrt((double) N); // a função sqrt declarada em math.h espera um valor double

---

Precedência

O trecho de programa abaixo deve ser evitado por um bom programador. Mas (infelizmente) tal trecho pode ser formulado. O que é impresso pelo trecho abaixo?

int i=2;
int j=(i=3)*i;
printf(“%d”, j);

Considere a tabela abaixo. Operadores na mesma linha têm igual precedência, operadores nas linhas superiores têm precedência sobre operadores nas linhas inferiores:

Existem ainda vários outros tipos de operadores que serão discutidos ao longo da disciplina. Alguns deles poderiam ser discutidos desde já, tais como os operadores de deslocamento (<<, >>, >>>), outros operadores serão discutidos em um contexto bem especializado

Um dos problemas que devem ser enfrentados com expressões envolvendo os tipos double e float são os erros de arredondamento

A linguagem C oferece a função rand() que retorna números pseudo-aleatórios no intervalo de 0 a 32767. A geração de números é condicionada ao estabelecimento de uma “semente” utilizando a função srand(). Se não houver uma “semeadura” a função rand() irá gerar sempre a mesma sequência de números. Exemplo de programa no DEV-C++ sem “semeadura”:

---

#include <stdio.h>

#include <stdlib.h>

int main(int argc, char *argv[]){ 

//rand() retorna um valor pseudo-aleatorio

// entre 0 e 32767

  int cnt;

  for(cnt=0; cnt<10; cnt++)

    printf("%d ", rand()%6+1);

printf("\n");

  system("PAUSE");     

  return 0;

}

---

O programa abaixo utiliza uma representação de números de segundos da hora do computador para semear a geração de números pseudo-aleatórios. Exemplo de programa no DEV-C++que semeia a geração de números pseudo-aleatórios

---

#include <stdio.h>

#include <stdlib.h>

int main(int argc, char *argv[]){

  printf("max rand:%d\n", RAND_MAX);

  time_t timer;    //tipo aritmetico

  timer=time(NULL);//current time

srand(timer);    //ajusta semente

  printf("max rand:%d\n", RAND_MAX);

  //rand() retorna um valor pseudo-aleatorio

// entre 0 e 32767 */

  int cnt;

  for(cnt=0; cnt<10; cnt++)

    printf("%d ", rand()%6+1);

printf("\n");

  system("PAUSE");     

  return 0;

}

---

Ambos os programas simulam o lançamento de um dado (valores de 1 a 6) por 10 vezes. O estilo acima é mais inteligível do que o seguinte estilo (que economiza uma variável):
srand(time(NULL));    //ajusta semente

Vários exercícios podem ser imaginados e a verificação da correção dos resultados do programa pode ser verificada em função de escolher problemas que tenham solução analítica. Exemplo: não é muito complicado derivar analiticamente que a probabilidade do valor de um primeiro dado de seis valores ser maior do que o valor de um segundo dado é 5/12. Escreva um programa em C que faz um certo número de lançamentos de dois dados e calcula o percentual de vezes que o primeiro dado foi maior que o segundo. Neste elo uma sugestão de solução (não olhe antes de tentar fazer!).

A sugestão apresentada “gasta” os números pseudo-aleatórios, uma alternativa é “economizar” os números:

v2=rand()%6+1;

for(cntLanca=0; cntLanca<totalLanca; cntLanca++){

   v1=v2;

   v2=rand()%6+1;

    if(v1>v2) cntMaior++; 

}

Verifique que gerar dois números e compará-los dá um resultado similar a gerar apenas um número e compará-lo com o número anterior.

Depois do aprendizado do materia de “Arranjos” faça um programa que caminha de forma “pseudo-aleatória” em uma grade na forma 24x80. Neste elo uma sugestão de solução.

A linguagem C define várias diferentes funções, exemplificadas abaixo:

---

sin(x) sine of x

cos(x) cosine of x

tan(x) tangent of x

asin(x) sin inverse (x) in range [-pi/2,pi/2], x in [-1,1].

acos(x) cos inverse (x) in range [0,pi], x in [-1,1].

atan(x) tan inverse (x) in range [-pi/2,pi/2].

atan2(y,x) tan inverse (y/x) in range [-pi,pi].

sinh(x) hyperbolic sine of x

cosh(x) hyperbolic cosine of x

tanh(x) hyperbolic tangent of x

exp(x) exponential function e^x

log(x) natural logarithm ln(x), x>0.

log10(x) base 10 logarithm, x>0.

pow(x,y) x^y. A domain error occurs if x=0 and y<=0, or if x<0 and y is not an integer.

sqrt(x) square root of x, x>=0.

ceil(x) smallest integer not less than x, as a double.

floor(x) largest integer not greater than x, as a double.

fabs(x) absolute value of x

ldexp(x,n) x*2^n

frexp(x, int *ip) splits x into a normalized fraction in the interval [1/2,1) which is returned, and a power of 2, which is stored in *exp. If x is zero, both parts of the result are zero.

modf(x, double *ip) splits x into integral and fractional parts, each with the same sign as x. It stores the integral part in *ip, and returns the fractional part. Exemplo:

double d=123.456; double inteira, frac;
frac=modf(d, &inteira);
printf(“numero:%e parte inteira:%e parte fracionaria:%e\n”, d, inteira, frac);

fmod(x,y) floating-point remainder of x/y, with the same sign as x. If y is zero, the result is implementation-defined.