1
00:00:00,000 --> 00:00:11,860

2
00:00:11,860 --> 00:00:13,120
>> Högtalare 1: Okej, så vi är tillbaka.

3
00:00:13,120 --> 00:00:14,480
Välkommen till CS50.

4
00:00:14,480 --> 00:00:16,510
Detta är slutet på vecka sju.

5
00:00:16,510 --> 00:00:20,200
Så minns att förra gången började vi
titta på något mer sofistikerade

6
00:00:20,200 --> 00:00:21,100
datastrukturer.

7
00:00:21,100 --> 00:00:25,110
Sedan fram till nu, allt vi hade verkligen
till vårt förfogande var här, en matris.

8
00:00:25,110 --> 00:00:29,340
>> Men innan vi kasta arrayen som inte
så intressant, som det faktiskt

9
00:00:29,340 --> 00:00:33,570
egentligen är, vad är några av de
plussidan av denna enkla uppgifter

10
00:00:33,570 --> 00:00:34,560
struktur hittills?

11
00:00:34,560 --> 00:00:36,110
Vad är det bra på?

12
00:00:36,110 --> 00:00:39,450
Så vitt vi har sett?

13
00:00:39,450 --> 00:00:42,540
Vad har du?

14
00:00:42,540 --> 00:00:44,028
Ingenting.

15
00:00:44,028 --> 00:00:45,020
>> STUDENT: [OHÖRBAR].

16
00:00:45,020 --> 00:00:45,395
>> Högtalare 1: Vad är det?

17
00:00:45,395 --> 00:00:46,410
>> STUDENT: [OHÖRBAR].

18
00:00:46,410 --> 00:00:47,000
>> Högtalare 1: Fast storlek.

19
00:00:47,000 --> 00:00:51,260
OK, så varför är fast storlek bra ändå?

20
00:00:51,260 --> 00:00:53,180
>> STUDENT: [OHÖRBAR].

21
00:00:53,180 --> 00:00:56,240
>> Högtalare 1: OK, så det är effektivt i
den meningen att du kan tilldela ett

22
00:00:56,240 --> 00:01:00,070
fast belopp på utrymme, vilket förhoppningsvis
är precis lika mycket

23
00:01:00,070 --> 00:01:01,180
utrymme som du vill.

24
00:01:01,180 --> 00:01:02,720
Så det skulle vara absolut ett plus.

25
00:01:02,720 --> 00:01:06,530
>> Vad är en annan upp sidan av en matris?

26
00:01:06,530 --> 00:01:07,610
Yeah?

27
00:01:07,610 --> 00:01:08,750
>> STUDENT: [OHÖRBAR].

28
00:01:08,750 --> 00:01:09,550
>> Högtalare 1: Alla - förlåt?

29
00:01:09,550 --> 00:01:11,270
>> STUDENT: [OHÖRBAR].

30
00:01:11,270 --> 00:01:13,620
>> Högtalare 1: Alla rutorna i minnet
eller bredvid varandra.

31
00:01:13,620 --> 00:01:15,220
Och det är till någon hjälp - varför?

32
00:01:15,220 --> 00:01:15,970
Det är helt sant.

33
00:01:15,970 --> 00:01:18,611
Men hur kan vi utnyttja denna sanning?

34
00:01:18,611 --> 00:01:21,500
>> STUDENT: [OHÖRBAR].

35
00:01:21,500 --> 00:01:24,490
>> Högtalare 1: Exakt, kan vi hålla koll på
där allt är bara genom att veta

36
00:01:24,490 --> 00:01:28,560
en adress, nämligen adressen för
första byte i denna bit av minnet.

37
00:01:28,560 --> 00:01:30,420
Eller i fallet av strängen,
adressen för den första

38
00:01:30,420 --> 00:01:31,460
röding i den strängen.

39
00:01:31,460 --> 00:01:33,330
Och därifrån kan vi hitta
slutet av strängen.

40
00:01:33,330 --> 00:01:35,710
Vi hittar det andra elementet,
tredje element, och så vidare.

41
00:01:35,710 --> 00:01:38,740
>> Och så fint sätt att beskriva det
funktion är att matriser ger oss

42
00:01:38,740 --> 00:01:40,020
random access.

43
00:01:40,020 --> 00:01:44,330
Bara med hjälp av klammer
notation och ett nummer, kan du hoppa till

44
00:01:44,330 --> 00:01:48,070
ett specifikt element i arrayen
i konstant tid, big O

45
00:01:48,070 --> 00:01:49,810
av en, så att säga.

46
00:01:49,810 --> 00:01:51,080
>> Men det har varit några nackdelar.

47
00:01:51,080 --> 00:01:53,110
Vad en array inte mycket lätt?

48
00:01:53,110 --> 00:01:55,810

49
00:01:55,810 --> 00:01:57,170
Vad det är inte bra på?

50
00:01:57,170 --> 00:01:58,810
>> STUDENT: [OHÖRBAR].

51
00:01:58,810 --> 00:01:59,860
>> Högtalare 1: Vad är det?

52
00:01:59,860 --> 00:02:00,530
>> STUDENT: [OHÖRBAR].

53
00:02:00,530 --> 00:02:01,460
>> Högtalare 1: Utöka i storlek.

54
00:02:01,460 --> 00:02:04,800
Så baksidorna av arrayen är
precis motsatsen till vad

55
00:02:04,800 --> 00:02:05,540
upsides är.

56
00:02:05,540 --> 00:02:07,610
Så en av de avigsidor är
att det är en fast storlek.

57
00:02:07,610 --> 00:02:09,400
Så du kan inte riktigt odla den.

58
00:02:09,400 --> 00:02:13,510
Du kan omfördela en större bit av
minne, och sedan flytta de gamla elementen

59
00:02:13,510 --> 00:02:14,460
i den nya arrayen.

60
00:02:14,460 --> 00:02:18,060
Och sedan fri den gamla arrayen, för
exempel, genom att använda malloc eller en liknande

61
00:02:18,060 --> 00:02:21,180
Funktionen kallas realloc, vilket
omfördelar minne.

62
00:02:21,180 --> 00:02:25,490
>> Realloc, som åt sidan, försöker att ge dig
minne som är bredvid array

63
00:02:25,490 --> 00:02:26,610
att du redan har.

64
00:02:26,610 --> 00:02:28,740
Men det kan röra sig saker
runt helt och hållet.

65
00:02:28,740 --> 00:02:30,710
Men kort sagt, det är dyrt, eller hur?

66
00:02:30,710 --> 00:02:33,440
För om du har en bit av minnet av
denna storlek, men du vill verkligen en

67
00:02:33,440 --> 00:02:36,710
av denna storlek, och du vill bevara
de ursprungliga element, måste du

68
00:02:36,710 --> 00:02:40,510
ungefär en linjär tid kopieringen
som måste ske från

69
00:02:40,510 --> 00:02:41,900
gamla array till nya.

70
00:02:41,900 --> 00:02:44,630
Och verkligheten är att be operativsystemet
systemet igen och igen och

71
00:02:44,630 --> 00:02:48,340
igen för stora bitar av minnet kan börja
att kosta dig lite tid också.

72
00:02:48,340 --> 00:02:52,250
Så det är både en välsignelse och en förbannelse i
dölja det faktum att dessa matriser

73
00:02:52,250 --> 00:02:53,860
är av fast storlek.

74
00:02:53,860 --> 00:02:56,790
Men om vi inför i stället något
som denna, som vi kallade en länkad

75
00:02:56,790 --> 00:03:00,580
lista, får vi några upsides och
några nackdelar här också.

76
00:03:00,580 --> 00:03:05,780
>> Så en länkad lista är helt enkelt en data
struktur som består av C-structs i detta

77
00:03:05,780 --> 00:03:09,850
fall, där en struct, återkallelse, är bara
en behållare för en eller flera särskilda

78
00:03:09,850 --> 00:03:11,100
typer av variabler.

79
00:03:11,100 --> 00:03:16,110
I det här fallet, vad gör de datatyper
verkar vara inne i struct som

80
00:03:16,110 --> 00:03:17,600
förra gången vi ringde en nod?

81
00:03:17,600 --> 00:03:19,380
Var och en av dessa rektanglar är en nod.

82
00:03:19,380 --> 00:03:22,660
Och var och en av de mindre rektanglar
insidan av det är en datatyp.

83
00:03:22,660 --> 00:03:25,300
Vilka typer gjorde vi säger
de var på måndag?

84
00:03:25,300 --> 00:03:26,478
Yeah?

85
00:03:26,478 --> 00:03:27,870
>> STUDENT: [OHÖRBAR].

86
00:03:27,870 --> 00:03:30,721
>> SPEAKER 1: En variabel och en pekare, eller
mer specifikt, en int, för n,

87
00:03:30,721 --> 00:03:32,180
och en pekare på botten.

88
00:03:32,180 --> 00:03:35,360
Båda av dem råkar vara 32 bitar, på
åtminstone på en dator som denna CS50

89
00:03:35,360 --> 00:03:37,980
Appliance, och så de är
dras lika i storlek.

90
00:03:37,980 --> 00:03:42,260
>> Så vad använder pekaren
men för tydligen?

91
00:03:42,260 --> 00:03:47,690
Varför lägga till denna pil nu när arrayer var
så fin och ren och enkel?

92
00:03:47,690 --> 00:03:50,460
Vad pekaren gör för
oss i alla dessa noder?

93
00:03:50,460 --> 00:03:52,160
>> STUDENT: [OHÖRBAR].

94
00:03:52,160 --> 00:03:52,465
>> SPEAKER 1: Exakt.

95
00:03:52,465 --> 00:03:54,120
Det är att berätta om
nästa är.

96
00:03:54,120 --> 00:03:57,350
Så jag slags använder analogin av
med hjälp av en tråd att sortera på

97
00:03:57,350 --> 00:03:59,180
trär dessa noder tillsammans.

98
00:03:59,180 --> 00:04:01,760
Och det är precis vad vi gör med
pekare eftersom var och en av dessa

99
00:04:01,760 --> 00:04:06,360
bitar av minnet kan eller inte kan vara
sammanhängande, rygg mot rygg mot rygg

100
00:04:06,360 --> 00:04:09,500
insidan av RAM, eftersom varje gång du
ringa malloc säger, ge mig tillräckligt

101
00:04:09,500 --> 00:04:12,510
byte för en ny nod, kanske det
vara här eller det kan vara här.

102
00:04:12,510 --> 00:04:13,120
Det kan vara här.

103
00:04:13,120 --> 00:04:13,730
Det kan vara här.

104
00:04:13,730 --> 00:04:14,640
Du vet bara inte.

105
00:04:14,640 --> 00:04:17,880
>> Men att använda pekare i adresser
dessa noder, kan du sy dem

106
00:04:17,880 --> 00:04:22,370
tillsammans på ett sätt som ser visuellt
som en lista även om dessa saker är

107
00:04:22,370 --> 00:04:26,770
alla utspridda över din ena eller
dina två eller dina fyra gigabyte RAM-minne

108
00:04:26,770 --> 00:04:28,760
insidan av din egen dator.

109
00:04:28,760 --> 00:04:33,230
>> Så nedsidan, då, om
en länkad lista är vad?

110
00:04:33,230 --> 00:04:34,670
Vad är ett pris vi är
tydligen betalar?

111
00:04:34,670 --> 00:04:36,010
>> STUDENT: [OHÖRBAR].

112
00:04:36,010 --> 00:04:36,920
>> Högtalare 1: Mer utrymme, rätt?

113
00:04:36,920 --> 00:04:39,340
Vi har, i detta fall, fördubblades mängden
utrymme eftersom vi har gått

114
00:04:39,340 --> 00:04:43,500
från 32 bitar för varje nod, för varje
int, så nu 64 bitar för att vi måste

115
00:04:43,500 --> 00:04:45,050
hålla runt en pekare liksom.

116
00:04:45,050 --> 00:04:48,860
Du får mer effektivitet om din struct
är större än denna enkla sak.

117
00:04:48,860 --> 00:04:52,020
Om du har faktiskt en elev inne
av vilket är ett par strängar för

118
00:04:52,020 --> 00:04:55,430
namn och hus, kanske ett ID-nummer,
kanske några andra områden helt och hållet.

119
00:04:55,430 --> 00:04:59,000
>> Så om du har en tillräckligt stor struct,
då kanske kostnaden för pekaren är

120
00:04:59,000 --> 00:05:00,010
inte så stor roll.

121
00:05:00,010 --> 00:05:03,570
Detta är en bit av ett hörn fall, eftersom
vi lagrar sådan enkel primitiv

122
00:05:03,570 --> 00:05:04,760
insidan av den länkade listan.

123
00:05:04,760 --> 00:05:05,790
Men poängen är densamma.

124
00:05:05,790 --> 00:05:08,230
Du är definitivt spendera mer
minne, men du får

125
00:05:08,230 --> 00:05:08,990
flexibilitet.

126
00:05:08,990 --> 00:05:12,280
För nu om jag vill lägga till ett element
i början av denna lista,

127
00:05:12,280 --> 00:05:14,340
Jag måste allokera en ny nod.

128
00:05:14,340 --> 00:05:17,180
Och jag måste bara uppdatera dem
pilar på något sätt genom att bara flytta

129
00:05:17,180 --> 00:05:17,980
några tips runt.

130
00:05:17,980 --> 00:05:20,580
>> Om jag vill infoga något i
mitten av listan, behöver jag inte

131
00:05:20,580 --> 00:05:24,410
skjuta alla åt sidan som vi gjorde i
veckor tidigare med våra volontärer som

132
00:05:24,410 --> 00:05:25,700
representerade en matris.

133
00:05:25,700 --> 00:05:29,470
Jag kan bara tilldela en ny nod och
sedan bara peka på pilarna i

134
00:05:29,470 --> 00:05:32,290
olika riktningar eftersom den inte
måste förbli i själva

135
00:05:32,290 --> 00:05:35,670
minne en riktig linje som jag har ritat
det här på skärmen.

136
00:05:35,670 --> 00:05:38,400
>> Och sedan sist, om du vill infoga
något i slutet av listan, det är

137
00:05:38,400 --> 00:05:39,210
ännu enklare.

138
00:05:39,210 --> 00:05:43,320
Detta är en slags godtycklig notation,
men 34 pekare, ta en gissning.

139
00:05:43,320 --> 00:05:46,710
Vad är värdet av dess pekare mest
sannolikt dras ungefär som en gammal

140
00:05:46,710 --> 00:05:47,700
skola antenn där?

141
00:05:47,700 --> 00:05:48,920
>> STUDENT: [OHÖRBAR].

142
00:05:48,920 --> 00:05:49,900
>> Högtalare 1: Det är förmodligen noll.

143
00:05:49,900 --> 00:05:52,710
Och faktiskt det är en författares
representation av null.

144
00:05:52,710 --> 00:05:56,310
Och det är null eftersom du absolut
behöver veta var slutet på en länkad

145
00:05:56,310 --> 00:06:00,050
listan är, så att du håller efter och
följa och följa dessa pilar

146
00:06:00,050 --> 00:06:01,170
till vissa skräp värde.

147
00:06:01,170 --> 00:06:06,230
Så null kommer att innebära att det inte finns någon
fler noder till höger om numret 34,

148
00:06:06,230 --> 00:06:07,200
i det här fallet.

149
00:06:07,200 --> 00:06:10,270
>> Så vi föreslår att vi kan genomföra
denna nod i koden.

150
00:06:10,270 --> 00:06:12,130
Och vi har sett den här typen
av syntax innan.

151
00:06:12,130 --> 00:06:15,090
Typedef definierar bara en ny typ av
oss, ger oss en synonym som

152
00:06:15,090 --> 00:06:17,100
string var för char *.

153
00:06:17,100 --> 00:06:21,030
I det här fallet, det kommer att ge oss
stenografi notation så att struct node

154
00:06:21,030 --> 00:06:24,010
kan istället bara skrivas som
nod, som är mycket renare.

155
00:06:24,010 --> 00:06:25,360
Det är mycket mindre mångordig.

156
00:06:25,360 --> 00:06:30,080
>> Inuti en nod är tydligen en int
kallas n, och sedan en struct node *

157
00:06:30,080 --> 00:06:34,670
vilket betyder precis vad vi ville
pilarna för att betyda, en pekare till en annan

158
00:06:34,670 --> 00:06:36,940
nod av exakt samma datatyp.

159
00:06:36,940 --> 00:06:40,300
Och jag föreslår att vi skulle kunna genomföra en
sökfunktion som denna, som vid

160
00:06:40,300 --> 00:06:41,890
första anblicken kan tyckas
lite komplicerat.

161
00:06:41,890 --> 00:06:43,330
Men låt oss se det i sitt sammanhang.

162
00:06:43,330 --> 00:06:45,480
>> Låt mig gå över till apparaten här.

163
00:06:45,480 --> 00:06:48,460
Låt mig öppna en fil som heter
Listan noll prick timmar.

164
00:06:48,460 --> 00:06:53,950
Och som bara innehåller den definition vi
såg bara en stund sedan att dessa uppgifter

165
00:06:53,950 --> 00:06:55,390
typ som kallas en nod.

166
00:06:55,390 --> 00:06:57,350
Så vi har lagt in det i en punkt h-fil.

167
00:06:57,350 --> 00:07:01,430
>> Och som en parentes, även om detta
program som du är på väg att se är

168
00:07:01,430 --> 00:07:05,410
inte så komplicerat, det är sannerligen
konvent när du skriver ett program för att

169
00:07:05,410 --> 00:07:10,270
sätta saker som datatyper, att dra
konstanter ibland, insidan av dina

170
00:07:10,270 --> 00:07:13,210
header-fil och inte nödvändigtvis i
din C-fil, säkert när din

171
00:07:13,210 --> 00:07:17,370
program blir större och större, så att
du vet var du ska leta för både

172
00:07:17,370 --> 00:07:20,840
dokumentation i vissa fall, eller
för grunderna som detta, de

173
00:07:20,840 --> 00:07:22,360
definition av någon typ.

174
00:07:22,360 --> 00:07:25,680
>> Om jag öppnar nu upp listan noll prick
c, märker några saker.

175
00:07:25,680 --> 00:07:29,090
Den innehåller några header-filer, de flesta
som vi har sett tidigare.

176
00:07:29,090 --> 00:07:31,980
Den innehåller en egen header-fil.

177
00:07:31,980 --> 00:07:35,200
>> Och som en parentes, varför det är dubbelt
citat här, i motsats till den vinkel

178
00:07:35,200 --> 00:07:38,340
fästen på den linje som
Jag har markerat det?

179
00:07:38,340 --> 00:07:39,180
>> STUDENT: [OHÖRBAR].

180
00:07:39,180 --> 00:07:40,460
>> Högtalare 1: Ja, så det är en lokal fil.

181
00:07:40,460 --> 00:07:44,300
Så om det är en lokal fil på din egen här
på rad 15, till exempel, använder du

182
00:07:44,300 --> 00:07:46,570
de dubbla citattecken i stället
av de vinklade parentes.

183
00:07:46,570 --> 00:07:48,270
>> Nu är det här ganska intressant.

184
00:07:48,270 --> 00:07:51,830
Lägg märke till att jag har deklarerat en global
variabel i detta program på rad 18

185
00:07:51,830 --> 00:07:55,910
kallas första, är tanken att detta
kommer att vara en pekare till den första

186
00:07:55,910 --> 00:07:59,190
nod i min länkad lista, och jag har
initieras till null, eftersom jag har

187
00:07:59,190 --> 00:08:02,310
inte tilldelats någon faktisk
noder ännu.

188
00:08:02,310 --> 00:08:07,570
>> Så detta innebär, bildmässigt, vad vi
såg nyss på bilden som

189
00:08:07,570 --> 00:08:10,090
att pekaren på långt
vänster sida.

190
00:08:10,090 --> 00:08:12,260
Så just nu, att pekaren
har inte en pil.

191
00:08:12,260 --> 00:08:14,590
Det är istället bara null.

192
00:08:14,590 --> 00:08:17,880
Men det representerar vad som kommer att
adressen för den första egentliga

193
00:08:17,880 --> 00:08:19,480
nod i denna lista.

194
00:08:19,480 --> 00:08:22,120
Så jag har genomfört det är en global
eftersom, som ni ser, allt detta

195
00:08:22,120 --> 00:08:25,310
Programmet gör i livet är att genomföra
en länkad lista för mig.

196
00:08:25,310 --> 00:08:27,050
>> Nu har jag ett par prototyper här.

197
00:08:27,050 --> 00:08:31,190
Jag beslutade att implementera funktioner som
deletion, insertion, söka, och

198
00:08:31,190 --> 00:08:31,740
traversering -

199
00:08:31,740 --> 00:08:35,210
det sista bara vara promenad över
lista, skrivs ut dess beståndsdelar.

200
00:08:35,210 --> 00:08:36,750
Och nu här är min viktigaste rutin.

201
00:08:36,750 --> 00:08:39,890
Och vi kommer inte att spendera alltför mycket tid på
dessa eftersom det är typ av, förhoppningsvis

202
00:08:39,890 --> 00:08:41,780
förlegat nu.

203
00:08:41,780 --> 00:08:45,370
>> Jag kommer att göra följande,
medan användaren samverkar.

204
00:08:45,370 --> 00:08:47,300
Så en, jag ska skriva ut
ut denna meny.

205
00:08:47,300 --> 00:08:49,420
Och jag har formaterat den som
rent som jag kunde.

206
00:08:49,420 --> 00:08:52,240
Om användaren skriver i ett, som innebär
De vill ta bort något.

207
00:08:52,240 --> 00:08:54,560
Om användaren skriver i två, som innebär
de vill infoga något.

208
00:08:54,560 --> 00:08:55,930
Och så vidare.

209
00:08:55,930 --> 00:08:58,270
Jag ska sedan be
sedan för ett kommando.

210
00:08:58,270 --> 00:08:59,300
Och sen ska jag använda getInt.

211
00:08:59,300 --> 00:09:02,790
>> Så det här är en riktigt enkel menuing
gränssnitt där du bara behöver skriva

212
00:09:02,790 --> 00:09:05,270
ett nummer mappning till en
av dessa kommandon.

213
00:09:05,270 --> 00:09:08,730
Och nu har jag en fin ren switch
uttalande som kommer att slå på

214
00:09:08,730 --> 00:09:10,090
vad användaren skrivit i.

215
00:09:10,090 --> 00:09:12,180
Och om de skrivit något, jag
samtal bort och bryta.

216
00:09:12,180 --> 00:09:14,380
Om de skrivit två, jag
ringa in och bryta.

217
00:09:14,380 --> 00:09:16,490
>> Och nu märker jag har lagt varje
av dessa på samma linje.

218
00:09:16,490 --> 00:09:18,360
Detta är bara en stilistisk beslut.

219
00:09:18,360 --> 00:09:20,210
Normalt har vi sett något
såhär.

220
00:09:20,210 --> 00:09:23,260
Men jag bestämde mig bara, ärligt talat, mitt program
såg mer lättläst eftersom

221
00:09:23,260 --> 00:09:25,980
Det var bara fyra ärenden till
bara lista det så här.

222
00:09:25,980 --> 00:09:28,360
Helt legitim användning av stil.

223
00:09:28,360 --> 00:09:31,480
Och jag kommer att göra det så länge
Användaren har inte skrivit noll, vilket jag

224
00:09:31,480 --> 00:09:33,910
beslutat kommer att innebära att de vill sluta.

225
00:09:33,910 --> 00:09:36,630
>> Så nu märker vad jag
ska göra här.

226
00:09:36,630 --> 00:09:38,650
Jag ska befria listan tydligen.

227
00:09:38,650 --> 00:09:40,230
Men mer om det på bara ett ögonblick.

228
00:09:40,230 --> 00:09:41,640
Låt oss först köra programmet.

229
00:09:41,640 --> 00:09:45,250
Så låt mig göra en större terminal
fönster, dot slash lista 0.

230
00:09:45,250 --> 00:09:49,510
Jag ska gå vidare och sätter av
skriva två, ett antal som 50, och nu

231
00:09:49,510 --> 00:09:51,590
ser du listan är nu 50.

232
00:09:51,590 --> 00:09:53,380
Och min text rullas bara upp lite.

233
00:09:53,380 --> 00:09:55,940
Så nu märker listan innehåller
numret 50.

234
00:09:55,940 --> 00:09:58,220
>> Låt oss göra en insats genom att ta två.

235
00:09:58,220 --> 00:10:01,630
Låt oss skriva in numret som en.

236
00:10:01,630 --> 00:10:03,940
Lista är nu ett, följt av 50.

237
00:10:03,940 --> 00:10:06,020
Så det här är bara en textuell representation
i listan.

238
00:10:06,020 --> 00:10:10,550
Och låt oss sätta ett fler antal som
numret 42, vilket är förhoppningsvis

239
00:10:10,550 --> 00:10:14,620
kommer att hamna i mitten, eftersom
detta program särskilt sorterar det

240
00:10:14,620 --> 00:10:16,320
element som den sätter dem.

241
00:10:16,320 --> 00:10:17,220
Så där har vi det.

242
00:10:17,220 --> 00:10:20,730
Super enkelt program som kunde
absolut ha använt en array, men jag

243
00:10:20,730 --> 00:10:23,280
råkar använda en länkad lista
bara så jag kan dynamiskt

244
00:10:23,280 --> 00:10:24,610
växa och krympa den.

245
00:10:24,610 --> 00:10:28,470
>> Så låt oss ta en titt för sökning, om jag
köra kommandot tre, vill jag söka

246
00:10:28,470 --> 00:10:31,040
för, säg, antalet 43.

247
00:10:31,040 --> 00:10:34,190
Och ingenting var tydligen funnit,
eftersom jag fick tillbaka inget svar.

248
00:10:34,190 --> 00:10:35,010
Så låt oss göra det igen.

249
00:10:35,010 --> 00:10:35,690
Sök.

250
00:10:35,690 --> 00:10:39,520
Låt söka 50 eller snarare search
för 42, som har en fin

251
00:10:39,520 --> 00:10:40,850
lite subtil innebörd.

252
00:10:40,850 --> 00:10:42,610
Och jag hittade meningen med livet där.

253
00:10:42,610 --> 00:10:44,990
Nummer 42, om du inte vet
referens, googla det.

254
00:10:44,990 --> 00:10:45,350
Okej.

255
00:10:45,350 --> 00:10:47,130
Så vad har detta program gjort för mig?

256
00:10:47,130 --> 00:10:50,660
Det är bara tillät mig att infoga därmed
långt och sök efter element.

257
00:10:50,660 --> 00:10:53,650
>> Låt oss snabbspola framåt, då, att
som fungerar vi sneglade på

258
00:10:53,650 --> 00:10:55,360
på måndagen som en teaser.

259
00:10:55,360 --> 00:10:59,620
Så denna funktion, hävdar jag, söker efter
ett element i listan genom att först

260
00:10:59,620 --> 00:11:03,830
en, uppmanar användaren och sedan ringa
GetInt att få en verklig int

261
00:11:03,830 --> 00:11:05,060
som du vill söka efter.

262
00:11:05,060 --> 00:11:06,460
>> Sedan märker detta.

263
00:11:06,460 --> 00:11:10,690
Jag kommer att skapa en temporär variabel
i linje 188 kallas pekare -

264
00:11:10,690 --> 00:11:11,270
PTR -

265
00:11:11,270 --> 00:11:12,440
skulle ha kallat det något.

266
00:11:12,440 --> 00:11:16,140
Och det är en pekare till en nod
eftersom jag sa nod * där.

267
00:11:16,140 --> 00:11:19,900
Och jag initierade den vara lika med
först så att jag faktiskt har min

268
00:11:19,900 --> 00:11:22,860
finger, så att säga, på den mycket
första elementet i listan.

269
00:11:22,860 --> 00:11:27,460
Så om min högra hand här är PTR jag
pekar på samma sak som första

270
00:11:27,460 --> 00:11:28,670
pekar på.

271
00:11:28,670 --> 00:11:31,430
>> Så nu tillbaka i koden,
vad som händer härnäst -

272
00:11:31,430 --> 00:11:35,070
detta är ett vanligt paradigm när iteration
över en struktur som en

273
00:11:35,070 --> 00:11:35,970
länkad lista.

274
00:11:35,970 --> 00:11:40,410
Jag kommer att göra följande medan
pekaren inte är lika med noll Så medan

275
00:11:40,410 --> 00:11:47,530
mitt finger pekar inte på några null
värde, om Pilpekaren n är lika n.

276
00:11:47,530 --> 00:11:52,290
Vi kommer att märka först att n är vad
användaren har skrivit in per GetInts ringa hit.

277
00:11:52,290 --> 00:11:54,280
>> Och Pilpekaren n betyder vad?

278
00:11:54,280 --> 00:11:59,020
Tja, om vi går tillbaka till bilden här,
om jag har ett finger som pekar på

279
00:11:59,020 --> 00:12:02,960
att första noden innehållande nio, den
pil innebär i huvudsak gå till att

280
00:12:02,960 --> 00:12:08,860
nod och greppa värdet på plats n,
i detta fall kallas datafältet n.

281
00:12:08,860 --> 00:12:14,120
>> Inom parentes - och vi såg detta ett par
veckor sedan när någon frågade -

282
00:12:14,120 --> 00:12:18,840
denna syntax är nytt, men det gör det inte
ge oss krafter som vi

283
00:12:18,840 --> 00:12:20,040
inte redan har.

284
00:12:20,040 --> 00:12:25,325
Vad var denna fras motsvarar användning
dot notation och stjärnan ett par

285
00:12:25,325 --> 00:12:29,490
veckor sedan när vi skalade tillbaka
detta skikt lite för tidigt?

286
00:12:29,490 --> 00:12:31,780
>> STUDENT: [OHÖRBAR].

287
00:12:31,780 --> 00:12:38,880
>> Högtalare 1: Exakt, det var stjärna, och
då var det stjärnan dot n, med

288
00:12:38,880 --> 00:12:41,930
parentes här, som ser,
Uppriktigt sagt tror jag en hel del

289
00:12:41,930 --> 00:12:43,320
mer kryptiskt att läsa.

290
00:12:43,320 --> 00:12:46,270
Men stjärnan pekare, som alltid,
medel gå dit.

291
00:12:46,270 --> 00:12:49,090
Och när du är det, vilka uppgifter
område vill du komma?

292
00:12:49,090 --> 00:12:52,730
Jo du använda punktnotation att komma
en structs datafält, och jag

293
00:12:52,730 --> 00:12:54,140
specifikt vill n.

294
00:12:54,140 --> 00:12:56,240
>> Ärligt talat, skulle jag hävda detta
är bara svårare att läsa.

295
00:12:56,240 --> 00:12:58,080
Det är svårare att komma ihåg var
gör parenteserna går, den

296
00:12:58,080 --> 00:12:59,030
stjärna och allt detta.

297
00:12:59,030 --> 00:13:02,150
Så världen antog några syntaktiska
socker, så att säga.

298
00:13:02,150 --> 00:13:04,740
Bara ett sexigt sätt att säga,
Detta är likvärdigt, och

299
00:13:04,740 --> 00:13:05,970
kanske mer intuitiv.

300
00:13:05,970 --> 00:13:09,600
Om pekaren är verkligen en pekare, det
arrow notation medel gå dit och hitta

301
00:13:09,600 --> 00:13:11,890
fältet i det här fallet kallas n.

302
00:13:11,890 --> 00:13:13,660
>> Så om jag hittar det, märker vad jag gör.

303
00:13:13,660 --> 00:13:17,430
Jag kan helt enkelt skriva ut, hittade jag procent i,
koppla in värdet för den int.

304
00:13:17,430 --> 00:13:20,730
Jag kallar sova för en sekund att bara slag
av paus saker på skärmen för att

305
00:13:20,730 --> 00:13:22,900
ge användaren en sekund för att absorbera
vad som hände precis.

306
00:13:22,900 --> 00:13:24,290
Och då bryter jag.

307
00:13:24,290 --> 00:13:26,330
Annars, vad ska jag göra?

308
00:13:26,330 --> 00:13:30,960
Jag uppdaterar pekaren till lika
pekaren pilen bredvid.

309
00:13:30,960 --> 00:13:35,840
>> Så bara för att vara tydlig, innebär detta går
där, med min gamla skolan notation.

310
00:13:35,840 --> 00:13:39,580
Så detta betyder bara att gå till valfri
du pekar på, vilket i mycket

311
00:13:39,580 --> 00:13:43,660
första fallet är jag pekar på
struct med nio i det.

312
00:13:43,660 --> 00:13:44,510
Så jag har gått där.

313
00:13:44,510 --> 00:13:47,880
Och sedan punktnotation betyder,
får värdet på nästa.

314
00:13:47,880 --> 00:13:50,470
>> Men värdet, trots att det ritas
som en smal, är bara en siffra.

315
00:13:50,470 --> 00:13:51,720
Det är en numerisk adress.

316
00:13:51,720 --> 00:13:55,670
Så här en rad kod, oavsett om
skrivas så här, desto mer kryptiska

317
00:13:55,670 --> 00:14:00,190
sätt, eller som den här, den något mer
intuitivt sätt, betyder bara flytta min hand

318
00:14:00,190 --> 00:14:03,460
från den första noden till den nästa,
och sedan nästa, och sedan

319
00:14:03,460 --> 00:14:05,320
nästa, och så vidare.

320
00:14:05,320 --> 00:14:09,920
>> Så vi kommer inte att uppehålla mig vid den andra
implementationer av infoga och ta bort

321
00:14:09,920 --> 00:14:14,030
och traversering, de två första av
som är ganska involverad.

322
00:14:14,030 --> 00:14:17,010
Och jag tycker det är ganska lätt att få
förlorad när man gör det muntligt.

323
00:14:17,010 --> 00:14:19,890
Men vad vi kan göra här är
försöka avgöra hur

324
00:14:19,890 --> 00:14:21,640
bäst att göra detta visuellt.

325
00:14:21,640 --> 00:14:24,800
Eftersom jag skulle föreslå att om vi
vill infoga element i detta

326
00:14:24,800 --> 00:14:26,680
befintlig lista, vilket
har fem element -

327
00:14:26,680 --> 00:14:29,530
9, 17, 22, 26, och 33 -

328
00:14:29,530 --> 00:14:33,300
Om jag skulle genomföra detta i
kod, måste jag överväga hur man ska gå

329
00:14:33,300 --> 00:14:34,160
om att göra detta.

330
00:14:34,160 --> 00:14:37,720
>> Och jag skulle föreslå att ta baby steg
varvid, i det här fallet menar jag, vad är

331
00:14:37,720 --> 00:14:41,090
de möjliga scenarier som vi
kan stöta på i allmänhet?

332
00:14:41,090 --> 00:14:44,120
Vid genomförandet av insatsen för en länkad
listan, händer detta bara vara en

333
00:14:44,120 --> 00:14:46,090
specifikt exempel på storlek fem.

334
00:14:46,090 --> 00:14:50,420
Tja om du vill infoga ett nummer,
vilja säga nummer ett, och

335
00:14:50,420 --> 00:14:53,380
upprätthålla sorterad ordning, där
uppenbarligen gör nummer ett måste

336
00:14:53,380 --> 00:14:55,686
gå i detta specifika exempel?

337
00:14:55,686 --> 00:14:56,840
Liksom i början.

338
00:14:56,840 --> 00:15:00,030
>> Men vad som är intressant det är att
Om du vill infoga en i detta

339
00:15:00,030 --> 00:15:04,100
lista, vad som behöver speciell pekare
ska uppdateras tydligen?

340
00:15:04,100 --> 00:15:04,610
First.

341
00:15:04,610 --> 00:15:07,830
Så jag skulle säga, detta är det första fallet
att vi kanske vill överväga en

342
00:15:07,830 --> 00:15:11,140
scenario med insättning på
början av listan.

343
00:15:11,140 --> 00:15:15,400
>> Låt oss plocka ut kanske en så enkel eller ens
lättare fall, relativt sett.

344
00:15:15,400 --> 00:15:18,110
Anta att jag vill infoga
nummer 35 i sorterad ordning.

345
00:15:18,110 --> 00:15:20,600
Det tillhör naturligtvis borta.

346
00:15:20,600 --> 00:15:25,320
Så vad pekaren uppenbarligen kommer att
måste uppdateras i det scenariot?

347
00:15:25,320 --> 00:15:30,060
34 pekare blir inte null
men adressen till struct

348
00:15:30,060 --> 00:15:31,800
innehåller numret 35.

349
00:15:31,800 --> 00:15:32,750
Så det är fallet två.

350
00:15:32,750 --> 00:15:36,190
Så redan, jag slags kvantisera
hur mycket arbete jag har att göra här.

351
00:15:36,190 --> 00:15:39,880
>> Och slutligen, är det uppenbart mellersta fallet
faktiskt, i mitten, om jag vill

352
00:15:39,880 --> 00:15:45,870
infoga något som säger 23, som går
mellan 23 och 26, men

353
00:15:45,870 --> 00:15:48,680
Nu börjar det bli lite mer
inblandade eftersom det

354
00:15:48,680 --> 00:15:52,800
pekare behöver ändras?

355
00:15:52,800 --> 00:15:56,680
Så 22 måste givetvis ändras
eftersom han inte kan peka på 26 längre.

356
00:15:56,680 --> 00:16:00,320
Han behöver peka på den nya noden som
Jag måste fördela genom att ringa

357
00:16:00,320 --> 00:16:01,770
malloc eller något motsvarande.

358
00:16:01,770 --> 00:16:05,990
>> Men då behöver jag också att nya noden, 23
i detta fall, för att ha dess pekare

359
00:16:05,990 --> 00:16:07,870
pekar på vem?

360
00:16:07,870 --> 00:16:08,560
26.

361
00:16:08,560 --> 00:16:10,380
Och det kommer att bli en
ordning av verksamheten här.

362
00:16:10,380 --> 00:16:13,410
För om jag gör det dumt, och jag
till exempel start i början av

363
00:16:13,410 --> 00:16:16,040
listan, och mitt mål är att sätta 23.

364
00:16:16,040 --> 00:16:18,610
Och jag kolla, det hör
Här, nära nio?

365
00:16:18,610 --> 00:16:18,950
Nej.

366
00:16:18,950 --> 00:16:20,670
Tillhör det här, bredvid 17?

367
00:16:20,670 --> 00:16:20,940
Nej.

368
00:16:20,940 --> 00:16:22,530
Har det hör hemma här intill 22?

369
00:16:22,530 --> 00:16:23,300
Ja.

370
00:16:23,300 --> 00:16:26,400
>> Nu om jag är dum här, och inte
tänka igenom detta, kan jag

371
00:16:26,400 --> 00:16:28,320
fördela min nya noden för 23.

372
00:16:28,320 --> 00:16:32,080
Jag kanske uppdaterar pekaren från
noden kallas 22, pekar

373
00:16:32,080 --> 00:16:33,080
det på den nya noden.

374
00:16:33,080 --> 00:16:36,140
Och vad har jag att uppdatera
den nya nodens pekare att vara?

375
00:16:36,140 --> 00:16:38,120
>> STUDENT: [OHÖRBAR].

376
00:16:38,120 --> 00:16:38,385
>> SPEAKER 1: Exakt.

377
00:16:38,385 --> 00:16:39,710
Pekar på 26.

378
00:16:39,710 --> 00:16:45,590
Men dammit om jag inte redan uppdatera
22: s pekare att peka på den här killen, och

379
00:16:45,590 --> 00:16:48,260
nu har jag föräldralösa, resten
av listan, så att säga.

380
00:16:48,260 --> 00:16:52,140
Så räkneordningen här
kommer att vara viktigt.

381
00:16:52,140 --> 00:16:55,100
>> För att göra detta kunde jag stjäla,
säga, sex frivilliga.

382
00:16:55,100 --> 00:16:57,650
Och låt oss se om vi inte kan göra detta
visuellt i stället för kod-wise.

383
00:16:57,650 --> 00:16:59,330
Och vi har några härliga stressen
bollar för dig idag.

384
00:16:59,330 --> 00:17:02,510
OK, vad sägs om en, två, i
back - på slutet där.

385
00:17:02,510 --> 00:17:04,530
tre, fyra, ni båda
killar på slutet.

386
00:17:04,530 --> 00:17:05,579
Och fem, sex.

387
00:17:05,579 --> 00:17:05,839
Visst.

388
00:17:05,839 --> 00:17:06,450
Fem och sex.

389
00:17:06,450 --> 00:17:08,390
Okej, och vi kommer
till er nästa gång.

390
00:17:08,390 --> 00:17:09,640
Okej, kom upp.

391
00:17:09,640 --> 00:17:12,010

392
00:17:12,010 --> 00:17:14,819
>> Okej, eftersom du är här uppe först,
skulle du vilja vara ett olyckligt

393
00:17:14,819 --> 00:17:16,119
i Google Glass här?

394
00:17:16,119 --> 00:17:19,075
Okej, så, OK, glas,
spela in en video.

395
00:17:19,075 --> 00:17:22,720

396
00:17:22,720 --> 00:17:24,589
OK, du är bra att gå.

397
00:17:24,589 --> 00:17:27,950
>> Okej, så om ni kan komma över
Här har jag förberett i förväg

398
00:17:27,950 --> 00:17:30,110
några siffror.

399
00:17:30,110 --> 00:17:31,240
Okej, kom hit.

400
00:17:31,240 --> 00:17:33,440
Och varför inte du gå lite
vidare på det sättet.

401
00:17:33,440 --> 00:17:35,520
Och låt oss se, vad heter du,
med Google Glass?

402
00:17:35,520 --> 00:17:35,910
>> STUDENT: Ben.

403
00:17:35,910 --> 00:17:36,230
>> Högtalare 1: Ben?

404
00:17:36,230 --> 00:17:38,380
OK, Ben, kommer du att vara först, bokstavligen.

405
00:17:38,380 --> 00:17:40,580
Så vi kommer att skicka dig
till slutet av scenen.

406
00:17:40,580 --> 00:17:41,670
Okej, och ditt namn?

407
00:17:41,670 --> 00:17:41,990
>> STUDENT: Jason.

408
00:17:41,990 --> 00:17:44,530
>> Högtalare 1: Jason, OK kommer du
vara nummer nio.

409
00:17:44,530 --> 00:17:46,700
Så om du vill följa Ben på det sättet.

410
00:17:46,700 --> 00:17:47,010
>> STUDENT: Jill.

411
00:17:47,010 --> 00:17:49,630
>> Högtalare 1: Jill, du kommer att bli
17, som om jag hade gjort detta mer

412
00:17:49,630 --> 00:17:51,260
intelligent, skulle jag ha
började vid den andra änden.

413
00:17:51,260 --> 00:17:52,370
Du går den vägen.

414
00:17:52,370 --> 00:17:53,030
22.

415
00:17:53,030 --> 00:17:53,670
Och du är?

416
00:17:53,670 --> 00:17:53,980
>> STUDENT: Mary.

417
00:17:53,980 --> 00:17:56,130
>> Högtalare 1: Mary, du ska vara 22.

418
00:17:56,130 --> 00:17:58,420
Och ditt namn är?

419
00:17:58,420 --> 00:17:58,810
>> STUDENT: Chris.

420
00:17:58,810 --> 00:18:00,100
>> Högtalare 1: Chris, du ska vara 26.

421
00:18:00,100 --> 00:18:00,740
Och sedan sist.

422
00:18:00,740 --> 00:18:01,400
>> STUDENT: Diana.

423
00:18:01,400 --> 00:18:02,670
>> Högtalare 1: Diana, du ska vara 34.

424
00:18:02,670 --> 00:18:03,920
Så du kommer på hit.

425
00:18:03,920 --> 00:18:06,360
>> Okej, så perfekt sorteras
beställa redan.

426
00:18:06,360 --> 00:18:09,600
Och låt oss gå vidare och göra detta
så att vi verkligen kan -

427
00:18:09,600 --> 00:18:11,720
Ben är du bara typ av ser
ut i ingenstans där.

428
00:18:11,720 --> 00:18:15,670
OK, så låt oss gå vidare och skildra detta
med vapen, ungefär som jag var, exakt,

429
00:18:15,670 --> 00:18:16,250
vad som händer.

430
00:18:16,250 --> 00:18:19,540
Så gå vidare och ge er själva en
fot eller två mellan er.

431
00:18:19,540 --> 00:18:22,900
Och gå vidare och pekar med ena handen
vem du ska peka på

432
00:18:22,900 --> 00:18:23,470
baserat på detta.

433
00:18:23,470 --> 00:18:25,890
Och om du är null bara peka
rakt ner till golvet.

434
00:18:25,890 --> 00:18:27,690
OK, så bra.

435
00:18:27,690 --> 00:18:32,290
>> Så nu har vi en länkad lista, och låt mig
föreslår att jag ska spela rollen av

436
00:18:32,290 --> 00:18:35,110
PTR, så jag kommer inte att bry sig
bär detta runt.

437
00:18:35,110 --> 00:18:37,830
Och då - någon dum konvent -
du kan kalla detta något du vill -

438
00:18:37,830 --> 00:18:39,800
föregångare pekare, pred pekare -

439
00:18:39,800 --> 00:18:43,930
det är bara smeknamnet vi gav i
vår exempelkod på min vänstra hand.

440
00:18:43,930 --> 00:18:47,240
Den andra handen som kommer att hålla
reda på vem som är vem i

441
00:18:47,240 --> 00:18:48,400
Följande scenarier.

442
00:18:48,400 --> 00:18:52,390
>> Så antar, först, jag vill plocka bort
att första exemplet att infoga, säg

443
00:18:52,390 --> 00:18:54,330
20, in i listan.

444
00:18:54,330 --> 00:18:57,160
Så jag kommer att behöva någon att
förkroppsligar nummer 20 för oss.

445
00:18:57,160 --> 00:18:58,950
Så jag behöver malloc någon
från publiken.

446
00:18:58,950 --> 00:18:59,380
Kom upp.

447
00:18:59,380 --> 00:19:00,340
Vad är ditt namn?

448
00:19:00,340 --> 00:19:01,300
>> STUDENT: Brian.

449
00:19:01,300 --> 00:19:05,270
>> Högtalare 1: Brian, okej, så du
skall vara den nod som innehåller 20.

450
00:19:05,270 --> 00:19:06,810
Okej, kom hit.

451
00:19:06,810 --> 00:19:10,025
Och självklart, där
hör Brian?

452
00:19:10,025 --> 00:19:12,190
Så, mitt i - faktiskt,
vänta en minut.

453
00:19:12,190 --> 00:19:13,420
Vi gör detta i ordning.

454
00:19:13,420 --> 00:19:17,170
Vi gör detta mycket svårare
än den behöver vara i början.

455
00:19:17,170 --> 00:19:21,210
OK, vi ska fria Brian
och realloc Brian som fem.

456
00:19:21,210 --> 00:19:23,680
>> OK, så nu vill vi infoga
Brian som fem.

457
00:19:23,680 --> 00:19:25,960
Så kom hit intill
Ben för bara ett ögonblick.

458
00:19:25,960 --> 00:19:28,250
Och du kan antagligen berätta
där denna historia går.

459
00:19:28,250 --> 00:19:30,500
Men låt oss tänka igenom
ordningen på verksamheten.

460
00:19:30,500 --> 00:19:32,880
Och det är just denna visuella
som kommer att rada upp

461
00:19:32,880 --> 00:19:34,080
med provkoden.

462
00:19:34,080 --> 00:19:40,120
Så här har jag PTR pekar inledningsvis
inte på Ben, per se, men oavsett på vilken

463
00:19:40,120 --> 00:19:43,245
värdesätter han innehåller, som i detta fall
är - vad heter du nu igen?

464
00:19:43,245 --> 00:19:43,670
>> STUDENT: Jason.

465
00:19:43,670 --> 00:19:47,350
>> Högtalare 1: Jason, så både Ben och jag är
pekar på Jason i denna stund.

466
00:19:47,350 --> 00:19:49,700
Så nu måste jag bestämma,
där hör Brian?

467
00:19:49,700 --> 00:19:53,500
Så det enda jag har tillgång till
just nu är hans n dataelement.

468
00:19:53,500 --> 00:19:58,280
Så jag ska kolla, är
Brian mindre än Jason?

469
00:19:58,280 --> 00:19:59,770
Svaret är sant.

470
00:19:59,770 --> 00:20:03,680
>> Så vad måste nu ske,
i rätt ordning?

471
00:20:03,680 --> 00:20:07,120
Jag behöver uppdatera hur många pekare
totalt i den här historien?

472
00:20:07,120 --> 00:20:10,720
Om min hand är fortfarande pekar på
Jason och din hand - om du vill

473
00:20:10,720 --> 00:20:12,930
sätta handen som, liksom, jag
vet inte, ett frågetecken.

474
00:20:12,930 --> 00:20:14,070
OK, bra.

475
00:20:14,070 --> 00:20:15,670
>> Okej, så du har
några kandidater.

476
00:20:15,670 --> 00:20:20,500
Antingen Ben eller jag eller Brian eller Jason
eller alla andra, vilket

477
00:20:20,500 --> 00:20:21,370
pekare behöver ändra?

478
00:20:21,370 --> 00:20:23,260
Hur många totalt?

479
00:20:23,260 --> 00:20:24,080
>> OK, så två.

480
00:20:24,080 --> 00:20:27,090
Min pekaren spelar egentligen ingen roll längre
eftersom jag är bara tillfällig.

481
00:20:27,090 --> 00:20:31,370
Så det är dessa två killar, förmodligen,
både Ben och Brian.

482
00:20:31,370 --> 00:20:34,410
Så låt mig föreslå att vi uppdaterar
Ben, eftersom han är först.

483
00:20:34,410 --> 00:20:36,350
Den första delen av denna lista
kommer nu att bli Brian.

484
00:20:36,350 --> 00:20:38,070
Så Ben pekar på Brian.

485
00:20:38,070 --> 00:20:39,320
OK, nu vad?

486
00:20:39,320 --> 00:20:41,950

487
00:20:41,950 --> 00:20:43,460
>> Vem blir pekade på vem?

488
00:20:43,460 --> 00:20:44,710
>> STUDENT: [OHÖRBAR].

489
00:20:44,710 --> 00:20:46,180
>> Högtalare 1: OK så Brian har
att peka på Jason.

490
00:20:46,180 --> 00:20:48,360
Men jag har tappat bort den pekare?

491
00:20:48,360 --> 00:20:49,980
Vet jag var Jason är?

492
00:20:49,980 --> 00:20:50,790
>> STUDENT: [OHÖRBAR].

493
00:20:50,790 --> 00:20:52,620
>> Högtalare 1: jag gör, eftersom jag är
den temporära pekaren.

494
00:20:52,620 --> 00:20:55,110
Och förmodligen har jag inte ändrat
att peka på den nya noden.

495
00:20:55,110 --> 00:20:58,300
Så vi kan bara ha Brian punkt
på vem jag pekar på.

496
00:20:58,300 --> 00:20:59,000
Och vi är klara.

497
00:20:59,000 --> 00:21:01,890
Så fall en, insättning på
början av listan.

498
00:21:01,890 --> 00:21:02,950
Det fanns två viktiga steg.

499
00:21:02,950 --> 00:21:06,750
Ett måste vi uppdatera Ben, och sedan
Vi har också att uppdatera Brian.

500
00:21:06,750 --> 00:21:09,230
Och då jag inte behöver bry
traipsing genom resten av

501
00:21:09,230 --> 00:21:12,680
listan, eftersom vi redan hittat hans
plats, eftersom han tillhörde den

502
00:21:12,680 --> 00:21:14,080
kvar av det första elementet.

503
00:21:14,080 --> 00:21:15,400
>> Okej, så ganska enkelt.

504
00:21:15,400 --> 00:21:18,110
I själva verket känns som om vi är nästan
vilket gör detta alltför komplicerat.

505
00:21:18,110 --> 00:21:20,240
Så låt oss nu plocka ut slutet
av listan, och se var

506
00:21:20,240 --> 00:21:21,380
komplexiteten startar.

507
00:21:21,380 --> 00:21:24,560
Så om nu, alloc jag från publiken.

508
00:21:24,560 --> 00:21:25,540
Någon som vill spela 55?

509
00:21:25,540 --> 00:21:26,700
Okej, jag såg din hand först.

510
00:21:26,700 --> 00:21:29,620
Kom upp.

511
00:21:29,620 --> 00:21:30,030
Yeah.

512
00:21:30,030 --> 00:21:31,177
Vad är ditt namn?

513
00:21:31,177 --> 00:21:32,310
>> STUDENT: [OHÖRBAR].

514
00:21:32,310 --> 00:21:33,240
>> SPEAKER 1: Habata.

515
00:21:33,240 --> 00:21:33,890
OK, kom upp.

516
00:21:33,890 --> 00:21:35,730
Du kommer att vara nummer 55.

517
00:21:35,730 --> 00:21:37,820
Så du, naturligtvis, tillhör
i slutet av listan.

518
00:21:37,820 --> 00:21:41,850
Så låt oss spela om simuleringen med mig
vara PTR för bara ett ögonblick.

519
00:21:41,850 --> 00:21:44,050
Så jag först kommer att peka på
vad Ben pekar på.

520
00:21:44,050 --> 00:21:45,900
Vi är båda pekar nu på Brian.

521
00:21:45,900 --> 00:21:48,420
Så 55 är inte mindre än fem.

522
00:21:48,420 --> 00:21:52,510
Så jag kommer att uppdatera mig själv genom
pekar på Brians nästa pekare, som

523
00:21:52,510 --> 00:21:54,450
Nu är förstås Jason.

524
00:21:54,450 --> 00:21:57,310
55 är inte mindre än nio, så
Jag kommer att uppdatera PTR.

525
00:21:57,310 --> 00:21:58,890
Jag kommer att uppdatera PTR.

526
00:21:58,890 --> 00:22:02,290
Jag kommer att uppdatera PTR
Jag kommer att uppdatera PTR.

527
00:22:02,290 --> 00:22:05,060
Och jag ska - hmm, vad är
ditt namn igen?

528
00:22:05,060 --> 00:22:05,560
>> STUDENT: Diana.

529
00:22:05,560 --> 00:22:09,190
>> SPEAKER 1: Diana pekar, naturligtvis,
på noll med sin vänstra hand.

530
00:22:09,190 --> 00:22:13,030
Så var Habata faktiskt
tillhör tydligt?

531
00:22:13,030 --> 00:22:15,050
Till vänster här.

532
00:22:15,050 --> 00:22:19,460
Så hur vet jag att sätta henne här
Jag tror att jag har skruvat upp.

533
00:22:19,460 --> 00:22:22,420
För vad är PTR konst
denna tidpunkt?

534
00:22:22,420 --> 00:22:23,240
Null.

535
00:22:23,240 --> 00:22:25,580
Så även om, visuellt, kan vi
naturligtvis se alla dessa

536
00:22:25,580 --> 00:22:26,610
killarna här på scenen.

537
00:22:26,610 --> 00:22:29,680
Jag har inte hållit koll på de tidigare
person i listan.

538
00:22:29,680 --> 00:22:33,210
Jag har inte ett finger pekar ut,
i detta fall, det nodnummer 34.

539
00:22:33,210 --> 00:22:34,760
>> Så låt oss faktiskt börja över.

540
00:22:34,760 --> 00:22:37,560
Så nu har jag egentligen inte behöver
en andra lokal variabel.

541
00:22:37,560 --> 00:22:40,980
Och detta är vad du ser i
aktuella provet C-kod, där som jag går,

542
00:22:40,980 --> 00:22:45,860
när jag uppdaterar min högra hand för att peka
Jason, vilket lämnar Brian bakom, jag

543
00:22:45,860 --> 00:22:51,440
bättre börja använda min vänstra hand till
uppdatera där jag var, så att när jag går

544
00:22:51,440 --> 00:22:52,700
igenom den här listan -

545
00:22:52,700 --> 00:22:55,040
mer tafatt än jag tänkt
nu här visuellt -

546
00:22:55,040 --> 00:22:56,740
Jag kommer att komma till
slutet av listan.

547
00:22:56,740 --> 00:23:00,020
>> Denna handen är fortfarande noll, vilket är ganska
värdelös, annat än för att indikera

548
00:23:00,020 --> 00:23:02,980
Jag är helt klart i slutet av listan,
men nu åtminstone jag har detta

549
00:23:02,980 --> 00:23:08,270
föregångare pekaren pekar här, så
nu vad händer och vad pekare behöver

550
00:23:08,270 --> 00:23:10,150
ska uppdateras?

551
00:23:10,150 --> 00:23:13,214
Vars hand vill du ha
att konfigurera om först?

552
00:23:13,214 --> 00:23:15,190
>> STUDENT: [OHÖRBAR].

553
00:23:15,190 --> 00:23:16,220
>> Högtalare 1: OK, så Dianas.

554
00:23:16,220 --> 00:23:21,110
Vart vill du peka
Dianas vänstra pekaren på?

555
00:23:21,110 --> 00:23:23,620
Vid 55, förmodligen, så att
Vi har satt dit.

556
00:23:23,620 --> 00:23:25,560
Och där ska 55 pekare gå?

557
00:23:25,560 --> 00:23:27,000
Ner, representerande null.

558
00:23:27,000 --> 00:23:28,890
Och mina händer, på denna punkt, inte
roll eftersom de var bara

559
00:23:28,890 --> 00:23:30,070
temporära variabler.

560
00:23:30,070 --> 00:23:31,030
Så nu vi är klara.

561
00:23:31,030 --> 00:23:34,650
>> Så den extra komplexitet där - och
det är inte så svårt att genomföra,

562
00:23:34,650 --> 00:23:38,660
men vi behöver en sekundär variabel att göra
Se till att innan jag flyttar min rätt

563
00:23:38,660 --> 00:23:42,140
handen, uppdaterar jag värdet av min vänstra
handen, pred pekaren i det här fallet, så

564
00:23:42,140 --> 00:23:45,860
att jag har en släpande pekare
att hålla reda på var jag var.

565
00:23:45,860 --> 00:23:49,360
Nu som en åt sidan, om du tänker här
igenom, känns det som om det är en

566
00:23:49,360 --> 00:23:51,490
lite irriterande att behöva hålla
koll på denna vänster hand.

567
00:23:51,490 --> 00:23:54,015
>> Vad skulle en annan lösning
på detta problem har varit?

568
00:23:54,015 --> 00:23:56,500
Om du fick göra om data
struktur vi pratar

569
00:23:56,500 --> 00:23:59,630
igenom just nu?

570
00:23:59,630 --> 00:24:02,690
Om detta bara typ av känns lite
irriterande att ha, liksom, två pekare

571
00:24:02,690 --> 00:24:08,430
gå igenom listan, kunde vem
ha, i en perfekt värld, underhålls

572
00:24:08,430 --> 00:24:10,160
information som vi behöver?

573
00:24:10,160 --> 00:24:11,360
Yeah?

574
00:24:11,360 --> 00:24:12,610
>> STUDENT: [OHÖRBAR].

575
00:24:12,610 --> 00:24:15,160

576
00:24:15,160 --> 00:24:16,150
>> SPEAKER 1: Exakt.

577
00:24:16,150 --> 00:24:19,130
Rätt så finns det faktiskt en intressant
fröet till en idé.

578
00:24:19,130 --> 00:24:22,470
Och denna idé om en tidigare pekare,
pekar på föregående element.

579
00:24:22,470 --> 00:24:25,580
Vad händer om jag förkroppsligade just det
insidan av själva listan?

580
00:24:25,580 --> 00:24:27,810
Och det kommer att vara svårt att visualisera
detta utan alla papper

581
00:24:27,810 --> 00:24:28,830
faller till golvet.

582
00:24:28,830 --> 00:24:31,860
Men antar att killarna använde både
av sina händer för att få en tidigare

583
00:24:31,860 --> 00:24:35,950
pekare, och en nästa pekare, därigenom
genomföra vad vi kallar ett dubbelt

584
00:24:35,950 --> 00:24:36,830
länkad lista.

585
00:24:36,830 --> 00:24:41,090
Som skulle tillåta mig att sortera i bakåt,
mycket lättare utan mig, det

586
00:24:41,090 --> 00:24:43,800
programmerare, behöva hålla
spåra manuellt -

587
00:24:43,800 --> 00:24:44,980
verkligen manuellt -

588
00:24:44,980 --> 00:24:47,280
där jag hade tidigare
i listan.

589
00:24:47,280 --> 00:24:48,110
Så vi kommer inte att göra det.

590
00:24:48,110 --> 00:24:50,950
Vi ska hålla det enkelt eftersom det är
kommer att komma till ett pris, dubbelt så

591
00:24:50,950 --> 00:24:53,450
mycket utrymme för pekare,
Om du vill ha en andra.

592
00:24:53,450 --> 00:24:55,760
Men det är verkligen en gemensam
datastruktur känd som en

593
00:24:55,760 --> 00:24:57,410
dubbellänkad lista.

594
00:24:57,410 --> 00:25:01,310
>> Låt oss göra det sista exemplet här och sätta
dessa killar ur deras elände.

595
00:25:01,310 --> 00:25:03,270
Så malloc 20.

596
00:25:03,270 --> 00:25:05,320
Kom upp från gången där.

597
00:25:05,320 --> 00:25:06,280
Okej, vad heter du?

598
00:25:06,280 --> 00:25:07,440
>> STUDENT: [OHÖRBAR].

599
00:25:07,440 --> 00:25:07,855
>> Högtalare 1: Förlåt?

600
00:25:07,855 --> 00:25:08,480
>> STUDENT: [OHÖRBAR].

601
00:25:08,480 --> 00:25:09,410
>> Högtalare 1: Demeron?

602
00:25:09,410 --> 00:25:10,230
OK Kom upp.

603
00:25:10,230 --> 00:25:11,910
Du ska vara 20.

604
00:25:11,910 --> 00:25:14,720
Du uppenbarligen kommer att
hör mellan 17 och 22.

605
00:25:14,720 --> 00:25:16,150
Så låt mig lära min läxa.

606
00:25:16,150 --> 00:25:18,150
Jag ska börja pekare
pekar på Brian.

607
00:25:18,150 --> 00:25:21,190
Och jag kommer att ha min vänstra hand
bara uppdatera till Brian som jag flyttar till

608
00:25:21,190 --> 00:25:23,600
Jason, kontroll gör 20 mindre än nio?

609
00:25:23,600 --> 00:25:24,060
Nej.

610
00:25:24,060 --> 00:25:25,430
Är 20 mindre än 17?

611
00:25:25,430 --> 00:25:25,880
Nej.

612
00:25:25,880 --> 00:25:27,450
Är 20 mindre än 22?

613
00:25:27,450 --> 00:25:28,440
Ja.

614
00:25:28,440 --> 00:25:34,070
Så vad pekare eller händer behöver ändra
där de pekar nu?

615
00:25:34,070 --> 00:25:37,070
>> Så vi kan göra 17 pekar på 20.

616
00:25:37,070 --> 00:25:37,860
Så det är bra.

617
00:25:37,860 --> 00:25:40,080
Var vill vi peka
pekaren nu?

618
00:25:40,080 --> 00:25:41,330
Vid 22.

619
00:25:41,330 --> 00:25:45,410
Och vi vet var 22 är, återigen tack
till min tillfälliga pekare.

620
00:25:45,410 --> 00:25:46,760
Så vi är OK där.

621
00:25:46,760 --> 00:25:49,440
Så på grund av detta tillfälliga lagring
Jag har hållit koll på var alla är.

622
00:25:49,440 --> 00:25:55,055
Och nu kan du visuellt gå in där
du hör hemma, och nu behöver vi 1, 2, 3,

623
00:25:55,055 --> 00:25:58,410
4, 5, 6, 7, 8, 9 stress bollar,
och en applåd för

624
00:25:58,410 --> 00:25:59,770
dessa killar, om vi kunde.

625
00:25:59,770 --> 00:26:00,410
Snyggt gjort.

626
00:26:00,410 --> 00:26:05,320
>> [Applåder]

627
00:26:05,320 --> 00:26:06,330
>> Högtalare 1: Okej.

628
00:26:06,330 --> 00:26:09,860
Och du kan hålla bitarna
av papper som souvenirer.

629
00:26:09,860 --> 00:26:15,930
>> Okej, så, tro mig det är en hel del
lättare att gå igenom det med

630
00:26:15,930 --> 00:26:17,680
människor än vad det är med själva koden.

631
00:26:17,680 --> 00:26:22,690
Men vad du hittar på bara ett ögonblick
Nu är det samma - Åh, tack.

632
00:26:22,690 --> 00:26:23,630
Tack -

633
00:26:23,630 --> 00:26:29,360
är att du kommer att upptäcka att samma data
struktur, en länkad lista, kan faktiskt

634
00:26:29,360 --> 00:26:33,200
användas som en byggsten för att ännu mer
avancerade datastrukturer.

635
00:26:33,200 --> 00:26:37,620
>> Och inser också temat här är att
Vi har helt infört mer

636
00:26:37,620 --> 00:26:40,060
komplexiteten i genomförandet
av denna algoritm.

637
00:26:40,060 --> 00:26:43,940
Insättning, och om vi gick igenom det,
radering och sökning, är en liten

638
00:26:43,940 --> 00:26:46,660
mer komplicerat än det
var med en array.

639
00:26:46,660 --> 00:26:48,040
Men vi få en viss dynamik.

640
00:26:48,040 --> 00:26:50,180
Vi får en adaptiv datastruktur.

641
00:26:50,180 --> 00:26:54,010
>> Men återigen, vi betalar ett pris för att ha några
ytterligare komplexitet, både i

642
00:26:54,010 --> 00:26:54,910
genomföra det.

643
00:26:54,910 --> 00:26:56,750
Och vi gett upp random access.

644
00:26:56,750 --> 00:27:00,450
Och för att vara ärlig, det finns inte några trevliga
ren bild jag kan ge dig det

645
00:27:00,450 --> 00:27:03,120
säger här är varför en länkad lista
är bättre än en array.

646
00:27:03,120 --> 00:27:04,100
Och stannar vid detta.

647
00:27:04,100 --> 00:27:07,520
Eftersom temat upprepas nu, även
mer så under de kommande veckorna, är

648
00:27:07,520 --> 00:27:10,200
att det inte nödvändigtvis
ett korrekt svar.

649
00:27:10,200 --> 00:27:13,830
>> Det är därför vi har den separat axel
av design för problemsamlingar.

650
00:27:13,830 --> 00:27:17,700
Det kommer att bli mycket sammanhangsberoende
om du vill använda dessa data

651
00:27:17,700 --> 00:27:21,750
struktur eller att en, och det kommer
beror på vad som är viktigt för dig när det gäller

652
00:27:21,750 --> 00:27:24,620
av resurser och komplexitet.

653
00:27:24,620 --> 00:27:28,830
>> Men låt mig föreslå att den ideala uppgifter
struktur, den heliga graal, skulle vara

654
00:27:28,830 --> 00:27:32,200
något som är konstant tid,
oavsett hur mycket grejer är

655
00:27:32,200 --> 00:27:36,940
inuti det, skulle det inte vara fantastiskt om en
datastruktur gav svar i

656
00:27:36,940 --> 00:27:37,920
konstant tid.

657
00:27:37,920 --> 00:27:38,330
Ja.

658
00:27:38,330 --> 00:27:40,110
Detta ord är i din enorma ordboken.

659
00:27:40,110 --> 00:27:41,550
Eller nej, är detta ord inte.

660
00:27:41,550 --> 00:27:43,270
Eller något sådant problem där.

661
00:27:43,270 --> 00:27:46,360
Nå, låt oss se om vi kan inte minst
ta ett steg mot det.

662
00:27:46,360 --> 00:27:50,190
>> Låt mig föreslå en ny datastruktur som
kan användas för olika saker,

663
00:27:50,190 --> 00:27:52,260
i detta fall kallas en hash-tabell.

664
00:27:52,260 --> 00:27:55,590
Och så är vi faktiskt tillbaka till ögna
på en matris, i det här fallet, och

665
00:27:55,590 --> 00:28:00,550
något godtyckligt, har jag dragit detta
hash tabell som en array med en slags

666
00:28:00,550 --> 00:28:02,810
tvådimensionell array -

667
00:28:02,810 --> 00:28:05,410
eller snarare det skildras här som en två
dimensionell array - men detta är bara

668
00:28:05,410 --> 00:28:10,770
en matris med storlek 26, så att om vi
ring arrayen tabellen, bordsfäste

669
00:28:10,770 --> 00:28:12,440
noll är den rektangel på toppen.

670
00:28:12,440 --> 00:28:15,090
Bordsfäste 25 är rektangeln
längst ned.

671
00:28:15,090 --> 00:28:18,620
Och detta är hur jag skulle rita en data
struktur där jag vill lagra

672
00:28:18,620 --> 00:28:19,790
folks namn.

673
00:28:19,790 --> 00:28:24,370
>> Så till exempel, och jag kommer inte att dra
hela saken här på overhead, om jag

674
00:28:24,370 --> 00:28:29,160
hade denna matris, som jag nu kommer att
ringa en hashtabell, och detta är återigen

675
00:28:29,160 --> 00:28:31,360
läge noll.

676
00:28:31,360 --> 00:28:34,840
Detta är här plats
en, och så vidare.

677
00:28:34,840 --> 00:28:37,880
Jag hävdar att jag vill använda dessa data
struktur, för diskussionens skull,

678
00:28:37,880 --> 00:28:42,600
att lagra människors namn, Alice och Bob
och Charlie och andra sådana namn.

679
00:28:42,600 --> 00:28:46,110
Så tänk på det nu som början
av, säg, en ordbok

680
00:28:46,110 --> 00:28:47,520
med massor av ord.

681
00:28:47,520 --> 00:28:49,435
De råkar vara namn
i vårt exempel här.

682
00:28:49,435 --> 00:28:52,560
Och allt detta är alltför förbunden, kanske, att
genomföra en stavningskontroll, som vi

683
00:28:52,560 --> 00:28:54,400
kanske för problem som sex.

684
00:28:54,400 --> 00:28:59,300
>> Så om vi har en rad total storlek 26
så att det är den 25: e plats

685
00:28:59,300 --> 00:29:03,390
längst ner, och jag hävdar att Alice är
det första ordet i ordlistan för

686
00:29:03,390 --> 00:29:07,260
namn som jag vill infoga i RAM,
i denna datastruktur, där finns

687
00:29:07,260 --> 00:29:12,480
instinkter som talar om att Alices
namn bör gå i denna samling?

688
00:29:12,480 --> 00:29:13,510
>> Vi har 26 alternativ.

689
00:29:13,510 --> 00:29:14,990
Om vi ​​vill sätta henne?

690
00:29:14,990 --> 00:29:16,200
Vi vill ha henne i fästet noll, eller hur?

691
00:29:16,200 --> 00:29:18,280
A för Alice, låt oss kalla det noll.

692
00:29:18,280 --> 00:29:20,110
And B kommer att vara ett, och C kommer att vara två.

693
00:29:20,110 --> 00:29:22,600
Så vi kommer att skriva
Alices namn här uppe.

694
00:29:22,600 --> 00:29:24,890
Om vi ​​sätter då Bob, hans
Namnet kommer att gå här.

695
00:29:24,890 --> 00:29:27,280
Charlie kommer att gå här.

696
00:29:27,280 --> 00:29:30,500
Och så vidare ner genom
denna datastruktur.

697
00:29:30,500 --> 00:29:32,090
>> Detta är en underbar datastruktur.

698
00:29:32,090 --> 00:29:32,730
Varför?

699
00:29:32,730 --> 00:29:37,460
Nå vad är gångtiden
sätter en människas namn i detta

700
00:29:37,460 --> 00:29:39,850
datastruktur just nu?

701
00:29:39,850 --> 00:29:43,702
Med tanke på att denna tabell är implementerad,
verkligen, som en matris.

702
00:29:43,702 --> 00:29:44,940
Jo det är konstant tid.

703
00:29:44,940 --> 00:29:45,800
Det är av storleksordningen en.

704
00:29:45,800 --> 00:29:46,360
Varför?

705
00:29:46,360 --> 00:29:48,630
>> Nå hur kan du avgöra
där Alice tillhör?

706
00:29:48,630 --> 00:29:51,000
Du tittar på vilken bokstaven i hennes namn?

707
00:29:51,000 --> 00:29:51,490
Den första.

708
00:29:51,490 --> 00:29:54,350
Och du kan få det, om det är en sträng,
genom att bara titta på snöre

709
00:29:54,350 --> 00:29:55,200
konsol noll.

710
00:29:55,200 --> 00:29:57,110
Så den nollte tecknet i strängen.

711
00:29:57,110 --> 00:29:57,610
Det är enkelt.

712
00:29:57,610 --> 00:30:00,350
Vi gjorde det i krypto
Uppdraget veckor sedan.

713
00:30:00,350 --> 00:30:05,310
Och sedan när du vet att Alices
brev är kapitalet A, kan vi subtrahera

714
00:30:05,310 --> 00:30:08,160
rabatt 65 eller kapitalet A självt,
som ger oss noll.

715
00:30:08,160 --> 00:30:10,940
Så vi vet nu att Alice tillhör
vid stället noll.

716
00:30:10,940 --> 00:30:14,240
>> Och med tanke på en pekare till dessa data
struktur, av något slag, hur lång tid tar

717
00:30:14,240 --> 00:30:18,840
det tar mig att hitta plats
noll i en array?

718
00:30:18,840 --> 00:30:22,080
Bara ett steg, höger Det är konstant tid
grund av direktåtkomsten vi

719
00:30:22,080 --> 00:30:23,780
Förslaget var en del av en matris.

720
00:30:23,780 --> 00:30:28,570
Så kort sagt, räkna ut vad indexet
av Alice heter, vilket är i

721
00:30:28,570 --> 00:30:32,610
detta fall är A, eller låt oss bara lösa
att till noll, där B är en och C är

722
00:30:32,610 --> 00:30:34,900
två, räkna ut det
är konstant tid.

723
00:30:34,900 --> 00:30:38,510
Jag måste bara titta på hennes första brev,
räkna ut var noll är en

724
00:30:38,510 --> 00:30:40,460
array är också konstant tid.

725
00:30:40,460 --> 00:30:42,140
Så tekniskt det är
som två steg nu.

726
00:30:42,140 --> 00:30:43,330
Men det är fortfarande konstant.

727
00:30:43,330 --> 00:30:46,880
Så vi kallar den stora O i en, så vi har
insatt Alice in denna tabell i

728
00:30:46,880 --> 00:30:48,440
konstant tid.

729
00:30:48,440 --> 00:30:50,960
>> Men självklart, jag är
naiva här, eller hur?

730
00:30:50,960 --> 00:30:53,240
Tänk om det finns en Aaron i klassen?

731
00:30:53,240 --> 00:30:53,990
Eller Alicia?

732
00:30:53,990 --> 00:30:57,230
Eller några andra namn som börjar med
A. Där ska vi sätta

733
00:30:57,230 --> 00:31:00,800
den personen, eller hur?

734
00:31:00,800 --> 00:31:03,420
Jag menar, just nu finns det bara tre
människor på bordet, så kanske vi

735
00:31:03,420 --> 00:31:07,490
bör sätta Aaron på plats
noll ett två tre.

736
00:31:07,490 --> 00:31:09,480
>> Höger, kunde jag sätta en hit.

737
00:31:09,480 --> 00:31:13,350
Men sedan, om vi försöker att sätta David in
denna lista, inte där David går?

738
00:31:13,350 --> 00:31:15,170
Nu vårt system börjar bryta
nedåt, höger?

739
00:31:15,170 --> 00:31:19,210
Eftersom nu David hamnar här
om Aaron är faktiskt här.

740
00:31:19,210 --> 00:31:23,060
Och så nu detta hela idén med att ha en
ren datastruktur som ger oss

741
00:31:23,060 --> 00:31:28,010
konstant tid infogningar är inte längre
konstant tid, eftersom jag måste

742
00:31:28,010 --> 00:31:31,240
kolla, åh, damnit, är någon som redan
på Alice plats.

743
00:31:31,240 --> 00:31:35,320
>> Låt mig undersöka resten av dessa data
struktur, letar efter en plats att sätta

744
00:31:35,320 --> 00:31:37,130
någon som Arons namn.

745
00:31:37,130 --> 00:31:39,390
Och så att alltför börjar
ta linjär tid.

746
00:31:39,390 --> 00:31:42,710
Dessutom, om du nu vill hitta
Aaron i denna datastruktur, och du

747
00:31:42,710 --> 00:31:45,430
kontrollera, och Arons namn är inte här.

748
00:31:45,430 --> 00:31:47,960
Helst skulle du bara säga Arons
inte i datastrukturen.

749
00:31:47,960 --> 00:31:51,530
Men om du börjar göra plats för
Aaron där det borde ha varit en D

750
00:31:51,530 --> 00:31:55,600
eller E, dig, värsta fall, måste kolla
hela datastruktur, i

751
00:31:55,600 --> 00:31:59,480
vilket fall det överlåter till något
linjär i storleken på bordet.

752
00:31:59,480 --> 00:32:00,920
>> Så okej, jag ska fixa det här.

753
00:32:00,920 --> 00:32:04,200
Problemet här är att jag hade
26 element i arrayen.

754
00:32:04,200 --> 00:32:05,000
Låt mig ändra det.

755
00:32:05,000 --> 00:32:06,010
Hoppsan.

756
00:32:06,010 --> 00:32:10,600
Låt mig ändra det så att snarare vara av
storlek 26 totalt, märker botten

757
00:32:10,600 --> 00:32:12,720
Indexet kommer att förändras till n minus 1.

758
00:32:12,720 --> 00:32:16,610
Om 26 är alldeles för litet för människor "
namn, eftersom det finns tusentals

759
00:32:16,610 --> 00:32:20,830
namnen i världen, låt oss bara göra
i 100 eller 1000 eller 10.000.

760
00:32:20,830 --> 00:32:22,960
Låt oss bara anslå mycket mer utrymme.

761
00:32:22,960 --> 00:32:27,230
>> Tja det inte nödvändigtvis minskar
sannolikheten för att vi inte kommer att ha två

762
00:32:27,230 --> 00:32:31,510
personer med namn som börjar med A, och
så, skulle du försöka att sätta ett

763
00:32:31,510 --> 00:32:33,120
Namnen på plats noll fortfarande.

764
00:32:33,120 --> 00:32:36,850
De kommer fortfarande att kollidera, vilket
innebär att vi fortfarande behöver en lösning för att sätta

765
00:32:36,850 --> 00:32:41,020
Alice och Aron och Alicia och andra
namn som börjar med A annanstans.

766
00:32:41,020 --> 00:32:43,460
Men hur mycket av ett problem är det här?

767
00:32:43,460 --> 00:32:46,870
Vad är sannolikheten att du
har kollisioner i en data

768
00:32:46,870 --> 00:32:48,240
struktur som denna?

769
00:32:48,240 --> 00:32:52,570
>> Nåväl, låt mig - vi kommer tillbaka
på den frågan här.

770
00:32:52,570 --> 00:32:55,530
Och titta på hur vi kan
lösa det först.

771
00:32:55,530 --> 00:32:58,480
Låt mig dra upp detta förslag här.

772
00:32:58,480 --> 00:33:02,020
Vad vi just beskrivit är en algoritm,
en heuristisk kallas linjär

773
00:33:02,020 --> 00:33:05,030
sondering där, om du försökte sätta
något här i dessa data

774
00:33:05,030 --> 00:33:08,920
struktur, som kallas en hash-tabell,
och det finns inget utrymme där du

775
00:33:08,920 --> 00:33:12,000
verkligen sondera datastruktur
kontroll, är det tillgängligt?

776
00:33:12,000 --> 00:33:13,430
Är detta Finns detta tillgängligt?

777
00:33:13,430 --> 00:33:13,980
Finns detta tillgängligt?

778
00:33:13,980 --> 00:33:17,550
Och när det äntligen är, sätter du
namn som du tänkt

779
00:33:17,550 --> 00:33:19,370
håll på den platsen.

780
00:33:19,370 --> 00:33:23,360
Men i värsta fall, den enda fläcken
kan vara mycket botten av data

781
00:33:23,360 --> 00:33:25,090
struktur, alldeles i slutet av arrayen.

782
00:33:25,090 --> 00:33:30,130
>> Så linjär sondering, i värsta fall,
ankommer till en linjär algoritm där

783
00:33:30,130 --> 00:33:34,500
Aaron, om han råkar införas senast
i denna datastruktur, kan han

784
00:33:34,500 --> 00:33:39,540
kolliderar med detta första läge, men
sedan avsluta med otur på slutet.

785
00:33:39,540 --> 00:33:43,940
Så detta är inte en konstant
tid heliga graal för oss.

786
00:33:43,940 --> 00:33:47,650
Denna metod att infoga element i
en datastruktur som kallas en hash

787
00:33:47,650 --> 00:33:52,050
Tabellen verkar inte vara konstant tid
åtminstone inte i det allmänna fallet.

788
00:33:52,050 --> 00:33:54,000
Det kan överlåta till något linjär.

789
00:33:54,000 --> 00:33:56,970
>> Så vad händer om vi löser kollisioner
något annorlunda?

790
00:33:56,970 --> 00:34:00,740
Så här är en mer sofistikerad
inställning till vad är fortfarande

791
00:34:00,740 --> 00:34:02,800
kallas en hash-tabell.

792
00:34:02,800 --> 00:34:05,890
Och genom hash, som en parentes, vad
Jag menar är det index som

793
00:34:05,890 --> 00:34:07,070
Jag hänvisade till tidigare.

794
00:34:07,070 --> 00:34:09,810
Till hash något kan vara
tänkt som ett verb.

795
00:34:09,810 --> 00:34:13,690
>> Så om du hash Alice är ett namn,
en hashfunktion, så att säga,

796
00:34:13,690 --> 00:34:14,710
ska returnera ett tal.

797
00:34:14,710 --> 00:34:18,199
I detta fall är noll om hon hör hemma
Platsen noll, en, om hon hör hemma

798
00:34:18,199 --> 00:34:20,000
plats ett, och så vidare.

799
00:34:20,000 --> 00:34:24,360
Så min hashfunktion hittills varit
super enkelt, bara att titta på

800
00:34:24,360 --> 00:34:26,159
första bokstaven i någons namn.

801
00:34:26,159 --> 00:34:29,090
Men en hashfunktion tar så
ingång viss bit data, en

802
00:34:29,090 --> 00:34:30,210
sträng, en int, oavsett.

803
00:34:30,210 --> 00:34:32,239
Och det spottar ut vanligtvis ett nummer.

804
00:34:32,239 --> 00:34:35,739
Och den siffran är där att data
elementet hör hemma i en datastruktur

805
00:34:35,739 --> 00:34:37,800
känd här som en hash-tabell.

806
00:34:37,800 --> 00:34:41,400
>> Så bara intuitivt, är detta en
något annorlunda sammanhang.

807
00:34:41,400 --> 00:34:44,170
Detta är faktiskt hänvisar till ett exempel
involverar födelsedagar, där

808
00:34:44,170 --> 00:34:46,850
det kan finnas så många som
31 dagar i månaden.

809
00:34:46,850 --> 00:34:52,239
Men vad gjorde denna person beslutar att
göra i händelse av en kollision?

810
00:34:52,239 --> 00:34:55,304
Sammanhang är nu, inte en kollision mellan
namn, men en kollision på födelsedagar,

811
00:34:55,304 --> 00:35:00,760
Om två personer har samma födelsedag på
den 2 oktober till exempel.

812
00:35:00,760 --> 00:35:02,120
>> STUDENT: [OHÖRBAR].

813
00:35:02,120 --> 00:35:05,010
>> Högtalare 1: Ja, så här har vi
den hävstångseffekt av länkade listor.

814
00:35:05,010 --> 00:35:07,830
Så det ser lite annorlunda
än vi drog den tidigare.

815
00:35:07,830 --> 00:35:10,790
Men vi tycks behöva en array
på vänster sida.

816
00:35:10,790 --> 00:35:13,230
Det är ett index, för ingen
särskilda skäl.

817
00:35:13,230 --> 00:35:14,630
Men det är fortfarande en array.

818
00:35:14,630 --> 00:35:16,160
Det är en samling av pekare.

819
00:35:16,160 --> 00:35:20,670
Och var och en av dessa delar, var och en av
dessa cirklar eller snedstreck - ett snedstreck

820
00:35:20,670 --> 00:35:23,970
representerar null - alla dessa
pekare uppenbarligen pekar på

821
00:35:23,970 --> 00:35:25,730
vilken datastruktur?

822
00:35:25,730 --> 00:35:26,890
En länkad lista.

823
00:35:26,890 --> 00:35:30,530
>> Så nu har vi möjlighet att
hårt kod i vårt program

824
00:35:30,530 --> 00:35:32,010
storleken på tabellen.

825
00:35:32,010 --> 00:35:35,360
I det här fallet, vet vi att det finns aldrig
mer än 31 dagar i en månad.

826
00:35:35,360 --> 00:35:38,480
Så hårt kodning ett värde som 31 är
rimliga i detta sammanhang.

827
00:35:38,480 --> 00:35:42,700
I samband med namn, hård kodning
26 är inte orimligt det folks

828
00:35:42,700 --> 00:35:46,340
Namnen börjar bara med, till exempel,
alfabetet involverar A till Z.

829
00:35:46,340 --> 00:35:50,180
>> Vi kan klämma dem alla i dessa data
struktur så länge, när vi får en

830
00:35:50,180 --> 00:35:55,330
kollision, sätter vi inte namnen här,
vi tänker i stället för dessa celler

831
00:35:55,330 --> 00:36:00,270
inte som strängar själva, men som
pekare till, till exempel, Alice.

832
00:36:00,270 --> 00:36:03,660
Och så Alice kan ha en annan pekare
till ett annat namn som börjar med

833
00:36:03,660 --> 00:36:06,150
A. Och Bob går faktiskt över hit.

834
00:36:06,150 --> 00:36:10,850
>> Och om det finns ett annat namn som börjar
med B, hamnar han hit.

835
00:36:10,850 --> 00:36:15,070
Och så var och en av de delar av detta
bord två, om vi utformat detta en

836
00:36:15,070 --> 00:36:17,350
lite mer skickligt -

837
00:36:17,350 --> 00:36:18,125
kom igen -

838
00:36:18,125 --> 00:36:22,950
Om vi ​​utformat detta lite mer
skickligt, blir nu en adaptiv uppgifter

839
00:36:22,950 --> 00:36:27,720
struktur, där det finns ingen hård gräns
på hur många element som du kan infoga

840
00:36:27,720 --> 00:36:30,700
in i det, för om du inte har
en kollision, det är bra.

841
00:36:30,700 --> 00:36:34,690
Bara gå vidare och lägga det till
vad vi såg lite sedan var

842
00:36:34,690 --> 00:36:38,290
känd som en länkad lista.

843
00:36:38,290 --> 00:36:39,690
>> Nåväl låt oss stanna upp ett ögonblick.

844
00:36:39,690 --> 00:36:42,570
Vad är sannolikheten för en kollision
i första hand?

845
00:36:42,570 --> 00:36:45,480
Höger, kanske jag över tänker, kanske
Jag är över Engineering Denna problemet,

846
00:36:45,480 --> 00:36:46,370
eftersom du vet vad?

847
00:36:46,370 --> 00:36:49,070
Ja, kan jag komma med godtyckliga
Exempel från toppen av mitt huvud som

848
00:36:49,070 --> 00:36:52,870
Allison och Aron, men i verkligheten,
ges en likformig fördelning av

849
00:36:52,870 --> 00:36:56,990
ingångar, som är en del slumpmässiga insättningar
i en datastruktur, vad som verkligen är

850
00:36:56,990 --> 00:36:58,580
sannolikheten för en kollision?

851
00:36:58,580 --> 00:37:01,670
Väl visar sig, det är faktiskt
super hög.

852
00:37:01,670 --> 00:37:03,850
Låt mig generalisera detta
Problemet är som denna.

853
00:37:03,850 --> 00:37:08,890
>> Så i ett rum n CS50 studenter, vad är
sannolikheten för att åtminstone

854
00:37:08,890 --> 00:37:11,010
två studenter i rummet
har samma födelsedag?

855
00:37:11,010 --> 00:37:13,346
Så det är vad. några hund -

856
00:37:13,346 --> 00:37:16,790
200, 300 människor här och flera
hundra personer hemma idag.

857
00:37:16,790 --> 00:37:20,670
Så om du ville fråga oss vad som är
sannolikheten för två personer

858
00:37:20,670 --> 00:37:23,930
i det här rummet som har samma födelsedag,
vi kan lista ut.

859
00:37:23,930 --> 00:37:26,250
Och jag hävdar faktiskt det finns två
människor med samma födelsedag.

860
00:37:26,250 --> 00:37:29,560
>> Till exempel, är det någon
har födelsedag idag?

861
00:37:29,560 --> 00:37:31,340
Igår?

862
00:37:31,340 --> 00:37:32,590
I morgon?

863
00:37:32,590 --> 00:37:35,980
Okej, så det känns som jag ska
att behöva göra detta 363 eller så mer

864
00:37:35,980 --> 00:37:39,500
gånger för att faktiskt räkna ut
om vi har en kollision.

865
00:37:39,500 --> 00:37:42,350
Eller så kan vi bara göra det matematiskt
snarare än tediously

866
00:37:42,350 --> 00:37:43,200
göra detta.

867
00:37:43,200 --> 00:37:44,500
Och föreslår följande.

868
00:37:44,500 --> 00:37:48,740
>> Så jag föreslår att vi kunde modellera
sannolikheten av två personer som har

869
00:37:48,740 --> 00:37:55,320
samma födelsedag som sannolikheten för ett
minus sannolikheten för ingen har

870
00:37:55,320 --> 00:37:56,290
samma födelsedag.

871
00:37:56,290 --> 00:37:59,960
Så för att få den här, och detta är bara
finare sätt att skriva detta, för

872
00:37:59,960 --> 00:38:03,090
första personen i rummet, han eller hon
kan ha vilken som helst av den möjliga

873
00:38:03,090 --> 00:38:07,370
födelsedagar antar 365 dagar i året,
med ursäkter till personer med

874
00:38:07,370 --> 00:38:08,760
i februari 29: e födelsedag.

875
00:38:08,760 --> 00:38:13,470
>> Så den första personen i det här rummet är gratis
att ha valfritt antal födelsedagar

876
00:38:13,470 --> 00:38:18,280
av de 365 möjligheter så att
vi kommer att göra det 365 delat med 365,

877
00:38:18,280 --> 00:38:18,990
vilket är ett.

878
00:38:18,990 --> 00:38:22,700
Nästa person i rummet, om målet
är att undvika en kollision, kan endast

879
00:38:22,700 --> 00:38:26,460
har hans eller hennes födelsedag på hur
många olika möjliga dagar?

880
00:38:26,460 --> 00:38:27,610
364.

881
00:38:27,610 --> 00:38:31,430
Så den andra termen i detta uttryck är
huvudsak gör att matte för oss

882
00:38:31,430 --> 00:38:33,460
genom att subtrahera bort en möjlig dag.

883
00:38:33,460 --> 00:38:36,390
Och sedan nästa dag, nästa dag, den
nästa dag ner till det totala antalet

884
00:38:36,390 --> 00:38:38,100
av människor i rummet.

885
00:38:38,100 --> 00:38:41,290
>> Och om vi då överväga, vad är då
sannolikheten inte att alla har

886
00:38:41,290 --> 00:38:45,265
unika födelsedagar, men återigen ett minus
som, vad vi får är ett uttryck

887
00:38:45,265 --> 00:38:47,810
som kan mycket fancifully
se ut så här.

888
00:38:47,810 --> 00:38:50,330
Men det är mer intressant
att titta på visuellt.

889
00:38:50,330 --> 00:38:55,120
Detta är ett diagram där på x-axeln är
antalet personer i rummet, det

890
00:38:55,120 --> 00:38:56,180
antal födelsedagar.

891
00:38:56,180 --> 00:38:59,840
På y-axeln är sannolikheten
av en kollision, två personer

892
00:38:59,840 --> 00:39:01,230
har samma födelsedag.

893
00:39:01,230 --> 00:39:05,020
>> Och takeaway från denna kurva är
att så fort du kommer att gilla 40

894
00:39:05,020 --> 00:39:11,110
studenter, är du på en 90% sannolikhet
combinatorically av två

895
00:39:11,110 --> 00:39:13,550
personer eller fler har
samma födelsedag.

896
00:39:13,550 --> 00:39:18,600
Och när du kommer att gilla 58 personer är det
nästan 100% av en slump de två

897
00:39:18,600 --> 00:39:21,310
personer i rummet kommer att ha
samma födelsedag, även om det finns

898
00:39:21,310 --> 00:39:26,650
365 eller 366 möjliga hinkar, och
endast 58 personer i rummet.

899
00:39:26,650 --> 00:39:29,900
Bara statistiskt är det sannolikt att
få kollisioner, vilket i korthet

900
00:39:29,900 --> 00:39:31,810
motiverar denna diskussion.

901
00:39:31,810 --> 00:39:35,890
Att även om vi får fint här, och
börjar med dessa kedjor, är vi fortfarande

902
00:39:35,890 --> 00:39:36,950
kommer att ha kollisioner.

903
00:39:36,950 --> 00:39:42,710
>> Så det väcker frågan, vad är det
kostnaden för att göra insättningar och deletioner

904
00:39:42,710 --> 00:39:44,850
i en datastruktur som denna?

905
00:39:44,850 --> 00:39:46,630
Nå, låt mig föreslå -

906
00:39:46,630 --> 00:39:51,570
och låt mig gå tillbaka till skärmen över
här - om vi har n element i

907
00:39:51,570 --> 00:39:56,330
listan, så om vi försöker att infoga
n element, och vi har

908
00:39:56,330 --> 00:39:58,050
Hur många hinkar?

909
00:39:58,050 --> 00:40:03,450
Låt oss säga totalt 31 skopor
i fallet med födelsedagar.

910
00:40:03,450 --> 00:40:09,240
Vad är den maximala längden på en
av dessa kedjor potentiellt?

911
00:40:09,240 --> 00:40:12,670
>> Om igen det finns 31 möjliga
födelsedagar i en viss månad.

912
00:40:12,670 --> 00:40:14,580
Och vi bara klampa alla -

913
00:40:14,580 --> 00:40:15,580
faktiskt det är en dum exempel.

914
00:40:15,580 --> 00:40:16,960
Låt oss göra 26 istället.

915
00:40:16,960 --> 00:40:20,890
Så om faktiskt har personer vars namn
börja med A till Z, och därmed ge

916
00:40:20,890 --> 00:40:22,780
us 26 möjligheter.

917
00:40:22,780 --> 00:40:25,920
Och vi använder en datastruktur som
den vi just såg, där vi har

918
00:40:25,920 --> 00:40:30,210
en array av pekare, vilka var och en
pekar på en länkad lista där

919
00:40:30,210 --> 00:40:32,360
första listan är alla
med namnet Alice.

920
00:40:32,360 --> 00:40:35,770
Den andra listan är alla med
namn som börjar med A, start

921
00:40:35,770 --> 00:40:36,980
med B, och så vidare.

922
00:40:36,980 --> 00:40:41,020
>> Vad är den sannolika längden av varje
dessa listor om vi antar en trevlig ren

923
00:40:41,020 --> 00:40:45,410
fördelning av namn A till Z
över hela datastrukturen?

924
00:40:45,410 --> 00:40:50,210
Det finns n folk i datastrukturen
dividerat med 26, om de är snyggt

925
00:40:50,210 --> 00:40:52,110
utspridda över hela
datastruktur.

926
00:40:52,110 --> 00:40:54,970
Så längden på var och en av dessa
kedjor är n dividerat med 26.

927
00:40:54,970 --> 00:40:57,380
Men i stort O notation, vad är det?

928
00:40:57,380 --> 00:41:00,100

929
00:41:00,100 --> 00:41:02,440
Vad är det egentligen?

930
00:41:02,440 --> 00:41:04,150
Så det är egentligen bara n, rätt?

931
00:41:04,150 --> 00:41:06,620
Eftersom vi har sagt tidigare,
att usch du dividera med 26.

932
00:41:06,620 --> 00:41:08,710
Ja, i verkligheten är det snabbare.

933
00:41:08,710 --> 00:41:12,720
Men i teorin är det inte i grunden
allt snabbare.

934
00:41:12,720 --> 00:41:16,040
>> Så vi verkar inte vara så mycket
närmare denna heliga graal.

935
00:41:16,040 --> 00:41:17,750
I själva verket är detta bara linjär tid.

936
00:41:17,750 --> 00:41:20,790
Heck, på denna punkt, varför gör inte vi
bara använda en enorm länkad lista?

937
00:41:20,790 --> 00:41:23,510
Varför inte vi använder bara en enorm
array för att lagra namnen på

938
00:41:23,510 --> 00:41:25,010
alla i rummet?

939
00:41:25,010 --> 00:41:28,280
Tja, är det fortfarande något
övertygande om en hash-tabell?

940
00:41:28,280 --> 00:41:30,810
Finns det fortfarande något övertygande
om en datastruktur

941
00:41:30,810 --> 00:41:33,940
som ser ut så här?

942
00:41:33,940 --> 00:41:35,182
Detta.

943
00:41:35,182 --> 00:41:37,050
>> STUDENT: [OHÖRBAR].

944
00:41:37,050 --> 00:41:39,840
>> Högtalare 1: Höger, och igen om det bara
en linjär tid algoritm, och en

945
00:41:39,840 --> 00:41:42,780
linjär tid datastruktur, varför gör inte jag
bara lagra allas namn i en stor

946
00:41:42,780 --> 00:41:44,210
array, eller i en länkad stor lista?

947
00:41:44,210 --> 00:41:47,010
Och sluta göra CS så mycket svårare
än det behöver vara?

948
00:41:47,010 --> 00:41:49,600

949
00:41:49,600 --> 00:41:53,190
Vad är övertygande om detta, även
fast jag kliade det ut?

950
00:41:53,190 --> 00:41:54,930
>> STUDENT: [OHÖRBAR].

951
00:41:54,930 --> 00:41:57,040
>> Högtalare 1: Infogningar inte?

952
00:41:57,040 --> 00:41:58,140
Dyrt längre.

953
00:41:58,140 --> 00:42:03,390
Så infogningar kunde potentiellt fortfarande
vara konstant tid, även om dina uppgifter

954
00:42:03,390 --> 00:42:07,910
struktur ser ut så här, en rad
pekare, är var och en pekar på

955
00:42:07,910 --> 00:42:09,550
potentiellt en länkad lista.

956
00:42:09,550 --> 00:42:15,220
Hur kan du uppnå konstant
tid insättning av namnen?

957
00:42:15,220 --> 00:42:16,280
Stick den i fronten, eller hur?

958
00:42:16,280 --> 00:42:19,290
>> Om vi ​​offrar en konstruktion mål från
tidigare, där vi ville behålla

959
00:42:19,290 --> 00:42:22,650
allas namn, till exempel, sorteras,
eller alla nummer på scenen sorteras,

960
00:42:22,650 --> 00:42:25,020
Anta att vi har en
osorterad länkad lista.

961
00:42:25,020 --> 00:42:29,960
Det kostar oss bara ett eller två steg,
som i fallet med Ben och Brian

962
00:42:29,960 --> 00:42:32,750
tidigare, för att infoga ett element vid
början av listan.

963
00:42:32,750 --> 00:42:36,090
Så om vi inte bryr oss om att sortera alla
av de namn som börjar med A eller samtliga

964
00:42:36,090 --> 00:42:39,660
namnen som börjar med B, kan vi fortfarande
uppnå konstant tid insättningen.

965
00:42:39,660 --> 00:42:43,900
Nu tittar upp Alice eller Bob eller några namn
mer generellt är fortfarande vad?

966
00:42:43,900 --> 00:42:48,100
Det är stort O n dividerat med 26, i
ideala fallet där alla är enhetligt

967
00:42:48,100 --> 00:42:51,190
distribueras, där det finns så många A: s
som det finns Zs, vilket förmodligen är

968
00:42:51,190 --> 00:42:52,220
orealistiskt.

969
00:42:52,220 --> 00:42:53,880
Men det är fortfarande linjär.

970
00:42:53,880 --> 00:42:57,120
>> Men här kommer vi tillbaka till den punkt
av asymptotisk notation som

971
00:42:57,120 --> 00:42:58,600
teoretiskt sant.

972
00:42:58,600 --> 00:43:02,960
Men i den verkliga världen, om jag hävdar att
mitt program kan göra något 26 gånger

973
00:43:02,960 --> 00:43:06,210
snabbare än din, vars program
ska du föredrar att använda?

974
00:43:06,210 --> 00:43:09,660
Yours eller gruvan, vilket
är 26 gånger snabbare?

975
00:43:09,660 --> 00:43:14,320
Realistiskt, är den person vars 26
gånger snabbare, även om teoretiskt

976
00:43:14,320 --> 00:43:18,790
våra algoritmer körs i samma
asymptotiska gångtid.

977
00:43:18,790 --> 00:43:20,940
>> Låt mig föreslå en annan
lösning helt och hållet.

978
00:43:20,940 --> 00:43:24,380
Och om detta inte blåsa ditt sinne,
vi ut ur datastrukturer.

979
00:43:24,380 --> 00:43:27,420
Så det här är det en trie -

980
00:43:27,420 --> 00:43:28,520
typ av ett dumt namn.

981
00:43:28,520 --> 00:43:32,880
Den kommer från hämtningar, och ordet
stavas trie, t-r-i-e, på grund av

982
00:43:32,880 --> 00:43:34,450
Naturligtvis hämtning låter som trie.

983
00:43:34,450 --> 00:43:36,580
Men det är historia
av ordet trie.

984
00:43:36,580 --> 00:43:40,980
>> Så en trie är faktiskt någon form av träd,
och det är också en lek med det ordet.

985
00:43:40,980 --> 00:43:46,330
Och även om du inte riktigt kan se det
med denna visualisering är en trie en

986
00:43:46,330 --> 00:43:50,790
träd strukturerad, som ett släktträd med
en förfader på toppen och massor

987
00:43:50,790 --> 00:43:54,530
av barnbarn och barnbarnsbarn
som löv på botten.

988
00:43:54,530 --> 00:43:58,100
Men varje nod i ett trie är en array.

989
00:43:58,100 --> 00:44:00,680
Och det är i en array - och låt oss
oversimplify för ett ögonblick - det är ett

990
00:44:00,680 --> 00:44:04,600
array, i detta fall, med storlek 26, där
varje nod är återigen en matris med storleken

991
00:44:04,600 --> 00:44:09,000
26, där den nollte element i den
array representerar A, och den sista

992
00:44:09,000 --> 00:44:11,810
elementet i varje sådan
arrayen representerar Z.

993
00:44:11,810 --> 00:44:15,520
>> Så jag föreslår alltså att dessa uppgifter
struktur, känd som en trie kan vara

994
00:44:15,520 --> 00:44:17,600
används också för att lagra ord.

995
00:44:17,600 --> 00:44:21,740
Vi såg en stund sedan hur vi skulle kunna lagra
ord, eller i detta fall namn, och vi

996
00:44:21,740 --> 00:44:25,440
såg tidigare hur vi kan spara nummer,
men om vi fokuserar på namn eller strängar

997
00:44:25,440 --> 00:44:27,460
här, märker vad som är intressant.

998
00:44:27,460 --> 00:44:32,210
Jag hävdar att namnet Maxwell är
insidan av denna datastruktur.

999
00:44:32,210 --> 00:44:33,730
Var ser ni Maxwell?

1000
00:44:33,730 --> 00:44:35,140
>> STUDENT: [OHÖRBAR].

1001
00:44:35,140 --> 00:44:36,240
>> Högtalare 1: Till vänster.

1002
00:44:36,240 --> 00:44:39,910
Så vad är intressant med dessa data
struktur är i stället lagra

1003
00:44:39,910 --> 00:44:46,200
string M-A-X-W-E-L-L backslash noll, alla
angränsande, vad du gör istället

1004
00:44:46,200 --> 00:44:46,890
följer.

1005
00:44:46,890 --> 00:44:50,510
Om detta är en trie som datastruktur,
vars samtliga noder är återigen en array,

1006
00:44:50,510 --> 00:44:54,650
och du vill lagra Maxwell, du först
index och så roten nod, så

1007
00:44:54,650 --> 00:44:57,810
att tala, den översta noden,
på plats M, rätt, så

1008
00:44:57,810 --> 00:44:59,160
ungefär i mitten.

1009
00:44:59,160 --> 00:45:03,740
Och sedan därifrån, följer du en
pekare till ett barn noder, så att säga.

1010
00:45:03,740 --> 00:45:06,150
Så i släktträdet mening,
du följer den nedåt.

1011
00:45:06,150 --> 00:45:09,030
Och som leder dig till en annan nod
till vänster där, vilket är

1012
00:45:09,030 --> 00:45:10,540
bara en annan array.

1013
00:45:10,540 --> 00:45:14,710
>> Och sedan om du vill lagra Maxwell,
du hittar pekaren som representerar

1014
00:45:14,710 --> 00:45:16,430
A, är som den här här.

1015
00:45:16,430 --> 00:45:17,840
Då går du till nästa nod.

1016
00:45:17,840 --> 00:45:20,100
Och notera - det är därför bildens
lite lura -

1017
00:45:20,100 --> 00:45:21,990
denna nod ser super liten.

1018
00:45:21,990 --> 00:45:26,050
Men till höger om detta är Y och Z.
Det är bara författaren har avkortat

1019
00:45:26,050 --> 00:45:27,630
bilden så att du faktiskt
se saker.

1020
00:45:27,630 --> 00:45:30,400
Annars här bilden
skulle vara enormt stort.

1021
00:45:30,400 --> 00:45:36,180
Så nu index i plats X, sedan
W, sedan E, sedan L, då L. vad är

1022
00:45:36,180 --> 00:45:37,380
denna nyfikenhet?

1023
00:45:37,380 --> 00:45:41,250
>> Tja, om vi använder denna typ av nya
ta om hur du lagrar en sträng i en

1024
00:45:41,250 --> 00:45:44,500
datastruktur, måste du ändå
huvudsak bocka i data

1025
00:45:44,500 --> 00:45:47,250
struktur som ett ord slutar här.

1026
00:45:47,250 --> 00:45:50,830
Med andra ord, var och en av dessa noder
på något sätt måste komma ihåg att vi

1027
00:45:50,830 --> 00:45:53,500
faktiskt följt alla dessa pekare
och lämnar en liten

1028
00:45:53,500 --> 00:45:58,370
brödinkråm längst ner här i detta
struktur för att indikera M-A-X-W-E-L-L är

1029
00:45:58,370 --> 00:46:00,230
verkligen i denna datastruktur.

1030
00:46:00,230 --> 00:46:02,040
>> Så vi kan göra detta på följande sätt.

1031
00:46:02,040 --> 00:46:06,810
Var och en av noderna i den bild vi bara
Sågen har en, en matris med storlek 27.

1032
00:46:06,810 --> 00:46:10,550
Och det är nu 27, eftersom p satt sex,
vi faktiskt ge dig en apostrof,

1033
00:46:10,550 --> 00:46:13,590
så att vi kan ha namn som O'Reilly
och andra med apostrofer.

1034
00:46:13,590 --> 00:46:14,820
Men samma idé.

1035
00:46:14,820 --> 00:46:17,710
Vart och ett av dessa element i
array pekar på en struct

1036
00:46:17,710 --> 00:46:19,320
nod, så bara en nod.

1037
00:46:19,320 --> 00:46:21,430
Så detta är mycket påminner
av vår länkad lista.

1038
00:46:21,430 --> 00:46:24,550
>> Och då har jag en Boolean, som jag ska
kalla ord, vilket bara kommer att bli

1039
00:46:24,550 --> 00:46:29,120
sant om ett ord slutar vid detta
nod i trädet.

1040
00:46:29,120 --> 00:46:32,870
Den representerar effektivt det lilla
triangel vi såg för en stund sedan.

1041
00:46:32,870 --> 00:46:37,190
Så om ett ord slutar vid den noden i
träd, kommer det ordet fältet vara sant,

1042
00:46:37,190 --> 00:46:41,990
som begreppsmässigt är att bocka av, eller
vi drar denna triangel, ja det

1043
00:46:41,990 --> 00:46:44,080
är ett ord här.

1044
00:46:44,080 --> 00:46:45,120
>> Så detta är en trie.

1045
00:46:45,120 --> 00:46:48,540
Och nu är frågan, vad
är dess gångtid?

1046
00:46:48,540 --> 00:46:49,930
Är det stora O n?

1047
00:46:49,930 --> 00:46:51,410
Är det något annat?

1048
00:46:51,410 --> 00:46:57,330
Tja, om du har n namn i dessa data
struktur, Maxwell är bara en av

1049
00:46:57,330 --> 00:47:02,330
dem, vad är gångtiden
insättning eller hitta Maxwell?

1050
00:47:02,330 --> 00:47:06,230

1051
00:47:06,230 --> 00:47:09,050
Vad är gångtiden
att infoga Maxwell?

1052
00:47:09,050 --> 00:47:11,740
Om det finns n andra namn
redan i tabellen?

1053
00:47:11,740 --> 00:47:12,507
Yeah?

1054
00:47:12,507 --> 00:47:15,429
>> STUDENT: [OHÖRBAR].

1055
00:47:15,429 --> 00:47:17,550
>> Högtalare 1: Ja, det är längden
av namnet, eller hur?

1056
00:47:17,550 --> 00:47:24,420
Så M-a-x-w-e-l-l så det känns som detta
Algoritmen är stort O i sju.

1057
00:47:24,420 --> 00:47:26,580
Nu, naturligtvis, namnet
kommer att variera i längd.

1058
00:47:26,580 --> 00:47:27,380
Kanske är det ett kort namn.

1059
00:47:27,380 --> 00:47:28,600
Kanske är det ett längre namn.

1060
00:47:28,600 --> 00:47:33,390
Men vad är nyckeln här är att
det är ett konstant antal.

1061
00:47:33,390 --> 00:47:36,810
Och kanske är det inte riktigt konstant,
men gud, om realistiskt, i en

1062
00:47:36,810 --> 00:47:41,570
lexikon, det finns förmodligen någon gräns
på antalet bokstäver i ett

1063
00:47:41,570 --> 00:47:43,820
personens namn i ett visst land.

1064
00:47:43,820 --> 00:47:46,940
>> Och så kan vi anta att
värde är en konstant.

1065
00:47:46,940 --> 00:47:47,750
Jag vet inte vad det är.

1066
00:47:47,750 --> 00:47:50,440
Det är förmodligen större än
Vi tycker att det är.

1067
00:47:50,440 --> 00:47:52,720
Eftersom det finns alltid något hörn
fallet med ett galet långt namn.

1068
00:47:52,720 --> 00:47:56,360
Så låt oss kalla det k, men det är fortfarande en
konstant förmodligen, eftersom varje

1069
00:47:56,360 --> 00:48:00,190
namn i världen, åtminstone i ett
visst land, är att längden eller

1070
00:48:00,190 --> 00:48:01,780
kortare, så det är konstant.

1071
00:48:01,780 --> 00:48:04,490
Men när vi har sagt något är stort
O för ett konstant värde, vad är det

1072
00:48:04,490 --> 00:48:07,760
verkligen motsvarar?

1073
00:48:07,760 --> 00:48:10,420
Det är egentligen samma sak
som säger konstant tid.

1074
00:48:10,420 --> 00:48:11,530
>> Nu är vi typ av fusk, eller hur?

1075
00:48:11,530 --> 00:48:15,340
Vi är typ av hävstångseffekt viss teori
här för att säga att ja, är ordningen k

1076
00:48:15,340 --> 00:48:17,450
egentligen bara beställa av en,
och det är konstant tid.

1077
00:48:17,450 --> 00:48:18,200
Men det är egentligen.

1078
00:48:18,200 --> 00:48:22,550
Eftersom den viktigaste insikten här är att
Om vi ​​har n namn redan i detta

1079
00:48:22,550 --> 00:48:26,010
datastruktur, och vi skär Maxwell,
är den tid det tar för oss att

1080
00:48:26,010 --> 00:48:29,530
infoga Maxwell alls påverkade
av hur många andra människor

1081
00:48:29,530 --> 00:48:31,100
är i datastrukturen?

1082
00:48:31,100 --> 00:48:31,670
Verkar inte vara.

1083
00:48:31,670 --> 00:48:36,280
Om jag hade en miljard fler element till detta
trie och sedan in Maxwell, är

1084
00:48:36,280 --> 00:48:38,650
han alls påverkas?

1085
00:48:38,650 --> 00:48:39,050
Nej.

1086
00:48:39,050 --> 00:48:42,950
Och det är till skillnad från någon av dagen uppgifter
strukturer som vi har sett hittills, där

1087
00:48:42,950 --> 00:48:46,820
speltid för din algoritm är
helt oberoende av hur mycket

1088
00:48:46,820 --> 00:48:51,430
grejer är eller inte redan
i den datastruktur.

1089
00:48:51,430 --> 00:48:54,650
>> Och så detta ger dig är nu en
möjlighet för p set sex, vilket kommer

1090
00:48:54,650 --> 00:48:58,310
återigen innebära att implementera en egen
stavningskontroll, läsning i 150.000

1091
00:48:58,310 --> 00:49:01,050
ord, hur man bäst för att lagra den
inte nödvändigtvis är uppenbart.

1092
00:49:01,050 --> 00:49:04,030
Och även om jag har strävat efter att hitta
den heliga graal, gör jag inte

1093
00:49:04,030 --> 00:49:05,330
hävdar att ett trie är.

1094
00:49:05,330 --> 00:49:09,810
Faktum är att en hash-tabell kan mycket väl
visa sig vara mycket effektivare.

1095
00:49:09,810 --> 00:49:10,830
Men de är bara -

1096
00:49:10,830 --> 00:49:14,620
det är bara en av de designbeslut
du måste göra.

1097
00:49:14,620 --> 00:49:18,920
>> Men stängning låt oss ta 50 eller så
sekunder för att ta en titt på vad som ligger

1098
00:49:18,920 --> 00:49:22,190
framåt nästa vecka och därefter vi övergången
från denna kommandoraden

1099
00:49:22,190 --> 00:49:26,220
världen Om C-program till saker web
baserade och språk som PHP och

1100
00:49:26,220 --> 00:49:30,350
JavaScript och internet i sig,
protokoll som HTTP, som du har

1101
00:49:30,350 --> 00:49:32,870
tas för givet i år
nu, och skrivit de flesta varje

1102
00:49:32,870 --> 00:49:34,440
dag, kanske, eller sett.

1103
00:49:34,440 --> 00:49:37,420
Och vi börjar att skala tillbaka
lager av vad som är internet.

1104
00:49:37,420 --> 00:49:40,650
Och vad är den kod som
ligger bakom dagens verktyg.

1105
00:49:40,650 --> 00:49:43,230
Så 50 sekunder av denna teaser här.

1106
00:49:43,230 --> 00:49:46,570
Jag ger dig Warriors of the Net.

1107
00:49:46,570 --> 00:49:51,370
>> [VIDEO SPELA]

1108
00:49:51,370 --> 00:49:56,764
>> -Han kom med ett budskap.

1109
00:49:56,764 --> 00:50:00,687
Med ett protokoll all hans eget.

1110
00:50:00,687 --> 00:50:13,370

1111
00:50:13,370 --> 00:50:19,780
Han kom till en värld av grymma brandväggar,
likgiltig routrar, och faror långt

1112
00:50:19,780 --> 00:50:22,600
värre än döden.

1113
00:50:22,600 --> 00:50:23,590
Han är snabb.

1114
00:50:23,590 --> 00:50:25,300
Han är stark.

1115
00:50:25,300 --> 00:50:27,700
Han är TCPIP.

1116
00:50:27,700 --> 00:50:30,420
Och han har fått din adress.

1117
00:50:30,420 --> 00:50:32,920

1118
00:50:32,920 --> 00:50:34,590
Krigare av nätet.

1119
00:50:34,590 --> 00:50:35,290
>> [END VIDEOAVSPELNING]

1120
00:50:35,290 --> 00:50:38,070
>> Högtalare 1: Det är hur internet
ska arbeta med nästa vecka.

1121
00:50:38,070 --> 00:50:40,406