migf1 Δημοσ. 21 Νοεμβρίου 2012 Δημοσ. 21 Νοεμβρίου 2012 με μπερδευει κατι οταν κανουμε typedef struct . 1. γιατι δεν μπορουμε να κανουμε typedef struct foo*{...}; ? 2. στο typedef struct foo{...}foo2; τι σχεση εχουν τα foo/foo2 τι διαφορα εχει οταν βαζουμε το foo2 και δεν το αφησουμε κενο. Ειναι καλη τακτικη να τα εχουμε και τα 2 foo? Για το 1ο δεν έχω καταλάβει τι ακριβώς ρωτάς, κατάλαβα όμως νομιζω για το 2ο. > struct Foo { ... }; Εδώ (από πάνω δλδ) Το struct Foo είναι ένας τύπος δομής. > struct Foo { ... } foo; Εδώ το struct Foo είναι ένας τύπος δομής και η foo είναι μια μεταβλητή τύπου: struct Foo. > typedef struct Foo { ... } Foo; Εδώ το struct Foo είναι ένας τύπος δομής τον οποίον για συντομία τον ορίζουμε και ως σκέτο Foo (του δημιουργούμε δηλαδή έναν alias, μια εναλλακτική γραφή). Με το παραπάνω typedef, είτε γράψουμε κατόπιν στον κώδικά μας struct Foo είτε σκέτο Foo είναι το ίδιο πράγμα. Π.χ, με το παραπάνω typedef μπορείς να ορίσεις μια μεταβλητή foo με οποιονδήποτε από τους εξής τρόπους... > typedef struct Foo { ... } Foo; ... int main( void ) { Foo foo1; // same as: struct Foo foo1 struct Foo foo2; // same as: Foo foo2; ... Για να τα ξεχωρίζεις λίγο καλύτερα, το ANSI C Coding Standard προτείνει τους τύπους να τους ορίζεις με κεφαλαίο το 1ο γράμμα, ενώ τις μεταβλητές με όλα τους τα γράμματα πεζά.
fonsde Δημοσ. 21 Νοεμβρίου 2012 Δημοσ. 21 Νοεμβρίου 2012 > typedef struct Foo { ... } *Foo; εδω ? κανω Foo x ; ο x ειναι δεικτης στην struct Foo?
imitheos Δημοσ. 21 Νοεμβρίου 2012 Δημοσ. 21 Νοεμβρίου 2012 Φιλε @imitheos ειμαι ακομα πρωταρεις.. Σημερα κιολας ειχαμε το μαθημα για τους pointers και τις δηλωσεις και ακομα δεν τα εχω εμπεδωσει καλα.. Εξου και η (προφανως βλακεια) απαντηση μου.. Για αυτό πρότεινα να διαβάσεις καλά το βιβλίο για να το εμπεδώσεις καλά . Δεν το είπα επικριτικά. Όλοι πρωτάρηδες ξεκινάνε. με μπερδευει κατι οταν κανουμε typedef struct . 1. γιατι δεν μπορουμε να κανουμε typedef struct foo*{...}; ? 2. στο typedef struct foo{...}foo2; τι σχεση εχουν τα foo/foo2 τι διαφορα εχει οταν βαζουμε το foo2 και δεν το αφησουμε κενο. Ειναι καλη τακτικη να τα εχουμε και τα 2 foo? Ας δούμε το 2 πρώτα. > 1) struct foo { ... } foo2; 2) struct { ... } foo2; Αρχικά έχουμε σκέτο struct. Η 1η έκφραση δηλώνει απλά μια δομή με όνομα foo και τάδε μέλη και έπειτα δηλώνει μια μεταβλητή με όνομα foo2. Δηλαδή είναι σαν να είχες γράψει "struct foo foo2". Η 2η έκφραση δηλώνει μια δομή χωρίς όμως όνομα τύπου και μετά δημιουργεί μια μεταβλητή με όνομα foo2. Δηλαδή έχει το ίδιο αποτέλεσμα με την 1η με την διαφορά ότι δεν μπορούμε να δηλώσουμε κάποια άλλη μεταβλητή foo3. Ας έρθουμε τώρα στο typedef το οποίο λειτουργεί διαφορετικά. Καταρχήν να πούμε ότι το typedef δημιουργεί ψευδώνυμα για τύπους και η σύνταξή του είναι "τύπος ψευδώνυμο". > typedef int myint; int mitsos; myint kotsos; Δημιουργήσαμε ένα "τύπο" με όνομα myint και έτσι μπορούμε να δηλώσουμε μεταβλητές με αυτόν τον τύπο. > 1) typedef struct foo { ... } foo2; 2) typedef struct { ... } foo2; Από την περιγραφή του typedef καταλαβαίνουμε ότι η συμπεριφορά είναι διαφορετική από ό,τι με το σκέτο struct και εδώ το foo2 δεν είναι δήλωση μεταβλητής αλλά το ψευδώνυμο που επιλέξαμε για το typedef. Το foo2 είναι ένας νέος "τύπος" ο οποίος είναι ψευδώνυμο της δομής foo. Είναι δηλαδή 2 δηλώσεις σε μία. Αφενός έχουμε τη δήλωση του σκέτου struct όπως πριν και μετά έχουμε τη δημιουργία ενός ψευδώνυμου foo2. Έτσι οι παρακάτω δηλώσεις είναι επιτρεπτές: > struct foo mitsos; foo2 kotsos; Ας δούμε τώρα το 1. Γιατί δεν επιτρέπεται το "typedef struct foo*{...}". Βγάλε από το μυαλό σου το typedef και δες σκέτη τη δήλωση. Η έκφραση "foo *" είναι σωστή ? Αν ναι, τι δηλώνει ? Αυτό που θέλεις να κάνεις φυσικά γίνεται απλά πρέπει να το γράψεις διαφορετικά ως "typedef struct foo { ... } *foo2". Όπως είπαμε πριν, έχουμε δύο δηλώσεις σε μία. Αφενός ορίζουμε μια δομή με όνομα foo και τάδε μέλη, αφετέρου δημιουργούμε ένα ψευδώνυμο foo2 το οποίο είναι δείκτης στη δομή foo. Βέβαια αυτό δεν θεωρείται καλή τακτική γιατί κρύβει στον αναγνώστη το γεγονός ότι το foo2 είναι δείκτης. Edit: Μέχρι να το γράψω με πρόλαβες
migf1 Δημοσ. 21 Νοεμβρίου 2012 Δημοσ. 21 Νοεμβρίου 2012 Όταν κάνεις τέτοια περίεργα, φρόντιζε να δίνεις περιγραφικά ονόματα, αλλιώς είναι πολύ εύκολο να χαθεί η μπάλα. > typedef struct Student { ... } Student, *PtrStudent; ... int main( void ) { Student student; PtrStudent pStudent; // same as: Student *pStudent Προσωπικά θεωρώ κακή πρακτική να κρύβουμε τους δείκτες με typedef's, αλλά θα βρεις πάαααρα πολλούς κώδικες να το κάνουν. 1
imitheos Δημοσ. 21 Νοεμβρίου 2012 Δημοσ. 21 Νοεμβρίου 2012 Προσωπικά δεν μπορώ να καταλάβω γιατί χρησιμοποιείται το typedef σε αυτές τις περιπτώσεις Το typedef έχει δόκιμες χρήσεις για να απλουστεύσει πολύπλοκες εκφράσεις (πχ function pointers), για να κρύψει πληροφορίες (ξέρει κανείς τι έχει μέσα το FILE ?), για portability όπως οι standard τύποι της C99, κτλ. Για την απλή περίπτωση μιας δομής όμως δεν προσφέρει τίποτα και καταλήγουμε και σε προβλήματα όταν χρησιμοποιείται με δείκτες όπως ανέφερε και ο migf1 και εγώ. Πόσο πιο δύσκολο είναι να γράψει κάποιος "struct foo myvar" αντί για "foo myvar". Πολύ πιο χρήσιμο πιστεύω θα ήταν αν υπήρχε κάτι σαν το WITH της pascal.
migf1 Δημοσ. 21 Νοεμβρίου 2012 Δημοσ. 21 Νοεμβρίου 2012 Εγώ το χρησιμοποιώ κατά κόρον σε απλές δομές κυρίως για να γλιτώνω μετέπειτα typing, ενώ το αποφεύγω όπως ο διάολος το λιβάνι όταν κρύβει δείκτες. Επίσης προσπαθώ να το αποφεύγω και στους δείκτες συναρτήσεων, εκτός πια αν έχω να κάνω με πραγματικά πολύπλοκο ορισμό (πράγμα σπάνιο). Όσο για το 'with' και μένα με χαλάει που δεν υπάρχει κάτι αντίστοιχο στην C... αυτό που χρησιμοποιείται συχνά ως 'with' είναι ένας τοπικός δείκτης στη δομή. Π.χ. > #define PRIVATE // void typedef struct Point { int x, y; } Point; typedef struct Rect { Point ul; // upper-left corner Point br; // bottom-right corner PRIVATE int width; PRIVATE int height; ... } Rect; ... Rect arrRect[MAX_RECTS]; ... void arrRect_recalc( Rect arrRect[] ) { Rect *r = NULL; // something like Pascal's 'with' for (int i=0; i < MAX_RECTS; i++) { r = &arrRect[i]; r->width = r->br.y - r->ul.y; r->height = r->br.x - r->ul.x; } } Χωρίς το r θα είχαμε... > void arrRect_recalc( Rect arrRect[] ) { for (int i=0; i < MAX_RECTS; i++) { arrRect[i].width = arrRect[i].br.y - arrRect[i].ul.y; arrRect[i].height = arrRect[i].br.x - arrRect[i].ul.x; } }
migf1 Δημοσ. 21 Νοεμβρίου 2012 Δημοσ. 21 Νοεμβρίου 2012 Σχετικά με τις ταξινομήσεις, θυμάμαι ο παπι έκανε παλιότερα συγκρίσεις της quick-sort μεταξύ C και C# αν θυμάμαι καλά, χρησιμοποιώντας στην C την έτοιμη qsort() της libc. Όπως είχαμε πει τότε η qsort() αφενός δεν έχει ίδιο implementation σε όλους τους compilers, κι αφετέρου η γενική της φύση (μέρος της οποίας αποτελεί και το πέρασμα της comparator function ως όρισμα) την καθιστά μη optimal. Του είχα πει τότε να βρει στο Internet μια optimized έκδοση της quick-sort για να κάνει την σύγκριση, αλλά είχε μείνει εκεί το θέμα. Οπότε τώρα που άρχισα να ασχολούμαι, παραθέτω παρακάτω 2 links με optimized υλοποιήσεις της quick-sort, ένα χωρίς recursion κι ένα με recursion. Non-recursive: http://alienryderflex.com/quicksort/ (την τελευταία εκδοχή αυτής έχω βάλει κι εγώ στο προγραμματάκι που κάνω... 3η μέρα σήμερα and we keep going ) > /// custom type for holding algorithm statistics typedef struct Stats { uint64_t nIterations; ///< # of loop iterations uint64_t nComparisons; ///< # of comparisons uint64_t nSwaps; ///< # of swaps uint64_t nRCalls; ///< # of recursive function calls struct { ///< for calculating execution time clock_t end, start; double ellapsed; } timeCpu; } Stats; ... /** * Quick Sort, Optimized version (Alien Ryder Flex) * Time Benchmark Friendly Implementation */ #define QSORT_O1_MAXLEVELS 300 bool arrInt32_sort_quickO1_bench( int32_t arrInt[], int32_t maxelems, Stats *stats ) { int32_t pivotValue; int32_t beg[QSORT_O1_MAXLEVELS], end[QSORT_O1_MAXLEVELS]; int32_t i=0, left, right; int32_t temp; // for swapping values // sanity checks if ( !arrInt || !VALID_ARRINT_LEN(maxelems) || !stats ) return false; // start timer stats->timeCpu.start = clock(); beg[0] = 0; end[0] = maxelems; while ( i >= 0 ) { left = beg[i]; right = end[i]-1; if ( left < right ) { pivotValue = arrInt[left]; while ( left < right ) { while ( arrInt[right] >= pivotValue && left < right ) right--; if ( left < right ) arrInt[left++] = arrInt[right]; while ( arrInt[left] <= pivotValue && left < right ) left++; if ( left < right ) arrInt[right--] = arrInt[left]; } arrInt[left] = pivotValue; beg[i+1] = left+1; end[i+1] = end[i]; end[i++] = left; if ( end[i]-beg[i] > end[i-1]-beg[i-1] ) { // swap beg[i] & beg[i-1] temp = beg[i]; beg[i] = beg[i-1]; beg[i-1]= temp; // swap end[i] & end[i-1] temp = end[i]; end[i] = end[i-1]; end[i-1]= temp; } } else { i--; } } // end timer stats->timeCpu.end = clock(); stats->timeCpu.ellapsed = ((double) (stats->timeCpu.end - stats->timeCpu.start)) / CLOCKS_PER_SEC; return true; } Recursive: http://www.daniweb.com/software-development/c/code/216323/optimized-quicksort-implementation# Όπως αναφέρεται και στο 2ο link, το ιδανικό είναι ο συνδυασμός περισσοτέρων του ενός αλγόριθμους, ανάλογα την περίσταση.
pmav99 Δημοσ. 21 Νοεμβρίου 2012 Δημοσ. 21 Νοεμβρίου 2012 @migf1 Αν θέλεις δες και την timsort. Είναι ο αλγόριθμός που χρησιμοποιεί η Python για sorting http://en.wikipedia.org/wiki/Timsort http://hg.python.org/cpython/file/tip/Objects/listsort.txt http://www.drmaciver.com/2010/01/understanding-timsort-1adaptive-mergesort/
migf1 Δημοσ. 21 Νοεμβρίου 2012 Δημοσ. 21 Νοεμβρίου 2012 @migf1 Αν θέλεις δες και την timsort. Είναι ο αλγόριθμός που χρησιμοποιεί η Python για sorting http://en.wikipedia.org/wiki/Timsort http://hg.python.org/cpython/file/tip/Objects/listsort.txt http://www.drmaciver.com/2010/01/understanding-timsort-1adaptive-mergesort/ Ευχαριστώ, χρήσιμο κι ενδιαφέρον! Παρόμοιας λογικής είναι και η Introspective Sort την οποία χρησιμοποιούν πολλοί C++ compilers ως υλοποίηση της std::sort. Είναι συνδυασμός quick & heap sort. Βασικά υπάρχουν πάρα πολλές ρουτίνες ταξινόμησης. Εγώ εδώ τώρα έχω μπλέξει με το μενού του προγράμματος, διότι για τη λειτουργίες που θέλω να κάνει το πρόγραμμα, βγαίνει ολόκληρο μαρκυνάρι το μενού (κοντεύω να γράψω custom GUI κώδικα διαχείρισης μενού ) Κοιτάξτε τι λέω να κάνω, θα τελειώσω με το μενού, θα τσεκάρω ξανά και τον κώδικα που μετράει iterations & comparisons, θα βάλω σχόλια και θα το ανεβάσω σε κάνα mercurial ώστε να μπορεί όποιος θέλει να προσθέσει κι άλλες ρουτίνες ταξινόμησης, απευθείας, σε κοινή ομπρέλα. Άμα έχει ενδιαφέρον, θα ψηθώ να του βάλω και x-platform GUI (δλδ GTK μιας και είναι C ή έστω Win32 API... εκτός αν θέλει κανείς άλλος ). Ποιος ξέρει, άμα ψηθούν κι άλλοι και προσθέσουν ρουτίνες ταξινόμησης μπορεί στο τέλος να βγει καμιά ωραία, ενδεχομένως και χρήσιμη (χλωμό) συλλογή από ρουτίνες ταξινόμησης με head-to-head benchmarks. Προς το παρόν, συγκριτικά με το προηγούμενο ποστ του έχω προσθέσει αυτά που πρότεινε ο imitheos, δηλαδή Random, Sorted & Reversely Sorted data set, που λειτουργούν σαν GUI radio buttons (δλδ μόνο το 1 είναι ενεργό ανά πάσα στιγμή)... Θα κάνω κάτι αντίστοιχο στο μενού και για 3 modes: Full, Times Only και Stats Only (πάλι σε στυλ radio-button). και μια μόνο Roundup εντολή, πιθανότατα κάτω από την Merge (ή όποια θα είναι τελευταία). Οπότε άμα διαλέγουμε ας πούμε Bubble, τότε ανάλογα με το ενεργό mode setting και το ενεργό data-set setting, θα τρέχει η αντίστοιχη έκδοση της bubble (full, timeonly ή stat). Ομοίως άμα διαλέγουμε Roundup, μόνο που εκεί θα τρέχει όλους τους αλγόριθμους. Από εκεί και μετά το μόνο που θα μένει θα είναι να προστίθενται αλγόριθμοι (σε 3 εκδοχές ο καθένας: full, time-only και stat-only) Αυτά τα έχω ήδη έτοιμα για τους υπάρχοντες αλγόριθμους, με το μενού ασχολούμαι τώρα.
migf1 Δημοσ. 26 Νοεμβρίου 2012 Δημοσ. 26 Νοεμβρίου 2012 >#define my_INT_MAX ( ((unsigned int)-1) >> 1 ) // or ( ((unsigned int)-1)/2 ) vs #define my_INT_MAX ~( 1 << (sizeof(int)*8-1) ) Comments?
albNik Δημοσ. 26 Νοεμβρίου 2012 Δημοσ. 26 Νοεμβρίου 2012 Στο δεύτερο για 32-bit 2^(4*8-1)=2^31 Δεν ξέρω αν ισχύει αυτό στην αναπαράσταση θετικά-αρνητικά (συμπλήρωμα προς 2). ~(2^31)==2^31-1 ΟΚ 1<<31=1000..00 ( 31 μηδενικά) ~(1<<31)=011...11 (31 άσσοι) ΕΔΙΤ Για το πρώτο λογικά το -1 είναι 11...11 (32 άσσοι)
imitheos Δημοσ. 26 Νοεμβρίου 2012 Δημοσ. 26 Νοεμβρίου 2012 > #define my_INT_MAX INT_MAX >#define my_INT_MAX ( ((unsigned int)-1) >> 1 ) // or ( ((unsigned int)-1)/2 ) vs #define my_INT_MAX ~( 1 << (sizeof(int)*8-1) ) Comments? Στο 1ο δεν βλέπω κάποιο λάθος αλλά κάτι δεν μου κάθεται καλά στο μάτι όταν το βλέπω. Ίσως έχω στο μυαλό μου κάποια περίπτωση που δεν παίζει αλλά δεν μου έρχεται στο μυαλό. Το 2ο δεν μαρέσει. Εκτός ότι το συμπλήρωμα είναι συχνά πηγή προβλημάτων, η έκφραση δεν είναι portable. Αν έχεις σκοπό να το χρησιμοποιήσεις μόνο σε "κλασικές" πλατφόρμες με 8bits char, συμπλήρωμα ως προς 2, όχι padding τότε θα παίξει τζάμι. Ακόμη και να αντικαταστήσεις το 8 με CHAR_BIT πάλι δεν θα είναι portable γιατί η έκφραση sizeof(int)*CHAR_BIT θα σου δώσει όλα τα bits που καταλαμβάνει ο int αντί για μόνο τα value bits. Αν ο τύπος χρησιμοποιεί padding θα βγάλεις μεγαλύτερη τιμή από ό,τι υποστηρίζει. Ο μόνος που γνωρίζει 100% πως υλοποιούνται οι τύποι είναι ο implementor οπότε μόνο ό,τι λέει το limits.h είναι δόκιμο. Αν όμως έπρεπε να διαλέξω οπωσδήποτε ένα από τα 2, πιστεύω θα επέλεγα το 1ο. ΕΔΙΤ Για το πρώτο λογικά το -1 είναι 11...11 (32 άσσοι) Έτσι είναι όντως αλλά να σημειώσουμε ότι στην C τα πάντα δουλεύουν με τιμές και όχι με bits. Όταν θέτουμε την τιμή -1 στον unsigned int δεν λέει ο compiler "το -1 έχει όλα τα bit 1 οπότε θα γράψω όλα τα bit 1". Αν γινόταν αυτό θα είχαμε σωστό αποτέλεσμα μόνο σε μηχανές με συμπλήρωμα ως προς 2 που το -1 έχει όντως όλα τα bit 1. Αντίθετα δουλεύει με την τιμή -1. Σε unsigned τύπους δεν γίνεται να υπάρξει overflow (ή αν θέλεις με άλλα λόγια είναι πλήρως ορισμένο τι γίνεται όταν υπάρξει) και έτσι όταν θέτουμε μια αρνητική τιμή έχουμε modulo αριθμητική με (μέγιστη τιμή + 1) μέχρι να βρούμε τιμή που υποστηρίζει ο τύπος. Έτσι το -1 θα γίνει (UINT_MAX + 1) -1 δηλαδή UINT_MAX. Ακόμη και αν το -1 αναπαρίσταται ως 100.......001 (sign+magnitude), θέτοντας -1 σε unsigned τύπο πάντα θα μας δώσει την μέγιστη τιμή που υποστηρίζει ο τύπος για αυτό και είναι ο καλύτερος και πιο portable τρόπος για αυτό.
Re4cTiV3 Δημοσ. 26 Νοεμβρίου 2012 Δημοσ. 26 Νοεμβρίου 2012 Όταν κάνω >lseek(fd, 0L, SEEK_END); γιατί μου εμφανίζει ξέρω γω οτι το αρχείο περιέχει π.χ 8 chars ενώ είναι 7γραμμένοι; είναι το \0 ;
Προτεινόμενες αναρτήσεις