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. малая: Добра.

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
Больш падрабязна можна
знайшоў па гэтым адрасе тут.

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
Добра.

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
Так памяці або аператыўнай памяці, дзе праграмы
існуюць у той час як вы працуеце іх.

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
ў аператыўнай памяці, памяці адвольнага доступу, дзе
ён жыве, пакуль харчаванне не адключыцца,

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 або ПК,

46
00:02:03,910 --> 00:02:08,030
або пры запуску кропку слэш Марыё на
Linux кампутар у вашым акне тэрміналу,

47
00:02:08,030 --> 00:02:12,460
нулі і адзінкі, якія складаюць
Слова або Марыё часова захоўваюцца

48
00:02:12,460 --> 00:02:16,610
ў аператыўнай памяці кампутара ў так званы
тэкставы сегмент для канкрэтнай праграмы.

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. малая: Для функцый?

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. малая: Точно.

64
00:02:49,660 --> 00:02:52,650
Пры выкліку функцыі, яе
Аргументы капіююцца ў стэк.

65
00:02:52,650 --> 00:02:56,330
Таму любыя іксы або Y сайт або сайт або B,
што вы перадаеце ў функцыю

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
унізе мы ўбачылі некаторы час таму, калі
Я быў важдацца з клавіятуры адзін дзень

73
00:03:15,690 --> 00:03:20,050
і я пачаў доступу рэчы
як агду 100 ці агду 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
Кантузія, што было
жыцця даволі шмат кампутараў.

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
А потым ён заяўляе, усярэдзіне
з F, масіў сімвалаў

107
00:04:57,470 --> 00:04:59,930
называецца c-- 12 такіх знакаў.

108
00:04:59,930 --> 00:05:03,580
>> Зараз, па гісторыі, якую я распавядаў
хвіліну таму, калі ў памяці

109
00:05:03,580 --> 00:05:06,720
з'яўляецца с, або тыя, 12
сімвалы будзе ў канчатковым выніку?

110
00:05:06,720 --> 00:05:07,570
Проста каб быць ясна.

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

112
00:05:08,070 --> 00:05:08,590
>> АЎДЫТОРЫЯ: На стэку.

113
00:05:08,590 --> 00:05:09,420
>> David J. малая: На стэку.

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
Гэта азначае радок копію, але
толькі рускія літары, п знакаў.

121
00:05:25,200 --> 00:05:31,990
Так п сімвалаў будзе
капіюецца з бара ў с.

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. малая: Не ўключае
пакой для нулявога знака.

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. малая: Выдатна.

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 знакаў з бара ў С, тым самым

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
У прыватнасці, калі асноўныя выклікі Фу, асноўныя сайт
уласны адрас у памяці, бык-то,

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
>> Так што, калі мы тут канцэптуальна,
у асноўны, то F выклікаецца.

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
Але гэта ідэя. е
проста павінен ведаць, што

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
з памяці, што F
спецыяльна выкарыстоўвае.

188
00:08:19,630 --> 00:08:22,990
Так, адпаведна, заўважыць, што
Бар у гэтай карціне.

189
00:08:22,990 --> 00:08:23,980
Бар быў яго аргумент.

190
00:08:23,980 --> 00:08:27,240
І мы сцвярджалі, што аргументы
Функцыі атрымаць у стэк.

191
00:08:27,240 --> 00:08:29,910
І з, вядома,
Таксама ў гэтай карціне.

192
00:08:29,910 --> 00:08:33,520
>> І толькі для пазначэнняў мэтаў,
заўважыць ў верхнім левым куце

193
00:08:33,520 --> 00:08:37,020
тое, што было б з кранштэйнам 0 і
затым злёгку ўніз, направа

194
00:08:37,020 --> 00:08:38,220
з'яўляецца з кранштэйна 11.

195
00:08:38,220 --> 00:08:41,240
Такім чынам, іншымі словамі, вы можаце сабе ўявіць
што ёсць сетка байт

196
00:08:41,240 --> 00:08:44,380
ёсць, першы з якіх
верхні левы, ніжні з якіх

197
00:08:44,380 --> 00:08:48,360
апошні з гэтых 12 байт.

198
00:08:48,360 --> 00:08:49,930
>> Але цяпер паспрабуйце для хуткай перамоткі наперад.

199
00:08:49,930 --> 00:08:55,580
Што павінна адбыцца, калі мы перадамо
у струннай бары, гэта больш, чым з?

200
00:08:55,580 --> 00:08:59,130
І мы не праверка, калі
гэта сапраўды больш, чым 12.

201
00:08:59,130 --> 00:09:03,146
Якая частка гэтай карціны збіраецца
страчаны байт 0, 1, 2, 3,

202
00:09:03,146 --> 00:09:07,890
кропка кропка кропка, 11, а затым
дрэнна, 12, 13 праз 19?

203
00:09:07,890 --> 00:09:11,820
Што адбудзецца тут,
калі вы вывесці з замовы

204
00:09:11,820 --> 00:09:14,790
што з кранштэйны 0 знаходзіцца на вяршыні
і з кранштэйны 11 з'яўляецца свайго роду ўніз

205
00:09:14,790 --> 00:09:15,812
ў парадку?

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

207
00:09:16,796 --> 00:09:19,260
>> АЎДЫТОРЫЯ: Ну, гэта будзе
перазапісаць сімвал * бар.

208
00:09:19,260 --> 00:09:22,260
>> David J. малая: Так, гэта выглядае як
Вы збіраецеся перазапісаць сімвал * бар.

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
вярнуцца да таго, калі F
робіцца пры выкліку.

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-РФ, што выдаліць усе
з жорсткага дыска ці рассылання спаму

234
00:10:25,150 --> 00:10:27,000
ці інакш атакаваць машыну?

235
00:10:27,000 --> 00:10:29,570
>> Такім чынам, калі кожны з іх
Лісты проста ўяўляе,

236
00:10:29,570 --> 00:10:32,380
канцэптуальна, атака, атака,
атака, атака, некаторыя дрэнныя код

237
00:10:32,380 --> 00:10:36,410
што хто-то напісаў, але
калi гэта асоба досыць разумны,

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
Вы можаце эфектыўна падмануць кампутар
у заўважаючы пры е робіцца выканання,

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-РФ.

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
мы можам Malloc што шмат памяці.

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 неўсвядомлена для
некалькі тыдняў, усё памяці Malloc ў

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
такім чынам, што выходзіць за рамкі проста кажу,
Гэта Int, гэта сімвал.

324
00:14:50,720 --> 00:14:52,930
Мы можам пачаць кластара рэчаў разам.

325
00:14:52,930 --> 00:14:54,460
>> Так масіў выглядае наступным чынам.

326
00:14:54,460 --> 00:14:57,270
І тое, што было ключавым у аб
Масіў з'яўляецца тое, што яна дае вам

327
00:14:57,270 --> 00:14:59,724
спіна да спіны кавалкі
памяці, кожны з якіх

328
00:14:59,724 --> 00:15:02,765
будзе таго ж тыпу, Int,
Int, Int, 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. малая: Выбачайце?

345
00:15:31,315 --> 00:15:32,380
>> АЎДЫТОРЫЯ: Пакладзеце яго на канцы.

346
00:15:32,380 --> 00:15:33,796
>> David J. малая: Пакладзеце яго на канцы.

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
Паказальнік, ці не так?

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
Зараз, я яшчэ не ў курсе любога тыпу дадзеных
у С, што дае не толькі 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. малая: Што гэта?

409
00:18:17,360 --> 00:18:17,880
>> АЎДЫТОРЫЯ: Новая структура.

410
00:18:17,880 --> 00:18:19,590
>> David J. малая: Так, так чаму
ня мы ствараем новую структуру,

411
00:18:19,590 --> 00:18:20,920
або ў С, структуры?

412
00:18:20,920 --> 00:18:25,990
Мы бачылі структур і раней, калі коратка,
дзе мы мелі справу са студэнцкай структуры

413
00:18:25,990 --> 00:18:27,780
як гэта, хто меў імя і дом.

414
00:18:27,780 --> 00:18:31,980
У Pset 3 прарыў вы выкарыстоўвалі цэлы
куча structs-- GRect і GOvals

415
00:18:31,980 --> 00:18:34,810
, Што Стэнфард стварыў у
Кластар інфармацыя разам.

416
00:18:34,810 --> 00:18:38,580
Так што, калі мы возьмем гэтую ж ідэю
ключавыя словы "аб'яваў тыпаў" і "структурай,"

417
00:18:38,580 --> 00:18:42,890
а затым некаторыя студэнт-канкрэтныя рэчы,
і развівацца гэта ў наступным:

418
00:18:42,890 --> 00:18:46,210
ЬурейеЕ структуры node-- і вузел
толькі вельмі агульнае інфарматыка

419
00:18:46,210 --> 00:18:49,980
Тэрмін-то ў структуры дадзеных,
Кантэйнер ў структуры дадзеных.

420
00:18:49,980 --> 00:18:53,900
Вузел я сцвярджаю, будзе мець
Int N, вельмі просты ,,

421
00:18:53,900 --> 00:18:58,810
а затым яшчэ трохі загадкава,
гэта другая лінія, структура вузла * наступны.

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. малая:
паказальнік на іншы вузел.

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
І калі я запускаю гэта я стварыў супер
просты графічны інтэрфейс, графічны інтэрфейс карыстальніка,

462
00:20:44,980 --> 00:20:46,460
але гэта сапраўды проста PRINTF.

463
00:20:46,460 --> 00:20:50,930
І зараз я даў сабе некалькі меню
options-- Выдаліць, Уставіць, Пошук,

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
Устаўце збіраецца дадаць
лік у спіс.

469
00:21:00,200 --> 00:21:02,181
Пошук будзе выглядаць
лікі ў спісе.

470
00:21:02,181 --> 00:21:04,930
І траверс толькі мудрагелісты спосаб
сказаць, хадзіць па спісе,

471
00:21:04,930 --> 00:21:06,245
раздрукаваць яго, але гэта так.

472
00:21:06,245 --> 00:21:07,720
Не змяняйце яго ў любым выпадку.

473
00:21:07,720 --> 00:21:08,570
>> Так давайце паспрабуем гэта.

474
00:21:08,570 --> 00:21:10,160
Давайце пойдзем далей і ўвесці 2.

475
00:21:10,160 --> 00:21:12,710
А потым я збіраюся
ўвядзіце нумар, кажуць 9.

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

477
00:21:13,620 --> 00:21:17,480
І цяпер мая праграма проста
запраграмаваны сказаць, спіс зараз 9.

478
00:21:17,480 --> 00:21:20,190
Зараз, калі я пайду наперад і
у Устаўце зноў, хай

479
00:21:20,190 --> 00:21:23,680
мне ісці наперад і памяншэння маштабу і ўвядзіце ў 17.

480
00:21:23,680 --> 00:21:25,770
Цяпер мой спіс 9, затым 17.

481
00:21:25,770 --> 00:21:27,750
Калі я ўставіць зноў, давайце прапусцім адзін.

482
00:21:27,750 --> 00:21:32,400
Замест 22, як за карціны мы ў
глядзеў на тут, дазвольце мне перайсці наперад

483
00:21:32,400 --> 00:21:34,630
і ўставіць 26 наступная.

484
00:21:34,630 --> 00:21:36,230
Так што я збіраюся набраць 26.

485
00:21:36,230 --> 00:21:37,755
Гэты спіс, як я чакаю.

486
00:21:37,755 --> 00:21:40,630
Але цяпер, проста каб паглядзець, калі гэтага кода
збіраецца быць гнуткім, дазвольце мне цяпер

487
00:21:40,630 --> 00:21:43,520
Тып 22, якая, па меншай меры
канцэптуальна, калі мы

488
00:21:43,520 --> 00:21:46,520
Маючы гэта сартуюцца, якія сапраўды
будзе іншая мэта прама зараз,

489
00:21:46,520 --> 00:21:48,690
павінны пайсці ў перыяд з 17 па 26.

490
00:21:48,690 --> 00:21:50,270
Так я трапіў Enter.

491
00:21:50,270 --> 00:21:51,380
На самай справе, што працуе.

492
00:21:51,380 --> 00:21:54,950
І вось цяпер дазвольце мне ўставіць
нарэшце, за карціны, 34.

493
00:21:54,950 --> 00:21:55,450
>> Добра.

494
00:21:55,450 --> 00:21:58,980
Так што на дадзены дазвольце мне прадугледжваюць, што
Выдаліць і Traverse і пошук зрабіць,

495
00:21:58,980 --> 00:21:59,760
На самай справе, працаваць.

496
00:21:59,760 --> 00:22:04,180
На самай справе, калі я запусціць пошук, давайце
пошук па нумары 22, Enter.

497
00:22:04,180 --> 00:22:05,010
Было ўстаноўлена, 22.

498
00:22:05,010 --> 00:22:07,580
Так што тое, што гэта
Праграма Спіс Нуль робіць.

499
00:22:07,580 --> 00:22:10,230
>> Але што на самай справе адбываецца
на які рэалізуе гэта?

500
00:22:10,230 --> 00:22:14,530
Ну, спачатку я, магчыма, прыйдзецца, і на самай справе
У мяне ёсць, файл з імем list0.h.

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

502
00:22:16,540 --> 00:22:20,690
І дзе-то там гэта
лінія, ЬурейеЕ, структура вузла,

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
Структура, вузел побач.

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
А потым у пэўны момант я
прыйдзецца Int, галоўная, анулявання.

520
00:23:03,910 --> 00:23:06,530
А потым я збіраюся
ёсць некаторыя да справы тут.

521
00:23:06,530 --> 00:23:10,620
Я таксама збіраюся мець
Прататып, як пустэч, пошук, INT,

522
00:23:10,620 --> 00:23:13,610
н, чыя мэта ў жыцці
шукаць элемента.

523
00:23:13,610 --> 00:23:18,310
А потым сюды я сцвярджаю ў
сённяшняя код, несапраўднымі, пошук, Int, н,

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. малая: паказальнік на вузел.

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. малая: Так,
верагодна, толькі першы.

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
І "на самай справе працуе" я
значыць, гэтак жа, як радкі,

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 н,
што не дрэнна, справядлівасці дзеля.

600
00:26:33,470 --> 00:26:34,800
Але гэта з'яўляецца лінейным.

601
00:26:34,800 --> 00:26:37,980
Мы адмовіліся ад таго, што функцыя
масіваў шляхам перамяшчэння больш

602
00:26:37,980 --> 00:26:43,130
да гэтай карціне дынамічна
пераплятаюцца або звязаны вузлы?

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

604
00:26:44,970 --> 00:26:46,687
Мы адмовіліся ад выпадковага доступу.

605
00:26:46,687 --> 00:26:48,770
Масіў прыемна, таму што
матэматычна ўсе

606
00:26:48,770 --> 00:26:50,340
з'яўляецца спіна да спіны да спіны да спіны.

607
00:26:50,340 --> 00:26:52,370
Нават пры тым, што гэтай карціне
выглядае прыгожа, і нават

608
00:26:52,370 --> 00:26:55,830
хоць гэта выглядае як гэтых вузлоў
прыгожа разнесеныя, у рэальнасці

609
00:26:55,830 --> 00:26:56,830
яны могуць быць дзе заўгодна.

610
00:26:56,830 --> 00:27:01,590
Ox1, Ox50, Ox123, Ox99, гэтыя
вузлы могуць быць дзе заўгодна.

611
00:27:01,590 --> 00:27:05,960
Таму Таноса робіць вылучыць памяць
з кучы, але ў любым месцы ў кучы.

612
00:27:05,960 --> 00:27:09,080
Вам не абавязкова ведаць, што гэта
будзе спіна да спіны да спіны.

613
00:27:09,080 --> 00:27:12,460
І так гэтая карціна ў Рэальнасці
не збіраецца быць гэтак значнай.

614
00:27:12,460 --> 00:27:16,140
>> Так ён збіраецца заняць крыху
працаваць над рэалізацыяй гэтай функцыі.

615
00:27:16,140 --> 00:27:17,880
Так давайце рэалізуем пошук цяпер.

616
00:27:17,880 --> 00:27:20,250
І мы ўбачым роду
разумны спосаб зрабіць гэта.

617
00:27:20,250 --> 00:27:24,660
Так што, калі я функцыя пошуку і
Я даў зменнай, лік п

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
>> Калі паказальнік кропка п, дазвольце мне вярнуцца
ў тым, што, 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
Фактычная п, які быў прыняты ў.

633
00:28:06,590 --> 00:28:09,020
Дык вось яшчэ адна асаблівасць
С і шматлікія мовы.

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
І мы пакінем гэта як
каментаваць або псевдокод код.

645
00:28:37,930 --> 00:28:40,190
Астатняе, і вось
цікавая частка, што

646
00:28:40,190 --> 00:28:47,320
я хачу рабіць, калі бягучы вузел
які не ўтрымлівае п, што я клапачуся аб?

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. малая: Так, так што ў наступны.

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
Я збіраюся ўсталяваць паказальнік
роўна якой паказальніка is--

660
00:29:19,234 --> 00:29:22,150
і зноў жа, гэта будзе
невялікая дзіцячая калыска для moment-- кропкай наступнага.

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

662
00:29:23,551 --> 00:29:26,550
Іншымі словамі, я збіраюся прыняць мае
палец, які, паказваючы на ​​гэтым вузле

663
00:29:26,550 --> 00:29:31,247
тут, і я збіраюся сказаць, вы ведаеце,
што, зірніце на наступнае поле

664
00:29:31,247 --> 00:29:33,330
і перамясціць палец у
там яно паказваючы на.

665
00:29:33,330 --> 00:29:35,163
І гэта будзе
Паўтараю, паўтараць, паўтараць.

666
00:29:35,163 --> 00:29:37,630
Але калі робіць свой палец
спыніць рабіць амаль нічога?

667
00:29:37,630 --> 00:29:40,095
Як толькі што радок кода удараў у?

668
00:29:40,095 --> 00:29:40,970
АЎДЫТОРЫЯ: [неразборліва]

669
00:29:40,970 --> 00:29:43,060
David J. малая: Калі кропка а
паказальнік ня роўны нулю.

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-- я не
думаю, што я больш-здзяйсненне здесь-- Я

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. малая: Андрэй,
вы нумар 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. малая: Джэн.

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. малая: Юлія, Дэвід.

743
00:32:26,980 --> 00:32:27,545
Колькасць 20.

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

745
00:32:28,507 --> 00:32:29,340
АЎДЫТОРЫЯ: Крысціян.

746
00:32:29,340 --> 00:32:30,715
David J. малая: Крысціян, Дэвід.

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. малая: JP.

751
00:32:33,440 --> 00:32:34,880
Колькасць 29.

752
00:32:34,880 --> 00:32:37,080
Так ісці наперад і атрымаць в-- Ой-ой.

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

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

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

756
00:32:39,650 --> 00:32:40,150
У рэжыме чакання.

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

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

759
00:32:42,390 --> 00:32:43,682
Хто-небудзь ёсць маркер?

760
00:32:43,682 --> 00:32:44,890
АЎДЫТОРЫЯ: У мяне ёсць шулеры.

761
00:32:44,890 --> 00:32:45,660
David J. малая: Вы атрымалі шулеры?

762
00:32:45,660 --> 00:32:46,159
Добра.

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

764
00:32:47,577 --> 00:32:49,160
І хто-небудзь ёсць лісток паперы?

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

766
00:32:51,562 --> 00:32:52,270
Захавайце лекцыю.

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

768
00:32:53,810 --> 00:32:55,362
Падыдзі.

769
00:32:55,362 --> 00:32:56,320
АЎДЫТОРЫЯ: У нас ёсць яго.

770
00:32:56,320 --> 00:32:57,600
David J. малая: Мы атрымалі яго?

771
00:32:57,600 --> 00:32:58,577
Добра, дзякуй.

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

773
00:33:01,380 --> 00:33:02,520
Тут мы ідзем.

774
00:33:02,520 --> 00:33:03,582
Ці быў гэты ад вас?

775
00:33:03,582 --> 00:33:04,540
Вы проста выратавалі дзень.

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

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

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

779
00:33:10,510 --> 00:33:11,110
Добра.

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

781
00:33:13,360 --> 00:33:14,890
Я няправільна 29, але добра.

782
00:33:14,890 --> 00:33:15,720
Працягвай.

783
00:33:15,720 --> 00:33:18,114
Добра, я дам вам
Ваш пяро назад на імгненне.

784
00:33:18,114 --> 00:33:19,280
Таму ў нас ёсць гэтыя людзі тут.

785
00:33:19,280 --> 00:33:20,330
Давайце адзін іншы.

786
00:33:20,330 --> 00:33:23,750
Гейб, ты хочаш гуляць
Першы элемент тут?

787
00:33:23,750 --> 00:33:25,705
Мы маем патрэбу ў вас, каб паказаць
на гэтых выдатных людзей.

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

789
00:33:26,930 --> 00:33:31,030
Так 9, 17, 20, 22, адсартуйце
з 29, а затым 34.

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

791
00:33:32,160 --> 00:33:33,325
Хіба мы губляем каго?

792
00:33:33,325 --> 00:33:33,950
У мяне ёсць 34.

793
00:33:33,950 --> 00:33:36,730
Дзе did-- ОК, хто хоча быць 34?

794
00:33:36,730 --> 00:33:37,605
ОК, давай да, 34.

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

796
00:33:39,280 --> 00:33:41,220
Добра, гэта будзе
варта кульмінацыя.

797
00:33:41,220 --> 00:33:41,550
Як цябе завуць?

798
00:33:41,550 --> 00:33:42,040
>> АЎДЫТОРЫЯ: Піцер.

799
00:33:42,040 --> 00:33:43,456
>> David J. малая: Піцер, давай до.

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
тут, ісці наперад і кропка
адзін на аднаго, з Gabe

809
00:34:07,585 --> 00:34:11,030
у прыватнасці, паказваючы на
нумар 9 для прадстаўлення спісу.

810
00:34:11,030 --> 00:34:14,050
ОК, і лік 34, левая рука
трэба проста паказваючы на ​​падлозе.

811
00:34:14,050 --> 00:34:15,750
>> ОК, так што гэта звязаны спіс.

812
00:34:15,750 --> 00:34:17,580
Так што гэта сцэнар пад пытаннем.

813
00:34:17,580 --> 00:34:20,210
І на самай справе, гэта прадстаўнік
з аднаго класа задач

814
00:34:20,210 --> 00:34:21,929
што вы маглі б паспрабаваць вырашыць з кодам.

815
00:34:21,929 --> 00:34:25,020
Вы хочаце, каб у канчатковым рахунку ўставіць
новы элемент у спіс.

816
00:34:25,020 --> 00:34:27,494
У гэтым выпадку, мы збіраемся
паспрабуйце ўставіць лік 55.

817
00:34:27,494 --> 00:34:28,500

818
00:34:28,500 --> 00:34:30,860
Але ёсць будзе
розныя выпадкі разгледзець.

819
00:34:30,860 --> 00:34:34,409
І на самай справе, гэта будзе адзін
з вялікай карціны ежы на дом тут, з'яўляецца,

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. малая: У канцы, у
сярэдні, або ў пачатку.

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
>> І памятайце, якое значэнне
ж мы ініцыялізаваць паказальнік на?

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
>> АЎДЫТОРЫЯ: Джэк.

871
00:36:31,420 --> 00:36:32,295
>> David J. малая: Джэк?

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
Я ініцыялізаваць мой 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. малая: 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
>> Добра, так now-- і
Як у баку, імёны

899
00:37:24,280 --> 00:37:28,510
Я не раблю прамога згадвання правы
Зараз, před паказальнік, паказальнік папярэднік

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. малая: Крысціна.

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. малая: Юлія, вы можаце поп
, І бабінец, што вы ніколі не былі там?

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
>> АЎДЫТОРЫЯ: Крысціян.

940
00:38:39,230 --> 00:38:40,060
>> David J. малая: хрысціянін ці?

941
00:38:40,060 --> 00:38:40,560
>> АЎДЫТОРЫЯ: Эндзі.

942
00:38:40,560 --> 00:38:40,905
>> David J. малая: Эндзі.

943
00:38:40,905 --> 00:38:41,654
Крысціян або Эндзі?

944
00:38:41,654 --> 00:38:44,280

945
00:38:44,280 --> 00:38:45,690
Эндзі павінен паказаць на?

946
00:38:45,690 --> 00:38:46,780

947
00:38:46,780 --> 00:38:47,341
Юлія.

948
00:38:47,341 --> 00:38:47,840
Добра.

949
00:38:47,840 --> 00:38:48,960
Так Эндзі, ты хочаш, каб паказаць на Джулію?

950
00:38:48,960 --> 00:38:50,120
Але пачакайце хвіліну.

951
00:38:50,120 --> 00:38:53,260
У гісторыі да гэтага часу,
Я-то адзін

952
00:38:53,260 --> 00:38:56,800
адказвае, у тым сэнсе, што
паказальнік з'яўляецца рэч, якая

953
00:38:56,800 --> 00:38:57,850
перасоўванне па спісе.

954
00:38:57,850 --> 00:39:00,800
Мы можам мець імя для Эндзі, але
няма пераменная называецца Эндзі.

955
00:39:00,800 --> 00:39:04,320
Адзіны іншай зменнай ў нас ёсць,
першы, хто прадстаўлены Гейба.

956
00:39:04,320 --> 00:39:07,690
>> Так што гэта на самай справе, чаму такім чынам
Пакуль мы не мелі патрэбу ў гэтым.

957
00:39:07,690 --> 00:39:10,846
Але цяпер на экране ёсць
яшчэ раз адзначыць, з před паказальніка.

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
Але дазвольце мне ёсць před паказальнік,
паказальнік папярэднік, гэта

963
00:39:22,500 --> 00:39:24,740
выгляд паказваючы на
элемент я быў проста ў.

964
00:39:24,740 --> 00:39:27,330
Таму, калі я іду сюды, зараз
Мая левая рука абнаўлення.

965
00:39:27,330 --> 00:39:29,370
Калі я іду тут мае левыя абнаўлення ўручную.

966
00:39:29,370 --> 00:39:33,090
І зараз у мяне ёсць не толькі паказальнік
элемент, які ідзе пасля Джуліі,

967
00:39:33,090 --> 00:39:36,300
Я да гэтага часу ёсць паказальнік на
Эндзі, элемент раней.

968
00:39:36,300 --> 00:39:39,430
Так у вас ёсць доступ, па сутнасці,
паніровачных сухароў, калі хочаце,

969
00:39:39,430 --> 00:39:41,500
для ўсіх неабходных паказальнікаў.

970
00:39:41,500 --> 00:39:43,710
>> Так што, калі я, паказваючы на
Эндзі і я таксама паказваючы

971
00:39:43,710 --> 00:39:47,105
на Крысціяна, чые рукі
павінны зараз адзначыць у іншым месцы?

972
00:39:47,105 --> 00:39:48,770

973
00:39:48,770 --> 00:39:51,960
Так Эндзі цяпер могуць паказаць на Джулію.

974
00:39:51,960 --> 00:39:54,460
Цяпер Юлія можа паказваць на хрысціяніна.

975
00:39:54,460 --> 00:39:56,950
Таму што яна можа скапіяваць мой
паказальнік правай рукі.

976
00:39:56,950 --> 00:40:00,044
І, што эфектыўна ставіць вас
назад у гэтым месцы тут.

977
00:40:00,044 --> 00:40:02,460
Такім чынам, у агульным, хоць гэта
вядзе нас накшталт назаўжды

978
00:40:02,460 --> 00:40:04,510
на самай справе абнаўлення
звязаны спіс, рэалізаваць

979
00:40:04,510 --> 00:40:06,580
што аперацыі
адносна простыя.

980
00:40:06,580 --> 00:40:10,030
Гэта з аднаго, двух, трох
радкоў кода, у канчатковым рахунку.

981
00:40:10,030 --> 00:40:12,780
Але абгорнутыя вакол тых,
радкоў кода меркавана

982
00:40:12,780 --> 00:40:16,350
трохі логікі, якія эфектыўна
задае пытанне, дзе мы знаходзімся?

983
00:40:16,350 --> 00:40:18,970
Няўжо мы ў самым пачатку,
сярэдні, ці канец?

984
00:40:18,970 --> 00:40:21,890
>> Зараз, ёсць, вядома, некаторыя іншыя
Аперацыі, якія мы маглі б рэалізаваць.

985
00:40:21,890 --> 00:40:24,880
І гэтыя фатаграфіі тут проста адлюстраваць
тое, што мы толькі што зрабілі з людзьмі.

986
00:40:24,880 --> 00:40:26,080
А як наконт выдалення?

987
00:40:26,080 --> 00:40:30,650
Калі я хачу, напрыклад,
выдаліць нумар 34 ці 55,

988
00:40:30,650 --> 00:40:34,680
Я мог бы мець такі ж код,
але я буду мець патрэбу ў адзін ці два этапы.

989
00:40:34,680 --> 00:40:36,110
Таму што новага?

990
00:40:36,110 --> 00:40:40,460
Калі я выдалю каго ў канцы,
як лікі 55, а затым 34,

991
00:40:40,460 --> 00:40:42,995
што таксама павінна змяніцца, як мне гэта зрабіць?

992
00:40:42,995 --> 00:40:44,870
Я павінен не evict--
як цябе клічуць?

993
00:40:44,870 --> 00:40:45,380
>> АЎДЫТОРЫЯ: Джэк.

994
00:40:45,380 --> 00:40:46,255
>> David J. малая: Джэк.

995
00:40:46,255 --> 00:40:49,770
Я павінен не толькі evict-- бясплатна Джэк,
так літаральна назваць бясплатны Джэк, ці, па меншай меры,

996
00:40:49,770 --> 00:40:53,530
паказальнік там жа, але цяпер
што неабходна змяніць з Пятром?

997
00:40:53,530 --> 00:40:55,510
Яго рука лепш пачаць ўніз.

998
00:40:55,510 --> 00:40:59,300
Таму што, як толькі я тэлефанаваць бясплатна на
Джэк, калі яшчэ паказвае Пятра на Джэка

999
00:40:59,300 --> 00:41:02,530
і я таму трымаеце абыходзе
спіс і доступ гэты паказальнік,

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. малая: Я жудасна
на імёны, па-відаць.

1013
00:41:31,408 --> 00:41:34,011
Так Крысціна і Гейб,
чые рукі неабходна змяніць

1014
00:41:34,011 --> 00:41:36,510
калі мы спрабуем выдаліць Крысціну,
лік 5, ад карціны?

1015
00:41:36,510 --> 00:41:37,550

1016
00:41:37,550 --> 00:41:38,820
Такім чынам, давайце зробім Гейб.

1017
00:41:38,820 --> 00:41:40,950
Гейб збіраецца паказаць,
як мяркуецца, у доме нумар 9.

1018
00:41:40,950 --> 00:41:42,230

1019
00:41:42,230 --> 00:41:44,642
Але што наступны павінен адбыцца?

1020
00:41:44,642 --> 00:41:46,600
АЎДЫТОРЫЯ: Крысціна павінна
быць пустым [неразборліва].

1021
00:41:46,600 --> 00:41:50,244
David J. малая: Добра, мы павінны, верагодна,
make-- я пачуў "нулявы" дзе.

1022
00:41:50,244 --> 00:41:51,410
АЎДЫТОРЫЯ: Null і вызваліць яе.

1023
00:41:51,410 --> 00:41:51,855
David J. малая: Null што?

1024
00:41:51,855 --> 00:41:53,074
АЎДЫТОРЫЯ: Null і вызваліць яе.

1025
00:41:53,074 --> 00:41:54,490
David J. малая: 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
І такім чынам, мы лепш патэлефанаваць бясплатна зараз на
Крысцін, каб даць гэтую памяць таму.

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
>> [Апладысменты]

1046
00:42:45,320 --> 00:42:46,700
>> David J. малая: Добра.

1047
00:42:46,700 --> 00:42:51,110
Так пару аналітычная
пытанні потым, калі я мог.

1048
00:42:51,110 --> 00:42:59,670
Мы бачылі гэта абазначэнне раней,
Big 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
>> Адзін, і мы сказалі, гэта
перш, чым жа працуе

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 н, лінейны.

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. малая: зноў сказаць?

1065
00:43:40,920 --> 00:43:41,800
АЎДЫТОРЫЯ: Адвольны доступ.

1066
00:43:41,800 --> 00:43:43,049
David J. малая: Адвольны доступ.

1067
00:43:43,049 --> 00:43:46,330
І ў сваю чаргу гэта азначае, што мы можам не
больш выкарыстоўваць слабы нулі, інтуіцыю,

1068
00:43:46,330 --> 00:43:49,365
і відавочнасць выкарыстоўваючы двайковы
пошук і падзяляй і ўладар.

1069
00:43:49,365 --> 00:43:51,240
Таму што нават пры тым, што мы
людзі маглі, відавочна,

1070
00:43:51,240 --> 00:43:54,610
бачыць, што Эндзі або хрысціянін былі
прыкладна ў сярэдзіне спісу,

1071
00:43:54,610 --> 00:43:57,670
вядома толькі, што, як
кампутар шляхам зняцця верхняга пласта спіс

1072
00:43:57,670 --> 00:43:59,029
з самага пачатку.

1073
00:43:59,029 --> 00:44:00,570
Такім чынам, мы адмовіліся, што адвольны доступ.

1074
00:44:00,570 --> 00:44:04,380
>> Настолькі вялікі O п цяпер гэта верхняя
мяжа нашага часу пошуку.

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. малая: зноў сказаць?

1079
00:44:13,040 --> 00:44:13,420
АЎДЫТОРЫЯ: Адзін.

1080
00:44:13,420 --> 00:44:13,800
David J. малая: Адзін.

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. малая: зноў сказаць?

1094
00:44:36,420 --> 00:44:37,067
АЎДЫТОРЫЯ: н.

1095
00:44:37,067 --> 00:44:38,900
David J. малая: п
сапраўды верхняя мяжа.

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
Прымае ад нас назаўсёды, ці
п крокаў, каб знайсці яго.

1099
00:44:45,419 --> 00:44:46,460
Дык вось верхняя мяжа.

1100
00:44:46,460 --> 00:44:47,430
Гэта лінейная, упэўнены.

1101
00:44:47,430 --> 00:44:50,970
І ў лепшым выпадку час працы, або
ніжнія мяжы ў лепшым выпадку

1102
00:44:50,970 --> 00:44:51,975
будзе сталая часу.

1103
00:44:51,975 --> 00:44:54,600
Таму што, можа быць, мы спрабуем выдаліць
Крысцін, і мы проста павезці

1104
00:44:54,600 --> 00:44:55,558
яна ў пачатку.

1105
00:44:55,558 --> 00:44:56,350
Цяпер пачакайце хвіліну.

1106
00:44:56,350 --> 00:44:59,370
Гейб таксама ў пачатку,
і мы таксама павінны былі абнавіць Гейб.

1107
00:44:59,370 --> 00:45:01,150
Так што не было яшчэ адзін этап.

1108
00:45:01,150 --> 00:45:04,210
Так гэта сапраўды пастаяннай
Час, у лепшым выпадку,

1109
00:45:04,210 --> 00:45:06,345
выдаліць найменшы элемент?

1110
00:45:06,345 --> 00:45:07,360

1111
00:45:07,360 --> 00:45:10,960
Гэта, нягледзячы на ​​тое, што можа быць два,
тры ці нават 100 радкоў кода,

1112
00:45:10,960 --> 00:45:14,000
калі гэта тое ж самае колькасць
лініі, не ў некаторай завесы,

1113
00:45:14,000 --> 00:45:16,577
і не залежыць ад памеру
са спісу, абсалютна.

1114
00:45:16,577 --> 00:45:18,660
Выдаленне элемента ў
пачатак спісу,

1115
00:45:18,660 --> 00:45:21,940
нават калі мы маем справу з
Гейб, яшчэ пастаянная часу.

1116
00:45:21,940 --> 00:45:24,220
>> Так гэта здаецца
масіўны крок назад.

1117
00:45:24,220 --> 00:45:27,000
І тое, што гэта пустая трата часу
калі, у тыдзень адзін і тыдня

1118
00:45:27,000 --> 00:45:30,250
нуля, мы павінны былі не толькі
Код псевдокод але фактычны код

1119
00:45:30,250 --> 00:45:35,780
рэалізаваць тое, што гэта часопіс
база н, або ўвайдзіце, хутчэй, з п, база 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. малая: Такім чынам, вы можаце
дадаваць элементы ў масіў.

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. малая: Так, мы
таксама ёсць паказальнік.

1143
00:46:23,310 --> 00:46:25,560
Так што гэта minorly раздражняе
у тым, што больш не з'яўляюся

1144
00:46:25,560 --> 00:46:27,780
Я захоўвання проста Int
для прадстаўлення Int.

1145
00:46:27,780 --> 00:46:30,990
Я запамінання Int і а
паказальнік, які таксама 32 біт.

1146
00:46:30,990 --> 00:46:33,470
Так што я літаральна падвойваючы
ўдзел аб'ём прасторы.

1147
00:46:33,470 --> 00:46:36,040
Дык вось кампраміс, але
вось у выпадку міжнар.

1148
00:46:36,040 --> 00:46:39,580
Выкажам здагадку, што вы не захоўвання Int,
але выкажам здагадку, што кожны з гэтых прастакутнікаў

1149
00:46:39,580 --> 00:46:43,290
або кожны з гэтых людзей прадстаўляў
слова, ангельскае слова, якое

1150
00:46:43,290 --> 00:46:46,430
можа ўтрымліваць пяць знакаў, 10
сімвалы, можа быць, нават больш.

1151
00:46:46,430 --> 00:46:49,940
Тады дадаўшы ўсяго 32 больш бітаў
можа быць менш буйной здзелкі.

1152
00:46:49,940 --> 00:46:52,160
>> Што рабіць, калі кожны са студэнтаў
у дэманстрацыі

1153
00:46:52,160 --> 00:46:55,107
былі літаральна студэнцкія Структуры, якія
маюць імёны і дамоў і, магчыма,

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
Пошук сталая.

1167
00:47:26,920 --> 00:47:28,320
Выдаліць сталая.

1168
00:47:28,320 --> 00:47:29,570
Устаўка сталая.

1169
00:47:29,570 --> 00:47:32,260
Усе гэтыя аперацыі з'яўляюцца сталымі.

1170
00:47:32,260 --> 00:47:33,750
Гэта было б нашым Святога Грааля.

1171
00:47:33,750 --> 00:47:36,690
І што гэта, дзе мы
падбяруць наступны раз.

1172
00:47:36,690 --> 00:47:38,600
Ўбачымся.

1173
00:47:38,600 --> 00:47:39,371