1
00:00:00,000 --> 00:00:11,860

2
00:00:11,860 --> 00:00:13,120
>> СПИКЕР 1: У реду, тако да смо се вратили.

3
00:00:13,120 --> 00:00:14,480
Добродошли у ЦС50.

4
00:00:14,480 --> 00:00:16,510
Ово је крај недеље седам.

5
00:00:16,510 --> 00:00:20,200
Дакле, подсетити да последњи пут, почели смо
гледа мало софистициранији

6
00:00:20,200 --> 00:00:21,100
структуре података.

7
00:00:21,100 --> 00:00:25,110
Пошто до сада, сви смо заиста имали
на располагању је ово, низ.

8
00:00:25,110 --> 00:00:29,340
>> Али пре него што је одбаците као низ не
све то интересантно, што је заиста

9
00:00:29,340 --> 00:00:33,570
заправо, шта су неки од
плусева ове једноставне података

10
00:00:33,570 --> 00:00:34,560
структура до сада?

11
00:00:34,560 --> 00:00:36,110
Шта је то добро?

12
00:00:36,110 --> 00:00:39,450
До сада, као што смо видели?

13
00:00:39,450 --> 00:00:42,540
Шта имаш?

14
00:00:42,540 --> 00:00:44,028
Ништа.

15
00:00:44,028 --> 00:00:45,020
>> СТУДЕНТ: [ИНАУДИБЛЕ].

16
00:00:45,020 --> 00:00:45,395
>> СПИКЕР 1: Шта је то?

17
00:00:45,395 --> 00:00:46,410
>> СТУДЕНТ: [ИНАУДИБЛЕ].

18
00:00:46,410 --> 00:00:47,000
>> СПИКЕР 1: Фиксна величина.

19
00:00:47,000 --> 00:00:51,260
У реду, па зашто је фиксна величина добра, иако?

20
00:00:51,260 --> 00:00:53,180
>> СТУДЕНТ: [ИНАУДИБЛЕ].

21
00:00:53,180 --> 00:00:56,240
>> СПИКЕР 1: У реду, тако да је ефикасан у
осећај да можете доделити

22
00:00:56,240 --> 00:01:00,070
фиксни износ од простора, и надам се да
Управо толико

23
00:01:00,070 --> 00:01:01,180
простора колико желите.

24
00:01:01,180 --> 00:01:02,720
Дакле, то би могао да буде апсолутно плус.

25
00:01:02,720 --> 00:01:06,530
>> Оно што је још горе страна низа?

26
00:01:06,530 --> 00:01:07,610
Да?

27
00:01:07,610 --> 00:01:08,750
>> СТУДЕНТ: [ИНАУДИБЛЕ].

28
00:01:08,750 --> 00:01:09,550
>> СПИКЕР 1: Сви - жао?

29
00:01:09,550 --> 00:01:11,270
>> СТУДЕНТ: [ИНАУДИБЛЕ].

30
00:01:11,270 --> 00:01:13,620
>> СПИКЕР 1: Све кутије у меморији
или један поред другог.

31
00:01:13,620 --> 00:01:15,220
И то је корисно - зашто?

32
00:01:15,220 --> 00:01:15,970
То је сасвим тачно.

33
00:01:15,970 --> 00:01:18,611
Али како можемо искористити ту истину?

34
00:01:18,611 --> 00:01:21,500
>> СТУДЕНТ: [ИНАУДИБЛЕ].

35
00:01:21,500 --> 00:01:24,490
>> СПИКЕР 1: Управо тако, можемо да пратимо
где је све само знајући

36
00:01:24,490 --> 00:01:28,560
једна адреса, односно адреса
Први бајт тог меморију.

37
00:01:28,560 --> 00:01:30,420
Или у случају ниске,
адреса првог

38
00:01:30,420 --> 00:01:31,460
Чар у том низу.

39
00:01:31,460 --> 00:01:33,330
А одатле, можемо наћи
крај низа.

40
00:01:33,330 --> 00:01:35,710
Можемо наћи други елемент,
Трећи елемент, и тако даље.

41
00:01:35,710 --> 00:01:38,740
>> И тако фенси начин да се опише то
карактеристика је да нам дају низови

42
00:01:38,740 --> 00:01:40,020
директног приступа.

43
00:01:40,020 --> 00:01:44,330
Само помоћу угласте заграде
нотација и број, можете да пређете на

44
00:01:44,330 --> 00:01:48,070
специфичан елемент у низу
у сталном времену, Биг О

45
00:01:48,070 --> 00:01:49,810
једног, да тако кажем.

46
00:01:49,810 --> 00:01:51,080
>> Али ту је било и неки недостаци.

47
00:01:51,080 --> 00:01:53,110
Шта низ не баш лако?

48
00:01:53,110 --> 00:01:55,810

49
00:01:55,810 --> 00:01:57,170
Оно што није добро?

50
00:01:57,170 --> 00:01:58,810
>> СТУДЕНТ: [ИНАУДИБЛЕ].

51
00:01:58,810 --> 00:01:59,860
>> СПИКЕР 1: Шта је то?

52
00:01:59,860 --> 00:02:00,530
>> СТУДЕНТ: [ИНАУДИБЛЕ].

53
00:02:00,530 --> 00:02:01,460
>> СПИКЕР 1: Проширење у величини.

54
00:02:01,460 --> 00:02:04,800
Тако мана низу су
управо супротно од онога што

55
00:02:04,800 --> 00:02:05,540
позитивних су.

56
00:02:05,540 --> 00:02:07,610
Дакле, једна од мана је
да је фиксне величине.

57
00:02:07,610 --> 00:02:09,400
Тако да стварно не могу да расте.

58
00:02:09,400 --> 00:02:13,510
Можете да прерасподели већи комад
меморије, а затим померите старе елементе

59
00:02:13,510 --> 00:02:14,460
у нови низ.

60
00:02:14,460 --> 00:02:18,060
А онда слободно стари низ, за
пример, коришћењем маллоц или сличну

61
00:02:18,060 --> 00:02:21,180
Функција се зове реаллоц, који
поново додељује меморија.

62
00:02:21,180 --> 00:02:25,490
>> Реаллоц, као страну, покушава да вам да
меморија која је поред низа

63
00:02:25,490 --> 00:02:26,610
које већ имате.

64
00:02:26,610 --> 00:02:28,740
Али можда се ствари
укупно око.

65
00:02:28,740 --> 00:02:30,710
Али укратко, то је скупо, зар не?

66
00:02:30,710 --> 00:02:33,440
Јер ако имате комад меморије
ове величине, али ви стварно желите један

67
00:02:33,440 --> 00:02:36,710
ове величине, а желите да сачувате
оригинални елементи, имате

68
00:02:36,710 --> 00:02:40,510
отприлике линеарно време процес удвајања
то треба да се догоди из

69
00:02:40,510 --> 00:02:41,900
старо за ново низ.

70
00:02:41,900 --> 00:02:44,630
А реалност поставља радом
систем поново и поново и

71
00:02:44,630 --> 00:02:48,340
поново за велике комаде меморије може да почне
да вас коштати мало времена и.

72
00:02:48,340 --> 00:02:52,250
Тако да је и благослов и проклетство у
прикрије, чињеницу да ови низови

73
00:02:52,250 --> 00:02:53,860
су фиксне величине.

74
00:02:53,860 --> 00:02:56,790
Али ако уместо тога увести нешто
овако, коју смо назвали повезана

75
00:02:56,790 --> 00:03:00,580
листа, добијамо неколико позитивних и
неколико мана овде.

76
00:03:00,580 --> 00:03:05,780
>> Тако повезана листа је једноставно података
структура коју чине Ц Структуре у ово

77
00:03:05,780 --> 00:03:09,850
случај, где струцт, подсетимо, је само
контејнер за један или више специфичних

78
00:03:09,850 --> 00:03:11,100
Типови променљивих.

79
00:03:11,100 --> 00:03:16,110
У том случају, шта типове података
Чини се да унутар структуре попунити да

80
00:03:16,110 --> 00:03:17,600
Последњи пут када смо се зове чвор?

81
00:03:17,600 --> 00:03:19,380
Сваки од ових правоугаоника је чвор.

82
00:03:19,380 --> 00:03:22,660
И сваки од мањих правоугаоника
у њему је тип података.

83
00:03:22,660 --> 00:03:25,300
Које врсте смо рекли
су у понедељак?

84
00:03:25,300 --> 00:03:26,478
Да?

85
00:03:26,478 --> 00:03:27,870
>> СТУДЕНТ: [ИНАУДИБЛЕ].

86
00:03:27,870 --> 00:03:30,721
>> СПИКЕР 1: променљива и показивач, или
тачније, инт, за н,

87
00:03:30,721 --> 00:03:32,180
и показивач на дну.

88
00:03:32,180 --> 00:03:35,360
И оних десити да се 32 бита, на
бар на рачунару као што је овај ЦС50

89
00:03:35,360 --> 00:03:37,980
Апарата, и тако су
извући једнако величине.

90
00:03:37,980 --> 00:03:42,260
>> Дакле, шта се користи показивач
мада за очигледно?

91
00:03:42,260 --> 00:03:47,690
Зашто додали ово стрелицу сада када су низови
тако лепо и чисто и једноставно?

92
00:03:47,690 --> 00:03:50,460
Шта се ради показивач за
нас у сваком од ових чворова?

93
00:03:50,460 --> 00:03:52,160
>> СТУДЕНТ: [ИНАУДИБЛЕ].

94
00:03:52,160 --> 00:03:52,465
>> СПИКЕР 1: Управо тако.

95
00:03:52,465 --> 00:03:54,120
То вам је рекао где
следећи је.

96
00:03:54,120 --> 00:03:57,350
Тако да сам на неки начин користи аналогију
користите конац да некако

97
00:03:57,350 --> 00:03:59,180
провуците заједно ових чворова.

98
00:03:59,180 --> 00:04:01,760
А то је управо оно што ми радимо са
показивачи јер сваки од њих

99
00:04:01,760 --> 00:04:06,360
комади меморије могу или не могу бити
заразне, бацк то бацк то бацк

100
00:04:06,360 --> 00:04:09,500
унутар РАМ, јер сваки пут када
позовите маллоц говорећи, дај ми довољно

101
00:04:09,500 --> 00:04:12,510
бајтова за нови чвор, да би могло
бити овде, или можда овде.

102
00:04:12,510 --> 00:04:13,120
Можда овде.

103
00:04:13,120 --> 00:04:13,730
Можда овде.

104
00:04:13,730 --> 00:04:14,640
Ви једноставно не знам.

105
00:04:14,640 --> 00:04:17,880
>> Али, користећи показиваче на адресама
ти чворови, можете их бодом

106
00:04:17,880 --> 00:04:22,370
заједно на начин који изгледа визуелно
као листа, чак и ако се ове ствари

107
00:04:22,370 --> 00:04:26,770
Све шири у целом једном или
Ваши два или четири своје гигабајта РАМ-а

108
00:04:26,770 --> 00:04:28,760
унутар свог рачунара.

109
00:04:28,760 --> 00:04:33,230
>> Дакле мана, онда,
повезана листа је шта?

110
00:04:33,230 --> 00:04:34,670
Која је цена коју смо
очигледно плаћају?

111
00:04:34,670 --> 00:04:36,010
>> СТУДЕНТ: [ИНАУДИБЛЕ].

112
00:04:36,010 --> 00:04:36,920
>> СПИКЕР 1: Више простора, зар не?

113
00:04:36,920 --> 00:04:39,340
Ми смо, у овом слуцају, удвостручио износ
простора, јер смо отишли

114
00:04:39,340 --> 00:04:43,500
од 32 бита за сваки чвор, за сваки
инт, тако да сада 64 бита, јер ми морамо да

115
00:04:43,500 --> 00:04:45,050
држати око показивача, као добро.

116
00:04:45,050 --> 00:04:48,860
Можете добити више ефикасности ако ваш Структ
је већи од ове једноставне ствари.

117
00:04:48,860 --> 00:04:52,020
Ако заиста имате ученика у
од којих је неколико жица за

118
00:04:52,020 --> 00:04:55,430
име и кућа, можда матични број,
можда неким другим пољима укупно.

119
00:04:55,430 --> 00:04:59,000
>> Дакле, ако имате довољно велики строги,
онда можда цена је показивач

120
00:04:59,000 --> 00:05:00,010
није тако велика ствар.

121
00:05:00,010 --> 00:05:03,570
Ово је мало корнер предмета у који
смо складиштење тако једноставна примитивни

122
00:05:03,570 --> 00:05:04,760
унутар повезане листе.

123
00:05:04,760 --> 00:05:05,790
Али поента је иста.

124
00:05:05,790 --> 00:05:08,230
Ти си дефинитивно троши више
меморије, али ви добијате

125
00:05:08,230 --> 00:05:08,990
флексибилност.

126
00:05:08,990 --> 00:05:12,280
Јер сад ако желим да додам елемент
на почетку ове листе,

127
00:05:12,280 --> 00:05:14,340
Морам да издвоји нови чвор.

128
00:05:14,340 --> 00:05:17,180
И ја морам да ажурирате само оне
Стрелице некако само од кретања

129
00:05:17,180 --> 00:05:17,980
неколико смерница око.

130
00:05:17,980 --> 00:05:20,580
>> Ако желим да убаците нешто у
половини листе, ја не морам да

131
00:05:20,580 --> 00:05:24,410
гурнути у страну све што смо радили у
Последњих недеља "са нашим волонтерима који су

132
00:05:24,410 --> 00:05:25,700
представља низ.

133
00:05:25,700 --> 00:05:29,470
Ја само могу да издвоје нови чвор и
онда само указују на стрелице у

134
00:05:29,470 --> 00:05:32,290
различита правца, јер не
морају да остану у стварни

135
00:05:32,290 --> 00:05:35,670
меморија прави ред као да сам нацртао
овде на екрану.

136
00:05:35,670 --> 00:05:38,400
>> И онда на крају, ако желите да убаците
нешто на крају листе, то је

137
00:05:38,400 --> 00:05:39,210
још лакше.

138
00:05:39,210 --> 00:05:43,320
То је врста произвољне нотацији,
али 34 је показивач, Погоди.

139
00:05:43,320 --> 00:05:46,710
Која је вредност њеног показивача већине
вероватно извући нешто као стари

140
00:05:46,710 --> 00:05:47,700
школа антена тамо?

141
00:05:47,700 --> 00:05:48,920
>> СТУДЕНТ: [ИНАУДИБЛЕ].

142
00:05:48,920 --> 00:05:49,900
>> СПИКЕР 1: То је вероватно нула.

143
00:05:49,900 --> 00:05:52,710
И заиста, то је за једног аутора
представљање нулл.

144
00:05:52,710 --> 00:05:56,310
А то је зато што апсолутно ништаван
Треба да се зна где је крај повезана

145
00:05:56,310 --> 00:06:00,050
Списак је, да не би и даље следе и
пратећи и након ових стрелица

146
00:06:00,050 --> 00:06:01,170
неком смеће вредности.

147
00:06:01,170 --> 00:06:06,230
Дакле, нула ће значити да нема
више чворова на десно од броја 34,

148
00:06:06,230 --> 00:06:07,200
у овом случају.

149
00:06:07,200 --> 00:06:10,270
>> Зато предлажемо да можемо имплементирати
Овај чвор у коду.

150
00:06:10,270 --> 00:06:12,130
А ми смо видели ову врсту
синтаксе пре.

151
00:06:12,130 --> 00:06:15,090
Типедеф само дефинише нови тип за
нама, нам даје као синоним

152
00:06:15,090 --> 00:06:17,100
ниска је за цхар *.

153
00:06:17,100 --> 00:06:21,030
У овом случају, то ће нам дати
стенографски запис тако да струцт чвор

154
00:06:21,030 --> 00:06:24,010
може уместо тога само да се напише као
чвор, што је много чистији.

155
00:06:24,010 --> 00:06:25,360
То је много мање опсирнији.

156
00:06:25,360 --> 00:06:30,080
>> Унутар чвор је очигледно инт
позвао н, а затим струцт чвор *

157
00:06:30,080 --> 00:06:34,670
што значи управо оно што смо желели
стрелице да значи, показивач на други

158
00:06:34,670 --> 00:06:36,940
чвор на потпуно исти тип података.

159
00:06:36,940 --> 00:06:40,300
И ја предлажем да се спроведе
функција претраге овако, што у

160
00:06:40,300 --> 00:06:41,890
први поглед може да изгледа
мало комплекс.

161
00:06:41,890 --> 00:06:43,330
Али, хајде да видимо то у контексту.

162
00:06:43,330 --> 00:06:45,480
>> Пусти ме да одем на уређај овде.

163
00:06:45,480 --> 00:06:48,460
Дозволите ми да отворим фајл који се зове
Листа нула тачка х.

164
00:06:48,460 --> 00:06:53,950
И то само садржи Дефиниција коју
Управо сам видео пре тренутак за овим подацима

165
00:06:53,950 --> 00:06:55,390
Тип се зове чвор.

166
00:06:55,390 --> 00:06:57,350
Дакле, ми смо ставили да у дот х датотеке.

167
00:06:57,350 --> 00:07:01,430
>> И као по страни, иако је ово
програм који сте видети је

168
00:07:01,430 --> 00:07:05,410
није све тако сложен, то је заиста
Конвенција приликом писања програма за

169
00:07:05,410 --> 00:07:10,270
стави ствари као типове података, да се повуче
константе понекад, унутар вашег

170
00:07:10,270 --> 00:07:13,210
заглавље датотеке, а не нужно у
Ваша датотека Ц, свакако када ваш

171
00:07:13,210 --> 00:07:17,370
програми добијају све већи и већи, тако да
знате где да погледате како за

172
00:07:17,370 --> 00:07:20,840
документација у неким случајевима, или
основе за овако,

173
00:07:20,840 --> 00:07:22,360
дефиниција неке врсте.

174
00:07:22,360 --> 00:07:25,680
>> Ако сад отворим листу нула тачка
Ц, приметићете неколико ствари.

175
00:07:25,680 --> 00:07:29,090
Садржи неколико заглавља датотеке, највише
од које смо већ видели.

176
00:07:29,090 --> 00:07:31,980
То укључује сопствени хеадер фајл.

177
00:07:31,980 --> 00:07:35,200
>> И успут, зашто то је двоструко
цитира овде, за разлику од угла

178
00:07:35,200 --> 00:07:38,340
конзоле на линију која
Сам тамо нагласио?

179
00:07:38,340 --> 00:07:39,180
>> СТУДЕНТ: [ИНАУДИБЛЕ].

180
00:07:39,180 --> 00:07:40,460
>> СПИКЕР 1: Да, па то је локални фајл.

181
00:07:40,460 --> 00:07:44,300
Дакле, ако је овде фајл са своје
на линији 15, на пример, користите

182
00:07:44,300 --> 00:07:46,570
знакова навода уместо
од Угаоне заграде.

183
00:07:46,570 --> 00:07:48,270
>> Сада ово је веома интересантно.

184
00:07:48,270 --> 00:07:51,830
Обратите пажњу да сам проглашена глобална
променљиве у овом програму на линији 18

185
00:07:51,830 --> 00:07:55,910
зове прво, идеја је ово
ће бити показивач на први

186
00:07:55,910 --> 00:07:59,190
чвор у мом повезаној листи, а ја сам
иницијализују се нулл, јер сам

187
00:07:59,190 --> 00:08:02,310
није додељена сваки стварни
чворови још увек.

188
00:08:02,310 --> 00:08:07,570
>> Дакле, ово представља, сликовито, шта смо
Видео сам малопре на слици као

189
00:08:07,570 --> 00:08:10,090
да показивач на далеко
левој страни.

190
00:08:10,090 --> 00:08:12,260
Управо сада, да показивач
нема стрелу.

191
00:08:12,260 --> 00:08:14,590
Уместо тога, она је само нулл.

192
00:08:14,590 --> 00:08:17,880
Али, он представља оно што ће бити
адреса први стварни

193
00:08:17,880 --> 00:08:19,480
чвор на овој листи.

194
00:08:19,480 --> 00:08:22,120
Тако сам спроведен је глобална
јер, као што ћете видети, све ово

195
00:08:22,120 --> 00:08:25,310
Програм се спроводи у животу је
повезана листа за мене.

196
00:08:25,310 --> 00:08:27,050
>> Сада имам неколико прототипова овде.

197
00:08:27,050 --> 00:08:31,190
Одлучио сам да спроведе карактеристике као
брисање, уметање, претраживање, и

198
00:08:31,190 --> 00:08:31,740
траверсал -

199
00:08:31,740 --> 00:08:35,210
последњи само што хода преко
листа, штампање његове елементе.

200
00:08:35,210 --> 00:08:36,750
А сада је моја главна рутина.

201
00:08:36,750 --> 00:08:39,890
А ми не проводе превише времена на
Ово јер је то врста, надам се

202
00:08:39,890 --> 00:08:41,780
стари шешир до сада.

203
00:08:41,780 --> 00:08:45,370
>> Ја ћу да урадите следеће,
док корисник сарађује.

204
00:08:45,370 --> 00:08:47,300
Зато је један, ја ћу да одштампате
из овог менија.

205
00:08:47,300 --> 00:08:49,420
И ја сам га форматиран као
чисто што сам могао.

206
00:08:49,420 --> 00:08:52,240
Ако корисник упише у једном, то значи
желе нешто да избришете.

207
00:08:52,240 --> 00:08:54,560
Ако корисник упише у два, то значи
они желе да убаците нешто.

208
00:08:54,560 --> 00:08:55,930
И тако даље.

209
00:08:55,930 --> 00:08:58,270
Ја ћу вас онда питати
затим на команду.

210
00:08:58,270 --> 00:08:59,300
И онда ћу користити Затамњена.

211
00:08:59,300 --> 00:09:02,790
>> Дакле, ово је веома једноставан менуинг
интерфејс где само треба да унесете

212
00:09:02,790 --> 00:09:05,270
мапирање број један
ове команде.

213
00:09:05,270 --> 00:09:08,730
И сада имам лепу чисту прекидач
изјаву да ће да укључите

214
00:09:08,730 --> 00:09:10,090
год корисник унесе

215
00:09:10,090 --> 00:09:12,180
И ако су уписали једну, ја ћу
позовите брисање и сломити.

216
00:09:12,180 --> 00:09:14,380
Ако се откуца два, ја ћу
позовите убаците и сломити.

217
00:09:14,380 --> 00:09:16,490
>> Запазите сада сам сваки пут
од њих на истој линији.

218
00:09:16,490 --> 00:09:18,360
Ово је само стилска одлука.

219
00:09:18,360 --> 00:09:20,210
Обично смо видели нешто
овако.

220
00:09:20,210 --> 00:09:23,260
Али сам одлучио, искрено, мој програм
Погледао више читљиви, јер

221
00:09:23,260 --> 00:09:25,980
било је само четири предмета у
само списак је овако.

222
00:09:25,980 --> 00:09:28,360
Потпуно легитимно коришћење стила.

223
00:09:28,360 --> 00:09:31,480
И ја ћу да урадим ово све док
члан није откуцао нулу, што сам

224
00:09:31,480 --> 00:09:33,910
одлучили ће значити да желе да престану.

225
00:09:33,910 --> 00:09:36,630
>> Сада обратите пажњу шта сам
да радимо овде.

226
00:09:36,630 --> 00:09:38,650
Идем да очигледно ослободи листу.

227
00:09:38,650 --> 00:09:40,230
Али, више о томе на тренутак.

228
00:09:40,230 --> 00:09:41,640
Хајде да прво покрене овај програм.

229
00:09:41,640 --> 00:09:45,250
Дакле, дозволите ми да већи терминал
прозор, тачка црта 0 листа.

230
00:09:45,250 --> 00:09:49,510
Ја ћу ићи напред и убаците стране
куцање два, број 50, и сада

231
00:09:49,510 --> 00:09:51,590
видећете списак је сада 50.

232
00:09:51,590 --> 00:09:53,380
И мој текст само помера се мало.

233
00:09:53,380 --> 00:09:55,940
Дакле, сада приметити листа садржи
број 50.

234
00:09:55,940 --> 00:09:58,220
>> Хајде да урадимо још један уметак узимањем два.

235
00:09:58,220 --> 00:10:01,630
Хајде да унети број као један.

236
00:10:01,630 --> 00:10:03,940
Листа је сада једна, затим 50.

237
00:10:03,940 --> 00:10:06,020
Дакле, ово је само текстуална репрезентација
листе.

238
00:10:06,020 --> 00:10:10,550
И да убаците још један број као
број 42, који се надамо

239
00:10:10,550 --> 00:10:14,620
ће се завршити у средини, јер
Овај програм посебно сортирању

240
00:10:14,620 --> 00:10:16,320
елементи јер их убацује.

241
00:10:16,320 --> 00:10:17,220
Тако да га имамо.

242
00:10:17,220 --> 00:10:20,730
Супер једноставан програм који би могао
апсолутно су користили низ, али ја

243
00:10:20,730 --> 00:10:23,280
буде користио повезану листу
Само тако могу да динамички

244
00:10:23,280 --> 00:10:24,610
расте и психијатар га.

245
00:10:24,610 --> 00:10:28,470
>> Дакле, хајде да погледамо за претрагу, ако
покрените команду три, желим да тражи

246
00:10:28,470 --> 00:10:31,040
за, рецимо, број 43.

247
00:10:31,040 --> 00:10:34,190
И ништа је очигледно пронашао,
зато што сам се вратио никакав одговор.

248
00:10:34,190 --> 00:10:35,010
Па хајде да поновимо ово.

249
00:10:35,010 --> 00:10:35,690
Тражи.

250
00:10:35,690 --> 00:10:39,520
Хајде да се потрага за 50, или пре претрагу
за 42, што је леп

251
00:10:39,520 --> 00:10:40,850
мало суптилније значење.

252
00:10:40,850 --> 00:10:42,610
И нашао је смисао живота тамо.

253
00:10:42,610 --> 00:10:44,990
Број 42, ако не знате
референца, на Гооглеу.

254
00:10:44,990 --> 00:10:45,350
У реду.

255
00:10:45,350 --> 00:10:47,130
Дакле, шта је овај програм урадио за мене?

256
00:10:47,130 --> 00:10:50,660
Је само дозвољено да на тај начин убаците
далеко и трагање за елементима.

257
00:10:50,660 --> 00:10:53,650
>> Хајде да брзо напред, онда, да
та функција ми је погледао

258
00:10:53,650 --> 00:10:55,360
у понедељак као тизер.

259
00:10:55,360 --> 00:10:59,620
Дакле ове функције, ја тврдим, претраге за
елемент у листи прво

260
00:10:59,620 --> 00:11:03,830
један, пита корисника, а затим позива
Затамњена да се стварни инт

261
00:11:03,830 --> 00:11:05,060
коју желите да потражите.

262
00:11:05,060 --> 00:11:06,460
>> Онда приметити.

263
00:11:06,460 --> 00:11:10,690
Ја ћу створити привремену променљиву
у складу назива показивач 188 -

264
00:11:10,690 --> 00:11:11,270
ПТР -

265
00:11:11,270 --> 00:11:12,440
Могао је то назвао ништа.

266
00:11:12,440 --> 00:11:16,140
И то је показивач на чвор
зато сам рекао чвор * тамо.

267
00:11:16,140 --> 00:11:19,900
А ја иницијализација да буде једнака
први, тако да ја имам своје ефективно

268
00:11:19,900 --> 00:11:22,860
прст, да тако кажем, на веома
први елемент листе.

269
00:11:22,860 --> 00:11:27,460
Дакле, ако је моја десна рука овде је ПТР сам
указујући на исту ствар да прво

270
00:11:27,460 --> 00:11:28,670
указује на.

271
00:11:28,670 --> 00:11:31,430
>> Дакле, сада је поново у коду,
шта се даље дешава -

272
00:11:31,430 --> 00:11:35,070
ово је заједничка парадигма када итератинг
преко структура као

273
00:11:35,070 --> 00:11:35,970
повезана листа.

274
00:11:35,970 --> 00:11:40,410
Ја ћу да урадим следеће док
показивач није једнако тако док нулл

275
00:11:40,410 --> 00:11:47,530
мој прст не указује на неке НУЛЛ
вредност, ако показивач стрелица Н једнака н.

276
00:11:47,530 --> 00:11:52,290
Прво ћемо приметити да је оно што је н
корисник откуцао на ГетИнтс зову овде.

277
00:11:52,290 --> 00:11:54,280
>> И показивач стрелица н значи шта?

278
00:11:54,280 --> 00:11:59,020
Па ако се вратимо на слици овде,
ако имам прст показујући на

279
00:11:59,020 --> 00:12:02,960
да први чвор који садржи девет, на
стрелица у суштини значи да иду у

280
00:12:02,960 --> 00:12:08,860
чвор и зграби вредност на локацију Н,
у овом случају, подаци поље зове н.

281
00:12:08,860 --> 00:12:14,120
>> Као страну - и ми смо видели тај пар
недеља пре када неко питао -

282
00:12:14,120 --> 00:12:18,840
Ова синтакса је нова, али то није то
да нам дају овлашћења да

283
00:12:18,840 --> 00:12:20,040
није већ имају.

284
00:12:20,040 --> 00:12:25,325
Шта је ово еквивалентно са коришћењем фраза
дот нотација и звезда пар

285
00:12:25,325 --> 00:12:29,490
недеља пре када смо скинуле
овај слој мало прерано?

286
00:12:29,490 --> 00:12:31,780
>> СТУДЕНТ: [ИНАУДИБЛЕ].

287
00:12:31,780 --> 00:12:38,880
>> СПИКЕР 1: Тачно, то је звезда, а
онда је звезда тачка Н, са

288
00:12:38,880 --> 00:12:41,930
заграде овде, што изгледа,
искрено, ја мислим да је много

289
00:12:41,930 --> 00:12:43,320
мање јасни за читање.

290
00:12:43,320 --> 00:12:46,270
Али показивач звезда, као и увек,
значи ићи тамо.

291
00:12:46,270 --> 00:12:49,090
И када си тамо, који подаци
поље желите да приступите?

292
00:12:49,090 --> 00:12:52,730
Па ви користите тачка нотацију за приступ
Структуре података поље, и ја

293
00:12:52,730 --> 00:12:54,140
Желим посебно н.

294
00:12:54,140 --> 00:12:56,240
>> Искрено, ја бих рекао ово
теже је само за читање.

295
00:12:56,240 --> 00:12:58,080
То је теже да се сетим где
не иду заграде,

296
00:12:58,080 --> 00:12:59,030
звезда и све то.

297
00:12:59,030 --> 00:13:02,150
Дакле, свет донела неке синтаксичке
шећер, да тако кажем.

298
00:13:02,150 --> 00:13:04,740
Само секси начин да се каже,
ово је еквивалент, и

299
00:13:04,740 --> 00:13:05,970
можда више интуитивно.

300
00:13:05,970 --> 00:13:09,600
Ако показивач заиста показивач,
арров нотације средства иду тамо и наћи

301
00:13:09,600 --> 00:13:11,890
поље у овом случају зове н.

302
00:13:11,890 --> 00:13:13,660
>> Дакле, ако га не нађем, приметити шта радим.

303
00:13:13,660 --> 00:13:17,430
Ја једноставно штампају, посто сам ја нашао,
укључивања у вредности за тај инт.

304
00:13:17,430 --> 00:13:20,730
Позивам спавам на тренутак само да натури
паузе ствари на екрану да бисте

305
00:13:20,730 --> 00:13:22,900
дају кориснику други да апсорбују
што се управо догодило.

306
00:13:22,900 --> 00:13:24,290
И онда сам сломити.

307
00:13:24,290 --> 00:13:26,330
Иначе, шта да радим?

308
00:13:26,330 --> 00:13:30,960
Ажурирам показивач на једнак
показивач стрелицу поред.

309
00:13:30,960 --> 00:13:35,840
>> Дакле, само да буде јасно, то значи да идемо
тамо, користећи своје старе школе нотацију.

310
00:13:35,840 --> 00:13:39,580
Дакле, то само значи да се на било
упериш у, који је у веома

311
00:13:39,580 --> 00:13:43,660
Први случај је да мислим на
струцт са девет у њему.

312
00:13:43,660 --> 00:13:44,510
Тако да сам тамо отишао.

313
00:13:44,510 --> 00:13:47,880
И онда тачка нотација значи,
се вредност на следећи.

314
00:13:47,880 --> 00:13:50,470
>> Али вредност, иако је то привукло
као уска, је само број.

315
00:13:50,470 --> 00:13:51,720
То је нумеричка адреса.

316
00:13:51,720 --> 00:13:55,670
Према томе, ова линија кода, да ли
написано овако, мање јасни

317
00:13:55,670 --> 00:14:00,190
начин, или овако, мало више
интуитиван начин, само значи да померим руку

318
00:14:00,190 --> 00:14:03,460
од првог чвора на следећи,
а онда следећи, а затим

319
00:14:03,460 --> 00:14:05,320
следећи, и тако даље.

320
00:14:05,320 --> 00:14:09,920
>> Тако се нећемо задржавати на друге
имплементације уметање и брисање

321
00:14:09,920 --> 00:14:14,030
и траверсал, прва два од
који су прилично укључени.

322
00:14:14,030 --> 00:14:17,010
И ја мислим да је прилично лако добити
изгубио када то раде вербално.

323
00:14:17,010 --> 00:14:19,890
Али, оно што можемо да урадимо јесте
покушати да утврди како

324
00:14:19,890 --> 00:14:21,640
најбоље да се то уради визуелно.

325
00:14:21,640 --> 00:14:24,800
Јер ја бих предложио да ако
желите да убаците елемената у ово

326
00:14:24,800 --> 00:14:26,680
постојећи списак, који
има пет елемената -

327
00:14:26,680 --> 00:14:29,530
9, 17, 22, 26, и 33 -

328
00:14:29,530 --> 00:14:33,300
ако је требало да спроведе ово у
код, треба да размотре како да се

329
00:14:33,300 --> 00:14:34,160
да ће то урадити.

330
00:14:34,160 --> 00:14:37,720
>> И ја бих предложио пужевим корацима
при чему, у овом случају мислим, шта су

331
00:14:37,720 --> 00:14:41,090
могуће сценарије које смо
наићи уопште?

332
00:14:41,090 --> 00:14:44,120
Приликом спровођења уметак за повезана
листа, то се дешава само да буде

333
00:14:44,120 --> 00:14:46,090
Конкретан пример за величине пет.

334
00:14:46,090 --> 00:14:50,420
Па ако желите да унесете број,
свиђа кажем број један, и

335
00:14:50,420 --> 00:14:53,380
одржавање реда поређане, где
очигледно не број један треба да

336
00:14:53,380 --> 00:14:55,686
иди у овом конкретном примеру?

337
00:14:55,686 --> 00:14:56,840
Као и на почетку.

338
00:14:56,840 --> 00:15:00,030
>> Али, оно што је занимљиво је да
Ако желите да убаците једну у ово

339
00:15:00,030 --> 00:15:04,100
листа, шта треба посебан показивач
очигледно да се ажурира?

340
00:15:04,100 --> 00:15:04,610
Прва.

341
00:15:04,610 --> 00:15:07,830
Дакле, рекао бих да је ово први случај
да ћемо желети да размотрите,

342
00:15:07,830 --> 00:15:11,140
Сценарио укључује убацивање у
почетак листе.

343
00:15:11,140 --> 00:15:15,400
>> Хајде да уберу искључен можда тако лако или чак
лакше случају, релативно говорећи.

344
00:15:15,400 --> 00:15:18,110
Рецимо да желите да убаците
број 35 у сортираном редоследу.

345
00:15:18,110 --> 00:15:20,600
Очигледно припада тамо.

346
00:15:20,600 --> 00:15:25,320
Дакле, шта показивач очигледно ће
морају да се ажурирају у том сценарију?

347
00:15:25,320 --> 00:15:30,060
34 је показивач не постане нула
али адреса струцт

348
00:15:30,060 --> 00:15:31,800
садржи број 35.

349
00:15:31,800 --> 00:15:32,750
Дакле, то је случај два.

350
00:15:32,750 --> 00:15:36,190
Тако је већ, ја сам некако квантизирање
колико посла морам да урадим овде.

351
00:15:36,190 --> 00:15:39,880
>> И на крају, очигледно средњи случај
заиста, у средини, ако желим да

352
00:15:39,880 --> 00:15:45,870
убаците нешто као рецимо 23, који иде
између 23 и 26, али

353
00:15:45,870 --> 00:15:48,680
Сада се ствари мало више
укључени зато што

354
00:15:48,680 --> 00:15:52,800
показивачи треба да се промени?

355
00:15:52,800 --> 00:15:56,680
Дакле, 22 очигледно треба да се промени
јер он не може да укаже на 26. више.

356
00:15:56,680 --> 00:16:00,320
Он треба да укаже на нови чвор који
Ја ћу морати да издвоји позивом

357
00:16:00,320 --> 00:16:01,770
маллоц или неки еквивалент.

358
00:16:01,770 --> 00:16:05,990
>> Али, онда сам и треба ми тај нови чвор, 23
у овом случају, да има свој показивач

359
00:16:05,990 --> 00:16:07,870
показујући на кога?

360
00:16:07,870 --> 00:16:08,560
26.

361
00:16:08,560 --> 00:16:10,380
И тамо ће бити
редослед операција овде.

362
00:16:10,380 --> 00:16:13,410
Јер ако урадим ово глупо, и ја
на пример старт на почетку

363
00:16:13,410 --> 00:16:16,040
листа, а мој циљ је да убаците 23.

364
00:16:16,040 --> 00:16:18,610
И провери, да ли то припада
Овде, близу девет?

365
00:16:18,610 --> 00:16:18,950
Не.

366
00:16:18,950 --> 00:16:20,670
Да ли овде припада, поред 17?

367
00:16:20,670 --> 00:16:20,940
Не.

368
00:16:20,940 --> 00:16:22,530
Да ли овде припада поред 22?

369
00:16:22,530 --> 00:16:23,300
Да.

370
00:16:23,300 --> 00:16:26,400
>> Сада, ако сам ја луд овде, а не
размишљам о овоме, могао бих

371
00:16:26,400 --> 00:16:28,320
издвојити мој нови чвор за 23..

372
00:16:28,320 --> 00:16:32,080
Можда ажурирање показивача из
чвор се зове 22, указујући

373
00:16:32,080 --> 00:16:33,080
је у новом чвору.

374
00:16:33,080 --> 00:16:36,140
И онда ста треба да ажурирате
новог чвора показивач да буде?

375
00:16:36,140 --> 00:16:38,120
>> СТУДЕНТ: [ИНАУДИБЛЕ].

376
00:16:38,120 --> 00:16:38,385
>> СПИКЕР 1: Управо тако.

377
00:16:38,385 --> 00:16:39,710
Указујући на 26.

378
00:16:39,710 --> 00:16:45,590
Али даммит ако нисам већ ажурирали
22 је показивач да се укаже на овог момка, а

379
00:16:45,590 --> 00:16:48,260
сада имам сирочади, остатак
списка, да се тако изразим.

380
00:16:48,260 --> 00:16:52,140
Дакле, редослед операција овде
ће бити важна.

381
00:16:52,140 --> 00:16:55,100
>> Да бисте то урадили могу да краду,
кажу, шест добровољаца.

382
00:16:55,100 --> 00:16:57,650
И хајде да видимо да ли можемо урадити
визуелно уместо кода питању.

383
00:16:57,650 --> 00:16:59,330
И ми имамо неке дивне стреса
лопте за вас данас.

384
00:16:59,330 --> 00:17:02,510
У реду, шта је са један, два, у
назад - на крају тамо.

385
00:17:02,510 --> 00:17:04,530
три, четири, обојица
момци на крају.

386
00:17:04,530 --> 00:17:05,579
И пет, шест.

387
00:17:05,579 --> 00:17:05,839
Наравно.

388
00:17:05,839 --> 00:17:06,450
Пет и шест.

389
00:17:06,450 --> 00:17:08,390
Добро, и ми ћемо доћи
да вас следећи пут.

390
00:17:08,390 --> 00:17:09,640
У реду, идемо горе.

391
00:17:09,640 --> 00:17:12,010

392
00:17:12,010 --> 00:17:14,819
>> Добро, пошто си овде прво,
желите да буде један незгодно

393
00:17:14,819 --> 00:17:16,119
овде Гоогле стакла?

394
00:17:16,119 --> 00:17:19,075
У реду, па, у реду, стакло,
видео записа.

395
00:17:19,075 --> 00:17:22,720

396
00:17:22,720 --> 00:17:24,589
У реду, ви сте на добром путу.

397
00:17:24,589 --> 00:17:27,950
>> У реду, тако да ако ви можете доћи
овде, ја сам припремио унапред

398
00:17:27,950 --> 00:17:30,110
неки бројеви.

399
00:17:30,110 --> 00:17:31,240
У реду, хајде овамо.

400
00:17:31,240 --> 00:17:33,440
А зашто не одеш мало
даље тако.

401
00:17:33,440 --> 00:17:35,520
И да видимо, како се зовеш,
са Гоогле стакла?

402
00:17:35,520 --> 00:17:35,910
>> СТУДЕНТ: Бен.

403
00:17:35,910 --> 00:17:36,230
>> СПИКЕР 1: Бен?

404
00:17:36,230 --> 00:17:38,380
У реду, Бен, ви ћете бити први, буквално.

405
00:17:38,380 --> 00:17:40,580
Дакле, ми ћемо вам послати
до краја фазе.

406
00:17:40,580 --> 00:17:41,670
У реду, и ваше име?

407
00:17:41,670 --> 00:17:41,990
>> СТУДЕНТ: Јасон.

408
00:17:41,990 --> 00:17:44,530
>> СПИКЕР 1: Џејсон, ОК ти ћеш
бити број девет.

409
00:17:44,530 --> 00:17:46,700
Дакле, ако желите да пратите Бен тај начин.

410
00:17:46,700 --> 00:17:47,010
>> СТУДЕНТ: Џил.

411
00:17:47,010 --> 00:17:49,630
>> СПИКЕР 1: Џил, ти ћеш бити
17, који ако бих учинио више

412
00:17:49,630 --> 00:17:51,260
интелигентно, ја бих
почео на другом крају.

413
00:17:51,260 --> 00:17:52,370
Ти иди тамо.

414
00:17:52,370 --> 00:17:53,030
22.

415
00:17:53,030 --> 00:17:53,670
А ти си?

416
00:17:53,670 --> 00:17:53,980
>> СТУДЕНТ: Мери.

417
00:17:53,980 --> 00:17:56,130
>> СПИКЕР 1: Мери, бићете 22.

418
00:17:56,130 --> 00:17:58,420
А твоје име?

419
00:17:58,420 --> 00:17:58,810
>> СТУДЕНТ: Крис.

420
00:17:58,810 --> 00:18:00,100
>> СПИКЕР 1: Крис, бићеш 26.

421
00:18:00,100 --> 00:18:00,740
И онда на крају.

422
00:18:00,740 --> 00:18:01,400
>> СТУДЕНТ: Диана.

423
00:18:01,400 --> 00:18:02,670
>> СПИКЕР 1: Диана, бићете 34.

424
00:18:02,670 --> 00:18:03,920
Тако сте дошли овамо.

425
00:18:03,920 --> 00:18:06,360
>> У реду, тако савршен сортиране
нареди већ.

426
00:18:06,360 --> 00:18:09,600
И идемо напред и урадите
тако да заиста можемо -

427
00:18:09,600 --> 00:18:11,720
Бен си само мало потрази
Повратак у нигде.

428
00:18:11,720 --> 00:18:15,670
У реду, тако да идемо напред и то описују
употребе оружја, баш као да сам, тачно,

429
00:18:15,670 --> 00:18:16,250
шта се дешава.

430
00:18:16,250 --> 00:18:19,540
Дакле, само напред и да сам себи
стопала или два између себе.

431
00:18:19,540 --> 00:18:22,900
И само напред и укаже са једне стране,
Ко год да треба бити усмерена на

432
00:18:22,900 --> 00:18:23,470
на основу тога.

433
00:18:23,470 --> 00:18:25,890
А ако си нула само упутити
равно на под.

434
00:18:25,890 --> 00:18:27,690
У реду, добро.

435
00:18:27,690 --> 00:18:32,290
>> Дакле, сада имамо повезану листу, и пусти ме
предлаже да ћу играти улогу

436
00:18:32,290 --> 00:18:35,110
ПТР, па нећу гњавити
ношење око овог.

437
00:18:35,110 --> 00:18:37,830
А онда - неко глуп конвенција -
можете назвати ово све што желите -

438
00:18:37,830 --> 00:18:39,800
претходник показивач, пред показивач -

439
00:18:39,800 --> 00:18:43,930
то је само надимак ми дали у
наш узорак код за леву руку.

440
00:18:43,930 --> 00:18:47,240
С друге стране да ће се чување
евиденцију о томе ко је ко у

441
00:18:47,240 --> 00:18:48,400
Следећи сценарији.

442
00:18:48,400 --> 00:18:52,390
>> Претпостављам, прво, желим да се уберу искључен
да је први пример убацивања, каже

443
00:18:52,390 --> 00:18:54,330
20, у листу.

444
00:18:54,330 --> 00:18:57,160
Зато ћу да треба неко да
отелотворују број 20 за нас.

445
00:18:57,160 --> 00:18:58,950
Зато морам да маллоц некоме
из публике.

446
00:18:58,950 --> 00:18:59,380
Хајде горе.

447
00:18:59,380 --> 00:19:00,340
Како се зовеш?

448
00:19:00,340 --> 00:19:01,300
>> СТУДЕНТ: Брајан.

449
00:19:01,300 --> 00:19:05,270
>> СПИКЕР 1: Брајан, у реду, тако да
ће бити чвор који садржи 20.

450
00:19:05,270 --> 00:19:06,810
У реду, хајде овамо.

451
00:19:06,810 --> 00:19:10,025
И очигледно, где
Брајан се припада?

452
00:19:10,025 --> 00:19:12,190
Дакле, у средини - у ствари,
чекај мало.

453
00:19:12,190 --> 00:19:13,420
Ми ово радимо из реда.

454
00:19:13,420 --> 00:19:17,170
Радимо ово много теже
него то треба да буде на првом месту.

455
00:19:17,170 --> 00:19:21,210
У реду, идемо на слободан Бриан
Брајан као и реаллоц пет.

456
00:19:21,210 --> 00:19:23,680
>> У реду, тако да сада желимо да убаците
Брајан и пет.

457
00:19:23,680 --> 00:19:25,960
Па хајде овамо поред
Бен за тренутак.

458
00:19:25,960 --> 00:19:28,250
И ви сте, претпостављам да кажете
где ова прича иде.

459
00:19:28,250 --> 00:19:30,500
Али, хајде да добро размислите о
редослед операција.

460
00:19:30,500 --> 00:19:32,880
И управо је ово визуелно
који ће се построје

461
00:19:32,880 --> 00:19:34,080
са том примеру кода.

462
00:19:34,080 --> 00:19:40,120
Дакле, овде сам ПТР указују на почетку
не на Бена, пер се, него на било

463
00:19:40,120 --> 00:19:43,245
вреднују он садржи, што у овом случају
је - оно зовеш?

464
00:19:43,245 --> 00:19:43,670
>> СТУДЕНТ: Јасон.

465
00:19:43,670 --> 00:19:47,350
>> СПИКЕР 1: Џејсон, тако и Бен и ја смо
показујући на Јасона у овом тренутку.

466
00:19:47,350 --> 00:19:49,700
Тако да сада морам да се утврди,
где се Брајан припада?

467
00:19:49,700 --> 00:19:53,500
Дакле, једино што имам приступ
сада је његов н податак.

468
00:19:53,500 --> 00:19:58,280
Зато ћу да проверим, је
Брајан мање него Јасон?

469
00:19:58,280 --> 00:19:59,770
Одговор је истина.

470
00:19:59,770 --> 00:20:03,680
>> Па шта сад треба да се догоди,
у исправном стању?

471
00:20:03,680 --> 00:20:07,120
Морам да ажурирате колико показиваче
је укупно у овој причи?

472
00:20:07,120 --> 00:20:10,720
Где ми је рука и даље показује на
Џејсон, и руку - ако желите да

473
00:20:10,720 --> 00:20:12,930
стави руку као, на неки начин, ја
Не знам, знак питања.

474
00:20:12,930 --> 00:20:14,070
У реду, добро.

475
00:20:14,070 --> 00:20:15,670
>> У реду, тако да имате
неколико кандидата.

476
00:20:15,670 --> 00:20:20,500
Или Бен и ја и Брајан или Џејсон
и сви остали, који

477
00:20:20,500 --> 00:20:21,370
показивачи треба да се промени?

478
00:20:21,370 --> 00:20:23,260
Колико укупно?

479
00:20:23,260 --> 00:20:24,080
>> У реду, тако два.

480
00:20:24,080 --> 00:20:27,090
Мој показивач није битно више
јер ја сам само привремено.

481
00:20:27,090 --> 00:20:31,370
Тако да је ова двојица, по свој прилици,
и Бен и Брајан.

482
00:20:31,370 --> 00:20:34,410
Тако да ме предлажем да ажурирате
Бен, пошто је он први.

483
00:20:34,410 --> 00:20:36,350
Први елемент ове листе
сада ће бити Брајан.

484
00:20:36,350 --> 00:20:38,070
Дакле, Бен тачка на Брајана.

485
00:20:38,070 --> 00:20:39,320
Ок, шта сада?

486
00:20:39,320 --> 00:20:41,950

487
00:20:41,950 --> 00:20:43,460
>> Ко добија указао на кога?

488
00:20:43,460 --> 00:20:44,710
>> СТУДЕНТ: [ИНАУДИБЛЕ].

489
00:20:44,710 --> 00:20:46,180
>> СПИКЕР 1: У реду, тако је Брајан
да укаже на Јасона.

490
00:20:46,180 --> 00:20:48,360
Али, да сам изгубила појам тог показивача?

491
00:20:48,360 --> 00:20:49,980
Да ли знам где је Јасон?

492
00:20:49,980 --> 00:20:50,790
>> СТУДЕНТ: [ИНАУДИБЛЕ].

493
00:20:50,790 --> 00:20:52,620
>> СПИКЕР 1: радим, јер сам
привремено показивач.

494
00:20:52,620 --> 00:20:55,110
И вероватно, нисам се променила
да укаже на нови чвор.

495
00:20:55,110 --> 00:20:58,300
Тако да једноставно имамо Бриан тачку
на кога ја мислим на.

496
00:20:58,300 --> 00:20:59,000
И ми смо готови.

497
00:20:59,000 --> 00:21:01,890
Дакле један случај, убацивање у
почетак листе.

498
00:21:01,890 --> 00:21:02,950
Била су два кључна корака.

499
00:21:02,950 --> 00:21:06,750
Један, морамо да ажурирате Бена, а затим
морамо да ажурирате Брајана.

500
00:21:06,750 --> 00:21:09,230
И онда ја не морам да се трудите
траипсинг кроз остатак

501
00:21:09,230 --> 00:21:12,680
списак, јер смо већ нашао
локација, јер је припадао

502
00:21:12,680 --> 00:21:14,080
лево од првог елемента.

503
00:21:14,080 --> 00:21:15,400
>> У реду, тако да прилично јасно.

504
00:21:15,400 --> 00:21:18,110
У ствари, изгледа као да смо скоро
тако да је ово превише компликовано.

505
00:21:18,110 --> 00:21:20,240
Па хајде да сада чупају искључен крај
листе, а видите где

506
00:21:20,240 --> 00:21:21,380
сложеност почиње.

507
00:21:21,380 --> 00:21:24,560
Дакле, ако сада, ја Аллоц из публике.

508
00:21:24,560 --> 00:21:25,540
Свако ко жели да игра 55?

509
00:21:25,540 --> 00:21:26,700
У реду, видео сам прво руку.

510
00:21:26,700 --> 00:21:29,620
Хајде горе.

511
00:21:29,620 --> 00:21:30,030
Да.

512
00:21:30,030 --> 00:21:31,177
Како се зовеш?

513
00:21:31,177 --> 00:21:32,310
>> СТУДЕНТ: [ИНАУДИБЛЕ].

514
00:21:32,310 --> 00:21:33,240
>> СПИКЕР 1: Хабата.

515
00:21:33,240 --> 00:21:33,890
ОК, идемо горе.

516
00:21:33,890 --> 00:21:35,730
Ти ћеш бити број 55.

517
00:21:35,730 --> 00:21:37,820
Тако да, наравно, припада
на крају листе.

518
00:21:37,820 --> 00:21:41,850
Па хајде да играте симулације са мном
као ПТР за тренутак.

519
00:21:41,850 --> 00:21:44,050
Дакле, прво ћу да укаже на
год Бенова показујући на.

520
00:21:44,050 --> 00:21:45,900
Ми смо обоје указујући сада на Брајана.

521
00:21:45,900 --> 00:21:48,420
Дакле, 55 је не мање од пет.

522
00:21:48,420 --> 00:21:52,510
Дакле, ја ћу да се ажурира по
указујући на следећи поинтер Брианову, који

523
00:21:52,510 --> 00:21:54,450
Сада је, наравно, Јасон.

524
00:21:54,450 --> 00:21:57,310
55 није мањи од девет, тако
Идем да ажурирате ПТР.

525
00:21:57,310 --> 00:21:58,890
Идем да ажурирате ПТР.

526
00:21:58,890 --> 00:22:02,290
Идем да ажурирате ПТР
Ја ћу да ажурирате ПТР.

527
00:22:02,290 --> 00:22:05,060
И ја ћу - хм, шта је
зовеш?

528
00:22:05,060 --> 00:22:05,560
>> СТУДЕНТ: Диана.

529
00:22:05,560 --> 00:22:09,190
>> СПИКЕР 1: Диана показује, наравно,
на нула са својом левом руком.

530
00:22:09,190 --> 00:22:13,030
Дакле, где се заправо Хабата
припадају јасно?

531
00:22:13,030 --> 00:22:15,050
Лево, овде.

532
00:22:15,050 --> 00:22:19,460
Па како да знам да је ту доспела
Мислим да сам зезнуо.

533
00:22:19,460 --> 00:22:22,420
Јер шта је уметност ПТР
овај тренутак у времену?

534
00:22:22,420 --> 00:22:23,240
Нулл.

535
00:22:23,240 --> 00:22:25,580
Дакле, иако је, визуелно, можемо
очигледно види све ово

536
00:22:25,580 --> 00:22:26,610
момци овде на сцени.

537
00:22:26,610 --> 00:22:29,680
Не сам пратила претходну
особа на листи.

538
00:22:29,680 --> 00:22:33,210
Немам прст који указује,
у овом случају, број 34 чвора.

539
00:22:33,210 --> 00:22:34,760
>> Па хајде да заиста почну овоме.

540
00:22:34,760 --> 00:22:37,560
Дакле, сада сам стварно треба
Друга локална променљива.

541
00:22:37,560 --> 00:22:40,980
И то је оно што ћете видети у
Стварни број узорак Ц, где је као ја идем,

542
00:22:40,980 --> 00:22:45,860
када сам упдате моју десну руку до тачке
Џејсон, остављајући за собом Брајане, ја

543
00:22:45,860 --> 00:22:51,440
Боље почните да користите леву руку да
ажурирање где сам био, тако да као да идем

544
00:22:51,440 --> 00:22:52,700
кроз ове листе -

545
00:22:52,700 --> 00:22:55,040
више него што сам намеравао неспретно
сада овде визуелно -

546
00:22:55,040 --> 00:22:56,740
Ја ћу доћи до
крај листе.

547
00:22:56,740 --> 00:23:00,020
>> Ова рука је и даље нула, што је прилично
бескорисно, осим да укаже

548
00:23:00,020 --> 00:23:02,980
Ја сам јасно на крају листе,
али сада барем имам ово

549
00:23:02,980 --> 00:23:08,270
претходник показивач показивање овде, па
шта сада предаје и шта треба показивачи

550
00:23:08,270 --> 00:23:10,150
да буде ажуриран?

551
00:23:10,150 --> 00:23:13,214
Чија рука хоћеш
за реконфигурацију први?

552
00:23:13,214 --> 00:23:15,190
>> СТУДЕНТ: [ИНАУДИБЛЕ].

553
00:23:15,190 --> 00:23:16,220
>> СПИКЕР 1: У реду, тако Диана.

554
00:23:16,220 --> 00:23:21,110
Где желите да покажете
Диана показивач на лево?

555
00:23:21,110 --> 00:23:23,620
На 55, по свој прилици, тако да
сам тамо убацили смо.

556
00:23:23,620 --> 00:23:25,560
А где би требало да показивач иде 55?

557
00:23:25,560 --> 00:23:27,000
Доле, представља нулл.

558
00:23:27,000 --> 00:23:28,890
И моје руке, у овом тренутку, не
само због тога што су управо

559
00:23:28,890 --> 00:23:30,070
привремене променљиве.

560
00:23:30,070 --> 00:23:31,030
Дакле, сада смо урадили.

561
00:23:31,030 --> 00:23:34,650
>> Дакле, додатна сложеност тамо - и
није тако тешко спровести,

562
00:23:34,650 --> 00:23:38,660
али ми треба секундарни променљиву да би
да ли пре него што кренем своје право

563
00:23:38,660 --> 00:23:42,140
рука, ја ажурирати вредност моје лево
рука, пред показивач у овом случају, тако да

564
00:23:42,140 --> 00:23:45,860
да имам пратећи показивач
да пратите где сам био.

565
00:23:45,860 --> 00:23:49,360
Сада као страну, ако мислиш ово
путем, ово изгледа као да је

566
00:23:49,360 --> 00:23:51,490
мало непријатно да треба да задржи
пратите ове леве руке.

567
00:23:51,490 --> 00:23:54,015
>> Шта би друго решење
на овај проблем био?

568
00:23:54,015 --> 00:23:56,500
Ако имаш да редизајнира податке
Структура говоримо

569
00:23:56,500 --> 00:23:59,630
до сада?

570
00:23:59,630 --> 00:24:02,690
Ако је то само врста осећа мало
непријатно да су, као, два показивача

571
00:24:02,690 --> 00:24:08,430
пролази кроз листу, ко би други могао
су, у идеалном свету, одржава

572
00:24:08,430 --> 00:24:10,160
информације које нам је потребно?

573
00:24:10,160 --> 00:24:11,360
Да?

574
00:24:11,360 --> 00:24:12,610
>> СТУДЕНТ: [ИНАУДИБЛЕ].

575
00:24:12,610 --> 00:24:15,160

576
00:24:15,160 --> 00:24:16,150
>> СПИКЕР 1: Управо тако.

577
00:24:16,150 --> 00:24:19,130
Право да заправо има занимљиво
Клица идеје.

578
00:24:19,130 --> 00:24:22,470
И ова идеја претходне показивача,
показујући на претходни елемент.

579
00:24:22,470 --> 00:24:25,580
Шта ако сам управо оличена да
унутар саме листе?

580
00:24:25,580 --> 00:24:27,810
И то ће бити тешко замислити
то без свих папира

581
00:24:27,810 --> 00:24:28,830
пада на под.

582
00:24:28,830 --> 00:24:31,860
Али, претпоставимо да су ови момци и
из њихових руку да претходни

583
00:24:31,860 --> 00:24:35,950
показивач, и следећи показивач, тиме
спровођење шта ћемо назвати двоструко

584
00:24:35,950 --> 00:24:36,830
повезана листа.

585
00:24:36,830 --> 00:24:41,090
То би омогућило да некако уназад,
много лакше без мене,

586
00:24:41,090 --> 00:24:43,800
програмер, морате да задржите
трацк ручно -

587
00:24:43,800 --> 00:24:44,980
заиста ручно -

588
00:24:44,980 --> 00:24:47,280
где сам раније био
на листи.

589
00:24:47,280 --> 00:24:48,110
Тако да то неће урадити.

590
00:24:48,110 --> 00:24:50,950
Ми ћемо наставити да то једноставно зато што је то
ће доћи у цени, дупло

591
00:24:50,950 --> 00:24:53,450
много простора за показивачи,
ако желите једно друго.

592
00:24:53,450 --> 00:24:55,760
Али то је заиста заједничка
структура података позната као

593
00:24:55,760 --> 00:24:57,410
двоструко повезане листе.

594
00:24:57,410 --> 00:25:01,310
>> Хајде да урадимо последњи пример овде и ставио
ови момци ван њихове беде.

595
00:25:01,310 --> 00:25:03,270
Тако маллоц 20.

596
00:25:03,270 --> 00:25:05,320
Хајде се из пролаза тамо.

597
00:25:05,320 --> 00:25:06,280
У реду, како ти је име?

598
00:25:06,280 --> 00:25:07,440
>> СТУДЕНТ: [ИНАУДИБЛЕ].

599
00:25:07,440 --> 00:25:07,855
>> СПИКЕР 1: Молим?

600
00:25:07,855 --> 00:25:08,480
>> СТУДЕНТ: [ИНАУДИБЛЕ].

601
00:25:08,480 --> 00:25:09,410
>> СПИКЕР 1: Демерон?

602
00:25:09,410 --> 00:25:10,230
Добро дошли на горе.

603
00:25:10,230 --> 00:25:11,910
Ви треба да буде 20.

604
00:25:11,910 --> 00:25:14,720
Ви очигледно ће
припадају између 17 и 22.

605
00:25:14,720 --> 00:25:16,150
Тако да ме науче своју лекцију.

606
00:25:16,150 --> 00:25:18,150
Ја ћу почети показивач
показујући на Брајана.

607
00:25:18,150 --> 00:25:21,190
И ја ћу имати своју леву руку
само упдате Бриану као што сам се пресели у

608
00:25:21,190 --> 00:25:23,600
Џејсон, провера да ли 20 мање од девет?

609
00:25:23,600 --> 00:25:24,060
Не.

610
00:25:24,060 --> 00:25:25,430
Да ли је 20 мање од 17?

611
00:25:25,430 --> 00:25:25,880
Не.

612
00:25:25,880 --> 00:25:27,450
Да ли је 20 мање од 22?

613
00:25:27,450 --> 00:25:28,440
Да.

614
00:25:28,440 --> 00:25:34,070
Па шта показивачи или руке треба да промените
где су они сада показује?

615
00:25:34,070 --> 00:25:37,070
>> Тако да можемо да урадимо 17 указујући на 20.

616
00:25:37,070 --> 00:25:37,860
Дакле, то је у реду.

617
00:25:37,860 --> 00:25:40,080
Где желимо да истакнемо
показивач сада?

618
00:25:40,080 --> 00:25:41,330
На 22.

619
00:25:41,330 --> 00:25:45,410
А знамо где је 22, опет хвала
до мог привременог показивачу.

620
00:25:45,410 --> 00:25:46,760
Дакле, ми смо у реду тамо.

621
00:25:46,760 --> 00:25:49,440
Дакле, због овог привременог складиштења
Ја сам стално пратите где су сви.

622
00:25:49,440 --> 00:25:55,055
А сада можете визуелно да иде у којој
ви припадате, а сада нам треба 1, 2, 3,

623
00:25:55,055 --> 00:25:58,410
4, 5, 6, 7, 8, 9 стрес лоптице,
и аплауз за

624
00:25:58,410 --> 00:25:59,770
ови момци, ако можемо.

625
00:25:59,770 --> 00:26:00,410
Лепо урађено.

626
00:26:00,410 --> 00:26:05,320
>> [Апплаусе]

627
00:26:05,320 --> 00:26:06,330
>> СПИКЕР 1: У реду.

628
00:26:06,330 --> 00:26:09,860
И можете да задржите делове
папира као успомена.

629
00:26:09,860 --> 00:26:15,930
>> У реду, тако да, верујте ми то је много
лакше да хода кроз то са

630
00:26:15,930 --> 00:26:17,680
људи него што је то са стварним кодом.

631
00:26:17,680 --> 00:26:22,690
Али, оно што ћете наћи у само једном тренутку
Сада, то је иста - Ох, хвала.

632
00:26:22,690 --> 00:26:23,630
Хвала -

633
00:26:23,630 --> 00:26:29,360
је да ћете наћи да је исте податке
структура, повезана листа, заправо могу

634
00:26:29,360 --> 00:26:33,200
да се користи као грађевински блок за још
софистициране структуре података.

635
00:26:33,200 --> 00:26:37,620
>> А схватити и овде је тема која
апсолутно ми смо увели више

636
00:26:37,620 --> 00:26:40,060
комплексност у примени
овог алгоритма.

637
00:26:40,060 --> 00:26:43,940
Убацивања, па ако смо ишли кроз њега,
брисање и претраживање, је мало

638
00:26:43,940 --> 00:26:46,660
компликованије од тога
је са низом.

639
00:26:46,660 --> 00:26:48,040
Али, ми смо добили неку динамику.

640
00:26:48,040 --> 00:26:50,180
Добијамо адаптивног структуру података.

641
00:26:50,180 --> 00:26:54,010
>> Али опет, ми плаћамо цену да се одређени
додатне сложености, како у

642
00:26:54,010 --> 00:26:54,910
имплементација.

643
00:26:54,910 --> 00:26:56,750
И ми смо одустали случајан приступ.

644
00:26:56,750 --> 00:27:00,450
И да будем искрен, не постоји неки леп
очистите слајд ја да ти дам

645
00:27:00,450 --> 00:27:03,120
каже ево зашто повезана листа
је бољи од низа.

646
00:27:03,120 --> 00:27:04,100
И нека остане на томе.

647
00:27:04,100 --> 00:27:07,520
Јер тема понавља сада, чак и
више у наредних неколико недеља, је

648
00:27:07,520 --> 00:27:10,200
да не постоји нужно
тачан одговор.

649
00:27:10,200 --> 00:27:13,830
>> То је разлог зашто имамо посебан осу
решења за проблем поставе.

650
00:27:13,830 --> 00:27:17,700
То ће бити веома контекст осетљиви
да ли желите да користите ове податке

651
00:27:17,700 --> 00:27:21,750
структуру или да је један, и то ће
зависити од онога што је вама важно у смислу

652
00:27:21,750 --> 00:27:24,620
ресурса и сложености.

653
00:27:24,620 --> 00:27:28,830
>> Али, дозволите ми да предложи идеални подаци
структура, свети грал, био би

654
00:27:28,830 --> 00:27:32,200
нешто што је константа време,
без обзира на то колико је ствари

655
00:27:32,200 --> 00:27:36,940
унутар њега, не би било невероватно ако
структура података вратио одговоре

656
00:27:36,940 --> 00:27:37,920
константа време.

657
00:27:37,920 --> 00:27:38,330
Да.

658
00:27:38,330 --> 00:27:40,110
Ова реч је у великом речнику.

659
00:27:40,110 --> 00:27:41,550
Или не, ова реч није.

660
00:27:41,550 --> 00:27:43,270
Или било таквих проблема тамо.

661
00:27:43,270 --> 00:27:46,360
Па да видимо, ако не можемо макар
предузети корак ка томе.

662
00:27:46,360 --> 00:27:50,190
>> Дозволите ми да предложи нову структуру података која
се може користити за различите ствари,

663
00:27:50,190 --> 00:27:52,260
у овом случају зове хеш табела.

664
00:27:52,260 --> 00:27:55,590
И тако смо се вратили у ствари поглед
у низу, у овом случају, и

665
00:27:55,590 --> 00:28:00,550
нешто произвољно, ја сам нацртао ово
хасх табела као низ са врстом

666
00:28:00,550 --> 00:28:02,810
дводимензионални низ -

667
00:28:02,810 --> 00:28:05,410
односно то је овде приказана као два
димензионални низ - али то је само

668
00:28:05,410 --> 00:28:10,770
низ величине 26, тако да ако се
позовите сто низа, стони држач

669
00:28:10,770 --> 00:28:12,440
нула је правоугаоник на врху.

670
00:28:12,440 --> 00:28:15,090
Табела 25 носач је правоугаоник
на дну.

671
00:28:15,090 --> 00:28:18,620
А ово је како ја могу нацртати података
Структура у којој желим да сачувате

672
00:28:18,620 --> 00:28:19,790
Имена људи.

673
00:28:19,790 --> 00:28:24,370
>> Тако на пример, а ја нећу извући
Цела ствар овде на графоскоп, ако

674
00:28:24,370 --> 00:28:29,160
имао овај низ, који сада ћу да
позовите хеш табели, а то је опет

675
00:28:29,160 --> 00:28:31,360
локација нула.

676
00:28:31,360 --> 00:28:34,840
Ово овде је локација
један, и тако даље.

677
00:28:34,840 --> 00:28:37,880
Ја тврдим да ја желим да користите ове податке
структура, ради расправе,

678
00:28:37,880 --> 00:28:42,600
да меморишете имена људи, Алиса и Боб
и Чарли и других таквих имена.

679
00:28:42,600 --> 00:28:46,110
Дакле, мислим да је ово сада као почетке
од, рецимо, речник

680
00:28:46,110 --> 00:28:47,520
са много речи.

681
00:28:47,520 --> 00:28:49,435
Они се деси да се називи
у нашем примеру овде.

682
00:28:49,435 --> 00:28:52,560
А ово је све сувише Германе, можда, да се
спроводи контролу правописа, као што смо

683
00:28:52,560 --> 00:28:54,400
Можда проблем за шест сет.

684
00:28:54,400 --> 00:28:59,300
>> Дакле, ако имамо низ укупне величине 26
тако да је ово 25. место

685
00:28:59,300 --> 00:29:03,390
на дну, а ја тврдим да је Алице
прва реч у речнику

686
00:29:03,390 --> 00:29:07,260
имена које желим да убаците у РАМ,
у ову структуру података, где су

687
00:29:07,260 --> 00:29:12,480
инстинкти који вам каже да је Алиса
Име би требало да иде у том низу?

688
00:29:12,480 --> 00:29:13,510
>> Имамо 26 опције.

689
00:29:13,510 --> 00:29:14,990
Где желимо да је ставим?

690
00:29:14,990 --> 00:29:16,200
Ми јој желимо у конзолу нула, зар не?

691
00:29:16,200 --> 00:29:18,280
За Алице, назовимо да нулу.

692
00:29:18,280 --> 00:29:20,110
И Б ће бити један, и Ц ће бити два.

693
00:29:20,110 --> 00:29:22,600
Дакле, ми ћемо писати
Алисин име овде.

694
00:29:22,600 --> 00:29:24,890
Ако убаците Боба, његов
име ће отићи овде.

695
00:29:24,890 --> 00:29:27,280
Чарли ће отићи овде.

696
00:29:27,280 --> 00:29:30,500
И тако даље доле кроз
Ова структура података.

697
00:29:30,500 --> 00:29:32,090
>> Ово је диван структура података.

698
00:29:32,090 --> 00:29:32,730
Зашто?

699
00:29:32,730 --> 00:29:37,460
Па шта је покренут време
убацивање име људског на оваквом

700
00:29:37,460 --> 00:29:39,850
структура података сада?

701
00:29:39,850 --> 00:29:43,702
С обзиром да је ово сто се спроводи,
заиста, као низ.

702
00:29:43,702 --> 00:29:44,940
Па то је константа време.

703
00:29:44,940 --> 00:29:45,800
То је поредак једне.

704
00:29:45,800 --> 00:29:46,360
Зашто?

705
00:29:46,360 --> 00:29:48,630
>> Па како да утврдите
где је Алице припада?

706
00:29:48,630 --> 00:29:51,000
Можете погледати на којој слово њеног имена?

707
00:29:51,000 --> 00:29:51,490
Прва.

708
00:29:51,490 --> 00:29:54,350
И можете да добијете, ако је ниска,
само гледајући низ

709
00:29:54,350 --> 00:29:55,200
носач нула.

710
00:29:55,200 --> 00:29:57,110
Дакле нулте карактера ниске.

711
00:29:57,110 --> 00:29:57,610
То је лако.

712
00:29:57,610 --> 00:30:00,350
То смо урадили у крипто
Пре додељивања недеља.

713
00:30:00,350 --> 00:30:05,310
И онда када знате да Алисин
Писмо је капитал, може се одузети

714
00:30:05,310 --> 00:30:08,160
искључивање 65 или капитала сама по себи,
То нам даје нулу.

715
00:30:08,160 --> 00:30:10,940
Дакле, ми сада знамо да Алиса припада
на локацији нула.

716
00:30:10,940 --> 00:30:14,240
>> А с обзиром показивач на овим подацима
структуре, неке врсте, колико дуго траје

717
00:30:14,240 --> 00:30:18,840
је потребно да ме пронађе локацију
нулу, у низу?

718
00:30:18,840 --> 00:30:22,080
Само један корак, право је време константно
због случајног приступа се

719
00:30:22,080 --> 00:30:23,780
Предложена је карактеристика низа.

720
00:30:23,780 --> 00:30:28,570
Дакле укратко, откријем шта индекс
Алице се зове, која је, у

721
00:30:28,570 --> 00:30:32,610
овом случају је, или хајде да реши
да на нулу, где је Б и Ц је један

722
00:30:32,610 --> 00:30:34,900
два, решио да се
Време је константа.

723
00:30:34,900 --> 00:30:38,510
Само треба да погледамо своје прво писмо,
схватите где је нула

724
00:30:38,510 --> 00:30:40,460
низ је такође константно време.

725
00:30:40,460 --> 00:30:42,140
Дакле, то је технички
као два корака уназад.

726
00:30:42,140 --> 00:30:43,330
Али то је и даље константна.

727
00:30:43,330 --> 00:30:46,880
Дакле, ми то зовемо Биг О једне, па смо
убаци Алиса у овој табели у

728
00:30:46,880 --> 00:30:48,440
константа време.

729
00:30:48,440 --> 00:30:50,960
>> Али, наравно, ја сам био
наиван овде, зар не?

730
00:30:50,960 --> 00:30:53,240
Шта ако је Арон у класи?

731
00:30:53,240 --> 00:30:53,990
Или Алициа?

732
00:30:53,990 --> 00:30:57,230
Или било ког другог имена почињу са
О: Где ћемо ставити

733
00:30:57,230 --> 00:31:00,800
та особа, зар не?

734
00:31:00,800 --> 00:31:03,420
Мислим, сада има само три
људи на столу, тако да можда можемо

735
00:31:03,420 --> 00:31:07,490
треба ставити на локацији Арона
нула један два три.

736
00:31:07,490 --> 00:31:09,480
>> Добро, ја могу ставити овде.

737
00:31:09,480 --> 00:31:13,350
Али онда, ако покушамо да убаците у Давида
ова листа, где се Дејвид иде?

738
00:31:13,350 --> 00:31:15,170
Сада наш систем почиње разбијање
доле, зар не?

739
00:31:15,170 --> 00:31:19,210
Јер сада Дејвид завршава овде
ако Арон је заправо овде.

740
00:31:19,210 --> 00:31:23,060
И сада цела ова идеја има
чиста структура података која нам даје

741
00:31:23,060 --> 00:31:28,010
константно време уметања није више
константа време, јер морам да

742
00:31:28,010 --> 00:31:31,240
провери, ох, јебо те, неко је већ
у Алисине локацији.

743
00:31:31,240 --> 00:31:35,320
>> Дозволите ми да испитују остатак ових података
структура, у потрази за место да стави

744
00:31:35,320 --> 00:31:37,130
неко као име Арону.

745
00:31:37,130 --> 00:31:39,390
И тако и то је полазна
да линеарно време.

746
00:31:39,390 --> 00:31:42,710
Осим тога, ако сада желите да пронађете
Арон у ову структуру података, и ви

747
00:31:42,710 --> 00:31:45,430
провери, и Аронов име није овде.

748
00:31:45,430 --> 00:31:47,960
У идеалном случају, само би рекао Арону
не у структури података.

749
00:31:47,960 --> 00:31:51,530
Али ако почнете да зарађујете простора за
Арон где би било Д

750
00:31:51,530 --> 00:31:55,600
или Е, да, у најгорем случају, морам да проверим
Цела структура података, у

751
00:31:55,600 --> 00:31:59,480
ком случају се преноси у нешто
линеарно од величине табеле.

752
00:31:59,480 --> 00:32:00,920
>> Па добро, ја ћу то поправити.

753
00:32:00,920 --> 00:32:04,200
Проблем је у томе што сам имао
26 елемената у овом низу.

754
00:32:04,200 --> 00:32:05,000
Пусти ме да га промените.

755
00:32:05,000 --> 00:32:06,010
Упс.

756
00:32:06,010 --> 00:32:10,600
Дозволите ми да промени, тако да радије буду од
Величина 26 укупно, приметио дно

757
00:32:10,600 --> 00:32:12,720
Индекс ће се променити на минус 1 н.

758
00:32:12,720 --> 00:32:16,610
26. Ако је очигледно сувише мали за људе "
имена, јер има хиљаде

759
00:32:16,610 --> 00:32:20,830
имена у свету, хајде да направи
на 100, 1.000 или 10.000.

760
00:32:20,830 --> 00:32:22,960
Хајде да издвоји много више простора.

761
00:32:22,960 --> 00:32:27,230
>> Па то не мора да смањи
вероватноћа да нећемо имати два

762
00:32:27,230 --> 00:32:31,510
људи са именима почиње са, и
тако, да ћеш покушати да стави

763
00:32:31,510 --> 00:32:33,120
имена на локацију нули даље.

764
00:32:33,120 --> 00:32:36,850
Још увек су на сударе, која
значи да и даље треба да се стави решење

765
00:32:36,850 --> 00:32:41,020
Алиса и Арон и Алиша и других
имена почињу са А на другом месту.

766
00:32:41,020 --> 00:32:43,460
Али колико је то проблем?

767
00:32:43,460 --> 00:32:46,870
Која је вероватноћа да сте
има сударе у дата

768
00:32:46,870 --> 00:32:48,240
Структура овако?

769
00:32:48,240 --> 00:32:52,570
>> Па, пусти ме - Вратићемо
на то питање овде.

770
00:32:52,570 --> 00:32:55,530
А погледајте како бисмо могли
прво решити га.

771
00:32:55,530 --> 00:32:58,480
Дозволите ми станите овде овај предлог.

772
00:32:58,480 --> 00:33:02,020
Оно што смо управо описали је алгоритам,
хеуристички зове линеарна

773
00:33:02,020 --> 00:33:05,030
прескок где, ако сте покушали да убаците
нешто овде у овим подацима

774
00:33:05,030 --> 00:33:08,920
структуру, која се зове хеш табела,
и нема места тамо, ви

775
00:33:08,920 --> 00:33:12,000
заиста испитују структуру података
провере, ово је на располагању?

776
00:33:12,000 --> 00:33:13,430
Да ли је ово Доступно је то доступно?

777
00:33:13,430 --> 00:33:13,980
Да ли је то доступно?

778
00:33:13,980 --> 00:33:17,550
И када је коначно, убаците
Име које сте првобитно намењен

779
00:33:17,550 --> 00:33:19,370
на другом месту на тој локацији.

780
00:33:19,370 --> 00:33:23,360
Али, у најгорем случају, једино место
може да буде на самом дну података

781
00:33:23,360 --> 00:33:25,090
структура, на самом крају низа.

782
00:33:25,090 --> 00:33:30,130
>> Дакле линеарни прескок, у најгорем случају,
прелази у линеарном алгоритма где

783
00:33:30,130 --> 00:33:34,500
Арон, ако се деси да се убаци последњи
у овој структури података, могао би

784
00:33:34,500 --> 00:33:39,540
сударају са овом првом месту, али
онда завршим пех на самом крају.

785
00:33:39,540 --> 00:33:43,940
Дакле, ово није константа
време свети грал за нас.

786
00:33:43,940 --> 00:33:47,650
Овај приступ уметање елемената у
Структура података који се зове хеш

787
00:33:47,650 --> 00:33:52,050
сто не изгледа да буде константна време
бар не у општем случају.

788
00:33:52,050 --> 00:33:54,000
То може да пренесе у нешто линеарно.

789
00:33:54,000 --> 00:33:56,970
>> Па шта ако смо решили судара
нешто другачије?

790
00:33:56,970 --> 00:34:00,740
Дакле, овде је софистициранији
приступ томе шта је још

791
00:34:00,740 --> 00:34:02,800
зове хеш табела.

792
00:34:02,800 --> 00:34:05,890
И по хашиш, као на страну, шта
Мислим да је индекс

793
00:34:05,890 --> 00:34:07,070
Сам раније поменуо.

794
00:34:07,070 --> 00:34:09,810
Да размотре нешто може бити
мисли као глагол.

795
00:34:09,810 --> 00:34:13,690
>> Дакле, ако сте хасх Алиса је име,
хасх функција, да тако кажем,

796
00:34:13,690 --> 00:34:14,710
треба да врати број.

797
00:34:14,710 --> 00:34:18,199
У овом случају је нула, ако је она спада у
Локација нула, један, ако она припада у

798
00:34:18,199 --> 00:34:20,000
локација један, и тако даље.

799
00:34:20,000 --> 00:34:24,360
Дакле, мој хасх функција до сада је
супер једноставно, само гледајући

800
00:34:24,360 --> 00:34:26,159
Прво слово нечијег имена.

801
00:34:26,159 --> 00:34:29,090
Али хасх функција узима као
улаз неки податак,

802
00:34:29,090 --> 00:34:30,210
стринг, инт, шта год.

803
00:34:30,210 --> 00:34:32,239
И избацује најчешће без броја.

804
00:34:32,239 --> 00:34:35,739
И тај број је где да се подаци
елеменат спада у структури података

805
00:34:35,739 --> 00:34:37,800
познат овде као хеш табели.

806
00:34:37,800 --> 00:34:41,400
>> Дакле, само интуитивно, ово је
мало другачији контекст.

807
00:34:41,400 --> 00:34:44,170
Ово је у ствари односи на пример
укључују рођендани, где

808
00:34:44,170 --> 00:34:46,850
можда постоји чак
31 дана у месецу.

809
00:34:46,850 --> 00:34:52,239
Али шта је та особа одлучи да
уради у случају судара?

810
00:34:52,239 --> 00:34:55,304
Контекст сада бити, не судара
имена, али је судар на рођендане,

811
00:34:55,304 --> 00:35:00,760
ако двоје људи имају исти рођендан
2. октобра, на пример.

812
00:35:00,760 --> 00:35:02,120
>> СТУДЕНТ: [ИНАУДИБЛЕ].

813
00:35:02,120 --> 00:35:05,010
>> СПИКЕР 1: Да, тако да овде имамо
усклађивање повезаних листа.

814
00:35:05,010 --> 00:35:07,830
Па изгледа мало другачије
него што је нацртао раније.

815
00:35:07,830 --> 00:35:10,790
Али изгледа да смо на низ
на левој страни.

816
00:35:10,790 --> 00:35:13,230
То је један показатељ, јер не
посебног разлога.

817
00:35:13,230 --> 00:35:14,630
Али, то је још увек низ.

818
00:35:14,630 --> 00:35:16,160
То је низ показивача.

819
00:35:16,160 --> 00:35:20,670
И сваки од тих елемената, сваки од
ови кругови или косе црте - сласх

820
00:35:20,670 --> 00:35:23,970
представља нулл - сваки од ових
показивачи се очигледно указује на

821
00:35:23,970 --> 00:35:25,730
шта структура података?

822
00:35:25,730 --> 00:35:26,890
Повезана листа.

823
00:35:26,890 --> 00:35:30,530
>> Дакле, сада имамо могућност да
Тешко код у наш програм

824
00:35:30,530 --> 00:35:32,010
величина табеле.

825
00:35:32,010 --> 00:35:35,360
У овом случају, знамо да никада нема
више од 31 дана у месецу.

826
00:35:35,360 --> 00:35:38,480
Тако тешко кодирање вредности као што је 31.
разумне у том контексту.

827
00:35:38,480 --> 00:35:42,700
У контексту имена, тешко кодирање
26 није неразумно то народном

828
00:35:42,700 --> 00:35:46,340
имена само почетак, на пример,
писмо укључује преко З.

829
00:35:46,340 --> 00:35:50,180
>> Можемо да их све стрпати у тим подацима
структуре све док, када се

830
00:35:50,180 --> 00:35:55,330
судара, овде не стави имена,
ми уместо да мисле од ових ћелија

831
00:35:55,330 --> 00:36:00,270
не као жице сами, већ као
показивачи на, на пример, Алице.

832
00:36:00,270 --> 00:36:03,660
А онда Алиса може имати још један показивач
на друго име почиње са

833
00:36:03,660 --> 00:36:06,150
О: И Боб заправо иде овамо.

834
00:36:06,150 --> 00:36:10,850
>> И ако постоји други који почиње име
са Б, он завршава овде.

835
00:36:10,850 --> 00:36:15,070
И тако сваки од елемената ове
Табела два, ако смо дизајнирали ово

836
00:36:15,070 --> 00:36:17,350
мало паметно -

837
00:36:17,350 --> 00:36:18,125
хајде -

838
00:36:18,125 --> 00:36:22,950
ако смо дизајнирали ово мало
паметно, сада постаје адаптивног податке

839
00:36:22,950 --> 00:36:27,720
структура, где нема чврсто ограничење
о томе колико елемената можете да уметнете

840
00:36:27,720 --> 00:36:30,700
у њега, јер ако имате
судара, то је у реду.

841
00:36:30,700 --> 00:36:34,690
Само напред и додајте га у
оно шта је било мало

842
00:36:34,690 --> 00:36:38,290
познат као повезане листе.

843
00:36:38,290 --> 00:36:39,690
>> Па хајде да застанемо на тренутак.

844
00:36:39,690 --> 00:36:42,570
Која је вероватноћа судара
на првом месту?

845
00:36:42,570 --> 00:36:45,480
Добро, можда сам више размишљам, можда
Ја сам преко инжењеринг овај проблем,

846
00:36:45,480 --> 00:36:46,370
јер знате шта?

847
00:36:46,370 --> 00:36:49,070
Да, ја могу доћи до произвољно
Примери са врха моје главе као

848
00:36:49,070 --> 00:36:52,870
Алисон и Арон, али у стварности,
дао униформу дистрибуција

849
00:36:52,870 --> 00:36:56,990
улаза, односно неки случајни уметања
у структури података, оно што је стварно

850
00:36:56,990 --> 00:36:58,580
вероватноћа судара?

851
00:36:58,580 --> 00:37:01,670
Па испада, то је заправо
Супер Хигх.

852
00:37:01,670 --> 00:37:03,850
Дозволите ми да генерализујемо ово
Проблем је што ово.

853
00:37:03,850 --> 00:37:08,890
>> Дакле, у соби од н ЦС50 студената, што је
вероватноћа да је најмање

854
00:37:08,890 --> 00:37:11,010
два студента у соби
имају исти рођендан?

855
00:37:11,010 --> 00:37:13,346
Тако да је оно. неколико Хунд -

856
00:37:13,346 --> 00:37:16,790
200, 300 и неколико људи овде
стотина људи код куће данас.

857
00:37:16,790 --> 00:37:20,670
Дакле, ако сте желели да се запитамо шта је
вероватноћа двоје људи

858
00:37:20,670 --> 00:37:23,930
у овој соби има исти рођендан,
можемо да решимо ово.

859
00:37:23,930 --> 00:37:26,250
А ја у ствари тврдим постоје два
људи са истим рођендан.

860
00:37:26,250 --> 00:37:29,560
>> На пример, да ли ико
имају рођендан данас?

861
00:37:29,560 --> 00:37:31,340
Јуче?

862
00:37:31,340 --> 00:37:32,590
Сутра?

863
00:37:32,590 --> 00:37:35,980
У реду, тако да изгледа као да идем
морати да уради 363 или тако више

864
00:37:35,980 --> 00:37:39,500
времена да се заиста схвати
Ако имамо судар.

865
00:37:39,500 --> 00:37:42,350
Или бисмо могли урадити математички
него мукотрпно

866
00:37:42,350 --> 00:37:43,200
радим ово.

867
00:37:43,200 --> 00:37:44,500
И предлажу следеће.

868
00:37:44,500 --> 00:37:48,740
>> Зато предлажем да се моделира
вероватноћа двоје људи који имају

869
00:37:48,740 --> 00:37:55,320
Исто рођендан као могућност 1
минус вероватноћа не има један

870
00:37:55,320 --> 00:37:56,290
исти рођендан.

871
00:37:56,290 --> 00:37:59,960
Тако да се ово, а то је само
фенси начин писања овог, за

872
00:37:59,960 --> 00:38:03,090
Прва особа у соби, он или она
могу имати један од могућих

873
00:38:03,090 --> 00:38:07,370
рођендани под претпоставком 365 дана у години,
уз извињење особама са

874
00:38:07,370 --> 00:38:08,760
фебруар 29. рођендан.

875
00:38:08,760 --> 00:38:13,470
>> Дакле, прва особа у овој просторији је бесплатна
да има било који број рођендана

876
00:38:13,470 --> 00:38:18,280
од укупно 365 могућности, тако да
ми ћемо то урадити 365 подељено са 365,

877
00:38:18,280 --> 00:38:18,990
што је један.

878
00:38:18,990 --> 00:38:22,700
Следећа особа у просторији, ако је циљ
је да избегне судар, може само

879
00:38:22,700 --> 00:38:26,460
имати свој рођендан на начин
много различитих могућих дана?

880
00:38:26,460 --> 00:38:27,610
364.

881
00:38:27,610 --> 00:38:31,430
Дакле, други термин у овом изразу је
у суштини раде да математика за нас

882
00:38:31,430 --> 00:38:33,460
одузимањем искључен један могући дан.

883
00:38:33,460 --> 00:38:36,390
А онда следећег дана, следећег дана,
Сутрадан доле на укупан број

884
00:38:36,390 --> 00:38:38,100
људи у просторији.

885
00:38:38,100 --> 00:38:41,290
>> И ако онда размислите, шта је онда
вероватноћа не поседовања свакога

886
00:38:41,290 --> 00:38:45,265
јединствене рођендане, али опет минус 1
да, ми добијамо израз

887
00:38:45,265 --> 00:38:47,810
да могу веома изванредном споју
изгледа овако.

888
00:38:47,810 --> 00:38:50,330
Међутим, веома је занимљиво
да погледа визуелно.

889
00:38:50,330 --> 00:38:55,120
Ово је табела у којој на к-оси је
број људи у просторији,

890
00:38:55,120 --> 00:38:56,180
Број на рођендане.

891
00:38:56,180 --> 00:38:59,840
На и-оси је вероватноћа
у судару, двоје људи

892
00:38:59,840 --> 00:39:01,230
имају исти рођендан.

893
00:39:01,230 --> 00:39:05,020
>> И понети из ове криве
да чим ти се свиђа 40

894
00:39:05,020 --> 00:39:11,110
студенти, ви сте се на 90% вероватноће
цомбинаторицалли два

895
00:39:11,110 --> 00:39:13,550
или више људи који имају
исти рођендан.

896
00:39:13,550 --> 00:39:18,600
А када дођете до 58 људи воле да је
скоро 100% шансе два

897
00:39:18,600 --> 00:39:21,310
људи у соби ће имати
исти рођендан, иако постоји

898
00:39:21,310 --> 00:39:26,650
365 или 366 могућих кашике, и
Само 58 људи у соби.

899
00:39:26,650 --> 00:39:29,900
Само статистички вероватно ћете
се сударе, која укратко

900
00:39:29,900 --> 00:39:31,810
мотивише ову дискусију.

901
00:39:31,810 --> 00:39:35,890
То чак и ако добијемо фенси овде, и
почети да се те ланце, још увек смо

902
00:39:35,890 --> 00:39:36,950
ће имати судара.

903
00:39:36,950 --> 00:39:42,710
>> Тако да отвара питање, шта је
Трошкови ради уметања и брисања

904
00:39:42,710 --> 00:39:44,850
у структури података као што је овај?

905
00:39:44,850 --> 00:39:46,630
Па да предложи -

906
00:39:46,630 --> 00:39:51,570
и да се вратимо на екран преко
овде - ако имамо н елемената у

907
00:39:51,570 --> 00:39:56,330
листа, па ако покушавамо да убаците
н елемената, а ми имамо

908
00:39:56,330 --> 00:39:58,050
Колико укупно кашике?

909
00:39:58,050 --> 00:40:03,450
Рецимо 31 Укупно кашике
у случају рођендана.

910
00:40:03,450 --> 00:40:09,240
Која је максимална дужина једног
од ових ланаца потенцијално?

911
00:40:09,240 --> 00:40:12,670
>> Ако опет има 31 могуће
рођендани у датом месецу.

912
00:40:12,670 --> 00:40:14,580
И управо смо циркулише свима -

913
00:40:14,580 --> 00:40:15,580
заправо то је глупа пример.

914
00:40:15,580 --> 00:40:16,960
Хајде да уместо 26.

915
00:40:16,960 --> 00:40:20,890
Дакле, ако заиста има људи чија имена
почети до З, дајући на тај начин

916
00:40:20,890 --> 00:40:22,780
нас 26 могућности.

917
00:40:22,780 --> 00:40:25,920
И ми користимо структуру података као што
коју смо управо видели, чиме смо

918
00:40:25,920 --> 00:40:30,210
низ показивача, од којих сваки
указује на повезаној листи, где је

919
00:40:30,210 --> 00:40:32,360
Први списак је свако
по имену Алиса.

920
00:40:32,360 --> 00:40:35,770
Друга листа је сваки са
име почиње са, почевши

921
00:40:35,770 --> 00:40:36,980
са Б, и тако даље.

922
00:40:36,980 --> 00:40:41,020
>> Шта ће дужина сваке од
те листе ако претпоставимо леп чист

923
00:40:41,020 --> 00:40:45,410
дистрибуција имена до З
преко целе структуре података?

924
00:40:45,410 --> 00:40:50,210
Има н људи у структури података
подељено са 26, ако су лепо су

925
00:40:50,210 --> 00:40:52,110
распоређено у току целе
структура података.

926
00:40:52,110 --> 00:40:54,970
Дакле, дужина сваког од њих
ланци је н подељено са 26..

927
00:40:54,970 --> 00:40:57,380
Али у великом О нотацији, шта је то?

928
00:40:57,380 --> 00:41:00,100

929
00:41:00,100 --> 00:41:02,440
Шта је то заправо?

930
00:41:02,440 --> 00:41:04,150
Дакле, то је заиста само н, зар не?

931
00:41:04,150 --> 00:41:06,620
Зато што смо рекли у прошлости,
ух да ћете поделити по 26 година.

932
00:41:06,620 --> 00:41:08,710
Да, у стварности то је брже.

933
00:41:08,710 --> 00:41:12,720
Али у теорији, то није суштински
све то брже.

934
00:41:12,720 --> 00:41:16,040
>> Дакле, ми се не чини да је све то много
ближи овом светим гралом.

935
00:41:16,040 --> 00:41:17,750
У ствари, ово је само линеарно време.

936
00:41:17,750 --> 00:41:20,790
Пакао, у овом тренутку, зашто не бисмо
само користите једну велику повезану листу?

937
00:41:20,790 --> 00:41:23,510
Зашто не бисмо користили један велики
низ за смештање имена

938
00:41:23,510 --> 00:41:25,010
сви у просторији?

939
00:41:25,010 --> 00:41:28,280
Па, има ли још нешто
убедљив о хеш табели?

940
00:41:28,280 --> 00:41:30,810
Да ли постоји још нешто убедљив
података о структури

941
00:41:30,810 --> 00:41:33,940
да изгледа овако?

942
00:41:33,940 --> 00:41:35,182
Ово.

943
00:41:35,182 --> 00:41:37,050
>> СТУДЕНТ: [ИНАУДИБЛЕ].

944
00:41:37,050 --> 00:41:39,840
>> СПИКЕР 1: Добро, а опет ако је то само
линеарно време алгоритам, а

945
00:41:39,840 --> 00:41:42,780
линеарна структура података пут, зашто не бих
Само име продавнице свима у велики

946
00:41:42,780 --> 00:41:44,210
низ, или у великом повезане листе?

947
00:41:44,210 --> 00:41:47,010
И престани да правиш ЦС толико много теже
него то треба да буде?

948
00:41:47,010 --> 00:41:49,600

949
00:41:49,600 --> 00:41:53,190
Шта је убедљив о томе, чак и
иако сам га огребе напоље?

950
00:41:53,190 --> 00:41:54,930
>> СТУДЕНТ: [ИНАУДИБЛЕ].

951
00:41:54,930 --> 00:41:57,040
>> СПИКЕР 1: Уметања не?

952
00:41:57,040 --> 00:41:58,140
Скупо више.

953
00:41:58,140 --> 00:42:03,390
Дакле уметци потенцијално могао даље
бити константна време, чак и ако ваши подаци

954
00:42:03,390 --> 00:42:07,910
структура изгледа овако, низ
показивачи, од којих се указује на

955
00:42:07,910 --> 00:42:09,550
потенцијално повезане листе.

956
00:42:09,550 --> 00:42:15,220
Како си могао да постигне константна
Време убацивање имена?

957
00:42:15,220 --> 00:42:16,280
Стави га у напред, зар не?

958
00:42:16,280 --> 00:42:19,290
>> Ако се жртвујемо гол дизајн из
раније, где смо желели да

959
00:42:19,290 --> 00:42:22,650
свачије име, на пример, сортирају,
или свих бројева на сцени поредани,

960
00:42:22,650 --> 00:42:25,020
претпоставимо да имамо
некласификовани повезана листа.

961
00:42:25,020 --> 00:42:29,960
То нас кошта само један или два корака,
као у случају Бен и Брајан

962
00:42:29,960 --> 00:42:32,750
раније, да убаците елемент у
почетак листе.

963
00:42:32,750 --> 00:42:36,090
Дакле, ако ми није стало сортирање свих
од имена почињу или све

964
00:42:36,090 --> 00:42:39,660
имена почињу са Б, још можемо
оствари сталан Време убацивања.

965
00:42:39,660 --> 00:42:43,900
Сада гледајући Алиса или Боб, или било које име
уопште још шта?

966
00:42:43,900 --> 00:42:48,100
То је велика О од н подељено са 26, у
идеалан случај када су сви равномерно

967
00:42:48,100 --> 00:42:51,190
дистрибуира, где има колико је
као што постоје З, који је вероватно

968
00:42:51,190 --> 00:42:52,220
нереално.

969
00:42:52,220 --> 00:42:53,880
Али, то је још увек линеарно.

970
00:42:53,880 --> 00:42:57,120
>> Али, овде морамо вратити до тачке
од сада асимптотическој нотацији

971
00:42:57,120 --> 00:42:58,600
теоретски тачно.

972
00:42:58,600 --> 00:43:02,960
Али, у стварном свету, ако ја тврдим да
мој програм може да уради нешто 26 пута

973
00:43:02,960 --> 00:43:06,210
бржи од твог, чији програм
ћеш радије користе?

974
00:43:06,210 --> 00:43:09,660
Ваш или мој, који
је 26 пута брже?

975
00:43:09,660 --> 00:43:14,320
Реално, човек чија је 26
пута брже, чак и ако теоретски

976
00:43:14,320 --> 00:43:18,790
наши алгоритми раде у истом
асимптотско време извршавања.

977
00:43:18,790 --> 00:43:20,940
>> Дозволите ми да предложи другачији
решење заједно.

978
00:43:20,940 --> 00:43:24,380
А ако то не одушевити,
ми смо из структура података.

979
00:43:24,380 --> 00:43:27,420
Дакле, ово је Трие -

980
00:43:27,420 --> 00:43:28,520
некако глупо име.

981
00:43:28,520 --> 00:43:32,880
Она долази из претраживања база података, а реч
је написано Трие, Т-Р-и-е, због

982
00:43:32,880 --> 00:43:34,450
Курс преузимање звучи као Трие.

983
00:43:34,450 --> 00:43:36,580
Али то је историја
речи Трие.

984
00:43:36,580 --> 00:43:40,980
>> Дакле Трие је заиста нека врста дрвета,
и то је такође игра на ту реч.

985
00:43:40,980 --> 00:43:46,330
А чак и ако не могу да га виде
са овим визуелизације, Трие је

986
00:43:46,330 --> 00:43:50,790
дрво структуиран, попут породичног стабла са
један предак на врху и још много

987
00:43:50,790 --> 00:43:54,530
за унуке и праунуке
као оставља на дну.

988
00:43:54,530 --> 00:43:58,100
Али сваки чвор у Трие је низ.

989
00:43:58,100 --> 00:44:00,680
И то је у низу - и хајде да
поједностављују за тренутак - то је

990
00:44:00,680 --> 00:44:04,600
низ, у овом случају, од величине 26, где
сваки чвор поново је низ величине

991
00:44:04,600 --> 00:44:09,000
26, где нулти елемент који
представља низ, а последњи

992
00:44:09,000 --> 00:44:11,810
елемент у сваки такав
представља низ З.

993
00:44:11,810 --> 00:44:15,520
>> Тако да ја предлажем, онда, да ови подаци
структура, познат као Трие, може бити

994
00:44:15,520 --> 00:44:17,600
Такође се користи за складиштење речи.

995
00:44:17,600 --> 00:44:21,740
Видели смо малочас како бисмо могли да сачувате
речи, или у овом случају имена, а ми

996
00:44:21,740 --> 00:44:25,440
раније видели како можемо да сачувате бројеве,
али ако се фокусирамо на имена или ниске

997
00:44:25,440 --> 00:44:27,460
овде, шта је занимљиво приметити.

998
00:44:27,460 --> 00:44:32,210
Ја тврдим да је име Максвел
унутар ове структуре података.

999
00:44:32,210 --> 00:44:33,730
Где видите Маквелл?

1000
00:44:33,730 --> 00:44:35,140
>> СТУДЕНТ: [ИНАУДИБЛЕ].

1001
00:44:35,140 --> 00:44:36,240
>> СПИКЕР 1: На левој страни.

1002
00:44:36,240 --> 00:44:39,910
Дакле, оно што је занимљиво са овим подацима
Структура је него у продавници

1003
00:44:39,910 --> 00:44:46,200
М-стринг-Кс-Ш-Е-Л-Л обрнута коса црта нула, све
цонтигуоусли, шта ти уместо тога

1004
00:44:46,200 --> 00:44:46,890
прати.

1005
00:44:46,890 --> 00:44:50,510
Ако је ово Трие као структуре података,
сваки од чворова чији је поново низ,

1006
00:44:50,510 --> 00:44:54,650
и желите да сачувате Маквелл, прво
индекс и тако корен је чвор, тако

1007
00:44:54,650 --> 00:44:57,810
да говори, на највишем чвор,
на локацију М, десно, тако

1008
00:44:57,810 --> 00:44:59,160
отприлике у средини.

1009
00:44:59,160 --> 00:45:03,740
А онда одатле, да пратите
показивач детету чворова, да тако кажем.

1010
00:45:03,740 --> 00:45:06,150
Дакле, у смислу породичног стабла,
ви га пратите на доле.

1011
00:45:06,150 --> 00:45:09,030
И то вас одвести у други чвор
Са леве стране, што је

1012
00:45:09,030 --> 00:45:10,540
само још један низ.

1013
00:45:10,540 --> 00:45:14,710
>> А онда, ако желите да сачувате Маквелл,
вам је показивач који представља

1014
00:45:14,710 --> 00:45:16,430
, Што је овај овде.

1015
00:45:16,430 --> 00:45:17,840
Онда идите на следећи чвор.

1016
00:45:17,840 --> 00:45:20,100
И обавештење - то је разлог зашто је слика
мало варљива -

1017
00:45:20,100 --> 00:45:21,990
Овај чвор изгледају супер мали.

1018
00:45:21,990 --> 00:45:26,050
Али, са десне стране је И и З.
То је само аутор је скраћени

1019
00:45:26,050 --> 00:45:27,630
слика, тако да заправо
виде ствари.

1020
00:45:27,630 --> 00:45:30,400
Иначе ова слика
ће бити веома широк.

1021
00:45:30,400 --> 00:45:36,180
Дакле, сада сте у индекс локацију Кс, онда
Е, онда је Е, онда сам, па шта је онда Л

1022
00:45:36,180 --> 00:45:37,380
то радозналост?

1023
00:45:37,380 --> 00:45:41,250
>> Па, ако користимо ову врсту нове
преузимају како да сачувате низ у

1024
00:45:41,250 --> 00:45:44,500
структура података, и даље треба да
суштини провјерите у подацима

1025
00:45:44,500 --> 00:45:47,250
структура која реч завршава овде.

1026
00:45:47,250 --> 00:45:50,830
Другим речима, сваки од ових чворова
некако мора да се сетим да смо

1027
00:45:50,830 --> 00:45:53,500
заправо пратили све ове показивача
и одлазе мало

1028
00:45:53,500 --> 00:45:58,370
презла на дну ове овде
структуре да укаже М-А-Кс-В-Е-Л-Л

1029
00:45:58,370 --> 00:46:00,230
заиста у овом структуром података.

1030
00:46:00,230 --> 00:46:02,040
>> Тако смо могли урадити на следећи начин.

1031
00:46:02,040 --> 00:46:06,810
Сваки од чворова у слици смо управо
тестера има једну, низ величине 27.

1032
00:46:06,810 --> 00:46:10,550
А сада је 27, јер у п сет шест,
ми заправо ћемо вам дати апостроф,

1033
00:46:10,550 --> 00:46:13,590
тако да можемо имати имена као О'Реилли
и други с апострофа.

1034
00:46:13,590 --> 00:46:14,820
Али, иста идеја.

1035
00:46:14,820 --> 00:46:17,710
Сваки од ових елемената у
низ указује на структуру

1036
00:46:17,710 --> 00:46:19,320
чвор, па само чвор.

1037
00:46:19,320 --> 00:46:21,430
Дакле, ово је веома подсећа
наше повезаној листи.

1038
00:46:21,430 --> 00:46:24,550
>> И онда имам Боолеан, што ћу
позовите реч, која це једноставно бити

1039
00:46:24,550 --> 00:46:29,120
ако је тачно реч завршава на тај
чвор у стаблу.

1040
00:46:29,120 --> 00:46:32,870
То практично представља мали
троугао смо видели малопре.

1041
00:46:32,870 --> 00:46:37,190
Дакле, ако је реч завршава на тај чвор у
дрво, да реч поље ће бити истина,

1042
00:46:37,190 --> 00:46:41,990
који је концептуално проверу искључен, или
смо цртање овај троугао, да тамо

1043
00:46:41,990 --> 00:46:44,080
је овде реч.

1044
00:46:44,080 --> 00:46:45,120
>> Дакле, ово је Трие.

1045
00:46:45,120 --> 00:46:48,540
А сада питање је, шта
је његово време ради?

1046
00:46:48,540 --> 00:46:49,930
Да ли је велики О од н?

1047
00:46:49,930 --> 00:46:51,410
Да ли је то нешто друго?

1048
00:46:51,410 --> 00:46:57,330
Па, ако сте н имена тих података
структура, Максвел само је једна од

1049
00:46:57,330 --> 00:47:02,330
их, што је покренут време
убацивање или проналажење Маквелл?

1050
00:47:02,330 --> 00:47:06,230

1051
00:47:06,230 --> 00:47:09,050
Шта је време извршавања
убацивања Маквелл?

1052
00:47:09,050 --> 00:47:11,740
Ако постоји н друга имена
Већ у табели?

1053
00:47:11,740 --> 00:47:12,507
Да?

1054
00:47:12,507 --> 00:47:15,429
>> СТУДЕНТ: [ИНАУДИБЛЕ].

1055
00:47:15,429 --> 00:47:17,550
>> СПИКЕР 1: Да, то је дужина
назива, зар не?

1056
00:47:17,550 --> 00:47:24,420
Дакле, М--к-Ш-Е-ја-ја тако да изгледа овако
алгоритам је велики о седам.

1057
00:47:24,420 --> 00:47:26,580
Сада, наравно, име
ће варирати у дужини.

1058
00:47:26,580 --> 00:47:27,380
Можда је то кратко име.

1059
00:47:27,380 --> 00:47:28,600
Можда је име дуже.

1060
00:47:28,600 --> 00:47:33,390
Али, оно што је кључно је да је овде
то је исти број.

1061
00:47:33,390 --> 00:47:36,810
А можда то није баш константна,
Али Бог, ако је реално, у

1062
00:47:36,810 --> 00:47:41,570
речник, вероватно постоји нека граница
о броју слова у

1063
00:47:41,570 --> 00:47:43,820
име особе у одређеној земљи.

1064
00:47:43,820 --> 00:47:46,940
>> И тако можемо претпоставити да
вредност је константна.

1065
00:47:46,940 --> 00:47:47,750
Ја не знам шта је то.

1066
00:47:47,750 --> 00:47:50,440
То је вероватно већи од
мислимо да јесте.

1067
00:47:50,440 --> 00:47:52,720
Јер увек постоји неки кутак
случај са лудом дуго име.

1068
00:47:52,720 --> 00:47:56,360
Дакле, назовимо је К, али је и даље
константа вероватно, јер сваки

1069
00:47:56,360 --> 00:48:00,190
име у свету, барем у
одређене земље, или је то дужина

1070
00:48:00,190 --> 00:48:01,780
краћи, тако да је константан.

1071
00:48:01,780 --> 00:48:04,490
Али, када смо рекли да је нешто велико
О константне вредности, шта је то

1072
00:48:04,490 --> 00:48:07,760
заиста одговара?

1073
00:48:07,760 --> 00:48:10,420
То је заправо иста ствар
како наводи константно време.

1074
00:48:10,420 --> 00:48:11,530
>> Сада смо некако вара, зар не?

1075
00:48:11,530 --> 00:48:15,340
Некако смо усклађивање неку теорију
овде да кажем да је добро, ред је к

1076
00:48:15,340 --> 00:48:17,450
заиста само наредби,
и то је константа време.

1077
00:48:17,450 --> 00:48:18,200
Али, то је стварно.

1078
00:48:18,200 --> 00:48:22,550
Пошто кључни увид овде је да
ако смо н имена већ у ово

1079
00:48:22,550 --> 00:48:26,010
структура података, а ми убаците Максвел,
је количина времена које је потребно да нас

1080
00:48:26,010 --> 00:48:29,530
убаците Маквелл уопште погођени
по томе колико других људи

1081
00:48:29,530 --> 00:48:31,100
су у структури података?

1082
00:48:31,100 --> 00:48:31,670
Не изгледа да буде.

1083
00:48:31,670 --> 00:48:36,280
Да сам имао више од милијарду елементе за ову
Трие, а затим убаците Маквелл, је

1084
00:48:36,280 --> 00:48:38,650
утицала је на све?

1085
00:48:38,650 --> 00:48:39,050
Не.

1086
00:48:39,050 --> 00:48:42,950
И то је за разлику од свих дневних података
структуре које смо видели до сада, где

1087
00:48:42,950 --> 00:48:46,820
време рада вашег алгоритма је
потпуно независно од тога колико

1088
00:48:46,820 --> 00:48:51,430
ствари јесте или није већ
у тој структури података.

1089
00:48:51,430 --> 00:48:54,650
>> И тако уз то пружа сада је
прилика за п шест сет, који ће

1090
00:48:54,650 --> 00:48:58,310
поново укључити спровођење сопствене
правописа, читање у 150.000

1091
00:48:58,310 --> 00:49:01,050
речи, како најбоље да сачувате
није нужно очигледан.

1092
00:49:01,050 --> 00:49:04,030
И иако сам тежио да пронађе
свети грал, не знам

1093
00:49:04,030 --> 00:49:05,330
тврде да је Трие.

1094
00:49:05,330 --> 00:49:09,810
У ствари, хеш табела може веома добро
доказати да буде много ефикаснији.

1095
00:49:09,810 --> 00:49:10,830
Али, то су само -

1096
00:49:10,830 --> 00:49:14,620
то је само једна од одлуке о дизајну
ћете морати да направите.

1097
00:49:14,620 --> 00:49:18,920
>> Али, хајде да затварање 50 или тако
секунди да се завири у оно што лежи

1098
00:49:18,920 --> 00:49:22,190
напред следеће недеље и даље што смо транзицији
из ове командне линије

1099
00:49:22,190 --> 00:49:26,220
света, ако Ц Програми веб ствари
на језицима као што су и ПХП и

1100
00:49:26,220 --> 00:49:30,350
Јава и сама интернет,
протоколи као што су ХТТП, који сте

1101
00:49:30,350 --> 00:49:32,870
узети здраво за готово годинама
сада, а већина сваког откуцаног

1102
00:49:32,870 --> 00:49:34,440
дана, можда, или видео.

1103
00:49:34,440 --> 00:49:37,420
И ми ћемо почети да одлепите
слојеви Шта је Интернет.

1104
00:49:37,420 --> 00:49:40,650
А шта је то код
чини основу данашње алата.

1105
00:49:40,650 --> 00:49:43,230
Дакле 50 секунди овог тизер овде.

1106
00:49:43,230 --> 00:49:46,570
Ја вам Ратници Интернету.

1107
00:49:46,570 --> 00:49:51,370
>> [ВИДЕО РЕПРОДУКЦИЈА]

1108
00:49:51,370 --> 00:49:56,764
>> -Он је дошао са поруком.

1109
00:49:56,764 --> 00:50:00,687
Са протоколом све своје.

1110
00:50:00,687 --> 00:50:13,370

1111
00:50:13,370 --> 00:50:19,780
Он је дошао у свет сурове зидова,
далеко унцаринг рутери, и опасности

1112
00:50:19,780 --> 00:50:22,600
горе од смрти.

1113
00:50:22,600 --> 00:50:23,590
Он је брз.

1114
00:50:23,590 --> 00:50:25,300
Он је јак.

1115
00:50:25,300 --> 00:50:27,700
Он је ТЦПИП.

1116
00:50:27,700 --> 00:50:30,420
И он има своју адресу.

1117
00:50:30,420 --> 00:50:32,920

1118
00:50:32,920 --> 00:50:34,590
Ратници у мрежи.

1119
00:50:34,590 --> 00:50:35,290
>> [ЕНД ВИДЕО РЕПРОДУКЦИЈА]

1120
00:50:35,290 --> 00:50:38,070
>> СПИКЕР 1: Тако интернету
ће радити од наредне недеље.

1121
00:50:38,070 --> 00:50:40,406