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

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

Και πάλι, pset6 είναι ορθογραφικά λάθη, το chipset αυτής της εβδομάδας. Και αυτό θα ενθαρρύνει επίσης, και εγώ Σας ενθαρρύνουμε, να χρησιμοποιήσετε κάποιο άλλο πόρους ειδικά για αυτό το chipset. Ειδικότερα, τα τρία έχω που αναφέρονται στην οθόνη - gdb, το οποίο έχουμε εξοικειωθεί με και έχουν χρησιμοποιήσει για μια στιγμή τώρα, είναι πρόκειται να είναι πολύ χρήσιμη αυτή την εβδομάδα. Έτσι έβαλα ότι μέχρι εδώ. Αλλά κάθε φορά που εργάζεστε με C, θα πρέπει πάντα να χρησιμοποιείτε gdb για να debug τα προγράμματά σας. Αυτή την εβδομάδα επίσης Valgrind. Ξέρει κανείς τι valgrind κάνει; 

ΚΟΙΝΟ: Ελέγχει για διαρροές μνήμης; 

JASON Hirschhorn: Valgrind ελέγχους για διαρροές μνήμης. Έτσι, αν malloc κάτι που σου πρόγραμμα, ζητάς για τη μνήμη. Στο τέλος του προγράμματός σας, έχετε να γράψει ελεύθερα σε ό, τι έχετε malloced για να δώσει τη μνήμη πίσω. Αν δεν γράψετε ελεύθερο στο τέλος και το πρόγραμμά σας έρχεται σε ένα συμπέρασμα, τα πάντα αυτόματα θα να απελευθερωθεί. Και για τα μικρά προγράμματα, είναι δεν είναι ότι μεγάλη μια διαπραγμάτευση. Αλλά αν είστε γραπτώς μια μεγαλύτερη λειτουργία πρόγραμμα που δεν κλείνει, κατ 'ανάγκην, σε λίγα λεπτά ή λίγα δευτερόλεπτα, στη συνέχεια, τη μνήμη διαρροές μπορεί να γίνει μια τεράστια συμφωνία. 

Έτσι, για pset6, η προσδοκία είναι ότι θα έχετε μηδέν διαρροές μνήμης με το πρόγραμμά σας. Για να ελέγξετε για διαρροές μνήμης, εκτελέστε valgrind και αυτό θα σας δώσει κάποια ωραία εξόδου επιτρέποντάς σας να γνωρίζετε αν ή δεν ήταν όλα δωρεάν. Θα εξασκηθείτε με αυτό αργότερα σήμερα, ελπίζω. 

Τέλος, η εντολή diff. Θα χρησιμοποιηθεί για κάτι παρόμοιο με αυτό σε pset5 με το εργαλείο ματιά. Επέτρεψε να κοιτάξουμε μέσα. Θα χρησιμοποιηθεί επίσης diff, επίσης, ανά το πρόβλημα που spec. Αλλά σε σας τη δυνατότητα να συγκρίνετε δύο αρχεία. Μπορείτε να συγκρίνετε το αρχείο bitmap και info κεφαλίδες ενός διαλύματος προσωπικού και λύση σας σε pset5 εάν επιλέξατε να το χρησιμοποιήσετε. Diff θα σας επιτρέψει να το κάνουμε αυτό, καθώς και. Μπορείτε να συγκρίνετε τη σωστή απάντηση για πρόβλημα αυτής της εβδομάδας που την απάντησή σας και να δούμε αν γραμμών πάνω ή προς τα δείτε όπου τα σφάλματα είναι. 

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

Γι 'αυτό και πρόκειται να δαπανήσει το μεγαλύτερο μέρος των τμήμα, όπως ανέφερα, μιλάμε για συνδεδεμένες λίστες και πίνακες κατακερματισμού, η οποία θα είναι άμεσα εφαρμοστέες στην πρόβλημα που αυτή την εβδομάδα. Συνδεδεμένες λίστες θα πάμε σε σχετικά γρήγορα επειδή έχουμε περάσει μια δίκαιη λίγο του χρόνου πηγαίνει πέρα ​​από αυτό το σημείο. Και έτσι θα πάρετε κατ 'ευθείαν στο κωδικοποίησης προβλήματα για συνδεδεμένες λίστες. Και στη συνέχεια, στο τέλος θα μιλήσουμε για hash πίνακες και πώς εφαρμόζεται σε αυτό πρόβλημα που τίθεται εβδομάδας. 

Έχετε δει αυτόν τον κώδικα πριν. Αυτό είναι ένα struct, και αυτό είναι ο καθορισμός κάτι νέο ονομάζεται κόμβος. Και μέσα σε ένα κόμβο υπάρχει ένας ακέραιος εδώ και υπάρχει ένας δείκτης σε ένα άλλο κόμβο. Το έχουμε δει αυτό πριν. Αυτό έχει να ανεβαίνει για μια-δυο εβδομάδες τώρα. Συνδυάζει δείκτες, που έχουμε ήδη σε συνεργασία με, και structs, οι οποίες επιτρέπουν μας να συνδυάσει δύο διαφορετικά τα πράγματα σε έναν τύπο δεδομένων. 

Υπάρχει μια παρτίδα σε εξέλιξη στην οθόνη. Αλλά όλοι θα πρέπει να είναι σχετικά εξοικειωμένος με σας. Από την πρώτη γραμμή, δηλώνουν ένα νέο κόμβο. Και στη συνέχεια, μέσα σε αυτό το νέο κόμβο, μπορώ να ορίσω ο ακέραιος στην εν λόγω κόμβο προς ένα. Βλέπουμε στην επόμενη γραμμή κάνω μια printf εντολή, αλλά έχω σκιασμένα η εντολή printf διότι η πραγματικά σημαντικό μέρος είναι αυτή η γραμμή εδώ - new_node.n. Τι σημαίνει η τελεία σημαίνει; 

ΚΟΙΝΟ: Πηγαίνετε στον κόμβο και εκτιμήσει την αξία n για αυτό. 

JASON Hirschhorn: Αυτό είναι ακριβώς δεξιά. Dot σημαίνει μεταβείτε στον n μέρος αυτού του νέου κόμβου. Αυτή η επόμενη γραμμή κάνει τι; Michael. 

ΚΟΙΝΟ: Δημιουργεί ένα άλλο κόμβο που θα οδηγεί στο νέο κόμβο. 

JASON Hirschhorn: Γι 'αυτό δεν δημιουργήσετε ένα νέο κόμβο. Δημιουργεί ένα τι; 

ΚΟΙΝΟ: Ένας δείκτης. 

JASON Hirschhorn: Ένας δείκτης σε κόμβο, όπως υποδεικνύεται από αυτόν τον κόμβο * εδώ. Έτσι ώστε να δημιουργεί ένα δείκτη σε έναν κόμβο. Και το οποίο ο κόμβος είναι αυτό που δείχνει να, Μάικλ; 

ΚΟΙΝΟ: Νέος κόμβος; 

JASON Hirschhorn: Νέος κόμβος. Και αυτό δείχνει εκεί, γιατί έχουμε έδωσε την διεύθυνση του νέου κόμβου. Και τώρα σε αυτή τη γραμμή βλέπουμε δύο διαφορετικούς τρόπους εκφράζουν το ίδιο πράγμα. Και θα ήθελα να επισημάνω πως αυτές δύο πράγματα είναι τα ίδια. Στην πρώτη γραμμή, Αποαναφορά ο δείκτης. Έτσι πάμε στον κόμβο. Αυτό είναι ό, τι σημαίνει αυτό το αστέρι. Έχουμε δει ότι πριν με δείκτες. Πηγαίνετε σε αυτόν τον κόμβο. Αυτό είναι σε παρενθέσεις. Και στη συνέχεια να έχουν πρόσβαση μέσω του τελεστή τελεία το ν στοιχείο αυτού του κόμβου. 

Έτσι ώστε να παίρνει τη σύνταξη είδαμε εδώ και τώρα χρήση με ένα δείκτη. Φυσικά, παίρνει το είδος της απασχολημένος αν είστε γραπτώς αυτές τις παρενθέσεις - Αυτό το αστέρι και η τελεία. Παίρνει λίγο απασχολημένος. Έτσι έχουμε κάποια συντακτική ζάχαρη. Και αυτή η γραμμή ακριβώς εδώ - ptr_node-> n. Αυτό κάνει το ίδιο ακριβώς πράγμα. Έτσι, οι δύο αυτές γραμμές κώδικα είναι ισοδύναμες και θα κάνει ακριβώς το ίδιο πράγμα. 

Θα ήθελα όμως να επισημάνω τα έξω πριν προχωρήσουμε περαιτέρω, έτσι ώστε να κατανοήσουν ότι πραγματικά αυτό το πράγμα εδώ είναι απλά συντακτική ζάχαρη για dereferencing ο δείκτης και στη συνέχεια πρόκειται να το n μέρος αυτής της struct. Οποιεσδήποτε ερωτήσεις σχετικά με αυτήν τη διαφάνεια; OK. 

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

Αυτά τα κουτιά δεν έχουν συνταχθεί με κλίμακα, διότι πόσο μεγάλο είναι ένας ακέραιος σε bytes; Πόσο μεγάλη τώρα; Four. Και πόσο μεγάλο είναι ένας δείκτης; Four. Έτσι, πραγματικά, αν ήταν να επιστήσει αυτή την κλίμακα και τα δύο κουτιά θα ήταν το ίδιο μέγεθος. Σε αυτή την περίπτωση, θέλουμε να εισαγάγετε κάτι μέσα στην συνδεδεμένη λίστα. Έτσι, μπορείτε να δείτε εδώ κάτω είμαστε εισαγωγή Έχουμε πέντε διασχίσει μέσα από το συνδεδεμένη λίστα, βρείτε όπου πέντε πηγαίνει, και στη συνέχεια τοποθετήστε. 

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

Έτσι, αν βλέπουμε δύο και θέλουμε να σε πέντε, τι κάνουμε όταν βλέπουμε κάτι λιγότερο από εμάς; Τι; Θέλουμε να εισαγάγετε πέντε σε αυτό συνδεδεμένη λίστα, κρατώντας ταξινομημένο. Βλέπουμε νούμερο δύο. Οπότε τι κάνουμε; Μάρκους; 

ΚΟΙΝΟ: Καλέστε το δείκτη στον επόμενο κόμβο. 

JASON Hirschhorn: Και γιατί πάμε στο επόμενο; 

ΚΟΙΝΟ: Επειδή είναι το επόμενο κόμβο στη λίστα. Και γνωρίζουμε ότι η άλλη θέση μόνο. 

JASON Hirschhorn: Και τα πέντε είναι μεγαλύτερη από δύο, ειδικότερα. Επειδή θέλουμε να κρατήσουμε ταξινομημένο. Έτσι πέντε είναι μεγαλύτερο από δύο. Γι 'αυτό και να προχωρήσουμε στο επόμενο. Και τώρα φτάνουμε τέσσερα. Και τι συμβαίνει όταν έχουμε φτάσει τέσσερα; 

Πέντε είναι μεγαλύτερη από τέσσερα. Γι 'αυτό και συνεχίζω. Και τώρα είμαστε στις έξι. Και τι βλέπουμε σε έξι; Ναι, Κάρλος; 

ΚΟΙΝΟ: Έξι είναι μεγαλύτερη από πέντε. 

JASON Hirschhorn: Έξι είναι μεγαλύτερες από πέντε. Έτσι, αυτό είναι που θέλουμε να εισαγάγετε πέντε. Ωστόσο, να έχετε κατά νου ότι αν έχουν μόνο ένα δείκτη εδώ - αυτό είναι επιπλέον δείκτη μας, που είναι διέρχονται μέσα από τη λίστα. Και είμαστε επισημαίνοντας έξι. Έχουμε χάσει την αίσθηση του τι έρχεται πριν από έξι. Έτσι, αν θέλουμε να εισάγετε κάτι σε ο κατάλογος αυτός κρατώντας ταξινόμηση, εμείς μάλλον πρέπει πόσοι δείκτες; 

ΚΟΙΝΟ: Δύο. 

JASON ΗιγβοΙίοπτ: Δύο. Κάποιος να παρακολουθείτε την τρέχουσα ένα και ένα να παρακολουθείτε η προηγούμενη. Αυτό είναι μόνο ένα μεμονωμένα συνδεδεμένη λίστα. Πηγαίνει μόνο προς μία κατεύθυνση. Αν είχαμε μια διπλά συνδεδεμένη λίστα, όπου τα πάντα δείχνουν προς το πράγμα αφού και το πράγμα πριν, τότε δεν θα πρέπει να το κάνουμε αυτό. Αλλά σε αυτή την περίπτωση δεν θέλουν να χάσουν παρακολουθείτε ό, τι ήρθαν πριν από εμάς, σε περίπτωση θα πρέπει να τοποθετήσετε κάπου πέντε στη μέση. Πείτε μας την εισαγωγή εννέα. Τι θα συμβεί όταν φτάσαμε στο οκτώ; 

ΚΟΙΝΟ: Θα έπρεπε να πάρετε αυτό το μηδενικό σημείο. Αντί να έχουμε μηδενικό σημείο θα είχατε για να προσθέσετε ένα στοιχείο και στη συνέχεια να το σημείο με εννέα. 

JASON ΗιγβοΙίοπτ: Ακριβώς. Έτσι, έχουμε οκτώ. Φτάνουμε στο τέλος της λίστας, διότι αυτό δείχνει σε null. Και τώρα, αντί να το σημείο με null έχουμε το σημείο στο νέο κόμβο μας. Και θέτουμε το δείκτη του ποντικιού το νέο μας κόμβο σε null. Μήπως κάποιος έχει απορίες σχετικά με την εισαγωγή; Τι γίνεται αν δεν νοιάζονται για διατηρώντας τη λίστα ταξινομημένη; 

ΚΟΙΝΟ: Κολλήστε το κατά τη αρχή ή στο τέλος. 

JASON ΗιγβοΙίοπτ: Κολλήστε το στο η αρχή ή το τέλος. Ποιο από τα δύο πρέπει να κάνουμε; Μπόμπι; Γιατί το τέλος; 

ΚΟΙΝΟ: Επειδή η αρχή είναι ήδη γεμάτο. 

JASON ΗιγβοΙίοπτ: OK. Η αρχή έχει ήδη πληρωθεί. Ποιος θέλει να επιχειρηματολογήσει εναντίον Bobby. Μάρκους. 

ΚΟΙΝΟ: Λοιπόν, ίσως θέλετε να κολλήσει στην αρχή, επειδή αλλιώς αν το βάλετε σε το τέλος θα έπρεπε να διασχίσει ολόκληρη τη λίστα. 

JASON ΗιγβοΙίοπτ: Ακριβώς. Έτσι, εάν σκεφτόμαστε εκτέλεσης, το εκτέλεσης της εισαγωγής στο τέλος θα είναι n, το μέγεθος αυτό. Ποια είναι η μεγάλη O χρόνου εκτέλεσης της εισαγωγής στην αρχή; Σταθερό χρόνο. Έτσι, αν δεν νοιάζονται για τη διατήρηση κάτι που ταξινομούνται, πολύ καλύτερα σε μόλις τοποθετήστε στην αρχή του καταλόγου αυτού. Και αυτό μπορεί να γίνει σε σταθερό χρόνο. 

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

ΚΟΙΝΟ: Επιστροφή λάθος; 

JASON ΗιγβοΙίοπτ: Επιστροφή ψευδείς. Εμείς δεν το βρείτε. Εάν φτάσετε στο τέλος της λίστας και δεν βρείτε τον αριθμό είστε ψάχνετε, δεν είναι εκεί. Οποιεσδήποτε ερωτήσεις σχετικά με βρείτε; Εάν αυτό ήταν μια ταξινομημένη λίστα, τι θα να είναι διαφορετική για την αναζήτηση μας; Ναι. 

ΚΟΙΝΟ: Θα βρείτε την πρώτη τιμή αυτό είναι μεγαλύτερο από το ένα ψάχνετε και Στη συνέχεια επιστρέφει false. 

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

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

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

ΚΟΙΝΟ: Έτσι, αν πρόκειται να διαγράψετε αυτό, θα μπορείτε απλά να χρησιμοποιήσετε δωρεάν, επειδή προφανώς ήταν malloced; 

JASON ΗιγβοΙίοπτ: Αν θέλετε να ελευθερώσετε κάτι που είναι ακριβώς δεξιά και malloced αυτό. Πέστε ότι ήθελε να επιστρέψει αυτή την τιμή. Εμείς μπορεί να επιστρέψει έξι και στη συνέχεια ελεύθερος αυτός ο κόμβος και δωρεάν κλήση σε αυτό. Ή θα ήθελα ίσως να καλέσετε δωρεάν το πρώτο και στη συνέχεια να επιστρέψουν έξι. 

OK. Οπότε ας περάσουμε στην πράξη κωδικοποίησης. Εμείς πάμε για να κωδικοποιήσει τις τρεις λειτουργίες. Η πρώτη ονομάζεται insert_node. Έτσι έχετε κωδικό που σας μέσω e-mail, και αν το βλέπεις αυτό αργότερα μπορείτε να αποκτήσετε πρόσβαση στο κώδικα σε linked.c στην ιστοσελίδα του CS50. Αλλά σε linked.c, υπάρχει κάποια σκελετός κώδικα που είναι ήδη έχουν γραφτεί για εσάς. Και έπειτα υπάρχει ένα ζευγάρι λειτουργίες θα πρέπει να γράψετε. 

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

Αυτό είναι ό, τι σου ζητάω να κάνετε τώρα. Και πάλι, στο linked.c, το οποίο θα όλοι, είναι ο σκελετός κώδικα. Και θα πρέπει να δείτε προς τα κάτω η δήλωση της συνάρτησης του δείγματος. Ωστόσο, πριν να υπεισέλθω σε κωδικοποίηση αυτή σε C, θα ήθελα πολύ να σας ενθαρρύνω να πάει μέσα από τα βήματα που έχουμε πάει την άσκηση κάθε εβδομάδα. Έχουμε ήδη περάσει μια εικόνα από αυτό. Έτσι, θα πρέπει να έχετε κάποια κατανόηση το πώς αυτό λειτουργεί. Αλλά θα ήθελα να σας ενθαρρύνω να γράψω κάποια pseudocode πριν από την κατάδυση in Και θα πάμε να πάει πέρα ​​από pseudocode ως ομάδα. Και στη συνέχεια, αφού έχετε γράψει σας ψευδοκώδικα, και μόλις έχουμε γράψει μας pseudocode ως ομάδα, μπορείτε να πάει σε κωδικοποίηση την Γ. 

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

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

Ας ξεκινήσουμε με το γράψιμο μερικές pseudocode στο διοικητικό συμβούλιο. Ποιος μπορεί να μου δώσει την πρώτη γραμμή pseudocode για αυτό το πρόγραμμα; Για αυτή τη λειτουργία, και όχι - insert_node. Alden; 

ΚΟΙΝΟ: Έτσι, το πρώτο πράγμα που έκανα ήταν δημιουργήσετε ένα νέο δείκτη προς τον κόμβο και εγώ προετοιμαστεί να δείχνουν προς την ίδια πράγμα που κατάλογος επισημαίνοντας. 

JASON ΗιγβοΙίοπτ: OK. Έτσι είστε δημιουργία ενός νέου δείκτη στη λίστα, όχι στον κόμβο. 

ΚΟΙΝΟ: Σωστά. Ναι. 

JASON ΗιγβοΙίοπτ: OK. Και τότε τι θέλουμε να κάνουμε; Τι μετά από αυτό; Τι γίνεται με τον κόμβο; Δεν έχουμε έναν κόμβο. Απλά έχουν μια τιμή. Εάν θέλετε να εισαγάγετε ένα κόμβο, τι κάνουμε εμείς πρέπει να κάνετε πρώτα, πριν μπορούμε ακόμη σκεφτείτε την τοποθετήσετε; 

ΚΟΙΝΟ: Συγγνώμη. πρέπει να malloc χώρο για ένα κόμβο. 

JASON ΗιγβοΙίοπτ: Εξαιρετική. Ας κάνουμε - OK. Δεν μπορεί να φτάσει τόσο ψηλά. OK. Εμείς πάμε για να πάει κάτω, και στη συνέχεια είμαστε με δύο στήλες. Δεν μπορώ να πάω ότι - OK. Δημιουργήστε ένα νέο κόμβο. Μπορείτε να δημιουργήσετε έναν άλλο δείκτη στη λίστα ή τη λίστα, μπορείτε να χρησιμοποιήσετε ακριβώς όπως υπάρχει. Μπορείτε πραγματικά δεν χρειάζεται να το κάνουμε αυτό. 

Έτσι δημιουργούμε ένα νέο κόμβο. Μεγάλη. Αυτό είναι ό, τι κάνουμε πρώτα. Ποιο είναι το επόμενο; 

ΚΟΙΝΟ: Περιμένετε. Θα πρέπει να δημιουργήσουμε ένα νέο κόμβο τώρα ή θα πρέπει να περιμένουμε για να βεβαιωθείτε ότι δεν υπάρχει καμία αντίγραφα του κόμβου στη λίστα πριν τη δημιουργία του; 

JASON ΗιγβοΙίοπτ: Καλή ερώτηση. Ας κρατήσει ότι για αργότερα, επειδή η πλειοψηφία του χρόνου θα είναι η δημιουργία ένας νέος κόμβος. Γι 'αυτό και θα κρατήσει αυτό εδώ. Αλλά αυτό είναι μια καλή ερώτηση. Αν θέλουμε να δημιουργήσουμε και να βρούμε ένα αντίγραφο, τι θα έπρεπε κάνουμε πριν από την επιστροφή; 

ΚΟΙΝΟ: Ελευθερώστε το. 

JASON ΗιγβοΙίοπτ: Ναι. Πιθανώς να απελευθερώσει. OK. Τι κάνουμε μετά εμείς δημιουργήσετε ένα νέο κόμβο; Annie; 

ΚΟΙΝΟ: Βάζουμε το αριθμός στον κόμβο; 

JASON ΗιγβοΙίοπτ: Ακριβώς. Βάζουμε τον αριθμό - που malloc χώρο. Πάω να το αφήσουμε όλα σε μία γραμμή. Αλλά έχεις δίκιο. Εμείς malloc χώρο, και στη συνέχεια έχουμε θέσει τον αριθμό in Μπορούμε επίσης να ρυθμίσετε το δείκτη τμήμα της στο μηδέν. Αυτό είναι ακριβώς σωστό. Και τότε τι γίνεται μετά από αυτό; Εμείς επέστησε την εικόνα αυτή στο διοικητικό συμβούλιο. Οπότε τι κάνουμε; 

ΚΟΙΝΟ: Έχουμε περάσει μέσα από τη λίστα. 

JASON ΗιγβοΙίοπτ: Περάστε από τη λίστα. OK. Και τι θα ελέγξει για κάθε κόμβο. Kurt, τι ελέγχουμε για κάθε κόμβο; 

ΚΟΙΝΟ: Δείτε αν η τιμή του n ότι ο κόμβος είναι μεγαλύτερη από την τιμή n του κόμβου μας. 

JASON ΗιγβοΙίοπτ: OK. Πάω να κάνω - Ναι, εντάξει. Έτσι είναι n - Πάω να πω αν η αξία είναι μεγαλύτερη από αυτόν τον κόμβο, τότε τι κάνουμε; 

ΚΟΙΝΟ: Λοιπόν, τότε εισάγουμε το πράγμα ακριβώς πριν από αυτό. 

JASON ΗιγβοΙίοπτ: OK. Οπότε αν είναι μεγαλύτερο από αυτό, τότε θα θέλετε να εισαγάγετε. Αλλά θέλουμε να το τοποθετήσετε σωστά πριν διότι και εμείς θα πρέπει να είναι την παρακολούθηση, στη συνέχεια, από ό, τι ήταν πριν. Έτσι, πριν από την εισαγωγή. Γι 'αυτό και ίσως χάσει κάτι νωρίτερα. Εμείς μάλλον θα πρέπει να κρατώντας παρακολουθείτε τι συμβαίνει. Αλλά θα φτάσουμε εκεί πίσω. Έτσι, ποια αξία είναι μικρότερη από ό, τι; Kurt, τι θα κάνουμε αν η αξία είναι μικρότερη από ό, τι; 

ΚΟΙΝΟ: Στη συνέχεια, μπορείτε απλά συνεχίστε αν δεν είναι η τελευταία. 

JASON ΗιγβοΙίοπτ: Μου αρέσει αυτό. Έτσι, πηγαίνετε στον επόμενο κόμβο. Εκτός και αν είναι η τελευταία - είμαστε κατά πάσα πιθανότητα τον έλεγχο για αυτό σύμφωνα με τους όρους μιας κατάστασης. Αλλά ναι, το επόμενο κόμβο. Και αυτό είναι να πάρει πάρα πολύ χαμηλή, έτσι θα προχωρήσουμε εδώ. Αλλά αν - μπορεί ο καθένας βλέπεις αυτό; Αν είμαστε ίσα τι κάνουμε; Εάν η τιμή που προσπαθούμε να εισάγετε είναι ίση με την αξία αυτού του κόμβου; Ναι; 

ΚΟΙΝΟ: [δεν ακούγεται]. 

JASON ΗιγβοΙίοπτ: Ναι. Λαμβάνοντας υπόψη αυτό - Μάρκους είναι σωστό. Θα μπορούσαμε να είχαμε ίσως κάνει κάτι διαφορετικό. Αλλά δεδομένου ότι έχουμε το δημιούργησε, εδώ θα πρέπει να ελευθερώσετε και στη συνέχεια επιστρέφουν. Oh boy. Είναι ότι καλύτερο; Πώς σου φαίνεται αυτό; OK. Δωρεάν και τότε τι κάνουμε εμείς επιστρέψει, [δεν ακούγεται]; OK. Μήπως λείπει κάτι; Έτσι, όταν είμαστε παρακολούθηση της προηγούμενης κόμβου; 

ΚΟΙΝΟ: Νομίζω ότι θα πάει μετά τη δημιουργία ενός νέου κόμβου. 

JASON ΗιγβοΙίοπτ: OK. Έτσι, στην αρχή θα χρειαστεί κατά πάσα πιθανότητα - ναι, μπορούμε να δημιουργήσουμε ένα δείκτη σε μια νέα κόμβο, σαν ένα προηγούμενο δείκτη κόμβο και ένα δείκτη τρέχουσας κόμβο. Έτσι, ας προσθέσουμε ότι εδώ. Δημιουργία τρέχουσα και τις προηγούμενες δείκτες προς τους κόμβους. Αλλά όταν εμείς προσαρμοστούν οι εν λόγω δείκτες; Όταν το κάνουμε αυτό στον κώδικα; Jeff; 

ΚΟΙΝΟ: - συνθήκες αξία; 

JASON ΗιγβοΙίοπτ: Ποια ένα ιδιαίτερα; 

ΚΟΙΝΟ: Είμαι απλά σύγχυση. Αν η τιμή είναι μεγαλύτερη από αυτόν τον κόμβο, Δεν σημαίνει αυτό ότι θέλετε να πάτε στον επόμενο κόμβο; 

JASON Hirschhorn: Έτσι, αν η αξία μας είναι μεγαλύτερη από την αξία αυτού του κόμβου. 

ΚΟΙΝΟ: Ναι, τότε θα θέλετε να προχωρήσει περαιτέρω κάτω από τη γραμμή, έτσι δεν είναι; 

JASON Hirschhorn: Σωστά. Γι 'αυτό και δεν την εισάγετε εδώ. Αν η τιμή είναι μικρότερη από αυτόν τον κόμβο, στη συνέχεια, πάμε στον επόμενο κόμβο - ή τότε εισάγετε πριν. 

ΚΟΙΝΟ: Περιμένετε, το οποίο είναι αυτό κόμβο και το οποίο είναι η αξία; 

JASON Hirschhorn: Καλή ερώτηση. Αξία ανά ορισμό αυτής της συνάρτησης είναι αυτό που μας δίνεται. Έτσι, η τιμή είναι ο αριθμός μας δίνεται. Έτσι, αν η τιμή είναι μικρότερη από αυτή κόμβο, χρειαζόμαστε χρόνο για να εισαγάγετε. Αν η τιμή είναι μεγαλύτερη από αυτόν τον κόμβο, πάμε στον επόμενο κόμβο. Και πίσω στην αρχική ερώτηση, όμως, όπου - 

ΚΟΙΝΟ: Εάν η τιμή είναι μεγαλύτερη από αυτόν τον κόμβο. 

JASON Hirschhorn: Και έτσι τι κάνουμε εδώ; Sweet. Αυτό είναι σωστό. Είμαι ακριβώς πρόκειται να γράψω ενημέρωση δείκτες. Αλλά ναι, με το σημερινό που θα τον ενημερώνει για την σημείο στο επόμενο. Οτιδήποτε άλλο μας λείπει; Έτσι, Πάω να πληκτρολογήσετε αυτό κωδικοποιήσει σε gedit. Και ενώ το κάνετε αυτό, μπορείτε να έχετε ένα ζευγάρι περισσότερα λεπτά για να εργαστεί για την κωδικοποίηση αυτό C. 

Έτσι έχω την είσοδο ψευδοκώδικα. Μια γρήγορη σημείωση πριν ξεκινήσουμε. Εμείς μπορεί να μην είναι σε θέση να εντελώς τελειώσει αυτό σε όλες τις τρεις από αυτές τις λειτουργίες. Υπάρχει σωστές λύσεις σε αυτά ότι θα e-mail για να σας παιδιά Μετά το σημείο, και θα να αναρτηθεί στην CS50.net. Γι 'αυτό δεν σας ενθαρρύνουμε να πηγαίνετε να δείτε στα τμήματα. Θα σας ενθαρρύνουν να δοκιμάσετε αυτά για σας κατέχουν, και στη συνέχεια χρησιμοποιήστε το την πρακτική προβλήματα για να ελέγξετε τις απαντήσεις σας. Αυτά όλα έχουν σχεδιαστεί για εκ του σύνεγγυς αφορούν και να τηρούν σε ό, τι που έχετε να κάνετε για το σύνολο του προβλήματος. Γι 'αυτό σας ενθαρρύνουμε να ασκήσετε αυτό για τη δική σας και στη συνέχεια χρησιμοποιήστε τον κωδικό για να ελέγξετε τις απαντήσεις σας. Επειδή θέλω να προχωρήσουμε σε hash τραπέζια σε κάποιο σημείο στην ενότητα. Έτσι, θα μπορούσαμε να μην περάσει όλα. Αλλά εμείς θα κάνουμε ό, τι μπορούμε τώρα. 

OK. Ας ξεκινήσουμε. Ασάμ, πώς μπορούμε να δημιουργήσουμε ένα νέο κόμβο; 

ΚΟΙΝΟ: Μπορείτε να το κάνετε struct *. 

JASON Hirschhorn: Γι 'αυτό και έχει ότι μέχρι εδώ. Ω, συγγνώμη. Έλεγες struct *. 

ΚΟΙΝΟ: Και τότε [? είδος?] κόμβου ή γ κόμβο. 

JASON Hirschhorn: OK. Πάω να το ονομάσουμε new_node ώστε να μπορούμε να παραμείνουμε συνεπείς. 

ΚΟΙΝΟ: Και θέλετε να ορίσετε ότι στο κεφάλι, τον πρώτο κόμβο. 

JASON Hirschhorn: OK. Έτσι, τώρα αυτό που δείχνουν προς - έτσι αυτό δεν έχει δημιουργήσει ένα νέο κόμβο ακόμα. Αυτό είναι ακριβώς που δείχνουν προς το πρώτο κόμβο στη λίστα. Πώς μπορώ να δημιουργήσω ένα νέο κόμβο; Αν χρειαστεί χώρο για να δημιουργήσετε ένα νέο κόμβο. Malloc. Και πόσο μεγάλο είναι; 

ΚΟΙΝΟ: Το μέγεθος του struct. 

JASON Hirschhorn: Η μέγεθος του struct. Και ποιο είναι το struct που ονομάζεται; 

ΚΟΙΝΟ: Κόμβος; 

JASON Hirschhorn: Κόμβος. Έτσι malloc (sizeof (node))? μας δίνει χώρο. Και είναι αυτή η γραμμή - ένα πράγμα είναι λανθασμένη σε αυτή τη γραμμή. Είναι ένας δείκτης σε μια struct new_node; Αυτό είναι ένα γενικό όνομα. Τι είναι αυτό - κόμβο, ακριβώς. Είναι ένας κόμβος *. Και τι κάνουμε αμέσως μετά εμείς malloc κάτι, Asan; Ποιο είναι το πρώτο πράγμα που κάνουμε; Τι γίνεται αν δεν λειτουργεί; 

ΚΟΙΝΟ: Ω, ελέγξτε αν επισημαίνει στον κόμβο; 

JASON Hirschhorn: Ακριβώς. Έτσι, αν new_node ισούται ισούται null, τι κάνουμε; Αυτό επιστρέφει bool, αυτή τη λειτουργία. Ακριβώς. Φαίνεται καλό. Οτιδήποτε για να προσθέσετε; Θα προσθέσουμε τα πράγματα στο τέλος. Αλλά αυτό μέχρι στιγμής φαίνεται καλό. Δημιουργία τρέχουσα και τις προηγούμενες υποδείξεις. Μιχαήλ, πώς μπορώ να κάνω αυτό; 

ΚΟΙΝΟ: Θα πρέπει να κάνει έναν κόμβο *. Θα έπρεπε να κάνουν ένα δεν για new_node αλλά και για την κόμβους που ήδη έχουμε. 

JASON Hirschhorn: OK. Έτσι, ο τρέχων κόμβος είμαστε σε. Θα πάρω αυτό το curr. Εντάξει. Έχουμε αποφασίσει ότι θέλετε να κρατήσετε δύο, διότι πρέπει να γνωρίζουμε τι είναι πριν από αυτό. Τι να προετοιμαστεί για να? 

ΚΟΙΝΟ: Η αξία τους στη λίστα μας. 

JASON Hirschhorn: Έτσι ποια είναι η το πρώτο πράγμα στη λίστα μας; Ή πώς ξέρουμε όπου η αρχή της λίστας μας είναι; 

ΚΟΙΝΟ: Δεν είναι πέρασε στη λειτουργία; 

JASON Hirschhorn: Σωστά. Αυτό ψηφίστηκε το δικαίωμα εδώ. Έτσι, αν έχει περάσει στη λειτουργία, η ξεκινήσει από τη λίστα, αυτό θα πρέπει να έχουμε ορίσετε την τρέχουσα ίσο με; 

ΚΟΙΝΟ: List. 

JASON Hirschhorn: List. Αυτό είναι ακριβώς σωστό. Τώρα έχει τη διεύθυνση του η αρχή της λίστας μας. Και τι γίνεται με τα προηγούμενα; 

ΚΟΙΝΟ: Λίστα μείον ένα; 

JASON Hirschhorn: Δεν υπάρχει τίποτα πριν από αυτό. Τι μπορούμε λοιπόν να κάνουμε για να δηλώσουν τίποτα; 

ΚΟΙΝΟ: Null. 

JASON Hirschhorn: Ναι. Αυτό ακούγεται σαν μια καλή ιδέα. Τέλεια. Σας ευχαριστώ. Περάστε από τη λίστα. Κωνσταντίνου, πόσο καιρό θα πάμε να περάσουν από τη λίστα; 

ΚΟΙΝΟ: Μέχρι Φτάνουμε null. 

JASON Hirschhorn: OK. Έτσι, αν, ενώ για βρόγχο. Τι κάνουμε; 

ΚΟΙΝΟ: Ίσως ένα για βρόχο; 

JASON Hirschhorn: Ας κάνουμε ένα βρόχο. OK. 

ΚΟΙΝΟ: Και λέμε για - μέχρι την τρέχουσα δείκτη δεν είναι ίση με null. 

JASON Hirschhorn: Έτσι, αν γνωρίζουμε ότι η κατάσταση, πώς μπορούμε να γράψει ένα βρόχο βασίζεται στα ανοικτά αυτή την κατάσταση. Τι είδους βρόχου θα πρέπει να χρησιμοποιήσουμε; 

ΚΟΙΝΟ: Ενώ. 

JASON Hirschhorn: Ναι. Αυτό είναι πιο λογικό με βάση μακριά από αυτό που είπατε. Αν απλά θέλετε να πάτε σε μας θα ήταν Απλά ξέρω αυτό το πράγμα, θα ήταν δεν έχει νόημα σε ένα βρόχο while. Ενώ η σημερινή δεν είναι ίσο με null, αν η τιμή είναι μικρότερη από αυτόν τον κόμβο. Akshar, να μου δώσει αυτή τη γραμμή. 

ΚΟΙΝΟ: Εάν η τρέχουσα-> n n λιγότερο από την αξία. Ή να αντιστρέψει αυτό. Ενεργοποιήστε αυτό το στήριγμα. 

JASON Hirschhorn: Συγγνώμη. 

ΚΟΙΝΟ: Αλλάξτε το στήριγμα. 

JASON Hirschhorn: Έτσι, αν είναι μεγαλύτερη από την τιμή. Επειδή αυτό είναι σύγχυση με το σχόλιο παραπάνω, Πάω να το κάνουμε αυτό. Αλλά ναι. Αν η αξία μας είναι μικρότερο από αυτό κόμβο, τι κάνουμε; Αχ. Το έχω εδώ. Εισάγετε πριν. OK. Πώς θα το κάνουμε αυτό; 

ΚΟΙΝΟ: Είναι ακόμα μου; 

JASON Hirschhorn: Ναι. 

ΚΟΙΝΟ: Μπορείτε - new_node-> επόμενο. 

JASON Hirschhorn: Λοιπόν, τι είναι ότι πρόκειται να ισούται; 

ΚΟΙΝΟ: Δεν πρόκειται να ίση ρεύμα. 

JASON Hirschhorn: Ακριβώς. Και έτσι το άλλο - τι άλλο θα πρέπει να ενημερώσετε; 

ΚΟΙΝΟ: Ελέγξτε εάν το παρελθόν ισούται με null. 

JASON Hirschhorn: Αν prev - οπότε αν προηγ ισούται με null. 

ΚΟΙΝΟ: Αυτό σημαίνει ότι πρόκειται για να γίνει το κεφάλι. 

JASON Hirschhorn: Αυτό σημαίνει ότι έχει γίνει το κεφάλι. Και τότε τι θα κάνουμε; 

ΚΟΙΝΟ: Κάνουμε το κεφάλι ισούται new_node. 

JASON Hirschhorn: Head ισούται με new_node. Και γιατί το κεφάλι εδώ, δεν λίστα; 

ΚΟΙΝΟ: Επειδή το κεφάλι είναι μια παγκόσμια μεταβλητή, η οποία είναι η αρχική θέση. 

JASON Hirschhorn: Sweet. OK. Και - 

ΚΟΙΝΟ: Τότε έχετε άλλο προηγ-> επόμενη ισούται new_node. Και τότε θα επιστρέψει αλήθεια. 

JASON Hirschhorn: Πού θέτουμε τέλος new_node; 

ΚΟΙΝΟ: Θα ήθελα - Μπορώ να ορίσω ότι στην αρχή. 

JASON Hirschhorn: Λοιπόν, τι γραμμή; 

ΚΟΙΝΟ: Μετά την δήλωση if τον έλεγχο, αν είναι γνωστή. 

JASON Hirschhorn: Δικαίωμα εδώ; 

ΚΟΙΝΟ: Θα έκανα new_node-> n ισούται με την αξία. 

JASON Hirschhorn: Ακούγεται καλό. Μάλλον είναι λογικό - δεν το κάνουμε Πρέπει να ξέρετε τι λίστα είμαστε σε επειδή είμαστε μόνο που ασχολούνται με μια λίστα. Έτσι, μια καλύτερη δήλωση της συνάρτησης για αυτό είναι μόνο για να απαλλαγούμε από αυτό εντελώς και απλά τοποθετήστε μια τιμή στο κεφάλι. Δεν χρειάζεται καν να γνωρίζουν ποια λίστα είμαστε μέσα Αλλά εγώ θα το κρατήσει για τώρα και τότε να το αλλάξετε μετά την ενημέρωση των διαφανειών και τον κωδικό. Έτσι ώστε να φαίνεται καλό για τώρα. Εάν η τιμή - που μπορεί να κάνει αυτή τη γραμμή; Αν - τι κάνουμε εδώ, ο Νώε. 

ΚΟΙΝΟ: Εάν η τιμή είναι μεγαλύτερη από curr-> n - 

JASON Hirschhorn: Πώς πάμε στον επόμενο κόμβο; 

ΚΟΙΝΟ: Curr-> n είναι ίση με new_node. 

JASON Hirschhorn: Έτσι είναι n ποιο μέρος του struct; Ο ακέραιος. Και new_node είναι ένας δείκτης σε έναν κόμβο. Λοιπόν, τι μέρος της curr θα πρέπει να ενημερώσετε; Αν δεν n, τότε τι είναι το άλλο μέρος; Νώε, τι είναι το άλλο μέρος. 

ΚΟΙΝΟ: Ω, το επόμενο. 

JASON Hirschhorn: Στη συνέχεια, ακριβώς. Ακριβώς. Επόμενο είναι το σωστό. Και τι άλλο χρειαζόμαστε για την ενημέρωση, ο Νώε; 

ΚΟΙΝΟ: Οι δείκτες. 

JASON Hirschhorn: Έτσι ανανεώσαμε ρεύμα. 

ΚΟΙΝΟ: Προηγούμενο-> επόμενο. 

JASON Hirschhorn: Ναι. Εντάξει, θα διακόψετε. Ποιος μπορεί να μας βοηθήσει εδώ; Manu, τι πρέπει να κάνουμε; 

ΚΟΙΝΟ: Έχετε να ορίσετε είναι ίσο με το curr-> επόμενο. Αλλά το κάνουμε αυτό πριν από την προηγούμενη γραμμή. 

JASON Hirschhorn: OK. Οτιδήποτε άλλο; Akshar. 

ΚΟΙΝΟ: Δεν νομίζω ότι είσαι έμελλε να αλλάξει curr-> επόμενο. Νομίζω ότι είναι γραφτό να κάνουν curr ίσων curr-> επόμενο να πάει στο επόμενο κόμβο. 

JASON Hirschhorn: Συγγνώμη, πού; Σε ποια γραμμή; Αυτή η γραμμή; 

ΚΟΙΝΟ: Ναι. Κάντε curr ισούται curr-> επόμενο. 

JASON Hirschhorn: Έτσι, αυτό είναι σωστό επειδή η τρέχουσα είναι μια δείκτη σε έναν κόμβο. Και θέλουμε να δείξουν προς την επόμενη κόμβο του τι να πάρει σήμερα επεσήμανε. Curr ίδια έχει και επόμενο. Αλλά αν ήταν να ενημερώσετε curr.next, εμείς θα ανανεώσουμε την πραγματική σημείωση μόνη της, όπου αυτό δεν δείκτης έδειχνε. Τι γίνεται με αυτή τη γραμμή, όμως. AVI; 

ΚΟΙΝΟ: Προηγούμενη-> ισούται με το επόμενο curr. 

JASON Hirschhorn: Έτσι και πάλι, αν προηγ είναι δείκτη σε έναν κόμβο, προηγ-> επόμενο είναι η πραγματικό δείκτη στον κόμβο. Έτσι, αυτό θα ήταν μια ενημέρωση pointer σε ένα κόμβο στο Curr. Δεν θέλουμε να ενημερώσετε ένα δείκτη σε ένα κόμβο. Θέλουμε να ενημερώσετε τα προηγούμενα. Έτσι, πώς θα το κάνουμε αυτό; 

ΚΟΙΝΟ: Θα ήταν απλώς να προηγ. 

JASON Hirschhorn: Σωστά. Προηγούμενη είναι ένας δείκτης σε έναν κόμβο. Τώρα είμαστε το αλλάζει σε ένα νέο δείκτη σε έναν κόμβο. OK Ας προχωρήσουμε προς τα κάτω. Τέλος, αυτή η τελευταία προϋπόθεση. Jeff, τι κάνουμε εδώ; 

ΚΟΙΝΟ: Εάν η τιμή είναι ίση με curr-> n. 

JASON Hirschhorn: Συγγνώμη. Ω Θεέ μου. Τι; Αξία == curr-> n. Τι πρέπει να κάνουμε; 

ΚΟΙΝΟ: Θα ήθελα να ελευθερώσετε new_node μας, και τότε θα επιστρέψει false. 

JASON Hirschhorn: Αυτό είναι ό, τι έχουμε γράψει μέχρι τώρα. Μήπως κάποιος έχει τίποτα να προστεθούν, πριν κάνουμε; OK. Ας το δοκιμάσουμε. Ο έλεγχος μπορεί να φθάσει στο τέλος ενός μη άκυρη λειτουργία. Avi, τι συμβαίνει; 

ΚΟΙΝΟ: Είστε υποτίθεται για να βάλει επιστροφή αλήθεια έξω από το βρόχο, ενώ; 

JASON Hirschhorn: Δεν ξέρω. Μήπως θέλεις να; 

ΚΟΙΝΟ: Δεν πειράζει. Όχι. 

JASON Hirschhorn: Akshar; 

ΚΟΙΝΟ: Νομίζω ότι θα σήμαινε να βάλει ψευδή δήλωση στο τέλος από τον βρόχο while. 

JASON Hirschhorn: Έτσι, όταν Δεν θέλετε να πάτε; 

ΚΟΙΝΟ: Όπως και έξω από το βρόχο while. Έτσι, αν βγείτε από το βρόχο, ενώ αυτό σημαίνει ότι ότι έχετε φτάσει στο τέλος και τίποτα δεν συνέβη. 

JASON Hirschhorn: OK. Λοιπόν, τι κάνουμε εδώ; 

ΚΟΙΝΟ: Θα επιστρέψει false εκεί. 

JASON Hirschhorn: Ω, το κάνει σε δύο μέρη; 

ΚΟΙΝΟ: Ναι. 

JASON Hirschhorn: OK. Θα πρέπει να πάμε; Ω Θεέ μου. Λυπάμαι. Ζητώ συγγνώμη για την οθόνη. Είναι το είδος της φρικάρει μας. Έτσι, επιλέγουν μια επιλογή. Μηδέν, ανά κωδικό, κλείνει το πρόγραμμα. Ένα εισάγει κάτι. Ας εισάγει τρεις. Το ένθετο δεν ήταν επιτυχής. Πάω να εκτυπώσετε. Δεν έχω τίποτα. OK. Ίσως αυτό να ήταν απλά ένα λάθος. Τοποθετήστε το ένα. Δεν είναι επιτυχής. OK. Ας τρέχει μέσα GDB πολύ γρήγορα για να δείτε τι συμβαίνει. 

Θυμηθείτε gdb. / Το όνομα της ιστοσελίδας σας πρόγραμμα μας παίρνει στο GDB. Είναι ότι πολλά για να χειριστεί; Η αναβοσβήνει; Πιθανώς. Κλείστε τα μάτια σας και να πάρετε κάποια βαθιά ανάσες αν έχετε κουραστεί το κοιτάξουμε. Είμαι στην GDB. Ποιο είναι το πρώτο πράγμα που κάνω το GDB; Έχουμε να καταλάβω τι συμβαίνει εδώ. Ας δούμε. Έχουμε έξι λεπτά για να σχήμα τι συμβαίνει. Σπάστε κύριο. Και τότε τι μπορώ να κάνω; Κάρλος; Τρέξτε. OK. Ας επιλέξουν μια επιλογή. Και τι κάνουμε N; Επόμενο. Ναι. 

ΚΟΙΝΟ: Δεν σας αναφέρω - Δεν είπες ότι το κεφάλι, ήταν αρχικοποιείται null στην αρχή. Αλλά σκέφτηκα είπατε ότι ήταν εντάξει. 

JASON Hirschhorn: Πάμε - ας ρίξουμε μια ματιά στην GDB, και στη συνέχεια θα πάμε πίσω. Αλλά ακούγεται σαν έχετε ήδη μερικές ιδέες για το τι συμβαίνει. Έτσι θέλουμε να εισάγετε κάτι. OK. Έχουμε την εισαγωγή. Παρακαλώ εισάγετε έναν int. Θα εισάγει τρεις. Και τότε είμαι σε αυτή τη γραμμή. Πώς μπορώ να πάω να αρχίσει debugging το ένθετο γνωστή λειτουργία; Ω Θεέ μου. Αυτό είναι ένα πολύ. Είναι ότι φρικάρει πολύ; 

ΚΟΙΝΟ: Ω, πέθανε. 

JASON Hirschhorn: απλά το τράβηξε έξω. OK. 

ΚΟΙΝΟ: Ίσως είναι η άλλο άκρο του σύρματος. 

JASON Hirschhorn: Wow. Έτσι, η κατώτατη γραμμή - τι είπες; 

ΚΟΙΝΟ: Είπα η ειρωνεία της τεχνικής δυσκολίες σε αυτή την κατηγορία. 

JASON Hirschhorn: Το ξέρω. Αν είχα τον έλεγχο αυτό το μέρος. [Δεν ακούγεται] Αυτό ακούγεται μεγάλη. Γιατί δεν κάνετε εσείς να αρχίσουμε να σκεφτόμαστε τι θα μπορούσαμε να είχαμε κάνει λάθος, και θα είμαστε πίσω σε 90 δευτερόλεπτα. 

Avica, Πάω να σας ρωτήσω πώς να πάτε μέσα insert_node να debug. Έτσι, αυτό είναι όπου είχατε σταματήσει. Πώς μπορώ να πάω μέσα insert_node, Avica, να εξετάσει τι συμβαίνει; Τι GDB εντολή; Break δεν θα με μεταφέρει στο εσωτερικό. Μήπως Marquise ξέρει; 

ΚΟΙΝΟ: Τι; 

JASON Hirschhorn: Τι εντολή GDB Μπορώ να χρησιμοποιήσω για να πάει μέσα αυτή τη λειτουργία; 

ΚΟΙΝΟ: Βήμα; 

JASON Hirschhorn: Βήμα μέσω S. Αυτό με βάζει μέσα. OK. New_node mallocing κάποιο διάστημα. Αυτό φαίνεται σαν όλα της πηγαίνει. Ας εξετάσουμε new_node. Πήρε κάποια διεύθυνση μνήμης. Ας ελέγξει - ότι είναι όλα σωστά. Έτσι, τα πάντα εδώ φαίνεται να να λειτουργεί σωστά. 

ΚΟΙΝΟ: Ποια είναι η διαφορά μεταξύ P και η οθόνη; 

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

OK. Έτσι είμαστε στη γραμμή 80 του κώδικα μας, ρύθμιση κόμβο * curr ίση με λίστα. Ας εκτυπώσετε curr. Ισούται με λίστα. Sweet. Περιμένετε. Ισούται με κάτι. Αυτό δεν φαίνεται σωστό. Εκεί πάμε. Είναι επειδή το GDB, σωστά, αν Είναι η γραμμή είστε σε αυτό δεν έχει εκτελεστεί ακόμη. Έτσι, θα πρέπει να πληκτρολογήσετε στην πραγματικότητα δίπλα να εκτελέσει τη γραμμή πριν δει τα αποτελέσματά της. Έτσι, εδώ είμαστε. Εμείς απλά εκτελούνται αυτή τη γραμμή, προηγούμενο ισούται με null. Έτσι και πάλι, αν τυπώνουμε προηγούμενο δεν θα δούμε τίποτα περίεργο. Αλλά αν μπορούμε πραγματικά να εκτελέσει ότι γραμμή, τότε θα δούμε ότι η γραμμή λειτούργησε. 

Έτσι έχουμε curr. Αυτοί είναι και οι δύο καλά. Σωστά; Τώρα είμαστε σε αυτή τη γραμμή εδώ. Ενώ curr δεν είναι ίσο με null. Λοιπόν, τι κάνει curr ίσοι; Εμείς απλά είδε ισοφάρισε null. Μπορούμε να εκτυπωθεί. Θα το εκτυπώσετε ξανά. Έτσι, είναι ότι, ενώ βρόχο πρόκειται να εκτελέσει; 

ΚΟΙΝΟ: Όχι. 

JASON Hirschhorn: Έτσι, όταν θα πληκτρολογήσει ότι γραμμή, θα δείτε ότι πήδηξε σε όλη τη διαδρομή στο κάτω μέρος, επιστρέφει false. Και μετά θα πάμε να επιστρέψει false και να πάει πίσω στο πρόγραμμά μας και τελικά να εκτυπώσετε, όπως είδαμε, Το ένθετο δεν ήταν επιτυχής. Έτσι, οποιοσδήποτε έχει κάποιες ιδέες για το τι πρέπει να κάνουμε για να το διορθώσω αυτό; Πάω να περιμένω μέχρι να δω ένα ζευγάρι χέρια ανεβαίνουν. Εμείς δεν εκτελέσει αυτό. Κρατήστε στο μυαλό, αυτό ήταν το πρώτο πράγμα που κάναμε. Είμαι δεν πρόκειται να κάνει ένα ζευγάρι. Πάω να κάνω μερικές. Επειδή ένα ζευγάρι σημαίνει δύο. Θα περιμένω για περισσότερο από δύο. 

Η πρώτη εισαγωγή, curr, από προεπιλογή ισούται με null. Και αυτός ο βρόχος εκτελεί μόνο αν curr δεν είναι null. Λοιπόν, πώς μπορώ να πάρω γύρω από αυτό; Βλέπω τρία χέρια. Θα περιμένω για περισσότερα από τρία. Marcus, τι νομίζεις; 

ΚΟΙΝΟ: Λοιπόν, αν το χρειάζεστε για να εκτελέσει περισσότερες από μία φορές, απλά αλλάξετε σε ένα do-while loop. 

JASON Hirschhorn: OK. Θα λύσει το πρόβλημα αυτό μας, όμως; 

ΚΟΙΝΟ: Στην περίπτωση αυτή δεν εξαιτίας της το γεγονός ότι η λίστα είναι κενή. Έτσι, τότε ίσως απλά πρέπει να προσθέσετε δήλωση ότι, αν ο βρόχος τότε θα πρέπει να είναι στο τέλος του ο κατάλογος, σε ποιο σημείο θα μπορεί να εισαχθεί μόνο. 

JASON Hirschhorn: Μου αρέσει αυτό. Αυτό είναι λογικό. Αν ο βρόχος βγαίνει - γιατί θα επιστρέψει false εδώ. Έτσι, αν τα βρόχος, τότε είμαστε σε το τέλος της λίστας, ή ίσως το ξεκινήσει από μια λίστα αν δεν υπάρχει τίποτα στο αυτό, το οποίο είναι το ίδιο με το άκρο. Έτσι, τώρα θέλουμε να εισαγάγετε κάτι εδώ. Έτσι, πώς αυτός κώδικας δούμε, Μάρκους; 

ΚΟΙΝΟ: Αν έχεις ήδη τον κόμβο malloced, θα μπορούσε απλώς να πω new_node-> επόμενο ισούται με null, διότι θα πρέπει να είναι στο τέλος. Ή new_node-> επόμενο ισούται με null. 

JASON Hirschhorn: OK. Λυπάμαι. New_node-> επόμενο ισούται με null επειδή είμαστε στο τέλος. Αυτό δεν το βάλετε μέσα Πώς μπορούμε να το βάλετε στη λίστα; Δεξιά. Αυτό είναι ακριβώς ίση με τη ρύθμιση. Όχι πώς μπορούμε πραγματικά βάλετε στη λίστα; Τι δείχνουν προς το τέλος της λίστας; 

ΚΟΙΝΟ: Head. 

JASON Hirschhorn: Συγγνώμη; 

ΚΟΙΝΟ: Επικεφαλής είναι στραμμένο στο τέλος της λίστας. 

JASON Hirschhorn: Αν δεν υπάρχει τίποτα στο ο κατάλογος, το κεφάλι είναι στραμμένη προς το τέλος της λίστας. Έτσι, αυτό θα λειτουργήσει για το πρώτη εισαγωγή. Τι γίνεται αν υπάρχουν ένα ζευγάρι τα πράγματα στη λίστα; Από ό, τι δεν θέλετε να ορίσετε κεφάλι ίσο με new_node. Τι θέλουμε να κάνουμε εκεί; Ναι; Πιθανώς προηγούμενο. Θα αυτό το έργο; Υπενθυμίζουμε ότι τα προηγούμενα είναι απλώς ένα δείκτη σε έναν κόμβο. Και τα προηγούμενα είναι μια τοπική μεταβλητή. Έτσι, αυτή η γραμμή θα δημιουργήσει μια τοπική μεταβλητή, προηγούμενο, ίση ή δείχνουν προς αυτή τη νέα κόμβο. Αυτό δεν θα το βάλουμε στην πραγματικότητα στην λίστα μας, όμως. Πώς μπορούμε να το βάλετε στη λίστα μας; Akchar; 

ΚΟΙΝΟ: Νομίζω ότι εσείς κάνουν ρεύματος> επόμενο. 

JASON Hirschhorn: OK. curr-> επόμενο. Έτσι και πάλι, ο μόνος λόγος που είμαστε κάτω εδώ είναι, τι κάνει ρεύμα ίσο; 

ΚΟΙΝΟ: Ίσο με null. 

JASON Hirschhorn: Και έτσι αυτό θα συμβεί αν κάνουμε null-> επόμενο; Τι πρόκειται να πάρει; Θα πάρετε ένα σφάλμα κατάτμησης. 

ΚΟΙΝΟ: Να curr ισούται με null. 

JASON Hirschhorn: Αυτό είναι το ίδιο πράγμα ως προηγούμενο, όμως, γιατί υπάρχει μια τοπική μεταβλητή είμαστε ρύθμιση ίση με αυτό το νέο κόμβο. Ας πάμε πίσω στην εικόνα μας της εισαγωγής κάτι. Πείτε είμαστε εισάγοντας στο τέλος του καταλόγου, έτσι ακριβώς εδώ. Έχουμε μια τρέχουσα δείκτη που είναι επισημαίνοντας null και ένα προηγούμενο σημείο αυτό είναι που δείχνουν προς 8. Έτσι, αυτό που χρειαζόμαστε για να ενημερώσετε, AVI; 

ΚΟΙΝΟ: Previous-> επόμενο; 

JASON Hirschhorn: Previous-> επόμενο είναι αυτό που θέλουμε να ενημερώσετε γιατί αυτό θα την εισάγετε στην πραγματικότητα σε το τέλος της λίστας. Έχουμε ακόμα ένα bug, όμως, ότι θα πάμε να τρέχει σε. Τι είναι αυτό σφάλμα; Ναι; 

ΚΟΙΝΟ: Δεν πρόκειται να επιστρέψει false σε αυτή την περίπτωση; 

JASON Hirschhorn: Ω, είναι η πρόκειται να επιστρέψει false. Αλλά υπάρχει ένα άλλο bug. Γι 'αυτό θα πρέπει να τεθεί σε αντάλλαγμα αλήθεια. 

ΚΟΙΝΟ: Μήπως τα προηγούμενα παραμένουν στα ίδια επίπεδα null στην κορυφή της λίστας; 

JASON Hirschhorn: Έτσι προηγούμενο ακόμα ισούται με null στην αρχή. Έτσι, πώς μπορούμε να το ξεπεράσω αυτό; Ναι; 

ΚΟΙΝΟ: Νομίζω ότι μπορείτε να κάνετε έναν έλεγχο πριν από το βρόχο while να δούμε αν είναι μια κενή λίστα. 

JASON Hirschhorn: OK. Οπότε ας πάμε εδώ. Κάντε έναν έλεγχο. Αν - 

ΚΟΙΝΟ: Έτσι, αν το κεφάλι ισούται ισούται με null. 

JASON Hirschhorn: Αν το κεφάλι ισούται ισούται με null - που θα μας πει αν είναι μια κενή λίστα. 

ΚΟΙΝΟ: Και τότε θα κάνει το κεφάλι ισούται με νέα. 

JASON Hirschhorn: Head ισούται με new_node; Και τι άλλο πρέπει να κάνουμε; 

ΚΟΙΝΟ: Και τότε θα επιστρέψει αλήθεια. 

JASON Hirschhorn: Δεν είναι αρκετά. Μας λείπει ένα βήμα. 

ΚΟΙΝΟ: New_node επόμενο πρέπει να δείχνουν μηδέν. 

JASON Hirschhorn: Ακριβώς, Alden. Και τότε μπορούμε να επιστρέψουμε αλήθεια. OK. Αλλά είναι ακόμα μια καλή ιδέα να κάνετε πράγματα στο τέλος της λίστας, έτσι δεν είναι; Εντάξει. Ακόμα μπορεί να πάρει πραγματικά στο τέλος της λίστας. Έτσι είναι αυτός ο κώδικας πρόστιμο αν είμαστε κατά τη τέλος του καταλόγου και υπάρχουν μερικά τα πράγματα στη λίστα; Σωστά; Επειδή έχουμε ακόμα ιδέα Μάρκους. Θα μπορούσαμε να βγείτε από αυτό το βρόχο, διότι είμαστε στο τέλος της λίστας. Έτσι, δεν θέλουμε ακόμα αυτό κωδικοποιήσει εδώ κάτω; 

ΚΟΙΝΟ: Ναι. 

JASON Hirschhorn: Ναι. Και τι θα πρέπει να αλλάξει αυτό; True. Μήπως αυτό ακούγεται καλό σε όλους τους μέχρι τώρα; Ο καθένας έχει κάποια - Avi, δεν έχετε κάτι να προσθέσετε; 

ΚΟΙΝΟ: Όχι. 

JASON Hirschhorn: OK. Έτσι, έχουμε κάνει μια-δυο αλλαγές. Έχουμε κάνει αυτόν τον έλεγχο πριν πήγε σε μια κενή λίστα. Έτσι έχουμε φροντίσει μια κενή λίστα. Και εδώ έχουμε φρόντισε εισαγωγή κάτι στο τέλος της λίστας. Φαίνεται λοιπόν ότι αυτό που λαμβάνουν, ενώ βρόχο φροντίσει τα πράγματα στο μεταξύ, κάπου στον κατάλογο, εφόσον υπάρχει είναι τα πράγματα στη λίστα. 

OK. Ας τρέξει αυτό το πρόγραμμα ξανά. Δεν είναι επιτυχής. 

ΚΟΙΝΟ: Δεν το έκανε. 

JASON Hirschhorn: Ω, Εγώ δεν το κάνει. Καλό σημείο, Μάικλ. Ας προσθέσουμε μια μάρκα που συνδέονται με. Γραμμή 87 υπάρχει ένα σφάλμα. Γραμμή 87. Alden, αυτή ήταν η γραμμή που μου έδωσες. Τι είναι λάθος; 

ΚΟΙΝΟ: Πρέπει να είναι σε μηδέν. 

JASON Hirschhorn: Εξαιρετική. Ακριβώς δεξιά. Θα πρέπει να είναι μηδενική. Ας κάνουμε και πάλι. Η μεταγλώττιση. OK. Ας εισάγει τρεις. Το ένθετο ήταν επιτυχής. Ας το εκτυπώσετε. Αχ, αν μόνο να ελέγξουμε. Αλλά δεν κάναμε το εκτυπώσετε τη λειτουργία ακόμη. Ας εισάγετε κάτι άλλο. Τι θα πρέπει να μπούμε; 

ΚΟΙΝΟ: Επτά. 

JASON Hirschhorn: Επτά; 

ΚΟΙΝΟ: Ναι. 

JASON Hirschhorn: Έχουμε ένα σφάλμα seg. Γι 'αυτό και πήρε ένα, αλλά σαφώς δεν μπορεί να πάρει δύο. Είναι 5:07. Έτσι, θα μπορούσαμε να διορθώσετε αυτό για τρία λεπτά. Αλλά Πάω να μας αφήσει εδώ και να προχωρήσουμε στο hash πίνακες. Αλλά και πάλι, οι απαντήσεις για αυτόν τον κωδικό Θα το e-mail σας σε ένα κομμάτι. Είμαστε πολύ κοντά σε αυτό. Θα ήθελα πολύ να σας ενθαρρύνω να καταλάβω τι συμβαίνει εδώ και να το διορθώσουμε. Γι 'αυτό θα σας στείλουμε έναν κωδικό ως και συν η λύση - ίσως η λύση αργότερα. Κατ 'αρχάς ο κώδικας αυτός. 

Το άλλο πράγμα που θέλω να κάνω πριν φινίρισμα είναι ότι δεν έχουν απελευθερωθεί τίποτα. Θέλω, λοιπόν, να σας δείξω τι valgrind μοιάζει. Αν τρέξουμε όρια valgrind σχετικά με το πρόγραμμα μας,. / συνδέονται μεταξύ τους. Και πάλι, σύμφωνα με αυτήν τη διαφάνεια, θα θα πρέπει να τρέξει valgrind με κάποιο τύπο επιλογή, σε αυτή την περίπτωση - Διαρροή-check = πλήρης. Έτσι, ας γράψουμε valgrind - Διαρροή-check = πλήρης. Έτσι, αυτό θα τρέξει valgrind σχετικά με το πρόγραμμα μας. Και τώρα το πρόγραμμα πραγματικά τρέχει. Έτσι θα πάμε για να τρέξει ακριβώς όπως πριν, βάλτε κάτι μέσα Πάω να θέσει σε τρεις. Αυτό λειτουργεί. Είμαι δεν πρόκειται να προσπαθήσει να θέσει σε κάτι γιατί αλλιώς θα πάμε να πάρετε μια ψευδή seg σε αυτή την περίπτωση. Έτσι, είμαι απλώς πρόκειται να σταματήσουν. 

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

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

Και στη συνέχεια, αν αυτό δεν ήταν η περίπτωση, αν κάναμε όλα δωρεάν, μπορούμε να ελέγξουμε αυτό. Ας κάνουμε το πρόγραμμα δεν θέτει σε τίποτα. Θα δείτε εδώ κάτω στη χρήση κατά την έξοδο - μηδέν bytes το μηδέν μπλοκ. Αυτό σημαίνει ότι είχαμε μείνει τίποτα όταν αυτό το πρόγραμμα τερματίζεται. Έτσι, πριν από την στροφή στην pset6, τρέχει valgrind και βεβαιωθείτε ότι δεν έχετε οποιαδήποτε μνήμη διαρροές στο πρόγραμμά σας. Εάν έχετε οποιεσδήποτε ερωτήσεις με valgrind, διστάσετε να φτάσει. Αλλά αυτό είναι το πώς μπορείτε να το χρησιμοποιήσετε. Πολύ απλό - δείτε αν μπορείτε έχουν σε χρήση κατά την έξοδο - τυχόν bytes σε κάθε μπλοκ. 

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

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

Υπάρχει σειρά μας. Υπάρχει λειτουργία μας. Ειδικότερα, συναρτήσεις κατακερματισμού πρέπει να κάνει μερικά πράγματα με αυτό. Πάω να μιλήσω ειδικά περίπου που αυτό το πρόβλημα. Είναι κατά πάσα πιθανότητα θα λαμβάνει σε μια σειρά. Και τι πρόκειται να επιστρέψει; Τι είδους δεδομένα; Alden; Συνάρτηση κατακερματισμού σας επιστρέψει; Ένας ακέραιος. Έτσι, αυτό είναι ό, τι το hash πίνακας αποτελείται από - ένας πίνακας με τη μορφή συστοιχίας και μια συνάρτηση κατακερματισμού. Πώς λειτουργεί; Δρα σε τρία βήματα. Μπορούμε να δώσουμε ένα κλειδί. Σε αυτή την περίπτωση, θα δώσει μια σειρά. Καλούμε την συνάρτηση κατακερματισμού ανά ένα βήμα στο κλειδί και παίρνουμε μια τιμή. 

Συγκεκριμένα, εμείς θα πούμε έχουμε έναν ακέραιο. Αυτό ακέραιος, υπάρχουν πολύ συγκεκριμένες όρια στο τι μπορεί να είναι ακέραιος. Σε αυτό το παράδειγμα, συστοιχία μας είναι το μέγεθος των τριών. Έτσι τι οι αριθμοί μπορεί να είναι ότι το ακέραιο. Ποιο είναι το εύρος των έγκυρων τιμών για ότι ακέραιος, ο τύπος επιστροφής αυτής hash λειτουργία; Zero, ένα και δύο. Το σημείο της συνάρτησης κατακερματισμού είναι να καταλάβω τη θέση στη συστοιχία πού είναι το κλειδί μας πηγαίνει. Είναι μόνο τρεις πιθανές υπάρχει μέρη εδώ - μηδέν, ένα, ή δύο. Έτσι, αυτή η λειτουργία καλύτερη απόδοση μηδέν, ένα, ή δύο. Μερικά έγκυρη indice σε αυτό το array. 

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

Πριν φτάσουμε εκεί, απορίες σχετικά με αυτό το βασικό set-up ενός πίνακα κατακερματισμού; Αυτή είναι μια εικόνα ακριβώς αυτό που επέστησε στο διοικητικό συμβούλιο. Αλλά δεδομένου ότι επέστησε στο διοικητικό συμβούλιο, I Δεν πρόκειται να υπεισέλθω σε περαιτέρω. Ουσιαστικά πλήκτρα, το μαγικό μαύρο κουτί - ή στην περίπτωση αυτή, το πλαίσιο teal - ενός hash λειτουργία τους βάζει σε κουβάδες. Και σε αυτό το παράδειγμα είμαστε Δεν βάζοντας το όνομα. Βάζουμε το σχετικό τηλέφωνο τον αριθμό του ονόματος στον κάδο. Αλλά θα μπορούσε πολύ καλά μόνο βάλετε το όνομα στον κάδο. 

Αυτή είναι μόνο μια εικόνα του τι αντλήσαμε στο διοικητικό συμβούλιο. Έχουμε πιθανές παγίδες, όμως. Και υπάρχουν δύο ιδιαίτερα διαφάνειες ότι θέλω να πάω πάνω. Το πρώτο είναι περίπου μια συνάρτηση κατακερματισμού. Γι 'αυτό και έθεσε το ερώτημα, τι κάνει μια καλή συνάρτηση κατακερματισμού; Δίνω δύο απαντήσεις. Το πρώτο είναι ότι είναι ντετερμινιστική. Στο πλαίσιο των hash συναρτήσεων, Τι σημαίνει αυτό; Ναι; 

ΚΟΙΝΟ: Μπορεί να βρει το δείκτη σε σταθερό χρόνο; 

JASON Hirschhorn: Ότι Δεν είναι ό, τι αυτό σημαίνει. Αλλά αυτό είναι μια καλή εικασία. Οποιοσδήποτε άλλος έχει μια εικασία με ό, τι σημαίνει αυτό; Ότι μια καλή συνάρτηση κατακερματισμού είναι προσδιοριστική; Annie; 

ΚΟΙΝΟ: Αυτό το κλειδί μπορεί να αντιστοιχιστεί μόνο σε μία θέση στον πίνακα κατακερματισμού. 

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

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

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

Δεν ταιριάζει. Αλλά πρέπει να πάει κάπου. Αυτό είναι το τραπέζι hash μου μετά από όλα, και ό, τι χρειάζεται για να πάει κάπου. Έτσι, όταν θα πάτε ρόπαλο; Οποιεσδήποτε σκέψεις; Εικασίες; Καλή εικασίες; 

ΚΟΙΝΟ: Μηδέν. 

JASON Hirschhorn: Γιατί το μηδέν; 

ΚΟΙΝΟ: Επειδή τρεις modulo τρεις είναι μηδέν; 

JASON Hirschhorn: Τρία modulo τρεις είναι μηδέν. Αυτό είναι μια μεγάλη εικασία, και αυτό είναι σωστό. Έτσι, στην περίπτωση αυτή θα πρέπει να πάει πιθανώς στο μηδέν. Έτσι, ένας καλός τρόπος για να εξασφαλιστεί ότι αυτό το hash συνάρτηση επιστρέφει ισχύει μόνο δύο δείκτες να modulo από το μέγεθος του πίνακα. Αν modulo ό, τι αυτό επιστρέφει από τρεις, είστε πάντα πρόκειται να πάρει κάτι μεταξύ μηδέν, ένα και δύο. Και αν αυτό επιστρέφει πάντα επτά, και πάντα με μέτρο από τρεις, είστε πάντα πρόκειται να πάρει το ίδιο πράγμα. 

Έτσι είναι ακόμα ντετερμινιστική αν modulo. Αλλά αυτό θα εξασφαλίσει ότι θα δεν παίρνουν ποτέ κάτι - άκυρη βιομηχανία. Σε γενικές γραμμές, η modulo πρέπει να συμβεί μέσα hash λειτουργία σας. Έτσι δεν χρειάζεται να ανησυχείτε γι 'αυτό. Μπορείτε απλά να διασφαλίσει ότι αυτό είναι ένα έγκυρο indice. Οποιεσδήποτε ερωτήσεις σχετικά με αυτό το δυνητική παγίδα; 

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

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

Έτσι έβαλα κολοκύθα. Επιστρέφει το μηδέν. Και έβαλα κολοκύθα εδώ. Στη συνέχεια έβαλα στο - τι άλλο Απόκριες με θέμα το πράγμα; 

ΚΟΙΝΟ: Candy. 

JASON Hirschhorn: Candy! Αυτό είναι ένα μεγάλο. Έβαλα στην καραμέλα και καραμέλα μου δίνει επίσης μηδέν. Τι μπορώ να κάνω; Οποιεσδήποτε ιδέες; Επειδή όλοι γνωρίζουμε το είδος της τι Ξεχωριστές αλυσίδες είναι. Έτσι, οποιεσδήποτε ιδέες τι να κάνω; Ναι. 

ΚΟΙΝΟ: Κάνοντας το string πραγματικά στον πίνακα κατακερματισμού. 

JASON Hirschhorn: Έτσι θα πάμε για να επιστήσει την καλή ιδέα εδώ. OK. 

ΚΟΙΝΟ: Έχετε το hashtable [Δεν ακούγεται] ο δείκτης που δείχνει προς η αρχή μιας λίστας. Και στη συνέχεια να κολοκύθα είναι η πρώτη τιμή στην εν λόγω συνδεδεμένη λίστα και γλυκά είναι η δεύτερη τιμή στην εν λόγω συνδεδεμένη λίστα. 

JASON Hirschhorn: OK. Marcus, που ήταν εξαιρετική. Πάω να σπάσει το κάτω. Ο Μάρκους λέει δεν αντικαταστήσετε κολοκύθα. Αυτό θα ήταν κακό. Μη βάζετε καραμέλα κάπου αλλού. Εμείς πάμε για να τους βάλει τόσο στο μηδέν. Αλλά θα πάμε να ασχοληθεί με τη θέση τους σε μηδέν δημιουργώντας μια λίστα στο μηδέν. Και θα πάμε για να δημιουργήσετε μια λίστα όλα αυτά που αντιστοιχίζεται στο μηδέν. Και ο καλύτερος τρόπος που μάθαμε να δημιουργήσετε μια λίστα που μπορεί να αναπτυχθεί και να συρρικνωθεί δυναμικά δεν είναι εντός άλλη διάταξη. Έτσι, δεν είναι μια πολυδιάστατη array. Αλλά για να δημιουργήσετε μόνο μια συνδεδεμένη λίστα. 

Έτσι, αυτό που πρότεινε - Πάω να πάρετε ένα νέο - είναι να δημιουργήσετε έναν πίνακα με δείκτες, μια σειρά από δείκτες. OK. Κάθε ιδέα ή υπόδειξη από τον τύπο αυτής δείκτες θα πρέπει να είναι; Μάρκους; 

ΚΟΙΝΟ: Δείκτες σε - 

JASON Hirschhorn: Επειδή σας είπε μια συνδεδεμένη λίστα, έτσι - 

ΚΟΙΝΟ: Δείκτες κόμβου; 

JASON Hirschhorn: Δείκτες κόμβου. Αν τα πράγματα στη συνδέεται μας λίστα είναι οι κόμβοι τότε θα πρέπει να είναι δείκτες κόμβο. Και τι ισούται αρχικά; 

ΚΟΙΝΟ: Null. 

JASON Hirschhorn: Null. Έτσι, υπάρχει κενό πράγμα μας. Επιστρέφει κολοκύθας μηδέν. Τι πρέπει να κάνουμε; Περπατήστε μου μέσα από αυτό; Στην πραγματικότητα, Marcus ήδη μου έδωσε. Κάποιος άλλος τα πόδια μου μέσα από αυτό. Τι κάνουμε όταν - Αυτό μοιάζει πολύ με ό, τι μας κάνει ακριβώς. Avi. 

ΚΟΙΝΟ: Πάω να λάβει μια εικασία. Έτσι, όταν θα έχετε καραμέλα. 

JASON Hirschhorn: Ναι. Λοιπόν, έχουμε κολοκύθα. Ας πάρουμε πρώτα το ένα μας. Έχουμε κολοκύθα. 

ΚΟΙΝΟ: OK. Επιστρέφει κολοκύθας μηδέν. Έτσι, μπορείτε να το βάλετε σε αυτό. Ή στην πραγματικότητα, μπορείτε να το βάλετε στην συνδεδεμένη λίστα. 

JASON Hirschhorn: Πώς μπορούμε να το βάζουμε σε συνδεδεμένη λίστα; 

ΚΟΙΝΟ: Ω, η πραγματική σύνταξη; 

JASON Hirschhorn: Μόνο με τα πόδια - πω περισσότερα. Τι πρέπει να κάνουμε; 

ΚΟΙΝΟ: Απλά τοποθετήστε ως τον πρώτο κόμβο. 

JASON Hirschhorn: OK. Έτσι έχουμε τον κόμβο μας, κολοκύθα. Και τώρα πώς μπορώ να το τοποθετήσετε; 

ΚΟΙΝΟ: Μπορείτε να εκχωρήσετε να το δείκτη. 

JASON Hirschhorn: Ποια δείκτη; 

ΚΟΙΝΟ: Ο δείκτης στο μηδέν. 

JASON Hirschhorn: Έτσι, όταν κάνει αυτό το σημείο; 

ΚΟΙΝΟ: Να null τώρα. 

JASON Hirschhorn: Λοιπόν, είναι να υποδεικνύουν σε null. Αλλά βάζω στην κολοκύθα. Έτσι, όταν θα πρέπει να το σημείο; 

ΚΟΙΝΟ: Να κολοκύθα. 

JASON Hirschhorn: Να κολοκύθα. Ακριβώς. Έτσι, αυτό δείχνει την κολοκύθα. Και όταν το κάνει αυτό δείκτη Στο σημείο κολοκύθα; Να 

ΚΟΙΝΟ: Null. 

JASON Hirschhorn: Να μηδέν. Ακριβώς. Γι 'αυτό και μόλις εισαχθεί κάτι στην συνδεδεμένη λίστα. Γράψαμε ακριβώς αυτόν τον κωδικό για να γίνει αυτό. Σχεδόν έχουμε σχεδόν το πήρα εντελώς ραγισμένα. Τώρα εισάγουμε καραμέλα. Καραμέλα μας πηγαίνει επίσης στο μηδέν. Λοιπόν, τι θα κάνουμε με την καραμέλα; 

ΚΟΙΝΟ: Εξαρτάται από το αν ή Δεν προσπαθούμε να το λύσουμε. 

JASON Hirschhorn: Αυτό είναι ακριβώς δεξιά. Εξαρτάται από το εάν ή όχι προσπαθούμε να το λύσουμε. Ας υποθέσουμε ότι δεν είμαστε πρόκειται να το λύσουμε. 

ΚΟΙΝΟ: Λοιπόν, όπως συζητήσαμε πριν, αυτό είναι απλούστερο απλά για να το θέσω από την αρχή, ώστε ο δείκτης από μηδέν βαθμούς σε καραμέλα. 

JASON Hirschhorn: OK. Περίμενε. Επιτρέψτε μου να δημιουργήσει καραμέλα εδώ. Έτσι, αυτό το δείκτη - 

ΚΟΙΝΟ: Ναι, πρέπει τώρα πρέπει να δείχνουν προς την καραμέλα. Στη συνέχεια, έχουμε το δείκτη από σημείο καραμέλα κολοκύθα. 

JASON Hirschhorn: Σας αρέσει αυτό; Και έλεγα ότι έχουμε ένα άλλο πράγμα για να χαρτογραφήσουν το μηδέν; 

ΚΟΙΝΟ: Λοιπόν, απλά κάνουν το ίδιο πράγμα; 

JASON Hirschhorn: Κάνετε το ίδιο πράγμα. Έτσι, σε αυτή την περίπτωση, αν δεν το κάνουμε θέλετε να κρατήσετε το ταξινομημένο Ακούγεται αρκετά απλό. Παίρνουμε το δείκτη του ποντικιού στην indice δίνεται από τη λειτουργία hash μας. Έχουμε αυτό το σημείο στο νέο κόμβο μας. Και τότε ό, τι έδειχνε στο παρελθόν - σε αυτή την περίπτωση null, στην δεύτερη περίπτωση κολοκύθα - ότι, όποια και αν είναι δείχνοντας προηγουμένως, προσθέτουμε στο επόμενο της νέος κόμβος μας. Είμαστε εισάγοντας κάτι στην αρχή. Στην πραγματικότητα αυτό είναι μια πολύ απλούστερη από ό, τι προσπαθεί να κρατήσει τη λίστα ταξινομημένο. Αλλά και πάλι, η αναζήτηση θα είναι περιπλέκεται περισσότερο εδώ. Θα πρέπει πάντα να πάει μέχρι το τέλος. 

OK. Οποιεσδήποτε ερωτήσεις σχετικά με Ξεχωριστές αλυσίδες; Πώς λειτουργεί; Παρακαλώ ρωτήστε τους τώρα. Θέλω πραγματικά να βεβαιωθείτε ότι έχετε όλα καταλάβουμε αυτό πριν από το κεφάλι έξω. 

ΚΟΙΝΟ: Γιατί βάζετε κολοκύθα και καραμέλα στο ίδιο μέρος του πίνακα κατακερματισμού; 

JASON Hirschhorn: Καλή ερώτηση. Γιατί τα βάζουμε στο ίδιο μέρος του πίνακα κατακερματισμού; Λοιπόν, σε αυτή την περίπτωση η συνάρτηση κατακερματισμού μας επιστρέφει μηδέν και για τους δύο. Γι 'αυτό πρέπει να πάμε στο μηδέν indice επειδή αυτό είναι όπου θα πάμε να αναζητήστε τους αν ποτέ θέλουν να τα αναζητήσετε. Και πάλι, με μια προσέγγιση γραμμική ανίχνευση εμείς δεν θα τους έθετε τόσο στο μηδέν. Αλλά στην προσέγγιση χωριστή αλυσίδα, θα πάμε να τα βάλουμε τόσο στο μηδέν και στη συνέχεια να δημιουργήσετε μια λίστα μακριά από το μηδέν. 

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

OK. Κάρλος. Γραμμική σχολαστικά συνεπάγεται - αν βρήκαμε μια σύγκρουση στο μηδέν, έχουμε θα δούμε στο επόμενο σημείο για να δούμε αν ήταν ανοιχτή και να το βάλεις εκεί. Και τότε θα δούμε στο επόμενο αθλητισμό και να δούμε αν αυτό ήταν ανοιχτή και να το βάλεις εκεί. Έτσι, βρίσκουμε το επόμενο διαθέσιμο ανοικτή θέση και να το βάλετε εκεί. Οποιεσδήποτε άλλες ερωτήσεις; Ναι, Avi. 

ΚΟΙΝΟ: Ως συνέχεια αυτού, τι εννοείς με το επόμενο σημείο; Στον πίνακα hash ή σε συνδεδεμένη λίστα. 

JASON Hirschhorn: Για τις γραμμικές προγραμματισμού, δεν συνδέονται με τους καταλόγους. Το επόμενο σημείο του πίνακα κατακερματισμού. 

ΚΟΙΝΟ: OK. Έτσι, ο πίνακας κατακερματισμού θα ήταν αρχικοποιείται με το μέγεθος - όπως ο αριθμός των χορδών ότι είστε εισαγωγή; 

JASON Hirschhorn: Θα το έκανες θέλουν να είναι πραγματικά μεγάλο. Ναι. Εδώ είναι μια εικόνα του τι θα μόλις επέστησε στο διοικητικό συμβούλιο. Και πάλι, έχουμε μια σύγκρουση εδώ. σε 152. Και θα δείτε δημιουργήσαμε μια συνδεδεμένη λίστα μακριά από αυτό. Και πάλι, ο πίνακας κατακερματισμού Ξεχωριστές αλυσίδες προσέγγιση δεν είναι αυτό που πρέπει να ληφθούν για τα προβλήματα που έξι, αλλά είναι αυτό που πολλοί οι μαθητές τείνουν να λάβουν. Έτσι, σε αυτό το σημείωμα, ας μιλήσουμε λίγο πριν από το κεφάλι έξω για το πρόβλημα των έξι, και, στη συνέχεια, θα μοιραστώ μαζί σας μια ιστορία. Έχουμε τρία λεπτά. 

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

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

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

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

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