Programexempel från Progmet-föreläsning 9, tisdag 27 september 2011
===================================================================

Dagens program:

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. Ett förtydligande av kompendiet

7. Repetition: Olika datastrukturer för sökning
8. Repetition: Binärsökning i en sorterad array
9. Binärsökning i en länkad lista?
10. Binärt träd
11. Träd av högre ordning (ordning N = max N grenar under varje nod)
12. Hashtabeller (kallas "söktabeller" i kompendiet)
13. Läs mer om datastrukturer



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 (std::list<Person> och std::list<Par>)

En modul som inte är en abstrakt datatyp:

    * Dating, som är huvudmodulen med main-funktionen 



6. Ett 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. 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. Repetition: Binärsökning i en sorterad array
===============================================

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



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



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



9. Binärsökning i en länkad lista?
==================================

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



10. Binärt träd
===============

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



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



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



11. Träd av högre ordning ("ordning N" = 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)



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



13. Läs mer
===========

"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