1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Недеља 6]

2
00:00:02,000 --> 00:00:04,000
[Давид Ј. Малан] [Универзитет Харвард]

3
00:00:04,000 --> 00:00:08,000
[Ово је ЦС50.] [ЦС50.ТВ]

4
00:00:08,000 --> 00:00:12,000
>> Ово је ЦС50, и то је почетак недеље 6,

5
00:00:12,000 --> 00:00:16,000
па пар нових алата су сада доступни за вас да искористите,

6
00:00:16,000 --> 00:00:19,000
први који се зове ЦС50 Стиле.

7
00:00:19,000 --> 00:00:22,000
Шансе су, ако сте попут мене или било наставних момци,

8
00:00:22,000 --> 00:00:26,000
Вероватно сте видели програм чији стил изгледа мало несто овако.

9
00:00:26,000 --> 00:00:30,000
Можда почнете сечење неке углове касно ноћу, или ћете се бавити касније,

10
00:00:30,000 --> 00:00:32,000
и онда ТФ или ЦА долази преко у току радног времена.

11
00:00:32,000 --> 00:00:34,000
Онда је тешко за нас да чита.

12
00:00:34,000 --> 00:00:38,000
Па, овај код је синтаксно исправна, а то ће компајлирати, и то је заправо ће се покренути.

13
00:00:38,000 --> 00:00:40,000
Али то дефинитивно није 5 за стил.

14
00:00:40,000 --> 00:00:45,000
>> Али сада, ако идемо у овај директоријум овде-

15
00:00:45,000 --> 00:00:48,000
и приметио да имам цондитионс2.ц-

16
00:00:48,000 --> 00:00:55,000
и ја покренули ову нову команду, стиле50, на овом датотеке цондитионс2.ц, Ентер,

17
00:00:55,000 --> 00:00:57,000
приметити да ме је обавестио да је било стилизована.

18
00:00:57,000 --> 00:01:00,000
Гедит приметили да датотека је промењена на диску,

19
00:01:00,000 --> 00:01:08,000
и ако сам дугме релоад, сви ваши проблеми су сада аутоматизован.

20
00:01:08,000 --> 00:01:15,000
[Аплауз]

21
00:01:15,000 --> 00:01:17,000
То је једна од ствари које смо радили овај викенд.

22
00:01:17,000 --> 00:01:20,000
Схватите да је несавршена јер постоје неки код

23
00:01:20,000 --> 00:01:23,000
да једноставно неће бити у стању да савршено стилизовати,

24
00:01:23,000 --> 00:01:26,000
али схватите ово је сада алатка коју можете да искористите

25
00:01:26,000 --> 00:01:33,000
ако је само да се очисти неке од еррантли ставља заграда и слично.

26
00:01:33,000 --> 00:01:36,000
>> Али више убедљив сада је ЦС50 хотела.

27
00:01:36,000 --> 00:01:39,000
Са ЦС50 потврду, можете заправо обављају исте тестове исправност

28
00:01:39,000 --> 00:01:42,000
на свом коду да наставе момци су у стању да.

29
00:01:42,000 --> 00:01:44,000
Ово је командна линија услужни програм који долази сада у апарату

30
00:01:44,000 --> 00:01:46,000
чим ураде упдате50 као по

31
00:01:46,000 --> 00:01:49,000
псет 4 спецификације, и ви га користите у суштини овако.

32
00:01:49,000 --> 00:01:51,000
Трчиш командне цхецк50.

33
00:01:51,000 --> 00:01:56,000
Онда сте проћи у аргумент командне линије, или више опште познат као прекидач или заставу.

34
00:01:56,000 --> 00:01:58,000
Генерално, ствари које имају цртице зову прекидач

35
00:01:58,000 --> 00:02:02,000
за програм командне линије, тако ц прецизира

36
00:02:02,000 --> 00:02:04,000
провере које желите да покренете.

37
00:02:04,000 --> 00:02:07,000
>> Тестови које желите да покренете идентификовани су јединствено овом низу,

38
00:02:07,000 --> 00:02:10,000
2012/псет4/ресизе.

39
00:02:10,000 --> 00:02:13,000
Другим речима, то је само произвољан али је јединствено ниска

40
00:02:13,000 --> 00:02:18,000
које користимо за јединствену идентификацију тестове псет 4 је исправност.

41
00:02:18,000 --> 00:02:21,000
А онда одредите простор одвојен листу датотека које желите да поставите

42
00:02:21,000 --> 00:02:24,000
да ЦС50 Провери за анализу.

43
00:02:24,000 --> 00:02:29,000
На пример, ако ја одем у мом решењу овде ресизе.ц-

44
00:02:29,000 --> 00:02:31,000
дозволите ми да отворим прозор већи терминал-

45
00:02:31,000 --> 00:02:42,000
и ја напред и покрените рецимо цхецк50 ц 2012/псет4/ресизе,

46
00:02:42,000 --> 00:02:46,000
и онда ићи напред и навести имена датотека,

47
00:02:46,000 --> 00:02:49,000
ресизе.ц, а затим притисните Ентер, он сабија,

48
00:02:49,000 --> 00:02:53,000
она постављено, проверава, а ја сам успео гомилу тестова.

49
00:02:53,000 --> 00:02:59,000
Један у црвеном у горњем левом углу каже да ресизе.ц и БМП постоје.

50
00:02:59,000 --> 00:03:01,000
То је био тест. То је питање које смо питали.

51
00:03:01,000 --> 00:03:04,000
И то је несрећан, јер одговор је био лажан.

52
00:03:04,000 --> 00:03:08,000
Бели текст испод ње очекује каже бмп.х да постоји, а то је једноставно моја кривица.

53
00:03:08,000 --> 00:03:11,000
Заборавила сам да га постави, па морам да уплоад обе датотеке,

54
00:03:11,000 --> 00:03:14,000
ресизе.ц и бмп.х.

55
00:03:14,000 --> 00:03:17,000
Али сада приметите све друге тестове су у жуто, јер нису покренути,

56
00:03:17,000 --> 00:03:21,000
па насмејано лице је вертикална јер је није ни срећан ни тужан,

57
00:03:21,000 --> 00:03:25,000
али морамо да се исправи тај проблем у црвеном пре него што су друге провере ће се покренути.

58
00:03:25,000 --> 00:03:27,000
>> Дозволите ми да поправим ово.

59
00:03:27,000 --> 00:03:30,000
Дозволите ми да умањите и реприза ово, овај пут са бмп.х такође

60
00:03:30,000 --> 00:03:34,000
на командној линији, Ентер, а сада ако све иде добро,

61
00:03:34,000 --> 00:03:38,000
то ће да провери и онда се вратити резултат од-задржите дах-

62
00:03:38,000 --> 00:03:42,000
све зелено, што значи да радим стварно добро на псет 4 до сада.

63
00:03:42,000 --> 00:03:44,000
Можете да видите и закључити из описног текста овде

64
00:03:44,000 --> 00:03:47,000
шта је то што ми тестирали.

65
00:03:47,000 --> 00:03:49,000
Тестирали смо прво да се фајлови постоје?

66
00:03:49,000 --> 00:03:51,000
Затим смо тестирали не ресизе.ц саставити?

67
00:03:51,000 --> 00:03:58,000
Онда смо тестирали то не промените величину 1к1 пиксела БМП када н ресизе фактор је 1.

68
00:03:58,000 --> 00:04:01,000
Сада, ако немаш појма шта је н, једном ћете зароните у псет 4,

69
00:04:01,000 --> 00:04:04,000
али то је једноставно здрав разум проверите да се уверите да нисте промена величине

70
00:04:04,000 --> 00:04:08,000
слика уопште ако промене величине фактор 1.

71
00:04:08,000 --> 00:04:14,000
Ако се, насупрот томе, она прилагођава 1к1 пиксела ка 1к1 пиксела БМП да правилно 2к2

72
00:04:14,000 --> 00:04:19,000
када је н 2, а затим исто тако, моје сходно формира.

73
00:04:19,000 --> 00:04:22,000
>> Укратко, ово је значило да, једном, предузмите Прелазећи прстима

74
00:04:22,000 --> 00:04:25,000
из једначине испред вас пошаљите псет.

75
00:04:25,000 --> 00:04:28,000
Ви ћете тачно знати шта ваш ТФ ће ускоро знати

76
00:04:28,000 --> 00:04:30,000
када идете о подношењу неке од ових проблема скупова,

77
00:04:30,000 --> 00:04:34,000
и педагошки мотивација је заиста ставити

78
00:04:34,000 --> 00:04:37,000
прилика испред себе тако да када знате а приори

79
00:04:37,000 --> 00:04:39,000
да има бугова у свом коду и тестови који се не прошао,

80
00:04:39,000 --> 00:04:43,000
можете ставити у ефикаснијем време напред у решавању тих проблема

81
00:04:43,000 --> 00:04:45,000
него изгубити поене, добити повратне информације из ТФ,

82
00:04:45,000 --> 00:04:48,000
а онда, "Ахх," као да сам схватио да од.

83
00:04:48,000 --> 00:04:50,000
Сада барем постоји алат ће вам помоћи да пронађете то.

84
00:04:50,000 --> 00:04:52,000
То неће указати где је грешка, али то ће вам рећи

85
00:04:52,000 --> 00:04:54,000
оно што је симптоматично то.

86
00:04:54,000 --> 00:04:57,000
>> Сада схватају да тестови нису нужно коначан.

87
00:04:57,000 --> 00:04:59,000
Само зато што сте добили екран пун зеленог смилеи лица

88
00:04:59,000 --> 00:05:02,000
не значи ваш код је савршен, али то не значи

89
00:05:02,000 --> 00:05:06,000
који је прошао одређене тестове прописане спец.

90
00:05:06,000 --> 00:05:08,000
Понекад нећемо објавити чекове.

91
00:05:08,000 --> 00:05:10,000
На пример, детективски роман, један од аспеката псет 4,

92
00:05:10,000 --> 00:05:15,000
је врста разочаравајуће ако вам дам

93
00:05:15,000 --> 00:05:18,000
одговор о томе шта јесте, а ту је и број начина да се откривају

94
00:05:18,000 --> 00:05:21,000
ко лице је у том црвеном буке.

95
00:05:21,000 --> 00:05:24,000
Спецификације ће увек наведете у будућности псет 5 па надаље

96
00:05:24,000 --> 00:05:26,000
шта проверава постоје за вас.

97
00:05:26,000 --> 00:05:28,000
Приметићете да је ова бела УРЛ адреса на дну.

98
00:05:28,000 --> 00:05:30,000
За сада, ово је само дијагностички излаз.

99
00:05:30,000 --> 00:05:33,000
Ако посетите тај УРЛ, добићете гомилу лудих, криптичне поруке

100
00:05:33,000 --> 00:05:36,000
да сте добродошли да погледате, али то је углавном то за запослене

101
00:05:36,000 --> 00:05:41,000
тако да можемо дијагностиковати и отклањање грешака грешке у самом цхецк50.

102
00:05:41,000 --> 00:05:46,000
>> Без оклевања, идемо на тамо где смо стали.

103
00:05:46,000 --> 00:05:48,000
ЦС50 библиотека ми узео здраво за готово за неколико недеља,

104
00:05:48,000 --> 00:05:52,000
али онда прошле недеље, почели смо пилинг назад један од слојева њега.

105
00:05:52,000 --> 00:05:55,000
Почели смо стављајући на страну стринг у корист чега уместо?

106
00:05:55,000 --> 00:05:57,000
[Студенти] Цхар.

107
00:05:57,000 --> 00:05:59,000
Знак *, која је цхар све ово време,

108
00:05:59,000 --> 00:06:03,000
али сада не морам да се претварам да је стварни тип података стринг.

109
00:06:03,000 --> 00:06:06,000
Уместо тога, она је била синоним за врста цхар *,

110
00:06:06,000 --> 00:06:09,000
а стринг је низ знакова,

111
00:06:09,000 --> 00:06:14,000
па зашто то смисла да представљају низове као цхар * с?

112
00:06:14,000 --> 00:06:20,000
Шта цхар представљају у контексту овог концепта низу?

113
00:06:20,000 --> 00:06:23,000
Да >> [Студентски] Први карактер..

114
00:06:23,000 --> 00:06:25,000
Добро је, први знак, али не баш први карактер.

115
00:06:25,000 --> 00:06:27,000
То су-[Ученици] Адреса.

116
00:06:27,000 --> 00:06:29,000
Добро, адреса првог карактера.

117
00:06:29,000 --> 00:06:33,000
Све што је потребно да представља ниску у меморију рачунара

118
00:06:33,000 --> 00:06:36,000
је само јединствена адреса његовог првог бајта.

119
00:06:36,000 --> 00:06:38,000
Не морате чак ни да знам колико дуго је

120
00:06:38,000 --> 00:06:42,000
јер како можете схватио динамички?

121
00:06:42,000 --> 00:06:44,000
[Студентски] Стринг дужине.

122
00:06:44,000 --> 00:06:48,000
Можете позвати дужину жица, одлично, али како стринг дужине ради?

123
00:06:48,000 --> 00:06:50,000
Шта то радиш? Да.

124
00:06:50,000 --> 00:06:52,000
[Студентски] Наставите док не добијете нулл карактер.

125
00:06:52,000 --> 00:06:54,000
Да, тачно, то је само понавља са петљом за, док је петља,

126
00:06:54,000 --> 00:06:57,000
год од * до краја, а крај је заступљен

127
00:06:57,000 --> 00:07:01,000
по \ 0, такозвани нул карактер, нул,

128
00:07:01,000 --> 00:07:05,000
не треба мешати са нула, што је показивач,

129
00:07:05,000 --> 00:07:07,000
који ће доћи у разговору поново данас.

130
00:07:07,000 --> 00:07:11,000
>> Вратили смо ољуштене слој ГетИнт, а онда је погледао на ГетСтринг,

131
00:07:11,000 --> 00:07:14,000
и сећам се да су од тих функција, или стварно,

132
00:07:14,000 --> 00:07:18,000
ГетСтринг, користила одређену функцију

133
00:07:18,000 --> 00:07:21,000
да стварно анализу, која је, читају или анализу, унос корисника.

134
00:07:21,000 --> 00:07:25,000
А шта је то нова функција?

135
00:07:25,000 --> 00:07:27,000
Сцанф или ссцанф. То је заправо долази у неколико различитих укуса.

136
00:07:27,000 --> 00:07:31,000
Ту је сцанф, ту је ссцанф, има фсцанф.

137
00:07:31,000 --> 00:07:35,000
За сада, међутим, да се усредсреди на један најлакше илустрована

138
00:07:35,000 --> 00:07:38,000
и пусти ме да иде напред и отворити у апарату

139
00:07:38,000 --> 00:07:41,000
фајл овако, сцанф1.ц.

140
00:07:41,000 --> 00:07:43,000
Ово је супер једноставан програм,

141
00:07:43,000 --> 00:07:46,000
али да уради нешто што никада нисмо урадили

142
00:07:46,000 --> 00:07:48,000
без помоћ ЦС50 библиотеке.

143
00:07:48,000 --> 00:07:51,000
Ово добија инт од корисника. Како то функционише?

144
00:07:51,000 --> 00:07:53,000
Па, у реду 16 тамо,

145
00:07:53,000 --> 00:07:56,000
примећујемо да прогласе инт зове к, а у овом тренутку у причи,

146
00:07:56,000 --> 00:07:58,000
шта је вредност од к?

147
00:07:58,000 --> 00:08:00,000
[Нечујан ученик одговор]

148
00:08:00,000 --> 00:08:02,000
[Давид М.] Тако је, ко зна, нека смеће вредност потенцијално, тако да у 17 година, ми смо само реци корисника

149
00:08:02,000 --> 00:08:06,000
дај ми број, молим те, и корак 18 је место где се добија занимљиво.

150
00:08:06,000 --> 00:08:11,000
Сцанф изгледа да позајми идеју из иф у томе што користи ове кодове формата у наводницима.

151
00:08:11,000 --> 00:08:13,000
% Д је наравно децимални број.

152
00:08:13,000 --> 00:08:21,000
Али зашто ја пролазу у & к уместо само Кс?

153
00:08:21,000 --> 00:08:24,000
Бивши је тачно. Да.

154
00:08:24,000 --> 00:08:26,000
[Нечујан ученик одговор]

155
00:08:26,000 --> 00:08:31,000
Тачно, ако је циљ тог програма, као и функције ГетИнт самој

156
00:08:31,000 --> 00:08:34,000
је да добије инт од корисника могу проћи функције

157
00:08:34,000 --> 00:08:38,000
све променљиве желим, али ако их не прође по референци

158
00:08:38,000 --> 00:08:41,000
или адресу или показивача, све синоним за потребе данашњих,

159
00:08:41,000 --> 00:08:46,000
онда функција нема способност да мења садржај те променљиве.

160
00:08:46,000 --> 00:08:49,000
То ће проћи у копији баш као бугги верзију своп

161
00:08:49,000 --> 00:08:51,000
да смо разговарали о неколико пута сада.

162
00:08:51,000 --> 00:08:54,000
>> Али уместо тога, радећи и к, буквално сам пролазу у шта?

163
00:08:54,000 --> 00:08:57,000
[Студентски] Адреса. >> Адреси к.

164
00:08:57,000 --> 00:09:01,000
То је као цртање мапа за функцију зове сцанф и говори овде,

165
00:09:01,000 --> 00:09:04,000
ово су смернице за комад меморије у рачунару

166
00:09:04,000 --> 00:09:07,000
да можете ићи сачувати неке цео унутра

167
00:09:07,000 --> 00:09:10,000
Да би ссцанф сада да урадим

168
00:09:10,000 --> 00:09:13,000
шта оператер, шта комад синтаксе ће то морати да користе

169
00:09:13,000 --> 00:09:19,000
иако га не можемо видети јер је неко други написао ову функцију?

170
00:09:19,000 --> 00:09:21,000
Другим речима - шта је то?

171
00:09:21,000 --> 00:09:23,000
[Студентски] Кс чита.

172
00:09:23,000 --> 00:09:27,000
Ту ће бити неких читање, али само у односу на к овде.

173
00:09:27,000 --> 00:09:30,000
Ако сцанф се донела адресу к,

174
00:09:30,000 --> 00:09:35,000
синтаксички, шта оператер је дужан да негде постоји

175
00:09:35,000 --> 00:09:38,000
Унутрашњост је сцанф имплементације тако да се сцанф

176
00:09:38,000 --> 00:09:42,000
заправо може написати број 2 на тој адреси?

177
00:09:42,000 --> 00:09:44,000
Да, тако *.

178
00:09:44,000 --> 00:09:47,000
Подсетимо се да је наша * дереференце оператера, што у суштини значи ићи тамо.

179
00:09:47,000 --> 00:09:50,000
>> Када сте предали адресу, као што је овде случај,

180
00:09:50,000 --> 00:09:53,000
сцанф је вероватно-ако смо заиста погледао око изворног кода-

181
00:09:53,000 --> 00:09:59,000
ради * к или еквивалент да стварно одем на ту адресу и тамо ставио неку вредност.

182
00:09:59,000 --> 00:10:02,000
Сада, као и за колико сцанф учитава са тастатуре,

183
00:10:02,000 --> 00:10:04,000
ћемо махати наше руке за данас.

184
00:10:04,000 --> 00:10:07,000
Само претпоставимо да оперативни систем омогућава ссцанф да разговарају

185
00:10:07,000 --> 00:10:11,000
до тастатуре корисника, али у овом тренутку сада у линији 19,

186
00:10:11,000 --> 00:10:14,000
када смо једноставно штампају к, чини се да је случај

187
00:10:14,000 --> 00:10:17,000
да сцанф ставила Инт у к.

188
00:10:17,000 --> 00:10:19,000
То је тачно како сцанф ради, и сећам се прошле недеље

189
00:10:19,000 --> 00:10:25,000
То је тачно како ГетСтринг и ГетИнт и његова друга породица функција

190
00:10:25,000 --> 00:10:28,000
коначно ради, иако са благим варијансе као ссцанф,

191
00:10:28,000 --> 00:10:31,000
што значи скенирање низ уместо тастатуре.

192
00:10:31,000 --> 00:10:33,000
Али хајде да погледамо мало варијансе ово.

193
00:10:33,000 --> 00:10:37,000
У сцанф2, ја стварно зезнуо.

194
00:10:37,000 --> 00:10:42,000
Шта није у реду и да ћу сакрити коментар који објашњава колико-

195
00:10:42,000 --> 00:10:47,000
шта није у реду са овим програмом, верзија 2?

196
00:10:47,000 --> 00:10:55,000
Будите што је могуће техничке овом тренутку.

197
00:10:55,000 --> 00:10:57,000
Изгледа прилично добро.

198
00:10:57,000 --> 00:11:03,000
То је лепо увучен, али-

199
00:11:03,000 --> 00:11:07,000
ок, како о будимо орезати до краћих питања?

200
00:11:07,000 --> 00:11:17,000
Линија 16. Шта линија 16 ради у прецизном већ техничка енглеском?

201
00:11:17,000 --> 00:11:20,000
Добијање мало незгодно. Да, Мајкл.

202
00:11:20,000 --> 00:11:25,000
[Студентски] То указује на првом слову ниске.

203
00:11:25,000 --> 00:11:27,000
>> Ок, близу. Дозволите ми да дотера мало.

204
00:11:27,000 --> 00:11:33,000
Указујући на првом слову ниске, ви декларисање променљиве зове бафер

205
00:11:33,000 --> 00:11:36,000
која ће указати на првом обраћању на ниске,

206
00:11:36,000 --> 00:11:39,000
односно, да ће указати конкретније знак.

207
00:11:39,000 --> 00:11:42,000
Обратите пажњу да не показује је заправо нигде јер нема оператор доделе.

208
00:11:42,000 --> 00:11:46,000
Нема знака једнакости, па све што радимо је додељивање променљиву зове бафер.

209
00:11:46,000 --> 00:11:49,000
То се дешава да се 32 бита јер је показивач,

210
00:11:49,000 --> 00:11:52,000
и садржај бафера вероватно на крају

211
00:11:52,000 --> 00:11:57,000
ће садржати адресу карактер, али за сада, шта бафер садржи?

212
00:11:57,000 --> 00:11:59,000
Само неки лажни, ко зна, нека смеће вредност,

213
00:11:59,000 --> 00:12:03,000
јер ми нисмо изричито иницијализован, тако да не би требало да преузме ништа.

214
00:12:03,000 --> 00:12:06,000
Ок, сада ред 17 је-шта линија 17 ради?

215
00:12:06,000 --> 00:12:08,000
Можда ће загрејати ово.

216
00:12:08,000 --> 00:12:10,000
Он штампа стринг, зар не?

217
00:12:10,000 --> 00:12:12,000
Он штампа Стринг молим.

218
00:12:12,000 --> 00:12:15,000
>> Линија 18 је врста позната сада у које смо управо видели варијансу овог

219
00:12:15,000 --> 00:12:18,000
али са различитим формата кода, па је у складу 18,

220
00:12:18,000 --> 00:12:23,000
ми говориш сцанф овде је адреса комад меморије.

221
00:12:23,000 --> 00:12:27,000
Желим да звони у низу, као што је имплицирано% с

222
00:12:27,000 --> 00:12:32,000
али проблем је у томе нисмо овде урадили неколико ствари.

223
00:12:32,000 --> 00:12:35,000
Шта је један од проблема?

224
00:12:35,000 --> 00:12:38,000
[Студентски] Покушава да дереференце нулл показивач.

225
00:12:38,000 --> 00:12:41,000
Добри, нулл, или само на други начин непознат показивачи.

226
00:12:41,000 --> 00:12:45,000
Ти предаје сцанф адресу, али сте рекли малочас

227
00:12:45,000 --> 00:12:49,000
да је адреса неке смеће вредност јер нисмо заправо доделити било шта,

228
00:12:49,000 --> 00:12:53,000
па ви говорите сцанф ефективно ићи ставио овде низ,

229
00:12:53,000 --> 00:12:56,000
али ми не знамо где се овде још увек је,

230
00:12:56,000 --> 00:12:59,000
тако да нисмо заправо издвојила меморије за бафер.

231
00:12:59,000 --> 00:13:03,000
Осим тога, оно што такође није ни говорио сцанф?

232
00:13:03,000 --> 00:13:06,000
Претпостављам да је ово био комад меморије, и то није био смеће вредност,

233
00:13:06,000 --> 00:13:09,000
али још увек не говори сцанф нешто важно.

234
00:13:09,000 --> 00:13:12,000
[Студентски] Где је то заправо, амперсанд.

235
00:13:12,000 --> 00:13:15,000
Амперсанд, тако да у овом случају, то је у реду.

236
00:13:15,000 --> 00:13:18,000
Пошто бафер је већ проглашен као показивач

237
00:13:18,000 --> 00:13:22,000
са * комад синтаксе, не морате да користите амперсанд

238
00:13:22,000 --> 00:13:25,000
јер је већ адреса, али мислим да сам га чуо овде.

239
00:13:25,000 --> 00:13:27,000
[Студентски] Како је велика?

240
00:13:27,000 --> 00:13:29,000
Добро, нећемо рећи сцанф колики је бафер,

241
00:13:29,000 --> 00:13:32,000
што значи да чак и ако су били тампон показивач,

242
00:13:32,000 --> 00:13:35,000
говоримо сцанф, ставио овде низ,

243
00:13:35,000 --> 00:13:38,000
али овде може бити 2 бајта, могло би да буде 10 бајта, то би могло да буде мегабајт.

244
00:13:38,000 --> 00:13:41,000
Сцанф нема појма, и зато је ово комад меморије

245
00:13:41,000 --> 00:13:43,000
вероватно, није ниска још.

246
00:13:43,000 --> 00:13:48,000
То је само жица када сте написали карактера и \ 0 до тог комад меморије.

247
00:13:48,000 --> 00:13:51,000
Сада је то само неки комад меморије.

248
00:13:51,000 --> 00:13:55,000
Сцанф неће знати када да престану писања на ту адресу.

249
00:13:55,000 --> 00:13:59,000
>> Ако се сећате неке примере у прошлости, где сам случајно уписани на тастатури

250
00:13:59,000 --> 00:14:03,000
Покушавам да преливају бафер, и разговарали смо у петак око управо то.

251
00:14:03,000 --> 00:14:07,000
Ако противник некако убацује у програм много већи реч

252
00:14:07,000 --> 00:14:10,000
или реченица или фраза онда сте очекивали можете преливати

253
00:14:10,000 --> 00:14:13,000
комад меморије, што може имати лоше последице,

254
00:14:13,000 --> 00:14:15,000
као узимање током целог самог програма.

255
00:14:15,000 --> 00:14:17,000
Морамо да поправимо ово некако.

256
00:14:17,000 --> 00:14:20,000
Дозволите ми да умањите и отићи у верзији 3 овог програма.

257
00:14:20,000 --> 00:14:22,000
То је мало боље.

258
00:14:22,000 --> 00:14:24,000
У овој верзији, приметити разлику.

259
00:14:24,000 --> 00:14:27,000
У 16. реду, опет сам ја проглашења променљиву зове бафер,

260
00:14:27,000 --> 00:14:29,000
али оно што је сада?

261
00:14:29,000 --> 00:14:33,000
То је низ од 16 карактера.

262
00:14:33,000 --> 00:14:36,000
То је добро, јер то значи да ја сада могу да кажем сцанф

263
00:14:36,000 --> 00:14:39,000
овде је стварна комад меморије.

264
00:14:39,000 --> 00:14:42,000
Скоро да мислим низова као показивачи сада,

265
00:14:42,000 --> 00:14:44,000
иако они нису у ствари еквивалент.

266
00:14:44,000 --> 00:14:47,000
Они ће различито понашају у различитим контекстима.

267
00:14:47,000 --> 00:14:50,000
Али то свакако случај да бафер референцирање

268
00:14:50,000 --> 00:14:53,000
16 суседне слова, јер то је оно што је низ

269
00:14:53,000 --> 00:14:55,000
и био је за неколико недеља сада.

270
00:14:55,000 --> 00:14:59,000
>> Ево, ја кажем сцанф ево комад меморије.

271
00:14:59,000 --> 00:15:01,000
Овај пут, то је заправо комад меморије,

272
00:15:01,000 --> 00:15:07,000
али зашто је то програм и даље експлоатисати?

273
00:15:07,000 --> 00:15:11,000
Шта није у реду и даље?

274
00:15:11,000 --> 00:15:14,000
Ја сам рекао да ми 16 бајтова, али-

275
00:15:14,000 --> 00:15:16,000
[Студентски] Шта ако се упишете на више од 16 година?

276
00:15:16,000 --> 00:15:20,000
Тачно, шта ако корисник упише у 17 знакова или 1700 карактера?

277
00:15:20,000 --> 00:15:23,000
У ствари, да видимо ако не можемо саплели ове грешке сада.

278
00:15:23,000 --> 00:15:25,000
То је боље, али није савршена.

279
00:15:25,000 --> 00:15:28,000
Пусти ме само напред и покрените да сцанф3 да састави овај програм.

280
00:15:28,000 --> 00:15:34,000
Дозволите ми да покренете сцанф3, Стринг молим вас поздравим, и ми изгледа у реду.

281
00:15:34,000 --> 00:15:37,000
Дозволите ми да покушам нешто дужи, здраво.

282
00:15:37,000 --> 00:15:42,000
Ок, хајде да здраво како си данас, Ентер.

283
00:15:42,000 --> 00:15:54,000
Како се овде врсту среће, рецимо здраво како си.

284
00:15:54,000 --> 00:15:56,000
Дођавола.

285
00:15:56,000 --> 00:16:03,000
Ок, тако да смо се посрећило. Хајде да видимо, ако не можемо поправити.

286
00:16:03,000 --> 00:16:06,000
Не, то неће да ме пусте да копирате.

287
00:16:06,000 --> 00:16:09,000
Хајде да покушамо поново.

288
00:16:09,000 --> 00:16:12,000
У реду, станд би.

289
00:16:12,000 --> 00:16:20,000
Видећемо колико дуго могу да се претварам да се фокусирамо док још увек раде.

290
00:16:20,000 --> 00:16:23,000
Дођавола. То је прилично могуће, заправо.

291
00:16:23,000 --> 00:16:26,000
Ту смо.

292
00:16:26,000 --> 00:16:30,000
Поинт направио.

293
00:16:30,000 --> 00:16:34,000
>> Ово непријатно иако је такође, то је такође један од извора велике конфузије

294
00:16:34,000 --> 00:16:38,000
када пишете програме који имају бугова јер се манифестују

295
00:16:38,000 --> 00:16:40,000
само једном у неко време понекад.

296
00:16:40,000 --> 00:16:43,000
Реалност је да чак и ако је ваш број је потпуно сломљена,

297
00:16:43,000 --> 00:16:46,000
Можда једино да се потпуно сломљено једном у неко време

298
00:16:46,000 --> 00:16:49,000
јер понекад, у суштини оно што се дешава је оперативни систем додељује

299
00:16:49,000 --> 00:16:52,000
мало више меморије него што вас заиста потребно из било ког разлога,

300
00:16:52,000 --> 00:16:57,000
па нико други не користи меморију одмах након комад 16 карактера,

301
00:16:57,000 --> 00:17:01,000
тако да ако идете на 17, 18, 19, шта год, није то таква велика ствар.

302
00:17:01,000 --> 00:17:04,000
Сада, рачунар, чак и ако то не сруши у том тренутку,

303
00:17:04,000 --> 00:17:09,000
Можда евентуално користити бајта број 17 или 18 или 19 за нешто друго,

304
00:17:09,000 --> 00:17:14,000
при чему су ваше податке које сте тамо рекли, мада претерано дуго,

305
00:17:14,000 --> 00:17:18,000
ће добити преписани потенцијално неком другом функцијом.

306
00:17:18,000 --> 00:17:21,000
То не мора нужно ће остати нетакнута,

307
00:17:21,000 --> 00:17:23,000
али то не значи да ће изазвати СЕГ грешку.

308
00:17:23,000 --> 00:17:26,000
Али у овом случају, коначно сам обезбедио довољно знакова

309
00:17:26,000 --> 00:17:29,000
да сам у суштини премашила свој сегмент меморије, и бам,

310
00:17:29,000 --> 00:17:33,000
оперативни систем је рекао: "Жао ми је, то није добро, сегментација грешка."

311
00:17:33,000 --> 00:17:38,000
>> И хајде сад видимо да ли оно остаје овде у мом именику,

312
00:17:38,000 --> 00:17:40,000
приметити да ја овде имам овај фајл, језгро.

313
00:17:40,000 --> 00:17:42,000
Обратите пажњу да је ово опет зове језгро депонију.

314
00:17:42,000 --> 00:17:46,000
То је у суштини је фајл који садржи садржај меморије програма

315
00:17:46,000 --> 00:17:48,000
у тренутку у коме се срушио,

316
00:17:48,000 --> 00:17:51,000
и само овде пробати мало примера да ме пусте унутра

317
00:17:51,000 --> 00:17:57,000
и покретање ГДБ на сцанф3 а затим одредите трећи аргумент зове језгро,

318
00:17:57,000 --> 00:18:01,000
и приметио да ако сам овде навести шифру

319
00:18:01,000 --> 00:18:06,000
моћи ћемо као и обично са ГДБ да почнете да ходате кроз овај програм,

320
00:18:06,000 --> 00:18:10,000
и ја могу да трчим и чим сам ударио-као корак са командом у ГДБ-

321
00:18:10,000 --> 00:18:13,000
чим сам ударио потенцијално Бугги линију после куцања у огромној ниске,

322
00:18:13,000 --> 00:18:16,000
Ја ћу бити у стању да се заиста га идентификују овде.

323
00:18:16,000 --> 00:18:19,000
Више од тога, међутим, у делу у погледу основних депонијама

324
00:18:19,000 --> 00:18:22,000
и волим, тако да можете заправо џаку око унутар језгра депоније

325
00:18:22,000 --> 00:18:27,000
и видети шта лине програм вам није успело.

326
00:18:27,000 --> 00:18:32,000
Сва питања онда о показивачима и на адресе?

327
00:18:32,000 --> 00:18:36,000
Зато данас, ми ћемо почети узимајући здраво за готово да су ове ствари постоје

328
00:18:36,000 --> 00:18:40,000
и ми знамо тачно шта су.

329
00:18:40,000 --> 00:18:42,000
Да.

330
00:18:42,000 --> 00:18:46,000
>> [Студентски] Како то да ниси морао да стави амперсанд поред дела-

331
00:18:46,000 --> 00:18:48,000
Добро питање.

332
00:18:48,000 --> 00:18:51,000
Како сам дошао није морао да стави амперсанд поред низа знакова, као што сам раније урадио

333
00:18:51,000 --> 00:18:53,000
са већином наших примера?

334
00:18:53,000 --> 00:18:55,000
Кратак одговор је низови су мало посебан.

335
00:18:55,000 --> 00:18:59,000
Можете готово да мислиш бафер као што заправо адреса,

336
00:18:59,000 --> 00:19:03,000
и то је тако једноставно деси да буде случај да заграда нотација

337
00:19:03,000 --> 00:19:06,000
је погодност, тако да можемо да идемо у држач 0, 1, носећи

338
00:19:06,000 --> 00:19:10,000
носач 2, без потребе да користите ознаку *.

339
00:19:10,000 --> 00:19:13,000
То је мало беле лажи, јер низови и показивачи

340
00:19:13,000 --> 00:19:17,000
су, у ствари, мало другачије, али су се често, али не увек да се користе наизменично.

341
00:19:17,000 --> 00:19:21,000
Укратко, када функција очекује показивач на комад меморије,

342
00:19:21,000 --> 00:19:24,000
Можете да га положе адресу која је враћена од маллоц,

343
00:19:24,000 --> 00:19:29,000
па ћемо видети маллоц опет пре времена, или можете да га прође име низа.

344
00:19:29,000 --> 00:19:32,000
Не морате да урадите амперсанд са низовима, јер су они већ

345
00:19:32,000 --> 00:19:34,000
суштини као адресе.

346
00:19:34,000 --> 00:19:36,000
То је један изузетак.

347
00:19:36,000 --> 00:19:39,000
Угласте заграде да их посебно.

348
00:19:39,000 --> 00:19:41,000
>> Да ли сте ставили амперсанд поред бафер?

349
00:19:41,000 --> 00:19:43,000
Не у овом случају.

350
00:19:43,000 --> 00:19:46,000
То не би функционисало, јер опет, овог угла случаја

351
00:19:46,000 --> 00:19:49,000
где низови нису сасвим заправо адресе.

352
00:19:49,000 --> 00:19:54,000
Али ми ћемо можда вратити на то пре него што дуго са другим примерима.

353
00:19:54,000 --> 00:19:56,000
Хајде да покушамо да овде реши проблем.

354
00:19:56,000 --> 00:20:00,000
Имамо структуру података које смо користећи неко време познат као низ.

355
00:20:00,000 --> 00:20:02,000
Случај у тачки, то је оно што смо управо имали.

356
00:20:02,000 --> 00:20:04,000
Али низови имају неки упсидес и негативне.

357
00:20:04,000 --> 00:20:06,000
Низови су лепе зашто?

358
00:20:06,000 --> 00:20:11,000
Шта је једна ствар која вам се допада, у мери у којој вам се допада низови-о низовима?

359
00:20:11,000 --> 00:20:13,000
Шта је згодно о њима? Шта је убедљив?

360
00:20:13,000 --> 00:20:18,000
Зашто смо их увести у првом месту?

361
00:20:18,000 --> 00:20:20,000
Да.

362
00:20:20,000 --> 00:20:27,000
[Студентски] Они могу сачувати много података, а ви не морате да користите целу ствар.

363
00:20:27,000 --> 00:20:29,000
Можете да користите одељак.

364
00:20:29,000 --> 00:20:32,000
Добро, са низом можете складиштити много података,

365
00:20:32,000 --> 00:20:35,000
а ви не морате да користите све то, тако да можете овераллоцате,

366
00:20:35,000 --> 00:20:39,000
што може бити згодно ако не знате унапред колико нешто очекивати.

367
00:20:39,000 --> 00:20:41,000
>> ГетСтринг је савршен пример.

368
00:20:41,000 --> 00:20:44,000
ГетСтринг, написан од стране нас, нема појма колико слова можете да очекујете,

369
00:20:44,000 --> 00:20:48,000
тако чињеница да можемо издвојити комаде целовите меморије је добро.

370
00:20:48,000 --> 00:20:51,000
Низови се реши проблем који смо видели пре пар недеља сада

371
00:20:51,000 --> 00:20:54,000
где ваш код почиње да се пренесу у нешто веома лоше дизајниран.

372
00:20:54,000 --> 00:20:57,000
Подсетимо се да сам направио студент структуру зове Давид,

373
00:20:57,000 --> 00:21:00,000
а онда је заправо алтернатива, међутим,

374
00:21:00,000 --> 00:21:04,000
да имају променљиве под називом име и другу променљиву зове, мислим, кућа,

375
00:21:04,000 --> 00:21:08,000
и други променљиви позвао ИД јер у тој причи сам тада хтела да уведе нешто друго

376
00:21:08,000 --> 00:21:11,000
свиђа Роб у програм, па онда сам одлучио сачекати мало,

377
00:21:11,000 --> 00:21:13,000
Морам да преименујете ове променљиве.

378
00:21:13,000 --> 00:21:16,000
Назовимо рудник НАМЕ1, ид1, хоусе1.

379
00:21:16,000 --> 00:21:20,000
Назовимо Робов име2, хоусе2, ИД2.

380
00:21:20,000 --> 00:21:22,000
Али онда чекај мало, шта о Томи?

381
00:21:22,000 --> 00:21:24,000
Онда смо имали још три променљиве.

382
00:21:24,000 --> 00:21:27,000
Увели смо некога, четири комплета променљивих.

383
00:21:27,000 --> 00:21:30,000
Свет је почео да се компликују врло брзо,

384
00:21:30,000 --> 00:21:33,000
па смо увели Структуре, а оно што је убедљив о струцт?

385
00:21:33,000 --> 00:21:39,000
Шта Ц струцт да радите?

386
00:21:39,000 --> 00:21:42,000
То је заиста непријатно данас.

387
00:21:42,000 --> 00:21:44,000
Шта >> [нечујан ученик одговор?]

388
00:21:44,000 --> 00:21:47,000
Да, конкретно, типедеф вам омогућава да креирате нови тип података,

389
00:21:47,000 --> 00:21:51,000
и струцт, струцт кључна реч, омогућава вам да обухвати

390
00:21:51,000 --> 00:21:54,000
концептуално повезани делови података заједно

391
00:21:54,000 --> 00:21:56,000
а након тога их зову нешто као студент.

392
00:21:56,000 --> 00:21:58,000
>> То је добро јер сада можемо моделовати

393
00:21:58,000 --> 00:22:03,000
много више врста концептуално конзистентна појам студента у променљива

394
00:22:03,000 --> 00:22:07,000
него произвољно има један за ниске, један за ИД, и тако даље.

395
00:22:07,000 --> 00:22:10,000
Низови су лепе, јер су нам омогућити да почне чишћење наш код.

396
00:22:10,000 --> 00:22:13,000
Али, шта је мана сада од низа?

397
00:22:13,000 --> 00:22:15,000
Шта можете да не? Да.

398
00:22:15,000 --> 00:22:17,000
[Студентски] Морате да знате колики је.

399
00:22:17,000 --> 00:22:19,000
Морате да знате колики је, тако да је нека врста бола.

400
00:22:19,000 --> 00:22:21,000
Они од вас са претходног програмирања искуством знају да у многим језицима,

401
00:22:21,000 --> 00:22:24,000
као Јава, можете питати комад меморије, посебно низа,

402
00:22:24,000 --> 00:22:28,000
колики си, дужине, имовине, тако да кажем, и то је заиста згодно.

403
00:22:28,000 --> 00:22:32,000
У Ц, не могу ни назвати стрлен на генеричком низу

404
00:22:32,000 --> 00:22:35,000
јер стрлен, као реч подразумева, само за гудаче,

405
00:22:35,000 --> 00:22:39,000
и можете схватити дужину стринга због овог људског конвенције

406
00:22:39,000 --> 00:22:43,000
да се има \ 0, већ низ, више уопштено, само комад меморије.

407
00:22:43,000 --> 00:22:46,000
Ако је низ Интс, не постоји ће бити неки специјални карактер

408
00:22:46,000 --> 00:22:48,000
на крају чека.

409
00:22:48,000 --> 00:22:50,000
Морате да запамтите дужину низа.

410
00:22:50,000 --> 00:22:54,000
Друга мана низа дигао главу у себе ГетСтринг.

411
00:22:54,000 --> 00:22:59,000
Шта је још мана низа?

412
00:22:59,000 --> 00:23:01,000
Господине, само ти и ја данас.

413
00:23:01,000 --> 00:23:04,000
[Нечујан ученик одговор] >> То је шта?

414
00:23:04,000 --> 00:23:06,000
Је проглашен на стек.

415
00:23:06,000 --> 00:23:09,000
Ок, изјавио на стек. Зашто не свиђа?

416
00:23:09,000 --> 00:23:13,000
[Студентски] Зато што бива поново користити.

417
00:23:13,000 --> 00:23:15,000
Добија поново користити је.

418
00:23:15,000 --> 00:23:18,000
Ок, ако користите низ издвојити меморију,

419
00:23:18,000 --> 00:23:21,000
Ви не можете, на пример, да се врате јер је на стек.

420
00:23:21,000 --> 00:23:23,000
Ок, то је мана.

421
00:23:23,000 --> 00:23:25,000
А како би било да неко други са низом?

422
00:23:25,000 --> 00:23:28,000
Када га издвоји, ти си некако сјебана ако вам је потребно више простора

423
00:23:28,000 --> 00:23:30,000
него низ има.

424
00:23:30,000 --> 00:23:34,000
>> Затим смо увели, подсјетимо, маллоц, који нам је дао могућност да динамички алоцира меморију.

425
00:23:34,000 --> 00:23:37,000
Али, шта ако смо покушали сасвим другачији свет?

426
00:23:37,000 --> 00:23:40,000
Шта ако желимо да решимо неколико тих проблема

427
00:23:40,000 --> 00:23:45,000
тако да смо уместо тога, моје перо је заспао овде-

428
00:23:45,000 --> 00:23:51,000
шта ако уместо тога желели да суштински створи свет који се више не овако?

429
00:23:51,000 --> 00:23:56,000
То је низ, и, наравно, ова врста погоршава када смо погодили крај низа,

430
00:23:56,000 --> 00:24:00,000
и сада више нема простора за другу цео или другог карактера.

431
00:24:00,000 --> 00:24:03,000
Шта ако некако смо превентивно кажу добро, зашто не бисмо се опустите

432
00:24:03,000 --> 00:24:07,000
овај услов да су сви ови комади меморије бити континуални бацк то бацк,

433
00:24:07,000 --> 00:24:10,000
и зашто не, кад треба инт или цхар,

434
00:24:10,000 --> 00:24:12,000
дај ми простор за једног од њих?

435
00:24:12,000 --> 00:24:14,000
И када ми треба још један, дајте ми још један размак,

436
00:24:14,000 --> 00:24:16,000
а кад ми треба још, дај још простора.

437
00:24:16,000 --> 00:24:19,000
Предност која сада јесте да ако неко други

438
00:24:19,000 --> 00:24:21,000
узима меморију овамо, није велика ствар.

439
00:24:21,000 --> 00:24:25,000
Ја ћу узети ову додатну комад меморије овде и онда ово.

440
00:24:25,000 --> 00:24:28,000
>> Сада, само цака је у томе што је овај готово осећа као да имам

441
00:24:28,000 --> 00:24:30,000
гомила различитих променљивих.

442
00:24:30,000 --> 00:24:33,000
То се осећа као пет различитих променљивих потенцијално.

443
00:24:33,000 --> 00:24:36,000
Али шта ако ми украде идеју од жице

444
00:24:36,000 --> 00:24:41,000
чиме смо некако повезати ове ствари заједно концептуално, и шта ако сам урадио ово?

445
00:24:41,000 --> 00:24:44,000
Ово је мој веома лоше нацртана стрелица.

446
00:24:44,000 --> 00:24:46,000
Али претпоставимо да је сваки од ових комада меморије

447
00:24:46,000 --> 00:24:52,000
указао на други, а овај момак, који нема рођак са његове десне стране,

448
00:24:52,000 --> 00:24:54,000
нема такву стрелицу.

449
00:24:54,000 --> 00:24:56,000
То је у ствари оно што се назива повезана листа.

450
00:24:56,000 --> 00:25:00,000
Ово је нова структура података који нам омогућава да издвоје комад меморије,

451
00:25:00,000 --> 00:25:03,000
па још један, па још један, па још један, сваки пут ми желимо

452
00:25:03,000 --> 00:25:07,000
током програма, и сећам се да су сви некако везани

453
00:25:07,000 --> 00:25:11,000
буквално цхаининг их заједно, а ми смо то урадили сликовито овде са стрелом.

454
00:25:11,000 --> 00:25:15,000
Али у коду, шта ће бити механизам преко којег сте некако успео да се повеже,

455
00:25:15,000 --> 00:25:20,000
скоро као нуле, један комад на други комад?

456
00:25:20,000 --> 00:25:22,000
Могли би да користите показивач, зар не?

457
00:25:22,000 --> 00:25:25,000
Јер заиста стрелица која иде од горњег левог квадрата,

458
00:25:25,000 --> 00:25:31,000
овај момак овде на ово, могу садржавати унутар овог трга

459
00:25:31,000 --> 00:25:34,000
не само неки ИНТС, а не само неки знак, али шта ако ја заправо издвојила

460
00:25:34,000 --> 00:25:37,000
мало више простора, тако да сада,

461
00:25:37,000 --> 00:25:41,000
сваки од мојих комада меморије, иако ће ме коштати,

462
00:25:41,000 --> 00:25:45,000
сада изгледа мало више правоугаоног где је један од комада меморије

463
00:25:45,000 --> 00:25:47,000
се користи за број, као и број 1,

464
00:25:47,000 --> 00:25:50,000
а онда, ако овај момак чува број 2,

465
00:25:50,000 --> 00:25:52,000
овај други комад меморије се користи за стрелом,

466
00:25:52,000 --> 00:25:54,000
или још конкретније, показивач.

467
00:25:54,000 --> 00:25:59,000
И претпостављам да меморишете број 3 овамо, док ја користим ово да укаже на тог момка,

468
00:25:59,000 --> 00:26:02,000
и сад овај момак, претпоставимо желим само три такве комаде меморије.

469
00:26:02,000 --> 00:26:05,000
Ја ћу повући линију кроз то, указујући нулл.

470
00:26:05,000 --> 00:26:07,000
Нема додатних карактера.

471
00:26:07,000 --> 00:26:10,000
>> Заиста, ово је како можемо да идемо на имплементацији

472
00:26:10,000 --> 00:26:12,000
нешто што се зове повезана листа.

473
00:26:12,000 --> 00:26:18,000
Повезана листа је нова структура података, а то је одскочна даска ка

474
00:26:18,000 --> 00:26:21,000
много одгајиваца структуре података које почињу да решавају проблеме

475
00:26:21,000 --> 00:26:23,000
дуж линије Фацебоок-типа проблема и Гоогле типа проблемима

476
00:26:23,000 --> 00:26:26,000
где имате огромне сетова података, и то више не сече

477
00:26:26,000 --> 00:26:29,000
за складиштење све цонтигуоусли и користите нешто као линеарне претраге

478
00:26:29,000 --> 00:26:31,000
или чак нешто као бинарни претрагу.

479
00:26:31,000 --> 00:26:33,000
Хоћеш још боље трчање пута.

480
00:26:33,000 --> 00:26:37,000
У ствари, једна од светих Граилс ћемо причати о касније ове недеље или следећег

481
00:26:37,000 --> 00:26:41,000
је алгоритам чије време рада је константна.

482
00:26:41,000 --> 00:26:44,000
Другим речима, она увек има исту количину времена без обзира

483
00:26:44,000 --> 00:26:47,000
колики је улаз, а то би заиста било убедљиво,

484
00:26:47,000 --> 00:26:49,000
чак и више него нечим логаритамском.

485
00:26:49,000 --> 00:26:51,000
Шта је ово на екрану овде?

486
00:26:51,000 --> 00:26:55,000
Сваки од правоугаоника је управо оно што сам нацртао руком.

487
00:26:55,000 --> 00:26:59,000
Али ствар скроз са леве стране је посебна променљива.

488
00:26:59,000 --> 00:27:02,000
То ће бити један показивач, јер је један готцха

489
00:27:02,000 --> 00:27:04,000
са повезану листу, јер те ствари се зову,

490
00:27:04,000 --> 00:27:09,000
је да морате да виси на једном крају повезану листу.

491
00:27:09,000 --> 00:27:13,000
>> Баш као и са низом, морате да знате адресу првог знак.

492
00:27:13,000 --> 00:27:15,000
Иста ствар за повезаним листама.

493
00:27:15,000 --> 00:27:19,000
Морате да знате адресу првог комад меморије

494
00:27:19,000 --> 00:27:25,000
јер од тамо, можете стићи у сваки други.

495
00:27:25,000 --> 00:27:27,000
Мана.

496
00:27:27,000 --> 00:27:30,000
Коју цену плаћамо за ову разноврсност има динамички

497
00:27:30,000 --> 00:27:34,000
Значајан структура података да ако смо икада потребно више меморије, фино,

498
00:27:34,000 --> 00:27:37,000
само издвојити још један комад и извући из показивач

499
00:27:37,000 --> 00:27:39,000
старог на нови реп листи?

500
00:27:39,000 --> 00:27:41,000
Да.

501
00:27:41,000 --> 00:27:43,000
[Студентски] Потребно је око два пута онолико простора.

502
00:27:43,000 --> 00:27:45,000
Потребно је дупло толико простора, тако да је то дефинитивно мана, а ми смо видели

503
00:27:45,000 --> 00:27:48,000
Поента пре између времена и простора и флексибилности

504
00:27:48,000 --> 00:27:51,000
где је до сада, ми не треба 32 бита за сваку од ових бројева.

505
00:27:51,000 --> 00:27:57,000
Ми заиста потребна 64, 32 за броју и 32 за показивача.

506
00:27:57,000 --> 00:27:59,000
Али, хеј, имам 2 гигабајта РАМ-а.

507
00:27:59,000 --> 00:28:02,000
Додавање још 32 бита овде и овде не изгледа тако велика од договора.

508
00:28:02,000 --> 00:28:05,000
Али за великим скуповима података, то је дефинитивно додаје до буквално дупло толико.

509
00:28:05,000 --> 00:28:09,000
Шта је друго Лоша сада, или шта играни ми одустати,

510
00:28:09,000 --> 00:28:12,000
ако представљају спискове ствари са повезаном листом, а не низа?

511
00:28:12,000 --> 00:28:14,000
[Студент] Не могу да прођу уназад.

512
00:28:14,000 --> 00:28:16,000
Ви не можете прећи уназад, тако да си мало зезнуо ако ходате

513
00:28:16,000 --> 00:28:19,000
слева на десно помоћу фор петља или вхиле петље

514
00:28:19,000 --> 00:28:21,000
и онда схватиш: "О, ја желим да се вратим на почетак листе."

515
00:28:21,000 --> 00:28:26,000
Не могу, јер ови показивачи само иду од лева на десно, као стрелице показују.

516
00:28:26,000 --> 00:28:29,000
>> Сада можете да запамтите почетак листе са другом променљиве,

517
00:28:29,000 --> 00:28:31,000
али то је комплексност имати на уму.

518
00:28:31,000 --> 00:28:35,000
Низ, без обзира колико далеко идете, увек можете да урадите минус, минус, минус, минус

519
00:28:35,000 --> 00:28:37,000
и врати се одакле си дошао.

520
00:28:37,000 --> 00:28:40,000
Шта је овде још мана? Да.

521
00:28:40,000 --> 00:28:43,000
[Нечујан ученик питање]

522
00:28:43,000 --> 00:28:47,000
Могао, па си ви заправо сте управо предложио структуру података зове двоструко повезана листа,

523
00:28:47,000 --> 00:28:50,000
и заиста, ти би додати још једну показивач на сваку од ових правоугаоника

524
00:28:50,000 --> 00:28:53,000
који иде други правац, који наопако

525
00:28:53,000 --> 00:28:55,000
сада можете прећи и назад,

526
00:28:55,000 --> 00:28:59,000
мана које се сада ви користите три пута више меморије као што смо некада

527
00:28:59,000 --> 00:29:04,000
и додао сложеност у смислу кода морате да напишете да га добијете праву.

528
00:29:04,000 --> 00:29:08,000
Али ово су све можда врло разумни компромиси, ако преокрет је важније.

529
00:29:08,000 --> 00:29:10,000
Да.

530
00:29:10,000 --> 00:29:12,000
[Студент] Такође не можете имати 2Д повезану листу.

531
00:29:12,000 --> 00:29:16,000
Добро, не можете заиста имају 2Д повезане листе.

532
00:29:16,000 --> 00:29:18,000
Ти би могао. То није ни изблиза лако као низа.

533
00:29:18,000 --> 00:29:21,000
Као низу, ти отворену заграду, затворени постоље отворено постоље затворен носач,

534
00:29:21,000 --> 00:29:23,000
и добити неки 2-димензионалну структуру.

535
00:29:23,000 --> 00:29:26,000
Могли спровести 2-димензионалну повезане листе

536
00:29:26,000 --> 00:29:29,000
ако ти додаци као што је предложио-трећи показивач на сваку од ових ствари,

537
00:29:29,000 --> 00:29:34,000
и ако мислите о другој листи долази на вас 3Д стил

538
00:29:34,000 --> 00:29:40,000
на екрану за све нас, што је само још један ланац неке врсте.

539
00:29:40,000 --> 00:29:45,000
Могли би то да урадим, али то није тако једноставно као куцање отворену заграду, заграда. Да.

540
00:29:45,000 --> 00:29:48,000
[Нечујан ученик питање]

541
00:29:48,000 --> 00:29:50,000
Добро, тако да је ово прави бунтовник.

542
00:29:50,000 --> 00:29:54,000
>> Ови алгоритми које смо пинед преко, као и ох, бинарне претраге,

543
00:29:54,000 --> 00:29:57,000
можете да претражујете низ бројева на табли

544
00:29:57,000 --> 00:30:01,000
или именик толико много брже уколико користите завади па владај

545
00:30:01,000 --> 00:30:05,000
и бинарни претрагу алгоритам, али бинарни тражи потребно две претпоставке.

546
00:30:05,000 --> 00:30:09,000
Један, који је сортиран подаци.

547
00:30:09,000 --> 00:30:11,000
Сада смо вероватно да задржите сортиран,

548
00:30:11,000 --> 00:30:14,000
па можда то није брига, али бинарни претрагу такође преузела

549
00:30:14,000 --> 00:30:18,000
да сте имали насумичну приступ листи бројева,

550
00:30:18,000 --> 00:30:21,000
и низ омогућава вам да имате случајан приступ, као и случајним приступом,

551
00:30:21,000 --> 00:30:24,000
Мислим, ако си дао низ, колико времена то одвести

552
00:30:24,000 --> 00:30:26,000
доћи до конзоле 0?

553
00:30:26,000 --> 00:30:29,000
Једна операција, само користите [0], а ти си тамо.

554
00:30:29,000 --> 00:30:33,000
Колико корака је потребно да стигнете до локације 10?

555
00:30:33,000 --> 00:30:36,000
Један корак, само идите на [10] и да си тамо.

556
00:30:36,000 --> 00:30:40,000
Насупрот томе, како се долази до 10. цео у повезаној листи?

557
00:30:40,000 --> 00:30:42,000
Морате почети на почетку јер ви само сећајући

558
00:30:42,000 --> 00:30:45,000
почетак повезану листу, баш као стринг се памти

559
00:30:45,000 --> 00:30:48,000
по адресу свог првог цхар и да нађемо тај 10. Инт

560
00:30:48,000 --> 00:30:53,000
или да 10. карактер у низу, морате да претражите целу проклету ствар.

561
00:30:53,000 --> 00:30:55,000
>> Опет, ми не решава све наше проблеме.

562
00:30:55,000 --> 00:31:00,000
Ми смо увођењем нових, али то заиста зависи од тога шта ви покушавате да дизајнира за.

563
00:31:00,000 --> 00:31:04,000
У погледу спровођења овог, можемо позајмити идеју од тог студентског структуре.

564
00:31:04,000 --> 00:31:07,000
Синтакса је веома слична, само што је сада, идеја је мало апстрактно

565
00:31:07,000 --> 00:31:09,000
од куће и име и ИД.

566
00:31:09,000 --> 00:31:13,000
Али ја предлажем да имамо структуру података у Ц

567
00:31:13,000 --> 00:31:17,000
која се зове чвор, као последња реч на слајду сугерише,

568
00:31:17,000 --> 00:31:21,000
унутар чвора и чвора је само генерички контејнер у рачунарству.

569
00:31:21,000 --> 00:31:25,000
Обично се извући као круг или квадрат или правоугаоник као што смо урадили.

570
00:31:25,000 --> 00:31:27,000
И у овој структури података, имамо инт, н,

571
00:31:27,000 --> 00:31:29,000
тако да је то број који желите да сачувате.

572
00:31:29,000 --> 00:31:36,000
Али, шта је ово друга линија, струцт ноде * следећи?

573
00:31:36,000 --> 00:31:40,000
Зашто је то тачно, или шта је улога ово игра,

574
00:31:40,000 --> 00:31:42,000
иако је мало криптичан на први поглед?

575
00:31:42,000 --> 00:31:44,000
Да.

576
00:31:44,000 --> 00:31:46,000
[Нечујан ученик одговор]

577
00:31:46,000 --> 00:31:50,000
Тачно тако * врста плена да је показивач неке врсте.

578
00:31:50,000 --> 00:31:53,000
Име овог показивача је самовољно следећа,

579
00:31:53,000 --> 00:32:00,000
али могли смо га звали шта хоћемо, али шта то показивач указују?

580
00:32:00,000 --> 00:32:03,000
[Студентски] Други чвор >> Тачно, то. Указује на другу таквом чвору.

581
00:32:03,000 --> 00:32:05,000
>> Дакле, ово је нека врста знатижеље Ц.

582
00:32:05,000 --> 00:32:09,000
Подсетимо да је Ц чита компајлер врха до дна, с лева на десно,

583
00:32:09,000 --> 00:32:13,000
што значи да ако-ово је мало другачији од онога што смо урадили са учеником.

584
00:32:13,000 --> 00:32:16,000
Када смо дефинисали студента, ми заправо није ставио ту реч.

585
00:32:16,000 --> 00:32:18,000
То је управо рекао типедеф.

586
00:32:18,000 --> 00:32:20,000
Онда смо имали инт ид, стринг име, стринг кућу,

587
00:32:20,000 --> 00:32:23,000
и онда студент на дну струцт.

588
00:32:23,000 --> 00:32:26,000
Ова изјава је мало другачија јер,

589
00:32:26,000 --> 00:32:28,000
опет, Ц компајлер је мало глупо.

590
00:32:28,000 --> 00:32:30,000
То је само ћу да прочитам од врха ка дну,

591
00:32:30,000 --> 00:32:33,000
па ако стигне овде 2. линију

592
00:32:33,000 --> 00:32:37,000
где поред проглашен и види, ох, ево променљива зове следећи.

593
00:32:37,000 --> 00:32:39,000
То је показивач на структуру струцт чвор.

594
00:32:39,000 --> 00:32:42,000
Компајлер ће схватити шта је струцт ноде?

595
00:32:42,000 --> 00:32:44,000
Никад нисам чуо за ове ствари пре,

596
00:32:44,000 --> 00:32:47,000
јер реч чвор не би другачије појавити

597
00:32:47,000 --> 00:32:49,000
до дна, тако да је ово редундантност.

598
00:32:49,000 --> 00:32:53,000
Мораш овде да кажем чвор струцт, које затим могу да скрате касније

599
00:32:53,000 --> 00:32:56,000
захваљујући типедеф овде, али то је зато

600
00:32:56,000 --> 00:33:02,000
смо референцирање саму структуру унутар структуре.

601
00:33:02,000 --> 00:33:05,000
То је једна готцха тамо.

602
00:33:05,000 --> 00:33:07,000
>> Неки интересантни проблеми ће настати.

603
00:33:07,000 --> 00:33:09,000
Имамо списак бројева. Како да убаците у њега?

604
00:33:09,000 --> 00:33:11,000
Како да га тражи? Како ћемо избрисати из ње?

605
00:33:11,000 --> 00:33:13,000
Посебно сада када морамо да управљају свим овим показивача.

606
00:33:13,000 --> 00:33:15,000
Мислили сте да су показивачи врсте ума савијања

607
00:33:15,000 --> 00:33:17,000
када сте имали један од њих само покушава да прочитате Инт на њега.

608
00:33:17,000 --> 00:33:20,000
Сада морамо да манипулишу вреди читаву листу о.

609
00:33:20,000 --> 00:33:22,000
Зашто не узмемо овде 5-минутни одмор, и онда ћемо донети

610
00:33:22,000 --> 00:33:34,000
неки људи на бину да уради управо то.

611
00:33:34,000 --> 00:33:36,000
>> Ц је много забавније када је поступила.

612
00:33:36,000 --> 00:33:39,000
Ко би желео да буквално буде први?

613
00:33:39,000 --> 00:33:41,000
Ок, хајде горе. Ти си први.

614
00:33:41,000 --> 00:33:44,000
Ко би желео да буде 9? Ок, 9.

615
00:33:44,000 --> 00:33:46,000
Шта кажеш 9? 17?

616
00:33:46,000 --> 00:33:51,000
Мало клике овде. 22 и 26 у том првом реду.

617
00:33:51,000 --> 00:33:53,000
И како онда о некоме тамо се истакао у.

618
00:33:53,000 --> 00:33:57,000
Ти си 34. Ок, 34, дођи горе.

619
00:33:57,000 --> 00:33:59,000
Прво је тамо. Ок, све четири од вас.

620
00:33:59,000 --> 00:34:01,000
А ко смо рекли за 9?

621
00:34:01,000 --> 00:34:04,000
Ко је наш 9?

622
00:34:04,000 --> 00:34:07,000
Ко заиста жели да буде 9? Добро, хајде, буди 9.

623
00:34:07,000 --> 00:34:10,000
Идемо.

624
00:34:10,000 --> 00:34:13,000
34, ми ћемо вас срести тамо.

625
00:34:13,000 --> 00:34:17,000
Први део је направити и сами изгледају тако.

626
00:34:17,000 --> 00:34:21,000
26, 22, 17, добро.

627
00:34:21,000 --> 00:34:25,000
Ако можете стајати са стране, јер ћемо вас маллоц у тренутку.

628
00:34:25,000 --> 00:34:29,000
>> Добро, добро.

629
00:34:29,000 --> 00:34:32,000
Ок, одлично, па хајде да поставим овде пар питања.

630
00:34:32,000 --> 00:34:34,000
И заправо, како се зовеш >> Анита.

631
00:34:34,000 --> 00:34:37,000
Анита, у реду, хајде овамо.

632
00:34:37,000 --> 00:34:41,000
Анита ће да нам помогне да некако реши једна прилично једноставно питање, прво,

633
00:34:41,000 --> 00:34:44,000
што је како наћи да ли или не вредност на листи?

634
00:34:44,000 --> 00:34:48,000
Сада, приметите да је први, представљен овде Луцас,

635
00:34:48,000 --> 00:34:52,000
је мало другачија, па је његов комад папира је намерно бочно

636
00:34:52,000 --> 00:34:55,000
јер то није толико висок, а не заузима толико бита,

637
00:34:55,000 --> 00:34:58,000
иако технички има исту величину папира само ротирају.

638
00:34:58,000 --> 00:35:01,000
Али он је мало другачији по томе што је само 32 бита за показивачем,

639
00:35:01,000 --> 00:35:05,000
и све од ових момака су 64 бита, од чега је половина броја, од чега је половина показивач.

640
00:35:05,000 --> 00:35:08,000
Али показивач није приказан, тако да ако ви могли нешто неспретно

641
00:35:08,000 --> 00:35:12,000
користите леву руку да укаже на особу поред себе.

642
00:35:12,000 --> 00:35:14,000
А ти си број 34. Које је твоје име?

643
00:35:14,000 --> 00:35:16,000
Ари.

644
00:35:16,000 --> 00:35:19,000
Ари, па заправо, држи папир у десну руку, а лева рука иде равно доле.

645
00:35:19,000 --> 00:35:21,000
Ви представљате нула са леве стране.

646
00:35:21,000 --> 00:35:24,000
>> Сада је наш људски слика је веома конзистентан.

647
00:35:24,000 --> 00:35:26,000
Ово је заправо колико показивачи раде.

648
00:35:26,000 --> 00:35:29,000
И ако можете да повити мало овако па нисам на путу.

649
00:35:29,000 --> 00:35:34,000
Анита овде, ми пронашли број 22,

650
00:35:34,000 --> 00:35:40,000
али претпостављају ограничења да није човек држи до комада папира,

651
00:35:40,000 --> 00:35:43,000
али ово је списак, а ви само треба да почне са Луцас

652
00:35:43,000 --> 00:35:46,000
јер је буквално прва показивач.

653
00:35:46,000 --> 00:35:51,000
Претпоставимо да сте сами сте показивач, па ви имате могућност да укаже на нешто.

654
00:35:51,000 --> 00:35:56,000
Зашто не почнеш указујући на шта Лукас указује на?

655
00:35:56,000 --> 00:35:58,000
Добро, и дозволите ми донесе ово овде.

656
00:35:58,000 --> 00:36:04,000
Само ради дискусије, дозволите ми да попните овде празну страницу.

657
00:36:04,000 --> 00:36:06,000
Како пише своје име >> Анита.

658
00:36:06,000 --> 00:36:08,000
Ок, Анита.

659
00:36:08,000 --> 00:36:18,000
Рецимо чвор * Анита = Лукаса.

660
00:36:18,000 --> 00:36:22,000
Па, не треба звати Луцас. Требало би да вас зову на првом месту.

661
00:36:22,000 --> 00:36:25,000
Зашто је то, у ствари, у складу са реалношћу овде?

662
00:36:25,000 --> 00:36:27,000
Један, први већ постоји.

663
00:36:27,000 --> 00:36:30,000
Прво је вероватно издвојено негде овде.

664
00:36:30,000 --> 00:36:35,000
Чвор * први, а то је било некако додељена листу.

665
00:36:35,000 --> 00:36:37,000
Ја не знам како се то десило. То се десило пре него што је почео класа.

666
00:36:37,000 --> 00:36:40,000
Ова повезана листа људи је направљен.

667
00:36:40,000 --> 00:36:44,000
И сада у овом тренутку прича све ово дешава на Фејсбуку очигледно касније-

668
00:36:44,000 --> 00:36:49,000
у овом тренутку у причи, Анита је иницијализован да буде једнака први,

669
00:36:49,000 --> 00:36:51,000
што не значи да Анита указује на Лукаса.

670
00:36:51,000 --> 00:36:53,000
Уместо тога, она указује на оно што је он указује на

671
00:36:53,000 --> 00:36:57,000
јер иста адреса која је унутар Луцас је 32 бита - 1, 2, 3 -

672
00:36:57,000 --> 00:37:01,000
сада је унутар Анита је 32 бита - 1, 2, 3.

673
00:37:01,000 --> 00:37:05,000
>> Сада је 22. Како би идете о радиш ово?

674
00:37:05,000 --> 00:37:07,000
Шта је то? >> Поинт то вхатевер.

675
00:37:07,000 --> 00:37:11,000
Покажите шта год, па само напред и делују га најбоље што могу.

676
00:37:11,000 --> 00:37:15,000
Добро, добро, а сада сте окренути-Како се зовеш са 22?

677
00:37:15,000 --> 00:37:18,000
Рамон. >> Рамон, па Рамон држи до 22.

678
00:37:18,000 --> 00:37:20,000
Сада сте урадили проверу.

679
00:37:20,000 --> 00:37:24,000
Да ли Рамон == 22, и ако је тако, на пример, можемо вратити истина.

680
00:37:24,000 --> 00:37:26,000
Пусти ме-док ови момци стоје овде помало неспретно-

681
00:37:26,000 --> 00:37:32,000
пусти ме да урадим нешто брже као Боол наћи.

682
00:37:32,000 --> 00:37:37,000
Идем да иде напред и рећи (чвор * листа, инт н).

683
00:37:37,000 --> 00:37:39,000
Ја ћу се вратити са вама. Морам да напишем нешто кода.

684
00:37:39,000 --> 00:37:45,000
А сада ћу да наставим и радити ово, чвор * Анита = листу.

685
00:37:45,000 --> 00:37:51,000
И ја ћу да наставим и рећи док (Анита = НУЛЛ!).

686
00:37:51,000 --> 00:37:57,000
>> Метафора овде постаје мало развучен, али док (Анита = НУЛЛ!), Шта желим да урадим?

687
00:37:57,000 --> 00:38:03,000
Треба неки начин референцирања

688
00:38:03,000 --> 00:38:05,000
цео број који Анита је показујући на.

689
00:38:05,000 --> 00:38:08,000
У прошлости, када смо имали структуре, који чвор је,

690
00:38:08,000 --> 00:38:11,000
користили смо дот нотацију, а ми би рекли нешто као

691
00:38:11,000 --> 00:38:15,000
анита.н, али овде је проблем што Анита није струцт по себи.

692
00:38:15,000 --> 00:38:17,000
Шта је она?

693
00:38:17,000 --> 00:38:21,000
Она је показивач, па стварно, ако желимо да користимо ову дот-нотацију

694
00:38:21,000 --> 00:38:23,000
и то ће да изгледа намерно мало гробни-

695
00:38:23,000 --> 00:38:28,000
морамо да урадимо нешто као прелазак на левој руци шта год Анита је показујући на

696
00:38:28,000 --> 00:38:31,000
и онда се поље зове н.

697
00:38:31,000 --> 00:38:35,000
Анита је показивач, али оно што је * анита?

698
00:38:35,000 --> 00:38:38,000
Шта вам је када одете на оно што је Анита показујући на?

699
00:38:38,000 --> 00:38:42,000
Струцт, чвор, и чвор, опозив, има поље под називом н

700
00:38:42,000 --> 00:38:47,000
јер је, подсетимо, ова 2 поља, следећи и Н,

701
00:38:47,000 --> 00:38:50,000
које смо видели пре тренутак овде.

702
00:38:50,000 --> 00:38:53,000
>> Да заиста имитирају ово коду,

703
00:38:53,000 --> 00:39:02,000
можемо урадити и рећи ако је ((* анита). н == н) н да тражим.

704
00:39:02,000 --> 00:39:04,000
Приметимо да је функција донет у броју ми је стало.

705
00:39:04,000 --> 00:39:10,000
Онда ја могу ићи напред и радити нешто слично повратку прави.

706
00:39:10,000 --> 00:39:12,000
Иначе, ако то није случај, шта желим да урадим?

707
00:39:12,000 --> 00:39:19,000
Како превести на кодирају шта Анита учинио интуитивно шетњом кроз листи?

708
00:39:19,000 --> 00:39:26,000
Шта треба да урадим овде да симулира Анита предузимање тог корака лево, тај корак са леве стране?

709
00:39:26,000 --> 00:39:28,000
[Нечујан ученик одговор] >> Шта је то?

710
00:39:28,000 --> 00:39:30,000
[Нечујан ученик одговор]

711
00:39:30,000 --> 00:39:34,000
Добро, није лоша идеја, али у прошлости, када смо то урадили, урадили смо анита + +

712
00:39:34,000 --> 00:39:37,000
јер би додали број 1 на Анити,

713
00:39:37,000 --> 00:39:40,000
што би обично указују на следећу особу, као Рамон,

714
00:39:40,000 --> 00:39:44,000
или лице поред њега, или поред њега лице низ линију.

715
00:39:44,000 --> 00:39:49,000
Али то није сасвим добро овде, јер шта је ова ствар изгледа у меморији?

716
00:39:49,000 --> 00:39:54,000
Није то. Морамо да онемогућите то.

717
00:39:54,000 --> 00:40:00,000
То изгледа овако у меморији, и иако сам извући 1 и 2 и 3 близу једна другој,

718
00:40:00,000 --> 00:40:03,000
ако смо заиста симулира ти ово-цан момци, док је још указујући на истим људима,

719
00:40:03,000 --> 00:40:07,000
се неки од вас узети случајни корак назад, неки од вас напред случајни корак?

720
00:40:07,000 --> 00:40:10,000
>> Овај неред је још увек повезана листа,

721
00:40:10,000 --> 00:40:13,000
али ови момци могу бити било где у меморији,

722
00:40:13,000 --> 00:40:15,000
па анита + + неће радити зашто?

723
00:40:15,000 --> 00:40:19,000
Шта је на локацији анита + +?

724
00:40:19,000 --> 00:40:21,000
Ко зна.

725
00:40:21,000 --> 00:40:24,000
То је нека друга вредност која само тако се дешава да се истурили

726
00:40:24,000 --> 00:40:28,000
између свих ових чворова случајно, јер ми не користимо низ.

727
00:40:28,000 --> 00:40:30,000
Ми додељена сваком од ових чворова појединачно.

728
00:40:30,000 --> 00:40:32,000
Ок, ако ви можете сами очистити назад.

729
00:40:32,000 --> 00:40:37,000
Дозволите ми предлажемо да уместо анита + +, ми смо уместо радимо Анита добија-

730
00:40:37,000 --> 00:40:42,000
Па, зашто не одемо на било Анита указује на и онда следећи.

731
00:40:42,000 --> 00:40:45,000
Другим речима, ми идемо да Рамон, који је држи на број 22,

732
00:40:45,000 --> 00:40:51,000
а онда следећи је као да ће се Анита копирање леву руку показивач..

733
00:40:51,000 --> 00:40:54,000
Али она не би ишла даље од Рамон, јер смо пронашли 22.

734
00:40:54,000 --> 00:40:56,000
Али то би била идеја. Дакле, ово је бог страшно неред.

735
00:40:56,000 --> 00:40:59,000
Искрено, нико неће запамтити ову синтаксу, па на срећу,

736
00:40:59,000 --> 00:41:04,000
то је заправо мало намерно-ох, ви нисте уствари видели шта сам написао.

737
00:41:04,000 --> 00:41:08,000
То би било више убедљив ако можеш. Воила!

738
00:41:08,000 --> 00:41:10,000
>> Иза сцене, ја сам решавању проблема на овај начин.

739
00:41:10,000 --> 00:41:14,000
Анита, да тај корак са леве стране,

740
00:41:14,000 --> 00:41:18,000
Прво, ми идемо на адресу коју је Анита показујући на

741
00:41:18,000 --> 00:41:23,000
и где ће наћи не само н, коју смо управо проверава Поређења ради,

742
00:41:23,000 --> 00:41:25,000
али ћете такође наћи следећи - у овом случају,

743
00:41:25,000 --> 00:41:28,000
Рамон је лева рука указује на следећи чвор у листи.

744
00:41:28,000 --> 00:41:32,000
Али ово је бог-страшно неред на које сам поменуо,

745
00:41:32,000 --> 00:41:34,000
али испоставило Ц омогућава нам поједностави ово.

746
00:41:34,000 --> 00:41:40,000
Уместо писања (* анита), ми смо уместо да само пишите Анита-> н,

747
00:41:40,000 --> 00:41:45,000
и то је тачно исто функционално, али је много више интуитивно,

748
00:41:45,000 --> 00:41:48,000
и то је много више у складу са сликом коју смо цртеж

749
00:41:48,000 --> 00:41:50,000
Све ово време користи стреле.

750
00:41:50,000 --> 00:41:57,000
>> На крају, шта је то што треба да урадимо на крају овог програма?

751
00:41:57,000 --> 00:42:00,000
Постоји једна линија преосталог кода.

752
00:42:00,000 --> 00:42:02,000
Повратак шта?

753
00:42:02,000 --> 00:42:05,000
Нетачно, јер ако смо се кроз целу вхиле петље

754
00:42:05,000 --> 00:42:10,000
и Анита је, у ствари, нулл, то значи да је она отишла скроз до краја листе

755
00:42:10,000 --> 00:42:12,000
где је показујући на-шта зовеш?

756
00:42:12,000 --> 00:42:15,000
Ари >> Ари је. Лева рука, која је нулл.

757
00:42:15,000 --> 00:42:18,000
Анита је сада нула, и схватам да само стојимо овде неспретно у лимбу

758
00:42:18,000 --> 00:42:21,000
јер Идем на монолог овде,

759
00:42:21,000 --> 00:42:23,000
али ћемо вас укључити поново само тренутак.

760
00:42:23,000 --> 00:42:27,000
Анита је нула у том тренутку у причи, тако да док се петља завршава,

761
00:42:27,000 --> 00:42:30,000
и морамо се вратити фалсе, јер ако је она добила, све до нулте поинтер Ари је

762
00:42:30,000 --> 00:42:34,000
тада није било број који је тражио на листи.

763
00:42:34,000 --> 00:42:39,000
Можемо очисти ово превише, али то је онда прилично добар имплементација

764
00:42:39,000 --> 00:42:43,000
од Траверсал функције, наћи функцију повезану листу.

765
00:42:43,000 --> 00:42:48,000
То је још увек линеарно претраживање, али то није тако једноставно као + + показивач

766
00:42:48,000 --> 00:42:52,000
или + + и променљива, јер сада не можемо погодити

767
00:42:52,000 --> 00:42:54,000
где сваки од ових чворова су у меморији.

768
00:42:54,000 --> 00:42:57,000
Морамо да буквално прате траг презлом или, тачније,

769
00:42:57,000 --> 00:43:00,000
показивачи, да се са једног чвора на други.

770
00:43:00,000 --> 00:43:02,000
>> Сада хајде да пробамо још један. Анита, да ли желе да се врате овде?

771
00:43:02,000 --> 00:43:06,000
Зашто не можемо ићи напред и издвоје једну особу из публике?

772
00:43:06,000 --> 00:43:08,000
Маллоц-Како се зовеш >> Ребека.

773
00:43:08,000 --> 00:43:10,000
Ребека. Ребека је маллоцед из публике,

774
00:43:10,000 --> 00:43:13,000
и она сада складиштење број 55.

775
00:43:13,000 --> 00:43:17,000
А циљ на дохват руке сада је за Анита да убаците

776
00:43:17,000 --> 00:43:22,000
Ребецца у повезану листу овде у свом одговарајућем месту.

777
00:43:22,000 --> 00:43:24,000
Дођи овамо на тренутак.

778
00:43:24,000 --> 00:43:28,000
Урадио сам нешто овако.

779
00:43:28,000 --> 00:43:32,000
Урадио сам чвор *. А шта ти је име?

780
00:43:32,000 --> 00:43:34,000
Ребека. >> Ребека, ок.

781
00:43:34,000 --> 00:43:41,000
Ребека добија маллоц (сизеоф (чвор)).

782
00:43:41,000 --> 00:43:44,000
Као што смо издвојили ствари као што су студенти и ситница у прошлости,

783
00:43:44,000 --> 00:43:46,000
морамо величину чвора, тако да сада Ребецца

784
00:43:46,000 --> 00:43:49,000
указује на шта?

785
00:43:49,000 --> 00:43:52,000
Ребека има два поља унутар ње, од којих је 55.

786
00:43:52,000 --> 00:43:55,000
Хајде да урадимо оно, Ребека-> = 55.

787
00:43:55,000 --> 00:44:00,000
Али онда Ребецца-> нект треба налик сада, њена рука је некако ко зна?

788
00:44:00,000 --> 00:44:03,000
То показује у неком смећа вредности, па зашто не и за добру меру

789
00:44:03,000 --> 00:44:07,000
ми смо барем урадите тако да лева рука је сада на њеној страни.

790
00:44:07,000 --> 00:44:09,000
Сада Анита, преузети одавде.

791
00:44:09,000 --> 00:44:11,000
Имате Ребека пошто је додељен.

792
00:44:11,000 --> 00:44:20,000
Иди напред и наћи где треба ставити Ребеку.

793
00:44:20,000 --> 00:44:25,000
Добро, веома добро.

794
00:44:25,000 --> 00:44:28,000
Ок, добро, а сада морамо да се обезбеди мало правцу,

795
00:44:28,000 --> 00:44:30,000
тако сте достигли Ари.

796
00:44:30,000 --> 00:44:33,000
Његова лева рука је ништаван, али Ребека јасно припада десно,

797
00:44:33,000 --> 00:44:36,000
па како то морамо да мењају овај повезана листу

798
00:44:36,000 --> 00:44:38,000
како да убаците Ребеку у одговарајућем месту?

799
00:44:38,000 --> 00:44:42,000
Ако буквално могао да се померим лево руке људи око себе као потребно,

800
00:44:42,000 --> 00:44:48,000
ћемо решити проблем који начин.

801
00:44:48,000 --> 00:44:52,000
Ок, добро, а у међувремену, Ребека је лева рука је сада поред ње.

802
00:44:52,000 --> 00:44:54,000
>> То је било превише лако.

803
00:44:54,000 --> 00:44:57,000
Хајде да покушамо додељивања-Ми скоро завршен, 20.

804
00:44:57,000 --> 00:44:59,000
Ок, хајде горе.

805
00:44:59,000 --> 00:45:04,000
20 је додељено, па ћу ићи напред и рећи поново овде

806
00:45:04,000 --> 00:45:07,000
Управо смо урадили чвор * Саад.

807
00:45:07,000 --> 00:45:11,000
Имамо маллоц (сизеоф (чвор)).

808
00:45:11,000 --> 00:45:16,000
Ми онда исту синтаксу као тачан смо урадили раније за 20,

809
00:45:16,000 --> 00:45:20,000
и ја ћу учинити следећи = нулл, а сада је на Анити

810
00:45:20,000 --> 00:45:23,000
да убаците у повезаној листи, ако би могао да играм ту потпуно исту улогу.

811
00:45:23,000 --> 00:45:30,000
Екецуте.

812
00:45:30,000 --> 00:45:32,000
Добро, добро.

813
00:45:32,000 --> 00:45:38,000
Сада размислите пре него што почнете креће лево руке.

814
00:45:38,000 --> 00:45:46,000
Ти далеко добио већину непријатна улогу данас.

815
00:45:46,000 --> 00:45:59,000
Коме треба прво преселио?

816
00:45:59,000 --> 00:46:02,000
Ок, чекај, ја чујем неке не-а.

817
00:46:02,000 --> 00:46:07,000
Ако неки људи би желели учтиво да помогне у решавању овде незгодну ситуацију.

818
00:46:07,000 --> 00:46:11,000
Чији лева рука треба да буде ажуриран прво можда? Да.

819
00:46:11,000 --> 00:46:13,000
[Студентски] Саад је.

820
00:46:13,000 --> 00:46:15,000
Ок, саад је, зашто, иако?

821
00:46:15,000 --> 00:46:17,000
[Нечујан ученик одговор]

822
00:46:17,000 --> 00:46:19,000
Добро, јер ако идемо-Како се зовеш >> Маршал.

823
00:46:19,000 --> 00:46:22,000
Маршал, ако померите руку прво до нулл,

824
00:46:22,000 --> 00:46:25,000
Сада смо буквално сироче четворо људи у овој листи

825
00:46:25,000 --> 00:46:29,000
јер је он био једина ствар показујући на Рамон и свима са леве стране,

826
00:46:29,000 --> 00:46:31,000
па ажурирање прво да показивач био лош.

827
00:46:31,000 --> 00:46:33,000
Идемо ундо то.

828
00:46:33,000 --> 00:46:37,000
Добро, а сад иди и помери леву руку одговарајући показивач на Рамон.

829
00:46:37,000 --> 00:46:39,000
То се осећа мало сувишан.

830
00:46:39,000 --> 00:46:41,000
Сада постоје две особе уперене Рамон, али то је у реду

831
00:46:41,000 --> 00:46:43,000
јер сада како другачије да смо ажурирали листу?

832
00:46:43,000 --> 00:46:48,000
Која је друга рука има да се крећу?

833
00:46:48,000 --> 00:46:53,000
Одлично, сада имамо изгубио памћење?

834
00:46:53,000 --> 00:46:57,000
Не, па добро, хајде да видимо, ако не можемо прекинути ово још једном.

835
00:46:57,000 --> 00:47:00,000
>> Маллоцинг последњи пут, број 5.

836
00:47:00,000 --> 00:47:04,000
Све начин у леђа, хајде доле.

837
00:47:04,000 --> 00:47:08,000
То је веома узбудљиво.

838
00:47:08,000 --> 00:47:15,000
[Аплауз]

839
00:47:15,000 --> 00:47:17,000
Које је твоје име >> Рон.

840
00:47:17,000 --> 00:47:19,000
Рон, у реду, ви маллоцед као број 5.

841
00:47:19,000 --> 00:47:23,000
Управо смо погубили код који је готово идентичан ово

842
00:47:23,000 --> 00:47:26,000
са само другим именом.

843
00:47:26,000 --> 00:47:28,000
Одлично.

844
00:47:28,000 --> 00:47:38,000
Сада, Анита, срећно убацивање број 5 на листи сада.

845
00:47:38,000 --> 00:47:43,000
Добро, и?

846
00:47:43,000 --> 00:47:47,000
Одлично, тако да је ово заиста трећа од три укупног броја случајева.

847
00:47:47,000 --> 00:47:49,000
Прво смо имали некога на крају, Ребека.

848
00:47:49,000 --> 00:47:51,000
Ми смо тада имали некога у средини.

849
00:47:51,000 --> 00:47:53,000
Сада имамо некога на почетку, у овом примеру,

850
00:47:53,000 --> 00:47:56,000
сада морали да ажурирате Лукаса први пут

851
00:47:56,000 --> 00:48:00,000
јер први елемент у листи сада има да укаже на новом чвору,

852
00:48:00,000 --> 00:48:03,000
која, опет, указује на број чвора 9.

853
00:48:03,000 --> 00:48:06,000
>> Ово је изузетно непријатно демонстрација, сигуран сам,

854
00:48:06,000 --> 00:48:08,000
тако велики аплауз за ове момке ако можеш.

855
00:48:08,000 --> 00:48:11,000
Лепо урађено.

856
00:48:11,000 --> 00:48:17,000
То је све. Можете задржати своје папире као мало меморије.

857
00:48:17,000 --> 00:48:22,000
Испоставило се да радиш у шифрама

858
00:48:22,000 --> 00:48:26,000
није баш тако једноставно као само кретање руке око

859
00:48:26,000 --> 00:48:28,000
и указивање на показиваче различите ствари.

860
00:48:28,000 --> 00:48:31,000
Али схватају да када је у питању време да спроведе нешто слично

861
00:48:31,000 --> 00:48:34,000
повезана листа или варијанта тога ако се усредсредите на стварно

862
00:48:34,000 --> 00:48:38,000
ове основне фундаменталне залогаја величине проблеми морам да схватим,

863
00:48:38,000 --> 00:48:43,000
да ли је ово рука или ово рука, схватите да оно што је иначе прилично сложен програм

864
00:48:43,000 --> 00:48:47,000
може, у ствари, бити сведен на релативно једноставне градивних блокова као што је ова.

865
00:48:47,000 --> 00:48:51,000
>> Узмимо ствари у софистициранијим правцу даље.

866
00:48:51,000 --> 00:48:53,000
Ми сада имамо појам повезану листу.

867
00:48:53,000 --> 00:48:57,000
Такође смо-захваљујући предлогу тамо-двоструко повезане листе,

868
00:48:57,000 --> 00:49:01,000
која изгледа скоро исто, али сада имамо две тројке унутар струцт

869
00:49:01,000 --> 00:49:05,000
уместо једног, а ми смо вероватно могли назвати оне показивачи претходни и следећи

870
00:49:05,000 --> 00:49:08,000
или лево или десно, али ми, у ствари, потребно двоје од њих.

871
00:49:08,000 --> 00:49:10,000
Код ће бити мало више укључени.

872
00:49:10,000 --> 00:49:12,000
Анита би морали да раде више овде на сцени.

873
00:49:12,000 --> 00:49:15,000
Али ми свакако може имплементирати такву структуру.

874
00:49:15,000 --> 00:49:19,000
У погледу вођења време, ипак, шта би било време рада

875
00:49:19,000 --> 00:49:24,000
за Аниту за проналажење броја н у повезаној листи сада?

876
00:49:24,000 --> 00:49:27,000
Ипак велики О н, тако да је бољи од линеарног претрагу.

877
00:49:27,000 --> 00:49:29,000
Ми не можемо бинарну претрагу, међутим, поново.

878
00:49:29,000 --> 00:49:34,000
Зашто је то тако? Ви не можете около скочи.

879
00:49:34,000 --> 00:49:36,000
Иако смо очигледно виде све људе на сцени,

880
00:49:36,000 --> 00:49:39,000
и Анита могао да еиебаллед и рекао: "Ево је средњи листе"

881
00:49:39,000 --> 00:49:42,000
она не би знао да ако је она компјутерски програм

882
00:49:42,000 --> 00:49:47,000
јер једино она је морала да се ухвате на на почетку сценарија

883
00:49:47,000 --> 00:49:50,000
био је Лукас, који је био први поентер.

884
00:49:50,000 --> 00:49:53,000
Она нужно морати да прати те везе,

885
00:49:53,000 --> 00:49:56,000
рачунајући свој пут док није нашао отприлике на средини,

886
00:49:56,000 --> 00:49:58,000
па чак и тада, она неће да зна када је она достигла средину

887
00:49:58,000 --> 00:50:01,000
осим ако она оде скроз до краја да схватим колико има,

888
00:50:01,000 --> 00:50:05,000
тада повлачи, и да превише би било тешко уколико сте имали

889
00:50:05,000 --> 00:50:07,000
двоструко повезана листа неке врсте.

890
00:50:07,000 --> 00:50:10,000
>> Решавање неких проблема данас, али увођење друге.

891
00:50:10,000 --> 00:50:12,000
Шта други структуру података укупно?

892
00:50:12,000 --> 00:50:15,000
Ово је фотографија од носача у Матхер Хоусе,

893
00:50:15,000 --> 00:50:19,000
и у овом случају, имамо структуру података и ми смо некако већ говори о томе.

894
00:50:19,000 --> 00:50:22,000
Разговарали смо о стека у контексту меморије,

895
00:50:22,000 --> 00:50:26,000
и то је нека врста намерно названа јер стек у погледу меморије

896
00:50:26,000 --> 00:50:31,000
је ефикасно структура података који има све више и више ствари слојевитим на врху.

897
00:50:31,000 --> 00:50:35,000
Али занимљива ствар у вези гомиле, као што је то случај у стварности,

898
00:50:35,000 --> 00:50:38,000
је да је посебна врста структуре података.

899
00:50:38,000 --> 00:50:42,000
То је структура података којом први елемент у

900
00:50:42,000 --> 00:50:46,000
је последњи елемент напоље.

901
00:50:46,000 --> 00:50:50,000
Ако сте први носач да се стави на стек,

902
00:50:50,000 --> 00:50:53,000
ћеш нажалост бити последњи послужавник да се скине штос

903
00:50:53,000 --> 00:50:55,000
а то није нужно добра ствар.

904
00:50:55,000 --> 00:50:58,000
Насупрот томе, можете да размислите о томе около други начин,

905
00:50:58,000 --> 00:51:02,000
последњи у је први напоље.

906
00:51:02,000 --> 00:51:05,000
>> Дакле, да ли сценарији долазе на памет, где има гомилу

907
00:51:05,000 --> 00:51:08,000
Структура података где имате ту имовину

908
00:51:08,000 --> 00:51:13,000
за последњи у, првом излаз, заправо убедљив?

909
00:51:13,000 --> 00:51:16,000
Да ли је то добра ствар? Да ли је то лоше?

910
00:51:16,000 --> 00:51:19,000
То је дефинитивно лоше ако нису тацне идентична

911
00:51:19,000 --> 00:51:21,000
и сви они су посебни различите боје или ситница,

912
00:51:21,000 --> 00:51:24,000
а боја коју желите скроз на дну.

913
00:51:24,000 --> 00:51:26,000
Наравно, не можете да добијете да без великог напора.

914
00:51:26,000 --> 00:51:28,000
Морате почети од врха и раде свој пут доле.

915
00:51:28,000 --> 00:51:31,000
Слично томе, шта ако сте били један од тих навијачких дечака

916
00:51:31,000 --> 00:51:34,000
ко чека целу ноћ покушавајући да добије иПхоне и линије уп

917
00:51:34,000 --> 00:51:36,000
на оваквом месту?

918
00:51:36,000 --> 00:51:40,000
Зар не би било лепо када би Аппле Сторе

919
00:51:40,000 --> 00:51:42,000
били стек података структура?

920
00:51:42,000 --> 00:51:44,000
Иаи? Наи?

921
00:51:44,000 --> 00:51:47,000
То је само добро за људе који се појаве у последњем могућем тренутку

922
00:51:47,000 --> 00:51:50,000
и онда се извукао ван редоследа.

923
00:51:50,000 --> 00:51:52,000
А у ствари, чињеница да сам био толико склон да кажем ред

924
00:51:52,000 --> 00:51:56,000
је заправо у складу са оним што бисмо ми назвали ова врста структуре података,

925
00:51:56,000 --> 00:51:59,000
један у стварности, где поредак битно,

926
00:51:59,000 --> 00:52:02,000
и желите да први у да буде први од

927
00:52:02,000 --> 00:52:04,000
ако је само због људске правичности.

928
00:52:04,000 --> 00:52:07,000
Ми генерално ћемо назвати куеуе структура података.

929
00:52:07,000 --> 00:52:11,000
>> Испоставило се, поред повезаним листама, можемо да почнете да користите исте основне идеје

930
00:52:11,000 --> 00:52:15,000
и почети стварање нове и различите врсте решења за проблеме.

931
00:52:15,000 --> 00:52:19,000
На пример, у случају гомиле, можемо представљати гомилу

932
00:52:19,000 --> 00:52:22,000
користећи структуру података овако, ја бих предлажемо.

933
00:52:22,000 --> 00:52:26,000
У том случају, ја сам проглашен за струцт, а ја сам рекао унутар ове структуре

934
00:52:26,000 --> 00:52:30,000
је низ бројева и онда променљива зове величина,

935
00:52:30,000 --> 00:52:33,000
и ја ћу да позовем ова ствар гомилу.

936
00:52:33,000 --> 00:52:35,000
Е сад, зашто се то заправо ради?

937
00:52:35,000 --> 00:52:43,000
У случају стека, могао сам да цртам ефикасно на екрану као низа.

938
00:52:43,000 --> 00:52:47,000
Овде је мој стек. То су моји бројеви.

939
00:52:47,000 --> 00:52:50,000
И ми ћемо их извући као ово, ово, ово, ово, ово.

940
00:52:50,000 --> 00:52:53,000
А онда сам овде имам неке друге податке члана,

941
00:52:53,000 --> 00:52:58,000
који се зове величина, тако да је ово величина, и то је број,

942
00:52:58,000 --> 00:53:02,000
и колективно, цела иПад овде представља једну стека структуру.

943
00:53:02,000 --> 00:53:07,000
Сада, по дефаулту, величина вероватно мора да се иницијализује на 0,

944
00:53:07,000 --> 00:53:11,000
и шта је унутра низа бројева иницијално

945
00:53:11,000 --> 00:53:14,000
када сам први пут доделити низ?

946
00:53:14,000 --> 00:53:16,000
Смеће. Ко зна? И то заправо не битно.

947
00:53:16,000 --> 00:53:20,000
Није битно да ли је то 1, 2, 3, 4, 5, потпуно насумично

948
00:53:20,000 --> 00:53:25,000
од лоше среће се налазе у мојој структури, јер докле год знам да је величина стека

949
00:53:25,000 --> 00:53:29,000
је 0, онда програмски знам, не гледај на неки од елемената у низу.

950
00:53:29,000 --> 00:53:31,000
Није битно шта је тамо.

951
00:53:31,000 --> 00:53:34,000
Не гледај у њих, као што би био импликација величине од 0.

952
00:53:34,000 --> 00:53:38,000
>> Али претпоставимо сада ићи напред и убаците нешто у стеку.

953
00:53:38,000 --> 00:53:42,000
Желим да убаците број 5, па сам ставио овде број 5,

954
00:53:42,000 --> 00:53:45,000
и онда шта сам ставио овде?

955
00:53:45,000 --> 00:53:48,000
Сада сам стварно бих спустио 1 по величини,

956
00:53:48,000 --> 00:53:50,000
и сада стек величине 1.

957
00:53:50,000 --> 00:53:53,000
Шта ако сам напред и ставите број, рецимо, 7 следећи?

958
00:53:53,000 --> 00:53:57,000
То онда добија ажуриран 2, а онда ћемо до 9,

959
00:53:57,000 --> 00:54:02,000
а онда добија ажурирани 3.

960
00:54:02,000 --> 00:54:05,000
Али занимљива карактеристика сад овог стека је да

961
00:54:05,000 --> 00:54:09,000
Ја треба да уклони елемент који, ако желим да поп

962
00:54:09,000 --> 00:54:12,000
нешто искључивање стеку, да се тако изразим?

963
00:54:12,000 --> 00:54:14,000
9 ће бити прва ствар коју треба да идем.

964
00:54:14,000 --> 00:54:18,000
Како би се слика промени ако желим да се појави елемент ван стек,

965
00:54:18,000 --> 00:54:20,000
волео послужавник у Матхер?

966
00:54:20,000 --> 00:54:22,000
Да >> [Студентски] Подешавање величине до 2..

967
00:54:22,000 --> 00:54:27,000
Тачно, све што урадите је да поставите величину до 2, и шта да радим са низом?

968
00:54:27,000 --> 00:54:29,000
Не морам ништа да радим.

969
00:54:29,000 --> 00:54:32,000
Сам могао, само да би анални, ставите 0 постоји или -1 или тако нешто, да означи

970
00:54:32,000 --> 00:54:34,000
да ово није легит вредност, али то није битно, јер

971
00:54:34,000 --> 00:54:37,000
Ја могу снимати изван самог низа колико је она

972
00:54:37,000 --> 00:54:41,000
тако да ја знам само осврнемо на прва два елемента у овом низу.

973
00:54:41,000 --> 00:54:47,000
Сада, ако одем и додајте број 8 на овај низ, како се слика промени следеце?

974
00:54:47,000 --> 00:54:50,000
Ово постаје 8, и то постаје 3.

975
00:54:50,000 --> 00:54:52,000
Ја сам овде сечење неколико углова.

976
00:54:52,000 --> 00:54:56,000
Сада имамо 5, 7, 8, и ми смо се вратили на величину од 3.

977
00:54:56,000 --> 00:54:58,000
То је прилично једноставан за примену,

978
00:54:58,000 --> 00:55:06,000
али када ћемо зажалити ову одлуку дизајн?

979
00:55:06,000 --> 00:55:09,000
Када се ствари почну да иду врло, врло погрешно? Да.

980
00:55:09,000 --> 00:55:11,000
[Нечујан ученик одговор]

981
00:55:11,000 --> 00:55:13,000
Када желите да се вратите и да први елемент сте ставили унутра

982
00:55:13,000 --> 00:55:18,000
>> Испоставило се овде, иако стек низ испод хаубе,

983
00:55:18,000 --> 00:55:21,000
ови подаци структуре смо почели да разговарамо о су опште познати као

984
00:55:21,000 --> 00:55:25,000
апстрактне структуре података чиме како они спроводе

985
00:55:25,000 --> 00:55:27,000
потпуно је поред тачке.

986
00:55:27,000 --> 00:55:31,000
Структура података као стек треба да дода подршку

987
00:55:31,000 --> 00:55:35,000
операције као што притиском, што гура послужавник на стек,

988
00:55:35,000 --> 00:55:39,000
и поп, који уклања елемент са стека, и то је то.

989
00:55:39,000 --> 00:55:43,000
Ако сте били да преузмете туђи код који већ имплементиран

990
00:55:43,000 --> 00:55:46,000
ово се зове стек, та особа би написали

991
00:55:46,000 --> 00:55:49,000
само два функције за вас гура и поп, чија је једина сврха у животу

992
00:55:49,000 --> 00:55:51,000
би да урадите управо то.

993
00:55:51,000 --> 00:55:54,000
Ти или он, или она која спроводи тај програм

994
00:55:54,000 --> 00:55:58,000
би био у потпуности један да одлучи како да се примени

995
00:55:58,000 --> 00:56:00,000
семантике гурања и кокичара испод хаубе

996
00:56:00,000 --> 00:56:03,000
или функционалност гура и кокичавости.

997
00:56:03,000 --> 00:56:07,000
И ја сам овде направио нешто кратковид одлуку

998
00:56:07,000 --> 00:56:10,000
спроводећи своју штос са овом једноставном структуру података зашто?

999
00:56:10,000 --> 00:56:12,000
Када се ове податке структуру паузу?

1000
00:56:12,000 --> 00:56:18,000
У ком тренутку морам вратити грешку када корисник позива Пусх, на пример?

1001
00:56:18,000 --> 00:56:20,000
[Студентски] Ако нема више простора.

1002
00:56:20,000 --> 00:56:23,000
Тачно, ако нема више простора, ако сам премашио капацитет,

1003
00:56:23,000 --> 00:56:27,000
што је све капе, јер сугерише да је то нека врста глобалне константе.

1004
00:56:27,000 --> 00:56:30,000
Па, онда ћу само морати да кажу: "Жао ми је, не могу да гурне друго вредност

1005
00:56:30,000 --> 00:56:32,000
на стеку, "много као у Матхер.

1006
00:56:32,000 --> 00:56:36,000
>> У неком тренутку, они ће да удари горњи део тог малог кабинета.

1007
00:56:36,000 --> 00:56:39,000
Нема више простора или капацитета у стеку, након чега постоји нека врста грешке.

1008
00:56:39,000 --> 00:56:42,000
Они морају да стави елемент негде другде, касета негде другде,

1009
00:56:42,000 --> 00:56:44,000
или нигде уопште.

1010
00:56:44,000 --> 00:56:47,000
Сада, са ред, можемо га имплементирати мало другачије.

1011
00:56:47,000 --> 00:56:50,000
Редослед је мало другачији по томе што испод хаубе, она може да се имплементира

1012
00:56:50,000 --> 00:56:54,000
као низ, али зашто, у овом случају, ја предлагање

1013
00:56:54,000 --> 00:56:59,000
да имају елемент подизања представља главу на листи,

1014
00:56:59,000 --> 00:57:06,000
предњи део листе, прва особа у реду на Аппле продавници, поред величине?

1015
00:57:06,000 --> 00:57:14,000
Зашто ми треба додатни податак?

1016
00:57:14,000 --> 00:57:16,000
Сетите се шта је бројева

1017
00:57:16,000 --> 00:57:18,000
ако сам извући на следећи начин.

1018
00:57:18,000 --> 00:57:21,000
Претпоставимо да је ово сада перчин уместо стека,

1019
00:57:21,000 --> 00:57:24,000
разлика бити-баш као Аппле сторе-ред је фер.

1020
00:57:24,000 --> 00:57:27,000
Прва особа у реду на почетку листе, број 5, у овом случају,

1021
00:57:27,000 --> 00:57:30,000
он или она ће бити пусти у продавници прво.

1022
00:57:30,000 --> 00:57:32,000
Хајде да то урадимо.

1023
00:57:32,000 --> 00:57:35,000
Претпоставимо да је ово стање мог ред у овом тренутку у времену, а сада Аппле продавница

1024
00:57:35,000 --> 00:57:39,000
отвара и прва особа, број 5, је водио у продавницу.

1025
00:57:39,000 --> 00:57:43,000
Како да промените слику сада сам одјављене чекању прву особу

1026
00:57:43,000 --> 00:57:47,000
на предњој линији?

1027
00:57:47,000 --> 00:57:50,000
Шта је то >> [Студентски] Промените редослед.

1028
00:57:50,000 --> 00:57:52,000
Промените главу, па 5 нестаје.

1029
00:57:52,000 --> 00:57:56,000
У стварности, то је као да-како најбоље да се то уради?

1030
00:57:56,000 --> 00:58:00,000
У стварности, то је као да је овај момак нестаје.

1031
00:58:00,000 --> 00:58:03,000
Шта би број 7 учинити у стварном продавници?

1032
00:58:03,000 --> 00:58:05,000
Они би унапред предузети велики корак.

1033
00:58:05,000 --> 00:58:08,000
>> Али оно што смо дошли да ценимо, када је у питању низови

1034
00:58:08,000 --> 00:58:10,000
и премештање ствари около?

1035
00:58:10,000 --> 00:58:12,000
То је нека врста отпада ваше време, зар не?

1036
00:58:12,000 --> 00:58:16,000
Зашто мораш да будеш тако аналног да имамо прву особу

1037
00:58:16,000 --> 00:58:21,000
на почетку линије на физички почетку комад меморије?

1038
00:58:21,000 --> 00:58:23,000
То је потпуно непотребно. Зашто?

1039
00:58:23,000 --> 00:58:26,000
Шта сам могао да се сетим само уместо >> [нечујан ученик одговор?]

1040
00:58:26,000 --> 00:58:30,000
Тачно, само сам могао да се сетим са овим додатним подацима чланица главе

1041
00:58:30,000 --> 00:58:34,000
да је сада на челу листе је више 0, која је пре тренутак.

1042
00:58:34,000 --> 00:58:39,000
Сада је заправо број 1. На овај начин, ја се мало оптимизацију.

1043
00:58:39,000 --> 00:58:44,000
Само зато што сам одјављене чекању некога из линије на почетку линије на Аппле продавници

1044
00:58:44,000 --> 00:58:47,000
не значи да сви треба да се мењају, што је присећање линеарна операција.

1045
00:58:47,000 --> 00:58:50,000
Ја уместо да само троше време константан

1046
00:58:50,000 --> 00:58:53,000
и постићи онда много бржи одговор.

1047
00:58:53,000 --> 00:58:56,000
Али цена коју плацам је оно да се добије тај додатни рад

1048
00:58:56,000 --> 00:58:58,000
и не морају да пребаце све?

1049
00:58:58,000 --> 00:59:01,000
Да >> [нечујан ученик одговор].

1050
00:59:01,000 --> 00:59:04,000
Могу да додају још људи, па то је проблем ортогонална

1051
00:59:04,000 --> 00:59:07,000
на чињеницу да нисмо Правац људе около.

1052
00:59:07,000 --> 00:59:11,000
То је и даље низ, тако да без обзира да ли смо или нисмо пребаце свима или не-

1053
00:59:11,000 --> 00:59:13,000
Ох, видим шта мислите, у реду.

1054
00:59:13,000 --> 00:59:16,000
Заправо, ја се слажем са оним што ви кажете да је у готово као да

1055
00:59:16,000 --> 00:59:19,000
ми смо сада никада неће више користити почетак овог низа

1056
00:59:19,000 --> 00:59:22,000
јер ако сам уклони 5, онда уклоните 7.

1057
00:59:22,000 --> 00:59:24,000
Али ја само ставити људе са десне стране.

1058
00:59:24,000 --> 00:59:28,000
>> То се осећа као да губим простор, и на крају ми је перчин распадне у ништа,

1059
00:59:28,000 --> 00:59:31,000
тако да смо само могли да имамо људе обвојно,

1060
00:59:31,000 --> 00:59:35,000
и могли бисмо да размишљамо о овом низу заиста као нека врста кружног објекта,

1061
00:59:35,000 --> 00:59:38,000
али ми користимо шта оператор у Ц да такве обвојно?

1062
00:59:38,000 --> 00:59:40,000
[Нечујан ученик одговор] >> модулу оператер.

1063
00:59:40,000 --> 00:59:43,000
Било би мало досадно да се размисли како да урадите обвојно,

1064
00:59:43,000 --> 00:59:46,000
али смо могли да радимо, и ми могли почети стављање људи на оно што је некада била испред линије,

1065
00:59:46,000 --> 00:59:52,000
али ми се сетим са овом главом променљиве који стварни шеф линије заправо јесте.

1066
00:59:52,000 --> 00:59:57,000
Шта ако, уместо тога, на крају наш циљ, међутим,

1067
00:59:57,000 --> 01:00:00,000
био је да потражите бројеве, као што смо овде урадили на позорници са Анита,

1068
01:00:00,000 --> 01:00:02,000
али ми заиста желимо најбоље од свих тих светова?

1069
01:00:02,000 --> 01:00:05,000
Желимо више софистицираности него низ омогућава

1070
01:00:05,000 --> 01:00:09,000
јер желимо могућност да динамички расте података структуру.

1071
01:00:09,000 --> 01:00:12,000
Али ми не желимо да морају да прибегну нешто што смо истакли

1072
01:00:12,000 --> 01:00:15,000
У првом предавању није била оптимална алгоритам,

1073
01:00:15,000 --> 01:00:17,000
да од линеарне претраге.

1074
01:00:17,000 --> 01:00:21,000
Испада да сте, у ствари, постигне

1075
01:00:21,000 --> 01:00:24,000
или барем близу сталном времену, при чему неко као Анита,

1076
01:00:24,000 --> 01:00:27,000
ако она подешава своју структуру података не буде повезана листа,

1077
01:00:27,000 --> 01:00:30,000
да не буде скуп, да не буде ред чекања, може се, у ствари,

1078
01:00:30,000 --> 01:00:33,000
дошао до података структуру која омогућава јој да изгледа горе ствари,

1079
01:00:33,000 --> 01:00:37,000
чак и речи, а не само бројеве, у шта ћемо звати константно време.

1080
01:00:37,000 --> 01:00:40,000
>> И у ствари, гледајући напред, један од псетс у овој класи је готово увек

1081
01:00:40,000 --> 01:00:43,000
имплементација Правопис, при чему

1082
01:00:43,000 --> 01:00:46,000
ми смо вам дати опет неке 150.000 речи енглеског језика и циљ је да се

1083
01:00:46,000 --> 01:00:51,000
учитати у меморију и они брзо бити у стању да одговори на питања о форми

1084
01:00:51,000 --> 01:00:54,000
се ова реч правилно написан?

1085
01:00:54,000 --> 01:00:58,000
И стварно би сиса, ако сте морали да вршите итерацију кроз све 150.000 речи да одговорим.

1086
01:00:58,000 --> 01:01:02,000
Али, у ствари, видећемо да то радимо у веома, веома брзо време.

1087
01:01:02,000 --> 01:01:06,000
И то ће укључити спроводи нешто што се зове хеш табели,

1088
01:01:06,000 --> 01:01:09,000
и иако на први поглед ово се зове хеш табела ће се

1089
01:01:09,000 --> 01:01:12,000
нека нам постигли ови супер брзи одзив,

1090
01:01:12,000 --> 01:01:18,000
Испоставило се да је у ствари проблем.

1091
01:01:18,000 --> 01:01:23,000
Када дође време да се спроведе ову ствар зове-опет, ја то радим поново.

1092
01:01:23,000 --> 01:01:25,000
Ја сам једини овде.

1093
01:01:25,000 --> 01:01:28,000
Када је у питању време да примени ову ствар зове хеш табела,

1094
01:01:28,000 --> 01:01:30,000
ћемо морати да донесе одлуку.

1095
01:01:30,000 --> 01:01:32,000
Колико велике би ова ствар заправо бити?

1096
01:01:32,000 --> 01:01:36,000
А када смо започели убацивањем бројеве у овој хеш табели,

1097
01:01:36,000 --> 01:01:38,000
како ћемо их чувати на такав начин

1098
01:01:38,000 --> 01:01:42,000
да можемо да их вратимо се тако брзо као што их је добио у?

1099
01:01:42,000 --> 01:01:45,000
Али видећемо убрзо да се ово питање

1100
01:01:45,000 --> 01:01:48,000
када је свачији рођендан је у класи ће бити сасвим германе.

1101
01:01:48,000 --> 01:01:51,000
Испада да у овој просторији, имамо неколико стотина људи,

1102
01:01:51,000 --> 01:01:56,000
па су шансе да нас двоје имамо исти рођендан је вероватно прилично висока.

1103
01:01:56,000 --> 01:01:58,000
Шта ако је било само 40 од нас у овој соби?

1104
01:01:58,000 --> 01:02:02,000
Какве су шансе да двоје људи имају исти рођендан?

1105
01:02:02,000 --> 01:02:04,000
[Студенти] Преко 50%.

1106
01:02:04,000 --> 01:02:06,000
Да, преко 50%. У ствари, чак сам донео графикон.

1107
01:02:06,000 --> 01:02:08,000
Испоставило се и да је ово заиста само снеак превиев-

1108
01:02:08,000 --> 01:02:12,000
ако има само 58 од нас у овој соби, вероватноћа од 2 нас

1109
01:02:12,000 --> 01:02:16,000
имају исти рођендан је изузетно висока, скоро 100%,

1110
01:02:16,000 --> 01:02:20,000
и да ће изазвати гомилу повредио за нас у среду.

1111
01:02:20,000 --> 01:02:24,000
>> Уз то је рекао, хајде да завршимо овде. Видимо се у среду.

1112
01:02:24,000 --> 01:02:28,000
[Аплауз]

1113
01:02:28,000 --> 01:02:30,000
[ЦС50.ТВ]