Programexempel från Progmet-föreläsning 8, tisdag 28 september 2010
===================================================================

Dagens program (och förmodligen morgondagens):

1. Programkonstruktion
2. Kom ihåg: Abstrakta datatyper
3. Inlämningsuppgift 3
4. Arbetsgång (jfr gunnars föreläsning nr 4, sid 6)
5. Mer om inlämningsuppgift 3
6. Obs! Förtydligande av kompendiet
7. Delvis repetition: Olika datastrukturer för sökning
8. Binärt träd
9. Träd av högre ordning (ordning N = max N grenar under varje nod)
10. Hashtabeller (kallas "söktabeller" i kompendiet)
11. Läs mer



1. Programkonstruktion
======================

En bok av Niklaus Wirth: "Algorithms + Data Structures = Programs"

Olika sätt att tänka ut hur programmet ska se ut:

1a) Programmets algoritmer ("bearbetningen", "programstegen") gör vi med stegvis förfining
    Vi kan rita det med strukturdiagram (inte flödesscheman), eller visa med pseudokod
1b) Eller genom att studera dataflöden
2) Och för programmets data kan vi använda abstrakta datatyper (jämför: ER-diagram, objektorientering)

Exempel: Frukost med kaffe och smörgåsar

Andra exempel:

1a) Stegvis förfining: Mätprogram enligt figuren i kompendiet sid 61
1b) Dataflöden: Valutaprogram enligt figuren i kompendiet sid 70
2) Abstrakta datatyper: Dating-programmet (se nedan)

(Se kompendiet kapitel 4, och hela del 4 av Gunnars föreläsningsanteckningar)



2. Kom ihåg: Abstrakta datatyper
================================

Abstrakt datatyp =
en modul ("avgränsad del", "svart låda") med "en sorts saker" och "operationer" på dessa

Exempel: heltal i C!
Sakerna = själva heltalen, lagras på något sätt
Operationer +, -, %, ==, <, =, ...



3. Inlämningsuppgift 3
======================

Exempel på programkonstruktion med abstrakta datatyper: Dating!

1. Pojkar och flickor med intressen
2. Programmet parar ihop dem enligt intressena

(Inget HBT-perspektiv här inte!)



4. Arbetsgång (jfr gunnars föreläsning nr 4, sid 6)
===================================================

1. Vilka saker ("objekt") ska vi jobba med?
   Ex: Pojkar, flickor, par, intressen

2. För var och en av dessa saker: Vad ska man kunna göra med den?
   Ex: Skapa, visa, jämföra...

3. Hitta beroenden, t ex som ett beroendediagram.

(Det ovanstående är redan klart.)

4. Implementera!
   Börja längst ner i beroendediagrammet ("bottom-up"),
   och testa varje modul för sig!

5. Igen: Testa varje modul för sig. Ni kommer väl ihåg testning?!

6. Integrationstest! Bottom-up! Inte big-bang-testning!



5. Mer om inlämningsuppgift 3
=============================

Saker som finns i programmet, och som blir abstrakta datatyper
(och separatkompilerade moduler):

    * Intressen, och samlingar av intressen: datatypen "Intressetabell"
    * Personer: datatypen "Person"
    * Listor av personer: datatypen "Personlista"
    * Par, som består av en pojke och en flicka: datatypen "Par"
    * Listor av par: datatypen "Parlista"

Listorna implementeras med hjälp av (std::list<Person> och std::list<Par>)

En modul som inte är en abstrakt datatyp:

    * Dating, som är huvudmodulen med main-funktionen 

Dessutom finns modulen "Dating", som är huvudprogrammet.



6. Obs! Förtydligande av kompendiet
===================================

En "modul" och en "abstrakt datatyp" är inte samma sak.

En abstrakt datatyp är en modul,
men inte alla moduler är abstrakta datatyper.

Exempel:

Huvudprogrammet "Dating" är en modul, men inte en abstrakt datatyp.

Stdio-paketet är en modul, men inte en abstrakt datatyp.
(Men man kan se datatypen FILE som en abstrakt datatyp!)



7. Delvis repetition: 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)



8. Binärt träd
==============

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



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



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



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

O(Nlog n) = O(log n)
Samma tidskomplexitet, men FÄRRE noder besöks (pga lägre och buskigare träd)



10. Hashtabeller (kallas "söktabeller" i kompendiet)
====================================================

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



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



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



11. Läs mer
===========

Om Programkonstruktion: Gunnar Jokis kompendium (på kursens hemsida) kapitel 4

"Vi lär oss det där med data: Grunder om lagringsstrukturer" (på hemsidan)

Gunnar Jokis kompendium (på kursens hemsida):
avsnitt 5.1 om träd
avsnitt 5.2 om hashtabeller

Bilting, "Vägen till C", 2000:
rekursion beskrivs på sid 135-136 och används på sid 213
binärsökning nämns på sid 247
avsnitt 8.2.2 om hashtabeller
avsnitt 8.2.3 om binära träd

Janlert et al, "Datatyper och algoritmer", 2000:
kapitel 11 om binära träd
kapitel 14 om binära sökträd
avsnitt 15.3 om hashtabeller

Weiss, "Data Structures and Algorithm Analysis in C++", 3d Ed, 2006:
binärsökning i avsnitt 2.4.4 (sid 58-60)
binära sökträd i kapitel 4
hashtabeller i kapitel 5