Programexempel från Progmet-föreläsning 7, måndag 21 september 2009 =================================================================== 1. Från förra gången: stack (lifo.h, lifo.c, charlifo.c) -------------------------------------------------------- Tidskomplexitet på push och pop? Tidskomplexitet på hela programmet, med många push och pop? 2. 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 3. 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; } 4. 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; } 5. Nu: en kö (fifo.h, fifo.c, charfifo.c) ----------------------------------------- Tidskomplexitet på infifo och utfifo? Tidskomplexitet på hela programmet, med många infifo och utfifo? 6. 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 7. 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; } 8. 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; } 9. 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! 10. 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 11. 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; } 12. Använd en färdig länkad lista -- twolist -------------------------------------------- En dubbellänkad lista med huvud-post och två pekare (Gunnar Jokis lösning, från kompendiet och zip-filen.) 13. twolist.h ------------- /* Specifikation av tvåvägslista -- twolist.h */ #ifndef TWOLISTH #define TWOLISTH typedef int datatyp; /* Exempelvis */ typedef struct twolink { enum {head, link} kind; struct twolink *befo, *next; datatyp data; } headtyp, linktyp; void newhead(headtyp **hpp); /* Skapar en ny tom lista */ void newlink(linktyp **lpp); /* Skapar en ny tom länk */ void putlink(datatyp d, linktyp *lp); /* Sätter in data i en länk */ datatyp getlink(linktyp *lp); /* Returnerar data från länk */ void inlast(linktyp *lp, headtyp *hp); /* Sätter in länken sist i listan */ void infirst(linktyp *lp, headtyp *hp); /* Sätter in länken först i listan */ void inpred(linktyp *lp, linktyp *ep); /* Sätter in första länken före den andra */ void insucc(linktyp *lp, linktyp *ep); /* Sätter in första länken efter den andra */ void insort(linktyp *lp, headtyp *hp, int (*is_less)(datatyp d1, datatyp d2)); /* Sätter in länken sorterad enligt is_less */ linktyp *firstlink(headtyp *hp); /* Returnerar pekare till första länken i listan */ linktyp *lastlink(headtyp *hp); /* Returnerar pekare till sista länken i listan */ linktyp *predlink(linktyp *lp); /* Returnerar pekare till länken före */ linktyp *succlink(linktyp *lp); /* Returnerar pekare till länken efter */ int is_link(linktyp *lp); /* Returnerar 1 om länk annars 0 */ int empty(headtyp *hp); /* Returnerar 1 om listan tom annars 0 */ int nrlinks(headtyp *hp); /* Returnerar antalet länkar i listan */ void outlist(linktyp *lp); /* Tar bort länken från listan */ void elimlink(linktyp **lpp); /* Tar bort, avallokerar och NULL-ställer länken */ void clearhead(headtyp *hp); /* Tar bort alla länkar från listan */ void elimhead(headtyp **hpp); /* Eliminerar och NULL-ställer listan */ #endif 14. twolist.c ------------- /* Implementation av tvåvägslistrutiner -- twolist.c */ #include "twolist.h" #include void newhead(headtyp **hpp) /* Skapar en ny tom lista */ { *hpp = malloc(sizeof(headtyp)); (*hpp)->kind = head; (*hpp)->befo = (*hpp)->next = *hpp; } void newlink(linktyp **lpp) /* Skapar en ny tom länk */ { *lpp = malloc(sizeof(linktyp)); (*lpp)->kind = link; (*lpp)->befo = (*lpp)->next = NULL; } void putlink(datatyp d, linktyp *lp) /* Sätter in data i en länk */ { if (lp != NULL) lp->data = d; } datatyp getlink(linktyp *lp) /* Returnerar data från en länk */ { datatyp d; if (lp != NULL) d = lp->data; return d; } void inlast(linktyp *lp, headtyp *hp) /* Sätter in länk sist i lista */ { hp->befo->next = lp; lp->befo = hp->befo; hp->befo = lp; lp->next = hp; } void infirst(linktyp *lp, headtyp *hp) /* Sätter in länk först i lista */ { hp->next->befo = lp; lp->next = hp->next; hp->next = lp; lp->befo = hp; } void inpred(linktyp *lp, linktyp *ep) /* Sätter in första länken före den andra */ { ep->befo->next = lp; lp->befo = ep->befo; ep->befo = lp; lp->next = ep; } void insucc(linktyp *lp, linktyp *ep) /* Sätter in första länken efter den andra */ { ep->next->befo = lp; lp->next = ep->next; ep->next = lp; lp->befo = ep; } void insort(linktyp *lp, headtyp *hp, int (*is_less)(datatyp d1, datatyp d2)) /* Sätter in länken sorterad enligt is_less */ { 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); } linktyp *firstlink(headtyp *hp) /* Returnerar pekare till första länken i listan */ { linktyp *ep; if ( !empty(hp) ) ep = hp->next; else ep = NULL; return ep; } linktyp *lastlink(headtyp *hp) /* Returnerar pekare till sista länken i listan */ { linktyp *ep; if ( !empty(hp) ) ep = hp->befo; else ep = NULL; return ep; } linktyp *predlink(linktyp *lp) /* Returnerar pekare till länken före */ { linktyp *ep; if ( is_link(lp->befo) ) ep = lp->befo; else ep = NULL; return ep; } linktyp *succlink(linktyp *lp) /* Returnerar pekare till länken efter */ { linktyp *ep; if ( is_link(lp->next) ) ep = lp->next; else ep = NULL; return ep; } int is_link(linktyp *lp) /* Returnerar 1 om länk annars 0 */ { return (lp->kind == link); } int empty(headtyp *hp) /* Returnerar 1 om listan tom annars 0 */ { return ( hp->next->kind == head ); } int nrlinks(headtyp *hp) /* Returnerar antalet länkar i listan */ { int sum = 0; linktyp *ep; ep = firstlink(hp); while ( ep != NULL ) { sum++; ep = succlink(ep); } return sum; } void outlist(linktyp *lp) /* Tar bort länken från listan */ { if (lp->befo != NULL && lp->next !=NULL) { lp->befo->next = lp->next; lp->next->befo = lp->befo; lp->befo = NULL; lp->next = NULL; } } void elimlink(linktyp **lpp) /* Tar bort, avallokerar och NULL-ställer länken */ { outlist(*lpp); free(*lpp); *lpp = NULL; } void clearhead(headtyp *hp) /* Eliminerar alla länkar från listan */ { linktyp *ep; while ( !empty(hp) ) { ep = firstlink(hp); elimlink(&ep); } } void elimhead(headtyp **hpp) /* Eliminerar och NULL-ställer listan */ { clearhead(*hpp); free(*hpp); *hpp = NULL; } 15. 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; } 16. 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.) 17. SAOP - Short Array Of Pointers ---------------------------------- struct saop_header saop; saop_init(&saop); char c1, c2, c3, c4; char *p1 = &c1, *p2 = &c2, *p3 = &c3, *p4 = &c4; saop_init(&saop); saop_append(&saop, p1); CHECK( saop_length(&saop) == 1 ); CHECK( saop_get(&saop, 0) == p1 ); CHECK( saop_findfirst(&saop, p1) == 0 ); CHECK( saop_findfirst(&saop, p2) == -1 ); saop_insert(&saop, p4, 0); saop_remove(&saop, 0); saop_cleanup(&saop); 18. saop.h ---------- /* saop.h -- the API for the Short Array of Pointers * A dynamic array of pointers, * perhaps suited for up to a few hundred elements. * (Millions if you only append and delete at the end.) * Uses the "safe_malloc" package and "assert.h". * Will assert-fail for any detected illegal use. */ #ifndef SAOP_H #define SAOP_H #include struct saop_header { int used_length; int allocated_length; void** elements; }; /* Some invariants: * hp->used_length <= hp->allocated_length * (hp->allocated_length == 0) == (hp->elements == NULL) */ extern void saop_init(struct saop_header* hp); extern void saop_cleanup(struct saop_header* hp); /* extern int saop_length(struct saop_header* hp); */ #define saop_length(hp) ((hp)->used_length) extern void saop_append(struct saop_header* hp, void* new_element); extern void saop_insert(struct saop_header* hp, void* new_element, int position); extern void* saop_get(struct saop_header* hp, int position); extern void saop_remove(struct saop_header* hp, int position); extern int saop_findfirst(struct saop_header* hp, void* element); #endif 19. saop.c ---------- /* saop.c -- the implementation of the Short Array of Pointers */ #include #include #include #include #include "safe_malloc.h" #include "saop.h" /*----------------------------------------------------------------------------*/ #define MIN_ARRAY_SIZE 4 #define ARRAY_FACTOR 4 #define BIG_ARRAY_SIZE 16 /*----------------------------------------------------------------------------*/ static void expand(struct saop_header* hp) { assert(hp != NULL); assert(hp->used_length <= hp->allocated_length); assert((hp->allocated_length == 0) == (hp->elements == NULL)); assert(hp->used_length == hp->allocated_length); if (hp->allocated_length == 0) hp->allocated_length = MIN_ARRAY_SIZE; else hp->allocated_length *= ARRAY_FACTOR; hp->elements = safe_realloc(hp->elements, hp->allocated_length * sizeof(void*)); } /* expand */ /*----------------------------------------------------------------------------*/ static void maybe_shrink(struct saop_header* hp) { assert(hp != NULL); assert(hp->used_length <= hp->allocated_length); assert((hp->allocated_length == 0) == (hp->elements == NULL)); // If the allocated array is both big and very empty, shrink it if (hp->allocated_length >= BIG_ARRAY_SIZE && hp->allocated_length >= 8 * hp->used_length) { int newsize = MIN_ARRAY_SIZE; while (newsize < hp->used_length) newsize *= ARRAY_FACTOR; if (newsize < hp->allocated_length) { // Probably always, but just to be sure hp->allocated_length = newsize; hp->elements = safe_realloc(hp->elements, hp->allocated_length * sizeof(void*)); } } } /* maybe_shrink */ /*----------------------------------------------------------------------------*/ void saop_init(struct saop_header* hp) { assert(hp != NULL); hp->used_length = 0; hp->allocated_length = 0; hp->elements = NULL; } /*----------------------------------------------------------------------------*/ void saop_cleanup(struct saop_header* hp) { assert(hp != NULL); assert(hp->used_length <= hp->allocated_length); assert((hp->allocated_length == 0) == (hp->elements == NULL)); safe_free(hp->elements); hp->elements = NULL; hp->allocated_length = 0; hp->used_length = 0; } /* saop_cleanup */ /*----------------------------------------------------------------------------*/ void saop_append(struct saop_header* hp, void* new_element) { assert(hp != NULL); assert(hp->used_length <= hp->allocated_length); assert((hp->allocated_length == 0) == (hp->elements == NULL)); if (hp->used_length == hp->allocated_length) expand(hp); hp->elements[hp->used_length++] = new_element; } /* saop_append */ /*----------------------------------------------------------------------------*/ void saop_insert(struct saop_header* hp, void* new_element, int position) { assert(hp != NULL); assert(hp->used_length <= hp->allocated_length); assert((hp->allocated_length == 0) == (hp->elements == NULL)); assert(position >= 0); assert(position <= hp->used_length); /* Yes: "<=", not "<" */ if (hp->used_length == hp->allocated_length) expand(hp); if (position < hp->used_length) { /* Not the new last element */ memmove(&hp->elements[position + 1], &hp->elements[position], (hp->used_length - position) * sizeof(void*)); } hp->used_length++; hp->elements[position] = new_element; } /* saop_insert */ /*----------------------------------------------------------------------------*/ void* saop_get(struct saop_header* hp, int position) { assert(hp != NULL); assert(hp->used_length <= hp->allocated_length); assert((hp->allocated_length == 0) == (hp->elements == NULL)); assert(position >= 0); assert(position < hp->used_length); return hp->elements[position]; } /* saop_get */ /*----------------------------------------------------------------------------*/ void saop_remove(struct saop_header* hp, int position) { assert(hp != NULL); assert(hp->used_length <= hp->allocated_length); assert((hp->allocated_length == 0) == (hp->elements == NULL)); assert(position < hp->used_length); if (position < hp->used_length - 1) { /* Not the last element */ memmove(&hp->elements[position], &hp->elements[position + 1], (hp->used_length - position - 1) * sizeof(void*)); } hp->used_length--; maybe_shrink(hp); } /* saop_remove */ /*----------------------------------------------------------------------------*/ int saop_findfirst(struct saop_header* hp, void* element) { assert(hp != NULL); assert(hp->used_length <= hp->allocated_length); assert((hp->allocated_length == 0) == (hp->elements == NULL)); int n = hp->used_length; void** p = hp->elements; for (int i = 0; i < n; ++i) if (p[i] == element) return i; return -1; } /* saop_findfirst */