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

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.

1. Uppgift för betyget 3 respektive G

Ladda ner: personflest.c

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

#define MAX_NAME_LENGTH 100

struct Person {
    char name[MAX_NAME_LENGTH + 1]; // +1 för \0
    char address[MAX_NAME_LENGTH + 1]; // +1 för \0
    int count;
    struct Person *next;
};

struct Person *find_person_in_list(struct Person *first, char name[], char address[]) {
    struct Person *this = first;
    while (this != NULL) {
        if (strcmp(this->name, name) == 0 && strcmp(this->address, address) == 0)
            return this;
        this = this->next;
    }
    return NULL;
} // find_person_in_list

struct Person *insert_person_first_in_list(struct Person **firstpp, char name[], char address[]) {
    struct Person *new = malloc(sizeof (struct Person));
    strcpy(new->name, name);
    strcpy(new->address, address);
    new->count = 0;
    new->next = *firstpp;
    *firstpp = new;
    return new;
} // insert_person_first_in_list

void add_person(struct Person **firstpp, char name[], char address[]) {
    struct Person *found = find_person_in_list(*firstpp, name, address);
    if (found == NULL)
        found = insert_person_first_in_list(firstpp, name, address);
    found->count++;
} // add_person

struct Person *find_max_in_list(struct Person *first) {
    struct Person *this = first;
    struct Person *max_so_far = first;

    while (this != NULL) {
        if (this->count > max_so_far->count)
            max_so_far = this;
        this = this->next;
    }
    return max_so_far;
} // find_max_in_list

// Bara för testning
void show_all_in_list(struct Person *first) {
    struct Person *this = first;
    int number = 0;

    while (this != NULL) {
        printf("%s, %s: %d gång(er)\n", this->name, this->address, this->count);
        this = this->next;
        ++number;
    }
    printf("Antal personer i listan: %d\n", number);
} //show_all_in_list

int main(int argc, char *argv[]) {
    struct Person *first_person = NULL;

    if (argc != 2) {
        fprintf(stderr, "Skriv: personflest FILNAME\n");
        exit(EXIT_FAILURE);
    }
    char *filname = argv[1];
    FILE *tsin = fopen(filname, "r");
    if (tsin == NULL) {
        fprintf(stderr, "Kunde inte läsa filen '%s'\n", filname);
        exit(EXIT_FAILURE);
    }

    char name[MAX_NAME_LENGTH + 1 + 1]; // +1 för \n, +1 för \0
    char address[MAX_NAME_LENGTH + 1 + 1]; // +1 för \n, +1 för \0

    while (fgets(name, sizeof name, tsin) != NULL) {
        name[strlen(name) - 1] = '\0';
        fgets(address, sizeof address, tsin);
        address[strlen(address) - 1] = '\0';
        add_person(&first_person, name, address);
    }

    fclose(tsin);

    struct Person *max_person = find_max_in_list(first_person);

    printf("Flest: %s, %s: %d gång(er)\n", max_person->name, max_person->address, max_person->count);

    // Bara för testning
    // show_all_in_list(first_person);

    return EXIT_SUCCESS;
} // main

2. Uppgift för betyget 4 respektive VG

Ladda ner: hashflest.c

Programmet tar 10-20 sekunder att köra med exempelfilen testfil-1M.txt, som innehåller en miljon personuppgifter (två miljoner rader) om 993559 olika personer.

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

#define MAX_NAME_LENGTH 100
#define HASH_TABLE_SIZE 1000003 // A prime

struct Person {
    char name[MAX_NAME_LENGTH + 1]; // +1 för \0
    char address[MAX_NAME_LENGTH + 1]; // +1 för \0
    int count;
    struct Person *next;
};

struct Person *find_person_in_list(struct Person *first, char name[], char address[]) {
    struct Person *this = first;
    while (this != NULL) {
        if (strcmp(this->name, name) == 0 && strcmp(this->address, address) == 0)
            return this;
        this = this->next;
    }
    return NULL;
} // find_person_in_list

struct Person *insert_person_first_in_list(struct Person **firstpp, char name[], char address[]) {
    struct Person *new = malloc(sizeof (struct Person));
    strcpy(new->name, name);
    strcpy(new->address, address);
    new->count = 0;
    new->next = *firstpp;
    *firstpp = new;
    return new;
} // insert_person_first_in_list

void add_person(struct Person **firstpp, char name[], char address[]) {
    struct Person *found = find_person_in_list(*firstpp, name, address);
    if (found == NULL)
        found = insert_person_first_in_list(firstpp, name, address);
    found->count++;
} // add_person

struct Person *find_max_in_list(struct Person *first) {
    struct Person *this = first;
    struct Person *max_so_far = first;

    while (this != NULL) {
        if (this->count > max_so_far->count)
            max_so_far = this;
        this = this->next;
    }
    return max_so_far;
} // find_max_in_list

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

unsigned int hash_person(unsigned char name[], unsigned char address[]) {
    return (raw_hash_string(name) + raw_hash_string(address)) / HASH_TABLE_SIZE;
}

void hash_add_person(struct Person *hash_table[], char name[], char address[]) {
    unsigned int bucket = hash_person(name, address);
    struct Person *found = find_person_in_list(hash_table[bucket], name, address);
    if (found == NULL)
        found = insert_person_first_in_list(&hash_table[bucket], name, address);
    found->count++;
} // hash_add_person

struct Person *hash_find_max(struct Person *hash_table[]) {
    struct Person *max_so_far = NULL;
    for (int i = 0; i < HASH_TABLE_SIZE; ++i) {
        if (hash_table[i] != NULL) {
            struct Person *max_in_bucket = find_max_in_list(hash_table[i]);
            if (max_so_far == NULL || max_in_bucket->count > max_so_far->count) {
                max_so_far = max_in_bucket;
            }
        }
    }
    return max_so_far;
} // hash_find_max

// Bara för testning
void show_all_in_hash_table(struct Person *hash_table[]) {
    int number = 0;
    for (int i = 0; i < HASH_TABLE_SIZE; ++i) {
        struct Person *this = hash_table[i];
        while (this != NULL) {
            printf("%s, %s: %d gång(er)\n", this->name, this->address, this->count);
            this = this->next;
            ++number;
        }
    }
    printf("Antal personer i listan: %d\n", number);
} //show_all_in_hash_table

// Outside of main, since it might not fit on the stack
struct Person* hash_table[HASH_TABLE_SIZE];

int main(int argc, char *argv[]) {
    if (argc != 2) {
        fprintf(stderr, "Skriv: hashflest FILNAME\n");
        exit(EXIT_FAILURE);
    }
    char *filname = argv[1];
    FILE *tsin = fopen(filname, "r");
    if (tsin == NULL) {
        fprintf(stderr, "Kunde inte läsa filen '%s'\n", filname);
        exit(EXIT_FAILURE);
    }

    char name[MAX_NAME_LENGTH + 1 + 1]; // +1 för \n, +1 för \0
    char address[MAX_NAME_LENGTH + 1 + 1]; // +1 för \n, +1 för \0

    while (fgets(name, sizeof name, tsin) != NULL) {
        name[strlen(name) - 1] = '\0';
        fgets(address, sizeof address, tsin);
        address[strlen(address) - 1] = '\0';
        hash_add_person(hash_table, name, address);
    }

    fclose(tsin);

    struct Person *max_person = hash_find_max(hash_table);

    printf("Flest: %s, %s: %d gång(er)\n", max_person->name, max_person->address, max_person->count);

    // Bara för testning
    // show_all_in_hash_table(hash_table);

    return EXIT_SUCCESS;
} // main

3. Uppgift för betyget 5

Ingen lösning än.

Thomas Padron-McCarthy (thomas.padron-mccarthy@oru.se), 22 augusti 2012