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

2
00:00:11,860 --> 00:00:13,120
>> Kryetari 1: Të gjithë të drejtë, kështu që ne jemi prapa.

3
00:00:13,120 --> 00:00:14,480
Mirë se vini në CS50.

4
00:00:14,480 --> 00:00:16,510
Ky është fundi i javës së shtatë.

5
00:00:16,510 --> 00:00:20,200
Pra, kujtojnë se herën e fundit, kemi filluar
në kërkim të pak më të sofistikuar

6
00:00:20,200 --> 00:00:21,100
Strukturat e të dhënave.

7
00:00:21,100 --> 00:00:25,110
Që nga viti deri më tani, të gjithë kemi pasur me të vërtetë
në dispozicionin tonë ishte kjo, një koleksion.

8
00:00:25,110 --> 00:00:29,340
>> Por, para se të hidhni array si jo
të gjitha që interesante, e cila në të vërtetë ajo

9
00:00:29,340 --> 00:00:33,570
në fakt është, cilat janë disa nga
pluses e këtyre të dhënave të thjeshta

10
00:00:33,570 --> 00:00:34,560
Struktura e deritanishme?

11
00:00:34,560 --> 00:00:36,110
Çfarë është ajo e mirë në?

12
00:00:36,110 --> 00:00:39,450
Deri më tani si kemi parë?

13
00:00:39,450 --> 00:00:42,540
Çfarë keni?

14
00:00:42,540 --> 00:00:44,028
Asgjë.

15
00:00:44,028 --> 00:00:45,020
>> STUDENT: [padëgjueshme].

16
00:00:45,020 --> 00:00:45,395
>> Kryetari 1: Çfarë është ajo?

17
00:00:45,395 --> 00:00:46,410
>> STUDENT: [padëgjueshme].

18
00:00:46,410 --> 00:00:47,000
>> Kryetari 1: Madhësia fikse.

19
00:00:47,000 --> 00:00:51,260
OK, kështu që pse është madhësia fiks mirë edhe pse?

20
00:00:51,260 --> 00:00:53,180
>> STUDENT: [padëgjueshme].

21
00:00:53,180 --> 00:00:56,240
>> Kryetari 1: OK, prandaj është efikas në
Ndjenja që ju mund të ndajë një

22
00:00:56,240 --> 00:01:00,070
Shuma fikse e hapësirës, ​​të cilat shpresojmë se
është pikërisht aq sa

23
00:01:00,070 --> 00:01:01,180
hapësirë ​​si ju dëshironi.

24
00:01:01,180 --> 00:01:02,720
Kështu që mund të jetë absolutisht një plus.

25
00:01:02,720 --> 00:01:06,530
>> Çfarë është një anë tjetër nga një grup?

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

27
00:01:07,610 --> 00:01:08,750
>> STUDENT: [padëgjueshme].

28
00:01:08,750 --> 00:01:09,550
>> Kryetari 1: All - keq?

29
00:01:09,550 --> 00:01:11,270
>> STUDENT: [padëgjueshme].

30
00:01:11,270 --> 00:01:13,620
>> Kryetari 1: Të gjitha kutitë në kujtesën
ose pranë njëri-tjetrit.

31
00:01:13,620 --> 00:01:15,220
Dhe kjo është e dobishme - pse?

32
00:01:15,220 --> 00:01:15,970
Kjo është mjaft e vërtetë.

33
00:01:15,970 --> 00:01:18,611
Por si mund ta shfrytëzojnë këtë të vërtetë?

34
00:01:18,611 --> 00:01:21,500
>> STUDENT: [padëgjueshme].

35
00:01:21,500 --> 00:01:24,490
>> Kryetari 1: Pikërisht, ne mund të ruaj gjurmët e
ku çdo gjë është vetëm duke e ditur

36
00:01:24,490 --> 00:01:28,560
një adresë, pra adresën e
bajt i parë i asaj copë e kujtesës.

37
00:01:28,560 --> 00:01:30,420
Ose në rastin e vargut,
adresa e parë

38
00:01:30,420 --> 00:01:31,460
char në atë varg.

39
00:01:31,460 --> 00:01:33,330
Dhe nga atje, ne mund të gjeni
fundi i vargut.

40
00:01:33,330 --> 00:01:35,710
Ne mund të gjejmë elementin e dytë,
Elementi i tretë, dhe kështu me radhë.

41
00:01:35,710 --> 00:01:38,740
>> Dhe kështu mënyrë e sofistikuar për të përshkruar se
Tipar është se vargjeve të na japë

42
00:01:38,740 --> 00:01:40,020
qasje të rastit.

43
00:01:40,020 --> 00:01:44,330
Vetëm duke përdorur kllapa katrore
simbol dhe një numër, ju mund të kërcejnë për të

44
00:01:44,330 --> 00:01:48,070
një element specifik në rrjet
në kohë të vazhdueshme, Big O

45
00:01:48,070 --> 00:01:49,810
nga një, në mënyrë që të flasin.

46
00:01:49,810 --> 00:01:51,080
>> Por ka pasur disa dobësi.

47
00:01:51,080 --> 00:01:53,110
Çfarë nuk të bëjë një koleksion shumë e lehtë?

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

49
00:01:55,810 --> 00:01:57,170
Çfarë ajo nuk është e mirë në?

50
00:01:57,170 --> 00:01:58,810
>> STUDENT: [padëgjueshme].

51
00:01:58,810 --> 00:01:59,860
>> Kryetari 1: Çfarë është ajo?

52
00:01:59,860 --> 00:02:00,530
>> STUDENT: [padëgjueshme].

53
00:02:00,530 --> 00:02:01,460
>> Kryetari 1: Zgjerimi në madhësi.

54
00:02:01,460 --> 00:02:04,800
Pra, dobësi e vargut janë
pikërisht e kundërta e asaj që

55
00:02:04,800 --> 00:02:05,540
upsides janë.

56
00:02:05,540 --> 00:02:07,610
Kështu një nga dobësi eshte
se kjo është një madhësi të caktuar.

57
00:02:07,610 --> 00:02:09,400
Pra, ju nuk mund të vërtetë rritet ajo.

58
00:02:09,400 --> 00:02:13,510
Ju mund të rialokuar një copë të madhe të
kujtesës, dhe pastaj të lëvizë elementet e vjetra

59
00:02:13,510 --> 00:02:14,460
në rrjet të ri.

60
00:02:14,460 --> 00:02:18,060
Dhe pastaj pa array vjetër, për
shembull, duke përdorur malloc ose një të ngjashme

61
00:02:18,060 --> 00:02:21,180
funksion të quajtur realloc, e cila
rialokim kujtesës.

62
00:02:21,180 --> 00:02:25,490
>> Realloc, si një mënjanë, përpiqet të japë ty
kujtesës që më tej të array

63
00:02:25,490 --> 00:02:26,610
që ju tashmë keni.

64
00:02:26,610 --> 00:02:28,740
Por kjo mund të lëvizin gjërat
rreth krejt.

65
00:02:28,740 --> 00:02:30,710
Por në të shkurtër, kjo është e shtrenjtë, e drejtë?

66
00:02:30,710 --> 00:02:33,440
Sepse në qoftë se ju keni një copë e kujtesës së
këtë madhësi, por ju me të vërtetë duan një

67
00:02:33,440 --> 00:02:36,710
i kësaj madhësie, dhe ju doni për të ruajtur
elementet origjinale, ju keni

68
00:02:36,710 --> 00:02:40,510
afërsisht një proces linear kopjimi koha
që ka nevojë të ndodhë nga

69
00:02:40,510 --> 00:02:41,900
array vjetra në të reja.

70
00:02:41,900 --> 00:02:44,630
Dhe realiteti është kërkuar që veprojnë
Sistemi përsëri dhe përsëri dhe

71
00:02:44,630 --> 00:02:48,340
përsëri për chunks të mëdha të kujtesës mund të fillojnë
të ju kushtojë disa kohë si.

72
00:02:48,340 --> 00:02:52,250
Pra, kjo është si një bekim dhe një mallkim në
fsheh, faktin se këto vargjeve

73
00:02:52,250 --> 00:02:53,860
janë të madhësisë fikse.

74
00:02:53,860 --> 00:02:56,790
Por në qoftë se ne kemi prezantuar diçka në vend
si kjo, të cilën ne e quajti një linked

75
00:02:56,790 --> 00:03:00,580
lista, ne kemi marrë një upsides pak dhe
disa dobësi si edhe këtu.

76
00:03:00,580 --> 00:03:05,780
>> Pra, një listë e lidhur është thjesht një të dhënave
Struktura e përbërë nga structs C në këtë

77
00:03:05,780 --> 00:03:09,850
rasti, ku një struct, risjell, është vetëm
një enë për një ose më shumë specifik

78
00:03:09,850 --> 00:03:11,100
Llojet e variablave.

79
00:03:11,100 --> 00:03:16,110
Në këtë rast, çfarë bëni llojet e të dhënave
duket te jenë brendësi të struct që

80
00:03:16,110 --> 00:03:17,600
hera e fundit që kemi quajtur një nyje?

81
00:03:17,600 --> 00:03:19,380
Secila prej këtyre rectangles është një nyje.

82
00:03:19,380 --> 00:03:22,660
Dhe secili prej rectangles vogla
në brendësi të saj është një lloj i të dhënave.

83
00:03:22,660 --> 00:03:25,300
Çfarë lloje e themi
ata ishin të hënën?

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

85
00:03:26,478 --> 00:03:27,870
>> STUDENT: [padëgjueshme].

86
00:03:27,870 --> 00:03:30,721
>> FOLËSI 1: Një variabël dhe një akrep, ose
më konkretisht, një int, për n,

87
00:03:30,721 --> 00:03:32,180
dhe një akrep në pjesën e poshtme.

88
00:03:32,180 --> 00:03:35,360
Dy prej atyre të ndodhë që të jetë 32 bit, at
paktën në një kompjuter si kjo CS50

89
00:03:35,360 --> 00:03:37,980
Appliance, dhe kështu ata janë
tërhequr në mënyrë të barabartë në madhësi.

90
00:03:37,980 --> 00:03:42,260
>> Pra, çfarë jeni duke përdorur treguesin
edhe pse me sa duket për?

91
00:03:42,260 --> 00:03:47,690
Pse shtoni këtë shigjetën tani kur vargjeve ishin
aq e bukur dhe të pastër dhe të thjeshtë?

92
00:03:47,690 --> 00:03:50,460
Çfarë është bërë për treguesin
na në secilin prej këtyre nyjeve?

93
00:03:50,460 --> 00:03:52,160
>> STUDENT: [padëgjueshme].

94
00:03:52,160 --> 00:03:52,465
>> Kryetari 1: Pikërisht.

95
00:03:52,465 --> 00:03:54,120
Është thënë se ku
një tjetër është.

96
00:03:54,120 --> 00:03:57,350
Kështu që unë lloj përdorur analogjinë e
duke përdorur një fije të lloj

97
00:03:57,350 --> 00:03:59,180
thread këto nyje së bashku.

98
00:03:59,180 --> 00:04:01,760
Dhe kjo është pikërisht ajo që ne jemi duke bërë me
pointers sepse secili prej këtyre

99
00:04:01,760 --> 00:04:06,360
chunks e kujtesës mund ose nuk mund të jetë
puqur, të kthehet prapa për të mbështetur

100
00:04:06,360 --> 00:04:09,500
brenda RAM, sepse çdo herë që
telefononi malloc thënë, më jepni të mjaftueshme

101
00:04:09,500 --> 00:04:12,510
bytes për një nyje të re, ajo mund të
jetë këtu ose ajo mund të jetë këtu.

102
00:04:12,510 --> 00:04:13,120
Ajo mund të jetë këtu.

103
00:04:13,120 --> 00:04:13,730
Ajo mund të jetë këtu.

104
00:04:13,730 --> 00:04:14,640
Ju thjesht nuk e di.

105
00:04:14,640 --> 00:04:17,880
>> Por duke përdorur pointers në adresat e
ato nyjet, ju mund të thur ato

106
00:04:17,880 --> 00:04:22,370
bashku në një mënyrë që duket me sy
si një listë edhe në qoftë se këto gjëra janë

107
00:04:22,370 --> 00:04:26,770
të gjithë të shtrirë në të gjithë ose një tuaj
dy tuaj ose katër gigabajt të RAM tuaj

108
00:04:26,770 --> 00:04:28,760
brenda e kompjuterit tuaj.

109
00:04:28,760 --> 00:04:33,230
>> Pra downside, pastaj,
një listë e lidhur është ajo?

110
00:04:33,230 --> 00:04:34,670
Çfarë është një çmim që ne jemi
me sa duket duke paguar?

111
00:04:34,670 --> 00:04:36,010
>> STUDENT: [padëgjueshme].

112
00:04:36,010 --> 00:04:36,920
>> Kryetari 1: Më shumë hapësirë, e drejtë?

113
00:04:36,920 --> 00:04:39,340
Ne kemi, në këtë rast, dyfishuar shumën
e hapësirës, ​​sepse ne kemi shkuar

114
00:04:39,340 --> 00:04:43,500
nga 32 bit për çdo nyje, për secilin
int, kështu që tani e 64 bit, sepse ne kemi për të

115
00:04:43,500 --> 00:04:45,050
të mbajë rreth një pointer si.

116
00:04:45,050 --> 00:04:48,860
Ju merrni më shumë efikasitet nëse struct juaj
është më e madhe se sa kjo gjë e thjeshtë.

117
00:04:48,860 --> 00:04:52,020
Nëse jeni të vërtetë kanë një student brenda
i cili eshte nje çift i gradët

118
00:04:52,020 --> 00:04:55,430
Emri dhe shtëpi, ndoshta një numër ID,
ndoshta disa fusha të tjera krejt.

119
00:04:55,430 --> 00:04:59,000
>> Pra, nëse ju keni një struct mjaft i madh,
atëherë ndoshta kostoja e treguesin është

120
00:04:59,000 --> 00:05:00,010
nuk është e tillë një punë e madhe.

121
00:05:00,010 --> 00:05:03,570
Kjo është pak e një qoshe në rast se
ne jemi ruajtjen tillë primitive e thjeshtë

122
00:05:03,570 --> 00:05:04,760
brendësi të lista lidhura.

123
00:05:04,760 --> 00:05:05,790
Por pikë është e njëjtë.

124
00:05:05,790 --> 00:05:08,230
Ju jeni patjetër të shpenzojnë më shumë
kujtesës, por ju jeni duke marrë

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

126
00:05:08,990 --> 00:05:12,280
Sepse tani në qoftë se unë dua të shtoj një element
në fillim të kësaj liste,

127
00:05:12,280 --> 00:05:14,340
Unë duhet të akordojë një nyje të re.

128
00:05:14,340 --> 00:05:17,180
Dhe unë duhet të vetëm update ata
Shigjetat disi nga vetëm duke lëvizur

129
00:05:17,180 --> 00:05:17,980
disa pointers rreth.

130
00:05:17,980 --> 00:05:20,580
>> Nëse unë dua të futur diçka në
mesi i listës, unë nuk kam për të

131
00:05:20,580 --> 00:05:24,410
shtyjë të gjithëve mënjanë si ne e bëmë në
kaluarën javësh me vullnetarët tanë të cilët

132
00:05:24,410 --> 00:05:25,700
përfaqësuar një rrjet.

133
00:05:25,700 --> 00:05:29,470
Unë vetëm mund të ndajë një nyje të re dhe
atëherë vetëm pikë shigjetat në

134
00:05:29,470 --> 00:05:32,290
drejtimet e ndryshme, sepse ajo nuk
duhet të mbetet në aktuale

135
00:05:32,290 --> 00:05:35,670
kujtim një linjë të vërtetë si unë kam tërhequr
kjo këtu në ekran.

136
00:05:35,670 --> 00:05:38,400
>> Dhe pastaj së fundi, në qoftë se ju doni të futur
diçka në fund të listës, kjo është

137
00:05:38,400 --> 00:05:39,210
edhe më e lehtë.

138
00:05:39,210 --> 00:05:43,320
Kjo është lloj i simbol arbitrare,
por akrep 34-së, të marrë një guess.

139
00:05:43,320 --> 00:05:46,710
Cila është vlera e treguesin e saj më të
lloj të ngjarë të tërhequr si një i vjetër

140
00:05:46,710 --> 00:05:47,700
antenë shkollë atje?

141
00:05:47,700 --> 00:05:48,920
>> STUDENT: [padëgjueshme].

142
00:05:48,920 --> 00:05:49,900
>> Kryetari 1: Kjo është ndoshta null.

143
00:05:49,900 --> 00:05:52,710
Dhe me të vërtetë që është një autor të
përfaqësimi i null.

144
00:05:52,710 --> 00:05:56,310
Dhe kjo është për shkak se ju absolutisht të pavlefshëm
duhet të dinë se ku fundi i një linked

145
00:05:56,310 --> 00:06:00,050
Lista është, që të mos ju mbani poshtë dhe
ndjekur dhe duke ndjekur këto shigjeta

146
00:06:00,050 --> 00:06:01,170
për disa vlera mbeturinave.

147
00:06:01,170 --> 00:06:06,230
Pra, do null ditur se nuk ka asnjë
nyjet më shumë për të drejtën e numrit 34,

148
00:06:06,230 --> 00:06:07,200
në këtë rast.

149
00:06:07,200 --> 00:06:10,270
>> Pra, ne propozojmë që ne mund të zbatojë
kjo nyje në kodin.

150
00:06:10,270 --> 00:06:12,130
Dhe ne kemi parë këtë lloj
të sintaksës e para.

151
00:06:12,130 --> 00:06:15,090
Typedef thjesht përcakton një lloj të ri për
na, na jep një sinonim si

152
00:06:15,090 --> 00:06:17,100
string ishte për * char.

153
00:06:17,100 --> 00:06:21,030
Në këtë rast, ajo do të na japë
simbol stenografi në mënyrë që nyjen struct

154
00:06:21,030 --> 00:06:24,010
në vend të vetëm mund të shkruhet si
nyjeve, e cila eshte nje pastruese shumë.

155
00:06:24,010 --> 00:06:25,360
Kjo është një shumë më pak fjalëshumë.

156
00:06:25,360 --> 00:06:30,080
>> Brenda një nyje është me sa duket një int
n quajtur, dhe pastaj një nyje struct *

157
00:06:30,080 --> 00:06:34,670
që do të thotë saktësisht se çfarë ne kemi dashur
shigjeta për të do të thotë, një tregues për një tjetër

158
00:06:34,670 --> 00:06:36,940
Nyja e llojit të njëjtë e saktë të të dhënave.

159
00:06:36,940 --> 00:06:40,300
Dhe unë propozoj që ne mund të zbatojë një
kërko funksion si kjo, e cila në

160
00:06:40,300 --> 00:06:41,890
shikim të parë mund të duket
një kompleks pak.

161
00:06:41,890 --> 00:06:43,330
Por le të shohim atë në kontekst.

162
00:06:43,330 --> 00:06:45,480
>> Më lejoni të kalojmë në aplikim këtu.

163
00:06:45,480 --> 00:06:48,460
Më lejoni të hapur një skedar të quajtur
Lista zero dot h.

164
00:06:48,460 --> 00:06:53,950
Dhe që përmban vetëm përkufizimi
pashë vetëm një moment më parë për këto të dhëna

165
00:06:53,950 --> 00:06:55,390
Lloji quhet nyje.

166
00:06:55,390 --> 00:06:57,350
Pra, ne kemi vënë në një skedar h dot.

167
00:06:57,350 --> 00:07:01,430
>> Dhe si një mënjanë, edhe pse kjo
program që ju jeni gati për të parë është

168
00:07:01,430 --> 00:07:05,410
jo të gjithë se komplekse, ajo është me të vërtetë
Konventa kur shkruhet një program për

169
00:07:05,410 --> 00:07:10,270
vënë gjëra të tilla si lloje të të dhënave, për të tërhequr
konstanta ndonjëherë, brenda tuaj

170
00:07:10,270 --> 00:07:13,210
fotografi header dhe jo domosdoshmërisht në
C fotografinë tuaj, sigurisht kur tuaj

171
00:07:13,210 --> 00:07:17,370
Programet merrni më të mëdha dhe më të mëdha, në mënyrë që
ju e dini ku mund të shikoni për të dyja

172
00:07:17,370 --> 00:07:20,840
Dokumentacioni në disa raste, apo
për bazat si kjo,

173
00:07:20,840 --> 00:07:22,360
Përkufizimi i disa lloj.

174
00:07:22,360 --> 00:07:25,680
>> Nëse unë tashmë e hapur deri list zero dot
c, vini re disa gjëra.

175
00:07:25,680 --> 00:07:29,090
Ai përfshin një fotografi pak më Header,
nga të cilat ne kemi parë më parë.

176
00:07:29,090 --> 00:07:31,980
Ai përfshin vetë dosjen e saj header.

177
00:07:31,980 --> 00:07:35,200
>> Dhe si një mënjanë, pse kjo është e dyfishtë
citon këtu, në krahasim me kënd

178
00:07:35,200 --> 00:07:38,340
kllapa në linjën që
Unë e kam theksuar atje?

179
00:07:38,340 --> 00:07:39,180
>> STUDENT: [padëgjueshme].

180
00:07:39,180 --> 00:07:40,460
>> Kryetari 1: Po kështu kjo është një skedar lokal.

181
00:07:40,460 --> 00:07:44,300
Pra, në qoftë se ajo është një fotografi lokale nga mesi juaj ketu
on line 15, për shembull, ju përdorni

182
00:07:44,300 --> 00:07:46,570
kuotat e dyfishtë në vend
i kllapave angled.

183
00:07:46,570 --> 00:07:48,270
>> Tani kjo është lloj i interesante.

184
00:07:48,270 --> 00:07:51,830
Vini re se unë kam deklaruar një global
ndryshueshme në këtë program on line 18

185
00:07:51,830 --> 00:07:55,910
thirrur së pari, ideja e të qenit kjo është
do të jetë një kursori te pare

186
00:07:55,910 --> 00:07:59,190
Nyja në listën time të lidhura, dhe unë kam
initialized atë të pavlefshëm, sepse unë kam

187
00:07:59,190 --> 00:08:02,310
nuk ndahen asnjë aktuale
nyjet vetëm ende.

188
00:08:02,310 --> 00:08:07,570
>> Pra, kjo përfaqëson, në pikturë, ajo që ne
pashë një moment më parë në foto si

189
00:08:07,570 --> 00:08:10,090
se pointer on tani
anën e majtë.

190
00:08:10,090 --> 00:08:12,260
Deri tani, që pointer
nuk kanë një shigjetë.

191
00:08:12,260 --> 00:08:14,590
Ajo në vend është vetëm null.

192
00:08:14,590 --> 00:08:17,880
Por, ajo përfaqëson atë që do të jetë
adresa aktuale e parë

193
00:08:17,880 --> 00:08:19,480
Nyja në këtë listë.

194
00:08:19,480 --> 00:08:22,120
Kështu që unë kam zbatuar ajo është një global
sepse, si ju do të shihni, e gjithë kjo

195
00:08:22,120 --> 00:08:25,310
Programi bën në jetë është të zbatojë
një listë e lidhur për mua.

196
00:08:25,310 --> 00:08:27,050
>> Tani unë kam një prototipe disa këtu.

197
00:08:27,050 --> 00:08:31,190
I vendosur për të zbatuar karakteristika si
, fshirjen e futje, kërkim, dhe

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

199
00:08:31,740 --> 00:08:35,210
shëtitje nëpër fundit vetëm duke u
lista, shtypje nga elementet e saj.

200
00:08:35,210 --> 00:08:36,750
Dhe tani këtu është rutinë im kryesor.

201
00:08:36,750 --> 00:08:39,890
Dhe ne nuk do të shpenzojnë shumë kohë në
këto që kjo është lloj i, me shpresë

202
00:08:39,890 --> 00:08:41,780
hat e vjetër deri tani.

203
00:08:41,780 --> 00:08:45,370
>> Unë jam duke shkuar për të bërë në vijim,
ndërsa përdoruesit bashkëpunon.

204
00:08:45,370 --> 00:08:47,300
Pra një, unë jam duke shkuar për të shtypur
nga kjo menu.

205
00:08:47,300 --> 00:08:49,420
Dhe unë kam formatuar atë si
pastër si unë mund.

206
00:08:49,420 --> 00:08:52,240
Nëse përdoruesi lloje në njërën, që do të thotë
ata duan për të fshirë diçka.

207
00:08:52,240 --> 00:08:54,560
Nëse përdorues në dy lloje, që do të thotë
ata duan për të futur diçka.

208
00:08:54,560 --> 00:08:55,930
Dhe kështu me radhë.

209
00:08:55,930 --> 00:08:58,270
Unë jam duke shkuar për të pastaj të menjëhershëm
pastaj për një komandë.

210
00:08:58,270 --> 00:08:59,300
Dhe atëherë unë jam duke shkuar për të përdorur GetInt.

211
00:08:59,300 --> 00:09:02,790
>> Pra, kjo është një të vërtetë të thjeshtë menuing
kryesh ku ju vetëm duhet të shkruani

212
00:09:02,790 --> 00:09:05,270
një hartë me një numër
e këtyre komandave.

213
00:09:05,270 --> 00:09:08,730
Dhe tani kam një kaloni bukur të pastër
deklaratë që do të kaloni në

214
00:09:08,730 --> 00:09:10,090
çfarëdo përdoruesi typed in

215
00:09:10,090 --> 00:09:12,180
Dhe nëse ata shtypen një, unë do
telefononi fshini dhe pushim.

216
00:09:12,180 --> 00:09:14,380
Nëse ata shtypen dy, unë do të
telefononi futur dhe pushim.

217
00:09:14,380 --> 00:09:16,490
>> Dhe Tani vini re unë kam vënë çdo
nga këto në të njëjtën linjë.

218
00:09:16,490 --> 00:09:18,360
Kjo është vetëm një vendim stilistik.

219
00:09:18,360 --> 00:09:20,210
Zakonisht ne kemi parë diçka të
si kjo.

220
00:09:20,210 --> 00:09:23,260
Por unë thjesht vendosi, sinqerisht, programin tim
dukej më i lexueshëm për shkak

221
00:09:23,260 --> 00:09:25,980
ajo ishte vetëm katër raste për të
vetëm lista atë si kjo.

222
00:09:25,980 --> 00:09:28,360
Përdorimi Krejtësisht legjitime e stilit.

223
00:09:28,360 --> 00:09:31,480
Dhe unë jam duke shkuar për të bërë këtë për aq kohë sa
përdoruesi nuk ka shtypur zero, të cilat unë

224
00:09:31,480 --> 00:09:33,910
vendosur do të thotë se ata duan të lënë.

225
00:09:33,910 --> 00:09:36,630
>> Deri tani njoftim se çfarë unë jam
duke shkuar për të bërë këtu.

226
00:09:36,630 --> 00:09:38,650
Unë jam duke shkuar për të liruar listën me sa duket.

227
00:09:38,650 --> 00:09:40,230
Por më shumë se në një moment të vetëm.

228
00:09:40,230 --> 00:09:41,640
Le të parë të drejtuar këtë program.

229
00:09:41,640 --> 00:09:45,250
Pra më lejoni të bëjë një terminal të madhe
dritare, dot lista slash 0.

230
00:09:45,250 --> 00:09:49,510
Unë jam duke shkuar për të shkuar përpara dhe të futur nga
typing dy, një numër si 50, dhe tani

231
00:09:49,510 --> 00:09:51,590
ju do të shihni listë është tani 50.

232
00:09:51,590 --> 00:09:53,380
Dhe teksti time vetëm scrolled deri pak.

233
00:09:53,380 --> 00:09:55,940
Deri tani njoftim listë përmban
numër 50.

234
00:09:55,940 --> 00:09:58,220
>> Le të bëni një tjetër insert duke marrë dy.

235
00:09:58,220 --> 00:10:01,630
Le të shkruani në numrin si një.

236
00:10:01,630 --> 00:10:03,940
Lista e tani është një, e ndjekur nga 50.

237
00:10:03,940 --> 00:10:06,020
Pra, kjo është vetëm një përfaqësim tekstuale
nga lista.

238
00:10:06,020 --> 00:10:10,550
Dhe le të futni numrin një më shumë si
numër 42, e cila është shpresë

239
00:10:10,550 --> 00:10:14,620
do të përfundojë deri në mes, sepse
ky program në terezi ajo veçanta

240
00:10:14,620 --> 00:10:16,320
elemente si ajo fut ato.

241
00:10:16,320 --> 00:10:17,220
Kështu që nuk kemi atë.

242
00:10:17,220 --> 00:10:20,730
Super program i thjeshtë që mund të
absolutisht kanë përdorur një rrjet, por unë

243
00:10:20,730 --> 00:10:23,280
ndodhë të jetë duke përdorur një listë të lidhur
vetëm kështu unë mund të dinamike

244
00:10:23,280 --> 00:10:24,610
rritet dhe tkurret atë.

245
00:10:24,610 --> 00:10:28,470
>> Pra, le të marrin një vështrim për kërkimin, në qoftë se unë
drejtuar komandën tre, unë dua për të kërkuar

246
00:10:28,470 --> 00:10:31,040
për, të themi, me numrin 43.

247
00:10:31,040 --> 00:10:34,190
Dhe asgjë nuk u gjet me sa duket,
sepse unë kam kthyer asnjë përgjigje.

248
00:10:34,190 --> 00:10:35,010
Pra, le ta bëjmë këtë përsëri.

249
00:10:35,010 --> 00:10:35,690
Kërko.

250
00:10:35,690 --> 00:10:39,520
Kërko për 50 Le të, ose në vend të kërkoni
per 42, i cili ka nje mirë

251
00:10:39,520 --> 00:10:40,850
Kuptimi pak delikate.

252
00:10:40,850 --> 00:10:42,610
Dhe kam gjetur kuptimin e jetës atje.

253
00:10:42,610 --> 00:10:44,990
Numri 42, në qoftë se ju nuk e dini
referenca, Google atë.

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

255
00:10:45,350 --> 00:10:47,130
Pra, çfarë e ka këtë program bërë për mua?

256
00:10:47,130 --> 00:10:50,660
Ajo është e lejuar vetëm mua për të futur kështu
larg dhe kërkimit të elementeve.

257
00:10:50,660 --> 00:10:53,650
>> Le të shpejtë përpara, pastaj, për të
se funksioni ne lëshoi ​​në

258
00:10:53,650 --> 00:10:55,360
hënën si një ngacmues.

259
00:10:55,360 --> 00:10:59,620
Pra këtë funksion, unë pretendojnë, kërkimet për
një element në lista duke parë

260
00:10:59,620 --> 00:11:03,830
një, duke bërë që përdoruesit dhe pastaj duke e quajtur
GetInt për të marrë një int aktuale

261
00:11:03,830 --> 00:11:05,060
që ju doni të kërkoni për të.

262
00:11:05,060 --> 00:11:06,460
>> Pastaj këtë njoftim.

263
00:11:06,460 --> 00:11:10,690
Unë jam duke shkuar për të krijuar një ndryshore të përkohshme
në përputhje quajtur 188 pointer -

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

265
00:11:11,270 --> 00:11:12,440
mund të ketë e quajti atë gjë.

266
00:11:12,440 --> 00:11:16,140
Dhe kjo është një tregues për një nyje
sepse unë thashë: * nyje atje.

267
00:11:16,140 --> 00:11:19,900
Dhe unë jam Initializing që ajo të jetë e barabartë me
parë në mënyrë që unë efektivisht kanë mia

268
00:11:19,900 --> 00:11:22,860
gisht, kështu që të flasin, më shumë
elementi i parë i lista.

269
00:11:22,860 --> 00:11:27,460
Pra, në qoftë se dora ime e djathtë këtu është PTR unë jam
duke treguar në të njëjtën gjë që së pari

270
00:11:27,460 --> 00:11:28,670
është vënë në.

271
00:11:28,670 --> 00:11:31,430
>> Pra, tani është kthyer në kod,
çfarë ndodh ardhshëm -

272
00:11:31,430 --> 00:11:35,070
kjo është një paradigmë e zakonshme kur iterating
mbi një strukturë si një

273
00:11:35,070 --> 00:11:35,970
lista e lidhura.

274
00:11:35,970 --> 00:11:40,410
Unë jam duke shkuar për të bërë në vijim, ndërsa
akrep nuk është e barabartë me null Kështu, ndërsa

275
00:11:40,410 --> 00:11:47,530
Gishti im nuk është treguar në disa null
vlera, nëse akrep shigjeta n barabartë me n.

276
00:11:47,530 --> 00:11:52,290
Ne do të vëreni parë që është ajo n
përdorues shtypen në GetInts për të thirrur këtu.

277
00:11:52,290 --> 00:11:54,280
>> Dhe akrep shigjeta n do të thotë çfarë?

278
00:11:54,280 --> 00:11:59,020
E pra, nëse ne do të shkojmë përsëri në foto këtu,
në qoftë se unë kam një gisht duke treguar në

279
00:11:59,020 --> 00:12:02,960
se nyja e parë që përmban nëntë, e
shigjetë në thelb do të thotë se të shkojnë në

280
00:12:02,960 --> 00:12:08,860
Nyja dhe kap vlerën në lokacionin n,
në këtë rast, fusha të dhënave të quajtur n.

281
00:12:08,860 --> 00:12:14,120
>> Si një mënjanë - dhe ne e pamë këtë çift një
javë më parë, kur dikush e pyeti -

282
00:12:14,120 --> 00:12:18,840
kjo Sintaksa është e re, por kjo nuk e bën
na japin kompetenca që ne

283
00:12:18,840 --> 00:12:20,040
nuk ka tashmë kanë.

284
00:12:20,040 --> 00:12:25,325
Cila ishte kjo frazë e barabartë për të përdorur
dot simbol yll dhe një çift

285
00:12:25,325 --> 00:12:29,490
javë më parë, kur ne peeled mbrapa
kjo shtresë pak kohe?

286
00:12:29,490 --> 00:12:31,780
>> STUDENT: [padëgjueshme].

287
00:12:31,780 --> 00:12:38,880
>> Kryetari 1: Pikërisht, ajo ishte ylli, dhe
atëherë ajo ishte yll dot n, me

288
00:12:38,880 --> 00:12:41,930
kllapat këtu, e cila duket,
sinqerisht, unë mendoj se një shumë

289
00:12:41,930 --> 00:12:43,320
më të fshehtë për të lexuar.

290
00:12:43,320 --> 00:12:46,270
Por pointer yll, si gjithmonë,
do të thotë të shkojnë atje.

291
00:12:46,270 --> 00:12:49,090
Dhe një herë ju jeni atje, çfarë të dhëna
fushë nuk ju duan të hyni?

292
00:12:49,090 --> 00:12:52,730
E pra ju përdorni për të hyrë në simbol dot
një structs dhënat fushë, dhe unë

293
00:12:52,730 --> 00:12:54,140
veçanërisht dua n.

294
00:12:54,140 --> 00:12:56,240
>> Sinqerisht, unë do të argumentojnë këtë
është vetëm e vështirë për të lexuar.

295
00:12:56,240 --> 00:12:58,080
Është e vështirë për të kujtuar ku
bëni kllapat shkojnë,

296
00:12:58,080 --> 00:12:59,030
ylli dhe të gjithë se.

297
00:12:59,030 --> 00:13:02,150
Pra bota miratuar disa sintaktik
sheqer, mënyrë që të flasin.

298
00:13:02,150 --> 00:13:04,740
Vetëm një mënyrë për të thënë sexy,
kjo është ekuivalente, dhe

299
00:13:04,740 --> 00:13:05,970
ndoshta më shumë intuitiv.

300
00:13:05,970 --> 00:13:09,600
Në qoftë se është me të vërtetë një akrep akrep,
Mjetet simbol shigjetë shkoni atje dhe për të gjetur

301
00:13:09,600 --> 00:13:11,890
fushë në këtë rast quhet n.

302
00:13:11,890 --> 00:13:13,660
>> Pra, nëse unë gjej atë, njoftim se çfarë bëj unë.

303
00:13:13,660 --> 00:13:17,430
Unë thjesht të shtypura jashtë, unë kam gjetur për qind,
mbylljen në vlerë për atë int.

304
00:13:17,430 --> 00:13:20,730
Unë e quaj fle për një të dytë vetëm për të llojit
i gjërave pauzë në ekran për të

305
00:13:20,730 --> 00:13:22,900
dhënë përdoruesit një të dytë për të absorbuar
çfarë ka ndodhur vetëm.

306
00:13:22,900 --> 00:13:24,290
Dhe pastaj kam thyer.

307
00:13:24,290 --> 00:13:26,330
Përndryshe, çfarë të bëj?

308
00:13:26,330 --> 00:13:30,960
I update pointer të barabartë
shigjetë pointer ardhshëm.

309
00:13:30,960 --> 00:13:35,840
>> Pra, vetëm të jetë i qartë, kjo do të thotë të shkojnë
atje, duke përdorur simbol i vjetër-shkollën time.

310
00:13:35,840 --> 00:13:39,580
Pra, kjo do të thotë vetëm për të shkuar në çfarëdo
ju jeni duke treguar, e cila në shumë

311
00:13:39,580 --> 00:13:43,660
Rasti i parë është që unë jam vënë në
struct me nëntë në të.

312
00:13:43,660 --> 00:13:44,510
Kështu që unë kam shkuar atje.

313
00:13:44,510 --> 00:13:47,880
Dhe pastaj dot simbol do të thotë,
marrë në vlerën e ardhshëm.

314
00:13:47,880 --> 00:13:50,470
>> Por vlera, edhe pse ajo është tërhequr
si një të ngushtë, është vetëm një numër.

315
00:13:50,470 --> 00:13:51,720
Kjo është një adresë numerike.

316
00:13:51,720 --> 00:13:55,670
Pra, kjo një linjë e kodit, nëse
shkruar si kjo, më e fshehtë

317
00:13:55,670 --> 00:14:00,190
mënyra, ose si kjo, pak më shumë
mënyrë intuitive, thjesht do të thotë të lëvizë dorën time

318
00:14:00,190 --> 00:14:03,460
nga e nyjes së parë me një tjetër,
dhe pastaj një tjetër, dhe pastaj

319
00:14:03,460 --> 00:14:05,320
një tjetër, dhe kështu me radhë.

320
00:14:05,320 --> 00:14:09,920
>> Pra, ne nuk do të banojë në tjetrin
Implementimi i futur dhe fshini

321
00:14:09,920 --> 00:14:14,030
dhe traversal, dy të parë të
të cilat janë të përfshira në mënyrë të drejtë.

322
00:14:14,030 --> 00:14:17,010
Dhe unë mendoj se është mjaft e lehtë për të marrë
kur humbi bërë atë verbalisht.

323
00:14:17,010 --> 00:14:19,890
Por çfarë mund të bëjmë këtu është
përpiqen për të përcaktuar se si

324
00:14:19,890 --> 00:14:21,640
mirë për të bërë këtë visually.

325
00:14:21,640 --> 00:14:24,800
Sepse unë do të propozojë që në qoftë se ne
doni të futur elemente në këtë

326
00:14:24,800 --> 00:14:26,680
listë ekzistuese, e cila
ka pesë elemente -

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

328
00:14:29,530 --> 00:14:33,300
në qoftë se unë ishin duke shkuar për të zbatuar këtë në
Kodi, kam nevojë të marrin në konsideratë se si të shkojë

329
00:14:33,300 --> 00:14:34,160
për ta bërë këtë.

330
00:14:34,160 --> 00:14:37,720
>> Dhe unë do të propozojë marrjen hapa të fëmijës
ku, në këtë rast unë do të thotë, se çfarë janë

331
00:14:37,720 --> 00:14:41,090
skenarët e mundshme që ne
mund të hasni në përgjithësi?

332
00:14:41,090 --> 00:14:44,120
Kur zbatimin insert për një linked
listë, kjo thjesht ndodh të jetë një

333
00:14:44,120 --> 00:14:46,090
shembull specifik i madhësisë pesë.

334
00:14:46,090 --> 00:14:50,420
E pra në qoftë se ju doni të futur një numër,
si thonë numrin një, dhe

335
00:14:50,420 --> 00:14:53,380
mbajtjen e rendit të renditura, ku
padyshim bën numër një nevojë për të

336
00:14:53,380 --> 00:14:55,686
shkoni në këtë shembull të veçantë?

337
00:14:55,686 --> 00:14:56,840
Ashtu si në fillim.

338
00:14:56,840 --> 00:15:00,030
>> Por ajo që është interesante është se ka
në qoftë se ju doni të futur një në këtë

339
00:15:00,030 --> 00:15:04,100
listë, çfarë akrep veçantë duhet
të freskohen me sa duket?

340
00:15:04,100 --> 00:15:04,610
Së pari.

341
00:15:04,610 --> 00:15:07,830
Kështu që unë do të argumentojnë, ky është rasti i parë
që ne mund të dëshirojnë të marrin në konsideratë, një

342
00:15:07,830 --> 00:15:11,140
skenar që përfshin futur në
fillimi i lista.

343
00:15:11,140 --> 00:15:15,400
>> Le të hiqni ndoshta një aq e lehtë apo edhe
Rasti lehtë, relativisht të folur.

344
00:15:15,400 --> 00:15:18,110
Supozoni se unë dua të futur
Numri 35 në mënyrë renditura.

345
00:15:18,110 --> 00:15:20,600
Ajo padyshim i takon atje.

346
00:15:20,600 --> 00:15:25,320
Pra, çfarë akrep padyshim do të
duhet të jenë të përditësuar në këtë skenar?

347
00:15:25,320 --> 00:15:30,060
Akrep 34 e duke u bërë jo null
por adresa e struct

348
00:15:30,060 --> 00:15:31,800
përmbajnë numrin 35.

349
00:15:31,800 --> 00:15:32,750
Pra, kjo është rasti dy.

350
00:15:32,750 --> 00:15:36,190
Pra tashmë, unë jam lloj i quantizing
se sa shumë punë duhet të bëj këtu.

351
00:15:36,190 --> 00:15:39,880
>> Dhe së fundi, çështja e mesme është e qartë
në të vërtetë, në mes, në qoftë se unë dua të

352
00:15:39,880 --> 00:15:45,870
futur diçka si thonë 23, që shkon
në mes të 23 dhe 26, por

353
00:15:45,870 --> 00:15:48,680
tani gjërat merrni pak më shumë
përfshirë për shkak se çfarë

354
00:15:48,680 --> 00:15:52,800
pointers duhet të ndryshohet?

355
00:15:52,800 --> 00:15:56,680
22 Pra, padyshim duhet të ndryshohet
sepse ai nuk mund të tregojnë për 26 anymore.

356
00:15:56,680 --> 00:16:00,320
Ai ka nevojë për pikë në nyjen e re që
Unë do të duhet të ndajë duke telefonuar

357
00:16:00,320 --> 00:16:01,770
malloc ose disa ekuivalent.

358
00:16:01,770 --> 00:16:05,990
>> Por atëherë unë gjithashtu duhet se Nyja e re, 23
në këtë rast, që të ketë treguesin e saj

359
00:16:05,990 --> 00:16:07,870
duke vënë në kë?

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

361
00:16:08,560 --> 00:16:10,380
Dhe atje do të jetë një
Urdhri i operacioneve këtu.

362
00:16:10,380 --> 00:16:13,410
Sepse në qoftë se unë bëj këtë si një budalla dhe kam
për fillimin e shkallës në fillim të

363
00:16:13,410 --> 00:16:16,040
lista, dhe qëllimi im është për të futur 23.

364
00:16:16,040 --> 00:16:18,610
Dhe unë kontrolloni, ajo nuk i përkasin
këtu, afër nëntë?

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

366
00:16:18,950 --> 00:16:20,670
A është i përkasin këtu, pranë 17?

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

368
00:16:20,940 --> 00:16:22,530
A ajo i takon këtu ardhshme për 22?

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

370
00:16:23,300 --> 00:16:26,400
>> Tani, nëse unë jam budalla këtu, dhe nuk
duke menduar këtë anë, unë mund

371
00:16:26,400 --> 00:16:28,320
ndajë nyje tim të ri për 23.

372
00:16:28,320 --> 00:16:32,080
Unë mund të rinovuar në treguesin nga
nyjen quajtur 22, duke treguar

373
00:16:32,080 --> 00:16:33,080
ajo në nyjen e re.

374
00:16:33,080 --> 00:16:36,140
Dhe pastaj çfarë kam për të rinovuar
akrep nyjen e ri të jetë?

375
00:16:36,140 --> 00:16:38,120
>> STUDENT: [padëgjueshme].

376
00:16:38,120 --> 00:16:38,385
>> Kryetari 1: Pikërisht.

377
00:16:38,385 --> 00:16:39,710
Duke treguar në 26.

378
00:16:39,710 --> 00:16:45,590
Por dammit qoftë se unë nuk tashmë të rinovuar
Akrep 22 për pikë në këtë djalë, dhe

379
00:16:45,590 --> 00:16:48,260
tani kam jetimëve, pjesa tjetër
i listës, kështu që të flasin.

380
00:16:48,260 --> 00:16:52,140
Pra, rendi i operacioneve këtu
do të jetë e rëndësishme.

381
00:16:52,140 --> 00:16:55,100
>> Për ta bërë këtë mund ta vjedhin,
thonë, gjashtë vullnetarë.

382
00:16:55,100 --> 00:16:57,650
Dhe le të shohim nëse ne nuk mund ta bëjmë këtë
vizualisht në vend të kodit-mençur.

383
00:16:57,650 --> 00:16:59,330
Dhe ne kemi disa stres bukuroshe
topa për ju sot.

384
00:16:59,330 --> 00:17:02,510
Rregull, si rreth një, dy, ne
back - në fund atje.

385
00:17:02,510 --> 00:17:04,530
tre, katër, dy prej jush
djemtë në fund.

386
00:17:04,530 --> 00:17:05,579
Dhe pesë, gjashtë.

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

388
00:17:05,839 --> 00:17:06,450
Pesë dhe gjashtë.

389
00:17:06,450 --> 00:17:08,390
Të gjithë të drejtë dhe ne do të vijnë
për ju djema herën tjetër.

390
00:17:08,390 --> 00:17:09,640
Të gjithë të drejtë, vijnë më lart.

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

392
00:17:12,010 --> 00:17:14,819
>> Të gjithë të drejtë, pasi ju jeni këtu të parë,
do të ju pëlqen të jetë një dyluftimi në ajër

393
00:17:14,819 --> 00:17:16,119
në xham Google këtu?

394
00:17:16,119 --> 00:17:19,075
Të gjithë të drejtë, kështu që, OK, qelqi,
regjistroni një video.

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

396
00:17:22,720 --> 00:17:24,589
Ok, ju jeni të mirë për të shkuar.

397
00:17:24,589 --> 00:17:27,950
>> Të gjithë të drejtë, kështu që nëse ju djema mund të vijnë gjatë
këtu, unë kam përgatitur paraprakisht

398
00:17:27,950 --> 00:17:30,110
disa numra.

399
00:17:30,110 --> 00:17:31,240
Të gjithë të drejtë, eja mbi këtu.

400
00:17:31,240 --> 00:17:33,440
Dhe pse nuk shkoni pak
më tej në këtë mënyrë.

401
00:17:33,440 --> 00:17:35,520
Dhe le të shohim, çfarë është emri juaj,
Glass me Google?

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

403
00:17:35,910 --> 00:17:36,230
>> Kryetari 1: Ben?

404
00:17:36,230 --> 00:17:38,380
OK, Ben, ju do të jetë i pari, fjalë për fjalë.

405
00:17:38,380 --> 00:17:40,580
Pra, ne jemi duke shkuar për të ju dërgojnë
deri në fund të fazës.

406
00:17:40,580 --> 00:17:41,670
? Gjithë të drejtë, dhe emri juaj

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

408
00:17:41,990 --> 00:17:44,530
>> Kryetari 1: Jason, OK ju do të
të jetë numër nëntë.

409
00:17:44,530 --> 00:17:46,700
Pra, nëse ju doni të ndiqni rrugën e ben atë.

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

411
00:17:47,010 --> 00:17:49,630
>> Kryetari 1: Jill, ju jeni do të jetë
17, e cila në qoftë se unë do të bëhet kjo më shumë

412
00:17:49,630 --> 00:17:51,260
inteligjente, unë do të ketë
filloi në fund të tjera.

413
00:17:51,260 --> 00:17:52,370
Ju shkoni në këtë mënyrë.

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

415
00:17:53,030 --> 00:17:53,670
Dhe ju jeni?

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

417
00:17:53,980 --> 00:17:56,130
>> Kryetari 1: Mary, ju do të jetë 22.

418
00:17:56,130 --> 00:17:58,420
Dhe emri juaj është?

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

420
00:17:58,810 --> 00:18:00,100
>> Kryetari 1: Chris, ju do të jetë 26.

421
00:18:00,100 --> 00:18:00,740
Dhe pastaj së fundi.

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

423
00:18:01,400 --> 00:18:02,670
>> Kryetari 1: Diana, ju do të jetë 34.

424
00:18:02,670 --> 00:18:03,920
Kështu që ju vijnë më gjatë këtu.

425
00:18:03,920 --> 00:18:06,360
>> Të gjithë të drejtë, të renditura në mënyrë të përsosur
urdhërojë tashmë.

426
00:18:06,360 --> 00:18:09,600
Dhe le të shkojë përpara dhe të bëjë këtë
kështu që ne mund të vërtetë -

427
00:18:09,600 --> 00:18:11,720
Ben ju jeni vetëm në kërkim të lloj
jashtë në askund atje.

428
00:18:11,720 --> 00:18:15,670
OK, kështu që le të shkojnë përpara dhe të përshkruaj këtë
përdorimin e armëve, ashtu si unë ishte pikërisht,,

429
00:18:15,670 --> 00:18:16,250
çfarë po ndodh.

430
00:18:16,250 --> 00:18:19,540
Pra shkoni përpara dhe të japë vetes një
këmbë ose dy në mes vete.

431
00:18:19,540 --> 00:18:22,900
Dhe të shkojnë përpara dhe pikë me një dorë të
kushdo që ju duhet të vënë në

432
00:18:22,900 --> 00:18:23,470
bazuar në këtë.

433
00:18:23,470 --> 00:18:25,890
Dhe në qoftë se ju jeni vetëm pika null
drejt poshtë në dysheme.

434
00:18:25,890 --> 00:18:27,690
OK, në mënyrë të mirë.

435
00:18:27,690 --> 00:18:32,290
>> Pra, tani ne kemi një listë të lidhura, dhe më lejoni
propozojë që unë do të luajnë rolin e

436
00:18:32,290 --> 00:18:35,110
PTR, kështu që unë nuk do të shqetësojë
mbante këtë rreth.

437
00:18:35,110 --> 00:18:37,830
Dhe pastaj - Konventa dikush budalla -
ju mund të telefononi këtë gjë që ju dëshironi -

438
00:18:37,830 --> 00:18:39,800
Paraardhësi akrep, akrep pred -

439
00:18:39,800 --> 00:18:43,930
kjo është vetëm Mbyll kemi dhënë në
Kodi tonë mostër në dorën time të majtë.

440
00:18:43,930 --> 00:18:47,240
Dora tjetër që do të jetë mbajtur
gjurmët e kush është kush në

441
00:18:47,240 --> 00:18:48,400
pas skenarë.

442
00:18:48,400 --> 00:18:52,390
>> Pra, mendoj, së pari, unë dua të këpus off
se shembulli i parë i futur, thonë

443
00:18:52,390 --> 00:18:54,330
20 në listë.

444
00:18:54,330 --> 00:18:57,160
Kështu që unë jam duke shkuar për nevojë për dikë që
mishërojnë numrin 20 për ne.

445
00:18:57,160 --> 00:18:58,950
Kështu që kam nevojë për dikë malloc
nga audienca.

446
00:18:58,950 --> 00:18:59,380
Come on up.

447
00:18:59,380 --> 00:19:00,340
Cili është emri juaj?

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

449
00:19:01,300 --> 00:19:05,270
>> Kryetari 1: Brian, të gjithë të drejtë, kështu që ju
do të jetë nyja që përmbajnë 20.

450
00:19:05,270 --> 00:19:06,810
Të gjithë të drejtë, eja mbi këtu.

451
00:19:06,810 --> 00:19:10,025
Dhe natyrisht, ku
Brian nuk i përkasin?

452
00:19:10,025 --> 00:19:12,190
Kështu, ne mes te - vërtetë,
prisni një minutë.

453
00:19:12,190 --> 00:19:13,420
Ne jemi duke e bërë këtë nga e rendit.

454
00:19:13,420 --> 00:19:17,170
Ne jemi duke e bërë këtë një shumë e vështirë
sesa ajo ka nevojë të jetë në të parë.

455
00:19:17,170 --> 00:19:21,210
OK, ne jemi duke shkuar për të lirë Brian
dhe realloc Brian si pesë.

456
00:19:21,210 --> 00:19:23,680
>> OK, kështu që tani që ne duam të futur
Brian si pesë.

457
00:19:23,680 --> 00:19:25,960
Pra, të vijë në mbi këtu ardhshëm për
Ben për vetëm një moment.

458
00:19:25,960 --> 00:19:28,250
Dhe ju mund të tregoni sa duket
ku kjo histori është e shkuar.

459
00:19:28,250 --> 00:19:30,500
Por le të mendoni me kujdes për
Urdhri i operacioneve.

460
00:19:30,500 --> 00:19:32,880
Dhe kjo është pikërisht kjo vizuale
që do të vijë deri

461
00:19:32,880 --> 00:19:34,080
me atë kod mostër.

462
00:19:34,080 --> 00:19:40,120
Kështu që këtu unë kam treguar fillimisht PTR
jo me Ben, në vetvete, por në çfarëdo

463
00:19:40,120 --> 00:19:43,245
ai përmban vlera, e cila në këtë rast
është - çfarë është emri juaj përsëri?

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

465
00:19:43,670 --> 00:19:47,350
>> Kryetari 1: Jason, kështu që të dy Ben dhe unë jemi
duke vënë në Jason në këtë moment.

466
00:19:47,350 --> 00:19:49,700
Deri tani unë kam për të përcaktuar,
ku do Brian përkasin?

467
00:19:49,700 --> 00:19:53,500
Pra, e vetmja gjë që unë kam qasje në
tani është n e tij dhënave artikull.

468
00:19:53,500 --> 00:19:58,280
Kështu që unë jam duke shkuar për të kontrolluar, është e
Brian pak se Jason?

469
00:19:58,280 --> 00:19:59,770
Përgjigja është e vërtetë.

470
00:19:59,770 --> 00:20:03,680
>> Pra, çfarë duhet të ndodhë tani,
në mënyrë korrekte?

471
00:20:03,680 --> 00:20:07,120
Unë kam nevojë për të rinovuar sa pointers
në total në këtë histori?

472
00:20:07,120 --> 00:20:10,720
Ku dora ime është ende duke treguar në
Jason, dhe dora jote - në qoftë se ju doni të

473
00:20:10,720 --> 00:20:12,930
vëre dorën tënde si, lloj, unë
nuk e di, një pikëpyetje.

474
00:20:12,930 --> 00:20:14,070
OK, i mirë.

475
00:20:14,070 --> 00:20:15,670
>> Të gjithë të drejtë, kështu që ju keni
disa kandidatë.

476
00:20:15,670 --> 00:20:20,500
Ose ben ose unë ose Brian apo Jason
ose secili tjetër, e cila

477
00:20:20,500 --> 00:20:21,370
pointers duhet të ndryshojë?

478
00:20:21,370 --> 00:20:23,260
Sa në total?

479
00:20:23,260 --> 00:20:24,080
>> OK, kështu që dy.

480
00:20:24,080 --> 00:20:27,090
Akrep ime nuk ka të vërtetë rëndësi më
sepse unë jam vetëm i përkohshëm.

481
00:20:27,090 --> 00:20:31,370
Pra, kjo është këto dy guys, me sa duket,
Ben si dhe Brian.

482
00:20:31,370 --> 00:20:34,410
Pra më lejoni të propozojnë që ne update
Ben, pasi ai është i pari.

483
00:20:34,410 --> 00:20:36,350
Elementi i parë i kësaj liste
tani do të jetë Brian.

484
00:20:36,350 --> 00:20:38,070
Pra, pika e ben at Brian.

485
00:20:38,070 --> 00:20:39,320
OK, tani çka?

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

487
00:20:41,950 --> 00:20:43,460
>> Kush merr vuri në kë?

488
00:20:43,460 --> 00:20:44,710
>> STUDENT: [padëgjueshme].

489
00:20:44,710 --> 00:20:46,180
>> Kryetari 1: OK kështu Brian ka
për pikë në Jason.

490
00:20:46,180 --> 00:20:48,360
Por kam humbur gjurmët e asaj akrep?

491
00:20:48,360 --> 00:20:49,980
A e di se ku Jason është?

492
00:20:49,980 --> 00:20:50,790
>> STUDENT: [padëgjueshme].

493
00:20:50,790 --> 00:20:52,620
>> Kryetari 1: bëj, pasi që unë jam
pointer përkohshme.

494
00:20:52,620 --> 00:20:55,110
Dhe me sa duket, unë nuk kanë ndryshuar
për pikë në nyjen e re.

495
00:20:55,110 --> 00:20:58,300
Pra, ne thjesht mund të ketë pikë Brian
në kushdo që unë jam vënë në.

496
00:20:58,300 --> 00:20:59,000
Dhe ne jemi duke bërë.

497
00:20:59,000 --> 00:21:01,890
Pra një rast, futje në
fillim të listës.

498
00:21:01,890 --> 00:21:02,950
Kishte dy hapa kyçe.

499
00:21:02,950 --> 00:21:06,750
Një, ne kemi për të rinovuar Ben, dhe pastaj
ne gjithashtu kemi Brian për të rinovuar.

500
00:21:06,750 --> 00:21:09,230
Dhe atëherë unë nuk duhet të shqetësojë
traipsing nëpër pjesën tjetër të

501
00:21:09,230 --> 00:21:12,680
listë, sepse ne tashmë gjetur rrugën e tij
vend, sepse ai i përkiste

502
00:21:12,680 --> 00:21:14,080
la e elementit të parë.

503
00:21:14,080 --> 00:21:15,400
>> Të gjithë të drejtë, kështu që shumë i thjeshtë.

504
00:21:15,400 --> 00:21:18,110
Në fakt, ndihet si ne jemi gati
duke e bërë këtë shumë e komplikuar.

505
00:21:18,110 --> 00:21:20,240
Pra, le të tani nxirre jashtë fundin
i listës, dhe shiko ku

506
00:21:20,240 --> 00:21:21,380
Kompleksiteti fillon.

507
00:21:21,380 --> 00:21:24,560
Pra, në qoftë se tani unë shenjat e nga publiku.

508
00:21:24,560 --> 00:21:25,540
Çdokush duan të luajnë 55?

509
00:21:25,540 --> 00:21:26,700
Të gjithë të drejtë, unë pashë dorën tuaj të parë.

510
00:21:26,700 --> 00:21:29,620
Come on up.

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

512
00:21:30,030 --> 00:21:31,177
Cili është emri juaj?

513
00:21:31,177 --> 00:21:32,310
>> STUDENT: [padëgjueshme].

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

515
00:21:33,240 --> 00:21:33,890
OK, eja lart.

516
00:21:33,890 --> 00:21:35,730
Ju do të jetë numër 55.

517
00:21:35,730 --> 00:21:37,820
Pra, ju, natyrisht, i përkasin
ne fund te lista.

518
00:21:37,820 --> 00:21:41,850
Pra, le sërish simulimin me mua
duke qenë PTR për vetëm një moment.

519
00:21:41,850 --> 00:21:44,050
Kështu që unë jam duke shkuar për të parë pikë në
çfarëdo Ben është vënë në.

520
00:21:44,050 --> 00:21:45,900
Ne jemi të dy vënë tani në Brian.

521
00:21:45,900 --> 00:21:48,420
Pra, 55 është jo më pak se pesë.

522
00:21:48,420 --> 00:21:52,510
Kështu që unë jam duke shkuar për të rinovuar veten nga
duke treguar për treguesin e ardhshëm Brian, i cili

523
00:21:52,510 --> 00:21:54,450
tani është sigurisht Jason.

524
00:21:54,450 --> 00:21:57,310
55 A nuk është më pak se nëntë, në mënyrë
Unë jam duke shkuar për të rinovuar ptr.

525
00:21:57,310 --> 00:21:58,890
Unë jam duke shkuar për të rinovuar ptr.

526
00:21:58,890 --> 00:22:02,290
Unë jam duke shkuar për të rinovuar ptr
Unë do të rinovuar ptr.

527
00:22:02,290 --> 00:22:05,060
Dhe unë jam duke shkuar për - hmm, çfarë është
emri juaj përsëri?

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

529
00:22:05,560 --> 00:22:09,190
>> Kryetari 1: Diana është vënë, natyrisht,
at null me dorën e saj të majtë.

530
00:22:09,190 --> 00:22:13,030
Pra, ku e bën në fakt Habata
i përkasin në mënyrë të qartë?

531
00:22:13,030 --> 00:22:15,050
Në të majtë, këtu.

532
00:22:15,050 --> 00:22:19,460
Pra, si mund ta di për të vënë e saj këtu
Unë mendoj se kam dehur.

533
00:22:19,460 --> 00:22:22,420
Sepse ajo është PTR art
ky moment në kohë?

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

535
00:22:23,240 --> 00:22:25,580
Pra, edhe pse, vizualisht, ne mund të
padyshim shohim të gjitha këto

536
00:22:25,580 --> 00:22:26,610
djema këtu në skenë.

537
00:22:26,610 --> 00:22:29,680
Unë nuk kam mbajtur gjurmët e mëparshme
person në listë.

538
00:22:29,680 --> 00:22:33,210
Unë nuk kam një gisht duke treguar jashtë,
në këtë rast, numri 34 nyje.

539
00:22:33,210 --> 00:22:34,760
>> Pra, le të vërtetë të fillojë mbi këtë.

540
00:22:34,760 --> 00:22:37,560
Deri tani unë në fakt nuk kanë nevojë për
një variabël e dytë lokal.

541
00:22:37,560 --> 00:22:40,980
Dhe kjo është ajo që ju do të shihni në
Kodi aktuale mostër C, ku si shkoj unë,

542
00:22:40,980 --> 00:22:45,860
kur unë Përditëso dorën e djathtë të pikës
Jason, duke lënë prapa Brian, unë

543
00:22:45,860 --> 00:22:51,440
më mirë të fillojë duke përdorur dorën e majtë për
Përditëso ku isha, në mënyrë që sa të shkoj

544
00:22:51,440 --> 00:22:52,700
nëpërmjet kësaj liste -

545
00:22:52,700 --> 00:22:55,040
më shumë ajër se unë për qëllim
Tani këtu vizualisht -

546
00:22:55,040 --> 00:22:56,740
Unë jam duke shkuar për të marrë në
fundi i lista.

547
00:22:56,740 --> 00:23:00,020
>> Kjo dorë është ende null, e cila është shumë e
padobishme, përveç për të treguar

548
00:23:00,020 --> 00:23:02,980
Unë jam në mënyrë të qartë në fund të listës,
por tani të paktën unë kam këtë

549
00:23:02,980 --> 00:23:08,270
akrep paraardhësi i treguar këtu, kështu që
tani ajo që duart dhe çfarë pointers duhet

550
00:23:08,270 --> 00:23:10,150
të freskohen?

551
00:23:10,150 --> 00:23:13,214
Dorën e të cilit nuk ju duan
për të rikonfiguruar të parë?

552
00:23:13,214 --> 00:23:15,190
>> STUDENT: [padëgjueshme].

553
00:23:15,190 --> 00:23:16,220
>> Kryetari 1: OK, kështu që së Dianës.

554
00:23:16,220 --> 00:23:21,110
Ku ju doni të theksoj
Treguesin e majtë Dianës në?

555
00:23:21,110 --> 00:23:23,620
Në 55, me sa duket, në mënyrë që
ne kemi futur atje.

556
00:23:23,620 --> 00:23:25,560
Dhe ku duhet të shkojnë 55 akrep?

557
00:23:25,560 --> 00:23:27,000
Down, përfaqëson null.

558
00:23:27,000 --> 00:23:28,890
Dhe duart e mia, në këtë pikë, nuk
rëndësi, sepse ata ishin vetëm

559
00:23:28,890 --> 00:23:30,070
ndryshore të përkohshme.

560
00:23:30,070 --> 00:23:31,030
Pra, tani që ne jemi duke bërë.

561
00:23:31,030 --> 00:23:34,650
>> Pra, kompleksiteti shtesë atje - dhe
kjo nuk është se e vështirë për të zbatuar,

562
00:23:34,650 --> 00:23:38,660
por ne kemi nevojë për një ndryshore mesme për të bërë
Sigurohuni që para unë të lëvizin të drejtën time

563
00:23:38,660 --> 00:23:42,140
dorë, unë update vlerën e majtë ime
, dora akrep pred në këtë rast, kështu që

564
00:23:42,140 --> 00:23:45,860
se unë kam një pointer prapa vetes
të mbajnë gjurmët e ku isha.

565
00:23:45,860 --> 00:23:49,360
Tani si një mënjanë, në qoftë se jeni duke menduar këtë
anë, kjo ndjehet si ajo është një

566
00:23:49,360 --> 00:23:51,490
pak i bezdisshëm që të ketë për të mbajtur
gjurmët e këtij dorën e majtë.

567
00:23:51,490 --> 00:23:54,015
>> Çfarë do një tjetër zgjidhje
për këtë problem kanë qene?

568
00:23:54,015 --> 00:23:56,500
Nëse ju mori për të redesign e të dhënave
Struktura ne jemi duke folur

569
00:23:56,500 --> 00:23:59,630
nëpërmjet tani?

570
00:23:59,630 --> 00:24:02,690
Nëse ky lloj i ndjen vetëm pak
i bezdisshëm që të ketë, si, dy pointers

571
00:24:02,690 --> 00:24:08,430
duke shkuar nëpër lista, kush tjetër mund të
kanë, në botën ideale, mirëmbahen

572
00:24:08,430 --> 00:24:10,160
Informacioni që kemi nevojë?

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

574
00:24:11,360 --> 00:24:12,610
>> STUDENT: [padëgjueshme].

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

576
00:24:15,160 --> 00:24:16,150
>> Kryetari 1: Pikërisht.

577
00:24:16,150 --> 00:24:19,130
Drejtë kështu që nuk ka të vërtetë interesante
embrion i një ideje.

578
00:24:19,130 --> 00:24:22,470
Dhe kjo ideja e një akrep mëparshëm,
duke vënë në elementin e mëparshëm.

579
00:24:22,470 --> 00:24:25,580
Çka nëse unë mishëruar vetëm se
brenda të listës vetë?

580
00:24:25,580 --> 00:24:27,810
Dhe kjo do të jetë e vështirë për të parashikoj
kjo pa të gjitha në letër

581
00:24:27,810 --> 00:24:28,830
duke rënë në katin e.

582
00:24:28,830 --> 00:24:31,860
Por mendoj se këta djem përdoret edhe
e duarve të tyre që të ketë një paraardhëse

583
00:24:31,860 --> 00:24:35,950
kursori, dhe një akrep tej, në këtë mënyrë
zbatimin e asaj që ne do të thërrasë një dyfish

584
00:24:35,950 --> 00:24:36,830
lista e lidhura.

585
00:24:36,830 --> 00:24:41,090
Kjo do të lejoni që lloj i Rewind,
shumë më lehtë pa mua,

586
00:24:41,090 --> 00:24:43,800
programues, që ka për të mbajtur
ndjekur dorë -

587
00:24:43,800 --> 00:24:44,980
me të vërtetë dorë -

588
00:24:44,980 --> 00:24:47,280
prej ku kisha qenë më parë
ne lista.

589
00:24:47,280 --> 00:24:48,110
Pra, ne nuk do të bëjë këtë.

590
00:24:48,110 --> 00:24:50,950
Ne do të mbani atë të thjeshtë, sepse kjo është
do të vijnë me një çmim, dy herë më

591
00:24:50,950 --> 00:24:53,450
shumë hapësirë ​​për pointers,
në qoftë se ju doni një të dytë.

592
00:24:53,450 --> 00:24:55,760
Por kjo është me të vërtetë një të përbashkët
Të dhënat Struktura e njohur si një

593
00:24:55,760 --> 00:24:57,410
lidhur dyfish listë.

594
00:24:57,410 --> 00:25:01,310
>> Le të bëjmë shembullin përfundimtare këtu dhe vënë
këta njerëz nga mjerimi e tyre.

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

596
00:25:03,270 --> 00:25:05,320
Come on deri nga atje rresht.

597
00:25:05,320 --> 00:25:06,280
Të gjithë të drejtë, çfarë është emri juaj?

598
00:25:06,280 --> 00:25:07,440
>> STUDENT: [padëgjueshme].

599
00:25:07,440 --> 00:25:07,855
>> Kryetari 1: Na vjen keq?

600
00:25:07,855 --> 00:25:08,480
>> STUDENT: [padëgjueshme].

601
00:25:08,480 --> 00:25:09,410
>> Kryetari 1: Demeron?

602
00:25:09,410 --> 00:25:10,230
OK vijnë më lart.

603
00:25:10,230 --> 00:25:11,910
Ju do të jetë 20.

604
00:25:11,910 --> 00:25:14,720
Ju padyshim do të
përkasin në mes të 17 dhe 22.

605
00:25:14,720 --> 00:25:16,150
Pra më lejoni të mësuar mësimin tim.

606
00:25:16,150 --> 00:25:18,150
Unë jam duke shkuar për të filluar treguesin
duke treguar në Brian.

607
00:25:18,150 --> 00:25:21,190
Dhe unë jam duke shkuar të ketë dorën time të majtë
vetëm update për Brian si unë për të lëvizur

608
00:25:21,190 --> 00:25:23,600
Jason, kontrolluar e bën 20 më pak se nëntë?

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

610
00:25:24,060 --> 00:25:25,430
20 është më pak se 17?

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

612
00:25:25,880 --> 00:25:27,450
20 është më pak se 22?

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

614
00:25:28,440 --> 00:25:34,070
Pra, çfarë pointers ose duart duhet të ndryshojë
ku ata janë treguar tani?

615
00:25:34,070 --> 00:25:37,070
>> Pra, ne mund të bëjmë vënë 17 në 20.

616
00:25:37,070 --> 00:25:37,860
Pra, kjo është në rregull.

617
00:25:37,860 --> 00:25:40,080
Ku duam të theksoj
treguesin tuaj tani?

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

619
00:25:41,330 --> 00:25:45,410
Dhe ne e dimë se ku është 22, përsëri falë
për treguesin tim të përkohshëm.

620
00:25:45,410 --> 00:25:46,760
Pra, ne jemi OK atje.

621
00:25:46,760 --> 00:25:49,440
Pra, për shkak të këtij magazinimit të përkohshëm
Unë kam mbajtur gjurmët e ku të gjithë është.

622
00:25:49,440 --> 00:25:55,055
Dhe tani ju mund të shikimi të shkojnë në ku
ju i përkisni, dhe tani ne kemi nevojë për 1, 2, 3,

623
00:25:55,055 --> 00:25:58,410
4, 5, 6, 7, 8, 9 topa stresi,
dhe një raund i duartrokitje për

624
00:25:58,410 --> 00:25:59,770
këta njerëz, nëse ne mund të.

625
00:25:59,770 --> 00:26:00,410
Nicely done.

626
00:26:00,410 --> 00:26:05,320
>> [Duartrokitje]

627
00:26:05,320 --> 00:26:06,330
>> Kryetari 1: Në rregull.

628
00:26:06,330 --> 00:26:09,860
Dhe ju mund të mbani copa
i letrës si mementos.

629
00:26:09,860 --> 00:26:15,930
>> Të gjithë të drejtë, kështu që, besoni mua kjo është një shumë
më të lehtë të ecin nëpër se me

630
00:26:15,930 --> 00:26:17,680
njerëzit se ajo është me kodin aktual.

631
00:26:17,680 --> 00:26:22,690
Por ajo që ju do të gjeni në një moment të vetëm
tani, është se njëjtë - oh, thank you.

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

633
00:26:23,630 --> 00:26:29,360
është se ju do të gjeni se të njëjtat të dhëna
Struktura, një listë të lidhura, në fakt mund të

634
00:26:29,360 --> 00:26:33,200
të përdoret si një bllok ndërtimi për edhe më shumë
Strukturat e të dhënave të sofistikuara.

635
00:26:33,200 --> 00:26:37,620
>> Dhe të kuptojë too temë e këtu është se
ne kemi prezantuar absolutisht më shumë

636
00:26:37,620 --> 00:26:40,060
Kompleksiteti në zbatimin
i këtij algoritmi.

637
00:26:40,060 --> 00:26:43,940
Futje, dhe në qoftë se ne kemi shkuar nëpërmjet saj,
fshirjen dhe kërkimin, është pak

638
00:26:43,940 --> 00:26:46,660
më e komplikuar se ajo
ishte me një rrjet.

639
00:26:46,660 --> 00:26:48,040
Por ne kemi fituar disa dinamizëm.

640
00:26:48,040 --> 00:26:50,180
Ne kemi marrë një strukturë adaptive të dhënave.

641
00:26:50,180 --> 00:26:54,010
>> Por përsëri, ne të paguajë një çmim për të pasur disa
Kompleksiteti shtesë, si në

642
00:26:54,010 --> 00:26:54,910
zbatimin e tij.

643
00:26:54,910 --> 00:26:56,750
Dhe ne jemi të dhënë up qasje të rastit.

644
00:26:56,750 --> 00:27:00,450
Dhe të jetë i sinqertë, nuk është disa bukur
pastruar rrëshqitje unë mund të ju jap se

645
00:27:00,450 --> 00:27:03,120
thotë se këtu është arsyeja pse një listë e lidhur
është më mirë se një rrjet.

646
00:27:03,120 --> 00:27:04,100
Dhe të lënë atë në atë.

647
00:27:04,100 --> 00:27:07,520
Sepse temë reoccurring tani, madje edhe
aq më tepër në javët e ardhshme, është

648
00:27:07,520 --> 00:27:10,200
se nuk është domosdoshmërisht
një përgjigje të saktë.

649
00:27:10,200 --> 00:27:13,830
>> Kjo është arsyeja pse ne kemi aksin veçantë
e projektimit për grupe problem.

650
00:27:13,830 --> 00:27:17,700
Ajo do të jetë shumë e ndjeshme konteksti
nëse ju doni të përdorni këto të dhëna

651
00:27:17,700 --> 00:27:21,750
strukturë ose se një, dhe kjo do
varet nga ajo që ka rëndësi për ju në aspektin

652
00:27:21,750 --> 00:27:24,620
e burimeve dhe kompleksitet.

653
00:27:24,620 --> 00:27:28,830
>> Por më lejoni të propozojnë se të dhënat ideale
Struktura, Grail shenjtë, do të jetë

654
00:27:28,830 --> 00:27:32,200
diçka që është koha konstante,
pavarësisht nga sa shumë gjëra është

655
00:27:32,200 --> 00:27:36,940
brenda saj, nuk do të ishte e mahnitshme në qoftë se një
Struktura e të dhënave u kthye përgjigje në

656
00:27:36,940 --> 00:27:37,920
Ora konstante.

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

658
00:27:38,330 --> 00:27:40,110
Kjo fjalë është në fjalorin tuaj të madh.

659
00:27:40,110 --> 00:27:41,550
Apo jo, kjo fjalë nuk është.

660
00:27:41,550 --> 00:27:43,270
Ose ndonjë problem i tillë atje.

661
00:27:43,270 --> 00:27:46,360
E pra le të shohim nëse ne nuk mundemi të paktën
të marrë një hap drejt se.

662
00:27:46,360 --> 00:27:50,190
>> Më lejoni të propozojë një strukturë të re të të dhënave që
mund të përdoret për gjëra të ndryshme,

663
00:27:50,190 --> 00:27:52,260
në këtë rast quhet një tabelë hash.

664
00:27:52,260 --> 00:27:55,590
Dhe kështu që ne jemi në të vërtetë kthehet në glancing
me një rrjet, në këtë rast, dhe

665
00:27:55,590 --> 00:28:00,550
disi arbitrare, unë kam tërhequr këtë
tabelë hash si një grup me një lloj të

666
00:28:00,550 --> 00:28:02,810
dy-dimensional array -

667
00:28:02,810 --> 00:28:05,410
ose më mirë ajo është përshkruar këtu si dy
array dimensionale - por kjo është vetëm

668
00:28:05,410 --> 00:28:10,770
një grup i madhësisë 26, të tilla që në qoftë se ne
telefononi tabelën e vektorit, parantezë tavolinë

669
00:28:10,770 --> 00:28:12,440
zero eshte drejtkëndësh në majë.

670
00:28:12,440 --> 00:28:15,090
Kllapa Tabela 25 është drejtkëndësh
në fund.

671
00:28:15,090 --> 00:28:18,620
Dhe kjo është se si unë mund të tërheqë një të dhënave
strukturë në të cilën I duam të ruajtur

672
00:28:18,620 --> 00:28:19,790
njerëzit e emra.

673
00:28:19,790 --> 00:28:24,370
>> Kështu për shembull, dhe unë nuk do të tërheqë
Gjithë gjë këtu më lart, në qoftë se unë

674
00:28:24,370 --> 00:28:29,160
kishte këtë koleksion, të cilën unë jam tani do të
thërrasë një tryezë të hash, dhe kjo është përsëri

675
00:28:29,160 --> 00:28:31,360
Vendndodhja zero.

676
00:28:31,360 --> 00:28:34,840
Kjo këtu është vend
një, dhe kështu me radhë.

677
00:28:34,840 --> 00:28:37,880
Unë pretendojnë se unë dua që të përdorin këto të dhëna
struktura, per shkak te diskutimit,

678
00:28:37,880 --> 00:28:42,600
për të ruajtur emrat e njerëzve, Alice dhe Bob
dhe Charlie dhe emra të tjera të tilla.

679
00:28:42,600 --> 00:28:46,110
Pra, mendoj se kjo tani si në fillimet
e, të themi, një fjalor

680
00:28:46,110 --> 00:28:47,520
me shumë fjalë.

681
00:28:47,520 --> 00:28:49,435
Ata ndodhë që të jetë emrat
në shembullin tonë këtu.

682
00:28:49,435 --> 00:28:52,560
Dhe kjo është e gjitha shumë i përshtatshëm, ndoshta, për të
zbatimin e një spell checker, si ne

683
00:28:52,560 --> 00:28:54,400
mund të për problemin e ngritur gjashtë.

684
00:28:54,400 --> 00:28:59,300
>> Pra, nëse ne kemi një rrjet të madhësisë totale 26
në mënyrë që ky vend është 25

685
00:28:59,300 --> 00:29:03,390
në të poshtme, dhe pohoj se Alice është
fjala pare ne fjalorin e

686
00:29:03,390 --> 00:29:07,260
Emrat që unë dua për të futur në RAM,
në këtë strukturë të dhënash, ku janë

687
00:29:07,260 --> 00:29:12,480
Instinktet ju thënë se Alice
emri duhet të shkoni në këtë grup?

688
00:29:12,480 --> 00:29:13,510
>> Ne kemi 26 opsione.

689
00:29:13,510 --> 00:29:14,990
Ku duam të vënë e saj?

690
00:29:14,990 --> 00:29:16,200
Ne duam atë në kllapa zero, e drejtë?

691
00:29:16,200 --> 00:29:18,280
Një për të Alice, le të thërrasë atë zero.

692
00:29:18,280 --> 00:29:20,110
Dhe do të jetë një B, dhe C do të jetë dy.

693
00:29:20,110 --> 00:29:22,600
Pra, ne jemi duke shkuar për të shkruar
Emri Alice deri këtu.

694
00:29:22,600 --> 00:29:24,890
Nëse ne pastaj futni Bob tij,
Emri do të shkojnë këtu.

695
00:29:24,890 --> 00:29:27,280
Charlie do të shkojnë këtu.

696
00:29:27,280 --> 00:29:30,500
Dhe kështu me radhë poshtë nëpër
kjo Struktura e të dhënave.

697
00:29:30,500 --> 00:29:32,090
>> Kjo është një strukturë e mrekullueshme të dhënave.

698
00:29:32,090 --> 00:29:32,730
Pse?

699
00:29:32,730 --> 00:29:37,460
E pra çfarë është koha drejtimin e
futur emrin e një qenie njerëzore e në këtë

700
00:29:37,460 --> 00:29:39,850
Struktura e të dhënave tani?

701
00:29:39,850 --> 00:29:43,702
Duke pasur parasysh se kjo tabelë është zbatuar,
me të vërtetë, si një rrjet.

702
00:29:43,702 --> 00:29:44,940
E pra kjo është koha konstante.

703
00:29:44,940 --> 00:29:45,800
Kjo është mënyrë e njërit.

704
00:29:45,800 --> 00:29:46,360
Pse?

705
00:29:46,360 --> 00:29:48,630
>> E pra si mendoni ju të përcaktojë
ku Alice takon?

706
00:29:48,630 --> 00:29:51,000
Ju shikoni në të cilën letër e emrit të saj?

707
00:29:51,000 --> 00:29:51,490
Parë.

708
00:29:51,490 --> 00:29:54,350
Dhe ju mund të merrni atje, nëse kjo është një string,
vetëm duke shikuar në varg

709
00:29:54,350 --> 00:29:55,200
kllapa zero.

710
00:29:55,200 --> 00:29:57,110
Pra karakterit 0 të vargut.

711
00:29:57,110 --> 00:29:57,610
Kjo është e lehtë.

712
00:29:57,610 --> 00:30:00,350
Ne e bëmë që në kripto
caktimit javë më parë.

713
00:30:00,350 --> 00:30:05,310
Dhe pastaj një herë ju e dini se së Alice
Letra është kryeqyteti A, ne mund të zbres

714
00:30:05,310 --> 00:30:08,160
off 65 ose një kapital të vetë,
që na jep zero.

715
00:30:08,160 --> 00:30:10,940
Pra, ne tani e dimë se Alice takon
në lokacionin zero.

716
00:30:10,940 --> 00:30:14,240
>> Dhe duke pasur parasysh një tregues për këtyre të dhënave
Struktura, e disa lloj, sa kohë bën

717
00:30:14,240 --> 00:30:18,840
ajo merr mua për të gjetur vendndodhjen
zero në një grup?

718
00:30:18,840 --> 00:30:22,080
Vetëm një hap, e drejta Është koha konstante
për shkak të qasjes rastit ne

719
00:30:22,080 --> 00:30:23,780
propozuar ishte një tipar i një rrjet.

720
00:30:23,780 --> 00:30:28,570
Pra me pak fjalë, duke parafytyruar se çfarë indeksi
Emri i Alice është, i cili eshte, ne

721
00:30:28,570 --> 00:30:32,610
Në këtë rast, është Një, ose le të vetëm të zgjidhur
qe te zero, ku B është një dhe C eshte

722
00:30:32,610 --> 00:30:34,900
dy, duke parafytyruar se nga
është koha konstante.

723
00:30:34,900 --> 00:30:38,510
Unë vetëm duhet të shikoni në letrën e saj të parë,
zbulimin ku zero eshte nje

724
00:30:38,510 --> 00:30:40,460
array është edhe koha konstante.

725
00:30:40,460 --> 00:30:42,140
Pra, teknikisht kjo është
si dy hapa tani.

726
00:30:42,140 --> 00:30:43,330
Por kjo është ende konstante.

727
00:30:43,330 --> 00:30:46,880
Pra, ne e quajmë atë O e madhe e një, kështu që ne kemi
Alice futur në këtë tabelë në

728
00:30:46,880 --> 00:30:48,440
Ora konstante.

729
00:30:48,440 --> 00:30:50,960
>> Por sigurisht, unë jam duke u
naive këtu, e drejtë?

730
00:30:50,960 --> 00:30:53,240
Çka nëse nuk ka një Aaroni në klasë?

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

732
00:30:53,990 --> 00:30:57,230
Ose ndonjë emra të tjerë duke filluar me
A. Ku jemi duke shkuar për të vënë

733
00:30:57,230 --> 00:31:00,800
se personi, e drejtë?

734
00:31:00,800 --> 00:31:03,420
Unë do të thotë, tani për tani ka vetëm tre
njerëzit në tabelë, kështu që ndoshta ne

735
00:31:03,420 --> 00:31:07,490
duhet të vënë Aaronin në lokacionin
zero një dy tre.

736
00:31:07,490 --> 00:31:09,480
>> Drejtë, unë mund të vendos një këtu.

737
00:31:09,480 --> 00:31:13,350
Por pastaj, nëse ne përpiqemi për të futur Davidin në
kjo listë, ku do shkojnë Davidi?

738
00:31:13,350 --> 00:31:15,170
Tani sistemi ynë fillon thyer
poshtë, të drejtë?

739
00:31:15,170 --> 00:31:19,210
Sepse tani David përfundon këtu
nëse Aaron është në të vërtetë këtu.

740
00:31:19,210 --> 00:31:23,060
Dhe kështu që tani ky tërë ideja e të paturit e një
pastër të dhënave strukturë që na jep

741
00:31:23,060 --> 00:31:28,010
insertions konstante koha nuk është më e
Ora konstante, sepse unë kam për

742
00:31:28,010 --> 00:31:31,240
kontrolloni, oh, damnit, dikush është tashmë
Alice në vend.

743
00:31:31,240 --> 00:31:35,320
>> Më lejoni të shqyrtojmë pjesën tjetër të këtyre të dhënave
, struktura duke kërkuar për një vend për të vënë

744
00:31:35,320 --> 00:31:37,130
dikush si emrin e Aaronit.

745
00:31:37,130 --> 00:31:39,390
Dhe kështu që edhe është filluar
të marrë kohën lineare.

746
00:31:39,390 --> 00:31:42,710
Për më tepër, në qoftë se ju doni të gjeni tani
Aaroni në këtë strukturë të dhënave, dhe ju

747
00:31:42,710 --> 00:31:45,430
kontrolloni, dhe emri i Aaronit nuk është këtu.

748
00:31:45,430 --> 00:31:47,960
Idealisht, ju do të them vetëm për Aaronin
jo në strukturën dhënave.

749
00:31:47,960 --> 00:31:51,530
Por në qoftë se ju bëni filloni duke e bërë hapësirë ​​për
Aaroni ku nuk duhet të ketë qenë një D

750
00:31:51,530 --> 00:31:55,600
ose një, E ju, rasti më i keq, duhet të kontrolloni
gjithë struktura të dhënave, në

751
00:31:55,600 --> 00:31:59,480
të cilin rast ai bie në diçka
linear në madhësinë e tabelës.

752
00:31:59,480 --> 00:32:00,920
>> Pra, të gjithë të drejtë, unë do të rregullojmë këtë.

753
00:32:00,920 --> 00:32:04,200
Problemi këtu është se kam pasur
26 elemente në këtë grup.

754
00:32:04,200 --> 00:32:05,000
Më lejoni të ndryshojë atë.

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

756
00:32:06,010 --> 00:32:10,600
Më lejoni të ndryshojë atë në mënyrë që në vend të qenit i
Madhësia e 26 në total, njoftim pjesën e poshtme

757
00:32:10,600 --> 00:32:12,720
indeksi do të ndryshojë për të n minus 1.

758
00:32:12,720 --> 00:32:16,610
26 Në qoftë se është e qartë shumë e vogël për 'njerëzit
emrat, sepse ka mijëra

759
00:32:16,610 --> 00:32:20,830
Emrat e botës, le të vetëm të bëjë
në 100 apo 1000 apo 10000.

760
00:32:20,830 --> 00:32:22,960
Le të vetëm të ndajë një hapësirë ​​shumë më tepër.

761
00:32:22,960 --> 00:32:27,230
>> E pra kjo nuk domosdoshmërisht ulet
probabiliteti që ne nuk do të ketë dy

762
00:32:27,230 --> 00:32:31,510
njerëzit me emra duke filluar me A, dhe
Pra, ju u do të përpiqet për të vënë një

763
00:32:31,510 --> 00:32:33,120
Emrat në zero ende e lokacionit.

764
00:32:33,120 --> 00:32:36,850
Ata janë ende duke shkuar për të përplasjes, e cila
do të thotë që ne ende nevojë për një zgjidhje për të vënë

765
00:32:36,850 --> 00:32:41,020
Alice dhe Aaroni dhe Alicia dhe të tjera
emra duke filluar me një tjetërkund.

766
00:32:41,020 --> 00:32:43,460
Por si shumë e një problemi është ky?

767
00:32:43,460 --> 00:32:46,870
Cili është probabiliteti që ju
kanë goditjet në një të dhënave

768
00:32:46,870 --> 00:32:48,240
Struktura si kjo?

769
00:32:48,240 --> 00:32:52,570
>> E pra, më lejoni - ne do të kthehemi
për këtë pyetje këtu.

770
00:32:52,570 --> 00:32:55,530
Dhe shikoni se si ne mund të
zgjidhur atë së pari.

771
00:32:55,530 --> 00:32:58,480
Më lejoni të tërheq lart këtë propozim këtu.

772
00:32:58,480 --> 00:33:02,020
Ajo që ne vetëm të përshkruar një algoritmi,
një orientues i quajtur linear

773
00:33:02,020 --> 00:33:05,030
probing ku, nëse jeni përpjekur për të futur
diçka që këtu në këto të dhëna

774
00:33:05,030 --> 00:33:08,920
strukturë, e cila është quajtur një tabelë hash,
dhe nuk ka hapësirë ​​atje, ju

775
00:33:08,920 --> 00:33:12,000
vërtetë hetuar strukturën e të dhënave
kontrolluar, kjo është në dispozicion?

776
00:33:12,000 --> 00:33:13,430
A është kjo në dispozicion është në dispozicion kjo?

777
00:33:13,430 --> 00:33:13,980
A është kjo në dispozicion?

778
00:33:13,980 --> 00:33:17,550
Dhe kur më në fund ajo është, ju futur
përmendur që ju menduar fillimisht

779
00:33:17,550 --> 00:33:19,370
diku tjetër në atë vend.

780
00:33:19,370 --> 00:33:23,360
Por në rastin më të keq, i vetmi vend
mund të jetë shumë e poshtme e të dhënave

781
00:33:23,360 --> 00:33:25,090
struktura, skaj shumë e vektorit.

782
00:33:25,090 --> 00:33:30,130
>> Pra linear probing, në rastin më të keq,
bie në një algoritmi linear ku

783
00:33:30,130 --> 00:33:34,500
Aaroni, nëse ai ndodh të jetë futur fundit
në këtë strukturë të dhënave, ai mund të

784
00:33:34,500 --> 00:33:39,540
bien ndesh me këtë vend të parë, por
pastaj të përfundojë me fat të keq në fund.

785
00:33:39,540 --> 00:33:43,940
Pra, kjo nuk është një konstante
Ora Grail shenjtë për ne.

786
00:33:43,940 --> 00:33:47,650
Kjo qasje e elementeve të futur në
një strukturë e të dhënave e quajtur hash

787
00:33:47,650 --> 00:33:52,050
Tabela nuk duket të jetë kohë konstante
të paktën jo në rastin e përgjithshme.

788
00:33:52,050 --> 00:33:54,000
Ajo mund të bie në diçka lineare.

789
00:33:54,000 --> 00:33:56,970
>> Pra, çfarë nëse ne të zgjidhur goditjet
disi ndryshe?

790
00:33:56,970 --> 00:34:00,740
Pra, këtu është një më i sofistikuar
qasje në atë që është ende

791
00:34:00,740 --> 00:34:02,800
quajtur një tavolinë hash.

792
00:34:02,800 --> 00:34:05,890
Dhe duke hash, Si një mënjanë, çfarë
Unë do të thotë është se indeksi

793
00:34:05,890 --> 00:34:07,070
I përmendur më herët.

794
00:34:07,070 --> 00:34:09,810
Për të hash diçka mund të jetë
menduar si një folje.

795
00:34:09,810 --> 00:34:13,690
>> Pra, nëse ju Alice hash është një emër,
një funksion hash, kështu që të flasin,

796
00:34:13,690 --> 00:34:14,710
duhet të kthejë një numër.

797
00:34:14,710 --> 00:34:18,199
Në këtë rast është zero, nëse ajo i takon në
Vendndodhja zero, një, nëse ajo i takon në

798
00:34:18,199 --> 00:34:20,000
Vendndodhja një, dhe kështu me radhë.

799
00:34:20,000 --> 00:34:24,360
Pra, funksioni im hash deri tani ka qenë
super e thjeshtë, vetëm duke kërkuar në

800
00:34:24,360 --> 00:34:26,159
shkronja e parë në emër të dikujt.

801
00:34:26,159 --> 00:34:29,090
Por një funksion hash merr si
input disa pjesë të të dhënave, një

802
00:34:29,090 --> 00:34:30,210
string, int një, çfarëdo.

803
00:34:30,210 --> 00:34:32,239
Dhe kjo pështyn në mënyrë tipike nga një numër.

804
00:34:32,239 --> 00:34:35,739
Dhe ky numër është se ku të dhënat e
element i takon në strukturën e të dhënave

805
00:34:35,739 --> 00:34:37,800
e njohur këtu si një tryezë hash.

806
00:34:37,800 --> 00:34:41,400
>> Pra, vetëm intuitive, kjo është një
kontekst pak më ndryshe.

807
00:34:41,400 --> 00:34:44,170
Kjo në fakt është duke iu referuar një shembull
ditëlindjet përfshijnë, ku

808
00:34:44,170 --> 00:34:46,850
nuk mund të jetë aq sa
31 ditë në muaj.

809
00:34:46,850 --> 00:34:52,239
Por çfarë ka ky person të vendosë për
bëni në rast të një përplasjeje?

810
00:34:52,239 --> 00:34:55,304
Konteksti tani të qenit, jo një përplasje të
emra, por një përplasje e ditëlindje,

811
00:34:55,304 --> 00:35:00,760
në qoftë se dy njerëz kanë të njëjtën ditëlindje në
2 tetor, për shembull.

812
00:35:00,760 --> 00:35:02,120
>> STUDENT: [padëgjueshme].

813
00:35:02,120 --> 00:35:05,010
>> Kryetari 1: Yeah, kështu që këtu kemi
leveraging e listave të lidhura.

814
00:35:05,010 --> 00:35:07,830
Pra, kjo duket pak ndryshe
se sa ne tërhoqi atë më parë.

815
00:35:07,830 --> 00:35:10,790
Por ne duket se kanë një koleksion të
në anën e majtë.

816
00:35:10,790 --> 00:35:13,230
Kjo është një indeksi, për asnjë
Arsyeja veçanti.

817
00:35:13,230 --> 00:35:14,630
Por kjo është ende një array.

818
00:35:14,630 --> 00:35:16,160
Është një grup i pointers.

819
00:35:16,160 --> 00:35:20,670
Dhe secili prej këtyre elementeve, secila prej
këto qarqe ose ul - zvogëlojë

820
00:35:20,670 --> 00:35:23,970
null përfaqësojnë - secila nga këto
pointers është me sa duket duke treguar për

821
00:35:23,970 --> 00:35:25,730
çfarë Struktura e të dhënave?

822
00:35:25,730 --> 00:35:26,890
Një listë e lidhur.

823
00:35:26,890 --> 00:35:30,530
>> Pra, tani ne kemi aftësinë për të
Kodi vështirë në programin tonë

824
00:35:30,530 --> 00:35:32,010
madhësia e tabelës.

825
00:35:32,010 --> 00:35:35,360
Në këtë rast, ne e dimë se kurrë nuk ka
më shumë se 31 ditë në një muaj.

826
00:35:35,360 --> 00:35:38,480
Pra vështirë coding si një vlerë 31 është
arsyeshme në atë kontekst.

827
00:35:38,480 --> 00:35:42,700
Në kontekstin e emrave, e vështirë coding
26 nuk është e paarsyeshme që njerëzit e

828
00:35:42,700 --> 00:35:46,340
emra të fillojë vetëm me të, për shembull,
Alfabeti përfshin një anë të Z.

829
00:35:46,340 --> 00:35:50,180
>> Ne mund të mbushur të gjitha ato në të cilat të dhënat
Struktura aq kohë sa, kur ne të merrni një

830
00:35:50,180 --> 00:35:55,330
Përplasja, ne nuk e vënë emrat këtu,
ne mendojmë në vend të këtyre qelizave

831
00:35:55,330 --> 00:36:00,270
jo si vargjet vetë, por si
pointers, për shembull, Alice.

832
00:36:00,270 --> 00:36:03,660
Dhe pastaj Alice mund të ketë një tjetër treguesin
për të filluar me një emër tjetër

833
00:36:03,660 --> 00:36:06,150
A. Dhe Bob në fakt shkon mbi këtu.

834
00:36:06,150 --> 00:36:10,850
>> Dhe në qoftë se ka një tjetër emër duke filluar
me B, ai përfundon deri këtu.

835
00:36:10,850 --> 00:36:15,070
Dhe kështu secili prej elementeve të këtij
Tabela dy, në qoftë se ne kemi projektuar këtë një

836
00:36:15,070 --> 00:36:17,350
pak më shumë cleverly -

837
00:36:17,350 --> 00:36:18,125
eja -

838
00:36:18,125 --> 00:36:22,950
në qoftë se ne kemi projektuar këtë një pak më shumë
cleverly, tani bëhet një adaptive dhënat

839
00:36:22,950 --> 00:36:27,720
Struktura, ku nuk ka asnjë kufizim vështirë
se sa elementet që ju mund të futni

840
00:36:27,720 --> 00:36:30,700
në të, sepse në qoftë se ju keni
një përplasje, kjo është në rregull.

841
00:36:30,700 --> 00:36:34,690
Vetëm të shkojnë përpara dhe append atë në
atë që pamë pak më parë ishte

842
00:36:34,690 --> 00:36:38,290
i njohur si një listë e lidhur.

843
00:36:38,290 --> 00:36:39,690
>> E pra, le të pauzë për një moment të vetëm.

844
00:36:39,690 --> 00:36:42,570
Cili është probabiliteti i një përplasjeje të rëndë
në vendin e parë?

845
00:36:42,570 --> 00:36:45,480
E drejta, ndoshta unë jam mbi të menduarit, ndoshta
Unë jam inxhinieri mbi këtë problem,

846
00:36:45,480 --> 00:36:46,370
sepse ju e dini se çfarë?

847
00:36:46,370 --> 00:36:49,070
Po, unë mund të dalë me arbitrare
shembuj pjesa e sipërme e kokës sime si

848
00:36:49,070 --> 00:36:52,870
Allison dhe Aaroni, por në realitet,
jepet një shpërndarje uniforme të

849
00:36:52,870 --> 00:36:56,990
inputet, që është disa insertions të rastit
në strukturën e të dhënave, ajo që është me të vërtetë

850
00:36:56,990 --> 00:36:58,580
mundësia e një përplasjeje?

851
00:36:58,580 --> 00:37:01,670
E pra rezulton, ajo është në fakt
super të lartë.

852
00:37:01,670 --> 00:37:03,850
Më lejoni të përgjithësoj këtë
Problemi është si kjo.

853
00:37:03,850 --> 00:37:08,890
>> Pra, në një dhomë të n CS50 studentëve, çfarë është
probabiliteti që të paktën

854
00:37:08,890 --> 00:37:11,010
dy studentë në dhomë
kanë të njëjtën ditëlindje?

855
00:37:11,010 --> 00:37:13,346
Pra, nuk është ajo. një hund pak -

856
00:37:13,346 --> 00:37:16,790
200, 300 njerëz këtu dhe disa
qindra njerëz në shtëpi sot.

857
00:37:16,790 --> 00:37:20,670
Pra, nëse ju të kërkuar për të pyesni veten se çfarë është
probabiliteti i dy njerëzve

858
00:37:20,670 --> 00:37:23,930
në këtë dhomë ka të njëjtën ditëlindje,
ne mund të kuptoj këtë.

859
00:37:23,930 --> 00:37:26,250
Dhe unë pretendojnë fakt ekzistojnë dy
njerëzit me të njëjtën ditëlindje.

860
00:37:26,250 --> 00:37:29,560
>> Për shembull, e bën dikush
kanë ditëlindjen sot?

861
00:37:29,560 --> 00:37:31,340
Dje?

862
00:37:31,340 --> 00:37:32,590
Nesër?

863
00:37:32,590 --> 00:37:35,980
Të gjithë të drejtë, kështu që ai ndjehet si unë jam duke shkuar
që të ketë për të bërë këtë 363 ose kështu që më shumë

864
00:37:35,980 --> 00:37:39,500
herë që në fakt të kuptoj
në qoftë se ne kemi një përplasje.

865
00:37:39,500 --> 00:37:42,350
Ose ne mund vetëm të bëjë këtë matematikisht
sesa tediously

866
00:37:42,350 --> 00:37:43,200
bërë këtë.

867
00:37:43,200 --> 00:37:44,500
Dhe të propozojë në vijim.

868
00:37:44,500 --> 00:37:48,740
>> Kështu që unë propozoj që ne mund të modelojnë
Probabiliteti i dy njerëzve që kanë

869
00:37:48,740 --> 00:37:55,320
ditëlindjen e njëjtë si probabilitetin e 1
minus probabilitetin e Asnjëri që ka

870
00:37:55,320 --> 00:37:56,290
njëjtën ditëlindje.

871
00:37:56,290 --> 00:37:59,960
Pra, për të marrë këtë, dhe kjo është vetëm
Mënyra më e sofistikuar për të shkruar këtë, për

872
00:37:59,960 --> 00:38:03,090
personi i parë në dhomë, ai ose ajo
mund të ketë çdo njëri prej mundur

873
00:38:03,090 --> 00:38:07,370
ditëlindjet supozuar ditë 365 në vit,
me keqardhjet për personat me

874
00:38:07,370 --> 00:38:08,760
ditëlindjen e 29 Shkurt.

875
00:38:08,760 --> 00:38:13,470
>> Pra, personi i parë në këtë dhomë është i lirë
të ketë ndonjë numër të ditëlindje

876
00:38:13,470 --> 00:38:18,280
jashtë mundësive 365 në mënyrë që
ne do të bëjmë që ndahen nga 365 365,

877
00:38:18,280 --> 00:38:18,990
e cila është një.

878
00:38:18,990 --> 00:38:22,700
Personi tjetër në dhomë, në qoftë se qëllimi
është për të shmangur një përplasje, mund vetëm

879
00:38:22,700 --> 00:38:26,460
kanë ditëlindjen e tij ose të saj në mënyrën se si
shumë ditë të ndryshme të mundshme?

880
00:38:26,460 --> 00:38:27,610
364.

881
00:38:27,610 --> 00:38:31,430
Pra, termi i dytë në këtë shprehje është
në thelb të bërë atë matematikë për ne

882
00:38:31,430 --> 00:38:33,460
duke zbritur off një ditë të jetë e mundur.

883
00:38:33,460 --> 00:38:36,390
Dhe pastaj ditën tjetër, të nesërmen,
nesërmen poshtë në numrin e përgjithshëm

884
00:38:36,390 --> 00:38:38,100
e njerëzve në dhomë.

885
00:38:38,100 --> 00:38:41,290
>> Dhe nëse ne pastaj e konsiderojnë, çfarë atëherë është
probabiliteti i të gjithëve nuk ka

886
00:38:41,290 --> 00:38:45,265
ditëlindjet unike, por përsëri 1 minus
se, ajo që ne kemi marrë është një shprehje

887
00:38:45,265 --> 00:38:47,810
që mund shumë fancifully
duket si ky.

888
00:38:47,810 --> 00:38:50,330
Por kjo është më interesante
për të parë në sy.

889
00:38:50,330 --> 00:38:55,120
Kjo është një tabelë ku mbi boshtin x eshte
numri i njerëzve në dhomë,

890
00:38:55,120 --> 00:38:56,180
Numri i ditëlindje.

891
00:38:56,180 --> 00:38:59,840
Në y-aks është probabiliteti
e një përplasjeje të rëndë, dy njerëz

892
00:38:59,840 --> 00:39:01,230
pasur ditëlindjen njëjtë.

893
00:39:01,230 --> 00:39:05,020
>> Dhe takeaway nga kjo kurbë është
që sa më shpejt që ju të merrni për të si 40

894
00:39:05,020 --> 00:39:11,110
studentë, ju jeni deri në një probabilitet 90%
combinatorically i dy

895
00:39:11,110 --> 00:39:13,550
njerëzit apo më shumë kanë
njëjtën ditëlindje.

896
00:39:13,550 --> 00:39:18,600
Dhe një herë ju merrni për të si 58 njerëz kjo është
gati 100% e një shans dy

897
00:39:18,600 --> 00:39:21,310
njerëz në dhomë do të ketë
ditëlindjen e njëjtë, edhe pse ka

898
00:39:21,310 --> 00:39:26,650
365 ose 366 kova të mundshme, dhe
vetëm 58 njerëz në dhomë.

899
00:39:26,650 --> 00:39:29,900
Vetëm statistikisht ju jeni të ngjarë të
merrni goditjet, e cila në të shkurtër

900
00:39:29,900 --> 00:39:31,810
motivon këtë diskutim.

901
00:39:31,810 --> 00:39:35,890
Se edhe në qoftë se ne të merrni dashuroj këtu, dhe
fillojnë që këto zinxhirët, ne jemi ende

902
00:39:35,890 --> 00:39:36,950
do të ketë goditjet.

903
00:39:36,950 --> 00:39:42,710
>> Kështu që ngre pyetjen, çfarë është
Kostoja e bërë insertions dhe grisjeve

904
00:39:42,710 --> 00:39:44,850
në strukturën e të dhënave si kjo?

905
00:39:44,850 --> 00:39:46,630
E pra më lejoni të propozoj -

906
00:39:46,630 --> 00:39:51,570
dhe më lejoni të shkoj përsëri në ekran gjatë
këtu - në qoftë se ne kemi n elementet në

907
00:39:51,570 --> 00:39:56,330
listë, kështu që në qoftë se ne jemi duke u përpjekur për të futur
Elementet n, dhe ne kemi

908
00:39:56,330 --> 00:39:58,050
sa kova totale?

909
00:39:58,050 --> 00:40:03,450
Le të thonë se 31 kova totale
ne rastin e ditëlindje.

910
00:40:03,450 --> 00:40:09,240
Çfarë është gjatësia maksimale e njërit
prej këtyre zinxhirëve potencialisht?

911
00:40:09,240 --> 00:40:12,670
>> Nëse përsëri nuk ka mundur 31
ditëlindjet në një muaj të caktuar.

912
00:40:12,670 --> 00:40:14,580
Dhe ne jemi vetëm drejtim të grumbullimit të të gjithëve -

913
00:40:14,580 --> 00:40:15,580
në fakt kjo është një shembull budalla.

914
00:40:15,580 --> 00:40:16,960
Le të bëjmë në vend të 26.

915
00:40:16,960 --> 00:40:20,890
Pra, nëse në të vërtetë të ketë njerëz emrat e të cilëve
fillojnë me A derinë Z, duke dhënë

916
00:40:20,890 --> 00:40:22,780
na 26 mundësitë.

917
00:40:22,780 --> 00:40:25,920
Dhe ne jemi duke përdorur një strukturë të dhënave si
një ne vetëm e pa, ku kemi

918
00:40:25,920 --> 00:40:30,210
një grup i pointers, secila prej të cilave
pikë për një listë të lidhura, ku të

919
00:40:30,210 --> 00:40:32,360
Lista e parë është e të gjithë
me Alice Emri.

920
00:40:32,360 --> 00:40:35,770
Lista e dyta është me çdo
përmendur duke filluar me A, duke filluar

921
00:40:35,770 --> 00:40:36,980
me B, dhe kështu me radhë.

922
00:40:36,980 --> 00:40:41,020
>> Çfarë është gjatësia e mundshme të secilit prej
ato listat në qoftë se ne supozojmë një të pastër të bukur

923
00:40:41,020 --> 00:40:45,410
shpërndarja e emrave Një përmes Z
nëpër gjithë strukturës të të dhënave?

924
00:40:45,410 --> 00:40:50,210
Ka njerëz n në strukturën e të dhënave
pjesëtuar me 26, nëse ata janë të bukur

925
00:40:50,210 --> 00:40:52,110
të shtrirë mbi tërë
Struktura e të dhënave.

926
00:40:52,110 --> 00:40:54,970
Pra, gjatësia e secilit prej këtyre
Zinxhirët është n ndarë nga 26.

927
00:40:54,970 --> 00:40:57,380
Por në simbol Big O, çfarë është ajo?

928
00:40:57,380 --> 00:41:00,100

929
00:41:00,100 --> 00:41:02,440
Çfarë është që me të vërtetë?

930
00:41:02,440 --> 00:41:04,150
Pra, kjo është me të vërtetë vetëm n, apo jo?

931
00:41:04,150 --> 00:41:06,620
Sepse ne kemi thënë në të kaluarën,
që ohu ju ndani me 26.

932
00:41:06,620 --> 00:41:08,710
Po, në realitet ajo është më e shpejtë.

933
00:41:08,710 --> 00:41:12,720
Por në teori, kjo nuk është krejtësisht
gjithçka që të shpejtë.

934
00:41:12,720 --> 00:41:16,040
>> Pra, ne nuk duket të jetë mbi të gjitha se shumë
afër këtij Grail shenjtë.

935
00:41:16,040 --> 00:41:17,750
Në fakt, kjo është vetëm koha lineare.

936
00:41:17,750 --> 00:41:20,790
Heck, në këtë pikë, pse nuk e bëjmë ne
përdorni vetëm një listë të madhe lidhur?

937
00:41:20,790 --> 00:41:23,510
Pse nuk e përdorni vetëm një i madh
grup për të ruajtur emrat e

938
00:41:23,510 --> 00:41:25,010
të gjithë në dhomë?

939
00:41:25,010 --> 00:41:28,280
E pra, a ka ende diçka
bindëse në lidhje me një tabelë hash?

940
00:41:28,280 --> 00:41:30,810
A ka ende diçka bindëse
lidhje me strukturën e të dhënave

941
00:41:30,810 --> 00:41:33,940
që duket si kjo?

942
00:41:33,940 --> 00:41:35,182
Kjo.

943
00:41:35,182 --> 00:41:37,050
>> STUDENT: [padëgjueshme].

944
00:41:37,050 --> 00:41:39,840
>> Kryetari 1: drejta, dhe përsëri në qoftë se ajo është vetëm
nje algoritmi linear kohë, dhe nje

945
00:41:39,840 --> 00:41:42,780
Ora Struktura lineare dhënat, pse nuk kam
vetëm për të ruajtur emrin e të gjithëve në një i madh

946
00:41:42,780 --> 00:41:44,210
array, ose në një listë të madhe lidhur?

947
00:41:44,210 --> 00:41:47,010
Dhe të ndaluar marrjen e CS aq shumë më të vështirë
se ajo duhet të jetë?

948
00:41:47,010 --> 00:41:49,600

949
00:41:49,600 --> 00:41:53,190
Çfarë është bindëse në lidhje me këtë, edhe
pse unë gërvishtem atë?

950
00:41:53,190 --> 00:41:54,930
>> STUDENT: [padëgjueshme].

951
00:41:54,930 --> 00:41:57,040
>> Kryetari 1: insertions nuk janë?

952
00:41:57,040 --> 00:41:58,140
Shtrenjtë anymore.

953
00:41:58,140 --> 00:42:03,390
Pra, insertions potencialisht mund të ende
jetë koha konstante, edhe në qoftë se të dhënat tuaja

954
00:42:03,390 --> 00:42:07,910
Struktura duket si ky, një rrjet të
Pointers, secila prej të cilave është e treguar në

955
00:42:07,910 --> 00:42:09,550
potencialisht një listë të lidhura.

956
00:42:09,550 --> 00:42:15,220
Si mund të keni arritur të vazhdueshme
futje koha e emrave?

957
00:42:15,220 --> 00:42:16,280
Ngjit atë në para, e drejtë?

958
00:42:16,280 --> 00:42:19,290
>> Nëse ne sakrifikojmë një gol design nga
më herët, ku ne të kërkuar për të mbajtur

959
00:42:19,290 --> 00:42:22,650
emri i të gjithëve, për shembull, të renditura,
ose të gjithë numrat e renditura në skenë,

960
00:42:22,650 --> 00:42:25,020
mendoj se ne kemi një
Lista unsorted lidhura.

961
00:42:25,020 --> 00:42:29,960
Ajo vetëm na kushton një ose dy hapa,
si në rastin e Ben dhe Brian

962
00:42:29,960 --> 00:42:32,750
më herët, për të futur një element në
fillimi i lista.

963
00:42:32,750 --> 00:42:36,090
Pra, nëse ne nuk e kujdesit për klasifikim të gjithë
prej emrave të filluar me një ose të gjitha

964
00:42:36,090 --> 00:42:39,660
emrat që fillojnë me B, ne ende mund të
arritur futje konstante në kohë.

965
00:42:39,660 --> 00:42:43,900
Tani duke kërkuar deri Alice apo Bob as kujtim
më në përgjithësi është ende çfarë?

966
00:42:43,900 --> 00:42:48,100
Është i madh o n i ndarë nga 26, në
rasti ideal ku gjithkush është uniforme

967
00:42:48,100 --> 00:42:51,190
shpërndahet, ku ka aq shumë një të
si ka të Z, e cila është ndoshta

968
00:42:51,190 --> 00:42:52,220
joreale.

969
00:42:52,220 --> 00:42:53,880
Por kjo është ende lineare.

970
00:42:53,880 --> 00:42:57,120
>> Por këtu, kemi ardhur përsëri në pikën
e simbol asymptotic qenë

971
00:42:57,120 --> 00:42:58,600
teorikisht e vërtetë.

972
00:42:58,600 --> 00:43:02,960
Por, në botën reale, në qoftë se unë pretendojnë se
Programi im mund të bëjë diçka 26 herë

973
00:43:02,960 --> 00:43:06,210
më shpejt se sa tuajat, të cilit programi
po ju do të preferoni duke përdorur?

974
00:43:06,210 --> 00:43:09,660
Juaji apo minave, i cili
është 26 herë më të shpejtë?

975
00:43:09,660 --> 00:43:14,320
Realisht, personi të cilit është 26
herë më të shpejtë, madje edhe nëse teorikisht

976
00:43:14,320 --> 00:43:18,790
Algoritmet tona të kandidojë në të njëjtën
asymptotic running kohë.

977
00:43:18,790 --> 00:43:20,940
>> Më lejoni të propozojë një tjetër
zgjidhje krejt.

978
00:43:20,940 --> 00:43:24,380
Dhe në qoftë se kjo nuk do të fryj mendjen tuaj,
ne jemi jashtë strukturave të të dhënave.

979
00:43:24,380 --> 00:43:27,420
Pra, kjo është një trie -

980
00:43:27,420 --> 00:43:28,520
lloj i një emër stupid.

981
00:43:28,520 --> 00:43:32,880
Ajo vjen nga retrievals, dhe fjala
është shkruar trie, T-r-I-E, për shkak të

982
00:43:32,880 --> 00:43:34,450
rikthim kurs tingëllon si trie.

983
00:43:34,450 --> 00:43:36,580
Por kjo është historia
i trie fjalë.

984
00:43:36,580 --> 00:43:40,980
>> Pra, një trie është me të vërtetë një lloj i pemës,
dhe kjo është gjithashtu një lojë në atë fjalë.

985
00:43:40,980 --> 00:43:46,330
Dhe, edhe pse ju nuk mund të mjaft të shohin atë
me këtë vizualizimi, nje trie eshte nje

986
00:43:46,330 --> 00:43:50,790
pemë e strukturuar, si një pemë familjare me
një paraardhës në krye dhe shumë

987
00:43:50,790 --> 00:43:54,530
nga nipërit dhe nipërit e mbesat e mëdha
si lë në pjesën e poshtme.

988
00:43:54,530 --> 00:43:58,100
Por çdo nyje ne nje trie eshte nje grup.

989
00:43:58,100 --> 00:44:00,680
Dhe kjo është në një rrjet - dhe le
thjeshtëzoj për një çast - kjo është një

990
00:44:00,680 --> 00:44:04,600
grup, në këtë rast, të madhësisë 26, ku
çdo nyje përsëri është një koleksion i madhësisë

991
00:44:04,600 --> 00:44:09,000
26, ku 0 element në atë
Grup përfaqëson A, dhe fundit

992
00:44:09,000 --> 00:44:11,810
element në çdo të tillë
array përfaqëson Z.

993
00:44:11,810 --> 00:44:15,520
>> Kështu që unë propozoj, atëherë, që këto të dhëna
struktura, i njohur si nje trie, mund të jenë

994
00:44:15,520 --> 00:44:17,600
përdoret gjithashtu për të ruajtur fjalët.

995
00:44:17,600 --> 00:44:21,740
Ne pamë një moment më parë se si ne mund të ruani
fjalë, ose në këtë rast emrat, dhe ne

996
00:44:21,740 --> 00:44:25,440
pashë më herët se si ne mund të ruajë numrat,
por në qoftë se ne të përqëndrohet në emra apo vargjet

997
00:44:25,440 --> 00:44:27,460
këtu, njoftim se çfarë është interesante.

998
00:44:27,460 --> 00:44:32,210
Pohoj se Maxëell Emri eshte
brenda kësaj strukture të dhëna.

999
00:44:32,210 --> 00:44:33,730
Ku e shihni ju Maxwell?

1000
00:44:33,730 --> 00:44:35,140
>> STUDENT: [padëgjueshme].

1001
00:44:35,140 --> 00:44:36,240
>> Kryetari 1: Në të majtë.

1002
00:44:36,240 --> 00:44:39,910
Pra, çfarë është interesante me këtyre të dhënave
Struktura është më tepër se dyqan të

1003
00:44:39,910 --> 00:44:46,200
string M-A-X-W-E-L-L backslash zero, të gjithë
pranë njëri tjetrit, çfarë bëni ju në vend

1004
00:44:46,200 --> 00:44:46,890
është duke ndjekur.

1005
00:44:46,890 --> 00:44:50,510
Në qoftë se kjo është një trie si strukturën e të dhënave,
secili prej nyjeve të cilit është përsëri një grup,

1006
00:44:50,510 --> 00:44:54,650
dhe ju doni për të ruajtur Maxwell, ju së pari
indeksi dhe kështu nyja rrënjë, prandaj

1007
00:44:54,650 --> 00:44:57,810
të flasin, nyjen larti,
at e lokacionit M, e drejtë, kështu që

1008
00:44:57,810 --> 00:44:59,160
afërsisht në mes.

1009
00:44:59,160 --> 00:45:03,740
Dhe pastaj nga atje, ju do të ndiqni një
tregues për një nyje e fëmijëve, kështu që të flasin.

1010
00:45:03,740 --> 00:45:06,150
Pra, në kuptimin pemë familjare,
ju ndiqni atë në rënie.

1011
00:45:06,150 --> 00:45:09,030
Dhe që t'ju çojë në një tjetër nyje
nga e majta atje, e cila është

1012
00:45:09,030 --> 00:45:10,540
vetëm një array.

1013
00:45:10,540 --> 00:45:14,710
>> Dhe pastaj, nëse ju doni të ruajtur Maxwell,
ju gjeni që përfaqëson treguesin

1014
00:45:14,710 --> 00:45:16,430
A, i cili eshte ky nje here.

1015
00:45:16,430 --> 00:45:17,840
Pastaj ju shkoni në nyjen e ardhshëm.

1016
00:45:17,840 --> 00:45:20,100
Dhe vini re - kjo është arsyeja pse fotografia e
një mashtruese pak -

1017
00:45:20,100 --> 00:45:21,990
kjo nyje duken super vogël.

1018
00:45:21,990 --> 00:45:26,050
Por për të drejtën e kjo është e Y dhe Z.
Ajo është vetëm autori ka cunguar

1019
00:45:26,050 --> 00:45:27,630
foto kështu që ju në të vërtetë
shohin gjërat.

1020
00:45:27,630 --> 00:45:30,400
Perndryshe kjo foto
do të jetë jashtëzakonisht e gjerë.

1021
00:45:30,400 --> 00:45:36,180
Deri tani ju e lokacionit indeksi në X, atëherë
W, E Pastaj, pastaj L, atëherë L. Atëherë çfarë është

1022
00:45:36,180 --> 00:45:37,380
ky kuriozitet?

1023
00:45:37,380 --> 00:45:41,250
>> Epo, në qoftë se ne jemi duke përdorur këtë lloj të ri
marrë mbi se si për të ruajtur një varg në një

1024
00:45:41,250 --> 00:45:44,500
Struktura e të dhënave, ju ende nevojë për të
thelb kontrolloni off në të dhënat e

1025
00:45:44,500 --> 00:45:47,250
strukturë që një fjalë mbaron këtu.

1026
00:45:47,250 --> 00:45:50,830
Me fjalë të tjera, secila prej këtyre nyjeve
disi ka për të kujtuar se ne

1027
00:45:50,830 --> 00:45:53,500
ndjekur në fakt të gjitha këto pointers
dhe po largohen pak

1028
00:45:53,500 --> 00:45:58,370
thërrime buke në fund këtu e kësaj
strukturë për të treguar M-A-x-W-e-L-L është

1029
00:45:58,370 --> 00:46:00,230
të vërtetë në këtë strukturë të dhëna.

1030
00:46:00,230 --> 00:46:02,040
>> Pra, ne mund të bëjmë këtë si më poshtë.

1031
00:46:02,040 --> 00:46:06,810
Secili prej nyjave në foto ne vetëm
savs ka një, një grup të madhësisë 27.

1032
00:46:06,810 --> 00:46:10,550
Dhe kjo është tani 27, sepse në gjashtë p vendosur,
ne do të vërtetë të ju jap një apostrof,

1033
00:46:10,550 --> 00:46:13,590
kështu që ne mund të kemi emra si O'Reilly
dhe të tjerët me apostrofat.

1034
00:46:13,590 --> 00:46:14,820
Por, të njëjtën ide.

1035
00:46:14,820 --> 00:46:17,710
Secili prej këtyre elementeve në
pikë rreshtuan për një struct

1036
00:46:17,710 --> 00:46:19,320
nyje, kështu që vetëm një nyje.

1037
00:46:19,320 --> 00:46:21,430
Pra, kjo është shumë e kujton
e listës sonë të lidhura.

1038
00:46:21,430 --> 00:46:24,550
>> Dhe atëherë unë kam një Boolean, të cilën unë do të
telefononi fjalë, e cila është vetëm do të jetë

1039
00:46:24,550 --> 00:46:29,120
e vërtetë në qoftë se një fjalë mbaron në këtë
Nyja në pemë.

1040
00:46:29,120 --> 00:46:32,870
Ajo përfaqëson në mënyrë efektive pak
trekëndësh ne pamë një moment më parë.

1041
00:46:32,870 --> 00:46:37,190
Pra, nëse një fjalë mbaron në atë nyje në
pemë, që fusha e fjalës do të jetë e vërtetë,

1042
00:46:37,190 --> 00:46:41,990
e cila është konceptualisht kontrolluar off, ose
ne jemi tërhequr këtë trekëndësh, po ka

1043
00:46:41,990 --> 00:46:44,080
është një fjalë ketu.

1044
00:46:44,080 --> 00:46:45,120
>> Pra, kjo është një trie.

1045
00:46:45,120 --> 00:46:48,540
Dhe tani pyetja është, çfarë
është koha iken e saj?

1046
00:46:48,540 --> 00:46:49,930
A është kjo e madhe O n?

1047
00:46:49,930 --> 00:46:51,410
A është kjo diçka tjetër?

1048
00:46:51,410 --> 00:46:57,330
E pra, në qoftë se ju keni n emra në këto të dhëna
Struktura, Maxwell duke qenë vetëm një nga

1049
00:46:57,330 --> 00:47:02,330
ata, çfarë është hera drejtimin e
futur apo gjetjen Maxwell?

1050
00:47:02,330 --> 00:47:06,230

1051
00:47:06,230 --> 00:47:09,050
Cila është koha running
i futur Maxwell?

1052
00:47:09,050 --> 00:47:11,740
Nëse ka emra të tjerë n
tashmë në tryezë?

1053
00:47:11,740 --> 00:47:12,507
Po?

1054
00:47:12,507 --> 00:47:15,429
>> STUDENT: [padëgjueshme].

1055
00:47:15,429 --> 00:47:17,550
>> Kryetari 1: Po, kjo është gjatësia
e emrit, e drejtë?

1056
00:47:17,550 --> 00:47:24,420
Pra, M-a-x-W-e-l-l kështu ai ndjehet si kjo
Algorithm është i madh o të shtatë.

1057
00:47:24,420 --> 00:47:26,580
Tani, sigurisht, emri
do të ndryshojnë në gjatësi.

1058
00:47:26,580 --> 00:47:27,380
Ndoshta kjo është një emër të shkurtër.

1059
00:47:27,380 --> 00:47:28,600
Ndoshta kjo është një emër më të gjatë.

1060
00:47:28,600 --> 00:47:33,390
Por ajo që është kyç këtu është se
kjo është një numër konstant.

1061
00:47:33,390 --> 00:47:36,810
Dhe ndoshta kjo nuk është e vërtetë konstante,
Por Perëndia, qoftë reale, në një

1062
00:47:36,810 --> 00:47:41,570
, fjalor nuk ka ndoshta disa kufi
në numrin e shkronjave në një

1063
00:47:41,570 --> 00:47:43,820
Emri personi në një vend të veçantë.

1064
00:47:43,820 --> 00:47:46,940
>> Dhe kështu që ne mund të supozojmë se
Vlera është një konstante.

1065
00:47:46,940 --> 00:47:47,750
Unë nuk e di se çfarë është ajo.

1066
00:47:47,750 --> 00:47:50,440
Kjo është ndoshta më e madhe se
ne mendojmë se është.

1067
00:47:50,440 --> 00:47:52,720
Sepse ka gjithmonë disa qoshe
rasti me një emër të çmendur të gjatë.

1068
00:47:52,720 --> 00:47:56,360
Pra, le të thërrasë atë k, por ajo është ende një
me sa duket konstant, sepse çdo

1069
00:47:56,360 --> 00:48:00,190
përmendur në të botës, të paktën në një
vend të veçantë, është se gjatësia ose

1070
00:48:00,190 --> 00:48:01,780
të shkurtër, kështu që është konstante.

1071
00:48:01,780 --> 00:48:04,490
Por, kur e kemi thënë diçka është e madhe
O i një vlere konstante, çfarë është që

1072
00:48:04,490 --> 00:48:07,760
me të vërtetë ekuivalente me?

1073
00:48:07,760 --> 00:48:10,420
Kjo është me të vërtetë e njëjta gjë
të ketë thënë kohë konstante.

1074
00:48:10,420 --> 00:48:11,530
>> Tani ne jemi lloj i mashtrimit, e drejtë?

1075
00:48:11,530 --> 00:48:15,340
Ne jemi lloj i leveraging disa teori
këtu për të thënë se mirë, rendi i është k

1076
00:48:15,340 --> 00:48:17,450
Urdhri i vërtetë vetëm një,
dhe kjo është koha konstante.

1077
00:48:17,450 --> 00:48:18,200
Por kjo është me të vërtetë.

1078
00:48:18,200 --> 00:48:22,550
Sepse Insajt kyç këtu është se
në qoftë se ne kemi n emra tashmë në këtë

1079
00:48:22,550 --> 00:48:26,010
Struktura e të dhënave, dhe ne insert Maxwell,
është sasia e kohës që na merr për të

1080
00:48:26,010 --> 00:48:29,530
Maxwell futur fare prekur
nga sa njerëzit e tjerë

1081
00:48:29,530 --> 00:48:31,100
janë në strukturën e të dhënave?

1082
00:48:31,100 --> 00:48:31,670
Nuk duket të jetë.

1083
00:48:31,670 --> 00:48:36,280
Po të kisha një miliard elemente shumë për këtë
trie, dhe pastaj futur Maxwell, është

1084
00:48:36,280 --> 00:48:38,650
ai në të gjithë të prekur?

1085
00:48:38,650 --> 00:48:39,050
Jo.

1086
00:48:39,050 --> 00:48:42,950
Dhe kjo është ndryshe nga ndonjë prej të dhënave ditë
Strukturat e kemi parë deri më tani, ku

1087
00:48:42,950 --> 00:48:46,820
Ora drejtimin e algorithm tuaj është
plotësisht i pavarur nga sa

1088
00:48:46,820 --> 00:48:51,430
stuff është ose nuk është tashmë
në atë strukturën e të dhënave.

1089
00:48:51,430 --> 00:48:54,650
>> Dhe aq me teper qe kjo tani është një
mundësi për të vendosur p gjashtë, e cila do

1090
00:48:54,650 --> 00:48:58,310
përsëri të përfshijë zbatimin mesi juaj
spell checker, duke lexuar në 150,000

1091
00:48:58,310 --> 00:49:01,050
fjalë të tjera, sa më të mirë për të ruajtur që
nuk është domosdoshmërisht e qartë.

1092
00:49:01,050 --> 00:49:04,030
Dhe pse unë kam aspiroi për të gjetur
Grail shenjtë, unë nuk bëj

1093
00:49:04,030 --> 00:49:05,330
pretendojnë se është një trie.

1094
00:49:05,330 --> 00:49:09,810
Në fakt, një tabelë hash shumë mirë mund të
të provojë të jetë shumë më efikase.

1095
00:49:09,810 --> 00:49:10,830
Por ata janë vetëm -

1096
00:49:10,830 --> 00:49:14,620
kjo është vetëm një nga vendimet e dizajnit
ju do të keni për të bërë.

1097
00:49:14,620 --> 00:49:18,920
>> Por në mbylljen e le të marrin 50 ose kështu
sekonda për të marrë një vështrim në atë që qëndron

1098
00:49:18,920 --> 00:49:22,190
përpara javën e ardhshme dhe më tej ne tranzicion
nga kjo command line

1099
00:49:22,190 --> 00:49:26,220
nëse botërore programe C për gjëra web
bazuar dhe gjuhët si PHP dhe

1100
00:49:26,220 --> 00:49:30,350
JavaScript dhe Interneti në vetvete,
protokollet si HTTP, të cilat ju keni

1101
00:49:30,350 --> 00:49:32,870
marrë për të dhënë për vite
tani, dhe më të shtypur çdo

1102
00:49:32,870 --> 00:49:34,440
ditë, ndoshta, apo shihet.

1103
00:49:34,440 --> 00:49:37,420
Dhe ne do të fillojë të zhvishem përsëri
Shtresat e çfarë është interneti.

1104
00:49:37,420 --> 00:49:40,650
Dhe çfarë është kodi që
nënvizon mjetet e sotme.

1105
00:49:40,650 --> 00:49:43,230
Kështu 50 sekonda e këtij teaser këtu.

1106
00:49:43,230 --> 00:49:46,570
Unë ju jap Warriors e neto.

1107
00:49:46,570 --> 00:49:51,370
>> [Video playback]

1108
00:49:51,370 --> 00:49:56,764
>> -Ai erdhi me një mesazh.

1109
00:49:56,764 --> 00:50:00,687
Me një protokoll të gjithë të tijat.

1110
00:50:00,687 --> 00:50:13,370

1111
00:50:13,370 --> 00:50:19,780
Ai erdhi për një botë të firewalls mizore,
routers pakujdesshëm, dhe rreziqet larg

1112
00:50:19,780 --> 00:50:22,600
keq se vdekja.

1113
00:50:22,600 --> 00:50:23,590
Ai është i shpejtë.

1114
00:50:23,590 --> 00:50:25,300
Ai është i fortë.

1115
00:50:25,300 --> 00:50:27,700
Ai është TCPIP.

1116
00:50:27,700 --> 00:50:30,420
Dhe ai e mori adresën tuaj.

1117
00:50:30,420 --> 00:50:32,920

1118
00:50:32,920 --> 00:50:34,590
Warriors e neto.

1119
00:50:34,590 --> 00:50:35,290
>> [VIDEO END rishikim]

1120
00:50:35,290 --> 00:50:38,070
>> Kryetari 1: Kjo është se si interneti
do të punojë si i javës së ardhshme.

1121
00:50:38,070 --> 00:50:40,406