Programação avançada com C

1Programação Avançada com C

© Pedro Guerreiro 1994-2002

Programação Avançada com CProgramaçãoAvançada com C

por

Pedro [email protected]

http://ctp.di.fct.unl.pt/~pg/

Departamento de InformáticaFaculdade de Ciências e Tecnologia

Universidade Nova de Lisboa

1994-2002



Primeira parte: Introdução

1. A linguagem de programação C.2. Funções. A função main.

3. As instruções do C.

4. Entradas e saídas.

5. Tipos de dados.

6. Variáveis.

7. Operadores.

8. Vectores.

9. Operadores ++ e ––

10. Operadores de afectação.

11. Ficheiros.

12. Cadeias de caracteres.

13. Ciclo de leitura.

14. Busca e ordenação



Características do C• É uma linguagem pequena (49 páginas para

o manual de referência + 18 páginas para a biblioteca)

• É uma linguagem com tipos frouxos (loosely typed language).

• Tem todas as estruturas de controlo modernas: if-else, while-do, do-while, for, case (switch).

• Trabalha com caracteres, números inteiros e números reais.

• Dispõe de construtores de tipos para quadros e registos (estruturas).

• Serve para manipular objectos ao nível do bit.

• Implementa apontadores muito versáteis.• Permite a compilação separada.



Bibliografia1. Kernighan, Ritchie, The C Programming

Language (ANSI C), 2.ª edição, Prentice-Hall (1988).

2. Hutchison, Just, Programming Using The C Language, McGraw-Hill (1988).

3. Müldner, Steele, C as a Second Language for Native Speakers of Pascal, Addison-Wesley (1988).

4. Schildt, C: The Complete Reference,McGraw-Hill (1987).

5. Schildt, C: Advanced C, 2.ª edição, McGraw-Hill (1988).

6. Galland, Le Langage C: Pratique etEnvironnement, Dunod (1989).

7. Dewhurst, Stark, Programming in C++,Prentice Hall (1989).

8. Guerreiro, Elementos de Programação com C, Europa-América (1991), reeditado em 2001 pela FCA.



O primeiro programa em C

K&R:“The first program to write is the same for all languages:

Print the wordshello, world

”

K&R:“The first program to write is the same for all languages:

Print the wordshello, world

”

#include <stdio.h>main(){

printf("Olá, pessoal\n");}

#include <stdio.h>main(){

printf("Olá, pessoal\n");}

Versão Lisboa 1991:



Componentes do primeiro programa#include <stdio.h>

main(){printf("Olá, pessoal\n");}

printf

"Olá, pessoal\n"

'\n'

Directiva para “incluir” o ficheiro stdio.h.

stdio.hFicheiro que contém informação sobre abiblioteca de IO do C.

A função main. Todos os programas C têm uma.

Uma função de biblioteca que serve para escrever coisas.

Uma cadeia de caracteres.

A representação do carácter newline.



Problema dos pontos na Fórmula 1

Escrever um programa para calcular onúmero de pontos que ganha um piloto nocampeonato mundial de fórmula 1, ao chegar ao fim num grande prémio. O programa pergunta em que lugar chegou o piloto eresponde afixando o número de pontos.

1.º 10 pontos2.º 6 pontos3.º 4 pontos4.º 3 pontos5.º 2 pontos6.º 1 ponto7.º em diante 0 pontos



Problema dos pontos (1.ª solução)

/* Pontos numa corrida de F1; primeira versão */#include <stdio.h>

int main (){

int place;

printf("Qual é o lugar? ");scanf("%d", &place);

if (place == 1)printf("Ganhou 10 pontos.\n");

else if (place == 2)printf("Ganhou 6 pontos.\n");




else if (place == 6)printf("Ganhou 1 ponto.\n");

elseprintf("Não ganhou pontos.\n");

return 0;}



Os comentáriosAparecem entre e

Exemplos:/* Pontos numa corrida de F1; primeira versão

*//* Escrito por Pedro Guerreiro *//* Data: 91.03.19 *//* Modificado em 91.03.22, por PG */

Habilidades com comentários:

/************************************************ ** *** * * ** * * * * ** * *** **** *** * ** ** ** * * * * * * * ** * * ** * ***** * * * * * * * ** * * * * * * * * * * ** *** *** **** *** * * * ** ************************************************/

/* */



A função main

int main (){

...

return 0;}

int main (){

...

return 0;}

int main ()int main ()

A função main não tem parâmetros e devolve um valor inteiro.

return 0;return 0;

Convencionalmente a função main devolve0 (zero), quando tudo corre bem!



O tipo int

int main (){

int place;

...}

int main (){

int place;

...}

int main ()int main ()

A função main devolve um número inteiro.

int place;int place;

place é uma variável inteira.

O tipo int representa os números inteiros entre -32768 e 32767, nos computadores de 16 bits, e entre -2147483648 e 2147483647,nos computadores de 32 bits.



A função printfint main (){

int place;

printf("Qual é o lugar? ");...


...}

int main (){

int place;

printf("Qual é o lugar? ");...


...}

printf("Qual é o lugar? ");printf("Qual é o lugar? ");

A função printf escreve cadeias decaracteres (e outras coisas também) noecrã do terminal.As cadeias de caracteres vêm entre aspas.\n é uma sequência de escape que representa o carácter newline.Para poder usar a função printf, é preciso incluir o ficheiro <stdio.h>.

printf("Ganhou 10 pontos.\n");printf("Ganhou 10 pontos.\n");



A função scanf

int main (){

int place;


...}

int main (){

int place;


...}

scanf("%d", &place);scanf("%d", &place);

A função scanf “lê” números, caracteres, e cadeias de caracteres digitados noteclado do terminal."%d" é uma cadeia de formato, que contémo especificador de conversão %d,indicando que a função scanf está àespera de ler um número inteiro decimal.A variável que vai receber o número digitado tem que ser precedida pelo operador &.Para poder usar a função scanf, é preciso incluir o ficheiro <stdio.h>.



A igualdade ==

int main (){

...if (place == 1)...

else if (place == 2)...

}

int main (){

...if (place == 1)...

else if (place == 2)...

}

== é o operador relacional de igualdade

expr1 == expr2

Vale 1 (um), se o valor de expr1 é igual aode expr2; vale 0 (zero), se o valor de expr1é diferente do valor de expr2.

!= é o operador relacional de desigualdade

place == 1place == 1

NB: == é diferente de =



A instrução if-else

...if (place == 1)printf("Ganhou 10 pontos.\n");







...}

...if (place == 1)printf("Ganhou 10 pontos.\n");







...}

if (expressão)instrução_1

elseinstrução_2

Avalia-se a expressão; se tiver um valor diferente de 0 (zero) executa-se ainstrução_1; se tiver um valor igual a 0 (zero) executa-se a instrução_2.



Instruções if-else em cascata

if (expressão_1)instrução_1

else if (expressão_2)instrução_2

elseinstrução_3















Dispor o código assim:



A instrução return

int main (){

...return 0;

}

int main (){

...return 0;

}

return 0;return 0;

return expressão;

Avalia-se a expressão; logo a seguir,termina a função; o valor calculado pela função é o valor que resultou da avaliação da expressão.



Problema dos pontos (2.ª solução)#include <stdio.h>

int main (){

int place;int pts;

printf("Qual é o lugar? ");scanf("%d", &place);if (place == 1)pts = 10;

else if (place == 2)pts = 6;





elsepts = 0;

if (pts > 1)printf("Ganhou %d pontos.\n", pts);

else if (pts == 1)printf("Ganhou 1 ponto.\n");


return 0;}



Declaração de variáveis

int main (){

int place;int pts;

...}

int main (){

int place;int pts;

...}

int place;int pts;int place;int pts;

int place, pts;int place, pts;

As variáveis têm que ser declaradas antes de ser usadas.

Uma declaração especifica um tipo e onome de uma variável:

ou de uma lista de variáveis:

Nota: Normalmente é preferível declarar uma variável decada vez.



Instrução de afectação =int main (){

int place;int pts;...if (place == 1)pts = 10;


...}

int main (){

int place;int pts;...if (place == 1)pts = 10;


...}

E1 = E2

Avalia-se a expressão E2; o resultado passa a constituir o valor de E1.

A afectação é uma expressão. O valor de E1 = E2 é o valor afectado a E1.

O operador = associa da direita para aesquerda. Logo:E1=E2=E3 é o mesmo que E1=(E2=E3)



A função printfcom vários argumentos (1)

...if (pts > 1)printf("Ganhou %d pontos.\n", pts);

else...

}


else...

}

printf("Ganhou %d pontos.\n", pts);printf("Ganhou %d pontos.\n", pts);

Primeiro argumento:

Há um especificador para cada argumento suplementar.

"Ganhou %d pontos.\n""Ganhou %d pontos.\n"

É a cadeia de formato. Contém caracteres que vão ser escritos tal e qual:

"Ganhou • pontos.\n""Ganhou • pontos.\n"

e especificadores de conversão:

%d%d Conversão inteira decimal



A função printfcom vários argumentos (2)

Exemplos:

printf("%d", pts);printf("%d", pts);

printf("Lugar: %d. Pontos: %d.\n",place, pts);

printf("Lugar: %d. Pontos: %d.\n",place, pts);

A cadeia de formato reduz-se à conversão:

O número de parâmetros suplementares é arbitrário:

printf("Ganhou %d pontos, porque ""ficou em %d.º lugar.\n",pts, place);

printf("Ganhou %d pontos, porque ""ficou em %d.º lugar.\n",pts, place);

Duas cadeias constantes de seguida são concatenadas:

Pode especificar-se a largura do campo:

printf("%8d %5d", pts, place);printf("%8d %5d", pts, place);



Operadores relacionais


else...

}


else...

}

>> maior que.

>=>= maior ou igual.

<< menor que.

<=<= menor ou igual.

e ainda:

==== igual.

!=!= diferente.



Problema dos pontos (3.ª solução)

...printf("Qual é o lugar? ");scanf("%d", &place);switch (place) {case 1:

pts = 10;break;

case 2:pts = 6;break;





default:pts = 0;break;

}if (pts > 1)printf("Ganhou %d pontos.\n", pts);

else ...}



A instrução switch

switch (expressão) {case expr-const: instruçõescase expr-const: instruções...case expr-const: instruçõesdefault: instruções

}

A execução da instrução switch começapela avaliação da expressão; se um doscasos tem um valor igual ao da expressão, a execução da instruçãoswitch continua pelas instruçõesdesse caso; se nenhum dos casos tiverum valor igual e houver um casodefault, então a instrução continuapelas instruções do caso default; senão houver, não acontece mais nada.



A instrução break

break;

A execução da instrução break fazterminar a execução da instrução switch(ou while, ou for, ou do) de que ainstrução break faz parte.

Usa-se muito com instruções switch,para evitar que se passe das instruçõesde um caso para as instruções do caso seguinte.

switch (expressão) {case expr-const_1: instrução_1_1;

...;break;

case expr-const_2: instrução_2_1...;break;

...default: instrução_0_1

...;break;

}



Definição de funçõesint points (int place){

switch (place) {case 1:

return 10;case 2:

return 6;case 3:

return 4;case 4:

return 3;case 5:

return 2;case 6:

return 1;default:

return 0;}

}

points é uma função inteira com uma variável (parâmetro) inteira, denotada pelo identificador place.

tipo_de_retorno nome_da_função(decl.parâmetros)

{declaraçõesinstruções

}

tipo_de_retorno nome_da_função(decl.parâmetros)

{declaraçõesinstruções

}

Forma da definição de uma função:



Utilização de uma função declarada#include <stdio.h>

int points (int);

main (){

int place;int pts;


pts = points(place);

if (pts > 1)printf("Ganhou %d pontos.\n", pts);

else if (pts == 1)printf("Ganhou 1 ponto.\n");


return 0;}

int points (int place){

switch (place) {case 1:

return 10;...default:

return 0;}

}

Aqui place é o parâ-metro da função; não confundir com a variávelplace da função main.

Aqui place é o parâ-metro da função; não confundir com a variávelplace da função main.

Chamada da função; avariável place é oargumento.

Chamada da função; avariável place é oargumento.

protótipo da função points.protótipo da função points.



Variantes para a função points


switch (place) {case 1: case 2:

return 14 - 4 * place;case 3: case 4: case 5: case 6:

return 7 - place;default:

return 0;}

}


switch (place) {case 1: case 2:

return 14 - 4 * place;case 3: case 4: case 5: case 6:

return 7 - place;default:

return 0;}

}


if (place <= 2)return 14 - 4 * place;

else if (place <= 6)return 7 - place;

elsereturn 0;

}


if (place <= 2)return 14 - 4 * place;

else if (place <= 6)return 7 - place;

elsereturn 0;

}

Instrução switch com casos múltiplos:

Instrução if-else (3 ramos):



Operadores aritméticos

**

%%

//

––

++

multiplicação.

divisão (quociente).

adição.

resto da divisão inteira.

subtracção.

Não há potenciação!

Operadores com a mesma priori-dade (* / %, + -) avaliam-se da esquerda para a direita.

A divisão ( / ) de dois números inteiros é a divisão inteira.



Uma função para calcular potências

int ipow(int, int);int ipow(int, int);

int ipow (int base, int n){if (n == 0)return 1;

elsereturn base * ipow (base, n-1);

}

int ipow (int base, int n){if (n == 0)return 1;

elsereturn base * ipow (base, n-1);

}

Protótipo:

Declaração:

O C aceita funções recursivas (funções quese chamam a elas próprias, directamente ou indirectamente).

int f(int x){

...g(...);...;

}

int f(int x){

...g(...);...;

}

int g(int x){

...f(...);...;

}

int g(int x){

...f(...);...;

}

Recursividade indirecta:



A expressão condicional

Outra maneira (melhor) de declarar a função ipow:

int ipow (int base, int n){return n == 0 ?

1 : base * ipow(base, n - 1);

}

int ipow (int base, int n){return n == 0 ?

1 : base * ipow(base, n - 1);

}

Expressão condicional:

expr_1 ? expr_2 : expr_3

Avalia-se expr_1; se der dife-rente de 0, avalia-se expr_2; seder 0 avalia-se expr_3; o valor da expressão condicional é ovalor de expr_2 ou de expr_3,consoante a que tiver sido avaliada.



Outras funções elementares

int max(int, int);int min(int, int);int ntrl(int);int pstv(int);

int max(int, int);int min(int, int);int ntrl(int);int pstv(int);

int max(int x, int y){return x >= y ? x : y;

}

int min(int x, int y){return x <= y ? x : y;

}

int ntrl(int x){return x >= 0 ? x : 0;

}

int pstv(int x);{return x >= 1 ? x : 1;

}

int max(int x, int y){return x >= y ? x : y;

}

int min(int x, int y){return x <= y ? x : y;

}

int ntrl(int x){return x >= 0 ? x : 0;

}

int pstv(int x);{return x >= 1 ? x : 1;

}



Exemplos de aplicação

int points (int place){return place <= 2 ?

14 - 4 * place :ntrl (7 - place);

}

int points (int place){return place <= 2 ?

14 - 4 * place :ntrl (7 - place);

}

int min3 (int x, int y, int z){return min(min(x, y), z);

}

int min3 (int x, int y, int z){return min(min(x, y), z);

}

int max3 (int x, int y, int z){return max(max(x, y), z);

}

int max3 (int x, int y, int z){return max(max(x, y), z);

}

int mid (int x, int y, int z){return x + y + z -

min3(x, y, z) -max3(x, y, z);

}

int mid (int x, int y, int z){return x + y + z -

min3(x, y, z) -max3(x, y, z);

}



Os inteiros long

Os inteiros long são pelo menos tão“extensos”como os inteiros int.Normalmente vão de -2147483648 a 2147483647, nos computadores de 32 bits.

Problema: Fazer um programa para calcular potências que possam ser números grandes.

#include <stdio.h>

long lpow(long, int);

main(){

long x;int i;printf("Indique a base e o expoente: ");scanf("%ld%d", &x, &i);printf("%ld elevado a %d vale %ld\n",

x, i, lpow(x, i));return 0;

}

long lpow(long base, int n){

return n ? base * lpow(base, n-1) : 1;}



Misturando int e long

Quando, numa operação aritmética, um dosoperando é int e o outro é long, o ope-rando int é promovido a long antes da operação.A afectação de um int a um long faz-se“naturalmente”.A afectação de um long a um int faz-sedesprezando os bits mais significativos (eportanto o resultado pode ser inesperado sealguns desses bits estiverem a 1).

long x;int i;printf("Um long: ");scanf("%ld", &x);i = x;printf("O int : %d\n",

i);

Um long: 186O int : 186

Um long: 186O int : 186

Um long: 523214O int : -1074

Um long: 523214O int : -1074

long x;int i;printf("Um int: ");scanf("%d", &i);x = i;printf("O long : %d\n",

i);

Um int: 452O long: 452

Um int: 452O long: 452

Um int: 214523O long: 32767

Um int: 214523O long: 32767



Os operadores lógicos

&&&& conjunção (“e”).

|||| disjunção (“ou”).

!! negação (“não”).

Os operadores && e || avaliam-se da esquerda para a direita e a avaliação páralogo que o resultado da expressão fica determinado:

x && y

x || y

Avalia-se x; se der 0 a expressão vale 0; se der diferente de 0 avalia-se y e o valor da expressão é 0 se o valor de y for 0 e 1 se não.

Avalia-se x; se der diferente de 0 aexpressão vale 1; se der 0 avalia-se y e ovalor da expressão é 0 se o valor de y for0 e 1 se não.



Utilização dos operadores lógicos

int isbtwn(int x, int a, int b){

return a <= x && x <= b;}

int isbtwn(int x, int a, int b){

return a <= x && x <= b;}

void greetint(int h){printf(isbtwn(h, 4,11) ? "Bom dia" :isbtwn(h,12,19) ? "Boa tarde" :

"Boa noite");}

void greetint(int h){printf(isbtwn(h, 4,11) ? "Bom dia" :isbtwn(h,12,19) ? "Boa tarde" :

"Boa noite");}

int isleap(int y){return y%4 == 0 && y%100 != 0 ||

y%400 == 0;}

int isleap(int y){return y%4 == 0 && y%100 != 0 ||

y%400 == 0;}

int daysof(int y){return 365 + isleap(y);

}

int daysof(int y){return 365 + isleap(y);

}



Simplificação das expressõesrelacionais

Em vez de x == 0 pode usar-se !x.Em vez de x != 0 pode usar-se x.

int isleap(int y){return !(y%4) && y%100 ||!(y%400);

}

int isleap(int y){return !(y%4) && y%100 ||!(y%400);

}

int ipow (int base, int n){return n ?

base * ipow(base, n-1) :1;

}

int ipow (int base, int n){return n ?

base * ipow(base, n-1) :1;

}

Exemplos:



Precedência dos operadores

()! + -* / %+ -< <= > >=== !=&&||?:=

Operadores Sentido

a)

a) () chamada de função.b) + e - unários.

Nota: esta tabela está incompleta, porque há outros operadores em C que ainda não foram apresentados.

b)



O tipo double

Os números reais (floating point) em Caparecem em dois tipos: float e double.

As funções matemáticas da biblioteca usamdouble.

O tipo das constantes floating point é double.

Exemplos de constantes double:

3.1415926531e-210E100.1e-1

Operações aritméticas:

** //

––++

multiplicação. divisão.

adição. subtracção.42Programação Avançada com C


Lendo e escrevendo double

double x;...printf("Valor de x = ");scanf("%lf", &x);

%lf especificador de conversão paradouble, na função scanf.

%lf especificador de conversão paradouble, na função scanf.

...printf("O quadrado de x é %f\n",

x * x);

%f especificador de conversão paradouble, na função printf. Escrito na forma [-]m.dddddd.

%f especificador de conversão paradouble, na função printf. Escrito na forma [-]m.dddddd.

%e especificador de conversão paradouble, na função printf. Escrito na forma [-]m.dddddde±xx.

%e especificador de conversão paradouble, na função printf. Escrito na forma [-]m.dddddde±xx.

...printf("O quadrado de x é %e\n",

x * x);



Largura do campo e precisão#include <stdio.h>main(){

double x;printf("Valor de x = ");scanf("%lf", &x);printf("O quadrado de x é %f\n", x * x);printf("O quadrado de x é %e\n", x * x);printf("O quadrado de x é %6.2f\n", x * x);printf("O quadrado de x é %6.2e\n", x * x);

}

Valor de x = 12.25O quadrado de x é 150.062500O quadrado de x é 1.500625e+02O quadrado de x é 150.06O quadrado de x é 1.50e+02

Valor de x = 12.25O quadrado de x é 150.062500O quadrado de x é 1.500625e+02O quadrado de x é 150.06O quadrado de x é 1.50e+02

Valor de x = 0.182O quadrado de x é 0.033124O quadrado de x é 3.312400e-02O quadrado de x é 0.03O quadrado de x é 3.31e-02

Valor de x = 0.182O quadrado de x é 0.033124O quadrado de x é 3.312400e-02O quadrado de x é 0.03O quadrado de x é 3.31e-02

Valor de x = 1024O quadrado de x é 1048576.000000O quadrado de x é 1.048576e+06O quadrado de x é 1048576.00O quadrado de x é 1.05e+06

Valor de x = 1024O quadrado de x é 1048576.000000O quadrado de x é 1.048576e+06O quadrado de x é 1048576.00O quadrado de x é 1.05e+06



O ficheiro <math.h>

double sin(double);double cos(double);double tan(double);double asin(double);double acos(double);double atan(double);

double sinh(double);double cosh(double);double tanh(double);

double exp(double);double log(double);double log10(double);double pow(double, double);double sqrt(double);

double ceil(double);double floor(double);

double fabs(double);...

a)b)

a) ceil(x) é menor inteiro >= x, em double.

b) floor(x) é o maior inteiro <= x, em double.



Conversão entre inteiros e reais

A conversão de int ou long para double faz-se “naturalmente”.A conversão de double para int ou long faz-se desprezando a parte decimal. Se oresultado não for representável, não se sabe oque acontece (é um erro de programação).É melhor assinalar a conversão de real para inteiro explicitamente, usando a função ceil,a função floor, ou os operadores deconversão (int) ou (long).

Valor de x = 34.7ceil(x) = 35.000000floor(x) = 34.000000(int) x = 34

Valor de x = 34.7ceil(x) = 35.000000floor(x) = 34.000000(int) x = 34

Valor de x = -12.4ceil(x) = -

12.000000floor(x) = -

13.000000(int) x = -12

Valor de x = -12.4ceil(x) = -

12.000000floor(x) = -

13.000000(int) x = -12

printf("Valor de x = ");scanf("%lf", &x);printf("ceil(x) = %f\n", ceil(x));printf("floor(x) = %f\n", floor(x));printf("(int) x = %d\n", (int) x);

Exemplo:



Exercícios (1)

O factorial de um número natural n, denotado por n! pode ser definido recursivamente assim:n! = n * (n-1)!, se n>0;0! = 1.

Para números grandes, a função de Sterling,definida a seguir, dá uma boa aproximação do factorial:sterling(n) = 2 * š * n * (n/e)

Pretende-se um programa C que aceite umnúmero inteiro do terminal e afixe o seufactorial e o seu número de sterling, para comparar.

n

Sugestões: o arcotangente de 1.0 é š/4.e é a exponencial de 1.0.



Exercícios (2)

A área de um triângulo é dada pela seguinte expressão:s * (s - a) * (s - b) * (s - c)

onde s é o semiperímetro e a, b, e c são asmedidas dos lados.

1. Pretende-se um programa que, dadas asmedidas dos lados, calcule a área dotriângulo.

A distância entre dois pontos de coorde-nadas (x1, y1) e (x2, y2) é dada pela seguinte expressão:

(x1 - x2) + (y1 - y2)2 2

2. Pretende-se um programa que, dados os três vértices por meio das suas coordenadas, calcule a área do triângulo.



Problema da classificação

2.º subproblema:Escrever um programa para registar aordem de chegada dos pilotos.

3.º subproblema:Escrever um programa para registar o tempo de cada piloto, à chegada à meta.

Problema:Escrever um programa para registar achegada dos pilotos, juntamente com o tempo, e para afixar a classificação final,ordenada, com número, tempo, média(em km/h e mph), e pontos conquistados.

Subproblemas:

1.º subproblema:Escrever uma função para dar o númerode pontos obtidos por um piloto, dado olugar em que ficou (já está).



QuadrosQuadros:

Sequências de valores do mesmo tipo,acessíveis por indexação.

Vectores: quadros unidimensionais.Matrizes: quadros bidimensionais.

Declaração de um vector para registar achegada de 26 corredores:

int arrivals[26];int arrivals[26];

Em C, os índices começam em 0. Por vezes,convém ocupar o vector só a partir da posição 1: int arrivals[27];

/* índice 0 não utilizado */

tipo nome [dimensão];tipo nome [dimensão];

Forma da declaração de um vector:



Constantes simbólicas

Directiva #define:

#define MAX_ARRIVALS 26int arrivals[MAX_ARRIVALS + 1];

#define MAX_ARRIVALS 26int arrivals[MAX_ARRIVALS + 1];

#define pi 3.141592653#define e 2.718281828

double sterling(int n){return sqrt(2 * pi * n) *

pow(n / e, n);}

#define pi 3.141592653#define e 2.718281828

double sterling(int n){return sqrt(2 * pi * n) *

pow(n / e, n);}

Outros exemplos:

As directivas (#define, #include) são interpretadas pelo preprocessador.



Registando a ordem de chegada#include <stdio.h>

#define MAX_ARRIVALS 26int arrivals [MAX_ARRIVALS + 1];

/* índice 0 não utilizado */int n_arrivals;int get_arrivals (void);

main (){

n_arrivals = get_arrivals ();printf("Número de chegadas: %2d\n"

"Número de desistentes: %2d\n",n_arrivals, MAX_ARRIVALS -

n_arrivals);return 0;

}

int get_arrivals (void){

int i;int number;for (i = 1; i <= MAX_ARRIVALS; ++i){printf("%2d.º lugar (0 p/ terminar): ",

i);scanf("%d", &number);if (!number)break;

arrivals [i] = number;}

return i - 1;}



Funções sem parâmetros

Protótipo:

Chamada:

int get_arrivals (void);int get_arrivals (void);

n_arrivals = get_arrivals ();n_arrivals = get_arrivals ();

Noutras circunstâncias, o valor da função poderia ser descartado:

...;get_arrivals ();...;

...;get_arrivals ();...;

Se nunca quiséssemos o resultado (ou não houvesse mesmo um resultado para devolver), o tipo da função seria void:

void get_arrivals (void);void get_arrivals (void);



Concatenação de cadeias constantesmain (){

n_arrivals = get_arrivals ();printf("Número de chegadas: %2d\n"

"Número de desistentes: %2d\n" ,n_arrivals, MAX_ARRIVALS -

n_arrivals);return 0;

}

A justaposição de cadeias constantes indica a sua concatenação.Usa-se para dispor o código de maneira mais agradável.



A instrução for







for (expr_1; expr_2; expr_3)instrução

expr_1 : expressão de inicialização.exp2_2 : expressão de continuação.expr_3 : expressão de progressão.

1. Avalia-se expr_1;2. Avalia-se expr_2; se der 0, a instrução

for termina. Se não:3. Executa-se a instrução;4. Avalia-se a expr_3;5. Recomeça-se pelo ponto 2.



Exemplos de instruções for

Problema: listar as potências de 2, cominteiros long.

#include <stdio.h>


main(){int i;for (i = 1; i <= 31; i = i + 1)printf("%ld\n", lpow(2, i));

return 0;}

long lpow(long base, int n){long p;int i;p = 1;for (i = 1; i <= n; i = i + 1)p = p * base;

return p;}

#include <stdio.h>


main(){int i;for (i = 1; i <= 31; i = i + 1)printf("%ld\n", lpow(2, i));

return 0;}

long lpow(long base, int n){long p;int i;p = 1;for (i = 1; i <= n; i = i + 1)p = p * base;

return p;}

Nota: Isto não fica assim!56Programação Avançada com C


A instrução composta

Uma instrução composta, ou bloco, éformada por uma lista de instruções colocadas entre chavetas { e }. Usa-sequando a sintaxe requer uma instrução e a lógica do programa requer várias.

for (i = 1; i <= MAX_ARRIVALS; ++i){printf("%2d.º lugar (0 p/ terminar): ", i);scanf("%d", &number);if (!number)break;




Exemplos:

if (number > MAX_NUMBER){printf("ERRO: Número inválido.\n");i = i - 1;

}else

arrivals [i] = number;

if (number > MAX_NUMBER){printf("ERRO: Número inválido.\n");i = i - 1;

}else




A instrução break(para terminar ciclos)

Normalmente, a instrução for terminaquando a condição de continuação dá 0. “Excepcionalmente”, podemos antecipar ofim, com a instrução break.





Exemplo:

Nota:!number é o idioma C para number == 0.



Os operadores de incrementação

for (i = 1; i <= MAX_ARRIVALS; ++i ){printf("%2dº. lugar (0 p/ terminar): ", i);scanf("%d", &number);if (!number)break;


for (i = 1; i <= MAX_ARRIVALS; ++i ){printf("%2dº. lugar (0 p/ terminar): ", i);scanf("%d", &number);if (!number)break;


++n vale n+1, e incrementa n.

n++ vale n, e incrementa n.

x = 5;printf("%d\n", x);printf("%d\n", ++x);printf("%d\n", x);

566

566

x = 5;printf("%d\n", x);printf("%d\n", x++);printf("%d\n", x);

556

556



Os operadores de decrementação

––n vale n-1, e decrementa n.

n–– vale n, e decrementa n.

Exemplo:#define MAX_NUMBER 39...if (number > MAX_NUMBER)

{printf("ERRO: Número inválido.\n");––i;

}else


#define MAX_NUMBER 39...if (number > MAX_NUMBER)

{printf("ERRO: Número inválido.\n");––i;

}else


x = 5;printf("%d\n", x);printf("%d\n", ––x);printf("%d\n", x);

544

544

x = 5;printf("%d\n", x);printf("%d\n", x––);printf("%d\n", x);

554

554



A instrução while

while (expr)instrução

expr: expressão de continuação.1. Avalia-se expr; se der 0, a

instrução while termina. Se não:2. Executa-se a instrução;3. Recomeça-se pelo ponto 1.

long lpow(long base, int n){long p;int i;p = 1;i = 1;while (i <= n){p = p * base;++i;

}return p;

}

long lpow(long base, int n){long p;int i;p = 1;i = 1;while (i <= n){p = p * base;++i;

}return p;

}

Exemplo:



Exemplos de instruções while


long p;int i;p = 1;i = n;while (i––)p = p * base;

return p;}


long p;int i;p = 1;i = n;while (i––)p = p * base;

return p;}

int placeof(int number){

int i;i = 1;while (i <= n_arrivals &&

number != arrivals [i])++i;

return i <= n_arrivals ? i : 0;}


int i;i = 1;while (i <= n_arrivals &&

number != arrivals [i])++i;

return i <= n_arrivals ? i : 0;}

Mais uma versão para a potenciação:

Uma função para dar o lugar em que chegouum concorrente (ou 0 se não tiver chegado):

i = n_arrivals;while (i >= 1 && number != arrivals [i])––i;

return i;

Ou:

Notar aavaliaçãosequencialdooperador&&



Equivalência entre for e whilewhile (expr)instrução

for ( ; expr; )instrução

for (expr_1;expr_2;expr_3)

instrução

expr_1;while (expr_2){instruçãoexpr_3;}


int i;for (i = 1;

i<=n_arrivals && number != arrivals [i];++i)

;return i <= n_arrivals ? i : 0;

}


int i;for (i = 1;

i<=n_arrivals && number != arrivals [i];++i)

;return i <= n_arrivals ? i : 0;

}


int i;for (i = n_arrivals;

i >= 1 && number != arrivals [i];––i)

;return i;

}


int i;for (i = n_arrivals;

i >= 1 && number != arrivals [i];––i)

;return i;

}



A instrução vazia

;



Incrementação do índiceint get_arrivals (void){

int i;int number;i = 0;while (i < MAX_ARRIVALS){printf("%2d.º lugar (0 para terminar): ",

i + 1);scanf("%d", &number);if (!number)break;

if (number > MAX_NUMBER)printf("ERRO: Número inválido.\n");

elsearrivals [++i] = number;

}return i;

}

int get_arrivals (void){

int i;int number;i = 0;while (i < MAX_ARRIVALS){printf("%2d.º lugar (0 para terminar): ",

i + 1);scanf("%d", &number);if (!number)break;

if (number > MAX_NUMBER)printf("ERRO: Número inválido.\n");

elsearrivals [++i] = number;

}return i;

}

É assim porque decidimos não usar a posição 0. Seusássemos ficava:

arrivals [++i] = number;

arrivals [i++] = number;



Registando os tempos (1)

#include <stdio.h>

#define MAX_NUMBER 39long times[MAX_NUMBER + 1];

long millisecs(int, int, int, int);int get_times(void);void display_times(void);

main (){

int n_cars;n_cars = get_times();printf("Números de carros que terminaram: "

"%d\n", n_cars);printf("\n");display_times();

}

long millisecs(int hrs, int mins, int secs, int mils)

{return (((hrs * 60L) + mins) * 60L

+ secs) * 1000L + mils;}...

Constantes long



Registando os tempos (2)...int get_times(void){

int n = 0;int number;int hrs;int mins;int secs;int mils;for (;;){printf("Número do carro (0 p/ terminar): ");scanf("%d", &number);if (!number)break;

if (number > MAX_NUMBER){printf("ERRO: número inválido.\n");continue;

}if (times[number]){

printf("ERRO: número repetido.\n");continue;

}printf("Tempo (h m s mil): ");scanf("%d%d%d%d",

&hrs, &mins, &secs, &mils);times[number] =

millisecs(hrs, mins, secs, mils);++n;

}return n;

}...



Inicialização na declaração

int get_times(void){

int n = 0;int number;...

}


long p = 1;int i;for (i = 1; i <= n; i = i + 1)p = p * base;

return p;}


long p = 1;int i;for (i = 1; i <= n; i = i + 1)p = p * base;

return p;}

Outro exemplo:

As variáveis externas (isto é,declaradas fora das funções) são automaticamente inicializadas a 0.

As variáveis externas (isto é,declaradas fora das funções) são automaticamente inicializadas a 0.

É o caso do vector times.



Os operadores de afectação

+=+= x += y x = x + y

-=-= x -= y x = x - y

*=*= x *= y x = x * y

/=/= x /= y x = x / y

%=%= x %= y x = x % y

long lpow(long base, int n){long p = 1;int i = n;while (i––)p *= base;

return p;}

long lpow(long base, int n){long p = 1;int i = n;while (i––)p *= base;

return p;}

Exemplo:



Ciclos infinitos

for (;;) while (1)(ou

for (;;){...if (...)break;

...}

for (;;){...if (...)return ...;

...}

)

Saída por break:

Saída por return:



A instrução continue

for (;;){...if (!number)break;




}...

}

for (;;){...if (!number)break;




}...

}

A execução duma instrução continue fazterminar o passo corrente da iteração.



Registando os tempos (3)

...void display_times(void){

int i;int hrs;int mins;int secs;int mils;long time;

for (i = 1; i <= MAX_NUMBER; ++i)if (time = times[i]){mils = time % 1000;time = time / 1000;secs = time % 60;time = time / 60;mins = time % 60;hrs = time / 60;printf("%3d %d:%02d:%02d.%03d\n",

i, hrs, mins, secs, mils);}

}

Ciclo for de enumeração:

for (i = 1; i <= MAX_NUMBER; ++i)



As afectações são expressõesif (time = times[i]){...

}

O valor da expressão de afectaçãotime = times[i] é o valor da variáveltime, depois de ter sido afectada.

for (i = 1; i <= MAX_NUMBER; ++i){time = times[i];if (time != 0) /* ou if (time)*/{

...}

}

Não confundir:

time = times[i]

time == times[i]

e

Alternativamente:



Enchimento de campos numéricosprintf("%3d %d:%02d:%02d.%03d\n",

i, hrs, mins, secs, mils);

printf("%3d %d:%2d:%2d.%3d\n",i, hrs, mins, secs, mils);

Número do carro (0 p/ terminar): 4Tempo (h m s mil): 1 53 6 12Número do carro (0 p/ terminar): 26Tempo (h m s mil): 1 53 34 45Número do carro (0 p/ terminar): 1Tempo (h m s mil): 1 53 59 823Número do carro (0 p/ terminar): 0Números de carros que terminaram: 3

1 1:53:59.8234 1:53:06.012

26 1:53:34.045

Números de carros que terminaram: 31 1:53:59.8234 1:53: 6. 12

26 1:53:34. 45



Validação dos inputslong scantime(void){

int hrs;int mins;int secs;int mils;return scanf("%d%d%d%d",

&hrs,&mins,&secs,&mils) == 4 &&isbtwn(hrs, 0, 23) &&isbtwn(mins, 0, 59) &&isbtwn(secs, 0, 59) &&isbtwn(mils, 0, 999) ?(((hrs * 60L)+mins) * 60L +

secs) * 1000L + mils :0;

}

long scantime(void){

int hrs;int mins;int secs;int mils;return scanf("%d%d%d%d",

&hrs,&mins,&secs,&mils) == 4 &&isbtwn(hrs, 0, 23) &&isbtwn(mins, 0, 59) &&isbtwn(secs, 0, 59) &&isbtwn(mils, 0, 999) ?(((hrs * 60L)+mins) * 60L +

secs) * 1000L + mils :0;

}

...printf("Tempo (h m s mil): ");if (!(time = scantime())){printf("ERRO: tempo inválido.\n");continue;

}times[number] = time;++n;

}return n;

}

...printf("Tempo (h m s mil): ");if (!(time = scantime())){printf("ERRO: tempo inválido.\n");continue;

}times[number] = time;++n;

}return n;

}

Nota: scanf devolve o número de argumentos lidos.



Escrevendo os temposint printtime(long time){

int hrs;int mins;int secs;int mils;mils = time % 1000;time = time / 1000;secs = time % 60;time = time / 60;mins = time % 60;hrs = time / 60;return printf("%d:%02d:%02d.%03d",

hrs, mins, secs, mils);}

int printtime(long time){

int hrs;int mins;int secs;int mils;mils = time % 1000;time = time / 1000;secs = time % 60;time = time / 60;mins = time % 60;hrs = time / 60;return printf("%d:%02d:%02d.%03d",


void display_times(void){

int i;for (i = 1; i <= MAX_NUMBER; ++i)if (times[i]){printf("%2d ", i);printtime(times[i]);printf("\n");

}}

void display_times(void){

int i;for (i = 1; i <= MAX_NUMBER; ++i)if (times[i]){printf("%2d ", i);printtime(times[i]);printf("\n");

}}

Nota: printf devolve o número de caracteres escritos.



O operador vírgula ,expr_1, expr_2

1. Avalia-se expr_1;2. Avalia-se expr_2; o resultado

constitui o valor da expressão.

if (time = scantime(), !time){printf("ERRO: tempo inválido.\n");continue;

}

if (time = scantime(), !time){printf("ERRO: tempo inválido.\n");continue;

}


long p;int i;for (p = 1, i = 1; i <= n; i = i + 1)p = p * base;

return p;}


long p;int i;for (p = 1, i = 1; i <= n; i = i + 1)p = p * base;

return p;}

Muitas vezes descarta-se o valor:



Calculando a classificação

int get_results(void){

int n = 0;...long time;long prev_time = 0;while (n < MAX_ARRIVALS){...printf("Tempo (h m s mil): ");if (time = scantime(), !time){printf("ERRO: tempo inválido.\n");continue;

}if (time < prev_time){printf("ERRO: tempo fora de

ordem.\n");continue;

}arrivals[++n] = number; times[number] = prev_time = time;

}return n;

}

Os tempos registam-se por ordem dechegada:



Calculando as médias#define ONE_MILE 1609.3

double kmh(long meters, long millisecs){

return(meters / 1000.0) /(millisecs / (double)(1000L * 60L * 60L));

}

double mph(long meters, long millisecs){

return kmh(meters, millisecs) / (ONE_MILE / 1000);

}

double kmh(long meters, long millisecs){

return(meters / 1000) /(millisecs / (1000L * 60L * 60L));

}

Aritmética mista (inteiros e reais):1. Conversão automática.2. Conversão por operador (double).3. Constantes (ex.: 1000.0, 1000L).

Aritmética mista (inteiros e reais):1. Conversão automática.2. Conversão por operador (double).3. Constantes (ex.: 1000.0, 1000L).



Escrevendo números reais

void display_results(void){

int i;long time;for (i = 1; i <= n_cars; ++i){printf("%2d.º %2d ", i, arrivals[i]);printtime(time = times[arrivals[i]]);printf(" %7.3f %7.3f\n",

kmh(length, time),mph(length, time));

}}

long length;...

main (){

printf("Comprimento do circuito (metros): ");scanf("%ld", &length);...

}

printf(" %7.3f %7.3f\n", ...

largura do campo precisão (número decasas decimais) 80Programação Avançada com C


Calculando a classificação (1)

#define MAX_CARS 26

long times[MAX_CARS + 1];int cars [MAX_CARS + 1];int n_cars;

int placeof(int n){

int i;for (i = n_cars; i >= 1 && cars[i] != n; ––i);

return i;}

Para evitar repetições:...if (placeof(number)){


}...

Posição de um carro no vector cars, dado onúmero:



Calculando a classificação (2)void get_results(void){

int number;long time;while (n_cars < MAX_CARS){printf("Carro número: (0 p/ terminar): ",

n_cars + 1);scanf("%d", &number);if (!number)break;


}if (placeof(number)){


}printf("Tempo (h m s mil): ");if (time = scantime(), !time){printf("ERRO: tempo inválido.\n");continue;

}cars[++n_cars] = number; times[n_cars] = time;

}}

Usa-se a variável externa n_cars, por causa da chamada placeof(number).

Usa-se a variável externa n_cars, por causa da chamada placeof(number).



Bubblesort

Bubblesort:

void bubblesort(int a[], int n){int i;int j;int m;for (i = 2; i <= n; ++i)for (j = n; j >= i; ––j)if (a[j-1] > a[j]){m = a[j-1];a[j-1] = a[j];a[j] = m;

}}

de um vector de inteiros a, com nelementos (posição 0 desocupada):



Ordenando os resultados

void sortcars(void){int i;int j;int my_car;long my_time;for (i = 2; i <= n_cars; ++i)for (j = n_cars; j >= i; ––j)if (times[j-1] > times[j]){my_time = times[j-1];times[j-1] = times[j];times[j] = my_time;my_car = cars[j-1];cars[j-1] = cars[j];cars[j] = my_car;

}}

void sortcars(void){int i;int j;int my_car;long my_time;for (i = 2; i <= n_cars; ++i)for (j = n_cars; j >= i; ––j)if (times[j-1] > times[j]){my_time = times[j-1];times[j-1] = times[j];times[j] = my_time;my_car = cars[j-1];cars[j-1] = cars[j];cars[j] = my_car;

}}

Bubblesort do vector times, comreordenação em paralelo do vector cars:



Variáveis estáticas

Uma outra maneira de programar a funçãopoints:

int points(int i){

static int table [] = {10, 6, 4, 3, 2, 1};return i <= 6 ? table[i - 1] : 0;

}

int points(int i){


}

As variáveis estáticas não “morrem”quando termina a função em que estão declaradas.

Inicialização de um vector na declaração:

double IRStax[] ={0.160, 0.200, 0.275, 0.350, 0.400};

long IRSlimits[] ={450, 850, 1250, 3000, 1000000000};

double IRStax[] ={0.160, 0.200, 0.275, 0.350, 0.400};

long IRSlimits[] ={450, 850, 1250, 3000, 1000000000};



Mostrando os resultadosvoid display_results(void){

int i;long time;for (i = 1; i <= n_cars; ++i){printf("%2d.º %2d ", i, cars[i]);printtime(time = times[i]);printf(" %7.3f %7.3f %2d\n",

kmh(length, time),mph(length, time),points(i));

}}

main (){

printf("Comprimento do circuito (metros): ");scanf("%ld", &length);get_results();printf("\n");printf("Números de carros que terminaram: "

"%d\n", n_cars);printf("\n");sortcars();display_results();

}

A função main:



Exercícios (3)1. Escrever um programa para simular o jogodo “preço certo”. O programa começa por pedir o preço secreto; depois aceita os palpi-tes dos quatros jogadores; finalmente anuncia qual ganhou, ou informa que ninguém ganhou,porque todos rebentaram. (Ganha o jogador que mais se aproxime do preço secreto, mas sem ultrapassar.)2. Escrever um programa para jogar aos da-dos. O trabalho do programa vai ser lançar osdados, registar os resultados, e anunciar ovencedor. Em cada jogo, lança-se os dadostrês vezes (no máximo) para cada jogador.Depois de cada lançamento (excepto depois doúltimo), o jogador pode escolher os dados que quer guardar e que não serão lançados na vez seguinte. O resultado de cada jogador é acombinação de números com que fica depoisdo último lançamento. Ganha o jogador que ficar com mais números iguais, de maior valor. Para fazer os lançamentos, usar a função degeração de números aleatórios rand(), doficheiro <stdlib.h>.3. Modificar o programa anterior para que oprograma seja também um dos jogadores.



Ficheiros

Os programas C manipulam ficheiros atravésde objectos de tipo FILE. O tipo FILE estádefinido no ficheiro <stdio.h>.

Declaração de um ficheiro:

FILE *fp;

Declaração de funções parametrizadas por ficheiros:

void fprint_results(FILE *f){...}

int fprinttime(FILE *f, long time){...}

Atenção ao asterisco



Operações sobre ficheiros (escrever)

Abrir um ficheiro para escrever, fopen:

FILE *fp;

fp = fopen("RESULTS", "w");

Fechar o ficheiro, fclose:fclose(fp);

Escrever no ficheiro, fprintf:

fprintf(fp,"%2d.º %2d ",i,cars[i]);

fprintf(fp, "%d:%02d:%02d.%03d",hrs, mins, secs, mils);

Abrir um ficheiro para acrescentar, fopen:

fp = fopen("HISTORY", "a");



Guardando os resultados (1)

int fprinttime(FILE *f, long time){

int hrs;int mins;int secs;int mils;mils = time % 1000;time = time / 1000;...return fprintf(f, "%d:%02d:%02d.%03d",


void fprint_results(FILE *f){

int i;long time;for (i = 1; i <= n_cars; ++i){

fprintf(f, "%2d.º %2d ", i, cars[i]);fprinttime(f, time = times[i]);fprintf(f, " %7.3f %7.3f %2d\n",

kmh(length, time),mph(length, time),points(i));

}}



Guardando os resultados (2)

main (){

FILE *pf;printf("Comprimento do circuito (metros): ");scanf("%ld", &length);scan_results();printf("\n");printf("Números de carros que terminaram: "

"%d\n", n_cars);sortcars();printf("\n");pf = fopen("RESULTS", "w");fprint_results(pf);fclose(pf);

}



Operações sobre ficheiros (ler)

Abrir um ficheiro para ler, fopen:

FILE *fp;

fp = fopen("RESULTS", "r");

Fechar o ficheiro, fclose:

fclose(fp);

Ler no ficheiro, fscanf:

fscanf(fp, "%d", &n);

fscanf(fp, "%d%d%ld", &i, &j, &x);

int n;

int i;int j;long x;



Ficheiros stdin, stdout, stderr

Quando um programa C arranca, o ficheiro stdin fica associado ao teclado do terminal e os ficheiros stdout e stderr ao ecrã. Em alguns ambientes, os ficheiros stdin estdout podem ser redirigidos para outros ficheiros ou para pipes, no momento da chamada do programa.A função scanf lê do ficheiro stdin; afunção printf escreve no ficheiro stdout. Oficheiro stderr é usado para receber asmensagens de erro.Para mudar no programa uma associação estabelecida por defeito, usa-se a função freopen para “reabrir” o ficheiro. Exemplo:

if (freopen("RESULTS", "w", stdout) == NULL)fprintf(stderr, "ERRO: impossível reabrir.\n");

else{...printf("Isto vai para o ficheiro RESULTS");...

}



Problema dos pilotos (1)

Problema:A lista dos concorrentes ao grande prémio existe num ficheiro de texto,chamado "CARS_TODAY". Cada linha deste ficheiro contém o número do carro e o nome (apelido) do piloto. Escrever umprograma para saber qual é o nome dopiloto que conduz determinado carro. Oprograma funciona ciclicamente e termina quando se der uma resposta vazia(newline), em vez do número do carro.

Solução:Usar dois vectores paralelos, um com os números dos carros, outro com os nomesdos pilotos; carregá-los a partir doficheiro; pesquisar o número dado no vector dos números; devolver o nome que está na posição correspondente.



Cadeias de caracteresOs nomes são cadeias de caracteres.

Em C, as cadeias de caracteres são vectoresde caracteres e são terminadas pelo carácterde código 0, escrito '\0'.

Em C, as cadeias de caracteres são vectoresde caracteres e são terminadas pelo carácterde código 0, escrito '\0'.

char name[16]; 1. índices entre 0 e 15.2. capacidade útil 15;

uma posição será ocupada por '\0'.

1. índices entre 0 e 15.2. capacidade útil 15;

uma posição será ocupada por '\0'.

O ficheiro <string.h> da biblioteca contém muitas funções para trabalhar com cadeias.

O ficheiro <string.h> da biblioteca contém muitas funções para trabalhar com cadeias.

int strlen(char s[]);{

int i;for (i = 0; s[i]; ++i);

return i;}

int strlen(char s[]);{

int i;for (i = 0; s[i]; ++i);

return i;}

Exemplo. Comprimento de uma cadeia:



Lendo cadeias de caracteres

%s especificador de conversão para cadeia, nas funções scanf e fscanf.

%s especificador de conversão para cadeia, nas funções scanf e fscanf.

char name[16];int number;FILE *f;...fscanf(f, "%d%s", &number, name);

...

Quando um argumento da função scanf oufscanf é uma cadeia, não se usa o &.

Quando um argumento da função scanf oufscanf é uma cadeia, não se usa o &.

Para ler uma linha inteira do terminal (até ao fim da linha inclusive), usa-se a função gets.O newline é substituído por '\0'.

Para ler uma linha inteira do terminal (até ao fim da linha inclusive), usa-se a função gets.O newline é substituído por '\0'.

...printf("Qual é o nome? ");gets(name);...



Vectores de cadeias

Um vector de cadeias é um vector devectores.

Um vector de cadeias é um vector devectores.

#define MAX_CARS 32

char names [MAX_CARS + 1][16];int numbers [MAX_CARS + 1];int n_cars;

Pode-se ler uma linha do ficheiro directa-mente para as posições nos vectores:

Pode-se ler uma linha do ficheiro directa-mente para as posições nos vectores:

fscanf(f, "%d%s",&numbers[i], names[i])



Ciclo de leitura

int loadcars(FILE *f){int i;for (i = 1;

fscanf(f, "%d%s",&numbers[i],names[i]) != EOF;

++i);

return i - 1;}

A função fscanf devolve o número deargumentos lidos, ou EOF, quando há umerro ou o ficheiro acabou. EOF é uma constante simbólica definida no ficheiro<stdio.h>

A função fscanf devolve o número deargumentos lidos, ou EOF, quando há umerro ou o ficheiro acabou. EOF é uma constante simbólica definida no ficheiro<stdio.h>



Verificando se o ficheiro existe

main (){

FILE *fcars;...fcars = fopen("CARS_TODAY", "r");n_cars = loadcars(fcars);fclose(fcars);...

}

main (){

FILE *fcars;...fcars = fopen("CARS_TODAY", "r");n_cars = loadcars(fcars);fclose(fcars);...

}

O ficheiro existe, de certeza (e pode ser lido):

Se a abertura do ficheiro não se puder fazer, afunção fopen devolve NULL (constantesimbólica definida no ficheiro <stdio.h>):#define NO_SUCH_FILE 1

main (){

FILE *fcars;...if ((fcars=fopen("CARS_TODAY", "r")) == NULL){printf("Ficheiro CARS_TODAY inacessível.");return NO_SUCH_FILE;

}n_cars = loadcars(fcars);fclose(fcars);...

}

#define NO_SUCH_FILE 1

main (){

FILE *fcars;...if ((fcars=fopen("CARS_TODAY", "r")) == NULL){printf("Ficheiro CARS_TODAY inacessível.");return NO_SUCH_FILE;


}



Tratamento de errosAs mensagens de erros de um programa Cdevem ser escritas no ficheiro stderr, com afunção fprintf.A função exit termina o programa em casode erro irrecuperável e transmite o valor doseu argumento (de tipo int) ao processo que chamou o programa que agora termina. Afunção exit vem declarada no ficheiro<stdlib.h>.


main (){

FILE *fcars;...if ((fcars=fopen("CARS_TODAY", "r")) == NULL){fprintf(stderr,

"Ficheiro CARS_TODAY inacessível.");exit(NO_SUCH_FILE);


}


main (){

FILE *fcars;...if ((fcars=fopen("CARS_TODAY", "r")) == NULL){fprintf(stderr,

"Ficheiro CARS_TODAY inacessível.");exit(NO_SUCH_FILE);


}



Controlando a forma dos inputs

main (){

FILE *fcars;char reply[81];int n;int i;

if ((fcars = fopen("CARS_TODAY", "r")) == NULL){printf("Ficheiro CARS_TODAY inacessível.");return NO_SUCH_FILE;

}n_cars = loadcars(fcars);fclose(fcars);

while (printf("Número: "), strlen(gets(reply))){if (!sscanf(reply, "%d", &n))printf("Número inválido.\n");

else if ((i = indexof(n)) == 0)printf("Não participa.\n");

elseprintf("%s\n", names[i]);

}return 0;

}

main (){


if ((fcars = fopen("CARS_TODAY", "r")) == NULL){printf("Ficheiro CARS_TODAY inacessível.");return NO_SUCH_FILE;

}n_cars = loadcars(fcars);fclose(fcars);

while (printf("Número: "), strlen(gets(reply))){if (!sscanf(reply, "%d", &n))printf("Número inválido.\n");

else if ((i = indexof(n)) == 0)printf("Não participa.\n");

elseprintf("%s\n", names[i]);

}return 0;

}

A função sscanf é análoga à fscanf, mas oprimeiro argumento é uma cadeia. Os carac-teres são “lidos” a partir dessa cadeia.



Buscas com sentinelaPara procurarmos um número no vector numbers podemos começar por colocá-lo na posição de índice 0, que está desocupada.Depois faz-se uma busca linear, de cima para baixo. O elemento será encontrado decerteza. Se for encontrado na posição 0, isso quer dizer que ele não existia:

int indexof(int n){int i;for (numbers[0] = n, i = n_cars;

numbers[i] != n;––i)

;return i;

}

int indexof(int n){int i;for (numbers[0] = n, i = n_cars;

numbers[i] != n;––i)

;return i;

}

O número colocado na posição 0 funciona como sentinela.



Buscas dicotómicasComo o vector numbers está ordenado,podemos fazer uma busca dicotómica. Em cada passo do ciclo, comparamos o número procurado com o elemento que está no meiodo intervalo de busca. Das três uma: ou são iguais, ou o primeiro é menor que o segundo,ou o segundo é menor que o primeiro:

int indexof(int n){int a;int i = 1;int j = n_cars;while (i <= j)if (n == numbers[a=(i+j)/2])return a;

else if (n < numbers[a])j = a - 1;

elsei = a + 1;

return 0;}

int indexof(int n){int a;int i = 1;int j = n_cars;while (i <= j)if (n == numbers[a=(i+j)/2])return a;

else if (n < numbers[a])j = a - 1;

elsei = a + 1;

return 0;}



Buscas dicotómicas (propriamente ditas)

Podemos fazer uma busca dicotómica comuma só comparação em cada passo do ciclo. O número procurado ou é menor ou igual ao elemento que está no meio do intervalo debusca, ou não é. Mas temos que esperar queo intervalo de busca se reduza a um único elemento:

int indexof(int n){int a;int i = 1;int j = n_cars;while (i < j)if (n <= numbers[a=(i+j)/2])j = a;

elsei = a + 1;

return (n == numbers[i] ? i : 0);}

int indexof(int n){int a;int i = 1;int j = n_cars;while (i < j)if (n <= numbers[a=(i+j)/2])j = a;

elsei = a + 1;

return (n == numbers[i] ? i : 0);}



Problema dos pilotos (2)

Problema:Como no problema anterior, a lista dosconcorrentes ao grande prémio existenum ficheiro de texto, chamado"CARS_TODAY". Cada linha deste ficheiro contém o número do carro e o nome(apelido) do piloto. Agora queremos escrever um programa para saber qual é ocarro conduzido por determinado piloto. Oprograma funciona ciclicamente e termina quando se der uma resposta vazia(newline), em vez do número do carro.

Solução:Como antes, usar dois vectores paralelos, um com os números dos carros, outrocom os nomes dos pilotos; carregá-los apartir do ficheiro; pesquisar o nome dado no vector dos nomes; devolver o número que está na posição correspondente.



Copiando cadeiasAs cadeias não se podem afectar directamente. Usa-se a função strcpy:

char s0[32];char s1[80];...strcpy(s0, s1); /* s0 = s1 */

...

char s0[32];char s1[80];...strcpy(s0, s1); /* s0 = s1 */

...

Exemplo:

É preciso que a cadeia s1 caiba na cadeia s0(ou seja, que o comprimento de s1 sejainferior à dimensão de s0). Caso contrário, amemória fica corrompida, porque a cópia vai continuar sobre uma zona que já não pertence à cadeia s0.



Comparando cadeias

As cadeias não se podem comparar directamente. Usa-se a função strcmp.strcmp(s1, s2) dá um número < 0 se s1 < s2, 0 se s1 == s2, e um número >0 se s1 > s2.

char s0[32];char s1[80];...if (strcmp(s0, s1) <= 0);

/* if (s0 <= s1) */...

if (!strcmp(s0, s1));/* if (s0 == s1) */

...

char s0[32];char s1[80];...if (strcmp(s0, s1) <= 0);

/* if (s0 <= s1) */...

if (!strcmp(s0, s1));/* if (s0 == s1) */

...



Buscas de cadeias com sentinela

int indexof(char s[]){int i;for (strcpy(names[0],s), i=n_cars;

strcmp(names[i],s);––i)

;return i;}

int indexof(char s[]){int i;for (strcpy(names[0],s), i=n_cars;

strcmp(names[i],s);––i)

;return i;}

main (){


fcars = fopen("CARS_TODAY", "r");n_cars = loadcars(fcars);fclose(fcars);

while (printf("Nome: "),strlen(gets(reply)))if ((i = indexof(reply)) == 0)printf("Não participa.\n");

elseprintf("%d\n", numbers[i]);

return 0;}

main (){


fcars = fopen("CARS_TODAY", "r");n_cars = loadcars(fcars);fclose(fcars);

while (printf("Nome: "),strlen(gets(reply)))if ((i = indexof(reply)) == 0)printf("Não participa.\n");

elseprintf("%d\n", numbers[i]);

return 0;}



Ordenação de um vector de cadeias

void bubblesort(void){

int i;int j;char my_name[16];int my_number;for (i = 2; i <= n_drivers; ++i)for (j = n_drivers; j >= i; ––j)if (strcmp(names[j - 1], names[j]) > 0){strcpy(my_name, names[j - 1]);strcpy(names[j - 1], names[j]);strcpy(names[j], my_name);my_number = numbers[j - 1];numbers[j - 1] = numbers[j];numbers[j] = my_number;

}}

void bubblesort(void){

int i;int j;char my_name[16];int my_number;for (i = 2; i <= n_drivers; ++i)for (j = n_drivers; j >= i; ––j)if (strcmp(names[j - 1], names[j]) > 0){strcpy(my_name, names[j - 1]);strcpy(names[j - 1], names[j]);strcpy(names[j], my_name);my_number = numbers[j - 1];numbers[j - 1] = numbers[j];numbers[j] = my_number;

}}

É preciso reordenar em paralelo o vector numbers.



Busca dicotómica de cadeias (1)

int indexof(char s[]){

int a;int i = 1;int j = n_drivers;while (i < j)if (strcmp(s, names[a = (i + j) / 2]) <= 0)

j = a;elsei = a + 1;

return (strcmp(s, names[i]) ? 0 : i);}


int a;int i = 1;int j = n_drivers;while (i < j)if (strcmp(s, names[a = (i + j) / 2]) <= 0)

j = a;elsei = a + 1;

return (strcmp(s, names[i]) ? 0 : i);}


int a;int i = 1;int j = n_drivers;while (i <= j)if (strcmp(s, names[a = (i + j) / 2]) < 0)j = a - 1;

else if (strcmp(s, names[a]) > 0)i = a + 1;

else return a;return 0;

}


int a;int i = 1;int j = n_drivers;while (i <= j)if (strcmp(s, names[a = (i + j) / 2]) < 0)j = a - 1;

else if (strcmp(s, names[a]) > 0)i = a + 1;

else return a;return 0;

}

Ou:



Busca dicotómica de cadeias (2)

int indexof(char name []){

int a;int i = 1;int j = n_drivers;while (i <= j)switch(sign(strcmp(name, names[a=(i+j) / 2])))

{case -1: j = a - 1;break;

case 0:return a;

case 1:i = a + 1;break;

}return 0;

}

int indexof(char name []){

int a;int i = 1;int j = n_drivers;while (i <= j)switch(sign(strcmp(name, names[a=(i+j) / 2])))

{case -1: j = a - 1;break;

case 0:return a;

case 1:i = a + 1;break;

}return 0;

}

int sign(int n){

return (n >= 0) - (n <= 0);}

int sign(int n){

return (n >= 0) - (n <= 0);}

Como a função strcmp pode dar três resulta-dos (<0, 0, >0) uma busca “tricotómica” pare-ce apropriada. Para usar a instrução switch épreciso calcular o sinal do resultado:



Segunda parte: C avançado

1. Apontadores.

2. Estruturas. Apontadores para estruturas

3. Processamento de texto.

4. Alocação dinâmica.

5. Vectores de apontadores.

6. Estruturas auto-referenciadas: listas eárvores.

7. Recursividade.

8. Tabelas de hash.

9. Operações sobre bits.

10. Listas de argumentos de comprimento variável.

11. Argumentos na linha de comando.

12. Passagem para o C++.



ApontadoresVariável:

nome...tipo...valor...localização...

Operador de endereço (ou referenciação):

int n;...&n /* o endereço da

variável n */

Operador de indirecção (ou desreferenciação):

&&

***&n /* a variável cujo

endereço é o endereçoda variável n, ou sejaa variável n */



Variáveis apontadores

Declaração de apontadores para int:

Declaração de apontadores para char:

Declaração de apontadores para double:

Os ficheiros são apontadores:

int *p;int *p;

char *c;char *c;

double *d;double *d;

FILE *fp;FILE *fp;

int n;int *p;...n = 3;p = &n;*p = 5;printf("%d\n", n);...



Passagem de parâmetros por valor

Em C, os parâmetros das funções são passados por valor. Quer dizer, a função usa,nos cálculos, uma cópia do valor do argu-mento, e não o argumento propriamente dito.Por isso, a função não pode modificar directamente o valor dos seus argumentos (amenos que a eles aceda externamente).

Em C, os parâmetros das funções são passados por valor. Quer dizer, a função usa,nos cálculos, uma cópia do valor do argu-mento, e não o argumento propriamente dito.Por isso, a função não pode modificar directamente o valor dos seus argumentos (amenos que a eles aceda externamente).

Quando uma função usa um parâmetro como variável, está de facto a usar uma variávellocal declarada implicitamente com o mesmo tipo do parâmetro e inicializada com o valor desse parâmetro.

Quando uma função usa um parâmetro como variável, está de facto a usar uma variávellocal declarada implicitamente com o mesmo tipo do parâmetro e inicializada com o valor desse parâmetro.

int sum(int n){

int s;for (s = 0;

n > 0;––n)

s += n;return s;

}

int sum(int n)/* código fictício

*/{

int _n = n;int s;for (s = 0;

_n > 0;––_n)

s += _n;return s;

}



Parâmetros de saída em funções

Para uma função poder modificar para-metricamente o valor de uma variável, estatem que ser passada por apontador. O valordo argumento, um apontador, não será modi-ficado, mas por indirecção pode modificar-se o valor da variável apontada.

Para uma função poder modificar para-metricamente o valor de uma variável, estatem que ser passada por apontador. O valordo argumento, um apontador, não será modi-ficado, mas por indirecção pode modificar-se o valor da variável apontada.

int roots(double a, double b, double c,double *x1, double *x2)

{double delta = b * b - 4.0 * a * c;if (delta >= 0.0){*x1 = (-b + sqrt(delta)) / (2.0 * a);*x2 = -b / a - *x1;return 1;

}elsereturn 0;

}

Exemplo: uma função para calcular as raízesdo polinómio ax + bx + c, devolvendo 0 se não houver raízes e 1 se houver:

2



Passagem por apontador

Assim estaria errado:

void swap (int *x, int *y){int temp;

temp = *x;*x = *y;*y = temp;

}

void swap (int x, int y){int temp;

temp = x;x = y;y = temp;

}

Exemplo: uma função para trocar os valores de duas variáveis int.



Apontadores na função scanfExemplo: um programa para usar a função

roots:#include <stdio.h>#include <math.h>

int roots(double, double, double,double *, double *);

main (){

double a, b, c;double x1, x2;printf("a, b, c: ");scanf("%lf%lf%lf", &a, &b, &c) ;if (roots( a, b, c, &x1, &x2) )printf("x1 = %6.2f x2 = %6.2f\n", x1, x2) ;

elseprintf("Não há raízes.\n");

return 0;}

int roots(double a, double b, double c,double *x1, double *x2)

{...

}



Os quadros são passadospor apontador

Em C, os parâmetros que são quadros são sempre passados por apontador. Assim, não há cópia local do valor do argumento, e asoperações fazem-se indirectamente sobre esse argumento.Por isso é que não aparece o operador & nasfunções scanf e fscanf, quando o argu-mento é uma cadeia:char name[16];int number;FILE *f;...fscanf(f, "%d%s", &number, name);

...

char reply[81];...while (printf("Número: "),

strlen(gets(reply))){...

}

Na função gets também não se usa o &:



Vectores e apontadores

Em C, há uma relação estreita entre os vectores e os apontadores.

Em C, há uma relação estreita entre os vectores e os apontadores.

&a[i] é o endereço do i-ésimo elemento do vector a. Pode ser afectado a um apontador para int:

int a[16];

Seja:

int *p;...p = &a[i];

Agora p aponta para o i–ésimo elemento do vector a e *p permite aceder a esse valor.

Aliás, o nome do vector “vale” o endereço doprimeiro elemento, e portanto

p = a;é o mesmo que

p = &a[0];



Aritmética de apontadores

int a[16];int *p;int *q;...p = &a[i];q = &a[j];

Seja:

p aponta para a[i];q aponta para a[j].

E também:

p + k p + k é um apontador que aponta para a[i + k].

*(p + k) *(p + k) referenciaa[i + k].

a[i] *(a+i)

&a[i] a+i

Então:

p - q p - q vale i - j.

p <= q p <= q vale i <= j.



Incrementação de apontadores

int a[16];int *p;...p = &a[i];

Seja ainda:

p aponta para a[i].Então:

++p aponta para a[i+1], e incrementa oapontador p (o qual fica a apontar para a[i+1]).

p++ aponta para a[i], e incrementa oapontador p (o qual fica a apontar para a[i+1]).

*++p referencia a[i+1], e incrementa oapontador p (o qual fica a apontar para a[i+1]).

*p++ referencia a[i], e incrementa oapontador p (o qual fica a apontar para a[i+1]).



Ciclo de leitura com apontadores (1)

int loadcars(FILE *f){

int i;for (i = 1;

fscanf(f, "%d%s",&numbers[i],names[i]) !=

EOF;++i)

;return i - 1;

}

int loadcars(FILE *f){

int i;for (i = 1;

fscanf(f, "%d%s",&numbers[i],names[i]) !=

EOF;++i)

;return i - 1;

}

int loadcars(FILE *f){int *ip;char (*sp) [16];for (ip=numbers+1, sp = names+1;

fscanf(f, "%d%s",ip++,*sp++) != EOF;

);

return ip - numbers - 2;}

int loadcars(FILE *f){int *ip;char (*sp) [16];for (ip=numbers+1, sp = names+1;

fscanf(f, "%d%s",ip++,*sp++) != EOF;

);

return ip - numbers - 2;}

Com vectores (revisão):

Com apontadores:



Ciclo de leitura com apontadores (2)

Observações:

char (*sp) [16];Declara sp como apontador para uma cadeiade 16 caracteres.

char *sp [16];Declararia sp como vector de 16 apontadores para char.

ip++No i-ésimo passo, ip++ “vale” um apontador que aponta para numbers[i].

sp++No i-ésimo passo, sp++ “vale” um apontador que aponta para names[i].

*sp++

No i-ésimo passo, *sp++ referencia names[i].Note-se que names[i] é uma cadeia.



Buscas lineares com apontadoresBuscas com sentinela:

int indexof(int n){int *ip;for (*numbers = n,

ip = numbers + n_cars;*ip != n;––ip)

;return ip - numbers;

}

int indexof(int n){int *ip;for (*numbers = n,

ip = numbers + n_cars;*ip != n;––ip)


}

Buscas simples:

int indexof(int n){int *ip;for (ip = numbers + n_cars;

ip > numbers && *ip != n;––ip)


}

int indexof(int n){int *ip;for (ip = numbers + n_cars;

ip > numbers && *ip != n;––ip)


}



Cadeias e apontadoresAs cadeias de caracteres são vectores eportanto são passadas por apontador. Nas funções, os parâmetros cadeia aparecem normalmente declarados char *.

int strlen(char *s);{char *p = s;while (*s)++s;

return s - p;}

int strlen(char *s);{char *p = s;while (*s)++s;

return s - p;}

int strcmp(char *s, char *t){for ( ; *s == *t; s++, t++)if (!*s)return 0;

return *s - *t;}

int strcmp(char *s, char *t){for ( ; *s == *t; s++, t++)if (!*s)return 0;

return *s - *t;}

Exemplo. O comprimento de uma cadeia:

Exemplo. A comparação de cadeias:



Funções que devolvem cadeiasEm C, as funções não podem ter vectores como resultado, mas apontadores sim:Exemplo. A função strcpy copia o segundo argumento para o primeiro e devolve umapontador para o primeiro:

Exemplo. A função strchr devolve umapontador para a primeira ocorrência dosegundo argumento (um char) no primeiro(uma cadeia):

char *strcpy(char *s, char *t){char *p = s;while (*s++ = *t++);

return p;}

char *strcpy(char *s, char *t){char *p = s;while (*s++ = *t++);

return p;}

char *strchr(char *s, char c){for ( ; *s; ++s)if (*s == c)return s;

return NULL;}

char *strchr(char *s, char c){for ( ; *s; ++s)if (*s == c)return s;

return NULL;}



O ficheiro <string.h>char *strcpy(char *, char *);char *strncpy(char *, char *, size_t);

char *strcat(char *, char *);char *strncat(char *, char *, size_t);

int strcmp(char *, char *);int strncmp(char *, char *, size_t);

char *strchr(char *, int);char *strrchr(char *, int);

char *strpbrk(char *, char *);char *strstr(char *, char *);

size_t strlen(char *);...

char *strcpy(char *, char *);char *strncpy(char *, char *, size_t);

char *strcat(char *, char *);char *strncat(char *, char *, size_t);

int strcmp(char *, char *);int strncmp(char *, char *, size_t);

char *strchr(char *, int);char *strrchr(char *, int);

char *strpbrk(char *, char *);char *strstr(char *, char *);

size_t strlen(char *);...

a)b)

c)d)

e)f)

g)h)

i)j)

k)

a) copia arg_2 para arg_1; devolve arg_1.b) copia arg_3 caracteres.c) concatena arg_2 a arg_1; devolve arg_1.d) concatena arg_3 caracteres.e) compara arg_1 e arg_2: < dá <0; == dá 0; > dá >0;f) compara arg_3 caracteres.g) apontador para a primeira ocorrência de arg_2 em arg_1.h) apontador para a última ocorrência de arg_2 em arg_1.i) apontador para a primeira ocorrência em arg_1 de um

dos caracteres de arg_2.j) apontador para a primeira ocorrência de arg_2 em arg_1.k) comprimento.

size_t é um tipo inteiro, definido em <string.h>.



Ler e escrever cadeias (1)

Funções declaradas no ficheiro <stdio.h>

char *fgets(char *, int, FILE *);int fputs(char *, FILE *);

char *gets(char *);int puts(char *);

char *fgets(char *, int, FILE *);int fputs(char *, FILE *);

char *gets(char *);int puts(char *);

a)b)

c)d)

a) Lê no máximo arg_2 - 1 caracteres para arg_1, até um newline, inclusive; junta '\0'. Devolve arg_1, ou NULL, em fim deficheiro ou erro.

b) Escreve arg_1 em arg_2. Devolve EOF emcaso de erro.

c) Lê uma linha do terminal, substituindo newline por '\0'. Devolve arg, ou NULL,em fim de ficheiro ou erro.

d) Escreve arg no terminal e depois newline.Devolve EOF em caso de erro.



Ler e escrever cadeias (2)

Escrever cadeias com printf:

%[–][width][.precision]s

[-] se presente, manda encostarà esquerda.

[width] se presente, especifica alargura mínina do campo deescrita. Valor por defeito: 1.

[.precision] se presente, especifica o nú-mero de caracteres a escre-ver. (Se não, escreve-setudo.)

Forma geral da conversão:

Um asterisco no lugar da largura ou da preci-são manda ir buscar o valor respectivo ao próximo argumento (que tem que ser int).

printf("%s%.*s\n",name1,32 - (int) strlen(name1),name2);

printf("%s%.*s\n",name1,32 - (int) strlen(name1),name2);



Exercícios (4)

1. Escrever um programa C para listar no terminal todas as linhas de um ficheiro que contenham determinada cadeia de caracteres.O programa começa por pedir a cadeia;depois, ciclicamente, pede o nome de umficheiro e analisa esse ficheiro; termina quando o utilizador responder com uma cadeia vazia para o nome do ficheiro.Cada linha afixada vem precedida pelo seu número de linha no ficheiro.2. Escrever uma variante deste programa que não distinga entre maiúsculas e minúsculas.3. Escrever um programa para numerar àdireita todas as linhas não vazias de umficheiro. A numeração deve aparecer encos-tada à coluna 80 e só deve ser escrita secouber.4. Escrever um programa para eliminar detodas as linhas de um ficheiro os caracteres brancos (espaços e tabs) à direita.



Estruturas (1)

typedef struct{ int number;char name [16];

} Car;


} Car;

#define MAX_CARS 26Car cars [MAX_CARS + 1];int n_cars;FILE *f_cars;Car temp_car;

int fscanfCar(FILE *, Car *);int loadCars(FILE *, Car *);

int fprintfCar(FILE *, Car *);void dumpCars(FILE *, Car *, int);


} Car;

#define MAX_CARS 26Car cars [MAX_CARS + 1];int n_cars;FILE *f_cars;Car temp_car;

int fscanfCar(FILE *, Car *);int loadCars(FILE *, Car *);

int fprintfCar(FILE *, Car *);void dumpCars(FILE *, Car *, int);



Estruturas (2)

typedef struct{ member_type member_name;member_type member_name;...member_type member_name;

} new_type;

typedef struct{ int invoice_no;long invoice_date;long invoice_amount;long invoice_paid;

} History;

typedef struct{ int account_no;int account_type;char name[32];char street[32];char city[16];int code;long last_payment;History payments[4];

} Client;

typedef struct{ int invoice_no;long invoice_date;long invoice_amount;long invoice_paid;

} History;

typedef struct{ int account_no;int account_type;char name[32];char street[32];char city[16];int code;long last_payment;History payments[4];

} Client;



Definição de nomes de tipostypedef already_known_type new_type;

typedef long Date;

typedef struct{ int invoice_no;Date invoice_date;long invoice_amount;Date invoice_paid;

} History;

...

typedef long Date;

typedef struct{ int invoice_no;Date invoice_date;long invoice_amount;Date invoice_paid;

} History;

...

typedef unsigned long size_t;typedef unsigned long size_t;

char *strncpy(char *, char *, size_t);char *strncat(char *, char *, size_t);int strncmp(char *, char *, size_t);

size_t strlen(char *);

char *strncpy(char *, char *, size_t);char *strncat(char *, char *, size_t);int strncmp(char *, char *, size_t);

size_t strlen(char *);

Exemplo. No ficheiro <string.h>:



Acesso aos membros da estrutura

int fprintfCar(FILE *, Car);int fscanfCar(FILE *, Car *);

int fprintfCar(FILE *f, Car c){

return fprintf(f, "%2d %-16s",c.number,c.name);

}

int fscanfCar(FILE *f, Car *p){

return fscanf(f, "%d%s",&(*p).number,(*p).name);

}

int fprintfCar(FILE *, Car);int fscanfCar(FILE *, Car *);

int fprintfCar(FILE *f, Car c){

return fprintf(f, "%2d %-16s",c.number,c.name);

}



}

structure_name . member

Operador ponto (membro de estrutura):

Exemplo:



Estruturas e funçõesQuando as estruturas são parâmetros de en-trada, podem ser passadas por valor. Noentanto, normalmente passam-se por aponta-dor, para evitar a sobrecarga da cópia para avariável local.Exemplo:

int fprintfCar(FILE *, Car *);int fscanfCar(FILE *, Car *);

int fprintfCar(FILE *f, Car *p){

return fprintf(f, "%2d %-16s",(*p).number,(*p).name);

}



}

int fprintfCar(FILE *, Car *);int fscanfCar(FILE *, Car *);


return fprintf(f, "%2d %-16s",(*p).number,(*p).name);

}



}



Apontadores para estruturasOperador seta (apontador para estrutura):

typedef struct{ ... x;... ...;

} T;

T *p;

Então:

(*p).x p –> x


return fprintf(f, "%2d %–16s",p–>number,p–>name);

}


return fscanf(f, "%d%s",&p–>number,p–>name);

}


return fprintf(f, "%2d %–16s",p–>number,p–>name);

}


return fscanf(f, "%d%s",&p–>number,p–>name);

}

Exemplo:



Tabela completa dos operadores

() [] –> .

! + - * & ++ –– ~ (type) sizeof

* / %

+ -

<< >>

< <= > >=

== !=

&

^

|

&&

||

?:

= += -= *= /= %= &= ^= |= <<= >>=

,

Operadores Sentido

Nota: Os operadores ~, sizeof, <<, >>, &, ^, |, &=, ^=, |=,<<=, e >>= não foram estudados.



Problema do Grande Prémio (1)

Pretende-se um programa para calcular a clas-sificação dos pilotos no campeonato do mundode fórmula 1, após a realização de um grande prémio, dada a classificação antes dele e aordem de chegada na corrida. A classificação“antes” vem num ficheiro de texto, onde cada linha contém três informações: nome do piloto,nome da equipa, e número de pontos já obtidos. Na classificação aparecem todos os pilotos inscritos no campeonato, mesmo os que ainda têm zero pontos. (Portanto, pode-mos ter a certeza de que se um piloto entra na corrida, o seu nome está no ficheiro da classi-ficação.) As linhas estão ordenadas decres-centemente pelo número de pontos. O nome dopiloto é formado pelo apelido, seguido de umespaço, seguido da inicial do nome próprio,seguida de um ponto. O nome da equipa não contém espaços. O ficheiro tem uma forma tabular, com os nomes dos pilotos alinhados àesquerda na coluna 1, os nomes das equipas alinhados à esquerda na coluna 21, e os números de pontos alinhados à direita na coluna 44. Os apelidos ocupam no máximo 15caracteres e os nomes das equipas 19. Por exemplo:




Senna A. McLaren-Honda 78Prost A. Ferrari 69Berger G. McLaren-Honda 40Piquet N. Benetton-Ford 35Boutsen T. Williams-Renault 32Mansell N. Ferrari 31Patrese R. Williams-Renault 22...

Senna A. McLaren-Honda 78Prost A. Ferrari 69Berger G. McLaren-Honda 40Piquet N. Benetton-Ford 35Boutsen T. Williams-Renault 32Mansell N. Ferrari 31Patrese R. Williams-Renault 22...

(continuação:)

Em cada corrida, o primeiro classificado ganha 10 pontos, o segundo 6, o terceiro 4, o quarto 3, o quinto 2, o sexto 1, e todos os outros não ganham pontos nenhuns.(continua)




(continuação)

Para evitar problemas com a introdução de dados no fim de cada corrida, em vez de se dar os nomes dos pilotos, indica-se o número docarro. Para permitir fazer a correspondência entre o número do carro e o nome do piloto que o tripula, existe um outro ficheiro de texto,previamente preparado, que em cada linha contém essas duas informações, para cada piloto que entra na corrida: primeiro o númerodo carro, depois um ou vários espaços, depoiso apelido do piloto, exactamente na forma em que aparece no ficheiro da classificação. (Sabe-se que todos os pilotos têm apelidos diferentes.) Este ficheiro vem ordenado pelo número do carro. (Nem todos os números são utilizados: por exemplo, ninguém quer corrercom o número 13, pelo sim, pelo não…)O ficheiro com a classificação “depois” decada grande prémio tem a mesma forma doficheiro inicial. No caso de dois ou mais concorrentes ficarem com o mesmo número depontos, respeita-se a ordem que eles tinhamantes da corrida.



Problema do Grande Prémio(estratégia de resolução)

Resolução:Começa-se por carregar os dois ficheiros comos dados para vectores. Depois, durante aintrodução da chegada, para verificar se umcarro, dado pelo seu número, participou mesmo na corrida, faz-se uma busca dico-tómica no vector dos carros, obtendo o nomedo condutor. Usando esse nome, faz-se uma busca linear no vector dos pilotos e adi-ciona-se o número de pontos. Trata-se deuma busca linear muito simplificada pois há agarantia de o elemento procurado existir (os ficheiros de dados não têm erros), mas épreciso ter cuidado para não registar por engano duas vezes a chegada do mesmo piloto. Finalmente, assim que termina a intro-dução manual da chegada, ordena-se o vec-tor da classificação por pontos e despeja-separa o ficheiro resultado.



Operações sobre carros


} Car;

int fscanfCar(FILE *, Car *);

int loadCars(FILE *, Car *);

#define MAX_CARS 26Car cars [MAX_CARS + 1];int n_cars;

int carsindexof(int);


} Car;

int fscanfCar(FILE *, Car *);

int loadCars(FILE *, Car *);

#define MAX_CARS 26Car cars [MAX_CARS + 1];int n_cars;

int carsindexof(int);

a)

b)

c)

d)

a) Definição do tipo Car.b) Declaração de duas funções que operam

sobre o tipo Car.c) Definição do vector cars, com MAX_CARS

+ 1 elementos de tipo Car (a posição 0não é ocupada).

d) Declaração de uma função de busca dicotómica no vector cars. (Este vectorestará ordenado pelo campo number.)



Operações sobre pilotos

typedef struct{ char name [16];char initial;char team [20];int pts;

} Driver;

int fscanfDriver(FILE *, Driver *);int loadDrivers(FILE *, Driver *);int fprintfDriver(FILE *, Driver *);void dumpDrivers(FILE *, Driver *, int);

#define MAX_DRIVERS 40Driver drivers [MAX_DRIVERS + 1];int n_drivers;

int driversindexof(char *);void bubblesortdrivers(void);

typedef struct{ char name [16];char initial;char team [20];int pts;

} Driver;

int fscanfDriver(FILE *, Driver *);int loadDrivers(FILE *, Driver *);int fprintfDriver(FILE *, Driver *);void dumpDrivers(FILE *, Driver *, int);

#define MAX_DRIVERS 40Driver drivers [MAX_DRIVERS + 1];int n_drivers;

int driversindexof(char *);void bubblesortdrivers(void);

a)

b)

c)

d)e)

a) Definição do tipo Driver.b) Declaração de quatro funções que operam

sobre o tipo Driver.c) Definição do vector drivers, com

MAX_DRIVERS + 1 elementos de tipo Car(a posição 0 não é ocupada).

d) Declaração de uma função de busca linear no vector drivers.

e) Função de ordenação do vector drivers.144Programação Avançada com C


A função para os pontos

int points(int);int points(int);

int points(int i){


}

int points(int i){


}

Declaração:

Definição (usando uma tabela estática):

...for (i = 1; i <= 6; ++i)

{...drivers[...].pts += points(i);...

}...

...for (i = 1; i <= 6; ++i)

{...drivers[...].pts += points(i);...

}...

Esquema de utilização:



Carregamento dos carros


return fscanf(f, "%d%s",&p->number,p->name);

}


return fscanf(f, "%d%s",&p->number,p->name);

}

int loadCars(FILE *f, Car *p){

Car *i = p;while (fscanfCar(f, i++) != EOF);

return i - 1 - p;}

int loadCars(FILE *f, Car *p){

Car *i = p;while (fscanfCar(f, i++) != EOF);

return i - 1 - p;}

Ler um Car a partir de um ficheiro:

Carregar um ficheiro de Car para memória, dado o endereço de carregamento; devolver onúmero de elementos lidos:


FILE *f_cars;...f_cars = fopen("CARS_TODAY", "r");n_cars = loadCars(f_cars, cars + 1);fclose(f_cars);...

FILE *f_cars;...f_cars = fopen("CARS_TODAY", "r");n_cars = loadCars(f_cars, cars + 1);fclose(f_cars);...



Busca dicotómica nos carros

int carsindexof(int n){

extern Car cars[];extern int n_cars;int a;int i = 1;int j = n_cars;while (i < j)if (n <= cars[a = (i + j) / 2].number)j = a;

elsei = a + 1;

return (n == cars[i].number ? i : 0);}

int carsindexof(int n){

extern Car cars[];extern int n_cars;int a;int i = 1;int j = n_cars;while (i < j)if (n <= cars[a = (i + j) / 2].number)j = a;

elsei = a + 1;

return (n == cars[i].number ? i : 0);}

Calcular o índice do elemento do vector cars cujo campo number tem um valordado. O vector cars está ordenado por essecampo e portanto usa-se uma busca dicotómica:

As duas declarações extern (opcionais se as definições correspondentes estiverem“antes”) servem para lembrar que asvariáveis cars[] e n_cars são externas.



Carregamento dos pilotos (1)

int fscanfDriver(FILE *f, Driver *p){

return fscanf(f, "%s%*c%c.%s%d",p->name,&p->initial,p->team,&p->pts);

}

int fscanfDriver(FILE *f, Driver *p){

return fscanf(f, "%s%*c%c.%s%d",p->name,&p->initial,p->team,&p->pts);

}

Ler um Driver a partir de um ficheiro:

"%s%*c%c.%s%d"cadeia, espaço, carácter, ponto, cadeia, número decimal.

Cadeia de formato:

O especificador %s “apanha” cadeias decaracteres não-brancos. Os caracteres brancos são o espaço (32), o tab (9), o newline (10), o carriage return (13), o tab vertical (11), e o formfeed (12).O especificador %c “apanha” um carácter,mesmo que seja branco.Um asterisco num especificador determina asupressão da afectação.Um carácter não branco na cadeia de formato fora dos especificadores de conversão tem que bater certo com o carácter lido.



Carregamento dos pilotos (2)


FILE *f_drivers;...

f_drivers = fopen("DRIVERS_BEFORE", "r");n_drivers = loadDrivers(f_drivers,drivers+1);fclose(f_drivers);

...

FILE *f_drivers;...


...

int loadDrivers(FILE *f, Driver *p){

Driver *i = p;while (fscanfDriver(f, i++) != EOF);

return i - 1 - p;}

int loadDrivers(FILE *f, Driver *p){

Driver *i = p;while (fscanfDriver(f, i++) != EOF);

return i - 1 - p;}

Carregar um ficheiro de Driver para memória, dado o endereço de carregamento; devolver onúmero de elementos lidos:



Descarregamento dos pilotos (1)

int fprintfDriver(FILE *f, Driver *p){

return fprintf(f, "%*s%-20s%4d\n",20 - fprintf(f, "%s %c.",

p->name,p->initial),

"",p->team,p->pts);

}

int fprintfDriver(FILE *f, Driver *p){

return fprintf(f, "%*s%-20s%4d\n",20 - fprintf(f, "%s %c.",

p->name,p->initial),

"",p->team,p->pts);

}

"%s %c."cadeia, espaço, carácter, ponto.

Cadeias de formato:

"%*s%-20s%4d\n"cadeia num campo cuja largura vem na lista de parâmetros(é o valor da expressão 20 - fprintf(...)), cadeia alinhada à esquerda num campo com largura 20, númerodecimal num campo de largura 4, mudar de linha.

Escrever um Driver num ficheiro:



Descarregamento dos pilotos (2)

void dumpDrivers(FILE *f, Driver *p, int n){

while (n––)fprintfDriver(f, p++);

}

void dumpDrivers(FILE *f, Driver *p, int n){

while (n––)fprintfDriver(f, p++);

}

Escrever num ficheiro n elementos de um vector de Driver:


FILE *f_drivers;...

f_drivers = fopen("DRIVERS_AFTER", "w");dumpDrivers(f_drivers, drivers+1, n_drivers);

fclose(f_drivers);...

FILE *f_drivers;...

f_drivers = fopen("DRIVERS_AFTER", "w");dumpDrivers(f_drivers, drivers+1, n_drivers);

fclose(f_drivers);...



Busca linear nos pilotos

int driversindexof(char *name){

extern Driver drivers[];Driver *i;for (i = drivers + 1;

strcmp(i->name, name);++i)

;return i - drivers;

}

int driversindexof(char *name){

extern Driver drivers[];Driver *i;for (i = drivers + 1;

strcmp(i->name, name);++i)

;return i - drivers;

}

Calcular o índice do elemento do vector drivers cujo campo name tem um valordado. O vector drivers não está ordenado por esse campo e portanto usa-se uma busca linear. A busca é garantida, porque onome dado existe de certeza:



Bubblesort do vector dos pilotos

void bubblesortdrivers(void){

extern Driver drivers[];extern int n_drivers;Driver d;Driver *i;Driver *j;for (i = drivers + 2;

i <= drivers + n_drivers;++i)

for (j = drivers + n_drivers;j >= i;––j)

if ((j - 1)->pts < j->pts){d = *(j - 1);*(j - 1) = *j;*j = d;

}}

void bubblesortdrivers(void){

extern Driver drivers[];extern int n_drivers;Driver d;Driver *i;Driver *j;for (i = drivers + 2;

i <= drivers + n_drivers;++i)

for (j = drivers + n_drivers;j >= i;––j)

if ((j - 1)->pts < j->pts){d = *(j - 1);*(j - 1) = *j;*j = d;

}}

O bubblesort baseia-se em percursos linea-res no vector. Por isso, pode programar-se com vantagem usando apontadores:



Variáveis da função main()

main(){

FILE *f_cars;FILE *f_drivers;

int this_number;char this_name[16];int this_index;int these_points;

int i_arrival;

int has_arrived [MAX_DRIVERS + 1] = {0};...

}

main(){

FILE *f_cars;FILE *f_drivers;

int this_number;char this_name[16];int this_index;int these_points;

int i_arrival;

int has_arrived [MAX_DRIVERS + 1] = {0};...

}

Fora da função main só ficam as variáveis que vão ser partilhadas por várias funções. Os ficheiros e as variáveis de controlo pertencem à função main.

a)

b)

c)

d)

a) Declaração dos ficheiros.b) Declaração de variáveis auxiliares.c) Índice do ciclo principal.d) Vector de booleanos para registar os

pilotos que já chegaram. É inicializado a 0na declaração.



Estrutura da função main()

main(){

FILE *f_cars;...f_cars = fopen("CARS_TODAY", "r");n_cars = loadCars(f_cars, cars + 1);fclose(f_cars);


for (i_arrival = 1; i_arrival <= 6;){...++i_arrival;

}

bubblesortdrivers();

f_drivers = fopen("DRIVERS_AFTER", "w");dumpDrivers(f_drivers, drivers+1, n_drivers);fclose(f_drivers);

}

main(){

FILE *f_cars;...f_cars = fopen("CARS_TODAY", "r");n_cars = loadCars(f_cars, cars + 1);fclose(f_cars);


for (i_arrival = 1; i_arrival <= 6;){...++i_arrival;

}

bubblesortdrivers();

f_drivers = fopen("DRIVERS_AFTER", "w");dumpDrivers(f_drivers, drivers+1, n_drivers);fclose(f_drivers);

}



O ciclo principalfor (i_arrival = 1; i_arrival <= 6;){printf("%dº. lugar: ", i_arrival);scanf("%d", &this_number);if (this_number < 0)

break;else if ((this_index =

carsindexof(this_number)) == 0)printf("ERRO: Não participou.\n");

else if (has_arrived[this_number])printf("ERRO: Chegou em %d.º lugar.\n",

has_arrived[this_number]);else

{has_arrived[this_number] = i_arrival;strcpy(this_name, cars[this_index].name);these_points = points(i_arrival);printf("%s, %d ponto%s.\n",

this_name,these_points,these_points > 1 ? "s" : "");

drivers[driversindexof(this_name)].pts +=these_points;

++i_arrival;}

}

for (i_arrival = 1; i_arrival <= 6;){printf("%dº. lugar: ", i_arrival);scanf("%d", &this_number);if (this_number < 0)

break;else if ((this_index =

carsindexof(this_number)) == 0)printf("ERRO: Não participou.\n");

else if (has_arrived[this_number])printf("ERRO: Chegou em %d.º lugar.\n",

has_arrived[this_number]);else

{has_arrived[this_number] = i_arrival;strcpy(this_name, cars[this_index].name);these_points = points(i_arrival);printf("%s, %d ponto%s.\n",

this_name,these_points,these_points > 1 ? "s" : "");

drivers[driversindexof(this_name)].pts +=these_points;

++i_arrival;}

}

Nota: Dar um número de carro negativo manda parar aintrodução de dados. Usa-se quando chegarem ao fim menos de 6 carros.



Exercícios (5)

1. Escrever um programa para afixar no terminal a classificação do campeonato deconstrutores. Os pontos de cada construtor são a soma dos pontos dos pilotos da equipa respectiva. O programa processa o ficheiro depilotos.2. Escrever um programa para criar umficheiro com a lista dos concorrentes que participam na corrida. Cada linha contém onúmero do carro, o nome do piloto (inicial,ponto, apelido), e o nome da equipa, e está ordenado por ordem alfabética das equipas, edentro de cada equipa, por ordem alfabéticados nomes dos pilotos.3. Existe um ficheiro onde se registam os resultados de todos os grandes prémios quese vão realizando. Cada linha desse ficheirotem o número do carro e uma lista de números(com o mesmo comprimento em todas aslinhas) que representam o lugar em que ficouo piloto (0 significa que desistiu e -1 que não entrou). Escrever um programa para actualizar este ficheiro no fim de uma corrida.



Operações com bits

& conjunção bit a bit| disjunção bit a bit^ disjunção exclusiva bit a bit~ complementação de bits<< deslocação para a esquerda>> deslocação para a direita

Aplicam-se a operandos inteiros (int, long,short, char) com ou sem sinal. Normal-mente, usa-se tipos unsigned, para evitar complicações com o bit do sinal na deslo-cação para a direita >>.



Ver os bits (1)

#define BITS_PER_INT 16

typedef char Bitstr[BITS_PER_INT+1];

char *bitsimag(Bitstr s, unsigned n){int i;s[i = BITS_PER_INT] = '\0';while (i––)s[i] = n % 2 + '0', n /= 2;

return s;}

unsigned bitsval(Bitstr s){unsigned n;for (n = 0; *s; ++s)n = 2 * n + *s – '0';

return n;}

Só com aritmética:



Ver os bits (2)

#define BITS_PER_INT 16

typedef char Bitstr[BITS_PER_INT+1];

char *bitsimag(Bitstr s, unsigned n){int i;s[i = BITS_PER_INT] = '\0';while (i--)s[i] = (n & 1) + '0', n >>= 1;

return s;}

unsigned bitsval(Bitstr s){unsigned n;for (n = 0; *s; ++s)n = n << 1 | *s - '0';

return n;}

Com os operadores de bits:

NB: os operadores aritméticos têm precedência sobre os operadores de bits.



Idiomas com bits

O valor do i-ésimo bit do número n:

O número cujos bits são todos 0:

O número cujos bits são todos 1:

O número em que os últimos k bits são 1 eos restantes 0:

0

~0

O número cujos bits são todos 0, excepto oúltimo:

1

~(~0 << k)

(n >> i) & 1



Posicionar bits um a um

Colocar a 1 o i-ésimo bit de uma variável n:

n |= 1 << i

Colocar a 0 o i-ésimo bit de uma variável n:

n &= ~(1 << i)

Trocar o i-ésimo bit de uma variável n:

n ^= 1 << i

Colocar a 1 o bit mais significativo de uma variável n:

n |= ~(~0U >> 1)

Colocar a 0 o bit mais significativo de uma variável n:

n &= ~0U >> 1

Nota: 0U (zero u) é o zero sem sinal (isto é, a constante 0considerada de tipo unsigned int).



Adivinhas…Que fazem as seguintes funções?

unsigned mystery1(unsigned n){return n << 1 | !!(n & ~(~0U>>1));}

unsigned mystery1(unsigned n){return n << 1 | !!(n & ~(~0U>>1));}

unsigned mystery2(unsigned n){return n >> 1 |

(n&1 ? ~(~0U>>1) : 0);}

unsigned mystery2(unsigned n){return n >> 1 |

(n&1 ? ~(~0U>>1) : 0);}

unsigned mystery4(unsigned n){

return ~(~n << 1 >> 1 | ~n & 1);}


return ~(~n << 1 >> 1 | ~n & 1);}


return n << 1 >> 1 | n & 1;}


return n << 1 >> 1 | n & 1;}



Conjuntos em C

Os conjuntos são um conceito elementar da Matemática, e são muito úteis em progra-mação. Em C, o que faz falta são os conjuntosde números naturais, entre 0 e uma constanteSET_MAX. Assim, em primeira aproximação,podemos definir um tipo Set assim:

Set s;

Dada uma variável s de tipo Set:

s[i] valer 1 significará que i pertence ao conjunto s; s[i] valer 0 significará que i nãopertence ao conjunto s.

typedef int Set[SET_MAX + 1];

A expressão i designa um valor do tipo doselementos do conjunto. Pode ser unsignedint, unsigned char, etc. Por exemplo:

typedef unsigned char Setelem;



Operações sobre conjuntos

Pertença:

int Setisin(Setelem, Set);

União, intersecção, diferença:

void Setunion(Set, Set);void Setinter(Set, Set);void Setdiff(Set, Set);

Por convenção, o resultado vem no primeiro argumento. Mas, tal como nas cadeias, con-vém devolver também um apontador para oresultado:

typedef int *SetPtr;

SetPtr Setunion(Set, Set);SetPtr Setinter(Set, Set);SetPtr Setdiff(Set, Set);

União, intersecção, diferença, devolvendo umapontador para o resultado:



Mais operações sobre conjuntosComplementação:SetPtr Setcompl(Set);

Inclusão:int Setissubset(Set, Set);

Cardinalidade:int Setcard(Set);

É vazio?: int Setisempty(Set);

Esvaziar:SetPtr Setclr(Set);



Mais operações sobre conjuntos (cont.)

Duplicação:SetPtr Setcpy(Set, Set);

São iguais? int Setisequal(Set, Set);

Juntar um elemento: SetPtr Setadd(Set, Setelem);

Retirar um elemento: SetPtr Setrm(Set, Setelem);

Também seria útil uma função para juntar vários elementos de uma vez, por exemplo,todos os números de um certo intervalo. Mas esta programar-se-á à base da função Setadd.



Implementação dos conjuntos

Para indicar a presença de um elemento numconjunto basta um bit! Portanto, os conjuntos podem implementar-se por meio de vectoresde bits. Mas em C não há vectores de bits. Por isso, usa-se, por exemplo, vectores de char,sabendo que cada char tem 8 bits. Em geral,número de caracteres num char é dado pela constante CHAR_BIT (ficheiro <limits.h>).

#define SET_DIM SET_MAX/CHAR_BIT+1

typedef unsigned char Set[SET_DIM];typedef unsigned char *SetPtr;typedef unsigned char Setelem;

int Setisin(Setelem x, Set s){return s[x/CHAR_BIT] >>

x % CHAR_BIT & 1;}

Pertença:



União, intersecção, diferençaSetPtr Setunion(Set s0, Set s1){SetPtr r = s0;int i;for (i = 0; i < SET_DIM; ++i)*s0++ |= *s1++;

return r;}

SetPtr Setunion(Set s0, Set s1){SetPtr r = s0;int i;for (i = 0; i < SET_DIM; ++i)*s0++ |= *s1++;

return r;}

SetPtr Setinter(Set s0, Set s1){SetPtr r = s0;int i;for (i = 0; i < SET_DIM; ++i)*s0++ &= *s1++;

return r;}

SetPtr Setinter(Set s0, Set s1){SetPtr r = s0;int i;for (i = 0; i < SET_DIM; ++i)*s0++ &= *s1++;

return r;}

SetPtr Setdiff(Set s0, Set s1){SetPtr r = s0;int i;for (i = 0; i < SET_DIM; ++i)*s0++ &= ~*s1++;

return r;}

SetPtr Setdiff(Set s0, Set s1){SetPtr r = s0;int i;for (i = 0; i < SET_DIM; ++i)*s0++ &= ~*s1++;

return r;}



Inclusão, cardinalidade

int Setissubset(Set s0, Set s1){int i;for (i = 0; i < SET_DIM; ++i)if (*s0++ & ~*s1++)return 0;

return 1;}

int Setissubset(Set s0, Set s1){int i;for (i = 0; i < SET_DIM; ++i)if (*s0++ & ~*s1++)return 0;

return 1;}

int Setcard(Set s){int n = 0;Setelem x;int i;for (i = 0; i < SET_DIM; ++i)for (x = *s++; x; x >>= 1)n += x & 1;

return n;}

int Setcard(Set s){int n = 0;Setelem x;int i;for (i = 0; i < SET_DIM; ++i)for (x = *s++; x; x >>= 1)n += x & 1;

return n;}



Esvaziar, é vazio?, são iguais?SetPtr Setclr(Set s){SetPtr r = s;int i;for (i = 0; i < SET_DIM; ++i)*s++ = 0;

return r;}

SetPtr Setclr(Set s){SetPtr r = s;int i;for (i = 0; i < SET_DIM; ++i)*s++ = 0;

return r;}

int Setisempty(Set s){int i;for (i = 0; i < SET_DIM; ++i)if (*s++)return 0;

return 1;}

int Setisempty(Set s){int i;for (i = 0; i < SET_DIM; ++i)if (*s++)return 0;

return 1;}

int Setisequal(Set s0, Set s1){int i;for (i = 0; i < SET_DIM; ++i)if (*s0++ != *s1++)return 0;

return 1;}

int Setisequal(Set s0, Set s1){int i;for (i = 0; i < SET_DIM; ++i)if (*s0++ != *s1++)return 0;

return 1;}



Duplicar, juntar, retirar

SetPtr Setcpy(Set s0, Set s1){SetPtr r = s0;int i;for (i = 0; i < SET_DIM; ++i)*s0++ = *s1++;

return r;}

SetPtr Setcpy(Set s0, Set s1){SetPtr r = s0;int i;for (i = 0; i < SET_DIM; ++i)*s0++ = *s1++;

return r;}

SetPtr Setadd(Set s, Setelem x){s[x/CHAR_BIT] |=1 << x % CHAR_BIT;

return s;}

SetPtr Setadd(Set s, Setelem x){s[x/CHAR_BIT] |=1 << x % CHAR_BIT;

return s;}

SetPtr Setrm(Set s, Setelem x){s[x/CHAR_BIT] &=~(1 << x % CHAR_BIT);

return s;}

SetPtr Setrm(Set s, Setelem x){s[x/CHAR_BIT] &=~(1 << x % CHAR_BIT);

return s;}



Exemplo: prémios no totoloto#define TOTOLOTO_MAX 49#define SET_MAX TOTOLOTO_MAX



#define TOTOLOTO_MAX 49#define SET_MAX TOTOLOTO_MAX



int hasprize(Set play, Set key){returnSetcard(Setinter(play, key)) >= 3;

}

int hasprize(Set play, Set key){returnSetcard(Setinter(play, key)) >= 3;

}

int hasprize(Set play, Set key){Set tmp;returnSetcard(Setinter(Setcpy(tmp, play), key)) >= 3;

}

int hasprize(Set play, Set key){Set tmp;returnSetcard(Setinter(Setcpy(tmp, play), key)) >= 3;

}

Ou então:



Compilação separada

As definições relativas aos conjuntos devemser agrupadas num ficheiro, compilável separadamente. Os diversos ficheiros que compõem o programa são depois reunidos nomomento da linkagem.

As outras unidades de compilação que usam conjuntos têm que conhecer as definições dostipos e as declarações das funções. Por isso,cria-se um ficheiro header com essas informações, que se inclui (com #include)onde for preciso.

Assim, haverá dois ficheiros-fonte para os conjuntos: o ficheiro header sets.h, e oficheiro com as definições das funçõessets.c. Uma das primeiras linhas do ficheirosets.c será:

#include "sets.h"



O ficheiro header sets.h

#include <limits.h>

#define SET_MAX UCHAR_MAX#define SET_DIM SET_MAX/CHAR_BIT+1

typedef unsigned int Setelem;typedef unsigned char Set[SET_DIM];typedef unsigned char *SetPtr;

int Setisin(Setelem, Set);SetPtr Setunion(Set, Set);SetPtr Setinter(Set, Set);SetPtr Setdiff(Set, Set);SetPtr Setcompl(Set);int Setissub(Set, Set);int Setcard(Set);SetPtr Setclr(Set);int Setisempty(Set);int Setisequal(Set, Set);SetPtr Setcpy(Set, Set);SetPtr Setadd(Set, Setelem);SetPtr Setrm(Set, Setelem);

#include <limits.h>



int Setisin(Setelem, Set);SetPtr Setunion(Set, Set);SetPtr Setinter(Set, Set);SetPtr Setdiff(Set, Set);SetPtr Setcompl(Set);int Setissub(Set, Set);int Setcard(Set);SetPtr Setclr(Set);int Setisempty(Set);int Setisequal(Set, Set);SetPtr Setcpy(Set, Set);SetPtr Setadd(Set, Setelem);SetPtr Setrm(Set, Setelem);

O ficheiro <limits.h> contém as definições de constantes que determinam certos limites dependentes da implemen-tação.



Headers não repetidosPara evitar definir duas vezes a mesma coisano mesmo programa, por inclusão dupla dasmesmas definições (não se pode ter dois typedefs para o mesmo tipo), usa-se oesquema da compilação condicional. Por exemplo, o ficheiro sets.h deveria começar assim:

#include <limits.h>

#ifndef _H_sets#define _H_sets



#endif

int Setisin(Setelem, Set);SetPtr Setunion(Set, Set);...

#include <limits.h>

#ifndef _H_sets#define _H_sets



#endif

int Setisin(Setelem, Set);SetPtr Setunion(Set, Set);...



Exercícios (6)

1. Escrever um programa para escrutinar oTotoloto. O programa pede a chave e o núme-ro suplementar. As apostas estão registadasnum ficheiro, uma por linha, precedidas porum número de identificação. O programa criará cinco ficheiros, um para os primeiros prémios, outros para os segundos, etc. Cada linha de cada um destes ficheiros conterá onúmero de identificação e a aposta premiada. No fim, o programa afixa no terminal o númerode premiados para cada prémio.2. Escrever um programa para gerir o jogo da roda da sorte. O programa começa por pedir afrase secreta. Depois aceita sucessivos palpi-tes, indicando de cada vez quantas letras iguais à indicada existem na frase. Em cada passo o programa mostra as letras já desco-bertas da frase secreta. Para isso, afixa afrase, substituindo cada letra ainda não des-coberta por um sublinhado. (Os espaços apa-recem como tal.) Enquanto houver consoan-tes por descobrir, não se aceita vogais. Oprograma avisa quando acabarem as con-soantes. (Não se pode jogar duas vezes amesma letra.)



Funções utilitárias sobre conjuntosQueremos três funções para juntar vários elementos a um conjunto, com uma só cha-mada: uma para juntar todos os caracteres deuma cadeia, uma para juntar todos os elementos de um intervalo, e uma para juntarum número variável de elementos, passados em argumento.Estas funções não são primitivas: progra-mam-se por intermédio das funções primiti-vas do ficheiro sets.h, sem aceder à repre-sentação dos conjuntos. Vamos reuni-las noficheiro sets_util.c. O ficheiro headerrespectivo, sets_util.h, é assim:

#include "sets.h"

SetPtr Setaddstr(Set, char *);SetPtr Setaddrng

(Set, Setelem, Setelem);SetPtr Setaddn(Set, int, ...);

#include "sets.h"

SetPtr Setaddstr(Set, char *);SetPtr Setaddrng

(Set, Setelem, Setelem);SetPtr Setaddn(Set, int, ...);

Os três pontos na função Setaddn significam que os parâ-metros não são fixos. Neste caso, o segundo parâmetroserve para indicar quantos argumentos suplementares haverá.



Juntar cadeia, juntar intervalo

#include "sets_util.h"

SetPtr Setaddstr(Set s, char *w){while (*w)Setadd(s, (Setelem) *w++);

return s;}

SetPtr Setaddrng(Set s, Setelem x0, Setelem x1)

{while (x0 <= x1)Setadd(s, x0++);

return s;}

...

#include "sets_util.h"

SetPtr Setaddstr(Set s, char *w){while (*w)Setadd(s, (Setelem) *w++);

return s;}

SetPtr Setaddrng(Set s, Setelem x0, Setelem x1)

{while (x0 <= x1)Setadd(s, x0++);

return s;}

...

O ficheiro sets_util.c começa assim:



Listas de argumentosde comprimento variável

Para programar a função Setaddn recorre-seao tipo va_list e às funções va_start,va_arg, e va_end, definidos no ficheiro<stdarg.h>. Com o tipo va_list declara-seuma variável que vai apontar para os suces-sivos argumentos anónimos; com a função va_start faz-se essa variável apontar para oprimeiro desses argumentos (o segundo argu-mento de va_start é o último argumento comnome); com a função va_arg obtém-se o valorde cada argumento; com a função va_endlimpa-se a casa, depois de terminar:

#include "stdarg.h"...

SetPtr Setaddn(Set s, int n, ...){va_list p;va_start(p, n);while (n––)Setadd(s, (Setelem)va_arg(p,int));

va_end(p);return s;}

#include "stdarg.h"...

SetPtr Setaddn(Set s, int n, ...){va_list p;va_start(p, n);while (n––)Setadd(s, (Setelem)va_arg(p,int));

va_end(p);return s;}



Utilização de listas de argumentosde comprimento variável (1)

#include <stdio.h>

#include "sets.h"#include "sets_util.h"

void scankey(Set, int *);void printSet(Set);

main(){Set key;int sup;scankey(key, &sup);printf("Chave: ");printSet(key);printf("\n");printf("Número suplementar: %d\n",

sup);}...

#include <stdio.h>

#include "sets.h"#include "sets_util.h"

void scankey(Set, int *);void printSet(Set);

main(){Set key;int sup;scankey(key, &sup);printf("Chave: ");printSet(key);printf("\n");printf("Número suplementar: %d\n",

sup);}...

Um programa de teste para aceitar a chave e onúmero suplementar, no Totoloto:



Utilização de listas de argumentosde comprimento variável (2)

...

void scankey(Set k, int *ns){int n1, n2, n3, n4, n5, n6;printf("A chave, sff: ");scanf("%d%d%d%d%d%d",

&n1, &n2, &n3,&n4, &n5, &n6);

Setaddn(Setclr(k), 6,n1, n2, n3, n4, n5, n6);

printf("O número suplementar," " sff: ");

scanf("%d", ns);}

void printSet(Set s){int i;for (i = 0; i <= SET_MAX; ++i)if (Setisin(i, s))printf("%d ", i);

}

...

void scankey(Set k, int *ns){int n1, n2, n3, n4, n5, n6;printf("A chave, sff: ");scanf("%d%d%d%d%d%d",

&n1, &n2, &n3,&n4, &n5, &n6);

Setaddn(Setclr(k), 6,n1, n2, n3, n4, n5, n6);

printf("O número suplementar," " sff: ");

scanf("%d", ns);}

void printSet(Set s){int i;for (i = 0; i <= SET_MAX; ++i)if (Setisin(i, s))printf("%d ", i);

}182Programação Avançada com C


Argumentos na linha de comando

Quando se chama um programa C, pode-sepassar-lhe argumentos directamente, escre-vendo-os na linha de comando, a seguir ao nome do programa. Para ir buscar esses argumentos, programa-se a função main comdois parâmetros: o primeiro é o número deargumentos na linha de comando, contandocom o nome do programa; o segundo é um vector de apontadores para esses argu-mentos (que são cadeias de caracteres).Exemplo: um programa para ecoar a linha decomando:

#include <stdio.h>

main(int argc, char **argv){while (argc––)printf(argc ? "%s " : "%s",

*argv++);printf("\n");

}

#include <stdio.h>

main(int argc, char **argv){while (argc––)printf(argc ? "%s " : "%s",

*argv++);printf("\n");

}



TemposO ficheiro <time.h> contém tipos e funções para controlar o tempo:#define CLOCKS_PER_SEC 60

typedef unsigned long clock_t;typedef unsigned long time_t;

struct tm {int tm_sec;int tm_min;int tm_hour;int tm_mday;int tm_mon;int tm_year;int tm_wday;int tm_yday;int tm_isdst;

};

clock_t clock(void);double difftime(time_t, time_t);time_t mktime(struct tm *);time_t time(time_t *);

char *asctime(struct tm *);char *ctime(time_t *);struct tm *gmtime(time_t *);struct tm *localtime(time_t *);size_t strftime

(char *, size_t, char *, struct tm *);

#define CLOCKS_PER_SEC 60

typedef unsigned long clock_t;typedef unsigned long time_t;

struct tm {int tm_sec;int tm_min;int tm_hour;int tm_mday;int tm_mon;int tm_year;int tm_wday;int tm_yday;int tm_isdst;

};

clock_t clock(void);double difftime(time_t, time_t);time_t mktime(struct tm *);time_t time(time_t *);

char *asctime(struct tm *);char *ctime(time_t *);struct tm *gmtime(time_t *);struct tm *localtime(time_t *);size_t strftime




Bom dia, boa tarde, ou boa noite#include <stdio.h>#include <string.h>#include <time.h>

char *hello(int);

main(){time_t now;time(&now);printf("%s\n",

hello(localtime(&now) ->tm_hour));

}

char *hello(int hour){switch((hour + 4) / 8){case 0: case 3:return "boa noite";

case 1:return "bom dia";

case 2:return "bom tarde";

}}

#include <stdio.h>#include <string.h>#include <time.h>

char *hello(int);

main(){time_t now;time(&now);printf("%s\n",

hello(localtime(&now) ->tm_hour));

}

char *hello(int hour){switch((hour + 4) / 8){case 0: case 3:return "boa noite";

case 1:return "bom dia";

case 2:return "bom tarde";

}}



Escrever a data e a horasize_t strftime


size_t strftime(char *, size_t, char *, struct tm *);

1.º arg: resultado.2.º arg: capacidade do resultado.3.º arg: cadeia de formato.4.º arg: o argumento tempo (apontador).

%H hora (00-23)%M minuto (00-56)%S segundo (00-61) (???)%W semana (00-53) (começa à segunda-feira)%Y ano completo%y ano módulo 100 (00-99)%m mês (01-12)%d dia do mês (01-31)%W semana (00-53) (começa à segunda-feira)%w dia da semana (0-6) (domingo é 0)

Especificadores mais usados:

char *strdate(char *s, struct tm *t){

strftime(s, 11, "%Y/%m/%d", t);return s;

}

char *strdate(char *s, struct tm *t){

strftime(s, 11, "%Y/%m/%d", t);return s;

}

char *strtime(char *s, struct tm *t){

strftime(s, 9, "%H:%M:%S", t); return s;

}

char *strtime(char *s, struct tm *t){

strftime(s, 9, "%H:%M:%S", t); return s;

}



Exercícios (7)

1. Escrever uma função para verificar se umprograma já caducou. A função compara a data do dia com o prazo de validade que vem inscrito no programa (num #define). Utilizeessa função no prólogo de um programa, para autorizar o acesso. Permita que um utilizador que conheça a palavra mágica se sirva doprograma, mesmo depois do prazo ter expi-rado. A palavra mágica escreve-se na linha decomando, a seguir ao nome do programa.2. Escreva uma função para construir uma cadeia com uma data em português por extenso, a partir de um apontador para structtm. Por exemplo:quinta–feira, 25 de abril de 1974

A função deve devolver um apontador para oresultado.3. Idem para uma cadeia com a data em formato militar. Por exemplo:25ABR1975

4. Escreva um programa que aceite umnúmero na linha de comando e o escreva por extenso no terminal.



Processamento de texto

Problemas:

1. Contar as palavras de um texto.

2. Determinar o índice de variabilidade voca-bular de um texto (isto é, a razão entre onúmero de palavras diferentes e o número depalavras).

3. Apresentar a tabela de frequências depalavras de um texto, ordenada alfabetica-mente ou por frequência.

4. Criar o índice de um texto, isto é, uma tabela ordenada alfabeticamente onde cada palavrade um texto aparece acompanhada pelo número das linhas em que ocorre.



O ficheiro <stdio.h>

...#define EOF (-1)...int fgetc(FILE *);char *fgets(char *, int, FILE *);int fputc(int, FILE *);int fputs(char *, FILE *);int getc(FILE *);int getchar(void);char *gets(char *);int putc(int, FILE *);int putchar(int);int puts(char *);int ungetc(int, FILE *);...

...#define EOF (-1)...int fgetc(FILE *);char *fgets(char *, int, FILE *);int fputc(int, FILE *);int fputs(char *, FILE *);int getc(FILE *);int getchar(void);char *gets(char *);int putc(int, FILE *);int putchar(int);int puts(char *);int ungetc(int, FILE *);...

Importante: as funções que devolvem carac-teres devolvem-nos através do tipo int. Isto éassim porque em caso de erro ou de fim deficheiro elas devolvem EOF, que vale -1.

NB: A função fgets inclui o newline nacadeia; a função gets não. A função putsacrescenta um newline ao escrever; a função fputs não.



O ficheiro <ctype.h>

...int isalnum(int);int isalpha(int);int iscntrl(int);int isdigit(int);int isgraph(int);int islower(int);int isprint(int);int ispunct(int);int isspace(int);int isupper(int);int isxdigit(int);

int tolower(int);int toupper(int);...

...int isalnum(int);int isalpha(int);int iscntrl(int);int isdigit(int);int isgraph(int);int islower(int);int isprint(int);int ispunct(int);int isspace(int);int isupper(int);int isxdigit(int);

int tolower(int);int toupper(int);...

Estas funções processam caracteres atravésdo tipo int. Os argumentos devem sercaracteres unsigned char ou EOF.No código ASCII de sete bits, os caracteres visíveis vão desde o espaço (32) até ao til (126). Os caracteres decontrolo vão desde NUL (0) a US (31) e ainda incluem o DEL(127). Os caracteres gráficos são os visíveis excepto oespaço. Os espaços são o espaço, o formfeed, o newline, o carriage return, o tab, e o tab vertical.



Ler palavras

Uma palavra é (por hipótese) uma sequência“maximal” de letras, algarismos e sublinha-dos contíguos.

Ao ler uma palavra pode-se chegar ao fim doficheiro. Convém avisar. Assim, por conven-ção, a função devolverá o carácter que já não pertence à palavra, ou EOF.

int ReadWord(FILE *f, char *s){int c;while (c = getc(f),

isalnum(c) || c == '_')*s++ = c;

*s = '\0';return ungetc(c, f);

}

int ReadWord(FILE *f, char *s){int c;while (c = getc(f),

isalnum(c) || c == '_')*s++ = c;

*s = '\0';return ungetc(c, f);

}

A função ungetc devolve o carácter que “regressa” ao ficheiro, ou EOF.

A cadeia apontada pelo argumento s deve ter capacidade para a palavra lida. Senão…



Saltar os caracteres entre palavrasOs caracteres entre duas palavras consecuti-vas podem ser ignorados. Trata-se de carac-teres de pontuação (excepto o sublinhado), decontrolo, ou espaços. A função devolve ocarácter que já não ignora ou EOF:

int SkipChars(FILE *f){int c;while (c = getc(f),

isspace(c) ||ispunct(c) && c != '_' ||iscntrl(c))

;return ungetc(c, f);

}

int SkipChars(FILE *f){int c;while (c = getc(f),

isspace(c) ||ispunct(c) && c != '_' ||iscntrl(c))

;return ungetc(c, f);

}

Esta função não dá pelos fins de linha!

Variantes: contar os caracteres ignorados; contar os fins de linha.



Contar as palavrasNo início de um ficheiro pode haver carac-teres para ignorar. Depois desses, o ficheiro éuma alternância de palavras e sequências decaracteres para ignorar:...char s[256];FILE *f;int n;int c;...n = 0;while (c = SkipChars(f), c != EOF){ReadWord(f, s);++n;

}printf("Número de palavras: %d", n);...

...char s[256];FILE *f;int n;int c;...n = 0;while (c = SkipChars(f), c != EOF){ReadWord(f, s);++n;

}printf("Número de palavras: %d", n);...

...for (n = 0;

c = SkipChars(f), c != EOF;++n)

ReadWord(f, s);...

...for (n = 0;

c = SkipChars(f), c != EOF;++n)

ReadWord(f, s);...

Podia usar-se um ciclo for:



Determinar o índice de variabilidadePara contar o número de palavras diferentes épreciso memorizar as palavras que vão aparecendo. Usa-se dois contadores: o daspalavras, como no problema anterior, e o daspalavras diferentes, que só é incrementado quando surge uma palavra nova.Ou então, conta-se o número de ocorrênciasde cada palavra. No fim conta-se as palavras e soma-se as ocorrências. Isto dá um pouco mais trabalho, mas serve já para o problema seguinte (fazer a tabela de frequências).Precisamos de um vector de contadores deocorrências de palavras. Cada um destes contadores tem dois campos: a palavra e ocontador:

typedef struct {char *word;int count;} Counter;

typedef struct {char *word;int count;} Counter;

A palavra é um apontador para uma cadeia que será criada dinamicamente.



Apontadores para contadores

Os contadores são estruturas. Ao passá-los como argumentos a funções, vamos usar apontadores:

Vai ser preciso ordenar o vector dos contado-res, de duas maneiras. Para maior generali-dade, usaremos um vector de apontadores para contadores:

typedef Counter *Item;typedef Counter *Item;

#define MAX_TABLE 256

Item items[MAX_TABLE];int n_items;

#define MAX_TABLE 256

Item items[MAX_TABLE];int n_items;

Os contadores apontados pelos elementos deste vector serão criados dinamicamente.



As funções malloc e calloc

void *malloc(size_t size);void *malloc(size_t size);

void *calloc(size_t n, size_t size);void *calloc(size_t n, size_t size);

A função calloc devolve um apontador paraum espaço inicializado a zero onde cabem nobjectos de tamanho size, ou NULL, se nãofor possível.

A função malloc devolve um apontador paraum espaço onde cabe um objecto de tamanhosize, ou NULL, se não for possível.

O tipo void * é um tipo genérico, usado nas funções para argumentos e resultados apontadores. Qualquer tipo apontador podeser convertido para void *, e inversamente,sem perda de informação.

O tipo void * é um tipo genérico, usado nas funções para argumentos e resultados apontadores. Qualquer tipo apontador podeser convertido para void *, e inversamente,sem perda de informação.



Criação de cadeias dinâmicas

char *strnew(char *s){return strcpy((char*)malloc(strlen(s)+1), s);

}

char *strnew(char *s){return strcpy((char*)malloc(strlen(s)+1), s);

}

Uma função para criar uma cadeia nova, iguala uma cadeia s, devolvendo um apontador para a cadeia criada:

Uma função para criar uma cadeia nova, apartir dos n primeiros caracteres de uma cadeia s, devolvendo um apontador para acadeia criada:

char *strnewn(char *s, size_t n){return strncpy((char*)calloc(n+1, 1), s, n);

}

char *strnewn(char *s, size_t n){return strncpy((char*)calloc(n+1, 1), s, n);

}

Não há problemas com o terminador '\0', porque o espaçoé inicializado a zero.



Operações sobre contadoresCriar um contador novo, a partir de uma cadeia, devolvendo o apontador. Paradescobrir o tamanho de uma variável de tipoCounter, usa-se o operador sizeof:

Counter *NewCounter(char *s){Counter *x =(Counter *)malloc(

sizeof(Counter));x -> word = strnew(s);x -> count = 0;return x;

}

Counter *NewCounter(char *s){Counter *x =(Counter *)malloc(

sizeof(Counter));x -> word = strnew(s);x -> count = 0;return x;

}

Incrementar o contador:

void IncCounter(Counter *x){

++x -> count;}

void IncCounter(Counter *x){

++x -> count;}

Estas funções vêm definidas nos ficheiro counter.c, com header counter.h.



A tabela de contadores

#include "table.h"#define MAX_TABLE 256

static Item items[MAX_TABLE];static int n_items;

#include "table.h"#define MAX_TABLE 256

static Item items[MAX_TABLE];static int n_items;

São as seguintes as operações que nos inte-ressam a respeito da tabela dos contadores:limpar; contabilizar uma palavra; calcular onúmero de ocorrências; calcular o número depalavras.Para evitar que operações definidas noutros ficheiros mexam directamente na tabela,declaramo-la static na sua unidade decompilação table.c:

O ficheiro table.h é assim:

void ClearTable(void);void EnterWord(char *);int NumberOfItems(void);int NumberOfEntries(void);

void ClearTable(void);void EnterWord(char *);int NumberOfItems(void);int NumberOfEntries(void);



As operações na tabela (1)

int NumberOfItems(void){return n_items;

}

int NumberOfItems(void){return n_items;

}

Em vez de somar todas as ocorrências, é mais prático manter um contador total:

static int n_entries;static int n_entries;

int NumberOfEntries(void){return n_entries;

}

int NumberOfEntries(void){return n_entries;

}

void ClearTable(void){n_items = 0;n_entries = 0;

}

void ClearTable(void){n_items = 0;n_entries = 0;

}

Limpar a tabela é anular os dois contadores gerais:



As operações na tabela (2)

void EnterWord(char *s){int i;for (i = 0, items[n_items] =

NewCounter(s);strcmp(items[i] -> word, s);++i)

;IncCounter(items[i]);n_items += i == n_items;++n_entries;

}

void EnterWord(char *s){int i;for (i = 0, items[n_items] =

NewCounter(s);strcmp(items[i] -> word, s);++i)

;IncCounter(items[i]);n_items += i == n_items;++n_entries;

}

Para contabilizar uma palavra usamos a téc-nica da sentinela: colocamos um contadornovo na primeira posição livre; procuramos apalavra com a certeza de encontrar; incre-mentamos o contador respectivo; incrementa-mos o contador de ocorrências e o daspalavras, este só a palavra for nova:

Ver as variantes a seguir.



Libertar espaço

void free(void *p);void free(void *p);

Os contadores criados de novo que não são utilizados ficam desaproveitados. É melhor libertar a espaço que eles ocupam. Para isso,existe a função free:

A função free desaloca o espaço apontado pelo seu argumento, espaço esse que deve sersido alocado anteriormente pelas funções malloc ou calloc.Para desalocar um contador, primeiro desaloca-se a cadeia, depois o contador:

void FreeCounter(Counter *x){free(x -> word);free(x);

}

void FreeCounter(Counter *x){free(x -> word);free(x);

}

Exemplo de utilização a seguir.



Percorrer vectores com apontadores

Nota: (*p) -> word é o mesmo que(**p).word.

void EnterWord(char *s){Item *p;for (p = items, items[n_items] =

NewCounter(s);strcmp((*p) -> word, s);++p)

;IncCounter(*p);if (p == items + n_items)++n_items;

elseFreeCounter(items[n_items]);

++n_entries;}

void EnterWord(char *s){Item *p;for (p = items, items[n_items] =

NewCounter(s);strcmp((*p) -> word, s);++p)

;IncCounter(*p);if (p == items + n_items)++n_items;

elseFreeCounter(items[n_items]);

++n_entries;}

Normalmente, quando se percorre um vectorlinearmente é melhor usar apontadores:



Contagens no textoO programa para calcular o índice de variabili-dade deve também dizer quantos caracterestem o texto, e quantas linhas.Para isso, é preciso modificar a função SkipChars, pois ela não repara nos fins delinha. Faz falta uma função que ignore carac-teres dentro de uma linha, mas que os conte:

int SkipCharsInLine(FILE *f, int *n){int c;int k = 0;while ((c = getc(f)) != '\n' &&

(isspace(c) ||ispunct(c) && c != '_' ||iscntrl(c)))

++k;*n = k;return ungetc(c, f);

}

int SkipCharsInLine(FILE *f, int *n){int c;int k = 0;while ((c = getc(f)) != '\n' &&

(isspace(c) ||ispunct(c) && c != '_' ||iscntrl(c)))

++k;*n = k;return ungetc(c, f);

}



Processar texto linha a linhaÉ preciso cuidado com a última linha, que pode não terminar com newline:...char s[256];FILE *f;int nl, nc;int n;int c;int np, npd;...nl = 0;nc = 0;ClearTable();while (ungetc(getc(f), f) != EOF)

{++nl;while (c = SkipCharsInLine(f, &n),

nc += n,c != EOF && c != '\n')

{ReadWord(f, s);nc += strlen(s);EnterWord(s);

}getc(f);

}npd = NumberOfItems();np = NumberOfEntries();printf(...);...

...char s[256];FILE *f;int nl, nc;int n;int c;int np, npd;...nl = 0;nc = 0;ClearTable();while (ungetc(getc(f), f) != EOF)

{++nl;while (c = SkipCharsInLine(f, &n),

nc += n,c != EOF && c != '\n')

{ReadWord(f, s);nc += strlen(s);EnterWord(s);

}getc(f);

}npd = NumberOfItems();np = NumberOfEntries();printf(...);...



A tabela das frequênciasPara imprimir a tabela das frequências, basta ordenar a tabela dos contadores de acordocom o critério (alfabético crescente ou fre-quência decrescente), e escrever os contado-res, um a um. A função de ordenação tem queser parametrizada com a função de ordem:

static void BubblesortTable(int(*f)(Item, Item))

{Item m;Item *i;Item *j;for (i = items+1;

i <= items + n_items - 1;++i)

for (j = items + n_items - 1;j >= i;--j)

if (!f(*(j-1), *j)){m = *(j-1);*(j-1) = *j;*j = m;}

}

static void BubblesortTable(int(*f)(Item, Item))

{Item m;Item *i;Item *j;for (i = items+1;

i <= items + n_items - 1;++i)

for (j = items + n_items - 1;j >= i;--j)

if (!f(*(j-1), *j)){m = *(j-1);*(j-1) = *j;*j = m;}



As funções de ordem

int itemltword(Item x, Item y){returnstrcmp(x->word, y->word) <= 0;

}

int itemltword(Item x, Item y){returnstrcmp(x->word, y->word) <= 0;

}

int itemgtcount(Item x, Item y){returnx->count > y->count ||x->count == y->count &&strcmp(x->word, y->word) <= 0;

}

int itemgtcount(Item x, Item y){returnx->count > y->count ||x->count == y->count &&strcmp(x->word, y->word) <= 0;

}

Ordem alfabética crescente:

Ordem decrescente das frequências, e depois ordem alfabética crescente:

Estas funções vêm definidas nos ficheiro item.c, com header item.h.



Afixar a tabela

void printfItem(char *fmt, Item x){printf(fmt, x->word, x->count);

}

void printfItem(char *fmt, Item x){printf(fmt, x->word, x->count);

}

Uma função com formato paramétrico para escrever um Item (item_io.c):

A função que afixa a tabela (table.c):

void PrintTable(void){int i = n_items;Item *p = items;while (i––)printfItem("%s %d\n", *p++);

}

void PrintTable(void){int i = n_items;Item *p = items;while (i––)printfItem("%s %d\n", *p++);

}

A função que afixa a tabela ordenada:

void PrintTableSorted(int(*f)(Item, Item))

{BubblesortTable(f);PrintTable();

}

void PrintTableSorted(int(*f)(Item, Item))

{BubblesortTable(f);PrintTable();

}



Operações genéricas paravectores de apontadores (1)

void BubblesortPointers(void **v,size_t n,int(*f)(void *, void *))

{void *m;void **i;void **j;for (i = v+1;

i <= v + n – 1;++i)

for (j = v + n – 1;j >= i;––j)

if (!f(*(j–1), *j)){m = *(j–1);*(j–1) = *j;*j = m;

}}

void BubblesortPointers(void **v,size_t n,int(*f)(void *, void *))

{void *m;void **i;void **j;for (i = v+1;

i <= v + n – 1;++i)

for (j = v + n – 1;j >= i;––j)

if (!f(*(j–1), *j)){m = *(j–1);*(j–1) = *j;*j = m;

}}

Bubblesort:

Esta função e as seguintes devem ser reunidas num ficheiro parray.c, com header parray.h.




void QuicksortPointers(void **v,size_t n,int(*f)(void *, void *))

{void **i = v;void **j = v + n – 1;void *a = *(i + (j – i) / 2);void *m;do{while (!f(a, *i))++i;

while (!f(*j, a))––j;

if (i <= j){m = *i;*i++ = *j;*j–– = m;

}}

while (i <= j);if (v < j)QuicksortPointers(v, j – v + 1, f);

if (i < v + n - 1)QuicksortPointers(i, v + n - i, f);

}

void QuicksortPointers(void **v,size_t n,int(*f)(void *, void *))

{void **i = v;void **j = v + n – 1;void *a = *(i + (j – i) / 2);void *m;do{while (!f(a, *i))++i;

while (!f(*j, a))––j;

if (i <= j){m = *i;*i++ = *j;*j–– = m;

}}

while (i <= j);if (v < j)QuicksortPointers(v, j – v + 1, f);

if (i < v + n - 1)QuicksortPointers(i, v + n - i, f);

}

Quicksort (só para especialistas…):




void ClearPointers(void **v, size_t n)

{while (n––)*v++ = NULL;

}

void ClearPointers(void **v, size_t n)

{while (n––)*v++ = NULL;

}

Limpar:

Construir um vector de apontadores v para osn primeiros elementos de um vector p; otamanho de cada elemento é s:

void BuildPointers(void **v,void *p, size_t n,size_t s)

{char *i;for (i=(char *)p; n; ––n, i+=s)*v++ = (void *)i;

}

void BuildPointers(void **v,void *p, size_t n,size_t s)

{char *i;for (i=(char *)p; n; ––n, i+=s)*v++ = (void *)i;

}




void *FirstPointer(void **v,size_t n,int(*f)(void *))

{for (; n--; ++v)if (f(*v))return *v;

return NULL;}

void *FirstPointer(void **v,size_t n,int(*f)(void *))

{for (; n--; ++v)if (f(*v))return *v;

return NULL;}

O primeiro apontador que satisfaz uma função paramétrica:

void IteratePointers(void **v,size_t n,void(*f)(void *))

{while (n--)f(*v++);

}

void IteratePointers(void **v,size_t n,void(*f)(void *))

{while (n--)f(*v++);

}

Um iterador (uma função que aplica uma função paramétrica a cada elemento de um vector):



Utilização das operações genéricas

static void displayItem(Item x){

printfItem("%s %d\n", x);}

void PrintTable(void){

IteratePointers((void **)items, n_items,displayItem);

}

static void displayItem(Item x){

printfItem("%s %d\n", x);}

void PrintTable(void){

IteratePointers((void **)items, n_items,displayItem);

}

static void QuicksortTable(int(*f)(Item,Item))

{SortPointers((void**)items, n_items, f);

}

void PrintTableSorted(int(*f)(Item, Item)){

QuicksortTable(f);PrintTable();

}

static void QuicksortTable(int(*f)(Item,Item))

{SortPointers((void**)items, n_items, f);

}

void PrintTableSorted(int(*f)(Item, Item)){

QuicksortTable(f);PrintTable();

}

Afixar a tabela:

Ordenar a tabela:

Importante: o operador de conversão (void **) é indispen-sável: só as conversões para void * é que são implícitas.



Exercícios (8)

1. Aperfeiçoar os programas de contagem para que eles possam processar devidamente programas em C, ignorando as linhas para opré-processador (começam por #), os comen-tários (entre /* e */), as cadeias de carac-teres constantes (entre " e "), e os caracteres constantes (entre ' e ').2. Idem, em relação a textos escritos em português: não distinguir entre maiúsculas eminúsculas, ignorar acentos e cedilhas, não distinguir entre singular e plural, e entre ostempos de um mesmo verbo (?).3. Escrever um programa para processar umtexto em português, garantindo que entre cada duas palavras consecutivas fica apenas umespaço.4. Escrever um programa para processar umtexto em português, afixando no terminaltodas as palavras que ocorram mais que duas vezes no mesmo parágrafo. Os parágrafos estão separados uns dos outros por linhas em branco. Há uma lista de excepções, com aspalavras que não interessa controlar.



Processar texto linha a linhacom as funções fgets e strtok (1)

char *fgets(char *s,int n,FILE *f);char *fgets(char *s,int n,FILE *f);

A função fgets lê de uma linha de um ficheirof quanto muito n–1 caracteres colocando-os na cadeia s, parando se encontrar um newline,o qual também vai para a cadeia:

Às vezes, é preciso retirar o newline (se estiver lá):

char *strnlrm(char *s){

char *p = s;if ((s = strchr(s, '\n')) != NULL)*s = '\0';

return p;}

char *strnlrm(char *s){

char *p = s;if ((s = strchr(s, '\n')) != NULL)*s = '\0';

return p;}

Esquema para processar linha a linha:

while (fgets(line, 256, f) != NULL){strnlrm(line);...

}

while (fgets(line, 256, f) != NULL){strnlrm(line);...

}




char *strtok(char *s, char *r);char *strtok(char *s, char *r);

A função strtok serve para percorrer uma cadeia s “extraindo” pedaços (tokens)delimitados pelos caracteres da cadeia r:

Para obter todos os tokens de uma cadeia,chama-se a função strtok sucessivamente,até ela dar NULL. Da primeira vez o primeiro argumento é a cadeia a processar; das seguin-tes é NULL. O segundo argumento contém os delimitadores, e pode variar de uma chamada para a outra.Esquema para obter tokens:

#define DELIMITERS " ,.;:?!()"...

p = strtok(line, DELIMITERS);while (p != NULL){printf("%s\n", p); /* por exemplo */p = strtok(NULL, DELIMITERS);

}

#define DELIMITERS " ,.;:?!()"...

p = strtok(line, DELIMITERS);while (p != NULL){printf("%s\n", p); /* por exemplo */p = strtok(NULL, DELIMITERS);

}

Importante: a cadeia tokenizada fica modificada, pois afunção inscreve '\0' para marcar o fim de cada token.




#define DELIMITERS \" \t,.;:()?![]{}<>#%^|+–*/=~&'\"\\"

...char s[256];FILE *f;int nl, nc;int np, npd;...nl = 0;nc = 0;ClearTable();while (fgets(line, 256, f) != NULL)

{strnlrm(line);++nl;nc += strlen(line);p = strtok(line, DELIMITERS);while (p != NULL){EnterWord(p);p = strtok(NULL, DELIMITERS);

}}

npd = NumberOfItems();np = NumberOfEntries();printf(...);...

#define DELIMITERS \" \t,.;:()?![]{}<>#%^|+–*/=~&'\"\\"

...char s[256];FILE *f;int nl, nc;int np, npd;...nl = 0;nc = 0;ClearTable();while (fgets(line, 256, f) != NULL)

{strnlrm(line);++nl;nc += strlen(line);p = strtok(line, DELIMITERS);while (p != NULL){EnterWord(p);p = strtok(NULL, DELIMITERS);

}}

npd = NumberOfItems();np = NumberOfEntries();printf(...);...

Assim:



Estruturas auto-referenciadas, listas

Listas:

typedef struct lnode *List;typedef struct lnode {

Item value;List next;} listnode;

typedef struct lnode *List;typedef struct lnode {

Item value;List next;} listnode;

3 8 4



Estruturas auto-referenciadas, árvoresÁrvores:

typedef struct lnode *Tree;typedef struct lnode {

Item value;Tree sub[2];} treenode;

typedef enum {left, right} Child;

typedef struct lnode *Tree;typedef struct lnode {

Item value;Tree sub[2];} treenode;

typedef enum {left, right} Child;

4

3 12

2 9 18

5



Operações primitivas com listas

List listcpy(List *, List);List listnew(Item);List listclr(List *);List listcons(Item, List *);List listswtl(List s, List *t);int listlen(List);List liststhd(List, Item);int listnull(List);Item listhead(List);List listtail(List);

List listcpy(List *, List);List listnew(Item);List listclr(List *);List listcons(Item, List *);List listswtl(List s, List *t);int listlen(List);List liststhd(List, Item);int listnull(List);Item listhead(List);List listtail(List);

a)b)c)d)e)f)g)h)i)j)

a) duplicar a segunda lista para a primeira;b) fazer uma lista nova com o item;c) limpar a lista;d) colocar o item à cabeça da lista;e) trocar a cauda da primeira lista com a

segunda;f) o comprimento da lista;g) substituir a cabeça da lista pelo item;h) a lista é vazia?i) o item que está à cabeça da lista;j) a cauda da lista.



Fazer uma lista nova, listnew

Aloca-se o espaço para um nó com a função malloc; coloca-se o item no membro value eNULL no membro next; devolve-se o apon-tador para o espaço alocado:

List listnew(Item x){List p =(List) malloc(sizeof(listnode));p -> value = x;p -> next = NULL;return p;

}

List listnew(Item x){List p =(List) malloc(sizeof(listnode));p -> value = x;p -> next = NULL;return p;

}

8

88

x

x

Antes:

Depois:



Duplicar uma lista, listcpySe a lista fonte é vazia, a lista destino é vazia; se não, a cabeça da lista destino é um dupli-cado da cabeça da lista fonte; percorre-se oresto da lista fonte, pendurando sucessiva-mente no fim da lista destino duplicados doselementos por onde vai passando:

List listcpy(List *s, List t){List p;if (t == NULL)*s = NULL;else{*s = listnew(t->value);p = *s;t = t->next;while (t != NULL){p->next = listnew(t->value);p = p->next;t = t->next;

}}return *s;

}

List listcpy(List *s, List t){List p;if (t == NULL)*s = NULL;else{*s = listnew(t->value);p = *s;t = t->next;while (t != NULL){p->next = listnew(t->value);p = p->next;t = t->next;

}}return *s;



Listas vazias, listclr, listnull

Limpar uma lista é fazê-la ser o apontadorNULL:

List listclr(List *s){return *s = NULL;

}

List listclr(List *s){return *s = NULL;

}

Uma lista está vazia quando o seu valor for oapontador NULL:

int listnull(List s){return s == NULL;

}

int listnull(List s){return s == NULL;

}



Juntar à cabeça, listconsMudar a cabeça, liststhd

Para juntar um novo item à cabeça de uma lista, cria-se um novo nó, pondo o item nomembro value, e a lista no membro next;devolve-se o apontador para o nó recém- -criado:

List listcons(Item x, List *s){List p = listnew(x);p -> next = *s;return *s = p;

}

List listcons(Item x, List *s){List p = listnew(x);p -> next = *s;return *s = p;

}

Muda-se o valor da cabeça, mudando o valordo membro value do nó apontado:

List liststhd(List s, Item x){s -> value = x;return s;

}

List liststhd(List s, Item x){s -> value = x;return s;

}

Só para listas não vazias!



Trocar a cauda, listswtlTroca-se o membro next da primeira listacom a segunda lista: List listswtl(List s, List *t){List p;p = s -> next;s -> next = *t;*t = p;return s;

}

List listswtl(List s, List *t){List p;p = s -> next;s -> next = *t;*t = p;return s;

}

1 2

3 4 5

1 2

3 4 5

Antes:

Depois:

s

t

s

t

Só se a primeira lista não for vazia!



A cabeça, listheadA cauda, listtail

O valor da cabeça é o valor do membro valuedo nó apontado pela lista:

Item listhead(List s){return s -> value;

}

Item listhead(List s){return s -> value;

}

A cauda de uma lista é o membro next do nó apontado pela lista:

List listtail(List s){return s -> next;

}

List listtail(List s){return s -> next;

}





O comprimento, listlen

O comprimento é o número de nós na lista. Para o calcular, percorre-se a lista até ao fim,contando os nós:

int listlen(List s){int n;for (n = 0; s != NULL; ++n)s = s -> next;

return n;}

int listlen(List s){int n;for (n = 0; s != NULL; ++n)s = s -> next;

return n;}

Ou então…:

int listlen(List s){

returns == NULL ? 0 :

1 + listlen(s -> next);}

int listlen(List s){

returns == NULL ? 0 :

1 + listlen(s -> next);}



Concatenação de listasConcatenar duas listas não é uma operação primitiva. Programa-se melhor sem mexer nos apontadores, recorrendo apenas às funções anteriores.Para concatenar duas listas troca-se a caudado pé da primeira lista com a segunda lista. Opé de uma lista (não vazia) é a lista unitária que está no fim:

List listfoot(List s){while (!listnull(listtail(s)))s = listtail(s);

return s;}

List listfoot(List s){while (!listnull(listtail(s)))s = listtail(s);

return s;}

List listcat(List *s, List t){if (listnull(*s))*s = t;

elselistswtl(listfoot(*s), &t);

return *s;}

List listcat(List *s, List t){if (listnull(*s))*s = t;

elselistswtl(listfoot(*s), &t);

return *s;}

Concatenação (append):



Exercícios (9)

1. Escrever funções utilitárias sobre listas para:

a) devolver um apontador para o i-ésimo elemento da lista;

b) partir uma lista em duas, antes do i-ésimo elemento (i >= 2);

c) inserir um elemento novo, a seguir ao i-ésimo elemento;

d) inserir uma lista noutra, a seguir ao i-ésimo elemento;

e) devolver o apontador para o primeiro elemento com um certo valor, ou NULL, senão houver;

f) devolver o apontador para o primeiro elemento maior ou igual a um certo valor,ou NULL, se não houver;

g) devolver o apontador para o elementoanterior ao primeiro elemento maior ou igual a um certo valor, ou para o pé da listase não houver, tudo na hipótese de acabeça da lista ser menor que esse valor;

h) inserir um elemento numa lista ordenada.i) inverter uma lista.



Operações primitivas com árvores

Tree treenew(Item);Tree treeclr(Tree *);Tree treecpy(Tree *, Tree);Tree treecons(Item, Tree *, Child);Item treeroot(Tree);Tree treestrt(Tree, Item);Tree treechld(Tree, Child);int treenull(Tree);Tree treeins(Item, Tree *);

void treepre (Tree, void(*)(Item));void treein (Tree, void(*)(Item));void treepost(Tree, void(*)(Item));

Tree treenew(Item);Tree treeclr(Tree *);Tree treecpy(Tree *, Tree);Tree treecons(Item, Tree *, Child);Item treeroot(Tree);Tree treestrt(Tree, Item);Tree treechld(Tree, Child);int treenull(Tree);Tree treeins(Item, Tree *);

void treepre (Tree, void(*)(Item));void treein (Tree, void(*)(Item));void treepost(Tree, void(*)(Item));

a)b)c)d)e)f)g)h)i)

j)k)l)

a) fazer uma árvore nova com o item;b) limpar a árvore;c) duplicar a segunda árvore para a primeira;d) fazer um novo nó para a raiz, colocando lá o

item, e pendurando a árvore no lado indicado;e) o item que está na raiz da árvore;f) substituir a raiz da árvore pelo item;g) a subárvore do lado indicado;h) a árvore é vazia?i) inserir um elemento na árvore;j) percorrer a árvore prefixamente;k) percorrer a árvore infixamente;l) percorrer a árvore posfixamente.



Fazer uma árvore nova, treenewAloca-se o espaço para um nó com a função malloc; coloca-se o item no membro value eNULL nos dois membros sub; devolve-se oapontador para o espaço alocado:

Tree treenew(Item x){Tree p = (Tree)malloc(sizeof(treenode));p -> value = x;p -> sub[left] = p -> sub[right] = NULL;

return p;}

Tree treenew(Item x){Tree p = (Tree)malloc(sizeof(treenode));p -> value = x;p -> sub[left] = p -> sub[right] = NULL;

return p;}

8

88

x

x

Antes:

Depois:

*(p->sub+1) = *p->sub = NULL;*(p->sub+1) = *p->sub = NULL; ?



Duplicar uma árvore, treecpySe a árvore é vazia, o resultado é uma árvore vazia; se não, cria-se um nó novo com o valor da raiz e depois duplica-se cada uma dassubárvores para as subárvores do nó recém-criado:

Tree treecpy(Tree *s, Tree t){if (t == NULL)*s = NULL;

else{*s = treenew(t -> value);treecpy(&(*s) -> sub[left],

t -> sub[left]);treecpy(&(*s) -> sub[right],

t -> sub[right]);}

return *s;}

Tree treecpy(Tree *s, Tree t){if (t == NULL)*s = NULL;

else{*s = treenew(t -> value);treecpy(&(*s) -> sub[left],

t -> sub[left]);treecpy(&(*s) -> sub[right],

t -> sub[right]);}

return *s;}



Árvores vazias, treeclr, treenull

Limpar uma árvore é fazê-la ser o apontadorNULL:

Tree treeclr(Tree *s){return *s = NULL;

}

Tree treeclr(Tree *s){return *s = NULL;

}

Uma árvore está vazia quando o seu valor for o apontador NULL:

int treenull(Tree s){return s == NULL;

}

int treenull(Tree s){return s == NULL;

}



Crescer pela raiz, treecons

Para crescer pela raiz, cria-se um novo nó,pondo o item no membro value, e pendura- -se a árvore no lado indicado; devolve-se oapontador para o nó recém-criado:

Tree treecons(Item x,Tree *s,Child c){Tree t = treenew(x);t -> sub[c] = *s;return *s = t;

}

Tree treecons(Item x,Tree *s,Child c){Tree t = treenew(x);t -> sub[c] = *s;return *s = t;

}

6

3 8

7

s

6

3 8

7

s 9

Antes: Depois:treecons(9, s, left);



A raiz, treerootOs ramos, treechld

Mudar a raiz, treestrt

Muda-se o valor da raiz, mudando o valor domembro value do nó apontado pela árvore: Tree treestrt(Tree s, Item x){s -> value = x;return s;

}

Tree treestrt(Tree s, Item x){s -> value = x;return s;

}

O valor da raiz é o valor do membro value donó apontado pela árvore: Item treeroot(Tree s){return s -> value;

}

Item treeroot(Tree s){return s -> value;

}

O ramo da esquerda ou da direita é membrosub[left] ou sub[right] do nó apontado pela árvore: Tree treechld(Tree s, Child c){return s -> sub[c];

}

Tree treechld(Tree s, Child c){return s -> sub[c];

}

Tudo só paraárvoresnãovazias!



Árvores ordenadasUma árvore ordenada é uma árvore em que araiz de cada subárvore é maior que todas asraízes de subárvores à esquerda e menor que todas as raízes de subárvores à direita. Por exemplo:

6

3 8

71 10

14

Ao inserir um item numa árvore ordenada, épreciso garantir que a árvore continua orde-nada. Por exemplo, o item 5 seria penduradoà direita do 3; o item 9 à esquerda do 10; o item 12 à esquerda do 14.



Inserir um item numa árvoreSe a árvore for vazia, constrói-se uma novaárvore só com o item, e devolve-se; se não, se o item for igual à raiz, não se faz nada (não há repetições), mas devolve-se a árvore; se não,insere-se na subárvore esquerda ou na direita conforme o item for menor ou for maior que araiz.Tem que haver uma função de ordem para otipo Item, e uma função de igualdade:

int itemlt(Item, Item); /* <= */int itemeq(Item, Item); /* == */int itemlt(Item, Item); /* <= */int itemeq(Item, Item); /* == */

Por exemplo, com os itens usados noproblema do processamento de texto, seria:

int itemlt(Item x, Item y){

returnstrcmp(x -> word, y -> word) <= 0;

}

int itemlt(Item x, Item y){

returnstrcmp(x -> word, y -> word) <= 0;

}

int itemeq(Item x, Item y){

returnstrcmp(x -> word, y -> word) == 0;

}

int itemeq(Item x, Item y){

returnstrcmp(x -> word, y -> word) == 0;

}



Inserir um item numa árvore, treeins

Tree treeins(Item x, Tree *s){if (*s == NULL)return treecons(x, s, left);

else if (itemeq(x, (*s) -> value))return *s;

else if (itemlt(x,(*s)->value))returntreeins(x, &(*s)->sub[left]);

elsereturntreeins(x, &(*s)->sub[right]);

}

Tree treeins(Item x, Tree *s){if (*s == NULL)return treecons(x, s, left);


else if (itemlt(x,(*s)->value))returntreeins(x, &(*s)->sub[left]);

elsereturntreeins(x, &(*s)->sub[right]);

}

Tree treeins(Item x, Tree *s){

if (*s == NULL)return treecons(x, s, left);


elsereturntreeins(x, (*s) -> sub +

!itemlt(x, (*s) -> value));

}

Tree treeins(Item x, Tree *s){

if (*s == NULL)return treecons(x, s, left);


elsereturntreeins(x, (*s) -> sub +

!itemlt(x, (*s) -> value));

}

Ou então:

?!



Percorrer as árvoresPercurso prefixo: void treepre(Tree s,

void(*p)(Item)){

if (s != NULL){p(s -> value);treepre(s -> sub[left], p);treepre(s -> sub[right], p);

}}

void treepre(Tree s, void(*p)(Item))

{if (s != NULL){p(s -> value);treepre(s -> sub[left], p);treepre(s -> sub[right], p);

}}

Percurso infixo: void treein(Tree s, void(*p)(Item)){

if (s != NULL){treein(s -> sub[left], p); p(s -> value);treein(s -> sub[right], p);

}}

void treein(Tree s, void(*p)(Item)){

if (s != NULL){treein(s -> sub[left], p); p(s -> value);treein(s -> sub[right], p);

}}

Percurso pós-fixo: void treepost(Tree s,

void(*p)(Item)){

if (s != NULL){treepost(s -> sub[left], p);treepost(s -> sub[right], p); p(s -> value);

}}

void treepost(Tree s, void(*p)(Item))

{if (s != NULL){treepost(s -> sub[left], p);treepost(s -> sub[right], p); p(s -> value);

}}



Ver as árvores

Listar todos os nós, por ordem (árvore de int):void treeprint(Tree s){if (s != NULL){treeprint(s -> sub[left]);printf("%d\n", s -> value);treeprint(s -> sub[right]);

}}

void treeprint(Tree s){if (s != NULL){treeprint(s -> sub[left]);printf("%d\n", s -> value);treeprint(s -> sub[right]);

}}

Listar a raiz com margem m e as subárvorescom margem m + d (árvore de int):void treeprintm(Tree s,int m,int d){if (s != NULL){printf("%*s%d\n",m,"",s->value);treeprintm(s->sub[left], m+d,d);treeprintm(s->sub[right],m+d,d);}

}

void treeprintm(Tree s,int m,int d){if (s != NULL){printf("%*s%d\n",m,"",s->value);treeprintm(s->sub[left], m+d,d);treeprintm(s->sub[right],m+d,d);}

}

É um percurso infixo



Exercícios (10)

1. Escrever funções utilitárias sobre árvores para:a) calcular a altura; b) contar os nós;c) ver se uma árvore não vazia é uma folha;d) contar as folhas;e) eliminar as folhas;f) eliminar os nós a partir de certo nível; g) calcular o grau de uma árvore não vazia (o

grau é o número de filhos);h) calcular o grau de equilíbrio (isto é, a

diferença entre as alturas dos filhos, ou ograu de equilíbrio do filho mais desequi-librado, consoante for maior);

i) calcular o grau de equilíbrio perfeito (isto é, a maior diferença entre o número de nósdas duas subárvores de um nó na árvore);

j) criar uma árvore perfeitamente equilibrada(isto é, uma árvore com grau de equilíbrio perfeito inferior ou igual a 1) a partir de um vector ordenado;

i) percorrer uma árvore por nível (breadth-first).



C++

• ser um C melhor.• suportar a abstracção de dados• suportar a programação orientada pelos

objectos.

O C++ tem os mesmos mecanismos linguís-ticos básicos que o C (funções, variáveis,expressões, instruções, vectores, apontado-res, estruturas, input/output, bibliotecasstandard).

Então, o que é que o C++ tem que o C não tinha?Tem classes (e conceitos associados: heran-ça, funções virtuais, classes derivadas, etc.)E também umas coisitas para melhorar o C:por exemplo, o operador new, conversão detipos, referências, funções inline, etc.

Objectivos do C++:

O C e o C++:



O que é uma classe?A classe Point

Uma classe é uma estrutura com funções, com uma parte privada e outra pública…

Uma classe é uma estrutura com funções, com uma parte privada e outra pública…

class Point{private:int xx;int yy;

public:Point(void);void Set(int, int);void Move(int, int);double DistanceTo(Point);void Display(void);

};

class Point{private:int xx;int yy;

public:Point(void);void Set(int, int);void Move(int, int);double DistanceTo(Point);void Display(void);

};

Os membros da secção private só podemser acedidos pelas funções-membro da classe; os da secção public constituem a interface dos objectos da classe.

data members

member functions

E onde é que definimos as funções?E onde é que definimos as funções?

Cons-trutor



As funções-membro da classe Point

Point::Point(void){xx = 0;yy = 0;

}

Point::Point(void){xx = 0;yy = 0;

}

double Point::DistanceTo(Point p){

return sqrt(sqr(xx-p.xx)+sqr(yy-p.yy));

}

double Point::DistanceTo(Point p){

return sqrt(sqr(xx-p.xx)+sqr(yy-p.yy));

}

void Point::Move(int dX, int dY){xx += dX;yy += dY;

}

void Point::Move(int dX, int dY){xx += dX;yy += dY;

}

void Point::Set(int newX, int newY){xx = newX;yy = newY;

}

void Point::Set(int newX, int newY){xx = newX;yy = newY;

}

etc. double sqr(double x){

return x * x;}

Point:: éoqualificador

O construtor, chamado automaticamente quando umobjecto é criado, garante explicitamente que não há objectos não inicializados.



Níveis de acesso

class AccessLevels {private:int noAccess;int readOnly;int readWrite;int writeOnly;void PrivateFunction(void);

public:int GetReadOnly(void) const;void SetReadWrite(int);int GetReadWrite(void) const;void SetWriteOnly(int);

};

class AccessLevels {private:int noAccess;int readOnly;int readWrite;int writeOnly;void PrivateFunction(void);

public:int GetReadOnly(void) const;void SetReadWrite(int);int GetReadWrite(void) const;void SetWriteOnly(int);

};

Normalmente, na zona pública só há funções. Os membros que são valores ficam na zona privada, e só são acedidos através das fun-ções públicas. Por vezes também aparecem funções na zona privada, e essas só podemser usadas dentro da classe.Em esquema:

Definições na página seguinte…

Aqui, o especifi-cador constsignifica que asfunções deixamo objecto na mesma.



Níveis de acesso (2)

int AccessLevels::GetReadOnly(void) const{

return readOnly;}

void AccessLevels::SetReadWrite(int value){

readWrite = value;}

int AccessLevels::GetReadWrite(void) const{

return readWrite;}

void AccessLevels::SetWriteOnly(int value){

writeOnly = value;}

void AccessLevels::PrivateFunction(void){

// ...}

int AccessLevels::GetReadOnly(void) const{

return readOnly;}

void AccessLevels::SetReadWrite(int value){

readWrite = value;}

int AccessLevels::GetReadWrite(void) const{

return readWrite;}

void AccessLevels::SetWriteOnly(int value){

writeOnly = value;}

void AccessLevels::PrivateFunction(void){

// ...}

Definições:

É preciso repetir o const aquinasdefinições.

Tal como está, esta função não serve paranada…

… e o membro noAccess está mesmo inacessível.



Construtores

Normalmente todas as classes têm um (ou vários) construtores. O construtor é chamado sempre que um objecto é criado.Um objecto pode ser criado em quatro circunstâncias:

1 Quando a sua declaração é processada(objectos automáticos).

2 No início do programa (objectos estáticos).3 Por meio do operador new (objectos dinâ-

micos, acedidos por meio de apontadores).4 Quando é criado um objecto “maior” ou um

vector, do qual o objecto faz parte (objec-tos-membro).

Por vezes, as classes também têm destru-tores, que são chamados automaticamente quando os objectos são destruídos.



Um driver para a classe Pointint main(void){int x;int y;Point p;Point q;Point origin;

double d;

printf("Duas coordenadas:\n");scanf("%d%d", &x, &y);p.Display();p.Set(x, y);p.Display();d = p.DistanceTo(origin);printf("Dist 'a origem: %lf\n", d);p.Move(3, 7);p.Display();

q = p;q.Display();return 0;

}

int main(void){int x;int y;Point p;Point q;Point origin;

double d;

printf("Duas coordenadas:\n");scanf("%d%d", &x, &y);p.Display();p.Set(x, y);p.Display();d = p.DistanceTo(origin);printf("Dist 'a origem: %lf\n", d);p.Move(3, 7);p.Display();

q = p;q.Display();return 0;

}

afectação de objectos da mesma classe:membro a membro



Os objectos podem ser definidossó quando são precisos

int main(void){

int x;int y;Point p;

double d;

printf("Duas coordenadas:\n");scanf("%d%d", &x, &y);p.Display();p.Set(x, y);p.Display();

Point origin;d = p.DistanceTo(origin);printf("Dist 'a origem: %lf\n", d);p.Move(3, 7);p.Display();

Point q;q = p;q.Display();return 0;

}

int main(void){

int x;int y;Point p;

double d;

printf("Duas coordenadas:\n");scanf("%d%d", &x, &y);p.Display();p.Set(x, y);p.Display();

Point origin;d = p.DistanceTo(origin);printf("Dist 'a origem: %lf\n", d);p.Move(3, 7);p.Display();

Point q;q = p;q.Display();return 0;

}

for(int i=0; i < n; i++){...

}

for(int i=0; i < n; i++){...

}

Definições no meiodas instruções

Outro exemplo típico:



Exercícios 11

3. Programar uma classe Triangle, comfunções para calcular a área, mover, etc.

Escrever também drivers para testar as classes.

2. Declarar uma classe Segment, represen-tando segmentos de recta definidos por dois pontos, com funções para o comprimento dosegmento, para calcular o ponto médio, mover o segmento, esticar o segmento, etc.

1. Enriquecer a classe Point com funções para reflectir o ponto no eixo dos xx, no eixodos yy, na diagonal principal, para rodar oponto de um certo ângulo, etc.

A área de um triângulo é dada pela seguinte expressão:s * (s - a) * (s - b) * (s - c)

onde s é o semiperímetro e a, b, e c são as medidas doslados.



continue;continue;

Documents

Programação avançada com C