1
00:00:00,000 --> 00:00:03,423
>> [Музички]

2
00:00:03,423 --> 00:00:05,380

3
00:00:05,380 --> 00:00:08,210
>> АНДИ Пенг: Добредојдовте на недела 6 на секција.

4
00:00:08,210 --> 00:00:11,620
Ние се отклонува од нашиот стандард
време дел од вторник

5
00:00:11,620 --> 00:00:14,130
Попладнето на оваа прекрасна недела наутро.

6
00:00:14,130 --> 00:00:17,330
Ви благодариме за сите оние кои
приклучи мене денес, но сериозно,

7
00:00:17,330 --> 00:00:18,170
аплауз.

8
00:00:18,170 --> 00:00:20,600
>> Тоа е прилично голем напор.

9
00:00:20,600 --> 00:00:23,600
Јас скоро и да не дури и го направи
во тоа време, но тоа е во ред.

10
00:00:23,600 --> 00:00:27,520
Па знам дека сите од вас
Само што го направи на квиз.

11
00:00:27,520 --> 00:00:30,370
Прво на сите, добредојде да
На друга страна на тоа.

12
00:00:30,370 --> 00:00:32,917
>> Второ, ние ќе разговараме за тоа.

13
00:00:32,917 --> 00:00:34,000
Ќе зборуваме за квизот.

14
00:00:34,000 --> 00:00:35,700
Ние ќе зборуваме за тоа како
што го правиш во класата.

15
00:00:35,700 --> 00:00:36,550
Ќе биде во ред.

16
00:00:36,550 --> 00:00:39,080
Имам вашето квизови за
ви на крајот од тука,

17
00:00:39,080 --> 00:00:42,120
па ако момци сакаат да ги преземат
погледне во него, сосема во ред.

18
00:00:42,120 --> 00:00:46,590
>> Толку брзо, пред да почне,
агенда за денес е како што следува.

19
00:00:46,590 --> 00:00:48,430
Како што можете да видите, ние сме
во основа брзо отпуштање

20
00:00:48,430 --> 00:00:52,120
преку целиот куп на структури на податоци
навистина, навистина, навистина брзо.

21
00:00:52,120 --> 00:00:54,380
Па како таква, таа нема да биде
супер интерактивни денес.

22
00:00:54,380 --> 00:00:59,620
Тоа само ќе биде мене вид на викање
работи кои што, и ако ви се збуни,

23
00:00:59,620 --> 00:01:02,680
ако јас одам премногу брзо, да ме известите.

24
00:01:02,680 --> 00:01:05,200
Тие се само различни податоци
структури, и како дел

25
00:01:05,200 --> 00:01:07,070
на вашиот pset за ова
претстојната недела, ќе

26
00:01:07,070 --> 00:01:10,340
да се побара да се спроведе еден од нив,
можеби две од them-- две од нив

27
00:01:10,340 --> 00:01:12,319
во вашиот pset.

28
00:01:12,319 --> 00:01:14,610
Добро, па јас сум само ќе
започне со некои најави.

29
00:01:14,610 --> 00:01:19,070
Ние ќе одиме во текот Купишта и редици повеќе во
длабочина од она што ние го сторивме пред квиз.

30
00:01:19,070 --> 00:01:20,990
Ние ќе одиме во текот поврзани
листата повторно, уште еднаш,

31
00:01:20,990 --> 00:01:23,899
повеќе во длабочина од она што
имавме пред квиз.

32
00:01:23,899 --> 00:01:26,440
А потоа ние ќе зборуваме за хаш
маси, дрвја и неуспешни обиди, во која

33
00:01:26,440 --> 00:01:28,890
се прилично потребно за вашиот pset.

34
00:01:28,890 --> 00:01:32,925
И потоа ќе одиме во текот на некои
корисни совети за pset5.

35
00:01:32,925 --> 00:01:37,360
>> Добро, па квиз 0.

36
00:01:37,360 --> 00:01:41,090
Просекот бил 58%.

37
00:01:41,090 --> 00:01:45,370
Тоа беше многу ниска, и така вие момци сите
направи многу, многу добро во согласност

38
00:01:45,370 --> 00:01:46,510
со тоа.

39
00:01:46,510 --> 00:01:49,970
>> Прилично многу, непишано правило е ако сте
во рок од една стандардна девијација на средната вредност

40
00:01:49,970 --> 00:01:52,990
особено бидејќи се наоѓаме во помалку
удобни секција, ти си сосема во ред.

41
00:01:52,990 --> 00:01:54,120
Вие сте на вистинскиот пат.

42
00:01:54,120 --> 00:01:55,190
Животот е добар.

43
00:01:55,190 --> 00:01:58,952
>> Знам дека е страшно да се размислува дека
Добив како 40% на овој квиз.

44
00:01:58,952 --> 00:02:00,160
Одам да пропадне оваа класа.

45
00:02:00,160 --> 00:02:02,243
Јас Ви ветувам, вие не сте
ќе пропадне класата.

46
00:02:02,243 --> 00:02:03,680
Ти си сосема во ред.

47
00:02:03,680 --> 00:02:06,850
>> За оние од вас кои се здобија со текот
средна вредност, импресивен, импресивен,

48
00:02:06,850 --> 00:02:08,780
како, сериозно добро направено.

49
00:02:08,780 --> 00:02:09,689
Јас ги имаат со мене.

50
00:02:09,689 --> 00:02:11,730
Се чувствуваат слободни да дојдат да ги добие
на крајот на секција.

51
00:02:11,730 --> 00:02:14,520
Дозволете ми да знам ако имате било какви
прашања, прашања со нив.

52
00:02:14,520 --> 00:02:17,204
Ако ние додадете вашиот резултат
во ред, ги споделите со нас.

53
00:02:17,204 --> 00:02:21,240
>> Добро, па pset5, ова е навистина
чудни недела за Јеил во смисла

54
00:02:21,240 --> 00:02:24,240
дека нашите pset се должи
Среда на пладне вклучувајќи

55
00:02:24,240 --> 00:02:27,317
Кон крајот на денот, така што е, всушност,
теоретски поради денеска на пладне.

56
00:02:27,317 --> 00:02:29,150
Веројатно никој не заврши
во вторник на пладне.

57
00:02:29,150 --> 00:02:30,830
Тоа е сосема во ред.

58
00:02:30,830 --> 00:02:33,700
Ние ќе треба да се има на работното време
Вечерва, како и во понеделникот вечерта.

59
00:02:33,700 --> 00:02:36,810
И сите делови на оваа недела ќе го
всушност може да се претвори во работилници,

60
00:02:36,810 --> 00:02:38,800
па можете слободно да поп во
секој дел што го сакате,

61
00:02:38,800 --> 00:02:42,810
и тие ќе бидат во вид на мини-pset
работилници за помош на тоа.

62
00:02:42,810 --> 00:02:45,620
Така како што се, ова е само дел
каде што ние сме наставен материјал.

63
00:02:45,620 --> 00:02:49,220
Сите други потези ќе се фокусира
исклучиво на помош за pset.

64
00:02:49,220 --> 00:02:50,146
Да?

65
00:02:50,146 --> 00:02:52,000
>> ПУБЛИКАТА: Каде се работното време?

66
00:02:52,000 --> 00:02:56,120
>> АНДИ Пенг: Работно време
tonight-- ох, добро прашање.

67
00:02:56,120 --> 00:03:00,580
Мислам дека работното време вечерва
се во ТЕАЛ или на Ризницата.

68
00:03:00,580 --> 00:03:02,984
Ако ја изберете онлајн CS50
и да одите на работното време,

69
00:03:02,984 --> 00:03:05,650
треба да има распоред кој
ви, каде што сите од нив се кажува.

70
00:03:05,650 --> 00:03:07,954
>> Знам или вечерва
или утре е ТЕАЛ,

71
00:03:07,954 --> 00:03:10,120
и мислам дека може да има
комонс за друга ноќ.

72
00:03:10,120 --> 00:03:11,020
Не сум сигурен.

73
00:03:11,020 --> 00:03:11,700
Добро прашање.

74
00:03:11,700 --> 00:03:14,430
Проверете на CS50.

75
00:03:14,430 --> 00:03:18,780
>> Кул, било какви прашања во врска со
распоред за наредните три дена, како?

76
00:03:18,780 --> 00:03:21,690
Јас ветувам дека вие момци како Дејвид
рече, ова е врвот на ридот.

77
00:03:21,690 --> 00:03:23,050
Вие момци се речиси таму.

78
00:03:23,050 --> 00:03:24,644
Само уште три дена.

79
00:03:24,644 --> 00:03:26,310
Одам таму, и тогаш сите ние ќе се сруши.

80
00:03:26,310 --> 00:03:28,114
Ќе имаме убав CS без пауза.

81
00:03:28,114 --> 00:03:28,780
Ќе се вратиме.

82
00:03:28,780 --> 00:03:30,779
Ние ќе се нурне во интернет
програмирање и развој,

83
00:03:30,779 --> 00:03:35,150
работи кои се многу забавно споредба
на некои од други psets.

84
00:03:35,150 --> 00:03:37,974
И тоа ќе биде студ, и
ќе имаме многу забава.

85
00:03:37,974 --> 00:03:38,890
Ќе имаме повеќе бонбони.

86
00:03:38,890 --> 00:03:39,730
Жал ми е за слатки.

87
00:03:39,730 --> 00:03:40,945
Го заборавив бонбони.

88
00:03:40,945 --> 00:03:43,310
Тоа беше груба утро.

89
00:03:43,310 --> 00:03:46,340
Па вие сте речиси таму,
и јас сум навистина горд на вас момци.

90
00:03:46,340 --> 00:03:49,570
>> Добро, па Купишта.

91
00:03:49,570 --> 00:03:53,331
Кој ги сака прашањето за Џек
и неговата облека на квизот?

92
00:03:53,331 --> 00:03:53,830
Никој?

93
00:03:53,830 --> 00:03:56,500
Добро, тоа е во ред.

94
00:03:56,500 --> 00:04:00,200
>> Значи во суштина како што можете да
слика Џек, овој човек овде,

95
00:04:00,200 --> 00:04:03,350
сака да ги преземе облека
од врвот на магацинот,

96
00:04:03,350 --> 00:04:05,750
и тој го става назад кон
магацинот откако тој е направено.

97
00:04:05,750 --> 00:04:07,600
Така на овој начин, тој никогаш не
се чини дека се добива

98
00:04:07,600 --> 00:04:10,090
на дното на
магацинот во неговата облека.

99
00:04:10,090 --> 00:04:12,600
Така овој вид на опишува
основната структура на податоци

100
00:04:12,600 --> 00:04:16,610
за тоа како се спроведува оџак.

101
00:04:16,610 --> 00:04:20,060
>> Во суштина, се мисли на
магацинот како и секоја магацинот на објекти

102
00:04:20,060 --> 00:04:24,900
каде што ќе се стави работите кон врвот, и
потоа ќе ги поп надвор од врвот.

103
00:04:24,900 --> 00:04:28,600
Па LIFO е акроним што ни се допаѓа
да use-- Последно, а прв.

104
00:04:28,600 --> 00:04:32,480
И така трае до врвот на
Стек е првиот што излегува.

105
00:04:32,480 --> 00:04:34,260
И така на два мандата
ние сакале да се дружат

106
00:04:34,260 --> 00:04:36,190
со кои се нарекуваат притисни и поп.

107
00:04:36,190 --> 00:04:39,790
Кога ќе се притисне нешто врз
магацинот, и можете да го поп назад.

108
00:04:39,790 --> 00:04:43,422
>> И така претпоставувам дека ова е вид на
апстрактен поим за оние од вас

109
00:04:43,422 --> 00:04:45,630
кои сакаат да видат како
Крај на спроведувањето на оваа

110
00:04:45,630 --> 00:04:46,740
во реалниот свет.

111
00:04:46,740 --> 00:04:50,170
Колкумина од вас имаат напишано есеј
можеби како еден час пред тоа се должи,

112
00:04:50,170 --> 00:04:54,510
и случајно избришиме огромен
парче од него, како случајно?

113
00:04:54,510 --> 00:04:58,560
И тогаш што се направи контрола
ние ги користиме за да го стави назад?

114
00:04:58,560 --> 00:05:00,030
Контрола-Зи, је?

115
00:05:00,030 --> 00:05:03,640
Контрола-Зи, така што износот на време
кои го контролираат Зи го спаси животот,

116
00:05:03,640 --> 00:05:08,820
спасила мојот газ, во секое време
кој е спроведен преку оџак.

117
00:05:08,820 --> 00:05:13,020
>> Во суштина сите информации
што е на вашиот Word документ,

118
00:05:13,020 --> 00:05:15,080
таа добива се наметнува и појави по своја волја.

119
00:05:15,080 --> 00:05:19,460
И така во суштина секогаш кога ќе
избришете нешто, можете да го поп назад.

120
00:05:19,460 --> 00:05:22,820
А потоа, ако е потребно, со што ви
да извршат притисок, што е она што control-C е така.

121
00:05:22,820 --> 00:05:26,770
И светот функционира толку реално
за тоа како едноставна структура на податоци

122
00:05:26,770 --> 00:05:28,690
може да помогне во вашиот секојдневен живот.

123
00:05:28,690 --> 00:05:31,710

124
00:05:31,710 --> 00:05:40,150
>> Па struct е начинот на кој
ние всушност го создаде оџак.

125
00:05:40,150 --> 00:05:44,720
Ние се дефинира тип struct, а потоа
ние ја нарекуваме магацинот на дното.

126
00:05:44,720 --> 00:05:47,440
И во рамките на магацинот,
имаме два параметри

127
00:05:47,440 --> 00:05:51,580
кои во суштина може да се манипулира,
па ние имаме капацитет знак ѕвезда жици.

128
00:05:51,580 --> 00:05:55,150
>> Сето тоа го прави
е создавање на низа

129
00:05:55,150 --> 00:05:58,835
дека ние може да се сместат што и да сакате
која може да се утврди неговиот капацитет.

130
00:05:58,835 --> 00:06:01,990
Капацитет е само максималното количество на
предмети што може да се стави во оваа низа.

131
00:06:01,990 --> 00:06:05,660
int големина е контра што ги држи
пратите на колку предмети се во моментов

132
00:06:05,660 --> 00:06:07,850
во магацинот.

133
00:06:07,850 --> 00:06:11,860
Па тогаш можеме да ги пратите на тоа, А,
и колку големи вистинските оџакот е,

134
00:06:11,860 --> 00:06:14,850
а, Б, колкав дел од тие магацинот
ние исполнет бидејќи ние не сакаме

135
00:06:14,850 --> 00:06:18,800
до претекување поради, како што е нашиот капацитет.

136
00:06:18,800 --> 00:06:24,340
>> Така на пример, во оваа прекрасна
прашање е на вашиот квиз.

137
00:06:24,340 --> 00:06:28,160
Во суштина како ние да им помогнам на
кон врвот на магацинот.

138
00:06:28,160 --> 00:06:28,830
Прилично едноставна.

139
00:06:28,830 --> 00:06:30,621
Ако се погледне во него,
ние ќе одиме преку ова.

140
00:06:30,621 --> 00:06:32,640
Ако [Беззвучен] size--
се сеќавам, секогаш кога ќе

141
00:06:32,640 --> 00:06:35,300
сакате да пристапите на некој
параметар во рамките на struct,

142
00:06:35,300 --> 00:06:40,320
го прават името на struct.parameter.

143
00:06:40,320 --> 00:06:42,720
>> Во овој случај, s е
името на нашиот оџак.

144
00:06:42,720 --> 00:06:46,230
Ние сакаме да се пристапи на големина
од него, па правиме s.size.

145
00:06:46,230 --> 00:06:50,280
Така што додека големината не е
еднаква на лице или како долг

146
00:06:50,280 --> 00:06:52,940
како што тоа е помалку од капацитет,
или ќе работат тука.

147
00:06:52,940 --> 00:06:57,180
>> Сакате да пристапите на внатрешната
на вашиот оџак, па s.strings,

148
00:06:57,180 --> 00:07:00,790
и ви се случува да се стави дека новиот број
што сакате да го вметнете во таму.

149
00:07:00,790 --> 00:07:05,030
Да речеме ние ќе сакате да го
внесете int n врз оџакот,

150
00:07:05,030 --> 00:07:08,905
можеме да направиме s.strings,
загради, s.size еднаква на n.

151
00:07:08,905 --> 00:07:11,030
Поради големината е местото каде што ние
во моментов се во магацинот

152
00:07:11,030 --> 00:07:14,590
ако ние се случува да им помогнам на
тоа, ние само пристап

153
00:07:14,590 --> 00:07:17,370
каде големината е,
тековната полнотата на магацинот,

154
00:07:17,370 --> 00:07:21,729
а ние им помогнам на int n врз него.

155
00:07:21,729 --> 00:07:24,770
А потоа ние сакаме да се осигураме дека
ние сме, исто така, ја зголемува големината на n,

156
00:07:24,770 --> 00:07:27,436
за да можеме да ги пратите на тоа ние сме
додаде екстра работа да магацинот.

157
00:07:27,436 --> 00:07:29,660
Сега имаме поголема големина.

158
00:07:29,660 --> 00:07:33,196
Дали ова тука имало смисла да се
сите, како логично тоа функционира?

159
00:07:33,196 --> 00:07:34,160
Тоа беше вид на брз.

160
00:07:34,160 --> 00:07:39,535

161
00:07:39,535 --> 00:07:42,160
ПУБЛИКАТА: Можете ли да одиме во текот
на s.stringss.strings [s.size] повторно?

162
00:07:42,160 --> 00:07:45,808
АНДИ Пенг: Секако, така што она што го прави тоа
s.size моментов ни ја даде?

163
00:07:45,808 --> 00:07:47,440
ПУБЛИКАТА: Тоа е моменталната големина.

164
00:07:47,440 --> 00:07:50,890
АНДИ Пенг: Точно, така што
Тековниот индекс на нашите големина е во,

165
00:07:50,890 --> 00:07:57,780
и затоа сакаме да се стави нова цел број
кои сакаме да ги вметнете во s.size.

166
00:07:57,780 --> 00:07:58,760
Дали тоа има смисла?

167
00:07:58,760 --> 00:08:01,110
Бидејќи s.strings, сето она што
е е името на низата.

168
00:08:01,110 --> 00:08:03,510
Сето тоа е се што пристапуваат на
низа во рамките на нашите struct,

169
00:08:03,510 --> 00:08:06,030
и така, ако сакаме да
поставите n во тој индекс,

170
00:08:06,030 --> 00:08:09,651
ние само може да го пристап
користење s.size загради.

171
00:08:09,651 --> 00:08:10,150
Кул.

172
00:08:10,150 --> 00:08:13,580

173
00:08:13,580 --> 00:08:18,916
>> Добро, поп, го pseudocode надвор
за вас момци, но сличен концепт.

174
00:08:18,916 --> 00:08:19,790
Дали тоа има смисла?

175
00:08:19,790 --> 00:08:22,310
Ако големината е поголема
од нула, тогаш

176
00:08:22,310 --> 00:08:25,350
знаете дека сакате да се земе нешто
надвор, бидејќи ако големината не е

177
00:08:25,350 --> 00:08:27,620
поголем од нула, тогаш
немаш ништо во магацинот.

178
00:08:27,620 --> 00:08:29,840
>> Па вие само сакате да се изврши
овој законик, тоа само може да

179
00:08:29,840 --> 00:08:32,320
pop ако има нешто од поп музиката.

180
00:08:32,320 --> 00:08:35,830
Па ако големината е поголема
од 0, ние минус големина.

181
00:08:35,830 --> 00:08:40,020
Ние опаѓа големината и потоа да се вратат
она што е во него, бидејќи

182
00:08:40,020 --> 00:08:42,710
со пукање, ние сакаме да
пристап што и да се чуваат

183
00:08:42,710 --> 00:08:45,694
во индексот на врвот на магацинот.

184
00:08:45,694 --> 00:08:46,610
Сè што има смисла?

185
00:08:46,610 --> 00:08:49,693
Ако сум направил вие момци пишувам ова,
би вие момци можат да се напише?

186
00:08:49,693 --> 00:08:52,029

187
00:08:52,029 --> 00:08:53,570
Добро, вие момци можат да се позанимавам со неа.

188
00:08:53,570 --> 00:08:55,252
Не се грижи, ако не го добие.

189
00:08:55,252 --> 00:08:57,460
Ние немаме време да се код
го ова денес, бидејќи ние сме

190
00:08:57,460 --> 00:08:59,959
доби многу на овие структури
да се оди преку, но во суштина

191
00:08:59,959 --> 00:09:02,214
pseudocode, многу, многу слични да им помогнам.

192
00:09:02,214 --> 00:09:03,380
Само да го следат заедно логиката.

193
00:09:03,380 --> 00:09:06,092
Бидете сигурни дека ќе се пристапува на сите
карактеристики на вашиот struct правилно.

194
00:09:06,092 --> 00:09:06,574
Да?

195
00:09:06,574 --> 00:09:09,282
>> ПУБЛИКАТА: Дали овие слајдови и
целата оваа работа да биде до денес-носталгичната?

196
00:09:09,282 --> 00:09:11,586
АНДИ Пенг: Секогаш, Да.

197
00:09:11,586 --> 00:09:13,710
Одам да се обиде да го стави
овој горе како еден час после.

198
00:09:13,710 --> 00:09:16,626
Јас ќе мејл Дејвид, Дејвид ќе се обиде да
го стави како еден час по ова.

199
00:09:16,626 --> 00:09:20,040

200
00:09:20,040 --> 00:09:25,470
>> Добро, па потоа да се движиме во оваа друга
прекрасна податоци структура наречена редица.

201
00:09:25,470 --> 00:09:30,140
Како вие момци можат да се види тука,
на дното, за Британците меѓу нас,

202
00:09:30,140 --> 00:09:32,010
сето тоа е една линија.

203
00:09:32,010 --> 00:09:34,680
Така спротивно на она што
мислите дека магацинот е,

204
00:09:34,680 --> 00:09:37,750
задача е токму она што
логично е што мислам дека е.

205
00:09:37,750 --> 00:09:41,914
Се одржува со правилата на FIFO,
кој е прв, а прв.

206
00:09:41,914 --> 00:09:43,705
Ако сте прв
еден во низата, ти си

207
00:09:43,705 --> 00:09:46,230
првиот што
излегува на линијата.

208
00:09:46,230 --> 00:09:49,680
>> Значи она што сакаме да го нарекуваме овој
е dequeueing и enqueueing.

209
00:09:49,680 --> 00:09:52,380
Ако сакаме да додадете нешто
на нашата листа на чекање, ние Стави во ред.

210
00:09:52,380 --> 00:09:55,690
Ако сакаме да dequeue, или да
нешто далеку, ние dequeue.

211
00:09:55,690 --> 00:10:03,350
>> Па истото чувство дека ние сме вид на
создавање елементи фиксна големина кои ги

212
00:10:03,350 --> 00:10:06,500
може да се сместат одредени
работи, но ние исто така може

213
00:10:06,500 --> 00:10:10,100
промени каде што ние сме поставување
параметри внатре од нив

214
00:10:10,100 --> 00:10:13,140
врз основа на тоа каков тип на
функционалност сакаме.

215
00:10:13,140 --> 00:10:16,700
Купишта така, сакавме последните
еден, N за да биде првиот надвор.

216
00:10:16,700 --> 00:10:19,800
Ред е што сакаме првата работа
во да биде првото нешто надвор.

217
00:10:19,800 --> 00:10:22,510

218
00:10:22,510 --> 00:10:26,710
>> Па на struct тип
се дефинира, како што можете да видите,

219
00:10:26,710 --> 00:10:29,470
тоа е малку поинаква
од она што беше на оџакот

220
00:10:29,470 --> 00:10:33,120
затоа што не само што ќе мора да се задржи
следи каде големината е моментално,

221
00:10:33,120 --> 00:10:37,420
ние, исто така, сакаат да ги пратите на главата
како и тоа каде сме сега.

222
00:10:37,420 --> 00:10:39,580
Па мислам дека тоа е полесно
ако јас се подготви ова.

223
00:10:39,580 --> 00:10:53,270
Значи, да се замисли ние го добивме на листа на чекање,
па да речеме на главата е во право тука.

224
00:10:53,270 --> 00:10:55,811

225
00:10:55,811 --> 00:10:58,310
Шефот на линија, ајде
само да се каже дека е таму во моментов,

226
00:10:58,310 --> 00:11:01,809
и ние сакаме да внесете
нешто во редот.

227
00:11:01,809 --> 00:11:04,350
Одам да се јавите големина суштина
е истото што и опашка,

228
00:11:04,350 --> 00:11:06,314
на крајот од каде вашиот ред е.

229
00:11:06,314 --> 00:11:07,730
Да речеме големина е во право тука.

230
00:11:07,730 --> 00:11:14,380

231
00:11:14,380 --> 00:11:18,400
>> Значи, како некој feasibly
внесете нешто во ред?

232
00:11:18,400 --> 00:11:21,000

233
00:11:21,000 --> 00:11:24,130
Што индекс сакаме да се одржи
каде што сакате да го вметнете во.

234
00:11:24,130 --> 00:11:29,320
Ако ова е почетокот на Вашиот
задача и ова е крајот на тоа

235
00:11:29,320 --> 00:11:31,860
или големината на тоа, каде што го правиме
сакате да го додадете следниот објект?

236
00:11:31,860 --> 00:11:32,920
>> ПУБЛИКАТА: [Беззвучен]

237
00:11:32,920 --> 00:11:35,920
АНДИ Пенг: Токму така, сакате да го додадете
во зависност од тоа сте го напишале.

238
00:11:35,920 --> 00:11:37,840
Или ова не е празно или дека не е празно.

239
00:11:37,840 --> 00:11:42,630
Па сакате да го додадете веројатно
тука, бидејќи ако големината is--

240
00:11:42,630 --> 00:11:50,540
доколку овие сите се полни, сакате
за да го додадете во право тука, нели?

241
00:11:50,540 --> 00:11:57,150
>> И така тоа е, додека многу, многу
едноставно, не баш секогаш точни

242
00:11:57,150 --> 00:12:00,690
бидејќи главната разлика
помеѓу редот и магацинот

243
00:12:00,690 --> 00:12:04,350
е дека задача може
всушност, да се манипулира

244
00:12:04,350 --> 00:12:06,980
така што промените на главата
во зависност од каде што сакате

245
00:12:06,980 --> 00:12:08,650
на почетокот на вашиот знак, за почеток.

246
00:12:08,650 --> 00:12:11,900
И како резултат на тоа, вашиот опашка
е исто така се случува да се промени.

247
00:12:11,900 --> 00:12:14,770
И така да ги разгледаме во
овој код во моментов.

248
00:12:14,770 --> 00:12:18,620
Како вие момци исто така беа замолени да
напише на квизот, Стави во ред.

249
00:12:18,620 --> 00:12:22,580
Можеби ќе се зборува низ зошто
одговорот беше она што беше.

250
00:12:22,580 --> 00:12:26,790
>> Не можев сосема одговара на оваа линија на еден,
но во суштина овој дел од кодот

251
00:12:26,790 --> 00:12:29,030
треба да биде во една линија.

252
00:12:29,030 --> 00:12:30,140
Трошат како 30 секунди.

253
00:12:30,140 --> 00:12:33,000
Погледнете, и да видиме зошто
ова е начинот на кој таа е.

254
00:12:33,000 --> 00:12:50,030

255
00:12:50,030 --> 00:12:55,420
>> Многу, многу слични struct, многу, многу
слична структура како и претходните

256
00:12:55,420 --> 00:12:58,090
магацинот освен можеби
една линија код.

257
00:12:58,090 --> 00:13:01,190
И дека една линија код
одредува функционалност.

258
00:13:01,190 --> 00:13:03,900
И тоа навистина го издвојува
редица од оџак.

259
00:13:03,900 --> 00:13:18,510

260
00:13:18,510 --> 00:13:22,010
>> Секој сака да земе прободе
да се објасни причините зошто го

261
00:13:22,010 --> 00:13:24,980
добив оваа комплицирана работа во оваа ситуација?

262
00:13:24,980 --> 00:13:27,845
Гледаме враќањето на нашите
прекрасен модул пријател.

263
00:13:27,845 --> 00:13:31,020
Како вие момци наскоро ќе дојде
да се препознае во програмирање,

264
00:13:31,020 --> 00:13:34,910
речиси во секое време ви треба нешто
да се заврши околу било што,

265
00:13:34,910 --> 00:13:36,850
модул ќе биде начин да го направи тоа.

266
00:13:36,850 --> 00:13:40,510
Па знаејќи дека, дали некој сака
да се обиде објаснувајќи дека линија код?

267
00:13:40,510 --> 00:13:44,060

268
00:13:44,060 --> 00:13:47,507
Да, сите одговори се
прифатени и добредојдени.

269
00:13:47,507 --> 00:13:48,840
ПУБЛИКАТА: Дали сте зборуваме за мене?

270
00:13:48,840 --> 00:13:49,506
АНДИ Пенг: Да.

271
00:13:49,506 --> 00:13:56,200
ПУБЛИКАТА: О, не ми е жал.

272
00:13:56,200 --> 00:14:00,250
АНДИ Пенг: Во ред, па ајде
прошетка низ овој код.

273
00:14:00,250 --> 00:14:03,642
Па кога ќе се обидуваш да се
додадете нешто кон дното,

274
00:14:03,642 --> 00:14:08,510
во прекрасната случај дека шефот случува
да се биде тука, тоа е многу лесно за нас

275
00:14:08,510 --> 00:14:10,960
само да се оди до крај
внесете нешто, нели?

276
00:14:10,960 --> 00:14:14,690
Но целата поента на ред е
дека шефот всушност може динамички

277
00:14:14,690 --> 00:14:17,280
менува во зависност од каде што
сакам самиот почеток на нашиот q за да биде,

278
00:14:17,280 --> 00:14:19,880
и како такво, на опашката
е исто така се случува да се промени.

279
00:14:19,880 --> 00:14:31,100
>> И така се замисли дека ова не беше
на дното, туку ова е листа на чекање.

280
00:14:31,100 --> 00:14:37,900

281
00:14:37,900 --> 00:14:39,330
Да речеме, на главата е во право тука.

282
00:14:39,330 --> 00:14:54,900

283
00:14:54,900 --> 00:14:56,980
Да речеме дека нашата задача изгледа вака.

284
00:14:56,980 --> 00:15:00,190
Ако сакаме да се префрлат во која
на почетокот на линија, е,

285
00:15:00,190 --> 00:15:03,400
Да речеме дека ние се префрли главата
На овој начин и големини тука.

286
00:15:03,400 --> 00:15:07,100
>> Сега сакаме да додадете нешто на
оваа задача, но како што вие момци можат да се види,

287
00:15:07,100 --> 00:15:11,150
тоа не е толку едноставно како што е да се само
додадете она што е по големина

288
00:15:11,150 --> 00:15:13,630
затоа што тогаш ќе ги потрошиме
границите на нашите вистински низа.

289
00:15:13,630 --> 00:15:16,190
Каде би сакале да додадете навистина е тука.

290
00:15:16,190 --> 00:15:18,610
Тоа е убавината на редица
е во тоа што за нас, визуелно го

291
00:15:18,610 --> 00:15:22,380
личи на линија оди вака,
но кога се чуваат во податочна структура,

292
00:15:22,380 --> 00:15:29,370
тие го даде како што е како еден циклус.

293
00:15:29,370 --> 00:15:32,360
Тој вид на се обвива околу
на предниот дел на ист начин

294
00:15:32,360 --> 00:15:34,780
која линија, исто така може да заврши
околу зависност од каде и да

295
00:15:34,780 --> 00:15:36,279
сакате да го почетокот на линијата да биде.

296
00:15:36,279 --> 00:15:38,630
И така, ако ги
погледне надолу тука, ајде

297
00:15:38,630 --> 00:15:40,880
велат дека сакавме да се создаде
функција наречена Стави во ред.

298
00:15:40,880 --> 00:15:43,980
Сакавме да додадете int n во тоа н.

299
00:15:43,980 --> 00:15:49,250
Ако q.size q-- ние ќе го наречеме дека нашите податоци
structure-- ако нашите queue.size не

300
00:15:49,250 --> 00:15:52,520
еднаква на капацитет или ако
тоа е помалку од капацитет,

301
00:15:52,520 --> 00:15:55,120
q.strings е низа во рамките на нашите q.

302
00:15:55,120 --> 00:15:58,380
Ние ќе треба да се постави
дека еднаква q.heads,

303
00:15:58,380 --> 00:16:02,730
кој е во право тука, плус q.size
модул од страна на капацитет, што

304
00:16:02,730 --> 00:16:04,290
заврши ни назад околу тука.

305
00:16:04,290 --> 00:16:08,040
>> Така што во овој пример, индексот
на главата е 1, нели?

306
00:16:08,040 --> 00:16:11,480
На индекс на големина е 0, 1, 2, 3, 4.

307
00:16:11,480 --> 00:16:19,500
За да можеме да се направи 1 плус 4 модул
од страна на нашиот капацитет кој е на 5.

308
00:16:19,500 --> 00:16:20,920
Што ни даде?

309
00:16:20,920 --> 00:16:23,270
Што е индекс, кој
ќе излезе од ова?

310
00:16:23,270 --> 00:16:24,080
>> ПУБЛИКАТА: 0.

311
00:16:24,080 --> 00:16:27,870
>> АНДИ Пенг: 0, што
се случува да биде тука,

312
00:16:27,870 --> 00:16:30,640
и затоа сакаме да биде во можност
да се вметне во право тука.

313
00:16:30,640 --> 00:16:34,730
И така оваа равенка тука вид
од само работи со било кој број

314
00:16:34,730 --> 00:16:36,750
зависност од тоа каде вашиот
главата и вашата големина се.

315
00:16:36,750 --> 00:16:38,541
Ако знаете што тие
работите се, знаеш

316
00:16:38,541 --> 00:16:43,170
точно каде сакате да го вметнете
што и да е, по својата задача.

317
00:16:43,170 --> 00:16:44,640
Дали тоа има смисла за секого?

318
00:16:44,640 --> 00:16:48,560
>> Знам вид на мозокот
закачка особено бидејќи ова

319
00:16:48,560 --> 00:16:50,512
дојдоа во последиците на вашиот квиз.

320
00:16:50,512 --> 00:16:52,220
Но се надевам дека сите
сега може да се разбере

321
00:16:52,220 --> 00:16:57,800
зошто ова решение или ова
функција е начинот на кој таа е.

322
00:16:57,800 --> 00:16:59,840
Секој малку нејасни за тоа?

323
00:16:59,840 --> 00:17:03,471

324
00:17:03,471 --> 00:17:03,970
ВО РЕД.

325
00:17:03,970 --> 00:17:07,109

326
00:17:07,109 --> 00:17:09,970
>> И така сега, ако
сакаше да dequeue, овој

327
00:17:09,970 --> 00:17:15,240
е местото каде нашата глава ќе биде менувањето
затоа што ако ние требаше да dequeue,

328
00:17:15,240 --> 00:17:17,030
ние не ги тргнеме на крајот на q.

329
00:17:17,030 --> 00:17:19,130
Ние сакаме да ги тргнеме на главата, нели?

330
00:17:19,130 --> 00:17:24,260
Па како резултат на тоа, шефот ќе се промени,
и тоа е причината зошто, кога ќе Стави во ред,

331
00:17:24,260 --> 00:17:26,800
вие мора да ги пратите на
каде главата и вашата големина

332
00:17:26,800 --> 00:17:29,450
треба да биде во можност да се вметне
во правилна позиција.

333
00:17:29,450 --> 00:17:32,740
>> И така, кога ќе dequeue,
Јас, исто така го pseudocode надвор.

334
00:17:32,740 --> 00:17:35,480
Се чувствуваат слободни да ако сакате
да се направи обид за кодирање ова.

335
00:17:35,480 --> 00:17:36,980
Сакате да се движат на главата, нели?

336
00:17:36,980 --> 00:17:39,320
Ако сакав да dequeue, јас
ќе се движат на главата над.

337
00:17:39,320 --> 00:17:40,800
Ова ќе биде на чело.

338
00:17:40,800 --> 00:17:45,617
>> И нашите сегашни големина ќе
одземе затоа што ние веќе не

339
00:17:45,617 --> 00:17:46,950
има четири елементи во низата.

340
00:17:46,950 --> 00:17:51,370
Имаме само три, а потоа ние сакаме
да се врати она што беше се чуваат внатре

341
00:17:51,370 --> 00:17:56,260
на главата, бидејќи сакаме да ја искористам оваа
вредност од толку многу слична на магацинот.

342
00:17:56,260 --> 00:17:58,010
Само сте преземање
од некое друго место,

343
00:17:58,010 --> 00:18:01,770
и ќе мора повторно да го пренесе вашиот покажувач
до друго место, како резултат.

344
00:18:01,770 --> 00:18:03,890
Логично, секој следат?

345
00:18:03,890 --> 00:18:05,690
Одлично.

346
00:18:05,690 --> 00:18:10,156
>> Добро, така што ние ќе треба да се зборува малку
повеќе во длабочина за поврзани листи

347
00:18:10,156 --> 00:18:13,280
затоа што ќе биде многу, многу вредни
за вас во текот на оваа недела

348
00:18:13,280 --> 00:18:14,964
psets.

349
00:18:14,964 --> 00:18:17,130
Поврзани листи, како вие момци
да се сетам, сите тие се

350
00:18:17,130 --> 00:18:22,570
се јазли што се јазли на одредени
вредности на двете вредност и покажувач

351
00:18:22,570 --> 00:18:26,290
кои се поврзани заедно
од страна на оние покажувачи.

352
00:18:26,290 --> 00:18:29,880
И така на struct за тоа како
ние создаваме јазол еве ние

353
00:18:29,880 --> 00:18:33,569
имаат int n, што е без оглед на
вредноста во продавница или стринг n

354
00:18:33,569 --> 00:18:35,610
или што и да сакате да го
го нарекуваат, знак ѕвезда о.

355
00:18:35,610 --> 00:18:41,482
Struct јазол ѕвезда, што е покажувачот
што сакате да го имаат во секој јазол,

356
00:18:41,482 --> 00:18:43,690
сте ќе го имаат тоа
покажувачот точка кон следниот.

357
00:18:43,690 --> 00:18:48,207

358
00:18:48,207 --> 00:18:50,040
Ќе мора на шефот
на која е поврзана листа

359
00:18:50,040 --> 00:18:53,140
ќе укажуваат на остатокот од
вредностите така натаму и така натаму

360
00:18:53,140 --> 00:18:55,290
додека не се на крајот да стигне до крајот.

361
00:18:55,290 --> 00:18:58,040
И ова е само последен јазол
случува да не имаат покажувач.

362
00:18:58,040 --> 00:18:59,952
Тоа се случува да се укаже на
нула, а тоа е кога

363
00:18:59,952 --> 00:19:01,910
знаете дека сте го погоди
крајот на вашиот поврзани листа

364
00:19:01,910 --> 00:19:04,076
е кога последен пат го покажувачот
не укажуваат на ништо.

365
00:19:04,076 --> 00:19:06,670

366
00:19:06,670 --> 00:19:10,990
>> Па ние ќе одиме малку повеќе во
длабочина за тоа како еден би веројатно

367
00:19:10,990 --> 00:19:12,400
пребарување на поврзани листа.

368
00:19:12,400 --> 00:19:15,460
Се сеќавам што се некои од
недостатоци на поврзани листи

369
00:19:15,460 --> 00:19:19,340
стихови низа однос пребарувања.

370
00:19:19,340 --> 00:19:22,565
Низа можеш бинарни пребарување, но
Зошто не можете да го направат на поврзани листа?

371
00:19:22,565 --> 00:19:26,834

372
00:19:26,834 --> 00:19:30,320
>> ПУБЛИКАТА: Поради тоа што сите тие се поврзани,
но не сосема знаат каде

373
00:19:30,320 --> 00:19:31,330
[Беззвучен].

374
00:19:31,330 --> 00:19:34,600
>> АНДИ Пенг: Да, токму така се сеќавам
дека брилијантноста на низа

375
00:19:34,600 --> 00:19:37,190
е фактот дека имавме
меморија за случаен пристап, каде што

376
00:19:37,190 --> 00:19:41,580
ако сакав вредност од индексот
шест, јас само може да се каже индекс шест,

377
00:19:41,580 --> 00:19:42,407
ми даде таа вредност.

378
00:19:42,407 --> 00:19:45,240
И тоа е затоа низи се сортирани
во соседни простор на меморија

379
00:19:45,240 --> 00:19:48,020
на едно место, додека
вид на поврзани листи

380
00:19:48,020 --> 00:19:52,820
по случаен избор се прошарани сите околу себе,
и единствениот начин на кој може да се најде еден

381
00:19:52,820 --> 00:19:56,890
е преку покажувач кој ви кажува
на адресата на која што следниот јазол е.

382
00:19:56,890 --> 00:20:00,290
>> Па како резултат на тоа, единствениот начин
за да пребарувате низ поврзани листа

383
00:20:00,290 --> 00:20:01,560
е линеарно пребарување.

384
00:20:01,560 --> 00:20:05,890
Бидејќи јас не знам каде точно
12-та вредност на поврзани листа е,

385
00:20:05,890 --> 00:20:08,780
Морам да напречни интегритет
од кои една поврзана листа

386
00:20:08,780 --> 00:20:12,450
од страна на еден од главата во првиот јазол,
на вториот јазол, на третиот јазол,

387
00:20:12,450 --> 00:20:17,690
сите патот надолу се додека конечно се
за тоа каде тој јазол го барам е.

388
00:20:17,690 --> 00:20:22,110
И така, во таа смисла, барај
на поврзани листа е секогаш n.

389
00:20:22,110 --> 00:20:23,040
Тоа секогаш е n.

390
00:20:23,040 --> 00:20:25,690
Тоа секогаш е во линеарно време.

391
00:20:25,690 --> 00:20:28,470
>> И така го кодот во кои
ние спроведување на оваа, а оваа

392
00:20:28,470 --> 00:20:32,620
е нешто ново за вас, бидејќи вие момци
момци имаат навистина не зборуваше за тоа или кога било

393
00:20:32,620 --> 00:20:35,000
види совети за тоа како да
пребарување низ покажувачи,

394
00:20:35,000 --> 00:20:37,670
па ние ќе одиме преку
ова е многу, многу бавно.

395
00:20:37,670 --> 00:20:40,200
Па пребарување bool, десно,
ајде да замислиме што сакаме

396
00:20:40,200 --> 00:20:42,820
за да се создаде функција наречена
пребарување кој враќа true

397
00:20:42,820 --> 00:20:46,820
ако најде вредност во внатрешноста на поврзани
листа, и таа се враќа false поинаку.

398
00:20:46,820 --> 00:20:50,030
Листа со омилени јазол е
во моментов само на покажувачот

399
00:20:50,030 --> 00:20:52,960
на првата ставка во вашата поврзани листа.

400
00:20:52,960 --> 00:20:56,700
int n е вредноста која сте
бараат во таа листа.

401
00:20:56,700 --> 00:20:58,770
>> Па јазол ѕвезда покажувачот еднаква на листата.

402
00:20:58,770 --> 00:21:00,970
Тоа значи дека ние сме поставување
и создавање на покажувачот

403
00:21:00,970 --> 00:21:03,592
за да се дека првиот јазол во внатрешноста на листата.

404
00:21:03,592 --> 00:21:04,300
Секој со мене?

405
00:21:04,300 --> 00:21:06,530
Значи, ако ние требаше да одат
врати тука, ќе морам

406
00:21:06,530 --> 00:21:13,850
иницијализиран покажувач кој укажува на
шефот на што и да е листа.

407
00:21:13,850 --> 00:21:18,600
>> А потоа, откако ќе се фаќате тука,
додека покажувачот не еднакви нула,

408
00:21:18,600 --> 00:21:22,160
така што е јамка во која се наоѓаме
ќе биде дополнително traversing

409
00:21:22,160 --> 00:21:25,940
остатокот од нашата листа затоа што
се случува кога покажувачот е еднаква на нула?

410
00:21:25,940 --> 00:21:27,550
Ние знаеме дека ние have--

411
00:21:27,550 --> 00:21:28,450
>> ПУБЛИКАТА: [Беззвучен]

412
00:21:28,450 --> 00:21:31,491
>> АНДИ Пенг: Точно, па знаеме дека
ние сме стигнале до крајот на листата, нели?

413
00:21:31,491 --> 00:21:34,470
Ако се вратиме тука, секој јазол
треба да се укажува на друг јазол

414
00:21:34,470 --> 00:21:36,550
и така натаму и така натаму
додека не го погоди на крајот

415
00:21:36,550 --> 00:21:41,589
опашката на вашиот поврзани листа,
која има покажувач дека само

416
00:21:41,589 --> 00:21:43,130
не укажуваат било каде, освен бр.

417
00:21:43,130 --> 00:21:47,510
И така треба да знаете дека во основа
Вашата листа е сеуште таму нагоре

418
00:21:47,510 --> 00:21:50,900
додека покажувачот не е еднакво на
нула затоа што еднаш тоа е еднакво на нула,

419
00:21:50,900 --> 00:21:53,310
знаеш дека нема повеќе нешта.

420
00:21:53,310 --> 00:21:56,930
>> Па тоа е циклус во кој ние сме
ќе имаат вистински пребарување.

421
00:21:56,930 --> 00:22:01,690
А ако pointer-- гледате
тој вид на стрелката функција таму?

422
00:22:01,690 --> 00:22:06,930
Па ако покажувачот поени на n, ако
покажувачот на n еднаква еднаква n,

423
00:22:06,930 --> 00:22:09,180
па тоа значи дека ако
покажувачот дека сте

424
00:22:09,180 --> 00:22:13,420
бараат на крајот на секоја
јазол е всушност еднаков на вредноста

425
00:22:13,420 --> 00:22:15,990
што го барате, а потоа
сакате да се вратите точно.

426
00:22:15,990 --> 00:22:19,280
Значи, во основа, ако сте на еден јазол кој
има вредност која што го барате,

427
00:22:19,280 --> 00:22:23,550
знаете дека сте биле
можност успешно пребарување.

428
00:22:23,550 --> 00:22:27,150
>> Во спротивно, ќе сакате да го поставите
покажувачот на следното јазол.

429
00:22:27,150 --> 00:22:28,850
Тоа е она што таа линија, тука е тоа.

430
00:22:28,850 --> 00:22:31,750
Покажувачот еднаква на покажувачот следната.

431
00:22:31,750 --> 00:22:33,360
Секој се види како тоа е работат?

432
00:22:33,360 --> 00:22:36,580
>> И во суштина си оди за да се само
напречни целината на листата,

433
00:22:36,580 --> 00:22:41,920
ресетирам вашиот покажувач секое време до
ти на крајот хит на крајот на листата.

434
00:22:41,920 --> 00:22:45,030
И знаеш дека не постојат
повеќе јазли за да пребарувате низ,

435
00:22:45,030 --> 00:22:47,999
а потоа можете да се вратите лажна
затоа што знаете дека, добро де,

436
00:22:47,999 --> 00:22:50,540
ако јас сум бил во можност да пребарување
преку севкупноста на листата.

437
00:22:50,540 --> 00:22:54,530
Ако во овој пример, ако сакав
да се погледне за вредност од 10,

438
00:22:54,530 --> 00:22:57,250
и јас со почеток во главата, и
Јас пребарување на целиот пат,

439
00:22:57,250 --> 00:23:00,550
и јас конечно стигнав до оваа, која
покажувач кој укажува на нула,

440
00:23:00,550 --> 00:23:04,415
Знам дека, глупости, претпоставувам дека 10 не е во
оваа листа, бидејќи не можев да го најдам.

441
00:23:04,415 --> 00:23:06,520
И јас сум на крајот на листата.

442
00:23:06,520 --> 00:23:11,040
И во кој случај ќе се знае
Одам да се врати лажни.

443
00:23:11,040 --> 00:23:12,900
>> Дозволувајте тоа да се впие во за малку.

444
00:23:12,900 --> 00:23:17,350
Ова ќе биде убава
важно за вашиот pset.

445
00:23:17,350 --> 00:23:21,140
Логиката на тоа е многу едноставно, можеби
синтаксички само да го спроведат.

446
00:23:21,140 --> 00:23:23,365
Вие момци сакаат да направат
сигурни дека ќе се разбере.

447
00:23:23,365 --> 00:23:25,870

448
00:23:25,870 --> 00:23:27,650
Кул.

449
00:23:27,650 --> 00:23:32,560
>> Ok, па како ние би биле
вметнување јазли, десно,

450
00:23:32,560 --> 00:23:35,380
во листата, бидејќи се сеќавам
Кои се придобивките од она што

451
00:23:35,380 --> 00:23:39,230
на постоење на поврзани листа наспроти
низа во однос на чување?

452
00:23:39,230 --> 00:23:41,110
>> ПУБЛИКАТА: Тоа е динамичен,
така што е полесно to--

453
00:23:41,110 --> 00:23:43,180
>> АНДИ Пенг: Токму така,
така што е динамично што

454
00:23:43,180 --> 00:23:46,880
значи дека може да се прошири и да се намали
во зависност од потребите на корисникот.

455
00:23:46,880 --> 00:23:56,570
И така, во таа смисла, ние не треба
да губите непотребни меморија, бидејќи јас

456
00:23:56,570 --> 00:24:00,850
ако не знам колку вредности сакам
до продавница, тоа не дава никаква смисла за мене

457
00:24:00,850 --> 00:24:04,310
да се создаде низа бидејќи
ако сакам да се сместат 10 вредности

458
00:24:04,310 --> 00:24:08,380
и јас се создаде низа на 1.000, што е
многу потроши меморија распределени.

459
00:24:08,380 --> 00:24:11,180
Тоа е причината зошто ние сакаме да се користи во врска
листа за да бидат во можност да се динамички

460
00:24:11,180 --> 00:24:13,860
се менува или да се намали нашата големина.

461
00:24:13,860 --> 00:24:17,040
>> И така што го прави вметнување
малку посложена.

462
00:24:17,040 --> 00:24:20,810
Бидејќи ние не може случајно да пристапите елементи
начинот на кој ние би на низа.

463
00:24:20,810 --> 00:24:24,270
Ако сакам да се вметне елемент
во седмата индекс,

464
00:24:24,270 --> 00:24:26,930
Јас само може да го вметнете
во седмата индекс.

465
00:24:26,930 --> 00:24:30,020
На поврзани листа, тоа не го прави тоа
доста работи како лесно,

466
00:24:30,020 --> 00:24:34,947
и така, ако сакавме да го вметнете
Од една тука во поврзани листа,

467
00:24:34,947 --> 00:24:36,280
визуелно, тоа е многу лесно да се види.

468
00:24:36,280 --> 00:24:39,363
Ние само сакаме да го вметнете во право, таму,
правото на почетокот на листата,

469
00:24:39,363 --> 00:24:40,840
веднаш по главата.

470
00:24:40,840 --> 00:24:44,579
>> Но начинот на кој ние треба да го распореди
покажувачи е малку згрчена

471
00:24:44,579 --> 00:24:47,620
или, логично, тоа го прави смисла, но
вие сакате да бидете сигурни дека можете да го имаат

472
00:24:47,620 --> 00:24:50,250
целосно надолу, бидејќи
последно нешто што сакате

473
00:24:50,250 --> 00:24:52,990
е да го распореди на покажувачот
начинот на кој што го правиме тука.

474
00:24:52,990 --> 00:24:58,170
Ако dereference на
покажувачот од глава до 1,

475
00:24:58,170 --> 00:25:01,086
потоа одеднаш на
остатокот од вашата поврзани листа

476
00:25:01,086 --> 00:25:04,680
е изгубена, бидејќи не сте, всушност,
креира привремен ништо.

477
00:25:04,680 --> 00:25:06,220
Кој укажа на 2.

478
00:25:06,220 --> 00:25:10,080
Ако го преназначаване на покажувачот, тогаш
остатокот од вашата листа е целосно изгубена.

479
00:25:10,080 --> 00:25:13,310
Значи сакате да бидете
многу, многу внимателен тука

480
00:25:13,310 --> 00:25:17,010
прво да му ја додели на
покажувачот од она што ќе го

481
00:25:17,010 --> 00:25:20,150
сакате да го вметнете во каде и
што го сакате, а потоа ќе

482
00:25:20,150 --> 00:25:22,710
може dereference остатокот од вашата листа.

483
00:25:22,710 --> 00:25:25,250
>> Така ова се однесува за каде
ќе се обидуваш да се вметне во.

484
00:25:25,250 --> 00:25:27,520
Ако сакате да го вметнете во
главата, ако сакате да се одговори тука,

485
00:25:27,520 --> 00:25:29,455
ако сакате да ги внесете во
На крајот, и, на крајот јас

486
00:25:29,455 --> 00:25:30,910
Претпоставувам дека би само
Немате покажувач, но вие

487
00:25:30,910 --> 00:25:33,830
сакате да бидете сигурни дека ќе не направи
изгуби остатокот од вашата листа.

488
00:25:33,830 --> 00:25:36,640
Вие секогаш сакате да бидете сигурни дека
Вашиот нов јазол е да се покажува

489
00:25:36,640 --> 00:25:39,330
кон она што
сакате да го вметнете во,

490
00:25:39,330 --> 00:25:42,170
а потоа можете да го додадете врзувањето на.

491
00:25:42,170 --> 00:25:43,330
Секој јасно?

492
00:25:43,330 --> 00:25:45,427
>> Ова се случува да биде
еден од вистинските прашања.

493
00:25:45,427 --> 00:25:48,010
Еден од повеќето големи проблеми
ви се случува да имате на вашиот pset

494
00:25:48,010 --> 00:25:51,340
е дека си оди за да се обиде да создаде
на поврзани листа и вметнете работи

495
00:25:51,340 --> 00:25:53,340
но тогаш едноставно изгуби
остатокот од вашата поврзани листа.

496
00:25:53,340 --> 00:25:54,900
И ви се случува да се биде како, јас
не знам зошто ова се случува?

497
00:25:54,900 --> 00:25:58,040
И тоа е болката да се оди преку
и пребарување на сите ваши покажувачи.

498
00:25:58,040 --> 00:26:02,100
>> И јас ви гарантирам на овој pset,
пишување и цртање овие јазли надвор

499
00:26:02,100 --> 00:26:03,344
ќе биде многу, многу корисни.

500
00:26:03,344 --> 00:26:06,010
Па не може целосно да ги пратите
од каде што сите ваши покажувачи се,

501
00:26:06,010 --> 00:26:08,540
она што се случува во ред,
каде сите ваши јазли,

502
00:26:08,540 --> 00:26:12,660
она што треба да направите за да пристапите или
вметнете или бришење или било кој од нив.

503
00:26:12,660 --> 00:26:14,550
Секој добар во тоа?

504
00:26:14,550 --> 00:26:15,050
Кул.

505
00:26:15,050 --> 00:26:19,300

506
00:26:19,300 --> 00:26:22,600
>> Значи, ако сакаме да се погледне на кодот?

507
00:26:22,600 --> 00:26:24,470
О, јас не знам дали ние
може да се види the-- ОК, значи

508
00:26:24,470 --> 00:26:27,940
на врвот на сите што е е во функција
именуван вметнете каде сакаме

509
00:26:27,940 --> 00:26:31,365
за да вметнете int n во поврзаните листа.

510
00:26:31,365 --> 00:26:32,740
Ние ќе треба да се оди преку ова.

511
00:26:32,740 --> 00:26:34,770
Тоа е многу код, многу нови синтакса.

512
00:26:34,770 --> 00:26:36,220
Ќе биде во ред.

513
00:26:36,220 --> 00:26:39,120
>> Па на врвот, секогаш кога
ние сакаме да се создаде ништо

514
00:26:39,120 --> 00:26:42,380
што ни е потребно да се направи, особено ако
сакате тоа да не бидат зачувани на оџакот

515
00:26:42,380 --> 00:26:43,920
но во грамада?

516
00:26:43,920 --> 00:26:45,460
Одиме во Примерок, нели?

517
00:26:45,460 --> 00:26:48,240
Па ние ќе се создаде покажувачот.

518
00:26:48,240 --> 00:26:52,074
Јазол, покажувач, нови еднаквите
Примерок од големината на еден јазол

519
00:26:52,074 --> 00:26:53,740
затоа што ние сакаме тој јазол да биде создадена.

520
00:26:53,740 --> 00:26:56,720
Ние сакаме на износот на
меморија што еден јазол зазема

521
00:26:56,720 --> 00:26:59,300
што треба да се распределени за
создавањето на новиот јазол.

522
00:26:59,300 --> 00:27:02,270
>> И тогаш ние ќе треба да се провери да се
види дали новиот еднаквите еднакво на нула.

523
00:27:02,270 --> 00:27:03,370
Се сеќавам она што го кажавме?

524
00:27:03,370 --> 00:27:06,470
Што и да Примерок,
она што мора секогаш да направам?

525
00:27:06,470 --> 00:27:09,490
Треба секогаш да се провери да се види
дали или не тој е нула.

526
00:27:09,490 --> 00:27:13,620
>> На пример, ако вашиот оперативен
системот е целосно полна,

527
00:27:13,620 --> 00:27:17,060
ако нема повеќе меморија на
сите и ќе се обидат да Примерок,

528
00:27:17,060 --> 00:27:18,410
тоа ќе се врати нула за вас.

529
00:27:18,410 --> 00:27:21,094
И така, ако се обидете да го користите
кога беше укажува на нула,

530
00:27:21,094 --> 00:27:23,260
вие нема да се во можност
за пристап до тие информации.

531
00:27:23,260 --> 00:27:27,010
И така, како такви, сакавме да се направи
Осигурајте се дека кога сте mallocing,

532
00:27:27,010 --> 00:27:30,500
ти си секогаш проверка за да види дали
тој спомен на тебе е нула.

533
00:27:30,500 --> 00:27:33,670
И ако тоа не е, тогаш може да се движи
на со остатокот од нашиот код.

534
00:27:33,670 --> 00:27:36,140
>> Па ние ќе треба да
иницијализира на новиот јазол.

535
00:27:36,140 --> 00:27:39,050
Ние ќе треба да се направи нов n еднаква на n.

536
00:27:39,050 --> 00:27:42,390
И тогаш ние ќе треба да се направи
постави нови покажувачот на нови

537
00:27:42,390 --> 00:27:46,900
на нула, бидејќи во моментов ние не
сакам ништо за тоа да се насочува.

538
00:27:46,900 --> 00:27:48,755
Немаме поим каде
тоа се случува да се стави,

539
00:27:48,755 --> 00:27:50,630
а потоа, ако сакаме да
вметнете ја во главата,

540
00:27:50,630 --> 00:27:53,820
тогаш можеме да преназначаване
покажувачот на главата.

541
00:27:53,820 --> 00:27:58,530
Дали секој следат логиката
од каде што се случува?

542
00:27:58,530 --> 00:28:02,502
>> Сите ние сме прави е создавање на нов
јазли, поставување на покажувачот на нула,

543
00:28:02,502 --> 00:28:04,210
а потоа и прераспределување
тоа на главата ако ние

544
00:28:04,210 --> 00:28:06,320
Знаеме дека сакате да го вметнете во главата.

545
00:28:06,320 --> 00:28:09,420
А потоа на главата ќе
точка кон тој нов јазол.

546
00:28:09,420 --> 00:28:11,060
Секој ред со тоа?

547
00:28:11,060 --> 00:28:12,380
>> Така, тоа е процес од два чекори.

548
00:28:12,380 --> 00:28:14,760
Имаш да се Прво доделете
она што ќе го создаде.

549
00:28:14,760 --> 00:28:18,260
Во собата што покажувачот на
повикување, а потоа ќе

550
00:28:18,260 --> 00:28:21,400
да вид на dereference
првиот покажувач

551
00:28:21,400 --> 00:28:22,972
и насочете го кон нов јазол.

552
00:28:22,972 --> 00:28:25,680
Каде сакате да го вметнете,
таа логика ќе се одржи точно.

553
00:28:25,680 --> 00:28:27,530
>> Тоа е вид на како доделување
привремени променливи.

554
00:28:27,530 --> 00:28:28,700
Се сеќавам, имаш
за да бидете сигурни дека ќе

555
00:28:28,700 --> 00:28:30,346
не се изгуби патеката на ако сте Замена.

556
00:28:30,346 --> 00:28:33,470
Вие сакате да бидете сигурни дека ќе имаат
привремена променлива таква држи

557
00:28:33,470 --> 00:28:35,620
следи каде што нешто
се чуваат, така што ќе

558
00:28:35,620 --> 00:28:41,190
не губат било која вредност во текот
на како Месинг околу со него.

559
00:28:41,190 --> 00:28:42,710
>> Добро, така што кодот ќе биде тука.

560
00:28:42,710 --> 00:28:45,020
Вие момци ги разгледаме по дел.

561
00:28:45,020 --> 00:28:48,060
Тоа ќе биде таму.

562
00:28:48,060 --> 00:28:50,280
>> Па претпоставувам колку чини
ова се разликуваат, ако сакавме

563
00:28:50,280 --> 00:28:52,300
да се вметне во средината или на крајот?

564
00:28:52,300 --> 00:28:57,892
Дали некој има идеја за она што е
pseudocode како логична референца

565
00:28:57,892 --> 00:29:00,350
дека ќе ги преземе ако сакавме
за да го внесеш во средината?

566
00:29:00,350 --> 00:29:03,391
Значи, ако сакаме да го вметнете во
шеф, сите ние го правиме е да се создаде нов јазол.

567
00:29:03,391 --> 00:29:06,311
Ние го поставите покажувачот на таа
нов јазол на она што на главата,

568
00:29:06,311 --> 00:29:08,310
а потоа во собата на главата
на новиот јазол, нели?

569
00:29:08,310 --> 00:29:11,560
Ако сакавме да го внесеш во средината
на листата, што ќе имаме да се направи?

570
00:29:11,560 --> 00:29:14,108

571
00:29:14,108 --> 00:29:16,110
>> ПУБЛИКАТА: Тоа би уште
биде сличен процес

572
00:29:16,110 --> 00:29:19,114
на, како и доделување на покажувачот
тогаш назначување дека покажувач,

573
00:29:19,114 --> 00:29:20,530
но ќе треба да се лоцира таму.

574
00:29:20,530 --> 00:29:23,560
>> АНДИ Пенг: Точно, токму така
истиот процес, освен тебе

575
00:29:23,560 --> 00:29:27,820
мора да се лоцира каде точно
сакаат дека новите покажувачот да одат во,

576
00:29:27,820 --> 00:29:44,790
па ако сакам да го вметнете во
средината на поврзани list-- ред,

577
00:29:44,790 --> 00:29:46,370
ајде да речеме дека е наша поврзани листа.

578
00:29:46,370 --> 00:29:49,500
Ако сакаме да го внесеш токму тука,
ние ќе треба да се создаде нов јазол.

579
00:29:49,500 --> 00:29:50,520
Ние ќе треба да Примерок.

580
00:29:50,520 --> 00:29:52,220
Ние ќе треба да се создаде нов јазол.

581
00:29:52,220 --> 00:29:55,940
Ние ќе треба да му ја додели на
покажувачот на овој јазол тука.

582
00:29:55,940 --> 00:29:58,335
>> Но, проблемот кој се разликува
од каде што главата е

583
00:29:58,335 --> 00:30:00,490
е дека ние точно знаел
која главата е.

584
00:30:00,490 --> 00:30:01,930
Дека тоа е правото на првото, нели?

585
00:30:01,930 --> 00:30:04,870
Но тука ние мора да ги пратите
од каде што ние сме вметнување во.

586
00:30:04,870 --> 00:30:07,930
Ако ние се нашата вметнување
јазол тука, ние го добивме

587
00:30:07,930 --> 00:30:12,270
за да бидете сигурни дека на
една тема на овој јазол

588
00:30:12,270 --> 00:30:14,172
е онаа која reassigns покажувачот.

589
00:30:14,172 --> 00:30:16,380
Па тогаш мора да се вид на
ги пратите на две работи.

590
00:30:16,380 --> 00:30:19,420
Ако ги пратите на тоа каде тоа
јазол во моментов е вметнување во.

591
00:30:19,420 --> 00:30:23,280
Можете исто така треба да ги пратите на тоа каде
претходниот јазол дека сте во потрага на

592
00:30:23,280 --> 00:30:24,340
исто така беше таму.

593
00:30:24,340 --> 00:30:25,830
Секој добар во тоа?

594
00:30:25,830 --> 00:30:26,500
ВО РЕД.

595
00:30:26,500 --> 00:30:28,000
>> Како за ставање во крајот?

596
00:30:28,000 --> 00:30:34,220
Ако сакав да го додадете here-- ако сакав
за да додадете нов јазол до крајот на листата,

597
00:30:34,220 --> 00:30:37,009
како би можел да се обратите за тоа го прават?

598
00:30:37,009 --> 00:30:39,300
ПУБЛИКАТА: Значи, во моментов,
Последната укажувале ништовни.

599
00:30:39,300 --> 00:30:40,960
АНДИ Пенг: Да.

600
00:30:40,960 --> 00:30:43,560
Точно, така што ова
во моментов е насочен да се знае,

601
00:30:43,560 --> 00:30:46,720
и така претпоставувам, во оваа смисла, тоа е
многу лесно да додадете до крајот на листата.

602
00:30:46,720 --> 00:30:51,810
Се што треба да направите е да го поставите
еднакви на нула, а потоа бум.

603
00:30:51,810 --> 00:30:53,070
Право, таму, многу лесно.

604
00:30:53,070 --> 00:30:53,960
Многу едноставна.

605
00:30:53,960 --> 00:30:56,430
>> Многу сличен на
главата, но логично вас

606
00:30:56,430 --> 00:30:59,690
сакате да бидете сигурни дека чекорите
ве однесе кон правење било од тоа,

607
00:30:59,690 --> 00:31:01,500
ти си по должината.

608
00:31:01,500 --> 00:31:04,420
Тоа е многу лесно да се, во средината
на вашиот код, да се фатат за,

609
00:31:04,420 --> 00:31:05,671
ох, имам толку многу покажувачи.

610
00:31:05,671 --> 00:31:07,461
Не знам каде
нешто е да се покажува.

611
00:31:07,461 --> 00:31:09,170
Јас дури и не знаат кој јазол јас сум на.

612
00:31:09,170 --> 00:31:11,490
Што се случува?

613
00:31:11,490 --> 00:31:13,620
>> Релаксираат, се смири, земе длабок здив.

614
00:31:13,620 --> 00:31:15,530
Извлече вашата поврзани листа.

615
00:31:15,530 --> 00:31:18,800
Ако ти кажам, знам каде точно
Јас треба да го вметнете ова во

616
00:31:18,800 --> 00:31:22,970
и знам точно како да го распореди на мојот
покажувачи, многу, многу полесно да се слика

617
00:31:22,970 --> 00:31:27,200
out-- многу, многу полесно да не
да се изгуби во грешки на вашиот код.

618
00:31:27,200 --> 00:31:29,410
Секој ред со тоа?

619
00:31:29,410 --> 00:31:31,380
ВО РЕД.

620
00:31:31,380 --> 00:31:35,120
>> Па претпоставувам концепт кој не сме
навистина разговаравме за пред сега,

621
00:31:35,120 --> 00:31:38,131
и јас ќе се погоди веројатно
не ќе се судрите со многу yet--

622
00:31:38,131 --> 00:31:40,880
тоа е вид на напредна concept--
е дека ние, всушност, имаат податоци

623
00:31:40,880 --> 00:31:43,900
структура наречена двојно поврзана листата.

624
00:31:43,900 --> 00:31:46,390
Така што вие момци можат да се види,
сите ние сме прави е создавање

625
00:31:46,390 --> 00:31:50,400
вистинска вредност, екстра
покажувачот на секоја од нашите јазли

626
00:31:50,400 --> 00:31:52,660
што исто така укажува на претходниот јазол.

627
00:31:52,660 --> 00:31:58,170
Затоа, не само што имаме нашите
јазли укажуваат на следниот.

628
00:31:58,170 --> 00:32:01,430
Тие, исто така, укажуваат на претходниот.

629
00:32:01,430 --> 00:32:04,310
Одам да ги игнорира овие две моментов.

630
00:32:04,310 --> 00:32:06,740
>> Па тогаш имате синџир
кои можат да се движат во двете насоки,

631
00:32:06,740 --> 00:32:09,630
и тогаш тоа е малку полесно
да логично следат заедно.

632
00:32:09,630 --> 00:32:11,896
Како тука, наместо
следење на, ох, се

633
00:32:11,896 --> 00:32:14,520
Треба да знаете дека овој јазол е
оној што морам да го распореди,

634
00:32:14,520 --> 00:32:17,532
Јас само може да оди тука и
само се повлече претходната.

635
00:32:17,532 --> 00:32:19,490
Тогаш знам точно каде
што е, а потоа ќе

636
00:32:19,490 --> 00:32:21,130
немора да напречни
целината на поврзани листа.

637
00:32:21,130 --> 00:32:22,180
Тоа е малку полесно.

638
00:32:22,180 --> 00:32:24,960
>> Но, како што се, ќе мора двојно
износот на покажувачи,

639
00:32:24,960 --> 00:32:26,960
што е двојно повеќе од количината на меморија.

640
00:32:26,960 --> 00:32:28,950
Тоа е многу совети како да ги пратите.

641
00:32:28,950 --> 00:32:32,140
Тоа е малку посложена, но тоа е
малку повеќе корисник пријателски зависност

642
00:32:32,140 --> 00:32:34,080
на она што се обидуваат да се постигне.

643
00:32:34,080 --> 00:32:36,910
>> Значи овој тип на податоци
структура сосема постои,

644
00:32:36,910 --> 00:32:40,280
и структурата за е многу, многу
едноставна освен сите што си имаат е,

645
00:32:40,280 --> 00:32:43,850
наместо само покажувач на следниот,
можете исто така имаат покажувач на претходната.

646
00:32:43,850 --> 00:32:45,940
Тоа е се што разликата беше.

647
00:32:45,940 --> 00:32:47,740
Секој добар во тоа?

648
00:32:47,740 --> 00:32:48,240
Кул.

649
00:32:48,240 --> 00:32:50,940

650
00:32:50,940 --> 00:32:53,280
>> Добро, па сега сум
навистина да поминат веројатно

651
00:32:53,280 --> 00:32:56,870
како и од 15 до 20 минути, или најголемиот дел
на остатокот од времето во делот

652
00:32:56,870 --> 00:32:58,360
Станува збор за хаш маси.

653
00:32:58,360 --> 00:33:02,590
Колкумина од вас момци
Ги прочитав pset5 спецификации?

654
00:33:02,590 --> 00:33:03,620
Добро, добро.

655
00:33:03,620 --> 00:33:06,160
Тоа е поголем од 50% од нормално.

656
00:33:06,160 --> 00:33:07,560
Во ред е.

657
00:33:07,560 --> 00:33:10,345
>> Така што вие момци ќе видиме,
ти си предизвик во pset5

658
00:33:10,345 --> 00:33:16,790
ќе биде да спроведе речникот
каде што ќе се вчита над 140.000 зборови

659
00:33:16,790 --> 00:33:20,610
што ние ви даде или проверка на правопис
тоа против сите на текстот.

660
00:33:20,610 --> 00:33:22,580
Ние ќе ви дадеме случаен
парчиња на литературата.

661
00:33:22,580 --> 00:33:23,520
Ние ќе ви дадеме Одисеја.

662
00:33:23,520 --> 00:33:24,561
Ние ќе ви дадеме Илијада.

663
00:33:24,561 --> 00:33:26,350
Ние ќе ви дадеме Остин сили.

664
00:33:26,350 --> 00:33:28,220
>> И вашиот предизвик
ќе биде да се проверка на правопис

665
00:33:28,220 --> 00:33:31,760
секој еден збор во сите
на оние речници

666
00:33:31,760 --> 00:33:34,960
во суштина со нашите проверува правописот.

667
00:33:34,960 --> 00:33:38,620
И така има неколку делови
на создавање на овој pset,

668
00:33:38,620 --> 00:33:41,970
прво што сакате да биде
можност да всушност се вчита

669
00:33:41,970 --> 00:33:43,970
сите зборови во вашиот
речникот, а потоа ќе

670
00:33:43,970 --> 00:33:45,530
сакаат да бидат во можност да
проверка на правописот сите од нив.

671
00:33:45,530 --> 00:33:48,780
И така како што се, ви се случува да се бара
структура на податоци што може да го направите ова брзо

672
00:33:48,780 --> 00:33:50,790
и ефикасно и динамично.

673
00:33:50,790 --> 00:33:52,900
>> Па претпоставувам најлесниот
начин да го направите ова,

674
00:33:52,900 --> 00:33:55,010
најверојатно, ќе се создаде низа, нели?

675
00:33:55,010 --> 00:33:58,910
Најлесен начин на чување на вас е
може да се создаде низа на 140.000 зборови

676
00:33:58,910 --> 00:34:03,400
и само да ги ставите сите таму и
потоа да ги напречни преку бинарни пребарување

677
00:34:03,400 --> 00:34:06,780
или со селекции или not--
Жал ми е што го средат.

678
00:34:06,780 --> 00:34:10,729
Може да ги подредувате и потоа да ги напречни
со бинарна пребарување или само линеарно пребарување

679
00:34:10,729 --> 00:34:13,730
и само во финалето на зборови, туку дека
зема огромна сума на меморија,

680
00:34:13,730 --> 00:34:15,190
и тоа не е многу ефикасен.

681
00:34:15,190 --> 00:34:18,350
>> И така ние се случува да започне
Станува збор за начини за правење

682
00:34:18,350 --> 00:34:20,110
нашето време работи поефикасно.

683
00:34:20,110 --> 00:34:23,190
И нашата цел е да се добие
постојана време каде

684
00:34:23,190 --> 00:34:25,810
тоа е речиси како низи, каде
имате моментален пристап.

685
00:34:25,810 --> 00:34:28,560
Ако сакав да барате ништо,
Сакам да бидам во можност да само,

686
00:34:28,560 --> 00:34:30,810
бум, таа се најде точно, и извлечете ја.

687
00:34:30,810 --> 00:34:34,100
И така структура во која
ние ќе се станува многу блиску

688
00:34:34,100 --> 00:34:37,569
за да биде во можност за пристап до постојана
време, овој светиот грал

689
00:34:37,569 --> 00:34:41,370
во програмирање на постојана
време се нарекува хаш табелата.

690
00:34:41,370 --> 00:34:45,370
И така Давид претходно рековме на
[Беззвучен] малку во предавањето,

691
00:34:45,370 --> 00:34:49,100
но ние се случува да навистина
нурне длабоко во оваа недела

692
00:34:49,100 --> 00:34:51,780
на парче што е во врска со
како хаш табелата работи.

693
00:34:51,780 --> 00:34:53,949
>> Па начинот на кој хаш
маса дела, на пример,

694
00:34:53,949 --> 00:35:00,230
ако сакав да ја запази еден куп на зборови,
куп на зборови во англискиот јазик,

695
00:35:00,230 --> 00:35:02,940
Јас теоретски би можеле да се стави
банана, јаболко, киви, манго, пар,

696
00:35:02,940 --> 00:35:04,980
и диња сите на само низа.

697
00:35:04,980 --> 00:35:07,044
Сите тие може да се вклопат во и да се најде.

698
00:35:07,044 --> 00:35:09,210
Тоа би било вид на болка да се
пребарување и пристап,

699
00:35:09,210 --> 00:35:12,920
но на полесен начин да се направи ова е
дека ние, всушност, може да се создаде структура

700
00:35:12,920 --> 00:35:15,680
вика хаш табелата, каде што хаш.

701
00:35:15,680 --> 00:35:19,880
Трчаме сите наши клучеви преку
хеш функција, равенка,

702
00:35:19,880 --> 00:35:22,600
дека сите ги претвора во
некој вид на вредност

703
00:35:22,600 --> 00:35:28,740
кој потоа ќе можеме да ги чувате со излез
суштина низа на поврзани листа.

704
00:35:28,740 --> 00:35:32,570
>> И така тука, ако сакавме
за чување на англиски зборови,

705
00:35:32,570 --> 00:35:37,250
ние потенцијално би можеле само, јас не
Знаете, се претвори сите на првите букви

706
00:35:37,250 --> 00:35:39,630
во некој вид на број.

707
00:35:39,630 --> 00:35:43,140
И така, на пример, ако сакав
А за да биде синоним за apple--

708
00:35:43,140 --> 00:35:47,460
или со индекс на 0, и
Б да биде синоним за 1,

709
00:35:47,460 --> 00:35:51,030
може да имаме 26 записи
дека само може да се сместат

710
00:35:51,030 --> 00:35:53,610
сите букви од
писмо дека ќе се започне со.

711
00:35:53,610 --> 00:35:56,130
И тогаш можеме да имаме
јаболко на индексот на 0.

712
00:35:56,130 --> 00:35:59,160
Ние може да има банана на индексот на
1, диња во индексот на 2,

713
00:35:59,160 --> 00:36:00,540
и така натаму и така натаму.

714
00:36:00,540 --> 00:36:04,460
А со тоа и да сакав да го бара
мојата хаш табелата и пристап јаболко,

715
00:36:04,460 --> 00:36:07,560
Знам дека Apple ќе почне со
А, и знам точно

716
00:36:07,560 --> 00:36:10,860
дека мора да биде и на хаш
маса во индекс 0, бидејќи

717
00:36:10,860 --> 00:36:13,620
на функцијата претходно доделени.

718
00:36:13,620 --> 00:36:16,572
>> Па не знам, ние сме
програма во која корисникот

719
00:36:16,572 --> 00:36:18,780
ќе биде обвинет
не arbitrarily-- произволно,

720
00:36:18,780 --> 00:36:22,530
со обидот да се смислено
мислам на добар равенки

721
00:36:22,530 --> 00:36:25,460
за да може да се шири
од сите на вашите вредности

722
00:36:25,460 --> 00:36:29,370
на некој начин тие можат лесно да пристапите
тоа подоцна со како равенка

723
00:36:29,370 --> 00:36:31,130
кои ви се, себе си, знам.

724
00:36:31,130 --> 00:36:35,210
Па во таа смисла, ако сакав да се оди на
манго, знам, ох, тоа започнува со м.

725
00:36:35,210 --> 00:36:37,134
Тоа мора да биде на листата на 12.

726
00:36:37,134 --> 00:36:38,800
Јас не мора да пребарувате низ ништо.

727
00:36:38,800 --> 00:36:42,080
Знам exactly-- јас само може да оди на
индексот на 12 и повлечете тоа.

728
00:36:42,080 --> 00:36:45,520
>> Сите јасни за тоа како еден
функција хаш табелата е работи?

729
00:36:45,520 --> 00:36:48,380
Тоа е вид на само една покомплексна низа.

730
00:36:48,380 --> 00:36:50,010
Тоа е се што и да е.

731
00:36:50,010 --> 00:36:51,630
ВО РЕД.

732
00:36:51,630 --> 00:36:57,690
>> Па претпоставувам дека трчаме во
ова прашање на она што

733
00:36:57,690 --> 00:37:06,390
се случува ако имаш повеќе работи
кои ви даде истиот индекс?

734
00:37:06,390 --> 00:37:10,570
Така велат нашите функција, сето тоа
го направив беше да се земе дека првата буква

735
00:37:10,570 --> 00:37:14,490
и се претвори дека во
соодветните 0 преку 25 индекс.

736
00:37:14,490 --> 00:37:17,137
Тоа е сосема во ред, ако
имате само една на секој.

737
00:37:17,137 --> 00:37:18,970
Но, во втората ќе почнете
има повеќе, ти си

738
00:37:18,970 --> 00:37:20,910
случува да имаат она што се нарекува судир.

739
00:37:20,910 --> 00:37:25,580
>> Значи, ако јас се обидувам да внесете го закопа во хаш
маса која веќе има банана на неа,

740
00:37:25,580 --> 00:37:27,870
што ќе се случи кога
ќе се обидат да се вметне тоа?

741
00:37:27,870 --> 00:37:30,930
Лоши работи затоа банана
веќе постои во рамките на индексот

742
00:37:30,930 --> 00:37:33,800
што сакате да го складирате во.

743
00:37:33,800 --> 00:37:35,560
Бери вид е како, ах, она што можам да направам?

744
00:37:35,560 --> 00:37:37,080
Не знам каде да одат.

745
00:37:37,080 --> 00:37:38,410
Како можам да се реши тоа?

746
00:37:38,410 --> 00:37:41,150
>> И така ќе ви момци вид на
види го правиме тоа слабо нешто

747
00:37:41,150 --> 00:37:44,810
секаде каде што можеме, всушност вид на
создаде поврзани листа во нашата низи.

748
00:37:44,810 --> 00:37:46,840
И така најлесно
да се размислува за тоа,

749
00:37:46,840 --> 00:37:50,830
сите хаш табелата е
низа на поврзани листи.

750
00:37:50,830 --> 00:37:55,670
И така, во таа смисла, треба да
оваа прекрасна низа од покажувачи,

751
00:37:55,670 --> 00:37:58,740
а потоа секој покажувачот во
таа вредност, во тој индекс,

752
00:37:58,740 --> 00:38:00,740
всушност, може да укажуваат на други работи.

753
00:38:00,740 --> 00:38:05,720
И за да можете да ги имаат сите овие одделни
Синџири излетаат на една голема низа.

754
00:38:05,720 --> 00:38:07,960
>> И така тука, ако можам
сакаше да внесете Бери,

755
00:38:07,960 --> 00:38:11,220
Јас знам, во ред, јас ќе одам да го внесете
тоа преку мојот хеш функција.

756
00:38:11,220 --> 00:38:15,070
Одам да се заокружи со индексот на
1, а потоа јас ќе одам да се биде во можност да имаат

757
00:38:15,070 --> 00:38:20,410
само еден помал подмножество на овој
гигант 140.000 збор речникот.

758
00:38:20,410 --> 00:38:24,220
И јас тогаш може само да се погледне
преку 1/26 од тоа.

759
00:38:24,220 --> 00:38:27,910
>> И така, тогаш јас само може да внесете
Бери пред или по банана

760
00:38:27,910 --> 00:38:28,820
во овој случај?

761
00:38:28,820 --> 00:38:29,700
По, нели?

762
00:38:29,700 --> 00:38:33,920
И така ќе се случува да сакаат да
вметнете овој јазол по банана,

763
00:38:33,920 --> 00:38:36,667
и така си оди за да се вметне
на опашката на таа поврзани листа.

764
00:38:36,667 --> 00:38:38,500
Одам да се вратиш
на оваа тема слајд,

765
00:38:38,500 --> 00:38:40,680
па вие момци можат да се види како
хаш функција работи.

766
00:38:40,680 --> 00:38:43,980
>> Па хеш функција е оваа равенка
дека сте водење вид на вашиот влез

767
00:38:43,980 --> 00:38:46,940
преку да добиете она што индекс
што сакате да го доделите насока.

768
00:38:46,940 --> 00:38:51,130
И така, во овој пример, сите сакавме
да направат е да се земе на првата буква,

769
00:38:51,130 --> 00:38:55,890
се претвори дека во индекс, тогаш ние
кои може да се сместат во нашата хеш функција.

770
00:38:55,890 --> 00:39:00,160
Сите што го правиме тука е дека сме
конвертирање на првата буква.

771
00:39:00,160 --> 00:39:04,770
Па keykey [0] е само првата буква
на она што низа што ги имаме,

772
00:39:04,770 --> 00:39:05,720
ние сме поминува во.

773
00:39:05,720 --> 00:39:09,740
Ние сме конвертирање дека на горниот дел, и
ние сме одземање од страна на голема буква А,

774
00:39:09,740 --> 00:39:11,740
така што сите тоа го прави
ни дава голем број

775
00:39:11,740 --> 00:39:13,670
во кој можеме да хаш нашите вредности излез.

776
00:39:13,670 --> 00:39:16,550
>> И тогаш ние ќе треба да
врати хаш модул големина.

777
00:39:16,550 --> 00:39:19,340
Да биде многу, многу внимателно
затоа што, теоретски, тука

778
00:39:19,340 --> 00:39:21,870
Вашиот hash вредност може да биде бесконечна.

779
00:39:21,870 --> 00:39:23,660
Тоа може само да одат на и на и на.

780
00:39:23,660 --> 00:39:26,080
Тоа може да биде некои навистина,
навистина голема вредност,

781
00:39:26,080 --> 00:39:29,849
но бидејќи вашиот хаш табелата што
сте создадени има само 26 индекси,

782
00:39:29,849 --> 00:39:31,890
вие сакате да бидете сигурни дека вашата
modulusing така што ќе

783
00:39:31,890 --> 00:39:33,848
не run-- тоа е истиот
нешто како вашиот queue--

784
00:39:33,848 --> 00:39:36,320
така што не ви се избега на
долниот дел од хаш функција.

785
00:39:36,320 --> 00:39:39,210
>> Сакате да ја заврши назад околу
на ист начин во [Беззвучен] кога

786
00:39:39,210 --> 00:39:41,750
сте имале како многу,
многу големи букви, ќе

787
00:39:41,750 --> 00:39:43,740
не сакате тоа да се
само избега на крајот.

788
00:39:43,740 --> 00:39:46,948
Истото се тука, вие сакате да бидете сигурни дека
тоа не избега на крај со групирање

789
00:39:46,948 --> 00:39:48,330
околу на врвот на табелата.

790
00:39:48,330 --> 00:39:50,530
Значи ова е само еден многу
едноставна хеш функција.

791
00:39:50,530 --> 00:39:56,570
Сето она што го направив беше да го направи првиот
писмото на она што нашите влезни беше

792
00:39:56,570 --> 00:40:01,660
и се претвори дека во индекс кој
ние би можеле да се стави во нашите хаш табелата.

793
00:40:01,660 --> 00:40:05,450
>> Да, и така како што реков претходно,
начинот на кој се справи со судири

794
00:40:05,450 --> 00:40:09,330
во нашата хаш маси се имаат,
она што ние го нарекуваме, врзувањето.

795
00:40:09,330 --> 00:40:13,860
Значи, ако се обидете да внесете повеќе
зборови што почнуваат со истото,

796
00:40:13,860 --> 00:40:16,145
ви се случува да имаат еден hash вредност.

797
00:40:16,145 --> 00:40:18,770
Авокадо и јаболко, ако сте
се пушта и преку нашите хеш функција,

798
00:40:18,770 --> 00:40:21,450
се случува да ви даде
истиот број, бројот на 0.

799
00:40:21,450 --> 00:40:24,550
Така и на начинот на кој ние се реши што е
дека ние всушност вид на може да ги врска

800
00:40:24,550 --> 00:40:27,010
заедно преку поврзани листи.

801
00:40:27,010 --> 00:40:29,600
>> И така, во таа смисла,
вие момци можат да се види каков вид

802
00:40:29,600 --> 00:40:32,640
за тоа како структурата на податоците кои
ние сме поставување на претходно

803
00:40:32,640 --> 00:40:35,870
како суво грозје поврзани листа вид
на може да дојде заедно во една.

804
00:40:35,870 --> 00:40:38,860
А потоа можете да се создаде досега
поефикасно структури на податоци

805
00:40:38,860 --> 00:40:43,350
што може да се справи со поголеми количини на
податоци, кои динамично менување на големината во зависност

806
00:40:43,350 --> 00:40:44,870
од вашите потреби.

807
00:40:44,870 --> 00:40:45,620
Секој јасно?

808
00:40:45,620 --> 00:40:47,580
Секој вид на јасни
на она што се случува овде?

809
00:40:47,580 --> 00:40:52,110
>> Ако сакав да insert-- она ​​што е
овошје, која започнува со, не знам,

810
00:40:52,110 --> 00:40:54,726
Б, освен Бери, банана.

811
00:40:54,726 --> 00:40:55,710
>> ПУБЛИКАТА: Blackberry.

812
00:40:55,710 --> 00:40:57,910
>> АНДИ Пенг: Blackberry, капина.

813
00:40:57,910 --> 00:41:00,530
Каде што го прави BlackBerry оди тука?

814
00:41:00,530 --> 00:41:04,251
Па, ние, всушност, не се подредени
ова сеуште, но теоретски

815
00:41:04,251 --> 00:41:06,250
ако сакаме да ја имаат оваа
по азбучен ред,

816
00:41:06,250 --> 00:41:07,944
каде што треба да се оди на BlackBerry?

817
00:41:07,944 --> 00:41:09,210
>> ПУБЛИКАТА: [Беззвучен]

818
00:41:09,210 --> 00:41:11,100
>> АНДИ Пенг: Точно, откако тука, нели?

819
00:41:11,100 --> 00:41:14,950
Но, бидејќи тоа е многу тешко да се
reorder-- Претпоставувам дека тоа е до вас момци.

820
00:41:14,950 --> 00:41:17,920
Вие момци можат целосно
спроведување на она што сакате.

821
00:41:17,920 --> 00:41:20,730
На поефикасен начин
да се направи ова, можеби

822
00:41:20,730 --> 00:41:24,570
ќе биде да се најде решение за вашата врска
листа во азбучен ред,

823
00:41:24,570 --> 00:41:26,520
и така, кога ќе завршиш
вметнување на нештата, сакате

824
00:41:26,520 --> 00:41:28,632
да бидат сигурни да ги внесете
во азбучен ред

825
00:41:28,632 --> 00:41:30,590
така што тогаш кога сте
обидувајќи се да ги пребарувате,

826
00:41:30,590 --> 00:41:32,410
вие не мора да се напречни сè.

827
00:41:32,410 --> 00:41:35,290
Да знаат точно каде
што е, и тоа е полесно.

828
00:41:35,290 --> 00:41:39,100
>> Но, ако сте вид на мора
работите прошарани по случаен избор,

829
00:41:39,100 --> 00:41:41,420
ти си уште се случува да имаат
за да ја преминат и онака.

830
00:41:41,420 --> 00:41:44,990
И така, ако сакав да се само
BlackBerry внесете тука

831
00:41:44,990 --> 00:41:47,470
и јас сакав да го бара за
тоа, знам, ох, капина

832
00:41:47,470 --> 00:41:52,012
мора да се почне со индексот на 1, па јас
знаеме моментално Само за пребарување на 1.

833
00:41:52,012 --> 00:41:53,970
А потоа можам да вид на
напречни поврзани листа

834
00:41:53,970 --> 00:41:56,120
се додека не се дојде до BlackBerry,
и then-- је?

835
00:41:56,120 --> 00:41:59,550
>> ПУБЛИКАТА: Ако се обидуваш да се create--
Претпоставувам како ова е многу едноставен хаш

836
00:41:59,550 --> 00:42:00,050
функција.

837
00:42:00,050 --> 00:42:02,835
А ако се сака да се направи
повеќе слоеви на кој, како,

838
00:42:02,835 --> 00:42:05,870
Добро, ние сакаме да се одвои во
како и сите азбучен писма

839
00:42:05,870 --> 00:42:09,040
а потоа повторно да се како друг сет
од азбучен писма во рамките на таа,

840
00:42:09,040 --> 00:42:11,715
ние се стави како хаш
табела во табела хаш,

841
00:42:11,715 --> 00:42:13,256
или како функција во рамките на функција?

842
00:42:13,256 --> 00:42:14,880
Или е that--

843
00:42:14,880 --> 00:42:17,510
>> АНДИ Пенг: Значи вашиот хаш
function-- вашиот хаш табелата

844
00:42:17,510 --> 00:42:19,360
може да биде голем како што сакате тоа да.

845
00:42:19,360 --> 00:42:21,930
Па во таа смисла, јас мислев
тоа е многу лесно, многу

846
00:42:21,930 --> 00:42:25,320
едноставно за мене да се заснова само вид
на букви од првиот збор.

847
00:42:25,320 --> 00:42:28,690
И така, има само 26 опции.

848
00:42:28,690 --> 00:42:32,650
Може да се добие само 26 опции од
0-25, бидејќи тие само може да

849
00:42:32,650 --> 00:42:36,510
почне од А до Ш, но ако сакаа
за да додадете, можеби, повеќе комплексност

850
00:42:36,510 --> 00:42:39,260
или побрзо време да се кандидира на вашиот
хаш табелата, можете апсолутно

851
00:42:39,260 --> 00:42:40,760
може да направи сите видови на нештата.

852
00:42:40,760 --> 00:42:43,330
Можете да направите свој
равенка која ги дава

853
00:42:43,330 --> 00:42:48,000
повеќе дистрибуција во вашата
зборови, а потоа, кога барате,

854
00:42:48,000 --> 00:42:49,300
тоа се случува да биде побрзо.

855
00:42:49,300 --> 00:42:52,100
>> Тоа е целосно зависи од вас момци
како сакате да го спроведат тоа.

856
00:42:52,100 --> 00:42:55,140
Сфатете го тоа како само кофи.

857
00:42:55,140 --> 00:42:57,376
Ако сакав да се имаат
26 кофи, јас ќе одам

858
00:42:57,376 --> 00:42:59,420
да одат во оние кофи.

859
00:42:59,420 --> 00:43:02,980
Но јас ќе одам да се има еден куп
на работи во секоја канта,

860
00:43:02,980 --> 00:43:05,890
па ако сакате да го направи тоа
побрзо и поефикасно,

861
00:43:05,890 --> 00:43:07,190
дозволете ми да имаат сто кофи.

862
00:43:07,190 --> 00:43:09,290
>> Но тогаш ќе мора да дознаам
начин да одат, за да бидат

863
00:43:09,290 --> 00:43:11,040
во соодветна кофа тие треба да бидат во.

864
00:43:11,040 --> 00:43:13,331
Но, тогаш вие всушност кога
сакате да се погледне во тоа кофа,

865
00:43:13,331 --> 00:43:16,410
тоа е многу побрзо, бидејќи има
помалку работи во секоја канта.

866
00:43:16,410 --> 00:43:20,250
И така, да, тоа е, всушност,
трик за вас момци во pset5

867
00:43:20,250 --> 00:43:22,360
е дека ќе биде
соочат со предизвикот да само да се создаде

868
00:43:22,360 --> 00:43:26,170
што и е најефикасен
функција, можете да замислите да се биде

869
00:43:26,170 --> 00:43:28,520
можност да ги чувате и да се провери овие вредности.

870
00:43:28,520 --> 00:43:30,840
>> Целосно зависи од вас момци
сепак сакате да го направи тоа,

871
00:43:30,840 --> 00:43:32,229
но тоа е навистина добра поента.

872
00:43:32,229 --> 00:43:34,520
Кој вид на логика
сакаат да почнат да размислуваат за

873
00:43:34,520 --> 00:43:37,236
е, добро, зошто да не се направи повеќе кофи.

874
00:43:37,236 --> 00:43:39,527
И тогаш јас треба да го бара
помалку работи, а потоа можеби и јас

875
00:43:39,527 --> 00:43:41,640
имаат различни хаш функција.

876
00:43:41,640 --> 00:43:45,500
>> Да, има многу начини да го направите ова
pset, некои се побрзо од другите.

877
00:43:45,500 --> 00:43:50,630
Јас сум целосно случува само види како
брзо беше најбрз вие момци ќе

878
00:43:50,630 --> 00:43:55,170
да биде во можност да ја добиете вашата функции за работа.

879
00:43:55,170 --> 00:43:58,176
Добро, добро за секого
врзувањето и хаш маси?

880
00:43:58,176 --> 00:44:00,800
Тоа е всушност како еден многу едноставен
концепт, ако мислите дека за тоа.

881
00:44:00,800 --> 00:44:05,160
Сето тоа е она што е одвојување
вашите податоци се во кофи,

882
00:44:05,160 --> 00:44:10,670
сортирање нив, а потоа да бараат на
наведува дека е поврзано со.

883
00:44:10,670 --> 00:44:11,852
>> Кул.

884
00:44:11,852 --> 00:44:18,160
Во ред, сега имаме еден поинаков вид
на податочна структура што се вика едно дрво.

885
00:44:18,160 --> 00:44:20,850
Ајде да одиме на и да разговараат за се обидува
кои се многу различни,

886
00:44:20,850 --> 00:44:22,330
но во истата категорија.

887
00:44:22,330 --> 00:44:29,010
Во суштина, сите дрво е наместо
за организирање на податоците во линеарен начин

888
00:44:29,010 --> 00:44:32,560
дека хаш табелата ви does--
Знаете, тоа е се здобија со врвот и дното

889
00:44:32,560 --> 00:44:37,900
а потоа ќе каков линк исклучување на it-- на
Дрвото има на врвот кој го нарекувате корен,

890
00:44:37,900 --> 00:44:40,220
и тогаш тоа има лисја сите околу неа.

891
00:44:40,220 --> 00:44:42,390
>> И така сите го имаме тука
е само врвот јазол

892
00:44:42,390 --> 00:44:45,980
што укажува на други јазли, дека поени
на повеќе јазли, и така натаму и така натаму.

893
00:44:45,980 --> 00:44:48,130
И па вие само треба разделување гранки.

894
00:44:48,130 --> 00:44:53,255
Тоа е само еден поинаков начин на организирање
на податоци, и затоа што ние го нарекуваме дрво,

895
00:44:53,255 --> 00:44:56,270
вие момци just-- тоа е само
моделирани надвор за да изгледа како дрво.

896
00:44:56,270 --> 00:44:57,670
Тоа е причината зошто ние го нарекуваме дрвја.

897
00:44:57,670 --> 00:44:59,370
>> Хаш табелата изгледа како маса.

898
00:44:59,370 --> 00:45:01,310
Дрвото само изгледа како дрво.

899
00:45:01,310 --> 00:45:03,300
Сето тоа е посебна
начин на организирање на јазли

900
00:45:03,300 --> 00:45:06,020
во зависност од она што вашите потреби се.

901
00:45:06,020 --> 00:45:11,810
>> За да можете да имате root и
тогаш мора лисја.

902
00:45:11,810 --> 00:45:15,380
Начинот на кој што можеме особено
мислам за тоа е бинарно дрво,

903
00:45:15,380 --> 00:45:18,150
бинарно дрво е само
посебен вид на дрво

904
00:45:18,150 --> 00:45:22,450
каде што секој јазол само точки
да, на Макс, две други јазли.

905
00:45:22,450 --> 00:45:25,434
И така тука треба посебна
симетрија во дрво

906
00:45:25,434 --> 00:45:28,600
што го прави полесно да се вид на изгледаат
во она што го цени сте затоа што тогаш

907
00:45:28,600 --> 00:45:30,150
мора секогаш лево или десно.

908
00:45:30,150 --> 00:45:33,150
Таму никогаш не е како трет од лево
лево или четврта по лева страна.

909
00:45:33,150 --> 00:45:36,358
Тоа е само да имате лево и десно
и можете да пребарувате било кој од овие две.

910
00:45:36,358 --> 00:45:38,980
И така зошто е ова корисно?

911
00:45:38,980 --> 00:45:40,980
Начинот на кој ова е
корисно е ако сте во потрага

912
00:45:40,980 --> 00:45:42,890
да пребарувате низ вредности, нели?

913
00:45:42,890 --> 00:45:45,640
Наместо спроведување бинарни
Барај во Array грешка,

914
00:45:45,640 --> 00:45:49,260
ако си сакал да биде во можност да го вметнете јазли
и да однесе јазли по волја и, исто така,

915
00:45:49,260 --> 00:45:52,185
зачувување на пребарувањето
капацитетите на бинарни пребарување.

916
00:45:52,185 --> 00:45:54,560
Така на овој начин, ние сме вид на
tricking-- сеќавам кога ние

917
00:45:54,560 --> 00:45:56,530
изјави поврзани листи не може бинарни пребарување?

918
00:45:56,530 --> 00:46:01,700
Ние сме вид на создавањето на податоци структура
кои трикови кои во работа.

919
00:46:01,700 --> 00:46:05,034
>> И така, бидејќи поврзани листи се линеарни,
тие само се поврзат еден по друг.

920
00:46:05,034 --> 00:46:06,950
Ние може да се вид на мора
различен вид на совети

921
00:46:06,950 --> 00:46:09,408
кои укажуваат на различни јазли
што може да ни помогне со пребарување.

922
00:46:09,408 --> 00:46:12,590
И така тука, ако сакав да
имаат бинарни пребарување дрво,

923
00:46:12,590 --> 00:46:14,090
Знам дека моето средината ако 55.

924
00:46:14,090 --> 00:46:18,280
Јас сум само ќе се создаде дека
како мојата средина, како root ми,

925
00:46:18,280 --> 00:46:20,770
а потоа јас ќе одам да имаат
вредности spin off на тоа.

926
00:46:20,770 --> 00:46:25,610
>> Па еве, ако јас одам да се бараат
вредноста на 66, јас може да почне на 55.

927
00:46:25,610 --> 00:46:27,310
Тоа е 66 поголем од 55?

928
00:46:27,310 --> 00:46:30,970
Да тоа е, па знам дека Мус пребарување
В о десно покажувачот од ова дрво.

929
00:46:30,970 --> 00:46:32,440
Одам на 77.

930
00:46:32,440 --> 00:46:35,367
Добро, што е помалку од 66 или поголем од 77?

931
00:46:35,367 --> 00:46:37,950
Тоа е помалку од, па да знаете, ох,
што треба да биде оставен јазол.

932
00:46:37,950 --> 00:46:41,410
>> И така тука ние сме вид на зачувување на
сите од големите нешта за низи,

933
00:46:41,410 --> 00:46:44,420
толку како динамична промена на големината
на предмети, да се биде

934
00:46:44,420 --> 00:46:49,530
можност да се вметне и да го избришете по волја,
без да мора да се грижите за фиксна

935
00:46:49,530 --> 00:46:50,370
износот на просторот.

936
00:46:50,370 --> 00:46:52,820
Ние се уште ги зачува сите
оние прекрасни нешта

937
00:46:52,820 --> 00:46:57,140
а во исто време да биде во можност да се зачува
се најавите и да пребарувате времето на бинарни пребарување

938
00:46:57,140 --> 00:47:00,450
дека сме биле само претходно
можност да се добие фраза.

939
00:47:00,450 --> 00:47:06,310
>> Кул податочна структура, вид на
комплекс да се спроведе, на јазол.

940
00:47:06,310 --> 00:47:08,311
Како што можете да видите, сите тоа
е на struct на јазолот

941
00:47:08,311 --> 00:47:10,143
е тоа што имаш лево
и право покажувач.

942
00:47:10,143 --> 00:47:11,044
Тоа е се што и да е.

943
00:47:11,044 --> 00:47:12,960
Па наместо само
има x или претходна.

944
00:47:12,960 --> 00:47:15,920
Имаш лево или десно, а потоа
можете да вид ги поврзат заедно

945
00:47:15,920 --> 00:47:16,836
сепак така одберете.

946
00:47:16,836 --> 00:47:21,080

947
00:47:21,080 --> 00:47:24,270
>> ОК, ние сме всушност ќе
само да потрае неколку минути.

948
00:47:24,270 --> 00:47:25,790
Па ние ќе треба да се вратиш тука.

949
00:47:25,790 --> 00:47:28,270
Како што реков претходно,
Јас вид на објаснето

950
00:47:28,270 --> 00:47:31,520
логиката зад тоа како ние
ќе го бара преку ова.

951
00:47:31,520 --> 00:47:33,860
Ние ќе треба да се обиде
pseudocoding ова за да се види

952
00:47:33,860 --> 00:47:38,000
ако може да се вид на примени
Истата логика на бинарни пребарување

953
00:47:38,000 --> 00:47:40,055
во друг тип на податоци структура.

954
00:47:40,055 --> 00:47:45,049
Ако вие момци сакате да се земе како неколку
минути за да се само се размислува за тоа.

955
00:47:45,049 --> 00:48:45,927

956
00:48:45,927 --> 00:48:46,925
ВО РЕД.

957
00:48:46,925 --> 00:48:51,407
Добро, јас ќе одам да
всушност, само да ви даде нема the--,

958
00:48:51,407 --> 00:48:52,990
ние ќе зборуваме за pseudocode прво.

959
00:48:52,990 --> 00:48:56,580
Сака ли некој така
да им даде прободе во тоа што

960
00:48:56,580 --> 00:49:02,100
Првото нешто што сакате да направите кога
сте почнуваат да го бара тоа?

961
00:49:02,100 --> 00:49:04,460
Ако ние сме во потрага по
вредноста на 66, што е

962
00:49:04,460 --> 00:49:07,940
првото нешто што сакате да направите, ако
ние сакаме да се бинарни пребарување ова дрво?

963
00:49:07,940 --> 00:49:10,760
>> ПУБЛИКАТА: Сакате да изгледа добро
и се погледне лево и да видиме [Беззвучен]

964
00:49:10,760 --> 00:49:11,230
поголем број.

965
00:49:11,230 --> 00:49:12,271
>> АНДИ Пенг: Да, точно.

966
00:49:12,271 --> 00:49:15,350
Па ви се случува да се погледне во вашиот корен.

967
00:49:15,350 --> 00:49:18,180
Има многу начини на кои можете да се јавите
тоа, вашиот надреден јазол луѓе велат.

968
00:49:18,180 --> 00:49:21,317
Ми се допаѓа да се каже, бидејќи коренот
тоа е како коренот од дрвото.

969
00:49:21,317 --> 00:49:23,400
Ви се случува да се погледне
Вашиот коренот јазол, а ти си

970
00:49:23,400 --> 00:49:26,940
ќе го видите е 66 поголеми
или помала од 55.

971
00:49:26,940 --> 00:49:30,360
И, ако е поголема од, добро, тоа е
поголема од, каде ќе сакате да се погледне?

972
00:49:30,360 --> 00:49:32,000
Каде сакаме да го бара сега, нели?

973
00:49:32,000 --> 00:49:34,340
Ние сакаме да ги пребарувате на
десната половина од ова дрво.

974
00:49:34,340 --> 00:49:38,390
>> Па ние имаме, погодно, односно
покажувач кој покажува на десно.

975
00:49:38,390 --> 00:49:44,325
И така, тогаш може да се постави
нашата нова root за да биде 77.

976
00:49:44,325 --> 00:49:46,450
Ние само може да оди каде и
покажувачот е да се покажува.

977
00:49:46,450 --> 00:49:49,100
Добро, О, еве ние сме почнуваат
на 77, а ние може да се само

978
00:49:49,100 --> 00:49:51,172
рекурзивно да го направите ова повторно и повторно.

979
00:49:51,172 --> 00:49:52,880
На овој начин, можете вид
за да имаат некоја функција.

980
00:49:52,880 --> 00:49:57,430
Имате начин на пребарување кои ви
може само да се повторува одново и одново и одново,

981
00:49:57,430 --> 00:50:02,720
зависност од тоа каде сакате да се погледне
додека не се дојде до крајот на вредноста

982
00:50:02,720 --> 00:50:04,730
кои сте во потрага по.

983
00:50:04,730 --> 00:50:05,230
Има смисла?

984
00:50:05,230 --> 00:50:07,800
>> Јас сум за да ви покажеме вистинските
код, и тоа е многу код.

985
00:50:07,800 --> 00:50:08,674
Нема потреба да навивач надвор.

986
00:50:08,674 --> 00:50:09,910
Ќе зборуваме низ него.

987
00:50:09,910 --> 00:50:13,410

988
00:50:13,410 --> 00:50:14,020
>> Всушност, не.

989
00:50:14,020 --> 00:50:15,061
Тоа беше само pseudocode.

990
00:50:15,061 --> 00:50:17,860
Добро, тоа беше само pseudocode,
што е малку комплекс,

991
00:50:17,860 --> 00:50:19,751
но тоа е сосема во ред.

992
00:50:19,751 --> 00:50:21,000
Секој следниве заедно во оваа ситуација?

993
00:50:21,000 --> 00:50:24,260
Ако коренот е ништовен, враќање
лажно, бидејќи тоа значи

994
00:50:24,260 --> 00:50:26,850
Вие дури и не мора ништо таму.

995
00:50:26,850 --> 00:50:31,376
>> Ако n е корен на вредноста, па ако тоа
се случува да биде оној што го барате,

996
00:50:31,376 --> 00:50:34,000
тогаш ви се случува да се врати точно
бидејќи знаете дека ја најдов.

997
00:50:34,000 --> 00:50:36,250
Но, ако вредноста е помала
од корен на n, ти си

998
00:50:36,250 --> 00:50:38,332
ќе пребарување на левата
дете или лево лист,

999
00:50:38,332 --> 00:50:39,540
што и да сакате да го наречеме.

1000
00:50:39,540 --> 00:50:41,750
И ако вредноста е поголема од корен,
ви се случува да се бара право дрво,

1001
00:50:41,750 --> 00:50:44,610
тогаш едноставно се кандидира на функцијата
преку пребарување повторно.

1002
00:50:44,610 --> 00:50:48,037
>> И ако коренот е ништовен, дека тој
значи дека сте достигнавме крајот?

1003
00:50:48,037 --> 00:50:50,120
Тоа значи дека може да има
повеќе повеќе листови за пребарување,

1004
00:50:50,120 --> 00:50:52,230
тогаш знаете, ох, се
Претпоставувам дека тоа не е тука

1005
00:50:52,230 --> 00:50:55,063
бидејќи јас откако разгледав
целата работа и тоа не е тука,

1006
00:50:55,063 --> 00:50:56,930
тоа само може да не е тука.

1007
00:50:56,930 --> 00:50:58,350
>> Дали тоа има смисла за секого?

1008
00:50:58,350 --> 00:51:03,230
Па тоа е како бинарни пребарување зачувување
можностите на поврзани листи.

1009
00:51:03,230 --> 00:51:09,200
Кул, така и на вториот тип
на податоците што структурата момци

1010
00:51:09,200 --> 00:51:13,180
Може да се обидете спроведување на вашиот pset,
вие само треба да се избере еден метод.

1011
00:51:13,180 --> 00:51:19,430
Но можеби и алтернативна метода за
хаш табелата е она што ние го нарекуваме Trie.

1012
00:51:19,430 --> 00:51:24,080
>> Сето Trie е е
специфични тип на дрво и

1013
00:51:24,080 --> 00:51:28,600
има вредности кои одат на други вредности.

1014
00:51:28,600 --> 00:51:31,450
Значи наместо бинарен
дрво во смисла на тоа дека само една

1015
00:51:31,450 --> 00:51:35,940
нешто што може да укаже на две, може да имаат
едно нешто точка за многу, многу работи.

1016
00:51:35,940 --> 00:51:39,450
Вие во суштина имаат низи
во внатрешноста на кој ќе ги чувате

1017
00:51:39,450 --> 00:51:41,790
покажувачи кои упатуваат на други низи.

1018
00:51:41,790 --> 00:51:45,210

1019
00:51:45,210 --> 00:51:49,460
>> Па јазол на тоа како ние
да дефинира Trie

1020
00:51:49,460 --> 00:51:52,590
ако сакаме да се имаат
Логичка, в збор, нели?

1021
00:51:52,590 --> 00:51:54,920
Па јазолот е Булова
како вистински или лажни,

1022
00:51:54,920 --> 00:51:58,490
пред сè на чело на
таа низа, е овој збор?

1023
00:51:58,490 --> 00:52:03,620
Второ, сакате да имате покажувачи
на она што остатокот од нив се.

1024
00:52:03,620 --> 00:52:07,470
Малку комплексен, малку апстрактен, но
Јас ќе се објасни она што сите средства.

1025
00:52:07,470 --> 00:52:13,800
>> Па еве, на врвот, ако
имаат низа веќе објави,

1026
00:52:13,800 --> 00:52:17,040
еден јазол каде што треба Булова
вредност се чуваат во пред

1027
00:52:17,040 --> 00:52:19,490
кој ви кажува дали е ова некој збор?

1028
00:52:19,490 --> 00:52:20,520
Зарем ова не е зборот?

1029
00:52:20,520 --> 00:52:23,240
И тогаш го имате
остатокот од вашата низа која

1030
00:52:23,240 --> 00:52:26,040
всушност зачувува сите
можности за тоа што би можело да биде.

1031
00:52:26,040 --> 00:52:28,660
Така, на пример, како
на врвот имаш

1032
00:52:28,660 --> 00:52:32,140
првото нешто што се вели дека е точно или
лажни, да или не, ова е еден збор.

1033
00:52:32,140 --> 00:52:38,130
>> А потоа ќе мора од 0 до 26 од
буквите што можете да ги чувате.

1034
00:52:38,130 --> 00:52:42,790
Ако сакав да ги барате
за лилјак, одам на врвот

1035
00:52:42,790 --> 00:52:49,200
и јас со нетрпение за B. најдам Б во мојата
низа, и така знам, во ред, Б е зборот?

1036
00:52:49,200 --> 00:52:53,010
Б не е збор, па на тој начин
Јас мора да продолжи со барањето.

1037
00:52:53,010 --> 00:52:56,410
Одам од Б, и гледам на
покажувач, кој укажува на Б

1038
00:52:56,410 --> 00:53:00,900
и јас не гледам друга низа на информации,
истата структура кои ги имале претходно.

1039
00:53:00,900 --> 00:53:05,240
>> Here-- и ох, следниот
писмо во [Беззвучен] е А.

1040
00:53:05,240 --> 00:53:07,210
Значи ние се погледне во таа низа.

1041
00:53:07,210 --> 00:53:10,860
Ние се најде на осмото вредност,
а потоа ние со нетрпение да се види, ох,

1042
00:53:10,860 --> 00:53:12,840
еј, е во тоа што еден збор, е Б-А зборот?

1043
00:53:12,840 --> 00:53:13,807
Тоа не е збор.

1044
00:53:13,807 --> 00:53:14,890
Ние мора да ги бараме.

1045
00:53:14,890 --> 00:53:17,850
>> И така, тогаш ние со нетрпение да каде
покажувачот на A поени,

1046
00:53:17,850 --> 00:53:21,130
и тоа укажува на уште еден начин на
која ние имаме повеќе вредност се чуваат.

1047
00:53:21,130 --> 00:53:24,150
И на крајот, ние се дојде до
B-А-Т, која е збор.

1048
00:53:24,150 --> 00:53:25,970
И така следниот пат
ќе се погледне, си оди

1049
00:53:25,970 --> 00:53:30,850
да го имаат тоа проверка, да,
оваа Булова функција е точно.

1050
00:53:30,850 --> 00:53:35,450
И така во таа смисла ние сме вид
да има едно дрво со низи.

1051
00:53:35,450 --> 00:53:39,890
>> Па тогаш може да се вид на пребарување надолу.

1052
00:53:39,890 --> 00:53:43,650
Наместо хаш функција и
Доделување вредности од страна на поврзани листа,

1053
00:53:43,650 --> 00:53:49,190
вие само може да се спроведе
Trie која бара downwords.

1054
00:53:49,190 --> 00:53:50,850
Навистина, навистина комплицирани работи.

1055
00:53:50,850 --> 00:53:54,060
Не е лесно да се размислува за, бидејќи јас сум како
плукање толку многу структури на податоци од

1056
00:53:54,060 --> 00:53:58,710
во тебе, но не секој вид на
се разбере како функционира логиката на ова?

1057
00:53:58,710 --> 00:54:01,920
>> Добро, кул.

1058
00:54:01,920 --> 00:54:05,600
Па B-A-T, а потоа
ви се случува да се бара.

1059
00:54:05,600 --> 00:54:07,940
Следниот пат кога ќе си оди
за да ја видите, ох, еј, тоа е точно,

1060
00:54:07,940 --> 00:54:09,273
така знам дека ова мора да биде еден збор.

1061
00:54:09,273 --> 00:54:12,030

1062
00:54:12,030 --> 00:54:13,770
>> Истото за зоолошката градина.

1063
00:54:13,770 --> 00:54:17,960
Значи, тука е нешто во моментов, ако се
сакаше да пребарувате за зоолошката градина, во моментов,

1064
00:54:17,960 --> 00:54:20,780
моментално не е зоолошката градина
збор во нашето речникот

1065
00:54:20,780 --> 00:54:25,300
бидејќи, како што вие момци можат да се види,
прво место дека имаме Булова

1066
00:54:25,300 --> 00:54:28,590
врати вистина е на крајот на зумирање.

1067
00:54:28,590 --> 00:54:30,430
Имаме Z-О-О-М.

1068
00:54:30,430 --> 00:54:33,900
>> И така тука, не, всушност, имаат
зборот, зоолошката градина, во нашето речникот

1069
00:54:33,900 --> 00:54:36,070
затоа оваа опција не е обележана.

1070
00:54:36,070 --> 00:54:39,540
Така што компјутер не го прави тоа
знам дека зоолошката градина е збор

1071
00:54:39,540 --> 00:54:42,430
бидејќи начинот на кој ние сме
тоа се чуваат, само зум тука

1072
00:54:42,430 --> 00:54:44,920
всушност има Булова вредност
и тоа е се покажа точно.

1073
00:54:44,920 --> 00:54:49,380
Значи, ако сакаме да го вметнете
збор, зоолошката градина, во нашето речникот,

1074
00:54:49,380 --> 00:54:51,770
како ќе се оди за тоа го прават?

1075
00:54:51,770 --> 00:54:55,960
Што треба да направите за да се осигураме дека нашите
компјутер знае дека Z-О-О е збор

1076
00:54:55,960 --> 00:54:58,130
а не на првиот збор е Z-О-О-М?

1077
00:54:58,130 --> 00:54:59,360
>> ПУБЛИКАТА: [Беззвучен]

1078
00:54:59,360 --> 00:55:01,450
>> АНДИ Пенг: Точно, ние
сакате да бидете сигурни дека овој

1079
00:55:01,450 --> 00:55:07,890
тука, дека Булова вредност е
штиклирани дека тоа е вистина.

1080
00:55:07,890 --> 00:55:13,297
Z-О-О, тогаш ние ќе треба да проверите,
па ние точно знаеме, еј, зоолошка градина е еден збор.

1081
00:55:13,297 --> 00:55:15,380
Одам да кажам
компјутер дека тоа е збор, така

1082
00:55:15,380 --> 00:55:18,000
дека кога проверките на компјутерот,
таа знае дека е зоолошката градина збор.

1083
00:55:18,000 --> 00:55:21,269
>> Затоа што се сеќавам на сите овие податоци
структури, тоа е многу лесно за нас

1084
00:55:21,269 --> 00:55:22,310
да се каже дека, ох, лилјак е збор.

1085
00:55:22,310 --> 00:55:22,851
Зоолошката градина е еден збор.

1086
00:55:22,851 --> 00:55:23,611
Зум е збор.

1087
00:55:23,611 --> 00:55:25,860
Но, кога ќе го гради,
компјутерот нема идеја.

1088
00:55:25,860 --> 00:55:28,619
>> Па мора да го кажам токму
во кој момент е овој збор?

1089
00:55:28,619 --> 00:55:29,910
На која точка не е тоа збор?

1090
00:55:29,910 --> 00:55:31,784
И во кој момент да направам
треба да се бараат работи,

1091
00:55:31,784 --> 00:55:34,000
и во кој момент ми е потребно да одите понатаму?

1092
00:55:34,000 --> 00:55:37,010
Секој јасно на што?

1093
00:55:37,010 --> 00:55:39,540
Кул.

1094
00:55:39,540 --> 00:55:42,530
>> И така тогаш доаѓа
проблемот за тоа како би ние

1095
00:55:42,530 --> 00:55:45,560
одат за вметнување на нешто
кои, всушност, не е таму?

1096
00:55:45,560 --> 00:55:49,090
Па да речеме ние сакаме да го внесете
зборот, бања, во нашата Trie.

1097
00:55:49,090 --> 00:55:53,589
Како вие момци можат да се види како во моментов
сите го имаме сега е Б-А-Т,

1098
00:55:53,589 --> 00:55:55,630
и оваа нова структура на податоци
имаше едно пивце дека

1099
00:55:55,630 --> 00:55:59,740
укажа null бидејќи претпоставуваме
дека, ох, нема зборови по Б-А-Т,

1100
00:55:59,740 --> 00:56:02,530
Зошто се потребни за да се задржи
имајќи работите после тоа Т.

1101
00:56:02,530 --> 00:56:06,581
>> Но, проблемот се појавува ако го правиш
сакаат да имаат еден збор што доаѓа по

1102
00:56:06,581 --> 00:56:07,080
Т е.

1103
00:56:07,080 --> 00:56:09,500
Ако имате бања, ти си
ќе сакаат правото H.

1104
00:56:09,500 --> 00:56:13,290
Така и на начинот на кој ние се случува да се направи, што е
ние ќе треба да се создаде посебна јазол.

1105
00:56:13,290 --> 00:56:16,840
Ние не сме партиционираш без оглед на износот
на меморија за оваа нова низа,

1106
00:56:16,840 --> 00:56:20,720
и ние ќе го преназначаване покажувачи.

1107
00:56:20,720 --> 00:56:22,947
>> Ние ќе треба да му ја додели на
Н, Прво на сите, ова нула,

1108
00:56:22,947 --> 00:56:24,030
ние ќе треба да се ослободи од.

1109
00:56:24,030 --> 00:56:26,590
Ние ќе треба да имаат
надолу Н точка.

1110
00:56:26,590 --> 00:56:30,600
Ако можеме да видиме еден Н, ние го сакаме
да одат на друго место.

1111
00:56:30,600 --> 00:56:33,910
>> Овде, ние тогаш може да се провери надвор да.

1112
00:56:33,910 --> 00:56:38,170
Ако ние го погоди часа по Т, ох,
тогаш знаеме дека ова е еден збор.

1113
00:56:38,170 --> 00:56:41,110
Булова се случува да се врати вистина.

1114
00:56:41,110 --> 00:56:42,950
Сите јасни за тоа како што се случи?

1115
00:56:42,950 --> 00:56:45,110
ВО РЕД.

1116
00:56:45,110 --> 00:56:47,214
>> Значи во суштина, сето
овие структури на податоци

1117
00:56:47,214 --> 00:56:50,130
дека ние сме поминале повеќе од денес, јас сум
качил над нив, навистина, навистина брзо

1118
00:56:50,130 --> 00:56:52,192
а не да се многу
детали, и тоа е во ред.

1119
00:56:52,192 --> 00:56:53,900
Откако ќе почнете да Месинг
со него, ќе биде

1120
00:56:53,900 --> 00:56:55,733
следење на каде
сите покажувачи се,

1121
00:56:55,733 --> 00:56:58,060
она што се случува во вашата
структури на податоци, итн.

1122
00:56:58,060 --> 00:56:59,810
Тие ќе бидат многу корисни,
и тоа е на вас останува

1123
00:56:59,810 --> 00:57:03,890
момци да целосно да дознаам како
сакате да се имплементираат работите.

1124
00:57:03,890 --> 00:57:07,650
>> И така pset4, на 5-- ох, тоа е во ред.

1125
00:57:07,650 --> 00:57:10,140
Pset5 е грешките во правописот.

1126
00:57:10,140 --> 00:57:13,710
Како што реков претходно, си оди за да се, еднаш
повторно, да го симнете изворниот код од нас.

1127
00:57:13,710 --> 00:57:16,210
Таму се случува да биде три главни
работи што ќе бидат симнување.

1128
00:57:16,210 --> 00:57:18,470
Ќе преземете речници,
КЕРС, и текстови.

1129
00:57:18,470 --> 00:57:21,660
>> Сите тие работи се се
или речници на зборови

1130
00:57:21,660 --> 00:57:25,190
дека ние сакаме да се провери
или тест на информации

1131
00:57:25,190 --> 00:57:26,930
дека ние сакаме да се проверка на правопис.

1132
00:57:26,930 --> 00:57:29,670
И така на речници
даваме ви се случува

1133
00:57:29,670 --> 00:57:34,870
да ви даде вистински зборови кои сакаме
да ги чувате на некој начин, на начин што е

1134
00:57:34,870 --> 00:57:36,530
поефикасно од низа.

1135
00:57:36,530 --> 00:57:38,470
А потоа и текстовите се
ќе биде она што ние сме

1136
00:57:38,470 --> 00:57:43,900
ќе побара од вас да ги запишува проверете да бидете сигурни
сите зборови се вистински зборови.

1137
00:57:43,900 --> 00:57:47,970
>> И така на три блока на
програми кои ќе ви даде

1138
00:57:47,970 --> 00:57:51,130
се нарекуваат dictionary.c,
dictionary.h, и speller.c.

1139
00:57:51,130 --> 00:57:56,500
И така сите dictionary.c не е
она што ќе ви биде побарано да ги спроведе.

1140
00:57:56,500 --> 00:57:57,880
Се вчитува зборови.

1141
00:57:57,880 --> 00:58:02,000
Го пишува чекови нив, и тоа го прави сигурни
дека сè е правилно вметната.

1142
00:58:02,000 --> 00:58:05,180
>> diction.h е само библиотека датотека
изјавува дека сите оние функции.

1143
00:58:05,180 --> 00:58:07,650
И speller.c, ние се случува да ви даде.

1144
00:58:07,650 --> 00:58:09,290
Вие не треба да се промени ништо од тоа.

1145
00:58:09,290 --> 00:58:14,290
Сите speller.c не е се земе дека,
товари него, ја проверува брзината на тоа,

1146
00:58:14,290 --> 00:58:19,190
тестови за репер за како тоа, како
брзо сте во можност да се прават работите.

1147
00:58:19,190 --> 00:58:20,410
>> Тоа е правопис.

1148
00:58:20,410 --> 00:58:23,920
Само да не се плеткаш со него, но го направи
Дали сте сигурни дека се разбере она што таа го прави.

1149
00:58:23,920 --> 00:58:28,090
Ние ги користиме на функција наречена getrusage дека
тестови на перформансите на вашиот правопис

1150
00:58:28,090 --> 00:58:28,590
Проверка на.

1151
00:58:28,590 --> 00:58:32,200
Сите тоа го прави е во основа се тестира
време на се што е во вашиот речник,

1152
00:58:32,200 --> 00:58:33,680
така погрижете се да го разбереш.

1153
00:58:33,680 --> 00:58:36,660
Бидете внимателни да не се плеткаш со него или
друго работите нема да се води уредно.

1154
00:58:36,660 --> 00:58:39,740

1155
00:58:39,740 --> 00:58:44,170
>> И најголемиот дел од овој предизвик е за
вие момци навистина да ги менувате dictionary.c.

1156
00:58:44,170 --> 00:58:48,526
Ние ќе треба да ви даде
140.000 зборови во речник.

1157
00:58:48,526 --> 00:58:50,900
Ние ќе треба да ви даде текст
датотека која има овие зборови,

1158
00:58:50,900 --> 00:58:54,840
и ние сакаме да биде во можност да организира
нив во хаш табелата или Trie

1159
00:58:54,840 --> 00:58:58,140
бидејќи кога бараме од вас да ги запишува
check-- замислите ако сте правопис

1160
00:58:58,140 --> 00:59:00,690
проверка како Одисеја на Хомер.

1161
00:59:00,690 --> 00:59:03,010
Тоа е како овој огромен, огромен тест.

1162
00:59:03,010 --> 00:59:05,190
>> Замислете ако секој
зборот кој сте имале да се погледне

1163
00:59:05,190 --> 00:59:08,100
преку низа на 140.000 вредности.

1164
00:59:08,100 --> 00:59:10,350
Кои би се засекогаш
за вашата машина да се кандидира.

1165
00:59:10,350 --> 00:59:14,490
Тоа е причината зошто ние сакаме да го организираме нашето
податоци во поефикасно структури на податоци

1166
00:59:14,490 --> 00:59:17,270
како што се маса хаш или Trie.

1167
00:59:17,270 --> 00:59:20,700
А потоа вие момци можат вид
од кога барате пристап

1168
00:59:20,700 --> 00:59:22,570
работите полесно и побрзо.

1169
00:59:22,570 --> 00:59:24,934
>> И така да се биде внимателен да го реши судири.

1170
00:59:24,934 --> 00:59:27,350
Си оди за да се добие еден куп
на зборовите кои почнуваат со А.

1171
00:59:27,350 --> 00:59:29,957
Си оди за да се добие еден куп зборови
кои почнуваат со Б. До вас

1172
00:59:29,957 --> 00:59:31,290
момци како сакате да го реши тоа.

1173
00:59:31,290 --> 00:59:34,144
Можеби има уште
ефикасен хеш функција

1174
00:59:34,144 --> 00:59:36,810
од само првата буква од
нешто, и така што е на вас

1175
00:59:36,810 --> 00:59:38,190
момци да се вид на правите што сакате.

1176
00:59:38,190 --> 00:59:40,148
>> Можеби сакате да го додадете
сите букви заедно.

1177
00:59:40,148 --> 00:59:43,410
Можеби сакате да се направи чудни работи се допаѓа
на сметка на бројот на букви,

1178
00:59:43,410 --> 00:59:43,970
како и да е.

1179
00:59:43,970 --> 00:59:45,386
До вас момци како што сакате да направите.

1180
00:59:45,386 --> 00:59:49,262
Ако сакате да се направи хаш табелата, ако
сакате да се обидете со Trie, целосно зависи од вас.

1181
00:59:49,262 --> 00:59:52,470
Јас ќе ве предупреди пред време дека
Trie е обично малку потешко

1182
00:59:52,470 --> 00:59:54,520
само затоа што има многу
повеќе совети како да ги пратите.

1183
00:59:54,520 --> 00:59:55,645
Но целосно зависи од вас момци.

1184
00:59:55,645 --> 00:59:58,742
Тоа е далеку поефикасно
во повеќето случаи.

1185
00:59:58,742 --> 01:00:01,450
Сакате навистина да се биде во можност да го задржи
пратите на сите ваши покажувачи.

1186
01:00:01,450 --> 01:00:03,850
Како да го прават истото
дека правам овде.

1187
01:00:03,850 --> 01:00:06,871
Кога ќе се обидуваш да го вметнете
вредности во хаш табелата или избришете,

1188
01:00:06,871 --> 01:00:08,620
бидете сигурни дека сте
навистина следење

1189
01:00:08,620 --> 01:00:11,860
од каде што се е поради
тоа е навистина лесен за да сум

1190
01:00:11,860 --> 01:00:14,727
обидувајќи се да го вметнете како зборот, Енди.

1191
01:00:14,727 --> 01:00:16,810
Да речеме дека тоа е
вистински збор, зборот, Енди,

1192
01:00:16,810 --> 01:00:19,640
во огромна листа на А зборови.

1193
01:00:19,640 --> 01:00:22,450
>> Ако јас само да се случи да преназначаване
покажувач погрешно, Упс,

1194
01:00:22,450 --> 01:00:24,940
таму оди на интегритет на
остатокот на мојот поврзани листа.

1195
01:00:24,940 --> 01:00:26,897
Сега единствен збор јас
имаме е Енди, а сега

1196
01:00:26,897 --> 01:00:29,230
сите на други зборови во
речникот да се изгуби.

1197
01:00:29,230 --> 01:00:31,370
И така ќе сакате да бидете сигурни дека ќе
ги пратите на сите ваши совети

1198
01:00:31,370 --> 01:00:33,661
или на друго место ќе ја добиеме
огромни проблеми во вашиот код.

1199
01:00:33,661 --> 01:00:35,840
Цртаат работи надвор внимателно чекор по чекор.

1200
01:00:35,840 --> 01:00:37,870
Тоа го прави многу полесно да се замисли.

1201
01:00:37,870 --> 01:00:40,910
>> И на крај, вие сакате да бидете во можност да
ги тестираат вашите перформанси на вашата програма

1202
01:00:40,910 --> 01:00:41,618
на големата табла.

1203
01:00:41,618 --> 01:00:43,710
Ако вие момци се земе
погледне во CS50 токму сега,

1204
01:00:43,710 --> 01:00:45,210
имаме она што се вика на големата табла.

1205
01:00:45,210 --> 01:00:50,200
Тоа е резултат на состојба од најбрзите
проверка на правопис пати во сите на CS50

1206
01:00:50,200 --> 01:00:55,720
во моментов, мислам дека на врвот како 10
Времето Мислам дека осум од нив се вработени.

1207
01:00:55,720 --> 01:00:57,960
Ние навистина сакаме вие ​​момци да ни го победи.

1208
01:00:57,960 --> 01:01:00,870
>> Сите од нас се обидуваат да се спроведе
најбрзо кодот што е можно.

1209
01:01:00,870 --> 01:01:04,880
Ние сакаме вие ​​момци да се обиде да го оспори
нас и да се спроведе побрз од сите нас

1210
01:01:04,880 --> 01:01:05,550
може.

1211
01:01:05,550 --> 01:01:07,970
Па така ова е навистина
прв пат, дека ние сме

1212
01:01:07,970 --> 01:01:12,680
ќе побара од вас момци да се направи pset дека
навистина може да се направи во кој било метод

1213
01:01:12,680 --> 01:01:13,760
ти сакаш.

1214
01:01:13,760 --> 01:01:17,730
>> Јас секогаш се каже, ова е повеќе слично
до решение вистинскиот живот, нели?

1215
01:01:17,730 --> 01:01:19,550
Велам, еј, јас треба да го направите тоа.

1216
01:01:19,550 --> 01:01:21,380
Изгради една програма која го прави ова за мене.

1217
01:01:21,380 --> 01:01:22,630
Направете го тоа како сакате.

1218
01:01:22,630 --> 01:01:24,271
Јас само знам дека сакам да пости.

1219
01:01:24,271 --> 01:01:25,770
Тоа е предизвик вашите за оваа недела.

1220
01:01:25,770 --> 01:01:27,531
Вие момци, ние ќе
да ви даде задача.

1221
01:01:27,531 --> 01:01:29,030
Ние ќе треба да ви даде предизвик.

1222
01:01:29,030 --> 01:01:31,559
И тогаш тоа е до вас момци
целосно само дознаам

1223
01:01:31,559 --> 01:01:34,100
што е најбрзиот и повеќето
ефикасен начин за спроведување на оваа.

1224
01:01:34,100 --> 01:01:34,600
Да?

1225
01:01:34,600 --> 01:01:37,476
>> ПУБЛИКАТА: Дали смееме да ако
Резултатите од ова истражување побрзо начини

1226
01:01:37,476 --> 01:01:40,821
хаш маси да се направи на интернет, можеме да направиме
дека и цитираат код на некој друг?

1227
01:01:40,821 --> 01:01:42,070
АНДИ Пенг: Да, сосема во ред.

1228
01:01:42,070 --> 01:01:44,320
Значи, ако вие момци го прочитате
спецификации, има линија

1229
01:01:44,320 --> 01:01:48,310
во спецификации кој се вели дека момците
се целосно слободни да истражуваат хаш

1230
01:01:48,310 --> 01:01:51,070
функции на она што се некои
побрзото хаш функции

1231
01:01:51,070 --> 01:01:54,720
да се кандидира работи преку како
колку што ќе се цитираат овој код.

1232
01:01:54,720 --> 01:01:57,220
Па некои луѓе веќе имаат
сфатиле брзи начини

1233
01:01:57,220 --> 01:02:00,250
на водење проверувачи за правопис, на брза
начини на складирање на информации.

1234
01:02:00,250 --> 01:02:02,750
Целосно зависи од вас момци ако
сакам само да се земе тоа, нели?

1235
01:02:02,750 --> 01:02:04,045
Бидете сигурни дека сте повикувајќи.

1236
01:02:04,045 --> 01:02:06,170
Предизвикот тука навистина
дека ние се обидуваме да се тестира

1237
01:02:06,170 --> 01:02:09,750
е да се осигура дека знаете
снајдете покажувачи.

1238
01:02:09,750 --> 01:02:12,700
Колку што спроведување
вистинските хеш функција

1239
01:02:12,700 --> 01:02:15,070
и доаѓа со се допаѓа
математика се прави тоа,

1240
01:02:15,070 --> 01:02:17,570
вие момци може да истражување било
методи онлајн вие момци сакате.

1241
01:02:17,570 --> 01:02:17,996
Да?

1242
01:02:17,996 --> 01:02:19,700
>> ПУБЛИКАТА: Можеме ли да се цитираат само
со користење на [Беззвучен]?

1243
01:02:19,700 --> 01:02:20,120
>> АНДИ Пенг: Да.

1244
01:02:20,120 --> 01:02:22,328
Може да се само, со твојот коментар,
можете да се цитираат како, о,

1245
01:02:22,328 --> 01:02:26,127
земени од ала, ала,
ала, хеш функција.

1246
01:02:26,127 --> 01:02:27,210
Секој имате било какви прашања?

1247
01:02:27,210 --> 01:02:29,694
Ние всушност breezed
преку делот денес.

1248
01:02:29,694 --> 01:02:31,610
Јас ќе бидам тука за да се
одговори на прашањата, како и.

1249
01:02:31,610 --> 01:02:36,570
>> Исто така, како што реков, канцеларија
часа вечерва и утре.

1250
01:02:36,570 --> 01:02:40,307
Спец оваа недела е, всушност,
супер лесен и супер краток за да ја прочитате.

1251
01:02:40,307 --> 01:02:43,140
Јас би навестиле преземање на ум, само
Прошетајте низ целината на него.

1252
01:02:43,140 --> 01:02:45,730
>> И Zamyla всушност ќе шета
преку секоја од функциите

1253
01:02:45,730 --> 01:02:49,796
што треба да се спроведе, и така тоа е
многу, многу јасно како да се направи сè.

1254
01:02:49,796 --> 01:02:51,920
Само за да бидете сигурни дека сте
следење на покажувачи.

1255
01:02:51,920 --> 01:02:53,650
Ова е многу предизвикувачки pset.

1256
01:02:53,650 --> 01:02:56,744
>> Тоа не е предизвик, бидејќи како и,
ох, концептите се толку многу повеќе

1257
01:02:56,744 --> 01:02:59,160
тешко, па ќе мора да научат
толку многу нови синтаксата на патот

1258
01:02:59,160 --> 01:03:00,650
што сте направиле за последните pset.

1259
01:03:00,650 --> 01:03:03,320
Pset ова е тешко, бидејќи
има толку многу покажувачи,

1260
01:03:03,320 --> 01:03:06,980
и тогаш тоа е многу, многу лесно да се еднаш
имаш грешка во кодот не можат

1261
01:03:06,980 --> 01:03:08,315
да се најде каде што вирусот е.

1262
01:03:08,315 --> 01:03:13,200
>> И така комплетна и крајна вера во тебе
момци да бидат во можност да се победи на нашите [Беззвучен]

1263
01:03:13,200 --> 01:03:13,700
правопис.

1264
01:03:13,700 --> 01:03:16,640
Јас всушност немаат никаква писмена рудник
уште, но јас сум за да се напише рудникот.

1265
01:03:16,640 --> 01:03:19,070
Па така додека сте пишување
твое, јас ќе напишам мој.

1266
01:03:19,070 --> 01:03:21,070
Одам да се обидат да се направи
рудникот побрзо од твое.

1267
01:03:21,070 --> 01:03:23,940
Ќе видиме кој има најбрзо еден.

1268
01:03:23,940 --> 01:03:27,340
>> И да, јас ќе ги видиш сите од
вие момци тука во вторникот.

1269
01:03:27,340 --> 01:03:29,510
Јас ќе се кандидира еден вид како pset работилница.

1270
01:03:29,510 --> 01:03:32,640
Сите делови на оваа
недела се pset работилници,

1271
01:03:32,640 --> 01:03:36,690
па вие момци имаат многу можности
за помош, на работното време, како и секогаш,

1272
01:03:36,690 --> 01:03:41,330
и јас навистина со нетрпение очекуваме да
читањето на сите на вашиот код, момци '.

1273
01:03:41,330 --> 01:03:44,160
Имам квизови се тука ако
момци сакаат да дојдат да се оние.

1274
01:03:44,160 --> 01:03:45,880
Тоа е се.

1275
01:03:45,880 --> 01:03:48,180