Programexempel från Progmet-föreläsning 6, onsdag 24 september 2008 =================================================================== 1. Repetition: LIFO = stack --------------------------- Lägg till nya element överst Plocka bort element överst "last in, first out" 2. Generell modul med hjälp av typedef-tricket ---------------------------------------------- typedef double datatyp; /* Exempelvis */ struct link { datatyp data; struct link *next; }; 3. FIFO = kö ------------ Lägg till nya element sist Plocka bort element först "first in, first out" 4. Ett exempel med FIFO: programmet "eko" ----------------------------------------- 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; } 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; } 5. 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) 6. fifo-2.c ----------- Ha en pekare till sista elementet i listan också! 7. Tidskomplexitet ------------------ Tiden det tar att måla golvlisterna i ett rum: O(n) Tiden det tar att måla golvet i rummet: O(n^2) Exempel: Toaletten är 1x1 meter: golvlisterna tar 1 timme att måla, golvet tar 1 timme. Badrummet är 2x2 meter: golvlisterna tar 2 timmar att måla, golvet tar 4 timmar. Klassrummet är 10x10 meter: golvlisterna tar 10 timmar att måla, golvet tar 100 timmar. Fabriken är 100x100 meter: golvlisterna tar 100 timmar att måla, golvet tar 10000 timmar. Tiden det tar att måla en ballong: O(n^2) Tiden det tar att blåsa upp ballongen: O(n^3) Exempel: 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 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; } 8. Dubbellänkad lista med huvud-post och två pekare --------------------------------------------------- (Gunnar Jokis lösning, från kompendiet och zip-filen.) twolist.h --------- /* Specifikation av tvåvägslista -- twolist.h */ #ifndef TWOLIST_H #define TWOLIST_H typedef int datatyp; /* Exempelvis */ typedef struct twolink { enum {head, link} kind; struct twolink *befo, *next; datatyp data; } headtyp, linktyp; /* Skapar en ny tom lista */ void newhead(headtyp **hpp); /* Skapar en ny tom länk */ void newlink(linktyp **lpp); /* Sätter in data i en länk */ void putlink(datatyp d, linktyp *lp); /* Returnerar data från länk */ datatyp getlink(linktyp *lp); /* Sätter in länken sist i listan */ void inlast(linktyp *lp, headtyp *hp); /* Sätter in länken först i listan */ void infirst(linktyp *lp, headtyp *hp); /* Sätter in första länken före den andra */ void inpred(linktyp *lp, linktyp *ep); /* Sätter in första länken efter den andra */ void insucc(linktyp *lp, linktyp *ep); /* Sätter in länken sorterad enligt is_less */ void insort(linktyp *lp, headtyp *hp, int (*is_less)(datatyp d1, datatyp d2)); /* Returnerar pekare till första länken i listan */ linktyp *firstlink(headtyp *hp); /* Returnerar pekare till sista länken i listan */ linktyp *lastlink(headtyp *hp); /* Returnerar pekare till länken före */ linktyp *predlink(linktyp *lp); /* Returnerar pekare till länken efter */ linktyp *succlink(linktyp *lp); /* Returnerar 1 om länk annars 0 */ int is_link(linktyp *lp); /* Returnerar 1 om listan tom annars 0 */ int empty(headtyp *hp); /* Returnerar antalet länkar i listan */ int nrlinks(headtyp *hp); /* Tar bort länken från listan */ void outlist(linktyp *lp); /* Tar bort, avallokerar och NULL-ställer länken */ void elimlink(linktyp **lpp); /* Tar bort alla länkar från listan */ void clearhead(headtyp *hp); /* Eliminerar och NULL-ställer listan */ void elimhead(headtyp **hpp); #endif twolist.c --------- /* Implementation av tvåvägslistrutiner -- twolist.c */ #include #include "twolist.h" /* Skapar en ny tom lista */ void newhead(headtyp **hpp) { *hpp = malloc(sizeof(headtyp)); (*hpp)->kind = head; (*hpp)->befo = (*hpp)->next = *hpp; } /* Skapar en ny tom länk */ void newlink(linktyp **lpp) { *lpp = malloc(sizeof(linktyp)); (*lpp)->kind = link; (*lpp)->befo = (*lpp)->next = NULL; } /* Sätter in data i en länk */ void putlink(datatyp d, linktyp *lp) { if (lp != NULL) lp->data = d; } /* Returnerar data från en länk */ datatyp getlink(linktyp *lp) { datatyp d; if (lp != NULL) d = lp->data; return d; } /* Sätter in länk sist i lista */ void inlast(linktyp *lp, headtyp *hp) { hp->befo->next = lp; lp->befo = hp->befo; hp->befo = lp; lp->next = hp; } /* Sätter in länk först i lista */ void infirst(linktyp *lp, headtyp *hp) { hp->next->befo = lp; lp->next = hp->next; hp->next = lp; lp->befo = hp; } /* Sätter in första länken före den andra */ void inpred(linktyp *lp, linktyp *ep) { ep->befo->next = lp; lp->befo = ep->befo; ep->befo = lp; lp->next = ep; } /* Sätter in första länken efter den andra */ void insucc(linktyp *lp, linktyp *ep) { ep->next->befo = lp; lp->next = ep->next; ep->next = lp; lp->befo = ep; } /* Sätter in länken sorterad enligt is_less */ void insort(linktyp *lp, headtyp *hp, int (*is_less)(datatyp d1, datatyp d2)) { linktyp *sp, *ep; newlink(&sp); *sp = *lp; infirst(sp, hp); ep = lastlink(hp); while ( is_less(lp->data, ep->data) ) ep = predlink(ep); insucc(lp, ep); elimlink(&sp); } /* Returnerar pekare till första länken i listan */ linktyp *firstlink(headtyp *hp) { linktyp *ep; if ( !empty(hp) ) ep = hp->next; else ep = NULL; return ep; } /* Returnerar pekare till sista länken i listan */ linktyp *lastlink(headtyp *hp) { linktyp *ep; if ( !empty(hp) ) ep = hp->befo; else ep = NULL; return ep; } /* Returnerar pekare till länken före */ linktyp *predlink(linktyp *lp) { linktyp *ep; if ( is_link(lp->befo) ) ep = lp->befo; else ep = NULL; return ep; } /* Returnerar pekare till länken efter */ linktyp *succlink(linktyp *lp) { linktyp *ep; if ( is_link(lp->next) ) ep = lp->next; else ep = NULL; return ep; } /* Returnerar 1 om länk annars 0 */ int is_link(linktyp *lp) { return (lp->kind == link); } /* Returnerar 1 om listan tom annars 0 */ int empty(headtyp *hp) { return ( hp->next->kind == head ); } /* Returnerar antalet länkar i listan */ int nrlinks(headtyp *hp) { int sum = 0; linktyp *ep; ep = firstlink(hp); while ( ep != NULL ) { sum++; ep = succlink(ep); } return sum; } /* Tar bort länken från listan */ void outlist(linktyp *lp) { if (lp->befo != NULL && lp->next !=NULL) { lp->befo->next = lp->next; lp->next->befo = lp->befo; lp->befo = NULL; lp->next = NULL; } } /* Tar bort, avallokerar och NULL-ställer länken */ void elimlink(linktyp **lpp) { outlist(*lpp); free(*lpp); *lpp = NULL; } /* Eliminerar alla länkar från listan */ void clearhead(headtyp *hp) { linktyp *ep; while ( !empty(hp) ) { ep = firstlink(hp); elimlink(&ep); } } /* Eliminerar och NULL-ställer listan */ void elimhead(headtyp **hpp) { clearhead(*hpp); free(*hpp); *hpp = NULL; } eko-2.c ------- /* eko.c */ #include #include "twolist.h" int main(void) { headtyp* listan = NULL; char tecken; newhead(&listan); printf("Ge en textrad: "); tecken = getchar(); while (tecken != '\n') { linktyp* link; newlink(&link); putlink(tecken, link); inlast(link, listan); tecken = getchar(); } while (!empty(listan)) { linktyp* link; link = firstlink(listan); char c = getlink(link); elimlink(&link); putchar(c); } putchar('\n'); return 0; } 9. Snabbare? ------------ 1000 tecken: 0 sekunder (dvs ej mätbart) 10000 tecken: 0 sekunder 20000 tecken: 0 sekunder 100000 tecken: 0 sekunder 1 miljon tecken: 0.33 sekunder 10 miljoner tecken: 3.39 sekunder