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

2
00:00:10,900 --> 00:00:15,860
>> СПЕАКЕР 1: Добро, тако да је ово
ЦС50 Ово је крај недеље пет.

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
јер на ЦС50 ИДЕ у много модерног
компјутери, показивач или адреса

35
00:01:32,200 --> 00:01:33,700
није у ствари четири бајта.

36
00:01:33,700 --> 00:01:36,090
То је веома често ово
дана осам бајтова, што

37
00:01:36,090 --> 00:01:38,530
значи дно највише
правоугаоника тамо у стварности

38
00:01:38,530 --> 00:01:40,900
су врста дупло
велика као што сам извући,

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

40
00:01:44,409 --> 00:01:46,700
Сада истовремено, ми смо
још увек говоримо бајтова, зар не?

41
00:01:46,700 --> 00:01:49,140
Ми не нужно говоримо
мегабајта или гигабајта,

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

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

44
00:01:54,510 --> 00:01:57,310
ефикасније ако се у
Чињеница подаци добија већи.

45
00:01:57,310 --> 00:02:00,360
Али хајде да покушамо да цаноницализе
Прве операције

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

47
00:02:02,460 --> 00:02:04,790
Дакле, нешто као повезана
Листа генерално подржава

48
00:02:04,790 --> 00:02:07,514
операције воле делете,
убаците и претрагу.

49
00:02:07,514 --> 00:02:08,639
А шта хоћу да кажем?

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

51
00:02:11,222 --> 00:02:14,287
они или неко други је имплементирао
функције као што су брисање, инсерт,

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

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

54
00:02:18,030 --> 00:02:20,760
Дакле, хајде да кратак поглед
колико смо могли имплементирати

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

56
00:02:24,530 --> 00:02:27,885
>> Дакле, ово је само неки Ц код,
ни комплетан програм

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
Има инт да ћемо звати Н,
али можемо га назвати било шта,

65
00:02:48,790 --> 00:02:51,920
а затим звезда струцт чвор се зове следећи.

66
00:02:51,920 --> 00:02:55,520
И само да буде јасно, да друга
линија, он лине шест, шта је то?

67
00:02:55,520 --> 00:02:57,930
Шта ради за нас?

68
00:02:57,930 --> 00:03:01,044
Зато што свакако изгледа више
Цриптиц од наших уобичајених варијабли.

69
00:03:01,044 --> 00:03:02,740
>> ПУБЛИКА: То чини помери један.

70
00:03:02,740 --> 00:03:04,650
>> СПЕАКЕР 1: То чини помери један.

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

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

73
00:03:11,582 --> 00:03:13,540
Тако да неће
нужно кретање ништа.

74
00:03:13,540 --> 00:03:15,290
Само ће
складиштити вредност, која је

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

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

77
00:03:20,810 --> 00:03:22,370
показивач или адреса.

78
00:03:22,370 --> 00:03:26,390
У реду, тако да сада ако претпоставимо да имамо
ово Н доступни нама, и идемо

79
00:03:26,390 --> 00:03:29,490
претпоставимо да неко други има
убаци гомилу природних бројева

80
00:03:29,490 --> 00:03:30,400
у повезане листе.

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

82
00:03:35,640 --> 00:03:39,040
променљива се зове листа која је
донет овде као параметар,

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

84
00:03:43,120 --> 00:03:45,990
Другим речима, ако сам имплементацији
Функција чија је сврха у животу

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

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

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

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
Ако поинтер-- и сад сам хтео
да радимо оно што смо урадили са студентом

106
00:04:51,820 --> 00:04:57,410
струцтуре-- ако показивач тачка следећу
екуалс-- а, ако показивач тачка Н, једнако

107
00:04:57,410 --> 00:05:02,290
једнак је променљива Н,
Аргумент да је донет у,

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

109
00:05:05,370 --> 00:05:11,020
Нашао сам број н Инсиде оф
један од чворова мог повезане листе.

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
већ зато што показивач није показивач
а не сама стварна струцт,

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

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

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
>> Па, имамо све потребне
синтакса на располагању у Ц. кажем,

158
00:07:50,020 --> 00:07:53,830
дај ми дефиницију типа
струцт унутар стеку,

159
00:07:53,830 --> 00:07:58,030
Ја ћу рећи је низ, олуја са
гомила бројева, а онда величина.

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

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

162
00:08:03,830 --> 00:08:06,317
Дакле, ово је говорећи ми дајте
структура која има низ,

163
00:08:06,317 --> 00:08:09,400
а ја не знам шта је капацитет,
је очигледно нека константа која имам

164
00:08:09,400 --> 00:08:10,858
дефинисан на другом месту, и то је у реду.

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

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

167
00:08:16,700 --> 00:08:21,730
Овај елемент у мом
Структура ће се звати бројеве.

168
00:08:21,730 --> 00:08:24,020
А онда ми је потребан
друга променљива очигледно

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

170
00:08:27,814 --> 00:08:29,730
Ако нема ништа у
стацк, величина је нула,

171
00:08:29,730 --> 00:08:31,420
и то је вредности за смеће у бројкама.

172
00:08:31,420 --> 00:08:33,450
Немам појма шта је унутра још.

173
00:08:33,450 --> 00:08:36,059
>> Дакле, ако желим да гура
нешто на стек,

174
00:08:36,059 --> 00:08:40,780
Претпостављам да позовем функцију пусх, и
Кажем гурати 50, као и број 50,

175
00:08:40,780 --> 00:08:44,090
где би ви предлажете
Ја га нацртати у овом низу?

176
00:08:44,090 --> 00:08:47,124
Постоји пет различитих могућих одговора.

177
00:08:47,124 --> 00:08:48,790
Где желиш да се број 50?

178
00:08:48,790 --> 00:08:51,899
Ако је циљ овде, опет, позовите
Функција Пусх, пролазе у аргумента

179
00:08:51,899 --> 00:08:52,940
од 50, где сам га ставио?

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

181
00:08:55,680 --> 00:08:59,052
Пет поссибле-- 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
И мислим назад у ПСЕТ4, ако сте прочитали
чланак о форензика, ПДФ

243
00:11:37,680 --> 00:11:40,780
да смо имали ви прочитали, или ти
ће прочитати ове недеље ПСЕТ4.

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
Ако кажете гиве ме фиве
НЛХС их позивате бројеве,

264
00:12:32,524 --> 00:12:33,940
То је све што ћеш да га добити.

265
00:12:33,940 --> 00:12:38,790
Тако да ћемо сада да радимо од понедељка, има
способност да изрази решење

266
00:12:38,790 --> 00:12:42,480
ипак, само треба да подесите
дефиниција нашег стацк

267
00:12:42,480 --> 00:12:46,840
да не буде неки хард-цодед низ,
али само за похрану адресу.

268
00:12:46,840 --> 00:12:47,890
>> Зашто је ово?

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

270
00:12:51,690 --> 00:12:53,730
Ја вероватно идем у
морам да питам људске,

271
00:12:53,730 --> 00:12:55,110
колико бројева желиш да сачувате?

272
00:12:55,110 --> 00:12:56,776
Дакле, улаз мора да дође однекуд.

273
00:12:56,776 --> 00:12:59,140
Али када знам да
број, онда ја могу само

274
00:12:59,140 --> 00:13:02,470
користе оно што функционише дати
ми комад меморије?

275
00:13:02,470 --> 00:13:03,580
Могу да користим маллоц.

276
00:13:03,580 --> 00:13:06,710
И могу да кажем било који број
бајтова сам се за ове НТХС желе.

277
00:13:06,710 --> 00:13:10,910
И све што имам да сачувате у бројевима
променљива овде унутар ове струцт

278
00:13:10,910 --> 00:13:13,480
треба да буде шта?

279
00:13:13,480 --> 00:13:18,440
Шта се заправо улази у
бројеви у том сценарију?

280
00:13:18,440 --> 00:13:21,300
Да, показивач на прву
бајт тог комад сећања,

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

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

283
00:13:27,300 --> 00:13:28,890
Само треба да се брине о првом месту.

284
00:13:28,890 --> 00:13:31,530
Јер оно што маллоц гаранције и
моје гаранције оперативног система,

285
00:13:31,530 --> 00:13:34,170
је да је комад меморије И
да, то ће бити суседни.

286
00:13:34,170 --> 00:13:35,378
Неће бити празнине.

287
00:13:35,378 --> 00:13:38,576
Дакле, ако сам тражио 50
бајтова или 1000 бајтова,

288
00:13:38,576 --> 00:13:40,450
сви ћемо бити
бацк то бацк то бацк.

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

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

291
00:13:46,230 --> 00:13:48,660
>> Тако да сада имамо могућност у коду.

292
00:13:48,660 --> 00:13:51,280
Додусе, то ће нас одвести
више времена да пишем ово,

293
00:13:51,280 --> 00:13:55,900
сада могли преусмјерити тај меморију
само чување другу адресу тамо

294
00:13:55,900 --> 00:13:59,060
ако желимо већи или чак
мањи комад меморије.

295
00:13:59,060 --> 00:14:00,170
Дакле, овде на компромис.

296
00:14:00,170 --> 00:14:01,360
Сада долазимо динамику.

297
00:14:01,360 --> 00:14:03,350
Имамо још
цонтигуоуснесс тврдим.

298
00:14:03,350 --> 00:14:05,881
Због маллоц ће нам дати
суседни комад меморије.

299
00:14:05,881 --> 00:14:08,630
Али ово ће бити бол у
врат за нас, програмер,

300
00:14:08,630 --> 00:14:09,770
да заправо кодира горе.

301
00:14:09,770 --> 00:14:10,730
То је само још посла.

302
00:14:10,730 --> 00:14:13,930
Морамо код сличан ономе што сам био
изда малопре.

303
00:14:13,930 --> 00:14:16,120
Врло изводљиво, али додаје комплексност.

304
00:14:16,120 --> 00:14:19,520
И тако време програмер, програмер
Сада је још један ресурс

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

306
00:14:22,520 --> 00:14:24,020
И наравно да постоји ред.

307
00:14:24,020 --> 00:14:26,227
Нећемо ићи у ово
један у много детаља.

308
00:14:26,227 --> 00:14:27,560
Али то је врло слично у духу.

309
00:14:27,560 --> 00:14:31,220
Могао бих провести ред, и
своје одговарајуће операције,

310
00:14:31,220 --> 00:14:35,660
енкуеуе или декуеуе, као што додати или уклонити,
то је само одгајивач начин да се то каже,

311
00:14:35,660 --> 00:14:38,100
енкуеуе или декуеуе, као што следи.

312
00:14:38,100 --> 00:14:41,170
Ја само могу себи дати градитеља,
то опет има низ један број је,

313
00:14:41,170 --> 00:14:44,000
то опет има величину,
али зашто ми сада треба

314
00:14:44,000 --> 00:14:46,940
да пратите предњем делу реда?

315
00:14:46,940 --> 00:14:50,630
Нисам морам да знам
предњи део мог стека.

316
00:14:50,630 --> 00:14:53,570
Па, ако сам опет за
куеуе-- хајде да тешко

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

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
Ја енкуеуед 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
Морам да ажурира ове величине, тако да идем
од нуле до један до два до три.

330
00:15:33,680 --> 00:15:35,760
Како да декуеуе?

331
00:15:35,760 --> 00:15:36,890
Шта се дешава са декуеуе?

332
00:15:36,890 --> 00:15:41,950
Ко би требало да дође са ове листе први
ако је линија на Аппле Сторе?

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

334
00:15:42,780 --> 00:15:44,700
Тако некако је компликованије овај пут.

335
00:15:44,700 --> 00:15:47,880
Док последњи пут је то било супер
лако само ради величина минус један,

336
00:15:47,880 --> 00:15:51,440
Ја се до краја мог низа ефикасно
где су бројеви, отклања 61.

337
00:15:51,440 --> 00:15:52,920
Али ја не желим да уклоните 61.

338
00:15:52,920 --> 00:15:55,030
Желим да се 50, који
Био сам тамо у 5:00

339
00:15:55,030 --> 00:15:56,790
да се построје за
нови иПхоне или шта све не.

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
Али сада Поред децрементинг
величина, управо смо повећајте фронт.

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
они су обично узимају рачунар
наука курсеви на Харварду после ЦС50.

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
И, у ствари, оно што оператер
у Ц вероватно летс

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

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

381
00:17:50,160 --> 00:17:53,160
Дакле, шта је кул о реду,
иако смо стално цртање низова

382
00:17:53,160 --> 00:17:56,520
јер ови попут правих линија, ти ако
врста мисли о овоме као кривљења

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

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

385
00:18:01,590 --> 00:18:05,190
Ви би и даље морати да спроведе
да ментални модел у коду.

386
00:18:05,190 --> 00:18:07,550
Дакле, то није тешко,
на крају, да спроведе,

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

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

389
00:18:15,310 --> 00:18:20,010
а онда негде у мом коду имам
на позив шта функционише да стварно створе

390
00:18:20,010 --> 00:18:23,720
Низ бираних бројева?

391
00:18:23,720 --> 00:18:26,190
Маллоц, или неки сличан
функција, тачно.

392
00:18:26,190 --> 00:18:30,481
Сва питања на гомиле или редовима.

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

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

395
00:18:33,657 --> 00:18:34,240
Добро питање.

396
00:18:34,240 --> 00:18:35,830
Шта модулу би ви користите овде.

397
00:18:35,830 --> 00:18:38,520
Дакле генерално, када се користи
Мод, ти би то урадио

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

399
00:18:40,620 --> 00:18:44,120
Дакле, нешто као пет или капацитета, ако
то је константа, је вероватно укључен.

400
00:18:44,120 --> 00:18:47,100
Али само ради по модулу пет
Вероватно није довољно,

401
00:18:47,100 --> 00:18:51,380
јер морамо да знамо и ми
врап овде или овде или овде.

402
00:18:51,380 --> 00:18:54,160
Дакле, ви сте вероватно такође
желети да укључи

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

404
00:18:57,220 --> 00:19:00,140
Дакле, то је само ово релативно
Једноставна математика израз,

405
00:19:00,140 --> 00:19:02,000
али по модулу ће бити кључни састојак.

406
00:19:02,000 --> 00:19:03,330
>> Дакле, кратки филм, ако хоћете.

407
00:19:03,330 --> 00:19:05,780
Анимација да неки
људи на другом универзитету

408
00:19:05,780 --> 00:19:08,060
саставио које смо
прилагођени за ову расправу.

409
00:19:08,060 --> 00:19:12,630
То укључује Џек учење
Чињенице о редовима и статистика.

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

411
00:19:19,010 --> 00:19:21,890
>> Филм: Једном давно,
је био неки тип по имену Џек.

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
Стално одећу, ЦД,
и књиге у стеку.

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
А можда ваш рачунар или ЦС50
ИД, има гигабајт меморије или РАМ

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
Ваш оперативни систем
Виндовс или Мац ОС или Линук,

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

471
00:21:53,110 --> 00:21:57,110
>> Сада случајно, један од тих
ствари, један од ових сегмената меморије,

472
00:21:57,110 --> 00:21:58,350
назива се стек.

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

474
00:22:01,680 --> 00:22:05,900
да сте назвали
функција, на пример маин.

475
00:22:05,900 --> 00:22:08,410
Подсетимо се да сваки пут имам
Меморија Дравн рачунара,

476
00:22:08,410 --> 00:22:10,640
Увек сам некако извући
пола правоугаоника овде

477
00:22:10,640 --> 00:22:12,520
и не смета говори
шта је горе.

478
00:22:12,520 --> 00:22:15,980
Јер, када се зове главни, ја тврдим
да ти овај делић меморије

479
00:22:15,980 --> 00:22:16,970
да иде доле.

480
00:22:16,970 --> 00:22:20,650
А ако главна зове функција
као свап, и замена иде овде.

481
00:22:20,650 --> 00:22:23,720
И испоставило се да је
где је заврши.

482
00:22:23,720 --> 00:22:26,277
На нечега што се зове гомила
унутар меморије рачунара.

483
00:22:26,277 --> 00:22:28,360
Сада на крају дана,
ово је само бави.

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

485
00:22:30,680 --> 00:22:33,130
Али ако мислите о томе
као овај објекат правоугаоне,

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

487
00:22:35,130 --> 00:22:37,180
лаиеринг нови комад меморије.

488
00:22:37,180 --> 00:22:41,700
Дајемо ту функцију кришка
властитог меморије за рад.

489
00:22:41,700 --> 00:22:44,490
>> И сетим да је то важно.

490
00:22:44,490 --> 00:22:46,400
Јер ако немате
нешто као свап

491
00:22:46,400 --> 00:22:51,610
и две локалне променљиве као што су А и Б и
мењамо те вредности од једног и два

492
00:22:51,610 --> 00:22:55,130
да два и опозива,
када размена врати,

493
00:22:55,130 --> 00:22:58,330
то је као да овај комад
меморије је управо отишао.

494
00:22:58,330 --> 00:23:00,080
У стварности, то је још увек
тамо форензички.

495
00:23:00,080 --> 00:23:01,940
И нешто је још увек у ствари тамо.

496
00:23:01,940 --> 00:23:05,410
Али концептуално, то је као
Иако је потпуно нестао.

497
00:23:05,410 --> 00:23:10,910
И тако главни не знам ништа о раду
које је урађено у тој свап функцији,

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

499
00:23:14,890 --> 00:23:17,790
Сада, основна решење
да тај проблем са свап

500
00:23:17,790 --> 00:23:19,970
пролази ствари у по адреси.

501
00:23:19,970 --> 00:23:23,250
Али испоставило се, такође, шта је
се дешава изнад тог дела

502
00:23:23,250 --> 00:23:26,330
правоугаоника све ово време је
ипак тамо нема више меморије горе.

503
00:23:26,330 --> 00:23:28,790
А када динамички
доделите меморију,

504
00:23:28,790 --> 00:23:32,020
да ли је унутар ГетСтринг који
смо радили за вас у ЦС50

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
То је исто РАМ-а.

511
00:23:44,285 --> 00:23:45,160
То је иста меморија.

512
00:23:45,160 --> 00:23:49,080
То је само РАМ то до
тамо уместо овде.

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

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
Главни у аргц Чар стар аргв.

539
00:24:57,650 --> 00:24:59,830
Дакле, то је програм који узима
командне линије аргументи.

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

541
00:25:03,620 --> 00:25:04,610
И испуњава неке у шта?

542
00:25:04,610 --> 00:25:05,490
Аргв једног.

543
00:25:05,490 --> 00:25:09,320
Тако да прелази у Ф год
реч је да је корисник откуца

544
00:25:09,320 --> 00:25:11,500
на линији, након што је
Име програма уопште.

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

546
00:25:15,730 --> 00:25:16,680
>> Дакле, шта је Ф?

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

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
А онда цхар ц 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
Baš tako.

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
у адресу указао на Ц. Али Ц
је само превентивно даје као 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
Тако да показивач који ће да сторе--
а тој локалној аргумент који је

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
Горња лева је Ц носач нула и
у доњем десном један је Ц носач 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 или Ц носач 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
В-е-л-л-о обрнута коса црта нула, завршава у
те 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
тако да улаз на корисника цлобберс
или преписује ту црвену део,

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
И тако се бафера
Напад у својој сржи

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

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

657
00:30:55,320 --> 00:30:59,330
да проверите дужину проклети било којег
низови да смо манипулише.

658
00:30:59,330 --> 00:31:00,750
Дакле, да би било јасно, шта је поправити?

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

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

661
00:31:08,000 --> 00:31:10,620
Шта још треба да се ради на
спречи овај напад у потпуности?

662
00:31:10,620 --> 00:31:14,110
Не желим да кажем само слепо
да копирате онолико бајтова

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

664
00:31:16,140 --> 00:31:18,910
Хоћу да кажем, копирање и
многи бајтова као у бару

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

666
00:31:24,090 --> 00:31:27,450
Зато ми треба неки ако услов
да не проверите дужину бара,

667
00:31:27,450 --> 00:31:32,800
али ако прелази 12, ми смо само хард код
12 као максимално могуће растојање.

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

669
00:31:35,910 --> 00:31:38,451
На дну тих слајдове,
Ако сте радознали да сазнате више

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

671
00:31:41,200 --> 00:31:44,550
>> Али сада, међу цени
плаћени овде је неефикасности.

672
00:31:44,550 --> 00:31:46,680
Дакле, то је било брзо
Низак ниво поглед на оно што

673
00:31:46,680 --> 00:31:49,709
Проблеми могу настати сада да смо
имају приступ меморији рачунара.

674
00:31:49,709 --> 00:31:51,750
Али друга ми проблема
већ наишао је у понедељак

675
00:31:51,750 --> 00:31:53,800
је само неефикасност
од повезане листе.

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

677
00:31:56,019 --> 00:31:57,560
Ми више нема сусједном низ.

678
00:31:57,560 --> 00:31:58,980
Ми немамо случајан приступ.

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

680
00:32:00,710 --> 00:32:04,590
Ми буквално морамо да користимо вхиле петља
као један сам написао пре неколико тренутака.

681
00:32:04,590 --> 00:32:09,740
Али у понедељак, тврдио смо да можемо
црееп врати у царство ефикасности

682
00:32:09,740 --> 00:32:13,040
постизање нешто што је
логаритамске можда, или још најбоље,

683
00:32:13,040 --> 00:32:16,120
можда чак и нешто што је
тзв константа тиме.

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

685
00:32:19,840 --> 00:32:22,210
и тхреадинг ствари сами?

686
00:32:22,210 --> 00:32:23,960
Па, претпостављам да
Овде, ово је гомила

687
00:32:23,960 --> 00:32:27,170
бројева који желимо да Чувати на
структура података и ефикасно претраживање.

688
00:32:27,170 --> 00:32:30,960
Ми апсолутно може ревинд у недељу
два, баци их у низ,

689
00:32:30,960 --> 00:32:33,150
иу њима помоћу бинарног претрагу.

690
00:32:33,150 --> 00:32:34,040
Завади па владај.

691
00:32:34,040 --> 00:32:37,720
А у ствари сте написали
бинарни тражи у ПСЕТ3,

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
У принципу, трее-- и
твоји родитељи, бабе и деде

719
00:33:54,990 --> 00:33:57,640
могу имати онолико деце или
унуци као они заправо желе,

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

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

722
00:34:05,480 --> 00:34:08,496
И то је лепо имовина,
јер ако је капом по двоје,

723
00:34:08,496 --> 00:34:10,620
ћемо бити у стању да
се мало лог базу два

724
00:34:10,620 --> 00:34:11,975
Акција се овде дешава на крају.

725
00:34:11,975 --> 00:34:13,350
Дакле, имамо нешто логаритамске.

726
00:34:13,350 --> 00:34:14,558
Али више о томе у овом тренутку.

727
00:34:14,558 --> 00:34:19,810
Тражи дрво значи да су бројеви
уређено тако да је лева детета

728
00:34:19,810 --> 00:34:22,429
вредност већа од корена.

729
00:34:22,429 --> 00:34:26,010
И његово право дете
већи од корена.

730
00:34:26,010 --> 00:34:29,290
Другим речима, ако узмете било који од
чворови, кругови у овој слици,

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

732
00:34:31,840 --> 00:34:34,739
прво треба бити мања од,
други треба да буде већа.

733
00:34:34,739 --> 00:34:36,159
Дакле, разум цхецк 55.

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

735
00:34:37,780 --> 00:34:38,620
То је мање од.

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

737
00:34:40,929 --> 00:34:41,783
То је већи од.

738
00:34:41,783 --> 00:34:43,199
И то је рекурзивна дефиниција.

739
00:34:43,199 --> 00:34:46,480
Можемо проверити сваки од ових
чворова и исти образац ће одржати.

740
00:34:46,480 --> 00:34:49,389
>> Дакле, оно што је лепо у А
бинарно стабло претраге је

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

742
00:34:52,204 --> 00:34:54,620
И иако смо бацање
много објеката у твој,

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

744
00:34:56,560 --> 00:35:00,570
Синтакса је и даље волшебни сигурно,
али садржај чвор у ово

745
00:35:00,570 --> 00:35:02,786
цонтект-- и чувамо
користи реч чвор,

746
00:35:02,786 --> 00:35:04,910
да ли је правоугаоник
на екрану или круга,

747
00:35:04,910 --> 00:35:08,970
то је само неки генерички контејнер,
у овом случају дрвета, као што је овај

748
00:35:08,970 --> 00:35:11,780
видели смо, морамо цео број
у сваком од чворова

749
00:35:11,780 --> 00:35:15,460
и онда морам два показивача Указујући
на левој дете и десне детета,

750
00:35:15,460 --> 00:35:16,590
респективно.

751
00:35:16,590 --> 00:35:20,730
Па тако бисмо могли
спроводи то у Струцт.

752
00:35:20,730 --> 00:35:22,315
И како би га спровести у коду?

753
00:35:22,315 --> 00:35:26,730
Па, узмимо брзо
погледај овог малог примера.

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

755
00:35:29,820 --> 00:35:33,510
А ако моја функција за бинарни
претрага дрво се зове претрага,

756
00:35:33,510 --> 00:35:36,980
и то узима два аргумента,
цео број Н и показивач

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

758
00:35:41,400 --> 00:35:43,482
Како да идем о потрази за Н?

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

762
00:35:54,279 --> 00:35:55,070
То не може бити, зар не?

763
00:35:55,070 --> 00:35:56,870
Ако сам прошлост нулл,
нема ништа.

764
00:35:56,870 --> 00:35:59,230
Могао бих као и само
слепо кажу ретурн фалсе.

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

766
00:36:04,050 --> 00:36:04,750
цхецк сада?

767
00:36:04,750 --> 00:36:12,830
Ја ћу рећи и друго ако је Н
мање него оно што је на дрвету чвор

768
00:36:12,830 --> 00:36:16,300
да сам предао Н вриједност.

769
00:36:16,300 --> 00:36:20,270
Другим речима, ако је број сам
лоокинг фор, Н, мањи од чвора

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

775
00:36:35,960 --> 00:36:38,590
Како да изражавају сеарцхинг оставио?

776
00:36:38,590 --> 00:36:41,560
Да буде јасно, ако је ово
слика у питању,

777
00:36:41,560 --> 00:36:44,612
и ја сам положио је највиши
арров да је окренут надоле.

778
00:36:44,612 --> 00:36:45,570
То је моја дрво показивач.

779
00:36:45,570 --> 00:36:48,060
Ја сам показујући на корен дрвета.

780
00:36:48,060 --> 00:36:52,100
И тражим рецимо, за
број 44, произвољно.

781
00:36:52,100 --> 00:36:55,300
Да ли је 44 или мање од
већи од 55 оцигледно?

782
00:36:55,300 --> 00:36:56,360
Дакле, то је мање од.

783
00:36:56,360 --> 00:36:58,760
И то ако услов важи.

784
00:36:58,760 --> 00:37:03,981
Дакле, концептуално, шта хоћу да
тражење следеће ако сам у потрази за 44?

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

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

787
00:37:08,310 --> 00:37:11,100
>> Тачно, желим да
тражење леви дете,

788
00:37:11,100 --> 00:37:12,789
или лево под-стабло ову слику.

789
00:37:12,789 --> 00:37:14,830
И у ствари, пустите ме да прођем
слика доле

790
00:37:14,830 --> 00:37:17,770
за тренутак, јер
Ја не могу огребати ово.

791
00:37:17,770 --> 00:37:21,150
Ако овде се крећу од 55, и
Знам да је вредност 44

792
00:37:21,150 --> 00:37:23,180
Ја тражим је да
лева, некако је

793
00:37:23,180 --> 00:37:26,010
Као цепања телефонског именика у
пола или кидање дрво на пола.

794
00:37:26,010 --> 00:37:29,660
Ја више не морају да брину о
цела ова половина дрвета.

795
00:37:29,660 --> 00:37:33,270
Па ипак, радознало во однос на
структура, ова ствар овде која

796
00:37:33,270 --> 00:37:36,682
почиње са 33, који сам по себи
је бинарно стабло претраге.

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

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

799
00:37:41,707 --> 00:37:44,540
Ви можда има дрво које је ово
велика, али свако од своје деце

800
00:37:44,540 --> 00:37:46,870
представља дрво само мало мањи.

801
00:37:46,870 --> 00:37:50,910
Уместо тога буде деда
или бака, сад је само мама

802
00:37:50,910 --> 00:37:54,300
или-- Не могу говоре-- не мама
или тата, то би било чудно.

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
И сеарцх фор Н у дрвету стрелице лево
иф Н е већи од вредности

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
прође Н ово и рекурзивно претрагу
суб-дрво и само повратак

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
Али претпоставимо да је ово чува као
ГИФ, или ЈПЕГ или Битмап, или пинг,

837
00:39:31,930 --> 00:39:34,240
свака графички формат датотеке
са којим сте упознати,

838
00:39:34,240 --> 00:39:36,460
од којих су неки смо
играње са у ПСЕТ4.

839
00:39:36,460 --> 00:39:41,550
Ово не изгледа исплати да сачувате
црна пиксела, црна пиксела, црна пиксела,

840
00:39:41,550 --> 00:39:44,790
тачка, тачка, тачка, цела гомила
црни пиксели за прву Сцанлине,

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
Baš tako.

855
00:40:21,970 --> 00:40:24,550
Зашто не пре него се сетим
боја сваког пиксела проклетом

856
00:40:24,550 --> 00:40:28,200
баш као да радите у ПСЕТ4
са форматом битмап датотеке,

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

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

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
Па, сваки од ликова у
АСЦИИ се један бајт, или осам бита.

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
чешће него као В или К или З,
у зависности од језика на којем

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
Zašto?

916
00:43:10,950 --> 00:43:13,130
Јер, ми ћемо само да
да их користите ређе.

917
00:43:13,130 --> 00:43:15,838
>> Па, испоставља се да има
било покушаја да то урадите.

918
00:43:15,838 --> 00:43:18,630
А ако се сећате из разреда
школа или гимназија, Морзеова азбука.

919
00:43:18,630 --> 00:43:20,400
Морзеова азбука има тачке
и црте то може бити

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

921
00:43:24,270 --> 00:43:25,930
Али Морзеова азбука је супер чист.

922
00:43:25,930 --> 00:43:29,010
То је нека врста бинарном систему у
да ли имате тачке или црте.

923
00:43:29,010 --> 00:43:30,977
Али ако видиш, на пример, два тачке.

924
00:43:30,977 --> 00:43:33,810
Или, ако мислите назад на оператора
који иде овако бип, бип, бип,

925
00:43:33,810 --> 00:43:36,760
бип, ударање мало окидач
који преноси сигнал,

926
00:43:36,760 --> 00:43:40,360
ако вас, прималац, добија два
тачака, коју поруку сте добили?

927
00:43:40,360 --> 00:43:43,490
Потпуно произвољна.

928
00:43:43,490 --> 00:43:44,450
>> Ја?

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

930
00:43:45,060 --> 00:43:47,500
Или шта о-- или ја?

931
00:43:47,500 --> 00:43:49,570
Можда је то била само два Е у праву?

932
00:43:49,570 --> 00:43:52,480
Тако да је овај проблем
од Могућност декодирања са Морсе

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
можда је два Е или можда један И.

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
састављена од само А, Б, Ц је Д'с и Е је,
али има доста вишка запослених овде.

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
Дакле, ако сте заиста рачунати од свих
А, б, ц је, Д'с, и Е је, ево

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
фреквенције као покретним зарезом
вредност, или можете да га користите је Н, такође,

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 ас
АСЦИИ што је осам читаве бита,

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

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
Ово је-- а ја ћу махати
моја рука на то како вас

1003
00:46:52,538 --> 00:46:55,570
Можда спроводи ово као Ц структуре.

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

1013
00:47:25,960 --> 00:47:30,330
Срца, хеартс-- па сам
буцкетизинг све улаза овде.

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
ствари из спољашњег [? Анненберг?], Тако

1027
00:47:57,950 --> 00:48:00,289
Овде је пет који заступају
А до З. А ако ја

1028
00:48:00,289 --> 00:48:03,580
види студента чије име почиње са А,
Ја ћу његову или њену квиз ставио тамо.

1029
00:48:03,580 --> 00:48:08,850
Ако неко почне са Ц, тамо,
А-- заправо, није хтео то да урадим.

1030
00:48:08,850 --> 00:48:10,060
Б иде овамо.

1031
00:48:10,060 --> 00:48:13,390
Дакле, имам А и Б и Ц. И
Сада овде је још један студент.

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

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
Стављање где је Год требало да буде?

1053
00:49:12,840 --> 00:49:14,810
Зашто не само да
изван [? Анненберг?],

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

1066
00:49:55,740 --> 00:49:59,429
где сте имам судара, два
људи са истим именом, па онда

1067
00:49:59,429 --> 00:50:00,970
почнете да их повезује.

1068
00:50:00,970 --> 00:50:03,900
И можда би држати их поредани
по абецедном реду, можда не.

1069
00:50:03,900 --> 00:50:05,900
Али барем сада имамо динамику.

1070
00:50:05,900 --> 00:50:10,250
Дакле, с једне стране имамо супер брз
константа време и врсту линеарног времена

1071
00:50:10,250 --> 00:50:14,110
укључени ако овим повезаних листи
почну да се мало дуго.

1072
00:50:14,110 --> 00:50:16,880
>> Дакле, ова врста глупо,
Гееки јоке пре много година.

1073
00:50:16,880 --> 00:50:19,590
На ЦС50 Хацк-А-Тхон,
када су студенти цхецк ин,

1074
00:50:19,590 --> 00:50:22,040
неки РЦ или ЦА сваке године
мисли да је смешно да трпим

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

1078
00:50:31,110 --> 00:50:33,290
то је смешно можда касније у семестру.

1079
00:50:33,290 --> 00:50:36,420
Али постоји и други
начин да то урадите, превише.

1080
00:50:36,420 --> 00:50:37,410
Врати се на то.

1081
00:50:37,410 --> 00:50:38,600
>> Тако да је ово структура.

1082
00:50:38,600 --> 00:50:40,420
А ово је наша последња
структура за данас,

1083
00:50:40,420 --> 00:50:42,400
што је нешто што се зове трие.

1084
00:50:42,400 --> 00:50:47,140
Т-Р-И-Е, који из неког разлога је кратко
за проналажење, али то се зове трие.

1085
00:50:47,140 --> 00:50:51,389
Дакле, трие је још један занимљив
мешавина много ових идеја.

1086
00:50:51,389 --> 00:50:52,930
То је дрво, које смо раније видели.

1087
00:50:52,930 --> 00:50:54,180
То није бинарно стабло претраге.

1088
00:50:54,180 --> 00:50:58,410
То је дрво са било којим бројем деце,
али сваки од деце у Трие

1089
00:50:58,410 --> 00:51:00,090
је низ.

1090
00:51:00,090 --> 00:51:04,790
Низ величине, рецимо, 26 или можда 27
Ако желите да подржите хипхенатед имена

1091
00:51:04,790 --> 00:51:06,790
или апострофа у именима људи.

1092
00:51:06,790 --> 00:51:08,280
>> И то је структура података.

1093
00:51:08,280 --> 00:51:10,290
И ако погледате одозго
до дна, као да вас

1094
00:51:10,290 --> 00:51:13,710
погледамо горњи чвор тамо, М, је
указујући на крајњој левој ствари тамо,

1095
00:51:13,710 --> 00:51:17,665
који је затим А, Кс, В, Е, Л, Л. Тхис ис
само структура података која произвољно

1096
00:51:17,665 --> 00:51:19,120
је чување имена људи.

1097
00:51:19,120 --> 00:51:25,720
И Максвел је чува само следеће
пут од низа до низа до низа.

1098
00:51:25,720 --> 00:51:30,050
Али оно што је невероватно о трие је
да, док повезане листе, па чак и

1099
00:51:30,050 --> 00:51:34,520
низ, најбољи који смо икада добили је
линеарног времена или логаритамске време у потрази

1100
00:51:34,520 --> 00:51:35,600
неко горе.

1101
00:51:35,600 --> 00:51:40,530
У овој структури података у Трие, ако
моја структура података има само једно име у њој

1102
00:51:40,530 --> 00:51:43,720
и ја тражим Маквелл, ја сам
ће га наћи прилично брзо.

1103
00:51:43,720 --> 00:51:47,910
Ја гледам за М-А-Кс-В-Е-Л-Л. Ako
ова структура података, с друге стране,

1104
00:51:47,910 --> 00:51:51,830
ако је Н је милион, ако постоји
милион имена у овом структуром података,

1105
00:51:51,830 --> 00:51:57,100
Максвел је и даље ће бити
видљив након само П-А-Кс-Ш-Е-Л-Л

1106
00:51:57,100 --> 00:51:58,090
кораци.

1107
00:51:58,090 --> 00:52:01,276
Анд Давид-- Д-А-В-И-Д корака.

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
Износ време ми је потребно да нађемо
М-А-Кс-Е-е-л-Л у овој структури података је

1114
00:52:20,135 --> 00:52:22,260
пропорционална није до
величини објекта података,

1115
00:52:22,260 --> 00:52:25,930
већ са дужином имена.

1116
00:52:25,930 --> 00:52:28,440
А реално
имена гледамо горе

1117
00:52:28,440 --> 00:52:29,970
никада неће бити луди дуго.

1118
00:52:29,970 --> 00:52:32,600
Можда неко има 10 карактера
наме, 20 име карактера.

1119
00:52:32,600 --> 00:52:33,900
То је свакако коначно, зар не?

1120
00:52:33,900 --> 00:52:37,110
Постоји људско на Земљи који
има најдужи могући име,

1121
00:52:37,110 --> 00:52:39,920
али то име је константа
Дужина вредност, зар не?

1122
00:52:39,920 --> 00:52:41,980
Она не варира у било ком смислу.

1123
00:52:41,980 --> 00:52:45,090
Дакле, на овај начин, ми смо
остварили структуру података

1124
00:52:45,090 --> 00:52:47,800
То је константна време лоок-уп.

1125
00:52:47,800 --> 00:52:50,670
То се предузму низ корака
зависно од дужине улаз,

1126
00:52:50,670 --> 00:52:54,250
али не и број имена
у структури података.

1127
00:52:54,250 --> 00:52:58,700
Дакле, ако удвостручити број имена
наредне године од милијарду до две милијарде,

1128
00:52:58,700 --> 00:53:03,720
налаз Максвел ће узети
потпуно исти број седам корака

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
У понедељак лецтуре-- То је празник
овде на Харварду у понедељак.

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
називају "Дееп Тхоугхтс"
од Давен Фарнама, који

1140
00:53:26,910 --> 00:53:30,850
је инспирисан прошле године у суботу
Нигхт Ливе "је Дееп Тхоугхтс"

1141
00:53:30,850 --> 00:53:35,700
Јацк Ханди, који
би сада смисла.

1142
00:53:35,700 --> 00:53:38,810
>> ФИЛМ: А сада, "Дубоко
Мисли "по Давен Фарнама.

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
А иа-Да иа-Да иа-Да,
их спојити заједно.

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
Даг, не можеш само Иа-Да иа-Да,
Иа-Да, свој пут кроз стапања врсте.

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

1174
00:54:45,690 --> 00:54:46,612
>> Иан: Знам.

1175
00:54:46,612 --> 00:54:49,320
И не можемо само Иа-Да иа-Да,
Иа-Да, кроз цео процес.

1176
00:54:49,320 --> 00:54:52,200
Морате да објасни како је
Две стране се заједно спојили.

1177
00:54:52,200 --> 00:54:53,570
>> Даг: Али већ смо
објаснио како два сидес--

1178
00:54:53,570 --> 00:54:55,321
>> Иан: Управо сте приказано
им Стапање низ.

1179
00:54:55,321 --> 00:54:56,486
Даг: Знају процес.

1180
00:54:56,486 --> 00:54:57,172
Они су добро.

1181
00:54:57,172 --> 00:54:58,380
Прешли смо преко њега десет пута.

1182
00:54:58,380 --> 00:55:00,330
>> Иан: Само Прескочио њега.

1183
00:55:00,330 --> 00:55:03,360
Враћамо се на један, ви
не можеш Иа-Да иа-да преко њега.

1184
00:55:03,360 --> 00:55:05,480
У реду, назад на један.

1185
00:55:05,480 --> 00:55:07,833
>> Даг: Морам да се вратим
кроз све слајдове?

1186
00:55:07,833 --> 00:55:08,332
Боже.

1187
00:55:08,332 --> 00:55:11,008

1188
00:55:11,008 --> 00:55:13,004
То је као шести пут, Иан.

1189
00:55:13,004 --> 00:55:13,940
Уреду је.

1190
00:55:13,940 --> 00:55:15,200
>> Иан: У реду.

1191
00:55:15,200 --> 00:55:16,590
Јесте ли спремни?

1192
00:55:16,590 --> 00:55:17,400
Велики.

1193
00:55:17,400 --> 00:55:18,950
Акција.