Programexempel från Progmet-föreläsning 8, tisdag 9 oktober 2012
================================================================

1. Lite mer om funktionspekare
2. Lästips om funktionspekare, C++-klasser, templates
3. Två abstrakta datatyper: Stackar och köer
       Kö: FIFO (First In, First Out)
       Stack: LIFO (Last In, First Out)
4. Olika implementationer av stack och kö
5. En stack "direkt i programmet"
6. En stack som en abstrakt datatyp: "StackOfDoubles"
7. En annan implementation av samma abstrakta "StackOfDoubles"
8. En generisk stack ur standardbiblioteket i C++: std::stack
9. En kö "direkt i programmet"
10. En generisk kö ur standardbiblioteket i C++: std::queue
11. Lästips om stackar och köer
12. Lästips om komplexitetsteori

Resten är om vi hinner, men blir nog på nästa föreläsning!

1. Rekursion
2. Olika datastrukturer för sökning
3. Sökning i en (vanlig fast) array
4. Sökning i en dynamisk array
5. Sökning i en länkad lista
6. Binärsökning i en sorterad array
7. Binärsökning i en länkad lista?
8. Binärt träd
9. Träd av högre ordning ("ordning N" = N grenar under varje nod)
10. Hashtabeller (kallas "söktabeller" i kompendiet)
11. Läs mer



1. Lite mer om funktionspekare
==============================

int jfr_tal(const void* p1, const void* p2) {
    return *(double*)p1 - *(double*)p2;
}

int main(void) {
    printf("Ge (högst 10) rella tal. Avsluta med ett negativt.\n");
    double talen[10];
    int antal = 0;
    double talet;
    printf("Ge ett tal: ");
    scanf("%lf", &talet);
    while (talet >= 0) {
        talen[antal++] = talet;
        printf("Ge ett tal: ");
        scanf("%lf", &talet);
    }
    qsort(talen, antal, sizeof(double), jfr_tal);
    printf("Talen sorterade:");
    for (int i = 0; i < antal; ++i)
        printf(" %.2f", talen[i]);
    printf("\n");
    return 0;
}



2. Lästips om funktionspekare, C++-klasser, templates
=====================================================

Bilting-boken ("Vägen till C, 2:a uppl"):
  Om qsort avsnitt 10.7.5 (s 247)
  Om Funktionspekare: avsnitt 7.11 (s 184-186)

Weiss-boken ("Data Structures and Algorithm Analysis in C++, 3d Ed"):
  Om C++-klasser avsnitt 1.4 t o m 1.4.3 (s 11-17)
  Om Templates avsnitt 1.6 (s 29-32)



3. Två abstrakta datatyper: Stackar och köer
============================================

Kö: FIFO (First In, First Out)
Prioritetskö: sorterad i prioritetsordning
Stack: LIFO (Last In, First Out)
FILO? LILO?
Datorer: GIGO...



4. Olika implementationer av stack och kö
=========================================

"Stack" och "kö" är abstrakta datatyper.
De är inte länkade listor, arrayer, filer eller något annat.
Men de kan implementeras ("förverkligas") med hjälp av
länkade listor, arrayer, filer eller något annat.



5. En stack "direkt i programmet"
=================================



pushpop-1.cpp
-------------

// pushpop-1.cpp -- push och pop på en stack

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

#define STACK_MAX_SIZE 100

double stack[STACK_MAX_SIZE];
int stack_size = 0;

int main(void) {
    while (1) {
        printf("Push (1) eller pop (2)? ");
        int operation;
        scanf("%d", &operation);
        if (operation == 1) {
            printf("Vilket tal? ");
            double the_number;
            scanf("%lf", &the_number);
            stack[stack_size++] = the_number;
        }
        else {
            double the_number = stack[--stack_size];
            printf("Poppat tal: %f\n", the_number);
        }
        printf("Antal element på stacken nu: %d\n", stack_size);
    }

    return 0;
}



pushpop-2.cpp
-------------

// pushpop-2.cpp -- push och pop på en stack, med mer felkontroll

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

#define STACK_MAX_SIZE 100

double stack[STACK_MAX_SIZE];
int stack_size = 0;

int main(void) {
    while (1) {
        printf("Push (1) eller pop (2)? ");
        int operation;
        scanf("%d", &operation);
        if (operation == 1) {
            if (stack_size == STACK_MAX_SIZE) {
                printf("Stacken är redan full!\n");
            }
            else {
                printf("Vilket tal? ");
                double the_number;
                scanf("%lf", &the_number);
                stack[stack_size++] = the_number;
            }
        }
        else if (operation == 2) {
            if (stack_size == 0) {
                printf("Stacken är redan tom!\n");
            }
            else {
                double the_number = stack[--stack_size];
                printf("Poppat tal: %f\n", the_number);
            }
        }
        else {
            printf("Fel val!\n");
        }
        printf("Antal element på stacken nu: %d\n", stack_size);
    }

    return 0;
}



6. En stack som en abstrakt datatyp: "StackOfDoubles"
=====================================================



StackOfDoubles.h
----------------

// StackOfDoubles.h

#ifndef STACKOFDOUBLES_H
#define STACKOFDOUBLES_H

#define STACKOFDOUBLES_MAX_SIZE 100

struct StackOfDoubles {
    double data[STACKOFDOUBLES_MAX_SIZE];
    int size;
};

extern StackOfDoubles *SOD_create(void);
extern void SOD_destroy(StackOfDoubles *this_stack);
extern int SOD_size(StackOfDoubles *this_stack);

extern void SOD_push(StackOfDoubles *this_stack, double new_data);
extern double SOD_pop(StackOfDoubles *this_stack);
extern double SOD_peek(StackOfDoubles *this_stack);
extern double SOD_is_empty(StackOfDoubles *this_stack);

#endif
// #ifndef STACKOFDOUBLES_H



StackOfDoubles.cpp
------------------

// StackOfDoubles.cpp

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

static void *safe_malloc(size_t s) {
    void *result = malloc(s);
    if (result == NULL) {
        fprintf(stderr, "StackOfDoubles: Memory full. Couldn't allocate %lu bytes.\n", (unsigned long)s);
        exit(EXIT_FAILURE);
    }
    return result;
}

StackOfDoubles *SOD_create(void) {
    StackOfDoubles *this_stack = (StackOfDoubles *) safe_malloc(sizeof(StackOfDoubles));
    this_stack->size = 0;
    return this_stack;
}

void SOD_destroy(StackOfDoubles *this_stack) {
    free(this_stack);
}

extern int SOD_size(StackOfDoubles *this_stack) {
    return this_stack->size;
}

void SOD_push(StackOfDoubles *this_stack, double new_data) {
    if (this_stack->size == STACKOFDOUBLES_MAX_SIZE) {
        fprintf(stderr, "StackOfDoubles: Stack is full (%d elements).\n", STACKOFDOUBLES_MAX_SIZE);
        exit(EXIT_FAILURE);
    }
    this_stack->data[this_stack->size++] = new_data;
}

double SOD_pop(StackOfDoubles *this_stack) {
    if (this_stack->size == 0) {
        fprintf(stderr, "StackOfDoubles: Stack is empty.\n");
        exit(EXIT_FAILURE);
    }
    return this_stack->data[--this_stack->size];
}

double SOD_peek(StackOfDoubles *this_stack) {
    if (this_stack->size == 0) {
        fprintf(stderr, "StackOfDoubles: Stack is empty.\n");
        exit(EXIT_FAILURE);
    }
    return this_stack->data[this_stack->size - 1];
}

extern double SOD_is_empty(StackOfDoubles *this_stack) {
    return this_stack->size == 0;
}



pushpop-3.cpp
-------------

// pushpop-3.cpp -- push och pop på en stack

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

int main(void) {
    StackOfDoubles *stack = SOD_create();

    while (1) {
        printf("Push (1) eller pop (2)? ");
        int operation;
        scanf("%d", &operation);
        if (operation == 1) {
            printf("Vilket tal? ");
            double the_number;
            scanf("%lf", &the_number);
            SOD_push(stack, the_number);
        }
        else if (operation == 2) {
            double the_number = SOD_pop(stack);
            printf("Poppat tal: %f\n", the_number);
        }
        else {
            printf("Fel val!\n");
        }
        printf("Antal element på stacken nu: %d\n", SOD_size(stack));
    }

    SOD_destroy(stack);

    return 0;
}



7. En annan implementation av samma abstrakta "StackOfDoubles"
==============================================================



StackOfDoubles.h
----------------

// StackOfDoubles.h

#ifndef STACKOFDOUBLES_H
#define STACKOFDOUBLES_H

#include "ListOfDoubles.h"

struct StackOfDoubles {
    ListOfDoubles* the_list;
};

extern StackOfDoubles *SOD_create(void);
extern void SOD_destroy(StackOfDoubles *this_stack);
extern int SOD_size(StackOfDoubles *this_stack);

extern void SOD_push(StackOfDoubles *this_stack, double new_data);
extern double SOD_pop(StackOfDoubles *this_stack);
extern double SOD_peek(StackOfDoubles *this_stack);
extern double SOD_is_empty(StackOfDoubles *this_stack);

#endif
// #ifndef STACKOFDOUBLES_H



// StackOfDoubles.cpp
---------------------

#include <stdlib.h>
#include <stdio.h>
#include "ListOfDoubles.h"
#include "StackOfDoubles.h"

static void *safe_malloc(size_t s) {
    void *result = malloc(s);
    if (result == NULL) {
        fprintf(stderr, "ListOfDoubles: Memory full. Couldn't allocate %lu bytes.\n", (unsigned long)s);
        exit(EXIT_FAILURE);
    }
    return result;
}

StackOfDoubles *SOD_create(void) {
    StackOfDoubles *this_stack = (StackOfDoubles *) safe_malloc(sizeof(StackOfDoubles));
    this_stack->the_list = LOD_create();
    return this_stack;
}

void SOD_destroy(StackOfDoubles *this_stack) {
    LOD_destroy(this_stack->the_list);
    free(this_stack);
}

extern int SOD_size(StackOfDoubles *this_stack) {
    return LOD_length(this_stack->the_list);
}

void SOD_push(StackOfDoubles *this_stack, double new_data) {
    LOD_insert_first(this_stack->the_list, new_data);
}

double SOD_pop(StackOfDoubles *this_stack) {
    if (LOD_length(this_stack->the_list) == 0) {
        fprintf(stderr, "StackOfDoubles: Stack is empty.\n");
        exit(EXIT_FAILURE);
    }
    double result = LOD_get_first(this_stack->the_list);
    LOD_remove_first(this_stack->the_list);
    return result;
}

double SOD_peek(StackOfDoubles *this_stack) {
    if (LOD_length(this_stack->the_list) == 0) {
        fprintf(stderr, "StackOfDoubles: Stack is empty.\n");
        exit(EXIT_FAILURE);
    }
    return LOD_get_first(this_stack->the_list);
}

extern double SOD_is_empty(StackOfDoubles *this_stack) {
    return LOD_length(this_stack->the_list) == 0;
}



8. En generisk stack ur standardbiblioteket i C++: std::stack
=============================================================



pushpop-4.cpp
-------------

// pushpop-4.cpp -- push och pop på en stack, med std::stack

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

int main(void) {
    std::stack<double> stack;

    while (1) {
        printf("Push (1) eller pop (2)? ");
        int operation;
        scanf("%d", &operation);
        if (operation == 1) {
            printf("Vilket tal? ");
            double the_number;
            scanf("%lf", &the_number);
            stack.push(the_number);
        }
        else if (operation == 2) {
            double the_number = stack.top();
            stack.pop();
            printf("Poppat tal: %f\n", the_number);
        }
        else {
            printf("Fel val!\n");
        }
        printf("Antal element på stacken nu: %d\n", (int)stack.size());
    }

    return 0;
}



9. En kö "direkt i programmet"
==============================



putget-1.cpp
------------

// putget-1.cpp -- put och get på en kö

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

#define QUEUE_MAX_LENGTH 100

double queue[QUEUE_MAX_LENGTH];
int queue_length = 0;

int main(void) {
    while (1) {
        printf("Put (1) eller get (2)? ");
        int operation;
        scanf("%d", &operation);
        if (operation == 1) {
            printf("Vilket tal? ");
            double the_number;
            scanf("%lf", &the_number);
            queue[queue_length++] = the_number;
        }
        else {
            double the_number = queue[0];
            for (int i = 1; i < queue_length; ++i)
                queue[i - 1] = queue[i];
            --queue_length;
            printf("Talet som stod först i kön: %f\n", the_number);
        }
        printf("Antal element i kön nu: %d\n", queue_length);
    }

    return 0;
}



10. En generisk kö ur standardbiblioteket i C++: std::queue
===========================================================



putget-2.cpp
------------

// putget-2.cpp -- put och get på en kö, med std::queue

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

int main(void) {
    std::queue<double> queue;

    while (1) {
        printf("Put (1) eller get (2)? ");
        int operation;
        scanf("%d", &operation);
        if (operation == 1) {
            printf("Vilket tal? ");
            double the_number;
            scanf("%lf", &the_number);
            queue.push(the_number);
        }
        else if (operation == 2) {
            double the_number = queue.front();
            queue.pop();
            printf("Talet som stod först i kön: %f\n", the_number);
        }
        else {
            printf("Fel val!\n");
        }
        printf("Antal element i kön nu: %d\n", (int)queue.size());
    }

    return 0;
}



11. Lästips om stackar och köer
===============================

Gunnar Jokis kompendium (på kursens hemsida): avsnitt 3.1 (s 41-49)

(Men missförstå inte kapitel 3: Stackar och köer är INTE en sorts länkade istor!
De är inte heller arrayer, filer eller något annat.
De är abstrakta datatyper, som kan implementeras ("förverkligas") med hjälp av
länkade listor, arrayer, filer eller något annat.)

Bilting, "Vägen till C", 2000:
s 158-160 om en implementation av en stack
s 297 om programstacken (där funktionsanrop lagras)
s 288 om ett bättre sätt att implementera en kö som en array

Weiss, "Data Structures and Algorithm Analysis in C++", 3d Ed, 2006:
avsnitt 3.6 om stackar
avsnitt 3.7 om köer

Janlert et al, "Datatyper och algoritmer", 2000:
kapitel 7 om den abstrakta datatypen stack
kapitel 8 om den abstrakta datatypen kö



12. Lästips om komplexitetsteori
================================

Vi lär oss det där med data: Grunderna om komplexitet
(http://basen.oru.se/kurser/progmet/2010-2011-p1/texter/thomas/komplexitet/index.html)

Janlert et al, "Datatyper och algoritmer", 2000: s 36-37 och kapitel 12, särskilt avsnitt 12.2

Weiss, "Data Structures and Algorithm Analysis in C++", 3d Ed, 2006: kapitel 2, särskilt avsnitt 12.1



Resten är om vi hinner, men blir nog på nästa föreläsning!



1. Rekursion
============

1a: Rekursion
-------------

Behövs innan vi jobbar vidare med sökning i sorterade arrayer, träd mm.



1b: rekursion.c
---------------

#include <stdio.h>

void rekfunk(int a) {
    printf("%d\n", a);
    if (a < 3)
        rekfunk(a+1); /* Rekursivt anrop! */
    printf("%d\n", a);
}

int main() {
    rekfunk(1);
    return 0;
}



1c: 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;
}



1d: Körexempel
---------------

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



2. 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)



3. Sökning i en (vanlig fast) array
===================================

O(n)

    #define MAX_ANTAL 417
    double a[MAX_ANTAL];
    int antal;
    double sokt;
    // Fyll arrayen "a", sätt "antal", ta reda på "sokt"
    for (int i; i < antal; ++i) {
        if (a[i] == sokt) {
            // Hittade det!
            // ....
            // Och avsluta loopen!
        }
    }



4. Sökning i en dynamisk array
==============================

Sökdelen är precis samma, så fortfarande O(n)

    double* a;
    int antal;
    double sokt;
    // Allokera arrayen "a", fyll den, sätt "antal", ta reda på "sokt"
    for (int i; i < antal; ++i) {
        if (a[i] == sokt) {
            // Hittade det!
            // ....
            // Och avsluta loopen!
        }
    



5. Sökning i en länkad lista
============================

O(n) precis som i en array



6. Binärsökning i en sorterad array
===================================

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



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



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



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

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



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" = 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)
====================================================



11. 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