Programmeringsmetodik: Lösningar till tentamen 2009-08-20

Observera också att just den här lösningen inte skulle ge full poäng på tentan, eftersom jag inte modulariserat programmet med abstrakta datatyper och uppdelning på flera filer.

Om man skulle skriva det här programmet på riktigt, och inte som en tentauppgift där man just ska visa att man förstått modularisering, skulle man förmodligen inte bry sig om den typen av modularisering, eftersom programmet är så litet att det blir överblickbart ändå, och alltför mycket uppdelning kan tvärtom göra programmet svårare att skriva och förstå.

Här finns också ett program som slumpar fram filerna platser.txt och mosade.txt, så att man kan provköra sitt program: skapa-filer.c. (Programmet skapar 3 miljarder mosningar, och filen mosade.txt blir ungefär 30 gigabyte stor.)

Uppgiften (30 p)

Programmet max-mosade.c:

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

#define TROLIGT_ANTAL_PLATSER (3*1000*1000)
#define HASH_SIZE (TROLIGT_ANTAL_PLATSER * 2)

struct plats {
    int nr;
    double latitud, longitud;
    int mosade; // Vi räknar med att maxantalet mosade får plats i en vanlig "int"
    struct plats* next_in_bucket;
};

struct plats* hash_table[HASH_SIZE];

int hashfunktion(int nyckel) {
    return nyckel % HASH_SIZE;
}

struct plats* find(int platsnummer) {
    struct plats* p = hash_table[hashfunktion(platsnummer)];
    while (p != NULL) {
        if (p->nr == platsnummer)
            return p;
        p = p->next_in_bucket;
    }
    return NULL;
}

int main(void) {
    FILE* platsfil = fopen("platser.txt", "r");
    if (platsfil == NULL) {
        fprintf(stderr, "Gick inte att öppna platsfilen!\n");
        exit(EXIT_FAILURE);
    }

    printf("Läser platser...\n");
    int antal_platser = 0;
    struct plats platsen;
    while (fscanf(platsfil, "%d %lf %lf", &platsen.nr, &platsen.latitud, &platsen.longitud) == 3) {

        platsen.mosade = 0;
        platsen.next_in_bucket = NULL;

        struct plats* p = malloc(sizeof(struct plats));
        if (p == NULL) {
            fprintf(stderr, "För många platser. Minnet är fullt!\n");
            exit(EXIT_FAILURE);
        }

        *p = platsen;

        // Stoppa in platsen i hashtabellen!
        int hashplats = hashfunktion(p->nr);
        p->next_in_bucket = hash_table[hashplats];
        hash_table[hashplats] = p;

        ++antal_platser;
    }

    fclose(platsfil);

    printf("Läst in platser: %d\n", antal_platser);

    FILE* mosfil = fopen("mosade.txt", "r");
    if (mosfil == NULL) {
        fprintf(stderr, "Gick inte att öppna mosfilen!\n");
        exit(EXIT_FAILURE);
    }

    printf("Läser mosade...\n");
    long int antal_mosningar = 0; // Det totala antalet mosningar får nog inte plats i en vanlig "int"
    int platsnummer, mosade;
    while (fscanf(mosfil, "%d %d", &platsnummer, &mosade) == 2) {

        struct plats* p = find(platsnummer);
        if (p == NULL) {
            fprintf(stderr, "Aj aj aj! Plats nummer %d finns inte!\n", platsnummer);
            exit(EXIT_FAILURE);
        }
        p->mosade += mosade;

        ++antal_mosningar;
    }

    fclose(mosfil);

    printf("Läst in mosningar: %ld\n", antal_mosningar);

    printf("Letar efter platsen med maxantalet...\n");

    // Vi förutsätter att det finns minst en plats med mer än noll mosade
    struct plats maxmosning;
    maxmosning.mosade = 0;
    for (int i = 0; i < HASH_SIZE; ++i) {
        struct plats* p = hash_table[i];
        while (p != NULL) {
            if (p->mosade > maxmosning.mosade)
                maxmosning = *p;
            p = p->next_in_bucket;
        }
    }

    printf("Platsen med maxantalet: nummer %d, latitud %f, longitud %f, %d mosade!\n",
           maxmosning.nr, maxmosning.latitud, maxmosning.longitud, maxmosning.mosade);

    return 0;
}