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 Маланом: Ова е 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
Некој би сакал да се нагаѓа зошто ова
графикон е толку JAGGY, нагоре надолу, нагоре надолу,

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 Маланом: Навистина.

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 Маланом: вметнување.

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
>> ПУБЛИКАТА: Насекаде заедно
Листа [нечујни].

41
00:01:37,872 --> 00:01:38,770
>> DAVID Маланом: Добро.

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 Маланом: Совршена.

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

56
00:02:10,590 --> 00:02:11,090
Совршен.

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
>> ПУБЛИКАТА: Не случаен пристап.

76
00:02:57,560 --> 00:02:58,809
>> DAVID Маланом: Не случаен пристап.

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 Маланом: Токму така.

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 Маланом: требаат повеќе меморија.

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 Маланом: Токму така.

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
беа големи О на 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
Јас би можеле да се стави сите на г-ѓа таму.

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

129
00:04:52,710 --> 00:04:55,020
Еве А. Па јас би можеле да
стави Како овде.

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

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

132
00:04:57,980 --> 00:05:02,490
Еве З. Еве уште еден М. И така
Јас би можеле да почнат да прават купови вака.

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-Н-

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
дека ако видам некој е
име кој започнува со,

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
Каде сакате да се стави
во однос на нејзината 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
>> ПУБЛИКАТА: Минус А.

159
00:06:10,206 --> 00:06:10,956
>> DAVID Маланом: Да.

160
00:06:10,956 --> 00:06:13,190
Па минус А или минус
конкретно 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
за ТФ да се најдат неговите или
квизови нејзините ученици.

174
00:06:54,050 --> 00:06:56,060
>> Па оваа идеја на hashing
тоа ќе го видите е

175
00:06:56,060 --> 00:07:00,520
доста моќен е всушност прилично
вообичаена и многу интуитивен,

176
00:07:00,520 --> 00:07:03,000
многу како можеби се делат и
Conquer беше во недела нула.

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
и З.Ш. таму.

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
Г-ѓа може да оди тука.

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
>> Сега порано јас вид на
измамени и го направи ова или јас

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 Маланом: Да.

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
Па ќе одам да го стави
технички каде Б ќе одат.

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

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

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
Биг О на што?

265
00:10:50,002 --> 00:10:51,147
>> ПУБЛИКАТА: n.

266
00:10:51,147 --> 00:10:52,480
DAVID Маланом: Еднаш го слушнав голема О на n.

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 Маланом: И дозволете ми да го направи визуелно.

273
00:11:00,380 --> 00:11:04,720
Така да претпоставиме ова е писмо С.

274
00:11:04,720 --> 00:11:05,604
>> ПУБЛИКАТА: Тоа е една.

275
00:11:05,604 --> 00:11:06,520
DAVID Маланом: Тоа е една.

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
и сфаќаме дека,
ох, тука е мојот влез С,

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
>> Но, се разбира, штом стигнам до
вториот човек кој е име е А или Б или Ц

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 Маланом: Значи тоа е n навистина еднаш
имате доволно голема група на податоци.

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
Како и нивните име или писмо
B, тоа може потенцијално

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 Маланом: Што ќе се воведат?

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
не врз основа на имиња на лицето,
но врз основа на нивните birthdates.

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 Маланом: Да.

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
И навистина, тоа исто така би
да се нарекува hash табелата,

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
во најлош случај тоа се случува да биде n.

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 Маланом: Совршена.

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
е голем O на n над 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 на n.

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
>> Но, во реалниот свет, со нас луѓето
дека сопствените Macs или компјутери или што

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
На онаа што го крајот чекори или
оној кој зема N поделено со 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
>> Поточно, јас ќе одам да се третираат
ова е A, тогаш B, тогаш C, а потоа D,

470
00:19:28,190 --> 00:19:29,310
ова овде.

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

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
Штом почнав Д известување
нема покажувачот таму.

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
Ако ова е само еден јазол во меморија, која
I создадени со Примерок, со користење на структура

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

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

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-- Д--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
>> Тогаш ние ќе треба да
сметаат дека тоа е В.

496
00:20:35,712 --> 00:20:44,920
А потоа надолу тука ние ќе да индекс
надолу од V во она што ние ќе се разгледа Е.

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
да се оди таму, затоа што ние би можеле да
никогаш не внесете збор како Девенпорт

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
Но, што ако на врвот
одно-- дното нечиј

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
>> Во меѓувреме, ако имав повеќе простор
тука, јас не можеше да стори П-О-Р-Т,

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

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
Trie, која е наводно
историски умен име за дрво

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

539
00:22:49,040 --> 00:22:50,870
е напишано со I-Е па тоа е Trie.

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

541
00:22:52,710 --> 00:22:55,860
>> Па еден Trie е ова дрво-like податоци
структура како семејно стебло

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 и Ес и Н.С.,

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 Маланом: Време.

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
David ќе биде пет чекори, како и.

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
Со други зборови, ако I
сакав да сега вметнете

576
00:24:15,460 --> 00:24:20,540
Колтон или Габриел или Роб или Zamyla или
Alison или Белинда или било која друга називи

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
Бидејќи сме ефикасно користење
овој мулти-слој hash табелата.

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

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
bool наречен 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 вие само треба еден
Покажувач на коренот на оваа 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
>> ПУБЛИКАТА: Што е bool збор?

623
00:26:17,220 --> 00:26:20,490
>> DAVID Маланом: 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
>> И покрај тоа што Dave се случува да биде
легитимни збор, тој не е во 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
И Г-не е збор или име.

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
Значи тоа е сите bool
таму се прави за нас.

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
Што ако имате Дејв и Daven?

642
00:26:59,945 --> 00:27:00,820
DAVID Маланом: Совршена.

643
00:27:00,820 --> 00:27:02,580
Што ако имате Дејв и 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
Константно време асимптотично.

655
00:27:21,590 --> 00:27:26,300
И сега ние сме посочи дека двете Дејв
и 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
Магацинот, како овие
Табли тука во Mather,

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

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

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
ПУБЛИКАТА: Тие се случува да pop еднократна.

677
00:28:24,480 --> 00:28:26,550
DAVID Маланом: Тие се случува да се
поп еднократна, се надевам на врвот.

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
и ви се разбудив во 03:00
да се редат на некои продавница

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 продавница

699
00:29:21,690 --> 00:29:25,700
но вие сте ефикасно долното
тава, бидејќи вработените Епл потоа

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
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
Ако јас сум првиот човек на Епл
Чување и ова е на влезната врата,

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
>> ПУБЛИКАТА: опашка.

722
00:30:14,542 --> 00:30:15,667
DAVID Маланом: Па, на опашката.

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
>> ПУБЛИКАТА: поврзани листа.

726
00:30:17,600 --> 00:30:18,990
>> DAVID Маланом: поврзани
листа можете да ги спроведе.

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
iPhone-на првиот ден, можеби

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
Зошто може да биде корисно за да не мора
нешто како фенси како Trie, која

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
Што е шемата за тоа како I
вметнале цели броеви во ова дрво?

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 Маланом: Да.

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
е да пребарување за вредност
како n, цел број,

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
Ајде само return false.

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 е помал од
дрво стрелка N-- сега стрелка н,

821
00:34:17,900 --> 00:34:20,670
потсетиме воведовме супер
кратко пред некој ден,

822
00:34:20,670 --> 00:34:25,100
и тоа само значи de-референца
покажувач и се погледне на областа наречена н.

823
00:34:25,100 --> 00:34:27,690
Па тоа значи одиме таму и
погледнете во областа наречена н.

824
00:34:27,690 --> 00:34:33,810
Значи, ако н, вредноста сте дадено, е помалку
од вредноста на дрво integer,

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

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
>> Во меѓувреме, ако n е поголема од
јазол Јас сум во моментов во потрага по,

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
web-базирани на програми и
интернет на генерално

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
Тој дојде во светот на суров
firewalls, незасегнатата рутери,

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 Маланом: следната недела пришествие.

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 Фарнхам.

874
00:36:59,240 --> 00:37:02,030

875
00:37:02,030 --> 00:37:05,820
-Дэвид Секогаш започнува
предавања со, "Сите во право."

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 видео репродукција]