DOUG LLOYD: Έτσι σε CS50, καλύψαμε πολλές διαφορετικές δομές δεδομένων, έτσι δεν είναι; Έχουμε δει συστοιχίες, και συνδέεται λίστες και πίνακες κατακερματισμού, και προσπαθεί, στοίβες και ουρές. Επίσης, θα μάθετε λίγο σχετικά με τα δέντρα και τους σωρούς, αλλά πραγματικά όλα αυτά μόλις τελειώσει να είναι παραλλαγές σε ένα θέμα. Πραγματικά υπάρχουν αυτά το είδος των τεσσάρων βασικών ιδεών ότι ό, τι άλλο μπορεί να συνοψίζεται σε. Πίνακες, συνδεδεμένες λίστες, hash πίνακες, και προσπαθεί. Και όπως είπα, υπάρχει είναι παραλλαγές τους, αλλά αυτό είναι αρκετά πολύ θα συνοψίσω ό, τι θα πάμε να μιλήσουμε περίπου σε αυτή την κατηγορία από την άποψη του C. Αλλά πώς το κάνουμε όλα αυτά πράξη επάνω, δεξιά; Έχουμε μιλήσει για τα πλεονεκτήματα και τα μειονεκτήματα καθενός ξεχωριστά σε βίντεο τους, αλλά υπάρχει πολλή αριθμούς να πάρει ρίχνονται γύρω. Υπάρχουν πολλές γενικές σκέψεις να πάρει ρίχνονται γύρω. Ας προσπαθήσουμε και να ενοποιήσει το σε ένα μόνο μέρος. Ας σταθμίσει τα υπέρ έναντι Τα μειονεκτήματα, και να εξετάσει η οποία δομή δεδομένων θα μπορούσε να είναι η σωστή δεδομένων δομή για την περίπτωσή σας, Ανεξάρτητα από το είδος των δεδομένων που θέλετε να αποθηκεύσετε. Δεν χρειάζεται απαραιτήτως πρέπει πάντα να χρησιμοποιήστε το σούπερ γρήγορη εισαγωγή, διαγραφή, και αναζήτηση ενός trie αν πραγματικά Δεν με νοιάζει για την εισαγωγή και τη διαγραφή πάρα πολύ. Αν το μόνο που χρειάζεται γρήγορα τυχαία πρόσβασης, ίσως ένας πίνακας είναι καλύτερη. Ας απόσταξη αυτό. Ας μιλήσουμε για καθένα από τα τέσσερα μείζονα είδη δομών δεδομένων ότι έχουμε μιλήσει, και απλά δείτε όταν θα μπορούσαν να είναι καλό, και όταν μπορεί να μην είναι τόσο καλή. Ας ξεκινήσουμε με συστοιχίες. Έτσι εισαγωγής, αυτό είναι το είδος των κακών. 

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

Ομοίως, διαγραφή, εκτός και αν είμαστε διαγραφή από το τέλος μιας συστοιχίας, Είναι πιθανόν επίσης δεν είναι τόσο μεγάλη, αν δεν θέλουμε να αφήσετε κενά κενά, η οποία συνήθως δεν το κάνουμε. Θέλουμε να καταργήσετε ένα στοιχείο, και τότε το είδος του καθιστούν άνετη και πάλι. Και έτσι από τη διαγραφή στοιχείων ένας πίνακας, επίσης, δεν είναι τόσο μεγάλη. 

Αναζήτηση, όμως, είναι μεγάλη. Έχουμε τυχαίας προσπέλασης, συνεχής αναζήτηση του χρόνου. Θα πω μόνο επτά, και πάμε σε σειρά μετεγκατάσταση επτά. Λέμε 20, με πηγαίνετε στο μετεγκατάσταση πίνακα 20. Δεν έχουμε να επαναλάβει ολόκληρη. Αυτό είναι πολύ καλό. 

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

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

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

Με μια συνδεδεμένη λίστα, εισαγωγής είναι αρκετά εύκολο. Εμείς απλά καρφί στο μπροστινό. Η διαγραφή είναι επίσης αρκετά εύκολο. Πρέπει να βρούμε τα στοιχεία. Αυτό συνεπάγεται κάποια έρευνα. 

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

Αναζήτηση είναι κακό όμως, σωστά; Για να μπορέσουμε να βρούμε μια στοιχείο σε μια συνδεδεμένη λίστα, είτε μεμονωμένα είτε διπλά συνδεδεμένες, θα πρέπει να είναι γραμμική αναζήτηση. Πρέπει να ξεκινήσουμε από την αρχή και μετακινήστε το τέλος, ή να αρχίσει στο τέλος κίνηση στην αρχή. Δεν έχουμε πια τυχαίας προσπέλασης. Έτσι, αν κάνουμε μια πολλή αναζήτηση, ίσως μια συνδεδεμένη λίστα δεν είναι είναι και τόσο καλό για εμάς. 

Είναι επίσης πολύ δύσκολο να ταξινομήσετε, σωστά; Ο μόνος τρόπος για να πραγματικά ταξινομήσετε μια συνδεδεμένη λίστα είναι να ταξινομήσετε όπως εσείς να το κατασκευάσει. Αλλά αν το ταξινομήσετε όπως εσείς την κατασκευή τους, δεν είστε πλέον κάνοντας γρήγορη ενθέσεις πια. Δεν είστε μόνο στερέωση πράγματα πάνω στο μέτωπο. Θα πρέπει να βρείτε το σωστό σημείο για να το θέσω, και στη συνέχεια την εισαγωγή σας γίνεται σχεδόν τόσο κακή ως εισαγωγή σε μια σειρά. Έτσι, συνδεδεμένες λίστες δεν είναι τόσο μεγάλη για την ταξινόμηση των δεδομένων. 

Είναι επίσης αρκετά μικρό, το μέγεθος-σοφός. Διπλά συνδεδεμένη λίστα ελαφρώς μεγαλύτερο από μεμονωμένα συνδεδεμένες λίστες, η οποία είναι ελαφρώς μεγαλύτερα από συστοιχίες, αλλά δεν είναι ένα τεράστιο ποσό των σπατάλη χώρου. Έτσι, αν το διάστημα είναι σε ένα ασφάλιστρο, αλλά δεν είναι μια πραγματικά έντονη πριμοδότηση, αυτό θα μπορούσε να είναι ο σωστός τρόπος να πάει. 

Hash πίνακες. Εισαγωγή σε έναν πίνακα κατακερματισμού είναι αρκετά απλή. Είναι μια διαδικασία δύο σταδίων. Πρώτα πρέπει να τρέχει μέσα από τα δεδομένα μας μια συνάρτηση κατακερματισμού για να πάρετε έναν κωδικό κατακερματισμού, και στη συνέχεια εισάγουμε το στοιχείο σε ο hash πίνακα στη συγκεκριμένη τοποθεσία κωδικό κατακερματισμού. 

Διαγραφή, παρόμοια με συνδεδεμένη λίστα, Είναι εύκολο μόλις βρείτε το στοιχείο. Θα πρέπει να το βρουν την πρώτη, αλλά στη συνέχεια, όταν το διαγράψετε, το μόνο που χρειάζεται να ανταλλάσσουν ένα ζευγάρι των δεικτών, αν χρησιμοποιείτε Ξεχωριστές αλυσίδες. Εάν χρησιμοποιείτε την ανίχνευση, ή αν δεν είστε χρησιμοποιώντας την αλυσιδωτή σύνδεση σε όλα στον πίνακα κατακερματισμού σας, διαγραφή είναι πραγματικά πολύ εύκολο. Το μόνο που χρειάζεται να κάνετε είναι να το hash δεδομένων, και στη συνέχεια να πάμε σε αυτήν τη θέση. Και με την προϋπόθεση να μην κάνετε έχετε οποιεσδήποτε συγκρούσεις, θα είστε σε θέση να διαγράψετε πολύ γρήγορα. 

Τώρα, αναζήτηση είναι όπου τα πράγματα πάρετε μια λίγο πιο περίπλοκη. Είναι κατά μέσο όρο καλύτερη από συνδεδεμένες λίστες. Εάν χρησιμοποιείτε αλυσιδωτή σύνδεση, έχετε ακόμα μια συνδεδεμένη λίστα, πράγμα που σημαίνει ότι έχετε ακόμα το αναζήτηση ζημιώνει μια συνδεδεμένη λίστα. Αλλά επειδή παίρνετε συνδέονται σας κατάλογο και διάσπαση πάνω από 100 ή 1.000 ή n στοιχεία στον πίνακα κατακερματισμού σας, είστε συνδεδεμένες λίστες είναι όλα μια νιοστή το μέγεθος. Είναι όλα σημαντικά μικρότερα. Έχετε n συνδεδεμένες λίστες, αντί μιας συνδεδεμένης λίστας μεγέθους n. 

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

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

Και προσπαθεί είναι η τέταρτη αυτών των δομών ότι έχουμε μιλήσει. Τοποθέτηση σε trie είναι πολύπλοκη. Υπάρχει μια πολύ δυναμική κατανομή μνήμης, ειδικά στην αρχή, καθώς ξεκινάτε να οικοδομήσουμε. Αλλά είναι σταθερά χρόνου. Είναι μόνο το ανθρώπινο στοιχείο Εδώ που το καθιστά δύσκολο. Έχοντας να αντιμετωπίσουν κενό δείκτη, malloc χώρο, πηγαίνετε εκεί, ενδεχομένως malloc χώρο Από εκεί και πάλι. Το είδος του παράγοντα εκφοβισμό δείκτες στη δυναμική κατανομή μνήμης είναι το εμπόδιο για να καθαρίσει. Αλλά από τη στιγμή που θα έχετε καθαριστεί, εισαγωγή στην πραγματικότητα έρχεται αρκετά απλή, και σίγουρα είναι σταθερά χρόνου. 

Η διαγραφή είναι εύκολο. Το μόνο που χρειάζεται να κάνετε είναι να περιηγηθείτε κάτω από ένα ζευγάρι των δεικτών και δωρεάν κόμβο, έτσι ώστε να είναι αρκετά καλή. Αναζήτηση είναι επίσης αρκετά γρήγορα. Είναι βασισμένο μόνο σχετικά με την το μήκος των δεδομένων σας. Έτσι, αν όλα τα δεδομένα σας είναι πέντε σειρές χαρακτήρα, για παράδειγμα, είστε αποθήκευση πέντε στοιχειοσειρές στο Trie σας, διαρκεί μόνο πέντε βήματα για να βρείτε αυτό που ψάχνετε. Πέντε είναι απλά ένας σταθερός παράγοντας, έτσι πάλι, εισαγωγή, διαγραφή και αναζήτηση εδώ είναι όλα σταθερά χρόνου, αποτελεσματικά. 

Ένα άλλο πράγμα είναι ότι είναι trie σας πραγματικά το είδος των ήδη διευθετηθεί, έτσι δεν είναι; Δυνάμει του πώς είμαστε εισαγωγή στοιχείων, πηγαίνοντας επιστολή με την επιστολή της κλειδί, ή κατά ψηφίο του κλειδιού, τυπικά, trie σας καταλήγει να είναι είδος ταξινομημένο ως το φτιάξεις. Δεν κάνει πραγματικά λογικό να σκεφτούμε διαλογής με τον ίδιο τρόπο που σκεφτόμαστε για με συστοιχίες, ή συνδεδεμένες λίστες, ή πίνακες κατακερματισμού. Αλλά κατά κάποιο τρόπο, σας trie ταξινομούνται as you go. 

Το μειονέκτημα, βέβαια, είναι ότι η α trie γρήγορα γίνεται τεράστια. Από κάθε σημείο σύνδεσης, ίσως have-- αν το κλειδί σας αποτελείται από ψηφία, έχετε 10 άλλους μέρη που μπορείτε να πάτε, η οποία σημαίνει ότι κάθε κόμβος Περιέχει πληροφορίες σχετικά με τα δεδομένα που θέλετε να αποθηκεύσετε σε αυτόν τον κόμβο, καθώς και 10 δείκτες. Η οποία, σε CS50 IDE, είναι 80 bytes. Έτσι είναι τουλάχιστον 80 byte για κάθε κόμβος που δημιουργείτε, και ότι δεν είναι καν καταμέτρηση δεδομένων. Και αν οι κόμβοι σας γράμματα αντί ψηφία, τώρα έχετε 26 δείκτες από κάθε τοποθεσία. Και 26 φορές 8 είναι κατά πάσα πιθανότητα 200 bytes, ή κάτι τέτοιο. Και έχετε κεφαλαίων και μπορείτε να lowercase-- δείτε πού πάω με αυτό, έτσι δεν είναι; Κόμβους σας μπορεί να πάρει πραγματικά μεγάλο, και έτσι η trie η ίδια, συνολικά, μπορεί να να πάρει πραγματικά μεγάλο, πάρα πολύ. Έτσι, αν το διάστημα είναι σε υψηλό premium στο σύστημά σας, α trie μπορεί να μην είναι ο σωστός τρόπος για να πάει, ακόμα κι αν άλλα οφέλη μπαίνουν στο παιχνίδι. Είμαι ο Νταγκ Lloyd. Αυτό είναι CS50.