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
DAVID J. 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
Ако бихте искали да се присъединят към нас,
отправят към обичайната URL адреса тук.

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
Останете на линия за курса
сайт за местоположение и подробности.

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
Просто-- това ще бъде невероятно.

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
OK.

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, Random Access Memory, където
той живее, докато захранването се изключва,

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
или когато стартирате точка наклонена черта Mario на
Linux компютър в терминален прозорец ви,

47
00:02:08,030 --> 00:02:12,460
от нули и единици, които съставят
Word или Mario се съхранява временно

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

49
00:02:16,610 --> 00:02:19,080
По-долу, че отива инициализира
и неинициализирани данни.

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
>> DAVID J. 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
>> DAVID J. 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
само като един от Аненберг
трапезария корита, както и неща

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

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

70
00:03:06,290 --> 00:03:08,602
като температура, тези две
до края на стека.

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

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
Е, и това е преминаване в argv [1].

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

103
00:04:43,960 --> 00:04:49,310
и след това произволна функция на
отгоре, е, отнема в низ, AKA Чар *,

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
И тогава тя декларира, вътре
на е, за масив от знаци

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
>> АУДИТОРИЯ: On стека.

113
00:05:08,590 --> 00:05:09,420
>> DAVID J. Malan: On стека.

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
Така н символи ще бъдат
копиран от бар в C.

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
DAVID J. Malan: Не включва
стая за нищожна характер.

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

135
00:06:02,073 --> 00:06:04,810
има толкова много като плюс 1 до
настанят че нищожна характер.

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
DAVID J. Malan: Perfect.

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

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
Е, тук е увеличената-версия на
тази картина на паметта на моя компютър.

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
ефективно получава сложи върху купчината
така че, когато е се извършва нейното изпълнение

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
Е, това малко
трохи в червено тук,

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
Но това е идеята. F
просто трябва да се знае какво

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
Така че в началото на тази картина в
син е на стека рамка за F, така че всичко,

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
Bar е нейната теза.

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
Какво предстои да се случи, ако ние минаваме
в низ бар, който е по-дълъг от C?

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
>> АУДИТОРИЯ: Е, това се случва
да презапишете Чар * бара.

208
00:09:19,260 --> 00:09:22,260
>> DAVID J. Malan: Да, тя изглежда като
ти започваш да презапишете Чар * бар.

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
Което отново е точно като
трохи да каже на програмата, където

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
>> Така че, ако всеки от тях
букви A точно представлява,

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-RFS, но също

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
можете ефективно да подвежда компютъра
в забележи, когато F е направено изпълнение,

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
Това всъщност е нещо като Bash,
или действително програма, която му дава

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
Java е имунизиран, например,
на този конкретен въпрос.

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
ако някога видя намек за нещо
като препълване на буфера атака,

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
ние питаш оперативните
система, Linux, за паметта.

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
по начин, който отива отвъд просто казвам,
това е междинно съединение, това е знак.

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, 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
>> DAVID J. Malan: Моля?

345
00:15:31,315 --> 00:15:32,380
>> АУДИТОРИЯ: Сложете го на края.

346
00:15:32,380 --> 00:15:33,796
>> DAVID J. 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 и Дейвин и Гейб имена

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
A показалка, нали?

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
>> DAVID J. Malan: Какво е това?

409
00:18:17,360 --> 00:18:17,880
>> АУДИТОРИЯ: New структура.

410
00:18:17,880 --> 00:18:19,590
>> DAVID J. Malan: Да, така че защо
не ние създаваме нова структура,

411
00:18:19,590 --> 00:18:20,920
или в C, а структурата?

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
че Stanford създаден, за да
клъстер информация заедно.

416
00:18:34,810 --> 00:18:38,580
И какво от това, ако вземем същата тази идея за
ключовите думи "typedef" и "структура"

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

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

419
00:18:46,210 --> 00:18:49,980
термин за нещо в структурата на данните,
контейнер в структурата на данните.

420
00:18:49,980 --> 00:18:53,900
Възел, аз твърдя, ще има
едно цяло число N, напълно ясна,

421
00:18:53,900 --> 00:18:58,810
и след това малко по-загадъчно
тази втора линия, структурата възел * следващия.

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
DAVID J. Malan: A
указател към друг възел.

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
Това е малко по-многословен, този път,
но това е от тип структура възел *.

431
00:19:18,206 --> 00:19:22,960
Всеки път, когато съм виждал нещо звезда, че
означава, че е указател към този тип данни.

432
00:19:22,960 --> 00:19:26,810
Така че следващия очевидно е
указател към структура възел.

433
00:19:26,810 --> 00:19:28,310
>> Сега, това, което е структура на възел?

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
но това е наистина само ФОРМАТ.

463
00:20:46,460 --> 00:20:50,930
И сега съм си дал малко меню
options-- Изтриване, Insert, издирване,

464
00:20:50,930 --> 00:20:51,750
и Traverse.

465
00:20:51,750 --> 00:20:52,630
И Quit.

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
Insert ще добавите
номер към списъка.

469
00:21:00,200 --> 00:21:02,181
Search ще изглежда
за номер в списъка.

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
Така че за сега нека да предвидят, че
Изтрий и Traverse и Search направя,

495
00:21:58,980 --> 00:21:59,760
в действителност, да работят.

496
00:21:59,760 --> 00:22:04,180
В действителност, ако аз тичам Search, нека
търсите номера 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, структура на възел,

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

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 е файл, искам
да се включат в моя C файл.

519
00:22:59,690 --> 00:23:03,910
И след това в някакъв момент, че съм
Ще трябва ПНА, основната, анулира.

520
00:23:03,910 --> 00:23:06,530
И тогава аз отивам да
има някои неща за вършене тук.

521
00:23:06,530 --> 00:23:10,620
Аз съм също ще има
прототип, като нищожен, търсене, вътр,

522
00:23:10,620 --> 00:23:13,610
N, чиято цел в живота е
за търсене на елемент.

523
00:23:13,610 --> 00:23:18,310
И след това тук аз твърдя в
днешния код, нищожен, търсене, ПНА, п,

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
DAVID J. Malan: A указател към възел.

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
>> DAVID J. Malan: Да,
вероятно само първия.

555
00:24:31,942 --> 00:24:34,030
И забележи, на първо
възел е с различна форма.

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

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
Не само е нищожна използва като като специален
върнатата стойност за неща като 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
И под "наистина работи" I
да кажа, много прилича на низ,

578
00:25:39,250 --> 00:25:42,180
ни позволява да премине от първия знак
в име Дейвин към втория,

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
>> Толкова дълго, тъй като ние сме садене
Всички тези възли заедно,

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
Дявол да го вземе, това е голям O на 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
ОХ1, ОХ50, 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
Така че, ако аз съм функция за търсене и
Аз съм дал променлива, число п

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

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

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
Въпреки че структура, наречена възел
има стойност н, напълно законен

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

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

637
00:28:20,085 --> 00:28:22,087
че п е вероятно
различен от този вал.

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
като обявим, че ние открихме, п.

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
Ако пръстът ми в
момент е PTR, и това е

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
Е, какъв е трохи сме
ще следват в този случай?

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
DAVID J. 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
ще отида напред и да кажа, показалка, която
е само временно променлива-- това е

658
00:29:12,990 --> 00:29:15,320
странно име, PTR, но
Това е точно като temp--

659
00:29:15,320 --> 00:29:19,234
Отивам да зададете на показалеца
равна на каквото и показалеца е--

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
DAVID J. 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
за конструкции, показалеца не е структура.

675
00:29:55,220 --> 00:29:56,580
PTR е какво?

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-- аз не
мисля, че съм по-извършване тук-- I

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
все още можете да използвате нотация точка.

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
Ти буквално казва, сочен
показалеца и там.

700
00:30:56,530 --> 00:30:59,320
След това вземете .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
>> DAVID J. Malan: Andrew,
сте номер 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
DAVID J. 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
>> DAVID J. 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
АУДИТОРИЯ: Christian.

746
00:32:29,340 --> 00:32:30,715
DAVID J. Malan: Christian, Дейвид.

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
>> АУДИТОРИЯ: JP.

750
00:32:32,649 --> 00:32:33,440
DAVID J. Malan: JP.

751
00:32:33,440 --> 00:32:34,880
Номер 29.

752
00:32:34,880 --> 00:32:37,080
Така че продължавайте напред и да получите в-- Uh о.

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

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

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

756
00:32:39,650 --> 00:32:40,150
Standby.

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
DAVID J. Malan: Имаш Sharpie?

762
00:32:45,660 --> 00:32:46,159
OK.

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
DAVID J. 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
I е неправилно изписана 29, но OK.

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-- OK, който иска да бъде 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
>> АУДИТОРИЯ: Peter.

799
00:33:42,040 --> 00:33:43,456
>> DAVID J. Malan: Peter, хайде нагоре.

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
OK, и номер 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
И наистина, това ще бъде едно
на голям снимката храна за вкъщи тук, е,

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

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
DAVID J. 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
И аз отивам да има PTR, които
Ще представлявам тук с моя пръст,

833
00:35:07,670 --> 00:35:08,370
както обикновено.

834
00:35:08,370 --> 00:35:12,430
>> И не забравяйте, каква стойност
сме се инициализира PTR да?

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
Ако задам PTR равна на първо място, това, което
трябва ръката ми наистина да сочи?

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
>> АУДИТОРИЯ: Jack.

871
00:36:31,420 --> 00:36:32,295
>> DAVID J. 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
I инициализира ми PTR
указател към номер 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
Чиито ръце, Гейб или Давид
или-- какво е името на номер 9 е?

881
00:36:54,820 --> 00:36:55,740
>> АУДИТОРИЯ: Джен.

882
00:36:55,740 --> 00:36:58,406
>> DAVID J. Malan: hands-- Джен
кои от нашите ръце, трябва да се промени?

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
>> Добре, така сега-- и
Като настрана, имената

899
00:37:24,280 --> 00:37:28,510
Аз не съм на изрично споменаване на правото
сега, Предвиждане показалка, предшественик на показалеца

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
>> DAVID J. 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
DAVID J. 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
Така ръката ви може да бъде вид
надолу нула или някаква стойност боклук.

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
И аз осъзнавам, ох, Джулия
трябва да отида до 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
Джулия, мина, или--
какъв ти е името?

939
00:38:38,360 --> 00:38:39,230
>> АУДИТОРИЯ: Christian.

940
00:38:39,230 --> 00:38:40,060
>> DAVID J. Malan: Christian или?

941
00:38:40,060 --> 00:38:40,560
>> Публика: Анди.

942
00:38:40,560 --> 00:38:40,905
>> DAVID J. Malan: Andy.

943
00:38:40,905 --> 00:38:41,654
Christian или Анди?

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
И сега имам не само указател към
елементът, който върви след Julia,

967
00:39:33,090 --> 00:39:36,300
Аз все още имам указател към
Анди елемент преди.

968
00:39:36,300 --> 00:39:39,430
Така имате достъп, по същество,
галета, ако щете,

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
I може да има същия вид на код,
но аз отивам да имат нужда от една или две стъпки.

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
>> АУДИТОРИЯ: Jack.

994
00:40:45,380 --> 00:40:46,255
>> DAVID J. Malan: Jack.

995
00:40:46,255 --> 00:40:49,770
Аз трябва да не само evict-- безплатно Jack,
така буквално се обаждате безплатно Джак, или най-малко

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
Защото веднага щом се обаждате безплатно на
Джак, ако Петър все още сочеше Jack

999
00:40:59,300 --> 00:41:02,530
и затова аз продължавам преминаващи
списъка и достъпа този указател,

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
>> DAVID J. 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
АУДИТОРИЯ: Christine трябва
е нищожен [недоловим].

1021
00:41:46,600 --> 00:41:50,244
DAVID J. Malan: Добре, ние трябва най-вероятно
make-- чух "нула" някъде.

1022
00:41:50,244 --> 00:41:51,410
АУДИТОРИЯ: Null и я освободи.

1023
00:41:51,410 --> 00:41:51,855
DAVID J. Malan: Null какво?

1024
00:41:51,855 --> 00:41:53,074
АУДИТОРИЯ: Null и я освободи.

1025
00:41:53,074 --> 00:41:54,490
DAVID J. Malan: Null и я освободи.

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
И така, ние бяхме по-добре се обаждате безплатно сега нататък
Christine да дам, че паметта обратно.

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
използване на байта на Кристин
памет вече.

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
>> [APPLAUSE]

1046
00:42:45,320 --> 00:42:46,700
>> DAVID J. Malan: Добре.

1047
00:42:46,700 --> 00:42:51,110
Така няколко аналитична
въпроси тогава, ако можех.

1048
00:42:51,110 --> 00:42:59,670
Видяхме тази нотация и преди,
голям O и омега, горните граници

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
>> One, и ние го каза
преди, какво е управлението

1052
00:43:07,090 --> 00:43:10,647
време на търсене на
списък по отношение на голям O?

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
Това е голям O на 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
DAVID J. Malan: отново Кажи?

1065
00:43:40,920 --> 00:43:41,800
АУДИТОРИЯ: Random достъп.

1066
00:43:41,800 --> 00:43:43,049
DAVID J. Malan: Random достъп.

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
се види, че Анди или Christian бяха
приблизително в средата на списъка,

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
>> Толкова големи О п сега е на горната
граница на нашето време за търсене.

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
DAVID J. Malan: отново Кажи?

1079
00:44:13,040 --> 00:44:13,420
АУДИТОРИЯ: One.

1080
00:44:13,420 --> 00:44:13,800
DAVID J. Malan: One.

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
DAVID J. Malan: отново Кажи?

1094
00:44:36,420 --> 00:44:37,067
АУДИТОРИЯ: п.

1095
00:44:37,067 --> 00:44:38,900
DAVID J. Malan: н е
наистина горната граница.

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
Gabe също беше в началото,
и ние също трябваше да актуализира Габе.

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
DAVID J. 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
>> DAVID J. Malan: Да, ние
Също така имате показалеца.

1143
00:46:23,310 --> 00:46:25,560
Така че това е minorly досадно
с това, че вече не съм

1144
00:46:25,560 --> 00:46:27,780
I съхраняване само INT
да представлява вътр.

1145
00:46:27,780 --> 00:46:30,990
Аз съм съхраняване на едно цяло число и
указател, който е 32 бита.

1146
00:46:30,990 --> 00:46:33,470
Така че аз съм буквално удвояване
размера на пространството, участващи.

1147
00:46:33,470 --> 00:46:36,040
Така че това е компромис, но
това е в случай на вътр.

1148
00:46:36,040 --> 00:46:39,580
Да предположим, че вие ​​не сте съхраняване на ПНА,
но предполагам, че всеки един от тези правоъгълници

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
телефонни номера и Twitter
дръжки и други подобни.

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
може да намерите елементи като Джак или
Christine или други елементи

1165
00:47:22,870 --> 00:47:25,870
в този масив в истинската константно време?

1166
00:47:25,870 --> 00:47:26,920
Search е постоянна.

1167
00:47:26,920 --> 00:47:28,320
Изтрий е постоянна.

1168
00:47:28,320 --> 00:47:29,570
Insert е постоянна.

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