Programexempel från Progmet-föreläsning 7, torsdag 4 oktober 2012
=================================================================

Planering för idag. Först rest från förra föreläsningen:

1. En generisk lista i C++ - typ 3, med en mall ("template")
2. Standard-listan från standardbiblioteket i C++: std::list
3. Vad som ingår i kursen för godkänt

Nytt:

4. Iteratorer
5. Funktionspekare
6. Lästips om funktionspekare, C++-klasser, templates

Om vi hinner:

7. Två abstrakta datatyper: Stackar och köer
       Kö: FIFO (First In, First Out)
       Stack: LIFO (Last In, First Out)
8. Olika implementationer av stack och kö
9. En stack "direkt i programmet"
10. En stack som en abstrakt datatyp: "StackOfDoubles"
11. En annan implementation av samma abstrakta "StackOfDoubles"
12. En generisk stack ur standardbiblioteket i C++: std::stack
13. En kö "direkt i programmet"
14. En generisk kö ur standardbiblioteket i C++: std::queue
15. Lästips om stackar och köer
16. Lästips om komplexitetsteori



4. Iteratorer
=============

Varför?
-------

Jämför array:

    double a[10];

    for (int i = 0; i < 10; ++i) {
        printf("%f\n", a[i]);
    }

Länkad lista "inifrån":

    struct Link *this = first;

    while (this != NULL) {
        printf("%f\n", this->talet);
        this = this->next;
    }

Länkad lista "utifrån":

    ListOfDoubles *listan = LOD_create();

    for (int i = 0; i < 10; ++i) {
        printf("%f\n", LOD_get(listan, i);
    }



baklanges-med-iterator.cpp
--------------------------

// baklanges-med-iterator.c -- använder ListOfDoubles

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

int main(void) {
    ListOfDoubles *talen = LOD_create();

    FILE *tsin = fopen("reella-tal.txt", "r");
    double talet;
    while (fscanf(tsin, "%lf", &talet) != EOF) {
        LOD_insert_first(talen, talet);
    }
    fclose(tsin);

    FILE *tsut = fopen("ny-fil.txt", "w");

    LOD_iterator *current = LOD_begin(talen);
    LOD_iterator *end = LOD_end(talen);
    while (current != end) {
        talet = LOD_data(current);
        current = LOD_next(current);
        fprintf(tsut, "%f\n", talet);
    }
    fclose(tsut);

    LOD_destroy(talen);

    return 0;
}



ListOfDoubles.h -- versionen med iteratorer
---------------

// ListOfDoubles.h

#ifndef LISTOFDOUBLES_H
#define LISTOFDOUBLES_H

struct LOD_link {
    double data;
    struct LOD_link *previous;
    struct LOD_link *next;
};

struct ListOfDoubles {
    struct LOD_link *sentinel;
    int length; // Cached for performance
};

typedef struct LOD_link LOD_link;
typedef struct ListOfDoubles ListOfDoubles;

extern ListOfDoubles *LOD_create(void);
extern void LOD_destroy(ListOfDoubles *this_list);
extern int LOD_length(ListOfDoubles *this_list);

extern double LOD_get(ListOfDoubles *this_list, int position);
extern double LOD_get_first(ListOfDoubles *this_list);
extern double LOD_get_last(ListOfDoubles *this_list);

extern int LOD_find(ListOfDoubles *this_list, double wanted);

extern void LOD_insert(ListOfDoubles *this_list, double new_data, int position);
extern void LOD_insert_first(ListOfDoubles *this_list, double new_data);
extern void LOD_insert_last(ListOfDoubles *this_list, double new_data);

extern void LOD_remove(ListOfDoubles *this_list, int position);
extern void LOD_remove_first(ListOfDoubles *this_list);
extern void LOD_remove_last(ListOfDoubles *this_list);

typedef struct LOD_link LOD_iterator;

extern LOD_iterator *LOD_begin(ListOfDoubles *this_list);
extern LOD_iterator *LOD_end(ListOfDoubles *this_list);
extern LOD_iterator *LOD_next(LOD_iterator *this_iterator);
extern LOD_iterator *LOD_previous(LOD_iterator *this_iterator);

extern double LOD_data(LOD_iterator *this_iterator);

#endif
// #ifndef LISTOFDOUBLES_H



ListOfDoubles.cpp -- versionen med iteratorer
-----------------

// ListOfDoubles.cpp

#include <stdlib.h>
#include <stdio.h>
#include "ListOfDoubles.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;
}

ListOfDoubles *LOD_create(void) {
    ListOfDoubles *this_list = (ListOfDoubles *) safe_malloc(sizeof(ListOfDoubles));
    LOD_link *sentinel = (LOD_link *) safe_malloc(sizeof(LOD_link));
    sentinel->data = -4711.4711; // Should never be used, but may give debugging hints if it shows up
    sentinel->previous = sentinel;
    sentinel->next = sentinel;
    this_list->sentinel = sentinel;
    this_list->length = 0;
    return this_list;
}

void LOD_destroy(ListOfDoubles *this_list) {
    LOD_link *sentinel = this_list->sentinel;
    LOD_link *current_link = sentinel->next;
    while (current_link != sentinel) {
        LOD_link *doomed_link = current_link;
        current_link = current_link->next;
        free(doomed_link);
    }
    free(sentinel);
    free(this_list);
}

extern int LOD_length(ListOfDoubles *this_list) {
    return this_list->length;
}

double LOD_get(ListOfDoubles *this_list, int position) {
    int length = LOD_length(this_list);
    if (position < 0 || position >= length) {
        fprintf(stderr, "ListOfDoubles: Couldn't get from position %d in a list of length %d.\n", position, length);
        exit(EXIT_FAILURE);
    }
    LOD_link *sentinel = this_list->sentinel;
    LOD_link *current_link = sentinel->next;
    for (int i = 0; i < position; ++i) {
        current_link = current_link->next;
    }
    return current_link->data;
}

extern double LOD_get_first(ListOfDoubles *this_list) {
    return LOD_get(this_list, 0);
}

extern double LOD_get_last(ListOfDoubles *this_list) {
    return LOD_get(this_list, LOD_length(this_list) - 1);
}

int LOD_find(ListOfDoubles *this_list, double wanted) {
    LOD_link *sentinel = this_list->sentinel;
    LOD_link *current_link = sentinel->next;
    int position = 0;
    while (current_link != sentinel) {
        if (current_link->data == wanted)
            return position;
        ++position;
        current_link = current_link->next;
    }
    return -1;
}

void LOD_insert(ListOfDoubles *this_list, double new_data, int position) {
    int length = LOD_length(this_list);
    if (position < 0 || position > length) {
        fprintf(stderr, "ListOfDoubles: Couldn't insert at position %d in a list of length %d.\n", position, length);
        exit(EXIT_FAILURE);
    }
    LOD_link *sentinel = this_list->sentinel;
    LOD_link *current_link = sentinel;; // Points to the sentinel now, not to the first actual link
    for (int i = 0; i < position; ++i) {
        current_link = current_link->next;
    }

    // We should insert the new link AFTER the "current_link" link

    LOD_link *new_link = (LOD_link *) safe_malloc(sizeof(LOD_link));
    new_link->data = new_data;
    new_link->previous = current_link;
    new_link->next = current_link->next;
    current_link->next->previous = new_link;
    current_link->next = new_link;

    this_list->length++;
}

void LOD_insert_first(ListOfDoubles *this_list, double new_data) {
    LOD_insert(this_list, new_data, 0);
}

void LOD_insert_last(ListOfDoubles *this_list, double new_data) {
    LOD_insert(this_list, new_data, LOD_length(this_list));
}

void LOD_remove(ListOfDoubles *this_list, int position) {
    int length = LOD_length(this_list);
    if (position < 0 || position >= length) {
        fprintf(stderr, "ListOfDoubles: Couldn't remove position %d in a list of length %d.\n", position, length);
        exit(EXIT_FAILURE);
    }
    LOD_link *sentinel = this_list->sentinel;
    LOD_link *current_link = sentinel->next; // Points to the first actual link now!
    for (int i = 0; i < position; ++i) {
        current_link = current_link->next;
    }

    LOD_link *doomed_link = current_link;
    current_link->previous->next = current_link->next;
    current_link->next->previous = current_link->previous;

    free(doomed_link);

    this_list->length--;
}

void LOD_remove_first(ListOfDoubles *this_list) {
    LOD_remove(this_list, 0);
}

void LOD_remove_last(ListOfDoubles *this_list) {
    LOD_remove(this_list, LOD_length(this_list) - 1);
}

LOD_iterator *LOD_begin(ListOfDoubles *this_list) {
    return this_list->sentinel->next;
}

LOD_iterator *LOD_end(ListOfDoubles *this_list) {
    return this_list->sentinel;
}

LOD_iterator *LOD_next(LOD_iterator *this_iterator) {
    return this_iterator->next;
}

LOD_iterator *LOD_previous(LOD_iterator *this_iterator)  {
    return this_iterator->previous;
}

double LOD_data(LOD_iterator *this_iterator) {
    return this_iterator->data;
}



Iteratorer i std::list
----------------------

// baklanges.cpp -- använder std::list

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

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

    FILE *tsin = fopen("reella-tal.txt", "r");
    double talet;
    while (fscanf(tsin, "%lf", &talet) != EOF) {
        talen.push_front(talet);
    }
    fclose(tsin);
    
    FILE *tsut = fopen("ny-fil.txt", "w");
    std::list<double>::iterator current = talen.begin();
    std::list<double>::iterator end = talen.end();
    while (current != end) {
        talet = *current;
        current++;
        fprintf(tsut, "%f\n", talet);
    }
    fclose(tsut);

    return 0;
}



5. Funktionspekare
==================



enkel-fp.cpp
------------

// enkel-fp.cpp

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

int addera(int x, int y) {
    return x + y;
}

int subtrahera(int x, int y) {
    return x - y;
}

int main(void) {
    int a, b;
    printf("Ge ett heltal: ");
    scanf("%d", &a);
    printf("Ge ett heltal till: ");
    scanf("%d", &b);

    int (*p)(int, int);
    
    printf("Plus eller minus (1 = plus, 2 = minus)? ");
    int vilken_operator;
    scanf("%d", &vilken_operator);

    if (vilken_operator == 1)
        p = addera;
    else
        p = subtrahera;

    int resultat = p(a, b);

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

    return 0;
}



sortera.cpp
-----------

// sortera.cpp -- använder qsort

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

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



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



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



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



9. 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;
}



10. 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;
}



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



12. 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;
}



13. 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;
}



14. 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;
}



15. 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ö



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