1
00:00:00,000 --> 00:00:03,423
>> [За възпроизвеждане на музика]

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

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

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

5
00:00:11,620 --> 00:00:14,130
следобед на тази прекрасна неделя сутринта.

6
00:00:14,130 --> 00:00:17,330
Благодаря ви за всички, че
се присъедини към мен днес, но сериозно,

7
00:00:17,330 --> 00:00:18,170
аплодисменти.

8
00:00:18,170 --> 00:00:20,600
>> Това е доста голямо усилие.

9
00:00:20,600 --> 00:00:23,600
Аз почти дори не го направи
с течение на времето, но беше ОК.

10
00:00:23,600 --> 00:00:27,520
Така че аз знам, че всички от вас,
Току-що го е направил, за да викторината.

11
00:00:27,520 --> 00:00:30,370
Първо, добре дошли в
обратната страна на това.

12
00:00:30,370 --> 00:00:32,917
>> На второ място, ние ще говорим за това.

13
00:00:32,917 --> 00:00:34,000
Ще говорим за теста.

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

15
00:00:35,700 --> 00:00:36,550
Ще ти мине.

16
00:00:36,550 --> 00:00:39,080
Имам си викторини за
ви в края на тук,

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

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

19
00:00:46,590 --> 00:00:48,430
Както можете да видите, че сме
основно бърза стрелба

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

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

22
00:00:54,380 --> 00:00:59,620
Тя просто ще бъде ми вид крещи
неща, които вие, и ако ви обърка,

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

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

25
00:01:05,200 --> 00:01:07,070
на вашия pset за това
предстоящата седмица, ще

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

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

28
00:01:12,319 --> 00:01:14,610
ОК, така че аз съм просто ще
започнем с някои съобщения.

29
00:01:14,610 --> 00:01:19,070
Ние ще отидем стекове и опашки още в
дълбочина, отколкото това, което направихме преди теста.

30
00:01:19,070 --> 00:01:20,990
Ние ще отидем свързана
изброят отново, за пореден път,

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

32
00:01:23,899 --> 00:01:26,440
И тогава ние ще говорим за хеш
маси, дървета и опит, които

33
00:01:26,440 --> 00:01:28,890
всички са доста необходимо за вашата pset.

34
00:01:28,890 --> 00:01:32,925
И тогава ние ще отидем по някои
полезни съвети за pset5.

35
00:01:32,925 --> 00:01:37,360
>> ОК, така викторина 0.

36
00:01:37,360 --> 00:01:41,090
Средната стойност е 58%.

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

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

39
00:01:46,510 --> 00:01:49,970
>> Доста, правило е, ако сте
в стандартно отклонение от средната стойност

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

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

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

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

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

45
00:02:00,160 --> 00:02:02,243
Обещавам ви, че не сте
Ще успеят класа.

46
00:02:02,243 --> 00:02:03,680
Вие сте напълно добре.

47
00:02:03,680 --> 00:02:06,850
>> За тези от вас, които имам над
средната стойност, впечатляваща, впечатляваща,

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

49
00:02:08,780 --> 00:02:09,689
Аз ги нося със себе си.

50
00:02:09,689 --> 00:02:11,730
Чувствайте се свободни да дойдат да ги получите
в края на раздел.

51
00:02:11,730 --> 00:02:14,520
Нека да знаят, ако имате някакво
въпроси, въпроси с тях.

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

53
00:02:17,204 --> 00:02:21,240
>> ОК, така pset5, това е наистина
странно седмица за Йейл, в смисъл,

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

55
00:02:24,240 --> 00:02:27,317
покойния ден, така че това е всъщност
теоретично поради вторник по обяд.

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

57
00:02:29,150 --> 00:02:30,830
Това е напълно наред.

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

59
00:02:33,700 --> 00:02:36,810
И всички секции тази седмица ще
действително да се превърне в работилници,

60
00:02:36,810 --> 00:02:38,800
да се чувстват свободни да поп в
всеки раздел, което искате,

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

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

63
00:02:45,620 --> 00:02:49,220
Всички други секции ще бъдат фокусирани
изключително на помощ за pset.

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

65
00:02:50,146 --> 00:02:52,000
>> АУДИТОРИЯ: Къде са работно време?

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

67
00:02:56,120 --> 00:03:00,580
Мисля, че работното време тази вечер
са в Teal или най Commons.

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
>> Cool, всички въпроси по отношение на
график за следващия като три дни?

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
OK, това е добре.

94
00:03:56,500 --> 00:04:00,200
>> Така че по същество, колкото можете
снимка на Джак, този човек тук,

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

96
00:04:03,350 --> 00:04:05,750
и той го поставя обратно върху
стека, след като той е направил.

97
00:04:05,750 --> 00:04:07,600
Така че по този начин, той никога
изглежда се

98
00:04:07,600 --> 00:04:10,090
до дъното на
стека в дрехите си.

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

100
00:04:12,600 --> 00:04:16,610
за това как се изпълнява комин.

101
00:04:16,610 --> 00:04:20,060
>> По същество, мисля, че на
стека, както всеки комин на обекти

102
00:04:20,060 --> 00:04:24,900
където можете да постави нещата на върха, и
След това можете да ги извадите от върха.

103
00:04:24,900 --> 00:04:28,600
Така LIFO е съкращение ни харесва
да use-- Last In, First Out.

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
Контрол, 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
И тогава, ако имате нужда от него отново, вие
го натиснете, което е това, което Control-C прави.

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

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

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

124
00:05:31,710 --> 00:05:40,150
>> Така Struct е начинът,
ние всъщност създаде стак.

125
00:05:40,150 --> 00:05:44,720
Ние написали определи структура на, и след това
ние наричаме това поставете на дъното.

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
Размер на инт е на тезгяха, която поддържа
следите колко елемента са в момента

132
00:06:05,660 --> 00:06:07,850
в стека.

133
00:06:07,850 --> 00:06:11,860
Така че тогава ще можем да следим, A,
както колко голям действителната стека е,

134
00:06:11,860 --> 00:06:14,850
и, В, колко от тази купчина
напълнихме, защото ние не искаме

135
00:06:14,850 --> 00:06:18,800
да прелее над това, което е нашата способност.

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

137
00:06:24,340 --> 00:06:28,160
По същество как ще бутнете
върху купчината.

138
00:06:28,160 --> 00:06:28,830
Доста проста.

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

140
00:06:30,621 --> 00:06:32,640
Ако [недоловим] size--
не забравяйте, когато

141
00:06:32,640 --> 00:06:35,300
искате да влезете
параметър в рамките на една структура на,

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
Нека просто кажем, че ще искате да
вмъкнете инт п върху купчината,

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
и ние натиснете инт п върху нея.

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
АНДИ Пенг: Разбира се, така че какво прави
s.size момента ни даде?

163
00:07:45,808 --> 00:07:47,440
АУДИТОРИЯ: Това е текущия размер.

164
00:07:47,440 --> 00:07:50,890
АНДИ Пенг: Точно така, така че
текущия индекс, че нашата размер е най-,

165
00:07:50,890 --> 00:07:57,780
и така искаме да се сложи новото число
че искаме да вмъкнете в s.size.

166
00:07:57,780 --> 00:07:58,760
Това прави ли смисъл?

167
00:07:58,760 --> 00:08:01,110
Защото s.strings, всичко, което
е е името на масива.

168
00:08:01,110 --> 00:08:03,510
Всичко това е с достъп на
масив в рамките на нашата структура на,

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
OK, вие може да си поиграете с него.

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
АНДИ Пенг: Винаги, Аха.

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,
което е, пръв Out.

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

207
00:09:43,705 --> 00:09:46,230
първият, който
излиза от линията.

208
00:09:46,230 --> 00:09:49,680
>> Така че това, което сме искали да наречем това
е dequeueing и enqueueing.

209
00:09:49,680 --> 00:09:52,380
Ако искаме да добавите нещо
в нашия опашка, ние Enqueue.

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

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

212
00:10:03,350 --> 00:10:06,500
може да съхранява определен
неща, но ние можем също

213
00:10:06,500 --> 00:10:10,100
променя, когато ние сме пускането
параметри в тях

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

215
00:10:13,140 --> 00:10:16,700
Така стекове, искахме последният
един, N да бъде първата една навън.

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

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
АНДИ Пенг: Точно така, искате да добавите
то в зависимост от сте го написали.

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
Както вие, момчета, също бяха помолени да
напиша на теста, Enqueue.

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
АНДИ Пенг: Да.

271
00:13:49,506 --> 00:13:56,200
АУДИТОРИЯ: О, не съжалявам.

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

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
кажем ние искахме да се създаде
функция, наречена Enqueue.

298
00:15:40,880 --> 00:15:43,980
Искахме да добавите инт п в която р.

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

306
00:16:08,040 --> 00:16:11,480
Индексът на размер е 0, 1, 2, 3, 4.

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

308
00:16:19,500 --> 00:16:20,920
Какво ни дава това?

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

310
00:16:23,270 --> 00:16:24,080
>> АУДИТОРИЯ: 0.

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

312
00:16:27,870 --> 00:16:30,640
и така искаме да бъде в състояние
да вмъкнете в точно тук.

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

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

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

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

317
00:16:43,170 --> 00:16:44,640
Това прави ли смисъл на всички?

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

319
00:16:48,560 --> 00:16:50,512
дойде в резултат на вашия тест.

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

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

322
00:16:57,800 --> 00:16:59,840
Всеки, който е малко неясно за това?

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

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

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

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

327
00:17:09,970 --> 00:17:15,240
е мястото, където главата ни ще бъде изместване
защото ако бяхме да dequeue,

328
00:17:15,240 --> 00:17:17,030
ние не свалиш края на р.

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

330
00:17:19,130 --> 00:17:24,260
Така че, в резултат, на главата няма да се промени,
и затова, когато Enqueue,

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

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

333
00:17:29,450 --> 00:17:32,740
>> И така, когато dequeue,
Аз също го Псевдокод навън.

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

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

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

337
00:17:39,320 --> 00:17:40,800
Това би било в главата.

338
00:17:40,800 --> 00:17:45,617
>> И сегашните ни размери би
изважда, защото ние вече не

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

340
00:17:46,950 --> 00:17:51,370
Ние имаме само три, а след това ние искаме
да се върне каквато била съхранена в

341
00:17:51,370 --> 00:17:56,260
на главата, защото искаме да се възползвам от тази
стойност, така много подобен на стека.

342
00:17:56,260 --> 00:17:58,010
Просто сте като
от друго място,

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

344
00:18:01,770 --> 00:18:03,890
Логично, всеки се приложи?

345
00:18:03,890 --> 00:18:05,690
Страхотен.

346
00:18:05,690 --> 00:18:10,156
>> ОК, така че ние ще поговорим малко
по-задълбочено за свързани списъци

347
00:18:10,156 --> 00:18:13,280
защото те ще бъдат много, много ценно
за вас в хода на тази седмица

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

349
00:18:14,964 --> 00:18:17,130
Свързани списъци, като вас, момчета
мога да си спомня, всички те са

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

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

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

353
00:18:29,880 --> 00:18:33,569
имат инт п, което е независимо от
стойността в магазин или низ п

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

355
00:18:35,610 --> 00:18:41,482
Struct възел звезда, която е на показалеца
че искате да имате във всеки възел,

356
00:18:41,482 --> 00:18:43,690
започваш да има, че
показалка точка към следващата.

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

358
00:18:48,207 --> 00:18:50,040
Ще имате на главата
на свързан списък, който е

359
00:18:50,040 --> 00:18:53,140
Ще посоча с останалата част от
стойностите така нататък и така нататък

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

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

362
00:18:58,040 --> 00:18:59,952
Това ще посочим
нищожна, и това е, когато

363
00:18:59,952 --> 00:19:01,910
знаеш, че си удари
край на вашия свързан списък

364
00:19:01,910 --> 00:19:04,076
е, когато миналата показалеца
не сочи към нищо.

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

366
00:19:06,670 --> 00:19:10,990
>> Така че ние ще отидем малко по-в
дълбочина по отношение на това как всеки би евентуално

367
00:19:10,990 --> 00:19:12,400
търси свързан списък.

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

369
00:19:15,460 --> 00:19:19,340
стихове масив отношение търсения.

370
00:19:19,340 --> 00:19:22,565
Масивът можете двоично търсене, но
защо да не може да се направи, че в свързан списък?

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

372
00:19:26,834 --> 00:19:30,320
>> АУДИТОРИЯ: Защото всички те са свързани,
но не съвсем знам къде

373
00:19:30,320 --> 00:19:31,330
[Недоловим].

374
00:19:31,330 --> 00:19:34,600
>> АНДИ Пенг: Да, точно така, не забравяйте,
че блясъка на масив

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

376
00:19:37,190 --> 00:19:41,580
ако исках стойността от индекса
шест, бих могъл само да кажа индекс шест,

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

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

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

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

381
00:19:52,820 --> 00:19:56,890
е чрез указател, който ви казва
адреса на къде, че следващия възел е.

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

383
00:20:00,290 --> 00:20:01,560
е линейно търсене.

384
00:20:01,560 --> 00:20:05,890
Защото аз не знам къде точно
12 стойност на свързания списък е,

385
00:20:05,890 --> 00:20:08,780
Аз трябва да премине през цялата
от които свързан списък една

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

387
00:20:12,450 --> 00:20:17,690
по целия път надолу, докато най-накрая да получите
до мястото, където този възел Търся е.

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

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
Списък звезда Node е
В момента само на показалеца

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

400
00:20:52,960 --> 00:20:56,700
инт п е стойността, която сте
търсите в този списък.

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
останалата част от нашия списък, защото това, което
се случва, когато показалеца равнява нула?

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

411
00:21:27,550 --> 00:21:28,450
>> АУДИТОРИЯ: [недоловим]

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

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

414
00:21:34,470 --> 00:21:36,550
и така нататък, и т.н.
докато не се удари в крайна сметка

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

416
00:21:41,589 --> 00:21:43,130
не посочи друго място, освен не.

417
00:21:43,130 --> 00:21:47,510
И така, вие знаете, че в общи линии
вашия списък е все още там нагоре

418
00:21:47,510 --> 00:21:50,900
докато показалеца не е равно
нищожна, защото, след като тя е равна на нула,

419
00:21:50,900 --> 00:21:53,310
знаете ли, че има не повече неща.

420
00:21:53,310 --> 00:21:56,930
>> Така, че е на линия, в която сме
Ще трябва реалното търсене.

421
00:21:56,930 --> 00:22:01,690
И ако pointer-- виждаш
този вид на стрелка функция там?

422
00:22:01,690 --> 00:22:06,930
Така че, ако показалецът пункта до п, ако
показалеца на п равнява равнява п,

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
Pointer равнява показалеца следващата.

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

432
00:22:33,360 --> 00:22:36,580
>> И по същество ти започваш да се просто
прекосяват съвкупността от списъка,

433
00:22:36,580 --> 00:22:41,920
нулиране на показалеца всеки път, докато
в крайна сметка се удари в края на списъка.

434
00:22:41,920 --> 00:22:45,030
А ти знаеш, че не са налице
повече възли, за да търсят сред,

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

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

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

438
00:22:54,530 --> 00:22:57,250
и аз започвам в главата, и
Търся по целия път надолу,

439
00:22:57,250 --> 00:23:00,550
и аз в крайна сметка стигна до това, което
указател, който сочи към нула,

440
00:23:00,550 --> 00:23:04,415
Знам, че, глупости, предполагам, че 10 не е в
този списък, защото аз не можах да го намеря.

441
00:23:04,415 --> 00:23:06,520
И аз съм в края на списъка.

442
00:23:06,520 --> 00:23:11,040
И в този случай ли, че
Отивам да се върне фалшиви.

443
00:23:11,040 --> 00:23:12,900
>> Нека, който се накисва в за малко.

444
00:23:12,900 --> 00:23:17,350
Това ще бъде доста
важно за вашия pset.

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

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

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

448
00:23:25,870 --> 00:23:27,650
Готино.

449
00:23:27,650 --> 00:23:32,560
>> ОК, така че как ще бъде
вмъкване възли, надясно,

450
00:23:32,560 --> 00:23:35,380
в списъка, защото не забравяйте,
какви са това, което на обезщетенията

451
00:23:35,380 --> 00:23:39,230
на наличието на свързан списък сравнение
масив от гледна точка на съхранение?

452
00:23:39,230 --> 00:23:41,110
>> АУДИТОРИЯ: Това е динамичен,
така че е по-лесно to--

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

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

455
00:23:46,880 --> 00:23:56,570
И така, в този смисъл, ние не се нуждаят от
да губите излишно памет, защото аз

456
00:23:56,570 --> 00:24:00,850
ако аз не знам колко стойности искам
до магазина, то няма смисъл за мен

457
00:24:00,850 --> 00:24:04,310
да се създаде масив, защото
ако искам да се съхранява 10 стойности

458
00:24:04,310 --> 00:24:08,380
и аз се създаде масив от 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
ако искате да се вмъкнете в
края, добре, крайният I

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
И ти започваш да бъде като, I
Не знам защо това се случва?

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

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

499
00:26:02,100 --> 00:26:03,344
ще бъде много, много полезен.

500
00:26:03,344 --> 00:26:06,010
Така че можете да напълно да следите
на мястото, където всички ваши указатели са,

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

502
00:26:08,540 --> 00:26:12,660
това, което трябва да направите, за да получите достъп или
вмъкнете или изтриете или към някоя от тях.

503
00:26:12,660 --> 00:26:14,550
Всеки добър с това?

504
00:26:14,550 --> 00:26:15,050
Готино.

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

506
00:26:19,300 --> 00:26:22,600
>> Така че, ако искаме да разгледаме кода?

507
00:26:22,600 --> 00:26:24,470
О, аз не знам дали ние
да разгледате the-- ОК, така че

508
00:26:24,470 --> 00:26:27,940
в горната всичко е е функция
име посочете къде искаме

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

510
00:26:31,365 --> 00:26:32,740
Отиваме да минеш през това.

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

512
00:26:34,770 --> 00:26:36,220
Ще се оправи.

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

514
00:26:39,120 --> 00:26:42,380
какво трябва да направим, особено ако сте
искам тя да не се съхраняват в стека

515
00:26:42,380 --> 00:26:43,920
но в купчината?

516
00:26:43,920 --> 00:26:45,460
Ще отидем до изчистване, нали?

517
00:26:45,460 --> 00:26:48,240
Така че ние ще създадем показалка.

518
00:26:48,240 --> 00:26:52,074
Възел, показалеца, нови равни
изчистване на размера на възел

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

520
00:26:53,740 --> 00:26:56,720
Искаме размера на
памет, която възел заема

521
00:26:56,720 --> 00:26:59,300
ще бъдат разпределени за
изработката на новата възел.

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

523
00:27:02,270 --> 00:27:03,370
Не забравяйте това, което казахме?

524
00:27:03,370 --> 00:27:06,470
Каквото и да изчистване,
какво трябва да правиш винаги?

525
00:27:06,470 --> 00:27:09,490
Винаги трябва да се провери, за да видите
независимо от това дали е нищожна.

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

527
00:27:13,620 --> 00:27:17,060
ако сте имали не повече памет
всички и да се опитате да изчистване,

528
00:27:17,060 --> 00:27:18,410
той ще се върне за нищожна за вас.

529
00:27:18,410 --> 00:27:21,094
И така, ако се опитате да го използвате
когато тя сочеше към нула,

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

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

532
00:27:27,010 --> 00:27:30,500
винаги сте проверка, за да се види дали
че паметта дадено ви е нищожна.

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

534
00:27:33,670 --> 00:27:36,140
>> Така че ние ще
инициализира нов възел.

535
00:27:36,140 --> 00:27:39,050
Ние ще направим нова п равнява п.

536
00:27:39,050 --> 00:27:42,390
И тогава ние ще направим
установяване на нови показалеца на нова

537
00:27:42,390 --> 00:27:46,900
до нула, тъй като в момента не го правим
искам нищо за него да посочи.

538
00:27:46,900 --> 00:27:48,755
Нямаме представа къде
това ще ви постави,

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

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

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

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

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

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

545
00:28:06,320 --> 00:28:09,420
И тогава в главата ще се
сочи към този нов възел.

546
00:28:09,420 --> 00:28:11,060
Всеки OK с това?

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
>> АНДИ Пенг: Точно така, точно така,
същия процес с изключение на вас

575
00:29:23,560 --> 00:29:27,820
Трябва да се намери къде точно сте
Искам тази нова показалка, за да отидат в,

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

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
АНДИ Пенг: Да.

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
Всеки OK с това?

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

620
00:31:31,380 --> 00:31:35,120
>> Така че предполагам, концепция, която ние не сме
Наистина говорихме досега,

621
00:31:35,120 --> 00:31:38,131
и аз предполагам, че вероятно
няма да срещнете много yet--

622
00:31:38,131 --> 00:31:40,880
това е вид напреднал concept--
е, че ние всъщност имаме данни

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

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

625
00:31:46,390 --> 00:31:50,400
действителна стойност, допълнително
показалеца на всеки един от нашите възли

626
00:31:50,400 --> 00:31:52,660
че също така посочва предишния възел.

627
00:31:52,660 --> 00:31:58,170
Така че не само ние имаме
възли сочат към следващата.

628
00:31:58,170 --> 00:32:01,430
Те посочват също с предишния.

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

630
00:32:04,310 --> 00:32:06,740
>> Така че след това имате верига
че може да се движи в двете посоки,

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

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

633
00:32:11,896 --> 00:32:14,520
Трябва да знаете, че този възел е
тази, която имам за преназначаване,

634
00:32:14,520 --> 00:32:17,532
Не мога просто отидете тук и
Просто издърпайте от предишното.

635
00:32:17,532 --> 00:32:19,490
Тогава аз знам точно къде
че е, и след това можете

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

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

638
00:32:22,180 --> 00:32:24,960
>> Но като такива, имат двойно вас
сумата от указатели,

639
00:32:24,960 --> 00:32:26,960
това е в двоен размер на паметта.

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

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

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

643
00:32:34,080 --> 00:32:36,910
>> Така че този тип данни
структура напълно съществува,

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

645
00:32:40,280 --> 00:32:43,850
вместо само указател към следващия,
вие също трябва указател към предишния.

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

647
00:32:45,940 --> 00:32:47,740
Всеки добър с това?

648
00:32:47,740 --> 00:32:48,240
Готино.

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

650
00:32:50,940 --> 00:32:53,280
>> Добре, така че сега аз съм
наистина да прекарат вероятно

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

652
00:32:56,870 --> 00:32:58,360
Говорим за хеш таблици.

653
00:32:58,360 --> 00:33:02,590
Колко от вас, момчета
Прочетох pset5 спец?

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

655
00:33:03,620 --> 00:33:06,160
Това е по-висока от 50% от обикновено.

656
00:33:06,160 --> 00:33:07,560
ОК е.

657
00:33:07,560 --> 00:33:10,345
>> Така че, както вие ще видите,
ти си предизвикателство в pset5

658
00:33:10,345 --> 00:33:16,790
ще бъде изпълнението на речника
когато зареждате над 140,000 думи

659
00:33:16,790 --> 00:33:20,610
че ние ви даваме и правописа проверка
то срещу целия текст.

660
00:33:20,610 --> 00:33:22,580
Ние ще ви дадем случайна
литературни произведения.

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

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

663
00:33:24,561 --> 00:33:26,350
Ние ще ви дадем Остин Пауърс.

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

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

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

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

668
00:33:38,620 --> 00:33:41,970
Първият искате да бъдете
в състояние реално да се зареди

669
00:33:41,970 --> 00:33:43,970
всички думи във вашия
речника, а след това ви

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

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

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

673
00:33:50,790 --> 00:33:52,900
>> Така че предполагам, че най-лесният
начин да направите това, вие

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

675
00:33:55,010 --> 00:33:58,910
Най-лесният начин за съхранение ви е
може да се създаде масив от 140,000 думи

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

677
00:34:03,400 --> 00:34:06,780
или чрез селекции или not--
Съжалявам, че е за сортиране.

678
00:34:06,780 --> 00:34:10,729
Можете да ги сортирате и след това да ги прекосяват
от двоично търсене или просто линейно търсене

679
00:34:10,729 --> 00:34:13,730
и само крайните думите, но това
отнема огромно количество памет,

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

681
00:34:15,190 --> 00:34:18,350
>> И така, ние ще започнем
говорим за начини за печелене

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

683
00:34:20,110 --> 00:34:23,190
А нашата цел е да се получи
константно време, когато

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

685
00:34:25,810 --> 00:34:28,560
Ако исках да търсите за нищо,
Искам да бъда в състояние само,

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

687
00:34:30,810 --> 00:34:34,100
И така структура, в която
ние ще се превръща в непосредствена близост

688
00:34:34,100 --> 00:34:37,569
да бъде в състояние да получите достъп до постоянно
времето, това Свещения Граал

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

690
00:34:41,370 --> 00:34:45,370
И така, Давид вече бе споменато в
[Недоловим] малко в лекция,

691
00:34:45,370 --> 00:34:49,100
но ние ще се вижда
гмуркане в дълбока тази седмица

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

693
00:34:51,780 --> 00:34:53,949
>> Така че начинът, по който хеш
трапезни произведения, например,

694
00:34:53,949 --> 00:35:00,230
ако исках да се съхранява един куп думи,
куп думи на английски език,

695
00:35:00,230 --> 00:35:02,940
Аз теоретично би могла да сложи
банан, ябълка, киви, манго, чифт,

696
00:35:02,940 --> 00:35:04,980
и пъпеш всичко на само един масив.

697
00:35:04,980 --> 00:35:07,044
Те всички да могат да се поберат в и да се намери.

698
00:35:07,044 --> 00:35:09,210
Ще бъде нещо като болки, за да
търси чрез и достъп,

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

700
00:35:12,920 --> 00:35:15,680
наречено хеш таблица, където ние хеш.

701
00:35:15,680 --> 00:35:19,880
В момента тече всички наши ключове чрез
хеш функция, уравнение,

702
00:35:19,880 --> 00:35:22,600
че ги превръща в
някаква стойност

703
00:35:22,600 --> 00:35:28,740
че тогава ние може да съхранява върху
същество масив от свързан списък.

704
00:35:28,740 --> 00:35:32,570
>> И така тук, ако искахме
за съхранение на английски думи,

705
00:35:32,570 --> 00:35:37,250
бихме могли потенциално просто, аз не правя
знам, включете всички първите букви

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

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

708
00:35:43,140 --> 00:35:47,460
или с индекса 0, и
B да бъде синоним с 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
Така че, в смисъл, ако исках да отида, за да
манго, знам, о, тя започва с m.

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

726
00:36:37,134 --> 00:36:38,800
Не е нужно да се търси чрез нищо.

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

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

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

730
00:36:48,380 --> 00:36:50,010
Това е всичко, това е.

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

732
00:36:51,630 --> 00:36:57,690
>> Така че предполагам, ние тичам в
този въпрос на това, което

733
00:36:57,690 --> 00:37:06,390
се случва, ако имате няколко неща
които ти дават един и същ индекс?

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

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

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

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

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

739
00:37:20,910 --> 00:37:25,580
>> Така че, ако се опитам да вмъкнете погребат в хеш
таблица, която вече има банан върху него,

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

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

742
00:37:30,930 --> 00:37:33,800
че искате да го съхранявате инча

743
00:37:33,800 --> 00:37:35,560
Berry вид е като, ах, какво да правя?

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
Знам, OK, аз отивам да вход
то чрез моя хеш функция.

756
00:38:11,220 --> 00:38:15,070
Отивам да се окажете с индекса на
1, а след това аз ще бъда в състояние да имат

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

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

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
>> И тогава ние ще
върнете хеш модул SIZE.

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
Б, различни от зърна, банан.

811
00:40:54,726 --> 00:40:55,710
>> АУДИТОРИЯ: Blackberry.

812
00:40:55,710 --> 00:40:57,910
>> АНДИ Пенг: Blackberry, къпина.

813
00:40:57,910 --> 00:41:00,530
Къде къпина отидете тук?

814
00:41:00,530 --> 00:41:04,251
Е, ние всъщност не са сортирани
това все още, но теоретично

815
00:41:04,251 --> 00:41:06,250
ако искаме да имаме тази
по азбучен ред,

816
00:41:06,250 --> 00:41:07,944
където трябва BlackBerry отидете?

817
00:41:07,944 --> 00:41:09,210
>> АУДИТОРИЯ: [недоловим]

818
00:41:09,210 --> 00:41:11,100
>> АНДИ Пенг: Точно така, след като тук, нали?

819
00:41:11,100 --> 00:41:14,950
Но тъй като това е много трудно да се
reorder-- Предполагам, това е до вас, момчета.

820
00:41:14,950 --> 00:41:17,920
Вие, момчета, може напълно
приложи каквото си искате.

821
00:41:17,920 --> 00:41:20,730
Най-ефикасният начин
за това може би

822
00:41:20,730 --> 00:41:24,570
ще бъде да сортирате свързана
изброят в азбучен ред,

823
00:41:24,570 --> 00:41:26,520
и така, когато сте
вмъкване на нещата, което искате

824
00:41:26,520 --> 00:41:28,632
да не забравяйте да ги вмъкнете
в азбучен ред

825
00:41:28,632 --> 00:41:30,590
така че след това, когато сте
опитвайки се да ги търсите,

826
00:41:30,590 --> 00:41:32,410
че не трябва да преминават всичко.

827
00:41:32,410 --> 00:41:35,290
Вие знаете точно къде
тя е, и това е по-лесно.

828
00:41:35,290 --> 00:41:39,100
>> Но ако има нещо
неща, разпръснати на случаен принцип,

829
00:41:39,100 --> 00:41:41,420
вие все още ще има
да го прекосяват във всеки случай.

830
00:41:41,420 --> 00:41:44,990
И така, ако аз исках просто да си
вмъкнете къпина тук

831
00:41:44,990 --> 00:41:47,470
и аз исках да търси за
го, знам, о, къпина

832
00:41:47,470 --> 00:41:52,012
Трябва да се започне с индекса на 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
OK, ние искаме да се раздели на
като всички азбучен буквите

839
00:42:05,870 --> 00:42:09,040
и след това отново да се харесва друг комплект
на азбучен писма в рамките на този,

840
00:42:09,040 --> 00:42:11,715
ние пускането като хеш
маса в рамките на хеш таблица,

841
00:42:11,715 --> 00:42:13,256
или като функция в рамките на функция?

842
00:42:13,256 --> 00:42:14,880
Или е that--

843
00:42:14,880 --> 00:42:17,510
>> АНДИ Пенг: Така си хеш
function-- си хеш таблица

844
00:42:17,510 --> 00:42:19,360
може да бъде толкова голям, колкото искаш.

845
00:42:19,360 --> 00:42:21,930
Така че в този смисъл, аз мислех,
това е много лесно, много

846
00:42:21,930 --> 00:42:25,320
просто за мен да се основава само на сортиране
на писма от първата дума.

847
00:42:25,320 --> 00:42:28,690
И така, има само 26 възможности.

848
00:42:28,690 --> 00:42:32,650
Мога да получа само 26 възможности от
От 0 до 25, тъй като те могат само

849
00:42:32,650 --> 00:42:36,510
започнете от А до Я. Но Ако искахте
да се добави, може би, по-голяма сложност

850
00:42:36,510 --> 00:42:39,260
или по-бързо тече време, за да си
хеш таблица, вие абсолютно

851
00:42:39,260 --> 00:42:40,760
може да направи най-различни неща.

852
00:42:40,760 --> 00:42:43,330
Можете да направите своя собствена
уравнение, което дава

853
00:42:43,330 --> 00:42:48,000
по разпределение във вашия
думи, а след това, когато търсите,

854
00:42:48,000 --> 00:42:49,300
това ще бъде по-бързо.

855
00:42:49,300 --> 00:42:52,100
>> Това е напълно до вас, момчета
как искате да го привеждат в изпълнение.

856
00:42:52,100 --> 00:42:55,140
Мислете за това като само кофи.

857
00:42:55,140 --> 00:42:57,376
Ако исках да имам
26 кофи, аз отивам

858
00:42:57,376 --> 00:42:59,420
да подреди нещата в тези кофи.

859
00:42:59,420 --> 00:43:02,980
Но аз ще има куп
неща във всяка кофа,

860
00:43:02,980 --> 00:43:05,890
така че, ако искате да го направите
по-бързо и по-ефективно,

861
00:43:05,890 --> 00:43:07,190
нека да има сто кофи.

862
00:43:07,190 --> 00:43:09,290
>> Но тогава ще трябва да измислим
начин да подреди нещата така, че те са

863
00:43:09,290 --> 00:43:11,040
в правилното кофата те трябва да бъдат в.

864
00:43:11,040 --> 00:43:13,331
Но тогава, когато действително
искате да погледнете, че кофа,

865
00:43:13,331 --> 00:43:16,410
това е много по-бързо, защото има
по-малко неща в всяка кофа.

866
00:43:16,410 --> 00:43:20,250
И така, да, това е всъщност
трик за вас, момчета в pset5

867
00:43:20,250 --> 00:43:22,360
е, че вие ​​ще бъдете
изправени пред предизвикателството да създадат само

868
00:43:22,360 --> 00:43:26,170
каквото и да е най-ефективната
функция може да се мисли за

869
00:43:26,170 --> 00:43:28,520
може да съхранява и да провери тези стойности.

870
00:43:28,520 --> 00:43:30,840
>> Totally до вас, момчета
обаче искате да го направя,

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
OK, всеки добре на
веригите и хеш таблици?

880
00:43:58,176 --> 00:44:00,800
Това всъщност е като един много прост
концепция, ако си мислиш за него.

881
00:44:00,800 --> 00:44:05,160
Всичко това е е отделяне на каквото и
Вашите входове са в кофи,

882
00:44:05,160 --> 00:44:10,670
сортирането им, а след това и търсенето в
изброява, че има, свързани с.

883
00:44:10,670 --> 00:44:11,852
>> Готино.

884
00:44:11,852 --> 00:44:18,160
Добре, сега имаме различен вид
на структура от данни, която се нарича дърво.

885
00:44:18,160 --> 00:44:20,850
Нека да продължим и да се говори за опит
които са видимо различен,

886
00:44:20,850 --> 00:44:22,330
но в същата категория.

887
00:44:22,330 --> 00:44:29,010
По същество, всички дърво е вместо
за организиране на данните в линеен начин

888
00:44:29,010 --> 00:44:32,560
че хеш таблица можете does--
знам, тя има горна и долна

889
00:44:32,560 --> 00:44:37,900
и след това някак си създадете връзка на разстояние от един it--
дървото има горна които ти се обадя корена,

890
00:44:37,900 --> 00:44:40,220
и след това го има листа на всички около него.

891
00:44:40,220 --> 00:44:42,390
>> И така, всичко, което имаме тук
е само най-горния възел

892
00:44:42,390 --> 00:44:45,980
който сочи към други възли, които точки
за повече възли, и така нататък и така нататък.

893
00:44:45,980 --> 00:44:48,130
И така, вие просто трябва разделяне клонове.

894
00:44:48,130 --> 00:44:53,255
Това е просто един различен начин на организиране
данни, и тъй като ние го наричаме дърво,

895
00:44:53,255 --> 00:44:56,270
вие just-- това е просто
моделира, за да изглежда като дърво.

896
00:44:56,270 --> 00:44:57,670
Ето защо ние го наричаме дървета.

897
00:44:57,670 --> 00:44:59,370
>> Hash маса прилича на маса.

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
Да, това е, така че аз знам, че Mus търсене
аз п десния показалец на това дърво.

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
>> Cool данни структура, вид
сложна за изпълнение, на възела.

940
00:47:06,310 --> 00:47:08,311
Както можете да видите, всичко
е Struct на възела

941
00:47:08,311 --> 00:47:10,143
е, че имате ляв
и право на показалеца.

942
00:47:10,143 --> 00:47:11,044
Това е всичко, това е.

943
00:47:11,044 --> 00:47:12,960
Така че вместо само
имащ X или предишна.

944
00:47:12,960 --> 00:47:15,920
Имате лявата или право, и след това
можете да вид ги свържем заедно

945
00:47:15,920 --> 00:47:16,836
обаче така решите.

946
00:47:16,836 --> 00:47:21,080

947
00:47:21,080 --> 00:47:24,270
>> OK, ние всъщност ще
Просто отделете няколко минути.

948
00:47:24,270 --> 00:47:25,790
Така че ние ще се върнем тук.

949
00:47:25,790 --> 00:47:28,270
Както казах по-рано,
I вид обяснено

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
>> АНДИ Пенг: Да, точно така.

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
OK, това беше само Псевдокод,
което е малко сложен,

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
>> All синтактично дърво е е
специфичен вид дърво, което

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
Така възелът е Boolean
като вярно или невярно,

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 в моята
масив, и така аз знам, OK, е B дума?

1036
00:52:49,200 --> 00:52:53,010
B не е дума, така че по този начин
Аз трябва да продължавам да търся.

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-- о, на следващия
писмо, в [недоловим] е A.

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
хей, е, че една дума, е B-A дума?

1043
00:53:12,840 --> 00:53:13,807
Това не е дума.

1044
00:53:13,807 --> 00:53:14,890
Ние трябва да продължим да търсим.

1045
00:53:14,890 --> 00:53:17,850
>> И така, след това ние гледаме към мястото, където
показалеца на A точки,

1046
00:53:17,850 --> 00:53:21,130
и го насочва към друг начин в
които ние имаме повече стойност, съхранявана.

1047
00:53:21,130 --> 00:53:24,150
И в крайна сметка, ние се да
B-A-T, която е дума.

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
може просто да се приложи
синтактично дърво, която търси 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-О-О-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-O-O-M?

1077
00:54:58,130 --> 00:54:59,360
>> АУДИТОРИЯ: [недоловим]

1078
00:54:59,360 --> 00:55:01,450
>> АНДИ Пенг: Точно така, ние
искате да се уверите, че това

1079
00:55:01,450 --> 00:55:07,890
тук, че Булева стойност не е
отметнали, че това е вярно.

1080
00:55:07,890 --> 00:55:13,297
Z-О-О, тогава ние отиваме да се провери дали,
така че ние знаем точно, хей, зоологическа градина е дума.

1081
00:55:13,297 --> 00:55:15,380
Отивам да кажа на
компютър, че това е една дума, така

1082
00:55:15,380 --> 00:55:18,000
че когато проверките за компютърни,
той знае, че зоологическа градина е дума.

1083
00:55:18,000 --> 00:55:21,269
>> Защото не забравяйте, всички тези данни
структури, това е много лесно за нас

1084
00:55:21,269 --> 00:55:22,310
да се каже, о, прилеп е една дума.

1085
00:55:22,310 --> 00:55:22,851
Zoo е една дума.

1086
00:55:22,851 --> 00:55:23,611
Zoom е една дума.

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
Както вие може да видите като в момента
всичко, което имаме сега е B-A-T,

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
Защо имаме нужда да се запази
като взе нещата след това T.

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
>> Отиваме да възложи
H, На първо място, тази нищожна,

1108
00:56:22,947 --> 00:56:24,030
отиваме да се отървете от.

1109
00:56:24,030 --> 00:56:26,590
Отиваме да имат
надолу на H момент.

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
All speller.c се е да го вземеш,
товар това, проверява скоростта на това,

1146
00:58:14,290 --> 00:58:19,190
тества бенчмарка на като как
бързо сте в състояние да направи неща.

1147
00:58:19,190 --> 00:58:20,410
>> Това е правопис.

1148
00:58:20,410 --> 00:58:23,920
Просто не се забъркваш с него, но се уверете,
уверете, че разбирате това, което прави.

1149
00:58:23,920 --> 00:58:28,090
Ние използваме функция, наречена getrusage че
тества производителността на правописа

1150
00:58:28,090 --> 00:58:28,590
пул.

1151
00:58:28,590 --> 00:58:32,200
Всички го прави груб теста за
време за всичко във вашия речник,

1152
00:58:32,200 --> 00:58:33,680
така се уверете, че го разбирам.

1153
00:58:33,680 --> 00:58:36,660
Бъдете внимателни, за да не се забъркваш с него или
друг нещата няма да се показват правилно.

1154
00:58:36,660 --> 00:58:39,740

1155
00:58:39,740 --> 00:58:44,170
>> И по-голямата част от това предизвикателство е за
вие наистина да променят dictionary.c.

1156
00:58:44,170 --> 00:58:48,526
Отиваме да ви дам
140,000 думи от речника.

1157
00:58:48,526 --> 00:58:50,900
Отиваме да ви дам един текст
файл, който има тези думи,

1158
00:58:50,900 --> 00:58:54,840
и ние искаме да бъде в състояние да организира
ги в хеш таблица или синтактично дърво

1159
00:58:54,840 --> 00:58:58,140
защото, когато ние ви молим да обяснят
check-- представете си, ако сте на правописа

1160
00:58:58,140 --> 00:59:00,690
проверка като Odyssey Омир.

1161
00:59:00,690 --> 00:59:03,010
Това е като този огромен, огромен тест.

1162
00:59:03,010 --> 00:59:05,190
>> Представете си, ако всеки един
дума, която трябваше да погледне

1163
00:59:05,190 --> 00:59:08,100
чрез масив от 140,000 стойности.

1164
00:59:08,100 --> 00:59:10,350
Това ще отнеме цяла вечност
за вашето устройство, за да се изпълнява.

1165
00:59:10,350 --> 00:59:14,490
Ето защо ние искаме да организираме
данни в по-ефективни структури от данни

1166
00:59:14,490 --> 00:59:17,270
като хеш таблица или синтактично дърво.

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
Вие ще получите един куп думи
които започват с B. До вас

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
в гигантски списък с A думи.

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
Сега единствената дума I
имам е Анди, а сега

1196
01:00:26,897 --> 01:00:29,230
всички други думи в
речника са били загубени.

1197
01:00:29,230 --> 01:00:31,370
И така, вие искате да сте сигурни, че
да следите всичките си указатели

1198
01:00:31,370 --> 01:00:33,661
или иначе ти започваш да се получи
огромни проблеми в кода си.

1199
01:00:33,661 --> 01:00:35,840
Начертайте нещата внимателно стъпка по стъпка.

1200
01:00:35,840 --> 01:00:37,870
Това го прави много по-лесно да се сетиш.

1201
01:00:37,870 --> 01:00:40,910
>> И накрая, вие искате да бъдете в състояние да
тества производителността на вашата програма

1202
01:00:40,910 --> 01:00:41,618
на големия борд.

1203
01:00:41,618 --> 01:00:43,710
Ако вие отнеме
Посетете CS50 точно сега,

1204
01:00:43,710 --> 01:00:45,210
ние имаме това, което се нарича голяма дъска.

1205
01:00:45,210 --> 01:00:50,200
Това е листа с резултатите от най-бързо
правописа пъти проверка във всичките CS50

1206
01:00:50,200 --> 01:00:55,720
точно сега, мисля, че на върха като 10
Часовете Мисля, осем от тях са служители.

1207
01:00:55,720 --> 01:00:57,960
Ние наистина искаме вие ​​да ни бият.

1208
01:00:57,960 --> 01:01:00,870
>> Всички от нас се опитват да приложат
най-бързият кодът е възможно.

1209
01:01:00,870 --> 01:01:04,880
Искаме вие, момчета, за да се опита да оспори
ни и приложат по-бързо от всички нас

1210
01:01:04,880 --> 01:01:05,550
може.

1211
01:01:05,550 --> 01:01:07,970
И така, това е наистина
за първи път, че сме

1212
01:01:07,970 --> 01:01:12,680
ви питам момчета да се направи, че pset
наистина може да направи по какъвто и метод

1213
01:01:12,680 --> 01:01:13,760
искаш.

1214
01:01:13,760 --> 01:01:17,730
>> Винаги съм казвал, че това е по-близко
към разтвор от реалния живот, нали?

1215
01:01:17,730 --> 01:01:19,550
Аз казвам, хей, имам нужда от теб, за да направите това.

1216
01:01:19,550 --> 01:01:21,380
Изграждане на програма, която прави това за мен.

1217
01:01:21,380 --> 01:01:22,630
Направи го обаче искате.

1218
01:01:22,630 --> 01:01:24,271
Просто знам, че искам да постят.

1219
01:01:24,271 --> 01:01:25,770
Това е предизвикателство си за тази седмица.

1220
01:01:25,770 --> 01:01:27,531
Вие, момчета, отиваме
да ви дам задача.

1221
01:01:27,531 --> 01:01:29,030
Отиваме да ви дам едно предизвикателство.

1222
01:01:29,030 --> 01:01:31,559
И тогава това е до вас, момчета
напълно да разбера точно

1223
01:01:31,559 --> 01:01:34,100
каква е бързият и най-
ефективен начин за прилагане на настоящия.

1224
01:01:34,100 --> 01:01:34,600
Да?

1225
01:01:34,600 --> 01:01:37,476
>> АУДИТОРИЯ: Дали сме се оставя да се, ако
Исках да проучи бързи начини

1226
01:01:37,476 --> 01:01:40,821
да се направи хеш таблици онлайн, можем да направим
че и цитират код на някой друг?

1227
01:01:40,821 --> 01:01:42,070
АНДИ Пенг: Да, напълно добре.

1228
01:01:42,070 --> 01:01:44,320
Така че, ако вие прочетете
спец, има ред

1229
01:01:44,320 --> 01:01:48,310
в спецификацията, която казва, вие, момчета,
са напълно безплатни за изследвания хеш

1230
01:01:48,310 --> 01:01:51,070
функции в какви са някои
на по-бързи хеш функции

1231
01:01:51,070 --> 01:01:54,720
да тече нещата като
стига да цитират този код.

1232
01:01:54,720 --> 01:01:57,220
Така че някои хора вече имат
измисли бързи начини

1233
01:01:57,220 --> 01:02:00,250
за правене на правописа, на бързо
начини за съхраняване на информация.

1234
01:02:00,250 --> 01:02:02,750
Totally до вас, момчета, ако
Искам просто да си вземе това, нали?

1235
01:02:02,750 --> 01:02:04,045
Уверете се, че сте цитиране.

1236
01:02:04,045 --> 01:02:06,170
Предизвикателството тук наистина
че ние се опитваме да тествате

1237
01:02:06,170 --> 01:02:09,750
е като се уверите, че знаете
пътя си около Указатели.

1238
01:02:09,750 --> 01:02:12,700
Що ли изпълнителните
действителната разбъркваща функция

1239
01:02:12,700 --> 01:02:15,070
и идва с харесват
по математика, за да направи това,

1240
01:02:15,070 --> 01:02:17,570
вие може да изследват независимо
методи онлайн вас, момчета искат.

1241
01:02:17,570 --> 01:02:17,996
Да?

1242
01:02:17,996 --> 01:02:19,700
>> АУДИТОРИЯ: Можем ли да дам само
с помощта на [недоловим]?

1243
01:02:19,700 --> 01:02:20,120
>> АНДИ Пенг: Да.

1244
01:02:20,120 --> 01:02:22,328
Можете просто, в коментар,
можете да се цитират като, о,

1245
01:02:22,328 --> 01:02:26,127
взета от бала, ала-,
бала, хеш функция.

1246
01:02:26,127 --> 01:02:27,210
Всеки, който има някакви въпроси?

1247
01:02:27,210 --> 01:02:29,694
Ние всъщност breezed
през секция днес.

1248
01:02:29,694 --> 01:02:31,610
Аз ще бъда тук, за да
отговори на въпросите, както добре.

1249
01:02:31,610 --> 01:02:36,570
>> Също така, както вече казах, офис
часа тази вечер и утре.

1250
01:02:36,570 --> 01:02:40,307
Спецификацията тази седмица е всъщност
супер лесно и супер кратък, за да се чете.

1251
01:02:40,307 --> 01:02:43,140
Бих предложил да погледнете, само
прочетете изцяло от него.

1252
01:02:43,140 --> 01:02:45,730
>> И Zamyla всъщност ви разходки
чрез всяка от функциите

1253
01:02:45,730 --> 01:02:49,796
трябва да се прилагат, и затова е
много, много ясно как да се направи всичко.

1254
01:02:49,796 --> 01:02:51,920
Само за да се уверете, че сте
следене на указатели.

1255
01:02:51,920 --> 01:02:53,650
Това е много предизвикателна pset.

1256
01:02:53,650 --> 01:02:56,744
>> Това не е предизвикателство, тъй като,
о, концепциите са толкова много повече

1257
01:02:56,744 --> 01:02:59,160
трудно, или ще трябва да се научат
толкова много нови синтаксис пътя

1258
01:02:59,160 --> 01:03:00,650
че си направил за последен pset.

1259
01:03:00,650 --> 01:03:03,320
Това е трудно, защото pset
има толкова много указатели,

1260
01:03:03,320 --> 01:03:06,980
и след това е много, много лесно да се веднъж
имате грешка в кода си, не е в състояние

1261
01:03:06,980 --> 01:03:08,315
да се намери, когато това е бъг.

1262
01:03:08,315 --> 01:03:13,200
>> И така, пълна и абсолютна вяра в себе си
момчета, за да бъдат в състояние да победи нашата [недоловим]

1263
01:03:13,200 --> 01:03:13,700
правопис.

1264
01:03:13,700 --> 01:03:16,640
Аз всъщност има не всеки писмен мина
все още, но аз съм на път да пиша моя.

1265
01:03:16,640 --> 01:03:19,070
Така че, докато пишете
твоя, аз ще се пишат мина.

1266
01:03:19,070 --> 01:03:21,070
Отивам да се опита да направи
мина по-бързо от твоя.

1267
01:03:21,070 --> 01:03:23,940
Ще видим кой има най-бързия.

1268
01:03:23,940 --> 01:03:27,340
>> И да, аз ще видите всички
вие, момчета, тук във вторник.

1269
01:03:27,340 --> 01:03:29,510
Ще тичам един вид като pset работилница.

1270
01:03:29,510 --> 01:03:32,640
Всички раздели тази
седмица са pset работилници,

1271
01:03:32,640 --> 01:03:36,690
така че вие ​​момчета имате много възможности
за помощ, работно време, както винаги,

1272
01:03:36,690 --> 01:03:41,330
и аз наистина очаквам с нетърпение
четене на всички код вашите момчета.

1273
01:03:41,330 --> 01:03:44,160
Имам викторини до тук, ако
момчета искат да дойдат да получите тези.

1274
01:03:44,160 --> 01:03:45,880
Това е всичко.

1275
01:03:45,880 --> 01:03:48,180