1
00:00:00,000 --> 00:00:02,832
>> [Мусиц плаиинг]

2
00:00:02,832 --> 00:00:05,670

3
00:00:05,670 --> 00:00:08,560
>> Даг Ллоид: У реду, тако да
Ова тачка у току,

4
00:00:08,560 --> 00:00:15,300
покрили смо пуно основама Ц.
Ми знамо много о променљиве, низови,

5
00:00:15,300 --> 00:00:17,610
показивачи, све добре ствари.

6
00:00:17,610 --> 00:00:21,610
Они су сви некако изградио
у да видим као основе,

7
00:00:21,610 --> 00:00:23,880
али можемо учинити више, зар не?

8
00:00:23,880 --> 00:00:27,930
Ми могу комбиновати ствари
заједно интересантне начине.

9
00:00:27,930 --> 00:00:31,010
>> И тако урадимо то, хајде да почнемо
да се грана из онога што нам даје, Ц,

10
00:00:31,010 --> 00:00:35,270
и почети да креирате сопствени податке
структуре које користе ове зграде

11
00:00:35,270 --> 00:00:40,590
блокови заједно да урадимо нешто
заиста вредан и користан.

12
00:00:40,590 --> 00:00:43,420
Један од начина можемо да урадимо је ово
да разговарамо о колекцијама.

13
00:00:43,420 --> 00:00:48,360
Дакле, до сада смо имали једну врсту података
структура за заступање колекције

14
00:00:48,360 --> 00:00:51,030
Као вредности, сличне вредности.

15
00:00:51,030 --> 00:00:52,350
То би било низ.

16
00:00:52,350 --> 00:00:57,020
Имамо колекцију целих бројева, или
колекције ликова и тако даље.

17
00:00:57,020 --> 00:01:00,890
>> Структуре су такође врста података
структура за прикупљање информација,

18
00:01:00,890 --> 00:01:03,220
али то није за прикупљање као вредности.

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

20
00:01:08,090 --> 00:01:10,750
Али то није сама
некада ланац заједно

21
00:01:10,750 --> 00:01:16,920
или се повежите заједно слично
предмети, попут низа.

22
00:01:16,920 --> 00:01:20,960
Низови су одличне за
Елемент погледати, али рецалл

23
00:01:20,960 --> 00:01:24,262
да је веома тешко
да убаците у матрици,

24
00:01:24,262 --> 00:01:26,470
осим ако смо убацивањем у
на самом крају тог низа.

25
00:01:26,470 --> 00:01:29,730
>> А најбољи пример имам
за то је уметање врста.

26
00:01:29,730 --> 00:01:31,650
Ако се сећате наш видео
на унесени врсте,

27
00:01:31,650 --> 00:01:34,110
било је доста
расход укључени у има

28
00:01:34,110 --> 00:01:37,970
да покупи елементе, а схифт их
из начин да се уклапају нешто

29
00:01:37,970 --> 00:01:41,290
у средини вашег поља.

30
00:01:41,290 --> 00:01:44,690
Низови такође пате од другог
проблем, који је нефлексибилност.

31
00:01:44,690 --> 00:01:47,150
Када смо прогласити низ,
добијамо једну шансу у томе.

32
00:01:47,150 --> 00:01:49,790
Ми добијамо да кажем, хоћу
оволико елемената.

33
00:01:49,790 --> 00:01:51,940
Може бити 100, могло би
бити 1.000, могло би

34
00:01:51,940 --> 00:01:55,930
бити х где је к број који је корисник
дао нас на упит или у команди

35
00:01:55,930 --> 00:01:56,630
линија.

36
00:01:56,630 --> 00:01:59,905
>> Али ми само један хитац у томе, ми
немој да се онда каже Ох, уствари

37
00:01:59,905 --> 00:02:04,360
потребно 101 или ми је потребно Кс плус 20.

38
00:02:04,360 --> 00:02:07,910
Прекасно, већ смо је прогласио
Арраи, и ако желимо да се 101 или х

39
00:02:07,910 --> 00:02:12,050
Плус 20, морамо да се изјасни
потпуно другачији низ,

40
00:02:12,050 --> 00:02:15,540
копирати све елементе низа
преко, а онда имамо довољно.

41
00:02:15,540 --> 00:02:19,880
А шта ако смо опет у праву, шта
ако стварно треба 102, или к плус 40,

42
00:02:19,880 --> 00:02:21,970
морамо ово поново да урадимо.

43
00:02:21,970 --> 00:02:26,250
Дакле, они су врло нефлексибилна
за промену величине наше податке,

44
00:02:26,250 --> 00:02:29,360
али ако смо заједно неки комбинујемо
од основа које смо већ

45
00:02:29,360 --> 00:02:33,230
сазнао показивачима и структура,
посебно уз динамичке меморије

46
00:02:33,230 --> 00:02:36,180
расподела са маллоц, ми
можете ставити ове коцкице

47
00:02:36,180 --> 00:02:40,960
Да бисте креирали нове податке струцтуре-- А
појединачно повезане листе можемо говоре--

48
00:02:40,960 --> 00:02:45,400
који нам омогућава да расте и
скупити колекцију вредности

49
00:02:45,400 --> 00:02:48,800
и нећемо имати расипа простора.

50
00:02:48,800 --> 00:02:53,320
>> Дакле, опет зовемо ову идеју,
Овај појам, повезане листе.

51
00:02:53,320 --> 00:02:56,320
Конкретно, у овом видеу смо
говоримо о појединачно повезане листе,

52
00:02:56,320 --> 00:02:59,185
а онда још један видео снимак који смо разговараћемо
о двоструко повезане листе, које

53
00:02:59,185 --> 00:03:01,560
је само варијација на тему овде.

54
00:03:01,560 --> 00:03:05,200
Али појединачно повезана листа
се састоји од чворова,

55
00:03:05,200 --> 00:03:08,559
чворови само што апстрактна терм--
то је само нешто што зовем

56
00:03:08,559 --> 00:03:10,350
То је нека врста
структура, у основи, ја сам?

57
00:03:10,350 --> 00:03:16,190
Само ћу га назвати ноде-- и ово
чвор има два члана, или два поља.

58
00:03:16,190 --> 00:03:20,300
Има података, обично
цео број, флоат карактер,

59
00:03:20,300 --> 00:03:23,790
или може бити неки други тип података
да сте дефинисан типа деф.

60
00:03:23,790 --> 00:03:29,290
И то садржи показивач на
други чвор истог типа.

61
00:03:29,290 --> 00:03:34,710
>> Дакле, имамо две ствари унутар
Овај чвор, података и показивач

62
00:03:34,710 --> 00:03:36,380
у други чвор.

63
00:03:36,380 --> 00:03:39,370
А ако почнете замислити
, можете мислити о томе

64
00:03:39,370 --> 00:03:42,280
као ланац чворова који
су повезана заједно.

65
00:03:42,280 --> 00:03:45,070
Имамо први чвор, то
садржи податке, и показивач

66
00:03:45,070 --> 00:03:49,110
на други чвор која садржи
података и показивач на трећем чвор.

67
00:03:49,110 --> 00:03:52,940
И то је разлог зашто смо то позив
линкед лист, да су они повезани заједно.

68
00:03:52,940 --> 00:03:56,070
>> Шта ова посебна
Структура чвор изгледа?

69
00:03:56,070 --> 00:04:01,120
Па, ако се сећате из наше видео на
дефинисање прилагођене врсте, са типом деф,

70
00:04:01,120 --> 00:04:05,400
можемо дефинисати и струцтуре--
тип дефинише структуру овако.

71
00:04:05,400 --> 00:04:11,240
тиепдеф струцт сллист, а онда сам
коришћењем овде реч вредност произвољно

72
00:04:11,240 --> 00:04:13,891
да укаже заиста било коју врсту података.

73
00:04:13,891 --> 00:04:16,890
Можете да пренесем цео или пловак,
можете имати шта год желите.

74
00:04:16,890 --> 00:04:19,389
Није ограничено на само
целих, или тако нешто.

75
00:04:19,389 --> 00:04:22,790
Дакле, вредност није само произвољна
тип података, а затим и показивач

76
00:04:22,790 --> 00:04:26,310
на другу чвор истог типа.

77
00:04:26,310 --> 00:04:29,690
>> Сада, постоји мало улов
овде са дефинисања структуре

78
00:04:29,690 --> 00:04:33,030
када је само референтна структура.

79
00:04:33,030 --> 00:04:35,340
Морам имати привремени
наме фор ми структуре.

80
00:04:35,340 --> 00:04:37,640
На крају дана сам се
оцигледно зелис да га зову

81
00:04:37,640 --> 00:04:43,030
СЛЛ чвор, то је на крају нова
наме дио мојој дефиницији типа,

82
00:04:43,030 --> 00:04:47,450
али ја не могу користити Слл чвор
у сред овога.

83
00:04:47,450 --> 00:04:51,430
Разлог је тај што нисам
створио тип се зове Слл чвор

84
00:04:51,430 --> 00:04:55,200
док сам погодио ову последњу тачку овде.

85
00:04:55,200 --> 00:04:59,720
До тада, морам да имам
још један начин да се односи на ову врсту података.

86
00:04:59,720 --> 00:05:02,440
>> И ово је само
референтни тип података.

87
00:05:02,440 --> 00:05:06,314
То; с врсту података Оф А
структуре која садржи податке,

88
00:05:06,314 --> 00:05:08,480
и показивач на други
структура истог типа.

89
00:05:08,480 --> 00:05:11,750
Зато морам да будем у могућности да се односи на
ове податке Тип барем привремено,

90
00:05:11,750 --> 00:05:14,910
тако му даје привремени
Име струцт сллист

91
00:05:14,910 --> 00:05:18,540
ми дозвољава да се каже Желим
поинтер на другу струцт сллист,

92
00:05:18,540 --> 00:05:24,690
струцт сллист звезда, а затим
након што сам завршио дефиницију,

93
00:05:24,690 --> 00:05:27,220
Ја сада могу назвати укуцајте СЛЛ чвор.

94
00:05:27,220 --> 00:05:30,520
>> Зато сте видели ту
привремени назив овде,

95
00:05:30,520 --> 00:05:31,879
али трајно име овде.

96
00:05:31,879 --> 00:05:33,920
Понекад можете видети
дефиниције структуре,

97
00:05:33,920 --> 00:05:36,570
на пример, да нису
само референтна, да

98
00:05:36,570 --> 00:05:39,390
немају овде име спецификатором.

99
00:05:39,390 --> 00:05:43,040
Само бих типедеф струцт,
отвори коврџаву браце, а затим га дефинисати.

100
00:05:43,040 --> 00:05:45,620
Али, ако сте струцт је само
референтна, јер ово је,

101
00:05:45,620 --> 00:05:49,010
морате да наведете
привремени тип име.

102
00:05:49,010 --> 00:05:51,310
Али на крају, сада
да смо урадили ово,

103
00:05:51,310 --> 00:05:53,620
можемо да се односе на
ови чворови, ове јединице,

104
00:05:53,620 --> 00:05:57,900
као СЛЛ чворова за сврхе
остатка овај видео.

105
00:05:57,900 --> 00:06:00,900
>> У реду, тако да знамо како да
створити повезане листе чвор.

106
00:06:00,900 --> 00:06:03,240
Ми знамо како да дефинишемо
повезане листе чвор.

107
00:06:03,240 --> 00:06:06,670
Сада, ако ћемо да почне
користећи их за прикупљање информација,

108
00:06:06,670 --> 00:06:10,360
има неколико операција смо
треба да схвате и рад.

109
00:06:10,360 --> 00:06:12,860
Морамо да знамо како да направите
повезане листе из ведра неба.

110
00:06:12,860 --> 00:06:14,901
Ако већ нема листе,
желимо да покренемо једну.

111
00:06:14,901 --> 00:06:16,960
Дакле, морамо бити у стању
да створи повезану листу,

112
00:06:16,960 --> 00:06:19,130
морамо да вероватно тражити
кроз листу линкова

113
00:06:19,130 --> 00:06:21,830
да пронађе елемента смо у потрази за.

114
00:06:21,830 --> 00:06:24,430
Морамо бити у стању да убаците
нове ствари у попис,

115
00:06:24,430 --> 00:06:25,930
желимо да наша листа бити у стању да расте.

116
00:06:25,930 --> 00:06:28,638
Слично томе, желимо да будемо у стању
да бисте избрисали ствари из наше листе,

117
00:06:28,638 --> 00:06:30,250
желимо да наша листа бити у могућности да смањује.

118
00:06:30,250 --> 00:06:32,160
И на крају нашег
програми, посебно

119
00:06:32,160 --> 00:06:34,550
ако се сећате да смо
динамички доделе меморије

120
00:06:34,550 --> 00:06:38,337
за изградњу ове листе обично,
желимо да ослободимо све те меморије

121
00:06:38,337 --> 00:06:39,670
када смо завршили рад са њим.

122
00:06:39,670 --> 00:06:44,627
И тако морамо бити у стању да избришете
Цео повезана листа у једном не упале.

123
00:06:44,627 --> 00:06:46,460
Дакле, идемо кроз
неке од ових операција

124
00:06:46,460 --> 00:06:51,192
и како бисмо могли да их визуализовати,
говори у псеудокоду код конкретно.

125
00:06:51,192 --> 00:06:53,150
Зато желимо да створимо
повезане листе, тако да можда можемо

126
00:06:53,150 --> 00:06:56,480
Желим да дефинишемо функцију
са овом прототипу.

127
00:06:56,480 --> 00:07:01,690
СЛЛ чвор звезда, стварају, а ја пролазу
у једном аргумент, нека произвољна подаци

128
00:07:01,690 --> 00:07:05,530
тип опет неког произвољног типа података.

129
00:07:05,530 --> 00:07:10,482
Али ја ретурнинг-- ову функцију треба
врати ми се показивач, до А појединачно

130
00:07:10,482 --> 00:07:11,190
линкед лист чвор.

131
00:07:11,190 --> 00:07:14,050
Опет, покушавамо да створимо
повезане листе из ведра неба,

132
00:07:14,050 --> 00:07:17,900
па ми треба показивач на
та листа кад завршим.

133
00:07:17,900 --> 00:07:19,420
>> Дакле, шта су кораци који су укључени овде?

134
00:07:19,420 --> 00:07:20,960
Па, прва ствар коју сам
да урадите је динамички

135
00:07:20,960 --> 00:07:22,550
доделити простор за нови чвор.

136
00:07:22,550 --> 00:07:26,689
Опет, ми то стварање из ничега
ваздух, тако да морамо да маллоц простора за њега.

137
00:07:26,689 --> 00:07:28,480
И наравно, одмах
након што смо маллоц,

138
00:07:28,480 --> 00:07:31,692
увек проверите да бисте се уверили наши
поинтер-- нисмо вратимо нула.

139
00:07:31,692 --> 00:07:33,650
Јер ако покушамо и
попустљивост нулл показивач,

140
00:07:33,650 --> 00:07:36,190
ћемо патити
сегфаулт и не желимо то.

141
00:07:36,190 --> 00:07:39,510
>> Затим желимо да попуните поље,
желимо да покрене поље Валуе

142
00:07:39,510 --> 00:07:41,690
и покрене следеће поље.

143
00:07:41,690 --> 00:07:45,450
А онда ми желимо да-- на крају као
Функција прототип индицатес-- желимо

144
00:07:45,450 --> 00:07:49,940
да се врати показивач на слл чвора.

145
00:07:49,940 --> 00:07:51,710
Дакле, оно што чини ово личи визуелно?

146
00:07:51,710 --> 00:07:55,230
Па, прво ћемо да динамички
доделити простор за нови слл чвора,

147
00:07:55,230 --> 00:07:58,320
тако да маллоц-- да је
визуелна представа

148
00:07:58,320 --> 00:08:00,020
чвора смо створили.

149
00:08:00,020 --> 00:08:02,757
И ми проверите да ли
није нулл-- у овом случају,

150
00:08:02,757 --> 00:08:04,840
слика не би имао
појавио ако је нула,

151
00:08:04,840 --> 00:08:07,298
ми би понестало меморије,
тако да смо добри да идем тамо.

152
00:08:07,298 --> 00:08:10,200
Дакле, сада смо на корак Ц,
покрене поље чворови вредности.

153
00:08:10,200 --> 00:08:12,280
Па, на основу ове функције
звати ја користим овде,

154
00:08:12,280 --> 00:08:16,700
Изгледа као да желим да прође у 6,
па ћу 6 на терену вредности.

155
00:08:16,700 --> 00:08:18,865
Сада, покрените следеће поље.

156
00:08:18,865 --> 00:08:21,640
Па, шта ћу тамо да ради,
не постоји ништа следећи, зар не,

157
00:08:21,640 --> 00:08:23,600
ово је једина ствар на листи.

158
00:08:23,600 --> 00:08:27,206
Дакле, шта је следећа ствар на листи?

159
00:08:27,206 --> 00:08:29,660
>> То не би требало да укаже на било шта, зар не.

160
00:08:29,660 --> 00:08:33,600
Нема ништа друго тамо, па шта је
концепт знамо да је нотхинг--

161
00:08:33,600 --> 00:08:35,638
показивачи на ништа?

162
00:08:35,638 --> 00:08:37,929
То би требало да буде можда желимо
тамо стави Нулл Поинтер,

163
00:08:37,929 --> 00:08:40,178
и ја ћу представљају нулл
поинтер као само црвену кутију,

164
00:08:40,178 --> 00:08:41,559
не можемо ићи даље.

165
00:08:41,559 --> 00:08:44,430
Као ћемо видети нешто касније,
ћемо морати евентуално ланце

166
00:08:44,430 --> 00:08:46,330
стрелица повезивање
Те тачке заједно,

167
00:08:46,330 --> 00:08:48,480
али када ударио
Ред Бок, то је нула,

168
00:08:48,480 --> 00:08:51,150
не можемо ићи даље,
то је крај листе.

169
00:08:51,150 --> 00:08:53,960
>> И на крају, ми само желимо да
вратити показивач на овом чвору.

170
00:08:53,960 --> 00:08:56,160
Дакле, ми ћемо га звати нова,
и вратиће нови

171
00:08:56,160 --> 00:08:59,370
тако да се може користити у
год функција је створио.

172
00:08:59,370 --> 00:09:03,100
Дакле, идемо, ми смо направили појединачно
линкед лист чвор из ведра неба,

173
00:09:03,100 --> 00:09:05,920
и сада имамо списак можемо радити са.

174
00:09:05,920 --> 00:09:08,260
>> Сада, да смо већ рекли
имају велики ланац,

175
00:09:08,260 --> 00:09:09,800
и желимо да пронађемо нешто у њој.

176
00:09:09,800 --> 00:09:12,716
И желимо функцију која се догађа
да се врате тачно или нетачно, зависно

177
00:09:12,716 --> 00:09:15,840
о томе да ли вредност постоји у тој листи.

178
00:09:15,840 --> 00:09:18,160
Функција прототип, или
декларација за ту функцију,

179
00:09:18,160 --> 00:09:23,320
може изгледати као ово-- боол наћи и
онда желимо да прође у два аргумента.

180
00:09:23,320 --> 00:09:26,996
>> Први је показивач на
први елемент повезане листе.

181
00:09:26,996 --> 00:09:29,620
Ово је заправо нешто што ћу
увек желе да пратите,

182
00:09:29,620 --> 00:09:33,110
и заправо може бити нешто што
чак ставити у глобалној променљивој.

183
00:09:33,110 --> 00:09:35,360
Када направите листу,
Увек, увек

184
00:09:35,360 --> 00:09:38,990
желите да пратите од самог
први елемент листе.

185
00:09:38,990 --> 00:09:43,690
На тај начин можете се односе на све остале
елементи за само након ланац,

186
00:09:43,690 --> 00:09:47,300
без потребе да задржи савете
нетакнута у сваком елементу.

187
00:09:47,300 --> 00:09:50,920
Потребно је само да пратите први
једна ако су сви у ланцима заједно.

188
00:09:50,920 --> 00:09:52,460
>> А онда друга ствар
Пролазимо поново

189
00:09:52,460 --> 00:09:54,376
је произвољно неке--
било које врсте података смо

190
00:09:54,376 --> 00:09:59,640
лоокинг фор постоји унутар
надам се да је један од чворова на листи.

191
00:09:59,640 --> 00:10:00,980
Дакле, шта су кораци?

192
00:10:00,980 --> 00:10:04,250
Па, прва ствар коју радимо је
стварамо трансверзалну показивач

193
00:10:04,250 --> 00:10:06,015
указујући на главу листе.

194
00:10:06,015 --> 00:10:08,890
Па, зашто ми то већ радимо
има показивач на челу листе,

195
00:10:08,890 --> 00:10:10,974
зашто не бисмо се помери за око?

196
00:10:10,974 --> 00:10:13,140
Па, као што сам рекао,
то је заиста важно за нас

197
00:10:13,140 --> 00:10:17,580
да увек водити евиденцију о
Први елемент у листи.

198
00:10:17,580 --> 00:10:21,270
И тако је заправо боље
да створи дупликат који,

199
00:10:21,270 --> 00:10:25,350
и користи га да се креће тако да нисмо
случајно се удаљи, или увек

200
00:10:25,350 --> 00:10:30,430
има показивач у неком тренутку који је
Право на први елемент листе.

201
00:10:30,430 --> 00:10:33,290
Тако да је боље да се створи
Други је да користимо за кретање.

202
00:10:33,290 --> 00:10:35,877
>> Онда смо само упоредити да ли
поље вредност у том чвору

203
00:10:35,877 --> 00:10:38,960
је оно што тражите, а ако је
Не, ми смо само прелазимо на следећи чвор.

204
00:10:38,960 --> 00:10:41,040
И чувамо то ради
више, и више, и више,

205
00:10:41,040 --> 00:10:44,811
док не нађемо било
елемент, или смо ударили

206
00:10:44,811 --> 00:10:47,310
нулл-- смо стигли до краја
листе и не постоји.

207
00:10:47,310 --> 00:10:50,540
Ово би требало да надамо се звони звоно
за вас као само линеарно претраживање,

208
00:10:50,540 --> 00:10:54,430
Само је реплицира у
појединачно повезана листа структура

209
00:10:54,430 --> 00:10:56,280
уместо да помоћу низа да то уради.

210
00:10:56,280 --> 00:10:58,210
>> Дакле, овде је пример
појединачно повезана листа.

211
00:10:58,210 --> 00:11:00,043
Ово се састоји од
пет чворова, и имамо

212
00:11:00,043 --> 00:11:04,330
показивач на шефа
листа, која се зове листа.

213
00:11:04,330 --> 00:11:07,385
Прва ствар коју желите да урадите је
опет, створили ту Траверсал показивач.

214
00:11:07,385 --> 00:11:09,760
Дакле, имамо сада два савете
које указују на исту ствар.

215
00:11:09,760 --> 00:11:15,025
>> Сада, приметите и овде, нисам
треба да Маллоц било простора за трав.

216
00:11:15,025 --> 00:11:18,970
Нисам рекао Трав једнака маллоц
нешто што чвор већ постоји,

217
00:11:18,970 --> 00:11:21,160
тај простор у меморији већ постоји.

218
00:11:21,160 --> 00:11:24,290
Тако да све што заправо радим је
стварајући још један показивач на њега.

219
00:11:24,290 --> 00:11:28,210
Нисам маллоцинг додатна
простор, само су сада две тројке

220
00:11:28,210 --> 00:11:31,370
указујући на исту ствар.

221
00:11:31,370 --> 00:11:33,710
>> Тако је 2 оно што тражим?

222
00:11:33,710 --> 00:11:37,220
Па, не, тако да уместо да сам
прећи на следећу.

223
00:11:37,220 --> 00:11:41,740
Дакле, у основи, рекао бих,
Трав Трав једнака следећи.

224
00:11:41,740 --> 00:11:43,630
Да ли је 3 оно што тражим, бр.

225
00:11:43,630 --> 00:11:45,780
Тако сам и даље ићи
кроз, док на крају

226
00:11:45,780 --> 00:11:48,690
дођете до 6 то је оно што тражим
за заснован на позива функције

227
00:11:48,690 --> 00:11:51,600
Имам на врху
тамо, па сам готов.

228
00:11:51,600 --> 00:11:54,150
>> Сада, шта ако елемент сам
лоокинг фор није на листи,

229
00:11:54,150 --> 00:11:55,510
да ли је и даље иде на посао?

230
00:11:55,510 --> 00:11:57,120
Па, приметити да листа
Овде је суптилно различит,

231
00:11:57,120 --> 00:11:59,410
и то је још једна ствар која је
важно са повезаним листама,

232
00:11:59,410 --> 00:12:01,780
не морате да сачувају
да у сваком конкретном циљу.

233
00:12:01,780 --> 00:12:05,390
Можете, ако желите, али
Можда сте већ приметили

234
00:12:05,390 --> 00:12:09,310
да нисмо праћење
Који број елеменат смо у.

235
00:12:09,310 --> 00:12:13,150
>> И то је нека врста једне трговине да
има са повезане листе стихови низове,

236
00:12:13,150 --> 00:12:15,300
је то што немамо
директног приступа више.

237
00:12:15,300 --> 00:12:18,150
Не можемо само рећи, хоћу
да иде на 0-тог елемента,

238
00:12:18,150 --> 00:12:21,410
или 6. елемент моје низа,
што могу да урадим у низу.

239
00:12:21,410 --> 00:12:25,080
Ја не могу да кажем да желим да одем до
0тх елемент, односно 6. елемент,

240
00:12:25,080 --> 00:12:30,360
или 25. елемент моје повезане листе,
нема индекс повезан са њима.

241
00:12:30,360 --> 00:12:33,660
И тако није битно
ако сачувамо нашу листу како.

242
00:12:33,660 --> 00:12:36,080
Ако желите да вас
Свакако, али постоји

243
00:12:36,080 --> 00:12:38,567
нема разлога зашто они треба да
бити очуван у било ком редоследу.

244
00:12:38,567 --> 00:12:40,400
Дакле, опет, хајде да пробамо и
финд 6 на овој листи.

245
00:12:40,400 --> 00:12:43,200
Па, ми почети на
почиње, не нађемо 6,

246
00:12:43,200 --> 00:12:47,690
а онда и даље не проналажење
6, док смо на крају доћи до овде.

247
00:12:47,690 --> 00:12:52,790
Дакле, сада Трав указује на чвору
садржи 8, а шест није унутра.

248
00:12:52,790 --> 00:12:55,250
>> Дакле, следећи корак би био
да иде на следећи показивача,

249
00:12:55,250 --> 00:12:57,440
тако рећи Трав Трав једнака следећи.

250
00:12:57,440 --> 00:13:00,750
Па, Трав следеће, указује
Тхе Ред Бок постоји, нулл.

251
00:13:00,750 --> 00:13:03,020
Дакле, нема где другде да
иди, па у овом тренутку

252
00:13:03,020 --> 00:13:06,120
можемо закључити да смо стигли
крај повезане листе,

253
00:13:06,120 --> 00:13:07,190
и 6 није унутра.

254
00:13:07,190 --> 00:13:10,980
И то ће бити враћена
лажна у овом случају.

255
00:13:10,980 --> 00:13:14,540
>> У реду, како да убаците нови
чвор у повезане листе?

256
00:13:14,540 --> 00:13:17,310
Тако смо били у стању да створи
повезане листе ниоткуда,

257
00:13:17,310 --> 00:13:19,370
али ми вероватно желите да
изгради ланац и не

258
00:13:19,370 --> 00:13:22,620
створити гомилу различитих спискова.

259
00:13:22,620 --> 00:13:25,700
Желимо да имамо један списак који
има гомилу чворова у њему,

260
00:13:25,700 --> 00:13:28,040
не гомила листе са једним чвором.

261
00:13:28,040 --> 00:13:31,260
Дакле, не можемо само наставите користећи Цреате
Функција смо дефинисали раније, сада

262
00:13:31,260 --> 00:13:33,860
желите да унесете у један
Листа која већ постоји.

263
00:13:33,860 --> 00:13:36,499
>> Дакле овом случају, идемо
да прође у два аргумента,

264
00:13:36,499 --> 00:13:39,290
показивач на главу да
повезане листе које желимо да додате.

265
00:13:39,290 --> 00:13:40,910
Опет, зато је тако
битно да смо увек

266
00:13:40,910 --> 00:13:43,400
пратити, јер
то је једини начин да стварно

267
00:13:43,400 --> 00:13:46,690
треба да се односи на цео списак
само од показивач на првог елемента.

268
00:13:46,690 --> 00:13:49,360
Дакле, желимо да прође у А
Поинтер на том првом елементу,

269
00:13:49,360 --> 00:13:52,226
и све вредности ми
желите да додате на листу.

270
00:13:52,226 --> 00:13:54,600
И на крају ова функција
ће вратити показивач

271
00:13:54,600 --> 00:13:57,980
до новог шефа повезане листе.

272
00:13:57,980 --> 00:13:59,700
>> Који су кораци укључени овде?

273
00:13:59,700 --> 00:14:02,249
Па, баш као са стварају,
морамо да динамички додели

274
00:14:02,249 --> 00:14:05,540
простор за нови чвор, и проверите да
Сигурно да не понестане меморије, опет,

275
00:14:05,540 --> 00:14:07,150
јер ми користимо маллоц.

276
00:14:07,150 --> 00:14:09,080
Затим желимо да уведемо
и убаците чвор,

277
00:14:09,080 --> 00:14:12,730
тако да је број, како год
Вал је, у чвор.

278
00:14:12,730 --> 00:14:17,310
Желимо да убаците у чвор
почетак повезане листе.

279
00:14:17,310 --> 00:14:19,619
>> Постоји разлог што сам
желим ово да радим, и то

280
00:14:19,619 --> 00:14:21,910
можда вреди мало
за паузирање видео овде,

281
00:14:21,910 --> 00:14:25,860
и мислим о томе зашто бих желео да
убаците на почетку повезан

282
00:14:25,860 --> 00:14:26,589
листа.

283
00:14:26,589 --> 00:14:28,630
Опет, што сам раније поменуо
да се то заправо не

284
00:14:28,630 --> 00:14:33,020
битно да смо га сачувати у једном
ред, па можда то је траг.

285
00:14:33,020 --> 00:14:36,040
И видели сте шта би се десило ако бисмо
Хтео да-- или само секунд

286
00:14:36,040 --> 00:14:37,360
пре када смо ишли
кроз потрази сте

287
00:14:37,360 --> 00:14:39,235
могао да види шта би могло
догодити ако смо покушавали

288
00:14:39,235 --> 00:14:41,330
за уметање на крају листе.

289
00:14:41,330 --> 00:14:44,750
Зато што немам
поинтер на крај листе.

290
00:14:44,750 --> 00:14:47,490
>> Дакле, разлог због којег бих желео
да убаците на почетку,

291
00:14:47,490 --> 00:14:49,380
је зато што може да уради одмах.

292
00:14:49,380 --> 00:14:52,730
Имам показивач на почетку, и
ћемо видети у визуелни у секунди.

293
00:14:52,730 --> 00:14:55,605
Али, ако желим да убаците на крају,
Морам да кренемо од почетка,

294
00:14:55,605 --> 00:14:58,760
пролазе скроз до
крај, а затим га тацк на.

295
00:14:58,760 --> 00:15:01,420
Дакле, то би значило да
уметање на крају листе

296
00:15:01,420 --> 00:15:04,140
би постао О од н
рад, враћам

297
00:15:04,140 --> 00:15:06,720
на нашој дискусији о
рачунарска комплексност.

298
00:15:06,720 --> 00:15:10,140
То би постао О од н операције, гдје
као списак добио већи, и већи,

299
00:15:10,140 --> 00:15:13,310
и већи, то ће постати све више и
теже да се осуши нешто

300
00:15:13,310 --> 00:15:14,661
на на крају.

301
00:15:14,661 --> 00:15:17,410
Али увек је стварно лако да
тацк нешто на на почетку,

302
00:15:17,410 --> 00:15:19,060
ти си увек на почетку.

303
00:15:19,060 --> 00:15:21,620
>> А видећемо визуелни ово поново.

304
00:15:21,620 --> 00:15:24,100
И онда кад смо урадили, једном
смо убаци нови чвор,

305
00:15:24,100 --> 00:15:26,880
желимо да се врати нашу показивач на
нови шеф повезане листе, која

306
00:15:26,880 --> 00:15:29,213
јер смо убацивање На
почетком, заправо ће бити

307
00:15:29,213 --> 00:15:31,060
показивач на чвор смо управо креирали.

308
00:15:31,060 --> 00:15:33,280
Хајде да визуализују ово,
јер мислим да ће помоћи.

309
00:15:33,280 --> 00:15:36,661
>> Дакле, овде је наша листа, састоји се од
четири елемента, чвор који садржи 15,

310
00:15:36,661 --> 00:15:38,410
што указује на чвор
садрже 9, која

311
00:15:38,410 --> 00:15:41,370
указује на чвор који садржи 13,
што указује на чвор који садржи

312
00:15:41,370 --> 00:15:44,840
10, која има нулти
показивач као следећем показивач

313
00:15:44,840 --> 00:15:47,010
тако да је крај листе.

314
00:15:47,010 --> 00:15:50,200
Дакле, желимо да уметање
нови чвор са вредношћу 12

315
00:15:50,200 --> 00:15:52,720
на почетку овог
Листа, шта да радимо?

316
00:15:52,720 --> 00:15:58,770
Па, прво маллоц простор за
чвор, а онда пут 12 унутра.

317
00:15:58,770 --> 00:16:02,211
>> Дакле, сада смо достигли
Одлука поента, зар не?

318
00:16:02,211 --> 00:16:03,960
Имамо пар
показивачи да смо могли

319
00:16:03,960 --> 00:16:06,770
селе, као што би требало да први корак?

320
00:16:06,770 --> 00:16:09,250
Ако правимо 12 поен у
нови шеф лист--

321
00:16:09,250 --> 00:16:13,020
или извините, треба да правимо 12
указују на старом носилац листе?

322
00:16:13,020 --> 00:16:15,319
Или да кажемо да је
Листа сада почиње у 12.

323
00:16:15,319 --> 00:16:17,110
Ту је разлика
тамо, а ми ћемо гледати

324
00:16:17,110 --> 00:16:19,870
шта се дешава са оба у секунди.

325
00:16:19,870 --> 00:16:23,350
>> Али ово доводи до
велика тема за сидебар,

326
00:16:23,350 --> 00:16:26,280
а то је да једна од
најтежих ствари са повезаним листама

327
00:16:26,280 --> 00:16:30,980
се договорити за савете
у исправном редоследу.

328
00:16:30,980 --> 00:16:34,520
Ако преместите ствари из реда,
можете завршити случајно

329
00:16:34,520 --> 00:16:36,050
орпханинг остатак листе.

330
00:16:36,050 --> 00:16:37,300
И ево примера за то.

331
00:16:37,300 --> 00:16:40,540
Дакле, идемо са идејом од--
Па, управо смо створили 12.

332
00:16:40,540 --> 00:16:43,180
Знамо да 12 ће бити
нови носилац листе,

333
00:16:43,180 --> 00:16:47,660
па зашто не бисмо само померите
листа показивач на ту укаже.

334
00:16:47,660 --> 00:16:49,070
>> У реду, то је добро.

335
00:16:49,070 --> 00:16:51,560
Дакле, сада гдје се 12 следећу тачку?

336
00:16:51,560 --> 00:16:54,580
Мислим, визуелно можемо да видимо
да ће указати на 15,

337
00:16:54,580 --> 00:16:57,250
као људи стварно је очигледно за нас.

338
00:16:57,250 --> 00:17:00,300
Како компјутер зна?

339
00:17:00,300 --> 00:17:02,720
Ми немамо ништа
указујући на 15 више, зар не?

340
00:17:02,720 --> 00:17:05,869
>> Изгубили смо сваку могућност да се обрати 15.

341
00:17:05,869 --> 00:17:11,460
Не можемо рећи да нова стрелицу поред једнаки
нешто, тамо нема ништа.

342
00:17:11,460 --> 00:17:13,510
У ствари, ми смо сироче
остатак листе

343
00:17:13,510 --> 00:17:16,465
на тај начин, ми смо
случајно пробили ланац.

344
00:17:16,465 --> 00:17:18,089
А ми сигурно не желим то да урадим.

345
00:17:18,089 --> 00:17:20,000
>> Дакле, хајде да се вратимо и покушајте поново.

346
00:17:20,000 --> 00:17:24,060
Можда је права ствар
је да постави 12 је следећи показивач

347
00:17:24,060 --> 00:17:28,290
старом носилац листе првог,
онда можемо да пређемо преко листе.

348
00:17:28,290 --> 00:17:30,420
У ствари, то је
тачно да бисмо

349
00:17:30,420 --> 00:17:32,836
треба да прати кад смо
рад са појединачно повезане листе.

350
00:17:32,836 --> 00:17:36,460
Ми смо увек желе прикључити
нови елемент у листи,

351
00:17:36,460 --> 00:17:41,010
пре него што се такав
значајан корак промене

352
00:17:41,010 --> 00:17:43,360
где је шеф повезане листе је.

353
00:17:43,360 --> 00:17:46,740
Опет, то је тако основна ствар,
не желимо да изгубимо траг о томе.

354
00:17:46,740 --> 00:17:49,310
>> Зато желимо да се уверите да
све је окован заједно,

355
00:17:49,310 --> 00:17:52,040
пре него што кренемо да показивач.

356
00:17:52,040 --> 00:17:55,300
И то би био исправан поредак,
што је за повезивање 12 на листу,

357
00:17:55,300 --> 00:17:57,630
онда рећи да је листа покреће 12.

358
00:17:57,630 --> 00:18:00,860
Ако смо рекли списак почиње у 12 и
Онда је покушао да се повеже на листу 12,

359
00:18:00,860 --> 00:18:02,193
смо већ видели шта се дешава.

360
00:18:02,193 --> 00:18:04,920
Губимо списак грешком.

361
00:18:04,920 --> 00:18:06,740
>> У реду, тако да још једну ствар да разговарамо.

362
00:18:06,740 --> 00:18:09,750
Шта ако желимо да се ослободимо
цео повезана листу одједном?

363
00:18:09,750 --> 00:18:11,750
Опет, ми маллоцинг
све ово простор, па смо

364
00:18:11,750 --> 00:18:13,351
треба да га ослободе, када смо завршили.

365
00:18:13,351 --> 00:18:15,350
Тако да сада желите да избришете
цела повезана листа.

366
00:18:15,350 --> 00:18:16,850
Па, шта желимо да урадимо?

367
00:18:16,850 --> 00:18:20,460
>> Ако смо стигли до Нулл Поинтер, ми
Желим да престане, иначе, само брисање

368
00:18:20,460 --> 00:18:23,420
остатак листе, а затим ме ослободи.

369
00:18:23,420 --> 00:18:28,890
Обришите остатак листе,
а затим ослободи тренутни чвор.

370
00:18:28,890 --> 00:18:32,850
Шта то звучи као,
оно технику имамо разговарали

371
00:18:32,850 --> 00:18:35,440
о претходно вам то звучи?

372
00:18:35,440 --> 00:18:39,560
Обриши све друго, онда
врати и брисање ме.

373
00:18:39,560 --> 00:18:42,380
>> То је рецурсион смо извршена
Проблем мало мања,

374
00:18:42,380 --> 00:18:46,910
говоримо обрисати све
друго, онда можете да ме избрисати.

375
00:18:46,910 --> 00:18:50,940
И даље низ пут, тај чвор
ће рећи, избрисати све друго.

376
00:18:50,940 --> 00:18:53,940
Али на крају ћемо се до
тачка у којој је листа нулл,

377
00:18:53,940 --> 00:18:55,310
и то је наш основни случај.

378
00:18:55,310 --> 00:18:57,010
>> Дакле, хајде да погледамо ово,
и како то може радити.

379
00:18:57,010 --> 00:18:59,759
Дакле, овде је наша листа, то је иста
лист смо причали,

380
00:18:59,759 --> 00:19:00,980
а ту су и кораци.

381
00:19:00,980 --> 00:19:04,200
Има пуно текста овде, али
надамо се визуелизација ће помоћи.

382
00:19:04,200 --> 00:19:08,557
>> Тако смо бих-- и такође сам извукао
до нашег стек фрамес илустрација

383
00:19:08,557 --> 00:19:10,890
из наше видео на гомиле позива,
и надамо се све ово

384
00:19:10,890 --> 00:19:13,260
заједно ће вам показати шта се дешава.

385
00:19:13,260 --> 00:19:14,510
Дакле, овде је наш Псеудокод број.

386
00:19:14,510 --> 00:19:17,830
Ако се постигне нулл
показивач, стоп, у супротном,

387
00:19:17,830 --> 00:19:21,320
обришите остатак листе,
онда ослободи тренутни чвор.

388
00:19:21,320 --> 00:19:25,700
Тако сада, лист--
показивач да смо

389
00:19:25,700 --> 00:19:28,410
пролази да уништи поена за 12.

390
00:19:28,410 --> 00:19:33,340
12 није Нулл Поинтер, тако да смо
ће обрисати остатак листе.

391
00:19:33,340 --> 00:19:35,450
>> Шта је брисања
остали укључени?

392
00:19:35,450 --> 00:19:37,950
Па, то значи чинећи
позове да уништи, рекавши

393
00:19:37,950 --> 00:19:42,060
да 15 је на почетку
Остатак листе желимо да уништимо.

394
00:19:42,060 --> 00:19:47,480
И тако је позив да се уништи
12 је некако на чекању.

395
00:19:47,480 --> 00:19:52,690
То је било замрзнуто, чекајући да се
позове да уништи 15, да заврши свој посао.

396
00:19:52,690 --> 00:19:56,280
>> Па, 15 није Нулл Поинтер, и
тако да ће рећи, у реду,

397
00:19:56,280 --> 00:19:58,450
добро, избришите остатак листе.

398
00:19:58,450 --> 00:20:00,760
Остатак листе почиње
у 9, па само ћемо

399
00:20:00,760 --> 00:20:04,514
сачекајте док не избришете све то
ствари, онда се врати и брисање ме.

400
00:20:04,514 --> 00:20:06,680
Па 9 ће рећи, добро,
Ја нисам Нулл Поинтер,

401
00:20:06,680 --> 00:20:09,020
па обрисати остатак листе одавде.

402
00:20:09,020 --> 00:20:11,805
И тако покушати да униште 13.

403
00:20:11,805 --> 00:20:15,550
13 каже, нисам Нулл Поинтер,
иста ствар, она пролази долар.

404
00:20:15,550 --> 00:20:17,930
10 није Нулл Поинтер, 10
садржи Нулл Поинтер,

405
00:20:17,930 --> 00:20:20,200
али 10 није само по себи
Нулл Поинтер сада,

406
00:20:20,200 --> 00:20:22,470
па испуњава неке превише на долар.

407
00:20:22,470 --> 00:20:25,560
>> И сад лист бодова ето,
Заиста би указивало на неке--

408
00:20:25,560 --> 00:20:28,710
кад бих имао више простора у слици,
то би указивало на неки случајних простора

409
00:20:28,710 --> 00:20:29,960
да ми не знамо шта је то.

410
00:20:29,960 --> 00:20:34,680
То је нула показивач ипак, листа
се буквално сада постављен је вредност нулл.

411
00:20:34,680 --> 00:20:36,820
То је у реду показује у тој црвеној кутији.

412
00:20:36,820 --> 00:20:39,960
Постигли смо Нулл Поинтер, тако
можемо зауставити, и готови смо.

413
00:20:39,960 --> 00:20:46,230
>> И то љубичаста оквир је сада-- На
врх стацк-- да је активна оквир,

414
00:20:46,230 --> 00:20:47,017
али се то ради.

415
00:20:47,017 --> 00:20:48,600
Ако смо дошли до Нулл Поинтер, стоп.

416
00:20:48,600 --> 00:20:51,290
Ми не радимо ништа, ми
не може ослободити нулл показивач,

417
00:20:51,290 --> 00:20:55,070
нисмо маллоц било
простор, па смо урадили.

418
00:20:55,070 --> 00:20:57,590
Дакле, ту функцију оквира
је уништена, а ми

419
00:20:57,590 --> 00:21:00,930
ресуме-- смо покупили где смо стали
офф са следећим највећом један, која

420
00:21:00,930 --> 00:21:02,807
ово тамно плаве оквир овде.

421
00:21:02,807 --> 00:21:04,390
Тако смо покупили тамо где смо стали.

422
00:21:04,390 --> 00:21:06,598
Ми избрисан остатка
Листа већ, па сад смо

423
00:21:06,598 --> 00:21:08,000
ће ослободити тренутне чворова.

424
00:21:08,000 --> 00:21:12,920
Сада можемо да ослободимо овај чвор, и сада
смо стигли до краја функције.

425
00:21:12,920 --> 00:21:16,810
И тако да се функција оквир је уништен,
и ми покупити на светло плавој.

426
00:21:16,810 --> 00:21:20,650
>> Тако да рекао-- сам већ доне--
брисање остатак листе, тако

427
00:21:20,650 --> 00:21:23,140
ослободи тренутни чвор.

428
00:21:23,140 --> 00:21:26,520
И сада добија жути оквир је
назад на врх гомиле.

429
00:21:26,520 --> 00:21:29,655
И тако, као што видите, сада смо
уништавање листу са десна на лево.

430
00:21:29,655 --> 00:21:33,710

431
00:21:33,710 --> 00:21:37,280
>> Шта би се догодило, међутим,
Ако смо урадили ствари на погрешан начин?

432
00:21:37,280 --> 00:21:39,410
Као када смо покушали
да додате елемент.

433
00:21:39,410 --> 00:21:41,909
Ако забрљао ланац, ако
нисмо повезали показивачи

434
00:21:41,909 --> 00:21:44,690
у исправном редоследу, ако
Управо ослобођен први елемент,

435
00:21:44,690 --> 00:21:47,420
ако смо је ослободио
носилац листе, сада

436
00:21:47,420 --> 00:21:49,642
Нема начина да се позива на
остатак листе.

437
00:21:49,642 --> 00:21:51,350
И тако бисмо имали
сироче све,

438
00:21:51,350 --> 00:21:53,880
имали бисмо шта је
назива цурење меморије.

439
00:21:53,880 --> 00:21:56,800
Ако се сећате из наше видео
на динамичког додељивања меморије,

440
00:21:56,800 --> 00:21:58,650
то није веома добра ствар.

441
00:21:58,650 --> 00:22:00,810
>> Дакле, као што сам рекао, тамо
неколико операција

442
00:22:00,810 --> 00:22:04,010
да морамо да користимо за рад
са ефикасно повезани листу.

443
00:22:04,010 --> 00:22:08,430
А можда сте приметили сам пропустио један,
брисање један елемент са повезаног

444
00:22:08,430 --> 00:22:09,064
листа.

445
00:22:09,064 --> 00:22:10,980
Разлог зашто сам то урадио
је то у ствари нека врста

446
00:22:10,980 --> 00:22:14,360
Трицки да размишљају о томе како да избришете
један елемент из А појединачно

447
00:22:14,360 --> 00:22:15,600
линкед лист.

448
00:22:15,600 --> 00:22:19,950
Морамо бити у стању да прескочим
нешто на листи, која

449
00:22:19,950 --> 00:22:22,975
значи да се до поента ве
желите да избришете ову ноде--

450
00:22:22,975 --> 00:22:25,350
али како да се направи тако да смо
не губи било какву информацију,

451
00:22:25,350 --> 00:22:30,530
морамо повезати ово
чвор овде, овде.

452
00:22:30,530 --> 00:22:33,390
>> Тако да сам вероватно урадио погрешно
из визуелне перспективе.

453
00:22:33,390 --> 00:22:36,830
Дакле, ми смо на почетку нашег
Листа, ми смо одвија кроз,

454
00:22:36,830 --> 00:22:40,510
желимо да обришете овај чвор.

455
00:22:40,510 --> 00:22:43,440
Ако смо га избрисати,
смо пробили ланац.

456
00:22:43,440 --> 00:22:45,950
Овај чвор овде
односи се на све друго,

457
00:22:45,950 --> 00:22:48,260
садржи ланац од сада па надаље.

458
00:22:48,260 --> 00:22:51,190
>> Дакле, оно што треба да урадите ствари
након што дођемо до ове тачке,

459
00:22:51,190 --> 00:22:56,670
је морамо да вратимо корак један, и
повезати овај чвор на ову чвора,

460
00:22:56,670 --> 00:22:58,590
па онда можете брисати
онај у средини.

461
00:22:58,590 --> 00:23:02,120
Али појединачно повезане листе не
пружају нам пут да се врати назад.

462
00:23:02,120 --> 00:23:05,160
Зато морамо да их задржите
два показивачи, и да их

463
00:23:05,160 --> 00:23:09,527
врста офф корак, један иза
другима као идемо, или дођете до тачке

464
00:23:09,527 --> 00:23:11,110
а затим послати још један показивач преко.

465
00:23:11,110 --> 00:23:13,150
И као што можете видети, то
може добити мало неуредан.

466
00:23:13,150 --> 00:23:15,360
Срећом, имамо
још један начин да се то реши,

467
00:23:15,360 --> 00:23:17,810
када говоримо о двоструко повезане листе.

468
00:23:17,810 --> 00:23:20,720
>> Ја сам Доуг Ллоид, ово је ЦС50.

469
00:23:20,720 --> 00:23:22,298