1
00:00:00,000 --> 00:00:10,900

2
00:00:10,900 --> 00:00:15,860
>> SPEAKER 1: Okei, joten tämä on
CS50 Tämä on viikon lopussa viisi.

3
00:00:15,860 --> 00:00:19,220
Ja muistaa, että viimeinen kerta
alkoi tarkastella harrastaja tiedot

4
00:00:19,220 --> 00:00:22,310
rakenteiden alkoi ratkaista
ongelmia, jotka alkoivat ottaa käyttöön

5
00:00:22,310 --> 00:00:25,640
uusia ongelmia, mutta avain tähän
oli sellainen ketjuttaminen että me

6
00:00:25,640 --> 00:00:27,940
alkoi tehdä solmusta toiseen.

7
00:00:27,940 --> 00:00:30,085
Joten tämä on tietenkin
yksittäin linkitetyn listan.

8
00:00:30,085 --> 00:00:31,960
Ja yksittäin liittyy,
Siis siellä on vain yksi

9
00:00:31,960 --> 00:00:33,380
kierre jokaisen näistä solmuja.

10
00:00:33,380 --> 00:00:35,890
Osoittautuu voit tehdä harrastaja
asioita, kuten kaksin verroin liittyvät luettelot

11
00:00:35,890 --> 00:00:38,470
jolloin sinulla nuoli
menee molempiin suuntiin, joka

12
00:00:38,470 --> 00:00:40,320
voi auttaa tiettyjen tehokkuusetuja.

13
00:00:40,320 --> 00:00:42,000
Mutta tämä ratkaisi ongelman?

14
00:00:42,000 --> 00:00:43,500
Mikä ongelma ei tässä ratkaista?

15
00:00:43,500 --> 00:00:46,620
Miksi välitämme maanantaina?

16
00:00:46,620 --> 00:00:49,820
Miksi, teoriassa, ei välitämme maanantaina?

17
00:00:49,820 --> 00:00:50,630
Mitä se tekee?

18
00:00:50,630 --> 00:00:51,950
>> Yleisö: Voimme dynaamisesti muuttaa sen kokoa.

19
00:00:51,950 --> 00:00:53,740
>> SPEAKER 1: OK, joten voimme
dynaamisesti muuttaa sen kokoa.

20
00:00:53,740 --> 00:00:54,710
Hyvin tehty molemmat.

21
00:00:54,710 --> 00:00:57,560
Joten voit dynaamisesti muuttaa tätä
tietorakenne, kun taas array,

22
00:00:57,560 --> 00:01:00,760
Recall, sinun täytyy tietää
priori kuinka paljon tilaa haluat

23
00:01:00,760 --> 00:01:03,870
ja jos tarvitset hieman enemmän
tilaa, olet eräänlainen onnea.

24
00:01:03,870 --> 00:01:05,560
Sinun on luotava kokonaan uusi joukko.

25
00:01:05,560 --> 00:01:07,893
Sinun täytyy siirtää kaikki
tietoja toisiinsa,

26
00:01:07,893 --> 00:01:10,600
lopulta vapauttaa vanha array
jos voit, ja jatka sitten.

27
00:01:10,600 --> 00:01:13,891
Joka vain tuntuu erittäin kallista ja hyvin
tehoton, ja se todellakin voi olla.

28
00:01:13,891 --> 00:01:14,890
Mutta tämä ei ole kaikki hyviä.

29
00:01:14,890 --> 00:01:18,180
Me maksamme hintaa, mikä oli yksi
selvempi hintoja me

30
00:01:18,180 --> 00:01:20,550
maksaa käyttämällä linkitettyä listaa?

31
00:01:20,550 --> 00:01:22,825
>> Yleisö: Meidän on käytettävä
kaksinkertainen tilaa jokaiselle.

32
00:01:22,825 --> 00:01:25,200
SPEAKER 1: Joo, joten tarvitsemme
vähintään kaksi kertaa niin paljon tilaa.

33
00:01:25,200 --> 00:01:27,700
Itse tajusin tätä kuvaa n
jopa hieman harhaanjohtava,

34
00:01:27,700 --> 00:01:32,200
koska on CS50 IDE paljon nykyaikaisen
tietokoneet, osoitin tai osoite

35
00:01:32,200 --> 00:01:33,700
ei itse asiassa neljä tavua.

36
00:01:33,700 --> 00:01:36,090
Se on hyvin usein nämä
päivää kahdeksan tavua, joka

37
00:01:36,090 --> 00:01:38,530
tarkoittaa alimmainen
suorakulmioita siellä todellisuudessa

38
00:01:38,530 --> 00:01:40,900
ovat sellaisia ​​kaksi kertaa
iso kuin mitä olen piirretään,

39
00:01:40,900 --> 00:01:44,409
mikä tarkoittaa käytät kolme kertaa
paljon tilaa kuin meillä olisi muuten.

40
00:01:44,409 --> 00:01:46,700
Nyt samaan aikaan, olemme
vielä puhuessaan tavua, eikö?

41
00:01:46,700 --> 00:01:49,140
Emme välttämättä puhu
gigabitteinä,

42
00:01:49,140 --> 00:01:51,000
jollei näitä tietorakenteita saada iso.

43
00:01:51,000 --> 00:01:54,510
>> Ja niin tänään alkaa harkita
miten voisimme tutkia tiedot

44
00:01:54,510 --> 00:01:57,310
tehokkaammin jos
Itse asiassa tiedot suurenee.

45
00:01:57,310 --> 00:02:00,360
Mutta yritetään muunna
toiminta ensimmäinen

46
00:02:00,360 --> 00:02:02,460
että voit tehdä näitä
erilaisia ​​tietorakenteita.

47
00:02:02,460 --> 00:02:04,790
Joten jotain liittyy
lista tukee yleisesti

48
00:02:04,790 --> 00:02:07,514
toimintoja, kuten poistaa,
lisätä, ja etsi.

49
00:02:07,514 --> 00:02:08,639
Ja mitä minä tarkoitan, että?

50
00:02:08,639 --> 00:02:11,222
Se vain tarkoittaa, että yleensä,
jos ihmiset käyttävät linkitetty lista,

51
00:02:11,222 --> 00:02:14,287
he tai joku muu on toteuttanut
toimintoja, kuten poistaa, lisätä,

52
00:02:14,287 --> 00:02:16,120
ja haku, joten voit
itse tehdä jotain

53
00:02:16,120 --> 00:02:18,030
hyödyllinen tietorakenne.

54
00:02:18,030 --> 00:02:20,760
Joten ottaa vilkaista
miten voisimme toteuttaa

55
00:02:20,760 --> 00:02:24,530
Joissakin koodi linkitetyn listan seuraavasti.

56
00:02:24,530 --> 00:02:27,885
>> Joten tämä on vain joitakin C-koodia,
ei edes täydellinen ohjelma

57
00:02:27,885 --> 00:02:29,260
että olen todella nopeasti lyöty jopa.

58
00:02:29,260 --> 00:02:32,300
Se ei ole verkossa jakelussa
koodi, koska se ei todella ajaa.

59
00:02:32,300 --> 00:02:33,790
Mutta huomaa Olen juuri
jossa kommentti sanoi,

60
00:02:33,790 --> 00:02:36,130
dot dot dot, on jotain
siellä, piste piste piste, jotain siellä.

61
00:02:36,130 --> 00:02:38,410
Ja nyt vain katsoa
mitä mehukas osat ovat.

62
00:02:38,410 --> 00:02:40,790
Niin linjalla kolme,
muistuttaa, että tämä on nyt

63
00:02:40,790 --> 00:02:45,960
ehdotimme julistamisesta solmu viime
aika, yksi niistä suorakulmainen esineitä.

64
00:02:45,960 --> 00:02:48,790
Se on int että soitamme N,
mutta voisimme kutsua sitä jotain,

65
00:02:48,790 --> 00:02:51,920
ja sitten struct solmu tähti sanottujen seuraavan.

66
00:02:51,920 --> 00:02:55,520
Ja vain tehdä selväksi, että toinen
linja, rivillä kuusi, mikä se on?

67
00:02:55,520 --> 00:02:57,930
Mitä se tekee meille?

68
00:02:57,930 --> 00:03:01,044
Koska se varmasti näyttää enemmän
arvoituksellinen kuin tavallisia muuttujia.

69
00:03:01,044 --> 00:03:02,740
>> Yleisö: Se tekee siirtyä yksi.

70
00:03:02,740 --> 00:03:04,650
>> SPEAKER 1: Se tekee sen liikkua yli.

71
00:03:04,650 --> 00:03:08,580
Ja tarkemmin sanottuna,
se tallentaa osoite

72
00:03:08,580 --> 00:03:11,582
solmun, joka on tarkoitus olla
semanttisesti sen vieressä, eikö?

73
00:03:11,582 --> 00:03:13,540
Joten se ei tule
välttämättä siirrä mitään.

74
00:03:13,540 --> 00:03:15,290
Se on vain menossa
tallentaa arvon, joka on

75
00:03:15,290 --> 00:03:17,170
olemaan osoitteeseen
joidenkin muiden solmun,

76
00:03:17,170 --> 00:03:20,810
ja siksi olemme sanoneet struct
solmu tähti, tähti ilmaiseva

77
00:03:20,810 --> 00:03:22,370
osoitin tai osoite.

78
00:03:22,370 --> 00:03:26,390
OK, joten nyt jos oletetaan, että meillä on
tämä N käytettävissämme, ja nyt

79
00:03:26,390 --> 00:03:29,490
olettaa, että joku muu on
Lisätään koko joukko kokonaislukuja

80
00:03:29,490 --> 00:03:30,400
osaksi linkitetty lista.

81
00:03:30,400 --> 00:03:35,640
Ja että linkitetty lista on
osoitteen sivulle jossain vaiheessa

82
00:03:35,640 --> 00:03:39,040
muuttuja nimeltä lista, joka on
hyväksyttiin täällä parametri,

83
00:03:39,040 --> 00:03:43,120
miten voin mennä noin linja
14 täytäntöönpanosta haku?

84
00:03:43,120 --> 00:03:45,990
Toisin sanoen, jos olen täytäntöönpanosta
jonka tehtävänä elämässä

85
00:03:45,990 --> 00:03:48,889
on otettava int ja sitten
alussa linkitetty lista,

86
00:03:48,889 --> 00:03:50,430
että on osoitin linkitetyn listan.

87
00:03:50,430 --> 00:03:52,992
Kuten ensimmäinen, joka mielestäni David
oli meidän vapaaehtoinen maanantaina,

88
00:03:52,992 --> 00:03:54,700
hän oli suunnattu
koko linkitetty lista,

89
00:03:54,700 --> 00:03:57,820
se on ikään kuin me ohimennen
David meidän argumentti täällä.

90
00:03:57,820 --> 00:03:59,990
Miten edetä liikkumisesta tämä lista?

91
00:03:59,990 --> 00:04:04,640
No, käy ilmi, että vaikka
osoittimet ovat suhteellisen uusi nyt meille,

92
00:04:04,640 --> 00:04:07,010
voimme tehdä tämän suhteellisen
mutkattomasti.

93
00:04:07,010 --> 00:04:09,500
>> Aion mennä eteenpäin ja
julistaa väliaikainen muuttuja, joka

94
00:04:09,500 --> 00:04:12,364
sovitun käytännön on juuri menossa
kutsua osoitin, tai PTR,

95
00:04:12,364 --> 00:04:14,030
mutta voit kutsua sitä mitä haluat.

96
00:04:14,030 --> 00:04:16,470
Ja aion alustaa
sen alkua luettelon.

97
00:04:16,470 --> 00:04:20,050
Voit siis sellaista ajatella tämän
kuten minulle opettaja toinen päivä,

98
00:04:20,050 --> 00:04:23,580
sellainen suunnattu joku
keskuudessa ihmisten vapaaehtoisina.

99
00:04:23,580 --> 00:04:26,470
Joten olen väliaikainen muuttuja, joka on
vain suunnattu sama asia

100
00:04:26,470 --> 00:04:31,390
että sattumalta nimetty
vapaaehtoinen David oli myös muistuttaa.

101
00:04:31,390 --> 00:04:35,440
Nyt kun osoitin on
ei null, koska muistaa

102
00:04:35,440 --> 00:04:40,350
että null on joitakin erityisiä Sentinel arvo
rajataan listan loppuun,

103
00:04:40,350 --> 00:04:44,280
joten vaikka en ole suunnattu
maahan kuin meidän viime vapaaehtoisten

104
00:04:44,280 --> 00:04:47,190
oli, mennään eteenpäin
ja toimi seuraavasti.

105
00:04:47,190 --> 00:04:51,820
Jos pointer-- ja nyt olen sellainen haluavat
tehdä, mitä teimme opiskelija

106
00:04:51,820 --> 00:04:57,410
structure-- jos osoitin piste seuraava
equals-- pikemminkin, jos osoitin piste n on

107
00:04:57,410 --> 00:05:02,290
on yhtä suuri kuin muuttuja N,
väite joka on ohitettu,

108
00:05:02,290 --> 00:05:05,370
sitten haluan mennä eteenpäin
ja sano palata totta.

109
00:05:05,370 --> 00:05:11,020
Olen löytänyt lukumäärä N sisäpuoli
yksi solmuista minun linkitetyn listan.

110
00:05:11,020 --> 00:05:13,500
Mutta piste ei enää
toimii tässä yhteydessä,

111
00:05:13,500 --> 00:05:17,260
koska osoitin, PTR, on
todellakin osoitin, osoite,

112
00:05:17,260 --> 00:05:20,632
me oikeastaan ​​voi ihanan
käyttää lopulta pala syntaksin

113
00:05:20,632 --> 00:05:22,590
sellainen merkkeihin
intuitiivinen tunne ja todella

114
00:05:22,590 --> 00:05:27,870
Käytä nuoli täällä, mikä tarkoittaa menevät
että osoite kokonaisluku siellä.

115
00:05:27,870 --> 00:05:30,160
Joten se on hyvin samankaltainen
henki piste operaattori,

116
00:05:30,160 --> 00:05:33,860
mutta koska osoitin ei ole osoitin
eikä varsinaista struct itse,

117
00:05:33,860 --> 00:05:35,380
me vain nuolinäppäimillä.

118
00:05:35,380 --> 00:05:40,620
>> Joten jos nykyinen solmu, että minä,
väliaikainen muuttuja, olen osoittaen

119
00:05:40,620 --> 00:05:43,060
ei ole N, mitä haluan tehdä?

120
00:05:43,060 --> 00:05:45,910
No, minun ihmisen vapaaehtoisten
että meillä oli täällä toinen päivä,

121
00:05:45,910 --> 00:05:49,710
jos ensimmäinen ihmisen ei ole minun
haluavat, ja ehkä toinen ihmisen ei ole

122
00:05:49,710 --> 00:05:52,660
yksi haluan, ja kolmanneksi, I
täytyy pitää fyysisesti liikkuvat.

123
00:05:52,660 --> 00:05:54,690
Kuten miten voin selata lista?

124
00:05:54,690 --> 00:05:57,470
Kun meillä oli jono, te
vain teimme kuten minä plus plus.

125
00:05:57,470 --> 00:06:03,660
Mutta tässä tapauksessa riittää, kun
do osoitin, saa, osoitin, seuraavaksi.

126
00:06:03,660 --> 00:06:07,580
Toisin sanoen, seuraavan kentän
on kuin kaikki jäljellä käsissä

127
00:06:07,580 --> 00:06:10,880
että meidän vapaaehtoisille ihmisille maanantaina
käyttivät pisteeseen joitakin muita solmuun.

128
00:06:10,880 --> 00:06:12,890
Ne olivat seuraavaa naapureita.

129
00:06:12,890 --> 00:06:17,060
>> Joten jos haluan selata tähän luetteloon,
En voi vain tehdä minä plus plus enää,

130
00:06:17,060 --> 00:06:20,120
Olen sen sijaan on sanottava
Minä, osoitin, on menossa

131
00:06:20,120 --> 00:06:24,650
yhtä suureksi riippumatta seuraavaan kenttään on,
seuraava kenttä, seuraava kenttä on,

132
00:06:24,650 --> 00:06:28,350
seuraavat kaikki nämä jäljellä käsissä
että meillä oli lavalla osoittelee

133
00:06:28,350 --> 00:06:30,000
Joidenkin myöhemmin arvoja.

134
00:06:30,000 --> 00:06:32,590
Ja jos saan läpi
että koko iteraation

135
00:06:32,590 --> 00:06:39,330
ja lopuksi, osuin null, joilla ei ole
löytyi N vielä, minä vain return false.

136
00:06:39,330 --> 00:06:44,100
Joten jälleen, kaikki että teemme täällä,
kohti kuvan hetki sitten,

137
00:06:44,100 --> 00:06:47,840
alkaa osoittamalla
luettelon alussa oletettavasti.

138
00:06:47,840 --> 00:06:50,970
Ja sitten voin tarkistaa, on arvo
Etsin yhtä yhdeksän?

139
00:06:50,970 --> 00:06:52,650
Jos näin on, palaan totta ja olen valmis.

140
00:06:52,650 --> 00:06:56,450
Jos ei, voin päivittää käsi,
AKA osoitin, kohtaan

141
00:06:56,450 --> 00:06:59,540
seuraavassa nuolen sijainti, ja
niin seuraava nuolen sijainti,

142
00:06:59,540 --> 00:07:00,480
ja seuraava.

143
00:07:00,480 --> 00:07:03,770
Olen yksinkertaisesti kävelemällä tämän taulukon.

144
00:07:03,770 --> 00:07:06,010
>> Joten jälleen, who cares?

145
00:07:06,010 --> 00:07:07,861
Kuten mitä on tämä ainesosa?

146
00:07:07,861 --> 00:07:10,360
No, muistuttaa, että otimme käyttöön
käsite pino, joka

147
00:07:10,360 --> 00:07:15,400
on abstrakti tietotyyppi sikäli kuin se on
ei C asia, se ei ole CS50 asia,

148
00:07:15,400 --> 00:07:19,430
se abstrakti ajatus, tämä ajatus
pinoaminen asiat päällekkäin toistensa

149
00:07:19,430 --> 00:07:21,820
että voidaan toteuttaa
rypäleterttuja eri tavoin.

150
00:07:21,820 --> 00:07:25,600
Ja yksi tapa ehdotimme oli kanssa
array, tai linkitetty lista.

151
00:07:25,600 --> 00:07:29,570
Ja käy ilmi, että kanonisesti,
pino tukee ainakin kaksi operaatiota.

152
00:07:29,570 --> 00:07:32,320
Ja sirinä sanat ovat push, että
työntää jotain pinoon,

153
00:07:32,320 --> 00:07:34,770
kuten uusi lokero
ruokasalissa, tai pop,

154
00:07:34,770 --> 00:07:39,000
mikä tarkoittaa poistaa ylimmän
lokero pinosta dining

155
00:07:39,000 --> 00:07:41,500
sali, ja sitten ehkä joitakin
muut toiminnot samoin.

156
00:07:41,500 --> 00:07:45,770
Miten me voimme määritellä rakenne
että olemme nyt soittaa pino?

157
00:07:45,770 --> 00:07:50,020
>> No, meillä on kaikki tarvittavat
syntaksi käytössämme C. sanon,

158
00:07:50,020 --> 00:07:53,830
antaa minulle eräänlainen määritelmä
struct sisällä pino,

159
00:07:53,830 --> 00:07:58,030
Aion sanoa on joukko, on
koko joukko numeroita ja sitten koko.

160
00:07:58,030 --> 00:08:00,930
Eli toisin sanoen, jos haluan
toteuttaa tämän koodin,

161
00:08:00,930 --> 00:08:03,830
anna minun mennä ja juuri sellainen
piirtää mitä tämä sanoo.

162
00:08:03,830 --> 00:08:06,317
Joten tämä sanoo, anna minulle
rakenne, joka sai array,

163
00:08:06,317 --> 00:08:09,400
ja en tiedä mitä kapasiteetti on,
se on ilmeisesti joitakin vakio, että olen

164
00:08:09,400 --> 00:08:10,858
määritelty muualla, ja se käy hyvin.

165
00:08:10,858 --> 00:08:15,260
Mutta kai se on vain yksi,
kaksi, kolme, neljä, viisi.

166
00:08:15,260 --> 00:08:16,700
Joten kapasiteetti on 5.

167
00:08:16,700 --> 00:08:21,730
Tämä elementti sisällä minun
rakenne kutsutaan numerot.

168
00:08:21,730 --> 00:08:24,020
Ja sitten tarvitsen yksi
muut muuttuvat ilmeisesti

169
00:08:24,020 --> 00:08:27,814
nimeltään koko että aluksi aion
säätää alustetaan nollaksi.

170
00:08:27,814 --> 00:08:29,730
Jos ei mitään
pino, koko on nolla,

171
00:08:29,730 --> 00:08:31,420
ja se on roskaa arvot numeroina.

172
00:08:31,420 --> 00:08:33,450
Minulla ei ole aavistustakaan mitä siellä vielä.

173
00:08:33,450 --> 00:08:36,059
>> Joten jos haluan ajaa
jotain pinoon,

174
00:08:36,059 --> 00:08:40,780
kai soittaa toiminto push, ja
Sanon push 50, kuten numero 50,

175
00:08:40,780 --> 00:08:44,090
jossa ehdottaisitte
Piirsin sitä tässä array?

176
00:08:44,090 --> 00:08:47,124
On viisi eri vastausvaihtoehtoa.

177
00:08:47,124 --> 00:08:48,790
Missä haluat ajaa numero 50?

178
00:08:48,790 --> 00:08:51,899
Jos tavoitteena täällä, taas, soita
toiminto push, kulkea argumentti

179
00:08:51,899 --> 00:08:52,940
50, jossa voin laittaa sen?

180
00:08:52,940 --> 00:08:55,680

181
00:08:55,680 --> 00:08:59,052
Viisi possible-- 20% mahdollisuus
arvaamaan oikein.

182
00:08:59,052 --> 00:08:59,896
Kyllä?

183
00:08:59,896 --> 00:09:00,740
>> Yleisö: Äärimmäisenä oikealla.

184
00:09:00,740 --> 00:09:01,990
>> SPEAKER 1: Äärimmäisenä oikealla.

185
00:09:01,990 --> 00:09:08,359
Nyt 25% mahdollisuus
arvaamaan oikein.

186
00:09:08,359 --> 00:09:09,650
Jotta olisi todella hienoa.

187
00:09:09,650 --> 00:09:12,770
Sovitun käytännön sanon jossa joukko,
olisimme yleensä alkaa vasemmalla,

188
00:09:12,770 --> 00:09:14,519
mutta voisimme varmasti
alkavat oikeaan.

189
00:09:14,519 --> 00:09:17,478
Joten spoileri tässä olisi olen
luultavasti piirtää sen vasemmalla,

190
00:09:17,478 --> 00:09:20,060
aivan kuten normaalissa array jossa
I alkaa menee vasemmalta oikealle.

191
00:09:20,060 --> 00:09:21,780
Mutta jos voit kääntää
aritmeettinen, hieno.

192
00:09:21,780 --> 00:09:23,060
Se vain ei ole tavanomaista.

193
00:09:23,060 --> 00:09:24,880
OK, minun täytyy tehdä yksi
lisää muutos kuitenkin.

194
00:09:24,880 --> 00:09:27,710
Nyt kun olen ajanut jotain
pinoon, mitä seuraavaksi?

195
00:09:27,710 --> 00:09:29,400
>> Okei, minun täytyy kasvattaa koko.

196
00:09:29,400 --> 00:09:32,600
Joten anna minun mennä eteenpäin ja vain
päivittää tämän, joka oli nolla.

197
00:09:32,600 --> 00:09:35,950
Ja sen sijaan nyt, aion
laittaa arvon yksi.

198
00:09:35,950 --> 00:09:39,460
Ja nyt kai työntää toisen
numero pinoon, kuten 51.

199
00:09:39,460 --> 00:09:42,680
No, minun täytyy tehdä yksi
muutos, joka on jopa koko kaksi.

200
00:09:42,680 --> 00:09:46,100
Ja sitten kai raivata lisää
numero pinoon kuten 61,

201
00:09:46,100 --> 00:09:52,530
nyt minun täytyy päivittää koko yksi
aika, ja saada arvo 3, kun koko.

202
00:09:52,530 --> 00:09:54,690
Ja nyt kai soittaa pop.

203
00:09:54,690 --> 00:09:57,250
Nyt pop Sopimuksen mukaan
ei anneta argumentteja.

204
00:09:57,250 --> 00:10:00,430
Pino, koko
kohta lokeron metafora

205
00:10:00,430 --> 00:10:03,450
on, että sinulla ei ole harkintavaltaa
mennä saada, että tarjotin, kaikki mitä voi tehdä

206
00:10:03,450 --> 00:10:06,330
on pop ylin yksi
pino, vain siksi.

207
00:10:06,330 --> 00:10:08,010
Sitähän tämä tietorakenne ei.

208
00:10:08,010 --> 00:10:12,250
>> Joten että logiikka jos minä
sanoa pop, mikä irtoaa?

209
00:10:12,250 --> 00:10:13,080
Niin 61.

210
00:10:13,080 --> 00:10:15,402
Joten mitä todella on tietokone
aikoo tehdä muistiin?

211
00:10:15,402 --> 00:10:16,610
Mitä minun koodi on tehtävä?

212
00:10:16,610 --> 00:10:20,330
Mitä ehdottaisitte
muutamme ruudulla?

213
00:10:20,330 --> 00:10:23,410
Mitä pitäisi muuttaa?

214
00:10:23,410 --> 00:10:24,960
Anteeksi?

215
00:10:24,960 --> 00:10:26,334
Joten pääsemme eroon 61.

216
00:10:26,334 --> 00:10:27,500
Joten en voi varmasti tehdä sen.

217
00:10:27,500 --> 00:10:28,640
Ja voin päästä eroon 61.

218
00:10:28,640 --> 00:10:30,980
Ja sitten mitä muut
muutos täytyy tapahtua?

219
00:10:30,980 --> 00:10:33,160
Koko luultavasti on palattava kaksi.

220
00:10:33,160 --> 00:10:34,210
Ja niin se on hieno.

221
00:10:34,210 --> 00:10:36,690
Mutta hetkinen, koko
hetki sitten oli kolme.

222
00:10:36,690 --> 00:10:38,240
Haluan vain tehdä nopeasti järki tarkistaa.

223
00:10:38,240 --> 00:10:41,810
Kuinka me tiedämme, että me
halusi päästä eroon 61?

224
00:10:41,810 --> 00:10:42,760
Koska olemme popping.

225
00:10:42,760 --> 00:10:46,450
Ja niin minulla on tämä toinen ominaisuus koko.

226
00:10:46,450 --> 00:10:48,470
>> Hetkinen, olen
Muistelen viikko kaksi

227
00:10:48,470 --> 00:10:51,660
kun aloimme puhua
taulukot, jossa tämä oli paikka nolla,

228
00:10:51,660 --> 00:10:55,920
tämä oli paikalla yksi, tämä oli paikka
kaksi, tämä on paikka kolme, neljä,

229
00:10:55,920 --> 00:10:58,460
se näyttää
suhde koko

230
00:10:58,460 --> 00:11:02,780
ja elementti, että haluan poistaa
alkaen array näyttää vain olla mitä?

231
00:11:02,780 --> 00:11:05,120
Koko miinus yksi.

232
00:11:05,120 --> 00:11:07,786
Ja jotta Näin ihmisinä
Tiedämme 61 tulee ensin.

233
00:11:07,786 --> 00:11:09,160
Miten tietokone menee tietää?

234
00:11:09,160 --> 00:11:11,701
Kun koodi, jossa luultavasti
haluavat tehdä koko miinus yksi,

235
00:11:11,701 --> 00:11:14,950
joten kolme miinus yksi on kaksi, ja että
tarkoittaa, että haluamme päästä eroon 61.

236
00:11:14,950 --> 00:11:18,000
Ja sitten voimme todellakin päivittää
kokoa niin, että koko nyt

237
00:11:18,000 --> 00:11:20,300
menee kolmesta vain kaksi.

238
00:11:20,300 --> 00:11:24,520
Ja vain olla pikkutarkka, aion
ehdottaa, että olen valmis, eikö?

239
00:11:24,520 --> 00:11:27,660
Ehdotitte intuitiivisesti
oikein minun pitäisi päästä eroon 61.

240
00:11:27,660 --> 00:11:30,700
Mutta ei ole Olen sellainen
tavallaan päässyt eroon 61?

241
00:11:30,700 --> 00:11:33,790
Olen tehokkaasti unohtanut
että se on itse siellä.

242
00:11:33,790 --> 00:11:37,680
Ja muistelen PSET4, jos olet lukenut
artikkeli Forensics, PDF

243
00:11:37,680 --> 00:11:40,780
että meillä oli te lukea, tai et
lukee tällä viikolla PSET4.

244
00:11:40,780 --> 00:11:44,300
Muista, että tämä on todella germane
koko ajatus tietokone oikeus.

245
00:11:44,300 --> 00:11:47,820
Mikä tietokone yleensä tekee, on
se vain unohtaa missä jotain on,

246
00:11:47,820 --> 00:11:51,300
mutta se ei mene sisään ja kuten
yrittää raapia sitä tai ohitus

247
00:11:51,300 --> 00:11:54,560
ne bitit nollia ja ykkösiä
tai jokin muu satunnainen kuvio

248
00:11:54,560 --> 00:11:56,690
ellet itse niin tarkoituksella.

249
00:11:56,690 --> 00:11:58,930
Joten intuitio oli
oikea, nyt päästä eroon 61.

250
00:11:58,930 --> 00:12:00,650
Todellisuudessa emme tarvitse vaivautua.

251
00:12:00,650 --> 00:12:04,040
Meidän täytyy vain unohtaa, että
se on siellä muuttamalla koko.

252
00:12:04,040 --> 00:12:05,662
>> Nyt on ongelma tämän pinon.

253
00:12:05,662 --> 00:12:07,620
Jos minun pitää ajaa asioita
pinoon, mitä

254
00:12:07,620 --> 00:12:11,167
ilmeisesti tule tapahtumaan
vain hetken aikaa?

255
00:12:11,167 --> 00:12:12,500
Aiomme tila loppuu.

256
00:12:12,500 --> 00:12:13,580
Ja mitä me teemme?

257
00:12:13,580 --> 00:12:14,680
Olemme tavallaan ruuvattu.

258
00:12:14,680 --> 00:12:19,000
Tämä täytäntöönpano ei anna
meille kokoa array, koska käyttämällä

259
00:12:19,000 --> 00:12:21,240
tämä syntaksi, jos
muistelen viikolla kaksi,

260
00:12:21,240 --> 00:12:23,520
kun olet julistanut
koko joukko,

261
00:12:23,520 --> 00:12:26,780
emme ole nähneet mekanismia vielä jossa
voit muuttaa taulukon koko.

262
00:12:26,780 --> 00:12:29,020
Ja todellakin C ei ole kyseistä ominaisuutta.

263
00:12:29,020 --> 00:12:32,524
Jos sanot antaa minulle viisi
Nths, soita heille numerot,

264
00:12:32,524 --> 00:12:33,940
siinä kaikki aiot saada se.

265
00:12:33,940 --> 00:12:38,790
Joten teemme nyt maanantaina, ovat
kykyä ilmaista ratkaisu

266
00:12:38,790 --> 00:12:42,480
kuitenkin, meidän täytyy vain nipistää
määritelmä meidän pinon

267
00:12:42,480 --> 00:12:46,840
jotta ei olla joitakin kovakoodattuja array,
mutta vain tallentaa osoite.

268
00:12:46,840 --> 00:12:47,890
>> Nyt miksi tämä on?

269
00:12:47,890 --> 00:12:51,690
Nyt meidän täytyy vain olla tyytyväinen
että kun minun ohjelma toimii,

270
00:12:51,690 --> 00:12:53,730
Olen luultavasti menossa
on kysyttävä ihmisen,

271
00:12:53,730 --> 00:12:55,110
kuinka monta numeroa haluat tallentaa?

272
00:12:55,110 --> 00:12:56,776
Joten panos on tultava jostain.

273
00:12:56,776 --> 00:12:59,140
Mutta kun tiedän, että
numero, niin voin vain

274
00:12:59,140 --> 00:13:02,470
käyttää mitä toimia antaa
minulle kimpale muistia?

275
00:13:02,470 --> 00:13:03,580
Voin käyttää malloc.

276
00:13:03,580 --> 00:13:06,710
Ja voin sanoa minkä tahansa määrän
tavua Haluan takaisin näiden Nths.

277
00:13:06,710 --> 00:13:10,910
Ja kaikki minun täytyy tallentaa numerot
vaihteleva täällä sisällä tämän struct

278
00:13:10,910 --> 00:13:13,480
olisi mitä?

279
00:13:13,480 --> 00:13:18,440
Mitä todella menee
numeroita tässä tilanteessa?

280
00:13:18,440 --> 00:13:21,300
Niin, osoitin ensimmäiseen
tavu että kimpale muistia,

281
00:13:21,300 --> 00:13:24,940
tai tarkemmin, osoite
Ensimmäisen näistä tavua.

282
00:13:24,940 --> 00:13:27,300
Ei ole väliä, jos se on yksi
tavu tai miljardi tavua,

283
00:13:27,300 --> 00:13:28,890
Minun täytyy vain välitä ensin.

284
00:13:28,890 --> 00:13:31,530
Koska mitä malloc takuut ja
käyttöjärjestelmää takeita,

285
00:13:31,530 --> 00:13:34,170
on että kimpale muisti I
saada, se tulee olla vierekkäisiä.

286
00:13:34,170 --> 00:13:35,378
Siellä ei tule olemaan aukkoja.

287
00:13:35,378 --> 00:13:38,576
Joten jos olen pyytänyt 50
tavua tai 1000 tavua,

288
00:13:38,576 --> 00:13:40,450
he kaikki olemaan
takaisin takaisin takaisin.

289
00:13:40,450 --> 00:13:44,500
Ja niin kauan kuin muistan, kuinka suuri, kuinka
paljon pyysin, kaikki mitä tarvitsee tietää

290
00:13:44,500 --> 00:13:46,230
on ensimmäinen osoite.

291
00:13:46,230 --> 00:13:48,660
>> Joten nyt meillä on kyky koodi.

292
00:13:48,660 --> 00:13:51,280
Vaikkakin, se vie meitä
enemmän aikaa kirjoittaa tämän ylös,

293
00:13:51,280 --> 00:13:55,900
voisimme nyt kohdentaa että muistia
vain tallentamalla toinen osoite siellä

294
00:13:55,900 --> 00:13:59,060
jos haluamme isompi tai jopa
pienempi kimpale muistia.

295
00:13:59,060 --> 00:14:00,170
Joten tässä on kaupan pois.

296
00:14:00,170 --> 00:14:01,360
Nyt saamme dynaamisuutta.

297
00:14:01,360 --> 00:14:03,350
Meillä on vielä
contiguousness Olen väittäen.

298
00:14:03,350 --> 00:14:05,881
Koska malloc antaa meille
vierekkäisiä kimpale muistia.

299
00:14:05,881 --> 00:14:08,630
Mutta tämä tulee olemaan kipua
kaula meille, ohjelmoija,

300
00:14:08,630 --> 00:14:09,770
todella koodia ylös.

301
00:14:09,770 --> 00:14:10,730
Se on vain enemmän työtä.

302
00:14:10,730 --> 00:14:13,930
Meidän koodi sukua mitä olin
paukutti ulos vain hetki sitten.

303
00:14:13,930 --> 00:14:16,120
Hyvin toteutettavissa, mutta se lisää monimutkaisuutta.

304
00:14:16,120 --> 00:14:19,520
Ja niin kehittäjä aikaa, ohjelmoija
aika on vielä toinen resurssi

305
00:14:19,520 --> 00:14:22,520
että saatamme tarvita viettää
jonkin aikaa saada uusia ominaisuuksia.

306
00:14:22,520 --> 00:14:24,020
Ja sitten tietysti on jono.

307
00:14:24,020 --> 00:14:26,227
Emme aio mennä tätä
yksi yksityiskohtaisesti.

308
00:14:26,227 --> 00:14:27,560
Mutta se on hyvin samanlainen hengessä.

309
00:14:27,560 --> 00:14:31,220
Voisin toteuttaa jono, ja
sen vastaava toiminta,

310
00:14:31,220 --> 00:14:35,660
enqueue tai dequeue, kuten lisätä tai poistaa,
se on vain harrastaja tapa sanoa se,

311
00:14:35,660 --> 00:14:38,100
enqueue tai dequeue, seuraavasti.

312
00:14:38,100 --> 00:14:41,170
Voin vain antaa itselleni struct
että jälleen on useita: n array,

313
00:14:41,170 --> 00:14:44,000
että jälleen on kooltaan,
mutta miksi minun täytyy nyt

314
00:14:44,000 --> 00:14:46,940
seurata edessä jonossa?

315
00:14:46,940 --> 00:14:50,630
En tarvitse tietää
edessä minun pinon.

316
00:14:50,630 --> 00:14:53,570
No, jos minä vielä kerran
queue-- Haluan vain kovaa

317
00:14:53,570 --> 00:14:57,870
koodi sen olevan kuin viisi
kokonaislukuja täällä mahdollisesti.

318
00:14:57,870 --> 00:15:00,940
Joten tämä on nolla, yksi, kaksi, kolme, neljä.

319
00:15:00,940 --> 00:15:03,430
Tämä tulee olemaan
valitut numerot uudelleen.

320
00:15:03,430 --> 00:15:06,940
Ja tämä kutsutaan koko.

321
00:15:06,940 --> 00:15:10,056
>> Miksi se ei riitä
on vain koko?

322
00:15:10,056 --> 00:15:11,680
No, työnnä nuo samat numerot.

323
00:15:11,680 --> 00:15:14,220
Joten en pushed-- I enqueued, tai työntää.

324
00:15:14,220 --> 00:15:20,150
Nyt olen laittaa jonoon 50, ja sitten
51, ja sitten 61, ja piste piste piste.

325
00:15:20,150 --> 00:15:21,070
Niin, että enqueue.

326
00:15:21,070 --> 00:15:23,176
I enqueued 50, sitten 51, sitten 61.

327
00:15:23,176 --> 00:15:25,050
Ja joka näyttää identtinen
pinoon toistaiseksi

328
00:15:25,050 --> 00:15:27,190
paitsi en täytyy tehdä yksi muutos.

329
00:15:27,190 --> 00:15:33,680
Minun täytyy päivittää tämän koon, joten menen
nollasta yhteen kolmelle nyt.

330
00:15:33,680 --> 00:15:35,760
Miten dequeue?

331
00:15:35,760 --> 00:15:36,890
Mitä tapahtuu dequeue?

332
00:15:36,890 --> 00:15:41,950
Kenen pitäisi tulla pois tästä luettelosta
jos se linja Apple Storessa?

333
00:15:41,950 --> 00:15:42,780
Niin 50.

334
00:15:42,780 --> 00:15:44,700
Joten se on eräänlainen hankalampi tällä kertaa.

335
00:15:44,700 --> 00:15:47,880
Ottaa huomioon, että viime kerralla se oli super
helppoa vain tehdä koko miinus yksi,

336
00:15:47,880 --> 00:15:51,440
Saan loppuun minun array tehokkaasti
jos numerot ovat, se poistaa 61.

337
00:15:51,440 --> 00:15:52,920
Mutta en halua poistaa 61.

338
00:15:52,920 --> 00:15:55,030
Haluan ottaa 50, joka
oli siellä 05:00

339
00:15:55,030 --> 00:15:56,790
riviin
uusi iPhone tai vaikka mitä.

340
00:15:56,790 --> 00:16:01,200
Ja niin päästä eroon 50, I
voi vain tehdä tämän, eikö?

341
00:16:01,200 --> 00:16:02,547
Voin yliviivata 50.

342
00:16:02,547 --> 00:16:04,380
Mutta me vain sanoimme
ei tarvitse olla niin anaali

343
00:16:04,380 --> 00:16:06,330
kuten raapia pois tai piilottaa tiedot.

344
00:16:06,330 --> 00:16:08,090
Voimme vain unohtaa missä se on.

345
00:16:08,090 --> 00:16:12,330
>> Mutta jos muutan kokoa nyt
kaksi, on tämä riittävät tiedot

346
00:16:12,330 --> 00:16:15,711
tietää mitä minun jonossa?

347
00:16:15,711 --> 00:16:16,680
Ei oikeastaan.

348
00:16:16,680 --> 00:16:19,830
Mun koko on kaksi, mutta
mistä jono alkaa,

349
00:16:19,830 --> 00:16:22,980
varsinkin jos minulla on vielä
nämä samat numerot muistiin.

350
00:16:22,980 --> 00:16:24,260
50, 51, 61.

351
00:16:24,260 --> 00:16:27,090
Joten minun täytyy muistaa
nyt kun edessä on.

352
00:16:27,090 --> 00:16:29,630
Ja niin kuin ehdotin ylös
siellä, me juuri nimeltään

353
00:16:29,630 --> 00:16:33,729
Nnen edessä, jonka ensimmäinen
arvo olisi pitänyt mitä?

354
00:16:33,729 --> 00:16:35,270
Nolla, vain listan alkuun.

355
00:16:35,270 --> 00:16:40,876
Mutta nyt lisäksi decrementing
koko, me vain increment edessä.

356
00:16:40,876 --> 00:16:42,000
Nyt täällä on toinen ongelma.

357
00:16:42,000 --> 00:16:43,030
Joten kun olen pitää käynnissä.

358
00:16:43,030 --> 00:16:47,520
Oletetaan tämä on määrä
kuten 121, 124, ja sitten, perkele,

359
00:16:47,520 --> 00:16:48,610
Olen pois tilaa.

360
00:16:48,610 --> 00:16:50,390
Mutta hetkinen, en ole.

361
00:16:50,390 --> 00:16:55,630
Joten tässä vaiheessa tarinan,
Oletetaan, että koko on yksi, kaksi,

362
00:16:55,630 --> 00:17:00,370
kolme, neljä, joten oletetaan, että
koko on neljä, edessä on yksi,

363
00:17:00,370 --> 00:17:01,621
joten 51 on edessä.

364
00:17:01,621 --> 00:17:04,329
Haluan esittää toisen numeron täällä,
mutta, Hemmetti, olen pois tilaa.

365
00:17:04,329 --> 00:17:06,710
Mutta en ole oikeastaan, eikö?

366
00:17:06,710 --> 00:17:11,192
Missä voisin laittaa
lisäarvoa, kuten 171?

367
00:17:11,192 --> 00:17:13,400
Joo, voisin vain sellainen
palata tuonne, eikö?

368
00:17:13,400 --> 00:17:18,161
Ja sitten yliviivaa 50, tai
vain korvata se 171.

369
00:17:18,161 --> 00:17:20,410
Ja jos mietit miksi
meidän numerot sai niin satunnainen,

370
00:17:20,410 --> 00:17:24,150
nämä ovat yleisesti otettu tietokone
opiskelemaan Harvardin jälkeen CS50.

371
00:17:24,150 --> 00:17:27,510
Mutta se oli hyvä optimointi,
koska nyt en tuhlaa tilaa.

372
00:17:27,510 --> 00:17:30,750
Minulla on vielä muistaa
kuinka suuri tämä asia on yhteensä.

373
00:17:30,750 --> 00:17:31,500
Se on viisi yhteensä.

374
00:17:31,500 --> 00:17:33,375
Koska en halua
Aloita korvaa 51.

375
00:17:33,375 --> 00:17:36,260
Joten nyt olen edelleen loppui,
joten sama ongelma kuin ennen.

376
00:17:36,260 --> 00:17:39,140
Mutta voit nähdä, kuinka nyt
koodissa, luultavasti

377
00:17:39,140 --> 00:17:41,910
täytyy kirjoittaa hieman
monimutkaisuus tehdä tämän tapahtua.

378
00:17:41,910 --> 00:17:44,510
Ja itse asiassa, mitä operaattori
C luultavasti avulla

379
00:17:44,510 --> 00:17:48,110
te maagisesti tehdä tämän kierron?

380
00:17:48,110 --> 00:17:50,160
Joo modulo operaattori,
prosenttimerkki.

381
00:17:50,160 --> 00:17:53,160
Niin mitä eräänlainen jäähtyä noin jono,
vaikka pidämme piirustus taulukot

382
00:17:53,160 --> 00:17:56,520
koska nämä kuten suoria viivoja, jos
sellaista ajattele tätä kaartuvat

383
00:17:56,520 --> 00:18:00,341
ympärillä kuin ympyrän, sitten vain
intuitiivisesti se tavallaan toimii henkisesti

384
00:18:00,341 --> 00:18:01,590
Mielestäni hieman siististi.

385
00:18:01,590 --> 00:18:05,190
Sinun olisi vielä toteuttaa
että henkinen malli koodi.

386
00:18:05,190 --> 00:18:07,550
Joten ei ole niin kova,
lopulta, toteuttaa,

387
00:18:07,550 --> 00:18:12,430
mutta me silti menettää size-- pikemminkin,
kyky muuttaa, ellemme tee tätä.

388
00:18:12,430 --> 00:18:15,310
>> Meidän täytyy päästä eroon array, me
korvata sen yhdellä osoitin,

389
00:18:15,310 --> 00:18:20,010
ja sitten jossain minun koodi Minulla
soittaa mitä toimia itse luoda

390
00:18:20,010 --> 00:18:23,720
array soittanut?

391
00:18:23,720 --> 00:18:26,190
Malloc, tai vastaavalla
toiminto, tarkalleen.

392
00:18:26,190 --> 00:18:30,481
Kysyttävää pinot tai jonoja.

393
00:18:30,481 --> 00:18:30,980
Joo?

394
00:18:30,980 --> 00:18:33,657

395
00:18:33,657 --> 00:18:34,240
Hyvä kysymys.

396
00:18:34,240 --> 00:18:35,830
Mitä modulo käyttäisit täällä.

397
00:18:35,830 --> 00:18:38,520
Joten yleensä, kun käytät
mod, voisitte tehdä sen

398
00:18:38,520 --> 00:18:40,620
koon
koko tietorakenne.

399
00:18:40,620 --> 00:18:44,120
Joten jotain viisi tai kapasiteettia, jos
se on vakio, on todennäköisesti mukana.

400
00:18:44,120 --> 00:18:47,100
Mutta juuri tekemässä modulo viisi
luultavasti ei ole riittävä,

401
00:18:47,100 --> 00:18:51,380
koska meidän on tiedettävä me
kääri täällä tai täällä tai täällä.

402
00:18:51,380 --> 00:18:54,160
Joten olet luultavasti myös
menossa haluavat ottaa

403
00:18:54,160 --> 00:18:57,220
koko juttu, tai
edessä muuttujaan.

404
00:18:57,220 --> 00:19:00,140
Joten se on vain tämän suhteellisen
yksinkertainen aritmeettinen lauseke,

405
00:19:00,140 --> 00:19:02,000
mutta modulo on olennainen ainesosa.

406
00:19:02,000 --> 00:19:03,330
>> Joten lyhytelokuva jos tahtoa.

407
00:19:03,330 --> 00:19:05,780
Animaatio, että jotkut
ihmiset muussa yliopistossa

408
00:19:05,780 --> 00:19:08,060
koota että olemme
sovitettu tähän keskusteluun.

409
00:19:08,060 --> 00:19:12,630
Siihen liittyy Jack oppiminen
faktoja jonoja ja tilastot.

410
00:19:12,630 --> 00:19:19,010

411
00:19:19,010 --> 00:19:21,890
>> FILM: Olipa kerran,
siellä oli mies nimeltä Jack.

412
00:19:21,890 --> 00:19:25,330
Kun se tuli ystävien,
Jack ei ollut taito.

413
00:19:25,330 --> 00:19:28,220
Joten Jack meni puhumaan
suosituin kaveri hän tiesi.

414
00:19:28,220 --> 00:19:30,920
Hän meni Lou ja kysyi, mitä teen?

415
00:19:30,920 --> 00:19:33,400
Lou näki, että hänen ystävänsä
oli todella ahdistunut.

416
00:19:33,400 --> 00:19:36,050
No, hän alkoi, vain
katso miten olet pukeutunut.

417
00:19:36,050 --> 00:19:38,680
Eikö sinulla ole mitään vaatteita
jossa eri ulkoasua?

418
00:19:38,680 --> 00:19:39,660
Kyllä, sanoi Jack.

419
00:19:39,660 --> 00:19:40,840
Olen varma tehdä.

420
00:19:40,840 --> 00:19:43,320
Tulla kotiini ja
Näytän ne teille.

421
00:19:43,320 --> 00:19:44,550
Niin he menivät pois Jackin.

422
00:19:44,550 --> 00:19:47,520
Ja Jack osoitti Lou laatikko
jossa hän piti kaikki hänen paitoja,

423
00:19:47,520 --> 00:19:49,260
ja hänen housut, ja hänen sukat.

424
00:19:49,260 --> 00:19:52,290
Lou sanoi, Näen sinut on
kaikki vaatteet kasaan.

425
00:19:52,290 --> 00:19:54,870
Miksi et käyttää joitakin
toiset silloin tällöin?

426
00:19:54,870 --> 00:19:58,020
>> Jack sanoi, hyvin, kun
riisu vaatteita ja sukat,

427
00:19:58,020 --> 00:20:00,780
Pesen ne ja laittaa
ne pois ruutuun.

428
00:20:00,780 --> 00:20:03,210
Sitten tulee seuraava
aamulla, ja jopa minä hop.

429
00:20:03,210 --> 00:20:06,380
Menen ruutuun ja saada
vaatteeni päältä.

430
00:20:06,380 --> 00:20:09,070
Lou nopeasti tajusi
ongelma Jack.

431
00:20:09,070 --> 00:20:12,080
Hän piti vaatteita, CD,
ja kirjoja pino.

432
00:20:12,080 --> 00:20:14,420
Kun hän pääsi varten
jotain lukea tai käyttää,

433
00:20:14,420 --> 00:20:17,100
hän oli valita alkuun kirjan tai alusvaatteet.

434
00:20:17,100 --> 00:20:19,500
Sitten kun hän oli tehnyt, hän
olisi laittaa se takaisin.

435
00:20:19,500 --> 00:20:21,970
Takaisin se menisi päälle pinon.

436
00:20:21,970 --> 00:20:24,460
Tiedän ratkaisu,
sanoi voittoisa Loud.

437
00:20:24,460 --> 00:20:27,090
Sinun täytyy oppia
alkaa käyttää jono.

438
00:20:27,090 --> 00:20:29,870
Lou otti Jackin vaatteita ja
ripustaa ne kaappiin.

439
00:20:29,870 --> 00:20:32,710
Ja kun hän oli tyhjentänyt
laatikko, hän vain heitti sen.

440
00:20:32,710 --> 00:20:36,500
>> Sitten hän sanoi, nyt Jack, lopussa
päivä, laittaa vaatteet vasemmalla

441
00:20:36,500 --> 00:20:37,990
kun laitat ne pois.

442
00:20:37,990 --> 00:20:41,300
Sitten huomisaamuna, kun
katso auringonpaiste, saat vaatteet

443
00:20:41,300 --> 00:20:43,440
oikealla, lopusta linjan.

444
00:20:43,440 --> 00:20:44,880
Etkö näe? sanoi Lou.

445
00:20:44,880 --> 00:20:46,370
Se on niin mukavaa.

446
00:20:46,370 --> 00:20:49,770
Sinun käyttää kaiken kerran
ennen käytät jotain kahdesti.

447
00:20:49,770 --> 00:20:52,670
Ja kaiken jonoissa
hänen vaatekaappi ja hylly,

448
00:20:52,670 --> 00:20:55,160
Jack alkoi tuntua
melko varma itsestään.

449
00:20:55,160 --> 00:20:59,720
Kaikki kiitos Lou ja
hänen ihana jono.

450
00:20:59,720 --> 00:21:01,220
SPEAKER 1: Okei, se on ihana.

451
00:21:01,220 --> 00:21:05,920

452
00:21:05,920 --> 00:21:10,080
Joten mitä on todella tapahtuu
on alla huppu nyt?

453
00:21:10,080 --> 00:21:12,370
Että meillä on osoittimet,
että meillä on malloc,

454
00:21:12,370 --> 00:21:15,680
että meillä on kyky luoda
paloina muisti itsellemme

455
00:21:15,680 --> 00:21:16,344
dynaamisesti.

456
00:21:16,344 --> 00:21:18,510
Joten tämä on kuva me
vilaukselta juuri muutama päivä.

457
00:21:18,510 --> 00:21:21,180
Emme todellakaan asu
sitä, mutta tämä kuva

458
00:21:21,180 --> 00:21:24,180
on jatkunut alla
huppu viikkoja nyt.

459
00:21:24,180 --> 00:21:27,050
Ja niin tämä merkitsee, vain
suorakulmio että olemme laadittu,

460
00:21:27,050 --> 00:21:28,180
tietokoneen muistiin.

461
00:21:28,180 --> 00:21:31,850
Ja ehkä tietokone, tai CS50
ID, on gigatavu muistia tai RAM

462
00:21:31,850 --> 00:21:33,050
tai kaksi gigatavua tai neljä.

463
00:21:33,050 --> 00:21:34,450
Se ei ole oikeastaan ​​väliä.

464
00:21:34,450 --> 00:21:37,240
Käyttöjärjestelmä
Windows tai Mac OS tai Linux,

465
00:21:37,240 --> 00:21:41,120
olennaisesti mahdollistaa ohjelman
ajatella, että sillä on mahdollisuus

466
00:21:41,120 --> 00:21:42,982
sitten kaikkiin
tietokoneen muistiin,

467
00:21:42,982 --> 00:21:45,440
vaikka saatat olla käynnissä
useita ohjelmia kerralla.

468
00:21:45,440 --> 00:21:46,990
Joten todellisuudessa, että ei oikein toimi.

469
00:21:46,990 --> 00:21:49,448
Mutta se on eräänlainen illuusio
annetaan kaikki ohjelmat.

470
00:21:49,448 --> 00:21:53,110
Joten jos sinulla on ollut kaksi keikkaa muistia, tämä
on miten tietokone voisi ajatella sitä.

471
00:21:53,110 --> 00:21:57,110
>> Nyt sattumalta, yksi näistä
asioita, yksi näistä segmenteistä muistia,

472
00:21:57,110 --> 00:21:58,350
kutsutaan pinon.

473
00:21:58,350 --> 00:22:01,680
Ja todellakin tahansa
toistaiseksi kirjallisesti koodi

474
00:22:01,680 --> 00:22:05,900
että olet soittanut
toiminto, esimerkiksi tärkein.

475
00:22:05,900 --> 00:22:08,410
Muista, että aina olen
drawn tietokoneen muistiin,

476
00:22:08,410 --> 00:22:10,640
Olen aina piirtää tavallaan
puolet suorakulmion täällä

477
00:22:10,640 --> 00:22:12,520
ja älä välitä puhua
siitä, mitä edellä.

478
00:22:12,520 --> 00:22:15,980
Koska kun tärkein on nimeltään, minä väittävät
että saat tämän suikale muistia

479
00:22:15,980 --> 00:22:16,970
että menee alas täällä.

480
00:22:16,970 --> 00:22:20,650
Ja jos tärkein kutsui toiminto
kuten swap, hyvin swap menee täällä.

481
00:22:20,650 --> 00:22:23,720
Ja se kääntyy pois, se on
jos se päätyy.

482
00:22:23,720 --> 00:22:26,277
Jotain kutsutaan pino
sisällä tietokoneen muistiin.

483
00:22:26,277 --> 00:22:28,360
Nyt lopussa päivä,
tämä on vain korjaa.

484
00:22:28,360 --> 00:22:30,680
Se on kuin tavu nolla,
tavu yksi, tavu 2000000000.

485
00:22:30,680 --> 00:22:33,130
Mutta jos ajattelee sitä
koska tämä suorakulmainen esine,

486
00:22:33,130 --> 00:22:35,130
kaikki teemme joka
aika kutsumme toiminto on

487
00:22:35,130 --> 00:22:37,180
kerrospukeutuminen uusi siivu muistia.

488
00:22:37,180 --> 00:22:41,700
Annamme tämän tehtävän viipale
sen omaa muistia työskennellä.

489
00:22:41,700 --> 00:22:44,490
>> Ja muistuttaa nyt, että tämä on tärkeää.

490
00:22:44,490 --> 00:22:46,400
Koska jos meillä on
jotain swap

491
00:22:46,400 --> 00:22:51,610
ja kaksi paikallista muuttujaa kuten A ja B ja
muutamme nuo arvot yhdestä ja kahdesta

492
00:22:51,610 --> 00:22:55,130
kaksi ja yksi, Recall
että kun swap palaa,

493
00:22:55,130 --> 00:22:58,330
se on ikään kuin tämä siivu
muistia on juuri mennyt.

494
00:22:58,330 --> 00:23:00,080
Todellisuudessa se on edelleen
siellä forensically.

495
00:23:00,080 --> 00:23:01,940
Ja jotain on vielä todella siellä.

496
00:23:01,940 --> 00:23:05,410
Mutta käsitteellisesti, se on niin
vaikka se on täysin poissa.

497
00:23:05,410 --> 00:23:10,910
Ja niin tärkein ei tiedä mitään työtä
että tehtiin että swap-toiminto,

498
00:23:10,910 --> 00:23:14,890
ellei se on todella kulunut kyseisissä
perustelut osoitin tai viittaamalla.

499
00:23:14,890 --> 00:23:17,790
Nyt, perusratkaisua
tähän ongelmaan swap

500
00:23:17,790 --> 00:23:19,970
kulkee asiat osoitteen.

501
00:23:19,970 --> 00:23:23,250
Mutta näyttää siltä, ​​liian, mitä
jatkunut edellä, että osa

502
00:23:23,250 --> 00:23:26,330
suorakulmion koko ajan on
mutta siellä on enemmän muistia siellä.

503
00:23:26,330 --> 00:23:28,790
Ja kun dynaamisesti
varata muistia,

504
00:23:28,790 --> 00:23:32,020
onko se sisällä GetString, joka
olemme tehneet sinulle CS50

505
00:23:32,020 --> 00:23:34,710
kirjasto, tai jos te
soittaa malloc ja kysyä

506
00:23:34,710 --> 00:23:37,950
käyttöjärjestelmä kimpale
muistia, se ei tule pinosta.

507
00:23:37,950 --> 00:23:40,960
Se tulee toisesta paikasta
tietokoneen muistiin

508
00:23:40,960 --> 00:23:42,220
että kutsutaan kasaan.

509
00:23:42,220 --> 00:23:43,430
Ja se ei ole mitään erilaista.

510
00:23:43,430 --> 00:23:44,285
Se on sama RAM.

511
00:23:44,285 --> 00:23:45,160
Se on sama muisti.

512
00:23:45,160 --> 00:23:49,080
Se on vain RAM on jopa
siellä sijaan täällä.

513
00:23:49,080 --> 00:23:50,750
>> Ja niin mitä se tarkoittaa?

514
00:23:50,750 --> 00:23:53,650
No, jos tietokoneessa on
rajallinen määrä muistia

515
00:23:53,650 --> 00:23:57,450
ja pino on kasvamassa, joten
puhua, ja kasan mukaan

516
00:23:57,450 --> 00:23:59,349
Tämän nuoli, kasvaa alaspäin.

517
00:23:59,349 --> 00:24:01,140
Toisin sanoen, jokainen
kun soitat malloc,

518
00:24:01,140 --> 00:24:03,430
olet annetaan viipale
muistia ylhäältä,

519
00:24:03,430 --> 00:24:06,630
niin ehkä hieman pienempi, sitten hieman
alempi, aina soittaa malloc,

520
00:24:06,630 --> 00:24:10,100
kasaan, se käyttö,
on eräänlainen kasvaa,

521
00:24:10,100 --> 00:24:11,950
kasvaa lähemmäs mitä?

522
00:24:11,950 --> 00:24:13,382
Pino.

523
00:24:13,382 --> 00:24:14,840
Joten tämä kuulostaa hyvä idea?

524
00:24:14,840 --> 00:24:18,420

525
00:24:18,420 --> 00:24:22,140
Tarkoitan, jos se ei ole kovin selkeä
mitä muuta voit tehdä, jos vain

526
00:24:22,140 --> 00:24:23,910
on rajallinen määrä muistia.

527
00:24:23,910 --> 00:24:25,200
Mutta tämä on varmasti huono.

528
00:24:25,200 --> 00:24:27,920
Nämä kaksi nuolet ovat
tehokurssi toisiaan.

529
00:24:27,920 --> 00:24:31,930
>> Ja käy ilmi, että huono kaveri, ihmiset, jotka
ovat erityisen hyvä ohjelma,

530
00:24:31,930 --> 00:24:36,140
ja yrittää murtautua tietokoneisiin,
voi hyödyntää tätä todellisuutta.

531
00:24:36,140 --> 00:24:38,290
Itse asiassa, nyt harkita
pieni pätkä.

532
00:24:38,290 --> 00:24:41,350
Joten tämä on esimerkki voit lukea
noin tarkemmin Wikipediassa.

533
00:24:41,350 --> 00:24:43,100
Me kohta sinua
artikkeli jos utelias.

534
00:24:43,100 --> 00:24:45,650
Mutta on hyökkäys yleisesti
tunnettu puskurin ylivuoto että

535
00:24:45,650 --> 00:24:49,570
on olemassa niin kauan kuin ihmisillä
on ollut kyky manipuloida

536
00:24:49,570 --> 00:24:53,120
tietokoneen muistiin, erityisesti C.
Joten tämä on hyvin mielivaltainen ohjelma,

537
00:24:53,120 --> 00:24:55,130
mutta katsotaanpa lukea se alhaalta ylöspäin.

538
00:24:55,130 --> 00:24:57,650
Tärkeimmät osaksi argc merkkiä tähden argv.

539
00:24:57,650 --> 00:24:59,830
Joten se on ohjelma, joka ottaa
komentoriviargumentteja.

540
00:24:59,830 --> 00:25:03,620
Ja kaikki tärkeimmät ei ilmeisesti on puhelu
toiminto, kutsuvat sitä F yksinkertaisuuden.

541
00:25:03,620 --> 00:25:04,610
Ja se kulkee mitä?

542
00:25:04,610 --> 00:25:05,490
Argv yhden.

543
00:25:05,490 --> 00:25:09,320
Joten se kulkee F riippumatta
sana on, että käyttäjä kirjoittanut

544
00:25:09,320 --> 00:25:11,500
kehoitteessa jälkeen
Ohjelman nimi ollenkaan.

545
00:25:11,500 --> 00:25:15,730
Niin paljon kuin Caesar tai Vigenere, joka
saatat muistaa teet argv.

546
00:25:15,730 --> 00:25:16,680
>> Joten mikä on F?

547
00:25:16,680 --> 00:25:19,760
F ottaa merkkijono
ainoana väitteen,

548
00:25:19,760 --> 00:25:22,100
AKA char tähti, sama
asia, kuten merkkijono.

549
00:25:22,100 --> 00:25:24,920
Ja sitä kutsutaan mielivaltaisesti
baari tässä esimerkissä.

550
00:25:24,920 --> 00:25:27,710
Ja sitten char C 12,
vain maallikon termein,

551
00:25:27,710 --> 00:25:31,750
mikä on char c kiinnike 12 tekee meille?

552
00:25:31,750 --> 00:25:33,440
Mitä se tekee?

553
00:25:33,440 --> 00:25:36,490
Varaaminen muisti, erityisesti
12 tavua 12 merkkiä.

554
00:25:36,490 --> 00:25:36,990
Aivan.

555
00:25:36,990 --> 00:25:40,000
Ja sitten viimeinen rivi, sekoita ja
kopio, olet todennäköisesti ole nähnyt.

556
00:25:40,000 --> 00:25:43,360
Tämä on merkkijono kopio
jonka tehtävänä elämässä

557
00:25:43,360 --> 00:25:48,160
on kopioida sen toiseen väitteeseen
osaksi sen ensimmäinen väite,

558
00:25:48,160 --> 00:25:51,190
mutta vain
tietty määrä tavua.

559
00:25:51,190 --> 00:25:53,860
Joten kolmas väite sanoo,
kuinka monta tavua pitäisi kuuletko?

560
00:25:53,860 --> 00:25:56,720
Pituus baari,
mitä käyttäjä kirjoitettu.

561
00:25:56,720 --> 00:25:59,320
Ja sisältö
baari, että jono, ovat

562
00:25:59,320 --> 00:26:02,330
kopioitu muistiin osoitti at C

563
00:26:02,330 --> 00:26:04,060
>> Joten tämä näyttää typerää, ja se on.

564
00:26:04,060 --> 00:26:06,300
Se on keinotekoinen esimerkki,
mutta se on edustava

565
00:26:06,300 --> 00:26:10,100
luokan hyökkäys vektoreita,
tapa hyökätä ohjelman.

566
00:26:10,100 --> 00:26:15,050
Kaikki on hieno ja hyvä, jos käyttäjä
nimikkeet sana, joka on 11 merkkiä

567
00:26:15,050 --> 00:26:18,040
tai vähemmän, sekä kenoviiva nolla.

568
00:26:18,040 --> 00:26:22,830
Entä jos käyttäjä on yli
11 tai 12 tai 20 tai 50 merkkiä?

569
00:26:22,830 --> 00:26:25,090
Mikä tämä ohjelma aikoo tehdä?

570
00:26:25,090 --> 00:26:29,360
Mahdollisesti seg vika. Se menee
sokeasti kopioida kaiken bar ylös

571
00:26:29,360 --> 00:26:31,750
sen pituus, joka on
kirjaimellisesti kaiken baari,

572
00:26:31,750 --> 00:26:36,307
osoiteriville osoitti C. Mutta C
on vain ennaltaehkäisevästi annettu 12 tavua.

573
00:26:36,307 --> 00:26:37,640
Mutta ei ole ylimääräistä tarkistaa.

574
00:26:37,640 --> 00:26:38,700
Ei ole, jos olosuhteet.

575
00:26:38,700 --> 00:26:40,580
Ei ole virhe tarkkailun täällä.

576
00:26:40,580 --> 00:26:43,270
>> Ja niin mitä tämä ohjelma on
aikoo tehdä, on vain sokeasti

577
00:26:43,270 --> 00:26:45,750
kopioida yksi asia toiseen.

578
00:26:45,750 --> 00:26:47,880
Joten jos me tehdä tätä
kuten kuva, tässä

579
00:26:47,880 --> 00:26:49,860
vain suikale muistia.

580
00:26:49,860 --> 00:26:53,470
Niin huomaa alareunassa, me
on paikallinen muuttuja baarissa.

581
00:26:53,470 --> 00:26:57,330
Niin että osoitin että menee store--
pikemminkin, että paikalliset väite, jonka on

582
00:26:57,330 --> 00:26:58,672
menossa tallentaa merkkijonon bar.

583
00:26:58,672 --> 00:27:00,380
Ja sitten huomaa vain
sen yläpuolella pino,

584
00:27:00,380 --> 00:27:02,505
koska aina kun kysyä
muisti pinoon,

585
00:27:02,505 --> 00:27:04,310
se menee vähän
yläpuolella kuvallisesti,

586
00:27:04,310 --> 00:27:06,270
ilmoittaa, että meillä 12 tavua siellä.

587
00:27:06,270 --> 00:27:10,690
Ylhäällä vasemmalla yksi on C kiinnike nolla ja
Alhaalla oikealla yksi on C kiinnike 11.

588
00:27:10,690 --> 00:27:12,870
Se on vain miten tietokoneet
menossa antaa se pois.

589
00:27:12,870 --> 00:27:18,300
Joten intuitiivisesti, jos baari on enemmän
kuin 12 merkkiä yhteensä, mukaan lukien

590
00:27:18,300 --> 00:27:25,790
kenoviiva nolla, jossa on
12 tai C kannatin 12 menossa?

591
00:27:25,790 --> 00:27:28,440
Tai pikemminkin jossa on 12
merkin tai 13 merkin,

592
00:27:28,440 --> 00:27:30,900
sadasosa merkki menossa
päätyä kuvan?

593
00:27:30,900 --> 00:27:33,400
Yli tai alle?

594
00:27:33,400 --> 00:27:36,300
>> Oikea, sillä vaikka
pino itse kasvaa ylöspäin,

595
00:27:36,300 --> 00:27:39,590
kun olet laittaa tavaraa
se, se rakennesyistä,

596
00:27:39,590 --> 00:27:41,294
tuo muisti ylhäältä alas.

597
00:27:41,294 --> 00:27:44,460
Joten jos sinulla enemmän kuin 12 tavua,
aiot alkaa korvata bar.

598
00:27:44,460 --> 00:27:47,280
Nyt se on vika, mutta se on
ei oikeastaan ​​iso juttu.

599
00:27:47,280 --> 00:27:51,130
Mutta se on iso juttu, koska siellä
lisää juttuja muistissa.

600
00:27:51,130 --> 00:27:53,074
Joten tässä miten voisimme
laittaa Hei, olla selvillä.

601
00:27:53,074 --> 00:27:54,490
Jos olen kirjoittanut Hei kehoitteeseen.

602
00:27:54,490 --> 00:27:59,330
H-E-L-L-O kenoviiva nolla, päätyy sisällä
ne 12 tavua, ja olemme erittäin turvallinen.

603
00:27:59,330 --> 00:28:00,330
Kaikki on hyvin.

604
00:28:00,330 --> 00:28:03,020
Mutta jos kirjoitan jotain
pidempään, mahdollisesti se on

605
00:28:03,020 --> 00:28:05,860
menossa hiipiä bar avaruuteen.

606
00:28:05,860 --> 00:28:08,405
Mutta vielä pahempaa, se kääntyy
kaikki tällä kertaa,

607
00:28:08,405 --> 00:28:11,530
vaikka emme ole koskaan puhuneet
se, pino käytetään muita juttuja.

608
00:28:11,530 --> 00:28:13,560
Se ei ole vain paikallisia muuttujia.

609
00:28:13,560 --> 00:28:15,100
>> C on hyvin alhainen kieli.

610
00:28:15,100 --> 00:28:17,810
Ja se tavallaan salaa
käyttää pinon myös

611
00:28:17,810 --> 00:28:21,260
muistaa
toimintoa kutsutaan, mitä

612
00:28:21,260 --> 00:28:26,040
osoite on edellisen toiminnon,
joten se voi hypätä takaisin tuon toiminnan.

613
00:28:26,040 --> 00:28:29,980
Joten kun tärkeimmät puhelut vaihtaa, joukossa
asiat työnnetään pinoon

614
00:28:29,980 --> 00:28:34,380
eivät ole vain swapit paikallisia muuttujia,
tai sen perusteluja, myös salaa työnsi

615
00:28:34,380 --> 00:28:37,510
pinoon edustamana
jonka punainen siivu täällä,

616
00:28:37,510 --> 00:28:40,520
on osoite tärkein fyysisesti
tietokoneen muistiin,

617
00:28:40,520 --> 00:28:44,180
niin, että kun vaihto on tehty, tietokone
tietää minun täytyy mennä takaisin päävalikkoon

618
00:28:44,180 --> 00:28:46,760
ja lopuksi täytäntöönpanosta päätehtävä.

619
00:28:46,760 --> 00:28:51,960
Joten tämä on vaarallista nyt, koska jos
käyttäjä on hyvin enemmän kuin hei,

620
00:28:51,960 --> 00:28:57,030
siten, että käyttäjä tulo clobbers
tai korvaa että punainen osa,

621
00:28:57,030 --> 00:28:59,820
loogisesti jos tietokoneen
juuri menossa sokeasti olettaa

622
00:28:59,820 --> 00:29:03,830
että tavua että punainen siivu ovat
osoite, johon se pitäisi palauttaa,

623
00:29:03,830 --> 00:29:09,020
mitä jos vastustaja on fiksu tai
onni laittaa järjestyksessä tavuja

624
00:29:09,020 --> 00:29:13,450
siellä joka näyttää osoitteen,
mutta se on osoite koodia

625
00:29:13,450 --> 00:29:18,730
että hän haluaa tietokone
suorittaa sijasta tärkein?

626
00:29:18,730 --> 00:29:21,670
>> Toisin sanoen, jos se, mitä
käyttäjä on kirjoittaa kehoitteessa,

627
00:29:21,670 --> 00:29:23,850
ei ole vain jotain
harmittomia kuten Hei,

628
00:29:23,850 --> 00:29:28,210
mutta se on itse asiassa koodi, joka on vastaava
poistaa kaikki tämän käyttäjän tiedostot?

629
00:29:28,210 --> 00:29:30,060
Tai sähköpostitse salasanansa minulle?

630
00:29:30,060 --> 00:29:31,940
Tai aloita kirjautumalla niiden
näppäimistön, oikea?

631
00:29:31,940 --> 00:29:34,920
Meillä on yksi keino, nyt säätää tänään,
että he voivat kirjoittaa ei just hello

632
00:29:34,920 --> 00:29:36,711
maailma tai heidän nimensä,
he voisivat olennaisesti

633
00:29:36,711 --> 00:29:39,570
pass koodin, nollat ​​ja
ne, että tietokone

634
00:29:39,570 --> 00:29:43,450
virheitä sekä koodin ja osoite.

635
00:29:43,450 --> 00:29:48,950
Joten vaikkakin abstraktisti, jos
käyttäjä on tarpeeksi kontradiktorisessa koodi

636
00:29:48,950 --> 00:29:52,330
että me yleistää täällä
A. on hyökkäys tai vastustajia.

637
00:29:52,330 --> 00:29:53,140
Joten vain huonoja juttuja.

638
00:29:53,140 --> 00:29:55,306
Emme välitä
numeroita tai nollia tai niistä

639
00:29:55,306 --> 00:29:59,470
tänään, niin että voit päätyä
korvaamasta että punainen osa,

640
00:29:59,470 --> 00:30:01,580
huomata, että sekvenssi tavuja.

641
00:30:01,580 --> 00:30:05,020
O 835 C nolla kahdeksan nolla.

642
00:30:05,020 --> 00:30:08,960
Ja nyt Wikipedian artikkeli tästä
on ehdottanut, jos nyt todella alkaa

643
00:30:08,960 --> 00:30:12,460
merkinnät tavua tietokoneesi
muisti, mitä Wikipedia artikkeli on

644
00:30:12,460 --> 00:30:19,060
Ehdotuksen on, että mitä jos osoite
Kyseisen vasemmassa yläkulmassa tavu on 80 C 0 3508.

645
00:30:19,060 --> 00:30:22,200
>> Toisin sanoen, jos pahis on
fiksu kanssa hänen koodi

646
00:30:22,200 --> 00:30:26,650
todella laittaa numero täällä, että
vastaa osoitteen koodin

647
00:30:26,650 --> 00:30:29,180
hän ruiskutetaan
tietokoneeseen, voit

648
00:30:29,180 --> 00:30:31,050
voi huijata tietokoneen
osaksi tee mitään.

649
00:30:31,050 --> 00:30:34,140
Tiedostojen poistaminen, sähköpostitse
asioita, haistaa liikennettä,

650
00:30:34,140 --> 00:30:36,710
kirjaimellisesti mitään voisi olla
ruiskutetaan tietokoneeseen.

651
00:30:36,710 --> 00:30:39,220
Ja niin puskurin ylivuoto
hyökkäys sen ytimessä

652
00:30:39,220 --> 00:30:43,530
on vain tyhmä, tyhmä
ohittaminen array, joka

653
00:30:43,530 --> 00:30:45,840
ei ollut sen rajoja tarkistetaan.

654
00:30:45,840 --> 00:30:48,850
Ja tämä on mitä on erittäin vaarallinen
ja samanaikaisesti super tehokas

655
00:30:48,850 --> 00:30:52,560
C on se, että meillä todellakin on
pääsy kaikkialle muistiin.

656
00:30:52,560 --> 00:30:55,320
Se on jopa meille, ohjelmoijat,
joka kirjoittaa alkuperäisen koodin

657
00:30:55,320 --> 00:30:59,330
tarkistaa hiton pituus tahansa
paneelit että olemme manipuloimalla.

658
00:30:59,330 --> 00:31:00,750
Joten tehdä selväksi, mikä on korjata?

659
00:31:00,750 --> 00:31:03,190
Jos me palauta tämä
koodi, minun ei pitäisi vain

660
00:31:03,190 --> 00:31:08,000
muuttaa pituutta baari, mitä
muuten minun pitäisi tarkistaa?

661
00:31:08,000 --> 00:31:10,620
Mitä muuta minun pitäisi tehdä jotta
estää tämän hyökkäyksen täysin?

662
00:31:10,620 --> 00:31:14,110
En halua vain sokeasti sanoa
että sinun pitäisi kopioida niin monta tavua

663
00:31:14,110 --> 00:31:16,140
kuten pituus bar.

664
00:31:16,140 --> 00:31:18,910
Haluan sanoa, kopioida kuin
monet tavua ovat baarissa

665
00:31:18,910 --> 00:31:24,090
asti myönnetyn
muisti, tai 12 maksimaalisesti.

666
00:31:24,090 --> 00:31:27,450
Joten minun on jonkinlainen jos ehto
että ei tarkista pituus baari,

667
00:31:27,450 --> 00:31:32,800
mutta jos se ylittää 12, me vain kova koodi
12 koska suurin mahdollinen etäisyys.

668
00:31:32,800 --> 00:31:35,910
Muuten ns puskuriin
ylivuoto hyökkäys voi tapahtua.

669
00:31:35,910 --> 00:31:38,451
Alareunassa näiden dioja,
jos olet kiinnostunut lukea lisää

670
00:31:38,451 --> 00:31:41,200
on todellinen alkuperäinen artikkeli
jos haluat katsoa.

671
00:31:41,200 --> 00:31:44,550
>> Mutta nyt, joukossa hinnat
maksettu täällä oli tehottomuutta.

672
00:31:44,550 --> 00:31:46,680
Joten se oli nopea
alhainen katsomaan mitä

673
00:31:46,680 --> 00:31:49,709
ongelmia voi syntyä nyt että me
on pääsy tietokoneen muistiin.

674
00:31:49,709 --> 00:31:51,750
Mutta toinen ongelma meillä
jo kompastellut maanantaina

675
00:31:51,750 --> 00:31:53,800
oli juuri tehottomuus
linkitetyn listan.

676
00:31:53,800 --> 00:31:56,019
Olemme takaisin lineaarisen ajan.

677
00:31:56,019 --> 00:31:57,560
Meillä ei ole enää yhtenäinen joukko.

678
00:31:57,560 --> 00:31:58,980
Meillä ei ole random access.

679
00:31:58,980 --> 00:32:00,710
Emme voi käyttää hakasulku merkintätapa.

680
00:32:00,710 --> 00:32:04,590
Me kirjaimellisesti täytyy käyttää while-silmukka
jollainen Kirjoitin hetki sitten.

681
00:32:04,590 --> 00:32:09,740
Mutta maanantaina, me väitti, että voimme
hiipiä takaisin osaksi keskustelussa tehokkuus

682
00:32:09,740 --> 00:32:13,040
saavuttamiseksi jotain, joka on
logaritminen ehkä, tai paras vielä,

683
00:32:13,040 --> 00:32:16,120
ehkä jopa jotain, joka on
niin kutsuttu vakio ajan.

684
00:32:16,120 --> 00:32:19,840
Miten siis voimme tehdä, että käyttämällä näitä uusia
työkalut, nämä osoitteet, nämä osoittimia,

685
00:32:19,840 --> 00:32:22,210
ja ketjuttaminen asioita oman?

686
00:32:22,210 --> 00:32:23,960
No, oletetaan, että
täällä, nämä ovat joukko

687
00:32:23,960 --> 00:32:27,170
numeroita että haluamme tallentaa
tietorakenne ja haku tehokkaasti.

688
00:32:27,170 --> 00:32:30,960
Voimme ehdottomasti kelata viikko
kaksi, heittää nämä taulukkoon,

689
00:32:30,960 --> 00:32:33,150
ja etsiä niitä käyttämällä binäärihakupuu.

690
00:32:33,150 --> 00:32:34,040
Hajota ja hallitse.

691
00:32:34,040 --> 00:32:37,720
Ja itse asiassa kirjoitit
binary toimialalla PSET3,

692
00:32:37,720 --> 00:32:40,100
jossa toteutetaan Etsi ohjelma.

693
00:32:40,100 --> 00:32:40,890
Mutta tiedätkö mitä.

694
00:32:40,890 --> 00:32:45,060
Siellä on tavallaan enemmän
fiksu tapa tehdä tämä.

695
00:32:45,060 --> 00:32:47,390
Se on vähän enemmän
hienostunut ja se ehkä

696
00:32:47,390 --> 00:32:50,830
antaa meille mahdollisuuden nähdä, miksi binary
haku on niin paljon nopeammin.

697
00:32:50,830 --> 00:32:52,980
Ensimmäinen, nyt käyttöön
käsite puu.

698
00:32:52,980 --> 00:32:54,730
Joka vaikka
todellisuus puut eräänlainen

699
00:32:54,730 --> 00:32:57,730
kasvaa näin, maailman tietokoneen
tiede he eräänlainen kasvaa alaspäin

700
00:32:57,730 --> 00:33:00,830
kuten sukupuu, jossa on
isovanhemmat tai suurta isovanhemmat

701
00:33:00,830 --> 00:33:04,580
tai vaikka mitä huipulla, patriarkka ja
matriarkka perheen, vain yksi

702
00:33:04,580 --> 00:33:07,930
ns root, solmu, alle
jotka ovat sen lapsia,

703
00:33:07,930 --> 00:33:11,442
jonka alapuolella ovat sen lapsia, tai
sen jälkeläiset yleisemmin.

704
00:33:11,442 --> 00:33:13,400
Ja kukaan roikkui
pohja perheen

705
00:33:13,400 --> 00:33:16,070
puu on paitsi
perheen pienimmille,

706
00:33:16,070 --> 00:33:19,520
voi myös vain olla yleisesti
kutsutaan puun lehdet.

707
00:33:19,520 --> 00:33:21,800
>> Joten tämä on vain nippu
sanoja ja määritelmiä

708
00:33:21,800 --> 00:33:25,790
jotain kutsutaan puu tietokone
tiede, aivan kuten sukupuu.

709
00:33:25,790 --> 00:33:28,770
Mutta on harrastaja inkarnaatioita
puita, joista yksi

710
00:33:28,770 --> 00:33:30,780
kutsutaan binäärihakupuu.

711
00:33:30,780 --> 00:33:34,380
Ja voit eräänlainen härnätä
lisäksi mitä tämä asia ei.

712
00:33:34,380 --> 00:33:37,180
No, se on binary missä mielessä?

713
00:33:37,180 --> 00:33:41,455
Mistä binary tulevat tänne?

714
00:33:41,455 --> 00:33:41,955
Anteeksi?

715
00:33:41,955 --> 00:33:45,961

716
00:33:45,961 --> 00:33:47,210
Se ei ole niin paljon joko tai.

717
00:33:47,210 --> 00:33:52,000
Se on enemmän, että kussakin solmussa ei ole
enemmän kuin kaksi lasta, kuten näemme täällä.

718
00:33:52,000 --> 00:33:54,990
Yleensä, tree-- ja
teidän vanhemmat ja isovanhemmat

719
00:33:54,990 --> 00:33:57,640
voi olla niin monta lasta tai
grandkids koska he todella haluavat,

720
00:33:57,640 --> 00:34:00,820
ja niin esimerkiksi siellä meillä on kolme
lapset pois, että oikea käsi solmu,

721
00:34:00,820 --> 00:34:05,480
mutta binääripuun, solmulla on
nolla, yksi tai kaksi lasta maksimaalisesti.

722
00:34:05,480 --> 00:34:08,496
Ja se on mukava ominaisuus,
koska jos se on rajattu kahdella,

723
00:34:08,496 --> 00:34:10,620
aiomme pystyä
saada hieman log pohja kaksi

724
00:34:10,620 --> 00:34:11,975
toiminta täällä lopulta.

725
00:34:11,975 --> 00:34:13,350
Joten meillä on jotain logaritminen.

726
00:34:13,350 --> 00:34:14,558
Mutta siitä lisää hetken kuluttua.

727
00:34:14,558 --> 00:34:19,810
Hae puu tarkoittaa, että numerot ovat
järjestetty siten, että vasen lapsen

728
00:34:19,810 --> 00:34:22,429
arvo on suurempi kuin juuri.

729
00:34:22,429 --> 00:34:26,010
Ja sen oikea lapsi on
suurempi kuin juuri.

730
00:34:26,010 --> 00:34:29,290
Toisin sanoen, jos käytät jotakin
solmut, piireissä tätä kuvaa,

731
00:34:29,290 --> 00:34:31,840
ja katsoo sen vasen
lapsi ja sen oikea lapsi,

732
00:34:31,840 --> 00:34:34,739
ensimmäinen tulisi olla alle,
Toinen tulisi olla suurempi kuin.

733
00:34:34,739 --> 00:34:36,159
Joten järki tarkistaa 55.

734
00:34:36,159 --> 00:34:37,780
Se on jäljellä lapsi on 33.

735
00:34:37,780 --> 00:34:38,620
Se on vähemmän kuin.

736
00:34:38,620 --> 00:34:40,929
55, sen oikea lapsi on 77.

737
00:34:40,929 --> 00:34:41,783
Se on suurempi kuin.

738
00:34:41,783 --> 00:34:43,199
Ja se on rekursiivinen määritelmä.

739
00:34:43,199 --> 00:34:46,480
Voisimme tarkistaa jokainen näistä
solmut ja sama kuvio vaikeuttaisivat.

740
00:34:46,480 --> 00:34:49,389
>> Niin mitä mukavaa
binäärihakupuu, on

741
00:34:49,389 --> 00:34:52,204
että yksi, voimme toteuttaa sen
kanssa struct, aivan kuten tämä.

742
00:34:52,204 --> 00:34:54,620
Ja vaikka olemme heitto
paljon rakenteiden teidän,

743
00:34:54,620 --> 00:34:56,560
he hieman
intuitiivinen nyt toivottavasti.

744
00:34:56,560 --> 00:35:00,570
Syntaksi on edelleen vaikeaselkoisten varma,
mutta sisällön solmun tässä

745
00:35:00,570 --> 00:35:02,786
context-- ja pidämme
käyttää sanaa solmu,

746
00:35:02,786 --> 00:35:04,910
onko se suorakulmio
näytöllä tai ympyrä,

747
00:35:04,910 --> 00:35:08,970
se on vain joitakin yleisiä kontti,
tässä tapauksessa puu, jollainen

748
00:35:08,970 --> 00:35:11,780
näimme, tarvitsemme kokonaisluku
kussakin solmujen

749
00:35:11,780 --> 00:35:15,460
ja sitten minun täytyy kaksi osoitinta osoittelee
vasemmalle lapsi ja oikea lapsi,

750
00:35:15,460 --> 00:35:16,590
vastaavasti.

751
00:35:16,590 --> 00:35:20,730
Niin, että miten voisimme
toteuttaa että struct.

752
00:35:20,730 --> 00:35:22,315
Ja miten voisin toteuttaa se koodi?

753
00:35:22,315 --> 00:35:26,730
No, katsotaanpa ottaa nopeasti
katsokaa tämä pieni esimerkki.

754
00:35:26,730 --> 00:35:29,820
Se ei ole toimiva, mutta olen
kopioida ja liittää, että rakenne.

755
00:35:29,820 --> 00:35:33,510
Ja jos toiminto binary
hakupuu kutsutaan haku,

756
00:35:33,510 --> 00:35:36,980
ja tämä ottaa kaksi argumenttia,
kokonaisluku N ja osoitin

757
00:35:36,980 --> 00:35:41,400
solmuun, joten osoitin puun
tai osoitin juureen puu,

758
00:35:41,400 --> 00:35:43,482
miten voin mennä noin etsivät N?

759
00:35:43,482 --> 00:35:45,440
No, ensinnäkin, koska olen
käsitellään osoittimet,

760
00:35:45,440 --> 00:35:46,750
Aion tehdä järki tarkistaa.

761
00:35:46,750 --> 00:35:54,279
Jos puu tasavertaisten vastaa null, on N
tässä puussa tai ei tässä puussa?

762
00:35:54,279 --> 00:35:55,070
Se ei voi olla, eikö?

763
00:35:55,070 --> 00:35:56,870
Jos olen viime null,
Siellä ei ole mitään.

764
00:35:56,870 --> 00:35:59,230
Voisin yhtä hyvin vain
sokeasti sanoa return false.

765
00:35:59,230 --> 00:36:04,050
Jos annat minulle mitään, en varmasti voi
löytäneet numero N. Mitä muuta voisin

766
00:36:04,050 --> 00:36:04,750
Tarkista nyt?

767
00:36:04,750 --> 00:36:12,830
Aion sanoa hyvin muuta, jos N on
vähemmän kuin mitä on puu solmu

768
00:36:12,830 --> 00:36:16,300
että olen ollut luovutettu N arvo.

769
00:36:16,300 --> 00:36:20,270
Toisin sanoen, jos määrä olen
etsivät, N on pienempi kuin solmun

770
00:36:20,270 --> 00:36:21,340
että Etsin.

771
00:36:21,340 --> 00:36:23,190
Ja solmu etsin
klo kutsutaan puu,

772
00:36:23,190 --> 00:36:26,370
ja muistaa edellisen esimerkin
saada aikaa arvon osoitin,

773
00:36:26,370 --> 00:36:28,310
Käytän nuoli merkintää.

774
00:36:28,310 --> 00:36:35,960
Joten jos N on pienempi kuin puu nuoli
N, haluan käsitteellisesti mennä vasemmalle.

775
00:36:35,960 --> 00:36:38,590
Miten ilmaista etsiminen jäljellä?

776
00:36:38,590 --> 00:36:41,560
Tehtävä selväksi, jos tämä on
kuva kyseessä,

777
00:36:41,560 --> 00:36:44,612
ja olen läpäissyt että ylin
nuoli, joka on alaspäin.

778
00:36:44,612 --> 00:36:45,570
Se on minun puu osoitin.

779
00:36:45,570 --> 00:36:48,060
Olen suunnattu puun juureen.

780
00:36:48,060 --> 00:36:52,100
Ja Etsin sanoa, varten
numero 44, mielivaltaisesti.

781
00:36:52,100 --> 00:36:55,300
On 44 pienempi tai
yli 55 ilmeisesti?

782
00:36:55,300 --> 00:36:56,360
Joten se on vähemmän kuin.

783
00:36:56,360 --> 00:36:58,760
Ja niin tämä jos ehto koskee.

784
00:36:58,760 --> 00:37:03,981
Joten käsitteellisesti, mitä haluan
etsi seuraava jos Etsin 44?

785
00:37:03,981 --> 00:37:04,480
Joo?

786
00:37:04,480 --> 00:37:08,310

787
00:37:08,310 --> 00:37:11,100
>> Aivan, haluan
etsi vasen lapsi,

788
00:37:11,100 --> 00:37:12,789
tai vasen osa-puu tätä kuvaa.

789
00:37:12,789 --> 00:37:14,830
Ja itse asiassa, haluan kautta
kuva täällä

790
00:37:14,830 --> 00:37:17,770
vain hetken, koska
En voi naarmuttaa tätä.

791
00:37:17,770 --> 00:37:21,150
Jos aloitan täällä 55, ja
Tiedän, että arvo 44

792
00:37:21,150 --> 00:37:23,180
Etsin on
vasemmalle, se on eräänlainen

793
00:37:23,180 --> 00:37:26,010
samankaltaisten repiminen puhelinluettelon
puolet tai repiminen puu kahtia.

794
00:37:26,010 --> 00:37:29,660
En enää tarvitse välittää
tämä koko puolet puusta.

795
00:37:29,660 --> 00:37:33,270
Ja kuitenkin, kumma suhteen
rakenne, tämä asia täällä, että

796
00:37:33,270 --> 00:37:36,682
alkaa 33, että itse
on binäärihakupuu.

797
00:37:36,682 --> 00:37:39,890
Sanoin sanan rekursiivinen ennen koska
todellakin tämä on tietorakenne, joka

798
00:37:39,890 --> 00:37:41,707
määritelmän on rekursiivinen.

799
00:37:41,707 --> 00:37:44,540
Saatat olla puu, joka on tämän
iso, mutta jokainen sen lapsista

800
00:37:44,540 --> 00:37:46,870
edustaa puu vain hieman pienempi.

801
00:37:46,870 --> 00:37:50,910
Sen sijaan se on Isoisä
tai mummo, nyt se on vain äiti

802
00:37:50,910 --> 00:37:54,300
or-- En voi say-- ei äiti
tai isä, joka olisi outoa.

803
00:37:54,300 --> 00:37:59,000
Sen sijaan kaksi lasta siellä
olisi kuin veli ja sisarus.

804
00:37:59,000 --> 00:38:01,120
Uuden sukupolven sukupuun.

805
00:38:01,120 --> 00:38:02,900
Mutta rakenteellisesti, se on sama ajatus.

806
00:38:02,900 --> 00:38:06,790
Ja se osoittautuu Minulla toiminto
jolla voin hakea binäärihaku

807
00:38:06,790 --> 00:38:07,290
puu.

808
00:38:07,290 --> 00:38:08,680
Sitä kutsutaan hakua.

809
00:38:08,680 --> 00:38:17,870
Etsin N puu nuoli vasemmalle
muuten, jos N on suurempi kuin arvo

810
00:38:17,870 --> 00:38:18,870
että olen tällä hetkellä.

811
00:38:18,870 --> 00:38:20,800
55 tarina hetki sitten.

812
00:38:20,800 --> 00:38:23,780
Minulla on toiminto nimeltään
hakukone, jonka voin vain

813
00:38:23,780 --> 00:38:29,660
siirtää N tämä ja rekursiivisesti etsiä
sub-puu ja vain paluu

814
00:38:29,660 --> 00:38:30,620
mitä se sitten vastaus.

815
00:38:30,620 --> 00:38:33,530
Else Minulla joitakin lopullinen pohja tässä tapauksessa.

816
00:38:33,530 --> 00:38:35,310
>> Mikä on lopullinen asia?

817
00:38:35,310 --> 00:38:36,570
Puu on joko nolla.

818
00:38:36,570 --> 00:38:39,980
Arvo Olen joko etsimässä on
vähemmän kuin se tai suurempi kuin

819
00:38:39,980 --> 00:38:42,610
tai yhtä suuri kuin se.

820
00:38:42,610 --> 00:38:44,750
Ja voisin sanoa yhtä suuri
tasa-arvoisia, mutta loogisesti se on

821
00:38:44,750 --> 00:38:46,500
vastaa vain sanoa muuta täällä.

822
00:38:46,500 --> 00:38:49,150
Niin totta on, miten löydän jotain.

823
00:38:49,150 --> 00:38:51,710
Joten toivottavasti tämä on
entistäkin pakottavia esimerkki

824
00:38:51,710 --> 00:38:54,900
kuin tyhmä sigma toiminto
teimme muutamia luentoja takaisin,

825
00:38:54,900 --> 00:38:58,360
jossa se oli yhtä helppo käyttää silmukka
laskea ylös kaikki numerot yhdestä

826
00:38:58,360 --> 00:39:02,390
N. täällä tietorakenne
että itse on rekursiivisesti

827
00:39:02,390 --> 00:39:07,050
määritelty ja rekursiivisesti piirretty, nyt meillä
on kyky ilmaista itseämme

828
00:39:07,050 --> 00:39:09,780
koodin että itsessään on rekursiivinen.

829
00:39:09,780 --> 00:39:12,580
Joten tämä on täsmälleen sama koodi tähän.

830
00:39:12,580 --> 00:39:14,400
>> Mitä muita ongelmia voimme ratkaista?

831
00:39:14,400 --> 00:39:18,160
Joten nopea askeleen päässä
puita vain hetken.

832
00:39:18,160 --> 00:39:20,130
Tässä on, sanovat, Saksan lipun.

833
00:39:20,130 --> 00:39:22,020
Ja siellä on selvästi
kuvio tämä lippu.

834
00:39:22,020 --> 00:39:23,811
Ja siellä on paljon
liput maailmassa

835
00:39:23,811 --> 00:39:27,560
ovat niin yksinkertaista kuin tämä suhteen
niiden värejä ja kuvioita.

836
00:39:27,560 --> 00:39:31,930
Mutta olettaa, että tämä on tallennettu
.GIF Tai JPEG, tai bittikartta, tai ping,

837
00:39:31,930 --> 00:39:34,240
tahansa graafinen tiedostomuoto
jolla olet tuttu,

838
00:39:34,240 --> 00:39:36,460
joista osa olemme
leikkii in PSET4.

839
00:39:36,460 --> 00:39:41,550
Tämä ei tunnu kannata tallentaa
musta pikseli, musta pikseli, musta pikseli,

840
00:39:41,550 --> 00:39:44,790
piste, piste, piste, koko joukko
musta pikseliä ensimmäinen juova,

841
00:39:44,790 --> 00:39:47,430
tai rivin, sitten koko joukko
sama, niin koko joukko

842
00:39:47,430 --> 00:39:49,530
sama, ja sitten
koko joukko punainen pikseliä,

843
00:39:49,530 --> 00:39:53,020
punainen pikseliä, punainen pikseliä, sitten koko
nippu keltainen pikseliä, keltainen, eikö?

844
00:39:53,020 --> 00:39:55,050
>> Siellä on niin tehottomuutta täällä.

845
00:39:55,050 --> 00:39:59,040
Miten intuitiivisesti
pakkaa Saksan lippu

846
00:39:59,040 --> 00:40:01,320
jos täytäntöönpanosta sen tiedostona?

847
00:40:01,320 --> 00:40:04,940
Kuten mitä tietoja voimme olla
vaivautua tallentamiseen levyllä järjestyksessä

848
00:40:04,940 --> 00:40:08,040
pienentää meidän tiedoston koon kuten
megatavu on kilotavu, jotain

849
00:40:08,040 --> 00:40:09,430
pienempiä?

850
00:40:09,430 --> 00:40:13,130
Jossa sijaitsee irtisanominen
tässä tehdä selväksi?

851
00:40:13,130 --> 00:40:13,880
Mitä voisit tehdä?

852
00:40:13,880 --> 00:40:14,380
Joo?

853
00:40:14,380 --> 00:40:21,380

854
00:40:21,380 --> 00:40:21,970
Aivan.

855
00:40:21,970 --> 00:40:24,550
Miksi ette ennemmin kuin muistaa
väri jokaisen hiton pikselin

856
00:40:24,550 --> 00:40:28,200
aivan kuten olet tekemässä PSET4
kanssa bitmap tiedostomuoto,

857
00:40:28,200 --> 00:40:32,060
miksi et vain edustaa
vasemmassa reunassa pikseliä, esimerkiksi

858
00:40:32,060 --> 00:40:35,370
joukko mustia pisteitä, nippu
punainen, ja joukko keltainen,

859
00:40:35,370 --> 00:40:39,210
ja sitten vain jotenkin koodata
Ajatus Toista 100 kertaa

860
00:40:39,210 --> 00:40:41,020
tai toista tämä 1000 kertaa?

861
00:40:41,020 --> 00:40:43,430
Jos 100 tai 1000 on
vain kokonaisluku, joten voit

862
00:40:43,430 --> 00:40:47,290
saada pois vain yhden numeron
sen sijaan, satoja tai tuhansia

863
00:40:47,290 --> 00:40:48,270
ylimääräisiä pikseliä.

864
00:40:48,270 --> 00:40:50,990
Ja todellakin, näin me
voisi puristaa Saksan lippu.

865
00:40:50,990 --> 00:40:51,490
Ja

866
00:40:51,490 --> 00:40:53,470
Nyt Entä Ranskan lipun?

867
00:40:53,470 --> 00:40:58,930
Ja pieni jonkinlainen
mielenterveyden käyttää, mikä lippu

868
00:40:58,930 --> 00:41:01,040
voidaan pakata enemmän levylle?

869
00:41:01,040 --> 00:41:05,720
Saksan lipun tai Ranskan
lippu, jos otamme tämän lähestymistavan?

870
00:41:05,720 --> 00:41:08,490
Saksan lippu, koska siellä
horisontaalisempaa irtisanominen.

871
00:41:08,490 --> 00:41:12,190
Ja suunnittelu, monet graafinen tiedosto
formaatit todellakin toimi ositusriviä

872
00:41:12,190 --> 00:41:12,830
vaakasuunnassa.

873
00:41:12,830 --> 00:41:14,674
He voisivat toimia
pystysuoraan, vain ihmiskunta

874
00:41:14,674 --> 00:41:17,090
päätti vuotta sitten, että me will
yleensä ajatella asioita rivi

875
00:41:17,090 --> 00:41:18,880
riviltä sijaan sarake kerrallaan.

876
00:41:18,880 --> 00:41:20,820
Joten todellakin jos olisit
tarkastella tiedosto

877
00:41:20,820 --> 00:41:24,670
koko Saksan lipun ja ranskalainen
lippu, niin kauan kuin päätöslauselma on

878
00:41:24,670 --> 00:41:27,530
sama, sama leveys
ja korkeus, tämä

879
00:41:27,530 --> 00:41:31,580
täällä tulee olemaan suurempi, koska olet
on toistettava itse kolme kertaa.

880
00:41:31,580 --> 00:41:35,570
Sinun täytyy määrittää sininen, toista
itse, valkoinen, toista itseäsi, punainen,

881
00:41:35,570 --> 00:41:36,740
Toistan itse.

882
00:41:36,740 --> 00:41:39,000
Et voi vain mennä
aivan oikealle.

883
00:41:39,000 --> 00:41:41,200
Ja syrjään, jotta
tyhjentää puristus

884
00:41:41,200 --> 00:41:43,910
on kaikkialla, jos nämä ovat
neljä kehyksiä video-- sinua

885
00:41:43,910 --> 00:41:45,890
Muistanette, että elokuva
tai video on yleensä

886
00:41:45,890 --> 00:41:47,286
kuten 29 tai 30 kuvaa sekunnissa.

887
00:41:47,286 --> 00:41:50,410
Se on kuin pieni läppä kirja, jossa
vain nähdä kuva, kuva, kuva, kuva,

888
00:41:50,410 --> 00:41:54,410
kuva vain huippunopea niin se näyttää
toimijoiden ruudulla liikkuvat.

889
00:41:54,410 --> 00:41:57,130
Tässä kimalaisten päälle
alkuun kukkakimpun.

890
00:41:57,130 --> 00:41:59,790
Ja vaikka se voisi olla eräänlainen
vaikea nähdä ensi silmäyksellä,

891
00:41:59,790 --> 00:42:04,020
ainoa asia liikkuvat
tämä elokuva on mehiläinen.

892
00:42:04,020 --> 00:42:06,880
>> Mikä on tyhmä varastoinnista
video pakkaamattomana?

893
00:42:06,880 --> 00:42:11,420
Se on tavallaan jätteiden tallentaa video
neljä lähes identtinen kuvien

894
00:42:11,420 --> 00:42:13,670
poikkeavat toisistaan ​​vain siltä osin kuin jos mehiläinen on.

895
00:42:13,670 --> 00:42:16,280
Voit heittää pois useimmat
näistä tiedoista

896
00:42:16,280 --> 00:42:20,190
ja muistan vain, esimerkiksi,
ensimmäinen runko ja viimeisen kuvan,

897
00:42:20,190 --> 00:42:22,180
Avainruutujen jos olet
koskaan kuullut sanan,

898
00:42:22,180 --> 00:42:24,337
ja vain säilytä
keskimmäinen jossa mehiläinen on.

899
00:42:24,337 --> 00:42:26,170
Ja sinun ei tarvitse
tallentaa kaikki vaaleanpunainen,

900
00:42:26,170 --> 00:42:28,330
ja sininen, ja
vihreät arvot samoin.

901
00:42:28,330 --> 00:42:31,200
Joten tämä on vain sanoa, että
puristus on kaikkialla.

902
00:42:31,200 --> 00:42:34,900
Se on tekniikka käytämme usein
tai ottaa itsestäänselvyytenä näinä päivinä.

903
00:42:34,900 --> 00:42:38,750
>> Mutta miten pakata tekstin?

904
00:42:38,750 --> 00:42:40,450
Miten te sitten puristamalla tekstiä?

905
00:42:40,450 --> 00:42:45,410
No, jokainen merkkiä
ASCII on yksi tavu, tai kahdeksan bittiä.

906
00:42:45,410 --> 00:42:47,360
Ja se on tavallaan tyhmä, eikö?

907
00:42:47,360 --> 00:42:51,160
Koska olet todennäköisesti kirjoitat
ja E ja I ja O ja U paljon

908
00:42:51,160 --> 00:42:55,270
useammin kuin kuten W tai Q tai Z,
riippuen kielestä, jolla

909
00:42:55,270 --> 00:42:56,610
kirjoitat varmasti.

910
00:42:56,610 --> 00:42:59,600
Ja niin miksi käytämme
kahdeksan bittiä jokaisen kirjeen,

911
00:42:59,600 --> 00:43:02,040
mukaan lukien vähiten
suosittu kirjaimia, eikö?

912
00:43:02,040 --> 00:43:05,300
Miksi ei käytä vähemmän bittiä
Super suosittu kirjaimet,

913
00:43:05,300 --> 00:43:07,760
kuten E, mitä arvata
ensimmäinen Wheel of Fortune,

914
00:43:07,760 --> 00:43:10,450
ja käyttää enemmän bittiä
vähemmän suosittu kirjaimet?

915
00:43:10,450 --> 00:43:10,950
Miksi?

916
00:43:10,950 --> 00:43:13,130
Koska olemme juuri menossa
käyttää niitä harvemmin.

917
00:43:13,130 --> 00:43:15,838
>> No, käy ilmi, että siellä on
ollut yritetty tehdä tätä.

918
00:43:15,838 --> 00:43:18,630
Ja jos muistaa palkkaluokasta
koulu tai lukion, morseaakkoset.

919
00:43:18,630 --> 00:43:20,400
Morseaakkoset on pisteitä
ja viivoja, jotka voivat olla

920
00:43:20,400 --> 00:43:24,270
lähetetty pitkin lanka
ääniä tai signaaleja jonkinlaisia.

921
00:43:24,270 --> 00:43:25,930
Mutta Morse koodi on super clean.

922
00:43:25,930 --> 00:43:29,010
Se on tavallaan binary järjestelmän
että sinulla on pisteitä tai viivoja.

923
00:43:29,010 --> 00:43:30,977
Mutta jos näet esimerkiksi kaksi pistettä.

924
00:43:30,977 --> 00:43:33,810
Tai jos luulet takaisin toimijalle
joka menee piip, piip, piip,

925
00:43:33,810 --> 00:43:36,760
äänimerkin, lyömällä hieman laukaista
joka lähettää signaalin,

926
00:43:36,760 --> 00:43:40,360
jos, vastaanottaja, saa kaksi
pisteitä, minkä viestin olet saanut?

927
00:43:40,360 --> 00:43:43,490
Täysin mielivaltaista.

928
00:43:43,490 --> 00:43:44,450
>> I?

929
00:43:44,450 --> 00:43:45,060
I?

930
00:43:45,060 --> 00:43:47,500
Tai mitä about-- tai I?

931
00:43:47,500 --> 00:43:49,570
Ehkä se oli vain kaksi E oikeutta?

932
00:43:49,570 --> 00:43:52,480
Joten ei tämä ongelma
ja decodability kanssa Morse

933
00:43:52,480 --> 00:43:54,890
koodi, jolloin jollei
henkilö lähettää sinulle viestin

934
00:43:54,890 --> 00:43:59,510
todella pysähtyy joten voit lajitella
nähdä tai kuulla erot kirjaimet,

935
00:43:59,510 --> 00:44:02,990
se ei ole riittävää vain
Lähetä virta nollia ja ykkösiä,

936
00:44:02,990 --> 00:44:05,610
tai pisteitä ja viivoja,
koska siellä on epäselvyyttä.

937
00:44:05,610 --> 00:44:08,640
E on yksi piste, joten jos
katso kaksi pistettä tai kuulet kaksi pistettä,

938
00:44:08,640 --> 00:44:11,254
ehkä se on kaksi E: n tai ehkä se on yksi I.

939
00:44:11,254 --> 00:44:13,670
Joten tarvitsemme järjestelmän, joka on
hieman viisaampi kuin.

940
00:44:13,670 --> 00:44:16,851
Joten mies nimeltä Huffman vuotta
sitten keksi juuri tämän.

941
00:44:16,851 --> 00:44:18,600
Joten me vain menossa
ottaa nopealla silmäyksellä

942
00:44:18,600 --> 00:44:20,114
kuinka puut ovat Germane tähän.

943
00:44:20,114 --> 00:44:22,530
Oletetaan, että tämä on noin
tyhmä viesti, jonka haluat lähettää,

944
00:44:22,530 --> 00:44:26,342
koostuu vain A, B, C: n D: n ja E: n,
mutta siellä on paljon irtisanomisten täällä.

945
00:44:26,342 --> 00:44:27,550
Se ei ole tarkoitus olla Englanti.

946
00:44:27,550 --> 00:44:28,341
Se ei ole salattu.

947
00:44:28,341 --> 00:44:30,540
Se on vain tyhmä viestiä
jossa on paljon toistoa.

948
00:44:30,540 --> 00:44:34,010
Joten jos todella laskea kaikki
N, B: n, C: n, D: n ja E: n, tässä

949
00:44:34,010 --> 00:44:34,890
taajuus.

950
00:44:34,890 --> 00:44:37,800
20% kirjaimet ovat
A: n, 45%: n kirjainten

951
00:44:37,800 --> 00:44:39,660
ovat E: n, ja kolme muita taajuuksia.

952
00:44:39,660 --> 00:44:41,960
Laskimme siellä manuaalisesti
ja vain teki matematiikka.

953
00:44:41,960 --> 00:44:44,579
>> Joten käy ilmi, että
Huffman, jokin aika sitten,

954
00:44:44,579 --> 00:44:46,620
tajusi, että tiedät
mitä, jos aloitan rakennus

955
00:44:46,620 --> 00:44:51,172
puu, tai metsä puita, jos haluatte,
seuraavasti, voin tehdä seuraavasti.

956
00:44:51,172 --> 00:44:53,880
Aion antaa solmuun jokaiselle
kirjaimet, jotka välitän

957
00:44:53,880 --> 00:44:55,530
ja aion säilyttää
sisällä että solmun

958
00:44:55,530 --> 00:44:58,610
taajuuksia liukuluku
arvo, tai voit käyttää sitä N, liian,

959
00:44:58,610 --> 00:45:00,210
mutta me vain käyttää float täällä.

960
00:45:00,210 --> 00:45:03,100
Ja algoritmi
hän ehdotti, että te

961
00:45:03,100 --> 00:45:07,210
tätä metsä yhden solmun
puita, joten Super lyhyt puita,

962
00:45:07,210 --> 00:45:11,920
ja aloitat liittämällä ne
uusia ryhmiä, uudet vanhemmat, jos haluatte.

963
00:45:11,920 --> 00:45:16,150
Ja voit tehdä tämän valitsemalla
kaksi pienintä taajuutta kerrallaan.

964
00:45:16,150 --> 00:45:18,110
Joten otin 10% ja 10%.

965
00:45:18,110 --> 00:45:19,090
Luon uuden solmu.

966
00:45:19,090 --> 00:45:20,910
Ja kehotan uusi solmu 20%.

967
00:45:20,910 --> 00:45:22,750
>> Joka kahden solmun yhdistän seuraavaksi?

968
00:45:22,750 --> 00:45:23,810
Se on vähän epäselvä.

969
00:45:23,810 --> 00:45:26,643
Joten on joitakin nurkkaan tapauksissa
harkita, mutta pitää asiat melko,

970
00:45:26,643 --> 00:45:29,300
Aion valita 20% -
Olen nyt sivuuttaa lapsia.

971
00:45:29,300 --> 00:45:33,640
Aion valita 20% ja
15% ja piirtää kaksi uutta reunat.

972
00:45:33,640 --> 00:45:35,624
Ja nyt joka kahden solmun
voin loogisesti yhdistää?

973
00:45:35,624 --> 00:45:38,540
Ohita kaikki lapset, kaikki
lapsenlapset, katsokaa juuret

974
00:45:38,540 --> 00:45:39,070
nyt.

975
00:45:39,070 --> 00:45:42,220
Mitkä kaksi solmua voin sitoa yhteen?

976
00:45:42,220 --> 00:45:44,530
Kohta kaksi ja 0,35.

977
00:45:44,530 --> 00:45:45,890
Sallikaa minun tehdä kaksi uutta reunat.

978
00:45:45,890 --> 00:45:47,570
Ja sitten Minulla on vain yksi jäljellä.

979
00:45:47,570 --> 00:45:48,650
Joten tässä on puu.

980
00:45:48,650 --> 00:45:51,160
Ja se on laadittu tarkoituksella
etsiä sellainen aika,

981
00:45:51,160 --> 00:45:55,870
mutta huomaa, että reunat ovat
myös merkitty nolla ja yksi.

982
00:45:55,870 --> 00:45:59,510
Joten kaikki vasemmat reunat ovat nolla
mielivaltaisesti, mutta johdonmukaisesti.

983
00:45:59,510 --> 00:46:01,170
Kaikki oikeat reunat ovat sellaisia.

984
00:46:01,170 --> 00:46:05,070
>> Ja niin mitä Hoffman ehdotetaan,
jos haluat edustaa B,

985
00:46:05,070 --> 00:46:10,080
sijaan edustavat useita 66
Ascii joka on kahdeksan koko bittiä,

986
00:46:10,080 --> 00:46:13,360
Tiedätkö mitä, juuri myymälä
kuvio nolla, nolla, nolla,

987
00:46:13,360 --> 00:46:17,030
nolla, koska se on polku
minun puu, herra Huffman n puu,

988
00:46:17,030 --> 00:46:18,600
lehteen juuresta.

989
00:46:18,600 --> 00:46:20,970
Jos haluat tallentaa
E, sitä vastoin eivät

990
00:46:20,970 --> 00:46:26,290
Lähetä kahdeksan bittiä, jotka edustavat E.
Sen sijaan, lähettää mitä kuvio bittiä?

991
00:46:26,290 --> 00:46:26,890
Yksi.

992
00:46:26,890 --> 00:46:30,410
Ja mitä mukavaa tästä on
että E on suosituin kirjeen,

993
00:46:30,410 --> 00:46:32,340
ja käytät
lyhin koodia.

994
00:46:32,340 --> 00:46:34,090
Seuraavaksi suosituimpia
kirjain näyttää se

995
00:46:34,090 --> 00:46:37,380
oli A. Ja niin kuinka monta bittiä
hän ehdottaa käyttävät tätä?

996
00:46:37,380 --> 00:46:38,270
Nolla, yksi.

997
00:46:38,270 --> 00:46:41,060
>> Ja koska se on pantu täytäntöön
koska tämä puu, nyt

998
00:46:41,060 --> 00:46:43,350
haluaisin määrätä siellä
ei epäselvyyttä Morse

999
00:46:43,350 --> 00:46:46,090
koodi, koska kaikki
kirjeitä välität

1000
00:46:46,090 --> 00:46:48,780
ovat lopussa näiden reunojen.

1001
00:46:48,780 --> 00:46:50,580
Niin se on vain yksi
soveltaminen puu.

1002
00:46:50,580 --> 00:46:52,538
Tämä is-- ja minä aalto
käteni tässä miten

1003
00:46:52,538 --> 00:46:55,570
voisi toteuttaa tätä C rakenne.

1004
00:46:55,570 --> 00:46:58,260
Meidän täytyy vain yhdistää
symboli, kuten char,

1005
00:46:58,260 --> 00:46:59,910
ja taajuus vasemmalle ja oikealle.

1006
00:46:59,910 --> 00:47:02,510
Mutta katsokaamme kaksi
lopullinen esimerkkejä että sinun

1007
00:47:02,510 --> 00:47:06,070
saada varsin tuttuja jälkeen
tietokilpailu nolla ongelma asettaa viisi.

1008
00:47:06,070 --> 00:47:09,210
>> Joten on datarakenne
tunnetaan hajautustaulua.

1009
00:47:09,210 --> 00:47:12,247
Ja hash table on eräänlainen
jäähtyä että se on kauhat.

1010
00:47:12,247 --> 00:47:14,830
Ja oletetaan siellä on neljä kauhat
täällä, vain neljä välilyöntejä.

1011
00:47:14,830 --> 00:47:20,830
Tässä korttipakan, ja täällä on
Club, lapio, klubi, timantit, klubi,

1012
00:47:20,830 --> 00:47:25,960
timantteja, klubi, timantit,
clubs-- joten tämä on satunnainen.

1013
00:47:25,960 --> 00:47:30,330
Hearts, hearts-- joten olen
bucketizing kaikille lähteille täällä.

1014
00:47:30,330 --> 00:47:32,430
Ja tiiviste tarpeisiin
katsomaan teidän panos,

1015
00:47:32,430 --> 00:47:34,850
ja sitten laittaa se tietyllä
aseta perustuu mitä näet.

1016
00:47:34,850 --> 00:47:35,600
Se algoritmia.

1017
00:47:35,600 --> 00:47:37,980
Ja Käytin super
yksinkertainen visuaalinen algoritmi.

1018
00:47:37,980 --> 00:47:40,030
Vaikein osa oli
muistaa, mitä kuvat olivat.

1019
00:47:40,030 --> 00:47:41,590
Ja sitten on neljä yhteensä asioita.

1020
00:47:41,590 --> 00:47:45,440
>> Nyt pinot kasvoivat, mikä
on tarkoituksellinen suunnittelu asia täällä.

1021
00:47:45,440 --> 00:47:46,540
Mutta mitä muuta voisi tehdä?

1022
00:47:46,540 --> 00:47:49,080
Joten oikeastaan ​​täällä meillä
joukko vanhoja koulun tenttikirjat.

1023
00:47:49,080 --> 00:47:51,240
Oletetaan, että joukko
opiskelijat nimet ovat täällä.

1024
00:47:51,240 --> 00:47:52,570
Tässä isompi hajautustaulua.

1025
00:47:52,570 --> 00:47:54,867
Neljän sijasta kauhat,
Olen, sanokaamme 26.

1026
00:47:54,867 --> 00:47:57,950
Ja emme halua mennä lainata 26
asioita ulkopuolelta [? Annenberg?], Niin

1027
00:47:57,950 --> 00:48:00,289
tässä on viisi, jotka edustavat
Z. Ja jos minä

1028
00:48:00,289 --> 00:48:03,580
katso opiskelija nimi alkaa,
Aion laittaa hänen tietokilpailu siellä.

1029
00:48:03,580 --> 00:48:08,850
Jos joku alkaa C, tuolla,
A-- oikeastaan, ei halua tehdä sitä.

1030
00:48:08,850 --> 00:48:10,060
B menee tänne.

1031
00:48:10,060 --> 00:48:13,390
Joten minulla ja B ja C And
nyt tässä on toinen opiskelija.

1032
00:48:13,390 --> 00:48:16,212
Mutta jos tämä tiiviste on
toteutettu joukko,

1033
00:48:16,212 --> 00:48:17,920
Olen sellainen ruuvattu
tässä vaiheessa, eikö?

1034
00:48:17,920 --> 00:48:19,510
Olen sellainen täytyy laittaa tämä jonnekin.

1035
00:48:19,510 --> 00:48:24,380
>> Joten yksi tapa voin ratkaista tämä on, kaikki
oikea, on kiireinen, B on varattu, C on varattu.

1036
00:48:24,380 --> 00:48:28,880
Aion laittaa hänet D. Joten
ensimmäinen, minulla on satunnainen välittömän pääsyn

1037
00:48:28,880 --> 00:48:31,064
kuhunkin kauhat opiskelijoille.

1038
00:48:31,064 --> 00:48:33,230
Mutta nyt se on tavallaan hajautettujen
jotain lineaarinen,

1039
00:48:33,230 --> 00:48:36,750
koska jos haluan etsiä joku
jonka nimi alkaa, tarkistan täällä.

1040
00:48:36,750 --> 00:48:38,854
Mutta jos tämä ei ole
opiskelija Etsin,

1041
00:48:38,854 --> 00:48:41,520
Olen sellainen täytyy aloittaa tarkkailun
kauhat, sillä mitä tein

1042
00:48:41,520 --> 00:48:44,530
oli tavallaan lineaarisesti
koetin tietorakennetta.

1043
00:48:44,530 --> 00:48:47,710
Typerä tapa sanoa katsokaa
ensimmäisen käytettävissä aukon,

1044
00:48:47,710 --> 00:48:51,850
ja laittaa niin suunnitelma B, niin sanoakseni,
tai suunnitelma D tässä tapauksessa arvo

1045
00:48:51,850 --> 00:48:53,340
kyseisessä paikassa sijaan.

1046
00:48:53,340 --> 00:48:56,470
Tämä on vain niin, että jos olet
sai 26 paikkakunnalla ja ei opiskelijoiden

1047
00:48:56,470 --> 00:49:00,600
nimi Q tai Z, tai jotain
että ainakin käytät tilaa.

1048
00:49:00,600 --> 00:49:03,140
>> Mutta olemme jo nähneet enemmän
fiksu ratkaisuja täällä, eikö?

1049
00:49:03,140 --> 00:49:04,870
Mitä sinä tekisit sen sijaan
jos sinulla on törmäyksen?

1050
00:49:04,870 --> 00:49:06,670
Jos kaksi ihmistä on
nimi, mitä olisi

1051
00:49:06,670 --> 00:49:09,160
ovat älykkäämpiä tai enemmän
intuitiivinen ratkaisu kuin vain

1052
00:49:09,160 --> 00:49:12,840
laskemisesta jossa D on tarkoitus olla?

1053
00:49:12,840 --> 00:49:14,810
Miksi en vain mennä
ulkopuolella [? Annenberg?],

1054
00:49:14,810 --> 00:49:19,960
kuten malloc, toinen solmu, laita se
täällä, ja sitten laittaa että opiskelija täällä.

1055
00:49:19,960 --> 00:49:22,120
Niin että olen lähinnä on
jonkinlainen array,

1056
00:49:22,120 --> 00:49:25,590
tai ehkä enemmän tyylikkäästi kuin olemme
alkavat nähdä linkitetty lista.

1057
00:49:25,590 --> 00:49:29,520
>> Ja niin hash table on rakenne
että voisi näyttää aivan kuten tämä,

1058
00:49:29,520 --> 00:49:33,900
mutta enemmän taitavasti, jotain nimeltään
erillinen ketjutus, jolloin tiiviste

1059
00:49:33,900 --> 00:49:38,340
yksinkertaisesti on joukko, jokaisen
jonka alkiot ei ole numero,

1060
00:49:38,340 --> 00:49:40,470
on itse linkitetty lista.

1061
00:49:40,470 --> 00:49:45,080
Niin että saat erittäin nopean pääsyn
päätettäessä, missä hash oman arvon.

1062
00:49:45,080 --> 00:49:48,059
Aivan kuten kanssa korttien esimerkiksi
Tein erittäin nopeita päätöksiä.

1063
00:49:48,059 --> 00:49:49,600
Hearts menee täällä, timantit menee täällä.

1064
00:49:49,600 --> 00:49:52,180
Sama täällä, menee täällä,
D menee täällä, B menee täällä.

1065
00:49:52,180 --> 00:49:55,740
Joten huippunopea look-ups, ja jos
satut törmätä tapaus

1066
00:49:55,740 --> 00:49:59,429
jossa sinulla törmäyksiä, kaksi
ihmiset samanniminen, hyvin sitten

1067
00:49:59,429 --> 00:50:00,970
vain alkaa liittämällä ne yhteen.

1068
00:50:00,970 --> 00:50:03,900
Ja ehkä pitää ne lajitellaan
aakkosjärjestyksessä, ehkä et.

1069
00:50:03,900 --> 00:50:05,900
Mutta ainakin nyt meillä on dynamiikkaa.

1070
00:50:05,900 --> 00:50:10,250
Niin toisaalta meillä on huippunopea
vakio aika, ja tavallaan lineaarisen ajan

1071
00:50:10,250 --> 00:50:14,110
mukana jos nämä liittyvät luettelot
alkaa saada hieman pitkä.

1072
00:50:14,110 --> 00:50:16,880
>> Joten tällainen typerä,
geeky vitsi vuotta sitten.

1073
00:50:16,880 --> 00:50:19,590
Klo CS50 hakata--thon,
kun opiskelijat tarkistaa,

1074
00:50:19,590 --> 00:50:22,040
jotkut TF tai CA vuosittain
mielestä on hauska sietää

1075
00:50:22,040 --> 00:50:27,772
merkki näin, jos se vain
tarkoittaa jos nimi alkaa,

1076
00:50:27,772 --> 00:50:28,870
mennä tällä tavalla.

1077
00:50:28,870 --> 00:50:31,110
Jos nimesi alkaa
jossa B, mene this-- OK,

1078
00:50:31,110 --> 00:50:33,290
se on hauskaa ehkä myöhemmin lukukauden.

1079
00:50:33,290 --> 00:50:36,420
Mutta on toinen
tapa tehdä tämä, liian.

1080
00:50:36,420 --> 00:50:37,410
Tule takaisin, että.

1081
00:50:37,410 --> 00:50:38,600
>> Joten on tämä rakenne.

1082
00:50:38,600 --> 00:50:40,420
Ja tämä on meidän viimeinen
rakenne tänään,

1083
00:50:40,420 --> 00:50:42,400
joka on jotain kutsutaan trie.

1084
00:50:42,400 --> 00:50:47,140
T-R-I-E, joka jostain syystä on lyhyt
koskevia hakuja, mutta sitä kutsutaan trie.

1085
00:50:47,140 --> 00:50:51,389
Joten trie on toinen mielenkiintoinen
amalgaami paljon näitä ajatuksia.

1086
00:50:51,389 --> 00:50:52,930
Se on puu, joka olemme nähneet aiemmin.

1087
00:50:52,930 --> 00:50:54,180
Se ei ole binäärihakupuu.

1088
00:50:54,180 --> 00:50:58,410
Se on puu väliä Lasten lukumäärä,
mutta jokainen lasten trie

1089
00:50:58,410 --> 00:51:00,090
on jono.

1090
00:51:00,090 --> 00:51:04,790
Taulukon koko, sanovat, 26 tai ehkä 27
jos haluat tukea väliviivalliset nimet

1091
00:51:04,790 --> 00:51:06,790
tai heittomerkit ihmisten nimet.

1092
00:51:06,790 --> 00:51:08,280
>> Ja niin tämä on tietorakenne.

1093
00:51:08,280 --> 00:51:10,290
Ja jos tarkastellaan ylhäältä
alas, kuten jos

1094
00:51:10,290 --> 00:51:13,710
katso yläsolmun siellä, M, on
osoittaa vasemmanpuoleisin asia siellä,

1095
00:51:13,710 --> 00:51:17,665
joka sitten, X, W, E, L, L. Tämä on
vain tiedot rakenne, joka mielivaltaisesti

1096
00:51:17,665 --> 00:51:19,120
on tallentamiseen ihmisten nimet.

1097
00:51:19,120 --> 00:51:25,720
Ja Maxwell on tallentaa vain seuraavia
polku array array array.

1098
00:51:25,720 --> 00:51:30,050
Mutta mikä on hämmästyttävää noin trie on
että, kun taas linkitetty lista ja jopa

1099
00:51:30,050 --> 00:51:34,520
array, paras olemme koskaan saanut on
lineaarisen ajan tai logaritminen aikaa etsimässä

1100
00:51:34,520 --> 00:51:35,600
jonkun kyytiin.

1101
00:51:35,600 --> 00:51:40,530
Tämän datarakenteen trien, jos
tietoni rakenne on yksi nimi sen

1102
00:51:40,530 --> 00:51:43,720
ja etsin Maxwell, minä olen
menossa löytää hänet melko nopeasti.

1103
00:51:43,720 --> 00:51:47,910
Minä vain etsiä M--X-W-E-L-L. Jos
Näiden tietojen rakenne, sitä vastoin,

1104
00:51:47,910 --> 00:51:51,830
jos N on miljoona, jos on
miljoonaa nimeä tässä datarakenteeseen

1105
00:51:51,830 --> 00:51:57,100
Maxwell on edelleen olemaan
löydettävissä jälkeen vain M--X-W-E-L-L

1106
00:51:57,100 --> 00:51:58,090
vaiheet.

1107
00:51:58,090 --> 00:52:01,276
Ja David-- D--V-I-D-vaiheita.

1108
00:52:01,276 --> 00:52:03,400
Toisin sanoen, rakentamalla
tietorakenne, joka on

1109
00:52:03,400 --> 00:52:07,240
sai kaikki nämä ryhmät, jotka kaikki
itse tukea random access,

1110
00:52:07,240 --> 00:52:11,090
Voin aloittaa etsii ihmisten
nimi käyttämällä aikaa, joka on

1111
00:52:11,090 --> 00:52:14,340
verrannollinen ei numero
asioita tietorakenteen,

1112
00:52:14,340 --> 00:52:16,330
kuin miljoona nykyiset nimet.

1113
00:52:16,330 --> 00:52:20,135
Aikaa se vie minut löytää
M--X-W-E-L-L tällä tietorakenne on

1114
00:52:20,135 --> 00:52:22,260
verrannollinen ei
datan koko rakenteen,

1115
00:52:22,260 --> 00:52:25,930
vaan nimen pituus.

1116
00:52:25,930 --> 00:52:28,440
Ja realistisesti
nimet etsimme ylös

1117
00:52:28,440 --> 00:52:29,970
eivät koskaan hullu pitkä.

1118
00:52:29,970 --> 00:52:32,600
Ehkä joku on 10 merkki
nimi, 20 nimi.

1119
00:52:32,600 --> 00:52:33,900
Se on varmasti rajallinen, eikö?

1120
00:52:33,900 --> 00:52:37,110
On ihmisen maan päällä, jotka
on pisin mahdollinen nimi,

1121
00:52:37,110 --> 00:52:39,920
mutta nimi on vakio
arvo pituus, eikö?

1122
00:52:39,920 --> 00:52:41,980
Se ei vaihtele millään tavoin.

1123
00:52:41,980 --> 00:52:45,090
Joten tällä tavalla, olemme
saavutti tietorakenne

1124
00:52:45,090 --> 00:52:47,800
joka on vakio aika look-up.

1125
00:52:47,800 --> 00:52:50,670
Se kestää useita vaiheita
pituudesta riippuen syötteen,

1126
00:52:50,670 --> 00:52:54,250
mutta ei määrää nimi
tietorakenteen.

1127
00:52:54,250 --> 00:52:58,700
Joten jos me kaksinkertainen määrä nimien
ensi vuoden miljardista kahteen miljardiin,

1128
00:52:58,700 --> 00:53:03,720
havainto Maxwell vie
täsmälleen sama määrä seitsemän vaihetta

1129
00:53:03,720 --> 00:53:04,650
löytää hänet.

1130
00:53:04,650 --> 00:53:08,810
Ja niin me näytämme saavuttaneet
Meidän pyhä Graal ajoaikaan.

1131
00:53:08,810 --> 00:53:10,860
>> Joten Muutaman nopean ilmoituksia.

1132
00:53:10,860 --> 00:53:11,850
Quiz nolla on tulossa.

1133
00:53:11,850 --> 00:53:14,600
Siitä lisää kurssin verkkosivuilla
seuraavien parin päivän.

1134
00:53:14,600 --> 00:53:17,120
Maanantain lecture-- se loma
täällä Harvardissa maanantaina.

1135
00:53:17,120 --> 00:53:18,850
Se ei ole New Haven,
joten viemme luokka

1136
00:53:18,850 --> 00:53:20,310
New Haven luento maanantaina.

1137
00:53:20,310 --> 00:53:22,550
Kaikki on filmattu
ja suoratoistona kuten tavallista,

1138
00:53:22,550 --> 00:53:24,900
mutta Lopetetaan tänään
30 s leike

1139
00:53:24,900 --> 00:53:26,910
nimeltään "Deep Ajatuksia"
by Daven Farnham, joka

1140
00:53:26,910 --> 00:53:30,850
innostui viime vuonna lauantai
Night Liven "syvä ajatuksia"

1141
00:53:30,850 --> 00:53:35,700
Jack Handy, joka
olisi nyt järkevää.

1142
00:53:35,700 --> 00:53:38,810
>> FILM: Ja nyt, "Deep
Ajatuksia "by Daven Farnham.

1143
00:53:38,810 --> 00:53:42,100

1144
00:53:42,100 --> 00:53:42,870
Tiiviste.

1145
00:53:42,870 --> 00:53:45,940

1146
00:53:45,940 --> 00:53:47,660
>> SPEAKER 1: Okei, siinä se nyt.

1147
00:53:47,660 --> 00:53:48,805
Nähdään ensi viikolla.

1148
00:53:48,805 --> 00:53:55,380

1149
00:53:55,380 --> 00:53:56,680
>> DOUG: Voit nähdä sen toiminnassa.

1150
00:53:56,680 --> 00:53:58,304
Joten katsomaan juuri nyt.

1151
00:53:58,304 --> 00:53:59,890
Joten tässä, meillä on lajittelemattoman jono.

1152
00:53:59,890 --> 00:54:04,860
>> IAN: Doug, voit mennä eteenpäin ja uudelleenkäynnistys
tämä vain yksi sekunti, kiitos.

1153
00:54:04,860 --> 00:54:08,562
Selvä, kamerat liikkuva, joten
toimenpiteet kun olet valmis, Doug, OK?

1154
00:54:08,562 --> 00:54:11,020
DOUG: Hyvä on, niin mitä me
on tässä lajittelematonta array.

1155
00:54:11,020 --> 00:54:13,960
Ja olen värillinen kaikki elementit
punaisena, eli se on, itse asiassa,

1156
00:54:13,960 --> 00:54:14,460
lajittelemattomana.

1157
00:54:14,460 --> 00:54:17,960
Niin muistaa, että ensimmäinen asia, teemme
on me lajitella vasen puoli jono.

1158
00:54:17,960 --> 00:54:20,630
Sitten lajitella oikea
puolet jono.

1159
00:54:20,630 --> 00:54:22,830
Ja ya-da, ya-da, ya-da,
me yhdistää ne yhteen.

1160
00:54:22,830 --> 00:54:24,520
Ja meillä on täysin lajitellun array.

1161
00:54:24,520 --> 00:54:25,360
Niin, että miten yhdistää lajitella toimii.

1162
00:54:25,360 --> 00:54:27,109
>> IAN: Hei, hei, hei,
leikata, leikata, leikata, cut.

1163
00:54:27,109 --> 00:54:30,130
Doug, et voi vain ya-da, ya-da,
ya-da, läpi yhdistämisen lajitella.

1164
00:54:30,130 --> 00:54:31,970
>> DOUG: tein.

1165
00:54:31,970 --> 00:54:32,832
Se on okei.

1166
00:54:32,832 --> 00:54:33,540
Olemme hyvä mennä.

1167
00:54:33,540 --> 00:54:34,760
Haluan vain rullaa.

1168
00:54:34,760 --> 00:54:35,380
Niin joka tapauksessa,

1169
00:54:35,380 --> 00:54:37,800
>> IAN: on selitettävä
se täydellisemmin kuin.

1170
00:54:37,800 --> 00:54:39,999
Se vain ei ole tarpeeksi.

1171
00:54:39,999 --> 00:54:41,790
DOUG: Ian, emme
täytyy mennä takaisin yhteen.

1172
00:54:41,790 --> 00:54:42,350
Se on okei.

1173
00:54:42,350 --> 00:54:45,690
Niin joka tapauksessa, jos jatkamme merge--
Ian, olemme keskellä kuvaamisen.

1174
00:54:45,690 --> 00:54:46,612
>> IAN: Tiedän.

1175
00:54:46,612 --> 00:54:49,320
Ja emme voi vain ya-da, ya-da,
ya-da, läpi koko prosessin.

1176
00:54:49,320 --> 00:54:52,200
Sinun täytyy selittää, miten
osapuolet saavat yhdistyivät.

1177
00:54:52,200 --> 00:54:53,570
>> DOUG: Mutta olemme jo
selitti kuinka kaksi sides--

1178
00:54:53,570 --> 00:54:55,321
>> IAN: Olet juuri osoittanut
niitä yhdistää joukko.

1179
00:54:55,321 --> 00:54:56,486
DOUG: He tietävät prosessi.

1180
00:54:56,486 --> 00:54:57,172
He ovat kunnossa.

1181
00:54:57,172 --> 00:54:58,380
Olemme menneet yli kymmenen kertaa.

1182
00:54:58,380 --> 00:55:00,330
>> IAN: Sinä vain ohitetaan oikeus yli sen.

1183
00:55:00,330 --> 00:55:03,360
Menemme takaisin yhteen, sinulle
voi sinua ya-da, ya-da sen yli.

1184
00:55:03,360 --> 00:55:05,480
Okei, takaisin yhteen.

1185
00:55:05,480 --> 00:55:07,833
>> DOUG: Minun täytyy mennä takaisin
läpi kaikki diat?

1186
00:55:07,833 --> 00:55:08,332
Jumalani.

1187
00:55:08,332 --> 00:55:11,008

1188
00:55:11,008 --> 00:55:13,004
Se on kuin kuudennen kerran, Ian.

1189
00:55:13,004 --> 00:55:13,940
Se on okei.

1190
00:55:13,940 --> 00:55:15,200
>> IAN: Selvä.

1191
00:55:15,200 --> 00:55:16,590
Oletko valmis?

1192
00:55:16,590 --> 00:55:17,400
Suuri.

1193
00:55:17,400 --> 00:55:18,950
Toimi.