Programexempel från Progmet-föreläsning 9, måndag 28 september 2009
===================================================================



1. Fortsättning: Olika datastrukturer för sökning
-------------------------------------------------

a) Array: O(n)
   Om man hittar det sökta efter i genomsnitt halva arrayen: O(n/2) = fortfarande O(n)

b) Dynamisk array: också O(n)

c) Sökning i en länkad lista: också O(n)

d) Binärsökning i en sorterad array: O(2log n) = O(log n)

e) Binärsökning i en länkad lista?

f) Binärt träd: O(2log n) = O(log n)

g) Träd av högre ordning: O(Nlog n) = O(log n)

h) Hashtabeller (kallas "söktabeller" i kompendiet): O(1)



Förra gången:

Sökning i en (vanlig fast) array: O(n)
Sökning i en dynamisk array: O(n)
O(n) precis som i en array
Inför resten: Rekursion, programmet "rekursion.c"



2a: fakultet.c
--------------

#include <stdio.h>

int fakultet(int a) {
    if (a == 0)
        return 1;
    else
        return a * fakultet(a - 1);
}

int main() {
    printf("fakultet(3) = %d\n", fakultet(3));
    printf("fakultet(10) = %d\n", fakultet(10));
    printf("fakultet(20) = %d\n", fakultet(20));
    return 0;
}



2b: Körexempel
--------------

fakultet(3) = 6
fakultet(10) = 3628800
fakultet(20) = -2102132736



3. Binärsökning i en sorterad array
-----------------------------------

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



3a: bs-1.c
----------

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

/* Rekursiv binärsökning */
int hitta(double a[], int forsta, int sista, double sokt) {
    if (sista < forsta)
        return -1;
    int mitten = (forsta + sista) / 2;
    if (a[mitten] == sokt)
        return mitten;
    else if (sokt < a[mitten])
        return hitta(a, forsta, mitten - 1, sokt);
    else /* if (sokt > a[mitten]) */
        return hitta(a, mitten + 1, sista, sokt);
}

int main(void) {
    double a[] = {
        -8.37, -7.98, -7.31, -6.88, -3.87, -2.29, 2.13, 6.15, 22.50, 38.40,
        41.74, 42.36, 44.85, 50.95, 58.96, 59.72, 61.77, 62.94, 69.99, 71.47,
        71.78, 71.99, 73.35, 73.76, 74.68, 74.75, 75.00, 78.05, 78.95, 80.16
    };
    int antal = sizeof(a) / sizeof(a[0]);
    double sokt = 22.5;

    int resultat = hitta(a, 0, antal - 1, sokt);

    printf("Resultat = %d\n", resultat);

    return 0;
}



3b: bs-2.c
----------

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

/* Iterativ binärsökning */
int hitta_iterativt(double a[], int antal, double sokt) {
    int forsta = 0;
    int sista = antal - 1;

    while (forsta <= sista) {
        int mitten = (forsta + sista) / 2;
        if (a[mitten] == sokt)
            return mitten;
        else if (sokt < a[mitten])
            sista = mitten - 1;     
        else /* if (sokt > a[mitten]) */
            forsta = mitten + 1;
    }
    return -1;
}

int main(void) {
    double a[] = {
        -8.37, -7.98, -7.31, -6.88, -3.87, -2.29, 2.13, 6.15, 22.50, 38.40,
        41.74, 42.36, 44.85, 50.95, 58.96, 59.72, 61.77, 62.94, 69.99, 71.47,
        71.78, 71.99, 73.35, 73.76, 74.68, 74.75, 75.00, 78.05, 78.95, 80.16
    };
    int antal = sizeof(a) / sizeof(a[0]);
    double sokt = 22.5;

    int resultat = hitta_iterativt(a, antal, sokt);

    printf("Resultat = %d\n", resultat);

    return 0;
}



4. Binärsökning i en länkad lista?
----------------------------------

Går inte. Övning: Varför?



5. Binärt träd
--------------

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



5a: bt.c
--------

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

struct TreeNode {
    double data;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct TreeNode* tree_search(struct TreeNode* root, double wanted) {
    if (root == NULL)
        return NULL;
    else if (root->data == wanted)
        return root;
    else if (wanted < root->data)
        return tree_search(root->left, wanted);
    else /* if (wanted > root->data) */
        return tree_search(root->right, wanted);
}

void tree_insert(struct TreeNode** rootp, double newdata) {
    if (*rootp == NULL) {
        struct TreeNode* newnode = malloc(sizeof(struct TreeNode));
        newnode->data = newdata;
        newnode->left = newnode->right = NULL;
        *rootp = newnode;
    }
    else if (newdata < (*rootp)->data)
        tree_insert(&(*rootp)->left, newdata);
    else /* if (newdata > (*rootp)->data) */
        tree_insert(&(*rootp)->right, newdata);
}

int main(void) {
    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]);
    struct TreeNode* root = NULL;

    for (int i = 0; i < antal; ++i)
        tree_insert(&root, a[i]);

    double talet;
    printf("Skriv tal. Avsluta med EOF eller ett ogiltigt tal.\n");
    while (scanf("%lf", &talet) == 1) {
        struct TreeNode* resultat = tree_search(root, talet);
        if (resultat != NULL)
            printf("Hittade det.\n");
        else
            printf("Hittade det inte.\n");
    }

    return 0;
}



5b: 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;
}



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

O(Nlog n) = O(log n)



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

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



7a: 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;
}



7b: 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;
}