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

2
00:00:11,460 --> 00:00:12,250
>> Дејвид MALAN: Во ред.

3
00:00:12,250 --> 00:00:13,860
Добредојде назад кон CS50.

4
00:00:13,860 --> 00:00:16,190
Ова е почеток на недела 8.

5
00:00:16,190 --> 00:00:21,320
И се сети дека проблемот сет 5 завршила
со малку од предизвик.

6
00:00:21,320 --> 00:00:25,210
Значи под претпоставка дека ги обнови сите вашите
наставата соработници и фотографии издавачот на сертификати

7
00:00:25,210 --> 00:00:30,480
во датотеката card.raw, имате право
до сега се најдат сите оние луѓе, и

8
00:00:30,480 --> 00:00:34,510
еден среќен добитник ќе одиме дома со еден
на овие работи, скок движење

9
00:00:34,510 --> 00:00:37,450
уред кој можете да го користите за конечна
проекти, на пример.

10
00:00:37,450 --> 00:00:39,860
>> Ова, секоја година, доведува до
малку морничавост.

11
00:00:39,860 --> 00:00:43,480
И така она што мислев јас би го сторила е удел
со вас некои од забелешките кои имаат

12
00:00:43,480 --> 00:00:47,370
качил напред и назад во текот
на персоналот листа на крајот.

13
00:00:47,370 --> 00:00:51,110
На пример, само минатата ноќ, цитат
unquote, од еден на персоналот

14
00:00:51,110 --> 00:00:55,000
членови, "Јас само имаше еден студент тропаат
на мојата врата да се слика со мене.

15
00:00:55,000 --> 00:00:59,020
Stalkers, ќе ти кажам. "Го започна натпреварот
прилично описни и потоа се пресели

16
00:00:59,020 --> 00:01:02,830
за да, еден час или па подоцна ", имав една
Студентот ме чека по секција

17
00:01:02,830 --> 00:01:06,080
и тој имаше сите наши имиња и фотографии
на некои листови хартија. "Сите во право.

18
00:01:06,080 --> 00:01:09,230
Така организирани, но не
сето тоа гаден уште.

19
00:01:09,230 --> 00:01:12,520
>> Потоа, ", бев надвор од градот овој викенд,
и кога се вратив, имаше еден во

20
00:01:12,520 --> 00:01:12,630
мојата

21
00:01:12,630 --> 00:01:16,740
спалната соба. "[Смеа]

22
00:01:16,740 --> 00:01:20,410
Дејвид MALAN: Следна цитат од на персоналот
член ", дојде еден студент во мојата куќа на

23
00:01:20,410 --> 00:01:25,330
Самервил на 04:00 ова утро. "Напред
персонал, "Јас имам на мојот хотел во Сан

24
00:01:25,330 --> 00:01:30,016
Франциско и студент е на чекање за
мене во фоајето со три DSLRs. "

25
00:01:30,016 --> 00:01:31,510
Тип на камера.

26
00:01:31,510 --> 00:01:34,980
"Јас не сум дури и врз вработените овој семестар,
но еден студент провалил во мојата куќа

27
00:01:34,980 --> 00:01:40,480
наутро и се евидентираат целата работа
со Google стакло. "И тогаш на крај,

28
00:01:40,480 --> 00:01:43,650
"Најмалку 12 лица беа со нетрпение
чека за мене кога ја добив од мојата

29
00:01:43,650 --> 00:01:44,800
лимузина, а потоа јас

30
00:01:44,800 --> 00:01:46,970
разбудил. "Сите во право.

31
00:01:46,970 --> 00:01:57,690
Па меѓу фотографии, како што може
потсетиме, се овој човек тука, кој ќе

32
00:01:57,690 --> 00:02:01,850
би можеле да знаат како Мило Банана, кој живее
со Lauren Карваљо, нашата глава

33
00:02:01,850 --> 00:02:02,905
настава соработник.

34
00:02:02,905 --> 00:02:05,170
Мило, Мило, дојди овде момче.

35
00:02:05,170 --> 00:02:06,320
Мило.

36
00:02:06,320 --> 00:02:08,650
Мило.

37
00:02:08,650 --> 00:02:12,230
Иначе, тој носи на Google стакло, па
ние ќе ви покаже сето ова после.

38
00:02:12,230 --> 00:02:16,190
Па ова е Мило, ако би сакал да
да фотографира со него потоа.

39
00:02:16,190 --> 00:02:18,240
Ако сакате да внимавате
на публиката таму.

40
00:02:18,240 --> 00:02:19,430
OK.

41
00:02:19,430 --> 00:02:20,200
Тоа е добро снимката.

42
00:02:20,200 --> 00:02:22,556
Па, Мило Банана.

43
00:02:22,556 --> 00:02:23,941
Ох, не го правам тоа.

44
00:02:23,941 --> 00:02:29,020
>> [Смеа]

45
00:02:29,020 --> 00:02:29,470
>> OK.

46
00:02:29,470 --> 00:02:34,550
Па еден збор, тогаш на она што се наоѓа напред,
бидејќи, како што ние почнат да се транзиција,

47
00:02:34,550 --> 00:02:38,410
оваа недела конкретно, од C во
командната линија на животната средина за PHP и

48
00:02:38,410 --> 00:02:42,720
Вклучите Javascript-и SQL и HTML и CSS во
веб-базирана средина, ќе биде

49
00:02:42,720 --> 00:02:44,490
опремување на вас со сите
повеќе знаење за

50
00:02:44,490 --> 00:02:46,010
потенцијални крајни проекти.

51
00:02:46,010 --> 00:02:49,240
Кон таа цел, се разбира има
Традицијата на одржување на семинари кои

52
00:02:49,240 --> 00:02:50,950
се на површни теми
на курсот.

53
00:02:50,950 --> 00:02:54,330
Многу поврзана со програмирање и да
стан развој и така натаму, но

54
00:02:54,330 --> 00:02:57,010
не мора да посегнуваат
на курсот е наставната програма.

55
00:02:57,010 --> 00:03:00,250
>> Па ако може да бидат заинтересирани во една
или повеќе од семинари оваа година,

56
00:03:00,250 --> 00:03:02,530
регистрирам cs50.net/seminar.

57
00:03:02,530 --> 00:03:06,170
Постојат постари семинари
на cs50.net/seminars.

58
00:03:06,170 --> 00:03:10,620
И на списокот досега за оваа година
се неверојатни веб апликации со Ruby on

59
00:03:10,620 --> 00:03:13,580
Шини, која е алтернатива
јазик во PHP.

60
00:03:13,580 --> 00:03:14,900
Компјутерска лингвистика.

61
00:03:14,900 --> 00:03:18,710
Воведувањето на iOS, кој е
платформа која се користи за iPhone и

62
00:03:18,710 --> 00:03:19,850
iPad развој.

63
00:03:19,850 --> 00:03:22,890
JavaScript за веб апликации, ние ќе ги покрие
тоа, но во овој семинар, ќе одам

64
00:03:22,890 --> 00:03:24,070
во повеќе детали.

65
00:03:24,070 --> 00:03:27,390
>> Скок движење, па ние всушност ќе имаме некои
на нашите пријатели од скок движење,

66
00:03:27,390 --> 00:03:29,160
на самата компанија, да ни се придружат.

67
00:03:29,160 --> 00:03:31,800
Утре, всушност, да обезбеди
рацете на семинарот, ако

68
00:03:31,800 --> 00:03:33,320
од интерес за вас.

69
00:03:33,320 --> 00:03:38,770
Meteor.js, алтернативна техника за
користејќи го вклучите Javascript не во прелистувачот,

70
00:03:38,770 --> 00:03:39,970
но на серверот.

71
00:03:39,970 --> 00:03:42,110
Node.js, што е многу многу
Во таа смисла, како и.

72
00:03:42,110 --> 00:03:43,650
Елегантен Андроид дизајн.

73
00:03:43,650 --> 00:03:46,990
Андроид да се биде многу популарна алтернатива
на iOS и Windows Телефон

74
00:03:46,990 --> 00:03:48,790
и други мобилни платформи.

75
00:03:48,790 --> 00:03:51,180
И веб безбедност активна одбрана.

76
00:03:51,180 --> 00:03:54,590
>> Така, всушност, ако би сакал
да се вклучат во тоа, нека ме

77
00:03:54,590 --> 00:03:55,840
направи забелешка на тоа.

78
00:03:55,840 --> 00:03:57,790
Ние сме многу среќни да се каже дека
нашите пријатели во скок

79
00:03:57,790 --> 00:03:59,140
Движење, што е стартување -

80
00:03:59,140 --> 00:04:01,300
овој уред навистина само што дојде
надвор пред неколку месеци -

81
00:04:01,300 --> 00:04:05,960
нема грациозно донираа 30 такви уреди
на класата за онолку студенти, доколку

82
00:04:05,960 --> 00:04:08,670
сакате да ги позајмите хардвер
кон крајот семестар и го користат за

83
00:04:08,670 --> 00:04:10,390
вистински конечниот проект.

84
00:04:10,390 --> 00:04:11,890
Тие ги поддржуваат голем број на јазици.

85
00:04:11,890 --> 00:04:16,040
Никој од нив Ц, никој од нив не PHP, така
сфатат една или повеќе од овие семинари

86
00:04:16,040 --> 00:04:16,899
може да се покаже на интерес.

87
00:04:16,899 --> 00:04:19,730
И сите од нив ќе се снима во
случај дека не сте во можност

88
00:04:19,730 --> 00:04:21,380
да присуствува во лице.

89
00:04:21,380 --> 00:04:25,000
Распоредот бидат објавени преку
e-mail, како што се зацврсти соби.

90
00:04:25,000 --> 00:04:28,460
>> И на крај, ако одите на
projects.cs.50.net, ова е веб-сајт

91
00:04:28,460 --> 00:04:31,450
ние одржување секоја година дека ние покани
луѓе од заедницата, факултет,

92
00:04:31,450 --> 00:04:36,420
одделенија, персонал, и двете
во надвор од CS50 да

93
00:04:36,420 --> 00:04:37,730
предложи проектни идеи.

94
00:04:37,730 --> 00:04:39,050
Работите од интерес за студентски групи.

95
00:04:39,050 --> 00:04:40,600
Работите од интерес за оддели.

96
00:04:40,600 --> 00:04:43,990
Па се претвори таму ако сте се борат
со несигурност за тоа што

97
00:04:43,990 --> 00:04:46,700
себе би сакале да се справи.

98
00:04:46,700 --> 00:04:51,760
>> Па последен пат воведе веројатно
повеќе комплексна структура на податоци отколку што би

99
00:04:51,760 --> 00:04:53,300
гледа во недели минатото.

100
00:04:53,300 --> 00:04:56,550
Ние би биле користење на низи прилично
среќно како корисно ако

101
00:04:56,550 --> 00:04:58,160
симплистички податоци структура.

102
00:04:58,160 --> 00:05:00,570
Тогаш ние воведе овие, кои
се разбира се поврзани листи.

103
00:05:00,570 --> 00:05:05,470
И она што беше еден од мотивите за
воведување на оваа податочна структура?

104
00:05:05,470 --> 00:05:06,930
Да?

105
00:05:06,930 --> 00:05:07,250
Што е тоа?

106
00:05:07,250 --> 00:05:08,080
>> ПУБЛИКАТА: Динамички големина.

107
00:05:08,080 --> 00:05:09,040
>> Дејвид MALAN: Динамички големина.

108
00:05:09,040 --> 00:05:11,890
Значи додека во низа, што треба да
знаат нејзината големина однапред кога

109
00:05:11,890 --> 00:05:12,740
ќе ја распредели.

110
00:05:12,740 --> 00:05:14,380
Во поврзана листа, вие не
Треба да знаете дека.

111
00:05:14,380 --> 00:05:17,610
Можете да само Примерок, или поопшто,
распредели дополнителен

112
00:05:17,610 --> 00:05:20,720
јазол, така да се каже, секој пат кога ќе
сакате да го вметнете повеќе податоци.

113
00:05:20,720 --> 00:05:22,670
И јазол не предодредено значење.

114
00:05:22,670 --> 00:05:25,580
Тоа е само генерички поим опишувајќи
некој вид на сад, дека ние сме

115
00:05:25,580 --> 00:05:29,610
користење во нашата структура на податоци за чување
некој предмет на интерес, кој во овој

116
00:05:29,610 --> 00:05:31,750
случај да се случи да бидат цели броеви.

117
00:05:31,750 --> 00:05:33,160
>> Но секогаш постои Губитокот.

118
00:05:33,160 --> 00:05:38,070
Па да добиеме динамичен големини на податоци
структура, но која цена ние плаќаат?

119
00:05:38,070 --> 00:05:40,040
Она што е во надолна линија на поврзани листи?

120
00:05:40,040 --> 00:05:41,006
Да?

121
00:05:41,006 --> 00:05:41,980
>> ПУБЛИКАТА: Потребна повеќе меморија.

122
00:05:41,980 --> 00:05:44,240
>> Дејвид MALAN: Се бара повеќе
меморија, како точно?

123
00:05:44,240 --> 00:05:46,440
>> ПУБЛИКАТА: [нечујни].

124
00:05:46,440 --> 00:05:47,050
>> Дејвид MALAN: Токму така.

125
00:05:47,050 --> 00:05:50,460
Така, сега имаме совети преземањето
дополнителна меморија што ние претходно

126
00:05:50,460 --> 00:05:53,040
не се потребни, бидејќи предност
на низа, се разбира, е тоа што

127
00:05:53,040 --> 00:05:54,860
сè е соседни, назад
да се врати да се врати, кои

128
00:05:54,860 --> 00:05:56,380
ви дава случаен пристап.

129
00:05:56,380 --> 00:06:00,710
Затоа што само со помош квадратни загради
нотација, или повеќе технички покажувачот

130
00:06:00,710 --> 00:06:03,580
аритметика, многу едноставна Покрај тоа,
можете да пристапите на некој

131
00:06:03,580 --> 00:06:05,700
елементи во постојана време.

132
00:06:05,700 --> 00:06:08,975
И во Всушност, тоа е вид на алудирајќи на
друга цена, дека ние сме плаќаат со

133
00:06:08,975 --> 00:06:09,760
поврзана листа.

134
00:06:09,760 --> 00:06:13,890
>> Што се случува со трчање време на
нешто како пребарување, ако сакам да

135
00:06:13,890 --> 00:06:17,270
најдете некои вредност и во внатрешноста
на поврзана листа?

136
00:06:17,270 --> 00:06:20,290
Што значи моето трчање време стана?

137
00:06:20,290 --> 00:06:21,560
Биг О од n.

138
00:06:21,560 --> 00:06:24,060
Ако тоа е сортирана да?

139
00:06:24,060 --> 00:06:25,440
Што ако на податочна структура е сортирана?

140
00:06:25,440 --> 00:06:28,640
Можам да го направи подобро од големите
О на n за пребарување?

141
00:06:28,640 --> 00:06:31,700
Не, затоа што во најлош случај тоа би можело да
многу добро да бидат подредени, но бројот

142
00:06:31,700 --> 00:06:32,950
сте во потрага за да биде голема.

143
00:06:32,950 --> 00:06:35,370
Тоа би можело да биде број 100, која
може да се случи да биде на сите

144
00:06:35,370 --> 00:06:36,410
начинот на кој на крајот.

145
00:06:36,410 --> 00:06:39,950
И затоа што може само да пристапите на поврзан
листа во оваа имплементација од страна на

146
00:06:39,950 --> 00:06:42,690
начин на својот прв јазол, ти си
уште вид на надвор од среќа.

147
00:06:42,690 --> 00:06:47,450
Ќе мора да напречни целата работа
од прво до последно, со цел да се најде

148
00:06:47,450 --> 00:06:49,150
дека голема вредност како 100.

149
00:06:49,150 --> 00:06:51,350
Или да се утврди дали тоа е
дури и не постојат.

150
00:06:51,350 --> 00:06:55,960
>> Па не можеме да го направи она што алгоритам во податоците
структура што личи ова?

151
00:06:55,960 --> 00:06:59,460
Не можеме да правиме бинарни пребарување, бидејќи
бинарни пребарување потребно дека имавме

152
00:06:59,460 --> 00:07:00,740
случаен пристап.

153
00:07:00,740 --> 00:07:04,500
Ние може само да се фрлиш од локација за
локација, без да ги следат

154
00:07:04,500 --> 00:07:07,080
овие трошки од леб во форма
на сите овие совети.

155
00:07:07,080 --> 00:07:08,300
>> Сега, како сме спроведување на оваа?

156
00:07:08,300 --> 00:07:12,830
Па, ако ние одиме на екранот тука, ако
ние брзо може да reimplement овие податоци

157
00:07:12,830 --> 00:07:13,440
структура -

158
00:07:13,440 --> 00:07:15,670
мојот ракопис не е сето она што
голем тука, но ние ќе се обидеме.

159
00:07:15,670 --> 00:07:22,030
Па typedef struct, и што правел јас
сакате да го повикате ова нешто овде?

160
00:07:22,030 --> 00:07:22,960
Јазол.

161
00:07:22,960 --> 00:07:24,580
Па јас ќе добиете ни почнати.

162
00:07:24,580 --> 00:07:27,860
И сега, она што треба да бидат внатре на
на податочна структура за која одделно

163
00:07:27,860 --> 00:07:28,430
поврзана листа?

164
00:07:28,430 --> 00:07:29,950
Колку полиња?

165
00:07:29,950 --> 00:07:30,450
>> Па две.

166
00:07:30,450 --> 00:07:31,570
Една од нив е прилично лесно.

167
00:07:31,570 --> 00:07:33,050
Па int n.

168
00:07:33,050 --> 00:07:35,930
И ние може да се нарече n ништо сакаме,
но тоа треба да биде цел број, ако ние сме

169
00:07:35,930 --> 00:07:37,660
спроведување на поврзана листа за ints.

170
00:07:37,660 --> 00:07:41,920
И сега што го прави вториот
поле треба да биде?

171
00:07:41,920 --> 00:07:43,460
Struct јазол *.

172
00:07:43,460 --> 00:07:50,570
Значи, ако го направам struct јазол *, а потоа јас
да го наречеме овој, исто така, она што сакам,

173
00:07:50,570 --> 00:07:53,510
но само да биде јасно Ќе му се јавам
тоа следната, како што ние си правеле.

174
00:07:53,510 --> 00:07:55,270
И тогаш Јас ќе ја затворам мојата кадрава загради.

175
00:07:55,270 --> 00:08:00,700
>> И сега, како минатиот пат,
Ја ставив јазол овде долу.

176
00:08:00,700 --> 00:08:03,830
Но, ако јас сум прогласување ова е како
јазол, зошто јас се мачам да биде толку

177
00:08:03,830 --> 00:08:07,320
опширниот тука во декларирањето struct
јазол * следната, како што се противат

178
00:08:07,320 --> 00:08:09,210
само јазол * следно?

179
00:08:09,210 --> 00:08:09,904
Да?

180
00:08:09,904 --> 00:08:12,810
>> ПУБЛИКАТА: [нечујни].

181
00:08:12,810 --> 00:08:14,050
>> Дејвид MALAN: Токму така.

182
00:08:14,050 --> 00:08:14,530
Токму така.

183
00:08:14,530 --> 00:08:18,320
Бидејќи C навистина ќе ве однесе буквално и
само гледа дефиницијата на јазол

184
00:08:18,320 --> 00:08:21,230
патот надолу тука, не можете да
се однесува на тоа тука горе.

185
00:08:21,230 --> 00:08:24,760
Значи ние треба овој вид на превентивна
декларација тука, што е значително

186
00:08:24,760 --> 00:08:25,390
повеќе опширниот.

187
00:08:25,390 --> 00:08:27,810
Struct јазол, тоа значи дека
ние сега може да го пристап

188
00:08:27,810 --> 00:08:29,760
внатрешноста на податочна структура.

189
00:08:29,760 --> 00:08:33,370
>> И како настрана, бидејќи ова е
станува малку повеќе субјективен сега,

190
00:08:33,370 --> 00:08:36,230
ѕвездата технички може да оди тука,
тоа може да оди тука, може да

191
00:08:36,230 --> 00:08:37,179
дури и одат во средината.

192
00:08:37,179 --> 00:08:39,890
Ние сме донесени, во стилот водич за
на курсот, на конвенцијата на ставање

193
00:08:39,890 --> 00:08:42,299
ѕвездата веднаш до податоци
тип, кој во овој случај,

194
00:08:42,299 --> 00:08:43,460
ќе биде struct јазол.

195
00:08:43,460 --> 00:08:46,620
Но сфати во многу учебници и
онлајн референци, можеби навистина

196
00:08:46,620 --> 00:08:48,450
види тоа на другата страна.

197
00:08:48,450 --> 00:08:52,200
Но само сфатат дека и двете ќе всушност се
работат и можете едноставно треба да биде

198
00:08:52,200 --> 00:08:52,970
доследни.

199
00:08:52,970 --> 00:08:53,580
>> Сите во право.

200
00:08:53,580 --> 00:08:55,630
Така што беше нашата декларација
на struct јазол.

201
00:08:55,630 --> 00:08:59,430
Но потоа почнавме прави повеќе
софистицирани нешта.

202
00:08:59,430 --> 00:09:03,410
На пример, решивме да се воведе
нешто како хаш табелата.

203
00:09:03,410 --> 00:09:08,160
Па овде е хаш табелата на големина n,
индексирани од 0 на горниот лев агол на n

204
00:09:08,160 --> 00:09:09,690
минус 1 на дното лево.

205
00:09:09,690 --> 00:09:11,640
Ова може да биде хаш
маса за ништо.

206
00:09:11,640 --> 00:09:15,340
Но, она што видови на работите си зборуваме
за користење на хаш табелата за?

207
00:09:15,340 --> 00:09:18,370
Складирање на што?

208
00:09:18,370 --> 00:09:18,800
>> Имиња.

209
00:09:18,800 --> 00:09:20,870
Можеме да направиме имиња како
ние го сторивме последен пат.

210
00:09:20,870 --> 00:09:22,200
И навистина, може да складира ништо.

211
00:09:22,200 --> 00:09:24,640
И ние ќе го гледаат ова повторно во
PHP и во JavaScript.

212
00:09:24,640 --> 00:09:28,550
А хаш табелата е убав вид на Швајцарската
Војнички нож кој ви овозможува да ги чувате

213
00:09:28,550 --> 00:09:33,690
доста она што го сакате во внатрешноста на
тоа со асоцирањето клучеви со вредности.

214
00:09:33,690 --> 00:09:34,770
Копчињата со вредности.

215
00:09:34,770 --> 00:09:37,800
>> Сега, во овој едноставен случај, нашите
копчињата се само бројки.

216
00:09:37,800 --> 00:09:40,380
Ние сме за воведување на хаш
маса како низа.

217
00:09:40,380 --> 00:09:43,500
И така на копчињата се 0,
1, 2, и така натаму.

218
00:09:43,500 --> 00:09:47,200
И така ние, како луѓе, одлучи минатата
недела дека знаете што, ако ние сме

219
00:09:47,200 --> 00:09:50,410
ќе продавница имиња, ајде да
арбитрарно, туку прилично разумно,

220
00:09:50,410 --> 00:09:54,680
претпостави дека Алис, А името,
само ќе бидат индексирани во 0.

221
00:09:54,680 --> 00:09:58,030
И Боб, име Б, ќе бидат индексирани
во 1, и така натаму.

222
00:09:58,030 --> 00:10:02,490
Па моравме мапирање помеѓу влезови,
кои се стрингови, и хаш

223
00:10:02,490 --> 00:10:04,560
локации, кои се бројки.

224
00:10:04,560 --> 00:10:07,740
>> Така што процесот е општо познато како
хаш функција, и можете да навистина

225
00:10:07,740 --> 00:10:09,130
се спроведе тоа во кодот.

226
00:10:09,130 --> 00:10:12,080
Ако сакав да се спроведе hash функција
кои го прави токму она што го

227
00:10:12,080 --> 00:10:17,070
само што е опишано од последниот пат, би можел да
прогласи функција која зема, како

228
00:10:17,070 --> 00:10:18,330
влез за пример -

229
00:10:18,330 --> 00:10:22,190
и ајде да го направите тоа на овој
екранот овде.

230
00:10:22,190 --> 00:10:26,180
Ако сакав да се спроведе хаш
функција, би можел да кажам

231
00:10:26,180 --> 00:10:27,410
нешто како ова.

232
00:10:27,410 --> 00:10:29,030
>> Тоа се случува да се врати int.

233
00:10:29,030 --> 00:10:33,600
Тоа се случува да се нарече хаш, а тоа е
ќе го прифати како аргумент за

234
00:10:33,600 --> 00:10:38,920
стринг, или можеме да бидеме повеќе соодветна сега,
и да каже char *, ние ќе го наречеме s.

235
00:10:38,920 --> 00:10:43,840
А потоа сите оваа функција треба да се направи,
во крајна линија, е се врати int.

236
00:10:43,840 --> 00:10:45,990
Сега, како го прави тоа што би можело да
Не биди толку јасни.

237
00:10:45,990 --> 00:10:49,510
Одам да се спроведе оваа без никакви
форма на проверка на грешка моментов.

238
00:10:49,510 --> 00:10:55,740
Јас сум само ќе слепо се каже, да се вратите
она што е во е заградата 0, минус,

239
00:10:55,740 --> 00:10:58,850
да речеме, капитал-запирка.

240
00:10:58,850 --> 00:10:59,960
>> Целосно скршен.

241
00:10:59,960 --> 00:11:02,620
Тоа не е совршен, бидејќи
еден, што ако s е нула?

242
00:11:02,620 --> 00:11:04,000
Лоши работи се случува да се случи.

243
00:11:04,000 --> 00:11:07,940
Две, што ако првата буква во оваа
името не е голема буква?

244
00:11:07,940 --> 00:11:09,860
Тоа не се случува да се сврти
добро или.

245
00:11:09,860 --> 00:11:11,970
Тоа би можело да биде мали букви
или не писмо на сите.

246
00:11:11,970 --> 00:11:15,520
Така целосно простор за подобрување тука,
но ова е основната идеја.

247
00:11:15,520 --> 00:11:19,010
>> Она што ние го опиша минатата недела вербално
само процесот на мапирање Алис да

248
00:11:19,010 --> 00:11:23,360
0 и Боб до 1 може да се изрази
сигурно повеќе formulaically како C

249
00:11:23,360 --> 00:11:24,320
функционира тука.

250
00:11:24,320 --> 00:11:28,630
Повика повторно хаш, потребно е стринг како
влез, а потоа некако не нешто

251
00:11:28,630 --> 00:11:31,020
со што влезот за да се произведе излез.

252
00:11:31,020 --> 00:11:34,130
Не за разлика од нашите црна кутија опис
дека ние сме одамна направено.

253
00:11:34,130 --> 00:11:36,550
Не знам како ова може да биде
работат под хауба.

254
00:11:36,550 --> 00:11:40,120
>> За проблемот сет 6, еден од предизвиците
е за вас да се одлучи што

255
00:11:40,120 --> 00:11:41,920
Вашиот хаш функција ќе биде?

256
00:11:41,920 --> 00:11:45,760
Она што се случува за да биде внатре во тоа црно
кутија, и веројатно, тоа ќе биде

257
00:11:45,760 --> 00:11:50,380
малку поинтересно од оваа, и
дефинитивно повеќе склони кон грешки

258
00:11:50,380 --> 00:11:53,180
проверка од овој особено
имплементација.

259
00:11:53,180 --> 00:11:54,580
>> Но проблеми можат да настанат, нели?

260
00:11:54,580 --> 00:11:57,760
Ако имаме податочна структура, како што тоа
еден, што е еден од проблемите

261
00:11:57,760 --> 00:12:01,600
можете да го извршите во текот на времето како ќе го вметнете
се повеќе и повеќе имиња во

262
00:12:01,600 --> 00:12:02,880
хаш табелата?

263
00:12:02,880 --> 00:12:04,630
Ќе добиете судири, нели?

264
00:12:04,630 --> 00:12:07,560
Што ако имате Алис и Арон,
две лица чии имиња се случи

265
00:12:07,560 --> 00:12:08,190
да се започне со?

266
00:12:08,190 --> 00:12:11,660
Кој моли на прашањето, каде што
стави втората такво име?

267
00:12:11,660 --> 00:12:15,050
>> Добро, можеби наивно само да го стави
каде Боб припаѓа, но потоа Боб е

268
00:12:15,050 --> 00:12:17,300
вид на зезнав ако се обидете да
вметнете неговото име следната и

269
00:12:17,300 --> 00:12:18,240
нема простор за него.

270
00:12:18,240 --> 00:12:21,400
Така што може да се стави Боб каде што Чарли е,
и можете да замислите оваа многу брзо

271
00:12:21,400 --> 00:12:23,020
пренесени во малку неред.

272
00:12:23,020 --> 00:12:25,600
Нешто линеарно на крајот, каде што
едноставно мора да пребарувате на целата работа

273
00:12:25,600 --> 00:12:28,190
во потрага по Алис или Боб
или Арон или Чарли.

274
00:12:28,190 --> 00:12:33,230
>> Така, наместо ние предложи, наместо само
линеарно љубопитство за отворени простори

275
00:12:33,230 --> 00:12:36,450
и plopping имињата таму, ние
предложи познавач пристап.

276
00:12:36,450 --> 00:12:41,740
А хаш табелата спроведува уште со
низа на индексите, но податоците тип на

277
00:12:41,740 --> 00:12:44,500
оние индекси сега се покажувачи.

278
00:12:44,500 --> 00:12:47,360
Покажувачи на што?

279
00:12:47,360 --> 00:12:48,730
Покажувачи на поврзани листи.

280
00:12:48,730 --> 00:12:53,330
>> Бидејќи се потсетиме дека поврзана листа е
навистина само покажувач на еден јазол, и

281
00:12:53,330 --> 00:12:57,110
јазол има следните поле, и тој јазол
има следниот поле, и така натаму.

282
00:12:57,110 --> 00:13:00,690
Значи сега ќе можете да размислувате на оваа низа на
на левата страна од хаш табелата како

283
00:13:00,690 --> 00:13:01,820
што доведува до поврзана листа.

284
00:13:01,820 --> 00:13:07,000
Предноста на кој е ако добиете
судир меѓу Алис и Арон,

285
00:13:07,000 --> 00:13:09,300
што правиш со
втор таков човек?

286
00:13:09,300 --> 00:13:14,150
Вие само го закачите или неа да
крајот, или дури и на почетокот

287
00:13:14,150 --> 00:13:15,490
на тој поврзана листа.

288
00:13:15,490 --> 00:13:17,340
>> А всушност, ајде само глупак преку
дека за само една секунда.

289
00:13:17,340 --> 00:13:18,640
Каде што ќе направи најмногу смисла?

290
00:13:18,640 --> 00:13:22,060
Ако јас внесете Алис и таа завршува на
првата локација, тогаш јас се обидувам да

291
00:13:22,060 --> 00:13:25,310
внесете име на Aaron, и има
очигледно судир, јас треба да се стави

292
00:13:25,310 --> 00:13:27,400
него на почетокот
на поврзана листа?

293
00:13:27,400 --> 00:13:30,944
Тоа е во тоа прва локација,
или на крајот?

294
00:13:30,944 --> 00:13:31,440
>> ПУБЛИКАТА: [нечујни].

295
00:13:31,440 --> 00:13:31,990
>> Дејвид MALAN: OK.

296
00:13:31,990 --> 00:13:32,490
Слушнав почеток.

297
00:13:32,490 --> 00:13:33,903
Зошто на почетокот?

298
00:13:33,903 --> 00:13:34,750
>> ПУБЛИКАТА: [нечујни].

299
00:13:34,750 --> 00:13:34,940
>> Дејвид MALAN: OK.

300
00:13:34,940 --> 00:13:36,520
Тоа е азбучен, па тоа е убаво.

301
00:13:36,520 --> 00:13:37,330
Тоа е добра имотот.

302
00:13:37,330 --> 00:13:39,335
Тоа ќе ме спаси некое време потенцијално.

303
00:13:39,335 --> 00:13:43,290
Тоа нема да ми дозволи да направи бинарни пребарување, но јас
најмалку би можело да биде во можност да се пробие

304
00:13:43,290 --> 00:13:47,340
на јамка ако Сфаќам, добро, јас сум начин
минатото биле Арон да биде во оваа

305
00:13:47,340 --> 00:13:48,310
сортирани поврзаните листа.

306
00:13:48,310 --> 00:13:50,360
Јас не треба да отпад моето време бараат
по целиот пат до крај.

307
00:13:50,360 --> 00:13:51,530
Па тоа е разумно.

308
00:13:51,530 --> 00:13:54,710
Зошто друго можеби ќе сакате да го вметнете
на судирање име на

309
00:13:54,710 --> 00:13:56,660
почетокот на листа?

310
00:13:56,660 --> 00:13:57,397
Што е тоа?

311
00:13:57,397 --> 00:13:58,680
>> ПУБЛИКАТА: [нечујни].

312
00:13:58,680 --> 00:14:00,820
>> Дејвид MALAN: Тоа би можело да трае долго време
да се дојде до крајот на листата.

313
00:14:00,820 --> 00:14:02,490
И всушност, подолго и подолго.

314
00:14:02,490 --> 00:14:04,920
На повеќе имиња ќе го вметнете дека
Започнете со, на подолг дека

315
00:14:04,920 --> 00:14:06,280
синџир се случува да се добие.

316
00:14:06,280 --> 00:14:07,890
На подолг дека се поврзани
листа ќе добиете.

317
00:14:07,890 --> 00:14:09,420
Па ти си навистина само
трошат вашето време.

318
00:14:09,420 --> 00:14:14,070
Можеби ти си подобро одржување
постојана вметнување време, голем О од 1,

319
00:14:14,070 --> 00:14:18,470
од секогаш ставање на судир името на
почетокот на поврзана листа,

320
00:14:18,470 --> 00:14:21,230
и не се грижам колку
за сортирање.

321
00:14:21,230 --> 00:14:22,600
>> Кој е најдобар одговор?

322
00:14:22,600 --> 00:14:23,320
Тоа е јасно.

323
00:14:23,320 --> 00:14:26,140
Тој вид на зависи од тоа што
дистрибуција е, она што моделот е

324
00:14:26,140 --> 00:14:27,850
од имињата што се вметнување.

325
00:14:27,850 --> 00:14:29,430
Тоа не е нужно
очигледен одговор.

326
00:14:29,430 --> 00:14:33,100
Но тука за да, пак, е
дизајн можност.

327
00:14:33,100 --> 00:14:37,220
>> Па ние потоа погледна во оваа работа, која
е навистина другата голема можност

328
00:14:37,220 --> 00:14:38,180
за p-сет 6.

329
00:14:38,180 --> 00:14:41,770
И ќе сфати, ако веќе не сте,
Zamyla нурка во двете од овие, хеш

330
00:14:41,770 --> 00:14:43,260
маси и неуспешни обиди, во повеќе детали.

331
00:14:43,260 --> 00:14:45,630
И видео Walkthrough е
вградени во спецификации п-сет.

332
00:14:45,630 --> 00:14:46,590
Ова беше Trie -

333
00:14:46,590 --> 00:14:51,670
Т-Р-И-Е. И она што беше интересно за
ова беше тоа што трчање време

334
00:14:51,670 --> 00:14:59,510
на потрага по име, како Максвел
последен пат, беше големо O на што?

335
00:14:59,510 --> 00:15:01,040
Што е тоа?

336
00:15:01,040 --> 00:15:01,920
>> ПУБЛИКАТА: Бројот на букви.

337
00:15:01,920 --> 00:15:02,550
>> Дејвид MALAN: Број на букви.

338
00:15:02,550 --> 00:15:03,210
Слушнав две работи.

339
00:15:03,210 --> 00:15:04,630
Број на букви и постојана време.

340
00:15:04,630 --> 00:15:05,540
Па ајде да одиме со тоа во прв план.

341
00:15:05,540 --> 00:15:06,410
Бројот на букви.

342
00:15:06,410 --> 00:15:10,195
Па, ова податочна структура, се потсетиме, е
како дрво, семејство дрво, секоја од

343
00:15:10,195 --> 00:15:12,860
чии јазли се составени од низи.

344
00:15:12,860 --> 00:15:16,300
И оние низи се покажувачи на
други такви јазли, или други слични

345
00:15:16,300 --> 00:15:17,670
низи на дрвото.

346
00:15:17,670 --> 00:15:22,890
>> Значи, ако сакавме да потоа да одреди
дали Максвел е овде, би можел да одам

347
00:15:22,890 --> 00:15:26,890
на првата низа, во самиот врв на
на дрво, т.н. корен, врвот на

348
00:15:26,890 --> 00:15:30,521
на Trie, а потоа следат покажувачот метри,
тогаш покажувач, а потоа X,

349
00:15:30,521 --> 00:15:31,710
W, E, ј, л.

350
00:15:31,710 --> 00:15:34,910
А потоа кога ќе видам некои посебни симбол,
означувал тука како триаголник.

351
00:15:34,910 --> 00:15:38,480
Во кодот ќе видите ние предлагаме дека
спроведува како bool, само велејќи да

352
00:15:38,480 --> 00:15:40,540
или не, збор запира тука.

353
00:15:40,540 --> 00:15:45,270
>> Па, откако ќе си отиде со М-А-Х-З-Е-Л-L,
се чувствува како седум, можеби

354
00:15:45,270 --> 00:15:48,910
осум ако одиме еден покрај тоа, осум
чекори да се најде Максвел.

355
00:15:48,910 --> 00:15:53,050
Или ајде да го наречеме К Но потсетиме минатата
време, јас тврдеше дека ако има

356
00:15:53,050 --> 00:15:57,540
реално максимална должина на
збор, како 40-некои чудни карактери,

357
00:15:57,540 --> 00:16:00,810
Максималната должина подразбира
константна вредност.

358
00:16:00,810 --> 00:16:05,770
Значи, навистина, да, тоа е технички големо O
од 8 или 7, или навистина голема О на К Но,

359
00:16:05,770 --> 00:16:09,420
ако има конечен капа на она што
К би можело да биде, тоа е константа.

360
00:16:09,420 --> 00:16:12,080
И така тоа е голема О од 1 на
На крајот на денот.

361
00:16:12,080 --> 00:16:13,040
>> Не во реалниот свет.

362
00:16:13,040 --> 00:16:15,960
Не кога ќе всушност почнете гледајќи
Вашиот часовник што се трчање вашата програма.

363
00:16:15,960 --> 00:16:20,690
Тоа е апсолутно случува да биде малку
побавно отколку вистински постојана

364
00:16:20,690 --> 00:16:21,840
време со еден чекор.

365
00:16:21,840 --> 00:16:25,540
Тоа се случува да биде седум или осум чекори,
но сепак тоа е многу, многу подобро

366
00:16:25,540 --> 00:16:30,080
од алгоритам како големо O на n дека
зависи од големината на она што е во

367
00:16:30,080 --> 00:16:31,220
податочна структура.

368
00:16:31,220 --> 00:16:34,970
>> Забележите наопаку тука е што може да се вметне
еден милион повеќе имиња во оваа

369
00:16:34,970 --> 00:16:38,170
податочна структура, но колку повеќе чекори
е тоа ќе не однесе да се најде

370
00:16:38,170 --> 00:16:40,480
Максвел во тој случај?

371
00:16:40,480 --> 00:16:40,780
Нема.

372
00:16:40,780 --> 00:16:41,820
Тој е непроменета.

373
00:16:41,820 --> 00:16:45,480
И до денес, јас не мислам дека ние сме виделе
пример за податочна структура или

374
00:16:45,480 --> 00:16:48,560
алгоритам кој беше целосно
под влијание на надворешни

375
00:16:48,560 --> 00:16:50,040
однесувања како што.

376
00:16:50,040 --> 00:16:51,160
Но, ова не може да биде неверојатна.

377
00:16:51,160 --> 00:16:52,900
Ова не може да биде единствено решение
за п-сет

378
00:16:52,900 --> 00:16:53,570
>> И тоа не е.

379
00:16:53,570 --> 00:16:55,980
Ова не е нужно на податоци
структура треба да гравитираат кон,

380
00:16:55,980 --> 00:16:58,220
бидејќи како хеш табели, Губитокот.

381
00:16:58,220 --> 00:17:00,500
Она што е цената што ја плаќате тука?

382
00:17:00,500 --> 00:17:00,940
Меморија.

383
00:17:00,940 --> 00:17:02,890
Мислам, ова е крволочен
количина на меморија.

384
00:17:02,890 --> 00:17:05,569
А вие не сосема да го видите тука, бидејќи
авторот на оваа слика

385
00:17:05,569 --> 00:17:09,420
очигледно скратена сите низи,
и ние не гледате многу А и

386
00:17:09,420 --> 00:17:12,700
Б и Ц и П, а на Y
и Z во овие низи.

387
00:17:12,700 --> 00:17:13,630
Но тие се таму.

388
00:17:13,630 --> 00:17:17,660
>> Секој од овие јазли е цела низа
на некои 26 или повеќе бајти, секоја од

389
00:17:17,660 --> 00:17:19,170
што претставува едно писмо.

390
00:17:19,170 --> 00:17:22,920
27 во нашиот случај, така што ние може да ги поддржи
апострофи во проблемот сет.

391
00:17:22,920 --> 00:17:27,030
Па оваа податочна структура е навистина,
навистина густа и широка.

392
00:17:27,030 --> 00:17:30,880
И дека сам може да заврши забавува
нешта долу, или барем ве чини

393
00:17:30,880 --> 00:17:32,240
многу повеќе простор.

394
00:17:32,240 --> 00:17:34,020
Но, повторно, можеме да извлечеме
споредби тука.

395
00:17:34,020 --> 00:17:39,190
>> Потсетиме некое време наназад, ние остваривме многу
повеќе возбудлив трчање време во сортирање

396
00:17:39,190 --> 00:17:42,880
кога ние ги користиме спојат вид, но цената
ја плативме за да се постигне n најавите n за спојување

397
00:17:42,880 --> 00:17:46,930
вид потребно, ние трошиме
повеќе она ресурс?

398
00:17:46,930 --> 00:17:47,690
Повеќе простор.

399
00:17:47,690 --> 00:17:50,530
Ни е потребно средно низа да се
копирате луѓе во, исто како и

400
00:17:50,530 --> 00:17:51,620
ние го сторивме тука на сцената.

401
00:17:51,620 --> 00:17:55,880
Значи, повторно, не постојат јасни победници,
но само субјективни дизајн

402
00:17:55,880 --> 00:17:57,710
одлуките да се носат.

403
00:17:57,710 --> 00:17:58,060
>> Сите во право.

404
00:17:58,060 --> 00:17:59,130
Па, како во врска со ова?

405
00:17:59,130 --> 00:18:02,050
Секој препознае кои Д-сала?

406
00:18:02,050 --> 00:18:02,440
OK.

407
00:18:02,440 --> 00:18:03,170
Па три од нас го прават.

408
00:18:03,170 --> 00:18:03,750
Mather куќа.

409
00:18:03,750 --> 00:18:05,070
Па ова е за јадење Mather е.

410
00:18:05,070 --> 00:18:09,650
Ќе залог сите јадење сали имаат
Купишта на коцки како оваа.

411
00:18:09,650 --> 00:18:11,950
И ова е всушност претставник
на нешто што сум

412
00:18:11,950 --> 00:18:13,050
очигледно се гледа веќе.

413
00:18:13,050 --> 00:18:14,850
Ние го нарече буквално оџак.

414
00:18:14,850 --> 00:18:18,970
И на магацинот, во однос на вашиот
меморија на компјутерот, е местото каде податоците оди

415
00:18:18,970 --> 00:18:20,460
додека функции се нарекува.

416
00:18:20,460 --> 00:18:23,410
>> За пример, она што видови на работите одат
на магацинот во однос на

417
00:18:23,410 --> 00:18:27,420
меморија распоред сме разговараа
во недели минатото?

418
00:18:27,420 --> 00:18:28,736
Што е тоа?

419
00:18:28,736 --> 00:18:29,670
>> ПУБЛИКАТА: Повиците на функции.

420
00:18:29,670 --> 00:18:30,260
>> Дејвид MALAN: Жал ми е.

421
00:18:30,260 --> 00:18:31,210
>> ПУБЛИКАТА: Повиците на функции.

422
00:18:31,210 --> 00:18:33,590
>> Дејвид MALAN: Повиците на функции, но
Поточно, она што е внатре на секоја од

423
00:18:33,590 --> 00:18:35,340
тие рамки?

424
00:18:35,340 --> 00:18:37,220
Какви видови на нештата?

425
00:18:37,220 --> 00:18:37,460
Да.

426
00:18:37,460 --> 00:18:38,500
Па локални променливи.

427
00:18:38,500 --> 00:18:43,080
Во секое време ни е потребно некои локални складирање,
како аргумент, или int i, или int

428
00:18:43,080 --> 00:18:45,940
Temp, или што и локалната
променлива, ние сме

429
00:18:45,940 --> 00:18:47,210
ставање дека на магацинот.

430
00:18:47,210 --> 00:18:49,610
И ние ја нарекуваме оџак, бидејќи
на таа дели идеја.

431
00:18:49,610 --> 00:18:52,940
Само вид на натпревари со реалноста,
концептот него.

432
00:18:52,940 --> 00:18:56,650
>> Но излегува дека оџакот може исто така да
да се гледа како на податоци структура,

433
00:18:56,650 --> 00:19:00,110
алтернатива низа, алтернатива
на поврзана листа.

434
00:19:00,110 --> 00:19:02,770
Нешто концептуално поинтересна
што се 'уште може да биде

435
00:19:02,770 --> 00:19:06,030
спроведува со користење или на оние
работите, но тоа е друг тип на

436
00:19:06,030 --> 00:19:09,140
податочна структура поддршка, навистина,
само две операции.

437
00:19:09,140 --> 00:19:11,000
Но можете да додадете на познавач
функции од овие.

438
00:19:11,000 --> 00:19:12,180
Но, овие се основите -

439
00:19:12,180 --> 00:19:13,510
им помогнам и поп музиката.

440
00:19:13,510 --> 00:19:19,240
>> А идејата со магацинот е дека ако јас
имаме овде, со или без Annenberg

441
00:19:19,240 --> 00:19:22,880
знаејќи, послужавник од следната врата
со бројот 9 на неа.

442
00:19:22,880 --> 00:19:23,870
Па само Инт.

443
00:19:23,870 --> 00:19:26,990
И сакам да им помогнам на оваа излез на податоци
структура, која во моментов е празна.

444
00:19:26,990 --> 00:19:28,790
Сметаат дека ова дното на магацинот.

445
00:19:28,790 --> 00:19:33,150
Јас ќе им помогнам овој број 9 врз
магацинот, а сега тоа е право таму.

446
00:19:33,150 --> 00:19:36,040
>> Но интересна работа во врска оџак
е дека ако јас сега сакаат да им помогнам на

447
00:19:36,040 --> 00:19:40,210
некои други вредност, како 17, и јас им помогнам на
ова врз оџакот, јас ќе одам да направите

448
00:19:40,210 --> 00:19:43,290
само интуитивно работа, јас сум само ќе
да го стави десно каде што ние, луѓето

449
00:19:43,290 --> 00:19:45,180
ќе бидат склони да го стави, на врвот.

450
00:19:45,180 --> 00:19:48,850
Но она што е интересно сега
е, како можам да добијам на 9?

451
00:19:48,850 --> 00:19:50,670
Знаете, јас не направи без некои напори.

452
00:19:50,670 --> 00:19:54,070
>> Значи она што е интересно за
магацинот е дека од страна на дизајнот,

453
00:19:54,070 --> 00:19:56,330
тоа е податоци LIFO структура.

454
00:19:56,330 --> 00:19:59,680
Глупо начин на опишување на
последен во, прво од.

455
00:19:59,680 --> 00:20:03,280
Па во последните број во
во тоа време беше 17.

456
00:20:03,280 --> 00:20:07,540
Значи, ако јас сакам да pop нешто надвор
на магацинот, тоа може да биде само 17.

457
00:20:07,540 --> 00:20:11,890
Па постои задолжително цел на
операции тука, каде што последната ставка

458
00:20:11,890 --> 00:20:14,260
во мора да биде првиот надвор.

459
00:20:14,260 --> 00:20:16,440
Оттука акроним, LIFO.

460
00:20:16,440 --> 00:20:19,160
>> Па зошто ова може да биде корисно?

461
00:20:19,160 --> 00:20:22,690
Дали нивните контексти во кои вие би
сакате податочна структура, како тоа?

462
00:20:22,690 --> 00:20:24,810
Па, тоа е сигурно е корисно
внатрешноста на компјутерот.

463
00:20:24,810 --> 00:20:29,050
Па оперативни системи јасно го користите овој
вид на структура на податоци за Купишта.

464
00:20:29,050 --> 00:20:32,800
Ние, исто така, ќе се види на истата идеја
кога станува збор за веб страници.

465
00:20:32,800 --> 00:20:35,890
Така оваа недела и следната недела и пошироко,
и како што ќе почнете спроведување на веб-

466
00:20:35,890 --> 00:20:39,490
страници на јазик наречен HTML, можете да
всушност употреба на податоци структура како

467
00:20:39,490 --> 00:20:42,690
ова за да се утврди дали страница
е правилно форматиран.

468
00:20:42,690 --> 00:20:47,170
Затоа што ние ќе видиме сите веб страници следат
еден вид на хиерархија, кратер

469
00:20:47,170 --> 00:20:52,030
кои, на крајот на денот, да биде
дрво структура под хауба.

470
00:20:52,030 --> 00:20:53,620
Толку повеќе за тоа во само малку.

471
00:20:53,620 --> 00:20:56,560
>> Но, за сега, ајде да предложи за
моментот, како би можеле да се обратите за

472
00:20:56,560 --> 00:20:58,830
претставуваат она што магацинот е?

473
00:20:58,830 --> 00:21:03,370
Дозволете ми да предложи дека ние се имплементираат
магацинот со кодот вака.

474
00:21:03,370 --> 00:21:07,990
Па магацинот се случува да имаат во него
две работи, низа, наречен пепелниците,

475
00:21:07,990 --> 00:21:09,510
само за да бидат во согласност со демо.

476
00:21:09,510 --> 00:21:12,660
И секоја од точките во таа низа
се случува да биде тип int.

477
00:21:12,660 --> 00:21:14,740
И капацитет е веројатно она што?

478
00:21:14,740 --> 00:21:18,796
Бидејќи јас не сум напишал на
целосна дефиниција тука.

479
00:21:18,796 --> 00:21:21,535
>> Тоа е веројатно максимум
големината на низата.

480
00:21:21,535 --> 00:21:25,150
И тоа е веројатно декларирани како остар
дефинирање на врвот на датотеката, некои

481
00:21:25,150 --> 00:21:28,450
вид на постојана како имплицирани од
самиот капитализација.

482
00:21:28,450 --> 00:21:32,250
Па некаде капацитет се дефинира
како максимална можна големина.

483
00:21:32,250 --> 00:21:35,590
Во меѓувреме, во внатрешноста на податочната структура
познат како оџак ќе има

484
00:21:35,590 --> 00:21:38,630
да биде цел број само познат
едноставно како големина.

485
00:21:38,630 --> 00:21:43,400
>> Значи, ако јас требаше да ја претставува оваа сега
сликовито, да претпоставиме дека оваа

486
00:21:43,400 --> 00:21:48,070
Целиот црна кутија претставува мојот оџак.

487
00:21:48,070 --> 00:21:50,070
Во него е две променливи.

488
00:21:50,070 --> 00:21:54,780
Па ќе одам да се подготви на
првиот како големина.

489
00:21:54,780 --> 00:21:57,420
А вториот Одам
да се подготви како низа.

490
00:21:57,420 --> 00:22:01,060
>> Но само да го задржи нешта уредно,
нормално јас ќе привлече низа како

491
00:22:01,060 --> 00:22:04,910
ова, но тоа е вид на убаво
ако ние одговараат на реалноста, или

492
00:22:04,910 --> 00:22:06,230
одговара на ментална модел.

493
00:22:06,230 --> 00:22:12,880
Па да ми наместо исцртување на низа
вертикално, што е само, повторно,

494
00:22:12,880 --> 00:22:13,840
уметникот препевот.

495
00:22:13,840 --> 00:22:16,610
Не е важно она што го
е под хауба.

496
00:22:16,610 --> 00:22:20,350
А ние ќе се каже дека, по дифолт,
капацитет ќе биде три.

497
00:22:20,350 --> 00:22:23,480
Па ова ќе биде локација 0, овој
ќе биде локација 1, овој

498
00:22:23,480 --> 00:22:25,740
ќе биде локација 2.

499
00:22:25,740 --> 00:22:29,330
>> Ако јас ги поткупат со стрес топчето, би
Некој како да се излезе и да ја стартувате

500
00:22:29,330 --> 00:22:30,870
качи тука за само еден миг?

501
00:22:30,870 --> 00:22:31,960
Добро, видов вашата рака во прв план.

502
00:22:31,960 --> 00:22:33,950
Ајде горе.

503
00:22:33,950 --> 00:22:36,500
Сите во право.

504
00:22:36,500 --> 00:22:38,760
Па јас верувам дека тоа е Стивен.

505
00:22:38,760 --> 00:22:40,035
Ајде горе.

506
00:22:40,035 --> 00:22:40,770
Сите во право.

507
00:22:40,770 --> 00:22:46,760
>> Но, да претпоставиме сега ние ја премотам касетата на почетна
состојбата на светот каде што

508
00:22:46,760 --> 00:22:52,180
имате само прогласи магацинот, а тоа е
ќе биде на капацитетот три.

509
00:22:52,180 --> 00:22:54,470
Но, големината се уште не е утврден.

510
00:22:54,470 --> 00:22:56,100
Пепелниците се уште не е утврден.

511
00:22:56,100 --> 00:22:57,300
Па неколку прашања во прв план.

512
00:22:57,300 --> 00:23:01,310
И дозволете ми да ви даде микрофон за да можете да
причестуваат поактивно во ова.

513
00:23:01,310 --> 00:23:05,190
>> Значи она што е внатре големина во овој момент
во времето кога сите што го сторив е

514
00:23:05,190 --> 00:23:09,340
прогласи магацинот со
една линија код?

515
00:23:09,340 --> 00:23:10,100
>> Стивен: Не многу.

516
00:23:10,100 --> 00:23:12,080
>> Дејвид MALAN: Добро, не многу.

517
00:23:12,080 --> 00:23:14,410
Знаеме што е внатре на големината,
знаеме што е внатре

518
00:23:14,410 --> 00:23:16,330
на оваа низа тука?

519
00:23:16,330 --> 00:23:18,630
>> Стивен: Само случаен кодот, нели?

520
00:23:18,630 --> 00:23:20,220
Само -

521
00:23:20,220 --> 00:23:23,230
>> Дејвид MALAN: Да, јас ќе одам да
го нарекуваат код, но случајни -

522
00:23:23,230 --> 00:23:23,820
>> Стивен: Работи што треба.

523
00:23:23,820 --> 00:23:28,290
>> Дејвид MALAN: Работи како случаен

524
00:23:28,290 --> 00:23:28,870
>> Стивен: битови.

525
00:23:28,870 --> 00:23:29,530
>> Дејвид MALAN: битови, нели?

526
00:23:29,530 --> 00:23:31,190
Па ѓубре вредности, нели?

527
00:23:31,190 --> 00:23:33,470
Па пермутации на 0 и 1 е.

528
00:23:33,470 --> 00:23:35,920
Остатоци од претходната примени
на оваа меморија.

529
00:23:35,920 --> 00:23:38,150
И ние навистина не знаат што вредности
се, па ние обично ги привлече

530
00:23:38,150 --> 00:23:38,930
како прашалници.

531
00:23:38,930 --> 00:23:41,990
>> Така првото нешто ние сме веројатно
ќе сакате да го направите тука -

532
00:23:41,990 --> 00:23:46,630
и дозволете ми даде ова поле внатре
од таму името - пепелниците.

533
00:23:46,630 --> 00:23:49,540
Она што треба ние веројатно се иницијализира
Големината да ако сакаме да

534
00:23:49,540 --> 00:23:51,040
започнат со користење на оваа оџакот?

535
00:23:51,040 --> 00:23:53,070
>> Стивен: носачот е под 3.

536
00:23:53,070 --> 00:23:53,910
>> Дејвид MALAN: Значи, ОК.

537
00:23:53,910 --> 00:23:56,710
Да биде јасно, капацитет е прогласена
друго место како што три.

538
00:23:56,710 --> 00:23:58,570
И тоа е она што јас сум користел
за да се распредели низа.

539
00:23:58,570 --> 00:24:03,535
Големината се случува да се однесува на тоа колку
пепелниците се во моментов на магацинот.

540
00:24:03,535 --> 00:24:03,880
>> Стивен: Нулта.

541
00:24:03,880 --> 00:24:04,460
>> Дејвид MALAN: Така треба да биде нула.

542
00:24:04,460 --> 00:24:07,760
Така одат напред и со било кој прст,
подготви нула во големина.

543
00:24:07,760 --> 00:24:08,440
Сите во право.

544
00:24:08,440 --> 00:24:10,920
Па сега, она што е внатре на овој
тука, ние не знаеме.

545
00:24:10,920 --> 00:24:12,160
Овие се навистина само ѓубре вредности.

546
00:24:12,160 --> 00:24:14,800
Па ние би можеле да подготви прашалници, но
ајде да се задржи одбор чисти сега за сега

547
00:24:14,800 --> 00:24:16,300
затоа што тоа не е важно
она што е таму.

548
00:24:16,300 --> 00:24:19,130
Ние не треба да се иницијализира на низа
на ништо, бидејќи ако знаеме дека

549
00:24:19,130 --> 00:24:23,100
големината на оџакот е нула, добро, ние
не треба да се гледа во нешто во

550
00:24:23,100 --> 00:24:25,590
оваа низа сепак на
овој момент во времето.

551
00:24:25,590 --> 00:24:29,970
>> Па сега да претпоставиме дека сум им помогнам на
број 9 врз оџакот.

552
00:24:29,970 --> 00:24:33,750
Колку ние треба да се ажурира на податоци структура
во внатрешноста на оваа црна кутија?

553
00:24:33,750 --> 00:24:35,540
Кои вредности треба да се промени?

554
00:24:35,540 --> 00:24:36,200
>> Стивен: Во текот на -

555
00:24:36,200 --> 00:24:37,400
големината?

556
00:24:37,400 --> 00:24:37,650
>> Дејвид MALAN: OK.

557
00:24:37,650 --> 00:24:38,770
Големина треба да стане она?

558
00:24:38,770 --> 00:24:39,580
>> Стивен: Големина ќе биде една.

559
00:24:39,580 --> 00:24:39,870
>> Дејвид MALAN: OK.

560
00:24:39,870 --> 00:24:41,110
Па големината треба да стане еден.

561
00:24:41,110 --> 00:24:42,540
Па можете да го направите тоа во неколку начини.

562
00:24:42,540 --> 00:24:46,920
Дозволете ми да ви даде, сега вашиот
прст е гума за бришење.

563
00:24:46,920 --> 00:24:47,260
Сите во право.

564
00:24:47,260 --> 00:24:49,960
Тогаш сега вашиот прст е четка.

565
00:24:49,960 --> 00:24:50,330
Сите во право.

566
00:24:50,330 --> 00:24:52,820
И сега што друго има да се промени,
очигледно, во податочна структура?

567
00:24:52,820 --> 00:24:57,060
>> Стивен: Ние ќе од
дното до 9.

568
00:24:57,060 --> 00:24:57,760
>> Дејвид MALAN: 9.

569
00:24:57,760 --> 00:24:58,420
Добро, добро.

570
00:24:58,420 --> 00:25:01,550
Па се уште не е важно она што е во
локација една или две, бидејќи тие се

571
00:25:01,550 --> 00:25:04,520
ѓубре вредности, но ние не треба да пречи
бараат таму, бидејќи големината е

572
00:25:04,520 --> 00:25:07,540
да ни кажува дека само првиот елемент
е, всушност, легитимна.

573
00:25:07,540 --> 00:25:10,400
Па сега јас им помогнам 17 кон листата.

574
00:25:10,400 --> 00:25:11,830
Што се случува со оваа слика?

575
00:25:11,830 --> 00:25:14,720
>> Стивен: Значи големина се случува да одат на две.

576
00:25:14,720 --> 00:25:15,300
>> Дејвид MALAN: OK.

577
00:25:15,300 --> 00:25:16,070
Ти си Бришачот -

578
00:25:16,070 --> 00:25:16,810
Упс.

579
00:25:16,810 --> 00:25:18,026
Ти си гума за бришење.

580
00:25:18,026 --> 00:25:18,840
>> Стивен: Гума за бришење.

581
00:25:18,840 --> 00:25:19,720
>> Дејвид MALAN: Ти си четка.

582
00:25:19,720 --> 00:25:20,560
>> Стивен: Четка.

583
00:25:20,560 --> 00:25:20,920
>> Дејвид MALAN: OK.

584
00:25:20,920 --> 00:25:21,600
И што друго?

585
00:25:21,600 --> 00:25:22,600
>> Стивен: И тогаш -

586
00:25:22,600 --> 00:25:22,915
>> Дејвид MALAN: Ние се наметнува 17.

587
00:25:22,915 --> 00:25:24,760
>> Стивен: Ние се држиме 17 на врвот, па -

588
00:25:24,760 --> 00:25:25,710
>> Дејвид MALAN: Добро, добро.

589
00:25:25,710 --> 00:25:27,040
>> Стивен: - тоа паѓачкото.

590
00:25:27,040 --> 00:25:27,530
>> Дејвид MALAN: Во ред.

591
00:25:27,530 --> 00:25:27,940
Станува лесно.

592
00:25:27,940 --> 00:25:29,300
Јас не одам за да ви помогнат тоа време.

593
00:25:29,300 --> 00:25:30,510
Притисни 22.

594
00:25:30,510 --> 00:25:31,720
>> Стивен: Done.

595
00:25:31,720 --> 00:25:34,870
Станува гума за бришење.

596
00:25:34,870 --> 00:25:37,340
Јас сум да стане четка.

597
00:25:37,340 --> 00:25:39,340
И тогаш јас сум ставање 22.

598
00:25:39,340 --> 00:25:40,100
>> Дејвид MALAN: 22.

599
00:25:40,100 --> 00:25:40,620
Одличен.

600
00:25:40,620 --> 00:25:41,380
Значи уште еднаш.

601
00:25:41,380 --> 00:25:44,280
Јас сум сега ќе да им помогнам на
врз оџакот 26.

602
00:25:44,280 --> 00:25:46,350
>> Стивен: Ooh.

603
00:25:46,350 --> 00:25:50,278
Ох боже.

604
00:25:50,278 --> 00:25:52,520
Вие навистина ме фати исклучи стража.

605
00:25:52,520 --> 00:25:53,703
>> Дејвид MALAN: Вие не
види ова доаѓа?

606
00:25:53,703 --> 00:25:55,930
>> Стивен: Јас не го гледаат ова што доаѓаат.

607
00:25:55,930 --> 00:25:58,756
Да можеме повторно почетен капацитет?

608
00:25:58,756 --> 00:25:59,790
>> Дејвид MALAN: Тоа е добро прашање.

609
00:25:59,790 --> 00:26:02,360
Па ние сме вид на се насликани
во некој ќош тука.

610
00:26:02,360 --> 00:26:06,740
Тука навистина не е добро надвор за Стивен
затоа што ние сме распределени оваа низа

611
00:26:06,740 --> 00:26:09,130
статички, така да се каже, во внатрешноста
на податочна структура.

612
00:26:09,130 --> 00:26:12,170
И ние во суштина хард кодирани
таа да биде со големина од три.

613
00:26:12,170 --> 00:26:14,170
Па ние навистина не може да го пренамени.

614
00:26:14,170 --> 00:26:20,020
>> Ние би можеле да ако се вративме во, ние
редефинира коцки да биде показател дека

615
00:26:20,020 --> 00:26:22,300
ние потоа користете Примерок на рака меморија за да се.

616
00:26:22,300 --> 00:26:25,050
Затоа што ако добивме меморија од
грамада преку Примерок, ние

617
00:26:25,050 --> 00:26:26,430
тогаш би можеле да го ослободи.

618
00:26:26,430 --> 00:26:29,630
Но, пред ослободувањето на тоа, ние би можеле
пренамени поголем парче на меморија,

619
00:26:29,630 --> 00:26:31,330
ажурирање на покажувач, и така натаму.

620
00:26:31,330 --> 00:26:33,500
Но, за сега, ова е навистина
најдоброто што може да се направи.

621
00:26:33,500 --> 00:26:36,360
Им помогнам и поп се претпоставува дека ќе
мора да сигнализираат некои грешка.

622
00:26:36,360 --> 00:26:40,270
>> Така на пример, нашата институција
на притисни може да се врати на bool кои

623
00:26:40,270 --> 00:26:42,390
претходно се врати вистина, вистина, вистина.

624
00:26:42,390 --> 00:26:48,390
Но по четврти пат, тоа се случува да имаат
за да се вратите лажна, на пример.

625
00:26:48,390 --> 00:26:48,540
Сите во право.

626
00:26:48,540 --> 00:26:49,540
Многу добро направено.

627
00:26:49,540 --> 00:26:50,060
Алал да му е.

628
00:26:50,060 --> 00:26:52,160
Сте заработени вашиот стрес топчето денес.

629
00:26:52,160 --> 00:26:53,110
>> [Аплауз]

630
00:26:53,110 --> 00:26:54,382
>> Стивен: Ви благодариме.

631
00:26:54,382 --> 00:26:55,680
>> Дејвид MALAN: Ви благодариме.

632
00:26:55,680 --> 00:26:59,740
Добро, па се чини дека ова не е многу
на еден чекор напред, нели?

633
00:26:59,740 --> 00:27:01,410
Што е опишано оваа податочна структура.

634
00:27:01,410 --> 00:27:02,320
Тоа е огромна, нели?

635
00:27:02,320 --> 00:27:03,200
Оперативни системи се допаѓа.

636
00:27:03,200 --> 00:27:06,360
Очигледно на интернет може да се направи употреба на ова,
и други апликации се уште.

637
00:27:06,360 --> 00:27:10,870
Но она што е глупаво ограничување дека ние сме
се врати да се вид на недела две граници

638
00:27:10,870 --> 00:27:12,880
каде што имаме фиксна големина на низи.

639
00:27:12,880 --> 00:27:15,010
>> Па така постојат навистина неколку
начините на кои може да го реши ова.

640
00:27:15,010 --> 00:27:18,750
Ние динамички може да ги распредели низа,
не со тешко кодирање како што сум

641
00:27:18,750 --> 00:27:22,600
направено овде, но наместо повторно прогласување
ова, само за да бидат јасни, како

642
00:27:22,600 --> 00:27:23,830
нешто како ова.

643
00:27:23,830 --> 00:27:29,040
Int * пепелниците не, одлучувајќи
на капацитет уште.

644
00:27:29,040 --> 00:27:35,460
Но, кога ќе го прогласи магацинот на друго место
во мојот код, јас тогаш може да се нарече Примерок,

645
00:27:35,460 --> 00:27:38,250
ја добиете адресата на парче
меморија, и можев да доделите

646
00:27:38,250 --> 00:27:39,980
таа адреса да пепелниците.

647
00:27:39,980 --> 00:27:43,340
>> А потоа, бидејќи тоа е само еден дел од
меморија, би можел да продолжи да го користи плоштад

648
00:27:43,340 --> 00:27:45,450
заградата нотација на вообичаениот начин.

649
00:27:45,450 --> 00:27:49,020
Затоа што еднаш, таму е еден вид на овој
функционален еквивалент на низи и

650
00:27:49,020 --> 00:27:50,820
делови од меморијата кои доаѓаат
се врати од Примерок.

651
00:27:50,820 --> 00:27:53,090
Ние можеме да се третираат како и другите
користење на покажувачот аритметички или

652
00:27:53,090 --> 00:27:54,440
квадратни загради нотација.

653
00:27:54,440 --> 00:27:55,660
Значи тоа е еден пристап.

654
00:27:55,660 --> 00:28:00,120
>> Но како поинаку би можеле да ја имплементираат оваа
истата податочна структура, потенцијално?

655
00:28:00,120 --> 00:28:00,280
Нели?

656
00:28:00,280 --> 00:28:04,530
Се чувствувам како ние едноставно се реши овој
проблем како пред една недела.

657
00:28:04,530 --> 00:28:08,860
Она што беше на решение за овој проблем
дека Стивен налетав?

658
00:28:08,860 --> 00:28:10,370
Така поврзани листи, нели.

659
00:28:10,370 --> 00:28:13,410
>> Ако проблемот е во тоа што ние сме сликарство
се во ќошот со распределба

660
00:28:13,410 --> 00:28:17,580
однапред премалку меморија дека ние
потоа ја некако да се справи со, добро,

661
00:28:17,580 --> 00:28:19,880
зошто да не само се избегне тоа
издаде заедно?

662
00:28:19,880 --> 00:28:26,170
Зошто да не само прогласи коцки да биде
покажувачот на еден јазол, ergo е поврзана листа,

663
00:28:26,170 --> 00:28:30,740
и потоа едноставно алоцирање на нови јазли
секој пат Стивен потребни за да се вклопи со

664
00:28:30,740 --> 00:28:32,400
број во податочна структура.

665
00:28:32,400 --> 00:28:34,200
>> Па сликата ќе треба да се промени.

666
00:28:34,200 --> 00:28:38,220
Тоа нема да биде толку чист и како
едноставно како што само низа од три ints.

667
00:28:38,220 --> 00:28:42,970
Сега тоа се случува да биде покажувач кон
struct, и дека struct се случува да се

668
00:28:42,970 --> 00:28:44,830
имаат int и следната покажувач.

669
00:28:44,830 --> 00:28:47,670
Тоа се случува да доведат преку кој покажувачот
на друг како struct да

670
00:28:47,670 --> 00:28:48,600
друга таква struct.

671
00:28:48,600 --> 00:28:50,560
Па сликата ќе всушност
се добие малку Messier.

672
00:28:50,560 --> 00:28:52,950
И ние би го стрели врзување
сето заедно.

673
00:28:52,950 --> 00:28:55,280
>> Но тоа е во ред, нели, затоа што
видовме како да го направите тоа.

674
00:28:55,280 --> 00:28:58,180
И штом еднаш ќе се чувствуваме удобно
спроведување на нешто како поврзани

675
00:28:58,180 --> 00:29:01,450
листа, која ќе треба да направите ако
изберете да се спроведе хаш табелата со

676
00:29:01,450 --> 00:29:05,120
посебна врзувањето за P-сет 6, можете да
користат како градење на блок, или

677
00:29:05,120 --> 00:29:08,870
состојка, или во Скреч имено,
постапка, нешто што ќе се стави, можете

678
00:29:08,870 --> 00:29:12,560
креирано свој загатка парче
што потоа може да повторна употреба.

679
00:29:12,560 --> 00:29:17,090
Па размени, но потенцијални решенија
дека ние сме всушност видел.

680
00:29:17,090 --> 00:29:20,560
>> Па доста често, ќе видите ова секој
година или две кога Епл изданија

681
00:29:20,560 --> 00:29:23,060
нешто ново, и сите луди луѓе
линија надвор од Епл

682
00:29:23,060 --> 00:29:27,050
продавница за да купи нивниот маргинален
надградба на хардверот.

683
00:29:27,050 --> 00:29:30,420
Ова го велам, тоа е во ред, затоа што
Јас сум еден од оние луѓе.

684
00:29:30,420 --> 00:29:35,140
Значи каков вид на податоци структура
може да ја претставува оваа реалност?

685
00:29:35,140 --> 00:29:36,980
>> Добро, ајде да го наречеме дното, на линија.

686
00:29:36,980 --> 00:29:40,270
Па Британците би го нарекол тоа обично
редот и онака, па тоа е убаво име.

687
00:29:40,270 --> 00:29:44,960
И двете операции кои редица
ќе ги поддржи ние ќе го нарекуваат Стави во ред

688
00:29:44,960 --> 00:29:48,900
операција и dequeue операција,
кои се слични во

689
00:29:48,900 --> 00:29:50,120
дух да им помогнам и поп музиката.

690
00:29:50,120 --> 00:29:54,060
Тоа е само вид на различен во
конвенција, она што ние сме повикување на овие.

691
00:29:54,060 --> 00:29:57,680
Но да Стави во ред нешто значи да додадете
или вметнете ја до податоците структура.

692
00:29:57,680 --> 00:29:59,570
Да dequeue значи да го отстраните.

693
00:29:59,570 --> 00:30:05,170
Но со оглед на тоа оџакот беше на податоци LIFO
структура, задачата е прв во,

694
00:30:05,170 --> 00:30:06,740
Првиот надвор податочна структура.

695
00:30:06,740 --> 00:30:10,050
>> Ако сте првата личност во линија,
ќе биде првата личност да се добие

696
00:30:10,050 --> 00:30:12,420
надвор од линијата и да купам вашиот нов уред.

697
00:30:12,420 --> 00:30:18,070
Замислете колку вознемирени овие луѓе ќе биде
ако Apple наместо да се користи оџак, за

698
00:30:18,070 --> 00:30:21,250
пример, за спроведување на Бране
up на својата нова играчка.

699
00:30:21,250 --> 00:30:24,310
Па редици се направи смисла, секако, и
можеме да размислуваме за сите видови на

700
00:30:24,310 --> 00:30:27,480
апликации, веројатно, за редици,
особено кога сакате праведност.

701
00:30:27,480 --> 00:30:30,040
Па како да ги имплементираат овие
како податочна структура?

702
00:30:30,040 --> 00:30:33,680
>> Па, јас предложи дека ние би можеле да
треба да го направи тоа на овој начин.

703
00:30:33,680 --> 00:30:35,225
Па јас ќе одам да сега имаат броеви.

704
00:30:35,225 --> 00:30:38,190
Па ние ќе ја задржиш едноставен и не
мора да зборуваме во однос на коцки.

705
00:30:38,190 --> 00:30:40,220
Само броеви кои луѓето од добивано.

706
00:30:40,220 --> 00:30:43,760
Капацитет ќе се, повторно, да утврдат на
вкупниот број на луѓе кои можат да бидат во

707
00:30:43,760 --> 00:30:46,900
оваа линија, како три или
без оглед на друга вредност.

708
00:30:46,900 --> 00:30:50,760
>> Но јас предложи дека јас треба да ги пратите
не само на големината на

709
00:30:50,760 --> 00:30:52,370
на дното, колку многу нешта се во неа.

710
00:30:52,370 --> 00:30:56,310
Значи големина е сегашната големина, капацитет
е максималната големина.

711
00:30:56,310 --> 00:30:58,540
Само еднаш, номенклатура
со конвенција.

712
00:30:58,540 --> 00:31:03,680
Зошто ми е потребен дополнителен int внатре
на дното да ги пратите на кој е во

713
00:31:03,680 --> 00:31:05,365
предниот дел на линија?

714
00:31:05,365 --> 00:31:07,930

715
00:31:07,930 --> 00:31:10,910
Зошто воопшто морам да го сторат тоа во овој случај?

716
00:31:10,910 --> 00:31:14,750

717
00:31:14,750 --> 00:31:16,190
>> Па, како е ова слика
ќе се промени?

718
00:31:16,190 --> 00:31:19,280
Јас веројатно може да повторна употреба повеќето
од оваа слика.

719
00:31:19,280 --> 00:31:21,480
Дозволете ми да оди напред и да ги избрише она што е овде.

720
00:31:21,480 --> 00:31:24,580
Ние ќе им даде на овој малку
друго име тука горе.

721
00:31:24,580 --> 00:31:28,930
Ајде да се ослободи од 17, да се ослободи
на 9, ајде да се ослободи од 3.

722
00:31:28,930 --> 00:31:30,410
И ајде да додадете една друга работа.

723
00:31:30,410 --> 00:31:34,710
Јас предложи дека јас треба да ги пратите на
на предниот дел на листата, која е само

724
00:31:34,710 --> 00:31:35,570
нема да биде int, како и.

725
00:31:35,570 --> 00:31:36,550
И ние ќе го чувам едноставна.

726
00:31:36,550 --> 00:31:37,740
Не поврзана листа за сега.

727
00:31:37,740 --> 00:31:40,900
>> Ние ќе признаам дека ние ќе
судрат против оваа граница.

728
00:31:40,900 --> 00:31:43,720
Но, она што сакам да го видам
се случи овој пат?

729
00:31:43,720 --> 00:31:47,240
Па претпоставувам дека одиме напред и првиот
лице доаѓа во линија, и

730
00:31:47,240 --> 00:31:48,560
тоа е број 9.

731
00:31:48,560 --> 00:31:49,680
Ние немаме стрес топки.

732
00:31:49,680 --> 00:31:51,330
Јас може да украде, да речеме, две или три лица?

733
00:31:51,330 --> 00:31:52,690
Еден, два, три?

734
00:31:52,690 --> 00:31:53,120
Ајде горе.

735
00:31:53,120 --> 00:31:56,022
Право од фронтот, бидејќи
ние ќе направи ова е еден брз.

736
00:31:56,022 --> 00:31:59,415
>> Секој од вас сега ќе биде
Навивач момче во линија на Apple.

737
00:31:59,415 --> 00:32:03,970

738
00:32:03,970 --> 00:32:06,210
Вие нема да се примаат Apple хардвер
на крајот од ова, секако.

739
00:32:06,210 --> 00:32:06,500
Сите во право.

740
00:32:06,500 --> 00:32:09,430
Па ти си број 9, ти си
број 17, број 22.

741
00:32:09,430 --> 00:32:12,130
Овие се произволни броеви, како
студент ИД или какво ли не.

742
00:32:12,130 --> 00:32:14,550
И во само еден момент, ајде да започне
за да започне додавајќи нешта.

743
00:32:14,550 --> 00:32:16,000
И јас ќе се кандидира на одборот тука тоа време.

744
00:32:16,000 --> 00:32:19,570
>> Значи во овој случај, јас сум иницијализира
пред да биде -

745
00:32:19,570 --> 00:32:22,380
Јас всушност навистина не се грижат што
Предниот дел е, бидејќи големината е нула.

746
00:32:22,380 --> 00:32:24,480
Па ова би можело, како и само
биде знак прашалник.

747
00:32:24,480 --> 00:32:26,170
Овие се сите прашалници.

748
00:32:26,170 --> 00:32:29,880
Па сега ние ќе почнат да всушност гледаат некои
луѓе обидел во продавницата.

749
00:32:29,880 --> 00:32:33,320
>> Значи, ако бројот 9, ти си првиот
таму во 5:00, оди напред и да се редат,

750
00:32:33,320 --> 00:32:34,210
или ноќта пред тоа.

751
00:32:34,210 --> 00:32:34,580
OK.

752
00:32:34,580 --> 00:32:35,940
Па сега 9 е тука.

753
00:32:35,940 --> 00:32:37,940
Значи 9 е во предниот дел на листата.

754
00:32:37,940 --> 00:32:41,440
Па јас ќе одам да се оди напред и да се ажурира
големината на овој тековните податоци

755
00:32:41,440 --> 00:32:44,740
структура не да биде 0 повеќе,
но за да биде 1.

756
00:32:44,740 --> 00:32:47,630
Одам да се стави 9 на
пред листа.

757
00:32:47,630 --> 00:32:51,020
Дозволете ми да оди напред и да ја префрлате на екранот
па може да се види минатото нас овде.

758
00:32:51,020 --> 00:32:53,220
>> И сега што сакам
да се стави на предната?

759
00:32:53,220 --> 00:32:56,240
Одам да ги пратите дека
редот на чекање во моментов

760
00:32:56,240 --> 00:32:58,570
е на локација 0.

761
00:32:58,570 --> 00:33:00,510
Затоа што она што следната ќе се случи?

762
00:33:00,510 --> 00:33:03,000
Па, претпоставувам сега јас Стави во ред
17, како и.

763
00:33:03,000 --> 00:33:04,510
Значи хоп во линија таму.

764
00:33:04,510 --> 00:33:07,060
И повторно, вид на вратата на
продавница ќе биде тука.

765
00:33:07,060 --> 00:33:08,700
Па сега јас додадов 17.

766
00:33:08,700 --> 00:33:10,810
И иако овие момци се блокира
на екранот, тоа е во ред,

767
00:33:10,810 --> 00:33:12,300
затоа што ние може да се види тука.

768
00:33:12,300 --> 00:33:12,910
Жал.

769
00:33:12,910 --> 00:33:13,810
>> ПУБЛИКАТА: Ние може да се движи -

770
00:33:13,810 --> 00:33:14,660
>> Дејвид MALAN: Не, тоа е во ред.

771
00:33:14,660 --> 00:33:16,000
Тоа е огромна таму горе.

772
00:33:16,000 --> 00:33:18,580
Па 17 е сега во внатрешноста на задачата.

773
00:33:18,580 --> 00:33:21,332
Јас треба да се ажурира кои
полиња сега иако?

774
00:33:21,332 --> 00:33:23,210
Добро, дефинитивно големина.

775
00:33:23,210 --> 00:33:26,430
И како за пред?

776
00:33:26,430 --> 00:33:27,040
Добро, нема.

777
00:33:27,040 --> 00:33:30,200
Напред, не треба да се менува, затоа што
за разлика од оџакот, ние

778
00:33:30,200 --> 00:33:31,370
сакаат да го задржат праведност.

779
00:33:31,370 --> 00:33:35,150
Па ако 9 дојде во првата, сакаме 9
да биде првиот надвор од линија

780
00:33:35,150 --> 00:33:36,420
и во продавница.

781
00:33:36,420 --> 00:33:37,220
>> Всушност, ајде да видиме тоа.

782
00:33:37,220 --> 00:33:42,235
Пред да ја вметнете 22, ајде да
повелете и dequeue 9.

783
00:33:42,235 --> 00:33:42,970
Како се викаш повторно?

784
00:33:42,970 --> 00:33:43,680
>> ПУБЛИКАТА: Џејк.

785
00:33:43,680 --> 00:33:45,440
>> Дејвид MALAN: Џејк се случува
да се dequeued сега.

786
00:33:45,440 --> 00:33:48,050
Па ќе го добиете да одиме во продавница.

787
00:33:48,050 --> 00:33:49,880
И да се преправам дека во продавницата
е таму.

788
00:33:49,880 --> 00:33:51,970
Па сега она што треба - dit-dit-dit!

789
00:33:51,970 --> 00:33:53,400
Што треба да се случи сега?

790
00:33:53,400 --> 00:33:54,490
Дизајн одлука.

791
00:33:54,490 --> 00:33:56,825
Па не е лоша инстинкт, но -
Како се викаш повторно?

792
00:33:56,825 --> 00:33:57,090
>> ПУБЛИКАТА: Дејвид.

793
00:33:57,090 --> 00:33:57,500
>> Дејвид MALAN: Дејвид.

794
00:33:57,500 --> 00:33:58,810
Значи она што не Дејвид направам?

795
00:33:58,810 --> 00:34:02,590
Тој се обидува да најде решение за поправат податоци
структура и се движат од неговата локација

796
00:34:02,590 --> 00:34:04,100
во поранешната локација на Jake.

797
00:34:04,100 --> 00:34:06,740
И тоа е во ред, ако ние сме подготвени
да прифатат дека како

798
00:34:06,740 --> 00:34:08,199
имплементација детали.

799
00:34:08,199 --> 00:34:11,100
Но, прво, ајде да ажурирање на податоците
структура, пред да го направите тоа.

800
00:34:11,100 --> 00:34:14,139
Бидејќи јас не сум вкусот на идеја на сите
на луѓето менувањето во оваа линија.

801
00:34:14,139 --> 00:34:17,360
>> Тоа не е голема работа ако Дејвид тоа го прави со
еден чекор, но повторно, се сетам на

802
00:34:17,360 --> 00:34:20,360
кога имавме осум волонтери на
фаза и ние го направивме како вметнување

803
00:34:20,360 --> 00:34:22,600
вид, каде што моравме да почне
се движат сите околу.

804
00:34:22,600 --> 00:34:23,790
Кој доби скап, нели?

805
00:34:23,790 --> 00:34:28,330
Што ме прави раболепнича за големи О
на n, големо O на n квадрат повторно.

806
00:34:28,330 --> 00:34:30,650
Тоа не се чувствува како
идеална исход.

807
00:34:30,650 --> 00:34:32,080
>> Па да ја ажурирате оваа.

808
00:34:32,080 --> 00:34:35,120
Па од големината на редот
не е повеќе 2.

809
00:34:35,120 --> 00:34:37,090
Тоа е сега едноставно 1.

810
00:34:37,090 --> 00:34:40,360
Но јас сега може да се ажурира нешто
Јас не ажурирање порано,

811
00:34:40,360 --> 00:34:41,130
пред листа.

812
00:34:41,130 --> 00:34:45,420
Јас само може да се каже, е таа локација 1?

813
00:34:45,420 --> 00:34:49,770
Така, сега имаме ѓубре вредност тука,
ѓубре вредност тука, и Дејвид во

814
00:34:49,770 --> 00:34:51,469
средината на оваа ѓубре.

815
00:34:51,469 --> 00:34:54,980
Но податоците структура
е сеуште недопрена.

816
00:34:54,980 --> 00:34:58,540
>> И во Всушност, јас дури и не треба да се
промена поранешниот број на Jake

817
00:34:58,540 --> 00:35:00,460
9, затоа што оној кој се грижи.

818
00:35:00,460 --> 00:35:04,470
Имам доволно информации сега во
големина што знам има едно лице во

819
00:35:04,470 --> 00:35:05,030
оваа задача.

820
00:35:05,030 --> 00:35:08,340
И знам дека тоа лице
е во локација 1 не, 0.

821
00:35:08,340 --> 00:35:09,760
Јас не сум броење.

822
00:35:09,760 --> 00:35:11,300
Па 1, како и.

823
00:35:11,300 --> 00:35:13,410
Па податочна структура е се уште во ред.

824
00:35:13,410 --> 00:35:14,330
>> Па, она што се случува следно?

825
00:35:14,330 --> 00:35:15,010
Ајде Стави во ред -

826
00:35:15,010 --> 00:35:15,370
Што е вашето име?

827
00:35:15,370 --> 00:35:16,160
>> ПУБЛИКАТА: Callen.

828
00:35:16,160 --> 00:35:16,580
>> Дејвид MALAN: Callen.

829
00:35:16,580 --> 00:35:20,770
Ајде да Стави во ред со Callen, и
22 е сега во редот.

830
00:35:20,770 --> 00:35:22,300
Па сега што мора да се смени тука?

831
00:35:22,300 --> 00:35:24,380
Напред, не се случува да се
промени, очигледно.

832
00:35:24,380 --> 00:35:27,160
Големина ќе се промени за да биде 2 повторно.

833
00:35:27,160 --> 00:35:31,590
И 22 завршува тука, 9 се уште е присутна,
но тоа е ефикасно

834
00:35:31,590 --> 00:35:32,600
ѓубре вредност сега.

835
00:35:32,600 --> 00:35:35,910
Тоа е само остаток од Џејк минатото.

836
00:35:35,910 --> 00:35:39,200
>> Па сега што ќе се случи ако
Јас dequeue Давид?

837
00:35:39,200 --> 00:35:41,560
Едно последно операција, dequeue Давид.

838
00:35:41,560 --> 00:35:46,070
Ние би можеле да ја префрлат, но јас предложи ајде
направите како што е малку работа како е можно.

839
00:35:46,070 --> 00:35:50,280
Сега, мојот податочна структура оди
се врати во големина 2-1.

840
00:35:50,280 --> 00:35:53,730
Но пред редот
сега станува 2.

841
00:35:53,730 --> 00:35:56,640
Јас не треба да ги промените овие броеви
само уште, затоа што тие се

842
00:35:56,640 --> 00:35:58,230
само ѓубре вредности.

843
00:35:58,230 --> 00:35:59,720
>> Но, сега што се случува?

844
00:35:59,720 --> 00:36:03,280
Претпоставувам дека си Стави во ред, 26?

845
00:36:03,280 --> 00:36:05,890
Се чувствувам како да припаѓаат овде.

846
00:36:05,890 --> 00:36:06,890
Па јас сум се enqueued.

847
00:36:06,890 --> 00:36:08,760
Па јас вид на припаѓам овде.

848
00:36:08,760 --> 00:36:11,300
И иако не сосема
го ценат тоа визуелно на сцената,

849
00:36:11,300 --> 00:36:15,075
бидејќи имаме многу простор, јас треба да
не се стои тука, зошто?

850
00:36:15,075 --> 00:36:16,290
>> ПУБЛИКАТА: Ти си надвор од границите.

851
00:36:16,290 --> 00:36:16,370
>> Дејвид MALAN: Право.

852
00:36:16,370 --> 00:36:16,940
Јас сум надвор од границите.

853
00:36:16,940 --> 00:36:19,330
Сум индексирани надвор од
границите на оваа низа.

854
00:36:19,330 --> 00:36:23,420
Јас навистина треба да биде во една од
три можни локации.

855
00:36:23,420 --> 00:36:25,150
Сега, каде е најприродната да одиме?

856
00:36:25,150 --> 00:36:27,760
Предлагам ние балон
една недела еден трик.

857
00:36:27,760 --> 00:36:30,150
МО оператор, процент.

858
00:36:30,150 --> 00:36:36,850
Бидејќи јас сум технички стои во
локација 3, но јас не 3 современи капацитети,

859
00:36:36,850 --> 00:36:40,250
толку 3, знакот за процент, 3 -

860
00:36:40,250 --> 00:36:40,970
капацитет е 3.

861
00:36:40,970 --> 00:36:41,720
Што е тоа?

862
00:36:41,720 --> 00:36:43,700
Она што е остатокот кога
ќе делат 3 од 3?

863
00:36:43,700 --> 00:36:44,070
0.

864
00:36:44,070 --> 00:36:48,140
>> Така што ме става беа Џејк беше,
кој е всушност добро.

865
00:36:48,140 --> 00:36:50,370
Па сега на имплементација
на ова нешто се случува да

866
00:36:50,370 --> 00:36:51,250
да биде малку главоболка.

867
00:36:51,250 --> 00:36:53,740
Тоа е навистина само една линија
на главоболка, на код.

868
00:36:53,740 --> 00:36:56,580
Но барем сега има ѓубре
вредност тука, но има две

869
00:36:56,580 --> 00:36:57,910
легитимни ints тука.

870
00:36:57,910 --> 00:37:04,160
И тврдам дека сега ние сме го направиле
токму она што ние треба да направите толку долго како

871
00:37:04,160 --> 00:37:08,600
ние се промени она што на Jake
вредност требаше да биде 26.

872
00:37:08,600 --> 00:37:12,110
>> Сега имаме доволно информации сé уште
да се задржи интегритет

873
00:37:12,110 --> 00:37:13,060
на овој податочна структура.

874
00:37:13,060 --> 00:37:17,160
Ние сме се уште вид на надвор од среќа кога ќе
сакате да вметнете четири или повеќе вкупните

875
00:37:17,160 --> 00:37:20,740
елементи, но можам да се направи барем прилично
ефикасно користење на оваа постојана

876
00:37:20,740 --> 00:37:21,740
време, во факт.

877
00:37:21,740 --> 00:37:27,150
Јас не мора да се грижите за менувањето
сите, како склоност Давид беше.

878
00:37:27,150 --> 00:37:30,816
>> Било какви прашања во Купишта,
или оваа задача?

879
00:37:30,816 --> 00:37:32,184
>> ПУБЛИКАТА: Дали е причината зошто
ви треба големината, па да знаете

880
00:37:32,184 --> 00:37:34,010
каде да се има личност?

881
00:37:34,010 --> 00:37:34,770
>> Дејвид MALAN: Токму така.

882
00:37:34,770 --> 00:37:38,230
Јас треба да се знае големината на низата
затоа што треба да знаат точно како

883
00:37:38,230 --> 00:37:41,940
многу од овие вредности се легитимни,
и така што ќе можам да најдам каде да се стави

884
00:37:41,940 --> 00:37:42,800
следниот лице.

885
00:37:42,800 --> 00:37:43,300
Токму така.

886
00:37:43,300 --> 00:37:44,580
Големината е -

887
00:37:44,580 --> 00:37:46,360
всушност, ние не ја ажурирате оваа уште.

888
00:37:46,360 --> 00:37:48,380
Јас додадени на 26.

889
00:37:48,380 --> 00:37:51,760
Големината е сега, не е 1, но 2.

890
00:37:51,760 --> 00:37:57,780
Па сега ова навистина ми помага да се најдат на
шеф на листата, која не е 0, не

891
00:37:57,780 --> 00:37:59,250
1, но е 2.

892
00:37:59,250 --> 00:38:01,665
На предниот дел на листа
е навистина бројот 22.

893
00:38:01,665 --> 00:38:05,120
Бидејќи тој дојде во прв, па затоа тој треба да
биде дозволено во продавница пред мене,

894
00:38:05,120 --> 00:38:08,780
иако визуелно Стојам
поблиску до продавница.

895
00:38:08,780 --> 00:38:09,220
>> Сите нели?

896
00:38:09,220 --> 00:38:12,410
А аплауз за овие момци
а ние ќе ги пуштам од таму.

897
00:38:12,410 --> 00:38:17,090
>> [Аплауз]

898
00:38:17,090 --> 00:38:18,150
>> Дејвид MALAN: не можев да
да ги задржи на послужавник.

899
00:38:18,150 --> 00:38:20,760
Можевме да видиме што ќе се случи ако
што сакате, но можеби не.

900
00:38:20,760 --> 00:38:21,590
Сите во право.

901
00:38:21,590 --> 00:38:25,380
И сега што, дали тоа ни остави?

902
00:38:25,380 --> 00:38:28,900
Па, дозволете ми предложи дека има
неколку други структури на податоци би можеле да

903
00:38:28,900 --> 00:38:33,810
започне додавајќи до нашата алатка комплет кој ќе
всушност ќе биде доста, доста релевантни како

904
00:38:33,810 --> 00:38:35,270
ние се нурне во веб нешта.

905
00:38:35,270 --> 00:38:38,150
Кои, повторно, има некој вид на врска
за дрва во форма на

906
00:38:38,150 --> 00:38:40,550
нешто што се нарекува ДОМ, документ
објект модел.

907
00:38:40,550 --> 00:38:42,370
Но ќе видиме повеќе од
дека пред долго.

908
00:38:42,370 --> 00:38:46,260
>> Дозволете ми да предложи definitionally дека ние
јавете дрво сега она што би можеле да знаат како

909
00:38:46,260 --> 00:38:48,820
повеќе од семејно стебло, каде што
имаат некој предок на

910
00:38:48,820 --> 00:38:49,790
корењата на дрвото.

911
00:38:49,790 --> 00:38:54,480
А патријархални или матриарх на
на самиот врв на дрво.

912
00:38:54,480 --> 00:38:56,700
Без нивниот брачен другар, во овој случај.

913
00:38:56,700 --> 00:39:00,940
Но сега имаме она што ќе го наречеме
деца, што се јазли кои висат

914
00:39:00,940 --> 00:39:05,480
надвор од левата дете или право дете,
стрели како што е прикажано тука.

915
00:39:05,480 --> 00:39:10,490
>> Со други зборови, во дрво структура на податоци
во компјутерот, едно дрво има нула

916
00:39:10,490 --> 00:39:11,480
или повеќе лимфни јазли.

917
00:39:11,480 --> 00:39:13,500
Ако има најмалку еден јазол,
што се вика коренот.

918
00:39:13,500 --> 00:39:15,700
Тоа е она визуелно дека
цртаме на врвот.

919
00:39:15,700 --> 00:39:20,280
И тој јазол, како и секој друг јазол, може да
имаат нула, еден, или два, или три,

920
00:39:20,280 --> 00:39:23,600
или сепак многу деца на
податочна структура поддржува.

921
00:39:23,600 --> 00:39:29,150
Во овој случај, коренот, чување на
вредност еден, има две деца, 2 и 3,

922
00:39:29,150 --> 00:39:33,020
па ние обично се јавите 2 левата
дете и 3 на десната дете.

923
00:39:33,020 --> 00:39:36,940
>> А потоа кога ќе се фаќате за 5, 6 и
7, 6 може да се нарече средината дете.

924
00:39:36,940 --> 00:39:38,940
Ако имате четири деца,
станува збунувачки.

925
00:39:38,940 --> 00:39:42,260
Значи ние да престане со користење таков вид
на кратенка вербално.

926
00:39:42,260 --> 00:39:44,580
Но тоа е навистина само семејно стебло.

927
00:39:44,580 --> 00:39:48,880
А лисјата тука се јазли кои
самите немаат деца.

928
00:39:48,880 --> 00:39:52,540
Тие висат надвор од дното на дрвото.

929
00:39:52,540 --> 00:39:56,940
>> Па како да се спроведе дрво кое
има само две деца максимално?

930
00:39:56,940 --> 00:39:58,410
Ние ќе го наречеме бинарен дрво.

931
00:39:58,410 --> 00:40:00,960
Bi повторно значи два, во овој
случај, како и со бинарни.

932
00:40:00,960 --> 00:40:04,830
И така тоа може да има нула, еден,
или две деца максимално.

933
00:40:04,830 --> 00:40:08,650
>> Јас ќе предложи дека ние спроведување на јазол
за таа структура со int n,

934
00:40:08,650 --> 00:40:11,910
а потоа две покажувачи, една што се вика
лево, една што се вика во право.

935
00:40:11,910 --> 00:40:14,830
Но тие се само убаво
произволни конвенции.

936
00:40:14,830 --> 00:40:18,170
И она што е убаво сега, особено ако
вид на се бореше концептуално со

937
00:40:18,170 --> 00:40:21,300
рекурзија, или мисли дека тоа не е
навистина решение за ништо,

938
00:40:21,300 --> 00:40:23,120
особено ако може
снема меморија.

939
00:40:23,120 --> 00:40:26,600
Сега дека ние зборуваме за податоци
структури и алгоритми кои им овозможуваат на

940
00:40:26,600 --> 00:40:31,030
ни за напречни и манипулираат со нив,
Излегува дека рекурзија се враќа во

941
00:40:31,030 --> 00:40:34,240
многу повеќе привлечни
Ако не е убава начин.

942
00:40:34,240 --> 00:40:38,670
>> Значи ова го предлагам е спроведувањето
на функцијата за пребарување.

943
00:40:38,670 --> 00:40:39,870
Дадени два влеза -

944
00:40:39,870 --> 00:40:41,570
па мислам на ова како црна кутија.

945
00:40:41,570 --> 00:40:46,560
Дадени два елемента, n, на број, и
покажувачот за дрво, покажувач кон

946
00:40:46,560 --> 00:40:50,020
јазол, или навистина во коренот на дрвото, јас
тврдат дека оваа функција може да се врати

947
00:40:50,020 --> 00:40:53,530
лажни или вистинити, дека n вредност
е во внатрешноста на ова дрво.

948
00:40:53,530 --> 00:40:55,210
>> Она што е внатре на оваа црна кутија?

949
00:40:55,210 --> 00:40:57,440
Па, четири гранки.

950
00:40:57,440 --> 00:40:58,385
Првиот само проверки.

951
00:40:58,385 --> 00:41:00,490
Ако дрвото е null, само враќање false.

952
00:41:00,490 --> 00:41:04,580
Ако нема јазол, нема n,
нема број, само враќање false.

953
00:41:04,580 --> 00:41:12,330
Ако сепак, n, вредноста сте во потрага
за, е помала од дрво стрелките на n и

954
00:41:12,330 --> 00:41:15,180
само за да бидат јасни, што значи тоа кога
Јас пишувам дрво, а потоа на стрелката

955
00:41:15,180 --> 00:41:18,150
нотација, n?

956
00:41:18,150 --> 00:41:18,690
Токму така.

957
00:41:18,690 --> 00:41:21,970
Тоа значи dereference дека
покажувач кој се нарекува дрво.

958
00:41:21,970 --> 00:41:26,750
Оди таму, а потоа се добие во внатрешноста на таа
јазол и да добијат своето поле нарекува n.

959
00:41:26,750 --> 00:41:30,810
А потоа се споредат реалните n тоа беше
донесен во Барај против тоа.

960
00:41:30,810 --> 00:41:35,390
>> Па ако n е помала n вредност
во дрво јазол себе, добро,

961
00:41:35,390 --> 00:41:36,720
Што значи тоа?

962
00:41:36,720 --> 00:41:40,690
Што не значи ништо на прв поглед.

963
00:41:40,690 --> 00:41:40,900
Нели?

964
00:41:40,900 --> 00:41:45,560
Исто како кога ќе имаат низа на
вредности, можеби ќе сакате да се применуваат бинарни

965
00:41:45,560 --> 00:41:48,290
пребарување како форма на поделба
и освојување.

966
00:41:48,290 --> 00:41:51,790
Но, она што претпоставка не ни треба да се направи
за бинарни пребарување за да работат на сите

967
00:41:51,790 --> 00:41:54,510
во телефонот книга и
претходните примери?

968
00:41:54,510 --> 00:41:55,530
>> Како да се подредени.

969
00:41:55,530 --> 00:41:59,490
Па ајде да ја прилагодите на дефиниција на дрвото
тука да не биде само едно дрво, што може да

970
00:41:59,490 --> 00:42:00,880
има неограничен број на деца.

971
00:42:00,880 --> 00:42:04,700
Не само бинарно дрво, што може да
имаат 0, 1 или 2 максимално.

972
00:42:04,700 --> 00:42:09,700
Но како бинарен за пребарување дрво, или БСТ,
која е само фенси начин да се каже на

973
00:42:09,700 --> 00:42:15,430
бинарно дрво таква што секој јазол
левата дете, доколку се присутни, е

974
00:42:15,430 --> 00:42:16,830
помалку од јазол.

975
00:42:16,830 --> 00:42:20,170
И секој јазол е во право дете,
ако се присутни, е поголем

976
00:42:20,170 --> 00:42:21,740
од јазол себе.

977
00:42:21,740 --> 00:42:25,200
>> Значи со други зборови, ако сте во ситуација да се подготви
дрво надвор, сите на броеви се

978
00:42:25,200 --> 00:42:30,620
внимателно избалансирани вака, така што ако
имате 55 како root, 33 можат да одат

979
00:42:30,620 --> 00:42:33,090
да неговата лева, бидејќи тоа е помалку од 55.

980
00:42:33,090 --> 00:42:36,430
77 може да оди на своето право, бидејќи
тоа е поголема од 55.

981
00:42:36,430 --> 00:42:40,750
Но сега забележите, истата дефиниција,
тоа е рекурзивен дефиниција вербално,

982
00:42:40,750 --> 00:42:42,600
мора да аплицираат за 33.

983
00:42:42,600 --> 00:42:47,610
33 го напушти детето мора да биде помало од тоа,
и правото на детето 33 е 44, мора да биде

984
00:42:47,610 --> 00:42:48,580
поголем од него.

985
00:42:48,580 --> 00:42:51,670
>> Значи ова е бинарно пребарување дрво, и
Јас предложи, со користење на малку на

986
00:42:51,670 --> 00:42:53,910
рекурзија, ние сега може да се најде n.

987
00:42:53,910 --> 00:42:59,160
Значи, ако n е помала од вредноста n тоа е
тековната јазол, јас ќе одам да си

988
00:42:59,160 --> 00:43:04,090
напред и залог, така да се каже, и само
се врати она што одговорот е на

989
00:43:04,090 --> 00:43:08,470
во потрага по n на
левата дрвото дете.

990
00:43:08,470 --> 00:43:11,370
Забележите повторно, оваа функција само
очекува јазол ѕвезда,

991
00:43:11,370 --> 00:43:12,780
покажувач кон јазол.

992
00:43:12,780 --> 00:43:17,360
Па сигурно јас само може да се направи дрво
стрелка лево, што ќе доведе

993
00:43:17,360 --> 00:43:18,400
ме до друг јазол.

994
00:43:18,400 --> 00:43:19,480
Но она што е тој јазол?

995
00:43:19,480 --> 00:43:22,820
>> Па, според оваа декларација,
лево е само покажувач, така што само

996
00:43:22,820 --> 00:43:27,090
значи јас сум поминува до функцијата за пребарување
различни покажувач, имено

997
00:43:27,090 --> 00:43:30,750
оној што претставува
мојата лева дете дрво.

998
00:43:30,750 --> 00:43:36,040
Значи во овој случај, на покажувачот до 33, ако
ова е нашиот примерок влез меѓувреме, ако

999
00:43:36,040 --> 00:43:40,740
n е поголема од вредноста n на
тековната јазол во стеблото, тогаш јас сум

1000
00:43:40,740 --> 00:43:43,370
ќе одиме напред и залог во други
насока и само велат, јас не

1001
00:43:43,370 --> 00:43:47,280
знам дали оваа вредност n е во дрво,
но знам ако е така, тоа е по моите

1002
00:43:47,280 --> 00:43:49,090
право гранка, така да се каже.

1003
00:43:49,090 --> 00:43:53,120
Па ајде мене повик рекурзивно пребарување,
поминува еден n повторно, но поминува во

1004
00:43:53,120 --> 00:43:54,580
покажувачот на моето право дете.

1005
00:43:54,580 --> 00:44:00,020
>> Со други зборови, ако јас сум моментално на 55
и јас барам за 99, знам дека 99

1006
00:44:00,020 --> 00:44:04,270
е поголем од 55, па онака како што раскина
на телефонот книга недели и ние

1007
00:44:04,270 --> 00:44:07,140
отиде право, слично сме ние
одам да си во право тука.

1008
00:44:07,140 --> 00:44:11,960
И јас не знам дали тоа е во мојата десна
дете, и тоа не е, 77 е таму, но

1009
00:44:11,960 --> 00:44:13,210
Знам дека е во таа насока.

1010
00:44:13,210 --> 00:44:18,770
Па јас го нарекувам пребарување на моето право дете,
77, и нека пребарување дознаам од

1011
00:44:18,770 --> 00:44:24,950
таму ако 99 во оваа произволна
Пример за ова е всушност таму.

1012
00:44:24,950 --> 00:44:26,900
>> Друго, она што е конечниот случај?

1013
00:44:26,900 --> 00:44:28,620
Ако дрвото е null е еден случај.

1014
00:44:28,620 --> 00:44:31,890
Ако n е помалку од сегашната јазол
вредност е друг случај.

1015
00:44:31,890 --> 00:44:35,120
Ако n е поголема од тековната
вредност јазол е трет случај.

1016
00:44:35,120 --> 00:44:38,250
Што е четвртиот и последен случај?

1017
00:44:38,250 --> 00:44:39,480
Мислам дека ние сме надвор од случаите, нели?

1018
00:44:39,480 --> 00:44:44,690
Тоа мора да биде дека n е во
тековната јазол дека јас сум на.

1019
00:44:44,690 --> 00:44:49,640
>> Значи, ако јас сум во потрага по 55 во овој момент
во приказната, таа гранка на

1020
00:44:49,640 --> 00:44:51,780
дрво ќе се врати вистина.

1021
00:44:51,780 --> 00:44:55,380
Значи она што е интересно овде е дека ние
всушност, за разлика недели минатото, ние вид

1022
00:44:55,380 --> 00:44:56,740
на имаат два база случаи.

1023
00:44:56,740 --> 00:44:58,300
И тие не мора да се
биде на врвот.

1024
00:44:58,300 --> 00:45:01,390
На врвот е база случај, бидејќи ако
дрво е нула, нема ништо да се направи.

1025
00:45:01,390 --> 00:45:03,410
Само се вратат на хард кодирани
вредноста на неточно.

1026
00:45:03,410 --> 00:45:07,400
>> На дното гранка е вид на
Стандардно, при што ако ние Сум проверил за

1027
00:45:07,400 --> 00:45:11,550
нула, ние Сум проверил дали тоа треба да биде
лево, но тоа не треба да биде, ние сме

1028
00:45:11,550 --> 00:45:14,640
проверува дали тој треба да биде во право, но тоа
не треба да биде, јасно е дека мора да биде

1029
00:45:14,640 --> 00:45:15,870
право, каде сме.

1030
00:45:15,870 --> 00:45:16,780
Тоа е база случај.

1031
00:45:16,780 --> 00:45:19,920
Значи има две рекурзивен случаи
сендвич таму во средината.

1032
00:45:19,920 --> 00:45:21,630
Но можев да го имаат напишано
ова во секој ред.

1033
00:45:21,630 --> 00:45:24,520
Јас само мислев дека вид на се чувствува природно
прво да се провери за можна грешка,

1034
00:45:24,520 --> 00:45:28,340
тогаш проверете остави, тогаш проверете во право, тогаш
Претпоставуваме дека сте на јазол

1035
00:45:28,340 --> 00:45:30,630
ти си, всушност барате.

1036
00:45:30,630 --> 00:45:36,240
>> Па зошто ова може да биде корисно?

1037
00:45:36,240 --> 00:45:37,910
Така што се испоставува -

1038
00:45:37,910 --> 00:45:42,110
и дозволете ми да скокнат до закачка
тука тоа е во мрежата.

1039
00:45:42,110 --> 00:45:44,920
Ние ќе треба да почнат да го користат не
програмскиот јазик во прво време, но

1040
00:45:44,920 --> 00:45:46,030
Селектирај јазик.

1041
00:45:46,030 --> 00:45:48,740
А јазик за Селектирај е оној кој е
слични во духот со програмирање

1042
00:45:48,740 --> 00:45:51,715
јазик, но тоа не ви даде
способност да се изразат логично.

1043
00:45:51,715 --> 00:45:55,070
Тоа само ви дава можност да се
изразат себе си структурно.

1044
00:45:55,070 --> 00:45:57,960
>> Каде сакате да се стави нешто
на оваа страница, веб-страница?

1045
00:45:57,960 --> 00:45:59,200
Каква боја сакаш да се направи тоа?

1046
00:45:59,200 --> 00:46:00,950
Што големина на фонт сакаш да се направи тоа?

1047
00:46:00,950 --> 00:46:02,970
Она што зборовите ќе го направите, всушност,
сакате на веб страната?

1048
00:46:02,970 --> 00:46:04,060
Така што е маркап јазик.

1049
00:46:04,060 --> 00:46:07,690
Но, тогаш ние многу брзо ќе се воведе
JavaScript, која е полноправна членка на

1050
00:46:07,690 --> 00:46:08,560
програмски јазик.

1051
00:46:08,560 --> 00:46:12,530
Многу слични синтаксички во изгледот
на C, но тоа ќе има некои

1052
00:46:12,530 --> 00:46:15,200
убаво, помоќен,
корисник пријателски особини.

1053
00:46:15,200 --> 00:46:18,050
>> И еден од фрустрации во овој
точка во семестар е дека ние ќе

1054
00:46:18,050 --> 00:46:22,065
наскоро спроведе правопис во далеку помалку
линии на код со употреба на други јазици

1055
00:46:22,065 --> 00:46:25,580
од C себе дозволува, туку и за причина за
ние наскоро ќе се разбере.

1056
00:46:25,580 --> 00:46:27,750
Ова ќе биде прв ваков веб-страница.

1057
00:46:27,750 --> 00:46:30,120
Таа ќе биде целосно underwhelming,
првиот правиме.

1058
00:46:30,120 --> 00:46:31,400
Тоа едноставно ќе се каже, Здраво светот.

1059
00:46:31,400 --> 00:46:34,010
Но ако никогаш не сум го видел
пред, ова е HTML,

1060
00:46:34,010 --> 00:46:35,670
HyperText Markup Language.

1061
00:46:35,670 --> 00:46:39,310
>> Ако одите до одреден опција од менито во
повеќето секој интернет пребарувач, на било кој веб-страница на

1062
00:46:39,310 --> 00:46:43,160
на интернет, можете да видите на HTML
дека некои луѓе му напиша писмо на

1063
00:46:43,160 --> 00:46:44,400
создаде таа веб страница.

1064
00:46:44,400 --> 00:46:47,850
И тоа најверојатно не изгледа како
кратка или како уредни како оваа.

1065
00:46:47,850 --> 00:46:51,400
Но, тоа ќе го следат моделот на овие
отворен загради и засеци и

1066
00:46:51,400 --> 00:46:53,660
писма и потенцијално броеви.

1067
00:46:53,660 --> 00:46:56,770
>> Мислев дека ќе ви даде краток вовед
од она што ќе биде во можност да го стори

1068
00:46:56,770 --> 00:46:57,950
по преземањето CS50.

1069
00:46:57,950 --> 00:47:02,620
Дозволете ми да одат на cs.harvard.edu / одземеш,
почетната страница од пребарувачот нашите сопствени Роб Бауден.

1070
00:47:02,620 --> 00:47:06,080
Тој го направи тоа за нас.

1071
00:47:06,080 --> 00:47:07,490
Па дека наскоро ќе биде во можност да го стори тоа.

1072
00:47:07,490 --> 00:47:10,660
И, исто така, она што го слушнав
ова утро -

1073
00:47:10,660 --> 00:47:12,480
она што го слушнав ова утро -

1074
00:47:12,480 --> 00:47:13,780
>> [Хрчак денс музиката]

1075
00:47:13,780 --> 00:47:15,702
>> - You'Ll да биде во можност да се направи ова.

1076
00:47:15,702 --> 00:47:16,790
Што не чека во средата.

1077
00:47:16,790 --> 00:47:17,791
Ние ќе се видиме тогаш.

1078
00:47:17,791 --> 00:47:22,950
>> [Хрчак денс музиката]

1079
00:47:22,950 --> 00:47:24,300
Дејвид MALAN: На следниот CS50 -

1080
00:47:24,300 --> 00:47:31,670