Programexempel från Progmet-föreläsning 12, onsdag 22 oktober 2008 ================================================================== 1. Lite mer lågnivåprogrammering: bitar och bytes ------------------------------------------------- Kom ihåg de bitvisa operatorerna -------------------------------- Vänsterskift: << Högerskift: >> Bitvis OCH ("AND"): & Bitvis ELLER ("OR"): | Bitvis XOR: ^ Bitvis INTE ("NOT"): ~ Några bra operationer --------------------- Ä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 ---------------- 2. 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 ---------------------- .... 3. Hårdvarunära programmering -----------------------------