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

2
00:00:10,900 --> 00:00:15,860
>> ЗВУЧНИЦИ 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
>> ЗВУЧНИЦИ 1: Добро, така што можеме
динамички да се менува големината.

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
ЗВУЧНИЦИ 1: Да, па ние треба
најмалку двојно повеќе простор.

33
00:01:25,200 --> 00:01:27,700
Всушност, сфатив оваа слика е
дури и малку погрешно,

34
00:01:27,700 --> 00:01:32,200
затоа што на CS50 ИРО во многу модерни
компјутери, покажувач или адреса

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
Но, ајде да се обидеме да canonicalize
работењето прв

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
Таа има int дека ние ќе го наречеме N,
но ние би можеле да го наречеме ништо,

65
00:02:48,790 --> 00:02:51,920
а потоа ѕвезда struct јазол наречен следната.

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
>> ЗВУЧНИЦИ 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
и тоа е причината зошто сме го кажале struct
јазол ѕвезда, ѕвезда означувајќи

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
е да се земе int и тогаш
почеток на поврзани листа,

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

87
00:03:50,430 --> 00:03:52,992
Како прво, за кого мислам дека Дејвид
беше нашите волонтери, во понеделникот,

88
00:03:52,992 --> 00:03:54,700
тој беше посочувајќи на
целата поврзани листа,

89
00:03:54,700 --> 00:03:57,820
тоа е како да сме полагање
Давид како наш аргумент тука.

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
по конвенција е само ќе
да се нарече покажувач, или кон меморија,

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
бидејќи покажувачот кон меморија, е
навистина покажувач, адреса,

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
туку затоа што покажувачот не е покажувач
а не се вистинските struct,

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
не е Н, она што сакам да го направам?

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
оној што го сакате, и трето,
треба да се задржи физички се движат.

123
00:05:52,660 --> 00:05:54,690
Како и како можам да влезете низ листа?

124
00:05:54,690 --> 00:05:57,470
Кога имавме низа вас,
само не како јас плус плус.

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
Јас наместо да кажам
Јас, покажувач, се случува

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
и на крај, јас хит null немање
Пронајдени N уште, јас само return false.

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
Ако не, јас се ажурираат мојата рака,
АКА покажувач, до точка

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
е тип на апстрактен податоци доколку тоа е
не нешто Ц, тоа не е нешто 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
ми даде дефиниција на тип на
на struct внатрешноста на оџакот,

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
>> ПУБЛИКАТА: екстремната десница.

184
00:09:00,740 --> 00:09:01,990
>> ЗВУЧНИЦИ 1: екстремната десница.

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
Добро, јас треба да се направи една
повеќе промени, секако.

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
И навистина Ц не дека имаат функција.

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
иако, ние само треба да го tweak
дефинирањето на нашиот оџак

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
И сè што ми треба да се сместат на бројот
променлива тука во внатрешноста на оваа struct

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
е тоа што на парче меморија јас
добие, тоа се случува да биде соседни.

286
00:13:34,170 --> 00:13:35,378
Таму не се случува да биде празнини.

287
00:13:35,378 --> 00:13:38,576
Значи, ако сум го побарал 50
бајти или 1.000 бајти,

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
Многу doable, но додава комплексност.

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
Стави во ред или dequeue, како да додадете или отстраните,
тоа е само познавач начин на велејќи:

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

312
00:14:38,100 --> 00:14:41,170
Јас само може да си даде struct
дека повторно има низа број е,

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
Сега ќе Стави во ред 50, а потоа
51, а потоа 61, и точка точка точка.

325
00:15:20,150 --> 00:15:21,070
Значи тоа е Стави во ред.

326
00:15:21,070 --> 00:15:23,176
Јас enqueued 50, потоа 51, па 61.

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

328
00:15:25,050 --> 00:15:27,190
освен што треба да се направи една промена.

329
00:15:27,190 --> 00:15:33,680
Јас треба да се ажурира оваа големина, па одам
од нула до еден до 2-3 сега.

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 продавница?

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, кој
беше таму во 05:00

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

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

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
Енти фронт, чија почетна
вредност треба да биде она што?

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

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

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
Је оператор modulo,
знак за процент.

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
Modulo што ќе се користи тука.

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
Туку само прави modulo пет
Веројатно не е доволен,

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
но modulo ќе биде клучна состојка.

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
>> Филм: Еднаш, многу одамна,
имаше еден дечко по име Џек.

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
И Џек Лу покажа полето
каде што се чуваат сите негови кошули,

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
Потоа доаѓа следниот
наутро, а јас до хоп.

429
00:20:03,210 --> 00:20:06,380
Одам во кутија и да добијат
мојата облека од врвот.

430
00:20:06,380 --> 00:20:09,070
Лу брзо сфатија
проблемот со Џек.

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
Знам дека од решението,
рече триумфален гласно.

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
ЗВУЧНИЦИ 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
Проект, има GIGABYTE на меморија или 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 или Линукс,

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
И ако главниот нарекува функцијата
како swap, и swap оди овде.

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
Во реалноста, тоа е сепак
постојат форензички.

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
И така главната не знае некој од работа
она што беше направено во таа swap функција,

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
Значи ова е пример можете да го прочитате
за повеќе детали на Википедија.

533
00:24:41,350 --> 00:24:43,100
Ние ќе ви укаже на
член, ако љубопитни.

534
00:24:43,100 --> 00:24:45,650
Но, има една напад генерално
познат како buffer overflow дека

535
00:24:45,650 --> 00:24:49,570
постои се додека луѓето
имале можност да манипулира

536
00:24:49,570 --> 00:24:53,120
компјутерска меморија, особено во В.
Така што ова е многу произволна програма,

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

538
00:24:55,130 --> 00:24:57,650
Главната во 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
АКА знак ѕвезда, исто
работа, како стринг.

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

550
00:25:24,920 --> 00:25:27,710
А потоа знак C 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
копирани во меморијата вперен во В.

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
>> Ц е на многу ниско ниво јазик.

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
дека ние ќе се генерализира и тука
А. е удар или противници.

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
О 835 С нула осум нула.

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

643
00:30:08,960 --> 00:30:12,460
означување на бајти во вашиот компјутер
меморија, што на Википедија е

644
00:30:12,460 --> 00:30:19,060
предлагачот е во тоа, што ако адреса
од кои горниот лев бајт е 80 С 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
И така на buffer overflow
напад на неговото јадро

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
Инаку т.н. тампон
overflow напад може да се случи.

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
може да има колку деца или
grandkids како тие всушност сакаат,

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
оној, ние може да се имплементира
со struct, само се допаѓа тоа.

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
Значи тоа е како да
имплементира дека во struct.

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
Јас како и едноставно
слепо велат return false.

765
00:35:59,230 --> 00:36:04,050
Ако ми даде ништо, јас сигурно не може да
најдете било кој број Н. Па што друго би можел да

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 е помала од дрво со стрелки
Н, сакам да се концептуално одат лево.

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
и јас сум бил донесен дека врвниот
arrow кој покажуваше надолу.

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
Дрво или е ништовен.

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, или bitmap, или пинг,

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
со форматот на bitmap датотека,

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
Затоа што најверојатно тип А
и Е и јас и О и У многу

908
00:42:51,160 --> 00:42:55,270
почесто отколку како W или П или 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
како Е, работите кои ви се погоди
прв во Тркало на среќата,

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
И ако се потсетиме од одделение
училиште или средно училиште, Morse code.

919
00:43:18,630 --> 00:43:20,400
Morse code има точки
и цртички кои можат да бидат

920
00:43:20,400 --> 00:43:24,270
пренесува заедно со жица како
звуци или сигнали на некој вид.

921
00:43:24,270 --> 00:43:25,930
Но Morse code е супер чист.

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
>> Јас?

929
00:43:44,450 --> 00:43:45,060
Јас?

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
Значи има овој проблем
на Можност за декодираwе со Морс

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
Е е една точка, па ако
види две точки или слушнете две точки,

938
00:44:08,640 --> 00:44:11,254
можеби тоа е два на E или можеби е еден И.

939
00:44:11,254 --> 00:44:13,670
Па ние треба систем кој е
малку повеќе умен од тоа.

940
00:44:13,670 --> 00:44:16,851
Па еден човек по име Хафман години
Пред излезе со токму тоа.

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
составен од само А, Б, Ц на 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
се Е, а три други фреквенции.

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
>> Кои два јазли јас се комбинираат следно?

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
Точка два и 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
>> И уште па што Хофман предложени се применува,
ако сакате да го претставува Б,

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
Ако сакате да се складира
Е, од друга страна, не се

990
00:46:20,970 --> 00:46:26,290
испрати осум битови кои претставуваат Е.
Наместо тоа, пратете што шема на битови?

991
00:46:26,290 --> 00:46:26,890
Еден.

992
00:46:26,890 --> 00:46:30,410
И она што е убаво за ова е
Е дека е најпопуларниот писмо,

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
беше А. И така колку битови
тој го предлага користење за тоа?

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-- па јас сум
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
Еве пет кои претставуваат
A до Ш И ако јас

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
Б оди овде.

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
>> Значи еден начин може да се реши овој е, сите
право, е зафатен, Б е зафатен, Ц е зафатен.

1036
00:48:24,380 --> 00:48:28,880
Одам да го стави во Д. Значи во
прв, јас имаат случаен брз пристап

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
Но, ако тоа не е на А
Студентот го барам,

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
и да се стави како план Б, така да се каже,
или план Д во овој случај, на вредноста

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
со П име или 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
прекрасен каде 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
Хартс оди овде, дијаманти оди овде.

1064
00:49:49,600 --> 00:49:52,180
Исто тука, оди овде,
Д оди овде, Б оди овде.

1065
00:49:52,180 --> 00:49:55,740
Така супер брз гледам-up прозорци, и ако
да се случи да се кандидира во случај

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
>> Така овој вид на глупо,
geeky пред шега години.

1073
00:50:16,880 --> 00:50:19,590
На CS50 hack-а-thon,
кога студентите се провери,

1074
00:50:19,590 --> 00:50:22,040
некои ТФ или CA секоја година
смета дека тоа е смешно да се стави

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
Ако почне вашето име
со Б, оди this-- ред,

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
што е нешто што се нарекува Trie.

1084
00:50:42,400 --> 00:50:47,140
Т-Р-И-E, кои поради некоја причина е кратко
за пребарување, но тоа се вика Trie.

1085
00:50:47,140 --> 00:50:51,389
Па Trie е уште една интересна
амалгам на многу од овие идеи.

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
Тоа е едно дрво со било кој број на деца,
но секое од децата во Trie

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
погледнете во горниот јазол таму, М, е
што укажува на најлевата нешто таму,

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
Но, она што е неверојатно за Trie е
дека, со оглед на поврзани листа, па дури и

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
Јас само да се погледне за М-А-Х-W-Е-Л-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-- Д-А-В-јас-Д чекори.

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
На износот на време ми треба да се најде
M-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
тоа е постојана време погледнете-up.

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
наод Максвел се случува да се земе
точно ист број на седум чекори

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
Квиз нула доаѓа.

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
Џек Практични, која
сега треба да се направи смисла.

1142
00:53:35,700 --> 00:53:38,810
>> Филм: И сега, "Длабоко
Мисли "од Daven Farnham.

1143
00:53:38,810 --> 00:53:42,100

1144
00:53:42,100 --> 00:53:42,870
Хаш табелата.

1145
00:53:42,870 --> 00:53:45,940

1146
00:53:45,940 --> 00:53:47,660
>> ЗВУЧНИЦИ 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
>> Иан: Даг, ќе може да оди напред и да го рестартирате
тоа за само една секунда, ве молам.

1153
00:54:04,860 --> 00:54:08,562
Добро, камери се тркалаат, па
акција секогаш кога ќе бидете подготвени, Даг, во ред?

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
И ти-да, Ya-де, Ya-да,
ние ги спои заедно.

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
Даг: Иан, ние не
треба да се врати во еден.

1172
00:54:41,790 --> 00:54:42,350
Во ред е.

1173
00:54:42,350 --> 00:54:45,690
Значи во секој случај, ако продолжиме со merge--
Иан, ние сме во средината на снимањето.

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
Се враќаме на еден, можете
нели ти-да, Ya-da над неа.

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
Акција.