1
00:00:00,000 --> 00:00:02,520
[Powered by Google Translate] [Εβδομάδα 6, Συνέχεια]

2
00:00:02,520 --> 00:00:04,160
[David J. Malan] [Πανεπιστήμιο του Χάρβαρντ]

3
00:00:04,160 --> 00:00:08,720
[Αυτό είναι CS50.] [CS50.TV]

4
00:00:08,720 --> 00:00:12,970
Αυτό είναι CS50 και αυτό είναι το τέλος της εβδομάδας 6.

5
00:00:12,970 --> 00:00:17,970
Έτσι CS50x, ένα από τα πρώτα μαθήματα του Χάρβαρντ που συμμετέχουν στην πρωτοβουλία EDX

6
00:00:17,970 --> 00:00:20,590
Πράγματι, έκανε το ντεμπούτο του την περασμένη Δευτέρα.

7
00:00:20,590 --> 00:00:23,460
Αν θέλετε να πάρετε μια γεύση από το τι άλλοι στο Διαδίκτυο

8
00:00:23,460 --> 00:00:27,180
ακολουθούν τώρα μαζί με, μπορείτε να κατευθυνθείτε προς x.cs50.net.

9
00:00:27,180 --> 00:00:30,350
Αυτό θα σας ανακατευθύνει στην κατάλληλη θέση για edx.org,

10
00:00:30,350 --> 00:00:34,160
η οποία ήταν και αυτή όπου άλλα μαθήματα από το MIT και το Berkeley ζουν τώρα.

11
00:00:34,160 --> 00:00:38,140
Θα πρέπει να εγγραφείτε για ένα λογαριασμό? Θα βρείτε ότι το υλικό είναι σε μεγάλο βαθμό η ίδια

12
00:00:38,140 --> 00:00:42,170
όπως είχατε αυτό το εξάμηνο, αν και καθυστέρησε μερικές εβδομάδες, όπως έχουμε πάρει τα πάντα έτοιμα.

13
00:00:42,170 --> 00:00:46,930
Αλλά ό, τι οι μαθητές στο CS50x θα δούμε τώρα είναι μια διεπαφή αρκετά όπως αυτό.

14
00:00:46,930 --> 00:00:50,040
Αυτό, για παράδειγμα, είναι Zamyla οδηγεί το walkthrough για σετ προβλήματος 0.

15
00:00:50,040 --> 00:00:54,230
Μόλις συνδεθείτε με edx.org, ένας φοιτητής CS50x βλέπει τα είδη των πραγμάτων

16
00:00:54,230 --> 00:00:57,170
που θα περιμένατε να δείτε σε ένα μάθημα: η διάλεξη για τη Δευτέρα,

17
00:00:57,170 --> 00:01:01,650
διάλεξη για την Τετάρτη, διάφορα σορτς, τα σύνολα πρόβλημα, τα περάσματα, αρχεία PDF.

18
00:01:01,650 --> 00:01:04,459
Επιπλέον, όπως βλέπετε εδώ, αυτόματες μεταφράσεις

19
00:01:04,459 --> 00:01:08,390
της αγγλικής μεταγραφές σε κινεζικά, ιαπωνικά, ισπανικά, ιταλικά,

20
00:01:08,390 --> 00:01:12,810
και ένα σωρό άλλες γλώσσες που σίγουρα θα είναι ατελής

21
00:01:12,810 --> 00:01:15,840
όπως εμείς τους ανοίγουμε με προγραμματισμό χρησιμοποιώντας κάτι που ονομάζεται ένα API,

22
00:01:15,840 --> 00:01:18,360
ή διεπαφή προγραμματισμού εφαρμογών, από την Google

23
00:01:18,360 --> 00:01:21,360
που μας επιτρέπει να μετατρέψετε Αγγλικά σε αυτές τις άλλες γλώσσες.

24
00:01:21,360 --> 00:01:24,100
Αλλά χάρη στο υπέροχο πνεύμα μερικών εκατοντάδων εθελοντών-plus,

25
00:01:24,100 --> 00:01:26,940
τυχαίους ανθρώπους στο διαδίκτυο που προσφέρθηκαν ευγενικά να συμμετάσχουν

26
00:01:26,940 --> 00:01:30,180
σε αυτό το έργο, θα πρέπει σταδιακά να βελτιωθεί η ποιότητα των μεταφράσεων

27
00:01:30,180 --> 00:01:35,790
από τους ανθρώπους που έχουν διορθώσει τα λάθη που οι υπολογιστές μας έχουν κάνει.

28
00:01:35,790 --> 00:01:42,330
>> Έτσι αποδεικνύεται είχαμε λίγα περισσότεροι φοιτητές δείχνουν μέχρι τη Δευτέρα από ό, τι αρχικά αναμενόταν.

29
00:01:42,330 --> 00:01:48,980
Στην πραγματικότητα, τώρα έχει CS50x 100.000 άνθρωποι μετά μαζί στο σπίτι.

30
00:01:48,980 --> 00:01:54,430
Έτσι συνειδητοποιήσει ότι είναι όλα μέρος αυτής της εναρκτήριας κατηγορίας του κάνει αυτή την πορεία στην επιστήμη των υπολογιστών

31
00:01:54,430 --> 00:01:57,370
εκπαίδευση γενικότερα, ευρύτερα, προσβάσιμα.

32
00:01:57,370 --> 00:02:00,130
Και η πραγματικότητα είναι τώρα, με μερικά από αυτά τα τεράστια online μαθήματα,

33
00:02:00,130 --> 00:02:04,070
όλα αρχίζουν με αυτούς τους πολύ μεγάλους αριθμούς, όπως φαίνεται να έχουν γίνει εδώ.

34
00:02:04,070 --> 00:02:08,759
Αλλά ο στόχος, εν τέλει, για CS50x είναι πραγματικά να πάρει, όπως πολλοί άνθρωποι στην γραμμή του τερματισμού όσο το δυνατόν.

35
00:02:08,759 --> 00:02:12,000
Από τη σχεδίαση, CS50x πρόκειται να προσφέρει από αυτό περασμένη Δευτέρα

36
00:02:12,000 --> 00:02:17,430
σε όλη τη διαδρομή μέσα από 15 του Απριλίου 2013, έτσι ώστε οι λαοί που έχουν δεσμεύσεις αλλού σχολείο,

37
00:02:17,430 --> 00:02:20,990
την εργασία, την οικογένεια, άλλες συγκρούσεις και τα παρόμοια, έχουν λίγο περισσότερη ευελιξία

38
00:02:20,990 --> 00:02:23,640
με την οποία να βουτήξει σε αυτή την πορεία, η οποία, αρκεί να πούμε,

39
00:02:23,640 --> 00:02:30,540
είναι αρκετά φιλόδοξα, αν γίνει μόνο κατά τη διάρκεια του μόλις τρεις μήνες κατά τη διάρκεια μιας συνήθους εξάμηνο.

40
00:02:30,540 --> 00:02:34,190
Αλλά αυτοί οι μαθητές θα αντιμετωπιστούν οι ίδιες ομάδες πρόβλημα, που βλέπουν το ίδιο περιεχόμενο,

41
00:02:34,190 --> 00:02:36,350
έχοντας πρόσβαση στις ίδιες σορτς και τα παρόμοια.

42
00:02:36,350 --> 00:02:38,990
Έτσι συνειδητοποιούμε ότι είμαστε όλοι πραγματικά σε αυτή μαζί.

43
00:02:38,990 --> 00:02:42,360
Και ένας από τους στόχους τέλος του CS50x δεν είναι μόνο για να πάρει όσες λαοί

44
00:02:42,360 --> 00:02:45,720
στη γραμμή του τερματισμού και να τους δώσουμε αυτή την πρωτόγνωρη κατανόηση της επιστήμης των υπολογιστών

45
00:02:45,720 --> 00:02:49,000
και τον προγραμματισμό, αλλά και να έχουν τους έχουν αυτή την κοινή εμπειρία.

46
00:02:49,000 --> 00:02:52,010
Ένα από τα καθοριστικά χαρακτηριστικά των 50 στην πανεπιστημιούπολη, ελπίζουμε,

47
00:02:52,010 --> 00:02:56,260
έχει αυτό το είδος των κοινόχρηστων εμπειρία, προς το καλύτερο ή προς το χειρότερο, μερικές φορές,

48
00:02:56,260 --> 00:02:59,480
αλλά έχοντας τα άτομα αυτά να στραφούν σε προς τα αριστερά και προς τα δεξιά,

49
00:02:59,480 --> 00:03:01,830
και ώρες γραφείου και ο hackathon και η εύλογη.

50
00:03:01,830 --> 00:03:04,560
Είναι λίγο δύσκολο να το κάνουμε αυτό σε πρόσωπο με τους λαούς σε απευθείας σύνδεση,

51
00:03:04,560 --> 00:03:10,580
αλλά CS50x θα ολοκληρωθεί τον Απρίλιο με την πρώτη CS50 Expo,

52
00:03:10,580 --> 00:03:13,630
το οποίο θα είναι ένα online προσαρμογή της ιδέας μας της δίκαιης

53
00:03:13,630 --> 00:03:18,250
όπου οι χιλιάδες μαθητές θα κληθούν όλοι να υποβάλουν 1 - σε 2-λεπτών βίντεο,

54
00:03:18,250 --> 00:03:22,480
είτε ένα screencast του τελικού σχεδίου ή βίντεο τους από τους κουνώντας γεια

55
00:03:22,480 --> 00:03:24,490
και μιλούν για το έργο τους και να demoing,

56
00:03:24,490 --> 00:03:27,610
πολύ όπως και οι προκάτοχοί σας έχουν κάνει εδώ στην πανεπιστημιούπολη στην εύλογη,

57
00:03:27,610 --> 00:03:31,400
έτσι ώστε μέχρι το τέλος του εξαμήνου, η ελπίδα είναι να έχουμε μια παγκόσμια έκθεση

58
00:03:31,400 --> 00:03:37,080
των τελικών σχεδίων των CS50x φοιτητών, σαν εκείνο που σας περιμένει αυτό το Δεκέμβρη στην πανεπιστημιούπολη.

59
00:03:37,080 --> 00:03:39,680
Έτσι, περισσότερα για αυτό κατά τους μήνες που έρχονται.

60
00:03:39,680 --> 00:03:43,640
>> Με 100.000 σπουδαστές, όμως, έρχεται μια ανάγκη για λίγα ΑΠ.

61
00:03:43,640 --> 00:03:47,590
Δεδομένου ότι εσείς είστε απίστευτα το μονοπάτι εδώ και λαμβάνοντας CS50

62
00:03:47,590 --> 00:03:51,630
αρκετές εβδομάδες πριν από την κυκλοφορία αυτού του υλικού για τους λαούς για EDX,

63
00:03:51,630 --> 00:03:55,330
συνειδητοποιούν θα θέλαμε να συμμετέχουν, όπως πολλοί από τους σπουδαστές μας όσο το δυνατόν σε αυτή την πρωτοβουλία,

64
00:03:55,330 --> 00:03:58,720
τόσο κατά τη διάρκεια του εξαμήνου, καθώς και αυτό το χειμώνα και την ερχόμενη άνοιξη.

65
00:03:58,720 --> 00:04:01,620
Έτσι, αν θα θέλατε να λάβετε μέρος σε CS50x,

66
00:04:01,620 --> 00:04:07,450
ιδιαίτερα για ένταξη στην CS50x Συζητήστε, η έκδοση του EDX CS50 Συζητήστε,

67
00:04:07,450 --> 00:04:10,140
το οποίο πολλοί από εσάς έχουν χρησιμοποιήσει στην πανεπιστημιούπολη, η σε απευθείας σύνδεση πίνακα ανακοινώσεων,

68
00:04:10,140 --> 00:04:13,040
παρακαλώ να το κάνετε αυτό στο κεφάλι URL, να μας πείτε ποιος είστε,

69
00:04:13,040 --> 00:04:16,450
επειδή θα θέλαμε να δημιουργήσουν μια ομάδα φοιτητών και προσωπικού και το διδακτικό προσωπικό όσο

70
00:04:16,450 --> 00:04:19,630
στην πανεπιστημιούπολη που απλά παίζουν μαζί και να βοηθήσει έξω.

71
00:04:19,630 --> 00:04:21,720
Και όταν βλέπουν μια ερώτηση που είναι εξοικειωμένοι με αυτούς,

72
00:04:21,720 --> 00:04:25,320
ακούτε ένα φοιτητή αναφέρουν κάποια bug κάπου εκεί έξω, σε κάποια χώρα στο Διαδίκτυο,

73
00:04:25,320 --> 00:04:27,450
και ότι τα δαχτυλίδια ένα κουδούνι, γιατί είχε πάρα πολύ το ίδιο θέμα

74
00:04:27,450 --> 00:04:32,620
στο d-αίθουσα πριν από λίγο καιρό, ελπίζω τότε μπορείτε να συνάδουν και να μοιραστείτε την εμπειρία σας.

75
00:04:32,620 --> 00:04:37,300
Επομένως, σας παρακαλώ μην συμμετάσχουν εάν θα θέλατε.

76
00:04:37,300 --> 00:04:39,360
>> Μαθήματα επιστήμης των υπολογιστών στο Χάρβαρντ έχουν ένα κομμάτι της παράδοσης,

77
00:04:39,360 --> 00:04:44,730
CS50 μεταξύ τους, να έχουν κάποια ένδυσης, κάποια ρούχα, που μπορείτε να φοράτε με περηφάνια

78
00:04:44,730 --> 00:04:49,090
στο τέλος του εξαμήνου, λέγοντας πολύ περήφανα ότι έχετε τελειώσει CS50

79
00:04:49,090 --> 00:04:51,830
και πήρε CS50 και τα παρόμοια, και προσπαθούμε πάντα να εμπλέξουν τους μαθητές

80
00:04:51,830 --> 00:04:54,540
σε αυτή τη διαδικασία όσο το δυνατόν περισσότερο, σύμφωνα με την οποία καλούμε,

81
00:04:54,540 --> 00:04:56,900
όλο αυτό το διάστημα του εξαμήνου, οι φοιτητές να υποβάλουν τα σχέδια

82
00:04:56,900 --> 00:04:59,330
χρησιμοποιώντας το Photoshop, ή ό, τι το εργαλείο της επιλογής που θέλετε να χρησιμοποιήσετε

83
00:04:59,330 --> 00:05:02,330
εάν είστε ένας σχεδιαστής, να υποβάλουν σχέδια για T-shirts και φούτερ

84
00:05:02,330 --> 00:05:06,100
και ομπρέλες και φουλάρια λίγο για τα σκυλιά που έχουμε τώρα και τα παρόμοια.

85
00:05:06,100 --> 00:05:09,370
Και ό, τι είναι τότε - οι νικητές κάθε χρόνο, στη συνέχεια εκτίθενται

86
00:05:09,370 --> 00:05:12,700
στην ιστοσελίδα του μαθήματος στο store.cs50.net.

87
00:05:12,700 --> 00:05:15,790
Τα πάντα πωλείται σε τιμή κόστους εκεί, αλλά η ιστοσελίδα τρέχει το ίδιο ακριβώς

88
00:05:15,790 --> 00:05:18,330
και επιτρέπει στους ανθρώπους να επιλέξετε τα χρώματα και τα σχέδια που τους αρέσει.

89
00:05:18,330 --> 00:05:20,420
Έτσι σκέφτηκα ότι θα μοιράζονται μόνο μερικά από τα σχέδια του περασμένου έτους

90
00:05:20,420 --> 00:05:25,130
που ήταν στο δικτυακό τόπο εκτός από αυτό εδώ, το οποίο είναι μια ετήσια παράδοση.

91
00:05:25,130 --> 00:05:29,410
«Κάθε μέρα είμαι ακολ Faultn" ήταν ένα από τα αιτήματα πέρυσι,

92
00:05:29,410 --> 00:05:32,290
η οποία εξακολουθεί να είναι διαθέσιμη εκεί για τους αποφοίτους.

93
00:05:32,290 --> 00:05:35,820
Είχαμε αυτό το ένα, "CS50, ιδρύθηκε το 1989."

94
00:05:35,820 --> 00:05:39,010
Ένα από Bowdens μας, Rob, ήταν πολύ δημοφιλής πέρυσι.

95
00:05:39,010 --> 00:05:43,480
"Ομάδα Bowden" γεννήθηκε, το σχέδιο αυτό υποβλήθηκε, μεταξύ των κορυφαίων πωλητών.

96
00:05:43,480 --> 00:05:49,040
Όπως ήταν αυτό εδώ. Πολλοί άνθρωποι είχαν "Πυρετός Bowden", σύμφωνα με τις καταγραφές των πωλήσεων.

97
00:05:49,040 --> 00:05:52,650
Συνειδητοποιήστε ότι θα μπορούσε τώρα να είναι το σχέδιό σας εκεί, επάνω στο Διαδίκτυο.

98
00:05:52,650 --> 00:05:57,510
Περισσότερες λεπτομέρειες για το θέμα αυτό στην επόμενη θέτει πρόβλημα να έρθει.

99
00:05:57,510 --> 00:06:00,330
>> Ένα ακόμη εργαλείο: είχατε κάποια έκθεση και ελπίζω τώρα

100
00:06:00,330 --> 00:06:02,350
κάποια hands-on εμπειρία με το GDB,

101
00:06:02,350 --> 00:06:04,570
το οποίο είναι, φυσικά, ένα πρόγραμμα εντοπισμού σφαλμάτων και σας επιτρέπει να χειριστείτε

102
00:06:04,570 --> 00:06:09,500
το πρόγραμμά σας σε ένα αρκετά χαμηλό επίπεδο, κάνει ό, τι τα είδη των πραγμάτων;

103
00:06:09,500 --> 00:06:13,030
Τι σημαίνει GDB σας επιτρέπουν να το κάνετε;

104
00:06:13,030 --> 00:06:15,030
Ναι; Δώσε μου κάτι. [Απάντηση Φοιτητής, ακατάληπτο]

105
00:06:15,030 --> 00:06:18,120
Καλή. Βήμα σε λειτουργία, έτσι ώστε να μην πρέπει απλώς να πληκτρολογήσετε run

106
00:06:18,120 --> 00:06:22,310
και έχουν το χτύπημα του προγράμματος μέσω σύνολό της, εκτύπωση από τα πράγματα στην κανονική έξοδο.

107
00:06:22,310 --> 00:06:25,190
Αντίθετα, μπορείτε να το βήμα μέσα από το γραμμή προς γραμμή, είτε πληκτρολογώντας επόμενη

108
00:06:25,190 --> 00:06:30,300
για να πάει γραμμή προς γραμμή, γραμμή βήμα ή να βουτήξει σε μια λειτουργία, συνήθως αυτό που γράψατε.

109
00:06:30,300 --> 00:06:35,240
Τι άλλο GDB σας επιτρέπουν να κάνετε; Ναι; [Απάντηση Φοιτητής, ακατάληπτο]

110
00:06:35,240 --> 00:06:38,100
Εκτύπωση μεταβλητών. Έτσι, εάν θέλετε να κάνετε μια μικρή ενδοσκόπηση μέσα από το πρόγραμμα σας

111
00:06:38,100 --> 00:06:41,500
χωρίς να χρειάζεται να καταφύγουν σε γραπτή printf δηλώσεις σε όλη τη χώρα,

112
00:06:41,500 --> 00:06:44,600
μπορείτε να εκτυπώσετε μόνο μια μεταβλητή ή να εμφανίσετε μια μεταβλητή.

113
00:06:44,600 --> 00:06:46,710
Τι άλλο μπορείτε να κάνετε με ένα πρόγραμμα εντοπισμού σφαλμάτων, όπως GDB;

114
00:06:46,710 --> 00:06:49,170
[Απάντηση Φοιτητής, ακατάληπτο]

115
00:06:49,170 --> 00:06:52,080
Ακριβώς. Μπορείτε να ορίσετε σημεία διακοπής? Μπορείτε να πείτε την εκτέλεση διάλειμμα

116
00:06:52,080 --> 00:06:54,020
στην κύρια λειτουργία ή τη λειτουργία foo.

117
00:06:54,020 --> 00:06:56,800
Μπορείτε να πείτε την εκτέλεση διάλειμμα στη γραμμή 123.

118
00:06:56,800 --> 00:06:58,950
Και όρια ευαισθησίας είναι μια πραγματικά ισχυρή τεχνική

119
00:06:58,950 --> 00:07:01,110
διότι αν έχετε μια γενική αίσθηση για το πού το πρόβλημά σας

120
00:07:01,110 --> 00:07:05,360
πιθανότατα είναι, δεν πρέπει να χάνουμε χρόνο με την ενίσχυση σύνολο του προγράμματος.

121
00:07:05,360 --> 00:07:08,250
Μπορείτε να μεταβείτε ουσιαστικά εκεί και μετά αρχίστε την πληκτρολόγηση -

122
00:07:08,250 --> 00:07:10,970
ενίσχυση μέσα από αυτό το βήμα ή τον επόμενο ή τα παρόμοια.

123
00:07:10,970 --> 00:07:14,340
Όμως, τα αλιεύματα με κάτι σαν GDB είναι ότι σας βοηθά, ο άνθρωπος,

124
00:07:14,340 --> 00:07:16,940
βρείτε τα προβλήματά σας και να βρείτε σφάλματα σας.

125
00:07:16,940 --> 00:07:19,470
Αυτό δεν σημαίνει απαραίτητα να τους βρείτε τόσα πολλά για σας.

126
00:07:19,470 --> 00:07:23,070
>> Γι 'αυτό και εισήγαγε την άλλη style50 ημέρα, το οποίο είναι ένα μικρό εργαλείο της γραμμής εντολών

127
00:07:23,070 --> 00:07:27,500
που προσπαθεί να στυλιζάρω κωδικό σας λίγο πιο καθαρά από ό, τι, ο άνθρωπος, θα μπορούσε να έχει γίνει.

128
00:07:27,500 --> 00:07:29,530
Αλλά αυτό, επίσης, είναι πραγματικά ακριβώς ένα αισθητικό πράγμα.

129
00:07:29,530 --> 00:07:34,110
Αλλά αποδεικνύεται ότι υπάρχει αυτό το άλλο εργαλείο που ονομάζεται Valgrind που είναι λίγο πιο απόκρυφες να χρησιμοποιήσετε.

130
00:07:34,110 --> 00:07:36,860
Τα αποτελέσματά του είναι atrociously αινιγματικά με την πρώτη ματιά.

131
00:07:36,860 --> 00:07:39,420
Αλλά είναι θαυμάσια χρήσιμο, ειδικά τώρα που είμαστε στο τμήμα του όρου

132
00:07:39,420 --> 00:07:43,080
Όπου και αν αρχίζουν να χρησιμοποιούν malloc και δυναμική κατανομή μνήμης.

133
00:07:43,080 --> 00:07:45,420
Τα πράγματα μπορούν να πάνε πολύ, πολύ γρήγορα λάθος.

134
00:07:45,420 --> 00:07:49,320
Διότι, αν ξεχάσετε να ελευθερώσετε τη μνήμη σας, ή έχετε κάποια dereference NULL δείκτη,

135
00:07:49,320 --> 00:07:55,770
ή μπορείτε dereference κάποιο δείκτη σκουπίδια, ό, τι είναι συνήθως το σύμπτωμα που προκύπτει;

136
00:07:55,770 --> 00:07:59,470
Seg σφάλμα. Και μπορείτε να πάρετε αυτό το αρχείο πυρήνα κάποιον αριθμό των kilobyte ή megabytes

137
00:07:59,470 --> 00:08:02,990
που αντιπροσωπεύει την κατάσταση της μνήμης του προγράμματός σας, όταν συνετρίβη,

138
00:08:02,990 --> 00:08:05,730
αλλά το πρόγραμμα σας διαχωρίζονται από βλάβες τελικά, σφάλμα κατάτμησης,

139
00:08:05,730 --> 00:08:08,450
που σημαίνει κάτι κακό συνέβη σχεδόν πάντα συνδέονται

140
00:08:08,450 --> 00:08:11,750
σε μια μνήμη που σχετίζονται λάθος που κάνατε κάπου.

141
00:08:11,750 --> 00:08:14,100
Έτσι Valgrind σας βοηθά να βρείτε τα πράγματα όπως αυτό.

142
00:08:14,100 --> 00:08:17,720
Είναι ένα εργαλείο που εκτελείτε, όπως GDB, αφού έχετε καταρτίζονται πρόγραμμα σας,

143
00:08:17,720 --> 00:08:20,330
αλλά αντί να τρέξετε το πρόγραμμά σας άμεσα, μπορείτε να εκτελέσετε Valgrind

144
00:08:20,330 --> 00:08:23,960
και να περάσετε το πρόγραμμά σας, ακριβώς όπως κάνετε με το GDB.

145
00:08:23,960 --> 00:08:26,220
Τώρα, η χρήση του, για να πάρει το καλύτερο είδος της παραγωγής,

146
00:08:26,220 --> 00:08:30,410
είναι λίγο καιρό, έτσι εκεί στην κορυφή της οθόνης θα δείτε Valgrind-v.

147
00:08:30,410 --> 00:08:35,350
"-V" σχεδόν καθολικά σημαίνει φλύαρη όταν χρησιμοποιείτε προγράμματα σε υπολογιστή με Linux.

148
00:08:35,350 --> 00:08:38,770
Έτσι, αυτό σημαίνει φτύσει περισσότερα δεδομένα από ό, τι ίσως από προεπιλογή.

149
00:08:38,770 --> 00:08:45,510
"- Έλεγχος διαρροών = πλήρης." Αυτό που λέει ακριβώς επιταγή για όλες τις πιθανές διαρροές μνήμης,

150
00:08:45,510 --> 00:08:49,430
τα λάθη που μπορεί να έγιναν. Αυτό, επίσης, είναι ένα κοινό παράδειγμα με προγράμματα Linux.

151
00:08:49,430 --> 00:08:52,710
Σε γενικές γραμμές, αν έχετε ένα όρισμα γραμμής εντολών αυτό είναι ένα «διακόπτη»,

152
00:08:52,710 --> 00:08:55,830
που υποτίθεται για να αλλάξει τη συμπεριφορά του προγράμματος, και αυτό είναι ένα μόνο γράμμα,

153
00:08:55,830 --> 00:09:00,310
είναι-κατά, αλλά αν αυτό είναι ενεργοποιημένο, μόνο από το σχεδιασμό του προγραμματιστή,

154
00:09:00,310 --> 00:09:05,150
είναι μια λέξη ή πλήρη σειρά των λέξεων, το επιχείρημα της γραμμής εντολών ξεκινά με -.

155
00:09:05,150 --> 00:09:08,190
Αυτά είναι μόνο τα ανθρώπινα, αλλά θα τους δούμε όλο και περισσότερο.

156
00:09:08,190 --> 00:09:12,410
Και έπειτα, τελικά, "a.out" είναι η αυθαίρετη όνομα για το πρόγραμμα σε αυτό το συγκεκριμένο παράδειγμα.

157
00:09:12,410 --> 00:09:14,640
Και εδώ είναι μερικά εκπρόσωπος εξόδου.

158
00:09:14,640 --> 00:09:22,890
>> Πριν κοιτάξουμε τι μπορεί να σημαίνει αυτό, επιτρέψτε μου να πάει πάνω σε ένα απόσπασμα του κώδικα εδώ.

159
00:09:22,890 --> 00:09:26,390
Και επιτρέψτε μου να μετακινήσετε αυτό το έξω από το δρόμο, σύντομα,

160
00:09:26,390 --> 00:09:32,120
και ας ρίξουμε μια ματιά στο memory.c, το οποίο είναι αυτό το σύντομο παράδειγμα εδώ.

161
00:09:32,120 --> 00:09:36,290
Έτσι, σε αυτό το πρόγραμμα, επιτρέψτε μου να μεγεθύνετε τις λειτουργίες και τις ερωτήσεις.

162
00:09:36,290 --> 00:09:39,430
Έχουμε μια κύρια λειτουργία που απαιτεί μια λειτουργία, στ,

163
00:09:39,430 --> 00:09:45,590
και στη συνέχεια, τι στ προχωρήσει να κάνει, σε ελαφρώς τεχνικό αγγλικά;

164
00:09:45,590 --> 00:09:49,760
Τι σημαίνει στ προχωρήσει να κάνει;

165
00:09:49,760 --> 00:09:53,680
Πόσο περίπου θα αρχίσω με τη γραμμή 20, και τη θέση του αστεριού δεν έχει σημασία,

166
00:09:53,680 --> 00:09:56,720
αλλά εγώ θα πρέπει ακριβώς να είναι συνεπής εδώ με την τελευταία διάλεξη.

167
00:09:56,720 --> 00:09:59,910
Ποια είναι η γραμμή 20 κάνει για μας; Από την αριστερή πλευρά. Θα το σπάσει περαιτέρω.

168
00:09:59,910 --> 00:10:02,410
Int * x: τι κάνει ότι κάνει;

169
00:10:02,410 --> 00:10:04,940
Εντάξει. Είναι δηλώνοντας ένα δείκτη, και τώρα ας είναι ακόμα πιο τεχνικό.

170
00:10:04,940 --> 00:10:10,230
Τι σημαίνει, πολύ συγκεκριμένα, να δηλώσει ένα δείκτη; Κάποιος άλλος;

171
00:10:10,230 --> 00:10:15,050
Ναι; [Απάντηση Φοιτητής, ακατάληπτο] Πάρα πολύ.

172
00:10:15,050 --> 00:10:17,060
Έτσι, μπορείτε να διαβάζετε στη δεξιά πλευρά του συμβόλου του ίσον.

173
00:10:17,060 --> 00:10:20,290
Ας επικεντρωθούν στα αριστερά, ακριβώς στο int * x.

174
00:10:20,290 --> 00:10:24,700
Αυτό σημαίνει "δηλώνει" ένα δείκτη, αλλά τώρα ας βουτήξει σε πιο βαθιά σε αυτόν τον ορισμό.

175
00:10:24,700 --> 00:10:28,330
Τι σημαίνει ότι συγκεκριμένα, τεχνικά σημαίνει; Ναι;

176
00:10:28,330 --> 00:10:31,940
[Απάντηση Φοιτητής, ακατάληπτο]

177
00:10:31,940 --> 00:10:35,090
Εντάξει. Είναι ετοιμάζεται να αποθηκεύσετε μία διεύθυνση στη μνήμη.

178
00:10:35,090 --> 00:10:40,680
Καλή. Και ας πάρουμε ένα βήμα παραπέρα? Αυτό είναι που κηρύσσει μια μεταβλητή, x, που είναι 32 bits.

179
00:10:40,680 --> 00:10:44,440
Και ξέρω ότι είναι 32 bit, επειδή -

180
00:10:44,440 --> 00:10:47,390
Δεν είναι επειδή είναι ένα int, επειδή είναι ένας δείκτης σε αυτή την περίπτωση.

181
00:10:47,390 --> 00:10:49,650
Σύμπτωση ότι είναι ένα και το αυτό με έναν int,

182
00:10:49,650 --> 00:10:51,970
αλλά το γεγονός ότι υπάρχει το αστέρι σημαίνει ότι υπάρχει αυτό είναι ένας δείκτης

183
00:10:51,970 --> 00:10:57,300
και στη συσκευή, όπως με πολλούς υπολογιστές, αλλά όχι όλες, δείκτες είναι 32 bits.

184
00:10:57,300 --> 00:11:01,850
Στις πιο σύγχρονο εξοπλισμό, όπως τις τελευταίες υπολογιστές Mac, οι τελευταίες υπολογιστές, μπορεί να έχετε 64-bit δείκτες,

185
00:11:01,850 --> 00:11:04,160
αλλά στη συσκευή, αυτά τα πράγματα είναι 32 bits.

186
00:11:04,160 --> 00:11:08,380
Γι 'αυτό και θα τυποποιηθούν σε αυτό. Πιο συγκεκριμένα, η ιστορία συνεχίζεται ως εξής:

187
00:11:08,380 --> 00:11:10,820
Εμείς "δηλώνουν" ένα δείκτη? Τι σημαίνει αυτό;

188
00:11:10,820 --> 00:11:12,810
Έχουμε προετοιμάσει για να αποθηκεύσετε μια διεύθυνση μνήμης.

189
00:11:12,810 --> 00:11:15,530
Τι σημαίνει αυτό;

190
00:11:15,530 --> 00:11:19,810
Έχουμε δημιουργήσει μια μεταβλητή που ονομάζεται x που καταλαμβάνει 32 bits

191
00:11:19,810 --> 00:11:23,810
που θα αποθηκεύσει σύντομα τη διεύθυνση του ακεραίου.

192
00:11:23,810 --> 00:11:26,470
Και αυτό είναι πιθανώς περίπου τόσο ακριβής όσο μπορούμε να πάρουμε.

193
00:11:26,470 --> 00:11:31,810
Είναι ωραία κινείται προς τα εμπρός για να απλοποιήσει τον κόσμο και να πω κηρύξει δείκτη που ονομάζεται x.

194
00:11:31,810 --> 00:11:35,380
Δηλώστε ένα δείκτη, αλλά συνειδητοποιούν και να κατανοήσουν τι πραγματικά συμβαίνει

195
00:11:35,380 --> 00:11:38,490
ακόμη και σε εκείνες τις λίγες μόλις χαρακτήρες.

196
00:11:38,490 --> 00:11:42,040
>> Τώρα, αυτό είναι σχεδόν λίγο πιο εύκολη, ακόμα κι αν είναι μεγαλύτερη έκφραση.

197
00:11:42,040 --> 00:11:48,160
Έτσι, αυτό που κάνει αυτό, που είναι τώρα τόνισε: "malloc (10 * sizeof (int))?" Ναι;

198
00:11:48,160 --> 00:11:52,350
[Απάντηση Φοιτητής, ακατάληπτο]

199
00:11:52,350 --> 00:11:58,250
Καλή. Και θα το πάρω εκεί. Είναι ένα κομμάτι κατανομή της μνήμης για δέκα ακέραιοι.

200
00:11:58,250 --> 00:12:02,190
Και τώρα ας βουτήξει σε λίγο βαθύτερα? Αυτό είναι ένα κομμάτι κατανομή της μνήμης για δέκα ακέραιοι.

201
00:12:02,190 --> 00:12:05,390
Τι είναι η malloc στη συνέχεια επιστρέφει;

202
00:12:05,390 --> 00:12:10,390
Η διεύθυνση του εν λόγω κομμάτι, ή, πιο συγκεκριμένα, η διεύθυνση του πρώτου byte του εν λόγω κομμάτι.

203
00:12:10,390 --> 00:12:14,080
Πώς λοιπόν είμαι, ο προγραμματιστής, για να ξέρετε πού αυτό το κομμάτι της μνήμης άκρα;

204
00:12:14,080 --> 00:12:18,340
Ξέρω ότι είναι συνεχόμενες. Malloc, εξ ορισμού, θα σας δώσει ένα συνεχόμενο τμήμα της μνήμης.

205
00:12:18,340 --> 00:12:21,240
Δεν υπάρχουν κενά σε αυτό. Έχετε πρόσβαση σε κάθε byte σε αυτό το κομμάτι,

206
00:12:21,240 --> 00:12:26,760
πλάτη με πλάτη με πλάτη, αλλά πώς μπορώ να ξέρω όπου το τέλος του τρέχοντος κομμάτι της μνήμης είναι;

207
00:12:26,760 --> 00:12:28,850
Όταν χρησιμοποιείτε malloc; [Απάντηση Φοιτητής, ακατάληπτο] Καλή.

208
00:12:28,850 --> 00:12:30,670
Δεν κάνουμε. Θα πρέπει να θυμόμαστε.

209
00:12:30,670 --> 00:12:35,960
Θα πρέπει να θυμάστε ότι θα χρησιμοποιηθεί η τιμή 10, και δεν χρειάζεται καν να φαίνεται ότι έχουν κάνει εδώ.

210
00:12:35,960 --> 00:12:41,000
Αλλά η ευθύνη είναι αποκλειστικά για μένα. Strlen, που έχουμε γίνει λίγο εξαρτάται από για έγχορδα,

211
00:12:41,000 --> 00:12:45,860
λειτουργεί μόνο εξαιτίας αυτής της σύμβασης που έχει \ 0

212
00:12:45,860 --> 00:12:48,840
ή αυτή η ειδική nul χαρακτήρα, NUL, στο τέλος του string.

213
00:12:48,840 --> 00:12:51,740
Αυτό δεν ισχύει μόνο για την αυθαίρετη κομμάτια της μνήμης.

214
00:12:51,740 --> 00:12:58,590
Είναι στο χέρι σας. Έτσι, γραμμή 20, λοιπόν, διαθέτει ένα μεγάλο κομμάτι της μνήμης

215
00:12:58,590 --> 00:13:02,590
που μπορεί να αποθηκεύσει δέκα ακέραιοι, και αποθηκεύει τη διεύθυνση του πρώτου byte

216
00:13:02,590 --> 00:13:05,610
του εν λόγω κομμάτι της μνήμης του που ονομάζεται μεταβλητή x.

217
00:13:05,610 --> 00:13:11,140
Ergo, η οποία είναι ένας δείκτης. Έτσι, γραμμή 21, δυστυχώς, ήταν ένα λάθος.

218
00:13:11,140 --> 00:13:16,110
Αλλά, πρώτα τι είναι αυτό που κάνει; Είναι λέγοντας κατάστημα στη θέση 10, 0 τιμαριθμική αναπροσαρμογή,

219
00:13:16,110 --> 00:13:19,480
από το κομμάτι της μνήμης που ονομάζεται x η τιμή 0.

220
00:13:19,480 --> 00:13:21,510
>> Έτσι παρατηρούμε μια-δυο πράγματα συμβαίνουν.

221
00:13:21,510 --> 00:13:25,420
Ακόμα κι αν το x είναι ένας δείκτης, ανάκληση από μερικές εβδομάδες πριν

222
00:13:25,420 --> 00:13:29,440
ότι μπορείτε ακόμα να χρησιμοποιήσετε τον πίνακα στυλ σημειογραφία βραχίονα πλατεία.

223
00:13:29,440 --> 00:13:36,180
Επειδή αυτό είναι πραγματικά σύντομη-χέρι συμβολισμό για την πιο αινιγματικά εμφάνιση αριθμητική δείκτη.

224
00:13:36,180 --> 00:13:40,320
όπου θα κάναμε κάτι σαν αυτό: Πάρτε το x διεύθυνση, κινούνται πάνω από 10 σημεία,

225
00:13:40,320 --> 00:13:44,550
τότε πάμε εκεί σε ό, τι διεύθυνση αποθηκεύεται σε αυτή τη θέση.

226
00:13:44,550 --> 00:13:48,090
Αλλά ειλικρινά, αυτό είναι ακριβώς φρικτό να διαβάσετε και να πάρει άνετα με.

227
00:13:48,090 --> 00:13:52,900
Έτσι, ο κόσμος χρησιμοποιεί συνήθως τις αγκύλες, ακριβώς επειδή είναι τόσο πολύ πιο φιλικό προς τον άνθρωπο για να διαβάσετε.

228
00:13:52,900 --> 00:13:55,140
Αλλά αυτό είναι ό, τι πραγματικά συμβαίνει κάτω από την κουκούλα?

229
00:13:55,140 --> 00:13:58,190
χ είναι μια διεύθυνση, όχι μια συστοιχία, per se.

230
00:13:58,190 --> 00:14:02,410
Έτσι, αυτό αποθηκεύει 0 στο σημείο 10 στο x.

231
00:14:02,410 --> 00:14:06,120
Γιατί είναι αυτό το κακό; Ναι;

232
00:14:06,120 --> 00:14:17,370
[Απάντηση Φοιτητής, ακατάληπτο] Ακριβώς.

233
00:14:17,370 --> 00:14:21,100
Θα διατεθεί μόνο δέκα ints, αλλά μετράμε από το 0 κατά τον προγραμματισμό σε C,

234
00:14:21,100 --> 00:14:25,690
έτσι ώστε να έχετε πρόσβαση σε 0 1 2 3 4 5 6 7 8 9, αλλά όχι 10.

235
00:14:25,690 --> 00:14:30,270
Έτσι, είτε το πρόγραμμα πρόκειται να seg βλάβη ή δεν είναι.

236
00:14:30,270 --> 00:14:32,900
Αλλά εμείς δεν γνωρίζουμε πραγματικά? Αυτό είναι ένα είδος nondeterministic συμπεριφορά.

237
00:14:32,900 --> 00:14:35,600
Είναι πραγματικά εξαρτάται από το αν είμαστε τυχεροί.

238
00:14:35,600 --> 00:14:40,650
Αν αποδειχθεί ότι το λειτουργικό σύστημα δεν πειράζει αν μπορώ να χρησιμοποιήσω αυτό το επιπλέον byte,

239
00:14:40,650 --> 00:14:43,360
ακόμη και αν δεν έχει δοθεί σε μένα, το πρόγραμμά μου μπορεί να μην συντριβή.

240
00:14:43,360 --> 00:14:46,780
Είναι ωμό, είναι λάθη, αλλά δεν μπορείτε να δείτε αυτό το σύμπτωμα,

241
00:14:46,780 --> 00:14:48,960
ή μπορείτε να το δείτε μόνο μία φορά σε μια στιγμή.

242
00:14:48,960 --> 00:14:51,230
Αλλά η πραγματικότητα είναι ότι το σφάλμα είναι, στην πραγματικότητα, εκεί.

243
00:14:51,230 --> 00:14:54,320
Και είναι πραγματικά προβληματική εάν έχετε γράψει ένα πρόγραμμα που θέλετε να είναι σωστή,

244
00:14:54,320 --> 00:14:58,840
ότι έχετε πωληθεί το πρόγραμμα στο οποίο οι άνθρωποι χρησιμοποιούν ότι κάθε φορά σε μια στιγμή κολλάει

245
00:14:58,840 --> 00:15:02,450
επειδή, φυσικά, αυτό δεν είναι καλό. Στην πραγματικότητα, εάν έχετε ένα τηλέφωνο Android ή το iPhone

246
00:15:02,450 --> 00:15:05,550
και να κατεβάσετε εφαρμογές αυτές τις μέρες, αν είχατε ποτέ μια εφαρμογή μόλις σταματήσουν το κάπνισμα,

247
00:15:05,550 --> 00:15:10,040
ξαφνικά εξαφανίζεται, αυτό είναι σχεδόν πάντα το αποτέλεσμα κάποιας μνήμης που σχετίζονται με το θέμα,

248
00:15:10,040 --> 00:15:12,830
σύμφωνα με την οποία ο προγραμματιστής σκάτωσε και αναχθούν ένα δείκτη

249
00:15:12,830 --> 00:15:18,670
ότι αυτός ή αυτή δεν πρέπει να έχει, και το αποτέλεσμα του iOS ή Android είναι να σκοτώσει μόνο το πρόγραμμα συνολικά

250
00:15:18,670 --> 00:15:23,080
παρά τον κίνδυνο απροσδιόριστη συμπεριφορά ή κάποιου είδους συμβιβασμό της ασφάλειας.

251
00:15:23,080 --> 00:15:25,950
>> Υπάρχει ένα άλλο σφάλμα σε αυτό το πρόγραμμα, εκτός από αυτό.

252
00:15:25,950 --> 00:15:30,180
Τι άλλο έχω μαντάρα σε αυτό το πρόγραμμα;

253
00:15:30,180 --> 00:15:32,740
Δεν έχω ασκήσει ό, τι έχω κηρύξει. Ναι;

254
00:15:32,740 --> 00:15:34,760
[Απάντηση Φοιτητής, ακατάληπτο] Καλή.

255
00:15:34,760 --> 00:15:36,880
Δεν έχω απελευθερωθεί η μνήμη. Έτσι, ο κανόνας του αντίχειρα σήμερα

256
00:15:36,880 --> 00:15:43,150
πρέπει να είναι ανά πάσα στιγμή να καλέσετε malloc, θα πρέπει να καλέσετε χωρίς χρέωση, όταν τελειώσετε με αυτή τη μνήμη.

257
00:15:43,150 --> 00:15:45,610
Τώρα, όταν θα θέλω να απελευθερώσετε αυτή τη μνήμη;

258
00:15:45,610 --> 00:15:49,780
Πιθανώς, παραδοχή αυτή η πρώτη γραμμή ήταν σωστή, θα ήθελα να το κάνω εδώ.

259
00:15:49,780 --> 00:15:55,710
Επειδή δεν μπορούσα, για παράδειγμα, να το κάνετε εδώ κάτω. Γιατί;

260
00:15:55,710 --> 00:15:57,860
Ακριβώς έξω από το πεδίο εφαρμογής. Έτσι ακόμα κι αν μιλάμε για δείκτες,

261
00:15:57,860 --> 00:16:04,830
αυτή την εβδομάδα είναι 2 ή 3 θέμα, όπου x είναι μόνο στο πεδίο εφαρμογής μέσα από τα άγκιστρα, όπου ανακηρύχθηκε.

262
00:16:04,830 --> 00:16:11,000
Έτσι, μπορείτε σίγουρα δεν μπορεί να το ελευθερώσουν. Μόνο ευκαιρία μου για να ελευθερώσετε είναι περίπου μετά την γραμμή 21.

263
00:16:11,000 --> 00:16:15,170
Αυτό είναι ένα αρκετά απλό πρόγραμμα? Ήταν αρκετά εύκολο μόλις το είδος του τυλιγμένο το μυαλό σας

264
00:16:15,170 --> 00:16:17,870
γύρω από αυτό το πρόγραμμα κάνει, όπου τα λάθη ήταν.

265
00:16:17,870 --> 00:16:20,500
Και ακόμα κι αν δεν το δείτε στο πρώτο, ελπίζω να είναι λίγο προφανές τώρα

266
00:16:20,500 --> 00:16:23,870
ότι αυτά τα λάθη αρκετά λυθεί εύκολα και πολύ εύκολο να γίνει.

267
00:16:23,870 --> 00:16:28,720
Αλλά όταν ένα πρόγραμμα είναι περισσότερο από 12 γραμμές καιρό, είναι 50 γραμμές μήκους 100 γραμμές καιρό,

268
00:16:28,720 --> 00:16:31,150
περπάτημα μέσω της γραμμής με τον κωδικό σας γραμμή, σκέφτεται λογικά μέσα από αυτό,

269
00:16:31,150 --> 00:16:35,110
είναι δυνατόν, αλλά δεν είναι ιδιαίτερα διασκεδαστικό να το κάνουμε, συνεχώς ψάχνει για σφάλματα,

270
00:16:35,110 --> 00:16:38,340
και είναι επίσης δύσκολο να γίνει, και γι 'αυτό ένα εργαλείο όπως το Valgrind υπάρχει.

271
00:16:38,340 --> 00:16:40,900
Επιτρέψτε μου να προχωρήσει και να το κάνετε αυτό: επιτρέψτε μου να ανοίξει παράθυρο τερματικού μου,

272
00:16:40,900 --> 00:16:45,400
και επιτρέψτε μου να μην τρέξει μόνο τη μνήμη, επειδή η μνήμη φαίνεται να είναι μια χαρά.

273
00:16:45,400 --> 00:16:49,180
Είμαι τυχερός να πάρει. Πηγαίνοντας στο εν λόγω επιπλέον byte στο τέλος της συστοιχίας

274
00:16:49,180 --> 00:16:51,060
δεν φαίνεται να είναι πολύ προβληματική.

275
00:16:51,060 --> 00:16:56,370
Αλλά επιτρέψτε μου, παρ 'όλα αυτά, κάνει έναν έλεγχο λογική, η οποία απλά σημαίνει να ελέγξετε

276
00:16:56,370 --> 00:16:58,320
αν αυτό δεν είναι πραγματικά σωστή.

277
00:16:58,320 --> 00:17:04,690
>> Ας κάνουμε valgrind-v - διαρροή-check = πλήρης,

278
00:17:04,690 --> 00:17:07,520
και στη συνέχεια το όνομα του προγράμματος σε αυτή την περίπτωση δεν είναι η μνήμη, a.out.

279
00:17:07,520 --> 00:17:10,760
Επιτρέψτε μου λοιπόν να προχωρήσει και να το κάνουμε αυτό. Πατήστε Enter.

280
00:17:10,760 --> 00:17:14,109
Θεέ μου. Αυτή είναι η έξοδος του, και αυτό είναι αυτό που προαναφέρθηκε.

281
00:17:14,109 --> 00:17:17,550
Αλλά, αν μπορείτε να μάθετε να διαβάσετε όλες τις ανοησίες εδώ,

282
00:17:17,550 --> 00:17:20,760
τα περισσότερα από αυτά είναι μόνο διαγνωστική έξοδος που δεν είναι τόσο ενδιαφέρουσα.

283
00:17:20,760 --> 00:17:24,829
Τι μάτι σας θέλει πραγματικά να είναι ψάχνει για οποιαδήποτε αναφορά σφάλματος ή άκυρο.

284
00:17:24,829 --> 00:17:26,800
Λέξεις που υποδηλώνουν προβλήματα.

285
00:17:26,800 --> 00:17:29,340
Και πράγματι, ας δούμε τι συμβαίνει λάθος εδώ κάτω.

286
00:17:29,340 --> 00:17:35,230
Έχω μια περίληψη κάποιου είδους, "σε χρήση στην έξοδο: 40. Bytes σε 1 μπλοκ"

287
00:17:35,230 --> 00:17:38,750
Δεν είμαι πραγματικά βέβαιος τι είναι ένα μπλοκ ακόμα, αλλά 40 bytes

288
00:17:38,750 --> 00:17:41,260
πραγματικά αισθάνεται σαν να μπορούσα να καταλάβω ότι όταν έρχεται από.

289
00:17:41,260 --> 00:17:45,030
40 bytes. Γιατί είναι 40 bytes σε χρήση στην έξοδο;

290
00:17:45,030 --> 00:17:48,780
Και πιο συγκεκριμένα, αν μετακινηθείτε προς τα κάτω εδώ,

291
00:17:48,780 --> 00:17:54,520
γιατί έχω χάσει σίγουρα 40 bytes; Ναι;

292
00:17:54,520 --> 00:17:59,520
[Απάντηση Φοιτητής, ακατάληπτο] Perfect. Ναι, ακριβώς.

293
00:17:59,520 --> 00:18:03,540
Υπήρχαν δέκα ακέραιοι, και κάθε ένα από αυτά είναι το μέγεθος των 4, ή 32 bits,

294
00:18:03,540 --> 00:18:08,300
έτσι έχω χάσει 40 bytes ακριβώς επειδή, όπως προτείνεται, δεν έχω που ονομάζεται δωρεάν.

295
00:18:08,300 --> 00:18:13,460
Αυτό είναι ένα bug, και τώρα ας δούμε τα κάτω λίγο περισσότερο και να δούμε δίπλα σε αυτό,

296
00:18:13,460 --> 00:18:16,900
"Άκυρο γράφουν μεγέθους 4." Τώρα, τι είναι αυτό;

297
00:18:16,900 --> 00:18:21,150
Αυτή η διεύθυνση εκφράζεται τι συμβολισμό βάσης, προφανώς;

298
00:18:21,150 --> 00:18:23,640
Αυτό είναι δεκαεξαδικό, και κάθε φορά που θα δείτε μια σειρά αρχίζοντας με 0x,

299
00:18:23,640 --> 00:18:29,410
αυτό σημαίνει δεκαεξαδικό, το οποίο κάναμε τον τρόπο πίσω το, νομίζω, το τμήμα 0 του PSET ερωτήσεων,

300
00:18:29,410 --> 00:18:34,090
η οποία ήταν μόνο για να κάνει μια άσκηση προθέρμανσης, τη μετατροπή δεκαδικό σε δεκαεξαδικό σε δυαδικό και ούτω καθεξής.

301
00:18:34,090 --> 00:18:39,220
Δεκαεξαδικό, μόνο από την ανθρώπινη συνθήκη, είναι συνήθως χρησιμοποιούνται για να αντιπροσωπεύσουν δείκτες

302
00:18:39,220 --> 00:18:41,570
ή, γενικότερα, διευθύνσεις. Είναι απλά μια σύμβαση,

303
00:18:41,570 --> 00:18:45,340
επειδή είναι λίγο πιο εύκολο να διαβάσει, είναι λίγο πιο συμπαγής από κάτι σαν δεκαδικό,

304
00:18:45,340 --> 00:18:47,720
και δυαδική είναι άχρηστο για τους περισσότερους ανθρώπους να χρησιμοποιούν.

305
00:18:47,720 --> 00:18:50,840
Και τώρα τι σημαίνει αυτό; Λοιπόν, φαίνεται σαν να υπάρχει μια έγκυρη εγγραφή

306
00:18:50,840 --> 00:18:54,480
μεγέθους 4 στη γραμμή 21 του memory.c.

307
00:18:54,480 --> 00:18:59,180
Ας πάμε πίσω στη γραμμή 21, και μάλιστα, εδώ είναι ότι άκυρη εγγραφή.

308
00:18:59,180 --> 00:19:02,640
Έτσι Valgrind δεν πρόκειται να κρατήσει εντελώς το χέρι μου και να μου πείτε ποια είναι η λύση είναι,

309
00:19:02,640 --> 00:19:05,520
αλλά ανιχνεύει ότι κάνω μια έγκυρη εγγραφή.

310
00:19:05,520 --> 00:19:08,800
Είμαι αγγίζοντας 4 byte ότι δεν θα πρέπει να είναι, και προφανώς αυτό είναι επειδή,

311
00:19:08,800 --> 00:19:13,960
όπως επεσήμανε, κάνω [10] αντί του [9] μέγιστη

312
00:19:13,960 --> 00:19:16,660
ή [0] ή κάτι στο μεταξύ.

313
00:19:16,660 --> 00:19:19,690
Με Valgrind, συνειδητοποιούν κάθε φορά που γράφεις τώρα ένα πρόγραμμα

314
00:19:19,690 --> 00:19:24,190
που χρησιμοποιεί δείκτες και χρησιμοποιεί μνήμη, και πιο συγκεκριμένα malloc,

315
00:19:24,190 --> 00:19:27,080
σίγουρα να πάρει τη συνήθεια να τρέχει αυτή τη μακρά

316
00:19:27,080 --> 00:19:30,890
αλλά πολύ εύκολα να αντιγραφεί και επικολληθεί εντολή του Valgrind

317
00:19:30,890 --> 00:19:32,650
για να δούμε αν υπάρχει κάποια λάθη εκεί.

318
00:19:32,650 --> 00:19:34,820
Και αυτό θα είναι συντριπτική κάθε φορά που θα δείτε την έξοδο,

319
00:19:34,820 --> 00:19:39,430
αλλά απλώς να αναλύσει μέσα από οπτικά το σύνολο της παραγωγής και να δούμε αν δείτε αναφέρει σφαλμάτων

320
00:19:39,430 --> 00:19:43,190
ή προειδοποιήσεις ή άκυρο ή χαθεί.

321
00:19:43,190 --> 00:19:46,200
Όποια από τις λέξεις που ακούγονται σαν να σκάτωσε κάπου.

322
00:19:46,200 --> 00:19:48,580
Έτσι αντιλαμβάνονται ότι είναι ένα νέο εργαλείο στην εργαλειοθήκη σας.

323
00:19:48,580 --> 00:19:51,270
>> Τώρα, τη Δευτέρα, είχαμε ένα σωρό λαοί έρχονται εδώ

324
00:19:51,270 --> 00:19:53,150
και αντιπροσωπεύουν την έννοια του συνδεδεμένη λίστα.

325
00:19:53,150 --> 00:20:00,970
Και εμείς εισήγαγε την συνδεδεμένη λίστα ως λύση σε ποιο το πρόβλημα;

326
00:20:00,970 --> 00:20:04,590
Ναι; [Απάντηση Φοιτητής, ακατάληπτο] Καλή.

327
00:20:04,590 --> 00:20:06,530
Οι πίνακες δεν μπορούν να έχουν μνήμη προστεθούν σε αυτά.

328
00:20:06,530 --> 00:20:09,440
Αν ορίσουμε έναν πίνακα μεγέθους 10, αυτό είναι το μόνο που έχετε να πάρετε.

329
00:20:09,440 --> 00:20:13,690
Μπορείτε να καλέσετε μια συνάρτηση όπως realloc αν ονομάζεται αρχικά malloc,

330
00:20:13,690 --> 00:20:17,580
και ότι μπορεί να προσπαθήσει να αυξηθεί το συστοιχία αν υπάρχει χώρος προς το τέλος του

331
00:20:17,580 --> 00:20:21,610
ότι κανένας άλλος δεν χρησιμοποιεί, και αν δεν υπάρχει, απλά θα βρείτε ένα μεγαλύτερο κομμάτι κάπου αλλού.

332
00:20:21,610 --> 00:20:25,040
Αλλά τότε θα αντιγράψει όλα αυτά τα bytes στο νέο πίνακα.

333
00:20:25,040 --> 00:20:28,310
Αυτό ακούγεται σαν μια πολύ σωστή λύση.

334
00:20:28,310 --> 00:20:34,790
Γιατί είναι αυτή η ελκυστική;

335
00:20:34,790 --> 00:20:36,940
Θέλω να πω ότι δουλεύει, οι άνθρωποι έχουν λύσει αυτό το πρόβλημα.

336
00:20:36,940 --> 00:20:40,710
Γιατί πρέπει να το επιλύσουν τη Δευτέρα με συνδεδεμένες λίστες; Ναι;

337
00:20:40,710 --> 00:20:44,060
[Απάντηση Φοιτητής, ακατάληπτο] Θα μπορούσε να πάρει πολύ χρόνο.

338
00:20:44,060 --> 00:20:49,260
Στην πραγματικότητα, κάθε φορά που καλείτε malloc ή realloc ή calloc, το οποίο είναι ένα ακόμα,

339
00:20:49,260 --> 00:20:52,470
κάθε φορά που το πρόγραμμα, μιλάμε για το λειτουργικό σύστημα,

340
00:20:52,470 --> 00:20:54,310
έχετε την τάση να επιβραδύνει το πρόγραμμα προς τα κάτω.

341
00:20:54,310 --> 00:20:57,470
Και αν κάνετε αυτά τα είδη των πραγμάτων σε βρόχους, είστε πραγματικά επιβράδυνση πράγματα κάτω.

342
00:20:57,470 --> 00:21:00,740
Δεν πρόκειται να παρατηρήσετε αυτό για την απλούστερη των "hello world" προγράμματα τύπου,

343
00:21:00,740 --> 00:21:04,300
αλλά σε πολύ μεγαλύτερα προγράμματα, ζητώντας από το λειτουργικό σύστημα ξανά και ξανά για τη μνήμη

344
00:21:04,300 --> 00:21:07,520
ή δίνοντας ξανά και ξανά δεν τείνει να είναι ένα καλό πράγμα.

345
00:21:07,520 --> 00:21:11,210
Πλέον, είναι ακριβώς το είδος της πνευματικά - είναι ένα πλήρες χάσιμο χρόνου.

346
00:21:11,210 --> 00:21:16,490
Γιατί να διαθέσουν όλο και περισσότερη μνήμη, ο κίνδυνος αντιγραφή τα πάντα στη νέα σειρά,

347
00:21:16,490 --> 00:21:21,980
εάν έχετε μια εναλλακτική λύση που σας επιτρέπει να διαθέτουν μόνο τόσο πολύ μνήμη, όπως μπορείτε πραγματικά ανάγκη;

348
00:21:21,980 --> 00:21:24,130
Έτσι, υπάρχει συν και τα πλην εδώ.

349
00:21:24,130 --> 00:21:26,730
Ένα από τα συν είναι ότι τώρα έχουμε δυναμισμό.

350
00:21:26,730 --> 00:21:29,100
Δεν έχει σημασία, όπου τα κομμάτια της μνήμης είναι ότι είναι δωρεάν,

351
00:21:29,100 --> 00:21:32,070
Μπορώ απλώς να ταξινομήσετε τη δημιουργία αυτών των ψίχουλα ψωμιού μέσω δείκτες

352
00:21:32,070 --> 00:21:34,470
να πλέκετε όλη συνδεδεμένη λίστα μου μαζί.

353
00:21:34,470 --> 00:21:36,470
Αλλά μπορώ να πληρώσω τουλάχιστον μία τιμή.

354
00:21:36,470 --> 00:21:40,060
>> Τι πρέπει να εγκαταλείψουν στην απόκτηση συνδεδεμένες λίστες;

355
00:21:40,060 --> 00:21:42,470
Ναι; [Απάντηση Φοιτητής, ακατάληπτο] Καλή.

356
00:21:42,470 --> 00:21:45,650
Χρειάζεται περισσότερη μνήμη. Τώρα χρειάζονται χώρο για αυτούς τους δείκτες,

357
00:21:45,650 --> 00:21:47,900
και στην περίπτωση αυτού του σούπερ συνδέονται απλή λίστα

358
00:21:47,900 --> 00:21:51,410
Αυτός είναι ο μόνος που προσπαθεί να αποθηκεύουν ακέραιους αριθμούς, που είναι 4 bytes, συνεχίζουμε να λέμε

359
00:21:51,410 --> 00:21:54,240
καλά, ένας δείκτης είναι 4 bytes, οπότε τώρα έχω κυριολεκτικά διπλασιαστεί

360
00:21:54,240 --> 00:21:57,290
η ποσότητα της μνήμης που χρειάζεται μόνο για να αποθηκεύσετε αυτή τη λίστα.

361
00:21:57,290 --> 00:21:59,680
Αλλά και πάλι, αυτό είναι μια συνεχής συμβιβασμός στην επιστήμη των υπολογιστών

362
00:21:59,680 --> 00:22:03,440
μεταξύ του χρόνου και του χώρου και την ανάπτυξη, την προσπάθεια και άλλους πόρους.

363
00:22:03,440 --> 00:22:06,630
Τι είναι ένα άλλο μειονέκτημα του χρησιμοποιώντας μια συνδεδεμένη λίστα; Ναι;

364
00:22:06,630 --> 00:22:10,150
[Απάντηση Φοιτητής, ακατάληπτο]

365
00:22:10,150 --> 00:22:12,600
Καλή. Δεν είναι τόσο εύκολη η πρόσβαση. Μπορούμε πλέον να μόχλευσης

366
00:22:12,600 --> 00:22:15,530
εβδομάδα 0 αρχές, όπως διαίρει και βασίλευε.

367
00:22:15,530 --> 00:22:18,220
Και πιο συγκεκριμένα, δυαδική αναζήτηση. Διότι ακόμα κι αν εμείς οι άνθρωποι

368
00:22:18,220 --> 00:22:20,400
μπορεί να δει περίπου όπου η μέση του καταλόγου αυτού είναι,

369
00:22:20,400 --> 00:22:25,840
ο υπολογιστής ξέρει μόνο ότι αυτή η συνδεδεμένη λίστα ξεκινά στη διεύθυνση που ονομάζεται πρώτη.

370
00:22:25,840 --> 00:22:28,250
Και αυτό είναι 0x123 ή κάτι τέτοιο.

371
00:22:28,250 --> 00:22:30,990
Και ο μόνος τρόπος για το πρόγραμμα μπορείτε να βρείτε το μεσαίο στοιχείο

372
00:22:30,990 --> 00:22:33,350
είναι να ψάξει πραγματικά όλη τη λίστα.

373
00:22:33,350 --> 00:22:35,500
Και ακόμα και τότε, δεν έχει κυριολεκτικά να ψάξετε ολόκληρη τη λίστα, επειδή

374
00:22:35,500 --> 00:22:38,950
ακόμα και τη στιγμή που θα φτάσει το μεσαίο στοιχείο, ακολουθώντας τους δείκτες,

375
00:22:38,950 --> 00:22:42,380
σας, το πρόγραμμα, δεν έχουν ιδέα πόσο καιρό αυτή η λίστα είναι, δυνητικά,

376
00:22:42,380 --> 00:22:45,250
μέχρι να χτυπήσει το τέλος του, και πώς ξέρετε προγραμματισμού

377
00:22:45,250 --> 00:22:48,600
ότι είστε στο τέλος μιας συνδεδεμένη λίστα;

378
00:22:48,600 --> 00:22:51,120
Υπάρχει ένα ειδικό δείκτη NULL, οπότε και πάλι, μια σύμβαση.

379
00:22:51,120 --> 00:22:53,870
Αντί να χρησιμοποιήσετε αυτό το δείκτη, εμείς σίγουρα δεν θέλουμε να είναι κάποια αξία σκουπίδια

380
00:22:53,870 --> 00:22:57,750
δείχνοντας εκτός σκηνής κάπου? θέλουμε να είναι το χέρι προς τα κάτω, NULL,

381
00:22:57,750 --> 00:23:01,530
έτσι ώστε να έχουμε αυτό το τέρμα σε αυτή τη δομή των δεδομένων έτσι ώστε να γνωρίζουν πού τελειώνει.

382
00:23:01,530 --> 00:23:03,410
>> Τι γίνεται αν θέλουμε να χειριστείτε αυτό;

383
00:23:03,410 --> 00:23:05,980
Κάναμε το μεγαλύτερο μέρος αυτής της οπτικής, και με τους ανθρώπους,

384
00:23:05,980 --> 00:23:07,630
αλλά τι γίνεται αν θέλουμε να κάνουμε μια εισαγωγή;

385
00:23:07,630 --> 00:23:12,360
Έτσι ο αρχικός κατάλογος ήταν 9, 17, 20, 22, 29, 34.

386
00:23:12,360 --> 00:23:16,730
Τι θα συμβεί αν έχουμε συνέχεια θέλησε να malloc χώρο για τον αριθμό 55, ένας κόμβος για αυτό,

387
00:23:16,730 --> 00:23:20,730
και στη συνέχεια θέλουμε να εισάγετε 55 στη λίστα ακριβώς όπως κάναμε τη Δευτέρα;

388
00:23:20,730 --> 00:23:23,690
Πώς θα το κάνουμε αυτό; Λοιπόν, Ανίτα ήρθε και μπήκε ουσιαστικά τη λίστα.

389
00:23:23,690 --> 00:23:27,500
Ξεκίνησε στο πρώτο στοιχείο, τότε το επόμενο, το επόμενο, το επόμενο, το επόμενο, το επόμενο.

390
00:23:27,500 --> 00:23:29,500
Τέλος, χτύπησε το αριστερό χέρι σε όλη τη διαδρομή

391
00:23:29,500 --> 00:23:34,480
και συνειδητοποίησα OH, αυτό είναι NULL. Έτσι, αυτό που χειραγώγησης δείκτη έπρεπε να γίνει;

392
00:23:34,480 --> 00:23:37,980
Το άτομο που ήταν στο τέλος, αριθμός 34, απαιτείται το αριστερό του χέρι ανέκυψαν

393
00:23:37,980 --> 00:23:46,220
να επισημάνω σε 55, 55 χρειάζεται το αριστερό χέρι τους προς τα κάτω για να είναι ο νέος NULL τερματισμού. Τέλος.

394
00:23:46,220 --> 00:23:49,540
Αρκετά εύκολο να εισάγετε 55 σε μια ταξινομημένη λίστα.

395
00:23:49,540 --> 00:23:51,800
Και πώς θα μπορούσε αυτή η ματιά;

396
00:23:51,800 --> 00:23:55,690
>> Επιτρέψτε μου να προχωρήσει και να ανοίξει κάποιο παράδειγμα κώδικα εδώ.

397
00:23:55,690 --> 00:23:58,120
Θα ανοίξει το gedit, και επιτρέψτε μου να ανοίξει δύο αρχεία πρώτα.

398
00:23:58,120 --> 00:24:02,050
Το ένα είναι list1.h, και επιτρέψτε μου να υπενθυμίσω ότι αυτό ήταν το κομμάτι του κώδικα

399
00:24:02,050 --> 00:24:04,920
ότι χρησιμοποιείται για να αντιπροσωπεύει έναν κόμβο.

400
00:24:04,920 --> 00:24:13,040
Ένας κόμβος έχει και έναν int n ονομάζεται και ένα δείκτη που ονομάζεται επόμενο ότι μόνο τα σημεία για το επόμενο πράγμα στη λίστα.

401
00:24:13,040 --> 00:24:15,450
Αυτό είναι τώρα σε ένα αρχείο. H. Γιατί;

402
00:24:15,450 --> 00:24:19,090
Υπάρχει αυτή η σύμβαση, και δεν έχουν επωφεληθεί από αυτό το τεράστιο ποσό τους εαυτούς μας,

403
00:24:19,090 --> 00:24:22,220
αλλά το πρόσωπο που έγραψε printf και άλλες λειτουργίες

404
00:24:22,220 --> 00:24:27,150
έδωσε ως δώρο στον κόσμο όλες αυτές τις λειτουργίες, γράφοντας ένα αρχείο με όνομα stdio.h.

405
00:24:27,150 --> 00:24:30,950
Και έπειτα υπάρχει string.h, και στη συνέχεια υπάρχει map.h, και υπάρχει όλα αυτά τα αρχεία h

406
00:24:30,950 --> 00:24:34,410
ότι μπορεί να έχετε δει ή να χρησιμοποιηθούν κατά τη διάρκεια γραμμένα από άλλους ανθρώπους.

407
00:24:34,410 --> 00:24:38,470
Συνήθως σε αυτές. H αρχεία είναι μόνο πράγματα όπως typedefs

408
00:24:38,470 --> 00:24:42,310
ή δηλώσεις των προσαρμοσμένων τύπων ή δηλώσεις σταθερές.

409
00:24:42,310 --> 00:24:47,890
Δεν τίθεται υλοποιήσεις λειτουργίες »στα αρχεία κεφαλίδας.

410
00:24:47,890 --> 00:24:50,570
Βάζετε, αντί απλώς πρωτοτύπων τους.

411
00:24:50,570 --> 00:24:53,050
Θα βάλει τα πράγματα που θέλετε να μοιραστείτε με τον κόσμο αυτό που χρειάζονται

412
00:24:53,050 --> 00:24:55,640
Για να υπολογίσουν τον κωδικό τους. Έτσι, μόνο και μόνο για να μπει σε αυτή τη συνήθεια,

413
00:24:55,640 --> 00:24:59,110
αποφασίσαμε να κάνουμε το ίδιο πράγμα. Δεν υπάρχει πολύ σε list1.h,

414
00:24:59,110 --> 00:25:02,070
αλλά έχουμε βάλει κάτι που θα μπορούσε να ενδιαφέρει τους ανθρώπους του κόσμου

415
00:25:02,070 --> 00:25:05,030
που θέλετε να χρησιμοποιήσετε την εφαρμογή συνδεδεμένη λίστα μας.

416
00:25:05,030 --> 00:25:08,040
Τώρα, σε list1.c, δεν θα περάσει μέσα από όλο αυτό το πράγμα

417
00:25:08,040 --> 00:25:11,390
επειδή είναι λίγο καιρό, αυτό το πρόγραμμα, αλλά ας τρέξει πραγματικά γρήγορα στη γραμμή εντολών.

418
00:25:11,390 --> 00:25:15,720
Επιτρέψτε μου να συγκεντρώνουν κατάλογο1, επιτρέψτε μου να τρέξει τότε κατάλογο1, και αυτό που θα δείτε είναι

419
00:25:15,720 --> 00:25:18,070
προσομοίωση έχουμε ένα απλό μικρό πρόγραμμα εδώ

420
00:25:18,070 --> 00:25:20,990
που πρόκειται να μου επιτρέψετε να προσθέσετε και να καταργήσετε τους αριθμούς σε μια λίστα.

421
00:25:20,990 --> 00:25:24,310
Επιτρέψτε μου λοιπόν να προχωρήσουμε και πληκτρολογήστε 3 για την 3 η επιλογή του μενού.

422
00:25:24,310 --> 00:25:27,880
Θέλω να εισαγάγετε τον αριθμό - ας κάνουμε το πρώτο νούμερο, το οποίο ήταν 9,

423
00:25:27,880 --> 00:25:30,550
και τώρα είμαι είπε ο κατάλογος είναι τώρα 9.

424
00:25:30,550 --> 00:25:33,760
Επιτρέψτε μου να προχωρήσει και να κάνει μια άλλη εισαγωγή, έτσι χτύπησα μενού 3.

425
00:25:33,760 --> 00:25:36,760
Τι αριθμό μπορώ να θέλετε να εισάγετε; 17.

426
00:25:36,760 --> 00:25:39,220
Enter. Και θα το κάνω μόνο ένα περισσότερο.

427
00:25:39,220 --> 00:25:41,720
Επιτρέψτε μου να εισάγετε τον αριθμό 22.

428
00:25:41,720 --> 00:25:45,850
Έτσι, έχουμε τις απαρχές της συνδεδεμένη λίστα που είχαμε σε μορφή διαφανειών πριν από λίγο.

429
00:25:45,850 --> 00:25:48,740
Πώς είναι αυτή η παρεμβολή πραγματικά συμβαίνει;

430
00:25:48,740 --> 00:25:52,000
Πράγματι, είναι τώρα 22 στο τέλος της λίστας.

431
00:25:52,000 --> 00:25:55,050
Έτσι, η ιστορία που είπε στη σκηνή τη Δευτέρα και ανακεφαλαίωσε μόλις τώρα

432
00:25:55,050 --> 00:25:57,460
Πρέπει πραγματικά να συμβαίνει στον κώδικα.

433
00:25:57,460 --> 00:25:59,700
Ας ρίξουμε μια ματιά. Επιτρέψτε μου να μετακινηθείτε προς τα κάτω σε αυτό το αρχείο.

434
00:25:59,700 --> 00:26:01,720
Θα gloss πάνω από ορισμένες από τις λειτουργίες,

435
00:26:01,720 --> 00:26:05,630
αλλά θα πάμε κάτω, ας πούμε, η λειτουργία ένθετο.

436
00:26:05,630 --> 00:26:11,720
>> Ας δούμε πώς θα προχωρήσουμε σχετικά με την εισαγωγή ενός νέου κόμβου σε αυτή την συνδεδεμένη λίστα.

437
00:26:11,720 --> 00:26:14,550
Πού είναι η λίστα δήλωσε; Λοιπόν, ας μετακινηθείτε σε όλη τη διαδρομή μέχρι την κορυφή,

438
00:26:14,550 --> 00:26:19,970
και παρατηρήστε ότι συνδεδεμένη λίστα μου είναι ουσιαστικά δηλώνονται ως ένα ενιαίο δείκτη που είναι αρχικά NULL.

439
00:26:19,970 --> 00:26:23,180
Έτσι είμαι χρησιμοποιώντας μια καθολική μεταβλητή εδώ, το οποίο σε γενικές γραμμές έχουμε κηρύξει κατά

440
00:26:23,180 --> 00:26:25,280
διότι καθιστά τον κωδικό σας λίγο ακατάστατη να διατηρήσει,

441
00:26:25,280 --> 00:26:29,080
Είναι το είδος της τεμπέλης, συνήθως, αλλά αυτό δεν είναι τεμπέλης και δεν είναι λάθος και δεν είναι κακό

442
00:26:29,080 --> 00:26:33,660
αν μοναδικός σκοπός του προγράμματός σας στη ζωή είναι να προσομοιώσει μία συνδεδεμένη λίστα.

443
00:26:33,660 --> 00:26:35,460
Ποια είναι ακριβώς αυτό που κάνουμε.

444
00:26:35,460 --> 00:26:39,100
Έτσι, αντί να το δηλώσει στην κύρια και στη συνέχεια πρέπει να περάσει σε κάθε λειτουργία

445
00:26:39,100 --> 00:26:42,640
έχουμε γράψει σε αυτό το πρόγραμμα, αντί να συνειδητοποιήσουμε OH, ας κάνει το παγκόσμιο

446
00:26:42,640 --> 00:26:47,060
επειδή όλος ο σκοπός του προγράμματος αυτού είναι να παρουσιάσει μία και μόνο μία συνδεδεμένη λίστα.

447
00:26:47,060 --> 00:26:50,700
Έτσι, αυτό αισθάνεται εντάξει. Εδώ είναι πρωτότυπα μου, και δεν θα περάσουν από όλα αυτά,

448
00:26:50,700 --> 00:26:55,800
αλλά έγραψα μια λειτουργία διαγραφής, μια λειτουργία της αναζήτησης, μια λειτουργία ένθετο, και μια λειτουργία τραβέρσα.

449
00:26:55,800 --> 00:26:59,080
Αλλά ας πάμε τώρα πίσω στη λειτουργία ένθετο

450
00:26:59,080 --> 00:27:01,490
και να δούμε πώς αυτό λειτουργεί εδώ.

451
00:27:01,490 --> 00:27:09,940
Εισαγωγή είναι on line - εδώ πάμε.

452
00:27:09,940 --> 00:27:12,850
Εισαγωγή. Γι 'αυτό δεν παίρνει κανένα όρισμα, επειδή θα πάμε να ρωτήσω

453
00:27:12,850 --> 00:27:15,930
ο χρήστης μέσα από αυτή τη λειτουργία για τον αριθμό που θέλετε να εισαγάγετε.

454
00:27:15,930 --> 00:27:19,410
Αλλά πρώτα, ετοιμαζόμαστε να τους δώσουμε λίγο χώρο.

455
00:27:19,410 --> 00:27:22,050
Αυτό είναι το είδος αντιγραφή και επικόλληση από το άλλο παράδειγμα.

456
00:27:22,050 --> 00:27:25,110
Σε αυτή την περίπτωση, θα όριζαν ένα int? Αυτή τη φορά είμαστε κατανομή ενός κόμβου.

457
00:27:25,110 --> 00:27:27,910
Πραγματικά, δεν θυμάμαι πόσα bytes είναι ένας κόμβος, αλλά αυτό είναι εντάξει.

458
00:27:27,910 --> 00:27:30,460
Sizeof μπορεί να καταλάβει ότι για μένα.

459
00:27:30,460 --> 00:27:33,340
Και γιατί είμαι ο έλεγχος για NULL στη γραμμή 120;

460
00:27:33,340 --> 00:27:37,530
Τι θα μπορούσε να πάει στραβά στη γραμμή 119; Ναι;

461
00:27:37,530 --> 00:27:40,530
[Απάντηση Φοιτητής, ακατάληπτο]

462
00:27:40,530 --> 00:27:43,440
Καλή. Απλά θα μπορούσε να είναι η περίπτωση που έχω ζητήσει πάρα πολύ μνήμη

463
00:27:43,440 --> 00:27:47,020
ή κάτι δεν πάει καλά και το λειτουργικό σύστημα δεν έχει αρκετά bytes να μου δώσει,

464
00:27:47,020 --> 00:27:50,640
γι 'αυτό σηματοδοτεί τόσο από την επιστροφή NULL, και αν δεν ελέγξετε ότι

465
00:27:50,640 --> 00:27:54,710
και εγώ απλά τυφλά προβεί σε χρήση η διεύθυνση που επιστρέφεται, θα μπορούσε να είναι NULL.

466
00:27:54,710 --> 00:27:58,400
Θα μπορούσε να είναι κάποια άγνωστη τιμή? Δεν είναι ένα καλό πράγμα εάν εγώ -

467
00:27:58,400 --> 00:28:00,590
στην πραγματικότητα δεν θα είναι μια άγνωστη τιμή. Θα μπορούσε να είναι NULL, έτσι δεν θέλω

468
00:28:00,590 --> 00:28:02,550
για να την καταχραστούν και να διακινδυνεύσει εύρεση τιμών.

469
00:28:02,550 --> 00:28:07,410
Αν συμβεί αυτό, θα ήθελα απλώς να επιστρέψετε και θα προσποιηθώ όπως δεν είχα πάρει πίσω κάποια μνήμη καθόλου.

470
00:28:07,410 --> 00:28:12,270
>> Σε αντίθετη περίπτωση, λέω ο χρήστης να μου δώσει έναν αριθμό για να εισάγετε, καλώ παλιά GetInt φίλος μας,

471
00:28:12,270 --> 00:28:15,530
και στη συνέχεια αυτή ήταν η νέα σύνταξη εισαγάγαμε τη Δευτέρα.

472
00:28:15,530 --> 00:28:20,320
«Newptr-> n 'σημαίνει αναλάβει την διεύθυνση που σας δόθηκε από την malloc

473
00:28:20,320 --> 00:28:23,490
που αντιπροσωπεύει το πρώτο byte ενός νέου αντικειμένου κόμβο,

474
00:28:23,490 --> 00:28:26,860
και στη συνέχεια, μεταβείτε στο πεδίο που ονομάζεται n.

475
00:28:26,860 --> 00:28:35,270
Ένα μικρό trivia ερώτηση: Αυτό είναι ισοδύναμο με το τι πιο αινιγματικό γραμμή κώδικα;

476
00:28:35,270 --> 00:28:38,110
Πώς αλλιώς θα μπορούσα να έχω γράψει αυτό; Θέλετε να πάρετε μια μαχαιριά;

477
00:28:38,110 --> 00:28:41,480
[Απάντηση Φοιτητής, ακατάληπτο]

478
00:28:41,480 --> 00:28:44,870
Καλή. Χρησιμοποιώντας το. N, αλλά δεν είναι αρκετά τόσο απλό όσο αυτό.

479
00:28:44,870 --> 00:28:47,090
Τι θα πρέπει πρώτα να κάνετε; [Απάντηση Φοιτητής, ακατάληπτο]

480
00:28:47,090 --> 00:28:52,730
Καλή. Πρέπει να κάνω * newptr.n.

481
00:28:52,730 --> 00:28:55,610
Έτσι, αυτό που λέει νέο δείκτη είναι προφανώς μια διεύθυνση. Γιατί;

482
00:28:55,610 --> 00:28:59,520
Επειδή επέστρεψε από malloc. Η newptr * λέγοντας «πάμε εκεί»,

483
00:28:59,520 --> 00:29:02,970
και στη συνέχεια, όταν είστε εκεί, τότε μπορείτε να χρησιμοποιήσετε την πιο οικεία. n,

484
00:29:02,970 --> 00:29:05,730
αλλά αυτό φαίνεται λίγο άσχημο, ειδικά αν εμείς οι άνθρωποι πρόκειται να

485
00:29:05,730 --> 00:29:10,360
επιστήσει δείκτες με βέλη όλη την ώρα? ο κόσμος έχει τυποποιηθεί σε αυτό το συμβολισμό βέλος,

486
00:29:10,360 --> 00:29:12,320
το οποίο κάνει ακριβώς το ίδιο πράγμα.

487
00:29:12,320 --> 00:29:16,070
Έτσι, μπορείτε να χρησιμοποιήσετε μόνο το -> συμβολισμό όταν το πράγμα στα αριστερά είναι ένας δείκτης.

488
00:29:16,070 --> 00:29:18,790
Διαφορετικά, αν είναι μια πραγματική struct, χρησιμοποιήστε το. N.

489
00:29:18,790 --> 00:29:25,800
Και τότε αυτό: Γιατί μπορώ να προετοιμαστεί newptr-> δίπλα στο NULL;

490
00:29:25,800 --> 00:29:28,610
Δεν θέλουμε ένα κουνάμε το αριστερό χέρι μακριά από το τέλος του σταδίου.

491
00:29:28,610 --> 00:29:31,630
Θέλουμε να κοιτάνε προς τα κάτω, πράγμα που σημαίνει το τέλος αυτής της λίστας

492
00:29:31,630 --> 00:29:34,980
θα μπορούσε ενδεχομένως να είναι σε αυτόν τον κόμβο, γι 'αυτό καλύτερα να βεβαιωθείτε ότι είναι NULL.

493
00:29:34,980 --> 00:29:38,460
Και, σε γενικές γραμμές, την αρχικοποίηση μεταβλητών δεδομένων σας ή τα μέλη σας και structs

494
00:29:38,460 --> 00:29:40,470
να είναι κάτι απλά καλή πρακτική.

495
00:29:40,470 --> 00:29:45,170
Απλά να αφήσει σκουπίδια υπάρχουν και συνεχίζουν να υπάρχουν γενικά σας παίρνει σε μπελάδες

496
00:29:45,170 --> 00:29:48,650
αν ξεχάσετε να κάνετε κάτι αργότερα.

497
00:29:48,650 --> 00:29:51,590
>> Εδώ είναι μερικές περιπτώσεις. Αυτό, πάλι, είναι η λειτουργία ενθέτου,

498
00:29:51,590 --> 00:29:54,930
και το πρώτο πράγμα που μπορώ να ελέγξω για το αν είναι μεταβλητή που ονομάζεται κατ 'αρχάς,

499
00:29:54,930 --> 00:29:58,240
ότι η παγκόσμια μεταβλητή είναι NULL, αυτό σημαίνει ότι δεν υπάρχει συνδεδεμένη λίστα.

500
00:29:58,240 --> 00:30:02,460
Δεν έχουν εισαχθεί οποιουσδήποτε αριθμούς, γι 'αυτό είναι ασήμαντο για να εισάγετε τον αριθμό αυτό το ρεύμα

501
00:30:02,460 --> 00:30:05,240
στον κατάλογο, διότι ανήκει ακριβώς στην αρχή της λίστας.

502
00:30:05,240 --> 00:30:08,100
Έτσι, αυτό ήταν όταν ήταν μόλις Anita όρθιος μόνος εδώ, προσποιούμενος

503
00:30:08,100 --> 00:30:11,390
κανείς άλλος δεν ήταν μέχρι εδώ πάνω στη σκηνή μέχρι να διατεθεί ένα κόμβο,

504
00:30:11,390 --> 00:30:13,940
τότε θα μπορούσε να σηκώσει το χέρι της για πρώτη φορά,

505
00:30:13,940 --> 00:30:17,420
αν όλοι οι άλλοι είχαν καταλήξει στη σκηνή μετά την Δευτέρα.

506
00:30:17,420 --> 00:30:22,900
Τώρα, εδώ, αυτό είναι ένα μικρό έλεγχο όπου έχω να πω αν η αξία του νέου κόμβου του n

507
00:30:22,900 --> 00:30:27,370
είναι <η τιμή του η στην τρέχουσα πρώτο κόμβο,

508
00:30:27,370 --> 00:30:29,930
αυτό σημαίνει ότι υπάρχει μία συνδεδεμένη λίστα που είναι αρχίσει.

509
00:30:29,930 --> 00:30:32,330
Υπάρχει τουλάχιστον ένας κόμβος στη λίστα, αλλά αυτό το νέο τύπο

510
00:30:32,330 --> 00:30:37,230
ανήκει πριν, έτσι πρέπει να κινηθούν τα πράγματα γύρω.

511
00:30:37,230 --> 00:30:43,450
Με άλλα λόγια, αν η λίστα έχει ξεκινήσει με απλά, ας πούμε,

512
00:30:43,450 --> 00:30:48,100
μόνο ο αριθμός 17, που είναι το - στην πραγματικότητα, μπορούμε να το κάνουμε αυτό πιο καθαρά.

513
00:30:48,100 --> 00:30:56,010
Αν αρχίσουμε την ιστορία μας με ένα δείκτη που ονομάζεται εδώ πρώτα,

514
00:30:56,010 --> 00:30:59,870
και αρχικά είναι NULL, και εισάγετε τον αριθμό 9,

515
00:30:59,870 --> 00:31:02,510
ο αριθμός 9 ανήκει σαφώς κατά την έναρξη της λίστας.

516
00:31:02,510 --> 00:31:07,400
Ας προσποιηθούμε ότι malloced απλά τη διεύθυνση ή τον αριθμό 9 και το βάζουμε εδώ.

517
00:31:07,400 --> 00:31:13,170
Αν το πρώτο είναι 9 από προεπιλογή, το πρώτο σενάριο που συζητήθηκε σημαίνει ακριβώς το σημείο ας αυτός ο τύπος εδώ,

518
00:31:13,170 --> 00:31:15,790
αφήστε αυτό ως NULL? τώρα έχουμε τον αριθμό 9.

519
00:31:15,790 --> 00:31:18,280
Ο επόμενος αριθμός που θέλετε να εισαγάγετε είναι 17.

520
00:31:18,280 --> 00:31:22,420
17 ανήκει εδώ, έτσι θα πάμε να χρειαστεί να κάνετε κάποια λογική εντατικοποίηση μέσα από αυτό.

521
00:31:22,420 --> 00:31:26,060
Ας αντ 'αυτού, πριν το κάνουμε αυτό, ας προσποιηθούμε ότι θέλαμε να εισάγετε τον αριθμό 8.

522
00:31:26,060 --> 00:31:28,650
>> Έτσι, μόνο για λόγους ευκολίας, εγώ είμαι πρόκειται να συντάξουν εδώ.

523
00:31:28,650 --> 00:31:30,760
Αλλά θυμηθείτε, malloc να το βάλετε πιο οπουδήποτε.

524
00:31:30,760 --> 00:31:33,460
Αλλά για χάρη του σχεδίου, εγώ θα το πω εδώ.

525
00:31:33,460 --> 00:31:38,440
Έτσι έχω προσποιηθεί διατίθενται μόνο έναν κόμβο για τον αριθμό 8? Αυτό είναι NULL από προεπιλογή.

526
00:31:38,440 --> 00:31:42,800
Τι πρέπει να συμβεί τώρα; Ένα ζευγάρι από τα πράγματα.

527
00:31:42,800 --> 00:31:47,090
Κάναμε αυτό το λάθος στη σκηνή τη Δευτέρα, όπου θα ενημερώνεται ένα δείκτη, όπως αυτό,

528
00:31:47,090 --> 00:31:51,890
τότε το έκανε αυτό, και στη συνέχεια ισχυρίστηκε - ορφανά που όλοι οι άλλοι πάνω στη σκηνή.

529
00:31:51,890 --> 00:31:54,350
Επειδή εσείς can't - η σειρά των εργασιών είναι σημαντικό εδώ,

530
00:31:54,350 --> 00:31:58,760
γιατί τώρα έχουμε χάσει αυτό το κόμβο 9 που είναι ακριβώς το είδος των επιπλέουν στο διάστημα.

531
00:31:58,760 --> 00:32:01,150
Έτσι, αυτό δεν ήταν η σωστή προσέγγιση, τη Δευτέρα.

532
00:32:01,150 --> 00:32:03,330
Θα πρέπει πρώτα να κάνουμε κάτι άλλο.

533
00:32:03,330 --> 00:32:06,280
Η κατάσταση του κόσμου μοιάζει με αυτό. Αρχικά, 8 έχει διατεθεί.

534
00:32:06,280 --> 00:32:10,550
Τι θα ήταν ένας καλύτερος τρόπος για την εισαγωγή των 8;

535
00:32:10,550 --> 00:32:14,720
Αντί για την ενημέρωση αυτού του δείκτη πρώτα ενημερώσει μόνο αυτό το ένα εδώ αντ 'αυτού.

536
00:32:14,720 --> 00:32:17,720
Έτσι, χρειαζόμαστε μια γραμμή κώδικα που πρόκειται να μετατρέψει αυτό το χαρακτήρα NULL

537
00:32:17,720 --> 00:32:22,020
σε ένα πραγματικό δείκτη που είναι δείχνοντας στον κόμβο 9,

538
00:32:22,020 --> 00:32:27,970
και τότε μπορούμε με ασφάλεια να αλλάξετε πρώτα να επισημάνω σε αυτόν τον τύπο εδώ.

539
00:32:27,970 --> 00:32:31,330
Τώρα έχουμε μια λίστα, μια συνδεδεμένη λίστα, από δύο στοιχεία.

540
00:32:31,330 --> 00:32:33,580
Και τι σημαίνει αυτό πραγματικά μοιάζει εδώ;

541
00:32:33,580 --> 00:32:36,900
Αν κοιτάξουμε τον κώδικα, παρατηρώ ότι έχω κάνει ακριβώς αυτό.

542
00:32:36,900 --> 00:32:41,970
Έχω πει newptr, και σε αυτή την ιστορία, newptr έδειχνε σε αυτόν τον τύπο.

543
00:32:41,970 --> 00:32:45,520
>> Έτσι, επιτρέψτε μου να επιστήσω κάτι ακόμα, και θα έπρεπε να είχα μείνει λίγο περισσότερο χώρο για αυτό.

544
00:32:45,520 --> 00:32:48,540
Έτσι συγχωρήσει το μικροσκοπικό μικρό σχέδιο.

545
00:32:48,540 --> 00:32:52,140
Αυτός ο τύπος ονομάζεται newptr.

546
00:32:52,140 --> 00:32:57,940
Αυτή είναι η μεταβλητή που κήρυξε λίγες γραμμές νωρίτερα, στη γραμμή - λίγο πάνω από 25.

547
00:32:57,940 --> 00:33:03,430
Και αυτό είναι που δείχνουν προς 8. Έτσι, όταν λέω newptr-> επόμενο, αυτό σημαίνει ότι πηγαίνετε στο struct

548
00:33:03,430 --> 00:33:07,910
Αυτό είναι που υποδεικνύεται από newptr, έτσι είμαστε εδώ, πηγαίνετε εκεί.

549
00:33:07,910 --> 00:33:13,990
Στη συνέχεια, το βέλος που λέει να πάρει το επόμενο πεδίο, και στη συνέχεια το = λέει ό, τι βάλει αξία εκεί;

550
00:33:13,990 --> 00:33:17,280
Η τιμή αυτή ήταν το πρώτο? Τι αξία ήταν στην πρώτη;

551
00:33:17,280 --> 00:33:21,930
Πρώτη έδειχνε σε αυτόν τον κόμβο, έτσι αυτό σημαίνει ότι αυτό πρέπει τώρα να επισημάνω σε αυτό το κόμβο.

552
00:33:21,930 --> 00:33:25,660
Με άλλα λόγια, ό, τι φαίνεται όμως ένα γελοίο χάος με τη γραφή μου,

553
00:33:25,660 --> 00:33:28,620
τι είναι μια απλή ιδέα του απλά μετακινώντας τα βέλη γύρω από

554
00:33:28,620 --> 00:33:31,560
μεταφράζεται σε κώδικα με ακριβώς αυτή επένδυση ένα.

555
00:33:31,560 --> 00:33:38,110
Φυλάσσεται τι είναι στην πρώτη στο επόμενο πεδίο και στη συνέχεια να επικαιροποιεί τι πρώτη είναι στην πραγματικότητα.

556
00:33:38,110 --> 00:33:40,900
Ας πάμε μπροστά και fast-forward μέσω μερικών από αυτά,

557
00:33:40,900 --> 00:33:44,220
και να εξετάσουμε μόνο σε αυτό το εισαγωγή ουρά για τώρα.

558
00:33:44,220 --> 00:33:51,210
Ας υποθέσουμε ότι έχω φτάσει στο σημείο όπου θεωρώ ότι το επόμενο πεδίο κάποιου κόμβου είναι NULL.

559
00:33:51,210 --> 00:33:53,410
Και σε αυτό το σημείο στην ιστορία, μια λεπτομέρεια που είμαι συγκαλύπτουμε

560
00:33:53,410 --> 00:33:58,170
είναι ότι έχω εισήγαγε ένα άλλο δείκτη μέχρι εδώ στην γραμμή 142, δείκτης ο προκάτοχός.

561
00:33:58,170 --> 00:34:01,320
Ουσιαστικά, σε αυτό το σημείο στην ιστορία, αφού η λίστα παίρνει μεγάλη,

562
00:34:01,320 --> 00:34:04,800
Ι το είδος πρέπει να περπατήσει με τα δύο δάχτυλα, γιατί αν πάω πολύ μακριά,

563
00:34:04,800 --> 00:34:08,219
θυμάμαι σε ένα ενιαίο μήκους λίστα, δεν μπορείτε να πάτε προς τα πίσω.

564
00:34:08,219 --> 00:34:13,659
Έτσι, αυτή η ιδέα του predptr είναι το αριστερό μου δάχτυλο, και newptr - δεν newptr.

565
00:34:13,659 --> 00:34:17,199
Ένας άλλος δείκτης που είναι εδώ είναι άλλο δάχτυλο μου, και είμαι ακριβώς το είδος της τη λίστα με τα πόδια.

566
00:34:17,199 --> 00:34:22,179
Γι 'αυτό ότι υπάρχει. Αλλά ας αναλογιστούμε μόνο μία από τις απλούστερες περιπτώσεις εδώ.

567
00:34:22,179 --> 00:34:26,620
Αν επόμενο πεδίο της εν λόγω δείκτης είναι NULL, ποια είναι η λογική συνέπεια;

568
00:34:26,620 --> 00:34:30,840
Αν διέρχονται από αυτή τη λίστα και να χτυπήσει ένα NULL δείκτη;

569
00:34:30,840 --> 00:34:35,780
Είστε στο τέλος της λίστας, και έτσι ο κώδικας για να προσθέσετε τότε αυτό ένα πρόσθετο στοιχείο

570
00:34:35,780 --> 00:34:41,230
είναι το είδος της διαισθητικής θα λάβουν την επόμενη κόμβος των οποίων ο δείκτης είναι NULL,

571
00:34:41,230 --> 00:34:46,120
έτσι αυτό είναι σήμερα NULL, και να αλλάξει αυτό, όμως, να είναι η διεύθυνση του νέου κόμβου.

572
00:34:46,120 --> 00:34:52,260
Έτσι, είμαστε μόλις στην κατάρτιση κώδικα το βέλος που είχαμε στη σκηνή με την αύξηση αριστερό χέρι κάποιου.

573
00:34:52,260 --> 00:34:54,070
>> Και στην περίπτωση που θα κυματίσει τα χέρια μου σε προς το παρόν,

574
00:34:54,070 --> 00:34:58,020
μόνο και μόνο επειδή νομίζω ότι είναι εύκολο να χαθεί, όταν το κάνουμε σε αυτό το είδος του περιβάλλοντος,

575
00:34:58,020 --> 00:35:00,600
ελέγχει για εισαγωγή στο μέσο της λίστας.

576
00:35:00,600 --> 00:35:03,220
Αλλά μόνο διαισθητικά, τι πρέπει να συμβεί, αν θέλετε να υπολογίσετε

577
00:35:03,220 --> 00:35:06,600
όπου κάποιος αριθμός ανήκει στη μέση είναι εσείς πρέπει να το περπατήσετε

578
00:35:06,600 --> 00:35:09,510
με περισσότερα από ένα δάχτυλο, περισσότερα από ένα δείκτη,

579
00:35:09,510 --> 00:35:12,920
καταλάβω, όπου ανήκει από έλεγχο είναι το στοιχείο <η σημερινή,

580
00:35:12,920 --> 00:35:15,450
> Το σημερινό, και τη στιγμή που θα βρείτε αυτό το μέρος,

581
00:35:15,450 --> 00:35:20,400
τότε θα πρέπει να κάνετε αυτό το είδος του παιχνιδιού κέλυφος, όπου μπορείτε να μετακινήσετε τους δείκτες γύρω από πολύ προσεκτικά.

582
00:35:20,400 --> 00:35:23,850
Και η απάντηση, αν θέλετε να τον λόγο μέσα από αυτό στο σπίτι με δική σας,

583
00:35:23,850 --> 00:35:28,340
βράζει κάτω ακριβώς σε αυτές τις δύο γραμμές κώδικα, αλλά η σειρά αυτών των γραμμών είναι εξαιρετικά σημαντικό.

584
00:35:28,340 --> 00:35:31,390
Γιατί αν πέσει το χέρι κάποιου και να αυξήσει κάποιος άλλος είναι σε λάθος σειρά,

585
00:35:31,390 --> 00:35:34,580
και πάλι, θα μπορούσατε να καταλήξετε ορφανού τη λίστα.

586
00:35:34,580 --> 00:35:39,500
Για να συνοψίσουμε περισσότερο εννοιολογικά, η εισαγωγή στην ουρά είναι σχετικά απλή.

587
00:35:39,500 --> 00:35:42,940
Η εισαγωγή στο κεφάλι είναι επίσης σχετικά απλή,

588
00:35:42,940 --> 00:35:45,580
αλλά θα πρέπει να ενημερώσετε ένα πρόσθετο δείκτη αυτή τη φορά

589
00:35:45,580 --> 00:35:47,930
να αποσπάσουν τον αριθμό 5 στην λίστα εδώ,

590
00:35:47,930 --> 00:35:51,560
και στη συνέχεια την εισαγωγή στο μέσον περιλαμβάνει ακόμη μεγαλύτερη προσπάθεια,

591
00:35:51,560 --> 00:35:56,130
με πολύ προσεκτικά εισάγετε τον αριθμό 20 στην σωστή θέση του,

592
00:35:56,130 --> 00:35:58,350
η οποία είναι μεταξύ 17 και 22.

593
00:35:58,350 --> 00:36:02,700
Έτσι πρέπει να κάνουμε κάτι σαν να έχει το νέο σημείο κόμβο 20 έως 22,

594
00:36:02,700 --> 00:36:08,470
και, στη συνέχεια, δείκτης που κόμβου θα πρέπει να ενημερώνεται το τελευταίο;

595
00:36:08,470 --> 00:36:10,630
Είναι 17, για την εισαγωγή στην πραγματικότητα.

596
00:36:10,630 --> 00:36:14,080
Έτσι, και πάλι, εγώ θα αναβάλει την πραγματική κώδικα για τη συγκεκριμένη εφαρμογή.

597
00:36:14,080 --> 00:36:17,280
>> Με την πρώτη ματιά, είναι λίγο συντριπτική, αλλά είναι πραγματικά ακριβώς ένα άπειρο βρόχο

598
00:36:17,280 --> 00:36:21,770
Αυτό είναι looping, looping, looping, looping, και το σπάσιμο μόλις χτυπήσει το NULL δείκτη,

599
00:36:21,770 --> 00:36:24,590
σημείο στο οποίο μπορείτε να κάνετε την απαραίτητη εισαγωγή.

600
00:36:24,590 --> 00:36:30,960
Αυτό, λοιπόν, είναι αντιπροσωπευτική συνδέονται κώδικα εισαγωγής λίστα.

601
00:36:30,960 --> 00:36:34,590
Αυτό ήταν το είδος του πολύ, και αισθάνεται σαν έχουμε λύσει ένα πρόβλημα,

602
00:36:34,590 --> 00:36:36,940
αλλά έχουμε εισαγάγει μια ολόκληρη άλλη. Ειλικρινά, έχουμε περάσει όλο αυτό το διάστημα

603
00:36:36,940 --> 00:36:40,540
O στις μεγάλες και Ω και χρόνο λειτουργίας, προσπαθεί να λύσει τα προβλήματα πιο γρήγορα,

604
00:36:40,540 --> 00:36:43,270
και εδώ κάνουμε ένα μεγάλο βήμα προς τα πίσω, αισθάνεται.

605
00:36:43,270 --> 00:36:45,380
Και όμως, αν ο στόχος είναι η αποθήκευση δεδομένων,

606
00:36:45,380 --> 00:36:48,010
αισθάνεται σαν το Άγιο Δισκοπότηρο, όπως δήλωσε τη Δευτέρα, θα είναι πραγματικά

607
00:36:48,010 --> 00:36:50,470
να αποθηκεύουν τα πράγματα αμέσως.

608
00:36:50,470 --> 00:36:53,930
>> Στην πραγματικότητα, ας υποθέσουμε ότι κάναμε βάλει στην άκρη συνδεδεμένη λίστα για μια στιγμή

609
00:36:53,930 --> 00:36:56,000
και εισήγαγε την έννοια αντί ενός πίνακα.

610
00:36:56,000 --> 00:36:59,110
Και ας σκεφτούμε ένα τραπέζι για μια στιγμή ως μια σειρά.

611
00:36:59,110 --> 00:37:03,790
Αυτός ο πίνακας και η υπόθεση αυτή έχει εδώ 26 περίπου στοιχεία, από 0 έως 25,

612
00:37:03,790 --> 00:37:07,940
και ας υποθέσουμε ότι έχετε ανάγκη από κάποιο κομμάτι της αποθήκευσης για τα ονόματα:

613
00:37:07,940 --> 00:37:10,350
Alice και ο Bob και ο Τσάρλι και τα παρόμοια.

614
00:37:10,350 --> 00:37:12,880
Και θα πρέπει να έχετε κάποια δομή δεδομένων για την αποθήκευση αυτών των ονομάτων.

615
00:37:12,880 --> 00:37:15,000
Λοιπόν, μπορείτε να χρησιμοποιήσετε κάτι σαν μια συνδεδεμένη λίστα

616
00:37:15,000 --> 00:37:20,260
και μπορείτε να περπατήσετε τη λίστα πριν από την εισαγωγή Alice Bob και ο Τσάρλι, μετά τον Bob και ούτω καθεξής.

617
00:37:20,260 --> 00:37:23,850
Και, στην πραγματικότητα, αν θέλετε να δείτε τον κώδικα, όπως ότι ένα μέρος,

618
00:37:23,850 --> 00:37:27,230
Γνωρίζουμε ότι σε list2.h, κάνουμε ακριβώς αυτό.

619
00:37:27,230 --> 00:37:30,610
Εμείς δεν θα περάσει μέσα από αυτόν τον κώδικα, αλλά αυτό είναι μία παραλλαγή του πρώτου παραδείγματος

620
00:37:30,610 --> 00:37:34,640
που εισάγει ένα άλλο struct έχουμε ξαναδεί ονομάζεται φοιτητής,

621
00:37:34,640 --> 00:37:40,330
και στη συνέχεια ό, τι στην πραγματικότητα αποθηκεύει στην συνδεδεμένη λίστα είναι ένας δείκτης σε μια δομή φοιτητή

622
00:37:40,330 --> 00:37:44,520
μάλλον παρά μια απλή μικρή ακέραιος, n.

623
00:37:44,520 --> 00:37:46,900
Έτσι, συνειδητοποιούν ότι υπάρχει κώδικας εκεί που περιλαμβάνει την πραγματική χορδές,

624
00:37:46,900 --> 00:37:49,940
αλλά αν ο στόχος στο χέρι πραγματικά τώρα είναι να αντιμετωπιστεί το πρόβλημα της αποτελεσματικότητας,

625
00:37:49,940 --> 00:37:53,380
Δεν θα ήταν ωραίο αν μας δίνεται ένα αντικείμενο που ονομάζεται Alice,

626
00:37:53,380 --> 00:37:56,020
θέλουμε να την βάλει στη σωστή θέση σε μια δομή δεδομένων,

627
00:37:56,020 --> 00:37:58,860
αισθάνεται όπως θα ήθελα να είναι πραγματικά ωραίο να τεθεί μόνο Alice,

628
00:37:58,860 --> 00:38:01,180
του οποίου το όνομα αρχίζει με Α, στην πρώτη θέση.

629
00:38:01,180 --> 00:38:05,270
Και ο Μπομπ, του οποίου το όνομα αρχίζει με το Β, στην δεύτερη θέση.

630
00:38:05,270 --> 00:38:09,580
Με μια σειρά, ή ας αρχίσουμε καλώντας το ένα τραπέζι, ένα πίνακα κατακερματισμού στο ότι,

631
00:38:09,580 --> 00:38:13,650
μπορούμε να κάνουμε ακριβώς αυτό. Αν μας δίνεται ένα όνομα σαν την Αλίκη,

632
00:38:13,650 --> 00:38:16,700
μια σειρά σαν την Αλίκη, όπου βάζετε ένα-λ-ι-γ-ε;

633
00:38:16,700 --> 00:38:20,540
Χρειαζόμαστε μια hueristic. Χρειαζόμαστε μια λειτουργία για να λάβει κάποια στοιχεία σαν την Αλίκη

634
00:38:20,540 --> 00:38:24,610
και να επιστρέψει μια απάντηση, "Alice Βάλτε σε αυτή τη θέση."

635
00:38:24,610 --> 00:38:28,720
Και αυτή η λειτουργία, αυτό το μαύρο κουτί, θα πρέπει να ονομάζεται συνάρτηση κατακερματισμού.

636
00:38:28,720 --> 00:38:32,330
>> Μια συνάρτηση κατακερματισμού είναι κάτι που παίρνει μια είσοδο, όπως το "Alice",

637
00:38:32,330 --> 00:38:38,080
και επιστρέφει σε εσάς, συνήθως, η αριθμητική θέση σε κάποια δομή δεδομένων όπου ανήκει Alice.

638
00:38:38,080 --> 00:38:40,830
Σε αυτή την περίπτωση, συνάρτηση κατακερματισμού μας θα πρέπει να είναι σχετικά απλή.

639
00:38:40,830 --> 00:38:47,510
Hash λειτουργία μας πρέπει να πω, αν σας δίνεται "Alice", το οποίο χαρακτήρας θα πρέπει να με νοιάζει;

640
00:38:47,510 --> 00:38:55,660
Το πρώτο. Έτσι κοιτάζω [0], και στη συνέχεια να πω αν [0] χαρακτήρας είναι ένα, επιστρέφει τον αριθμό 0.

641
00:38:55,660 --> 00:39:01,130
Αν είναι Β, επιστρέφει 1. Αν C είναι, επιστρέφει 2, και ούτω καθεξής.

642
00:39:01,130 --> 00:39:05,940
Όλα δείκτη 0, και ότι θα μου επιτρέψετε να εισάγετε Alice και ο Bob, στη συνέχεια και στη συνέχεια Charlie και ούτω καθεξής

643
00:39:05,940 --> 00:39:10,960
σε αυτή τη δομή δεδομένων. Αλλά υπάρχει ένα πρόβλημα.

644
00:39:10,960 --> 00:39:13,060
Τι θα συμβεί αν Anita έρχεται και πάλι;

645
00:39:13,060 --> 00:39:17,510
Πού βάζουμε Anita; Το όνομά της, πάρα πολύ, αρχίζει με το γράμμα Α,

646
00:39:17,510 --> 00:39:20,330
και αισθάνεται σαν έχουμε κάνει ένα ακόμη μεγαλύτερο χάος από αυτό το πρόβλημα.

647
00:39:20,330 --> 00:39:24,380
Έχουμε τώρα άμεση εισαγωγή, συνεχή εισαγωγή του χρόνου, σε μια δομή δεδομένων

648
00:39:24,380 --> 00:39:27,100
παρά στη χειρότερη περίπτωση γραμμική,

649
00:39:27,100 --> 00:39:29,510
αλλά τι μπορούμε να κάνουμε με την Anita σε αυτή την περίπτωση;

650
00:39:29,510 --> 00:39:34,110
Ποιες είναι οι δύο επιλογές, πραγματικά; Ναι;

651
00:39:34,110 --> 00:39:37,410
[Απάντηση Φοιτητής, ακατάληπτο] Εντάξει, έτσι θα μπορούσαμε να έχουμε μια άλλη διάσταση.

652
00:39:37,410 --> 00:39:42,320
Αυτό είναι καλό. Έτσι μπορούμε να οικοδομήσουμε τα πράγματα σε 3D, όπως μιλήσαμε προφορικά τη Δευτέρα.

653
00:39:42,320 --> 00:39:46,700
Θα μπορούσαμε να προσθέσετε μια άλλη πρόσβαση εδώ, αλλά ας υποθέσουμε ότι δεν υπάρχει, είμαι προσπαθεί να κρατήσει το απλό.

654
00:39:46,700 --> 00:39:50,160
Το σύνολο στόχος εδώ είναι να έχουμε άμεση σταθερό χρόνο πρόσβασης,

655
00:39:50,160 --> 00:39:52,170
έτσι ώστε να είναι η προσθήκη πάρα πολύ περίπλοκο.

656
00:39:52,170 --> 00:39:55,970
Ποιες είναι οι άλλες επιλογές, όταν προσπαθείτε να εισαγάγετε Anita σε αυτή τη δομή δεδομένων; Ναι;

657
00:39:55,970 --> 00:39:58,610
[Απάντηση Φοιτητής, ακατάληπτο] Καλή. Έτσι, θα μπορούσαμε να προχωρήσουμε όλοι οι άλλοι κάτω,

658
00:39:58,610 --> 00:40:03,040
όπως Charlie nudges κάτω Bob και η Alice, και στη συνέχεια βάζουμε Anita όπου θέλει πραγματικά να είναι.

659
00:40:03,040 --> 00:40:05,660
>> Φυσικά, τώρα, υπάρχει μια παρενέργεια αυτού.

660
00:40:05,660 --> 00:40:09,000
Αυτή η δομή δεδομένων είναι μάλλον χρήσιμο όχι επειδή θέλουμε να εισάγετε τους ανθρώπους μια φορά

661
00:40:09,000 --> 00:40:11,250
αλλά επειδή θέλουμε να ελέγξετε αν είστε εκεί αργότερα

662
00:40:11,250 --> 00:40:13,600
αν θέλουμε να εκτυπώσετε όλα τα ονόματα στη δομή των δεδομένων.

663
00:40:13,600 --> 00:40:15,850
Εμείς πάμε για να κάνουμε κάτι με αυτά τα δεδομένα τελικά.

664
00:40:15,850 --> 00:40:20,810
Έτσι τώρα έχουμε το είδος της βιδωθεί πάνω από Alice, ο οποίος δεν είναι πλέον όπου υποτίθεται ότι είναι.

665
00:40:20,810 --> 00:40:23,880
Ούτε είναι ο Bob, ούτε είναι ο Τσάρλι.

666
00:40:23,880 --> 00:40:26,060
Έτσι, ίσως αυτό δεν είναι και τόσο καλή ιδέα.

667
00:40:26,060 --> 00:40:28,830
Αλλά πράγματι, αυτό είναι μια επιλογή. Θα μπορούσαν να στρέψουν όλοι κάτω,

668
00:40:28,830 --> 00:40:32,240
ή heck, Anita ήρθε αργά στο παιχνίδι, γιατί δεν βάζουμε μόνο Anita

669
00:40:32,240 --> 00:40:35,870
δεν είναι εδώ, δεν είναι εδώ, δεν είναι εδώ, ας βάλουμε της λίγο χαμηλότερα στη λίστα.

670
00:40:35,870 --> 00:40:38,680
Στη συνέχεια, όμως αυτό το πρόβλημα αρχίζει να περιέρχεται και πάλι.

671
00:40:38,680 --> 00:40:41,630
Ίσως να είναι σε θέση να βρείτε Alice αμέσως, με βάση το όνομά της.

672
00:40:41,630 --> 00:40:44,320
Και ο Bob αμέσως, και ο Τσάρλι. Αλλά τότε θα κοιτάξουμε για Anita,

673
00:40:44,320 --> 00:40:46,360
και θα δείτε, χμμ, Alice είναι στο δρόμο.

674
00:40:46,360 --> 00:40:48,770
Λοιπόν, επιτρέψτε μου να ελέγξετε κάτω από Alice. Bob δεν είναι Anita.

675
00:40:48,770 --> 00:40:51,850
Τσάρλι δεν είναι Anita. Ω, υπάρχει Ανίτα.

676
00:40:51,850 --> 00:40:54,720
Και αν συνεχίσετε το τρένο της λογικής σε όλη τη διαδρομή,

677
00:40:54,720 --> 00:41:00,690
Ποια είναι η χειρότερη περίπτωση χρόνος λειτουργίας για την εξεύρεση ή την εισαγωγή Anita σε αυτή τη νέα δομή δεδομένων;

678
00:41:00,690 --> 00:41:03,280
Είναι O (n), έτσι δεν είναι;

679
00:41:03,280 --> 00:41:06,280
Επειδή στη χειρότερη περίπτωση, υπάρχει Alice, ο Bob, ο Τσάρλι. . .

680
00:41:06,280 --> 00:41:10,150
σε όλη τη διαδρομή σε κάποιον που ονομάζεται "Υ", έτσι υπάρχει μόνο ένα σημείο αριστερά.

681
00:41:10,150 --> 00:41:13,950
Ευτυχώς, δεν έχουμε ένα ονομάζεται "Ζ", έτσι βάλαμε Anita στο κάτω μέρος.

682
00:41:13,950 --> 00:41:16,040
>> Εμείς δεν έχουμε λύσει πραγματικά το πρόβλημα.

683
00:41:16,040 --> 00:41:19,890
Έτσι, ίσως χρειάζεται να εισαγάγει αυτή την τρίτη διάσταση.

684
00:41:19,890 --> 00:41:22,230
Και αποδεικνύεται, αν δεν εισάγουν αυτή την τρίτη διάσταση,

685
00:41:22,230 --> 00:41:25,240
δεν μπορούμε να κάνουμε αυτό τέλεια, αλλά το Άγιο Δισκοπότηρο πρόκειται να πάρει

686
00:41:25,240 --> 00:41:28,370
σταθερής χρονική στιγμή της εισαγωγής και δυναμικές προσθήκες έτσι ώστε να

687
00:41:28,370 --> 00:41:30,960
δεν έχουμε στο σκληρό-κώδικα ένας πίνακας μεγέθους 26.

688
00:41:30,960 --> 00:41:34,400
Μπορούμε να εισάγετε ως πολλά ονόματα όπως θέλουμε, αλλά ας ρίξουμε 5-λεπτά διάλειμμα μας εδώ

689
00:41:34,400 --> 00:41:38,790
και στη συνέχεια, κάντε ότι σωστά.

690
00:41:38,790 --> 00:41:46,020
Εντάξει. Έθεσα την ιστορία μέχρι εκεί αρκετά τεχνητά

691
00:41:46,020 --> 00:41:48,670
επιλέγοντας Alice και ο Bob, στη συνέχεια και στη συνέχεια Charlie και στη συνέχεια, Anita,

692
00:41:48,670 --> 00:41:51,000
του οποίου το όνομα ήταν προφανώς πρόκειται να συγκρουστούν με την Αλίκη.

693
00:41:51,000 --> 00:41:54,120
Αλλά το ερώτημα που έληξε τη Δευτέρα με το πόσο είναι πιθανό να είναι

694
00:41:54,120 --> 00:41:56,370
ότι θα πάρει αυτά τα είδη των συγκρούσεων; Με άλλα λόγια,

695
00:41:56,370 --> 00:42:00,490
αν αρχίσουμε να χρησιμοποιήσετε αυτό το πίνακα δομή, η οποία είναι πραγματικά ακριβώς μια σειρά,

696
00:42:00,490 --> 00:42:02,460
σε αυτή την περίπτωση από 26 περιοχές,

697
00:42:02,460 --> 00:42:05,740
τι θα γίνει αν οι εισροές μας αντί ομοιόμορφα κατανεμημένες;

698
00:42:05,740 --> 00:42:09,620
Δεν είναι τεχνητά Alice και ο Bob και ο Τσάρλι και ο David και ούτω καθεξής αλφαβητικά,

699
00:42:09,620 --> 00:42:12,380
αυτό είναι ομοιόμορφα κατανεμημένο πάνω από το A έως το Z.

700
00:42:12,380 --> 00:42:15,220
>> Ίσως απλά θα πάρετε τυχεροί και εμείς δεν πρόκειται να έχει δύο Α ή δύο Β

701
00:42:15,220 --> 00:42:17,640
με πολύ μεγάλη πιθανότητα, αλλά όπως επεσήμανε κάποιος,

702
00:42:17,640 --> 00:42:20,730
αν γενικευμένη αυτό το πρόβλημα και δεν κάνουμε 0 - 25

703
00:42:20,730 --> 00:42:26,060
αλλά, ας πούμε, από 0 έως 364 ή 65, συχνά ο αριθμός των ημερών σε ένα τυπικό χρόνια,

704
00:42:26,060 --> 00:42:31,170
και ζήτησε από την ερώτηση, "Ποια είναι η πιθανότητα ότι δύο από εμάς σε αυτό το δωμάτιο έχουν την ίδια γενέθλια;"

705
00:42:31,170 --> 00:42:34,600
Βάλτε έναν άλλο τρόπο, ποια είναι η πιθανότητα ότι δύο από μας έχουν ένα όνομα που αρχίζει με ένα;

706
00:42:34,600 --> 00:42:37,190
Το είδος της ερώτησης είναι η ίδια, αλλά αυτό το χώρο διευθύνσεων,

707
00:42:37,190 --> 00:42:39,940
αυτός ο χώρος αναζήτησης, είναι μεγαλύτερο στην περίπτωση της γενέθλια,

708
00:42:39,940 --> 00:42:42,820
γιατί έχουμε τόσες πολλές περισσότερες ημέρες του έτους από γράμματα του αλφαβήτου.

709
00:42:42,820 --> 00:42:44,910
Ποια είναι η πιθανότητα μιας σύγκρουσης;

710
00:42:44,910 --> 00:42:48,410
Λοιπόν, μπορούμε να σκεφτούμε αυτό από βγάλει τα μαθηματικά με τον αντίθετο τρόπο.

711
00:42:48,410 --> 00:42:50,580
Ποια είναι η πιθανότητα χωρίς συγκρούσεις;

712
00:42:50,580 --> 00:42:53,970
Λοιπόν, αυτή η έκφραση εδώ λέει πως ό, τι είναι η πιθανότητα

713
00:42:53,970 --> 00:42:58,770
αν υπάρχει μόνο ένα άτομο σε αυτή την αίθουσα, ότι έχουν μια μοναδική γενέθλια;

714
00:42:58,770 --> 00:43:01,190
Είναι 100%. Διότι, αν υπάρχει μόνο ένα άτομο στο δωμάτιο,

715
00:43:01,190 --> 00:43:03,940
του ή τα γενέθλιά της μπορεί να είναι οποιαδήποτε από τις 365 ημέρες από το χρόνο.

716
00:43:03,940 --> 00:43:08,650
Έτσι, 365/365 επιλογές μου δίνει την τιμή 1.

717
00:43:08,650 --> 00:43:11,250
Έτσι, η εν λόγω πιθανότητα αυτή τη στιγμή είναι μόλις 1.

718
00:43:11,250 --> 00:43:13,270
Αλλά αν υπάρχει ένα δεύτερο άτομο στο δωμάτιο,

719
00:43:13,270 --> 00:43:16,490
Ποια είναι η πιθανότητα ότι τα γενέθλιά τους είναι διαφορετική;

720
00:43:16,490 --> 00:43:20,680
Υπάρχει δυνατή μόλις 364 ημέρες, αγνοώντας τα δίσεκτα έτη,

721
00:43:20,680 --> 00:43:23,580
για τα γενέθλιά τους, να μην συγκρούονται με τα άλλα πρόσωπα.

722
00:43:23,580 --> 00:43:31,920
Έτσι, 364/365. Αν ένα τρίτο άτομο έρχεται σε, είναι 363/365, και ούτω καθεξής.

723
00:43:31,920 --> 00:43:35,790
Έτσι κρατάμε το γινόμενο αυτών των κλασμάτων, οι οποίες γίνονται όλο και μικρότερα,

724
00:43:35,790 --> 00:43:40,720
για να καταλάβουμε ποια είναι η πιθανότητα ότι όλοι μας έχουμε το μοναδικό γενέθλια;

725
00:43:40,720 --> 00:43:43,570
Στη συνέχεια, όμως μπορούμε, φυσικά, μόλις λάβει την απάντηση και γυρίστε το γύρω

726
00:43:43,570 --> 00:43:47,210
και να κάνει 1 μείον όλα αυτά, μια έκφραση που θα πάρει τελικά

727
00:43:47,210 --> 00:43:51,250
αν θυμάστε το πίσω μέρος των βιβλίων σας μαθηματικά, φαίνεται λίγο κάτι σαν αυτό,

728
00:43:51,250 --> 00:43:54,590
η οποία είναι πολύ πιο εύκολα να ερμηνευθεί γραφικά.

729
00:43:54,590 --> 00:43:57,820
Και αυτό το γραφικό εδώ έχει στον άξονα x τον αριθμό των γενεθλίων,

730
00:43:57,820 --> 00:44:02,030
ή ο αριθμός των ατόμων με γενέθλια, και στον άξονα y είναι η πιθανότητα ενός αγώνα.

731
00:44:02,030 --> 00:44:06,060
Και τι είναι αυτό που λέει είναι ότι αν έχετε, ας πούμε, ακόμα,

732
00:44:06,060 --> 00:44:10,860
Ας επιλέξουν κάτι σαν 22, 23.

733
00:44:10,860 --> 00:44:13,160
Αν υπάρχει 22 ή 23 άτομα σε ένα δωμάτιο,

734
00:44:13,160 --> 00:44:17,100
η πιθανότητα ότι δύο από αυτές τις πολύ λίγοι άνθρωποι θα έχουν την ίδια γενέθλια

735
00:44:17,100 --> 00:44:19,560
Είναι πραγματικά εξαιρετικά υψηλή, συνδυαστικά.

736
00:44:19,560 --> 00:44:23,450
50% πιθανότητες ότι σε μια κατηγορία από μόνο 22 άτομα, ένα σεμινάριο, πρακτικά,

737
00:44:23,450 --> 00:44:25,790
2 από αυτούς τους ανθρώπους θα έχουν την ίδια γενέθλια.

738
00:44:25,790 --> 00:44:28,520
Επειδή υπάρχει τόσο πολλοί τρόποι με τους οποίους μπορείτε να έχετε την ίδια γενέθλια.

739
00:44:28,520 --> 00:44:31,110
Ακόμη χειρότερα, αν δείτε στη δεξιά πλευρά του γραφήματος,

740
00:44:31,110 --> 00:44:34,040
από τη στιγμή που έχετε μια τάξη με 58 μαθητές σε αυτό,

741
00:44:34,040 --> 00:44:39,270
η πιθανότητα 2 άτομα έχουν γενέθλια είναι super, super υψηλή, σχεδόν 100%.

742
00:44:39,270 --> 00:44:41,880
Τώρα, αυτό είναι ένα είδος διασκέδασης γεγονός για την πραγματική ζωή.

743
00:44:41,880 --> 00:44:45,850
>> Αλλά οι συνέπειες, τώρα, για τις δομές δεδομένων και αποθήκευση πληροφοριών

744
00:44:45,850 --> 00:44:51,100
σημαίνει ότι μόνο με την προϋπόθεση να έχουν μια ωραία, καθαρή, ομοιόμορφη κατανομή των δεδομένων

745
00:44:51,100 --> 00:44:53,650
και έχετε μια αρκετά μεγάλη ποικιλία για να χωρέσει ένα σωρό πράγματα

746
00:44:53,650 --> 00:44:59,360
δεν σημαίνει ότι θα πάμε για να πάρει τους ανθρώπους σε μοναδικές τοποθεσίες.

747
00:44:59,360 --> 00:45:03,810
Θα πάμε να έχουν συγκρούσεις. Έτσι, η έννοια του κατακερματισμού, όπως λέγεται,

748
00:45:03,810 --> 00:45:07,450
λαμβάνοντας μια είσοδο σαν «Αλίκη» και το μασάζ με κάποιο τρόπο

749
00:45:07,450 --> 00:45:10,190
και στη συνέχεια να πάρει πίσω μια απάντηση όπως 0 ή 1 ή 2.

750
00:45:10,190 --> 00:45:17,500
Να πάρει πίσω κάποια έξοδο από την λειτουργία μαστίζεται από την παρούσα πιθανότητα σύγκρουσης.

751
00:45:17,500 --> 00:45:19,530
Λοιπόν, πώς μπορούμε να χειριστούμε αυτές τις συγκρούσεις;

752
00:45:19,530 --> 00:45:21,940
Λοιπόν, σε μία περίπτωση, μπορούμε να πάρουμε την ιδέα που προτάθηκε.

753
00:45:21,940 --> 00:45:25,100
Μπορούμε να μετατοπιστεί λίγο όλοι κάτω, ή ίσως, λίγο πιο απλά,

754
00:45:25,100 --> 00:45:29,870
όχι ο καθένας κίνηση άλλος, ας προχωρήσουμε λίγο Anita στο κάτω μέρος του διαθέσιμου σημείο.

755
00:45:29,870 --> 00:45:32,810
Έτσι, αν Alice είναι 0, ο Bob είναι σε 1, Τσάρλι είναι σε 2,

756
00:45:32,810 --> 00:45:35,260
θα βάλουμε απλώς Anita στη θέση 3.

757
00:45:35,260 --> 00:45:38,860
Και αυτό είναι μια τεχνική σε δομές δεδομένων που ονομάζεται γραμμική σχολαστικά.

758
00:45:38,860 --> 00:45:41,310
Γραμμική επειδή περπατάτε ακριβώς αυτή τη γραμμή, και είστε το είδος της σχολαστικά

759
00:45:41,310 --> 00:45:43,640
για διαθέσιμες θέσεις στη δομή δεδομένων.

760
00:45:43,640 --> 00:45:46,210
Φυσικά, αυτό περιέρχεται σε O (n).

761
00:45:46,210 --> 00:45:49,590
Αν η δομή των δεδομένων είναι πραγματικά πλήρης, υπάρχει 25 άτομα σε αυτό ήδη,

762
00:45:49,590 --> 00:45:54,120
και στη συνέχεια έρχεται Anita, που καταλήγει σε τι θέση θα είναι Ζ, και ότι είναι μια χαρά.

763
00:45:54,120 --> 00:45:56,540
Της ταιριάζει ακόμα, και μπορούμε να τη βρούμε αργότερα.

764
00:45:56,540 --> 00:46:00,100
>> Αλλά αυτό ήταν αντίθετο προς το στόχο της επιτάχυνση πράγματα.

765
00:46:00,100 --> 00:46:02,530
Τι κι αν έχουμε εισαγάγει αντί αυτή η τρίτη διάσταση;

766
00:46:02,530 --> 00:46:06,400
Αυτή η τεχνική ονομάζεται γενικά ξεχωριστό αλυσοποίηση, ή με αλυσίδες.

767
00:46:06,400 --> 00:46:10,030
Και τι ένα πίνακα κατακερματισμού είναι τώρα, αυτή η δομή πίνακα,

768
00:46:10,030 --> 00:46:13,450
το τραπέζι σας είναι απλώς μια σειρά από δείκτες.

769
00:46:13,450 --> 00:46:18,230
Αλλά ποιοί είναι αυτοί οι δείκτες δείχνουν να είναι εικασία τι;

770
00:46:18,230 --> 00:46:21,970
Μια συνδεδεμένη λίστα. Τι κι αν πάρουμε το καλύτερο και των δύο αυτών κόσμων;

771
00:46:21,970 --> 00:46:26,500
Χρησιμοποιούμε πίνακες για τις αρχικές δείκτες

772
00:46:26,500 --> 00:46:32,070
μέσα στην δομή δεδομένων έτσι ώστε να μπορούμε αμέσως πάμε στο [0] [1], [30], ή ούτω καθεξής,

773
00:46:32,070 --> 00:46:36,480
αλλά έτσι ώστε να έχουμε κάποια ευελιξία και θα μπορούν να χωρέσουν Anita και η Alice και ο Αδάμ

774
00:46:36,480 --> 00:46:38,630
και οποιοδήποτε άλλο Ένα όνομα,

775
00:46:38,630 --> 00:46:43,470
εμείς αντί να αφήσουμε το άλλο άξονα αυξάνεται αυθαίρετα.

776
00:46:43,470 --> 00:46:47,340
Και τελικά, από τη Δευτέρα, έχουν αυτό το εκφραστικό δυνατότητα με συνδεδεμένη λίστα.

777
00:46:47,340 --> 00:46:49,530
Μπορούμε να αναπτυχθεί μια δομή δεδομένων αυθαίρετα.

778
00:46:49,530 --> 00:46:52,450
Εναλλακτικά, θα μπορούσαμε να κάνουμε μόνο μια τεράστια 2-διάστατο πίνακα,

779
00:46:52,450 --> 00:46:57,190
αλλά ότι πρόκειται να είναι μια φρικτή κατάσταση, εάν μία από τις σειρές σε ένα 2-διάστατο πίνακα

780
00:46:57,190 --> 00:47:01,280
δεν είναι αρκετά μεγάλο για το επιπλέον άτομο το όνομα του οποίου συμβαίνει να ξεκινήσει με Α.

781
00:47:01,280 --> 00:47:04,200
Θεός φυλάξοι θα πρέπει να ανακατανείμει μια τεράστια 2-τρισδιάστατη δομή

782
00:47:04,200 --> 00:47:06,600
μόνο και μόνο επειδή υπάρχει τόσο πολλοί άνθρωποι που ονομάζεται Α,

783
00:47:06,600 --> 00:47:09,480
ειδικά όταν υπάρχει τόσο λίγοι άνθρωποι που ονομάζεται Z κάτι.

784
00:47:09,480 --> 00:47:12,170
Είναι ακριβώς πρόκειται να είναι μια πολύ αραιή δομή δεδομένων.

785
00:47:12,170 --> 00:47:15,400
Έτσι δεν είναι τέλειο, με οποιοδήποτε μέσο, ​​αλλά τώρα έχουμε τουλάχιστον τη δυνατότητα

786
00:47:15,400 --> 00:47:19,090
να βρείτε άμεσα ή όπου Alice Anita ανήκει,

787
00:47:19,090 --> 00:47:21,090
τουλάχιστον από την άποψη του κατακόρυφο άξονα,

788
00:47:21,090 --> 00:47:25,850
και στη συνέχεια εμείς απλά πρέπει να αποφασίσετε πού να βάλει Anita ή Αλίκη στη χώρα αυτή συνδεδεμένη λίστα.

789
00:47:25,850 --> 00:47:32,480
Αν δεν με νοιάζει για να τακτοποιήσει τα πράγματα, πόσο γρήγορα θα μπορούσαμε να εισάγετε Αλίκη σε μια δομή σαν αυτό;

790
00:47:32,480 --> 00:47:35,370
Είναι σταθερό χρόνο. Εμείς δείκτη σε [0], αν και δεν υπάρχει κανείς,

791
00:47:35,370 --> 00:47:37,550
Alice πηγαίνει κατά την έναρξη της εν λόγω συνδεδεμένη λίστα.

792
00:47:37,550 --> 00:47:40,000
Αλλά αυτό δεν είναι μια τεράστια συμφωνία. Γιατί αν Anita έρχεται έπειτα κατά μήκος

793
00:47:40,000 --> 00:47:42,160
μερικά βήματα από τον αριθμό αργότερα, όπου δεν ανήκουν Anita;

794
00:47:42,160 --> 00:47:45,140
Λοιπόν, [0]. OOP. Alice είναι ήδη σε αυτή συνδεδεμένη λίστα.

795
00:47:45,140 --> 00:47:47,760
>> Αλλά αν δεν με νοιάζει για τη διαλογή αυτά τα ονόματα,

796
00:47:47,760 --> 00:47:53,580
μπορούμε να προχωρήσουμε λίγο πάνω από Alice, ένθετο Anita, αλλά ακόμα και αυτό είναι σταθερό χρόνο.

797
00:47:53,580 --> 00:47:57,010
Ακόμα κι αν υπάρχει Αλίκη και ο Αδάμ και όλα τα άλλα ονόματα Α,

798
00:47:57,010 --> 00:47:59,410
δεν είναι μετατόπιση τους πραγματικά σωματικά. Γιατί;

799
00:47:59,410 --> 00:48:04,090
Επειδή ακριβώς έκανε εδώ με συνδεδεμένη λίστα, ποιος ξέρει ήταν οι κόμβοι αυτοί είναι ούτως ή άλλως;

800
00:48:04,090 --> 00:48:06,550
Το μόνο που έχετε να κάνετε είναι να μετακινήσετε τα ψίχουλα ψωμιού.

801
00:48:06,550 --> 00:48:10,930
Μετακινήστε τα βέλη γύρω? Δεν πρέπει να προχωρήσουμε φυσικά όλα τα δεδομένα γύρω.

802
00:48:10,930 --> 00:48:14,610
Έτσι μπορούμε να εισάγουμε Anita, στην περίπτωση αυτή, αμέσως. Σταθερό χρόνο.

803
00:48:14,610 --> 00:48:20,250
Έτσι έχουμε συνεχή χρόνο αναζήτησης, και σταθερής χρονική στιγμή της εισαγωγής του κάποιος σαν τον Ανίτα.

804
00:48:20,250 --> 00:48:22,740
Αλλά το είδος της υπεραπλούστευση τον κόσμο.

805
00:48:22,740 --> 00:48:28,510
Κι αν αργότερα θέλετε να βρείτε Alice;

806
00:48:28,510 --> 00:48:31,050
Κι αν αργότερα θέλετε να βρείτε Alice;

807
00:48:31,050 --> 00:48:35,690
Πόσα βήματα είναι ότι πρόκειται να πάρει;

808
00:48:35,690 --> 00:48:37,850
[Απάντηση Φοιτητής, ακατάληπτο]

809
00:48:37,850 --> 00:48:40,950
Ακριβώς. Ο αριθμός των ανθρώπων πριν Αλίκη στη συνδεδεμένη λίστα.

810
00:48:40,950 --> 00:48:45,420
Έτσι δεν είναι αρκετά τέλειος, επειδή η δομή των δεδομένων μας, πάλι, έχει αυτή την κάθετη πρόσβαση

811
00:48:45,420 --> 00:48:50,240
και στη συνέχεια να έχει αυτές τις συνδεδεμένες λίστες κρέμονται - στην πραγματικότητα, ας μην το τραβάμε μια μια σειρά.

812
00:48:50,240 --> 00:48:56,020
Έχει αυτά τα συνδεδεμένες λίστες κρέμεται μακριά από αυτό που μοιάζει λίγο κάτι σαν αυτό.

813
00:48:56,020 --> 00:48:59,110
Αλλά το πρόβλημα είναι αν η Alice και ο Αδάμ και όλα τα άλλα ονόματα Α

814
00:48:59,110 --> 00:49:01,720
καταλήγουν όλο και περισσότερο εκεί,

815
00:49:01,720 --> 00:49:04,810
εύρεση κάποιος θα μπορούσε να καταλήγουν να λαμβάνουν ένα μάτσο βήματα,

816
00:49:04,810 --> 00:49:06,670
bcause θα πρέπει να διασχίσει τη συνδεδεμένη λίστα,

817
00:49:06,670 --> 00:49:08,090
η οποία είναι μια γραμμική λειτουργία.

818
00:49:08,090 --> 00:49:14,270
Έτσι, στην πραγματικότητα, τότε, η χρονική στιγμή της εισαγωγής είναι τελικά O (n), όπου n είναι ο αριθμός των στοιχείων στη λίστα.

819
00:49:14,270 --> 00:49:21,780
Χωρίζεται από την, ας το ονομάσουμε αυθαίρετα m, όπου m είναι ο αριθμός των συνδεδεμένων λιστών

820
00:49:21,780 --> 00:49:24,500
ότι έχουμε σε αυτό το κατακόρυφο άξονα.

821
00:49:24,500 --> 00:49:27,180
Με άλλα λόγια, αν υποθέσουμε πραγματικά μια ομοιόμορφη κατανομή των ονομάτων,

822
00:49:27,180 --> 00:49:30,150
εντελώς μη ρεαλιστικό. Υπάρχει προφανώς περισσότερο από κάποιες επιστολές από τους άλλους.

823
00:49:30,150 --> 00:49:32,580
>> Αλλά αν υποθέσουμε για την στιγμή που μια ομοιόμορφη κατανομή,

824
00:49:32,580 --> 00:49:37,350
και έχουμε n συνολικά άτομα, και μ σύνολο αλυσίδες

825
00:49:37,350 --> 00:49:40,630
έχουμε στη διάθεσή μας, τότε το μήκος καθενός από αυτές τις αλυσίδες

826
00:49:40,630 --> 00:49:44,380
αρκετά απλά πρόκειται να είναι το σύνολο, n διαιρείται με τον αριθμό των αλυσίδων.

827
00:49:44,380 --> 00:49:48,900
Έτσι, n / m. Αλλά εδώ είναι όπου μπορούμε να είμαστε όλοι μαθηματικά έξυπνος.

828
00:49:48,900 --> 00:49:53,030
m είναι μια σταθερά, επειδή υπάρχει ένα σταθερό αριθμό από αυτά.

829
00:49:53,030 --> 00:49:54,620
Θα πάμε να δηλώσει σειρά σας στην αρχή,

830
00:49:54,620 --> 00:49:58,450
και δεν είμαστε αλλάζοντας το μέγεθος του κατακόρυφου άξονα. Εξ ορισμού, το οποίο παραμένει σταθερό.

831
00:49:58,450 --> 00:50:01,220
Είναι μόνο ο οριζόντιος άξονας, να το πω έτσι, αυτό αλλάζει.

832
00:50:01,220 --> 00:50:04,760
Έτσι τεχνικώς, αυτή είναι μια σταθερά. Μέχρι τώρα, η χρονική στιγμή της εισαγωγής

833
00:50:04,760 --> 00:50:09,700
είναι λίγο πολύ O (n).

834
00:50:09,700 --> 00:50:12,410
Έτσι, αυτό δεν αισθάνονται όλοι ότι πολύ καλύτερα.

835
00:50:12,410 --> 00:50:14,940
Αλλά ποια είναι η αλήθεια εδώ; Λοιπόν, όλο αυτό το διάστημα, για εβδομάδες,

836
00:50:14,940 --> 00:50:20,640
έχουμε πει O (n ²). O (n), 2 χ ν ², - n, διαιρούμενο με 2. . . ech.

837
00:50:20,640 --> 00:50:23,580
Είναι ακριβώς n ². Αλλά τώρα, σε αυτό το μέρος του εξαμήνου,

838
00:50:23,580 --> 00:50:25,560
μπορούμε να αρχίσουμε να μιλάμε για τον πραγματικό κόσμο και πάλι.

839
00:50:25,560 --> 00:50:31,520
Και n / m είναι απολύτως ταχύτερα από ό, τι ακριβώς n μόνο.

840
00:50:31,520 --> 00:50:35,170
Αν έχετε χίλια ονόματα, και να τους χωρίσει σε πολλαπλά κάδους

841
00:50:35,170 --> 00:50:37,820
έτσι ώστε να έχετε μόνο δέκα ονόματα σε κάθε μία από αυτές τις αλυσίδες,

842
00:50:37,820 --> 00:50:41,670
απολύτως αναζήτηση δέκα πράγματα θα είναι πιο γρήγορα από χίλια πράγματα.

843
00:50:41,670 --> 00:50:43,740
Και έτσι ένα από τα επόμενα σετ πρόβλημα δεν πρόκειται να σας προκαλέσει

844
00:50:43,740 --> 00:50:46,100
να σκεφτούν ακριβώς ότι ακόμα κι αν, ναι,

845
00:50:46,100 --> 00:50:49,520
ασυμπτωτικά και μαθηματικά, αυτό εξακολουθεί να είναι ακριβώς γραμμική,

846
00:50:49,520 --> 00:50:51,700
η οποία σε γενικές γραμμές είναι χάλια, όταν προσπαθούν να βρουν τα πράγματα.

847
00:50:51,700 --> 00:50:54,530
Στην πραγματικότητα, πρόκειται να είναι ταχύτερη από ό, τι η

848
00:50:54,530 --> 00:50:56,520
λόγω αυτού του διαιρέτη.

849
00:50:56,520 --> 00:50:58,310
Και έτσι είναι και πάλι εκεί θα είναι αυτό το trade-off

850
00:50:58,310 --> 00:51:01,390
και αυτή η σύγκρουση μεταξύ θεωρίας και πραγματικότητας,

851
00:51:01,390 --> 00:51:03,550
και ένα από τα κομβία θα αρχίσει καμπής σε αυτό το σημείο στο εξάμηνο

852
00:51:03,550 --> 00:51:07,510
είναι περισσότερο από το ένα ως πραγματικότητα εμείς είδος προετοιμαστούν για το τέλος του semster,

853
00:51:07,510 --> 00:51:09,280
όπως έχουμε εισαγάγει τον κόσμο του web προγραμματισμό,

854
00:51:09,280 --> 00:51:11,530
όπου πραγματικά, η απόδοση θα μετρήσει επειδή οι χρήστες σας πρόκειται να

855
00:51:11,530 --> 00:51:14,880
αρχίσετε να αισθάνεστε και να εκτιμήσουν κακές αποφάσεις σχεδιασμού.

856
00:51:14,880 --> 00:51:19,950
>> Έτσι, πώς πηγαίνετε για την εφαρμογή ενός συνδεδεμένου - έναν πίνακα κατακερματισμού με 31 στοιχεία;

857
00:51:19,950 --> 00:51:22,600
Και το προηγούμενο παράδειγμα ήταν αυθαίρετα για γενέθλια.

858
00:51:22,600 --> 00:51:26,190
Αν κάποιος έχει γενέθλια την 1η Ιανουαρίου ή 1 Φεβρουαρίου, θα τους βάλει σε αυτό το κουβά.

859
00:51:26,190 --> 00:51:28,960
Αν είναι 2 Ιανουαρίου, 2 Φεβρουαρίου, 2 Μαρτίου, θα τους βάλει σε αυτό το κουβά.

860
00:51:28,960 --> 00:51:32,220
Γι 'αυτό ήταν 31. Πώς μπορείτε να κηρύξει πίνακα κατακερματισμού;

861
00:51:32,220 --> 00:51:37,480
Μπορεί να είναι αρκετά απλή, κόμβος πίνακα * είναι αυθαίρετο το όνομά μου για αυτό, [31].

862
00:51:37,480 --> 00:51:42,400
Αυτό μου δίνει 31 δείκτες σε κόμβους,

863
00:51:42,400 --> 00:51:45,370
και που μου δίνει τη δυνατότητα να έχουν 31 δείκτες σε συνδεδεμένες λίστες

864
00:51:45,370 --> 00:51:48,800
ακόμη και αν οι αλυσίδες είναι αρχικά NULL.

865
00:51:48,800 --> 00:51:54,860
Τι θέλω να βάλω αν θέλετε να αποθηκεύσετε "Alice", "βαρίδι", "Τσάρλι";

866
00:51:54,860 --> 00:51:57,010
Λοιπόν, θα πρέπει να τυλίξετε αυτά τα πράγματα σε μια δομή

867
00:51:57,010 --> 00:52:00,530
γιατί πρέπει να επισημάνω Alice στον Bob, να επισημάνω Charlie, και ούτω καθεξής.

868
00:52:00,530 --> 00:52:04,940
Δεν μπορούμε να έχουμε μόνο τα ονόματα από μόνα τους, γι 'αυτό θα μπορούσε να δημιουργήσει μια νέα δομή που ονομάζεται κόμβος εδώ.

869
00:52:04,940 --> 00:52:08,310
>> Τι είναι ένας πραγματικός κόμβος; Τι είναι ένας κόμβος συνδέεται σε αυτό το νέο κατάλογο;

870
00:52:08,310 --> 00:52:11,840
Το πρώτο πράγμα, που ονομάζεται λέξη, είναι για το όνομα του ατόμου.

871
00:52:11,840 --> 00:52:14,340
ΜΗΚΟΣ, προφανώς, σχετίζεται με το μέγιστο μήκος του ονόματος ενός ανθρώπου,

872
00:52:14,340 --> 00:52:18,210
ό, τι, δηλαδή, 20, 30, 40 χαρακτήρες σε τρελή γωνία περιπτώσεις,

873
00:52:18,210 --> 00:52:22,680
+1 είναι και για τι; Είναι ακριβώς το επιπλέον χαρακτήρα NULL, \ 0.

874
00:52:22,680 --> 00:52:27,410
Έτσι, αυτός ο κόμβος είναι περιτύλιγμα "κάτι" μέσα από μόνη της,

875
00:52:27,410 --> 00:52:29,640
αλλά δηλώνει επίσης ένα δείκτη που ονομάζεται επόμενο

876
00:52:29,640 --> 00:52:32,580
έτσι ώστε να μπορούμε αλυσίδα Alice στον Bob να Τσάρλι και ούτω καθεξής.

877
00:52:32,580 --> 00:52:36,700
Μπορεί να είναι NULL, αλλά δεν είναι απαραίτητο να είναι.

878
00:52:36,700 --> 00:52:40,110
Οποιεσδήποτε ερωτήσεις σχετικά με αυτούς τους πίνακες κατακερματισμού; Ναι;

879
00:52:40,110 --> 00:52:46,190
[Φοιτητών ζητώντας ερώτηση, ακατάληπτο] Μια σειρά - καλή ερώτηση.

880
00:52:46,190 --> 00:52:50,120
Γιατί είναι αυτή η λέξη char σε μια σειρά και όχι μόνο char *;

881
00:52:50,120 --> 00:52:53,830
Σε αυτό το κάπως αυθαίρετη παράδειγμα, δεν ήθελα να χρειαστεί να καταφύγουν

882
00:52:53,830 --> 00:52:56,190
στην malloc για καθένα από τα αρχικά ονόματα.

883
00:52:56,190 --> 00:52:59,530
Ήθελα να δηλώσει ένα μέγιστο ποσό μνήμης για τη σειρά

884
00:52:59,530 --> 00:53:06,020
ώστε να μπορώ να αντιγράψετε στη δομή Alice \ 0 και δεν πρέπει να ασχοληθεί με malloc και δωρεάν και τα παρόμοια.

885
00:53:06,020 --> 00:53:11,710
Αλλά θα μπορούσα να κάνω ότι αν ήθελα να είναι πιο συνειδητή χρήση του χώρου. Καλή ερώτηση.

886
00:53:11,710 --> 00:53:14,780
Ας προσπαθήσουμε να γενικεύσουμε μακριά από αυτό

887
00:53:14,780 --> 00:53:18,350
και να επικεντρωθεί το υπόλοιπο του σήμερα στις δομές δεδομένων γενικότερα

888
00:53:18,350 --> 00:53:21,170
και άλλα προβλήματα που μπορούμε να λύσουμε με τις ίδιες βασικές αρχές

889
00:53:21,170 --> 00:53:24,590
ακόμη και αν οι ίδιοι δομές δεδομένων μπορεί να διαφέρουν σε στοιχεία τους.

890
00:53:24,590 --> 00:53:27,910
>> Έτσι αποδεικνύεται στην επιστήμη των υπολογιστών, τα δέντρα είναι πολύ συχνές.

891
00:53:27,910 --> 00:53:29,760
Και μπορείτε να σκεφτείτε ένα είδος δέντρου, όπως ένα οικογενειακό δέντρο,

892
00:53:29,760 --> 00:53:31,830
όπου υπάρχει κάποια ρίζες, κάποια γυναίκα αρχηγός φυλής ή πατριάρχης,

893
00:53:31,830 --> 00:53:34,540
γιαγιά ή ο παππούς ή νωρίτερα πίσω,

894
00:53:34,540 --> 00:53:38,880
κάτω από τις οποίες είναι η μαμά και ο μπαμπάς ή διάφορες αδέλφια ή τα παρόμοια.

895
00:53:38,880 --> 00:53:42,500
Έτσι, μια δομή δέντρου έχει κόμβους και έχει παιδιά,

896
00:53:42,500 --> 00:53:45,260
συνήθως 0 ή περισσότερα παιδιά για κάθε κόμβο.

897
00:53:45,260 --> 00:53:47,320
Και μερικές από την ορολογία που βλέπετε στην εικόνα εδώ

898
00:53:47,320 --> 00:53:50,630
Είναι κάποιο από τα μικρά παιδιά ή τα εγγόνια στις άκρες

899
00:53:50,630 --> 00:53:52,330
που δεν έχουν βέλη που προέρχονται από αυτά,

900
00:53:52,330 --> 00:53:55,070
αυτά είναι τα λεγόμενα φύλλα, και ο καθένας στο εσωτερικό

901
00:53:55,070 --> 00:53:58,790
είναι ένα εσωτερικό κόμβο? μπορείτε να καλέσετε το τίποτα προς αυτή την κατεύθυνση.

902
00:53:58,790 --> 00:54:01,430
Αλλά αυτή η δομή είναι αρκετά κοινή. Αυτό και μόνο είναι λίγο αυθαίρετο.

903
00:54:01,430 --> 00:54:04,930
Έχουμε ένα παιδί στα αριστερά, έχουμε τρία παιδιά στα δεξιά,

904
00:54:04,930 --> 00:54:06,830
δύο παιδιά κάτω αριστερά.

905
00:54:06,830 --> 00:54:10,740
Έτσι μπορούμε να έχουμε διαφορετικού μεγέθους δέντρα, αλλά αν αρχίσουμε να τυποποιήσουν τα πράγματα,

906
00:54:10,740 --> 00:54:15,330
και ίσως να θυμάστε αυτό από το βίντεο του Πάτρικ σε δυαδική αναζήτηση από μια προηγούμενη σύντομη

907
00:54:15,330 --> 00:54:19,490
σε απευθείας σύνδεση, δυαδική αναζήτηση δεν πρέπει να υλοποιηθεί με μια σειρά

908
00:54:19,490 --> 00:54:21,410
ή κομμάτια χαρτιού σε έναν πίνακα.

909
00:54:21,410 --> 00:54:25,490
Ας υποθέσουμε ότι θέλετε να αποθηκεύσετε αριθμούς σας σε μια πιο εξελιγμένη δομή δεδομένων.

910
00:54:25,490 --> 00:54:27,680
Θα μπορούσατε να δημιουργήσετε ένα δέντρο σαν αυτό.

911
00:54:27,680 --> 00:54:35,290
Θα μπορούσε να έχει ένα κόμβο δηλωθεί σε C, και ότι ο κόμβος μπορεί να έχει τουλάχιστον δύο στοιχεία στο εσωτερικό του.

912
00:54:35,290 --> 00:54:39,470
Το ένα είναι ο αριθμός που θέλετε να αποθηκεύσετε, και το άλλο είναι - καλά, χρειαζόμαστε ένα ακόμη.

913
00:54:39,470 --> 00:54:41,540
Η άλλη είναι τα παιδιά του.

914
00:54:41,540 --> 00:54:45,150
Έτσι, εδώ είναι μια άλλη δομή δεδομένων. Αυτή τη φορά, ένας κόμβος ορίζεται ως αποθήκευση ενός αριθμού n

915
00:54:45,150 --> 00:54:49,060
και στη συνέχεια δίποντα? αριστερό και δεξιό παιδί.

916
00:54:49,060 --> 00:54:52,100
Και δεν είναι αυθαίρετη. Αυτό που είναι ενδιαφέρον σχετικά με αυτό το δέντρο;

917
00:54:52,100 --> 00:55:00,550
>> Ποιο είναι το σχέδιο για το πώς έχουμε αυτό που έξω ή πώς ο Patrick είναι που στο βίντεο του;

918
00:55:00,550 --> 00:55:02,790
Είναι το είδος του είναι προφανές ότι υπάρχει κάποια διαλογή συμβαίνει εδώ,

919
00:55:02,790 --> 00:55:04,460
αλλά ποιο είναι το απλό κανόνα; Ναι;

920
00:55:04,460 --> 00:55:08,350
[Απάντηση Φοιτητής, ακατάληπτο]

921
00:55:08,350 --> 00:55:12,040
Τέλεια. Αν ρίξουμε μια ματιά σε αυτό, μπορείτε να δείτε τους μικρούς αριθμούς στα αριστερά,

922
00:55:12,040 --> 00:55:14,690
μεγάλους αριθμούς στα αριστερά, αλλά είναι αλήθεια ότι για κάθε κόμβο.

923
00:55:14,690 --> 00:55:20,370
Για κάθε κόμβο, αριστερό παιδί του λιγότερο από αυτό, και το δεξί παιδί του μεγαλύτερες από αυτή.

924
00:55:20,370 --> 00:55:25,210
Αυτό σημαίνει ότι τώρα είναι αν θέλετε να αναζητήσετε αυτή τη δομή δεδομένων για, ας πούμε, με τον αριθμό 44,

925
00:55:25,210 --> 00:55:29,320
Θα πρέπει να ξεκινήσει από τη ρίζα, γιατί όπως με όλες αυτές τις πιο σύνθετες δομές δεδομένων τώρα,

926
00:55:29,320 --> 00:55:31,910
έχουμε μόνο ένα δείκτη σε ένα πράγμα, η αρχή.

927
00:55:31,910 --> 00:55:35,010
Και σε αυτή την περίπτωση, η αρχή είναι η ρίζα. Δεν είναι το αριστερό άκρο,

928
00:55:35,010 --> 00:55:39,530
είναι η ρίζα αυτής της δομής. Έτσι βλέπω εδώ είναι 55, και ψάχνω για 44.

929
00:55:39,530 --> 00:55:41,430
Ποια κατεύθυνση θέλω να πάω;

930
00:55:41,430 --> 00:55:45,680
Λοιπόν, θέλω να πάω προς τα αριστερά, διότι προφανώς, στα δεξιά θα είναι πάρα πολύ μεγάλο.

931
00:55:45,680 --> 00:55:49,050
Έτσι παρατηρούμε εδώ, είστε το είδος του εννοιολογικά κόψιμο του δέντρου στο μισό

932
00:55:49,050 --> 00:55:51,700
επειδή δεν πρόκειται ποτέ κάτω στην δεξιά πλευρά.

933
00:55:51,700 --> 00:55:55,410
Έτσι τώρα θα πάω από το 55 έως το 33. Είναι πολύ μικρός σε αριθμό.

934
00:55:55,410 --> 00:56:01,590
Ψάχνω για 44, αλλά τώρα ξέρω αν 44 είναι σε αυτό το δέντρο, μπορώ να πάω προφανώς προς τα δεξιά.

935
00:56:01,590 --> 00:56:04,460
Έτσι, και πάλι, είμαι κλάδεμα του δέντρου στο μισό.

936
00:56:04,460 --> 00:56:06,780
Είναι λίγο πολύ ίδια εννοιολογικά στον τηλεφωνικό κατάλογο.

937
00:56:06,780 --> 00:56:09,510
Είναι ίδιο με αυτό που κάναμε με τα έγγραφα σχετικά με το μαυροπίνακα,

938
00:56:09,510 --> 00:56:13,940
αλλά είναι μια πιο εξελιγμένη δομή που μας επιτρέπει να κάνουμε πραγματικότητα

939
00:56:13,940 --> 00:56:16,880
αυτό το διαίρει και βασίλευε από το σχεδιασμό του αλγορίθμου,

940
00:56:16,880 --> 00:56:19,420
και στην πραγματικότητα, διασχίζοντας μια δομή σαν αυτή - κραυγών.

941
00:56:19,420 --> 00:56:22,870
Διασχίζοντας μια δομή όπως αυτή, όπου είναι μόνο «πάει με αυτό τον τρόπο ή να πάτε με αυτόν τον τρόπο,"

942
00:56:22,870 --> 00:56:26,870
σημαίνει ότι όλες κώδικα που λυγισμένο μυαλό σας κατά την πρώτη κατά την εφαρμογή της στο τμήμα

943
00:56:26,870 --> 00:56:31,270
ή περπατώντας μέσα στο σπίτι, για δυαδική αναζήτηση, χρησιμοποιώντας αναδρομή ή επανάληψη,

944
00:56:31,270 --> 00:56:35,060
Είναι ένας πόνος στο λαιμό. Βρείτε το μεσαίο στοιχείο, στη συνέχεια, κάντε στρογγυλοποίηση προς τα πάνω ή προς τα κάτω.

945
00:56:35,060 --> 00:56:39,230
>> Υπάρχει μια ομορφιά σε αυτό, διότι μπορούμε να χρησιμοποιήσουμε τώρα αναδρομή και πάλι,

946
00:56:39,230 --> 00:56:43,760
αλλά πολύ πιο καθαρά. Πράγματι, αν είστε στο νούμερο 55 και θέλετε να βρείτε 44,

947
00:56:43,760 --> 00:56:48,450
πηγαίνετε αριστερά σε αυτή την περίπτωση, τότε τι κάνεις; Μπορείτε να εκτελέσετε την ακριβή ίδιο αλγόριθμο.

948
00:56:48,450 --> 00:56:51,560
Μπορείτε να ελέγξετε την τιμή του κόμβου, τότε πηγαίνετε αριστερά ή προς τα δεξιά.

949
00:56:51,560 --> 00:56:53,670
Στη συνέχεια θα ελέγξει την τιμή του κόμβου, πηγαίνετε αριστερά ή προς τα δεξιά.

950
00:56:53,670 --> 00:56:56,710
Αυτό ταιριάζει απόλυτα με αναδρομή.

951
00:56:56,710 --> 00:57:00,920
Έτσι, ακόμη και αν στο παρελθόν έχουμε κάνει κάποια αρκετά παραδείγματα που αφορούν αυθαίρετη αναδρομή

952
00:57:00,920 --> 00:57:03,430
αυτό δεν πρέπει να είναι αναδρομική, με stuctures δεδομένων,

953
00:57:03,430 --> 00:57:07,820
ειδικά δέντρα, είναι μια τέλεια εφαρμογή αυτής της ιδέας της λήψης ενός προβλήματος,

954
00:57:07,820 --> 00:57:12,920
συρρίκνωση, και στη συνέχεια την επίλυση τον ίδιο τύπο, αλλά μικρότερες, πρόγραμμα.

955
00:57:12,920 --> 00:57:14,590
>> Έτσι, υπάρχει μια άλλη δομή δεδομένων που μπορεί να εισάγει.

956
00:57:14,590 --> 00:57:18,760
Αυτό και μόνο είναι σχεδιασμένο με την πρώτη ματιά να δούμε αινιγματικά, αλλά αυτό είναι καταπληκτικό.

957
00:57:18,760 --> 00:57:25,090
Έτσι, αυτό είναι μια δομή δεδομένων που ονομάζεται trie, trie, η οποία κληρονόμησε από την ανάκτηση λέξη,

958
00:57:25,090 --> 00:57:30,210
η οποία δεν προφέρεται εκ νέου προσπάθεια-val, αλλά αυτό είναι που ο κόσμος αποκαλεί αυτά τα πράγματα. Προσπαθεί. Τ-r-ί-ε.

959
00:57:30,210 --> 00:57:35,190
Είναι μια δομή δέντρου κάποιου είδους, αλλά κάθε ένα από τους κόμβους σε ένα trie

960
00:57:35,190 --> 00:57:41,280
φαίνεται να είναι αυτό; Και αυτό είναι λίγο παραπλανητικό, διότι αυτό είναι το είδος του συντομογραφία.

961
00:57:41,280 --> 00:57:45,960
Αλλά μοιάζει με κάθε κόμβος σε αυτό το trie είναι στην πραγματικότητα μια σειρά.

962
00:57:45,960 --> 00:57:48,840
Και παρόλο που ο συγγραφέας αυτού του διαγράμματος δεν έχει δείξει ότι,

963
00:57:48,840 --> 00:57:54,130
σε αυτή την περίπτωση, αυτό trie είναι μια δομή δεδομένων των οποίων ο σκοπός στη ζωή είναι να αποθηκεύουν τις λέξεις

964
00:57:54,130 --> 00:57:57,330
σαν A-l-i-c-e ή Β-o-β.

965
00:57:57,330 --> 00:58:02,480
Και ο τρόπος με τον οποίο αποθηκεύει δεδομένα Alice και ο Bob και ο Τσάρλι και η Anita και ούτω καθεξής

966
00:58:02,480 --> 00:58:06,970
είναι αυτό που χρησιμοποιεί μια σειρά με την οποία να αποθηκεύσετε Αλίκη σε ένα trie,

967
00:58:06,970 --> 00:58:09,820
που ξεκινούν από τον κόμβο ρίζα που μοιάζει με έναν πίνακα,

968
00:58:09,820 --> 00:58:12,080
και είναι ήδη γραμμένο σε σημειογραφία στενογραφία.

969
00:58:12,080 --> 00:58:15,070
Ο συγγραφέας ABCDEFG παραλείπεται επειδή δεν υπήρχαν τα ονόματα με αυτό.

970
00:58:15,070 --> 00:58:19,150
Μπορούν έδειξε μόνο Μ και Ρ και Τ, αλλά στην περίπτωση αυτή,

971
00:58:19,150 --> 00:58:22,780
Ας ξεφύγουμε από την Alice και ο Bob και ο Τσάρλι σε κάποια ονόματα που είναι εδώ.

972
00:58:22,780 --> 00:58:25,670
Maxwell είναι πραγματικά σε αυτό το διάγραμμα.

973
00:58:25,670 --> 00:58:29,570
Λοιπόν, πώς έκανε το κατάστημα συγγραφέας Μ-Α-Χ-ν-ε-λ-λ;

974
00:58:29,570 --> 00:58:36,990
Αυτός ή αυτή που ξεκίνησε στον κόμβο ρίζα, και πήγε στο [M], έτσι περίπου 13, η 13η θέση του πίνακα.

975
00:58:36,990 --> 00:58:40,750
Στη συνέχεια, από εκεί, υπάρχει ένας δείκτης.

976
00:58:40,750 --> 00:58:42,760
Ένας δείκτης που οδηγεί σε έναν άλλο πίνακα.

977
00:58:42,760 --> 00:58:47,880
Από εκεί και πέρα ​​ο συγγραφέας αναπροσαρμόζονται σε αυτού του πίνακα στη θέση Α, όπως φαίνεται εκεί στην κορυφή αριστερά,

978
00:58:47,880 --> 00:58:52,250
και τότε αυτός ή αυτή ακολουθεί την δείκτη σε άλλο πίνακα,

979
00:58:52,250 --> 00:58:55,460
και πήγε στο δείκτη στη θέση X.

980
00:58:55,460 --> 00:58:59,840
Στη συνέχεια, στο επόμενο συστοιχία θέση W, E, L, L, και ούτω καθεξής,

981
00:58:59,840 --> 00:59:03,090
και, τέλος, ας προσπαθήσουμε πραγματικά να θέσει μια εικόνα σε αυτό.

982
00:59:03,090 --> 00:59:05,380
Τι κάνει ένας κόμβος μοιάζει στον κώδικα;

983
00:59:05,380 --> 00:59:11,820
Ένας κόμβος σε ένα trie περιέχει μια σειρά από δείκτες σε περισσότερους κόμβους.

984
00:59:11,820 --> 00:59:16,090
Αλλά υπάρχει επίσης πήρε να είναι κάποιο είδος του boolean τιμή, τουλάχιστον σε αυτή την εφαρμογή.

985
00:59:16,090 --> 00:59:18,770
Τυχαίνει να το ονομάσουμε is_word. Γιατί;

986
00:59:18,770 --> 00:59:22,670
Διότι όταν είστε εισαγωγή Maxwell, δεν είστε εισαγωγή

987
00:59:22,670 --> 00:59:25,300
τίποτα σε αυτή τη δομή δεδομένων.

988
00:59:25,300 --> 00:59:27,480
Δεν είστε γραπτώς Μ. Δεν είστε γράψει το X.

989
00:59:27,480 --> 00:59:30,240
Το μόνο που κάνετε είναι μετά δείκτες.

990
00:59:30,240 --> 00:59:33,360
Ο δείκτης που αντιπροσωπεύει M, τότε ο δείκτης που αντιπροσωπεύει Α,

991
00:59:33,360 --> 00:59:36,310
τότε ο δείκτης που αντιπροσωπεύει το Χ, τότε το W, E, L, L,

992
00:59:36,310 --> 00:59:41,950
αλλά αυτό που πρέπει να κάνετε στο τέλος είναι το είδος του πάει, ελέγχει, θα φθάσει σε αυτό το σημείο.

993
00:59:41,950 --> 00:59:45,560
Υπήρχε μια λέξη που τελειώνει εδώ στη δομή δεδομένων.

994
00:59:45,560 --> 00:59:48,190
>> Έτσι, ό, τι ένα trie είναι πραγματικά γεμάτη με και ο συγγραφέας επέλεξε να εκπροσωπήσει

995
00:59:48,190 --> 00:59:51,880
terminuses με αυτά τα μικρά τρίγωνα.

996
00:59:51,880 --> 00:59:56,470
Αυτό σημαίνει απλά ότι το γεγονός αυτό το τρίγωνο είναι εδώ, αυτή η boolean τιμή της πραγματικής

997
00:59:56,470 --> 00:59:59,200
σημαίνει ότι αν πάτε πίσω στο δέντρο,

998
00:59:59,200 --> 01:00:02,420
αυτό σημαίνει ότι μια λέξη είναι το όνομα Maxwell σε αυτό.

999
01:00:02,420 --> 01:00:04,870
Αλλά η λέξη foo, για παράδειγμα,

1000
01:00:04,870 --> 01:00:07,970
δεν είναι στο δέντρο, γιατί αν αρχίσω στον κόμβο ρίζα μέχρι εδώ στην κορυφή,

1001
01:00:07,970 --> 01:00:14,030
Δεν υπάρχει στ δείκτη, δεν δείκτη o, o δείκτης καμία. Foo δεν είναι ένα όνομα σε αυτό το λεξικό.

1002
01:00:14,030 --> 01:00:22,460
Αλλά αντιθέτως, θρωση, ί-υ-r-ί-ν-ζ. Και πάλι, δεν είχα αποθηκεύσει t ή u ή r ή θ ή ν ή g.

1003
01:00:22,460 --> 01:00:29,820
Αλλά έκανα κατάστημα σε αυτή τη δομή δεδομένων η αξία της αληθινής τρόπος κάτω εδώ σε αυτόν τον κόμβο - στο δέντρο

1004
01:00:29,820 --> 01:00:33,030
θέτοντας αυτή την boolean τιμή του is_word να ισχύει.

1005
01:00:33,030 --> 01:00:35,740
Έτσι, μια trie είναι το είδος της αυτή την πολύ ενδιαφέρουσα δομή μετα,

1006
01:00:35,740 --> 01:00:39,810
Όπου και αν δεν είναι πραγματικά αποθήκευση των ίδιων των λέξεων για αυτό το είδος του λεξικό.

1007
01:00:39,810 --> 01:00:45,100
Για να είμαι σαφής, είστε μόνο την αποθήκευση ναι ή όχι, υπάρχει μια λέξη που τελειώνει εδώ.

1008
01:00:45,100 --> 01:00:46,430
>> Τώρα, ποια είναι η επίπτωση;

1009
01:00:46,430 --> 01:00:51,120
Αν έχετε 150.000 λέξεις σε ένα λεξικό που προσπαθείτε να αποθηκεύσετε στη μνήμη

1010
01:00:51,120 --> 01:00:53,400
χρησιμοποιώντας κάτι σαν μια συνδεδεμένη λίστα,

1011
01:00:53,400 --> 01:00:56,870
θα έχετε την ευκαιρία να έχουν 150.000 κόμβους σε συνδεδεμένη λίστα σας.

1012
01:00:56,870 --> 01:01:00,250
Και βρίσκοντας μία από αυτές τις λέξεις θα μπορούσε να πάρει αλφαβητικά O (n) χρόνο.

1013
01:01:00,250 --> 01:01:04,370
Γραμμική χρόνο. Όμως, στην προκειμένη περίπτωση του trie,

1014
01:01:04,370 --> 01:01:09,210
τι είναι ο χρόνος εκτέλεσης της εξεύρεσης μια λέξη;

1015
01:01:09,210 --> 01:01:17,390
Βγάζει την ομορφιά εδώ είναι ότι ακόμη και αν έχετε ήδη 149.999 λέξεις σε αυτό το λεξικό,

1016
01:01:17,390 --> 01:01:20,170
όπως εφαρμόζεται με αυτή τη δομή δεδομένων,

1017
01:01:20,170 --> 01:01:25,560
πόσος χρόνος χρειάζεται για να βρουν ή να εισάγετε ένα ακόμη πρόσωπο σε αυτό, σαν την Αλίκη, Αλίκη;

1018
01:01:25,560 --> 01:01:30,640
Λοιπόν, αυτό είναι μόνο 5, ίσως 6 βήματα για το χαρακτήρα τέλους.

1019
01:01:30,640 --> 01:01:32,880
Επειδή πιθανολογείται η παρουσία άλλων ονομάτων στη δομή

1020
01:01:32,880 --> 01:01:35,340
δεν παίρνει με τον τρόπο της εισαγωγής Alice.

1021
01:01:35,340 --> 01:01:39,640
Επιπλέον, η εύρεση Alice φορά υπάρχουν 150.000 λέξεις σε αυτό το λεξικό

1022
01:01:39,640 --> 01:01:41,960
δεν πάρει το δρόμο σας για την εξεύρεση Alice καθόλου,

1023
01:01:41,960 --> 01:01:46,880
Alice επειδή είναι. . . . . εδώ, γιατί βρήκα μια boolean τιμή.

1024
01:01:46,880 --> 01:01:50,920
Και αν δεν υπάρχει boolean αληθές, τότε Alice δεν είναι σε αυτή τη δομή δεδομένων των λέξεων.

1025
01:01:50,920 --> 01:01:56,220
Με άλλα λόγια, ο χρόνος για την εξεύρεση πράγματα και εισάγοντας τα πράγματα σε αυτό το νέο

1026
01:01:56,220 --> 01:02:01,920
δομή δεδομένων του trie είναι Ξ - δεν είναι n.

1027
01:02:01,920 --> 01:02:05,730
Επειδή πιθανολογείται η παρουσία 150.000 άνθρωποι έχει καμία επίδραση στην Αλίκη, φαίνεται.

1028
01:02:05,730 --> 01:02:11,560
Ας το ονομάσουμε k, όπου k είναι το μέγιστο μήκος μιας λέξης στα αγγλικά

1029
01:02:11,560 --> 01:02:14,050
το οποίο είναι τυπικά όχι περισσότερο από 20-κάτι χαρακτήρες.

1030
01:02:14,050 --> 01:02:17,940
Έτσι k είναι μια σταθερά. Έτσι, το Άγιο Δισκοπότηρο που φαίνεται να έχουν βρει τώρα

1031
01:02:17,940 --> 01:02:26,000
είναι ότι από ένα trie, σταθερό χρόνο για ένθετα, για αναζητήσεις, για τις διαγραφές.

1032
01:02:26,000 --> 01:02:29,170
Επειδή ο αριθμός των πραγμάτων ήδη στη δομή,

1033
01:02:29,170 --> 01:02:32,600
η οποία δεν είναι ακόμα σωματικά εκεί. Και πάλι, από όπου και αν ακριβώς το είδος της απενεργοποιήσει, ναι ή όχι,

1034
01:02:32,600 --> 01:02:35,050
δεν έχει καμία επίπτωση στις μελλοντικές χρόνο λειτουργίας του.

1035
01:02:35,050 --> 01:02:37,940
>> Αλλά εκεί πήρε να είναι μια παγίδα, αλλιώς δεν θα είχαμε χάσει τόσο πολύ χρόνο

1036
01:02:37,940 --> 01:02:41,460
σε όλες τις άλλες δομές δεδομένων μόνο για να πάρει τελικά το μυστικό για ένα που είναι καταπληκτικό.

1037
01:02:41,460 --> 01:02:46,410
Λοιπόν, τι τιμή πληρώνουμε για την επίτευξη αυτού του μεγαλείου εδώ; Space.

1038
01:02:46,410 --> 01:02:49,010
Αυτό το πράγμα είναι τεράστια. Και ο λόγος για τον οποίο ο συγγραφέας

1039
01:02:49,010 --> 01:02:52,400
δεν το παρουσιάζουμε εδώ, παρατηρούμε ότι όλα αυτά τα πράγματα που μοιάζουν με πίνακες,

1040
01:02:52,400 --> 01:02:55,400
δεν είχε επιστήσει την υπόλοιπη δέντρο, το υπόλοιπο του trie,

1041
01:02:55,400 --> 01:02:58,060
επειδή απλά δεν έχουν σχέση με την ιστορία.

1042
01:02:58,060 --> 01:03:01,870
Αλλά όλες αυτές οι κόμβοι είναι πολύ ευρεία, και κάθε κόμβος στο δέντρο καταλαμβάνει

1043
01:03:01,870 --> 01:03:07,780
26 ή στην πραγματικότητα, θα μπορούσε να είναι 27 χαρακτήρες, διότι σε αυτή την περίπτωση ήμουν συμπεριλαμβανομένων χώρο για την απόστροφο

1044
01:03:07,780 --> 01:03:09,980
έτσι ώστε θα μπορούσαμε να έχουμε apostrophized λόγια.

1045
01:03:09,980 --> 01:03:14,450
Σε αυτή την περίπτωση, αυτά είναι μεγάλη συστοιχίες. Έτσι, ακόμα κι αν δεν είστε picutured,

1046
01:03:14,450 --> 01:03:18,190
αυτό καταλαμβάνει ένα τεράστιο ποσό της μνήμης RAM.

1047
01:03:18,190 --> 01:03:20,670
Ποια θα μπορούσε να είναι μια χαρά, especilly σε σύγχρονο υλικό,

1048
01:03:20,670 --> 01:03:25,650
αλλά αυτό είναι το δίλημμα. Έχουμε πάρει λιγότερο χρόνο από τις δαπάνες περισσότερο χώρο.

1049
01:03:25,650 --> 01:03:28,580
Τόσο πού είναι όλα αυτά πας;

1050
01:03:28,580 --> 01:03:32,640
Λοιπόν, ας το κάνουμε - να δούμε εδώ.

1051
01:03:32,640 --> 01:03:39,510
Ας κάνουμε ένα άλμα προς αυτόν τον τύπο εδώ.

1052
01:03:39,510 --> 01:03:43,450
>> Είτε το πιστεύετε είτε όχι, τόσο πολλή διασκέδαση όπως C έχει εδώ και αρκετό καιρό,

1053
01:03:43,450 --> 01:03:48,130
είμαστε φθάσει στο σημείο στο εξάμηνο, όπου ήρθε η ώρα για τη μετάβαση σε πιο σύγχρονα πράγματα.

1054
01:03:48,130 --> 01:03:50,950
Τα πράγματα σε ένα υψηλότερο επίπεδο. Και ακόμα κι αν για τις επόμενες δύο εβδομάδες

1055
01:03:50,950 --> 01:03:54,580
θα εξακολουθούν να μας βυθίσει στον κόσμο των δεικτών και διαχείριση μνήμης

1056
01:03:54,580 --> 01:03:57,210
για να πάρει ότι η άνεση με την οποία μπορούμε να οικοδομήσουμε την τότε,

1057
01:03:57,210 --> 01:04:01,270
τέλος το παιχνίδι είναι τελικά να εισαγάγει, κατά ειρωνεία της τύχης, όχι αυτή η γλώσσα.

1058
01:04:01,270 --> 01:04:03,330
Θα περάσουν, όπως 10 λεπτά μιλάμε για HTML.

1059
01:04:03,330 --> 01:04:05,950
Όλα HTML είναι είναι μια γλώσσα σήμανσης, και τι είναι γλώσσα σήμανσης

1060
01:04:05,950 --> 01:04:10,220
είναι αυτές οι σειρές των ανοικτών και κλειστών παρένθεση παρένθεση που λένε «κάνουν αυτό το τολμηρό»

1061
01:04:10,220 --> 01:04:12,000
«Κάντε αυτό πλάγιους», «κάνουν αυτό το κέντρο».

1062
01:04:12,000 --> 01:04:14,250
Δεν είναι όλα τα πνευματικά ενδιαφέροντα ότι, αλλά είναι εξαιρετικά χρήσιμο.

1063
01:04:14,250 --> 01:04:16,650
Και είναι σίγουρα πανταχού παρούσα αυτές τις μέρες.

1064
01:04:16,650 --> 01:04:19,450
Αλλά ό, τι είναι δυνατό για τον κόσμο του HTML, web προγραμματισμό και γενικότερα,

1065
01:04:19,450 --> 01:04:25,910
χτίζει δυναμική πράγματα? γράφοντας κώδικα σε γλώσσες όπως η PHP ή Python ή Ruby ή Java ή C #.

1066
01:04:25,910 --> 01:04:30,360
Πραγματικά, ανεξάρτητα από τη γλώσσα της επιλογής σας είναι, και παράγει δυναμικά HTML.

1067
01:04:30,360 --> 01:04:32,960
Παραγωγή κάτι που ονομάζεται CSS δυναμικά.

1068
01:04:32,960 --> 01:04:35,810
Cascading Style Sheets, που είναι επίσης σχετικά με την αισθητική.

1069
01:04:35,810 --> 01:04:41,360
Και έτσι ακόμα κι αν, σήμερα, αν πάω σε κάποιο δικτυακό τόπο, όπως το γνωστό Google.com,

1070
01:04:41,360 --> 01:04:46,100
και πάω να τη δείτε, προγραμματιστής, πηγή άποψη, που ίσως έχετε κάνει πριν,

1071
01:04:46,100 --> 01:04:49,800
αλλά θα δείτε πηγή, αυτά τα πράγματα φαίνεται μάλλον αρκετά αινιγματικός.

1072
01:04:49,800 --> 01:04:55,320
Αλλά αυτό είναι το υποκείμενο κώδικα που υλοποιεί Google.com.

1073
01:04:55,320 --> 01:04:57,940
Στο μπροστινό άκρο. Και πράγματι όλα αυτά τα πράγματα είναι αφράτο αισθητική.

1074
01:04:57,940 --> 01:05:01,740
Αυτό είναι CSS μέχρι εδώ. Αν συνεχίσετε την κύλιση κάτω θα πάρετε κάποια χρωματική κωδικοποίηση πράγματα.

1075
01:05:01,740 --> 01:05:06,890
Αυτό είναι HTML. Κώδικα της Google μοιάζει με ένα χάος, αλλά αν μπορώ πραγματικά να ανοίξει ένα διαφορετικό παράθυρο,

1076
01:05:06,890 --> 01:05:09,380
μπορούμε να δούμε κάποια δομή σε αυτό.

1077
01:05:09,380 --> 01:05:12,640
Αν ανοίξω αυτό επάνω, παρατηρούμε εδώ, είναι λίγο πιο ευανάγνωστο.

1078
01:05:12,640 --> 01:05:16,850
Εμείς πάμε να δούμε πριν από καιρό αυτήν την ετικέτα, [λέξη] είναι μια ετικέτα,

1079
01:05:16,850 --> 01:05:23,520
HTML, το κεφάλι, το σώμα, div, σενάριο, περιοχή κειμένου, διάρκεια, στο κέντρο, div.

1080
01:05:23,520 --> 01:05:26,770
Και αυτό είναι επίσης αινιγματικά ταξινομήσετε του εμφάνιση με την πρώτη ματιά,

1081
01:05:26,770 --> 01:05:30,890
αλλά όλο αυτό το χάος ακολουθεί ορισμένα σχέδια, μοτίβα και επαναλαμβανόμενη,

1082
01:05:30,890 --> 01:05:33,850
έτσι ώστε όταν θα έχουμε τα βασικά κάτω, θα είστε σε θέση να γράφουν κώδικα, όπως αυτό

1083
01:05:33,850 --> 01:05:37,550
και στη συνέχεια να χειριστείτε κώδικα όπως αυτό χρησιμοποιώντας ακόμα μια άλλη γλώσσα, που ονομάζεται το JavaScript.

1084
01:05:37,550 --> 01:05:40,440
Και το JavaScript είναι μια γλώσσα που τρέχει μέσα από ένα πρόγραμμα περιήγησης

1085
01:05:40,440 --> 01:05:44,380
σήμερα που χρησιμοποιούμε για τα μαθήματα του Χάρβαρντ, για το εργαλείο ψώνια βέβαια ότι χρησιμοποιεί χάρτες Google

1086
01:05:44,380 --> 01:05:48,660
για να σας δώσει ένα σωρό από δυναμισμό, το Facebook σας δίνει για να δείξει άμεσα ενημερώσεις κατάστασης,

1087
01:05:48,660 --> 01:05:51,430
Twitter χρησιμοποιεί για να σας δείξω tweets αμέσως.

1088
01:05:51,430 --> 01:05:53,820
Όλα αυτά θα αρχίσουν να εμπλακούμε μέσα

1089
01:05:53,820 --> 01:05:57,190
Αλλά για να φτάσουμε εκεί, πρέπει να καταλάβουμε λίγο κάτι σχετικά με το Διαδίκτυο.

1090
01:05:57,190 --> 01:06:01,130
Αυτό το κλιπ εδώ είναι μόνο ένα λεπτό μακριά, και ας υποθέσουμε ότι για τώρα αυτό είναι, στην πραγματικότητα,

1091
01:06:01,130 --> 01:06:08,380
πώς λειτουργεί το Ίντερνετ ως ένα teaser για το τι είναι έτοιμος να έρθει. Σας δίνω "Warriors of the Net».

1092
01:06:08,380 --> 01:06:14,720
>> [Αργή ♫ ♫ μουσική χορωδία]

1093
01:06:14,720 --> 01:06:20,450
[Αντρας αφηγητής] Ήρθε με ένα μήνυμα.

1094
01:06:20,450 --> 01:06:23,770
Με ένα πρωτόκολλο όλα δικά του.

1095
01:06:23,770 --> 01:06:37,270
[♫ Ταχύτερη ηλεκτρονική μουσική ♫]

1096
01:06:37,270 --> 01:06:41,330
Ήρθε σε ένα κόσμο δροσερό firewalls, routers αδιάφορος,

1097
01:06:41,330 --> 01:06:45,690
και κινδύνους πολύ χειρότερη από τον θάνατο.

1098
01:06:45,690 --> 01:06:55,400
Είναι γρήγορος. Είναι ισχυρή. Είναι το πρωτόκολλο TCP / IP, και πήρε τη διεύθυνσή σας.

1099
01:06:55,400 --> 01:06:59,250
Πολεμιστές του Net.

1100
01:06:59,250 --> 01:07:05,290
[Malan] Την επόμενη εβδομάδα, στη συνέχεια. Το Διαδίκτυο. Προγραμματισμού Web. Αυτό είναι CS50.

1101
01:07:05,290 --> 01:07:08,290
[CS50.TV]