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
>> ANDI Пэн: Сардэчна запрашаем у тыдзень 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
>> ANDI Пэн: Гадзіннік
tonight-- аб, добры пытанне.

67
00:02:56,120 --> 00:03:00,580
Я думаю, што сёння ўвечары офіс гадзін
у Teal або абшчын.

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
Так ЛИФО з'яўляецца абрэвіятурай нам падабаецца
каб 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
Control-Z, так?

115
00:05:00,030 --> 00:05:03,640
Control-Z, так што колькасць часу
што Control-Z выратаваў маё жыццё,

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
І потым, калі вам гэта трэба зноў, вам
штурхаць яго, што гэта тое, што Ctrl + 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
>> Такім чынам, структура з'яўляецца спосабам, якім
мы на самай справе стварыць стэк.

125
00:05:40,150 --> 00:05:44,720
Набіраем вызначыць-структуру, а затым
мы называем гэта стэк на дне.

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
Калі [неразборліва] размер--
памятаеце, калі вы

141
00:06:32,640 --> 00:06:35,300
хочаце атрымаць доступ да любой
Параметр у структуры,

142
00:06:35,300 --> 00:06:40,320
вы імя struct.parameter.

143
00:06:40,320 --> 00:06:42,720
>> У гэтым выпадку, з-за
імя нашага стэка.

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 роўны п.

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
А потым мы хочам, каб пераканацца, што
мы таксама павялічваючы памер п,

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
ANDI Пэн: Вядома, так, што робіць
s.size цяперашні час нам дае?

163
00:07:45,808 --> 00:07:47,440
АЎДЫТОРЫЯ: Гэта бягучы памер.

164
00:07:47,440 --> 00:07:50,890
ANDI Пэн: Роўна, таму
бягучы індэкс, што наш памер на,

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
Усё гэта звяртаецца да
Масіў у нашай структуры,

169
00:08:03,510 --> 00:08:06,030
і таму, калі мы хочам, каб
размясціць п у гэтым індэксе,

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
>> Добра, поп, я псевдокод яго
для вас, хлопцы, але аналагічнай канцэпцыі.

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
поп, калі ёсць што-тое, каб поп-музыкі.

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
псевдокод, вельмі, вельмі падобныя, каб падштурхнуць.

192
00:09:02,214 --> 00:09:03,380
Проста выконвайце ўздоўж логікі.

193
00:09:03,380 --> 00:09:06,092
Пераканайцеся, што вы звяртаецеся ўсе
асаблівасці вашай мадэлі правільна.

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
ANDI Пэн: Заўсёды, так.

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
>> Такім чынам, што мы хацелі б назваць гэта
у вызваленні пакета з чаргі і enqueueing.

209
00:09:49,680 --> 00:09:52,380
Калі мы хочам нешта дадаць
ў нашай чарзе, мы ў чаргу.

210
00:09:52,380 --> 00:09:55,690
Калі мы хочам, каб з чаргі, або ўзяць
то прэч, мы з чаргі.

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
>> Так у структуры тыпу
вызначыць, як вы можаце бачыць,

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
>> Так як жа рэальна
ўставіць нешта у чарзе?

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
ANDI Пэн: Роўна, вы хочаце, каб дадаць
гэта ў залежнасці ад вы напісалі гэта.

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
>> Вельмі, вельмі падобныя структура, вельмі, вельмі
Падобная структура, як і папярэдні

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
ANDI Пэн: Так.

271
00:13:49,506 --> 00:13:56,200
АЎДЫТОРЫЯ: О, не прабачце.

272
00:13:56,200 --> 00:14:00,250
ANDI Пэн: ОК, так што давайце
хадзіць праз гэты код.

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
мяняцца ў залежнасці ад дзе
хочаце пачатак нашага ц быць,

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 гэта масіў у нашай ц.

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
>> ANDI Пэн: 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
>> І вось зараз, калі вы
хацеў з чаргі, гэта

327
00:17:09,970 --> 00:17:15,240
дзе наша галава будзе пераход
таму што, калі мы павінны былі з чаргі,

328
00:17:15,240 --> 00:17:17,030
мы не зняць канец в.

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
>> І таму, калі вы з чаргі,
Я таксама псевдокод яго.

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
Калі б я хацеў, каб з чаргі, я
будзе рухацца галаву над.

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
І таму ад таго, як структура
мы ствараем вузел тут мы

353
00:18:29,880 --> 00:18:33,569
ёсць Int N, які з'яўляецца тое, што
значэнне ў краме ці струннага п

354
00:18:33,569 --> 00:18:35,610
або што вы хочаце, каб
гэта называюць, паўкокс зорка н.

355
00:18:35,610 --> 00:18:41,482
Структура, вузел зорка, якая з'яўляецца паказальнікам
што вы хочаце, каб у кожным вузле,

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
Гэта будзе паказваць на
NULL, і што, калі

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
>> ANDI Пэн: Так, менавіта так памятаю
што бляск масіва

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
І таму ў гэтым сэнсе, пошук
на звязаны спіс заўсёды п.

389
00:20:22,110 --> 00:20:23,040
Гэта заўсёды п.

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
Так пошук лагічны, права,
давайце прадставім, што мы хочам

396
00:20:40,200 --> 00:20:42,820
стварыць функцыю з імем
Пошук, які вяртае сапраўднае

397
00:20:42,820 --> 00:20:46,820
калі вы знайшлі значэнне ўнутры звязаны
спіс, і вяртае ілжывае у адваротным выпадку.

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 п значэнне, што вы
пошук у гэтым спісе.

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
так што гэта пятля, у якой мы
будзе пасля праходжання

409
00:21:22,160 --> 00:21:25,940
астатнія нашым спісе, таму што тое, што
адбываецца, калі паказальнік роўны NULL?

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
>> ANDI Пэн: Роўна, таму мы ведаем, што
мы дасягнулі канца спісу, дакладна?

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
Так што, калі паказальнік паказвае п, калі
паказальнік на п роўны роўны п,

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
і я ў рэшце рэшт атрымаў на гэта, што
паказальнік, які паказвае на NULL,

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
>> Такім чынам, як мы б
ўстаўкі вузлоў, права,

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
>> АЎДЫТОРЫЯ: Гэта дынамічны,
так лягчэй, мэтай якіх

453
00:23:41,110 --> 00:23:43,180
>> ANDI Пэн: Роўна,
так што гэта дынамічны, які

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
і стварыць масіў 1000, гэта
шмат марна памяць, выдзелена.

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
Калі вы разыменовать
паказальнік з галавы да 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
можа разыменовать астатняй спіс.

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-- OK, так

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
Вы заўсёды павінны праверыць, каб убачыць
ці не, што гэта NULL.

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
гэта вернецца NULL для вас.

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
Мы збіраемся зрабіць новы п роўны п.

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
>> Усё, што мы робім, ствараючы новы
вузел, усталяваўшы паказальнік на NULL,

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
можа роду разнаймення
першы паказальнік

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
Хто-небудзь ёсць ідэя аб тым, што гэта
псевдокод, як лагічнае спасылкай

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
>> ANDI Пэн: Роўна, так дакладна
той жа самы працэс, акрамя вас

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
гэта той, які прысвойвае паказальнік.

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
ANDI Пэн: Так.

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
будзе рэалізаваць слоўнік
дзе вы загрузіць больш 140000 слоў

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
Самы просты спосаб захоўвання вас
можна стварыць масіў 140000 слоў

676
00:33:58,910 --> 00:34:03,400
і проста размясціць іх там, і ўсё
затым прайсці іх бінарнага пошуку

677
00:34:03,400 --> 00:34:06,780
ці выбараў ці не--
шкада, што гэта сартаванне.

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
Я ведаю, яблык пачынаецца з
Л-і я дакладна ведаю,

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
>> Усё ясна, як
Функцыя Hash Table працуе?

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
Ваш хэш-значэнне можа быць бясконцым.

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
Вы будзеце мець адзін хэш-значэнне.

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
B, акрамя ягад, банан.

811
00:40:54,726 --> 00:40:55,710
>> АЎДЫТОРЫЯ: Ажына.

812
00:40:55,710 --> 00:40:57,910
>> ANDI Пэн: Blackberry, ажына.

813
00:40:57,910 --> 00:41:00,530
Дзе ажыны ісці сюды?

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
>> ANDI Пэн: Роўна, пасля тут, праўда?

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
І таму, калі я хацеў, каб проста
ўстаўце ажыны тут

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
>> ANDI Пэн: Так ваш хэш
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
пачаць ад А да Z. Але калі вы хочаце
дадаць, мабыць, больш за складанасці

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
вы, хлопцы, просто-- гэта проста
мадэлюецца, каб глядзець, як дрэва.

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
>> Так у вас ёсць карані і
то ў вас ёсць лісце.

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
Замест рэалізацыі двайковы
пошук у масіве памылак,

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
Я проста хачу, каб стварыць што
як мой сярэдзіне, як мой корань,

925
00:46:18,280 --> 00:46:20,770
і тады я буду мець
Значэння выдзяленні з яго.

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
Як вы можаце бачыць, усё гэта
гэта структура вузла

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
Такім чынам, замест проста
які мае х ці папярэдні.

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
мы будзем казаць аб псевдокоде першым.

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
>> ANDI Пэн: Так, менавіта так.

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
І так, то мы можам усталяваць
наш новы корань, каб быць 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
Гэта было проста псевдокод.

990
00:50:15,061 --> 00:50:17,860
ОК, гэта было проста псевдокод,
які з'яўляецца трохі складаным,

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
>> Калі корань п значэнне, таму, калі ён
здараецца, той, які вы глядзіце,

996
00:50:31,376 --> 00:50:34,000
то вы будзеце вяртацца праўда
таму што вы ведаеце вы яго знайшлі.

997
00:50:34,000 --> 00:50:36,250
Але калі значэнне менш
чым корань п, вы

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
Але, магчыма, альтэрнатыўны метад
хэш-табліца з'яўляецца тое, што мы называем сінтаксічнага дрэва.

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
>> Такім чынам, вузел, як мы
будзе вызначаць сінтаксічнага дрэва

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
масіў, так што я ведаю, добра, гэта B слова?

1036
00:52:49,200 --> 00:52:53,010
У гэта не тое слова, так, такім чынам,
Я павінен працягваць пошукі.

1037
00:52:53,010 --> 00:52:56,410
Я іду ад B, і я з нецярпеннем да
паказальнік, які паказвае на B

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
>> І так, то мы глядзім, дзе
паказальнік А кропак,

1046
00:53:17,850 --> 00:53:21,130
і гэта паказвае на адзін спосаб,
якія ў нас ёсць больш значэння захоўваюцца.

1047
00:53:21,130 --> 00:53:24,150
І ў рэшце рэшт, мы атрымліваем
У-А-Т, якая з'яўляецца слова.

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-O-O-M.

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
>> ANDI Пэн: Роўна, мы
хочаце, каб пераканацца, што гэта

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
Так што давайце проста сказаць, што мы хочам, каб ўставіць
слова, ванна, у нашай сінтаксічнага дрэва.

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
паказаў на нуль, таму што мы лічым,
што, ох, няма ніякіх слоў, пасля B-A-T,

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
Калі мы бачым H, мы хочам яго
ісці кудысьці яшчэ.

1111
00:56:30,600 --> 00:56:33,910
>> Тут, мы можам праверыць з так.

1112
00:56:33,910 --> 00:56:38,170
Калі мы трапілі ў H пасля Т, аб,
то мы ведаем, што гэтае слова.

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
Вы спампаваць слоўнікі,
KERS, і тэксты.

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
Мы збіраемся даць вам
140000 слоў у слоўніку.

1157
00:58:48,526 --> 00:58:50,900
Мы збіраемся даць вам тэкст
файл, які мае тыя словы,

1158
00:58:50,900 --> 00:58:54,840
і мы хочам, каб вы маглі арганізаваць
іх у хэш-табліцы або сінтаксічнага дрэва

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
праз масіў 140000 значэнняў.

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
такіх як хэш-табліцы або сінтаксічнага дрэва.

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
Калі вы хочаце зрабіць хэш-табліцу, калі вы
хачу паспрабаваць сінтаксічнага дрэва, цалкам залежыць ад вас.

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
ANDI Пэн: Так, цалкам нармальна.

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
>> ANDI Пэн: Так.

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
Мы на самай справе веяў
праз падзел і сёння.

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