Programmeringsmetodik: Lösningar till tentamen 2012-11-08

Observera att detta är ett förslag på lösningar. Det finns andra lösningar som också är korrekta.

Lösningarna är skrivna i en modernare version av C än vad Visual Studio 2010 klarar av. Vi har inte gjort någon modularisering med separatkompilering, men det skulle kunna underlätta arbetet.

1. Uppgift för betyget 3 respektive G

Här visar vi två olika lösningar, en som arbetar med länkade listor (list-aliens.c), och en lite enklare lösning som arbetar med fasta arrayer (array-aliens.c). Bägge programmen tar ett par timmar att köra med exempelfilen testfil-1M.txt, som innehåller en miljon observationer. Den exakta tiden beror förstås på hur snabb dator man har.

Först list-lösningen (139 rader). Ladda ner: list-aliens.c

// list-aliens.c

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

// Det här är en observation. Varje signal kan ha många observationer.
// De observationer som hör till en viss signal bildar en länkad lista.
struct Observation {
    int observatory;
    struct Observation *next_observation_p;
};

// Det här är en signal. h+m+s+x+y bildar en unik identifierare.
// Alla signalerna bildar en länkad lista.
struct Signal {
    int h, m, s; // Tidpunkt
    int x, y; // Riktning
    struct Observation *first_observation_p;
    struct Signal *next_signal_p;
};

// Det här är en inläst rad med en observation från filen.
// Den används bara medan man arbetar med den raden, och sparas inte.
struct ObsLine {
    int observatory;
    int h, m, s; // Tidpunkt
    int x, y; // Riktning
};

// Returnerar en signal som matchar raden, eller NULL om ingen finns
struct Signal *find_signal_in_list(struct Signal *first_signal_p, struct ObsLine *olp) {
    struct Signal *sp = first_signal_p;
    while (sp != NULL) {
        if (sp->h == olp->h && sp->m == olp->m && sp->s == olp->s && sp->x == olp->x && sp->y == olp->y)
            return sp;
        sp = sp->next_signal_p;
    }
    return NULL;
}

// Lägger till en signal i listan av signaler.
// Vi förutsätter att ingen likadan signal redan finns.
struct Signal *add_signal_to_list(struct Signal **first_signal_pp, struct ObsLine *olp) {
    struct Signal *newp = malloc(sizeof(struct Signal));
    if (newp == NULL) {
        fprintf(stderr, "Minnet fullt.\n");
        exit(EXIT_FAILURE);
    }
    newp->h = olp->h;
    newp->m = olp->m;
    newp->s = olp->s;
    newp->x = olp->x;
    newp->y = olp->y;
    newp->first_observation_p = NULL;
    newp->next_signal_p = *first_signal_pp;
    (*first_signal_pp) = newp;
    return newp;
}

// Lägger till en observation till en signal
void add_observation_to_signal(struct Signal *this_signal_p, int observatory) {
    struct Observation *newp = malloc(sizeof(struct Observation));
    if (newp == NULL) {
        fprintf(stderr, "Minnet fullt.\n");
        exit(EXIT_FAILURE);
    }
    newp->observatory = observatory;
    newp->next_observation_p = this_signal_p->first_observation_p;
    this_signal_p->first_observation_p = newp;
}

// Läser in en rad med data om en observation.
// Returnerar 1 om det gick bra, 0 vid filslut, och avbryter vid fel.
int read_obsline(FILE *tsin, struct ObsLine *olp) {
    static int line_number = 0;
    char line[100]; // Borde räcka gott och väl
    if (fgets(line, sizeof line, tsin) == NULL)
        return 0;
    ++line_number;
    // Ta bort radslutstecken om det finns
    int n = strlen(line);
    if (line[n - 1] == '\n')
        line[n - 1] = '\0';
    if (sscanf(line, "%d %d:%d:%d %d %d",
               &olp->observatory, &olp->h, &olp->m, &olp->s, &olp->x, &olp->y) != 6) {
        fprintf(stderr, "Felaktig rad nummer %d: '%s'\n", line_number, line);
        exit(EXIT_FAILURE);
    }
    return 1;
}

// Skriver ut de signaler i listan som hade mer än en observation
void show_interesting_signals_in_list(struct Signal *first_signal_p) {
    struct Signal *sp = first_signal_p;
    while (sp != NULL) {
        // Det finns alltid minst en observation, så det kan inte bli NULL-fel i villkoret nedan
        if (sp->first_observation_p->next_observation_p != NULL) {
            // Minst två observationer
            printf("Tid: %02d:%02d:%02d Riktning: %d %d Observatorier:",
                   sp->h, sp->m, sp->s, sp->x, sp->y);
            struct Observation *op = sp->first_observation_p;
            while (op != NULL) {
                printf(" %d", op->observatory);
                op = op->next_observation_p;
            }
            printf("\n");
        }
        sp = sp->next_signal_p;
    }
}

int main(int argc, char *argv[]) {
    if (argc != 2) {
        fprintf(stderr, "Skriv: list-aliens FILNAMN\n");
        exit(EXIT_FAILURE);
    }
    char *file_name = argv[1];
    FILE *tsin = fopen(file_name, "r");
    if (tsin == NULL) {
        fprintf(stderr, "Kunde inte läsa filen '%s'\n", file_name);
        fprintf(stderr, "Möjlig orsak: %s (felkod %d)\n", strerror(errno), errno);
        exit(EXIT_FAILURE);
    }
    struct ObsLine obsline;
    struct Signal *first_signal_p = NULL;
    while (read_obsline(tsin, &obsline) == 1) {
        struct Signal *signal_p = find_signal_in_list(first_signal_p, &obsline);
        if (signal_p == NULL)
            signal_p = add_signal_to_list(&first_signal_p, &obsline);
        add_observation_to_signal(signal_p, obsline.observatory);
    }
    fclose(tsin);

    show_interesting_signals_in_list(first_signal_p);

    return EXIT_SUCCESS;
} // main

Därefter array-lösningen (94 rader). Ladda ner: array-aliens.c

// array-aliens.c

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

#define MAX_SIGNALS 1000000
#define MAX_OBSERVATIONS 10

// Det här är en signal. h+m+s+x+y bildar en unik identifierare.
struct Signal {
    int h, m, s; // Tidpunkt
    int x, y; // Riktning
    int observatories[MAX_OBSERVATIONS];
    int nr_observations;
};

struct Signal signals[MAX_SIGNALS];
int nr_signals = 0;

// Returnerar vilken signal som matchar raden, eller -1 om ingen finns
int find_signal(int h, int  m, int s, int x, int y) {
    for (int i = 0; i < nr_signals; ++i) {
        if (signals[i].h == h && signals[i].m == m && signals[i].s == s && signals[i].x == x && signals[i].y == y)
            return i;
    }
    return -1;
}

// Lägger till en signal i arrayen av signaler.
// Vi förutsätter att ingen likadan signal redan finns.
int add_signal(int h, int  m, int s, int x, int y) {
    signals[nr_signals].h = h;
    signals[nr_signals].m = m;
    signals[nr_signals].s = s;
    signals[nr_signals].x = x;
    signals[nr_signals].y = y;
    signals[nr_signals].nr_observations = 0;
    return nr_signals++;
}

// Lägger till en observation till en signal
void add_observation(int signal_nr, int observatory) {
    int nr_observations = signals[signal_nr].nr_observations;
    signals[signal_nr].observatories[nr_observations] = observatory;
    signals[signal_nr].nr_observations++;

    // Eller bara:
    // signals[signal_nr].observatories[signals[signal_nr].nr_observations++] = observatory;
}

// Skriver ut de signaler i arrayen som hade mer än en observation
void show_interesting_signals(void) {
    for (int s = 0; s < nr_signals; ++s) {
        if (signals[s].nr_observations > 1) {
            // Minst två observationer
            printf("Tid: %02d:%02d:%02d Riktning: %d %d Observatorier:",
                   signals[s].h, signals[s].m, signals[s].s, signals[s].x, signals[s].y);
            for (int o = 0; o < signals[s].nr_observations; ++o) {
                printf(" %d", signals[s].observatories[o]);
            }
            printf("\n");
        }
    }
}

int main(int argc, char *argv[]) {
    if (argc != 2) {
        fprintf(stderr, "Skriv: array-aliens FILNAMN\n");
        exit(EXIT_FAILURE);
    }
    char *file_name = argv[1];
    FILE *tsin = fopen(file_name, "r");
    if (tsin == NULL) {
        fprintf(stderr, "Kunde inte läsa filen '%s'\n", file_name);
        fprintf(stderr, "Möjlig orsak: %s (felkod %d)\n", strerror(errno), errno);
        exit(EXIT_FAILURE);
    }
    int observatory;
    int h, m, s; // Tidpunkt
    int x, y; // Riktning
    while (fscanf(tsin, "%d %d:%d:%d %d %d", &observatory, &h, &m, &s, &x, &y) != EOF) {
        int signal_nr = find_signal(h, m, s, x, y);
        if (signal_nr == -1)
            signal_nr = add_signal(h, m, s, x, y);
        add_observation(signal_nr, observatory);
    }
    fclose(tsin);

    show_interesting_signals();

    return EXIT_SUCCESS;
} // main

2. Uppgift för betyget 4 respektive VG

En lösning med en hashtabell (170 rader). Programmet tar ett par sekunder att köra med exempelfilen testfil-1M.txt, som innehåller en miljon observationer. Vi har återanvänt mycket av koden från list-aliens.c ovan. Ladda ner: hash-aliens.c

// hash-aliens.c

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

// Det här är en observation. Varje signal kan ha många observationer.
// De observationer som hör till en viss signal bildar en länkad lista.
struct Observation {
    int observatory;
    struct Observation *next_observation_p;
};

// Det här är en signal. h+m+s+x+y bildar en unik identifierare.
// Signalerna i en buycket i hashtabellen bildar en länkad lista.
struct Signal {
    int h, m, s; // Tidpunkt
    int x, y; // Riktning
    struct Observation *first_observation_p;
    struct Signal *next_signal_p;
};

// Det här är en inläst rad med en observation från filen.
// Den används bara medan man arbetar med den raden, och sparas inte.
struct ObsLine {
    int observatory;
    int h, m, s; // Tidpunkt
    int x, y; // Riktning
};

#define HASH_TABLE_SIZE (3*1000*1000 + 1)

// Alla platserna i hashtabellen initieras automatiskt till NULL
struct Signal *hash_table[HASH_TABLE_SIZE];

unsigned int hash_signal(struct ObsLine *olp) {
    return ((3600 * olp->h + 60 * olp->m + olp->s) * 1000 + 1000 * olp->x + olp->y) % HASH_TABLE_SIZE;
}

// Returnerar en signal som matchar raden, eller NULL om ingen finns
struct Signal *find_signal_in_list(struct Signal *first_signal_p, struct ObsLine *olp) {
    struct Signal *sp = first_signal_p;
    while (sp != NULL) {
        if (sp->h == olp->h && sp->m == olp->m && sp->s == olp->s && sp->x == olp->x && sp->y == olp->y)
            return sp;
        sp = sp->next_signal_p;
    }
    return NULL;
}

// Returnerar en signal som matchar raden, eller NULL om ingen finns
struct Signal *find_signal_in_hash_table(struct ObsLine *olp) {
    unsigned int bucket = hash_signal(olp);
    struct Signal *sp = hash_table[bucket];
    return find_signal_in_list(sp, olp);

    // Eller bara: return find_signal_in_list(hash_table[hash_signal(olp)], olp);
}

// Lägger till en signal i listan av signaler.
// Vi förutsätter att ingen likadan signal redan finns.
struct Signal *add_signal_to_list(struct Signal **first_signal_pp, struct ObsLine *olp) {
    struct Signal *newp = malloc(sizeof(struct Signal));
    if (newp == NULL) {
        fprintf(stderr, "Minnet fullt.\n");
        exit(EXIT_FAILURE);
    }
    newp->h = olp->h;
    newp->m = olp->m;
    newp->s = olp->s;
    newp->x = olp->x;
    newp->y = olp->y;
    newp->first_observation_p = NULL;
    newp->next_signal_p = *first_signal_pp;
    (*first_signal_pp) = newp;
    return newp;
}

// Lägger till en signal i hashtabellen.
// Vi förutsätter att ingen likadan signal redan finns.
struct Signal *add_signal_to_hash_table(struct ObsLine *olp) {
    unsigned int bucket = hash_signal(olp);
    return add_signal_to_list(&hash_table[bucket], olp);
}

// Lägger till en observation till en signal
void add_observation_to_signal(struct Signal *this_signal_p, int observatory) {
    struct Observation *newp = malloc(sizeof(struct Observation));
    if (newp == NULL) {
        fprintf(stderr, "Minnet fullt.\n");
        exit(EXIT_FAILURE);
    }
    newp->observatory = observatory;
    newp->next_observation_p = this_signal_p->first_observation_p;
    this_signal_p->first_observation_p = newp;
}

// Läser in en rad med data om en observation.
// Returnerar 1 om det gick bra, 0 vid filslut, och avbryter vid fel.
int read_obsline(FILE *tsin, struct ObsLine *olp) {
    static int line_number = 0;
    char line[100]; // Borde räcka gott och väl
    if (fgets(line, sizeof line, tsin) == NULL)
        return 0;
    ++line_number;
    // Ta bort radslutstecken om det finns
    int n = strlen(line);
    if (line[n - 1] == '\n')
        line[n - 1] = '\0';
    if (sscanf(line, "%d %d:%d:%d %d %d",
               &olp->observatory, &olp->h, &olp->m, &olp->s, &olp->x, &olp->y) != 6) {
        fprintf(stderr, "Felaktig rad nummer %d: '%s'\n", line_number, line);
        exit(EXIT_FAILURE);
    }
    return 1;
}

// Skriver ut de signaler i listan som hade mer än en observation
void show_interesting_signals_in_list(struct Signal *first_signal_p) {
    struct Signal *sp = first_signal_p;
    while (sp != NULL) {
        // Det finns alltid minst en observation, så det kan inte bli NULL-fel i villkoret nedan
        if (sp->first_observation_p->next_observation_p != NULL) {
            // Minst två observationer
            printf("Tid: %02d:%02d:%02d Riktning: %d %d Observatorier:",
                   sp->h, sp->m, sp->s, sp->x, sp->y);
            struct Observation *op = sp->first_observation_p;
            while (op != NULL) {
                printf(" %d", op->observatory);
                op = op->next_observation_p;
            }
            printf("\n");
        }
        sp = sp->next_signal_p;
    }
}

// Skriver ut de signaler i hashtabellen som hade mer än en observation
void show_interesting_signals_in_hash_table(void) {
    for (unsigned int bucket = 0; bucket < HASH_TABLE_SIZE; ++bucket) {
        show_interesting_signals_in_list(hash_table[bucket]);
    }
}

int main(int argc, char *argv[]) {
    if (argc != 2) {
        fprintf(stderr, "Skriv: hash-aliens FILNAMN\n");
        exit(EXIT_FAILURE);
    }
    char *file_name = argv[1];
    FILE *tsin = fopen(file_name, "r");
    if (tsin == NULL) {
        fprintf(stderr, "Kunde inte läsa filen '%s'\n", file_name);
        fprintf(stderr, "Möjlig orsak: %s (felkod %d)\n", strerror(errno), errno);
        exit(EXIT_FAILURE);
    }
    struct ObsLine obsline;
    while (read_obsline(tsin, &obsline) == 1) {
        struct Signal *signal_p = find_signal_in_hash_table(&obsline);
        if (signal_p == NULL)
            signal_p = add_signal_to_hash_table(&obsline);
        add_observation_to_signal(signal_p, obsline.observatory);
    }
    fclose(tsin);

    show_interesting_signals_in_hash_table();

    return EXIT_SUCCESS;
} // main

3. Uppgift för betyget 5

Ingen lösning än.

Thomas Padron-McCarthy (thomas.padron-mccarthy@oru.se), 16 november 2012