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
ние сме обхванати голяма част от основите на C.
Ние знаем много за променливи, масиви,

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
>> И така, нека да направим това, нека да започнем
за разклоняване на това, което ни дава C,

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-- а
поединично свързан списък можем да 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
или може да бъде друг вид информация
че сте дефинирана с тип дефиниция.

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
можем да определим и 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
Тя; е тип данни на
структура, която съдържа данни,

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
отиваме имаше
segfault и ние не искаме това.

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
И тогава ние искаме to-- в крайна сметка, тъй като
функция прототип 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
Така че сега сме към стъпка C,
инициализира поле възли стойност.

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
A функция прототип, или
декларация за тази функция,

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 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
Не можем просто да кажем, искам
за да отидете на 0th елемент,

238
00:12:18,150 --> 00:12:21,410
или 6-ия елемент на моя масив,
което мога да направя в масив.

239
00:12:21,410 --> 00:12:25,080
Не мога да кажа, че искам да отида до
0th елемент, или 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
>> OK, как да вмъкнете нов
възел в свързан списък?

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
А ти видя какво ще стане, ако ние
Исках to-- или от само на секунда

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
orphaning останалата част от списъка.

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 не е самата
нищожна показалеца точно сега,

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
И може би сте забелязали I пропусне една,
изтриване на един елемент от свързано

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