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

2
00:00:00,500 --> 00:00:11,137
[Музички]

3
00:00:11,137 --> 00:00:12,220
Дејвид Џ MALAN: Во ред.

4
00:00:12,220 --> 00:00:13,950
Ова е CS50.

5
00:00:13,950 --> 00:00:18,560
Ова е недела пет продолжува, а ние
има некои добри вести и некои лоши вести.

6
00:00:18,560 --> 00:00:21,140
Па Добрата вест е дека CS50
започна овој петок.

7
00:00:21,140 --> 00:00:24,430
Ако би сакале да ни се придружат,
се упатат кон вообичаените рачно тука.

8
00:00:24,430 --> 00:00:28,670
Уште подобра вест, нема предавање
ова доаѓа понеделник 13-ти.

9
00:00:28,670 --> 00:00:31,970
Малку помалку подобра вест,
квиз нула е следната среда.

10
00:00:31,970 --> 00:00:33,840
Повеќе детали може да биде
најдат на овој URL тука.

11
00:00:33,840 --> 00:00:36,340
И во текот на следните неколку дена
ние ќе се пополнување на празни места

12
00:00:36,340 --> 00:00:39,234
во однос на соби
дека ќе се задржани.

13
00:00:39,234 --> 00:00:41,400
Подобра вест е дека таму ќе
биде разбира ширум преглед

14
00:00:41,400 --> 00:00:43,570
седница оваа доаѓаат
Понеделник навечер.

15
00:00:43,570 --> 00:00:46,270
Stay tuned до на курсот
веб-страница за локација и детали.

16
00:00:46,270 --> 00:00:49,290
Делови, иако тоа е
празник, ќе се сретне и како и.

17
00:00:49,290 --> 00:00:50,490

18
00:00:50,490 --> 00:00:52,940
Најдобрата вест, предавање следниот петок.

19
00:00:52,940 --> 00:00:56,220
Значи ова е традиција
имаат, како на наставната програма.

20
00:00:56,220 --> 00:00:58,100
Just-- тоа се случува да биде неверојатно.

21
00:00:58,100 --> 00:01:02,510
Ќе видите работи како
постојана време структури на податоци

22
00:01:02,510 --> 00:01:04,730
и хаш маси и дрва и се обидува.

23
00:01:04,730 --> 00:01:07,150
И ние ќе зборуваме за роденден проблеми.

24
00:01:07,150 --> 00:01:09,440
А целиот куп на работи
чека следниот петок.

25
00:01:09,440 --> 00:01:11,212

26
00:01:11,212 --> 00:01:12,200
Во ред.

27
00:01:12,200 --> 00:01:13,190
Во секој случај.

28
00:01:13,190 --> 00:01:17,080
>> Така се потсетиме дека ние сме
фокусирајќи се на оваа слика на она што е

29
00:01:17,080 --> 00:01:18,980
во внатрешноста на меморија нашиот компјутер.

30
00:01:18,980 --> 00:01:22,875
Значи меморија или RAM меморија е местото каде што програми
постојат додека си ги работи.

31
00:01:22,875 --> 00:01:25,215
Ако ќе кликнете двапати на
иконата за да се кандидира на некои програма

32
00:01:25,215 --> 00:01:27,520
или со двоен клик на
иконата за да го отворам во некои датотеки,

33
00:01:27,520 --> 00:01:30,430
тоа е натоварен од вашиот хард
диск или цврста состојба диск

34
00:01:30,430 --> 00:01:34,190
во RAM меморија, Случаен Пристап меморија, каде
тоа живее до моќта заминува,

35
00:01:34,190 --> 00:01:36,700
на лаптопот се затвора,
или ќе ја завршите програмата.

36
00:01:36,700 --> 00:01:38,960
>> Сега дека меморија,
кои најверојатно имаат

37
00:01:38,960 --> 00:01:41,950
1 гигабајт овие денови, 2
гигабајти, или дури и многу повеќе,

38
00:01:41,950 --> 00:01:44,420
генерално се утврдени
за одредена програма

39
00:01:44,420 --> 00:01:47,170
во овој вид на правоаголна
концептуален модел

40
00:01:47,170 --> 00:01:50,860
при што имаме магацинот на дното
и еден куп други нешта на врвот.

41
00:01:50,860 --> 00:01:53,140
Нешто во самиот врв
видовме на оваа слика

42
00:01:53,140 --> 00:01:55,670
пред, но никогаш не зборуваше за
е т.н. текст сегмент.

43
00:01:55,670 --> 00:01:58,419
Текстот сегмент е само стилизиран начин
на велејќи дека нули и оние кои

44
00:01:58,419 --> 00:02:01,150
компонира вашиот вистински состави програма.

45
00:02:01,150 --> 00:02:03,910
>> Значи, кога ќе кликнете двапати на
Microsoft Word на вашиот Mac или PC,

46
00:02:03,910 --> 00:02:08,030
или кога ќе ја стартувате точка намали Марио на
Линукс компјутер во вашиот терминал,

47
00:02:08,030 --> 00:02:12,460
на нули и единици кои ја сочинуваат
Збор или Марио се чуваат привремено

48
00:02:12,460 --> 00:02:16,610
во RAM меморија на вашиот компјутер во т.н.
текстот сегмент за одредена програма.

49
00:02:16,610 --> 00:02:19,080
Под што оди иницијализира
и Uninitialized податоци.

50
00:02:19,080 --> 00:02:22,655
Ова е нешто како глобални променливи,
дека не сум користел многу од,

51
00:02:22,655 --> 00:02:24,910
но понекогаш ние сме
имаше глобални променливи

52
00:02:24,910 --> 00:02:28,819
или статички дефинирани стрингови кои
е хард кодирани зборови како "здраво"

53
00:02:28,819 --> 00:02:31,860
кои не се земени во од страна на корисникот
кои се хард-кодирани во вашата програма.

54
00:02:31,860 --> 00:02:34,230
>> Сега, одредување на дното ние
имаат т.н. оџак.

55
00:02:34,230 --> 00:02:37,665
И магацинот, досега, ние сме
користење за какви цели?

56
00:02:37,665 --> 00:02:39,706

57
00:02:39,706 --> 00:02:40,997
Што е оџакот се користи за?

58
00:02:40,997 --> 00:02:41,160
Да?

59
00:02:41,160 --> 00:02:42,070
>> ПУБЛИКАТА: Функции.

60
00:02:42,070 --> 00:02:43,320
>> Дејвид Џ MALAN: За функции?

61
00:02:43,320 --> 00:02:44,980
Во која смисла за функции?

62
00:02:44,980 --> 00:02:48,660
>> ПУБЛИКАТА: Кога ќе се јавите на функција,
аргументи се копирани врз оџакот.

63
00:02:48,660 --> 00:02:49,660
>> Дејвид Џ MALAN: Токму така.

64
00:02:49,660 --> 00:02:52,650
Кога ќе се јавите на функција, нејзиниот
аргументи се копирани врз оџакот.

65
00:02:52,650 --> 00:02:56,330
Така било на X или Y или А или Б
дека сте поминува во функција

66
00:02:56,330 --> 00:02:58,680
привремено се стави на
т.н. стек,

67
00:02:58,680 --> 00:03:02,000
како еден од Annenberg
јадење салата сад, а исто така работи

68
00:03:02,000 --> 00:03:03,190
како локални променливи.

69
00:03:03,190 --> 00:03:06,290
Ако вашиот foo функција или вашиот swap
функција има локални променливи,

70
00:03:06,290 --> 00:03:08,602
како Temp, овие две
заврши на магацинот.

71
00:03:08,602 --> 00:03:11,560
Сега, ние нема да зборуваме премногу за
нив, но овие животната средина променливи

72
00:03:11,560 --> 00:03:15,690
на дното видовме пред некое време кога
Бев futzing на тастатурата еден ден

73
00:03:15,690 --> 00:03:20,050
и јас почнав да пристапуваат работи
како argv 100 или argv 1000,

74
00:03:20,050 --> 00:03:22,320
само elements-- заборавам
на numbers-- но тоа

75
00:03:22,320 --> 00:03:24,330
не требаше да се пристапи од страна на мене.

76
00:03:24,330 --> 00:03:26,581
Почнавме да гледате некои
фанки симболи на екранот.

77
00:03:26,581 --> 00:03:28,330
Тоа беа таканаречените
животната средина променливи

78
00:03:28,330 --> 00:03:32,390
како глобалните поставувања за мојата
програмата или за мојот компјутер, не

79
00:03:32,390 --> 00:03:37,090
поврзани со последните
грешка што зборувавме,

80
00:03:37,090 --> 00:03:39,670
Shellshock, тоа е се
оптоваруваат неколку компјутери.

81
00:03:39,670 --> 00:03:42,960
>> Сега на крај, во денешниот фокус
ние на крајот ќе биде на грамада.

82
00:03:42,960 --> 00:03:44,864
Ова е уште една парче од меморијата.

83
00:03:44,864 --> 00:03:47,030
И во основа сите овие
меморија е истата работа.

84
00:03:47,030 --> 00:03:48,040
Тоа е истиот хардвер.

85
00:03:48,040 --> 00:03:49,956
Ние сме само вид на
лекување на различни кластери

86
00:03:49,956 --> 00:03:51,460
на бајти за различни намени.

87
00:03:51,460 --> 00:03:56,540
Грамада е, исто така, ќе биде каде
променливи и меморијата што ќе го побарате

88
00:03:56,540 --> 00:03:58,810
од оперативниот систем
привремено се чуваат.

89
00:03:58,810 --> 00:04:01,890
>> Но, има еден вид на проблем
тука, како на сликата подразбира.

90
00:04:01,890 --> 00:04:05,261
Ние вид на имаат два
бродови за да се судираат.

91
00:04:05,261 --> 00:04:08,010
Бидејќи, како што имате потреба при користење се повеќе и повеќе
на магацинот, и како што гледаме денес

92
00:04:08,010 --> 00:04:11,800
па натаму, како што се користи се повеќе и повеќе на
грамада, сигурно лоши работи може да се случи.

93
00:04:11,800 --> 00:04:15,054
И навистина, што може да предизвика дека
намерно или ненамерно.

94
00:04:15,054 --> 00:04:16,970
Па cliffhanger последен
време беше оваа програма,

95
00:04:16,970 --> 00:04:20,570
кои не служат било функционална
друга цел, освен да се демонстрира

96
00:04:20,570 --> 00:04:24,750
колку вас, како лошо момче всушност може да се
Предноста на грешки во нечија програма

97
00:04:24,750 --> 00:04:28,460
и да се преземе на програмата, па дури и
целиот компјутерски систем или серверот.

98
00:04:28,460 --> 00:04:31,660
Па само да се загледувам кратко, можете
забележи дека главниот на дното

99
00:04:31,660 --> 00:04:34,510
зема во командната линија
аргументи, како на argv.

100
00:04:34,510 --> 00:04:38,480
И има повик на функција f,
суштина безимени функција наречена

101
00:04:38,480 --> 00:04:40,250
ѓ, а тоа е поминува во avg [1].

102
00:04:40,250 --> 00:04:43,960
>> Значи она што зборот на корисникот видови во во
брза по името на оваа програма,

103
00:04:43,960 --> 00:04:49,310
а потоа оваа произволна функција до
врвот, ѓ, ги зема во низа, АКА char *,

104
00:04:49,310 --> 00:04:51,720
како што ние си почнал да разговараат,
и тоа само го нарекува "бар".

105
00:04:51,720 --> 00:04:53,310
Но, ние би можеле да го наречеме нешто.

106
00:04:53,310 --> 00:04:57,470
А потоа се декларира, во внатрешноста
на f, низа на карактери

107
00:04:57,470 --> 00:04:59,930
наречен c-- 12 такви карактери.

108
00:04:59,930 --> 00:05:03,580
>> Сега, според расказот бев кажувам
пред една момент, што во меморијата

109
00:05:03,580 --> 00:05:06,720
е в, или оние 12
знаци ќе заврши?

110
00:05:06,720 --> 00:05:07,570
Само за да биде јасно.

111
00:05:07,570 --> 00:05:08,070
Да?

112
00:05:08,070 --> 00:05:08,590
>> ПУБЛИКАТА: На оџакот.

113
00:05:08,590 --> 00:05:09,420
>> Дејвид Џ MALAN: На оџакот.

114
00:05:09,420 --> 00:05:10,720
Па в е локална променлива.

115
00:05:10,720 --> 00:05:14,079
Бараме 12 карактери или 12 бајти.

116
00:05:14,079 --> 00:05:16,120
Тие се случува да се заокружи
на т.н. оџак.

117
00:05:16,120 --> 00:05:18,530
Сега конечно е тоа друга функција
тоа е всушност прилично корисна,

118
00:05:18,530 --> 00:05:20,571
но не сум навистина се користи
тоа самите себеси, strncopy.

119
00:05:20,571 --> 00:05:21,550

120
00:05:21,550 --> 00:05:25,200
Тоа значи низа копија, но
само n писма, n карактери.

121
00:05:25,200 --> 00:05:31,990
Па n знаци ќе бидат
копирани од бар во в.

122
00:05:31,990 --> 00:05:32,980
И колку?

123
00:05:32,980 --> 00:05:34,110
Должината на бар.

124
00:05:34,110 --> 00:05:36,330
Значи со други зборови,
една линија, strncopy,

125
00:05:36,330 --> 00:05:39,500
се случува да го копирате
ефикасно бар во в.

126
00:05:39,500 --> 00:05:42,340
>> Сега, само да се вид на се предвиди
Поуката од оваа приказна,

127
00:05:42,340 --> 00:05:44,750
она што е потенцијално проблематични тука?

128
00:05:44,750 --> 00:05:49,710
Иако ние сме проверка на должината
на бар и тоа поминува во strncopy,

129
00:05:49,710 --> 00:05:53,145
Која е вашата стомакот велиш дека е
уште скршени за оваа програма?

130
00:05:53,145 --> 00:05:54,410

131
00:05:54,410 --> 00:05:55,220
Да?

132
00:05:55,220 --> 00:05:57,491
>> ПУБЛИКАТА: Не вклучува
простор за нула карактер.

133
00:05:57,491 --> 00:05:59,990
Дејвид Џ MALAN: не вклучува
простор за нула карактер.

134
00:05:59,990 --> 00:06:02,073
Потенцијално, за разлика од
досегашната практика ние дури и не

135
00:06:02,073 --> 00:06:04,810
имаат толку многу како плус 1 до
го исполниме тоа null карактер.

136
00:06:04,810 --> 00:06:06,649
Но, тоа е уште полошо од тоа.

137
00:06:06,649 --> 00:06:07,940
Што друго што не успеаја да направам?

138
00:06:07,940 --> 00:06:08,432
Да?

139
00:06:08,432 --> 00:06:09,307
>> ПУБЛИКАТА: [Беззвучен]

140
00:06:09,307 --> 00:06:15,440

141
00:06:15,440 --> 00:06:16,440
Дејвид Џ MALAN: Совршена.

142
00:06:16,440 --> 00:06:18,490
Ние сме хард кодирани 12 прилично произволно.

143
00:06:18,490 --> 00:06:19,497

144
00:06:19,497 --> 00:06:21,330
Тоа не е толку
проблем, но факт

145
00:06:21,330 --> 00:06:25,630
дека ние не сме дури и проверка дали
должината на лентата е помалку од 12,

146
00:06:25,630 --> 00:06:28,530
во кој случај ќе биде
безбедно да го стави во меморија

147
00:06:28,530 --> 00:06:30,260
наречен C дека ние сме распределени.

148
00:06:30,260 --> 00:06:32,960
Навистина, ако бар е како
20 карактери,

149
00:06:32,960 --> 00:06:39,010
оваа функција се чини дека копирање
20 ликови од бар во C, а со тоа

150
00:06:39,010 --> 00:06:41,310
земајќи најмалку 8 бајти
дека тоа не треба да биде.

151
00:06:41,310 --> 00:06:42,690
Тоа е импликацијата тука.

152
00:06:42,690 --> 00:06:44,347
>> Значи во кратки, скршени програма.

153
00:06:44,347 --> 00:06:45,180
Не толку голем договор.

154
00:06:45,180 --> 00:06:46,360
Можеби ќе добие сегментација грешка.

155
00:06:46,360 --> 00:06:47,651
Ние сме сите имаа грешки во програми.

156
00:06:47,651 --> 00:06:50,196
Сите ние би можеле да имаат грешки
во програмите од сега.

157
00:06:50,196 --> 00:06:51,320
Но она што е импликација?

158
00:06:51,320 --> 00:06:54,390
Па, тука е zoomed во верзија на
таа слика на меморија мојот компјутер.

159
00:06:54,390 --> 00:06:56,230
Ова е дното на моето оџак.

160
00:06:56,230 --> 00:06:59,644
И навистина, на самото дно е она што е
наречен родител рутински оџакот, фенси начин

161
00:06:59,644 --> 00:07:00,560
да се каже дека е главен.

162
00:07:00,560 --> 00:07:03,772
Така што секој кој се нарекува функцијата
ѓ дека ние зборуваме за.

163
00:07:03,772 --> 00:07:05,230
Значи ова е на дното од оџакот.

164
00:07:05,230 --> 00:07:06,640
Врати адреса е нешто ново.

165
00:07:06,640 --> 00:07:08,810
Тоа е секогаш таму,
секогаш биле во таа слика.

166
00:07:08,810 --> 00:07:10,440
Ние само никогаш не се јавиле внимание на тоа.

167
00:07:10,440 --> 00:07:15,290
Затоа што се покажува начинот на кој функционира е ц
дека кога една функција повикува друга,

168
00:07:15,290 --> 00:07:18,780
не само што аргументи за таа
функција се турка врз оџакот,

169
00:07:18,780 --> 00:07:22,470
не само локално на функцијата
променливи се турка врз оџакот,

170
00:07:22,470 --> 00:07:26,820
нешто што се нарекува врати адреса
исто така, добива се стави врз оџакот.

171
00:07:26,820 --> 00:07:33,330
Поточно, ако главната повици Foo, главниот на
адреса во меморијата, волот нешто,

172
00:07:33,330 --> 00:07:38,240
ефикасно добива се стави врз оџакот
така што кога f е направено негово извршување

173
00:07:38,240 --> 00:07:43,630
знае каде да скокнете назад во текстот
сегмент со цел да се продолжи извршување.

174
00:07:43,630 --> 00:07:47,760
>> Значи, ако ние сме тука концептуално,
Во главната, тогаш ѓ добива се нарекува.

175
00:07:47,760 --> 00:07:50,200
Како ѓ знае кој
на рака контрола назад?

176
00:07:50,200 --> 00:07:52,020
Па, ова малку
Breadcrumb во црвено тука,

177
00:07:52,020 --> 00:07:54,978
наречена повратна адреса, тоа само
проверки, што е тоа враќање адреса?

178
00:07:54,978 --> 00:07:57,039
Ох, дозволете ми да скокнете назад на главната тука.

179
00:07:57,039 --> 00:07:59,080
И тоа е малку
на симплификација,

180
00:07:59,080 --> 00:08:00,750
бидејќи нули и единици
за главните технички

181
00:08:00,750 --> 00:08:01,967
тука во тек сегмент.

182
00:08:01,967 --> 00:08:03,800
Но, тоа е идејата. ѓ
едноставно мора да знаете што

183
00:08:03,800 --> 00:08:06,680
до каде контролата на крајот враќа назад.

184
00:08:06,680 --> 00:08:09,790
>> Но начинот на компјутери
одамна поставени работите

185
00:08:09,790 --> 00:08:12,320
како локални променливи и
аргументи е вака.

186
00:08:12,320 --> 00:08:17,180
Па во врвот на оваа слика
сино е на магацинот рамка за ѓ, така што сите

187
00:08:17,180 --> 00:08:19,630
на меморијата што ѓ
посебно е користење.

188
00:08:19,630 --> 00:08:22,990
Па според тоа, да се забележи дека
бар е во оваа слика.

189
00:08:22,990 --> 00:08:23,980
Бар беше неговиот аргумент.

190
00:08:23,980 --> 00:08:27,240
И ние тврди дека аргументите на
функции се турка кон оџакот.

191
00:08:27,240 --> 00:08:29,910
И в, се разбира, е
Исто така во оваа слика.

192
00:08:29,910 --> 00:08:33,520
>> И само за нотни цели,
забележите во горниот лев агол

193
00:08:33,520 --> 00:08:37,020
е она што ќе биде в заградата 0 и
потоа малку надолу на правото

194
00:08:37,020 --> 00:08:38,220
е в заградата 11.

195
00:08:38,220 --> 00:08:41,240
Значи со други зборови, може да се замисли
дека има мрежа на бајти

196
00:08:41,240 --> 00:08:44,380
таму, од кои првиот е
горниот лев агол, долниот дел кој

197
00:08:44,380 --> 00:08:48,360
е последниот од тие 12 бајти.

198
00:08:48,360 --> 00:08:49,930
>> Но, сега се обидуваат да премотувате напред.

199
00:08:49,930 --> 00:08:55,580
Што ќе се случи ако се помине
во низа бар што е повеќе од в?

200
00:08:55,580 --> 00:08:59,130
И ние не сме проверка дали
тоа е навистина повеќе од 12.

201
00:08:59,130 --> 00:09:03,146
Кој дел од оваа слика се случува да се
се препишани од страна на бајти 0, 1, 2, 3,

202
00:09:03,146 --> 00:09:07,890
точка точка точка, 11, и потоа
лошо, 12, 13 до 19?

203
00:09:07,890 --> 00:09:11,820
Што ќе се случи тука,
ако заклучиме од нарачување

204
00:09:11,820 --> 00:09:14,790
дека в заградата 0 е на врвот
и в заградата 11 е вид на долу

205
00:09:14,790 --> 00:09:15,812
на правото?

206
00:09:15,812 --> 00:09:16,796
Да?

207
00:09:16,796 --> 00:09:19,260
>> ПУБЛИКАТА: Па, тоа се случува
да ја пребришете char * бар.

208
00:09:19,260 --> 00:09:22,260
>> Дејвид Џ MALAN: Да, тоа изгледа како
ви се случува да ја пребришете char * бар.

209
00:09:22,260 --> 00:09:26,245
И уште полошо, ако пратите во навистина долго
стринг, вие може дури да ја пребришете што?

210
00:09:26,245 --> 00:09:27,460

211
00:09:27,460 --> 00:09:28,570
Враќање адреса.

212
00:09:28,570 --> 00:09:31,380
Кои, повторно, е исто како
Breadcrumb да ја каже програма, каде

213
00:09:31,380 --> 00:09:34,060
да се вратам на кога ѓ
се прави се нарекува.

214
00:09:34,060 --> 00:09:37,140
>> Така што лошите момци обично прават
е ако тие се среќаваме програма

215
00:09:37,140 --> 00:09:41,290
дека тие се љубопитни дали е
експлоатирачки, кабриолет на таков начин

216
00:09:41,290 --> 00:09:43,550
дека тој или таа може да се
предностите на таа грешка,

217
00:09:43,550 --> 00:09:45,720
обично тие не се
ова право првиот пат.

218
00:09:45,720 --> 00:09:48,590
Тие едноставно започнете со испраќање на, на пример,
случаен жици во вашата програма,

219
00:09:48,590 --> 00:09:50,260
без разлика дали на тастатура,
или искрено тие веројатно

220
00:09:50,260 --> 00:09:52,740
пишувам малку програма за само
автоматски да се генерираат жици,

221
00:09:52,740 --> 00:09:55,430
и да почне трескањето на вашата програма од
испраќање во многу различни влезови

222
00:09:55,430 --> 00:09:56,340
во различни должини.

223
00:09:56,340 --> 00:09:58,990
>> Штом вашата програма се урна,
тоа е неверојатно нешто.

224
00:09:58,990 --> 00:10:01,020
Затоа што тој мисли
или таа откри

225
00:10:01,020 --> 00:10:02,660
она што е веројатно навистина е бубачка.

226
00:10:02,660 --> 00:10:05,830
А потоа тие можат да добијат повеќе умен
и почна да се фокусира потесно

227
00:10:05,830 --> 00:10:07,420
за тоа како да ги искористат дека бубачка.

228
00:10:07,420 --> 00:10:11,480
Особено, она што тој или таа може да
направите е да испратите, во најдобар случај, здраво.

229
00:10:11,480 --> 00:10:12,210
Нема ништо страшно.

230
00:10:12,210 --> 00:10:14,750
Тоа е стринг кој е доволно кратко.

231
00:10:14,750 --> 00:10:18,100
Но, што ако тој или таа праќа,
и ние ќе го генерализира како,

232
00:10:18,100 --> 00:10:20,890
напад code-- така нули
и оние кои ги прават работите

233
00:10:20,890 --> 00:10:25,150
како rm-rf, кој се отстрани сè
од хард диск или испрати спам

234
00:10:25,150 --> 00:10:27,000
или некако го нападне машина?

235
00:10:27,000 --> 00:10:29,570
>> Значи, ако секој од овие
писма А само претставува,

236
00:10:29,570 --> 00:10:32,380
Концептуално, напад, напад,
напад, напад, некои лоши код

237
00:10:32,380 --> 00:10:36,410
дека некој друг напишал, но
ако тоа лице е доволно паметни

238
00:10:36,410 --> 00:10:40,790
не само да ги вклучи сите
на оние RM-Едукација, но, исто така,

239
00:10:40,790 --> 00:10:46,100
има неговата или нејзината последните неколку бајти
има голем број што одговара

240
00:10:46,100 --> 00:10:50,540
на адресата на неговиот
или нејзината сопствена напад кодот

241
00:10:50,540 --> 00:10:53,820
дека тој или таа помина во само
преку обезбедување на тоа во конзолата,

242
00:10:53,820 --> 00:10:58,760
можете успешно да трик на компјутер
во забележи кога ѓ се прави извршување,

243
00:10:58,760 --> 00:11:02,400
ох, тоа е време за мене да скокаат
назад кон црвениот враќање адреса.

244
00:11:02,400 --> 00:11:06,070
Туку затоа што тој или таа има некако
поклопуваа дека враќањето адреса

245
00:11:06,070 --> 00:11:09,602
со свои број,
и тие се доволно паметни

246
00:11:09,602 --> 00:11:11,560
да ги конфигурирате што
број да се однесуваат, како што

247
00:11:11,560 --> 00:11:13,740
види во супер врвот
лев агол таму,

248
00:11:13,740 --> 00:11:18,020
вистинската адреса во компјутер
меморија на некои од нивните напад код,

249
00:11:18,020 --> 00:11:21,740
лошо момче може да трик на компјутер
во извршување на неговата или нејзината сопствена код.

250
00:11:21,740 --> 00:11:23,700
>> И тој код, пак, може да биде ништо.

251
00:11:23,700 --> 00:11:26,120
Тоа е обично се нарекува
школка код, што е само

252
00:11:26,120 --> 00:11:29,030
начин да се каже дека тоа не е
генерално нешто едноставно како rm-rf.

253
00:11:29,030 --> 00:11:32,340
Тоа е всушност нешто како баш,
или вистински програма која му дава

254
00:11:32,340 --> 00:11:37,230
или нејзините програмски контрола да се изврши
нешто друго што тие сакаат да.

255
00:11:37,230 --> 00:11:40,210
Значи во кратки, сето ова
произлегува од едноставниот факт

256
00:11:40,210 --> 00:11:44,490
дека овој баг се вклучени не проверка
границите на вашиот низа.

257
00:11:44,490 --> 00:11:47,250
И поради начинот на кој
компјутери работа е тоа што тие

258
00:11:47,250 --> 00:11:49,430
користење на магацинот од
ефикасно, концептуално,

259
00:11:49,430 --> 00:11:54,830
дното на нагоре, но потоа на елементи
ве одвлече во магацинот расте врвот надолу,

260
00:11:54,830 --> 00:11:56,624
ова е неверојатно проблематична.

261
00:11:56,624 --> 00:11:58,290
Сега, постојат начини да се работи околу тоа.

262
00:11:58,290 --> 00:12:00,800
И искрено, постојат јазици
со кој да работи околу ова.

263
00:12:00,800 --> 00:12:03,100
Јава е имун, на пример,
да ова конкретно прашање.

264
00:12:03,100 --> 00:12:04,110
Бидејќи тие не ви даде совети.

265
00:12:04,110 --> 00:12:05,943
Тие не ви даде
директни приклучоци за мемориски адреси.

266
00:12:05,943 --> 00:12:08,560
Значи со оваа моќ што ја имаме
да се допре нешто во меморијата

267
00:12:08,560 --> 00:12:11,580
ние сакаме доаѓа, очигледно, голем ризик.

268
00:12:11,580 --> 00:12:12,430
>> Па да се внимава надвор.

269
00:12:12,430 --> 00:12:14,596
Ако, искрено, во месеците
или годините што доаѓаат, во секое време

270
00:12:14,596 --> 00:12:17,740
ќе прочитате за некои експлоатација
на програма или сервер,

271
00:12:17,740 --> 00:12:22,370
Ако некогаш сте се види навестување на нешто
како на buffer overflow напади,

272
00:12:22,370 --> 00:12:25,390
или магацинот претекување е друг вид
на напад, слични во духот,

273
00:12:25,390 --> 00:12:28,770
колку што инспирира на веб страницата
име, ако го знаете,

274
00:12:28,770 --> 00:12:33,170
тоа е сите зборуваат за само
преплавени со големина на некои карактер

275
00:12:33,170 --> 00:12:36,200
низа или низа некои поопшто.

276
00:12:36,200 --> 00:12:38,822
Било какви прашања, тогаш, за ова?

277
00:12:38,822 --> 00:12:39,780
Не се обиде ова дома.

278
00:12:39,780 --> 00:12:41,620

279
00:12:41,620 --> 00:12:42,300
>> Во ред.

280
00:12:42,300 --> 00:12:47,270
Па Примерок досега е нашата нова
пријател со тоа што може да се алоцира меморија

281
00:12:47,270 --> 00:12:50,540
дека ние не мора да знаете во
однапред дека ние сакаме ние немаме

282
00:12:50,540 --> 00:12:52,920
на хард код во нашата
програма броеви како 12.

283
00:12:52,920 --> 00:12:55,550
Еднаш на корисникот ни кажува колку
податоци тој или таа сака да влез,

284
00:12:55,550 --> 00:12:58,000
можеме да Примерок дека многу меморија.

285
00:12:58,000 --> 00:13:01,484
>> Па Примерок што се испоставува, на
мера што сме го користат,

286
00:13:01,484 --> 00:13:03,900
експлицитно последен пат, а потоа
вие момци се го користите

287
00:13:03,900 --> 00:13:08,160
за getstring знае за
неколку недели, сите на меморија Примерок на

288
00:13:08,160 --> 00:13:09,820
доаѓа од т.н. грамада.

289
00:13:09,820 --> 00:13:13,852
И тоа е причината зошто getstring, на пример,
може да се алоцира меморија динамички

290
00:13:13,852 --> 00:13:16,060
без да се знае она што си
случува да напишеш во однапред,

291
00:13:16,060 --> 00:13:21,520
рака ќе се врати на покажувачот во тој меморија,
и дека меморијата е сеуште твое да го задржи,

292
00:13:21,520 --> 00:13:24,080
дури и по getstring враќа.

293
00:13:24,080 --> 00:13:27,450
Бидејќи се потсетиме на крајот на краиштата дека
магацинот постојано одат нагоре и надолу,

294
00:13:27,450 --> 00:13:27,950
нагоре и надолу.

295
00:13:27,950 --> 00:13:30,230
И штом тоа оди
долу, тоа значи дека на мемориската

296
00:13:30,230 --> 00:13:33,030
оваа функција се користи треба
не се користи од страна на некој друг.

297
00:13:33,030 --> 00:13:34,570
Тоа е ѓубре вредности сега.

298
00:13:34,570 --> 00:13:36,120
>> Но, на грамада е тука.

299
00:13:36,120 --> 00:13:39,360
И она што е убаво за Примерок е дека
кога Примерок доделува меморија до тука,

300
00:13:39,360 --> 00:13:42,070
тоа не е влијание, за
најголем дел, од магацинот.

301
00:13:42,070 --> 00:13:46,000
И така било функција да пристапите
меморија која е malloc'd,

302
00:13:46,000 --> 00:13:49,120
дури и од страна на функција како getstring,
дури и откако ќе се враќа.

303
00:13:49,120 --> 00:13:51,700
>> Сега, обратно од Примерок е бесплатно.

304
00:13:51,700 --> 00:13:53,900
И навистина, правило
треба да започне усвојување

305
00:13:53,900 --> 00:13:58,950
е било, било, во секое време да го користите Примерок
можете сами да користат бесплатен, на крајот,

306
00:13:58,950 --> 00:14:00,280
на истиот покажувач.

307
00:14:00,280 --> 00:14:03,289
Сето ова време ние сме биле пишување
кабриолет, кабриолет код, за многу причини.

308
00:14:03,289 --> 00:14:05,580
Но, еден од кои е
со користење на CS50 библиотека, која

309
00:14:05,580 --> 00:14:09,010
сам по себе е намерно
кабриолет, тоа протекување меморија.

310
00:14:09,010 --> 00:14:11,410
Секое време си се нарекува getstring
во текот на изминатите неколку недели

311
00:14:11,410 --> 00:14:13,870
бараме оперативниот
систем, Линукс, за меморија.

312
00:14:13,870 --> 00:14:15,780
А ти никогаш не еднаш го даде назад.

313
00:14:15,780 --> 00:14:17,730
И ова не е,
пракса, добра работа.

314
00:14:17,730 --> 00:14:20,330
>> И Valgrind, еден од
алатки воведе во Pset 4,

315
00:14:20,330 --> 00:14:22,900
е за сите да ви помогнеме,
сега се најдат грешки како што.

316
00:14:22,900 --> 00:14:27,060
Но, за среќа за Pset 4 не треба
да се користи CS50 библиотека или getstring.

317
00:14:27,060 --> 00:14:31,220
Така било грешки поврзани со меморијата се
во крајна линија ќе биде своја.

318
00:14:31,220 --> 00:14:34,060
>> Па Примерок е повеќе од само
погоден за оваа намена.

319
00:14:34,060 --> 00:14:37,420
Можеме да всушност сега реши
фундаментално различни проблеми,

320
00:14:37,420 --> 00:14:41,640
и фундаментално решавање на проблемите повеќе
ефикасно како неделно нула ветување.

321
00:14:41,640 --> 00:14:44,720
Досега ова е најсекси
податочна структура имавме.

322
00:14:44,720 --> 00:14:47,804
И од страна на податоци структура Јас само значи
начин на конципирање на меморија

323
00:14:47,804 --> 00:14:50,720
на начин што оди подалеку од само велејќи:
ова е int, ова е знак.

324
00:14:50,720 --> 00:14:52,930
Ние може да почнат да се кластер работите заедно.

325
00:14:52,930 --> 00:14:54,460
>> Па низа изгледаше вака.

326
00:14:54,460 --> 00:14:57,270
И она што беше клучен за околу еден
низа е тоа што ви дава

327
00:14:57,270 --> 00:14:59,724
назад-до-назад делови од
меморија, од кои секој

328
00:14:59,724 --> 00:15:02,765
ќе биде од ист тип, цел број,
int, int, int, или знак, знак, знак,

329
00:15:02,765 --> 00:15:03,330
знак.

330
00:15:03,330 --> 00:15:04,496
Но, има неколку недостатоци.

331
00:15:04,496 --> 00:15:06,570
Ова на пример, е
низа на големината шест.

332
00:15:06,570 --> 00:15:10,650
Да претпоставиме дека се пополни оваа низа со шест
броеви и потоа, за било кои причини,

333
00:15:10,650 --> 00:15:13,187
Вашиот корисникот сака да даде
ќе седми број.

334
00:15:13,187 --> 00:15:14,020
Каде ќе го стави?

335
00:15:14,020 --> 00:15:15,490

336
00:15:15,490 --> 00:15:18,990
>> Она што е решението ако имате
создаде низа на магацинот,

337
00:15:18,990 --> 00:15:22,030
на пример, само со недела
две нотација дека ќе воведе,

338
00:15:22,030 --> 00:15:23,730
квадратни загради со голем број внатре?

339
00:15:23,730 --> 00:15:25,160

340
00:15:25,160 --> 00:15:27,260
Па, имаш шест
броеви во овие кутии.

341
00:15:27,260 --> 00:15:28,530
Што ќе биде вашиот инстинкт?

342
00:15:28,530 --> 00:15:29,973
Каде што ќе сакате да го стави?

343
00:15:29,973 --> 00:15:30,860
>> ПУБЛИКАТА: [Беззвучен]

344
00:15:30,860 --> 00:15:31,315
>> Дејвид Џ MALAN: Молам?

345
00:15:31,315 --> 00:15:32,380
>> ПУБЛИКАТА: Стави ја на крај.

346
00:15:32,380 --> 00:15:33,796
>> Дејвид Џ MALAN: Стави ја на крај.

347
00:15:33,796 --> 00:15:35,880
Па само во текот на правото,
надвор од ова поле.

348
00:15:35,880 --> 00:15:38,710
Кој ќе биде убаво, но тоа
испоставува дека не може да го стори тоа.

349
00:15:38,710 --> 00:15:41,350
Бидејќи ако не го праша
за ова парче од меморијата,

350
00:15:41,350 --> 00:15:44,490
тоа би можело да биде случајно што ова
се користи од страна на некои други променливи

351
00:15:44,490 --> 00:15:45,030
заедно.

352
00:15:45,030 --> 00:15:49,210
Сетам една недела или така кога ние положи
надвор Zamyla и Davin и Габе имиња

353
00:15:49,210 --> 00:15:49,930
во меморијата.

354
00:15:49,930 --> 00:15:51,638
Тие беа буквално
назад да се врати за да се врати.

355
00:15:51,638 --> 00:15:53,550
Па не можеме да мора да
верувам дека она што го

356
00:15:53,550 --> 00:15:55,800
овде е на располагање за мене да го користите.

357
00:15:55,800 --> 00:15:56,990
>> Па што друго би можеле да направите?

358
00:15:56,990 --> 00:16:00,282
Па, откако ќе реализираат
треба низа на големината седум,

359
00:16:00,282 --> 00:16:02,490
може само да се создаде
спектар на големината седум потоа користете

360
00:16:02,490 --> 00:16:05,950
на за телефонска линија или додека јамка,
го ископирате во новата низа,

361
00:16:05,950 --> 00:16:09,680
и потоа некако само да се ослободи од
оваа низа или само престане да го користи.

362
00:16:09,680 --> 00:16:12,130
Но, тоа не е особено ефикасен.

363
00:16:12,130 --> 00:16:15,340
На кратко, низи, не дозволувајте
можете динамично менување на големината.

364
00:16:15,340 --> 00:16:17,900
>> Значи од една страна ќе се
случаен пристап, кој е неверојатен.

365
00:16:17,900 --> 00:16:20,108
Бидејќи тоа ни овозможува да се прават работите
како поделба и освојување,

366
00:16:20,108 --> 00:16:23,100
бинарни пребарување, од кои сите ние сме
зборуваше за на екранот овде.

367
00:16:23,100 --> 00:16:24,950
Но, сте се наслика во еден агол.

368
00:16:24,950 --> 00:16:27,810
Веднаш штом ќе го погоди
на крајот на вашиот низа,

369
00:16:27,810 --> 00:16:29,980
што треба да направите многу
скапи работа

370
00:16:29,980 --> 00:16:33,910
или да напишете целиот куп на код
До сега се справи со тој проблем.

371
00:16:33,910 --> 00:16:36,680
>> Па што ако, наместо имавме
нешто што се нарекува листа,

372
00:16:36,680 --> 00:16:38,820
или поврзана листа особено?

373
00:16:38,820 --> 00:16:41,930
Што ако наместо
правоаголници да се врати назад да се врати,

374
00:16:41,930 --> 00:16:45,730
имаме правоаголници кои оставаат малку
малку шаване соба во меѓу нив?

375
00:16:45,730 --> 00:16:49,670
И иако сум подготвен овој
слика или прилагодени оваа слика

376
00:16:49,670 --> 00:16:54,696
од еден од текстовите тука за да се врати на
назад да се врати многу уреден, во реалноста,

377
00:16:54,696 --> 00:16:56,820
еден од оние правоаголници
би можело да биде тука во меморијата.

378
00:16:56,820 --> 00:16:58,028
Еден од нив би можел да биде тука.

379
00:16:58,028 --> 00:17:00,420
Еден од нив би можел да биде тука,
овде, и така натаму.

380
00:17:00,420 --> 00:17:02,910
>> Но, што ако ние привлече,
во овој случај, стрели

381
00:17:02,910 --> 00:17:05,650
дека некако ги поврзат овие
правоаголници заедно?

382
00:17:05,650 --> 00:17:08,170
Всушност, видовме технички
инкарнација на стрела.

383
00:17:08,170 --> 00:17:09,839

384
00:17:09,839 --> 00:17:13,710
Што сме се користи во последниве
дена дека, под хаубата,

385
00:17:13,710 --> 00:17:15,210
е претставник на стрела?

386
00:17:15,210 --> 00:17:16,290

387
00:17:16,290 --> 00:17:17,349
Покажувач, нели?

388
00:17:17,349 --> 00:17:19,780
>> Па што ако, наместо
само чување на броеви,

389
00:17:19,780 --> 00:17:23,130
како 9, 17, 22, 26, 34,
што ако ние не се чуваат

390
00:17:23,130 --> 00:17:27,079
само број, но покажувач
до секој таков број?

391
00:17:27,079 --> 00:17:30,690
Така што многу како тебе би се нишка на
игла низ целиот куп на ткаенина,

392
00:17:30,690 --> 00:17:32,950
некако врзување работи
заедно, на сличен начин може да

393
00:17:32,950 --> 00:17:35,550
ние со покажувачи, како
инкарниран со стрелка тука,

394
00:17:35,550 --> 00:17:38,550
вид на ткаат заедно
овие индивидуални правоаголници

395
00:17:38,550 --> 00:17:41,780
од страна на ефикасно користење на покажувач
до секој број кој

396
00:17:41,780 --> 00:17:46,065
укажува на некои следната број, односно
укажува, пак, некои следниот број?

397
00:17:46,065 --> 00:17:47,940
Значи со други зборови, она што
ако ние всушност сакаа

398
00:17:47,940 --> 00:17:49,820
да се спроведе вакво нешто?

399
00:17:49,820 --> 00:17:53,610
И за жал, овие правоаголници,
барем на еден со 9, 17, 22,

400
00:17:53,610 --> 00:17:57,040
и така натаму, овие се веќе
убав плоштади со еден броеви.

401
00:17:57,040 --> 00:17:59,960
На дното, правоаголник
под 9, на пример,

402
00:17:59,960 --> 00:18:04,330
го претставува она што треба
да биде покажувач, 32 бита.

403
00:18:04,330 --> 00:18:09,460
Сега, јас не сум свесен за било кој тип на податоци
во C која ви дава не само int

404
00:18:09,460 --> 00:18:11,630
но покажувач заедно.

405
00:18:11,630 --> 00:18:15,020
>> Значи она што е решението ако сакаме
да измисли свој одговор на ова?

406
00:18:15,020 --> 00:18:15,760
Да?

407
00:18:15,760 --> 00:18:16,640
>> ПУБЛИКАТА: [Беззвучен]

408
00:18:16,640 --> 00:18:17,360
>> Дејвид Џ MALAN: Што е тоа?

409
00:18:17,360 --> 00:18:17,880
>> ПУБЛИКАТА: Нова структура.

410
00:18:17,880 --> 00:18:19,590
>> Дејвид Џ MALAN: Да, па зошто
да не се создаде нова структура,

411
00:18:19,590 --> 00:18:20,920
или во C, на struct?

412
00:18:20,920 --> 00:18:25,990
Видовме structs пред, ако на кратко,
каде што се занимаваа со структурата на учениците

413
00:18:25,990 --> 00:18:27,780
вака, кој имаше име и куќа.

414
00:18:27,780 --> 00:18:31,980
Во Pset 3 Збег сте користеле целина
куп на structs-- GRect и GOvals

415
00:18:31,980 --> 00:18:34,810
дека Стенфорд создаден за да се
кластер информации заедно.

416
00:18:34,810 --> 00:18:38,580
Па што ако се земе истата идеја
клучни зборови "typedef" и "struct"

417
00:18:38,580 --> 00:18:42,890
а потоа некои студент специфични нешта,
и се развива ова на следниов начин:

418
00:18:42,890 --> 00:18:46,210
typedef struct node-- и јазол е
само многу генерички компјутерски науки

419
00:18:46,210 --> 00:18:49,980
термин за нешто во податочна структура,
контејнер во податоци структура.

420
00:18:49,980 --> 00:18:53,900
А јазол тврдам се случува да имаат
на int n, сосема јасна,

421
00:18:53,900 --> 00:18:58,810
а потоа малку повеќе cryptically,
оваа втора линија, struct јазол * следната.

422
00:18:58,810 --> 00:19:01,300
Но за помалку технички термини,
што е тоа втора линија

423
00:19:01,300 --> 00:19:02,980
на код во внатрешноста на големи загради?

424
00:19:02,980 --> 00:19:03,737
Да?

425
00:19:03,737 --> 00:19:04,851
>> ПУБЛИКАТА: [Беззвучен]

426
00:19:04,851 --> 00:19:06,600
Дејвид Џ MALAN: А
Покажувач на друг јазол.

427
00:19:06,600 --> 00:19:09,910
Значи, мора да признаеме, синтакса малку криптичната.

428
00:19:09,910 --> 00:19:13,250
Но, ако го чита буквално,
следната е името на променливата.

429
00:19:13,250 --> 00:19:14,410
Каков е нејзиниот тип на податок?

430
00:19:14,410 --> 00:19:18,206
Тоа е малку опширниот тоа време,
но тоа е од типот struct јазол *.

431
00:19:18,206 --> 00:19:22,960
Секое време видовме нешто ѕвезда, кој
значи дека е покажувачот во тој тип на податок.

432
00:19:22,960 --> 00:19:26,810
Значи следниот е очигледно
Покажувач на struct јазол.

433
00:19:26,810 --> 00:19:28,310
>> Сега, она што е struct јазол?

434
00:19:28,310 --> 00:19:31,044
Па, забележите ќе видите тие
истите зборови на горниот десен агол.

435
00:19:31,044 --> 00:19:33,960
И навистина, исто така, види на зборот
"Јазол" овде во долниот лев агол.

436
00:19:33,960 --> 00:19:35,640
И ова е всушност само погодност.

437
00:19:35,640 --> 00:19:39,930
Забележете дека во нашиот студент дефиниција
има зборот "студент" само еднаш.

438
00:19:39,930 --> 00:19:42,510
И тоа е затоа што на студентот
објект не е авто-референтен.

439
00:19:42,510 --> 00:19:45,340
Нема ништо во внатрешноста на студент
што треба да се укаже на друг ученик,

440
00:19:45,340 --> 00:19:45,610
persay.

441
00:19:45,610 --> 00:19:47,630
Тоа би било вид на
чудно во реалниот свет.

442
00:19:47,630 --> 00:19:50,880
>> Но, со еден јазол во поврзани
листа, ние сакаме еден јазол

443
00:19:50,880 --> 00:19:53,970
да биде референцијално на сличен објект.

444
00:19:53,970 --> 00:19:57,900
И така забележите промена тука не е
само она што е внатре во големи загради.

445
00:19:57,900 --> 00:20:00,800
Но, ние го додадете зборот "јазол"
на врвот, како и

446
00:20:00,800 --> 00:20:02,930
додавање на тоа да на дното
наместо на "студент".

447
00:20:02,930 --> 00:20:06,000
И ова е само технички детали
така што, повторно, вашите податоци структура

448
00:20:06,000 --> 00:20:11,380
може да биде авто-референтен, така што
јазол може да укажуваат на уште еден таков јазол.

449
00:20:11,380 --> 00:20:13,840
>> Па што е ова на крајот
ќе значи за нас?

450
00:20:13,840 --> 00:20:17,560
Па, еден, овој материјал во
е содржината на нашите јазол.

451
00:20:17,560 --> 00:20:19,360
Ова нешто овде,
горниот десен агол, е толку

452
00:20:19,360 --> 00:20:20,860
дека, повторно, ние може да се однесува на нас самите.

453
00:20:20,860 --> 00:20:23,401
А потоа најоддалечените работи,
иако јазол е нов термин,

454
00:20:23,401 --> 00:20:25,500
можеби, тоа е сепак
исто како студент и што

455
00:20:25,500 --> 00:20:27,520
беше под хаубата во SPL.

456
00:20:27,520 --> 00:20:31,095
>> Значи, ако ние сега сака да започне
спроведување на овој поврзана листа,

457
00:20:31,095 --> 00:20:33,220
како можеме да ги претвориме
нешто како ова да кодот?

458
00:20:33,220 --> 00:20:35,350
Па, ајде да ја видите
пример за програма со која

459
00:20:35,350 --> 00:20:36,840
всушност користи поврзана листа.

460
00:20:36,840 --> 00:20:40,870
Меѓу денешните дистрибуција код
е програма наречена Листа на нула.

461
00:20:40,870 --> 00:20:44,980
И ако јас ја извршите оваа Јас создаде супер
едноставен GUI, графички кориснички интерфејс,

462
00:20:44,980 --> 00:20:46,460
но тоа е навистина само printf.

463
00:20:46,460 --> 00:20:50,930
И сега сум дадени себе неколку мени
options-- Избриши, Insert, пребарување,

464
00:20:50,930 --> 00:20:51,750
и Траверс.

465
00:20:51,750 --> 00:20:52,630
И да престанам.

466
00:20:52,630 --> 00:20:55,970
Ова се само заеднички операции на
податоци структура позната како линк листа.

467
00:20:55,970 --> 00:20:58,409
>> Сега, Избриши се случува да се
избришете некој број од листата.

468
00:20:58,409 --> 00:21:00,200
Вметнете се случува да додадете
голем број на листата.

469
00:21:00,200 --> 00:21:02,181
Пребарување се случува да се погледне
за бројот на листата.

470
00:21:02,181 --> 00:21:04,930
И напречни е само стилизиран начин
каже, прошетка низ листата,

471
00:21:04,930 --> 00:21:06,245
печати ја надвор, но тоа е тоа.

472
00:21:06,245 --> 00:21:07,720
Не го менува во било кој начин.

473
00:21:07,720 --> 00:21:08,570
>> Па ајде да се обидеме ова.

474
00:21:08,570 --> 00:21:10,160
Ајде да одиме напред и тип 2.

475
00:21:10,160 --> 00:21:12,710
А потоа јас ќе одам да
внесете го бројот, велат 9.

476
00:21:12,710 --> 00:21:13,620
Enter.

477
00:21:13,620 --> 00:21:17,480
И сега мојата програма е само
програмирани да се каже, листата сега е 9.

478
00:21:17,480 --> 00:21:20,190
Сега, ако јас одам напред и
ставајте повторно, да

479
00:21:20,190 --> 00:21:23,680
мене оди напред и одзумирате и тип во 17.

480
00:21:23,680 --> 00:21:25,770
Сега мојата листа е 9, тогаш 17.

481
00:21:25,770 --> 00:21:27,750
Ако го направам внесете повторно, да прескокнете едно.

482
00:21:27,750 --> 00:21:32,400
Наместо 22, како на сликата ние сме
гледа во тука, дозволете ми скок напред

483
00:21:32,400 --> 00:21:34,630
и вметнете 26 следната.

484
00:21:34,630 --> 00:21:36,230
Па ќе одам да напишеш 26.

485
00:21:36,230 --> 00:21:37,755
Листата е како што се очекува.

486
00:21:37,755 --> 00:21:40,630
Но, сега, само за да се види дали овој код
се случува да се биде флексибилен, дозволете ми сега

487
00:21:40,630 --> 00:21:43,520
тип 22, кои најмалку
Концептуално, ако ние сме

488
00:21:43,520 --> 00:21:46,520
Задржување на оваа сортирани, што е навистина
ќе биде уште еден гол токму сега,

489
00:21:46,520 --> 00:21:48,690
треба да одат во меѓу 17 и 26.

490
00:21:48,690 --> 00:21:50,270
Па јас хит Enter.

491
00:21:50,270 --> 00:21:51,380
Всушност, тоа функционира.

492
00:21:51,380 --> 00:21:54,950
И така сега дозволете ми да го вметнете
последните, по сликата, 34.

493
00:21:54,950 --> 00:21:55,450
>> Во ред.

494
00:21:55,450 --> 00:21:58,980
Па за сега дозволете ми да пропише дека
Бришење и Траверс и Барај направи,

495
00:21:58,980 --> 00:21:59,760
всушност, работат.

496
00:21:59,760 --> 00:22:04,180
Всушност, ако јас се кандидира Барај, да
пребарување на број 22, Enter.

497
00:22:04,180 --> 00:22:05,010
Го најде 22.

498
00:22:05,010 --> 00:22:07,580
Значи тоа е она што ова
Програмата Листа Нулта прави.

499
00:22:07,580 --> 00:22:10,230
>> Но, она што е, всушност, се случува
на која спроведува ова?

500
00:22:10,230 --> 00:22:14,530
Па, прво јас би можеле да имаат, и навистина
Јас немам, фајл наречен list0.h.

501
00:22:14,530 --> 00:22:16,540

502
00:22:16,540 --> 00:22:20,690
И некаде таму е овој
линија, typedef, struct јазол,

503
00:22:20,690 --> 00:22:24,850
тогаш имам големи загради, int n и
тогаш struct-- она ​​што беше дефиниција?

504
00:22:24,850 --> 00:22:26,530

505
00:22:26,530 --> 00:22:28,545
Struct јазол следната.

506
00:22:28,545 --> 00:22:29,920

507
00:22:29,920 --> 00:22:31,045
Значи ние треба ѕвездата.

508
00:22:31,045 --> 00:22:33,420
Сега технички да се влезе во
навика за цртање овде.

509
00:22:33,420 --> 00:22:35,670
Можете да видите учебници и
онлајн референци го направи таму.

510
00:22:35,670 --> 00:22:36,660
Тоа е функционално еквивалентни.

511
00:22:36,660 --> 00:22:37,980
Всушност, ова е малку повеќе типични.

512
00:22:37,980 --> 00:22:40,563
Но, јас ќе биде во согласност со она што
ние го сторивме последен пат и го направите тоа.

513
00:22:40,563 --> 00:22:42,350
А потоа на крај, јас ќе одам да го направите тоа.

514
00:22:42,350 --> 00:22:45,550
>> Значи во заглавието на датотеката
некаде, во list0.h

515
00:22:45,550 --> 00:22:49,200
денес е ова struct дефиниција,
а можеби и некои други работи.

516
00:22:49,200 --> 00:22:52,580
Во меѓувреме, во list0c има
ќе биде неколку работи.

517
00:22:52,580 --> 00:22:54,740
Но, ние се случува да се само
проектот и да не заврши ова.

518
00:22:54,740 --> 00:22:59,690
List0.h е датотека сакам
да се вклучат во мојот Ц датотека.

519
00:22:59,690 --> 00:23:03,910
А потоа во некој момент јас сум
ќе мора int, главно, неважечки.

520
00:23:03,910 --> 00:23:06,530
А потоа јас ќе одам да
имаат некои to-do е овде.

521
00:23:06,530 --> 00:23:10,620
Јас сум исто така се случува да имаат
прототип, како неважечки, пребарување, int,

522
00:23:10,620 --> 00:23:13,610
n, чија цел во животот е
да пребарувате за елемент.

523
00:23:13,610 --> 00:23:18,310
И тогаш овде тврдам во
денес код, празнина, пребарување, int, n,

524
00:23:18,310 --> 00:23:21,020
нема запирка, но отворена големи загради.

525
00:23:21,020 --> 00:23:25,049
И сега сакам да некако пребарување
за елемент во листата.

526
00:23:25,049 --> 00:23:27,340
Но, ние немаме доволно
информации на екранот сеуште.

527
00:23:27,340 --> 00:23:29,800
Не сум всушност
претставен на листата себе.

528
00:23:29,800 --> 00:23:33,070
Значи еден начин ние би можеле да се имплементираат
поврзана листа во програма

529
00:23:33,070 --> 00:23:37,520
е јас вид на сакаат да направат нешто
како изјавувам поврзана листа тука.

530
00:23:37,520 --> 00:23:40,520
За едноставност, јас ќе одам да се направи
оваа глобална, иако во принцип ние

531
00:23:40,520 --> 00:23:41,645
не треба да го направите тоа премногу.

532
00:23:41,645 --> 00:23:43,260
Но, тоа ќе се поедностави овој пример.

533
00:23:43,260 --> 00:23:45,890
Па сакам да се изјаснат
поврзана листа тука.

534
00:23:45,890 --> 00:23:47,010
Сега, како би можел да го направам тоа?

535
00:23:47,010 --> 00:23:48,810

536
00:23:48,810 --> 00:23:50,750
>> Тука е слика на поврзани листа.

537
00:23:50,750 --> 00:23:53,030
И јас навистина не
знае во моментот како

538
00:23:53,030 --> 00:23:56,710
Одам да се обратите за застапување
толку многу работи со само еден

539
00:23:56,710 --> 00:23:58,040
променлива во меморијата.

540
00:23:58,040 --> 00:23:59,160
Но се сетам момент.

541
00:23:59,160 --> 00:24:00,830
Сето ова време имавме
жици, кои потоа

542
00:24:00,830 --> 00:24:02,913
открива дека низи на
ликови, кои потоа

543
00:24:02,913 --> 00:24:05,740
откри само да биде покажувач
на првиот карактер

544
00:24:05,740 --> 00:24:08,890
во низа на карактери
тоа е нула прекинат.

545
00:24:08,890 --> 00:24:13,530
Значи со таа логика, а со тоа
слика вид на засејување своите мисли,

546
00:24:13,530 --> 00:24:17,964
она што треба ние всушност пишува во нашата
кодот да претставуваат поврзана листа?

547
00:24:17,964 --> 00:24:21,130
Колку од овие информации ни се потребни
да го фати во C код, што би рекол?

548
00:24:21,130 --> 00:24:22,654

549
00:24:22,654 --> 00:24:23,154
Да?

550
00:24:23,154 --> 00:24:24,738
>> ПУБЛИКАТА: Ние треба покажувач на еден јазол.

551
00:24:24,738 --> 00:24:26,237
Дејвид Џ MALAN: покажувач на еден јазол.

552
00:24:26,237 --> 00:24:29,320
Особено, кој јазол би Вашиот
инстинкти биде да се задржи покажувач?

553
00:24:29,320 --> 00:24:30,026
>> ПУБЛИКАТА: Првиот јазол.

554
00:24:30,026 --> 00:24:31,942
>> Дејвид Џ MALAN: Да,
веројатно само првиот.

555
00:24:31,942 --> 00:24:34,030
И ќе забележите, првата
јазол е поинаков облик.

556
00:24:34,030 --> 00:24:37,690
Тоа е само половина од големината на struct,
затоа што тоа е навистина само покажувач.

557
00:24:37,690 --> 00:24:44,650
Значи она што навистина може да направите е да се изјасни
поврзана листа да биде од типот јазол *.

558
00:24:44,650 --> 00:24:47,780
И ајде да го наречеме прв
и да се иницијализира на нула.

559
00:24:47,780 --> 00:24:49,910
Значи нула, повторно, е што доаѓаат
во сликата тука.

560
00:24:49,910 --> 00:24:53,620
Не само што е null користи како како посебен
повратната вредност за нешта како getstring

561
00:24:53,620 --> 00:24:57,770
и Примерок, нула е исто така на нула
покажувачот, недостатокот на покажувачот,

562
00:24:57,770 --> 00:24:58,430
ако сакате.

563
00:24:58,430 --> 00:25:00,309
Тоа само значи ништо не е уште тука.

564
00:25:00,309 --> 00:25:02,100
Сега прво, јас би можеле да го
ова го нарече нешто.

565
00:25:02,100 --> 00:25:04,200
Можев да го нарече "листа"
или било кој број на други работи.

566
00:25:04,200 --> 00:25:06,960
Но јас сум нарекувајќи го "прва", така што
тоа линии со оваа слика.

567
00:25:06,960 --> 00:25:10,280
Па само како стринг може да се претстави
со адреса на својот прв бајт,

568
00:25:10,280 --> 00:25:11,280
па може да биде поврзана листа.

569
00:25:11,280 --> 00:25:13,480
И ќе видиме други податоци
структури да бидат претставени

570
00:25:13,480 --> 00:25:16,700
со само еден покажувач,
32-битен стрела, покажувајќи

571
00:25:16,700 --> 00:25:18,740
на самиот прв јазол во структурата.

572
00:25:18,740 --> 00:25:20,340
>> Но сега да се предвиди проблем.

573
00:25:20,340 --> 00:25:23,230
Ако јас сум само сеќавајќи
во мојата програма на адресата

574
00:25:23,230 --> 00:25:27,220
на првиот јазол, првиот
правоаголник во оваа податочна структура,

575
00:25:27,220 --> 00:25:31,760
што беше подобро да биде случај за
имплементација на остатокот од мојот листа?

576
00:25:31,760 --> 00:25:35,820
Што е клучен детали што се случува
за да се обезбеди ова всушност се работи?

577
00:25:35,820 --> 00:25:39,250
И од "всушност работи" Јас
значи, слично како стринг,

578
00:25:39,250 --> 00:25:42,180
ни овозможува да одат од првиот карактер
во името на Davin на втората,

579
00:25:42,180 --> 00:25:44,755
на третата, на
Четврто, на самиот крај,

580
00:25:44,755 --> 00:25:47,880
како да знаеме кога сме на крајот
на поврзани листа што личи ова?

581
00:25:47,880 --> 00:25:50,035

582
00:25:50,035 --> 00:25:50,660
Кога тоа е нула.

583
00:25:50,660 --> 00:25:53,640
И јас сум претставен овој вид на како
како електро инженер моќ,

584
00:25:53,640 --> 00:25:56,420
со малку заземјување
симбол, на сорти.

585
00:25:56,420 --> 00:25:58,246
Но тоа само значи нула во овој случај.

586
00:25:58,246 --> 00:26:00,370
Можете да го нацрта било кој број
начини, но овој автор

587
00:26:00,370 --> 00:26:02,800
се случи да го користите овој симбол тука.

588
00:26:02,800 --> 00:26:06,260
>> Толку долго како што ние сме stringing
сите од овие јазли заедно,

589
00:26:06,260 --> 00:26:08,600
само сеќавајќи се, каде
првиот е, се додека

590
00:26:08,600 --> 00:26:11,760
како што се стави посебен симбол на
последен јазол во листата,

591
00:26:11,760 --> 00:26:15,130
и ние ќе го користите нула, затоа што тоа е
она што го имаме на располагање,

592
00:26:15,130 --> 00:26:16,480
оваа листа е завршена.

593
00:26:16,480 --> 00:26:20,190
И дури и ако јас само ви даде покажувач
првиот елемент, можете, на програмерот,

594
00:26:20,190 --> 00:26:22,486
секако, може да пристапите на остатокот од неа.

595
00:26:22,486 --> 00:26:24,360
Но, ајде да ги споделите вашите мисли
талкаат малку,

596
00:26:24,360 --> 00:26:26,140
ако тие не се веќе
доста wandered-- што е

597
00:26:26,140 --> 00:26:28,723
ќе биде во времетраење од
наоѓање на нешто во оваа листа?

598
00:26:28,723 --> 00:26:30,450

599
00:26:30,450 --> 00:26:33,470
По ѓаволите, тоа е голема О на n,
што не е лошо, во праведноста.

600
00:26:33,470 --> 00:26:34,800
Но, тоа е линеарна.

601
00:26:34,800 --> 00:26:37,980
Сме се откажале што функција
на низи со поместување повеќе

602
00:26:37,980 --> 00:26:43,130
кон оваа слика на динамички
плетени заедно или се поврзани јазли?

603
00:26:43,130 --> 00:26:44,970

604
00:26:44,970 --> 00:26:46,687
Ние сме се откажале случаен пристап.

605
00:26:46,687 --> 00:26:48,770
Низа е убаво, бидејќи
математички што

606
00:26:48,770 --> 00:26:50,340
е назад да се врати за да се врати назад.

607
00:26:50,340 --> 00:26:52,370
Иако оваа слика
изгледа убаво, па дури и

608
00:26:52,370 --> 00:26:55,830
и покрај тоа што изгледа како овие јазли
се убаво распоредени покрај, во реалноста

609
00:26:55,830 --> 00:26:56,830
тие можат да бидат секаде.

610
00:26:56,830 --> 00:27:01,590
Ox1, Ox50, Ox123, Ox99, овие
јазли можат да бидат секаде.

611
00:27:01,590 --> 00:27:05,960
Бидејќи Примерок прави алоцира меморија
од грамада, но никаде во грамада.

612
00:27:05,960 --> 00:27:09,080
Вие не мора да знаете дека тоа е
ќе биде да се врати назад кон назад.

613
00:27:09,080 --> 00:27:12,460
И така оваа слика во реалноста на
нема да биде доста оваа убава.

614
00:27:12,460 --> 00:27:16,140
>> Па затоа се случува да се земе малку
работат на спроведување на оваа функција.

615
00:27:16,140 --> 00:27:17,880
Значи, да се спроведе пребарување сега.

616
00:27:17,880 --> 00:27:20,250
И ќе видиме каков вид на
паметен начин да се направи ова.

617
00:27:20,250 --> 00:27:24,660
Значи, ако јас сум за пребарување функција и
Јас сум со оглед на променливата, број n

618
00:27:24,660 --> 00:27:28,490
да барате, треба да знаете
нова синтакса за потрага во

619
00:27:28,490 --> 00:27:32,400
од структурата што е
посочи, да се најде n.

620
00:27:32,400 --> 00:27:33,210
Значи, да го направите тоа.

621
00:27:33,210 --> 00:27:36,030
>> Значи прво ќе одам да се оди
напред и прогласи јазол *.

622
00:27:36,030 --> 00:27:39,400
И јас одам да го наречеме
покажувач, само со Конвенцијата.

623
00:27:39,400 --> 00:27:41,710
И јас одам да го иницијализирам прво.

624
00:27:41,710 --> 00:27:43,770
И сега можам да го направите тоа
во голем број на начини.

625
00:27:43,770 --> 00:27:45,436
Но јас ќе одам да се земе заеднички пристап.

626
00:27:45,436 --> 00:27:50,180
Додека покажувачот не е еднакво на
нула, и тоа е валидна синтакса.

627
00:27:50,180 --> 00:27:54,550
И тоа само значи направите следново, па
додека не сте покажувајќи кон ништо.

628
00:27:54,550 --> 00:27:55,800
Што сакам да направам?

629
00:27:55,800 --> 00:28:01,939
>> Ако покажувачот точка n, дозволете ми да се врати
тоа, equals-- еднаква на што?

630
00:28:01,939 --> 00:28:03,105
Што вредност сум јас барате?

631
00:28:03,105 --> 00:28:04,920

632
00:28:04,920 --> 00:28:06,590
Вистински n што беше донесен во.

633
00:28:06,590 --> 00:28:09,020
Значи тука е уште една карактеристика
на C и многу јазици.

634
00:28:09,020 --> 00:28:13,705
Иако структура наречена јазол
има вредност n, сосема легитимни

635
00:28:13,705 --> 00:28:17,530
исто така да имаат локална аргумент
или променлива наречена n.

636
00:28:17,530 --> 00:28:20,085
Затоа што дури и ние, со
човечки очи, може да се направи разлика

637
00:28:20,085 --> 00:28:22,087
дека n е веројатно
различни од оваа n.

638
00:28:22,087 --> 00:28:23,420
Бидејќи синтаксата е различна.

639
00:28:23,420 --> 00:28:26,211
Имаш точка и покажувач,
додека овој има такво нешто.

640
00:28:26,211 --> 00:28:27,290
Значи ова е во ред.

641
00:28:27,290 --> 00:28:29,120
Тоа е во ред да им се јавам на исти работи.

642
00:28:29,120 --> 00:28:32,380
>> Ако јас да ти се најде ова, јас сум
ќе сакате да направите нешто

643
00:28:32,380 --> 00:28:35,000
како објавиме дека најдовме n.

644
00:28:35,000 --> 00:28:37,930
И ние ќе го оставиме тоа како
коментира или pseudocode код.

645
00:28:37,930 --> 00:28:40,190
Друго, и тука е
Интересните дел, што

646
00:28:40,190 --> 00:28:47,320
сакам да направам, ако тековната јазол
не ги содржи n дека јас се грижат за?

647
00:28:47,320 --> 00:28:50,700
Како можам да го постигне следното?

648
00:28:50,700 --> 00:28:53,710
Ако мојот прст на
момент е меморија, и тоа е

649
00:28:53,710 --> 00:28:55,920
покажувајќи кон она што
Првиот е да се покажува во,

650
00:28:55,920 --> 00:28:59,290
како можам да се движи мојот прст
кон следниот јазол во код?

651
00:28:59,290 --> 00:29:01,915
Па, она што е Breadcrumb сме
ќе следат во овој случај?

652
00:29:01,915 --> 00:29:03,464

653
00:29:03,464 --> 00:29:04,380
ПУБЛИКАТА: [Беззвучен].

654
00:29:04,380 --> 00:29:05,630
Дејвид Џ MALAN: Да, па следната.

655
00:29:05,630 --> 00:29:06,640

656
00:29:06,640 --> 00:29:09,824
Значи, ако јас се вратам во мојата
код овде, навистина, јас сум

657
00:29:09,824 --> 00:29:12,990
ќе одиме напред и да се каже покажувач, што
е само привремена variable-- тоа е

658
00:29:12,990 --> 00:29:15,320
чудно име, кон меморија, но
тоа е исто како temp--

659
00:29:15,320 --> 00:29:19,234
Одам да го поставите покажувачот
еднакви на она што покажувачот is--

660
00:29:19,234 --> 00:29:22,150
и повторно, тоа се случува да биде
малку кабриолет за moment-- точка веднаш.

661
00:29:22,150 --> 00:29:23,551

662
00:29:23,551 --> 00:29:26,550
Со други зборови, јас ќе одам да земам
прст кој е покажувајќи кон овој јазол

663
00:29:26,550 --> 00:29:31,247
тука и јас одам да се каже, знаете
што, погледнете во следното поле

664
00:29:31,247 --> 00:29:33,330
и да се движат вашиот прст за да
што и да се покажува кон.

665
00:29:33,330 --> 00:29:35,163
И ова се случува да се
повторувам, повторувам, повторете.

666
00:29:35,163 --> 00:29:37,630
Но, кога го прави мојот прст
престане да прави ништо на сите?

667
00:29:37,630 --> 00:29:40,095
Штом она линија код клоци во?

668
00:29:40,095 --> 00:29:40,970
ПУБЛИКАТА: [Беззвучен]

669
00:29:40,970 --> 00:29:43,060
Дејвид Џ MALAN: Ако точка а
покажувач не е еднаква на нула.

670
00:29:43,060 --> 00:29:44,900
Во одреден момент мојот прст на
ќе биде покажувајќи кон нула

671
00:29:44,900 --> 00:29:47,070
и јас одам да се реализира
тоа е крајот на оваа листа.

672
00:29:47,070 --> 00:29:48,910
Сега, ова е малку
бела лага за едноставност.

673
00:29:48,910 --> 00:29:51,580
Излегува дека иако
само научиле оваа точка нотација

674
00:29:51,580 --> 00:29:55,220
за структури, покажувачот не е struct.

675
00:29:55,220 --> 00:29:56,580
кон меморија е она?

676
00:29:56,580 --> 00:29:58,350
Само за да биде повеќе nitpicky.

677
00:29:58,350 --> 00:29:59,720

678
00:29:59,720 --> 00:30:01,360
Тоа е покажувач кон јазол.

679
00:30:01,360 --> 00:30:03,120
Тоа не е еден јазол себе.

680
00:30:03,120 --> 00:30:06,650
Ако немав ѕвезда тука, покажувачот
absolutely-- тоа е еден јазол.

681
00:30:06,650 --> 00:30:08,650
Ова е како една недела
прогласување на променлива,

682
00:30:08,650 --> 00:30:10,120
иако зборот "јазол" е нова.

683
00:30:10,120 --> 00:30:13,860
>> Но штом ќе се воведат
ѕвезда, тоа е сега покажувач на еден јазол.

684
00:30:13,860 --> 00:30:17,960
И за жал не можете да користите
дот нотација за покажувач.

685
00:30:17,960 --> 00:30:21,070
Мора да се користи на стрелките
нотација, кои, неверојатно,

686
00:30:21,070 --> 00:30:23,470
е прв пат било парче
на синтаксата изгледа интуитивно.

687
00:30:23,470 --> 00:30:25,245
Ова буквално изгледа како стрела.

688
00:30:25,245 --> 00:30:26,370
И така тоа е добра работа.

689
00:30:26,370 --> 00:30:28,995
И овде буквално
изгледа како стрела.

690
00:30:28,995 --> 00:30:31,870
Па мислам дека тоа е la-- јас не
дека сум над-извршување here-- јас

691
00:30:31,870 --> 00:30:34,120
мислам дека тоа е последната нова фигура
на синтакса ние сме случува да се види.

692
00:30:34,120 --> 00:30:36,500
И за среќа, тоа е навистина
малку повеќе интуитивна.

693
00:30:36,500 --> 00:30:40,090
>> Сега, за оние од вас кои
би можеле да преферираат стариот начин,

694
00:30:40,090 --> 00:30:42,550
можете да го користите dot нотација.

695
00:30:42,550 --> 00:30:45,380
Но, како по понеделникот
разговор, ние прво

696
00:30:45,380 --> 00:30:50,530
треба да се оди таму, одат за тоа
адреса, а потоа пристап област.

697
00:30:50,530 --> 00:30:51,897
Значи, ова е, исто така, точно.

698
00:30:51,897 --> 00:30:53,730
И искрено, ова е
малку повеќе педантниот.

699
00:30:53,730 --> 00:30:56,530
Ќе бидете буквално велејќи dereference
на покажувачот и да си одат таму.

700
00:30:56,530 --> 00:30:59,320
А потоа го зграби .n, полето се нарекува n.

701
00:30:59,320 --> 00:31:01,370
Но, искрено, никој не сака
за да напишете или да прочитате ова.

702
00:31:01,370 --> 00:31:03,620
И така светот измислени
на стрелката нотација, кои

703
00:31:03,620 --> 00:31:06,980
е еквивалентно, идентични,
тоа е само синтаксички шеќер.

704
00:31:06,980 --> 00:31:10,570
Така фенси начин да се каже ова
изгледа подобро, или изгледа поедноставно.

705
00:31:10,570 --> 00:31:12,296
>> Па сега јас ќе одам да направите една друга работа.

706
00:31:12,296 --> 00:31:15,420
Одам да се каже "пауза" еднаш сум
најде тоа, така што не ги бараме за тоа.

707
00:31:15,420 --> 00:31:17,620
Но, ова е главното обележје
на функцијата за пребарување.

708
00:31:17,620 --> 00:31:21,710
Но, тоа е многу полесно, во
крајот, не да одат преку код.

709
00:31:21,710 --> 00:31:25,570
Ова е навистина формалното спроведување
на пребарување во денешниот дистрибуција код.

710
00:31:25,570 --> 00:31:30,530
Јас се осмелувам да кажам дека вметнете не е
особено забавно да се оди преку

711
00:31:30,530 --> 00:31:33,180
визуелно, ниту пак го избришете, па дури и
иако на крајот од денот

712
00:31:33,180 --> 00:31:35,460
тие се сведуваат на прилично
едноставни хеуристичко.

713
00:31:35,460 --> 00:31:36,330
>> Значи, да го направите тоа.

714
00:31:36,330 --> 00:31:39,250
Ако ќе хумор мене тука, јас не
донесе еден куп на стрес топки.

715
00:31:39,250 --> 00:31:40,620
Имам еден куп на броеви.

716
00:31:40,620 --> 00:31:46,562
И може да се добие само неколку волонтери
да претставуваат 9, 17, 20, 22, 29, и 34?

717
00:31:46,562 --> 00:31:48,270
Значи во суштина сите
кој е тука и денес.

718
00:31:48,270 --> 00:31:50,170

719
00:31:50,170 --> 00:31:52,760
Тоа беше еден, два, три,
четири, пет, шест лица.

720
00:31:52,760 --> 00:31:55,740
И јас сум бил побарано да go-- се види, нема
еден во задниот крева рацете.

721
00:31:55,740 --> 00:32:01,910
Добро, еден, два, три, четири,
five-- дозволете ми да се вчита balance-- шест.

722
00:32:01,910 --> 00:32:03,051
Добро, ќе дојде на шест до.

723
00:32:03,051 --> 00:32:04,050
Ќе треба други луѓе.

724
00:32:04,050 --> 00:32:05,460
Ние донесе екстра стрес топки.

725
00:32:05,460 --> 00:32:08,200
И ако може, на
само еден миг, линија

726
00:32:08,200 --> 00:32:10,490
себе се само
како оваа слика овде.

727
00:32:10,490 --> 00:32:15,200

728
00:32:15,200 --> 00:32:15,959
>> Во ред.

729
00:32:15,959 --> 00:32:17,125
Ајде да видиме, како се викаш?

730
00:32:17,125 --> 00:32:17,550
>> ПУБЛИКАТА: Андреј.

731
00:32:17,550 --> 00:32:18,800
>> Дејвид Џ MALAN: Андреј,
сте број 9.

732
00:32:18,800 --> 00:32:19,540
Убаво да ви се исполнат.

733
00:32:19,540 --> 00:32:20,400
Овде и да одите.

734
00:32:20,400 --> 00:32:21,593

735
00:32:21,593 --> 00:32:22,176
ПУБЛИКАТА: Џен.

736
00:32:22,176 --> 00:32:22,662
Дејвид Џ MALAN: Џен.

737
00:32:22,662 --> 00:32:23,162
Давид.

738
00:32:23,162 --> 00:32:23,765
Број 17.

739
00:32:23,765 --> 00:32:24,950

740
00:32:24,950 --> 00:32:25,450
Да?

741
00:32:25,450 --> 00:32:26,400
>> ПУБЛИКАТА: Јас сум Џулија.

742
00:32:26,400 --> 00:32:26,980
>> Дејвид Џ MALAN: Јулија, Дејвид.

743
00:32:26,980 --> 00:32:27,545
Број 20.

744
00:32:27,545 --> 00:32:28,507

745
00:32:28,507 --> 00:32:29,340
ПУБЛИКАТА: христијанин.

746
00:32:29,340 --> 00:32:30,715
Дејвид Џ MALAN: Кристијан Давид.

747
00:32:30,715 --> 00:32:31,541
Број 22.

748
00:32:31,541 --> 00:32:32,040
И?

749
00:32:32,040 --> 00:32:32,649
>> ПУБЛИКАТА: ЈП.

750
00:32:32,649 --> 00:32:33,440
Дејвид Џ MALAN: ЈП.

751
00:32:33,440 --> 00:32:34,880
Број 29.

752
00:32:34,880 --> 00:32:37,080
Така одат напред и да добијат in-- Ух ох.

753
00:32:37,080 --> 00:32:38,486

754
00:32:38,486 --> 00:32:38,985
Ух ох.

755
00:32:38,985 --> 00:32:39,650

756
00:32:39,650 --> 00:32:40,150
Мирување.

757
00:32:40,150 --> 00:32:41,360

758
00:32:41,360 --> 00:32:42,390
20.

759
00:32:42,390 --> 00:32:43,682
Дали некој има маркер?

760
00:32:43,682 --> 00:32:44,890
ПУБЛИКАТА: Имам Sharpie.

761
00:32:44,890 --> 00:32:45,660
Дејвид Џ MALAN: Имаш Sharpie?

762
00:32:45,660 --> 00:32:46,159
Во ред.

763
00:32:46,159 --> 00:32:47,577

764
00:32:47,577 --> 00:32:49,160
И дали некој има парче хартија?

765
00:32:49,160 --> 00:32:51,562

766
00:32:51,562 --> 00:32:52,270
Спаси предавање.

767
00:32:52,270 --> 00:32:53,810

768
00:32:53,810 --> 00:32:55,362
Ајде.

769
00:32:55,362 --> 00:32:56,320
ПУБЛИКАТА: Ние сме го добив.

770
00:32:56,320 --> 00:32:57,600
Дејвид Џ MALAN: Ние го зедов тоа?

771
00:32:57,600 --> 00:32:58,577
Добро, ви благодарам.

772
00:32:58,577 --> 00:33:01,380

773
00:33:01,380 --> 00:33:02,520
Еве ќе одиме.

774
00:33:02,520 --> 00:33:03,582
Беше тоа од вас?

775
00:33:03,582 --> 00:33:04,540
Вие само спаси денот.

776
00:33:04,540 --> 00:33:05,670

777
00:33:05,670 --> 00:33:07,220
Па 29.

778
00:33:07,220 --> 00:33:10,510

779
00:33:10,510 --> 00:33:11,110
Во ред.

780
00:33:11,110 --> 00:33:13,360

781
00:33:13,360 --> 00:33:14,890
Јас погрешно напишани 29, но во ред.

782
00:33:14,890 --> 00:33:15,720
Оди напред.

783
00:33:15,720 --> 00:33:18,114
Добро, јас ќе ви даде
вашиот пенкало врати веднаш.

784
00:33:18,114 --> 00:33:19,280
Значи ние треба овие луѓе тука.

785
00:33:19,280 --> 00:33:20,330
Ајде да имаат еден друг.

786
00:33:20,330 --> 00:33:23,750
Габе, дали сакате да играте
првиот елемент тука?

787
00:33:23,750 --> 00:33:25,705
Ќе треба да се истакне
овие фини луѓе.

788
00:33:25,705 --> 00:33:26,930

789
00:33:26,930 --> 00:33:31,030
Значи 9, 17, 20, 22, сортирање
на 29, а потоа 34.

790
00:33:31,030 --> 00:33:32,160

791
00:33:32,160 --> 00:33:33,325
Дали ја губиме некој?

792
00:33:33,325 --> 00:33:33,950
Имам 34.

793
00:33:33,950 --> 00:33:36,730
Каде did-- Добро, кој сака да биде 34?

794
00:33:36,730 --> 00:33:37,605
Добро, ајде нагоре, 34.

795
00:33:37,605 --> 00:33:39,280

796
00:33:39,280 --> 00:33:41,220
Добро, ова ќе биде
добро вреди кулминација.

797
00:33:41,220 --> 00:33:41,550
Што е вашето име?

798
00:33:41,550 --> 00:33:42,040
>> ПУБЛИКАТА: Петар.

799
00:33:42,040 --> 00:33:43,456
>> Дејвид Џ MALAN: Питер, ајде нагоре.

800
00:33:43,456 --> 00:33:46,810
Добро, па тука е
целиот куп на јазли.

801
00:33:46,810 --> 00:33:49,060
Секој од вас момци претставува
еден од овие правоаголници.

802
00:33:49,060 --> 00:33:51,930
И Габе, малку чудно
човек, претставува прв план.

803
00:33:51,930 --> 00:33:54,850
Па неговата покажувачот е малку помал
на екранот од сите други.

804
00:33:54,850 --> 00:33:58,120
И во овој случај, секој од лево
рацете се случува да се укаже или надолу,

805
00:33:58,120 --> 00:34:01,085
со тоа што претставува нула, па
само на отсуство на покажувач,

806
00:34:01,085 --> 00:34:03,210
или тоа ќе биде покажувајќи
на еден јазол до тебе.

807
00:34:03,210 --> 00:34:05,440
>> Па сега ако украсуваат
себе како на сликата

808
00:34:05,440 --> 00:34:07,585
тука, одиме напред и точка
еден во друг, со Габе

809
00:34:07,585 --> 00:34:11,030
особено укажувањето на
број 9 да претставуваат листа.

810
00:34:11,030 --> 00:34:14,050
Добро, и бројот 34, левата рака
само треба да се укажува на подот.

811
00:34:14,050 --> 00:34:15,750
>> Добро, така што ова е поврзана листа.

812
00:34:15,750 --> 00:34:17,580
Значи ова е сценарио во прашање.

813
00:34:17,580 --> 00:34:20,210
И навистина, тој е претставник
на класа на проблеми

814
00:34:20,210 --> 00:34:21,929
што може да се обиде да го реши со код.

815
00:34:21,929 --> 00:34:25,020
Сакате да на крајот се вметне
нов елемент во листата.

816
00:34:25,020 --> 00:34:27,494
Во овој случај, ние ќе
се обиде вметнување на број 55.

817
00:34:27,494 --> 00:34:28,500

818
00:34:28,500 --> 00:34:30,860
Но, има се случува да биде
различни случаи да се разгледа.

819
00:34:30,860 --> 00:34:34,409
И навистина, тоа се случува да биде една
на голем слика takeaways тука е,

820
00:34:34,409 --> 00:34:35,659
што се различни случаи.

821
00:34:35,659 --> 00:34:39,120
Кои се различни, ако условите или
гранки кои вашата програма може да има?

822
00:34:39,120 --> 00:34:42,024
>> Па, бројот што се обидуваат да
вметнете, кои знаеме сега треба да биде 55,

823
00:34:42,024 --> 00:34:44,650
но ако не сте знаеле
однапред, јас daresay

824
00:34:44,650 --> 00:34:47,840
паѓа во најмалку три
можни ситуации.

825
00:34:47,840 --> 00:34:49,717
Каде нов елемент може да биде?

826
00:34:49,717 --> 00:34:51,050
ПУБЛИКАТА: И на крајот или средината.

827
00:34:51,050 --> 00:34:54,150
Дејвид Џ MALAN: На крајот, во
средината, или на почетокот.

828
00:34:54,150 --> 00:34:56,650
Така тврдам има најмалку
три проблеми што треба да се реши.

829
00:34:56,650 --> 00:34:58,691
Ајде да се избере она што е можеби
веројатно најпростиот

830
00:34:58,691 --> 00:35:01,090
еден, каде што новиот елемент
припаѓа на почетокот.

831
00:35:01,090 --> 00:35:04,040
Па јас ќе одам да имаат код доста
како пребарување, што јас само напишав.

832
00:35:04,040 --> 00:35:07,670
И јас одам да имаат кон меморија, која
Ќе го претставуваме тука со мојот прст,

833
00:35:07,670 --> 00:35:08,370
како и обично.

834
00:35:08,370 --> 00:35:12,430
>> И се сеќавам, она што вредност
не се иницијализира кон меморија до?

835
00:35:12,430 --> 00:35:15,300
Па ние го иницијализира на нула на почетокот.

836
00:35:15,300 --> 00:35:16,410

837
00:35:16,410 --> 00:35:19,770
Но, тогаш она што не го правиме откако ќе
беа во нашите функцијата за пребарување?

838
00:35:19,770 --> 00:35:20,940

839
00:35:20,940 --> 00:35:24,870
Ние во собата го еднаква на прво место,
што не значи тоа.

840
00:35:24,870 --> 00:35:25,890

841
00:35:25,890 --> 00:35:30,570
Ако јас во собата кон меморија еднаква на прво, што
треба мојата рака навистина да биде покажувајќи кон?

842
00:35:30,570 --> 00:35:31,070
Право.

843
00:35:31,070 --> 00:35:33,290
Значи, ако Габе и јас се случува
да бидат еднакви вредности тука,

844
00:35:33,290 --> 00:35:34,760
ние треба да и точка на број 9.

845
00:35:34,760 --> 00:35:36,420
>> Значи ова беше на почетокот на нашата приказна.

846
00:35:36,420 --> 00:35:38,700
А сега ова е само јасна,
иако синтаксата е нова.

847
00:35:38,700 --> 00:35:40,580
Концепциски, ова е само линеарно пребарување.

848
00:35:40,580 --> 00:35:42,750
Е 55 еднаков на 9?

849
00:35:42,750 --> 00:35:45,559
Или подобро кажано, да речеме помалку од 9.

850
00:35:45,559 --> 00:35:47,600
Затоа што јас се обидувам да
дознаам каде да се стави 55.

851
00:35:47,600 --> 00:35:51,270
Помалку од 9, помалку од 17, помалку
од 20, помалку од 22, помалку од 29,

852
00:35:51,270 --> 00:35:52,510
помалку од 34, бр.

853
00:35:52,510 --> 00:35:55,080
Па сега сме во случај
еден од најмалку три.

854
00:35:55,080 --> 00:35:59,910
>> Ако сакате да го вметнете 55 ваму, што
линии на код треба да се извршуваат?

855
00:35:59,910 --> 00:36:01,890
Како го прави ова слика на
луѓето треба да се промени?

856
00:36:01,890 --> 00:36:03,181
Што да правам со мојата лева рака?

857
00:36:03,181 --> 00:36:04,530

858
00:36:04,530 --> 00:36:07,360
Ова треба да биде нула на почетокот,
бидејќи јас сум на крајот на листата.

859
00:36:07,360 --> 00:36:09,318
И она што треба да се случи
тука со Петар, беше тоа?

860
00:36:09,318 --> 00:36:10,520

861
00:36:10,520 --> 00:36:12,430
Тој очигледно се случува да се укаже мене.

862
00:36:12,430 --> 00:36:15,580
Така тврдам има најмалку две линии
на код во примерокот кодот од денес

863
00:36:15,580 --> 00:36:18,570
што се случува за спроведување на оваа
сценарио за додавање на 55 на опашката.

864
00:36:18,570 --> 00:36:20,950
И може да имам некој хоп
и само претставуваат 55?

865
00:36:20,950 --> 00:36:22,200
Добро, вие сте новиот 55.

866
00:36:22,200 --> 00:36:23,580

867
00:36:23,580 --> 00:36:27,054
>> Па сега што ако следниот
сценарио доаѓа заедно,

868
00:36:27,054 --> 00:36:29,720
и ние сакаме да се вметне на
почетокот или на чело на оваа листа?

869
00:36:29,720 --> 00:36:31,100
И она што е вашето име, број 55?

870
00:36:31,100 --> 00:36:31,420
>> ПУБЛИКАТА: Џек.

871
00:36:31,420 --> 00:36:32,295
>> Дејвид Џ MALAN: Џек?

872
00:36:32,295 --> 00:36:33,585
Добро, убаво да ви се исполнат.

873
00:36:33,585 --> 00:36:34,210
Добредојдовте на бродот.

874
00:36:34,210 --> 00:36:36,640
Па сега ние ќе се
вметнете, да речеме, бројот 5.

875
00:36:36,640 --> 00:36:39,840
Тука е втор случај на
три дојдовме до пред.

876
00:36:39,840 --> 00:36:43,050
Значи, ако 5 припаѓа на почетокот,
ајде да видиме како ќе најдеме тоа.

877
00:36:43,050 --> 00:36:46,310
Јас се иницијализира моите кон меморија
покажувач на бројот 9 се повторно.

878
00:36:46,310 --> 00:36:49,140
И сфатив, о, 5 е помала од 9.

879
00:36:49,140 --> 00:36:50,880
Па се поправи оваа слика за нас.

880
00:36:50,880 --> 00:36:54,820
Чии раце, Габе или Давид
or-- она ​​што е број 9 име?

881
00:36:54,820 --> 00:36:55,740
>> ПУБЛИКАТА: Џен.

882
00:36:55,740 --> 00:36:58,406
>> Дејвид Џ MALAN: hands-- на Jen
кој од нашите раце треба да се промени?

883
00:36:58,406 --> 00:36:58,905

884
00:36:58,905 --> 00:37:00,970
Добро, така Габе укажува на она што сега?

885
00:37:00,970 --> 00:37:01,640
Во мене.

886
00:37:01,640 --> 00:37:02,750
Јас сум нов јазол.

887
00:37:02,750 --> 00:37:04,870
Па јас ќе само вид на потег
тука за да го видите визуелно.

888
00:37:04,870 --> 00:37:06,435
А во меѓувреме она што можам да истакнам дека?

889
00:37:06,435 --> 00:37:07,910

890
00:37:07,910 --> 00:37:09,020
Сепак, каде што јас сум покажува.

891
00:37:09,020 --> 00:37:10,000
Значи тоа е тоа.

892
00:37:10,000 --> 00:37:13,717
Па само навистина една линија код поправки
ова конкретно прашање, тоа ќе изгледа.

893
00:37:13,717 --> 00:37:14,800
Сите во право, па тоа е добро.

894
00:37:14,800 --> 00:37:17,580
И некој може да биде случаеви за 5?

895
00:37:17,580 --> 00:37:18,080
Ајде до.

896
00:37:18,080 --> 00:37:20,270

897
00:37:20,270 --> 00:37:21,320
Ќе ти најдеме следниот пат.

898
00:37:21,320 --> 00:37:24,280
>> Добро, така now-- и
Како настрана, имињата

899
00:37:24,280 --> 00:37:28,510
Јас не сум што експлицитно споменување на право
сега, pred покажувач, претходник покажувачот

900
00:37:28,510 --> 00:37:31,260
и нови покажувачот, тоа е
само имиња дадени

901
00:37:31,260 --> 00:37:35,280
во примерокот кодот на совети или
моите раце и тоа е вид на покажувајќи наоколу.

902
00:37:35,280 --> 00:37:36,060
Што е вашето име?

903
00:37:36,060 --> 00:37:36,700
>> ПУБЛИКАТА: Кристин.

904
00:37:36,700 --> 00:37:37,100
>> Дејвид Џ MALAN: Кристин.

905
00:37:37,100 --> 00:37:38,090
Добредојдовте на бродот.

906
00:37:38,090 --> 00:37:42,180
Добро, па ајде да се разгледа сега
малку повеќе досадни сценарио,

907
00:37:42,180 --> 00:37:46,350
при што сакам да го вметнете
нешто како 26 во тоа.

908
00:37:46,350 --> 00:37:47,090
20?

909
00:37:47,090 --> 00:37:47,590
Што?

910
00:37:47,590 --> 00:37:50,510
Овие are-- добра работа имаме ова пенкало.

911
00:37:50,510 --> 00:37:51,955
Добро, 20.

912
00:37:51,955 --> 00:37:53,640

913
00:37:53,640 --> 00:37:57,570
Ако некој може да се добие уште еден дел од
хартија подготвен, само во case-- ред.

914
00:37:57,570 --> 00:37:58,370
Ох, интересно.

915
00:37:58,370 --> 00:37:59,760

916
00:37:59,760 --> 00:38:02,390
Па ова е пример
на предавање бубачка.

917
00:38:02,390 --> 00:38:03,894
Добро па што е вашето име повторно?

918
00:38:03,894 --> 00:38:04,560
ПУБЛИКАТА: Јулија.

919
00:38:04,560 --> 00:38:07,559
Дејвид Џ MALAN: Јулија, може да ви се појави
надвор и се преправам сте биле никогаш таму?

920
00:38:07,559 --> 00:38:09,040
Добро, тоа никогаш не се случило.

921
00:38:09,040 --> 00:38:09,680
Ви благодарам.

922
00:38:09,680 --> 00:38:12,180
Значи да претпоставиме што сакате да внесете
Јулија во оваа поврзани листа.

923
00:38:12,180 --> 00:38:13,780
Таа е број 20.

924
00:38:13,780 --> 00:38:15,530
И, се разбира таа е
ќе припаѓаат на

925
00:38:15,530 --> 00:38:17,521
begin-- не упатуваат на ништо сеуште.

926
00:38:17,521 --> 00:38:20,020
Па раката вид на може да биде
надолу null или некои ѓубре вредност.

927
00:38:20,020 --> 00:38:21,210
Ајде да кажам на брз приказна.

928
00:38:21,210 --> 00:38:22,980
Јас сум покажувајќи кон број 5 на овој период.

929
00:38:22,980 --> 00:38:23,880
Тогаш јас се провери 9.

930
00:38:23,880 --> 00:38:25,130
Тогаш јас провери 17.

931
00:38:25,130 --> 00:38:26,247
Тогаш јас провери 22.

932
00:38:26,247 --> 00:38:27,650

933
00:38:27,650 --> 00:38:32,485
И сфаќам, ooh, Јулија
треба да се оди пред 22.

934
00:38:32,485 --> 00:38:33,580

935
00:38:33,580 --> 00:38:34,660
Значи она што треба да се случи?

936
00:38:34,660 --> 00:38:35,786

937
00:38:35,786 --> 00:38:36,910
Чии раце треба да се промени?

938
00:38:36,910 --> 00:38:38,360
Јулија, мојата, or--
она што е вашето име повторно?

939
00:38:38,360 --> 00:38:39,230
>> ПУБЛИКАТА: христијанин.

940
00:38:39,230 --> 00:38:40,060
>> Дејвид Џ MALAN: Кристијан или?

941
00:38:40,060 --> 00:38:40,560
>> ПУБЛИКАТА: Енди.

942
00:38:40,560 --> 00:38:40,905
>> Дејвид Џ MALAN: Енди.

943
00:38:40,905 --> 00:38:41,654
Христијанин или Енди?

944
00:38:41,654 --> 00:38:44,280

945
00:38:44,280 --> 00:38:45,690
Енди треба да се укаже на?

946
00:38:45,690 --> 00:38:46,780

947
00:38:46,780 --> 00:38:47,341
Јулија.

948
00:38:47,341 --> 00:38:47,840
Во ред.

949
00:38:47,840 --> 00:38:48,960
Па Енди, сакаш да се укаже на Јулија?

950
00:38:48,960 --> 00:38:50,120
Но, чекајте.

951
00:38:50,120 --> 00:38:53,260
Во приказната досега,
Јас сум вид на еден

952
00:38:53,260 --> 00:38:56,800
одговорен, во смисла дека
покажувачот е нешто што е

953
00:38:56,800 --> 00:38:57,850
се движат низ листата.

954
00:38:57,850 --> 00:39:00,800
Ние би можеле да имаат име за Енди, но
нема променлива наречена Енди.

955
00:39:00,800 --> 00:39:04,320
Единствената друга променлива што го имаме е
Првиот, кој е претставен од страна на Габе.

956
00:39:04,320 --> 00:39:07,690
>> Значи ова е всушност зошто тоа
далеку не сме потребни ова.

957
00:39:07,690 --> 00:39:10,846
Но, сега на екранот постои
споменам повторно на pred покажувач.

958
00:39:10,846 --> 00:39:11,970
Па да ми биде повеќе експлицитни.

959
00:39:11,970 --> 00:39:14,820
Ако ова е покажувач, имав подобро
се добие малку поинтелигентен

960
00:39:14,820 --> 00:39:15,950
за мојот повторување.

961
00:39:15,950 --> 00:39:19,580
Ако не ти пречи мојата минува низ овде
повторно, посочувајќи тука, покажувајќи тука.

962
00:39:19,580 --> 00:39:22,500
Но, дозволете ми да имаат pred покажувач,
претходник покажувач, тоа е

963
00:39:22,500 --> 00:39:24,740
вид посочувајќи на
елемент бев во.

964
00:39:24,740 --> 00:39:27,330
Па кога одам тука, сега
мојата лева рака надградби.

965
00:39:27,330 --> 00:39:29,370
Кога одам тука мојата лева рака надградби.

966
00:39:29,370 --> 00:39:33,090
И сега имам само покажувач на
елемент кој оди по Јулија,

967
00:39:33,090 --> 00:39:36,300
Јас се уште имаат покажувач
Енди, елементот порано.

968
00:39:36,300 --> 00:39:39,430
Па имате пристап, во суштина,
breadcrumbs, ако сакате,

969
00:39:39,430 --> 00:39:41,500
на сите потребните совети.

970
00:39:41,500 --> 00:39:43,710
>> Значи, ако јас сум покажувајќи кон
Енди и јас сум исто така, покажува

971
00:39:43,710 --> 00:39:47,105
на Кристијан, чии раце
сега треба да се истакне на друго место?

972
00:39:47,105 --> 00:39:48,770

973
00:39:48,770 --> 00:39:51,960
Па Енди сега може да укаже на Јулија.

974
00:39:51,960 --> 00:39:54,460
Јулија сега може да укаже на христијанин.

975
00:39:54,460 --> 00:39:56,950
Затоа што таа може да копирам
покажувачот десна рака е.

976
00:39:56,950 --> 00:40:00,044
И дека ефективно ве става
назад во ова место тука.

977
00:40:00,044 --> 00:40:02,460
Значи во кратки, иако ова
не води вид на засекогаш

978
00:40:02,460 --> 00:40:04,510
всушност да ажурирате
поврзана листа, реализира

979
00:40:04,510 --> 00:40:06,580
дека операциите
се релативно едноставни.

980
00:40:06,580 --> 00:40:10,030
Тоа е од еден, два, три
линии на код во крајна линија.

981
00:40:10,030 --> 00:40:12,780
Но обвиткана околу оние
линии на код се претпоставува дека

982
00:40:12,780 --> 00:40:16,350
е малку логика, која ефикасно
го поставува прашањето, каде сме ние?

983
00:40:16,350 --> 00:40:18,970
Дали сме на почетокот,
средината или на крајот?

984
00:40:18,970 --> 00:40:21,890
>> Сега, секако дека постојат некои други
операции што може да се спроведе.

985
00:40:21,890 --> 00:40:24,880
И овие слики тука само отслика
она што го направија со луѓето.

986
00:40:24,880 --> 00:40:26,080
Што е со отстранување?

987
00:40:26,080 --> 00:40:30,650
Ако сакам да, на пример,
отстрани број 34 или 55,

988
00:40:30,650 --> 00:40:34,680
Јас би можеле да имаат ист вид на код,
но јас ќе одам да треба еден или два чекори.

989
00:40:34,680 --> 00:40:36,110
Бидејќи она што е ново?

990
00:40:36,110 --> 00:40:40,460
Ако јас отстраните некој на крајот,
како број 55, а потоа 34,

991
00:40:40,460 --> 00:40:42,995
што, исто така, мора да се промени како што јас го правам тоа?

992
00:40:42,995 --> 00:40:44,870
Морам да го evict--
она што е вашето име повторно?

993
00:40:44,870 --> 00:40:45,380
>> ПУБЛИКАТА: Џек.

994
00:40:45,380 --> 00:40:46,255
>> Дејвид Џ MALAN: Џек.

995
00:40:46,255 --> 00:40:49,770
Морам да не само evict-- слободен Џек,
па буквално повик ослободени Џек, или барем

996
00:40:49,770 --> 00:40:53,530
покажувачот таму, но сега
што треба да се промени со Петар?

997
00:40:53,530 --> 00:40:55,510
Раката подобро е да почнеме покажува надолу.

998
00:40:55,510 --> 00:40:59,300
Затоа што веднаш штом ли повик ослободени од
Џек, ако Петар уште покажувајќи кон Џек

999
00:40:59,300 --> 00:41:02,530
и јас тоа го задржи traversing
листата и пристап до оваа покажувач,

1000
00:41:02,530 --> 00:41:05,650
тоа е кога нашиот стар пријател сегментација
грешка всушност би можеле да умирам.

1001
00:41:05,650 --> 00:41:07,860
Затоа што сум со оглед на
меморија назад Џек.

1002
00:41:07,860 --> 00:41:10,760
>> Можете да остане таму
чудно за само еден миг.

1003
00:41:10,760 --> 00:41:13,410
Бидејќи имаме само неколку
завршните операции за да се разгледа.

1004
00:41:13,410 --> 00:41:15,600
Отстранување на чело на листата,
или beginning-- и ова ми е

1005
00:41:15,600 --> 00:41:16,349
малку досадни.

1006
00:41:16,349 --> 00:41:19,640
Затоа што ние треба да знаат дека Габе
е вид на специјални во оваа програма.

1007
00:41:19,640 --> 00:41:21,440
Бидејќи навистина, тој има своја покажувач.

1008
00:41:21,440 --> 00:41:24,860
Тој не е само вперени во,
како што е речиси сите други овде.

1009
00:41:24,860 --> 00:41:28,112
>> Па кога на чело на листата е
отстранети, чии раце треба да се промени сега?

1010
00:41:28,112 --> 00:41:29,070
Што е вашето име повторно?

1011
00:41:29,070 --> 00:41:29,450
>> ПУБЛИКАТА: Кристин.

1012
00:41:29,450 --> 00:41:31,408
>> Дејвид Џ MALAN: Јас сум ужасна
на имиња, очигледно.

1013
00:41:31,408 --> 00:41:34,011
Па Кристин и Габе,
чии раце треба да се промени

1014
00:41:34,011 --> 00:41:36,510
кога ќе се обидат да се отстрани Кристин,
број 5 од сликата?

1015
00:41:36,510 --> 00:41:37,550

1016
00:41:37,550 --> 00:41:38,820
Добро, така нека направи Габе.

1017
00:41:38,820 --> 00:41:40,950
Габе ќе се укаже,
веројатно, во број 9.

1018
00:41:40,950 --> 00:41:42,230

1019
00:41:42,230 --> 00:41:44,642
Но, она што следната треба да се случи?

1020
00:41:44,642 --> 00:41:46,600
ПУБЛИКАТА: Кристин треба
бидат ништовни [Беззвучен].

1021
00:41:46,600 --> 00:41:50,244
Дејвид Џ MALAN: Добро, ние најверојатно треба
make-- слушнав "нула" некаде.

1022
00:41:50,244 --> 00:41:51,410
ПУБЛИКАТА: Нулев и слободни неа.

1023
00:41:51,410 --> 00:41:51,855
Дејвид Џ MALAN: NULL што?

1024
00:41:51,855 --> 00:41:53,074
ПУБЛИКАТА: Нулев и слободни неа.

1025
00:41:53,074 --> 00:41:54,490
Дејвид Џ MALAN: Нулев и слободни неа.

1026
00:41:54,490 --> 00:41:55,422
Значи ова е многу лесно.

1027
00:41:55,422 --> 00:41:58,380
И тоа е совршена дека ти си сега вид
на постојани таму, кои не припаѓаат.

1028
00:41:58,380 --> 00:42:00,430
Бидејќи сте биле
одделат од листата.

1029
00:42:00,430 --> 00:42:02,820
Сте ефикасно се
сираче од листата.

1030
00:42:02,820 --> 00:42:07,770
И така имавме подобра повик ослободени сега
Кристин да им даде дека меморијата назад.

1031
00:42:07,770 --> 00:42:10,240
Инаку секој пат кога ние
избришете еден јазол од листата

1032
00:42:10,240 --> 00:42:14,230
ние би можеле да се прави листа
пократок, но не и всушност се намалува

1033
00:42:14,230 --> 00:42:15,096
големината на меморијата.

1034
00:42:15,096 --> 00:42:17,720
И така, ако ние ги додавајќи и
додавање, додавајќи работи на списокот,

1035
00:42:17,720 --> 00:42:19,280
мојот компјутер може да се добие побавно
и побавно и побавно,

1036
00:42:19,280 --> 00:42:21,740
бидејќи јас сум истекува на
меморија, дури и ако не сум всушност

1037
00:42:21,740 --> 00:42:25,580
користење на бајти на Christine
меморија повеќе.

1038
00:42:25,580 --> 00:42:28,500
>> Па на крајот постојат и други
сценарија, на course-- отстранување

1039
00:42:28,500 --> 00:42:30,640
во средината, отстранување
на крајот, како што видовме.

1040
00:42:30,640 --> 00:42:32,348
Но поинтересно
Предизвикот сега е

1041
00:42:32,348 --> 00:42:34,770
ќе биде да се разгледа точно
она трчање време е.

1042
00:42:34,770 --> 00:42:36,640
Затоа, не само што може да ги задржи вашите
парчиња хартија, ако Габе,

1043
00:42:36,640 --> 00:42:38,640
не би ум даваат
секој стрес топката.

1044
00:42:38,640 --> 00:42:42,100
Ви благодарам многу за нашите поврзана листа
на волонтери тука, ако може.

1045
00:42:42,100 --> 00:42:45,320
>> [Аплауз]

1046
00:42:45,320 --> 00:42:46,700
>> Дејвид Џ MALAN: Во ред.

1047
00:42:46,700 --> 00:42:51,110
Па неколку аналитички
прашања тогаш, ако можам.

1048
00:42:51,110 --> 00:42:59,670
Видовме оваа нотација пред,
голема О и омега, горната граница

1049
00:42:59,670 --> 00:43:02,520
и долниот границите на
трчање време на некои алгоритам.

1050
00:43:02,520 --> 00:43:04,950
Па ајде да се разгледа само
неколку прашања.

1051
00:43:04,950 --> 00:43:07,090
>> Еден, и ние тоа го рече
пред, што е водење

1052
00:43:07,090 --> 00:43:10,647
време на потрагата по
листа во однос на големите О?

1053
00:43:10,647 --> 00:43:13,480
Што е горна граница на водење
време на пребарувањето на поврзани листа

1054
00:43:13,480 --> 00:43:16,340
а се имплементирани од нашите волонтери тука?

1055
00:43:16,340 --> 00:43:17,820
Тоа е голема О на n, линеарна.

1056
00:43:17,820 --> 00:43:20,630
Затоа што во најлош случај,
на елемент, како 55,

1057
00:43:20,630 --> 00:43:23,830
ние би можеле да се гледа за може да биде каде што
Џек беше, сè на крајот.

1058
00:43:23,830 --> 00:43:28,250
И, за жал, за разлика од низа
не можеме да се фенси тоа време.

1059
00:43:28,250 --> 00:43:31,820
Иако сите наши луѓе беа
подредени од мали елементи, 5,

1060
00:43:31,820 --> 00:43:35,900
сите на патот до поголем елемент,
55, тоа е обично е добра работа.

1061
00:43:35,900 --> 00:43:38,815
Но, она што го прави таа претпоставка
не ни дозволуваат да направам?

1062
00:43:38,815 --> 00:43:39,775

1063
00:43:39,775 --> 00:43:40,650
ПУБЛИКАТА: [Беззвучен]

1064
00:43:40,650 --> 00:43:40,920
Дејвид Џ MALAN: Кажи повторно?

1065
00:43:40,920 --> 00:43:41,800
ПУБЛИКАТА: Случајни пристап.

1066
00:43:41,800 --> 00:43:43,049
Дејвид Џ MALAN: Случајни пристап.

1067
00:43:43,049 --> 00:43:46,330
И пак тоа значи дека ние не може
не се користи слаби нули, интуиција,

1068
00:43:46,330 --> 00:43:49,365
и очигледност на користење на бинарни
пребарување и подели па владеј.

1069
00:43:49,365 --> 00:43:51,240
Бидејќи иако ние
луѓето би можеле очигледно

1070
00:43:51,240 --> 00:43:54,610
види дека Енди или христијански беа
приближно во средината на листата,

1071
00:43:54,610 --> 00:43:57,670
ние знаеме само дека како
компјутер со впивам листата

1072
00:43:57,670 --> 00:43:59,029
од самиот почеток.

1073
00:43:59,029 --> 00:44:00,570
Значи ние сме се откажале дека случаен пристап.

1074
00:44:00,570 --> 00:44:04,380
>> Толку голема О од n сега е на горниот
граница на нашите пребарување време.

1075
00:44:04,380 --> 00:44:07,920
Што е со омега на нашите пребарување?

1076
00:44:07,920 --> 00:44:11,535
Што е долната граница на пребарувањето
за некои број во оваа листа?

1077
00:44:11,535 --> 00:44:12,410
ПУБЛИКАТА: [Беззвучен]

1078
00:44:12,410 --> 00:44:13,040
Дејвид Џ MALAN: Кажи повторно?

1079
00:44:13,040 --> 00:44:13,420
ПУБЛИКАТА: Еден.

1080
00:44:13,420 --> 00:44:13,800
Дејвид Џ MALAN: Еден.

1081
00:44:13,800 --> 00:44:14,760
Па постојано време.

1082
00:44:14,760 --> 00:44:17,020
Во најдобар случај, Кристин е
навистина на почетокот на листата.

1083
00:44:17,020 --> 00:44:19,020
И ние сме во потрага за
број 5, па ние ја најде.

1084
00:44:19,020 --> 00:44:19,787
Па нема ништо страшно.

1085
00:44:19,787 --> 00:44:22,370
Но таа мора да биде во
почетокот на списокот во овој случај.

1086
00:44:22,370 --> 00:44:23,745
Она што за такво нешто избришете?

1087
00:44:23,745 --> 00:44:24,717

1088
00:44:24,717 --> 00:44:26,300
Што ако сакате да ги избришете елемент?

1089
00:44:26,300 --> 00:44:29,200
Што е горната граница и долната граница
за бришење на нешто од поврзани

1090
00:44:29,200 --> 00:44:29,699
Листа?

1091
00:44:29,699 --> 00:44:35,195

1092
00:44:35,195 --> 00:44:36,070
ПУБЛИКАТА: [Беззвучен]

1093
00:44:36,070 --> 00:44:36,420
Дејвид Џ MALAN: Кажи повторно?

1094
00:44:36,420 --> 00:44:37,067
ПУБЛИКАТА: n.

1095
00:44:37,067 --> 00:44:38,900
Дејвид Џ MALAN: n е
навистина горната граница.

1096
00:44:38,900 --> 00:44:41,700
Затоа што во најлош случај ќе се обидеме
да ги избришете Џек, како што го направија.

1097
00:44:41,700 --> 00:44:43,050
Тој е начинот на кој на крајот.

1098
00:44:43,050 --> 00:44:45,419
Ни треба цела вечност, или
n чекори за да го најде.

1099
00:44:45,419 --> 00:44:46,460
Па тоа е горна граница.

1100
00:44:46,460 --> 00:44:47,430
Тоа е линеарна, секако.

1101
00:44:47,430 --> 00:44:50,970
И најдобар случај трчање време, или
долниот границите во најдобар случај

1102
00:44:50,970 --> 00:44:51,975
ќе биде постојана време.

1103
00:44:51,975 --> 00:44:54,600
Затоа што можеби ќе се обидеме да ги избришете
Кристин, а ние само ќе имаат среќа

1104
00:44:54,600 --> 00:44:55,558
таа е на почетокот.

1105
00:44:55,558 --> 00:44:56,350
Сега почекајте една минута.

1106
00:44:56,350 --> 00:44:59,370
Габе беше, исто така, на почетокот,
и ние, исто така, мораше да се ажурира Габе.

1107
00:44:59,370 --> 00:45:01,150
Па тоа не е само еден чекор.

1108
00:45:01,150 --> 00:45:04,210
Па тоа е навистина постојан
време, во најдобар случај,

1109
00:45:04,210 --> 00:45:06,345
за да се отстрани и најмалата елемент?

1110
00:45:06,345 --> 00:45:07,360

1111
00:45:07,360 --> 00:45:10,960
Тоа е, иако тоа би можело да биде два,
три, па дури и 100 линии на код,

1112
00:45:10,960 --> 00:45:14,000
ако е ист број на
линии, а не во некој циклус,

1113
00:45:14,000 --> 00:45:16,577
и независно од големината на
на листата, апсолутно.

1114
00:45:16,577 --> 00:45:18,660
Бришење на елемент во
на почетокот на листата,

1115
00:45:18,660 --> 00:45:21,940
дури и ако ние треба да се занимаваат со
Габе, се уште е постојана време.

1116
00:45:21,940 --> 00:45:24,220
>> Значи ова се чини како
масивни чекор наназад.

1117
00:45:24,220 --> 00:45:27,000
И што е губење на време
ако во една недела и недела

1118
00:45:27,000 --> 00:45:30,250
нула имавме не само
pseudocode код, но реалните код

1119
00:45:30,250 --> 00:45:35,780
за спроведување на нешто што е дневник
база n, или да се најавите, туку од n, база 2,

1120
00:45:35,780 --> 00:45:37,150
во однос на своите работи време.

1121
00:45:37,150 --> 00:45:40,710
Значи, зошто е грижам ние би сакале да започне
користење на нешто како се поврзани листа?

1122
00:45:40,710 --> 00:45:41,517
Да.

1123
00:45:41,517 --> 00:45:44,022
>> ПУБЛИКАТА: Значи можете да додадете
елементи на низата.

1124
00:45:44,022 --> 00:45:46,230
Дејвид Џ MALAN: Значи можете да
додадете елементи на низата.

1125
00:45:46,230 --> 00:45:47,550
И тоа исто така е тематски.

1126
00:45:47,550 --> 00:45:49,740
И ние ќе продолжиме да ја видите
ова, оваа трампа, многу

1127
00:45:49,740 --> 00:45:51,573
како видовме
трампа со спојување вид.

1128
00:45:51,573 --> 00:45:54,606
Ние навистина би можеле да го забрзаат
пребарување или сортирање, поточно,

1129
00:45:54,606 --> 00:45:57,480
ако ние трошиме малку повеќе простор и
имаат дополнителен парче на меморија

1130
00:45:57,480 --> 00:45:58,760
или низа за спојување вид.

1131
00:45:58,760 --> 00:46:01,270
Но, ние трошиме повеќе
простор, но заштедите време.

1132
00:46:01,270 --> 00:46:04,820
Во овој случај, ние сме
откажување време, но ние сме

1133
00:46:04,820 --> 00:46:08,170
стекнување на флексибилност,
динамика ако сакате,

1134
00:46:08,170 --> 00:46:10,280
кој е веројатно позитивна карактеристика.

1135
00:46:10,280 --> 00:46:11,520
>> Ние сме, исто така трошење простор.

1136
00:46:11,520 --> 00:46:13,710
Во која смисла е поврзан
листа поскапи

1137
00:46:13,710 --> 00:46:15,700
во смисла на простор од низа?

1138
00:46:15,700 --> 00:46:18,379

1139
00:46:18,379 --> 00:46:19,920
Каде е екстра простор доаѓаат од?

1140
00:46:19,920 --> 00:46:20,460
Да?

1141
00:46:20,460 --> 00:46:21,800
>> ПУБЛИКАТА: [Беззвучен] покажувач.

1142
00:46:21,800 --> 00:46:23,310
>> Дејвид Џ MALAN: Да, ние
исто така, имаат покажувач.

1143
00:46:23,310 --> 00:46:25,560
Значи ова е minorly досадни
во кој повеќе не сум

1144
00:46:25,560 --> 00:46:27,780
Јас складирање само int
да претставува цел број.

1145
00:46:27,780 --> 00:46:30,990
Јас сум чување на int и
покажувач, кој исто така е 32 бита.

1146
00:46:30,990 --> 00:46:33,470
Па јас сум буквално удвојување
износот на простор се вклучени.

1147
00:46:33,470 --> 00:46:36,040
Па тоа е трампа, но
тоа е во случај на int.

1148
00:46:36,040 --> 00:46:39,580
Да претпоставиме дека не сте складирање int,
но претпоставувам секој од овие правоаголници

1149
00:46:39,580 --> 00:46:43,290
или од секоја од овие луѓе беше ги претставуваат
еден збор, на англиски зборот што

1150
00:46:43,290 --> 00:46:46,430
може да биде пет карактери, 10
карактери, можеби дури и повеќе.

1151
00:46:46,430 --> 00:46:49,940
Потоа додавање на само 32 повеќе битови
може да биде помалку од една голема зделка.

1152
00:46:49,940 --> 00:46:52,160
>> Што ако секој од студентите
во демонстрациите

1153
00:46:52,160 --> 00:46:55,107
беа буквално студент structs дека
имаат имиња и куќи, а можеби и

1154
00:46:55,107 --> 00:46:57,065
телефонски броеви и Твитер
рачки и слично.

1155
00:46:57,065 --> 00:46:59,564
Така што сите на полиња почнавме
зборуваме за друг ден,

1156
00:46:59,564 --> 00:47:02,410
многу помалку од една голема зделка, како
нашите јазли се поинтересна

1157
00:47:02,410 --> 00:47:05,972
и големи да поминат, еј, дополнителни
покажувачот само за да ги поврзат заедно.

1158
00:47:05,972 --> 00:47:07,180
Но, навистина, тоа е трампа.

1159
00:47:07,180 --> 00:47:09,560
И навистина, го кодот е
посложени, како што ќе

1160
00:47:09,560 --> 00:47:11,770
види со впивам преку
таа пример.

1161
00:47:11,770 --> 00:47:14,302
Но, што ако имало
некои светиот грал тука.

1162
00:47:14,302 --> 00:47:17,010
Што ако не се преземе чекор
наназад, но голем чекор напред

1163
00:47:17,010 --> 00:47:19,180
и спроведување на податоци
структура преку која

1164
00:47:19,180 --> 00:47:22,870
може да се најдат елементи како Џек или
Кристин или било кој други елементи

1165
00:47:22,870 --> 00:47:25,870
во оваа низа во вистинска постојано време?

1166
00:47:25,870 --> 00:47:26,920
Пребарување е константна.

1167
00:47:26,920 --> 00:47:28,320
Избришете е константна.

1168
00:47:28,320 --> 00:47:29,570
Вметнете е константна.

1169
00:47:29,570 --> 00:47:32,260
Сите овие операции се константа.

1170
00:47:32,260 --> 00:47:33,750
Тоа ќе биде нашата светиот грал.

1171
00:47:33,750 --> 00:47:36,690
И дека е местото каде што
ќе ги собереш следниот пат.

1172
00:47:36,690 --> 00:47:38,600
Се гледаме тогаш.

1173
00:47:38,600 --> 00:47:39,371