Programexempel från Progmet-föreläsning 12, onsdag 7 oktober 2009 ================================================================= 1. Forts från förra gången: hashtabell.c -- men vi visade en version med pekare i stället ---------------------------------------- #include #include #include #define HASH_TABLE_SIZE 47 struct HashNode { int in_use; double data; struct HashNode* next_in_bucket; }; int hashfunktion(double data) { return (int)fabs(data) % HASH_TABLE_SIZE; } int hash_search(struct HashNode ht[], double wanted) { int position = hashfunktion(wanted); if (ht[position].data == wanted) return 1; struct HashNode* p = ht[position].next_in_bucket; while (p != NULL) { if (p->data == wanted) return 1; p = p->next_in_bucket; } return 0; } void hash_insert(struct HashNode ht[], double newdata) { int position = hashfunktion(newdata); if (ht[position].in_use == 0) { ht[position].in_use = 1; ht[position].data = newdata; } else { struct HashNode* newnode = malloc(sizeof(struct HashNode)); newnode->data = newdata; newnode->next_in_bucket = ht[position].next_in_bucket; ht[position].next_in_bucket = newnode; } } int main(void) { struct HashNode ht[HASH_TABLE_SIZE]; for (int i = 0; i < HASH_TABLE_SIZE; ++i) { ht[i].in_use = 0; ht[i].next_in_bucket = NULL; } 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]); for (int i = 0; i < antal; ++i) hash_insert(ht, a[i]); double talet; printf("Skriv tal. Avsluta med EOF eller ett ogiltigt tal.\n"); while (scanf("%lf", &talet) == 1) { int resultat = hash_search(ht, talet); if (resultat) printf("Hittade det.\n"); else printf("Hittade det inte.\n"); } return 0; } 2. hashwordcounter.c -------------------- #include #include #include #define MAX_WORD_LENGTH 20 #define HASH_TABLE_SIZE 47 struct HashNode { char key[MAX_WORD_LENGTH + 1]; int count; struct HashNode* next_in_bucket; }; unsigned int hashfunktion(unsigned char *s) { unsigned int resultat = 5381; int c; while ((c = *s++) != '\0') resultat = resultat * 33 + c; return resultat % HASH_TABLE_SIZE; } unsigned int samma_hashfunktion(unsigned char *s) { unsigned int resultat = 5381; int n = strlen(s); for (int i = 0; i < n; ++i) resultat = resultat * 33 + s[i]; return resultat % HASH_TABLE_SIZE; } void hash_insert(struct HashNode* ht[], char* newkey) { int position = hashfunktion(newkey); struct HashNode* p = ht[position]; while (p != NULL) { if (strcmp(newkey, p->key) == 0) { ++p->count; return; } p = p->next_in_bucket; } struct HashNode* newnode = malloc(sizeof(struct HashNode)); strcpy(newnode->key, newkey); newnode->count = 1; newnode->next_in_bucket = ht[position]; ht[position] = newnode; } void print_table(struct HashNode* ht[]) { for (int position = 0; position < HASH_TABLE_SIZE; ++position) { struct HashNode* p = ht[position]; while (p != NULL) { printf("%s: %d\n", p->key, p->count); p = p->next_in_bucket; } } } int main(void) { struct HashNode* hashtabellen[HASH_TABLE_SIZE]; for (int i = 0; i < HASH_TABLE_SIZE; ++i) hashtabellen[i] = NULL; char key[MAX_WORD_LENGTH + 1]; while (scanf("%20s", key) == 1) hash_insert(hashtabellen, key); print_table(hashtabellen); return 0; } 3. Lågnivåprogrammering: bitar och bytes ---------------------------------------- Bitar och byte (char) binärt, decimalt och hexadecimalt little-endian och big-endian Kom ihåg de bitvisa operatorerna -------------------------------- Vänsterskift: << Högerskift: >> Bitvis OCH ("AND"): & Bitvis ELLER ("OR"): | Bitvis XOR: ^ Bitvis INTE ("NOT"): ~ Jämför med logisk, inte bitvis, OCH: && Jämför med logisk, inte bitvis, ELLER: || Jämför med logisk, inte bitvis, INTE: ! Några bra operationer --------------------- Notera att & och | har konstig prioritet Är bit N satt? c & (1 << N) Sätt bit N c = c | (1 << N) c |= (1 << N) Nolla bit N c = c & ~(1 << N) c &= ~(1 << N) Toggla bit N c = c ^ (1 << N) c ^= (1 << N) Utmatning av bitarna i minnet ----------------------------- Decimalt: %d, %u Hexadecimalt: %x Binärt Bitfält i poster ---------------- 4. En abstrakt datatyp: mängd av heltal --------------------------------------- Variant 1 - fast array av tal, ett tal per position --------------------------------------------------- /* bilnummer.c */ #include #include "IntSet.h" int main(void) { IntSet mina_bilnummer; IntSet_init(&mina_bilnummer); printf("Mata in heltalsdelen av bilnummer. Avsluta med ett ogiltigt tal.\n"); int bilnumret; while (scanf("%d", &bilnumret) == 1) { if (IntSet_is_member(&mina_bilnummer, bilnumret)) printf("Fanns redan.\n"); else { printf("Nytt!\n"); IntSet_add(&mina_bilnummer, bilnumret); } } IntSet_cleanup(&mina_bilnummer); return 0; } /* IntSet.h */ #ifndef INTSET_H #define INTSET_H #define INTSET_MAX_MEMBERS 1000 struct IntSet { int members[INTSET_MAX_MEMBERS]; int nr_members; }; typedef struct IntSet IntSet; extern void IntSet_init(IntSet* isp); extern void IntSet_add(IntSet* isp, int n); extern int IntSet_is_member(IntSet* isp, int n); extern void IntSet_remove(IntSet* isp, int n); extern void IntSet_cleanup(IntSet* isp); #endif /* IntSet.c */ #include #include #include "IntSet.h" void IntSet_init(IntSet* isp) { isp->nr_members = 0; } void IntSet_add(IntSet* isp, int new_number) { if (IntSet_is_member(isp, new_number)) { // Already a member, so do nothing } else if (isp->nr_members == INTSET_MAX_MEMBERS) { fprintf(stderr, "IntSet: Set full. Sorry.\n"); exit(EXIT_FAILURE); } else { isp->members[isp->nr_members++] = new_number; } } /* void int IntSet_is_member(IntSet* isp, int wanted) { for (int i = 0; i < isp->nr_members; ++i) if (isp->members[i] == wanted) return 1; return 0; } */ static int find_position(IntSet* isp, int wanted) { for (int i = 0; i < isp->nr_members; ++i) if (isp->members[i] == wanted) return i; return -1; } int IntSet_is_member(IntSet* isp, int wanted) { return find_position(isp, wanted) != -1; } void IntSet_remove(IntSet* isp, int doomed) { int position = find_position(isp, doomed); if (position == -1) { // Not a member, so do nothing } else { for (int i = position; i < isp->nr_members - 1; ++i) isp->members[i] = isp->members[i + 1]; --isp->nr_members; } } void IntSet_cleanup(IntSet* isp) { isp->nr_members = 0; } Variant 2 - dynamisk allokerad array av tal, ett tal per position ----------------------------------------------------------------- /* IntSet.h */ #ifndef INTSET_H #define INTSET_H struct IntSet { int* members; int allocated_members; int nr_members; }; typedef struct IntSet IntSet; extern void IntSet_init(IntSet* isp); extern void IntSet_add(IntSet* isp, int n); extern int IntSet_is_member(IntSet* isp, int n); extern void IntSet_remove(IntSet* isp, int n); extern void IntSet_cleanup(IntSet* isp); #endif /* IntSet.c */ #include #include #include "IntSet.h" void IntSet_init(IntSet* isp) { isp->members = NULL; isp->allocated_members = 0; isp->nr_members = 0; } void IntSet_add(IntSet* isp, int new_number) { if (IntSet_is_member(isp, new_number)) { // Already a member, so do nothing } else { if (isp->nr_members == isp->allocated_members) { if (isp->allocated_members == 0) isp->allocated_members = 16; else isp->allocated_members *= 2; isp->members = realloc(isp->members, isp->allocated_members * sizeof(isp->members[0])); if (isp->members == NULL) { fprintf(stderr, "IntSet: Memory full. Couldn't allocate %ld bytes. Sorry.\n", (long int)(isp->allocated_members * sizeof(isp->members[0]))); exit(EXIT_FAILURE); } } isp->members[isp->nr_members++] = new_number; } } static int find_position(IntSet* isp, int wanted) { for (int i = 0; i < isp->nr_members; ++i) if (isp->members[i] == wanted) return i; return -1; } int IntSet_is_member(IntSet* isp, int wanted) { return find_position(isp, wanted) != -1; } void IntSet_remove(IntSet* isp, int doomed) { int position = find_position(isp, doomed); if (position == -1) { // Not a member, so do nothing } else { for (int i = position; i < isp->nr_members - 1; ++i) isp->members[i] = isp->members[i + 1]; --isp->nr_members; } } void IntSet_cleanup(IntSet* isp) { free(isp->members); isp->members = NULL; isp->allocated_members = 0; isp->nr_members = 0; } Variant 3 - fast array av flaggor, en per möjligt tal ----------------------------------------------------- /* IntSet.h */ #ifndef INTSET_H #define INTSET_H #define INTSET_MAX_NUMBER 1000 struct IntSet { int members[INTSET_MAX_NUMBER + 1]; }; typedef struct IntSet IntSet; extern void IntSet_init(IntSet* isp); extern void IntSet_add(IntSet* isp, int n); extern int IntSet_is_member(IntSet* isp, int n); extern void IntSet_remove(IntSet* isp, int n); extern void IntSet_cleanup(IntSet* isp); #endif /* IntSet.c */ #include #include #include "IntSet.h" void IntSet_init(IntSet* isp) { for (int i = 0; i <= INTSET_MAX_NUMBER; ++i) isp->members[i] = 0; } void IntSet_add(IntSet* isp, int new_number) { if (IntSet_is_member(isp, new_number)) { // Already a member, so do nothing } else if (new_number < 0 || new_number > INTSET_MAX_NUMBER) { fprintf(stderr, "IntSet: Number outside allowed range. Sorry.\n"); exit(EXIT_FAILURE); } else { isp->members[new_number] = 1; } } int IntSet_is_member(IntSet* isp, int wanted) { if (wanted < 0 || wanted > INTSET_MAX_NUMBER) return 0; else return isp->members[wanted]; } void IntSet_remove(IntSet* isp, int doomed) { if (doomed < 0 || doomed > INTSET_MAX_NUMBER) { // Outside range, so can't be in the set. Do nothing. exit(EXIT_FAILURE); } else { isp->members[doomed] = 0; } } void IntSet_cleanup(IntSet* isp) { for (int i = 0; i <= INTSET_MAX_NUMBER; ++i) isp->members[i] = 0; } Variant 4 - fast array av flaggor, en per möjligt tal, men packad ----------------------------------------------------------------- /* IntSet.h */ #ifndef INTSET_H #define INTSET_H #include #define INTSET_MAX_NUMBER 1000 #define INTSET_NR_BYTES ((INTSET_MAX_NUMBER + 1) / CHAR_BIT + 1) struct IntSet { char members[INTSET_NR_BYTES]; }; typedef struct IntSet IntSet; extern void IntSet_init(IntSet* isp); extern void IntSet_add(IntSet* isp, int n); extern int IntSet_is_member(IntSet* isp, int n); extern void IntSet_remove(IntSet* isp, int n); extern void IntSet_cleanup(IntSet* isp); #endif /* IntSet.c */ #include #include #include "IntSet.h" void IntSet_init(IntSet* isp) { for (int i = 0; i <= INTSET_NR_BYTES; ++i) isp->members[i] = 0; } void IntSet_add(IntSet* isp, int new_number) { if (IntSet_is_member(isp, new_number)) { // Already a member, so do nothing } else if (new_number < 0 || new_number > INTSET_MAX_NUMBER) { fprintf(stderr, "IntSet: Number outside allowed range. Sorry.\n"); exit(EXIT_FAILURE); } else { isp->members[new_number / CHAR_BIT] |= (1 << new_number % CHAR_BIT); } } int IntSet_is_member(IntSet* isp, int wanted) { if (wanted < 0 || wanted > INTSET_MAX_NUMBER) return 0; else return (isp->members[wanted / CHAR_BIT] & (1 << wanted % CHAR_BIT)) != 0; // return isp->members[wanted / CHAR_BIT] & (1 << wanted % CHAR_BIT); -- Doesn't work: } void IntSet_remove(IntSet* isp, int doomed) { if (doomed < 0 || doomed > INTSET_MAX_NUMBER) { // Outside range, so can't be in the set. Do nothing. exit(EXIT_FAILURE); } else { isp->members[doomed / CHAR_BIT] &= ~(1 << doomed % CHAR_BIT); } } void IntSet_cleanup(IntSet* isp) { for (int i = 0; i <= INTSET_NR_BYTES; ++i) isp->members[i] = 0; } Variant 5 - binärt träd ----------------------- /* IntSet.h */ #ifndef INTSET_H #define INTSET_H struct IntSetNode { int member; struct IntSetNode* left; struct IntSetNode* right; }; struct IntSet { struct IntSetNode* root; }; typedef struct IntSet IntSet; extern void IntSet_init(IntSet* isp); extern void IntSet_add(IntSet* isp, int n); extern int IntSet_is_member(IntSet* isp, int n); extern void IntSet_remove(IntSet* isp, int n); extern void IntSet_cleanup(IntSet* isp); #endif /* IntSet.c */ .... Variant 6 - hashtabell ---------------------- ....