Programmeringsmetodik: Lösningar till tentamen 2012-12-15

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, dels en som arbetar med länkade listor (list-kuponger.c), och dels en både kortare och smartare lösning som arbetar med fasta arrayer (array-kuponger.c). List-programmet har tidskomplexiteten O(n²) och tar ett par timmar att köra med den stora exempelfilen testfil-1M.txt, som innehåller en miljon observationer. Array-programmet har tidskomplexiteten O(n log n) och går mycket fortare. De exakta tiderna beror förstås på hur snabb dator man har.

Först list-lösningen (98 rader). Ladda ner: list-kuponger.c

// list-kuponger.c

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

#define MAXNUMMERLANGD 10

struct Kupongnummer {
    char nummer[MAXNUMMERLANGD + 1];
    int antal;
    struct Kupongnummer *next;
};

// Returnerar 1 om en kupongrad lästes in, 0 vid filslut. Avslutar programmet vid fel.
int las_nummer_fran_rad(FILE *tsin, char resultatplats[]) {
    char nummer[MAXNUMMERLANGD + 1];
    int r, y, m, d, h, min, s;
    int fscanf_resultat;
    fscanf_resultat =
        fscanf(tsin, "%s %d %d-%d-%d %d:%d:%d\n", nummer, &r, &y, &m, &d, &h, &min, &s);
    if (fscanf_resultat == 8) {
        strcpy(resultatplats, nummer);
        return 1;
    }
    else if (fscanf_resultat == EOF) {
        return 0;
    }
    else {
        fprintf(stderr, "list-kuponger: Felaktig rad på filen\n");
        exit(EXIT_FAILURE);
    }
}        

// Returnerar en pekare till den hittade kupongposten, eller NULL om ingen match
struct Kupongnummer *hitta(char nummer[], struct Kupongnummer *forsta_kupongen) {
    struct Kupongnummer *p = forsta_kupongen;
    while (p != NULL) {
        if (strcmp(p->nummer, nummer) == 0) {
            return p;
        }
        p = p->next;
    }
    return NULL;
}

// Lägger till 1 till den rätta kupongposten. Skapar en ny post om ingen matchade.
void lagra(char nummer[], struct Kupongnummer **forsta_kupongen_pp) {
    struct Kupongnummer *nummerposten = hitta(nummer, *forsta_kupongen_pp);
    if (nummerposten == NULL) {
        nummerposten = malloc(sizeof(struct Kupongnummer));
        if (nummerposten == NULL) {
            fprintf(stderr, "list-kuponger: Minnet är fullt\n");
            exit(EXIT_FAILURE);
        }
        strcpy(nummerposten->nummer, nummer);
        nummerposten->antal = 0;
        nummerposten->next = *forsta_kupongen_pp;
        *forsta_kupongen_pp = nummerposten;
    }
    nummerposten->antal++;
}

// Skriver ut numren på alla poster med antal större än 1
void visa_dubbletter(struct Kupongnummer *forsta_kupongen) {
    struct Kupongnummer *p = forsta_kupongen;
    while (p != NULL) {
        if (p->antal > 1) {
            printf("%s\n", p->nummer);
        }
        p = p->next;
    }
}

int main(int argc, char *argv[]) {
    if (argc != 2) {
        fprintf(stderr, "Skriv: list-kuponger FILNAMN\n");
        exit(EXIT_FAILURE);
    }
    FILE *tsin = fopen(argv[1], "r");
    if (tsin == NULL) {
        fprintf(stderr, "list-kuponger: Kunde inte öppna filen '%s'\n", argv[1]);
        exit(EXIT_FAILURE);
    }

    struct Kupongnummer *forsta_kupongen = NULL;

    char nummer[MAXNUMMERLANGD + 1];
    while (las_nummer_fran_rad(tsin, nummer) == 1) {
        lagra(nummer, &forsta_kupongen);
    }

    fclose(tsin);

    visa_dubbletter(forsta_kupongen);

    return EXIT_SUCCESS;
}

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

// array-kuponger.c

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

#define MAX_NUMMER_LANGD 10
#define MAX_KUPONGER 1000000

char kuponger[MAX_KUPONGER][MAX_NUMMER_LANGD + 1];
int antal_kuponger = 0;

int jamfor_kupongnummer(const void *k1, const void *k2) {
    return strcmp((char*)k1, (char*)k2);
}

int main(int argc, char *argv[]) {
    if (argc != 2) {
        fprintf(stderr, "Skriv: array-kuponger 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);
    }
    char kupongnummer[MAX_NUMMER_LANGD + 1];
    while (fscanf(tsin, "%s", kupongnummer) != EOF) {
        // Skippa resten av raden. Vi bryr oss bara om kupongnumren.
        while (getc(tsin) != '\n')
            ;
        if (antal_kuponger >= MAX_KUPONGER) {
            fprintf(stderr, "array-kuponger: För många kuponger\n");
            exit(EXIT_FAILURE);
        }
        strcpy(kuponger[antal_kuponger++], kupongnummer);
    }
    fclose(tsin);

    qsort(kuponger, antal_kuponger, sizeof(kuponger[0]), jamfor_kupongnummer);

    int aktuell_kupong = 0;
    while (aktuell_kupong < antal_kuponger) {
        if (strcmp(kuponger[aktuell_kupong], kuponger[aktuell_kupong + 1]) != 0) {
            // Den aktuella kupongen, och nästa, är olika, så ingen dubblett här.
            ++aktuell_kupong;
        }
        else {
            // Vi har hittat (minst) en dubblett. Den aktuella kupongen, och nästa, är lika.
            printf("%s\n", kuponger[aktuell_kupong]);
            do {
                ++aktuell_kupong;
            } while (aktuell_kupong < antal_kuponger && strcmp(kuponger[aktuell_kupong], kuponger[aktuell_kupong - 1]) == 0);
        }
    }

    return EXIT_SUCCESS;
} // main

2. Uppgift för betyget 4 respektive VG

En lösning med ett binärt träd (112 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-kuponger.c ovan. Ladda ner: trad-kuponger.c

// trad-kuponger.c

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

#define MAXNUMMERLANGD 10

struct TreeNode {
    char nummer[MAXNUMMERLANGD + 1];
    int antal;
    struct TreeNode *left, *right;
};

// Returnerar 1 om en kupongrad lästes in, 0 vid filslut. Avslutar programmet vid fel.
int las_nummer_fran_rad(FILE *tsin, char resultatplats[]) {
    char nummer[MAXNUMMERLANGD + 1];
    int r, y, m, d, h, min, s;
    int fscanf_resultat;
    fscanf_resultat =
        fscanf(tsin, "%s %d %d-%d-%d %d:%d:%d\n", nummer, &r, &y, &m, &d, &h, &min, &s);
    if (fscanf_resultat == 8) {
        strcpy(resultatplats, nummer);
        return 1;
    }
    else if (fscanf_resultat == EOF) {
        return 0;
    }
    else {
        fprintf(stderr, "trad-kuponger: Felaktig rad på filen\n");
        exit(EXIT_FAILURE);
    }
}        

// Returnerar en pekare till den hittade kupongposten, eller NULL om ingen match
struct TreeNode *hitta(char nummer[], struct TreeNode *root) {
    int strcmp_result;
    if (root == NULL) {
        return NULL;
    }
    else if ((strcmp_result = strcmp(root->nummer, nummer)) == 0) {
        return root;
    }
    else if (strcmp_result < 0) {
        return hitta(nummer, root->right);
    }
    else /* if (strcmp_result > 0) */ {
        return hitta(nummer, root->left);
    }
}

// Lägger till 1 till den rätta kupongposten. Skapar en ny post om ingen matchade.
void lagra(char nummer[], struct TreeNode **root_pp) {
    int strcmp_result;
    if (*root_pp == NULL) {
        struct TreeNode *new = malloc(sizeof(struct TreeNode));
        if (new == NULL) {
            fprintf(stderr, "trad-kuponger: Minnet är fullt\n");
            exit(EXIT_FAILURE);
        }
        strcpy(new->nummer, nummer);
        new->antal = 1;
        new->left = NULL;
        new->right = NULL;
        *root_pp = new;
    }
    else if ((strcmp_result = strcmp((*root_pp)->nummer, nummer)) == 0) {
        (*root_pp)->antal++;
    }
    else if (strcmp_result < 0) {
        lagra(nummer, &(*root_pp)->right);
    }
    else /* if (strcmp_result > 0) */ {
        lagra(nummer, &(*root_pp)->left);
    }
}

// Skriver ut numren på alla poster med antal större än 1
void visa_dubbletter(struct TreeNode *root) {
    if (root != NULL) {
        visa_dubbletter(root->left);
        if (root->antal > 1) {
            printf("%s\n", root->nummer);
        }
        visa_dubbletter(root->right);
    }
}

int main(int argc, char *argv[]) {
    if (argc != 2) {
        fprintf(stderr, "Skriv: trad-kuponger FILNAMN\n");
        exit(EXIT_FAILURE);
    }
    FILE *tsin = fopen(argv[1], "r");
    if (tsin == NULL) {
        fprintf(stderr, "trad-kuponger: Kunde inte öppna filen '%s'\n", argv[1]);
        exit(EXIT_FAILURE);
    }

    struct TreeNode *root = NULL;

    char nummer[MAXNUMMERLANGD + 1];
    while (las_nummer_fran_rad(tsin, nummer) == 1) {
        lagra(nummer, &root);
    }

    fclose(tsin);

    visa_dubbletter(root);

    return EXIT_SUCCESS;
}

3. Uppgift för betyget 5

Ingen lösning än.

Thomas Padron-McCarthy (thomas.padron-mccarthy@oru.se), 15 december 2012