2. Exercícios

Solução não publicada.
Solução não publicada.
Ver solução abaixo (filas.c e filas.h).
Ver solução abaixo (aula8.c).

2.1 Módulo `filas`

2.1.1 Ficheiro `filas.h`

/*
 * Modulo: filas (ficheiro de cabecalho)
 * 
 * Descricao: Implementa o conceito de fila. As operacoes permitidas com as 
 * filas sao as associadas 'as funcoes descritas abaixo. 
 * 
 * Notas: 
 * 
 * Autores: 
 *     Manuel Menezes de Sequeira, ISCTE, 1997. 
 */
#ifndef FILAS_H
#define FILAS_H

/* Inclusao do ficheiro com tipos de utilidade generica (v.g. Logico): */
#include "tipos.h"

/* Definicao do tipo das variaveis que guardam manipulos de acesso 'as 
   filas. */
typedef struct Fila *Fila;

/* Definicao do tipo dos elementos que serao guardados nas filas: */
typedef int Fdados;

#include <limits.h>
#define FerroDados INT_MIN

/* Cria uma nova fila, vazia, devolvendo um manipulo (um endereco) para a 
   mesma. Podem ser criadas quantas filas se desejar, desde que para isso 
   haja memoria. */
Fila Fcria(void);

/* Destroi a fila associada ao manipulo f passado como argumento. Toda a
   memoria associada 'a fila e' libertada. O manipulo (endereco) da fila
   torna-se invalido depois de passado a esta funcao. */
void Fdestroi(Fila f);

/* Insere os dados d no fim da fila cujo manipulo e' f. Se a insercao tiver
   sucesso, devolve Verdadeiro, no caso contrario devolve Falso. */
Logico Finsere(Fila f, Fdados d);

/* Remove o elemento do inicio da fila cujo manipulo e' f. Se a fila estiver
   vazia, devolve Falso, caso contrario devolve Verdadeiro. */
Logico Fremove(Fila f);

/* Devolve os dados do elemento no inicio da fila cujo manipulo e' f. O
   resultado e' indefinido se a fila estiver vazia. */
Fdados Ffrente(Fila f);

/* Devolve o comprimento (numero de elementos) da fila cujo manipulo e' f: */
size_t Fcomprimento(Fila f);

#endif /* FILAS_H */

2.1.2 Ficheiro `filas.c`

/*
 * Modulo: filas.c
 * 
 * Descricao: Implementa o conceito de fila. As operacoes permitidas com as 
 * filas sao as associadas 'as funcoes descritas abaixo. 
 * 
 * Notas: 
 * 
 * Autores: 
 *     Manuel Menezes de Sequeira, ISCTE, 1997. 
 */

#include <stdlib.h>

#include "filas.h"

struct Fila
{
    size_t i;			/* indice do inicio da fila. */
    size_t f;			/* indice do fim da fila. */
    size_t n;			/* numero de elementos na fila
				   (comprimento.) */
    size_t t;			/* tamanho corrente da matriz. */
    Fdados *m;			/* matriz de elementos. */
};

#define INCR 4U

#if INCR == 0U
#error Valor do incremento invalido.
#endif

/* Cria uma nova fila, vazia, devolvendo um manipulo (um endereco) para a 
   mesma. Podem ser criadas quantas filas se desejar, desde que para isso 
   haja memoria. */
Fila Fcria(void)
{
    Fila f;
    
    if((f = malloc(sizeof *f)) == NULL)
	return NULL;
    f->t = INCR;
    if((f->m = calloc(f->t, sizeof *f->m)) == NULL)
    {
	free(f);
	return NULL;
    }
    f->i = f->f = f->n = 0U;

    return f;
}

/* Destroi a fila associada ao manipulo f passado como argumento. Toda a
   memoria associada 'a fila e' libertada. O manipulo (endereco) da fila
   torna-se invalido depois de passado a esta funcao. */
void Fdestroi(Fila f)
{
    if(f != NULL)
    {
	free(f->m);
	free(f);
    }
}

/* Calculo do mdc pelo metodo de Euclides: */
static size_t mdc(size_t m, size_t n)
{
    size_t r;

    while((r = m % n) != 0)
    {
	m = n;
	n = r;
    }
    return n;
}

/* 
 * Reorganiza a fila. Este e' um problema interessante. E' necessario
 * colocar o primeiro da fila na posicao 0 da matriz. Isso significa
 * deslocar todos os elementos de f->i para a esquerda. Nao esquecer que a
 * matriz esta' cheia nesta fase! Como fazer os deslocamentos? A solucao
 * mais evidente e' colocar numa matriz auxiliar os f->i primeiros elementos
 * da matriz, deslocar os outros, e copiar da matriz auxiliar para o final
 * da matriz. Mas ha' uma solucao que so' precisa duma posicao de memoria
 * extra (alem do espaco usado pelas variaveis de indice). T.P.C.: perceber
 * os ciclos abaixo (experimente com t->n = 12 e t->i = 1,...,11).
 *
 * (Nota: quando esta funcao e' chamada temos f->n = f->t e f->i = f->f.)
*/
static void reorganiza(Fila f)
{
    size_t n;			/* tamanho da matriz. */
    size_t d;			/* deslocamento. */
    size_t c;			/* numero de ciclos de deslocamento. */
    size_t i;			/* inicio dos ciclos. */
    size_t j, k;		/* para o ciclo de transferencias. */

    /* Verificar casos em que os deslocamentos a realizar nao tem qualquer
       efeito: */
    if(f->n == 1U || f->i == 0U)
	return;
    /* Guardar tamanho da matriz e deslocamento a realizar em n e d: */
    n = f->n;
    d = f->i;
    /* Calcular o numero de ciclos de transferencia a realizar: */
    c = mdc(n, d);
    /* Realizar o c ciclos de tranferencia: */
    for(i = 0U; i < c; i++)
    {
	/* Realizar um ciclo de transferencias: */
	int aux = f->m[i];
	for(j = i, k = (i + d) % n; k != i; j = k, k = (k + d) % n)
	    f->m[j] = f->m[k];
	f->m[j] = aux;
    }
    /* Agora o inicio e o fim (ou melhor, o proximo final) estao na origem,
       como se desejava: */
    f->i = f->f = 0U;
}

/* Redimensiona a fila (reorganizando-a primeiro): */
static Logico redimensiona(Fila f)
{
    Fdados *m;
    size_t t;

    /* Antes de reservar memoria reorganizamos a matriz de modo a que o
       primeiro elemento da fila esteja na posicao 0: */
    reorganiza(f);
    
    /* Agora ja' podemos redimensionar a matriz: */
    t = f->t + INCR;
    if((m = realloc(f->m, t * sizeof(Fdados))) == NULL)
	return Insucesso;
    f->m = m;			/* nova matriz redimensionada. */
    f->t = t;			/* novo tamanho. */
    f->f = f->n;		/* novo final. */

    return Sucesso;
}

/* Insere os dados d no fim da fila cujo manipulo e' f. Se a insercao tiver
   sucesso, devolve Verdadeiro, no caso contrario devolve Falso. */
Logico Finsere(Fila f, Fdados d)
{
    if(f == NULL)
	return Insucesso;

    /* Se nao houver espaco redimensionar: */
    if(f->n == f->t && !redimensiona(f))
	return Insucesso;

    /* Agora ha' espaco: */
    f->m[f->f] = d;
    if(++f->f == f->t)		/* deu a volta? */
	f->f = 0U;

    f->n++;
    
    return Sucesso;
}

/* Remove o elemento do inicio da fila cujo manipulo e' f. Se a fila estiver
   vazia, devolve Falso, caso contrario devolve Verdadeiro. */
Logico Fremove(Fila f)
{
    if(f == NULL || f->n == 0U)
	return Insucesso;

    if(++f->i == f->t)		/* deu a volta? */
	f->i = 0U;

    f->n--;

    return Sucesso;
}

/* Devolve os dados do elemento no inicio da fila cujo manipulo e' f. O
   resultado e' indefinido se a fila estiver vazia. */
Fdados Ffrente(Fila f)
{
    if(f == NULL || f->n == 0U)
	return FerroDados;

    return f->m[f->i];
}

/* Devolve o comprimento (numero de elementos) da fila cujo manipulo e' f: */
size_t Fcomprimento(Fila f)
{
    if(f == NULL)
	return 0U;
    return f->n;
}

2.2 Programa de teste `aula8.c`

#include <stdio.h>
#include <stdlib.h>

#include "filas.h"
#include "menu.h"
#include "teclado.h"

int main(void)
{
    Fila f;
    int opcao;
    int valor;
    
    f = Fcria();
    do
    {
	switch(opcao = MNpedeOpcao("I - Insere.\n"
				   "R - Remove.\n"
				   "P - Primeiro.\n"
				   "S - Sair.\n", '\n'))
	{
	  case 'I':
	    scanf("%d", &valor); getchar();
	    if(!Finsere(f, valor))
		printf("Erro inserindo.\n");
	    break;
	  case 'R':
	    if(!Fremove(f))
		printf("Erro removendo (fila vazia?).\n");
	    break;
	  case 'P':
	    if((valor = Ffrente(f)) == FerroDados)
		printf("Erro obtendo primeiro (fila vazia?).\n");
	    else
		printf("Frente: %d.\n", valor);
	    break;
	}
    }
    while(opcao != 'S' && opcao != EOF);
    
    Fdestroi(f);

    return EXIT_SUCCESS;
}

2. Exercícios

2.1 Módulo filas

2.1.1 Ficheiro filas.h

2.1.2 Ficheiro filas.c

2.2 Programa de teste aula8.c

2.1 Módulo `filas`

2.1.1 Ficheiro `filas.h`

2.1.2 Ficheiro `filas.c`

2.2 Programa de teste `aula8.c`