1
00:00:00,000 --> 00:00:00,500

2
00:00:00,500 --> 00:00:11,137
[ΜΟΥΣΙΚΗ ΠΑΙΖΟΝΤΑΣ]

3
00:00:11,137 --> 00:00:12,220
DAVID J. MALAN: Εντάξει.

4
00:00:12,220 --> 00:00:13,950
Αυτό είναι CS50.

5
00:00:13,950 --> 00:00:18,560
Αυτή είναι η εβδομάδα των πέντε συνεχιστεί, και εμείς
έχουμε κάποια καλά νέα και άσχημα νέα.

6
00:00:18,560 --> 00:00:21,140
Έτσι, τα καλά νέα είναι ότι το CS50
ξεκινά την ερχόμενη Παρασκευή.

7
00:00:21,140 --> 00:00:24,430
Αν θα θέλατε να ενωθούν μαζί μας,
κατευθυνθείτε προς το συνηθισμένο URL εδώ.

8
00:00:24,430 --> 00:00:28,670
Ακόμα καλύτερα νέα, καμία διάλεξη
την ερχόμενη Δευτέρα 13 του μηνός.

9
00:00:28,670 --> 00:00:31,970
Ελαφρώς λιγότερο καλύτερα νέα,
κουίζ μηδέν είναι την επόμενη Τετάρτη.

10
00:00:31,970 --> 00:00:33,840
Περισσότερες λεπτομέρειες μπορούν να
βρέθηκαν σε αυτό το URL εδώ.

11
00:00:33,840 --> 00:00:36,340
Και κατά τη διάρκεια των επόμενων δύο ημερών
θα πρέπει να συμπληρώσετε τα κενά

12
00:00:36,340 --> 00:00:39,234
σε σχέση με τις αίθουσες
ότι θα έχουμε διατηρούνται.

13
00:00:39,234 --> 00:00:41,400
Η καλύτερη είδηση ​​είναι ότι θα υπάρχει
είναι μια ανασκόπηση πορεία σε ολόκληρη την

14
00:00:41,400 --> 00:00:43,570
συνεδρία την ερχόμενη
Δευτέρα το βράδυ.

15
00:00:43,570 --> 00:00:46,270
Μείνετε συντονισμένοι με την πορεία του
ιστοσελίδα για την τοποθεσία και τις λεπτομέρειες.

16
00:00:46,270 --> 00:00:49,290
Τμήματα, έστω και αν είναι ένα
διακοπές, θα συναντηθεί, επίσης, καθώς και.

17
00:00:49,290 --> 00:00:50,490

18
00:00:50,490 --> 00:00:52,940
Best news, διάλεξη την επόμενη Παρασκευή.

19
00:00:52,940 --> 00:00:56,220
Έτσι, αυτό είναι μια παράδοση που
έχουν, σύμφωνα με την εξεταστέα ύλη.

20
00:00:56,220 --> 00:00:58,100
Μόνο-- πρόκειται να είναι καταπληκτικό.

21
00:00:58,100 --> 00:01:02,510
Θα δείτε τα πράγματα όπως
δομών δεδομένων σταθερό χρόνο

22
00:01:02,510 --> 00:01:04,730
και πίνακες κατακερματισμού και δέντρα και προσπαθεί.

23
00:01:04,730 --> 00:01:07,150
Και θα μιλήσουμε για τα προβλήματα γενεθλίων.

24
00:01:07,150 --> 00:01:09,440
Ένα σωρό πράγματα
περιμένει την επόμενη Παρασκευή.

25
00:01:09,440 --> 00:01:11,212

26
00:01:11,212 --> 00:01:12,200
OK.

27
00:01:12,200 --> 00:01:13,190
Εν πάση περιπτώσει.

28
00:01:13,190 --> 00:01:17,080
>> Έτσι, υπενθυμίζουν ότι έχουμε πάει
εστιάζοντας σε αυτή την εικόνα για το τι είναι

29
00:01:17,080 --> 00:01:18,980
μέσα από τη μνήμη του υπολογιστή μας.

30
00:01:18,980 --> 00:01:22,875
Έτσι, μνήμη RAM ή είναι όπου τα προγράμματα
Υπάρχουν ενώ είστε τους λειτουργία.

31
00:01:22,875 --> 00:01:25,215
Αν κάνετε διπλό κλικ σε μια
εικονίδιο για να τρέξει κάποιο πρόγραμμα

32
00:01:25,215 --> 00:01:27,520
ή κάντε διπλό κλικ σε ένα
εικονίδιο για να ανοίξετε κάποιο αρχείο,

33
00:01:27,520 --> 00:01:30,430
είναι φορτωμένο από το σκληρό σας
οδηγείτε ή μονάδα στερεάς κατάστασης

34
00:01:30,430 --> 00:01:34,190
στη μνήμη RAM, Random Access Memory, όπου
ζει μέχρι να σβήσει,

35
00:01:34,190 --> 00:01:36,700
το lap-top καπάκι κλείνει,
ή να κλείσετε το πρόγραμμα.

36
00:01:36,700 --> 00:01:38,960
>> Τώρα η μνήμη, των
το οποίο πιθανότατα έχετε

37
00:01:38,960 --> 00:01:41,950
1 gigabyte αυτές τις μέρες, 2
gigabytes, ή ακόμα και πολύ περισσότερο,

38
00:01:41,950 --> 00:01:44,420
γενικά που ορίζονται
για ένα δεδομένο πρόγραμμα

39
00:01:44,420 --> 00:01:47,170
σε αυτό το είδος της ορθογώνιας
εννοιολογικό μοντέλο

40
00:01:47,170 --> 00:01:50,860
οπότε έχουμε τη στοίβα στο κάτω μέρος
και ένα σωρό άλλα πράγματα στην κορυφή.

41
00:01:50,860 --> 00:01:53,140
Το πράγμα στην κορυφή
έχουμε δει σε αυτή την εικόνα

42
00:01:53,140 --> 00:01:55,670
πριν, αλλά ποτέ δεν μίλησε για
είναι το λεγόμενο τμήμα κειμένου.

43
00:01:55,670 --> 00:01:58,419
Τμήμα κειμένου είναι μόνο ένα φανταχτερό τρόπο
πει ότι τα μηδενικά και αυτά που

44
00:01:58,419 --> 00:02:01,150
συνθέτουν την πραγματική καταρτίζονται πρόγραμμα σας.

45
00:02:01,150 --> 00:02:03,910
>> Έτσι, όταν κάνετε διπλό κλικ
Microsoft Word για Mac ή το PC σας,

46
00:02:03,910 --> 00:02:08,030
ή όταν εκτελείτε dot κάθετο Mario σε μια
Linux υπολογιστή στο παράθυρο του τερματικού σας,

47
00:02:08,030 --> 00:02:12,460
τα μηδενικά και αυτά που συνθέτουν
Word ή Mario αποθηκεύονται προσωρινά

48
00:02:12,460 --> 00:02:16,610
στη μνήμη RAM του υπολογιστή σας στο λεγόμενο
τμήμα κειμένου για ένα συγκεκριμένο πρόγραμμα.

49
00:02:16,610 --> 00:02:19,080
Κάτω από αυτό πηγαίνει προετοιμασία
και έχει προετοιμαστεί δεδομένων.

50
00:02:19,080 --> 00:02:22,655
Αυτό είναι τα πράγματα όπως καθολικές μεταβλητές,
ότι δεν έχω χρησιμοποιήσει πολλές από τις,

51
00:02:22,655 --> 00:02:24,910
αλλά σε ορισμένες περιπτώσεις έχουμε
είχε καθολικές μεταβλητές

52
00:02:24,910 --> 00:02:28,819
ή στατικά ορίζονται χορδές ότι
είναι σκληρό κωδικοποιημένες λέξεις όπως "γεια"

53
00:02:28,819 --> 00:02:31,860
που δεν λαμβάνονται από τον χρήστη
που είναι σκληρό κωδικοποιούνται στο πρόγραμμά σας.

54
00:02:31,860 --> 00:02:34,230
>> Τώρα, στο κάτω μέρος μας
έχουν το λεγόμενο στοίβα.

55
00:02:34,230 --> 00:02:37,665
Και η στοίβα, μέχρι στιγμής, έχουμε πάει
χρησιμοποιώντας για το ποια είδη σκοπούς;

56
00:02:37,665 --> 00:02:39,706

57
00:02:39,706 --> 00:02:40,997
Τι είναι η στοίβα έχει χρησιμοποιηθεί για;

58
00:02:40,997 --> 00:02:41,160
Ναι;

59
00:02:41,160 --> 00:02:42,070
>> ΚΟΙΝΟ: Λειτουργίες.

60
00:02:42,070 --> 00:02:43,320
>> DAVID J. MALAN: Για λειτουργίες;

61
00:02:43,320 --> 00:02:44,980
Με ποια έννοια για τις λειτουργίες;

62
00:02:44,980 --> 00:02:48,660
>> ΚΟΙΝΟ: Όταν καλείτε μια συνάρτηση, η
Τα επιχειρήματα που αντιγράφονται στη στοίβα.

63
00:02:48,660 --> 00:02:49,660
>> DAVID J. MALAN: Ακριβώς.

64
00:02:49,660 --> 00:02:52,650
Όταν καλείτε μια συνάρτηση, της
Τα επιχειρήματα που αντιγράφονται στη στοίβα.

65
00:02:52,650 --> 00:02:56,330
Έτσι, κάθε Χ ή Υ ή Α ή Β
ότι είστε περνώντας σε λειτουργία

66
00:02:56,330 --> 00:02:58,680
Τα προσωρινά τεθεί σε
η λεγόμενη στοίβα,

67
00:02:58,680 --> 00:03:02,000
όπως ακριβώς ένας από τους Annenberg
τραπεζαρία δίσκοι αίθουσα, και επίσης τα πράγματα

68
00:03:02,000 --> 00:03:03,190
όπως οι τοπικές μεταβλητές.

69
00:03:03,190 --> 00:03:06,290
Εάν η λειτουργία foo σας ή μετάθεσης
λειτουργία έχουν τοπικές μεταβλητές,

70
00:03:06,290 --> 00:03:08,602
όπως η θερμοκρασία, τα δύο αυτά
καταλήγουν στη στοίβα.

71
00:03:08,602 --> 00:03:11,560
Τώρα, εμείς δεν θα μιλήσουμε πολύ για
τους, αλλά αυτές οι μεταβλητές περιβάλλοντος

72
00:03:11,560 --> 00:03:15,690
στο κάτω μέρος είδαμε πριν από λίγο καιρό, όταν
Ήμουν futzing στο πληκτρολόγιο μία ημέρα

73
00:03:15,690 --> 00:03:20,050
και άρχισα πρόσβαση σε πράγματα
όπως argv 100 ή argv 1000,

74
00:03:20,050 --> 00:03:22,320
Απλά elements-- ξεχάσω
η numbers-- αλλά ότι

75
00:03:22,320 --> 00:03:24,330
δεν θα έπρεπε να είναι προσβάσιμες από εμένα.

76
00:03:24,330 --> 00:03:26,581
Αρχίσαμε να βλέπουμε κάποια
funky σύμβολα που εμφανίζονται στην οθόνη.

77
00:03:26,581 --> 00:03:28,330
Αυτοί ήταν λεγόμενες
μεταβλητές περιβάλλοντος

78
00:03:28,330 --> 00:03:32,390
όπως η παγκόσμια ρυθμίσεις για μου
πρόγραμμα ή για τον υπολογιστή μου, δεν

79
00:03:32,390 --> 00:03:37,090
άσχετα με την πρόσφατη
bug που συζητήσαμε,

80
00:03:37,090 --> 00:03:39,670
Shellshock, αυτό ήταν
μαστίζουν αρκετά υπολογιστές.

81
00:03:39,670 --> 00:03:42,960
>> Τώρα, τέλος, στη σημερινή εστίαση
θα είναι τελικά στο σωρό.

82
00:03:42,960 --> 00:03:44,864
Αυτό είναι ένα άλλο κομμάτι της μνήμης.

83
00:03:44,864 --> 00:03:47,030
Και ουσιαστικά όλα αυτά
μνήμη είναι το ίδιο πράγμα.

84
00:03:47,030 --> 00:03:48,040
Είναι το ίδιο υλικό.

85
00:03:48,040 --> 00:03:49,956
Είμαστε ακριβώς το είδος της
θεραπεία διαφορετικές ομάδες

86
00:03:49,956 --> 00:03:51,460
ψηφιολέξεων για διαφορετικούς σκοπούς.

87
00:03:51,460 --> 00:03:56,540
Ο σωρός είναι, επίσης, πρόκειται να είναι, όπου
μεταβλητές και τη μνήμη που ζητάτε

88
00:03:56,540 --> 00:03:58,810
από το λειτουργικό σύστημα
αποθηκεύεται προσωρινά.

89
00:03:58,810 --> 00:04:01,890
>> Αλλά υπάρχει το είδος του προβλήματος
εδώ, καθώς η εικόνα υποδηλώνει.

90
00:04:01,890 --> 00:04:05,261
Είμαστε είδος έχει δύο
πλοία για να συγκρουστούν.

91
00:04:05,261 --> 00:04:08,010
Επειδή όπως μπορείτε να χρησιμοποιήσετε όλο και περισσότερο
της στοίβας, και όπως βλέπουμε σήμερα

92
00:04:08,010 --> 00:04:11,800
προς τα εμπρός, όπως μπορείτε να χρησιμοποιήσετε όλο και περισσότερο από το
σωρός, σίγουρα άσχημα πράγματα μπορεί να συμβούν.

93
00:04:11,800 --> 00:04:15,054
Και πράγματι, μπορούμε να προκαλέσει η
ηθελημένα ή αθέλητα.

94
00:04:15,054 --> 00:04:16,970
Έτσι, την τελευταία δραματική στιγμή
φορά ήταν το πρόγραμμα αυτό,

95
00:04:16,970 --> 00:04:20,570
η οποία δεν εξυπηρετεί καμία λειτουργική
σκοπό εκτός από το να καταδείξει

96
00:04:20,570 --> 00:04:24,750
πώς εσείς, ως ένας κακός τύπος μπορεί να πάρει πραγματικά
επωφεληθούν από σφάλματα στο πρόγραμμα κάποιου

97
00:04:24,750 --> 00:04:28,460
και να αναλάβει ένα πρόγραμμα ή ακόμα και ένα
ολόκληρο το σύστημα υπολογιστή ή διακομιστή.

98
00:04:28,460 --> 00:04:31,660
Έτσι απλά να ρίξουμε μια ματιά για λίγο, θα
παρατηρήσετε ότι η κύρια στο κάτω μέρος

99
00:04:31,660 --> 00:04:34,510
παίρνει σε γραμμή εντολών
επιχειρήματα, όπως ανά argv.

100
00:04:34,510 --> 00:04:38,480
Και αυτό έχει μια κλήση σε μια συνάρτηση f,
ουσιαστικά ένα ανώνυμο λειτουργία που ονομάζεται

101
00:04:38,480 --> 00:04:40,250
f, και αυτό είναι που περνά στο argv [1].

102
00:04:40,250 --> 00:04:43,960
>> Έτσι, ανεξάρτητα από λέξη που πληκτρολογεί ο χρήστης στο
η γραμμή μετά το όνομα αυτού του προγράμματος,

103
00:04:43,960 --> 00:04:49,310
και, στη συνέχεια, αυτή η αυθαίρετη λειτουργία επάνω
κορυφή, στ, παίρνει σε μια σειρά, AKA char *,

104
00:04:49,310 --> 00:04:51,720
όπως έχουμε αρχίσει να συζητούν,
και αυτό που αποκαλεί απλά "bar."

105
00:04:51,720 --> 00:04:53,310
Αλλά θα μπορούσαμε να το ονομάσουμε τίποτα.

106
00:04:53,310 --> 00:04:57,470
Και τότε δηλώνει, στο εσωτερικό
της f, μια σειρά από χαρακτήρες

107
00:04:57,470 --> 00:04:59,930
ονομάζεται c-- 12 τέτοιες χαρακτήρες.

108
00:04:59,930 --> 00:05:03,580
>> Τώρα, με την ιστορία που έλεγε
Πριν από ένα χρόνο, όπου στη μνήμη

109
00:05:03,580 --> 00:05:06,720
είναι c, ή είναι αυτοί 12
χαρακτ πρόκειται να καταλήξετε;

110
00:05:06,720 --> 00:05:07,570
Ακριβώς για να είναι σαφής.

111
00:05:07,570 --> 00:05:08,070
Ναι;

112
00:05:08,070 --> 00:05:08,590
>> ΚΟΙΝΟ: Στο στοίβα.

113
00:05:08,590 --> 00:05:09,420
>> DAVID J. MALAN: Από την στοίβα.

114
00:05:09,420 --> 00:05:10,720
Έτσι c είναι μια τοπική μεταβλητή.

115
00:05:10,720 --> 00:05:14,079
Ζητάμε από 12 χαρακτήρες ή 12 bytes.

116
00:05:14,079 --> 00:05:16,120
Όσοι πρόκειται να καταλήξετε
σχετικά με το λεγόμενο στοίβα.

117
00:05:16,120 --> 00:05:18,530
Τώρα είναι επιτέλους αυτή η άλλη λειτουργία
αυτό είναι πραγματικά αρκετά χρήσιμο,

118
00:05:18,530 --> 00:05:20,571
αλλά δεν έχω χρησιμοποιήσει πραγματικά
μόνοι μας, strncopy.

119
00:05:20,571 --> 00:05:21,550

120
00:05:21,550 --> 00:05:25,200
Σημαίνει αντίγραφο εγχόρδων, αλλά
μόνο γράμματα n, n χαρακτήρες.

121
00:05:25,200 --> 00:05:31,990
Έτσι, n χαρακτήρες θα είναι
αντιγραφεί από το μπαρ σε c.

122
00:05:31,990 --> 00:05:32,980
Και πόσα;

123
00:05:32,980 --> 00:05:34,110
Το μήκος της ράβδου.

124
00:05:34,110 --> 00:05:36,330
Έτσι με άλλα λόγια, ότι
μία γραμμή, strncopy,

125
00:05:36,330 --> 00:05:39,500
πρόκειται να αντιγράψετε
αποτελεσματικά μπαρ για να γ.

126
00:05:39,500 --> 00:05:42,340
>> Τώρα, ακριβώς το είδος της πρόβλεψης
το ηθικό δίδαγμα αυτής της ιστορίας,

127
00:05:42,340 --> 00:05:44,750
τι είναι δυνητικά προβληματική εδώ;

128
00:05:44,750 --> 00:05:49,710
Ακόμα κι αν είμαστε ο έλεγχος του μήκους
των μπαρ και περνώντας σε strncopy,

129
00:05:49,710 --> 00:05:53,145
τι είναι το έντερό σας σας λέει είναι
εξακολουθούν να σπάσει σχετικά με αυτό το πρόγραμμα;

130
00:05:53,145 --> 00:05:54,410

131
00:05:54,410 --> 00:05:55,220
Ναι;

132
00:05:55,220 --> 00:05:57,491
>> ΚΟΙΝΟ: Δεν περιλαμβάνονται
δωμάτιο για το null χαρακτήρα.

133
00:05:57,491 --> 00:05:59,990
DAVID J. MALAN: Δεν περιλαμβάνονται
δωμάτιο για το null χαρακτήρα.

134
00:05:59,990 --> 00:06:02,073
Δυνητικά, σε αντίθεση
πρακτικές του παρελθόντος δεν το κάνουμε, ακόμη και

135
00:06:02,073 --> 00:06:04,810
έχουν τόσο πολύ ως συν 1
φιλοξενήσει αυτό το null χαρακτήρα.

136
00:06:04,810 --> 00:06:06,649
Αλλά αυτό είναι ακόμα χειρότερο από αυτό.

137
00:06:06,649 --> 00:06:07,940
Τι άλλο μπορούμε παραλείποντας να κάνουμε;

138
00:06:07,940 --> 00:06:08,432
Ναι;

139
00:06:08,432 --> 00:06:09,307
>> ΚΟΙΝΟ: [δεν ακούγεται]

140
00:06:09,307 --> 00:06:15,440

141
00:06:15,440 --> 00:06:16,440
DAVID J. MALAN: Perfect.

142
00:06:16,440 --> 00:06:18,490
Έχουμε σκληρά κωδικοποιημένους 12 αρκετά αυθαίρετα.

143
00:06:18,490 --> 00:06:19,497

144
00:06:19,497 --> 00:06:21,330
Αυτό δεν είναι τόσο η
πρόβλημα, αλλά το γεγονός

145
00:06:21,330 --> 00:06:25,630
ότι δεν είμαστε καν να ελέγχει εάν
το μήκος της ράβδου είναι μικρότερο από 12,

146
00:06:25,630 --> 00:06:28,530
περίπτωση κατά την οποία πρόκειται να
ασφαλές για να το θέσω στη μνήμη

147
00:06:28,530 --> 00:06:30,260
που ονομάζεται c που έχουμε διατεθεί.

148
00:06:30,260 --> 00:06:32,960
Πράγματι, εάν το μπαρ είναι σαν
20 χαρακτήρες,

149
00:06:32,960 --> 00:06:39,010
η λειτουργία αυτή φαίνεται να αντιγραφή
20 χαρακτήρες από το μπαρ σε c, έτσι

150
00:06:39,010 --> 00:06:41,310
λαμβάνοντας τουλάχιστον 8 bytes
ότι δεν πρέπει να είναι.

151
00:06:41,310 --> 00:06:42,690
Αυτό είναι το συμπέρασμα εδώ.

152
00:06:42,690 --> 00:06:44,347
>> Έτσι, με λίγα λόγια, σπασμένα πρόγραμμα.

153
00:06:44,347 --> 00:06:45,180
Δεν είναι μια τέτοια μεγάλη υπόθεση.

154
00:06:45,180 --> 00:06:46,360
Ίσως μπορείτε να πάρετε ένα σφάλμα κατάτμησης.

155
00:06:46,360 --> 00:06:47,651
Έχουμε όλοι είχαν σφάλματα στα προγράμματα.

156
00:06:47,651 --> 00:06:50,196
Όλοι μας μπορεί να έχει σφάλματα
σε προγράμματα τώρα.

157
00:06:50,196 --> 00:06:51,320
Αλλά ποια είναι η επίπτωση;

158
00:06:51,320 --> 00:06:54,390
Λοιπόν, εδώ είναι ένα μεγεθυσμένο στην έκδοση της
ότι η εικόνα της μνήμης του υπολογιστή μου.

159
00:06:54,390 --> 00:06:56,230
Αυτό είναι το κάτω μέρος της στοίβας μου.

160
00:06:56,230 --> 00:06:59,644
Και πράγματι, στο κάτω μέρος είναι ό, τι είναι
που ονομάζεται μητρική ρουτίνα στοίβα, φανταχτερό τρόπο

161
00:06:59,644 --> 00:07:00,560
του λέγοντας ότι είναι κύριος.

162
00:07:00,560 --> 00:07:03,772
Έτσι ώστε όποιος καλείται η συνάρτηση
f που μιλάμε.

163
00:07:03,772 --> 00:07:05,230
Έτσι, αυτό είναι το κάτω μέρος της στοίβας.

164
00:07:05,230 --> 00:07:06,640
Η διεύθυνση επιστροφής είναι κάτι νέο.

165
00:07:06,640 --> 00:07:08,810
Είναι πάντα εκεί,
πάντα σε αυτήν την εικόνα.

166
00:07:08,810 --> 00:07:10,440
Εμείς απλά δεν επέστησε την προσοχή σε αυτό.

167
00:07:10,440 --> 00:07:15,290
Επειδή αποδεικνύεται ο τρόπος c λειτουργεί είναι
ότι όταν μία λειτουργία καλεί άλλη,

168
00:07:15,290 --> 00:07:18,780
όχι μόνο κάνουν τα επιχειρήματα που
λειτουργία να ωθείται στη στοίβα,

169
00:07:18,780 --> 00:07:22,470
όχι μόνο οι τοπικές η λειτουργία του
μεταβλητές πάρει έσπρωξε στη στοίβα,

170
00:07:22,470 --> 00:07:26,820
κάτι που ονομάζεται διεύθυνση επιστροφής
παίρνει επίσης να θέσει στη στοίβα.

171
00:07:26,820 --> 00:07:33,330
Συγκεκριμένα, αν η κύρια κλήσεις foo, κύρια του
δική του διεύθυνση στη μνήμη, βόδι κάτι,

172
00:07:33,330 --> 00:07:38,240
αποτελεσματικά παίρνει θέσει στη στοίβα
έτσι ώστε όταν f γίνεται από την εκτέλεση του

173
00:07:38,240 --> 00:07:43,630
ξέρει πού να πηδήσει πίσω στο κείμενο
τμήμα, προκειμένου να συνεχίσει την εκτέλεση.

174
00:07:43,630 --> 00:07:47,760
>> Έτσι, αν είμαστε εδώ εννοιολογικά,
σε κεντρικό, τότε η f παίρνει ονομάζεται.

175
00:07:47,760 --> 00:07:50,200
Πώς στ ξέρω ποιος
για τον έλεγχο χέρι πίσω;

176
00:07:50,200 --> 00:07:52,020
Λοιπόν, αυτό το μικρό
τριμμένη φρυγανιά σε κόκκινο εδώ,

177
00:07:52,020 --> 00:07:54,978
ονομάζεται διεύθυνση επιστροφής, απλά
ελέγχους, τι είναι η διεύθυνση επιστροφής;

178
00:07:54,978 --> 00:07:57,039
Ω, επιτρέψτε μου να πηδήσει πίσω στο κύριο εδώ.

179
00:07:57,039 --> 00:07:59,080
Και αυτό είναι λίγο
υπεραπλούστευση,

180
00:07:59,080 --> 00:08:00,750
επειδή τα μηδενικά και μονάδες
για την κύρια είναι τεχνικώς

181
00:08:00,750 --> 00:08:01,967
εδώ στο τμήμα τεχνολογίας.

182
00:08:01,967 --> 00:08:03,800
Αλλά αυτή είναι η ιδέα. f
Απλά πρέπει να ξέρει τι

183
00:08:03,800 --> 00:08:06,680
σε περίπτωση που ο έλεγχος πηγαίνει τελικά πίσω.

184
00:08:06,680 --> 00:08:09,790
>> Αλλά ο τρόπος υπολογιστές
εδώ και καιρό που τα πράγματα

185
00:08:09,790 --> 00:08:12,320
όπως οι τοπικές μεταβλητές και
επιχειρήματα είναι σαν αυτό.

186
00:08:12,320 --> 00:08:17,180
Έτσι, στην κορυφή αυτής της εικόνας σε
το μπλε είναι το πλαίσιο στοίβας για f, έτσι ώστε όλα

187
00:08:17,180 --> 00:08:19,630
της μνήμης ότι f
Συγκεκριμένα χρησιμοποιεί.

188
00:08:19,630 --> 00:08:22,990
Έτσι, κατά συνέπεια, παρατηρούμε ότι
bar είναι σε αυτή την εικόνα.

189
00:08:22,990 --> 00:08:23,980
Bar ήταν το επιχείρημά του.

190
00:08:23,980 --> 00:08:27,240
Και υποστήριξε ότι τα επιχειρήματα για να
λειτουργίες να ωθείται στη στοίβα.

191
00:08:27,240 --> 00:08:29,910
Και c, φυσικά, είναι
Επίσης, σε αυτή την εικόνα.

192
00:08:29,910 --> 00:08:33,520
>> Και μόνο για συμβολισμούς σκοπούς,
παρατηρήσετε στο πάνω αριστερή γωνία

193
00:08:33,520 --> 00:08:37,020
είναι αυτό που θα ήταν γ υποστήριγμα 0 και
Στη συνέχεια ελαφρώς προς τα κάτω προς τα δεξιά

194
00:08:37,020 --> 00:08:38,220
είναι c βραχίονα 11.

195
00:08:38,220 --> 00:08:41,240
Έτσι, με άλλα λόγια, μπορείτε να φανταστείτε
ότι υπάρχει ένα πλέγμα από bytes

196
00:08:41,240 --> 00:08:44,380
εκεί, πρώτο εκ των οποίων είναι
πάνω αριστερά, κάτω από το οποίο

197
00:08:44,380 --> 00:08:48,360
είναι η τελευταία από τις 12 bytes.

198
00:08:48,360 --> 00:08:49,930
>> Αλλά τώρα προσπαθούν να προχωρήσετε μπροστά.

199
00:08:49,930 --> 00:08:55,580
Τι πρόκειται να συμβεί, αν περνάμε
σε μια γραμμή κορδόνι που είναι περισσότερο από c;

200
00:08:55,580 --> 00:08:59,130
Και δεν είμαστε ελέγχοντας αν
Είναι πράγματι περισσότερο από 12.

201
00:08:59,130 --> 00:09:03,146
Ποιο μέρος αυτής της εικόνας θα
να αντικατασταθούν από bytes 0, 1, 2, 3,

202
00:09:03,146 --> 00:09:07,890
dot dot dot, 11, και έπειτα
κακή, 12, 13 έως 19?

203
00:09:07,890 --> 00:09:11,820
Τι πρόκειται να συμβεί εδώ,
αν συμπεράνουμε από την παραγγελία

204
00:09:11,820 --> 00:09:14,790
ότι ο βραχίονας είναι 0 στην κορυφή
και γ βραχίονα 11 είναι είδος προς τα κάτω

205
00:09:14,790 --> 00:09:15,812
προς τα δεξιά;

206
00:09:15,812 --> 00:09:16,796
Ναι;

207
00:09:16,796 --> 00:09:19,260
>> ΚΟΙΝΟ: Λοιπόν, πρόκειται
να αντικαταστήσετε τη γραμμή char *.

208
00:09:19,260 --> 00:09:22,260
>> DAVID J. MALAN: Ναι, μοιάζει
θα πάμε να αντικαταστήσετε char * μπαρ.

209
00:09:22,260 --> 00:09:26,245
Και το χειρότερο, αν σας στείλουν σε ένα πραγματικά μεγάλο
string, θα μπορούσε να αντικαταστήσει ακόμη και τι;

210
00:09:26,245 --> 00:09:27,460

211
00:09:27,460 --> 00:09:28,570
Η διεύθυνση επιστροφής.

212
00:09:28,570 --> 00:09:31,380
Πράγμα που και πάλι, είναι ακριβώς όπως ένα
τριμμένη φρυγανιά για να πει το πρόγραμμα που

213
00:09:31,380 --> 00:09:34,060
να πάει πίσω όταν f
γίνεται να ονομάζεται.

214
00:09:34,060 --> 00:09:37,140
>> Έτσι, αυτό που συνήθως κάνουν τους κακούς
είναι αν θα έρθει σε ένα πρόγραμμα

215
00:09:37,140 --> 00:09:41,290
ότι είστε περίεργοι αν είναι
εκμεταλλεύσιμο, αμαξάκι με τέτοιο τρόπο

216
00:09:41,290 --> 00:09:43,550
ότι αυτός ή αυτή μπορεί να πάρει
πλεονέκτημα αυτού του bug,

217
00:09:43,550 --> 00:09:45,720
γενικά δεν παίρνουν
αυτό το δικαίωμα η πρώτη φορά.

218
00:09:45,720 --> 00:09:48,590
Απλώς ξεκινήστε την αποστολή, για παράδειγμα,
τυχαία strings στο πρόγραμμά σας,

219
00:09:48,590 --> 00:09:50,260
είτε στο πληκτρολόγιο,
ή ειλικρινά πιθανώς

220
00:09:50,260 --> 00:09:52,740
γράψετε ένα μικρό πρόγραμμα σε μόλις
δημιουργήσει αυτόματα χορδές,

221
00:09:52,740 --> 00:09:55,430
και να αρχίσει να χτυπάει στο πρόγραμμά σας
αποστολή σε πολλές διαφορετικές εισόδους

222
00:09:55,430 --> 00:09:56,340
σε διάφορα μήκη.

223
00:09:56,340 --> 00:09:58,990
>> Μόλις κολλάει το πρόγραμμά σας,
αυτό είναι ένα καταπληκτικό πράγμα.

224
00:09:58,990 --> 00:10:01,020
Επειδή αυτό σημαίνει ότι
ή έχει ανακαλύψει

225
00:10:01,020 --> 00:10:02,660
τι είναι πιθανόν πράγματι ένα bug.

226
00:10:02,660 --> 00:10:05,830
Και τότε μπορεί να πάρει πιο έξυπνοι
και να αρχίσει εστιάζοντας περισσότερο στενά

227
00:10:05,830 --> 00:10:07,420
σχετικά με το πώς να εκμεταλλευτούν αυτό το bug.

228
00:10:07,420 --> 00:10:11,480
Συγκεκριμένα, τι αυτός ή αυτή θα μπορούσε
κάνετε είναι να στείλετε, στην καλύτερη περίπτωση, γεια σου.

229
00:10:11,480 --> 00:10:12,210
Δεν είναι μεγάλη υπόθεση.

230
00:10:12,210 --> 00:10:14,750
Είναι μια σειρά που είναι αρκετά σύντομη.

231
00:10:14,750 --> 00:10:18,100
Αλλά ό, τι και αν αυτός ή αυτή στέλνει,
και εμείς θα το γενικεύσουμε, όπως,

232
00:10:18,100 --> 00:10:20,890
επίθεση code-- έτσι μηδενικά
και αυτά που κάνουμε τα πράγματα

233
00:10:20,890 --> 00:10:25,150
όπως rm-rf, που απομακρύνουν τα πάντα
από τον σκληρό δίσκο ή να στείλει spam

234
00:10:25,150 --> 00:10:27,000
ή με κάποιο τρόπο επιτεθεί το μηχάνημα;

235
00:10:27,000 --> 00:10:29,570
>> Έτσι, αν κάθε ένα από αυτά
γράμματα Α αντιπροσωπεύει ακριβώς,

236
00:10:29,570 --> 00:10:32,380
εννοιολογικά, επίθεση, επίθεση,
επίθεση, επίθεση, μερικές κακές κώδικα

237
00:10:32,380 --> 00:10:36,410
ότι κάποιος άλλος έγραψε, αλλά
αν το πρόσωπο αυτό είναι αρκετά έξυπνος

238
00:10:36,410 --> 00:10:40,790
όχι μόνο να περιλαμβάνει όλα
αυτών rm-RFS, αλλά επίσης

239
00:10:40,790 --> 00:10:46,100
έχουν τελευταία bytes του ή της
είναι ένας αριθμός που αντιστοιχεί

240
00:10:46,100 --> 00:10:50,540
στη διεύθυνση του του
ή το δικό της κώδικα επίθεσης

241
00:10:50,540 --> 00:10:53,820
ότι αυτός ή αυτή πέρασε σε μόλις
παρέχοντας τη στη γραμμή,

242
00:10:53,820 --> 00:10:58,760
μπορείτε να ξεγελάσουν αποτελεσματικά τον υπολογιστή
σε παρατηρήσει όταν f γίνεται η εκτέλεση,

243
00:10:58,760 --> 00:11:02,400
Ω, ήρθε η ώρα για μένα να πηδήξει
πίσω στην κόκκινη διεύθυνση επιστροφής.

244
00:11:02,400 --> 00:11:06,070
Αλλά γιατί αυτός ή αυτή έχει κάπως
επικαλύπτονται ότι η διεύθυνση επιστροφής

245
00:11:06,070 --> 00:11:09,602
με το δικό τους αριθμό,
και είναι αρκετά έξυπνος

246
00:11:09,602 --> 00:11:11,560
να έχουν διαμορφωθεί ότι
αριθμός να αναφερθώ, όπως σας

247
00:11:11,560 --> 00:11:13,740
δείτε το super top
αριστερή γωνία εκεί,

248
00:11:13,740 --> 00:11:18,020
η πραγματική διεύθυνση του υπολογιστή
μνήμη ορισμένων από κώδικα επίθεσης τους,

249
00:11:18,020 --> 00:11:21,740
κακός μπορεί να ξεγελάσουν τον υπολογιστή
σε εκτέλεση δική του κώδικα.

250
00:11:21,740 --> 00:11:23,700
>> Και ότι ο κώδικας, και πάλι, μπορεί να είναι οτιδήποτε.

251
00:11:23,700 --> 00:11:26,120
Είναι γενικά ονομάζεται
Κωδικός κέλυφος, το οποίο είναι ακριβώς

252
00:11:26,120 --> 00:11:29,030
ένας τρόπος για να πούμε ότι δεν είναι
γενικά κάτι τόσο απλό όπως rm-rf.

253
00:11:29,030 --> 00:11:32,340
Είναι πραγματικά κάτι σαν Bash,
ή ένα πραγματικό πρόγραμμα που του δίνει

254
00:11:32,340 --> 00:11:37,230
ή προγραμματικό έλεγχο της να εκτελέσει
οτιδήποτε άλλο που θέλουν να.

255
00:11:37,230 --> 00:11:40,210
Έτσι, με λίγα λόγια, όλα αυτά
απορρέει από το απλό γεγονός

256
00:11:40,210 --> 00:11:44,490
ότι αυτό το bug που εμπλέκονται όχι έλεγχο
τα όρια του πίνακα σας.

257
00:11:44,490 --> 00:11:47,250
Και επειδή ο τρόπος
υπολογιστές εργασίας είναι ότι

258
00:11:47,250 --> 00:11:49,430
χρησιμοποιούν τη στοίβα από
αποτελεσματικά, εννοιολογικά,

259
00:11:49,430 --> 00:11:54,830
πυθμένα επάνω, αλλά στη συνέχεια τα στοιχεία
ωθείτε επάνω στη στοίβα αυξηθεί πάνω προς τα κάτω,

260
00:11:54,830 --> 00:11:56,624
αυτό είναι εξαιρετικά προβληματικό.

261
00:11:56,624 --> 00:11:58,290
Τώρα, υπάρχουν τρόποι για να αντιμετωπίσετε αυτό.

262
00:11:58,290 --> 00:12:00,800
Και ειλικρινά, υπάρχουν γλώσσες
με την οποία να επιλύσετε αυτό.

263
00:12:00,800 --> 00:12:03,100
Java είναι το ανοσοποιητικό, για παράδειγμα,
για το συγκεκριμένο θέμα.

264
00:12:03,100 --> 00:12:04,110
Επειδή δεν σας δίνουν υποδείξεις.

265
00:12:04,110 --> 00:12:05,943
Δεν σας δώσει
άμεση διευθύνσεις μνήμης.

266
00:12:05,943 --> 00:12:08,560
Έτσι, με αυτή τη δύναμη που έχουμε
να αγγίξει τίποτα στη μνήμη

267
00:12:08,560 --> 00:12:11,580
που θέλετε έρχεται, ομολογουμένως, μεγάλο κίνδυνο.

268
00:12:11,580 --> 00:12:12,430
>> Έτσι κρατήσει ένα μάτι έξω.

269
00:12:12,430 --> 00:12:14,596
Εάν, ειλικρινά, κατά τους μήνες
ή χρόνια, οποτεδήποτε

270
00:12:14,596 --> 00:12:17,740
μπορείτε να διαβάσετε για κάποια εκμετάλλευση
ενός προγράμματος ή ενός εξυπηρετητή,

271
00:12:17,740 --> 00:12:22,370
αν ποτέ δείτε έναν υπαινιγμό για κάτι
σαν μια επίθεση buffer overflow,

272
00:12:22,370 --> 00:12:25,390
ή υπερχείλιση στοίβας είναι ένα άλλο είδος
της επίθεσης, παρόμοιο σε πνεύμα,

273
00:12:25,390 --> 00:12:28,770
όσο εμπνέει την ιστοσελίδα του
όνομα, αν το ξέρετε,

274
00:12:28,770 --> 00:12:33,170
είναι όλα μιλάμε για απλά
ξεχειλίζει το μέγεθος κάποιου χαρακτήρα

275
00:12:33,170 --> 00:12:36,200
σειρά ή κάποια σειρά γενικότερα.

276
00:12:36,200 --> 00:12:38,822
Οποιεσδήποτε ερωτήσεις, στη συνέχεια, για αυτό;

277
00:12:38,822 --> 00:12:39,780
Μην το δοκιμάσετε στο σπίτι.

278
00:12:39,780 --> 00:12:41,620

279
00:12:41,620 --> 00:12:42,300
>> Εντάξει.

280
00:12:42,300 --> 00:12:47,270
Έτσι malloc μέχρι στιγμής υπήρξε νέα μας
φίλος σε ότι μπορούμε να εκχωρήσει μνήμη

281
00:12:47,270 --> 00:12:50,540
ότι εμείς δεν πρέπει απαραίτητα να γνωρίζουν σε
εκ των προτέρων ότι θέλουμε έτσι δεν έχουμε

282
00:12:50,540 --> 00:12:52,920
στο σκληρό κώδικα σε μας
αριθμοί πρόγραμμα όπως το 12.

283
00:12:52,920 --> 00:12:55,550
Μόλις ο χρήστης μας λέει πόσο
τα δεδομένα που θέλει να εισάγει,

284
00:12:55,550 --> 00:12:58,000
μπορούμε να malloc ότι το μέγεθος της μνήμης.

285
00:12:58,000 --> 00:13:01,484
>> Έτσι malloc αποδεικνύεται, με το
βαθμό που έχουμε ήδη το χρησιμοποιεί,

286
00:13:01,484 --> 00:13:03,900
ρητά την τελευταία φορά, και στη συνέχεια,
έχετε παιδιά έχουν χρησιμοποιήσει

287
00:13:03,900 --> 00:13:08,160
για GetString εν αγνοία τους για
αρκετές εβδομάδες, όλοι της μνήμης malloc του

288
00:13:08,160 --> 00:13:09,820
προέρχεται από τη λεγόμενη σωρού.

289
00:13:09,820 --> 00:13:13,852
Και αυτός είναι ο λόγος GetString, για παράδειγμα,
μπορεί να εκχωρήσει μνήμη δυναμικά

290
00:13:13,852 --> 00:13:16,060
χωρίς να γνωρίζουν τι είστε
πρόκειται να πληκτρολογήσετε εκ των προτέρων,

291
00:13:16,060 --> 00:13:21,520
θα παραδώσει ένα δείκτη σε αυτή τη μνήμη,
και ότι η μνήμη είναι ακόμα δικός σας να κρατήσει,

292
00:13:21,520 --> 00:13:24,080
ακόμη και μετά την GetString αποδόσεις.

293
00:13:24,080 --> 00:13:27,450
Επειδή η ανάκληση μετά από όλα ότι η
στοίβα συνεχώς ανεβαίνει και προς τα κάτω,

294
00:13:27,450 --> 00:13:27,950
πάνω και κάτω.

295
00:13:27,950 --> 00:13:30,230
Και μόλις πηγαίνει
προς τα κάτω, αυτό σημαίνει ότι κάθε μνήμη

296
00:13:30,230 --> 00:13:33,030
Αυτή η λειτουργία χρησιμοποιείται πρέπει να
δεν πρέπει να χρησιμοποιείται από οποιονδήποτε άλλον.

297
00:13:33,030 --> 00:13:34,570
Είναι αξίες σκουπίδια τώρα.

298
00:13:34,570 --> 00:13:36,120
>> Αλλά ο σωρός είναι εδώ.

299
00:13:36,120 --> 00:13:39,360
Και αυτό είναι καλό για την malloc είναι ότι
όταν malloc διαθέτει μνήμη μέχρι εδώ,

300
00:13:39,360 --> 00:13:42,070
δεν έχει επηρεαστεί, για το
μεγαλύτερο μέρος, από τη στοίβα.

301
00:13:42,070 --> 00:13:46,000
Και έτσι κάθε λειτουργία μπορεί να έχει πρόσβαση
μνήμης που έχει malloc'd,

302
00:13:46,000 --> 00:13:49,120
ακόμη και από μια συνάρτηση, όπως GetString,
ακόμη και μετά από αυτό επιστρέφεται.

303
00:13:49,120 --> 00:13:51,700
>> Τώρα, το αντίστροφο της malloc είναι δωρεάν.

304
00:13:51,700 --> 00:13:53,900
Και πράγματι, ο κανόνας σας
πρέπει να αρχίσει την έγκριση

305
00:13:53,900 --> 00:13:58,950
είναι κάποια, οποιαδήποτε, κάθε φορά που χρησιμοποιείτε malloc
θα πρέπει να τον εαυτό σας να χρησιμοποιήσετε δωρεάν, τελικά,

306
00:13:58,950 --> 00:14:00,280
σε αυτό το ίδιο δείκτη.

307
00:14:00,280 --> 00:14:03,289
Όλο αυτό το διάστημα έχουμε γράψει
buggy, προβληματικό κώδικα, για πολλούς λόγους.

308
00:14:03,289 --> 00:14:05,580
Αλλά ένα από τα οποία έχει
χρησιμοποιώντας τη βιβλιοθήκη CS50, η οποία

309
00:14:05,580 --> 00:14:09,010
το ίδιο είναι σκόπιμα
buggy, είναι διαρροών μνήμης.

310
00:14:09,010 --> 00:14:11,410
Κάθε φορά που έχετε ονομάσει GetString
κατά τη διάρκεια των τελευταίων εβδομάδων

311
00:14:11,410 --> 00:14:13,870
ζητάμε από το λειτουργικό
συστήματος, το Linux, για τη μνήμη.

312
00:14:13,870 --> 00:14:15,780
Και έχετε ποτέ τη στιγμή που θα δοθεί πίσω.

313
00:14:15,780 --> 00:14:17,730
Και αυτό δεν είναι, σε
πρακτική, ένα καλό πράγμα.

314
00:14:17,730 --> 00:14:20,330
>> Και Valgrind, ένα από τα
εργαλείων που έχουν εισαχθεί στο Pset 4,

315
00:14:20,330 --> 00:14:22,900
είναι όλα για να σας βοηθήσει να
τώρα βρείτε σφάλματα όπως αυτό.

316
00:14:22,900 --> 00:14:27,060
Αλλά ευτυχώς για Pset 4 δεν χρειάζεται
να χρησιμοποιούν τη βιβλιοθήκη CS50 ή GetString.

317
00:14:27,060 --> 00:14:31,220
Έτσι, τυχόν σφάλματα που σχετίζονται με τη μνήμη είναι
τελικά, θα είναι δική σας.

318
00:14:31,220 --> 00:14:34,060
>> Έτσι malloc είναι κάτι περισσότερο από
βολικό για το σκοπό αυτό.

319
00:14:34,060 --> 00:14:37,420
Μπορούμε πραγματικά να λύσει τώρα
διαφορετικής φύσεως προβλήματα,

320
00:14:37,420 --> 00:14:41,640
και ουσιαστικά να λύσει τα προβλήματα περισσότερο
αποτελεσματικά σύμφωνα με την υπόσχεση εβδομάδα μηδενικά.

321
00:14:41,640 --> 00:14:44,720
Μέχρι στιγμής αυτό είναι το πιο σέξι
δομή των δεδομένων που είχαμε.

322
00:14:44,720 --> 00:14:47,804
Και από τη δομή των δεδομένων απλά εννοώ
ένας τρόπος θεώρησης της μνήμης

323
00:14:47,804 --> 00:14:50,720
με τρόπο που να πηγαίνει πέρα ​​από την απλή λέγοντας,
αυτό είναι ένα int, αυτό είναι ένα char.

324
00:14:50,720 --> 00:14:52,930
Μπορούμε να αρχίσουμε με τα πράγματα σύμπλεγμα μαζί.

325
00:14:52,930 --> 00:14:54,460
>> Έτσι, μια σειρά έμοιαζε με αυτό.

326
00:14:54,460 --> 00:14:57,270
Και αυτό ήταν το κλειδί σε περίπου ένα
array είναι ότι σας δίνει

327
00:14:57,270 --> 00:14:59,724
back-to-back κομμάτια της
μνήμη, καθεμία από τις οποίες

328
00:14:59,724 --> 00:15:02,765
πρόκειται να είναι του ίδιου τύπου, int,
int, int, int, ή char, char, char,

329
00:15:02,765 --> 00:15:03,330
char.

330
00:15:03,330 --> 00:15:04,496
Αλλά υπάρχουν μερικά μειονεκτήματα.

331
00:15:04,496 --> 00:15:06,570
Αυτό, για παράδειγμα, είναι
μια σειρά από έξι μέγεθος.

332
00:15:06,570 --> 00:15:10,650
Ας υποθέσουμε ότι μπορείτε να συμπληρώσετε αυτό το array με έξι
αριθμών και, στη συνέχεια, για οποιουσδήποτε λόγους,

333
00:15:10,650 --> 00:15:13,187
χρήστη σας θέλει να δώσει
έχετε ένα έβδομο αριθμό.

334
00:15:13,187 --> 00:15:14,020
Πού έχεις βάλει;

335
00:15:14,020 --> 00:15:15,490

336
00:15:15,490 --> 00:15:18,990
>> Ποια είναι η λύση, αν έχετε
δημιουργήσει μια σειρά στη στοίβα,

337
00:15:18,990 --> 00:15:22,030
για παράδειγμα, ακριβώς με την εβδομάδα
δύο συμβολισμός που εισήγαγε,

338
00:15:22,030 --> 00:15:23,730
από αγκύλες με έναν αριθμό μέσα;

339
00:15:23,730 --> 00:15:25,160

340
00:15:25,160 --> 00:15:27,260
Λοιπόν, έχετε έξι
αριθμούς σε αυτά τα πλαίσια.

341
00:15:27,260 --> 00:15:28,530
Τι θα ήταν το ένστικτό σας είναι;

342
00:15:28,530 --> 00:15:29,973
Που θα θέλετε να το βάλετε;

343
00:15:29,973 --> 00:15:30,860
>> ΚΟΙΝΟ: [δεν ακούγεται]

344
00:15:30,860 --> 00:15:31,315
>> DAVID J. MALAN: Συγγνώμη;

345
00:15:31,315 --> 00:15:32,380
>> ΚΟΙΝΟ: Βάλτε το στην άκρη.

346
00:15:32,380 --> 00:15:33,796
>> DAVID J. MALAN: Βάλτε το στην άκρη.

347
00:15:33,796 --> 00:15:35,880
Έτσι ακριβώς πάνω προς τα δεξιά,
έξω από το παράθυρο.

348
00:15:35,880 --> 00:15:38,710
Ποια θα ήταν ωραίο, αλλά
Αποδεικνύεται ότι δεν μπορεί να το κάνει.

349
00:15:38,710 --> 00:15:41,350
Διότι, αν δεν έχετε ζητήσει
γι 'αυτό το κομμάτι της μνήμης,

350
00:15:41,350 --> 00:15:44,490
θα μπορούσε να είναι τυχαίο ότι αυτή η
χρησιμοποιείται από κάποια άλλη μεταβλητή

351
00:15:44,490 --> 00:15:45,030
συνολικά.

352
00:15:45,030 --> 00:15:49,210
Σκεφτείτε μια εβδομάδα ή έτσι, όταν εμείς που
τα ονόματα Zamyla και Davin και Gabe του

353
00:15:49,210 --> 00:15:49,930
στη μνήμη.

354
00:15:49,930 --> 00:15:51,638
Ήταν κυριολεκτικά
πλάτη με πλάτη με πλάτη.

355
00:15:51,638 --> 00:15:53,550
Έτσι, δεν μπορούμε απαραιτήτως
εμπιστοσύνη ότι όποιες και αν είναι

356
00:15:53,550 --> 00:15:55,800
εδώ είναι διαθέσιμα για να τα χρησιμοποιήσετε.

357
00:15:55,800 --> 00:15:56,990
>> Λοιπόν, τι άλλο θα μπορούσε να σας κάνει;

358
00:15:56,990 --> 00:16:00,282
Λοιπόν, μόλις συνειδητοποιούν σας
Χρειάζεται μια σειρά μεγέθους επτά,

359
00:16:00,282 --> 00:16:02,490
μπορείτε να δημιουργήσετε μόνο ένα
σειρά μεγέθους επτά στη συνέχεια χρησιμοποιήστε

360
00:16:02,490 --> 00:16:05,950
ένα βρόχο ή ένα βρόχο while,
αντιγράψετε στο νέο πίνακα,

361
00:16:05,950 --> 00:16:09,680
και, στη συνέχεια, κατά κάποιον τρόπο απλά να απαλλαγούμε από
αυτή η σειρά ή απλά να σταματήσουν να χρησιμοποιούν αυτό.

362
00:16:09,680 --> 00:16:12,130
Αλλά αυτό δεν είναι ιδιαίτερα αποτελεσματική.

363
00:16:12,130 --> 00:16:15,340
Εν ολίγοις, συστοιχίες μην αφήνετε
μπορείτε να αλλάξετε το μέγεθος δυναμικά.

364
00:16:15,340 --> 00:16:17,900
>> Έτσι, από τη μία πλευρά έχετε
τυχαίας προσπέλασης, το οποίο είναι εκπληκτικό.

365
00:16:17,900 --> 00:16:20,108
Επειδή αυτό μας επιτρέπει να κάνουμε τα πράγματα
όπως το διαίρει και βασίλευε,

366
00:16:20,108 --> 00:16:23,100
δυαδική αναζήτηση, όλα από τα οποία έχουμε
μίλησε για την οθόνη εδώ.

367
00:16:23,100 --> 00:16:24,950
Αλλά θα ζωγραφίσει τον εαυτό σας σε μια γωνία.

368
00:16:24,950 --> 00:16:27,810
Μόλις πατήσετε
το τέλος του πίνακα σας,

369
00:16:27,810 --> 00:16:29,980
θα πρέπει να κάνουμε μια πολύ
δαπανηρή λειτουργία

370
00:16:29,980 --> 00:16:33,910
ή να γράψετε ένα σωρό κώδικα
τώρα ασχολούνται με αυτό το πρόβλημα.

371
00:16:33,910 --> 00:16:36,680
>> Τι κι αν, αντί είχαμε
κάτι που ονομάζεται μια λίστα,

372
00:16:36,680 --> 00:16:38,820
ή μια λίστα που συνδέεται ειδικότερα;

373
00:16:38,820 --> 00:16:41,930
Τι εάν αντί να έχουμε
ορθογώνια πλάτη με πλάτη με πλάτη,

374
00:16:41,930 --> 00:16:45,730
έχουμε ορθογώνια που αφήνουν λίγο
bit του δωματίου κουνάω μεταξύ τους;

375
00:16:45,730 --> 00:16:49,670
Και παρόλο που έχω σχεδιάσει αυτό
εικόνα ή διασκευασμένη αυτή την εικόνα

376
00:16:49,670 --> 00:16:54,696
από ένα από τα κείμενα εδώ για να ξαναγυρίσει
πλάτη με πλάτη πολύ ομαλή, στην πραγματικότητα,

377
00:16:54,696 --> 00:16:56,820
ένα από αυτά τα ορθογώνια
θα μπορούσε να είναι εδώ στη μνήμη.

378
00:16:56,820 --> 00:16:58,028
Ένας από αυτούς θα μπορούσε να είναι εδώ.

379
00:16:58,028 --> 00:17:00,420
Ένας από αυτούς θα μπορούσε να είναι εδώ,
πάνω από εδώ, και ούτω καθεξής.

380
00:17:00,420 --> 00:17:02,910
>> Αλλά τι θα γινόταν αν επέστησε,
στην περίπτωση αυτή, τα βέλη

381
00:17:02,910 --> 00:17:05,650
ότι κατά κάποιο τρόπο συνδέουν αυτά
ορθογώνια μεταξύ τους;

382
00:17:05,650 --> 00:17:08,170
Πράγματι, έχουμε δει μια τεχνική
ενσάρκωση της ένα βέλος.

383
00:17:08,170 --> 00:17:09,839

384
00:17:09,839 --> 00:17:13,710
Τι έχουμε χρησιμοποιήθηκαν σε πρόσφατες
ημέρες ότι, κάτω από την κουκούλα,

385
00:17:13,710 --> 00:17:15,210
είναι αντιπροσωπευτική της ένα βέλος;

386
00:17:15,210 --> 00:17:16,290

387
00:17:16,290 --> 00:17:17,349
Ένας δείκτης, σωστά;

388
00:17:17,349 --> 00:17:19,780
>> Τι κι αν, αντί της
ακριβώς την αποθήκευση των αριθμών,

389
00:17:19,780 --> 00:17:23,130
όπως 9, 17, 22, 26, 34,
τι θα γινόταν αν δεν αποθηκεύονται

390
00:17:23,130 --> 00:17:27,079
μόνο ένας αριθμός, αλλά ένας δείκτης
δίπλα σε κάθε τέτοιο αριθμό;

391
00:17:27,079 --> 00:17:30,690
Έτσι, τόσο πολύ όπως θα περάστε ένα
βελόνα μέσα από ένα σωρό από ύφασμα,

392
00:17:30,690 --> 00:17:32,950
κάπως δέσιμο πράγματα
μαζί, παρομοίως μπορεί

393
00:17:32,950 --> 00:17:35,550
εμείς με δείκτες, όπως
ενσαρκώνεται από βέλη εδώ,

394
00:17:35,550 --> 00:17:38,550
το είδος της ύφανσης μαζί
αυτά τα ορθογώνια παραλληλόγραμμα

395
00:17:38,550 --> 00:17:41,780
με την αποτελεσματική χρήση ενός δείκτη
δίπλα σε κάθε αριθμό στον οποίο

396
00:17:41,780 --> 00:17:46,065
επισημαίνει σε κάποιο επόμενο αριθμό, ότι
επισημαίνει, με τη σειρά τους, ορισμένες επόμενο αριθμό;

397
00:17:46,065 --> 00:17:47,940
Έτσι, με άλλα λόγια, ό, τι
αν πραγματικά θέλαμε

398
00:17:47,940 --> 00:17:49,820
να εφαρμόσει κάτι σαν αυτό;

399
00:17:49,820 --> 00:17:53,610
Καλά Δυστυχώς, αυτές ορθογώνια,
τουλάχιστον το ένα με 9, 17, 22,

400
00:17:53,610 --> 00:17:57,040
και ούτω καθεξής, αυτά δεν είναι πλέον
ωραίο πλατείες με μόνο αριθμούς.

401
00:17:57,040 --> 00:17:59,960
Το κάτω μέρος, ορθογώνιο
κάτω 9, για παράδειγμα,

402
00:17:59,960 --> 00:18:04,330
αντιπροσωπεύει αυτό που θα πρέπει να
είναι ένας δείκτης, 32 bits.

403
00:18:04,330 --> 00:18:09,460
Τώρα, δεν είμαι ακόμα γνωρίζουν κάθε τύπο δεδομένων
σε C που σας δίνει όχι μόνο μια int

404
00:18:09,460 --> 00:18:11,630
αλλά ένας δείκτης εντελώς.

405
00:18:11,630 --> 00:18:15,020
>> Έτσι ποια είναι η λύση, αν θέλουμε
να εφεύρουν τη δική μας απάντηση σε αυτό;

406
00:18:15,020 --> 00:18:15,760
Ναι;

407
00:18:15,760 --> 00:18:16,640
>> ΚΟΙΝΟ: [δεν ακούγεται]

408
00:18:16,640 --> 00:18:17,360
>> DAVID J. MALAN: Τι είναι αυτό;

409
00:18:17,360 --> 00:18:17,880
>> ΚΟΙΝΟ: Νέα δομή.

410
00:18:17,880 --> 00:18:19,590
>> DAVID J. MALAN: Ναι, οπότε γιατί
Δεν έχουμε δημιουργήσει μια νέα δομή,

411
00:18:19,590 --> 00:18:20,920
ή σε C, ένα struct;

412
00:18:20,920 --> 00:18:25,990
Έχουμε δει structs πριν, αν εν συντομία,
όπου ασχοληθήκαμε με μια δομή φοιτητή

413
00:18:25,990 --> 00:18:27,780
όπως αυτός, ο οποίος είχε ένα όνομα και ένα σπίτι.

414
00:18:27,780 --> 00:18:31,980
Σε Pset 3 ξεμπλοκάρισμα χρησιμοποιήσατε μια ολόκληρη
μάτσο structs-- GRect και GOvals

415
00:18:31,980 --> 00:18:34,810
ότι Στάνφορντ που δημιουργήθηκε για να
cluster πληροφορίες μαζί.

416
00:18:34,810 --> 00:18:38,580
Έτσι, ό, τι και αν πάρουμε την ίδια την ιδέα της
οι λέξεις-κλειδιά "typedef" και "struct"

417
00:18:38,580 --> 00:18:42,890
και στη συνέχεια κάποιες φοιτητή-ειδικά πράγματα,
και να εξελιχθεί αυτή στο εξής:

418
00:18:42,890 --> 00:18:46,210
typedef struct node-- και ο κόμβος είναι
μόνο μια πολύ γενική επιστήμη των υπολογιστών

419
00:18:46,210 --> 00:18:49,980
όρος για κάτι σε μια δομή δεδομένων,
ένα δοχείο σε μια δομή δεδομένων.

420
00:18:49,980 --> 00:18:53,900
Ένας κόμβος που ισχυρίζονται πρόκειται να έχουν
ένα int n, εντελώς απλή,

421
00:18:53,900 --> 00:18:58,810
και στη συνέχεια λίγο πιο κρυφά,
αυτή η δεύτερη γραμμή, struct node * επόμενο.

422
00:18:58,810 --> 00:19:01,300
Αλλά σε λιγότερο τεχνικούς όρους,
τι είναι η δεύτερη γραμμή

423
00:19:01,300 --> 00:19:02,980
του κώδικα μέσα στα άγκιστρα;

424
00:19:02,980 --> 00:19:03,737
Ναι;

425
00:19:03,737 --> 00:19:04,851
>> ΚΟΙΝΟ: [δεν ακούγεται]

426
00:19:04,851 --> 00:19:06,600
DAVID J. MALAN: A
δείκτη σε άλλο κόμβο.

427
00:19:06,600 --> 00:19:09,910
Έτσι, κατά γενική ομολογία, την σύνταξη λίγο αινιγματικό.

428
00:19:09,910 --> 00:19:13,250
Αλλά αν το διαβάσετε κυριολεκτικά,
επόμενο είναι το όνομα μιας μεταβλητής.

429
00:19:13,250 --> 00:19:14,410
Τι είναι ο τύπος δεδομένων του;

430
00:19:14,410 --> 00:19:18,206
Είναι λίγο φλύαρο αυτή τη φορά,
αλλά είναι του τύπου struct node *.

431
00:19:18,206 --> 00:19:22,960
Κάθε φορά που έχουμε δει κάτι αστέρων, ότι
σημαίνει ότι είναι ένας δείκτης για το συγκεκριμένο τύπο δεδομένων.

432
00:19:22,960 --> 00:19:26,810
Μέχρι την επόμενη είναι προφανώς ένα
δείκτης σε μια struct node.

433
00:19:26,810 --> 00:19:28,310
>> Τώρα, τι είναι ένας κόμβος struct;

434
00:19:28,310 --> 00:19:31,044
Λοιπόν, παρατηρήσετε θα δείτε εκείνες
ίδιες λέξεις στην πάνω δεξιά.

435
00:19:31,044 --> 00:19:33,960
Και πράγματι, θα δείτε επίσης τη λέξη
"Κόμβος" εδώ κάτω στο κάτω μέρος αριστερά.

436
00:19:33,960 --> 00:19:35,640
Και αυτό είναι στην πραγματικότητα μια ευκολία.

437
00:19:35,640 --> 00:19:39,930
Παρατηρήστε ότι στον ορισμό των φοιτητών μας
υπάρχει η λέξη "σπουδαστής" μόνο μία φορά.

438
00:19:39,930 --> 00:19:42,510
Και αυτό γιατί ένα μαθητή
αντικείμενο δεν ήταν αυτοαναφορική.

439
00:19:42,510 --> 00:19:45,340
Δεν υπάρχει τίποτα στο εσωτερικό του φοιτητή
ότι πρέπει να επισημάνω ένα άλλο μαθητή,

440
00:19:45,340 --> 00:19:45,610
PerSay.

441
00:19:45,610 --> 00:19:47,630
Αυτό θα είναι το είδος της
παράξενο στον πραγματικό κόσμο.

442
00:19:47,630 --> 00:19:50,880
>> Αλλά με ένα κόμβο σε ένα συνδεδεμένο
κατάλογος, γιατί θέλουμε έναν κόμβο

443
00:19:50,880 --> 00:19:53,970
να είναι αναφορική με παρόμοιο αντικείμενο.

444
00:19:53,970 --> 00:19:57,900
Και έτσι παρατηρήσετε την αλλαγή εδώ δεν είναι
ακριβώς ό, τι είναι μέσα στις αγκύλες.

445
00:19:57,900 --> 00:20:00,800
Αλλά προσθέτουμε τη λέξη "κόμβο"
στην κορυφή, καθώς

446
00:20:00,800 --> 00:20:02,930
προσθήκη του στο κάτω μέρος
αντί του "μαθητή".

447
00:20:02,930 --> 00:20:06,000
Και αυτό είναι μόνο μια τεχνική λεπτομέρεια
έτσι ώστε, και πάλι, η δομή των δεδομένων σας

448
00:20:06,000 --> 00:20:11,380
μπορεί να είναι αυτοαναφορική, έτσι ώστε ένα
κόμβος μπορεί να δείξει ένα άλλο τέτοιο κόμβο.

449
00:20:11,380 --> 00:20:13,840
>> Έτσι τι είναι αυτό τελικά
θα σημαίνει για μας;

450
00:20:13,840 --> 00:20:17,560
Λοιπόν, το ένα, αυτά τα πράγματα στο εσωτερικό
είναι τα περιεχόμενα του κόμβου μας.

451
00:20:17,560 --> 00:20:19,360
Αυτό το πράγμα μέχρι εδώ,
πάνω δεξιά, είναι ακριβώς έτσι

452
00:20:19,360 --> 00:20:20,860
ότι, και πάλι, μπορούμε να αναφερθούμε στους εαυτούς μας.

453
00:20:20,860 --> 00:20:23,401
Και τότε ο εξόχως απόκεντρες πράγματα,
ακόμα κι αν ο κόμβος είναι ένας νέος όρος,

454
00:20:23,401 --> 00:20:25,500
ίσως, είναι ακόμα η
ίδια ως φοιτητής και τι

455
00:20:25,500 --> 00:20:27,520
ήταν κάτω από την κουκούλα στο SPL.

456
00:20:27,520 --> 00:20:31,095
>> Έτσι, αν τώρα ήθελε να ξεκινήσει
την εφαρμογή της παρούσας συνδεδεμένη λίστα,

457
00:20:31,095 --> 00:20:33,220
πώς θα μπορούσαμε να μεταφράσει
κάτι σαν αυτό να κωδικοποιήσει;

458
00:20:33,220 --> 00:20:35,350
Λοιπόν, ας δούμε ένα
παράδειγμα ένα πρόγραμμα το οποίο

459
00:20:35,350 --> 00:20:36,840
στην πραγματικότητα χρησιμοποιεί μια συνδεδεμένη λίστα.

460
00:20:36,840 --> 00:20:40,870
Μεταξύ κώδικα της διανομής του σήμερα
είναι ένα πρόγραμμα που ονομάζεται Λίστα Zero.

461
00:20:40,870 --> 00:20:44,980
Και αν μπορώ να εκτελέσω αυτό δημιούργησα ένα super
απλό GUI, Graphical User Interface,

462
00:20:44,980 --> 00:20:46,460
αλλά είναι πραγματικά ακριβώς printf.

463
00:20:46,460 --> 00:20:50,930
Και τώρα έχω δώσει τον εαυτό μου μερικά μενού
options-- Διαγραφή, Εισαγωγή, Αναζήτηση,

464
00:20:50,930 --> 00:20:51,750
και Traverse.

465
00:20:51,750 --> 00:20:52,630
Και Quit.

466
00:20:52,630 --> 00:20:55,970
Αυτά είναι μόνο κοινές λειτουργίες σε ένα
δομή δεδομένων γνωστή ως λίστα σύνδεσμο.

467
00:20:55,970 --> 00:20:58,409
>> Τώρα, Διαγραφή πρόκειται να
διαγράψετε έναν αριθμό από τη λίστα.

468
00:20:58,409 --> 00:21:00,200
Εισάγετε πρόκειται να προσθέσετε
ένας αριθμός στη λίστα.

469
00:21:00,200 --> 00:21:02,181
Αναζήτηση πρόκειται να δούμε
για αριθμό στη λίστα.

470
00:21:02,181 --> 00:21:04,930
Και τραβέρσα είναι μόνο ένα φανταχτερό τρόπο
λέγοντας, με τα πόδια μέσα από τον κατάλογο,

471
00:21:04,930 --> 00:21:06,245
εκτυπώσετε, αλλά αυτό είναι όλο.

472
00:21:06,245 --> 00:21:07,720
Μην το αλλάξετε με οποιοδήποτε τρόπο.

473
00:21:07,720 --> 00:21:08,570
>> Οπότε ας προσπαθήσουμε αυτό.

474
00:21:08,570 --> 00:21:10,160
Ας πάμε μπροστά και τύπου 2.

475
00:21:10,160 --> 00:21:12,710
Και στη συνέχεια, Πάω να
εισάγετε τον αριθμό, ας πούμε 9.

476
00:21:12,710 --> 00:21:13,620
Enter.

477
00:21:13,620 --> 00:21:17,480
Και τώρα το πρόγραμμά μου είναι απλά
προγραμματισμένο να πω, η λίστα είναι τώρα 9.

478
00:21:17,480 --> 00:21:20,190
Τώρα, αν θα προχωρήσει και
Δεν Τοποθετήστε πάλι, ας

479
00:21:20,190 --> 00:21:23,680
Θέλω να προχωρήσει και σμίκρυνση και πληκτρολογήστε 17.

480
00:21:23,680 --> 00:21:25,770
Τώρα λίστα μου είναι 9, τότε 17.

481
00:21:25,770 --> 00:21:27,750
Αν το κάνω, τοποθετήστε και πάλι, ας παραλείψετε μία.

482
00:21:27,750 --> 00:21:32,400
Αντί για 22, σύμφωνα με την εικόνα που έχουμε
κοιτάζοντας εδώ, επιτρέψτε μου να βγαίνουμε μπροστά

483
00:21:32,400 --> 00:21:34,630
και τοποθετήστε 26 επόμενη.

484
00:21:34,630 --> 00:21:36,230
Έτσι, Πάω να πληκτρολογήσετε 26.

485
00:21:36,230 --> 00:21:37,755
Ο κατάλογος είναι όπως περιμένω.

486
00:21:37,755 --> 00:21:40,630
Αλλά τώρα, ακριβώς για να δούμε αν αυτό το κώδικα
πρόκειται να είναι ευέλικτη, επιτρέψτε μου τώρα

487
00:21:40,630 --> 00:21:43,520
Τύπος 22, η οποία τουλάχιστον
εννοιολογικά, αν είμαστε

488
00:21:43,520 --> 00:21:46,520
Κρατώντας αυτό διευθετηθεί, η οποία είναι πράγματι
πρόκειται να είναι ένα άλλο στόχο τώρα,

489
00:21:46,520 --> 00:21:48,690
θα πρέπει να πάμε σε μεταξύ 17 και 26.

490
00:21:48,690 --> 00:21:50,270
Γι 'αυτό και πατήστε Enter.

491
00:21:50,270 --> 00:21:51,380
Πράγματι, αυτό λειτουργεί.

492
00:21:51,380 --> 00:21:54,950
Και τώρα επιτρέψτε μου να εισάγετε το
τελευταία, ανά την εικόνα, 34.

493
00:21:54,950 --> 00:21:55,450
>> Εντάξει.

494
00:21:55,450 --> 00:21:58,980
Έτσι, για τώρα επιτρέψτε μου να ορίζουν ότι
Διαγραφή και Traverse και Αναζήτηση κάνουμε,

495
00:21:58,980 --> 00:21:59,760
στην πραγματικότητα, λειτουργεί.

496
00:21:59,760 --> 00:22:04,180
Στην πραγματικότητα, αν δεν τρέξει Αναζήτηση, ας
αναζήτηση για τον αριθμό 22, Enter.

497
00:22:04,180 --> 00:22:05,010
Διαπίστωσε 22.

498
00:22:05,010 --> 00:22:07,580
Έτσι, αυτό είναι ό, τι αυτό
Πρόγραμμα Λίστα Zero κάνει.

499
00:22:07,580 --> 00:22:10,230
>> Αλλά τι πραγματικά συμβαίνει
στο ότι υλοποιεί αυτό;

500
00:22:10,230 --> 00:22:14,530
Λοιπόν, το πρώτο που θα μπορούσε να έχει, και μάλιστα
Θα έχετε, ένα αρχείο που ονομάζεται list0.h.

501
00:22:14,530 --> 00:22:16,540

502
00:22:16,540 --> 00:22:20,690
Και κάπου εκεί είναι αυτό
γραμμή, typedef, struct node,

503
00:22:20,690 --> 00:22:24,850
τότε έχω άγκιστρα μου, int n, και
Στη συνέχεια struct-- ό, τι ήταν ο ορισμός;

504
00:22:24,850 --> 00:22:26,530

505
00:22:26,530 --> 00:22:28,545
Struct node επόμενη.

506
00:22:28,545 --> 00:22:29,920

507
00:22:29,920 --> 00:22:31,045
Έτσι χρειαζόμαστε το αστέρι.

508
00:22:31,045 --> 00:22:33,420
Τώρα τεχνικά φτάσουμε σε
η συνήθεια της σχεδίασης είναι εδώ.

509
00:22:33,420 --> 00:22:35,670
Μπορείτε να δείτε τα βιβλία και
σε απευθείας σύνδεση αναφορές που κάνουν εκεί.

510
00:22:35,670 --> 00:22:36,660
Είναι λειτουργικά ισοδύναμες.

511
00:22:36,660 --> 00:22:37,980
Στην πραγματικότητα, αυτό είναι λίγο πιο χαρακτηριστική.

512
00:22:37,980 --> 00:22:40,563
Αλλά θα είμαι συνεπής με ό, τι
κάναμε την τελευταία φορά και να το κάνουμε αυτό.

513
00:22:40,563 --> 00:22:42,350
Και στη συνέχεια, τέλος, Πάω να το κάνουμε αυτό.

514
00:22:42,350 --> 00:22:45,550
>> Έτσι, σε ένα αρχείο κεφαλίδας
κάπου, σε list0.h

515
00:22:45,550 --> 00:22:49,200
σήμερα είναι ο ορισμός struct,
και ίσως και κάποια άλλα πράγματα.

516
00:22:49,200 --> 00:22:52,580
Εν τω μεταξύ, σε list0c υπάρχει
πρόκειται να είναι μερικά πράγματα.

517
00:22:52,580 --> 00:22:54,740
Αλλά θα πάμε για λίγο
ξεκινήσει και να μην τελειώσει αυτό.

518
00:22:54,740 --> 00:22:59,690
List0.h είναι ένα αρχείο που θέλω
να συμπεριλάβουν στο φάκελο C μου.

519
00:22:59,690 --> 00:23:03,910
Και τότε σε κάποιο σημείο είμαι
πρόκειται να έχουν int, κύρια, άκυρη.

520
00:23:03,910 --> 00:23:06,530
Και στη συνέχεια, Πάω να
έχουν κάποια to-do είναι εδώ.

521
00:23:06,530 --> 00:23:10,620
Είμαι, επίσης, πρόκειται να έχει ένα
πρωτότυπο, όπως κενό, αναζήτηση, int,

522
00:23:10,620 --> 00:23:13,610
n, σκοπός της οποίας στη ζωή είναι
για να αναζητήσετε ένα στοιχείο.

523
00:23:13,610 --> 00:23:18,310
Και στη συνέχεια κάτω εδώ ισχυρίζομαι μέσα
σημερινή κώδικα, κενό, αναζήτηση, int, n,

524
00:23:18,310 --> 00:23:21,020
Δεν ερωτηματικό, αλλά ανοιχτή σε αγκύλες.

525
00:23:21,020 --> 00:23:25,049
Και τώρα θέλω να με κάποιο τρόπο αναζήτησης
για ένα στοιχείο σε αυτή τη λίστα.

526
00:23:25,049 --> 00:23:27,340
Αλλά δεν έχουμε αρκετό
πληροφορίες στην οθόνη ακόμα.

527
00:23:27,340 --> 00:23:29,800
Δεν έχω πραγματικά
αντιπροσώπευε την ίδια τη λίστα.

528
00:23:29,800 --> 00:23:33,070
Έτσι, ένας τρόπος που θα μπορούσε να εφαρμόσει
μια συνδεδεμένη λίστα σε ένα πρόγραμμα

529
00:23:33,070 --> 00:23:37,520
Θα είναι σαν να θέλω να κάνω κάτι
όπως Κηρύσσω την λίστα συνδέονται εδώ.

530
00:23:37,520 --> 00:23:40,520
Για λόγους απλότητας, Πάω να
αυτό το παγκόσμιο, αν και σε γενικές γραμμές μπορούμε

531
00:23:40,520 --> 00:23:41,645
Δεν πρέπει να το κάνετε αυτό πάρα πολύ.

532
00:23:41,645 --> 00:23:43,260
Αλλά αυτό θα απλοποιήσει αυτό το παράδειγμα.

533
00:23:43,260 --> 00:23:45,890
Θέλω, λοιπόν, να δηλώσουν
μια συνδεδεμένη λίστα εδώ.

534
00:23:45,890 --> 00:23:47,010
Τώρα, πώς θα μπορούσε να το κάνω αυτό;

535
00:23:47,010 --> 00:23:48,810

536
00:23:48,810 --> 00:23:50,750
>> Εδώ είναι η εικόνα μιας συνδεδεμένης λίστας.

537
00:23:50,750 --> 00:23:53,030
Και δεν το κάνω πραγματικά
γνωρίζουμε αυτή τη στιγμή πώς

538
00:23:53,030 --> 00:23:56,710
Πάω να πάει για την εκπροσωπούν
τόσα πολλά πράγματα με ένα μόνο

539
00:23:56,710 --> 00:23:58,040
μεταβλητή στη μνήμη.

540
00:23:58,040 --> 00:23:59,160
Αλλά σκεφτείτε για ένα λεπτό.

541
00:23:59,160 --> 00:24:00,830
Όλο αυτό το διάστημα είχαμε
χορδές, το οποίο εμείς, στη συνέχεια,

542
00:24:00,830 --> 00:24:02,913
αποκάλυψε ότι είναι συστοιχίες
χαρακτήρες, η οποία στη συνέχεια θα

543
00:24:02,913 --> 00:24:05,740
έδειξε να είναι μόνο ένας δείκτης
στον πρώτο χαρακτήρα

544
00:24:05,740 --> 00:24:08,890
σε μια σειρά από χαρακτήρες
ότι είναι null τερματιστεί.

545
00:24:08,890 --> 00:24:13,530
Έτσι, με αυτή τη λογική, και με αυτό
είδος εικόνα της σποράς τις σκέψεις σας,

546
00:24:13,530 --> 00:24:17,964
τι χρειάζεται να είμαστε πραγματικά γράφετε σε μας
κώδικα για να αντιπροσωπεύουν μια συνδεδεμένη λίστα;

547
00:24:17,964 --> 00:24:21,130
Πόσο αυτών των πληροφοριών χρειαζόμαστε
να συλλάβει τον κωδικό C, θα λέγατε;

548
00:24:21,130 --> 00:24:22,654

549
00:24:22,654 --> 00:24:23,154
Ναι;

550
00:24:23,154 --> 00:24:24,738
>> ΚΟΙΝΟ: Χρειαζόμαστε ένα δείκτη σε ένα κόμβο.

551
00:24:24,738 --> 00:24:26,237
DAVID J. MALAN: Ένας δείκτης σε κόμβο.

552
00:24:26,237 --> 00:24:29,320
Ειδικότερα, η οποία κόμβος θα σας
ένστικτα είναι να κρατήσει ένα δείκτη για να?

553
00:24:29,320 --> 00:24:30,026
>> ΚΟΙΝΟ: Το πρώτο κόμβο.

554
00:24:30,026 --> 00:24:31,942
>> DAVID J. MALAN: Ναι,
ίσως μόνο η πρώτη.

555
00:24:31,942 --> 00:24:34,030
Και παρατηρήσετε, το πρώτο
κόμβος είναι ένα διαφορετικό σχήμα.

556
00:24:34,030 --> 00:24:37,690
Είναι μόνο το μισό μέγεθος του struct,
επειδή είναι πράγματι ένας δείκτης.

557
00:24:37,690 --> 00:24:44,650
Έτσι τι μπορείτε να κάνετε είναι πράγματι δηλώσει
μια συνδεδεμένη λίστα είναι του τύπου κόμβου *.

558
00:24:44,650 --> 00:24:47,780
Και ας πούμε ότι είναι το πρώτο
και να προετοιμαστεί για να null.

559
00:24:47,780 --> 00:24:49,910
Έτσι, null, και πάλι, είναι που έρχονται
στην εικόνα εδώ.

560
00:24:49,910 --> 00:24:53,620
Όχι μόνο είναι null χρησιμοποιείται ως σαν μια ειδική
τιμή επιστροφής για πράγματα όπως GetString

561
00:24:53,620 --> 00:24:57,770
και malloc, null είναι επίσης το μηδέν
δείκτη, η έλλειψη ενός δείκτη,

562
00:24:57,770 --> 00:24:58,430
αν θέλετε.

563
00:24:58,430 --> 00:25:00,309
Σημαίνει απλώς ότι τίποτα δεν είναι ακόμα εδώ.

564
00:25:00,309 --> 00:25:02,100
Τώρα το πρώτο, θα μπορούσα να έχω
ονομάζεται αυτό το τίποτα.

565
00:25:02,100 --> 00:25:04,200
Θα μπορούσα να είχα την αποκάλεσε "λίστα"
ή οποιοδήποτε αριθμό άλλων πραγμάτων.

566
00:25:04,200 --> 00:25:06,960
Αλλά είμαι χαρακτηρίζοντάς την "πρώτη", έτσι ώστε
να ευθυγραμμιστεί με αυτήν την εικόνα.

567
00:25:06,960 --> 00:25:10,280
Έτσι ακριβώς όπως ένα string μπορεί να εκπροσωπείται
με τη διεύθυνση του πρώτου byte του,

568
00:25:10,280 --> 00:25:11,280
έτσι μπορεί μια συνδεδεμένη λίστα.

569
00:25:11,280 --> 00:25:13,480
Και θα δούμε και άλλα στοιχεία
να εκπροσωπούνται δομές

570
00:25:13,480 --> 00:25:16,700
με ένα μόνο δείκτη,
ένα 32-bit βέλος, δείχνοντας

571
00:25:16,700 --> 00:25:18,740
κατά την πρώτη κιόλας κόμβου στη δομή.

572
00:25:18,740 --> 00:25:20,340
>> Αλλά τώρα ας προβλέψει ένα πρόβλημα.

573
00:25:20,340 --> 00:25:23,230
Αν είμαι μόνο να θυμόμαστε
στο πρόγραμμά μου τη διεύθυνση

574
00:25:23,230 --> 00:25:27,220
του πρώτου κόμβου, η πρώτη
ορθογώνιο σε αυτή τη δομή δεδομένων,

575
00:25:27,220 --> 00:25:31,760
τι είχε καλύτερα να είναι η περίπτωση για την
εφαρμογή της υπόλοιπης λίστα μου;

576
00:25:31,760 --> 00:25:35,820
Τι είναι μια βασική λεπτομέρεια που πρόκειται
για να εξασφαλιστεί αυτό λειτουργεί πραγματικά;

577
00:25:35,820 --> 00:25:39,250
Και με το "λειτουργεί πραγματικά" I
Δηλαδή, σαν ένα string,

578
00:25:39,250 --> 00:25:42,180
ας πάμε από τον πρώτο χαρακτήρα
στο όνομα του Davin στη δεύτερη,

579
00:25:42,180 --> 00:25:44,755
με το τρίτο, εις το
τέταρτο, μέχρι το τέλος,

580
00:25:44,755 --> 00:25:47,880
πώς ξέρουμε πότε είμαστε στο τέλος
από μια συνδεδεμένη λίστα που μοιάζει με αυτό;

581
00:25:47,880 --> 00:25:50,035

582
00:25:50,035 --> 00:25:50,660
Όταν είναι null.

583
00:25:50,660 --> 00:25:53,640
Και έχω εκπροσωπείται αυτού του είδους, όπως
σαν μια ηλεκτρική δύναμη μηχανικός,

584
00:25:53,640 --> 00:25:56,420
με το μικρό γείωσης
σύμβολο, των ειδών.

585
00:25:56,420 --> 00:25:58,246
Αλλά αυτό ακριβώς σημαίνει null σε αυτή την περίπτωση.

586
00:25:58,246 --> 00:26:00,370
Μπορείτε να σχεδιάσετε οποιοδήποτε αριθμό
τρόπους, αλλά αυτό το συγγραφέα

587
00:26:00,370 --> 00:26:02,800
έτυχε να χρησιμοποιούν αυτό το σύμβολο εδώ.

588
00:26:02,800 --> 00:26:06,260
>> Εφ 'όσον είμαστε κλωστή
όλα από αυτούς τους κόμβους μεταξύ τους,

589
00:26:06,260 --> 00:26:08,600
μόνο θυμόμαστε όπου
το πρώτο είναι, εφ '

590
00:26:08,600 --> 00:26:11,760
όπως βάζουμε ένα ειδικό σύμβολο σε
το πολύ τελευταίο κόμβο στη λίστα,

591
00:26:11,760 --> 00:26:15,130
και θα χρησιμοποιήσει μηδενική, γιατί αυτό είναι
ό, τι έχουμε στη διάθεσή μας,

592
00:26:15,130 --> 00:26:16,480
ο κατάλογος είναι πλήρης.

593
00:26:16,480 --> 00:26:20,190
Και ακόμα κι αν σας δώσω μόνο ένα δείκτη για να
το πρώτο στοιχείο, εσείς, ο προγραμματιστής,

594
00:26:20,190 --> 00:26:22,486
σίγουρα μπορεί να έχει πρόσβαση το υπόλοιπο.

595
00:26:22,486 --> 00:26:24,360
Αλλά ας αφήσουμε το μυαλό σας
περιπλανηθεί λίγο,

596
00:26:24,360 --> 00:26:26,140
αν δεν είναι ήδη
αρκετά wandered-- τι είναι

597
00:26:26,140 --> 00:26:28,723
πρόκειται να είναι ο χρόνος εκτέλεσης του
εύρεση τίποτα σε αυτή τη λίστα;

598
00:26:28,723 --> 00:26:30,450

599
00:26:30,450 --> 00:26:33,470
Γαμώτο, αυτό είναι μεγάλο O του n,
το οποίο δεν είναι κακό, για να είμαστε δίκαιοι.

600
00:26:33,470 --> 00:26:34,800
Αλλά είναι γραμμική.

601
00:26:34,800 --> 00:26:37,980
Έχουμε δώσει μέχρι ποιο χαρακτηριστικό
συστοιχιών μετακινώντας περισσότερα

602
00:26:37,980 --> 00:26:43,130
προς αυτήν την εικόνα της δυναμικής
υφασμένα από κοινού ή συνδέονται με τους κόμβους;

603
00:26:43,130 --> 00:26:44,970

604
00:26:44,970 --> 00:26:46,687
Έχουμε παραιτηθεί τυχαίας προσπέλασης.

605
00:26:46,687 --> 00:26:48,770
Ένας πίνακας είναι ωραία γιατί
μαθηματικά τα πάντα

606
00:26:48,770 --> 00:26:50,340
είναι πίσω στην πλάτη με πλάτη με πλάτη.

607
00:26:50,340 --> 00:26:52,370
Ακόμα κι αν αυτή την εικόνα
φαίνεται αρκετά, και ακόμη

608
00:26:52,370 --> 00:26:55,830
αν και μοιάζει με αυτούς τους κόμβους
Τα όμορφα απόσταση μεταξύ τους, στην πραγματικότητα

609
00:26:55,830 --> 00:26:56,830
θα μπορούσαν να είναι οπουδήποτε.

610
00:26:56,830 --> 00:27:01,590
ΟΧ1, ΟΧ50, Ox123, Ox99, αυτά
κόμβοι θα μπορούσαν να είναι οπουδήποτε.

611
00:27:01,590 --> 00:27:05,960
Επειδή malloc κάνει εκχώρηση μνήμης
από το σωρό, αλλά οπουδήποτε στο σωρό.

612
00:27:05,960 --> 00:27:09,080
Δεν χρειάζεται απαραιτήτως να ξέρετε ότι είναι
πρόκειται να είναι πλάτη με πλάτη με πλάτη.

613
00:27:09,080 --> 00:27:12,460
Και έτσι αυτή η εικόνα στην πραγματικότητα είναι
δεν πρόκειται να είναι αρκετά αυτό το όμορφο.

614
00:27:12,460 --> 00:27:16,140
>> Έτσι πρόκειται να πάρει ένα κομμάτι της
εργαστούν για την εφαρμογή αυτής της λειτουργίας.

615
00:27:16,140 --> 00:27:17,880
Ας εφαρμόσουν αναζήτηση τώρα.

616
00:27:17,880 --> 00:27:20,250
Και θα δούμε το είδος της μια
έξυπνος τρόπος για να γίνει αυτό.

617
00:27:20,250 --> 00:27:24,660
Έτσι, αν είμαι μια λειτουργία αναζήτησης και
Είμαι δοθεί μια μεταβλητή, ακέραιος n

618
00:27:24,660 --> 00:27:28,490
να αναζητήσουν, θα πρέπει να γνωρίζουν το
νέα σύνταξη για την ψάχνει μέσα

619
00:27:28,490 --> 00:27:32,400
μιας δομής που είναι
επεσήμανε, για να βρείτε n.

620
00:27:32,400 --> 00:27:33,210
Έτσι, ας κάνουμε αυτό.

621
00:27:33,210 --> 00:27:36,030
>> Έτσι, η πρώτη Πάω να πάει
μπροστά και να κηρύξει κόμβο *.

622
00:27:36,030 --> 00:27:39,400
Και Πάω να το ονομάσουμε
δείκτη, μόνο κατά σύμβαση.

623
00:27:39,400 --> 00:27:41,710
Και Πάω να προετοιμαστεί για την πρώτη.

624
00:27:41,710 --> 00:27:43,770
Και τώρα μπορώ να το κάνω αυτό
σε έναν αριθμό τρόπων.

625
00:27:43,770 --> 00:27:45,436
Αλλά Πάω να λάβει μια κοινή προσέγγιση.

626
00:27:45,436 --> 00:27:50,180
Ενώ δείκτης δεν είναι ίση προς
null, και ότι είναι έγκυρη σύνταξη.

627
00:27:50,180 --> 00:27:54,550
Και αυτό σημαίνει απλά να κάνετε τα εξής, έτσι
εφ 'όσον δεν είστε δείχνοντας τίποτα.

628
00:27:54,550 --> 00:27:55,800
Τι θέλω να κάνω;

629
00:27:55,800 --> 00:28:01,939
>> Αν δείκτη dot n, επιτρέψτε μου να επανέλθω
στο ότι, equals-- ισούται με τι;

630
00:28:01,939 --> 00:28:03,105
Τι αξία ψάχνω;

631
00:28:03,105 --> 00:28:04,920

632
00:28:04,920 --> 00:28:06,590
Η πραγματική n που ψηφίστηκε.

633
00:28:06,590 --> 00:28:09,020
Έτσι, εδώ είναι ένα άλλο χαρακτηριστικό
της C και πολλές γλώσσες.

634
00:28:09,020 --> 00:28:13,705
Ακόμη και αν η δομή που ονομάζεται κόμβος
έχει μια τιμή n, εντελώς νόμιμα

635
00:28:13,705 --> 00:28:17,530
να έχουν επίσης μια τοπική επιχείρημα
ή μεταβλητή που ονομάζεται n.

636
00:28:17,530 --> 00:28:20,085
Διότι ακόμα και εμείς, με
ανθρώπινα μάτια, μπορεί να διακρίνει

637
00:28:20,085 --> 00:28:22,087
ότι αυτή η είναι πιθανώς
διαφορετική από αυτή n.

638
00:28:22,087 --> 00:28:23,420
Επειδή η σύνταξη είναι διαφορετική.

639
00:28:23,420 --> 00:28:26,211
Έχετε μια τελεία και ένα δείκτη,
ενώ αυτό δεν έχει τέτοιο πράγμα.

640
00:28:26,211 --> 00:28:27,290
Έτσι, αυτό είναι εντάξει.

641
00:28:27,290 --> 00:28:29,120
Αυτό είναι εντάξει για να τους καλέσει τα ίδια πράγματα.

642
00:28:29,120 --> 00:28:32,380
>> Αν δεν μπορείτε να βρείτε αυτό, είμαι
πρόκειται να θέλουν να κάνουν κάτι

643
00:28:32,380 --> 00:28:35,000
όπως ανακοινώσει ότι βρήκαμε n.

644
00:28:35,000 --> 00:28:37,930
Και αυτό θα το αφήσουμε ως
σχόλιο ή κωδικό ψευδοκώδικα.

645
00:28:37,930 --> 00:28:40,190
Αλλιώς, και εδώ είναι η
ενδιαφέρον μέρος, ό, τι

646
00:28:40,190 --> 00:28:47,320
θέλω να κάνω εάν το τρέχον κόμβο
δεν περιέχουν n που με νοιάζει;

647
00:28:47,320 --> 00:28:50,700
Πώς μπορώ να επιτύχουν τα ακόλουθα;

648
00:28:50,700 --> 00:28:53,710
Αν το δάχτυλό μου στο η
στιγμή είναι PTR, και είναι

649
00:28:53,710 --> 00:28:55,920
δείχνοντας σε ό, τι
πρώτος δείχνοντας,

650
00:28:55,920 --> 00:28:59,290
πώς μπορώ να μετακινήσετε το δάχτυλό μου
στον επόμενο κόμβο στον κώδικα;

651
00:28:59,290 --> 00:29:01,915
Λοιπόν, ποιο είναι το ψίχουλο είμαστε
πρόκειται να ακολουθήσει σε αυτή την περίπτωση;

652
00:29:01,915 --> 00:29:03,464

653
00:29:03,464 --> 00:29:04,380
ΚΟΙΝΟ: [δεν ακούγεται].

654
00:29:04,380 --> 00:29:05,630
DAVID J. MALAN: Ναι, έτσι ώστε την επόμενη.

655
00:29:05,630 --> 00:29:06,640

656
00:29:06,640 --> 00:29:09,824
Έτσι, αν πάω πίσω για να μου
κώδικα εδώ, πράγματι, είμαι

657
00:29:09,824 --> 00:29:12,990
πρόκειται να προχωρήσει και να πω δείκτη, η οποία
Είναι απλά μια προσωρινή variable-- είναι

658
00:29:12,990 --> 00:29:15,320
ένα παράξενο όνομα, ptr, αλλά
Είναι ακριβώς όπως temp--

659
00:29:15,320 --> 00:29:19,234
Πάω να ορίσετε δείκτη
ίση με ό, τι δείκτη is--

660
00:29:19,234 --> 00:29:22,150
και πάλι, αυτό πρόκειται να είναι ένα
μικρό αμαξάκι για μια moment-- dot επόμενη.

661
00:29:22,150 --> 00:29:23,551

662
00:29:23,551 --> 00:29:26,550
Με άλλα λόγια, είμαι πρόκειται να πάρει μου
δάχτυλο που να υποδεικνύουν αυτόν τον κόμβο

663
00:29:26,550 --> 00:29:31,247
εδώ και είμαι έτοιμος να πω, ξέρετε
αυτό, ρίξτε μια ματιά στο επόμενο πεδίο

664
00:29:31,247 --> 00:29:33,330
και μετακινήστε το δάχτυλό σας για να
ό, τι είναι να υποδεικνύουν.

665
00:29:33,330 --> 00:29:35,163
Και αυτό πρόκειται να
Επαναλαμβάνω, επαναλαμβάνω, επαναλάβετε.

666
00:29:35,163 --> 00:29:37,630
Αλλά όταν κάνει το δάχτυλό μου
σταματήσουμε να κάνουμε τίποτα σε όλα;

667
00:29:37,630 --> 00:29:40,095
Μόλις το τι γραμμή κλωτσιές κώδικα σε;

668
00:29:40,095 --> 00:29:40,970
ΚΟΙΝΟ: [δεν ακούγεται]

669
00:29:40,970 --> 00:29:43,060
DAVID J. MALAN: Εάν το σημείο, ενώ
δείκτης δεν είναι ίσο με το μηδέν.

670
00:29:43,060 --> 00:29:44,900
Σε κάποιο σημείο το δάχτυλό μου
θα πρέπει να δείχνει σε null

671
00:29:44,900 --> 00:29:47,070
και Πάω να συνειδητοποιήσουν
αυτό είναι το τέλος αυτής της λίστας.

672
00:29:47,070 --> 00:29:48,910
Τώρα, αυτό είναι λίγο
λευκό ψέμα για λόγους απλότητας.

673
00:29:48,910 --> 00:29:51,580
Αποδεικνύεται ότι ακόμα κι αν
μόλις έμαθε αυτό dot σημειογραφία

674
00:29:51,580 --> 00:29:55,220
για τις δομές, δείκτης δεν είναι ένα struct.

675
00:29:55,220 --> 00:29:56,580
ptr είναι αυτό;

676
00:29:56,580 --> 00:29:58,350
Ακριβώς για να είναι πιο nitpicky.

677
00:29:58,350 --> 00:29:59,720

678
00:29:59,720 --> 00:30:01,360
Είναι ένας δείκτης σε κόμβο.

679
00:30:01,360 --> 00:30:03,120
Δεν είναι το ίδιο ένας κόμβος.

680
00:30:03,120 --> 00:30:06,650
Αν δεν είχα αστέρι εδώ, δείκτης
absolutely-- είναι ένας κόμβος.

681
00:30:06,650 --> 00:30:08,650
Αυτό είναι σαν μια εβδομάδα
δήλωση μιας μεταβλητής,

682
00:30:08,650 --> 00:30:10,120
ακόμη και αν η λέξη «κόμβος» είναι νέα.

683
00:30:10,120 --> 00:30:13,860
>> Αλλά μόλις εισάγουμε ένα
αστέρι, είναι τώρα ένας δείκτης σε κόμβο.

684
00:30:13,860 --> 00:30:17,960
Και, δυστυχώς, δεν μπορείτε να χρησιμοποιήσετε
ο συμβολισμός κουκκίδα για την ύπαρξη δείκτη.

685
00:30:17,960 --> 00:30:21,070
Θα πρέπει να χρησιμοποιήσετε το βέλος
σημειογραφία, η οποία, εντυπωσιακά,

686
00:30:21,070 --> 00:30:23,470
Είναι η πρώτη φορά κάθε κομμάτι
της σύνταξης φαίνεται διαισθητικό.

687
00:30:23,470 --> 00:30:25,245
Αυτό μοιάζει κυριολεκτικά σαν ένα βέλος.

688
00:30:25,245 --> 00:30:26,370
Και αυτό είναι ένα καλό πράγμα.

689
00:30:26,370 --> 00:30:28,995
Και εδώ κάτω κυριολεκτικά
Μοιάζει με ένα βέλος.

690
00:30:28,995 --> 00:30:31,870
Έτσι, νομίζω ότι είναι η la-- εγώ δεν κάνω
ότι είμαι πάνω-διάπραξη here-- I

691
00:30:31,870 --> 00:30:34,120
Πιστεύω ότι είναι το τελευταίο νέο κομμάτι
της σύνταξης θα πάμε να δούμε.

692
00:30:34,120 --> 00:30:36,500
Και ευτυχώς, είναι όντως
λίγο πιο διαισθητικό.

693
00:30:36,500 --> 00:30:40,090
>> Τώρα, για όσους από εσάς
μπορεί να προτιμούν τον παλιό τρόπο,

694
00:30:40,090 --> 00:30:42,550
μπορείτε ακόμα να χρησιμοποιήσετε το συμβολισμό με την τελεία.

695
00:30:42,550 --> 00:30:45,380
Αλλά, όπως κάθε Δευτέρα
συνομιλία, πρέπει πρώτα

696
00:30:45,380 --> 00:30:50,530
Πρέπει να πάμε εκεί, πηγαίνετε στο ότι
αντιμετώπιση, και στη συνέχεια πρόσβαση στο χώρο.

697
00:30:50,530 --> 00:30:51,897
Έτσι, αυτό είναι επίσης σωστό.

698
00:30:51,897 --> 00:30:53,730
Και ειλικρινά, αυτό είναι ένα
λίγο πιο σχολαστικός.

699
00:30:53,730 --> 00:30:56,530
Είστε κυριολεκτικά λέγοντας, dereference
ο δείκτης και να πάει εκεί.

700
00:30:56,530 --> 00:30:59,320
Στη συνέχεια, πιάσε .n, το πεδίο που ονομάζεται n.

701
00:30:59,320 --> 00:31:01,370
Αλλά ειλικρινά, κανείς δεν θέλει
να πληκτρολογήσετε ή να διαβάσετε αυτό.

702
00:31:01,370 --> 00:31:03,620
Και έτσι ο κόσμος εφευρέθηκε
ο συμβολισμός βέλος, το οποίο

703
00:31:03,620 --> 00:31:06,980
είναι ισοδύναμο, πανομοιότυπα,
Είναι απλά συντακτική ζάχαρη.

704
00:31:06,980 --> 00:31:10,570
Έτσι, ένα φανταχτερό τρόπο λέγοντας αυτό
Φαίνεται καλύτερα, ή φαίνεται απλούστερη.

705
00:31:10,570 --> 00:31:12,296
>> Έτσι, τώρα θα πάω να κάνω κάτι άλλο.

706
00:31:12,296 --> 00:31:15,420
Πάω να πω "διάλειμμα" από τη στιγμή έχω
Βρέθηκε έτσι δεν συνεχίσετε να ψάχνετε για αυτό.

707
00:31:15,420 --> 00:31:17,620
Αλλά αυτή είναι η ουσία
της λειτουργίας αναζήτησης.

708
00:31:17,620 --> 00:31:21,710
Αλλά είναι πολύ πιο εύκολο, στην
τέλος, να μην περπατάτε μέσα από τον κώδικα.

709
00:31:21,710 --> 00:31:25,570
Αυτή είναι πράγματι η επίσημη εφαρμογή
αναζήτησης στον κώδικα της διανομής του σήμερα.

710
00:31:25,570 --> 00:31:30,530
Τολμώ να πω ότι το ένθετο δεν είναι
ιδιαίτερα διασκεδαστικό να περπατήσετε μέσα

711
00:31:30,530 --> 00:31:33,180
οπτικά, ούτε να διαγράψετε, ακόμα και
αν και στο τέλος της ημέρας

712
00:31:33,180 --> 00:31:35,460
βράζουν κάτω αρκετά
απλά heuristics.

713
00:31:35,460 --> 00:31:36,330
>> Έτσι, ας κάνουμε αυτό.

714
00:31:36,330 --> 00:31:39,250
Αν εσείς θα το χιούμορ μου εδώ, έκανα
φέρει ένα σωρό μπάλες άγχος.

715
00:31:39,250 --> 00:31:40,620
Έφερα ένα μάτσο αριθμούς.

716
00:31:40,620 --> 00:31:46,562
Και θα μπορούσαμε να πάρετε μόνο λίγα εθελοντές
να αντιπροσωπεύει 9, 17, 20, 22, 29, και 34?

717
00:31:46,562 --> 00:31:48,270
Έτσι, ουσιαστικά όλοι
που είναι εδώ σήμερα.

718
00:31:48,270 --> 00:31:50,170

719
00:31:50,170 --> 00:31:52,760
Αυτό ήταν ένα, δύο, τρία,
τέσσερα, πέντε, έξι άτομα.

720
00:31:52,760 --> 00:31:55,740
Και έχω κληθεί να go-- δείτε, δεν
ένα στο πίσω σηκώνει τα χέρια τους.

721
00:31:55,740 --> 00:32:01,910
ΟΚ, ένα, δύο, τρία, τέσσερα,
five-- επιτρέψτε μου να φορτώσει balance-- έξι.

722
00:32:01,910 --> 00:32:03,051
OK, θα έρθει σε έξι up.

723
00:32:03,051 --> 00:32:04,050
Θα χρειαστούμε άλλους ανθρώπους.

724
00:32:04,050 --> 00:32:05,460
Φέραμε επιπλέον μπάλες άγχος.

725
00:32:05,460 --> 00:32:08,200
Και αν μπορούσε, για
μόνο μια στιγμή, γραμμή

726
00:32:08,200 --> 00:32:10,490
τον εαυτό σας επάνω ακριβώς
όπως αυτή την εικόνα εδώ.

727
00:32:10,490 --> 00:32:15,200

728
00:32:15,200 --> 00:32:15,959
>> Εντάξει.

729
00:32:15,959 --> 00:32:17,125
Ας δούμε, τι είναι το όνομά σας;

730
00:32:17,125 --> 00:32:17,550
>> ΚΟΙΝΟ: Andrew.

731
00:32:17,550 --> 00:32:18,800
>> DAVID J. MALAN: Andrew,
είστε αριθμό 9.

732
00:32:18,800 --> 00:32:19,540
Χαίρω πολύ.

733
00:32:19,540 --> 00:32:20,400
Εδώ θα πάτε.

734
00:32:20,400 --> 00:32:21,593

735
00:32:21,593 --> 00:32:22,176
ΚΟΙΝΟ: Jen.

736
00:32:22,176 --> 00:32:22,662
DAVID J. MALAN: Jen.

737
00:32:22,662 --> 00:32:23,162
David.

738
00:32:23,162 --> 00:32:23,765
Αριθμός 17.

739
00:32:23,765 --> 00:32:24,950

740
00:32:24,950 --> 00:32:25,450
Ναι;

741
00:32:25,450 --> 00:32:26,400
>> ΚΟΙΝΟ: Είμαι η Τζούλια.

742
00:32:26,400 --> 00:32:26,980
>> DAVID J. MALAN: Τζούλια, David.

743
00:32:26,980 --> 00:32:27,545
Αριθμός 20.

744
00:32:27,545 --> 00:32:28,507

745
00:32:28,507 --> 00:32:29,340
ΚΟΙΝΟ: Christian.

746
00:32:29,340 --> 00:32:30,715
DAVID J. MALAN: Christian, David.

747
00:32:30,715 --> 00:32:31,541
Αριθμός 22.

748
00:32:31,541 --> 00:32:32,040
Και;

749
00:32:32,040 --> 00:32:32,649
>> ΚΟΙΝΟ: JP.

750
00:32:32,649 --> 00:32:33,440
DAVID J. MALAN: JP.

751
00:32:33,440 --> 00:32:34,880
Αριθμός 29.

752
00:32:34,880 --> 00:32:37,080
Έτσι προχωρήστε και να πάρει in-- Ωχ.

753
00:32:37,080 --> 00:32:38,486

754
00:32:38,486 --> 00:32:38,985
Ωχ.

755
00:32:38,985 --> 00:32:39,650

756
00:32:39,650 --> 00:32:40,150
Αναμονής.

757
00:32:40,150 --> 00:32:41,360

758
00:32:41,360 --> 00:32:42,390
20.

759
00:32:42,390 --> 00:32:43,682
Υπάρχει κάποιος που έχει ένα δείκτη;

760
00:32:43,682 --> 00:32:44,890
ΚΟΙΝΟ: Έχω ένα Sharpie.

761
00:32:44,890 --> 00:32:45,660
DAVID J. MALAN: Έχεις ένα Sharpie;

762
00:32:45,660 --> 00:32:46,159
OK.

763
00:32:46,159 --> 00:32:47,577

764
00:32:47,577 --> 00:32:49,160
Και όμως κάποιοι έχουν ένα κομμάτι χαρτί;

765
00:32:49,160 --> 00:32:51,562

766
00:32:51,562 --> 00:32:52,270
Αποθηκεύστε τη διάλεξη.

767
00:32:52,270 --> 00:32:53,810

768
00:32:53,810 --> 00:32:55,362
Έλα.

769
00:32:55,362 --> 00:32:56,320
ΚΟΙΝΟ: Έχουμε το πήρα.

770
00:32:56,320 --> 00:32:57,600
DAVID J. MALAN: Μας πήρε;

771
00:32:57,600 --> 00:32:58,577
Εντάξει, σας ευχαριστώ.

772
00:32:58,577 --> 00:33:01,380

773
00:33:01,380 --> 00:33:02,520
Εδώ πάμε.

774
00:33:02,520 --> 00:33:03,582
Αυτή η από εσάς;

775
00:33:03,582 --> 00:33:04,540
Απλά έσωσε την ημέρα.

776
00:33:04,540 --> 00:33:05,670

777
00:33:05,670 --> 00:33:07,220
Έτσι, 29.

778
00:33:07,220 --> 00:33:10,510

779
00:33:10,510 --> 00:33:11,110
Εντάξει.

780
00:33:11,110 --> 00:33:13,360

781
00:33:13,360 --> 00:33:14,890
I ανορθόγραφη 29, αλλά ΟΚ.

782
00:33:14,890 --> 00:33:15,720
Προχωρήστε.

783
00:33:15,720 --> 00:33:18,114
Εντάξει, εγώ θα σας δώσω
στυλό σας πίσω στιγμιαία.

784
00:33:18,114 --> 00:33:19,280
Έτσι έχουμε αυτά τα παιδιά εδώ.

785
00:33:19,280 --> 00:33:20,330
Ας έχουμε ένα άλλο.

786
00:33:20,330 --> 00:33:23,750
Gabe, θέλετε να παίξετε
το πρώτο στοιχείο εδώ;

787
00:33:23,750 --> 00:33:25,705
Θα πρέπει να επισημάνω
σε αυτά τα ωραία λαοί.

788
00:33:25,705 --> 00:33:26,930

789
00:33:26,930 --> 00:33:31,030
Έτσι, 9, 17, 20, 22, ταξινόμησης
των 29, και στη συνέχεια 34.

790
00:33:31,030 --> 00:33:32,160

791
00:33:32,160 --> 00:33:33,325
Μήπως χάνουμε κάποιον;

792
00:33:33,325 --> 00:33:33,950
Έχω μια 34.

793
00:33:33,950 --> 00:33:36,730
Όταν did-- OK, ο οποίος θέλει να είναι 34;

794
00:33:36,730 --> 00:33:37,605
Εντάξει, έλα επάνω, 34.

795
00:33:37,605 --> 00:33:39,280

796
00:33:39,280 --> 00:33:41,220
Εντάξει, αυτό θα είναι
αξίζει το αποκορύφωμα.

797
00:33:41,220 --> 00:33:41,550
Ποιο είναι το όνομά σου;

798
00:33:41,550 --> 00:33:42,040
>> ΚΟΙΝΟ: Peter.

799
00:33:42,040 --> 00:33:43,456
>> DAVID J. MALAN: Peter, έλα επάνω.

800
00:33:43,456 --> 00:33:46,810
Εντάξει, τόσο εδώ είναι μια
σωρό των κόμβων.

801
00:33:46,810 --> 00:33:49,060
Κάθε ένας από εσάς παιδιά αντιπροσωπεύει
ένα από αυτά τα ορθογώνια.

802
00:33:49,060 --> 00:33:51,930
Και Gabe, το ελαφρώς παράξενο
άνθρωπο έξω, αντιπροσωπεύει την πρώτη.

803
00:33:51,930 --> 00:33:54,850
Έτσι δείκτης του είναι λίγο μικρότερο
στην οθόνη από ό, τι όλοι οι άλλοι.

804
00:33:54,850 --> 00:33:58,120
Και σε αυτή την περίπτωση, καθένα από τα αριστερά
τα χέρια πρόκειται είτε να κλίνουν προς τα κάτω,

805
00:33:58,120 --> 00:34:01,085
εκπροσωπώντας έτσι null, έτσι
μόλις η απουσία ενός δείκτη,

806
00:34:01,085 --> 00:34:03,210
ή πρόκειται να δείχνουν
σε έναν κόμβο δίπλα σας.

807
00:34:03,210 --> 00:34:05,440
>> Έτσι τώρα, αν κοσμούν
τον εαυτό σας όπως την εικόνα

808
00:34:05,440 --> 00:34:07,585
εδώ, να προχωρήσει και να το σημείο
σε κάθε άλλη, με Gabe

809
00:34:07,585 --> 00:34:11,030
ιδίως κατάδειξης σε
τον αριθμό 9 για να εκπροσωπεί τη λίστα.

810
00:34:11,030 --> 00:34:14,050
OK, και τον αριθμό 34, το αριστερό χέρι σας
Πρέπει απλά να δείχνει στο πάτωμα.

811
00:34:14,050 --> 00:34:15,750
>> Εντάξει, έτσι αυτό είναι η συνδεδεμένη λίστα.

812
00:34:15,750 --> 00:34:17,580
Έτσι, αυτό είναι το σενάριο στο ερώτημα.

813
00:34:17,580 --> 00:34:20,210
Και πράγματι, αυτή είναι αντιπροσωπευτική
από μια κατηγορία προβλημάτων

814
00:34:20,210 --> 00:34:21,929
ότι μπορείτε να προσπαθήσετε να λύσετε με κωδικό.

815
00:34:21,929 --> 00:34:25,020
Θέλετε να τοποθετήσετε τελικά
ένα νέο στοιχείο στη λίστα.

816
00:34:25,020 --> 00:34:27,494
Σε αυτή την περίπτωση, θα πάμε να
δοκιμάστε να τοποθετήσετε τον αριθμό 55.

817
00:34:27,494 --> 00:34:28,500

818
00:34:28,500 --> 00:34:30,860
Αλλά εκεί πρόκειται να είναι
διαφορετικές περιπτώσεις για να εξετάσει.

819
00:34:30,860 --> 00:34:34,409
Και πράγματι, αυτό πρόκειται να είναι ένα
από το big-εικόνα Takeaways εδώ, είναι,

820
00:34:34,409 --> 00:34:35,659
ποιες είναι οι διαφορετικές περιπτώσεις.

821
00:34:35,659 --> 00:34:39,120
Ποια είναι η διαφορετική εάν οι συνθήκες ή
υποκαταστήματα που το πρόγραμμά σας μπορεί να έχει;

822
00:34:39,120 --> 00:34:42,024
>> Λοιπόν, ο αριθμός που προσπαθείτε να
ένθετο, που γνωρίζουμε τώρα είναι 55,

823
00:34:42,024 --> 00:34:44,650
αλλά αν δεν ξέρατε
εκ των προτέρων, τολμώ να πω

824
00:34:44,650 --> 00:34:47,840
πέφτει σε τουλάχιστον τρία
πιθανές καταστάσεις.

825
00:34:47,840 --> 00:34:49,717
Πού θα μπορούσε ένα νέο στοιχείο είναι;

826
00:34:49,717 --> 00:34:51,050
ΚΟΙΝΟ: Και το τέλος ή τη μέση.

827
00:34:51,050 --> 00:34:54,150
David J. MALAN: Στο τέλος, σε
η μέση, ή στην αρχή.

828
00:34:54,150 --> 00:34:56,650
Γι 'αυτό και ισχυρίζονται ότι υπάρχει τουλάχιστον
τρία προβλήματα που πρέπει να λύσουμε.

829
00:34:56,650 --> 00:34:58,691
Ας επιλέξουν τι είναι ίσως
αναμφισβήτητα το πιο απλό

830
00:34:58,691 --> 00:35:01,090
ένα, όπου το νέο στοιχείο
ανήκει στην αρχή.

831
00:35:01,090 --> 00:35:04,040
Έτσι, Πάω να έχουν κωδικό αρκετά
όπως η αναζήτηση, η οποία μόλις έγραψα.

832
00:35:04,040 --> 00:35:07,670
Και Πάω να έχουν ptr, η οποία
Θα εκπροσωπώ εδώ με το δάχτυλό μου,

833
00:35:07,670 --> 00:35:08,370
ως συνήθως.

834
00:35:08,370 --> 00:35:12,430
>> Και να θυμάστε, ποια αξία
δεν έχουμε προετοιμαστεί ptr να;

835
00:35:12,430 --> 00:35:15,300
Έτσι μπορούμε να προετοιμαστεί για να null αρχικά.

836
00:35:15,300 --> 00:35:16,410

837
00:35:16,410 --> 00:35:19,770
Αλλά τότε τι κάναμε κάποτε εμείς
ήταν μέσα λειτουργία αναζήτησης μας;

838
00:35:19,770 --> 00:35:20,940

839
00:35:20,940 --> 00:35:24,870
Θέσαμε αυτό ισούται με το πρώτο,
πράγμα που δεν σημαίνει να γίνει αυτό.

840
00:35:24,870 --> 00:35:25,890

841
00:35:25,890 --> 00:35:30,570
Αν ορίσω ptr ίσο με το πρώτο, τι
θα πρέπει να το χέρι μου πραγματικά να δείχνετε;

842
00:35:30,570 --> 00:35:31,070
Δεξιά.

843
00:35:31,070 --> 00:35:33,290
Έτσι, αν Gabe και εγώ θα
να είναι ίσες τιμές εδώ,

844
00:35:33,290 --> 00:35:34,760
χρειαζόμαστε τόσο για το σημείο στο νούμερο 9.

845
00:35:34,760 --> 00:35:36,420
>> Έτσι, αυτό ήταν η αρχή της ιστορίας μας.

846
00:35:36,420 --> 00:35:38,700
Και τώρα αυτό είναι μόνο απλή,
ακόμη και αν η σύνταξη είναι νέα.

847
00:35:38,700 --> 00:35:40,580
Εννοιολογικά αυτό είναι ακριβώς γραμμική αναζήτηση.

848
00:35:40,580 --> 00:35:42,750
55 είναι ίση προς 9;

849
00:35:42,750 --> 00:35:45,559
Ή μάλλον, ας πούμε λιγότερο από 9.

850
00:35:45,559 --> 00:35:47,600
Επειδή προσπαθώ να
καταλάβω πού να βάλει 55.

851
00:35:47,600 --> 00:35:51,270
Λιγότερο από 9, λιγότερο από 17, λιγότερο
από 20, λιγότερο από 22, λιγότερο από 29,

852
00:35:51,270 --> 00:35:52,510
μικρότερο από 34, όχι.

853
00:35:52,510 --> 00:35:55,080
Μέχρι τώρα είμαστε στην περίπτωση
μία από τουλάχιστον τρία.

854
00:35:55,080 --> 00:35:59,910
>> Αν θέλετε να εισάγετε 55 πάνω από εδώ, τι
γραμμές κώδικα ανάγκη να εκτελεστεί;

855
00:35:59,910 --> 00:36:01,890
Πώς κάνει αυτή την εικόνα της
οι άνθρωποι πρέπει να αλλάξουν;

856
00:36:01,890 --> 00:36:03,181
Τι μπορώ να κάνω με το αριστερό χέρι μου;

857
00:36:03,181 --> 00:36:04,530

858
00:36:04,530 --> 00:36:07,360
Αυτό θα πρέπει να είναι μηδενική αρχικά,
επειδή είμαι στο τέλος της λίστας.

859
00:36:07,360 --> 00:36:09,318
Και τι πρέπει να γίνει
εδώ με τον Peter, ήταν;

860
00:36:09,318 --> 00:36:10,520

861
00:36:10,520 --> 00:36:12,430
Αυτός είναι προφανώς πρόκειται να το σημείο μου.

862
00:36:12,430 --> 00:36:15,580
Γι 'αυτό και ισχυρίζονται ότι υπάρχει τουλάχιστον δύο γραμμές
του κώδικα του δείγματος κώδικα από σήμερα

863
00:36:15,580 --> 00:36:18,570
ότι πρόκειται να εφαρμόσουν αυτό
σενάριο της προσθήκης 55 στην ουρά.

864
00:36:18,570 --> 00:36:20,950
Και θα μπορούσα να έχω κάποιον hop
και μόνο αντιπροσωπεύουν 55;

865
00:36:20,950 --> 00:36:22,200
Εντάξει, θα είναι το νέο 55.

866
00:36:22,200 --> 00:36:23,580

867
00:36:23,580 --> 00:36:27,054
>> Έτσι, τώρα τι θα γίνει αν το επόμενο
σενάριο έρχεται μαζί,

868
00:36:27,054 --> 00:36:29,720
και θέλουμε να εισάγετε κατά τη
αρχίζουν ή η επικεφαλής του εν λόγω καταλόγου;

869
00:36:29,720 --> 00:36:31,100
Και τι είναι το όνομά σας, τον αριθμό 55;

870
00:36:31,100 --> 00:36:31,420
>> ΚΟΙΝΟ: Jack.

871
00:36:31,420 --> 00:36:32,295
>> DAVID J. MALAN: Jack;

872
00:36:32,295 --> 00:36:33,585
Εντάξει, ωραίο να σας γνωρίσουμε.

873
00:36:33,585 --> 00:36:34,210
Καλώς ήρθατε.

874
00:36:34,210 --> 00:36:36,640
Έτσι τώρα θα πάμε να
εισαγωγή, ας πούμε, τον αριθμό 5.

875
00:36:36,640 --> 00:36:39,840
Εδώ είναι η δεύτερη περίπτωση του
τρεις καταλήξαμε με πριν.

876
00:36:39,840 --> 00:36:43,050
Έτσι, αν 5 ανήκει στην αρχή,
ας δούμε πώς θα βρούμε ότι έξω.

877
00:36:43,050 --> 00:36:46,310
Θα προετοιμαστεί ptr μου
δείκτη για τον αριθμό 9 και πάλι.

878
00:36:46,310 --> 00:36:49,140
Και συνειδητοποίησα, oh, 5 είναι μικρότερο από 9.

879
00:36:49,140 --> 00:36:50,880
Έτσι διορθώσετε αυτή την εικόνα για μας.

880
00:36:50,880 --> 00:36:54,820
Ποιανού τα χέρια, Gabe ή Δαβίδ
ή-- τι όνομα τον αριθμό 9 του;

881
00:36:54,820 --> 00:36:55,740
>> ΚΟΙΝΟ: Jen.

882
00:36:55,740 --> 00:36:58,406
>> DAVID J. MALAN: hands-- Τζεν
ποια από τα χέρια μας πρέπει να αλλάξει;

883
00:36:58,406 --> 00:36:58,905

884
00:36:58,905 --> 00:37:00,970
Εντάξει, έτσι Gabe σημεία σε ό, τι τώρα;

885
00:37:00,970 --> 00:37:01,640
Σε μένα.

886
00:37:01,640 --> 00:37:02,750
Είμαι ο νέος κόμβος.

887
00:37:02,750 --> 00:37:04,870
Γι 'αυτό θα πρέπει ακριβώς το είδος της κίνησης
εδώ για να δείτε οπτικά.

888
00:37:04,870 --> 00:37:06,435
Και εν τω μεταξύ, τι μπορώ να επισημάνω ότι;

889
00:37:06,435 --> 00:37:07,910

890
00:37:07,910 --> 00:37:09,020
Ακόμα, όπου είμαι δείχνοντας.

891
00:37:09,020 --> 00:37:10,000
Έτσι, αυτό είναι όλο.

892
00:37:10,000 --> 00:37:13,717
Έτσι ακριβώς πραγματικά μια σειρά από διορθώσεις στον κώδικα
αυτό το συγκεκριμένο θέμα, φαίνεται.

893
00:37:13,717 --> 00:37:14,800
Εντάξει, έτσι αυτό είναι καλό.

894
00:37:14,800 --> 00:37:17,580
Και μπορεί κάποιος να είναι ένα σύμβολο κράτησης θέσης για το 5;

895
00:37:17,580 --> 00:37:18,080
Έλα πάνω.

896
00:37:18,080 --> 00:37:20,270

897
00:37:20,270 --> 00:37:21,320
Θα έχετε την επόμενη φορά.

898
00:37:21,320 --> 00:37:24,280
>> Εντάξει, έτσι now-- και
ως ένα μέρος, τα ονόματα

899
00:37:24,280 --> 00:37:28,510
Δεν έχω κάνει ρητή μνεία του δικαιώματος
τώρα, pred, δείκτης ο προκάτοχός

900
00:37:28,510 --> 00:37:31,260
και νέο δείκτη, που είναι
μόνο τα ονόματα που δίνονται

901
00:37:31,260 --> 00:37:35,280
στο δείγμα κώδικα για τους δείκτες ή
τα χέρια μου που είναι είδος προς τα γύρω.

902
00:37:35,280 --> 00:37:36,060
Ποιο είναι το όνομά σου;

903
00:37:36,060 --> 00:37:36,700
>> ΚΟΙΝΟ: Christine.

904
00:37:36,700 --> 00:37:37,100
>> DAVID J. MALAN: Christine.

905
00:37:37,100 --> 00:37:38,090
Καλώς ήρθατε.

906
00:37:38,090 --> 00:37:42,180
Εντάξει, ας εξετάσουμε τώρα
ένα ελαφρώς πιο ενοχλητικό σενάριο,

907
00:37:42,180 --> 00:37:46,350
σύμφωνα με την οποία θέλω να εισάγετε
κάτι σαν 26 σε αυτό.

908
00:37:46,350 --> 00:37:47,090
20;

909
00:37:47,090 --> 00:37:47,590
Τι;

910
00:37:47,590 --> 00:37:50,510
Αυτά are-- καλό που έχουμε αυτό το στυλό.

911
00:37:50,510 --> 00:37:51,955
Εντάξει, 20.

912
00:37:51,955 --> 00:37:53,640

913
00:37:53,640 --> 00:37:57,570
Αν κάποιος θα μπορούσε να πάρει ένα άλλο κομμάτι της
χαρτί έτοιμο, ακριβώς στην case-- εντάξει.

914
00:37:57,570 --> 00:37:58,370
Ω, ενδιαφέρουσα.

915
00:37:58,370 --> 00:37:59,760

916
00:37:59,760 --> 00:38:02,390
Λοιπόν αυτό είναι ένα παράδειγμα
ενός bug διάλεξη.

917
00:38:02,390 --> 00:38:03,894
Εντάξει ναι, ποιο είναι το όνομά σας και πάλι;

918
00:38:03,894 --> 00:38:04,560
ΚΟΙΝΟ: Τζούλια.

919
00:38:04,560 --> 00:38:07,559
DAVID J. MALAN: Τζούλια, μπορείτε να ποπ
και να προσποιείσαι ότι δεν ήταν ποτέ εκεί;

920
00:38:07,559 --> 00:38:09,040
Εντάξει, αυτό δεν συνέβη ποτέ.

921
00:38:09,040 --> 00:38:09,680
Σας ευχαριστώ.

922
00:38:09,680 --> 00:38:12,180
Έτσι, ας υποθέσουμε ότι θέλουμε να εισάγετε
Julia σε αυτό συνδεδεμένη λίστα.

923
00:38:12,180 --> 00:38:13,780
Είναι ο αριθμός 20.

924
00:38:13,780 --> 00:38:15,530
Και φυσικά αυτή είναι
πρόκειται να ανήκουν σε η

925
00:38:15,530 --> 00:38:17,521
begin-- δεν αναφέρουν τίποτα ακόμα.

926
00:38:17,521 --> 00:38:20,020
Έτσι, το χέρι σας μπορεί να είναι το είδος του
κάτω μηδενική ή κάποια αξία σκουπίδια.

927
00:38:20,020 --> 00:38:21,210
Ας πούμε την γρήγορη ιστορία.

928
00:38:21,210 --> 00:38:22,980
Είμαι δείχνοντας τον αριθμό 5 αυτή τη φορά.

929
00:38:22,980 --> 00:38:23,880
Τότε μπορώ να ελέγξω 9.

930
00:38:23,880 --> 00:38:25,130
Τότε μπορώ να ελέγξω 17.

931
00:38:25,130 --> 00:38:26,247
Τότε μπορώ να ελέγξω 22.

932
00:38:26,247 --> 00:38:27,650

933
00:38:27,650 --> 00:38:32,485
Και συνειδητοποιώ, ooh, Τζούλια
πρέπει να πάει πριν από τις 22.

934
00:38:32,485 --> 00:38:33,580

935
00:38:33,580 --> 00:38:34,660
Λοιπόν, τι πρέπει να συμβεί;

936
00:38:34,660 --> 00:38:35,786

937
00:38:35,786 --> 00:38:36,910
Ποιανού τα χέρια θα πρέπει να αλλάξει;

938
00:38:36,910 --> 00:38:38,360
Τζούλια, η δική μου, ή--
τι είναι το όνομά σας και πάλι;

939
00:38:38,360 --> 00:38:39,230
>> ΚΟΙΝΟ: Christian.

940
00:38:39,230 --> 00:38:40,060
>> DAVID J. MALAN: Χριστιανός ή;

941
00:38:40,060 --> 00:38:40,560
>> ΚΟΙΝΟ: Andy.

942
00:38:40,560 --> 00:38:40,905
>> DAVID J. MALAN: Andy.

943
00:38:40,905 --> 00:38:41,654
Χριστιανική ή Άντι;

944
00:38:41,654 --> 00:38:44,280

945
00:38:44,280 --> 00:38:45,690
Andy πρέπει να επισημάνει;

946
00:38:45,690 --> 00:38:46,780

947
00:38:46,780 --> 00:38:47,341
Τζούλια.

948
00:38:47,341 --> 00:38:47,840
Εντάξει.

949
00:38:47,840 --> 00:38:48,960
Έτσι Andy, θέλεις να επισημάνω στην Τζούλια;

950
00:38:48,960 --> 00:38:50,120
Αλλά περιμένετε ένα λεπτό.

951
00:38:50,120 --> 00:38:53,260
Στην ιστορία μέχρι σήμερα,
Είμαι το είδος του ενός

952
00:38:53,260 --> 00:38:56,800
στο τέλος, με την έννοια ότι
δείκτης είναι το πράγμα που είναι

953
00:38:56,800 --> 00:38:57,850
μετακίνηση μέσα στη λίστα.

954
00:38:57,850 --> 00:39:00,800
Θα μπορούσαμε να έχουμε ένα όνομα για τον Andy, αλλά
δεν υπάρχει μεταβλητή που ονομάζεται Andy.

955
00:39:00,800 --> 00:39:04,320
Η μόνη άλλη μεταβλητή που έχουμε είναι
πρώτο, που είναι αντιπροσωπεύεται από Gabe.

956
00:39:04,320 --> 00:39:07,690
>> Έτσι, αυτό είναι πραγματικά γιατί έτσι
τώρα δεν έχω χρειάζεται αυτό.

957
00:39:07,690 --> 00:39:10,846
Αλλά τώρα στην οθόνη υπάρχει
αναφέρουμε και πάλι από προβλ δείκτη.

958
00:39:10,846 --> 00:39:11,970
Έτσι, επιτρέψτε μου να είμαι πιο σαφής.

959
00:39:11,970 --> 00:39:14,820
Αν αυτό είναι δείκτης, είχα την καλύτερη
πάρετε μια λίγο πιο έξυπνο

960
00:39:14,820 --> 00:39:15,950
για την επανάληψη μου.

961
00:39:15,950 --> 00:39:19,580
Αν δεν σας πειράζει να μου περνάει εδώ
και πάλι, δείχνοντας εδώ, δείχνοντας εδώ.

962
00:39:19,580 --> 00:39:22,500
Αλλά επιτρέψτε μου να έχουν μια pred δείκτη,
δείκτη προκάτοχό του, ότι είναι

963
00:39:22,500 --> 00:39:24,740
το είδος του δείχνοντας το
στοιχείο Ήμουν ακριβώς στο.

964
00:39:24,740 --> 00:39:27,330
Έτσι, όταν πάω εδώ, τώρα
αριστερά ενημερώσεις χέρι μου.

965
00:39:27,330 --> 00:39:29,370
Όταν πάω εδώ αριστερά ενημερώσεις χέρι μου.

966
00:39:29,370 --> 00:39:33,090
Και τώρα δεν έχω μόνο ένα δείκτη για να
το στοιχείο που πηγαίνει μετά Julia,

967
00:39:33,090 --> 00:39:36,300
Έχω ακόμα ένα δείκτη για να
Andy, το στοιχείο πριν.

968
00:39:36,300 --> 00:39:39,430
Έτσι έχετε πρόσβαση, κατ 'ουσίαν,
φρυγανιά, αν θέλετε,

969
00:39:39,430 --> 00:39:41,500
σε όλες τις απαιτούμενες δείκτες.

970
00:39:41,500 --> 00:39:43,710
>> Έτσι, αν είμαι δείχνοντας
Andy και εγώ επίσης δείχνει

971
00:39:43,710 --> 00:39:47,105
στο Christian, του οποίου τα χέρια
πρέπει τώρα να τονιστεί αλλού;

972
00:39:47,105 --> 00:39:48,770

973
00:39:48,770 --> 00:39:51,960
Έτσι Andy μπορεί πλέον σημείο στο Julia.

974
00:39:51,960 --> 00:39:54,460
Julia μπορεί πλέον σημείο στο χριστιανικό.

975
00:39:54,460 --> 00:39:56,950
Επειδή μπορεί να αντιγράψει μου
δείκτη του δεξιού χεριού του.

976
00:39:56,950 --> 00:40:00,044
Και αυτό σας βάζει αποτελεσματικά
πίσω σε αυτό το μέρος εδώ.

977
00:40:00,044 --> 00:40:02,460
Έτσι, με λίγα λόγια, ακόμη και αν αυτό
Μας παίρνει το είδος του για πάντα

978
00:40:02,460 --> 00:40:04,510
να ενημερώσει πραγματικά ένα
συνδεδεμένη λίστα, συνειδητοποιούν

979
00:40:04,510 --> 00:40:06,580
ότι οι εργασίες
είναι σχετικά απλή.

980
00:40:06,580 --> 00:40:10,030
Είναι από ένα, δύο, τρία
γραμμές κώδικα τελικά.

981
00:40:10,030 --> 00:40:12,780
Αλλά τυλιγμένο γύρω από εκείνους που
γραμμές κώδικα πιθανώς

982
00:40:12,780 --> 00:40:16,350
Είναι ένα κομμάτι της λογικής που ουσιαστικά
θέτει το ερώτημα, πού είμαστε;

983
00:40:16,350 --> 00:40:18,970
Είμαστε στην αρχή,
η μέση ή το τέλος;

984
00:40:18,970 --> 00:40:21,890
>> Τώρα, υπάρχουν σίγουρα κάποια άλλη
δραστηριότητες που θα μπορούσαν να εφαρμόσουν.

985
00:40:21,890 --> 00:40:24,880
Και αυτές οι εικόνες εδώ ακριβώς απεικονίζουν
τι κάναμε με τους ανθρώπους.

986
00:40:24,880 --> 00:40:26,080
Τι γίνεται με την αφαίρεση;

987
00:40:26,080 --> 00:40:30,650
Αν θέλω να, για παράδειγμα,
αφαιρέσετε τον αριθμό 34 ή 55,

988
00:40:30,650 --> 00:40:34,680
Θα ήθελα να έχουμε το ίδιο είδος κώδικα,
αλλά Πάω να χρειαστεί μία ή δύο βήματα.

989
00:40:34,680 --> 00:40:36,110
Γιατί ό, τι είναι νέο;

990
00:40:36,110 --> 00:40:40,460
Αν μπορώ να αφαιρέσω κάποιον στο τέλος,
όπως τον αριθμό 55 και στη συνέχεια 34,

991
00:40:40,460 --> 00:40:42,995
τι πρέπει να αλλάξει, όπως το κάνω αυτό;

992
00:40:42,995 --> 00:40:44,870
Δεν έχω να evict--
τι είναι το όνομά σας και πάλι;

993
00:40:44,870 --> 00:40:45,380
>> ΚΟΙΝΟ: Jack.

994
00:40:45,380 --> 00:40:46,255
>> DAVID J. MALAN: Jack.

995
00:40:46,255 --> 00:40:49,770
Θα πρέπει όχι μόνο να evict-- ελεύθερη Jack,
τόσο κυριολεκτικά καλέστε δωρεάν Jack, ή τουλάχιστον

996
00:40:49,770 --> 00:40:53,530
ο δείκτης εκεί, αλλά τώρα
τι πρέπει να αλλάξει με τον Πέτρο;

997
00:40:53,530 --> 00:40:55,510
Το χέρι του καλύτερη εκκίνηση προς τα κάτω.

998
00:40:55,510 --> 00:40:59,300
Επειδή το συντομότερο Καλώ δωρεάν
Jack, αν Πέτρου ακόμα δείχνοντας Jack

999
00:40:59,300 --> 00:41:02,530
και ως εκ τούτου, να κρατήσει διέρχονται
ο κατάλογος και η πρόσβαση αυτή δείκτη,

1000
00:41:02,530 --> 00:41:05,650
ότι όταν παλιός φίλος του κατακερματισμού μας
σφάλμα θα μπορούσε πράγματι να κλωτσήσει in.

1001
00:41:05,650 --> 00:41:07,860
Επειδή έχουμε δώσει το
πίσω μνήμης με τον Τζακ.

1002
00:41:07,860 --> 00:41:10,760
>> Μπορείτε να μείνετε εκεί
αδέξια για μια στιγμή.

1003
00:41:10,760 --> 00:41:13,410
Επειδή έχουμε μόνο ένα ζευγάρι
τελικές εργασίες για να εξετάσει.

1004
00:41:13,410 --> 00:41:15,600
Αφαίρεση της κεφαλής της λίστας,
ή ο beginning-- και αυτό κάποιου

1005
00:41:15,600 --> 00:41:16,349
λίγο ενοχλητικό.

1006
00:41:16,349 --> 00:41:19,640
Επειδή έχουμε να γνωρίζουμε ότι Gabe
είναι το είδος των ειδικών σε αυτό το πρόγραμμα.

1007
00:41:19,640 --> 00:41:21,440
Διότι πράγματι, έχει τη δική του δείκτη.

1008
00:41:21,440 --> 00:41:24,860
Δεν είναι μόνο που επισήμανε σε,
όπως σχεδόν όλοι οι άλλοι εδώ.

1009
00:41:24,860 --> 00:41:28,112
>> Έτσι, όταν η κεφαλή της λίστας είναι
απομακρύνονται, τα χέρια του οποίου πρέπει να αλλάξει τώρα;

1010
00:41:28,112 --> 00:41:29,070
Ποιο είναι το όνομά σας και πάλι;

1011
00:41:29,070 --> 00:41:29,450
>> ΚΟΙΝΟ: Christine.

1012
00:41:29,450 --> 00:41:31,408
>> DAVID J. MALAN: Είμαι χάλια
σε ονόματα, προφανώς.

1013
00:41:31,408 --> 00:41:34,011
Έτσι, Christine και Gabe,
των οποίων τα χέρια θα πρέπει να αλλάξει

1014
00:41:34,011 --> 00:41:36,510
όταν προσπαθούμε να αφαιρέσετε Christine,
αριθμός 5, από την εικόνα;

1015
00:41:36,510 --> 00:41:37,550

1016
00:41:37,550 --> 00:41:38,820
Εντάξει, ας κάνουμε Gabe.

1017
00:41:38,820 --> 00:41:40,950
Gabe πρόκειται να επισημάνω,
κατά πάσα πιθανότητα, στο νούμερο 9.

1018
00:41:40,950 --> 00:41:42,230

1019
00:41:42,230 --> 00:41:44,642
Ποιο είναι το επόμενο όμως θα πρέπει να συμβεί;

1020
00:41:44,642 --> 00:41:46,600
ΚΟΙΝΟ: Christine θα πρέπει να
είναι null [δεν ακούγεται].

1021
00:41:46,600 --> 00:41:50,244
DAVID J. MALAN: Εντάξει, θα έπρεπε ίσως
make-- άκουσα "null" κάπου.

1022
00:41:50,244 --> 00:41:51,410
ΚΟΙΝΟ: Null και χωρίς αυτήν.

1023
00:41:51,410 --> 00:41:51,855
DAVID J. MALAN: Null τι;

1024
00:41:51,855 --> 00:41:53,074
ΚΟΙΝΟ: Null και χωρίς αυτήν.

1025
00:41:53,074 --> 00:41:54,490
DAVID J. MALAN: Null και χωρίς αυτήν.

1026
00:41:54,490 --> 00:41:55,422
Έτσι αυτό είναι πολύ εύκολη.

1027
00:41:55,422 --> 00:41:58,380
Και αυτό είναι τέλειο ότι είστε τώρα το είδος
να στέκεται εκεί, δεν ανήκουν.

1028
00:41:58,380 --> 00:42:00,430
Επειδή έχετε πάει
αποσυνδεδεμένη από τη λίστα.

1029
00:42:00,430 --> 00:42:02,820
Έχετε αποτελεσματικά ήταν
ορφανά από τη λίστα.

1030
00:42:02,820 --> 00:42:07,770
Και έτσι είχαμε καλύτερη καλέστε δωρεάν τώρα και στο εξής
Christine για να δώσουμε αυτή τη μνήμη πίσω.

1031
00:42:07,770 --> 00:42:10,240
Διαφορετικά, κάθε φορά που
διαγράψετε ένα κόμβο από τη λίστα

1032
00:42:10,240 --> 00:42:14,230
θα μπορούσε να κάνει τη λίστα
μικρότερη, αλλά στην πραγματικότητα δεν μειώνεται

1033
00:42:14,230 --> 00:42:15,096
το μέγεθος στη μνήμη.

1034
00:42:15,096 --> 00:42:17,720
Και έτσι, αν συνεχίσουμε να προσθέτουμε και
προσθέτοντας, προσθέτοντας πράγματα στη λίστα,

1035
00:42:17,720 --> 00:42:19,280
ο υπολογιστής μου θα μπορούσε να πάρει πιο αργή
και πιο αργή και πιο αργά,

1036
00:42:19,280 --> 00:42:21,740
επειδή είμαι εξαντλείται
μνήμη, ακόμα και αν δεν είμαι στην πραγματικότητα

1037
00:42:21,740 --> 00:42:25,580
χρησιμοποιώντας bytes Κριστίν
της μνήμης πια.

1038
00:42:25,580 --> 00:42:28,500
>> Έτσι, στο τέλος υπάρχουν και άλλες
σενάρια, από course-- αφαίρεση

1039
00:42:28,500 --> 00:42:30,640
στη μέση, την απομάκρυνση
στο τέλος, όπως είδαμε.

1040
00:42:30,640 --> 00:42:32,348
Αλλά το πιο ενδιαφέρον
πρόκληση τώρα είναι

1041
00:42:32,348 --> 00:42:34,770
θα είναι να εξετάσει ακριβώς
τι ο χρόνος είναι.

1042
00:42:34,770 --> 00:42:36,640
Έτσι, όχι μόνο μπορεί να σας κρατήσει σας
κομμάτια από χαρτί, αν, Gabe,

1043
00:42:36,640 --> 00:42:38,640
δεν θα με πείραζε να δίνει
ο καθένας μια μπάλα για το άγχος.

1044
00:42:38,640 --> 00:42:42,100
Σας ευχαριστώ πάρα πολύ για την συνδεδεμένη λίστα μας
των εθελοντών εδώ, αν μπορούσε.

1045
00:42:42,100 --> 00:42:45,320
>> [Χειροκρότημα]

1046
00:42:45,320 --> 00:42:46,700
>> DAVID J. MALAN: Εντάξει.

1047
00:42:46,700 --> 00:42:51,110
Έτσι, ένα ζευγάρι των αναλυτικών
ερωτήσεις στη συνέχεια, αν μπορούσα.

1048
00:42:51,110 --> 00:42:59,670
Έχουμε δει αυτή την παράσταση πριν,
O μεγάλος και ωμέγα, άνω φράγματα

1049
00:42:59,670 --> 00:43:02,520
και χαμηλότερα όρια για την
χρόνο από κάποιο αλγόριθμο που εκτελείται.

1050
00:43:02,520 --> 00:43:04,950
Έτσι, ας αναλογιστούμε μόνο
μια-δυο ερωτήσεις.

1051
00:43:04,950 --> 00:43:07,090
>> Ένα, και το είπαμε
πριν, ποια είναι η λειτουργία

1052
00:43:07,090 --> 00:43:10,647
χρόνος αναζήτησης για ένα
κατάλογος από την άποψη των μεγάλων O;

1053
00:43:10,647 --> 00:43:13,480
Τι είναι ένα άνω φράγμα για τη λειτουργία
χρόνο ψάχνοντας μια συνδεδεμένη λίστα

1054
00:43:13,480 --> 00:43:16,340
όπως εφαρμόζεται από τους εθελοντές μας εδώ;

1055
00:43:16,340 --> 00:43:17,820
Είναι μεγάλη O του n, γραμμική.

1056
00:43:17,820 --> 00:43:20,630
Επειδή, στη χειρότερη περίπτωση,
το στοιχείο, όπως το 55,

1057
00:43:20,630 --> 00:43:23,830
θα μπορούσε να ψάχνει για μπορεί να είναι, όπου
Jack ήταν, σε όλη τη διαδρομή στο τέλος.

1058
00:43:23,830 --> 00:43:28,250
Και, δυστυχώς, σε αντίθεση με μια σειρά
δεν μπορεί να πάρει φανταχτερά αυτή τη φορά.

1059
00:43:28,250 --> 00:43:31,820
Ακόμα κι αν όλοι οι άνθρωποι μας ήταν
ταξινομούνται από μικρά στοιχεία, 5,

1060
00:43:31,820 --> 00:43:35,900
σε όλη τη διαδρομή μέχρι το μεγαλύτερο στοιχείο,
55, αυτό είναι συνήθως ένα καλό πράγμα.

1061
00:43:35,900 --> 00:43:38,815
Αλλά αυτό που κάνει αυτή την υπόθεση
δεν επιτρέπουν πλέον να κάνουμε;

1062
00:43:38,815 --> 00:43:39,775

1063
00:43:39,775 --> 00:43:40,650
ΚΟΙΝΟ: [δεν ακούγεται]

1064
00:43:40,650 --> 00:43:40,920
DAVID J. MALAN: Πείτε ξανά;

1065
00:43:40,920 --> 00:43:41,800
ΚΟΙΝΟ: τυχαίας προσπέλασης.

1066
00:43:41,800 --> 00:43:43,049
DAVID J. MALAN: τυχαίας προσπέλασης.

1067
00:43:43,049 --> 00:43:46,330
Και με τη σειρά του αυτό σημαίνει ότι μπορούμε όχι
χρησιμοποιούν πλέον αδύναμο μηδενικά, διαίσθηση,

1068
00:43:46,330 --> 00:43:49,365
και τον κατάφωρο χρησιμοποιώντας δυαδικό
αναζητήσετε και να διαίρει και βασίλευε.

1069
00:43:49,365 --> 00:43:51,240
Διότι ακόμα κι αν
οι άνθρωποι θα μπορούσαν προφανώς

1070
00:43:51,240 --> 00:43:54,610
δείτε ότι ο Andy ή Χριστιανός
περίπου στη μέση της λίστας,

1071
00:43:54,610 --> 00:43:57,670
γνωρίζουμε μόνο ότι ως
υπολογιστή με αποκορύφωση τη λίστα

1072
00:43:57,670 --> 00:43:59,029
από την αρχή.

1073
00:43:59,029 --> 00:44:00,570
Έτσι έχουμε δώσει μέχρι αυτή την τυχαία πρόσβαση.

1074
00:44:00,570 --> 00:44:04,380
>> Έτσι, μεγάλη O ν τώρα είναι το ανώτερο
δεσμεύεται για το χρόνο αναζήτησης.

1075
00:44:04,380 --> 00:44:07,920
Τι γίνεται με το ωμέγα της αναζήτησης;

1076
00:44:07,920 --> 00:44:11,535
Ποιο είναι το κατώτερο όριο για την αναζήτηση
για κάποιο αριθμό σε αυτή τη λίστα;

1077
00:44:11,535 --> 00:44:12,410
ΚΟΙΝΟ: [δεν ακούγεται]

1078
00:44:12,410 --> 00:44:13,040
DAVID J. MALAN: Πείτε ξανά;

1079
00:44:13,040 --> 00:44:13,420
ΚΟΙΝΟ: One.

1080
00:44:13,420 --> 00:44:13,800
DAVID J. MALAN: One.

1081
00:44:13,800 --> 00:44:14,760
Τόσο σταθερό χρόνο.

1082
00:44:14,760 --> 00:44:17,020
Στην καλύτερη περίπτωση, Christine είναι
πράγματι στην αρχή της λίστας.

1083
00:44:17,020 --> 00:44:19,020
Και ψάχνουμε για
αριθμός 5, έτσι τη βρήκαμε.

1084
00:44:19,020 --> 00:44:19,787
Έτσι, δεν είναι μεγάλη υπόθεση.

1085
00:44:19,787 --> 00:44:22,370
Αλλά πήρε να είναι σε η
ξεκινώντας από τη λίστα σε αυτή την περίπτωση.

1086
00:44:22,370 --> 00:44:23,745
Τι γίνεται με κάτι σαν Διαγραφή;

1087
00:44:23,745 --> 00:44:24,717

1088
00:44:24,717 --> 00:44:26,300
Τι γίνεται αν θέλετε να διαγράψετε ένα στοιχείο;

1089
00:44:26,300 --> 00:44:29,200
Τι είναι το άνω όριο και κάτω φράγμα
σχετικά με τη διαγραφή κάτι από ένα συνδεδεμένο

1090
00:44:29,200 --> 00:44:29,699
λίστα;

1091
00:44:29,699 --> 00:44:35,195

1092
00:44:35,195 --> 00:44:36,070
ΚΟΙΝΟ: [δεν ακούγεται]

1093
00:44:36,070 --> 00:44:36,420
DAVID J. MALAN: Πείτε ξανά;

1094
00:44:36,420 --> 00:44:37,067
ΚΟΙΝΟ: n.

1095
00:44:37,067 --> 00:44:38,900
DAVID J. MALAN: n είναι
Πράγματι, το ανώτατο όριο.

1096
00:44:38,900 --> 00:44:41,700
Επειδή στη χειρότερη περίπτωση θα προσπαθήσουμε
να διαγράψετε Jack, όπως μόλις κάναμε.

1097
00:44:41,700 --> 00:44:43,050
Αυτός είναι όλος ο τρόπος στο τέλος.

1098
00:44:43,050 --> 00:44:45,419
Μας παίρνει για πάντα, ή
n βήματα για να τον βρει.

1099
00:44:45,419 --> 00:44:46,460
Έτσι, αυτό είναι ένα άνω φράγμα.

1100
00:44:46,460 --> 00:44:47,430
Αυτό είναι γραμμική, βέβαιος.

1101
00:44:47,430 --> 00:44:50,970
Και η καλύτερη περίπτωση χρόνος τρέχει, ή
τα χαμηλότερα όρια στην καλύτερη περίπτωση

1102
00:44:50,970 --> 00:44:51,975
θα είναι σταθερό χρόνο.

1103
00:44:51,975 --> 00:44:54,600
Επειδή ίσως προσπαθούμε να διαγράψετε
Christine, και εμείς απλά να πάρετε τυχεροί

1104
00:44:54,600 --> 00:44:55,558
αυτή είναι στην αρχή.

1105
00:44:55,558 --> 00:44:56,350
Τώρα, περιμένετε ένα λεπτό.

1106
00:44:56,350 --> 00:44:59,370
Gabe ήταν, επίσης, στην αρχή,
και θα έπρεπε επίσης να ενημερώσετε Gabe.

1107
00:44:59,370 --> 00:45:01,150
Έτσι, ότι δεν ήταν απλά ένα βήμα.

1108
00:45:01,150 --> 00:45:04,210
Έτσι είναι πράγματι σταθερές
ώρα, στην καλύτερη περίπτωση,

1109
00:45:04,210 --> 00:45:06,345
για να αφαιρέσετε το μικρότερο στοιχείο;

1110
00:45:06,345 --> 00:45:07,360

1111
00:45:07,360 --> 00:45:10,960
Είναι, αν και θα μπορούσε να είναι δύο,
τρεις, ή ακόμη και 100 γραμμές κώδικα,

1112
00:45:10,960 --> 00:45:14,000
αν είναι το ίδιο αριθμό
γραμμές, όχι σε κάποιο βρόχο,

1113
00:45:14,000 --> 00:45:16,577
και ανεξάρτητο από το μέγεθος
από τη λίστα, απολύτως.

1114
00:45:16,577 --> 00:45:18,660
Διαγραφή του στοιχείου σε
η αρχή της λίστας,

1115
00:45:18,660 --> 00:45:21,940
ακόμα κι αν έχουμε να κάνουμε με
Gabe, εξακολουθεί να είναι σταθερό χρόνο.

1116
00:45:21,940 --> 00:45:24,220
>> Έτσι, αυτό φαίνεται σαν μια
τεράστιο βήμα προς τα πίσω.

1117
00:45:24,220 --> 00:45:27,000
Και τι χάσιμο χρόνου
αν, σε μία εβδομάδα και εβδομάδες

1118
00:45:27,000 --> 00:45:30,250
μηδέν είχαμε όχι μόνο
Κωδικός ψευδοκώδικα αλλά πραγματικό κώδικα

1119
00:45:30,250 --> 00:45:35,780
να εφαρμόσει κάτι που είναι log
βάση n, ή να συνδεθείτε, μάλλον, από n, βάσης 2,

1120
00:45:35,780 --> 00:45:37,150
από την άποψη του χρόνου λειτουργίας του.

1121
00:45:37,150 --> 00:45:40,710
Έτσι, γιατί στο καλό θα θέλουμε να αρχίσουμε
χρησιμοποιώντας κάτι σαν μια συνδεδεμένη λίστα;

1122
00:45:40,710 --> 00:45:41,517
Ναι.

1123
00:45:41,517 --> 00:45:44,022
>> ΚΟΙΝΟ: Έτσι, μπορείτε να προσθέσετε
στοιχεία στη συστοιχία.

1124
00:45:44,022 --> 00:45:46,230
DAVID J. MALAN: Έτσι, μπορείτε να
προσθέσετε στοιχεία στη συστοιχία.

1125
00:45:46,230 --> 00:45:47,550
Και αυτό είναι πάρα πολύ θεματικό.

1126
00:45:47,550 --> 00:45:49,740
Και εμείς θα συνεχίσουμε να βλέπουμε
αυτό, αυτό το εμπόριο-off, πολύ

1127
00:45:49,740 --> 00:45:51,573
όπως έχουμε δει μια
trade-off με συγχώνευση ταξινόμησης.

1128
00:45:51,573 --> 00:45:54,606
Θα μπορούσε πραγματικά να επιταχύνει
αναζήτηση ή ταξινόμηση, μάλλον,

1129
00:45:54,606 --> 00:45:57,480
αν περάσουν λίγο περισσότερο χώρο και
έχουν ένα επιπλέον κομμάτι της μνήμης

1130
00:45:57,480 --> 00:45:58,760
ή μια σειρά για συγχώνευση ταξινόμησης.

1131
00:45:58,760 --> 00:46:01,270
Αλλά ξοδεύουμε περισσότερα
χώρο, αλλά έχουμε εξοικονόμηση χρόνου.

1132
00:46:01,270 --> 00:46:04,820
Σε αυτή την περίπτωση, είμαστε
δίνοντας το χρόνο, αλλά είμαστε

1133
00:46:04,820 --> 00:46:08,170
κερδίζει την ευελιξία,
δυναμισμό, αν θέλετε,

1134
00:46:08,170 --> 00:46:10,280
η οποία είναι αναμφισβήτητα ένα θετικό στοιχείο.

1135
00:46:10,280 --> 00:46:11,520
>> Είμαστε, επίσης, οι δαπάνες χώρο.

1136
00:46:11,520 --> 00:46:13,710
Με ποια έννοια είναι ένα συνδεδεμένο
λίστα πιο ακριβά

1137
00:46:13,710 --> 00:46:15,700
από την άποψη του χώρου από μια σειρά;

1138
00:46:15,700 --> 00:46:18,379

1139
00:46:18,379 --> 00:46:19,920
Πού είναι ο επιπλέον χώρος που προέρχονται από;

1140
00:46:19,920 --> 00:46:20,460
Ναι;

1141
00:46:20,460 --> 00:46:21,800
>> ΚΟΙΝΟ: [δεν ακούγεται] δείκτη.

1142
00:46:21,800 --> 00:46:23,310
>> DAVID J. MALAN: Ναι, μπορούμε
έχουν επίσης το δείκτη.

1143
00:46:23,310 --> 00:46:25,560
Έτσι, αυτό είναι ενοχλητικό minorly
ότι δεν είμαι πλέον

1144
00:46:25,560 --> 00:46:27,780
I αποθήκευση μόνο ένα int
να αντιπροσωπεύουν ένα int.

1145
00:46:27,780 --> 00:46:30,990
Είμαι αποθήκευση ενός int και ένα
δείκτη, η οποία είναι επίσης 32 bits.

1146
00:46:30,990 --> 00:46:33,470
Έτσι είμαι κυριολεκτικά διπλασιασμό
το ποσό του χώρου που εμπλέκονται.

1147
00:46:33,470 --> 00:46:36,040
Έτσι, αυτό είναι ένα trade-off, αλλά
ότι είναι στην περίπτωση της int.

1148
00:46:36,040 --> 00:46:39,580
Ας υποθέσουμε ότι δεν είστε αποθήκευση int,
αλλά ας υποθέσουμε ότι κάθε ένα από αυτά τα ορθογώνια

1149
00:46:39,580 --> 00:46:43,290
ή το καθένα από αυτά τον άνθρωπο, που αντιπροσωπεύουν
μια λέξη, μια αγγλική λέξη που

1150
00:46:43,290 --> 00:46:46,430
μπορεί να είναι πέντε χαρακτήρες, 10
χαρακτήρες, ίσως ακόμη περισσότερο.

1151
00:46:46,430 --> 00:46:49,940
Στη συνέχεια, προσθέτοντας μόλις 32 περισσότερα bits
μπορεί να είναι λιγότερο από ένα big deal.

1152
00:46:49,940 --> 00:46:52,160
>> Τι θα συμβεί αν κάθε ένα από τους μαθητές
στη διαδήλωση

1153
00:46:52,160 --> 00:46:55,107
ήταν κυριολεκτικά structs μαθητή ότι
έχουν ονόματα και τα σπίτια και ίσως

1154
00:46:55,107 --> 00:46:57,065
αριθμούς τηλεφώνου και Twitter
λαβές και τα παρόμοια.

1155
00:46:57,065 --> 00:46:59,564
Έτσι, όλα τα πεδία που ξεκινήσαμε
μιλάμε για την άλλη μέρα,

1156
00:46:59,564 --> 00:47:02,410
πολύ λιγότερο από ένα big deal, όπως
κόμβους μας πάρει πιο ενδιαφέρουσα

1157
00:47:02,410 --> 00:47:05,972
και μεγάλη για να περάσετε, ε, ένα πρόσθετο
pointer ακριβώς για να τους συνδέουν μεταξύ τους.

1158
00:47:05,972 --> 00:47:07,180
Αλλά, πράγματι, είναι ένα trade-off.

1159
00:47:07,180 --> 00:47:09,560
Και πράγματι, ο κώδικας είναι
πιο περίπλοκη, όπως θα

1160
00:47:09,560 --> 00:47:11,770
δείτε από ξεφυλλίζει
ότι το συγκεκριμένο παράδειγμα.

1161
00:47:11,770 --> 00:47:14,302
Αλλά τι θα γινόταν αν δεν υπήρχαν
κάποια Άγιο Δισκοπότηρο εδώ.

1162
00:47:14,302 --> 00:47:17,010
Τι θα συμβεί αν δεν κάνουμε ένα βήμα
προς τα πίσω, αλλά ένα τεράστιο βήμα προς τα εμπρός

1163
00:47:17,010 --> 00:47:19,180
και να εφαρμόσουν ένα στοιχεία
δομή μέσω της οποίας εμείς

1164
00:47:19,180 --> 00:47:22,870
μπορούν να βρουν στοιχεία, όπως ο Jack ή
Christine ή οποιαδήποτε άλλα στοιχεία

1165
00:47:22,870 --> 00:47:25,870
σε αυτήν την σειρά σε πραγματικό συνεχή χρόνο;

1166
00:47:25,870 --> 00:47:26,920
Αναζήτηση είναι σταθερή.

1167
00:47:26,920 --> 00:47:28,320
Διαγραφή είναι σταθερή.

1168
00:47:28,320 --> 00:47:29,570
Ένθετο είναι σταθερή.

1169
00:47:29,570 --> 00:47:32,260
Όλες αυτές οι λειτουργίες είναι σταθερές.

1170
00:47:32,260 --> 00:47:33,750
Αυτό θα είναι το ιερό δισκοπότηρο μας.

1171
00:47:33,750 --> 00:47:36,690
Και αυτό είναι όπου εμείς
θα πάρει την επόμενη φορά.

1172
00:47:36,690 --> 00:47:38,600
Τα λέμε τότε.

1173
00:47:38,600 --> 00:47:39,371