Πρόβλημα με λίστες σε C

[Shadowvault]

Οκ ευχαριστώ και πάλι.Θα κοιτάξψ τώρα το link

[migf1]

Οκ ευχαριστώ και πάλι.Θα κοιτάξψ τώρα το link

Παρακαλώ, καλή συνέχεια.

 

Ναι εργασία και μας περιορίζουν πολύ.Κανουμε τραγικά πράγματα μόνο και μόνο για να δούμε πως δουλεύουν.Έτσι το πήγα και εγώ,κάθε φορα που βάζω κάτι στη λίστα πρεπει να κάνω συνέχεια αναζήτηση.Δεν υπάρχει κατι πιο αποτελεσματικό ε?Τώρα στην αναζήτηση εκανα κάτι του στιλ for (curr=head;strcmp(newnode->name,curr->name)<0;curr=curr->nxt);

Υπάρχουν διάφορα, όπως για παράδειγμα να κρατάς 3 έξτρα δείκτες: head, tail και mid στην αρχή, στο τέλος και στη μέση της ταξινομημένης λίστας σου. Ο mid θα μπορούσε να είναι είτε στην απόλυτη μέση της λίστας είτε σε κάποιο σημείο μετά ή πριν από το οποίο αναμένεις περισσότερα insertions, είτε στον τελευταίο κόμβο που εισήγαγες.

 

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

 

Μια πιο απλή παραλλαγή του παραπάνω είναι να έχεις μόνο head και tail δείκτες (στην αρχή και στο τέλος της ταξινομημένης σου λίστας) και πριν εισαγάγεις έναν νέο κόμβο, να αρχίσεις να "κουνάς" ταυτόχρονα τους head & tail προς την μέση της λίστας. Όποιος βρει πρώτος τη θέση που πρέπει να μπει ο νέος κόμβος, σου την επιστρέφει και βάζεις εκεί τον νέο κόμβο σου.

 

Guarantee σου κατεβάζει το χρόνο αναζήτησης τουλάχιστον στον μισό.

[FarCry]

http://debugmode.net/2010/09/18/inserting-element-in-sorted-generic-list-list-using-binary-search/

[migf1]

http://debugmode.net/2010/09/18/inserting-element-in-sorted-generic-list-list-using-binary-search/

Το binary search προϋποθέτει random access για να είναι efficient, και οι λίστες δεν είναι random access data-structures. Το link που παραθέτεις αναφέρεται σε C# χρησιμοποιώντας την κλάση List<T>, η οποία εσωτερικά υλοποιείται ως array (άρα random access). Χώρια ότι σου παρέχει έτοιμη μέθοδο BinarySearch.

 

Αν θες να κάνεις binary search σε linked list, μπορείς υπό κάποιες προυποθέσεις (π.χ: http://en.wikipedia.org/wiki/Skip_list ή http://algo-faq.com/Searching/Implement-binary-search-in-Linked-list.php) αλλά δεν είναι ούτε trivial ούτε πάντα efficient.

[FarCry]

Το binary search προϋποθέτει random access για να είναι efficient, και οι λίστες δεν είναι random access data-structures. Το link που παραθέτεις αναφέρεται σε C# χρησιμοποιώντας την κλάση List<T>, η οποία εσωτερικά υλοποιείται ως array (άρα random access). Χώρια ότι σου παρέχει έτοιμη μέθοδο BinarySearch.

 

Αν θες να κάνεις binary search σε linked list, μπορείς υπό κάποιες προυποθέσεις (π.χ: http://en.wikipedia.org/wiki/Skip_list ή http://algo-faq.com/Searching/Implement-binary-search-in-Linked-list.php) αλλά δεν είναι ούτε trivial ούτε πάντα efficient.

 

 

α δε το γνωριζα αυτο για την C#. καλη φαση παντως

 

το skip list ομολογω δε το γνωριζα

[migf1]

α δε το γνωριζα αυτο για την C#. καλη φαση παντως

 

το skip list ομολογω δε το γνωριζα

Υπάρχουν υπερ και κατά μεταξύ λιστών και πινάκων. Για γενικές υλοποιήσεις κλασέων, templates, κλπ, που πραγματεύονται λίστες συνήθως εξυπηρετεί καλύτερα να υλοποιηθούν ως πίνακες (για να καλύπτουν ευρύτερες ανάγκες). Οι περισσότερες από αυτές τις υλοποιήσεις χρησιμοποιούν dynamically re-allocated arrays, σε μια προσπάθεια να παντρέψουν τα πλεονεκτήματα των εναλλακτικών σε μια, και για να μετριάσουν τα μειονεκτήματα της κάθε εναλλακτικής συχνά χρησιμοποιούν κι άλλα, έξτρα data-structures.