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

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

3
00:00:03,340 --> 00:00:11,020

4
00:00:11,020 --> 00:00:14,010
>> DAVID Malan: Това е CS50.

5
00:00:14,010 --> 00:00:18,090
И това е, както за началото и
end-- като literally-- почти до края

6
00:00:18,090 --> 00:00:18,825
на шестата седмица.

7
00:00:18,825 --> 00:00:20,030

8
00:00:20,030 --> 00:00:22,640
>> Мислех, че ще споделите
малко един забавен факт.

9
00:00:22,640 --> 00:00:25,370
Аз бях изтеглен тази изправяне от
определени данни минало семестър е.

10
00:00:25,370 --> 00:00:29,710
Може би си спомняте, че ние ви молим за всеки
р набор форма, ако сте гледали онлайн

11
00:00:29,710 --> 00:00:31,580
или ако сте присъства лично.

12
00:00:31,580 --> 00:00:33,020
И тук са данните.

13
00:00:33,020 --> 00:00:34,710
Така че днес е много по-предсказуема.

14
00:00:34,710 --> 00:00:37,126
Но ние искахме да прекарат малко
от време с вас все пак.

15
00:00:37,126 --> 00:00:40,599
Дали някой искал да предположим защо тази
графика е толкова съдран, нагоре надолу, нагоре надолу,

16
00:00:40,599 --> 00:00:41,265
така постоянно?

17
00:00:41,265 --> 00:00:42,980

18
00:00:42,980 --> 00:00:45,130
Какво направи всеки един от върховете
и улеи представляват?

19
00:00:45,130 --> 00:00:46,005
>> АУДИТОРИЯ: [недоловим]

20
00:00:46,005 --> 00:00:47,002

21
00:00:47,002 --> 00:00:47,835
DAVID Malan: Наистина.

22
00:00:47,835 --> 00:00:50,900

23
00:00:50,900 --> 00:00:55,480
И по-забавно, не дай боже,
ние държим една лекция в петък

24
00:00:55,480 --> 00:00:58,960
в началото на семестъра,
това е, което виждаме да се случи.

25
00:00:58,960 --> 00:01:03,430
Така че днес, ние участваме в малко
повече за структури от данни.

26
00:01:03,430 --> 00:01:06,660
И за да ви дам повече от солидна
мисловен модел за проблеми в пет,

27
00:01:06,660 --> 00:01:07,450
който сега е навън.

28
00:01:07,450 --> 00:01:10,817
Правописни грешки, при което ние ще
ви предаде текстов файл някои 100,000

29
00:01:10,817 --> 00:01:12,650
плюс английски думи, и
ти започваш да имат

30
00:01:12,650 --> 00:01:17,770
за да разбера как да се умело ги заредите
в паметта, в RAM, използвайки някои данни

31
00:01:17,770 --> 00:01:19,330
структура по свой избор.

32
00:01:19,330 --> 00:01:22,470
>> Сега една такава структура на данните може
да, но най-вероятно не трябва да бъде,

33
00:01:22,470 --> 00:01:25,630
сравнително опростен свързан списък,
които ние въведохме за последен път.

34
00:01:25,630 --> 00:01:29,220
И свързан списък е имал най-малко
едно предимство над масив.

35
00:01:29,220 --> 00:01:32,096
Какво е едно предимство на
свързан списък може би?

36
00:01:32,096 --> 00:01:32,950
>> АУДИТОРИЯ: вмъкване.

37
00:01:32,950 --> 00:01:33,908
>> DAVID Malan: вмъкване.

38
00:01:33,908 --> 00:01:34,155

39
00:01:34,155 --> 00:01:35,196
Какво искаш да кажеш с това?

40
00:01:35,196 --> 00:01:37,872
>> АУДИТОРИЯ: Anywhere заедно
списъка [недоловим].

41
00:01:37,872 --> 00:01:38,770
>> DAVID Malan: Добре.

42
00:01:38,770 --> 00:01:42,090
Така че можете да вмъкнете елемент, където
искате в средата на списъка

43
00:01:42,090 --> 00:01:45,490
без да се налага да разбъркате всичко,
които ние заключихме, в нашия сортиране

44
00:01:45,490 --> 00:01:47,630
дискусии, не е
непременно нещо добро,

45
00:01:47,630 --> 00:01:51,200
защото това отнема време да се действително се движат
всички тези хора, наляво или надясно.

46
00:01:51,200 --> 00:01:55,540
И така със свързан списък, можете да
просто разпределя с изчистване, нов възел,

47
00:01:55,540 --> 00:01:58,385
и след това да актуализирате няколко
pointers-- две, три операции max--

48
00:01:58,385 --> 00:02:01,480
и ние сме в състояние да се промуши човек
навсякъде в списък.

49
00:02:01,480 --> 00:02:03,550
>> Какво друго е изгодно
за свързан списък?

50
00:02:03,550 --> 00:02:04,980

51
00:02:04,980 --> 00:02:05,659
Така ли?

52
00:02:05,659 --> 00:02:06,534
>> АУДИТОРИЯ: [недоловим]

53
00:02:06,534 --> 00:02:07,538

54
00:02:07,538 --> 00:02:08,413
DAVID Malan: Perfect.

55
00:02:08,413 --> 00:02:10,590

56
00:02:10,590 --> 00:02:11,090
Perfect.

57
00:02:11,090 --> 00:02:12,070
Това наистина е много динамичен.

58
00:02:12,070 --> 00:02:15,100
И че не сте извършва,
предварително до известна фиксиран размер

59
00:02:15,100 --> 00:02:18,750
парче от паметта, като вие ще трябва
да с масив, нагоре от които

60
00:02:18,750 --> 00:02:22,455
е, че могат да отделят възли само на
търсенето като по този начин се използват само най-голямо пространство

61
00:02:22,455 --> 00:02:23,330
като действително се нуждаят.

62
00:02:23,330 --> 00:02:26,830
За разлика от масив, може да
случайно се разпределят твърде малко.

63
00:02:26,830 --> 00:02:28,871
И след това просто ще
да бъде болка в областта на шията

64
00:02:28,871 --> 00:02:32,440
да преразпредели нов голям масив, копирате
всичко свърши, освободи стария масив,

65
00:02:32,440 --> 00:02:33,990
и след това се премести за вашия бизнес.

66
00:02:33,990 --> 00:02:37,479
Или по-лошо, може да се отпусне начин
повече памет, отколкото сте в действителност се нуждае,

67
00:02:37,479 --> 00:02:40,520
и така вие ще имате много
слабо населени масив, така да се каже.

68
00:02:40,520 --> 00:02:44,350
>> Така свързан списък дава тези
предимства на динамика и гъвкавост

69
00:02:44,350 --> 00:02:46,080
с инсерции и делеции.

70
00:02:46,080 --> 00:02:48,000
Но със сигурност трябва да има цена, платена.

71
00:02:48,000 --> 00:02:50,000
Всъщност, една от темите
проучени викторина нула

72
00:02:50,000 --> 00:02:52,430
е няколко компромисите
сме виждали до този момент.

73
00:02:52,430 --> 00:02:56,161
Така че това, което е платена цена или
Недостатъкът на свързан списък?

74
00:02:56,161 --> 00:02:56,660
Да.

75
00:02:56,660 --> 00:02:57,560
>> АУДИТОРИЯ: No произволен достъп.

76
00:02:57,560 --> 00:02:58,809
>> DAVID Malan: No произволен достъп.

77
00:02:58,809 --> 00:02:59,540
Но на кого му пука?

78
00:02:59,540 --> 00:03:01,546
Произволен достъп не звучи убедителна.

79
00:03:01,546 --> 00:03:02,421
>> АУДИТОРИЯ: [недоловим]

80
00:03:02,421 --> 00:03:04,865

81
00:03:04,865 --> 00:03:05,740
DAVID Malan: Точно така.

82
00:03:05,740 --> 00:03:07,580
Ако искате да имате
определен algorithm--

83
00:03:07,580 --> 00:03:10,170
и нека действително да предложи
търсене двоичен по-специално, което

84
00:03:10,170 --> 00:03:12,600
е едно сме използвали доста bit--
ако не разполагате със свободен достъп,

85
00:03:12,600 --> 00:03:15,516
не можеш да направиш, че проста аритметика
за намиране като средния елемент

86
00:03:15,516 --> 00:03:16,530
и скача към него.

87
00:03:16,530 --> 00:03:20,239
Вие вместо да започне в първата
елемент и линейно търсене отляво

88
00:03:20,239 --> 00:03:22,780
надясно, ако искате да намерите
средата или някакъв друг елемент.

89
00:03:22,780 --> 00:03:24,410
>> АУДИТОРИЯ: Вероятно отнема повече памет.

90
00:03:24,410 --> 00:03:25,040
>> DAVID Malan: отнема повече памет.

91
00:03:25,040 --> 00:03:27,464
Къде е тази допълнителна
струва, идващи от паметта?

92
00:03:27,464 --> 00:03:28,339
>> АУДИТОРИЯ: [недоловим]

93
00:03:28,339 --> 00:03:32,566

94
00:03:32,566 --> 00:03:33,440
DAVID Malan: Точно така.

95
00:03:33,440 --> 00:03:35,679
В този случай тук, имахме
свързан списък за цели числа,

96
00:03:35,679 --> 00:03:37,470
и все пак ние сме удвояване
размера на паметта

97
00:03:37,470 --> 00:03:39,680
ние се нуждаем от и съхраняване на тези насоки.

98
00:03:39,680 --> 00:03:42,090
Сега по-малко от една голяма сделка, както
Вашите structs получават по-големи

99
00:03:42,090 --> 00:03:45,320
и сте съхранение не е номер, но
може би студент или някакъв друг обект.

100
00:03:45,320 --> 00:03:46,880
Но въпросът със сигурност остава.

101
00:03:46,880 --> 00:03:49,421
И така, някои от операциите
на свързани списъци бяха наречени

102
00:03:49,421 --> 00:03:50,570
бяха големи O на, N- линейна.

103
00:03:50,570 --> 00:03:54,730
Неща като вмъкване или търсене
или заличаване в случай елемент

104
00:03:54,730 --> 00:03:57,720
се случи да бъде в самия край на
списъка независимо дали е сортирано или не.

105
00:03:57,720 --> 00:04:01,167
>> Понякога може да получите късмет и в
толкова по-ниски граници на тези операции

106
00:04:01,167 --> 00:04:04,250
може също така да бъде постоянно време, ако сте
винаги търсим в първия елемент,

107
00:04:04,250 --> 00:04:05,070
например.

108
00:04:05,070 --> 00:04:09,360
Но в крайна сметка, ние обеща
за постигане на Светия Граал

109
00:04:09,360 --> 00:04:12,630
на структури от данни, или
някои сближаване него,

110
00:04:12,630 --> 00:04:14,290
по пътя на постоянно време.

111
00:04:14,290 --> 00:04:17,579
Можем ли да намерим елементи или добавяне на елементи
или премахване на елементи от списък?

112
00:04:17,579 --> 00:04:19,059
Ние ще видим съвсем скоро.

113
00:04:19,059 --> 00:04:21,100
И се оказва, че един
на механизмите, ние сме

114
00:04:21,100 --> 00:04:23,464
ще започне да се използва и днес,
годишното потребление в р определя пет,

115
00:04:23,464 --> 00:04:24,630
всъщност е доста познато.

116
00:04:24,630 --> 00:04:27,430
Например, ако това е куп
на изпита книги, всеки от които

117
00:04:27,430 --> 00:04:29,660
има студент първи
име и фамилия на нея,

118
00:04:29,660 --> 00:04:31,820
и аз си ги вземете от
в края на изпита,

119
00:04:31,820 --> 00:04:33,746
и всички те са доста
много в произволен ред,

120
00:04:33,746 --> 00:04:36,370
и ние искаме да отидем за сортиране
тези изпити, така че веднъж степенуват

121
00:04:36,370 --> 00:04:38,661
това е просто много по-лесно и
по-бързо, за да ги предаде обратно

122
00:04:38,661 --> 00:04:40,030
за студенти по азбучен ред.

123
00:04:40,030 --> 00:04:42,770
Какви биха били вашите инстинкти
за купчина изпити като този?

124
00:04:42,770 --> 00:04:45,019
>> Е, ако сте като мен,
може да се види, че това е m,

125
00:04:45,019 --> 00:04:48,505
така че аз отивам да сортирате сложи това под,
ако това е моята маса или ми етаж, където

126
00:04:48,505 --> 00:04:50,650
Аз разпространение неща
out-- или моя масив really--

127
00:04:50,650 --> 00:04:52,210
I може да се постави цялата на г-жа там.

128
00:04:52,210 --> 00:04:52,710
О.

129
00:04:52,710 --> 00:04:55,020
Ето един A. Така че бих могъл
поставя, както е тук.

130
00:04:55,020 --> 00:04:55,520
О.

131
00:04:55,520 --> 00:04:57,980
Ето още един A. Отивам
да сложи това тук.

132
00:04:57,980 --> 00:05:02,490
Ето един Z. Тук е друг M. И така
I може да започнете да печелите пилоти като този.

133
00:05:02,490 --> 00:05:06,620
И тогава може би щях да отида в по-късно
и нещо много nitpicky-Ly сортиране

134
00:05:06,620 --> 00:05:07,710
отделните купчини.

135
00:05:07,710 --> 00:05:11,300
Но въпросът е, аз ще гледам
на входа, че аз съм ръка

136
00:05:11,300 --> 00:05:14,016
и бих искал да се направят някои изчислява
решение въз основа на този вход.

137
00:05:14,016 --> 00:05:15,640
Ако тя започва с А, я сложи там.

138
00:05:15,640 --> 00:05:18,980
Ако тя започва с Z, поставете го върху
там, и всичко между тях.

139
00:05:18,980 --> 00:05:22,730
>> Така че това е техника, която е
известен като hashing-- H-A-S-H--

140
00:05:22,730 --> 00:05:26,550
които най-общо означава да се вземат като
въвеждане и използване на този вход, за да се изчисли

141
00:05:26,550 --> 00:05:30,940
стойност, като цяло число, и че
номер на индекса в съхранение

142
00:05:30,940 --> 00:05:32,260
контейнер, като масив.

143
00:05:32,260 --> 00:05:35,490
Така че с други думи, може да има
хеш функция, както аз правя в главата ми,

144
00:05:35,490 --> 00:05:37,940
че ако видя някой е
име, което започва с A,

145
00:05:37,940 --> 00:05:40,190
Отивам да се набележат, че
до нула в главата ми.

146
00:05:40,190 --> 00:05:44,160
И ако видя някой с Z, аз съм
Ще карта, че до 25 в главата ми

147
00:05:44,160 --> 00:05:46,220
и след това пуснати, че в
последната най-купчината.

148
00:05:46,220 --> 00:05:50,990
>> Сега, ако мислите, че не мозъкът ми
но програмата C, какви номера могат

149
00:05:50,990 --> 00:05:53,170
вие разчитате, за да се постигне същия резултат?

150
00:05:53,170 --> 00:05:55,594
С други думи, ако сте
имаше ASCII символи А,

151
00:05:55,594 --> 00:05:57,510
как да се определи
какво кофа, за да го сложи в?

152
00:05:57,510 --> 00:05:59,801
Може би не искате да
го постави в кофа 65, което

153
00:05:59,801 --> 00:06:01,840
ще бъде като там
без основателна причина.

154
00:06:01,840 --> 00:06:04,320
Къде искате да поставите A
по отношение на ASCII стойност?

155
00:06:04,320 --> 00:06:05,600

156
00:06:05,600 --> 00:06:08,920
Къде искаш да направя, за да си ASCII
стойност да излезе с по-интелигентна кофа

157
00:06:08,920 --> 00:06:09,480
да го поставите в?

158
00:06:09,480 --> 00:06:10,206
>> АУДИТОРИЯ: Minus A.

159
00:06:10,206 --> 00:06:10,956
>> DAVID Malan: Да.

160
00:06:10,956 --> 00:06:13,190
Така минус A или минус
специално 65, ако това е

161
00:06:13,190 --> 00:06:18,240
капитал А. Или 98, ако
това е с малки букви а.

162
00:06:18,240 --> 00:06:21,300
И така, това ще ни позволи да, много
просто и много аритметично,

163
00:06:21,300 --> 00:06:23,260
сложи нещо в кофа подобно.

164
00:06:23,260 --> 00:06:26,010
Така се оказва, че ние всъщност правим
това, както добре дори и с викторини.

165
00:06:26,010 --> 00:06:29,051
>> Така че можете да си спомните, че отбележите си
Име на преподаване колега на корицата.

166
00:06:29,051 --> 00:06:32,270
И бяха организирани имена на ТФ
в тези колони, по азбучен ред,

167
00:06:32,270 --> 00:06:34,400
Е, вярвате или не,
когато всички 80 плюс един от нас

168
00:06:34,400 --> 00:06:37,800
Събрахме се онази вечер до степен,
последната стъпка в нашия процес на категоризация

169
00:06:37,800 --> 00:06:41,830
е да се разискват на тестовете в голяма
пространство на пода на [недоловим]

170
00:06:41,830 --> 00:06:45,110
и да се викторини на всеки от
точно по реда на техните ТФ

171
00:06:45,110 --> 00:06:47,700
имена на корицата, защото
тогава е много по-лесно за нас

172
00:06:47,700 --> 00:06:51,290
да търсите чрез които се използва линейна
търсите или някакъв вид интелигентност

173
00:06:51,290 --> 00:06:54,050
за TF да намери своя или
викторини си студентите.

174
00:06:54,050 --> 00:06:56,060
>> Така че тази идея за хеширане
че вие ​​ще видите, е

175
00:06:56,060 --> 00:07:00,520
доста мощен всъщност е доста
често срещано и много интуитивен,

176
00:07:00,520 --> 00:07:03,000
подобно може би се разделят и
владей е в нула седмица.

177
00:07:03,000 --> 00:07:05,250
Аз бързо напред към Hackathon
а преди няколко години.

178
00:07:05,250 --> 00:07:08,040
Това беше Zamyla и няколко
други студенти поздравителни персонал

179
00:07:08,040 --> 00:07:09,030
тъй като влезе.

180
00:07:09,030 --> 00:07:12,680
И ние имахме един куп сгъване
маси там с табелки с имена.

181
00:07:12,680 --> 00:07:15,380
И бяхме организирани поименните маркери
с както и над там

182
00:07:15,380 --> 00:07:16,690
и Zs там.

183
00:07:16,690 --> 00:07:20,350
И така, един от TFS много хитро
написах това и инструкциите

184
00:07:20,350 --> 00:07:21,030
за деня.

185
00:07:21,030 --> 00:07:24,480
И в 12-та седмица на семестъра това
всички направени перфектни смисъл и всеки

186
00:07:24,480 --> 00:07:25,310
знаех какво да правя.

187
00:07:25,310 --> 00:07:27,900
Но винаги, когато съм
наредена на опашка в един и същи начин,

188
00:07:27,900 --> 00:07:30,272
вие сте за прилагане на
същото понятие на хашиш.

189
00:07:30,272 --> 00:07:31,730
Така че нека да го прави малко по-официално.

190
00:07:31,730 --> 00:07:32,890
Тук е масив.

191
00:07:32,890 --> 00:07:36,820
Той е съставен да бъде малко
широк само да изобрази визуално,

192
00:07:36,820 --> 00:07:38,920
че ние може да сложи струни
в нещо като това.

193
00:07:38,920 --> 00:07:41,970
И този масив е
ясно на площ от 26 общо.

194
00:07:41,970 --> 00:07:43,935
И нещо, което се нарича
маса произволно.

195
00:07:43,935 --> 00:07:48,930
Но това е само интерпретация на един художник
на това, което може да бъде хеш таблица.

196
00:07:48,930 --> 00:07:52,799
>> Така хеш таблица сега ще
да бъде по-висока структура на данните ниво.

197
00:07:52,799 --> 00:07:54,840
В края на деня
ние сме на път да се види, че сте

198
00:07:54,840 --> 00:07:58,700
могат да се реализират на хеш таблица, която
е много като чек-ин линия

199
00:07:58,700 --> 00:08:02,059
в Hackathon много прилича това
маса се използва за сортиране изпита книги.

200
00:08:02,059 --> 00:08:03,850
Но хеш таблица е
вид на това високо ниво

201
00:08:03,850 --> 00:08:08,250
концепция, която може да се използва масив
под капака, за да го приложи,

202
00:08:08,250 --> 00:08:11,890
или може да се използва списък с дължина, или дори
може би някои други структури от данни.

203
00:08:11,890 --> 00:08:15,590
И сега това е theme-- вземането
някои от тези основни съставки

204
00:08:15,590 --> 00:08:18,310
като масив и тази сграда
блокират сега на списък с дължина

205
00:08:18,310 --> 00:08:21,740
и виждам какво друго можем да изградим
на върха на тези, като съставки

206
00:08:21,740 --> 00:08:26,550
в една рецепта, като все повече и повече
интересни и полезни крайните резултати.

207
00:08:26,550 --> 00:08:28,680
>> Така че с хеш таблица
бихме могли да го приложат

208
00:08:28,680 --> 00:08:32,540
в памет картинки като тази, но
как може тя действително да се кодират до?

209
00:08:32,540 --> 00:08:33,789
Е, може би най-просто е това.

210
00:08:33,789 --> 00:08:38,270
Ако капацитет във всички капачки, е просто
някои constant-- например 26,

211
00:08:38,270 --> 00:08:42,030
в продължение на 26 букви от alphabet--
Мога да се обадя ми променлива маса,

212
00:08:42,030 --> 00:08:45,630
и мога да твърдя, че аз отивам да
сложи Чар звезди там, или низ.

213
00:08:45,630 --> 00:08:49,880
Така че това е толкова просто, колкото това, ако
искат да приложат на хеш таблица.

214
00:08:49,880 --> 00:08:51,490
И все пак, това е наистина само един масив.

215
00:08:51,490 --> 00:08:53,198
Но отново, хеш
маса сега е това, което ние ще

216
00:08:53,198 --> 00:08:57,470
наричаме абстрактен тип данни, който е просто
сортиране на идеен наслояване на върха

217
00:08:57,470 --> 00:09:00,780
на нещо по-банално
Сега искал масив.

218
00:09:00,780 --> 00:09:02,960
>> Сега, как да отидем
за решаване на проблеми?

219
00:09:02,960 --> 00:09:06,980
Е, по-рано имах лукса
да имат достатъчно пространство за таблици тук

220
00:09:06,980 --> 00:09:09,460
така че може да постави
викторини навсякъде исках.

221
00:09:09,460 --> 00:09:10,620
Така че, както може да отидете тук.

222
00:09:10,620 --> 00:09:12,100
Zs могат да отидат тук.

223
00:09:12,100 --> 00:09:13,230
Ms може да отидете тук.

224
00:09:13,230 --> 00:09:14,740
И тогава имах някои допълнително пространство.

225
00:09:14,740 --> 00:09:18,740
Но това е малко на измама полето
сега, защото тази таблица, ако наистина

226
00:09:18,740 --> 00:09:22,720
мислеше за него като за масив, е просто
ще бъде от определен размер.

227
00:09:22,720 --> 00:09:25,380
>> Така че, технически, ако аз извадя
до викторина друг студент

228
00:09:25,380 --> 00:09:28,490
и виж, о, този човек
име започва с А също

229
00:09:28,490 --> 00:09:30,980
Някак искам да го сложа там.

230
00:09:30,980 --> 00:09:34,740
Но веднага след като съм го сложил там, ако
тази таблица наистина представлява масив,

231
00:09:34,740 --> 00:09:37,840
Отивам да се първостепенни или докара пред
който викторина този студент е.

232
00:09:37,840 --> 00:09:38,340
Така ли е?

233
00:09:38,340 --> 00:09:41,972
Ако това е масив, само едно нещо, което може да
отидете във всяка една от тези клетки или елементи.

234
00:09:41,972 --> 00:09:43,680
И така, аз вид трябва
да избирате.

235
00:09:43,680 --> 00:09:45,735
>> Сега по-рано бях вид
измамен и е направил това или I

236
00:09:45,735 --> 00:09:47,526
просто вид на чипове
ги един над друг.

237
00:09:47,526 --> 00:09:49,170
Но това няма да летят в код.

238
00:09:49,170 --> 00:09:52,260
Е, къде мога да тури
втори студент, чието име

239
00:09:52,260 --> 00:09:54,964
е А ако всичко, което трябваше е това
свободна маса пространство?

240
00:09:54,964 --> 00:09:57,880
И аз съм използвал три слота и го
изглежда има само няколко други.

241
00:09:57,880 --> 00:09:58,959
Какво можете да направите?

242
00:09:58,959 --> 00:09:59,834
АУДИТОРИЯ: [недоловим]

243
00:09:59,834 --> 00:10:00,565

244
00:10:00,565 --> 00:10:01,315
DAVID Malan: Да.

245
00:10:01,315 --> 00:10:02,370
Може би нека просто да го прости.

246
00:10:02,370 --> 00:10:02,660
Така ли е?

247
00:10:02,660 --> 00:10:04,243
Той не се вписва мястото, където искам да го пуснат.

248
00:10:04,243 --> 00:10:07,450
Така че аз отивам да го слагам
технически, където B ще отида.

249
00:10:07,450 --> 00:10:09,932
Сега, разбира се, аз съм се започне
да си рисува в ъгъла.

250
00:10:09,932 --> 00:10:11,890
Ако стигнем до студент
чието име всъщност е B,

251
00:10:11,890 --> 00:10:14,840
Сега B ще се премести малко
напред, тъй като може да се случи, да,

252
00:10:14,840 --> 00:10:17,530
ако това е Б, сега той трябва да премине тук.

253
00:10:17,530 --> 00:10:20,180
>> И така, това много бързо
може да стане проблематично,

254
00:10:20,180 --> 00:10:23,850
но това е техника, която всъщност
се нарича линеен сондиране,

255
00:10:23,850 --> 00:10:26,650
при което просто помисли си
масив да бъде по линията.

256
00:10:26,650 --> 00:10:29,680
А вие просто вид на сонда или
инспектира всеки наличен елемент

257
00:10:29,680 --> 00:10:31,360
търси достъпно място.

258
00:10:31,360 --> 00:10:34,010
И веднага след като установите,
един, можете да го пуснете там.

259
00:10:34,010 --> 00:10:38,390
>> Сега цената се плаща в момента
за това решение е, какво?

260
00:10:38,390 --> 00:10:41,300
Ние имаме фиксиран размер масив,
и когато поставите имена

261
00:10:41,300 --> 00:10:44,059
в него, поне в началото, какво е
времето за работа на вмъкване

262
00:10:44,059 --> 00:10:46,350
за въвеждане на студентите
викторини в правилните кофи?

263
00:10:46,350 --> 00:10:48,710

264
00:10:48,710 --> 00:10:50,002
Big O на какво?

265
00:10:50,002 --> 00:10:51,147
>> АУДИТОРИЯ: п.

266
00:10:51,147 --> 00:10:52,480
DAVID Malan: Чух голям О п.

267
00:10:52,480 --> 00:10:53,530

268
00:10:53,530 --> 00:10:54,300
Не е вярно.

269
00:10:54,300 --> 00:10:56,490
Но ние ще дразни освен
Затова в един момент.

270
00:10:56,490 --> 00:10:57,702
Какво друго би могло да бъде?

271
00:10:57,702 --> 00:10:58,755
>> АУДИТОРИЯ: [недоловим]

272
00:10:58,755 --> 00:11:00,380
DAVID Malan: И нека го направим визуално.

273
00:11:00,380 --> 00:11:04,720
Така че предполагам това е буквата S.

274
00:11:04,720 --> 00:11:05,604
>> АУДИТОРИЯ: Това е един.

275
00:11:05,604 --> 00:11:06,520
DAVID Malan: Това е един.

276
00:11:06,520 --> 00:11:06,710
Така ли е?

277
00:11:06,710 --> 00:11:08,950
Това е масив, който
означава, че има произволен достъп.

278
00:11:08,950 --> 00:11:11,790
И ако ние мислим за това
като нула и това като на 25 г.

279
00:11:11,790 --> 00:11:13,800
и ние осъзнаваме, че,
О, тук е моят принос S,

280
00:11:13,800 --> 00:11:16,350
Със сигурност мога да конвертирате
S, един ASCII характер,

281
00:11:16,350 --> 00:11:18,540
за съответния брой
между нула и 25

282
00:11:18,540 --> 00:11:20,910
и след това незабавно
го постави там, където принадлежи.

283
00:11:20,910 --> 00:11:26,120
>> Но, разбира се, веднага след като се стигна до
втори човек, който е име е А или B или C

284
00:11:26,120 --> 00:11:29,300
в крайна сметка, ако съм използвал
линейни сондиране като моето решение,

285
00:11:29,300 --> 00:11:31,360
времето за работа на
вмъкване в най-лошия случай

286
00:11:31,360 --> 00:11:33,120
всъщност ще бъде поверено в какво?

287
00:11:33,120 --> 00:11:34,270

288
00:11:34,270 --> 00:11:36,045
И аз съм го чуете тук
правилно в началото на деня.

289
00:11:36,045 --> 00:11:36,920
АУДИТОРИЯ: [недоловим]

290
00:11:36,920 --> 00:11:41,620
DAVID Malan: Така че това е п наистина веднъж
имате достатъчно голям набор от данни.

291
00:11:41,620 --> 00:11:44,410
Така, от една страна, ако
Вашата масив е достатъчно голям

292
00:11:44,410 --> 00:11:48,287
и данните ви е рядка достатъчно, можете
получите тази красива константно време.

293
00:11:48,287 --> 00:11:50,620
Но веднага след като започнете
все повече и повече елементи,

294
00:11:50,620 --> 00:11:53,200
и само статистически получавате
повече хора с буквата

295
00:11:53,200 --> 00:11:56,030
А, както е тяхното име или на писмото
Б, тя може потенциално

296
00:11:56,030 --> 00:11:57,900
прехвърлят в нещо по-линейна.

297
00:11:57,900 --> 00:11:59,640
Така че не е съвсем добра.

298
00:11:59,640 --> 00:12:00,690
Така че бихме могли да направим по-добре?

299
00:12:00,690 --> 00:12:03,210
>> Е, каква е нашата
решение преди, когато ние

300
00:12:03,210 --> 00:12:06,820
искам да имам повече динамика от
нещо като масив позволено?

301
00:12:06,820 --> 00:12:08,085

302
00:12:08,085 --> 00:12:08,960
АУДИТОРИЯ: [недоловим]

303
00:12:08,960 --> 00:12:10,030
DAVID Malan: Какво ще се въведе?

304
00:12:10,030 --> 00:12:10,530
Да.

305
00:12:10,530 --> 00:12:11,430
Така свързан списък.

306
00:12:11,430 --> 00:12:14,430
Е, нека да видим какво са свързани с
списък може да направи за нас, вместо да.

307
00:12:14,430 --> 00:12:17,630
Е, нека да предложи, че ние
изготвяне на снимката, както следва.

308
00:12:17,630 --> 00:12:19,620
Сега това е различно
картина от пример

309
00:12:19,620 --> 00:12:24,750
от различен текст, всъщност, че
всъщност, като се използва набор от размер 31.

310
00:12:24,750 --> 00:12:28,220
И този автор просто
реши да хеш струни

311
00:12:28,220 --> 00:12:32,430
не се основава на имена на лицето,
но въз основа на техните рождени дати.

312
00:12:32,430 --> 00:12:35,680
Независимо от месец, те измислили
ако сте родени на първия ден от месец

313
00:12:35,680 --> 00:12:39,580
или 31 на месец, авторът
ще сегментиране въз основа на тази стойност,

314
00:12:39,580 --> 00:12:44,154
така че да се разпространи имената на малко
повече от 26 точки могат да позволят.

315
00:12:44,154 --> 00:12:47,320
И може би това е малко по-равномерно
да обстрелват с буквени писма,

316
00:12:47,320 --> 00:12:50,236
защото, разбира се, там е най-вероятно
повече хора в света с имена

317
00:12:50,236 --> 00:12:54,020
които започват с над сигурност
някои други букви от азбуката.

318
00:12:54,020 --> 00:12:56,380
Така че може би това е малко
по-равномерно, ако приемем,

319
00:12:56,380 --> 00:12:58,640
равномерно разпределение
на бебета в целия месец.

320
00:12:58,640 --> 00:12:59,990
>> Но, разбира се, това все още е несъвършена.

321
00:12:59,990 --> 00:13:00,370
Така ли е?

322
00:13:00,370 --> 00:13:01,370
Ние сме като сблъсъци.

323
00:13:01,370 --> 00:13:04,680
Множество хора в тази
структура на данните са все още

324
00:13:04,680 --> 00:13:08,432
със същата рождена дата поне
ти си независимо от месец.

325
00:13:08,432 --> 00:13:09,640
Но това, което е направил автора?

326
00:13:09,640 --> 00:13:13,427
Е, изглежда, че имаме масив
на лявата ръка, изготвен вертикално,

327
00:13:13,427 --> 00:13:15,010
но това е само интерпретация на един художник.

328
00:13:15,010 --> 00:13:18,009
Няма значение какво посока
изготвя масив, тя все още е масив.

329
00:13:18,009 --> 00:13:20,225
Какво е това масив от очевидно?

330
00:13:20,225 --> 00:13:21,500
>> АУДИТОРИЯ: свързан списък.

331
00:13:21,500 --> 00:13:21,650
>> DAVID Malan: Да.

332
00:13:21,650 --> 00:13:23,490
Тя изглежда като това е
масив на свързан списък.

333
00:13:23,490 --> 00:13:26,490
Така че отново, до този момент на сортиране
за използване на тези структури от данни сега

334
00:13:26,490 --> 00:13:28,550
като съставки за по-
интересни решения,

335
00:13:28,550 --> 00:13:30,862
вие може напълно да вземе
фундаментални, като масив,

336
00:13:30,862 --> 00:13:33,320
и след това да вземе нещо повече
интересно като свързан списък

337
00:13:33,320 --> 00:13:36,660
и дори да ги комбинирате в още
по-интересна структура на данните.

338
00:13:36,660 --> 00:13:39,630
И наистина, това също би
се нарича хеш таблица,

339
00:13:39,630 --> 00:13:42,610
което масива
наистина хеш таблицата,

340
00:13:42,610 --> 00:13:45,600
но това хеш таблица има
вериги, така да се каже,

341
00:13:45,600 --> 00:13:50,220
че може да расте или намалява на базата на на
брой елементи, който искате да вмъкнете.

342
00:13:50,220 --> 00:13:52,990
>> Сега, съответно, какво е
времето за работа сега?

343
00:13:52,990 --> 00:13:58,030
Ако искате да поставите някого
чийто рожден ден е 31 октомври

344
00:13:58,030 --> 00:13:59,040
къде е той или тя отиде?

345
00:13:59,040 --> 00:14:00,530

346
00:14:00,530 --> 00:14:01,030
Добре.

347
00:14:01,030 --> 00:14:02,819
На самото дъно, където се казва 31.

348
00:14:02,819 --> 00:14:03,610
И това е перфектно.

349
00:14:03,610 --> 00:14:05,060
Това е константно време.

350
00:14:05,060 --> 00:14:08,760
Но какво, ако ние се намери някой друг
чийто рожден ден е, нека да видим,

351
00:14:08,760 --> 00:14:10,950
Октомври, ноември 31 декември?

352
00:14:10,950 --> 00:14:12,790
Къде е той или тя ще отиде?

353
00:14:12,790 --> 00:14:13,290
Същото нещо.

354
00:14:13,290 --> 00:14:13,970
Две стъпка все пак.

355
00:14:13,970 --> 00:14:15,303
Това е постоянен, макар и не е тя?

356
00:14:15,303 --> 00:14:16,360

357
00:14:16,360 --> 00:14:16,860
Добре.

358
00:14:16,860 --> 00:14:17,840
В момента тя е.

359
00:14:17,840 --> 00:14:20,570
Но в общия случай,
колкото повече хора, които добавяме,

360
00:14:20,570 --> 00:14:23,790
вероятностно, отиваме
за да получите повече и повече сблъсъци.

361
00:14:23,790 --> 00:14:26,820
>> Сега това е малко по-
по-добре, защото е технически

362
00:14:26,820 --> 00:14:34,580
сега ми вериги могат да бъдат в
най-лошия случай колко дълго?

363
00:14:34,580 --> 00:14:38,890
Ако въведете н хора в това по-
сложна структура от данни, п хора,

364
00:14:38,890 --> 00:14:41,080
в най-лошия случай това ще бъде п.

365
00:14:41,080 --> 00:14:41,815
Защо?

366
00:14:41,815 --> 00:14:43,332
>> АУДИТОРИЯ: Защото, ако всеки
има същия рожден ден,

367
00:14:43,332 --> 00:14:44,545
те ще бъдат един ред.

368
00:14:44,545 --> 00:14:45,420
DAVID Malan: Perfect.

369
00:14:45,420 --> 00:14:47,480
Тя може да е малко измислен,
но наистина в най-лошия случай,

370
00:14:47,480 --> 00:14:50,117
ако всеки има същия рожден ден,
предвид входящите данни, които имате,

371
00:14:50,117 --> 00:14:51,950
ти започваш да имат
масово дълга верига.

372
00:14:51,950 --> 00:14:54,241
И така, бихте могли да го наричаме
хеш таблицата, но наистина това е

373
00:14:54,241 --> 00:14:56,810
просто масивна свързан списък с
един куп губи пространство.

374
00:14:56,810 --> 00:15:00,460
Но като цяло, ако приемем, че
поне рождени дни са uniform--

375
00:15:00,460 --> 00:15:01,750
и то вероятно не е така.

376
00:15:01,750 --> 00:15:02,587
Аз си го измислям.

377
00:15:02,587 --> 00:15:04,420
Но ако приемем, за
заради дискусия

378
00:15:04,420 --> 00:15:07,717
че те са, след това на теория, ако
това е вертикално представяне

379
00:15:07,717 --> 00:15:11,050
на масива, и след това се надяваме, че сте
ще получите вериги, които са, вие знаете,

380
00:15:11,050 --> 00:15:15,880
приблизително същата дължина, където всеки от
това представлява ден на месеца.

381
00:15:15,880 --> 00:15:19,930
>> Сега, ако има 31 дни в месеца,
това означава, че моята работа време наистина

382
00:15:19,930 --> 00:15:25,230
е голям О п над 31, които
чувства по-добре, отколкото линейна.

383
00:15:25,230 --> 00:15:27,950
Но това, което е един от нашите
ангажименти за няколко седмици

384
00:15:27,950 --> 00:15:31,145
Преди, когато става дума за изразяване
времето за работа на алгоритъм?

385
00:15:31,145 --> 00:15:33,450

386
00:15:33,450 --> 00:15:35,190
Само погледнете само в срока висок ред.

387
00:15:35,190 --> 00:15:35,690
Така ли е?

388
00:15:35,690 --> 00:15:37,400
31 определено е полезно.

389
00:15:37,400 --> 00:15:39,610
Но това все още е голям O п.

390
00:15:39,610 --> 00:15:41,730
Но една от темите
на проблема определя пет

391
00:15:41,730 --> 00:15:43,950
ще бъде да се
признаем, че абсолютно,

392
00:15:43,950 --> 00:15:47,320
асимптотично, теоретично
тази структура данни

393
00:15:47,320 --> 00:15:50,470
не е по-добре, отколкото просто
една масивна свързан списък.

394
00:15:50,470 --> 00:15:53,550
И наистина, в най-лошия случай, това
хеш таблица може да бъде поверено в това.

395
00:15:53,550 --> 00:15:57,620
>> Но в реалния свят, с нас, хората
че собствените Mac-ове или компютри или каквото и

396
00:15:57,620 --> 00:16:01,240
и се изпълняват в реалния свят
софтуер за реалния свят на данни,

397
00:16:01,240 --> 00:16:03,260
които алгоритъм смяташ да предпочитате?

398
00:16:03,260 --> 00:16:09,180
Онзи, който взема крайни мерки или
която се приема н разделена на 31 стъпки

399
00:16:09,180 --> 00:16:12,900
да намери някаква част от данните, или
да търсите някаква информация?

400
00:16:12,900 --> 00:16:16,580
Искам да кажа, абсолютно 31 марките
разлика в реалния свят.

401
00:16:16,580 --> 00:16:18,540
Той е 31 пъти по-бързо.

402
00:16:18,540 --> 00:16:20,880
И ние, хората, със сигурност
Ще оценявам това.

403
00:16:20,880 --> 00:16:23,004
>> Така се реализира дихотомията
има между действително

404
00:16:23,004 --> 00:16:25,920
Говорим за неща теоретично
и асимптотично които определено

405
00:16:25,920 --> 00:16:28,760
има стойност, тъй като сме виждали,
но в реалния свят,

406
00:16:28,760 --> 00:16:32,930
ако те е грижа за просто вземане на
човека щастлив за общи входове,

407
00:16:32,930 --> 00:16:36,010
може много добре да приемам
факта, че, да, това е линейна,

408
00:16:36,010 --> 00:16:38,360
но това е 31 пъти по-бързо
от линеен може да бъде.

409
00:16:38,360 --> 00:16:41,610
И още по-добре, ние не само трябва да
направя нещо произволно като дата на раждане,

410
00:16:41,610 --> 00:16:44,030
бихме могли да прекарат малко
повече време и интелигентност

411
00:16:44,030 --> 00:16:47,140
и да мисля за това, което можем да направим,
име и може би едно лице

412
00:16:47,140 --> 00:16:50,130
тяхната дата на раждане, за да се съчетаят тези
съставки, за да разбера нещо

413
00:16:50,130 --> 00:16:52,720
че наистина е по-
уеднаквено и по-малко съдран,

414
00:16:52,720 --> 00:16:56,250
така да се каже, отколкото тази снимка
В момента показва, че може да бъде.

415
00:16:56,250 --> 00:16:57,750
Как бихме могли да приложат това код?

416
00:16:57,750 --> 00:17:00,280
Е, нека да предложи, че ние
само назаем някои синтаксис ние сме

417
00:17:00,280 --> 00:17:01,799
използва няколко пъти досега.

418
00:17:01,799 --> 00:17:03,590
И аз отивам да се определи
една възлова точка, която отново

419
00:17:03,590 --> 00:17:06,812
е общ термин за само някои
контейнер за някаква структура данни.

420
00:17:06,812 --> 00:17:09,020
Отивам да предложи
низ се случва там.

421
00:17:09,020 --> 00:17:11,369
Но ние отиваме да започнете да приемате
тези обучение колелата сега.

422
00:17:11,369 --> 00:17:13,230
>> Не по-CS50 библиотека
Наистина, освен ако не искате

423
00:17:13,230 --> 00:17:15,230
да го използва за своя окончателен
проект, което е добре,

424
00:17:15,230 --> 00:17:18,569
но сега отиваме да се отдръпни
завеса и да кажа, че това е просто знак звезда.

425
00:17:18,569 --> 00:17:22,069
Така че думата там ще бъде
името на лицето под въпрос.

426
00:17:22,069 --> 00:17:25,079
И сега имам връзка
тук към следващия възел

427
00:17:25,079 --> 00:17:28,170
така че те да представляват
всяка от възли

428
00:17:28,170 --> 00:17:30,950
във веригата, потенциално,
на свързан списък.

429
00:17:30,950 --> 00:17:34,090
>> И сега как мога да декларирам
Самият хеш таблицата?

430
00:17:34,090 --> 00:17:36,660
Как се декларира цялата тази структура?

431
00:17:36,660 --> 00:17:40,960
Е, наистина, много като аз използвах указател
само първият елемент от списък

432
00:17:40,960 --> 00:17:44,510
преди, по същия начин мога само да кажа,
Трябва ми само един куп от указатели

433
00:17:44,510 --> 00:17:46,270
да приложи цялата тази хеш таблица.

434
00:17:46,270 --> 00:17:49,484
Отивам да имате масив
нарича таблица за хеш таблица.

435
00:17:49,484 --> 00:17:50,900
Тя ще бъде на капацитета размер.

436
00:17:50,900 --> 00:17:52,525
Ето как много елементи могат да се поберат в него.

437
00:17:52,525 --> 00:17:56,180
И всеки от тези елементи в тази
масив ще бъде звезда възел.

438
00:17:56,180 --> 00:17:56,810
Защо?

439
00:17:56,810 --> 00:18:00,160
Е, на тази картина, това, което съм
прилагане на хеш таблицата като

440
00:18:00,160 --> 00:18:04,330
ефективно в началото е просто
този масив, който сме изготвен вертикално,

441
00:18:04,330 --> 00:18:06,820
всеки от чиито квадрати
представлява показалка.

442
00:18:06,820 --> 00:18:09,170
Ето тези, които имат черти
чрез тях са само нищожна.

443
00:18:09,170 --> 00:18:11,410
И тези, които имат
стрелки ще правото

444
00:18:11,410 --> 00:18:16,140
са действителни указатели към действителните възли,
Ergo началото на свързан списък.

445
00:18:16,140 --> 00:18:19,050
>> Така че тук, след това, е как можем да
прилагане на хеш таблица, която

446
00:18:19,050 --> 00:18:21,580
изпълнява отделна верижното.

447
00:18:21,580 --> 00:18:22,840
Сега можем да направим по-добре?

448
00:18:22,840 --> 00:18:25,632
Добре обещах миналия път, че
можем да постигнем постоянен време.

449
00:18:25,632 --> 00:18:27,381
И някак си дал
константно време тук,

450
00:18:27,381 --> 00:18:29,850
но тогава не каза наистина
константно време, тъй като тя все още е

451
00:18:29,850 --> 00:18:31,890
зависи от общата
брой елементи

452
00:18:31,890 --> 00:18:34,500
сте въвеждане в
структурата на данните.

453
00:18:34,500 --> 00:18:35,980
Но предполагам, че е направил това.

454
00:18:35,980 --> 00:18:39,550
Позволете ми да се върна на екрана тук.

455
00:18:39,550 --> 00:18:44,520
Позволете ми да проектира този тук, ясно
на екрана, и предполагам, че е направил това.

456
00:18:44,520 --> 00:18:49,300
Да предположим, че аз исках да въведете името
Daven в в моята структура данни.

457
00:18:49,300 --> 00:18:52,100
>> Така че аз искам да вмъкнете низ
Daven в структурата на данните.

458
00:18:52,100 --> 00:18:54,370
Какво става, ако не използвате
хеш таблица, но аз използвам

459
00:18:54,370 --> 00:18:56,980
нещо, което е по-дървовидна
като родословно дърво, където

460
00:18:56,980 --> 00:18:59,670
имате някакъв корен в
отгоре и след това възли и листа

461
00:18:59,670 --> 00:19:01,440
които отиват надолу и навън.

462
00:19:01,440 --> 00:19:04,450
Да предположим тогава, че аз
искате да вмъкнете Daven на

463
00:19:04,450 --> 00:19:06,430
в това, което е в момента празен списък.

464
00:19:06,430 --> 00:19:09,780
Отивам да направите следното: Аз съм
ще създаде възел в това семейство

465
00:19:09,780 --> 00:19:15,170
дървовидна структура от данни, която изглежда
малко по този начин, всеки от които

466
00:19:15,170 --> 00:19:19,640
правоъгълници е, да речем,
За сега 26 елементи в него.

467
00:19:19,640 --> 00:19:21,650
И всяка една от клетките
в този масив се случва

468
00:19:21,650 --> 00:19:23,470
да представлява буквата на азбуката.

469
00:19:23,470 --> 00:19:28,190
>> По-конкретно, аз отивам за лечение
Това е, след това, след това С, след което D,

470
00:19:28,190 --> 00:19:29,310
този тук.

471
00:19:29,310 --> 00:19:32,940
Така че това ще е ефективно
представлява буквата D.

472
00:19:32,940 --> 00:19:36,040
Но за да поставите всички Daven на
име, което трябва да направя малко повече.

473
00:19:36,040 --> 00:19:37,840
Така че аз съм първият ще хашиш, така да се каже.

474
00:19:37,840 --> 00:19:41,049
Отивам да гледам на първата буква
в Daven, която очевидно е D,

475
00:19:41,049 --> 00:19:42,840
и аз отивам да се разпределят
възел, който изглежда

476
00:19:42,840 --> 00:19:45,570
като this-- голям правоъгълник голям
достатъчно, за да се побере цялата азбука.

477
00:19:45,570 --> 00:19:47,140
>> Сега D е направено.

478
00:19:47,140 --> 00:19:49,720
Сега A. D-A-V-E-N е целта.

479
00:19:49,720 --> 00:19:51,220
Така че сега това, което аз ще направя, е това.

480
00:19:51,220 --> 00:19:54,027
Веднага след като започнах известие D
че няма показалка там.

481
00:19:54,027 --> 00:19:56,860
Това е стойности за боклук в момента,
или за да го инициализира с нула.

482
00:19:56,860 --> 00:19:59,630
Но позволете ми да продължа с
тази идея за изграждане на едно дърво.

483
00:19:59,630 --> 00:20:04,260
Позволете ми да отпусне още един от тях
възли, които има 26 елементи в него.

484
00:20:04,260 --> 00:20:05,150
>> И знаеш ли какво?

485
00:20:05,150 --> 00:20:09,130
Ако това е само един възел в паметта, която
Аз създадох с изчистване, използвайки структура

486
00:20:09,130 --> 00:20:11,240
тъй като ние скоро ще видите,
Отивам да направя this--

487
00:20:11,240 --> 00:20:14,450
Отивам да се направи една стрела от
нещото, което представена D надолу

488
00:20:14,450 --> 00:20:15,860
към този нов възел.

489
00:20:15,860 --> 00:20:19,240
И сега, на първо място в следващия
писмо, в името Daven е,

490
00:20:19,240 --> 00:20:24,150
V-- D-A-V-- Отивам да вървим напред
и да изготви друг възел по този начин,

491
00:20:24,150 --> 00:20:30,150
, при която елементите V тук, които
ще изготви за instance-- Опа.

492
00:20:30,150 --> 00:20:31,020
Ние няма да се направи там.

493
00:20:31,020 --> 00:20:31,936
Това ще отидете тук.

494
00:20:31,936 --> 00:20:32,890

495
00:20:32,890 --> 00:20:35,712
>> След това ние ще
че това е V.

496
00:20:35,712 --> 00:20:44,920
И тогава тук отиваме към индекс
надолу от V в това, което ние ще вземем E.

497
00:20:44,920 --> 00:20:50,100
И след това от тук отиваме да
отида имате един от тези възли тук.

498
00:20:50,100 --> 00:20:52,930
И сега имам един въпрос да се отговори.

499
00:20:52,930 --> 00:20:57,840
Трябва да се посочи, че по някакъв начин
ние сме в края на низа Daven.

500
00:20:57,840 --> 00:20:59,490
Така че аз може просто да го оставите за нищожна.

501
00:20:59,490 --> 00:21:02,670
>> Но какво, ако имаме Daven на
пълно име също, което

502
00:21:02,670 --> 00:21:04,280
е, както казахме, Дейвънпорт?

503
00:21:04,280 --> 00:21:06,970
И какво, ако е Daven
всъщност е подниз,

504
00:21:06,970 --> 00:21:08,960
префикс на много по-дълъг низ?

505
00:21:08,960 --> 00:21:11,450
Ние не можем просто постоянно
казват, нищо не се случва

506
00:21:11,450 --> 00:21:14,410
да отида там, защото можехме
никога не поставяйте дума като Davenport

507
00:21:14,410 --> 00:21:15,840
в тази структура на данните

508
00:21:15,840 --> 00:21:19,560
>> И така, какво можем да направим вместо е
лечение на всеки един от тези елементи

509
00:21:19,560 --> 00:21:22,170
като може би с два
елементи вътре в тях.

510
00:21:22,170 --> 00:21:24,810
Един от тях е указател, наистина,
както съм правил.

511
00:21:24,810 --> 00:21:27,100
Така че всяка една от тези кутии
Не е само една клетка.

512
00:21:27,100 --> 00:21:29,855
Но какво, ако на върха
one-- долния нечии

513
00:21:29,855 --> 00:21:32,230
ще бъде нулев, тъй като
не съществува Davenport, просто все още.

514
00:21:32,230 --> 00:21:34,197
Какво става, ако най-отгоре
е някаква особена стойност?

515
00:21:34,197 --> 00:21:36,530
И това ще бъде малко
Трудно е да го направи този размер.

516
00:21:36,530 --> 00:21:38,130
Но предполагам, че това е просто една отметка.

517
00:21:38,130 --> 00:21:38,920
Проверка.

518
00:21:38,920 --> 00:21:44,230
D-A-V-E-N е низ
в тази структура данни.

519
00:21:44,230 --> 00:21:48,350
>> В същото време, ако имах повече пространство
тук, можех да направя P-O-R-T,

520
00:21:48,350 --> 00:21:52,650
и аз може да постави отметка в възел
който има буквата T в самия край.

521
00:21:52,650 --> 00:21:55,460
Така че това е масова
комплекс изглеждащ структура на данните.

522
00:21:55,460 --> 00:21:57,210
И моят почерк
със сигурност не помага.

523
00:21:57,210 --> 00:22:00,043
Но ако исках да вмъкнете нещо
друго, помислете за това, което ще направя.

524
00:22:00,043 --> 00:22:03,370
Ако искахме да постави Давид,
ние ще следваме същата логика, D-A-V,

525
00:22:03,370 --> 00:22:08,802
но сега искам да посоча в следващия
елемент не от E, но от I до D.

526
00:22:08,802 --> 00:22:10,760
Така че там ще бъде
повече възли в това дърво.

527
00:22:10,760 --> 00:22:12,325
Ние ще имаме разговор изчистване повече.

528
00:22:12,325 --> 00:22:14,700
Но аз не искам да се направи
пълна бъркотия на тази снимка.

529
00:22:14,700 --> 00:22:17,710
Така че нека вместо разгледаме един
, която е била предварително формулирани

530
00:22:17,710 --> 00:22:21,810
като тази с не DOT, точка,
точки, но съкратените масиви.

531
00:22:21,810 --> 00:22:23,950
Но всеки от възлите
в това дърво тук

532
00:22:23,950 --> 00:22:26,700
представлява същия thing--
масив Ray с размер 26.

533
00:22:26,700 --> 00:22:28,860
>> Или ако искаме да бъдем
наистина правилно сега, това, което

534
00:22:28,860 --> 00:22:30,790
ако някой име като
апостроф, нека

535
00:22:30,790 --> 00:22:35,560
Предполагам, че всеки възел всъщност има
като 27 индекси в него, а не само 26.

536
00:22:35,560 --> 00:22:42,020
Така че това сега ще бъде на данни
структура, наречена trie-- T-R-I-E.

537
00:22:42,020 --> 00:22:46,120
Синтактично дърво, което се предполага, че
исторически умен име за дърво

538
00:22:46,120 --> 00:22:49,040
че е оптимизиран за
извличане, което, разбира се,

539
00:22:49,040 --> 00:22:50,870
е изписано с I-E, така че е синтактично дърво.

540
00:22:50,870 --> 00:22:52,710
Но това е историята на Trie.

541
00:22:52,710 --> 00:22:55,860
>> Така синтактично дърво е това дърво, като данните
структура като родословно дърво

542
00:22:55,860 --> 00:22:57,510
които в крайна сметка се държи по този начин.

543
00:22:57,510 --> 00:23:00,890
И тук е просто още един пример за
цял куп имена на други хора.

544
00:23:00,890 --> 00:23:03,540
Но въпросът сега
на ръка е това, което трябва

545
00:23:03,540 --> 00:23:08,070
сме спечелили чрез въвеждане безспорно по-
сложна структура данни и един,

546
00:23:08,070 --> 00:23:09,870
честно казано, че използва много памет.

547
00:23:09,870 --> 00:23:11,703
>> Защото, въпреки че,
в момента, аз съм само

548
00:23:11,703 --> 00:23:15,050
използване D'и показалеца и
А и V и Es и Ns,

549
00:23:15,050 --> 00:23:16,700
Аз губя един чесало на много памет.

550
00:23:16,700 --> 00:23:18,030

551
00:23:18,030 --> 00:23:22,660
Но там, където прекарвам един ресурс,
Склонен съм да се получат обратно друга.

552
00:23:22,660 --> 00:23:26,020
Така че, ако аз съм харчат повече пространство,
това, което е най-вероятно с надеждата?

553
00:23:26,020 --> 00:23:27,407
Че аз съм харчат по-малко какво?

554
00:23:27,407 --> 00:23:28,240
АУДИТОРИЯ: По-малко време.

555
00:23:28,240 --> 00:23:28,990
DAVID Malan: Time.

556
00:23:28,990 --> 00:23:30,320
А защо може да бъде това?

557
00:23:30,320 --> 00:23:33,880
Е, какво е вмъкването
време, от гледна точка на големия O сега,

558
00:23:33,880 --> 00:23:37,660
на име като Daven
или Дейвънпорт или Давид?

559
00:23:37,660 --> 00:23:39,340
Е, Daven беше пет стъпки.

560
00:23:39,340 --> 00:23:42,350
Дейвънпорт ще бъде девет стъпки,
така че би било още няколко стъпки.

561
00:23:42,350 --> 00:23:44,250
Дейвид ще бъде пет стъпки, както добре.

562
00:23:44,250 --> 00:23:47,230
Така че тези, които са бетон
номера, но със сигурност има

563
00:23:47,230 --> 00:23:49,550
горна граница на
дължина на името на някого.

564
00:23:49,550 --> 00:23:52,240
И наистина, в проблема
групи от пет спецификация,

565
00:23:52,240 --> 00:23:54,050
отиваме да предложи
че това е нещо,

566
00:23:54,050 --> 00:23:55,470
това е 40-някои по-странни знаци.

567
00:23:55,470 --> 00:23:58,180
>> Реално, никой няма
безкрайно дълго име,

568
00:23:58,180 --> 00:24:01,542
което означава, че дължината на
Име или дължината на низ бихме могли

569
00:24:01,542 --> 00:24:03,750
има някои състоянието на
структура е може би това, което?

570
00:24:03,750 --> 00:24:05,550

571
00:24:05,550 --> 00:24:06,250
Това е постоянна.

572
00:24:06,250 --> 00:24:06,430
Така ли е?

573
00:24:06,430 --> 00:24:09,310
Тя може да бъде една голяма постоянна като
40-нещо, но е постоянна.

574
00:24:09,310 --> 00:24:13,752
И това не е зависимост от това колко
други имена са в тази структура на данните.

575
00:24:13,752 --> 00:24:15,460
С други думи, ако
Исках да вмъкнете сега

576
00:24:15,460 --> 00:24:20,540
Колтън или Gabriel или Rob или Zamyla или
Алисън или Белинда или всякакви други имена

577
00:24:20,540 --> 00:24:23,940
от персонала в тези данни
структура, е времето за изпълнение

578
00:24:23,940 --> 00:24:26,750
на вмъкване други имена
щеше да бъде изобщо повлияха

579
00:24:26,750 --> 00:24:30,220
от колко други елементи са
в структурата на данните вече?

580
00:24:30,220 --> 00:24:31,040
Това не е така.

581
00:24:31,040 --> 00:24:31,540
Така ли е?

582
00:24:31,540 --> 00:24:36,150
Защото ние сме ефективно използване на
тази многопластова хеш таблица.

583
00:24:36,150 --> 00:24:38,280
И времето за работа на
всяка от тези операции

584
00:24:38,280 --> 00:24:41,510
не зависи от броя на
елементи, които са в структурата на данните

585
00:24:41,510 --> 00:24:43,090
или че в крайна сметка ще
да бъде в структурата на данните,

586
00:24:43,090 --> 00:24:44,714
но дължината на какво конкретно?

587
00:24:44,714 --> 00:24:46,500

588
00:24:46,500 --> 00:24:49,200
>> Поредицата е
Добавя, което наистина прави

589
00:24:49,200 --> 00:24:52,580
това асимптотично постоянно
time-- голям O на една.

590
00:24:52,580 --> 00:24:54,720
И честно казано, само в
реалния свят, това

591
00:24:54,720 --> 00:24:58,380
означава вмъкване на име Daven на заема
като пет стъпки, или Davenport девет

592
00:24:58,380 --> 00:25:00,100
стъпки, или David пет стъпки.

593
00:25:00,100 --> 00:25:03,071
Това е дяволски много малки експлоатационни пъти.

594
00:25:03,071 --> 00:25:05,320
И наистина, това е много
нещо добро, особено когато

595
00:25:05,320 --> 00:25:08,126
не е зависима от общото
брой на елементите в там.

596
00:25:08,126 --> 00:25:10,500
И така, как бихме могли да приложат тази
вид структура на код?

597
00:25:10,500 --> 00:25:12,900
Това е малко по-
сложна, но все пак това е

598
00:25:12,900 --> 00:25:15,050
просто прилагане на
основните градивни блокове.

599
00:25:15,050 --> 00:25:17,830
Отивам да се предефинират
ни възел, както следва:

600
00:25:17,830 --> 00:25:21,100
булев нарича word-- и това
може да се нарече нещо.

601
00:25:21,100 --> 00:25:23,970
Но BOOL представлява
това, което привлече като отметка.

602
00:25:23,970 --> 00:25:24,490
Да.

603
00:25:24,490 --> 00:25:26,720
Това е края на низ
в тази структура данни.

604
00:25:26,720 --> 00:25:30,702
>> И, разбира се, звездата на възела
там се отнася за деца.

605
00:25:30,702 --> 00:25:32,410
И наистина, точно като
родословно дърво, можете

606
00:25:32,410 --> 00:25:34,370
ще разгледа възлите
които се виси

607
00:25:34,370 --> 00:25:36,920
на дъното на някои майка
елемент за деца.

608
00:25:36,920 --> 00:25:40,510
И така децата ще
е масив от 27, на 27-ми този

609
00:25:40,510 --> 00:25:41,680
просто е за апостроф.

610
00:25:41,680 --> 00:25:43,390
Отиваме да сортирате
на специален случай това.

611
00:25:43,390 --> 00:25:45,400
Така че може да има някои
имена с апострофи.

612
00:25:45,400 --> 00:25:47,399
Може би дори тире трябва
отида там, но ще

613
00:25:47,399 --> 00:25:50,330
виж в стр комплект 5 ние само грижи
за букви и апострофи.

614
00:25:50,330 --> 00:25:52,990
>> И тогава как ще представляват
самата структура на данни?

615
00:25:52,990 --> 00:25:56,454
Как сте представител на корена
на този Trie, така да се каже?

616
00:25:56,454 --> 00:25:59,620
Е, точно като с свързан списък,
трябва указател към първия елемент.

617
00:25:59,620 --> 00:26:04,270
С Trie трябва само един
указател към корена на тази синтактично дърво.

618
00:26:04,270 --> 00:26:07,290
И от там можете да хеш
пътя си надолу по-дълбоко и по-дълбоко

619
00:26:07,290 --> 00:26:10,460
на всеки друг възел в структурата.

620
00:26:10,460 --> 00:26:13,440
Така че просто с тази кутия
ние представляваме, че структура.

621
00:26:13,440 --> 00:26:15,877
>> Сега Meanwhile-- О, въпрос.

622
00:26:15,877 --> 00:26:17,220
>> АУДИТОРИЯ: Какво е булев дума?

623
00:26:17,220 --> 00:26:20,490
>> DAVID Malan: BOOL дума
просто това C въплъщение

624
00:26:20,490 --> 00:26:22,920
от това, което е описано по-
в тази кутия тук, когато

625
00:26:22,920 --> 00:26:26,000
Започнах разделяне всяка от
елементи в две парчета масива.

626
00:26:26,000 --> 00:26:27,600
Един от тях е указател към следващия възел.

627
00:26:27,600 --> 00:26:30,280
Другият трябва да бъде
нещо като отметка

628
00:26:30,280 --> 00:26:33,770
да се каже, да, има
Думата Daven че свършва тук,

629
00:26:33,770 --> 00:26:35,610
защото ние не искаме,
в момента, Дейв.

630
00:26:35,610 --> 00:26:39,320
>> Въпреки че Дейв ще бъде
легитимна дума, той не е в Trie

631
00:26:39,320 --> 00:26:39,830
още.

632
00:26:39,830 --> 00:26:40,950
И D не е дума.

633
00:26:40,950 --> 00:26:42,770
И D-A не е дума или име.

634
00:26:42,770 --> 00:26:45,020
Така отметката
показва само веднъж

635
00:26:45,020 --> 00:26:48,190
удари този възел е
предишния път на героите

636
00:26:48,190 --> 00:26:50,700
всъщност е низ, който сте вмъкнали.

637
00:26:50,700 --> 00:26:53,660
Така че това е всичко, на булев
там се прави за нас.

638
00:26:53,660 --> 00:26:55,500
>> Всякакви други въпроси, свързани с опита?

639
00:26:55,500 --> 00:26:56,215
Да.

640
00:26:56,215 --> 00:26:58,035
>> АУДИТОРИЯ: Какво е припокриването?

641
00:26:58,035 --> 00:26:59,945
Какво става, ако имате Dave и Daven?

642
00:26:59,945 --> 00:27:00,820
DAVID Malan: Perfect.

643
00:27:00,820 --> 00:27:02,580
Какво става, ако имате Dave и Daven?

644
00:27:02,580 --> 00:27:06,240
Така че, ако ние вмъкнете, да кажем, псевдоним,
за David-- Dave-- D-A-V-E?

645
00:27:06,240 --> 00:27:07,370

646
00:27:07,370 --> 00:27:08,700
Това всъщност е супер проста.

647
00:27:08,700 --> 00:27:10,325
Така че ние само ще отнеме четири стъпки.

648
00:27:10,325 --> 00:27:11,042

649
00:27:11,042 --> 00:27:15,847
D-A-V-E. И какво трябва да се
направи веднъж ударих, че четвъртият възел?

650
00:27:15,847 --> 00:27:16,680
Просто щеше да се провери.

651
00:27:16,680 --> 00:27:18,000
Ние вече сте добре да тръгвам.

652
00:27:18,000 --> 00:27:18,840
Готово.

653
00:27:18,840 --> 00:27:19,750
Четири стъпки.

654
00:27:19,750 --> 00:27:21,590
Constant време асимптотично.

655
00:27:21,590 --> 00:27:26,300
И сега ние сме посочили, че и двете Dave
и Daven са струни в структурата.

656
00:27:26,300 --> 00:27:27,710
Така че не е проблем.

657
00:27:27,710 --> 00:27:30,200
И забележете как присъствието
на Daven не го направи

658
00:27:30,200 --> 00:27:34,750
приемайте повече време или по-малко
време за Дейв и обратно.

659
00:27:34,750 --> 00:27:36,000
>> И така, какво друго можем да направим сега?

660
00:27:36,000 --> 00:27:40,680
Ние сме използвали тази метафора преди
на корита, представляваща нещо.

661
00:27:40,680 --> 00:27:43,380
Но се оказва, че
купчина тави е всъщност

662
00:27:43,380 --> 00:27:47,187
демонстративна на друга абстрактна данни
type-- по-висока структура на данните ниво

663
00:27:47,187 --> 00:27:49,770
че в края на деня е просто
като масив или свързан списък

664
00:27:49,770 --> 00:27:50,970
или нещо по-банално.

665
00:27:50,970 --> 00:27:53,270
Но това е по-интересно
концептуална идея.

666
00:27:53,270 --> 00:27:56,440
A стак, като тези
тави тук в Mather,

667
00:27:56,440 --> 00:27:58,750
обикновено се нарича
просто that-- комин.

668
00:27:58,750 --> 00:28:02,540
>> И в този тип структура на данните
имате две operations--

669
00:28:02,540 --> 00:28:05,880
имате една, наречена тласък за
добави нещо към стека,

670
00:28:05,880 --> 00:28:08,320
като да сложиш друга тава
обратно на върха на стека.

671
00:28:08,320 --> 00:28:11,350
И тогава се появи, което означава,
вземе най-горната тава излитане.

672
00:28:11,350 --> 00:28:16,210
Но това, което е ключово за комин е, че
тя има тази любопитна характеристика.

673
00:28:16,210 --> 00:28:19,560
Както персонал столова са
пренареждане на тавите за следващото хранене,

674
00:28:19,560 --> 00:28:21,380
какво ще бъде
вярно за това как студентите

675
00:28:21,380 --> 00:28:22,856
взаимодействат с тази структура данни?

676
00:28:22,856 --> 00:28:24,480
АУДИТОРИЯ: Те ще се появи еднократно.

677
00:28:24,480 --> 00:28:26,550
DAVID Malan: Те ще
поп еднократно, надявам се на върха.

678
00:28:26,550 --> 00:28:28,910
В противен случай това е просто вид на глупав
да отидем по целия път до дъното.

679
00:28:28,910 --> 00:28:29,070
Така ли е?

680
00:28:29,070 --> 00:28:31,620
Структурата на данните наистина не позволи
можете да вземете долната тава най-малко

681
00:28:31,620 --> 00:28:32,520
лесно.

682
00:28:32,520 --> 00:28:35,040
Така че този любопитен
имот на комин

683
00:28:35,040 --> 00:28:39,730
че последният елемент в е
ще бъде първият Един.

684
00:28:39,730 --> 00:28:43,400
И компютърни учени наричат
това LIFO-- продължи, първа изходяща.

685
00:28:43,400 --> 00:28:45,540
И това всъщност няма
интересни приложения.

686
00:28:45,540 --> 00:28:50,090
Това не е задължително, както е очевидно, тъй като някои
други, но може наистина да бъдат полезни,

687
00:28:50,090 --> 00:28:54,040
и действително може да се прилага
по няколко различни начина.

688
00:28:54,040 --> 00:28:58,550
>> Така един, и всъщност, нека
Не ме да се потопите в това.

689
00:28:58,550 --> 00:28:59,860
Нека да направим това вместо това.

690
00:28:59,860 --> 00:29:03,700
Нека разгледаме един, който е почти
същата идея, но тя е малко по-справедливо.

691
00:29:03,700 --> 00:29:04,200
Така ли е?

692
00:29:04,200 --> 00:29:07,560
Ако вие сте един от тези фен момчета или
момичета, които наистина се интересува от Apple продукти

693
00:29:07,560 --> 00:29:10,130
и се събудих в 3:00 AM
да се подредят в някакъв магазин

694
00:29:10,130 --> 00:29:14,150
за да получите най-новите iPhone, можете
може да са наредени на опашка по този начин.

695
00:29:14,150 --> 00:29:15,800
>> Сега на опашката е много съзнателно име.

696
00:29:15,800 --> 00:29:18,190
Това е линия, защото там е
някаква справедливост към него.

697
00:29:18,190 --> 00:29:18,690
Така ли е?

698
00:29:18,690 --> 00:29:21,690
Би вид смуче, ако сте
беше първа в Apple Store

699
00:29:21,690 --> 00:29:25,700
но на практика са най-долен
тава, защото служителите на Apple след това

700
00:29:25,700 --> 00:29:28,189
поп последният човек, който
всъщност имам в линия.

701
00:29:28,189 --> 00:29:31,230
Така стекове и опашки, въпреки че
функционално те са вид на same--

702
00:29:31,230 --> 00:29:33,105
това е само тази колекция
на ресурсите, което е

703
00:29:33,105 --> 00:29:36,210
ще расте и shrink-- има
тази справедливост аспект към него,

704
00:29:36,210 --> 00:29:39,634
най-малко в реалния свят,
където операциите тренирате

705
00:29:39,634 --> 00:29:40,800
са коренно различни.

706
00:29:40,800 --> 00:29:43,360
A stack-- опашка
rather-- се казва, че има

707
00:29:43,360 --> 00:29:45,320
две операции: N опашка и г опашката.

708
00:29:45,320 --> 00:29:46,341

709
00:29:46,341 --> 00:29:48,090
Или можете да ги наречем
произволен брой неща.

710
00:29:48,090 --> 00:29:50,770
Но вие просто искате да заснемете
идеята, че едно е добавянето

711
00:29:50,770 --> 00:29:53,230
и един в крайна сметка се извади.

712
00:29:53,230 --> 00:29:58,840
>> Сега под предния капак, както топчето
и опашката могат да бъдат приложени по какъв начин?

713
00:29:58,840 --> 00:30:01,390
Ние няма да отида в кода на
Дали защото на по-високо ниво

714
00:30:01,390 --> 00:30:03,387
Идеята е нещо по-очевидна.

715
00:30:03,387 --> 00:30:04,470
Искам да кажа, какво правят хората?

716
00:30:04,470 --> 00:30:07,030
Ако аз съм първият човек в Apple
Съхранявайте и това е входната врата,

717
00:30:07,030 --> 00:30:08,130
знаете ли, аз отивам да стоя тук.

718
00:30:08,130 --> 00:30:09,750
И на следващия човек
Ще стоя тук.

719
00:30:09,750 --> 00:30:11,500
И на следващия човек
Ще стоя тук.

720
00:30:11,500 --> 00:30:13,792
Така че това, което структурата на данните
се поддава на опашка?

721
00:30:13,792 --> 00:30:14,542
>> Аудитория: A опашка.

722
00:30:14,542 --> 00:30:15,667
DAVID Malan: Е, на опашката.

723
00:30:15,667 --> 00:30:16,390
Разбира се.

724
00:30:16,390 --> 00:30:16,920
Какво друго?

725
00:30:16,920 --> 00:30:17,600
>> Аудитория: A свързан списък.

726
00:30:17,600 --> 00:30:18,990
>> DAVID Malan: A свързан
Списъкът, който може да се приложи.

727
00:30:18,990 --> 00:30:22,500
И свързан списък е хубаво, защото след това
че може да расте произволно дълго в сравнение

728
00:30:22,500 --> 00:30:24,880
да има някакъв определен брой
на хората в магазина.

729
00:30:24,880 --> 00:30:27,030
Но може би на фиксиран номер
на места е законно.

730
00:30:27,030 --> 00:30:30,350
Защото, ако те имат само около 20
Iphones на първия ден, може би

731
00:30:30,350 --> 00:30:33,930
те само трябва масив на площ
20 да декларирате, че опашката, която

732
00:30:33,930 --> 00:30:37,070
само да кажа, сега, след като ние започнем да говорим
за тези по-високи нива на проблеми,

733
00:30:37,070 --> 00:30:38,890
можете да го приложат
в произволен брой начини.

734
00:30:38,890 --> 00:30:42,030
И там е най-вероятно просто ще
да бъде компромис в пространството и времето

735
00:30:42,030 --> 00:30:43,950
или само в собствения си код сложност.

736
00:30:43,950 --> 00:30:45,380
>> Какво ще кажете за комин?

737
00:30:45,380 --> 00:30:48,190
Е, една купчина, която сме виждали твърде
може да бъде само тези тави.

738
00:30:48,190 --> 00:30:50,007
И вие може да приложи този масив.

739
00:30:50,007 --> 00:30:53,090
Но в един момент, ако използвате масив,
какво ще се случи с тавите

740
00:30:53,090 --> 00:30:54,173
се опитвате да остави?

741
00:30:54,173 --> 00:30:55,170

742
00:30:55,170 --> 00:30:55,670
Добре.

743
00:30:55,670 --> 00:30:57,490
Вие само ще
да бъде в състояние да отиде толкова високо.

744
00:30:57,490 --> 00:31:00,156
И аз мисля, че в Mather те са
всъщност издълбана в този отвор.

745
00:31:00,156 --> 00:31:01,950
Така че, наистина, това е почти
като Mather използва

746
00:31:01,950 --> 00:31:03,783
масив от фиксиран размер,
защото само вие можете да

747
00:31:03,783 --> 00:31:08,302
поберат толкова много тави в тази пролука в
стената долу коленете на хората.

748
00:31:08,302 --> 00:31:10,010
И така, това може да бъде
казва, че е масив,

749
00:31:10,010 --> 00:31:14,300
но ние със сигурност може да го прилагат
по-общо свързан списък.

750
00:31:14,300 --> 00:31:16,390
>> Е, какво да кажем за друга структура данни?

751
00:31:16,390 --> 00:31:18,760
Позволете ми да спра един друг визуален тук.

752
00:31:18,760 --> 00:31:24,710
Нещо като как за този тук?

753
00:31:24,710 --> 00:31:28,920
Защо би могло да бъде полезно да не са
нещо като фантазия като синтактично дърво, което

754
00:31:28,920 --> 00:31:32,370
видяхме имаше тези много широки възли,
всеки от които е в масив?

755
00:31:32,370 --> 00:31:35,740
Но какво, ако можем да направим нещо по-
просто, като старата школа родословно дърво,

756
00:31:35,740 --> 00:31:38,110
всеки един от които възли тук
е просто съхраняване на брой.

757
00:31:38,110 --> 00:31:42,180
Вместо име или потомък
е просто съхраняване на брой като този.

758
00:31:42,180 --> 00:31:45,250
>> Е, на жаргон ние използваме в
структури от данни е двата опита

759
00:31:45,250 --> 00:31:49,510
и дървета, където Trie отново е
само един, чиито възли са масиви,

760
00:31:49,510 --> 00:31:51,680
все още е това, което може
използвате от началното училище

761
00:31:51,680 --> 00:31:53,860
когато сте направили семейство
tree-- листата и корена

762
00:31:53,860 --> 00:31:57,250
на дървото и деца на
майка и братя и сестри от тях.

763
00:31:57,250 --> 00:32:03,670
И ние може да изпълни едно дърво,
например, като просто като това.

764
00:32:03,670 --> 00:32:07,420
Дърво, ако като възел, един от
тези кръгове, че има няколко,

765
00:32:07,420 --> 00:32:09,947
това няма да има
една показалка, но две.

766
00:32:09,947 --> 00:32:11,780
И веднага след като добавите
втори указател, можете

767
00:32:11,780 --> 00:32:13,905
всъщност сега може да се направи нещо
на двумерен данни

768
00:32:13,905 --> 00:32:14,780
структури в паметта.

769
00:32:14,780 --> 00:32:16,660
Много прилича двуизмерен
масив, можете да

770
00:32:16,660 --> 00:32:18,904
има вид на двумерен
свързани списъци, но такива

771
00:32:18,904 --> 00:32:20,820
които следват един модел
където няма цикли.

772
00:32:20,820 --> 00:32:24,487
Това е наистина едно дърво с един
дядо път до тук и след това

773
00:32:24,487 --> 00:32:27,320
някои родители и деца и
внуци и правнуци.

774
00:32:27,320 --> 00:32:28,370
и така нататък.

775
00:32:28,370 --> 00:32:32,390
>> Но това, което е наистина хубаво за това също,
само за да ви дразни с малко код,

776
00:32:32,390 --> 00:32:35,370
изземване рекурсия от
известно време назад, при което

777
00:32:35,370 --> 00:32:38,220
пишете функция, която нарича себе си.

778
00:32:38,220 --> 00:32:41,140
Това е една красива възможност
да приложи нещо

779
00:32:41,140 --> 00:32:42,920
като рекурсия, тъй като смятат, че това.

780
00:32:42,920 --> 00:32:43,860
>> Това е дърво.

781
00:32:43,860 --> 00:32:48,040
И аз съм бил малко анален с колко
Сложих числа на улицата.

782
00:32:48,040 --> 00:32:51,020
Толкова много, така, че да има специална
name-- двоично търсене дърво.

783
00:32:51,020 --> 00:32:53,460
Сега сме чували за двоичен
търсите, но може да ви

784
00:32:53,460 --> 00:32:55,180
работят назад от името на това нещо е?

785
00:32:55,180 --> 00:32:59,280
Какъв е модела на това как
Създава числа в това дърво?

786
00:32:59,280 --> 00:33:00,696
Това не е произволно.

787
00:33:00,696 --> 00:33:01,570
Има някои модел.

788
00:33:01,570 --> 00:33:02,090
Да.

789
00:33:02,090 --> 00:33:03,370
>> АУДИТОРИЯ: по-малки от ляво.

790
00:33:03,370 --> 00:33:03,690
>> DAVID Malan: Да.

791
00:33:03,690 --> 00:33:05,062
По-малките от тях са от ляво.

792
00:33:05,062 --> 00:33:06,270
По-големите от тях са в дясно.

793
00:33:06,270 --> 00:33:12,940
Такава, че вярно твърдение е
майка е по-голяма от лявата му дете,

794
00:33:12,940 --> 00:33:14,850
но по-малко от правото си дете.

795
00:33:14,850 --> 00:33:17,750
И че само е дори
рекурсивни словесно определение

796
00:33:17,750 --> 00:33:20,500
защото можете да приложите, че
същата логика на всеки възел

797
00:33:20,500 --> 00:33:23,080
и то само дъна
от базова случай, ако

798
00:33:23,080 --> 00:33:25,740
ще, когато ви удари един от
листата, така да се каже,

799
00:33:25,740 --> 00:33:28,580
където отпуск е без деца по-нататък.

800
00:33:28,580 --> 00:33:30,614
>> Сега как може да намерите броя 44?

801
00:33:30,614 --> 00:33:32,280
Можете да започнете от корените и да кажа, хм.

802
00:33:32,280 --> 00:33:35,690
55 не е 44, Така че искам да отида
право или искам да тръгнете наляво?

803
00:33:35,690 --> 00:33:37,190
Е, очевидно искате да отидете наляво.

804
00:33:37,190 --> 00:33:40,060
И така, това е точно като на телефона
Например книга в двоично търсене

805
00:33:40,060 --> 00:33:41,099
по-общо.

806
00:33:41,099 --> 00:33:43,390
Но ние сме го прилагане
сега е малко по-динамично

807
00:33:43,390 --> 00:33:45,339
от масив може да позволи.

808
00:33:45,339 --> 00:33:48,130
И всъщност, ако искате да изглеждате
в кода, на пръв поглед сигурно.

809
00:33:48,130 --> 00:33:49,671
Прилича на куп линии.

810
00:33:49,671 --> 00:33:51,220
Но това е изключително лесно.

811
00:33:51,220 --> 00:33:54,490
Ако искате да се приложи функция
нарича търсене, чиято цел в живота

812
00:33:54,490 --> 00:33:57,290
е да се търси за стойност
като п е цяло число,

813
00:33:57,290 --> 00:34:01,756
и сте преминали през един pointer--
указател към възел на корените,

814
00:34:01,756 --> 00:34:04,380
по-скоро на това дърво, от които
можете да получите достъп до всичко останало,

815
00:34:04,380 --> 00:34:08,850
забележите как прямо
можете да реализирате логиката.

816
00:34:08,850 --> 00:34:10,880
Ако дървото е нула,
очевидно той не е там.

817
00:34:10,880 --> 00:34:11,880
Нека просто да се върне фалшиви.

818
00:34:11,880 --> 00:34:12,000
Така ли е?

819
00:34:12,000 --> 00:34:14,040
Ако го предаде нищо,
там няма нищо.

820
00:34:14,040 --> 00:34:17,900
>> Иначе, ако п е по-малко от
дърво стрелка, N- сега стрелка п,

821
00:34:17,900 --> 00:34:20,670
спомням ние въведохме супер
накратко на другия ден,

822
00:34:20,670 --> 00:34:25,100
и това просто означава, де-позоваването на
показалеца и погледнете в областта, наречена п.

823
00:34:25,100 --> 00:34:27,690
Така че това означава, че там и
погледнем в областта, наречена п.

824
00:34:27,690 --> 00:34:33,810
Така че, ако п, стойността ти даде, е по-малко
от стойността на числото дървета,

825
00:34:33,810 --> 00:34:35,449
Къде искате да отидете?

826
00:34:35,449 --> 00:34:36,389
Вляво.

827
00:34:36,389 --> 00:34:37,780
>> Така че забележите рекурсията.

828
00:34:37,780 --> 00:34:39,860
Аз съм returning-- не е вярно.

829
00:34:39,860 --> 00:34:40,989
Не е лъжа.

830
00:34:40,989 --> 00:34:45,670
Аз съм връщане, независимо от отговора
е от разговор с мен, минавайки

831
00:34:45,670 --> 00:34:50,100
п отново, което е излишно,
но това, което е малко по-различно сега?

832
00:34:50,100 --> 00:34:51,989
Как ми прави проблема по-малък?

833
00:34:51,989 --> 00:34:54,920
Аз съм преминаване в като втори
аргумент, а не на основата на дървото,

834
00:34:54,920 --> 00:34:59,616
но лявата детето в този случай.

835
00:34:59,616 --> 00:35:00,990
Така че аз съм преминаване в лявата детето.

836
00:35:00,990 --> 00:35:04,720
>> Междувременно, ако п е по-голям от
възела, Аз съм в момента гледа,

837
00:35:04,720 --> 00:35:06,690
Търся отдясно.

838
00:35:06,690 --> 00:35:10,880
Иначе, ако дървото не е нула, и
ако елементът не е вляво

839
00:35:10,880 --> 00:35:13,240
и това не е надясно,
това, което е чудесно за случая?

840
00:35:13,240 --> 00:35:14,630

841
00:35:14,630 --> 00:35:18,440
Ние сме всъщност намерих възел в
въпрос, и затова се върнете вярно.

842
00:35:18,440 --> 00:35:21,490
>> Така че ние току-що се почеса по повърхността
сега някои от тези структури от данни.

843
00:35:21,490 --> 00:35:24,370
При проблем определя пет вие ще
проучи тези още по-нататък,

844
00:35:24,370 --> 00:35:27,250
и вие ще се дава своя дизайн
избор за това как да отида за това.

845
00:35:27,250 --> 00:35:30,250
Онова, което бих искал да се направи заключение за
е само 30 секунди закачка

846
00:35:30,250 --> 00:35:32,080
от това, което очаква през следващата седмица и след това.

847
00:35:32,080 --> 00:35:35,390
>> Както begin-- щастие ви мощ
think-- нашия преход бавно

848
00:35:35,390 --> 00:35:38,680
от света на C и по-ниска
подробности по изпълнението ниво,

849
00:35:38,680 --> 00:35:42,090
в един свят, в който можем да вземем за
даденост, че някой друг е най-накрая

850
00:35:42,090 --> 00:35:44,010
изпълнява тези данни
структури за нас,

851
00:35:44,010 --> 00:35:47,570
и ние ще започнем да се разбере
реалния свят, означава на изпълнителните

852
00:35:47,570 --> 00:35:50,560
уеб-базирани програми и
уебсайтове, по-общо

853
00:35:50,560 --> 00:35:52,910
и също така много сигурността
последици, които сме само

854
00:35:52,910 --> 00:35:54,850
започнал да надраскат повърхността на.

855
00:35:54,850 --> 00:35:57,320
Ето какво ни очаква
в идните дни.

856
00:35:57,320 --> 00:36:00,480
>> [Възпроизвеждане на видео]

857
00:36:00,480 --> 00:36:03,432

858
00:36:03,432 --> 00:36:12,780
>> -Той Излезе със съобщение,
с протокол всичко сам.

859
00:36:12,780 --> 00:36:26,110

860
00:36:26,110 --> 00:36:30,894
Той дойде в един свят на жестока
защитни стени, незаинтересовани рутери,

861
00:36:30,894 --> 00:36:33,368
и опасностите далеч по-лоши от смъртта.

862
00:36:33,368 --> 00:36:35,280

863
00:36:35,280 --> 00:36:36,236
Той е бърз.

864
00:36:36,236 --> 00:36:37,980
Той е силен.

865
00:36:37,980 --> 00:36:42,830
Той е TCP / IP, и той има си адрес.

866
00:36:42,830 --> 00:36:45,290

867
00:36:45,290 --> 00:36:48,074
"Войни на мрежата."

868
00:36:48,074 --> 00:36:49,660
[END възпроизвеждане на видео]

869
00:36:49,660 --> 00:36:50,910
DAVID Malan: Очаквайте следващата седмица.

870
00:36:50,910 --> 00:36:51,880
Ние ще ви видя тогава.

871
00:36:51,880 --> 00:36:54,615

872
00:36:54,615 --> 00:36:56,060
[Възпроизвеждане на видео]

873
00:36:56,060 --> 00:36:59,240
-И Сега, "Дълбоки мисли"
от Daven Farnham.

874
00:36:59,240 --> 00:37:02,030

875
00:37:02,030 --> 00:37:05,820
-David Винаги започва
лекции с: "Добре."

876
00:37:05,820 --> 00:37:08,750
Защо не, "Тук е решението
за тази седмица проблем комплект "

877
00:37:08,750 --> 00:37:12,180
или "Ние даваме на всички вас, А?"

878
00:37:12,180 --> 00:37:13,380
[Сайта]

879
00:37:13,380 --> 00:37:15,530
[END възпроизвеждане на видео]