1
00:00:00,000 --> 00:00:00,500

2
00:00:00,500 --> 00:00:05,120
[За възпроизвеждане на музика]

3
00:00:05,120 --> 00:00:12,026

4
00:00:12,026 --> 00:00:12,900
SPEAKER 1: Добре.

5
00:00:12,900 --> 00:00:14,600
Всеки добре дошли обратно към раздел.

6
00:00:14,600 --> 00:00:18,660
Надявам се, че всички вие сте успешно
възстановени от вашия тест

7
00:00:18,660 --> 00:00:19,510
от миналата седмица.

8
00:00:19,510 --> 00:00:22,564
Знам, че е малко луд в пъти.

9
00:00:22,564 --> 00:00:25,230
Както казах и преди, ако сте
в рамките на стандартното отклонение,

10
00:00:25,230 --> 00:00:28,188
наистина не се тревожи за това, особено
за по-малко удобни раздел.

11
00:00:28,188 --> 00:00:30,230
Ето за това къде трябва да бъде.

12
00:00:30,230 --> 00:00:32,850
>> Ако сте направили страхотно, след страхотно.

13
00:00:32,850 --> 00:00:33,650
Слава на вас.

14
00:00:33,650 --> 00:00:36,149
И ако се чувствате като теб трябва
още малко помощ, моля

15
00:00:36,149 --> 00:00:38,140
Чувствайте се свободни да се постигне
от всяка от TFS.

16
00:00:38,140 --> 00:00:40,030
Ние всички сме тук, за да помогнем.

17
00:00:40,030 --> 00:00:40,960
>> Ето защо ние учим.

18
00:00:40,960 --> 00:00:44,550
Ето защо аз съм тук, всеки понеделник за вас
момчета и в офиса часа в четвъртък.

19
00:00:44,550 --> 00:00:48,130
Така че, моля, чувствайте се свободни да ме уведомите
Ако се притеснявате за нищо

20
00:00:48,130 --> 00:00:52,450
или ако има нещо, за викторината
че искате наистина искал да се обърна.

21
00:00:52,450 --> 00:00:56,940
>> Така че в дневния ред за днес е
всичко за структури от данни.

22
00:00:56,940 --> 00:01:01,520
Някои от тях са просто щеше да бъде просто
за да сте запознати с тях.

23
00:01:01,520 --> 00:01:04,870
Вие не може някога изпълнение
тях в този клас.

24
00:01:04,870 --> 00:01:08,690
Някои от тях щете,
като за правопис pset.

25
00:01:08,690 --> 00:01:11,380
>> Вие ще имате избор
между хеш таблици и опитва.

26
00:01:11,380 --> 00:01:13,680
Така че ние със сигурност ще се случва през тези.

27
00:01:13,680 --> 00:01:18,690
Това ще бъде определено по рода
на участък с високо ниво днес, обаче,

28
00:01:18,690 --> 00:01:22,630
защото има много от тях, и ако
отидохме в подробностите по изпълнението

29
00:01:22,630 --> 00:01:26,490
на всички от тях, ние не би
дори да получите чрез свързани списъци

30
00:01:26,490 --> 00:01:28,520
а може би и по-малко на хеш таблици.

31
00:01:28,520 --> 00:01:31,200
>> Така че носят с мен.

32
00:01:31,200 --> 00:01:33,530
Ние няма да правим
колкото кодираща този момент.

33
00:01:33,530 --> 00:01:36,870
Ако имате някакви въпроси относно това
или искате да видите това на практика

34
00:01:36,870 --> 00:01:39,260
или го изпробвате за себе си,
Определено препоръчвам

35
00:01:39,260 --> 00:01:44,250
ще study.cs50.net, които
има примери за всяко от тях.

36
00:01:44,250 --> 00:01:46,400
Ще имам PowerPoints
с бележки, които ние

37
00:01:46,400 --> 00:01:50,860
са склонни да използват, както и някои програмиране
упражнения, особено за неща,

38
00:01:50,860 --> 00:01:55,250
като свързани списъци и двоичен
дървета стекове и знаци.

39
00:01:55,250 --> 00:01:59,590
Така че малко по-високо ниво, което
би било хубаво за вас, момчета.

40
00:01:59,590 --> 00:02:01,320
>> Така че с това, ние ще се стартира.

41
00:02:01,320 --> 00:02:03,060
И също така, yes-- викторини.

42
00:02:03,060 --> 00:02:06,550
Мисля, че повечето от вас, които са в
моята секция има си викторини,

43
00:02:06,550 --> 00:02:12,060
но дойде някой или някаква причина
не, те са точно тук, в предната част.

44
00:02:12,060 --> 00:02:12,740
>> Така свързани списъци.

45
00:02:12,740 --> 00:02:15,650
Знам, че този вид отива
да архивирате преди викторина.

46
00:02:15,650 --> 00:02:17,940
Това беше преди седмица
че сме научили за това.

47
00:02:17,940 --> 00:02:21,040
Но в този случай, ние просто ще
отида малко по-задълбочено.

48
00:02:21,040 --> 00:02:25,900
>> Така че, защо бихме могли да изберем
свързан списък над масив?

49
00:02:25,900 --> 00:02:27,130
Това, което ги отличава?

50
00:02:27,130 --> 00:02:27,630
Да?

51
00:02:27,630 --> 00:02:30,464
>> АУДИТОРИЯ: Може да разширите свързан
изброят срещу фиксиран размер на масива.

52
00:02:30,464 --> 00:02:31,171
SPEAKER 1: Точно така.

53
00:02:31,171 --> 00:02:33,970
Масивът е фиксиран размер има предвид, че
свързан списък е с различен размер.

54
00:02:33,970 --> 00:02:36,970
Така че, ако ние не знаем как
много искаме да се съхранява,

55
00:02:36,970 --> 00:02:39,880
свързан списък ни дава голямо
начин да се направи това, защото ние можем само

56
00:02:39,880 --> 00:02:43,730
добавяне на нов възел и добавяне на
друг възел и добавяне на друг възел.

57
00:02:43,730 --> 00:02:45,750
Но това, което може да е компромис?

58
00:02:45,750 --> 00:02:49,521
Дали някой си спомня компромис
между масиви и свързани списъци?

59
00:02:49,521 --> 00:02:50,020
Mmhmm?

60
00:02:50,020 --> 00:02:51,460
>> АУДИТОРИЯ: Трябва да се
мине през целия път

61
00:02:51,460 --> 00:02:53,738
чрез свързан списък
намиране на елемент в списък.

62
00:02:53,738 --> 00:02:55,570
В масив, можете да
намерите само един елемент.

63
00:02:55,570 --> 00:02:56,278
>> SPEAKER 1: Точно така.

64
00:02:56,278 --> 00:02:57,120
Така че с arrays--

65
00:02:57,120 --> 00:02:58,500
>> АУДИТОРИЯ: [недоловим].

66
00:02:58,500 --> 00:03:01,090
>> SPEAKER 1: С масиви, имаме
това, което се нарича случаен достъп.

67
00:03:01,090 --> 00:03:04,820
Това означава, че ако искаме това, което е
някога петата точка на списък

68
00:03:04,820 --> 00:03:07,230
или петата точка на нашата
масив, можем просто да го вземете.

69
00:03:07,230 --> 00:03:10,440
Ако това е свързан списък, ние имаме
превъртите през, нали?

70
00:03:10,440 --> 00:03:14,020
Така достъп до елемент в
масив е константно време,

71
00:03:14,020 --> 00:03:19,530
като има предвид, с свързания списък би
най-вероятно ще бъде на линейното време, защото може би

72
00:03:19,530 --> 00:03:21,370
нашата елемент е чак в края.

73
00:03:21,370 --> 00:03:23,446
Ние трябва да се търси чрез всичко.

74
00:03:23,446 --> 00:03:25,320
Така че с всички тези данни
структури Отиваме

75
00:03:25,320 --> 00:03:29,330
да се разходите малко повече време на,
какви са плюсовете и минусите.

76
00:03:29,330 --> 00:03:31,480
Когато може да искаме да
използвате една върху друга?

77
00:03:31,480 --> 00:03:34,970
И това е вид на
голям нещо, за да отнемат.

78
00:03:34,970 --> 00:03:40,140
>> Така че ние имаме тук
определяне на възел.

79
00:03:40,140 --> 00:03:43,040
Това е като един елемент в
нашата свързан списък, нали?

80
00:03:43,040 --> 00:03:46,180
Така че всички ние сме запознати
с нашите typedef structs,

81
00:03:46,180 --> 00:03:47,980
който отиде в прегледа за последен път.

82
00:03:47,980 --> 00:03:53,180
Това е в общи линии просто създаване
друг вид данни, които бихме могли да използваме.

83
00:03:53,180 --> 00:03:57,930
>> И в този случай, това е някакъв възел
че ще проведе някои число вътре.

84
00:03:57,930 --> 00:04:00,210
И тогава това, което е втората част тук?

85
00:04:00,210 --> 00:04:03,192

86
00:04:03,192 --> 00:04:05,677
Някой?

87
00:04:05,677 --> 00:04:06,680
>> АУДИТОРИЯ: [недоловим].

88
00:04:06,680 --> 00:04:07,020
>> SPEAKER 1: Да.

89
00:04:07,020 --> 00:04:08,400
Това е указател към следващия възел.

90
00:04:08,400 --> 00:04:12,610
Така че това всъщност трябва да бъде тук.

91
00:04:12,610 --> 00:04:18,790
Това е указател от тип
възел към следващото нещо.

92
00:04:18,790 --> 00:04:22,410
И това е, което те
обхваща нашия възел.

93
00:04:22,410 --> 00:04:24,060
Cool.

94
00:04:24,060 --> 00:04:29,390
>> Добре, така че с търсене, тъй като бяхме
просто казвам, преди ръка, ако сте

95
00:04:29,390 --> 00:04:31,840
ще се търси чрез,
Имате ли наистина да превъртите

96
00:04:31,840 --> 00:04:33,660
чрез вашия свързан списък.

97
00:04:33,660 --> 00:04:38,530
Така че, ако ние не търсим за броя
9, ние ще започне в главата ни

98
00:04:38,530 --> 00:04:41,520
и това ни напомня в началото
на нашия свързан списък, нали?

99
00:04:41,520 --> 00:04:44,600
И ние казваме, добре, прави това
възел съдържа номера 9?

100
00:04:44,600 --> 00:04:45,690
Не?

101
00:04:45,690 --> 00:04:47,500
>> Добре, да отидете на следващия.

102
00:04:47,500 --> 00:04:48,312
Следвайте го.

103
00:04:48,312 --> 00:04:49,520
Дали тя съдържа номера 9?

104
00:04:49,520 --> 00:04:50,570
Не.

105
00:04:50,570 --> 00:04:51,550
Следвайте следващия.

106
00:04:51,550 --> 00:04:55,490
>> Така че ние трябва действително да превъртите
чрез нашата свързан списък.

107
00:04:55,490 --> 00:05:00,070
Не можем просто да отидете директно до мястото, където 9 е.

108
00:05:00,070 --> 00:05:05,860
И ако вие действително искате да
вижте някои псевдо-код там.

109
00:05:05,860 --> 00:05:10,420
Ние имаме някои функция за търсене тук
че отнема in-- какво го взема в?

110
00:05:10,420 --> 00:05:13,110

111
00:05:13,110 --> 00:05:14,320
Какво мислите вие?

112
00:05:14,320 --> 00:05:15,960
Така лесна.

113
00:05:15,960 --> 00:05:17,784
Какво е това?

114
00:05:17,784 --> 00:05:18,700
АУДИТОРИЯ: [недоловим].

115
00:05:18,700 --> 00:05:20,366
SPEAKER 1: Броят търсим.

116
00:05:20,366 --> 00:05:20,980
Така ли е?

117
00:05:20,980 --> 00:05:22,875
И какво би това съответства?

118
00:05:22,875 --> 00:05:25,020
Това е указател към?

119
00:05:25,020 --> 00:05:26,000
>> Аудитория: A възел.

120
00:05:26,000 --> 00:05:28,980
>> SPEAKER 1: A възел към списъка
че ние не търсим в, нали?

121
00:05:28,980 --> 00:05:33,700
Така че ние имаме някои възли са показалецът тук.

122
00:05:33,700 --> 00:05:37,240
Това е момент, който ще
всъщност обхождане чрез нашия списък.

123
00:05:37,240 --> 00:05:39,630
Ние го настроите равна на списък
защото това е просто

124
00:05:39,630 --> 00:05:44,380
създаване то равно на
началото на нашия свързан списък.

125
00:05:44,380 --> 00:05:50,660
>> И докато това не е NULL, докато
ние все още имаме неща в нашия списък,

126
00:05:50,660 --> 00:05:55,580
проверка, за да се види дали този възел има
броя, което търсим.

127
00:05:55,580 --> 00:05:57,740
Назад вярно.

128
00:05:57,740 --> 00:06:01,070
В противен случай, той се актуализира, нали?

129
00:06:01,070 --> 00:06:04,870
>> Ако е NULL, ние се оттегляме нашата
линия, докато и връщане фалшиви

130
00:06:04,870 --> 00:06:08,340
защото това означава, че не сме го намерили.

131
00:06:08,340 --> 00:06:11,048
Всички ли се как се работи?

132
00:06:11,048 --> 00:06:11,548
OK.

133
00:06:11,548 --> 00:06:14,940

134
00:06:14,940 --> 00:06:20,260
>> Така е и с вмъкване, можете
има три различни начина.

135
00:06:20,260 --> 00:06:25,250
Може да се добавя нищо, можете да добавите
и можете да вмъкнете в асорти.

136
00:06:25,250 --> 00:06:28,215
В този случай, ние сме
ще направим сравнява първите.

137
00:06:28,215 --> 00:06:33,380
Някой знае ли как тези
три случая може да се различават?

138
00:06:33,380 --> 00:06:36,920
>> Така сравнява първите означава, че сте поставили
то в предната част на вашия списък.

139
00:06:36,920 --> 00:06:39,770
Така че, това би означавало, че няма значение
какъв е вашият възел е, без значение

140
00:06:39,770 --> 00:06:43,160
каква стойност е, ти започваш
да го пуснат тук отпред, OK?

141
00:06:43,160 --> 00:06:45,160
Това ще бъде първият
елемент във вашия списък.

142
00:06:45,160 --> 00:06:49,510
>> Ако го добавите, че ще
за да отидете на гърба на вашия списък.

143
00:06:49,510 --> 00:06:54,010
И поставете в асорти означава, че сте
ще сложи действително на мястото

144
00:06:54,010 --> 00:06:57,700
където тя продължава да си свързан списък сортиран.

145
00:06:57,700 --> 00:07:00,810
Отново, как да използвате
тези и когато използвате

146
00:07:00,810 --> 00:07:02,530
им ще варира в зависимост от вашия случай.

147
00:07:02,530 --> 00:07:05,834

148
00:07:05,834 --> 00:07:07,750
Ако това не е необходимо да
да се сортира, сравнява първите клони

149
00:07:07,750 --> 00:07:10,460
да бъде това, което повечето хора
използвате, защото не правим

150
00:07:10,460 --> 00:07:15,680
трябва да премине през целия списък
да намерите в края, за да го добавите, нали?

151
00:07:15,680 --> 00:07:17,720
Можете просто да го придържаме полето вътре.

152
00:07:17,720 --> 00:07:21,930
>> Така че ние ще отидем през
вмъкване 1 в момента.

153
00:07:21,930 --> 00:07:26,360
Така че едно нещо, което аз отивам да
Силно препоръчвам на този pset

154
00:07:26,360 --> 00:07:29,820
е да се направи нещата, както винаги.

155
00:07:29,820 --> 00:07:35,130
Това е много важно да се актуализира
Вашите указатели в правилния ред

156
00:07:35,130 --> 00:07:38,620
защото ако ги актуализира
малко от ред,

157
00:07:38,620 --> 00:07:42,210
ти започваш да се окажете
загуба на части от вашия списък.

158
00:07:42,210 --> 00:07:49,680
>> Така например, в този случай, ние сме
казва главата само точка 1.

159
00:07:49,680 --> 00:07:56,070
Ако ние просто направи това
без да записвате това 1,

160
00:07:56,070 --> 00:07:58,570
ние нямаме представа какво
1 трябва да се отбележи сега

161
00:07:58,570 --> 00:08:02,490
защото сме загубили това, което
главата посочи.

162
00:08:02,490 --> 00:08:05,530
Така че едно нещо, което да се помни,
когато правиш на прикрепяне

163
00:08:05,530 --> 00:08:09,630
е да спаси това, което на
главни точки на първата,

164
00:08:09,630 --> 00:08:15,210
След това я прехвърли, и след това да актуализирате
какво ново вашия възел трябва да посочат.

165
00:08:15,210 --> 00:08:20,870

166
00:08:20,870 --> 00:08:22,560
В този случай, това е един от начините да го направя.

167
00:08:22,560 --> 00:08:25,440
>> Така че, ако бяхме го направили по този начин
където ние просто преместени на главата,

168
00:08:25,440 --> 00:08:30,320
ние губим основно ни
Целият списък, нали?

169
00:08:30,320 --> 00:08:38,000
Един от начините да го направите е да има по 1 точка
На следващо място, и след това да има точка на главата до 1.

170
00:08:38,000 --> 00:08:42,650
Или можете да направите нещо като
временно съхранение, което говорихме.

171
00:08:42,650 --> 00:08:45,670
>> Но пренасочване си
указатели в правилния ред

172
00:08:45,670 --> 00:08:48,750
ще бъде много, много
важно за този pset.

173
00:08:48,750 --> 00:08:53,140
В противен случай, вие ще трябва хеш
маса или да опитате, че просто ще се

174
00:08:53,140 --> 00:08:56,014
само част от думите, които ви
искам и след това you're-- mmhmm?

175
00:08:56,014 --> 00:08:58,930
АУДИТОРИЯ: Какво е временната
нещо съхранение сте говориш?

176
00:08:58,930 --> 00:09:00,305
SPEAKER 1: временно съхранение.

177
00:09:00,305 --> 00:09:02,760
Така че основно друг
начина, по който може да направи това

178
00:09:02,760 --> 00:09:07,650
се съхранява главата на нещо като
го съхранява временно променлива.

179
00:09:07,650 --> 00:09:11,250
Присвояване на 1 и
след това да актуализирате 1 до точка

180
00:09:11,250 --> 00:09:13,830
какъвто и да е главата, използвана да посочи.

181
00:09:13,830 --> 00:09:16,920
По този начин е очевидно
по-елегантен, защото

182
00:09:16,920 --> 00:09:20,770
не се нуждаят от временна стойност, но
просто предлага друг начин да го направя.

183
00:09:20,770 --> 00:09:23,999

184
00:09:23,999 --> 00:09:25,790
И ние всъщност имаме
някакъв код за това.

185
00:09:25,790 --> 00:09:28,080
Така че за свързан списък, ние
всъщност има някакъв код.

186
00:09:28,080 --> 00:09:31,930
Така поставете тук, това се поставите символа.

187
00:09:31,930 --> 00:09:34,290
Значи това влиза в главата.

188
00:09:34,290 --> 00:09:38,820
>> Така че първото нещо, което трябва да
създадете своя нов възел, разбира се,

189
00:09:38,820 --> 00:09:40,790
и да се провери за NULL.

190
00:09:40,790 --> 00:09:43,250
Винаги добра.

191
00:09:43,250 --> 00:09:47,840
И тогава ще трябва да зададете стойностите.

192
00:09:47,840 --> 00:09:51,260
Всеки път, когато се създаде нов възел, вие
Не знам какво е, сочещи към следващия,

193
00:09:51,260 --> 00:09:54,560
така че искам да го инициализира с NULL.

194
00:09:54,560 --> 00:09:58,760
Ако все пак в крайна сметка посочи нещо
друго, той се преотстъпва и това е добре.

195
00:09:58,760 --> 00:10:00,740
Ако това е първото нещо,
в списъка, тя се нуждае от

196
00:10:00,740 --> 00:10:04,270
да сочи към NULL защото
това е края на списъка.

197
00:10:04,270 --> 00:10:12,410
>> Така че след това да я поставите, ние виждаме тук
се възлагане на следващата стойност на нашата възел

198
00:10:12,410 --> 00:10:17,380
да бъде каквото и да е главата,
което е това, което имахме тук.

199
00:10:17,380 --> 00:10:19,930
Това е, което ние просто го направих.

200
00:10:19,930 --> 00:10:25,820
И тогава ние сме възлагане главата до точка
в нашия нов възел, защото си спомням,

201
00:10:25,820 --> 00:10:31,090
нов някои указател към възел,
и това е точно това, което е на главата.

202
00:10:31,090 --> 00:10:34,370
Това е точно защо ние
имат тази стрелка Accessor.

203
00:10:34,370 --> 00:10:37,030

204
00:10:37,030 --> 00:10:37,530
Cool?

205
00:10:37,530 --> 00:10:38,130
Mmhmm?

206
00:10:38,130 --> 00:10:41,100
>> АУДИТОРИЯ: Трябва ли да
инициализира нов до NULL първо,

207
00:10:41,100 --> 00:10:44,240
или можем просто да го инициализира с глава?

208
00:10:44,240 --> 00:10:48,210
>> SPEAKER 1: New следващия
трябва да бъде NULL за да започнете

209
00:10:48,210 --> 00:10:53,760
защото не знаете
къде ще бъде.

210
00:10:53,760 --> 00:10:56,100
Също така, това е един вид
Точно като парадигма.

211
00:10:56,100 --> 00:10:59,900
Можете да го настроите, равен на NULL, само за да направи
сигурни, че всички ваши бази са покрити

212
00:10:59,900 --> 00:11:04,070
преди да направите всяко пренасочване, така че
сте винаги е гарантирано, че ще

213
00:11:04,070 --> 00:11:08,880
да се посочи конкретна стойност
спрямо като стойност за боклук.

214
00:11:08,880 --> 00:11:12,210
Защото, да, ние присвоите
Новият следващия автоматично,

215
00:11:12,210 --> 00:11:15,420
но това е по-точно като
Добра практика е да го инициализира

216
00:11:15,420 --> 00:11:19,270
по този начин и след това пренасочване.

217
00:11:19,270 --> 00:11:23,420
>> ОК, така че двойно свързан списък сега.

218
00:11:23,420 --> 00:11:24,601
Какво мислите?

219
00:11:24,601 --> 00:11:26,350
Какво е по-различно с
двойно свързан списък?

220
00:11:26,350 --> 00:11:30,750

221
00:11:30,750 --> 00:11:34,300
>> Така че в нашите свързани списъци, ние можем
се движи само в една посока, нали?

222
00:11:34,300 --> 00:11:35,270
Ние имаме само следващия.

223
00:11:35,270 --> 00:11:36,760
Можем само да се върви напред.

224
00:11:36,760 --> 00:11:40,300
>> С двойно свързан списък,
ние също може да се движи назад.

225
00:11:40,300 --> 00:11:44,810
Така че ние имаме не само
номер, който ние искаме да се съхранява,

226
00:11:44,810 --> 00:11:50,110
имаме къде да сочи към следващия
и къде точно идва.

227
00:11:50,110 --> 00:11:52,865
Така че това дава възможност за
някои по-добре прекосява.

228
00:11:52,865 --> 00:11:56,620

229
00:11:56,620 --> 00:12:01,240
>> Така двойно свързани възли,
много подобно, нали?

230
00:12:01,240 --> 00:12:05,000
Единствената разлика сега е, че ние
има следващата и предишната.

231
00:12:05,000 --> 00:12:06,235
Това е единствената разлика.

232
00:12:06,235 --> 00:12:09,570

233
00:12:09,570 --> 00:12:14,790
>> Така че, ако бяхме да се добавя нищо append-- ние
не оказват код за това до here--

234
00:12:14,790 --> 00:12:17,830
но ако ви се налага да се опита и
поставете го, важното

235
00:12:17,830 --> 00:12:19,980
е, че трябва да се направи
уверете, че сте възлагане

236
00:12:19,980 --> 00:12:23,360
както предишния си и си
следващата показалеца правилно.

237
00:12:23,360 --> 00:12:29,010
Така че в този случай, бихте
не само се инициализира следващия,

238
00:12:29,010 --> 00:12:31,820
нулирате предишния.

239
00:12:31,820 --> 00:12:36,960
Ако ние сме в началото на списъка, ние
не само ще направи главата равен нова,

240
00:12:36,960 --> 00:12:41,750
но нашата нова предходната трябва
точка на главата, нали?

241
00:12:41,750 --> 00:12:43,380
>> Това е единствената разлика.

242
00:12:43,380 --> 00:12:47,200
И, ако искате повече практика с
тези със свързани списъци, с вмъкване,

243
00:12:47,200 --> 00:12:49,900
с изтриване, с вложка
в един разнообразен списък,

244
00:12:49,900 --> 00:12:52,670
моля, проверете study.cs50.net.

245
00:12:52,670 --> 00:12:54,870
Има един куп страхотни упражнения.

246
00:12:54,870 --> 00:12:55,870
Аз силно ги препоръчвам.

247
00:12:55,870 --> 00:12:59,210
Иска ми се да имах време да мине през тях
но има много структури от данни

248
00:12:59,210 --> 00:13:01,530
да се измъкне сам.

249
00:13:01,530 --> 00:13:02,650
>> ОК, така че хеш таблици.

250
00:13:02,650 --> 00:13:07,070
Това е може би най-
полезна малко за вашия pset

251
00:13:07,070 --> 00:13:11,090
тук, защото започваш да бъде
изпълнението на една от тях, или да опитате.

252
00:13:11,090 --> 00:13:12,200
Аз наистина харесвам хеш таблици.

253
00:13:12,200 --> 00:13:13,110
Те са много готино.

254
00:13:13,110 --> 00:13:17,080
>> Така че основно това, което
се случва, е хеш таблица

255
00:13:17,080 --> 00:13:22,050
е, когато ние наистина се нуждаят от бързо
вмъкване, изтриване и търсене.

256
00:13:22,050 --> 00:13:25,010
Това са неща, които ние сме
приоритизиране в хеш таблица.

257
00:13:25,010 --> 00:13:29,500
Те могат да получат доста големи,
но както ще видим с опит

258
00:13:29,500 --> 00:13:33,040
има неща, които са много по-големи.

259
00:13:33,040 --> 00:13:38,330
>> Но общо взето, всички хеш
маса е функция хашиш

260
00:13:38,330 --> 00:13:47,215
който ви казва, който кофа да постави всеки
на данните си, всеки един от вашите елементи вътре.

261
00:13:47,215 --> 00:13:51,140
Един прост начин да се мисли за хеш таблица
е, че тя е само на кофи с неща,

262
00:13:51,140 --> 00:13:51,770
нали?

263
00:13:51,770 --> 00:13:59,720
Така че, когато се сортиране неща от
като първата буква от името си,

264
00:13:59,720 --> 00:14:01,820
това е нещо като хеш таблица.

265
00:14:01,820 --> 00:14:06,180
>> Така че, ако бях на мястото на група момчета е
в групи от който започва името

266
00:14:06,180 --> 00:14:11,670
с A тук, или който и да е рожден ден
е през януари, февруари, март,

267
00:14:11,670 --> 00:14:15,220
независимо, че е ефективно
създаване на хеш таблица.

268
00:14:15,220 --> 00:14:18,120
Това е просто създаване на кофи, че
Вие сами си елементи в

269
00:14:18,120 --> 00:14:19,520
така че можете да ги намерите по-лесно.

270
00:14:19,520 --> 00:14:22,300
Така че по този начин, когато имам нужда
да се намери един от вас,

271
00:14:22,300 --> 00:14:24,680
Не е нужно да търсите
през всяка от вашите имена.

272
00:14:24,680 --> 00:14:29,490
I може да бъде като, о, аз знам, че
Рожден ден на Даниел е in--

273
00:14:29,490 --> 00:14:30,240
АУДИТОРИЯ: --April.

274
00:14:30,240 --> 00:14:30,948
SPEAKER 1: Април.

275
00:14:30,948 --> 00:14:33,120
Така че аз гледам в моята април
кофа, и с малко късмет,

276
00:14:33,120 --> 00:14:38,270
тя ще бъде само един там и
времето ми е постоянно в този смисъл,

277
00:14:38,270 --> 00:14:41,230
като има предвид, ако трябва да погледнем
през един куп хора,

278
00:14:41,230 --> 00:14:43,090
това ще отнеме много повече време.

279
00:14:43,090 --> 00:14:45,830
Така хеш таблици са наистина само кофи.

280
00:14:45,830 --> 00:14:48,630
Лесен начин да се мисли за тях.

281
00:14:48,630 --> 00:14:52,930
>> Така че е много важно нещо за
хеш таблица е хеш функция.

282
00:14:52,930 --> 00:14:58,140
Така че нещата, аз просто говори, като
Вашето първо писмо на първата си име

283
00:14:58,140 --> 00:15:01,450
или вашия рожден ден месец
Това са идеи, които

284
00:15:01,450 --> 00:15:03,070
наистина корелира с хеш функция.

285
00:15:03,070 --> 00:15:08,900
Това е просто начин на вземане на решение, което
вие сте кофа елемент отива в, OK?

286
00:15:08,900 --> 00:15:14,850
Така че за това pset, можете да погледнете нагоре
почти всеки хеш функция, която желаете.

287
00:15:14,850 --> 00:15:16,030
>> Не трябва да бъде себе си.

288
00:15:16,030 --> 00:15:21,140
Има някои наистина готини хора от
там, които правят всички видове луд математика.

289
00:15:21,140 --> 00:15:25,170
А ако искате да направите вашия
проверка на правописа супер бързо,

290
00:15:25,170 --> 00:15:27,620
Определено бих
гледам в един от тях.

291
00:15:27,620 --> 00:15:32,390
>> Но има също така
прости, като изчислителна

292
00:15:32,390 --> 00:15:39,010
сумата на думите, като
всяка буква има номер.

293
00:15:39,010 --> 00:15:39,940
Изчислете сумата.

294
00:15:39,940 --> 00:15:42,230
Това определя кофата.

295
00:15:42,230 --> 00:15:45,430
Те също така имат лесни тези, които
са точно като всички от A-те тук,

296
00:15:45,430 --> 00:15:47,050
всички от B е тук.

297
00:15:47,050 --> 00:15:48,920
Всеки един от тези.

298
00:15:48,920 --> 00:15:55,770
>> По принцип, той просто ви казва, който
индекс масив вашия елемент трябва да отидат в.

299
00:15:55,770 --> 00:15:58,690
Просто решаването на bucket--
всичко е функция на хашиш е.

300
00:15:58,690 --> 00:16:04,180
Така че тук имаме пример, който е
само първата буква на низ

301
00:16:04,180 --> 00:16:05,900
че аз просто се говори.

302
00:16:05,900 --> 00:16:11,900
>> Така че имате някакъв хеш това е просто
първата буква на низ минус A,

303
00:16:11,900 --> 00:16:16,090
който ще ви даде някои
число между 0 и 25 години.

304
00:16:16,090 --> 00:16:20,790
И това, което искате да направите, е
уверете се, че това представлява

305
00:16:20,790 --> 00:16:24,110
размера на хеш table--
колко кофи са там.

306
00:16:24,110 --> 00:16:25,860
С много от тях
хеш функции, те са

307
00:16:25,860 --> 00:16:31,630
ще се върне ценности, които биха могли
е далеч над броя на кофи

308
00:16:31,630 --> 00:16:33,610
че всъщност трябва
в хеш таблица,

309
00:16:33,610 --> 00:16:37,240
така че трябва да се направи
сигурен и моден от тях.

310
00:16:37,240 --> 00:16:42,190
В противен случай, той ще каже,
О, тя трябва да бъде в кофа 5000

311
00:16:42,190 --> 00:16:46,040
но имате само 30
кофи във вашия хеш таблица.

312
00:16:46,040 --> 00:16:49,360
И разбира се, ние всички знаем, че е
ще доведе до някои луди грешки.

313
00:16:49,360 --> 00:16:52,870
Така че не забравяйте да мод от
размер на вашия хеш таблица.

314
00:16:52,870 --> 00:16:58,430

315
00:16:58,430 --> 00:16:58,930
Cool.

316
00:16:58,930 --> 00:17:00,506
Така сблъсъци.

317
00:17:00,506 --> 00:17:02,620
Хубаво ли всички досега?

318
00:17:02,620 --> 00:17:03,120
Mmhmm?

319
00:17:03,120 --> 00:17:05,900
>> АУДИТОРИЯ: Защо би го
се върне като масивна стойност?

320
00:17:05,900 --> 00:17:09,210
>> SPEAKER 1: В зависимост от алгоритъма
че си хеш функция използва.

321
00:17:09,210 --> 00:17:12,270
Някои от тях ще направя
луд умножение.

322
00:17:12,270 --> 00:17:16,270
И това е всичко, за получаване на
с равномерно разпределение,

323
00:17:16,270 --> 00:17:18,490
така че те да се направят някои наистина
луди неща понякога.

324
00:17:18,490 --> 00:17:20,960
Това е всичко.

325
00:17:20,960 --> 00:17:22,140
Нещо друго?

326
00:17:22,140 --> 00:17:22,829
OK.

327
00:17:22,829 --> 00:17:24,480
>> Така сблъсъци.

328
00:17:24,480 --> 00:17:29,270
По принцип, както казах по-рано,
в най-добрия случай,

329
00:17:29,270 --> 00:17:32,040
всяка кофа гледам в е
ще има едно нещо,

330
00:17:32,040 --> 00:17:34,160
така че не е нужно да разгледаме всички, нали?

331
00:17:34,160 --> 00:17:37,040
Аз нито знам, че е там, или това е
Не, и това е, което наистина искаме.

332
00:17:37,040 --> 00:17:43,960
Но ако имаме десетки хиляди
точки на данни и по-малко от този брой

333
00:17:43,960 --> 00:17:48,700
кофи, ние ще имаме
сблъсъци, където в крайна сметка нещо

334
00:17:48,700 --> 00:17:54,210
ще трябва да се окажете в
кофа, която вече има елемент.

335
00:17:54,210 --> 00:17:57,390
>> Така че въпросът е, какво
правим в този случай?

336
00:17:57,390 --> 00:17:58,480
Какво ще правим?

337
00:17:58,480 --> 00:17:59,300
Ние вече имаме нещо там?

338
00:17:59,300 --> 00:18:00,060
Да, ние просто го хвърли?

339
00:18:00,060 --> 00:18:00,700
>> Не.

340
00:18:00,700 --> 00:18:01,980
Ние трябва да поддържаме и двете от тях.

341
00:18:01,980 --> 00:18:06,400
Така начина, по който
обикновено се прави това е какво?

342
00:18:06,400 --> 00:18:08,400
Каква е структурата на данните
ние просто говорихме?

343
00:18:08,400 --> 00:18:09,316
АУДИТОРИЯ: свързан списък.

344
00:18:09,316 --> 00:18:10,500
SPEAKER 1: свързан списък.

345
00:18:10,500 --> 00:18:16,640
Така че сега, вместо на всеки от тях
кофи само с един елемент,

346
00:18:16,640 --> 00:18:24,020
тя ще съдържа свързан списък на
елементите, които са хеширани в нея.

347
00:18:24,020 --> 00:18:27,588
OK, може всеки вид получите тази идея?

348
00:18:27,588 --> 00:18:30,546
Защото не може да има масив
защото ние не знаем колко много неща

349
00:18:30,546 --> 00:18:31,730
ще бъде там.

350
00:18:31,730 --> 00:18:36,540
A свързан списък ни позволява да
Трябва просто точния брой, че

351
00:18:36,540 --> 00:18:38,465
се сегментира в тази кофа, нали?

352
00:18:38,465 --> 00:18:42,260

353
00:18:42,260 --> 00:18:50,500
>> Така линейни сондиране е
основно това idea--

354
00:18:50,500 --> 00:18:52,300
това е един от начините за справяне с евентуален сблъсък.

355
00:18:52,300 --> 00:18:58,010
Какво можете да направите, е, ако в този
случай, Бери се сегментира в 1

356
00:18:58,010 --> 00:19:01,130
и ние вече имаме
нещо там, просто

357
00:19:01,130 --> 00:19:04,840
продължавай, докато
можете да намерите на празен слот.

358
00:19:04,840 --> 00:19:06,370
Това е един от начините да се справя.

359
00:19:06,370 --> 00:19:09,020
Другият начин да се справят с
е с това, което току-що

360
00:19:09,020 --> 00:19:12,280
called-- Свързаните
списък се нарича извикване.

361
00:19:12,280 --> 00:19:20,510
>> Така че тази идея работи, ако
Вашата хеш таблица мислите

362
00:19:20,510 --> 00:19:24,150
е много по-голям от
определени вашите данни или ако

363
00:19:24,150 --> 00:19:28,870
искате да опитате и да се минимизира верижното
докато не е абсолютно необходимо.

364
00:19:28,870 --> 00:19:34,050
Така че едно нещо е линейна
сондиране очевидно означава

365
00:19:34,050 --> 00:19:37,290
че си хеш функция
не е чак толкова полезен

366
00:19:37,290 --> 00:19:42,200
защото вие ще се окажете с помощта
Вашата функция хашиш, Как да стигнем до точката,

367
00:19:42,200 --> 00:19:46,400
можете линейни сонда до
известно място, което е на разположение.

368
00:19:46,400 --> 00:19:49,670
Но сега, разбира се, нищо
друго, което завършва там,

369
00:19:49,670 --> 00:19:52,050
вие ще трябва да
търсите, дори още по-надолу.

370
00:19:52,050 --> 00:19:55,650
>> И там е много по-
Разходи за търсене,

371
00:19:55,650 --> 00:19:59,820
отива в въвеждане елемент
в хеш таблица, сега, нали?

372
00:19:59,820 --> 00:20:05,640
И сега, когато отидете и се опитайте да намерите
Бери отново, ти започваш да го хеш,

373
00:20:05,640 --> 00:20:07,742
и то се случва да се каже,
О, погледнете в кофа 1,

374
00:20:07,742 --> 00:20:09,700
и това няма да бъде
в кофа 1, така че вие ​​сте

375
00:20:09,700 --> 00:20:11,970
ще трябва да преминават
през останалата част от тях.

376
00:20:11,970 --> 00:20:17,720
Така че понякога е полезно,
но в повечето случаи,

377
00:20:17,720 --> 00:20:22,660
ние ще кажем, че
верижното е това, което искам да правя.

378
00:20:22,660 --> 00:20:25,520
>> Така че ние говорихме за това по-рано.

379
00:20:25,520 --> 00:20:27,812
Аз имам малко по-напред от себе си.

380
00:20:27,812 --> 00:20:33,560
Но верижното е основно, че
всяка кофа в хеш таблица

381
00:20:33,560 --> 00:20:36,120
е просто свързан списък.

382
00:20:36,120 --> 00:20:39,660
>> Така че по друг начин, или по-технически
начин да се мисли за хеш таблица

383
00:20:39,660 --> 00:20:44,490
е, че това е просто масив
на свързани списъци, които

384
00:20:44,490 --> 00:20:49,330
когато пишете си речник
а вие се опитвате да го заредите,

385
00:20:49,330 --> 00:20:52,070
мисля за него като за
масив от свързани списъци

386
00:20:52,070 --> 00:20:54,390
ще го направи много по-лесно
за да можете да се инициализира.

387
00:20:54,390 --> 00:20:57,680
>> АУДИТОРИЯ: Така хеш таблица
има предварително определен размер,

388
00:20:57,680 --> 00:20:58,980
като [недоловим] от кофи?

389
00:20:58,980 --> 00:20:59,220
>> SPEAKER 1: Точно така.

390
00:20:59,220 --> 00:21:01,655
Така че има определен брой
кофи, че determine--

391
00:21:01,655 --> 00:21:03,530
които вие трябва да
Чувствайте се свободни да се играе с тях.

392
00:21:03,530 --> 00:21:05,269
Тя може да бъде доста хладно
да видим какво ще стане

393
00:21:05,269 --> 00:21:06,810
като промените вашия номер на кофи.

394
00:21:06,810 --> 00:21:09,410

395
00:21:09,410 --> 00:21:11,510
Но да, той има
номер на кофи.

396
00:21:11,510 --> 00:21:15,360
Какво Ви дава възможност да се поберат като
много елементи, от които се нуждаете

397
00:21:15,360 --> 00:21:19,350
е този отделен верижното ви, където
са свързани списъци във всяка кофа.

398
00:21:19,350 --> 00:21:22,850
Това означава, че вашият хеш таблица
ще бъде точно на размера

399
00:21:22,850 --> 00:21:25,440
че имате нужда от него, за да бъде, нали?

400
00:21:25,440 --> 00:21:27,358
Това е целият смисъл на свързани списъци.

401
00:21:27,358 --> 00:21:30,850

402
00:21:30,850 --> 00:21:32,480
Cool.

403
00:21:32,480 --> 00:21:38,780
>> Така че всеки OK там?

404
00:21:38,780 --> 00:21:39,801
Добре.

405
00:21:39,801 --> 00:21:40,300
Ah.

406
00:21:40,300 --> 00:21:41,860
Какво точно се случи?

407
00:21:41,860 --> 00:21:42,960
Наистина сега.

408
00:21:42,960 --> 00:21:45,250
Предполагам, някой ме убива.

409
00:21:45,250 --> 00:21:52,060
>> ОК, ние ще отидем в
опит, които са малко луди.

410
00:21:52,060 --> 00:21:53,140
Обичам хеш таблици.

411
00:21:53,140 --> 00:21:54,460
Мисля, че те са наистина страхотно.

412
00:21:54,460 --> 00:21:56,710
Опитва са готини, също.

413
00:21:56,710 --> 00:21:59,590
>> Така че няма кой да си спомня какво пробвам е?

414
00:21:59,590 --> 00:22:01,740
Вие трябва да са преминали през
то за кратко в лекция?

415
00:22:01,740 --> 00:22:04,570

416
00:22:04,570 --> 00:22:06,377
Спомняте ли си вид на това как тя работи?

417
00:22:06,377 --> 00:22:08,460
АУДИТОРИЯ: Аз съм просто кимаше
че мина над него.

418
00:22:08,460 --> 00:22:09,626
SPEAKER 1: Ние трябва да излизат над него.

419
00:22:09,626 --> 00:22:13,100
ОК, ние сме наистина ще отида
над него сега е това, което казва.

420
00:22:13,100 --> 00:22:14,860
>> АУДИТОРИЯ: Това е за извличане на дърво.

421
00:22:14,860 --> 00:22:15,280
>> SPEAKER 1: Да.

422
00:22:15,280 --> 00:22:16,196
Това е извличане на дърво.

423
00:22:16,196 --> 00:22:16,960
Awesome.

424
00:22:16,960 --> 00:22:23,610
Така че едно нещо, което трябва да отбележим е, че ние
търсите в отделните герои

425
00:22:23,610 --> 00:22:24,480
тук, нали?

426
00:22:24,480 --> 00:22:29,710
>> Така че, преди с нашата хеш функция, ние
Гледаха думите като цяло,

427
00:22:29,710 --> 00:22:32,270
а сега ние търсим повече
на героите, нали?

428
00:22:32,270 --> 00:22:38,380
Така че ние имаме Maxwell тук и Мендел.

429
00:22:38,380 --> 00:22:47,840
Така че основно try-- начин да се мисли
за това е, че всяко ниво тук

430
00:22:47,840 --> 00:22:49,000
е набор от букви.

431
00:22:49,000 --> 00:22:53,310

432
00:22:53,310 --> 00:22:55,790
Така че това е вашият корен възел тук, нали?

433
00:22:55,790 --> 00:23:01,980
Това има всички символи на
азбука за началото на всяка дума.

434
00:23:01,980 --> 00:23:06,480
>> И това, което искате да направите, е
да речем, ОК, ние имаме някои M дума.

435
00:23:06,480 --> 00:23:10,590
Отиваме да търсим Максуел, така
отиваме на М. И М пункта до цяло

436
00:23:10,590 --> 00:23:14,800
друг масив, където всеки
дума, докато има

437
00:23:14,800 --> 00:23:17,044
е дума, която има
като втората буква,

438
00:23:17,044 --> 00:23:19,460
толкова дълго, тъй като има една дума, която
има B като втората буква,

439
00:23:19,460 --> 00:23:24,630
тя ще има указател
става до известна следващия масив.

440
00:23:24,630 --> 00:23:29,290
>> Вероятно не е
дума, която MP нещо,

441
00:23:29,290 --> 00:23:32,980
така че в позиция Р в този
масив, тя просто ще бъде NULL.

442
00:23:32,980 --> 00:23:38,840
Той би казал, OK, няма дума
че е M последвано от P, OK?

443
00:23:38,840 --> 00:23:43,100
Така че, ако ние мислим за това, всеки
един от тези малки неща

444
00:23:43,100 --> 00:23:47,990
всъщност е един от тях
големи масиви от А до Z.

445
00:23:47,990 --> 00:23:55,064
Така че това, което може да бъде едно от нещата,
това е един вид недостатък на опит?

446
00:23:55,064 --> 00:23:56,500
>> Аудитория: A много памет.

447
00:23:56,500 --> 00:23:59,940
>> SPEAKER 1: Това е един тон на паметта, нали?

448
00:23:59,940 --> 00:24:08,750
Всеки един от тези блокове тук
представлява 26 места, 26 елемент масив.

449
00:24:08,750 --> 00:24:13,680
Така че се опитва да получите невероятно пространство тежък.

450
00:24:13,680 --> 00:24:17,100
>> Но те са много бързи.

451
00:24:17,100 --> 00:24:22,540
Така невероятно бързо, но
наистина пространство неефективна.

452
00:24:22,540 --> 00:24:24,810
Нещо трябва да разбера
кои точно искате.

453
00:24:24,810 --> 00:24:29,470
Това са наистина страхотно за вашата pset,
но те не заемат много памет,

454
00:24:29,470 --> 00:24:30,290
така че да пласирам.

455
00:24:30,290 --> 00:24:31,480
Така ли?

456
00:24:31,480 --> 00:24:34,300
>> АУДИТОРИЯ: Би ли било възможно
да се създаде пробвам и след това

457
00:24:34,300 --> 00:24:37,967
след като имате всички
данни в това, че вие ​​need--

458
00:24:37,967 --> 00:24:39,550
Аз не знам дали това би имало смисъл.

459
00:24:39,550 --> 00:24:42,200
Бях се отървем от всички
NULL герои, но след това

460
00:24:42,200 --> 00:24:42,910
вие не ще бъде в състояние да индексира them--

461
00:24:42,910 --> 00:24:43,275
>> SPEAKER 1: Вие все още се нуждаят от тях.

462
00:24:43,275 --> 00:24:44,854
>> АУДИТОРИЯ: - по същия начин всеки път.

463
00:24:44,854 --> 00:24:45,520
SPEAKER 1: Да.

464
00:24:45,520 --> 00:24:50,460
Вие се нуждаете от NULL герои, за да
Знаете ли, че ако там не е една дума там.

465
00:24:50,460 --> 00:24:52,040
Бен имахте ли нещо, което искате?

466
00:24:52,040 --> 00:24:52,540
OK.

467
00:24:52,540 --> 00:24:54,581
Добре, така че отиваме
да отида малко по-

468
00:24:54,581 --> 00:24:58,920
в техническа подробност зад
пробвам и работи чрез един пример.

469
00:24:58,920 --> 00:25:01,490
>> ОК, така че това е едно и също нещо.

470
00:25:01,490 --> 00:25:06,290
Като има предвид, свързан списък, основната ни
вид of-- каква е думата, която искате? -

471
00:25:06,290 --> 00:25:08,350
като изграждане на блок беше възел.

472
00:25:08,350 --> 00:25:12,280
В опит, ние също имаме един възел,
но това е определено по различен начин.

473
00:25:12,280 --> 00:25:17,000
>> Така че ние имаме някакъв булев че
представлява дали дума всъщност

474
00:25:17,000 --> 00:25:23,530
съществува на това място, и след това
ние имаме някои масив here-- или по-скоро,

475
00:25:23,530 --> 00:25:27,840
това е указател към
масив от 27 символа.

476
00:25:27,840 --> 00:25:33,339
И това е, в този случай, този
27-- Сигурен съм, че всички от вас са като, чакай,

477
00:25:33,339 --> 00:25:34,880
има 26 букви в азбуката.

478
00:25:34,880 --> 00:25:36,010
Защо имаме 27?

479
00:25:36,010 --> 00:25:37,870
>> Така че в зависимост от
начина, по който изпълнява тази,

480
00:25:37,870 --> 00:25:43,240
това е от pset че
разрешени за апострофи.

481
00:25:43,240 --> 00:25:46,010
Така че това е защо допълнително един.

482
00:25:46,010 --> 00:25:50,500
Вие също ще трябва по някакъв
случаи нулевата Терминатор

483
00:25:50,500 --> 00:25:53,230
е включен като един от
знаци, че това е право да бъде,

484
00:25:53,230 --> 00:25:56,120
и това е, как те проверете
да видим дали това е краят на думата.

485
00:25:56,120 --> 00:26:01,340
Ако сте заинтересувани, проверете
Видео Кевин за study.cs50,

486
00:26:01,340 --> 00:26:04,790
както и Wikipedia има
някои добри ресурси там.

487
00:26:04,790 --> 00:26:09,000
>> Но ние ще отидем през просто вид
на начина, по който може да работи чрез пробвам

488
00:26:09,000 --> 00:26:11,010
ако даден човек.

489
00:26:11,010 --> 00:26:16,230
Така че ние имаме супер проста тук
има думи "прилеп" и "увеличение" в тях.

490
00:26:16,230 --> 00:26:18,920
И както виждаме тук,
това малко пространство тук

491
00:26:18,920 --> 00:26:22,560
представлява нашата булев че
казва, да, това е думата.

492
00:26:22,560 --> 00:26:27,060
И тогава това е нашата
масиви от символи, нали?

493
00:26:27,060 --> 00:26:33,480
>> Така че ние ще да мине през
намиране на "прилепите" в този опит.

494
00:26:33,480 --> 00:26:38,340
Така че започнете от върха, нали?

495
00:26:38,340 --> 00:26:46,290
И ние знаем, че б съответства
Вторият показател, вторият елемент

496
00:26:46,290 --> 00:26:47,840
в този масив, защото и б.

497
00:26:47,840 --> 00:26:51,340
Така приблизително втория.

498
00:26:51,340 --> 00:26:58,820
>> И той казва, OK, хладно, следва, че в
следващата масива, защото, ако си спомним,

499
00:26:58,820 --> 00:27:02,160
това не е, че всеки от тях
всъщност съдържа елемент.

500
00:27:02,160 --> 00:27:07,110
Всеки един от тези масиви
съдържа указател, нали?

501
00:27:07,110 --> 00:27:10,030
Това е важно разграничение да се направи.

502
00:27:10,030 --> 00:27:13,450
>> Знам, че това ще се be-- опита са
Наистина е трудно да се кача на първия път,

503
00:27:13,450 --> 00:27:15,241
така че дори и ако това е
втори или трети път

504
00:27:15,241 --> 00:27:18,370
и тя все още е вид
на привидна трудно,

505
00:27:18,370 --> 00:27:21,199
Обещавам, ако отидете часовник
краткосрочен отново утре,

506
00:27:21,199 --> 00:27:22,740
то най-вероятно ще направи много по-дълбок смисъл.

507
00:27:22,740 --> 00:27:23,890
Това отнема много за храносмилане.

508
00:27:23,890 --> 00:27:27,800
Аз все още понякога съм
като, чакай, какво е опит?

509
00:27:27,800 --> 00:27:29,080
Как мога да използвам това?

510
00:27:29,080 --> 00:27:33,880
>> Така че ние сме Б, в този случай,
която е втората ни индекс.

511
00:27:33,880 --> 00:27:40,240
Ако имахме, да речем, в или
г или друг писмо,

512
00:27:40,240 --> 00:27:45,810
ние трябва да се набележат, че обратно към индекса
на нашия масив, че съответства.

513
00:27:45,810 --> 00:27:56,930
Така че ние ще вземе като rchar и ние просто
изваждане на разстояние, за да го преобразувате от 0 до 25.

514
00:27:56,930 --> 00:27:58,728
Всеки добър как
Карта нашите герои?

515
00:27:58,728 --> 00:28:00,440
OK.

516
00:28:00,440 --> 00:28:05,980
>> Така че отиваме на втората и ние
се види, че, да, това не е да NULL.

517
00:28:05,980 --> 00:28:07,780
Ние можем да преминем към следващия набор.

518
00:28:07,780 --> 00:28:12,300
Така че отиваме към следващия набор тук.

519
00:28:12,300 --> 00:28:15,500
>> И ние казваме, добре, сега ние
трябва да се види дали е тук.

520
00:28:15,500 --> 00:28:18,590
Дали A нула или го прави
всъщност се движи напред?

521
00:28:18,590 --> 00:28:21,880
Така че в действителност се движи
предаде в този масив.

522
00:28:21,880 --> 00:28:24,570
И ние казваме, OK, т е последното ни писмо.

523
00:28:24,570 --> 00:28:27,580
Така че отиваме в тона на индекса.

524
00:28:27,580 --> 00:28:30,120
И тогава ние се движат напред
защото има още един.

525
00:28:30,120 --> 00:28:38,340
И това казва основно, че, да,
се казва, че има една дума here--

526
00:28:38,340 --> 00:28:41,750
че ако следвате този
път сте пристигнали

527
00:28:41,750 --> 00:28:43,210
в една дума, която знам, е "прилеп".

528
00:28:43,210 --> 00:28:43,800
Да?

529
00:28:43,800 --> 00:28:46,770
>> АУДИТОРИЯ: Дали е стандарт за това
като индекс 0 и след това да има нещо в едно

530
00:28:46,770 --> 00:28:47,660
или да има в края?

531
00:28:47,660 --> 00:28:48,243
>> SPEAKER 1: No.

532
00:28:48,243 --> 00:28:55,360
Така че, ако погледнем назад в нашия
декларация тук, това е булев,

533
00:28:55,360 --> 00:28:59,490
така че това е неговата собствена елемент във вашата възел.

534
00:28:59,490 --> 00:29:03,331
Така че това не е част от масива.

535
00:29:03,331 --> 00:29:03,830
Cool.

536
00:29:03,830 --> 00:29:08,370
Така че, когато ние завършим нашата дума и ние сме
в този масив, което искаме да направим

537
00:29:08,370 --> 00:29:12,807
е да направи проверка за това нито дума.

538
00:29:12,807 --> 00:29:14,390
И в този случай, тя ще се върне да.

539
00:29:14,390 --> 00:29:17,220

540
00:29:17,220 --> 00:29:24,090
>> Така че по тази бележка, ние знаем, че "зоопарк" -
ние знаем, като хора, които "зоологическа градина" е дума,

541
00:29:24,090 --> 00:29:24,820
нали?

542
00:29:24,820 --> 00:29:28,990
Но се опитайте тук ще
се каже, не, това не е така.

543
00:29:28,990 --> 00:29:33,980
И бих казал, че тъй като ние
не го е определила като дума тук.

544
00:29:33,980 --> 00:29:40,440
Въпреки че можем да прекосяват
чрез на този масив,

545
00:29:40,440 --> 00:29:43,890
този опит ще кажа, че, не,
зоологическа градина не е във вашия речник

546
00:29:43,890 --> 00:29:47,070
защото ние не сме
го е определила като такава.

547
00:29:47,070 --> 00:29:52,870
>> Така че един от начините да направите that--
О, съжалявам, това.

548
00:29:52,870 --> 00:29:59,450
Така че в този случай, "зоопарк" не е
С една дума, но тя е в нашия опит.

549
00:29:59,450 --> 00:30:05,690
Но в това, да кажем че го искат
въведе думата "баня", какво се случва,

550
00:30:05,690 --> 00:30:08,260
е, че ние следваме through-- б, в, т.

551
00:30:08,260 --> 00:30:11,820
Ние сме в този масив, и
отидем да търсите за час.

552
00:30:11,820 --> 00:30:15,220
>> В този случай, когато ние
погледнем показалеца на час,

553
00:30:15,220 --> 00:30:17,890
това е, сочещи към NULL, OK?

554
00:30:17,890 --> 00:30:20,780
Така че, освен ако не е изрично
сочейки към друг масив,

555
00:30:20,780 --> 00:30:25,000
приемем, че всички указатели
в този масив са насочени към нула.

556
00:30:25,000 --> 00:30:28,270
Така че в този случай, ч е насочена
до нула, така че ние не можем да направим нищо,

557
00:30:28,270 --> 00:30:31,540
така че също ще се върне
невярно, "баня" не е тук.

558
00:30:31,540 --> 00:30:34,102

559
00:30:34,102 --> 00:30:35,810
Така че сега ние сме всъщност
ще мине през

560
00:30:35,810 --> 00:30:39,790
как ще можем действително да кажа
че "зоологическа градина" се намира в нашия опит.

561
00:30:39,790 --> 00:30:42,920
Как да вмъкнете "зоопарк" в нашия опит?

562
00:30:42,920 --> 00:30:47,810
Така че в един и същи начин, че ние започнахме с
нашата свързан списък, започваме в корена.

563
00:30:47,810 --> 00:30:50,600
Когато се колебаете, започнете
на основата на тези неща.

564
00:30:50,600 --> 00:30:53,330
>> И ние ще кажем, OK, Z.

565
00:30:53,330 --> 00:30:55,650
Z съществува в това, и го прави.

566
00:30:55,650 --> 00:30:58,370
Значи да преминат към
следващата си масив, OK?

567
00:30:58,370 --> 00:31:01,482
И след това на следващия,
ние казваме, OK, се о съществува?

568
00:31:01,482 --> 00:31:03,000
Това е така.

569
00:31:03,000 --> 00:31:04,330
Това отново.

570
00:31:04,330 --> 00:31:08,670
>> И така, на следващата ни един, казахме,
OK, "зоопарк" вече съществува тук.

571
00:31:08,670 --> 00:31:12,440
Всичко, което трябва да направите е да зададете този равен
да е вярно, че има една дума там.

572
00:31:12,440 --> 00:31:15,260
Ако беше последвано всичко
до преди този момент,

573
00:31:15,260 --> 00:31:17,030
това е една дума, така че просто
задайте равна на себе си.

574
00:31:17,030 --> 00:31:17,530
Да?

575
00:31:17,530 --> 00:31:22,550
>> АУДИТОРИЯ: Така че след това прави това
означава, че "ба" е дума, също?

576
00:31:22,550 --> 00:31:24,120
>> SPEAKER 1: No.

577
00:31:24,120 --> 00:31:28,870
Така че в този случай, "ба", ние ще се
тук, ние ще кажем, че е една дума,

578
00:31:28,870 --> 00:31:31,590
и тя все още ще бъде не.

579
00:31:31,590 --> 00:31:32,822
OK?

580
00:31:32,822 --> 00:31:33,740
Mmhmm?

581
00:31:33,740 --> 00:31:36,360
>> АУДИТОРИЯ: Така че, след като е го
дума и ще ви кажа, да, то тогава

582
00:31:36,360 --> 00:31:38,380
ще съдържа за да отидете на m?

583
00:31:38,380 --> 00:31:42,260
>> SPEAKER 1: Така че това трябва да се направи
with-- сте зареждането на тази вътре.

584
00:31:42,260 --> 00:31:43,640
Вие казвате "зоологическа градина" е дума.

585
00:31:43,640 --> 00:31:47,020
Когато отидете да check--
като, да речем, искате да кажете,

586
00:31:47,020 --> 00:31:49,400
означава "зоопарк" съществува в този речник?

587
00:31:49,400 --> 00:31:54,200
Вие само ще търсене за "зоопарк"
и след това да проверите дали това е думата.

588
00:31:54,200 --> 00:31:57,291
Вие никога няма да се движат
чрез да m, защото това не е

589
00:31:57,291 --> 00:31:58,290
това, което търсите.

590
00:31:58,290 --> 00:32:02,690

591
00:32:02,690 --> 00:32:08,070
>> Така че, ако ние наистина искахме да
добави "баня" в този опит,

592
00:32:08,070 --> 00:32:11,390
ние ще направим същото
както направихме с "зоопарк"

593
00:32:11,390 --> 00:32:15,380
освен ние ще видим, че когато ние
се опита да стигне до час, то не съществува.

594
00:32:15,380 --> 00:32:20,090
Така че може да се мисли за това като се опитва
за да добавите нов възел в свързан списък,

595
00:32:20,090 --> 00:32:27,210
така че ние ще трябва да се добавят още
един от тези масиви, като така.

596
00:32:27,210 --> 00:32:35,670
И след това, което правим е, че ние просто настройте ч
елемент на този масив, сочещи към това.

597
00:32:35,670 --> 00:32:39,430
>> И тогава какво ще искаме да направим тук?

598
00:32:39,430 --> 00:32:43,110
Добавете го равно на истински
защото това е една дума.

599
00:32:43,110 --> 00:32:46,350

600
00:32:46,350 --> 00:32:48,150
Cool.

601
00:32:48,150 --> 00:32:48,700
Знам.

602
00:32:48,700 --> 00:32:51,170
Опитва не са най-вълнуващите.

603
00:32:51,170 --> 00:32:54,250
Повярвай ми, знам.

604
00:32:54,250 --> 00:32:58,040
>> Така че едно е да се реализира с опит
Аз казах, те са много ефективни.

605
00:32:58,040 --> 00:33:00,080
Така че ние сме те виждали
да отнеме до един тон на пространството.

606
00:33:00,080 --> 00:33:01,370
Те са вид объркващо.

607
00:33:01,370 --> 00:33:03,367
Така че, защо би някога сме ги използвате?

608
00:33:03,367 --> 00:33:05,450
Ние използваме тези, защото те са
невероятно ефективен.

609
00:33:05,450 --> 00:33:08,130
>> Така че, ако някога търсите
с една дума, вие сте единствената

610
00:33:08,130 --> 00:33:10,450
ограничена от дължината на думата.

611
00:33:10,450 --> 00:33:15,210
Така че, ако търсите за
дума, която е с дължина пет,

612
00:33:15,210 --> 00:33:20,940
сте само някога ще трябва да се
направи най-много пет сравнения, OK?

613
00:33:20,940 --> 00:33:25,780
Така че това го прави по същество постоянна.

614
00:33:25,780 --> 00:33:29,150
Подобно на вмъкване и справка
са основно константно време.

615
00:33:29,150 --> 00:33:33,750
>> Така че, ако можете да си получите
нещо константно време,

616
00:33:33,750 --> 00:33:35,150
това е толкова добър, колкото го получава.

617
00:33:35,150 --> 00:33:37,990
Вие не можете да получите по-добре, отколкото
константно време за тези неща.

618
00:33:37,990 --> 00:33:43,150
Така че това е един от най
огромните плюсове на опита.

619
00:33:43,150 --> 00:33:46,780
>> Но това е много място.

620
00:33:46,780 --> 00:33:50,380
Така че някак си трябва да реши
това, което е по-важно за вас.

621
00:33:50,380 --> 00:33:54,700
И на днешните компютри, на
пространство, което пробвам може да отнеме

622
00:33:54,700 --> 00:33:57,740
може би не засяга
ви, че е много, но може би

623
00:33:57,740 --> 00:34:01,350
имаш работа с нещо
че има много, много повече неща,

624
00:34:01,350 --> 00:34:02,810
и опит просто не е разумно.

625
00:34:02,810 --> 00:34:03,000
Да?

626
00:34:03,000 --> 00:34:05,610
>> АУДИТОРИЯ: Чакай, така че трябва 26
писма във всеки един от тях?

627
00:34:05,610 --> 00:34:07,440
>> SPEAKER 1: Mmhmm.

628
00:34:07,440 --> 00:34:08,570
Да, имате 26.

629
00:34:08,570 --> 00:34:16,984
Имате някои е дума маркер и след това
имате 26 указатели във всеки един.

630
00:34:16,984 --> 00:34:17,775
И те point--

631
00:34:17,775 --> 00:34:20,280
>> АУДИТОРИЯ: И всеки 26
те всеки има 26?

632
00:34:20,280 --> 00:34:21,500
>> SPEAKER 1: Да.

633
00:34:21,500 --> 00:34:27,460
И ето защо, колкото можете
виж, тя се разширява много бързо.

634
00:34:27,460 --> 00:34:28,130
Добре.

635
00:34:28,130 --> 00:34:32,524
Така че отиваме да влязат в дървета, които
Аз се чувствам като е по-лесно и вероятно ще

636
00:34:32,524 --> 00:34:36,150
е една хубава малка отсрочка
от опита там.

637
00:34:36,150 --> 00:34:39,620
Така че, надявам се повечето от вас
съм виждал дърво преди.

638
00:34:39,620 --> 00:34:41,820
Не харесвам доста
хора отвън, които съм

639
00:34:41,820 --> 00:34:44,340
не знам дали някой
отиде на открито наскоро.

640
00:34:44,340 --> 00:34:49,230
Отидох ябълка бране този уикенд,
и о, Боже мой, че е красива.

641
00:34:49,230 --> 00:34:52,250
Не знаех листа
може да изглежда, че доста.

642
00:34:52,250 --> 00:34:53,610
>> Така че това е само едно дърво, нали?

643
00:34:53,610 --> 00:34:56,790
Това е просто някакъв възел, и
сочи към куп други възли.

644
00:34:56,790 --> 00:34:59,570
Както виждате тук, това е
вид на повтаряща се тема.

645
00:34:59,570 --> 00:35:03,720
Възли, насочен към възли е вид
същността на много структури от данни.

646
00:35:03,720 --> 00:35:06,670
Просто зависи от това как ние
да ги насочи към всяка друга

647
00:35:06,670 --> 00:35:08,600
и начина, по който преминават
чрез тях и как можем

648
00:35:08,600 --> 00:35:14,500
въведете неща, които определя
техните различни характеристики.

649
00:35:14,500 --> 00:35:17,600
>> Така че просто някои терминология,
които аз съм използвал преди.

650
00:35:17,600 --> 00:35:20,010
Така корен е всичко, което е на самия връх.

651
00:35:20,010 --> 00:35:21,200
това е мястото, където ние винаги се започне.

652
00:35:21,200 --> 00:35:23,610
Можете да мислите за него като за главата също.

653
00:35:23,610 --> 00:35:28,750
Но за дървета, ние сме склонни да
се отнасят към него като корен.

654
00:35:28,750 --> 00:35:32,820
>> Всичко в долния here--
в много, много bottom--

655
00:35:32,820 --> 00:35:34,500
са считани листа.

656
00:35:34,500 --> 00:35:37,210
Така че върви заедно с
цялата работа дърво, нали?

657
00:35:37,210 --> 00:35:39,860
Листата са по краищата на вашето дърво.

658
00:35:39,860 --> 00:35:45,820
>> И тогава ние също имаме няколко
термини, за да говорят за възли във връзка

659
00:35:45,820 --> 00:35:46,680
един към друг.

660
00:35:46,680 --> 00:35:49,700
Така че ние имаме майка,
деца, братя и сестри.

661
00:35:49,700 --> 00:35:56,260
Така че в този случай 3 е
майка на 5, 6 и 7.

662
00:35:56,260 --> 00:36:00,370
Така родителят е такова, каквото е
една стъпка по-горе каквото и да сте

663
00:36:00,370 --> 00:36:02,940
отнасящи се до тях, така че просто
като родословно дърво.

664
00:36:02,940 --> 00:36:07,090
Надяваме се, че всичко това е малко по-
малко по-интуитивен от опитите.

665
00:36:07,090 --> 00:36:10,970
>> Братя и сестри са всички, които имат
същата майка, нали?

666
00:36:10,970 --> 00:36:13,470
Те са на същото ниво тук.

667
00:36:13,470 --> 00:36:16,960
И тогава, както бях
казвайки, децата са просто

668
00:36:16,960 --> 00:36:22,630
каквото и да е с една стъпка по-долу
възел в въпрос, нали?

669
00:36:22,630 --> 00:36:23,470
Cool.

670
00:36:23,470 --> 00:36:25,610
Така двоично дърво.

671
00:36:25,610 --> 00:36:31,450
Може ли някой да отгатна на един от
характеристиките на двоичен дърво?

672
00:36:31,450 --> 00:36:32,770
>> АУДИТОРИЯ: Max два листа.

673
00:36:32,770 --> 00:36:33,478
>> SPEAKER 1: Точно така.

674
00:36:33,478 --> 00:36:34,640
Така максимум от два листа.

675
00:36:34,640 --> 00:36:39,730
Така че в това и преди, ние имахме този
че имаше три, но в двоичен дърво,

676
00:36:39,730 --> 00:36:45,000
имате максимум от две
деца на една майка, нали?

677
00:36:45,000 --> 00:36:46,970
Има още
интересна характеристика.

678
00:36:46,970 --> 00:36:51,550
Някой знае ли, че?

679
00:36:51,550 --> 00:36:52,620
Binary дърво.

680
00:36:52,620 --> 00:37:00,350
>> Така двоично дърво ще има всичко
на the-- това не е sorted--

681
00:37:00,350 --> 00:37:05,320
но в сортирано двоично дърво,
всичко на правото

682
00:37:05,320 --> 00:37:08,530
е по-голяма от родител,
и всичко в ляво

683
00:37:08,530 --> 00:37:10,035
е по-малко, отколкото на родителя.

684
00:37:10,035 --> 00:37:15,690
И това е тест
въпрос преди, така че е добре да знаете.

685
00:37:15,690 --> 00:37:19,500
Така че начина, по който ние определяме това,
отново, ние имаме друг възел.

686
00:37:19,500 --> 00:37:21,880
Това изглежда много подобно на това?

687
00:37:21,880 --> 00:37:28,336

688
00:37:28,336 --> 00:37:28,836
Двойно

689
00:37:28,836 --> 00:37:29,320
>> АУДИТОРИЯ: свързани списъци

690
00:37:29,320 --> 00:37:31,100
>> SPEAKER 1: двойно свързан списък, нали?

691
00:37:31,100 --> 00:37:33,690
Така че, ако ние вместо това
с предходната и следващата,

692
00:37:33,690 --> 00:37:35,670
това ще бъде двойно свързан списък.

693
00:37:35,670 --> 00:37:40,125
Но в този случай, ние всъщност
има ляво и дясно и това е всичко.

694
00:37:40,125 --> 00:37:41,500
В противен случай, това е точно същото.

695
00:37:41,500 --> 00:37:43,374
Ние все още имаме елемент
което търсите,

696
00:37:43,374 --> 00:37:45,988
и просто да има две насоки
Ще каквото е следващата.

697
00:37:45,988 --> 00:37:49,210

698
00:37:49,210 --> 00:37:51,870
Да, така двоично търсене дърво.

699
00:37:51,870 --> 00:37:57,665
Ако забележите, всичко на
точно тук е по-голяма than--

700
00:37:57,665 --> 00:37:59,850
или всичко веднага
надясно тук

701
00:37:59,850 --> 00:38:02,840
е по-голяма от всичко
тук е по-малко от.

702
00:38:02,840 --> 00:38:06,980

703
00:38:06,980 --> 00:38:14,000
>> Така че, ако трябва да се търси чрез това
трябва да изглежда много близо до двоично търсене

704
00:38:14,000 --> 00:38:14,910
тук, нали?

705
00:38:14,910 --> 00:38:17,640
Освен, вместо да гледаш
на половината от масив,

706
00:38:17,640 --> 00:38:21,720
ние сме просто гледам или отляво
страна или от дясната страна на дървото.

707
00:38:21,720 --> 00:38:24,850
Така става малко по-просто, мисля.

708
00:38:24,850 --> 00:38:29,300
>> Така че, ако си корен е NULL,
Очевидно това е просто невярно.

709
00:38:29,300 --> 00:38:33,470
И ако той е там, очевидно това е вярно.

710
00:38:33,470 --> 00:38:35,320
Ако тя е по-малко, отколкото, да търсим наляво.

711
00:38:35,320 --> 00:38:37,070
Ако тя е по-голяма от
ние търсим правото.

712
00:38:37,070 --> 00:38:39,890
Това е точно като двоично търсене,
просто различна структура на данни

713
00:38:39,890 --> 00:38:40,600
които ние използваме.

714
00:38:40,600 --> 00:38:42,790
Вместо масив,
това е просто двоично дърво.

715
00:38:42,790 --> 00:38:45,820

716
00:38:45,820 --> 00:38:48,090
>> OK, стекове.

717
00:38:48,090 --> 00:38:51,550
И също така, тя изглежда като ние
може да има по-малко време.

718
00:38:51,550 --> 00:38:54,460
Ако го направим, аз съм щастлив да отида
над нищо от това отново.

719
00:38:54,460 --> 00:38:56,856
ОК, така че купища.

720
00:38:56,856 --> 00:39:02,695
Дали някой си спомня какво stacks--
всички характеристики на комин?

721
00:39:02,695 --> 00:39:05,550

722
00:39:05,550 --> 00:39:10,400
>> ОК, така че повечето от нас, мисля,
яде в трапезарията halls--

723
00:39:10,400 --> 00:39:13,100
толкова, колкото ние не може да искате да.

724
00:39:13,100 --> 00:39:16,900
Но очевидно, можеш да се сетиш на комин
буквално като купчина тави

725
00:39:16,900 --> 00:39:18,460
или купчина от неща.

726
00:39:18,460 --> 00:39:21,820
И това, което е важно
да осъзнаят е, че тя е

727
00:39:21,820 --> 00:39:26,850
something-- характеристиката
че ние го наричаме по-- е LIFO.

728
00:39:26,850 --> 00:39:28,450
Някой знае ли какво означава?

729
00:39:28,450 --> 00:39:29,070
Mmhmm?

730
00:39:29,070 --> 00:39:30,650
>> АУДИТОРИЯ: Последно, първа изходяща.

731
00:39:30,650 --> 00:39:32,250
>> SPEAKER 1: Точно така, да продължи, първа изходяща.

732
00:39:32,250 --> 00:39:36,585
Така че, ако ние знаем, ако сме подреждане на нещата
нагоре, най-лесното нещо да вземете off--

733
00:39:36,585 --> 00:39:39,570
и може би единственото нещо, което може да вземете
изключва, ако ни стак е голям enough--

734
00:39:39,570 --> 00:39:40,850
е, че горния елемент.

735
00:39:40,850 --> 00:39:43,460
Така че каквото и да се постави на
last-- както виждаме тук,

736
00:39:43,460 --> 00:39:46,370
каквото и да е бил бутнат
на най-recently-- е

737
00:39:46,370 --> 00:39:51,160
ще бъде първият
нещо, което ние гърмя, OK?

738
00:39:51,160 --> 00:39:56,324
>> Така че това, което имаме тук, е
друг typedef структура.

739
00:39:56,324 --> 00:39:58,740
Това е наистина просто искал
интензивен курс по структура на данните,

740
00:39:58,740 --> 00:40:01,650
така че има много хвърлени по вас, момчета.

741
00:40:01,650 --> 00:40:02,540
Знам.

742
00:40:02,540 --> 00:40:04,970
Така че още една структура.

743
00:40:04,970 --> 00:40:06,740
Уау за структури.

744
00:40:06,740 --> 00:40:16,660
>> И в този случай, това е някаква показалка
на масив, който има някои капацитет.

745
00:40:16,660 --> 00:40:20,830
Така че това представлява нашата стак
тук, като реалното ни масив

746
00:40:20,830 --> 00:40:22,520
че държи на нашите елементи.

747
00:40:22,520 --> 00:40:24,850
И след това тук имаме някакъв размер.

748
00:40:24,850 --> 00:40:31,170
>> И обикновено, което искате да запазите
следите колко е голям вашият стак е

749
00:40:31,170 --> 00:40:36,180
защото това, което се случва, за да се даде възможност
можете да направите, е, ако знаете размера,

750
00:40:36,180 --> 00:40:39,170
тя ви позволява да се каже,
ОК, аз съм най-капацитет?

751
00:40:39,170 --> 00:40:40,570
Мога ли да добавите още нещо?

752
00:40:40,570 --> 00:40:44,650
И също така ви казва
където горната част на вашия стак

753
00:40:44,650 --> 00:40:48,180
е да знаете какво ви
всъщност може да се свали.

754
00:40:48,180 --> 00:40:51,760
И това всъщност ще
да е малко по-ясно тук.

755
00:40:51,760 --> 00:40:57,350
>> Така че, за да бута, едно нещо, ако сте
някога да приложи натиск,

756
00:40:57,350 --> 00:41:01,330
аз просто казвам, си
стак има ограничен размер, нали?

757
00:41:01,330 --> 00:41:03,990
Нашата гама имали някакъв капацитет.

758
00:41:03,990 --> 00:41:04,910
Това е масив.

759
00:41:04,910 --> 00:41:08,930
Това е с фиксиран размер, така че ние трябва да се
уверете се, че ние не сме пускането повече

760
00:41:08,930 --> 00:41:11,950
в нашия набор от нас
всъщност има място за.

761
00:41:11,950 --> 00:41:16,900
>> Така че, когато създавате тласък
функция, първото нещо, което правя е да речем, OK,

762
00:41:16,900 --> 00:41:18,570
имам място в моя стак?

763
00:41:18,570 --> 00:41:23,330
Защото, ако не го направя, съжалявам,
Аз не може да се съхранява вашата стихия.

764
00:41:23,330 --> 00:41:28,980
Ако го направя, а след това искате да съхраните
то в горната част на комина, нали?

765
00:41:28,980 --> 00:41:31,325
>> И това е защо ние имаме
да следите нашия размер.

766
00:41:31,325 --> 00:41:35,290
Ако не следите на нашия размер,
ние не знаем къде да го сложи.

767
00:41:35,290 --> 00:41:39,035
Ние не знаем колко много неща
са в нашата вече масив.

768
00:41:39,035 --> 00:41:41,410
Както очевидно има начини
че може би ще го направя.

769
00:41:41,410 --> 00:41:44,610
Може да се инициализира всичко NULL
и след това се проверява за най-новата NULL,

770
00:41:44,610 --> 00:41:47,950
но много по-лесно нещо е просто
да се каже, добре, следите от техния размер.

771
00:41:47,950 --> 00:41:51,840
Като знам, че има четири елемента
в моя набор, така че следващото нещо,

772
00:41:51,840 --> 00:41:55,930
че ние поставяме, ние сме
ще се съхранява в индекса 4.

773
00:41:55,930 --> 00:42:00,940
И след това, разбира се, това означава, че
успешно сте бутна нещо

774
00:42:00,940 --> 00:42:03,320
на вашия стак, вие
искате да увеличите размера

775
00:42:03,320 --> 00:42:08,880
така че да знаете къде се намирате, така че
че можете да натиснете повече неща.

776
00:42:08,880 --> 00:42:12,730
>> Така че, ако ние се опитваме да се появи
нещо извън стека,

777
00:42:12,730 --> 00:42:16,072
какво може да е първото нещо,
че искаме да се провери за?

778
00:42:16,072 --> 00:42:18,030
Вие се опитвате да се вземат
нещо от вашия стак.

779
00:42:18,030 --> 00:42:21,710

780
00:42:21,710 --> 00:42:24,781
Сигурни ли сте, че има
нещо във вашия стак?

781
00:42:24,781 --> 00:42:25,280
Не.

782
00:42:25,280 --> 00:42:26,894
И така, какво може да искаме да се провери?

783
00:42:26,894 --> 00:42:27,810
>> АУДИТОРИЯ: [недоловим].

784
00:42:27,810 --> 00:42:29,880
SPEAKER 1: Проверка за размера?

785
00:42:29,880 --> 00:42:31,840
Size.

786
00:42:31,840 --> 00:42:38,520
Така че ние искаме да се провери, за да се види дали
ни размер е по-голям от 0, OK?

787
00:42:38,520 --> 00:42:44,970
И ако е така, тогава ние искаме да се намали
ни размер от 0 и го върнете това.

788
00:42:44,970 --> 00:42:45,840
Защо?

789
00:42:45,840 --> 00:42:49,950
>> В първата бяхме
бутане, ние го избута

790
00:42:49,950 --> 00:42:52,460
върху размера и след това актуализиран размер.

791
00:42:52,460 --> 00:42:57,850
В този случай, ние сме намаляващи размери
и след това го свали, тя скубане

792
00:42:57,850 --> 00:42:58,952
от нашия масив.

793
00:42:58,952 --> 00:42:59,826
Защо бихме могли да направим това?

794
00:42:59,826 --> 00:43:04,800

795
00:43:04,800 --> 00:43:11,811
Така че, ако имам едно нещо на моя стак,
какъв ще бъде размера си в този момент?

796
00:43:11,811 --> 00:43:13,140
1.

797
00:43:13,140 --> 00:43:15,180
>> И къде е елемент 1 се съхранява?

798
00:43:15,180 --> 00:43:17,621
На какъв индекс?

799
00:43:17,621 --> 00:43:18,120
АУДИТОРИЯ: 0.

800
00:43:18,120 --> 00:43:19,060
SPEAKER 1: 0.

801
00:43:19,060 --> 00:43:22,800
Така че в този случай, ние
винаги трябва да се направи sure--

802
00:43:22,800 --> 00:43:27,630
вместо да се завърне
размер на минус 1, тъй като ние

803
00:43:27,630 --> 00:43:31,730
знаем, че нашата елемент е
ще се съхранява при по-малко 1

804
00:43:31,730 --> 00:43:34,705
каквото е нашето, това
просто се грижи за него.

805
00:43:34,705 --> 00:43:36,080
Това е малко по-елегантен начин.

806
00:43:36,080 --> 00:43:41,220
И ние просто намалите стъпково ни
размер и след това се върнете размер.

807
00:43:41,220 --> 00:43:42,330
Mmhmm?

808
00:43:42,330 --> 00:43:45,300
>> АУДИТОРИЯ: Предполагам, че просто като цяло,
защо би тази структура на данните

809
00:43:45,300 --> 00:43:47,800
да бъде от полза?

810
00:43:47,800 --> 00:43:50,660
>> SPEAKER 1: Това зависи от вашата връзка.

811
00:43:50,660 --> 00:43:57,420
Така че за някои от теорията,
ако работите with-- OK,

812
00:43:57,420 --> 00:44:02,750
нека да видим дали има благоприятен един
че е от полза за повече, отколкото навън

813
00:44:02,750 --> 00:44:05,420
на CS.

814
00:44:05,420 --> 00:44:15,780
С купчини, по всяко време имате нужда
да следите на нещо, което

815
00:44:15,780 --> 00:44:20,456
е най-наскоро добавя е, когато
вие ще искате да използвате стак.

816
00:44:20,456 --> 00:44:24,770
>> И не мога да се сетя за по добро
пример за това точно сега.

817
00:44:24,770 --> 00:44:29,955
Но когато най-новите
нещо, което е най-важно за вас,

818
00:44:29,955 --> 00:44:31,705
това е, когато купчина
ще бъде полезно.

819
00:44:31,705 --> 00:44:35,797

820
00:44:35,797 --> 00:44:39,330
Опитвам се да мисля, че ако
там е добра за това.

821
00:44:39,330 --> 00:44:43,720
Ако мисля за добър пример в следващия
20 минути, аз определено ще ви кажа.

822
00:44:43,720 --> 00:44:49,455
>> Но като цяло, ако има нещо,
както казах, най-много, когато най-новите

823
00:44:49,455 --> 00:44:52,470
Най-важното е, че е
където стак влезе в игра.

824
00:44:52,470 --> 00:44:58,860
Като има предвид, опашки са вид обратното.

825
00:44:58,860 --> 00:44:59,870
И всички малки кучета.

826
00:44:59,870 --> 00:45:00,890
Това не е ли страхотно, нали?

827
00:45:00,890 --> 00:45:03,299
Имам чувството, че трябва да
Просто трябва зайче видео

828
00:45:03,299 --> 00:45:05,090
точно в средата на
раздел за вас, момчета

829
00:45:05,090 --> 00:45:08,870
защото това е силен раздел.

830
00:45:08,870 --> 00:45:10,480
>> Така опашка.

831
00:45:10,480 --> 00:45:12,710
Основно опашка е като линия.

832
00:45:12,710 --> 00:45:15,780
Вие, момчета, аз съм сигурен, че тази употреба всеки ден,
точно като в нашите зали за хранене.

833
00:45:15,780 --> 00:45:18,160
Така че ние трябва да отидем в
и да получите нашите тави, аз съм

834
00:45:18,160 --> 00:45:21,260
Наистина ли трябва да чакат на опашка
да плъзнете или да получите вашата храна.

835
00:45:21,260 --> 00:45:24,650
>> Така че разликата тук
е, че това е FIFO.

836
00:45:24,650 --> 00:45:30,090
Така че, ако LIFO е на последно място в първо
се, FIFO е първата, първа изходяща.

837
00:45:30,090 --> 00:45:33,400
Така че това е мястото, където каквото и да постави
на първата е най-важната.

838
00:45:33,400 --> 00:45:35,540
Така че, ако сте били чака
в line-- може да ви

839
00:45:35,540 --> 00:45:39,130
представете си, че сте отишли ​​да
иди новия iPhone

840
00:45:39,130 --> 00:45:42,800
и имаше купчина където
Последният човек в съответствие го на първо място,

841
00:45:42,800 --> 00:45:44,160
хората ще се избиват един друг.

842
00:45:44,160 --> 00:45:49,800
>> Така че, FIFO, всички ние сме много добре запознати
с в реалния свят тук,

843
00:45:49,800 --> 00:45:54,930
и всичко това е свързано с действително
вид пресъздаване цялата тази линия

844
00:45:54,930 --> 00:45:56,900
и опашка структура.

845
00:45:56,900 --> 00:46:02,390
Така че, докато при стека,
имаме тласък и поп.

846
00:46:02,390 --> 00:46:06,440
С опашка, имаме
Enqueue и dequeue.

847
00:46:06,440 --> 00:46:10,910
Така Enqueue същество означава,
го постави върху гърба,

848
00:46:10,910 --> 00:46:13,680
и dequeue средства да се
разстояние от предната.

849
00:46:13,680 --> 00:46:18,680
Така че нашата структура от данни е
малко по-сложно.

850
00:46:18,680 --> 00:46:21,060
Имаме второ нещо, за да следите.

851
00:46:21,060 --> 00:46:25,950
>> Така че без главата, това
е точно комин, нали?

852
00:46:25,950 --> 00:46:27,900
Това е същата структура като комин.

853
00:46:27,900 --> 00:46:32,480
Единственото нещо различно сега е, че ние
има тази глава, която ти какво мислиш

854
00:46:32,480 --> 00:46:34,272
ще следите?

855
00:46:34,272 --> 00:46:35,510
>> АУДИТОРИЯ: Първият.

856
00:46:35,510 --> 00:46:38,685
>> SPEAKER 1: вдясно,
Първото нещо, което ще се постави вътре.

857
00:46:38,685 --> 00:46:41,130
Ръководителят на нашата опашка.

858
00:46:41,130 --> 00:46:42,240
Който е първи по ред.

859
00:46:42,240 --> 00:46:45,300

860
00:46:45,300 --> 00:46:49,420
Добре, така че ако правим Enqueue.

861
00:46:49,420 --> 00:46:52,720

862
00:46:52,720 --> 00:46:55,920
Отново, с някоя от
тези структури от данни,

863
00:46:55,920 --> 00:46:59,760
тъй като си имаме работа с масив,
ние трябва да се провери, ако имаме пространство.

864
00:46:59,760 --> 00:47:03,290
>> Това е нещо като да ми кажеш
вие, момчета, ако отворите даден файл,

865
00:47:03,290 --> 00:47:04,760
трябва да се провери за нищожна.

866
00:47:04,760 --> 00:47:08,330
С всяка от тези купчини
и опашки, от които се нуждаете

867
00:47:08,330 --> 00:47:13,420
за да види дали има място, защото ние сме
справяне с фиксиран размер масив,

868
00:47:13,420 --> 00:47:16,030
както виждаме here-- 0, 1, всички до 5.

869
00:47:16,030 --> 00:47:20,690
Така че това, което правим в този случай е проверка
за да видите дали все още има пространство.

870
00:47:20,690 --> 00:47:23,110
Дали нашата размер по-малко от капацитета?

871
00:47:23,110 --> 00:47:28,480
>> Ако е така, ние трябва да го съхранявате в
опашката и ние актуализираме размер.

872
00:47:28,480 --> 00:47:30,250
Така че това, което може да бъде на опашката в този случай?

873
00:47:30,250 --> 00:47:32,360
Това не е изрично изписано.

874
00:47:32,360 --> 00:47:33,380
Как бихме могли да го съхранявате?

875
00:47:33,380 --> 00:47:34,928
Какво ще бъде на опашката?

876
00:47:34,928 --> 00:47:38,600

877
00:47:38,600 --> 00:47:40,190
>> Така че нека да преминете през този пример.

878
00:47:40,190 --> 00:47:44,590
Така че това е масив с размер 6, нали?

879
00:47:44,590 --> 00:47:49,220
И ние имаме в момента, нашият размер е 5.

880
00:47:49,220 --> 00:47:55,240
И когато го поставите в, то се случва
да отидат в петия индекса, нали?

881
00:47:55,240 --> 00:47:57,030
Така се съхранява в опашка.

882
00:47:57,030 --> 00:48:05,600
>> Друг начин да се напише опашка би просто
да бъде наш масив на индекс на размер, нали?

883
00:48:05,600 --> 00:48:07,560
Това е размер 5.

884
00:48:07,560 --> 00:48:11,490
Следващото нещо е да отида в 5.

885
00:48:11,490 --> 00:48:12,296
Cool?

886
00:48:12,296 --> 00:48:13,290
OK.

887
00:48:13,290 --> 00:48:16,350
Той получава малко по-сложно,
когато започнем каша с главата.

888
00:48:16,350 --> 00:48:17,060
Да?

889
00:48:17,060 --> 00:48:20,090
>> АУДИТОРИЯ: Означава ли това, че ние
ще са декларирали масив, който

890
00:48:20,090 --> 00:48:23,880
беше дълга пет елемента и
След това ние добавяме към него?

891
00:48:23,880 --> 00:48:24,730
>> SPEAKER 1: No.

892
00:48:24,730 --> 00:48:27,560
Така че в този случай, това е купчина.

893
00:48:27,560 --> 00:48:31,760
Това ще бъде обявено
като масив с размер 6.

894
00:48:31,760 --> 00:48:37,120
И в този случай, ние
Просто трябва един пространство вляво.

895
00:48:37,120 --> 00:48:42,720
>> ОК, така че едно нещо, което е в тази
случай, ако главата ни е на 0,

896
00:48:42,720 --> 00:48:45,270
тогава ние просто да го добавите в размер.

897
00:48:45,270 --> 00:48:51,020
Но това става малко по-сложни
тъй като всъщност те

898
00:48:51,020 --> 00:48:52,840
не разполагат с пързалка
за това, така че аз ще

899
00:48:52,840 --> 00:48:56,670
да се направи, защото това не е
толкова просто, след като

900
00:48:56,670 --> 00:48:59,230
започне да се отървете от неща.

901
00:48:59,230 --> 00:49:03,920
Така че със стак
имате само някога

902
00:49:03,920 --> 00:49:08,920
да се притеснявате за това, което е с размерите
когато добавяте нещо,

903
00:49:08,920 --> 00:49:15,710
с опашка вие също трябва да се направи
сигурен, че главата ви се отчита,

904
00:49:15,710 --> 00:49:20,760
защото готино нещо за опашки
е, че ако не сте на капацитет,

905
00:49:20,760 --> 00:49:23,040
всъщност можете да го обгърне.

906
00:49:23,040 --> 00:49:28,810
>> ОК, така че един thing-- о,
това е ужасно тебешир.

907
00:49:28,810 --> 00:49:31,815
Едно нещо е да се помисли по случая.

908
00:49:31,815 --> 00:49:35,514

909
00:49:35,514 --> 00:49:37,140
Ние просто ще направя пет.

910
00:49:37,140 --> 00:49:41,810
ОК, така че ние ще
казват, че главата е тук.

911
00:49:41,810 --> 00:49:46,140
Това е 0, 1, 2, 3, 4.

912
00:49:46,140 --> 00:49:54,210
>> Главата е там, и
моля неща в тях.

913
00:49:54,210 --> 00:49:58,340
И ние искаме да се добави нещо, нали?

914
00:49:58,340 --> 00:50:01,170
Така че това, което ние трябва да се
знам е, че главата е винаги

915
00:50:01,170 --> 00:50:05,620
ще се движат по този начин и
след това по принципа на обратната наоколо, OK?

916
00:50:05,620 --> 00:50:10,190
>> Така че тази опашка има място, нали?

917
00:50:10,190 --> 00:50:13,950
Той има място в самото начало,
вид обратното на това.

918
00:50:13,950 --> 00:50:17,920
Така че това, което трябва да направите, е, че ние
трябва да се изчисли на опашката.

919
00:50:17,920 --> 00:50:20,530
Ако знаете, че вашият
глава не се е променила, опашката

920
00:50:20,530 --> 00:50:24,630
е просто вашия масив в
индексът на размера.

921
00:50:24,630 --> 00:50:30,000
>> Но в действителност, ако сте с помощта на опашката,
главата ти е вероятно да бъде актуализиран.

922
00:50:30,000 --> 00:50:33,890
Така че това, което трябва да направите, е
всъщност изчисли опашката.

923
00:50:33,890 --> 00:50:39,990
Така че това, което правим, е тази формула
тук, което аз отивам да ви разочарова

924
00:50:39,990 --> 00:50:42,680
момчета мислят за и
След това ние ще говорим за това.

925
00:50:42,680 --> 00:50:49,567

926
00:50:49,567 --> 00:50:50,400
Така че това е капацитет.

927
00:50:50,400 --> 00:50:55,890

928
00:50:55,890 --> 00:50:59,660
>> Така че това действително ще
ви дам един начин да го направя.

929
00:50:59,660 --> 00:51:03,205

930
00:51:03,205 --> 00:51:04,330
Защото в този случай, какво?

931
00:51:04,330 --> 00:51:09,205
Главата ни е на 1, нашия размер е 4.

932
00:51:09,205 --> 00:51:11,760

933
00:51:11,760 --> 00:51:18,490
Ако Министерството на отбраната, че до 5, ще получите 0,
което е мястото, където ние трябва да го въведете.

934
00:51:18,490 --> 00:51:23,320

935
00:51:23,320 --> 00:51:26,080
>> Така че след това в следващия случай,
ако трябва да направите това,

936
00:51:26,080 --> 00:51:33,390
ние казваме, добре, нека dequeue нещо.

937
00:51:33,390 --> 00:51:34,390
Ние dequeue това.

938
00:51:34,390 --> 00:51:37,740
Ние приемаме този елемент, нали?

939
00:51:37,740 --> 00:51:47,930
>> И сега главата ни се посочи тук,
и ние искаме да се добави в друго нещо.

940
00:51:47,930 --> 00:51:52,470
Това е в общи линии
обратно на нашата линия, нали?

941
00:51:52,470 --> 00:51:55,450
Опашките могат да увийте около масива.

942
00:51:55,450 --> 00:51:57,310
Това е една от основните разлики.

943
00:51:57,310 --> 00:51:58,780
Купища, не можете да направите това.

944
00:51:58,780 --> 00:52:01,140
>> С опашки, можете да
защото всичко, което има значение

945
00:52:01,140 --> 00:52:03,940
е, че вие ​​знаете какво
най-наскоро беше добавен.

946
00:52:03,940 --> 00:52:10,650
Тъй като всичко ще бъде добавен в
това наляво посока, в този случай,

947
00:52:10,650 --> 00:52:16,480
и след това увийте около, можете да
продължи въвеждането на нови елементи

948
00:52:16,480 --> 00:52:18,830
в предната част на масива
защото това не е наистина

949
00:52:18,830 --> 00:52:20,640
предната част на масива вече.

950
00:52:20,640 --> 00:52:26,320
Можете да мислите за началото на
масив и когато главата ти в действителност.

951
00:52:26,320 --> 00:52:29,710
>> Така че тази формула е как
да се изчисли си опашка.

952
00:52:29,710 --> 00:52:32,780

953
00:52:32,780 --> 00:52:35,610
Ли, че има смисъл?

954
00:52:35,610 --> 00:52:36,110
OK.

955
00:52:36,110 --> 00:52:39,400

956
00:52:39,400 --> 00:52:44,040
OK, dequeue, и след това
вие имате 10 минути

957
00:52:44,040 --> 00:52:48,840
да ми задавате уточняващи въпроси
искате, защото знам, че е луд.

958
00:52:48,840 --> 00:52:51,980
>> Добре, така че в същата way--
Аз не знам, ако вие забелязали,

959
00:52:51,980 --> 00:52:53,450
но CS е за всички модели.

960
00:52:53,450 --> 00:52:57,370
Нещата са доста по
едни и същи, само с малки ощипвам.

961
00:52:57,370 --> 00:52:58,950
Така че едно и също нещо тук.

962
00:52:58,950 --> 00:53:04,040
Ние трябва да се провери, за да видите, ако ние всъщност
има нещо в нашата опашка, нали?

963
00:53:04,040 --> 00:53:05,960
Кажи, OK, е нашият размер по-голям от 0?

964
00:53:05,960 --> 00:53:06,730
Cool.

965
00:53:06,730 --> 00:53:10,690
>> Ако го направим, тогава ние се движи главата си, което
е това, което току-що демонстрира тук.

966
00:53:10,690 --> 00:53:13,870
Ние актуализира главата ни да бъде един повече.

967
00:53:13,870 --> 00:53:18,390
И тогава ние намалите стъпково ни
размер и да се върнете на елемента.

968
00:53:18,390 --> 00:53:21,000

969
00:53:21,000 --> 00:53:26,250
>> Има много неща, по-конкретно
код на study.cs50.net,

970
00:53:26,250 --> 00:53:29,440
и аз силно препоръчвам става
чрез нея, ако имате време,

971
00:53:29,440 --> 00:53:30,980
дори ако това е само псевдо-код.

972
00:53:30,980 --> 00:53:35,980
И ако вие искате да говорите чрез
че с мен един по един, моля ви кажете ми

973
00:53:35,980 --> 00:53:37,500
знам.

974
00:53:37,500 --> 00:53:38,770
Щях да бъда щастлив да.

975
00:53:38,770 --> 00:53:42,720
Структури от данни, ако
вземете CS 124, ще

976
00:53:42,720 --> 00:53:47,830
Знам, че структури от данни стават много
забавно и това е само началото.

977
00:53:47,830 --> 00:53:50,350
>> Така че аз знам, че е трудно.

978
00:53:50,350 --> 00:53:51,300
Това е ОК.

979
00:53:51,300 --> 00:53:52,410
Ние се борим.

980
00:53:52,410 --> 00:53:53,630
Аз все още го правя.

981
00:53:53,630 --> 00:53:56,660
Така че не се тревожи твърде много за това.

982
00:53:56,660 --> 00:54:02,390
>> Но това е в основата си
катастрофата курс по структури от данни.

983
00:54:02,390 --> 00:54:03,400
Знам, че е много.

984
00:54:03,400 --> 00:54:06,860
Има ли нещо, което ние
биха искали да отидете отново?

985
00:54:06,860 --> 00:54:09,400
Всичко, което искаме да говорим чрез?

986
00:54:09,400 --> 00:54:10,060
Да?

987
00:54:10,060 --> 00:54:16,525
>> АУДИТОРИЯ: За този пример, така че
новата опашката е 0 над това?

988
00:54:16,525 --> 00:54:17,150
SPEAKER 1: Да.

989
00:54:17,150 --> 00:54:18,230
АУДИТОРИЯ: OK.

990
00:54:18,230 --> 00:54:24,220
Така че след това преминава през,
ще имате един плюс 4 or--

991
00:54:24,220 --> 00:54:27,671
>> SPEAKER 1: Така ли се казва,
когато искаме да направим това отново?

992
00:54:27,671 --> 00:54:28,296
АУДИТОРИЯ: Да.

993
00:54:28,296 --> 00:54:38,290
Така че, ако сте били фигуриращ out-- където са
ви изчисляване на опашката от това, че?

994
00:54:38,290 --> 00:54:44,260
>> SPEAKER 1: Така опашката
е in-- смених това.

995
00:54:44,260 --> 00:54:52,010
Така че в този пример тук, това е
масива гледаме, OK?

996
00:54:52,010 --> 00:54:54,670
Така че ние имаме неща в 1, 2, 3 и 4.

997
00:54:54,670 --> 00:55:05,850
Така че ние имаме нашата глава е равна на 1 в
този момент, и нашия размер е равен на 4

998
00:55:05,850 --> 00:55:07,050
в този момент, нали?

999
00:55:07,050 --> 00:55:08,960
>> Вие всички ще се съгласим, че е така?

1000
00:55:08,960 --> 00:55:14,620
Така че правим главата плюс размера, който
ни дава 5, а след това Министерството на отбраната с 5.

1001
00:55:14,620 --> 00:55:20,690
Ние получаваме 0, което ни казва, че 0 е
където е нашата опашка, където имаме пространство.

1002
00:55:20,690 --> 00:55:22,010
>> АУДИТОРИЯ: Какво е шапка?

1003
00:55:22,010 --> 00:55:23,520
>> SPEAKER 1: Капацитетът.

1004
00:55:23,520 --> 00:55:24,020
Извинете.

1005
00:55:24,020 --> 00:55:29,640
Така че това е размера на масив.

1006
00:55:29,640 --> 00:55:35,210

1007
00:55:35,210 --> 00:55:36,047
Да?

1008
00:55:36,047 --> 00:55:39,210
>> АУДИТОРИЯ: [недоловим] преди
ние върне елемент?

1009
00:55:39,210 --> 00:55:46,270
>> SPEAKER 1: Така че ние се премести на
главата или да се върне в момента?

1010
00:55:46,270 --> 00:55:52,680
Така че, ако ние се движат един, намалите постъпково размера?

1011
00:55:52,680 --> 00:55:54,150
Дръж се.

1012
00:55:54,150 --> 00:55:55,770
Определено забравих друг.

1013
00:55:55,770 --> 00:56:00,646

1014
00:56:00,646 --> 00:56:01,990
Няма нищо.

1015
00:56:01,990 --> 00:56:04,980
Там не е друга формула.

1016
00:56:04,980 --> 00:56:09,980
Да, вие ще искате да се върнете
на главата и след това се върнете обратно.

1017
00:56:09,980 --> 00:56:13,270
>> АУДИТОРИЯ: ОК, защото в този
точка, ръководител е на 0,

1018
00:56:13,270 --> 00:56:18,452
и след това искате да се върнете
индекс 0 и след това направи главата 1?

1019
00:56:18,452 --> 00:56:19,870
>> SPEAKER 1: Точно така.

1020
00:56:19,870 --> 00:56:22,820
Аз мисля, че има друг
формула нещо като това.

1021
00:56:22,820 --> 00:56:26,970
Аз не разполагат с него на върха на главата ми,
Аз не искам да ви даде грешен.

1022
00:56:26,970 --> 00:56:35,470
Но аз мисля, че е напълно валидна до
да речем, OK, съхранявайте това element-- каквото

1023
00:56:35,470 --> 00:56:40,759
елемент главата на is-- намалите стъпково си
размер, движи главата си над и връщане

1024
00:56:40,759 --> 00:56:41,800
каквото и да е елемент.

1025
00:56:41,800 --> 00:56:44,760
Това е напълно валиден.

1026
00:56:44,760 --> 00:56:45,260
OK.

1027
00:56:45,260 --> 00:56:48,360

1028
00:56:48,360 --> 00:56:53,560
Имам чувството, че това не е
като most-- не сте

1029
00:56:53,560 --> 00:56:55,740
ще излезе от тук
като, да, знам, че се опитва.

1030
00:56:55,740 --> 00:56:56,880
Аз го има всичко.

1031
00:56:56,880 --> 00:56:57,670
Това е ОК.

1032
00:56:57,670 --> 00:57:00,200
Обещавам.

1033
00:57:00,200 --> 00:57:05,240
Но структури от данни са нещо, което
това отнема много време, за да свикнеш.

1034
00:57:05,240 --> 00:57:10,010
Вероятно една от най-трудните
неща, мисля, че в курса.

1035
00:57:10,010 --> 00:57:15,330
>> Така че определено се
повторение и търсите at-- I

1036
00:57:15,330 --> 00:57:20,050
наистина не знам свързани списъци
докато аз го направих твърде много с тях,

1037
00:57:20,050 --> 00:57:22,550
по същия начин, че не го направих
Наистина разбирам указатели

1038
00:57:22,550 --> 00:57:27,040
докато аз трябваше да го научи за двама
години и да направят собствените си psets с него.

1039
00:57:27,040 --> 00:57:28,990
Това отнема много повторения и време.

1040
00:57:28,990 --> 00:57:32,600
И в крайна сметка, тя вид ще изберете.

1041
00:57:32,600 --> 00:57:36,320
>> Но в същото време, ако имате вид
на разбиране на високо ниво, което

1042
00:57:36,320 --> 00:57:39,321
те правят, техните плюсове
и cons-- което е това, което

1043
00:57:39,321 --> 00:57:41,820
ние наистина са склонни да се подчертае,
особено в хода интро.

1044
00:57:41,820 --> 00:57:45,511
Например, защо да използваме
пробвам над масив?

1045
00:57:45,511 --> 00:57:48,010
Например, какви са позитивите
и негативи на всяка една от тези?

1046
00:57:48,010 --> 00:57:51,610
>> И разбирането на компромисите
между всеки от тези структури

1047
00:57:51,610 --> 00:57:54,910
е това, което е много по-важно в момента.

1048
00:57:54,910 --> 00:57:58,140
Възможно е да има един луд
или два въпроса, които е

1049
00:57:58,140 --> 00:58:03,710
Ще ви помоля да приложат натиск или
изпълнява поп или Enqueue и dequeue.

1050
00:58:03,710 --> 00:58:07,340
Но за по-голямата част, като че
висше разбиране ниво и по-

1051
00:58:07,340 --> 00:58:09,710
на интуитивно разбиране е
по-важно, отколкото в действителност

1052
00:58:09,710 --> 00:58:11,250
е в състояние да го изпълни.

1053
00:58:11,250 --> 00:58:14,880
>> Ще бъде наистина страхотно, ако всички вие
може да изляза и да се приложи пробвам,

1054
00:58:14,880 --> 00:58:19,720
но ние разбираме, че не е задължително
най-разумното нещо, което точно сега.

1055
00:58:19,720 --> 00:58:23,370
Но можете в pset, ако искате
да, и тогава вие ще получите практика,

1056
00:58:23,370 --> 00:58:27,200
и тогава може би ще
наистина го разбирам.

1057
00:58:27,200 --> 00:58:27,940
Да?

1058
00:58:27,940 --> 00:58:30,440
>> АУДИТОРИЯ: ОК, така, кои от тях са
ние трябваше да се използва в pset?

1059
00:58:30,440 --> 00:58:31,916
Трябва ли да се използва един от тях?

1060
00:58:31,916 --> 00:58:32,540
SPEAKER 1: Да.

1061
00:58:32,540 --> 00:58:34,199
Така че имате избор.

1062
00:58:34,199 --> 00:58:36,740
Предполагам, че в този случай, ние можем
говорим за pset малко

1063
00:58:36,740 --> 00:58:40,480
защото аз се завтече през тях.

1064
00:58:40,480 --> 00:58:47,779
Така че във вашия pset, имате
избор на опита или хеш таблици.

1065
00:58:47,779 --> 00:58:49,570
Някои хора ще се опитат
и да използвате един цвят филтри,

1066
00:58:49,570 --> 00:58:51,840
но тези, които технически не са правилни.

1067
00:58:51,840 --> 00:58:55,804
Поради вероятностен характер,
те дават неверни положителни резултати понякога.

1068
00:58:55,804 --> 00:58:57,095
Те са хладен поглед, все пак.

1069
00:58:57,095 --> 00:58:59,030
Силно препоръчваме да търсите
в тях най-малко.

1070
00:58:59,030 --> 00:59:03,260
Но вие имате избор
между хеш таблица и пробвам.

1071
00:59:03,260 --> 00:59:06,660
И това ще бъде мястото, където
заредите във вашия речник.

1072
00:59:06,660 --> 00:59:09,230
>> И вие ще трябва да изберете
Вашата хеш функция,

1073
00:59:09,230 --> 00:59:13,420
вие ще трябва да изберете колко
Кофи имате, и тя ще варира.

1074
00:59:13,420 --> 00:59:17,440
Например, ако имате повече кофи,
Може би тя ще работи по-бързо.

1075
00:59:17,440 --> 00:59:22,790
Но може би вие губите
много пространство по този начин, все пак.

1076
00:59:22,790 --> 00:59:26,320
Трябва да го разбера.

1077
00:59:26,320 --> 00:59:27,140
Mmhmm?

1078
00:59:27,140 --> 00:59:29,875
>> АУДИТОРИЯ: Ти каза, че преди това
ние може да се използват и други хеш функции,

1079
00:59:29,875 --> 00:59:31,750
че ние не трябва да се
създаване на хеш функция?

1080
00:59:31,750 --> 00:59:32,666
>> SPEAKER 1: Да, точно така.

1081
00:59:32,666 --> 00:59:38,150
Така буквално за хеш функция,
като Google "хеш функция"

1082
00:59:38,150 --> 00:59:40,770
и за някои готини хора изглежда.

1083
00:59:40,770 --> 00:59:43,250
Не се очаква да се изгради
Вашите собствени хеш функции.

1084
00:59:43,250 --> 00:59:46,100
Хората прекарват
дипломни работи по тези неща.

1085
00:59:46,100 --> 00:59:50,250
>> Така че не се тревожи за изграждането на вашия собствен.

1086
00:59:50,250 --> 00:59:53,350
Намери един онлайн, за да започнете.

1087
00:59:53,350 --> 00:59:56,120
Някои от тях ще трябва да
манипулира малко

1088
00:59:56,120 --> 00:59:59,430
да се уверите, вида връщане съвпадат
и какво ли не, така че в началото,

1089
00:59:59,430 --> 01:00:02,420
Бих препоръчваме да използвате нещо
много лесно, че може би просто

1090
01:00:02,420 --> 01:00:04,680
хешове на първата буква.

1091
01:00:04,680 --> 01:00:08,760
И след това, след като сте, че работи,
вграден охладител хеш функция.

1092
01:00:08,760 --> 01:00:09,260
Mmhmm?

1093
01:00:09,260 --> 01:00:13,020
>> АУДИТОРИЯ: Ще пробвам да бъде или
ефективно, но просто по-трудно да, like--

1094
01:00:13,020 --> 01:00:15,880
>> SPEAKER 1: Значи пробвам, мисля,
е интуитивно трудно да се приложат

1095
01:00:15,880 --> 01:00:18,310
но е много бърз.

1096
01:00:18,310 --> 01:00:20,620
Въпреки това, заема повече място.

1097
01:00:20,620 --> 01:00:25,270
Отново можете да оптимизирате и двете от тези в
различни начини и има начини to--

1098
01:00:25,270 --> 01:00:26,770
АУДИТОРИЯ: Как сме класирани по този въпрос?

1099
01:00:26,770 --> 01:00:27,540
Има ли matter--

1100
01:00:27,540 --> 01:00:29,164
>> SPEAKER 1: Значи степен нормален начин.

1101
01:00:29,164 --> 01:00:31,330
Ти започваш да бъдат категоризирани по дизайн.

1102
01:00:31,330 --> 01:00:36,020
Накъдето и да правите, вие искате да
уверете, че тя е толкова елегантен, колкото може да бъде

1103
01:00:36,020 --> 01:00:38,610
и толкова ефективно, колкото може да бъде.

1104
01:00:38,610 --> 01:00:41,950
Но ако решите да опитате или хашиш
маса, докато тя работи,

1105
01:00:41,950 --> 01:00:45,350
ние сме щастливи с това.

1106
01:00:45,350 --> 01:00:48,370
И ако използвате нещо, което хешове
на първата буква, това е добре,

1107
01:00:48,370 --> 01:00:51,410
като може би като дизайн-мъдър.

1108
01:00:51,410 --> 01:00:53,410
Ние сме също така достигането на
точка в тази semester--

1109
01:00:53,410 --> 01:00:55,340
Аз не знам дали сте
момчета noticed-- ако сте

1110
01:00:55,340 --> 01:00:58,780
pset класове намалеят малко
защото на дизайн и какво ли не,

1111
01:00:58,780 --> 01:00:59,900
това е съвършено глоба.

1112
01:00:59,900 --> 01:01:02,960
Става все по-до точката, където си
програми стават все по-сложни.

1113
01:01:02,960 --> 01:01:04,830
Има повече места
можете да подобрите.

1114
01:01:04,830 --> 01:01:06,370
>> Така че това е напълно нормално.

1115
01:01:06,370 --> 01:01:08,810
Това не е, че сте
прави лошо на вашия pset.

1116
01:01:08,810 --> 01:01:11,885
Това е просто ние сме в по-трудно за вас сега.

1117
01:01:11,885 --> 01:01:13,732
Така че всеки е това чувство.

1118
01:01:13,732 --> 01:01:14,940
Просто степен всичките си psets.

1119
01:01:14,940 --> 01:01:16,490
Знам, че всеки го чувстваш.

1120
01:01:16,490 --> 01:01:19,600
>> Така че не се тревожи за това.

1121
01:01:19,600 --> 01:01:23,580
И ако имате някакви въпроси относно
преди psets или начини да се подобри,

1122
01:01:23,580 --> 01:01:27,760
Опитвам се и коментира спецификата
места, но понякога това е края

1123
01:01:27,760 --> 01:01:30,840
и аз се уморяват.

1124
01:01:30,840 --> 01:01:34,885
Има ли някакви други неща
около структури от данни?

1125
01:01:34,885 --> 01:01:37,510
Сигурен съм, че вие ​​наистина не
искам да говоря за тях повече,

1126
01:01:37,510 --> 01:01:42,650
но ако има, аз съм щастлив да
отида с тях, както и всичко,

1127
01:01:42,650 --> 01:01:45,580
от лекция миналия
седмица или миналата седмица.

1128
01:01:45,580 --> 01:01:51,580
>> Знам, че миналата седмица беше преглед, така че
ние може да прескочи някои преглед

1129
01:01:51,580 --> 01:01:54,190
от лекция.

1130
01:01:54,190 --> 01:01:58,230
Всякакви други въпроси мога да отговоря?

1131
01:01:58,230 --> 01:01:59,350
Добре, всичко е наред.

1132
01:01:59,350 --> 01:02:02,400
Е, вие се измъкнем 15 минути по-рано.

1133
01:02:02,400 --> 01:02:08,370
>> Надявам се, че това е полу-полезен най-малкото,
и аз ще ви видя, момчета следващата седмица,

1134
01:02:08,370 --> 01:02:12,150
или четвъртък работно време.

1135
01:02:12,150 --> 01:02:15,285
Има ли искания за закуски
за следващата седмица, това е нещо?

1136
01:02:15,285 --> 01:02:17,459
Защото аз забравих бонбони днес.

1137
01:02:17,459 --> 01:02:19,750
И донесе бонбони последно
седмица, но това е Деня на Колумб,

1138
01:02:19,750 --> 01:02:25,400
така че там бяха като шест души, които
имаше четири торби с бонбони за себе си.

1139
01:02:25,400 --> 01:02:28,820
Аз може да донесе Starbursts
отново, ако искате.

1140
01:02:28,820 --> 01:02:29,580
Starbursts?

1141
01:02:29,580 --> 01:02:32,250
ОК, звучи добре.

1142
01:02:32,250 --> 01:02:35,050
Имате голям ден, момчета.

1143
01:02:35,050 --> 01:02:39,510