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

2
00:00:11,860 --> 00:00:13,120
>> Выступоўца 1: Усё ў парадку, так што мы вярнуліся.

3
00:00:13,120 --> 00:00:14,480
Сардэчна запрашаем у CS50.

4
00:00:14,480 --> 00:00:16,510
Гэта канец тыдня сем.

5
00:00:16,510 --> 00:00:20,200
Таму нагадаем, што ў мінулы раз, мы пачалі
гледзячы на ​​некалькі больш складана

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

7
00:00:21,100 --> 00:00:25,110
Так як да гэтага часу, усё, што мы былі сапраўды
У нашым распараджэнні было гэтага, масіў.

8
00:00:25,110 --> 00:00:29,340
>> Але перш чым адкінуць масіў як ня
усё, што цікава, што гэта сапраўды так

9
00:00:29,340 --> 00:00:33,570
на самай справе, тое, што некаторыя з
Плюсы гэтага простага дадзеных

10
00:00:33,570 --> 00:00:34,560
структуры да гэтага часу?

11
00:00:34,560 --> 00:00:36,110
Якое гэта добра?

12
00:00:36,110 --> 00:00:39,450
Да гэтага часу, як мы бачылі?

13
00:00:39,450 --> 00:00:42,540
Што ў цябе?

14
00:00:42,540 --> 00:00:44,028
Нічога.

15
00:00:44,028 --> 00:00:45,020
>> Студэнт: [неразборліва].

16
00:00:45,020 --> 00:00:45,395
>> Выступоўца 1: Што гэта?

17
00:00:45,395 --> 00:00:46,410
>> Студэнт: [неразборліва].

18
00:00:46,410 --> 00:00:47,000
>> Выступоўца 1: фіксаваны памер.

19
00:00:47,000 --> 00:00:51,260
Такім чынам, чаму фіксаваны памер добры, хоць?

20
00:00:51,260 --> 00:00:53,180
>> Студэнт: [неразборліва].

21
00:00:53,180 --> 00:00:56,240
>> Выступоўца 1: Добра, так што гэта эфектыўна ў
тое сэнсе, што вы можаце вылучыць

22
00:00:56,240 --> 00:01:00,070
Фіксаваная сума ў прасторы, якая, мы спадзяемся,
Менавіта столькі

23
00:01:00,070 --> 00:01:01,180
прасторы, як вы хочаце.

24
00:01:01,180 --> 00:01:02,720
Так што можа быць абсалютна плюс.

25
00:01:02,720 --> 00:01:06,530
>> Што яшчэ па адным баку масіва?

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

27
00:01:07,610 --> 00:01:08,750
>> Студэнт: [неразборліва].

28
00:01:08,750 --> 00:01:09,550
>> Выступоўца 1: Усё - Прабачце?

29
00:01:09,550 --> 00:01:11,270
>> Студэнт: [неразборліва].

30
00:01:11,270 --> 00:01:13,620
>> Выступоўца 1: Усе скрынкі ў памяці
або побач адзін з адным.

31
00:01:13,620 --> 00:01:15,220
І гэта карысна - чаму?

32
00:01:15,220 --> 00:01:15,970
Цалкам дакладна.

33
00:01:15,970 --> 00:01:18,611
Але як мы можам выкарыстоўваць гэта праўда?

34
00:01:18,611 --> 00:01:21,500
>> Студэнт: [неразборліва].

35
00:01:21,500 --> 00:01:24,490
>> Выступоўца 1: Сапраўды, мы можам адсочваць
, Дзе ўсё проста, ведаючы,

36
00:01:24,490 --> 00:01:28,560
адзін адрас, а менавіта, адрасы
Першы байт, што блок памяці.

37
00:01:28,560 --> 00:01:30,420
Ці ў выпадку радкі,
адрас першага

38
00:01:30,420 --> 00:01:31,460
знак у гэтай радку.

39
00:01:31,460 --> 00:01:33,330
А адтуль, мы можам знайсці
канца радка.

40
00:01:33,330 --> 00:01:35,710
Мы можам знайсці другі элемент,
трэці элемент, і так далей.

41
00:01:35,710 --> 00:01:38,740
>> І такім мудрагелістым спосабам апісання, што
асаблівасць у тым, што масівы даюць нам

42
00:01:38,740 --> 00:01:40,020
адвольным доступам.

43
00:01:40,020 --> 00:01:44,330
Проста з дапамогай квадратных дужак
абазначэння і нумары, вы можаце перайсці да

44
00:01:44,330 --> 00:01:48,070
канкрэтнага элемента ў масіве
за пастаянны час, Big O

45
00:01:48,070 --> 00:01:49,810
аднаго, так бы мовіць.

46
00:01:49,810 --> 00:01:51,080
>> Але ёсць некаторыя мінусы.

47
00:01:51,080 --> 00:01:53,110
Што масіў не рабіць вельмі лёгка?

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

49
00:01:55,810 --> 00:01:57,170
Што гэта не вельмі добра?

50
00:01:57,170 --> 00:01:58,810
>> Студэнт: [неразборліва].

51
00:01:58,810 --> 00:01:59,860
>> Выступоўца 1: Што гэта?

52
00:01:59,860 --> 00:02:00,530
>> Студэнт: [неразборліва].

53
00:02:00,530 --> 00:02:01,460
>> Выступоўца 1: Пашырэнне ў памерах.

54
00:02:01,460 --> 00:02:04,800
Такім чынам, недахопы масіва
дакладна адваротнае таму, што

55
00:02:04,800 --> 00:02:05,540
расквітацца ёсць.

56
00:02:05,540 --> 00:02:07,610
Таму адным з недахопаў з'яўляецца
што гэта фіксаваны памер.

57
00:02:07,610 --> 00:02:09,400
Такім чынам, вы не можаце рэальна выгадаваць яго.

58
00:02:09,400 --> 00:02:13,510
Вы можаце пераразмеркаваць большы кавалак
памяці, а затым перамесціце стары элементы

59
00:02:13,510 --> 00:02:14,460
у новы масіў.

60
00:02:14,460 --> 00:02:18,060
, А затым вызваліць старога масіва, для
Напрыклад, пры выкарыстанні Таноса або аналагічнага

61
00:02:18,060 --> 00:02:21,180
Функцыя называецца Realloc, якая
пераразмяркоўвае памяць.

62
00:02:21,180 --> 00:02:25,490
>> Realloc, як у бок, спрабуе даць вам
памяці, што гэта побач з масівам

63
00:02:25,490 --> 00:02:26,610
што вы ўжо маеце.

64
00:02:26,610 --> 00:02:28,740
Але гэта можа перамяшчаць прадметы
вакол у цэлым.

65
00:02:28,740 --> 00:02:30,710
Але ў агульным, што дорага, ці не так?

66
00:02:30,710 --> 00:02:33,440
Таму што, калі ў вас ёсць кавалак памяці
такога памеру, але вы сапраўды хочаце адзін

67
00:02:33,440 --> 00:02:36,710
такога памеру, і вы хочаце захаваць
арыгінальныя элементы, у вас ёсць

68
00:02:36,710 --> 00:02:40,510
прыкладна лінейны працэс капіявання час
што павінна адбыцца ад

69
00:02:40,510 --> 00:02:41,900
старога масіва на новы.

70
00:02:41,900 --> 00:02:44,630
А рэальнасць такая просяць аперацыйнай
Сістэма зноў і зноў і

71
00:02:44,630 --> 00:02:48,340
зноў на вялікія кавалкі памяці можа пачацца
каштаваць вам некаторы час, а таксама.

72
00:02:48,340 --> 00:02:52,250
Так што гэта як дабраславеньне і праклён у
замаскіраваць той факт, што гэтыя масівы

73
00:02:52,250 --> 00:02:53,860
маюць фіксаваны памер.

74
00:02:53,860 --> 00:02:56,790
Але калі ўвесці замест нешта
як гэта, якое мы назвалі звязанага

75
00:02:56,790 --> 00:03:00,580
спіс, мы атрымліваем некалькі плюсы і
некалькі недахопаў і тут.

76
00:03:00,580 --> 00:03:05,780
>> Так звязаны спіс проста дадзеныя
структура, якая складаецца з структур C у гэтым

77
00:03:05,780 --> 00:03:09,850
выпадку, калі структура, нагадаем, з'яўляецца проста
кантэйнер для аднаго або больш канкрэтных

78
00:03:09,850 --> 00:03:11,100
тыпы зменных.

79
00:03:11,100 --> 00:03:16,110
У гэтым выпадку, што ж тыпы дадзеных
Відаць, усярэдзіне структуры, які

80
00:03:16,110 --> 00:03:17,600
Апошні раз мы называецца вузлом?

81
00:03:17,600 --> 00:03:19,380
Кожны з гэтых прастакутнікаў вузла.

82
00:03:19,380 --> 00:03:22,660
І кожны з меншых прастакутнікаў
Унутры гэта тып дадзеных.

83
00:03:22,660 --> 00:03:25,300
Якія ж тады мы казалі
яны былі ў панядзелак?

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

85
00:03:26,478 --> 00:03:27,870
>> Студэнт: [неразборліва].

86
00:03:27,870 --> 00:03:30,721
>> Выступоўца 1: зменныя і паказальнік, або
дакладней, цэлае для N,

87
00:03:30,721 --> 00:03:32,180
і паказальнік на дне.

88
00:03:32,180 --> 00:03:35,360
Абодва гэтыя, аказваецца, 32 біта, па крайняй
меры на кампутары, як гэта CS50

89
00:03:35,360 --> 00:03:37,980
Appliance, і таму яны
звяртаецца аднолькава ў памеры.

90
00:03:37,980 --> 00:03:42,260
>> Так што з дапамогай паказальніка
хоць для па-відаць?

91
00:03:42,260 --> 00:03:47,690
Навошта дадаваць гэтую стрэлку цяпер, калі масівы, былі
так добра і чыста і проста?

92
00:03:47,690 --> 00:03:50,460
Што робіце для паказальніка
намі у кожным з гэтых вузлоў?

93
00:03:50,460 --> 00:03:52,160
>> Студэнт: [неразборліва].

94
00:03:52,160 --> 00:03:52,465
>> Выступоўца 1: Цалкам дакладна.

95
00:03:52,465 --> 00:03:54,120
Гэта кажа вам, дзе
далей ідзе.

96
00:03:54,120 --> 00:03:57,350
Так што я, вядома, выкарыстоўваць аналогію
выкарыстаннем патоку да выгляду

97
00:03:57,350 --> 00:03:59,180
нітка гэтыя вузлы разам.

98
00:03:59,180 --> 00:04:01,760
І гэта менавіта тое, што мы робім з
паказальнікаў, паколькі кожны з гэтых

99
00:04:01,760 --> 00:04:06,360
участкаў памяці можа ці не можа быць
сумежныя, спіна да спіны да спіны

100
00:04:06,360 --> 00:04:09,500
ўнутры аператыўнай памяці, таму што кожны раз, калі вы
патэлефануеце Malloc кажуць: дай мне дастаткова

101
00:04:09,500 --> 00:04:12,510
байтаў для новага вузла, ён можа
быць тут, ці ён можа быць тут.

102
00:04:12,510 --> 00:04:13,120
Гэта магло б быць тут.

103
00:04:13,120 --> 00:04:13,730
Гэта магло б быць тут.

104
00:04:13,730 --> 00:04:14,640
Вы проста не ведаю.

105
00:04:14,640 --> 00:04:17,880
>> Але з дапамогай паказальнікаў у адрасах
гэтыя вузлы, вы можаце пашыць іх

106
00:04:17,880 --> 00:04:22,370
разам такім чынам, што візуальна выглядае
як спіс, нават калі гэтыя рэчы

107
00:04:22,370 --> 00:04:26,770
ўсе распаўсюджаныя на працягу ўсяго аднаго або
Вашы два ці вашы чатыры гігабайта аператыўнай памяці

108
00:04:26,770 --> 00:04:28,760
ўнутры вашага ўласнага кампутара.

109
00:04:28,760 --> 00:04:33,230
>> Такім чынам, недахоп, то,
Звязаны спіс ёсць што?

110
00:04:33,230 --> 00:04:34,670
Што такое цана, што мы
мабыць плаціць?

111
00:04:34,670 --> 00:04:36,010
>> Студэнт: [неразборліва].

112
00:04:36,010 --> 00:04:36,920
>> Выступоўца 1: Больш месца, ці не так?

113
00:04:36,920 --> 00:04:39,340
Мы, у дадзеным выпадку, падвоіў суму
прасторы, таму што мы прайшлі

114
00:04:39,340 --> 00:04:43,500
з 32 біт для кожнага вузла, для кожнага
Інтэлект, так што зараз 64 біта, таму што мы павінны

115
00:04:43,500 --> 00:04:45,050
трымаць вакол паказальніка, а таксама.

116
00:04:45,050 --> 00:04:48,860
Вы атрымліваеце больш эфектыўнасці, калі вашай структуры
больш, чым гэтая простая рэч.

117
00:04:48,860 --> 00:04:52,020
Калі ў вас сапраўды ёсць унутры студэнта
з якіх уяўляе сабой пару радкоў для

118
00:04:52,020 --> 00:04:55,430
імя і дом, можа быць, нумар пасведчання асобы,
магчыма, некаторыя іншыя вобласці ў цэлым.

119
00:04:55,430 --> 00:04:59,000
>> Так што калі ў вас ёсць дастаткова вялікая структура,
то, магчыма, кошт паказальнік

120
00:04:59,000 --> 00:05:00,010
Не такое ўжо вялікая справа.

121
00:05:00,010 --> 00:05:03,570
Гэта крыху з кута ў гэтым выпадку
мы захоўваем такія простыя прымітыўныя

122
00:05:03,570 --> 00:05:04,760
ўнутр звязанага спісу.

123
00:05:04,760 --> 00:05:05,790
Але сутнасць тая ж.

124
00:05:05,790 --> 00:05:08,230
Вы вызначана марнаваць больш
памяці, але вы атрымліваеце

125
00:05:08,230 --> 00:05:08,990
гнуткасць.

126
00:05:08,990 --> 00:05:12,280
Таму што цяпер, калі я хачу дадаць элемент
У пачатку гэтага спісу,

127
00:05:12,280 --> 00:05:14,340
Я павінен вылучыць новы вузел.

128
00:05:14,340 --> 00:05:17,180
І я павінен проста абнавіць гэтыя
Стрэлкі-то проста перасоўванне

129
00:05:17,180 --> 00:05:17,980
некаторыя паказальнікі вакол.

130
00:05:17,980 --> 00:05:20,580
>> Калі я хачу, каб ўставіць нешта ў
сярэдзіне спісу, я не прыйдзецца

131
00:05:20,580 --> 00:05:24,410
штурхаць у бок усё, што мы зрабілі ў
тыдняў мінулае з нашым добраахвотнікам, якія

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

133
00:05:25,700 --> 00:05:29,470
Я магу проста вылучыць новы вузел і
Затым проста паказаць стрэлкамі на

134
00:05:29,470 --> 00:05:32,290
розных напрамках, паколькі яна не
павінны заставацца ў фактычным

135
00:05:32,290 --> 00:05:35,670
памяці сапраўдных лініі, як я намаляваў
яе тут на экране.

136
00:05:35,670 --> 00:05:38,400
>> А потым, нарэшце, калі вы хочаце ўставіць
то ў канцы спісу, гэта

137
00:05:38,400 --> 00:05:39,210
яшчэ прасцей.

138
00:05:39,210 --> 00:05:43,320
Гэта свайго роду адвольныя абазначэння,
але ў 34 паказальнікаў, зрабіць здагадку.

139
00:05:43,320 --> 00:05:46,710
Што такое значэнне яго паказальніка найбольш
верагодна, звяртаецца накшталт як старыя

140
00:05:46,710 --> 00:05:47,700
школе ёсць антэна?

141
00:05:47,700 --> 00:05:48,920
>> Студэнт: [неразборліва].

142
00:05:48,920 --> 00:05:49,900
>> Выступоўца 1: Гэта, верагодна, нулявым.

143
00:05:49,900 --> 00:05:52,710
І на самай справе, што з'яўляецца адным аўтара
ўяўленне нулявы.

144
00:05:52,710 --> 00:05:56,310
І гэта нуль, таму што вы абсалютна
трэба ведаць, дзе да канца звязанага

145
00:05:56,310 --> 00:06:00,050
спіс, каб вы працягваеце пасля і
пасля і пасля гэтых стрэлак

146
00:06:00,050 --> 00:06:01,170
некаторым смеццем значэння.

147
00:06:01,170 --> 00:06:06,230
Так нулявых не будзе азначаць, што няма ніякай
больш вузлоў справа ад колькасці 34,

148
00:06:06,230 --> 00:06:07,200
ў гэтым выпадку.

149
00:06:07,200 --> 00:06:10,270
>> Таму мы лічым, што мы можам рэалізаваць
гэты вузел у кодзе.

150
00:06:10,270 --> 00:06:12,130
І мы бачылі такую
сінтаксісу раней.

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

152
00:06:15,090 --> 00:06:17,100
Радок была для сімвал *.

153
00:06:17,100 --> 00:06:21,030
У гэтым выпадку, ён збіраецца даць нам
скарочаны запіс, так што структура вузла

154
00:06:21,030 --> 00:06:24,010
Замест гэтага можна проста быць запісана ў выглядзе
вузел, які з'яўляецца нашмат больш чыстай.

155
00:06:24,010 --> 00:06:25,360
Гэта значна менш шматслоўным.

156
00:06:25,360 --> 00:06:30,080
>> Усярэдзіне вузла відаць цэлалікавай
называецца п, а затым структуры вузла *

157
00:06:30,080 --> 00:06:34,670
што азначае менавіта тое, што мы хацелі
Стрэлкі на ўвазе, паказальнік на іншы

158
00:06:34,670 --> 00:06:36,940
вузел сапраўды такі жа тып дадзеных.

159
00:06:36,940 --> 00:06:40,300
І я прапаную, каб мы маглі рэалізаваць
Функцыя пошуку, як гэта, якое ў

160
00:06:40,300 --> 00:06:41,890
першы погляд можа здацца,
трохі складаным.

161
00:06:41,890 --> 00:06:43,330
Але давайце паглядзім яго ў кантэксце.

162
00:06:43,330 --> 00:06:45,480
>> Дазвольце мне перайсці да прыбора тут.

163
00:06:45,480 --> 00:06:48,460
Дазвольце мне адкрыць файл з імем
Спіс нуля кропка ч.

164
00:06:48,460 --> 00:06:53,950
І што толькі змяшчае вызначэнне мы
толькі што бачылі хвіліну назад для гэтых дадзеных

165
00:06:53,950 --> 00:06:55,390
тып завецца вузлом.

166
00:06:55,390 --> 00:06:57,350
Таму мы ўвялі, што ў файл кропка ч.

167
00:06:57,350 --> 00:07:01,430
>> І, як у баку, хоць гэта
праграма, якую вы збіраецеся, каб убачыць гэта

168
00:07:01,430 --> 00:07:05,410
не ўсё, што комплекс, гэта сапраўды
Канвенцыі пры напісанні праграмы

169
00:07:05,410 --> 00:07:10,270
пакласці рэчы, як тыпы дадзеных, цягнуць
Канстанты часам, ўнутры вашага

170
00:07:10,270 --> 00:07:13,210
загаловак файла, а не абавязкова ў
З вашага файла, вядома ж, калі ваш

171
00:07:13,210 --> 00:07:17,370
праграм атрымаць больш і больш, так што
Вы ведаеце, дзе шукаць, як для

172
00:07:17,370 --> 00:07:20,840
дакументацыі ў некаторых выпадках ці
для асновы, як гэта,

173
00:07:20,840 --> 00:07:22,360
вызначэнне некаторага тыпу.

174
00:07:22,360 --> 00:07:25,680
>> Калі б я цяпер адкрыць спіс нуля кропка
C, заўважыць некалькі рэчаў.

175
00:07:25,680 --> 00:07:29,090
Яна ўключае ў сябе некалькі файлаў загалоўка, большасць
якога мы бачылі раней.

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

177
00:07:31,980 --> 00:07:35,200
>> І, як у баку, чаму гэта падвойная
каціроўкі тут, у адрозненне ад кута

178
00:07:35,200 --> 00:07:38,340
кранштэйны на лініі, якая
Я выдзеліў там?

179
00:07:38,340 --> 00:07:39,180
>> Студэнт: [неразборліва].

180
00:07:39,180 --> 00:07:40,460
>> Выступоўца 1: Так, так што гэта лакальны файл.

181
00:07:40,460 --> 00:07:44,300
Так што, калі гэта лакальны файл ўласнай тут
на лініі 15, напрыклад, вы карыстаецеся

182
00:07:44,300 --> 00:07:46,570
падвойныя двукоссі замест
ў вуглавыя дужкі.

183
00:07:46,570 --> 00:07:48,270
>> Зараз гэта збольшага цікава.

184
00:07:48,270 --> 00:07:51,830
Звярніце ўвагу, што я абвясціў глабальную
зменнай у гэтай праграме ў радку 18

185
00:07:51,830 --> 00:07:55,910
называецца першай, ідэя ў тым, што гэта
будзе паказальнік на першы

186
00:07:55,910 --> 00:07:59,190
вузел у маім звязаны спіс, а я
ініцыялізаваць яго да нуля, таму, што я

187
00:07:59,190 --> 00:08:02,310
не вылучаецца якіх-небудзь фактычных
вузлы толькі пакуль.

188
00:08:02,310 --> 00:08:07,570
>> Так што гэта ўяўляе, графічна, тое, што мы
ўбачыў хвіліну таму на малюнку як

189
00:08:07,570 --> 00:08:10,090
што паказальнік на Далёкім
з левага боку.

190
00:08:10,090 --> 00:08:12,260
Так што цяпер, што паказальнік
не мае стрэлкі.

191
00:08:12,260 --> 00:08:14,590
Замест гэтага ён проста нулявы.

192
00:08:14,590 --> 00:08:17,880
Але ён ўяўляе, які будзе
адрас першага фактычнага

193
00:08:17,880 --> 00:08:19,480
вузла ў гэтым спісе.

194
00:08:19,480 --> 00:08:22,120
Так я рэалізаваў гэта глабальная
таму што, як вы ўбачыце, усё гэта

195
00:08:22,120 --> 00:08:25,310
Праграма робіць у жыцці, гэта рэалізаваць
звязаны спіс для мяне.

196
00:08:25,310 --> 00:08:27,050
>> Цяпер у мяне ёсць некалькі прататыпаў тут.

197
00:08:27,050 --> 00:08:31,190
Я вырашыў рэалізаваць функцыі, такія як
дзялок, устаўкі, пошуку і

198
00:08:31,190 --> 00:08:31,740
абыходу -

199
00:08:31,740 --> 00:08:35,210
Апошні проста быць шпацыр праз
Спіс, раздрукаваць яе элементаў.

200
00:08:35,210 --> 00:08:36,750
А цяпер вось мой асноўнай праграме.

201
00:08:36,750 --> 00:08:39,890
І мы не будзем марнаваць занадта шмат часу на
гэта, так як гэта з'яўляецца свайго роду, мы спадзяемся,

202
00:08:39,890 --> 00:08:41,780
старая капялюш да гэтага часу.

203
00:08:41,780 --> 00:08:45,370
>> Я збіраюся зрабіць наступнае,
у той час як карыстальнік ўзаемадзейнічае.

204
00:08:45,370 --> 00:08:47,300
Так што, я збіраюся друкаваць
з гэтага меню.

205
00:08:47,300 --> 00:08:49,420
І я адфарматаваць яго ў якасці
чыста, як я мог.

206
00:08:49,420 --> 00:08:52,240
Калі карыстальнік ўводзіць у адным, гэта значыць
яны хочуць, каб выдаліць што-небудзь.

207
00:08:52,240 --> 00:08:54,560
Калі карыстальнік ўвядзе ў двух, гэта азначае, што
яны хочуць, каб ўставіць нешта.

208
00:08:54,560 --> 00:08:55,930
І гэтак далей.

209
00:08:55,930 --> 00:08:58,270
Я збіраюся потым падкажуць
Тады для каманды.

210
00:08:58,270 --> 00:08:59,300
А потым я збіраюся выкарыстоўваць GetInt.

211
00:08:59,300 --> 00:09:02,790
>> Так што гэта сапраўды проста menuing
інтэрфейс, дзе вы проста павінны ўвесці

212
00:09:02,790 --> 00:09:05,270
лік адлюстраванне аднаго
з гэтых каманд.

213
00:09:05,270 --> 00:09:08,730
І зараз у мяне ёсць добрая чыстая перамыкач
заяву, што збіраецца ўключыць

214
00:09:08,730 --> 00:09:10,090
любы карыстальнік ўвялі цалі

215
00:09:10,090 --> 00:09:12,180
І калі яны набралі адно, я буду
выкліку выдалення і ламацца.

216
00:09:12,180 --> 00:09:14,380
Калі яны ўвялі два, я буду
патэлефануеце ўставіць і ламацца.

217
00:09:14,380 --> 00:09:16,490
>> А цяпер звярніце ўвагу я змясціў кожнага
з іх на той жа лініі.

218
00:09:16,490 --> 00:09:18,360
Гэта ўсяго толькі стылістычнае рашэнне.

219
00:09:18,360 --> 00:09:20,210
Звычайна мы бачылі нешта
як гэта.

220
00:09:20,210 --> 00:09:23,260
Але я проста вырашыў, шчыра кажучы, мая праграма
выглядаў больш для чытання, так

221
00:09:23,260 --> 00:09:25,980
гэта было толькі чатыры выпадкі
проста пералічыць гэта так.

222
00:09:25,980 --> 00:09:28,360
Цалкам законнае выкарыстанне стылю.

223
00:09:28,360 --> 00:09:31,480
І я буду рабіць гэта так доўга, як
Карыстальнік не набрала нуля, што я

224
00:09:31,480 --> 00:09:33,910
вырашана будзе азначаць, што яны жадаюць кінуць паліць.

225
00:09:33,910 --> 00:09:36,630
>> Так што цяпер заўважаю, што я
будзем рабіць тут.

226
00:09:36,630 --> 00:09:38,650
Я збіраюся вызваліць спісе па-відаць.

227
00:09:38,650 --> 00:09:40,230
Але пра гэта праз хвіліну.

228
00:09:40,230 --> 00:09:41,640
Давайце спачатку запусціць гэтую праграму.

229
00:09:41,640 --> 00:09:45,250
Такім чынам, дазвольце мне зрабіць большы тэрмінал
вокны, кропка слэш спіс 0.

230
00:09:45,250 --> 00:09:49,510
Я збіраюся ісці наперад і ўстаўляйце іх
набраўшы два, як лік 50, а цяпер

231
00:09:49,510 --> 00:09:51,590
Вы ўбачыце спіс зараз на 50.

232
00:09:51,590 --> 00:09:53,380
І мой тэкст, проста пракручваецца няшмат.

233
00:09:53,380 --> 00:09:55,940
Так што цяпер Звярніце ўвагу на спіс ўтрымлівае
лік 50.

234
00:09:55,940 --> 00:09:58,220
>> Давайце яшчэ устаўкай, узяўшы два.

235
00:09:58,220 --> 00:10:01,630
Давайце увядзіце нумар, як адзін.

236
00:10:01,630 --> 00:10:03,940
Спіс з'яўляецца адной, а затым 50.

237
00:10:03,940 --> 00:10:06,020
Так што гэта проста тэкставае ўяўленне
спісу.

238
00:10:06,020 --> 00:10:10,550
І давайце уставім яшчэ адзін нумар, як
нумар 42, які з надзеяй

239
00:10:10,550 --> 00:10:14,620
будзе ў канчатковым выніку ў сярэдзіне, таму што
гэтай праграмы, у прыватнасці, сартуе яго

240
00:10:14,620 --> 00:10:16,320
элементы, як ён устаўляе іх.

241
00:10:16,320 --> 00:10:17,220
Так што ў нас гэта ёсць.

242
00:10:17,220 --> 00:10:20,730
Супер просто праграму, якая можа
Абсалютна выкарыстоўвалі мноства, але я

243
00:10:20,730 --> 00:10:23,280
, Здараецца, выкарыстоўваюць звязаны спіс
менавіта так я магу дынамічна

244
00:10:23,280 --> 00:10:24,610
павялічваюцца і памяншаюцца яго.

245
00:10:24,610 --> 00:10:28,470
>> Такім чынам, давайце зірнем на пошукі, калі я
запусціць каманду тры, я хачу пошуку

246
00:10:28,470 --> 00:10:31,040
, Скажам, лікі 43.

247
00:10:31,040 --> 00:10:34,190
І нічога не было знойдзена па-відаць,
таму што я не вярнуўся без адказу.

248
00:10:34,190 --> 00:10:35,010
Такім чынам, давайце зробім гэта зноў.

249
00:10:35,010 --> 00:10:35,690
Пошук.

250
00:10:35,690 --> 00:10:39,520
Давайце шукаць для 50, ці, хутчэй, пошук
для 42, у якога ёсць добрая

251
00:10:39,520 --> 00:10:40,850
амаль няўлоўная сэнс.

252
00:10:40,850 --> 00:10:42,610
І я знайшоў сэнс жыцця там.

253
00:10:42,610 --> 00:10:44,990
Лік 42, калі вы не ведаеце,
спасылкі Пошук у Інтэрнэце.

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

255
00:10:45,350 --> 00:10:47,130
Так, што гэтая праграма для мяне зрабіў?

256
00:10:47,130 --> 00:10:50,660
Гэта проста дазволіў мне ўставіць такім чынам,
далёка і пошук элементаў.

257
00:10:50,660 --> 00:10:53,650
>> Давай наперад, то, каб
функцыі, мы зірнуў на

258
00:10:53,650 --> 00:10:55,360
у панядзелак, як цвялілкі.

259
00:10:55,360 --> 00:10:59,620
Так што гэтая функцыя, я сцвярджаю, шукае
элемента ў спісе па першым

260
00:10:59,620 --> 00:11:03,830
адна, прапаноўваючы карыстачу з наступным выклікам
GetInt, каб атрымаць фактычныя дзесятковага

261
00:11:03,830 --> 00:11:05,060
што вы хочаце знайсці.

262
00:11:05,060 --> 00:11:06,460
>> Потым заўважыў гэтага.

263
00:11:06,460 --> 00:11:10,690
Я збіраюся стварыць часовую зменную
У лініі 188 называецца паказальнікам -

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

265
00:11:11,270 --> 00:11:12,440
мог бы назваць яе, як заўгодна.

266
00:11:12,440 --> 00:11:16,140
І гэта паказальнік на вузле
бо Я сказаў вузла * там.

267
00:11:16,140 --> 00:11:19,900
І я ініцыялізацыі роўным
першы, так што я эфектыўна маё

268
00:11:19,900 --> 00:11:22,860
пальца, так бы мовіць, на самай
Першы элемент спісу.

269
00:11:22,860 --> 00:11:27,460
Так што, калі мая правая рука тут PTR Я
паказваючы на ​​тое ж самае, што першы

270
00:11:27,460 --> 00:11:28,670
паказвае на.

271
00:11:28,670 --> 00:11:31,430
>> Так што цяпер яшчэ ў кодзе,
што будзе далей -

272
00:11:31,430 --> 00:11:35,070
гэта агульная парадыгма пры пераборы
па структуры, як

273
00:11:35,070 --> 00:11:35,970
звязаны спіс.

274
00:11:35,970 --> 00:11:40,410
Я збіраюся зрабіць наступнае ў той час як
паказальнік ня роўны нулю Такім чынам, хоць

275
00:11:40,410 --> 00:11:47,530
мой палец не паказвае на некаторыя нулявым
кошту, калі стрэлка паказальніка N роўна N.

276
00:11:47,530 --> 00:11:52,290
Мы заўважылі, што першыя N з'яўляецца тое, што
карыстач уводзіць у GetInts называю тут.

277
00:11:52,290 --> 00:11:54,280
>> І стрэлка паказальніка N азначае, што?

278
00:11:54,280 --> 00:11:59,020
Ну, калі мы вернемся да карціны тут,
ці ёсць у мяне пальцам, паказваючы на

279
00:11:59,020 --> 00:12:02,960
што першы вузел, які змяшчае дзевяць,
стрэлкі па сутнасці азначае, што перайсці да

280
00:12:02,960 --> 00:12:08,860
вузла і захапіць значэнне ў кропцы N,
У гэтым выпадку, поле дадзеных называецца н.

281
00:12:08,860 --> 00:12:14,120
>> Як у бок - і мы ўбачылі гэтую пару
тыдняў таму, калі хто-то спытаў -

282
00:12:14,120 --> 00:12:18,840
гэты сінтаксіс з'яўляецца новай, але гэта не так
даць нам сілы, якія мы

283
00:12:18,840 --> 00:12:20,040
ўжо не было.

284
00:12:20,040 --> 00:12:25,325
Што гэта за фраза эквівалентна выкарыстанню
кропкавай натацыі і зорка пара

285
00:12:25,325 --> 00:12:29,490
тыдняў таму, калі мы вычышчаныя назад
гэты пласт трохі заўчасна?

286
00:12:29,490 --> 00:12:31,780
>> Студэнт: [неразборліва].

287
00:12:31,780 --> 00:12:38,880
>> Выступоўца 1: Сапраўды, гэта была зорка, і
тады гэта была зорка кропкай N, з

288
00:12:38,880 --> 00:12:41,930
Тут дужкі, які выглядае,
шчыра кажучы, я думаю, што шмат

289
00:12:41,930 --> 00:12:43,320
больш загадкавыя чытаць.

290
00:12:43,320 --> 00:12:46,270
Але паказальнік зоркі, як заўсёды,
сродкі ідуць туды.

291
00:12:46,270 --> 00:12:49,090
І як толькі вы там, якія дадзеныя
поля вы хочаце атрымаць доступ?

292
00:12:49,090 --> 00:12:52,730
Ну вы выкарыстоўваюць кропку доступу да
поля структур дадзеных, і я

293
00:12:52,730 --> 00:12:54,140
спецыяльна хочуць н.

294
00:12:54,140 --> 00:12:56,240
>> Шчыра кажучы, я б сказаў, гэта
проста цяжка чытаць.

295
00:12:56,240 --> 00:12:58,080
Гэта складаней ўспомніць, дзе
зрабіць дужках ісці,

296
00:12:58,080 --> 00:12:59,030
зорка і ўсё такое.

297
00:12:59,030 --> 00:13:02,150
Такім чынам, свет прыняў некаторыя сінтаксічныя
цукар, так бы мовіць.

298
00:13:02,150 --> 00:13:04,740
Проста сэксуальна спосаб сказаць,
гэта эквівалентна, а таксама

299
00:13:04,740 --> 00:13:05,970
магчыма, больш інтуітыўным.

300
00:13:05,970 --> 00:13:09,600
Калі паказальнік сапраўды з'яўляецца паказальнікам,
сродкаў стрэлкі абазначэння пайсці туды і знайсці

301
00:13:09,600 --> 00:13:11,890
поля ў гэтым выпадку называюцца N.

302
00:13:11,890 --> 00:13:13,660
>> Так што, калі я знаходжу гэта, заўважце, што я раблю.

303
00:13:13,660 --> 00:13:17,430
Я проста раздрукаваць, я выявіў, я адсоткаў,
падлучэнне значэнне для гэтага Int.

304
00:13:17,430 --> 00:13:20,730
Я называю спаць на працягу адной секунды проста выгляд
паўзы рэчы на ​​экране, каб

305
00:13:20,730 --> 00:13:22,900
даць карыстачу другі паглынаць
што толькі што адбылося.

306
00:13:22,900 --> 00:13:24,290
І тады я парушу.

307
00:13:24,290 --> 00:13:26,330
У адваротным выпадку, што мне рабіць?

308
00:13:26,330 --> 00:13:30,960
Абнавіць паказальнік на роўных
паказальніка стрэлкі побач.

309
00:13:30,960 --> 00:13:35,840
>> Так што проста каб быць ясным, гэта азначае пайсці
там, з дапамогай маёй старой школы мелі наймення.

310
00:13:35,840 --> 00:13:39,580
Так што гэта проста азначае, ісці да таго, што
Вы паказваеце на, які ў самым

311
00:13:39,580 --> 00:13:43,660
Першы выпадак я паказваючы на
Структура з дзевяццю ў ім.

312
00:13:43,660 --> 00:13:44,510
Так што я пайшоў туды.

313
00:13:44,510 --> 00:13:47,880
І тады кропкавай натацыі азначае,
атрымаць значэнне ў наступным.

314
00:13:47,880 --> 00:13:50,470
>> Але каштоўнасць, хоць ён малюецца
як вузкія, проста нумар.

315
00:13:50,470 --> 00:13:51,720
Гэта адрас у лікавы.

316
00:13:51,720 --> 00:13:55,670
Так што гэта адзін радок кода, няхай гэта будзе
напісана, як гэта, больш схаваным

317
00:13:55,670 --> 00:14:00,190
шляху, ці, як гэта, некалькі больш
інтуітыўна зразумелым спосабам, проста азначае, паварушыць рукой

318
00:14:00,190 --> 00:14:03,460
ад першага вузла да наступнага,
а затым наступны, а затым

319
00:14:03,460 --> 00:14:05,320
наступнай, і так далей.

320
00:14:05,320 --> 00:14:09,920
>> Такім чынам, мы не будзем спыняцца на іншых
рэалізацый ўстаўляць і выдаляць

321
00:14:09,920 --> 00:14:14,030
і абыходу, першыя два з
якія з'яўляюцца дастаткова складанай.

322
00:14:14,030 --> 00:14:17,010
І я думаю, што гэта даволі лёгка атрымаць
страціў, калі робяць гэта ў вуснай форме.

323
00:14:17,010 --> 00:14:19,890
Але што мы можам зрабіць тут
Паспрабуйце вызначыць, як

324
00:14:19,890 --> 00:14:21,640
Лепш рабіць гэта візуальна.

325
00:14:21,640 --> 00:14:24,800
Таму што я хацеў бы прапанаваць, што калі мы
хочаце ўставіць элементы ў гэтай

326
00:14:24,800 --> 00:14:26,680
існуючы спіс, які
складаецца з пяці элементаў -

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

328
00:14:29,530 --> 00:14:33,300
Калі б я збіраўся ажыццявіць гэта ў
код, мне трэба падумаць, як ісці

329
00:14:33,300 --> 00:14:34,160
пра гэта.

330
00:14:34,160 --> 00:14:37,720
>> І я хацеў бы прапанаваць крокі дзіцяці
якой, у дадзеным выпадку я маю на ўвазе, якія

331
00:14:37,720 --> 00:14:41,090
магчымых сцэнарыяў, якія мы
могуць паўстаць у цэлым?

332
00:14:41,090 --> 00:14:44,120
Пры рэалізацыі ўстаўкі для звязанага
спісе, гэта толькі, здараецца,

333
00:14:44,120 --> 00:14:46,090
Пэўным прыкладам памер пяць.

334
00:14:46,090 --> 00:14:50,420
Ну, калі вы хочаце ўставіць лічбу,
як, скажам, нумар адзін, і

335
00:14:50,420 --> 00:14:53,380
падтрыманне парадку сартавання, дзе
, Відавочна, нумар адзін трэба

336
00:14:53,380 --> 00:14:55,686
ісці ў гэтым канкрэтным прыкладзе?

337
00:14:55,686 --> 00:14:56,840
Напрыклад, у пачатку.

338
00:14:56,840 --> 00:15:00,030
>> Але што цікава, ёсць тое, што
Калі Вы хочаце ўставіць адну ў гэтую

339
00:15:00,030 --> 00:15:04,100
спіс, што трэба спецыяльны паказальнік
абнавіць відавочна?

340
00:15:04,100 --> 00:15:04,610
Першая.

341
00:15:04,610 --> 00:15:07,830
Так што я б сказаў, што гэта першы выпадак
што мы маглі б хацець разгледзець,

342
00:15:07,830 --> 00:15:11,140
сцэнар, які ўключае ўвядзенне, па
пачатку спісу.

343
00:15:11,140 --> 00:15:15,400
>> Давайце абрываць, можа быць, так лёгка, ці нават
просты выпадак, умоўна кажучы.

344
00:15:15,400 --> 00:15:18,110
Выкажам здагадку, я хачу, каб ўставіць
35 чысла ў парадку сартавання.

345
00:15:18,110 --> 00:15:20,600
Гэта, відавочна, належыць там.

346
00:15:20,600 --> 00:15:25,320
Так што, відавочна, паказальнік будзе
павінны быць абноўлены ў гэтым сцэнары?

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

348
00:15:30,060 --> 00:15:31,800
які змяшчае нумар 35.

349
00:15:31,800 --> 00:15:32,750
Дык вось выпадак два.

350
00:15:32,750 --> 00:15:36,190
Так што ўжо, я накшталт квантавання
колькі працы я павінен зрабіць тут.

351
00:15:36,190 --> 00:15:39,880
>> І, нарэшце, відавочны выпадак сярэдзіна
Сапраўды, у сярэдзіне, калі я хачу

352
00:15:39,880 --> 00:15:45,870
ўстаўляць нешта накшталт кажуць 23, які ідзе
паміж 23 і 26, але

353
00:15:45,870 --> 00:15:48,680
Зараз усё становіцца трохі больш
ўдзельнічае, таму што

354
00:15:48,680 --> 00:15:52,800
паказальнікі павінны быць зменены?

355
00:15:52,800 --> 00:15:56,680
22 Так, безумоўна, павінна быць зменена
таму што ён не можа паказаць на 26 больш.

356
00:15:56,680 --> 00:16:00,320
Яму трэба, каб ён паказваў на новы вузел,
Мне прыйдзецца вылучыць па тэлефоне

357
00:16:00,320 --> 00:16:01,770
Malloc ці некаторы эквівалент.

358
00:16:01,770 --> 00:16:05,990
>> Але потым я таксама трэба, каб новы вузел, 23
У гэтым выпадку, каб мець свой паказальнік

359
00:16:05,990 --> 00:16:07,870
паказваючы на ​​каго?

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

361
00:16:08,560 --> 00:16:10,380
І там будзе
Парадак аперацый тут.

362
00:16:10,380 --> 00:16:13,410
Таму што калі я зраблю гэта па-дурному і я
Напрыклад пачатку ў пачатку

363
00:16:13,410 --> 00:16:16,040
спісе, і мая мэта, каб ўставіць 23.

364
00:16:16,040 --> 00:16:18,610
І я правяраў, яно належыць
тут, каля дзевяці?

365
00:16:18,610 --> 00:16:18,950
Няма.

366
00:16:18,950 --> 00:16:20,670
Ці мае месца тут, побач з 17?

367
00:16:20,670 --> 00:16:20,940
Няма.

368
00:16:20,940 --> 00:16:22,530
Ці мае яна належыць тут побач з 22?

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

370
00:16:23,300 --> 00:16:26,400
>> Цяпер, калі я дурны тут, і ня
думаючы, што гэта да канца, я мог бы

371
00:16:26,400 --> 00:16:28,320
вылучыць мой новы вузел 23.

372
00:16:28,320 --> 00:16:32,080
Я мог бы абнавіць паказальнік з
вузел, які называецца 22, паказваючы

373
00:16:32,080 --> 00:16:33,080
яго на новы вузел.

374
00:16:33,080 --> 00:16:36,140
І што тады мне давядзецца абнаўляць
паказальнік на новы вузел, каб быць?

375
00:16:36,140 --> 00:16:38,120
>> Студэнт: [неразборліва].

376
00:16:38,120 --> 00:16:38,385
>> Выступоўца 1: Цалкам дакладна.

377
00:16:38,385 --> 00:16:39,710
Паказваючы на ​​26.

378
00:16:39,710 --> 00:16:45,590
Але, чорт вазьмі, калі б я ўжо не абнаўляць
Паказальнік 22, каб яна паказвала на гэтага хлопца, і

379
00:16:45,590 --> 00:16:48,260
зараз у мяне ёсць сіроты, астатнія
спісу, так бы мовіць.

380
00:16:48,260 --> 00:16:52,140
Так што парадак аперацый тут
будзе важна.

381
00:16:52,140 --> 00:16:55,100
>> Для гэтага я мог скрасці,
скажам, шэсць добраахвотнікаў.

382
00:16:55,100 --> 00:16:57,650
І давайце паглядзім, калі мы не можам зрабіць гэтага
візуальна замест кода-мудрым.

383
00:16:57,650 --> 00:16:59,330
І ў нас ёсць некаторыя выдатныя стрэсу
шары для вас сёння.

384
00:16:59,330 --> 00:17:02,510
Добра, а як аб адным, двух, у
Назад - у канцы там.

385
00:17:02,510 --> 00:17:04,530
тры, чатыры, вы абодва
Хлопцы на канцы.

386
00:17:04,530 --> 00:17:05,579
І пяць, шэсць.

387
00:17:05,579 --> 00:17:05,839
Вядома.

388
00:17:05,839 --> 00:17:06,450
Пяць і шэсць.

389
00:17:06,450 --> 00:17:08,390
Добра, і мы прыедзем
каб вы, хлопцы, у наступны раз.

390
00:17:08,390 --> 00:17:09,640
Добра, падымайся.

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

392
00:17:12,010 --> 00:17:14,819
>> Добра, раз ужо ты тут, па-першае,
Вы хацелі б быць тым, няёмка

393
00:17:14,819 --> 00:17:16,119
Шкло ў Google тут?

394
00:17:16,119 --> 00:17:19,075
Добра, добра, шкло,
Запіс відэа.

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

396
00:17:22,720 --> 00:17:24,589
Добра, вы добра ісці.

397
00:17:24,589 --> 00:17:27,950
>> Добра, так што калі вы, хлопцы, можаце прыехаць
Тут, я падрыхтаваў загадзя

398
00:17:27,950 --> 00:17:30,110
некаторыя лічбы.

399
00:17:30,110 --> 00:17:31,240
Добра, ідзі сюды.

400
00:17:31,240 --> 00:17:33,440
А чаму б вам не пайсці крыху
далей, што шлях.

401
00:17:33,440 --> 00:17:35,520
І паглядзім, як цябе завуць,
Шкло з Google?

402
00:17:35,520 --> 00:17:35,910
>> Студэнт: Бэн.

403
00:17:35,910 --> 00:17:36,230
>> Выступоўца 1: Бэн?

404
00:17:36,230 --> 00:17:38,380
ОК, Бэн, ты будзеш першым, літаральна.

405
00:17:38,380 --> 00:17:40,580
Такім чынам, мы збіраемся адправіць вам
ў канцы стадыі.

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

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

408
00:17:41,990 --> 00:17:44,530
>> Выступоўца 1: Джэйсан, OK вы будзеце
быць нумарам дзевяць.

409
00:17:44,530 --> 00:17:46,700
Так што, калі вы хочаце прытрымлівацца Бэн такім чынам.

410
00:17:46,700 --> 00:17:47,010
>> Студэнт: Джыл.

411
00:17:47,010 --> 00:17:49,630
>> Выступоўца 1: Джыл, вы збіраецеся быць
17, які, калі б я зрабіў гэта больш

412
00:17:49,630 --> 00:17:51,260
разумна, я б
пачалося на іншым канцы.

413
00:17:51,260 --> 00:17:52,370
Вы ісці па гэтым шляху.

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

415
00:17:53,030 --> 00:17:53,670
А вы хто?

416
00:17:53,670 --> 00:17:53,980
>> Студэнт: Марыі.

417
00:17:53,980 --> 00:17:56,130
>> Выступоўца 1: Марыя, вы будзеце 22.

418
00:17:56,130 --> 00:17:58,420
А ваша імя?

419
00:17:58,420 --> 00:17:58,810
>> Студэнт: Крыс.

420
00:17:58,810 --> 00:18:00,100
>> Выступоўца 1: Крыс, вы будзеце 26.

421
00:18:00,100 --> 00:18:00,740
А потым, нарэшце.

422
00:18:00,740 --> 00:18:01,400
>> Студэнт: Дыяны.

423
00:18:01,400 --> 00:18:02,670
>> Выступоўца 1: Дыяна, вы будзеце 34.

424
00:18:02,670 --> 00:18:03,920
Такім чынам, вы ідзі сюды.

425
00:18:03,920 --> 00:18:06,360
>> Добра, настолькі дасканалы адсартаваны
Замовіць ужо.

426
00:18:06,360 --> 00:18:09,600
І давайце ісці наперад і рабіць гэта
так што мы можам на самай справе -

427
00:18:09,600 --> 00:18:11,720
Бэн, ты проста выгляд гледзячы
з ў нікуды там.

428
00:18:11,720 --> 00:18:15,670
Такім чынам, давайце пойдзем далей і малююць гэтую
ужываннем зброі, гэтак жа, як я быў, уласна,

429
00:18:15,670 --> 00:18:16,250
што адбываецца.

430
00:18:16,250 --> 00:18:19,540
Так што ісці наперад і даць сабе
фут ці два паміж сабой.

431
00:18:19,540 --> 00:18:22,900
І ісці наперад і адзначыць з аднаго боку,
хто б ты павінен быць накіраваны на

432
00:18:22,900 --> 00:18:23,470
на аснове гэтага.

433
00:18:23,470 --> 00:18:25,890
І калі вы проста паказаць нулявы
прама ўніз да падлогі.

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

435
00:18:27,690 --> 00:18:32,290
>> Так што цяпер у нас ёсць звязаны спіс, і дазвольце мне
прапаную, што я буду гуляць ролю

436
00:18:32,290 --> 00:18:35,110
PTR, так што я не буду турбавацца
правядзенне гэтага вакол.

437
00:18:35,110 --> 00:18:37,830
А потым - нехта дурны Канвенцыі -
Вы можаце называць гэта ўсё, што заўгодна -

438
00:18:37,830 --> 00:18:39,800
папярэдніка паказальнік, паказальнік PRED -

439
00:18:39,800 --> 00:18:43,930
гэта проста мянушка мы далі ў
наш ўзор кода для маёй левай руцэ.

440
00:18:43,930 --> 00:18:47,240
З іншага боку, што будзе захаванне
адсочваць, хто ёсць хто ў

441
00:18:47,240 --> 00:18:48,400
Наступныя сцэнары.

442
00:18:48,400 --> 00:18:52,390
>> Такім чынам, няхай, па-першае, я хачу абрываць
што першы прыклад ўстаўкі, скажам

443
00:18:52,390 --> 00:18:54,330
20 у спісе.

444
00:18:54,330 --> 00:18:57,160
Так што я збіраюся трэба, каб хтосьці
ўвасабляюць у сабе лік 20 для нас.

445
00:18:57,160 --> 00:18:58,950
Так што мне трэба каго-то Malloc
ад аўдыторыі.

446
00:18:58,950 --> 00:18:59,380
Падымайся.

447
00:18:59,380 --> 00:19:00,340
Як цябе завуць?

448
00:19:00,340 --> 00:19:01,300
>> Студэнт: Браян.

449
00:19:01,300 --> 00:19:05,270
>> Выступоўца 1: Браян, усё ў парадку, так што вы
павінен быць вузел, які змяшчае 20.

450
00:19:05,270 --> 00:19:06,810
Добра, ідзі сюды.

451
00:19:06,810 --> 00:19:10,025
І відавочна, што, дзе
Браян сапраўды належыце?

452
00:19:10,025 --> 00:19:12,190
Такім чынам, у сярэдзіне - уласна,
пачакай хвілінку.

453
00:19:12,190 --> 00:19:13,420
Мы робім гэта не ў парадку.

454
00:19:13,420 --> 00:19:17,170
Мы робім гэта нашмат складаней
, Чым яна павінна быць у першую чаргу.

455
00:19:17,170 --> 00:19:21,210
Добра, мы збіраемся бясплатна Браян
Браян і Realloc як пяць.

456
00:19:21,210 --> 00:19:23,680
>> Такім чынам, зараз мы хочам, каб ўставіць
Браян, як пяць.

457
00:19:23,680 --> 00:19:25,960
Так ідзі сюды побач з
Бэн на імгненне.

458
00:19:25,960 --> 00:19:28,250
І вы, верагодна, можа сказаць
дзе гэтая гісторыя ідзе.

459
00:19:28,250 --> 00:19:30,500
Але давайце старанна абдумайце
парадак выканання аперацый.

460
00:19:30,500 --> 00:19:32,880
І гэта менавіта гэта візуальнае
што адбываецца, каб выстраіцца

461
00:19:32,880 --> 00:19:34,080
з гэты ўзор кода.

462
00:19:34,080 --> 00:19:40,120
Дык вось я PTR першапачаткова паказваючы
Ці не на Бэна, як такой, але на любым

463
00:19:40,120 --> 00:19:43,245
ацэньваюць ён утрымлівае, які ў дадзеным выпадку
- Што цябе клічуць?

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

465
00:19:43,670 --> 00:19:47,350
>> Выступоўца 1: Джэйсан, так як Бэн і я
паказваючы на ​​Джэйсана ў гэты момант.

466
00:19:47,350 --> 00:19:49,700
Так што зараз у мяне ёсць, каб вызначыць,
дзе ж Браян належыце?

467
00:19:49,700 --> 00:19:53,500
Таму адзінае, што я маю доступ да
Прама цяпер яго N элемента дадзеных.

468
00:19:53,500 --> 00:19:58,280
Так што я збіраюся праверыць, ці з'яўляецца
Браян менш Джэйсан?

469
00:19:58,280 --> 00:19:59,770
Адказ на гэтае пытанне так.

470
00:19:59,770 --> 00:20:03,680
>> Так што зараз павінна адбыцца,
у правільным парадку?

471
00:20:03,680 --> 00:20:07,120
Мне трэба ўдакладніць, колькі паказальнікаў
Усяго ў гэтай гісторыі?

472
00:20:07,120 --> 00:20:10,720
Дзе мая рука ўсё яшчэ паказваючы на
Джэйсан, і ваша рука - калі вы хочаце

473
00:20:10,720 --> 00:20:12,930
пакласці руку, як, кшталту, я
Не ведаю, знакам пытання.

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

475
00:20:14,070 --> 00:20:15,670
>> Добра, так што вы павінны
некалькі кандыдатаў.

476
00:20:15,670 --> 00:20:20,500
Альбо Бэн ці я ці Джэйсан Браян або
ці ўсе астатнія, якія

477
00:20:20,500 --> 00:20:21,370
паказальнікі трэба змяніць?

478
00:20:21,370 --> 00:20:23,260
Колькі за ўсё?

479
00:20:23,260 --> 00:20:24,080
>> Такім чынам, два.

480
00:20:24,080 --> 00:20:27,090
Мой паказальнік на самай справе не мае ніякага значэння
таму што я толькі часова.

481
00:20:27,090 --> 00:20:31,370
Так што гэтыя два хлопцы, па-відаць,
як Бэн і Браяна.

482
00:20:31,370 --> 00:20:34,410
Такім чынам, дазвольце мне прапанаваць, што мы абнаўляем
Бэн, так як ён у першую чаргу.

483
00:20:34,410 --> 00:20:36,350
Першым элементам гэтага спісу
Цяпер будзе Браян.

484
00:20:36,350 --> 00:20:38,070
Так Бэн кропкі на Браяна.

485
00:20:38,070 --> 00:20:39,320
Добра, што цяпер?

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

487
00:20:41,950 --> 00:20:43,460
>> Хто атрымлівае паказаў на каго?

488
00:20:43,460 --> 00:20:44,710
>> Студэнт: [неразборліва].

489
00:20:44,710 --> 00:20:46,180
>> Выступоўца 1: Добра, такім чынам Браян
каб паказаць на Джэйсана.

490
00:20:46,180 --> 00:20:48,360
Але я страціў гэты паказальнік?

491
00:20:48,360 --> 00:20:49,980
Ці ведаю я, дзе Джэйсан?

492
00:20:49,980 --> 00:20:50,790
>> Студэнт: [неразборліва].

493
00:20:50,790 --> 00:20:52,620
>> Выступоўца 1: я раблю, так як я
часовы паказальнік.

494
00:20:52,620 --> 00:20:55,110
І па-відаць, я не змяніў
, Каб паказаць на новы вузел.

495
00:20:55,110 --> 00:20:58,300
Так што мы можам проста Браян пункту
той, хто на мяне паказваючы на.

496
00:20:58,300 --> 00:20:59,000
І мы зрабілі.

497
00:20:59,000 --> 00:21:01,890
Такім выпадкам, устаўка на
пачатак спісу.

498
00:21:01,890 --> 00:21:02,950
Былі два ключавых кроку.

499
00:21:02,950 --> 00:21:06,750
Па-першае, мы павінны абнавіць Бэна, а затым
Мы таксама павінны абнавіць Браян.

500
00:21:06,750 --> 00:21:09,230
І тады я не прыйдзецца турбавацца
тащась праз астатнюю

501
00:21:09,230 --> 00:21:12,680
спіс, таму што мы ўжо знайшлі яго
размяшчэнне, таму што ён належаў да

502
00:21:12,680 --> 00:21:14,080
злева ад першага элемента.

503
00:21:14,080 --> 00:21:15,400
>> Добра, даволі простая.

504
00:21:15,400 --> 00:21:18,110
На самай справе, здаецца, што мы ўжо амаль
робіць гэта занадта складана.

505
00:21:18,110 --> 00:21:20,240
Такім чынам, давайце абрываць канца
спісу, і ўбачыць, дзе

506
00:21:20,240 --> 00:21:21,380
Складанасць пачынаецца.

507
00:21:21,380 --> 00:21:24,560
Так што калі цяпер, я Alloc ад аўдыторыі.

508
00:21:24,560 --> 00:21:25,540
Любы хоча гуляць 55?

509
00:21:25,540 --> 00:21:26,700
Добра, я бачыў вашу руку першым.

510
00:21:26,700 --> 00:21:29,620
Падымайся.

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

512
00:21:30,030 --> 00:21:31,177
Як цябе завуць?

513
00:21:31,177 --> 00:21:32,310
>> Студэнт: [неразборліва].

514
00:21:32,310 --> 00:21:33,240
>> Выступоўца 1: Habata.

515
00:21:33,240 --> 00:21:33,890
ОК, давай ўверх.

516
00:21:33,890 --> 00:21:35,730
Вы будзеце нумарам 55.

517
00:21:35,730 --> 00:21:37,820
Такім чынам, вы, вядома, належаць
ў канцы спісу.

518
00:21:37,820 --> 00:21:41,850
Так што давайце перайграць мадэлявання са мной
быўшы PTR на імгненне.

519
00:21:41,850 --> 00:21:44,050
Так што я збіраюся першым, каб паказаць на
усё, што Бэна паказваючы на.

520
00:21:44,050 --> 00:21:45,900
Мы абодва цяпер, паказваючы на ​​Браяна.

521
00:21:45,900 --> 00:21:48,420
Так 55 ня менш, чым пяць.

522
00:21:48,420 --> 00:21:52,510
Так што я збіраюся абнавіць сябе,
паказваючы на ​​наступны паказальнік Браяна, які

523
00:21:52,510 --> 00:21:54,450
Цяпер, вядома, Джэйсан.

524
00:21:54,450 --> 00:21:57,310
55 складае не менш за дзевяць, так
Я збіраюся абнавіць PTR.

525
00:21:57,310 --> 00:21:58,890
Я збіраюся абнавіць PTR.

526
00:21:58,890 --> 00:22:02,290
Я збіраюся абнавіць PTR
Я збіраюся абнавіць PTR.

527
00:22:02,290 --> 00:22:05,060
І я збіраюся - Хм, што гэта
цябе завуць?

528
00:22:05,060 --> 00:22:05,560
>> Студэнт: Дыяны.

529
00:22:05,560 --> 00:22:09,190
>> Выступоўца 1: Дыяна паказвае, вядома,
пры нулявым левай рукой.

530
00:22:09,190 --> 00:22:13,030
Дык дзе ж на самай справе Habata
належаць ясна?

531
00:22:13,030 --> 00:22:15,050
З левага боку, тут.

532
00:22:15,050 --> 00:22:19,460
Так як я ведаю, паставіць яе тут
Я думаю, што я аблажаўся.

533
00:22:19,460 --> 00:22:22,420
Бо што такое мастацтва PTR
дадзены момант часу?

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

535
00:22:23,240 --> 00:22:25,580
Так што, хоць, візуальна, мы можам
Відавочна, усе гэтыя

536
00:22:25,580 --> 00:22:26,610
хлопцы тут на сцэне.

537
00:22:26,610 --> 00:22:29,680
Я не сачыў за папярэднімі
чалавек у спісе.

538
00:22:29,680 --> 00:22:33,210
У мяне няма пальцам паказваючы,
У гэтым выпадку нумар вузла 34.

539
00:22:33,210 --> 00:22:34,760
>> Так што давайце на самай справе пачаць над гэтым.

540
00:22:34,760 --> 00:22:37,560
Так што цяпер я на самой справе трэба
Другая лакальнай зменнай.

541
00:22:37,560 --> 00:22:40,980
І гэта тое, што вы ўбачыце ў
Сам ўзор кода C, дзе, як я іду,

542
00:22:40,980 --> 00:22:45,860
калі я абнаўляю маю правую руку, каб паказаць
Джэйсан, тым самым пакідаючы Браяна ззаду, я

543
00:22:45,860 --> 00:22:51,440
лепш пачаць выкарыстоўваць маю левую руку, каб
абнаўлення, дзе я быў, так што, як я іду

544
00:22:51,440 --> 00:22:52,700
праз гэты спіс -

545
00:22:52,700 --> 00:22:55,040
больш няёмка, чым хацеў
Цяпер вось візуальна -

546
00:22:55,040 --> 00:22:56,740
Я іду, каб дабрацца да
канцы спісу.

547
00:22:56,740 --> 00:23:00,020
>> Гэтая рука па-ранейшаму нулявы, які з'яўляецца даволі
бескарысным, акрамя ўказваць

548
00:23:00,020 --> 00:23:02,980
Я ясна ў канцы спісу
але цяпер па меншай меры, у мяне ёсць гэтая

549
00:23:02,980 --> 00:23:08,270
папярэдніка паказальнік, які паказвае тут, так што
Цяпер тое, што рукі і тое, што трэба паказальнікі

550
00:23:08,270 --> 00:23:10,150
ў абнаўленні?

551
00:23:10,150 --> 00:23:13,214
Чыя рука вы хочаце
пераналадзіць у першую чаргу?

552
00:23:13,214 --> 00:23:15,190
>> Студэнт: [неразборліва].

553
00:23:15,190 --> 00:23:16,220
>> Выступоўца 1: Такім чынам, Дыяны.

554
00:23:16,220 --> 00:23:21,110
Дзе Вы хочаце, каб паказаць
Левая Дыяны паказальнік ў?

555
00:23:21,110 --> 00:23:23,620
На 55, па-відаць, з тым каб
мы ўставілі туды.

556
00:23:23,620 --> 00:23:25,560
А дзе павінны 55 паказальніка ісці?

557
00:23:25,560 --> 00:23:27,000
Ўніз, якая прадстаўляе нулявы.

558
00:23:27,000 --> 00:23:28,890
І мае рукі, на дадзены момант, не
значэння, таму што яны былі проста

559
00:23:28,890 --> 00:23:30,070
часовых зменных.

560
00:23:30,070 --> 00:23:31,030
Так што цяпер мы скончым.

561
00:23:31,030 --> 00:23:34,650
>> Такім чынам, дадатковыя складанасці там - і
гэта не так складана рэалізаваць,

562
00:23:34,650 --> 00:23:38,660
але нам патрэбна другая зменная, каб зрабіць
упэўнены, што перш, чым я магу рухаць правай

563
00:23:38,660 --> 00:23:42,140
боку, я абнавіць значэнне маёй левай
боку, прад паказальнік у гэтым выпадку, так

564
00:23:42,140 --> 00:23:45,860
што ў мяне ёсць задні паказальнік
адсочваць, дзе я быў.

565
00:23:45,860 --> 00:23:49,360
Зараз, як у баку, калі вы думаеце, што гэта
праз гэта пачуццё, што гэта

566
00:23:49,360 --> 00:23:51,490
крыху раздражняе, каб захаваць
след гэтага левай рукой.

567
00:23:51,490 --> 00:23:54,015
>> Што б іншае рашэнне
гэтай праблемы былі?

568
00:23:54,015 --> 00:23:56,500
Калі ў вас ёсць, каб перапраектоўваць дадзеных
структуры мы гаворым

569
00:23:56,500 --> 00:23:59,630
праз прама цяпер?

570
00:23:59,630 --> 00:24:02,690
Калі гэта толькі збольшага адчувае сябе крыху
раздражняльным, быццам бы, два паказальніка

571
00:24:02,690 --> 00:24:08,430
збіраецца па спісе, хто яшчэ мог
былі, у ідэальным свеце, падтрымліваецца

572
00:24:08,430 --> 00:24:10,160
інфармацыю, якая нам патрэбна?

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

574
00:24:11,360 --> 00:24:12,610
>> Студэнт: [неразборліва].

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

576
00:24:15,160 --> 00:24:16,150
>> Выступоўца 1: Цалкам дакладна.

577
00:24:16,150 --> 00:24:19,130
Права так ёсць на самой справе цікавае
зародак ідэі.

578
00:24:19,130 --> 00:24:22,470
І гэтая ідэя папярэдняга паказальніка,
паказваючы на ​​папярэдні элемент.

579
00:24:22,470 --> 00:24:25,580
Што рабіць, калі я проста увасабленнем гэтага
ўнутры самога спісу?

580
00:24:25,580 --> 00:24:27,810
І гэта будзе цяжка візуалізаваць
Усё гэта без паперы

581
00:24:27,810 --> 00:24:28,830
падзення на падлогу.

582
00:24:28,830 --> 00:24:31,860
Але выкажам здагадку, што гэтыя хлопцы выкарыстоўвацца як
іх рукі, каб мець папярэднія

583
00:24:31,860 --> 00:24:35,950
паказальнік, і наступны паказальнік, тым самым
рэалізаваць тое, што мы назавем ўдвая

584
00:24:35,950 --> 00:24:36,830
звязаны спіс.

585
00:24:36,830 --> 00:24:41,090
Якая дазволіла б мне, каб разабрацца перамоткі,
значна лягчэй без мяне,

586
00:24:41,090 --> 00:24:43,800
праграміст, неабходнасці трымаць
адсочваць ўручную -

587
00:24:43,800 --> 00:24:44,980
сапраўды ўручную -

588
00:24:44,980 --> 00:24:47,280
ад таго, дзе я быў раней
у спісе.

589
00:24:47,280 --> 00:24:48,110
Таму мы не будзем гэтага рабіць.

590
00:24:48,110 --> 00:24:50,950
Мы будзем трымаць яго проста, таму што гэта
збіраецца прыйсці ў цане, у два разы

591
00:24:50,950 --> 00:24:53,450
шмат месца для паказальнікаў,
калі вы хочаце другую.

592
00:24:53,450 --> 00:24:55,760
Але гэта сапраўды агульны
Структура дадзеных вядомых як

593
00:24:55,760 --> 00:24:57,410
двойчы звязаны спіс.

594
00:24:57,410 --> 00:25:01,310
>> Давайце зробім апошні прыклад тут і пакласці
гэтыя хлопцы з іх пакуты.

595
00:25:01,310 --> 00:25:03,270
Так Malloc 20.

596
00:25:03,270 --> 00:25:05,320
Падымайцеся з праходу там.

597
00:25:05,320 --> 00:25:06,280
Добра, як цябе завуць?

598
00:25:06,280 --> 00:25:07,440
>> Студэнт: [неразборліва].

599
00:25:07,440 --> 00:25:07,855
>> Выступоўца 1: Прабачце?

600
00:25:07,855 --> 00:25:08,480
>> Студэнт: [неразборліва].

601
00:25:08,480 --> 00:25:09,410
>> Выступоўца 1: Demeron?

602
00:25:09,410 --> 00:25:10,230
ОК падымайся.

603
00:25:10,230 --> 00:25:11,910
Вы павінны быць 20.

604
00:25:11,910 --> 00:25:14,720
Вы, відавочна, збіраюцца
належаць ад 17 да 22.

605
00:25:14,720 --> 00:25:16,150
Такім чынам, дазвольце мне даведацца пра свой ўрок.

606
00:25:16,150 --> 00:25:18,150
Я збіраюся пачаць паказальнік
паказваючы на ​​Браяна.

607
00:25:18,150 --> 00:25:21,190
І я буду мець маю левую руку
абнаўляць толькі з Браянам, як я пераехаць у

608
00:25:21,190 --> 00:25:23,600
Джэйсан, 20 праверка робіць менш за дзевяць?

609
00:25:23,600 --> 00:25:24,060
Няма.

610
00:25:24,060 --> 00:25:25,430
На 20 менш, чым 17?

611
00:25:25,430 --> 00:25:25,880
Няма.

612
00:25:25,880 --> 00:25:27,450
На 20 менш, чым 22?

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

614
00:25:28,440 --> 00:25:34,070
Так што паказальнікі ці рук трэба змяніць
дзе яны паказваючы цяпер?

615
00:25:34,070 --> 00:25:37,070
>> Так што мы можам зрабіць, паказваючы на ​​17 20.

616
00:25:37,070 --> 00:25:37,860
Так што гэта нармальна.

617
00:25:37,860 --> 00:25:40,080
Куды мы хочам, каб паказаць
паказальнік цяпер?

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

619
00:25:41,330 --> 00:25:45,410
І мы ведаем, дзе 22, зноў жа дзякуючы
на мой часовы паказальнік.

620
00:25:45,410 --> 00:25:46,760
Такім чынам, мы ўсё ў парадку там.

621
00:25:46,760 --> 00:25:49,440
Дык з-за гэтага часовага захоўвання
Я сачыў, дзе ўсё.

622
00:25:49,440 --> 00:25:55,055
І цяпер вы можаце візуальна ўдавацца у якім
Вы належыце, і цяпер нам трэба 1, 2, 3,

623
00:25:55,055 --> 00:25:58,410
4, 5, 6, 7, 8, 9 шароў стрэс,
і апладысменты для

624
00:25:58,410 --> 00:25:59,770
гэтыя хлопцы, калі мы маглі.

625
00:25:59,770 --> 00:26:00,410
Прыгожа зроблена.

626
00:26:00,410 --> 00:26:05,320
>> [Апладысменты]

627
00:26:05,320 --> 00:26:06,330
>> Выступоўца 1: Добра.

628
00:26:06,330 --> 00:26:09,860
І вы можаце трымаць часткі
паперы на памяць.

629
00:26:09,860 --> 00:26:15,930
>> Добра, так што, паверце мне, гэта нашмат
лягчэй ісці праз гэта з

630
00:26:15,930 --> 00:26:17,680
людзей, чым з фактычным кодам.

631
00:26:17,680 --> 00:26:22,690
Але тое, што вы знойдзеце ў імгненне
Цяпер, то, што ж - о, дзякуй.

632
00:26:22,690 --> 00:26:23,630
Дзякуй -

633
00:26:23,630 --> 00:26:29,360
з'яўляецца тое, што вы ўбачыце, што тыя ж дадзеныя
структуры, звязаны спіс, можа на самай справе

634
00:26:29,360 --> 00:26:33,200
выкарыстоўвацца ў якасці будаўнічага блока, каб яшчэ больш
складаных структур дадзеных.

635
00:26:33,200 --> 00:26:37,620
>> І зразумейце, занадта тэма тут з'яўляецца тое, што
мы абсалютна ўвялі больш

636
00:26:37,620 --> 00:26:40,060
Складанасць у рэалізацыі
гэтага алгарытму.

637
00:26:40,060 --> 00:26:43,940
Ўстаўкі, і калі мы прайшлі праз гэта,
выдаленне і пошук, трохі

638
00:26:43,940 --> 00:26:46,660
складаней, чым
быў з масівам.

639
00:26:46,660 --> 00:26:48,040
Але мы атрымаць некаторую дынаміку.

640
00:26:48,040 --> 00:26:50,180
Мы атрымліваем адаптыўную структуру дадзеных.

641
00:26:50,180 --> 00:26:54,010
>> Але зноў жа, мы плацім цану наяўнасцю некаторых
дадатковыя складанасці, як у

642
00:26:54,010 --> 00:26:54,910
яго ажыццяўленні.

643
00:26:54,910 --> 00:26:56,750
І мы адмовіліся ад выпадковага доступу.

644
00:26:56,750 --> 00:27:00,450
І, шчыра кажучы, няма некаторых добрых
чыстае прадметнае я магу даць вам, што

645
00:27:00,450 --> 00:27:03,120
кажа вось чаму звязаны спіс
лепш, чым масіў.

646
00:27:03,120 --> 00:27:04,100
І пакінуць усё як ёсць.

647
00:27:04,100 --> 00:27:07,520
Таму што тэма паўтарэння цяпер, нават
больш, што ў бліжэйшыя тыдні, з'яўляецца

648
00:27:07,520 --> 00:27:10,200
што значыць не абавязкова
правільны адказ.

649
00:27:10,200 --> 00:27:13,830
>> Вось чаму ў нас ёсць асобныя восі
дызайну для хатніх заданняў.

650
00:27:13,830 --> 00:27:17,700
Гэта будзе вельмі кантэкстна-залежных
ці вы хочаце выкарыстоўваць гэтыя дадзеныя

651
00:27:17,700 --> 00:27:21,750
структуру або, што адно і яно будзе
залежыць ад таго, што для вас важна ў плане

652
00:27:21,750 --> 00:27:24,620
рэсурсаў і складанасці.

653
00:27:24,620 --> 00:27:28,830
>> Але дазвольце мне прапанаваць, што ідэальныя дадзеныя
Структура, Святы Грааль, былі б

654
00:27:28,830 --> 00:27:32,200
тое, што сталая часу,
незалежна ад таго, колькі матэрыял

655
00:27:32,200 --> 00:27:36,940
ўнутры яе, не было б дзіўна, калі
структура дадзеных, якая вяртаецца адказы

656
00:27:36,940 --> 00:27:37,920
пастаяннае час.

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

658
00:27:38,330 --> 00:27:40,110
Гэтае слова ў вашым велізарным слоўніку.

659
00:27:40,110 --> 00:27:41,550
Ці не, гэта слова не з'яўляецца.

660
00:27:41,550 --> 00:27:43,270
Або любая такая праблема.

661
00:27:43,270 --> 00:27:46,360
Ну давайце паглядзім, калі мы не можам па крайняй меры,
зрабіць крок на гэтым шляху.

662
00:27:46,360 --> 00:27:50,190
>> Дазвольце мне прапанаваць новую структуру дадзеных, якая
могуць быць выкарыстаны для розных мэтаў,

663
00:27:50,190 --> 00:27:52,260
У гэтым выпадку называюць хэш-табліцы.

664
00:27:52,260 --> 00:27:55,590
І вось мы на самай справе вярнуцца да зірнуўшы
ў масіве, і ў гэтым выпадку, а таксама

665
00:27:55,590 --> 00:28:00,550
некалькі адвольна, я намаляваў тую
хэш-табліцы ў выглядзе масіва роду

666
00:28:00,550 --> 00:28:02,810
двухмерных масіў -

667
00:28:02,810 --> 00:28:05,410
ці, хутчэй, ён намаляваны тут як два
аднамерны масіў - але гэта толькі

668
00:28:05,410 --> 00:28:10,770
масіў памерам 26, так што, калі мы
называюць масівам, настольны кранштэйны

669
00:28:10,770 --> 00:28:12,440
нуля прамавугольніка ў верхняй частцы.

670
00:28:12,440 --> 00:28:15,090
Табліца 25 кранштэйны ўяўляе сабой прастакутнік
у ніжняй часткі.

671
00:28:15,090 --> 00:28:18,620
І гэта, як я мог бы намаляваць дадзеныя
структура, у якой я хачу захаваць

672
00:28:18,620 --> 00:28:19,790
імёны людзей.

673
00:28:19,790 --> 00:28:24,370
>> Так, напрыклад, і я не буду маляваць
Усё гэта тут, на накладныя выдаткі, калі я

674
00:28:24,370 --> 00:28:29,160
было гэта масіў, які я зараз збіраюся
называюць хэш-табліцу, і гэта зноў жа

675
00:28:29,160 --> 00:28:31,360
Размяшчэнне нуля.

676
00:28:31,360 --> 00:28:34,840
Гэта вось размяшчэнне
, І гэтак далей.

677
00:28:34,840 --> 00:28:37,880
Я сцвярджаю, што я хачу выкарыстоўваць гэтыя дадзеныя
Структура, дзеля абмеркавання,

678
00:28:37,880 --> 00:28:42,600
захоўваць імёны людзей, Аліса і Боб
і Чарлі і іншыя падобныя імёны.

679
00:28:42,600 --> 00:28:46,110
Так што думаць пра гэта цяпер, калі пачаў
, Скажам, слоўнік

680
00:28:46,110 --> 00:28:47,520
з вялікай колькасцю слоў.

681
00:28:47,520 --> 00:28:49,435
Яны, аказваецца, імёны
У нашым прыкладзе.

682
00:28:49,435 --> 00:28:52,560
І ўсё гэта занадта дарэчныя, мабыць,
ажыццяўленне праверкі арфаграфіі, як мы

683
00:28:52,560 --> 00:28:54,400
можа для праблемных ўсталяваць шэсць.

684
00:28:54,400 --> 00:28:59,300
>> Так што, калі ў нас ёсць масіў ад агульнага памеру 26
так што гэта 25-й размяшчэнне

685
00:28:59,300 --> 00:29:03,390
у ніжняй часткі, і я сцвярджаю, што Аліса
Першае слова ў слоўніку

686
00:29:03,390 --> 00:29:07,260
імёны, якія я хачу ўставіць у аператыўную памяць,
у гэтую структуру дадзеных, дзе

687
00:29:07,260 --> 00:29:12,480
інстынкты кажуць вам, што Алісы
імя павінна ісці ў гэтым масіве?

688
00:29:12,480 --> 00:29:13,510
>> У нас ёсць 26 варыянтаў.

689
00:29:13,510 --> 00:29:14,990
Дзе мы хочам паставіць яе?

690
00:29:14,990 --> 00:29:16,200
Мы хочам яе ў кранштэйны нуля, ці не так?

691
00:29:16,200 --> 00:29:18,280
Для Алісы, давайце назавем што нуля.

692
00:29:18,280 --> 00:29:20,110
І B будзе адной і С будуць два.

693
00:29:20,110 --> 00:29:22,600
Такім чынам, мы збіраемся пісаць
Аліса імя тут.

694
00:29:22,600 --> 00:29:24,890
Калі мы затым устаўце Боб, яго
Назва пайду сюды.

695
00:29:24,890 --> 00:29:27,280
Чарлі пайду сюды.

696
00:29:27,280 --> 00:29:30,500
І гэтак далей ўніз праз
гэтай структуры дадзеных.

697
00:29:30,500 --> 00:29:32,090
>> Гэта выдатная структуры дадзеных.

698
00:29:32,090 --> 00:29:32,730
Чаму?

699
00:29:32,730 --> 00:29:37,460
Ну тое, што час працы
ўстаўка імя чалавека ў гэтую

700
00:29:37,460 --> 00:29:39,850
Структура дадзеных прама цяпер?

701
00:29:39,850 --> 00:29:43,702
Улічваючы, што гэтая табліца будзе рэалізаваны,
сапраўды, як масіў.

702
00:29:43,702 --> 00:29:44,940
Ну, гэта пастаяннае час.

703
00:29:44,940 --> 00:29:45,800
Гэта парадку адзінкі.

704
00:29:45,800 --> 00:29:46,360
Чаму?

705
00:29:46,360 --> 00:29:48,630
>> Ну як вы вызначаеце,
Дзе Alice належыць?

706
00:29:48,630 --> 00:29:51,000
Ты глядзіш на якую літару яе імя?

707
00:29:51,000 --> 00:29:51,490
Першае.

708
00:29:51,490 --> 00:29:54,350
І вы можаце атрымаць там, калі гэта радок,
проста гледзячы на ​​радок

709
00:29:54,350 --> 00:29:55,200
Кранштэйн нуля.

710
00:29:55,200 --> 00:29:57,110
Такім чынам, нулявы сімвал радка.

711
00:29:57,110 --> 00:29:57,610
Гэта лёгка.

712
00:29:57,610 --> 00:30:00,350
Мы зрабілі гэта ў Crypto
Прызначэнне тыдні таму.

713
00:30:00,350 --> 00:30:05,310
І тое, як толькі вы ведаеце, што Алісы
Ліст капіталу, мы можам адняць

714
00:30:05,310 --> 00:30:08,160
ад 65 гадоў і сам капітал,
, Што дае нам нуля.

715
00:30:08,160 --> 00:30:10,940
Такім чынам, мы цяпер ведаем, што Аліса належыць
па месцы знаходжання нуля.

716
00:30:10,940 --> 00:30:14,240
>> А калі ўлічыць, паказальнік на гэтыя дадзеныя
структуры, нейкай, як доўга

717
00:30:14,240 --> 00:30:18,840
мне спатрэбіцца, каб знайсці размяшчэнне
нуля ў масіў?

718
00:30:18,840 --> 00:30:22,080
Усяго толькі адзін крок, правая Гэта пастаяннае час
з-за выпадковага доступу мы

719
00:30:22,080 --> 00:30:23,780
Прапанаваны было асаблівасцю масіва.

720
00:30:23,780 --> 00:30:28,570
Карацей кажучы, высветліць, што індэкс
імя Алісы, якая, па

721
00:30:28,570 --> 00:30:32,610
гэтым выпадку, або давайце проста вырашаць
што да нуля, дзе B з'яўляецца адным і С

722
00:30:32,610 --> 00:30:34,900
два, мяркуючы, што з
пастаянная часу.

723
00:30:34,900 --> 00:30:38,510
Я проста глядзець на яе першы ліст,
высвятляючы, дзе нуль

724
00:30:38,510 --> 00:30:40,460
масіў таксама пастаяннае час.

725
00:30:40,460 --> 00:30:42,140
Так што тэхнічна гэта
як цяпер два кроку.

726
00:30:42,140 --> 00:30:43,330
Але гэта ўсё роўна пастаянна.

727
00:30:43,330 --> 00:30:46,880
Так мы называем гэта Big O аднаго Такім чынам мы
устаўленыя Аліса ў гэтую табліцу ў

728
00:30:46,880 --> 00:30:48,440
пастаяннае час.

729
00:30:48,440 --> 00:30:50,960
>> Але, вядома, я вяду сябе
наіўная, так?

730
00:30:50,960 --> 00:30:53,240
Што рабіць, калі ёсць Аарона ў класе?

731
00:30:53,240 --> 00:30:53,990
Ці Алісія?

732
00:30:53,990 --> 00:30:57,230
Або любыя іншыя імёны, якія пачынаюцца з
А. Куды мы збіраемся паставіць

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

734
00:31:00,800 --> 00:31:03,420
Я маю на ўвазе, прама зараз ёсць толькі тры
людзі на стол, таму магчыма, мы

735
00:31:03,420 --> 00:31:07,490
Аарон павінен пакласці па месцы знаходжання
нуль адзін два тры.

736
00:31:07,490 --> 00:31:09,480
>> Права, я мог бы паставіць тут.

737
00:31:09,480 --> 00:31:13,350
Але тады, калі мы спрабуем ўставіць Давіда ў
гэтага спісу, дзе ж Давід ісці?

738
00:31:13,350 --> 00:31:15,170
Цяпер наша сістэма пачынае парушэнні
ўніз, направа?

739
00:31:15,170 --> 00:31:19,210
Таму што цяпер Дэвід заканчвае тут
Калі на самай справе Аарон тут.

740
00:31:19,210 --> 00:31:23,060
І вось цяпер уся гэтая ідэя з
чыстая структура дадзеных, якая дае нам

741
00:31:23,060 --> 00:31:28,010
уставак пастаяннага часу ўжо не
пастаянны час, таму што я павінен

742
00:31:28,010 --> 00:31:31,240
праверыць, о, чорт вазьмі, хто-то ўжо
па месцы знаходжання Алісы.

743
00:31:31,240 --> 00:31:35,320
>> Дазвольце мне даследаваць астатнюю частку гэтага дадзеныя
Структура, шукаючы месца, каб пакласці

744
00:31:35,320 --> 00:31:37,130
хтосьці, як імя Аарона.

745
00:31:37,130 --> 00:31:39,390
І так, што таксама пачынае
прыняць лінейнае час.

746
00:31:39,390 --> 00:31:42,710
Больш за тое, калі вы цяпер хочаце знайсці
Аарон ў гэтай структуры дадзеных, і вы

747
00:31:42,710 --> 00:31:45,430
праверыць і імя Аарона тут няма.

748
00:31:45,430 --> 00:31:47,960
У ідэале, вы проста сказалі б Аарона
не ў структуры дадзеных.

749
00:31:47,960 --> 00:31:51,530
Але калі вы пачынаеце вызваляючы месца для
Аарон, дзе павінна было быць D

750
00:31:51,530 --> 00:31:55,600
або E, вы, горшым выпадку, прыйдзецца праверыць
Уся структура дадзеных, у

751
00:31:55,600 --> 00:31:59,480
гэтым выпадку яна пераходзіць ў нешта
лінейны у памер табліцы.

752
00:31:59,480 --> 00:32:00,920
>> Так што ўсё ў парадку, я буду гэта выправіць.

753
00:32:00,920 --> 00:32:04,200
Праблема тут у тым, што ў мяне было
26 элементаў у гэтым масіве.

754
00:32:04,200 --> 00:32:05,000
Дазвольце мне змяніць.

755
00:32:05,000 --> 00:32:06,010
На жаль.

756
00:32:06,010 --> 00:32:10,600
Дазвольце мне змяніць яго так, што замест быцця
памер 26 у агульнай складанасці, звярніце ўвагу на ніжнюю

757
00:32:10,600 --> 00:32:12,720
Індэкс будзе мяняцца да N мінус 1.

758
00:32:12,720 --> 00:32:16,610
Калі 26 відавочна занадта малы для людзей "
імёны, таму што ёсць тысячы

759
00:32:16,610 --> 00:32:20,830
імёны свету, давайце проста рабіць
ў 100 або 1000 ці 10000.

760
00:32:20,830 --> 00:32:22,960
Давайце проста вылучыць нашмат больш месца.

761
00:32:22,960 --> 00:32:27,230
>> Ну, што зусім не абавязкова зніжае
верагоднасць таго, што мы не будзем мець два

762
00:32:27,230 --> 00:32:31,510
людзі з імёнамі, якія пачынаюцца з, і
Такім чынам, вы збіраецеся, каб паспрабаваць пакласці

763
00:32:31,510 --> 00:32:33,120
імёны па месцы знаходжання нуля да гэтага часу.

764
00:32:33,120 --> 00:32:36,850
Яны ўсё яшчэ збіраемся сутыкаюцца, якая
азначае, што мы ўсё яшчэ трэба рашэнне, каб пакласці

765
00:32:36,850 --> 00:32:41,020
Аліса і Аарона і Алісія і іншыя
імёны, якія пачынаюцца з у іншым месцы.

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

767
00:32:43,460 --> 00:32:46,870
Якая верагоднасць таго, што вы
могуць узнікаць канфлікты ў дадзеных

768
00:32:46,870 --> 00:32:48,240
структуры, як гэта?

769
00:32:48,240 --> 00:32:52,570
>> Ну, дазвольце мне - мы вернемся
На гэтае пытанне тут.

770
00:32:52,570 --> 00:32:55,530
І паглядзіце, як мы маглі б
вырашыць у першую чаргу.

771
00:32:55,530 --> 00:32:58,480
Дазвольце мне падцягнуць гэтую прапанову тут.

772
00:32:58,480 --> 00:33:02,020
Тое, што мы толькі што апісалі алгарытм,
эўрыстычныя называюцца лінейнымі

773
00:33:02,020 --> 00:33:05,030
зандзіравання якой, калі б вы паспрабавалі ўставіць
нешта тут, у гэтым дадзеныя

774
00:33:05,030 --> 00:33:08,920
Структура, якая называецца хэш-табліцу,
і там няма месца там, вы

775
00:33:08,920 --> 00:33:12,000
сапраўды даследаваць структуры дадзеных
праверкі, гэта даступна?

776
00:33:12,000 --> 00:33:13,430
Ці з'яўляецца гэта даступна гэта даступна?

777
00:33:13,430 --> 00:33:13,980
Ці з'яўляецца гэта даступна?

778
00:33:13,980 --> 00:33:17,550
І калі ён, нарэшце, вы устаўце
імя, якое вы першапачаткова

779
00:33:17,550 --> 00:33:19,370
ў іншых месцах у гэтым месцы.

780
00:33:19,370 --> 00:33:23,360
Але ў горшым выпадку, адзінае месца,
можа быць у самым нізе дадзеных

781
00:33:23,360 --> 00:33:25,090
Структура, у самым канцы масіва.

782
00:33:25,090 --> 00:33:30,130
>> Так лінейнага зандзіравання, у горшым выпадку,
ператворыцца ў лінейны алгарытм, дзе

783
00:33:30,130 --> 00:33:34,500
Аарона, калі ён адбудзецца, будзе ўстаўлены апошні
У гэтай структуры дадзеных, ён можа

784
00:33:34,500 --> 00:33:39,540
сутыкацца з гэтай першай месцы, але
Затым скончыцца няўдачай ў самым канцы.

785
00:33:39,540 --> 00:33:43,940
Так што гэта не пастаянная
час святой Грааль для нас.

786
00:33:43,940 --> 00:33:47,650
Гэты падыход ўстаўкі элементаў у
структуру дадзеных, званую хэш

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

788
00:33:52,050 --> 00:33:54,000
Гэта можа ператворыцца ў нешта лінейнай.

789
00:33:54,000 --> 00:33:56,970
>> Так што, калі мы дазволу калізій
некалькі па-іншаму?

790
00:33:56,970 --> 00:34:00,740
Такім чынам, вось больш складаныя
падыходзіць да таго, што да гэтага часу

791
00:34:00,740 --> 00:34:02,800
званы хэш-табліцу.

792
00:34:02,800 --> 00:34:05,890
І хэш, а ў бок, што
Я маю на ўвазе, што індэкс

793
00:34:05,890 --> 00:34:07,070
Якім я казаў раней.

794
00:34:07,070 --> 00:34:09,810
Для хэш нешта можа быць
разглядаць як дзеяслоў.

795
00:34:09,810 --> 00:34:13,690
>> Так што калі вы хэш Алісы імя,
хэш-функцыі, так бы мовіць,

796
00:34:13,690 --> 00:34:14,710
павінна вяртаць лік.

797
00:34:14,710 --> 00:34:18,199
У гэтым выпадку роўна нулю, калі яна належыць на
нулявым месцы, адзін, калі яна належыць на

798
00:34:18,199 --> 00:34:20,000
месцазнаходжанне, і гэтак далей.

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

800
00:34:24,360 --> 00:34:26,159
Першая літара ў чыё-то імя.

801
00:34:26,159 --> 00:34:29,090
Але хэш-функцыя прымае ў якасці
ўвесці некаторыя часткі дадзеных,

802
00:34:29,090 --> 00:34:30,210
радок, цэлае ўсё.

803
00:34:30,210 --> 00:34:32,239
І ён выплёўвае звычайна лік.

804
00:34:32,239 --> 00:34:35,739
І гэты лік, дзе, што дадзеныя
элемент належыць у структуры дадзеных

805
00:34:35,739 --> 00:34:37,800
вядомы тут як хэш-табліцу.

806
00:34:37,800 --> 00:34:41,400
>> Так што проста інтуітыўна, гэта
некалькі іншым кантэксце.

807
00:34:41,400 --> 00:34:44,170
Гэта фактычна мае на ўвазе прыклад
з удзелам дні нараджэння, дзе

808
00:34:44,170 --> 00:34:46,850
там можа быць столькі, колькі
31 дзён у месяцы.

809
00:34:46,850 --> 00:34:52,239
Але тое, што гэтаму чалавеку вырашыць
рабіць у выпадку сутыкнення?

810
00:34:52,239 --> 00:34:55,304
Кантэкст у цяперашні час, а не сутыкненне
імёны, але сутыкненне дні нараджэння,

811
00:34:55,304 --> 00:35:00,760
калі два чалавекі маюць аднолькавы дзень нараджэння
2-га кастрычніка, напрыклад.

812
00:35:00,760 --> 00:35:02,120
>> Студэнт: [неразборліва].

813
00:35:02,120 --> 00:35:05,010
>> Выступоўца 1: Так, так што тут мы маем
больш эфектыўнага выкарыстання звязаных спісаў.

814
00:35:05,010 --> 00:35:07,830
Так гэта выглядае крыху па-іншаму
чым мы звярнулі яго раней.

815
00:35:07,830 --> 00:35:10,790
Але мы, здаецца, ёсць у масіў
на левай баку.

816
00:35:10,790 --> 00:35:13,230
У гэтым няма аднаго індэкса, для якія не
асаблівай прычыны.

817
00:35:13,230 --> 00:35:14,630
Але гэта ўсё яшчэ масіве.

818
00:35:14,630 --> 00:35:16,160
Гэта масіў паказальнікаў.

819
00:35:16,160 --> 00:35:20,670
І кожны з тых элементаў, кожны з
гэтыя колы або касая рыса - слэш

820
00:35:20,670 --> 00:35:23,970
прадстаўляе нулявы - кожная з гэтых
паказальнікаў па-відаць, якія паказваюць на

821
00:35:23,970 --> 00:35:25,730
якія дадзеныя структуры?

822
00:35:25,730 --> 00:35:26,890
Звязаны спіс.

823
00:35:26,890 --> 00:35:30,530
>> Так што цяпер у нас ёсць магчымасць
жорсткі код у нашай праграме

824
00:35:30,530 --> 00:35:32,010
Памер табліцы.

825
00:35:32,010 --> 00:35:35,360
У гэтым выпадку, мы ведаем, ніколі няма
больш за 31 дзён у месяц.

826
00:35:35,360 --> 00:35:38,480
Так жорсткае кадаваньне значэння, як 31
разумнае ў гэтым кантэксце.

827
00:35:38,480 --> 00:35:42,700
У кантэксце імёнаў, жорсткага кадавання
26 не зьяўляецца неабгрунтаваным яго людзей

828
00:35:42,700 --> 00:35:46,340
толькі імёны пачынаюцца з, напрыклад,
алфавіту з удзелам да Z.

829
00:35:46,340 --> 00:35:50,180
>> Мы можам ўціснуць іх усё ў гэтых дадзеных
Структура пакуль, калі мы атрымліваем

830
00:35:50,180 --> 00:35:55,330
сутыкнення, мы не ставім тут імёны,
мы замест гэтага думаць аб гэтых клетках

831
00:35:55,330 --> 00:36:00,270
а не як радкі сябе, але ў якасці
паказальнікаў, напрыклад, Эліс.

832
00:36:00,270 --> 00:36:03,660
І тады Аліса можа мець іншы паказальнік
ў іншае імя, якое пачынаецца з

833
00:36:03,660 --> 00:36:06,150
А. і Боб на самой справе ідзе сюды.

834
00:36:06,150 --> 00:36:10,850
>> І, калі ёсць іншы імя, якое пачынаецца
з В, ён сканчаецца тут.

835
00:36:10,850 --> 00:36:15,070
І таму кожны з элементаў гэтай
Табліца два, калі мы распрацавалі гэтую

836
00:36:15,070 --> 00:36:17,350
трохі разумнейшыя -

837
00:36:17,350 --> 00:36:18,125
Давай, -

838
00:36:18,125 --> 00:36:22,950
калі мы распрацавалі гэта крыху больш
разумнейшы, зараз становіцца адаптивами

839
00:36:22,950 --> 00:36:27,720
структура, у якой няма цвёрдага абмежавання
ад таго, колькі элементаў вы можаце ўставіць

840
00:36:27,720 --> 00:36:30,700
ў гэта, таму што калі ў вас ёсць
сутыкнення, гэта нармальна.

841
00:36:30,700 --> 00:36:34,690
Проста ісці наперад і дадаць яго ў
што мы бачылі трохі назад было

842
00:36:34,690 --> 00:36:38,290
вядомы як звязаны спіс.

843
00:36:38,290 --> 00:36:39,690
>> Ну давайце паўзу на імгненне.

844
00:36:39,690 --> 00:36:42,570
Якая верагоднасць сутыкнення
у першую чаргу?

845
00:36:42,570 --> 00:36:45,480
Права, можа быць, я па думаў, можа быць,
Я на інжынерных гэтую праблему,

846
00:36:45,480 --> 00:36:46,370
таму што вы ведаеце, што?

847
00:36:46,370 --> 00:36:49,070
Так, я магу прыдумаць адвольнае
Прыклады з верхняй частцы маёй галавы, як

848
00:36:49,070 --> 00:36:52,870
Allison і Аарона, але ў рэчаіснасці,
зададзена раўнамернае размеркаванне

849
00:36:52,870 --> 00:36:56,990
уваходаў, то ёсць некаторыя выпадковыя ўстаўкі
у структуру дадзеных, што на самой справе

850
00:36:56,990 --> 00:36:58,580
Верагоднасць сутыкнення?

851
00:36:58,580 --> 00:37:01,670
Добра атрымліваецца, гэта на самай справе
супер высокай.

852
00:37:01,670 --> 00:37:03,850
Дазвольце мне абагульніць гэтую
Праблема, як гэты.

853
00:37:03,850 --> 00:37:08,890
>> Такім чынам, у пакоі N CS50 студэнтаў, што
верагоднасць таго, што па меншай меры

854
00:37:08,890 --> 00:37:11,010
Два студэнта ў пакоі
маюць аднолькавы дзень нараджэння?

855
00:37:11,010 --> 00:37:13,346
Так што ёсць што. Некалькі Hund -

856
00:37:13,346 --> 00:37:16,790
200, 300 людзей тут і некалькі
сотні людзей у сябе дома сёння.

857
00:37:16,790 --> 00:37:20,670
Так што калі вы хацелі спытаць сябе, што гэта
верагоднасць два чалавекі

858
00:37:20,670 --> 00:37:23,930
У гэтым нумары, які мае той жа дзень нараджэння,
мы можам зразумець гэта.

859
00:37:23,930 --> 00:37:26,250
І я сцвярджаю, на самай справе ёсць два
людзей з такімі ж дзень нараджэння.

860
00:37:26,250 --> 00:37:29,560
>> Напрыклад, хто-небудзь
маюць сёння дзень нараджэння?

861
00:37:29,560 --> 00:37:31,340
Учора?

862
00:37:31,340 --> 00:37:32,590
Заўтра?

863
00:37:32,590 --> 00:37:35,980
Усё ў парадку, таму ён адчувае сябе, як я збіраюся
каб зрабіць гэта 363 або каля таго больш

864
00:37:35,980 --> 00:37:39,500
раз на самай справе высветліць,
Калі ў нас ёсць сутыкнення.

865
00:37:39,500 --> 00:37:42,350
Ці мы маглі б проста зрабіць гэта матэматычна
а ня стомна

866
00:37:42,350 --> 00:37:43,200
рабіць гэта.

867
00:37:43,200 --> 00:37:44,500
І прапаную наступнае.

868
00:37:44,500 --> 00:37:48,740
>> Таму я прапаную, каб мы маглі мадэляваць
Верагоднасць двух людзей з

869
00:37:48,740 --> 00:37:55,320
ж дзень нараджэння, як і верагоднасць 1
мінус верагоднасць які не мае

870
00:37:55,320 --> 00:37:56,290
той жа дзень нараджэння.

871
00:37:56,290 --> 00:37:59,960
Такім чынам, каб атрымаць гэта, і гэта толькі
мудрагелісты спосаб напісання гэтага, для

872
00:37:59,960 --> 00:38:03,090
Першы чалавек у пакоі, ён ці яна
можа мець любую адну з магчымых

873
00:38:03,090 --> 00:38:07,370
Дні нараджэння мяркуючы, 365 дзён у годзе,
з выбачэннямі для асоб з

874
00:38:07,370 --> 00:38:08,760
Лютаўская 29 гадоў.

875
00:38:08,760 --> 00:38:13,470
>> Такім чынам, першы чалавек у гэтым нумары бясплатны
мець любую колькасць нараджэнняў

876
00:38:13,470 --> 00:38:18,280
з 365 магчымасцяў так, каб
мы зробім гэта 365 падзяліць на 365,

877
00:38:18,280 --> 00:38:18,990
які з'яўляецца адным.

878
00:38:18,990 --> 00:38:22,700
Наступны чалавек у пакоі, калі мэта
, Каб пазбегнуць сутыкнення, можна толькі

879
00:38:22,700 --> 00:38:26,460
яго ці яе дзень нараджэння аб тым, як
шмат розных магчымых дзён?

880
00:38:26,460 --> 00:38:27,610
364.

881
00:38:27,610 --> 00:38:31,430
Такім чынам, другое складнік ў гэтым выразе
па сутнасці робяць, што матэматыка для нас

882
00:38:31,430 --> 00:38:33,460
шляхам адымання ад аднаго магчымы дзень.

883
00:38:33,460 --> 00:38:36,390
А потым на наступны дзень, на наступны дзень,
на наступны дзень да агульнай колькасці

884
00:38:36,390 --> 00:38:38,100
людзей у пакоі.

885
00:38:38,100 --> 00:38:41,290
>> І калі мы, то разгледзім, што ж тады ёсць
верагоднасць не кожны які мае

886
00:38:41,290 --> 00:38:45,265
унікальныя дні нараджэння, але зноў жа мінус 1
што, што мы атрымліваем выраз

887
00:38:45,265 --> 00:38:47,810
, Што можа вельмі мудрагеліста
выглядаць наступным чынам.

888
00:38:47,810 --> 00:38:50,330
Але гэта больш цікава
глядзець на візуальна.

889
00:38:50,330 --> 00:38:55,120
Гэта графік, дзе па восі абсцыс ўяўляе
Колькасць чалавек у пакоі,

890
00:38:55,120 --> 00:38:56,180
колькасць нараджэнняў.

891
00:38:56,180 --> 00:38:59,840
На восі ардынат верагоднасць
сутыкнення, два чалавекі

892
00:38:59,840 --> 00:39:01,230
якія маюць той жа дзень нараджэння.

893
00:39:01,230 --> 00:39:05,020
>> І ежу на дом ад гэтай крывой
што, як толькі вы атрымаеце як 40

894
00:39:05,020 --> 00:39:11,110
студэнты, твая чарга на 90% верагоднасці
камбінаторнага двух

895
00:39:11,110 --> 00:39:13,550
чалавек ці больш якая мае
той жа дзень нараджэння.

896
00:39:13,550 --> 00:39:18,600
І як толькі вы атрымаеце 58 чалавек падабаецца гэта
амаль 100% шанец двух

897
00:39:18,600 --> 00:39:21,310
людзей у пакоі збіраюцца мець
ж дзень нараджэння, хоць ёсць

898
00:39:21,310 --> 00:39:26,650
365 або 366 магчымых вядра, і
Толькі 58 чалавек у пакоі.

899
00:39:26,650 --> 00:39:29,900
Проста статыстычна вы, верагодна,
атрымаць сутыкненняў, якая ў кароткія

900
00:39:29,900 --> 00:39:31,810
матывуе гэта абмеркаванне.

901
00:39:31,810 --> 00:39:35,890
Што нават калі мы атрымаць фантазіі тут, і
пачаць з гэтых ланцугоў, мы ўсё яшчэ

902
00:39:35,890 --> 00:39:36,950
прыйдзецца сутыкненняў.

903
00:39:36,950 --> 00:39:42,710
>> Так што ўзнікае пытанне, што такое
затраты на вядзенне аперацыі ўстаўкі і выдаленні

904
00:39:42,710 --> 00:39:44,850
у структуру дадзеных, як гэта?

905
00:39:44,850 --> 00:39:46,630
Ну дазвольце мне прапанаваць -

906
00:39:46,630 --> 00:39:51,570
і дазвольце мне вярнуцца да экрана над
тут - калі мы п элементаў у

907
00:39:51,570 --> 00:39:56,330
спіс, так што калі мы спрабуем ўставіць
N элементаў, і ў нас ёсць

908
00:39:56,330 --> 00:39:58,050
колькі ўсяго вядра?

909
00:39:58,050 --> 00:40:03,450
Скажам, 31 за ўсё вядра
у выпадку нараджэння.

910
00:40:03,450 --> 00:40:09,240
Якая максімальная даўжыня аднаго
гэтых ланцугоў патэнцыйна?

911
00:40:09,240 --> 00:40:12,670
>> Калі зноў ёсць 31 магчымых
Дні нараджэння ў дадзеным месяцы.

912
00:40:12,670 --> 00:40:14,580
А бо гэта толькі зліпання ўсіх -

913
00:40:14,580 --> 00:40:15,580
на самай справе гэта дурны прыклад.

914
00:40:15,580 --> 00:40:16,960
Давайце рабіць, а не 26.

915
00:40:16,960 --> 00:40:20,890
Так што, калі на самай справе ёсць людзі, чые імёны
Пачніце з праз Z, тым самым даючы

916
00:40:20,890 --> 00:40:22,780
нам 26 магчымасцяў.

917
00:40:22,780 --> 00:40:25,920
І мы, выкарыстоўваючы структуру дадзеных, як
той, які мы толькі што бачылі, у выніку чаго мы маем

918
00:40:25,920 --> 00:40:30,210
масіў паказальнікаў, кожны з якіх
паказвае на звязаны спіс, дзе

919
00:40:30,210 --> 00:40:32,360
Першы спіс усё
з імем Эліс.

920
00:40:32,360 --> 00:40:35,770
Другі спіс з кожным
імя, якое пачынаецца з, пачынаючы

921
00:40:35,770 --> 00:40:36,980
з В, і гэтак далей.

922
00:40:36,980 --> 00:40:41,020
>> Якая верагоднасць даўжыня кожнага з
гэтыя спісы, калі выказаць здагадку, добры чысты

923
00:40:41,020 --> 00:40:45,410
Размеркаванне імёнаў праз Z
па ўсёй структуры дадзеных?

924
00:40:45,410 --> 00:40:50,210
Там у рускіх людзей у структуры дадзеных
падзеленае на 26, калі яны прыгожа

925
00:40:50,210 --> 00:40:52,110
распаўсюдзіцца па ўсёй
структуры дадзеных.

926
00:40:52,110 --> 00:40:54,970
Такім чынам, даўжыня кожнага з гэтых
ланцугоў п падзеленае на 26.

927
00:40:54,970 --> 00:40:57,380
Але ў вялікіх абазначэнне О, што гэта?

928
00:40:57,380 --> 00:41:00,100

929
00:41:00,100 --> 00:41:02,440
Што гэта на самай справе?

930
00:41:02,440 --> 00:41:04,150
Так што гэта сапраўды проста п, ці не так?

931
00:41:04,150 --> 00:41:06,620
Таму што мы казалі ў мінулым,
цьфу, што вы падзеліце на 26.

932
00:41:06,620 --> 00:41:08,710
Так, на самай справе гэта хутчэй.

933
00:41:08,710 --> 00:41:12,720
Але ў тэорыі, гэта не прынцыпова
усё, што хутчэй.

934
00:41:12,720 --> 00:41:16,040
>> Такім чынам, мы, здаецца, не так ужо шмат
бліжэй да гэтай Святой Грааль.

935
00:41:16,040 --> 00:41:17,750
На самай справе, гэта ўсяго толькі лінейнае час.

936
00:41:17,750 --> 00:41:20,790
Чорт вазьмі, у гэты момант, чаму б нам не
Размесціце адзін велізарны звязаны спіс?

937
00:41:20,790 --> 00:41:23,510
Чаму б нам не выкарыстоўваць толькі адзін велізарны
масіў для захоўвання імёнаў

938
00:41:23,510 --> 00:41:25,010
усё ў пакоі?

939
00:41:25,010 --> 00:41:28,280
Ну, ёсць яшчэ нешта
пераканаўчым аб хэш-табліцы?

940
00:41:28,280 --> 00:41:30,810
Ці ёсць яшчэ нешта пераканаўчых
аб структуры дадзеных

941
00:41:30,810 --> 00:41:33,940
, Які выглядае, як гэта?

942
00:41:33,940 --> 00:41:35,182
Гэта.

943
00:41:35,182 --> 00:41:37,050
>> Студэнт: [неразборліва].

944
00:41:37,050 --> 00:41:39,840
>> Выступоўца 1: Так, і яшчэ раз, калі гэта проста
лінейны алгарытм часу і

945
00:41:39,840 --> 00:41:42,780
лінейнае час структура дадзеных, чаму б мне не
проста захоўваць імя кожнага ў вялікі

946
00:41:42,780 --> 00:41:44,210
масіве або ў вялікім звязаны спіс?

947
00:41:44,210 --> 00:41:47,010
І спыніце рабіць CS нашмат цяжэй
, Чым яна павінна быць?

948
00:41:47,010 --> 00:41:49,600

949
00:41:49,600 --> 00:41:53,190
Што з'яўляецца пераканаўчым з гэтай нагоды, нават
хоць я падрапаў яго?

950
00:41:53,190 --> 00:41:54,930
>> Студэнт: [неразборліва].

951
00:41:54,930 --> 00:41:57,040
>> Выступоўца 1: заказчыкам не?

952
00:41:57,040 --> 00:41:58,140
Дарагія больш.

953
00:41:58,140 --> 00:42:03,390
Так ўстаўкамі патэнцыйна маглі яшчэ
сталай часу, нават калі вашы дадзеныя

954
00:42:03,390 --> 00:42:07,910
структура выглядае наступным чынам, масіў
паказальнікаў, кожны з якіх паказвае на

955
00:42:07,910 --> 00:42:09,550
патэнцыйна звязаны спіс.

956
00:42:09,550 --> 00:42:15,220
Як вы маглі б дасягнуць пастаяннай
Час ўвядзення імёны?

957
00:42:15,220 --> 00:42:16,280
Прыляпіце налепку на фронце, ці не так?

958
00:42:16,280 --> 00:42:19,290
>> Калі мы ахвяруем дызайн гол
раней, дзе мы хацелі захаваць

959
00:42:19,290 --> 00:42:22,650
ўсіх па імёнах, напрыклад, сартуюць,
ці ўсе лічбы на этапе адсартаваныя,

960
00:42:22,650 --> 00:42:25,020
Выкажам здагадку, што ў нас ёсць
малокомплектных звязаны спіс.

961
00:42:25,020 --> 00:42:29,960
Гэта толькі варта нам адзін або два этапы,
Як і ў выпадку з Бэнам і Браян

962
00:42:29,960 --> 00:42:32,750
раней, ўставіць элемент у
пачатку спісу.

963
00:42:32,750 --> 00:42:36,090
Так што, калі мы не клапоцімся пра сартаванні ўсё
з імёнаў, пачынаючы з або ўсё

964
00:42:36,090 --> 00:42:39,660
імёны, якія пачынаюцца з B, мы ўсё яшчэ можам
дасягнення пастаяннай час ўстаўкі.

965
00:42:39,660 --> 00:42:43,900
Цяпер гледзячы Алісы або Боба або любое імя
ў цэлым усё яшчэ што?

966
00:42:43,900 --> 00:42:48,100
Гэта вялікае Аб ад N падзеленае на 26, у
ідэальным выпадку, калі ўсё гэта раўнамерна

967
00:42:48,100 --> 00:42:51,190
размеркаваны, дзе ёсць столькі аўтара
як ёсць Z, які, верагодна,

968
00:42:51,190 --> 00:42:52,220
нерэальна.

969
00:42:52,220 --> 00:42:53,880
Але гэта па-ранейшаму лінейна.

970
00:42:53,880 --> 00:42:57,120
>> Але і тут мы вяртаемся да кропкі
асімптатычнай абазначэння быцця

971
00:42:57,120 --> 00:42:58,600
Тэарэтычна дакладна.

972
00:42:58,600 --> 00:43:02,960
Але ў рэальным свеце, калі я сцвярджаю, што
мая праграма можа зрабіць што-то 26 разоў

973
00:43:02,960 --> 00:43:06,210
хутчэй, чым ваша, чыя праграма
Вы збіраецеся аддаеце перавагу выкарыстоўваць?

974
00:43:06,210 --> 00:43:09,660
Ваша або мая, якая
у 26 разоў хутчэй?

975
00:43:09,660 --> 00:43:14,320
Рэальна, асобы, складае 26
разы хутчэй, нават калі тэарэтычна

976
00:43:14,320 --> 00:43:18,790
нашы алгарытмы працуюць у тым жа
асімптатычнае час.

977
00:43:18,790 --> 00:43:20,940
>> Дазвольце мне прапанаваць іншую
Рашэнне ў цэлым.

978
00:43:20,940 --> 00:43:24,380
І калі гэтага не адразу вас напавал,
мы са структур дадзеных.

979
00:43:24,380 --> 00:43:27,420
Дык гэта ён, сінтаксічнага дрэва -

980
00:43:27,420 --> 00:43:28,520
выгляд дурное імя.

981
00:43:28,520 --> 00:43:32,880
Яно паходзіць ад вымання, і слова
пішацца сінтаксічнага дрэва, т-р-і-е, з-за

982
00:43:32,880 --> 00:43:34,450
Вядома пошуку гучыць як сінтаксічнага дрэва.

983
00:43:34,450 --> 00:43:36,580
Але гэта гісторыя
словы сінтаксічнага дрэва.

984
00:43:36,580 --> 00:43:40,980
>> Так сінтаксічнага дрэва сапраўды свайго роду дрэва,
і гэта таксама гульня на гэтае слова.

985
00:43:40,980 --> 00:43:46,330
І хоць вы не можаце досыць убачыць яго
з гэтай візуалізацыі, сінтаксічнага дрэва з'яўляецца

986
00:43:46,330 --> 00:43:50,790
дрэва структураваныя, як сям'я дрэва з
адным продкам наверсе і шмат

987
00:43:50,790 --> 00:43:54,530
з унукаў і праўнукаў
як пакідае на дне.

988
00:43:54,530 --> 00:43:58,100
Але кожнаму вузлу ў выглядзе дрэва з'яўляецца масівам.

989
00:43:58,100 --> 00:44:00,680
І гэта ў масіве - і давай
спрашчаць на імгненне - гэта

990
00:44:00,680 --> 00:44:04,600
масіў, у гэтым выпадку, памер 26, дзе
кожны вузел зноў масіў памеру

991
00:44:04,600 --> 00:44:09,000
26, дзе нулявы элемент у гэтым
Масіў ўяўляе, а апошні

992
00:44:09,000 --> 00:44:11,810
элемент у кожным такім
Масіў ўяўляе Z.

993
00:44:11,810 --> 00:44:15,520
>> Так што я прапаную, тое, што гэтыя дадзеныя
структуры, вядомай як выглядзе дрэва, можа быць

994
00:44:15,520 --> 00:44:17,600
выкарыстоўвацца таксама для захоўвання слоў.

995
00:44:17,600 --> 00:44:21,740
Мы бачылі, як хвіліну назад, мы маглі захаваць
словамі, ці ў дадзеным выпадку імёны, і мы

996
00:44:21,740 --> 00:44:25,440
бачылі раней, як мы можам захоўваць лікі,
але калі мы арыентуемся на імёны ці радкі

997
00:44:25,440 --> 00:44:27,460
заўважце, што цікава.

998
00:44:27,460 --> 00:44:32,210
Я сцвярджаю, што імя Максвелла
Унутры гэтай структуры дадзеных.

999
00:44:32,210 --> 00:44:33,730
Дзе вы бачыце Максвелла?

1000
00:44:33,730 --> 00:44:35,140
>> Студэнт: [неразборліва].

1001
00:44:35,140 --> 00:44:36,240
>> Выступоўца 1: на левай баку.

1002
00:44:36,240 --> 00:44:39,910
Так што цікава, з гэтымі дадзенымі
структура, а не крама

1003
00:44:39,910 --> 00:44:46,200
Радок M-A-X-W-E-L-L зваротнай касой рысы нуля, усё
бесперапынна, а не тое, што вы робіце

1004
00:44:46,200 --> 00:44:46,890
складаецца ў наступным.

1005
00:44:46,890 --> 00:44:50,510
Калі гэта так сінтаксічнага дрэва структуры дадзеных,
кожны з якіх вузлоў зноў масіва

1006
00:44:50,510 --> 00:44:54,650
і вы хочаце захаваць Максвелла, спачатку
індэкс і так кораня вузла, так што

1007
00:44:54,650 --> 00:44:57,810
сказаць, верхні вузел,
ў становішчы М, направа, так

1008
00:44:57,810 --> 00:44:59,160
прыкладна ў сярэдзіне.

1009
00:44:59,160 --> 00:45:03,740
, А затым адтуль, вы будзеце прытрымлівацца
паказальніка на даччыныя вузлы, так бы мовіць.

1010
00:45:03,740 --> 00:45:06,150
Такім чынам, у тым сэнсе, дрэва сям'і,
вы будзеце прытрымлівацца яго ўніз.

1011
00:45:06,150 --> 00:45:09,030
І гэта прывядзе вас да іншага вузла
На левым баку, якая з'яўляецца

1012
00:45:09,030 --> 00:45:10,540
проста яшчэ адзін масіў.

1013
00:45:10,540 --> 00:45:14,710
>> І потым, калі вы хочаце захаваць Максвел,
вы знойдзеце паказальнік, які ўяўляе

1014
00:45:14,710 --> 00:45:16,430
, Якая з'яўляецца гэты тут.

1015
00:45:16,430 --> 00:45:17,840
Тады вы ідзяце да наступнага вузла.

1016
00:45:17,840 --> 00:45:20,100
І звярніце ўвагу - менавіта таму карціны
трохі падманвае -

1017
00:45:20,100 --> 00:45:21,990
гэты вузел выглядаць супер малюсенькія.

1018
00:45:21,990 --> 00:45:26,050
Але права гэта Y і Z.
Гэта проста аўтар ўсечанай

1019
00:45:26,050 --> 00:45:27,630
здымак так, каб вы на самой справе
бачыць рэчы.

1020
00:45:27,630 --> 00:45:30,400
У адваротным выпадку гэта фота
б надзвычай шырокі.

1021
00:45:30,400 --> 00:45:36,180
Такім чынам, зараз вы індэкса ў вочка X, то
W, то Е, то L, то L. Тады ў чым

1022
00:45:36,180 --> 00:45:37,380
гэта цікаўнасць?

1023
00:45:37,380 --> 00:45:41,250
>> Ну, калі мы выкарыстоўваем гэты выгляд новых
ўзяць на сябе, як захоўваць радок у

1024
00:45:41,250 --> 00:45:44,500
структуры дадзеных, вам усё роўна прыйдзецца
істотна галачку ў дадзеных

1025
00:45:44,500 --> 00:45:47,250
структуры, што слова заканчваецца.

1026
00:45:47,250 --> 00:45:50,830
Іншымі словамі, кожны з гэтых вузлоў
так ці інакш трэба памятаць, што мы

1027
00:45:50,830 --> 00:45:53,500
фактычна выканалі ўсе гэтыя паказальнікі
і з'язджаюць крыху

1028
00:45:53,500 --> 00:45:58,370
хлебных дробак на дне тут гэтага
Структура, каб паказаць, M-A-X-W-E-L-L ўяўляе

1029
00:45:58,370 --> 00:46:00,230
сапраўды, у гэтай структуры дадзеных.

1030
00:46:00,230 --> 00:46:02,040
>> Такім чынам, можна зрабіць наступным чынам.

1031
00:46:02,040 --> 00:46:06,810
Кожны з вузлоў на малюнку мы проста
піла мае адзін, масіў памерам 27.

1032
00:46:06,810 --> 00:46:10,550
І гэта зараз 27, так як у P ўсталяваць шэсць,
мы фактычна даюць вам апостраф,

1033
00:46:10,550 --> 00:46:13,590
каб мы маглі мець імёны, як O'Reilly
і іншыя з апострафа.

1034
00:46:13,590 --> 00:46:14,820
Але тая самая ідэя.

1035
00:46:14,820 --> 00:46:17,710
Кожны з гэтых элементаў у
масіва паказвае на структуру

1036
00:46:17,710 --> 00:46:19,320
вузел, так што проста вузлом.

1037
00:46:19,320 --> 00:46:21,430
Так што гэта вельмі нагадвае
нашай звязанага спісу.

1038
00:46:21,430 --> 00:46:24,550
>> А то ў мяне лагічны, які я
называю слова, якое проста будзе

1039
00:46:24,550 --> 00:46:29,120
дакладна, калі слова заканчваецца на гэтым
вузел у дрэве.

1040
00:46:29,120 --> 00:46:32,870
Гэта па сутнасці, ёсць трохі
трыкутніка мы бачылі некалькі хвілін таму.

1041
00:46:32,870 --> 00:46:37,190
Так што, калі слова заканчваецца ў гэтым вузле ў
Дрэва, гэтае слова поле будзе праўдай,

1042
00:46:37,190 --> 00:46:41,990
які канцэптуальна галачкі, або
мы малюем гэты трохкутнік, ды там

1043
00:46:41,990 --> 00:46:44,080
гэтае слова тут.

1044
00:46:44,080 --> 00:46:45,120
>> Так што гэта сінтаксічнага дрэва.

1045
00:46:45,120 --> 00:46:48,540
А цяпер пытанне ў тым, што
з'яўляецца час яго працы?

1046
00:46:48,540 --> 00:46:49,930
Ён вялікі O п?

1047
00:46:49,930 --> 00:46:51,410
Гэта што-то яшчэ?

1048
00:46:51,410 --> 00:46:57,330
Ну, калі вы п імёны ў гэтых дадзеных
Структура, Максвел ўсяго толькі адзін з

1049
00:46:57,330 --> 00:47:02,330
іх, што час працы
ўстаўкі або знайсці Максвелла?

1050
00:47:02,330 --> 00:47:06,230

1051
00:47:06,230 --> 00:47:09,050
Што час працы
ўстаўкі Максвелла?

1052
00:47:09,050 --> 00:47:11,740
Калі ёсць іншыя назвы N
ўжо ў табліцы?

1053
00:47:11,740 --> 00:47:12,507
Да?

1054
00:47:12,507 --> 00:47:15,429
>> Студэнт: [неразборліва].

1055
00:47:15,429 --> 00:47:17,550
>> Выступоўца 1: Так, гэта даўжыня
імя, ці не так?

1056
00:47:17,550 --> 00:47:24,420
Так М-а-х-З-е-л-л таму ён адчувае сябе, як гэта
Алгарытм Big O сямі.

1057
00:47:24,420 --> 00:47:26,580
Цяпер, вядома, імя
будзе вар'іравацца ў даўжыню.

1058
00:47:26,580 --> 00:47:27,380
Можа быць, гэта кароткае імя.

1059
00:47:27,380 --> 00:47:28,600
Можа быць, гэта доўгае імя.

1060
00:47:28,600 --> 00:47:33,390
Але тое, што ключавым тут з'яўляецца тое, што
гэта пастаяннае лік.

1061
00:47:33,390 --> 00:47:36,810
А можа быць, гэта не зусім сталае,
але Бог, калі рэальна, у

1062
00:47:36,810 --> 00:47:41,570
слоўнік, там, напэўна, некаторы мяжа
на колькасць літар у

1063
00:47:41,570 --> 00:47:43,820
імя чалавека ў канкрэтнай краіне.

1064
00:47:43,820 --> 00:47:46,940
>> І такім чынам, мы можам выказаць здагадку, што
значэнне з'яўляецца сталым.

1065
00:47:46,940 --> 00:47:47,750
Я не ведаю, што гэта такое.

1066
00:47:47,750 --> 00:47:50,440
Гэта, напэўна, больш, чым
мы думаем, што гэта такое.

1067
00:47:50,440 --> 00:47:52,720
Таму што заўсёды ёсць які-небудзь кут
выпадку з вар'ятам доўгае імя.

1068
00:47:52,720 --> 00:47:56,360
Так што давайце называць гэта К, але яна па-ранейшаму
пастаянная як мяркуецца, таму што кожны

1069
00:47:56,360 --> 00:48:00,190
назваць у свеце, па меншай меры
канкрэтнай краіны, з'яўляецца тое, што даўжыня або

1070
00:48:00,190 --> 00:48:01,780
карацей, так што гэта пастаянна.

1071
00:48:01,780 --> 00:48:04,490
Але калі мы сказалі нешта вялікае
O пастаяннага значэння, што гэта такое

1072
00:48:04,490 --> 00:48:07,760
сапраўды эквівалентныя?

1073
00:48:07,760 --> 00:48:10,420
Гэта сапраўды адно і тое ж
як кажуць пастаяннае час.

1074
00:48:10,420 --> 00:48:11,530
>> Зараз мы накшталт падману, праўда?

1075
00:48:11,530 --> 00:48:15,340
Мы накшталт выкарыстоўваючы некаторыя тэорыі
тут, каб сказаць, што добра, парадку Да

1076
00:48:15,340 --> 00:48:17,450
сапраўды толькі парадку адной,
і гэта пастаяннае час.

1077
00:48:17,450 --> 00:48:18,200
Але гэта на самай справе.

1078
00:48:18,200 --> 00:48:22,550
Паколькі ключавое разуменне ў тым, што
калі мы маем п імёны ўжо ў гэтым

1079
00:48:22,550 --> 00:48:26,010
структуру дадзеных, і мы ўстаўляем Максвел,
гэта колькасць часу, якое патрабуецца нам

1080
00:48:26,010 --> 00:48:29,530
ўставіць Максвелла на ўсіх пацярпелых
па тым, як шмат іншых людзей

1081
00:48:29,530 --> 00:48:31,100
ў структуры дадзеных?

1082
00:48:31,100 --> 00:48:31,670
Не падобна, каб быць.

1083
00:48:31,670 --> 00:48:36,280
Калі б я быў мільярд больш элементаў у гэтай
дрэва, а затым ўставіць Максвеллом

1084
00:48:36,280 --> 00:48:38,650
Ён на ўсіх пацярпелых?

1085
00:48:38,650 --> 00:48:39,050
Няма.

1086
00:48:39,050 --> 00:48:42,950
І гэта ў адрозненне ад любога дня дадзеныя
структур, якія мы бачылі да гэтага часу, дзе

1087
00:48:42,950 --> 00:48:46,820
час працы вашага алгарытму
зусім не залежыць ад таго, колькі

1088
00:48:46,820 --> 00:48:51,430
матэрыял або яшчэ не быў
У гэтай структуры дадзеных.

1089
00:48:51,430 --> 00:48:54,650
>> І так з гэтым дае вам цяпер
магчымасць усталяваць шэсць р, якая будзе

1090
00:48:54,650 --> 00:48:58,310
зноў звязана з ажыццяўленнем ўласнай
праверка арфаграфіі, чытання ў 150000

1091
00:48:58,310 --> 00:49:01,050
словамі, як лепш захаваць гэтую
не абавязкова з'яўляецца відавочным.

1092
00:49:01,050 --> 00:49:04,030
І хоць я імкнуўся знайсці
Святой Грааль, я не

1093
00:49:04,030 --> 00:49:05,330
сцвярджаюць, што гэта сінтаксічнага дрэва.

1094
00:49:05,330 --> 00:49:09,810
На самай справе, Хэш-табліцу можна вельмі добра
апынуцца значна больш эфектыўным.

1095
00:49:09,810 --> 00:49:10,830
Але гэта толькі -

1096
00:49:10,830 --> 00:49:14,620
гэта толькі адна з праектных рашэнняў
Вы павінны зрабіць.

1097
00:49:14,620 --> 00:49:18,920
>> Але ў заключэнне давайце 50 або каля таго
секунды, каб зірнуць на тое, што ляжыць

1098
00:49:18,920 --> 00:49:22,190
наперадзе на наступным тыдні і далей мы пераходзім
з гэтай каманднага радка

1099
00:49:22,190 --> 00:49:26,220
З светам, калі на вэб-праграмы рэчаў
заснаваны і моў, як PHP і

1100
00:49:26,220 --> 00:49:30,350
JavaScript і сам Інтэрнэт,
пратаколаў, такіх як HTTP, якія ў вас ёсць

1101
00:49:30,350 --> 00:49:32,870
само сабой якія разумеюцца, на працягу многіх гадоў
цяпер, і кожны набраў больш

1102
00:49:32,870 --> 00:49:34,440
дзень, мабыць, і не бачыў.

1103
00:49:34,440 --> 00:49:37,420
І мы пачнем адхіліце
пластах Што такое Інтэрнэт.

1104
00:49:37,420 --> 00:49:40,650
А што гэта за код, які
ляжыць у аснове сённяшняй інструментаў.

1105
00:49:40,650 --> 00:49:43,230
Так 50 секунд гэты тізер тут.

1106
00:49:43,230 --> 00:49:46,570
Я даю вам Воіны Сеткі.

1107
00:49:46,570 --> 00:49:51,370
>> [Прайграванне відэа]

1108
00:49:51,370 --> 00:49:56,764
>> -Ён прыйшоў з паведамленнем.

1109
00:49:56,764 --> 00:50:00,687
З пратаколам усё сваё.

1110
00:50:00,687 --> 00:50:13,370

1111
00:50:13,370 --> 00:50:19,780
Ён прыйшоў у свет жорсткіх брандмаўэраў,
абыякавымі маршрутызатары, і небяспекі далёка

1112
00:50:19,780 --> 00:50:22,600
горш, чым смерць.

1113
00:50:22,600 --> 00:50:23,590
Ён хуткі.

1114
00:50:23,590 --> 00:50:25,300
Ён моцны.

1115
00:50:25,300 --> 00:50:27,700
Ён TCPIP.

1116
00:50:27,700 --> 00:50:30,420
І ў яго ёсць ваш адрас.

1117
00:50:30,420 --> 00:50:32,920

1118
00:50:32,920 --> 00:50:34,590
Ваяры ў Сеткі.

1119
00:50:34,590 --> 00:50:35,290
>> [КАНЕЦ ВИДЕОВОСПРОИЗВЕДЕНИЕ]

1120
00:50:35,290 --> 00:50:38,070
>> Выступоўца 1: Гэта значыць, як у інтэрнэце
будзем працаваць на наступным тыдні.

1121
00:50:38,070 --> 00:50:40,406