Struct και stack

[migf1]

Αν δεν βρεί όμως διαθέσιμη συνεχόμενη μνήμη;

Αν δεν βρει συνεχόμενη μνήμη θα πρέπει να το "πιάνεις" στον κώδικά σου και να πράττεις ανάλογα (είτε να σταματάς, είτε να μικραίνεις το αιτούμενο μέγεθος και να ξανα-προσπαθείς, είτε οτιδήποτε άλλο θεωρείς απαραίτητο για τις ανάγκες της εφαρμογής σου). Στην ίδια δηλαδή λογική των λιστών αν αποτύχει το malloc() ενός κόμβου.

 

Οι λίστες έχουν το καλό, οτι θα πάρουν από όπου να ναι και εκτός αυτού μπορούν στην μια περίπτωση να αποθηκεύσουν έναν int και μετά κάποιο string.

Και με πίνακες μπορείς να το κάνεις αυτό, απλά αντί να έχεις τα στοιχεία τους ορισμένα ως Node τα έχεις δείκτες σε Node (*Node)...

 

>
Node *array[ MAX_ELEMENTS];

και προσαρμόζεις αντίστοιχα τον κώδικά σου ώστε αν το εκάστοτε array είναι NULL να το κάνει πρώτα malloc...

 

>
...
if ( NULL == array[i] && NULL == (array[i] = malloc( sizeof(Node) )  )
       	// handle failure here
(array[i])->value = value;
(array[i])->coefficient = coefficient;
...

 

Ανεξάρτητα όμως από το παραπάνω, το να έχεις ετερογενείς κόμβους δεν είναι trivial. Λίγο παλιότερα είχα φτιάξει ένα τέτοιο interface για μια Αμερικάνικη εταιρεία και είχαμε κάνει μια σχετική συζήτηση εδώ στο φόρουμ: http://www.insomnia....3%CE%B5-ansi-c/

 

 

Τελικά το δέχτηκαν

 

EDIT:

 

Διόρθωσα τη σύνταξη των array. σε (array)->

[defacer]

Αν δεν βρεί όμως διαθέσιμη συνεχόμενη μνήμη; Οι λίστες έχουν το καλό, οτι θα πάρουν από όπου να ναι και εκτός αυτού μπορούν στην μια περίπτωση να αποθηκεύσουν έναν int και μετά κάποιο string.

 

Όπως βασικά είπε και ο migf1: Αν θέλοντας να κάνεις allocate ένα κόμβο ακόμα στη λίστα σου δε βρει μνήμη; Το ίδιο πράγμα είναι (μην ακούσω τίποτα του στυλ "ναι αλλά πιο εύκολα να συμβεί το ένα παρά το άλλο" -- ή το πρόγραμμα έχει σοβαρά bugs ή δεν έχει).

[Re4cTiV3]

migf1 ενδιαφέρον,δεν το 'ξερα!Τότε γιατί μαθαίνουμε ότι σε έναν πίνακα αποθηκεύονται ίδια στοιχεία;

 

(μην ακούσω τίποτα του στυλ "ναι αλλά πιο εύκολα να συμβεί το ένα παρά το άλλο" -- ή το πρόγραμμα έχει σοβαρά bugs ή δεν έχει).

[migf1]

Σε γενικές γραμμές αν ξέρεις εκ των προτέρων το μέγιστο μήκος της λίστας σου και είναι κάποιο λογικό μέγεθος και ταυτόχρονα δεν σε νοιάζει η μνήμη, οι πίνακες είναι προτιμότεροι γιατί κάνεις άμεσο indexing στο i-οστό στοιχείο τους ανά πάσα στιγμή O(1). Αυτό είναι και το key-feature των hash-tables.

 

Επίσης είναι πολύ πιο απλός ο κώδικας (ειδικά αν προσπαθείς να "προσομοιώσεις" Ο(1) ταχύτερο* indexing με λίστες, που κι αυτό γίνεται αλλά με κόστος χρόνου αρχικοποίησης και πολυπλοκότητας κώδικα).

 

Υπάρχουν όμως κι άλλοι πολλοί παράγοντες για να αποφασίσει κανείς πόσες και τι είδους δομές θα χρησιμοποιήσει στην υλοποίηση του όποιου προβλήματος. Για παράδειγμα αν υπερτερεί η ανάγκη ταχύτερων ταξινομημένων εισαγωγών στη λίστα, τότε οι linked-lists έχουν σαφέστατο πλεονέκτημα έναντι των πινάκων.

 

----

* Πω πω, δεν είναι να κάνεις typos σε δημοφιλή φόρουμ... έχει ήδη αναπαραχθεί σε 3 παραθέσεις

Επεξ/σία 5 Ιουνίου 2012 από migf1

[Re4cTiV3]

 

Ασκήσεις πάνω σε δομές θα ξεκινήσω το καλοκαίρι στον ελεύθερο χρόνο.Αν προγραμματίζεις για δομές δεδομένων, πιστεύω μαθαίνεις και καλύτερα την γλώσσα που γράφεις, οπότε δυο σε ένα

 

Θα ψάξω κανένα site με data structure exercises.ξέρετε κανένα;

Συμφωνείτε σε αυτό που λεω;Ξέρετε κανένα site?

 

Σε γενικές γραμμές αν ξέρεις εκ των προτέρων το μέγιστο μήκος της λίστας σου και είναι κάποιο λογικό μέγεθος και ταυτόχρονα δεν σε νοιάζει η μνήμη, οι πίνακες είναι προτιμότεροι γιατί κάνεις άμεσο indexing στο i-οστό στοιχείο τους ανά πάσα στιγμή O(1). Αυτό είναι και το key-feature των hash-tables.

 

Επίσης είναι πολύ πιο απλός ο κώδικας (ειδικά αν προσπαθείς να "προσομοιώσεις" Ο(1) indexing με λίστες, που κι αυτό γίνεται αλλά με κόστος χρόνου αρχικοποίησης και πολυπλοκότητας κώδικα).

 

Υπάρχουν όμως κι άλλοι πολλοί παράγοντες για να αποφασίσει κανείς πόσες και τι είδους δομές θα χρησιμοποιήσει στην υλοποίηση του όποιου προβλήματος. Για παράδειγμα αν υπερτερεί η ανάγκη ταχύτερων ταξινομημένων εισαγωγών στη λίστα, τότε οι linked-lists έχουν σαφέστατο πλεονέκτημα έναντι των πινάκων.

Ναι αλλά για βρεις στην λίστα που είναι το στοιχείο άστα να πάνε ειδικά αν είναι προτελευταίο ή τελευταίο.Πιστεύω καλύτερη δομή είναι τα δένδρα.

[migf1]

Συμφωνείτε σε αυτό που λεω;Ξέρετε κανένα site?

Για μένα το καλύτερο είναι να βρεις κάποιο βιβλίο (κατά προτίμηση αγγλικό) εισαγωγικό σε Data Structures & Algorithms. Αυτά που ξέρω/έχω/'έμαθα από' εγώ είναι πολύ παλιά και κακογραμμένα σύμφωνα με τα σημερινά στάνταρ.

 

 

Ναι αλλά για βρεις στην λίστα που είναι το στοιχείο άστα να πάνε ειδικά αν είναι προτελευταίο ή τελευταίο.Πιστεύω καλύτερη δομή είναι τα δένδρα.

Όπως έγραψα και πριν υπάρχουν διάφοροι τρόποι και δομές που επισπεύδουν σημαντικά το indexing και σε λίστες, αλλά με κόστος στην πολυπλοκότητα του κώδικα και τον χρόνο αρχικοποίησης. Δες για παράδειγμα την skip list: http://en.wikipedia....wiki/Skip_list.

 

Μια πολύ πιο απλή (αλλά συνάμα και πολύ πιο απλοϊκή) προσέγγιση είναι να διατηρείς 2ο δείκτη στην ουρά μιας doubly-linked list. Αν η τιμή που ψάχνεις είναι μεγαλύτερη από τη μέση τιμή όλων των κόμβων, ξεκινάς το parsing από το τέλος της λίστας αντί από την αρχή της.

 

Γενικώς, το καλύτερο από όλα για μένα είναι να αναζητήσεις ένα σχετικό βιβλίο

Επεξ/σία 5 Ιουνίου 2012 από migf1

[migf1]

migf1 ενδιαφέρον,δεν το 'ξερα!Τότε γιατί μαθαίνουμε ότι σε έναν πίνακα αποθηκεύονται ίδια στοιχεία;

Ίδια στοιχεία έχεις και πάλι. Αλλά είναι δείκτες.

[defacer]

Σε γενικές γραμμές αν ξέρεις εκ των προτέρων το μέγιστο μήκος της λίστας σου και είναι κάποιο λογικό μέγεθος και ταυτόχρονα δεν σε νοιάζει η μνήμη, οι πίνακες είναι προτιμότεροι γιατί κάνεις άμεσο indexing στο i-οστό στοιχείο τους ανά πάσα στιγμή O(1). Αυτό είναι και το key-feature των hash-tables.

 

Δεν είμαι σίγουρος τι εννοείς εδώ (βασικά με έστειλε το ότι μιλάμε για πίνακες και μετά στο τέλος εμφανίζεται bonus ο hashtable που δεν έχει ξανα-αναφερθεί).

 

Το βασικό πλεονέκτημα των hashtables είναι ότι γενικά μιλώντας έχεις O(1) find -- όχι indexing όπως στους πίνακες. Διευκρινίζω γιατί μπορεί κάποιος άλλος να μπερδευτεί περισσότερο απο μένα όταν το διαβάσει.

 

Επίσης είναι πολύ πιο απλός ο κώδικας (ειδικά αν προσπαθείς να "προσομοιώσεις" Ο(1) indexing με λίστες, που κι αυτό γίνεται αλλά με κόστος χρόνου αρχικοποίησης και πολυπλοκότητας κώδικα).

 

O(1) indexing σε λίστα??? Μας βλέπουν και παιδιά ρε συ...

[migf1]

Δεν είμαι σίγουρος τι εννοείς εδώ (βασικά με έστειλε το ότι μιλάμε για πίνακες και μετά στο τέλος εμφανίζεται bonus ο hashtable που δεν έχει ξανα-αναφερθεί).

 

Το βασικό πλεονέκτημα των hashtables είναι ότι γενικά μιλώντας έχεις O(1) find -- όχι indexing όπως στους πίνακες. Διευκρινίζω γιατί μπορεί κάποιος άλλος να μπερδευτεί περισσότερο απο μένα όταν το διαβάσει.

Εννοώ πως όλη η ιδέα του hashtable στηρίζεται στο ότι οι πίνακες γίνονται indexed σε O(1) (το ίδιο πράγμα είναι το indexing με το find σε αυτό το context)

 

O(1) indexing σε λίστα??? Μας βλέπουν και παιδιά ρε συ...

Ουπς, αυτό είναι δικό μου typo!!!!!!

Πάω να το διορθώσω (αυτά παθαίνει κανείς αν γράφει σε 200 νήματα )