Exercícios de Programação II e respectivas resoluções

Observações

Note-se que:

1. As soluções apresentadas não são as únicas, e possivelmente também não as "melhores".
2. Estas soluções por vezes incluem algumas características do C que não tinham sido ainda apresentadas nas aulas teóricas correspondentes. No entanto, uma vez que as soluções são apresentadas como elemento de estudo, julgámos ser vantajoso apresentar código C tão completo quanto possível.
3. Quando as soluções são semelhantes entre si, as versões vão sendo sucessivamente menos comentadas.
4. Ao longo do texto usam-se sempre as expressões "abrir ficheiro", "fechar ficheiro", etc., que devem, em rigor, ser entendidas como "abrir canal de acesso ao ficheiro", etc.
5. Note que as funções scanf() e fscanf() devolvem o número de argumentos lidos.

Exercício 1

Alínea a)

Mostrar no terminal o conteúdo de um ficheiro de texto.

Resolução

O programa deve, ao ser executado, mostrar no ecrã o conteúdo dum ficheiro de texto já existente algures no disco.

• Algoritmo: recordar as cópias da primária...
• Algoritmo passo-a-passo:
  1. Abrir o ficheiro de entrada.
  2. Ler um caractere e mostrá-lo enquanto não se atingir o fim do ficheiro.
  3. Fechar o ficheiro de entrada.
• Linguagem C: ex1a.c
• Linguagem C (alternativa usando versão "sofisticada" da função main()): ex1a_alt.c
• Notas:
  1. Note-se a utilização das macros (definições de pré-processador, com #define.} EXIT_FAILURE e EXIT_SUCCESS (definidas em stdlib.h). Estes valores devem ser utilizados como argumentos na chamada da função exit() para se assinalar a ocorrência de erros ou a não ocorrência de erros, respectivamente. A instrução return x na função main(), e apenas nesta, tem o mesmo significado que chamar exit(x).
  2. Note-se também que, na primeira versão do programa, se utiliza a função fgets() e não gets() para leitura do nome do ficheiro do teclado. Tal deve-se a que apenas por intermédio de fgets() é possível limitar o número de caracteres lidos aos que cabem na cadeia de caracteres de destino. A macro FILENAME_MAX (definida em stdio.h) tem como valor o máximo número de caracteres possíveis de utilizar no nome de um ficheiro (directórios incluídos) na máquina e sistema operativo em que o programa for compilado. Assim garante-se o correcto funcionamento do programa em qualquer ambiente (repare-se a necessidade de espaço na matriz nome para o terminador da cadeia).
  3. Note-se ainda que na versão alternativa do código se utilizam os parâmetros da função main, tal como especificados na norma ANSI-C, para aceder aos argumentos passados ao programa na linha de comando do sistema operativo (e.g., MS-DOS ou UNIX). Os parâmetros são argc e argv. O primeiro contém o número de argumentos passados ao programa contando com o próprio nome do programa. O segundo consiste numa matriz (array) de ponteiros para cadeias de caracteres, cada uma contendo seu argumento (sendo o primeiro o nome do programa). Assim, se o programa executável se chamar meutype o comando:

     meutype texto.txt
     

     mostra no ecrã o conteúdo do ficheiro texto.txt.

  4. Finalmente, aquando da escrita no ecrã, apenas se testa a condição de erro no final da escrita e por intermédio da função ferror(); esta prática justifica-se muitas vezes, pois permite simultaneamente simplificar o código e torná-lo mais eficiente.

Alínea b)

Armazenar em ficheiro um texto lido do terminal.

Resolução

Entende-se por "texto" o que quer que seja escrito no teclado pelo utilizador do programa até que seja premida a combinação de teclas equivalente a um fim de ficheiro, que no MS-DOS é ctrl-z e em Unix é ctrl-d.

• Algoritmo: idem...
• Algoritmo passo-a-passo:
  1. Abrir o ficheiro de saída.
  2. Ler um caractere do teclado e guardá-lo no ficheiro de saída enquanto não se atingir o fim das entradas de dados pelo utilizador.
  3. Fechar o ficheiro de saída.
• Linguagem C: ex1b.c
• Notas: Repare na semelhança entre as soluções dos três primeiros exercícios (1.a), 1.b) e 1.c)).

Alínea c)

Fazer uma cópia dum ficheiro de texto.

Resolução

• Algoritmo: idem...
• Algoritmo passo-a-passo:
  1. Abrir o ficheiro de entrada.
  2. Abrir o ficheiro de saída.
  3. Ler um caractere do ficheiro de entrada, enquanto não se atingir o fim do ficheiro, e guardá-lo no ficheiro de saída.
  4. Fechar o ficheiro de entrada.
  5. Fechar o ficheiro de saída.
• Linguagem C: ex1c.c

Alínea d)

Concatenar dois ficheiros de texto.

Resolução

Neste caso optou-se por escrever o resultado da concatenação no ecrã, mas as alterações necessárias para que o resultado da concatenação seja escrito num terceiro ficheiro são triviais.

• Algoritmo: Repetir algoritmo do exercício 1.a) duas vezes.
• Algoritmo passo-a-passo:
  1. Abrir o ficheiro de entrada 1.
  2. Ler um caractere do ficheiro de entrada 1, enquanto não se atingir o fim do ficheiro, e escrevê-lo no ecrã.
  3. Fechar o ficheiro de entrada 1.
  4. Abrir o ficheiro de entrada 2.
  5. Ler um caractere do ficheiro de entrada 2, enquanto não se atingir o fim do ficheiro, e escrevê-lo no ecrã.
  6. Fechar o ficheiro de entrada 2.
• Linguagem C: ex1d.c
• Linguagem C (alternativa usando um ciclo for): ex1d_alt.c
• Notas:
  1. A utilização do ciclo for na solução alternativa permite ao programa concatenar um qualquer número de ficheiros, e não apenas dois, como na versão original.
  2. Note-se que, apesar de se abrirem (e fecharem) potencialmente muitos ficheiros, utiliza-se apenas uma variável do tipo FILE *.

Alínea e)

Comparar dois ficheiros de texto linha a linha e mostrar a primeira linha onde eles diferem.

Resolução

• Algoritmo: Ler a par linhas de ambos os ficheiros enquanto nenhum deles terminar. Se alguma vez as linhas forem diferentes, assinalar a diferença, mostrar ambas as linhas, e sair. Caso um ficheiro termine antes do outro indicar esta ocorrência e sair.
• Algoritmo passo-a-passo:
  1. Abrir o ficheiro de entrada 1.
  2. Abrir o ficheiro de entrada 2.
  3. Repetir indefinidamente:
     1. Ler uma linha de cada um dos ficheiros.
     2. Se alguma das leituras falhar, verificar se falharam ambas ou apenas uma da leituras. Caso tenha sido apenas uma, assinalar qual dos ficheiros é mais curto. Em qualquer dos casos abortar a repetição.
     3. Comparar as duas linhas, se forem diferentes assinalar a diferença e abortar a repetição.
  4. Fechar o ficheiro de entrada 1.
  5. Fechar o ficheiro de entrada 2.
• Linguagem C: ex1e.c
• Notas:
  1. A construção

     while(fgets(s1, n, entrada1) != NULL && 
           fgets(s2, n, entrada2) != NULL)
     

     tem a desvantagem de, quando a primeira condição do E falha, a segunda não chegar a ser calculada, ou seja, o segundo fgets() não chega a ser chamado (lembre-se que os operadores E (&&) e OU (||) são especiais, pois o operando esquerdo é calculado em primeiro lugar e, se determinar o resultado da expressão lógica, o operando direito não chega a ser calculado!). Isto leva a que, se ambos os ficheiros forem iguais, o ciclo termina com condição de fim-de-ficheiro no ficheiro correspondente a entrada1 mas não no entrada2 ! Isso tornaria mais dificil avaliar se os dois seriam de facto iguais ou não.

  2. Note-se também na definição de variáveis dentro de um bloco de instruções (variáveis eof1 e eof2).

Alínea f)

Contar os números de caracteres, palavras e linhas de um ficheiro de texto.

Resolução

São consideradas palavras sequências contíguas de caracteres que não contenham qualquer caractere "branco" (por exemplo ' ', tabulador '\t' ou fim-de-linha '\n').

• Algoritmo: Inicializar contadores de caracteres, palavras e linhas e zero. Ler caractere a caractere o ficheiro de entrada. Incrementar o contador de linhas de cada vez que o caractere lido for um fim-de-linha. Se o último caractere do ficheiro não for um fim-de-linha, o número de linhas é o número de fins-de-linha adicionado de um. Caso contrário o número de linhas será igual ao número de fins-de-linha. O contador de caracteres incrementa-se sempre, independentemente do caractere lido. O contador de palavras é incrementado sempre que o ultimo caractere lido for um "branco" e o penúltimo um "não-branco". O número de palavras é igual ao valor do contador de palavras, excepto se o último caractere do ficheiro for "não-branco", caso em que deverá ser adicionado de 1.
• Algoritmo passo-a-passo:
  1. Abrir o ficheiro de entrada.
  2. Inicializar contadores de caracteres, palavras e fins-de-linha a zero.
  3. Inicializar penúltimo caractere com um fim-de-linha (evita-se assim contar palavras ou linhas a mais).
  4. Enquanto se conseguir ler um caractere da entrada repetir:
     1. Incrementar o número de caracteres.
     2. Se o último caractere for "branco" e o penúltimo for "não-branco" incrementar o número de palavras.
     3. Se o último caractere for um fim-de-linha incrementar o número de linhas.
     4. Atribuir o valor de último caractere a penúltimo caractere.
  5. Se o penúltimo caractere for um "não-branco", incrementar o número de palavras.
  6. Se o penúltimo caractere não for um fim-de-linha, incrementar o número de linhas.
  7. Imprimir valores obtidos.
  8. Fechar o ficheiro de entrada.
• Linguagem C: ex1f.c
• Notas:
  1. A identificação de caracteres brancos pode ser feita por comparação explícita com todos os caracteres brancos ou mediante a função ANSI-C isspace(), cuja declaração se encontra no ficheiro de cabeçalho ctype.h.
  2. Utilizam-se contadores unsigned long int para assegurar que a sua gama não seja facil de ultrapassar ao se operar sobre ficheiros de texto normais.

Alínea g)

Mostrar as linhas de um ficheiro de texto onde ocorre uma dada sequência de caracteres.

Resolução

• Algoritmo: Ler o ficheiro linha e linha. Procurar a sequência de caracteres na linha (ver próximo item). Se estiver presente mostrar a linha.
• Algoritmo de procura: Para cada caractere da linha verificar se é o início da sequência de caracteres: para tal percorrem-se simultaneamente a linha (começando no caractere de início corrente) e a sequência de caracteres a encontrar (começando no início). Se se encontrar alguma diferença entre os caracteres, aborta-se a comparação e passa-se ao próximo caractere de início. Se durante a procura for atingido o final da sequência a procurar, isso significa que a procura teve sucesso, e devolve-se o ponteiro para o caractere de início da linha. Se o que foi atingido foi o final da linha, então não vale a pena procurar mais e devolve-se um ponteiro nulo.
• Algoritmo passo-a-passo - Procura duma cadeia s2 (a sequência a procurar) dentro duma cadeia s1 (e.g., a linha onde procurar), devolvendo-se a primeira posição de s1 onde se encontra a sequência s2:
  1. Para cada posição de s1 enquanto não for atingido o caractere nulo (que marca o final da cadeia) repetir (note-se que se pode utilizar o próprio ponteiro s1 para percorrer a cadeia, pois não temos qualquer interesse em poder "voltar a trás"):
     1. Percorrer simultaneamente ambas as cadeias (com ponteiros p1 e p2, em que p1 se começa não no início da cadeia original s1 mas no local apontado por s1 correntemente, e em que p2 começa no início de s2) até que se atinjam posições em que as cadeias são diferentes ou até que se atinja o final duma das cadeias. 1
     2. Se do ciclo anterior resultou p2 apontando o caractere nulo, isso significa que não se encontraram diferenças até que o final de s2 foi atingido. Ou seja, s2 está contida na cadeia s1 original. Neste caso devolve-se s1.
     3. Esta linha atinge-se apenas se s2 não terminou. Se p1 resultar apontando o caractere nulo, então a cadeia s2 é mais longa do que a parte que falta testar da cadeia original s1, e portanto pode-se abortar a procura imediatamente devolvendo NULL.
  2. Se esta linha for atingida, significa que a cadeia original s1 é vazia (só neste caso se atinge esta última linha do algoritmo: em caso de dúvida experimente-se o algoritmo manualmente para várias cadeias de entrada). Então, apenas se s2 estiver também vazia se pode considerar a pesquisa com sucesso. Nesse caso devolve-se s1, caso contrário devolve-se NULL.
• Linguagem C: ex1g.c
• Notas: Para procurar uma cadeia de caracteres dentro de outra poderia ter-se usado a função ANSI-C char *strstr(const char s1[], const char s2[]), que procura a primeira ocorrência de s2 dentro de s1 devolvendo um ponteiro para a sua localização em s1 ou NULL caso s2 não esteja presente em s1. A função procura() funciona duma forma semelhante.

Alínea h)

Gerar um ficheiro de texto contendo uma pauta de resultados de avaliações lida do terminal. O ficheiro conterá um registo de aluno por linha. Cada registo é composto pelos seguintes campos (separados por um caractere espaço): número de aluno (4 posições), nome (25 posições), notas do teste e do trabalho (2 posições cada).

Resolução

A concretização deste programa é trivial, requerendo apenas algum conhecimento das especificações de conversão da função printf().

• Linguagem C: ex1h.c
• Notas:
  1. Não sendo especificada qualquer condição de paragem no enunciado, arbitrou-se parar se for premida a combinação de teclas que assinala o fim do ficheiro, ou sempre que um valor inválido for introduzido.
  2. São de notar as particularidades das especificações de conversão da função printf() utilizadas:
     • %4d -- imprime um inteiro de modo a ocupar pelo menos quatro caracteres, acrescentando espaços à esquerda se necessário, isto é, justificando o número à direita.
     • %-*.*s -- a construção n.m, em que n e m são números indica que a cadeia de caracteres depois de impressa deve ocupar pelo menos n caracteres e que não devem ser impressos mais do que m caracteres da cadeia; sempre que m ou n forem substituídos por * (que é o caso) o valor correspondente será lido do próximo argumento de printf() (no caso a macro NOME_MAX); o caractere - indica que a cadeia de caracteres deverá ser justificada à esquerda, e não `a direita.
  3. Note-se ainda que a leitura do nome se faz por intermédio de fgets(), tendo-se no entanto o cuidado de eliminar todos os caracteres espúrios introduzidos pelo utilizador (até ao fim-de-linha) de modo a evitar a sua interpretação errónea aquando da leitura da nota do teste. Observe-se o tamanho da matriz nome, com espaço para os 25 caracteres do nome e para o terminador '\0'.
  4. A utilização de macros e do caractere * na especificação de conversão do nome (na chamada à função printf()) permitem mudar o tamanho máximo dos nomes alterando uma única linha do programa!

Alínea i)

Mostrar no terminal o conteúdo de ficheiros de texto gerados pelo programa da alínea anterior.

Resolução

A concretização deste programa é trivial, requerendo apenas algum conhecimento das especificações de conversão da função fscanf().

• Linguagem C: ex1i.c
• Notas: São de notar as particularidades das especificações de conversão da função fscanf() utilizadas. Em particular, a especificação de conversão %nc lê os próximos n caracteres da entrada para uma cadeia de caracteres. Note ainda que, neste caso, a conversão está "mascarada" em "%d %" NOMECAD "c %d %d": acontece que qualquer compilador ANSI-C tem obrigação de concatenar numa só qualquer sequência de cadeias de caracteres constantes, resultando pois "%d %25c %d %d" conforme desejado. A vantagem da utilização da macro NOMECAD está em concentrar em duas linhas a informação a alterar para mudar o tamanho máximo dos nomes a utilizar (a utilização do caractere * em fscanf() tem um significado totalmente diferente do que possuia para printf(), daí a necessidade deste "truque").

Alínea j)

Ler um conjunto de valores para uma matriz bidimensional de inteiros com dimensão 4x4. Escrever o conteúdo da matriz de duas formas diferentes: ficheiro de texto e ficheiro binário. Comparar o tamanho dos ficheiros obtidos.

Resolução

• Linguagem C: ex1j.c
• Notas: Como se pode verificar, é perfeitamente possível escrever num ficheiro binário uma matriz bidimensional toda duma só vez.

Alínea k)

Ler para matrizes os ficheiros do exercício 1.j) e afixar no ecrã o seu conteúdo.

Resolução

• Linguagem C: ex1k.c

Exercício 2

Faça um programa para gerir uma base de dados associada aos utentes de um parque de estacionamento universitário. Admite-se um máximo de 50 utentes armazenados sob a forma de uma matriz. Cada utente é descrito pelos seguintes campos:

• Nome (máximo de 40 caracteres).
• Categoria, com valores possíveis de 0, 1 ou 2.
• Código: um número positivo. Um valor negativo indica que a posição da matriz está livre.

O programa deve permitir as seguintes operações, a cada uma das quais corresponde um função:

1. Inserção de novos utentes: a função deve ter como único argumento a matriz de utentes. Os dados do utente são introduzidos pelo teclado. O utente será colocado na primeira posição livre da matriz.
2. Remoção de utentes: a função tem como único argumento a matriz de utentes. Deve perguntar o nome do utente a remover e retirá-lo da matriz (marcando a posição como livre), caso ele exista.
3. Armazenamento da base de dados num ficheiro de texto: a função tem como argumentos a matriz de utentes e o nome do ficheiro. Não se esqueça que o ficheiro de texto deve ser legível pela função do pr'oximo item.
4. Leitura da base de dados de um ficheiro de texto: a função tem como argumentos a matriz de utentes e o nome do ficheiro. Deve ler o ficheiro e guardar os utentes na matriz. A leitura termina quando o número máximo de utentes for atingido ou quando o fim do ficheiro for atingido. Todos os utentes existentes anteriormente na matriz serão eliminados. Não esquecer que as posições que não forem ocupadas por utentes lidos do ficheiro devem ser marcadas como livres.
5. Mostrar no ecrã o conteúdo das posições ocupadas da matriz: a função tem como único argumento a matriz de utentes.

A estrutura do programa principal, que faz uso das funções acima, fica ao critério do aluno, e deverá ser preparada antes das funções. Este assunto, tal como o resto do enunciado, deve ser pensado com antecedência.

Resolução

• Linguagem C: ex2.c
• Notas:
  1. Não se controlam repetições de nomes e/ou códigos (fica como exercício adicional...).
  2. Alterou-se o enunciado no que diz respeito às funções de leitura e escrita de ficheiros: têm apenas um argumento, pois perguntam elas próprias o nome dos ficheiros respectivos.
  3. Note-se a utilização da variável alterado em main(), para garantir que o utilizador do programa não deita a perder uma sessão de manipulação duma base de dados.
  4. Notem-se também os valores devolvidos pelas funções.
  5. Finalmente, note-se que a função mataLinha() se destina a descartar todos os caracteres até ao próximo fim-de-linha, tendo um efeito semelhante à chamada fflush(stdin) quando se usa o Turbo-C. Esta utilização de fflush() com um canal aberto para leitura (no caso stdin) tem resultados indefinidos, de acordo com a norma ANSI-C, pelo que torna os programas não "transportáveis", ou seja, com comportamento variável consoante o compilador e/ou sistema operativo utilizado.

Exercício 3

Faça um programa que leia um ficheiro de utentes de um parque de estacionamento, contendo, em cada linha, o código, a categoria e o nome de cada utente, por esta ordem. Estes dados devem ser carregados numa matriz de estruturas. O programa deve escrever num ficheiro a base de dados de utentes ordenada por nome ou por código. A execução do programa é feita com passagem de três argumentos (usando argc e argv de main()):

programa entrada saida campo

em que campo indica o campo pelo qual a ordenação é feita, podendo tomar os valores nome ou codigo.

Durante a ordenação a matriz de utentes permanece inalterada, para o que se deve utilizar uma matriz adicional de ponteiros para a estrutura de utente (inspire-se no exemplo 13P13 da página 246 do livro). Exemplo 1:

ordena entrada.txt saida.txt codigo

Este comando lê o ficheiro entrada.txt, carrega-o para a matriz de utentes, ordena-a pelo código (indirectamente, não esquecer), e escreve o resultado no ficheiro saida.txt.

Exemplo 2:

ordena entrada.txt saida.txt nome

Este comando lê o ficheiro entrada.txt, carrega-o para a matriz de utentes, ordena-a pelo nome do utente, e escreve o resultado no ficheiro saida.txt.

Resolução

• Linguagem C: ex3.c
• Notas:
  1. Admite-se que os ficheiros têm o mesmo formato utilizado no exercício 2, isto é, uma linha por cada campo. Este formato simplifica a leitura. Repare-se na utilização dum espaço em branco no formato passado à função scanf(): "%d%d ". Este espaço serve para que a função scanf() elimine os espaços em branco, incluindo fins-de-linha, depois de ler a categoria e o código, de modo a estes não afectarem a leitura do próximo nome.
  2. Repare-se que o algoritmo de ordenação utilizado é o de "ordenação por permutação" (em inglês "bubble sort"), diferente, e mais eficiente, que o utilizado no livro. Deve-se ter em conta que este algoritmo, embora interessante, é muito ineficiente (número de comparações proporcional, em média, a NxN, sendo N o número de elementos a ordenar), não sendo por isso recomendável a sua utilização (entre os algoritmos mais eficientes encontra-se a "ordenação rápida" - em inglês "quick sort" - cujo número de comparações é proporcional, em média, a Nxlog(N)).
  3. Note-se que, na função ordenaUtentes(), existem dois algoritmos de ordenação idênticos, um ordenando por código e outro por nome. Tal deve-se a que a utilização de um teste adicional (ao campo pelo qual ordenar) dentro dos ciclos de ordenação contribuiria fortemente para tornar a ordenação mais lenta. Muito embora neste caso esta preocupação seja exagerada, em programas exigindo a ordenação de um número de elementos muito grande estas medidas simples podem levar facilmente a um aumento considerável da velocidade de execução.
  4. Note-se finalmente na flexibilidade do programa face ao número de argumentos. Admitindo que o programa se chama ordena:

     ordena

     lê os dados do teclado e escreve-os, ordenados pelo nome, no ecrã.

     ordena entrada

     lê os dados do ficheiro entrada e escreve-os, ordenados pelo nome, no ecrã.

     ordena entrada saida

     lê os dados do ficheiro entrada e escreve-os, ordenados pelo nome, no ficheiro saida.

     ordena entrada saida campo

     lê os dados do ficheiro entrada e escreve-os, ordenados pelo nome ou pelo código (consoante o valor de campo), no ficheiro saida.

Exercício 4

Listas e recursividade:

Alínea a)

Refaça o programa do exercício 2 de modo a usar o conceito de lista simplesmente ligada. O programa deve, portanto, permitir:

1. leitura de ficheiro
2. escrita de ficheiro
3. inserção de utentes
4. remoção de utentes
5. listagem dos utentes

Alínea b)

Escreva duas funções que gerem a sucessão de Fibonacci até um determinado um determinado valor de n: F(0) = F(1) = 1 e, para n > 1, F(n) = F(n-1) + F(n-2). A primeira função deverá ser recursiva e a segunda iterativa. Compare a velocidade das duas funções. Veja o que sucede quando o valor de n é muito grande.

Resolução

• Linguagem C: ex4b.c
• Notas: A "moral" a retirar deste exercício é que, ainda que muitas vezes as funções recursivas correspondam à concretização mais evidente de um determinado algoritmo, geralmente também é verdade que conduzem a realizações muito ineficientes, como pode ser verificado correndo o programa apresentado como solução do exercício.

Alínea c)

Refaça o programa da alínea a) de modo a que as listas usadas sejam totalmente genéricas, não dependendo, portanto, dos dados a guardar. A estrutura de elemento da lista deverá conter um ponteiro generico (void *) para os dados a guardar. Deve também conter um campo que guardará uma chave de acesso aos dados (use uma chave inteira). As funções associadas às listas genéricas poderão, por exemplo, incluir:

Lista *Lcria()

cria lista vazia.

void *Linsere(Lista *l, void *dados, int chave)

insere dados na lista, devolvendo-o ou devolvendo NULL em caso de erro.

void *Lremove(Lista *l, int chave)

remove da lista os dados indexados por chave, devolvendo-os ou devolvendo NULL caso não existam ou em caso de erro.

void *Lbusca(Lista *l, int chave)

devolve os dados indexados chave, ou devolve NULL caso não existam ou em caso de erro.

void Ldestroi(Lista *l, int tudo)

desafecta toda a memória da lista; se tudo for verdadeira, liberta também a memória afectada aos dados.

void *LbuscaFunc(Lista *l, PFI função, void *oque)

procura dados contendo oque, usando uma função passada como argumento (a função devolve verdadeiro quando encontrou os dados). Assume-se que:

typedef int (*PFI)(void *dados, void *oque);

por exemplo:

int buscaNome(void *dadosgen, void *nomegen)
{
    Utente *dados = dadosgen;
    char *nome = nomegen;

    return strcmp(dados->nome, nome) == 0;
}

chamando-se a função, por exemplo, da seguinte forma

dados = LbuscaFunc(lista, buscaNome, "Zacarias Zagalo");

Notas: não esquecer, nas alíneas a) e c), que a memória afectada deve ser desafectada quando deixa de ser necessária.

Exercício 5

Introdução

Sumário

• Declaração vs. Definição
• Categoria, âmbito, classe ou permanência e validade de objectos e nomes em C
  • Categoria de objectos
  • Âmbito dos nomes
  • Classe ou permanência das variáveis
  • Validade de funções e variáveis

Apresentam-se de seguida algumas notas sobre a linguagem C que não dispensam a leitura da bibliografia da cadeira, nomedamente do livro "The C Programming Language" (segunda edição), B. Kernighan e D. Ritchie, Prentice Hall, 1988.

Repare-se que a nomenclatura usada nestas notas não corresponde exactamente à usada, por exemplo, no livro referido acima. Os nomes aqui usados (e.g., local vs. global, interno vs. externo) foram escolhidos de modo a fazerem algum sentido em conjunto com os qualificadores do ANSI-C (e.g., extern).

Declaração vs. definição

A linguagem C diferencia os conceitos de declaração e de definição. Uma declaração informa o compilador da existência de algo (uma declaração de x é entendida pelo compilador como "existe x"). Uma definição, para além de declarar a existência, diz ao compilador em que é que consiste o objecto definido (que instruções compõem uma função, que campos compõem uma estrutura) e reserva memória para o objecto (no caso de variáveis).

Por declaração no sentido lato entende-se normalmente qualquer declaração, com ou sem definição. Por declaração no sentido estrito entende-se uma declaração sem definição. Uma definição é sempre também uma declaração.

O exemplo mais claro desta distinção encontra-se nas funções:

int func(int a);

que é equivalente a

int func(int);

é uma declaração no sentido estrito, pois não se especificam os pormenores de concretização da função, i.e., não se define a função. Já

int func(int a)
{
    return a/2;
}

é uma definição (e consequentemente também uma declaração) da função func().

No que diz respeito às variáveis, a distinção entre declaração e definição exige o recurso aos conceitos da próxima secção, nomeadamente aos conceitos de categoria e validade . Por exemplo, considerem-se os seguintes ficheiros:

/* Ficheiro a.c */
int i = 10;

e

/* Ficheiro b.c */
extern int i;

No ficheiro a.c define-se (e consequentemente declara-se) a variável (global e externa) i enquanto no ficheiro b.c se declara (no sentido estrito) uma variável i, que se supõe estar definida noutro ficheiro (neste caso seria provavelmente o ficheiro a.c...).

A mesma distinção entre declaração e definição se pode estabelecer para estruturas:

struct a;

é uma declaração, no sentido estrito, duma estrutura, enquanto que

struct a
{
    int b;
    ...
}

é uma definição duma estrutura.

Note-se que este último facto torna possível esconder totalmente, do utilizador de um determinado módulo de funções, os seus pormenores de realização. Suponha-se, por exemplo, um módulo de processamento de listas. Os respectivos ficheiros listas.h (ficheiro de cabeçalho, do inglês header file) e listas.c poderiam ser:

/* listas.h */
/*
 * Declaracao (sentido estrito) da estrutura struct ListaStr e 
 * definicao do tipo Lista!
 */
typedef struct ListaStr Lista;
/* Declaracoes, sentido estrito, de funcoes de interface... */
Lista *Lcria(void);
...

e

/* listas.c */
/*
 * A inclusao do ficheiro de cabecalho .h no ficheiro .c do 
 * proprio modulo  permite:
 * 1. Ter acesso `a definicao do tipo Lista.
 * 2. Garantir coerencia entre as declaracoes das funcoes no 
 *    ficheiro .h e a sua definicao no ficheiro .c.
 */
#include "listas.h"
/* Declaracao da estrutura ElementoStr e definicao do 
   tipo Elemento: */
typedef struct ElementoStr Elemento;
/* Definicao da estrutura ElementoStr: */
struct ElementoStr
{
    void *dados;
    Elemento *seguinte;
};
/* Definicao da estrutura struct ListaStr (declarada em 
   listas.h): */
struct ListaStr
{
    unsigned long numero;
    Elemento *inicio;
}
/* Definicao das funcoes: */
Lista *Lcria(void)
{
    ...
}
...

Categoria, âmbito, classe ou permanência e validade de objectos e nomes em C

Categoria de objectos

Em C existem duas categorias de objectos: objectos locais e objectos globais. São objectos locais aqueles que se definem dentro duma função. Os objectos definidos fora de qualquer função são objectos globais. 2

As funções, não se podendo nunca definir dentro de outras funções, são sempre globais. Quanto às variáveis, são locais as variáveis definidas dentro de funções e todos os parâmetros das funções. Por exemplo:

/* A funcao f() e' global: */
int f(int i)                /* O parametro i e' local. */
{
    int n;                  /* A variavel n e' local. */
    n = i*i;
    for(; n > 0; n--)
    {
        int aux = n;        /* A variavel aux e' local. */
	i += aux;
    }
    return n;
}
int n;                      /* A variavel n e' global. */

Âmbito dos nomes

Outro conceito importante diz respeito ao âmbito (ou skope em inglês) dos nomes declarados, i.e., em que zonas dum ficheiro em C são visíveis esses nomes. As regras são bastante simples:

1. Os nomes declarados externamente às funções são visíveis desde o ponto de declaração até ao final do ficheiro.
2. Os nomes dos parâmetros das funções são válidos ao longo de toda a função.
3. Os nomes declarados dentro das funções são válidos desde a declaração até ao final do bloco em que foram declarados.
4. Nomes declarados dentro de funções ocultam os mesmos nomes (desde que pertencentes ao mesmo espaço de nomenclatura) declarados fora das funções.
5. Nomes declarados dentro de um bloco ocultam os mesmos nomes (desde que pertencentes ao mesmo espaço de nomenclatura) declarados em blocos que os envolvam.

Observe-se:

 1  int a;
 2  int f3(int);
 3  int f1(int b)
 4  {
 5      int c;
 6      int f2(int);
 7      for(c = 0; b > 0; b--)
 8      {
 9          static int d = 1;
10          c += f2(d);
11      }
12      return c;
13  }
14  int e;
15  int f2(int f)
16  {
17      return f3(f);
18  }
19  int f3(int g)
20  {
21      return 1;
22  }

Neste exemplo têm-se os seguintes nomes:

• a - visível da linha 1 à 22.
• f3 - visível da linha 2 à 22.
• f1 - visível da linha 3 à 22.
• b - visível ao longo de toda função f1() (linhas 3 a 13).
• c - visível da linha 5 à 13.
• f2 - visível da linha 6 à 13 (dentro da função f1()) e da linha 15 à 22.
• d - visível da linha 9 à 11.
• e - visível da linha 14 à 22.

Classe ou permanência das variáveis

As variáveis em C têm diferentes tipos de permanência na memória consoante os qualificadores usados na sua definição e consoante sejam globais ou locais. As variáveis podem pertencer a uma de duas possíveis classes de permanência (ou storage class em inglês):

Automáticas

São variáveis locais (i.e., definidas dentro duma função) que têm existência (i.e., um espaço de memória afectado) apenas durante a execução da função em que foram definidas. O seu valor, como é óbvio, perde-se entre chamadas sucessivas à função.

Estáticas

São variáveis que têm existência desde o início até ao fim do programa.

As variáveis globais são sempre estáticas. As variáveis locais são automáticas por omissão e são estáticas caso a sua definição seja precedida do qualificador static.

As variáveis automáticas, quando não forem explicitamente inicializadas durante a sua definição, tomam valores indefinidos até à primeira atribuição que lhes seja feita.

As variáveis estáticas, quando não forem explicitamente inicializadas durante a definição, são inicializadas implicitamente com valores nulos (zeros). A inicialização (explícita ou implícita) de variáveis estáticas é feita apenas no início do programa.

Assim, no exemplo acima, apenas as variáveis a, d e e são estáticas.

Validade de funções e variáveis

De modo a facilitar a escrita de programas consistindo de diferentes módulos, existe na linguagem C o conceito de validade das funções e variáveis. As validades (ou linkage, em inglês) são:

Interna

Para variáveis e funções acessíveis apenas dentro do ficheiro onde são definidas.

Externa

Para variáveis e funções acessíveis em todo o programa (qualquer que seja o ficheiro).

As variáveis locais (ver definição acima) têm sempre validade apenas interna. As variáveis ou funções globais têm, por omissão, validade externa. No entanto, a sua validade pode ser interna desde que a sua definição seja precedida do qualificador static. 3

Para poder utilizar um objecto externo definido noutro ficheiro é necessário declará-lo com o qualificador extern. Este qualificador é obrigatório no caso das variáveis e opcional no caso das funções.

Considerem-se, por exemplo, os ficheiros: 4

/* Ficheiro a.c */
#include "a.h"
/* Definicao de variaveis globais: */
static int globalInterna = 2;
int globalExterna = 1;
/* Definicao de funcoes: */
static int funcaoInterna(int a)
{
    return globalExterna * globalInterna * a * a;
}
int funcaoExterna(int a)
{
    return funcaoInterna(a)-1;
}

/* Ficheiro a.h */
/* Declaracao de variaveis globais: */
extern int globalExterna;
/* Declaracao de funcoes: */
int funcaoExterna(int);

e

/* Ficheiro b.c */
#include <stdio.h>
#include <stdlib.h>
#include "a.h"
int main(void)
{
    globalExterna = -1;
    printf("funcaoExterna(3) = %d\n", funcaoExterna(3));
    return EXIT_SUCCESS;
}

Neste programa existem duas funções (para além de main()). A primeira, funcaoInterna() apenas pode ser utilizada dentro do ficheiro a.c, enquanto a segunda, funcaoExterna(), pode ser utilizada ao longo de todo o programa.

Relativamente às duas variáveis globais passa-se o mesmo: a primeira, globalInterna, só pode ser usada dentro de a.c enquanto a segunda, globalExterna, pode ser usada em todo o programa.

Como é óbvio, a utilização dos objectos externos fora do ficheiro onde são definidos implica a sua declaração, o que é conseguido, neste caso, por intermédio da inclusão do ficheiro de cabeçalho a.h. Note-se que se utilizou o qualificador extern apenas para a declaração das variáveis, tendo-se omitido, por desnecessário, esse qualificador na declaração das funções.

Finalmente, é de frisar neste ponto que, em geral, a utilização de variáveis globais é desaconselhável, por reduzir consideravelmente a legibilidade dos programas ao permitir que as funções afectem mais do que os seus argumentos. Os exemplos apresentados destinam-se apenas a demonstrar conceitos, e não devem ser tomados como exemplos de boa programação.

Alínea a)

Altere o programa produzido no exercício 4.b) de modo a que o número de chamadas da versão recursiva da função possa ser contabilizado. Para isso, utilize uma variável local à função (que terá de ser, obviamente, estática). Essa variável deve ser anulada sempre que se chamar a função com o argumento -1. O número de chamadas à função deverá ser devolvido pela função sempre que for chamada com o argumento -2.

Resolução

• Linguagem C: ex5a.c
• Notas: repare que se utiliza

      printf("F(%d)    = %lu\n", n, fibonacciRec(n));
      printf("chamadas = %lu\n", fibonacciRec(-2));
  

  e não

      printf("F(%d)    = %lu\nchamadas = %lu\n", n, 
             fibonacciRec(n), fibonacciRec(-2));
  

  pois o ANSI-C não garante a ordem de cálculo dos argumentos duma função, e portanto fibonacciRec(-2) poderia ser calculada em primeiro lugar!

Alínea b)

Envolva todo o código relativo à contabilização de chamadas introduzido na alínea anterior em directivas do pré-processador de modo a ser compilado apenas se estiver definida a macro CONTABILIZA.

Recorra às seguintes directivas do pré-processador:

#define nome oque (em que oque é opcional)

define a macro nome, que é expandida para oque

#ifdef nome

o código entre esta directiva e a próxima directiva #else ou #endif é compilado apenas se a macro nome estiver definida.

Resolução

• Linguagem C: ex5b.c

Alínea c)

Coloque as funções de cálculo da sucessão de Fibonacci num módulo separado, de nome sucessao.c, com o respectivo ficheiro de cabeçalho sucessao.h. Utilize nomes e tipos apropriados para as funções e seus parâmetros, por exemplo unsigned long SUCfibonacci(int n) e unsigned long SUCfibonacciRec(int n).

Resolução

• Linguagem C: ex5cde.c, sucessao.c e sucessao.h
• Notas:
  1. Repare que o ficheiro de cabeçalho sucessao.h é incluido tanto em ex5cde.c como em sucessao.c.
  2. Note ainda que a macro CONTABILIZA se define (ou não) no ficheiro de cabeçalho.

Alínea d)

Tente calcular analiticamente o número de chamadas da função SUCfibonacciRec() quando lhe é passado o argumento n. Verifique que o número de chamadas pode ser expresso duma forma recursiva muito semelhante à da própria sucessão de Fibonacci! Escreva uma nova função, unsigned long SUCnfibbonaci(int n) (na sua forma iterativa!) que devolva o número de chamadas à função SUCfibbonaciRec() quando lhe é passado o argumento n.

Verifique que o valor calculado está correcto comparando-o com o valor contabilizado pela própria função SUCfibonacciRec().

Resolução

A dedução é simples. Seja a definição recursiva da sucessão: F(0) = F(1) = 1 e, para n > 1, F(n) = F(n-1) + F(n-2). Seja N(n) o número de chamadas à função de Fibonacci recursiva. Claramente N(0)=N(1)=1. Por outro lado, para calcular F(n) é necessário chamar a função uma vez, que por sua vez chamará F(n-1) e F(n-2). Então, a função N() define-se recursivamente, tal como F()! Em particular, N(0) = N(1) = 1 e, para n > 1, N(n) = 1 + N(n-1) + N(n-2).

• Linguagem C: ex5cde.c, sucessao.c e sucessao.h

Alínea e)

Um problema que surge frequentemente quando se trabalha com módulos é o da inclusão múltipla do mesmo ficheiro de cabeçalho. Por exemplo, considere o módulo de listas genéricas que foi programado no exercício 4.c), e admita que o ficheiro de cabeçalho respectivo se chama listas.h. Suponha que o (os) tipos definidos no ficheiro listas.h é (são) necessário(s) para a declaração das funções no ficheiro de cabeçalho de outro módulo, por exemplo utentes.h:

/* utentes.h */
#include "listas.h"
...

Se o módulo principal (aquele que contém a função main()) necessitar simultâneamente dos módulos listas e utentes, conterá, provavelmente, as directivas:

#include "listas.h"
#include "utentes.h"

o que resultará na inclusão do ficheiro listas.h duas vezes. Esta dupla inclusão acabará por gerar erros de compilação, porque o mesmo tipo não pode ser definido duas vezes (com typedef). Mas, mesmo que não ocorra qualquer erro de compilação, a dupla inclusão de um ficheiro de cabeçalho é inútil e desperdiça tempo de compilação.

Tente evitar a dupla inclusão, tal como descrita atrás, do ficheiro sucessao.h, recorrendo para isso às seguintes directivas do pré-processador:

#define nome oque (em que oque é opcional)

define a macro nome, que é expandida para oque

#ifndef nome

o código entre esta directiva e a próxima directiva #else ou #endif é compilado apenas se a macro nome não estiver definida.

Resolução

• Linguagem C: ex5cde.c, sucessao.c e sucessao.h
• Notas:
  1. Repare que para evitar os problemas da multipla inclusão se acrescentaram directivas do pré-processador apenas no ficheiro de cabeçalho!
  2. Note o comentário em

     #endif /* _SUCESSAO_H_ */
     

     uma vez que o ANSI-C não permite argumentos nas directivas #endif e #else.

  3. Repare ainda no nome escolhido para a macro definida, que: 1. evita colisões com outras macros já existentes (utilização de sublinhados), e 2. está relacionada com o nome do proprio ficheiro.

Alínea f)

Escreva um ficheiro de cabeçalho uteis.h, não correspondendo a qualquer módulo, que defina as seguintes macros úteis:

ABS(x)

Calcula o valor absoluto de x.

ABSDIF(x, y)

Calcula o valor absoluto da diferença entre x e y.

ABSMAIOR(x, y)

Devolve verdadeiro se |x| > y (com y positivo).

MAX(x, y)

Devolve o maior dos argumentos.

MIN(x, y)

Devolve o menor dos argumentos.

LIM(x, y, z)

Devolve o valor de y limitado ao intervalo [x z].

SINAL(x)

Devolve o sinal de x (-1 para negativo, 0 para nulo e 1 para positivo).

TROCA(x, y, aux)

Troca a variável x com y usando a variável auxiliar aux.

Comente claramente os possíveis efeitos secundários das macros, nomedamente indicando o número de vezes que cada argumento da macro é utilizado no texto de expansão da mesma.

Explique porque é que não se devem, em geral, chamar macros com argumentos envolvendo expressões complexas. Por exemplo:

x = ABS(sin(cos(x*x/y)));

Não se esqueça de usar parênteses generosamente para evitar os problemas de precedências, tão frequentes quando se utilizam macros!

Resolução

• Linguagem C: uteis.h

Repare que a chamada

x = ABS(sin(cos(x*x/y)));

é traduzida pelo compilador para

x = ((sin(cos(x*x/y))) >= 0 ? (sin(cos(x*x/y))) : 
                             -(sin(cos(x*x/y))));

o que implica que o cálculo completo é efectuado duas vezes, o que é extremamente ineficiente. Por outro lado

x = ABS(i++);

é traduzida pelo compilador para

x = ((i++) >= 0 ? (i++) : -(i++));

que não produzirá os resultados esperados nem em i nem em x!

Exercício 6

Refaça o programa do exercício 2 de modo a utilizar um ficheiro de registos binário para guardar a base de dados, em vez duma matriz. Assim, deixa de haver limitação quanto ao número de utentes. Não são permitidas repetições de nomes ou códigos.

Utilize as funções:

fopen() com modo "r+b" ou "w+b"

para criar um abrir ou criar um ficheiro no modo de actualização.

ftell()

para obter a posição de leitura/escrita corrente.

fseek()

para colocar a posição de leitura/escrita num local determinado.

fread()

para efectuar leituras de registos.

fwrite()

para efectuar escritas de registos.

feof()

devolve verdadeiro se e só se se tiver já tentado ler para além do fim do ficheiro (isto é, se o indicador de fim-de-ficheiro estiver activo).

Valores negativos no código dos utentes continuam a indicar que a posição, neste caso no ficheiro de registos, está livre.

Não esquecer que, nesta versão do programa, a base de dados é guardada, entre chamadas ao programa, no próprio ficheiro de registos binário (e não num ficheiro de texto como no exercício 2). 5

Note-se que é muito importante pensar nas funções a realizar antes de as começar a programar em C. Em particular, a utilização de um diagrama para representar o estado do ficheiro de registos e a evolução da posição de leitura/escrita revelar-se-á muito útil.

Finalmente, lembre-se de que a norma ANSI-C obriga a que entre passagens de leitura para escrita e vice versa sejam intercaladas chamadas a fflush(), fseek(), fsetpos() ou frewind(). Entre operações de leitura e escrita (neste sentido, de leitura para escrita), não é necessário intercalar estas funções se as funções de leitura terminaram colocando o indicador de fim-de-ficheiro no valor verdadeiro.

Resolução

• Linguagem C: ex6.c, leituras.c e leituras.h

Fica como exercício expurgar o ficheiro de registo de todos os registos livres antes de sair do programa.

Exercício 7

Alínea a)

Realize um módulo de pilhas genéricas (o último a entrar é o primeiro a sair). Faça também o respectivo programa de teste. Dever-se-ão utilizar matrizes para guardar os ponteiros genéricos (void *) para os dados do utilizador do módulo. Assim, sendo, existe um número máximo de elementos na pilha. O número máximo de elementos deverá poder ser especificado pelo utilizador aquando da criação duma nova pilha (i.e., deverá usar memória dinâmica para a matriz, que será afectada pela função calloc()).

Apresentam-se sugestões para as funções de interface do módulo (PM significa "pilhas com matrizes"):

PilhaM *PMcria(size_t n)

cria uma nova pilha cuja dimensão (número máximo de elementos guardados) é n.

void PMdestroi(PilhaM *p)

desafecta toda a memória associada à pilha p.

PilhaM *PMesvazia(PilhaM *p)

esvazia a pilha p.

size_t PMquantos(PilhaM *p)

devolve o número de elementos guardados na pilha p.

int PMcheia(PilhaM *p)

devolve verdadeiro se a pilha p estiver cheia.

PilhaM *PMpoe(PilhaM *p, void *d)

insere os dados d na pilha p; devolve zero se a pilha estiver cheia, caso contrário devolve o ponteiro para a pilha.

void *PMtira(PilhaM *p)

retira o elemento que se encontra há menos tempo na pilha p e devolve os seus dados; devolve zero se a pilha estiver vazia.

Resolução

• Linguagem C: pilhasm.c e pilhasm.h.

Alínea b)

Semelhante à alínea a), mas agora serão filas (o primeiro a entrar é o primeiro a sair), e não pilhas.

As funções de exemplo são semelhantes, substituindo-se PM por FM.

Note que a função void *FMtira(FilaM *f) retira o elemento que se encontra há mais tempo na fila f!

Repare que neste caso poderá usar os indíces de modo a que "dêem a volta", evitando-se assim a renormalização da matriz sempre que se retira um elemento.

Finalmente, note que a condição de "fila cheia" se pode confundir com a condição de "fila vazia"! Pode evitar o problema reservando n+1 posições na matriz e nunca deixando introduzir mais do que n elementos.

Resolução

• Linguagem C: filasm.c e filasm.h.

Alínea c)

Semelhante à alínea a), mas agora utilizando o módulo de listas genéricas, desenvolvido no exercício 4.c), e não matrizes. Exemplo de funções de interface do módulo (P significa "pilhas"):

Pilha *Pcria(void)

cria uma nova pilha.

void Pdestroi(Pilha *p)

desafecta toda a memória associada à pilha p.

Pilha *Pesvazia(Pilha *p)

esvazia a pilha p.

unsigned long Pquantos(Pilha *p)

devolve o número de elementos guardados na pilha p.

Pilha *Ppoe(Pilha *p, void *d)

insere os dados d na pilha p; devolve o ponteiro para a pilha.

void *Ptira(Pilha *p)

devolve os dados que se encontram há menos tempo na pilha p; devolve zero se a pilha estiver vazia.

Repare que neste caso não se especifica qualquer dimensão máxima para a pilha aquando da sua criação. Note-se ainda que não existe, como é óbvio, qualquer função para verificar se a pilha está cheia.

Note ainda que poderá necessitar de fazer algumas alterações ão módulo de listas genéricas, pois poderá faltar uma função que "retire o elemento inicial".

Resolução

• Linguagem C: pilhas.c e pilhas.h.

Alínea d)

Semelhante à alínea c), mas agora serão filas, e não pilhas.

As funções de exemplo são semelhantes, substituindo-se P por F.

Note que a função void *Ftira(Fila *f) retira o elemento que se encontra há mais tempo na fila f!

Note ainda que poderá necessitar de fazer algumas alterações ão módulo de listas genéricas, pois poderá faltar uma função que "retire o elemento final".

Resolução

• Linguagem C: filas.c e filas.h.

Exercício 8

Faça um programa que permita realizar as seguintes operações elementares com valores double:

• Atribuição de valores a variáveis. Se a variável indicada não existir deverá ser criada.
• Soma, subtracção, multiplicação e divisão de variáveis. Se alguma das variáveis não existir deverá ser assinalado um erro.
• Atribuição do último valor calculado a uma variável.

As variáveis, que consistirão em pares (nome,valor) (i.e., estruturas), devem ser guardadas numa lista (use o módulo de listas genéricas desenvolvido no exercício 4.c)).

Note que as variáveis a que este enunciado se refere não são variáveis da linguagem C, mas sim objectos guardados pelo programa e definidos pelo seu utilizador.

Resolução

• Linguagem C: ex8.c, leituras.c e leituras.h..

Página concebida e mantida por Eng. Manuel Menezes de Sequeira (última actualização 2006/07/07) Copyright © 1996-2001 ISCTE