Programexempel från Progmet-föreläsning 8, torsdag 22 september 2011 ==================================================================== 1. Rekursion 2. Olika datastrukturer för sökning 3. Sökning i en (vanlig fast) array 4. Sökning i en dynamisk array 5. Sökning i en länkad lista 6. Binärsökning i en sorterad array 7. Binärsökning i en länkad lista? 8. Binärt träd 9. Träd av högre ordning ("ordning N" = N grenar under varje nod) 10. Hashtabeller (kallas "söktabeller" i kompendiet) 11. Läs mer 1. Rekursion ============ 1a: Rekursion ------------- Behövs innan vi jobbar vidare med sökning i sorterade arrayer, träd mm. 1b: 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; } 1c: 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; } 1d: Körexempel --------------- fakultet(3) = 6 fakultet(10) = 3628800 fakultet(20) = -2102132736 2. 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) 3. 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! } } 4. 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! } 5. Sökning i en länkad lista ============================ O(n) precis som i en array 6. Binärsökning i en sorterad array =================================== O(2log n) = O(log n) 6a: 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; } 6b: 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; } 7. Binärsökning i en länkad lista? ================================== Går inte. Övning: Varför? 8. Binärt träd ============== O(2log n) = O(log n) 8a: 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; } 8b: 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; } 9. Träd av högre ordning ("ordning N" = N grenar under varje nod) ================================================================= O(Nlog n) = O(log n) Samma tidskomplexitet, men FÄRRE noder besöks (pga lägre och buskigare träd) 10. Hashtabeller (kallas "söktabeller" i kompendiet) ==================================================== 11. Läs mer =========== "Vi lär oss det där med data: Grunder om lagringsstrukturer" (på hemsidan) Gunnar Jokis kompendium (på kursens hemsida): avsnitt 5.1 om träd avsnitt 5.2 om hashtabeller Bilting, "Vägen till C", 2000: rekursion beskrivs på sid 135-136 och används på sid 213 binärsökning nämns på sid 247 avsnitt 8.2.2 om hashtabeller avsnitt 8.2.3 om binära träd Janlert et al, "Datatyper och algoritmer", 2000: kapitel 11 om binära träd kapitel 14 om binära sökträd avsnitt 15.3 om hashtabeller Weiss, "Data Structures and Algorithm Analysis in C++", 3d Ed, 2006: binärsökning i avsnitt 2.4.4 (sid 58-60) binära sökträd i kapitel 4 hashtabeller i kapitel 5