1
00:00:00,000 --> 00:00:02,832
>> [MUZYKI]

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

3
00:00:05,670 --> 00:00:08,560
>> DOUG LLOYD: OK, więc w
ten punkt w czasie,

4
00:00:08,560 --> 00:00:15,300
omówiliśmy wiele podstaw C
Wiemy dużo o zmiennych, tablic,

5
00:00:15,300 --> 00:00:17,610
wskaźniki, wszystko, co dobre rzeczy.

6
00:00:17,610 --> 00:00:21,610
Ci są jakby zbudowany
aby zobaczyć, jak podstaw,

7
00:00:21,610 --> 00:00:23,880
ale możemy zrobić więcej, prawda?

8
00:00:23,880 --> 00:00:27,930
Możemy łączyć rzeczy
razem w interesujący sposób.

9
00:00:27,930 --> 00:00:31,010
>> A więc zróbmy to, zacznijmy
się rozwijać, co C daje nam,

10
00:00:31,010 --> 00:00:35,270
i zacząć tworzyć własne dane
konstrukcje wykorzystujące te budynek

11
00:00:35,270 --> 00:00:40,590
bloki razem coś zrobić
naprawdę cenne, przydatne.

12
00:00:40,590 --> 00:00:43,420
Jednym ze sposobów możemy to zrobić
mówić o zbiorach.

13
00:00:43,420 --> 00:00:48,360
Tak więc do tej pory mieliśmy jeden rodzaj danych
struktura reprezentująca kolekcje

14
00:00:48,360 --> 00:00:51,030
od wartości, podobnie jak wartości.

15
00:00:51,030 --> 00:00:52,350
To byłoby tablicą.

16
00:00:52,350 --> 00:00:57,020
Mamy zbiory liczb całkowitych, lub
zbiory znaków i tak dalej.

17
00:00:57,020 --> 00:01:00,890
>> Struktury są również swego rodzaju danych
Struktura zbierania informacji,

18
00:01:00,890 --> 00:01:03,220
ale to nie jest do zbierania jak wartości.

19
00:01:03,220 --> 00:01:08,090
Zwykle łączy różne typy danych
razem wewnątrz jednej obudowie.

20
00:01:08,090 --> 00:01:10,750
Ale to nie jest sam
wykorzystywane do łańcucha razem

21
00:01:10,750 --> 00:01:16,920
lub łączyć ze sobą podobne
przedmioty, takie jak tablica.

22
00:01:16,920 --> 00:01:20,960
Tablice są idealne dla
Element patrzeć, ale przypominam sobie

23
00:01:20,960 --> 00:01:24,262
że jest to bardzo trudne
wstawić do tablicy,

24
00:01:24,262 --> 00:01:26,470
chyba, że ​​mamy do wkładania w
sam koniec tej tablicy.

25
00:01:26,470 --> 00:01:29,730
>> A najlepszym przykładem mam
za to jest Sortowanie przez wstawianie.

26
00:01:29,730 --> 00:01:31,650
Jeśli pamiętacie nasz film
na Sortowanie przez wstawianie,

27
00:01:31,650 --> 00:01:34,110
nie było wiele
Koszty udziału w konieczności

28
00:01:34,110 --> 00:01:37,970
podnieść elementy, i przeniesienie ich
się w sposób dopasować coś

29
00:01:37,970 --> 00:01:41,290
w środku swojej tablicy.

30
00:01:41,290 --> 00:01:44,690
Tablice również cierpią z powodu innego
Problem, który jest brak elastyczności.

31
00:01:44,690 --> 00:01:47,150
Kiedy zadeklarować tablicę,
mamy jedną szansę na to.

32
00:01:47,150 --> 00:01:49,790
Docieramy do powiedzenia, chcę
to wiele elementów.

33
00:01:49,790 --> 00:01:51,940
Może być 100, to może
1,000, to może

34
00:01:51,940 --> 00:01:55,930
x, gdzie x to numer, który użytkownik
dał nam na wiersz lub na komendzie

35
00:01:55,930 --> 00:01:56,630
Linia.

36
00:01:56,630 --> 00:01:59,905
>> Ale tylko jeden strzał na to, że
nie daj się potem mówią, oh, właściwie,

37
00:01:59,905 --> 00:02:04,360
potrzebne 101 lub Potrzebowałem X plus 20.

38
00:02:04,360 --> 00:02:07,910
Za późno, my już ogłoszony
tablica, a jeśli chcemy mieć 101 lub x

39
00:02:07,910 --> 00:02:12,050
plus 20, musimy zadeklarować
zupełnie inna tablica,

40
00:02:12,050 --> 00:02:15,540
skopiować wszystkie elementy tablicy
powyżej, a następnie mamy wystarczająco dużo.

41
00:02:15,540 --> 00:02:19,880
A co, jeśli jesteśmy znowu źle, co
jeśli rzeczywiście potrzeba 102 lub X plus 40,

42
00:02:19,880 --> 00:02:21,970
musimy to zrobić ponownie.

43
00:02:21,970 --> 00:02:26,250
Tak więc są bardzo nieelastyczne
do zmiany rozmiaru nasze dane,

44
00:02:26,250 --> 00:02:29,360
ale jeśli połączymy ze sobą pewne
z podstaw już, że mamy

45
00:02:29,360 --> 00:02:33,230
Dowiedziałem się o wskazówki i budowli,
w szczególności z wykorzystaniem pamięci dynamicznej

46
00:02:33,230 --> 00:02:36,180
Alokacja z malloc, że
można umieścić te elementy razem

47
00:02:36,180 --> 00:02:40,960
Aby utworzyć nowe dane structure-- A
pojedynczo związane listy możemy say--

48
00:02:40,960 --> 00:02:45,400
która pozwala nam się rozwijać i
kurczyć zbiór wartości

49
00:02:45,400 --> 00:02:48,800
i nie będziemy mieć żadnego marnował miejsca.

50
00:02:48,800 --> 00:02:53,320
>> Więc znowu, my nazywamy ten pomysł,
to pojęcie, połączonej listy.

51
00:02:53,320 --> 00:02:56,320
W szczególności, w tym filmie jesteśmy
mówisz pojedynczo połączonej listy,

52
00:02:56,320 --> 00:02:59,185
a potem jeszcze wideo porozmawiamy
o podwójnie związane listy, które

53
00:02:59,185 --> 00:03:01,560
jest po prostu wariacja na temat tutaj.

54
00:03:01,560 --> 00:03:05,200
Ale pojedynczo związane listy
składa się z węzłów

55
00:03:05,200 --> 00:03:08,559
węzły po prostu streszczenie term--
to jest po prostu coś Dzwonię

56
00:03:08,559 --> 00:03:10,350
to swego rodzaju
Struktura, w zasadzie, że jestem?

57
00:03:10,350 --> 00:03:16,190
Tylko będzie to nazwać node-- i to
węzeł ma dwóch członków, lub dwa pola.

58
00:03:16,190 --> 00:03:20,300
Ma danych, zwykle
całkowitą, pływak charakter,

59
00:03:20,300 --> 00:03:23,790
czy może być jakiś inny typ danych
które zostały zdefiniowane z typu def.

60
00:03:23,790 --> 00:03:29,290
I zawiera wskaźnik
inny węzeł tego samego typu.

61
00:03:29,290 --> 00:03:34,710
>> Mamy więc dwie rzeczy wewnątrz
węzeł, danych i wskaźnik

62
00:03:34,710 --> 00:03:36,380
do innego węzła.

63
00:03:36,380 --> 00:03:39,370
A jeśli zaczniesz wizualizować
to można o tym myśleć

64
00:03:39,370 --> 00:03:42,280
jak sieć węzłów
są ze sobą połączone.

65
00:03:42,280 --> 00:03:45,070
Mamy pierwszy węzeł, to
zawiera dane, a wskaźnik

66
00:03:45,070 --> 00:03:49,110
do drugiego węzła, zawierającym
Dane, a wskaźnik trzeciego węzła.

67
00:03:49,110 --> 00:03:52,940
A więc dlatego nazywamy go do
połączonej listy, są one ze sobą powiązane.

68
00:03:52,940 --> 00:03:56,070
>> Co to specjalny
Struktura węzła wygląda?

69
00:03:56,070 --> 00:04:01,120
Cóż, jeśli pamiętam z naszej wideo na
definiowania własnych typów, z typu def,

70
00:04:01,120 --> 00:04:05,400
możemy zdefiniować structure-- i
wpisz zdefiniować strukturę tak.

71
00:04:05,400 --> 00:04:11,240
tyepdef struct sllist, a następnie jestem
przy użyciu wartości słowa tu arbitralnie

72
00:04:11,240 --> 00:04:13,891
wskazać dowolny typ danych, naprawdę.

73
00:04:13,891 --> 00:04:16,890
Można zdać się na liczbę całkowitą lub pływaka,
możesz mieć co chcesz.

74
00:04:16,890 --> 00:04:19,389
To nie jest ograniczona do zaledwie
liczb całkowitych, lub coś w tym stylu.

75
00:04:19,389 --> 00:04:22,790
Tak więc wartość jest tylko arbitralne
Typ danych, a następnie wskaźnik

76
00:04:22,790 --> 00:04:26,310
do innego węzła tego samego typu.

77
00:04:26,310 --> 00:04:29,690
>> Teraz jest mały haczyk
tutaj z definiowania struktury

78
00:04:29,690 --> 00:04:33,030
kiedy to struktura siebie więzy.

79
00:04:33,030 --> 00:04:35,340
Muszę mieć tymczasowy
nazwa dla mojej konstrukcji.

80
00:04:35,340 --> 00:04:37,640
Na koniec dnia I
wyraźnie to nazwać

81
00:04:37,640 --> 00:04:43,030
Węzeł SLL, to ostatecznie nowy
wymienić część mojej definicji typu,

82
00:04:43,030 --> 00:04:47,450
ale nie mogę korzystać z węzła SLL
w środku tego.

83
00:04:47,450 --> 00:04:51,430
Wynika to z faktu, że nie mają
stworzył typ zwany węzeł SLL

84
00:04:51,430 --> 00:04:55,200
dopóki nie uderzył ten punkt końcowy tutaj.

85
00:04:55,200 --> 00:04:59,720
Do tego momentu, muszę mieć
inny sposób odnieść się do tego typu danych.

86
00:04:59,720 --> 00:05:02,440
>> I jest to samo
referencyjna typ danych.

87
00:05:02,440 --> 00:05:06,314
To; s do typu danych
Struktura, która zawiera dane

88
00:05:06,314 --> 00:05:08,480
i wskaźnik do innego
Struktura tego samego typu.

89
00:05:08,480 --> 00:05:11,750
Więc muszę być w stanie odnieść się do
Ten typ danych, przynajmniej czasowo,

90
00:05:11,750 --> 00:05:14,910
tak, nadając mu tymczasowy
Nazwa struct sllist

91
00:05:14,910 --> 00:05:18,540
Pozwala mi to powiedzieć chcę
wskaźnik do innego sllist struct,

92
00:05:18,540 --> 00:05:24,690
gwiazda struktura sllist, a następnie
po tym, jak zakończył definicję,

93
00:05:24,690 --> 00:05:27,220
Teraz mogę nazwać tego typu węzeł SLL.

94
00:05:27,220 --> 00:05:30,520
>> Więc dlatego widzisz tam
tymczasowa nazwa tutaj,

95
00:05:30,520 --> 00:05:31,879
ale na stałe nazwę.

96
00:05:31,879 --> 00:05:33,920
Czasami można zobaczyć
definicje struktury,

97
00:05:33,920 --> 00:05:36,570
Na przykład, nie jest
siebie więzy, które

98
00:05:36,570 --> 00:05:39,390
nie ma nazwy specyfikatora tutaj.

99
00:05:39,390 --> 00:05:43,040
To po prostu powiedzieć typedef struct,
otworzyć nawias klamrowy, a następnie zdefiniować.

100
00:05:43,040 --> 00:05:45,620
Ale jeśli struktura jest samo
więzy, jak ten jeden jest,

101
00:05:45,620 --> 00:05:49,010
trzeba określić
tymczasowa nazwa typu.

102
00:05:49,010 --> 00:05:51,310
Ale w końcu, teraz
że zrobiliśmy to,

103
00:05:51,310 --> 00:05:53,620
możemy po prostu odnosi się do
węzły te jednostki te,

104
00:05:53,620 --> 00:05:57,900
jako SLL węzłów dla celów
od pozostałej części tego obrazu.

105
00:05:57,900 --> 00:06:00,900
>> W porządku, więc wiemy, jak
stworzyć połączony węzeł listy.

106
00:06:00,900 --> 00:06:03,240
Wiemy, jak zdefiniować
węzeł wiązana listy.

107
00:06:03,240 --> 00:06:06,670
Teraz, gdy mamy zamiar zacząć
wykorzystując je do zbierania informacji,

108
00:06:06,670 --> 00:06:10,360
jest kilka operacji mamy
trzeba zrozumieć i pracować.

109
00:06:10,360 --> 00:06:12,860
Musimy wiedzieć, jak tworzyć
połączonej listy z powietrza.

110
00:06:12,860 --> 00:06:14,901
Jeśli nie ma już żadnej listy,
chcemy rozpocząć jeden.

111
00:06:14,901 --> 00:06:16,960
Więc musimy być w stanie
w celu utworzenia połączonej listy

112
00:06:16,960 --> 00:06:19,130
musimy chyba szukać
listę łącza

113
00:06:19,130 --> 00:06:21,830
znaleźć element szukamy.

114
00:06:21,830 --> 00:06:24,430
Musimy być w stanie wprowadzić
nowe rzeczy do listy,

115
00:06:24,430 --> 00:06:25,930
chcemy, aby nasza lista, aby móc się rozwijać.

116
00:06:25,930 --> 00:06:28,638
I podobnie, chcemy być w stanie
usunąć z naszej listy rzeczy,

117
00:06:28,638 --> 00:06:30,250
chcemy, aby nasza lista, aby móc się kurczyć.

118
00:06:30,250 --> 00:06:32,160
I na koniec nasze
programy, szczególnie

119
00:06:32,160 --> 00:06:34,550
jeśli przypomnieć, że jesteśmy
dynamicznego przydzielania pamięci

120
00:06:34,550 --> 00:06:38,337
budować te listy zwykle,
chcemy uwalniania całego tej pamięci

121
00:06:38,337 --> 00:06:39,670
kiedy skończymy pracę z nim.

122
00:06:39,670 --> 00:06:44,627
A więc musimy być w stanie usunąć
Cała lista połączone w jednym nie swoop.

123
00:06:44,627 --> 00:06:46,460
Warto więc przejść przez
Niektóre z tych działań

124
00:06:46,460 --> 00:06:51,192
i jak możemy je wizualizować,
rozmowy w kodzie pseudocode specjalnie.

125
00:06:51,192 --> 00:06:53,150
Dlatego chcemy, aby utworzyć
związane listy, więc być może

126
00:06:53,150 --> 00:06:56,480
Aby zdefiniować funkcję
z tego prototypu.

127
00:06:56,480 --> 00:07:01,690
SLL gwiazda węzłów, tworzenie i olewam
w jednym argumentem, niektóre arbitralne danych

128
00:07:01,690 --> 00:07:05,530
wpisz ponownie jakiegoś dowolnego typu danych.

129
00:07:05,530 --> 00:07:10,482
Ale ja returning-- tej funkcji powinny
wróć do mnie wskaźnik, Do pojedynczo

130
00:07:10,482 --> 00:07:11,190
związana węzłem listy.

131
00:07:11,190 --> 00:07:14,050
Ponownie, staramy się stworzyć
połączonej listy z powietrza,

132
00:07:14,050 --> 00:07:17,900
więc muszę wskaźnik do
że lista gdy skończę.

133
00:07:17,900 --> 00:07:19,420
>> Więc jakie są kolejne etapy tutaj?

134
00:07:19,420 --> 00:07:20,960
Cóż, pierwszą rzeczą, że jestem
zamiar zrobić to dynamicznie

135
00:07:20,960 --> 00:07:22,550
przydzielić miejsca dla nowego węzła.

136
00:07:22,550 --> 00:07:26,689
Ponownie tworzymy go z cienkiej
powietrza, więc musimy przestrzeni malloc dla niego.

137
00:07:26,689 --> 00:07:28,480
I oczywiście, natychmiast
po tym jak malloc,

138
00:07:28,480 --> 00:07:31,692
zawsze upewnij się, że nasze
pointer-- nie wrócić zerowy.

139
00:07:31,692 --> 00:07:33,650
Bo jeśli spróbujemy
poważanie pustego wskaźnika,

140
00:07:33,650 --> 00:07:36,190
będziemy cierpieć
wysypać, a my tego nie chcemy.

141
00:07:36,190 --> 00:07:39,510
>> Następnie chcemy wypełnić pole,
chcemy zainicjować pole wartości

142
00:07:39,510 --> 00:07:41,690
i zainicjować następne pole.

143
00:07:41,690 --> 00:07:45,450
A potem chcemy to-- końcu jak
Prototyp funkcji indicates-- chcemy

144
00:07:45,450 --> 00:07:49,940
zwraca wskaźnik do węzła SLL.

145
00:07:49,940 --> 00:07:51,710
Co więc zrobić to wygląda wizualnie?

146
00:07:51,710 --> 00:07:55,230
Cóż, najpierw jedziemy do dynamicznie
przydzielić miejsca dla nowego węzła SLL,

147
00:07:55,230 --> 00:07:58,320
więc malloc-- to
reprezentacja wizualna

148
00:07:58,320 --> 00:08:00,020
węzła właśnie utworzyliśmy.

149
00:08:00,020 --> 00:08:02,757
A my upewnij się,
nie jest null-- w tym wypadku

150
00:08:02,757 --> 00:08:04,840
obraz nie będzie miał
pokazał się, czy to null

151
00:08:04,840 --> 00:08:07,298
mielibyśmy zabraknie pamięci,
więc jesteśmy dobrze tam.

152
00:08:07,298 --> 00:08:10,200
Więc teraz jesteśmy do punktu C,
zainicjować pole wartości węzłów.

153
00:08:10,200 --> 00:08:12,280
Cóż, na podstawie tej funkcji
zadzwonić używam tutaj,

154
00:08:12,280 --> 00:08:16,700
Wygląda na to, że chcą przekazać w 6,
więc będę 6 w polu wartości.

155
00:08:16,700 --> 00:08:18,865
Teraz, zainicjować następne pole.

156
00:08:18,865 --> 00:08:21,640
No, co ja mam do zrobienia,
nie ma nic obok, w prawo,

157
00:08:21,640 --> 00:08:23,600
jest to jedyna rzecz na liście.

158
00:08:23,600 --> 00:08:27,206
Więc jaka jest następna rzecz na liście?

159
00:08:27,206 --> 00:08:29,660
>> To nie powinno wskazywać na cokolwiek, prawda.

160
00:08:29,660 --> 00:08:33,600
Nic więcej tam, więc to, co jest
koncepcja wiemy, że to nothing--

161
00:08:33,600 --> 00:08:35,638
wskaźniki do niczego?

162
00:08:35,638 --> 00:08:37,929
Powinno być może chcemy
aby tam pustego wskaźnika,

163
00:08:37,929 --> 00:08:40,178
a ja reprezentuje wartość null
wyżeł, jak tylko czerwone pole,

164
00:08:40,178 --> 00:08:41,559
nie możemy iść dalej.

165
00:08:41,559 --> 00:08:44,430
Jak zobaczymy trochę później,
będziemy mieć ewentualnie nawet łańcuchy

166
00:08:44,430 --> 00:08:46,330
strzał podłączenia
węzły te razem,

167
00:08:46,330 --> 00:08:48,480
ale gdy trafisz
czerwone pole, to null

168
00:08:48,480 --> 00:08:51,150
nie możemy iść dalej,
że to koniec listy.

169
00:08:51,150 --> 00:08:53,960
>> I wreszcie, po prostu chcemy
zwracają wskaźnik do tego węzła.

170
00:08:53,960 --> 00:08:56,160
Więc nazwijmy go nowym,
i wróci nowa

171
00:08:56,160 --> 00:08:59,370
dzięki czemu może być stosowany w
Funkcja to, co stworzył.

172
00:08:59,370 --> 00:09:03,100
Więc nie idziemy, stworzyliśmy pojedynczo
związane lista węzeł z powietrza,

173
00:09:03,100 --> 00:09:05,920
a teraz mamy listę możemy pracować.

174
00:09:05,920 --> 00:09:08,260
>> Teraz, powiedzmy, że już
mają duży łańcuch

175
00:09:08,260 --> 00:09:09,800
i chcemy znaleźć coś w nim.

176
00:09:09,800 --> 00:09:12,716
I chcemy funkcję, która się dzieje
powrót prawdziwe lub fałszywe, w zależności

177
00:09:12,716 --> 00:09:15,840
od tego, czy wartość istnieje w tym wykazie.

178
00:09:15,840 --> 00:09:18,160
Prototyp funkcji lub
Deklaracja dla tej funkcji,

179
00:09:18,160 --> 00:09:23,320
może wyglądać this-- bool znaleźć i
Następnie chcemy przekazać w dwóch argumentów.

180
00:09:23,320 --> 00:09:26,996
>> Pierwszy, to wskaźnik do
Pierwszym elementem połączonej listy.

181
00:09:26,996 --> 00:09:29,620
To jest rzeczywiście coś będziesz
zawsze chcesz śledzić,

182
00:09:29,620 --> 00:09:33,110
i rzeczywiście może być coś, co
nawet umieścić w zmiennej globalnej.

183
00:09:33,110 --> 00:09:35,360
Po utworzeniu listy,
zawsze, zawsze

184
00:09:35,360 --> 00:09:38,990
Aby śledzić bardzo
Pierwszy element listy.

185
00:09:38,990 --> 00:09:43,690
W ten sposób można zwrócić się do wszystkich innych
Elementy by tuż po łańcuch,

186
00:09:43,690 --> 00:09:47,300
bez konieczności utrzymania wskazówek
nienaruszone do każdego elementu.

187
00:09:47,300 --> 00:09:50,920
Wystarczy tylko śledzić pierwszy
jeden, czy wszystkie są połączone w łańcuch.

188
00:09:50,920 --> 00:09:52,460
>> A potem druga sprawa
przekazujemy ponownie

189
00:09:52,460 --> 00:09:54,376
jest arbitralnie some--
niezależnie od typu danych jesteśmy

190
00:09:54,376 --> 00:09:59,640
szukasz jest wewnątrz
z nadzieją jeden z węzłów w liście.

191
00:09:59,640 --> 00:10:00,980
Więc jakie są kroki?

192
00:10:00,980 --> 00:10:04,250
Cóż, pierwsze co robimy, jest
tworzymy wskaźnik poprzeczny

193
00:10:04,250 --> 00:10:06,015
wskazując na czele list.

194
00:10:06,015 --> 00:10:08,890
Cóż, dlaczego to robimy, mamy już
mieć wskaźnik na czele list,

195
00:10:08,890 --> 00:10:10,974
dlaczego nie możemy się poruszać, że jeden wokół?

196
00:10:10,974 --> 00:10:13,140
Cóż, tak właśnie powiedziałem,
to naprawdę ważne dla nas

197
00:10:13,140 --> 00:10:17,580
zawsze śledzić
Pierwszy element listy.

198
00:10:17,580 --> 00:10:21,270
A więc jest to rzeczywiście lepiej
stworzyć duplikat, który,

199
00:10:21,270 --> 00:10:25,350
i używać, aby poruszać się tak, że nigdy nie
przypadkowo odejść, lub zawsze

200
00:10:25,350 --> 00:10:30,430
mają wskaźnik w pewnym momencie, że jest
w prawo na pierwszym elemencie listy.

201
00:10:30,430 --> 00:10:33,290
Więc lepiej jest utworzyć
Drugi, którego używamy, aby przenieść.

202
00:10:33,290 --> 00:10:35,877
>> Następnie wystarczy porównać, czy
Pole wartości w tym węźle

203
00:10:35,877 --> 00:10:38,960
jest to, co szukasz, a jeśli jest to
Nie, po prostu przejść do następnego węzła.

204
00:10:38,960 --> 00:10:41,040
A my dalej robić, że
nad, i więcej, i więcej,

205
00:10:41,040 --> 00:10:44,811
aż albo znaleźć
element, albo uderzymy

206
00:10:44,811 --> 00:10:47,310
null-- dotarliśmy do końca
listy i go tam nie ma.

207
00:10:47,310 --> 00:10:50,540
Powinno to mam nadzieję, że pierścień dzwon
do ciebie, jak tylko liniowy wyszukiwarka,

208
00:10:50,540 --> 00:10:54,430
jesteśmy po prostu replikacji go w
pojedynczo połączone struktury lista

209
00:10:54,430 --> 00:10:56,280
zamiast przy użyciu tablicy, aby to zrobić.

210
00:10:56,280 --> 00:10:58,210
>> Więc tutaj jest przykład
pojedynczo połączonej listy.

211
00:10:58,210 --> 00:11:00,043
Ten składa się z
pięć węzłów, a my mamy

212
00:11:00,043 --> 00:11:04,330
wskaźnik na czele
Lista, która nazywa się lista.

213
00:11:04,330 --> 00:11:07,385
Pierwszą rzeczą, którą chcesz zrobić, to
ponownie utworzyć ten wskaźnik przejścia.

214
00:11:07,385 --> 00:11:09,760
Więc mamy teraz dwa wskaźniki
które wskazują na to samo.

215
00:11:09,760 --> 00:11:15,025
>> Teraz, tutaj odnotować również, ja nie
muszą malloc żadnego miejsca dla trav.

216
00:11:15,025 --> 00:11:18,970
Nie powiedziałem trav równa malloc
coś, że węzeł już istnieje,

217
00:11:18,970 --> 00:11:21,160
że przestrzeń w pamięci, już istnieje.

218
00:11:21,160 --> 00:11:24,290
Więc faktycznie robimy jest
tworząc kolejny wskaźnik do niego.

219
00:11:24,290 --> 00:11:28,210
Nie jestem mallocing dodatkowe
miejsca, po prostu mają teraz dwa wskaźniki

220
00:11:28,210 --> 00:11:31,370
wskazując tym samym.

221
00:11:31,370 --> 00:11:33,710
>> Tak jest 2, co szukam?

222
00:11:33,710 --> 00:11:37,220
Cóż, nie, tak, a nie jestem
zamiar, aby przejść do następnego.

223
00:11:37,220 --> 00:11:41,740
Więc w zasadzie powiedziałbym,
trav równa TRAV obok.

224
00:11:41,740 --> 00:11:43,630
Jest 3 co szukam, nie.

225
00:11:43,630 --> 00:11:45,780
Więc nadal iść
poprzez, aż ostatecznie

226
00:11:45,780 --> 00:11:48,690
dostać się do 6, który jest to, czego szukam
na podstawie wywołania funkcji

227
00:11:48,690 --> 00:11:51,600
Mam na górze
tam, i tak skończę.

228
00:11:51,600 --> 00:11:54,150
>> A co, jeśli element jestem
poszukuje nie jest na liście,

229
00:11:54,150 --> 00:11:55,510
jest to nadal będzie działać?

230
00:11:55,510 --> 00:11:57,120
Cóż, zauważysz, że lista
tutaj jest nieco inny,

231
00:11:57,120 --> 00:11:59,410
i to jest inna sprawa, że ​​to
ważne z połączonych listach,

232
00:11:59,410 --> 00:12:01,780
nie masz się zachować
je w określonej kolejności.

233
00:12:01,780 --> 00:12:05,390
Możesz, jeśli chcesz, ale
można już zauważyć

234
00:12:05,390 --> 00:12:09,310
że nie jesteśmy śledzenie
jaki numer elementem jesteśmy.

235
00:12:09,310 --> 00:12:13,150
>> I to jest jakby jednym handlu, które
mieć z połączonej listy wersety tablic,

236
00:12:13,150 --> 00:12:15,300
jest to, że nie mamy
o dostępie swobodnym już.

237
00:12:15,300 --> 00:12:18,150
Nie możemy po prostu powiedzieć, chcę
aby przejść do elementu 0TH,

238
00:12:18,150 --> 00:12:21,410
lub 6. elementem mojej tablicy,
które można zrobić w tablicy.

239
00:12:21,410 --> 00:12:25,080
Nie mogę powiedzieć, że chcą, aby przejść do
Element 0-gi lub 6th Element,

240
00:12:25,080 --> 00:12:30,360
lub 25. elementem mojego połączonej listy,
nie ma indeksu z nimi związane.

241
00:12:30,360 --> 00:12:33,660
I tak naprawdę nie ma znaczenia
jeśli mamy zachować naszą listę, w porządku.

242
00:12:33,660 --> 00:12:36,080
Jeśli chcesz Ciebie
Na pewno można, ale nie

243
00:12:36,080 --> 00:12:38,567
nie ma powodu, dlaczego muszą
przechowuje się w dowolnej kolejności.

244
00:12:38,567 --> 00:12:40,400
Więc jeszcze raz, spróbujmy
znaleźć 6 na tej liście.

245
00:12:40,400 --> 00:12:43,200
Cóż, możemy rozpocząć się
poczynając, nie znajdziemy 6,

246
00:12:43,200 --> 00:12:47,690
a następnie nie kontynuować znalezieniu
6, aż w końcu dostać się tutaj.

247
00:12:47,690 --> 00:12:52,790
Więc teraz trav wskazuje na węzeł
zawierające 8, sześć nie w środku.

248
00:12:52,790 --> 00:12:55,250
>> Więc następnym krokiem będzie
aby przejść do następnego wskaźnika,

249
00:12:55,250 --> 00:12:57,440
więc powiedzieć, trav równa TRAV obok.

250
00:12:57,440 --> 00:13:00,750
Cóż, trav następne, oznaczone
czerwone pole nie jest puste.

251
00:13:00,750 --> 00:13:03,020
Więc nie ma nigdzie indziej
go, a więc w tym momencie

252
00:13:03,020 --> 00:13:06,120
możemy stwierdzić, że osiągnęliśmy
końcem połączonym listy

253
00:13:06,120 --> 00:13:07,190
i 6, nie ma tam.

254
00:13:07,190 --> 00:13:10,980
I to być zwrócone
fałszywe w tym przypadku.

255
00:13:10,980 --> 00:13:14,540
>> OK, w jaki sposób wprowadzić nowy
węzeł w połączonej listy?

256
00:13:14,540 --> 00:13:17,310
Więc byliśmy w stanie stworzyć
połączonej listy znikąd,

257
00:13:17,310 --> 00:13:19,370
ale prawdopodobnie chcesz
zbudować łańcuch i nie

258
00:13:19,370 --> 00:13:22,620
utworzyć kilka różnych list.

259
00:13:22,620 --> 00:13:25,700
Chcemy mieć jedną listę,
ma kilka węzłów w nim,

260
00:13:25,700 --> 00:13:28,040
nie kilka list z jednego węzła.

261
00:13:28,040 --> 00:13:31,260
Więc nie możemy po prostu zachować używając Tworzenie
Funkcja zdefiniowaliśmy wcześniej, teraz my

262
00:13:31,260 --> 00:13:33,860
Aby wstawić do
Lista, która już istnieje.

263
00:13:33,860 --> 00:13:36,499
>> Więc tym przypadku, będziemy
przekazać w dwóch argumentów,

264
00:13:36,499 --> 00:13:39,290
wskaźnik do głowy, że
związane listy, które chcesz dodać do listy.

265
00:13:39,290 --> 00:13:40,910
Ponownie, to dlaczego jest tak
ważne, że zawsze

266
00:13:40,910 --> 00:13:43,400
śledzić, bo
jest to jedyny sposób, naprawdę

267
00:13:43,400 --> 00:13:46,690
muszą odnosić się do całej listy jest
tak by wskaźnik do pierwszego elementu.

268
00:13:46,690 --> 00:13:49,360
Dlatego chcemy, aby przejść w sposób
wskaźnik do tego pierwszego elementu,

269
00:13:49,360 --> 00:13:52,226
i cokolwiek Cenimy
chcesz dodać do listy.

270
00:13:52,226 --> 00:13:54,600
I ostatecznie ta funkcja
będzie zwracają wskaźnik

271
00:13:54,600 --> 00:13:57,980
do nowego czele połączonej listy.

272
00:13:57,980 --> 00:13:59,700
>> Jakie są kolejne etapy tutaj?

273
00:13:59,700 --> 00:14:02,249
Cóż, tak jak w przypadku tworzenia,
musimy dynamicznie przydzielać

274
00:14:02,249 --> 00:14:05,540
przestrzeń dla nowego węzła, i sprawdź,
pewność, że nie zabraknie pamięci, ponownie,

275
00:14:05,540 --> 00:14:07,150
ponieważ używamy malloc.

276
00:14:07,150 --> 00:14:09,080
Następnie chcemy wypełnić
i wstawić węzeł,

277
00:14:09,080 --> 00:14:12,730
więc umieścić numer, niezależnie od
val jest do węzła.

278
00:14:12,730 --> 00:14:17,310
Chcemy, aby wstawić węzeł na
początek połączonej listy.

279
00:14:17,310 --> 00:14:19,619
>> Jest powód, że
Aby to zrobić, i to

280
00:14:19,619 --> 00:14:21,910
może być warte podjęcia sekundę
aby wstrzymać film tutaj,

281
00:14:21,910 --> 00:14:25,860
i myśleć o tym, dlaczego miałbym chcieć
wstaw na początku związane

282
00:14:25,860 --> 00:14:26,589
lista.

283
00:14:26,589 --> 00:14:28,630
Ponownie, już wcześniej wspomniałem
że tak naprawdę nie ma

284
00:14:28,630 --> 00:14:33,020
znaczenia, czy zachowamy go w dowolnym
zamówienie, więc może to jakaś wskazówka.

285
00:14:33,020 --> 00:14:36,040
I zobaczyłem, co by się stało, gdybyśmy
chciał to-- lub tylko sekundę

286
00:14:36,040 --> 00:14:37,360
temu, kiedy mieliśmy
poprzez wyszukiwanie ci

287
00:14:37,360 --> 00:14:39,235
widział, co może
się stało, gdybyśmy starali

288
00:14:39,235 --> 00:14:41,330
wstawić na koniec listy.

289
00:14:41,330 --> 00:14:44,750
Ponieważ nie mają
wskaźnik na koniec listy.

290
00:14:44,750 --> 00:14:47,490
>> Więc dlatego, że nie chcę
wstawić na początku

291
00:14:47,490 --> 00:14:49,380
to dlatego, że mogę to zrobić natychmiast.

292
00:14:49,380 --> 00:14:52,730
Mam wskaźnik na początku i
zobaczymy to na wizualne w drugim.

293
00:14:52,730 --> 00:14:55,605
Ale jeśli chcę wstawić na końcu,
Muszę zacząć od początku,

294
00:14:55,605 --> 00:14:58,760
przechodzić przez całą drogę do
końca, a następnie przykleić ją na.

295
00:14:58,760 --> 00:15:01,420
Tak, oznaczałoby to, że
wstawienie na końcu listy

296
00:15:01,420 --> 00:15:04,140
staną się o N
Operacja, wracając

297
00:15:04,140 --> 00:15:06,720
do naszej dyskusji
złożoność obliczeniowa.

298
00:15:06,720 --> 00:15:10,140
Że to stać się o pracy n, gdzie
jako lista dostał większy i większy,

299
00:15:10,140 --> 00:15:13,310
i większe, to będzie stawać się coraz
trudniej hals coś

300
00:15:13,310 --> 00:15:14,661
on na końcu.

301
00:15:14,661 --> 00:15:17,410
Ale to jest zawsze bardzo łatwo
hals coś na początku,

302
00:15:17,410 --> 00:15:19,060
jesteś zawsze na początku.

303
00:15:19,060 --> 00:15:21,620
>> I zobaczymy wizualną tego ponownie.

304
00:15:21,620 --> 00:15:24,100
A potem, gdy skończymy, po
mamy wstawiony nowy węzeł,

305
00:15:24,100 --> 00:15:26,880
chcemy zwrócić naszą wskaźnik
nowy szef połączonej listy, które

306
00:15:26,880 --> 00:15:29,213
ponieważ jesteśmy wstawienie u
początek, rzeczywiście będzie

307
00:15:29,213 --> 00:15:31,060
wskaźnik do węzła po prostu stworzył.

308
00:15:31,060 --> 00:15:33,280
Miejmy wizualizację tego,
bo myślę, że to pomoże.

309
00:15:33,280 --> 00:15:36,661
>> Więc oto nasza lista, składa się z
cztery elementy, węzeł zawierający 15,

310
00:15:36,661 --> 00:15:38,410
co wskazuje na węzeł
zawierający 9, która

311
00:15:38,410 --> 00:15:41,370
Wskazuje węzła zawierającej 13,
co wskazuje na węzeł zawierający

312
00:15:41,370 --> 00:15:44,840
10, który ma zerowy
wskaźnik w kolejnym wskaźnikiem

313
00:15:44,840 --> 00:15:47,010
tak, że to koniec listy.

314
00:15:47,010 --> 00:15:50,200
Dlatego chcemy, aby wstawić
nowy węzeł o wartości 12

315
00:15:50,200 --> 00:15:52,720
na początku
lista, co mamy robić?

316
00:15:52,720 --> 00:15:58,770
Cóż, po pierwsze, że malloc przestrzeń dla
węzeł, a następnie kładziemy 12 tam.

317
00:15:58,770 --> 00:16:02,211
>> Więc teraz mamy osiągnięcia
punkt decyzji, prawda?

318
00:16:02,211 --> 00:16:03,960
Mamy kilka
wskaźniki, które mogliśmy

319
00:16:03,960 --> 00:16:06,770
przenieść, który z nich należy pierwszy ruch?

320
00:16:06,770 --> 00:16:09,250
Powinniśmy się 12 wskaż polecenie
nowy szef list--

321
00:16:09,250 --> 00:16:13,020
i przepraszam, powinniśmy uczynić 12
wskazują na starym czele listy?

322
00:16:13,020 --> 00:16:15,319
A może powinniśmy powiedzieć, że
Teraz zaczyna się na liście 12.

323
00:16:15,319 --> 00:16:17,110
Istnieje rozróżnienie
tam, i przyjrzymy

324
00:16:17,110 --> 00:16:19,870
przy czym dzieje się tak w drugim.

325
00:16:19,870 --> 00:16:23,350
>> Jednak prowadzi to do
świetny temat na pasku bocznym

326
00:16:23,350 --> 00:16:26,280
który jest jednym z
najtrudniejszych rzeczy z połączonych list

327
00:16:26,280 --> 00:16:30,980
jest ułożenie wskazówki
w prawidłowej kolejności.

328
00:16:30,980 --> 00:16:34,520
Jeśli przenieść rzeczy w porządku,
może skończyć się przypadkowo

329
00:16:34,520 --> 00:16:36,050
osierocanie resztę listy.

330
00:16:36,050 --> 00:16:37,300
A oto przykład tego.

331
00:16:37,300 --> 00:16:40,540
Więc chodźmy na pomysł of--
dobrze, że właśnie stworzył 12.

332
00:16:40,540 --> 00:16:43,180
Wiemy, że 12 będzie
nowy szef listy,

333
00:16:43,180 --> 00:16:47,660
więc dlaczego nie możemy się poruszać
wskaźnik Lista tam zwrócić.

334
00:16:47,660 --> 00:16:49,070
>> OK, więc to jest dobre.

335
00:16:49,070 --> 00:16:51,560
Więc teraz, gdy ma 12 następny punkt?

336
00:16:51,560 --> 00:16:54,580
Mam na myśli, wizualnie widać
który to punkt do 15,

337
00:16:54,580 --> 00:16:57,250
jak ludzie to naprawdę dla nas oczywiste.

338
00:16:57,250 --> 00:17:00,300
Jak działa komputer wiedzieć?

339
00:17:00,300 --> 00:17:02,720
Nie mamy nic
wskazując na 15 już, prawda?

340
00:17:02,720 --> 00:17:05,869
>> Straciliśmy żadnego zdolność do powoływania się na 15.

341
00:17:05,869 --> 00:17:11,460
Nie możemy powiedzieć, nowa strzałkę obok równych
coś, tam nic nie ma.

342
00:17:11,460 --> 00:17:13,510
W rzeczywistości, mamy osieroconych
reszta listy

343
00:17:13,510 --> 00:17:16,465
w ten sposób, mamy
przypadkowo uszkodzony łańcuch.

344
00:17:16,465 --> 00:17:18,089
I na pewno nie chcesz, aby to zrobić.

345
00:17:18,089 --> 00:17:20,000
>> Warto więc wrócić i spróbować jeszcze raz.

346
00:17:20,000 --> 00:17:24,060
Być może to, co trzeba zrobić,
jest ustawienie 12 w następny wskaźnik

347
00:17:24,060 --> 00:17:28,290
do starego czele listy pierwszej,
Następnie możemy przejść do listy powyżej.

348
00:17:28,290 --> 00:17:30,420
Oraz tym, że jest to
odpowiedniej kolejności, że my

349
00:17:30,420 --> 00:17:32,836
należy postępować, gdy jesteśmy
pracy z pojedynczo połączonej listy.

350
00:17:32,836 --> 00:17:36,460
Zawsze chcemy podłączyć
nowy element do listy,

351
00:17:36,460 --> 00:17:41,010
Zanim podejmiemy tego rodzaju
ważny krok zmiany

352
00:17:41,010 --> 00:17:43,360
gdzie szef połączonej listy jest.

353
00:17:43,360 --> 00:17:46,740
Ponownie, to takie podstawową rzeczą,
Nie chcemy, aby stracić to.

354
00:17:46,740 --> 00:17:49,310
>> Dlatego chcemy, aby upewnić się, że
wszystko jest połączone w łańcuch,

355
00:17:49,310 --> 00:17:52,040
zanim przejdziemy ten wskaźnik.

356
00:17:52,040 --> 00:17:55,300
I tak będzie to prawidłowa kolejność,
który jest połączenie 12 na liście

357
00:17:55,300 --> 00:17:57,630
to znaczy, że lista zaczyna się 12.

358
00:17:57,630 --> 00:18:00,860
Jeśli wspomniana lista zaczyna się o 12, a
następnie próbował połączyć 12 do listy,

359
00:18:00,860 --> 00:18:02,193
widzieliśmy już, co się dzieje.

360
00:18:02,193 --> 00:18:04,920
Tracimy listę przez pomyłkę.

361
00:18:04,920 --> 00:18:06,740
>> OK, więc jeszcze jedno o czym rozmawiać.

362
00:18:06,740 --> 00:18:09,750
Co zrobić, jeśli chcemy pozbyć
cała związana listy na raz?

363
00:18:09,750 --> 00:18:11,750
Znowu jesteśmy mallocing
wszystkie te miejsca, a więc

364
00:18:11,750 --> 00:18:13,351
trzeba zwolnić go, gdy skończymy.

365
00:18:13,351 --> 00:18:15,350
Teraz chcemy, aby usunąć
cała lista powiązane.

366
00:18:15,350 --> 00:18:16,850
Cóż, to, co chcemy zrobić?

367
00:18:16,850 --> 00:18:20,460
>> Jeśli doszliśmy do pustego wskaźnika, możemy
Aby zatrzymać, inaczej, po prostu usuń

368
00:18:20,460 --> 00:18:23,420
reszta z listy, a następnie uwolnij mnie.

369
00:18:23,420 --> 00:18:28,890
Usuń resztę listy,
a następnie zwolnić bieżący węzeł.

370
00:18:28,890 --> 00:18:32,850
Co to brzmi jak,
technikę, mają rozmawialiśmy

371
00:18:32,850 --> 00:18:35,440
o wcześniej Czy to brzmi jak?

372
00:18:35,440 --> 00:18:39,560
Usuń wszyscy, a następnie
wrócić i skasować mnie.

373
00:18:39,560 --> 00:18:42,380
>> To rekurencji, jakie sprawiły, że
Problem trochę mniejszy,

374
00:18:42,380 --> 00:18:46,910
Mówimy usunięcie wszystkich
indziej, to możesz mnie usunąć.

375
00:18:46,910 --> 00:18:50,940
I dalej w dół drogi, że węzeł
powie, usuń wszyscy.

376
00:18:50,940 --> 00:18:53,940
Ale w końcu dojdziemy do
Punkt, w którym lista jest null,

377
00:18:53,940 --> 00:18:55,310
i to jest nasza sprawa bazowej.

378
00:18:55,310 --> 00:18:57,010
>> Warto więc spojrzeć na to,
i jak to może działać.

379
00:18:57,010 --> 00:18:59,759
Więc oto nasza lista, to jest to samo
listy byliśmy po prostu mówisz,

380
00:18:59,759 --> 00:19:00,980
i tam kroki.

381
00:19:00,980 --> 00:19:04,200
Jest dużo tekstu tutaj, ale
mam nadzieję, że wizualizacja pomoże.

382
00:19:04,200 --> 00:19:08,557
>> Więc have-- i również wyciągnął
do ramki o naszej ilustracji

383
00:19:08,557 --> 00:19:10,890
z naszego połączenia wideo w stosy,
i mam nadzieję, że to wszystko

384
00:19:10,890 --> 00:19:13,260
razem pokaże, co się dzieje.

385
00:19:13,260 --> 00:19:14,510
Więc tutaj jest nasz kod pseudokod.

386
00:19:14,510 --> 00:19:17,830
Jeśli dojdziemy null
wskaźnik, zatrzymać, w przeciwnym razie,

387
00:19:17,830 --> 00:19:21,320
usuń resztę listy,
następnie zwolnić bieżący węzeł.

388
00:19:21,320 --> 00:19:25,700
Więc teraz, list--
wskaźnik, że jesteśmy

389
00:19:25,700 --> 00:19:28,410
przechodząc do niszczenia punktów do 12.

390
00:19:28,410 --> 00:19:33,340
12 nie jest wskaźnikiem NULL, więc jesteśmy
zamiar usunąć resztę listy.

391
00:19:33,340 --> 00:19:35,450
>> Co jest usunięcie
Reszta z nas uczestniczy?

392
00:19:35,450 --> 00:19:37,950
Cóż, to znaczy, dokonywania
zadzwonić do zniszczenia, mówiąc:

393
00:19:37,950 --> 00:19:42,060
że 15 jest na początku
Reszta listy chcemy zniszczyć.

394
00:19:42,060 --> 00:19:47,480
A więc wezwanie do zniszczenia
12 jest trochę zawieszone.

395
00:19:47,480 --> 00:19:52,690
To zamrożone tam, czekając na
zadzwonić do zniszczenia 15, aby zakończyć swoją pracę.

396
00:19:52,690 --> 00:19:56,280
>> Cóż, 15 nie jest wskaźnikiem NULL, a
tak to się mówi, wszystko w porządku,

397
00:19:56,280 --> 00:19:58,450
dobrze, usunąć resztę listy.

398
00:19:58,450 --> 00:20:00,760
Reszta listy zaczyna
na 9, a więc musimy po prostu

399
00:20:00,760 --> 00:20:04,514
zaczekać do momentu usunięcia wszystkiego,
rzeczy, a potem wrócić i skasować mnie.

400
00:20:04,514 --> 00:20:06,680
Cóż 9 powie, dobrze,
Nie jestem pusty wskaźnik,

401
00:20:06,680 --> 00:20:09,020
tak, usuń resztę listę tutaj.

402
00:20:09,020 --> 00:20:11,805
A więc spróbuj i zniszczyć 13.

403
00:20:11,805 --> 00:20:15,550
13 mówi, że nie jestem pusty wskaźnik,
samo, przechodzi złotówki.

404
00:20:15,550 --> 00:20:17,930
10 nie jest wskaźnikiem NULL, 10
zawiera pustego wskaźnika,

405
00:20:17,930 --> 00:20:20,200
ale 10 nie sama w sobie jest
teraz wskaźnik NULL,

406
00:20:20,200 --> 00:20:22,470
i tak przechodzi złotówki też.

407
00:20:22,470 --> 00:20:25,560
>> A teraz lista punktów nie, to
naprawdę zwraca się do some--

408
00:20:25,560 --> 00:20:28,710
gdybym miał więcej miejsca na obraz,
to zwraca się do jakiegoś losowego miejsca

409
00:20:28,710 --> 00:20:29,960
że nie wiemy co to jest.

410
00:20:29,960 --> 00:20:34,680
Jest to wskaźnik NULL choć lista
jest dosłownie teraz ustawić to wartości null.

411
00:20:34,680 --> 00:20:36,820
Jest skierowany bezpośrednio w tym czerwonym polu.

412
00:20:36,820 --> 00:20:39,960
Dotarliśmy do pustego wskaźnika, więc
możemy zatrzymać, i gotowe.

413
00:20:39,960 --> 00:20:46,230
>> I tak, że rama jest now-- purpury u
góry stack-- to aktywna ramka,

414
00:20:46,230 --> 00:20:47,017
ale to się robi.

415
00:20:47,017 --> 00:20:48,600
Jeśli doszliśmy pustego wskaźnika, stop.

416
00:20:48,600 --> 00:20:51,290
My nic nie robimy,
nie może uwolnić pustego wskaźnika,

417
00:20:51,290 --> 00:20:55,070
nie malloc dowolny
Przestrzeń i tak skończymy.

418
00:20:55,070 --> 00:20:57,590
Więc tej ramki funkcji
jest zniszczony, a my

419
00:20:57,590 --> 00:21:00,930
resume-- możemy odebrać, gdzie zostawiliśmy
się z kolejnym najwyższym jeden, który

420
00:21:00,930 --> 00:21:02,807
Jest to ciemna niebieska ramka tutaj.

421
00:21:02,807 --> 00:21:04,390
Więc możemy odebrać prawo w którym skończyliśmy.

422
00:21:04,390 --> 00:21:06,598
Mamy usunięte reszty
Lista już, więc teraz jesteśmy

423
00:21:06,598 --> 00:21:08,000
zamiar uwolnić bieżących węzłów.

424
00:21:08,000 --> 00:21:12,920
Więc teraz możemy uwolnić ten węzeł, a teraz
dotarliśmy do końca funkcji.

425
00:21:12,920 --> 00:21:16,810
I tak, że rama funkcja jest zniszczona,
i odbiór na jasnoniebieskim jeden.

426
00:21:16,810 --> 00:21:20,650
>> Więc to says-- Już done--
usuwanie reszty listy, tak

427
00:21:20,650 --> 00:21:23,140
uwolnić bieżący węzeł.

428
00:21:23,140 --> 00:21:26,520
A teraz żółta ramka jest
powrotem na górze stosu.

429
00:21:26,520 --> 00:21:29,655
A więc, jak widać, jesteśmy teraz
zniszczenia listę od prawej do lewej.

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

431
00:21:33,710 --> 00:21:37,280
>> Co by się stało, gdyby,
gdybyśmy zrobili rzeczy w niewłaściwy sposób?

432
00:21:37,280 --> 00:21:39,410
Tak jak kiedy próbowaliśmy
dodać element.

433
00:21:39,410 --> 00:21:41,909
Jeśli zawiedli łańcuch, jeśli to
nie podłączyć wskaźniki

434
00:21:41,909 --> 00:21:44,690
w odpowiedniej kolejności, jeśli będziemy
tylko uwolnił pierwszy element,

435
00:21:44,690 --> 00:21:47,420
jeśli tylko uwolnił
szef liście, teraz my

436
00:21:47,420 --> 00:21:49,642
nie sposób odnieść się do
reszta listy.

437
00:21:49,642 --> 00:21:51,350
I tak musielibyśmy
osierocone wszystko,

438
00:21:51,350 --> 00:21:53,880
mielibyśmy co
zwany przeciek pamięci.

439
00:21:53,880 --> 00:21:56,800
Jeśli pamiętacie z naszego filmu
na dynamicznej alokacji pamięci,

440
00:21:56,800 --> 00:21:58,650
że nie jest to bardzo dobra rzecz.

441
00:21:58,650 --> 00:22:00,810
>> Tak jak powiedziałem, nie
kilka operacji

442
00:22:00,810 --> 00:22:04,010
że musimy użyć do pracy
z listy skutecznie powiązane.

443
00:22:04,010 --> 00:22:08,430
I można zauważyć, że pominięto jeden,
usuwanie pojedynczy element z innej

444
00:22:08,430 --> 00:22:09,064
lista.

445
00:22:09,064 --> 00:22:10,980
Powód to zrobiłem
Jest to właściwie rodzaj

446
00:22:10,980 --> 00:22:14,360
trudne, aby myśleć o tym, jak usunąć
pojedynczy element z punktu A pojedynczo

447
00:22:14,360 --> 00:22:15,600
połączonej listy.

448
00:22:15,600 --> 00:22:19,950
Musimy być w stanie przeskoczyć
coś w liście, który

449
00:22:19,950 --> 00:22:22,975
oznacza, że ​​dostać się do point-- my
chcesz usunąć ten node--

450
00:22:22,975 --> 00:22:25,350
ale aby zrobić to tak, że
nie tracą żadnych informacji,

451
00:22:25,350 --> 00:22:30,530
musimy połączyć to
Węzeł tutaj, tutaj.

452
00:22:30,530 --> 00:22:33,390
>> Więc pewnie zrobił źle
z punktu widzenia.

453
00:22:33,390 --> 00:22:36,830
Więc jesteśmy na początku naszej
lista, jesteśmy przebiega przez,

454
00:22:36,830 --> 00:22:40,510
Chcemy, aby usunąć ten węzeł.

455
00:22:40,510 --> 00:22:43,440
Jeśli tylko go usunąć,
mamy uszkodzony łańcuch.

456
00:22:43,440 --> 00:22:45,950
Ten węzeł tutaj
odnosi się do wszystkiego,

457
00:22:45,950 --> 00:22:48,260
zawiera łańcuch stąd na zewnątrz.

458
00:22:48,260 --> 00:22:51,190
>> Więc co trzeba zrobić w rzeczywistości
po tym jak dostać się do tego punktu,

459
00:22:51,190 --> 00:22:56,670
to musimy cofnąć się jeden, a
podłączyć węzeł nad do tego węzła,

460
00:22:56,670 --> 00:22:58,590
więc można następnie usunąć
jeden w środku.

461
00:22:58,590 --> 00:23:02,120
Ale pojedynczo związane listy nie
zapewniają nam drogę, do tyłu.

462
00:23:02,120 --> 00:23:05,160
Więc musimy je zachować
dwa wskaźniki, i przenieść je

463
00:23:05,160 --> 00:23:09,527
rodzaj off kroku, jeden za
inne, jak idziemy, lub dostać się do punktu

464
00:23:09,527 --> 00:23:11,110
a następnie wysłać kolejny wskaźnik, dzięki.

465
00:23:11,110 --> 00:23:13,150
I jak widać, to
może trochę niechlujnie.

466
00:23:13,150 --> 00:23:15,360
Na szczęście mamy
inny sposób na rozwiązanie, które,

467
00:23:15,360 --> 00:23:17,810
kiedy mówimy o podwójnie połączonych listach.

468
00:23:17,810 --> 00:23:20,720
>> Jestem Doug Lloyd, to CS50.

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