Lösningsförslag till datorövning 5 i Programmeringsmetodik /* Uppg5a.c */ #include void rekut(int n) { if ( n > 1) rekut(n-1); printf("%d\n", n); } int main() { int tal; printf("Tal : "); scanf("%d", &tal); rekut(tal); return 0; } /* Uppg5b.c */ #include int fib(int n) { if ( n == 1 || n == 2) return 1; return fib(n-2) + fib(n-1); } int main() { int tal; printf("Tal : "); scanf("%d", &tal); printf("Fibonacci(%d) = %d\n", tal, fib(tal)); return 0; } /* Uppg5c.c */ /* Teltree.c */ #include #include "tree.h" /* #include "telpers.h" typedef person datatyp; */ int main() { FILE *bsin; nodtyp *ptree = NULL, *sokpek; person p; /* läs från fil till träd */ bsin = fopen("telreg.dat", "rb"); fread(&p, sizeof(person), 1, bsin); while(!feof(bsin)) { intotree(&ptree, p, jfr_personer); fread(&p, sizeof(person), 1, bsin); } /* sök efter telnr */ printf("Vems telnr söks? "); gets(p.namn); sokpek = searchtree(ptree, p, lika_personer, jfr_personer); if(sokpek != NULL) skriv_person(sokpek->data); else printf("Personen finns ej!\n"); return 0; } /* telpers.h */ typedef struct { char namn[31]; char tel[15]; } person; int las_person(person *pp); void skriv_person(person p); int jfr_personer(person p1, person p2); int lika_personer(person p1, person p2); /* telpers.c */ #include #include #include "telpers.h" int las_person(person *pp) { printf("Namn : "); gets(pp->namn); if(pp->namn[0] =='\0') return 0; printf("Tel : "); gets(pp->tel); return 1; } void skriv_person(person p) { printf("Namn : %s\n", p.namn); printf("Tel : %s\n", p.tel); } int jfr_personer(person p1, person p2) { return strcmp(p1.namn, p2.namn) < 0; } int lika_personer(person p1, person p2) { return stricmp(p1.namn, p2.namn) == 0; } /* Uppg5d.c */ /* Telhash.c */ #include #include "linkhash.h" /* #include "telpers.h" typedef person datatyp; */ int main() { FILE *bsin; linktyp *hashtab[HASHTABSIZE], *sokpek; person p; initlinkhash(hashtab); /* läs från fil till hashtabell */ bsin = fopen("telreg.dat", "rb"); fread(&p, sizeof(person), 1, bsin); while(!feof(bsin)) { intolinkhash(hashtab, p, hash); fread(&p, sizeof(person), 1, bsin); } /* sök efter telnr */ printf("Vems telnr söks? "); gets(p.namn); sokpek = searchlinkhash(hashtab, p, hash, lika_personer); if(sokpek != NULL) skriv_person(sokpek->data); else printf("Personen finns ej!\n"); return 0; } /* telpers.h */ typedef struct { char namn[31]; char tel[15]; } person; int las_person(person *pp); void skriv_person(person p); int jfr_personer(person p1, person p2); int lika_personer(person p1, person p2); int hash(person p); /* telpers.c */ #include #include #include "telpers.h" int las_person(person *pp) { printf("Namn : "); gets(pp->namn); if(pp->namn[0] =='\0') return 0; printf("Tel : "); gets(pp->tel); return 1; } void skriv_person(person p) { printf("Namn : %s\n", p.namn); printf("Tel : %s\n", p.tel); } int jfr_personer(person p1, person p2) { return strcmp(p1.namn, p2.namn) < 0; } int lika_personer(person p1, person p2) { return stricmp(p1.namn, p2.namn) == 0; } int hash(person p) { int i, sum = 0; /* summan av ascii-koderna i namn */ for (i = 0; i < strlen(p.namn); i++) sum += p.namn[i]; return sum; } /* Uppg5e.c */ /* Telopen.c */ #include #include "openhash.h" /* #include "telpers.h" typedef person datatyp; */ int main() { FILE *bsin; datatyp *hashtab[HASHTABSIZE], *sokpek; person p; initopenhash(hashtab); /* läs från fil till hashtabell */ bsin = fopen("telreg.dat", "rb"); fread(&p, sizeof(person), 1, bsin); while(!feof(bsin)) { intoopenhash(hashtab, p, hash); fread(&p, sizeof(person), 1, bsin); } /* sök efter telnr */ printf("Vems telnr söks? "); gets(p.namn); sokpek = searchopenhash(hashtab, p, hash, lika_personer); if(sokpek != NULL) skriv_person(*sokpek); else printf("Personen finns ej!\n"); return 0; } /* Uppg5f.c */ /* Teltree.c */ #include #include "tree.h" /* #include "telpers.h" typedef person datatyp; */ int main() { FILE *bsin; nodtyp *ptree = NULL; person p; /* läs från fil till träd */ bsin = fopen("telreg.dat", "rb"); fread(&p, sizeof(person), 1, bsin); while(!feof(bsin)) { intotree(&ptree, p, jfr_personer); fread(&p, sizeof(person), 1, bsin); } /* skriv alla personer i trädet följt av antal */ showtree(ptree, skriv_person); printf("\nAntal personer : %d\n", nodes(ptree)); return 0; } /* Specifikation av binärt träd -- tree.h */ #include "telpers.h" typedef person datatyp; /* Exempelvis */ typedef struct nod { datatyp data; struct nod *left, *right; } nodtyp; void intotree(nodtyp **rpp, datatyp d, int (*is_less)(datatyp, datatyp)); /* Stoppar in d i trädet ordnat enligt is_less */ void showtree(nodtyp *rp, void (*write_data)(datatyp)); /* Skriver ut trädet med write_data funktionen */ nodtyp *searchtree(nodtyp *rp, datatyp key, int (*is_equal)(datatyp, datatyp), int (*is_less)(datatyp, datatyp)); /* Returnerar pekare till nyckelposten om den finns annars NULL */ int nodes(nodtyp *rp); /* Räknar antalet noder i trädet */ /* Implementation av binära trädet -- tree.c */ #include "tree.h" #include void intotree(nodtyp **rpp, datatyp d, int (*is_less)(datatyp, datatyp)) { if ( *rpp == NULL ) { *rpp = malloc(sizeof(nodtyp)); (*rpp)->data = d; (*rpp)->left = NULL; (*rpp)->right = NULL; } else if ( is_less(d, (*rpp)->data) ) intotree(&(*rpp)->left, d, is_less); else intotree(&(*rpp)->right, d, is_less); } void showtree(nodtyp *rp, void (*write_data)(datatyp)) { if ( rp != NULL ) { showtree(rp->left, write_data); write_data(rp->data); showtree(rp->right, write_data); } } nodtyp *searchtree(nodtyp *rp, datatyp key, int (*is_equal)(datatyp, datatyp), int (*is_less)(datatyp, datatyp)) { if (rp == NULL) return NULL; else if ( is_equal(key, rp->data) ) return rp; else if (is_less(key, rp->data)) return searchtree(rp->left, key, is_equal, is_less); else return searchtree(rp->right, key, is_equal, is_less); } int nodes(nodtyp *rp) { if (rp == NULL) return 0; return 1 + nodes(rp->left) + nodes(rp->right); } /* Uppg5g.c */ /* Telhash.c */ #include #include "linkhash.h" /* #include "telpers.h" typedef person datatyp; */ int main() { FILE *bsin; linktyp *hashtab[HASHTABSIZE], *sokpek; person p; initlinkhash(hashtab); /* läs från fil till hashtabell */ bsin = fopen("telreg.dat", "rb"); fread(&p, sizeof(person), 1, bsin); while(!feof(bsin)) { intolinkhash(hashtab, p, hash); skriv_person(p); fread(&p, sizeof(person), 1, bsin); } /* ta bort sökt person */ printf("Vem ska bort? "); gets(p.namn); elimlinkhash(hashtab, p, hash, lika_personer); /* sök efter person som ej ska finnas kvar */ printf("Vem söks? "); gets(p.namn); sokpek = searchlinkhash(hashtab, p, hash, lika_personer); if(sokpek != NULL) skriv_person(sokpek->data); else printf("Personen finns ej!\n"); return 0; } /* Specifikation av länkad hashtabell -- linkhash.h */ #ifndef LINKHASH_H #define LINKHASH_H #include "telpers.h" typedef person datatyp; /* Exempelvis */ #define HASHTABSIZE 100 typedef struct link { datatyp data; struct link *next; } linktyp; void initlinkhash(linktyp *htab[]); /* NULL-ställer hashtabellen */ void intolinkhash(linktyp *htab[], datatyp d, int (*hashfunk)(datatyp)); /* Stoppar in d i hashtabell enligt hashfunk */ linktyp *searchlinkhash(linktyp *htab[], datatyp nyckel, int (*hashfunk)(datatyp), int (*is_equal)(datatyp, datatyp)); /* Söker efter nyckel i hashtabell */ void elimlinkhash(linktyp *htab[], datatyp nyckel, int (*hashfunk)(datatyp), int (*is_equal)(datatyp, datatyp)); /* Tar bort nyckel från hashtabell */ #endif /* Implementation av länkad hashtabell -- linkhash.c */ #include "linkhash.h" #include void initlinkhash(linktyp *htab[]) { int i; for ( i = 0; i < HASHTABSIZE; i++) htab[i] = NULL; } void intolinkhash(linktyp *htab[], datatyp d, int (*hashfunk)(datatyp)) { int index; linktyp *lp; index = hashfunk(d) % HASHTABSIZE; lp = malloc(sizeof(linktyp)); lp->data = d; lp->next = htab[index]; htab[index] = lp; } linktyp *searchlinkhash(linktyp *htab[], datatyp nyckel, int (*hashfunk)(datatyp), int (*is_equal)(datatyp, datatyp)) { int index; linktyp *lp; index = hashfunk(nyckel) % HASHTABSIZE; lp = htab[index]; while (lp != NULL && !is_equal(nyckel, lp->data)) lp = lp->next; return lp; } void elimlinkhash(linktyp *htab[], datatyp nyckel, int (*hashfunk)(datatyp), int (*is_equal)(datatyp, datatyp)) { int index; linktyp *lp, *ep; index = hashfunk(nyckel) % HASHTABSIZE; lp = htab[index]; if (lp != NULL && is_equal(nyckel, lp->data)) { free(lp); htab[index] = NULL; } else { ep = lp; lp = lp->next; while (lp != NULL && !is_equal(nyckel, lp->data)) { ep = lp; lp = lp->next; } if (lp != NULL) { ep->next = lp->next; free(lp); } } }