1
00:00:07,260 --> 00:00:10,050
[Powered by Google Translate] У праграмаванні, мы часта павінны падаваць спісы значэнняў,

2
00:00:10,050 --> 00:00:12,840
такія як імёны студэнтаў у раздзеле

3
00:00:12,840 --> 00:00:15,100
або іх вынікі на апошняй віктарыны.

4
00:00:15,100 --> 00:00:17,430
>> У мове C, заявіў масівы могуць быць выкарыстаны

5
00:00:17,430 --> 00:00:19,160
для захоўвання спісаў.

6
00:00:19,160 --> 00:00:21,200
Лёгка пералічыць элементы спісу

7
00:00:21,200 --> 00:00:23,390
захоўваюцца ў масіве, і калі вам трэба атрымаць доступ

8
00:00:23,390 --> 00:00:25,050
ці змяніць га элемента спісу

9
00:00:25,050 --> 00:00:27,570
для некаторага адвольнага індэкса I,

10
00:00:27,570 --> 00:00:29,910
што можа быць зроблена ў пастаянным часу,

11
00:00:29,910 --> 00:00:31,660
але масівы маюць недахопы.

12
00:00:31,660 --> 00:00:33,850
>> Калі мы аб'явім іх, мы абавязаны сказаць,

13
00:00:33,850 --> 00:00:35,900
фронт, як яны вялікія,

14
00:00:35,900 --> 00:00:38,160
гэта значыць, колькі элементаў яны могуць захоўваць

15
00:00:38,160 --> 00:00:40,780
і наколькі вялікі гэтыя элементы, якія вызначаюцца іх тыпам.

16
00:00:40,780 --> 00:00:45,450
Напрыклад, унутр обр (10)

17
00:00:45,450 --> 00:00:48,220
можа захоўваць 10 пунктаў

18
00:00:48,220 --> 00:00:50,200
, Якія з'яўляюцца памер Int.

19
00:00:50,200 --> 00:00:52,590
>> Мы не можам змяніць памер масіва пасля дэкларацыі.

20
00:00:52,590 --> 00:00:55,290
Мы павінны стварыць новы масіў, калі мы хочам захаваць некалькі элементаў.

21
00:00:55,290 --> 00:00:57,410
Прычына гэтага абмежаванні ў тым, што існуе наша

22
00:00:57,410 --> 00:00:59,040
Праграма захоўвае ўвесь масіў

23
00:00:59,040 --> 00:01:02,310
як бесперапынны кавалак памяці.

24
00:01:02,310 --> 00:01:04,500
Кажуць, што гэта буфер, дзе мы захоўвалі ў нашым масіве.

25
00:01:04,500 --> 00:01:06,910
Там могуць быць і іншыя зменныя

26
00:01:06,910 --> 00:01:08,310
размешчаны ў непасрэднай блізкасці да масіву

27
00:01:08,310 --> 00:01:10,060
ў памяці, таму мы не можам

28
00:01:10,060 --> 00:01:12,060
проста зрабіць масіва больш.

29
00:01:12,060 --> 00:01:15,700
>> Часам мы хацелі б гандляваць хуткі доступ да дадзеных масіва хуткасці

30
00:01:15,700 --> 00:01:17,650
для трохі больш гнуткасці.

31
00:01:17,650 --> 00:01:20,380
Калі ласка, увядзіце звязаны спіс, іншая асноўная структура дадзеных

32
00:01:20,380 --> 00:01:22,360
Вы можа быць не так добра знаёмыя.

33
00:01:22,360 --> 00:01:24,200
На высокім узроўні,

34
00:01:24,200 --> 00:01:26,840
Звязаны спіс захоўвае дадзеныя ў паслядоўнасць вузлоў

35
00:01:26,840 --> 00:01:29,280
, Якія звязаны адзін з адным спасылкамі,

36
00:01:29,280 --> 00:01:31,760
адсюль і назва «звязаны спіс.

37
00:01:31,760 --> 00:01:33,840
Як мы ўбачым, гэтая розніца ў дызайне

38
00:01:33,840 --> 00:01:35,500
прыводзіць да розных перавагі і недахопы

39
00:01:35,500 --> 00:01:37,000
чым масіў.

40
00:01:37,000 --> 00:01:39,840
>> Вось код C па вельмі просты звязаны спіс цэлых лікаў.

41
00:01:39,840 --> 00:01:42,190
Вы бачыце, што мы ўяўляем кожнаму вузлу

42
00:01:42,190 --> 00:01:45,520
У спісе, як структура, якая утрымоўвае 2 рэчы,

43
00:01:45,520 --> 00:01:47,280
цэлае для захоўвання пад назвай «Вал»

44
00:01:47,280 --> 00:01:50,460
і спасылку на наступны вузел у спісе

45
00:01:50,460 --> 00:01:52,990
, Якія мы прадстаўляем у якасці паказальніка называецца "Далей".

46
00:01:54,120 --> 00:01:56,780
Такім чынам, мы можам адсачыць увесь спіс

47
00:01:56,780 --> 00:01:58,790
з дапамогай ўсяго аднаго паказальніка на вузле 1,

48
00:01:58,790 --> 00:02:01,270
і тады мы зможам выканаць наступныя паказальнікі

49
00:02:01,270 --> 00:02:03,130
на 2-й вузел,

50
00:02:03,130 --> 00:02:05,280
да 3-га вузлу,

51
00:02:05,280 --> 00:02:07,000
да 4-га вузлу,

52
00:02:07,000 --> 00:02:09,889
і гэтак далей, пакуль мы не атрымаем да канца спісу.

53
00:02:10,520 --> 00:02:12,210
>> Вы маглі б глядзець 1 Перавага гэтага ёсць

54
00:02:12,210 --> 00:02:14,490
на статычную структуру масіва - з звязанага спісу,

55
00:02:14,490 --> 00:02:16,450
нам не трэба вялікі кавалак памяці ў цэлым.

56
00:02:17,400 --> 00:02:20,530
Першы вузел спісу маглі б жыць на гэтым месцы ў памяці,

57
00:02:20,530 --> 00:02:23,160
і 2-га вузла можа быць на ўсім шляху сюды.

58
00:02:23,160 --> 00:02:25,780
Мы можам дабрацца да ўсіх вузлоў, незалежна ад таго, дзе ў памяці яны ёсць,

59
00:02:25,780 --> 00:02:28,890
таму што, пачынаючы з першага вузла, наступнага паказальніка кожнага вузла

60
00:02:28,890 --> 00:02:31,700
кажа нам дакладна, куды ісці далей.

61
00:02:31,700 --> 00:02:33,670
>> Акрамя таго, мы не павінны гаварыць фронт

62
00:02:33,670 --> 00:02:36,740
наколькі вялікі звязаны спіс будзе так, як мы робім з статычныя масівы,

63
00:02:36,740 --> 00:02:39,060
так як мы можам працягваць дадаваць вузлы ў спіс

64
00:02:39,060 --> 00:02:42,600
тых часоў, пакуль ёсць вольнае месца дзесьці ў памяці для новых вузлоў.

65
00:02:42,600 --> 00:02:45,370
Таму, звязаных спісаў можна лёгка змяніць памер дынамічна.

66
00:02:45,370 --> 00:02:47,950
Скажам, пазней у праграме, нам трэба дадаць некалькі вузлоў

67
00:02:47,950 --> 00:02:49,350
у нашым спісе.

68
00:02:49,350 --> 00:02:51,480
Для ўстаўкі новага вузла ў нашым спісе на лета,

69
00:02:51,480 --> 00:02:53,740
усё, што нам трэба зрабіць, гэта вылучыць памяць для гэтага вузла,

70
00:02:53,740 --> 00:02:55,630
пляснуць у значэнні дадзеных,

71
00:02:55,630 --> 00:02:59,070
, А затым змясціць яго там, дзе мы хочам шляхам карэкціроўкі адпаведных паказальнікаў.

72
00:02:59,070 --> 00:03:02,310
>> Напрыклад, калі мы хочам размясціць вузел паміж

73
00:03:02,310 --> 00:03:04,020
2-й і 3-й вузлы спісу,

74
00:03:04,020 --> 00:03:06,800
 Мы не павінны былі б рухацца 2-й або 3. Вузлы на ўсіх.

75
00:03:06,800 --> 00:03:09,190
Сказаць, што мы чырвоныя ўстаўкі гэтых вузлоў.

76
00:03:09,190 --> 00:03:12,890
Усё, што мы павінны былі б зрабіць, гэта ўсталяваць наступны паказальнік новага вузла

77
00:03:12,890 --> 00:03:14,870
паказваць на 3-м вузле

78
00:03:14,870 --> 00:03:18,580
, А затым перамантаваць наступны паказальнік 2-га вузла

79
00:03:18,580 --> 00:03:20,980
паказваюць на нашым новым вузле.

80
00:03:22,340 --> 00:03:24,370
Такім чынам, мы можам змяніць памер нашых спісаў на лета

81
00:03:24,370 --> 00:03:26,090
З нашага кампутара не спадзявацца на індэксацыю,

82
00:03:26,090 --> 00:03:28,990
а на сувязі з дапамогай паказальнікаў для іх захоўвання.

83
00:03:29,120 --> 00:03:31,600
>> Тым не менш, недахоп звязаныя спісы

84
00:03:31,600 --> 00:03:33,370
з'яўляецца тое, што, у адрозненне ад статычнага масіва,

85
00:03:33,370 --> 00:03:36,690
Кампутар не можа проста скокнуць у сярэдзіну спісу.

86
00:03:38,040 --> 00:03:40,780
Так як кампутар павінен наведаць кожны вузел у звязаным спісе

87
00:03:40,780 --> 00:03:42,330
каб дабрацца да наступнага,

88
00:03:42,330 --> 00:03:44,770
гэта зойме больш часу, каб знайсці пэўны вузел

89
00:03:44,770 --> 00:03:46,400
чым гэта было б у масіве.

90
00:03:46,400 --> 00:03:48,660
Каб прайсці ўвесь спіс займае час, прапарцыйнае

91
00:03:48,660 --> 00:03:50,580
да даўжыні спісу,

92
00:03:50,580 --> 00:03:54,630
або O (N) у асімптатычнай наймення.

93
00:03:54,630 --> 00:03:56,510
У сярэднім, дасягнуўшы любога вузла

94
00:03:56,510 --> 00:03:58,800
таксама займае час, прапарцыйнае да н.

95
00:03:58,800 --> 00:04:00,700
>> Цяпер, давайце на самай справе напісаць код

96
00:04:00,700 --> 00:04:02,000
, Які працуе са звязанымі спісамі.

97
00:04:02,000 --> 00:04:04,220
Скажам, мы хочам звязаны спіс цэлых лікаў.

98
00:04:04,220 --> 00:04:06,140
Мы можам прадставіць вузел у наш спіс яшчэ раз

99
00:04:06,140 --> 00:04:08,340
як структура з 2 палямі,

100
00:04:08,340 --> 00:04:10,750
Цэлы лік называецца "Вал"

101
00:04:10,750 --> 00:04:13,490
і наступны паказальнік на наступны вузел спісу.

102
00:04:13,490 --> 00:04:15,660
Ну, здаецца досыць простым.

103
00:04:15,660 --> 00:04:17,220
>> Скажам, мы хочам напісаць функцыю,

104
00:04:17,220 --> 00:04:19,329
які праходзіць па спісе і выводзіць

105
00:04:19,329 --> 00:04:22,150
Значэнне, якое захоўваецца ў апошні вузел спісу.

106
00:04:22,150 --> 00:04:24,850
Ну, значыць, мы павінны будзем прайсці ўсе вузлы ў спісе

107
00:04:24,850 --> 00:04:27,310
каб знайсці апошняга, але так як мы не дадаем

108
00:04:27,310 --> 00:04:29,250
або выдаляючы, мы не хочам змяніць

109
00:04:29,250 --> 00:04:32,210
Унутраная структура наступнага паказальніка ў спісе.

110
00:04:32,210 --> 00:04:34,790
>> Такім чынам, нам спатрэбіцца паказальнік спецыяльна для абыходу

111
00:04:34,790 --> 00:04:36,940
які мы называем «гусенічныя».

112
00:04:36,940 --> 00:04:38,870
Яна будзе сканаваць праз усе элементы спісу

113
00:04:38,870 --> 00:04:41,190
, Выканаўшы наступную ланцужок паказальнікаў.

114
00:04:41,190 --> 00:04:43,750
Усё, што мы захавалі гэта паказальнік на вузел 1,

115
00:04:43,750 --> 00:04:45,730
або «галавы» спісу.

116
00:04:45,730 --> 00:04:47,370
Кіраўнік паказвае на першы вузел.

117
00:04:47,370 --> 00:04:49,120
Гэта тыпу паказальнік-на-вузла.

118
00:04:49,120 --> 00:04:51,280
>> Каб атрымаць фактычна першай вузел у спісе,

119
00:04:51,280 --> 00:04:53,250
мы павінны разнаймення гэтага паказальніка,

120
00:04:53,250 --> 00:04:55,100
але перш чым мы зможам разыменовать гэта, нам трэба праверыць

121
00:04:55,100 --> 00:04:57,180
калі паказальнік з'яўляецца нулявым першым.

122
00:04:57,180 --> 00:04:59,190
Калі ён пусты, спіс пусты,

123
00:04:59,190 --> 00:05:01,320
і мы павінны надрукаваць паведамленне, што, паколькі спіс пусты,

124
00:05:01,320 --> 00:05:03,250
няма апошняга вузла.

125
00:05:03,250 --> 00:05:05,190
Але, скажам, у спіс не пусты.

126
00:05:05,190 --> 00:05:08,340
Калі гэта не так, то мы павінны паўзці праз увесь спіс

127
00:05:08,340 --> 00:05:10,440
пакуль мы не атрымаем на апошні вузел спісу,

128
00:05:10,440 --> 00:05:13,030
і як мы можам сказаць, калі мы глядзім на апошні вузел у спісе?

129
00:05:13,670 --> 00:05:16,660
>> Ну, калі наступны паказальнік вузла з'яўляецца нулявым,

130
00:05:16,660 --> 00:05:18,320
Мы ведаем, што мы знаходзімся ў канцы

131
00:05:18,320 --> 00:05:22,390
З апошнім наступны паказальнік будзе мець наступны вузел у спісе, каб паказваць.

132
00:05:22,390 --> 00:05:26,590
Гэта добрая практыка, каб заўсёды мець наступны паказальнік апошняга вузла ініцыялізаваць да нуля

133
00:05:26,590 --> 00:05:30,800
мець стандартызаваны маёмасць, якое папярэджвае нас, калі мы дасягнулі канца спісу.

134
00:05:30,800 --> 00:05:33,510
>> Такім чынам, калі гусенічных → наступны пусты,

135
00:05:34,120 --> 00:05:38,270
памятаеце, што стрэлка сінтаксіс ярлык для разнаймення

136
00:05:38,270 --> 00:05:40,010
паказальнік на структуру, то доступ

137
00:05:40,010 --> 00:05:42,510
свайго наступнага поля эквівалентныя няёмка:

138
00:05:42,510 --> 00:05:48,750
(* Гусенічныя). Наступны.

139
00:05:49,820 --> 00:05:51,260
Як толькі мы выявілі, што апошні вузел,

140
00:05:51,260 --> 00:05:53,830
мы хочам надрукаваць гусенічных → Вал,

141
00:05:53,830 --> 00:05:55,000
значэнне ў бягучым вузле

142
00:05:55,000 --> 00:05:57,130
які мы ведаем, гэта апошні.

143
00:05:57,130 --> 00:05:59,740
У адваротным выпадку, калі мы яшчэ не ў апошнюю вузла ў спісе,

144
00:05:59,740 --> 00:06:02,340
мы павінны перайсці да наступнага вузла ў спісе

145
00:06:02,340 --> 00:06:04,750
і пераканайцеся, што гэта апошняя.

146
00:06:04,750 --> 00:06:07,010
Каб зрабіць гэта, мы проста ўсталяваць наш сканер паказальнік

147
00:06:07,010 --> 00:06:09,840
, Каб паказаць на наступнае значэнне бягучага вузла,

148
00:06:09,840 --> 00:06:11,680
, Гэта значыць на наступны вузел у спісе.

149
00:06:11,680 --> 00:06:13,030
Гэта робіцца шляхам усталёўкі

150
00:06:13,030 --> 00:06:15,280
Гусенічны = гусенічных → Далей.

151
00:06:16,050 --> 00:06:18,960
Тады мы паўтараем гэты працэс, з пятлёй напрыклад,

152
00:06:18,960 --> 00:06:20,960
пакуль мы не знойдзем апошні вузел.

153
00:06:20,960 --> 00:06:23,150
Так, напрыклад, калі гусенічных паказваў на галаву,

154
00:06:24,050 --> 00:06:27,710
Пакладзем гусенічных паказваюць на гусенічным → наступным,

155
00:06:27,710 --> 00:06:30,960
які гэтак жа, як у наступным поле 1-га вузла.

156
00:06:30,960 --> 00:06:33,620
Такім чынам, цяпер наш сканер паказвае на другім вузле,

157
00:06:33,620 --> 00:06:35,480
і, зноў жа, мы паўтараем гэта з пятлёй,

158
00:06:37,220 --> 00:06:40,610
пакуль мы не знайшлі апошняга вузла, гэта значыць,

159
00:06:40,610 --> 00:06:43,640
дзе наступны паказальнік вузла паказвае на нуль.

160
00:06:43,640 --> 00:06:45,070
І ў нас гэта ёсць,

161
00:06:45,070 --> 00:06:47,620
мы знайшлі апошняга вузла ў спісе, а каб надрукаваць яго значэнне,

162
00:06:47,620 --> 00:06:50,800
мы проста выкарыстоўваем гусенічных → знач.

163
00:06:50,800 --> 00:06:53,130
>> Перамяшчэнне не так ужо дрэнна, але тое, што аб устаноўцы?

164
00:06:53,130 --> 00:06:56,290
Дапусцім, мы хочам, каб ўставіць лік у 4-й пазіцыі

165
00:06:56,290 --> 00:06:58,040
У цэлага спісу.

166
00:06:58,040 --> 00:07:01,280
Гэта значыць паміж бягучых 3 і 4 вузлоў.

167
00:07:01,280 --> 00:07:03,760
Зноў жа, у нас ёсць для прагляду спісу толькі

168
00:07:03,760 --> 00:07:06,520
дабрацца да 3-га элемента, адзін мы ўстаўка пасля.

169
00:07:06,520 --> 00:07:09,300
Такім чынам, мы ствараем гусенічных паказальнік зноў прайсці спісу,

170
00:07:09,300 --> 00:07:11,400
праверыць, калі наша галава паказальнік з'яўляецца нулявым,

171
00:07:11,400 --> 00:07:14,810
і калі гэта не так, паказаць наш сканер паказальнік на галаўным вузле.

172
00:07:16,880 --> 00:07:18,060
Такім чынам, мы на 1-м элементам.

173
00:07:18,060 --> 00:07:21,020
Мы павінны ісці наперад яшчэ 2 элемента перш чым мы зможам ўставіць,

174
00:07:21,020 --> 00:07:23,390
таму мы можам выкарыстоўваць для цыклу

175
00:07:23,390 --> 00:07:26,430
Int я = 1; I <3, Я + +

176
00:07:26,430 --> 00:07:28,590
і ў кожнай ітэрацыі цыклу,

177
00:07:28,590 --> 00:07:31,540
прасоўваць наш сканер паказальнік наперад на 1 вузел

178
00:07:31,540 --> 00:07:34,570
, Правяраючы, калі наступнае поле бягучага вузла з'яўляецца нулявым,

179
00:07:34,570 --> 00:07:37,550
і калі гэта не так, перамесціце наш сканер паказальнік на наступны вузел

180
00:07:37,550 --> 00:07:41,810
, Усталяваўшы яго роўным наступны паказальнік бягучага вузла.

181
00:07:41,810 --> 00:07:45,210
Такім чынам, паколькі наш цыкл кажа, каб зрабіць гэта

182
00:07:45,210 --> 00:07:47,550
у два разы,

183
00:07:49,610 --> 00:07:51,190
мы дасягнулі 3. вузла,

184
00:07:51,190 --> 00:07:53,110
і як толькі наш сканер паказальнік дасягнуў вузел пасля

185
00:07:53,110 --> 00:07:55,270
які мы хочам ўставіць наш новы цэлы лік,

186
00:07:55,270 --> 00:07:57,050
Як мы на самай справе ўстаўка?

187
00:07:57,050 --> 00:07:59,440
>> Ну, наша новае цэлае павінен быць устаўлены ў спіс

188
00:07:59,440 --> 00:08:01,250
як частку сваёй уласнай структуры вузла,

189
00:08:01,250 --> 00:08:03,140
так як гэта сапраўды паслядоўнасць вузлоў.

190
00:08:03,140 --> 00:08:05,690
Такім чынам, давайце зробім новы паказальнік на вузел

191
00:08:05,690 --> 00:08:08,910
называецца "new_node"

192
00:08:08,910 --> 00:08:11,800
і ўсталяваць яго, каб паказаць на памяць, што мы зараз вылучыць

193
00:08:11,800 --> 00:08:14,270
ў кучы для самога вузла,

194
00:08:14,270 --> 00:08:16,000
памяці і колькі нам трэба вылучыць?

195
00:08:16,000 --> 00:08:18,250
Ну, памер вузла,

196
00:08:20,450 --> 00:08:23,410
і мы хочам ўсталяваць яго вал поле лік, якое мы хочам ўставіць.

197
00:08:23,410 --> 00:08:25,590
Скажам, 6.

198
00:08:25,590 --> 00:08:27,710
Цяпер вузел ўтрымлівае наш цэлае значэнне.

199
00:08:27,710 --> 00:08:30,650
Гэта таксама добрая практыка для ініцыялізацыі наступнага поля новага вузла

200
00:08:30,650 --> 00:08:33,690
паказваюць на нуль,

201
00:08:33,690 --> 00:08:35,080
Але што цяпер?

202
00:08:35,080 --> 00:08:37,179
>> Мы павінны змяніць ўнутраную структуру спісу

203
00:08:37,179 --> 00:08:40,409
і на наступны паказальнікаў, якія змяшчаюцца ў існуючых спісу

204
00:08:40,409 --> 00:08:42,950
3 і 4 вузлоў.

205
00:08:42,950 --> 00:08:46,560
З наступнага паказальніка вызначаюць парадак спісу,

206
00:08:46,560 --> 00:08:48,650
і так як мы ўстаўкі нашага новага вузла

207
00:08:48,650 --> 00:08:50,510
проста ў сярэдзіне спісу,

208
00:08:50,510 --> 00:08:52,010
яна можа быць крыху больш складана.

209
00:08:52,010 --> 00:08:54,250
Гэта таму, што памятаю, наш кампутар

210
00:08:54,250 --> 00:08:56,250
толькі ведае размяшчэнне вузлоў у спісе

211
00:08:56,250 --> 00:09:00,400
з-за чарговага паказальнікі захоўваюцца ў папярэдніх вузлах.

212
00:09:00,400 --> 00:09:03,940
Такім чынам, калі мы калі-небудзь страціў любую з гэтых месцаў,

213
00:09:03,940 --> 00:09:06,860
кажуць, змяніўшы адну з наступных паказальнікаў у нашым спісе

214
00:09:06,860 --> 00:09:09,880
Напрыклад, сказаць, што мы змяніліся

215
00:09:09,880 --> 00:09:12,920
Наступны 3. вузла поля

216
00:09:12,920 --> 00:09:15,610
паказаць на некаторыя вузла сюды.

217
00:09:15,610 --> 00:09:17,920
Мы былі б не пашанцавала, таму што мы не хочам

218
00:09:17,920 --> 00:09:20,940
ёсць ідэі, дзе знайсці астатнія часткі спісу,

219
00:09:20,940 --> 00:09:23,070
і гэта, відавочна, вельмі дрэнна.

220
00:09:23,070 --> 00:09:25,080
Такім чынам, мы павінны быць вельмі асцярожныя, аб парадку

221
00:09:25,080 --> 00:09:28,360
, У якой мы маніпуляваць нашым наступным паказальнікаў падчас усталёўкі.

222
00:09:28,360 --> 00:09:30,540
>> Такім чынам, каб спрасціць гэта, давайце скажам, што

223
00:09:30,540 --> 00:09:32,220
нашы першыя 4 вузлоў

224
00:09:32,220 --> 00:09:36,200
называюцца A, B, C, і D, са стрэлкамі, які ўяўляе ланцужок паказальнікаў

225
00:09:36,200 --> 00:09:38,070
, Якія злучаюць вузлы.

226
00:09:38,070 --> 00:09:40,050
Такім чынам, нам трэба ўставіць наш новы вузел

227
00:09:40,050 --> 00:09:42,070
паміж вузламі C і D.

228
00:09:42,070 --> 00:09:45,060
Вельмі важна рабіць гэта ў правільным парадку, і я пакажу вам, чаму.

229
00:09:45,060 --> 00:09:47,500
>> Давайце паглядзім на няправільны спосаб зрабіць гэта першым.

230
00:09:47,500 --> 00:09:49,490
Гэй, мы ведаем, што новы вузел павінен прыйсці адразу пасля C,

231
00:09:49,490 --> 00:09:51,910
так што давайце ўсталяваць наступны паказальнік Сі

232
00:09:51,910 --> 00:09:54,700
паказваюць на new_node.

233
00:09:56,530 --> 00:09:59,180
Добра, здаецца, усё ў парадку, мы проста павінны скончыць зараз,

234
00:09:59,180 --> 00:10:01,580
робіць наступны пункт паказальнік на новы вузел у D,

235
00:10:01,580 --> 00:10:03,250
Але пачакайце, як мы можам гэта зрабіць?

236
00:10:03,250 --> 00:10:05,170
Адзінае, што можа сказаць нам, дзе D быў,

237
00:10:05,170 --> 00:10:07,630
быў наступны паказальнік Раней захоўваецца ў C,

238
00:10:07,630 --> 00:10:09,870
але мы проста перапісалі, што паказальнік

239
00:10:09,870 --> 00:10:11,170
каб яна паказвала на новы вузел,

240
00:10:11,170 --> 00:10:14,230
такім чынам, мы больш не маюць паняцця, дзе D знаходзіцца ў памяці,

241
00:10:14,230 --> 00:10:17,020
і мы страцілі астатнюю частку спісу.

242
00:10:17,020 --> 00:10:19,000
Не падыходзіць.

243
00:10:19,000 --> 00:10:21,090
>> Такім чынам, як мы робім гэта правільна?

244
00:10:22,360 --> 00:10:25,090
Па-першае, пазначыць наступны паказальнік на новы вузел па адрасе D.

245
00:10:26,170 --> 00:10:28,990
Цяпер, як новы вузел і C у наступным паказальнікі

246
00:10:28,990 --> 00:10:30,660
паказваюць на той жа вузел, D,

247
00:10:30,660 --> 00:10:32,290
але гэта нармальна.

248
00:10:32,290 --> 00:10:35,680
Цяпер мы можам адзначыць наступны паказальнік C на новым вузле.

249
00:10:37,450 --> 00:10:39,670
Такім чынам, мы зрабілі гэта без страты дадзеных.

250
00:10:39,670 --> 00:10:42,280
У кодзе З бягучага вузла

251
00:10:42,280 --> 00:10:45,540
што абыход паказальнік гусенічных паказвае на,

252
00:10:45,540 --> 00:10:50,400
і D ўяўляе вузел, на які паказвае наступнае поле бягучага вузла,

253
00:10:50,400 --> 00:10:52,600
або гусенічным → Далей.

254
00:10:52,600 --> 00:10:55,460
Такім чынам, мы спачатку ўсталяваць наступны паказальнік новага вузла

255
00:10:55,460 --> 00:10:57,370
паказваюць на гусенічным → наступным,

256
00:10:57,370 --> 00:11:00,880
Сапраўды гэтак жа мы сказалі, наступны паказальнік павінен new_node

257
00:11:00,880 --> 00:11:02,780
паказваюць на D на малюнку.

258
00:11:02,780 --> 00:11:04,540
Тады, мы можам усталяваць наступны паказальнік бягучага вузла

259
00:11:04,540 --> 00:11:06,330
на нашым новым вузле,

260
00:11:06,330 --> 00:11:10,980
гэтак жа, як мы павінны былі чакаць да кропкі С, каб new_node на чарцяжы.

261
00:11:10,980 --> 00:11:12,250
Цяпер усё ў парадку, і мы не страцілі

262
00:11:12,250 --> 00:11:14,490
адсочванне любых дадзеных, і мы змаглі проста

263
00:11:14,490 --> 00:11:16,200
прытрымлівацца нашага новага вузла ў сярэдзіне спісу

264
00:11:16,200 --> 00:11:19,330
без перабудовы ўсё гэта ці нават перамяшчэнне любых элементаў

265
00:11:19,330 --> 00:11:22,490
тое, як мы павінны былі б з фіксаванай даўжынёй масіва.

266
00:11:22,490 --> 00:11:26,020
>> Такім чынам, звязаныя спісы з'яўляюцца асноўнымі, але важна, дынамічныя структуры дадзеных

267
00:11:26,020 --> 00:11:29,080
якія маюць як перавагі, так і недахопы

268
00:11:29,080 --> 00:11:31,260
у параўнанні з масіваў і іншых структур дадзеных,

269
00:11:31,260 --> 00:11:33,350
і, як гэта часта бывае ў кампутарнай навуцы,

270
00:11:33,350 --> 00:11:35,640
важна ведаць, калі выкарыстоўваць кожны інструмент,

271
00:11:35,640 --> 00:11:37,960
так што вы можаце выбраць правільны інструмент для правільнай працы.

272
00:11:37,960 --> 00:11:40,060
>> Для атрымання дадатковай практыкай, паспрабаваць напісаць функцый

273
00:11:40,060 --> 00:11:42,080
выдаліць вузлы з звязанага спісу -

274
00:11:42,080 --> 00:11:44,050
не забывайце быць асцярожнымі аб парадку, у якім вы пераставіць

275
00:11:44,050 --> 00:11:47,430
Ваш наступны паказальнік, каб не страціць кавалак вашага спісу -

276
00:11:47,430 --> 00:11:50,200
ці функцыя для падліку вузлы ў звязаным спісе,

277
00:11:50,200 --> 00:11:53,280
ці весела адзін, каб змяніць парадак усе вузлы ў звязаным спісе.

278
00:11:53,280 --> 00:11:56,090
>> Мяне клічуць Джэксан Steinkamp, ​​гэта CS50.