Programexempel från Progmet-föreläsning 12, tisdag 23 oktober 2012 ================================================================== Dagens program: 1. Fortsättning: bitar och bytes 2. Mer om hårdvarunära programmering: volatile mm 3. Sorteringsalgoritmer och deras tidskomplexitet 4. Varför? Om vi eventuellt hinner idag: 5. Programkonstruktion 6. En abstrakt datatyp: mängd av heltal 1. Lågnivåprogrammering: bitar och bytes ======================================== Bitar och byte (char) binärt, decimalt och hexadecimalt (men allt är binärt internt! eller?) little-endian och big-endian De bitvisa operatorerna ----------------------- Jämför med logisk, inte bitvis, OCH: && Jämför med logisk, inte bitvis, ELLER: || Jämför med logisk, inte bitvis, INTE: ! Bitvis OCH ("AND"): & Bitvis ELLER ("OR"): | Bitvis XOR: ^ Bitvis INTE ("NOT"): ~ Vänsterskift: << Högerskift: >> 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 storlekar.c ----------- #include #include int main(void) { printf("En char är %d bitar.\n", CHAR_BIT); printf("En int är %d bitar.\n", (int)(sizeof(int) * CHAR_BIT)); printf("En long int är %d bitar.\n", (int)(sizeof(long int) * CHAR_BIT)); printf("En void-pekare är %d bitar.\n", (int)(sizeof(void*) * CHAR_BIT)); return 0; } Utmatning på en i7 med Linux (64-bitars) ---------------------------------------- En char är 8 bitar. En int är 32 bitar. En long int är 64 bitar. En void-pekare är 64 bitar. Utmatning på en Sun Sparc (32-bitars) ------------------------------------- En char är 8 bitar. En int är 32 bitar. En long int är 32 bitar. En void-pekare är 32 bitar. byte-order.c ------------ #include #include void print_int(int n) { printf("%d = %08x =", n, n); unsigned char *p = (unsigned char*)&n; for (int i = 0; i < sizeof(n); ++i) printf(" %2.2x", p[i]); printf(" = "); for (int i = 0; i < sizeof(n); ++i) { for (int b = 0; b < CHAR_BIT; ++b) printf("%d", (p[i] & 1 << (CHAR_BIT - b - 1)) >> (CHAR_BIT - b - 1)); printf(" "); } printf("\n"); } int main(void) { int i1 = -1; // 11111111 11111111 11111111 11111111 int i2 = 17; // 00000000 00000000 00000000 00010001 int i3 = 300; // 00000000 00000000 00000001 00101100 print_int(i1); print_int(i2); print_int(i3); return 0; } Utmatning på en Sun Sparc (big-endian) -------------------------------------- -1 = ffffffff = ff ff ff ff = 11111111 11111111 11111111 11111111 17 = 00000011 = 00 00 00 11 = 00000000 00000000 00000000 00010001 300 = 0000012c = 00 00 01 2c = 00000000 00000000 00000001 00101100 Utmatning på en i7 med Linux (little-endian) -------------------------------------------- -1 = ffffffff = ff ff ff ff = 11111111 11111111 11111111 11111111 17 = 00000011 = 11 00 00 00 = 00010001 00000000 00000000 00000000 300 = 0000012c = 2c 01 00 00 = 00101100 00000001 00000000 00000000 Julgranar som bitar och som bitfält: julgranar.c ------------------------------------------------ #include #include struct julgran { unsigned int ljus1 : 1; unsigned int ljus2 : 1; unsigned int ljus3 : 1; unsigned int ljus4 : 1; unsigned int ljus5 : 1; unsigned int ljus6 : 1; unsigned int ljus7 : 1; unsigned int ljus8 : 1; }; void visa_julgran_int(int julgran) { if (julgran & 1) printf("*"); else printf("-"); if (julgran & 1 << 1) printf("*"); else printf("-"); if (julgran & 1 << 2) printf("*"); else printf("-"); if (julgran & 1 << 3) printf("*"); else printf("-"); if (julgran & 1 << 4) printf("*"); else printf("-"); if (julgran & 1 << 5) printf("*"); else printf("-"); if (julgran & 1 << 6) printf("*"); else printf("-"); if (julgran & 1 << 7) printf("*"); else printf("-"); printf("\n"); } void visa_julgran_bitfalt(struct julgran julgran) { if (julgran.ljus1) printf("*"); else printf("-"); if (julgran.ljus2) printf("*"); else printf("-"); if (julgran.ljus3) printf("*"); else printf("-"); if (julgran.ljus4) printf("*"); else printf("-"); if (julgran.ljus5) printf("*"); else printf("-"); if (julgran.ljus6) printf("*"); else printf("-"); if (julgran.ljus7) printf("*"); else printf("-"); if (julgran.ljus8) printf("*"); else printf("-"); printf("\n"); } int main(void) { int julgran1; struct julgran julgran2; julgran1 = 0; julgran2.ljus1 = 0; julgran2.ljus2 = 0; julgran2.ljus3 = 0; julgran2.ljus4 = 0; julgran2.ljus5 = 0; julgran2.ljus6 = 0; julgran2.ljus7 = 0; julgran2.ljus8 = 0; visa_julgran_int(julgran1); visa_julgran_bitfalt(julgran2); julgran1 |= 1; julgran1 |= 1 << 1; julgran1 |= 1 << 7; julgran2.ljus1 = 1; julgran2.ljus2 = 1; julgran2.ljus8 = 1; visa_julgran_int(julgran1); visa_julgran_bitfalt(julgran2); return 0; } Utmatning --------- -------- -------- **-----* **-----* 2. Mer om hårdvarunära programmering ==================================== minesmappning (till exempel I/O-portar) volatile mappa in fil (mmap i Unix; går det i Windows?) Exempel på användning av "volatile" ----------------------------------- volatile inporten; // Minnesmappad till en inport kopplad till en termometer int temperatur = inporten; // Vänta på att temperaturen ändras: while (inporten == temperatur) { // Gör inget } printf("Temperaturen har ändrats!\n"); 3. Sorteringsalgoritmer och deras tidskomplexitet ================================================= Sorting Out Sorting: http://video.google.com/videoplay?docid=-4110947752111188923 Från inlämningsuppgift 2: * Selection Sort // Sorts the array "a" of length "length" in ascending order using selection sort void sort_array(double a[], int length) { for (int sorted = 0; sorted < length - 1; ++sorted) { int smallest_in_rest = sorted; for (int in_rest = sorted + 1; in_rest < length; ++in_rest) { if (a[in_rest] < a[smallest_in_rest]) { smallest_in_rest = in_rest; } } double temp = a[sorted]; a[sorted] = a[smallest_in_rest]; a[smallest_in_rest] = temp; } } * Bogosort void bogosort_array(double a[], int length) { while (! is_array_sorted(a, length)) shuffle_array(a, length); } * Ännu dummare: void hopesort_array(double a[], int length) { // Gör inget, bara hoppas att den redan är sorterad } * Men! "Near sorting" ("soft heap") ... Fler: * Linear Insertion Sort -- O(n^2) // Sorts the array "a" of length "length" in ascending order using linear insertion sort void linear_insertion_sort(double a[], int length) { for (int sorted = 1; sorted < length; ++sorted) { // Insert the current elmenent (a[sorted]) at its place in the sorted part // Sorted part starts as 1, since a single element is always sorted! double current = a[sorted]; int place = sorted; while (place > 0 && a[place - 1] > current) { a[place] = a[place - 1]; --place; } a[place] = current; } } // linear_insertion_sort * Binary Insertion Sort -- O(n log n) jämförelser, men O(n^2) förflyttningar // Sorts the array "a" of length "length" in ascending order using binary insertion sort void binary_insertion_sort(double a[], int length) { for (int sorted = 1; sorted < length; ++sorted) { // Insert the current elmenent (a[sorted]) at its place in the sorted part // Sorted part starts as 1, since a single element is always sorted! double current = a[sorted]; // Binary search in the sorted part to find the right place for current int left = 0; int right = sorted; while (left < right) { int middle = (left + right) / 2; if (current >= a[middle]) left = middle + 1; else right = middle; } for (int i = sorted; i > left; --i) a[i] = a[i - 1]; a[left] = current; } } // binary_insertion_sort * Quicksort -- O(n log n), genomsnitt, men värsta fallet är sämre // Sorts the array "a" from (including) "left" to (also including) "right" static void qs(double a[], int left, int right) { int i, j; i = left; j = right; double pivot = a[(left+right)/2]; do { while((a[i] < pivot) && (i < right)) i++; while((pivot < a[j]) && (j > left)) j--; if(i <= j) { double temporary = a[i]; a[i] = a[j]; a[j] = temporary; i++; j--; } } while(i <= j); if(i < right) qs(a, i, right); if(left < j) qs(a, left, j); } // Sorts the array "a" of length "length" in ascending order using quicksort void quicksort(double a[], int length) { qs(a, 0, length - 1); } "Okonventionella" ("utan jämförelser"): * Counting Sort -- O(n) * Radix Sort -- O(n) Stora datamängder: * Merge sort "Fysisk sortering": Om det är järnvägsvagnar på en bangård, eller containrar på en båt? Hur gör man då? 4. Varför? Exempel: Ett program som hittar dubbletter av filer! =============================================================== Hur kan man tänka? 1. Två filer som är olika stora kan aldrig vara lika, så man behöver bara jämföra filer som är lika stora. 2. Man kan (från OS:et) snabbt få fram filstorleken för en fil, utan att öppna filen och läsa innehållet. 3. Sortera alla filerna i storleksordning med quicksort? Eller finns det en bättre lösning i det här fallet? 5. Programkonstruktion ====================== En bok av Niklaus Wirth: "Algorithms + Data Structures = Programs" Olika sätt att tänka ut hur programmet ska se ut: 1a) Programmets algoritmer ("bearbetningen", "programstegen") gör vi med stegvis förfining Vi kan rita det med strukturdiagram (inte flödesscheman), eller visa med pseudokod 1b) Eller genom att studera dataflöden 2) Och för programmets data kan vi använda abstrakta datatyper (jämför: ER-diagram, objektorientering) Exempel: Frukost med kaffe och smörgåsar Andra exempel: 1a) Stegvis förfining: Mätprogram enligt figuren i kompendiet sid 61 1b) Dataflöden: Valutaprogram enligt figuren i kompendiet sid 70 2) Abstrakta datatyper: Dating-programmet (se nedan) (Se kompendiet kapitel 4, och hela del 4 av Gunnars föreläsningsanteckningar) 5.1 Kom ihåg: Abstrakta datatyper ================================= Abstrakt datatyp = en modul ("avgränsad del", "svart låda") med "en sorts saker" och "operationer" på dessa Exempel: heltal i C! Sakerna = själva heltalen, lagras på något sätt Operationer +, -, %, ==, <, =, ... 5.2 Möjlig arbetsgång (jfr gunnars föreläsning nr 4, sid 6) =========================================================== Programkonstruktion med abstrakta datatyper Som exempel: Inlämningsuppgift 3, Dating! 1. Pojkar och flickor med intressen 2. Programmet parar ihop dem enligt intressena Arbetsgång: 1. Vilka saker ("objekt") ska vi jobba med? Ex: Pojkar, flickor, par, intressen 2. För var och en av dessa saker: Vad ska man kunna göra med den? Ex: Skapa, visa, jämföra... 3. Hitta beroenden, t ex som ett beroendediagram. (Det ovanstående är redan klart.) 4. Implementera! Börja längst ner i beroendediagrammet ("bottom-up"), och testa varje modul för sig! 5. Igen: Testa varje modul för sig. Ni kommer väl ihåg testning?! 6. Integrationstest! Bottom-up! Inte big-bang-testning! Saker som finns i programmet, och som blir abstrakta datatyper (och separatkompilerade moduler): * Intressen, och samlingar av intressen: datatypen "Intressetabell" * Personer: datatypen "Person" * Listor av personer: datatypen "Personlista" * Par, som består av en pojke och en flicka: datatypen "Par" * Listor av par: datatypen "Parlista" Listorna implementeras med hjälp av std::list (std::list och std::list) En modul som inte är en abstrakt datatyp: * Dating, som är huvudmodulen med main-funktionen 5.3 Ett förtydligande av kompendiet =================================== En "modul" och en "abstrakt datatyp" är inte samma sak. En abstrakt datatyp är en modul, men inte alla moduler är abstrakta datatyper. Exempel: Huvudprogrammet "Dating" är en modul, men inte en abstrakt datatyp. Stdio-paketet är en modul, men inte en abstrakt datatyp. (Men man kan se datatypen FILE som en abstrakt datatyp.) 6. En abstrakt datatyp: mängd av heltal ======================================= Ett gränssnitt: * Namnet IntSet * Funktionerna init, add, is_member, remove och cleanup * (De kallas IntSet_init, IntSet_add, IntSet_is_member, IntSet_remove och IntSet_cleanup.) Användning: Bilnummerspelet Flera möjliga implementationer: Variant 1 - fast array av tal, ett tal per position Variant 2 - dynamisk allokerad array av tal, ett tal per position Variant 3 - fast array av flaggor, en per möjligt tal Variant 4 - fast array av flaggor, en per möjligt tal, men packad Variant 5 - dynamiskt allokerad array av flaggor, en per möjligt tal, packad Variant 6 - binärt träd Variant 7 - hashtabell (Variant 8 - std::set) 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 - dynamiskt allokerad array av flaggor, en per möjligt tal, packad ---------------------------------------------------------------------------- ... Variant 6 - 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 7 - hashtabell ---------------------- /* IntSet.h */ #ifndef INTSET_H #define INTSET_H #define INTSET_HASH_TABLE_SIZE 4703 struct IntSetHashNode { int member; struct IntSetHashNode* next_in_bucket; }; struct IntSet { struct IntSetHashNode* hash_table[INTSET_HASH_TABLE_SIZE]; }; typedef struct IntSet IntSet; extern void IntSet_init(IntSet* isp); extern void IntSet_add(IntSet* isp, int new_number); extern int IntSet_is_member(IntSet* isp, int wanted); extern void IntSet_remove(IntSet* isp, int wanted); 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_HASH_TABLE_SIZE; ++i) isp->hash_table[i] = NULL; } static unsigned int hash_function(int n) { if (n < 0) n = -n; return n % INTSET_HASH_TABLE_SIZE; } void IntSet_add(IntSet* isp, int new_number) { if (IntSet_is_member(isp, new_number)) { // Already a member, so do nothing } else { struct IntSetHashNode* newnode = malloc(sizeof(struct IntSetHashNode)); if (newnode == NULL) { fprintf(stderr, "IntSet: Minnet är fullt. Vi beklagar. Adjö.\n"); exit(EXIT_FAILURE); } newnode->member = new_number; unsigned int position = hash_function(new_number); newnode->next_in_bucket = isp->hash_table[position]; isp->hash_table[position] = newnode; } } int IntSet_is_member(IntSet* isp, int wanted) { unsigned int position = hash_function(wanted); struct IntSetHashNode* p = isp->hash_table[position]; while (p != NULL) { if (p->member == wanted) return 1; else p = p->next_in_bucket; } return 0; } void IntSet_remove(IntSet* isp, int wanted) { unsigned int position = hash_function(wanted); struct IntSetHashNode* p = isp->hash_table[position]; struct IntSetHashNode* previous = NULL; while (p != NULL) { if (p->member == wanted) { struct IntSetHashNode* doomed = p; if (previous == NULL) isp->hash_table[position] = p->next_in_bucket; else previous->next_in_bucket = p->next_in_bucket; free(doomed); return; } previous = p; p = p->next_in_bucket; } } void IntSet_cleanup(IntSet* isp) { for (int i = 0; i < INTSET_HASH_TABLE_SIZE; ++i) { struct IntSetHashNode* p = isp->hash_table[i]; while (p != NULL) { struct IntSetHashNode* doomed = p; p = p->next_in_bucket; free(doomed); } } } (Variant 8 - std::set) ---------------------- Förstås enklare att implementera, men datastrukturen i botten är ju någon av de här (eller en annan). Övning: Vilken?