Programexempel från Progmet-föreläsning 10, onsdag 15 oktober 2008
==================================================================



1. Fortsättning: Binära träd
----------------------------

O(2log n) = O(log n)



wordcounter.c
-------------

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

#define MAX_WORD_LENGTH 20

struct TreeNode {
    char key[MAX_WORD_LENGTH + 1];
    int count;
    struct TreeNode* left;
    struct TreeNode* right;
};

void tree_insert(struct TreeNode** rootp, char newkey[]) {
    if (*rootp == NULL) {
        struct TreeNode* newnode = malloc(sizeof(struct TreeNode));
        strcpy(newnode->key, newkey);
        newnode->count = 1;
        newnode->left = newnode->right = NULL;
        *rootp = newnode;
    }
    else if (strcmp(newkey, (*rootp)->key) == 0)
        ++(*rootp)->count;
    else if (strcmp(newkey, (*rootp)->key) < 0)
        tree_insert(&(*rootp)->left, newkey);
    else /* if (strcmp(newkey, (*rootp)->key) > 0) */
        tree_insert(&(*rootp)->right, newkey);
}

void print_tree(struct TreeNode* root) {
    if (root != NULL) {
        print_tree(root->left);
        printf("%s: %d\n", root->key, root->count);
        print_tree(root->right);
    }
}

int main(void) {
    struct TreeNode* root = NULL;
    char key[MAX_WORD_LENGTH + 1];

    while (scanf("%20s", key) == 1)
        tree_insert(&root, key);

    print_tree(root);

    return 0;
}



2. Träd av högre ordning (ordning N = N grenar under varje nod)
----------------------------------------------------------------

O(Nlog n) = O(log n)



3. Hashtabeller (kallas "söktabeller" i kompendiet)
----------------------------------------------------

O(1), nästan i alla fall.



hashtabell.c
------------

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

#define HASH_TABLE_SIZE 47

struct HashNode {
    int in_use;
    double data;
    struct HashNode* next_in_bucket;
};

int hashfunktion(double data) {
    return (int)fabs(data) % HASH_TABLE_SIZE;
}

int hash_search(struct HashNode ht[], double wanted) {
    int position = hashfunktion(wanted);
    if (ht[position].data == wanted)
        return 1;
    struct HashNode* p = ht[position].next_in_bucket;
    while (p != NULL) {
        if (p->data == wanted)
            return 1;
        p = p->next_in_bucket;
    }
    return 0;
}

void hash_insert(struct HashNode ht[], double newdata) {
    int position = hashfunktion(newdata);
    if (ht[position].in_use == 0) {
        ht[position].in_use = 1;
        ht[position].data = newdata;
    }
    else {
        struct HashNode* newnode = malloc(sizeof(struct HashNode));
        newnode->data = newdata;
        newnode->next_in_bucket = ht[position].next_in_bucket;
        ht[position].next_in_bucket = newnode;
    }
}

int main(void) {
    struct HashNode ht[HASH_TABLE_SIZE];
    for (int i = 0; i < HASH_TABLE_SIZE; ++i) {
        ht[i].in_use = 0;
        ht[i].next_in_bucket = NULL;
    }
    double a[] = {
        80.16, 38.40, 74.75, 41.74, -3.87, -6.88, 58.96, 44.85, 6.15, 71.78,
        73.76, -8.37, 42.36, 71.99, 61.77, -7.98, 75.00, 22.50, 69.99, 78.05,
        71.47, -7.31, -2.29, 59.72, 62.94, 50.95, 73.35, 74.68, 78.95, 2.13
    };
    int antal = sizeof(a) / sizeof(a[0]);
    for (int i = 0; i < antal; ++i)
        hash_insert(ht, a[i]);

    double talet;
    printf("Skriv tal. Avsluta med EOF eller ett ogiltigt tal.\n");
    while (scanf("%lf", &talet) == 1) {
        int resultat = hash_search(ht, talet);
        if (resultat)
            printf("Hittade det.\n");
        else
            printf("Hittade det inte.\n");
    }

    return 0;
}



hashwordcounter.c
-----------------

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

#define MAX_WORD_LENGTH 20
#define HASH_TABLE_SIZE 47

struct HashNode {
    char key[MAX_WORD_LENGTH + 1];
    int count;
    struct HashNode* next_in_bucket;
};

unsigned int hashfunktion(unsigned char *s) {
    unsigned int resultat = 5381;
    int c;
    while ((c = *s++) != '\0')
        resultat = resultat * 33 + c;
    return resultat % HASH_TABLE_SIZE;
}

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

void hash_insert(struct HashNode* ht[], char* newkey) {
    int position = hashfunktion(newkey);
    struct HashNode* p = ht[position];
    while (p != NULL) {
        if (strcmp(newkey, p->key) == 0) {
            ++p->count;
            return;
        }
        p = p->next_in_bucket;
    }
    struct HashNode* newnode = malloc(sizeof(struct HashNode));
    strcpy(newnode->key, newkey);
    newnode->count = 1;
    newnode->next_in_bucket = ht[position];
    ht[position] = newnode;
}

void print_table(struct HashNode* ht[]) {
    for (int position = 0; position < HASH_TABLE_SIZE; ++position) {
        struct HashNode* p = ht[position];
        while (p != NULL) {
            printf("%s: %d\n", p->key, p->count);
            p = p->next_in_bucket;
        }
    }
}

int main(void) {
    struct HashNode* hashtabellen[HASH_TABLE_SIZE];
    for (int i = 0; i < HASH_TABLE_SIZE; ++i)
        hashtabellen[i] = NULL;
    char key[MAX_WORD_LENGTH + 1];

    while (scanf("%20s", key) == 1)
        hash_insert(hashtabellen, key);

    print_table(hashtabellen);

    return 0;
}