Programexempel från Progmet-föreläsning 8, onsdag 23 oktober 2009 ================================================================= 1. TwoList ---------- Kom ihåg från förra gången: TwoList. Titta på koden själva! 2. 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); 3. 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 4. 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 */ 5. 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) 6. Kom ihåg: Abstrakta datatyper -------------------------------- 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 +, -, %, ==, <, =, ... 7. 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!) 8. 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! 9. 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. 10. 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!) 11. Olika datastrukturer för sökning ------------------------------------ a) Array: O(n) Om man hittar det sökta efter i genomsnitt halva arrayen: O(n/2) = fortfarande O(n) b) Dynamisk array: också O(n) c) Sökning i en länkad lista: också O(n) d) Binärsökning i en sorterad array: O(2log n) = O(log n) e) Binärsökning i en länkad lista? f) Binärt träd: O(2log n) = O(log n) g) Träd av högre ordning: O(Nlog n) = O(log n) h) Hashtabeller (kallas "söktabeller" i kompendiet): O(1) 12. Sökning i en (vanlig fast) array ------------------------------------ O(n) #define MAX_ANTAL 417 double a[MAX_ANTAL]; int antal; double sokt; // Fyll arrayen "a", sätt "antal", ta reda på "sokt" for (int i; i < antal; ++i) { if (a[i] == sokt) { // Hittade det! // .... // Och avsluta loopen! } } 13. Sökning i en dynamisk array ------------------------------- Sökdelen är precis samma, så fortfarande O(n) double* a; int antal; double sokt; // Allokera arrayen "a", fyll den, sätt "antal", ta reda på "sokt" for (int i; i < antal; ++i) { if (a[i] == sokt) { // Hittade det! // .... // Och avsluta loopen! } 14. Sökning i en länkad lista ---------------------------- O(n) precis som i en array 14a: Rekursion ------------- Behövs innan vi jobbar vidare med sökning i sorterade arrayer, träd mm. 14b: rekursion.c --------------- #include void rekfunk(int a) { printf("%d\n", a); if (a < 3) rekfunk(a+1); /* Rekursivt anrop! */ printf("%d\n", a); } int main() { rekfunk(1); return 0; } 14c: fakultet.c --------------- #include int fakultet(int a) { if (a == 0) return 1; else return a * fakultet(a - 1); } int main() { printf("fakultet(3) = %d\n", fakultet(3)); printf("fakultet(10) = %d\n", fakultet(10)); printf("fakultet(20) = %d\n", fakultet(20)); return 0; } 14d: Körexempel --------------- fakultet(3) = 6 fakultet(10) = 3628800 fakultet(20) = -2102132736 15. Binärsökning i en sorterad array ------------------------------------ O(2log n) = O(log n) 15a: bs-1.c ----------- #include #include /* Rekursiv binärsökning */ int hitta(double a[], int forsta, int sista, double sokt) { if (sista < forsta) return -1; int mitten = (forsta + sista) / 2; if (a[mitten] == sokt) return mitten; else if (sokt < a[mitten]) return hitta(a, forsta, mitten - 1, sokt); else /* if (sokt > a[mitten]) */ return hitta(a, mitten + 1, sista, sokt); } int main(void) { double a[] = { -8.37, -7.98, -7.31, -6.88, -3.87, -2.29, 2.13, 6.15, 22.50, 38.40, 41.74, 42.36, 44.85, 50.95, 58.96, 59.72, 61.77, 62.94, 69.99, 71.47, 71.78, 71.99, 73.35, 73.76, 74.68, 74.75, 75.00, 78.05, 78.95, 80.16 }; int antal = sizeof(a) / sizeof(a[0]); double sokt = 22.5; int resultat = hitta(a, 0, antal - 1, sokt); printf("Resultat = %d\n", resultat); return 0; } 15b: bs-2.c ----------- #include #include /* Iterativ binärsökning */ int hitta_iterativt(double a[], int antal, double sokt) { int forsta = 0; int sista = antal - 1; while (forsta <= sista) { int mitten = (forsta + sista) / 2; if (a[mitten] == sokt) return mitten; else if (sokt < a[mitten]) sista = mitten - 1; else /* if (sokt > a[mitten]) */ forsta = mitten + 1; } return -1; } int main(void) { double a[] = { -8.37, -7.98, -7.31, -6.88, -3.87, -2.29, 2.13, 6.15, 22.50, 38.40, 41.74, 42.36, 44.85, 50.95, 58.96, 59.72, 61.77, 62.94, 69.99, 71.47, 71.78, 71.99, 73.35, 73.76, 74.68, 74.75, 75.00, 78.05, 78.95, 80.16 }; int antal = sizeof(a) / sizeof(a[0]); double sokt = 22.5; int resultat = hitta_iterativt(a, antal, sokt); printf("Resultat = %d\n", resultat); return 0; } 16. Binärsökning i en länkad lista? ----------------------------------- Går inte. Övning: Varför? 17. Binärt träd --------------- O(2log n) = O(log n) 17a: bt.c --------- #include #include struct TreeNode { double data; struct TreeNode* left; struct TreeNode* right; }; struct TreeNode* tree_search(struct TreeNode* root, double wanted) { if (root == NULL) return NULL; else if (root->data == wanted) return root; else if (wanted < root->data) return tree_search(root->left, wanted); else /* if (wanted > root->data) */ return tree_search(root->right, wanted); } void tree_insert(struct TreeNode** rootp, double newdata) { if (*rootp == NULL) { struct TreeNode* newnode = malloc(sizeof(struct TreeNode)); newnode->data = newdata; newnode->left = newnode->right = NULL; *rootp = newnode; } else if (newdata < (*rootp)->data) tree_insert(&(*rootp)->left, newdata); else /* if (newdata > (*rootp)->data) */ tree_insert(&(*rootp)->right, newdata); } int main(void) { double a[] = { 80.16, 38.40, 74.75, 41.74, -3.87, -6.88, 58.96, 44.85, 6.15, 71.78, 73.76, -8.37, 42.36, 71.99, 61.77, -7.98, 75.00, 22.50, 69.99, 78.05, 71.47, -7.31, -2.29, 59.72, 62.94, 50.95, 73.35, 74.68, 78.95, 2.13 }; int antal = sizeof(a) / sizeof(a[0]); struct TreeNode* root = NULL; for (int i = 0; i < antal; ++i) tree_insert(&root, a[i]); double talet; printf("Skriv tal. Avsluta med EOF eller ett ogiltigt tal.\n"); while (scanf("%lf", &talet) == 1) { struct TreeNode* resultat = tree_search(root, talet); if (resultat != NULL) printf("Hittade det.\n"); else printf("Hittade det inte.\n"); } return 0; } 17b: wordcounter.c ------------------ #include #include #include #define MAX_WORD_LENGTH 20 struct TreeNode { char key[MAX_WORD_LENGTH + 1]; int count; struct TreeNode* left; struct TreeNode* right; }; void tree_insert(struct TreeNode** rootp, char newkey[]) { if (*rootp == NULL) { struct TreeNode* newnode = malloc(sizeof(struct TreeNode)); strcpy(newnode->key, newkey); newnode->count = 1; newnode->left = newnode->right = NULL; *rootp = newnode; } else if (strcmp(newkey, (*rootp)->key) == 0) ++(*rootp)->count; else if (strcmp(newkey, (*rootp)->key) < 0) tree_insert(&(*rootp)->left, newkey); else /* if (strcmp(newkey, (*rootp)->key) > 0) */ tree_insert(&(*rootp)->right, newkey); } void print_tree(struct TreeNode* root) { if (root != NULL) { print_tree(root->left); printf("%s: %d\n", root->key, root->count); print_tree(root->right); } } int main(void) { struct TreeNode* root = NULL; char key[MAX_WORD_LENGTH + 1]; while (scanf("%20s", key) == 1) tree_insert(&root, key); print_tree(root); return 0; } 18. Träd av högre ordning (ordning N = N grenar under varje nod) ---------------------------------------------------------------- O(Nlog n) = O(log n) 19. Hashtabeller (kallas "söktabeller" i kompendiet) ---------------------------------------------------- O(1), nästan i alla fall.