Προς το περιεχόμενο

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


Shadowvault

Προτεινόμενες αναρτήσεις

Οκ ευχαριστώ και πάλι.Θα κοιτάξψ τώρα το 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 σου κατεβάζει το χρόνο αναζήτησης τουλάχιστον στον μισό.

Συνδέστε για να σχολιάσετε
Κοινοποίηση σε άλλες σελίδες

Το 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.

  • Like 1
Συνδέστε για να σχολιάσετε
Κοινοποίηση σε άλλες σελίδες

Το 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 ομολογω δε το γνωριζα :-)

Συνδέστε για να σχολιάσετε
Κοινοποίηση σε άλλες σελίδες

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

 

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

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

Συνδέστε για να σχολιάσετε
Κοινοποίηση σε άλλες σελίδες

Δημιουργήστε ένα λογαριασμό ή συνδεθείτε για να σχολιάσετε

Πρέπει να είστε μέλος για να αφήσετε σχόλιο

Δημιουργία λογαριασμού

Εγγραφείτε με νέο λογαριασμό στην κοινότητα μας. Είναι πανεύκολο!

Δημιουργία νέου λογαριασμού

Σύνδεση

Έχετε ήδη λογαριασμό; Συνδεθείτε εδώ.

Συνδεθείτε τώρα
  • Δημιουργία νέου...