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
>> Даг Lloyd: ОК, так што ў
гэтая кропка ў працэсе,

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, гэта магло б
быць 1000, гэта магло б

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
стварыць новыя дадзеныя structure-- A
односвязанны спіс мы маглі б say--

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
вузлы проста быць абстрактнай term--
гэта проста тое, што я тэлефаную

56
00:03:08,559 --> 00:03:10,350
гэта свайго роду
Структура, у асноўным, я?

57
00:03:10,350 --> 00:03:16,190
Проста буду называць яго node-- і гэта
вузел мае двух членаў, ці два поля.

58
00:03:16,190 --> 00:03:20,300
Ён мае дадзеныя, звычайна
лік, лік з якая плавае кропкай характар,

59
00:03:20,300 --> 00:03:23,790
ці можа быць некаторым іншым тыпам дадзеных,
што вы вызначыліся з тыпам DEF.

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
Ну, калі вы памятаеце з нашага відэа на
вызначэнне карыстацкіх тыпаў, з тыпу DEF,

70
00:04:01,120 --> 00:04:05,400
мы можам вызначыць structure-- і
увядзіце вызначыць структуру, як гэта.

71
00:04:05,400 --> 00:04:11,240
tyepdef структуры sllist, а затым я
выкарыстоўваючы значэнне слова тут адвольна

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

82
00:04:43,030 --> 00:04:47,450
але я не магу выкарыстоўваць SLL вузел
ў сярэдзіне гэтага.

83
00:04:47,450 --> 00:04:51,430
Прычына ў тым, я не
стварыў тып завецца SLL вузел

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
Гэта, S тып дадзеных з
Структура, якая змяшчае дадзеныя,

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
так даючы яму часовае
Імя структуры sllist

91
00:05:14,910 --> 00:05:18,540
дазваляе мне сказаць, то я хачу
паказальнік на іншай структуры sllist,

92
00:05:18,540 --> 00:05:24,690
на структуру sllist зорка, а затым
пасля таго як я завяршыў вызначэнне,

93
00:05:24,690 --> 00:05:27,220
Цяпер я магу назваць гэты тып SLL вузел.

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
Было б проста сказаць TYPEDEF-структуру,
адкрыць фігурную дужку, а затым вызначыць яго.

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
а SLL вузлоў для мэт
у астатняй частцы гэтага відэа.

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

128
00:07:01,690 --> 00:07:05,530
тып зноў, некаторага адвольнага тыпу дадзеных.

129
00:07:05,530 --> 00:07:10,482
Але я returning-- гэтую функцыю варта
вярнуцца да мяне паказальнік, каб аднакратна

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

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
А потым мы хочам, мэтай якіх у канчатковым выніку, як
Прататып функцыі indicates-- мы хочам

144
00:07:45,450 --> 00:07:49,940
вярнуць паказальнік на SLL вузла.

145
00:07:49,940 --> 00:07:51,710
Так што зрабіць гэта выглядаць візуальна?

146
00:07:51,710 --> 00:07:55,230
Ну, па-першае, мы збіраемся, каб дынамічна
вылучыць месца для новага вузла SLL,

147
00:07:55,230 --> 00:07:58,320
такім чынам, мы malloc-- гэта
візуальнае прадстаўленне

148
00:07:58,320 --> 00:08:00,020
вузла мы толькі што стварылі.

149
00:08:00,020 --> 00:08:02,757
І мы правяраем, каб пераканацца,
гэта не null-- ў гэтым выпадку,

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
Там няма нічога іншага, там, так што
канцэпцыя мы ведаем, што гэта nothing--

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

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
адвольна some--
незалежна ад тыпу дадзеных мы

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
null-- мы дасягнулі канца
спісу, і гэта не было.

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

216
00:11:15,025 --> 00:11:18,970
Я не кажу, Trav роўная Таноса
тое, што вузел ўжо існуе,

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

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
Так у асноўным, я б сказаў,
Траў роўная TRAV побач.

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
Так што цяпер Trav паказвае на вузел
які змяшчае 8, а шэсць не там.

248
00:12:52,790 --> 00:12:55,250
>> Так што наступны крок будзе
каб перайсці да наступнага паказальніку,

249
00:12:55,250 --> 00:12:57,440
так бы мовіць, Trav роўная TRAV побач.

250
00:12:57,440 --> 00:13:00,750
Ну, Trav побач, паказана
чырвоны каробка ёсць, з'яўляецца несапраўдным.

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 пункт
новы кіраўнік list--

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
Такім чынам, давайце з ідэяй of--
Ну, мы толькі што стварылі 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
Зноў жа, мы mallocing
Усё гэта прастору, і таму мы

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
>> Такім чынам, мы have-- і я таксама выцягнуў
да нашай кадраў стэка ілюстрацыі

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
Так што цяпер, list--
паказальнік, што мы

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 не само па сабе з'яўляецца
NULL паказальнік прама цяпер,

406
00:20:20,200 --> 00:20:22,470
і так яна праходзіць даляр таксама.

407
00:20:22,470 --> 00:20:25,560
>> А цяпер спіс кропак там, гэта
сапраўды будзе паказваць на some--

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
>> І так, што фіялетавы кадра now-- на
Верх stack-- гэта актыўны кадр,

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

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
>> Так што says-- я ўжо done--
выдаленне астатняй частцы спісу, так

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
азначае, што мы атрымліваем у point-- мы
хочаце выдаліць гэты node--

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
>> Я Дуг Лойд, гэта CS50.

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