Programexempel från Progmet-föreläsning 5, måndag 14 september 2008 =================================================================== 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 #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 #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 #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 #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.