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



baklanges-7.cpp (länkar in nya tal SIST i listan)
---------------

// baklanges-7.cpp -- men är "baklanges" ett bra namn?

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

struct talpost {
    double talet;
    struct talpost* next;
};

int main(void) {
    struct talpost* first = NULL;
    struct talpost* last = NULL;

    FILE *tsin = fopen("reella-tal.txt", "r");
    double talet;
    while (fscanf(tsin, "%lf", &talet) != EOF) {
        struct talpost* newp;
        newp = (struct talpost*)malloc(sizeof(struct talpost));
        newp->talet = talet;
        newp->next = NULL;
        if (first == NULL)
            first = last = newp;
        else {
            last->next = newp;
            last = newp;
        }
    }
    fclose(tsin);
    FILE *tsut = fopen("ny-fil.txt", "w");
    struct talpost* thisp = first;
    while (thisp != NULL) {
        fprintf(tsut, "%f\n", thisp->talet);
        thisp = thisp->next;
    }
    fclose(tsut);

    thisp = first;
    while (thisp != NULL) {
        struct talpost* doomed = thisp;
        thisp = thisp->next;
        free(doomed);
    }

    return 0;
}



Stackar och köer
----------------

Stack: LIFO (Last In, First Out)
Kö: FIFO (First In, First Out)
Datorer: GIGO...



skapa-tal.c
-----------

// skapa-tal.c

#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <errno.h>
#include <string.h>

void usage(void) {
    fprintf(stderr, "Skriv: skapa-reella-tal  ANTAL  MIN  MAX  FILNAMN\n");
    exit(EXIT_FAILURE);
}

int main(int argc, char *argv[]) {
    if (argc != 5)
        usage();
    unsigned long antal; // En vanlig int är ofta bara 32 bitar, även på 64-bitarssystem
    if (sscanf(argv[1], "%lu", &antal) != 1)
        usage();
    double min;
    if (sscanf(argv[2], "%lf", &min) != 1)
        usage();
    double max;
    if (sscanf(argv[3], "%lf", &max) != 1)
        usage();
    FILE *filen = fopen(argv[4], "w");
    if (filen == NULL) {
        fprintf(stderr, "Det gick inte att skriva filen '%s'.\n", argv[4]);
        fprintf(stderr, "Möjlig felorsak: %s (felkod %d).\n", strerror(errno), errno);
        exit(EXIT_FAILURE);
    }
    srand((unsigned int)time(NULL));
    for (unsigned long i = 0; i < antal; ++i)
        fprintf(filen, "%f\n", min + (max - min) * rand() / RAND_MAX);
    fclose(filen);

    return 0;
}



baklanges-7b.cpp (med 1000 extra traverseringar av listan)
----------------

// baklanges-7.cpp -- men är "baklanges" ett bra namn?

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

struct talpost {
    double talet;
    struct talpost* next;
};

int main(void) {
    struct talpost* first = NULL;
    struct talpost* last = NULL;

    FILE *tsin = fopen("reella-tal.txt", "r");
    double talet;
    while (fscanf(tsin, "%lf", &talet) != EOF) {
        struct talpost* newp;
        newp = (struct talpost*)malloc(sizeof(struct talpost));
        newp->talet = talet;
        newp->next = NULL;
        if (first == NULL)
            first = last = newp;
        else {
            last->next = newp;
            last = newp;
        }
    }
    fclose(tsin);
    FILE *tsut = fopen("ny-fil.txt", "w");
    struct talpost* thisp = first;
    while (thisp != NULL) {
        fprintf(tsut, "%f\n", thisp->talet);
        thisp = thisp->next;
    }
    fclose(tsut);

    for (int i = 0; i < 1000; ++i) {
        thisp = first;
        while (thisp != NULL) {
            thisp = thisp->next;
        }
    }

    thisp = first;
    while (thisp != NULL) {
        struct talpost* doomed = thisp;
        thisp = thisp->next;
        free(doomed);
    }

    return 0;
}



baklanges-7c.cpp (letar rätt på sista elementet varje gång det behövs)
----------------

// baklanges-7.cpp -- men är "baklanges" ett bra namn?

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

struct talpost {
    double talet;
    struct talpost* next;
};

int main(void) {
    struct talpost* first = NULL;
    // struct talpost* last = NULL; -- Nej, inte den här gången.

    FILE *tsin = fopen("reella-tal.txt", "r");
    double talet;
    while (fscanf(tsin, "%lf", &talet) != EOF) {
        struct talpost* newp;
        newp = (struct talpost*)malloc(sizeof(struct talpost));
        newp->talet = talet;
        newp->next = NULL;
        if (first == NULL)
            first = newp;
        else {
            // Börja med att hitta sista elementet i listan
            struct talpost* p = first;
            while (p->next != NULL)
                p = p->next;
            struct talpost* last = p;
            last->next = newp;
            last = newp;
        }
    }
    fclose(tsin);
    FILE *tsut = fopen("ny-fil.txt", "w");
    struct talpost* thisp = first;
    while (thisp != NULL) {
        fprintf(tsut, "%f\n", thisp->talet);
        thisp = thisp->next;
    }
    fclose(tsut);

    thisp = first;
    while (thisp != NULL) {
        struct talpost* doomed = thisp;
        thisp = thisp->next;
        free(doomed);
    }

    return 0;
}



Tidskomplexitet
---------------

Vi pratade om tidskomplexitet.

Hundkojan är 1x1x1 meter,
lagerlokalen är 10x10x10 meter,
VAB är 100x100x100 meter.

N är sidan (1, 10 eller 100 meter).

Att plantera blommor runt väggen är O(N).
Att måla golvet är O(N^2).
Att fylla huset med pingisbollar är O(N^3).

Tid(N) = 1.02 N = O(N)
Tid(N) = 1000000 N = O(N)
Tid(N) = 1.02 N + 17 = O(N)

Tid(N) = 0.000000000001 N^2 + 3 = O(N^2)
Tid(N) = 1000000 N + 17 = O(N)

Traveling salesman-problemet, fullständig sökning: O(N!)



*** RESTEN HANN VI INTE MED. IGNORERA.



namn.c (hann vi inte med på fö 4 2009 heller...)
------

// namn.c

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

int main(void) {
    char* namn;
    int langd;

    printf("Ange längden på namnet (avsluta med 0): ");
    scanf("%d", &langd);
    /* Och kolla om scanf gick bra... */
    while (getchar() != '\n')
        ;

    while (langd > 0) {
        namn = malloc(langd + 1 + 1); /* \n och \0 */
        /* Och kolla om malloc gick bra... */
        
        printf("Ange namnet: ");
        /* Undvik: gets(namn); */
        fgets(namn, langd + 1 + 1, stdin);
        namn[strlen(namn) - 1] = '\0';
        /* Men, om man ska vara noga... */

        for (int i = 0; i < langd; ++i) {
            if (namn[i] == ' ')
                putchar('\n');
            else
                putchar(namn[i]);
        }
        putchar('\n');

        free(namn);

        printf("Ange längden på namnet (avsluta med 0): ");
        scanf("%d", &langd);
        while (getchar() != '\n')
            ;
    }

    return 0;
}



Inlämningsuppgift 1
-------------------

Addition i flera positioner med decimala siffror
Addition i flera positioner med binära siffror

Bit
Bitstr
Omvandla
Digsim



lifo.h
------

/* lifo.h -- specifikation av LIFO-lista (stack) */

#ifndef LIFO_H
#define LIFO_H

typedef double datatyp; /* Exempelvis */

struct link {
    datatyp data;
    struct link *next;
};

typedef struct link linktyp;

void push(linktyp **lpp, datatyp d);
/* Stoppar in d i LIFO-listan */

datatyp pop(linktyp **lpp);
/* Tar bort data från LIFO-listan */

#endif



lifo.c
------

/* lifo.c -- implementation av LIFO-lista (stack) */

#include <stdlib.h>
#include "lifo.h"

void push(linktyp **lpp, datatyp d) {
    linktyp *tp;

    tp = malloc(sizeof(linktyp));
    tp->data = d;
    tp->next = *lpp;
    *lpp = tp;
}

datatyp pop(linktyp **lpp) {
    linktyp *tp;
    datatyp d;

    tp = *lpp;
    d = tp->data;
    *lpp = tp->next;
    free(tp);
    return d;
}



charlifo.c
----------

/* charlifo.c */

#include <stdio.h>
#include "lifo.h"

int main(void) {
    linktyp* teckenstacken = NULL;
    char tecken;

    printf("Ge en textrad: ");
    tecken = getchar();
    while (tecken != '\n') {
        push(&teckenstacken, tecken);
        tecken = getchar();     
    }
    while (teckenstacken != NULL) {
        putchar(pop(&teckenstacken));
    }
    putchar('\n');
    return 0;
}



fifo.h
------

/* fifo.h -- specifikation av FIFO-lista (kö) */

#ifndef FIFO_H
#define FIFO_H

typedef double datatyp; /* Exempelvis */

struct link
{
  datatyp data;
  struct link *next;
};

typedef struct link linktyp;

void infifo(linktyp **lpp, datatyp d);
/* Stoppar in d i FIFO-listan */

datatyp utfifo(linktyp **lpp);
/* Tar bort data från FIFO-listan */

#endif



fifo-1.c
--------

/* fifo.c -- en implementation av FIFO-lista (kö) */

#include <stdlib.h>
#include "fifo.h"

void infifo(linktyp **lpp, datatyp d) {
    linktyp *tp;

    if ( *lpp == NULL ) {
        /* Första länken */
        *lpp = malloc(sizeof(linktyp));
        (*lpp)->data = d;
        (*lpp)->next = NULL;
    }
    else {
        /* Flytta fram tp att peka på sista länken */
        tp = *lpp;
        while (tp->next != NULL)
            tp = tp->next;

        /* Stoppa in d efter sista länken i listan */
        tp->next = malloc(sizeof(linktyp));
        tp->next->data = d;
        tp->next->next = NULL;
    }
}

datatyp utfifo(linktyp **lpp) {
    linktyp *tp;
    datatyp d;

    tp = *lpp;
    d = tp->data;
    *lpp = tp->next;
    free(tp);
    return d;
}



charfifo.c
----------

/* charfifo.c */

#include <stdio.h>
#include "fifo.h"

int main(void) {
    linktyp* ko = NULL;
    char tecken;

    printf("Ge en textrad: ");
    tecken = getchar();
    while (tecken != '\n') {
        infifo(&ko, tecken);
        tecken = getchar();     
    }
    while (ko != NULL) {
        putchar(utfifo(&ko));
    }
    putchar('\n');
    return 0;
}



fifo-2.c
--------

Korta och medellånga rader går snabbt i fifo-1,
men långa rader går mycket långsamt. Varför?

Hur gör man den snabbare?

Tidskomplexitet:
Tiden det tar att måla väggarna i ett rum är O(n).
Tiden det tar att måla golvet i ett rum är O(n^2).

Toaletten är 1x1 meter: väggarna tar 1 timme att måla, golvet tar 1 timme.
Badrummet är 2x2 meter: väggarna tar 2 timmar att måla, golvet tar 4 timmar.
Klassrummet är 10x10 meter: väggarna tar 10 timmar att måla, golvet tar 100 timmar.
Fabriken är 100x100 meter: väggarna tar 100 timmar att måla, golvet tar 10000 timmar.