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

2
00:00:10,900 --> 00:00:15,860
>> SPEAKER 1: Добре, така че това е
CS50 Това е краят на пет седмици.

3
00:00:15,860 --> 00:00:19,220
И припомни, че за последен път сме
Започнах да търся в красиви данните

4
00:00:19,220 --> 00:00:22,310
структури, които са започнали да се реши
проблеми, които започнаха да се въведат

5
00:00:22,310 --> 00:00:25,640
нови проблеми, но ключът към това
беше от резби, че ние

6
00:00:25,640 --> 00:00:27,940
Започнах да правя от възел до възел.

7
00:00:27,940 --> 00:00:30,085
Така че това, разбира се,
с единична свързан списък.

8
00:00:30,085 --> 00:00:31,960
И от поединично свързани,
Искам да кажа, че има само един

9
00:00:31,960 --> 00:00:33,380
резба между всеки от тези възли.

10
00:00:33,380 --> 00:00:35,890
Оказва се, можете да го направите по-красиви
неща като двойно свързани списъци

11
00:00:35,890 --> 00:00:38,470
с което имате стрела
ще и в двете посоки, което

12
00:00:38,470 --> 00:00:40,320
може да помогне с някои ефективност.

13
00:00:40,320 --> 00:00:42,000
Но това реши проблема?

14
00:00:42,000 --> 00:00:43,500
Какъв проблем е това реши?

15
00:00:43,500 --> 00:00:46,620
Защо ни е грижа в понеделник?

16
00:00:46,620 --> 00:00:49,820
Защо, на теория, е ни е грижа в понеделник?

17
00:00:49,820 --> 00:00:50,630
Какво прави?

18
00:00:50,630 --> 00:00:51,950
>> АУДИТОРИЯ: Ние динамично да го преоразмерите.

19
00:00:51,950 --> 00:00:53,740
>> SPEAKER 1: OK, за да можем да
динамично преоразмеряване.

20
00:00:53,740 --> 00:00:54,710
Браво и на двама ви.

21
00:00:54,710 --> 00:00:57,560
Така че можете да промените размера на това динамично
структура на данните, като има предвид, масив,

22
00:00:57,560 --> 00:01:00,760
Спомнете си, вие трябва да знаете
априори колко място искате

23
00:01:00,760 --> 00:01:03,870
и ако имате нужда от малко по-
космоса, вие сте вид на късмет.

24
00:01:03,870 --> 00:01:05,560
Трябва да се създаде изцяло нов масив.

25
00:01:05,560 --> 00:01:07,893
Трябва да се преместите всичките си
данни от един на друг,

26
00:01:07,893 --> 00:01:10,600
в крайна сметка освободи стария масив
ако можеш, и след това да продължи.

27
00:01:10,600 --> 00:01:13,891
Което просто се чувства много скъпо и много
неефективно, а всъщност тя може да бъде.

28
00:01:13,891 --> 00:01:14,890
Но това не е всичко добро.

29
00:01:14,890 --> 00:01:18,180
Ние плащаме на цената, това, което беше едно
от по-очевидните цени ние

30
00:01:18,180 --> 00:01:20,550
плащат с помощта на свързан списък?

31
00:01:20,550 --> 00:01:22,825
>> АУДИТОРИЯ: Трябва да използваме
двойно пространство за всеки един.

32
00:01:22,825 --> 00:01:25,200
SPEAKER 1: Да, така че ние трябва
най-малко два пъти по-голямо пространство.

33
00:01:25,200 --> 00:01:27,700
В действителност, аз осъзнах, тази картина е
дори малко подвеждащо,

34
00:01:27,700 --> 00:01:32,200
защото на CS50 IDE в много модерна
компютри, указател или адрес

35
00:01:32,200 --> 00:01:33,700
не е в действителност четири байта.

36
00:01:33,700 --> 00:01:36,090
Това е много често това
осем дни байта, които

37
00:01:36,090 --> 00:01:38,530
означава най-долната
правоъгълници там в реалност

38
00:01:38,530 --> 00:01:40,900
са вид два пъти по-
голям, колкото това, което съм, изготвен,

39
00:01:40,900 --> 00:01:44,409
което означава, че използвате три пъти по-
толкова място, колкото можем да имаме друго.

40
00:01:44,409 --> 00:01:46,700
Сега в същото време, ние сме
още говорим байта, нали?

41
00:01:46,700 --> 00:01:49,140
Ние не говорим задължително
мегабайта или гигабайта,

42
00:01:49,140 --> 00:01:51,000
освен ако тези данни структури получават големи.

43
00:01:51,000 --> 00:01:54,510
>> И така, днес ние започваме да се разгледа
как можем да проучи данните

44
00:01:54,510 --> 00:01:57,310
по-ефективно, ако в
Всъщност данните получава по-голяма.

45
00:01:57,310 --> 00:02:00,360
Но нека се опитаме да канонизира
операциите първите

46
00:02:00,360 --> 00:02:02,460
което можете да направите за тях
видове структури от данни.

47
00:02:02,460 --> 00:02:04,790
Така че нещо като свързани
списък по принцип подкрепя

48
00:02:04,790 --> 00:02:07,514
операции искали да изтриете,
вмъкнете, и търсене.

49
00:02:07,514 --> 00:02:08,639
И това, което мога да кажа от това?

50
00:02:08,639 --> 00:02:11,222
Това просто означава, че обикновено,
ако хората използват свързан списък,

51
00:02:11,222 --> 00:02:14,287
те или някой друг е изпълнила
функции като изтриване, вмъкване,

52
00:02:14,287 --> 00:02:16,120
и търсене, така че можете да
всъщност направи нещо

53
00:02:16,120 --> 00:02:18,030
полезна със структурата на данните.

54
00:02:18,030 --> 00:02:20,760
Така че нека да хвърлим един бърз поглед
как бихме могли да приложат

55
00:02:20,760 --> 00:02:24,530
някои код за свързан списък, както следва.

56
00:02:24,530 --> 00:02:27,885
>> Така че това е само част C код,
дори не е пълна програма

57
00:02:27,885 --> 00:02:29,260
че аз наистина бързо разбита.

58
00:02:29,260 --> 00:02:32,300
Това не е онлайн в разпределението
код, защото той всъщност няма да се изпълнява.

59
00:02:32,300 --> 00:02:33,790
Но забележете аз току-що
с коментар каза,

60
00:02:33,790 --> 00:02:36,130
точка точка точка, има нещо
там, точка, точка точка, нещо там.

61
00:02:36,130 --> 00:02:38,410
И нека просто погледнете
какви са сочни части.

62
00:02:38,410 --> 00:02:40,790
Така на третия ред
Припомняме, че това сега е

63
00:02:40,790 --> 00:02:45,960
Ние предложихме за обявяване на последния възел
време, един от тези правоъгълни обекти.

64
00:02:45,960 --> 00:02:48,790
Той разполага с инт, че ние ще се обадя на N,
но можем да го наречем нещо,

65
00:02:48,790 --> 00:02:51,920
и след това звезда структура на възел, наречен по-нататък.

66
00:02:51,920 --> 00:02:55,520
И само за да бъде ясно, че втората
линия, по линия на шест, какво е това?

67
00:02:55,520 --> 00:02:57,930
Какво е да го прави за нас?

68
00:02:57,930 --> 00:03:01,044
Тъй като това със сигурност изглежда по-
загадъчен, отколкото обичайните ни променливи.

69
00:03:01,044 --> 00:03:02,740
>> АУДИТОРИЯ: Това го прави движат над милион.

70
00:03:02,740 --> 00:03:04,650
>> SPEAKER 1: Това го прави движат над милион.

71
00:03:04,650 --> 00:03:08,580
И за да бъдем по-точни,
тя ще се съхранява на адрес

72
00:03:08,580 --> 00:03:11,582
на възела, който е трябвало да бъде
семантично до него, нали?

73
00:03:11,582 --> 00:03:13,540
Така че това няма да
задължително се движи нищо.

74
00:03:13,540 --> 00:03:15,290
Това е просто ще
съхраняване на стойност, която е

75
00:03:15,290 --> 00:03:17,170
ще бъде на адреса
от друга възлова точка,

76
00:03:17,170 --> 00:03:20,810
и затова сме казвали структура на
възел звезда, звездата, обозначаващ

77
00:03:20,810 --> 00:03:22,370
указател или адрес.

78
00:03:22,370 --> 00:03:26,390
ОК, така че сега, ако приемем, че имаме
това N достъпна за нас, и нека

79
00:03:26,390 --> 00:03:29,490
Предполагам, че някой друг има
Създава цял куп числа

80
00:03:29,490 --> 00:03:30,400
в свързан списък.

81
00:03:30,400 --> 00:03:35,640
И това е свързан списък
, посочи от някакъв момент

82
00:03:35,640 --> 00:03:39,040
променлива, наречена списък, който е
преминал тук като параметър,

83
00:03:39,040 --> 00:03:43,120
как мога да отида за съответствие
14 изпълнителните търсене?

84
00:03:43,120 --> 00:03:45,990
С други думи, ако аз съм прилагане
функция, чиято цел в живота

85
00:03:45,990 --> 00:03:48,889
е да се вземе едно цяло число, а след това
започваща на свързан списък,

86
00:03:48,889 --> 00:03:50,430
че е указател към свързан списък.

87
00:03:50,430 --> 00:03:52,992
Подобно на първия, който мисля, че David
беше нашият доброволец в понеделник,

88
00:03:52,992 --> 00:03:54,700
Той сочеше
целият свързан списък,

89
00:03:54,700 --> 00:03:57,820
това е така, сякаш сме минаваща
David в нашия аргумент, както тук.

90
00:03:57,820 --> 00:03:59,990
Как да отида за преминаващи този списък?

91
00:03:59,990 --> 00:04:04,640
Е, оказва се, че въпреки че
указатели са сравнително нови сега за нас,

92
00:04:04,640 --> 00:04:07,010
можем да направим това относително
прямо.

93
00:04:07,010 --> 00:04:09,500
>> Отивам да вървим напред и да
Декларирам временна променлива, която

94
00:04:09,500 --> 00:04:12,364
по условие е просто ще
да се нарича указател, или PTR,

95
00:04:12,364 --> 00:04:14,030
но бихте могли да го наречем всичко, което искаш.

96
00:04:14,030 --> 00:04:16,470
И аз отивам да се инициализира
да началото на списъка.

97
00:04:16,470 --> 00:04:20,050
Така че можете да вид мислите за това
като мен учителят на другия ден,

98
00:04:20,050 --> 00:04:23,580
вид сочеше някого
сред нашите хора като доброволци.

99
00:04:23,580 --> 00:04:26,470
Така че аз съм временна променлива, която е
Просто посочи към едно и също нещо

100
00:04:26,470 --> 00:04:31,390
че нашата случайно име
доброволец Давид също се посочва.

101
00:04:31,390 --> 00:04:35,440
Сега, докато показалеца е
не нула, защото изземване

102
00:04:35,440 --> 00:04:40,350
че нищожна е някакъв специален часовой стойност
разграничава на края на списъка

103
00:04:40,350 --> 00:04:44,280
така че, докато аз не съм сочейки
земята като последната ни доброволец

104
00:04:44,280 --> 00:04:47,190
е, да вървим напред
и направете следното.

105
00:04:47,190 --> 00:04:51,820
Ако pointer-- и сега аз искам вид
да направи това, което направихме със студента

106
00:04:51,820 --> 00:04:57,410
structure-- ако показалеца точка до
equals---скоро, ако показалеца точка N е равно на

107
00:04:57,410 --> 00:05:02,290
равно на променлива N, на
аргумент, който е бил приет през,

108
00:05:02,290 --> 00:05:05,370
След това искам да отида напред
и да кажа върнете вярно.

109
00:05:05,370 --> 00:05:11,020
Аз не съм намерил на номер N вътре
един от възлите на моя свързан списък.

110
00:05:11,020 --> 00:05:13,500
Но точката вече не
работи в този контекст,

111
00:05:13,500 --> 00:05:17,260
защото показалеца, PTR, е
Наистина указател, на един адрес,

112
00:05:17,260 --> 00:05:20,632
ние всъщност може чудесно
използвате най-накрая парче синтаксис

113
00:05:20,632 --> 00:05:22,590
този вид марки
интуитивно усещане и действително

114
00:05:22,590 --> 00:05:27,870
използвате стрелка тук, което означава, отидете от
този адрес до цяло число има вътре.

115
00:05:27,870 --> 00:05:30,160
Така че това е много подобен на
дух на оператора на точка,

116
00:05:30,160 --> 00:05:33,860
но тъй като показалка не е указател
а не самата структура на действителната,

117
00:05:33,860 --> 00:05:35,380
ние просто използвайте стрелката.

118
00:05:35,380 --> 00:05:40,620
>> Така че, ако текущия възел, че Аз,
временна променлива, съм сочеше

119
00:05:40,620 --> 00:05:43,060
Не е N, какво искам да направя?

120
00:05:43,060 --> 00:05:45,910
Е, с моите хора доброволци
че имахме тук онзи ден,

121
00:05:45,910 --> 00:05:49,710
ако първият ми от човека, не е тази, която
искам, а може би и на втория човекът не е

122
00:05:49,710 --> 00:05:52,660
този, аз искам, а третият, I
трябва да се запази физическо преместване.

123
00:05:52,660 --> 00:05:54,690
Подобно как мога да се оттегли през списък?

124
00:05:54,690 --> 00:05:57,470
Когато трябваше масив вас,
Просто ми хареса I плюс плюс.

125
00:05:57,470 --> 00:06:03,660
Но в този случай е достатъчно да се
направя показалеца, получава, показалеца, следващата.

126
00:06:03,660 --> 00:06:07,580
С други думи, в следващото поле
е като всички останали ръцете на

127
00:06:07,580 --> 00:06:10,880
че нашите хора доброволци в понеделник
използваше да отбележа в някакъв друг възел.

128
00:06:10,880 --> 00:06:12,890
Това бяха следващите техните съседи.

129
00:06:12,890 --> 00:06:17,060
>> Така че, ако искам да преминете през този списък,
Не мога просто да направя аз, плюс плюс вече,

130
00:06:17,060 --> 00:06:20,120
Аз трябва да кажа, вместо
I, показалеца, ще

131
00:06:20,120 --> 00:06:24,650
да се изравни каквото следващото поле е,
следващото поле се, следващото поле е,

132
00:06:24,650 --> 00:06:28,350
след всички тези оставили ръцете
че имахме на сцената посочващо

133
00:06:28,350 --> 00:06:30,000
някои следващите стойности.

134
00:06:30,000 --> 00:06:32,590
И ако аз се измъкне сам
че цялата итерация,

135
00:06:32,590 --> 00:06:39,330
и накрая, аз удари нула не се налага
намерено N все пак, аз просто се върнете фалшива.

136
00:06:39,330 --> 00:06:44,100
Така че отново, всичко, което правим тук,
по картината преди малко,

137
00:06:44,100 --> 00:06:47,840
започва от сочейки
началото на списъка се предполага.

138
00:06:47,840 --> 00:06:50,970
И тогава аз се провери, е стойността
Търся равен на девет?

139
00:06:50,970 --> 00:06:52,650
Ако е така, аз се върнете вярно и аз съм свършен.

140
00:06:52,650 --> 00:06:56,450
Ако не, да актуализирам моята ръка,
AKA показалеца, за да посоча

141
00:06:56,450 --> 00:06:59,540
на място при следващата стрелка, а
След това на мястото на следващия стрелата,

142
00:06:59,540 --> 00:07:00,480
и на следващия.

143
00:07:00,480 --> 00:07:03,770
Аз съм просто се разхождах из този масив.

144
00:07:03,770 --> 00:07:06,010
>> Така че отново, на кого му пука?

145
00:07:06,010 --> 00:07:07,861
Подобно на това, което е тази съставка за?

146
00:07:07,861 --> 00:07:10,360
Е, Припомняме, че ние въведохме
понятието за комин, който

147
00:07:10,360 --> 00:07:15,400
е тип абстрактен данни, доколкото това е
не нещо C, това не е нещо CS50,

148
00:07:15,400 --> 00:07:19,430
това е една абстрактна идея, тази идея за
подреждане неща на върха на един друг

149
00:07:19,430 --> 00:07:21,820
които могат да бъдат приложени в
гроздове с различни начини.

150
00:07:21,820 --> 00:07:25,600
И един начин ние предложихме беше с
масив, или с свързан списък.

151
00:07:25,600 --> 00:07:29,570
И се оказва, че е канонично, а
стак поддържа най-малко две операции.

152
00:07:29,570 --> 00:07:32,320
И бръмча думи са бута, да
бутнете нещо върху купчината,

153
00:07:32,320 --> 00:07:34,770
като нова тава в
зала за хранене, или поп,

154
00:07:34,770 --> 00:07:39,000
което означава да се премахне най-горния
тава от комина в трапезарията

155
00:07:39,000 --> 00:07:41,500
антре, а след това може би някои
други операции, както добре.

156
00:07:41,500 --> 00:07:45,770
Е, как може да определим структурата
че ние сме вече призова комин?

157
00:07:45,770 --> 00:07:50,020
>> Е, ние имаме всичко на изискваните
синтаксис, с които разполагаме в C. казвам,

158
00:07:50,020 --> 00:07:53,830
ми даде определение тип
една структура на вътрешната страна на комин,

159
00:07:53,830 --> 00:07:58,030
Отивам да се каже, е масив, на
цял куп номера и след това размер.

160
00:07:58,030 --> 00:08:00,930
Така че, с други думи, ако искам
да приложи това в кода,

161
00:08:00,930 --> 00:08:03,830
нека отида и просто вид
изготвят какво казва.

162
00:08:03,830 --> 00:08:06,317
Така че това казва, дайте ми
структура, която има масив,

163
00:08:06,317 --> 00:08:09,400
и аз не знам какво е капацитет,
това е очевидно някои постоянно, че съм

164
00:08:09,400 --> 00:08:10,858
определено на друго място, и това е добре.

165
00:08:10,858 --> 00:08:15,260
Но предполагам, че това е само една,
две, три, четири, пет.

166
00:08:15,260 --> 00:08:16,700
Така капацитет е 5.

167
00:08:16,700 --> 00:08:21,730
Този елемент вътре в моето
структура ще се нарича номера.

168
00:08:21,730 --> 00:08:24,020
И тогава ми е такъв
друга променлива очевидно

169
00:08:24,020 --> 00:08:27,814
нарича размер, който първоначално Отивам
да се предвиди се инициализира на нула.

170
00:08:27,814 --> 00:08:29,730
Ако няма нищо в
стека, размерът е нула,

171
00:08:29,730 --> 00:08:31,420
и това е боклук стойности в цифри.

172
00:08:31,420 --> 00:08:33,450
Нямам представа какво е там, просто все още.

173
00:08:33,450 --> 00:08:36,059
>> Така че, ако искам да бутнете
нещо, върху купчината,

174
00:08:36,059 --> 00:08:40,780
Предполагам, че аз наричам функция тласък, и
Казвам бутнете 50, като броят на 50 г.

175
00:08:40,780 --> 00:08:44,090
където бихте предложили
Аз го привлече в този масив?

176
00:08:44,090 --> 00:08:47,124
Има пет различни възможни отговори.

177
00:08:47,124 --> 00:08:48,790
Къде искаш да прокара броя 50?

178
00:08:48,790 --> 00:08:51,899
Ако целта тук, отново, обадете се на
функция да бута, да премине в спор

179
00:08:51,899 --> 00:08:52,940
на 50, къде мога да го сложите?

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

181
00:08:55,680 --> 00:08:59,052
Пет possible-- 20% шанс
на познае правилно.

182
00:08:59,052 --> 00:08:59,896
Да?

183
00:08:59,896 --> 00:09:00,740
>> АУДИТОРИЯ: Far полето.

184
00:09:00,740 --> 00:09:01,990
>> SPEAKER 1: Far полето.

185
00:09:01,990 --> 00:09:08,359
Сега има 25% шанс
на познае правилно.

186
00:09:08,359 --> 00:09:09,650
Така че всъщност ще се оправи.

187
00:09:09,650 --> 00:09:12,770
По конвенция, аз ще кажа с масив,
ние обикновено ще започне в ляво,

188
00:09:12,770 --> 00:09:14,519
но ние със сигурност може да
започне в правото.

189
00:09:14,519 --> 00:09:17,478
Така че спойлера тук би било съм
Вероятно ще го привлече в ляво,

190
00:09:17,478 --> 00:09:20,060
точно като в нормален масив, където
Започвам да отида наляво надясно.

191
00:09:20,060 --> 00:09:21,780
Но ако можете да флип
аритметиката, глоба.

192
00:09:21,780 --> 00:09:23,060
Това просто не е конвенционална.

193
00:09:23,060 --> 00:09:24,880
OK, аз трябва да се направи една
повече промяна все пак.

194
00:09:24,880 --> 00:09:27,710
Сега, когато съм бутна нещо
върху комина, какво следва?

195
00:09:27,710 --> 00:09:29,400
>> Добре, аз трябва да увеличите размера.

196
00:09:29,400 --> 00:09:32,600
Така че нека да вървим напред и просто
актуализира това, което е нула.

197
00:09:32,600 --> 00:09:35,950
И вместо сега, аз ще съм
да се сложи в стойността една.

198
00:09:35,950 --> 00:09:39,460
И сега предполагам, че бутнете друг
номер върху купчината, като 51.

199
00:09:39,460 --> 00:09:42,680
Е, аз трябва да се направи една по-
промяна, която е до размера на две.

200
00:09:42,680 --> 00:09:46,100
И тогава аз предполагам, натиснете още един
номер върху купчината като 61,

201
00:09:46,100 --> 00:09:52,530
Сега имам нужда да се актуализира размера още един
време, и да получите стойността 3 като размера.

202
00:09:52,530 --> 00:09:54,690
И сега предполагам, аз наричам поп.

203
00:09:54,690 --> 00:09:57,250
Сега поп, по силата на споразумение,
не взема един аргумент.

204
00:09:57,250 --> 00:10:00,430
С стак, той като цяло
точка на тава метафората

205
00:10:00,430 --> 00:10:03,450
е, че не е нужно усмотрение
да отиде получи, че тава, всичко, което може да направи

206
00:10:03,450 --> 00:10:06,330
се появи най-горната един от
стека, само защото.

207
00:10:06,330 --> 00:10:08,010
Това е, което тази структура от данни прави.

208
00:10:08,010 --> 00:10:12,250
>> Така че по тази логика, ако аз
казват поп, това, което идва на разстояние?

209
00:10:12,250 --> 00:10:13,080
Така 61.

210
00:10:13,080 --> 00:10:15,402
Така че това, което наистина е на компютъра
ще направим в памет?

211
00:10:15,402 --> 00:10:16,610
Какво ми код трябва да направя?

212
00:10:16,610 --> 00:10:20,330
Какво бихте предложили
сменяме на екрана?

213
00:10:20,330 --> 00:10:23,410
Какво трябва да се промени?

214
00:10:23,410 --> 00:10:24,960
Съжаляваме?

215
00:10:24,960 --> 00:10:26,334
Така че ние се отървете от 61.

216
00:10:26,334 --> 00:10:27,500
Така че определено мога да направя това.

217
00:10:27,500 --> 00:10:28,640
И мога да се отърва от 61.

218
00:10:28,640 --> 00:10:30,980
И тогава какво друго
промяна трябва да се случи?

219
00:10:30,980 --> 00:10:33,160
Размер вероятно трябва да се върнем към две.

220
00:10:33,160 --> 00:10:34,210
И така, това е добре.

221
00:10:34,210 --> 00:10:36,690
Но почакайте, размер
преди малко беше три.

222
00:10:36,690 --> 00:10:38,240
Нека просто да се направи бърза проверка здрав разум.

223
00:10:38,240 --> 00:10:41,810
Откъде знаем, че сме
искаше да се отърве от 61?

224
00:10:41,810 --> 00:10:42,760
Тъй като ние сме се пръкват.

225
00:10:42,760 --> 00:10:46,450
И така, аз имам този втори размер собственост.

226
00:10:46,450 --> 00:10:48,470
>> Чакай малко, аз съм
мисли обратно към две седмици

227
00:10:48,470 --> 00:10:51,660
когато ние започнахме да говорим за
масиви, когато това е място нула,

228
00:10:51,660 --> 00:10:55,920
това е една локация, това е място
две, това е място три, четири,

229
00:10:55,920 --> 00:10:58,460
Той прилича на
връзка между размера

230
00:10:58,460 --> 00:11:02,780
и елемента, че искам да се премахне
от масива изглежда да бъде само това, което?

231
00:11:02,780 --> 00:11:05,120
Размер минус едно.

232
00:11:05,120 --> 00:11:07,786
И така, това е начина, като хора
ние знаем, 61 е на първо място.

233
00:11:07,786 --> 00:11:09,160
Как компютърът ще знаеш?

234
00:11:09,160 --> 00:11:11,701
Когато кода си, когато е най-вероятно
искам да направя размер минус едно,

235
00:11:11,701 --> 00:11:14,950
така три минус един е две, и че
означава, че ние искаме да се отървем от 61.

236
00:11:14,950 --> 00:11:18,000
И то наистина можем да актуализираме
размера, така че размер предприятието

237
00:11:18,000 --> 00:11:20,300
отива от три до само две.

238
00:11:20,300 --> 00:11:24,520
И само за да бъде педантичен, аз отивам
да предложи, че аз съм направил, нали?

239
00:11:24,520 --> 00:11:27,660
Можете предложен интуитивно
правилно, че трябва да се отървете от 61.

240
00:11:27,660 --> 00:11:30,700
Но има не съм вид
нещо се отървали от 61?

241
00:11:30,700 --> 00:11:33,790
Аз бях забравил ефективно
че това е действително има.

242
00:11:33,790 --> 00:11:37,680
И мисля, обратно към PSET4, ако сте чели
статията за съдебна медицина, в PDF

243
00:11:37,680 --> 00:11:40,780
че имахме момчета четат, или сте
ще прочетете тази седмица за PSET4.

244
00:11:40,780 --> 00:11:44,300
Припомнете си, че това всъщност е уместен за
цялата идея за компютърни лица.

245
00:11:44,300 --> 00:11:47,820
Какво компютър обикновено се прави, е
тя просто забравя, когато нещо е,

246
00:11:47,820 --> 00:11:51,300
но тя не ида и като
опитайте се да го задрасквам или пренебрегване

247
00:11:51,300 --> 00:11:54,560
тези битове с нули и единици
или някакъв друг произволен модел

248
00:11:54,560 --> 00:11:56,690
освен ако не си го направи нарочно.

249
00:11:56,690 --> 00:11:58,930
Така че интуицията е
Добре, да се отървете от 61.

250
00:11:58,930 --> 00:12:00,650
Но в действителност, ние не трябва да се притеснява.

251
00:12:00,650 --> 00:12:04,040
Ние просто трябва да забравяме, че
тя е налице, като промените нашия размер.

252
00:12:04,040 --> 00:12:05,662
>> Сега има проблем с този стак.

253
00:12:05,662 --> 00:12:07,620
Ако аз държа бутане неща
върху комина, какво е

254
00:12:07,620 --> 00:12:11,167
очевидно няма да се случи
само за няколко минути път?

255
00:12:11,167 --> 00:12:12,500
Отиваме да свършат на пространството.

256
00:12:12,500 --> 00:12:13,580
И какво ще правим?

257
00:12:13,580 --> 00:12:14,680
Ние сме вид прецакани.

258
00:12:14,680 --> 00:12:19,000
Това изпълнение не позволявайте
ни преоразмеряване на масива, тъй като се използва

259
00:12:19,000 --> 00:12:21,240
този синтаксис, ако
мисля, обратно на две седмица,

260
00:12:21,240 --> 00:12:23,520
след като веднъж сте декларирани
размера на масив,

261
00:12:23,520 --> 00:12:26,780
не сме виждали механизъм все още къде
можете да промените размера на масива.

262
00:12:26,780 --> 00:12:29,020
И наистина C не разполага с този елемент.

263
00:12:29,020 --> 00:12:32,524
Ако кажете, дайте ми пет
Nths, ги наричат ​​номера,

264
00:12:32,524 --> 00:12:33,940
това е всичко, ти започваш да го получи.

265
00:12:33,940 --> 00:12:38,790
Така че ние правим сега, считано от понеделник, имат
способността да експресират разтвор

266
00:12:38,790 --> 00:12:42,480
все пак, ние просто трябва да се ощипвам
определението на нашия купчина

267
00:12:42,480 --> 00:12:46,840
да не бъдат някои трудно кодирани масив,
но само за да се съхранява на адрес.

268
00:12:46,840 --> 00:12:47,890
>> Сега защо е това?

269
00:12:47,890 --> 00:12:51,690
Сега ние просто трябва да се чувстват удобно,
факта, че когато програмата ми изтече,

270
00:12:51,690 --> 00:12:53,730
Аз вероятно ще
Трябва да попитам човека,

271
00:12:53,730 --> 00:12:55,110
колко числа искаш да съхранявате?

272
00:12:55,110 --> 00:12:56,776
Така че на входа трябва да дойде от някъде.

273
00:12:56,776 --> 00:12:59,140
Но след като знам, че
номер, тогава мога само

274
00:12:59,140 --> 00:13:02,470
използвате това, което функционира до получаване на
ми парче от паметта?

275
00:13:02,470 --> 00:13:03,580
Мога да използвам изчистване.

276
00:13:03,580 --> 00:13:06,710
И мога да кажа, всеки брой на
байта Искам обратно за тези Nths.

277
00:13:06,710 --> 00:13:10,910
И всичко, което трябва да се съхранява в броя
променлива тук вътре в тази структура на

278
00:13:10,910 --> 00:13:13,480
трябва да бъде това, което?

279
00:13:13,480 --> 00:13:18,440
Какво всъщност отива в
номера в този сценарий?

280
00:13:18,440 --> 00:13:21,300
Да, указател към първия
байт, че парче от паметта,

281
00:13:21,300 --> 00:13:24,940
или по-специално, на адреса
на първото от тези байтове.

282
00:13:24,940 --> 00:13:27,300
Няма значение дали това е един
байтове или един милиард байта,

283
00:13:27,300 --> 00:13:28,890
Просто трябва да се грижи за първото.

284
00:13:28,890 --> 00:13:31,530
Защото това, което изчистване гаранции и
моите операционната система гаранции,

285
00:13:31,530 --> 00:13:34,170
е, че парчето памет I
получите, то се случва да бъдат съседни.

286
00:13:34,170 --> 00:13:35,378
Там няма да бъде пропуски.

287
00:13:35,378 --> 00:13:38,576
Така че, ако съм поискал 50
байта или 1000 байта,

288
00:13:38,576 --> 00:13:40,450
те всички ще бъдат
да се върна обратно към гърба.

289
00:13:40,450 --> 00:13:44,500
И доколкото си спомням колко е голям, колко
много ми поиска, всичко, което трябва да знаете

290
00:13:44,500 --> 00:13:46,230
е първият такъв адрес.

291
00:13:46,230 --> 00:13:48,660
>> Така че сега ние имаме възможността в код.

292
00:13:48,660 --> 00:13:51,280
Макар, че това ще ни отведе
повече време да напиша това нагоре,

293
00:13:51,280 --> 00:13:55,900
Сега можем да се преразпределят, че паметта от
Просто съхраняване на друг адрес там

294
00:13:55,900 --> 00:13:59,060
ако искаме по-голяма или дори
по-малко парче от паметта.

295
00:13:59,060 --> 00:14:00,170
Така че тук, за да пласирам.

296
00:14:00,170 --> 00:14:01,360
Сега ние се динамика.

297
00:14:01,360 --> 00:14:03,350
Все още имаме
contiguousness съм претендира.

298
00:14:03,350 --> 00:14:05,881
Защото изчистване ще ни даде
свързано парче от паметта.

299
00:14:05,881 --> 00:14:08,630
Но това ще бъде болка в
врата за нас, програмист,

300
00:14:08,630 --> 00:14:09,770
действително да се кодират до.

301
00:14:09,770 --> 00:14:10,730
Това е просто повече работа.

302
00:14:10,730 --> 00:14:13,930
Трябва код близко до това, което бях
чука навън само преди миг.

303
00:14:13,930 --> 00:14:16,120
Много изпълним, но добавя сложност.

304
00:14:16,120 --> 00:14:19,520
И така времето разработчик, програмист
времето е още един ресурс

305
00:14:19,520 --> 00:14:22,520
че ние може да се наложи да прекарат
известно време, за да получите нови функции.

306
00:14:22,520 --> 00:14:24,020
И след това, разбира се, има опашка.

307
00:14:24,020 --> 00:14:26,227
Ние няма да влезем в този
един в много подробности.

308
00:14:26,227 --> 00:14:27,560
Но това е много подобен по дух.

309
00:14:27,560 --> 00:14:31,220
Можех да приложат на опашка, и
съответните си операции,

310
00:14:31,220 --> 00:14:35,660
Enqueue или dequeue, като добавяте или премахвате,
това е просто любител начин да го казвам,

311
00:14:35,660 --> 00:14:38,100
Enqueue или dequeue, както следва.

312
00:14:38,100 --> 00:14:41,170
Аз просто мога да се даде структура на
че отново има масив редица му,

313
00:14:41,170 --> 00:14:44,000
който отново е с размер,
но защо аз сега трябва

314
00:14:44,000 --> 00:14:46,940
да следите отпред на опашката?

315
00:14:46,940 --> 00:14:50,630
Аз не трябва да знаете
предната част на моя стак.

316
00:14:50,630 --> 00:14:53,570
Е, ако аз отново за
queue-- нека просто трудно

317
00:14:53,570 --> 00:14:57,870
го код като имащи като петте
числа в потенциално тук.

318
00:14:57,870 --> 00:15:00,940
Така че това е нула, едно, две, три, четири.

319
00:15:00,940 --> 00:15:03,430
Това ще бъде
наречени отново номера.

320
00:15:03,430 --> 00:15:06,940
И това ще се нарича размер.

321
00:15:06,940 --> 00:15:10,056
>> Защо това не е достатъчно,
да има само размер?

322
00:15:10,056 --> 00:15:11,680
Ами, нека да прокара тези същите номера на.

323
00:15:11,680 --> 00:15:14,220
Така че аз съм pushed-- enqueued, или бутани.

324
00:15:14,220 --> 00:15:20,150
Сега ще Enqueue 50, и след това
51, и след това 61, и точка, точка точка.

325
00:15:20,150 --> 00:15:21,070
Така че това е Enqueue.

326
00:15:21,070 --> 00:15:23,176
I enqueued 50, после 51, после 61.

327
00:15:23,176 --> 00:15:25,050
И това изглежда идентично
да стак до този момент,

328
00:15:25,050 --> 00:15:27,190
с изключение на I е нужно да се направи една промяна.

329
00:15:27,190 --> 00:15:33,680
Имам нужда да се актуализира този размер, така че аз отивам
от нула до един до 02:58 сега.

330
00:15:33,680 --> 00:15:35,760
Как мога да dequeue?

331
00:15:35,760 --> 00:15:36,890
Какво се случва с dequeue?

332
00:15:36,890 --> 00:15:41,950
Кой трябва да влезе в този списък първи
ако това е линията на Apple Store?

333
00:15:41,950 --> 00:15:42,780
Така 50.

334
00:15:42,780 --> 00:15:44,700
Така че това е вид сложни и този път.

335
00:15:44,700 --> 00:15:47,880
Като има предвид, за последен път, че е супер
лесно просто да направите размер минус едно,

336
00:15:47,880 --> 00:15:51,440
Да стигна до края на моя масив ефективно
където цифрите са, тя премахва 61.

337
00:15:51,440 --> 00:15:52,920
Но аз не искам да се премахне 61.

338
00:15:52,920 --> 00:15:55,030
Искам да се възползвам от 50, които
беше там в 5:00 AM

339
00:15:55,030 --> 00:15:56,790
да се подредят за
Новият iPhone или какво ли още не.

340
00:15:56,790 --> 00:16:01,200
И така, за да се отървете от 50, I
Не може просто да направите това, нали?

341
00:16:01,200 --> 00:16:02,547
Мога да зачеркнете 50.

342
00:16:02,547 --> 00:16:04,380
Но ние просто си казахме
не е нужно да бъде толкова анален

343
00:16:04,380 --> 00:16:06,330
че да задрасквам или скриване на данните.

344
00:16:06,330 --> 00:16:08,090
Ние можем просто да забравите къде е.

345
00:16:08,090 --> 00:16:12,330
>> Но ако си променя размера на предприятието, за да
две, е това достатъчно информация

346
00:16:12,330 --> 00:16:15,711
да знаят какво се случва в моята опашка?

347
00:16:15,711 --> 00:16:16,680
Не съвсем.

348
00:16:16,680 --> 00:16:19,830
Както е моя размер две, но
когато не започва опашката,

349
00:16:19,830 --> 00:16:22,980
особено ако аз все още имам
Същите тези числа в паметта.

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

351
00:16:24,260 --> 00:16:27,090
Така че аз трябва да се помни,
Сега, когато отпред е.

352
00:16:27,090 --> 00:16:29,630
И така, както аз предложих нагоре
там, ще сме просто нарича

353
00:16:29,630 --> 00:16:33,729
N-та отпред, чиято първоначална
стойност трябва да е какво?

354
00:16:33,729 --> 00:16:35,270
Нула, само началото на списъка.

355
00:16:35,270 --> 00:16:40,876
Но сега, в допълнение към намаляващи
размера, ние просто нарастване на фронта.

356
00:16:40,876 --> 00:16:42,000
Сега тук е друг проблем.

357
00:16:42,000 --> 00:16:43,030
Така че след като аз да тръгвам.

358
00:16:43,030 --> 00:16:47,520
Да предположим, че това е броят на
като 121, 124, и след това, по дяволите,

359
00:16:47,520 --> 00:16:48,610
Аз съм на пространството.

360
00:16:48,610 --> 00:16:50,390
Но почакайте, аз не съм.

361
00:16:50,390 --> 00:16:55,630
Така че в този момент в историята,
Предполагам, че размерът е едно, две,

362
00:16:55,630 --> 00:17:00,370
три, четири, така че предполагам, че
размер е четири, отпред е един,

363
00:17:00,370 --> 00:17:01,621
51 е така отпред.

364
00:17:01,621 --> 00:17:04,329
Искам да сложа друг номер тук,
но, по дяволите, аз съм на пространството.

365
00:17:04,329 --> 00:17:06,710
Но аз не съм много, нали?

366
00:17:06,710 --> 00:17:11,192
Къде мога да се въведе някакъв
допълнителна стойност, като 171?

367
00:17:11,192 --> 00:17:13,400
Да, можех просто вид
се върна там, нали?

368
00:17:13,400 --> 00:17:18,161
И тогава зачеркнете 50, или
Просто го презапишете с 171.

369
00:17:18,161 --> 00:17:20,410
И ако сте се чудех защо
нашите номера дойдоха толкова произволни,

370
00:17:20,410 --> 00:17:24,150
те обикновено се вземат компютър
научни курсове в Харвард след CS50.

371
00:17:24,150 --> 00:17:27,510
Но това беше една добра оптимизация,
защото сега аз не губя пространство.

372
00:17:27,510 --> 00:17:30,750
Аз все още трябва да се помни
колко е голяма тази нещо е общо.

373
00:17:30,750 --> 00:17:31,500
Това е пет общо.

374
00:17:31,500 --> 00:17:33,375
Защото аз не искам да се
започнете презаписване 51.

375
00:17:33,375 --> 00:17:36,260
Така че сега аз съм все още на пространството,
така същия проблем, както преди.

376
00:17:36,260 --> 00:17:39,140
Но можете да видите как сега
в кода си, най-вероятно

377
00:17:39,140 --> 00:17:41,910
трябва да напиша малко по-
сложност, за да се случи това.

378
00:17:41,910 --> 00:17:44,510
И всъщност, какво оператор
в C-вероятно ви позволява

379
00:17:44,510 --> 00:17:48,110
можете да направите това по магически кръглостта?

380
00:17:48,110 --> 00:17:50,160
Да оператора на модул,
знака за процент.

381
00:17:50,160 --> 00:17:53,160
Така че това, което е нещо готино за опашка,
въпреки че ние продължаваме рисуване масиви

382
00:17:53,160 --> 00:17:56,520
тъй като тези като прави линии, ако
вид мисля за това като извита

383
00:17:56,520 --> 00:18:00,341
наоколо като кръг, след това просто
интуитивно го вид работи с умствени

384
00:18:00,341 --> 00:18:01,590
Мисля, че е малко по-чисто.

385
00:18:01,590 --> 00:18:05,190
Вие все още ще трябва да въведат
че мисловен модел в код.

386
00:18:05,190 --> 00:18:07,550
Така че не е толкова трудно,
в крайна сметка, да се приложат,

387
00:18:07,550 --> 00:18:12,430
но ние все още губи size-- по-скоро,
способност да преоразмерите, освен ако не правим това.

388
00:18:12,430 --> 00:18:15,310
>> Ние трябва да се отървете от масива, ние
да го замени с единен показалеца,

389
00:18:15,310 --> 00:18:20,010
и след това някъде в моя код Имам
а това, което наричаме функционира действително да се създаде

390
00:18:20,010 --> 00:18:23,720
масива, наречени номера?

391
00:18:23,720 --> 00:18:26,190
Изчистване, или някаква подобна
функция, точно.

392
00:18:26,190 --> 00:18:30,481
Всякакви въпроси за стекове или опашки.

393
00:18:30,481 --> 00:18:30,980
Да?

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

395
00:18:33,657 --> 00:18:34,240
Добър въпрос.

396
00:18:34,240 --> 00:18:35,830
Какво по модул ще можете да използвате тук.

397
00:18:35,830 --> 00:18:38,520
Така обикновено, когато се използва
Министерството на отбраната, ще го направя

398
00:18:38,520 --> 00:18:40,620
с размера на
Цялата структура на данните.

399
00:18:40,620 --> 00:18:44,120
Така че нещо като пет или капацитет, ако
това е постоянен, вероятно е замесен.

400
00:18:44,120 --> 00:18:47,100
Но просто правиш по модул пет
най-вероятно не е достатъчно,

401
00:18:47,100 --> 00:18:51,380
защото ние трябва да знаят, че ние правим
обгърне тук или тук или тук.

402
00:18:51,380 --> 00:18:54,160
Значи вие сте най-вероятно също
Ще искаме да включим

403
00:18:54,160 --> 00:18:57,220
размера на нещо, или
предната променлива, както добре.

404
00:18:57,220 --> 00:19:00,140
Така че това е просто този сравнително
прост аритметичен израз,

405
00:19:00,140 --> 00:19:02,000
но по модул ще бъде ключовата съставка.

406
00:19:02,000 --> 00:19:03,330
>> Така късометражен филм, ако щете.

407
00:19:03,330 --> 00:19:05,780
Една анимация, че някои
хора в друг университет

408
00:19:05,780 --> 00:19:08,060
взети заедно, че ние сме
адаптиран за тази дискусия.

409
00:19:08,060 --> 00:19:12,630
Тя включва изучаването на Джак
факти за опашки и статистики.

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

411
00:19:19,010 --> 00:19:21,890
>> FILM: Имало едно време,
имаше един човек на име Джак.

412
00:19:21,890 --> 00:19:25,330
Когато става дума за вземане на приятели,
Джак не е имал цака.

413
00:19:25,330 --> 00:19:28,220
Така че Джак отиде да говори с
Най-популярният човек знаеше.

414
00:19:28,220 --> 00:19:30,920
Той отиде до Лу и попита: Какво да правя?

415
00:19:30,920 --> 00:19:33,400
Лу видя, че приятелят му
Беше наистина в затруднено положение.

416
00:19:33,400 --> 00:19:36,050
Е, той започна, просто
вижте колко сте облечени.

417
00:19:36,050 --> 00:19:38,680
Не имате някакви дрехи
с различен поглед?

418
00:19:38,680 --> 00:19:39,660
Да, каза Джак.

419
00:19:39,660 --> 00:19:40,840
Убеден съм, че правя.

420
00:19:40,840 --> 00:19:43,320
Ела в къщата ми и
Аз ще ви ги покажа.

421
00:19:43,320 --> 00:19:44,550
И те отидоха на разстояние до Джак.

422
00:19:44,550 --> 00:19:47,520
И Джак показа Lou кутията
където държеше всичките си ризи,

423
00:19:47,520 --> 00:19:49,260
и панталоните си и чорапите му.

424
00:19:49,260 --> 00:19:52,290
Лу каза, виждам че имате
всичките си дрехи в купчина.

425
00:19:52,290 --> 00:19:54,870
Защо не носят някаква
други веднъж в известно време?

426
00:19:54,870 --> 00:19:58,020
>> Джак каза, добре, когато съм
премахване на дрехи и чорапи,

427
00:19:58,020 --> 00:20:00,780
Аз ги изпере и постави
ги далеч в наказателното поле.

428
00:20:00,780 --> 00:20:03,210
След това идва следващият
сутрин и до I-хоп.

429
00:20:03,210 --> 00:20:06,380
Отида на полето и да получите
дрехите ми на разстояние от върха.

430
00:20:06,380 --> 00:20:09,070
Lou бързо осъзнах
проблемът с Джак.

431
00:20:09,070 --> 00:20:12,080
Държеше дрехи, CD-та,
и книги в стека.

432
00:20:12,080 --> 00:20:14,420
Когато той посегна
нещо за четене или за носене,

433
00:20:14,420 --> 00:20:17,100
той ще избере най-горния книгата или бельото.

434
00:20:17,100 --> 00:20:19,500
Тогава, когато той е направил, той
ще го постави обратно.

435
00:20:19,500 --> 00:20:21,970
Обратно, че ще отида, на върха на стека.

436
00:20:21,970 --> 00:20:24,460
Знам, че решението,
каза триумфално Loud.

437
00:20:24,460 --> 00:20:27,090
Трябва да се научите да
започнете да използвате опашка.

438
00:20:27,090 --> 00:20:29,870
Лу взе дрехите на Джак и
ги затвори в килера.

439
00:20:29,870 --> 00:20:32,710
И когато той е изпразнен
на наказателното поле, той просто го хвърли.

440
00:20:32,710 --> 00:20:36,500
>> Тогава той каза, сега Джак, в края на
деня, сложи дрехите си в ляво

441
00:20:36,500 --> 00:20:37,990
когато ги направи.

442
00:20:37,990 --> 00:20:41,300
Тогава утре сутринта, когато
виж на слънцето, да получите вашите дрехи

443
00:20:41,300 --> 00:20:43,440
отдясно, от края на линията.

444
00:20:43,440 --> 00:20:44,880
Не виждаш ли? каза Лу.

445
00:20:44,880 --> 00:20:46,370
Тя ще бъде толкова хубаво.

446
00:20:46,370 --> 00:20:49,770
Ще нося всичко наведнъж
преди да носят нещо два пъти.

447
00:20:49,770 --> 00:20:52,670
И с всичко в опашки
в неговата тоалетна и срок,

448
00:20:52,670 --> 00:20:55,160
Джак започна да се чувства
съвсем сигурен в себе си.

449
00:20:55,160 --> 00:20:59,720
Всички благодарение на Лу и
прекрасно си опашка.

450
00:20:59,720 --> 00:21:01,220
SPEAKER 1: Добре, това е възхитителен.

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

452
00:21:05,920 --> 00:21:10,080
Така че това, което е наистина се случва
за под предния капак в момента?

453
00:21:10,080 --> 00:21:12,370
Това имаме указатели,
че имаме изчистване,

454
00:21:12,370 --> 00:21:15,680
че имаме възможността да се създават
парчета от паметта за себе си

455
00:21:15,680 --> 00:21:16,344
динамично.

456
00:21:16,344 --> 00:21:18,510
Така че това е една ние картина
зърнал онзи ден.

457
00:21:18,510 --> 00:21:21,180
Ние наистина не спирам
върху него, но тази снимка

458
00:21:21,180 --> 00:21:24,180
продължава вече под
качулката от седмици.

459
00:21:24,180 --> 00:21:27,050
И така, това означава, просто
правоъгълник, който установили сме,

460
00:21:27,050 --> 00:21:28,180
паметта на компютъра ви.

461
00:21:28,180 --> 00:21:31,850
И може би вашия компютър, или CS50
ID, има гигабайт памет или RAM

462
00:21:31,850 --> 00:21:33,050
или два гигабайта или четири.

463
00:21:33,050 --> 00:21:34,450
Това няма значение.

464
00:21:34,450 --> 00:21:37,240
Вашата операционна система
Windows или Mac OS или Linux,

465
00:21:37,240 --> 00:21:41,120
същество дава възможност на програма
да се мисли, че има достъп

466
00:21:41,120 --> 00:21:42,982
за целостта на
паметта на компютъра,

467
00:21:42,982 --> 00:21:45,440
въпреки че може да се работи
няколко програми наведнъж.

468
00:21:45,440 --> 00:21:46,990
Така че в действителност, че наистина не работи.

469
00:21:46,990 --> 00:21:49,448
Но това е вид илюзия
дава на всичките си програми.

470
00:21:49,448 --> 00:21:53,110
Така че, ако има две участия на RAM, това
е как компютърът може да мисли за това.

471
00:21:53,110 --> 00:21:57,110
>> Сега случайно, една от тях
неща, един от тези сегменти на паметта,

472
00:21:57,110 --> 00:21:58,350
се нарича комин.

473
00:21:58,350 --> 00:22:01,680
И наистина всяко време
до този момент в писмен код

474
00:22:01,680 --> 00:22:05,900
че сте се нарича
функция, например основната.

475
00:22:05,900 --> 00:22:08,410
Припомнете си, че всеки път, когато съм
памет, изготвен на компютъра,

476
00:22:08,410 --> 00:22:10,640
Аз винаги се направи нещо
половината от правоъгълник тук

477
00:22:10,640 --> 00:22:12,520
и не се притеснява да говори
за това, което е горе.

478
00:22:12,520 --> 00:22:15,980
Защото, когато основната се нарича, аз твърдя,
че получавате това късче памет

479
00:22:15,980 --> 00:22:16,970
че слиза тук.

480
00:22:16,970 --> 00:22:20,650
И ако основната функция, наречена
като суап, и суап отива тук.

481
00:22:20,650 --> 00:22:23,720
И се оказва, че е
къде е завършил.

482
00:22:23,720 --> 00:22:26,277
На нещо, наречено комин
вътре в паметта на компютъра ви.

483
00:22:26,277 --> 00:22:28,360
Сега в края на деня,
това е просто обръщение.

484
00:22:28,360 --> 00:22:30,680
Това е като байт нула,
байт, байт 2 млрд.

485
00:22:30,680 --> 00:22:33,130
Но ако си мислиш за него
като този правоъгълен обект,

486
00:22:33,130 --> 00:22:35,130
всичко, което правим всеки
време, което наричаме функция е

487
00:22:35,130 --> 00:22:37,180
наслояване ново парче от паметта.

488
00:22:37,180 --> 00:22:41,700
Ние даваме тази функция парче
на собствената си памет, за да се работи.

489
00:22:41,700 --> 00:22:44,490
>> И припомни, че сега това е важно.

490
00:22:44,490 --> 00:22:46,400
Защото, ако ние нямаме
нещо като суап

491
00:22:46,400 --> 00:22:51,610
и две локални променливи като А и Б и
ние променяме тези ценности от едно и две

492
00:22:51,610 --> 00:22:55,130
до два и един, изземване
че когато се връща за размяна,

493
00:22:55,130 --> 00:22:58,330
това е така, сякаш този отрязък
от системната памет е просто изчезна.

494
00:22:58,330 --> 00:23:00,080
В действителност, тя все още е
има forensically.

495
00:23:00,080 --> 00:23:01,940
И нещо още е действително има.

496
00:23:01,940 --> 00:23:05,410
Но концептуално, това е като
Въпреки че е напълно изчезнала.

497
00:23:05,410 --> 00:23:10,910
И така основният не знае нито една от дейностите
че се извършва в тази замяна функция,

498
00:23:10,910 --> 00:23:14,890
освен ако не е действително отражение в тези,
аргументи от страна на показалеца или чрез препратка.

499
00:23:14,890 --> 00:23:17,790
Сега, основното решение
на този проблем със суап

500
00:23:17,790 --> 00:23:19,970
преминава неща в по адрес.

501
00:23:19,970 --> 00:23:23,250
Но се оказва, също, което е
продължава вече над тази част

502
00:23:23,250 --> 00:23:26,330
на правоъгълника през цялото това време е
Все още има повече памет до там.

503
00:23:26,330 --> 00:23:28,790
И когато динамично
достатъчно памет,

504
00:23:28,790 --> 00:23:32,020
независимо дали е вътре в GetString, които
ние сме били прави за вас в CS50

505
00:23:32,020 --> 00:23:34,710
библиотека, или, ако вие
обадете изчистване и попитайте

506
00:23:34,710 --> 00:23:37,950
операционната система за парче
памет, тя не идва от комина.

507
00:23:37,950 --> 00:23:40,960
Тя идва от друго място
в паметта на компютъра си

508
00:23:40,960 --> 00:23:42,220
това се нарича купчината.

509
00:23:42,220 --> 00:23:43,430
И това не е по-различно.

510
00:23:43,430 --> 00:23:44,285
Това е същата RAM.

511
00:23:44,285 --> 00:23:45,160
Това е същата памет.

512
00:23:45,160 --> 00:23:49,080
Това е просто RAM, че е до
там вместо тук.

513
00:23:49,080 --> 00:23:50,750
>> И така, какво означава това?

514
00:23:50,750 --> 00:23:53,650
Е, ако компютърът ви има
ограничен размер на паметта

515
00:23:53,650 --> 00:23:57,450
и топчето се разраства, така че
да се каже, и на куп, според

516
00:23:57,450 --> 00:23:59,349
до тази стрелка, расте надолу.

517
00:23:59,349 --> 00:24:01,140
С други думи, всеки
време ти се обадя изчистване,

518
00:24:01,140 --> 00:24:03,430
което се дава на парче
на памет от по-горе,

519
00:24:03,430 --> 00:24:06,630
тогава може би малко по-ниско, а след малко
по-ниска, всеки път, когато ти се обадя изчистване,

520
00:24:06,630 --> 00:24:10,100
купчината, това е използване,
е вид расте,

521
00:24:10,100 --> 00:24:11,950
разраства все по-близо до това, което?

522
00:24:11,950 --> 00:24:13,382
Купчината.

523
00:24:13,382 --> 00:24:14,840
Така че прави това да изглежда като добра идея?

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

525
00:24:18,420 --> 00:24:22,140
Искам да кажа, когато това не е много ясно
какво друго можеш да направиш, ако само ти

526
00:24:22,140 --> 00:24:23,910
имат ограничен количество памет.

527
00:24:23,910 --> 00:24:25,200
Но това със сигурност е лошо.

528
00:24:25,200 --> 00:24:27,920
Тези две стрели са по
катастрофата Разбира се един за друг.

529
00:24:27,920 --> 00:24:31,930
>> И се оказва, че лош човек, хора, които
са особено добре с програмиране,

530
00:24:31,930 --> 00:24:36,140
и се опитва да проникна в компютрите,
може да използва това реалност.

531
00:24:36,140 --> 00:24:38,290
Всъщност, нека да разгледаме
малко фрагмент.

532
00:24:38,290 --> 00:24:41,350
Така че това е пример можете да прочетете
за по-подробно на Wikipedia.

533
00:24:41,350 --> 00:24:43,100
Ние ще ви насочи в
статия, ако любопитен.

534
00:24:43,100 --> 00:24:45,650
Но има една атака като цяло
известен като препълване на буфера, че

535
00:24:45,650 --> 00:24:49,570
е съществувала толкова дълго, колкото хората
да има способността да се манипулират

536
00:24:49,570 --> 00:24:53,120
памет на компютъра, особено в C.
Така че това е един много произволна програма,

537
00:24:53,120 --> 00:24:55,130
но нека си го чете от дъното нагоре.

538
00:24:55,130 --> 00:24:57,650
Main в argC Чар звезда argV.

539
00:24:57,650 --> 00:24:59,830
Така че това е една програма, която отнема
командния ред аргументи.

540
00:24:59,830 --> 00:25:03,620
И всичко се основна очевидно е разговор
функция, тя се обади F за простота.

541
00:25:03,620 --> 00:25:04,610
И тя преминава в какво?

542
00:25:04,610 --> 00:25:05,490
ArgV на един.

543
00:25:05,490 --> 00:25:09,320
Така той преминава в каквото и F
думата е, че потребителят напечатани

544
00:25:09,320 --> 00:25:11,500
в командния ред, след като на
Име на програмата на всички.

545
00:25:11,500 --> 00:25:15,730
Толкова много, като Цезар или Vigenere, които
можете да си спомните, правиш с argV.

546
00:25:15,730 --> 00:25:16,680
>> Така че това, което е F?

547
00:25:16,680 --> 00:25:19,760
F отнема в низ
като единствен аргумент,

548
00:25:19,760 --> 00:25:22,100
AKA Чар звезда, същата
нещо, като низ.

549
00:25:22,100 --> 00:25:24,920
И тя се нарича произволно
бар в този пример.

550
00:25:24,920 --> 00:25:27,710
И след това слага в 12,
само по отношение на лаик,

551
00:25:27,710 --> 00:25:31,750
това, което е Чар в скоба 12 прави за нас?

552
00:25:31,750 --> 00:25:33,440
Какво е това?

553
00:25:33,440 --> 00:25:36,490
Разпределяне на паметта, по-специално
12 байта за 12 символа.

554
00:25:36,490 --> 00:25:36,990
Точно.

555
00:25:36,990 --> 00:25:40,000
И тогава на последния ред, разбърква се и се
копие, най-вероятно не сте виждали.

556
00:25:40,000 --> 00:25:43,360
Това е низ копие
функция, чиято цел в живота

557
00:25:43,360 --> 00:25:48,160
е да копирате втория си довод
в първия си аргумент,

558
00:25:48,160 --> 00:25:51,190
но само до
определен брой байтове.

559
00:25:51,190 --> 00:25:53,860
Така трети аргумент казва,
колко байта да копирате?

560
00:25:53,860 --> 00:25:56,720
Дължината на бар,
независимо от потребителя написали инча

561
00:25:56,720 --> 00:25:59,320
И съдържанието на
Бар, че низ, са

562
00:25:59,320 --> 00:26:02,330
копирани в паметта посочи в C.

563
00:26:02,330 --> 00:26:04,060
>> Така че това изглежда някак глупаво, и това е.

564
00:26:04,060 --> 00:26:06,300
Това е измислен пример,
но това е представителна

565
00:26:06,300 --> 00:26:10,100
на клас вектори на атака,
начин на атаката програма.

566
00:26:10,100 --> 00:26:15,050
Всичко е наред и добро, ако потребителят
видове в една дума, която е 11 символа

567
00:26:15,050 --> 00:26:18,040
или по-малко, плюс наклонената черта нула.

568
00:26:18,040 --> 00:26:22,830
Какво става, ако потребителят в повече от
11 или 12 или 20 или 50 знака?

569
00:26:22,830 --> 00:26:25,090
Каква е тази програма ще направите?

570
00:26:25,090 --> 00:26:29,360
Потенциално сек вина. Това ще
сляпо да копирате всичко в бара до

571
00:26:29,360 --> 00:26:31,750
към дължината си, което е
буквално всичко в бар,

572
00:26:31,750 --> 00:26:36,307
в адреса посочи C. Но C
е само изпреварващо да се прилага като 12 байта.

573
00:26:36,307 --> 00:26:37,640
Но няма допълнителна проверка.

574
00:26:37,640 --> 00:26:38,700
Няма никакъв случай условия.

575
00:26:38,700 --> 00:26:40,580
Няма никаква проверка за грешки тук.

576
00:26:40,580 --> 00:26:43,270
>> И така, какво тази програма е
ще направя, е просто сляпо

577
00:26:43,270 --> 00:26:45,750
копират едно нещо към другия.

578
00:26:45,750 --> 00:26:47,880
И така, ако се направи това
като картина, ето

579
00:26:47,880 --> 00:26:49,860
просто частица от пространството на паметта.

580
00:26:49,860 --> 00:26:53,470
Така забележи в долната част, ние
има променлива бара местно.

581
00:26:53,470 --> 00:26:57,330
Така че показалеца, че ще ходи да store--
по-скоро, че местната аргумент, че това е

582
00:26:57,330 --> 00:26:58,672
ще съхранявате бара низ.

583
00:26:58,672 --> 00:27:00,380
И тогава просто забележите
над него в комин,

584
00:27:00,380 --> 00:27:02,505
защото всеки път, когато поиска
за паметта на стека,

585
00:27:02,505 --> 00:27:04,310
тя отива малко по-
над него живописно,

586
00:27:04,310 --> 00:27:06,270
известие, че ние имаме 12 байта там.

587
00:27:06,270 --> 00:27:10,690
В горния ляв тях е C скоба нула и
правилният дъното е C скоба 11.

588
00:27:10,690 --> 00:27:12,870
Това е само как компютрите
ще го изложи.

589
00:27:12,870 --> 00:27:18,300
Така че просто интуитивно, ако бар има повече
от 12 знака в общо, включително

590
00:27:18,300 --> 00:27:25,790
наклонената черта нула, където е най-
12 или скоба C 12 ще отиде?

591
00:27:25,790 --> 00:27:28,440
Или по-скоро, когато е 12-ти
характера или 13-ти характер,

592
00:27:28,440 --> 00:27:30,900
стотен характер ще
да се окажете на снимката?

593
00:27:30,900 --> 00:27:33,400
Над или под?

594
00:27:33,400 --> 00:27:36,300
>> Точно така, защото въпреки че
самата стека расте нагоре,

595
00:27:36,300 --> 00:27:39,590
след като веднъж сте сложи неща в
него, за конструктивни причини,

596
00:27:39,590 --> 00:27:41,294
поставя паметта от горе до долу.

597
00:27:41,294 --> 00:27:44,460
Така че, ако имаш повече от 12 байта,
започваш да се започне да се презапише бар.

598
00:27:44,460 --> 00:27:47,280
Сега това е бъг, но е
наистина не е голяма работа.

599
00:27:47,280 --> 00:27:51,130
Но това е голяма работа, защото има
повече неща се случва в паметта.

600
00:27:51,130 --> 00:27:53,074
Така че тук е как можем да
сложи здравей, за да бъде ясно.

601
00:27:53,074 --> 00:27:54,490
Ако аз напечатани в здравей в командния ред.

602
00:27:54,490 --> 00:27:59,330
H-E-L-L-O наклонена черта нула, се озовава в рамките на
тези 12 байта, и ние сме супер безопасни.

603
00:27:59,330 --> 00:28:00,330
Всичко е наред.

604
00:28:00,330 --> 00:28:03,020
Но ако объркате нещо
вече, това е потенциално

605
00:28:03,020 --> 00:28:05,860
Ще се вмъкват в бар пространство.

606
00:28:05,860 --> 00:28:08,405
Но още по-лошо, тя се превръща
от цялото това време,

607
00:28:08,405 --> 00:28:11,530
въпреки че никога не сме говорили за
това, топчето се използва за други неща.

608
00:28:11,530 --> 00:28:13,560
Това не е просто локални променливи.

609
00:28:13,560 --> 00:28:15,100
>> C е на много ниско ниво на езика.

610
00:28:15,100 --> 00:28:17,810
И това нещо тайно
използва стека също

611
00:28:17,810 --> 00:28:21,260
да се помни, когато
Функцията се нарича, това, което

612
00:28:21,260 --> 00:28:26,040
адресът е на предходната функция,
така че може да скочи обратно към тази функция.

613
00:28:26,040 --> 00:28:29,980
Така че, когато основните разговори разменят, наред
нещата избута върху купчината

614
00:28:29,980 --> 00:28:34,380
не са само суапове локални променливи,
или неговите аргументи, също тайно избута

615
00:28:34,380 --> 00:28:37,510
върху купчината, представлявано
от червено парче тук,

616
00:28:37,510 --> 00:28:40,520
е адресът на основната физически
в паметта на компютъра,

617
00:28:40,520 --> 00:28:44,180
така че, когато се прави суап, компютърът
знае, че аз трябва да се върна към основното

618
00:28:44,180 --> 00:28:46,760
и да завърши изпълнението на основната функция.

619
00:28:46,760 --> 00:28:51,960
Така че това е опасно сега, защото ако
типовете потребителски добре в повече от здравей,

620
00:28:51,960 --> 00:28:57,030
така, че въвеждане на потребителя clobbers
или презаписва, че червената точка,

621
00:28:57,030 --> 00:28:59,820
логично, ако на компютъра
просто ще приемем, сляпо

622
00:28:59,820 --> 00:29:03,830
че байта в тази червено парче са
адреса, на който тя трябва да се върне,

623
00:29:03,830 --> 00:29:09,020
какво ще стане ако противникът е достатъчно умен, или
достатъчно късмет, за да се сложи последователност от байтове

624
00:29:09,020 --> 00:29:13,450
там, че прилича на един адрес,
но това е адресът на код

625
00:29:13,450 --> 00:29:18,730
че той или тя иска компютъра
да изпълни вместо главната?

626
00:29:18,730 --> 00:29:21,670
>> С други думи, ако това, което на
потребител пише в командния ред,

627
00:29:21,670 --> 00:29:23,850
не е просто нещо
безвреден като здравей,

628
00:29:23,850 --> 00:29:28,210
но всъщност е код, който е еквивалентен
за да изтриете всички файлове на този потребител?

629
00:29:28,210 --> 00:29:30,060
Или пишете паролата си за мен?

630
00:29:30,060 --> 00:29:31,940
Или започнете да влезете им
клавиши, нали?

631
00:29:31,940 --> 00:29:34,920
Има начин, нека да постанови днес,
че те могат да напишете просто 'Здравей' не

632
00:29:34,920 --> 00:29:36,711
свят или тяхното име,
те биха могли по същество

633
00:29:36,711 --> 00:29:39,570
премине в кодови, нули и
такива, че компютърът

634
00:29:39,570 --> 00:29:43,450
грешки за код, така и на един адрес.

635
00:29:43,450 --> 00:29:48,950
Така че, макар и малко по-абстрактно, ако
типове потребители в достатъчно състезателна код

636
00:29:48,950 --> 00:29:52,330
че ние ще обобщим тук
A. A е атака или противници.

637
00:29:52,330 --> 00:29:53,140
Така че просто лоши неща.

638
00:29:53,140 --> 00:29:55,306
Ние не се грижим за
номера или нули или такива

639
00:29:55,306 --> 00:29:59,470
днес, така че в крайна сметка
презаписване, че червената точка,

640
00:29:59,470 --> 00:30:01,580
забележи, че последователност от байтове.

641
00:30:01,580 --> 00:30:05,020
O 835 C нула осем нула.

642
00:30:05,020 --> 00:30:08,960
И сега, както и статия в Уикипедия тук
предложи, ако сега започнете действително

643
00:30:08,960 --> 00:30:12,460
етикетирането на байтове в компютъра ви
памет, какво статията Wikipedia е

644
00:30:12,460 --> 00:30:19,060
предлагащата е, че това, което ако адресът
на тази горния ляв байт е 80 C 0 3508.

645
00:30:19,060 --> 00:30:22,200
>> С други думи, ако лош човек е
достатъчно умен, с неговия или нейния код

646
00:30:22,200 --> 00:30:26,650
действително да постави редица тук, че
съответства на адреса на кода

647
00:30:26,650 --> 00:30:29,180
той или тя инжектира
в компютъра, ви

648
00:30:29,180 --> 00:30:31,050
може да излъже компютъра
в прави нищо.

649
00:30:31,050 --> 00:30:34,140
Сваляне на файлове, за електронна поща
неща, смъркане на трафика,

650
00:30:34,140 --> 00:30:36,710
буквално всичко може да бъде
инжектира в компютъра.

651
00:30:36,710 --> 00:30:39,220
И така, препълване на буфера
атака в същността си

652
00:30:39,220 --> 00:30:43,530
е просто глупаво, глупаво
императивно от масив, който

653
00:30:43,530 --> 00:30:45,840
не са имали своите граници проверени.

654
00:30:45,840 --> 00:30:48,850
И това е, което е супер опасна
и едновременно супер мощен

655
00:30:48,850 --> 00:30:52,560
в C е, че ние наистина имаме
достъп до всяка точка в паметта.

656
00:30:52,560 --> 00:30:55,320
Това е до нас, програмистите,
които пишат оригиналния код

657
00:30:55,320 --> 00:30:59,330
да проверите дължината на всяка дяволски
масиви, че ние сме манипулирали.

658
00:30:59,330 --> 00:31:00,750
Така че да е ясно, каква е уговорката?

659
00:31:00,750 --> 00:31:03,190
Ако ние се търкаля към тази
код, аз не трябва просто

660
00:31:03,190 --> 00:31:08,000
промяна на дължината на бар, какво
друго трябва да се провери?

661
00:31:08,000 --> 00:31:10,620
Какво друго трябва да се прави, за да
предотвратяване на тази атака изцяло?

662
00:31:10,620 --> 00:31:14,110
Аз не искам да кажа, просто сляпо
че трябва да се копира колкото се може повече байта

663
00:31:14,110 --> 00:31:16,140
както е дължината на бар.

664
00:31:16,140 --> 00:31:18,910
Искам да кажа, като копирате
много байта като са в бар

665
00:31:18,910 --> 00:31:24,090
до отпуснатите
памет, или 12 максимално.

666
00:31:24,090 --> 00:31:27,450
Така че аз трябва някакъв вид ако състоянието
който прави проверка на дължината на бар,

667
00:31:27,450 --> 00:31:32,800
но ако тя надвишава 12, ние просто трудно код
12 като максималното възможно разстояние.

668
00:31:32,800 --> 00:31:35,910
В противен случай т.нар буфер
препълване атака може да се случи.

669
00:31:35,910 --> 00:31:38,451
В долната част на тези слайдове,
ако сте любопитни да научите повече

670
00:31:38,451 --> 00:31:41,200
е действителната оригиналната статия
ако искате да погледнете.

671
00:31:41,200 --> 00:31:44,550
>> Но сега, сред цени
платени тук е липсата на ефективност.

672
00:31:44,550 --> 00:31:46,680
Така че това е един бърз
ниско ниво поглед към това, което

673
00:31:46,680 --> 00:31:49,709
могат да възникнат проблеми сега, че ние
имат достъп до паметта на компютъра.

674
00:31:49,709 --> 00:31:51,750
Но друг проблем ние
вече се препъна в понеделник

675
00:31:51,750 --> 00:31:53,800
беше просто неефективността
на свързан списък.

676
00:31:53,800 --> 00:31:56,019
Ние сме обратно в линейното време.

677
00:31:56,019 --> 00:31:57,560
Ние вече нямаме съседна масив.

678
00:31:57,560 --> 00:31:58,980
Ние не разполагаме с произволен достъп.

679
00:31:58,980 --> 00:32:00,710
Ние не можем да използваме квадратна скоба нотация.

680
00:32:00,710 --> 00:32:04,590
Ние буквално трябва да се използва по време на цикъл
като този, аз написах преди малко.

681
00:32:04,590 --> 00:32:09,740
Но в понеделник, ние твърдеше, че можем
пълзене обратно в царството на ефективност

682
00:32:09,740 --> 00:32:13,040
постигане на нещо, което е
логаритмична може би, или най-добре все пак,

683
00:32:13,040 --> 00:32:16,120
може би дори нещо, което е
така наречените постоянно време.

684
00:32:16,120 --> 00:32:19,840
И така, как можем да направим, че с помощта на тези нови
инструменти, тези адреси, тези указатели,

685
00:32:19,840 --> 00:32:22,210
и резби неща от нашата собствена?

686
00:32:22,210 --> 00:32:23,960
Е, предполагам, че
тук, това са куп

687
00:32:23,960 --> 00:32:27,170
от числа, които искаме да се съхранява в
структура и търсене на данни ефективно.

688
00:32:27,170 --> 00:32:30,960
Абсолютно Можем да се върнем назад до седмица
две, хвърлят ги в масив,

689
00:32:30,960 --> 00:32:33,150
и да ги търсите с двоично търсене.

690
00:32:33,150 --> 00:32:34,040
Разделяй и владей.

691
00:32:34,040 --> 00:32:37,720
И всъщност ви е написал
Търсене в двоичен в PSET3,

692
00:32:37,720 --> 00:32:40,100
където изпълнява програмата находка.

693
00:32:40,100 --> 00:32:40,890
Но знаете ли какво.

694
00:32:40,890 --> 00:32:45,060
Има вид на по-
хитър начин за постигане на това.

695
00:32:45,060 --> 00:32:47,390
Това е малко по-
сложна и може би

696
00:32:47,390 --> 00:32:50,830
ни позволява да видим защо двоичен
търсене е толкова по-бързо.

697
00:32:50,830 --> 00:32:52,980
Първо, нека да въведат
понятието за едно дърво.

698
00:32:52,980 --> 00:32:54,730
Което, въпреки че в
риалити дървета вид

699
00:32:54,730 --> 00:32:57,730
растат по този начин, в света на компютъра
науката те вид расте надолу

700
00:32:57,730 --> 00:33:00,830
като родословно дърво, където трябва
баба си и дядо или баба и дядо велики

701
00:33:00,830 --> 00:33:04,580
или какво ли не най-отгоре, патриархът и
матриарх на семейството, точно този,

702
00:33:04,580 --> 00:33:07,930
така наречените корен, възел, под
които са си деца,

703
00:33:07,930 --> 00:33:11,442
по-долу, които са негови деца, или
неговите потомци по-общо.

704
00:33:11,442 --> 00:33:13,400
И всеки, който виси
дъното на семейството

705
00:33:13,400 --> 00:33:16,070
дърво, освен че е на
най-младият в семейството,

706
00:33:16,070 --> 00:33:19,520
също може да бъде само най-общо
нарича листата на дървото.

707
00:33:19,520 --> 00:33:21,800
>> Така че това е просто един куп
от думи и определения

708
00:33:21,800 --> 00:33:25,790
за нещо, наречено дърво в компютъра
наука, много прилича на родословно дърво.

709
00:33:25,790 --> 00:33:28,770
Но има и по-красиви превъплъщения
дървета, един от които

710
00:33:28,770 --> 00:33:30,780
се нарича двоично търсене дърво.

711
00:33:30,780 --> 00:33:34,380
И можете вид закачка
освен това, това нещо прави.

712
00:33:34,380 --> 00:33:37,180
Е, това е двоичен в какъв смисъл?

713
00:33:37,180 --> 00:33:41,455
Къде двоичен идват от тук?

714
00:33:41,455 --> 00:33:41,955
Съжаляваме?

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

716
00:33:45,961 --> 00:33:47,210
Това не е толкова много на едно или и.

717
00:33:47,210 --> 00:33:52,000
Това е още, че всеки от възли не
повече от две деца, тъй като ние видите тук.

718
00:33:52,000 --> 00:33:54,990
Като цяло, tree-- и
Вашите родители и прародители

719
00:33:54,990 --> 00:33:57,640
може да има колкото се може повече деца, или
внуци, тъй като те всъщност искат,

720
00:33:57,640 --> 00:34:00,820
и така например там имаме три
децата на разстояние, че дясната ръка на възел,

721
00:34:00,820 --> 00:34:05,480
но в двоично дърво, един възел има
нула, една или две деца максимално.

722
00:34:05,480 --> 00:34:08,496
И това е хубаво собственост,
защото, ако това е с таван от две,

723
00:34:08,496 --> 00:34:10,620
ние ще бъде в състояние да
получи малко дневник база двама

724
00:34:10,620 --> 00:34:11,975
действия става тук в крайна сметка.

725
00:34:11,975 --> 00:34:13,350
Така че ние имаме нещо логаритмична.

726
00:34:13,350 --> 00:34:14,558
Но повече за това след малко.

727
00:34:14,558 --> 00:34:19,810
Търсене дърво означава, че числата са
разположени така, че лявата детето

728
00:34:19,810 --> 00:34:22,429
стойност е по-голяма от корена.

729
00:34:22,429 --> 00:34:26,010
И правото си дете е
по-голям от основата.

730
00:34:26,010 --> 00:34:29,290
С други думи, ако вземе всяка от
възли, кръговете в тази картина,

731
00:34:29,290 --> 00:34:31,840
и поглежда към своя ляв
дете и правото си дете,

732
00:34:31,840 --> 00:34:34,739
първият трябва да бъде по-малко от,
Второто трябва да бъде по-голяма.

733
00:34:34,739 --> 00:34:36,159
Така че здравия разум провери 55.

734
00:34:36,159 --> 00:34:37,780
Той е оставил дете е 33.

735
00:34:37,780 --> 00:34:38,620
Това е по-малко от.

736
00:34:38,620 --> 00:34:40,929
55, правото му дете е 77.

737
00:34:40,929 --> 00:34:41,783
Това е по-голям от.

738
00:34:41,783 --> 00:34:43,199
И това е рекурсивно определение.

739
00:34:43,199 --> 00:34:46,480
Бихме могли да проверява всеки един от тези,
възли и същи модел би попречил.

740
00:34:46,480 --> 00:34:49,389
>> Така че това, което е хубаво в
двоично търсене дърво, е

741
00:34:49,389 --> 00:34:52,204
че един, можем да го приложат
с структура на, точно като тази.

742
00:34:52,204 --> 00:34:54,620
И въпреки, че сме хвърляне
много структури на вашия,

743
00:34:54,620 --> 00:34:56,560
те са малко по-
интуитивен сега се надяваме.

744
00:34:56,560 --> 00:35:00,570
Синтаксисът е все още тайнствена със сигурност,
но съдържанието на възел в този

745
00:35:00,570 --> 00:35:02,786
context-- и пазим
използване на думата възел,

746
00:35:02,786 --> 00:35:04,910
независимо дали това е правоъгълник
на екрана или в кръг,

747
00:35:04,910 --> 00:35:08,970
това е просто някаква родово контейнер,
в този случай на едно дърво, като този

748
00:35:08,970 --> 00:35:11,780
видяхме, имаме нужда от цяло число
във всяка от възли

749
00:35:11,780 --> 00:35:15,460
и след това имам нужда от две указатели, сочещи
към лявата и дясната детето детето,

750
00:35:15,460 --> 00:35:16,590
съответно.

751
00:35:16,590 --> 00:35:20,730
Така че това е как можем да
приложат, че в една структура на.

752
00:35:20,730 --> 00:35:22,315
И как бих могъл да го приложи в кода?

753
00:35:22,315 --> 00:35:26,730
Е, нека хвърлим един бърз
Посетете този малък пример.

754
00:35:26,730 --> 00:35:29,820
Това не е функционална, но аз съм
копира и тази структура.

755
00:35:29,820 --> 00:35:33,510
И ако ми функция за двоичен
Търсене в дърво се нарича търсене,

756
00:35:33,510 --> 00:35:36,980
и това отнема два аргумента,
цяло число N и указател

757
00:35:36,980 --> 00:35:41,400
на една възлова точка, така указател към дървото
или указател към корена на едно дърво,

758
00:35:41,400 --> 00:35:43,482
как да отида, за да търсите N?

759
00:35:43,482 --> 00:35:45,440
Ами, на първо място, защото аз съм
занимаващи се с указатели,

760
00:35:45,440 --> 00:35:46,750
Отивам да се направи проверка на здравия разум.

761
00:35:46,750 --> 00:35:54,279
Ако дървесни равни равнява на нула, е N
в това дърво или не в това дърво?

762
00:35:54,279 --> 00:35:55,070
Не може да бъде, нали?

763
00:35:55,070 --> 00:35:56,870
Ако аз съм минал нищожна,
там няма нищо.

764
00:35:56,870 --> 00:35:59,230
Че може и просто
сляпо кажа върне фалшиви.

765
00:35:59,230 --> 00:36:04,050
Ако ми дадеш нищо, аз със сигурност не може да
намирам кой номер N. Така че какво друго бих могъл да

766
00:36:04,050 --> 00:36:04,750
проверите сега?

767
00:36:04,750 --> 00:36:12,830
Отивам да се каже и друго, ако N е
по-малко от всичко, което е най-възела на дърво

768
00:36:12,830 --> 00:36:16,300
че съм бил предаден N стойност.

769
00:36:16,300 --> 00:36:20,270
С други думи, ако броят съм
търси, N, е по-малко от възела

770
00:36:20,270 --> 00:36:21,340
че аз разглеждам.

771
00:36:21,340 --> 00:36:23,190
И възела Търся
в се нарича дърво,

772
00:36:23,190 --> 00:36:26,370
и извикайте от предишния пример
за да получите най-стойността в указател,

773
00:36:26,370 --> 00:36:28,310
Аз използвам наколонените стрелка.

774
00:36:28,310 --> 00:36:35,960
Така че, ако N е по-малко от дърво стрелка
N, искам да отида концептуално лявата.

775
00:36:35,960 --> 00:36:38,590
Как мога да изразят търсите напусна?

776
00:36:38,590 --> 00:36:41,560
За да е ясно, дали това е
на снимката въпросния

777
00:36:41,560 --> 00:36:44,612
и аз съм бил приет, че най-горната
стрелка, която е насочена надолу.

778
00:36:44,612 --> 00:36:45,570
Това е моето дърво показалка.

779
00:36:45,570 --> 00:36:48,060
Аз съм като посочи в корена на дървото.

780
00:36:48,060 --> 00:36:52,100
И аз търся да речем, за
44 броя, произволно.

781
00:36:52,100 --> 00:36:55,300
Е 44 или по-малко от
по-голяма от 55 очевидно?

782
00:36:55,300 --> 00:36:56,360
Така че това е по-малко от.

783
00:36:56,360 --> 00:36:58,760
И така, това изискване се прилага, ако.

784
00:36:58,760 --> 00:37:03,981
Така че концептуално, какво искам да
търси следващия, ако аз съм гледам за 44?

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

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

787
00:37:08,310 --> 00:37:11,100
>> Точно така, аз искам да
Търсене по левия детето,

788
00:37:11,100 --> 00:37:12,789
или наляво под-дървото на тази снимка.

789
00:37:12,789 --> 00:37:14,830
И всъщност, нека чрез
на снимката тук

790
00:37:14,830 --> 00:37:17,770
само за миг, тъй като
Не мога да се почеше това.

791
00:37:17,770 --> 00:37:21,150
Ако започна тук, в 55, и
Знам, че стойността 44

792
00:37:21,150 --> 00:37:23,180
Търся да
отляво, това е вид

793
00:37:23,180 --> 00:37:26,010
на подобно разкъсване телефонния указател в
половината или разкъсване на дървото на половина.

794
00:37:26,010 --> 00:37:29,660
Аз вече не трябва да се грижим за
Цялата тази половината от дървото.

795
00:37:29,660 --> 00:37:33,270
И все пак, любопитно от гледна точка на
структура, това нещо тук, че

796
00:37:33,270 --> 00:37:36,682
започва с 33, че и самата
е двоичен търсене дърво.

797
00:37:36,682 --> 00:37:39,890
Аз казах думата рекурсивни преди, защото
Наистина това е структура от данни, че

798
00:37:39,890 --> 00:37:41,707
по дефиниция е рекурсивно.

799
00:37:41,707 --> 00:37:44,540
Може да се наложи едно дърво, което е това
голяма, но всеки един от нейните деца

800
00:37:44,540 --> 00:37:46,870
представлява едно дърво малко по-малък.

801
00:37:46,870 --> 00:37:50,910
Вместо да е дядо
или баба, сега това е просто мама

802
00:37:50,910 --> 00:37:54,300
or-- Не мога да не say-- майка
или татко, че би било странно.

803
00:37:54,300 --> 00:37:59,000
Вместо двете деца там
ще бъде като брат и сестра.

804
00:37:59,000 --> 00:38:01,120
Едно ново поколение на родословното дърво.

805
00:38:01,120 --> 00:38:02,900
Но структурно, това е една и съща идея.

806
00:38:02,900 --> 00:38:06,790
И се оказва, че имам функция
с които мога да търсите двоично търсене

807
00:38:06,790 --> 00:38:07,290
дърво.

808
00:38:07,290 --> 00:38:08,680
Тя се нарича търсене.

809
00:38:08,680 --> 00:38:17,870
Търся N в дърво лява стрелка
иначе, ако N е по-голяма от стойността

810
00:38:17,870 --> 00:38:18,870
Сигурен съм, че в момента в.

811
00:38:18,870 --> 00:38:20,800
55 в историята преди малко.

812
00:38:20,800 --> 00:38:23,780
Имам функция, наречена
търсене, което мога, просто

813
00:38:23,780 --> 00:38:29,660
мине N това и рекурсивно търсене
под-дърво и просто връщане

814
00:38:29,660 --> 00:38:30,620
независимо, че отговор.

815
00:38:30,620 --> 00:38:33,530
Иначе аз имам някаква окончателна базов модел тук.

816
00:38:33,530 --> 00:38:35,310
>> Каква е крайната случая?

817
00:38:35,310 --> 00:38:36,570
Tree е или нула.

818
00:38:36,570 --> 00:38:39,980
Стойността съм или търсите е
по-малко от това или по-голяма от

819
00:38:39,980 --> 00:38:42,610
или равна на нея.

820
00:38:42,610 --> 00:38:44,750
И мога да кажа, равна
равен, но това е логично

821
00:38:44,750 --> 00:38:46,500
еквивалентен на просто казвам друго тук.

822
00:38:46,500 --> 00:38:49,150
Така че истинската е как да намеря нещо.

823
00:38:49,150 --> 00:38:51,710
Така че да се надяваме това е
още по-наложителна например

824
00:38:51,710 --> 00:38:54,900
от функцията за глупав сигма
ние направихме няколко лекции в гърба,

825
00:38:54,900 --> 00:38:58,360
където е било толкова лесно да се използва линия
да брои до всички номера, от една

826
00:38:58,360 --> 00:39:02,390
Н. Тук със структурата на данните
че се е рекурсивно

827
00:39:02,390 --> 00:39:07,050
дефинирани и рекурсивно изготвен, сега ние
имат способността да се изразяваме

828
00:39:07,050 --> 00:39:09,780
в кода, който от своя страна е рекурсивно.

829
00:39:09,780 --> 00:39:12,580
Така че това е точно същия код тук.

830
00:39:12,580 --> 00:39:14,400
>> И така, какво друго можем да решим проблемите?

831
00:39:14,400 --> 00:39:18,160
Така бързо крачка от
дървета за миг.

832
00:39:18,160 --> 00:39:20,130
Ето, да речем, на германското знаме.

833
00:39:20,130 --> 00:39:22,020
А има и ясно
модел на този флаг.

834
00:39:22,020 --> 00:39:23,811
И има много
флагове в света, които

835
00:39:23,811 --> 00:39:27,560
са толкова прости, колкото това от гледна точка
на техните цветове и модели.

836
00:39:27,560 --> 00:39:31,930
Но предполагам, че това се съхранява като
.GIF Или JPEG, или растерна графика, или за пинг,

837
00:39:31,930 --> 00:39:34,240
всеки графичен файлов формат
с които сте запознати,

838
00:39:34,240 --> 00:39:36,460
някои от които сме
играе с по PSET4.

839
00:39:36,460 --> 00:39:41,550
Това не изглежда полезно да се съхранява
черен пиксел, черен пиксел, черен пиксел,

840
00:39:41,550 --> 00:39:44,790
точка, точка, точка, цял куп
черни пиксели за първи scanline,

841
00:39:44,790 --> 00:39:47,430
или ред, а след това цял куп
същата, тогава един куп

842
00:39:47,430 --> 00:39:49,530
на същото, и след това
цял куп червени пиксела,

843
00:39:49,530 --> 00:39:53,020
червени пиксела, червени пиксела, след цяло
куп жълти пиксела, жълто, нали?

844
00:39:53,020 --> 00:39:55,050
>> Има такава неефективност тук.

845
00:39:55,050 --> 00:39:59,040
Как бихте интуитивно
компресирате германското знаме

846
00:39:59,040 --> 00:40:01,320
ако го изпълняват като файл?

847
00:40:01,320 --> 00:40:04,940
Подобно на това каква информация може да не
притеснява съхраняване на диск, за да

848
00:40:04,940 --> 00:40:08,040
за да се намали размера на файла от нашия харесват
мегабайт до килобайт, нещо,

849
00:40:08,040 --> 00:40:09,430
по-малки?

850
00:40:09,430 --> 00:40:13,130
Където се намира на съкращенията
тук, за да бъде ясно?

851
00:40:13,130 --> 00:40:13,880
Какво може да направите?

852
00:40:13,880 --> 00:40:14,380
Да?

853
00:40:14,380 --> 00:40:21,380

854
00:40:21,380 --> 00:40:21,970
Точно.

855
00:40:21,970 --> 00:40:24,550
Защо не, а не си спомня
цвета на всеки пиксел кърпи

856
00:40:24,550 --> 00:40:28,200
точно като правиш в PSET4
с формата на растерна графика файл,

857
00:40:28,200 --> 00:40:32,060
защо просто не представляват
лявата колона на пиксела, например

858
00:40:32,060 --> 00:40:35,370
куп черни пиксели, куп
на червено, и куп жълти,

859
00:40:35,370 --> 00:40:39,210
и след това просто някак кодират
Идеята за Повторете това 100 пъти

860
00:40:39,210 --> 00:40:41,020
или Повторете това 1000 пъти?

861
00:40:41,020 --> 00:40:43,430
Когато 100 или 1000 е
само цяло число, така че

862
00:40:43,430 --> 00:40:47,290
може да се размине само с един номер
вместо стотици или хиляди

863
00:40:47,290 --> 00:40:48,270
допълнителни пиксела.

864
00:40:48,270 --> 00:40:50,990
И наистина, това е начина, по който
може да компресирате германското знаме.

865
00:40:50,990 --> 00:40:51,490
И

866
00:40:51,490 --> 00:40:53,470
Сега какво да кажем за френски флаг?

867
00:40:53,470 --> 00:40:58,930
И малко някаква
умствено упражнение, което флаг

868
00:40:58,930 --> 00:41:01,040
могат да бъдат компресирани повече диск?

869
00:41:01,040 --> 00:41:05,720
Германското знаме или французите
флаг, ако вземем този подход?

870
00:41:05,720 --> 00:41:08,490
Германското знаме, защото има
по-хоризонтална съкращения.

871
00:41:08,490 --> 00:41:12,190
И като дизайн, графичен файл мнозина
формати наистина работят линии като сканиране

872
00:41:12,190 --> 00:41:12,830
хоризонтално.

873
00:41:12,830 --> 00:41:14,674
Те биха могли да работят
вертикално, просто човечеството

874
00:41:14,674 --> 00:41:17,090
Преди години решиха, че ние ще
като цяло мисля за неща ред

875
00:41:17,090 --> 00:41:18,880
по ред, вместо колона по колона.

876
00:41:18,880 --> 00:41:20,820
Така че наистина, ако сте били
да погледнете файла

877
00:41:20,820 --> 00:41:24,670
размер на немски флаг и френски
флаг, докато резолюцията е

878
00:41:24,670 --> 00:41:27,530
същото, същата ширина
и височина, този път

879
00:41:27,530 --> 00:41:31,580
тук ще бъде по-голяма, защото
трябва да се повтаря себе си три пъти.

880
00:41:31,580 --> 00:41:35,570
Вие трябва да посочите, синьо, повторете
себе си, бяла, повторете себе си, червено,

881
00:41:35,570 --> 00:41:36,740
повтаря себе си.

882
00:41:36,740 --> 00:41:39,000
Не може просто да отидете на всички
Между другото в дясно.

883
00:41:39,000 --> 00:41:41,200
И като настрана, за да се
изчистване на компресия

884
00:41:41,200 --> 00:41:43,910
е навсякъде, ако те са
четири кадъра от една video-- ви

885
00:41:43,910 --> 00:41:45,890
да си спомните, че един филм
или видео е по принцип

886
00:41:45,890 --> 00:41:47,286
като 29 или 30 кадъра в секунда.

887
00:41:47,286 --> 00:41:50,410
Това е като малко флип книга, където можете
Просто вижте изображението, изображение, картинка, изображение,

888
00:41:50,410 --> 00:41:54,410
образ просто супер бързо, така че тя изглежда като
актьорите на екрана се движат.

889
00:41:54,410 --> 00:41:57,130
Ето една пчела на
Начало на букет цветя.

890
00:41:57,130 --> 00:41:59,790
И макар че може да е вид
трудно да се види на пръв поглед,

891
00:41:59,790 --> 00:42:04,020
единственото нещо, което се движи в
този филм е пчелата.

892
00:42:04,020 --> 00:42:06,880
>> Какво е тъпо за съхранение
видео разархивиране?

893
00:42:06,880 --> 00:42:11,420
Това е вид на отпадъците, за да съхранявате видео
като четири почти идентични изображения, които

894
00:42:11,420 --> 00:42:13,670
различават само дотолкова, доколкото когато пчелата е.

895
00:42:13,670 --> 00:42:16,280
Можете да изхвърлите най-
на тази информация

896
00:42:16,280 --> 00:42:20,190
и не забравяйте само, например,
първият кадър и последния кадър,

897
00:42:20,190 --> 00:42:22,180
ключови кадъра, ако сте
Някога чували думата,

898
00:42:22,180 --> 00:42:24,337
и просто да се съхранява в
средна когато пчелата е.

899
00:42:24,337 --> 00:42:26,170
И не е нужно да
съхраните всички розово,

900
00:42:26,170 --> 00:42:28,330
и синьо, а
зелени стойности, както добре.

901
00:42:28,330 --> 00:42:31,200
Така че това е да се каже само, че
сгъстяване е навсякъде.

902
00:42:31,200 --> 00:42:34,900
Това е техника, ние често използват
или приемаме за даденост, тези дни.

903
00:42:34,900 --> 00:42:38,750
>> Но как да компресирате текст?

904
00:42:38,750 --> 00:42:40,450
Как да отида за компресиране на текст?

905
00:42:40,450 --> 00:42:45,410
Е, всеки от героите в
Ascii е един байт, или осем бита.

906
00:42:45,410 --> 00:42:47,360
И това е нещо тъпо, нали?

907
00:42:47,360 --> 00:42:51,160
Защото най-вероятно тип А
и Е и I и O и U много

908
00:42:51,160 --> 00:42:55,270
по-често, отколкото като W или Q или Z,
в зависимост от езика, на който

909
00:42:55,270 --> 00:42:56,610
пишеш със сигурност.

910
00:42:56,610 --> 00:42:59,600
И защо да се използва
осем бита за всяка буква,

911
00:42:59,600 --> 00:43:02,040
включително най
популярните писма, нали?

912
00:43:02,040 --> 00:43:05,300
Защо не се използва по-малко битове за
супер популярни букви,

913
00:43:05,300 --> 00:43:07,760
като E, нещата, които предполагам
на първо място в Колелото на късмета,

914
00:43:07,760 --> 00:43:10,450
и да използват повече битове за
най-малко популярни букви?

915
00:43:10,450 --> 00:43:10,950
Защо?

916
00:43:10,950 --> 00:43:13,130
Защото ние просто ще
ги използват по-рядко.

917
00:43:13,130 --> 00:43:15,838
>> Е, оказва се, че там има
били направени опити да се направи това.

918
00:43:15,838 --> 00:43:18,630
И ако си спомняте от клас
училище или гимназия, морзовата азбука.

919
00:43:18,630 --> 00:43:20,400
Морзовата азбука има точици
и тирета, които могат да бъдат

920
00:43:20,400 --> 00:43:24,270
предава по жица като
звуци или сигнали от някакъв вид.

921
00:43:24,270 --> 00:43:25,930
Но Морзовата азбука е супер чист.

922
00:43:25,930 --> 00:43:29,010
Това е вид на бинарна система
че имате точки или тирета.

923
00:43:29,010 --> 00:43:30,977
Но, ако сте въвели, например, две точки.

924
00:43:30,977 --> 00:43:33,810
Или ако смятате, обратно към оператора
който върви като по сигнал, звуков сигнал, звуков сигнал,

925
00:43:33,810 --> 00:43:36,760
звуков сигнал, удря малко спусъка
който предава сигнал,

926
00:43:36,760 --> 00:43:40,360
ако получателят, получава две
точки, какво послание сте получили?

927
00:43:40,360 --> 00:43:43,490
Напълно произволно.

928
00:43:43,490 --> 00:43:44,450
>> I?

929
00:43:44,450 --> 00:43:45,060
I?

930
00:43:45,060 --> 00:43:47,500
Или какво about-- иначе?

931
00:43:47,500 --> 00:43:49,570
Може би това е само два полето E е?

932
00:43:49,570 --> 00:43:52,480
Така че има този проблем
на decodability с Морс

933
00:43:52,480 --> 00:43:54,890
код, при което освен ако
човек, който да изпратите съобщението

934
00:43:54,890 --> 00:43:59,510
всъщност прави пауза за да можете да сортирате на
видите или чуете пролуките между букви,

935
00:43:59,510 --> 00:44:02,990
това не е достатъчно просто да се
изпрати поток от нули и единици,

936
00:44:02,990 --> 00:44:05,610
или точки и тирета,
защото има неяснота.

937
00:44:05,610 --> 00:44:08,640
E е една точка, така че ако
виж две точки или чуете две точки,

938
00:44:08,640 --> 00:44:11,254
може би това е два E или може би това е една I.

939
00:44:11,254 --> 00:44:13,670
Така че ние се нуждаем от система, която е
малко по-умен от това.

940
00:44:13,670 --> 00:44:16,851
Така че един човек на име Huffman години
Преди дойде с точно това.

941
00:44:16,851 --> 00:44:18,600
Така че ние просто ще
да вземе един бърз поглед

942
00:44:18,600 --> 00:44:20,114
колко дървета са уместен за това.

943
00:44:20,114 --> 00:44:22,530
Да предположим, че това е известно
глупаво съобщение, който искате да изпратите,

944
00:44:22,530 --> 00:44:26,342
съставен от само A, B, C е D'е и E е,
но има много съкращения тук.

945
00:44:26,342 --> 00:44:27,550
Това не е писано да бъде на английски език.

946
00:44:27,550 --> 00:44:28,341
Това не е кодирано.

947
00:44:28,341 --> 00:44:30,540
Това е просто глупаво съобщение
с много повторения.

948
00:44:30,540 --> 00:44:34,010
Така че, ако действително отписвайте всички
На А, Б, С е, D'ите, и Е е, ето

949
00:44:34,010 --> 00:44:34,890
честотата.

950
00:44:34,890 --> 00:44:37,800
20% от писмата са
А на 45% от писмата,

951
00:44:37,800 --> 00:44:39,660
са E, а три други честоти.

952
00:44:39,660 --> 00:44:41,960
Преброихме там ръчно
и що е математика.

953
00:44:41,960 --> 00:44:44,579
>> Така се оказва, че
Хъфман, преди известно време,

954
00:44:44,579 --> 00:44:46,620
осъзнах, че, нали знаете
какво, ако започна сграда

955
00:44:46,620 --> 00:44:51,172
дърво или гора от дървета, ако щете,
както следва, което мога да направя следното.

956
00:44:51,172 --> 00:44:53,880
Отивам да дам един възел на всеки
от писмата, че ме е грижа за

957
00:44:53,880 --> 00:44:55,530
и аз отивам да се съхранява
вътрешността на този възел

958
00:44:55,530 --> 00:44:58,610
честотите като плаваща запетая
стойност, или можете да го използвате като N, също,

959
00:44:58,610 --> 00:45:00,210
но ние просто ще се използва плувка тук.

960
00:45:00,210 --> 00:45:03,100
И алгоритъма, че
той предлага, е, че вие

961
00:45:03,100 --> 00:45:07,210
възползвам от тази гора от един възел
дървета, така че супер къси дървета,

962
00:45:07,210 --> 00:45:11,920
и да започнете да ги свързва с
нови групи, нови родители, ако щете.

963
00:45:11,920 --> 00:45:16,150
И вие направите това, като изберете
двете най-малки честоти в даден момент.

964
00:45:16,150 --> 00:45:18,110
Тогава взех 10% и 10%.

965
00:45:18,110 --> 00:45:19,090
Създам нов възел.

966
00:45:19,090 --> 00:45:20,910
И аз призовавам новия възел 20%.

967
00:45:20,910 --> 00:45:22,750
>> Кои две възли I съчетават следващия?

968
00:45:22,750 --> 00:45:23,810
Това е малко неясно.

969
00:45:23,810 --> 00:45:26,643
Така че има някои случаи ъгъл, за да
помисли, но за да пазят нещата доста,

970
00:45:26,643 --> 00:45:29,300
Отивам да избере 20% -
Аз вече не обръща внимание на децата.

971
00:45:29,300 --> 00:45:33,640
Отивам да изберете съответно 20% и
15% и изготвя два нови ръбове.

972
00:45:33,640 --> 00:45:35,624
И сега кои два възела
мога логично комбинирате?

973
00:45:35,624 --> 00:45:38,540
Игнориране на всички деца, всички
внуци, просто погледнете в корените

974
00:45:38,540 --> 00:45:39,070
сега.

975
00:45:39,070 --> 00:45:42,220
Кои две възли мога да връзвам заедно?

976
00:45:42,220 --> 00:45:44,530
Point два и 0.35.

977
00:45:44,530 --> 00:45:45,890
Така че нека да се направи две нови ръбове.

978
00:45:45,890 --> 00:45:47,570
И тогава аз имам само един ляв.

979
00:45:47,570 --> 00:45:48,650
Така че тук е едно дърво.

980
00:45:48,650 --> 00:45:51,160
И това е било умишлено, изготвен
да изглеждат някак доста,

981
00:45:51,160 --> 00:45:55,870
но забележете, че ръбовете са
също е маркиран нула и единица.

982
00:45:55,870 --> 00:45:59,510
Така че всички останали ръбове са равни на нула
произволно, но последователно.

983
00:45:59,510 --> 00:46:01,170
Всички правилни ръбове са такива.

984
00:46:01,170 --> 00:46:05,070
>> И така, какво Хофман, предложен е,
ако искате да представляват B,

985
00:46:05,070 --> 00:46:10,080
вместо представлява броят като 66
на Ascii което е осем цели бита,

986
00:46:10,080 --> 00:46:13,360
Знаете ли какво, просто магазина
модела нула, нула, нула,

987
00:46:13,360 --> 00:46:17,030
нула, защото това е пътят
от дървото ми, г-н дърво Хъфман е,

988
00:46:17,030 --> 00:46:18,600
на крилото от основата.

989
00:46:18,600 --> 00:46:20,970
Ако искате да съхраните
E, за разлика от това, не го правят

990
00:46:20,970 --> 00:46:26,290
изпрати осем бита, които представляват Е.
Вместо това, изпрати онова модел на бита?

991
00:46:26,290 --> 00:46:26,890
One.

992
00:46:26,890 --> 00:46:30,410
И това, което е хубаво за това е,
E, че е най-популярният писмото,

993
00:46:30,410 --> 00:46:32,340
и сте с помощта на
-кратък код за него.

994
00:46:32,340 --> 00:46:34,090
Следващата най-популярните
писмо изглежда, че

995
00:46:34,090 --> 00:46:37,380
беше A. И така колко бита
каза той предложи като употреби за това?

996
00:46:37,380 --> 00:46:38,270
Нула, едно.

997
00:46:38,270 --> 00:46:41,060
>> И тъй като това е изпълнена
като това дърво, за сега

998
00:46:41,060 --> 00:46:43,350
нека да предвидят има
не неяснота в Morse

999
00:46:43,350 --> 00:46:46,090
код, тъй като всички по-
писма, които ви интересуват

1000
00:46:46,090 --> 00:46:48,780
са в края на тези ръбове.

1001
00:46:48,780 --> 00:46:50,580
Така че това е само един
прилагане на едно дърво.

1002
00:46:50,580 --> 00:46:52,538
Това is-- и ще помаха
ръката ми по това как се

1003
00:46:52,538 --> 00:46:55,570
може да приложи това като структура C.

1004
00:46:55,570 --> 00:46:58,260
Ние просто трябва да се комбинират
символ, като Чар,

1005
00:46:58,260 --> 00:46:59,910
и честотата, в ляво и дясно.

1006
00:46:59,910 --> 00:47:02,510
Но нека да разгледаме две
крайни примери, които ще

1007
00:47:02,510 --> 00:47:06,070
получи доста запознат с след
викторина нула в проблем зададете пет.

1008
00:47:06,070 --> 00:47:09,210
>> Така че има структурата на данните
известен като хеш таблица.

1009
00:47:09,210 --> 00:47:12,247
И хеш таблица е вид
охлади това, че има кофи.

1010
00:47:12,247 --> 00:47:14,830
И предполагам, че има четири кофи
тук, само четири празни пространства.

1011
00:47:14,830 --> 00:47:20,830
Ето едно тесте карти, а тук се
клуб, лопата, клуб, диаманти, клуб,

1012
00:47:20,830 --> 00:47:25,960
диаманти, клуб, диаманти,
clubs-- така че това е произволно.

1013
00:47:25,960 --> 00:47:30,330
Hearts, hearts-- така че аз съм
bucketizing всички входове тук.

1014
00:47:30,330 --> 00:47:32,430
И една нужди хеш таблици
да разгледаме вашия вход,

1015
00:47:32,430 --> 00:47:34,850
и след това го постави в определена
поставят въз основа на това, което виждате.

1016
00:47:34,850 --> 00:47:35,600
Това е един алгоритъм.

1017
00:47:35,600 --> 00:47:37,980
И аз бях с помощта на супер
проста визуална алгоритъм.

1018
00:47:37,980 --> 00:47:40,030
Най-трудната част от които е
спомняйки си какви са снимките.

1019
00:47:40,030 --> 00:47:41,590
И след това има четири общи неща.

1020
00:47:41,590 --> 00:47:45,440
>> Сега купчините растяха, които
е нещо умишлено дизайн тук.

1021
00:47:45,440 --> 00:47:46,540
Но какво друго да правя?

1022
00:47:46,540 --> 00:47:49,080
Така че всъщност тук имаме
куп стари училище изпит книги.

1023
00:47:49,080 --> 00:47:51,240
Да предположим, че един куп
студенти имена са тук.

1024
00:47:51,240 --> 00:47:52,570
Ето по-голяма хеш-таблица.

1025
00:47:52,570 --> 00:47:54,867
Вместо четири кофи,
Аз, да речем 26.

1026
00:47:54,867 --> 00:47:57,950
И ние не искахме да отидем назаем 26
неща от чужбина [? Annenberg?], Така че

1027
00:47:57,950 --> 00:48:00,289
Ето и петте, които представляват
А до Z. И ако аз

1028
00:48:00,289 --> 00:48:03,580
виж студент, чието име започва с А,
Отивам да си викторина сложил там.

1029
00:48:03,580 --> 00:48:08,850
Ако някой започне с C, ей там,
A-- всъщност, не исках да го направя.

1030
00:48:08,850 --> 00:48:10,060
B отива тук.

1031
00:48:10,060 --> 00:48:13,390
Така че аз имам A и B и C. И
Сега тук е друг Един студент.

1032
00:48:13,390 --> 00:48:16,212
Но ако това е хеш-таблица
реализира с масив,

1033
00:48:16,212 --> 00:48:17,920
Аз съм вид прецакани
в този момент, нали?

1034
00:48:17,920 --> 00:48:19,510
Някак трябва да се сложи някъде.

1035
00:48:19,510 --> 00:48:24,380
>> Така че един начин да се реши този е, всичко,
полето, A е зает, B е зает, C е зает.

1036
00:48:24,380 --> 00:48:28,880
Отивам да го сложи в D. Така че най-
на първо място, аз имам случаен незабавен достъп

1037
00:48:28,880 --> 00:48:31,064
към всяка от кофите за учениците.

1038
00:48:31,064 --> 00:48:33,230
Но сега това е вид децентрализиране
в нещо линейно,

1039
00:48:33,230 --> 00:48:36,750
защото, ако искам да потърсите някой,
чието име започва с А, да проверя тук.

1040
00:48:36,750 --> 00:48:38,854
Но ако това не е най-A
Студент търся,

1041
00:48:38,854 --> 00:48:41,520
Някак трябва да започнат проверка
кофите, защото това, което направих

1042
00:48:41,520 --> 00:48:44,530
Беше нещо линейно
изследва структурата на данните.

1043
00:48:44,530 --> 00:48:47,710
Глупава начин да се каже просто погледнете
за първия наличен отвор,

1044
00:48:47,710 --> 00:48:51,850
и постави като план Б, така да се каже,
или план D в този случай, стойността

1045
00:48:51,850 --> 00:48:53,340
в вместо това място.

1046
00:48:53,340 --> 00:48:56,470
Това е просто, така че, ако сте
получи 26 места и няма ученици

1047
00:48:56,470 --> 00:49:00,600
с Q име или Z, или нещо подобно
че, най-малко, че използвате пространството.

1048
00:49:00,600 --> 00:49:03,140
>> Но ние вече сме виждали по-
умни решения тук, нали?

1049
00:49:03,140 --> 00:49:04,870
Какво бихте направили, вместо
ако имате сблъсък?

1050
00:49:04,870 --> 00:49:06,670
Ако двама души имат
на името А, какво ще

1051
00:49:06,670 --> 00:49:09,160
са били по-умен или по-
интуитивно решение, отколкото просто

1052
00:49:09,160 --> 00:49:12,840
извеждайки A, където D е трябвало да бъде?

1053
00:49:12,840 --> 00:49:14,810
Защо не просто отидете
извън [? Annenberg?],

1054
00:49:14,810 --> 00:49:19,960
като изчистване, друг възел, да я тури
тук, и след това пуснати, че един студент тук.

1055
00:49:19,960 --> 00:49:22,120
Така че аз по същество имат
някакъв вид масив,

1056
00:49:22,120 --> 00:49:25,590
или може би по-елегантно, както сме
започваме да виждаме свързан списък.

1057
00:49:25,590 --> 00:49:29,520
>> И така хеш таблица е структура
които биха могли да изглежда точно като този,

1058
00:49:29,520 --> 00:49:33,900
но по-хитро, ти нещо, наречено
отделна верижното, като хеш таблица

1059
00:49:33,900 --> 00:49:38,340
съвсем просто е масив, всеки от
чиито елементи не е число,

1060
00:49:38,340 --> 00:49:40,470
от своя страна е свързан списък.

1061
00:49:40,470 --> 00:49:45,080
Така че можете да получите супер бърз достъп
да реши къде да си хеш стойност.

1062
00:49:45,080 --> 00:49:48,059
Много прилича с примера на карти,
Направих супер бързи решения.

1063
00:49:48,059 --> 00:49:49,600
Hearts отива тук, диаманти отива тук.

1064
00:49:49,600 --> 00:49:52,180
Same тук, A отива тук,
D отива тук, B отива тук.

1065
00:49:52,180 --> 00:49:55,740
Така че супер бързи поглед прозорци, и ако
Случайно да тичам в случай

1066
00:49:55,740 --> 00:49:59,429
когато имаш сблъсъци, две
хора с едно и също име, и след това

1067
00:49:59,429 --> 00:50:00,970
можете просто да започнете свързването им заедно.

1068
00:50:00,970 --> 00:50:03,900
И може би да ги сортира
по азбучен ред, може би не.

1069
00:50:03,900 --> 00:50:05,900
Но поне сега имаме динамизма.

1070
00:50:05,900 --> 00:50:10,250
Така че, от една страна имаме супер бързо
константно време, и вид на линейното време

1071
00:50:10,250 --> 00:50:14,110
участва, ако тези свързани списъци
започнете да се получи малко дълго.

1072
00:50:14,110 --> 00:50:16,880
>> Така че този вид е глупав,
шантавите преди шега години.

1073
00:50:16,880 --> 00:50:19,590
В CS50 хак-а-Thon,
когато учениците се настанят,

1074
00:50:19,590 --> 00:50:22,040
някои TF или Са всяка година
мисли, че е смешно да се примири

1075
00:50:22,040 --> 00:50:27,772
знак, подобен на този, когато тя просто
означава, ако името ти започва с А,

1076
00:50:27,772 --> 00:50:28,870
отидете по този начин.

1077
00:50:28,870 --> 00:50:31,110
Ако започва вашето име
с B, проверете this-- OK,

1078
00:50:31,110 --> 00:50:33,290
това е смешно, може би по-късно през семестъра.

1079
00:50:33,290 --> 00:50:36,420
Но има и друг
начин за това, също.

1080
00:50:36,420 --> 00:50:37,410
Върни се на това.

1081
00:50:37,410 --> 00:50:38,600
>> Така че има тази структура.

1082
00:50:38,600 --> 00:50:40,420
И това е нашият последен
структура за днес,

1083
00:50:40,420 --> 00:50:42,400
което е нещо, наречено синтактично дърво.

1084
00:50:42,400 --> 00:50:47,140
T-R-I-E, които по някаква причина е кратък
за извличане, но тя се нарича синтактично дърво.

1085
00:50:47,140 --> 00:50:51,389
Така синтактично дърво е друга интересна
амалгама от много от тези идеи.

1086
00:50:51,389 --> 00:50:52,930
Това е едно дърво, което сме виждали преди.

1087
00:50:52,930 --> 00:50:54,180
Това не е двоично търсене дърво.

1088
00:50:54,180 --> 00:50:58,410
Това е дърво с произволен брой на децата,
но всяко от децата в синтактично дърво

1089
00:50:58,410 --> 00:51:00,090
е масив.

1090
00:51:00,090 --> 00:51:04,790
Масив с размер на, да речем, 26 или може би 27
ако искате да подкрепите тирета имена

1091
00:51:04,790 --> 00:51:06,790
или апострофи в имената на хората.

1092
00:51:06,790 --> 00:51:08,280
>> И така, това е структура от данни.

1093
00:51:08,280 --> 00:51:10,290
И ако се вгледате от горе
до долу, като, ако

1094
00:51:10,290 --> 00:51:13,710
Посетете най-горния възел там, M, е
сочещи към най-лявата нещо там,

1095
00:51:13,710 --> 00:51:17,665
който след това А, X, W, E, L, L. Това е
само структурата на данните, които произволно

1096
00:51:17,665 --> 00:51:19,120
е съхраняване на имена на хора.

1097
00:51:19,120 --> 00:51:25,720
И Максуел се съхраняват само след
пътека от масив масив масив.

1098
00:51:25,720 --> 00:51:30,050
Но това, което е невероятно за синтактично дърво е
че, като има предвид, свързан списък и дори

1099
00:51:30,050 --> 00:51:34,520
масив, най-добрите, които някога сме придобили е
линейното време или логаритмична време в търсене

1100
00:51:34,520 --> 00:51:35,600
някого.

1101
00:51:35,600 --> 00:51:40,530
В тази структура данни на Trie, ако
моята структура на данните има едно име в него

1102
00:51:40,530 --> 00:51:43,720
и аз съм гледам за Максуел, аз съм
Ще го намерите доста бързо.

1103
00:51:43,720 --> 00:51:47,910
Аз просто гледам за M-A-X-W-E-L-L. Ако
тази структура от данни, от друга страна,

1104
00:51:47,910 --> 00:51:51,830
ако N е един милион, ако има
милион имена в тази структура данни,

1105
00:51:51,830 --> 00:51:57,100
Максуел все още продължава да бъде
откриваем след само M-A-X-W-E-L-L

1106
00:51:57,100 --> 00:51:58,090
стъпки.

1107
00:51:58,090 --> 00:52:01,276
И David-- D-A-V-I-D стъпки.

1108
00:52:01,276 --> 00:52:03,400
С други думи, чрез изграждане
структура, която е на данни

1109
00:52:03,400 --> 00:52:07,240
Трябва всички тези масиви, в които
се издържат с произволен достъп,

1110
00:52:07,240 --> 00:52:11,090
Мога да започне да се оглежда до народната
назове използват сума от време, който е

1111
00:52:11,090 --> 00:52:14,340
пропорционална не броя
на нещата в структурата на данните,

1112
00:52:14,340 --> 00:52:16,330
като един милион съществуващи имена.

1113
00:52:16,330 --> 00:52:20,135
Размерът на време ми отнема да се намери
М-A-X-W-E-L-L в тази структура данни е

1114
00:52:20,135 --> 00:52:22,260
пропорционална не на
размер на структурата на данните,

1115
00:52:22,260 --> 00:52:25,930
но на дължината на името.

1116
00:52:25,930 --> 00:52:28,440
И реалистично
имена, които търсим нагоре

1117
00:52:28,440 --> 00:52:29,970
никога няма да бъде луд дълго.

1118
00:52:29,970 --> 00:52:32,600
Може би някой има 10 герой
назове, 20 име характер.

1119
00:52:32,600 --> 00:52:33,900
Със сигурност това е крайно, нали?

1120
00:52:33,900 --> 00:52:37,110
Има човек на земята, който
има възможно най-дълго име,

1121
00:52:37,110 --> 00:52:39,920
но това име е константа
Дължина на стойност, нали?

1122
00:52:39,920 --> 00:52:41,980
Той не се променя във всеки смисъл.

1123
00:52:41,980 --> 00:52:45,090
Така че по този начин, ние сме
постига структурата на данните

1124
00:52:45,090 --> 00:52:47,800
че е константно време поглед нагоре.

1125
00:52:47,800 --> 00:52:50,670
Той прави предприемат редица стъпки
в зависимост от дължината на входа,

1126
00:52:50,670 --> 00:52:54,250
но не и числото на името
в структурата на данните.

1127
00:52:54,250 --> 00:52:58,700
Така че, ако можем да удвои броя на имената
следващата година от един милиард до два милиарда,

1128
00:52:58,700 --> 00:53:03,720
констатация Maxwell ще отнеме
точно същия брой седем стъпки

1129
00:53:03,720 --> 00:53:04,650
за да го намери.

1130
00:53:04,650 --> 00:53:08,810
И така, ние като че ли сме постигнали
нашата Светия Граал на времето за работа.

1131
00:53:08,810 --> 00:53:10,860
>> Така след няколко бързи съобщения.

1132
00:53:10,860 --> 00:53:11,850
Quiz нула идва.

1133
00:53:11,850 --> 00:53:14,600
Повече за това на интернет страницата на курса
през следващите няколко дни.

1134
00:53:14,600 --> 00:53:17,120
Понеделник lecture-- това е празник
тук в Харвард в понеделник.

1135
00:53:17,120 --> 00:53:18,850
Това не е в Ню Хейвън,
така че ние сме като класа

1136
00:53:18,850 --> 00:53:20,310
в Ню Хейвън за лекция в понеделник.

1137
00:53:20,310 --> 00:53:22,550
Всичко ще бъде заснет
и поточно както обикновено,

1138
00:53:22,550 --> 00:53:24,900
но нека да приключи днес
с 30 секунди клип

1139
00:53:24,900 --> 00:53:26,910
наречени "Дълбоки мисли"
от Daven Farnham, които

1140
00:53:26,910 --> 00:53:30,850
е вдъхновен миналата година от събота
"Дълбоки мисли" Night Live на

1141
00:53:30,850 --> 00:53:35,700
от Джак Handy, които
Сега трябва да има смисъл.

1142
00:53:35,700 --> 00:53:38,810
>> FILM: И сега, "Deep
Мисли "от Daven Farnham.

1143
00:53:38,810 --> 00:53:42,100

1144
00:53:42,100 --> 00:53:42,870
Hash маса.

1145
00:53:42,870 --> 00:53:45,940

1146
00:53:45,940 --> 00:53:47,660
>> SPEAKER 1: Добре, това е всичко за сега.

1147
00:53:47,660 --> 00:53:48,805
Ще се видим следващата седмица.

1148
00:53:48,805 --> 00:53:55,380

1149
00:53:55,380 --> 00:53:56,680
>> Дъг: За да го видим в действие.

1150
00:53:56,680 --> 00:53:58,304
Така че нека да погледнем, че точно сега.

1151
00:53:58,304 --> 00:53:59,890
Така че тук, имаме сортиран масив.

1152
00:53:59,890 --> 00:54:04,860
>> Иън: Doug, може ли да отида напред и рестартиране
това само за една секунда, моля.

1153
00:54:04,860 --> 00:54:08,562
Добре, камери са подвижен, така че
за действие, когато сте готови, Дъг, OK?

1154
00:54:08,562 --> 00:54:11,020
Дъг: Добре, така че това, което ние
имаме тук е сортиран масив.

1155
00:54:11,020 --> 00:54:13,960
И аз съм оцветен всички елементи
червено, за да покаже, че е в действителност,

1156
00:54:13,960 --> 00:54:14,460
сортиран.

1157
00:54:14,460 --> 00:54:17,960
Така се припомни, че първото нещо, което правим
е ние сортирате лявата половина на масива.

1158
00:54:17,960 --> 00:54:20,630
Тогава ние сортирате правото
половината от масива.

1159
00:54:20,630 --> 00:54:22,830
И ти-да, ти-да, ти-га,
ние ги обедините заедно.

1160
00:54:22,830 --> 00:54:24,520
И ние имаме един напълно сортиран масив.

1161
00:54:24,520 --> 00:54:25,360
Така че това е начина, сортиране чрез сливане работи.

1162
00:54:25,360 --> 00:54:27,109
>> Иън: Уау, чакай, чакай,
нарязани, нарязани, нарязани, нарязани.

1163
00:54:27,109 --> 00:54:30,130
Дъг, не може просто да ти-да, ти-га,
Ya-га, вашия начин чрез сливане на сортиране.

1164
00:54:30,130 --> 00:54:31,970
>> Дъг: Току-що го направих.

1165
00:54:31,970 --> 00:54:32,832
Това е добре.

1166
00:54:32,832 --> 00:54:33,540
Ние сме добре да тръгвам.

1167
00:54:33,540 --> 00:54:34,760
Нека просто да се запази при търкаляне.

1168
00:54:34,760 --> 00:54:35,380
Така или иначе,

1169
00:54:35,380 --> 00:54:37,800
>> Иън: Трябва да се обясни
по-пълно от това.

1170
00:54:37,800 --> 00:54:39,999
Това просто не е достатъчно.

1171
00:54:39,999 --> 00:54:41,790
Дъг: Ian, ние не правим
трябва да се върнем към едно.

1172
00:54:41,790 --> 00:54:42,350
Това е добре.

1173
00:54:42,350 --> 00:54:45,690
Така или иначе, ако продължим с merge--
Ian, ние сме в средата на снимките.

1174
00:54:45,690 --> 00:54:46,612
>> Иън: Знам.

1175
00:54:46,612 --> 00:54:49,320
И ние не можем просто да ти-да, ти-га,
Ya-га, през целия процес.

1176
00:54:49,320 --> 00:54:52,200
Трябва да се обясни как
двете страни се сливат заедно.

1177
00:54:52,200 --> 00:54:53,570
>> Дъг: Но вече сме
обясни как две sides--

1178
00:54:53,570 --> 00:54:55,321
>> Иън: Вие току-що е показано
ги сливане масив.

1179
00:54:55,321 --> 00:54:56,486
Дъг: Те знаят процеса.

1180
00:54:56,486 --> 00:54:57,172
Те са добре.

1181
00:54:57,172 --> 00:54:58,380
Минахме над нея десет пъти.

1182
00:54:58,380 --> 00:55:00,330
>> Иън: Ти просто прескача право върху него.

1183
00:55:00,330 --> 00:55:03,360
Връщаме до един,
Не можеш ли да ти-да, ти-га върху него.

1184
00:55:03,360 --> 00:55:05,480
Добре, обратно към едно.

1185
00:55:05,480 --> 00:55:07,833
>> Дъг: Аз трябва да се върна
през всички стъкла?

1186
00:55:07,833 --> 00:55:08,332
Господи.

1187
00:55:08,332 --> 00:55:11,008

1188
00:55:11,008 --> 00:55:13,004
Това е като шести път, Иън.

1189
00:55:13,004 --> 00:55:13,940
Това е добре.

1190
00:55:13,940 --> 00:55:15,200
>> Иън: Добре.

1191
00:55:15,200 --> 00:55:16,590
Готов ли си?

1192
00:55:16,590 --> 00:55:17,400
Страхотен.

1193
00:55:17,400 --> 00:55:18,950
Action.