From 737dadc64f3f0d85e9d2e71b81aed2bf24bfa079 Mon Sep 17 00:00:00 2001 From: Alexandre P Francisco Date: Mon, 16 May 2016 10:36:13 +0100 Subject: [PATCH] Add my project implementations for 1516s2. --- proj/1516s2p1.c | 469 ++++++++++++++++++++++++++++++++++++++++++++++++ proj/1516s2p2.c | 237 ++++++++++++++++++++++++ 2 files changed, 706 insertions(+) create mode 100644 proj/1516s2p1.c create mode 100644 proj/1516s2p2.c diff --git a/proj/1516s2p1.c b/proj/1516s2p1.c new file mode 100644 index 0000000..019ca98 --- /dev/null +++ b/proj/1516s2p1.c @@ -0,0 +1,469 @@ +/** + * @file proj1.c + * @brief Implementacao do primeiro projecto de IAED. + */ +#include +#include +#include +#include +#include + +#define IDLEN 4 /* Comprimento maximo do ID. */ +#define MAXNA 1000 /* Numero maximo de aeroportos. */ + +typedef enum {ABERTO, FECHADO} estado_t; + +/** + * @brief Estrutura que representa um produto. + */ +typedef struct { + int capacidade; /* Capacidade maxima de operacao. */ + int rotas; /* Numero de rotas actuais. */ + char id[IDLEN]; /* Codigo de identificacao. */ + estado_t estado; /* Estado: ABERTO ou FECHADO */ +} aeroporto_t; + + +/** + * Variaveis locais ao programa. + */ +static aeroporto_t aeroportos[MAXNA]; +static int ligacoes[MAXNA][MAXNA]; +static int n_aeroportos; + +/** + * Declaracao das funcaoes utilizadas neste programa. + */ +void comando_A(); +void comando_I(); +void comando_F(); +void comando_G(); +void comando_R(); +void comando_S(); +void comando_N(); +void comando_P(); +void comando_Q(); +void comando_V(); +void comando_C(); +void comando_O(); +void comando_L(); +void comando_X(); + +int id2idx(char id[]); + +/** + * @brief Funcao main. + * + * @return Codigo de estado de saida do programa. + */ +int +main() +{ + char comando; + + while (1) { + comando = getchar(); + + /* Processa o comando. */ + switch (comando) { + case 'A': + comando_A(); + break; + case 'I': + comando_I(); + break; + case 'F': + comando_F(); + break; + case 'G': + comando_G(); + break; + case 'R': + comando_R(); + break; + case 'S': + comando_S(); + break; + case 'N': + comando_N(); + break; + case 'P': + comando_P(); + break; + case 'Q': + comando_Q(); + break; + case 'V': + comando_V(); + break; + case 'C': + comando_C(); + break; + case 'O': + comando_O(); + break; + case 'L': + comando_L(); + break; + case 'X': + comando_X(); + /* Este comando termina o programa. */ + return EXIT_SUCCESS; + default: + /* Nao devemos chegar aqui. */ + assert(0); + } + + getchar(); /* Remover o '\n' no final do comando do stdin. */ + } + + /* Nao devemos chegar aqui em situacoes normais. */ + return EXIT_FAILURE; +} + +/** + * @brief Funcao para processar o comando 'A'. + */ +void comando_A() { + scanf("%s%d", aeroportos[n_aeroportos].id, &aeroportos[n_aeroportos].capacidade); + aeroportos[n_aeroportos].rotas = 0; + aeroportos[n_aeroportos].estado = ABERTO; + n_aeroportos ++; +} + +/** + * @brief Funcao para processar o comando 'I'. + */ +void comando_I() { + char id[IDLEN]; + int alteracao_de_capacidade, idx; + + scanf("%s%d", id, &alteracao_de_capacidade); + idx = id2idx(id); + + if (idx < 0 + || aeroportos[idx].estado == FECHADO + || aeroportos[idx].capacidade + alteracao_de_capacidade < aeroportos[idx].rotas + || aeroportos[idx].capacidade + alteracao_de_capacidade < 0) { + printf("*Capacidade de %s inalterada\n", id); + return; + } + + aeroportos[idx].capacidade += alteracao_de_capacidade; +} + +/** + * @brief Funcao para processar o comando 'F'. + */ +void comando_F() { + char idS[IDLEN], idT[IDLEN]; + int idxS, idxT; + + scanf("%s%s", idS, idT); + idxS = id2idx(idS); + idxT = id2idx(idT); + + if (idxS < 0 || idxT < 0 + || aeroportos[idxS].estado == FECHADO + || aeroportos[idxT].estado == FECHADO + || aeroportos[idxS].rotas >= aeroportos[idxS].capacidade - 1 + || aeroportos[idxT].rotas >= aeroportos[idxT].capacidade - 1) { + printf("*Impossivel adicionar voo RT %s %s\n", idS, idT); + return; + } + + ligacoes[idxS][idxT] ++; + ligacoes[idxT][idxS] ++; + aeroportos[idxS].rotas += 2; + aeroportos[idxT].rotas += 2; +} + +/** + * @brief Funcao para processar o comando 'G'. + */ +void comando_G() { + char idS[IDLEN], idT[IDLEN]; + int idxS, idxT; + + scanf("%s%s", idS, idT); + idxS = id2idx(idS); + idxT = id2idx(idT); + + if (idxS < 0 || idxT < 0 + || aeroportos[idxS].estado == FECHADO + || aeroportos[idxT].estado == FECHADO + || aeroportos[idxS].rotas >= aeroportos[idxS].capacidade + || aeroportos[idxT].rotas >= aeroportos[idxT].capacidade) { + printf("*Impossivel adicionar voo %s %s\n", idS, idT); + return; + } + + ligacoes[idxS][idxT] ++; + aeroportos[idxS].rotas ++; + aeroportos[idxT].rotas ++; +} + +/** + * @brief Funcao para processar o comando 'R'. + */ +void comando_R() { + char idS[IDLEN], idT[IDLEN]; + int idxS, idxT; + + scanf("%s%s", idS, idT); + idxS = id2idx(idS); + idxT = id2idx(idT); + + if (idxS < 0 || idxT < 0 + || aeroportos[idxS].estado == FECHADO + || aeroportos[idxT].estado == FECHADO + || ligacoes[idxS][idxT] < 1) { + printf("*Impossivel remover voo %s %s\n", idS, idT); + return; + } + + ligacoes[idxS][idxT] --; + aeroportos[idxS].rotas --; + aeroportos[idxT].rotas --; +} + +/** + * @brief Funcao para processar o comando 'S'. + */ +void comando_S() { + char idS[IDLEN], idT[IDLEN]; + int idxS, idxT; + + scanf("%s%s", idS, idT); + idxS = id2idx(idS); + idxT = id2idx(idT); + + if (idxS < 0 || idxT < 0 + || aeroportos[idxS].estado == FECHADO + || aeroportos[idxT].estado == FECHADO + || ligacoes[idxS][idxT] < 1 + || ligacoes[idxT][idxS] < 1) { + printf("*Impossivel remover voo RT %s %s\n", idS, idT); + return; + } + + ligacoes[idxS][idxT] --; + ligacoes[idxT][idxS] --; + aeroportos[idxS].rotas -= 2; + aeroportos[idxT].rotas -= 2; +} + +/** + * @brief Funcao para processar o comando 'N'. + */ +void comando_N() { + char idS[IDLEN], idT[IDLEN]; + int idxS, idxT; + + scanf("%s%s", idS, idT); + idxS = id2idx(idS); + idxT = id2idx(idT); + + if (idxS < 0) { + printf("*Aeroporto %s inexistente\n", idS); + return; + } + + if (idxT < 0) { + printf("*Aeroporto %s inexistente\n", idT); + return; + } + + printf("Voos entre cidades %s:%s:%d:%d\n", idS, idT, + ligacoes[idxS][idxT], ligacoes[idxT][idxS]); +} + +/** + * @brief Funcao para processar o comando 'P'. + */ +void comando_P() { + int idmax = 0, in, out, i; + + for (i = 1; i < n_aeroportos; i++) + if (aeroportos[i].rotas > aeroportos[idmax].rotas) + idmax = i; + + for (in = out = i = 0; i < n_aeroportos; i++) { + out += ligacoes[idmax][i]; + in += ligacoes[i][idmax]; + } + + printf("Aeroporto com mais rotas %s:%d:%d\n", + aeroportos[idmax].id, out, in); +} + +/** + * @brief Funcao para processar o comando 'Q'. + */ +void comando_Q() { + int i, j, d[MAXNA]; + + for (i = 0; i < n_aeroportos; i++) + d[i] = 0; + + for (i = 0; i < n_aeroportos; i++) + for (j = 0; j < n_aeroportos; j++) + if (ligacoes[i][j] > 0) { + d[i] ++; + if (ligacoes[j][i] == 0) + d[j] ++; + } + + for (i = 0, j = 1; j < n_aeroportos; j++) + if (d[j] > d[i]) + i = j; + + printf("Aeroporto com mais ligacoes %s:%d\n", aeroportos[i].id, d[i]); +} + +/** + * @brief Funcao para processar o comando 'V'. + */ +void comando_V() { + int i, j, s = 0, t = 0; + + for (i = 0; i < n_aeroportos; i++) + for (j = 0; j < n_aeroportos; j++) + if (ligacoes[s][t] < ligacoes[i][j]) { + s = i; + t = j; + } + + printf("Voo mais popular %s:%s:%d\n", + aeroportos[s].id, aeroportos[t].id, ligacoes[s][t]); +} + +/** + * @brief Funcao para processar o comando 'C'. + */ +void comando_C() { + char id[IDLEN]; + int idx, i; + + scanf("%s", id); + idx = id2idx(id); + + if (idx < 0) { + printf("*Aeroporto %s inexistente\n", id); + return; + } + + aeroportos[idx].estado = FECHADO; + aeroportos[idx].rotas = 0; + + for (i = 0; i < n_aeroportos; i++) { + aeroportos[i].rotas -= ligacoes[idx][i]; + aeroportos[i].rotas -= ligacoes[i][idx]; + ligacoes[idx][i] = ligacoes[i][idx] = 0; + } +} + +/** + * @brief Funcao para processar o comando 'O'. + */ +void comando_O() { + char id[IDLEN]; + int idx; + + scanf("%s", id); + idx = id2idx(id); + + if (idx < 0) { + printf("*Aeroporto %s inexistente\n", id); + return; + } + + aeroportos[idx].estado = ABERTO; +} + +static int iacmp(const void *p, const void *q) { + int i = *((int const *) p); + int j = *((int const *) q); + + return strcmp(aeroportos[i].id, aeroportos[j].id); +} + +/** + * @brief Funcao para processar o comando 'L'. + */ +void comando_L() { + int tipo, i, j, max, wdin[MAXNA], wdout[MAXNA], wd[MAXNA], idx[MAXNA], dist[MAXNA+1]; + + scanf("%d", &tipo); + + for (i = 0; i < n_aeroportos; i++) { + wdin[i] = wdout[i] = wd[i] = 0; + idx[i] = i; + } + + for (i = 0; i < n_aeroportos; i++) + for (j = 0; j < n_aeroportos; j++) + if (ligacoes[i][j] > 0) { + wdout[i] += ligacoes[i][j]; + wdin[j] += ligacoes[i][j]; + wd[i] += ligacoes[i][j]; + wd[j] += ligacoes[i][j]; + } + + /* Ordenamos apenas para a listagem tipo 1. */ + if (tipo == 1) + qsort(idx, n_aeroportos, sizeof(int), iacmp); + + if (tipo < 2) { + for (i = 0; i < n_aeroportos; i++) + printf("%s:%d:%d:%d\n", + aeroportos[idx[i]].id, aeroportos[idx[i]].capacidade, + wdout[idx[i]], wdin[idx[i]]); + return; + } + + /* Listagem tipo 2: */ + for (max = wd[0], i = 1; i < n_aeroportos; i++) + if (wd[i] > max) + max = wd[i]; + + for (i = 0; i <= max && i <= MAXNA; i++) + dist[i] = 0; + + for (i = 0; i < n_aeroportos; i++) + if (wd[i] <= MAXNA) + dist[wd[i]] ++; + + for (i = 0; i <= max && i <= MAXNA; i++) + if (dist[i] > 0) + printf("%d:%d\n", i, dist[i]); +} + +/** + * @brief Funcao para processar o comando 'X'. + */ +void comando_X() { + int i, soma = 0; + + for (i = 0; i < n_aeroportos; i++) + soma += aeroportos[i].rotas; + + printf("%d:%d\n", soma/2, n_aeroportos); +} + +/** + * @brief Determina o indice para um aeroporto. + * + * @param 'id' identificador do aeroporto + * @return indice para o aeroporto 'id', ou -1 se nao existir + */ +int id2idx(char id[]) { + int i = 0; + + for (i = 0; i < n_aeroportos; i++) + if (strcmp(id, aeroportos[i].id) == 0) + return i; + + return -1; +} + diff --git a/proj/1516s2p2.c b/proj/1516s2p2.c new file mode 100644 index 0000000..4c52b40 --- /dev/null +++ b/proj/1516s2p2.c @@ -0,0 +1,237 @@ +/** + * @file proj2.c + * @brief Implementacao do segundo projecto de IAED. + */ +#include +#include +#include +#include + +#define SIZE 524288 /* Tamanho inicial para as estruturas de dados. */ +#define BUFF_LEN 1024 /* Tamanho do buffer de leitura das mensagens. */ +#define NUMSEP 11 /* Numero de separadores -- ver vector abaixo. */ + +static const char separators[] = {' ','\t',',',';','.','?','!','"','\n',':','\0'}; + +/** + * @brief Estrutura que representa um contador para uma hashtag. + */ +typedef struct { + char * id; + int nr; +} hashtag_t; + +/** + * Variaveis locais ao programa. + */ +static hashtag_t * attic; +static size_t attic_size; +static size_t attic_idx; +static size_t attic_max; +static size_t total; + +static hashtag_t ** htable; +static int * qsortidx; + +/* Comparador de hashtags para utilizar na hashtable. */ +static int htcmp(const hashtag_t *p, const hashtag_t *q) { + return strcmp(p->id, q->id); +} + +/* Comparador de hashtags para obter a hashtag com um maior numero de + * ocorrencias. */ +static int htnrcmp(hashtag_t *p, hashtag_t *q) { + int r = q->nr - p->nr; + if (r != 0) return r; + return strcmp(p->id, q->id); +} + +/* Comparador indirecto de hashtags para utilizar no qsort. */ +static int iacmp(const void *p, const void *q) { + int i = *((int const *) p); + int j = *((int const *) q); + int r = attic[j].nr - attic[i].nr; + if (r != 0) return r; + return strcmp(attic[i].id, attic[j].id); +} + +/* Funcao de dispersao DJB2. */ +static unsigned long djb2(char * str) { + unsigned long hash = 5381; + int c; + while ((c = *str++)) + hash = ((hash << 5) + hash) + c; /* hash * 33 + c */ + return hash; +} + +/* Insercao com recurso a "linear probing". */ +static void hinsert(hashtag_t * x) { + unsigned long int i = djb2(x->id) % (2*attic_size); + + while (htable[i]) + i = (i+1) % (2*attic_size); + + htable[i] = x; +} + +/* Procura com recurso a "linear probing". */ +static hashtag_t * hfind(hashtag_t * x) { + unsigned long int i = djb2(x->id) % (2*attic_size); + + while (htable[i]) + if (!htcmp(x, htable[i])) + return htable[i]; + else + i = (i+1) % (2*attic_size); + + return NULL; +} + +/* Funcao auxiliar para redimensionar as estruturas de dados. */ +static void enlarge() { + size_t i; + + fprintf(stderr, "enlarging...\n"); + + attic_size *= 2; + attic = realloc(attic, attic_size*sizeof(hashtag_t)); + + htable = realloc(htable, 2*attic_size*sizeof(hashtag_t*)); + memset(htable, 0x0, 2*attic_size*sizeof(hashtag_t*)); + for (i = 0; i < attic_idx; i++) + hinsert(attic + i); + + qsortidx = realloc(qsortidx, attic_size*sizeof(int)); +} + +/* Funcao auxiliar para processar cada mensagem. */ +static void process_msg(char * line) { + char *token = strtok(line, separators), *p; + hashtag_t * htpp, httmp; + + while (token != NULL) { + + /* Avancar se nao temos uma hashtag. */ + if (token[0] != '#') { + token = strtok(NULL, separators); + continue; + } + + /* Transformar para minusculas. */ + for (p = token; *p; ++p) + *p = tolower(*p); + + /* Vamos verificar se ja' temos esta hashtag... */ + httmp.id = token; + htpp = hfind(&httmp); + if (htpp) { + + /* Sim, temos, vamos incrementar. */ + htpp->nr ++; + + /* Actualizar o maximo. */ + if (attic_max >= attic_idx + || htnrcmp(htpp, attic + attic_max) < 0) + attic_max = htpp - attic; + + } else { + + /* Nao, vamos verificar se temos de aumentar o espaco. */ + if (attic_idx >= attic_size) + enlarge(); + + /* Gardar a nova hash tag com uma ocorrencia observada. */ + attic[attic_idx].id = strdup(token); + attic[attic_idx].nr = 1; + + qsortidx[attic_idx] = attic_idx; + + /* Adicionar a nova hashtag ao mapa. */ + hinsert(attic + attic_idx); + + /* Actualizar o maximo. */ + if (attic_max >= attic_idx + || htnrcmp(attic + attic_idx, attic + attic_max) < 0) + attic_max = attic_idx; + + /* Incrementar a numero de hashtags observadas. */ + attic_idx ++; + } + + /* Incrementar o total de observações. */ + total ++; + + token = strtok(NULL, separators); + } +} + +/** + * @brief Funcao main. + * + * @return Codigo de estado de saida do programa. + */ +int main(void) +{ + char buffer[BUFF_LEN]; + int i, qsort_needed = 1; + char comando; + + /* Inicializacao do arquivo de hashtags. */ + attic_idx = 0; + attic_size = SIZE; + attic = malloc(attic_size*sizeof(hashtag_t)); + attic_max = 0; + + qsortidx = malloc(sizeof(int)*attic_size); + + /* Inicializacao da hashtable de indexacao. */ + htable = malloc(2*attic_size*sizeof(hashtag_t*)); + memset(htable, 0x0, 2*attic_size*sizeof(hashtag_t*)); + + while (1) { + comando = getchar(); + + /* Processa o comando. */ + switch (comando) { + case 'a': + fgets(buffer, BUFF_LEN, stdin); + process_msg(buffer); + qsort_needed = 1; + break; + case 'm': + if (attic_max < attic_idx) + printf("%s %d\n", attic[attic_max].id, attic[attic_max].nr); + getchar(); /* Remover o '\n' no final do comando do stdin. */ + break; + case 'l': + /* Ordenacao indirecta com base num vector de indices + * temporario. */ + if (qsort_needed) + qsort(qsortidx, attic_idx, sizeof(int), iacmp); + qsort_needed = 0; + + for (i = 0; i < attic_idx; i++) + printf("%s %d\n", attic[qsortidx[i]].id, attic[qsortidx[i]].nr); + getchar(); /* Remover o '\n' no final do comando do stdin. */ + break; + case 's': + printf("%lu %lu\n", attic_idx, total); + getchar(); /* Remover o '\n' no final do comando do stdin. */ + break; + case 'x': + /* Este comando termina o programa. Libertar a memoria... */ + free(htable); + free(qsortidx); + for (i = 0; i < attic_idx; i++) + free(attic[i].id); + free(attic); + return EXIT_SUCCESS; + default: + /* Nao devemos chegar aqui. */ + exit(EXIT_FAILURE); + } + } + + /* Nao devemos chegar aqui em situacoes normais. */ + return EXIT_FAILURE; +} -- 2.30.2