Programexempel från Progmet-föreläsning 8, onsdag 9 oktober 2008 ================================================================ 1. En C-finess: dynamiska arrayer med malloc och realloc -------------------------------------------------------- medel.c (läser in en tal till en dynamiskt växande array) --------------------------------------------------------- #include #include int main(void) { double* a; int n = 0; double talet; a = malloc(1 * sizeof(double)); printf("Skriv tal. Avsluta med EOF eller ett ogiltigt tal.\n"); while (scanf("%lf", &talet) == 1) { a = realloc(a, ++n * sizeof(double)); a[n-1] = talet; } double summan = 0; for (int i = 0; i < n; ++i) summan += a[i]; double medel = summan / n; printf("Medel: %.2f\n", medel); return 0; } antal-1.c (eftersom det egentligen var onödigt med en array i medel.c) ---------------------------------------------------------------------- #include #include int main(void) { double* a; int n = 0; double talet; a = malloc(1 * sizeof(double)); printf("Skriv tal. Avsluta med EOF eller ett ogiltigt tal.\n"); while (scanf("%lf", &talet) == 1) { a = realloc(a, ++n * sizeof(double)); a[n-1] = talet; } double summan = 0; for (int i = 0; i < n; ++i) summan += a[i]; double medel = summan / n; int antal_mindre = 0; for (int i = 0; i < n; ++i) if (a[i] < medel) ++antal_mindre; printf("%d av %d tal (%d%%) var mindre än genomsnittet (%.2f).\n", antal_mindre, n, 100 * antal_mindre / n, medel); return 0; } antal-2.c (som utnyttjar hur realloc fungerar) ---------------------------------------------- #include #include int main(void) { double* a = NULL; int n = 0; double talet; printf("Skriv tal. Avsluta med EOF eller ett ogiltigt tal.\n"); while (scanf("%lf", &talet) == 1) { // realloc(NULL, x) funkar som malloc(x) a = realloc(a, ++n * sizeof(double)); a[n-1] = talet; } double summan = 0; for (int i = 0; i < n; ++i) summan += a[i]; double medel = summan / n; int antal_mindre = 0; for (int i = 0; i < n; ++i) if (a[i] < medel) ++antal_mindre; printf("%d av %d tal (%d%%) var mindre än genomsnittet (%.2f).\n", antal_mindre, n, 100 * antal_mindre / n, medel); return 0; } antal-3.c (lite bättre tidsprestanda, men kräver lite mer minne) ---------------------------------------------------------------- #include #include int main(void) { double* talen = NULL; int antal_tal = 0; int arraystorlek = 0; double talet; printf("Skriv tal. Avsluta med EOF eller ett ogiltigt tal.\n"); while (scanf("%lf", &talet) == 1) { if (antal_tal == arraystorlek) { /* Ingen ledig plats kvar i arrayen */ if (arraystorlek == 0) arraystorlek = 10; else arraystorlek *= 2; talen = realloc(talen, arraystorlek * sizeof(double)); } talen[antal_tal++] = talet; } double summan = 0; for (int i = 0; i < antal_tal; ++i) summan += talen[i]; double medel = summan / antal_tal; int antal_mindre = 0; for (int i = 0; i < antal_tal; ++i) if (talen[i] < medel) ++antal_mindre; printf("%d av %d tal (%d%%) var mindre än genomsnittet (%.2f).\n", antal_mindre, antal_tal, 100 * antal_mindre / antal_tal, medel); return 0; } 2. Sökning ---------- Sökning: O(n), O(log n) eller O(1) Kom ihåg: Tid(n) = n + 13 = O(n) Tid(n) = 8*n + 13 = O(n) Tid(n) = 8*n + 13000000 = O(n) Tid(n) = 47*n**2 + 99*n + 999 = O(n**2) (Obs: ** betyder här "upphöjt till", men inte i C, C++, Java...) Varför? Jo, bara n blir tillräckligt stort, blir den "viktigaste" ("dominerande") termen (med störst exponent) så mycket större att man kan strunta i de andra. Vi struntar också i konstanterna. Mera: Tid(n) = 1 = O(1) Tid(n) = 47 = O(1) Tid(n) = 2log n = O(log n) Tid(n) = 2log n + 133 = O(log n) Tid(n) = 10log n = 2 * 100log n = 3 * 1000log n = O(log n) Tid(n) = n + 2log n = O(n) Tid(n) = n * 3log n = O(n * log n) 3. 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) 4. 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! } } 5. 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! } 6. Sökning i en länkad lista ---------------------------- O(n) precis som i en array 7. Rekursion ------------ 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; } 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; } Körexempel ---------- fakultet(3) = 6 fakultet(10) = 3628800 fakultet(20) = -2102132736 8. Binärsökning i en sorterad array ----------------------------------- O(2log n) = O(log n) 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; } 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; } 9. Binärsökning i en länkad lista? ---------------------------------- Går inte. Övning: Varför? 10. Binärt träd --------------- O(2log n) = O(log n) 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; } 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; } 11. Träd av högre ordning (ordning N = N grenar under varje nod) ---------------------------------------------------------------- O(Nlog n) = O(log n) 12. Hashtabeller (kallas "söktabeller" i kompendiet) ---------------------------------------------------- O(1), nästan i alla fall.