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

2
00:00:10,900 --> 00:00:15,860
>> SPEAKER 1: Labi, tāpēc tas ir
CS50 Tas ir nedēļas beigām pieci.

3
00:00:15,860 --> 00:00:19,220
Un atgādināt, ka pēdējo reizi, kad mēs
sākās apskatot mīļotājs datiem

4
00:00:19,220 --> 00:00:22,310
struktūras, kas sāka risināt
problēmas, kas sāka ieviest

5
00:00:22,310 --> 00:00:25,640
jaunas problēmas, bet galvenais, lai tas
bija tāda veida Threading, ka mēs

6
00:00:25,640 --> 00:00:27,940
sāka darīt no mezgla uz mezglu.

7
00:00:27,940 --> 00:00:30,085
Tātad tas, protams, ir
atsevišķi saistīts saraksts.

8
00:00:30,085 --> 00:00:31,960
Un atsevišķi saistītas,
Es domāju, ka ir tikai viens

9
00:00:31,960 --> 00:00:33,380
diegu starp katru no šiem punktiem.

10
00:00:33,380 --> 00:00:35,890
Izrādās, jūs varat darīt mīļotājs
lietas, piemēram, divkārt saistītas sarakstos

11
00:00:35,890 --> 00:00:38,470
saskaņā ar kuru jums ir bultiņa
notiek abos virzienos, kas

12
00:00:38,470 --> 00:00:40,320
var palīdzēt ar konkrētiem efektivitāti.

13
00:00:40,320 --> 00:00:42,000
Bet tas atrisināja problēmu?

14
00:00:42,000 --> 00:00:43,500
Kāda problēma bija šo atrisināt?

15
00:00:43,500 --> 00:00:46,620
Kāpēc mēs rūpējamies pirmdien?

16
00:00:46,620 --> 00:00:49,820
Kāpēc, teorētiski, vai mēs rūpējamies pirmdien?

17
00:00:49,820 --> 00:00:50,630
Ko tas dara?

18
00:00:50,630 --> 00:00:51,950
>> Mērķauditorija: Mēs varam dinamiski mainīt to.

19
00:00:51,950 --> 00:00:53,740
>> SPEAKER 1: OK, lai mēs varētu
dinamiski mainīt to.

20
00:00:53,740 --> 00:00:54,710
Labi darīts jums abiem.

21
00:00:54,710 --> 00:00:57,560
Tātad jūs varat dinamiski mainīt šo
datu struktūra, bet masīva,

22
00:00:57,560 --> 00:01:00,760
Atsaukt, jums ir jāzina
priori, cik daudz vietas vēlaties

23
00:01:00,760 --> 00:01:03,870
un, ja jums ir nepieciešams mazliet vairāk
telpa, tu esi veida no luck.

24
00:01:03,870 --> 00:01:05,560
Jums ir izveidot pilnīgi jaunu klāstu.

25
00:01:05,560 --> 00:01:07,893
Jums ir pārvietot visas jūsu
dati no viena uz otru,

26
00:01:07,893 --> 00:01:10,600
beidzot atbrīvotu veco masīvs
ja jūs varat, un tad doties.

27
00:01:10,600 --> 00:01:13,891
Kas vienkārši jūtas ļoti dārgi un ļoti
neefektīva, un tas patiešām var būt.

28
00:01:13,891 --> 00:01:14,890
Bet tas vēl nav viss labi.

29
00:01:14,890 --> 00:01:18,180
Mēs maksājam par cenu, kas bija viens
no vairāk acīmredzamas cenām mums

30
00:01:18,180 --> 00:01:20,550
samaksāt, izmantojot saistīts sarakstu?

31
00:01:20,550 --> 00:01:22,825
>> Mērķauditorija: Mums ir jāizmanto
dubultā platība katram.

32
00:01:22,825 --> 00:01:25,200
SPEAKER 1: Jā, tāpēc mums ir nepieciešams
vismaz divreiz tik daudz vietas.

33
00:01:25,200 --> 00:01:27,700
Patiesībā, es sapratu, tas bildes
pat nedaudz maldinošs,

34
00:01:27,700 --> 00:01:32,200
jo par CS50 IDE ir daudz mūsdienu
datori, rādītājs vai adrese

35
00:01:32,200 --> 00:01:33,700
nav faktiski četri baiti.

36
00:01:33,700 --> 00:01:36,090
Tas ir ļoti bieži šiem
dienas astoņi baiti, kas

37
00:01:36,090 --> 00:01:38,530
ir apakšā visvairāk
taisnstūri tur patiesībā

38
00:01:38,530 --> 00:01:40,900
ir sava veida divreiz
liels, kā tas, ko es esmu sastādīts,

39
00:01:40,900 --> 00:01:44,409
kas nozīmē, ka jūs izmantojat trīs reizes
daudz vietas, kā mēs varētu būt citādi.

40
00:01:44,409 --> 00:01:46,700
Tagad tajā pašā laikā, mēs esam
joprojām runā baiti, vai ne?

41
00:01:46,700 --> 00:01:49,140
Mēs ne vienmēr runā
megabaiti vai gigabaiti,

42
00:01:49,140 --> 00:01:51,000
ja vien šie dati struktūras iegūt lielas.

43
00:01:51,000 --> 00:01:54,510
>> Un tāpēc šodien mēs sākam apsvērt
kā mēs varētu izpētīt datus

44
00:01:54,510 --> 00:01:57,310
efektīvāk, ja
Fakts, dati kļūst lielāka.

45
00:01:57,310 --> 00:02:00,360
Bet pamēģināsim canonicalize
darbības pirmie

46
00:02:00,360 --> 00:02:02,460
ka jūs varat darīt, par šiem
veida datu struktūras.

47
00:02:02,460 --> 00:02:04,790
Tātad kaut kā saistīts
sarakstu kopumā atbalsta

48
00:02:04,790 --> 00:02:07,514
operācijas, piemēram, dzēst,
ievietot, un meklēt.

49
00:02:07,514 --> 00:02:08,639
Un ko es ar to domā?

50
00:02:08,639 --> 00:02:11,222
Tas tikai nozīmē, ka parasti,
ja cilvēki izmanto saistītas sarakstu,

51
00:02:11,222 --> 00:02:14,287
viņi vai kāds cits ir īstenojusi
funkcijas, piemēram, dzēst, ievietot,

52
00:02:14,287 --> 00:02:16,120
un meklēt, lai jūs varētu
faktiski darīt kaut ko

53
00:02:16,120 --> 00:02:18,030
noderīgs ar datu struktūru.

54
00:02:18,030 --> 00:02:20,760
Tātad pieņemsim ātri apskatīt
pie kā mēs varētu īstenot

55
00:02:20,760 --> 00:02:24,530
daži kods saistītu sarakstu šādi.

56
00:02:24,530 --> 00:02:27,885
>> Tātad tas ir tikai daži C kods,
nav pat pabeigta programma

57
00:02:27,885 --> 00:02:29,260
ka es tiešām ātri saputo.

58
00:02:29,260 --> 00:02:32,300
Tas nav online izplatīšanā
kodu, jo tas nav reāli darboties.

59
00:02:32,300 --> 00:02:33,790
Bet paziņojums es tikko
ar komentāru teica:

60
00:02:33,790 --> 00:02:36,130
dot dot dot, tur ir kaut kas
tur, dot dot dot, kaut ko tur.

61
00:02:36,130 --> 00:02:38,410
Un pieņemsim tikai apskatīt
kādi sulīgs daļas ir.

62
00:02:38,410 --> 00:02:40,790
Tātad uz līnijas trīs,
atgādina, ka tas ir tagad

63
00:02:40,790 --> 00:02:45,960
mēs ierosinājām deklarējot mezglu pēdējo
laiks, viens no šiem taisnstūra objektu.

64
00:02:45,960 --> 00:02:48,790
Tas ir int, ka mēs saucam N,
bet mēs varētu to nosaukt kaut,

65
00:02:48,790 --> 00:02:51,920
un tad struct mezglā zvaigzne sauc nākamo.

66
00:02:51,920 --> 00:02:55,520
Un tikai, lai būtu skaidrs, ka otrais
line, on line seši, kas tas ir?

67
00:02:55,520 --> 00:02:57,930
Ko tas dara mums?

68
00:02:57,930 --> 00:03:01,044
Jo tas, protams, izskatās vairāk
mistisks nekā mūsu parastajiem mainīgajiem.

69
00:03:01,044 --> 00:03:02,740
>> Mērķauditorija: Tas padara to pāriet vienu.

70
00:03:02,740 --> 00:03:04,650
>> SPEAKER 1: Tas padara to pāriet vienu.

71
00:03:04,650 --> 00:03:08,580
Un precīzāk,
tas būs saglabāt adresi

72
00:03:08,580 --> 00:03:11,582
mezgla, kas ir domāts, lai būtu
semantiski blakus tai, vai ne?

73
00:03:11,582 --> 00:03:13,540
Tātad tas nav gatavojas
obligāti pārcelties neko.

74
00:03:13,540 --> 00:03:15,290
Tas ir tikai gatavojas
saglabātu vērtību,, kas ir

75
00:03:15,290 --> 00:03:17,170
būs adresi
dažu citu mezglu,

76
00:03:17,170 --> 00:03:20,810
un tas ir iemesls, kāpēc mēs esam teica struct
mezglā zvaigzne, zvaigzne apzīmē

77
00:03:20,810 --> 00:03:22,370
rādītājs vai adresi.

78
00:03:22,370 --> 00:03:26,390
Labi, tāpēc tagad, ja jūs pieņemt, ka mēs esam
šis N pieejams pie mums, un pieņemsim

79
00:03:26,390 --> 00:03:29,490
pieņemu, ka kāds cits ir
Iekļauj visu ķekars integers

80
00:03:29,490 --> 00:03:30,400
uz saistīts sarakstā.

81
00:03:30,400 --> 00:03:35,640
Un tas saistīts saraksts
norādīja uz ko kādā brīdī

82
00:03:35,640 --> 00:03:39,040
mainīgais sauc sarakstu, kas ir
pagājis šeit kā parametrs,

83
00:03:39,040 --> 00:03:43,120
Kā es varu iet par tiešsaistes
14. Īstenojot meklēšanu?

84
00:03:43,120 --> 00:03:45,990
Citiem vārdiem sakot, ja es esmu īstenošanai
funkcija, kuras mērķis dzīvē

85
00:03:45,990 --> 00:03:48,889
ir veikt int un tad
sākums saistīts saraksta

86
00:03:48,889 --> 00:03:50,430
ka ir pointers uz saistītā sarakstā.

87
00:03:50,430 --> 00:03:52,992
Tāpat kā pirmā, kas es domāju Dāvidu
bija mūsu brīvprātīgais pirmdien,

88
00:03:52,992 --> 00:03:54,700
viņš norādot
viss saistīts saraksts,

89
00:03:54,700 --> 00:03:57,820
tas ir tā, it kā mēs iet
Dāvids kā mūsu arguments šeit.

90
00:03:57,820 --> 00:03:59,990
Kā mēs iet par šķērso šo sarakstu?

91
00:03:59,990 --> 00:04:04,640
Nu, izrādās, ka, lai gan
norādes ir salīdzinoši jauns, tagad pie mums,

92
00:04:04,640 --> 00:04:07,010
mēs varam izdarīt salīdzinoši
vienkāršākā.

93
00:04:07,010 --> 00:04:09,500
>> Es iešu uz priekšu un
atzīt pagaidu mainīgo, kas

94
00:04:09,500 --> 00:04:12,364
pēc vienošanās ir tikai gatavojas
varētu saukt rādītājs, vai PTR,

95
00:04:12,364 --> 00:04:14,030
bet jūs varētu sauc to kaut ko vēlaties.

96
00:04:14,030 --> 00:04:16,470
Un es esmu gatavojas, lai sāktu
tā sākuma saraksta.

97
00:04:16,470 --> 00:04:20,050
Tātad jūs varat veida domā par to
kā man skolotāja citu dienu,

98
00:04:20,050 --> 00:04:23,580
veida norādot uz kādu
starp mūsu cilvēkiem, kā brīvprātīgajiem.

99
00:04:23,580 --> 00:04:26,470
Tāpēc es esmu pagaidu mainīgo, kas ir
tieši norādot uz to pašu

100
00:04:26,470 --> 00:04:31,390
ka mūsu nejauši nosaukts
brīvprātīgais Dāvids bija arī norādot.

101
00:04:31,390 --> 00:04:35,440
Tagad, kamēr rādītājs ir
nav null, jo atsaukums

102
00:04:35,440 --> 00:04:40,350
ka null ir dažas īpašas Sentinel vērtība
norobežo galu saraksta,

103
00:04:40,350 --> 00:04:44,280
Tāpēc, kamēr es neesmu norādot uz
zemes tāpat kā mūsu pēdējā brīvprātīgais

104
00:04:44,280 --> 00:04:47,190
bija, iesim uz priekšu
un darīt šādi.

105
00:04:47,190 --> 00:04:51,820
Ja pointer-- un tagad es veida gribu
darīt to, ko mēs darījām ar studentu

106
00:04:51,820 --> 00:04:57,410
structure-- ja rādītājs dot blakus
equals-- diezgan, ja rādītājs dot N vienāds

107
00:04:57,410 --> 00:05:02,290
vienāds mainīgo N, tad
Arguments, ka ir bijis pieņemts,

108
00:05:02,290 --> 00:05:05,370
tad es gribu iet uz priekšu
un teikt atgriezties taisnība.

109
00:05:05,370 --> 00:05:11,020
Atradu numuru N iekšpusē
viens no mezgliem mana saistīta sarakstā.

110
00:05:11,020 --> 00:05:13,500
Bet dot vairs
darbojas šajā kontekstā,

111
00:05:13,500 --> 00:05:17,260
jo rādītājs, PTR, ir
patiešām rādītājs, adrese,

112
00:05:17,260 --> 00:05:20,632
mēs faktiski var lieliski
izmantot beidzot gabals sintakses

113
00:05:20,632 --> 00:05:22,590
šāda veida padara
intuitīva sajūta un faktiski

114
00:05:22,590 --> 00:05:27,870
izmantojiet bultiņu šeit, kas nozīmē aiziet no
šī adrese uz skaitlim tur in.

115
00:05:27,870 --> 00:05:30,160
Tātad, tas ir ļoti līdzīgs
gars ar dot operatoram,

116
00:05:30,160 --> 00:05:33,860
bet tāpēc, ka rādītājs nav rādītājs
un nav faktiskā struct pati,

117
00:05:33,860 --> 00:05:35,380
mēs tikai izmantot bultiņu.

118
00:05:35,380 --> 00:05:40,620
>> Tātad, ja pašreizējais mezglā ka es, tad
pagaidu mainīgo, esmu norādot

119
00:05:40,620 --> 00:05:43,060
nav N, ko es gribu darīt?

120
00:05:43,060 --> 00:05:45,910
Nu, ar saviem brīvprātīgajiem
ka mums bija šeit citu dienu,

121
00:05:45,910 --> 00:05:49,710
ja mans pirmais cilvēks nav viens es
gribu, un varbūt otrais cilvēks nav

122
00:05:49,710 --> 00:05:52,660
vienu es gribu, un trešais, es
ir nepieciešams, lai saglabātu fiziski pārvietojas.

123
00:05:52,660 --> 00:05:54,690
Tāpat kā es varu soli pa sarakstu?

124
00:05:54,690 --> 00:05:57,470
Kad mums bija masīvs, jums
vienkārši darīja tāpat I plus plus.

125
00:05:57,470 --> 00:06:03,660
Bet šajā gadījumā, pietiek
do rādītāju, saņem, rādītāju, blakus.

126
00:06:03,660 --> 00:06:07,580
Citiem vārdiem, nākamais lauks
ir tāpat kā visas kreisā rokās

127
00:06:07,580 --> 00:06:10,880
ka mūsu cilvēku brīvprātīgie pirmdien
bija izmantojot norādīt uz kādu citu mezglu.

128
00:06:10,880 --> 00:06:12,890
Tie bija viņu nākamie kaimiņi.

129
00:06:12,890 --> 00:06:17,060
>> Tātad, ja es gribu, lai soli pa šo sarakstu,
Es nevaru vienkārši man plus plus vairs,

130
00:06:17,060 --> 00:06:20,120
Man gan jāsaka
Es, rādītājs, kas notiek

131
00:06:20,120 --> 00:06:24,650
uz vienāda neatkarīgi nākamais lauks ir,
nākamais lauks, nākamais lauks ir,

132
00:06:24,650 --> 00:06:28,350
pēc visām šīm kreisās rokas
ka mums bija uz skatuves norādot

133
00:06:28,350 --> 00:06:30,000
dažiem turpmākajiem vērtībām.

134
00:06:30,000 --> 00:06:32,590
Un, ja man cauri
ka viss atkārtojuma,

135
00:06:32,590 --> 00:06:39,330
un, visbeidzot, es hit null, kam nav
konstatēts N vēl, es vienkārši atgriezties viltus.

136
00:06:39,330 --> 00:06:44,100
Tātad vēlreiz, viss, ko mēs darām šeit,
kā vienu attēlu pirms brīža,

137
00:06:44,100 --> 00:06:47,840
sāk norādot ne
sākot no saraksta iespējams.

138
00:06:47,840 --> 00:06:50,970
Un tad es varētu pārbaudīt, ir vērtība
Es meklēju vienāds ar deviņiem?

139
00:06:50,970 --> 00:06:52,650
Ja tā, tad es atgrieztos taisnība, un es esmu darīts.

140
00:06:52,650 --> 00:06:56,450
Ja nē, es atjaunināt manu roku,
AKA rādītājs, norādīt

141
00:06:56,450 --> 00:06:59,540
nākamajā ARROW atrašanās vietu, un
Tad Nākošais atrašanās vietu,

142
00:06:59,540 --> 00:07:00,480
un nākamo.

143
00:07:00,480 --> 00:07:03,770
Es esmu vienkārši ejot pa šo masīvu.

144
00:07:03,770 --> 00:07:06,010
>> Tātad vēlreiz, kurš rūpējas?

145
00:07:06,010 --> 00:07:07,861
Tāpat kā to, kas ir šī sastāvdaļa atrast?

146
00:07:07,861 --> 00:07:10,360
Nu, atgādināt, ka mēs ieviesām
jēdziens kaudze, kas

147
00:07:10,360 --> 00:07:15,400
ir abstrakts datu tips, ciktāl tas ir
nav C lieta, tas nav CS50 lieta,

148
00:07:15,400 --> 00:07:19,430
tas ir abstrakts ideja, šī ideja
kraušanas lietas virsū viens otram

149
00:07:19,430 --> 00:07:21,820
ka var īstenot
ķekarus dažādos veidos.

150
00:07:21,820 --> 00:07:25,600
Un viens no veidiem, mēs ierosinājām, bija ar
masīvs, vai ar saistīta sarakstu.

151
00:07:25,600 --> 00:07:29,570
Un izrādās, ka kanoniski A
kaudze atbalsta vismaz divas operācijas.

152
00:07:29,570 --> 00:07:32,320
Un buzz vārdi ir push, lai
push kaut uz kaudze,

153
00:07:32,320 --> 00:07:34,770
piemēram, jaunu paplāti
ēdamzāle, vai pop,

154
00:07:34,770 --> 00:07:39,000
kas nozīmē noņemt augšējais
paplāte no skursteņa ar ēdamistabas

155
00:07:39,000 --> 00:07:41,500
halle, un tad varbūt daži
citas darbības, kā arī.

156
00:07:41,500 --> 00:07:45,770
Tātad, kā mēs varbūt definētu struktūru
ka mēs tagad zvanot kaudze?

157
00:07:45,770 --> 00:07:50,020
>> Nu, mums ir visi vajadzīgie
sintakse mūsu rīcībā C. es saku,

158
00:07:50,020 --> 00:07:53,830
man tipa definīciju
struct iekšpusē kaudze,

159
00:07:53,830 --> 00:07:58,030
Es esmu gatavojas teikt, ir masīvs, kādas
viss ķekars numuriem, un pēc tam izmēra.

160
00:07:58,030 --> 00:08:00,930
Tātad citiem vārdiem sakot, ja es gribu
lai īstenotu šo kodu,

161
00:08:00,930 --> 00:08:03,830
ļaujiet man iet un tikai veida
izdarīt to, kas tas ir saprotams.

162
00:08:03,830 --> 00:08:06,317
Tātad tas ir saprotams, dod man
struktūra, kas ir ieguvuši masīvu,

163
00:08:06,317 --> 00:08:09,400
un es nezinu, kas jauda ir,
tas acīmredzot daži konstante, kas es esmu

164
00:08:09,400 --> 00:08:10,858
noteikts citur, un tas ir jauki.

165
00:08:10,858 --> 00:08:15,260
Bet pieņemsim, ka tas ir tikai viens,
divi, trīs, četri, pieci.

166
00:08:15,260 --> 00:08:16,700
Tātad jauda ir 5.

167
00:08:16,700 --> 00:08:21,730
Šis elements iekšpusē manu
struktūra sauks numurus.

168
00:08:21,730 --> 00:08:24,020
Un tad man tas ir nepieciešams
cits mainīgais acīmredzot

169
00:08:24,020 --> 00:08:27,814
sauc lielums ka sākotnēji es eju
noteikt, tiek inicializēts ar nulli.

170
00:08:27,814 --> 00:08:29,730
Ja tur nekas
kaudze, izmērs ir nulle,

171
00:08:29,730 --> 00:08:31,420
un tas ir atkritumu vērtības numuriem.

172
00:08:31,420 --> 00:08:33,450
Man nav ne jausmas, kas tur tikai pagaidām.

173
00:08:33,450 --> 00:08:36,059
>> Tātad, ja es gribu, lai push
kaut uz kaudze,

174
00:08:36,059 --> 00:08:40,780
domāju, ka es aicinu funkciju push, un
Es saku push 50, piemēram, numuru 50,

175
00:08:40,780 --> 00:08:44,090
kur jūs ierosināt
Es izdarīt to šajā masīvā?

176
00:08:44,090 --> 00:08:47,124
Ir piecas dažādas iespējamās atbildes.

177
00:08:47,124 --> 00:08:48,790
Ja jūs vēlaties, lai push numuru 50?

178
00:08:48,790 --> 00:08:51,899
Ja mērķis šeit, atkal, zvaniet
funkcija push, iet uz argumentu

179
00:08:51,899 --> 00:08:52,940
50, kur es varu likt to?

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

181
00:08:55,680 --> 00:08:59,052
Pieci possible-- 20% iespēja
guessing pareizi.

182
00:08:59,052 --> 00:08:59,896
Jā?

183
00:08:59,896 --> 00:09:00,740
>> Mērķauditorija: Far labi.

184
00:09:00,740 --> 00:09:01,990
>> SPEAKER 1: Far labi.

185
00:09:01,990 --> 00:09:08,359
Tagad ir 25% iespēja
guessing pareizi.

186
00:09:08,359 --> 00:09:09,650
Tā, ka faktiski nebūtu labi.

187
00:09:09,650 --> 00:09:12,770
Pēc vienošanās, es saku ar masīvu,
mēs parasti sākas no kreisās

188
00:09:12,770 --> 00:09:14,519
bet mēs, protams, var
sākas labi.

189
00:09:14,519 --> 00:09:17,478
Tātad spoileris šeit būtu es esmu
iespējams, gatavojas izdarīt to pa kreisi,

190
00:09:17,478 --> 00:09:20,060
tāpat kā parastā masīvs kur
Man sāk iet no kreisās uz labo.

191
00:09:20,060 --> 00:09:21,780
Bet, ja jūs varat uzsist
aritmētiskais, naudas sodu.

192
00:09:21,780 --> 00:09:23,060
Tas vienkārši nav parasto.

193
00:09:23,060 --> 00:09:24,880
Labi, man ir nepieciešams veikt vienu
vairāk maiņa though.

194
00:09:24,880 --> 00:09:27,710
Tagad, ka es esmu kaut ko uzstāja
uz steku, ko tālāk?

195
00:09:27,710 --> 00:09:29,400
>> Labi, man ir pieauguma lielumu.

196
00:09:29,400 --> 00:09:32,600
Tāpēc ļaujiet man iet uz priekšu un vienkārši
atjaunināt tas, kas bija nulle.

197
00:09:32,600 --> 00:09:35,950
Un tā vietā, tagad, es eju
likt vērtības vienā.

198
00:09:35,950 --> 00:09:39,460
Un tagad domāju, ka es push citu
numurs uz steku, piemēram, 51.

199
00:09:39,460 --> 00:09:42,680
Nu, man ir padarīt vēl viens
izmaiņas, kas ir līdz ar izmēru diviem.

200
00:09:42,680 --> 00:09:46,100
Un tad es domāju, ka push vēl viens
numurs uz kā 61 kaudze,

201
00:09:46,100 --> 00:09:52,530
tagad man ir nepieciešams, lai atjauninātu izmēru vēl viens
laiks, un iegūt vērtību 3, lielums.

202
00:09:52,530 --> 00:09:54,690
Un tagad domāju, ka es aicinu pop.

203
00:09:54,690 --> 00:09:57,250
Tagad pop, pēc vienošanās,
neņem argumentu.

204
00:09:57,250 --> 00:10:00,430
Ar steku, viss
punkts paplātes metafora

205
00:10:00,430 --> 00:10:03,450
ir tas, ka jums nav rīcības brīvības
iet saņemt šo paplāti, visu jūs varat darīt

206
00:10:03,450 --> 00:10:06,330
ir pop augšējais vienu no
kaudze, tikai tāpēc, ka.

207
00:10:06,330 --> 00:10:08,010
Tas, ko šis datu struktūra dara.

208
00:10:08,010 --> 00:10:12,250
>> Tātad, šī loģika, ja es
saka pop, kas nāk nost?

209
00:10:12,250 --> 00:10:13,080
Tātad 61.

210
00:10:13,080 --> 00:10:15,402
Tātad, kas īsti ir dators
darīsim atmiņā?

211
00:10:15,402 --> 00:10:16,610
Kāda mans kods ir jādara?

212
00:10:16,610 --> 00:10:20,330
Ko jūs varētu ieteikt
mēs mainīt uz ekrāna?

213
00:10:20,330 --> 00:10:23,410
Kas būtu jāmaina?

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

215
00:10:24,960 --> 00:10:26,334
Tātad, mēs atbrīvoties no 61.

216
00:10:26,334 --> 00:10:27,500
Tāpēc es varu noteikti darīt.

217
00:10:27,500 --> 00:10:28,640
Un es varu atbrīvoties no 61.

218
00:10:28,640 --> 00:10:30,980
Un tad kāds cits
izmaiņas nepieciešams notikt?

219
00:10:30,980 --> 00:10:33,160
Izmērs, iespējams, ir doties atpakaļ uz diviem.

220
00:10:33,160 --> 00:10:34,210
Un tā tas ir jauki.

221
00:10:34,210 --> 00:10:36,690
Bet pagaidiet minūti, izmērs
pirms brīža bija trīs.

222
00:10:36,690 --> 00:10:38,240
Pieņemsim tikai darīt ātri veselība pārbaudītu.

223
00:10:38,240 --> 00:10:41,810
Kā mēs zinām, ka mēs
vēlējās atbrīvoties no 61?

224
00:10:41,810 --> 00:10:42,760
Jo mēs esam popping.

225
00:10:42,760 --> 00:10:46,450
Un tāpēc man ir šī otrā īpašuma lielumu.

226
00:10:46,450 --> 00:10:48,470
>> Pagaidiet minūti, es esmu
domāšana atpakaļ uz nedēļu divām

227
00:10:48,470 --> 00:10:51,660
kad mēs sākām runāt par
bloki, kur tas bija vieta nulle,

228
00:10:51,660 --> 00:10:55,920
tas bija vieta viens, tas bija vieta
divi, tas ir vieta trīs, četri,

229
00:10:55,920 --> 00:10:58,460
izskatās, ka
Saistība starp izmērā

230
00:10:58,460 --> 00:11:02,780
un elements, kas es gribu noņemt
no masīva, šķiet, tieši tas, ko?

231
00:11:02,780 --> 00:11:05,120
Size mīnus viens.

232
00:11:05,120 --> 00:11:07,786
Un tā tas ir, kā par cilvēkiem
mēs zinām, 61 ir pirmajā vietā.

233
00:11:07,786 --> 00:11:09,160
Kā ir dators gatavojas zināt?

234
00:11:09,160 --> 00:11:11,701
Kad jūsu kods, kur jūs, iespējams,
gribu darīt izmērs mīnus viens,

235
00:11:11,701 --> 00:11:14,950
tā trīs mīnus viens ir divi, un ka
nozīmē, ka mēs gribam, lai atbrīvotos no 61.

236
00:11:14,950 --> 00:11:18,000
Un tad mēs varam patiesi atjaunināt
tā šī izmēra lielums tagad

237
00:11:18,000 --> 00:11:20,300
iet no trim līdz tikai divi.

238
00:11:20,300 --> 00:11:24,520
Un tikai, lai būtu pedantiska, es eju
ierosināt, ka es esmu darījis, vai ne?

239
00:11:24,520 --> 00:11:27,660
Jūs ierosināja intuitīvi
pareizi man vajadzētu atbrīvoties no 61.

240
00:11:27,660 --> 00:11:30,700
Bet es neesmu veida
kārtot gotten atbrīvoties no 61?

241
00:11:30,700 --> 00:11:33,790
Esmu aizmirsis efektīvi
ka tas ir faktiski tur.

242
00:11:33,790 --> 00:11:37,680
Un domāju, ka atpakaļ uz PSET4, ja esat izlasīt
raksts par kriminālistikas, PDF

243
00:11:37,680 --> 00:11:40,780
ka mums bija jūs guys lasīt, vai jūs
lasīt šonedēļ PSET4.

244
00:11:40,780 --> 00:11:44,300
Atgādināt, ka tas ir faktiski piederīgs
visa ideja par datoru kriminālistikas.

245
00:11:44,300 --> 00:11:47,820
Kas dators parasti dara, ir
tā vienkārši aizmirst, kur kaut kas ir,

246
00:11:47,820 --> 00:11:51,300
bet tas nav iet un, piemēram,
mēģināt saskrāpēt to, vai ignorēt

247
00:11:51,300 --> 00:11:54,560
šie gabaliņi ar nullēm un uzņēmumiem
vai kādu citu izlases modelis

248
00:11:54,560 --> 00:11:56,690
Ja vien jūs pats to darīt apzināti.

249
00:11:56,690 --> 00:11:58,930
Tātad jūsu intuīcija bija
labi, pieņemsim atbrīvoties no 61.

250
00:11:58,930 --> 00:12:00,650
Bet patiesībā, mums nav apnikt.

251
00:12:00,650 --> 00:12:04,040
Mums ir nepieciešams, lai aizmirst, ka
tas ir tur, mainot savu izmēru.

252
00:12:04,040 --> 00:12:05,662
>> Tagad tur ir problēma ar šo kaudze.

253
00:12:05,662 --> 00:12:07,620
Ja es glabāt stumšanas lietas
uz steku, kas ir

254
00:12:07,620 --> 00:12:11,167
acīmredzot notiks
tikai dažus mirkļus laikā?

255
00:12:11,167 --> 00:12:12,500
Mēs ejam, lai pietrūkt vietas.

256
00:12:12,500 --> 00:12:13,580
Un ko mēs darām?

257
00:12:13,580 --> 00:12:14,680
Mēs esam veida ieskrūvē.

258
00:12:14,680 --> 00:12:19,000
Šis īstenošana neļauj
mums mainīt masīvs, jo, izmantojot

259
00:12:19,000 --> 00:12:21,240
Tas sintakse, ja jums
domāju, ka atpakaļ uz nedēļu divām,

260
00:12:21,240 --> 00:12:23,520
kad jūs esat deklarēta
lielums masīva,

261
00:12:23,520 --> 00:12:26,780
mēs neesam redzējuši mehānismu vēl kur
Jūs varat mainīt izmēru masīva.

262
00:12:26,780 --> 00:12:29,020
Un tiešām C nav šo funkciju.

263
00:12:29,020 --> 00:12:32,524
Ja jūs sakāt man pieci
Nths, viņiem piezvanīt numurus,

264
00:12:32,524 --> 00:12:33,940
tas ir viss, jūs gatavojas, lai saņemtu to.

265
00:12:33,940 --> 00:12:38,790
Tāpēc mēs tagad darīt, jo pirmdien, ir
spēja izteikt risinājumu

266
00:12:38,790 --> 00:12:42,480
lai gan, mums ir nepieciešams, lai kniebiens
definīcija mūsu kaudze

267
00:12:42,480 --> 00:12:46,840
ne būt daži iekodēts masīvs,
bet tikai, lai uzglabātu adresi.

268
00:12:46,840 --> 00:12:47,890
>> Tagad, kāpēc tas ir?

269
00:12:47,890 --> 00:12:51,690
Tagad mums vienkārši ir, lai būtu ērti ar
tas, ka tad, kad mana programma darbojas,

270
00:12:51,690 --> 00:12:53,730
Es esmu domājams gatavojas
ir jālūdz cilvēkresursus,

271
00:12:53,730 --> 00:12:55,110
cik skaitļi jūs vēlaties saglabāt?

272
00:12:55,110 --> 00:12:56,776
Tātad ievade ir jānāk no kaut.

273
00:12:56,776 --> 00:12:59,140
Bet tad, kad es zinu, ka
numurs, tad es varu tikai

274
00:12:59,140 --> 00:13:02,470
izmantot to, kas darbojas, lai sniegtu
man rieciens atmiņas?

275
00:13:02,470 --> 00:13:03,580
Es varu izmantot malloc.

276
00:13:03,580 --> 00:13:06,710
Un es varu teikt jebkuru skaitu
bytes Es gribu atpakaļ uz šiem Nths.

277
00:13:06,710 --> 00:13:10,910
Un viss, kas man ir, lai glabāt numuriem
mainīgs šeit iekšā šajā struct

278
00:13:10,910 --> 00:13:13,480
vajadzētu būt, ko?

279
00:13:13,480 --> 00:13:18,440
Kas patiesībā tērēta
skaitļi šajā scenārijā?

280
00:13:18,440 --> 00:13:21,300
Jā, pointers uz pirmo
baitu šī rieciens atmiņas,

281
00:13:21,300 --> 00:13:24,940
vai precīzāk, adrese
no pirmo no minētajiem bytes.

282
00:13:24,940 --> 00:13:27,300
Nav svarīgi, vai tas ir viens
baitu vai viens miljards baitu,

283
00:13:27,300 --> 00:13:28,890
Man vienkārši vajag rūpēties par pirmo.

284
00:13:28,890 --> 00:13:31,530
Jo tas, ko malloc garantijas un
Mani operētājsistēmas garantijas,

285
00:13:31,530 --> 00:13:34,170
ir tas, ka rieciens atmiņas I
iegūt, tas būs blakus.

286
00:13:34,170 --> 00:13:35,378
Tur nebūs nepilnības.

287
00:13:35,378 --> 00:13:38,576
Tātad, ja es esmu lūgusi 50
baiti vai 1000 baiti,

288
00:13:38,576 --> 00:13:40,450
viņi visi būs
atpakaļ atpakaļ atpakaļ.

289
00:13:40,450 --> 00:13:44,500
Un tik ilgi, cik es atceros, cik liels, cik
daudz es lūdza, visi man ir nepieciešams zināt

290
00:13:44,500 --> 00:13:46,230
ir pirmais šāda adrese.

291
00:13:46,230 --> 00:13:48,660
>> Tāpēc tagad mums ir iespēja kodu.

292
00:13:48,660 --> 00:13:51,280
Kaut gan, tas notiek, lai mūs
vairāk laika, lai rakstītu šo augšu,

293
00:13:51,280 --> 00:13:55,900
Tagad mēs varētu pārdalīt šo atmiņu,
vienkārši uzglabātu citu adresi tur

294
00:13:55,900 --> 00:13:59,060
ja mēs gribam lielāka vai pat
mazāku rieciens atmiņas.

295
00:13:59,060 --> 00:14:00,170
Tātad šeit, lai tirdzniecības off.

296
00:14:00,170 --> 00:14:01,360
Tagad mēs dinamismu.

297
00:14:01,360 --> 00:14:03,350
Mums joprojām ir
contiguousness Es esmu apgalvojot.

298
00:14:03,350 --> 00:14:05,881
Jo malloc dos mums
blakusesoši rieciens atmiņas.

299
00:14:05,881 --> 00:14:08,630
Bet tas būs sāpes
kakls mums, programmētājs,

300
00:14:08,630 --> 00:14:09,770
faktiski kods up.

301
00:14:09,770 --> 00:14:10,730
Tas ir tikai vairāk darba.

302
00:14:10,730 --> 00:14:13,930
Mums ir nepieciešams kods līdzīgs, ko es biju
banging ārā tikai pirms brīža.

303
00:14:13,930 --> 00:14:16,120
Ļoti veicams, bet tas padara sarežģītāku.

304
00:14:16,120 --> 00:14:19,520
Un tā attīstītājs laiks, programmētājs
laiks ir vēl viens resurss

305
00:14:19,520 --> 00:14:22,520
ka mums, iespējams, vajadzēs tērēt
kādu laiku, lai iegūtu jaunas funkcijas.

306
00:14:22,520 --> 00:14:24,020
Un tad, protams, ir rinda.

307
00:14:24,020 --> 00:14:26,227
Mēs ne iedziļināties šajā
viens daudz sīkāk.

308
00:14:26,227 --> 00:14:27,560
Bet tas ir ļoti līdzīgs garā.

309
00:14:27,560 --> 00:14:31,220
Es varētu ieviest rindā, un
tās atbilst operācijas,

310
00:14:31,220 --> 00:14:35,660
Enqueue vai dequeue, piemēram, pievienot vai noņemt,
tas ir tikai mīļotājs veids, kā pateikt to,

311
00:14:35,660 --> 00:14:38,100
Enqueue vai dequeue šādi.

312
00:14:38,100 --> 00:14:41,170
Es varu tikai dot sev struct
ka atkal ir vairāki ir masīvs,

313
00:14:41,170 --> 00:14:44,000
kas atkal ir izmēru,
bet kāpēc man tagad vajag

314
00:14:44,000 --> 00:14:46,940
sekot priekšā rindā?

315
00:14:46,940 --> 00:14:50,630
Man nav nepieciešams zināt
priekšējo mana kaudze.

316
00:14:50,630 --> 00:14:53,570
Nu, ja es atkal priekšlikums
queue-- pieņemsim tikai grūti

317
00:14:53,570 --> 00:14:57,870
kodēt to kā, kam, piemēram, pieci
skaitļu šeit potenciāli.

318
00:14:57,870 --> 00:15:00,940
Tāpēc tas ir nulle, viens, divi, trīs, četri.

319
00:15:00,940 --> 00:15:03,430
Tas būs
sauktie skaitļi vēlreiz.

320
00:15:03,430 --> 00:15:06,940
Un tas tiks saukts izmērs.

321
00:15:06,940 --> 00:15:10,056
>> Kāpēc tas nav pietiekami,
lai ir tikai izmēru?

322
00:15:10,056 --> 00:15:11,680
Nu, pieņemsim virzīt tos pašus numurus.

323
00:15:11,680 --> 00:15:14,220
Tāpēc es pushed-- es enqueued vai stumšanai.

324
00:15:14,220 --> 00:15:20,150
Tagad es ņemšu ierindod 50, un pēc tam
51, un pēc tam 61, un dot dot dot.

325
00:15:20,150 --> 00:15:21,070
Tātad tas ir Enqueue.

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

327
00:15:23,176 --> 00:15:25,050
Un tas izskatās identiski
uz kaudze līdz šim,

328
00:15:25,050 --> 00:15:27,190
izņemot man ir nepieciešams veikt vienu maiņu.

329
00:15:27,190 --> 00:15:33,680
Man vajag, lai atjauninātu šo lielumu, tāpēc es dodos
no nulles līdz vienam līdz diviem līdz trīs tagad.

330
00:15:33,680 --> 00:15:35,760
Kā es varu dequeue?

331
00:15:35,760 --> 00:15:36,890
Kas notiek ar dequeue?

332
00:15:36,890 --> 00:15:41,950
Kam būtu jānāk pie šī saraksta pirmais
ja tas ir līnija pie Apple Store?

333
00:15:41,950 --> 00:15:42,780
Tātad 50.

334
00:15:42,780 --> 00:15:44,700
Tātad, tas ir sava veida sarežģītāk šoreiz.

335
00:15:44,700 --> 00:15:47,880
Tā kā pēdējo reizi tas bija super
viegli vienkārši darīt izmērs mīnus viens,

336
00:15:47,880 --> 00:15:51,440
Man uz beigām mana masīva efektīvi
ja šie skaitļi ir, tas noņem 61.

337
00:15:51,440 --> 00:15:52,920
Bet es negribu, lai novērstu 61.

338
00:15:52,920 --> 00:15:55,030
Es gribu, lai 50, kurš
bija tur at 5:00

339
00:15:55,030 --> 00:15:56,790
rindā, lai
Jaunais iPhone vai plauktiņš.

340
00:15:56,790 --> 00:16:01,200
Un tāpēc, lai atbrīvotos no 50, es
nevar vienkārši izdarīt, vai ne?

341
00:16:01,200 --> 00:16:02,547
Es varu izsvītrot 50.

342
00:16:02,547 --> 00:16:04,380
Bet mēs tikko teica, ka mums
nav jābūt tik Anal

343
00:16:04,380 --> 00:16:06,330
kā lai nesaskrāpētu ārā vai paslēptu datus.

344
00:16:06,330 --> 00:16:08,090
Mēs varam vienkārši aizmirst, kur tas ir.

345
00:16:08,090 --> 00:16:12,330
>> Bet, ja es varu mainīt savu izmēru tagad
divi, tas ir pietiekama informācija

346
00:16:12,330 --> 00:16:15,711
zināt, kas notiek manā rindā?

347
00:16:15,711 --> 00:16:16,680
Ne īsti.

348
00:16:16,680 --> 00:16:19,830
Tāpat kā mans izmērs ir divi, bet
ja nav rinda sākas,

349
00:16:19,830 --> 00:16:22,980
it īpaši, ja man vēl ir
šie paši skaitļi atmiņā.

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

351
00:16:24,260 --> 00:16:27,090
Tāpēc man ir nepieciešams atcerēties
tagad, kad priekšā ir.

352
00:16:27,090 --> 00:16:29,630
Un tā kā es ierosināju up
tur, mēs esam vienkārši sauc

353
00:16:29,630 --> 00:16:33,729
N priekšā, kuru sākotnējais
vērtība būtu bijis, ko?

354
00:16:33,729 --> 00:16:35,270
Zero, tikai sākums saraksta.

355
00:16:35,270 --> 00:16:40,876
Bet tagad papildus decrementing
lielums, mēs vienkārši pieauguma priekšā.

356
00:16:40,876 --> 00:16:42,000
Tagad šeit ir vēl viena problēma.

357
00:16:42,000 --> 00:16:43,030
Tātad, kad es turpinu iet.

358
00:16:43,030 --> 00:16:47,520
Domāt, tas ir skaitlis no
piemēram, 121, 124, un pēc tam, Nolāpīts,

359
00:16:47,520 --> 00:16:48,610
Es esmu no kosmosa.

360
00:16:48,610 --> 00:16:50,390
Bet pagaidiet minūti, es neesmu.

361
00:16:50,390 --> 00:16:55,630
Tātad šajā brīdī stāsts,
domāt, ka izmērs ir viens, divi,

362
00:16:55,630 --> 00:17:00,370
trīs, četri, tā domāt, ka
izmērs ir četri, priekšējā ir viens,

363
00:17:00,370 --> 00:17:01,621
tā 51 atrodas priekšpusē.

364
00:17:01,621 --> 00:17:04,329
Es gribu, lai citu numuru šeit,
bet, dammit, es esmu no kosmosa.

365
00:17:04,329 --> 00:17:06,710
Bet es neesmu īsti, vai ne?

366
00:17:06,710 --> 00:17:11,192
Kur es varētu likt kādu
papildu vērtību, piemēram, 171?

367
00:17:11,192 --> 00:17:13,400
Jā, es varētu tikai veida
atgriezties tur, labi?

368
00:17:13,400 --> 00:17:18,161
Un tad izsvītrot no 50, vai
tikai pārrakstīt ar 171.

369
00:17:18,161 --> 00:17:20,410
Un, ja jūs esat jautājums, kāpēc
Mūsu numuri dabūja tik nejauši,

370
00:17:20,410 --> 00:17:24,150
tie ir parasti ņem datoru
zinātņu kursus Hārvardas pēc CS50.

371
00:17:24,150 --> 00:17:27,510
Bet tas bija labs optimizācija,
jo tagad es neesmu izšķērdēt telpā.

372
00:17:27,510 --> 00:17:30,750
Man joprojām ir jāatceras
cik liela šī lieta ir kopā.

373
00:17:30,750 --> 00:17:31,500
Tas ir pieci kopā.

374
00:17:31,500 --> 00:17:33,375
Jo es negribu
sākt pārrakstot 51.

375
00:17:33,375 --> 00:17:36,260
Tāpēc tagad es esmu vēl no vietas,
tā pati problēma kā iepriekš.

376
00:17:36,260 --> 00:17:39,140
Bet jūs varat redzēt, kā tagad
savu kodu, jūs, iespējams,

377
00:17:39,140 --> 00:17:41,910
ir uzrakstīt mazliet vairāk
sarežģītība, lai tas notiktu.

378
00:17:41,910 --> 00:17:44,510
Un patiesībā, ko operators
C droši vien ļauj

379
00:17:44,510 --> 00:17:48,110
jūs maģiski to izdarītu riņķveida?

380
00:17:48,110 --> 00:17:50,160
Yeah Modulo operators,
procentuālais zīme.

381
00:17:50,160 --> 00:17:53,160
Tātad, kas ir sava veida atdzist apmēram rindā,
pat ja mēs turpinām zīmēšanas bloki

382
00:17:53,160 --> 00:17:56,520
kā šajās piemēram taisnām līnijām, ja jums
veida domāt par to, kā izliecas

383
00:17:56,520 --> 00:18:00,341
apkārt kā apli, tad vienkārši
intuitīvi tā veida darbojas garīgi

384
00:18:00,341 --> 00:18:01,590
Es domāju, ka nedaudz vairāk tīri.

385
00:18:01,590 --> 00:18:05,190
Jums joprojām būs jāīsteno
ka garīgā modelis kodu.

386
00:18:05,190 --> 00:18:07,550
Tātad nav tik grūti,
galu galā, lai īstenotu,

387
00:18:07,550 --> 00:18:12,430
bet mēs joprojām zaudēt size-- drīzāk,
Spēja mainīt, ja vien mēs to izdarītu.

388
00:18:12,430 --> 00:18:15,310
>> Mums ir atbrīvoties no masīva, mēs
aizstāt ar vienu rādītāju,

389
00:18:15,310 --> 00:18:20,010
un tad kaut kur manā kodu Man
zvanu, kādu funkciju, lai faktiski izveidot

390
00:18:20,010 --> 00:18:23,720
masīvs sauktie skaitļi?

391
00:18:23,720 --> 00:18:26,190
Malloc, vai kādu līdzīgu
funkcija, tieši tā.

392
00:18:26,190 --> 00:18:30,481
Visus jautājumus par skursteņi vai rindas.

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

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

395
00:18:33,657 --> 00:18:34,240
Labs jautājums.

396
00:18:34,240 --> 00:18:35,830
Ko Modulo jūs izmantojat šeit.

397
00:18:35,830 --> 00:18:38,520
Tātad kopumā, ja izmanto
mod, jūs varētu darīt to

398
00:18:38,520 --> 00:18:40,620
ar izmēru no
Visa datu struktūra.

399
00:18:40,620 --> 00:18:44,120
Tātad kaut kā pieci vai jaudu, ja
tas ir pastāvīgs, iespējams, ir iesaistīti.

400
00:18:44,120 --> 00:18:47,100
Bet tikai darot modulo pieci
iespējams, nav pietiekams,

401
00:18:47,100 --> 00:18:51,380
jo mums ir jāzina darīt mēs
aptīšanas šeit vai šeit vai šeit.

402
00:18:51,380 --> 00:18:54,160
Tātad jūs, iespējams, arī
gatavojas vēlaties, lai iesaistītu

403
00:18:54,160 --> 00:18:57,220
lielums lieta, vai
priekšējā mainīga, kā arī.

404
00:18:57,220 --> 00:19:00,140
Tātad, tas ir tikai šo salīdzinoši
vienkārša aritmētika izteiksme,

405
00:19:00,140 --> 00:19:02,000
bet Modulo būs galvenā sastāvdaļa.

406
00:19:02,000 --> 00:19:03,330
>> Tātad īsfilma, ja Jums gribas.

407
00:19:03,330 --> 00:19:05,780
Animācijas, ka daži
folks at citā augstskolā

408
00:19:05,780 --> 00:19:08,060
salikt kopā, ka mēs esam
pielāgotas šajā diskusijā.

409
00:19:08,060 --> 00:19:12,630
Tas ietver Jack apgūstot
fakti par rindām un stats.

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

411
00:19:19,010 --> 00:19:21,890
>> FILM: Reiz,
tur bija puisis vārdā Džeks.

412
00:19:21,890 --> 00:19:25,330
Kad tas nāca padarīt draugiem,
Jack nebija iemaņa.

413
00:19:25,330 --> 00:19:28,220
Tātad Jack gāja runāt ar
populārākais puisis viņš zināja.

414
00:19:28,220 --> 00:19:30,920
Viņš devās uz Lū un jautāja, ko man darīt?

415
00:19:30,920 --> 00:19:33,400
Lou redzēja, ka viņa draugs
bija tiešām noskumuši.

416
00:19:33,400 --> 00:19:36,050
Nu, viņš sāka, vienkārši
skatīties, kā jūs dressed.

417
00:19:36,050 --> 00:19:38,680
Vai nav jums ir kādi drēbes
ar atšķirīgu izskatu?

418
00:19:38,680 --> 00:19:39,660
Jā, teica Jack.

419
00:19:39,660 --> 00:19:40,840
Nudien darīt.

420
00:19:40,840 --> 00:19:43,320
Nāciet uz manu māju un
Es jums parādīs tos jums.

421
00:19:43,320 --> 00:19:44,550
Tāpēc viņi aizgāja uz Jack s.

422
00:19:44,550 --> 00:19:47,520
Un Jack parādīja Lou lodziņu
kur viņš tur visus savus kreklus,

423
00:19:47,520 --> 00:19:49,260
un viņa bikses, un viņa zeķes.

424
00:19:49,260 --> 00:19:52,290
Lū teica, es redzu, jums ir
visi jūsu drēbes kaudzē.

425
00:19:52,290 --> 00:19:54,870
Kāpēc jūs valkāt kādu
Citi reizi awhile?

426
00:19:54,870 --> 00:19:58,020
>> Džeks teica, labi, kad es
noņemt drēbes un zeķes,

427
00:19:58,020 --> 00:20:00,780
Es nomazgājiet tos un nodot
viņus prom lodziņā.

428
00:20:00,780 --> 00:20:03,210
Tad nāk nākamais
no rīta, un līdz es hop.

429
00:20:03,210 --> 00:20:06,380
Es eju uz kastes un saņemt
manas drēbes off augšpusē.

430
00:20:06,380 --> 00:20:09,070
Lou ātri saprata
problēma ar Jack.

431
00:20:09,070 --> 00:20:12,080
Viņš tur apģērbi, CD,
un grāmatas kaudze.

432
00:20:12,080 --> 00:20:14,420
Kad viņš sasniedza par
kaut ko lasīt vai valkāt,

433
00:20:14,420 --> 00:20:17,100
viņš gribētu izvēlēties top grāmatu vai apakšveļu.

434
00:20:17,100 --> 00:20:19,500
Tad, kad viņš bija darīts, viņš
varētu nodot to tiesības atpakaļ.

435
00:20:19,500 --> 00:20:21,970
Back to varētu iet, virsū kaudze.

436
00:20:21,970 --> 00:20:24,460
Es zinu risinājumu,
teica triumfējošs Loud.

437
00:20:24,460 --> 00:20:27,090
Jums ir nepieciešams, lai uzzinātu, lai
sākt izmantot rindā.

438
00:20:27,090 --> 00:20:29,870
Lou paņēma Jack drēbes un
karājās tos skapī.

439
00:20:29,870 --> 00:20:32,710
Un, kad viņš bija iztukšota
kastē, viņš vienkārši iemeta to.

440
00:20:32,710 --> 00:20:36,500
>> Tad viņš teica, tagad Jack, beigās
diena, lai jūsu drēbes pa kreisi

441
00:20:36,500 --> 00:20:37,990
kad jūs viņus prom.

442
00:20:37,990 --> 00:20:41,300
Tad rīt no rīta, kad jūs
redzēt sauli, saņemt savas drēbes

443
00:20:41,300 --> 00:20:43,440
labajā pusē, no gala līnijas.

444
00:20:43,440 --> 00:20:44,880
Vai tu neredzi? teica Lū.

445
00:20:44,880 --> 00:20:46,370
Tas būs tik jauki.

446
00:20:46,370 --> 00:20:49,770
Jūs valkāt visu reiz
Pirms jūs valkāt kaut divreiz.

447
00:20:49,770 --> 00:20:52,670
Un ar visu rindās
viņa skapī un plauktu,

448
00:20:52,670 --> 00:20:55,160
Jack sāku justies
diezgan pārliecināts par sevi.

449
00:20:55,160 --> 00:20:59,720
Visi pateicoties Lou un
viņa brīnišķīgi rinda.

450
00:20:59,720 --> 00:21:01,220
SPEAKER 1: Nu labi, tas ir adorable.

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

452
00:21:05,920 --> 00:21:10,080
Tātad, kas ir īsti notiek
par zem motora pārsega tagad?

453
00:21:10,080 --> 00:21:12,370
Ka mums ir norādes,
ka mums ir malloc,

454
00:21:12,370 --> 00:21:15,680
ka mums ir iespēja veidot
gabalos atmiņas par sevi

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

456
00:21:16,344 --> 00:21:18,510
Tātad tas ir attēlu mēs
glimpsed tikai otro dienu.

457
00:21:18,510 --> 00:21:21,180
Mums nav īsti kavēties
par to, bet šo attēlu

458
00:21:21,180 --> 00:21:24,180
turpinās jau zem
kapuci nedēļas tagad.

459
00:21:24,180 --> 00:21:27,050
Un tā tas ir, tikai
taisnstūris, ka mēs esam sagatavoti,

460
00:21:27,050 --> 00:21:28,180
datora atmiņā.

461
00:21:28,180 --> 00:21:31,850
Un varbūt jūsu dators, vai CS50
ID, ir gigabaitu atmiņas vai RAM

462
00:21:31,850 --> 00:21:33,050
vai divi gigabaiti vai četri.

463
00:21:33,050 --> 00:21:34,450
Tas nav īsti jautājums.

464
00:21:34,450 --> 00:21:37,240
Jūsu operētājsistēma
Windows vai Mac OS vai Linux,

465
00:21:37,240 --> 00:21:41,120
būtībā ļauj savu programmu
domāt, ka tai ir piekļuve

466
00:21:41,120 --> 00:21:42,982
uz visu
datora atmiņa,

467
00:21:42,982 --> 00:21:45,440
pat ja jūs varētu darboties
vairākas programmas vienlaicīgi.

468
00:21:45,440 --> 00:21:46,990
Tātad patiesībā, tas nav īsti strādāt.

469
00:21:46,990 --> 00:21:49,448
Bet tas ir sava veida ilūziju
pievērsta visas programmas.

470
00:21:49,448 --> 00:21:53,110
Tātad, ja jums ir divi gigs RAM, šis
ir kā dators varētu domāt par to.

471
00:21:53,110 --> 00:21:57,110
>> Tagad nejauši, viens no šiem
lietas, viens no šiem segmentiem atmiņas,

472
00:21:57,110 --> 00:21:58,350
sauc kaudze.

473
00:21:58,350 --> 00:22:01,680
Un tiešām jebkurā laikā
līdz šim rakstiski kodu

474
00:22:01,680 --> 00:22:05,900
ka esat sauc
funkcija, piemēram maģistrāli.

475
00:22:05,900 --> 00:22:08,410
Atgādināt, ka jebkurā laikā es esmu
Drawn datora atmiņā,

476
00:22:08,410 --> 00:22:10,640
Es vienmēr izdarīt veida
puse no taisnstūra šeit

477
00:22:10,640 --> 00:22:12,520
un nav apnikt runāt
par to, kas iepriekš.

478
00:22:12,520 --> 00:22:15,980
Jo tad, kad galvenais sauc, es apgalvot
ka jums šis skaida atmiņas

479
00:22:15,980 --> 00:22:16,970
kas iet uz leju šeit.

480
00:22:16,970 --> 00:22:20,650
Un, ja galvenais sauc funkcija
piemēram, swap, swap labi iet šeit.

481
00:22:20,650 --> 00:22:23,720
Un izrādās, ka ir
kur tas beidzot.

482
00:22:23,720 --> 00:22:26,277
Par kaut ko sauc kaudze
iekšpusē datora atmiņā.

483
00:22:26,277 --> 00:22:28,360
Tagad beigās, dienā,
tas ir tikai adreses.

484
00:22:28,360 --> 00:22:30,680
Tas ir tāpat kā baitu nulles,
baitu viens, baits 2 miljardiem.

485
00:22:30,680 --> 00:22:33,130
Bet, ja jūs domājat par to
kā šo taisnstūra objektu,

486
00:22:33,130 --> 00:22:35,130
viss, ko mēs darām katru
Šoreiz mēs saucam funkcija ir

487
00:22:35,130 --> 00:22:37,180
layering jaunu šķēle atmiņas.

488
00:22:37,180 --> 00:22:41,700
Mēs dodam šo funkciju šķēle
savas atmiņas, lai strādātu ar.

489
00:22:41,700 --> 00:22:44,490
>> Un atcerēties tagad, kad tas ir svarīgi.

490
00:22:44,490 --> 00:22:46,400
Jo, ja mums ir
kaut kā mijmaiņas

491
00:22:46,400 --> 00:22:51,610
un divas vietējās mainīgie, piemēram, A un B un
mēs mainīt šīs vērtības no viena un divu

492
00:22:51,610 --> 00:22:55,130
uz divām un vienu, atsaukšanas
ka tad, kad swap atgriežas,

493
00:22:55,130 --> 00:22:58,330
tas ir tā, it kā šī šķēle
atmiņas ir tikai aizgāja.

494
00:22:58,330 --> 00:23:00,080
Patiesībā, tas joprojām ir
tur forensically.

495
00:23:00,080 --> 00:23:01,940
Un kaut kas vēl patiesībā tur.

496
00:23:01,940 --> 00:23:05,410
Bet konceptuāli, tas ir kā
ja tas ir pilnīgi pagājis.

497
00:23:05,410 --> 00:23:10,910
Un tā galvenais nezina kādu no darba
kas tika darīts šajā mijmaiņas funkciju,

498
00:23:10,910 --> 00:23:14,890
ja vien tas ir faktiski nodots tiem
argumenti kursoru vai ar atsauci.

499
00:23:14,890 --> 00:23:17,790
Tagad galvenais risinājums
šai problēmai ar swap

500
00:23:17,790 --> 00:23:19,970
ir iet lietas pēc adreses.

501
00:23:19,970 --> 00:23:23,250
Bet izrādās, pārāk, kas ir
turpinās jau iepriekš, ka daļa

502
00:23:23,250 --> 00:23:26,330
no taisnstūra visu šo laiku ir
Pagaidām tur ir vairāk atmiņas tur augšā.

503
00:23:26,330 --> 00:23:28,790
Un, kad jūs dinamiski
piešķirt atmiņu,

504
00:23:28,790 --> 00:23:32,020
vai tas ir iekšpusē GetString, kas
mēs esam bijuši dara, lai jūs par CS50

505
00:23:32,020 --> 00:23:34,710
bibliotēka, vai, ja jūs guys
zvaniet malloc un jautāt

506
00:23:34,710 --> 00:23:37,950
operētājsistēma rieciens
atmiņa, tas nenāk no skursteņa.

507
00:23:37,950 --> 00:23:40,960
Tas nāk no citas vietas
Jūsu datora atmiņā

508
00:23:40,960 --> 00:23:42,220
ka sauc kaudze.

509
00:23:42,220 --> 00:23:43,430
Un tas vēl nav atšķirīgi.

510
00:23:43,430 --> 00:23:44,285
Tas ir tas pats RAM.

511
00:23:44,285 --> 00:23:45,160
Tas ir tas pats atmiņas.

512
00:23:45,160 --> 00:23:49,080
Tas ir tikai RAM, kas ir atkarīgs
tur, nevis uz leju šeit.

513
00:23:49,080 --> 00:23:50,750
>> Un tā, ko tas nozīmē?

514
00:23:50,750 --> 00:23:53,650
Nu, ja jūsu dators ir
ierobežots atmiņas apjoms

515
00:23:53,650 --> 00:23:57,450
un kaudze aug, tāpēc
runāt, un kaudze, saskaņā

516
00:23:57,450 --> 00:23:59,349
šim bultiņas, pieaug uz leju.

517
00:23:59,349 --> 00:24:01,140
Citiem vārdiem sakot, katrs
reizi, kad jūs zvanu malloc,

518
00:24:01,140 --> 00:24:03,430
jūs ir dota šķēle
atmiņas no augšas,

519
00:24:03,430 --> 00:24:06,630
tad varbūt nedaudz zemāks, tad nedaudz
zemāks, katru reizi, kad zvana malloc,

520
00:24:06,630 --> 00:24:10,100
kaudze, tā ir izmantošana,
ir sava veida pieaug,

521
00:24:10,100 --> 00:24:11,950
aug tuvāk un tuvāk, ko?

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

523
00:24:13,382 --> 00:24:14,840
Tātad tas šķist laba ideja?

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

525
00:24:18,420 --> 00:24:22,140
Es domāju, ja tas nav īsti skaidrs
ko vēl jūs varat darīt, ja jums ir tikai

526
00:24:22,140 --> 00:24:23,910
ir ierobežots atmiņas apjomu.

527
00:24:23,910 --> 00:24:25,200
Bet tas, protams, slikti.

528
00:24:25,200 --> 00:24:27,920
Šie divi bultas ir par
crash kurss par vienu citu.

529
00:24:27,920 --> 00:24:31,930
>> Un izrādās, ka slikts puisis, ļaudīm, kas
ir īpaši labi ar plānošanu,

530
00:24:31,930 --> 00:24:36,140
un mēģina uzlauzt datorus,
var izmantot šo realitāti.

531
00:24:36,140 --> 00:24:38,290
Patiesībā, pieņemsim apsvērt
mazliet fragments.

532
00:24:38,290 --> 00:24:41,350
Tātad šis ir piemērs, jūs varat izlasīt
par sīkāk par Wikipedia.

533
00:24:41,350 --> 00:24:43,100
Mēs punkts jums pie
raksts ja ziņkārīgs.

534
00:24:43,100 --> 00:24:45,650
Bet tur ir uzbrukums vispār
pazīstams kā bufera pārpildes, ka

535
00:24:45,650 --> 00:24:49,570
ir pastāvējusi tik ilgi, cik cilvēkiem
ir bijusi iespēja manipulēt

536
00:24:49,570 --> 00:24:53,120
datora atmiņa, īpaši C.
Tātad šī ir ļoti patvaļīgs programma,

537
00:24:53,120 --> 00:24:55,130
bet pieņemsim lasīt no apakšas uz augšu.

538
00:24:55,130 --> 00:24:57,650
Galvenā vērā argC char zvaigžņu argv.

539
00:24:57,650 --> 00:24:59,830
Tātad tā ir programma, kas ņem
komandrindas argumentus.

540
00:24:59,830 --> 00:25:03,620
Un viss galvenais tas acīmredzot ir aicinājums
funkcija, to sauc F vienkāršību.

541
00:25:03,620 --> 00:25:04,610
Un tas iet uz ko?

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

543
00:25:05,490 --> 00:25:09,320
Tātad tas nonāk F neatkarīgi
vārds ir tas, ka lietotājs drukāti

544
00:25:09,320 --> 00:25:11,500
pie uzvednē pēc tam, kad
Programmas nosaukums vispār.

545
00:25:11,500 --> 00:25:15,730
Tik daudz, piemēram, Cēzara vai Vigenere, kas
jūs varētu atgādināt darāt ar argv.

546
00:25:15,730 --> 00:25:16,680
>> Tātad, kas ir F?

547
00:25:16,680 --> 00:25:19,760
F notiek virknē
tās vienīgais arguments,

548
00:25:19,760 --> 00:25:22,100
AKA char zvaigzne, pats
lieta, kā virkni.

549
00:25:22,100 --> 00:25:24,920
Un to sauc patvaļīgi
bārs šajā piemērā.

550
00:25:24,920 --> 00:25:27,710
Un tad char c 12,
tikai lajs izteiksmē,

551
00:25:27,710 --> 00:25:31,750
kāda ir char c kronšteins 12 darot mums?

552
00:25:31,750 --> 00:25:33,440
Ko tas dara?

553
00:25:33,440 --> 00:25:36,490
Piešķirot atmiņu, īpaši
12 baiti par 12 simboli.

554
00:25:36,490 --> 00:25:36,990
Tieši tā.

555
00:25:36,990 --> 00:25:40,000
Un tad pēdējā rindā, samaisa un
kopija, jūs, iespējams, nav redzējuši.

556
00:25:40,000 --> 00:25:43,360
Tas ir virkne kopija
funkcija, kuras mērķis dzīvē

557
00:25:43,360 --> 00:25:48,160
ir kopēt savu otro argumentu
uz savu pirmo argumentu

558
00:25:48,160 --> 00:25:51,190
bet tikai līdz
noteiktu skaitu baitu.

559
00:25:51,190 --> 00:25:53,860
Tātad trešais arguments saka,
cik baiti jums vajadzētu kopēt?

560
00:25:53,860 --> 00:25:56,720
No bāra garums,
kāds lietotājs drukāti.

561
00:25:56,720 --> 00:25:59,320
Un saturs
bārs, ka virkne ir

562
00:25:59,320 --> 00:26:02,330
kopēts atmiņā norādīja at C.

563
00:26:02,330 --> 00:26:04,060
>> Tātad tas šķiet veida stulba, un tas ir.

564
00:26:04,060 --> 00:26:06,300
Tas ir izdomāts piemērs,
bet tas ir reprezentatīvs

565
00:26:06,300 --> 00:26:10,100
no klases uzbrukuma vektori,
veids, kā uzbrukt programmu.

566
00:26:10,100 --> 00:26:15,050
Viss ir labi un labi, ja lietotājs
veidi vārdu, kas ir 11 rakstzīmes

567
00:26:15,050 --> 00:26:18,040
vai mazāk, plus slīpsvītra nulle.

568
00:26:18,040 --> 00:26:22,830
Ko darīt, ja lietotājs veidi vairāk nekā
11 vai 12 vai 20 vai 50 simboli?

569
00:26:22,830 --> 00:26:25,090
Kas ir šī programma gatavojas darīt?

570
00:26:25,090 --> 00:26:29,360
Potenciāli SEG vaina. Tas notiek
akli kopēt visu bārā augšu

571
00:26:29,360 --> 00:26:31,750
uz tās garumā, kas ir
burtiski viss joslā,

572
00:26:31,750 --> 00:26:36,307
uz adresi norādīja C. Bet C
ir tikai preemptively dota kā 12 baitu.

573
00:26:36,307 --> 00:26:37,640
Bet tur nav papildu pārbaude.

574
00:26:37,640 --> 00:26:38,700
Nav ja apstākļi.

575
00:26:38,700 --> 00:26:40,580
Nav kļūdu pārbaude šeit.

576
00:26:40,580 --> 00:26:43,270
>> Un tā, ko šī programma ir
gatavojas darīt, ir tikai akli

577
00:26:43,270 --> 00:26:45,750
kopēt viena lieta uz otru.

578
00:26:45,750 --> 00:26:47,880
Un tāpēc, ja mēs izdarīt šo
kā attēlu, šeit ir

579
00:26:47,880 --> 00:26:49,860
tikai skaida no atmiņas vietas.

580
00:26:49,860 --> 00:26:53,470
Tā paziņojuma apakšā, mēs
ir vietējo mainīgo bar.

581
00:26:53,470 --> 00:26:57,330
Tā, ka rādītāja, kas notiek, lai store--
drīzāk, ka vietējās argumentu, kas ir

582
00:26:57,330 --> 00:26:58,672
gatavojas glabāt virknes bar.

583
00:26:58,672 --> 00:27:00,380
Un tad pamanīt tikai
Iepriekš tā kaudze,

584
00:27:00,380 --> 00:27:02,505
jo katru reizi, kad jūs lūgt
lai atmiņas par kaudze,

585
00:27:02,505 --> 00:27:04,310
tas iet mazliet
virs tā gleznieciski,

586
00:27:04,310 --> 00:27:06,270
paziņojums, ka mēs esam ieguvuši 12 baiti tur.

587
00:27:06,270 --> 00:27:10,690
Augšējā kreisajā viens ir C kronšteins nulle un
apakšējā labajā viens ir C kronšteins 11.

588
00:27:10,690 --> 00:27:12,870
Tas ir tikai kā datori
gatavojas nolikt to ārā.

589
00:27:12,870 --> 00:27:18,300
Tik vienkārši intuitīvi, ja josla ir vairāk
nekā 12 rakstzīmes kopā, t.sk.

590
00:27:18,300 --> 00:27:25,790
Reversā slīpsvītra nulles, kur ir
12 vai C kronšteins 12 gatavojas doties?

591
00:27:25,790 --> 00:27:28,440
Vai drīzāk, kur ir 12
raksturs vai 13 raksturs,

592
00:27:28,440 --> 00:27:30,900
Attiecīgā simtdaļa raksturs iet
nonākt attēlā?

593
00:27:30,900 --> 00:27:33,400
Virs vai zem?

594
00:27:33,400 --> 00:27:36,300
>> Pareizi, jo, pat ja
kaudze pati aug uz augšu,

595
00:27:36,300 --> 00:27:39,590
kad jūs esat likts sabāzt
tā, tā konstrukcijas iemeslu dēļ

596
00:27:39,590 --> 00:27:41,294
liek atmiņu no augšas uz leju.

597
00:27:41,294 --> 00:27:44,460
Tātad, ja jūs esat ieguvuši vairāk nekā 12 baiti,
jūs gatavojas sākt pārrakstīt bar.

598
00:27:44,460 --> 00:27:47,280
Tagad tas ir bug, bet tas ir
nav īsti liels darījumu.

599
00:27:47,280 --> 00:27:51,130
Bet tas ir īpašs, jo tur ir
vairāk sīkumi notiek atmiņā.

600
00:27:51,130 --> 00:27:53,074
Tātad, lūk, kā mēs varētu
likts hello, lai būtu skaidrs.

601
00:27:53,074 --> 00:27:54,490
Ja es drukāti sveiki pie uzvednē.

602
00:27:54,490 --> 00:27:59,330
H-E-L-L-O slīpsvītru nulle, beidzas laikā
šie 12 baiti, un mēs esam super droši.

603
00:27:59,330 --> 00:28:00,330
Viss ir labi.

604
00:28:00,330 --> 00:28:03,020
Bet, ja es tipa kaut ko
ilgāk, iespējams, tas ir

605
00:28:03,020 --> 00:28:05,860
gatavojas rāpot uz bāra telpas.

606
00:28:05,860 --> 00:28:08,405
Bet vēl sliktāk, izrādās
ārā visu šo laiku,

607
00:28:08,405 --> 00:28:11,530
kaut arī mēs nekad runāja par
tas, kaudze izmanto citas lietas.

608
00:28:11,530 --> 00:28:13,560
Tas ir ne tikai vietējie mainīgie.

609
00:28:13,560 --> 00:28:15,100
>> C ir ļoti zema līmeņa valoda.

610
00:28:15,100 --> 00:28:17,810
Un tā veida slepeni
izmanto kaudze arī

611
00:28:17,810 --> 00:28:21,260
atcerēties, kad
funkcija sauc, ko

612
00:28:21,260 --> 00:28:26,040
adrese ir no iepriekšējo funkciju,
lai tā varētu pāriet atpakaļ uz šo funkciju.

613
00:28:26,040 --> 00:28:29,980
Tātad, kad galvenie aicina swap, starp
lietas uzstāja uz skursteņa

614
00:28:29,980 --> 00:28:34,380
ir ne tikai mijmaiņas vietējo mainīgie,
vai tās argumenti, arī slepeni uzstāja

615
00:28:34,380 --> 00:28:37,510
uz skursteņa ko pārstāv
ar sarkano šķēli šeit,

616
00:28:37,510 --> 00:28:40,520
ir adrese galvenais fiziski
jūsu datora atmiņā,

617
00:28:40,520 --> 00:28:44,180
tā, ka tad, kad swap tiek darīts, dators
zina, man ir nepieciešams, lai dotos atpakaļ uz galveno

618
00:28:44,180 --> 00:28:46,760
un pabeigt izpildot galveno funkciju.

619
00:28:46,760 --> 00:28:51,960
Tātad tas ir bīstami tagad, jo, ja
lietotājs veidi arī vairāk nekā sveiki,

620
00:28:51,960 --> 00:28:57,030
tāds, ka lietotāja ievade clobbers
vai pārraksta ka sarkanā sadaļu,

621
00:28:57,030 --> 00:28:59,820
loģiski, ja dators ir
tikai gatavojas akli pieņemt,

622
00:28:59,820 --> 00:29:03,830
ka baiti šajā sarkanu šķēle ir
adresi, uz kuru tas būtu atgriezties,

623
00:29:03,830 --> 00:29:09,020
ko tad, ja pretinieks ir pietiekami gudrs, vai
paveicies likt secība baitu

624
00:29:09,020 --> 00:29:13,450
tur, ka izskatās adresi,
bet tas ir adrese kodu

625
00:29:13,450 --> 00:29:18,730
ka viņš vai viņa vēlas datoru
izpildīt, nevis galvenais?

626
00:29:18,730 --> 00:29:21,670
>> Citiem vārdiem sakot, ja tas, ko
lietotājs ir rakstīt par ātru,

627
00:29:21,670 --> 00:29:23,850
ir ne tikai kaut ko
nekaitīgs patīk hello,

628
00:29:23,850 --> 00:29:28,210
bet patiesībā tas ir kods, kas ir ekvivalents
izdzēst visus šī lietotāja failus?

629
00:29:28,210 --> 00:29:30,060
Vai e-pastu savu paroli uz mani?

630
00:29:30,060 --> 00:29:31,940
Vai sākt piesakoties viņu
keystrokes, vai ne?

631
00:29:31,940 --> 00:29:34,920
Ir veids, pieņemsim paredz šodien,
ka viņi varētu rakstīt ne tikai sveiki

632
00:29:34,920 --> 00:29:36,711
pasaules vai savu vārdu,
tie varētu būtiski

633
00:29:36,711 --> 00:29:39,570
apliecību kods, nulles un
dzīvotspēju, ka dators

634
00:29:39,570 --> 00:29:43,450
kļūdas, kuras gan kodu un adresi.

635
00:29:43,450 --> 00:29:48,950
Tātad kaut nedaudz abstrakti, ja
lietotājs veidu pietiekami sacīkstes kodu

636
00:29:48,950 --> 00:29:52,330
ka mēs vispārināt šeit kā
A. A ir uzbrukums vai pretiniekiem.

637
00:29:52,330 --> 00:29:53,140
Tik vienkārši slikti sīkumi.

638
00:29:53,140 --> 00:29:55,306
Mums nav rūp
numurus vai nulles vai tiem

639
00:29:55,306 --> 00:29:59,470
Šodien, piemēram, ka jūs galu galā
pārrakstīšanas ka sarkanā sadaļu,

640
00:29:59,470 --> 00:30:01,580
paziņojums, ka baitu secība.

641
00:30:01,580 --> 00:30:05,020
O 835 C nulle astoņi nulle.

642
00:30:05,020 --> 00:30:08,960
Un tagad, kad Vikipēdijas raksts šeit
ir ierosinājusi, ja jūs tagad faktiski sākt

643
00:30:08,960 --> 00:30:12,460
marķēšanas baitu datora
atmiņa, ko Wikipedia raksts ir

644
00:30:12,460 --> 00:30:19,060
iesniedzēja ir tas, kas notiks, ja adrese
Minētā augšējā kreisajā baits ir 80 C 0 3508.

645
00:30:19,060 --> 00:30:22,200
>> Citiem vārdiem sakot, ja slikts puisis ir
pietiekami gudrs, ar viņa vai viņas kodu

646
00:30:22,200 --> 00:30:26,650
faktiski likt numuru šeit
atbilst adresi koda

647
00:30:26,650 --> 00:30:29,180
viņš vai viņa injicē
datorā, jūs

648
00:30:29,180 --> 00:30:31,050
var triks datoru
uz darot jebko.

649
00:30:31,050 --> 00:30:34,140
Noņemot failus, e-pastu
lietas, sniffing savu satiksmes,

650
00:30:34,140 --> 00:30:36,710
burtiski kaut kas varētu būt
ievada datorā.

651
00:30:36,710 --> 00:30:39,220
Un tā bufera pārpildes
uzbrukums tās kodols

652
00:30:39,220 --> 00:30:43,530
ir tikai stulba, stulba
sevišķas no masīva, kas

653
00:30:43,530 --> 00:30:45,840
nebija pārbaudījusi tās robežas.

654
00:30:45,840 --> 00:30:48,850
Un tas ir tas, kas ir super bīstami
un vienlaicīgi super jaudīgu

655
00:30:48,850 --> 00:30:52,560
C ir tas, ka mums patiešām ir
piekļuve jebkur atmiņā.

656
00:30:52,560 --> 00:30:55,320
Tas ir atkarīgs no mums, programmētāji,
kas raksta sākotnējo kodu

657
00:30:55,320 --> 00:30:59,330
lai pārbaudītu darn garumu jebkurš
masīvi, ka mēs esam manipulācijas.

658
00:30:59,330 --> 00:31:00,750
Tātad, lai būtu skaidrs, kāda ir noteikt?

659
00:31:00,750 --> 00:31:03,190
Ja mēs roll atpakaļ uz šo
kods, es ne tikai

660
00:31:03,190 --> 00:31:08,000
mainīt garumu joslas, ko
cits man būtu pārbaudīt?

661
00:31:08,000 --> 00:31:10,620
Kas vēl man darīt, lai
novērstu šo uzbrukumu pilnībā?

662
00:31:10,620 --> 00:31:14,110
Es nevēlos, lai tikai akli teikt
ka jums vajadzētu kopēt tik daudz baitu

663
00:31:14,110 --> 00:31:16,140
kā ir garums bar.

664
00:31:16,140 --> 00:31:18,910
Es gribu teikt, kopēt kā
daudzi baiti kā ir bar

665
00:31:18,910 --> 00:31:24,090
līdz piešķirtais
atmiņa, vai 12 maksimāli.

666
00:31:24,090 --> 00:31:27,450
Tāpēc man vajag kādu, ja stāvoklis
kas nav pārbaudīt garumu joslas,

667
00:31:27,450 --> 00:31:32,800
bet, ja tas pārsniedz 12, mēs vienkārši grūti kodu
12 kā maksimālo iespējamo attālumu.

668
00:31:32,800 --> 00:31:35,910
Pretējā gadījumā tā saukto bufera
pārplūdes uzbrukums var notikt.

669
00:31:35,910 --> 00:31:38,451
Apakšā šiem slaidiem,
Ja jūs esat ieinteresēti, lai uzzinātu vairāk

670
00:31:38,451 --> 00:31:41,200
ir faktiskais sākotnējo rakstu
ja jūs vēlaties, lai to apskatīt.

671
00:31:41,200 --> 00:31:44,550
>> Bet tagad, starp cenām
maksā šeit bija neefektivitāte.

672
00:31:44,550 --> 00:31:46,680
Tā, ka bija ātrs
zems līmenis apskatīt to, ko

673
00:31:46,680 --> 00:31:49,709
problēmas var rasties tagad, ka mēs
piekļūt datora atmiņā.

674
00:31:49,709 --> 00:31:51,750
Bet vēl viena problēma, kas mums
jau paklupa pirmdien

675
00:31:51,750 --> 00:31:53,800
bija tikai neefektivitāti
no saistītajā sarakstā.

676
00:31:53,800 --> 00:31:56,019
Mēs esam atpakaļ uz lineāro laiku.

677
00:31:56,019 --> 00:31:57,560
Mums vairs nav blakusesošo masīvs.

678
00:31:57,560 --> 00:31:58,980
Mums nav brīvpieejas.

679
00:31:58,980 --> 00:32:00,710
Mēs nevaram izmantot kvadrātiekava notācija.

680
00:32:00,710 --> 00:32:04,590
Mums burtiski ir jāizmanto kamēr cilpa
kādu es uzrakstīju pirms brīža.

681
00:32:04,590 --> 00:32:09,740
Bet pirmdien, mēs apgalvoja, ka mēs varam
rāpot atpakaļ valstība efektivitātes

682
00:32:09,740 --> 00:32:13,040
panākt kaut ko, kas ir
logaritmiska varbūt, vai labākais vēl,

683
00:32:13,040 --> 00:32:16,120
varbūt pat kaut kas ir
tā saukto konstante laiks.

684
00:32:16,120 --> 00:32:19,840
Tātad, kā mēs varam darīt, ka, izmantojot šīs jaunās
instrumenti, šīs adreses, šie Pointers,

685
00:32:19,840 --> 00:32:22,210
un vītņu lietas mūsu pašu?

686
00:32:22,210 --> 00:32:23,960
Nu, pieņemsim, ka
šeit, tie ir ķekars

687
00:32:23,960 --> 00:32:27,170
skaitļu, ka mēs vēlamies, lai Uzglabāt
datu struktūru un meklēt efektīvi.

688
00:32:27,170 --> 00:32:30,960
Mēs varam pilnīgi attīt uz nedēļu
divi, mest tos vērā masīva,

689
00:32:30,960 --> 00:32:33,150
un meklēt tos, izmantojot bināro meklēšanu.

690
00:32:33,150 --> 00:32:34,040
Divide un iekarot.

691
00:32:34,040 --> 00:32:37,720
Un patiesībā jūs rakstījāt
binārā sektorā PSET3,

692
00:32:37,720 --> 00:32:40,100
kur jūs īstenoja atrašanas programmu.

693
00:32:40,100 --> 00:32:40,890
Bet jūs zināt, kas.

694
00:32:40,890 --> 00:32:45,060
Tur ir sava veida vairāk
gudrs veids, kā to izdarīt.

695
00:32:45,060 --> 00:32:47,390
Tas ir nedaudz vairāk
sarežģīta un tas, iespējams,

696
00:32:47,390 --> 00:32:50,830
ļauj mums redzēt, kāpēc bināro
meklēšana ir tik daudz ātrāk.

697
00:32:50,830 --> 00:32:52,980
Pirmkārt, pieņemsim iepazīstināt
jēdziens koku.

698
00:32:52,980 --> 00:32:54,730
Kurš kaut arī
realitāte koki veida

699
00:32:54,730 --> 00:32:57,730
augt, piemēram, tas, pasaulē datora
zinātne viņi veida aug uz leju

700
00:32:57,730 --> 00:33:00,830
piemēram, ģimenes koku, kur jums ir
jūsu vecvecāki vai vecvecvecākus

701
00:33:00,830 --> 00:33:04,580
vai plauktiņš augšpusē, patriarha un
matriarch ģimenes, tikai viens

702
00:33:04,580 --> 00:33:07,930
tā sauktais saknes, mezglu, zemāk
kas ir tās bērni,

703
00:33:07,930 --> 00:33:11,442
zem kuras ir tās bērni, vai
tās pēcteči kopumā.

704
00:33:11,442 --> 00:33:13,400
Un ikviens piekārtiem off
apakšā ģimenes

705
00:33:13,400 --> 00:33:16,070
koks, turklāt esot
jaunākais ģimenē,

706
00:33:16,070 --> 00:33:19,520
arī var vienkārši būt vispārēji
sauc koka lapas.

707
00:33:19,520 --> 00:33:21,800
>> Tātad tas ir tikai ķekars
vārdiem un definīcijas

708
00:33:21,800 --> 00:33:25,790
kaut ko sauc par koku datorā
zinātne, līdzīgi ciltskoku.

709
00:33:25,790 --> 00:33:28,770
Bet tur ir mīļotājs iemiesojumiem
koku, no kuriem viens

710
00:33:28,770 --> 00:33:30,780
To sauc par bināro meklēšanu koks.

711
00:33:30,780 --> 00:33:34,380
Un jūs varat veida kaitināt
izņemot to, ko šī lieta nav.

712
00:33:34,380 --> 00:33:37,180
Nu, tas ir bināro kādā ziņā?

713
00:33:37,180 --> 00:33:41,455
Kur binārais nāk no šejienes?

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

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

716
00:33:45,961 --> 00:33:47,210
Tas nav tik daudz, vai nu vai.

717
00:33:47,210 --> 00:33:52,000
Tas ir vairāk, ka katrs no mezgliem ir ne
vairāk nekā divi bērni, kā mēs redzam šeit.

718
00:33:52,000 --> 00:33:54,990
Vispār, tree-- un
jūsu vecāki un vecvecāki

719
00:33:54,990 --> 00:33:57,640
var būt tik daudz bērnus vai
grandkids jo viņi patiešām vēlas,

720
00:33:57,640 --> 00:34:00,820
un tāpēc, piemēram, tur mums ir trīs
Bērni off, ka labajā mezglā,

721
00:34:00,820 --> 00:34:05,480
bet bināro koku, mezgls ir
nulle, viens vai divi bērni maksimāli.

722
00:34:05,480 --> 00:34:08,496
Un tas ir jauki īpašums,
jo, ja tas ir ierobežots ar divi

723
00:34:08,496 --> 00:34:10,620
mēs ejam, lai varētu
saņemt nedaudz log bāzi divi

724
00:34:10,620 --> 00:34:11,975
darbība notiek šeit galu galā.

725
00:34:11,975 --> 00:34:13,350
Tātad mums ir kaut logaritmisko.

726
00:34:13,350 --> 00:34:14,558
Bet vairāk par to pēc brīža.

727
00:34:14,558 --> 00:34:19,810
Meklēt koks nozīmē, ka skaitļi ir
ierīkotas tā, lai pa kreisi bērna

728
00:34:19,810 --> 00:34:22,429
vērtība ir lielāka nekā saknes.

729
00:34:22,429 --> 00:34:26,010
Un tās tiesības bērns
lielāks nekā saknes.

730
00:34:26,010 --> 00:34:29,290
Citiem vārdiem sakot, ja jūs lietojat kādu no
mezglus, apļi šajā attēlā,

731
00:34:29,290 --> 00:34:31,840
un skatās tās pa kreisi
Bērns un tā tiesības bērns,

732
00:34:31,840 --> 00:34:34,739
pirmais jābūt mazākam nekā,
otrais jābūt lielākam par.

733
00:34:34,739 --> 00:34:36,159
Tātad vesels saprāts pārbaudīt 55.

734
00:34:36,159 --> 00:34:37,780
Tas ir atstājis bērnam ir 33.

735
00:34:37,780 --> 00:34:38,620
Tas ir mazāk nekā.

736
00:34:38,620 --> 00:34:40,929
55, tā tiesības bērns ir 77.

737
00:34:40,929 --> 00:34:41,783
Tas ir lielāks nekā.

738
00:34:41,783 --> 00:34:43,199
Un tas ir rekursīvs definīcija.

739
00:34:43,199 --> 00:34:46,480
Mēs varētu pārbaudīt katru no tiem
mezgli un tas pats modelis varētu turēt.

740
00:34:46,480 --> 00:34:49,389
>> Tātad, kas ir jauki
binārā meklēšana koks, ir

741
00:34:49,389 --> 00:34:52,204
ka viens, mēs varam īstenot
ar struktūrai, tāpat kā šo.

742
00:34:52,204 --> 00:34:54,620
Un, pat ja mēs esam throwing
daudz konstrukciju JŪSU,

743
00:34:54,620 --> 00:34:56,560
viņi nedaudz
intuitīvi tagad cerams.

744
00:34:56,560 --> 00:35:00,570
Sintakse ir joprojām Arcane pārliecināts,
bet saturs mezglu šajā

745
00:35:00,570 --> 00:35:02,786
context-- un mēs turpinām
izmantojot vārdu mezglu,

746
00:35:02,786 --> 00:35:04,910
vai tas ir taisnstūris
uz ekrāna vai apli,

747
00:35:04,910 --> 00:35:08,970
tas ir tikai daži vispārējs konteiners,
šajā gadījumā no koka, piemēram, vienu

748
00:35:08,970 --> 00:35:11,780
mēs redzējām, mums ir nepieciešams vesels skaitlis
katrā no mezgliem

749
00:35:11,780 --> 00:35:15,460
un tad man vajag divas norādes kas norāda
uz kreiso bērnu un labo bērnu,

750
00:35:15,460 --> 00:35:16,590
attiecīgi.

751
00:35:16,590 --> 00:35:20,730
Tātad, tas ir, kā mēs varētu
īsteno ka struct.

752
00:35:20,730 --> 00:35:22,315
Un kā es varētu īstenot to kodu?

753
00:35:22,315 --> 00:35:26,730
Nu, pieņemsim ātri
apskatīt šo tiny piemēru.

754
00:35:26,730 --> 00:35:29,820
Tas nav funkcionāls, bet es esmu
nokopēt un ielīmēt šo struktūru.

755
00:35:29,820 --> 00:35:33,510
Un, ja mana funkcija bināro
meklēšana koku sauc meklēšanu,

756
00:35:33,510 --> 00:35:36,980
un tas aizņem divus argumentus,
vesels skaitlis N un rādītājs

757
00:35:36,980 --> 00:35:41,400
uz mezglu, tāpēc rādītāju uz koku
vai rādītāju uz saknes koku,

758
00:35:41,400 --> 00:35:43,482
Kā es varu iet par meklē N?

759
00:35:43,482 --> 00:35:45,440
Nu, pirmkārt, tāpēc, ka es esmu
nodarbojas ar norādes,

760
00:35:45,440 --> 00:35:46,750
Es esmu gatavojas darīt veselība pārbaudītu.

761
00:35:46,750 --> 00:35:54,279
Ja koku vienlīdzīgi vienāds null, ir N
šajā kokā vai ne šajā kokā?

762
00:35:54,279 --> 00:35:55,070
Tā nevar būt, vai ne?

763
00:35:55,070 --> 00:35:56,870
Ja es esmu garām null,
tur nekā nav.

764
00:35:56,870 --> 00:35:59,230
Es varētu arī vienkārši
akli teikt atgriezties viltus.

765
00:35:59,230 --> 00:36:04,050
Ja jūs varētu man nekas, es, protams, nevaru
atrast nevienu numuru N. Tātad, ko vēl varētu man

766
00:36:04,050 --> 00:36:04,750
pārbaudiet tagad?

767
00:36:04,750 --> 00:36:12,830
Es esmu gatavojas teikt arī cits, ja N ir
mazāk nekā kāds ir koku mezglā

768
00:36:12,830 --> 00:36:16,300
ka es esmu nodota N vērtību.

769
00:36:16,300 --> 00:36:20,270
Citiem vārdiem sakot, ja numurs es esmu
meklē, N, ir mazāks nekā mezglā

770
00:36:20,270 --> 00:36:21,340
ka es esmu meklē.

771
00:36:21,340 --> 00:36:23,190
Un mezglu Es meklēju
at sauc koku,

772
00:36:23,190 --> 00:36:26,370
un atsauktu no iepriekšējā piemērā
nokļūt pie vērtības rādītājs,

773
00:36:26,370 --> 00:36:28,310
Es izmantoju bultiņas notācija.

774
00:36:28,310 --> 00:36:35,960
Tātad, ja N ir mazāks par koku bultas
N, es gribu, lai konceptuāli iet pa kreisi.

775
00:36:35,960 --> 00:36:38,590
Kā es varu izteikt meklēšanas, pa kreisi?

776
00:36:38,590 --> 00:36:41,560
Lai būtu skaidrs, ja tas ir
aina jautājumu

777
00:36:41,560 --> 00:36:44,612
un es esmu izturējis ka augšējais
bultiņa, kas ir vērsta uz leju.

778
00:36:44,612 --> 00:36:45,570
Tas ir mans koks rādītājs.

779
00:36:45,570 --> 00:36:48,060
Es esmu norādot uz koka saknēm.

780
00:36:48,060 --> 00:36:52,100
Un es esmu meklē teiksim, par
skaits 44, patvaļīgi.

781
00:36:52,100 --> 00:36:55,300
Ir 44 mazāk nekā vai
lielāks par 55 acīmredzami?

782
00:36:55,300 --> 00:36:56,360
Tātad, tas ir mazāk nekā.

783
00:36:56,360 --> 00:36:58,760
Un tā tas, ja nosacījums ir piemērojams.

784
00:36:58,760 --> 00:37:03,981
Tātad konceptuāli, ko vēlos
meklēt tālāk, ja es esmu meklē 44?

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

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

787
00:37:08,310 --> 00:37:11,100
>> Tieši tā, es gribu
meklēt kreiso bērnu,

788
00:37:11,100 --> 00:37:12,789
vai pa kreisi sub-tree par šo attēlu.

789
00:37:12,789 --> 00:37:14,830
Un patiesībā, ļaujiet man cauri
attēlu uz leju šeit

790
00:37:14,830 --> 00:37:17,770
tikai brīdi, jo
Es nevaru saskrāpēt šo out.

791
00:37:17,770 --> 00:37:21,150
Ja es sāktu šeit ir 55, un
Es zinu, ka vērtība 44

792
00:37:21,150 --> 00:37:23,180
Es meklēju, ir
kreiso, tas ir sava veida

793
00:37:23,180 --> 00:37:26,010
līdzīgu plīsumi telefona grāmatu
puse vai asarošana koku pusi.

794
00:37:26,010 --> 00:37:29,660
Man vairs nav jārūpējas par
Visa šī puse no koka.

795
00:37:29,660 --> 00:37:33,270
Un tomēr, savādi ziņā no
struktūru, šī lieta vairāk nekā šeit, ka

796
00:37:33,270 --> 00:37:36,682
sākas ar 33, kas pats par sevi
ir bināro meklēšanas koku.

797
00:37:36,682 --> 00:37:39,890
Es teicu vārdu rekursīvas agrāk, jo
patiešām tas ir datu struktūra, kas

798
00:37:39,890 --> 00:37:41,707
pēc definīcijas ir rekursīvs.

799
00:37:41,707 --> 00:37:44,540
Jums varētu būt koku, kas ir šī
liels, bet katrs no saviem bērniem

800
00:37:44,540 --> 00:37:46,870
apzīmē koku tikai nedaudz mazāka.

801
00:37:46,870 --> 00:37:50,910
Tā vietā, lai ar to Grandpa
vai vecmāmiņa, tagad tā ir tikai mamma

802
00:37:50,910 --> 00:37:54,300
or-- es nevaru say-- nav mamma
vai tētis, tas būtu dīvaini.

803
00:37:54,300 --> 00:37:59,000
Tā vietā divi bērni tur
būtu tāpat kā brālis un brālis.

804
00:37:59,000 --> 00:38:01,120
Jaunās paaudzes ģimenes koku.

805
00:38:01,120 --> 00:38:02,900
Bet strukturāli, tā ir tā pati ideja.

806
00:38:02,900 --> 00:38:06,790
Un izrādās, man ir funkcija
ar kuru es varu meklēt bināro meklēšanu

807
00:38:06,790 --> 00:38:07,290
koks.

808
00:38:07,290 --> 00:38:08,680
To sauc meklēšanu.

809
00:38:08,680 --> 00:38:17,870
Es meklētu N koku bultiņas pa kreisi
cits ja n ir lielāks par vērtību

810
00:38:17,870 --> 00:38:18,870
ka es esmu pašlaik.

811
00:38:18,870 --> 00:38:20,800
55. stāsts pirms brīža.

812
00:38:20,800 --> 00:38:23,780
Man ir funkciju sauc
search ka es varu tikai

813
00:38:23,780 --> 00:38:29,660
iet N šo un rekursīvi meklēt
sub-tree un vienkārši atgriešanās

814
00:38:29,660 --> 00:38:30,620
neatkarīgi ka atbilde.

815
00:38:30,620 --> 00:38:33,530
Else Man daži galīgo bāzes lietu šeit.

816
00:38:33,530 --> 00:38:35,310
>> Kas ir pēdējais gadījums?

817
00:38:35,310 --> 00:38:36,570
Tree ir vai nu nulle.

818
00:38:36,570 --> 00:38:39,980
Vērtība es esmu vai nu meklē ir
mazāks nekā tā, vai lielāks nekā tas

819
00:38:39,980 --> 00:38:42,610
vai vienāds ar to.

820
00:38:42,610 --> 00:38:44,750
Un es varētu teikt vienāds
vienāds, bet loģiski tas ir

821
00:38:44,750 --> 00:38:46,500
līdzvērtīgs tikai saku cits šeit.

822
00:38:46,500 --> 00:38:49,150
Tātad taisnība ir, kā es varu atrast kaut ko.

823
00:38:49,150 --> 00:38:51,710
Tātad cerams tas ir
vēl vairāk pārliecinošu piemēru

824
00:38:51,710 --> 00:38:54,900
nekā stulba sigma funkcijas
mēs darījām dažas lekcijas atpakaļ,

825
00:38:54,900 --> 00:38:58,360
kur tas bija tikpat viegli izmantot cilpu
saskaitīt visus numurus no viena

826
00:38:58,360 --> 00:39:02,390
ar N. šeit ar datu struktūru
kas pats par sevi ir rekursīvi

827
00:39:02,390 --> 00:39:07,050
definēts un rekursīvi sastādīts, tagad mēs
ir iespēja izteikt sevi

828
00:39:07,050 --> 00:39:09,780
ar kodu, kas pati par sevi ir rekursīvs.

829
00:39:09,780 --> 00:39:12,580
Tātad šī ir tieši tā pati kodu šeit.

830
00:39:12,580 --> 00:39:14,400
>> Tātad, ko citi problēmas mēs varam atrisināt?

831
00:39:14,400 --> 00:39:18,160
Tik ātri solis prom no
kokus tikai brīdi.

832
00:39:18,160 --> 00:39:20,130
Te ir, teiksim, Vācijas karogu.

833
00:39:20,130 --> 00:39:22,020
Un tur ir skaidri
modelis, lai šo karogu.

834
00:39:22,020 --> 00:39:23,811
Un tur ir daudz
karogi pasaulē, kas

835
00:39:23,811 --> 00:39:27,560
ir tik vienkārši, kā tas izteiksmē
par to krāsas un raksti.

836
00:39:27,560 --> 00:39:31,930
Bet pieņemsim, ka tas tiek saglabāts kā
.GIF, Vai JPEG, vai bitmap, vai ping,

837
00:39:31,930 --> 00:39:34,240
jebkurš grafisko failu formātu
ar kuru jūs esat pazīstami,

838
00:39:34,240 --> 00:39:36,460
daži no kuriem mēs esam
spēlē ar in PSET4.

839
00:39:36,460 --> 00:39:41,550
Tas nešķiet vērts saglabāt
melns pixel, melns pixel, melns pixel,

840
00:39:41,550 --> 00:39:44,790
dot, dot, dot, visu ķekars
melni pikseļi pirmajam scanline,

841
00:39:44,790 --> 00:39:47,430
vai rinda, tad viss ķekars
tas pats, tad viss ķekars

842
00:39:47,430 --> 00:39:49,530
no to pašu, un pēc tam
viss ķekars sarkano pikseļi,

843
00:39:49,530 --> 00:39:53,020
sarkans pikseļi, sarkanā pikseļi, tad viss
ķekars dzeltenās pikseļi, dzeltens, vai ne?

844
00:39:53,020 --> 00:39:55,050
>> Tur ir tik neefektivitāte šeit.

845
00:39:55,050 --> 00:39:59,040
Kā jūs intuitīvi
saspiest Vācijas karogu

846
00:39:59,040 --> 00:40:01,320
ja to īsteno kā failu?

847
00:40:01,320 --> 00:40:04,940
Tāpat kāda informācija mēs varam ne
apnikt glabāšanai diskā, lai

848
00:40:04,940 --> 00:40:08,040
lai samazinātu mūsu faila izmēru no, piemēram,
megabaitu uz kilobaiti, kaut

849
00:40:08,040 --> 00:40:09,430
mazākas?

850
00:40:09,430 --> 00:40:13,130
Kur slēpjas atlaišanas
šeit, lai būtu skaidrs?

851
00:40:13,130 --> 00:40:13,880
Ko jūs varētu darīt?

852
00:40:13,880 --> 00:40:14,380
Yeah?

853
00:40:14,380 --> 00:40:21,380

854
00:40:21,380 --> 00:40:21,970
Tieši tā.

855
00:40:21,970 --> 00:40:24,550
Kāpēc ne, nevis atcerēties
krāsa katru darn pikseli

856
00:40:24,550 --> 00:40:28,200
tāpat kā jūs darāt ar PSET4
ar bitmap failu formātā,

857
00:40:28,200 --> 00:40:32,060
kāpēc nav jūs vienkārši pārstāvēt
kreisās malas kolonnā pikseļi, piemēram,

858
00:40:32,060 --> 00:40:35,370
ķekars melni pikseļi, ķekars
no sarkanā, un ķekars dzeltena,

859
00:40:35,370 --> 00:40:39,210
un tad tikai kaut kā šifrēt
ideja par Atkārtojiet to 100 reizes

860
00:40:39,210 --> 00:40:41,020
vai atkārtot šo 1000 reizes?

861
00:40:41,020 --> 00:40:43,430
Ja 100 vai 1000 ir
tikai vesels skaitlis, lai jūs

862
00:40:43,430 --> 00:40:47,290
var saņemt prom ar tikai ar vienu numuru
nevis simtiem vai tūkstošiem

863
00:40:47,290 --> 00:40:48,270
papildu pikseļi.

864
00:40:48,270 --> 00:40:50,990
Un tiešām, tas, kā mēs
varētu saspiest Vācijas karogu.

865
00:40:50,990 --> 00:40:51,490
Un

866
00:40:51,490 --> 00:40:53,470
Tagad to par Francijas karogu?

867
00:40:53,470 --> 00:40:58,930
Un mazliet daži no veida
garīgās vingrinājums, kurā karogs

868
00:40:58,930 --> 00:41:01,040
var tikt saspiests vairāk uz diska?

869
00:41:01,040 --> 00:41:05,720
Vācijas karogu vai franču
karogs, ja mēs šo pieeju?

870
00:41:05,720 --> 00:41:08,490
Vācijas karogs, jo tur ir
vairāk horizontālā atlaišanu.

871
00:41:08,490 --> 00:41:12,190
Un ar dizainu, daudzi grafisko failu
formāti patiešām strādā kā skenēšanas līnijas

872
00:41:12,190 --> 00:41:12,830
horizontāli.

873
00:41:12,830 --> 00:41:14,674
Viņi varētu strādāt
vertikāli, tikai cilvēce

874
00:41:14,674 --> 00:41:17,090
Pirms nolēma gadiem, ka mēs
parasti domā par lietām, rindas

875
00:41:17,090 --> 00:41:18,880
pēc kārtas, nevis kolonnā pa kolonnas.

876
00:41:18,880 --> 00:41:20,820
Tātad, patiesi, ja tu būtu
apskatīt faila

877
00:41:20,820 --> 00:41:24,670
lielums Vācijas karogu un franču
karogs, tik ilgi, kamēr izšķirtspēja ir

878
00:41:24,670 --> 00:41:27,530
tas pats, tas pats platums
un augstums, tas viens

879
00:41:27,530 --> 00:41:31,580
šeit būs lielāks, jo jums
atkārtot sev trīs reizes.

880
00:41:31,580 --> 00:41:35,570
Jums ir jānorāda zils, atkārtojiet
yourself, balts, atkārtot sevi, sarkans,

881
00:41:35,570 --> 00:41:36,740
atkārtot sevi.

882
00:41:36,740 --> 00:41:39,000
Jūs varat ne tikai iet all
veids, kā labi.

883
00:41:39,000 --> 00:41:41,200
Un kā malā, lai padarītu
skaidrs saspiešanas

884
00:41:41,200 --> 00:41:43,910
ir visur, ja tie ir
četri kadri no a video-- jūs

885
00:41:43,910 --> 00:41:45,890
varētu atgādināt, ka filmu
vai video parasti

886
00:41:45,890 --> 00:41:47,286
piemēram, 29 vai 30 kadriem sekundē.

887
00:41:47,286 --> 00:41:50,410
Tas ir kā mazs uzsist grāmatu, kur jums
tikai redzēt attēlu, attēlu, attēlu, attēlu,

888
00:41:50,410 --> 00:41:54,410
attēls vienkārši super ātri, lai tā izskatās
aktieri uz ekrāna ir kustībā.

889
00:41:54,410 --> 00:41:57,130
Lūk kameņu par
top ķekars ziedu.

890
00:41:57,130 --> 00:41:59,790
Un, lai gan tas varētu būt sava veida
grūti redzēt pēc pirmā acu uzmetiena,

891
00:41:59,790 --> 00:42:04,020
vienīgā lieta virzās
šī filma ir bišu.

892
00:42:04,020 --> 00:42:06,880
>> Kas ir mēms par uzglabāšanu
video nesaspiesti?

893
00:42:06,880 --> 00:42:11,420
Tas ir sava veida atkritumus, lai uzglabātu video
kā četras gandrīz identisku attēlus, kas

894
00:42:11,420 --> 00:42:13,670
atšķiras tikai tiktāl, ciktāl, ja bite ir.

895
00:42:13,670 --> 00:42:16,280
Jūs varat mest prom visvairāk
Šīs informācijas

896
00:42:16,280 --> 00:42:20,190
un atcerēties tikai, piemēram,
pirmais kadrs un pēdējais kadrs,

897
00:42:20,190 --> 00:42:22,180
galvenie kadri ja esat
kādreiz dzirdējis vārdu,

898
00:42:22,180 --> 00:42:24,337
un tikai Uzglabāt
vidus, kad bite ir.

899
00:42:24,337 --> 00:42:26,170
Un jums nav
uzglabāt visu rozā,

900
00:42:26,170 --> 00:42:28,330
un zilā, un
zaļās vērtības, kā arī.

901
00:42:28,330 --> 00:42:31,200
Tātad tas ir tikai teikt, ka
kompresija ir visur.

902
00:42:31,200 --> 00:42:34,900
Tas ir paņēmiens, mēs bieži izmantojam
vai par pašsaprotamu šajās dienās.

903
00:42:34,900 --> 00:42:38,750
>> Bet kā jūs saspiest tekstu?

904
00:42:38,750 --> 00:42:40,450
Kā jūs iet par saspiežot tekstu?

905
00:42:40,450 --> 00:42:45,410
Nu, katrs no rakstzīmju
Ascii ir viens baits, vai astoņi biti.

906
00:42:45,410 --> 00:42:47,360
Un tas ir sava veida mēms, vai ne?

907
00:42:47,360 --> 00:42:51,160
Tāpēc, ka jūs, iespējams, A tipa
un E un I un O un U daudz

908
00:42:51,160 --> 00:42:55,270
biežāk nekā, piemēram, W vai Q vai Z,
atkarībā no valodas, kurā

909
00:42:55,270 --> 00:42:56,610
jūs esat rakstiski noteikti.

910
00:42:56,610 --> 00:42:59,600
Un tad kāpēc mēs izmantojam
astoņi biti par katru vēstuli,

911
00:42:59,600 --> 00:43:02,040
ieskaitot vismaz
tautas vēstules, vai ne?

912
00:43:02,040 --> 00:43:05,300
Kāpēc ne izmantot mazāk bitus
super tautas burti,

913
00:43:05,300 --> 00:43:07,760
piemēram, E, lietas jūs uzminēt
pirmais Wheel of Fortune,

914
00:43:07,760 --> 00:43:10,450
un izmantot vairāk bitus
mazāk populāri burtiem?

915
00:43:10,450 --> 00:43:10,950
Kāpēc?

916
00:43:10,950 --> 00:43:13,130
Tāpēc, ka mēs esam tikai gatavojas
tos izmanto retāk.

917
00:43:13,130 --> 00:43:15,838
>> Nu, izrādās, ka tur ir
bijuši mēģinājumi veikti, lai to paveiktu.

918
00:43:15,838 --> 00:43:18,630
Un, ja jūs atceraties no pakāpes
skola vai vidusskola, Morse kodu.

919
00:43:18,630 --> 00:43:20,400
Morzes kods ir punkti
un domuzīmes, kas var būt

920
00:43:20,400 --> 00:43:24,270
pārraida pa vadiem, kā
skaņas vai signāli veida.

921
00:43:24,270 --> 00:43:25,930
Bet Morse kods ir super tīrs.

922
00:43:25,930 --> 00:43:29,010
Tas ir sava veida bināro sistēmas
ka jums ir punktiņi vai domuzīmes.

923
00:43:29,010 --> 00:43:30,977
Bet, ja jūs redzat, piemēram, divus punktus.

924
00:43:30,977 --> 00:43:33,810
Vai, ja jūs domājat, ka atpakaļ uz operatora
kas iet kā pīkstiens, pīkstiens, pīkstiens,

925
00:43:33,810 --> 00:43:36,760
pīkstiens, trāpot nedaudz sprūda
kas pārraida signālu,

926
00:43:36,760 --> 00:43:40,360
ja jums, saņēmējs, saņem divas
punkti, ko ziņa esat saņēmis?

927
00:43:40,360 --> 00:43:43,490
Pilnīgi patvaļīgi.

928
00:43:43,490 --> 00:43:44,450
>> Es?

929
00:43:44,450 --> 00:43:45,060
Es?

930
00:43:45,060 --> 00:43:47,500
Vai kas about-- vai es?

931
00:43:47,500 --> 00:43:49,570
Varbūt tas bija tikai divi E tiesības?

932
00:43:49,570 --> 00:43:52,480
Tātad tur ir šī problēma
no decodability ar Morse

933
00:43:52,480 --> 00:43:54,890
kods, saskaņā ar kuru, ja vien
Persona sūtīt jums ziņu

934
00:43:54,890 --> 00:43:59,510
faktiski ietur pauzi, lai jūs varētu kārtot
redzēt vai dzirdēt atšķirības starp burtiem,

935
00:43:59,510 --> 00:44:02,990
tas nav pietiekams tikai, lai
nosūtīt straumi no nullēm un tiem,

936
00:44:02,990 --> 00:44:05,610
vai punktiņi un svītriņas,
jo tur ir neskaidrība.

937
00:44:05,610 --> 00:44:08,640
E ir viens dot, tādēļ, ja jums
redzēt divus punktus vai dzirdēt divus punktus,

938
00:44:08,640 --> 00:44:11,254
varbūt tas ir divas E ir vai varbūt tas ir viens I.

939
00:44:11,254 --> 00:44:13,670
Tāpēc mums ir vajadzīga sistēma, kas ir
nedaudz vairāk gudrs nekā.

940
00:44:13,670 --> 00:44:16,851
Tātad cilvēks nosaukts Huffman gadi
pirms nāca klajā ar tieši to.

941
00:44:16,851 --> 00:44:18,600
Tātad mēs esam tikai gatavojas
veikt ātrs skatiens

942
00:44:18,600 --> 00:44:20,114
cik koki ir piederīgs šim.

943
00:44:20,114 --> 00:44:22,530
Pieņemsim, ka tas ir daži
stulba ziņa jūs vēlaties nosūtīt,

944
00:44:22,530 --> 00:44:26,342
šādā sastāvā tikai A, B, C ir D's un E s,
bet tur ir daudz no atlaišanas šeit.

945
00:44:26,342 --> 00:44:27,550
Tas nav domāts, lai būtu angļu valoda.

946
00:44:27,550 --> 00:44:28,341
Tas nav šifrēts.

947
00:44:28,341 --> 00:44:30,540
Tas ir tikai stulba ziņa
ar daudz atkārtošanās.

948
00:44:30,540 --> 00:44:34,010
Tātad, ja jūs faktiski rēķināties visus
A s, B s, C s, D's, un E ir, lūk,

949
00:44:34,010 --> 00:44:34,890
biežums.

950
00:44:34,890 --> 00:44:37,800
20% no burtiem ir
A s, 45% no burtiem

951
00:44:37,800 --> 00:44:39,660
ir E s, un trīs citas frekvences.

952
00:44:39,660 --> 00:44:41,960
Mēs saskaitījām tur manuāli
un tikko izdarīja math.

953
00:44:41,960 --> 00:44:44,579
>> Tātad izrādās, ka
Huffman, kādu laiku atpakaļ,

954
00:44:44,579 --> 00:44:46,620
sapratu, ka jūs zināt
ko, ja es sāktu ēkas

955
00:44:46,620 --> 00:44:51,172
koks, vai meža koku, ja jūs,
šādi, es varu darīt šādi.

956
00:44:51,172 --> 00:44:53,880
Es esmu gatavojas sniegt mezglu uz katru
no vēstulēm, kas man rūp

957
00:44:53,880 --> 00:44:55,530
un es esmu gatavojas glabāt
iekšpusē šī mezgla

958
00:44:55,530 --> 00:44:58,610
frekvences kā peldošā punkta
vērtība, vai jūs varētu izmantot to par N, pārāk,

959
00:44:58,610 --> 00:45:00,210
bet mēs tikai izmantot peldēt šeit.

960
00:45:00,210 --> 00:45:03,100
Un algoritms, kas
Viņš ierosināja, ka jūs

961
00:45:03,100 --> 00:45:07,210
šo mežu vienā mezglā
koki, tāpēc super īsi koki,

962
00:45:07,210 --> 00:45:11,920
un tu sāktu, kas savieno tos ar
jaunas grupas, jauni vecāki, ja Jums gribas.

963
00:45:11,920 --> 00:45:16,150
Un jūs to izdarītu, izvēloties
divi mazākie frekvences vienlaicīgi.

964
00:45:16,150 --> 00:45:18,110
Tāpēc es ņēma 10% un 10%.

965
00:45:18,110 --> 00:45:19,090
Izveidot jaunu mezglu.

966
00:45:19,090 --> 00:45:20,910
Un es aicinu jaunajam mezglā 20%.

967
00:45:20,910 --> 00:45:22,750
>> Kuriem divi punkti es apvienot nākamais?

968
00:45:22,750 --> 00:45:23,810
Tas ir nedaudz neskaidrs.

969
00:45:23,810 --> 00:45:26,643
Tātad tur ir daži stūru gadījumiem
apsvērt, bet, lai saglabātu lietas diezgan,

970
00:45:26,643 --> 00:45:29,300
Es esmu gatavojas izvēlēties 20% -
Es tagad ignorēt bērnus.

971
00:45:29,300 --> 00:45:33,640
Es esmu gatavojas izvēlēties 20% un
15% un izdarīt divus jaunus malas.

972
00:45:33,640 --> 00:45:35,624
Un tagad kuriem divi punkti
man loģiski apvienot?

973
00:45:35,624 --> 00:45:38,540
Ignorēt visus bērnus, visi
mazbērni, paskatieties saknēm

974
00:45:38,540 --> 00:45:39,070
tagad.

975
00:45:39,070 --> 00:45:42,220
Kuriem divi punkti man tie kopā?

976
00:45:42,220 --> 00:45:44,530
Divi Point un 0,35.

977
00:45:44,530 --> 00:45:45,890
Tāpēc ļaujiet man izdarīt divas jaunas šķautnes.

978
00:45:45,890 --> 00:45:47,570
Un tad es esmu tikai ieguva vienu pa kreisi.

979
00:45:47,570 --> 00:45:48,650
Tātad, šeit ir koks.

980
00:45:48,650 --> 00:45:51,160
Un tas ir bijis sagatavots apzināti
izskatīties veida diezgan,

981
00:45:51,160 --> 00:45:55,870
bet paziņo, ka malas ir
arī tika marķēti nulli un vienu.

982
00:45:55,870 --> 00:45:59,510
Tātad, visi no kreisās puses, malām ir nulle
patvaļīgi, bet konsekventi.

983
00:45:59,510 --> 00:46:01,170
Visas labās malas ir tie.

984
00:46:01,170 --> 00:46:05,070
>> Un tā, kādi Hoffman piedāvātā,
ja jūs vēlaties pārstāvēt B,

985
00:46:05,070 --> 00:46:10,080
nevis pārstāv numuru 66, kā
ASCII kas ir astoņas visu biti,

986
00:46:10,080 --> 00:46:13,360
Jūs zināt, ko, tikai veikalu
modelis nulle, nulle, nulle,

987
00:46:13,360 --> 00:46:17,030
nulle, jo tas ir ceļš
no mana koka, Mr Huffman koks,

988
00:46:17,030 --> 00:46:18,600
uz lapas no saknes.

989
00:46:18,600 --> 00:46:20,970
Ja vēlaties saglabāt
E, gluži pretēji, nav

990
00:46:20,970 --> 00:46:26,290
nosūtīt astoņi biti, kas pārstāv kādu E.
Tā vietā, nosūtīt kāda modelis bitiem?

991
00:46:26,290 --> 00:46:26,890
One.

992
00:46:26,890 --> 00:46:30,410
Un, kas ir jauka par šo ir
ka E ir populārākais vēstule,

993
00:46:30,410 --> 00:46:32,340
un jūs izmantojat
īsākais koda.

994
00:46:32,340 --> 00:46:34,090
Nākamais populārākais
vēstule izskatās kā tas

995
00:46:34,090 --> 00:46:37,380
bija A. Un tik cik bitus
viņš ierosina izmantot par to?

996
00:46:37,380 --> 00:46:38,270
Nulle, viens.

997
00:46:38,270 --> 00:46:41,060
>> Un tāpēc, ka tas ir īstenots
kā šo koku, tagad

998
00:46:41,060 --> 00:46:43,350
ļaujiet man noteikt, tur ir
nē neskaidrību kā Morse

999
00:46:43,350 --> 00:46:46,090
kods, jo visi
burti jums rūp

1000
00:46:46,090 --> 00:46:48,780
ir pēc tam, kad minētie malām.

1001
00:46:48,780 --> 00:46:50,580
Tātad tas ir tikai viens
piemērošana no koka.

1002
00:46:50,580 --> 00:46:52,538
Tas is-- un es ņemšu vilnis
mana roka pie šī, kā jūs

1003
00:46:52,538 --> 00:46:55,570
varētu to īstenotu kā C struktūru.

1004
00:46:55,570 --> 00:46:58,260
Mums ir nepieciešams, lai apvienotu
simbols, kā char,

1005
00:46:58,260 --> 00:46:59,910
un biežums, kas pa kreisi un pa labi.

1006
00:46:59,910 --> 00:47:02,510
Bet aplūkosim divus
nobeiguma piemēri, kas jums

1007
00:47:02,510 --> 00:47:06,070
iegūt diezgan pazīstams ar pēc
viktorīna nulle problēmu noteikti pieci.

1008
00:47:06,070 --> 00:47:09,210
>> Tātad tur ir datu struktūra
pazīstams kā hash tabulu.

1009
00:47:09,210 --> 00:47:12,247
Un hash tabulu, ir sava veida
atdzesē, ka tā ir kausi.

1010
00:47:12,247 --> 00:47:14,830
Un pieņemsim, ka tur ir četri kausi
šeit, tikai četras tukšas vietas.

1011
00:47:14,830 --> 00:47:20,830
Lūk kārtis, un šeit ir
klubs, lāpsta, klubs, dimanti, klubs,

1012
00:47:20,830 --> 00:47:25,960
dimanti, klubs, dimanti,
clubs-- tāpēc tas ir nejauši.

1013
00:47:25,960 --> 00:47:30,330
Sirdis, hearts-- tāpēc es esmu
bucketizing visas izejvielas šeit.

1014
00:47:30,330 --> 00:47:32,430
Un hash tabulu vajadzības
paskatīties uz savu ieguldījumu,

1015
00:47:32,430 --> 00:47:34,850
un pēc tam nodot to zināmu
vietu, pamatojoties uz to, ko jūs redzēt.

1016
00:47:34,850 --> 00:47:35,600
Tas ir algoritms.

1017
00:47:35,600 --> 00:47:37,980
Un man bija, izmantojot super
vienkāršs vizuālais algoritms.

1018
00:47:37,980 --> 00:47:40,030
Par cieta daļa no kuriem bija
atceroties kādi bildes bija.

1019
00:47:40,030 --> 00:47:41,590
Un tad tur ir četras kopējās lietas.

1020
00:47:41,590 --> 00:47:45,440
>> Tagad skursteņi tika pieaug, kas
ir apzināta dizaina lieta šeit.

1021
00:47:45,440 --> 00:47:46,540
Bet ko vēl varētu man darīt?

1022
00:47:46,540 --> 00:47:49,080
Tātad patiesībā šeit mums ir
ķekars vecās skolas eksāmenu grāmatas.

1023
00:47:49,080 --> 00:47:51,240
Pieņemsim, ka ķekars
studentiem vārdi ir šeit.

1024
00:47:51,240 --> 00:47:52,570
Lūk lielāks hash tabulu.

1025
00:47:52,570 --> 00:47:54,867
Tā vietā, četri kausi,
Man ir, teiksim 26.

1026
00:47:54,867 --> 00:47:57,950
Un mēs negribējām iet aizņemties 26
lietas no ārpuses [? Annenberg?], Tāpēc

1027
00:47:57,950 --> 00:48:00,289
šeit ir pieci, kas pārstāv
A līdz Z. Un, ja es

1028
00:48:00,289 --> 00:48:03,580
redzēt students, kura vārds sākas ar A,
Es esmu gatavojas īstenot savu viktorīna tur.

1029
00:48:03,580 --> 00:48:08,850
Ja kāds sāk ar C, tur,
A-- faktiski, nevēlējās to darīt.

1030
00:48:08,850 --> 00:48:10,060
B iet vairāk nekā šeit.

1031
00:48:10,060 --> 00:48:13,390
Tāpēc es esam ieguvuši A un B un C. And
Tagad šeit ir vēl viens students.

1032
00:48:13,390 --> 00:48:16,212
Bet, ja tas hash tabulā ir
īsteno ar masīvu,

1033
00:48:16,212 --> 00:48:17,920
Es esmu veida ieskrūvē
šajā brīdī, vai ne?

1034
00:48:17,920 --> 00:48:19,510
Es veida nepieciešams, lai šo kaut kur.

1035
00:48:19,510 --> 00:48:24,380
>> Tātad viens veids, kā es varētu atrisināt, tas ir, viss
labi, ir aizņemts, B ir aizņemts, C ir aizņemts.

1036
00:48:24,380 --> 00:48:28,880
Es esmu gatavojas nodot viņam D. Tātad
pirmkārt, man ir izlases tūlītēja piekļuve

1037
00:48:28,880 --> 00:48:31,064
uz katru kausu studentiem.

1038
00:48:31,064 --> 00:48:33,230
Bet tagad tas ir sava veida nodota
uz kaut ko lineāra,

1039
00:48:33,230 --> 00:48:36,750
jo, ja es gribu, lai meklētu kādu
kura vārds sākas ar A, es varētu pārbaudīt šeit.

1040
00:48:36,750 --> 00:48:38,854
Bet, ja tas nav A
students Es meklēju,

1041
00:48:38,854 --> 00:48:41,520
Es veida ir jāsāk pārbaudīt
spaiņiem, jo ​​tas, ko es darīju

1042
00:48:41,520 --> 00:48:44,530
bija sava veida lineāri
zonde datu struktūru.

1043
00:48:44,530 --> 00:48:47,710
Muļķīgs veids, kā pateikt tikai izskatās
par pirmo pieejamo atvēršanas,

1044
00:48:47,710 --> 00:48:51,850
un nodot kā plāna B, tā sakot,
vai plāns D šajā gadījumā vērtība

1045
00:48:51,850 --> 00:48:53,340
šajā vietā vietā.

1046
00:48:53,340 --> 00:48:56,470
Tas ir tikai tāpēc, ka, ja jūs esat
ieguva 26 vietas un neviens students

1047
00:48:56,470 --> 00:49:00,600
ar nosaukumu Q vai Z, vai kaut kas tamlīdzīgs
ka, vismaz jūs izmantojat telpu.

1048
00:49:00,600 --> 00:49:03,140
>> Bet mēs jau esam redzējuši vairāk
gudrs risinājumu šeit, vai ne?

1049
00:49:03,140 --> 00:49:04,870
Ko jūs darītu, nevis
ja jums ir sadursmi?

1050
00:49:04,870 --> 00:49:06,670
Ja divi cilvēki ir
nosaukums A, ko būtu

1051
00:49:06,670 --> 00:49:09,160
bijuši gudrāki vai vairāk
intuitīvi risinājums nekā tikai

1052
00:49:09,160 --> 00:49:12,840
Liekot kur D ir vajadzēja būt?

1053
00:49:12,840 --> 00:49:14,810
Kāpēc es tikai iet
ārpus [? Annenberg?],

1054
00:49:14,810 --> 00:49:19,960
piemēram malloc, citu mezglu, ielieciet to
šeit, un pēc tam nodot, ka students šeit.

1055
00:49:19,960 --> 00:49:22,120
Tāpēc, ka man būtībā ir
sava veida masīva,

1056
00:49:22,120 --> 00:49:25,590
vai varbūt vairāk eleganti, jo mēs esam
sāk redzēt saistīts sarakstu.

1057
00:49:25,590 --> 00:49:29,520
>> Un tāpēc hash tabulu ir struktūra
kas varētu izskatīties tāpat kā tas,

1058
00:49:29,520 --> 00:49:33,900
bet vairāk gudri, tu kaut ko sauc
atsevišķa ķēžu rādītāju, ar kuru hash tabulu

1059
00:49:33,900 --> 00:49:38,340
vienkārši ir masīvs, katrs no
kurā sastāvdaļas nav skaitlis,

1060
00:49:38,340 --> 00:49:40,470
pati ir saistīts saraksts.

1061
00:49:40,470 --> 00:49:45,080
Tā, ka jūs saņemsiet super ātri piekļūt
izlemjot, kur hash savu vērtību.

1062
00:49:45,080 --> 00:49:48,059
Daudz, piemēram, ar kartēm piemēram,
Es super ātri pieņemt lēmumus.

1063
00:49:48,059 --> 00:49:49,600
Hearts iet šeit, dimanti iet šeit.

1064
00:49:49,600 --> 00:49:52,180
Same Lūk, iet šeit,
D iet šeit, B iet šeit.

1065
00:49:52,180 --> 00:49:55,740
Tik super ātri meklēt-ups, un ja
tev gadās uzskriet lietu

1066
00:49:55,740 --> 00:49:59,429
kur jūs esat ieguvuši sadursmes, divi
cilvēki ar tādu pašu nosaukumu, arī tad

1067
00:49:59,429 --> 00:50:00,970
jūs vienkārši sākt saistot tos kopā.

1068
00:50:00,970 --> 00:50:03,900
Un varbūt jūs saglabātu tos sakārtoti
alfabētiskā secībā, varbūt jums nav.

1069
00:50:03,900 --> 00:50:05,900
Bet vismaz tagad mums ir dinamismu.

1070
00:50:05,900 --> 00:50:10,250
Tā, no vienas puses, mums ir super ātri
pastāvīgs laiks, un veida lineārā laika

1071
00:50:10,250 --> 00:50:14,110
iesaistīti ja šiem saistītas sarakstiem
sāk saņemt mazliet garš.

1072
00:50:14,110 --> 00:50:16,880
>> Tātad šāda veida dumjš,
geeky joks gadus atpakaļ.

1073
00:50:16,880 --> 00:50:19,590
Pie CS50 kapāt-a-Thon,
kad studenti pārbaudi,

1074
00:50:19,590 --> 00:50:22,040
daži TF vai CA katru gadu
domā, ka tas ir smieklīgi, lai safasēti

1075
00:50:22,040 --> 00:50:27,772
pazīme, piemēram, tas, kur tā vienkārši
nozīmē, ja jūsu vārds sākas ar A,

1076
00:50:27,772 --> 00:50:28,870
iet šo ceļu.

1077
00:50:28,870 --> 00:50:31,110
Ja jūsu vārds sākas
ar B, iet this-- OK,

1078
00:50:31,110 --> 00:50:33,290
tas ir smieklīgi, varbūt vēlāk semestrī.

1079
00:50:33,290 --> 00:50:36,420
Bet tur ir cita
veids, kā to izdarīt, too.

1080
00:50:36,420 --> 00:50:37,410
Nāciet atpakaļ uz to.

1081
00:50:37,410 --> 00:50:38,600
>> Tātad tur ir šī struktūra.

1082
00:50:38,600 --> 00:50:40,420
Un tas ir mūsu pēdējais
struktūra šodien,

1083
00:50:40,420 --> 00:50:42,400
kas ir kaut kas sauc trie.

1084
00:50:42,400 --> 00:50:47,140
T-R-I-E, kas kaut kādu iemeslu dēļ ir īss
izguves, bet to sauc trie.

1085
00:50:47,140 --> 00:50:51,389
Tātad trie ir vēl viens interesants
amalgama daudz šīm idejām.

1086
00:50:51,389 --> 00:50:52,930
Tas ir koks, ko mēs esam redzējuši iepriekš.

1087
00:50:52,930 --> 00:50:54,180
Tas nav bināro meklēšanas koku.

1088
00:50:54,180 --> 00:50:58,410
Tas ir koks ar jebkuru bērnu skaitu,
bet katrs no bērniem sistēmu TRIE

1089
00:50:58,410 --> 00:51:00,090
ir masīvs.

1090
00:51:00,090 --> 00:51:04,790
Masīvs izmēra, teiksim, 26 vai varbūt 27
ja jūs vēlaties, lai atbalstītu hyphenated nosaukumus

1091
00:51:04,790 --> 00:51:06,790
vai apostrofs cilvēku vārdiem.

1092
00:51:06,790 --> 00:51:08,280
>> Un tā tas ir datu struktūra.

1093
00:51:08,280 --> 00:51:10,290
Un, ja paskatās no augšas
uz leju, piemēram, ja jūs

1094
00:51:10,290 --> 00:51:13,710
apskatīt augšējā mezglā tur, M, ir
norādot uz galējo kreiso lieta tur,

1095
00:51:13,710 --> 00:51:17,665
kuru pēc tam, X, W, E, L, L. Tas ir
tikai datu struktūra, kas patvaļīgi

1096
00:51:17,665 --> 00:51:19,120
ir uzglabātu cilvēku vārdus.

1097
00:51:19,120 --> 00:51:25,720
Un Maxwell glabā tikai pēc
ceļš no masīva ar masīvu masīvs.

1098
00:51:25,720 --> 00:51:30,050
Bet kas ir pārsteidzošs apmēram trie ir
ka, tā kā saistīta sarakstu un pat

1099
00:51:30,050 --> 00:51:34,520
masīvs, labākais, ko mēs jebkad esam gotten ir
lineārais laiks vai logaritmisko laiks meklē

1100
00:51:34,520 --> 00:51:35,600
kāds up.

1101
00:51:35,600 --> 00:51:40,530
Šajā datu struktūrā TRIE, ja
mans datu struktūra ir viens vārds tajā

1102
00:51:40,530 --> 00:51:43,720
un es esmu meklē Maxwell, es esmu
gatavojas atrast viņam diezgan ātri.

1103
00:51:43,720 --> 00:51:47,910
Es tikai meklē M-A-X-W-E-L-L. Ja
šo datu struktūra, gluži pretēji,

1104
00:51:47,910 --> 00:51:51,830
ja N ir miljons, ja tur ir
miljons vārdi šajā datu struktūru,

1105
00:51:51,830 --> 00:51:57,100
Maxwell joprojām būs
redzamu pēc tikko M-A-X-W-E-L-L

1106
00:51:57,100 --> 00:51:58,090
soļi.

1107
00:51:58,090 --> 00:52:01,276
Un David-- D-A-V-I-D soļus.

1108
00:52:01,276 --> 00:52:03,400
Citiem vārdiem sakot, veidojot
datu struktūra, kas ir

1109
00:52:03,400 --> 00:52:07,240
got visi no šiem blokiem, kas visi
paši atbalstīt brīvpieejas,

1110
00:52:07,240 --> 00:52:11,090
Es varu sākt meklēt up Tautas
nosaukt izmantojot laiku, kas ir

1111
00:52:11,090 --> 00:52:14,340
proporcionāls nevis numuru
no lietas datu struktūru,

1112
00:52:14,340 --> 00:52:16,330
kā miljons esošie nosaukumi.

1113
00:52:16,330 --> 00:52:20,135
Par laiku, kas nepieciešams, lai es atrastu summa
M-A-X-W-E-L-L šajā datu struktūra ir

1114
00:52:20,135 --> 00:52:22,260
proporcionāls nevis uz
izmērs no datu struktūru,

1115
00:52:22,260 --> 00:52:25,930
bet ar garumu nosaukuma.

1116
00:52:25,930 --> 00:52:28,440
Un reāli
nosaukumi mēs meklējam up

1117
00:52:28,440 --> 00:52:29,970
nekad būs traks garš.

1118
00:52:29,970 --> 00:52:32,600
Varbūt kādam ir 10 raksturs
nosaukt, 20 rakstzīmju nosaukumu.

1119
00:52:32,600 --> 00:52:33,900
Tas, protams, ierobežots, vai ne?

1120
00:52:33,900 --> 00:52:37,110
Ir cilvēks uz Zemes, kas
ir pēc iespējas garāku vārdu,

1121
00:52:37,110 --> 00:52:39,920
bet šis nosaukums ir nemainīga
vērtība garums, vai ne?

1122
00:52:39,920 --> 00:52:41,980
Tas nemainās nekādā ziņā.

1123
00:52:41,980 --> 00:52:45,090
Tātad šādā veidā, mēs esam
sasniegusi datu struktūra

1124
00:52:45,090 --> 00:52:47,800
tas ir nemainīgs laika meklēt-up.

1125
00:52:47,800 --> 00:52:50,670
Tas veikt vairākus soļus
atkarībā no tā garuma ievadi,

1126
00:52:50,670 --> 00:52:54,250
bet ne skaits nosaukuma
datu struktūrā,.

1127
00:52:54,250 --> 00:52:58,700
Tātad, ja mēs dubultu skaitu nosaukumiem
nākamgad no miljards līdz diviem miljardiem,

1128
00:52:58,700 --> 00:53:03,720
secinājums Maxwell gatavojas veikt
tieši tādu pašu numuru septiņi soļi

1129
00:53:03,720 --> 00:53:04,650
lai atrastu viņu.

1130
00:53:04,650 --> 00:53:08,810
Un tā mēs, šķiet, esam sasnieguši
Mūsu svēts grail darba laika.

1131
00:53:08,810 --> 00:53:10,860
>> Tātad pāris ātri paziņojumiem.

1132
00:53:10,860 --> 00:53:11,850
Viktorīna nulle nāk uz augšu.

1133
00:53:11,850 --> 00:53:14,600
Vairāk par ka par kursu mājas lapā
nākamo pāris dienu laikā.

1134
00:53:14,600 --> 00:53:17,120
Pirmdiena lecture-- tas ir brīvdiena
šeit Hārvardā pirmdien.

1135
00:53:17,120 --> 00:53:18,850
Tas nav New Haven,
tāpēc mēs esam ņemot klasi

1136
00:53:18,850 --> 00:53:20,310
New Haven par lekciju pirmdien.

1137
00:53:20,310 --> 00:53:22,550
Viss tiks filmēts
un noskatīties tiešraidē, kā ierasts,

1138
00:53:22,550 --> 00:53:24,900
bet pieņemsim beidzas šodien
ar 30 sekunžu klipu

1139
00:53:24,900 --> 00:53:26,910
saucamie "Deep Domas"
ar Daven Farnham, kas

1140
00:53:26,910 --> 00:53:30,850
iedvesmoja pagājušajā gadā līdz sestdienai
Night Live s "Deep Domas"

1141
00:53:30,850 --> 00:53:35,700
Jack, ērts, kas
tagad būtu jēga.

1142
00:53:35,700 --> 00:53:38,810
>> FILM: Un tagad, "Deep
Domas "ar Daven Farnham.

1143
00:53:38,810 --> 00:53:42,100

1144
00:53:42,100 --> 00:53:42,870
Hash tabulu.

1145
00:53:42,870 --> 00:53:45,940

1146
00:53:45,940 --> 00:53:47,660
>> SPEAKER 1: Labi, tas arī tagad.

1147
00:53:47,660 --> 00:53:48,805
Redzēsim tevi nākamnedēļ.

1148
00:53:48,805 --> 00:53:55,380

1149
00:53:55,380 --> 00:53:56,680
>> Doug: Lai redzētu to darbībā.

1150
00:53:56,680 --> 00:53:58,304
Tātad, pieņemsim to apskatīt, kas tieši tagad.

1151
00:53:58,304 --> 00:53:59,890
Tātad šeit, mums ir nešķirotas masīvs.

1152
00:53:59,890 --> 00:54:04,860
>> IAN: Doug, jūs varat iet uz priekšu un restart
tas tikai vienu sekundi, lūdzu.

1153
00:54:04,860 --> 00:54:08,562
Labi, kameras ir ritošā, tāpēc
darbība, kad jūs esat gatavs, Doug, OK?

1154
00:54:08,562 --> 00:54:11,020
Doug: Labi, lai to, ko mēs
ir šeit ir nešķirotas masīvs.

1155
00:54:11,020 --> 00:54:13,960
Un es esmu krāsainu visi elementi
sarkans, lai norādītu, ka tas ir, faktiski,

1156
00:54:13,960 --> 00:54:14,460
nešķiroti.

1157
00:54:14,460 --> 00:54:17,960
Tik atceros, ka pirmā lieta, ko mēs darām
ir mēs sakārtot kreiso pusi no masīva.

1158
00:54:17,960 --> 00:54:20,630
Tad mēs kārtot tiesības
puse no masīva.

1159
00:54:20,630 --> 00:54:22,830
Un ya-da, ya-da, ya-da,
mēs apvienot tos kopā.

1160
00:54:22,830 --> 00:54:24,520
Un mums ir pilnīgi sakārtoti masīvs.

1161
00:54:24,520 --> 00:54:25,360
Tātad tas, kā apvienot veida darbi.

1162
00:54:25,360 --> 00:54:27,109
>> IAN: Paga, paga, paga,
sagriezti, sagriezti, sagriezti, sagriezti.

1163
00:54:27,109 --> 00:54:30,130
Doug, jūs varat ne tikai ya-da, ya-da,
Ya-da, savu ceļu caur sapludināšanas kārtošanas.

1164
00:54:30,130 --> 00:54:31,970
>> Doug: Es tikko izdarīja.

1165
00:54:31,970 --> 00:54:32,832
Ir labi.

1166
00:54:32,832 --> 00:54:33,540
Mēs esam labi iet.

1167
00:54:33,540 --> 00:54:34,760
Pieņemsim tikai glabāt velmēšanas.

1168
00:54:34,760 --> 00:54:35,380
So anyway,

1169
00:54:35,380 --> 00:54:37,800
>> IAN: Jums ir, lai izskaidrotu
tā pilnīgāk nekā.

1170
00:54:37,800 --> 00:54:39,999
Tas ir vienkārši nav pietiekami.

1171
00:54:39,999 --> 00:54:41,790
Doug: Ian, mums nav
ir nepieciešams, lai dotos atpakaļ uz vienu.

1172
00:54:41,790 --> 00:54:42,350
Ir labi.

1173
00:54:42,350 --> 00:54:45,690
So anyway, ja mēs turpināsim ar merge--
Ian, mēs esam vidū filmēšanas.

1174
00:54:45,690 --> 00:54:46,612
>> IAN: Es zinu.

1175
00:54:46,612 --> 00:54:49,320
Un mēs varam ne tikai ya-da, ya-da,
Ya-da, cauri visam procesam.

1176
00:54:49,320 --> 00:54:52,200
Jums ir paskaidrot, kā
Abas puses saņemt apvienojās kopā.

1177
00:54:52,200 --> 00:54:53,570
>> Doug: Bet mēs jau esam
paskaidroja, kā divi sides--

1178
00:54:53,570 --> 00:54:55,321
>> IAN: Jūs esat tikko parādīts
viņus apvienot masīvs.

1179
00:54:55,321 --> 00:54:56,486
Doug: Viņi zina procesu.

1180
00:54:56,486 --> 00:54:57,172
Viņi labi.

1181
00:54:57,172 --> 00:54:58,380
Mēs esam aizgājuši pār to desmit reizes.

1182
00:54:58,380 --> 00:55:00,330
>> IAN: Jūs vienkārši izlaidis tiesības pār to.

1183
00:55:00,330 --> 00:55:03,360
Mēs ejam atpakaļ uz vienu, jums
nevar tu ya-da, ya-da pār to.

1184
00:55:03,360 --> 00:55:05,480
Labi, atpakaļ uz vienu.

1185
00:55:05,480 --> 00:55:07,833
>> Doug: man ir jāiet atpakaļ
cauri visiem slaidiem?

1186
00:55:07,833 --> 00:55:08,332
Mans Dievs.

1187
00:55:08,332 --> 00:55:11,008

1188
00:55:11,008 --> 00:55:13,004
Tas ir tāpat kā sesto reizi, Ian.

1189
00:55:13,004 --> 00:55:13,940
Ir labi.

1190
00:55:13,940 --> 00:55:15,200
>> IAN: Nu labi.

1191
00:55:15,200 --> 00:55:16,590
Esat gatavi?

1192
00:55:16,590 --> 00:55:17,400
Liels.

1193
00:55:17,400 --> 00:55:18,950
Darbība.