1
00:00:00,000 --> 00:00:11,860

2
00:00:11,860 --> 00:00:13,120
>> SPEAKER 1: Добре, така че ние сме назад.

3
00:00:13,120 --> 00:00:14,480
Добре дошли в CS50.

4
00:00:14,480 --> 00:00:16,510
Това е края на седмицата седем.

5
00:00:16,510 --> 00:00:20,200
Така се припомни, че последния път, ние започнахме
разглежда по-сложни леко

6
00:00:20,200 --> 00:00:21,100
структурата на данните.

7
00:00:21,100 --> 00:00:25,110
Тъй като до този момент, всичко, което трябваше наистина
на наше разположение беше този, масив.

8
00:00:25,110 --> 00:00:29,340
>> Но преди да се изхвърли масив като не
всичко това интересно, което наистина го

9
00:00:29,340 --> 00:00:33,570
всъщност е, какви са някои от
плюсове на този прост данни

10
00:00:33,570 --> 00:00:34,560
структура до този момент?

11
00:00:34,560 --> 00:00:36,110
Какво е то добър в?

12
00:00:36,110 --> 00:00:39,450
Доколкото сме виждали?

13
00:00:39,450 --> 00:00:42,540
Какво имаш?

14
00:00:42,540 --> 00:00:44,028
Нищо.

15
00:00:44,028 --> 00:00:45,020
>> Студентът: [недоловим].

16
00:00:45,020 --> 00:00:45,395
>> SPEAKER 1: Какво е това?

17
00:00:45,395 --> 00:00:46,410
>> Студентът: [недоловим].

18
00:00:46,410 --> 00:00:47,000
>> SPEAKER 1: Fixed размер.

19
00:00:47,000 --> 00:00:51,260
ОК, така че защо е фиксиран размер добро все пак?

20
00:00:51,260 --> 00:00:53,180
>> Студентът: [недоловим].

21
00:00:53,180 --> 00:00:56,240
>> SPEAKER 1: Добре, така че това е ефективна в
смисъл, че можете да се разпредели

22
00:00:56,240 --> 00:01:00,070
фиксирана сума на пространството, което се надяваме,
е точно толкова

23
00:01:00,070 --> 00:01:01,180
пространство, както искате.

24
00:01:01,180 --> 00:01:02,720
Така че може да бъде абсолютно плюс.

25
00:01:02,720 --> 00:01:06,530
>> Какво е друг до страна на масив?

26
00:01:06,530 --> 00:01:07,610
Да?

27
00:01:07,610 --> 00:01:08,750
>> Студентът: [недоловим].

28
00:01:08,750 --> 00:01:09,550
>> SPEAKER 1: Всички - Моля?

29
00:01:09,550 --> 00:01:11,270
>> Студентът: [недоловим].

30
00:01:11,270 --> 00:01:13,620
>> SPEAKER 1: Всички полета в паметта
или един до друг.

31
00:01:13,620 --> 00:01:15,220
А това е полезно - защо?

32
00:01:15,220 --> 00:01:15,970
Това е съвсем вярно.

33
00:01:15,970 --> 00:01:18,611
Но как можем да използват тази истина?

34
00:01:18,611 --> 00:01:21,500
>> Студентът: [недоловим].

35
00:01:21,500 --> 00:01:24,490
>> SPEAKER 1: Точно така, ние можем да следите
където всичко е просто, знаейки

36
00:01:24,490 --> 00:01:28,560
един адрес, а именно адреса на
Първият байт на това парче на паметта.

37
00:01:28,560 --> 00:01:30,420
Или в случай на низа,
на адреса на първия

38
00:01:30,420 --> 00:01:31,460
Чар в този низ.

39
00:01:31,460 --> 00:01:33,330
И от там, можем да намерим
края на низ.

40
00:01:33,330 --> 00:01:35,710
Ние можем да намерим втория елемент, на
Третият елемент, и така нататък.

41
00:01:35,710 --> 00:01:38,740
>> И така, на фантазия може да се опише, че
особеност е, че ни дават масиви

42
00:01:38,740 --> 00:01:40,020
произволен достъп.

43
00:01:40,020 --> 00:01:44,330
Само с помощта на квадратна скоба
нотация и номер, можете да преминете към

44
00:01:44,330 --> 00:01:48,070
специфичен елемент в масив
в константно време, голяма O

45
00:01:48,070 --> 00:01:49,810
на една, така да се каже.

46
00:01:49,810 --> 00:01:51,080
>> Но е имало някои недостатъци.

47
00:01:51,080 --> 00:01:53,110
Какво не масив направи много лесно?

48
00:01:53,110 --> 00:01:55,810

49
00:01:55,810 --> 00:01:57,170
Какво не е добър?

50
00:01:57,170 --> 00:01:58,810
>> Студентът: [недоловим].

51
00:01:58,810 --> 00:01:59,860
>> SPEAKER 1: Какво е това?

52
00:01:59,860 --> 00:02:00,530
>> Студентът: [недоловим].

53
00:02:00,530 --> 00:02:01,460
>> SPEAKER 1: Разширяване на размера.

54
00:02:01,460 --> 00:02:04,800
Така че недостатъците на масива са
точно обратното на това, което

55
00:02:04,800 --> 00:02:05,540
квит сме.

56
00:02:05,540 --> 00:02:07,610
Така че един от недостатъците е
че е с фиксиран размер.

57
00:02:07,610 --> 00:02:09,400
Така че наистина не може да го отглеждат.

58
00:02:09,400 --> 00:02:13,510
Можете да преразпределят по-голяма буца
памет, и след това се премести на старите елементи

59
00:02:13,510 --> 00:02:14,460
в нов масив.

60
00:02:14,460 --> 00:02:18,060
И тогава безплатно стария масив, за
Например, с помощта на изчистване или подобна

61
00:02:18,060 --> 00:02:21,180
функция, наречена презаделяне, които
пренасочи памет.

62
00:02:21,180 --> 00:02:25,490
>> Презаделяне, като отмени, се опитва да ви даде
памет, която е в непосредствена близост до масива

63
00:02:25,490 --> 00:02:26,610
, че вече имате.

64
00:02:26,610 --> 00:02:28,740
Но това може да се движи нещата
около напълно.

65
00:02:28,740 --> 00:02:30,710
Но накратко, че е скъпо, нали?

66
00:02:30,710 --> 00:02:33,440
Защото, ако има парче от паметта на
този размер, но наистина искате една

67
00:02:33,440 --> 00:02:36,710
с този размер, и искате да запазите
оригиналните елементи, трябва

68
00:02:36,710 --> 00:02:40,510
приблизително линеен процес, време за копиране
която трябва да стане от

69
00:02:40,510 --> 00:02:41,900
стария масив към новия.

70
00:02:41,900 --> 00:02:44,630
А реалността иска от операционната
система отново и отново, и

71
00:02:44,630 --> 00:02:48,340
отново за големи блокове памет може да започне
за да ви струва известно време, както добре.

72
00:02:48,340 --> 00:02:52,250
Така че това е едновременно благословия и проклятие в
прикрие фактът, че тези масиви

73
00:02:52,250 --> 00:02:53,860
са с фиксиран размер.

74
00:02:53,860 --> 00:02:56,790
Но ако се въведе вместо нещо
подобен на този, който се обадихме на свързана

75
00:02:56,790 --> 00:03:00,580
списък, ние да вземем няколко плюсове и
няколко недостатъци тук.

76
00:03:00,580 --> 00:03:05,780
>> Така че един свързан списък е просто данни
конструкция на structs С в тази

77
00:03:05,780 --> 00:03:09,850
случай, когато една структура, изземване, е само
контейнер за един или повече специфични

78
00:03:09,850 --> 00:03:11,100
видове променливи.

79
00:03:11,100 --> 00:03:16,110
В този случай, това, което направи на типовете данни
изглежда да е вътре в структурата, че

80
00:03:16,110 --> 00:03:17,600
Последният път, когато нарича възел?

81
00:03:17,600 --> 00:03:19,380
Всеки един от тези правоъгълници е възел.

82
00:03:19,380 --> 00:03:22,660
И всяка една от по-малките правоъгълници
във вътрешността му е тип данни.

83
00:03:22,660 --> 00:03:25,300
Какви видове казахме
те са били в понеделник?

84
00:03:25,300 --> 00:03:26,478
Да?

85
00:03:26,478 --> 00:03:27,870
>> Студентът: [недоловим].

86
00:03:27,870 --> 00:03:30,721
>> SPEAKER 1: A променлива и показалеца, или
По-специално, едно цяло число, за N,

87
00:03:30,721 --> 00:03:32,180
и указател на дъното.

88
00:03:32,180 --> 00:03:35,360
И двете от тези, които се случи да бъде 32 бита, в
поне на компютър, подобен на този CS50

89
00:03:35,360 --> 00:03:37,980
Техника, и така те са
съставен по равно по размер.

90
00:03:37,980 --> 00:03:42,260
>> Така че това, което използвате показалеца
макар и за очевидно?

91
00:03:42,260 --> 00:03:47,690
Защо добавите стрелка сега, когато бяха масиви
толкова хубаво и чисто и просто?

92
00:03:47,690 --> 00:03:50,460
Какво е показалеца правиш за
ние в всеки един от тези възли?

93
00:03:50,460 --> 00:03:52,160
>> Студентът: [недоловим].

94
00:03:52,160 --> 00:03:52,465
>> SPEAKER 1: Точно така.

95
00:03:52,465 --> 00:03:54,120
Той ти казва, когато
следващата се.

96
00:03:54,120 --> 00:03:57,350
Така че аз нещо като използваме аналогията на
с помощта на конец, за да сортирате на

97
00:03:57,350 --> 00:03:59,180
вденете тези възли заедно.

98
00:03:59,180 --> 00:04:01,760
И това е точно това, което правим с
указатели, тъй като всеки от тях

99
00:04:01,760 --> 00:04:06,360
блокове памет може или не може да бъде
тези, обратно към Насрещен

100
00:04:06,360 --> 00:04:09,500
вътрешността на RAM, защото всеки път, когато
обадете изчистване казвайки ми даде достатъчно

101
00:04:09,500 --> 00:04:12,510
байта за нов възел, може да
да е тук или че може да е тук.

102
00:04:12,510 --> 00:04:13,120
Тя може да бъде тук.

103
00:04:13,120 --> 00:04:13,730
Тя може да бъде тук.

104
00:04:13,730 --> 00:04:14,640
Вие просто не знам.

105
00:04:14,640 --> 00:04:17,880
>> Но използването на указатели в адресите на
тези възли, можете да ги бод

106
00:04:17,880 --> 00:04:22,370
заедно по начин, който изглежда визуално
като списък, дори ако тези неща са

107
00:04:22,370 --> 00:04:26,770
всички разпределени през целия си една или
Вашите две или вашите четири гигабайта RAM

108
00:04:26,770 --> 00:04:28,760
вътрешността на собствения си компютър.

109
00:04:28,760 --> 00:04:33,230
>> Така посока надолу, а след това, на
на свързан списък е какво?

110
00:04:33,230 --> 00:04:34,670
Каква е цената, която ние сме
очевидно плаща за това?

111
00:04:34,670 --> 00:04:36,010
>> Студентът: [недоловим].

112
00:04:36,010 --> 00:04:36,920
>> SPEAKER 1: Повече място, нали?

113
00:04:36,920 --> 00:04:39,340
Ние, в този случай, два пъти сумата,
на пространството, защото сме преминали

114
00:04:39,340 --> 00:04:43,500
от 32 бита за всеки възел, за всеки
Int, така че сега 64 бита, защото трябва да

115
00:04:43,500 --> 00:04:45,050
запази около показалеца, както добре.

116
00:04:45,050 --> 00:04:48,860
Можете да получите по-голяма ефективност, ако вашата структура
е по-голямо от това просто нещо.

117
00:04:48,860 --> 00:04:52,020
Ако действително има един студент в
на които е няколко струни за

118
00:04:52,020 --> 00:04:55,430
име и къща, може би идентификационен номер,
може би някои други области като цяло.

119
00:04:55,430 --> 00:04:59,000
>> Така че, ако имате достатъчно голяма структура,
тогава може би цената на показалеца е

120
00:04:59,000 --> 00:05:00,010
не е толкова голяма работа.

121
00:05:00,010 --> 00:05:03,570
Това е малко на един ъгъл в случай, че
ние сме съхраняване такъв прост примитивен

122
00:05:03,570 --> 00:05:04,760
вътрешността на свързан списък.

123
00:05:04,760 --> 00:05:05,790
Но въпросът е един и същ.

124
00:05:05,790 --> 00:05:08,230
Определено си харчи повече
памет, но сте се

125
00:05:08,230 --> 00:05:08,990
гъвкавост.

126
00:05:08,990 --> 00:05:12,280
Защото сега, ако искам да добавят елемент
в началото на този списък,

127
00:05:12,280 --> 00:05:14,340
Трябва да се разпредели нов възел.

128
00:05:14,340 --> 00:05:17,180
И аз трябва да актуализирате само тези,
стрелките някак си само с преместване

129
00:05:17,180 --> 00:05:17,980
някои насоки наоколо.

130
00:05:17,980 --> 00:05:20,580
>> Ако искате да вмъкнете нещо в
средата на списъка, не трябва да

131
00:05:20,580 --> 00:05:24,410
бутнете всеки настрана както направихме в
седмици миналото с нашите доброволци, които

132
00:05:24,410 --> 00:05:25,700
представени масив.

133
00:05:25,700 --> 00:05:29,470
Мога да си разпределят нов възел и
След това просто точка на стрелките в

134
00:05:29,470 --> 00:05:32,290
различни посоки, тъй като не
трябва да остане в действителната

135
00:05:32,290 --> 00:05:35,670
памет истински ред, че съм съставен
то тук на екрана.

136
00:05:35,670 --> 00:05:38,400
>> И тогава на последно място, ако искате да вмъкнете
нещо, което в края на списъка, че е

137
00:05:38,400 --> 00:05:39,210
още по-лесно.

138
00:05:39,210 --> 00:05:43,320
Това е нещо като произволна бройна система,
но 34 на показалеца, да предположите.

139
00:05:43,320 --> 00:05:46,710
Каква е стойността на показалеца си най-
вероятно изготвен нещо като стар

140
00:05:46,710 --> 00:05:47,700
училище антена там?

141
00:05:47,700 --> 00:05:48,920
>> Студентът: [недоловим].

142
00:05:48,920 --> 00:05:49,900
>> SPEAKER 1: Вероятно това е нищожна.

143
00:05:49,900 --> 00:05:52,710
И наистина това е един автора
представителство на нула.

144
00:05:52,710 --> 00:05:56,310
И това е нищожна, защото сте абсолютно
Трябва да знаем къде края на свързан

145
00:05:56,310 --> 00:06:00,050
Списъкът е, за да не се съхранява след и
след и след тези стрели

146
00:06:00,050 --> 00:06:01,170
някои боклук стойност.

147
00:06:01,170 --> 00:06:06,230
Така нула ще означава, че няма
повече възли на правото на номер 34,

148
00:06:06,230 --> 00:06:07,200
в този случай.

149
00:06:07,200 --> 00:06:10,270
>> Така че предлагам да могат да се реализират
този възел в кода.

150
00:06:10,270 --> 00:06:12,130
И сме виждали този вид
на синтаксиса преди.

151
00:06:12,130 --> 00:06:15,090
Typedef просто определя нов тип за
ни, ни дава синоним като

152
00:06:15,090 --> 00:06:17,100
низ е за Чар *.

153
00:06:17,100 --> 00:06:21,030
В този случай, това ще ни даде
краткото записване, така че структурата на възел

154
00:06:21,030 --> 00:06:24,010
може вместо просто да се запише като
възловата точка, която е много по-чисти.

155
00:06:24,010 --> 00:06:25,360
Това е много по-малко многословен.

156
00:06:25,360 --> 00:06:30,080
>> Вътре възел е очевидно едно цяло число
наречена N, а след това и структурата възел *

157
00:06:30,080 --> 00:06:34,670
което означава точно това, което искахме
стрелките, за да кажа, указател към друг

158
00:06:34,670 --> 00:06:36,940
възел на точно същия тип данни.

159
00:06:36,940 --> 00:06:40,300
И аз предлагам да може да приложи
функция за търсене, подобен на този, който най-

160
00:06:40,300 --> 00:06:41,890
пръв поглед може да изглежда
малко комплекс.

161
00:06:41,890 --> 00:06:43,330
Но нека да видим това в контекст.

162
00:06:43,330 --> 00:06:45,480
>> Оставете ме да премина към уреда тук.

163
00:06:45,480 --> 00:06:48,460
Нека да отворят файл, наречен
списък нулева точка з.

164
00:06:48,460 --> 00:06:53,950
И че само съдържа определението ние
Току-що видях преди малко за тези данни

165
00:06:53,950 --> 00:06:55,390
тип нарича възел.

166
00:06:55,390 --> 00:06:57,350
Така че ние сме поставени, че в точка файл з.

167
00:06:57,350 --> 00:07:01,430
>> И като настрана, въпреки че това
програма, която сте на път да видите, е

168
00:07:01,430 --> 00:07:05,410
Не всичко, което комплекс, това е наистина
Конвенцията при писане на програма за

169
00:07:05,410 --> 00:07:10,270
постави нещата като типове данни, за да дръпнете
константи понякога, вътрешността на

170
00:07:10,270 --> 00:07:13,210
заглавния файл, а не непременно в
си C файл, със сигурност, когато

171
00:07:13,210 --> 00:07:17,370
програми стават по-големи и по-големи, така че
Вие знаете къде да търсите, както за

172
00:07:17,370 --> 00:07:20,840
документация, в някои случаи, или
за основните неща по този начин,

173
00:07:20,840 --> 00:07:22,360
определяне на някакъв вид.

174
00:07:22,360 --> 00:07:25,680
>> Ако сега се отвори списък нулева точка
С забележите няколко неща.

175
00:07:25,680 --> 00:07:29,090
Тя включва няколко заглавни файлове, повечето
на което сме виждали преди.

176
00:07:29,090 --> 00:07:31,980
Тя включва собствен заглавен файл.

177
00:07:31,980 --> 00:07:35,200
>> И като настрана, защо това е двойно
Цитати тук, за разлика от ъгъла

178
00:07:35,200 --> 00:07:38,340
скоби на линията, която
Аз бях подчерта там?

179
00:07:38,340 --> 00:07:39,180
>> Студентът: [недоловим].

180
00:07:39,180 --> 00:07:40,460
>> SPEAKER 1: Да, така че е локален файл.

181
00:07:40,460 --> 00:07:44,300
Така че, ако това е локален файл на свой собствен тук
по линия 15, например, да използвате

182
00:07:44,300 --> 00:07:46,570
двойните кавички вместо
от ъглови скоби.

183
00:07:46,570 --> 00:07:48,270
>> Сега това е нещо интересно.

184
00:07:48,270 --> 00:07:51,830
Забележете, че съм обявен за глобален
променлива в тази програма по линия 18

185
00:07:51,830 --> 00:07:55,910
нарича Първо, идеята е това е
Ще бъде указател към първия

186
00:07:55,910 --> 00:07:59,190
възел в свързания списъка ми, и съм
инициализира го присвоява, защото съм

187
00:07:59,190 --> 00:08:02,310
не са разпределени всяко действително
възли, просто все още.

188
00:08:02,310 --> 00:08:07,570
>> Така че това означава, картинно, това, което ние
видях преди малко в картина като

189
00:08:07,570 --> 00:08:10,090
че показалецът на далеч
лявата страна.

190
00:08:10,090 --> 00:08:12,260
Така че точно сега, че показалеца
не оказва стрелка.

191
00:08:12,260 --> 00:08:14,590
Вместо това е само нищожна.

192
00:08:14,590 --> 00:08:17,880
Но той представлява това, което ще бъде
адресът на първия действителното

193
00:08:17,880 --> 00:08:19,480
възел в този списък.

194
00:08:19,480 --> 00:08:22,120
Така че аз съм приложен е глобален
защото, както ще видите, всичко това

195
00:08:22,120 --> 00:08:25,310
Програмата се прилага в живота е
на свързан списък за мен.

196
00:08:25,310 --> 00:08:27,050
>> Сега имам няколко прототипа тук.

197
00:08:27,050 --> 00:08:31,190
Реших да прилагат функции, като
изтриване, вмъкване, търсене, и

198
00:08:31,190 --> 00:08:31,740
прекосявам -

199
00:08:31,740 --> 00:08:35,210
последната просто е разходка през
списък, отпечатване на нейните елементи.

200
00:08:35,210 --> 00:08:36,750
И сега тук е моят основната програма.

201
00:08:36,750 --> 00:08:39,890
И ние няма да прекарват твърде много време в
тях, тъй като това е нещо, надявам се

202
00:08:39,890 --> 00:08:41,780
стара шапка от сега.

203
00:08:41,780 --> 00:08:45,370
>> Отивам да направя следното,
докато потребителят сътрудничи.

204
00:08:45,370 --> 00:08:47,300
Така един, аз отивам да отпечатате
от това меню.

205
00:08:47,300 --> 00:08:49,420
И съм форматирал него като
чисто, колкото можех.

206
00:08:49,420 --> 00:08:52,240
Ако потребителят на едно, това означава, че
те искат да изтриете нещо.

207
00:08:52,240 --> 00:08:54,560
Ако потребителят на две, това означава, че
те искат да вмъкнете нещо.

208
00:08:54,560 --> 00:08:55,930
И така нататък.

209
00:08:55,930 --> 00:08:58,270
Ще бъдете подканени
След това за команда.

210
00:08:58,270 --> 00:08:59,300
И тогава аз ще използвам GetInt.

211
00:08:59,300 --> 00:09:02,790
>> Така че това е много проста menuing
намесвам, когато просто трябва да въведете

212
00:09:02,790 --> 00:09:05,270
редица картографиране на една
на тези команди.

213
00:09:05,270 --> 00:09:08,730
И сега имам хубава чиста ключ
декларация, че ще се включите

214
00:09:08,730 --> 00:09:10,090
независимо от потребителя написали инча

215
00:09:10,090 --> 00:09:12,180
И ако те написали едно, аз ще
обадете изтриете и почивка.

216
00:09:12,180 --> 00:09:14,380
Ако те написали два, аз ще
обадете вмъкнете и почивка.

217
00:09:14,380 --> 00:09:16,490
>> И сега забелязвам сме поставени всеки
от тях на една и съща линия.

218
00:09:16,490 --> 00:09:18,360
Това е просто стилистични решения.

219
00:09:18,360 --> 00:09:20,210
Обикновено сме виждали нещо
по този начин.

220
00:09:20,210 --> 00:09:23,260
Но аз просто реших, честно казано, моята програма
изглеждаше по-разбираемо, защото

221
00:09:23,260 --> 00:09:25,980
тя е само четири случая на
просто го списъка по този начин.

222
00:09:25,980 --> 00:09:28,360
Totally законното използване на стил.

223
00:09:28,360 --> 00:09:31,480
И аз ще направя това, докато на
Потребителят не е въвел нула, което аз

224
00:09:31,480 --> 00:09:33,910
реши, ще означава, че те искат да се откажат.

225
00:09:33,910 --> 00:09:36,630
>> Така че сега забележите това, което съм
ще направим тук.

226
00:09:36,630 --> 00:09:38,650
Отивам да освободи списък очевидно.

227
00:09:38,650 --> 00:09:40,230
Но повече за, че в един момент.

228
00:09:40,230 --> 00:09:41,640
Нека първо да стартирате тази програма.

229
00:09:41,640 --> 00:09:45,250
Така че нека да се направи по-голям терминал
прозорец, точка наклонена черта списък 0.

230
00:09:45,250 --> 00:09:49,510
Отивам да се продължи напред и го поставете от
пишете две, редица като 50, а сега

231
00:09:49,510 --> 00:09:51,590
ще видите списък сега е 50.

232
00:09:51,590 --> 00:09:53,380
И моят текст просто превъртат малко.

233
00:09:53,380 --> 00:09:55,940
Така че сега забележите списъкът съдържа
50 броя.

234
00:09:55,940 --> 00:09:58,220
>> Нека да направим още една вложка, като се вземат две.

235
00:09:58,220 --> 00:10:01,630
Нека да изпишете номера като такъв.

236
00:10:01,630 --> 00:10:03,940
Списък сега е един, последван от 50.

237
00:10:03,940 --> 00:10:06,020
Така че това е просто текстово представяне
на списъка.

238
00:10:06,020 --> 00:10:10,550
И нека да вмъкнете още един номер като
броят 42, което е се надяваме

239
00:10:10,550 --> 00:10:14,620
ще свърши в средата, защото
тази програма, по-специално видове него

240
00:10:14,620 --> 00:10:16,320
елементи, тъй като им вложки.

241
00:10:16,320 --> 00:10:17,220
Така че ние я имаме.

242
00:10:17,220 --> 00:10:20,730
Super проста програма, която може да
абсолютно са използвали масив, но аз

243
00:10:20,730 --> 00:10:23,280
се случи да се използва свързан списък
само за да мога да динамично

244
00:10:23,280 --> 00:10:24,610
растат и да го свие.

245
00:10:24,610 --> 00:10:28,470
>> Така че, нека да погледнем за търсене, ако
Изпълнява КОМАНДА три, искам да търсите

246
00:10:28,470 --> 00:10:31,040
за, да речем, на номер 43.

247
00:10:31,040 --> 00:10:34,190
И нищо не е очевидно установено,
защото се върнах никакъв отговор.

248
00:10:34,190 --> 00:10:35,010
Така че нека да го направим отново.

249
00:10:35,010 --> 00:10:35,690
Търсене.

250
00:10:35,690 --> 00:10:39,520
Нека търсенето на 50, или по-скоро търсене
за 42, което има хубав

251
00:10:39,520 --> 00:10:40,850
малко коварен значение.

252
00:10:40,850 --> 00:10:42,610
И открих смисъла на живота там.

253
00:10:42,610 --> 00:10:44,990
Брой 42, ако не знаете
препратка, то Google.

254
00:10:44,990 --> 00:10:45,350
Добре.

255
00:10:45,350 --> 00:10:47,130
И така, какво е тази програма направи за мен?

256
00:10:47,130 --> 00:10:50,660
Това е просто ми позволи да вмъкнете този начин
далеч и търсене на елементи.

257
00:10:50,660 --> 00:10:53,650
>> Нека бързо напред, а след това, за да
тази функция ние погледна

258
00:10:53,650 --> 00:10:55,360
В понеделник като закачка.

259
00:10:55,360 --> 00:10:59,620
Така че тази функция, аз твърдя, търси
елемент в списъка, като първо

260
00:10:59,620 --> 00:11:03,830
един, подканване на потребителя и след това призовава
GetInt да получите действително Int

261
00:11:03,830 --> 00:11:05,060
, която искате да търсите.

262
00:11:05,060 --> 00:11:06,460
>> Тогава забележите това.

263
00:11:06,460 --> 00:11:10,690
Отивам да се създаде временна променлива
188 в съответствие нарича показалеца -

264
00:11:10,690 --> 00:11:11,270
PTR -

265
00:11:11,270 --> 00:11:12,440
можеше да го нарече нещо.

266
00:11:12,440 --> 00:11:16,140
И това е указател към възела
защото казах възел * там.

267
00:11:16,140 --> 00:11:19,900
И аз съм инициализиране тя да бъде равна на
първо, за да мога ефективно да имам

268
00:11:19,900 --> 00:11:22,860
пръст, така да се каже, на много
Първият елемент от списъка.

269
00:11:22,860 --> 00:11:27,460
Така че, ако дясната ми ръка тук е PTR съм
сочи едно и също нещо, че първата

270
00:11:27,460 --> 00:11:28,670
се посочи.

271
00:11:28,670 --> 00:11:31,430
>> Така че сега отново в кода,
какво се случва след това -

272
00:11:31,430 --> 00:11:35,070
това е една обща парадигма при обработката на текста
в продължение на структурата като

273
00:11:35,070 --> 00:11:35,970
свързан списък.

274
00:11:35,970 --> 00:11:40,410
Отивам да направите следното, докато
показалеца не е равна на нула Така че, докато

275
00:11:40,410 --> 00:11:47,530
пръста ми не е насочена към някои нула
стойност, ако Стрелката п равнява п.

276
00:11:47,530 --> 00:11:52,290
Ще забележите, че първо п е това, което
потребителя напечатани в на GetInts наричат ​​тук.

277
00:11:52,290 --> 00:11:54,280
>> Стрелката и п означава какво?

278
00:11:54,280 --> 00:11:59,020
Ами ако се върнем на снимката тук,
ако имам пръст сочеше

279
00:11:59,020 --> 00:12:02,960
че първата точка, съдържаща девет, на
стрелка по същество означава, отидете на тази

280
00:12:02,960 --> 00:12:08,860
възел и вземете стойността на местоположението N,
В този случай, данните поле, наречено п.

281
00:12:08,860 --> 00:12:14,120
>> Като настрана - и ние видяхме това няколко
Преди седмица, когато някой попита -

282
00:12:14,120 --> 00:12:18,840
този синтаксис е нова, но тя не
да ни даде сили, които ние

283
00:12:18,840 --> 00:12:20,040
не вече имате.

284
00:12:20,040 --> 00:12:25,325
Каква беше тази фраза едно да се използва
точкова нотация и звезда двойка

285
00:12:25,325 --> 00:12:29,490
Преди седмица, когато се отлепи назад
този слой малко преждевременно?

286
00:12:29,490 --> 00:12:31,780
>> Студентът: [недоловим].

287
00:12:31,780 --> 00:12:38,880
>> SPEAKER 1: Точно така, това е звезда, и
След това беше звездни точка N, с

288
00:12:38,880 --> 00:12:41,930
скоби тук, които изглежда,
честно казано, мисля, че много

289
00:12:41,930 --> 00:12:43,320
по-загадъчен за четене.

290
00:12:43,320 --> 00:12:46,270
Но звездата показалеца, както винаги,
средства там.

291
00:12:46,270 --> 00:12:49,090
И след като сте там, какви данни
областта искаш да влезете?

292
00:12:49,090 --> 00:12:52,730
Ами използвате точка нотация за достъп
а structs полето за данни, и аз

293
00:12:52,730 --> 00:12:54,140
специално искам п.

294
00:12:54,140 --> 00:12:56,240
>> Честно казано, бих казал, това
е просто по-трудно да се чете.

295
00:12:56,240 --> 00:12:58,080
Това е трудно да си спомня къде
се скобите отида, на

296
00:12:58,080 --> 00:12:59,030
звезда и всичко това.

297
00:12:59,030 --> 00:13:02,150
Така света приемат някои синтактични
захар, така да се каже.

298
00:13:02,150 --> 00:13:04,740
Само един секси начин да се каже,
това е еквивалентно, и

299
00:13:04,740 --> 00:13:05,970
може би по-интуитивен.

300
00:13:05,970 --> 00:13:09,600
Ако показалецът е наистина показалеца, на
средства със стрелки нотация отида там и да намерят

301
00:13:09,600 --> 00:13:11,890
областта в този случай нарича п.

302
00:13:11,890 --> 00:13:13,660
>> Така че, ако го намерите, обърнете внимание на това, което правя.

303
00:13:13,660 --> 00:13:17,430
Аз просто разпечатате, открих аз процента,
включване на стойност за този вътр.

304
00:13:17,430 --> 00:13:20,730
Призовавам спя за една секунда, само за да вид
на пауза неща на екрана, за да

305
00:13:20,730 --> 00:13:22,900
дава на потребителя секунди да абсорбира
какво стана.

306
00:13:22,900 --> 00:13:24,290
И тогава аз се счупят.

307
00:13:24,290 --> 00:13:26,330
В противен случай, какво да правя?

308
00:13:26,330 --> 00:13:30,960
I актуализира показалеца на равно
показалеца на стрелката.

309
00:13:30,960 --> 00:13:35,840
>> Така че просто да е ясно, това означава, отидете
там, използвайки моя старата школа нотация.

310
00:13:35,840 --> 00:13:39,580
Така че това просто означава, за да отидете на каквото и
, което сочи, които в много

311
00:13:39,580 --> 00:13:43,660
Първият случай е, че аз съм сочеше
на структура с девет в него.

312
00:13:43,660 --> 00:13:44,510
Така че аз съм отишъл там.

313
00:13:44,510 --> 00:13:47,880
И тогава точката нотация означава,
получите стойността на следващото.

314
00:13:47,880 --> 00:13:50,470
>> Но на стойност, въпреки че е изготвен
като тесен, е просто число.

315
00:13:50,470 --> 00:13:51,720
Това е цифров адрес.

316
00:13:51,720 --> 00:13:55,670
Така че това един ред код, независимо дали
написан по този начин, толкова по-загадъчен

317
00:13:55,670 --> 00:14:00,190
начин, или по този начин, малко по-
интуитивен начин, просто означава, премести ръката ми

318
00:14:00,190 --> 00:14:03,460
от първия възел към следващия,
и след това на следващия, и след това

319
00:14:03,460 --> 00:14:05,320
следващата, и така нататък.

320
00:14:05,320 --> 00:14:09,920
>> Така че ние няма да се спираме, от друга
реализации на вмъквате и изтривате

321
00:14:09,920 --> 00:14:14,030
и прекосявам, първите две от
които са доста участват.

322
00:14:14,030 --> 00:14:17,010
И мисля, че това е доста лесно да се получи
загубят, когато го правят устно.

323
00:14:17,010 --> 00:14:19,890
Но какво можем да направим тук, е
се опитват да определят как

324
00:14:19,890 --> 00:14:21,640
най-добре да направите това визуално.

325
00:14:21,640 --> 00:14:24,800
Защото аз предлагам, че ако
искате да вмъкнете елементи в тази

326
00:14:24,800 --> 00:14:26,680
съществуващ списък, който
има пет елемента -

327
00:14:26,680 --> 00:14:29,530
9, 17, 22, 26, и 33 -

328
00:14:29,530 --> 00:14:33,300
ако щяха да се приложи тази в
код, аз трябва да се помисли как да стане

329
00:14:33,300 --> 00:14:34,160
направят това.

330
00:14:34,160 --> 00:14:37,720
>> И аз предлагам да приемате малки стъпки
при което, в този случай искам да кажа, това, което са

331
00:14:37,720 --> 00:14:41,090
възможните сценарии, които ние
може да срещнете по принцип?

332
00:14:41,090 --> 00:14:44,120
При прилагането на вложка за свързан
списък, това просто се случва да бъде

333
00:14:44,120 --> 00:14:46,090
Характерен пример за размера пет.

334
00:14:46,090 --> 00:14:50,420
Е, ако искате да въведете цифра,
като твърдят, че броят една страна, и

335
00:14:50,420 --> 00:14:53,380
поддържане сортирани цел, когато е
очевидно прави номер едно трябва да

336
00:14:53,380 --> 00:14:55,686
отидете в този конкретен пример?

337
00:14:55,686 --> 00:14:56,840
Както в началото.

338
00:14:56,840 --> 00:15:00,030
>> Но това, което е интересно е, че
ако желаете да вмъкнете едно в тази

339
00:15:00,030 --> 00:15:04,100
списък, какви специални показалеца трябва
да се актуализира очевидно?

340
00:15:04,100 --> 00:15:04,610
Първо.

341
00:15:04,610 --> 00:15:07,830
Така че бих казал, че това е първият случай
че може да искате да разгледа, а

342
00:15:07,830 --> 00:15:11,140
сценарий включва поставяне на
началото на списъка.

343
00:15:11,140 --> 00:15:15,400
>> Нека одират може би един толкова лесно, или дори
по-лесно така, относително казано.

344
00:15:15,400 --> 00:15:18,110
Да предположим, че искате да вкарате
номер 35 в сортирани цел.

345
00:15:18,110 --> 00:15:20,600
Тя очевидно принадлежи там.

346
00:15:20,600 --> 00:15:25,320
И така, какво показалеца очевидно ще
трябва да се актуализира в този сценарий?

347
00:15:25,320 --> 00:15:30,060
34 на показалеца все не нула
но на адреса на структурата

348
00:15:30,060 --> 00:15:31,800
съдържащ броя 35.

349
00:15:31,800 --> 00:15:32,750
Така че това е случай две.

350
00:15:32,750 --> 00:15:36,190
Така вече, аз съм нещо като квантуване
колко много работа трябва да направя тук.

351
00:15:36,190 --> 00:15:39,880
>> И накрая, очевидно случая средата е
Действително, в средата, ако искам да

352
00:15:39,880 --> 00:15:45,870
вмъкнете нещо като думата 23, която отива
между 23 и 26, но

353
00:15:45,870 --> 00:15:48,680
Сега нещата стават малко по-
участва, защото това, което

354
00:15:48,680 --> 00:15:52,800
указатели трябва да се промени?

355
00:15:52,800 --> 00:15:56,680
Така 22 очевидно трябва да се промени
, тъй като не може да посочи 26 повече.

356
00:15:56,680 --> 00:16:00,320
Той трябва да сочи към нова възлова точка, която
Ще трябва да се разпределят, като се обадите

357
00:16:00,320 --> 00:16:01,770
изчистване или някакъв еквивалент.

358
00:16:01,770 --> 00:16:05,990
>> Но тогава аз също се нуждаят от този нов възел, 23
в този случай, да има своя показалеца

359
00:16:05,990 --> 00:16:07,870
посочи кого?

360
00:16:07,870 --> 00:16:08,560
26.

361
00:16:08,560 --> 00:16:10,380
И там ще бъде
цел на операциите тук.

362
00:16:10,380 --> 00:16:13,410
Защото, ако върша това безумие и аз
например започва от началото на

363
00:16:13,410 --> 00:16:16,040
списъка, и моята цел е да поставите 23.

364
00:16:16,040 --> 00:16:18,610
И да проверя, пък принадлежат
тук, в близост до девет?

365
00:16:18,610 --> 00:16:18,950
Не.

366
00:16:18,950 --> 00:16:20,670
Има ли тук мястото, до 17?

367
00:16:20,670 --> 00:16:20,940
Не.

368
00:16:20,940 --> 00:16:22,530
Дали тя принадлежи тук до 22?

369
00:16:22,530 --> 00:16:23,300
Да.

370
00:16:23,300 --> 00:16:26,400
>> Сега, ако аз съм глупаво тук, а не
мисля това през, може

371
00:16:26,400 --> 00:16:28,320
разпредели новата ми възел за 23.

372
00:16:28,320 --> 00:16:32,080
Аз може да актуализира показалеца от
възела, наречен 22, сочейки

373
00:16:32,080 --> 00:16:33,080
то на нов възел.

374
00:16:33,080 --> 00:16:36,140
И след това какво трябва да се актуализира
показалеца на нов възел да бъде?

375
00:16:36,140 --> 00:16:38,120
>> Студентът: [недоловим].

376
00:16:38,120 --> 00:16:38,385
>> SPEAKER 1: Точно така.

377
00:16:38,385 --> 00:16:39,710
Посочването на 26.

378
00:16:39,710 --> 00:16:45,590
Но дявол да го вземе, ако не бях вече актуализира
Показалеца 22 по точка в този човек, и

379
00:16:45,590 --> 00:16:48,260
сега имам сираци, останалите
на списъка, така да се каже.

380
00:16:48,260 --> 00:16:52,140
Така реда на операциите тук
ще бъде важно.

381
00:16:52,140 --> 00:16:55,100
>> За да направите това може ли да открадна,
да речем, шест доброволци.

382
00:16:55,100 --> 00:16:57,650
И нека да видим дали не можем да направим това
визуално вместо код-мъдър.

383
00:16:57,650 --> 00:16:59,330
И ние имаме някаква хубава стрес
топчета за вас днес.

384
00:16:59,330 --> 00:17:02,510
OK, какво ще кажеш за един, два, в
обратно - в края там.

385
00:17:02,510 --> 00:17:04,530
три, четири, и на двама ви
момчетата в края.

386
00:17:04,530 --> 00:17:05,579
И пет, шест.

387
00:17:05,579 --> 00:17:05,839
Разбира се.

388
00:17:05,839 --> 00:17:06,450
Пет и шест.

389
00:17:06,450 --> 00:17:08,390
Добре ние ще дойдем
с вас следващия път.

390
00:17:08,390 --> 00:17:09,640
Добре, качвай се.

391
00:17:09,640 --> 00:17:12,010

392
00:17:12,010 --> 00:17:14,819
>> Добре, след като си тук, първо,
бихте искали да бъде едно опасно

393
00:17:14,819 --> 00:17:16,119
в Google Glass тук?

394
00:17:16,119 --> 00:17:19,075
Добре, това е така, OK, стъкло,
запишете видеоклип.

395
00:17:19,075 --> 00:17:22,720

396
00:17:22,720 --> 00:17:24,589
ОК, вие сте добре да тръгвам.

397
00:17:24,589 --> 00:17:27,950
>> Добре, така че ако вие може да дойдеш
тук, съм приготвил предварително

398
00:17:27,950 --> 00:17:30,110
някои цифри.

399
00:17:30,110 --> 00:17:31,240
Добре, ела тук.

400
00:17:31,240 --> 00:17:33,440
И защо не отидеш малко
допълнително по този начин.

401
00:17:33,440 --> 00:17:35,520
И нека да видим, как ти е името,
с Glass Google?

402
00:17:35,520 --> 00:17:35,910
>> Студентът: Ben.

403
00:17:35,910 --> 00:17:36,230
>> SPEAKER 1: Бен?

404
00:17:36,230 --> 00:17:38,380
OK, Бен, ще бъдат първи, буквално.

405
00:17:38,380 --> 00:17:40,580
Така че, ние ще Ви изпратим
до края на етапа.

406
00:17:40,580 --> 00:17:41,670
Добре, и вашето име?

407
00:17:41,670 --> 00:17:41,990
>> Студентът: Джейсън.

408
00:17:41,990 --> 00:17:44,530
>> SPEAKER 1: Jason, OK ти ще
бъде номер девет.

409
00:17:44,530 --> 00:17:46,700
Така че, ако искате да следвате Ben този начин.

410
00:17:46,700 --> 00:17:47,010
>> Студентът: Jill.

411
00:17:47,010 --> 00:17:49,630
>> SPEAKER 1: Jill, ти започваш да бъде
17, които, ако бях направил това по-

412
00:17:49,630 --> 00:17:51,260
интелигентно, аз ще трябва
започна в от другата страна.

413
00:17:51,260 --> 00:17:52,370
Ти отиде по този начин.

414
00:17:52,370 --> 00:17:53,030
22.

415
00:17:53,030 --> 00:17:53,670
А вие сте?

416
00:17:53,670 --> 00:17:53,980
>> Студентът: Mary.

417
00:17:53,980 --> 00:17:56,130
>> SPEAKER 1: Mary, ще бъде 22.

418
00:17:56,130 --> 00:17:58,420
И името ти е?

419
00:17:58,420 --> 00:17:58,810
>> Студентът: Chris.

420
00:17:58,810 --> 00:18:00,100
>> SPEAKER 1: Крис, ще бъде 26.

421
00:18:00,100 --> 00:18:00,740
И тогава накрая.

422
00:18:00,740 --> 00:18:01,400
>> Студентът: Diana.

423
00:18:01,400 --> 00:18:02,670
>> SPEAKER 1: Diana, ще бъде 34.

424
00:18:02,670 --> 00:18:03,920
Така че ела тук.

425
00:18:03,920 --> 00:18:06,360
>> Добре, толкова съвършена, сортирано
поръчате вече.

426
00:18:06,360 --> 00:18:09,600
И да вървим напред и да направите това
така че наистина можем да -

427
00:18:09,600 --> 00:18:11,720
Ben ти си просто вид търсите
навън в нищото там.

428
00:18:11,720 --> 00:18:15,670
ОК, така че да вървим напред и да изобразяват тази
използване на оръжие, подобно бях точно,,

429
00:18:15,670 --> 00:18:16,250
какво става.

430
00:18:16,250 --> 00:18:19,540
Така че продължавайте напред и Подарете си
пеша или два между себе си.

431
00:18:19,540 --> 00:18:22,900
И давай напред и посочи с ръка към
всеки, който трябва да се посочи

432
00:18:22,900 --> 00:18:23,470
въз основа на това.

433
00:18:23,470 --> 00:18:25,890
И ако сте нула просто точка
право надолу към пода.

434
00:18:25,890 --> 00:18:27,690
ОК, така добре.

435
00:18:27,690 --> 00:18:32,290
>> Така че сега ние имаме свързан списък, и ме пусна
предложи, че ще играе ролята на

436
00:18:32,290 --> 00:18:35,110
PTR, така че аз няма да се притеснява
нося това наоколо.

437
00:18:35,110 --> 00:18:37,830
И след това - някой глупав конвенция -
можете да се обадите това всичко, което искате -

438
00:18:37,830 --> 00:18:39,800
предшественик показалеца, Pred показалеца -

439
00:18:39,800 --> 00:18:43,930
това е само псевдоним дадохме в
нашия примерен код за лявата си ръка.

440
00:18:43,930 --> 00:18:47,240
От друга страна, че ще бъде водене
следите на кой кой е в

441
00:18:47,240 --> 00:18:48,400
следните сценарии.

442
00:18:48,400 --> 00:18:52,390
>> Така че предполагам, първо, искам да скубя
че първият пример за вмъкване, да речем

443
00:18:52,390 --> 00:18:54,330
20, в списъка.

444
00:18:54,330 --> 00:18:57,160
Така че ми трябва някой, който да
въплъщават номер 20 за нас.

445
00:18:57,160 --> 00:18:58,950
Така че аз трябва да изчистване някой
от публиката.

446
00:18:58,950 --> 00:18:59,380
Хайде нагоре.

447
00:18:59,380 --> 00:19:00,340
Как се казваш?

448
00:19:00,340 --> 00:19:01,300
>> Студентът: Brian.

449
00:19:01,300 --> 00:19:05,270
>> SPEAKER 1: Brian, добре, така че
е възел, съдържащ 20.

450
00:19:05,270 --> 00:19:06,810
Добре, ела тук.

451
00:19:06,810 --> 00:19:10,025
И очевидно, когато
се Brian принадлежат?

452
00:19:10,025 --> 00:19:12,190
Така че, в средата на - всъщност,
чакай малко.

453
00:19:12,190 --> 00:19:13,420
Ние правим това от ред.

454
00:19:13,420 --> 00:19:17,170
Правим това много по-трудно
освен това трябва да бъде в началото.

455
00:19:17,170 --> 00:19:21,210
OK, отиваме на свободно Brian
и презаделяне Brian като пет.

456
00:19:21,210 --> 00:19:23,680
>> ОК, така че сега искаме да вмъкнете
Brian като пет.

457
00:19:23,680 --> 00:19:25,960
Така че ела тук до
Ben само за миг.

458
00:19:25,960 --> 00:19:28,250
И вие може да се предполага кажа
където тази история става.

459
00:19:28,250 --> 00:19:30,500
Но нека да помислят внимателно
реда на операциите.

460
00:19:30,500 --> 00:19:32,880
И това е точно този визуален
че това ще се подредят

461
00:19:32,880 --> 00:19:34,080
с този примерен код.

462
00:19:34,080 --> 00:19:40,120
Така че тук съм PTR сочи първоначално
не на Бен, сам по себе си, но каквото и

463
00:19:40,120 --> 00:19:43,245
ценим той съдържа, което в този случай
е - това, което ти беше името?

464
00:19:43,245 --> 00:19:43,670
>> Студентът: Джейсън.

465
00:19:43,670 --> 00:19:47,350
>> SPEAKER 1: Jason, така Ben както и аз сме
сочеше Jason в този момент.

466
00:19:47,350 --> 00:19:49,700
Така че сега ще трябва да се определи,
къде Brian принадлежат?

467
00:19:49,700 --> 00:19:53,500
Така че единственото нещо, което има достъп до
точно сега му е п показател за данни.

468
00:19:53,500 --> 00:19:58,280
Така че аз ще да се провери, е
Brian по-малко от Jason?

469
00:19:58,280 --> 00:19:59,770
Отговорът е вярно.

470
00:19:59,770 --> 00:20:03,680
>> И сега какво трябва да се случи,
в правилния ред?

471
00:20:03,680 --> 00:20:07,120
Трябва ли да актуализирам колко указатели
общо в тази история?

472
00:20:07,120 --> 00:20:10,720
Когато ръката ми все още сочеше
Джейсън, и ръката си - ако искате да

473
00:20:10,720 --> 00:20:12,930
сложи си ръка като, нещо, I
не знам, въпросителен знак.

474
00:20:12,930 --> 00:20:14,070
Добре, добре.

475
00:20:14,070 --> 00:20:15,670
>> Добре, така че имате
няколко кандидати.

476
00:20:15,670 --> 00:20:20,500
Ben или I или Brian или Jason
или всеки друг, който

477
00:20:20,500 --> 00:20:21,370
указатели трябва да се промени?

478
00:20:21,370 --> 00:20:23,260
Колко общо?

479
00:20:23,260 --> 00:20:24,080
>> ОК, така че два.

480
00:20:24,080 --> 00:20:27,090
Моята показалеца няма значение вече
защото аз съм само временно.

481
00:20:27,090 --> 00:20:31,370
Така че тези две момчета, вероятно,
Бен и Брайън.

482
00:20:31,370 --> 00:20:34,410
Така че позволете ми да предложа да актуализирате
Бен, тъй като той е на първо място.

483
00:20:34,410 --> 00:20:36,350
Първият елемент от този списък
сега ще бъде Брайън.

484
00:20:36,350 --> 00:20:38,070
Така Ben точка на Брайън.

485
00:20:38,070 --> 00:20:39,320
ОК, сега какво?

486
00:20:39,320 --> 00:20:41,950

487
00:20:41,950 --> 00:20:43,460
>> Кой ще посочи към кого?

488
00:20:43,460 --> 00:20:44,710
>> Студентът: [недоловим].

489
00:20:44,710 --> 00:20:46,180
>> SPEAKER 1: ОК, така Brian има
точка към Джейсън.

490
00:20:46,180 --> 00:20:48,360
Но съм изгубили следите на показалеца, че?

491
00:20:48,360 --> 00:20:49,980
Да знам къде е Джейсън?

492
00:20:49,980 --> 00:20:50,790
>> Студентът: [недоловим].

493
00:20:50,790 --> 00:20:52,620
>> SPEAKER едно: да направя, тъй като аз съм
временното показалеца.

494
00:20:52,620 --> 00:20:55,110
И се предполага, че не са се променили
да посочи в нов възел.

495
00:20:55,110 --> 00:20:58,300
Така че ние можем просто трябва Brian точка
в който аз съм сочеше.

496
00:20:58,300 --> 00:20:59,000
И сме готови.

497
00:20:59,000 --> 00:21:01,890
Така единия случай вмъкване в
началото на списъка.

498
00:21:01,890 --> 00:21:02,950
Имаше две ключови стъпки.

499
00:21:02,950 --> 00:21:06,750
One, трябва да актуализирате Бен, а след това
ние също трябва да се актуализира Брайън.

500
00:21:06,750 --> 00:21:09,230
И тогава не е нужно да се притеснява
traipsing през останалата част от

501
00:21:09,230 --> 00:21:12,680
списъка, тъй като вече е намерил своя
място, защото той принадлежи на

502
00:21:12,680 --> 00:21:14,080
отляво на първия елемент.

503
00:21:14,080 --> 00:21:15,400
>> Добре, така че доста ясен.

504
00:21:15,400 --> 00:21:18,110
В действителност, има усещането, че сме почти
извършването на тази твърде сложна.

505
00:21:18,110 --> 00:21:20,240
Така че нека сега одират края
на списъка, и да видим къде

506
00:21:20,240 --> 00:21:21,380
сложността започва.

507
00:21:21,380 --> 00:21:24,560
Така че, ако сега, заделянето на памет от страна на публиката.

508
00:21:24,560 --> 00:21:25,540
Всеки, който иска да играе 55?

509
00:21:25,540 --> 00:21:26,700
Добре, видях ръката си пръв.

510
00:21:26,700 --> 00:21:29,620
Хайде нагоре.

511
00:21:29,620 --> 00:21:30,030
Да.

512
00:21:30,030 --> 00:21:31,177
Как се казваш?

513
00:21:31,177 --> 00:21:32,310
>> Студентът: [недоловим].

514
00:21:32,310 --> 00:21:33,240
>> SPEAKER 1: Habata.

515
00:21:33,240 --> 00:21:33,890
Добре, качвай се.

516
00:21:33,890 --> 00:21:35,730
Ще се броят 55.

517
00:21:35,730 --> 00:21:37,820
Така че, разбира се, принадлежат
в края на списъка.

518
00:21:37,820 --> 00:21:41,850
Така че нека да замествам симулацията с мен
е на PTR само за миг.

519
00:21:41,850 --> 00:21:44,050
Така че аз съм първият ще посоча
независимо на Бен посочи.

520
00:21:44,050 --> 00:21:45,900
И двамата сочи сега на Браян.

521
00:21:45,900 --> 00:21:48,420
Така че 55 не е по-малко от пет.

522
00:21:48,420 --> 00:21:52,510
Така че, аз отивам да се актуализира от
сочещи към следващия показалеца на Брайън, който

523
00:21:52,510 --> 00:21:54,450
Сега, разбира се, Джейсън.

524
00:21:54,450 --> 00:21:57,310
55 не е по-малко от девет, така че
Отивам да се актуализира PTR.

525
00:21:57,310 --> 00:21:58,890
Отивам да се актуализира PTR.

526
00:21:58,890 --> 00:22:02,290
Отивам да се актуализира PTR
Аз ще актуализира PTR.

527
00:22:02,290 --> 00:22:05,060
И аз ще - Хм, какво е
ти беше името?

528
00:22:05,060 --> 00:22:05,560
>> Студентът: Diana.

529
00:22:05,560 --> 00:22:09,190
>> SPEAKER 1: Diana сочи, разбира се,
на нула с лявата си ръка.

530
00:22:09,190 --> 00:22:13,030
Е, къде прави Habata всъщност
принадлежат ясно?

531
00:22:13,030 --> 00:22:15,050
В ляво, тук.

532
00:22:15,050 --> 00:22:19,460
Е, как да знам, за да я сложи тук
Мисля, че съм провалил.

533
00:22:19,460 --> 00:22:22,420
Защото това, което е PTR изкуство
настоящия момент?

534
00:22:22,420 --> 00:22:23,240
Null.

535
00:22:23,240 --> 00:22:25,580
Така че, въпреки че, визуално, ние можем
очевидно виж всички от тях

536
00:22:25,580 --> 00:22:26,610
момчета тук на сцената.

537
00:22:26,610 --> 00:22:29,680
Аз не съм следял предходната
лице в списъка.

538
00:22:29,680 --> 00:22:33,210
Аз нямам пръст посочи,
в този случай възловата точка номер 34.

539
00:22:33,210 --> 00:22:34,760
>> Така че да започнете действително това свърши.

540
00:22:34,760 --> 00:22:37,560
Така че сега аз действително е нужно
втори локална променлива.

541
00:22:37,560 --> 00:22:40,980
И това е, което ще видите в
действителната проба C код, където, както и да отида,

542
00:22:40,980 --> 00:22:45,860
когато се актуализира дясната ми ръка да се отбележи
Джейсън, като по този начин остави зад Брайън, I

543
00:22:45,860 --> 00:22:51,440
По-добре да използва лявата си ръка, за да
актуализира, когато бях, така че като отида

544
00:22:51,440 --> 00:22:52,700
чрез този списък -

545
00:22:52,700 --> 00:22:55,040
по-опасно, отколкото възнамерявах
Сега тук визуално -

546
00:22:55,040 --> 00:22:56,740
Ще стигнем до
края на списъка.

547
00:22:56,740 --> 00:23:00,020
>> Тази страна все още е нула, което е доста
безполезни, освен да покаже,

548
00:23:00,020 --> 00:23:02,980
Аз съм ясно в края на списъка,
но сега поне имам тази

549
00:23:02,980 --> 00:23:08,270
предшественик показалеца сочи тук, така че
Сега това, което ръцете и какво указатели трябва

550
00:23:08,270 --> 00:23:10,150
за да се актуализира?

551
00:23:10,150 --> 00:23:13,214
Чия ръка искаш
да преконфигурирате първи?

552
00:23:13,214 --> 00:23:15,190
>> Студентът: [недоловим].

553
00:23:15,190 --> 00:23:16,220
>> SPEAKER 1: ОК, така че Даяна.

554
00:23:16,220 --> 00:23:21,110
Къде искате да посоча
Ляво Даяна показалеца на?

555
00:23:21,110 --> 00:23:23,620
На 55, вероятно, така че
ние сме добавя там.

556
00:23:23,620 --> 00:23:25,560
А там, където трябва 55 показалеца отидете?

557
00:23:25,560 --> 00:23:27,000
Down, представлява нищожна.

558
00:23:27,000 --> 00:23:28,890
И ръцете ми, в този момент, не
значение, защото те са само

559
00:23:28,890 --> 00:23:30,070
временни променливи.

560
00:23:30,070 --> 00:23:31,030
Така че сега сме готови.

561
00:23:31,030 --> 00:23:34,650
>> Така че допълнителната сложност там - и
това не е толкова трудно за изпълнение,

562
00:23:34,650 --> 00:23:38,660
но ние се нуждаем от помощна променлива, за да
се, че преди да се движи дясната си

563
00:23:38,660 --> 00:23:42,140
страна, аз се актуализира стойността на лявата ми
страна, Pred показалеца в този случай, така че

564
00:23:42,140 --> 00:23:45,860
че имам зад гърба показалеца
, за да следите къде се намирам.

565
00:23:45,860 --> 00:23:49,360
Сега като настрана, ако си мислиш това
чрез това се чувства като тя е

566
00:23:49,360 --> 00:23:51,490
малко досадно да трябва да се запази
проследяване на това лявата ръка.

567
00:23:51,490 --> 00:23:54,015
>> Какво би друго решение
на този проблем са?

568
00:23:54,015 --> 00:23:56,500
Ако имаш да редизайн на данните
структура говорим

569
00:23:56,500 --> 00:23:59,630
чрез точно сега?

570
00:23:59,630 --> 00:24:02,690
Ако това просто вид чувства малко
досадно да трябва, като, две указатели

571
00:24:02,690 --> 00:24:08,430
върви по списъка, кой друг може да
са, в един идеален свят, поддържа

572
00:24:08,430 --> 00:24:10,160
информация, която ни трябва?

573
00:24:10,160 --> 00:24:11,360
Да?

574
00:24:11,360 --> 00:24:12,610
>> Студентът: [недоловим].

575
00:24:12,610 --> 00:24:15,160

576
00:24:15,160 --> 00:24:16,150
>> SPEAKER 1: Точно така.

577
00:24:16,150 --> 00:24:19,130
Точно така всъщност има интересен
кълнове на една идея.

578
00:24:19,130 --> 00:24:22,470
И тази идея на предишния показалеца,
сочещи за предишния елемент.

579
00:24:22,470 --> 00:24:25,580
Ами ако просто въплътена че
вътре в себе си списък?

580
00:24:25,580 --> 00:24:27,810
И това ще бъде трудно да се визуализира
това, без цялата хартия

581
00:24:27,810 --> 00:24:28,830
падане на пода.

582
00:24:28,830 --> 00:24:31,860
Но да предположим, че тези момчета използват както
на ръцете им да имат предишен

583
00:24:31,860 --> 00:24:35,950
показалеца, и следващия показалеца, като по този начин
прилагане на това, което ние ще се обадя на двойно

584
00:24:35,950 --> 00:24:36,830
свързан списък.

585
00:24:36,830 --> 00:24:41,090
Това ще ми позволи да сортирате назад,
много по-лесно, без мен,

586
00:24:41,090 --> 00:24:43,800
програмист, се налага да се запази
проследявам ръчно -

587
00:24:43,800 --> 00:24:44,980
наистина ръчно -

588
00:24:44,980 --> 00:24:47,280
от мястото, където съм бил преди това
в списъка.

589
00:24:47,280 --> 00:24:48,110
Така че ние няма да направим това.

590
00:24:48,110 --> 00:24:50,950
Ние ще продължаваме да го прости, защото това е
ще дойде на цена, два пъти

591
00:24:50,950 --> 00:24:53,450
много място за указатели,
ако искате втори.

592
00:24:53,450 --> 00:24:55,760
Но това е наистина обща
данни структура, известна като

593
00:24:55,760 --> 00:24:57,410
двойно свързан списък.

594
00:24:57,410 --> 00:25:01,310
>> Нека да направим окончателния например тук и да
тези момчета на тяхното нещастие.

595
00:25:01,310 --> 00:25:03,270
Така изчистване 20.

596
00:25:03,270 --> 00:25:05,320
Хайде нагоре от пътеката там.

597
00:25:05,320 --> 00:25:06,280
Добре, как ти е името?

598
00:25:06,280 --> 00:25:07,440
>> Студентът: [недоловим].

599
00:25:07,440 --> 00:25:07,855
>> SPEAKER 1: Моля?

600
00:25:07,855 --> 00:25:08,480
>> Студентът: [недоловим].

601
00:25:08,480 --> 00:25:09,410
>> SPEAKER 1: Demeron?

602
00:25:09,410 --> 00:25:10,230
OK качвай се.

603
00:25:10,230 --> 00:25:11,910
Вие трябва да бъде 20.

604
00:25:11,910 --> 00:25:14,720
Вие очевидно ще
принадлежат между 17 и 22.

605
00:25:14,720 --> 00:25:16,150
Така че позволете ми да научат урока си.

606
00:25:16,150 --> 00:25:18,150
Аз ще започна показалеца
сочеше Брайън.

607
00:25:18,150 --> 00:25:21,190
И аз ще имам лявата ръка
актуализирате само да Brian като се преместя в

608
00:25:21,190 --> 00:25:23,600
Jason, проверка прави 20 по-малко от девет?

609
00:25:23,600 --> 00:25:24,060
Не.

610
00:25:24,060 --> 00:25:25,430
20 е по-малко от 17?

611
00:25:25,430 --> 00:25:25,880
Не.

612
00:25:25,880 --> 00:25:27,450
Е с 20 по-малко от 22?

613
00:25:27,450 --> 00:25:28,440
Да.

614
00:25:28,440 --> 00:25:34,070
И така, какво указатели или ръцете трябва да се промени
където те насочваш сега?

615
00:25:34,070 --> 00:25:37,070
>> Така че, можем да направим 17 сочеше 20.

616
00:25:37,070 --> 00:25:37,860
Така че, това е добре.

617
00:25:37,860 --> 00:25:40,080
Къде искаме да посоча
показалеца сега?

618
00:25:40,080 --> 00:25:41,330
В 22.

619
00:25:41,330 --> 00:25:45,410
И ние знаем, където 22 е, отново благодаря
да ми временно показалеца.

620
00:25:45,410 --> 00:25:46,760
Така че ние сме ОК там.

621
00:25:46,760 --> 00:25:49,440
Така че заради това временно складиране
Аз съм следял, където всеки е.

622
00:25:49,440 --> 00:25:55,055
И сега можете визуално да отидат в която
ти е мястото, а сега ние трябва 1, 2, 3,

623
00:25:55,055 --> 00:25:58,410
4, 5, 6, 7, 8, 9 стрес топки,
и аплодисменти за

624
00:25:58,410 --> 00:25:59,770
тези момчета, ако можехме.

625
00:25:59,770 --> 00:26:00,410
Браво.

626
00:26:00,410 --> 00:26:05,320
>> [APPLAUSE]

627
00:26:05,320 --> 00:26:06,330
>> SPEAKER 1: Добре.

628
00:26:06,330 --> 00:26:09,860
И вие може да задържи парчета
на хартия като спомени.

629
00:26:09,860 --> 00:26:15,930
>> Всички права, така, повярвай ми това е много
по-лесно да преминете през този с

630
00:26:15,930 --> 00:26:17,680
хора, отколкото е с застроена код.

631
00:26:17,680 --> 00:26:22,690
Но това, което ще намерите в един момент
сега, е, че една и съща - О, благодаря ви.

632
00:26:22,690 --> 00:26:23,630
Благодаря ви -

633
00:26:23,630 --> 00:26:29,360
е, че вие ​​ще откриете, че едни и същи данни
структура, на свързан списък, всъщност може

634
00:26:29,360 --> 00:26:33,200
да се използва като градивен елемент за още по-
сложни структури от данни.

635
00:26:33,200 --> 00:26:37,620
>> И осъзнават твърде темата тук е, че
ние сме абсолютно въведени по-

636
00:26:37,620 --> 00:26:40,060
сложността на изпълнението
на този алгоритъм.

637
00:26:40,060 --> 00:26:43,940
Insertion, и ако я преживяхме,
заличаване и търсене, е малко

638
00:26:43,940 --> 00:26:46,660
по-сложно, отколкото е
е с множество.

639
00:26:46,660 --> 00:26:48,040
Но ние получаваме някаква динамика.

640
00:26:48,040 --> 00:26:50,180
Ние получите адаптивна структура на данните.

641
00:26:50,180 --> 00:26:54,010
>> Но отново, плащаме цената на като някои
допълнителна сложност, както в

642
00:26:54,010 --> 00:26:54,910
прилагане него.

643
00:26:54,910 --> 00:26:56,750
И ние сме се отказали от произволен достъп.

644
00:26:56,750 --> 00:27:00,450
И за да бъда честен, не е някой хубав
чисто предметно мога да ви дам, че

645
00:27:00,450 --> 00:27:03,120
Тук пише защо свързан списък
е по-добре от масив.

646
00:27:03,120 --> 00:27:04,100
И да спрем дотук.

647
00:27:04,100 --> 00:27:07,520
Тъй като темата отново появяване на предприятието, дори
Още повече, че през следващите седмици, е

648
00:27:07,520 --> 00:27:10,200
че там не е задължително
един верен отговор.

649
00:27:10,200 --> 00:27:13,830
>> Ето защо ние имаме отделна ос
на дизайн за проблемните групи.

650
00:27:13,830 --> 00:27:17,700
Той ще бъде много зависи от контекста
дали искате да използвате тези данни

651
00:27:17,700 --> 00:27:21,750
структура или че един, и то ще
зависи от това, което има значение за вас по отношение

652
00:27:21,750 --> 00:27:24,620
на ресурсите и сложност.

653
00:27:24,620 --> 00:27:28,830
>> Но нека да предложи идеални данни
структура, Светия Граал, ще бъде

654
00:27:28,830 --> 00:27:32,200
нещо, което е константно време,
независимо от това колко неща е

655
00:27:32,200 --> 00:27:36,940
вътре в нея, не би ли било невероятно, ако
структурата на данните върнати отговори в

656
00:27:36,940 --> 00:27:37,920
константно време.

657
00:27:37,920 --> 00:27:38,330
Да.

658
00:27:38,330 --> 00:27:40,110
Тази дума е в огромния си речник.

659
00:27:40,110 --> 00:27:41,550
Или Не, тази дума няма.

660
00:27:41,550 --> 00:27:43,270
Или някой такъв проблем съществува.

661
00:27:43,270 --> 00:27:46,360
Ами нека да видим, ако не можем поне
предприеме стъпка към това.

662
00:27:46,360 --> 00:27:50,190
>> Нека да предложи нова структура на данните, които
може да се използва за различни неща,

663
00:27:50,190 --> 00:27:52,260
В този случай нарича хеш таблица.

664
00:27:52,260 --> 00:27:55,590
И така, ние всъщност сме обратно към фланга
в масив, в този случай, и

665
00:27:55,590 --> 00:28:00,550
донякъде произволно, съм нарисувал
хеш таблица като масив с нещо като

666
00:28:00,550 --> 00:28:02,810
двумерен масив -

667
00:28:02,810 --> 00:28:05,410
или по-скоро това е изобразен тук като две
двумерен масив - но това е само

668
00:28:05,410 --> 00:28:10,770
масив с размер 26, така че ако
обадете се на масив, маса скоба

669
00:28:10,770 --> 00:28:12,440
нула е правоъгълник в горната част.

670
00:28:12,440 --> 00:28:15,090
Таблица скоба 25 е правоъгълник
в долната част.

671
00:28:15,090 --> 00:28:18,620
А това е как бих могъл да нарисувате данни
структура, в която искам да се съхранява

672
00:28:18,620 --> 00:28:19,790
хората имена.

673
00:28:19,790 --> 00:28:24,370
>> Така например, и аз няма да привлече
всичко тук на режийни, ако

674
00:28:24,370 --> 00:28:29,160
имаше този масив, който аз сега ще
повикване на хеш таблица, и това е отново

675
00:28:29,160 --> 00:28:31,360
Местоположение нула.

676
00:28:31,360 --> 00:28:34,840
Това тук е мястото
една страна, и така нататък.

677
00:28:34,840 --> 00:28:37,880
Аз твърдя, че искам да използват тази информация,
структура, в името на дискусията,

678
00:28:37,880 --> 00:28:42,600
да съхранявате имената на хората, Alice и Bob
и Charlie и други такива имена.

679
00:28:42,600 --> 00:28:46,110
Така че мисля за това сега, като началото
на, да речем, един речник

680
00:28:46,110 --> 00:28:47,520
с много думи.

681
00:28:47,520 --> 00:28:49,435
Те се случи да бъде имена
В нашия пример тук.

682
00:28:49,435 --> 00:28:52,560
А това е твърде уместен, може би, за да
прилагане за проверка на правописа, тъй като ние

683
00:28:52,560 --> 00:28:54,400
може за определен проблем шест.

684
00:28:54,400 --> 00:28:59,300
>> Така че, ако имаме масив на обща площ 26
, така че това е 25-място

685
00:28:59,300 --> 00:29:03,390
на дъното, и аз твърдя, че Алис е
първата дума в речника на

686
00:29:03,390 --> 00:29:07,260
имена, които искам да вмъкнете в RAM,
в тази структура от данни, където са

687
00:29:07,260 --> 00:29:12,480
инстинктите ви казвам, че на Алис
Името трябва да отида в този масив?

688
00:29:12,480 --> 00:29:13,510
>> Имаме 26 опции.

689
00:29:13,510 --> 00:29:14,990
Когато искаме да я сложите?

690
00:29:14,990 --> 00:29:16,200
Ние я искам в скобата нула, нали?

691
00:29:16,200 --> 00:29:18,280
А за Алис, нека го наречем, че е нула.

692
00:29:18,280 --> 00:29:20,110
И B ще бъде една и С ще бъдат две.

693
00:29:20,110 --> 00:29:22,600
Така че ние ще напишем
Алис име тук.

694
00:29:22,600 --> 00:29:24,890
Ако след това поставете Bob, си
Името ще отидете тук.

695
00:29:24,890 --> 00:29:27,280
Charlie ще отидете тук.

696
00:29:27,280 --> 00:29:30,500
И така нататък надолу през
тези данни структура.

697
00:29:30,500 --> 00:29:32,090
>> Това е една прекрасна структура на данните.

698
00:29:32,090 --> 00:29:32,730
Защо?

699
00:29:32,730 --> 00:29:37,460
Ами това, което е времето на работа
поставите името на човека е в това

700
00:29:37,460 --> 00:29:39,850
структура на данните в момента?

701
00:29:39,850 --> 00:29:43,702
Като се има предвид, че тази таблица се прилага,
наистина, като масив.

702
00:29:43,702 --> 00:29:44,940
Ами това е константно време.

703
00:29:44,940 --> 00:29:45,800
Това е състояние на някой.

704
00:29:45,800 --> 00:29:46,360
Защо?

705
00:29:46,360 --> 00:29:48,630
>> Е, как да се определи
където Alice принадлежи?

706
00:29:48,630 --> 00:29:51,000
Вие търсите в която буква от името си?

707
00:29:51,000 --> 00:29:51,490
Първият.

708
00:29:51,490 --> 00:29:54,350
И вие можете да отидете там, ако това е низ,
от просто гледам на низ

709
00:29:54,350 --> 00:29:55,200
скоба нула.

710
00:29:55,200 --> 00:29:57,110
Така нулевия символ на низа.

711
00:29:57,110 --> 00:29:57,610
Това е лесно.

712
00:29:57,610 --> 00:30:00,350
Направихме го в крипто
присвояване седмици.

713
00:30:00,350 --> 00:30:05,310
И тогава след като знаете, че на Алис
Писмото е столица, ние можем да се изважда

714
00:30:05,310 --> 00:30:08,160
отстъпка 65 или капитал A себе си,
която ни дава нула.

715
00:30:08,160 --> 00:30:10,940
Така че ние вече знаем, че Alice принадлежи
в населено място нула.

716
00:30:10,940 --> 00:30:14,240
>> И тъй като указател към тези данни
структура, от някакъв вид, колко време

717
00:30:14,240 --> 00:30:18,840
ми отнеме да намерите място
нула в масив?

718
00:30:18,840 --> 00:30:22,080
Само една крачка, нали това е константно време
поради произволен достъп се

719
00:30:22,080 --> 00:30:23,780
планирана е функция на масив.

720
00:30:23,780 --> 00:30:28,570
Така че, накратко, фигуриращ какво индекса
от името на Алис е, което е, в

721
00:30:28,570 --> 00:30:32,610
този случай, е А, или нека просто решаване
че на нула, където В е един и С е

722
00:30:32,610 --> 00:30:34,900
две, смятайки, че от
е константно време.

723
00:30:34,900 --> 00:30:38,510
Просто трябва да погледнем в първата си писмо,
фигуриращ къде нула е

724
00:30:38,510 --> 00:30:40,460
масив е константно време.

725
00:30:40,460 --> 00:30:42,140
Така че технически това е
като две стъпки сега.

726
00:30:42,140 --> 00:30:43,330
Но това все още е постоянна.

727
00:30:43,330 --> 00:30:46,880
Така че ние наричаме тази голяма O на една, така че ние сме
добавя Алиса в тази таблица в

728
00:30:46,880 --> 00:30:48,440
константно време.

729
00:30:48,440 --> 00:30:50,960
>> Но, разбира се, аз съм като
наивна тук, нали?

730
00:30:50,960 --> 00:30:53,240
Какво става, ако има един Аарон в клас?

731
00:30:53,240 --> 00:30:53,990
Или Алисия?

732
00:30:53,990 --> 00:30:57,230
Или някакви други имена като се започне с
A. Къде отиваме да

733
00:30:57,230 --> 00:31:00,800
този човек, нали?

734
00:31:00,800 --> 00:31:03,420
Искам да кажа, в момента има само три
хората на масата, така че може би ние

735
00:31:03,420 --> 00:31:07,490
следва да Aaron в населено място
нула едно две три.

736
00:31:07,490 --> 00:31:09,480
>> Добре, може да доведе до тук.

737
00:31:09,480 --> 00:31:13,350
Но след това, ако се опитаме да вмъкнете David в
този списък, къде David отидете?

738
00:31:13,350 --> 00:31:15,170
Сега нашата система започва да се счупи
надолу, нали?

739
00:31:15,170 --> 00:31:19,210
Защото сега Дейвид завършва тук
ако Aaron всъщност е тук.

740
00:31:19,210 --> 00:31:23,060
И сега цялата тази идея да има
чиста структура от данни, която ни дава

741
00:31:23,060 --> 00:31:28,010
постоянни вмъквания време вече не е
константно време, защото трябва да

742
00:31:28,010 --> 00:31:31,240
проверите, о, по дяволите, някой вече е
на мястото на Алис.

743
00:31:31,240 --> 00:31:35,320
>> Нека сонда останалата част от тези данни
структура, търси място да се сложи

744
00:31:35,320 --> 00:31:37,130
някой като името на Аарон.

745
00:31:37,130 --> 00:31:39,390
И така, това също започва
да линейното време.

746
00:31:39,390 --> 00:31:42,710
Освен това, ако сега искате да намерите
Aaron в тази структура от данни, а вие

747
00:31:42,710 --> 00:31:45,430
проверите, и името на Аарон не е тук.

748
00:31:45,430 --> 00:31:47,960
В идеалния случай, просто ще кажа, Аарон
не в структурата на данните.

749
00:31:47,960 --> 00:31:51,530
Но ако го направите започнете да печелите място за
Аарон, където би трябвало да има един D

750
00:31:51,530 --> 00:31:55,600
или E, вие, най-лошия случай, трябва да се провери
цялата структура на данните, по-

751
00:31:55,600 --> 00:31:59,480
който случай тя преминава в нещо
линейно в рамките на размера на таблицата.

752
00:31:59,480 --> 00:32:00,920
>> Така че, добре, аз ще се определи това.

753
00:32:00,920 --> 00:32:04,200
Проблемът тук е, че трябва
26 елементи в този масив.

754
00:32:04,200 --> 00:32:05,000
Нека да го промените.

755
00:32:05,000 --> 00:32:06,010
Опа.

756
00:32:06,010 --> 00:32:10,600
Нека да го промените така, че вместо да е на
на площ от 26 общо забележите дъното

757
00:32:10,600 --> 00:32:12,720
Индексът ще се промени до п минус 1.

758
00:32:12,720 --> 00:32:16,610
Ако 26 е ясно твърде малък, за хората "
имена, защото има хиляди

759
00:32:16,610 --> 00:32:20,830
имена на света, нека просто да
на 100 или 1000 или 10000.

760
00:32:20,830 --> 00:32:22,960
Нека просто се разпределят много повече пространство.

761
00:32:22,960 --> 00:32:27,230
>> Добре, че не е задължително да намалява
вероятността, че няма да има две

762
00:32:27,230 --> 00:32:31,510
хора с имена започват с А, и
така, че ще се опита да сложи A

763
00:32:31,510 --> 00:32:33,120
имена на местоположението нула неподвижно.

764
00:32:33,120 --> 00:32:36,850
Те все пак ще се сблъскат, които
означава, че ние все още се нуждаят от решение да се сложи

765
00:32:36,850 --> 00:32:41,020
Alice и Аарон и Алисия и други
имена, започващи с A другаде.

766
00:32:41,020 --> 00:32:43,460
Но колко голям проблем е това?

767
00:32:43,460 --> 00:32:46,870
Каква е вероятността, че
има сблъсъци в данните

768
00:32:46,870 --> 00:32:48,240
структура като този?

769
00:32:48,240 --> 00:32:52,570
>> Е, нека да - ще се върнем
на този въпрос тук.

770
00:32:52,570 --> 00:32:55,530
И вижте как да
го реши пръв.

771
00:32:55,530 --> 00:32:58,480
Позволете ми да спра това предложение тук.

772
00:32:58,480 --> 00:33:02,020
Това, което току-що описах е един алгоритъм,
евристичен нарича линейна

773
00:33:02,020 --> 00:33:05,030
сондиране, при която, ако се опитате да вмъкнете
нещо тук, в тези данни

774
00:33:05,030 --> 00:33:08,920
структура, която се нарича хеш таблица,
и няма място там,

775
00:33:08,920 --> 00:33:12,000
наистина сонда за структура на данните
проверка, е това на разположение?

776
00:33:12,000 --> 00:33:13,430
Дали това разположение е това на разположение?

777
00:33:13,430 --> 00:33:13,980
Това е на разположение?

778
00:33:13,980 --> 00:33:17,550
И когато най-накрая е, поставите
името, което първоначално предназначени

779
00:33:17,550 --> 00:33:19,370
другаде на това място.

780
00:33:19,370 --> 00:33:23,360
Но в най-лошия случай, единственото място
може да бъде на дъното на данните

781
00:33:23,360 --> 00:33:25,090
структура, в самия край на масива.

782
00:33:25,090 --> 00:33:30,130
>> Така линейни сондиране, в най-лошия случай,
преминава в линеен алгоритъм, където

783
00:33:30,130 --> 00:33:34,500
Aaron, ако той се случва да се добавя последно
в тази структура от данни, той може да

784
00:33:34,500 --> 00:33:39,540
сблъскат с този първи място, но
след края на лош късмет в самия край.

785
00:33:39,540 --> 00:33:43,940
Така че това не е постоянна
време Светия Граал за нас.

786
00:33:43,940 --> 00:33:47,650
Този подход на вмъкването на елементи в
данни структура, наречена хеш

787
00:33:47,650 --> 00:33:52,050
Таблицата не изглежда да е константно време
поне не в общия случай.

788
00:33:52,050 --> 00:33:54,000
Той може да прехвърли в нещо линейна.

789
00:33:54,000 --> 00:33:56,970
>> И какво, ако ние решаване сблъсъци
малко по-различно?

790
00:33:56,970 --> 00:34:00,740
Така че тук е по-сложен
подход към това, което е все още

791
00:34:00,740 --> 00:34:02,800
наречена хеш таблица.

792
00:34:02,800 --> 00:34:05,890
И от хашиш, като настрана, това, което
Искам да кажа, е индексът, че

793
00:34:05,890 --> 00:34:07,070
I посочена рано.

794
00:34:07,070 --> 00:34:09,810
За да хеш нещо може да бъде
мисли като глагол.

795
00:34:09,810 --> 00:34:13,690
>> Така че, ако хеш Alice е име,
хеш функция, така да се каже,

796
00:34:13,690 --> 00:34:14,710
трябва да се върне редица.

797
00:34:14,710 --> 00:34:18,199
В този случай е равна на нула, ако тя принадлежи на
местоположение нула, едно, ако тя принадлежи на

798
00:34:18,199 --> 00:34:20,000
Местоположение една страна, и така нататък.

799
00:34:20,000 --> 00:34:24,360
Така че моята хеш функция до този момент е било
супер проста, само гледа към

800
00:34:24,360 --> 00:34:26,159
Първата буква в името на някого.

801
00:34:26,159 --> 00:34:29,090
Но хеш функция приема като
въвеждане на някаква част от данните, с

802
00:34:29,090 --> 00:34:30,210
низ, едно цяло число, независимо.

803
00:34:30,210 --> 00:34:32,239
И го изплюва обикновено число.

804
00:34:32,239 --> 00:34:35,739
И това е мястото, където броят на тези данни
елемент принадлежи към структурата на данните

805
00:34:35,739 --> 00:34:37,800
известен тук като хеш таблица.

806
00:34:37,800 --> 00:34:41,400
>> Така че просто интуитивно, това е
малко по-различен контекст.

807
00:34:41,400 --> 00:34:44,170
Това всъщност се позовава на пример
включващи рождени дни, когато е

808
00:34:44,170 --> 00:34:46,850
може да има толкова, колкото
Трийсет и един ден в месеца.

809
00:34:46,850 --> 00:34:52,239
Но какво е това лице да вземе решение за
правят в случай на катастрофа?

810
00:34:52,239 --> 00:34:55,304
Context сега е, а не сблъсък на
имена, но сблъсък на рождени дни,

811
00:34:55,304 --> 00:35:00,760
Ако двама души имат същия рожден ден
2-ри Октомври, например.

812
00:35:00,760 --> 00:35:02,120
>> Студентът: [недоловим].

813
00:35:02,120 --> 00:35:05,010
>> SPEAKER 1: Да, така че тук имаме
на деблокирането на свързани списъци.

814
00:35:05,010 --> 00:35:07,830
Така че изглежда малко по-различно
отколкото ние го привлече по-рано.

815
00:35:07,830 --> 00:35:10,790
Но изглежда, че имат към масив
на лявата страна.

816
00:35:10,790 --> 00:35:13,230
Това е един форум, за не
конкретна причина.

817
00:35:13,230 --> 00:35:14,630
Но тя все още е масив.

818
00:35:14,630 --> 00:35:16,160
Това е масив от указатели.

819
00:35:16,160 --> 00:35:20,670
И всеки от тези елементи, всеки от
тези кръгове или наклонени черти - наклонената черта

820
00:35:20,670 --> 00:35:23,970
представлява нищожна - всяка една от тези
указатели е очевидно, сочещи към

821
00:35:23,970 --> 00:35:25,730
какви данни структура?

822
00:35:25,730 --> 00:35:26,890
A свързан списък.

823
00:35:26,890 --> 00:35:30,530
>> Така че сега ние сме в състояние да
твърд код в нашата програма

824
00:35:30,530 --> 00:35:32,010
размера на таблицата.

825
00:35:32,010 --> 00:35:35,360
В този случай, знаем, че никога не е
повече от 31 дни в месеца.

826
00:35:35,360 --> 00:35:38,480
Толкова е трудно кодиране на стойност, като 31 е
разумно в този контекст.

827
00:35:38,480 --> 00:35:42,700
В контекста на имената трудно кодиране
26 не е неразумно хората

828
00:35:42,700 --> 00:35:46,340
имената само начало, например,
азбуката, включващи до Z.

829
00:35:46,340 --> 00:35:50,180
>> Ние можем да се тъпча всички тях в тези данни
структура, доколкото, когато получите

830
00:35:50,180 --> 00:35:55,330
сблъсък, ние не поставяме имената тук,
ние, вместо да мислят за тези клетки

831
00:35:55,330 --> 00:36:00,270
не като низове самите, а като
указатели към, например, Алис.

832
00:36:00,270 --> 00:36:03,660
И тогава Алис може да има друг показалеца
за друго име започва с

833
00:36:03,660 --> 00:36:06,150
A. И Боб всъщност става тук.

834
00:36:06,150 --> 00:36:10,850
>> И ако има друго име започва
с B, той завършва тук.

835
00:36:10,850 --> 00:36:15,070
И така, всеки от елементите на тази
масата две, ако ние създадохме този на

836
00:36:15,070 --> 00:36:17,350
малко по-хитро -

837
00:36:17,350 --> 00:36:18,125
хайде -

838
00:36:18,125 --> 00:36:22,950
ако ние създадохме това малко по-
хитро, сега става адаптивен данни

839
00:36:22,950 --> 00:36:27,720
структура, където няма твърда граница
от това колко елементи можете да вмъкнете

840
00:36:27,720 --> 00:36:30,700
в него, защото ако имате
сблъсък, това е добре.

841
00:36:30,700 --> 00:36:34,690
Просто върви напред и да го приложи към
това, което видяхме преди малко беше

842
00:36:34,690 --> 00:36:38,290
известен като свързан списък.

843
00:36:38,290 --> 00:36:39,690
>> Ами нека да пауза за момент.

844
00:36:39,690 --> 00:36:42,570
Каква е вероятността от сблъсък
на първо място?

845
00:36:42,570 --> 00:36:45,480
Добре, може би аз съм над мисли, може би
Аз съм над инженеринг този проблем,

846
00:36:45,480 --> 00:36:46,370
защото знаеш ли какво?

847
00:36:46,370 --> 00:36:49,070
Да, мога да излезе с произволна
примери разстояние от върха на главата ми като

848
00:36:49,070 --> 00:36:52,870
Allison и Аарон, но в действителност,
даден равномерно разпределение на

849
00:36:52,870 --> 00:36:56,990
входове, тоест някои случайни вмъквания
в структурата на данните, това, което наистина е

850
00:36:56,990 --> 00:36:58,580
вероятността за сблъсък?

851
00:36:58,580 --> 00:37:01,670
Ами оказва се, че всъщност
супер висока.

852
00:37:01,670 --> 00:37:03,850
Нека обобщим това
Проблемът е в това.

853
00:37:03,850 --> 00:37:08,890
>> Така в една стая на п CS50 учениците, какъв е
вероятността, че най-малко

854
00:37:08,890 --> 00:37:11,010
двама студенти в стаята
имат същия рожден ден?

855
00:37:11,010 --> 00:37:13,346
Така че има какво. няколко Hund -

856
00:37:13,346 --> 00:37:16,790
200, 300 хора тук и няколко
сто хора у дома днес.

857
00:37:16,790 --> 00:37:20,670
Така че, ако искате да се питаме какво е
вероятността от двама души

858
00:37:20,670 --> 00:37:23,930
В тази стая има същия рожден ден,
можем да разберем това.

859
00:37:23,930 --> 00:37:26,250
И аз твърдя, всъщност има два
хора със същия рожден ден.

860
00:37:26,250 --> 00:37:29,560
>> Например, има ли някой
има рожден ден днес?

861
00:37:29,560 --> 00:37:31,340
Вчера?

862
00:37:31,340 --> 00:37:32,590
Утре?

863
00:37:32,590 --> 00:37:35,980
Добре, така че тя се чувства като аз ще
да трябва да го правиш 363 или така по-

864
00:37:35,980 --> 00:37:39,500
пъти, за да разбера всъщност
ако имаме сблъсък.

865
00:37:39,500 --> 00:37:42,350
Или можем да го направим математически
а не досадно

866
00:37:42,350 --> 00:37:43,200
прави това.

867
00:37:43,200 --> 00:37:44,500
И предложа следното.

868
00:37:44,500 --> 00:37:48,740
>> Така че аз предлагам да може да се моделира
вероятността от двама души, имащи

869
00:37:48,740 --> 00:37:55,320
същия рожден ден като вероятността от 1
минус вероятността от никой като

870
00:37:55,320 --> 00:37:56,290
същия рожден ден.

871
00:37:56,290 --> 00:37:59,960
Така че да се получи това, и това е само
луксозен начин на писане на тази, за

872
00:37:59,960 --> 00:38:03,090
първият човек в стаята, той или тя
може да има всяка една от възможните

873
00:38:03,090 --> 00:38:07,370
рождени дни поема 365 дни в годината,
с извинения към хората с

874
00:38:07,370 --> 00:38:08,760
на 29 февруари рожден ден.

875
00:38:08,760 --> 00:38:13,470
>> Така че първият човек в тази зала е безплатно
да има произволен брой рождени дни

876
00:38:13,470 --> 00:38:18,280
от 365 възможности, така че
ние ще го направя 365, разделена на 365,

877
00:38:18,280 --> 00:38:18,990
който е един.

878
00:38:18,990 --> 00:38:22,700
Следващият човек в стаята, ако целта
е да се избегне сблъсък, може само

879
00:38:22,700 --> 00:38:26,460
има свой рожден ден за това как
много различни възможни дни?

880
00:38:26,460 --> 00:38:27,610
364.

881
00:38:27,610 --> 00:38:31,430
Така че втори мандат в този израз е
по същество това, че математиката за нас

882
00:38:31,430 --> 00:38:33,460
като се извади от един възможен ден.

883
00:38:33,460 --> 00:38:36,390
И след това на следващия ден, на следващия ден
следващия ден до общия брой

884
00:38:36,390 --> 00:38:38,100
на хората в залата.

885
00:38:38,100 --> 00:38:41,290
>> И ако след това помисли, какво тогава е
вероятността не на всеки да има

886
00:38:41,290 --> 00:38:45,265
уникални рождени дни, но отново един минус
че, това, което получаваме, е израз

887
00:38:45,265 --> 00:38:47,810
че може много fancifully
изглежда така.

888
00:38:47,810 --> 00:38:50,330
Но това е по-интересно
да погледнете визуално.

889
00:38:50,330 --> 00:38:55,120
Това е диаграма, където по оста х е
на броя на хората в помещението,

890
00:38:55,120 --> 00:38:56,180
броя на рождени дни.

891
00:38:56,180 --> 00:38:59,840
На ординатата е вероятността
от евентуален сблъсък, двама души

892
00:38:59,840 --> 00:39:01,230
със същия рожден ден.

893
00:39:01,230 --> 00:39:05,020
>> И на храна за вкъщи от тази крива е
че веднага след като стигнете до искал 40

894
00:39:05,020 --> 00:39:11,110
студенти, ти си на 90% вероятност
combinatorically на две

895
00:39:11,110 --> 00:39:13,550
или повече души имат
същия рожден ден.

896
00:39:13,550 --> 00:39:18,600
И след като стигна до 58 души като това е
почти 100% от шанс на две

897
00:39:18,600 --> 00:39:21,310
хората в залата ще имат
същия рожден ден, макар няма

898
00:39:21,310 --> 00:39:26,650
365 или 366 възможни кофи, и
само 58 души в залата.

899
00:39:26,650 --> 00:39:29,900
Просто статистически е по-вероятно да
получите сблъсъци, които в краткосрочен

900
00:39:29,900 --> 00:39:31,810
мотивира тази дискусия.

901
00:39:31,810 --> 00:39:35,890
Че дори да получите фантазия тук, и
започна като тези вериги, все още сме

902
00:39:35,890 --> 00:39:36,950
ще има сблъсъци.

903
00:39:36,950 --> 00:39:42,710
>> Така че това повдига въпроса, каква е
разходите за правене на вмъквания и заличавания

904
00:39:42,710 --> 00:39:44,850
в структурата на данните, подобен на този?

905
00:39:44,850 --> 00:39:46,630
Ами нека да предложи -

906
00:39:46,630 --> 00:39:51,570
и да се върна към екрана над
тук - ако сме п елементи в

907
00:39:51,570 --> 00:39:56,330
списък, така че ако се опитваме да вмъкнете
п елементи, а ние имаме

908
00:39:56,330 --> 00:39:58,050
Колко общо кофи?

909
00:39:58,050 --> 00:40:03,450
Да речем, 31 общо кофи
в случай на рождени дни.

910
00:40:03,450 --> 00:40:09,240
Каква е максималната дължина на един
на тези вериги потенциално?

911
00:40:09,240 --> 00:40:12,670
>> Ако отново има 31 възможни
Рождени дни в даден месец.

912
00:40:12,670 --> 00:40:14,580
И ние просто бучки всички -

913
00:40:14,580 --> 00:40:15,580
всъщност това е един глупав пример.

914
00:40:15,580 --> 00:40:16,960
Да го направим 26 вместо.

915
00:40:16,960 --> 00:40:20,890
Така че, ако действително има хора, чиито имена
Започнете с по Z, като по този начин

916
00:40:20,890 --> 00:40:22,780
26 възможности за нас.

917
00:40:22,780 --> 00:40:25,920
И ние сме с помощта на структурата на данните като
на един току-що видяхме, като имаме

918
00:40:25,920 --> 00:40:30,210
масив от указатели, всеки от които
точки в свързан списък, когато

919
00:40:30,210 --> 00:40:32,360
Първият списък е всеки
с името Alice.

920
00:40:32,360 --> 00:40:35,770
Вторият списък е всеки с
име, започващо с, като се започва

921
00:40:35,770 --> 00:40:36,980
с В, и така нататък.

922
00:40:36,980 --> 00:40:41,020
>> Какво е най-вероятно дължината на всеки от
тези списъци, ако приемем, хубава чиста

923
00:40:41,020 --> 00:40:45,410
разпределение на имена от А до Z
в цялата структура на данните?

924
00:40:45,410 --> 00:40:50,210
Има н хора в структурата на данните
разделена на 26, ако са добре

925
00:40:50,210 --> 00:40:52,110
разпределят в течение на целия
структурата на данните.

926
00:40:52,110 --> 00:40:54,970
Така дължината на всеки един от тези
вериги е М, разделена на 26.

927
00:40:54,970 --> 00:40:57,380
Но в голяма нотация O, какво е това?

928
00:40:57,380 --> 00:41:00,100

929
00:41:00,100 --> 00:41:02,440
Какво е това наистина?

930
00:41:02,440 --> 00:41:04,150
Така че това е наистина само N, нали?

931
00:41:04,150 --> 00:41:06,620
Защото казахме в миналото,
уф, че сте се разделят с 26.

932
00:41:06,620 --> 00:41:08,710
Да, в действителност то е по-бързо.

933
00:41:08,710 --> 00:41:12,720
Но на теория, това не е фундаментално
всичко, което по-бързо.

934
00:41:12,720 --> 00:41:16,040
>> Така че ние не изглежда да е чак толкова много
по-близо до тази Светия Граал.

935
00:41:16,040 --> 00:41:17,750
В действителност, това е само линейно време.

936
00:41:17,750 --> 00:41:20,790
По дяволите, в този момент, защо да не правим
просто използвайте един огромен свързан списък?

937
00:41:20,790 --> 00:41:23,510
Защо не просто използвайте един огромен
масив за съхранение на имената на

938
00:41:23,510 --> 00:41:25,010
всички в залата?

939
00:41:25,010 --> 00:41:28,280
Е, има ли още нещо
непреодолими за хеш-таблица?

940
00:41:28,280 --> 00:41:30,810
Има ли все още нещо завладяващо
за структурата на данните

941
00:41:30,810 --> 00:41:33,940
който изглежда така?

942
00:41:33,940 --> 00:41:35,182
Това.

943
00:41:35,182 --> 00:41:37,050
>> Студентът: [недоловим].

944
00:41:37,050 --> 00:41:39,840
>> SPEAKER 1: Да, и отново, ако това е просто
линеен алгоритъм време, и

945
00:41:39,840 --> 00:41:42,780
линейното време структурата на данните, защо да не правя
просто съхранява името на всички в един голям

946
00:41:42,780 --> 00:41:44,210
масив, или в голям свързан списък?

947
00:41:44,210 --> 00:41:47,010
И престани да направи CS така много по-трудно
, отколкото трябва да бъде?

948
00:41:47,010 --> 00:41:49,600

949
00:41:49,600 --> 00:41:53,190
Какво е убедителна за това, дори
въпреки че аз го надраска?

950
00:41:53,190 --> 00:41:54,930
>> Студентът: [недоловим].

951
00:41:54,930 --> 00:41:57,040
>> SPEAKER 1: вмъквания, не са?

952
00:41:57,040 --> 00:41:58,140
Expensive вече.

953
00:41:58,140 --> 00:42:03,390
Така вмъквания потенциално биха могли все още
бъде постоянна време, дори и ако вашите данни

954
00:42:03,390 --> 00:42:07,910
структура изглежда така, множество
указатели, всяка от които е насочена към

955
00:42:07,910 --> 00:42:09,550
потенциално свързан списък.

956
00:42:09,550 --> 00:42:15,220
Как може да се постигне постоянен
време вмъкване на имена?

957
00:42:15,220 --> 00:42:16,280
Придържайте се в предната част, нали?

958
00:42:16,280 --> 00:42:19,290
>> Ако жертваме гол дизайн от
по-рано, когато искаме да запазим

959
00:42:19,290 --> 00:42:22,650
името на всички, например, подредени,
или всички номера на сцената подредени,

960
00:42:22,650 --> 00:42:25,020
Предполагам, че имаме
несортиран свързан списък.

961
00:42:25,020 --> 00:42:29,960
Тя само ни струва една или две стъпки,
като в случай на Бен и Brian

962
00:42:29,960 --> 00:42:32,750
по-рано, за да вмъкнете елемент в
началото на списъка.

963
00:42:32,750 --> 00:42:36,090
Така че, ако ние не се грижи за сортиране на всички
на имена, започващи с А или всички

964
00:42:36,090 --> 00:42:39,660
имената, започващи с B, все още можем да
постигане на постоянно поставяне време.

965
00:42:39,660 --> 00:42:43,900
Сега гледам Алис или Боб или всяко име
по-общ план е все още какво?

966
00:42:43,900 --> 00:42:48,100
Това е голям О п разделена на 26, в
идеален случай, когато всички са еднакво

967
00:42:48,100 --> 00:42:51,190
разпределени, където има най-много на А
като има Z, която е вероятно

968
00:42:51,190 --> 00:42:52,220
нереалистично.

969
00:42:52,220 --> 00:42:53,880
Но това все още е линейна.

970
00:42:53,880 --> 00:42:57,120
>> Но тук, ние се връщаме към точка
от асимптотичната нотация е

971
00:42:57,120 --> 00:42:58,600
теоретично вярно.

972
00:42:58,600 --> 00:43:02,960
Но в реалния свят, ако се твърди, че
моята програма може да направи нещо 26 пъти

973
00:43:02,960 --> 00:43:06,210
по-бързо от твоя, чиято програма
отиваш предпочиташе да използвате?

974
00:43:06,210 --> 00:43:09,660
Yours или мина, която
е 26 пъти по-бързо?

975
00:43:09,660 --> 00:43:14,320
Реално, на лицето, чиято е 26
пъти по-бързо, дори ако теоретично

976
00:43:14,320 --> 00:43:18,790
алгоритмите ни тече в една и съща
асимптотичната времето за работа.

977
00:43:18,790 --> 00:43:20,940
>> Нека да предложи различен
разтвор напълно.

978
00:43:20,940 --> 00:43:24,380
И ако това не ви оставят без дъх,
Че ние сме извън структурите от данни.

979
00:43:24,380 --> 00:43:27,420
Така че това е Trie -

980
00:43:27,420 --> 00:43:28,520
Що за глупаво име.

981
00:43:28,520 --> 00:43:32,880
Тя идва от извличането на данни, а думата
е написан Trie, т-р-е-е, защото на

982
00:43:32,880 --> 00:43:34,450
Разбира извличане звучи като Trie.

983
00:43:34,450 --> 00:43:36,580
Но това е история
на думата Trie.

984
00:43:36,580 --> 00:43:40,980
>> Така Trie е наистина някаква дърво,
и тя също е игра на тази дума.

985
00:43:40,980 --> 00:43:46,330
И въпреки че не мога да си го видите
с тази визуализация, а Trie е

986
00:43:46,330 --> 00:43:50,790
дърво структурира, като родословно дърво с
един прародител в горната и много

987
00:43:50,790 --> 00:43:54,530
на внуци и правнуци
като оставя на дъното.

988
00:43:54,530 --> 00:43:58,100
Но всеки възел в Trie е масив.

989
00:43:58,100 --> 00:44:00,680
И това е в масив - и нека
свръхопростяването за момент - това е

990
00:44:00,680 --> 00:44:04,600
масив, в този случай, с размер 26, когато
всеки възел отново е масив от размера

991
00:44:04,600 --> 00:44:09,000
26, когато нулевия елемент с това, че
масив представлява, а последният

992
00:44:09,000 --> 00:44:11,810
елемент за всяка такава
масив представлява Z.

993
00:44:11,810 --> 00:44:15,520
>> Така че аз предлагам, а след това, че тези данни
структура, известна като Trie, може да бъде

994
00:44:15,520 --> 00:44:17,600
използва и за съхраняване на думи.

995
00:44:17,600 --> 00:44:21,740
Ние видяхме преди малко, как бихме могли да се съхранява
думи, или в този случай имената и ние

996
00:44:21,740 --> 00:44:25,440
видяхме по-рано как ние може да съхранява числа,
но ако ние се фокусираме върху имената или низове

997
00:44:25,440 --> 00:44:27,460
тук, забележете, което е интересно.

998
00:44:27,460 --> 00:44:32,210
Аз твърдя, че името Максуел е
вътрешността на структурата на данните.

999
00:44:32,210 --> 00:44:33,730
Къде виждате Maxwell?

1000
00:44:33,730 --> 00:44:35,140
>> Студентът: [недоловим].

1001
00:44:35,140 --> 00:44:36,240
>> SPEAKER 1: От лявата.

1002
00:44:36,240 --> 00:44:39,910
Така че това, което е интересно с тези данни
структура е по-скоро от магазин на

1003
00:44:39,910 --> 00:44:46,200
низ M-A-X-W-E-L-L наклонена черта нулеви, цялото
Последователно, какво да го правим

1004
00:44:46,200 --> 00:44:46,890
следи.

1005
00:44:46,890 --> 00:44:50,510
Ако това е Trie като структура на данните,
всеки един от които възли отново е масив,

1006
00:44:50,510 --> 00:44:54,650
и искате да съхранявате Maxwell, първо
индекс и така основата на възела, така че

1007
00:44:54,650 --> 00:44:57,810
да се каже, най-горната възел,
в населено място M, нали, така че

1008
00:44:57,810 --> 00:44:59,160
приблизително в средата.

1009
00:44:59,160 --> 00:45:03,740
И след това от там, следват
показалеца на дете възли, така да се каже.

1010
00:45:03,740 --> 00:45:06,150
Така че, в смисъл, родословно дърво,
го следват надолу.

1011
00:45:06,150 --> 00:45:09,030
И това да ви доведе до друг възел
в ляво там, който е

1012
00:45:09,030 --> 00:45:10,540
просто друг масив.

1013
00:45:10,540 --> 00:45:14,710
>> И след това, ако искате да съхранявате Maxwell,
ли, че показалецът, който представлява

1014
00:45:14,710 --> 00:45:16,430
A, който е този тук.

1015
00:45:16,430 --> 00:45:17,840
След това можете да преминете към следващото възел.

1016
00:45:17,840 --> 00:45:20,100
И забележете - това е защо на картината
малко измамна -

1017
00:45:20,100 --> 00:45:21,990
този възел изглежда супер малка.

1018
00:45:21,990 --> 00:45:26,050
Но правото на това е Y и Z.
Това е просто авторът е пресечен на

1019
00:45:26,050 --> 00:45:27,630
картината, така че всъщност
виждаме нещата.

1020
00:45:27,630 --> 00:45:30,400
В противен случай тази снимка
ще бъде изключително широк.

1021
00:45:30,400 --> 00:45:36,180
Така че сега вие индекс в населено място X, а след това
W, E Тогава, след това L, тогава L. Тогава какъв е

1022
00:45:36,180 --> 00:45:37,380
това любопитство?

1023
00:45:37,380 --> 00:45:41,250
>> Е, ако ние използваме този вид на новия
предприемат за съхранение на низ в

1024
00:45:41,250 --> 00:45:44,500
структурата на данните, все още трябва да
същество отмятате в данните

1025
00:45:44,500 --> 00:45:47,250
структура, която дума свършва тук.

1026
00:45:47,250 --> 00:45:50,830
С други думи, всеки един от тези възли
по някакъв начин трябва да се помни, че ние

1027
00:45:50,830 --> 00:45:53,500
всъщност след всички тези указатели
и се оставя малко

1028
00:45:53,500 --> 00:45:58,370
троха хляб в долната тук на тази
структура, за да покаже, M-A-X-W-E-L-L е

1029
00:45:58,370 --> 00:46:00,230
Всъщност в тази структура от данни.

1030
00:46:00,230 --> 00:46:02,040
>> Така че бихме могли да направите това, както следва.

1031
00:46:02,040 --> 00:46:06,810
Всеки от възлите в картината ние просто
трион има един, масив с размер 27.

1032
00:46:06,810 --> 00:46:10,550
И това е вече 27, защото в БКП определени шест,
ние всъщност ще ви дам един апостроф,

1033
00:46:10,550 --> 00:46:13,590
така че ние можем да имаме имена като O'Reilly
и други с апострофи.

1034
00:46:13,590 --> 00:46:14,820
Но една и съща идея.

1035
00:46:14,820 --> 00:46:17,710
Всеки един от тези елементи в
масиви сочи към структура

1036
00:46:17,710 --> 00:46:19,320
възел, така че само един възел.

1037
00:46:19,320 --> 00:46:21,430
Така че това е много напомня
на нашата свързан списък.

1038
00:46:21,430 --> 00:46:24,550
>> И след това имам Boolean, която аз ще
обадете дума, която е просто ще бъде

1039
00:46:24,550 --> 00:46:29,120
вярно, ако една дума завърши този
възел в дървото.

1040
00:46:29,120 --> 00:46:32,870
Той ефективно представлява малко
триъгълник видяхме преди малко.

1041
00:46:32,870 --> 00:46:37,190
Така че, ако думата завършва на този възел в
дървото, така че областта думата ще бъде вярно,

1042
00:46:37,190 --> 00:46:41,990
която е концептуално отмятане, или
ние рисувате този триъгълник, да има

1043
00:46:41,990 --> 00:46:44,080
е дума тук.

1044
00:46:44,080 --> 00:46:45,120
>> Така че това е Trie.

1045
00:46:45,120 --> 00:46:48,540
И сега въпросът е, какво
е неговото време на работа?

1046
00:46:48,540 --> 00:46:49,930
Дали е голям O на п?

1047
00:46:49,930 --> 00:46:51,410
Може ли нещо друго?

1048
00:46:51,410 --> 00:46:57,330
Е, ако сте п имена в тези данни
структура, Максуел е само един от

1049
00:46:57,330 --> 00:47:02,330
тях, какво е времето за работа на
поставяте или намиране на Максуел?

1050
00:47:02,330 --> 00:47:06,230

1051
00:47:06,230 --> 00:47:09,050
Какво е времето за работа
вмъкване на Максуел?

1052
00:47:09,050 --> 00:47:11,740
Ако има п други имена
вече в таблицата?

1053
00:47:11,740 --> 00:47:12,507
Да?

1054
00:47:12,507 --> 00:47:15,429
>> Студентът: [недоловим].

1055
00:47:15,429 --> 00:47:17,550
>> SPEAKER 1: Да, това е дължината
на име, нали?

1056
00:47:17,550 --> 00:47:24,420
Така M-а-х-w-е-л-л така тя се чувства като това
алгоритъм е голяма O на седем.

1057
00:47:24,420 --> 00:47:26,580
Сега, разбира се, името
ще варират по дължина.

1058
00:47:26,580 --> 00:47:27,380
Може би това е кратко име.

1059
00:47:27,380 --> 00:47:28,600
Може би това е по-дълго име.

1060
00:47:28,600 --> 00:47:33,390
Но това, което е ключът тук е, че
това е постоянно число.

1061
00:47:33,390 --> 00:47:36,810
И може би това не е наистина константа,
но Бог, ако реалистично, в

1062
00:47:36,810 --> 00:47:41,570
речник, вероятно има някаква граница
от броя на буквите в

1063
00:47:41,570 --> 00:47:43,820
лице име в дадена страна.

1064
00:47:43,820 --> 00:47:46,940
>> И така, можем да предположим, че
стойност е константа.

1065
00:47:46,940 --> 00:47:47,750
Аз не знам какво е то.

1066
00:47:47,750 --> 00:47:50,440
Това е може би по-голям от
ние смятаме, че е така.

1067
00:47:50,440 --> 00:47:52,720
Защото винаги има някой ъгъл
случай с един луд дълго име.

1068
00:47:52,720 --> 00:47:56,360
Така че, нека го наречем к, но тя все още е
постоянна вероятно, защото всеки

1069
00:47:56,360 --> 00:48:00,190
име в света, най-малко в
определена страна, е, че дължината или

1070
00:48:00,190 --> 00:48:01,780
по-кратък, така че това е постоянна.

1071
00:48:01,780 --> 00:48:04,490
Но когато съм казал нещо е голям
O на постоянна стойност, какво е това

1072
00:48:04,490 --> 00:48:07,760
Наистина еквивалентни?

1073
00:48:07,760 --> 00:48:10,420
Това е наистина едно и също нещо
както казва константно време.

1074
00:48:10,420 --> 00:48:11,530
>> Сега сме вид измама, нали?

1075
00:48:11,530 --> 00:48:15,340
Ние сме вид привличане някои теория
тук, за да се каже, че добре, за да е на к

1076
00:48:15,340 --> 00:48:17,450
наистина просто порядъка на една,
и това е константно време.

1077
00:48:17,450 --> 00:48:18,200
Но това наистина е така.

1078
00:48:18,200 --> 00:48:22,550
Тъй като ключовата поглед тук е, че
ако сме п имена вече в тази

1079
00:48:22,550 --> 00:48:26,010
структурата на данните, и ние вложка Maxwell,
е количеството време, което ни води до

1080
00:48:26,010 --> 00:48:29,530
вмъкнете Maxwell е засегнато
от колко други хора

1081
00:48:29,530 --> 00:48:31,100
са в структурата на данните?

1082
00:48:31,100 --> 00:48:31,670
Не изглежда да бъде.

1083
00:48:31,670 --> 00:48:36,280
Ако имах един милиард повече елементи на настоящата
Trie, а след това поставете Максуел, е

1084
00:48:36,280 --> 00:48:38,650
той е засегнато?

1085
00:48:38,650 --> 00:48:39,050
Не.

1086
00:48:39,050 --> 00:48:42,950
И това е, за разлика от някои от ден на данни
структури, които сме виждали до този момент, когато

1087
00:48:42,950 --> 00:48:46,820
времето за работа на вашия алгоритъм е
напълно независимо от това колко

1088
00:48:46,820 --> 00:48:51,430
неща е или не е вече
с това, че структурата на данните.

1089
00:48:51,430 --> 00:48:54,650
>> И така с това дава сега е
възможност за р набор шест, което ще

1090
00:48:54,650 --> 00:48:58,310
отново включва прилагане свой собствен
проверка на правопис, четене в 150000

1091
00:48:58,310 --> 00:49:01,050
думи, как най-добре да се съхранява, че
не е задължително очевидна.

1092
00:49:01,050 --> 00:49:04,030
И въпреки, че съм поставила за цел да намери
Светия Граал, не искам

1093
00:49:04,030 --> 00:49:05,330
твърдят, че е Trie.

1094
00:49:05,330 --> 00:49:09,810
В действителност, хеш таблица може много добре
да се окаже много по-ефективно.

1095
00:49:09,810 --> 00:49:10,830
Но това са само -

1096
00:49:10,830 --> 00:49:14,620
това е само една от дизайнерските решения
ще трябва да се направи.

1097
00:49:14,620 --> 00:49:18,920
>> Но в затваряне нека вземем 50 или така
секунди, за да вземе един поглед на това, което се намира

1098
00:49:18,920 --> 00:49:22,190
напред следващата седмица и след това ние прехода
от този команден ред

1099
00:49:22,190 --> 00:49:26,220
свят, ако C програми за неща Мрежата
основава и езици като PHP и

1100
00:49:26,220 --> 00:49:30,350
JavaScript и самият интернет,
като протоколите HTTP, до която сте

1101
00:49:30,350 --> 00:49:32,870
приема за даденост за година
сега, и печатен почти всеки

1102
00:49:32,870 --> 00:49:34,440
ден, може би, или наблюдавани.

1103
00:49:34,440 --> 00:49:37,420
И ние ще започнем да Обелете
слоеве на това, което е в интернет.

1104
00:49:37,420 --> 00:49:40,650
И това, което е кодът, който
лежи в основата на днешните средства.

1105
00:49:40,650 --> 00:49:43,230
Така 50 секунди на тази закачка тук.

1106
00:49:43,230 --> 00:49:46,570
Аз ви давам Warriors на мрежата.

1107
00:49:46,570 --> 00:49:51,370
>> [VIDEO PLAYBACK]

1108
00:49:51,370 --> 00:49:56,764
>> -Той дойде с послание.

1109
00:49:56,764 --> 00:50:00,687
С протокол всичките свои.

1110
00:50:00,687 --> 00:50:13,370

1111
00:50:13,370 --> 00:50:19,780
Той дойде в един свят на жестоки защитни стени,
незаинтересовани рутери, и опасностите, далеч

1112
00:50:19,780 --> 00:50:22,600
по-лошо от смъртта.

1113
00:50:22,600 --> 00:50:23,590
Той е бърз.

1114
00:50:23,590 --> 00:50:25,300
Той е силен.

1115
00:50:25,300 --> 00:50:27,700
Той е TCPIP.

1116
00:50:27,700 --> 00:50:30,420
И той има адреса си.

1117
00:50:30,420 --> 00:50:32,920

1118
00:50:32,920 --> 00:50:34,590
Warriors на мрежата.

1119
00:50:34,590 --> 00:50:35,290
>> [END възпроизвеждане на видео]

1120
00:50:35,290 --> 00:50:38,070
>> SPEAKER 1: Това е начина, по интернет
работят от следващата седмица.

1121
00:50:38,070 --> 00:50:40,406