Programexempel från Progmet-föreläsning 7, måndag 6 oktober 2008 ================================================================ (Vi får se om vi hinner med allt det här idag.) 1. Nya föreläsningar vecka 43 och 44 ------------------------------------ 2. Kommer ni ihåg eko-programmet som var O(n^2) ----------------------------------------------- FIFO = kö. Implementerad som en länkad lista, där nya element stoppas in sist i listan. Vi måste gå igenom ("traversera") hela listan för att hitta sista elementet. Tidskomplexitet: O(n*n) Enkel lösning: Ha en pekare till sista elementet i listan också! Tidskomplexitet: O(n) 4. 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; } 5. Snabbare? ------------ Detta program borde alltså ha tidskomplexiteten O(n): 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 Verkar stämma med O(n): 10 miljoner tecken är 10 gånger fler än 1 miljon tecken, och tar mycket riktigt 10 gånger längre tid. Jämför med gamla O(n^2): 1000 tecken: 0 sekunder (dvs ej mätbart) 10000 tecken: 0.42 sekunder 20000 tecken: 2.80 sekunder 100000 tecken: 1 minut 53.30 sekunder 1 miljon tecken: 3 timmar 17 minuter 56.05 sekunder Inte (bara) långsammare, utan "ökar snabbare"! Jämför 10k och 100k: 10 gånger fler tecken, men 270 gånger längre tid. Jämför 100k och 1M: 10 gånger fler tecken, men 105 gånger långsammare. (Varför 270 och inte 100? Gissning: overhead i malloc-hanteringen.) 6. Programkonstruktion ---------------------- "Algoritmer + data = program" 1a) Programmets algoritmer ("bearbetningen", "programstegen") gör vi med stegvis förfining. 1b) Eller genom att studera dataflöden 2) Och för programmets data kan vi använda abstrakta datatyper Ex: 1a) Stegvis förfining: Mätprogram enligt figuren i kompendiet sid 61 1b) Dataflöden: Valutaprogram nligt figuren i kompendiet sid 70 2) Abstrakta datatyper: Dating-programmet (se nedan) (Se kompendiet kapitel 4, och hela del 4 av Gunnars föreläsningsanteckningar) 7. Abstrakta datatyoer ---------------------- Abstrakt datatyp = en modul ("avgränsad del", "svart låda") med "en sorts saker" och "operationer" på dessa Exempel: heltal i C! Sakerna = själva heltalen, lagras på något sätt Operationer +, -, %, ==, <, =, ... 8. Inlämningsuppgift 2 ---------------------- Exempel på programkonstruktion med abstrakta datatyper: Dating! 1. Pojkar och flickor med intressen 2. Programmet parar ihop dem enligt intressena (Inget HBT-perspektiv här inte!) 9. Arbetsgång (jfr gunnars föreläsning nr 4, sid 6) --------------------------------------------------- 1. Vilka saker ("objekt") ska vi jobba med? Ex: Pojkar, flickor, par, intressen 2. För var och en av dessa saker: Vad ska man kunna göra med den? Ex: Skapa, visa, jämföra... 3. Hitta beroenden, t ex som ett beroendediagram. 4. Implementera! Börja längst ner i beroendediagrammet ("bottom-up"), och testa varje modul för sig! 10. Mer om inlämningsuppgift 2 ------------------------------ Saker som finns i programmet, och som blir abstrakta datatyper: "Itabbar". En "Itab" är en intressetabell. "Dingar". En "Ding" är antingen en person eller ett par. (Bra design???) "Dlistor". En "Dlist" (eller "Dlista") är en lista av "Dingar". Använder "Twolist", som är vår gamla dubbellänkade lista. Dessutom finns modulen "Dating", som är huvudprogrammet. 11. Obs! Fel i kompendiet ------------------------- En "modul" och en "abstrakt datatyp" är inte samma sak! En abstrakt datatyp är en modul, men inte alla moduler är abstrakta datatyper! Exempel: Huvudprogrammet "Dating" är en modul, men inte en abstrakt datatyp. Stdio-paketet är en modul, men inte en abstrakt datatyp. (Men man kan se datatypen FILE som en abstrakt datatyp!)