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

2
00:00:00,500 --> 00:00:11,137
[Mūzikas atskaņošanai]

3
00:00:11,137 --> 00:00:12,220
DAVID J. Malan: Nu labi.

4
00:00:12,220 --> 00:00:13,950
Tas ir CS50.

5
00:00:13,950 --> 00:00:18,560
Šī ir nedēļa pieci turpinājās, un mēs
ir dažas labas ziņas un dažas sliktas ziņas.

6
00:00:18,560 --> 00:00:21,140
Tik laba ziņa ir tā, ka CS50
uzsāk šo piektdien.

7
00:00:21,140 --> 00:00:24,430
Ja vēlaties mums pievienoties,
dodies uz parasto URL šeit.

8
00:00:24,430 --> 00:00:28,670
Pat labāk ziņas, ne lekcija
tas nāk pirmdiena 13.

9
00:00:28,670 --> 00:00:31,970
Nedaudz mazāk labāku ziņas,
viktorīna nulle ir nākamo trešdien.

10
00:00:31,970 --> 00:00:33,840
Sīkāka informācija var būt
atrast šajā URL šeit.

11
00:00:33,840 --> 00:00:36,340
Un nākamo pāris dienām
mēs būsim aizpildot tukšās

12
00:00:36,340 --> 00:00:39,234
attiecībā uz telpām
ka mēs esam aizsargātas.

13
00:00:39,234 --> 00:00:41,400
Labāka ziņa ir tā, ka tur būs
būt pārskatīšanu kursu mēroga

14
00:00:41,400 --> 00:00:43,570
sesija šo nāk
Pirmdiena vakarā.

15
00:00:43,570 --> 00:00:46,270
Sekojiet līdzi kursu s
Mājas atrašanās vieta un informāciju.

16
00:00:46,270 --> 00:00:49,290
Sekcijas, pat ja tas ir
svētki, arī tiksies arī.

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

18
00:00:50,490 --> 00:00:52,940
Labākā ziņa, lekciju nākamajā piektdienā.

19
00:00:52,940 --> 00:00:56,220
Tātad šī ir tradīcija mums
ir, kā vienu mācību.

20
00:00:56,220 --> 00:00:58,100
Just-- tas būs pārsteidzošs.

21
00:00:58,100 --> 00:01:02,510
Jūs redzēsiet lietas, piemēram,
nemainīgs laika datu struktūras

22
00:01:02,510 --> 00:01:04,730
un hash tabulas, kokus un mēģina.

23
00:01:04,730 --> 00:01:07,150
Un mēs runājam par dzimšanas dienas problēmām.

24
00:01:07,150 --> 00:01:09,440
Viss ķekars sīkumi
gaida nākamajā piektdienā.

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
Tik un tā.

28
00:01:13,190 --> 00:01:17,080
>> Tik atgādināt, ka mēs esam bijuši
koncentrējoties uz šo ainu par to, kas ir

29
00:01:17,080 --> 00:01:18,980
iekšpusē mūsu datora atmiņā.

30
00:01:18,980 --> 00:01:22,875
Tātad atmiņu vai RAM ir, ja programmas
pastāv, kamēr jūs tos palaižot.

31
00:01:22,875 --> 00:01:25,215
Ja jūs dubultklikšķi
ikonas, lai palaistu dažas programmas

32
00:01:25,215 --> 00:01:27,520
vai veiciet dubultklikšķi
ikona atvērt kādu failu,

33
00:01:27,520 --> 00:01:30,430
tas ir piekrauts no cietā
vadīt vai cietvielu disks

34
00:01:30,430 --> 00:01:34,190
RAM, brīvpiekļuves atmiņas, kur
tā dzīvo, kamēr atslēdz strāvas padevi,

35
00:01:34,190 --> 00:01:36,700
klēpjdators vāks aizveras,
vai jūs atmest programmu.

36
00:01:36,700 --> 00:01:38,960
>> Tagad, atmiņa, no
kas jums, iespējams, ir

37
00:01:38,960 --> 00:01:41,950
1 gigabaitu šajās dienās, 2
gigabaiti, vai pat daudz vairāk,

38
00:01:41,950 --> 00:01:44,420
parasti tiek izklāstīts
attiecībā uz konkrētu programmu

39
00:01:44,420 --> 00:01:47,170
šāda veida taisnstūra
konceptuālais modelis

40
00:01:47,170 --> 00:01:50,860
kuru mums ir stack apakšā
un ķekars citas lietas augšpusē.

41
00:01:50,860 --> 00:01:53,140
Lieta pašā augšā
mēs esam redzējuši par šo attēlu

42
00:01:53,140 --> 00:01:55,670
agrāk, bet nekad nav runājuši par
ir tā saucamā teksta segments.

43
00:01:55,670 --> 00:01:58,419
Teksts segments ir tikai iedomātā veids
, sakot nullēm un tiem, kas

44
00:01:58,419 --> 00:02:01,150
sacerēt savu faktisko apkopoti programmu.

45
00:02:01,150 --> 00:02:03,910
>> Tātad, ja jūs dubultklikšķi
Microsoft Word uz jūsu Mac vai PC,

46
00:02:03,910 --> 00:02:08,030
vai tad, kad jūs darbināt dot slash Mario uz
Linux dators jūsu termināla logā,

47
00:02:08,030 --> 00:02:12,460
uz nullēm un tiem, kas veido
Vārds vai Mario īslaicīgi tiek uzglabāti

48
00:02:12,460 --> 00:02:16,610
Jūsu datora RAM tā saukto
teksta segments par konkrētu programmu.

49
00:02:16,610 --> 00:02:19,080
Turpmāk, ka iet inicializēts
un neinicializētu dati.

50
00:02:19,080 --> 00:02:22,655
Tas ir sīkumi, piemēram, globālo mainīgo,
ka mēs esam nav izmantoti daudzi,

51
00:02:22,655 --> 00:02:24,910
bet reizēm mēs esam
bija globālo mainīgo

52
00:02:24,910 --> 00:02:28,819
vai statiski noteiktas virknes, kas
ir grūti kodēta vārdus kā "hello"

53
00:02:28,819 --> 00:02:31,860
, kas nav ņemts no lietotāja
kas ir iekodēts savā programmā.

54
00:02:31,860 --> 00:02:34,230
>> Tagad, uz leju apakšā mēs
ir ts kaudze.

55
00:02:34,230 --> 00:02:37,665
Un kaudze, līdz šim mēs esam bijuši
izmantojot, kādos nolūkos?

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

57
00:02:39,706 --> 00:02:40,997
Kas kaudze tikuši izmantoti?

58
00:02:40,997 --> 00:02:41,160
Yeah?

59
00:02:41,160 --> 00:02:42,070
>> Mērķauditorija: funkcijas.

60
00:02:42,070 --> 00:02:43,320
>> DAVID J. Malan: For funkcijām?

61
00:02:43,320 --> 00:02:44,980
Kādā jēga to funkciju?

62
00:02:44,980 --> 00:02:48,660
>> AUDITORIJA: Kad jūs zvanu funkciju,
argumenti tiek kopēti uz kaudze.

63
00:02:48,660 --> 00:02:49,660
>> DAVID J. Malan: Tieši tā.

64
00:02:49,660 --> 00:02:52,650
Kad jūs zvanu funkciju, tā
argumenti tiek kopēti uz kaudze.

65
00:02:52,650 --> 00:02:56,330
Tāpēc jebkuri krustiņus vai Y ir vai ir vai B s
ka jūs iet uz funkciju

66
00:02:56,330 --> 00:02:58,680
laiku tiek likts uz
tā saukto kaudze,

67
00:02:58,680 --> 00:03:02,000
tāpat kā viens no Annenberg
ēdamzāle paplātes, kā arī lietas

68
00:03:02,000 --> 00:03:03,190
piemēram, vietējās mainīgie.

69
00:03:03,190 --> 00:03:06,290
Ja jūsu foo funkcija vai jūsu mijmaiņas
funkcija ir vietējo mainīgie,

70
00:03:06,290 --> 00:03:08,602
tāpat temp, tie divi
galu galā uz skursteņa.

71
00:03:08,602 --> 00:03:11,560
Tagad, mēs nevarēsim runāt pārāk daudz par
viņiem, bet šie vides mainīgajiem

72
00:03:11,560 --> 00:03:15,690
apakšā mēs redzējām pirms, bet, kad
Man bija futzing pie klaviatūras kādu dienu

73
00:03:15,690 --> 00:03:20,050
un es sāku piekļūt lietas
piemēram ARGV 100 vai ARGV 1000,

74
00:03:20,050 --> 00:03:22,320
vienkārši elements-- es aizmirstu
numbers-- bet

75
00:03:22,320 --> 00:03:24,330
nebija paredzēts piekļūt ar mani.

76
00:03:24,330 --> 00:03:26,581
Mēs sākām redzēt dažus
bailīgs simboli ekrānā.

77
00:03:26,581 --> 00:03:28,330
Tie bija tā saucamie
vides mainīgos

78
00:03:28,330 --> 00:03:32,390
tāpat globālo uzstādījumus my
programma vai par manu datoru, nevis

79
00:03:32,390 --> 00:03:37,090
nesaistīti ar neseno
bug, ka mēs apspriedām,

80
00:03:37,090 --> 00:03:39,670
Shellshock, ka ir bijis
plaguing diezgan dažus datorus.

81
00:03:39,670 --> 00:03:42,960
>> Tagad visbeidzot, mūsdienu fokusā
mēs galu galā uz kaudzes.

82
00:03:42,960 --> 00:03:44,864
Tas ir vēl viens rieciens atmiņas.

83
00:03:44,864 --> 00:03:47,030
Un būtībā tas viss
atmiņa ir tās pašas lietas.

84
00:03:47,030 --> 00:03:48,040
Tas pats aparatūru.

85
00:03:48,040 --> 00:03:49,956
Esam tikai veida
apstrādājot dažādus kopu

86
00:03:49,956 --> 00:03:51,460
baitu dažādiem mērķiem.

87
00:03:51,460 --> 00:03:56,540
Kaudze arī būs kur
mainīgie un atmiņas, kas jums pieprasītu

88
00:03:56,540 --> 00:03:58,810
no operētājsistēmas
tiek īslaicīgi uzglabāti.

89
00:03:58,810 --> 00:04:01,890
>> Bet tur ir sava veida problēma
šeit, jo aina nozīmē.

90
00:04:01,890 --> 00:04:05,261
Mums veida ir divi
kuģiem aptuveni saduras.

91
00:04:05,261 --> 00:04:08,010
Jo, kā jūs izmantot vairāk un vairāk
skursteņa, un, kā mēs redzam šodien

92
00:04:08,010 --> 00:04:11,800
tālāk, kā jūs izmantot vairāk un vairāk
kaudze, protams sliktas lietas var notikt.

93
00:04:11,800 --> 00:04:15,054
Un tiešām, mēs varam izraisīt, ka
tīši vai netīši.

94
00:04:15,054 --> 00:04:16,970
Tātad uz cliffhanger pēdējā
laiks bija šo programmu,

95
00:04:16,970 --> 00:04:20,570
kurā nebija kalpot jebkurš funkcionāla
mērķim, kas nav, lai pierādītu

96
00:04:20,570 --> 00:04:24,750
kā jūs kā slikts puisis faktiski var veikt
priekšrocība bugs kāda programmā

97
00:04:24,750 --> 00:04:28,460
un pārņemt programmu vai pat
Visa datorsistēma vai serveri.

98
00:04:28,460 --> 00:04:31,660
Tik vienkārši skatienu īsi, jums
pamanīt, ka main apakšā

99
00:04:31,660 --> 00:04:34,510
uzņem komandrindas
argumenti, kā vienu ARGV.

100
00:04:34,510 --> 00:04:38,480
Un tā ir zvanu uz funkciju f,
būtībā nezināms funkciju sauc

101
00:04:38,480 --> 00:04:40,250
f, un tas ir kas iet ARGV [1].

102
00:04:40,250 --> 00:04:43,960
>> Tātad neatkarīgi vārds lietotājs veidi at
ātri pēc šīs programmas nosaukumu,

103
00:04:43,960 --> 00:04:49,310
un tad tas patvaļīgi funkcija augšu
top, f, notiek virknē, AKA char *,

104
00:04:49,310 --> 00:04:51,720
kā mēs esam sākuši apspriest,
un tas tikai sauc to par "bar".

105
00:04:51,720 --> 00:04:53,310
Bet mēs varētu saukt to neko.

106
00:04:53,310 --> 00:04:57,470
Un tad paziņo, iekšpusē
F, masīva rakstzīmes

107
00:04:57,470 --> 00:04:59,930
sauc C- 12 šādiem simboliem.

108
00:04:59,930 --> 00:05:03,580
>> Tagad, ar stāstu man bija spēcīgi
Pirms brīža, kad atmiņā

109
00:05:03,580 --> 00:05:06,720
ir c, vai arī tiem 12
simboli gatavojas galu galā?

110
00:05:06,720 --> 00:05:07,570
Tikai, lai būtu skaidrs.

111
00:05:07,570 --> 00:05:08,070
Yeah?

112
00:05:08,070 --> 00:05:08,590
>> AUDITORIJA: Par kaudze.

113
00:05:08,590 --> 00:05:09,420
>> DAVID J. Malan: Par kaudze.

114
00:05:09,420 --> 00:05:10,720
Tātad c ir vietējais mainīgs.

115
00:05:10,720 --> 00:05:14,079
Mēs prasām 12 rakstzīmēm vai 12 baiti.

116
00:05:14,079 --> 00:05:16,120
Tiem, kas gatavojas, lai galu galā
uz tā saukto krautnē.

117
00:05:16,120 --> 00:05:18,530
Tagad beidzot tas ir citas funkcijas
ka patiesībā diezgan noderīgs,

118
00:05:18,530 --> 00:05:20,571
bet mēs esam īsti izmantots
tā sevi, strncopy.

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

120
00:05:21,550 --> 00:05:25,200
Tas nozīmē virkni kopiju, bet
tikai n burtus, n rakstzīmes.

121
00:05:25,200 --> 00:05:31,990
Tātad n simboli būs
kopēts no bāra uz c.

122
00:05:31,990 --> 00:05:32,980
Un cik daudz?

123
00:05:32,980 --> 00:05:34,110
Sliedes garumu.

124
00:05:34,110 --> 00:05:36,330
Tātad, citiem vārdiem sakot, ka
vienā rindā, strncopy,

125
00:05:36,330 --> 00:05:39,500
gatavojas kopēt
efektīvi bārs, lai c.

126
00:05:39,500 --> 00:05:42,340
>> Tagad, tikai, lai veida prognozēt
morālo šo stāstu,

127
00:05:42,340 --> 00:05:44,750
to, kas ir potenciāli problemātiska šeit?

128
00:05:44,750 --> 00:05:49,710
Pat ja mēs pārbaudīt garumu
sliedes un iet to strncopy,

129
00:05:49,710 --> 00:05:53,145
kāda ir jūsu zarnu stāsta jums ir
joprojām ir sadalīti par šo programmu?

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

131
00:05:54,410 --> 00:05:55,220
Yeah?

132
00:05:55,220 --> 00:05:57,491
>> AUDITORIJA: Neietver
telpai null raksturs.

133
00:05:57,491 --> 00:05:59,990
DAVID J. Malan: Neietver
telpai null raksturs.

134
00:05:59,990 --> 00:06:02,073
Potenciāli, atšķirībā
iepriekšējā prakse mums nav pat

135
00:06:02,073 --> 00:06:04,810
ir tik daudz kā plus 1 līdz
uzņemt šo null raksturs.

136
00:06:04,810 --> 00:06:06,649
Bet tas ir vēl sliktāk nekā.

137
00:06:06,649 --> 00:06:07,940
Ko vēl mēs nedarot?

138
00:06:07,940 --> 00:06:08,432
Yeah?

139
00:06:08,432 --> 00:06:09,307
>> Mērķauditorija: [dzirdams]

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
Mēs esam smagi kodēta 12 diezgan patvaļīgi.

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

144
00:06:19,497 --> 00:06:21,330
Tas nav tik daudz
problēma, bet fakts

145
00:06:21,330 --> 00:06:25,630
ka mēs neesam pat pārbaudīt, ja
garums bar ir mazāks par 12,

146
00:06:25,630 --> 00:06:28,530
tādā gadījumā tas būs
droši nodot to atmiņā

147
00:06:28,530 --> 00:06:30,260
sauc c, ka mēs esam piešķirti.

148
00:06:30,260 --> 00:06:32,960
Patiešām, ja bārs ir līdzīgi
20 rakstzīmes garš,

149
00:06:32,960 --> 00:06:39,010
šī funkcija, šķiet, ir kopēšanas
20 rakstzīmes no bāra uz C, līdz ar to

150
00:06:39,010 --> 00:06:41,310
ņemot vismaz 8 baiti
, ka tā nedrīkst būt.

151
00:06:41,310 --> 00:06:42,690
Tas ir saistība šeit.

152
00:06:42,690 --> 00:06:44,347
>> Tik īsā, bojāta programmas.

153
00:06:44,347 --> 00:06:45,180
Nav tik liels darījumu.

154
00:06:45,180 --> 00:06:46,360
Varbūt jums segmentāciju vaina.

155
00:06:46,360 --> 00:06:47,651
Mēs visi esam bija bugs programmās.

156
00:06:47,651 --> 00:06:50,196
Mēs visi varētu būt bugs
programmās jau tagad.

157
00:06:50,196 --> 00:06:51,320
Bet kāda ir saistība?

158
00:06:51,320 --> 00:06:54,390
Nu, šeit ir pietuvināto-in versija
ka bilde mana datora atmiņā.

159
00:06:54,390 --> 00:06:56,230
Tas ir apakšā mana kaudze.

160
00:06:56,230 --> 00:06:59,644
Un tiešām, pašā apakšā ir tas, kas ir
sauc mātes rutīnas kaudze, iedomātā veids

161
00:06:59,644 --> 00:07:00,560
, sakot, ka ir galvenais.

162
00:07:00,560 --> 00:07:03,772
Tā, ka tas, kurš sauc funkciju
f, ka mēs runājam par.

163
00:07:03,772 --> 00:07:05,230
Tātad šis ir apakšā kaudze.

164
00:07:05,230 --> 00:07:06,640
Atgriešanās adrese ir kaut kas jauns.

165
00:07:06,640 --> 00:07:08,810
Tas vienmēr ir bijis tur,
vienmēr ir bijis šajā attēlā.

166
00:07:08,810 --> 00:07:10,440
Mēs vienkārši nekad sauc uzmanību uz to.

167
00:07:10,440 --> 00:07:15,290
Jo izrādās ceļš c darbojas, ir
ka, ja viena funkcija izsauc otru,

168
00:07:15,290 --> 00:07:18,780
ne tikai to argumentus, lai kas
funkcija iegūt uzstājām uz steku,

169
00:07:18,780 --> 00:07:22,470
ne tikai to funkcija ir vietējā
mainīgie iegūt uzstājām uz steku,

170
00:07:22,470 --> 00:07:26,820
kaut ko sauc atgriešanās adrese
arī izpaužas likts uz skursteņa.

171
00:07:26,820 --> 00:07:33,330
Konkrēti, ja galvenās zvani Foo, galvenie s
pašu adresi atmiņā, vērsis kaut,

172
00:07:33,330 --> 00:07:38,240
efektīvi izpaužas likts uz skursteņa
tā, ka tad, kad f tiek darīts izpildes to

173
00:07:38,240 --> 00:07:43,630
zina, kur lēkt atpakaļ tekstā
segments lai turpinātu izpildes.

174
00:07:43,630 --> 00:07:47,760
>> Tātad, ja mēs esam šeit konceptuāli,
pamatdarbā, tad f izpaužas sauc.

175
00:07:47,760 --> 00:07:50,200
Kā f zināt, kas
uz rokas kontroli atpakaļ?

176
00:07:50,200 --> 00:07:52,020
Nu, tas maz
atpakaļceļa sarkanā šeit

177
00:07:52,020 --> 00:07:54,978
sauc atgriešanās adrese, tā vienkārši
pārbaudes, kas ir, ka atgriešanās adrese?

178
00:07:54,978 --> 00:07:57,039
Ak, ļaujiet man lēkt atpakaļ uz galveno šeit.

179
00:07:57,039 --> 00:07:59,080
Un tas ir mazliet
no realitātei,

180
00:07:59,080 --> 00:08:00,750
jo nullēm un tiem
Maģistrālo ir tehniski

181
00:08:00,750 --> 00:08:01,967
up šeit tehnoloģiju segmentā.

182
00:08:01,967 --> 00:08:03,800
Bet tas ir ideja. f
vienkārši ir jāzina, ko

183
00:08:03,800 --> 00:08:06,680
kur kontrole galu galā iet atpakaļ.

184
00:08:06,680 --> 00:08:09,790
>> Bet veids datori
jau sen ir izklāstīts lietas

185
00:08:09,790 --> 00:08:12,320
piemēram, vietējās mainīgie un
argumenti ir līdzīgs šim.

186
00:08:12,320 --> 00:08:17,180
Tātad augšpusē bildi
zilā ir kaudze rāmis f, lai visi

187
00:08:17,180 --> 00:08:19,630
no atmiņas, ka f
konkrēti ir izmanto.

188
00:08:19,630 --> 00:08:22,990
Tātad attiecīgi, ievērosiet, ka
bārs ir šajā attēlā.

189
00:08:22,990 --> 00:08:23,980
Bārs bija tā arguments.

190
00:08:23,980 --> 00:08:27,240
Un mēs apgalvoja, ka argumenti, lai
funkcijas iegūt uzstājām uz skursteņa.

191
00:08:27,240 --> 00:08:29,910
C, protams, ir
arī šajā attēlā.

192
00:08:29,910 --> 00:08:33,520
>> Un tikai Apzīmējumi mērķiem,
paziņojums augšējā kreisajā stūrī

193
00:08:33,520 --> 00:08:37,020
ir tas, ko varētu būt c kronšteinu 0 un
tad nedaudz uz leju pa labi

194
00:08:37,020 --> 00:08:38,220
ir c kronšteins 11.

195
00:08:38,220 --> 00:08:41,240
Tātad citiem vārdiem sakot, jūs varat iedomāties
ka tur ir režģis baitu

196
00:08:41,240 --> 00:08:44,380
tur, no kuriem pirmais ir
Augšējā kreisajā, apakšējā no kuriem

197
00:08:44,380 --> 00:08:48,360
ir pēdējā no šīm 12 baitu.

198
00:08:48,360 --> 00:08:49,930
>> Bet tagad mēģināt ātri uz priekšu.

199
00:08:49,930 --> 00:08:55,580
Kas ir par to, lai notiktu, ja mēs caurlaide
tādā stīgu bārā, kas ir ilgāks par c?

200
00:08:55,580 --> 00:08:59,130
Un mēs esam ne pārbaudīt, ja
tas ir tiešām ilgāk nekā 12.

201
00:08:59,130 --> 00:09:03,146
Kura daļa no šī attēla gatavojas
get pārrakstīts baitu 0, 1, 2, 3,

202
00:09:03,146 --> 00:09:07,890
dot dot dot, 11, un pēc tam
slikti, 12, 13, izmantojot 19?

203
00:09:07,890 --> 00:09:11,820
Kas notiks šeit,
ja jūs secināt no pasūtīšanas

204
00:09:11,820 --> 00:09:14,790
ka c bracket 0 ir uz augšu
un c kronšteins 11 ir sava veida leju

205
00:09:14,790 --> 00:09:15,812
lai labi?

206
00:09:15,812 --> 00:09:16,796
Yeah?

207
00:09:16,796 --> 00:09:19,260
>> AUDITORIJA: Nu, tas notiek
pārrakstīt char * bar.

208
00:09:19,260 --> 00:09:22,260
>> DAVID J. Malan: Jā, izskatās, ka
jūs gatavojas pārrakstīt char * bar.

209
00:09:22,260 --> 00:09:26,245
Un sliktāk, ja jūs sūtīt patiešām ilgi
string, jūs pat varētu pārrakstīt, ko?

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

211
00:09:27,460 --> 00:09:28,570
Atgriešanās adrese.

212
00:09:28,570 --> 00:09:31,380
Kas atkal, ir tāpat kā
atpakaļceļa pateikt programmu kur

213
00:09:31,380 --> 00:09:34,060
, lai dotos atpakaļ, kad f
tiek darīts tiek saukta.

214
00:09:34,060 --> 00:09:37,140
>> Tātad, kādi sliktie puiši parasti darīt
ir, ja viņi saskaras ar programmu

215
00:09:37,140 --> 00:09:41,290
ka viņi ir ziņkārīgs, vai ir
izmantošanu, buggy tādā veidā

216
00:09:41,290 --> 00:09:43,550
, ka viņš vai viņa var veikt
priekšrocība šī bug,

217
00:09:43,550 --> 00:09:45,720
parasti viņi nesaņem
šīs tiesības pirmo reizi.

218
00:09:45,720 --> 00:09:48,590
Tie sāc nosūtot, piemēram,
izlases stīgas uz savu programmu,

219
00:09:48,590 --> 00:09:50,260
vai pie klaviatūras,
vai atklāti tie, iespējams,

220
00:09:50,260 --> 00:09:52,740
uzrakstīt nelielu programmu, lai tikai
automātiski ģenerēt stīgas,

221
00:09:52,740 --> 00:09:55,430
un sākt banging par savu programmu,
nosūtot daudz dažādām ieejām

222
00:09:55,430 --> 00:09:56,340
ir dažāda garuma.

223
00:09:56,340 --> 00:09:58,990
>> Tiklīdz jūsu programma avarē,
tas ir pārsteidzošs lieta.

224
00:09:58,990 --> 00:10:01,020
Jo tas nozīmē, ka viņš
vai viņa ir atklājis

225
00:10:01,020 --> 00:10:02,660
to, kas ir iespējams, patiešām bug.

226
00:10:02,660 --> 00:10:05,830
Un tad viņi var iegūt vairāk gudrs
un sākt koncentrēties šaurāka

227
00:10:05,830 --> 00:10:07,420
par to, kā izmantot šo bug.

228
00:10:07,420 --> 00:10:11,480
Jo īpaši, ko viņš vai viņa varētu
darīt, ir sūtīt, labākajā gadījumā, sveiki.

229
00:10:11,480 --> 00:10:12,210
Nav liels darījumu.

230
00:10:12,210 --> 00:10:14,750
Tas ir virkne, kas ir pietiekami īss.

231
00:10:14,750 --> 00:10:18,100
Bet ko tad, ja viņš vai viņa sūta,
un mēs vispārināt kā,

232
00:10:18,100 --> 00:10:20,890
uzbrukums code-- tik nullēm
un tie, kas darīt lietas

233
00:10:20,890 --> 00:10:25,150
tāpat kā RM-RF, ka noņemt visu
no cietā diska, vai sūtīt surogātpastu

234
00:10:25,150 --> 00:10:27,000
vai kaut uzbruktu mašīna?

235
00:10:27,000 --> 00:10:29,570
>> Tātad, ja katrs no šiem
burti tikko pārstāv,

236
00:10:29,570 --> 00:10:32,380
konceptuāli, uzbrukums, uzbrukums,
uzbrukums, uzbrukums, daži slikti kods

237
00:10:32,380 --> 00:10:36,410
ka kāds cits rakstīja, bet
ja šī persona ir pietiekami gudrs

238
00:10:36,410 --> 00:10:40,790
ne tikai ietver visas
Šo RM-RFS, bet arī

239
00:10:40,790 --> 00:10:46,100
ir viņa pēdējās pāris baiti
būt numuru, kas atbilst

240
00:10:46,100 --> 00:10:50,540
uz adresi viņa
vai viņas pašas uzbrukuma kods

241
00:10:50,540 --> 00:10:53,820
, ka viņš vai viņa pagājis tikai
nodrošinot to ātru,

242
00:10:53,820 --> 00:10:58,760
Jūs varat efektīvi triks datoru
vērā pamanījis kad f tiek darīts izpildes,

243
00:10:58,760 --> 00:11:02,400
Ak, tas ir laiks man lēkt
atpakaļ uz sarkano atgriešanās adresi.

244
00:11:02,400 --> 00:11:06,070
Bet tāpēc, ka viņš vai viņa ir kaut
pārklājās ka atpakaļadresi

245
00:11:06,070 --> 00:11:09,602
ar savu numuru,
un viņi pietiekami gudrs

246
00:11:09,602 --> 00:11:11,560
, ir konfigurēts, ka
numurs atsaukties, kā jūs

247
00:11:11,560 --> 00:11:13,740
redzēt super top
kreisajā stūrī tur,

248
00:11:13,740 --> 00:11:18,020
faktiskā adrese datora
atmiņa daži no viņu uzbrukuma kods,

249
00:11:18,020 --> 00:11:21,740
slikts puisis var triks datoru
uz izpildes savs kods.

250
00:11:21,740 --> 00:11:23,700
>> Un tas kods, atkal, var būt jebkas.

251
00:11:23,700 --> 00:11:26,120
Tas ir parasti sauc par
apvalks kods, kas ir tikai

252
00:11:26,120 --> 00:11:29,030
veids, kā pateikt, ka tas nav
vispār kaut kas tik vienkāršs kā RM-RF.

253
00:11:29,030 --> 00:11:32,340
Tas ir tiešām kaut kas līdzīgs Bash,
vai faktisko programma, kas dod viņam

254
00:11:32,340 --> 00:11:37,230
vai viņas programmatiskā kontrole izpildīt
kaut kas cits, ka viņi vēlas.

255
00:11:37,230 --> 00:11:40,210
Tātad īsumā, tas viss
cēlies no vienkāršu faktu

256
00:11:40,210 --> 00:11:44,490
ka šī kļūda iesaistīti ne pārbaude
robežas jūsu masīvs.

257
00:11:44,490 --> 00:11:47,250
Un tāpēc, ka ceļu
datoriem darbs, ir tas, ka viņi

258
00:11:47,250 --> 00:11:49,430
izmantot kaudzīti no
efektīvi, konceptuāli,

259
00:11:49,430 --> 00:11:54,830
apakšas uz augšu, bet tad elementi
jūs push uz kaudze aug no augšas uz leju,

260
00:11:54,830 --> 00:11:56,624
tas ir neticami problemātiska.

261
00:11:56,624 --> 00:11:58,290
Tagad tur ir veidi, kā strādāt ap šo.

262
00:11:58,290 --> 00:12:00,800
Un godīgi sakot, tur ir valodas
ar kuru strādāt ap šo.

263
00:12:00,800 --> 00:12:03,100
Java ir imūna, piemēram,
uz šo konkrēto jautājumu.

264
00:12:03,100 --> 00:12:04,110
Tāpēc, ka viņi nedod jums norādes.

265
00:12:04,110 --> 00:12:05,943
Viņi nedod jums
tiešie atmiņas adreses.

266
00:12:05,943 --> 00:12:08,560
Tātad ar šo spēku, kas mums ir
pieskarties kaut atmiņā

267
00:12:08,560 --> 00:12:11,580
mēs vēlamies nāk, protams, liels risks.

268
00:12:11,580 --> 00:12:12,430
>> Lai saglabātu acu out.

269
00:12:12,430 --> 00:12:14,596
Ja, atklāti sakot, turpmāko mēnešu
vai lai gados, jebkurā laikā

270
00:12:14,596 --> 00:12:17,740
Jūs lasīt par kādu izmantošanu
programmas vai servera,

271
00:12:17,740 --> 00:12:22,370
Ja jūs kādreiz redzēt mājienu par kaut ko
kā bufera pārpildes uzbrukumu,

272
00:12:22,370 --> 00:12:25,390
vai kaudze pārplūdes ir cita veida
uzbrukuma, līdzīga garā,

273
00:12:25,390 --> 00:12:28,770
cik iedvesmo portāla
nosaukums, ja jūs zināt to,

274
00:12:28,770 --> 00:12:33,170
tas viss runā par tikko
pārpildīta izmēru kādu rakstura

275
00:12:33,170 --> 00:12:36,200
masīvs vai kādu masīvs kopumā.

276
00:12:36,200 --> 00:12:38,822
Kādi jautājumi, tad, par šo?

277
00:12:38,822 --> 00:12:39,780
Nemēģiniet šo mājās.

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

279
00:12:41,620 --> 00:12:42,300
>> Viss labi.

280
00:12:42,300 --> 00:12:47,270
Tātad malloc līdz šim ir bijusi mūsu jaunais
draugs, ka mēs varam piešķirt atmiņu

281
00:12:47,270 --> 00:12:50,540
, ka mēs ne vienmēr zināt
iepriekš, ka mēs gribam, lai mums nav

282
00:12:50,540 --> 00:12:52,920
cietā kodu mūsu
programmu numuri, piemēram, 12.

283
00:12:52,920 --> 00:12:55,550
Tiklīdz lietotājs stāsta mums, cik daudz
datus, kurus viņš vai viņa vēlas, lai ievadītu,

284
00:12:55,550 --> 00:12:58,000
mēs varam malloc ka daudz atmiņu.

285
00:12:58,000 --> 00:13:01,484
>> Tātad malloc izrādās, lai
lielā mērā mēs esam bijis, izmantojot to,

286
00:13:01,484 --> 00:13:03,900
tieši pēdējā laikā, un pēc tam
jums puiši ir bijis, izmantojot to

287
00:13:03,900 --> 00:13:08,160
par getstring neapzināti par
vairākas nedēļas, visi malloc atmiņu

288
00:13:08,160 --> 00:13:09,820
nāk no tā sauktās kaudzē.

289
00:13:09,820 --> 00:13:13,852
Un tas ir iemesls, kāpēc getstring, piemēram,
var piešķirt atmiņu dinamiski

290
00:13:13,852 --> 00:13:16,060
nezinot, kas tu esi
gatavojas rakstīt iepriekš,

291
00:13:16,060 --> 00:13:21,520
roku jūs atpakaļ rādītāju uz šo atmiņu,
un ka atmiņa ir vēl jūsu, lai saglabātu,

292
00:13:21,520 --> 00:13:24,080
pat pēc getstring atdevi.

293
00:13:24,080 --> 00:13:27,450
Jo atgādināt galu galā, ka
kaudze ir pastāvīgi iet uz augšu un uz leju,

294
00:13:27,450 --> 00:13:27,950
uz augšu un uz leju.

295
00:13:27,950 --> 00:13:30,230
Un, tiklīdz tas notiek
uz leju, tas nozīmē, ka jebkurš atmiņu

296
00:13:30,230 --> 00:13:33,030
šī funkcija izmanto vajadzētu
nedrīkst izmantot kāds cits.

297
00:13:33,030 --> 00:13:34,570
Tas ir atkritumu vērtības tagad.

298
00:13:34,570 --> 00:13:36,120
>> Bet kaudze ir šeit.

299
00:13:36,120 --> 00:13:39,360
Un, kas ir jauka par malloc ir tas, ka
kad malloc piešķir atmiņu šeit,

300
00:13:39,360 --> 00:13:42,070
tas nav ietekmējis, jo
lielākā daļa, ko kaudze.

301
00:13:42,070 --> 00:13:46,000
Un tāpēc jebkurš funkciju var piekļūt
atmiņu, kas ir malloc'd,

302
00:13:46,000 --> 00:13:49,120
pat funkciju kā getstring,
pat pēc tam tiek atgriezta.

303
00:13:49,120 --> 00:13:51,700
>> Tagad, sarunāties ar malloc ir bez maksas.

304
00:13:51,700 --> 00:13:53,900
Un tiešām, jūs noteikums
nepieciešams, lai sāktu pieņemot

305
00:13:53,900 --> 00:13:58,950
ir jebkurš, jebkurš, jebkurā laikā jūs izmantojat malloc
jums ir sevi izmantot bez, galu galā,

306
00:13:58,950 --> 00:14:00,280
tajā pašā rādītājs.

307
00:14:00,280 --> 00:14:03,289
Visu šo laiku mēs esam rakstiski
buggy, buggy kodu, daudzu iemeslu dēļ.

308
00:14:03,289 --> 00:14:05,580
Bet viens no kuriem ir
izmantojot CS50 bibliotēku, kas

309
00:14:05,580 --> 00:14:09,010
pati par sevi ir apzināti
buggy, tas noplūdes atmiņu.

310
00:14:09,010 --> 00:14:11,410
Jebkurā laikā jūs esat sauc getstring
pēdējo nedēļu laikā

311
00:14:11,410 --> 00:14:13,870
mēs jautā darboties
sistēma, Linux, atmiņu.

312
00:14:13,870 --> 00:14:15,780
Un jūs nekad reiz dota to atpakaļ.

313
00:14:15,780 --> 00:14:17,730
Un tas nav, kas
prakse, ir laba lieta.

314
00:14:17,730 --> 00:14:20,330
>> Un Valgrind, viens no
ieviestie PSET 4 instrumenti,

315
00:14:20,330 --> 00:14:22,900
ir viss, lai palīdzētu jums
Tagad atrast kļūdas, piemēram, ka.

316
00:14:22,900 --> 00:14:27,060
Bet par laimi, lai PSET 4 jums nav nepieciešams
izmantot CS50 bibliotēku vai getstring.

317
00:14:27,060 --> 00:14:31,220
Tātad kādi bugs, kas saistīti ar atmiņu, ir
galu galā būs savu.

318
00:14:31,220 --> 00:14:34,060
>> Tātad malloc ir vairāk nekā tikai
ērta šim nolūkam.

319
00:14:34,060 --> 00:14:37,420
Mēs faktiski tagad var atrisināt
fundamentāli atšķirīgas problēmas,

320
00:14:37,420 --> 00:14:41,640
un fundamentāli atrisināt problēmas vairāk
efektīvi nedēļā nullei solījums.

321
00:14:41,640 --> 00:14:44,720
Līdz šim tas ir sexiest
datu struktūra mēs esam bija.

322
00:14:44,720 --> 00:14:47,804
Un datu struktūra es tikai domāju
veids conceptualizing atmiņas

323
00:14:47,804 --> 00:14:50,720
tādā veidā, kas pārsniedz vienkārši sakot,
Tas ir int, tas ir char.

324
00:14:50,720 --> 00:14:52,930
Mēs varam sākt klastera lietas kopā.

325
00:14:52,930 --> 00:14:54,460
>> Tik masīvs izskatījās.

326
00:14:54,460 --> 00:14:57,270
Un kāda bija galvenais apmēram
masīvs ir, ka tas dod jums

327
00:14:57,270 --> 00:14:59,724
back-to-back gabalos
atmiņa, no kuriem katrs

328
00:14:59,724 --> 00:15:02,765
būs tāda paša veida, int,
int, int, int, vai char, palija, palijas,

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

330
00:15:03,330 --> 00:15:04,496
Bet tur ir dažas ēnas.

331
00:15:04,496 --> 00:15:06,570
Tas, piemēram, ir
masīvs izmēra sešiem.

332
00:15:06,570 --> 00:15:10,650
Pieņemsim, ka jūs aizpildīt šo masīvu ar sešiem
numuri un tam, kādu iemeslu dēļ,

333
00:15:10,650 --> 00:15:13,187
jūsu lietotāja vēlas dot
Jūs septīto numuru.

334
00:15:13,187 --> 00:15:14,020
Ja jūs nodot to?

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

336
00:15:15,490 --> 00:15:18,990
>> Kāds ir risinājums, ja Jums ir
radīja masīvu uz skursteņa,

337
00:15:18,990 --> 00:15:22,030
Piemēram, tikai ar nedēļu
divi notācija ka mēs ieviesām,

338
00:15:22,030 --> 00:15:23,730
kvadrātveida iekavās ar vairākiem iekšā?

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

340
00:15:25,160 --> 00:15:27,260
Nu, jūs esat ieguvuši sešas
numuri šajos lodziņos.

341
00:15:27,260 --> 00:15:28,530
Kādi būtu jūsu instinkti būt?

342
00:15:28,530 --> 00:15:29,973
Kur jūs vēlaties, lai to?

343
00:15:29,973 --> 00:15:30,860
>> Mērķauditorija: [dzirdams]

344
00:15:30,860 --> 00:15:31,315
>> DAVID J. Malan: Sorry?

345
00:15:31,315 --> 00:15:32,380
>> AUDITORIJA: Put to uz beigām.

346
00:15:32,380 --> 00:15:33,796
>> DAVID J. Malan: Put to uz beigām.

347
00:15:33,796 --> 00:15:35,880
Tātad tikai nedaudz vairāk pa labi,
ārpus šīs kastes.

348
00:15:35,880 --> 00:15:38,710
Kas būtu jauki, bet tas
Izrādās, jūs nevarat darīt.

349
00:15:38,710 --> 00:15:41,350
Jo, ja jūs esat nav jautāts
Šim rieciens atmiņas,

350
00:15:41,350 --> 00:15:44,490
tas varētu būt sagadīšanās, ka šis
tiek izmantota kāda cita mainīgā

351
00:15:44,490 --> 00:15:45,030
vispār.

352
00:15:45,030 --> 00:15:49,210
Domāju, ka atpakaļ nedēļā, vai arī tad, kad mēs noteikti
out Zamyla un Davin un Gabe ir nosaukumi

353
00:15:49,210 --> 00:15:49,930
atmiņā.

354
00:15:49,930 --> 00:15:51,638
Viņi bija burtiski
atpakaļ atpakaļ uz muguras.

355
00:15:51,638 --> 00:15:53,550
Tātad, mēs varam ne vienmēr
ticu, ka kāda ir

356
00:15:53,550 --> 00:15:55,800
nekā šeit ir pieejama man izmantot.

357
00:15:55,800 --> 00:15:56,990
>> Tātad, ko vēl jūs varētu darīt?

358
00:15:56,990 --> 00:16:00,282
Nu, vienreiz realizējot jums
vajag masīvu izmēra septiņu,

359
00:16:00,282 --> 00:16:02,490
jūs varētu tikai radīt
masīvs izmēra septiņu tad izmantojiet

360
00:16:02,490 --> 00:16:05,950
cilpa vai kamēr cilpa,
kopēt to jaunajā masīvs,

361
00:16:05,950 --> 00:16:09,680
un tad kaut kā vienkārši atbrīvoties no
šis masīvs vai vienkārši pārtraukt to lietot.

362
00:16:09,680 --> 00:16:12,130
Bet tas nav īpaši efektīva.

363
00:16:12,130 --> 00:16:15,340
Īsāk sakot, masīvi neļaujiet
Jūs dinamiski mainīt.

364
00:16:15,340 --> 00:16:17,900
>> Tātad, no vienas puses, jums
brīvpiekļuves, kas ir pārsteidzošs.

365
00:16:17,900 --> 00:16:20,108
, Jo tas ļauj mums darīt lietas
piemēram, skaldi un valdi,

366
00:16:20,108 --> 00:16:23,100
bināro meklēšanu, viss, ko mēs esam
runāja par uz ekrāna šeit.

367
00:16:23,100 --> 00:16:24,950
Bet jūs krāsas sevi stūrī.

368
00:16:24,950 --> 00:16:27,810
Tiklīdz jūs hit
beigās jūsu masīvs,

369
00:16:27,810 --> 00:16:29,980
Jums ir jādara ļoti
dārga operācija

370
00:16:29,980 --> 00:16:33,910
vai uzrakstīt veselu ķekars kodu
tagad galā ar šo problēmu.

371
00:16:33,910 --> 00:16:36,680
>> Tātad, ko tad, ja tā vietā mums bija
kaut ko sauc par sarakstu,

372
00:16:36,680 --> 00:16:38,820
vai saistīta sarakstu, jo īpaši?

373
00:16:38,820 --> 00:16:41,930
Ko darīt, ja tā vietā,
taisnstūri atpakaļ atpakaļ uz muguras,

374
00:16:41,930 --> 00:16:45,730
mums ir taisnstūri, kas atstāj maz
mazliet valstīties telpā starp tām?

375
00:16:45,730 --> 00:16:49,670
Un, kaut arī es esmu sastādīts šis
attēlu vai pielāgoti šo attēlu

376
00:16:49,670 --> 00:16:54,696
no viena uz tekstu šeit, lai būtu atpakaļ
atpakaļ atpakaļ ļoti kārtīgi, patiesībā,

377
00:16:54,696 --> 00:16:56,820
viens no šiem taisnstūriem
varētu būt šeit atmiņā.

378
00:16:56,820 --> 00:16:58,028
Viens no tiem varētu būt šeit.

379
00:16:58,028 --> 00:17:00,420
Viens no tiem varētu būt šeit,
nekā šeit, un tā tālāk.

380
00:17:00,420 --> 00:17:02,910
>> Bet ko tad mēs vērsa,
šajā gadījumā, bultas

381
00:17:02,910 --> 00:17:05,650
ka kaut kā saistīt šos
taisnstūri kopā?

382
00:17:05,650 --> 00:17:08,170
Patiesi, mēs esam redzējuši tehnisks
iemiesojums bultiņu.

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

384
00:17:09,839 --> 00:17:13,710
Ko mēs esam izmantoti nesen
dienas, ka zem motora pārsega,

385
00:17:13,710 --> 00:17:15,210
tiek uzrādīts bultiņu?

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

387
00:17:16,290 --> 00:17:17,349
Rādītājs, vai ne?

388
00:17:17,349 --> 00:17:19,780
>> Tātad, ko tad, tā vietā,
vienkārši uzglabātu numurus,

389
00:17:19,780 --> 00:17:23,130
piemēram, 9, 17, 22, 26, 34,
kas notiks, ja mēs uzglabāt ne

390
00:17:23,130 --> 00:17:27,079
tikai numurs, bet rādītājs
blakus katru šādu numuru?

391
00:17:27,079 --> 00:17:30,690
Tā, ka daudz, piemēram, jūs varētu pavedienu
adatu cauri visai ķekars auduma,

392
00:17:30,690 --> 00:17:32,950
kaut kā sasaisti lietas
kopā, tāpat var

393
00:17:32,950 --> 00:17:35,550
mēs ar norādes, kā
iemiesojies ar bultiņām šeit

394
00:17:35,550 --> 00:17:38,550
veida aust kopā
individuālie taisnstūri

395
00:17:38,550 --> 00:17:41,780
efektīvi izmantojot rādītāju
blakus katram numuram

396
00:17:41,780 --> 00:17:46,065
norāda uz kādu nākamo numuru, kas
punktu, kas, savukārt, daži nākamais numurs?

397
00:17:46,065 --> 00:17:47,940
Tātad citiem vārdiem sakot,
ja mēs patiesībā gribēju

398
00:17:47,940 --> 00:17:49,820
īstenot kaut kas līdzīgs šim?

399
00:17:49,820 --> 00:17:53,610
Nu diemžēl šie taisnstūri,
Vismaz viens ar 9, 17, 22,

400
00:17:53,610 --> 00:17:57,040
un tā tālāk, tie vairs nav
jauki laukumi ar vienu numuru.

401
00:17:57,040 --> 00:17:59,960
Apakšējā, taisnstūris
līdz 9, piemēram,

402
00:17:59,960 --> 00:18:04,330
atspoguļo to, ko vajadzētu
būt rādītājs, 32 biti.

403
00:18:04,330 --> 00:18:09,460
Tagad, es neesmu vēl informēts par jebkādu datu tipa
C, kas dod jums ne tikai int

404
00:18:09,460 --> 00:18:11,630
bet rādītājs kopumā.

405
00:18:11,630 --> 00:18:15,020
>> Tātad, kas ir risinājums, ja mēs vēlamies
izgudrot savu atbildi uz šo?

406
00:18:15,020 --> 00:18:15,760
Yeah?

407
00:18:15,760 --> 00:18:16,640
>> Mērķauditorija: [dzirdams]

408
00:18:16,640 --> 00:18:17,360
>> DAVID J. Malan: Kas tas tāds?

409
00:18:17,360 --> 00:18:17,880
>> AUDITORIJA: Jauna struktūra.

410
00:18:17,880 --> 00:18:19,590
>> DAVID J. Malan: Jā, tad kāpēc
ne mēs izveidot jaunu struktūru,

411
00:18:19,590 --> 00:18:20,920
vai C, struct?

412
00:18:20,920 --> 00:18:25,990
Mēs esam redzējuši statņi iepriekš, ja īsi,
kur mēs nodarbojas ar studentu struktūru

413
00:18:25,990 --> 00:18:27,780
, piemēram, tas, kas bija vārdu un māju.

414
00:18:27,780 --> 00:18:31,980
In PSET 3 breakout tu izmanto veselu
ķekars structs-- GRect un GOvals

415
00:18:31,980 --> 00:18:34,810
ka Stanford izveidota, lai
klasteris informāciju kopā.

416
00:18:34,810 --> 00:18:38,580
Tātad, ko tad, ja mēs šo pašu domu par
atslēgvārdi "typedef" un "struct,"

417
00:18:38,580 --> 00:18:42,890
un tad dažas studentu specifiskās sīkumi,
un attīstās to vērā šādi:

418
00:18:42,890 --> 00:18:46,210
typedef struktūrai node-- un mezglu
tikai ļoti vispārīgas datorzinātņu

419
00:18:46,210 --> 00:18:49,980
termins kaut kādā datu struktūru,
konteineru datu struktūrā.

420
00:18:49,980 --> 00:18:53,900
Mezgls es varu pieprasīt nāksies
int n, pilnīgi vienkārša,

421
00:18:53,900 --> 00:18:58,810
un tad nedaudz vairāk cryptically,
šī otrā līnija, struct mezglā * nākamo.

422
00:18:58,810 --> 00:19:01,300
Bet mazāk tehniskā ziņā,
to, kas ir, ka otrā rinda

423
00:19:01,300 --> 00:19:02,980
koda iekšpusē cirtaini lencēm?

424
00:19:02,980 --> 00:19:03,737
Yeah?

425
00:19:03,737 --> 00:19:04,851
>> Mērķauditorija: [dzirdams]

426
00:19:04,851 --> 00:19:06,600
DAVID J. Malan:
rādītāju uz citu mezglu.

427
00:19:06,600 --> 00:19:09,910
Tātad, protams, sintakses mazliet noslēpumains.

428
00:19:09,910 --> 00:19:13,250
Bet, ja jūs lasīt to burtiski,
nākamais ir nosaukums mainīgo.

429
00:19:13,250 --> 00:19:14,410
Kas ir tās datu tips?

430
00:19:14,410 --> 00:19:18,206
Tas ir nedaudz runīgs šoreiz,
bet tas ir tipa struct mezglā *.

431
00:19:18,206 --> 00:19:22,960
Katru reizi, kad mēs esam redzējuši kaut zvaigzne, ka
nozīmē, ka tas ir rādītājs uz šo datu tipu.

432
00:19:22,960 --> 00:19:26,810
Tātad nākamais ir acīmredzot
rādītāju uz struct mezglā.

433
00:19:26,810 --> 00:19:28,310
>> Tagad, kas ir struct mezglā?

434
00:19:28,310 --> 00:19:31,044
Nu, ievērosiet redzat tiem
paši vārdi pie augšējā labajā stūrī.

435
00:19:31,044 --> 00:19:33,960
Un tiešām, jūs arī redzēt vārdu
"Mezgls", noteikti šeit apakšā pa kreisi.

436
00:19:33,960 --> 00:19:35,640
Un tas ir faktiski tikai ērtības.

437
00:19:35,640 --> 00:19:39,930
Ievērojiet, ka mūsu studentu definīcijā
tur ir vārds "students" tikai vienu reizi.

438
00:19:39,930 --> 00:19:42,510
Un tas ir tāpēc, ka students
objekts bija ne sevi godbijīgs.

439
00:19:42,510 --> 00:19:45,340
Tur nekas iekšpusē students
kas nepieciešams, lai norādītu uz citu students,

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

441
00:19:45,610 --> 00:19:47,630
Tas būtu sava veida
dīvaini reālajā pasaulē.

442
00:19:47,630 --> 00:19:50,880
>> Bet ar mezglu saistīta
sarakstu, mēs vēlamies mezglu

443
00:19:50,880 --> 00:19:53,970
būt par saistītu ar līdzīgu objektu.

444
00:19:53,970 --> 00:19:57,900
Un tā ievērojat izmaiņas šeit nav
tikai to, kas ir iekšpusē cirtaini lencēm.

445
00:19:57,900 --> 00:20:00,800
Bet mēs pievienojam vārdu "mezglu"
augšdaļā, kā arī

446
00:20:00,800 --> 00:20:02,930
pievienojot to apakšā
vietā "students."

447
00:20:02,930 --> 00:20:06,000
Un tas ir tikai tehniska detaļa
tā, ka, atkal, jūsu datu struktūra

448
00:20:06,000 --> 00:20:11,380
var būt self-saistītie, tā, lai
mezglu var norādīt uz citu šādu mezglu.

449
00:20:11,380 --> 00:20:13,840
>> Tātad, kas tas ir galu galā
gatavojas nozīmē mums?

450
00:20:13,840 --> 00:20:17,560
Nu, viens, šī stuff iekšā
ir saturs mūsu mezglā.

451
00:20:17,560 --> 00:20:19,360
Šī lieta šeit,
augšā pa labi, ir tikai tik

452
00:20:19,360 --> 00:20:20,860
ka, atkal, mēs varam atsaukties uz sevi.

453
00:20:20,860 --> 00:20:23,401
Un tad attālākajos sīkumi,
pat ja mezgls ir jauns termins,

454
00:20:23,401 --> 00:20:25,500
varbūt, tas joprojām
pats kā students un ko

455
00:20:25,500 --> 00:20:27,520
bija zem motora pārsega, kas SPL.

456
00:20:27,520 --> 00:20:31,095
>> Tātad, ja mēs tagad gribēju sākt
Īstenojot šo saistīts sarakstu,

457
00:20:31,095 --> 00:20:33,220
kā mēs varētu iztulkot
kaut kas līdzīgs šo kodu?

458
00:20:33,220 --> 00:20:35,350
Nu, pieņemsim tikai redzēt
piemērs programmai, kas

459
00:20:35,350 --> 00:20:36,840
faktiski izmanto saistīts sarakstu.

460
00:20:36,840 --> 00:20:40,870
Starp šodienas izplatīšanas kodu
ir programma, ko sauc saraksts Zero.

461
00:20:40,870 --> 00:20:44,980
Un, ja es palaist šo es izveidojis super
vienkāršu GUI, grafiskā lietotāja saskarne,

462
00:20:44,980 --> 00:20:46,460
bet tas tiešām tikai printf.

463
00:20:46,460 --> 00:20:50,930
Un tagad es esmu devis sev dažas izvēlni
options-- Dzēst, ievietošana, Search,

464
00:20:50,930 --> 00:20:51,750
un Traverse.

465
00:20:51,750 --> 00:20:52,630
Un Iziet.

466
00:20:52,630 --> 00:20:55,970
Šie ir tikai kopīgas operācijas
datu struktūra pazīstams kā saite sarakstā.

467
00:20:55,970 --> 00:20:58,409
>> Tagad, Dzēst gatavojas
dzēst numuru no saraksta.

468
00:20:58,409 --> 00:21:00,200
Ievietot gatavojas pievienot
numuru sarakstā.

469
00:21:00,200 --> 00:21:02,181
Meklēšana ir gatavojas meklēt
par numuru sarakstā.

470
00:21:02,181 --> 00:21:04,930
Un traversa ir tikai iedomātā veids
, sakot, staigāt pa sarakstu,

471
00:21:04,930 --> 00:21:06,245
izdrukāt to ārā, bet tas arī viss.

472
00:21:06,245 --> 00:21:07,720
Nemaina to nekādā veidā.

473
00:21:07,720 --> 00:21:08,570
>> Tātad, pieņemsim mēģināt šo.

474
00:21:08,570 --> 00:21:10,160
Iesim uz priekšu un 2 tips.

475
00:21:10,160 --> 00:21:12,710
Un tad es esmu gatavojas
ievietot numuru, saka 9.

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

477
00:21:13,620 --> 00:21:17,480
Un tagad mana programma ir tikai
ieprogrammēts teikt, saraksts tagad ir 9.

478
00:21:17,480 --> 00:21:20,190
Tagad, ja man iet uz priekšu un
do Ievietojiet atkal, ļaujiet

479
00:21:20,190 --> 00:21:23,680
man iet uz priekšu un tālināt un ierakstiet 17.

480
00:21:23,680 --> 00:21:25,770
Tagad mans saraksts ir 9, tad 17.

481
00:21:25,770 --> 00:21:27,750
Ja es to ievietot atkārtoti, pieņemsim izlaist vienu.

482
00:21:27,750 --> 00:21:32,400
Nevis 22, kā vienu attēlu mēs esam
ir meklē šeit, ļaujiet man lēkt uz priekšu

483
00:21:32,400 --> 00:21:34,630
un ievietojiet 26 nākamo.

484
00:21:34,630 --> 00:21:36,230
Tāpēc es esmu gatavojas rakstīt 26.

485
00:21:36,230 --> 00:21:37,755
Saraksts ir, kā es gaidīt.

486
00:21:37,755 --> 00:21:40,630
Bet tagad, tikai, lai redzētu, vai šo kodu
būs elastīga, ļaujiet man tagad

487
00:21:40,630 --> 00:21:43,520
22 tipa, kas ir vismaz
konceptuāli, ja mēs esam

488
00:21:43,520 --> 00:21:46,520
Paturot to sakārtoti, kas patiešām
būs vēl viens mērķis tieši tagad,

489
00:21:46,520 --> 00:21:48,690
jāiet starp 17 un 26.

490
00:21:48,690 --> 00:21:50,270
Tāpēc es hit Enter.

491
00:21:50,270 --> 00:21:51,380
Patiešām, kas darbojas.

492
00:21:51,380 --> 00:21:54,950
Un tāpēc tagad ļaujiet man ievietot
pēdējais, vienu attēlu, 34.

493
00:21:54,950 --> 00:21:55,450
>> Viss labi.

494
00:21:55,450 --> 00:21:58,980
Tātad tagad ļaujiet man noteikt, ka
Dzēst un Traverse un Search darīt,

495
00:21:58,980 --> 00:21:59,760
patiesībā, strādā.

496
00:21:59,760 --> 00:22:04,180
Patiesībā, ja man palaist meklēšanu, pieņemsim
meklēt numuru 22, Enter.

497
00:22:04,180 --> 00:22:05,010
Tā konstatēja 22.

498
00:22:05,010 --> 00:22:07,580
Tātad, kas ir tas, ko šis
Programma Saraksts Zero dara.

499
00:22:07,580 --> 00:22:10,230
>> Bet kas patiesībā notiek
gada, kas īsteno šo?

500
00:22:10,230 --> 00:22:14,530
Nu, vispirms es varētu būt, un patiešām
Man ir, failu sauc list0.h.

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

502
00:22:16,540 --> 00:22:20,690
Un kaut kur ir šī
līnija, typedef, struktūrai mezglā,

503
00:22:20,690 --> 00:22:24,850
Tad man ir cirtaini bikšturi, int n, un
tad struct-- kāda bija definīcija?

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

505
00:22:26,530 --> 00:22:28,545
Struct mezglā nākamo.

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

507
00:22:29,920 --> 00:22:31,045
Tāpēc mums ir nepieciešams zvaigzni.

508
00:22:31,045 --> 00:22:33,420
Tagad tehniski mēs nokļūt
ieradums zīmēšanas to šeit.

509
00:22:33,420 --> 00:22:35,670
Jūs varētu redzēt grāmatas un
tiešsaistes atsauces darīt tur.

510
00:22:35,670 --> 00:22:36,660
Tas ir funkcionāli līdzvērtīgi.

511
00:22:36,660 --> 00:22:37,980
Faktiski, tas ir nedaudz vairāk tipisks.

512
00:22:37,980 --> 00:22:40,563
Bet es būšu saskaņā ar ko
mēs darījām pēdējo laiku un darīt to.

513
00:22:40,563 --> 00:22:42,350
Un tad visbeidzot, es esmu gatavojas darīt.

514
00:22:42,350 --> 00:22:45,550
>> Tātad galvenes failā
kaut kur, jo list0.h

515
00:22:45,550 --> 00:22:49,200
šodien tas ir struct definīcija,
un varbūt daži citi sīkumi.

516
00:22:49,200 --> 00:22:52,580
Tikmēr list0c tur
būs dažas lietas.

517
00:22:52,580 --> 00:22:54,740
Bet mēs ejam vienkārši
sākuma un nav pabeigta to.

518
00:22:54,740 --> 00:22:59,690
List0.h ir fails es gribu
iekļaut manu C failā.

519
00:22:59,690 --> 00:23:03,910
Un tad kādā brīdī es esmu
nāksies int, galvenais, par spēkā neesošu.

520
00:23:03,910 --> 00:23:06,530
Un tad es esmu gatavojas
ir dažas to-do ir šeit.

521
00:23:06,530 --> 00:23:10,620
Es esmu arī nāksies
prototips, tāpat kā spēkā neesošu, meklēt, t.sk.,

522
00:23:10,620 --> 00:23:13,610
n, kuru mērķis dzīvē ir
lai meklētu elementa.

523
00:23:13,610 --> 00:23:18,310
Un tad noteikti šeit es apgalvot,
šodienas kods, spēkā neesošu, meklēt, int, n,

524
00:23:18,310 --> 00:23:21,020
nē semikols bet atvērtas cirtaini bikšturi.

525
00:23:21,020 --> 00:23:25,049
Un tagad es gribu, lai kaut kā meklēt
par elementu šajā sarakstā.

526
00:23:25,049 --> 00:23:27,340
Bet mums nav pietiekami daudz
informāciju uz ekrāna vēl.

527
00:23:27,340 --> 00:23:29,800
Man nav reāli
pārstāvēja pašu sarakstu.

528
00:23:29,800 --> 00:23:33,070
Tātad viens veids, kā mēs varētu īstenot
saistīts saraksts programmā

529
00:23:33,070 --> 00:23:37,520
ir es veida gribu darīt kaut ko
tāpat deklarēt saistīts saraksts šeit.

530
00:23:37,520 --> 00:23:40,520
Vienkāršības labad, es esmu gatavojas darīt
šis pasaules, kaut arī kopumā mēs

531
00:23:40,520 --> 00:23:41,645
nedrīkst darīt pārāk daudz.

532
00:23:41,645 --> 00:23:43,260
Bet tas būs vienkāršot šo piemēru.

533
00:23:43,260 --> 00:23:45,890
Tāpēc es gribu paziņot
saistīts saraksts šeit.

534
00:23:45,890 --> 00:23:47,010
Tagad, kā varētu man darīt?

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

536
00:23:48,810 --> 00:23:50,750
>> Lūk attēls saistītajā sarakstā.

537
00:23:50,750 --> 00:23:53,030
Un man nav īsti
zināt brīdī how

538
00:23:53,030 --> 00:23:56,710
Es iešu par pārstāvot
tik daudz lietas ar tikai vienu

539
00:23:56,710 --> 00:23:58,040
mainīgais atmiņā.

540
00:23:58,040 --> 00:23:59,160
Bet domāju, ka atpakaļ brīdi.

541
00:23:59,160 --> 00:24:00,830
Visu šo laiku mēs esam bija
virknes, kas mēs pēc tam

542
00:24:00,830 --> 00:24:02,913
atklāja, ka bloki
zīmes, kuras mēs pēc tam

543
00:24:02,913 --> 00:24:05,740
atklāja vienkārši rādītājs
ar pirmo raksturs

544
00:24:05,740 --> 00:24:08,890
masīva rakstzīmes
kas ir null izbeigta.

545
00:24:08,890 --> 00:24:13,530
Tātad, šī loģika, un ar to
attēlu veida sētu savas domas,

546
00:24:13,530 --> 00:24:17,964
Ko nepieciešams mēs faktiski rakstīt mūsu
kods pārstāvēt saistīts sarakstu?

547
00:24:17,964 --> 00:24:21,130
Cik daudz no šīs informācijas mēs vajag
sagūstīt C kodu, jūs teiktu?

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

549
00:24:22,654 --> 00:24:23,154
Yeah?

550
00:24:23,154 --> 00:24:24,738
>> AUDITORIJA: Mums ir nepieciešams rādītāju uz mezglu.

551
00:24:24,738 --> 00:24:26,237
DAVID J. Malan: rādītājs uz mezglu.

552
00:24:26,237 --> 00:24:29,320
Jo īpaši, kas mezgls būtu jūsu
instinkti būt saglabātu rādītāju?

553
00:24:29,320 --> 00:24:30,026
>> AUDITORIJA: Pirmais mezglā.

554
00:24:30,026 --> 00:24:31,942
>> DAVID J. Malan: Jā,
iespējams tikai pirmais.

555
00:24:31,942 --> 00:24:34,030
Un paziņojums, pirmais
mezgls ir atšķirīgas formas.

556
00:24:34,030 --> 00:24:37,690
Tas ir tikai puse lielums struktūrai,
tāpēc, ka tas ir tiešām tikai rādītājs.

557
00:24:37,690 --> 00:24:44,650
Tātad, ko jūs tiešām varat darīt, ir pasludināt
saistīts saraksts būt tipa mezglā *.

558
00:24:44,650 --> 00:24:47,780
Un pieņemsim tikai sauc to pirmo reizi
un inicializēt to null.

559
00:24:47,780 --> 00:24:49,910
Tātad nulle, atkal, ir nāk
stājas attēlu šeit.

560
00:24:49,910 --> 00:24:53,620
Ne tikai null izmanto kā, piemēram, īpašu
atgriešanās vērtību lietām, piemēram getstring

561
00:24:53,620 --> 00:24:57,770
un malloc, null ir arī nulle
rādītājs, nav rādītājs,

562
00:24:57,770 --> 00:24:58,430
Ja jūs.

563
00:24:58,430 --> 00:25:00,309
Tas tikai nozīmē, nekas vēl šeit.

564
00:25:00,309 --> 00:25:02,100
Tagad pirmo reizi, es varētu esam
sauc to neko.

565
00:25:02,100 --> 00:25:04,200
Es varētu būt to sauca "saraksts"
vai kādu citu lietu skaits.

566
00:25:04,200 --> 00:25:06,960
Bet es esmu nosaucot to par "pirmo reizi", lai
tā līniju līdz ar šo bildi.

567
00:25:06,960 --> 00:25:10,280
Tātad tāpat kā virkne var attēlot
ar adresi savu pirmo baitu,

568
00:25:10,280 --> 00:25:11,280
tā var saistīts saraksts.

569
00:25:11,280 --> 00:25:13,480
Un mēs redzēsim citus datus
pārstāvēta struktūras

570
00:25:13,480 --> 00:25:16,700
tikai ar vienu rādītāju,
32-bit bulta, norādot

571
00:25:16,700 --> 00:25:18,740
pašā pirmajā mezglā struktūrā.

572
00:25:18,740 --> 00:25:20,340
>> Bet tagad pieņemsim paredzēt problēmu.

573
00:25:20,340 --> 00:25:23,230
Ja es esmu tikai atceroties
manā programmā adresi

574
00:25:23,230 --> 00:25:27,220
pirmā mezgla, pirmais
taisnstūris šajā datu struktūru,

575
00:25:27,220 --> 00:25:31,760
kādi bija labāk lietu par
par pārējo manu sarakstu ieviešana?

576
00:25:31,760 --> 00:25:35,820
Kas ir galvenais detaļa, kas notiek
Lai to nodrošinātu faktiski darbojas?

577
00:25:35,820 --> 00:25:39,250
Un "faktiski darbojas" I
domāju, līdzīgi virknes,

578
00:25:39,250 --> 00:25:42,180
ļauj mums iet ar pirmo rakstzīmi
in Davin vārdu uz otro,

579
00:25:42,180 --> 00:25:44,755
uz trešo, lai
ceturtkārt, uz pašām beigām,

580
00:25:44,755 --> 00:25:47,880
kā mēs zinām, kad mēs esam beigās
no saistīta sarakstu, kas izskatās šādi?

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

582
00:25:50,035 --> 00:25:50,660
Kad tas ir null.

583
00:25:50,660 --> 00:25:53,640
Un es esmu pārstāvēta šāda veida, kā
tāpat kā elektromehāniķi spēku,

584
00:25:53,640 --> 00:25:56,420
ar nelielu sēkļa
simbols, nelāgi.

585
00:25:56,420 --> 00:25:58,246
Bet tas tikai nozīmē, null šajā gadījumā.

586
00:25:58,246 --> 00:26:00,370
Jūs varat izdarīt to jebkādu skaitu
veidos, bet šis autors

587
00:26:00,370 --> 00:26:02,800
noticis izmantot šo simbolu šeit.

588
00:26:02,800 --> 00:26:06,260
>> Tik ilgi, kamēr mēs esam rindu
visas šīs mezglu kopā,

589
00:26:06,260 --> 00:26:08,600
tikai atcerēties, kur
Pirmais ir, tik ilgi, kamēr

590
00:26:08,600 --> 00:26:11,760
kā mēs pievērsām īpašu simbolu pie
Pašā pēdējā mezglu sarakstā,

591
00:26:11,760 --> 00:26:15,130
un mēs izmantosim null, jo tas ir
kas mums ir pieejami pie mums,

592
00:26:15,130 --> 00:26:16,480
šis saraksts ir pilnīgs.

593
00:26:16,480 --> 00:26:20,190
Un pat tad, ja man ir tikai jums rādītāju uz
pirmais elements, jums, programmētājs,

594
00:26:20,190 --> 00:26:22,486
noteikti var piekļūt pārējo tā.

595
00:26:22,486 --> 00:26:24,360
Bet pieņemsim ļaujiet jūsu prātus
klīst mazliet,

596
00:26:24,360 --> 00:26:26,140
ja viņi jau nav
diezgan wandered-- kas ir

597
00:26:26,140 --> 00:26:28,723
būs darbības laiks
atrast kaut ko šajā sarakstā?

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

599
00:26:30,450 --> 00:26:33,470
Damn tas, tas ir liels O n,
kas nav slikti, jo taisnīgumu.

600
00:26:33,470 --> 00:26:34,800
Bet tas ir lineārs.

601
00:26:34,800 --> 00:26:37,980
Mēs esam atteikušies no kāda iezīme
par masīvu, pārvietojot vairāk

602
00:26:37,980 --> 00:26:43,130
pret šo attēlu dinamiski
austi kopā vai saistīti mezglu?

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

604
00:26:44,970 --> 00:26:46,687
Mēs esam atteikušies brīvpieejas.

605
00:26:46,687 --> 00:26:48,770
Masīvs ir jauki, jo
matemātiski viss

606
00:26:48,770 --> 00:26:50,340
ir atpakaļ atpakaļ atpakaļ atpakaļ.

607
00:26:50,340 --> 00:26:52,370
Pat ja šo attēlu
izskatās diezgan, un pat

608
00:26:52,370 --> 00:26:55,830
lai gan tas izskatās šiem mezgliem
ir labi atstarpi, patiesībā

609
00:26:55,830 --> 00:26:56,830
tie varētu būt jebkur.

610
00:26:56,830 --> 00:27:01,590
OX1, Ox50, Ox123, Ox99, šie
mezgli varētu būt jebkur.

611
00:27:01,590 --> 00:27:05,960
Jo malloc dara piešķirt atmiņu
no kaudzes, bet jebkur kaudzē.

612
00:27:05,960 --> 00:27:09,080
Jums nav obligāti zināt, ka tas ir
būs atpakaļ atpakaļ atpakaļ.

613
00:27:09,080 --> 00:27:12,460
Un tāpēc šī aina realitāte s
nebūs gluži tas diezgan.

614
00:27:12,460 --> 00:27:16,140
>> Tātad, tas notiek, lai mazliet
strādās, lai īstenotu šo funkciju.

615
00:27:16,140 --> 00:27:17,880
Tāpēc pieņemsim īstenot meklēšanu tagad.

616
00:27:17,880 --> 00:27:20,250
Un mēs redzēsim veida
gudrs veids, kā to izdarīt.

617
00:27:20,250 --> 00:27:24,660
Tātad, ja es esmu meklēšanas funkciju un
Es esmu dota mainīgo, skaitlim n

618
00:27:24,660 --> 00:27:28,490
meklēt, man ir nepieciešams zināt
Jaunais sintakse meklē iekšā

619
00:27:28,490 --> 00:27:32,400
kādas struktūras, kas ir
norādīja uz, lai atrastu n.

620
00:27:32,400 --> 00:27:33,210
Tāpēc pieņemsim to izdarītu.

621
00:27:33,210 --> 00:27:36,030
>> Tātad vispirms es iešu
priekšu un atzīt mezglu *.

622
00:27:36,030 --> 00:27:39,400
Un es esmu gatavojas to nosaukt
rādītājs, tikai pēc vienošanās.

623
00:27:39,400 --> 00:27:41,710
Un es esmu gatavojas, lai sāktu to vispirms.

624
00:27:41,710 --> 00:27:43,770
Un tagad es varu darīt
vairākos veidos.

625
00:27:43,770 --> 00:27:45,436
Bet es esmu gatavojas pieņemt kopēju pieeju.

626
00:27:45,436 --> 00:27:50,180
Kamēr rādītājs nav vienāds ar
null, un tas ir derīgs sintakse.

627
00:27:50,180 --> 00:27:54,550
Un tas nozīmē tikai to, rīkojieties šādi, tāpēc
Kamēr jūs neesat norādot pie nekas.

628
00:27:54,550 --> 00:27:55,800
Ko es gribu darīt?

629
00:27:55,800 --> 00:28:01,939
>> Ja rādītājs dot n, ļaujiet man atgriezties
to, ka, equals-- vienāds ko?

630
00:28:01,939 --> 00:28:03,105
Kāda vērtība es meklēju?

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

632
00:28:04,920 --> 00:28:06,590
Faktiskais n, kas tika pieņemts.

633
00:28:06,590 --> 00:28:09,020
Tātad, šeit ir vēl viens elements
C un daudzās valodās.

634
00:28:09,020 --> 00:28:13,705
Pat ja struktūru sauc mezglā
ir vērtība N, pilnīgi likumīgu

635
00:28:13,705 --> 00:28:17,530
lai ir arī vietējo arguments
vai mainīgs sauc n.

636
00:28:17,530 --> 00:28:20,085
Tāpēc, ka pat mēs, ar
cilvēka acīm, var atšķirt

637
00:28:20,085 --> 00:28:22,087
ka tas n ir, iespējams
atšķiras no šī n.

638
00:28:22,087 --> 00:28:23,420
Jo sintakse ir atšķirīgs.

639
00:28:23,420 --> 00:28:26,211
Tev dot un rādītāju,
tā kā šis viens nav tādas lietas.

640
00:28:26,211 --> 00:28:27,290
Tātad tas ir OK.

641
00:28:27,290 --> 00:28:29,120
Tas ir OK, lai izsauktu tās pašas lietas.

642
00:28:29,120 --> 00:28:32,380
>> Ja es jūs atrast, es esmu
gatavojas vēlaties darīt kaut ko

643
00:28:32,380 --> 00:28:35,000
tāpat kā paziņot, ka mēs atradām n.

644
00:28:35,000 --> 00:28:37,930
Un mēs ņemšu atvaļinājumu, ka
komentēt vai pseudocode kodu.

645
00:28:37,930 --> 00:28:40,190
Cits, un šeit ir
Interesantākais, ko

646
00:28:40,190 --> 00:28:47,320
es gribu to darīt, ja pašreizējā mezglā
tiek nesatur n, ka man rūp?

647
00:28:47,320 --> 00:28:50,700
Kā es varu panākt sekojošo?

648
00:28:50,700 --> 00:28:53,710
Ja mans pirkstu
moments ir PTR, un tas ir

649
00:28:53,710 --> 00:28:55,920
norādot jebkādā
Pirmais ir norādot uz,

650
00:28:55,920 --> 00:28:59,290
kā es varu pārvietot manu pirkstu
uz nākamo mezglu kodu?

651
00:28:59,290 --> 00:29:01,915
Nu, kas ir atpakaļceļa mēs esam
gatavojas sekot šajā gadījumā?

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

653
00:29:03,464 --> 00:29:04,380
AUDITORIJA: [nedzirdama].

654
00:29:04,380 --> 00:29:05,630
DAVID J. Malan: Jā, tā nākamais.

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

656
00:29:06,640 --> 00:29:09,824
Tātad, ja es dodos atpakaļ uz manu
kods šeit, protams, es esmu

657
00:29:09,824 --> 00:29:12,990
gatavojas iet uz priekšu un saka rādītāju, kas
ir tikai pagaidu variable-- tas ir

658
00:29:12,990 --> 00:29:15,320
dīvainais nosaukums, PTR, bet
tas ir tāpat kā temp--

659
00:29:15,320 --> 00:29:19,234
Es esmu gatavojas noteikt rādītāju
vienāds ar kāda rādītāju is--

660
00:29:19,234 --> 00:29:22,150
un atkal, tas būs
nedaudz buggy par moment-- dot nākamo.

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

662
00:29:23,551 --> 00:29:26,550
Citiem vārdiem sakot, es esmu gatavojas pieņemt manu
pirkstu, kas ir vērsta šajā mezglā

663
00:29:26,550 --> 00:29:31,247
šeit, un es esmu gatavojas teikt, jūs zināt
ko, ieskatieties nākamo lauku

664
00:29:31,247 --> 00:29:33,330
un pārvietot savu pirkstu, lai
neatkarīgi no tā norādot uz.

665
00:29:33,330 --> 00:29:35,163
Un tas notiek, lai
atkārtot, atkārtot, atkārtot.

666
00:29:35,163 --> 00:29:37,630
Bet, kad tas savu pirkstu
pārtraukt darīt kaut ko vispār?

667
00:29:37,630 --> 00:29:40,095
Tiklīdz kāda līnija koda kicks in?

668
00:29:40,095 --> 00:29:40,970
Mērķauditorija: [dzirdams]

669
00:29:40,970 --> 00:29:43,060
DAVID J. Malan: Ja punkts, bet
rādītājs nav vienāds ar null.

670
00:29:43,060 --> 00:29:44,900
Kādā brīdī mans pirksta
būs norādot uz null

671
00:29:44,900 --> 00:29:47,070
un es esmu gatavojas realizēt
ka ir beigas šajā sarakstā.

672
00:29:47,070 --> 00:29:48,910
Tagad, tas ir maz
balta meli vienkāršību.

673
00:29:48,910 --> 00:29:51,580
Izrādās, ka pat tad, ja mēs
tikko uzzināju šo dot notācija

674
00:29:51,580 --> 00:29:55,220
struktūrām, rādītājs nav struktūrai.

675
00:29:55,220 --> 00:29:56,580
PTR ir kas?

676
00:29:56,580 --> 00:29:58,350
Vien vairāk nitpicky.

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

678
00:29:59,720 --> 00:30:01,360
Tas ir rādītājs, lai mezglu.

679
00:30:01,360 --> 00:30:03,120
Tas nav mezglu pati.

680
00:30:03,120 --> 00:30:06,650
Ja man nebija zvaigzne šeit, rādītājs
absolutely-- tas mezglā.

681
00:30:06,650 --> 00:30:08,650
Tas ir tāpat kā nedēļu viens
deklarācija ir mainīgs,

682
00:30:08,650 --> 00:30:10,120
pat ja vārds "mezgls" ir jauns.

683
00:30:10,120 --> 00:30:13,860
>> Bet, tiklīdz mēs ieviest
zvaigzne, tas tagad ir rādītājs, lai mezglu.

684
00:30:13,860 --> 00:30:17,960
Un diemžēl jūs nevarat izmantot
dot notācija par rādītāju.

685
00:30:17,960 --> 00:30:21,070
Jums ir izmantot bultiņu
apzīmējums, kas pārsteidzoši,

686
00:30:21,070 --> 00:30:23,470
Pirmo reizi kāda no daļām
no sintakse izskatās intuitīvi.

687
00:30:23,470 --> 00:30:25,245
Tas burtiski izskatās kā bulta.

688
00:30:25,245 --> 00:30:26,370
Un tā tas ir laba lieta.

689
00:30:26,370 --> 00:30:28,995
Un šeit lejā burtiski
izskatās kā bulta.

690
00:30:28,995 --> 00:30:31,870
Tāpēc es domāju, ka la-- man nav
domāju, ka es esmu pārāk izdarīšanas here-- I

691
00:30:31,870 --> 00:30:34,120
domāju, ka ir pēdējais jaunais gabals
no sintakses mēs ejam, lai redzētu.

692
00:30:34,120 --> 00:30:36,500
Un par laimi, tas ir patiešām
nedaudz vairāk intuitīvi.

693
00:30:36,500 --> 00:30:40,090
>> Tagad, tiem no jums, kas
varētu dod veco ceļu,

694
00:30:40,090 --> 00:30:42,550
Jūs joprojām varat izmantot dot notācija.

695
00:30:42,550 --> 00:30:45,380
Bet kā vienu pirmdienas
saruna, mēs vispirms

696
00:30:45,380 --> 00:30:50,530
jādodas tur, dodieties uz, ka
risināt, un pēc tam piekļūt lauku.

697
00:30:50,530 --> 00:30:51,897
Tātad tas ir arī pareizi.

698
00:30:51,897 --> 00:30:53,730
Un godīgi sakot, tas ir
nedaudz vairāk pedantiska.

699
00:30:53,730 --> 00:30:56,530
Tu burtiski sakot, dereference
rādītājs un iet tur.

700
00:30:56,530 --> 00:30:59,320
Tad paķert .n, lauka sauc n.

701
00:30:59,320 --> 00:31:01,370
Bet atklāti sakot, neviens negrib
rakstīt vai lasīt šo.

702
00:31:01,370 --> 00:31:03,620
Un tā pasaule izgudrots
bultiņa notācija, kas

703
00:31:03,620 --> 00:31:06,980
ir līdzvērtīga, identisks,
tas ir tikai sintaktisko cukura.

704
00:31:06,980 --> 00:31:10,570
Tātad iedomātā veids, kā sakot
izskatās labāk, vai izskatās vienkāršāk.

705
00:31:10,570 --> 00:31:12,296
>> Tāpēc tagad es esmu gatavojas darīt vienu citu lietu.

706
00:31:12,296 --> 00:31:15,420
Es esmu gatavojas teikt "pārtraukums", kad es esmu
atrada to, lai man nav turēt meklē to.

707
00:31:15,420 --> 00:31:17,620
Bet tas ir būtība
no meklēšanas funkciju.

708
00:31:17,620 --> 00:31:21,710
Bet tas ir daudz vieglāk, jo
end, nevis staigāt pa kodu.

709
00:31:21,710 --> 00:31:25,570
Tas ir patiešām formāla ieviešana
Meklēšanas mūsdienu izplatīšanas kodu.

710
00:31:25,570 --> 00:31:30,530
Es uzdrošinos teikt, ka ieliktnis nav
īpaši jautri staigāt pa

711
00:31:30,530 --> 00:31:33,180
vizuāli, nedz dzēst, pat
gan beigās dienā

712
00:31:33,180 --> 00:31:35,460
viņi vāra uz leju, lai godīgi
vienkāršas heuristics.

713
00:31:35,460 --> 00:31:36,330
>> Tāpēc pieņemsim to izdarītu.

714
00:31:36,330 --> 00:31:39,250
Ja jūs humors mani šeit, es darīju
celt ķekars stresa bumbas.

715
00:31:39,250 --> 00:31:40,620
Es, kas ķekars numuriem.

716
00:31:40,620 --> 00:31:46,562
Un mēs varētu saņemt tikai dažus brīvprātīgos
pārstāvēt 9, 17, 20, 22, 29 un 34?

717
00:31:46,562 --> 00:31:48,270
Tātad būtībā ikviens
kurš šeit šodien.

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

719
00:31:50,170 --> 00:31:52,760
Tas ir viens, divi, trīs,
četri, pieci, seši cilvēki.

720
00:31:52,760 --> 00:31:55,740
Un es esmu lūgts go-- redzēt, ne
viens aizmugurē rada viņu rokās.

721
00:31:55,740 --> 00:32:01,910
OK, viens, divi, trīs, četru,
five-- ļaujiet man slodze balance-- seši.

722
00:32:01,910 --> 00:32:03,051
OK, tu seši nākt uz augšu.

723
00:32:03,051 --> 00:32:04,050
Mums būs nepieciešams citu cilvēku.

724
00:32:04,050 --> 00:32:05,460
Mēs celta papildus stresa bumbas.

725
00:32:05,460 --> 00:32:08,200
Un, ja jūs varētu,
tikai mirklis, līnijas

726
00:32:08,200 --> 00:32:10,490
paši veido tikai
patīk šī attēla šeit.

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

728
00:32:15,200 --> 00:32:15,959
>> Viss labi.

729
00:32:15,959 --> 00:32:17,125
Paskatīsimies, kāds ir tavs vārds?

730
00:32:17,125 --> 00:32:17,550
>> AUDITORIJA: Andrew.

731
00:32:17,550 --> 00:32:18,800
>> DAVID J. Malan: Andrew,
Jums ir vairāki 9.

732
00:32:18,800 --> 00:32:19,540
Prieks iepazīties.

733
00:32:19,540 --> 00:32:20,400
Šeit jums iet.

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

735
00:32:21,593 --> 00:32:22,176
AUDITORIJA: 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
Numurs 17.

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

740
00:32:24,950 --> 00:32:25,450
Jā?

741
00:32:25,450 --> 00:32:26,400
>> AUDITORIJA: Es esmu Julia.

742
00:32:26,400 --> 00:32:26,980
>> DAVID J. Malan: Julia, David.

743
00:32:26,980 --> 00:32:27,545
Numurs 20.

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

745
00:32:28,507 --> 00:32:29,340
AUDITORIJA: Christian.

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

747
00:32:30,715 --> 00:32:31,541
Numurs 22.

748
00:32:31,541 --> 00:32:32,040
Un?

749
00:32:32,040 --> 00:32:32,649
>> AUDITORIJA: JP.

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

751
00:32:33,440 --> 00:32:34,880
Numurs 29.

752
00:32:34,880 --> 00:32:37,080
Tik iet uz priekšu un iegūt in-- Uh oh.

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

754
00:32:38,486 --> 00:32:38,985
Uh oh.

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

756
00:32:39,650 --> 00:32:40,150
Gaidīšanas.

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
Vai kāds ir marķieri?

760
00:32:43,682 --> 00:32:44,890
AUDITORIJA: Man Sharpie.

761
00:32:44,890 --> 00:32:45,660
DAVID J. Malan: Tev 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
Un vai kāds ir papīra?

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

766
00:32:51,562 --> 00:32:52,270
Saglabājiet lekciju.

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

768
00:32:53,810 --> 00:32:55,362
Come on.

769
00:32:55,362 --> 00:32:56,320
AUDITORIJA: Mēs esam ieguvuši to.

770
00:32:56,320 --> 00:32:57,600
DAVID J. Malan: Mēs saņēmām to?

771
00:32:57,600 --> 00:32:58,577
Nu labi, paldies.

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

773
00:33:01,380 --> 00:33:02,520
Šeit mēs iet.

774
00:33:02,520 --> 00:33:03,582
Bija tas no jums?

775
00:33:03,582 --> 00:33:04,540
Jūs vienkārši saglabāts dienā.

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

777
00:33:05,670 --> 00:33:07,220
Tā 29.

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

779
00:33:10,510 --> 00:33:11,110
Viss labi.

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

781
00:33:13,360 --> 00:33:14,890
Es kļūdaini 29, bet OK.

782
00:33:14,890 --> 00:33:15,720
Iet uz priekšu.

783
00:33:15,720 --> 00:33:18,114
Nu labi, es došu jums
savu pildspalvu atpakaļ momentāni.

784
00:33:18,114 --> 00:33:19,280
Tāpēc mums ir šiem ļaudīm šeit.

785
00:33:19,280 --> 00:33:20,330
Pieņemsim ir viens otru.

786
00:33:20,330 --> 00:33:23,750
Gabe, jūs vēlaties spēlēt
šeit pirmais elements?

787
00:33:23,750 --> 00:33:25,705
Mums nāksies jūs norādīt
pie šiem naudas ļaudīm.

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

789
00:33:26,930 --> 00:33:31,030
Tātad, 9, 17, 20, 22, veida
29, un pēc tam 34.

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

791
00:33:32,160 --> 00:33:33,325
Vai mēs zaudējam kādu?

792
00:33:33,325 --> 00:33:33,950
Man ir 34.

793
00:33:33,950 --> 00:33:36,730
Kur did-- OK, kurš grib būt 34?

794
00:33:36,730 --> 00:33:37,605
OK, nāk uz augšu, 34.

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

796
00:33:39,280 --> 00:33:41,220
Nu labi, tas būs
labi vērts kulminācija.

797
00:33:41,220 --> 00:33:41,550
Kāds ir tavs vārds?

798
00:33:41,550 --> 00:33:42,040
>> AUDITORIJA: Peter.

799
00:33:42,040 --> 00:33:43,456
>> DAVID J. Malan: Peter, nākt uz augšu.

800
00:33:43,456 --> 00:33:46,810
Labi, tāpēc šeit ir
viss ķekars mezgliem.

801
00:33:46,810 --> 00:33:49,060
Katrs no jums, puiši pārstāv
viena no šīm taisnstūri.

802
00:33:49,060 --> 00:33:51,930
Un Gabe, nedaudz dīvaina
cilvēks, kas pārstāv pirmās.

803
00:33:51,930 --> 00:33:54,850
Tātad viņa rādītājs ir nedaudz mazāka
uz ekrāna, nekā jebkuram citam.

804
00:33:54,850 --> 00:33:58,120
Un šajā gadījumā, katram jūsu kreisi
rokas gatavojas nu punktu uz leju,

805
00:33:58,120 --> 00:34:01,085
tādējādi pārstāv nulle, tāpēc
tikai trūkums rādītājs,

806
00:34:01,085 --> 00:34:03,210
vai tas būs vērsta
pie mezglu blakus jums.

807
00:34:03,210 --> 00:34:05,440
>> Tātad tagad, ja jūs izgreznot
paši, piemēram, attēla

808
00:34:05,440 --> 00:34:07,585
šeit, iet uz priekšu un punkts
otru, ar Gabe

809
00:34:07,585 --> 00:34:11,030
jo īpaši norādot uz
numurs 9 pārstāvēt sarakstu.

810
00:34:11,030 --> 00:34:14,050
OK, un numuru 34, kreiso roku
būtu vienkārši norādot uz grīdas.

811
00:34:14,050 --> 00:34:15,750
>> Labi, tāpēc tas ir saistīts saraksts.

812
00:34:15,750 --> 00:34:17,580
Tātad šis ir scenārijs jautājumu.

813
00:34:17,580 --> 00:34:20,210
Un tiešām, tas tiek uzrādīts
par kādu problēmu

814
00:34:20,210 --> 00:34:21,929
ka jūs varētu mēģināt atrisināt ar kodu.

815
00:34:21,929 --> 00:34:25,020
Jūs vēlaties, lai galu galā ievietot
jauns elements iekļaušanu sarakstā.

816
00:34:25,020 --> 00:34:27,494
Šajā gadījumā, mēs ejam
mēģiniet ievietojot numuru 55.

817
00:34:27,494 --> 00:34:28,500

818
00:34:28,500 --> 00:34:30,860
Bet tur būs
Dažādos gadījumus izskatīt.

819
00:34:30,860 --> 00:34:34,409
Un tiešām, šis būs viens
no big-picture takeaways šeit, ir,

820
00:34:34,409 --> 00:34:35,659
kādi ir dažādi gadījumi.

821
00:34:35,659 --> 00:34:39,120
Kādas ir citāda, ja apstākļi vai
zari, ka jūsu programma varētu būt?

822
00:34:39,120 --> 00:34:42,024
>> Nu, numuru jūs mēģināt
ievietot, ko mēs tagad zinām, ir 55,

823
00:34:42,024 --> 00:34:44,650
bet, ja jūs nezināt
iepriekš, es daresay

824
00:34:44,650 --> 00:34:47,840
ietilpst vismaz trīs
iespējamās situācijas.

825
00:34:47,840 --> 00:34:49,717
Kur varētu jauns elements būt?

826
00:34:49,717 --> 00:34:51,050
AUDITORIJA: Un beigās vai vidū.

827
00:34:51,050 --> 00:34:54,150
DAVID J. Malan: beigās, it
vidējā vai sākumā.

828
00:34:54,150 --> 00:34:56,650
Tāpēc es varu pieprasīt tur vismaz
Trīs problēmas, mums ir nepieciešams, lai atrisinātu.

829
00:34:56,650 --> 00:34:58,691
Pieņemsim izvēlēties to, kas ir iespējams
varbūt vienkāršākais

830
00:34:58,691 --> 00:35:01,090
viens, kur jaunu elementu
pieder sākumā.

831
00:35:01,090 --> 00:35:04,040
Tāpēc es esmu nāksies kodu diezgan
piemēram, meklēt, ko es tikko uzrakstīju.

832
00:35:04,040 --> 00:35:07,670
Un es esmu nāksies PTR, kas
Es pārstāvēt šeit ar manu pirkstu,

833
00:35:07,670 --> 00:35:08,370
kā parasti.

834
00:35:08,370 --> 00:35:12,430
>> Un atcerieties, kāda vērtība
vai mēs sāktu PTR to?

835
00:35:12,430 --> 00:35:15,300
Tātad mēs inicializēts to null sākotnēji.

836
00:35:15,300 --> 00:35:16,410

837
00:35:16,410 --> 00:35:19,770
Bet tad ko gan mēs darām, kad mēs
bija iekšā mūsu meklēšanas funkciju?

838
00:35:19,770 --> 00:35:20,940

839
00:35:20,940 --> 00:35:24,870
Mēs noteikti tas ir vienāds ar, pirmkārt,
kas nenozīmē to izdarīt.

840
00:35:24,870 --> 00:35:25,890

841
00:35:25,890 --> 00:35:30,570
Ja es noteikti PTR ir vienāda ar pirmo, ko
būtu mana roka tiešām norādot uz?

842
00:35:30,570 --> 00:35:31,070
Labi.

843
00:35:31,070 --> 00:35:33,290
Tātad, ja Gabe un es gatavojas
lai būtu vienādas vērtības šeit

844
00:35:33,290 --> 00:35:34,760
mums ir gan stacionārajiem uz numuru 9.

845
00:35:34,760 --> 00:35:36,420
>> Tātad tas bija sākums mūsu stāsts.

846
00:35:36,420 --> 00:35:38,700
Un tagad tas ir tikai vienkāršs,
kaut sintakse ir jauns.

847
00:35:38,700 --> 00:35:40,580
Konceptuāli tas ir tikai lineārs meklēšanu.

848
00:35:40,580 --> 00:35:42,750
Ir 55 vienāds ar 9?

849
00:35:42,750 --> 00:35:45,559
Vai drīzāk, teiksim mazāk kā 9.

850
00:35:45,559 --> 00:35:47,600
Tā kā es cenšos
izdomāt, kur likt 55.

851
00:35:47,600 --> 00:35:51,270
Mazāks par 9, mazāks par 17, mazāks
par 20, mazāks par 22, mazāks par 29,

852
00:35:51,270 --> 00:35:52,510
mazāk nekā 34, Nr.

853
00:35:52,510 --> 00:35:55,080
Tāpēc tagad mēs esam gadījumā
viena no vismaz trīs.

854
00:35:55,080 --> 00:35:59,910
>> Ja es gribu, lai ievietotu 55 pār šeit, kādi
līnijas koda nepieciešamību saņemt izpildīts?

855
00:35:59,910 --> 00:36:01,890
Kā šo attēlu
cilvēkiem ir jāmaina?

856
00:36:01,890 --> 00:36:03,181
Ko man darīt ar manu kreiso roku?

857
00:36:03,181 --> 00:36:04,530

858
00:36:04,530 --> 00:36:07,360
Tam vajadzētu būt nulle sākotnēji
jo Es beigās sarakstā.

859
00:36:07,360 --> 00:36:09,318
Un ko vajadzētu notikt
šeit ar Pēteri, tas bija?

860
00:36:09,318 --> 00:36:10,520

861
00:36:10,520 --> 00:36:12,430
Viņš acīmredzot gatavojas norādīt uz mani.

862
00:36:12,430 --> 00:36:15,580
Tāpēc es pretenziju tur ir vismaz divas rindas
Koda parauga kodu no šodienas

863
00:36:15,580 --> 00:36:18,570
kas notiek, lai to īstenotu
scenārijs pievienojot 55 pie astes.

864
00:36:18,570 --> 00:36:20,950
Un es varētu būt kāds hop
augšu un tikai pārstāv 55?

865
00:36:20,950 --> 00:36:22,200
Nu labi, jums ir jaunais 55.

866
00:36:22,200 --> 00:36:23,580

867
00:36:23,580 --> 00:36:27,054
>> Tāpēc tagad, ko tad, ja nākamais
scenārijs nāk kopā,

868
00:36:27,054 --> 00:36:29,720
, un mēs vēlamies, lai ievietotu tajā
sākas vai vadītājs šo sarakstu?

869
00:36:29,720 --> 00:36:31,100
Un kāds ir tavs vārds, numuru 55?

870
00:36:31,100 --> 00:36:31,420
>> AUDITORIJA: Jack.

871
00:36:31,420 --> 00:36:32,295
>> DAVID J. Malan: Jack?

872
00:36:32,295 --> 00:36:33,585
OK, nice to meet you.

873
00:36:33,585 --> 00:36:34,210
Laipni lūdzam uz klāja.

874
00:36:34,210 --> 00:36:36,640
Tāpēc tagad mēs ejam
ievietot, teiksim, numuru 5.

875
00:36:36,640 --> 00:36:39,840
Lūk otrais gadījums
Trīs mēs nāca klajā ar pirms tam.

876
00:36:39,840 --> 00:36:43,050
Tātad, ja 5 pieder sākumā,
pieņemsim redzēt, kā mēs redzam, ka out.

877
00:36:43,050 --> 00:36:46,310
Es sāktu manu PTR
rādītāju uz numuru 9 vēlreiz.

878
00:36:46,310 --> 00:36:49,140
Un es realizēts, oh, 5 ir mazāks par 9.

879
00:36:49,140 --> 00:36:50,880
Tātad noteikt šo priekšstatu par mums.

880
00:36:50,880 --> 00:36:54,820
Kuru rokas, Gabe ir vai Dāvida
or-- kas ir cipars 9 vārds?

881
00:36:54,820 --> 00:36:55,740
>> AUDITORIJA: Jen.

882
00:36:55,740 --> 00:36:58,406
>> DAVID J. Malan: Jen hands--
kas mūsu rokās ir jāmaina?

883
00:36:58,406 --> 00:36:58,905

884
00:36:58,905 --> 00:37:00,970
Labi, tāpēc Gabe norāda uz to, ko tagad?

885
00:37:00,970 --> 00:37:01,640
Uz mani.

886
00:37:01,640 --> 00:37:02,750
Es esmu jaunā mezglu.

887
00:37:02,750 --> 00:37:04,870
Tāpēc es ņemšu tikai veida kustībā
šeit, lai redzētu to vizuāli.

888
00:37:04,870 --> 00:37:06,435
Un tikmēr, ko es varu norādīt, ka?

889
00:37:06,435 --> 00:37:07,910

890
00:37:07,910 --> 00:37:09,020
Still, kur es esmu, norādot.

891
00:37:09,020 --> 00:37:10,000
Tāpēc, ka tas arī viss.

892
00:37:10,000 --> 00:37:13,717
Tik vienkārši tiešām viena līnija koda labojumi
šo konkrēto jautājumu, tā varētu likties.

893
00:37:13,717 --> 00:37:14,800
Labi, tā, ka ir labi.

894
00:37:14,800 --> 00:37:17,580
Un var kāds būt vietturis 5?

895
00:37:17,580 --> 00:37:18,080
Nāciet uz augšu.

896
00:37:18,080 --> 00:37:20,270

897
00:37:20,270 --> 00:37:21,320
Mēs tev nākamreiz.

898
00:37:21,320 --> 00:37:24,280
>> Visas tiesības, tāpēc now-- un
Kā malā, nosaukumi

899
00:37:24,280 --> 00:37:28,510
Es neesmu padarot skaidra norāde uz tiesībām
Tagad, pred rādītājs, priekštecis rādītājs

900
00:37:28,510 --> 00:37:31,260
un jaunu rādītāju, kas ir
tikai vārdi dots

901
00:37:31,260 --> 00:37:35,280
parauga kodu uz norādes vai
manas rokas, kas ir sava veida norādot apkārt.

902
00:37:35,280 --> 00:37:36,060
Kāds ir tavs vārds?

903
00:37:36,060 --> 00:37:36,700
>> AUDITORIJA: Christine.

904
00:37:36,700 --> 00:37:37,100
>> DAVID J. Malan: Christine.

905
00:37:37,100 --> 00:37:38,090
Laipni lūdzam uz klāja.

906
00:37:38,090 --> 00:37:42,180
Labi, tāpēc pieņemsim apsvērt tagad
nedaudz vairāk kaitinošas scenārijs,

907
00:37:42,180 --> 00:37:46,350
ar kuru es gribu, lai ievietotu
kaut kas līdzīgs 26 stāšanās šis.

908
00:37:46,350 --> 00:37:47,090
20?

909
00:37:47,090 --> 00:37:47,590
Kas?

910
00:37:47,590 --> 00:37:50,510
Tie are-- laba lieta, mēs esam šo pildspalvu.

911
00:37:50,510 --> 00:37:51,955
Nu labi, 20.

912
00:37:51,955 --> 00:37:53,640

913
00:37:53,640 --> 00:37:57,570
Ja kāds varētu iegūt citu gabals
papīrs gatavs, tikai case-- labi.

914
00:37:57,570 --> 00:37:58,370
Ak, interesanti.

915
00:37:58,370 --> 00:37:59,760

916
00:37:59,760 --> 00:38:02,390
Nu tas ir piemērs
par lekciju bug.

917
00:38:02,390 --> 00:38:03,894
Labi, lai to, kas ir jūsu vārds atkal?

918
00:38:03,894 --> 00:38:04,560
AUDITORIJA: Julia.

919
00:38:04,560 --> 00:38:07,559
DAVID J. Malan: Julia, jūs varat pop
, un izlikties, tu nekad tur?

920
00:38:07,559 --> 00:38:09,040
Labi, tas nekad nav noticis.

921
00:38:09,040 --> 00:38:09,680
Paldies.

922
00:38:09,680 --> 00:38:12,180
Tātad pieņemsim, ka mēs gribam ievietot
Julia šajā saistīts sarakstā.

923
00:38:12,180 --> 00:38:13,780
Viņa ir numurs 20.

924
00:38:13,780 --> 00:38:15,530
Un, protams, viņa ir
gatavojas piederīgs

925
00:38:15,530 --> 00:38:17,521
begin-- neliecina par kaut ko vēl.

926
00:38:17,521 --> 00:38:20,020
Tātad jūsu rokas var veida būt
leju null vai kādu atkritumu vērtību.

927
00:38:20,020 --> 00:38:21,210
Pieņemsim pateikt ātri stāstu.

928
00:38:21,210 --> 00:38:22,980
Es esmu norādot uz vairākiem 5 šoreiz.

929
00:38:22,980 --> 00:38:23,880
Tad es varētu pārbaudīt 9.

930
00:38:23,880 --> 00:38:25,130
Tad es varētu pārbaudīt 17.

931
00:38:25,130 --> 00:38:26,247
Tad es varētu pārbaudīt 22.

932
00:38:26,247 --> 00:38:27,650

933
00:38:27,650 --> 00:38:32,485
Un es saprotu, ooh, Julia
ir jāiet pirms 22.

934
00:38:32,485 --> 00:38:33,580

935
00:38:33,580 --> 00:38:34,660
Tātad, kas nepieciešams, lai notiktu?

936
00:38:34,660 --> 00:38:35,786

937
00:38:35,786 --> 00:38:36,910
Kuru rokās ir jāmaina?

938
00:38:36,910 --> 00:38:38,360
Julia s, raktuves, or--
kāds ir tavs vārds atkal?

939
00:38:38,360 --> 00:38:39,230
>> AUDITORIJA: Christian.

940
00:38:39,230 --> 00:38:40,060
>> DAVID J. Malan: Christian vai?

941
00:38:40,060 --> 00:38:40,560
>> AUDITORIJA: Andy.

942
00:38:40,560 --> 00:38:40,905
>> DAVID J. Malan: Andy.

943
00:38:40,905 --> 00:38:41,654
Kristiešu vai Andy?

944
00:38:41,654 --> 00:38:44,280

945
00:38:44,280 --> 00:38:45,690
Andy ir nepieciešams norādīt uz?

946
00:38:45,690 --> 00:38:46,780

947
00:38:46,780 --> 00:38:47,341
Julia.

948
00:38:47,341 --> 00:38:47,840
Viss labi.

949
00:38:47,840 --> 00:38:48,960
Tātad Andy, jūs vēlaties norādīt uz Julia?

950
00:38:48,960 --> 00:38:50,120
Bet pagaidiet minūti.

951
00:38:50,120 --> 00:38:53,260
Stāsts līdz šim,
Es esmu veida viena

952
00:38:53,260 --> 00:38:56,800
atbild, tādā nozīmē, ka
rādītājs ir lieta, kas ir

953
00:38:56,800 --> 00:38:57,850
pārvietojas pa sarakstu.

954
00:38:57,850 --> 00:39:00,800
Mums varētu būt nosaukumu Andy, bet
tur nav mainīgo sauc Andy.

955
00:39:00,800 --> 00:39:04,320
Tikai citu mainīgais mums ir
Pirmais, kurš pārstāv Gabe.

956
00:39:04,320 --> 00:39:07,690
>> Tātad tas ir faktiski tāpēc, tādējādi
šim mēs esam nav nepieciešams to.

957
00:39:07,690 --> 00:39:10,846
Bet tagad uz ekrāna ir
pieminēt atkal no ieteik rādītāju.

958
00:39:10,846 --> 00:39:11,970
Tāpēc ļaujiet man būt precīzāk.

959
00:39:11,970 --> 00:39:14,820
Ja tas ir rādītājs, man bija labāk
iegūt nedaudz vairāk viedo

960
00:39:14,820 --> 00:39:15,950
par manu atkārtojuma.

961
00:39:15,950 --> 00:39:19,580
Ja jums nav prātā manu iet cauri šeit
atkal, norādot šeit, norādot šeit.

962
00:39:19,580 --> 00:39:22,500
Bet man ir ieteik rādītāju,
priekšgājējs rādītājs, kas ir

963
00:39:22,500 --> 00:39:24,740
veida norādot uz
elements Man bija tikai pie.

964
00:39:24,740 --> 00:39:27,330
Tātad, kad es iet šeit, tagad
manu kreiso roku atjauninājumus.

965
00:39:27,330 --> 00:39:29,370
Kad es iet šeit manu kreiso roku atjauninājumus.

966
00:39:29,370 --> 00:39:33,090
Un tagad man ir ne tikai rādītāju uz
elements, kas iet pēc Julia,

967
00:39:33,090 --> 00:39:36,300
Man joprojām ir rādītāju uz
Andy, elements pirms.

968
00:39:36,300 --> 00:39:39,430
Tātad jums ir piekļuve, būtībā,
rīvmaizes, ja jūs,

969
00:39:39,430 --> 00:39:41,500
visiem nepieciešamās norādes.

970
00:39:41,500 --> 00:39:43,710
>> Tātad, ja es esmu norādot uz
Andy, un es esmu arī norādot

971
00:39:43,710 --> 00:39:47,105
pie Kristietis, kura rokās
tagad būtu jānorāda citur?

972
00:39:47,105 --> 00:39:48,770

973
00:39:48,770 --> 00:39:51,960
Tātad Andy tagad var norādīt uz Julia.

974
00:39:51,960 --> 00:39:54,460
Julia tagad var norādīt uz kristiešu.

975
00:39:54,460 --> 00:39:56,950
Tāpēc, ka viņa var kopēt manu
labā roka ir rādītājs.

976
00:39:56,950 --> 00:40:00,044
Un tas faktiski liek jums
atpakaļ šajā vietā šeit.

977
00:40:00,044 --> 00:40:02,460
Tātad īsumā, kaut arī tas
sper mūs veida visiem laikiem

978
00:40:02,460 --> 00:40:04,510
faktiski atjaunināt
saistīta sarakstu, saprotam

979
00:40:04,510 --> 00:40:06,580
ka operāciju
ir salīdzinoši vienkārši.

980
00:40:06,580 --> 00:40:10,030
Tas ir viens, divi, trīs
rindas kods galu galā.

981
00:40:10,030 --> 00:40:12,780
Bet aptīt tiem
koda rindiņas varbūtējs

982
00:40:12,780 --> 00:40:16,350
ir mazliet loģikas, kas efektīvi
uzdod jautājumu, kur mēs esam?

983
00:40:16,350 --> 00:40:18,970
Vai mēs sākumā,
vidējā vai gala?

984
00:40:18,970 --> 00:40:21,890
>> Tagad, ir noteikti daži citi
operācijas mēs varētu īstenot.

985
00:40:21,890 --> 00:40:24,880
Un šīs bildes šeit vienkārši attēlot
tas, ko mēs tikko izdarījām ar cilvēkiem.

986
00:40:24,880 --> 00:40:26,080
Kas par noņemšanu?

987
00:40:26,080 --> 00:40:30,650
Ja es gribu, lai, piemēram,
noņemtu numuru 34 vai 55,

988
00:40:30,650 --> 00:40:34,680
Es varētu būt tāda paša veida kodu,
bet es esmu gatavojas nepieciešama vienu vai divus soļus.

989
00:40:34,680 --> 00:40:36,110
Tāpēc, ka to, kas jauns?

990
00:40:36,110 --> 00:40:40,460
Ja es izņemt kāds beigās,
piemēram numuru 55, un pēc tam 34,

991
00:40:40,460 --> 00:40:42,995
, kas ir arī mainīties, jo man darīt?

992
00:40:42,995 --> 00:40:44,870
Man ir ne evict--
kāds ir tavs vārds atkal?

993
00:40:44,870 --> 00:40:45,380
>> AUDITORIJA: Jack.

994
00:40:45,380 --> 00:40:46,255
>> DAVID J. Malan: Jack.

995
00:40:46,255 --> 00:40:49,770
Man ir ne tikai evict-- bezmaksas Jack,
tik burtiski zvanīt bezmaksas Jack, vai vismaz

996
00:40:49,770 --> 00:40:53,530
rādītājs arī tur, bet tagad
to, kas ir nepieciešams, lai mainītu ar Pēteri?

997
00:40:53,530 --> 00:40:55,510
Viņa roka labāk sākt uz leju.

998
00:40:55,510 --> 00:40:59,300
Jo, tiklīdz es aicinu bez maksas
Jack, ja Pētera joprojām norādot uz Jack

999
00:40:59,300 --> 00:41:02,530
un tāpēc es glabāt šķērso
sarakstu un piekļuves šis rādītājs,

1000
00:41:02,530 --> 00:41:05,650
tas ir tad, kad mūsu vecais draugs segmentācija
vaina tiešām var kick.

1001
00:41:05,650 --> 00:41:07,860
Tāpēc, ka esam radījuši
atmiņas atpakaļ uz Jack.

1002
00:41:07,860 --> 00:41:10,760
>> Jūs varat palikt tur
neveikli tikai brīdi.

1003
00:41:10,760 --> 00:41:13,410
Tāpēc, ka mums ir tikai pāris
gala darbības izskatīt.

1004
00:41:13,410 --> 00:41:15,600
Noņemot galvu saraksta,
vai beginning-- un tas viens ir

1005
00:41:15,600 --> 00:41:16,349
nedaudz kaitinošas.

1006
00:41:16,349 --> 00:41:19,640
Tāpēc, ka mums ir jāzina, ka Gabe
ir sava veida īpašs šajā programmā.

1007
00:41:19,640 --> 00:41:21,440
Jo tiešām, viņam ir savs rādītājs.

1008
00:41:21,440 --> 00:41:24,860
Viņš ir ne tikai tiek norādīja,
kā gandrīz visi citi šeit.

1009
00:41:24,860 --> 00:41:28,112
>> Tātad, ja galva sarakstā
noņemts, kura rokās ir nepieciešams mainīt tagad?

1010
00:41:28,112 --> 00:41:29,070
Kāds ir jūsu vārds atkal?

1011
00:41:29,070 --> 00:41:29,450
>> AUDITORIJA: Christine.

1012
00:41:29,450 --> 00:41:31,408
>> DAVID J. Malan: Es esmu šausmīgi
pie vārdiem, acīmredzot.

1013
00:41:31,408 --> 00:41:34,011
Tik Christine un Gabe,
kuru rokās ir jāmaina

1014
00:41:34,011 --> 00:41:36,510
kad mēs cenšamies, lai novērstu Christine,
numurs 5, no attēla?

1015
00:41:36,510 --> 00:41:37,550

1016
00:41:37,550 --> 00:41:38,820
Labi, tāpēc pieņemsim do Gabe.

1017
00:41:38,820 --> 00:41:40,950
Gabe dodas uz punktu,
domājams, uz numuru 9.

1018
00:41:40,950 --> 00:41:42,230

1019
00:41:42,230 --> 00:41:44,642
Bet ko nākamo vajadzētu notikt?

1020
00:41:44,642 --> 00:41:46,600
AUDITORIJA: Christine vajadzētu
būt null [nedzirdama].

1021
00:41:46,600 --> 00:41:50,244
DAVID J. Malan: Labi, mums vajadzētu, iespējams,
make-- es dzirdēju "null" kaut kur.

1022
00:41:50,244 --> 00:41:51,410
AUDITORIJA: Null un bez viņas.

1023
00:41:51,410 --> 00:41:51,855
DAVID J. Malan: null, ko?

1024
00:41:51,855 --> 00:41:53,074
AUDITORIJA: Null un bez viņas.

1025
00:41:53,074 --> 00:41:54,490
DAVID J. Malan: Null un bez viņas.

1026
00:41:54,490 --> 00:41:55,422
Tāpēc tas ir ļoti viegli.

1027
00:41:55,422 --> 00:41:58,380
Un tas ir lieliski, ka jūs tagad kārtošanas
Stāvvietu tur, nevis piederību.

1028
00:41:58,380 --> 00:42:00,430
Tāpēc, ka jūs esat bijis
atsaistīts no saraksta.

1029
00:42:00,430 --> 00:42:02,820
Jūs esat efektīvi bijuši
bāreņiem no saraksta.

1030
00:42:02,820 --> 00:42:07,770
Un tā mums bija labāk zvanīt bez tagad
Christine dot šo atmiņu atpakaļ.

1031
00:42:07,770 --> 00:42:10,240
Pretējā gadījumā katru reizi, kad mēs
izdzēst mezglu no saraksta

1032
00:42:10,240 --> 00:42:14,230
mēs varētu padarīt sarakstu
īsāks, bet faktiski samazinās

1033
00:42:14,230 --> 00:42:15,096
lielums atmiņā.

1034
00:42:15,096 --> 00:42:17,720
Un tāpēc, ja mēs saglabātu pievienojot un
piebilstot, pievienojot lietas sarakstā,

1035
00:42:17,720 --> 00:42:19,280
mans dators varētu saņemt lēnāk
un lēnāk un lēnāk,

1036
00:42:19,280 --> 00:42:21,740
tāpēc, ka es skrienu no
atmiņa, pat ja es neesmu faktiski

1037
00:42:21,740 --> 00:42:25,580
izmantojot Christine s baiti
atmiņas vairs.

1038
00:42:25,580 --> 00:42:28,500
>> Tātad beigās ir citi
scenāriji, no course-- izņemšanas

1039
00:42:28,500 --> 00:42:30,640
vidū, izvešana
gada beigās, kā mēs redzējām.

1040
00:42:30,640 --> 00:42:32,348
Bet vairāk interesanti
Tagad izaicinājums ir

1041
00:42:32,348 --> 00:42:34,770
būs izskatīt precīzi
kāda darbības laiks ir.

1042
00:42:34,770 --> 00:42:36,640
Tātad, ne tikai jūs varat saglabāt savu
papīra gabalus, ja, Gabe,

1043
00:42:36,640 --> 00:42:38,640
jūs neiebilstat dodot
visi stress bumbu.

1044
00:42:38,640 --> 00:42:42,100
Paldies jums tik daudz, lai mūsu saistīts sarakstam
brīvprātīgo šeit, ja varētu.

1045
00:42:42,100 --> 00:42:45,320
>> [Aplausi]

1046
00:42:45,320 --> 00:42:46,700
>> DAVID J. Malan: Nu labi.

1047
00:42:46,700 --> 00:42:51,110
Tātad pāris analītiskā
jautājumi, tad, ja es varētu.

1048
00:42:51,110 --> 00:42:59,670
Mēs esam redzējuši šo pierakstu pirms,
big O un omega, augšējo robežas

1049
00:42:59,670 --> 00:43:02,520
un apakšējā robeža uz
darbības laiks kādu algoritmu.

1050
00:43:02,520 --> 00:43:04,950
Tātad, pieņemsim apsvērt tikko
pāris jautājumiem.

1051
00:43:04,950 --> 00:43:07,090
>> Viens, un mēs teicām to
pirms, kas ir skriešanas

1052
00:43:07,090 --> 00:43:10,647
laiks meklēt
sarakstu ziņā lielo O?

1053
00:43:10,647 --> 00:43:13,480
Kas ir augšējā robeža uz darbību
laiks meklējot saistīts saraksts

1054
00:43:13,480 --> 00:43:16,340
kas īstenots ar mūsu brīvprātīgie šeit?

1055
00:43:16,340 --> 00:43:17,820
Tas ir liels O n, lineāra.

1056
00:43:17,820 --> 00:43:20,630
Jo sliktākajā gadījumā,
elements, piemēram, 55,

1057
00:43:20,630 --> 00:43:23,830
mēs varētu būt meklējat varētu būt tur, kur
Jack bija, visu veidu beigās.

1058
00:43:23,830 --> 00:43:28,250
Un diemžēl, atšķirībā no masīva
mēs nevaram iegūt iedomātā šoreiz.

1059
00:43:28,250 --> 00:43:31,820
Pat ja visiem mūsu cilvēkiem bija
kārtoti no maziem elementiem, 5,

1060
00:43:31,820 --> 00:43:35,900
visu ceļu līdz lielākiem elementu,
55, ka parasti laba lieta.

1061
00:43:35,900 --> 00:43:38,815
Bet ko dara šo pieņēmumu
vairs neļauj mums darīt?

1062
00:43:38,815 --> 00:43:39,775

1063
00:43:39,775 --> 00:43:40,650
Mērķauditorija: [dzirdams]

1064
00:43:40,650 --> 00:43:40,920
DAVID J. Malan: Say atkal?

1065
00:43:40,920 --> 00:43:41,800
AUDITORIJA: Brīvpiekļuves.

1066
00:43:41,800 --> 00:43:43,049
DAVID J. Malan: Brīvpiekļuves.

1067
00:43:43,049 --> 00:43:46,330
Un, savukārt, tas nozīmē, ka mēs varam ne
ilgāk izmantot vāja nullēm, intuīciju,

1068
00:43:46,330 --> 00:43:49,365
un acīmredzamības izmantojot bināro
meklēt un sadalīt un iekarot.

1069
00:43:49,365 --> 00:43:51,240
Jo, pat ja mēs
cilvēki varētu acīmredzami

1070
00:43:51,240 --> 00:43:54,610
redzēt, ka Andy vai kristietis, bija
apmēram vidū sarakstā

1071
00:43:54,610 --> 00:43:57,670
mēs tikai zinām, ka
dators nokrejojot sarakstu

1072
00:43:57,670 --> 00:43:59,029
no paša sākuma.

1073
00:43:59,029 --> 00:44:00,570
Tātad mēs esam atteikušies, ka brīva piekļuve.

1074
00:44:00,570 --> 00:44:04,380
>> Tik liels O n tagad ir augšējā
saistošs mūsu meklēšanas laiku.

1075
00:44:04,380 --> 00:44:07,920
Kas par omega mūsu meklēt?

1076
00:44:07,920 --> 00:44:11,535
Kāda ir zemākā robeža uz meklēšanu
kādu numuru šajā sarakstā?

1077
00:44:11,535 --> 00:44:12,410
Mērķauditorija: [dzirdams]

1078
00:44:12,410 --> 00:44:13,040
DAVID J. Malan: Say atkal?

1079
00:44:13,040 --> 00:44:13,420
AUDITORIJA: One.

1080
00:44:13,420 --> 00:44:13,800
DAVID J. Malan: One.

1081
00:44:13,800 --> 00:44:14,760
Tik nemainīgs laiku.

1082
00:44:14,760 --> 00:44:17,020
Labākajā gadījumā, Christine ir
pat pie saraksta sākumā.

1083
00:44:17,020 --> 00:44:19,020
Un mēs meklējam
numurs 5, tāpēc mēs atradām viņu.

1084
00:44:19,020 --> 00:44:19,787
Tāpēc nav liels darījumu.

1085
00:44:19,787 --> 00:44:22,370
Bet viņa ir nokļuvis būt
saraksta sākumā šajā gadījumā.

1086
00:44:22,370 --> 00:44:23,745
Ko par kaut ko, piemēram, dzēst?

1087
00:44:23,745 --> 00:44:24,717

1088
00:44:24,717 --> 00:44:26,300
Ko darīt, ja jūs vēlaties izdzēst elementu?

1089
00:44:26,300 --> 00:44:29,200
Kas ir augšējo robežu un apakšējo robežu
gada dzēšot kaut ko no saistīta

1090
00:44:29,200 --> 00:44:29,699
uzskaitīt?

1091
00:44:29,699 --> 00:44:35,195

1092
00:44:35,195 --> 00:44:36,070
Mērķauditorija: [dzirdams]

1093
00:44:36,070 --> 00:44:36,420
DAVID J. Malan: Say atkal?

1094
00:44:36,420 --> 00:44:37,067
AUDITORIJA: n.

1095
00:44:37,067 --> 00:44:38,900
DAVID J. Malan: n ir
patiešām augšējo robežu.

1096
00:44:38,900 --> 00:44:41,700
Jo sliktākajā gadījumā mēs cenšamies
izdzēst Jack, kā mēs tikko izdarīja.

1097
00:44:41,700 --> 00:44:43,050
Viņš visu ceļu beigās.

1098
00:44:43,050 --> 00:44:45,419
Ņem mūs uz visiem laikiem, vai
n soļi, lai atrastu viņu.

1099
00:44:45,419 --> 00:44:46,460
Tā ka ir augšējo robežu.

1100
00:44:46,460 --> 00:44:47,430
Tas ir lineāra, pārliecināts.

1101
00:44:47,430 --> 00:44:50,970
Un labākajā gadījumā darba laika, vai
apakšējās robežas labākajā gadījumā

1102
00:44:50,970 --> 00:44:51,975
būtu nemainīgs laiks.

1103
00:44:51,975 --> 00:44:54,600
Jo varbūt mēs cenšamies izdzēst
Christine, un mēs tikai iegūt laimīgs

1104
00:44:54,600 --> 00:44:55,558
viņa sākumā.

1105
00:44:55,558 --> 00:44:56,350
Tagad jāgaida minūti.

1106
00:44:56,350 --> 00:44:59,370
Gabe bija arī gada sākumā,
un mums bija arī atjaunināt Gabe.

1107
00:44:59,370 --> 00:45:01,150
Tā, ka bija ne tikai viens solis.

1108
00:45:01,150 --> 00:45:04,210
Tātad, tas ir patiešām nemainīgs
laiks, labākajā gadījumā,

1109
00:45:04,210 --> 00:45:06,345
noņemt mazāko elementu?

1110
00:45:06,345 --> 00:45:07,360

1111
00:45:07,360 --> 00:45:10,960
Tas ir, lai gan tas varētu būt divas,
trīs, vai pat 100 koda rindiņas,

1112
00:45:10,960 --> 00:45:14,000
ja tas ir tas pats skaits
līnijas, nevis dažās cilpa,

1113
00:45:14,000 --> 00:45:16,577
un neatkarīgi no lieluma
saraksta, absolūti.

1114
00:45:16,577 --> 00:45:18,660
Dzēšot elementu pie
saraksta sākumā,

1115
00:45:18,660 --> 00:45:21,940
pat tad, ja mums ir tikt galā ar
Gabe, joprojām ir nemainīgs laika.

1116
00:45:21,940 --> 00:45:24,220
>> Tātad tas šķiet
masveida solis atpakaļ.

1117
00:45:24,220 --> 00:45:27,000
Un kāda laika izšķiešana
ja nedēļā vienā un nedēļu

1118
00:45:27,000 --> 00:45:30,250
nulle mums bija ne tikai
pseudocode kods bet faktiskais kods

1119
00:45:30,250 --> 00:45:35,780
ieviest kaut ko, kas ir žurnāla
bāze n, vai ielogojieties, drīzāk, no n, bāze 2,

1120
00:45:35,780 --> 00:45:37,150
attiecībā uz tās darba laika.

1121
00:45:37,150 --> 00:45:40,710
Tātad, kāpēc heck vēlētos mēs gribam sākt
izmantojot kaut ko līdzīgu saistītajā sarakstā?

1122
00:45:40,710 --> 00:45:41,517
Jā.

1123
00:45:41,517 --> 00:45:44,022
>> AUDITORIJA: Tātad jūs varat pievienot
elementi masīva.

1124
00:45:44,022 --> 00:45:46,230
DAVID J. Malan: Tātad jūs varat
pievienot elementus uz masīvu.

1125
00:45:46,230 --> 00:45:47,550
Un tas arī ir tematiska.

1126
00:45:47,550 --> 00:45:49,740
Un mēs turpināsim redzēt
tam, šis kompromiss, daudz

1127
00:45:49,740 --> 00:45:51,573
kā mēs esam redzējuši
kompromiss ar sapludināšanas kārtošanas.

1128
00:45:51,573 --> 00:45:54,606
Mēs tiešām varētu paātrināt
meklēšanu vai šķirošanu, drīzāk,

1129
00:45:54,606 --> 00:45:57,480
ja mēs tērēt mazliet vairāk vietas un
ir papildu rieciens atmiņas

1130
00:45:57,480 --> 00:45:58,760
vai masīvs sapludināšanas kārtošanas.

1131
00:45:58,760 --> 00:46:01,270
Bet mēs tērēt vairāk
telpa, bet mums ietaupīt laiku.

1132
00:46:01,270 --> 00:46:04,820
Šajā gadījumā, mēs esam
atmest laiku, bet mēs esam

1133
00:46:04,820 --> 00:46:08,170
iegūt elastību,
dinamika, ja jūs,

1134
00:46:08,170 --> 00:46:10,280
kas ir neapšaubāmi pozitīva iezīme.

1135
00:46:10,280 --> 00:46:11,520
>> Mēs arī izdevumu telpu.

1136
00:46:11,520 --> 00:46:13,710
Kādā jēga ir saistīta
uzskaitīt dārgāks

1137
00:46:13,710 --> 00:46:15,700
izteiksmē vietas nekā masīva?

1138
00:46:15,700 --> 00:46:18,379

1139
00:46:18,379 --> 00:46:19,920
Ja ir papildu telpas nāk no?

1140
00:46:19,920 --> 00:46:20,460
Yeah?

1141
00:46:20,460 --> 00:46:21,800
>> Mērķauditorija: [dzirdams] rādītājs.

1142
00:46:21,800 --> 00:46:23,310
>> DAVID J. Malan: Jā, mēs
ir arī rādītājs.

1143
00:46:23,310 --> 00:46:25,560
Tātad šis ir minorly kaitinošas
jo vairs esmu

1144
00:46:25,560 --> 00:46:27,780
Es glabāšanai tikai int
pārstāvēt int.

1145
00:46:27,780 --> 00:46:30,990
Es esmu glabāšanai int un A
rādītājs, kas arī ir 32 biti.

1146
00:46:30,990 --> 00:46:33,470
Tāpēc es esmu burtiski divkāršojies
vietas daudzumu iesaistīti.

1147
00:46:33,470 --> 00:46:36,040
Tātad tas ir kompromiss, bet
kas ir gadījumā int.

1148
00:46:36,040 --> 00:46:39,580
Pieņemsim, ka jūs neesat glabāšanai int,
bet pieņemsim, ka katrs no šiem taisnstūriem

1149
00:46:39,580 --> 00:46:43,290
vai katrs no šiem cilvēkiem tika pārstāv
vārds, angļu vārds, kas

1150
00:46:43,290 --> 00:46:46,430
varētu būt piecas rakstzīmes, 10
rakstzīmes, varbūt pat vairāk.

1151
00:46:46,430 --> 00:46:49,940
Tam pievienojot tikai 32 vairāk bitu
varētu būt mazāk par lielu darījumu.

1152
00:46:49,940 --> 00:46:52,160
>> Ko darīt, ja katrs no studentiem
demonstrējumu

1153
00:46:52,160 --> 00:46:55,107
bija burtiski studentu structs ka
ir nosaukumi un māju un varbūt

1154
00:46:55,107 --> 00:46:57,065
tālruņu numurus un Twitter
rokturi un tamlīdzīgi.

1155
00:46:57,065 --> 00:46:59,564
Tātad visi lauki sākām
runājot par citu dienu,

1156
00:46:59,564 --> 00:47:02,410
daudz mazāk par lielu darījumu, kas
Mūsu mezglus iegūt vairāk interesantu

1157
00:47:02,410 --> 00:47:05,972
un liels tērēt, eh, papildu
rādītājs tikai lai savienotu tos kopā.

1158
00:47:05,972 --> 00:47:07,180
Bet tiešām, tas ir kompromiss.

1159
00:47:07,180 --> 00:47:09,560
Un tiešām, kods ir
sarežģītāka, jo jūs

1160
00:47:09,560 --> 00:47:11,770
skat nokrejojot cauri
ka konkrētais piemērs.

1161
00:47:11,770 --> 00:47:14,302
Bet ko tad, ja tur bija
daži Holy Grail šeit.

1162
00:47:14,302 --> 00:47:17,010
Ko darīt, ja neņemam soli
uz aizmuguri, bet masveida solis uz priekšu

1163
00:47:17,010 --> 00:47:19,180
un īstenot datu
struktūra, caur kuru mēs

1164
00:47:19,180 --> 00:47:22,870
var atrast elementus, piemēram, Jack vai
Christine vai kādi citi elementi

1165
00:47:22,870 --> 00:47:25,870
šajā masīva patiess konstantu laikā?

1166
00:47:25,870 --> 00:47:26,920
Meklēšana ir nemainīgs.

1167
00:47:26,920 --> 00:47:28,320
Dzēst ir nemainīgs.

1168
00:47:28,320 --> 00:47:29,570
Ieliktnis ir nemainīgs.

1169
00:47:29,570 --> 00:47:32,260
Visas šīs operācijas ir nemainīgi.

1170
00:47:32,260 --> 00:47:33,750
Tas būs mūsu svētais Grāls.

1171
00:47:33,750 --> 00:47:36,690
Un tas ir, ja mēs
uzņemt nākamreiz.

1172
00:47:36,690 --> 00:47:38,600
Tiekamies tad.

1173
00:47:38,600 --> 00:47:39,371