Programmeringsmetodik: Lösningar till tentamen 2013-08-22

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 2012 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

Först list-lösningen (64 rader). Ladda ner: list-svampar.c

// list-svampar.c

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

struct Bil {
    char bilnummer[6 + 1]; /* På formatet ABC123, utan mellanslag */
    double viktsumma;
    struct Bil *nasta_bil;
};

int main(int argc, char *argv[]) {
    if (argc != 2) {
        fprintf(stderr, "Skriv: list-svampar  SVAMPFILENS-NAMN\n");
        exit(EXIT_FAILURE);
    }
    FILE *svampfil = fopen(argv[1], "r");
    if (svampfil == NULL) {
        fprintf(stderr, "list-svampar: Kunde inte öppna filen '%s'\n", argv[1]);
        exit(EXIT_FAILURE);
    }
    struct Bil *forsta_bilen = NULL;
    double svampvikt;
    char bilnummer[6 + 1];

    while (fscanf(svampfil, "%*d %*s %lf %s", &svampvikt, bilnummer) == 2) {
        struct Bil *p = forsta_bilen;
        while (p != NULL && strcmp(bilnummer, p->bilnummer) != 0) {
            p = p->nasta_bil;
        }
        struct Bil *bilen;
        if (p != NULL) {
            bilen = p;
        }
        else {
            bilen = malloc(sizeof(struct Bil));
            if (bilen == NULL) {
                fprintf(stderr, "list-svampar: Kunde inte reservera %d bytes.\n",(int)sizeof(struct Bil));
                exit(EXIT_FAILURE);
            }
            strcpy(bilen->bilnummer, bilnummer);
            bilen->viktsumma = 0;
            bilen->nasta_bil = forsta_bilen;
            forsta_bilen = bilen;
        }
        bilen->viktsumma += svampvikt;
    }

    fclose(svampfil);

    struct Bil *p = forsta_bilen;
    struct Bil *tyngsta_bilen = forsta_bilen;

    while (p != NULL) {
        if (p->viktsumma > tyngsta_bilen->viktsumma)
            tyngsta_bilen = p;
        p = p->nasta_bil;
    }

    printf("Tyngsta bilen: %s\n", tyngsta_bilen->bilnummer);

    return EXIT_SUCCESS;
}

2. Uppgift för betyget 4 respektive VG

En lösning med en hashtabell (79 rader). Programmet tar ungefär en sekund att köra med exempelfilen 1M-svampar.txt, som innehåller en miljon svampar. Programmet ovan, med en länkad lista, tar ungefär en halvtimme. Ladda ner: hash-svampar.c

// hash-svampar.c

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

struct Bil {
    char bilnummer[6 + 1]; /* På formatet ABC123, utan mellanslag */
    double viktsumma;
    struct Bil *nasta_bil;
};

#define HASHTABELLENS_STORLEK 1000003

unsigned long int hasha_strang(char s[], long int hashtabellens_storlek) {
    unsigned long int resultat = 5381;
    int c;
    while ((c = *s++) != '\0')
        resultat = resultat * 33 + c;
    return resultat % hashtabellens_storlek;
}

struct Bil* hitta_bil(struct Bil **hashtabell, long int hashtabellens_storlek, char bilnummer[]) {
    long int bucket = hasha_strang(bilnummer, hashtabellens_storlek);
    struct Bil* p = hashtabell[bucket];
    while (p != NULL && strcmp(bilnummer, p->bilnummer) != 0) {
        p = p->nasta_bil;
    }
    return p;
}

struct Bil*  lagg_in_bil(struct Bil **hashtabell, long int hashtabellens_storlek, char bilnummer[]) {
    long int bucket = hasha_strang(bilnummer, hashtabellens_storlek);
    struct Bil* nya = malloc(sizeof(struct Bil));
    strcpy(nya->bilnummer, bilnummer);
    struct Bil* gamla_forsta = hashtabell[bucket];
    nya->nasta_bil = gamla_forsta;
    hashtabell[bucket] = nya;
    return nya;
}

struct Bil *bilhashtabellen[HASHTABELLENS_STORLEK]; // Lagringsklass extern, så den är nollad från början

int main(int argc, char *argv[]) {
    if (argc != 2) {
        fprintf(stderr, "Skriv: hash-svampar  SVAMPFILENS-NAMN\n");
        exit(EXIT_FAILURE);
    }
    FILE *svampfil = fopen(argv[1], "r");
    if (svampfil == NULL) {
        fprintf(stderr, "hash-svampar: Kunde inte öppna filen '%s'\n", argv[1]);
        exit(EXIT_FAILURE);
    }
    double svampvikt;
    char bilnummer[6 + 1];

    while (fscanf(svampfil, "%*d %*s %lf %s", &svampvikt, bilnummer) == 2) {
        struct Bil *bilen = hitta_bil(bilhashtabellen, HASHTABELLENS_STORLEK, bilnummer);
        if (bilen == NULL)
            bilen = lagg_in_bil(bilhashtabellen, HASHTABELLENS_STORLEK, bilnummer);
        bilen->viktsumma += svampvikt;
    }

    fclose(svampfil);

    struct Bil *tyngsta_bilen = NULL;
    for (long int bucket = 0; bucket < HASHTABELLENS_STORLEK; ++bucket) {
        struct Bil* p = bilhashtabellen[bucket];
        while (p != NULL) {
            if (tyngsta_bilen == NULL || p->viktsumma > tyngsta_bilen->viktsumma)
                tyngsta_bilen = p;
            p = p->nasta_bil;
        }
    }

    printf("Tyngsta bilen: %s\n", tyngsta_bilen->bilnummer);

    return EXIT_SUCCESS;
}

3. Uppgift för betyget 5

Ingen lösning än.

Thomas Padron-McCarthy (thomas.padron-mccarthy@oru.se), 21 augusti 2013