Programexempel från Progmet-föreläsning 6, onsdag 16 september 2009 =================================================================== 1. Inlämningsuppgift 1 ------------------- Addition i flera positioner med decimala siffror Addition i flera positioner med binära siffror Bit Bitstr Omvandla Digsim 2. Mer om tidskomplexitet: programkod! -------------------------------------- Exempel (rep): Tiden det tar att måla en ballong: O(n^2) Tiden det tar att blåsa upp ballongen: O(n^3) En ballong med diametern 1 dm tar 1 minut att måla och 1 minut att blåsa upp En ballong med diametern 2 dm tar 4 minuter att måla och 8 minuter att blåsa upp En ballong med diametern 10 dm tar 100 minuter att måla och 1000 minuter att blåsa upp Men det behöver inte vara exakt Tid(n)=n^2. Exempel: Tiden det tar att måla en ballong: Tid(n) = 2.17 n^2 + 3 = O(n^2) Tiden det tar att blåsa upp ballongen: O(n^3) = 0.19 * n^3 + 1.4 * n^2 + 26 = O(n^3) Tiden det tar att gå förbi ballongen: Tid(n) = n/2 = O(n) Tiden det tar att titta på ballongen: Tid(n) = 7 = O(1) Några exempel med programkod: Summera talen i en array med längden n: O(n) int a[N]; int summan = 0; for (int i = 0; i < N; ++i) summan += a[i]; Summera talen i en länkad lista med längden n: O(n) struct link* this_link = first_link; int summan = 0; while (this_link != NULL) { summan += this_link->talet; this_link = this_link->next; } Summera talen i en nxn-matris: O(n^2) int m[N][N]; int summan = 0; for (int x = 0; x < N; ++x) for (int y = 0; y < N; ++y) summan += m[x][y]; Räkna antalet förekomster av bokstaven 'A' i en sträng med längden N: O(n) eller O(n^2) ? char* s = ...... int antal = 0; for (int i = 0; i < strlen(s); ++i) if (s[i] == 'A') ++antal; char* s = ...... int antal = 0; int i = 0; while (i < strlen(s)) { if (s[i] == 'A') ++antal; ++i; } 3. Repetition: LIFO = stack, FIFO = kö -------------------------------------- Stack: Lägg till nya element överst Plocka bort element överst "last in, first out" Kö: Lägg till nya element sist Plocka bort element först "first in, first out" Implementation: fast array, malloc-allokerad array, länkad lista... 4. Vanlig länkad lista ---------------------- struct link { double data; struct link *next; }; struct plink { Person data; struct link *next; }; 5. Generell modul med hjälp av typedef-tricket (tidigare: funktion med array) ----------------------------------------------------------------------------- typedef double datatyp; /* Exempelvis */ struct link { datatyp data; struct link *next; }; 6. 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 7. 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; } 8. 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; } 9. 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 10. 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; } 11. eko.c --------- /* eko.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; } 12. Långsamt? Långsammare? -------------------------- Uppmätta tider med en rad av olika längd: 1000 tecken: 0 sekunder (dvs ej mätbart) 10000 tecken: 0.42 sekunder Om 10k tecken tar 0.42 sekunder, borde väl 20k tecken ta dubbelt så lång tid, dvs ungefär 0.84 sekunder, och 100k tecken borde ta 10 gånger så lång tid, dvs ungefär 4.2 sekunder? Men: 20000 tecken: 2.80 sekunder 100000 tecken: 1 minut 53.30 sekunder Varför? Varje tecken vi hittar stoppas in sist i FIFO-listan. Men då måste man gå igenom hela listan för att hitta slutet! Om vi ska stoppa in N tecken: N instoppningar, som var och en går igenom en lista som är i genomsnitt N/2 steg lång, Totalt: N*N/2 steg = N^2 / 2 1000 tecken = 1 miljon steg (vi struntar i faktorn 1/2) 10000 tecken = 100 miljoner steg x tecken = tiden y (ex: 1 sekund) 2x tecken = tiden 4y (ex: 4 sekunder) 10x tecken = tiden 100y (ex: 100 sekunder) Alltså: O(N^2) 13. fifo-2.c ------------ Ha en pekare till sista elementet i listan också! Men jobbigt att ha två olika pekare till listan, som man måste skicka till alla funktioner! Lösning: Huvud! 14. En ny fifo.h (queue.h) -------------------------- /* queue.h -- specifikation av en kö */ #ifndef QUEUE_H #define QUEUE_H typedef char datatyp; /* Exempelvis */ struct QueueLink { datatyp data; struct link *next; }; typedef struct QueueLink QueueLink; // Behövs i C, men inte i C++ struct QueueHead { QueueLink* first; QueueLink* last; }; typedef struct QueueHead QueueHead; /* Initierar kön, så den är tom */ void queue_init(QueueHead* qhp); /* Är kön tom? */ int queue_empty(QueueHead* qhp); /* Stoppar in datat d sist i kön */ void queue_in(QueueHead* qhp, datatyp d); /* Tar bort (och returnerar) första elementet från kön */ datatyp queue_get(QueueHead* qhp); #endif 15. eko.c --------- /* eko.c */ #include #include "queue.h" int main(void) { QueueHead ko; queue_init(&ko); printf("Ge en textrad: "); int tecken = getchar(); while ((tecken = getchar()) != '\n') { queue_in(&ko, tecken); } printf("Raden: "); while (!queue_empty(&ko)) { int c = queue_get(&ko); putchar(c); } putchar('\n'); return 0; }