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

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

3
00:00:05,670 --> 00:00:08,560
>> DOUG Lloyd: OK, joten on
tässä vaiheessa tietenkin

4
00:00:08,560 --> 00:00:15,300
Selvitimme jo paljon perusasiat C.
Tiedämme paljon muuttujia, taulukot,

5
00:00:15,300 --> 00:00:17,610
osoittimet, kaikki hyvät jutut.

6
00:00:17,610 --> 00:00:21,610
Ne ovat kaikki tavallaan rakennettu
vuonna nähdä niin perustekijät,

7
00:00:21,610 --> 00:00:23,880
mutta voimme tehdä enemmän, eikö?

8
00:00:23,880 --> 00:00:27,930
Voimme yhdistää asioita
yhdessä kiinnostavalla tavalla.

9
00:00:27,930 --> 00:00:31,010
>> Ja niin tehdään se, aloitetaan
sektoreita, mitä C antaa meille,

10
00:00:31,010 --> 00:00:35,270
ja alkaa luoda omia tietoja
rakenteet näiden rakennus

11
00:00:35,270 --> 00:00:40,590
lohkot yhdessä tehdä jotain
todella arvokas, hyödyllinen.

12
00:00:40,590 --> 00:00:43,420
Yksi tapa tehdä tämä on
puhua kokoelmista.

13
00:00:43,420 --> 00:00:48,360
Joten toistaiseksi meillä on ollut yksi millaisia ​​tietoja
rakenne edustaa kokoelmia

14
00:00:48,360 --> 00:00:51,030
samankaltaisten arvot, samat arvot.

15
00:00:51,030 --> 00:00:52,350
Se olisi jono.

16
00:00:52,350 --> 00:00:57,020
Meillä on kokoelmia kokonaislukuja, tai
kokoelmat merkkiä ja niin edelleen.

17
00:00:57,020 --> 00:01:00,890
>> Rakenteet ovat myös eräänlainen tietojen
rakenne tietojen keräämiseksi,

18
00:01:00,890 --> 00:01:03,220
mutta se ei ole keräämiseksi kuten arvoja.

19
00:01:03,220 --> 00:01:08,090
Se yleensä sekoittaa erilaiset tiedot
yhdessä sisällä yhden laatikon.

20
00:01:08,090 --> 00:01:10,750
Mutta se ei ole itse
käytetään ketjun yhdessä

21
00:01:10,750 --> 00:01:16,920
tai liittää yhteen samankaltaisia
kohteita, kuten array.

22
00:01:16,920 --> 00:01:20,960
Taulukot ovat hyvin
elementti etsiä, mutta muistuttaa

23
00:01:20,960 --> 00:01:24,262
että se on hyvin vaikeaa
lisättävän array,

24
00:01:24,262 --> 00:01:26,470
ellei olemme lisäämällä at
aivan lopussa, että jono.

25
00:01:26,470 --> 00:01:29,730
>> Ja paras esimerkki minulla on
että on lisäyslajittelun.

26
00:01:29,730 --> 00:01:31,650
Jos muistatte meidän video
sijoittamista lajitella,

27
00:01:31,650 --> 00:01:34,110
siellä oli paljon
kustannuksella mukana ottaa

28
00:01:34,110 --> 00:01:37,970
poimia elementtejä, ja siirtää niitä
pois tieltä sopivaksi jotain

29
00:01:37,970 --> 00:01:41,290
keskelle teidän array.

30
00:01:41,290 --> 00:01:44,690
Paneelit kärsivät myös toinen
ongelma, joka on joustamattomuus.

31
00:01:44,690 --> 00:01:47,150
Kun me julistamme array,
saamme yhden ampui sitä.

32
00:01:47,150 --> 00:01:49,790
Saamme sanoa, haluan
Tämän monia elementtejä.

33
00:01:49,790 --> 00:01:51,940
Voi olla 100, se voisi
olla 1000, se saattaa

34
00:01:51,940 --> 00:01:55,930
olla X, jossa x on numero, että käyttäjä
antoi meille nopeasti tai komento

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

36
00:01:56,630 --> 00:01:59,905
>> Mutta me vain saada yksi laukaus sitä, me
älä päästä sitten sanoa oh, itse asiassa

37
00:01:59,905 --> 00:02:04,360
tarvitaan 101, tai tarvitsin x + 20.

38
00:02:04,360 --> 00:02:07,910
Liian myöhäistä, olemme jo ilmoittanut
array, ja jos haluamme saada 101 tai X

39
00:02:07,910 --> 00:02:12,050
plus 20, meidän täytyy julistaa
täysin eri array,

40
00:02:12,050 --> 00:02:15,540
kopioi kaikki taulukon alkiot
yli, ja sitten meillä on riittävästi.

41
00:02:15,540 --> 00:02:19,880
Ja entä jos olemme väärässä jälleen, mitä
jos me todella tarvitsemme 102, tai X + 40,

42
00:02:19,880 --> 00:02:21,970
meidän täytyy tehdä tätä uudelleen.

43
00:02:21,970 --> 00:02:26,250
Joten he ovat hyvin joustamaton
koon muuttamisen tietomme,

44
00:02:26,250 --> 00:02:29,360
mutta jos yhdistämme yhteen joitakin
perusasiat, että olemme jo

45
00:02:29,360 --> 00:02:33,230
oppinut viitteitä ja rakenteita,
erityisesti käyttäen dynaaminen muisti

46
00:02:33,230 --> 00:02:36,180
jakamista malloc, me
voi laittaa nämä palaset yhteen

47
00:02:36,180 --> 00:02:40,960
luoda uutta tietoa structure--
yksittäin linkitetty lista voisimme say--

48
00:02:40,960 --> 00:02:45,400
jonka avulla voimme kasvaa ja
kutistua kokoelma arvojen

49
00:02:45,400 --> 00:02:48,800
ja meillä ei ole mitään hukkaan tilaa.

50
00:02:48,800 --> 00:02:53,320
>> Joten jälleen, me kutsumme tätä ajatusta,
käsitystä, linkitetty lista.

51
00:02:53,320 --> 00:02:56,320
Erityisesti tämän videon olemme
puhumme yksittäin linkitetty lista,

52
00:02:56,320 --> 00:02:59,185
ja sitten toinen video jutellaan
noin kaksinkertaisesti liittyvät luettelot, joka

53
00:02:59,185 --> 00:03:01,560
on vain muunnelma teemasta täällä.

54
00:03:01,560 --> 00:03:05,200
Mutta yksittäin linkitetty lista
koostuu solmut,

55
00:03:05,200 --> 00:03:08,559
solmut vain on abstrakti term--
se on vain jotain Soitan

56
00:03:08,559 --> 00:03:10,350
se eräänlainen
rakenne, periaatteessa, olen?

57
00:03:10,350 --> 00:03:16,190
Juuri menossa kutsua sitä node-- ja tämä
solmulla on kaksi jäsentä, tai kaksi kenttää.

58
00:03:16,190 --> 00:03:20,300
Se on tietoja, yleensä
kokonaisluku, merkki kellua,

59
00:03:20,300 --> 00:03:23,790
tai voisi olla jokin muu tietolaji
että olet määritetty tyyppi def.

60
00:03:23,790 --> 00:03:29,290
Ja se sisältää osoittimen
toisen solmun samaa tyyppiä.

61
00:03:29,290 --> 00:03:34,710
>> Joten meillä on kaksi asiaa sisällä
tämä solmu, tiedot ja osoitin

62
00:03:34,710 --> 00:03:36,380
toiseen solmuun.

63
00:03:36,380 --> 00:03:39,370
Ja jos alkaa visualisoida
tämän, voit ajatella sitä

64
00:03:39,370 --> 00:03:42,280
kuten ketju solmuja, jotka
on liitetty yhteen.

65
00:03:42,280 --> 00:03:45,070
Meillä on ensimmäinen solmu, se
sisältää dataa, ja osoitin

66
00:03:45,070 --> 00:03:49,110
toiselle solmulle, joka sisältää
datan, ja osoitin kolmanteen solmuun.

67
00:03:49,110 --> 00:03:52,940
Ja niin siksi me kutsumme sitä
linkitetty lista, ne toisiinsa.

68
00:03:52,940 --> 00:03:56,070
>> Mitä tämä erityinen
solmu rakenne näyttää?

69
00:03:56,070 --> 00:04:01,120
No, jos muistatte meidän video
määritellään räätälöidyt tyypit, tyypin def,

70
00:04:01,120 --> 00:04:05,400
voimme määritellä structure-- ja
Define rakenne näin.

71
00:04:05,400 --> 00:04:11,240
tyepdef struct sllist, ja sitten olen
käyttämällä sanaa arvo tähän mielivaltaisesti

72
00:04:11,240 --> 00:04:13,891
osoittamaan mitään tietotyyppi todella.

73
00:04:13,891 --> 00:04:16,890
Voisit siirtää kokonaisluku tai float,
sinulla voisi olla mitä haluat.

74
00:04:16,890 --> 00:04:19,389
Se ei rajoitu vain
kokonaisluvut, tai jotain sellaista.

75
00:04:19,389 --> 00:04:22,790
Joten arvo on vain mielivaltainen
tietotyyppi, ja sitten osoitin

76
00:04:22,790 --> 00:04:26,310
toisen solmun samaa tyyppiä.

77
00:04:26,310 --> 00:04:29,690
>> Nyt, siellä on pieni saalis
täällä määritellään rakenne

78
00:04:29,690 --> 00:04:33,030
kun se on itse viite rakenne.

79
00:04:33,030 --> 00:04:35,340
Minun on väliaikainen
nimi minun rakennetta.

80
00:04:35,340 --> 00:04:37,640
Lopussa päivän I
selvästi halua kutsua sitä

81
00:04:37,640 --> 00:04:43,030
SLL solmu, joka on viime kädessä uusi
nimi osa minun tyyppiä määritelmän,

82
00:04:43,030 --> 00:04:47,450
mutta en voi käyttää SLL solmu
keskellä tämä.

83
00:04:47,450 --> 00:04:51,430
Syynä on, en ole
luotu tyyppi nimeltä SLL solmu

84
00:04:51,430 --> 00:04:55,200
kunnes osuin tämä viimeinen kohta täällä.

85
00:04:55,200 --> 00:04:59,720
Tuohon asti, minun täytyy saada
toinen tapa viitata tietojen tyyppi.

86
00:04:59,720 --> 00:05:02,440
>> Ja tämä on itsestään
viitetietojen tyyppi.

87
00:05:02,440 --> 00:05:06,314
Se, s tietotyyppi
rakenne, joka sisältää tiedot,

88
00:05:06,314 --> 00:05:08,480
ja osoitin toiseen
rakenne samaa tyyppiä.

89
00:05:08,480 --> 00:05:11,750
Joten minun täytyy pystyä viitata
Tämä datatyyppi ainakin väliaikaisesti,

90
00:05:11,750 --> 00:05:14,910
joten antaa sille tilapäisen
nimi struct sllist

91
00:05:14,910 --> 00:05:18,540
sallii minun sitten sanoa haluan
osoitin toiseen struct sllist,

92
00:05:18,540 --> 00:05:24,690
struct sllist tähti, ja sitten
kun olen suorittanut määritelmä,

93
00:05:24,690 --> 00:05:27,220
Voin nyt soittaa tämäntyyppisiä SLL solmu.

94
00:05:27,220 --> 00:05:30,520
>> Joten siksi näet siellä
väliaikainen nimi täällä,

95
00:05:30,520 --> 00:05:31,879
mutta pysyvä nimi tähän.

96
00:05:31,879 --> 00:05:33,920
Joskus saatat nähdä
määritelmät rakenne,

97
00:05:33,920 --> 00:05:36,570
esimerkiksi, että eivät ole
itse viite, että

98
00:05:36,570 --> 00:05:39,390
ei ole määrittelyksi nimi tähän.

99
00:05:39,390 --> 00:05:43,040
Se olisi vain sanoa typedef struct,
avaa kihara ahdin ja sitten määritellä se.

100
00:05:43,040 --> 00:05:45,620
Mutta jos olet struct on itsenäinen
viite, koska tämä on,

101
00:05:45,620 --> 00:05:49,010
sinun täytyy määrittää
väliaikainen tyypin nimi.

102
00:05:49,010 --> 00:05:51,310
Mutta lopulta, nyt
että olemme tehneet tämän,

103
00:05:51,310 --> 00:05:53,620
voimme vain viitata
Nämä solmut, nämä yksiköt,

104
00:05:53,620 --> 00:05:57,900
kuten SLL solmut tarkoituksiin
muusta tämän videon.

105
00:05:57,900 --> 00:06:00,900
>> Selvä, joten osaamme
luoda linkitetyn listan solmu.

106
00:06:00,900 --> 00:06:03,240
Tiedämme miten määritellä
linkitetyn listan solmu.

107
00:06:03,240 --> 00:06:06,670
Nyt, jos aiomme aloittaa
käyttää niitä kerätä tietoa,

108
00:06:06,670 --> 00:06:10,360
siellä on pari toiminnassamme
täytyy ymmärtää ja työskennellä.

109
00:06:10,360 --> 00:06:12,860
Meidän täytyy tietää, miten luoda
linkitetty lista tyhjästä.

110
00:06:12,860 --> 00:06:14,901
Jos ei ole luettelo jo,
haluamme aloittaa yksi.

111
00:06:14,901 --> 00:06:16,960
Joten meidän on pystyttävä
luoda linkitetty lista,

112
00:06:16,960 --> 00:06:19,130
meidän on luultavasti etsiä
kautta linkkilista

113
00:06:19,130 --> 00:06:21,830
löytää elementti etsimme.

114
00:06:21,830 --> 00:06:24,430
Meidän täytyy pystyä lisätä
uusia asioita listaan,

115
00:06:24,430 --> 00:06:25,930
haluamme luettelo pystyä kasvamaan.

116
00:06:25,930 --> 00:06:28,638
Ja samalla haluamme pystyä
poistaa asioita listalta,

117
00:06:28,638 --> 00:06:30,250
haluamme luettelo pystyä kutistua.

118
00:06:30,250 --> 00:06:32,160
Ja lopussa meidän
ohjelmat, erityisesti

119
00:06:32,160 --> 00:06:34,550
Jos muistatte, että olemme
dynaamisesti jaetut muisti

120
00:06:34,550 --> 00:06:38,337
rakentaa nämä luettelot tyypillisesti,
haluamme vapauttaa kaikki tämä muisti

121
00:06:38,337 --> 00:06:39,670
kun olemme tehneet työtä se.

122
00:06:39,670 --> 00:06:44,627
Ja niin meidän täytyy pystyä poistamaan
koko linkitetty lista yhdellä epäonnistua syöksy.

123
00:06:44,627 --> 00:06:46,460
Joten mene läpi
jotkut näistä toiminnoista

124
00:06:46,460 --> 00:06:51,192
ja kuinka voisimme visualisoida niitä,
puhuu pseudokoodilla koodi erityisesti.

125
00:06:51,192 --> 00:06:53,150
Joten haluamme luoda
linkitetty lista, joten ehkä me

126
00:06:53,150 --> 00:06:56,480
haluat määrittää funktion
tämän prototyyppi.

127
00:06:56,480 --> 00:07:01,690
SLL solmu tähti, luoda, ja olen ohimennen
yksi argumentti, jotkut mielivaltaista dataa

128
00:07:01,690 --> 00:07:05,530
tyyppi jälleen, joidenkin mielivaltaista tietojen tyyppi.

129
00:07:05,530 --> 00:07:10,482
Mutta olen returning-- tämän toiminnon pitäisi
palata minulle osoitin, että yksittäin

130
00:07:10,482 --> 00:07:11,190
linkitetty lista solmu.

131
00:07:11,190 --> 00:07:14,050
Jälleen me yritämme luoda
linkitetty lista tyhjästä,

132
00:07:14,050 --> 00:07:17,900
joten minun täytyy osoitin
että luettelosta, kun olen valmis.

133
00:07:17,900 --> 00:07:19,420
>> Mitkä ovat vaiheista täällä?

134
00:07:19,420 --> 00:07:20,960
No, ensimmäinen asia olen
aikoo tehdä on dynaamisesti

135
00:07:20,960 --> 00:07:22,550
jakaa tilaa uusi solmu.

136
00:07:22,550 --> 00:07:26,689
Jälleen Luomme se tyhjästä
ilma, joten meidän on malloc tilaa se.

137
00:07:26,689 --> 00:07:28,480
Ja tietenkin, heti
kun olemme malloc,

138
00:07:28,480 --> 00:07:31,692
aina varmista, että meidän
pointer-- emme saaneet takaisin null.

139
00:07:31,692 --> 00:07:33,650
Koska jos yritämme
kunnioitus nollaosoittimen,

140
00:07:33,650 --> 00:07:36,190
aiomme kärsiä
segfault ja emme halua että.

141
00:07:36,190 --> 00:07:39,510
>> Sitten haluamme täyttää alalla,
haluamme alustaa arvon alalla

142
00:07:39,510 --> 00:07:41,690
ja alustaa seuraavaan kenttään.

143
00:07:41,690 --> 00:07:45,450
Ja sitten me haluamme to-- lopulta kuin
toiminto prototyyppi indicates-- haluamme

144
00:07:45,450 --> 00:07:49,940
palata osoitin SLL solmuun.

145
00:07:49,940 --> 00:07:51,710
Joten mitä tehdä tämä näyttää visuaalisesti?

146
00:07:51,710 --> 00:07:55,230
No, ensimmäinen aiomme dynaamisesti
jakaa tilaa uuden SLL solmu,

147
00:07:55,230 --> 00:07:58,320
joten malloc-- se
visuaalinen esitys

148
00:07:58,320 --> 00:08:00,020
solmun me juuri luotu.

149
00:08:00,020 --> 00:08:02,757
Ja me varmista
se ei ole null-- tässä tapauksessa,

150
00:08:02,757 --> 00:08:04,840
kuva ei olisi
saapunut jos se oli tyhjä,

151
00:08:04,840 --> 00:08:07,298
olisimme loppuu muisti,
joten olemme hyvä mennä sinne.

152
00:08:07,298 --> 00:08:10,200
Joten nyt olemme vaiheeseen C,
alustaa solmut arvo kenttään.

153
00:08:10,200 --> 00:08:12,280
No, joka perustuu tämä toiminto
soittaa Käytän tässä,

154
00:08:12,280 --> 00:08:16,700
näyttää haluan välittää 6,
niin minä 6 arvokentässä.

155
00:08:16,700 --> 00:08:18,865
Nyt alustaa seuraavaan kenttään.

156
00:08:18,865 --> 00:08:21,640
No, mitä aion tehdä siellä,
ei ole mitään vieressä, oikealla,

157
00:08:21,640 --> 00:08:23,600
tämä on ainoa asia luettelossa.

158
00:08:23,600 --> 00:08:27,206
Niin mitä seuraavaksi asia listassa?

159
00:08:27,206 --> 00:08:29,660
>> Se pitäisi ei viitannut mihinkään, oikealle.

160
00:08:29,660 --> 00:08:33,600
Ei ole mitään muuta siellä, niin mikä on
käsite tiedämme se nothing--

161
00:08:33,600 --> 00:08:35,638
viitteitä mitään?

162
00:08:35,638 --> 00:08:37,929
Sen pitäisi olla ehkä haluamme
laittaa nollaosoittimen siellä,

163
00:08:37,929 --> 00:08:40,178
ja minä edustavat null
osoittimen juuri punainen laatikko,

164
00:08:40,178 --> 00:08:41,559
emme voi mennä pidemmälle.

165
00:08:41,559 --> 00:08:44,430
Kuten näemme hieman myöhemmin,
saamme lopulta ketjut

166
00:08:44,430 --> 00:08:46,330
nuolia yhdistää
Nämä solmut yhdessä,

167
00:08:46,330 --> 00:08:48,480
mutta kun osut
punainen laatikko, joka on null,

168
00:08:48,480 --> 00:08:51,150
emme voi mennä pidemmälle,
se luettelon loppuun.

169
00:08:51,150 --> 00:08:53,960
>> Ja lopuksi, me vain haluamme
palata osoitin tähän solmuun.

170
00:08:53,960 --> 00:08:56,160
Joten me kutsumme sitä uutta,
ja palaa uuden

171
00:08:56,160 --> 00:08:59,370
joten sitä voidaan käyttää
mitä toimintoa luonut.

172
00:08:59,370 --> 00:09:03,100
Joten siellä mennään, Olemme luoneet yksittäin
linkitetty lista solmu tyhjästä,

173
00:09:03,100 --> 00:09:05,920
ja nyt meillä on lista voimme työskennellä.

174
00:09:05,920 --> 00:09:08,260
>> Nyt, sanokaamme meillä jo
on suuri ketju,

175
00:09:08,260 --> 00:09:09,800
ja haluamme löytää jotain se.

176
00:09:09,800 --> 00:09:12,716
Ja haluamme toiminto, joka menee
palata tosi tai epätosi riippuen

177
00:09:12,716 --> 00:09:15,840
onko arvo on olemassa kyseisessä luettelossa.

178
00:09:15,840 --> 00:09:18,160
Toiminto prototyyppi, tai
ilmoituksen, että toiminto,

179
00:09:18,160 --> 00:09:23,320
voisi näyttää this-- bool löytää, ja
sitten haluamme kulkea kaksi perustelua.

180
00:09:23,320 --> 00:09:26,996
>> Ensimmäinen, on osoitin
ensimmäinen osa linkitetyn listan.

181
00:09:26,996 --> 00:09:29,620
Tämä on todella jotain sinun
aina haluavat seurata,

182
00:09:29,620 --> 00:09:33,110
ja itse asiassa voi olla jotain, joka
edes laittaa globaali muuttuja.

183
00:09:33,110 --> 00:09:35,360
Kun olet luonut listan,
aina, aina

184
00:09:35,360 --> 00:09:38,990
haluavat seurata hyvin
ensimmäinen osa luettelosta.

185
00:09:38,990 --> 00:09:43,690
Näin voit viitata kaikki muut
elementit vain seuraava ketjun,

186
00:09:43,690 --> 00:09:47,300
ilman pitää viitteitä
ehjä jokaiseen elementtiin.

187
00:09:47,300 --> 00:09:50,920
Sinun tarvitsee vain seurata ensimmäisen
yksi jos he kaikki ketjuttaa.

188
00:09:50,920 --> 00:09:52,460
>> Ja sitten toinen asia
olemme ohimennen uudelleen

189
00:09:52,460 --> 00:09:54,376
on mielivaltaisesti some--
mitä tietotyyppi olemme

190
00:09:54,376 --> 00:09:59,640
etsivät siellä on sisällä
toivottavasti yksi solmujen luetteloon.

191
00:09:59,640 --> 00:10:00,980
Mitä ovat vaiheet?

192
00:10:00,980 --> 00:10:04,250
No, ensimmäinen asia mitä teemme on
luomme poikittainen osoitin

193
00:10:04,250 --> 00:10:06,015
osoittaa luetteloihin päähän.

194
00:10:06,015 --> 00:10:08,890
No, miksi me teemme, että olemme jo
on osoitin luettelot pään,

195
00:10:08,890 --> 00:10:10,974
miksi emme siirrä että yksi noin?

196
00:10:10,974 --> 00:10:13,140
No, kuten juuri sanoin,
se on todella tärkeää meille

197
00:10:13,140 --> 00:10:17,580
aina seurata
ensimmäinen elementti luettelosta.

198
00:10:17,580 --> 00:10:21,270
Ja niin se on itse asiassa parempi
luoda päällekkäisiä kyseisen,

199
00:10:21,270 --> 00:10:25,350
ja käyttää sitä liikkua niin emme koskaan
vahingossa siirtää pois, tai aina

200
00:10:25,350 --> 00:10:30,430
on osoitin jossain vaiheessa, että on
aivan ensimmäinen osa luettelosta.

201
00:10:30,430 --> 00:10:33,290
Joten on parempi luoda
toisessa, että käytämme liikkua.

202
00:10:33,290 --> 00:10:35,877
>> Sitten vain vertailla, onko
arvo kentän että solmu

203
00:10:35,877 --> 00:10:38,960
on mitä etsimme, ja jos se on
ei, me vain siirry seuraavaan solmuun.

204
00:10:38,960 --> 00:10:41,040
Ja me pitää tehdä, että
yli, ja yli, ja yli,

205
00:10:41,040 --> 00:10:44,811
kunnes joko löytää
elementti, tai me osuma

206
00:10:44,811 --> 00:10:47,310
null-- olemme päättynyt
luettelon ja se ei ole siellä.

207
00:10:47,310 --> 00:10:50,540
Tämä toivottavasti tutulta
sinulle vain lineaarinen haku,

208
00:10:50,540 --> 00:10:54,430
me vain jäljittelevän sitä
yksittäin linkitetyn listan rakenne

209
00:10:54,430 --> 00:10:56,280
käyttämisen sijaan array tehdä se.

210
00:10:56,280 --> 00:10:58,210
>> Joten tässä on esimerkki
yksittäin linkitetyn listan.

211
00:10:58,210 --> 00:11:00,043
Tämä yksi koostuu
viisi solmua, ja meillä on

212
00:11:00,043 --> 00:11:04,330
osoitin johtaja
luettelo, jota kutsutaan lista.

213
00:11:04,330 --> 00:11:07,385
Ensimmäinen asia, jota haluamme tehdä, on
jälleen, luoda että kulkea osoitin.

214
00:11:07,385 --> 00:11:09,760
Joten meillä on nyt kaksi osoitinta
että kohta sama asia.

215
00:11:09,760 --> 00:11:15,025
>> Nyt, huomaa tässä myös, en
on malloc mitään tilaa Trav.

216
00:11:15,025 --> 00:11:18,970
En sanonut Trav vastaa malloc
jotain, joka solmu on jo olemassa,

217
00:11:18,970 --> 00:11:21,160
että muistitilaa on jo olemassa.

218
00:11:21,160 --> 00:11:24,290
Joten kaikki Olen todella tekee on
luomalla uuden osoitin sen.

219
00:11:24,290 --> 00:11:28,210
En mallocing lisää
tilaa, vain nyt kaksi osoitinta

220
00:11:28,210 --> 00:11:31,370
osoittaa sama asia.

221
00:11:31,370 --> 00:11:33,710
>> Joten on 2 mitä etsin?

222
00:11:33,710 --> 00:11:37,220
No, ei, joten sen sijaan olen
aikoo siirtyä seuraavaan.

223
00:11:37,220 --> 00:11:41,740
Joten periaatteessa sanoisin,
trav vastaa trav seuraava.

224
00:11:41,740 --> 00:11:43,630
On 3 mitä etsin, ei.

225
00:11:43,630 --> 00:11:45,780
Joten olen edelleen mennä
kautta, kunnes lopulta

226
00:11:45,780 --> 00:11:48,690
saada 6, joka on mitä etsin
sillä perusteella funktiokutsua

227
00:11:48,690 --> 00:11:51,600
Minulla on huipulla
siellä, ja niin olen valmis.

228
00:11:51,600 --> 00:11:54,150
>> Nyt, mitä jos elementti olen
etsimässä ei ole luettelossa,

229
00:11:54,150 --> 00:11:55,510
Onko se vielä menossa töihin?

230
00:11:55,510 --> 00:11:57,120
No, huomaa, että luettelo
tässä hieman toisenlainen,

231
00:11:57,120 --> 00:11:59,410
ja tämä on toinen asia, joka on
tärkeää liittyvät luettelot,

232
00:11:59,410 --> 00:12:01,780
sinun ei tarvitse säilyttää
niitä missään tietyssä järjestyksessä.

233
00:12:01,780 --> 00:12:05,390
Voit, jos haluat, mutta
olet ehkä jo huomannut

234
00:12:05,390 --> 00:12:09,310
että emme pitää kirjaa
mitä numero elementti olemme.

235
00:12:09,310 --> 00:12:13,150
>> Ja se on eräänlainen yhden kaupan me
on kanssa linkitetty lista säkeet paneelit,

236
00:12:13,150 --> 00:12:15,300
se meillä ei ole
random access enää.

237
00:12:15,300 --> 00:12:18,150
Emme voi vain sanoa, haluan
mennä 0. elementti,

238
00:12:18,150 --> 00:12:21,410
tai 6. osa minun array,
jota voin tehdä array.

239
00:12:21,410 --> 00:12:25,080
En voi sanoa haluan mennä
0. elementti, tai 6. elementti,

240
00:12:25,080 --> 00:12:30,360
tai 25. osa minun linkitetty lista,
ei ole indeksiä niihin liittyviä.

241
00:12:30,360 --> 00:12:33,660
Ja niin se ei ole oikeastaan ​​väliä
jos säilytämme lista järjestyksessä.

242
00:12:33,660 --> 00:12:36,080
Jos haluat sinua
varmasti voi, mutta siellä on

243
00:12:36,080 --> 00:12:38,567
mitään syytä, miksi ne tarvitsevat
säilytettävä missä tahansa järjestyksessä.

244
00:12:38,567 --> 00:12:40,400
Joten jälleen, yritetään ja
löytää 6 tässä luettelossa.

245
00:12:40,400 --> 00:12:43,200
No, me alkavat
alkaa, emme löydä 6,

246
00:12:43,200 --> 00:12:47,690
ja sitten jatkamme ei löytää
6, kunnes me lopulta päästä tänne.

247
00:12:47,690 --> 00:12:52,790
Joten nyt trav pistettä solmuun
sisältävät 8, ja kuusi ei ole siellä.

248
00:12:52,790 --> 00:12:55,250
>> Niin seuraava askel olisi
Siirry seuraavaan osoitin,

249
00:12:55,250 --> 00:12:57,440
niin sanoa trav vastaa Trav seuraava.

250
00:12:57,440 --> 00:13:00,750
No, trav seuraavaksi, merkitty
punainen laatikko siellä, on nolla.

251
00:13:00,750 --> 00:13:03,020
Joten ei muuta paikkaa minne
mennä, ja niin tässä vaiheessa

252
00:13:03,020 --> 00:13:06,120
voimme päätellä, että olemme saavuttaneet
loppuun linkitetyn listan,

253
00:13:06,120 --> 00:13:07,190
ja 6 ei ole siellä.

254
00:13:07,190 --> 00:13:10,980
Ja se olisi palautettava
väärä tässä tapauksessa.

255
00:13:10,980 --> 00:13:14,540
>> OK, miten voimme lisätä uuden
solmun linkitetty lista?

256
00:13:14,540 --> 00:13:17,310
Joten olemme pystyneet luomaan
linkitetty lista tyhjästä,

257
00:13:17,310 --> 00:13:19,370
mutta me luultavasti halua
rakentaa ketju eikä

258
00:13:19,370 --> 00:13:22,620
luoda joukko erillisiä listoja.

259
00:13:22,620 --> 00:13:25,700
Haluamme olla yksi luettelosta
on joukko solmuja se,

260
00:13:25,700 --> 00:13:28,040
ei nippu luettelot yhden solmun.

261
00:13:28,040 --> 00:13:31,260
Joten emme voi vain pitää käyttämällä Luo
toiminto määrittelimme aikaisemmin, nyt meillä

262
00:13:31,260 --> 00:13:33,860
haluat lisätä osaksi
luettelo jo olemassa.

263
00:13:33,860 --> 00:13:36,499
>> Joten tässä tapauksessa, menemme
kulkea kaksi argumenttia,

264
00:13:36,499 --> 00:13:39,290
osoitin johtaja, joka
linkitetty lista, että haluamme lisätä.

265
00:13:39,290 --> 00:13:40,910
Jälleen siksi se on niin
tärkeää, että aina

266
00:13:40,910 --> 00:13:43,400
seurata sitä, koska
se on ainoa tapa, jolla voimme todella

267
00:13:43,400 --> 00:13:46,690
täytyy viitata koko lista on
vain osoitin ensimmäinen osa.

268
00:13:46,690 --> 00:13:49,360
Joten haluamme kulkea
Osoitin, että ensimmäinen elementti,

269
00:13:49,360 --> 00:13:52,226
ja arvosta riippumatta me
haluavat lisätä luetteloon.

270
00:13:52,226 --> 00:13:54,600
Ja lopulta tämä toiminto
aikoo palata osoitin

271
00:13:54,600 --> 00:13:57,980
jotta uusi johtaja linkitetyn listan.

272
00:13:57,980 --> 00:13:59,700
>> Mitä vaiheita mukana täällä?

273
00:13:59,700 --> 00:14:02,249
No, aivan kuten luoda,
meidän on dynaamisesti varata

274
00:14:02,249 --> 00:14:05,540
tilaa uusi solmu, ja tarkista,
varma emme lopu muisti, jälleen,

275
00:14:05,540 --> 00:14:07,150
koska käytämme malloc.

276
00:14:07,150 --> 00:14:09,080
Sitten haluamme asuttaa
ja aseta solmu,

277
00:14:09,080 --> 00:14:12,730
niin laita numero riippumatta
val on, osaksi solmu.

278
00:14:12,730 --> 00:14:17,310
Haluamme lisätä solmun
alussa linkitetyn listan.

279
00:14:17,310 --> 00:14:19,619
>> On syy, että olen
halua tehdä tätä, ja se

280
00:14:19,619 --> 00:14:21,910
voisi olla hyvä ottaa toinen
Keskeytä video tästä,

281
00:14:21,910 --> 00:14:25,860
ja miettiä, miksi en haluaisi
lisätä alussa linkitetyn

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

283
00:14:26,589 --> 00:14:28,630
Jälleen mainitsin aiemmin
että se ei ole oikeastaan

284
00:14:28,630 --> 00:14:33,020
merkitystä, me säilyttää sitä millään
järjestys, joten ehkä se vihje.

285
00:14:33,020 --> 00:14:36,040
Ja näit mitä tapahtuisi, jos me
halusi to-- tai vain toinen

286
00:14:36,040 --> 00:14:37,360
sitten kun olimme menossa
haun kautta voit

287
00:14:37,360 --> 00:14:39,235
voisi nähdä, mitä voisi
tapahtua, jos yritimme

288
00:14:39,235 --> 00:14:41,330
lisätä lopussa luettelosta.

289
00:14:41,330 --> 00:14:44,750
Koska meillä ei ole
Osoitin listan loppuun.

290
00:14:44,750 --> 00:14:47,490
>> Niin siitä syystä, että haluaisin
lisätä alussa,

291
00:14:47,490 --> 00:14:49,380
on koska voin tehdä sen heti.

292
00:14:49,380 --> 00:14:52,730
Minulla osoitin alussa, ja
näemme tämän visuaalisen toisessa.

293
00:14:52,730 --> 00:14:55,605
Mutta jos haluan lisätä lopussa,
Minun täytyy aloittaa alusta,

294
00:14:55,605 --> 00:14:58,760
kulkea aina
end, ja sitten tack se.

295
00:14:58,760 --> 00:15:01,420
Niin se tarkoittaisi että
työntämällä lopussa luettelo

296
00:15:01,420 --> 00:15:04,140
tulisi o n
toiminta, menee takaisin

297
00:15:04,140 --> 00:15:06,720
meidän keskustelua
laskennallinen monimutkaisuus.

298
00:15:06,720 --> 00:15:10,140
Se olisi tullut o n toimintaa, jossa
kuten luettelon sai isompi, ja isompi,

299
00:15:10,140 --> 00:15:13,310
ja isompi, siitä tulee yhä
vaikeampi tack jotain

300
00:15:13,310 --> 00:15:14,661
on lopussa.

301
00:15:14,661 --> 00:15:17,410
Mutta se on aina todella helppoa
tack jotain alussa,

302
00:15:17,410 --> 00:15:19,060
olet aina alussa.

303
00:15:19,060 --> 00:15:21,620
>> Ja näemme visuaalinen tämän uudelleen.

304
00:15:21,620 --> 00:15:24,100
Ja sitten kun olemme tehneet, kun
olemme lisätään uusi solmu,

305
00:15:24,100 --> 00:15:26,880
haluamme palata meidän osoitin
uusi johtaja linkitetty lista, joka

306
00:15:26,880 --> 00:15:29,213
koska olemme lisäämällä at
alussa, todella on

307
00:15:29,213 --> 00:15:31,060
osoitin solmuun me juuri luotu.

308
00:15:31,060 --> 00:15:33,280
Katsotaanpa visualisoida,
koska mielestäni se auttaa.

309
00:15:33,280 --> 00:15:36,661
>> Joten tässä on meidän lista, se koostuu
neljä elementtiä, solmu sisältää 15,

310
00:15:36,661 --> 00:15:38,410
mikä viittaa solmuun
jotka sisältävät 9, joka

311
00:15:38,410 --> 00:15:41,370
viittaa solmuun, joka sisältää 13,
mikä viittaa solmun sisältävä

312
00:15:41,370 --> 00:15:44,840
10, joka on nolla-
osoitin sen ensi osoitin

313
00:15:44,840 --> 00:15:47,010
niin se luettelon loppuun.

314
00:15:47,010 --> 00:15:50,200
Joten haluamme lisätä
uusi solmu kanssa arvo 12

315
00:15:50,200 --> 00:15:52,720
alussa tämän
lista, mitä teemme?

316
00:15:52,720 --> 00:15:58,770
No, ensin meidän malloc tilaa
solmu, ja sitten laitamme 12 siellä.

317
00:15:58,770 --> 00:16:02,211
>> Joten nyt olemme saavuttaneet
päätös, eikö?

318
00:16:02,211 --> 00:16:03,960
Meillä on pari
viitteitä, että voisimme

319
00:16:03,960 --> 00:16:06,770
liikkua, kumpi meidän pitäisi siirtyä ensin?

320
00:16:06,770 --> 00:16:09,250
Pitäisikö meidän tehdä 12 kohta
uusi johtaja list--

321
00:16:09,250 --> 00:16:13,020
tai anteeksi, meidän pitäisi tehdä 12
viittaavat vanha pää listan?

322
00:16:13,020 --> 00:16:15,319
Vai pitäisikö sanoa, että
Listassa on nyt alkaa 12.

323
00:16:15,319 --> 00:16:17,110
On ero
siellä, ja me tutustumme

324
00:16:17,110 --> 00:16:19,870
mitä tapahtuu sekä toisessa.

325
00:16:19,870 --> 00:16:23,350
>> Mutta tämä johtaa
suuri aihe sivupalkin,

326
00:16:23,350 --> 00:16:26,280
joka on, että yksi
vaikeimpia asioita liittyvät luettelot

327
00:16:26,280 --> 00:16:30,980
on järjestää viitteitä
oikeassa järjestyksessä.

328
00:16:30,980 --> 00:16:34,520
Jos muutat asioita epäkunnossa,
voit päätyä vahingossa

329
00:16:34,520 --> 00:16:36,050
orpoutumista loput luettelon.

330
00:16:36,050 --> 00:16:37,300
Ja tässä on esimerkki tästä.

331
00:16:37,300 --> 00:16:40,540
Joten mennä ajatus of--
No, olemme juuri luotu 12.

332
00:16:40,540 --> 00:16:43,180
Tiedämme 12 tulee olemaan
uusi johtaja luettelo,

333
00:16:43,180 --> 00:16:47,660
ja niin miksi emme siirrä
luettelon osoitin kohtaan siellä.

334
00:16:47,660 --> 00:16:49,070
>> OK, niin se on hyvä.

335
00:16:49,070 --> 00:16:51,560
Joten nyt jos ei 12 seuraava kohta?

336
00:16:51,560 --> 00:16:54,580
Tarkoitan, visuaalisesti voimme nähdä
että se tulee kohta 15,

337
00:16:54,580 --> 00:16:57,250
kuin ihmisillä se on todella selvää meille.

338
00:16:57,250 --> 00:17:00,300
Miten tietokone tietää?

339
00:17:00,300 --> 00:17:02,720
Meillä ei ole mitään
osoittaen 15 enää, eikö?

340
00:17:02,720 --> 00:17:05,869
>> Olemme menettäneet kyvyn viitata 15.

341
00:17:05,869 --> 00:17:11,460
Emme voi sanoa uusia nuolta tasavertaisten
jotain, ei ole mitään siellä.

342
00:17:11,460 --> 00:17:13,510
Itse asiassa, olemme orvoiksi
loput luettelon

343
00:17:13,510 --> 00:17:16,465
tekemällä niin, olemme
vahingossa rikki ketju.

344
00:17:16,465 --> 00:17:18,089
Ja emme missään nimessä halua tehdä sitä.

345
00:17:18,089 --> 00:17:20,000
>> Joten mennään takaisin ja kokeile tätä uudelleen.

346
00:17:20,000 --> 00:17:24,060
Ehkä oikein
on asettaa 12 seuraava osoitin

347
00:17:24,060 --> 00:17:28,290
vanha johtaja listan ensimmäinen,
sitten voimme siirtyä listan yli.

348
00:17:28,290 --> 00:17:30,420
Ja itse asiassa, että on
oikeassa järjestyksessä, että me

349
00:17:30,420 --> 00:17:32,836
täytyy seurata, kun olemme
työskennellä yksin linkitetyn listan.

350
00:17:32,836 --> 00:17:36,460
Haluamme aina yhdistää
uusi elementti listaan,

351
00:17:36,460 --> 00:17:41,010
ennen kuin ryhdymme tuollaisen
tärkeä askel muuttaa

352
00:17:41,010 --> 00:17:43,360
jossa pää linkitetyn listan on.

353
00:17:43,360 --> 00:17:46,740
Tämäkin on niin perustavanlaatuinen asia,
emme halua menettää seurata sitä.

354
00:17:46,740 --> 00:17:49,310
>> Joten haluamme varmistaa, että
kaikki on ketjuttaa,

355
00:17:49,310 --> 00:17:52,040
ennen kuin siirrymme että osoitin.

356
00:17:52,040 --> 00:17:55,300
Ja niin tämä olisi oikeassa järjestyksessä,
joka on kytkeä 12 listalle

357
00:17:55,300 --> 00:17:57,630
sitten sanoa, että luettelo alkaa 12.

358
00:17:57,630 --> 00:18:00,860
Jos me sanoi luettelo alkaa 12 ja
sitten yrittänyt liittää 12 listalle

359
00:18:00,860 --> 00:18:02,193
olemme jo nähneet, mitä tapahtuu.

360
00:18:02,193 --> 00:18:04,920
Menetämme lista vahingossa.

361
00:18:04,920 --> 00:18:06,740
>> OK, joten yksi asia puhua.

362
00:18:06,740 --> 00:18:09,750
Mitä jos haluamme päästä eroon
koko linkitetty lista kerralla?

363
00:18:09,750 --> 00:18:11,750
Jälleen olemme mallocing
kaikki tämä tila, ja niin me

364
00:18:11,750 --> 00:18:13,351
täytyy vapauttaa, kun olemme tehneet.

365
00:18:13,351 --> 00:18:15,350
Joten nyt haluamme poistaa
koko linkitetyn listan.

366
00:18:15,350 --> 00:18:16,850
No, mitä haluamme tehdä?

367
00:18:16,850 --> 00:18:20,460
>> Jos olemme saavuttaneet nollaosoittimen, me
halua lopettaa, muuten vain poistaa

368
00:18:20,460 --> 00:18:23,420
loput luettelosta ja sitten vapauta minut.

369
00:18:23,420 --> 00:18:28,890
Poistaa loput luettelon,
ja sitten vapauttaa nykyisen solmun.

370
00:18:28,890 --> 00:18:32,850
Mitä se kuulostaa,
mitä tekniikkaa on puhuimme

371
00:18:32,850 --> 00:18:35,440
noin aiemmin Kuulostaako?

372
00:18:35,440 --> 00:18:39,560
Poista kaikki muutkin, niin
palata ja poistaa minut.

373
00:18:39,560 --> 00:18:42,380
>> Se rekursio, olemme tehneet
ongelma hieman pienempi,

374
00:18:42,380 --> 00:18:46,910
sanomme poistaa kaikki
muuten, niin voit poistaa minut.

375
00:18:46,910 --> 00:18:50,940
Ja edelleen tiellä, että solmu
sanovat, poistaa kaikki muutkin.

376
00:18:50,940 --> 00:18:53,940
Mutta lopulta me saamme
kohdassa, jossa luettelo on tyhjä,

377
00:18:53,940 --> 00:18:55,310
ja se on meidän perustapaus.

378
00:18:55,310 --> 00:18:57,010
>> Joten katsomaan tämän,
ja miten tämä voisi toimia.

379
00:18:57,010 --> 00:18:59,759
Joten tässä on meidän lista, se on sama
luetella me vain puhumme,

380
00:18:59,759 --> 00:19:00,980
ja siellä vaiheet.

381
00:19:00,980 --> 00:19:04,200
Siellä on paljon tekstiä täällä, mutta
toivottavasti visualisointi auttaa.

382
00:19:04,200 --> 00:19:08,557
>> Joten me have-- ja olen myös vetänyt
jopa meidän pino kehyksiä kuva

383
00:19:08,557 --> 00:19:10,890
meidän video soittaa pinoja,
ja toivottavasti kaikki tämän

384
00:19:10,890 --> 00:19:13,260
yhdessä näyttää mitä tapahtuu.

385
00:19:13,260 --> 00:19:14,510
Joten tässä on meidän pseudokoodilla koodi.

386
00:19:14,510 --> 00:19:17,830
Jos pääsemme null
osoitin, stop, muuten,

387
00:19:17,830 --> 00:19:21,320
poistaa loput luettelon,
sitten vapauttaa nykyisen solmun.

388
00:19:21,320 --> 00:19:25,700
Joten juuri nyt, list--
osoitin, että olemme

389
00:19:25,700 --> 00:19:28,410
kulkee tuhota pistettä 12.

390
00:19:28,410 --> 00:19:33,340
12 ei nollaosoittimen, joten olemme
menossa poistaa loput luettelon.

391
00:19:33,340 --> 00:19:35,450
>> Mikä on poistaa
me muut mukana?

392
00:19:35,450 --> 00:19:37,950
No, se tarkoittaa tehtävien
soita tuhota, sanoi

393
00:19:37,950 --> 00:19:42,060
että 15 on alku
Loput luettelon haluamme tuhota.

394
00:19:42,060 --> 00:19:47,480
Ja niin puhelu tuhota
12 on eräänlainen pidossa.

395
00:19:47,480 --> 00:19:52,690
Se on jäädytetty siellä, odottamassa
soita tuhota 15, loppuun työnsä.

396
00:19:52,690 --> 00:19:56,280
>> No, 15 ei ole nollaosoittimen, ja
joten se tulee sanoa, okei,

397
00:19:56,280 --> 00:19:58,450
hyvin, poistaa loput luettelon.

398
00:19:58,450 --> 00:20:00,760
Loput luettelo alkaa
klo 9, ja niin me vain

399
00:20:00,760 --> 00:20:04,514
odota kunnes poistat kaikki että
kamaa, sitten tulevat takaisin ja poistaa minut.

400
00:20:04,514 --> 00:20:06,680
No 9 tulee sanoa, hyvin,
En ole nollaosoittimen,

401
00:20:06,680 --> 00:20:09,020
joten poista loput listan täältä.

402
00:20:09,020 --> 00:20:11,805
Ja niin kokeile ja tuhota 13.

403
00:20:11,805 --> 00:20:15,550
13 sanoo, en ole nollaosoittimen,
sama asia, se kulkee pukki.

404
00:20:15,550 --> 00:20:17,930
10 ei nollaosoittimen, 10
sisältää nollaosoittimen,

405
00:20:17,930 --> 00:20:20,200
mutta 10 ei itse
nollaosoittimen juuri nyt,

406
00:20:20,200 --> 00:20:22,470
ja niin se kulkee pukki liian.

407
00:20:22,470 --> 00:20:25,560
>> Ja nyt luetella pistettä siellä, se
todella osoittaisi some--

408
00:20:25,560 --> 00:20:28,710
jos minulla olisi enemmän tilaa kuva,
se osoittaa joitakin satunnaisia ​​tilaa

409
00:20:28,710 --> 00:20:29,960
että emme tiedä mitä se on.

410
00:20:29,960 --> 00:20:34,680
Se on tyhjän osoittimen kuitenkin, luettelo
on kirjaimellisesti nyt asetettu se arvoja null.

411
00:20:34,680 --> 00:20:36,820
Se osoittaa oikealle sisällä että punainen laatikko.

412
00:20:36,820 --> 00:20:39,960
Pääsimme nollaosoittimen, joten
voimme lopettaa, ja olemme tehneet.

413
00:20:39,960 --> 00:20:46,230
>> Ja jotta violetti kehys on now-- klo
päälle stack-- se aktiivinen kehys,

414
00:20:46,230 --> 00:20:47,017
mutta se on tehty.

415
00:20:47,017 --> 00:20:48,600
Jos olemme saavuttaneet nollaosoittimen, lopeta.

416
00:20:48,600 --> 00:20:51,290
Emme tee mitään, me
ei saa nollaosoittimen,

417
00:20:51,290 --> 00:20:55,070
emme malloc mitään
tilaa, ja niin olemme tehneet.

418
00:20:55,070 --> 00:20:57,590
Jotta toiminto kehys
tuhotaan, ja me

419
00:20:57,590 --> 00:21:00,930
resume-- haemme jossa jätimme
pois seuraavaksi korkein, joka

420
00:21:00,930 --> 00:21:02,807
on tämä tummansininen runko täällä.

421
00:21:02,807 --> 00:21:04,390
Joten me poimia oikea mihin jäimme.

422
00:21:04,390 --> 00:21:06,598
Poistimme loput
luettelo jo, joten nyt olemme

423
00:21:06,598 --> 00:21:08,000
menossa vapauttaa nykyisen solmut.

424
00:21:08,000 --> 00:21:12,920
Joten nyt voimme vapauttaa tämän solmun, ja nyt
olemme lopussa funktion.

425
00:21:12,920 --> 00:21:16,810
Ja niin että toiminta kehys on tuhottu,
ja me poimia vaaleansininen yksi.

426
00:21:16,810 --> 00:21:20,650
>> Joten se says-- olen jo done--
poistetaan loput listan, niin

427
00:21:20,650 --> 00:21:23,140
vapauttaa nykyisen solmun.

428
00:21:23,140 --> 00:21:26,520
Ja nyt keltainen kehys on
takaisin pinon.

429
00:21:26,520 --> 00:21:29,655
Ja niin näette, olemme nyt
tuhoaa listan oikealta vasemmalle.

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

431
00:21:33,710 --> 00:21:37,280
>> Mitä olisi tapahtunut, vaikka,
jos olisimme tehneet asiat väärin?

432
00:21:37,280 --> 00:21:39,410
Aivan kuten kun yritimme
lisätä elementin.

433
00:21:39,410 --> 00:21:41,909
Jos me sekaisin ketju, jos
emme yhdistä viitteitä

434
00:21:41,909 --> 00:21:44,690
oikeassa järjestyksessä, jos me
vain vapautti ensimmäinen elementti,

435
00:21:44,690 --> 00:21:47,420
jos me vain vapautti
johtaja luettelon, nyt meillä

436
00:21:47,420 --> 00:21:49,642
ei ole tapa viitata
loput luettelon.

437
00:21:49,642 --> 00:21:51,350
Ja niin meillä olisi
orvoksi kaiken,

438
00:21:51,350 --> 00:21:53,880
meillä olisi ollut mitä
kutsutaan muisti vuotaa.

439
00:21:53,880 --> 00:21:56,800
Jos muistatte meidän video
dynaaminen muistin jakamista,

440
00:21:56,800 --> 00:21:58,650
se ei ole kovin hyvä asia.

441
00:21:58,650 --> 00:22:00,810
>> Joten kuten sanoin, siellä
useita toimintoja

442
00:22:00,810 --> 00:22:04,010
että meidän on käytettävä töihin
kanssa linkitetty lista tehokkaasti.

443
00:22:04,010 --> 00:22:08,430
Ja olet ehkä huomannut minä pois yksi,
poistaa yksittäinen elementti liittyy

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

445
00:22:09,064 --> 00:22:10,980
Syy Tein että
on se oikeastaan ​​eräänlainen

446
00:22:10,980 --> 00:22:14,360
hankala miettiä, miten poistaa
yksittäinen elementti yksittäin

447
00:22:14,360 --> 00:22:15,600
linkitetty lista.

448
00:22:15,600 --> 00:22:19,950
Meidän täytyy pystyä ohittaa yli
jotain luettelossa, joka

449
00:22:19,950 --> 00:22:22,975
tarkoittaa saamme point-- me
Poistetaanko node--

450
00:22:22,975 --> 00:22:25,350
mutta jotta niin me
älä hävitä tietoja,

451
00:22:25,350 --> 00:22:30,530
Meidän täytyy liittää tähän
solmu tänne, täällä.

452
00:22:30,530 --> 00:22:33,390
>> Olen siis luultavasti teki sitä väärin
ulkoasut keskenään.

453
00:22:33,390 --> 00:22:36,830
Joten olemme alussa meidän
lista, olemme etenee läpi,

454
00:22:36,830 --> 00:22:40,510
haluamme poistaa tämän solmuun.

455
00:22:40,510 --> 00:22:43,440
Jos me vain poistaa sen,
olemme rikki ketju.

456
00:22:43,440 --> 00:22:45,950
Tämä solmu täällä
viittaa kaikki muu,

457
00:22:45,950 --> 00:22:48,260
se sisältää ketjun täällä ulos.

458
00:22:48,260 --> 00:22:51,190
>> Joten mitä meidän pitää tehdä todella
kun olemme päästä tähän pisteeseen,

459
00:22:51,190 --> 00:22:56,670
on meidän askel taaksepäin yksi, ja
liitä tämä solmu yli tämän solmun,

460
00:22:56,670 --> 00:22:58,590
jotta voimme sitten poistaa
yksi keskellä.

461
00:22:58,590 --> 00:23:02,120
Mutta yksittäin liittyy Luettelot eivät
meille tie taaksepäin.

462
00:23:02,120 --> 00:23:05,160
Joten meidän täytyy joko pitää
kaksi osoitinta, ja siirtää ne

463
00:23:05,160 --> 00:23:09,527
tavallaan pois askel, yksi takana
muut kuin menemme, tai saada pisteeseen

464
00:23:09,527 --> 00:23:11,110
ja sitten lähettää toisen osoitin kautta.

465
00:23:11,110 --> 00:23:13,150
Ja kuten näette, se
voi saada hieman sotkuinen.

466
00:23:13,150 --> 00:23:15,360
Onneksi meillä on
toinen tapa ratkaista että,

467
00:23:15,360 --> 00:23:17,810
kun puhumme kaksin verroin linkitetty luetteloista.

468
00:23:17,810 --> 00:23:20,720
>> Olen Doug Lloyd, tämä on CS50.

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