Programmeringsmetodik: Lösningar till tentamen 2008-11-06

Observera att detta är förslag på lösningar. Det kan finnas andra lösningar som också är korrekta, och det kan hända att en del av lösningarna är mer omfattande än vad som krävs för full poäng på uppgiften.

Uppgift 1 (1 p)

Uppgift 2 (1 p)

Uppgift 3 (1 p)

a) O(n)

b) Ungefär tio gånger längre tid, dvs ungefär 10 sekunder.

c) Datorn från b-uppgiften är mycket långsammare än en vanlig, modern skrivbordsdator. (I alla fall om det är själva loopen som tar en sekund att köra. Att starta programmet som loopen finns i kan ta ännu längre tid.)

Uppgift 4 (1 p)

a) O(n³)

b) Ungefär tusen gånger längre tid, dvs ungefär 1000 sekunder (17 minuter).

Uppgift 5 (1 p)

c1 = 3, c2 = 2, c3 = 13

Uppgift 6 (12 p)

a) (4p) Skriv (hela) include-filen MapPoint.h.

#ifndef MAPPOINT_H
#define MAPPOINT_H

#include <stdio.h>

struct MapPoint {
    int x;
    int y;
};

extern void init_point(struct MapPoint* mpp, int x, int y);
extern void save_point(FILE* f, struct MapPoint mp);
extern struct MapPoint fetch_point(FILE* f);
extern int same_point(struct MapPoint mp1, struct MapPoint mp2);

#endif

Kommentar 1: Det är inget fel, och kan till och med vara en snyggare lösning, att låta alla funktionerna ta en pekare till en MapPoint-post som argument, i stället för att skicka kopior (som i save_point) eller returnera en post (som i fetch_point).

Kommentar 2: Det kan också vara bra att använda typedef för att definiera en datatyp som bara heter MapPoint.

Kommentar 3: En alternativ lösning på init_point är att låta den returnera en post, som man sen med en vanlig tilldelning kopierar till den variabel som ska initieras.

b) (6p) Skriv (hela) implementationsfilen MapPoint.c.

#include <stdio.h>
#include "MapPoint.h"

void init_point(struct MapPoint* mpp, int x, int y) {
    mpp->x = x;
    mpp->y = y;
}

void save_point(FILE* f, struct MapPoint mp) {
    fprintf(f, "%d %d\n", mp.x, mp.y);
}

struct MapPoint fetch_point(FILE* f) {
    struct MapPoint mp;
    fscanf(f, "%d", &mp.x);
    fscanf(f, "%d", &mp.y);
    return mp;
}

int same_point(struct MapPoint mp1, struct MapPoint mp2) {
    return mp1.x == mp2.x && mp1.y == mp2.y;
}

c) (2p) Skriv (hela) filen test_points.c.

#include <stdio.h>
#include "MapPoint.h"

int main(void) {
    struct MapPoint p1;
    init_point(&p1, 3, 1);
    struct MapPoint p2;
    init_point(&p2, 4, 7);
    if (same_point(p1, p2) != 0)
        printf("Fel! same_point fungerade inte.\n");

    return 0;
}

Uppgift 7 (15 p)

a) (5p) Skriv (hela) include-filen Route.h.

#ifndef ROUTE_H
#define ROUTE_H

#include <stdio.h>
#include "MapPoint.h"

struct LinkPoint {
    struct MapPoint point;
    struct LinkPoint* next;
};

struct Route {
    struct LinkPoint* first;
    struct LinkPoint* last;
};

extern void init_route(struct Route* rp);
extern void append_point(struct Route* rp, struct MapPoint p);
extern void save_route(FILE* f, struct Route r);
extern struct Route fetch_route(FILE* f);
extern int has_visited(struct Route r, struct MapPoint p);
extern void cleanup_route(struct Route* rp);

#endif

Kommentar 1: I den här lösningen finns en pekare även till den sista länken i listan. Det går att klara sig med bara en pekare till den första, men då får inläggning i listan tidskomplexiteten O(n) i stället för O(1), eftersom man måste gå igenom hela listan för att hitta den sista länken. Insättning av n stycken punkter får då tidskomplexiteten O(n²) i stället för O(n). (Om man inte vänder listan med punkter baklänges!)

Kommentar 2: Det är inget fel, och kan till och med vara en snyggare lösning, att låta alla funktionerna ta pekare till Route som argument, i stället för att skicka kopior (som i save_route) eller returnera en post (som i fetch_route).

b) (10p) Skriv (hela) implementationsfilen Route.c.

#include <stdlib.h>
#include <stdio.h>
#include "Route.h"

void init_route(struct Route* rp) {
    rp->first = rp->last = NULL;
}

void append_point(struct Route* rp, struct MapPoint p) {
    struct LinkPoint* newnode = malloc(sizeof(struct LinkPoint));
    if (newnode == NULL) {
        fprintf(stderr, "Minnet är fullt. Programmet avslutas.\n");
        exit(EXIT_FAILURE);
    }
    newnode->point = p;
    newnode->next = NULL;
    if (rp->first == NULL) {
        rp->first = rp->last = newnode;
    }
    else {
        rp->last->next = newnode;
        rp->last = newnode;
    }
}

void save_route(FILE* f, struct Route r) {
    struct LinkPoint* node = r.first;
    while (node != NULL) {
        save_point(f, node->point);
        node = node->next;
    }
}

struct Route fetch_route(FILE* f) {
    struct Route r;
    init_route(&r);
    struct MapPoint p = fetch_point(f);
    while (!feof(f)) {
        append_point(&r, p);
        p = fetch_point(f);
    }
    return r;
}

int has_visited(struct Route r, struct MapPoint p) {
    struct LinkPoint* node = r.first;
    while (node != NULL) {
        if (same_point(node->point, p))
            return 1;
        node = node->next;
    }
    return 0;
}

void cleanup_route(struct Route* rp) {
    struct LinkPoint* node = rp->first;
    while (node != NULL) {
        struct LinkPoint* doomed = node;
        node = node->next;
        free(doomed);
    }
}

Uppgift 8 (8 p)

Först en lösning på a och b, med ett binärt träd:

a) (3p) Skriv (hela) include-filen PointSet.h.

#ifndef POINTSET_H
#define POINTSET_H

#include "MapPoint.h"

struct PointTreeNode {
    struct MapPoint point;
    struct PointTreeNode* left;
    struct PointTreeNode* right;
};

struct PointSet {
    struct PointTreeNode* root;
};

extern void init_pointset(struct PointSet* sp);
extern void add_point(struct PointSet* sp, struct MapPoint p);
extern int is_member(struct PointSet* sp, struct MapPoint p);

#endif

Kommentar 2: En punktmängd representeras av en post ("struct") som innehåller en pekare till rotnoden. Man kunde i stället använt bara en lös pekare till rotnoden, men för att det ska bli likadant som i de andra uppgifterna använder vi en post här också. Dessutom bygger hanteringen av abstrakta datatyper i C++ på att allt är structar (även om de där kallas för "klasser"), så det är lika bra att vänja sig redan nu.

b) (5p) Skriv (hela) implementationsfilen PointSet.c.

#include <stdlib.h>
#include <stdio.h>
#include "PointSet.h"

void init_pointset(struct PointSet* sp) {
    sp->root = NULL;
}

static int compare_points(struct MapPoint p1, struct MapPoint p2) {
    int xdiff = p1.x - p2.x;
    if (xdiff != 0)
        return xdiff;
    else
        return p1.y - p2.y;
}

static void tree_insert(struct PointTreeNode** rootp, struct MapPoint newpoint) {
    if (*rootp == NULL) {
        struct PointTreeNode* newnode = malloc(sizeof(struct PointTreeNode));
        if (newnode == NULL) {
            fprintf(stderr, "Minnet är fullt. Programmet avslutas.\n");
            exit(EXIT_FAILURE);
        }
        newnode->point = newpoint;
        newnode->left = newnode->right = NULL;
        *rootp = newnode;
    }
    else if (same_point(newpoint, (*rootp)->point))
        ;
    else if (compare_points(newpoint, (*rootp)->point) < 0)
        tree_insert(&(*rootp)->left, newpoint);
    else/* if (compare_points(newpoint, (*rootp)->point) > 0) */
        tree_insert(&(*rootp)->right, newpoint);
}

static struct PointTreeNode* tree_search(struct PointTreeNode* root, struct MapPoint wanted) {
    if (root == NULL)
        return NULL;
    else if (same_point(wanted, root->point))
        return root;
    else if (compare_points(wanted, root->point) < 0)
        return tree_search(root->left, wanted);
    else /* if (compare_points(wanted, root->point) > 0) */
        return tree_search(root->right, wanted);
}

void add_point(struct PointSet* sp, struct MapPoint p) {
    tree_insert(&sp->root, p);
}

int is_member(struct PointSet* sp, struct MapPoint p) {
    return tree_search(sp->root, p) != NULL;
}

Sedan en lösning på a och b, med en hashtabell:

a) (3p) Skriv (hela) include-filen PointSet.h.

#ifndef POINTSET_H
#define POINTSET_H

#include "MapPoint.h"

#define POINTSET_HASH_TABLE_SIZE 1000003

struct PointHashNode {
    struct MapPoint point;
    struct PointHashNode* next_in_bucket;
};

struct PointSet {
    struct PointHashNode* hash_table[POINTSET_HASH_TABLE_SIZE];
};

extern void init_pointset(struct PointSet* sp);
extern void add_point(struct PointSet* sp, struct MapPoint p);
extern int is_member(struct PointSet* sp, struct MapPoint p);

#endif

Kommentar 1: Alla funktionerna tar en pekare till PointSet som argument. Till is_member kunde man i stället ha skickat en kopia på posten, men för att göra koden likformig har valt att skicka en pekare även till den. Dessutom (varning!) innehåller posten hela hashtabell-arrayen, som är 4 megabyte stor eller ännu mer, och det kan hända att programmet kraschar om man försöker skicka ett så stort dataobjekt som argument till en funktion!

Kommentar 2: En punktmängd representeras av en post ("struct") som innehåller hashtabell-arrayen. Man kunde i stället använt bara en lös array, men för att det ska bli likadant som i de andra uppgifterna använder vi en post här också. Dessutom bygger hanteringen av abstrakta datatyper i C++ på att allt är structar (även om de där kallas för "klasser"), så det är lika bra att vänja sig redan nu. Ytterligare ett skäl till att baka in arrayen i en struct är att om man vill använda typedef för att definiera en datatyp som bara heter PointSet, så är det inte så bra att typedeffa arrayer. Arrayer fungerar lite speciellt i C, till exempel det där med att man inte kan skicka dem som kopior till och från funktioner, och därför kan det vara dumt att dölja det faktum att något är en array.

b) (5p) Skriv (hela) implementationsfilen PointSet.c.

#include <stdlib.h>
#include <stdio.h>
#include "PointSet.h"

void init_pointset(struct PointSet* sp) {
    for (int i = 0; i < POINTSET_HASH_TABLE_SIZE; ++i)
        sp->hash_table[i] = NULL;
}

static int hash(struct MapPoint p) {
    int sum = p.x + p.y;
    if (sum < 0)
        sum = -sum;
    return sum % POINTSET_HASH_TABLE_SIZE;
}

void add_point(struct PointSet* sp, struct MapPoint p) {
    if (is_member(sp, p) == 0) {
        int position = hash(p);
        struct PointHashNode* newnode = malloc(sizeof(struct PointHashNode));
        if (newnode == NULL) {
            fprintf(stderr, "Minnet är fullt. Programmet avslutas.\n");
            exit(EXIT_FAILURE);
        }
        newnode->point = p;
        newnode->next_in_bucket = sp->hash_table[position];
        sp->hash_table[position] = newnode;
    }
}

int is_member(struct PointSet* sp, struct MapPoint p) {
    int position = hash(p);
    struct PointHashNode* np = sp->hash_table[position];
    while (np != NULL) {
        if (same_point(np->point, p))
            return 1;
        np = np->next_in_bucket;
    }
    return 0;
}

Thomas Padron-McCarthy (Thomas.Padron-McCarthy@oru.se), 3 december 2008