Programmeringsmetodik: Lösningar till tentamen 2011-12-10

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

Här kommer två olika förslag på hur man kan lösa uppgiften.

Först en version som lagrar paren av sökord och webbadresser i en länkad lista. Listan består av poster av typen struct WordAddressPair. Den lösningen är bra på så sätt att den är relativt enkel och den har linjär tidskomplexitet, men den gör inget särskilt för att gruppera ihop förekomsterna av samma sökord. Därför vet man inte hur många unika ord det finns, och för att skriva ut antalet träffar innan man skriver ut adresserna måste man gå igenom listan två gånger.

Ladda ner: listgoogle-1.c

/* listgoogle-1.c */

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

#define MAX_WORD_LENGTH 100
#define MAX_ADDRESS_LENGTH 1000
#define MAX_FILE_NAME_LENGTH 1000

void *safe_malloc(size_t s) {
    void *result = malloc(s);
    if (result == NULL) {
        fprintf(stderr, "Kunde inte allokera %lu bytes.\n", (unsigned long)s);
        exit(EXIT_FAILURE);
    }
    return result;
}

struct WordAddressPair {
    char word[MAX_WORD_LENGTH + 1];
    char address[MAX_ADDRESS_LENGTH + 1];
    struct WordAddressPair *next_pair_p;
};

/* Some functions for working with the list of word/address pairs */

void add_pair(struct WordAddressPair **first_pair_pp, char word[], char address[]) {
    struct WordAddressPair *new_pair_p = malloc(sizeof(struct WordAddressPair));
    strcpy(new_pair_p->word, word);
    strcpy(new_pair_p->address, address);
    new_pair_p->next_pair_p = *first_pair_pp;
    *first_pair_pp = new_pair_p;
}

void search_and_print_the_hits(struct WordAddressPair *first_pair_p, char wanted_word[]) {
    struct WordAddressPair *this_pair_p = first_pair_p;
    int nr_hits = 0;
    /* First, just count the hits */
    while (this_pair_p != NULL) {
        if (strcmp(this_pair_p->word, wanted_word) == 0) {
            ++nr_hits;
        }
        this_pair_p = this_pair_p->next_pair_p;
    }
    printf("Hittade %d webbsidor.\n", nr_hits);
    /* Then print them */
    this_pair_p = first_pair_p;
    while (this_pair_p != NULL) {
        if (strcmp(this_pair_p->word, wanted_word) == 0) {
            printf("%s\n", this_pair_p->address);            
        }
        this_pair_p = this_pair_p->next_pair_p;
    }
}

int main(void) {
    struct WordAddressPair *first_pair_p = NULL;
    int nr_pairs = 0;
    char file_name[MAX_FILE_NAME_LENGTH + 1];
    FILE *tsin;
    char word[MAX_WORD_LENGTH + 1];
    char address[MAX_ADDRESS_LENGTH + 1];

    printf("Ange indatafilens namn: ");
    gets(file_name); /* Yes, we know: dangerous! */
    tsin = fopen(file_name, "r");
    if (tsin == NULL) {
        fprintf(stderr, "Kunde inte öppna filen '%s'.\n", file_name);
        exit(EXIT_FAILURE);
    }

    printf("Läser filen...\n");
    while (fscanf(tsin, "%s %s", word, address) == 2) { /* Yes, we know: dangerous! */
        add_pair(&first_pair_p, word, address);
        ++nr_pairs;
    }
    /* With this solution, we don't know the number of unique words. */
    printf("Klar. %d webbadresser.\n", nr_pairs);

    fclose(tsin);

    while (1) {
        printf("Ange ett ord: ");
        gets(word);
        search_and_print_the_hits(first_pair_p, word);
    }

    /* Never reached */
    return EXIT_SUCCESS;
}

Därefter en annan version, som arbetar med en länkad lista av sökord. Listan består av poster av typen struct Word. Varje sökord förekommer bara en gång i listan. I varje sådan ordpost startar sen ytterligare en länkad lista av de webbaddresser där det sökordet finns. Den listan består av poster av typen struct Address. Dessutom lagras ord och addresser inte i fasta strängfält, utan i lagom stora malloc-allokerade utrymmen.

Lösningen är lite mer komplicerad än den första, och den har kvadratisk tidskomplexitet vid inläsningen av filen. Men eftersom den grupperar ihop förekomsterna av samma sökord, vet man hur många unika ord det finns, och man kan skriva ut antalet träffar innan man skriver ut adresserna utan att gå igenom listan två gånger.

Ladda ner: listgoogle-2.c

/* listgoogle-2.c */

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

#define MAX_WORD_LENGTH 100
#define MAX_ADDRESS_LENGTH 1000
#define MAX_FILE_NAME_LENGTH 1000

void *safe_malloc(size_t s) {
    void *result = malloc(s);
    if (result == NULL) {
        fprintf(stderr, "Kunde inte allokera %lu bytes.\n", (unsigned long)s);
        exit(EXIT_FAILURE);
    }
    return result;
}

struct Address {
    char *address;
    struct Address *next_address_p;
};

struct Word {
    char *word;
    int nr_addresses;
    struct Address *first_address_p;
    struct Word *next_word_p;
};

/* A function for working with the lists of web addresses */

void add_address(struct Word *this_word_p, char address[]) {
    struct Address *new_address_p = malloc(sizeof(struct Address));
    new_address_p->address = safe_malloc(strlen(address) + 1);
    strcpy(new_address_p->address, address);
    new_address_p->next_address_p = this_word_p->first_address_p;
    this_word_p->first_address_p = new_address_p;
    ++this_word_p->nr_addresses;
}

/* Some functions for working with the list of search words */

struct Word *find_word(struct Word *first_word_p, char wanted_word[]) {
    struct Word *this_word_p = first_word_p;
    while (this_word_p != NULL) {
        if (strcmp(this_word_p->word, wanted_word) == 0)
            return this_word_p;
        this_word_p = this_word_p->next_word_p;
    }
    return NULL;
}

struct Word *add_word(struct Word **first_word_pp, char word[]) {
    struct Word *new_word_p = malloc(sizeof(struct Word));
    new_word_p->word = safe_malloc(strlen(word) + 1);
    strcpy(new_word_p->word, word);
    new_word_p->nr_addresses = 0;
    new_word_p->first_address_p = NULL;
    new_word_p->next_word_p = *first_word_pp;
    *first_word_pp = new_word_p;
    return new_word_p;
}

void show_word(struct Word *this_word_p) {
    if (this_word_p == NULL) {
        printf("Hittade 0 webbsidor.\n");
    }
    else {
        struct Address *this_address_p;
        printf("Hittade %d webbsidor.\n", this_word_p->nr_addresses);
        this_address_p = this_word_p->first_address_p;
        while (this_address_p != NULL) {
            printf("%s\n", this_address_p->address);
            this_address_p = this_address_p->next_address_p;
        }
    }
}

int main(void) {
    struct Word *first_word_p = NULL;
    int nr_words = 0;
    int nr_addresses = 0;
    char file_name[MAX_FILE_NAME_LENGTH + 1];
    FILE *tsin;
    char word[MAX_WORD_LENGTH + 1];
    char address[MAX_ADDRESS_LENGTH + 1];

    printf("Ange indatafilens namn: ");
    gets(file_name); /* Yes, we know: dangerous! */
    tsin = fopen(file_name, "r");
    if (tsin == NULL) {
        fprintf(stderr, "Kunde inte öppna filen '%s'.\n", file_name);
        exit(EXIT_FAILURE);
    }

    printf("Läser filen...\n");
    while (fscanf(tsin, "%s %s", word, address) == 2) { /* Yes, we know: dangerous! */
        struct Word *this_word_p;
        ++nr_addresses;
        this_word_p = find_word(first_word_p, word);
        if (this_word_p == NULL) {
            ++nr_words;
            this_word_p = add_word(&first_word_p, word);
        }
        add_address(this_word_p, address);
    }
    printf("Klar. %d unika sökord. %d webbadresser.\n", nr_words, nr_addresses);

    fclose(tsin);

    while (1) {
        struct Word *this_word_p;
        printf("Ange ett ord: ");
        gets(word);
        this_word_p = find_word(first_word_p, word);
        show_word(this_word_p);
    }

    /* Never reached */
    return EXIT_SUCCESS;
}

2. Uppgift för betyget 4 respektive VG

Den här lösningen liknar listgoogle-2.c ovan, men i stället för en länkad lista av sökord använder vi en hashtabell. Inläsningen av filen har nu linjär tidskomplexitet. Eftersom vi grupperar ihop förekomsterna av samma sökord, vet vi också hur många unika ord det finns, och man kan skriva ut antalet träffar innan man skriver ut adresserna, utan att leta två gånger.

Ladda ner: hashgoogle.c

/* hashgoogle.c */

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

#define MAX_WORD_LENGTH 100
#define MAX_ADDRESS_LENGTH 1000
#define MAX_FILE_NAME_LENGTH 1000
#define HASH_TABLE_SIZE 1000003

void *safe_malloc(size_t s) {
    void *result = malloc(s);
    if (result == NULL) {
        fprintf(stderr, "Kunde inte allokera %lu bytes.\n", (unsigned long)s);
        exit(EXIT_FAILURE);
    }
    return result;
}

struct Address {
    char *address;
    struct Address *next_address_p;
};

struct Word {
    char *word;
    int nr_addresses;
    struct Address *first_address_p;
    struct Word *next_word_p;
};

/* A function for working with the lists of web addresses */

void add_address(struct Word *this_word_p, char address[]) {
    struct Address *new_address_p = malloc(sizeof(struct Address));
    new_address_p->address = safe_malloc(strlen(address) + 1);
    strcpy(new_address_p->address, address);
    new_address_p->next_address_p = this_word_p->first_address_p;
    this_word_p->first_address_p = new_address_p;
    ++this_word_p->nr_addresses;
}

/* Some functions for working with the hash table of search words */

unsigned long int hash_string(char *s) {
    unsigned long int result = 5381;
    int n = strlen(s);
    for (int i = 0; i < n; ++i)
        result = result * 33 + (unsigned char)s[i];
    return result % HASH_TABLE_SIZE;
}

struct Word *find_word(struct Word *hash_table[], char wanted_word[]) {
    unsigned int bucket = hash_string(wanted_word);
    struct Word *this_word_p = hash_table[bucket];
    while (this_word_p != NULL) {
        if (strcmp(this_word_p->word, wanted_word) == 0)
            return this_word_p;
        this_word_p = this_word_p->next_word_p;
    }
    return NULL;
}

struct Word *add_word(struct Word *hash_table[], char word[]) {
    unsigned int bucket = hash_string(word);
    struct Word *new_word_p = malloc(sizeof(struct Word));
    new_word_p->word = safe_malloc(strlen(word) + 1);
    strcpy(new_word_p->word, word);
    new_word_p->nr_addresses = 0;
    new_word_p->first_address_p = NULL;
    new_word_p->next_word_p = hash_table[bucket];
    hash_table[bucket] = new_word_p;
    return new_word_p;
}

void show_word(struct Word *this_word_p) {
    if (this_word_p == NULL) {
        printf("Hittade 0 webbsidor.\n");
    }
    else {
        struct Address *this_address_p;
        printf("Hittade %d webbsidor.\n", this_word_p->nr_addresses);
        this_address_p = this_word_p->first_address_p;
        while (this_address_p != NULL) {
            printf("%s\n", this_address_p->address);
            this_address_p = this_address_p->next_address_p;
        }
    }
}

/* Outside main, which may be necessary for big variables. Also, automatically initialized to all NULL. */
struct Word *hash_table[HASH_TABLE_SIZE];

int main(void) {
    int nr_words = 0;
    int nr_addresses = 0;
    char file_name[MAX_FILE_NAME_LENGTH + 1];
    FILE *tsin;
    char word[MAX_WORD_LENGTH + 1];
    char address[MAX_ADDRESS_LENGTH + 1];

    printf("Ange indatafilens namn: ");
    gets(file_name); /* Yes, we know: dangerous! */
    tsin = fopen(file_name, "r");
    if (tsin == NULL) {
        fprintf(stderr, "Kunde inte öppna filen '%s'.\n", file_name);
        exit(EXIT_FAILURE);
    }

    printf("Läser filen...\n");
    while (fscanf(tsin, "%s %s", word, address) == 2) { /* Yes, we know: dangerous! */
        struct Word *this_word_p;
        ++nr_addresses;
        this_word_p = find_word(hash_table, word);
        if (this_word_p == NULL) {
            ++nr_words;
            this_word_p = add_word(hash_table, word);
        }
        add_address(this_word_p, address);
    }
    printf("Klar. %d unika sökord. %d webbadresser.\n", nr_words, nr_addresses);

    fclose(tsin);

    while (1) {
        struct Word *this_word_p;
        printf("Ange ett ord: ");
        gets(word);
        this_word_p = find_word(hash_table, word);
        show_word(this_word_p);
    }

    /* Never reached */
    return EXIT_SUCCESS;
}

3. Uppgift för betyget 5

Ingen lösning än.

Thomas Padron-McCarthy (thomas.padron-mccarthy@oru.se), 10 december 2011