1 00:00:00,000 --> 00:00:11,860 2 00:00:11,860 --> 00:00:13,120 >> ΟΜΙΛΗΤΗΣ 1: Εντάξει, έτσι είμαστε πίσω. 3 00:00:13,120 --> 00:00:14,480 Καλώς ήρθατε στο CS50. 4 00:00:14,480 --> 00:00:16,510 Αυτό είναι το τέλος της εβδομάδας επτά. 5 00:00:16,510 --> 00:00:20,200 Έτσι Υπενθυμίζεται ότι την περασμένη φορά, αρχίσαμε να κοιτάζοντας λίγο πιο εξελιγμένα 6 00:00:20,200 --> 00:00:21,100 δομών δεδομένων. 7 00:00:21,100 --> 00:00:25,110 Δεδομένου ότι μέχρι τώρα, όλοι είχαμε πραγματικά στη διάθεσή μας ήταν αυτό, μια σειρά. 8 00:00:25,110 --> 00:00:29,340 >> Αλλά πριν να απορρίψει τον πίνακα ως μη όλα αυτά ενδιαφέροντα, τα οποία μάλιστα 9 00:00:29,340 --> 00:00:33,570 πραγματικά είναι, ποια είναι μερικά από τα συν αυτής της απλής δεδομένων 10 00:00:33,570 --> 00:00:34,560 δομή μέχρι στιγμής; 11 00:00:34,560 --> 00:00:36,110 Τι είναι αυτό στο καλό; 12 00:00:36,110 --> 00:00:39,450 Μέχρι στιγμής, όπως έχουμε δει; 13 00:00:39,450 --> 00:00:42,540 Τι έχεις; 14 00:00:42,540 --> 00:00:44,028 Τίποτα. 15 00:00:44,028 --> 00:00:45,020 >> ΦΟΙΤΗΤΗΣ: [δεν ακούγεται]. 16 00:00:45,020 --> 00:00:45,395 >> ΟΜΙΛΗΤΗΣ 1: Τι είναι αυτό; 17 00:00:45,395 --> 00:00:46,410 >> ΦΟΙΤΗΤΗΣ: [δεν ακούγεται]. 18 00:00:46,410 --> 00:00:47,000 >> ΟΜΙΛΗΤΗΣ 1: Σταθερό μέγεθος. 19 00:00:47,000 --> 00:00:51,260 Εντάξει, τόσο γιατί είναι σταθερό μέγεθος καλό όμως; 20 00:00:51,260 --> 00:00:53,180 >> ΦΟΙΤΗΤΗΣ: [δεν ακούγεται]. 21 00:00:53,180 --> 00:00:56,240 >> ΟΜΙΛΗΤΗΣ 1: Εντάξει, έτσι ώστε να είναι αποτελεσματική στην με την έννοια ότι μπορείτε να διαθέσουν ένα 22 00:00:56,240 --> 00:01:00,070 σταθερό ποσό του χώρου, η οποία ελπίζουμε ότι είναι ακριβώς όσο 23 00:01:00,070 --> 00:01:01,180 χώρο όπως εσείς θέλετε. 24 00:01:01,180 --> 00:01:02,720 Έτσι, αυτό θα μπορούσε να είναι απολύτως ένα συν. 25 00:01:02,720 --> 00:01:06,530 >> Τι άλλο πάνω μέρος του μια σειρά; 26 00:01:06,530 --> 00:01:07,610 Ναι; 27 00:01:07,610 --> 00:01:08,750 >> ΦΟΙΤΗΤΗΣ: [δεν ακούγεται]. 28 00:01:08,750 --> 00:01:09,550 >> ΟΜΙΛΗΤΗΣ 1: Όλα τα - Ορίστε; 29 00:01:09,550 --> 00:01:11,270 >> ΦΟΙΤΗΤΗΣ: [δεν ακούγεται]. 30 00:01:11,270 --> 00:01:13,620 >> ΟΜΙΛΗΤΗΣ 1: Όλα τα κουτιά στη μνήμη ή ένα δίπλα στο άλλο. 31 00:01:13,620 --> 00:01:15,220 Και αυτό είναι χρήσιμο - γιατί; 32 00:01:15,220 --> 00:01:15,970 Αυτό είναι αλήθεια. 33 00:01:15,970 --> 00:01:18,611 Αλλά πώς μπορούμε να εκμεταλλευτεί την αλήθεια; 34 00:01:18,611 --> 00:01:21,500 >> ΦΟΙΤΗΤΗΣ: [δεν ακούγεται]. 35 00:01:21,500 --> 00:01:24,490 >> ΟΜΙΛΗΤΗΣ 1: Ακριβώς, μπορούμε να παρακολουθείτε όπου τα πάντα είναι μόνο με τη γνώση 36 00:01:24,490 --> 00:01:28,560 μία διεύθυνση, δηλαδή η διεύθυνση της πρώτο byte του εν λόγω κομμάτι της μνήμης. 37 00:01:28,560 --> 00:01:30,420 Ή στην περίπτωση των χορδών, η διεύθυνση του πρώτου 38 00:01:30,420 --> 00:01:31,460 char σε αυτό το string. 39 00:01:31,460 --> 00:01:33,330 Και από εκεί, μπορούμε να βρούμε το τέλος του string. 40 00:01:33,330 --> 00:01:35,710 Μπορούμε να βρούμε το δεύτερο στοιχείο, το τρίτο στοιχείο, και ούτω καθεξής. 41 00:01:35,710 --> 00:01:38,740 >> Και έτσι το φανταχτερό τρόπος περιγραφής που χαρακτηριστικό είναι ότι οι πίνακες που μας δίνουν 42 00:01:38,740 --> 00:01:40,020 τυχαίας προσπέλασης. 43 00:01:40,020 --> 00:01:44,330 Απλά με τη χρήση του αγκύλη συμβολισμό και μια σειρά, μπορείτε να μεταβείτε σε 44 00:01:44,330 --> 00:01:48,070 ένα ειδικό στοιχείο στη συστοιχία σε συνεχή χρόνο, μεγάλη O 45 00:01:48,070 --> 00:01:49,810 του ενός, να το πω έτσι. 46 00:01:49,810 --> 00:01:51,080 >> Αλλά έχει υπάρξει κάποια μειονεκτήματα. 47 00:01:51,080 --> 00:01:53,110 Αυτό δεν είναι μια σειρά κάνει πολύ εύκολα; 48 00:01:53,110 --> 00:01:55,810 49 00:01:55,810 --> 00:01:57,170 Τι είναι αυτό δεν είναι καλοί; 50 00:01:57,170 --> 00:01:58,810 >> ΦΟΙΤΗΤΗΣ: [δεν ακούγεται]. 51 00:01:58,810 --> 00:01:59,860 >> ΟΜΙΛΗΤΗΣ 1: Τι είναι αυτό; 52 00:01:59,860 --> 00:02:00,530 >> ΦΟΙΤΗΤΗΣ: [δεν ακούγεται]. 53 00:02:00,530 --> 00:02:01,460 >> ΟΜΙΛΗΤΗΣ 1: Επέκταση σε μέγεθος. 54 00:02:01,460 --> 00:02:04,800 Έτσι είναι τα μειονεκτήματα του πίνακα ακριβώς το αντίθετο από ό, τι η 55 00:02:04,800 --> 00:02:05,540 upsides είναι. 56 00:02:05,540 --> 00:02:07,610 Έτσι, ένα από τα μειονεκτήματα είναι ότι είναι ένα σταθερό μέγεθος. 57 00:02:07,610 --> 00:02:09,400 Έτσι δεν μπορεί να αναπτυχθεί πραγματικά. 58 00:02:09,400 --> 00:02:13,510 Μπορείτε να ανακατανέμουν ένα μεγαλύτερο κομμάτι του μνήμης, και στη συνέχεια μετακινήστε τα παλιά στοιχεία 59 00:02:13,510 --> 00:02:14,460 στο νέο πίνακα. 60 00:02:14,460 --> 00:02:18,060 Και τότε δωρεάν το παλιό πίνακα, για παράδειγμα, με τη χρήση malloc ή ένα παρόμοιο 61 00:02:18,060 --> 00:02:21,180 λειτουργία που ονομάζεται realloc, η οποία ανακατανέμονταν μνήμης. 62 00:02:21,180 --> 00:02:25,490 >> Realloc, ως μέρος, προσπαθεί να σας δώσει μνήμης που είναι δίπλα στην παράταξη 63 00:02:25,490 --> 00:02:26,610 που ήδη έχετε. 64 00:02:26,610 --> 00:02:28,740 Αλλά μπορεί να κινηθούν τα πράγματα περίπου συνολικά. 65 00:02:28,740 --> 00:02:30,710 Όμως, εν ολίγοις, αυτό είναι ακριβό, έτσι δεν είναι; 66 00:02:30,710 --> 00:02:33,440 Διότι, αν έχετε ένα μεγάλο κομμάτι της μνήμης της αυτό το μέγεθος, αλλά θέλετε πραγματικά ένα 67 00:02:33,440 --> 00:02:36,710 αυτού του μεγέθους, και θέλετε να διατηρήσετε τα πρωτότυπα στοιχεία, έχετε 68 00:02:36,710 --> 00:02:40,510 περίπου μια γραμμική διαδικασία αντιγραφής του χρόνου Αυτό πρέπει να συμβεί από 69 00:02:40,510 --> 00:02:41,900 παλιά σειρά στο νέο. 70 00:02:41,900 --> 00:02:44,630 Και η πραγματικότητα ζητά από το λειτουργικό το σύστημα ξανά και ξανά και 71 00:02:44,630 --> 00:02:48,340 και πάλι για μεγάλα κομμάτια της μνήμης μπορεί να ξεκινήσει να σας κοστίσει κάποιο χρόνο, καθώς και. 72 00:02:48,340 --> 00:02:52,250 Γι 'αυτό είναι τόσο ευλογία και κατάρα μεταμφίεση, το γεγονός ότι αυτές οι συστοιχίες 73 00:02:52,250 --> 00:02:53,860 είναι σταθερού μεγέθους. 74 00:02:53,860 --> 00:02:56,790 Αλλά αν έχουμε εισαγάγει αντ 'αυτού κάτι όπως αυτό, τα οποία ζητήσαμε ένα συνδεδεμένο 75 00:02:56,790 --> 00:03:00,580 λίστα, έχουμε μερικές upsides και μερικά μειονεκτήματα ως εδώ καλά. 76 00:03:00,580 --> 00:03:05,780 >> Έτσι, μια συνδεδεμένη λίστα είναι απλά ένα δεδομένο δομή που αποτελείται από C structs σε αυτό 77 00:03:05,780 --> 00:03:09,850 περίπτωση, όπου μια struct, ανάκληση, είναι ακριβώς ένα δοχείο για μία ή περισσότερες συγκεκριμένες 78 00:03:09,850 --> 00:03:11,100 τύπους μεταβλητών. 79 00:03:11,100 --> 00:03:16,110 Σε αυτή την περίπτωση, τι τους τύπους δεδομένων φαίνεται να είναι στο εσωτερικό του struct που 80 00:03:16,110 --> 00:03:17,600 τελευταία φορά που καλέσαμε έναν κόμβο; 81 00:03:17,600 --> 00:03:19,380 Καθένα από αυτά τα ορθογώνια είναι ένας κόμβος. 82 00:03:19,380 --> 00:03:22,660 Και κάθε ένα από τα μικρότερα ορθογώνια μέσα από αυτό είναι ένας τύπος δεδομένων. 83 00:03:22,660 --> 00:03:25,300 Ποια είδη δεν λέμε ήταν τη Δευτέρα; 84 00:03:25,300 --> 00:03:26,478 Ναι; 85 00:03:26,478 --> 00:03:27,870 >> ΦΟΙΤΗΤΗΣ: [δεν ακούγεται]. 86 00:03:27,870 --> 00:03:30,721 >> ΟΜΙΛΗΤΗΣ 1: Μια μεταβλητή και ένα δείκτη, ή Πιο συγκεκριμένα, ένας int, για Ν, 87 00:03:30,721 --> 00:03:32,180 και ένα δείκτη στο κάτω μέρος. 88 00:03:32,180 --> 00:03:35,360 Και οι δύο από αυτούς τυχαίνει να είναι 32 bits, σε τουλάχιστον σε έναν υπολογιστή, όπως αυτό CS50 89 00:03:35,360 --> 00:03:37,980 Appliance, και έτσι είναι που εξίσου σε μέγεθος. 90 00:03:37,980 --> 00:03:42,260 >> Λοιπόν, τι χρησιμοποιώντας το δείκτη αν και για φαινόμενα; 91 00:03:42,260 --> 00:03:47,690 Γιατί να προσθέσετε αυτό το βέλος τώρα, όταν συστοιχίες τόσο ωραίο και καθαρό και απλό; 92 00:03:47,690 --> 00:03:50,460 Τι είναι ο δείκτης να κάνει για μας σε κάθε ένα από αυτούς τους κόμβους; 93 00:03:50,460 --> 00:03:52,160 >> ΦΟΙΤΗΤΗΣ: [δεν ακούγεται]. 94 00:03:52,160 --> 00:03:52,465 >> ΟΜΙΛΗΤΗΣ 1: Ακριβώς. 95 00:03:52,465 --> 00:03:54,120 Είναι σας λέω, όπου το επόμενο είναι. 96 00:03:54,120 --> 00:03:57,350 Γι 'αυτό το είδος της χρησιμοποιώ την αναλογία των χρησιμοποιώντας ένα νήμα για να ταξινομήσετε του 97 00:03:57,350 --> 00:03:59,180 νήμα αυτούς τους κόμβους μαζί. 98 00:03:59,180 --> 00:04:01,760 Και αυτό είναι ακριβώς ό, τι κάνουμε με δείκτες διότι κάθε ένα από αυτά 99 00:04:01,760 --> 00:04:06,360 κομμάτια της μνήμης μπορεί να είναι ή να μην είναι συνεχόμενα, πλάτη με πλάτη με πλάτη 100 00:04:06,360 --> 00:04:09,500 στο εσωτερικό της μνήμης RAM, επειδή κάθε φορά που καλέστε malloc λέει, να μου δώσει αρκετά 101 00:04:09,500 --> 00:04:12,510 bytes για ένα νέο κόμβο, ίσως να είναι να είναι εδώ ή θα μπορούσε να είναι εδώ. 102 00:04:12,510 --> 00:04:13,120 Θα μπορούσε να είναι εδώ. 103 00:04:13,120 --> 00:04:13,730 Θα μπορούσε να είναι εδώ. 104 00:04:13,730 --> 00:04:14,640 Απλά δεν ξέρω. 105 00:04:14,640 --> 00:04:17,880 >> Αλλά χρησιμοποιώντας δείκτες στις διευθύνσεις των κόμβοι αυτοί, μπορείτε να βελονιά τους 106 00:04:17,880 --> 00:04:22,370 μαζί με έναν τρόπο που μοιάζει οπτικά όπως μια λίστα, ακόμη και αν είναι αυτά τα πράγματα 107 00:04:22,370 --> 00:04:26,770 απλώνονται σε όλη την μία ή δύο ή τέσσερα gigabytes σας RAM 108 00:04:26,770 --> 00:04:28,760 εσωτερικό του υπολογιστή σας. 109 00:04:28,760 --> 00:04:33,230 >> Έτσι, το μειονέκτημα, τότε, μια συνδεδεμένη λίστα είναι αυτό; 110 00:04:33,230 --> 00:04:34,670 Τι είναι ένα τίμημα που είμαστε προφανώς πληρώνει; 111 00:04:34,670 --> 00:04:36,010 >> ΦΟΙΤΗΤΗΣ: [δεν ακούγεται]. 112 00:04:36,010 --> 00:04:36,920 >> ΟΜΙΛΗΤΗΣ 1: Περισσότερος χώρος, έτσι δεν είναι; 113 00:04:36,920 --> 00:04:39,340 Έχουμε, στην περίπτωση αυτή, διπλασίασε το ποσό του χώρου, διότι έχουμε περάσει 114 00:04:39,340 --> 00:04:43,500 από 32 bits για κάθε κόμβο, για καθεμία int, τώρα, ώστε 64 bits, διότι πρέπει να 115 00:04:43,500 --> 00:04:45,050 κρατήσει γύρω από ένα δείκτη, καθώς και. 116 00:04:45,050 --> 00:04:48,860 Μπορείτε να πάρετε μεγαλύτερη αποτελεσματικότητα, αν struct σας είναι μεγαλύτερο από αυτό το απλό πράγμα. 117 00:04:48,860 --> 00:04:52,020 Αν έχετε πραγματικά ένα μαθητή μέσα εκ των οποίων είναι ένα ζευγάρι των strings για 118 00:04:52,020 --> 00:04:55,430 το όνομα και το σπίτι, ίσως ένα αριθμό ταυτότητας, ίσως κάποια άλλα πεδία εντελώς. 119 00:04:55,430 --> 00:04:59,000 >> Έτσι, εάν έχετε ένα αρκετά μεγάλο struct, τότε ίσως το κόστος του δείκτη είναι 120 00:04:59,000 --> 00:05:00,010 δεν είναι μια τέτοια μεγάλη υπόθεση. 121 00:05:00,010 --> 00:05:03,570 Αυτό είναι ένα κομμάτι από μια υπόθεση γωνία που είμαστε αποθήκευση μια τέτοια απλή πρωτόγονη 122 00:05:03,570 --> 00:05:04,760 εσωτερικό του συνδεδεμένη λίστα. 123 00:05:04,760 --> 00:05:05,790 Αλλά το σημείο είναι το ίδιο. 124 00:05:05,790 --> 00:05:08,230 Ξοδεύετε σίγουρα πιο μνήμη, αλλά παίρνετε 125 00:05:08,230 --> 00:05:08,990 ευελιξία. 126 00:05:08,990 --> 00:05:12,280 Γιατί τώρα, αν θέλω να προσθέσω ένα στοιχείο κατά την έναρξη αυτής της λίστας, 127 00:05:12,280 --> 00:05:14,340 Έχω να διαθέσει ένα νέο κόμβο. 128 00:05:14,340 --> 00:05:17,180 Και εγώ πρέπει να ενημερώσετε μόνο εκείνες βέλη κατά κάποιο τρόπο από μόνο κίνηση 129 00:05:17,180 --> 00:05:17,980 μερικοί δείκτες γύρω. 130 00:05:17,980 --> 00:05:20,580 >> Αν θέλω να εισχωρήσει κάτι μέσα του μέση της λίστας, δεν έχω να 131 00:05:20,580 --> 00:05:24,410 ωθεί τον καθένα στην άκρη, όπως κάναμε και στην τελευταίες εβδομάδες »με τους εθελοντές μας που 132 00:05:24,410 --> 00:05:25,700 αντιπροσώπευε μια σειρά. 133 00:05:25,700 --> 00:05:29,470 Μπορώ να διαθέσει μόνο ένα νέο κόμβο και τότε το σημείο ακριβώς τα βέλη στην 134 00:05:29,470 --> 00:05:32,290 διαφορετικές κατευθύνσεις, επειδή δεν πρέπει να παραμείνουν στην πραγματική 135 00:05:32,290 --> 00:05:35,670 μνήμη μια πραγματική γραμμή, όπως έχω σχεδιάσει εδώ στην οθόνη. 136 00:05:35,670 --> 00:05:38,400 >> Και στη συνέχεια, τέλος, εάν θέλετε να εισάγετε κάτι στο τέλος της λίστας, είναι 137 00:05:38,400 --> 00:05:39,210 ακόμα πιο εύκολη. 138 00:05:39,210 --> 00:05:43,320 Αυτό είναι το είδος της αυθαίρετης σημειογραφίας, αλλά και δείκτη 34, να λάβει μια εικασία. 139 00:05:43,320 --> 00:05:46,710 Ποια είναι η αξία του δείκτη της πιο που πιθανό είδος του σαν ένα παλιό 140 00:05:46,710 --> 00:05:47,700 κεραία σχολείο εκεί; 141 00:05:47,700 --> 00:05:48,920 >> ΦΟΙΤΗΤΗΣ: [δεν ακούγεται]. 142 00:05:48,920 --> 00:05:49,900 >> ΟΜΙΛΗΤΗΣ 1: Είναι μάλλον άκυρη. 143 00:05:49,900 --> 00:05:52,710 Και πράγματι αυτό είναι ένα συγγραφέα εκπροσώπηση των null. 144 00:05:52,710 --> 00:05:56,310 Και είναι μηδενική, γιατί είναι απολύτως Πρέπει να γνωρίζουμε πού το τέλος ενός συνδεδεμένου 145 00:05:56,310 --> 00:06:00,050 λίστα είναι, μήπως έχετε κρατήσει μετά και μετά και μετά από αυτά τα βέλη 146 00:06:00,050 --> 00:06:01,170 σε κάποια τιμή σκουπιδιών. 147 00:06:01,170 --> 00:06:06,230 Έτσι, null, θα σημαίνει ότι δεν υπάρχει περισσότερους κόμβους στα δεξιά του αριθμού 34, 148 00:06:06,230 --> 00:06:07,200 σε αυτή την περίπτωση. 149 00:06:07,200 --> 00:06:10,270 >> Γι 'αυτό και προτείνω να μπορούμε να εφαρμόσουμε ο κόμβος στον κώδικα. 150 00:06:10,270 --> 00:06:12,130 Και έχουμε δει αυτό το είδος της σύνταξης πριν. 151 00:06:12,130 --> 00:06:15,090 Typedef ορίζει μόνο ένα νέο είδος για την μας, μας δίνει ένα συνώνυμο, όπως 152 00:06:15,090 --> 00:06:17,100 χορδή ήταν για char *. 153 00:06:17,100 --> 00:06:21,030 Στην περίπτωση αυτή, πρόκειται να μας δώσει σημειογραφία έτσι ώστε κόμβο struct 154 00:06:21,030 --> 00:06:24,010 μπορεί, αντί απλά να γραφτεί ως κόμβο, το οποίο είναι ένα πολύ καθαρότερο. 155 00:06:24,010 --> 00:06:25,360 Είναι πολύ λιγότερο φλύαρη. 156 00:06:25,360 --> 00:06:30,080 >> Στο εσωτερικό ενός κόμβου είναι προφανώς ένα int ονομάζεται Ν, και στη συνέχεια ένας κόμβος struct * 157 00:06:30,080 --> 00:06:34,670 πράγμα που σημαίνει ακριβώς αυτό που θέλαμε το βέλη για να πω, ένα δείκτη σε μια άλλη 158 00:06:34,670 --> 00:06:36,940 κόμβο του ακριβούς ίδιου τύπου δεδομένων. 159 00:06:36,940 --> 00:06:40,300 Και εγώ προτείνω ότι θα μπορούσε να εφαρμόσει ένα λειτουργία αναζήτησης, όπως αυτό, τα οποία σε 160 00:06:40,300 --> 00:06:41,890 Εκ πρώτης όψεως μπορεί να φαίνεται λίγο περίπλοκο. 161 00:06:41,890 --> 00:06:43,330 Αλλά ας δούμε το πλαίσιο. 162 00:06:43,330 --> 00:06:45,480 >> Επιτρέψτε μου να πάω πάνω στη συσκευή εδώ. 163 00:06:45,480 --> 00:06:48,460 Επιτρέψτε μου να ανοίξει ένα αρχείο με το όνομα Λίστα μηδέν dot h. 164 00:06:48,460 --> 00:06:53,950 Και αυτό περιέχει μόνο εμείς τον ορισμό μόλις είδα πριν από λίγο για αυτά τα δεδομένα 165 00:06:53,950 --> 00:06:55,390 τύπο που ονομάζεται κόμβος. 166 00:06:55,390 --> 00:06:57,350 Έτσι, έχουμε βάλει ότι σε ένα αρχείο dot h. 167 00:06:57,350 --> 00:07:01,430 >> Και ως ένα μέρος, έστω και αν αυτό πρόγραμμα που είστε έτοιμος να δούμε είναι 168 00:07:01,430 --> 00:07:05,410 δεν είναι όλα αυτά συγκρότημα, είναι πράγματι σύμβαση όταν γράφετε ένα πρόγραμμα για να 169 00:07:05,410 --> 00:07:10,270 βάλει τα πράγματα όπως τύπους δεδομένων, να τραβήξει σταθερές μερικές φορές, μέσα σας 170 00:07:10,270 --> 00:07:13,210 αρχείο κεφαλίδας και όχι κατ 'ανάγκην C το αρχείο σας, σίγουρα όταν σας 171 00:07:13,210 --> 00:07:17,370 προγράμματα παίρνουν όλο και μεγαλύτερο, έτσι ώστε να ξέρετε πού να κοιτάξετε και για 172 00:07:17,370 --> 00:07:20,840 τεκμηρίωση, σε ορισμένες περιπτώσεις, ή για τα βασικά όπως αυτό, τα 173 00:07:20,840 --> 00:07:22,360 ορισμός κάποιου τύπου. 174 00:07:22,360 --> 00:07:25,680 >> Αν μου τώρα να ανοίξει λίστα μηδέν dot c, παρατηρήσετε μερικά πράγματα. 175 00:07:25,680 --> 00:07:29,090 Περιλαμβάνει μερικά αρχεία κεφαλίδας, οι περισσότεροι εκ των οποίων έχουμε ξαναδεί. 176 00:07:29,090 --> 00:07:31,980 Περιλαμβάνει το δικό της αρχείο επικεφαλίδα του. 177 00:07:31,980 --> 00:07:35,200 >> Και ως ένα μέρος, γιατί αυτό είναι διπλά εισαγωγικά εδώ, σε αντίθεση με τη γωνία 178 00:07:35,200 --> 00:07:38,340 παρένθεση στη γραμμή που Έχω τόνισε εκεί; 179 00:07:38,340 --> 00:07:39,180 >> ΦΟΙΤΗΤΗΣ: [δεν ακούγεται]. 180 00:07:39,180 --> 00:07:40,460 >> ΟΜΙΛΗΤΗΣ 1: Ναι, έτσι είναι ένα τοπικό αρχείο. 181 00:07:40,460 --> 00:07:44,300 Έτσι, αν είναι ένα τοπικό αρχείο της δικής σας εδώ στη γραμμή 15, για παράδειγμα, μπορείτε να χρησιμοποιήσετε 182 00:07:44,300 --> 00:07:46,570 τα διπλά εισαγωγικά, αντί των γωνιακών παρενθέσεων. 183 00:07:46,570 --> 00:07:48,270 >> Τώρα αυτό είναι το είδος της ενδιαφέρον. 184 00:07:48,270 --> 00:07:51,830 Παρατηρήστε ότι έχω δηλώσει μια παγκόσμια μεταβλητή σε αυτό το πρόγραμμα on line 18 185 00:07:51,830 --> 00:07:55,910 καλείται αρχικά, η ιδέα είναι αυτό είναι πρόκειται να είναι ένας δείκτης για την πρώτη 186 00:07:55,910 --> 00:07:59,190 κόμβο σε συνδεδεμένη λίστα μου, και έχω προετοιμαστεί να null, επειδή έχω 187 00:07:59,190 --> 00:08:02,310 δεν έχει χορηγηθεί καμία πραγματική κόμβους ακριβώς ακόμα. 188 00:08:02,310 --> 00:08:07,570 >> Έτσι, αυτό αντιπροσωπεύει, εικονογραφικά, τι μπορούμε είδαμε πριν από λίγο στην εικόνα, όπως 189 00:08:07,570 --> 00:08:10,090 ότι το δείκτη στο μέτρο αριστερή πλευρά. 190 00:08:10,090 --> 00:08:12,260 Μέχρι τώρα, η δείκτη δεν έχει ένα βέλος. 191 00:08:12,260 --> 00:08:14,590 Είναι, αντίθετα, απλώς άκυρη. 192 00:08:14,590 --> 00:08:17,880 Αλλά αντιπροσωπεύει ποια θα είναι η διεύθυνση του πρώτου πραγματικού 193 00:08:17,880 --> 00:08:19,480 κόμβο σε αυτή τη λίστα. 194 00:08:19,480 --> 00:08:22,120 Έτσι έχω εφαρμοστεί είναι ένα παγκόσμιο γιατί, όπως θα δούμε, όλα αυτά 195 00:08:22,120 --> 00:08:25,310 το πρόγραμμα έχει στη ζωή είναι να εφαρμόσει το μια συνδεδεμένη λίστα για μένα. 196 00:08:25,310 --> 00:08:27,050 >> Τώρα έχω μερικά πρωτότυπα εδώ. 197 00:08:27,050 --> 00:08:31,190 Αποφάσισα να εφαρμόσει τα χαρακτηριστικά, όπως διαγραφή, εισαγωγή, αναζήτηση, και 198 00:08:31,190 --> 00:08:31,740 διάσχιση - 199 00:08:31,740 --> 00:08:35,210 η τελευταία απλώς να περπατήσετε κατά μήκος του καταλόγου, εκτύπωση των στοιχείων του. 200 00:08:35,210 --> 00:08:36,750 Και τώρα εδώ είναι κύρια ρουτίνα μου. 201 00:08:36,750 --> 00:08:39,890 Και εμείς δεν θα ξοδεύουν πάρα πολύ χρόνο σε αυτά δεδομένου ότι αυτό είναι το είδος της, ελπίζουμε 202 00:08:39,890 --> 00:08:41,780 παλιό καπέλο από τώρα. 203 00:08:41,780 --> 00:08:45,370 >> Πάω να κάνετε τα εξής, ενώ ο χρήστης συνεργάζεται. 204 00:08:45,370 --> 00:08:47,300 Έτσι, ένα, Πάω να εκτυπώσετε από αυτό το μενού. 205 00:08:47,300 --> 00:08:49,420 Και έχω μορφοποιηθεί ως καθαρά όσο θα μπορούσα. 206 00:08:49,420 --> 00:08:52,240 Αν ο χρήστης πληκτρολογεί σε ένα, που σημαίνει που θέλετε να διαγράψετε κάτι. 207 00:08:52,240 --> 00:08:54,560 Αν ο χρήστης πληκτρολογεί σε δύο, που σημαίνει που θέλετε να εισαγάγετε κάτι. 208 00:08:54,560 --> 00:08:55,930 Και ούτω καθεξής. 209 00:08:55,930 --> 00:08:58,270 Πάω να ζητήσει στη συνέχεια στη συνέχεια, για μια εντολή. 210 00:08:58,270 --> 00:08:59,300 Και τότε είμαι πρόκειται να χρησιμοποιήσετε GetInt. 211 00:08:59,300 --> 00:09:02,790 >> Έτσι, αυτό είναι ένα πολύ απλό menuing διεπαφή όπου απλά πρέπει να πληκτρολογήσετε 212 00:09:02,790 --> 00:09:05,270 μια χαρτογράφηση αριθμό σε ένα των εν λόγω εντολών. 213 00:09:05,270 --> 00:09:08,730 Και τώρα έχω ένα ωραίο καθαρό διακόπτη δήλωση που πρόκειται να ενεργοποιήσετε 214 00:09:08,730 --> 00:09:10,090 ό, τι ο χρήστης πληκτρολογήσει μέσα 215 00:09:10,090 --> 00:09:12,180 Και αν πληκτρολογήσει κανείς, εγώ θα καλέστε διαγράψετε και να σπάσουν. 216 00:09:12,180 --> 00:09:14,380 Αν πληκτρολογήσει δύο, εγώ θα καλέστε εισάγετε και να σπάσουν. 217 00:09:14,380 --> 00:09:16,490 >> Και τώρα παρατηρήσετε έχω βάλει κάθε από αυτά στην ίδια γραμμή. 218 00:09:16,490 --> 00:09:18,360 Αυτή είναι μόνο μια υφολογική απόφαση. 219 00:09:18,360 --> 00:09:20,210 Συνήθως έχουμε δει κάτι όπως αυτό. 220 00:09:20,210 --> 00:09:23,260 Αλλά εγώ απλά αποφάσισε, ειλικρινά το πρόγραμμά μου φαινόταν πιο ευανάγνωστο, διότι 221 00:09:23,260 --> 00:09:25,980 ήταν μόνο τέσσερις περιπτώσεις απλά λίστα σαν αυτή. 222 00:09:25,980 --> 00:09:28,360 Απόλυτα νόμιμη χρήση του στυλ. 223 00:09:28,360 --> 00:09:31,480 Και Πάω να το κάνετε αυτό, εφόσον η Ο χρήστης δεν έχει πληκτρολογήσει το μηδέν, η οποία θ 224 00:09:31,480 --> 00:09:33,910 αποφάσισε σημαίνει ότι θέλουν να σταματήσουν το κάπνισμα. 225 00:09:33,910 --> 00:09:36,630 >> Έτσι τώρα παρατηρήστε τι είμαι πρόκειται να κάνουμε εδώ. 226 00:09:36,630 --> 00:09:38,650 Πάω να ελευθερώσει τη λίστα προφανώς. 227 00:09:38,650 --> 00:09:40,230 Αλλά περισσότερα για αυτό σε λίγο. 228 00:09:40,230 --> 00:09:41,640 Ας πρώτα να εκτελέσετε αυτό το πρόγραμμα. 229 00:09:41,640 --> 00:09:45,250 Έτσι, επιτρέψτε μου να κάνω ένα μεγαλύτερο τερματικό παράθυρο, dot slash λίστα 0. 230 00:09:45,250 --> 00:09:49,510 Πάω να πάει μπροστά και τοποθετήστε από πληκτρολόγηση δύο, ένας αριθμός όπως το 50, και τώρα 231 00:09:49,510 --> 00:09:51,590 θα δείτε τη λίστα είναι τώρα 50. 232 00:09:51,590 --> 00:09:53,380 Και το κείμενό μου μόλις κύλιση επάνω ένα κομμάτι. 233 00:09:53,380 --> 00:09:55,940 Έτσι τώρα παρατηρήσετε ο κατάλογος περιλαμβάνει ο αριθμός 50. 234 00:09:55,940 --> 00:09:58,220 >> Ας κάνουμε άλλο ένα ένθετο με τη λήψη δύο. 235 00:09:58,220 --> 00:10:01,630 Ας πληκτρολογήσετε τον αριθμό, όπως ένα. 236 00:10:01,630 --> 00:10:03,940 Λίστα τώρα είναι ένας, που ακολουθείται από 50. 237 00:10:03,940 --> 00:10:06,020 Έτσι, αυτό είναι απλά μια αναπαράσταση κειμένου του καταλόγου. 238 00:10:06,020 --> 00:10:10,550 Και ας προσθέσουμε ένα ακόμη αριθμό, όπως ο αριθμός 42, το οποίο είναι ενδεχομένως 239 00:10:10,550 --> 00:10:14,620 πρόκειται να καταλήξει στη μέση, γιατί Αυτό το πρόγραμμα, ιδίως τα είδη που 240 00:10:14,620 --> 00:10:16,320 στοιχεία, όπως τα ένθετα. 241 00:10:16,320 --> 00:10:17,220 Έτσι εκεί το έχετε. 242 00:10:17,220 --> 00:10:20,730 Σούπερ απλό πρόγραμμα που θα μπορούσε απολύτως έχουν χρησιμοποιήσει μια σειρά, αλλά εγώ 243 00:10:20,730 --> 00:10:23,280 τυχαίνει να είναι χρησιμοποιώντας μια συνδεδεμένη λίστα μόνο έτσι μπορώ να δυναμικά 244 00:10:23,280 --> 00:10:24,610 αναπτυχθούν και να συρρικνωθεί. 245 00:10:24,610 --> 00:10:28,470 >> Έτσι, ας ρίξουμε μια ματιά για την αναζήτηση, αν εκτελέστε την εντολή τρεις, θέλω να αναζητήσετε 246 00:10:28,470 --> 00:10:31,040 για, ας πούμε, με τον αριθμό 43. 247 00:10:31,040 --> 00:10:34,190 Και τίποτα δεν είχε προφανώς βρέθηκε, επειδή πήρα πάλι καμία απάντηση. 248 00:10:34,190 --> 00:10:35,010 Οπότε ας το κάνουμε πάλι. 249 00:10:35,010 --> 00:10:35,690 Αναζήτηση. 250 00:10:35,690 --> 00:10:39,520 Αναζήτηση Ας το για 50, ή μάλλον αναζήτηση για 42, η οποία έχει ένα ωραίο 251 00:10:39,520 --> 00:10:40,850 λίγο λεπτή έννοια. 252 00:10:40,850 --> 00:10:42,610 Και βρήκα το νόημα της ζωής εκεί. 253 00:10:42,610 --> 00:10:44,990 Number 42, αν δεν ξέρετε η αναφορά, το Google. 254 00:10:44,990 --> 00:10:45,350 Εντάξει. 255 00:10:45,350 --> 00:10:47,130 Έτσι, αυτό που έχει αυτό το πρόγραμμα κάνει για μένα; 256 00:10:47,130 --> 00:10:50,660 Είναι ακριβώς μου επέτρεψε να εισάγετε τον τρόπο τώρα και αναζήτηση για τα στοιχεία. 257 00:10:50,660 --> 00:10:53,650 >> Ας γρήγορα προς τα εμπρός, στη συνέχεια, να ότι η λειτουργία μας έριξε μια ματιά 258 00:10:53,650 --> 00:10:55,360 Δευτέρα ως ένα τρέιλερ. 259 00:10:55,360 --> 00:10:59,620 Έτσι, αυτή τη λειτουργία, αξιώνω, αναζητά ένα στοιχείο στη λίστα από την πρώτη 260 00:10:59,620 --> 00:11:03,830 μία, που προτρέπει το χρήστη και στη συνέχεια, καλώντας GetInt για να πάρετε μια πραγματική int 261 00:11:03,830 --> 00:11:05,060 που θέλετε να αναζητήσετε. 262 00:11:05,060 --> 00:11:06,460 >> Στη συνέχεια παρατηρήσετε αυτό. 263 00:11:06,460 --> 00:11:10,690 Πάω να δημιουργήσετε μια προσωρινή μεταβλητή στη γραμμή 188 που ονομάζεται δείκτη - 264 00:11:10,690 --> 00:11:11,270 PTR - 265 00:11:11,270 --> 00:11:12,440 θα μπορούσε να ονομάζεται το τίποτα. 266 00:11:12,440 --> 00:11:16,140 Και είναι ένας δείκτης σε κόμβο επειδή είπα κόμβο * εκεί. 267 00:11:16,140 --> 00:11:19,900 Και είμαι αρχικοποίηση να είναι ίση με πρώτα έτσι ώστε να μπορώ πραγματικά μου έχουν 268 00:11:19,900 --> 00:11:22,860 δάχτυλο, να το πω έτσι, για το πολύ πρώτο στοιχείο της λίστας. 269 00:11:22,860 --> 00:11:27,460 Έτσι, αν το δεξί μου χέρι εδώ είναι PTR είμαι δείχνοντας το ίδιο πράγμα ότι η πρώτη 270 00:11:27,460 --> 00:11:28,670 δείχνει σε. 271 00:11:28,670 --> 00:11:31,430 >> Μέχρι τώρα πίσω στον κώδικα, Τι θα συμβεί στη συνέχεια - 272 00:11:31,430 --> 00:11:35,070 Αυτό είναι ένα κοινό παράδειγμα κατά την επανάληψη πάνω από μια δομή, όπως ένα 273 00:11:35,070 --> 00:11:35,970 συνδεδεμένη λίστα. 274 00:11:35,970 --> 00:11:40,410 Πάω να κάνετε τα εξής, ενώ δείκτης δεν είναι ίση με null Έτσι, ενώ 275 00:11:40,410 --> 00:11:47,530 το δάχτυλό μου δεν δείχνει κάποια null τιμή, εάν δείκτη βέλους Ν ισούται με n. 276 00:11:47,530 --> 00:11:52,290 Θα παρατηρήσετε ότι η πρώτη είναι ό, τι η χρήστης πληκτρολογήσει σε κάθε GetInts αποκαλούν εδώ. 277 00:11:52,290 --> 00:11:54,280 >> Και δείκτη βέλους n σημαίνει τι; 278 00:11:54,280 --> 00:11:59,020 Λοιπόν, αν πάμε πίσω στην εικόνα εδώ, αν έχω ένα δάχτυλο που δείχνει στο 279 00:11:59,020 --> 00:12:02,960 ότι ο πρώτος κόμβος που περιέχει εννέα, το βέλος σημαίνει ουσιαστικά πάει με αυτό 280 00:12:02,960 --> 00:12:08,860 κόμβο και να αρπάξει την τιμή στη θέση n, στην περίπτωση αυτή, το πεδίο δεδομένων που ονομάζεται n. 281 00:12:08,860 --> 00:12:14,120 >> Ως μέρος - και το είδαμε αυτό ένα ζευγάρι πριν από λίγες εβδομάδες, όταν κάποιος ρώτησε - 282 00:12:14,120 --> 00:12:18,840 Αυτή η σύνταξη είναι νέο, αλλά δεν να μας δώσει εξουσίες που 283 00:12:18,840 --> 00:12:20,040 δεν έχουν ήδη. 284 00:12:20,040 --> 00:12:25,325 Ποια ήταν αυτή η φράση ισοδυναμεί με τη χρήση dot σημειογραφία και το αστέρι ένα ζευγάρι 285 00:12:25,325 --> 00:12:29,490 εβδομάδες πριν, όταν τραβηχτεί προς τα πίσω Αυτό το στρώμα είναι λίγο πρόωρα; 286 00:12:29,490 --> 00:12:31,780 >> ΦΟΙΤΗΤΗΣ: [δεν ακούγεται]. 287 00:12:31,780 --> 00:12:38,880 >> ΟΜΙΛΗΤΗΣ 1: Ακριβώς, ήταν αστέρι, και τότε ήταν αστέρι dot n, με 288 00:12:38,880 --> 00:12:41,930 παρένθεση εδώ, το οποίο μοιάζει, ειλικρινά, νομίζω ότι πολλά 289 00:12:41,930 --> 00:12:43,320 πιο αινιγματικά για να διαβάσετε. 290 00:12:43,320 --> 00:12:46,270 Αλλά δείκτη αστέρων, όπως πάντα, μέσα εκεί. 291 00:12:46,270 --> 00:12:49,090 Και μόλις είστε εκεί, ποια δεδομένα τομέα θέλετε να αποκτήσετε πρόσβαση; 292 00:12:49,090 --> 00:12:52,730 Καλά θα χρησιμοποιήσω την τελεία συμβολισμό για να αποκτήσετε πρόσβαση α structs πεδίο δεδομένων, και 293 00:12:52,730 --> 00:12:54,140 Συγκεκριμένα θέλουν n. 294 00:12:54,140 --> 00:12:56,240 >> Ειλικρινά, θα ήθελα να υποστηρίξω ότι αυτή η είναι απλά πιο δύσκολο να το διαβάσετε. 295 00:12:56,240 --> 00:12:58,080 Είναι πιο δύσκολο να θυμηθείτε πού κάνουν οι παρενθέσεις πάει, το 296 00:12:58,080 --> 00:12:59,030 αστέρι και όλα αυτά. 297 00:12:59,030 --> 00:13:02,150 Έτσι, ο κόσμος υιοθέτησε κάποια συντακτική ζάχαρη, να το πω έτσι. 298 00:13:02,150 --> 00:13:04,740 Ακριβώς ένα sexy τρόπος για να πούμε, Αυτό είναι ισοδύναμο, και 299 00:13:04,740 --> 00:13:05,970 ίσως πιο διαισθητικό. 300 00:13:05,970 --> 00:13:09,600 Αν δείκτη είναι πράγματι ένας δείκτης, ο μέσα συμβολισμό βέλος πάμε εκεί και να βρει 301 00:13:09,600 --> 00:13:11,890 το πεδίο σε αυτή την περίπτωση ονομάζεται n. 302 00:13:11,890 --> 00:13:13,660 >> Έτσι, αν μπορώ να το βρω, παρατηρήστε τι να κάνω. 303 00:13:13,660 --> 00:13:17,430 Απλά εκτυπώσετε, βρήκα τοις εκατό i, συνδέοντας την τιμή για το int. 304 00:13:17,430 --> 00:13:20,730 Καλώ τον ύπνο για ένα δευτερόλεπτο μόνο για το είδος των πραγμάτων παύση στην οθόνη για να 305 00:13:20,730 --> 00:13:22,900 δίνουν στο χρήστη ένα δεύτερο για να απορροφήσει τι ακριβώς συνέβη. 306 00:13:22,900 --> 00:13:24,290 Και τότε θα σπάσει. 307 00:13:24,290 --> 00:13:26,330 Διαφορετικά, τι μπορώ να κάνω; 308 00:13:26,330 --> 00:13:30,960 Μπορώ να ενημερώσω το δείκτη στην ίση βέλος του δείκτη επόμενο. 309 00:13:30,960 --> 00:13:35,840 >> Έτσι απλά για να είμαι σαφής, αυτό σημαίνει ότι πάμε , εκεί χρησιμοποιώντας old-school σημειογραφία μου. 310 00:13:35,840 --> 00:13:39,580 Έτσι, αυτό σημαίνει απλά να πάει σε ό, τι είστε δείχνοντας, τα οποία σε πολύ 311 00:13:39,580 --> 00:13:43,660 πρώτη περίπτωση είναι ότι είμαι δείχνοντας η struct με εννέα σε αυτό. 312 00:13:43,660 --> 00:13:44,510 Έτσι, έχω πάει εκεί. 313 00:13:44,510 --> 00:13:47,880 Και τότε ο συμβολισμός σημαίνει, πάρει την τιμή στην επόμενη. 314 00:13:47,880 --> 00:13:50,470 >> Αλλά η αξία, ακόμα κι αν είναι που ως στενός, είναι απλά ένας αριθμός. 315 00:13:50,470 --> 00:13:51,720 Είναι μια αριθμητική διεύθυνση. 316 00:13:51,720 --> 00:13:55,670 Έτσι, αυτή η μία γραμμή κώδικα, είτε γραμμένο σαν αυτό, το πιο αινιγματικό 317 00:13:55,670 --> 00:14:00,190 τρόπο, ή σαν αυτή, το ελαφρώς πιο διαισθητικό τρόπο, σημαίνει απλά μετακινήστε το χέρι μου 318 00:14:00,190 --> 00:14:03,460 από τον πρώτο κόμβο στον επόμενο, και στη συνέχεια το επόμενο, και στη συνέχεια το 319 00:14:03,460 --> 00:14:05,320 επόμενη, και ούτω καθεξής. 320 00:14:05,320 --> 00:14:09,920 >> Γι 'αυτό και δεν θα σταθώ στην άλλη υλοποιήσεις εισαγωγή και διαγραφή 321 00:14:09,920 --> 00:14:14,030 και διάσχισης, οι δύο πρώτοι από τα οποία είναι αρκετά εμπλέκονται. 322 00:14:14,030 --> 00:14:17,010 Και νομίζω ότι είναι αρκετά εύκολο να πάρει χάνεται όταν το κάνουν προφορικά. 323 00:14:17,010 --> 00:14:19,890 Αλλά τι μπορούμε να κάνουμε εδώ είναι προσπαθούν να καθορίσουν τον τρόπο 324 00:14:19,890 --> 00:14:21,640 καλύτερα να το κάνετε αυτό οπτικά. 325 00:14:21,640 --> 00:14:24,800 Επειδή θα ήθελα να προτείνω ότι, αν θέλετε να εισαγάγετε τα στοιχεία σε αυτό 326 00:14:24,800 --> 00:14:26,680 υπάρχουσα λίστα, η οποία έχει πέντε στοιχεία - 327 00:14:26,680 --> 00:14:29,530 9, 17, 22, 26, και 33 - 328 00:14:29,530 --> 00:14:33,300 αν επρόκειτο να εφαρμόσει αυτό κώδικα, θα πρέπει να εξετάσει πώς να πάει 329 00:14:33,300 --> 00:14:34,160 για να γίνει αυτό. 330 00:14:34,160 --> 00:14:37,720 >> Και θα ήθελα να προτείνω βηματάκια σύμφωνα με την οποία, στην περίπτωση αυτή Εννοώ, τι είναι 331 00:14:37,720 --> 00:14:41,090 τα πιθανά σενάρια που ενδέχεται να συναντήσουν σε γενικές γραμμές; 332 00:14:41,090 --> 00:14:44,120 Κατά την εφαρμογή ένθετο για ένα συνδεδεμένο λίστα, αυτό συμβαίνει ακριβώς να είναι ένα 333 00:14:44,120 --> 00:14:46,090 συγκεκριμένο παράδειγμα του μεγέθους πέντε. 334 00:14:46,090 --> 00:14:50,420 Λοιπόν, αν θέλετε να εισαγάγετε έναν αριθμό, ήθελα να πω το νούμερο ένα, και 335 00:14:50,420 --> 00:14:53,380 διατήρηση σειρά ταξινόμησης, όπου προφανώς κάνει το νούμερο ένα πρέπει να 336 00:14:53,380 --> 00:14:55,686 πάει στο συγκεκριμένο παράδειγμα; 337 00:14:55,686 --> 00:14:56,840 Όπως και στην αρχή. 338 00:14:56,840 --> 00:15:00,030 >> Αλλά αυτό που είναι ενδιαφέρον είναι ότι υπάρχει αν θέλετε να εισαγάγετε ένα σε αυτό 339 00:15:00,030 --> 00:15:04,100 κατάλογο, τις ειδικές ανάγκες δείκτη να ενημερώνεται προφανώς; 340 00:15:04,100 --> 00:15:04,610 Πρώτον. 341 00:15:04,610 --> 00:15:07,830 Έτσι, θα έλεγα, αυτή είναι η πρώτη περίπτωση ότι ίσως να θέλετε να εξετάσει το ενδεχόμενο, η 342 00:15:07,830 --> 00:15:11,140 σενάριο που θα περιλαμβάνει την εισαγωγή σε η αρχή της λίστας. 343 00:15:11,140 --> 00:15:15,400 >> Ας κόβω από ίσως ένα τόσο εύκολο ή ακόμα και ευκολότερη υπόθεση, μιλώντας σχετικά. 344 00:15:15,400 --> 00:15:18,110 Ας υποθέσουμε ότι θέλετε να εισαγάγετε το τον αριθμό 35 σε ταξινομημένη σειρά. 345 00:15:18,110 --> 00:15:20,600 Ανήκει προφανώς εκεί. 346 00:15:20,600 --> 00:15:25,320 Λοιπόν, τι δείκτη είναι προφανώς πρόκειται να πρέπει να ενημερώνεται σε αυτό το σενάριο; 347 00:15:25,320 --> 00:15:30,060 Δείκτη 34 είναι να γίνει δεν είναι null αλλά η διεύθυνση του struct 348 00:15:30,060 --> 00:15:31,800 περιέχει τον αριθμό 35. 349 00:15:31,800 --> 00:15:32,750 Έτσι, αυτό είναι υπόθεση δύο. 350 00:15:32,750 --> 00:15:36,190 Έτσι, ήδη, είμαι το είδος του quantizing πόση δουλειά έχω να κάνω εδώ. 351 00:15:36,190 --> 00:15:39,880 >> Και τέλος, η προφανής περίπτωση είναι μεσαία Πράγματι, στη μέση, αν θέλω να 352 00:15:39,880 --> 00:15:45,870 εισάγετε κάτι σαν π.χ. 23, που πηγαίνει μεταξύ του 23 και του 26, αλλά 353 00:15:45,870 --> 00:15:48,680 τώρα τα πράγματα γίνονται λίγο πιο που εμπλέκονται, διότι ό, τι 354 00:15:48,680 --> 00:15:52,800 δείκτες πρέπει να αλλάξει; 355 00:15:52,800 --> 00:15:56,680 Έτσι 22 πρέπει προφανώς να αλλάξει γιατί δεν μπορεί να το σημείο σε 26 πια. 356 00:15:56,680 --> 00:16:00,320 Αυτός πρέπει να δείχνει προς το νέο κόμβο που Θα πρέπει να διαθέσουν καλώντας 357 00:16:00,320 --> 00:16:01,770 malloc ή κάποιο ισοδύναμο. 358 00:16:01,770 --> 00:16:05,990 >> Αλλά τότε θα πρέπει, επίσης, ότι το νέο κόμβο, 23 στην περίπτωση αυτή, για να έχει δείκτη του 359 00:16:05,990 --> 00:16:07,870 δείχνει σε ποιον; 360 00:16:07,870 --> 00:16:08,560 26. 361 00:16:08,560 --> 00:16:10,380 Και εκεί πρόκειται να είναι μια σειρά των πράξεων εδώ. 362 00:16:10,380 --> 00:16:13,410 Διότι, αν το κάνω αυτό ανόητα, και εγώ για την έναρξη παράδειγμα κατά την έναρξη της 363 00:16:13,410 --> 00:16:16,040 ο κατάλογος, και ο στόχος μου είναι να τοποθετήσετε 23. 364 00:16:16,040 --> 00:16:18,610 Και μπορώ να ελέγξω, αυτό ανήκει εδώ, κοντά εννιά; 365 00:16:18,610 --> 00:16:18,950 Όχι. 366 00:16:18,950 --> 00:16:20,670 Μήπως ανήκει εδώ, δίπλα στο 17; 367 00:16:20,670 --> 00:16:20,940 Όχι. 368 00:16:20,940 --> 00:16:22,530 Μήπως ανήκει εδώ δίπλα στο 22; 369 00:16:22,530 --> 00:16:23,300 Ναι. 370 00:16:23,300 --> 00:16:26,400 >> Τώρα, αν είμαι ανόητο εδώ, και όχι σκέφτεται αυτό μέσα, θα μπορούσα 371 00:16:26,400 --> 00:16:28,320 διαθέσει νέο κόμβο μου για 23. 372 00:16:28,320 --> 00:16:32,080 Θα ήθελα να ενημερώσετε το δείκτη από ο κόμβος που ονομάζεται 22, δείχνοντας 373 00:16:32,080 --> 00:16:33,080 το στο νέο κόμβο. 374 00:16:33,080 --> 00:16:36,140 Και τότε τι έχω να ενημερώσετε δείκτη του νέου κόμβου να είναι; 375 00:16:36,140 --> 00:16:38,120 >> ΦΟΙΤΗΤΗΣ: [δεν ακούγεται]. 376 00:16:38,120 --> 00:16:38,385 >> ΟΜΙΛΗΤΗΣ 1: Ακριβώς. 377 00:16:38,385 --> 00:16:39,710 Τονίζοντας 26. 378 00:16:39,710 --> 00:16:45,590 Αλλά κυβερνάνε ρε αν δεν είχα ήδη ενημερώσει Δείκτη 22 για να επισημάνει αυτόν τον τύπο, και 379 00:16:45,590 --> 00:16:48,260 τώρα έχω ορφανά, ενώ το υπόλοιπο του καταλόγου, να το πω έτσι. 380 00:16:48,260 --> 00:16:52,140 Έτσι σειρά των πράξεων εδώ πρόκειται να είναι σημαντική. 381 00:16:52,140 --> 00:16:55,100 >> Για να το κάνετε αυτό θα μπορούσε να κλέψω, ας πούμε, έξι εθελοντές. 382 00:16:55,100 --> 00:16:57,650 Και ας δούμε αν δεν μπορούμε να το κάνουμε αυτό οπτικά αντί του κώδικα-σοφός. 383 00:16:57,650 --> 00:16:59,330 Και έχουμε κάποια όμορφη στρες μπάλες για σας σήμερα. 384 00:16:59,330 --> 00:17:02,510 Εντάξει, πώς για ένα, δύο, στην πίσω - στο τέλος εκεί. 385 00:17:02,510 --> 00:17:04,530 τρεις, τέσσερις, δύο από σας παιδιά για το τέλος. 386 00:17:04,530 --> 00:17:05,579 Και πέντε, έξι. 387 00:17:05,579 --> 00:17:05,839 Σίγουρα. 388 00:17:05,839 --> 00:17:06,450 Πέντε και έξι. 389 00:17:06,450 --> 00:17:08,390 Εντάξει και θα έρθει για σας παιδιά την επόμενη φορά. 390 00:17:08,390 --> 00:17:09,640 Εντάξει, έλα πάνω. 391 00:17:09,640 --> 00:17:12,010 392 00:17:12,010 --> 00:17:14,819 >> Εντάξει, αφού είσαι εδώ πρώτα, θα θέλατε να είναι η μία αδέξια 393 00:17:14,819 --> 00:17:16,119 σε γυαλί Google εδώ; 394 00:17:16,119 --> 00:17:19,075 Εντάξει, ναι, εντάξει, γυαλί, εγγραφή βίντεο. 395 00:17:19,075 --> 00:17:22,720 396 00:17:22,720 --> 00:17:24,589 Εντάξει, είστε καλοί να πάτε. 397 00:17:24,589 --> 00:17:27,950 >> Εντάξει, οπότε αν εσείς μπορεί να έρθει πάνω εδώ, έχω προετοιμαστεί εκ των προτέρων 398 00:17:27,950 --> 00:17:30,110 ορισμένοι αριθμοί. 399 00:17:30,110 --> 00:17:31,240 Εντάξει, έλα εδώ. 400 00:17:31,240 --> 00:17:33,440 Και γιατί δεν πας λίγο περαιτέρω με αυτόν τον τρόπο. 401 00:17:33,440 --> 00:17:35,520 Και ας δούμε, τι είναι το όνομά σας, με το ποτήρι Google; 402 00:17:35,520 --> 00:17:35,910 >> ΣΠΟΥΔΑΣΤΩΝ: Ben. 403 00:17:35,910 --> 00:17:36,230 >> ΟΜΙΛΗΤΗΣ 1: Μπεν; 404 00:17:36,230 --> 00:17:38,380 Εντάξει, Μπεν, θα είναι η πρώτη, κυριολεκτικά. 405 00:17:38,380 --> 00:17:40,580 Έτσι θα πάμε για να σας στείλουμε στο τέλος του σταδίου. 406 00:17:40,580 --> 00:17:41,670 Εντάξει, και το όνομά σας; 407 00:17:41,670 --> 00:17:41,990 >> ΣΠΟΥΔΑΣΤΩΝ: Jason. 408 00:17:41,990 --> 00:17:44,530 >> ΟΜΙΛΗΤΗΣ 1: Jason, εντάξει θα είστε είναι ο αριθμός εννέα. 409 00:17:44,530 --> 00:17:46,700 Έτσι, εάν θέλετε να ακολουθήσετε Ben με αυτόν τον τρόπο. 410 00:17:46,700 --> 00:17:47,010 >> ΣΠΟΥΔΑΣΤΩΝ: Jill. 411 00:17:47,010 --> 00:17:49,630 >> ΟΜΙΛΗΤΗΣ 1: Jill, θα πάμε να 17, το οποίο, αν είχα κάνει αυτό περισσότερο 412 00:17:49,630 --> 00:17:51,260 έξυπνα, θα είχα ξεκίνησε στο άλλο άκρο. 413 00:17:51,260 --> 00:17:52,370 Μπορείτε να πάτε με αυτόν τον τρόπο. 414 00:17:52,370 --> 00:17:53,030 22. 415 00:17:53,030 --> 00:17:53,670 Και εσύ είσαι; 416 00:17:53,670 --> 00:17:53,980 >> ΣΠΟΥΔΑΣΤΩΝ: Mary. 417 00:17:53,980 --> 00:17:56,130 >> ΟΜΙΛΗΤΗΣ 1: Mary, θα είναι 22. 418 00:17:56,130 --> 00:17:58,420 Και το όνομά σου είναι; 419 00:17:58,420 --> 00:17:58,810 >> ΣΠΟΥΔΑΣΤΩΝ: Chris. 420 00:17:58,810 --> 00:18:00,100 >> ΟΜΙΛΗΤΗΣ 1: Chris, θα είναι 26. 421 00:18:00,100 --> 00:18:00,740 Και μετά τέλος. 422 00:18:00,740 --> 00:18:01,400 >> ΣΠΟΥΔΑΣΤΩΝ: Diana. 423 00:18:01,400 --> 00:18:02,670 >> ΟΜΙΛΗΤΗΣ 1: Diana, θα είναι 34. 424 00:18:02,670 --> 00:18:03,920 Έτσι θα έρθει για πάνω από εδώ. 425 00:18:03,920 --> 00:18:06,360 >> Εντάξει, τόσο τέλεια ταξινόμηση διατάξει ήδη. 426 00:18:06,360 --> 00:18:09,600 Και ας πάμε μπροστά και να το κάνετε αυτό έτσι ώστε να μπορούμε πραγματικά - 427 00:18:09,600 --> 00:18:11,720 Ben είστε ακριβώς το είδος της ψάχνει έξω στο πουθενά εκεί. 428 00:18:11,720 --> 00:18:15,670 Εντάξει, ας πάμε μπροστά και να το απεικονίσω αυτό χρησιμοποιώντας τα χέρια, σαν ήμουν ακριβώς, 429 00:18:15,670 --> 00:18:16,250 τι συμβαίνει. 430 00:18:16,250 --> 00:18:19,540 Έτσι προχωρήστε και να δοθείτε πόδι ή δύο μεταξύ σας. 431 00:18:19,540 --> 00:18:22,900 Και να προχωρήσει και να το σημείο με το ένα χέρι για να όποιος κι αν θα πρέπει να δείχνει σε 432 00:18:22,900 --> 00:18:23,470 με βάση αυτό. 433 00:18:23,470 --> 00:18:25,890 Και αν είστε null ακριβώς σημείο κατ 'ευθείαν κάτω στο πάτωμα. 434 00:18:25,890 --> 00:18:27,690 Εντάξει, τόσο καλό. 435 00:18:27,690 --> 00:18:32,290 >> Έτσι τώρα έχουμε μια συνδεδεμένη λίστα, και επιτρέψτε μου να προτείνουν πως θα παίξει το ρόλο της 436 00:18:32,290 --> 00:18:35,110 PTR, γι 'αυτό δεν θα τον κόπο που μεταφέρουν αυτό γύρω. 437 00:18:35,110 --> 00:18:37,830 Και τότε - κάποιον ηλίθιο σύμβαση - μπορείτε να καλέσετε αυτό ό, τι θέλετε - 438 00:18:37,830 --> 00:18:39,800 δείκτη προκάτοχό του, προβλ δείκτη - 439 00:18:39,800 --> 00:18:43,930 Είναι ακριβώς το παρατσούκλι που έδωσε στην δείγμα κώδικα μας για το αριστερό μου χέρι. 440 00:18:43,930 --> 00:18:47,240 Η άλλη πλευρά που πρόκειται να κρατώντας παρακολουθείτε ποιος είναι ποιος στην 441 00:18:47,240 --> 00:18:48,400 ακόλουθα σενάρια. 442 00:18:48,400 --> 00:18:52,390 >> Έτσι, ας υποθέσουμε ότι, κατ 'αρχάς, θέλω να κόβω από ότι το πρώτο παράδειγμα της εισαγωγής, ας πούμε 443 00:18:52,390 --> 00:18:54,330 20, στον κατάλογο. 444 00:18:54,330 --> 00:18:57,160 Έτσι, Πάω να πρέπει κάποιος να ενσωματώνουν τον αριθμό 20 για μας. 445 00:18:57,160 --> 00:18:58,950 Γι 'αυτό πρέπει με κάποιον malloc από το ακροατήριο. 446 00:18:58,950 --> 00:18:59,380 Ανέβα. 447 00:18:59,380 --> 00:19:00,340 Ποιο είναι το όνομά σου; 448 00:19:00,340 --> 00:19:01,300 >> ΣΠΟΥΔΑΣΤΩΝ: Brian. 449 00:19:01,300 --> 00:19:05,270 >> ΟΜΙΛΗΤΗΣ 1: Brian, εντάξει, έτσι ώστε να πρέπει να είναι ο κόμβος που περιέχει 20. 450 00:19:05,270 --> 00:19:06,810 Εντάξει, έλα εδώ. 451 00:19:06,810 --> 00:19:10,025 Και προφανώς, όπου δεν Brian ανήκει; 452 00:19:10,025 --> 00:19:12,190 Έτσι, στη μέση της - στην πραγματικότητα, περιμένετε ένα λεπτό. 453 00:19:12,190 --> 00:19:13,420 Κάνουμε αυτό εκτός λειτουργίας. 454 00:19:13,420 --> 00:19:17,170 Κάνουμε αυτό ένα πολύ πιο δύσκολο από ό, τι χρειάζεται να είναι στην πρώτη. 455 00:19:17,170 --> 00:19:21,210 Εντάξει, θα πάμε στην ελεύθερη Brian και realloc Brian και πέντε. 456 00:19:21,210 --> 00:19:23,680 >> ΕΝΤΑΞΕΙ, έτσι τώρα θέλουμε να εισάγετε Brian και πέντε. 457 00:19:23,680 --> 00:19:25,960 Έτσι, έλα εδώ δίπλα Ben μόνο για μια στιγμή. 458 00:19:25,960 --> 00:19:28,250 Και μπορείτε να πείτε προφανώς όπου αυτή η ιστορία πηγαίνει. 459 00:19:28,250 --> 00:19:30,500 Αλλά ας σκεφτούμε προσεκτικά σχετικά με η σειρά των πράξεων. 460 00:19:30,500 --> 00:19:32,880 Και είναι ακριβώς αυτή η οπτική που πρόκειται να παρατάξει 461 00:19:32,880 --> 00:19:34,080 με αυτό το δείγμα κώδικα. 462 00:19:34,080 --> 00:19:40,120 Έτσι, εδώ έχω PTR επισημαίνοντας αρχικά όχι σε Ben, per se, αλλά σε ό, τι 463 00:19:40,120 --> 00:19:43,245 εκτιμούν ότι περιέχει, η οποία σε αυτή την περίπτωση είναι - τι είναι το όνομά σας και πάλι; 464 00:19:43,245 --> 00:19:43,670 >> ΣΠΟΥΔΑΣΤΩΝ: Jason. 465 00:19:43,670 --> 00:19:47,350 >> ΟΜΙΛΗΤΗΣ 1: Jason, έτσι και οι δύο Μπεν και εγώ είμαστε δείχνοντας Jason αυτή τη στιγμή. 466 00:19:47,350 --> 00:19:49,700 Έτσι, τώρα έχω να καθορίσει, πού Brian ανήκει; 467 00:19:49,700 --> 00:19:53,500 Έτσι, το μόνο πράγμα που έχω πρόσβαση σε τώρα είναι n στοιχείο του δεδομένων. 468 00:19:53,500 --> 00:19:58,280 Έτσι, Πάω να ελέγξει, είναι Brian λιγότερο από Jason; 469 00:19:58,280 --> 00:19:59,770 Η απάντηση είναι αλήθεια. 470 00:19:59,770 --> 00:20:03,680 >> Έτσι, αυτό που χρειάζεται τώρα για να συμβεί αυτό, με τη σωστή σειρά; 471 00:20:03,680 --> 00:20:07,120 Θα πρέπει να ενημερώσετε πόσα δείκτες συνολικά σε αυτή την ιστορία; 472 00:20:07,120 --> 00:20:10,720 Όταν το χέρι μου εξακολουθεί να δείχνει σε Jason, και το χέρι σας - αν θέλετε να 473 00:20:10,720 --> 00:20:12,930 βάλετε το χέρι σας, όπως, το είδος, I Δεν ξέρω, ένα ερωτηματικό. 474 00:20:12,930 --> 00:20:14,070 Εντάξει, καλά. 475 00:20:14,070 --> 00:20:15,670 >> Εντάξει, έτσι ώστε να έχουν λίγα υποψηφίων. 476 00:20:15,670 --> 00:20:20,500 Είτε Ben ή εγώ ή και Brian ή Jason ή όλοι οι άλλοι, που 477 00:20:20,500 --> 00:20:21,370 δείκτες πρέπει να αλλάξουν; 478 00:20:21,370 --> 00:20:23,260 Πόσοι συνολικά; 479 00:20:23,260 --> 00:20:24,080 >> Εντάξει, έτσι ώστε δύο. 480 00:20:24,080 --> 00:20:27,090 Pointer μου δεν έχει τόση σημασία πια επειδή είμαι μόνο προσωρινή. 481 00:20:27,090 --> 00:20:31,370 Έτσι είναι αυτά τα δύο παιδιά, κατά πάσα πιθανότητα, τόσο Μπεν και Brian. 482 00:20:31,370 --> 00:20:34,410 Έτσι, επιτρέψτε μου να προτείνω να ενημερώσετε Ben, αφού είναι το πρώτο. 483 00:20:34,410 --> 00:20:36,350 Το πρώτο στοιχείο αυτού του καταλόγου είναι τώρα πρόκειται να είναι Brian. 484 00:20:36,350 --> 00:20:38,070 Έτσι, το σημείο Ben στο Brian. 485 00:20:38,070 --> 00:20:39,320 Εντάξει, τώρα τι; 486 00:20:39,320 --> 00:20:41,950 487 00:20:41,950 --> 00:20:43,460 >> Ποιος παίρνει επισήμανε σε ποιον; 488 00:20:43,460 --> 00:20:44,710 >> ΦΟΙΤΗΤΗΣ: [δεν ακούγεται]. 489 00:20:44,710 --> 00:20:46,180 >> ΟΜΙΛΗΤΗΣ 1: Εντάξει έτσι Brian έχει στο σημείο στο Jason. 490 00:20:46,180 --> 00:20:48,360 Αλλά έχω χάσει τα ίχνη του εν λόγω δείκτη; 491 00:20:48,360 --> 00:20:49,980 Ξέρω όπου ο Ιάσονας είναι; 492 00:20:49,980 --> 00:20:50,790 >> ΦΟΙΤΗΤΗΣ: [δεν ακούγεται]. 493 00:20:50,790 --> 00:20:52,620 >> ΟΜΙΛΗΤΗΣ 1: να κάνω, δεδομένου ότι είμαι η προσωρινή δείκτη. 494 00:20:52,620 --> 00:20:55,110 Και προφανώς, δεν έχω αλλάξει να επισημάνει στο νέο κόμβο. 495 00:20:55,110 --> 00:20:58,300 Έτσι μπορούμε να έχουμε απλά Brian σημείο σε όποιον Είμαι δείχνοντας. 496 00:20:58,300 --> 00:20:59,000 Και τελειώσαμε. 497 00:20:59,000 --> 00:21:01,890 Έτσι, μία περίπτωση, εισαγωγής στο αρχή της λίστας. 498 00:21:01,890 --> 00:21:02,950 Υπήρχαν δύο βασικά στάδια. 499 00:21:02,950 --> 00:21:06,750 Ένα, θα πρέπει να ενημερώσετε τον Ben, και στη συνέχεια πρέπει επίσης να ενημερώσετε Brian. 500 00:21:06,750 --> 00:21:09,230 Και τότε δεν χρειάζεται να ασχοληθείτε traipsing μέσα από το υπόλοιπο της 501 00:21:09,230 --> 00:21:12,680 λίστα, γιατί έχουμε ήδη βρεθεί του θέση, γιατί ανήκε στην 502 00:21:12,680 --> 00:21:14,080 αριστερά του πρώτου στοιχείου. 503 00:21:14,080 --> 00:21:15,400 >> Εντάξει, αρκετά απλή. 504 00:21:15,400 --> 00:21:18,110 Στην πραγματικότητα, αισθάνεται σαν να είμαστε σχεδόν καθιστώντας αυτό το πολύ περίπλοκο. 505 00:21:18,110 --> 00:21:20,240 Οπότε ας πάμε τώρα κόβω από το τέλος του καταλόγου, και να δούμε πού 506 00:21:20,240 --> 00:21:21,380 η πολυπλοκότητα ξεκινά. 507 00:21:21,380 --> 00:21:24,560 Έτσι, αν τώρα, alloc από το ακροατήριο. 508 00:21:24,560 --> 00:21:25,540 Όποιος θέλει να παίξει 55; 509 00:21:25,540 --> 00:21:26,700 Εντάξει, είδα το χέρι σας πρώτα. 510 00:21:26,700 --> 00:21:29,620 Ανέβα. 511 00:21:29,620 --> 00:21:30,030 Ναι. 512 00:21:30,030 --> 00:21:31,177 Ποιο είναι το όνομά σου; 513 00:21:31,177 --> 00:21:32,310 >> ΦΟΙΤΗΤΗΣ: [δεν ακούγεται]. 514 00:21:32,310 --> 00:21:33,240 >> ΟΜΙΛΗΤΗΣ 1: Habata. 515 00:21:33,240 --> 00:21:33,890 Εντάξει, έλα επάνω. 516 00:21:33,890 --> 00:21:35,730 Θα είναι ο αριθμός 55. 517 00:21:35,730 --> 00:21:37,820 Έτσι, φυσικά, ανήκουν στο τέλος της λίστας. 518 00:21:37,820 --> 00:21:41,850 Οπότε ας επαναλάβει την προσομοίωση με μένα είναι το PTR για μια στιγμή. 519 00:21:41,850 --> 00:21:44,050 Έτσι είμαι πρώτος πρόκειται να επισημάνει ό, τι Μπεν δείχνοντας. 520 00:21:44,050 --> 00:21:45,900 Είμαστε και οι δύο δείχνουν τώρα στο Brian. 521 00:21:45,900 --> 00:21:48,420 Έτσι, 55 δεν είναι μικρότερη από πέντε. 522 00:21:48,420 --> 00:21:52,510 Έτσι, Πάω να ενημερωθώ από επισημαίνοντας δείκτη επόμενο Brian, ο οποίος 523 00:21:52,510 --> 00:21:54,450 τώρα είναι φυσικά Jason. 524 00:21:54,450 --> 00:21:57,310 55 δεν είναι μικρότερη από εννέα, έτσι Πάω να ενημερώσετε PTR. 525 00:21:57,310 --> 00:21:58,890 Πάω να ενημερώσετε PTR. 526 00:21:58,890 --> 00:22:02,290 Πάω να ενημερώσετε PTR Ι που πηγαίνει να ενημερώσετε PTR. 527 00:22:02,290 --> 00:22:05,060 Και Πάω να - Χμμ, τι είναι το όνομά σας και πάλι; 528 00:22:05,060 --> 00:22:05,560 >> ΣΠΟΥΔΑΣΤΩΝ: Diana. 529 00:22:05,560 --> 00:22:09,190 >> ΟΜΙΛΗΤΗΣ 1: Diana δείχνει, βέβαια, σε null με το αριστερό χέρι. 530 00:22:09,190 --> 00:22:13,030 Έτσι, όταν κάνει Habata πραγματικότητα ανήκουν καθαρά; 531 00:22:13,030 --> 00:22:15,050 Προς τα αριστερά, εδώ. 532 00:22:15,050 --> 00:22:19,460 Λοιπόν, πώς μπορώ να ξέρω να την βάλει εδώ Νομίζω ότι έχω μαντάρα. 533 00:22:19,460 --> 00:22:22,420 Γιατί αυτό είναι PTR τέχνης αυτή τη στιγμή; 534 00:22:22,420 --> 00:22:23,240 Null. 535 00:22:23,240 --> 00:22:25,580 Έτσι, ακόμη και αν, οπτικά, μπορούμε Προφανώς δείτε όλα αυτά 536 00:22:25,580 --> 00:22:26,610 παιδιά εδώ στη σκηνή. 537 00:22:26,610 --> 00:22:29,680 Δεν έχω παρακολουθημένη του προηγούμενου πρόσωπο στη λίστα. 538 00:22:29,680 --> 00:22:33,210 Δεν έχω ένα δάχτυλο επισημαίνοντας, σε αυτή την περίπτωση, ο κόμβος αριθμό 34. 539 00:22:33,210 --> 00:22:34,760 >> Ας αρχίσουμε πραγματικά αυτή τελειώσει. 540 00:22:34,760 --> 00:22:37,560 Μέχρι τώρα εγώ πραγματικά χρειάζεται μια δεύτερη τοπική μεταβλητή. 541 00:22:37,560 --> 00:22:40,980 Και αυτό είναι αυτό που θα δείτε στο πραγματικό δείγμα κώδικα C, όπου, όπως πάω, 542 00:22:40,980 --> 00:22:45,860 όταν μπορώ να ενημερώσω το δεξί μου χέρι να επισημάνω Jason, αφήνοντας έτσι Brian πίσω, I 543 00:22:45,860 --> 00:22:51,440 καλύτερα να αρχίσετε να χρησιμοποιείτε το αριστερό χέρι μου για να ενημερωθούν όταν ήμουν, έτσι ώστε, όπως πάω 544 00:22:51,440 --> 00:22:52,700 μέσω αυτού του καταλόγου - 545 00:22:52,700 --> 00:22:55,040 πιο αδέξια από ό, τι είχα την πρόθεση τώρα εδώ οπτικά - 546 00:22:55,040 --> 00:22:56,740 Πάω να φτάσουμε στην τέλος της λίστας. 547 00:22:56,740 --> 00:23:00,020 >> Αυτό το χέρι εξακολουθεί να είναι μηδενική, η οποία είναι αρκετά άχρηστο, εκτός από το να αναφέρουν 548 00:23:00,020 --> 00:23:02,980 Είμαι σαφώς στο τέλος της λίστας, αλλά τουλάχιστον τώρα έχω αυτό 549 00:23:02,980 --> 00:23:08,270 δείκτη του προκατόχου δείχνει εδώ, έτσι τώρα τι χέρια και τι δείκτες χρειάζονται 550 00:23:08,270 --> 00:23:10,150 να ενημερωθεί; 551 00:23:10,150 --> 00:23:13,214 Ποιανού το χέρι θέλεις να αναμορφώσουν πρώτα; 552 00:23:13,214 --> 00:23:15,190 >> ΦΟΙΤΗΤΗΣ: [δεν ακούγεται]. 553 00:23:15,190 --> 00:23:16,220 >> ΟΜΙΛΗΤΗΣ 1: Εντάξει, έτσι Νταϊάνα. 554 00:23:16,220 --> 00:23:21,110 Πού θέλετε να επισημάνω Αριστερό δείκτη Νταϊάνα σε; 555 00:23:21,110 --> 00:23:23,620 Σε 55, προφανώς, έτσι ώστε έχουμε τοποθετηθεί εκεί. 556 00:23:23,620 --> 00:23:25,560 Και πού θα πρέπει 55 δείκτη πάτε; 557 00:23:25,560 --> 00:23:27,000 Down, που αντιπροσωπεύουν null. 558 00:23:27,000 --> 00:23:28,890 Και τα χέρια μου, σε αυτό το σημείο, δεν σημασία επειδή ήταν απλά 559 00:23:28,890 --> 00:23:30,070 προσωρινές μεταβλητές. 560 00:23:30,070 --> 00:23:31,030 Έτσι, τώρα τελειώσαμε. 561 00:23:31,030 --> 00:23:34,650 >> Έτσι, η πρόσθετη πολυπλοκότητα εκεί - και δεν είναι ότι σκληρά για την εφαρμογή, 562 00:23:34,650 --> 00:23:38,660 αλλά χρειαζόμαστε μια δευτερεύουσα μεταβλητή για να βεβαιωθείτε ότι πριν προχωρήσουμε δικαίωμά μου 563 00:23:38,660 --> 00:23:42,140 Αντίθετα, μπορώ να ενημερώσω την αξία του αριστερού μου χέρι, προβλ δείκτη σε αυτή την περίπτωση, έτσι ώστε 564 00:23:42,140 --> 00:23:45,860 ότι έχω ένα κενό δείκτη να παρακολουθείτε πού ήμουν. 565 00:23:45,860 --> 00:23:49,360 Τώρα, ως ένα μέρος, εάν σκέφτεστε αυτό μέσα, αυτό το αισθάνεται σαν να είναι μια 566 00:23:49,360 --> 00:23:51,490 λίγο ενοχλητικό να πρέπει να κρατήσουν παρακολουθείτε αυτό το αριστερό χέρι. 567 00:23:51,490 --> 00:23:54,015 >> Τι θα ήταν μια άλλη λύση σε αυτό το πρόβλημα έχουν; 568 00:23:54,015 --> 00:23:56,500 Αν έχεις να επανασχεδιάσουν τα δεδομένα δομή μιλάμε 569 00:23:56,500 --> 00:23:59,630 μέσα από αυτή τη στιγμή; 570 00:23:59,630 --> 00:24:02,690 Εάν αυτό ακριβώς το είδος του αισθάνεται λίγο ενοχλητικό να πρέπει, όπως, δύο δείκτες 571 00:24:02,690 --> 00:24:08,430 που διέρχεται από τη λίστα, ποιος άλλος θα μπορούσε να έχουν, σε έναν ιδανικό κόσμο, διατήρησε 572 00:24:08,430 --> 00:24:10,160 πληροφορίες που χρειαζόμαστε; 573 00:24:10,160 --> 00:24:11,360 Ναι; 574 00:24:11,360 --> 00:24:12,610 >> ΦΟΙΤΗΤΗΣ: [δεν ακούγεται]. 575 00:24:12,610 --> 00:24:15,160 576 00:24:15,160 --> 00:24:16,150 >> ΟΜΙΛΗΤΗΣ 1: Ακριβώς. 577 00:24:16,150 --> 00:24:19,130 Δικαίωμα έτσι υπάρχει πράγματι μια ενδιαφέρουσα μικρόβιο μιας ιδέας. 578 00:24:19,130 --> 00:24:22,470 Και αυτή η ιδέα ενός προηγούμενου δείκτη, δείχνοντας το προηγούμενο στοιχείο. 579 00:24:22,470 --> 00:24:25,580 Τι θα συμβεί αν απλά ενσωματώνονται ότι εσωτερικό του καταλόγου ίδιο; 580 00:24:25,580 --> 00:24:27,810 Και αυτό πρόκειται να είναι δύσκολο να απεικονίσει αυτό χωρίς όλα στο χαρτί 581 00:24:27,810 --> 00:24:28,830 την πτώση στο πάτωμα. 582 00:24:28,830 --> 00:24:31,860 Αλλά ας υποθέσουμε ότι αυτοί οι τύποι που χρησιμοποιούνται τόσο των χεριών τους να έχουν μια προηγούμενη 583 00:24:31,860 --> 00:24:35,950 δείκτη, και ένα επόμενο δείκτη, έτσι εφαρμογή των όσων θα καλέσουμε μια διπλά 584 00:24:35,950 --> 00:24:36,830 συνδεδεμένη λίστα. 585 00:24:36,830 --> 00:24:41,090 Αυτό θα μου επιτρέψετε να ταξινομήσετε του προς τα πίσω, πολύ πιο εύκολα χωρίς εμένα, η 586 00:24:41,090 --> 00:24:43,800 προγραμματιστής, έχοντας να κρατήσει παρακολουθείτε το χέρι - 587 00:24:43,800 --> 00:24:44,980 πραγματικά το χέρι - 588 00:24:44,980 --> 00:24:47,280 από όπου είχε προηγουμένως στη λίστα. 589 00:24:47,280 --> 00:24:48,110 Γι 'αυτό και δεν θα το κάνουμε αυτό. 590 00:24:48,110 --> 00:24:50,950 Θα κρατήσουμε απλό, επειδή αυτό είναι πρόκειται να έρθει σε μια τιμή, δύο φορές 591 00:24:50,950 --> 00:24:53,450 πολύ χώρο για τους δείκτες, αν θέλετε ένα δεύτερο. 592 00:24:53,450 --> 00:24:55,760 Αλλά αυτό είναι πράγματι μια κοινή δομή δεδομένων γνωστή ως 593 00:24:55,760 --> 00:24:57,410 διπλά συνδεδεμένη λίστα. 594 00:24:57,410 --> 00:25:01,310 >> Ας κάνουμε το τελευταίο παράδειγμα εδώ και να θέσει αυτά τα παιδιά από τη δυστυχία τους. 595 00:25:01,310 --> 00:25:03,270 Έτσι malloc 20. 596 00:25:03,270 --> 00:25:05,320 Ελάτε επάνω από το διάδρομο εκεί. 597 00:25:05,320 --> 00:25:06,280 Εντάξει, ποιο είναι το όνομά σου; 598 00:25:06,280 --> 00:25:07,440 >> ΦΟΙΤΗΤΗΣ: [δεν ακούγεται]. 599 00:25:07,440 --> 00:25:07,855 >> ΟΜΙΛΗΤΗΣ 1: Συγνώμη; 600 00:25:07,855 --> 00:25:08,480 >> ΦΟΙΤΗΤΗΣ: [δεν ακούγεται]. 601 00:25:08,480 --> 00:25:09,410 >> ΟΜΙΛΗΤΗΣ 1: Demeron; 602 00:25:09,410 --> 00:25:10,230 OK Ανέβα. 603 00:25:10,230 --> 00:25:11,910 Θα πρέπει να είναι 20. 604 00:25:11,910 --> 00:25:14,720 Μπορείτε προφανώς πρόκειται να ανήκουν μεταξύ 17 και 22. 605 00:25:14,720 --> 00:25:16,150 Έτσι, επιτρέψτε μου να μάθουν το μάθημά μου. 606 00:25:16,150 --> 00:25:18,150 Πάω να ξεκινήσει δείκτη δείχνοντας Brian. 607 00:25:18,150 --> 00:25:21,190 Και Πάω να έχουν το αριστερό μου χέρι μόνο ενημέρωση για Brian όπως προχωρήσουμε σε 608 00:25:21,190 --> 00:25:23,600 Jason, ο έλεγχος έχει 20 λιγότερα από εννέα; 609 00:25:23,600 --> 00:25:24,060 Όχι. 610 00:25:24,060 --> 00:25:25,430 20 είναι λιγότερο από 17; 611 00:25:25,430 --> 00:25:25,880 Όχι. 612 00:25:25,880 --> 00:25:27,450 Είναι 20 λιγότερο από το 22; 613 00:25:27,450 --> 00:25:28,440 Ναι. 614 00:25:28,440 --> 00:25:34,070 Έτσι δείκτες ή τα χέρια ό, τι πρέπει να αλλάξει εκεί που δείχνει τώρα; 615 00:25:34,070 --> 00:25:37,070 >> Έτσι, μπορούμε να κάνουμε 17 δείχνοντας σε 20. 616 00:25:37,070 --> 00:25:37,860 Έτσι, αυτό είναι εντάξει. 617 00:25:37,860 --> 00:25:40,080 Πού θέλουμε να επισημάνουμε δείκτη σας τώρα; 618 00:25:40,080 --> 00:25:41,330 Σε 22. 619 00:25:41,330 --> 00:25:45,410 Και ξέρουμε όπου το 22 είναι, και πάλι ευχαριστώ την προσωρινή δείκτη μου. 620 00:25:45,410 --> 00:25:46,760 Έτσι, είμαστε εντάξει εκεί. 621 00:25:46,760 --> 00:25:49,440 Έτσι, λόγω αυτής της προσωρινής αποθήκευσης Έχω κρατήσει παρακολουθείτε όπου ο καθένας είναι. 622 00:25:49,440 --> 00:25:55,055 Και τώρα μπορείτε να πάτε σε οπτικά, όπου ανήκετε, και τώρα χρειαζόμαστε 1, 2, 3, 623 00:25:55,055 --> 00:25:58,410 4, 5, 6, 7, 8, 9 μπάλες άγχος, και το χειροκρότημά του για 624 00:25:58,410 --> 00:25:59,770 αυτά τα παιδιά, αν μπορούσαμε. 625 00:25:59,770 --> 00:26:00,410 Όμορφα γίνει. 626 00:26:00,410 --> 00:26:05,320 >> [Χειροκρότημα] 627 00:26:05,320 --> 00:26:06,330 >> ΟΜΙΛΗΤΗΣ 1: Εντάξει. 628 00:26:06,330 --> 00:26:09,860 Και μπορεί να κρατήσει τα κομμάτια χαρτιού ως αναμνηστικά. 629 00:26:09,860 --> 00:26:15,930 >> Εντάξει, ναι, πιστέψτε με ότι είναι πολύ ευκολότερο να περπατήσετε μέσα από αυτό με 630 00:26:15,930 --> 00:26:17,680 ανθρώπους από ό, τι είναι με το πραγματικό κώδικα. 631 00:26:17,680 --> 00:26:22,690 Αλλά αυτό που θα βρείτε σε μια στιγμή τώρα, είναι ότι η ίδια - Ω, σας ευχαριστώ. 632 00:26:22,690 --> 00:26:23,630 Σας ευχαριστούμε - 633 00:26:23,630 --> 00:26:29,360 είναι ότι θα διαπιστώσετε ότι τα ίδια δεδομένα δομή, μια συνδεδεμένη λίστα, μπορεί στην πραγματικότητα 634 00:26:29,360 --> 00:26:33,200 να χρησιμοποιείται ως δομικό στοιχείο για ακόμη πιο εξελιγμένες δομές δεδομένων. 635 00:26:33,200 --> 00:26:37,620 >> Και συνειδητοποιούν πάρα πολύ το θέμα εδώ είναι ότι εισάγαμε απολύτως περισσότερο 636 00:26:37,620 --> 00:26:40,060 πολυπλοκότητα στην εφαρμογή αυτού του αλγορίθμου. 637 00:26:40,060 --> 00:26:43,940 Εισαγωγή, και αν πήγαμε μέσα από αυτό, διαγραφή και την αναζήτηση, είναι λίγο 638 00:26:43,940 --> 00:26:46,660 πιο περίπλοκη από ό, τι ήταν με μια σειρά. 639 00:26:46,660 --> 00:26:48,040 Αλλά έχουμε αποκτήσει αρκετό δυναμισμό. 640 00:26:48,040 --> 00:26:50,180 Παίρνουμε μια προσαρμοστική δομή δεδομένων. 641 00:26:50,180 --> 00:26:54,010 >> Αλλά και πάλι, θα πληρώσει ένα τίμημα ότι έχει μερικά πρόσθετη πολυπλοκότητα, τόσο 642 00:26:54,010 --> 00:26:54,910 την εφαρμογή της. 643 00:26:54,910 --> 00:26:56,750 Και είμαστε παραιτηθεί τυχαία πρόσβαση. 644 00:26:56,750 --> 00:27:00,450 Και για να είμαι ειλικρινής, δεν υπάρχει κάποια ωραία καθαρίστε διαφάνεια μπορώ να σας δώσω ότι 645 00:27:00,450 --> 00:27:03,120 λέει εδώ είναι γιατί μια συνδεδεμένη λίστα είναι καλύτερη από μία συστοιχία. 646 00:27:03,120 --> 00:27:04,100 Και το αφήσουμε εκεί. 647 00:27:04,100 --> 00:27:07,520 Επειδή το θέμα επανάληψης τώρα, ακόμη περισσότερο τις επόμενες εβδομάδες, είναι 648 00:27:07,520 --> 00:27:10,200 ότι δεν υπάρχει ανάγκη η σωστή απάντηση. 649 00:27:10,200 --> 00:27:13,830 >> Αυτός είναι ο λόγος που έχουμε το ξεχωριστό άξονα του σχεδιασμού για τα σύνολα πρόβλημα. 650 00:27:13,830 --> 00:27:17,700 Θα είναι πολύ συμφραζόμενα αν θέλετε να χρησιμοποιήσετε αυτά τα δεδομένα 651 00:27:17,700 --> 00:27:21,750 δομή ή ότι ένα, και θα εξαρτηθεί από το τι έχει σημασία για σας από την άποψη 652 00:27:21,750 --> 00:27:24,620 των πόρων και την πολυπλοκότητα. 653 00:27:24,620 --> 00:27:28,830 >> Αλλά επιτρέψτε μου να προτείνω ότι το ιδανικό δεδομένα δομή, το Άγιο Δισκοπότηρο, θα ήταν 654 00:27:28,830 --> 00:27:32,200 κάτι που είναι σταθερό χρόνο, ανεξάρτητα από το πόσα πράγματα είναι 655 00:27:32,200 --> 00:27:36,940 μέσα σε αυτό, δεν θα ήταν καταπληκτικό αν ένα δομή δεδομένων επέστρεψε απαντήσεις 656 00:27:36,940 --> 00:27:37,920 σταθερό χρόνο. 657 00:27:37,920 --> 00:27:38,330 Ναι. 658 00:27:38,330 --> 00:27:40,110 Αυτή η λέξη είναι στην τεράστια λεξικό σας. 659 00:27:40,110 --> 00:27:41,550 Ή όχι, αυτή η λέξη δεν είναι. 660 00:27:41,550 --> 00:27:43,270 Ή οποιοδήποτε τέτοιο πρόβλημα εκεί. 661 00:27:43,270 --> 00:27:46,360 Λοιπόν ας δούμε αν δεν μπορούμε, τουλάχιστον κάνουμε ένα βήμα προς αυτό. 662 00:27:46,360 --> 00:27:50,190 >> Επιτρέψτε μου να προτείνω μια νέα δομή δεδομένων που μπορεί να χρησιμοποιηθεί για διαφορετικά πράγματα, 663 00:27:50,190 --> 00:27:52,260 σε αυτή την περίπτωση ονομάζεται hash table. 664 00:27:52,260 --> 00:27:55,590 Και έτσι είμαστε πραγματικά πίσω στην ανακλώμενη σε μία συστοιχία, στην περίπτωση αυτή, και 665 00:27:55,590 --> 00:28:00,550 κάπως αυθαίρετα, έχω σχεδιάσει αυτό hash πίνακα ως μια σειρά με ένα είδος 666 00:28:00,550 --> 00:28:02,810 δισδιάστατο πίνακα - 667 00:28:02,810 --> 00:28:05,410 ή μάλλον είναι απεικονίζεται εδώ ως δύο διαστάσεων πίνακα - αλλά αυτό είναι μόνο 668 00:28:05,410 --> 00:28:10,770 μια σειρά από μέγεθος 26, έτσι ώστε αν έχουμε καλέστε τον πίνακα array, βραχίονα πίνακα 669 00:28:10,770 --> 00:28:12,440 μηδέν είναι το ορθογώνιο στην κορυφή. 670 00:28:12,440 --> 00:28:15,090 Πίνακας βραχίονα 25 είναι το ορθογώνιο στο κάτω μέρος. 671 00:28:15,090 --> 00:28:18,620 Και αυτό είναι το πώς θα μπορούσε να συντάξει μια δεδομένων δομή στην οποία θέλετε να αποθηκεύσετε 672 00:28:18,620 --> 00:28:19,790 ανθρώπων ονόματα. 673 00:28:19,790 --> 00:28:24,370 >> Έτσι, για παράδειγμα, και δεν θα επιστήσει την όλο θέμα εδώ για την εναέρια, αν 674 00:28:24,370 --> 00:28:29,160 είχε αυτό το array, που είμαι τώρα πρόκειται να καλέσετε έναν πίνακα κατακερματισμού, και αυτό είναι και πάλι 675 00:28:29,160 --> 00:28:31,360 θέση μηδέν. 676 00:28:31,360 --> 00:28:34,840 Αυτό εδώ είναι θέση ένα, και ούτω καθεξής. 677 00:28:34,840 --> 00:28:37,880 Ισχυρίζομαι ότι θέλω να χρησιμοποιήσω αυτά τα δεδομένα δομής, για χάρη της συζήτησης, 678 00:28:37,880 --> 00:28:42,600 για να αποθηκεύσετε τα ονόματα των ανθρώπων, Alice και ο Bob και ο Τσάρλι και άλλα τέτοια ονόματα. 679 00:28:42,600 --> 00:28:46,110 Έτσι σκέφτομαι αυτό τώρα ως τις αρχές των, ας πούμε, ένα λεξικό 680 00:28:46,110 --> 00:28:47,520 με πολλά λόγια. 681 00:28:47,520 --> 00:28:49,435 Τυχαίνει να είναι τα ονόματα Στο παράδειγμά μας εδώ. 682 00:28:49,435 --> 00:28:52,560 Και όλα αυτά είναι πολύ συναφές, ίσως, να εφαρμογή έναν ορθογράφο, όπως 683 00:28:52,560 --> 00:28:54,400 θα μπορούσε για το πρόβλημα που έξι. 684 00:28:54,400 --> 00:28:59,300 >> Έτσι, αν έχουμε μια σειρά από συνολικό μέγεθος 26 έτσι ώστε αυτή είναι η 25η θέση 685 00:28:59,300 --> 00:29:03,390 στο κάτω μέρος, και ισχυρίζονται ότι η Alice είναι η πρώτη λέξη στο λεξικό 686 00:29:03,390 --> 00:29:07,260 ονόματα που θέλετε να εισαγάγετε στη μνήμη RAM, σε αυτή τη δομή δεδομένων, όπου 687 00:29:07,260 --> 00:29:12,480 το ένστικτό σας ενημερώνει ότι Αλίκης το όνομα θα πρέπει να πάει σε αυτό το πίνακα; 688 00:29:12,480 --> 00:29:13,510 >> Έχουμε 26 επιλογές. 689 00:29:13,510 --> 00:29:14,990 Όταν θέλουμε να την βάλει; 690 00:29:14,990 --> 00:29:16,200 Τη θέλουμε στο βραχίονα μηδέν, έτσι δεν είναι; 691 00:29:16,200 --> 00:29:18,280 Α για την Αλίκη, ας το ονομάσουμε αυτό το μηδενικό. 692 00:29:18,280 --> 00:29:20,110 Και B θα είναι ένα, και C θα είναι δύο. 693 00:29:20,110 --> 00:29:22,600 Έτσι θα πάμε για να γράψει Το όνομα της Αλίκης μέχρι εδώ. 694 00:29:22,600 --> 00:29:24,890 Αν στη συνέχεια τοποθετήστε Bob, του όνομα θα πάει εδώ. 695 00:29:24,890 --> 00:29:27,280 Charlie θα πάει εδώ. 696 00:29:27,280 --> 00:29:30,500 Και ούτω καθεξής κάτω μέσω Αυτή η δομή δεδομένων. 697 00:29:30,500 --> 00:29:32,090 >> Αυτή είναι μια θαυμάσια δομή δεδομένων. 698 00:29:32,090 --> 00:29:32,730 Γιατί; 699 00:29:32,730 --> 00:29:37,460 Καλά τι είναι ο χρόνος εκτέλεσης του εισάγοντας το όνομα ενός ανθρώπου σε αυτό 700 00:29:37,460 --> 00:29:39,850 δομή δεδομένων τώρα; 701 00:29:39,850 --> 00:29:43,702 Δεδομένου ότι ο πίνακας αυτός υλοποιείται, πραγματικά, ως μια σειρά. 702 00:29:43,702 --> 00:29:44,940 Καλά είναι σταθερό χρόνο. 703 00:29:44,940 --> 00:29:45,800 Είναι τάξης του ενός. 704 00:29:45,800 --> 00:29:46,360 Γιατί; 705 00:29:46,360 --> 00:29:48,630 >> Λοιπόν, πώς μπορώ να προσδιορίσω όπου η Alice ανήκει; 706 00:29:48,630 --> 00:29:51,000 Κοιτάς την οποία γράμμα του ονόματός της; 707 00:29:51,000 --> 00:29:51,490 Η πρώτη. 708 00:29:51,490 --> 00:29:54,350 Και μπορείτε να φτάσετε εκεί, αν είναι ένα string, από μόνο κοιτάζοντας κορδόνι 709 00:29:54,350 --> 00:29:55,200 βραχίονα μηδέν. 710 00:29:55,200 --> 00:29:57,110 Έτσι, η μηδενική χαρακτήρα του string. 711 00:29:57,110 --> 00:29:57,610 Αυτό είναι εύκολο. 712 00:29:57,610 --> 00:30:00,350 Κάναμε ότι στην κρυπτογραφική εκχώρηση εβδομάδες πριν. 713 00:30:00,350 --> 00:30:05,310 Και στη συνέχεια, αφού ξέρετε ότι Αλίκης επιστολή του κεφαλαίου Α, μπορούμε να αφαιρέσουμε 714 00:30:05,310 --> 00:30:08,160 από 65 ή του κεφαλαίου Α η ίδια, που μας δίνει το μηδέν. 715 00:30:08,160 --> 00:30:10,940 Έτσι, γνωρίζουμε πλέον ότι η Alice ανήκει στη θέση μηδέν. 716 00:30:10,940 --> 00:30:14,240 >> Και με δεδομένο ένα δείκτη σε αυτά τα δεδομένα δομή, κάποιου είδους, πόσο καιρό 717 00:30:14,240 --> 00:30:18,840 μου πάρει να βρει θέση μηδέν σε μια σειρά; 718 00:30:18,840 --> 00:30:22,080 Μόλις ένα βήμα, το δικαίωμα Είναι σταθερό χρόνο λόγω της τυχαίας πρόσβασης εμείς 719 00:30:22,080 --> 00:30:23,780 προτεινόμενο ήταν ένα χαρακτηριστικό γνώρισμα ενός πίνακα. 720 00:30:23,780 --> 00:30:28,570 Έτσι, με λίγα λόγια, υπολογίζει τι ο δείκτης του ονόματος της Αλίκης είναι, το οποίο είναι, σε 721 00:30:28,570 --> 00:30:32,610 Στην περίπτωση αυτή, είναι Α ή ας επιλύσει ότι στο μηδέν, όπου το Β είναι ένα και C είναι 722 00:30:32,610 --> 00:30:34,900 δύο, υπολογίζοντας ότι από είναι σταθερό χρόνο. 723 00:30:34,900 --> 00:30:38,510 Απλά πρέπει να δούμε το πρώτο γράμμα της, υπολογίζοντας όπου το μηδέν είναι μια 724 00:30:38,510 --> 00:30:40,460 συστοιχία είναι επίσης σταθερό χρόνο. 725 00:30:40,460 --> 00:30:42,140 Έτσι, από τεχνική ότι είναι σαν δύο μέτρα τώρα. 726 00:30:42,140 --> 00:30:43,330 Αλλά αυτό είναι ακόμα σταθερή. 727 00:30:43,330 --> 00:30:46,880 Έτσι λέμε ότι η μεγάλη O ενός, έτσι έχουμε εισάγεται Alice σε αυτό τον πίνακα σε 728 00:30:46,880 --> 00:30:48,440 σταθερό χρόνο. 729 00:30:48,440 --> 00:30:50,960 >> Αλλά φυσικά, ότι είμαι αφελής εδώ, έτσι δεν είναι; 730 00:30:50,960 --> 00:30:53,240 Τι γίνεται αν υπάρχει ένα Aaron στην τάξη; 731 00:30:53,240 --> 00:30:53,990 Ή Alicia; 732 00:30:53,990 --> 00:30:57,230 Ή οποιαδήποτε άλλα ονόματα που αρχίζουν με A. Όταν θα πάμε να θέσει 733 00:30:57,230 --> 00:31:00,800 το εν λόγω πρόσωπο, έτσι δεν είναι; 734 00:31:00,800 --> 00:31:03,420 Θέλω να πω, αυτή τη στιγμή υπάρχει μόνο τρεις οι άνθρωποι στο τραπέζι, οπότε ίσως είμαστε 735 00:31:03,420 --> 00:31:07,490 πρέπει να θέσει Aaron στη θέση μηδέν ένα δύο τρία. 736 00:31:07,490 --> 00:31:09,480 >> Σωστά, θα μπορούσατε να βάλετε ένα εδώ. 737 00:31:09,480 --> 00:31:13,350 Στη συνέχεια, όμως, αν προσπαθήσουμε να εισαγάγετε τον David σε Ο κατάλογος αυτός, όπου ο Δαβίδ πάτε; 738 00:31:13,350 --> 00:31:15,170 Τώρα το σύστημά μας ξεκινά το σπάσιμο κάτω, δεξιά; 739 00:31:15,170 --> 00:31:19,210 Επειδή τώρα ο David καταλήγει εδώ αν Aaron είναι πραγματικά εδώ. 740 00:31:19,210 --> 00:31:23,060 Και έτσι τώρα όλη αυτή η ιδέα του να έχετε ένα καθαρή δομή των δεδομένων που μας δίνει 741 00:31:23,060 --> 00:31:28,010 σταθερές εισαγωγές χρόνος δεν είναι πλέον σταθερό χρόνο, γιατί έχω να 742 00:31:28,010 --> 00:31:31,240 έλεγχο, oh, damnit, κάποιος είναι ήδη στη θέση της Αλίκης. 743 00:31:31,240 --> 00:31:35,320 >> Επιτρέψτε μου να εξετάσει το υπόλοιπο των εν λόγω στοιχείων δομή, ψάχνει για ένα μέρος για να θέσει 744 00:31:35,320 --> 00:31:37,130 κάποιος όπως το όνομα του Ααρών. 745 00:31:37,130 --> 00:31:39,390 Και έτσι που πολύ έχει αρχίσει να λάβει γραμμικό χρόνο. 746 00:31:39,390 --> 00:31:42,710 Επιπλέον, εάν θέλετε τώρα να βρει το Aaron σε αυτή τη δομή δεδομένων, και 747 00:31:42,710 --> 00:31:45,430 έλεγχο, και το όνομα του Ααρών δεν είναι εδώ. 748 00:31:45,430 --> 00:31:47,960 Ιδανικά, θα πω μόνο του Aaron όχι στη δομή δεδομένων. 749 00:31:47,960 --> 00:31:51,530 Αλλά αν το κάνετε να αρχίσουμε να κάνουμε χώρο για Aaron, όπου θα έπρεπε να υπάρχει ένα D 750 00:31:51,530 --> 00:31:55,600 ή Ε, εσείς, στη χειρότερη περίπτωση, πρέπει να ελέγξετε ολόκληρη η δομή των δεδομένων, 751 00:31:55,600 --> 00:31:59,480 οπότε και περιέρχεται σε κάτι γραμμική στο μέγεθος του πίνακα. 752 00:31:59,480 --> 00:32:00,920 >> Έτσι, εντάξει, εγώ θα το διορθώσω αυτό. 753 00:32:00,920 --> 00:32:04,200 Το πρόβλημα εδώ είναι ότι είχα 26 στοιχεία σε αυτή την συστοιχία. 754 00:32:04,200 --> 00:32:05,000 Επιτρέψτε μου να το αλλάξετε. 755 00:32:05,000 --> 00:32:06,010 Ωχ. 756 00:32:06,010 --> 00:32:10,600 Επιτρέψτε μου να το αλλάξετε έτσι ώστε αντί να της μέγεθος 26 στο σύνολο, παρατηρήσετε το κάτω μέρος 757 00:32:10,600 --> 00:32:12,720 Δείκτης πρόκειται να αλλάξει στο n μείον 1. 758 00:32:12,720 --> 00:32:16,610 Αν 26 είναι σαφώς πολύ μικρό για «τον άνθρωπο ονόματα, γιατί υπάρχουν χιλιάδες 759 00:32:16,610 --> 00:32:20,830 ονόματα του κόσμου, ας κάνουν σε 100 ή 1.000 ή 10.000. 760 00:32:20,830 --> 00:32:22,960 Ας διαθέσει μόνο πολύ περισσότερο χώρο. 761 00:32:22,960 --> 00:32:27,230 >> Καλά που δεν είναι αναγκαστικά μειώνεται η πιθανότητα ότι δεν θα έχουμε δύο 762 00:32:27,230 --> 00:32:31,510 οι άνθρωποι με τα ονόματα που αρχίζουν με A, και έτσι, επρόκειτο να προσπαθήσει να θέσει ένα 763 00:32:31,510 --> 00:32:33,120 ονόματα σε μηδενική θέση ακόμα. 764 00:32:33,120 --> 00:32:36,850 Είναι ακόμα πρόκειται να συγκρουστούν, η οποία σημαίνει ότι εξακολουθούμε να χρειαζόμαστε μια λύση για να τεθεί 765 00:32:36,850 --> 00:32:41,020 Alice και ο Ααρών και η Alicia και άλλα ονόματα που αρχίζουν με A αλλού. 766 00:32:41,020 --> 00:32:43,460 Αλλά πόσο σημαντικό πρόβλημα είναι αυτό; 767 00:32:43,460 --> 00:32:46,870 Ποια είναι η πιθανότητα ότι έχουν συγκρούσεις σε δεδομένα 768 00:32:46,870 --> 00:32:48,240 δομή, όπως αυτό; 769 00:32:48,240 --> 00:32:52,570 >> Λοιπόν, επιτρέψτε μου - θα επανέλθουμε σε αυτό το ερώτημα εδώ. 770 00:32:52,570 --> 00:32:55,530 Και να δούμε πώς μπορούμε να λύστε πρώτα. 771 00:32:55,530 --> 00:32:58,480 Επιτρέψτε μου να σηκώσει αυτήν την πρόταση εδώ. 772 00:32:58,480 --> 00:33:02,020 Αυτό που μόλις περιγράψαμε είναι ένας αλγόριθμος, μια ευρετική που ονομάζεται γραμμική 773 00:33:02,020 --> 00:33:05,030 σχολαστικά σύμφωνα με την οποία, αν προσπαθήσει να εισάγετε κάτι εδώ σε αυτά τα δεδομένα 774 00:33:05,030 --> 00:33:08,920 δομή, η οποία ονομάζεται πίνακα κατακερματισμού, και δεν υπάρχει χώρος εκεί, 775 00:33:08,920 --> 00:33:12,000 πραγματικά να εξετάσει τη δομή δεδομένων τον έλεγχο, είναι αυτό δυνατό; 776 00:33:12,000 --> 00:33:13,430 Είναι αυτό δυνατό είναι αυτό δυνατό; 777 00:33:13,430 --> 00:33:13,980 Είναι αυτό δυνατό; 778 00:33:13,980 --> 00:33:17,550 Και όταν τελικά, εισάγετε το όνομα που αρχικά προορίζονταν 779 00:33:17,550 --> 00:33:19,370 αλλού σε αυτή τη θέση. 780 00:33:19,370 --> 00:33:23,360 Όμως, στη χειρότερη περίπτωση, το μόνο σημείο μπορεί να είναι το κάτω μέρος των στοιχείων 781 00:33:23,360 --> 00:33:25,090 τη δομή, το τέλος του πίνακα. 782 00:33:25,090 --> 00:33:30,130 >> Έτσι γραμμική σχολαστικά, στη χειρότερη περίπτωση, περιέρχεται σε ένα γραμμικό αλγόριθμο όπου 783 00:33:30,130 --> 00:33:34,500 Aaron, αν συμβεί να εισαχθεί τελευταία σε αυτή τη δομή δεδομένων, θα μπορούσε 784 00:33:34,500 --> 00:33:39,540 συγκρούονται με αυτή την πρώτη θέση, αλλά στη συνέχεια καταλήγουν με την κακή τύχη στο τέλος. 785 00:33:39,540 --> 00:33:43,940 Έτσι, αυτό δεν είναι μια σταθερή χρόνο Άγιο Δισκοπότηρο για εμάς. 786 00:33:43,940 --> 00:33:47,650 Αυτή η προσέγγιση της εισαγωγής στοιχείων σε μια δομή δεδομένων που ονομάζεται ένα hash 787 00:33:47,650 --> 00:33:52,050 πίνακα δεν φαίνεται να είναι σταθερό χρόνο τουλάχιστον όχι στη γενική περίπτωση. 788 00:33:52,050 --> 00:33:54,000 Μπορεί να περιέλθει σε κάτι γραμμικό. 789 00:33:54,000 --> 00:33:56,970 >> Τι κι αν έχουμε επιλύσει συγκρούσεις κάπως διαφορετικά; 790 00:33:56,970 --> 00:34:00,740 Έτσι, εδώ είναι μια πιο εξελιγμένη προσέγγιση σε ό, τι είναι ακόμα 791 00:34:00,740 --> 00:34:02,800 ονομάζεται hash table. 792 00:34:02,800 --> 00:34:05,890 Και με χασίς, όπως Παρεμπιπτόντως, τι Εννοώ είναι ο δείκτης που 793 00:34:05,890 --> 00:34:07,070 Αναφέρθηκα προηγουμένως. 794 00:34:07,070 --> 00:34:09,810 Για hash κάτι που μπορεί να είναι θεωρηθεί ως ρήμα. 795 00:34:09,810 --> 00:34:13,690 >> Έτσι, αν hash Alice είναι ένα όνομα, μια συνάρτηση κατακερματισμού, να το πω έτσι, 796 00:34:13,690 --> 00:34:14,710 θα πρέπει να επιστρέψει έναν αριθμό. 797 00:34:14,710 --> 00:34:18,199 Σε αυτή την περίπτωση είναι μηδέν αν ανήκει σε θέση μηδέν, ένα, εάν ανήκει σε 798 00:34:18,199 --> 00:34:20,000 μία θέση, και ούτω καθεξής. 799 00:34:20,000 --> 00:34:24,360 Έτσι συνάρτηση κατακερματισμού μου μέχρι στιγμής έχει εξαιρετικά απλή, μόνο κοιτάζοντας το 800 00:34:24,360 --> 00:34:26,159 πρώτο γράμμα στο όνομα κάποιου. 801 00:34:26,159 --> 00:34:29,090 Αλλά μια hash συνάρτηση παίρνει ως input κάποιο κομμάτι των δεδομένων, 802 00:34:29,090 --> 00:34:30,210 string, ένας int, οτιδήποτε. 803 00:34:30,210 --> 00:34:32,239 Και φτύσει συνήθως μια σειρά. 804 00:34:32,239 --> 00:34:35,739 Και ο αριθμός αυτός είναι όπου αυτά τα δεδομένα στοιχείο ανήκει σε μία δομή δεδομένων 805 00:34:35,739 --> 00:34:37,800 γνωστή εδώ ως ένα πίνακα κατακερματισμού. 806 00:34:37,800 --> 00:34:41,400 >> Έτσι απλά διαισθητικά, αυτό είναι ένα ελαφρώς διαφορετικό πλαίσιο. 807 00:34:41,400 --> 00:34:44,170 Αυτό είναι στην πραγματικότητα αναφέρεται σε ένα παράδειγμα συμμετοχή γενέθλια, όπου 808 00:34:44,170 --> 00:34:46,850 μπορεί να υπάρχουν όσο το 31 ημέρες το μήνα. 809 00:34:46,850 --> 00:34:52,239 Αλλά τι έκανε αυτό το πρόσωπο αποφασίσει να κάνετε σε περίπτωση σύγκρουσης; 810 00:34:52,239 --> 00:34:55,304 Πλαίσιο που τώρα, δεν είναι μια σύγκρουση ονόματα, αλλά μια σύγκρουση της γενέθλια, 811 00:34:55,304 --> 00:35:00,760 εάν δύο άνθρωποι έχουν την ίδια ημερομηνία γέννησης για 2 Οκτωβρίου, για παράδειγμα. 812 00:35:00,760 --> 00:35:02,120 >> ΦΟΙΤΗΤΗΣ: [δεν ακούγεται]. 813 00:35:02,120 --> 00:35:05,010 >> ΟΜΙΛΗΤΗΣ 1: Ναι, έτσι και εδώ έχουμε η μόχλευση των συνδεδεμένων λιστών. 814 00:35:05,010 --> 00:35:07,830 Γι 'αυτό φαίνεται λίγο διαφορετικά από ό, τι επέστησε νωρίτερα. 815 00:35:07,830 --> 00:35:10,790 Αλλά εμείς φαίνεται να έχουν σε μία συστοιχία στην αριστερή πλευρά. 816 00:35:10,790 --> 00:35:13,230 Αυτό είναι ένα ευρετήριο, για κανένα ιδιαίτερος λόγος. 817 00:35:13,230 --> 00:35:14,630 Αλλά είναι ακόμα μια σειρά. 818 00:35:14,630 --> 00:35:16,160 Είναι μια σειρά από δείκτες. 819 00:35:16,160 --> 00:35:20,670 Και καθένα από αυτά τα στοιχεία, καθένα από τα οι κύκλοι ή καθέτους - η κάθετος 820 00:35:20,670 --> 00:35:23,970 εκπροσωπούν null - κάθε ένα από αυτά δείκτες προφανώς δείχνοντας 821 00:35:23,970 --> 00:35:25,730 Τι δομή δεδομένων; 822 00:35:25,730 --> 00:35:26,890 Μια συνδεδεμένη λίστα. 823 00:35:26,890 --> 00:35:30,530 >> Έτσι τώρα έχουμε τη δυνατότητα να σκληρό κώδικα στο πρόγραμμά μας 824 00:35:30,530 --> 00:35:32,010 το μέγεθος του πίνακα. 825 00:35:32,010 --> 00:35:35,360 Σε αυτή την περίπτωση, γνωρίζουμε ποτέ δεν υπάρχει περισσότερο από 31 ημέρες σε ένα μήνα. 826 00:35:35,360 --> 00:35:38,480 Έτσι κωδικοποίηση σκληρά μια τιμή, όπως 31 λογικό σε αυτό το πλαίσιο. 827 00:35:38,480 --> 00:35:42,700 Στο πλαίσιο των ονομάτων, σκληρό κωδικοποίησης 26 Δεν είναι παράλογο αυτό των ανθρώπων 828 00:35:42,700 --> 00:35:46,340 μόνο τα ονόματα ξεκινούν με, για παράδειγμα, το αλφάβητο που αφορούν Α έως Ζ. 829 00:35:46,340 --> 00:35:50,180 >> Μπορούμε να τους γεμίσουν όλα σε αυτά τα δεδομένα δομή, εφόσον, όταν παίρνουμε ένα 830 00:35:50,180 --> 00:35:55,330 σύγκρουσης, δεν θέσει τα ονόματα εδώ, εμείς αντί να σκεφτούμε αυτά τα κύτταρα 831 00:35:55,330 --> 00:36:00,270 όχι ως χορδές οι ίδιοι, αλλά ως δείκτες, για παράδειγμα, Alice. 832 00:36:00,270 --> 00:36:03,660 Και τότε Alice μπορεί να έχει άλλο δείκτη σε άλλο όνομα που αρχίζει με 833 00:36:03,660 --> 00:36:06,150 Α. Και Bob πηγαίνει πραγματικά εδώ. 834 00:36:06,150 --> 00:36:10,850 >> Και αν υπάρχει ένα άλλο όνομα που αρχίζει με Β, καταλήγει εδώ. 835 00:36:10,850 --> 00:36:15,070 Και έτσι καθένα από τα στοιχεία της παρούσας πίνακα δύο, αν σχεδιάσαμε αυτό το 836 00:36:15,070 --> 00:36:17,350 λίγο πιο έξυπνα - 837 00:36:17,350 --> 00:36:18,125 έλα - 838 00:36:18,125 --> 00:36:22,950 αν σχεδιάσαμε αυτό το λίγο περισσότερο Έξυπνα, γίνεται τώρα ένα προσαρμοστικό δεδομένων 839 00:36:22,950 --> 00:36:27,720 δομή, όπου δεν υπάρχει συγκεκριμένο όριο σχετικά με το πώς πολλά στοιχεία που μπορείτε να εισαγάγετε 840 00:36:27,720 --> 00:36:30,700 σε αυτό, διότι αν έχετε μια σύγκρουση, αυτό είναι εντάξει. 841 00:36:30,700 --> 00:36:34,690 Απλά πηγαίνετε μπροστά και να προσαρτήσει την Τι είδαμε λίγο πριν, ήταν 842 00:36:34,690 --> 00:36:38,290 γνωστή ως μια συνδεδεμένη λίστα. 843 00:36:38,290 --> 00:36:39,690 >> Λοιπόν ας σταματήσουμε για μια στιγμή. 844 00:36:39,690 --> 00:36:42,570 Ποια είναι η πιθανότητα μιας σύγκρουσης στην πρώτη θέση; 845 00:36:42,570 --> 00:36:45,480 Δεξιά, ίσως είμαι πέρα ​​από τη σκέψη, ίσως Είμαι πάνω από μηχανική αυτό το πρόβλημα, 846 00:36:45,480 --> 00:36:46,370 γιατί ξέρετε τι; 847 00:36:46,370 --> 00:36:49,070 Ναι, μπορώ να καταλήξει με την αυθαίρετη παραδείγματα από την κορυφή του κεφαλιού μου, όπως 848 00:36:49,070 --> 00:36:52,870 Allison και ο Ααρών, αλλά στην πραγματικότητα, δοθεί μια ομοιόμορφη κατανομή του 849 00:36:52,870 --> 00:36:56,990 εισόδους, που είναι κάποια τυχαία προσθήκες σε μια δομή δεδομένων, αυτό που πραγματικά είναι 850 00:36:56,990 --> 00:36:58,580 η πιθανότητα μιας σύγκρουσης; 851 00:36:58,580 --> 00:37:01,670 Λοιπόν, αποδεικνύεται, ότι είναι στην πραγματικότητα εξαιρετικά υψηλή. 852 00:37:01,670 --> 00:37:03,850 Επιτρέψτε μου να γενικεύσει αυτό πρόβλημα είναι όπως αυτό. 853 00:37:03,850 --> 00:37:08,890 >> Έτσι, σε ένα δωμάτιο του n CS50 μαθητών, τι είναι η πιθανότητα ότι τουλάχιστον 854 00:37:08,890 --> 00:37:11,010 δύο μαθητές στο δωμάτιο έχουν τα ίδια γενέθλια; 855 00:37:11,010 --> 00:37:13,346 Έτσι, υπάρχει αυτό. λίγα Hund - 856 00:37:13,346 --> 00:37:16,790 200, 300 άτομα εδώ και αρκετά εκατοντάδες άτομα στο σπίτι σήμερα. 857 00:37:16,790 --> 00:37:20,670 Έτσι, αν θέλετε να αναρωτηθούμε τι είναι η πιθανότητα δύο άτομα 858 00:37:20,670 --> 00:37:23,930 σε αυτό το δωμάτιο έχουν την ίδια ημερομηνία γέννησης, μπορούμε να το καταλάβουν αυτό. 859 00:37:23,930 --> 00:37:26,250 Και εγώ ισχυρίζομαι στην πραγματικότητα υπάρχουν δύο άτομα με την ίδια γενέθλια. 860 00:37:26,250 --> 00:37:29,560 >> Για παράδειγμα, κανείς δεν έχουν γενέθλια σήμερα; 861 00:37:29,560 --> 00:37:31,340 Χθες; 862 00:37:31,340 --> 00:37:32,590 Αύριο; 863 00:37:32,590 --> 00:37:35,980 Εντάξει, έτσι ώστε να αισθάνεται σαν να είμαι πρόκειται να έχουν να κάνουν αυτό το 363 ή έτσι περισσότερο 864 00:37:35,980 --> 00:37:39,500 φορές πραγματικά να καταλάβω Αν έχουμε μια σύγκρουση. 865 00:37:39,500 --> 00:37:42,350 Ή θα μπορούσαμε να κάνουμε μόνο αυτό μαθηματικά αντί tediously 866 00:37:42,350 --> 00:37:43,200 να γίνει αυτό. 867 00:37:43,200 --> 00:37:44,500 Και προτείνω τα ακόλουθα. 868 00:37:44,500 --> 00:37:48,740 >> Γι 'αυτό και προτείνω ότι θα μπορούσαμε να το μοντέλο του πιθανότητα δύο άτομα που έχουν την 869 00:37:48,740 --> 00:37:55,320 ίδια ημερομηνία γέννησης με την πιθανότητα 1 μείον την πιθανότητα κανείς δεν έχει 870 00:37:55,320 --> 00:37:56,290 η ίδια γενέθλια. 871 00:37:56,290 --> 00:37:59,960 Έτσι για να πάρετε αυτό, και αυτό είναι μόνο η φανταχτερό τρόπο γραφής αυτό, για το 872 00:37:59,960 --> 00:38:03,090 πρώτο άτομο στο δωμάτιο, αυτός ή αυτή μπορεί να έχει οποιαδήποτε μία από τις πιθανές 873 00:38:03,090 --> 00:38:07,370 Γενέθλια υποθέτοντας 365 ημέρες το χρόνο, με συγχωρείτε για τα άτομα με 874 00:38:07,370 --> 00:38:08,760 του Φεβρουαρίου 29α γενέθλια. 875 00:38:08,760 --> 00:38:13,470 >> Έτσι, το πρώτο πρόσωπο σε αυτό το δωμάτιο είναι δωρεάν να έχουν οποιοδήποτε αριθμό γενέθλια 876 00:38:13,470 --> 00:38:18,280 έξω από τις 365 δυνατότητες, έτσι ώστε θα κάνουμε ότι το 365 διαιρείται με 365, 877 00:38:18,280 --> 00:38:18,990 η οποία είναι μία. 878 00:38:18,990 --> 00:38:22,700 Το επόμενο πρόσωπο στο δωμάτιο, αν ο στόχος είναι να αποφευχθεί μια σύγκρουση, μπορεί μόνο να 879 00:38:22,700 --> 00:38:26,460 έχει του ή τα γενέθλιά της για το πώς πολλές διαφορετικές ημέρες; 880 00:38:26,460 --> 00:38:27,610 364. 881 00:38:27,610 --> 00:38:31,430 Έτσι, ο δεύτερος όρος αυτής της έκφρασης είναι ουσιαστικά κάνει ότι τα μαθηματικά για εμάς 882 00:38:31,430 --> 00:38:33,460 αφαιρώντας από μια πιθανή ημέρα. 883 00:38:33,460 --> 00:38:36,390 Και στη συνέχεια την επόμενη μέρα, την επόμενη μέρα, ο επόμενη μέρα τα κάτω με το συνολικό αριθμό 884 00:38:36,390 --> 00:38:38,100 των ανθρώπων σε ένα δωμάτιο. 885 00:38:38,100 --> 00:38:41,290 >> Και αν μπορούμε στη συνέχεια να εξετάσουν, τότε τι είναι η πιθανότητα όχι ο καθένας έχει 886 00:38:41,290 --> 00:38:45,265 μοναδικά γενέθλια, αλλά και πάλι 1 μείον ότι, αυτό που έχουμε είναι μια έκφραση 887 00:38:45,265 --> 00:38:47,810 που μπορεί να είναι πολύ ευφάνταστο μοιάζει με αυτό. 888 00:38:47,810 --> 00:38:50,330 Αλλά είναι πιο ενδιαφέρον για να δούμε οπτικά. 889 00:38:50,330 --> 00:38:55,120 Αυτό είναι ένα διάγραμμα όπου στον χ-άξονα είναι ο αριθμός των ατόμων στο δωμάτιο, η 890 00:38:55,120 --> 00:38:56,180 αριθμός γενέθλια. 891 00:38:56,180 --> 00:38:59,840 Σχετικά με την Υ-άξονας είναι η πιθανότητα σύγκρουσης, δύο άτομα 892 00:38:59,840 --> 00:39:01,230 έχει την ίδια γενέθλια. 893 00:39:01,230 --> 00:39:05,020 >> Και το φαγητό από αυτήν την καμπύλη είναι ότι το συντομότερο θα έχετε να αρέσει 40 894 00:39:05,020 --> 00:39:11,110 φοιτητές, είστε επάνω σε μια πιθανότητα 90% combinatorically των δύο 895 00:39:11,110 --> 00:39:13,550 ή περισσότερα άτομα που έχουν η ίδια γενέθλια. 896 00:39:13,550 --> 00:39:18,600 Και τη στιγμή που μπορείτε να πάρετε για τα 58 άτομα είναι σχεδόν το 100% της μια ευκαιρία οι δύο 897 00:39:18,600 --> 00:39:21,310 άτομα σε ένα δωμάτιο πρόκειται να έχουν το ίδια γενέθλια, ακόμα κι αν δεν υπάρχει 898 00:39:21,310 --> 00:39:26,650 365 ή 366 πιθανές κουβάδες, και μόνο 58 άτομα σε ένα δωμάτιο. 899 00:39:26,650 --> 00:39:29,900 Απλά στατιστικά είναι πιθανό να πάρετε συγκρούσεις, η οποία σε σύντομο 900 00:39:29,900 --> 00:39:31,810 παρακινεί αυτή τη συζήτηση. 901 00:39:31,810 --> 00:39:35,890 Ότι ακόμα κι αν πάρετε φανταχτερό εδώ, και αρχίζουν να έχουν αυτές τις αλυσίδες, είμαστε ακόμα 902 00:39:35,890 --> 00:39:36,950 πρόκειται να έχει συγκρούσεις. 903 00:39:36,950 --> 00:39:42,710 >> Έτσι, αυτό εγείρει το ερώτημα, ποια είναι η το κόστος του να κάνει προσθήκες και διαγραφές 904 00:39:42,710 --> 00:39:44,850 σε μια δομή δεδομένων, όπως αυτό; 905 00:39:44,850 --> 00:39:46,630 Λοιπόν, επιτρέψτε μου να προτείνω - 906 00:39:46,630 --> 00:39:51,570 και επιτρέψτε μου να πάω πίσω στην οθόνη πάνω εδώ - αν έχουμε n στοιχεία στην 907 00:39:51,570 --> 00:39:56,330 λίστα, οπότε αν προσπαθούμε να εισάγετε n στοιχεία, και έχουμε 908 00:39:56,330 --> 00:39:58,050 πόσα κουβάδες; 909 00:39:58,050 --> 00:40:03,450 Ας πούμε 31 στο σύνολο κουβάδες στην περίπτωση της γενέθλια. 910 00:40:03,450 --> 00:40:09,240 Ποια είναι η μέγιστη διάρκεια ενός από αυτές τις αλυσίδες δυνητικά; 911 00:40:09,240 --> 00:40:12,670 >> Αν πάλι υπάρχει 31 δυνατό Γενέθλια σε έναν δεδομένο μήνα. 912 00:40:12,670 --> 00:40:14,580 Και είμαστε συσσώρευση απλά ο καθένας - 913 00:40:14,580 --> 00:40:15,580 Στην πραγματικότητα αυτό είναι ένα ηλίθιο παράδειγμα. 914 00:40:15,580 --> 00:40:16,960 Ας κάνουμε 26 αντ 'αυτού. 915 00:40:16,960 --> 00:40:20,890 Έτσι, αν έχουν στην πραγματικότητα οι άνθρωποι των οποίων τα ονόματα Ξεκινήστε με ένα έως Z, δίνοντας έτσι 916 00:40:20,890 --> 00:40:22,780 26 μας δυνατότητες. 917 00:40:22,780 --> 00:40:25,920 Και είμαστε χρησιμοποιώντας μια δομή δεδομένων, όπως το ένα μόλις είδαμε, με την οποία έχουμε 918 00:40:25,920 --> 00:40:30,210 μια σειρά από δείκτες, καθένα από τα οποία σημεία σε μια συνδεδεμένη λίστα, όπου το 919 00:40:30,210 --> 00:40:32,360 πρώτος κατάλογος είναι ο καθένας με το όνομα Alice. 920 00:40:32,360 --> 00:40:35,770 Ο δεύτερος κατάλογος είναι κάθε με το όνομα που αρχίζει με Α, ξεκινώντας 921 00:40:35,770 --> 00:40:36,980 με το Β, και ούτω καθεξής. 922 00:40:36,980 --> 00:40:41,020 >> Ποια είναι η πιθανή μήκος κάθε οι κατάλογοι αν υποθέσουμε ένα ωραίο καθαρό 923 00:40:41,020 --> 00:40:45,410 διανομή των ονομάτων Α έως Ζ σε όλη την δομή των δεδομένων; 924 00:40:45,410 --> 00:40:50,210 Υπάρχει n ανθρώπους στη δομή δεδομένων διαιρείται με 26, αν είναι όμορφα 925 00:40:50,210 --> 00:40:52,110 απλώνονται σε όλο το δομή δεδομένων. 926 00:40:52,110 --> 00:40:54,970 Έτσι, το μήκος καθενός από αυτά αλυσίδες είναι n διαιρείται με 26. 927 00:40:54,970 --> 00:40:57,380 Αλλά σε μεγάλο συμβολισμό O, τι είναι αυτό; 928 00:40:57,380 --> 00:41:00,100 929 00:41:00,100 --> 00:41:02,440 Τι είναι αυτό πραγματικά; 930 00:41:02,440 --> 00:41:04,150 Έτσι, είναι πραγματικά ακριβώς n, έτσι δεν είναι; 931 00:41:04,150 --> 00:41:06,620 Επειδή έχουμε πει και στο παρελθόν, ότι ugh σας χωρίζουν από 26. 932 00:41:06,620 --> 00:41:08,710 Ναι, στην πραγματικότητα είναι πιο γρήγορα. 933 00:41:08,710 --> 00:41:12,720 Αλλά στη θεωρία, δεν είναι θεμελιωδώς όλα αυτά πιο γρήγορα. 934 00:41:12,720 --> 00:41:16,040 >> Γι 'αυτό και δεν φαίνεται να είναι όλα αυτά πολύ πιο κοντά σε αυτό το Άγιο Δισκοπότηρο. 935 00:41:16,040 --> 00:41:17,750 Στην πραγματικότητα, αυτό είναι μόνο γραμμικό χρόνο. 936 00:41:17,750 --> 00:41:20,790 Heck, σε αυτό το σημείο, γιατί δεν απλά χρησιμοποιήστε ένα τεράστιο συνδεδεμένη λίστα; 937 00:41:20,790 --> 00:41:23,510 Γιατί δεν χρησιμοποιούμε απλώς μια τεράστια πίνακα για να αποθηκεύσετε τα ονόματα των 938 00:41:23,510 --> 00:41:25,010 ο καθένας στο δωμάτιο; 939 00:41:25,010 --> 00:41:28,280 Λοιπόν, υπάρχει ακόμα κάτι συναρπαστικό για ένα πίνακα κατακερματισμού; 940 00:41:28,280 --> 00:41:30,810 Υπάρχει ακόμα υπάρχει κάτι συναρπαστικό για μια δομή δεδομένων 941 00:41:30,810 --> 00:41:33,940 που μοιάζει με αυτό; 942 00:41:33,940 --> 00:41:35,182 Αυτό. 943 00:41:35,182 --> 00:41:37,050 >> ΦΟΙΤΗΤΗΣ: [δεν ακούγεται]. 944 00:41:37,050 --> 00:41:39,840 >> ΟΜΙΛΗΤΗΣ 1: Δεξιά, και πάλι αν είναι απλά ένα γραμμικό αλγόριθμο του χρόνου, και ένα 945 00:41:39,840 --> 00:41:42,780 γραμμική δομή του χρόνου τα δεδομένα, γιατί δεν μπορώ να αποθηκεύουν μόνο το όνομα του καθενός σε ένα μεγάλο 946 00:41:42,780 --> 00:41:44,210 array, ή σε ένα συνδεδεμένο μεγάλη λίστα; 947 00:41:44,210 --> 00:41:47,010 Και σταματήσει να κάνει CS πολύ πιο δύσκολο ό, τι πρέπει να είναι; 948 00:41:47,010 --> 00:41:49,600 949 00:41:49,600 --> 00:41:53,190 Τι είναι συναρπαστικό γι 'αυτό, ακόμα και αν και το γδαρμένο έξω; 950 00:41:53,190 --> 00:41:54,930 >> ΦΟΙΤΗΤΗΣ: [δεν ακούγεται]. 951 00:41:54,930 --> 00:41:57,040 >> ΟΜΙΛΗΤΗΣ 1: Εισαγωγές δεν είναι; 952 00:41:57,040 --> 00:41:58,140 Ακριβά πια. 953 00:41:58,140 --> 00:42:03,390 Έτσι εισαγωγές δυνητικά θα μπορούσε ακόμα να είναι σταθερό χρόνο, ακόμα και αν τα δεδομένα σας 954 00:42:03,390 --> 00:42:07,910 δομή μοιάζει με αυτό, μια σειρά από δείκτες, καθένα από τα οποία να υποδεικνύουν 955 00:42:07,910 --> 00:42:09,550 δυνητικά μια συνδεδεμένη λίστα. 956 00:42:09,550 --> 00:42:15,220 Πώς θα μπορούσε να επιτευχθεί σταθερή εισαγωγή του χρόνου των ονομάτων; 957 00:42:15,220 --> 00:42:16,280 Κολλήστε το στο μπροστινό μέρος, έτσι δεν είναι; 958 00:42:16,280 --> 00:42:19,290 >> Αν θυσιάσουμε ένα γκολ σχεδιασμού από Νωρίτερα, όταν θέλαμε να κρατήσει 959 00:42:19,290 --> 00:42:22,650 το όνομα του καθενός, για παράδειγμα, ταξινόμηση, ή όλους τους αριθμούς στη σκηνή ταξινομημένο, 960 00:42:22,650 --> 00:42:25,020 υποθέσουμε ότι έχουμε ένα αδιαχώριστα συνδεδεμένη λίστα. 961 00:42:25,020 --> 00:42:29,960 Κοστίζει μόνο μας ένα ή δύο βήματα, όπως στην περίπτωση του Μπεν και Brian 962 00:42:29,960 --> 00:42:32,750 νωρίτερα, για να εισαγάγετε ένα στοιχείο σε η αρχή της λίστας. 963 00:42:32,750 --> 00:42:36,090 Έτσι, αν δεν νοιάζονται για τη διαλογή όλα τα ονόματα αρχίζουν με Α ή όλα 964 00:42:36,090 --> 00:42:39,660 τα ονόματα που αρχίζουν με B, μπορούμε ακόμα επιτύχουν σταθερή εισαγωγή του χρόνου. 965 00:42:39,660 --> 00:42:43,900 Τώρα, κοιτώντας ψηλά Alice ή Bob ή οποιοδήποτε όνομα γενικότερα εξακολουθεί να είναι ό, τι; 966 00:42:43,900 --> 00:42:48,100 Είναι μεγάλη O Ν διαιρείται με 26, στην ιδανική περίπτωση, όπου ο καθένας είναι ομοιόμορφα 967 00:42:48,100 --> 00:42:51,190 διανέμεται, όπου υπάρχει, όπως πολλοί Α καθώς υπάρχουν το Ζ, το οποίο είναι πιθανώς 968 00:42:51,190 --> 00:42:52,220 ρεαλιστικό. 969 00:42:52,220 --> 00:42:53,880 Αλλά αυτό είναι ακόμα γραμμικό. 970 00:42:53,880 --> 00:42:57,120 >> Αλλά εδώ, ερχόμαστε πίσω στο σημείο της ασυμπτωτικής συμβολισμός είναι 971 00:42:57,120 --> 00:42:58,600 θεωρητικά αλήθεια. 972 00:42:58,600 --> 00:43:02,960 Όμως στον πραγματικό κόσμο, αν πω ότι το το πρόγραμμά μου μπορεί να κάνει κάτι 26 φορές 973 00:43:02,960 --> 00:43:06,210 γρηγορότερα από το δικό σας, το πρόγραμμα των οποίων θα πας να προτιμούν να χρησιμοποιούν; 974 00:43:06,210 --> 00:43:09,660 Δικός σου ή δική μου, η οποία είναι 26 φορές πιο γρήγορα; 975 00:43:09,660 --> 00:43:14,320 Ρεαλιστικά, το πρόσωπο του οποίου είναι 26 φορές πιο γρήγορα, ακόμη και αν θεωρητικά 976 00:43:14,320 --> 00:43:18,790 αλγορίθμων μας τρέχουν στην ίδια ασυμπτωτική χρόνο λειτουργίας. 977 00:43:18,790 --> 00:43:20,940 >> Επιτρέψτε μου να προτείνω μια διαφορετική διαλύματος συνολικά. 978 00:43:20,940 --> 00:43:24,380 Και αν αυτό δεν φυσήξει το μυαλό σας, είμαστε έξω από τις δομές δεδομένων. 979 00:43:24,380 --> 00:43:27,420 Έτσι, αυτό είναι μια trie - 980 00:43:27,420 --> 00:43:28,520 είδος ηλίθιο όνομα. 981 00:43:28,520 --> 00:43:32,880 Προέρχεται από ανακτήσεων, και ο Λόγος γράφεται trie, t-r-i-e, λόγω της 982 00:43:32,880 --> 00:43:34,450 ανάκτηση φυσικά ακούγεται σαν trie. 983 00:43:34,450 --> 00:43:36,580 Αλλά αυτό είναι η ιστορία του trie λέξης. 984 00:43:36,580 --> 00:43:40,980 >> Έτσι, μια trie είναι πράγματι κάποιο είδος δέντρου, και είναι επίσης ένα παιχνίδι σε αυτή τη λέξη. 985 00:43:40,980 --> 00:43:46,330 Και ακόμα κι αν δεν μπορείτε να δείτε αρκετά με αυτή την απεικόνιση, ένα trie είναι ένα 986 00:43:46,330 --> 00:43:50,790 δέντρο δομή, σαν ένα οικογενειακό δέντρο με ένα πρόγονο στην κορυφή και πολλά 987 00:43:50,790 --> 00:43:54,530 από τα εγγόνια και τα δισέγγονα όπως τα φύλλα στο κάτω μέρος. 988 00:43:54,530 --> 00:43:58,100 Αλλά κάθε κόμβος σε ένα trie είναι ένας πίνακας. 989 00:43:58,100 --> 00:44:00,680 Και είναι σε μια σειρά - και ας υπεραπλουστεύσουμε για μια στιγμή - είναι μια 990 00:44:00,680 --> 00:44:04,600 συστοιχία, στην περίπτωση αυτή, το μέγεθος του 26, όπου κάθε κόμβος είναι και πάλι μια σειρά μεγέθους 991 00:44:04,600 --> 00:44:09,000 26, όπου το στοιχείο μηδενικής το ότι συστοιχία αντιπροσωπεύει Α, και το τελευταίο 992 00:44:09,000 --> 00:44:11,810 στοιχείο σε κάθε τέτοια array αντιπροσωπεύει Z. 993 00:44:11,810 --> 00:44:15,520 >> Γι 'αυτό και προτείνω, λοιπόν, ότι αυτά τα δεδομένα δομή, γνωστή ως ένα trie, μπορεί να είναι 994 00:44:15,520 --> 00:44:17,600 χρησιμοποιείται επίσης για την αποθήκευση λέξεις. 995 00:44:17,600 --> 00:44:21,740 Είδαμε πριν από λίγο το πώς θα μπορούσε να αποθηκεύσει λέξεις, ή σε αυτήν την περίπτωση τα ονόματα, και εμείς 996 00:44:21,740 --> 00:44:25,440 είδε νωρίτερα πόσο μπορούμε να αποθηκεύσουμε τους αριθμούς, αλλά αν έχουμε επικεντρωθεί σε ονόματα ή χορδές 997 00:44:25,440 --> 00:44:27,460 εδώ, παρατηρήστε τι είναι ενδιαφέρον. 998 00:44:27,460 --> 00:44:32,210 Ισχυρίζομαι ότι το όνομα Maxwell είναι στο εσωτερικό της δομής αυτής δεδομένων. 999 00:44:32,210 --> 00:44:33,730 Πού βλέπετε Maxwell; 1000 00:44:33,730 --> 00:44:35,140 >> ΦΟΙΤΗΤΗΣ: [δεν ακούγεται]. 1001 00:44:35,140 --> 00:44:36,240 >> ΟΜΙΛΗΤΗΣ 1: Στην αριστερή. 1002 00:44:36,240 --> 00:44:39,910 Έτσι, αυτό που είναι ενδιαφέρον με αυτά τα δεδομένα δομή είναι αντί κατάστημα της 1003 00:44:39,910 --> 00:44:46,200 συμβολοσειρά Μ-Α-Χ-W-E-L-L backslash μηδέν, όλα συνεχόμενα, τι αντί να κάνετε 1004 00:44:46,200 --> 00:44:46,890 ακολουθεί. 1005 00:44:46,890 --> 00:44:50,510 Εάν αυτό είναι ένα trie όπως η δομή των δεδομένων, κάθε ένα από τους κόμβους των οποίων είναι και πάλι μια σειρά, 1006 00:44:50,510 --> 00:44:54,650 και θέλετε να αποθηκεύσετε Maxwell, θα πρέπει πρώτα δείκτη και έτσι ο κόμβος της ρίζας, έτσι 1007 00:44:54,650 --> 00:44:57,810 να μιλήσει, το κορυφαίο κόμβο, στη θέση M, δεξιά, έτσι ώστε 1008 00:44:57,810 --> 00:44:59,160 περίπου στη μέση. 1009 00:44:59,160 --> 00:45:03,740 Και στη συνέχεια, από εκεί, θα ακολουθήσει μια δείκτη σε κόμβους του παιδιού, να το πω έτσι. 1010 00:45:03,740 --> 00:45:06,150 Έτσι, με την έννοια οικογενειακό δέντρο, μπορείτε να ακολουθήσετε προς τα κάτω. 1011 00:45:06,150 --> 00:45:09,030 Και αυτό θα οδηγήσει σε ένα άλλο κόμβο στην αριστερή εκεί, η οποία είναι 1012 00:45:09,030 --> 00:45:10,540 ακριβώς ένα άλλο πίνακα. 1013 00:45:10,540 --> 00:45:14,710 >> Και στη συνέχεια, αν θέλετε να αποθηκεύσετε Maxwell, μπορείτε να βρείτε το δείκτη που αντιπροσωπεύει 1014 00:45:14,710 --> 00:45:16,430 Α, το οποίο είναι αυτό εδώ. 1015 00:45:16,430 --> 00:45:17,840 Στη συνέχεια πηγαίνετε στον επόμενο κόμβο. 1016 00:45:17,840 --> 00:45:20,100 Και σημειώστε - αυτό είναι γιατί η εικόνα του λίγο παραπλανητική - 1017 00:45:20,100 --> 00:45:21,990 ο κόμβος βλέμμα σούπερ μικρό. 1018 00:45:21,990 --> 00:45:26,050 Αλλά για το δικαίωμα αυτό είναι Υ και Ζ. Είναι ακριβώς ο συγγραφέας έχει περικοπεί η 1019 00:45:26,050 --> 00:45:27,630 εικόνα έτσι ώστε να μπορείτε πραγματικά δείτε τα πράγματα. 1020 00:45:27,630 --> 00:45:30,400 Διαφορετικά, αυτή η εικόνα θα είναι εξαιρετικά ευρύ. 1021 00:45:30,400 --> 00:45:36,180 Έτσι τώρα μπορείτε δείκτη στην θέση Χ, στη συνέχεια, W, E, τότε L, στη συνέχεια L. Τότε τι είναι 1022 00:45:36,180 --> 00:45:37,380 αυτή η περιέργεια; 1023 00:45:37,380 --> 00:45:41,250 >> Λοιπόν, αν είστε με τη χρήση αυτού του είδους των νέων να λάβει σχετικά με το πώς να αποθηκεύσετε ένα string σε ένα 1024 00:45:41,250 --> 00:45:44,500 δομή των δεδομένων, θα πρέπει ακόμα να ουσιαστικά ελέγχουν off στα δεδομένα 1025 00:45:44,500 --> 00:45:47,250 δομή ότι μια λέξη τελειώνει εδώ. 1026 00:45:47,250 --> 00:45:50,830 Με άλλα λόγια, κάθε ένα από αυτούς τους κόμβους με κάποιο τρόπο θα πρέπει να θυμόμαστε ότι 1027 00:45:50,830 --> 00:45:53,500 πράγματι ακολούθησε όλες αυτές τις υποδείξεις και αφήνοντας λίγο 1028 00:45:53,500 --> 00:45:58,370 ψίχα ψωμιού στο κάτω μέρος της εδώ αυτό δομή για να δείξει Μ-Α-Χ-W-E-L-L είναι 1029 00:45:58,370 --> 00:46:00,230 Πράγματι, σε αυτή τη δομή δεδομένων. 1030 00:46:00,230 --> 00:46:02,040 >> Έτσι, μπορούμε να το κάνουμε αυτό ως εξής. 1031 00:46:02,040 --> 00:46:06,810 Κάθε ένας από τους κόμβους στην εικόνα που μόλις έχει ένα πριόνι, μια σειρά από μέγεθος 27. 1032 00:46:06,810 --> 00:46:10,550 Και είναι τώρα 27, γιατί το p έθεσε έξι, θα πραγματικά να σας δώσει μια απόστροφο, 1033 00:46:10,550 --> 00:46:13,590 έτσι ώστε να μπορούμε να έχουμε ονόματα όπως O'Reilly και άλλοι με απόστροφοι. 1034 00:46:13,590 --> 00:46:14,820 Αλλά ίδια ιδέα. 1035 00:46:14,820 --> 00:46:17,710 Κάθε ένα από τα στοιχεία αυτά στον σημεία πίνακα σε μια struct 1036 00:46:17,710 --> 00:46:19,320 κόμβο, έτσι απλά ένας κόμβος. 1037 00:46:19,320 --> 00:46:21,430 Έτσι, αυτό είναι πολύ θυμίζει των συνδεδεμένων λίστα μας. 1038 00:46:21,430 --> 00:46:24,550 >> Και τότε έχω μια Boolean, το οποίο εγώ θα καλέστε λέξη, η οποία είναι ακριβώς πρόκειται να είναι 1039 00:46:24,550 --> 00:46:29,120 αλήθεια αν μια λέξη τελειώνει σε αυτό κόμβο στο δέντρο. 1040 00:46:29,120 --> 00:46:32,870 Αποτελεί ουσιαστικά το μικρό τρίγωνο που είδαμε πριν από λίγο. 1041 00:46:32,870 --> 00:46:37,190 Έτσι, αν μια λέξη τελειώνει σε αυτόν τον κόμβο στην δέντρο, αυτό το πεδίο λέξη είναι αληθινή, 1042 00:46:37,190 --> 00:46:41,990 το οποίο είναι εννοιολογικά τον έλεγχο μακριά, ή είμαστε αντλώντας αυτό το τρίγωνο, ναι εκεί 1043 00:46:41,990 --> 00:46:44,080 είναι μια λέξη εδώ. 1044 00:46:44,080 --> 00:46:45,120 >> Έτσι, αυτό είναι μια trie. 1045 00:46:45,120 --> 00:46:48,540 Και τώρα το ερώτημα είναι, τι τρέχει του χρόνου; 1046 00:46:48,540 --> 00:46:49,930 Είναι μεγάλη O Ν; 1047 00:46:49,930 --> 00:46:51,410 Είναι κάτι άλλο; 1048 00:46:51,410 --> 00:46:57,330 Λοιπόν, αν έχετε n ονόματα σε αυτά τα δεδομένα δομή, Maxwell είναι ένα μόνο από 1049 00:46:57,330 --> 00:47:02,330 τους, τι είναι ο χρόνος εκτέλεσης του εισαγωγή ή την εύρεση Maxwell; 1050 00:47:02,330 --> 00:47:06,230 1051 00:47:06,230 --> 00:47:09,050 Τι είναι ο χρόνος εκτέλεσης της εισαγωγής Maxwell; 1052 00:47:09,050 --> 00:47:11,740 Αν υπάρχει n άλλα ονόματα ήδη στον πίνακα; 1053 00:47:11,740 --> 00:47:12,507 Ναι; 1054 00:47:12,507 --> 00:47:15,429 >> ΦΟΙΤΗΤΗΣ: [δεν ακούγεται]. 1055 00:47:15,429 --> 00:47:17,550 >> ΟΜΙΛΗΤΗΣ 1: Ναι, αυτό είναι το μήκος το όνομα, έτσι δεν είναι; 1056 00:47:17,550 --> 00:47:24,420 Έτσι, Μ-Α-Χ-w-e-l-l έτσι ώστε να αισθάνεται σαν αυτό αλγόριθμος είναι μεγάλη O επτά. 1057 00:47:24,420 --> 00:47:26,580 Τώρα, φυσικά, το όνομα θα ποικίλουν σε μήκος. 1058 00:47:26,580 --> 00:47:27,380 Ίσως αυτό είναι ένα σύντομο όνομα. 1059 00:47:27,380 --> 00:47:28,600 Ίσως είναι ένα μεγαλύτερο όνομα. 1060 00:47:28,600 --> 00:47:33,390 Αλλά αυτό είναι το κλειδί εδώ είναι ότι είναι ένας σταθερός αριθμός. 1061 00:47:33,390 --> 00:47:36,810 Και ίσως δεν είναι πολύ σταθερή, Αλλά ο Θεός, αν ρεαλιστικά, σε 1062 00:47:36,810 --> 00:47:41,570 λεξικό, είναι πιθανόν να υπάρχει κάποιο όριο σχετικά με τον αριθμό των γραμμάτων σε μια 1063 00:47:41,570 --> 00:47:43,820 το όνομα του ατόμου σε μια συγκεκριμένη χώρα. 1064 00:47:43,820 --> 00:47:46,940 >> Και έτσι μπορούμε να υποθέσουμε ότι τιμή είναι μια σταθερά. 1065 00:47:46,940 --> 00:47:47,750 Δεν ξέρω τι είναι. 1066 00:47:47,750 --> 00:47:50,440 Είναι πιθανώς μεγαλύτερη από ό, τι πιστεύουμε ότι είναι. 1067 00:47:50,440 --> 00:47:52,720 Επειδή υπάρχει πάντα κάποια γωνιά περίπτωση με ένα τρελό μεγάλο όνομα. 1068 00:47:52,720 --> 00:47:56,360 Έτσι, ας την ονομάσουμε k, αλλά είναι ακόμα ένα σταθερή κατά πάσα πιθανότητα, επειδή κάθε 1069 00:47:56,360 --> 00:48:00,190 όνομα στον κόσμο, τουλάχιστον σε ένα συγκεκριμένη χώρα, είναι ότι το μήκος ή 1070 00:48:00,190 --> 00:48:01,780 μικρότερη, έτσι ώστε να είναι σταθερή. 1071 00:48:01,780 --> 00:48:04,490 Αλλά όταν έχουμε πει κάτι είναι μεγάλο O από μια σταθερή αξία, τι είναι αυτό 1072 00:48:04,490 --> 00:48:07,760 πραγματικά ισοδυναμεί με; 1073 00:48:07,760 --> 00:48:10,420 Αυτό είναι πραγματικά το ίδιο πράγμα όπως λέει σταθερό χρόνο. 1074 00:48:10,420 --> 00:48:11,530 >> Τώρα είμαστε το είδος της εξαπάτησης, έτσι δεν είναι; 1075 00:48:11,530 --> 00:48:15,340 Είμαστε το είδος της μόχλευσης κάποια θεωρία εδώ να πω ότι καλά, σειρά k είναι 1076 00:48:15,340 --> 00:48:17,450 πραγματικά ακριβώς τάξης του ενός, και είναι σταθερό χρόνο. 1077 00:48:17,450 --> 00:48:18,200 Αλλά είναι πραγματικά. 1078 00:48:18,200 --> 00:48:22,550 Επειδή η βασική αντίληψη εδώ είναι ότι αν έχουμε n ονόματα που έχουν ήδη σ 'αυτό 1079 00:48:22,550 --> 00:48:26,010 δομή των δεδομένων, και εμείς ένθετο Maxwell, είναι το χρονικό διάστημα που μας χρειάζεται για να 1080 00:48:26,010 --> 00:48:29,530 εισάγετε Maxwell σε όλους τους πληγέντες από πόσοι άλλοι άνθρωποι 1081 00:48:29,530 --> 00:48:31,100 είναι στη δομή δεδομένων; 1082 00:48:31,100 --> 00:48:31,670 Δεν φαίνεται να είναι. 1083 00:48:31,670 --> 00:48:36,280 Αν είχα ένα δισεκατομμύριο περισσότερα στοιχεία σε αυτό trie, και στη συνέχεια τοποθετήστε Maxwell, είναι 1084 00:48:36,280 --> 00:48:38,650 ο ίδιος σε όλους τους πληγέντες; 1085 00:48:38,650 --> 00:48:39,050 Όχι. 1086 00:48:39,050 --> 00:48:42,950 Και αυτό είναι σε αντίθεση με οποιαδήποτε από τις ημέρας δεδομένων δομές που έχουμε δει μέχρι στιγμής, όπου 1087 00:48:42,950 --> 00:48:46,820 ο χρόνος εκτέλεσης του αλγορίθμου σας εντελώς ανεξάρτητη από το πόσο 1088 00:48:46,820 --> 00:48:51,430 τα πράγματα είναι ή δεν είναι ήδη στην εν λόγω δομή δεδομένων. 1089 00:48:51,430 --> 00:48:54,650 >> Και έτσι με αυτό σας δίνει είναι τώρα ένα ευκαιρία για την p σύνολο έξι, η οποία θα 1090 00:48:54,650 --> 00:48:58,310 και πάλι συνεπάγεται την εφαρμογή της δικής σας ορθογραφικός έλεγχος, διαβάζοντας σε 150.000 1091 00:48:58,310 --> 00:49:01,050 Δηλαδή, με τον καλύτερο τρόπο για να αποθηκεύετε τα δεν είναι απαραίτητα προφανής. 1092 00:49:01,050 --> 00:49:04,030 Και αν και έχω φιλοδοξούσε να βρει το Άγιο Δισκοπότηρο, δεν το κάνω 1093 00:49:04,030 --> 00:49:05,330 υποστηρίζουν ότι μια trie είναι. 1094 00:49:05,330 --> 00:49:09,810 Στην πραγματικότητα, ένας πίνακας κατακερματισμού μπορεί να είναι πολύ καλά αποδειχθεί να είναι πολύ πιο αποτελεσματική. 1095 00:49:09,810 --> 00:49:10,830 Αλλά αυτά είναι μόνο - 1096 00:49:10,830 --> 00:49:14,620 αυτό είναι μόνο μία από τις αποφάσεις σχεδιασμού θα πρέπει να κάνουν. 1097 00:49:14,620 --> 00:49:18,920 >> Αλλά στο κλείσιμο ας ρίξουμε 50 ή έτσι δευτερόλεπτα για να λάβει μια ματιά σε ό, τι βρίσκεται 1098 00:49:18,920 --> 00:49:22,190 την ερχόμενη εβδομάδα και πέρα ​​έχουμε μετάβαση από αυτή την γραμμή εντολών 1099 00:49:22,190 --> 00:49:26,220 κόσμο, εάν τα προγράμματα C τα πράγματα web βάση και γλώσσες όπως η PHP και 1100 00:49:26,220 --> 00:49:30,350 JavaScript και το ίδιο το διαδίκτυο, πρωτόκολλα όπως το HTTP, το οποίο έχετε 1101 00:49:30,350 --> 00:49:32,870 θεωρείται δεδομένη για πολλά χρόνια τώρα, και δακτυλογραφημένες πλέον κάθε 1102 00:49:32,870 --> 00:49:34,440 ημερών, ίσως, ή δει. 1103 00:49:34,440 --> 00:49:37,420 Και θα αρχίσουμε να φλούδα πίσω την στρώματα του τι είναι το διαδίκτυο. 1104 00:49:37,420 --> 00:49:40,650 Και τι είναι ο κώδικας που κρύβεται πίσω από τη σημερινή εργαλεία. 1105 00:49:40,650 --> 00:49:43,230 Έτσι, 50 δευτερόλεπτα αυτού του teaser εδώ. 1106 00:49:43,230 --> 00:49:46,570 Σας δίνω Πολεμιστές του Net. 1107 00:49:46,570 --> 00:49:51,370 >> [PLAYBACK VIDEO] 1108 00:49:51,370 --> 00:49:56,764 >> -Ήρθε με ένα μήνυμα. 1109 00:49:56,764 --> 00:50:00,687 Με ένα πρωτόκολλο όλα δικά του. 1110 00:50:00,687 --> 00:50:13,370 1111 00:50:13,370 --> 00:50:19,780 Ήρθε σε έναν κόσμο της σκληρής firewalls, αδιάφορος routers, και τους κινδύνους μακριά 1112 00:50:19,780 --> 00:50:22,600 χειρότερη από τον θάνατο. 1113 00:50:22,600 --> 00:50:23,590 Είναι γρήγορος. 1114 00:50:23,590 --> 00:50:25,300 Είναι ισχυρή. 1115 00:50:25,300 --> 00:50:27,700 Είναι TCPIP. 1116 00:50:27,700 --> 00:50:30,420 Και πήρε τη διεύθυνσή σας. 1117 00:50:30,420 --> 00:50:32,920 1118 00:50:32,920 --> 00:50:34,590 Πολεμιστές του Net. 1119 00:50:34,590 --> 00:50:35,290 >> [PLAYBACK VIDEO END] 1120 00:50:35,290 --> 00:50:38,070 >> ΟΜΙΛΗΤΗΣ 1: Αυτό είναι το πώς το Διαδίκτυο πρέπει να λειτουργήσει ως της επόμενης εβδομάδας. 1121 00:50:38,070 --> 00:50:40,406