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

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

3
00:00:05,670 --> 00:00:08,560
>> DOUG Lloyd: OK, kështu që në
kjo pikë në kurs,

4
00:00:08,560 --> 00:00:15,300
ne kemi mbuluar shumë bazat e C.
Ne e dimë shumë rreth variablave, vargjeve,

5
00:00:15,300 --> 00:00:17,610
pointers, të gjitha gjëra të mira.

6
00:00:17,610 --> 00:00:21,610
Ata janë ndërtuar të gjitha llojet e
për të parë si bazat,

7
00:00:21,610 --> 00:00:23,880
por ne mund të bëjmë më shumë, e drejtë?

8
00:00:23,880 --> 00:00:27,930
Ne mund të kombinohen gjëra
së bashku në mënyra interesante.

9
00:00:27,930 --> 00:00:31,010
>> Dhe kështu që le të bëjë këtë, le të fillojë
të zgjerohet nga çfarë C na jep,

10
00:00:31,010 --> 00:00:35,270
dhe të fillojnë për të krijuar të dhënat tona
Strukturat Duke përdorur këto ndërtesë

11
00:00:35,270 --> 00:00:40,590
blloqe së bashku për të bërë diçka
të vërtetë të vlefshme, e dobishme.

12
00:00:40,590 --> 00:00:43,420
Një mënyrë ne mund të bëjmë këtë është
për të folur për koleksioneve.

13
00:00:43,420 --> 00:00:48,360
Pra, deri tani ne kemi pasur një lloj të të dhënave
Struktura për përfaqësimin koleksione

14
00:00:48,360 --> 00:00:51,030
i pëlqen vlerat, vlera të ngjashme.

15
00:00:51,030 --> 00:00:52,350
Kjo do të jetë një grup.

16
00:00:52,350 --> 00:00:57,020
Ne kemi koleksionet e numrave të plotë, ose
koleksionet e karaktereve dhe kështu me radhë.

17
00:00:57,020 --> 00:01:00,890
>> Strukturat janë gjithashtu lloj i të dhënave
Struktura për mbledhjen e informacionit,

18
00:01:00,890 --> 00:01:03,220
por kjo nuk është për të mbledhur si vlera.

19
00:01:03,220 --> 00:01:08,090
Kjo zakonisht mixes lloje të ndryshme të të dhënave
së bashku në brendësi të një kuti vetme.

20
00:01:08,090 --> 00:01:10,750
Por kjo nuk është vetë
përdoret për të zinxhirit bashku

21
00:01:10,750 --> 00:01:16,920
ose të lidhë së bashku ngjashme
sende, si një grup.

22
00:01:16,920 --> 00:01:20,960
Vargjeve janë të mëdha për
element të kërkoni, por risjell

23
00:01:20,960 --> 00:01:24,262
kjo është shumë e vështirë
për të futur në një grup,

24
00:01:24,262 --> 00:01:26,470
nëse ne jemi futur në
fund të kësaj grup.

25
00:01:26,470 --> 00:01:29,730
>> Dhe shembulli më i mirë unë kam
për këtë është futje lloj.

26
00:01:29,730 --> 00:01:31,650
Nëse ju kujtohet video të tonë
në futje lloji,

27
00:01:31,650 --> 00:01:34,110
nuk ishte një shumë e
shpenzim i përfshirë në kesh

28
00:01:34,110 --> 00:01:37,970
për të marr elemente, dhe zhvendoset ato
nga rruga të përshtaten diçka

29
00:01:37,970 --> 00:01:41,290
në mes të vektorit tuaj.

30
00:01:41,290 --> 00:01:44,690
Vargjeve gjithashtu vuajnë nga një tjetër
problem, e cila është e papërkulshmëri.

31
00:01:44,690 --> 00:01:47,150
Kur ne të deklarojë një grup,
ne të merrni një e shtënë në të.

32
00:01:47,150 --> 00:01:49,790
Ne kemi marrë për të thënë, unë dua
Kjo shumë elemente.

33
00:01:49,790 --> 00:01:51,940
Mund të jetë 100, ajo mund
të jetë 1000, ajo mund

34
00:01:51,940 --> 00:01:55,930
të jetë x, ku x është një numër që përdoruesi
na dha në një shpejtë apo në komandën

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

36
00:01:56,630 --> 00:01:59,905
>> Por ne vetëm të marrë një e shtënë në të, ne
nuk do të marrë për të pastaj thonë oh, në të vërtetë unë

37
00:01:59,905 --> 00:02:04,360
nevojiten 101, ose unë e nevojshme x plus 20.

38
00:02:04,360 --> 00:02:07,910
Shumë vonë, ne kemi deklaruar tashmë
array, dhe në qoftë se ne duam që të merrni 101 ose x

39
00:02:07,910 --> 00:02:12,050
plus 20, ne duhet të deklarojnë
një grup krejtësisht të ndryshme,

40
00:02:12,050 --> 00:02:15,540
kopje të të gjitha elementet e vektorit
mbi, dhe pastaj ne kemi mjaft.

41
00:02:15,540 --> 00:02:19,880
Dhe çka nëse ne jemi gabim përsëri, çfarë
në qoftë se ne fakt duhet 102, ose 40 x plus,

42
00:02:19,880 --> 00:02:21,970
ne duhet të bëjmë këtë përsëri.

43
00:02:21,970 --> 00:02:26,250
Pra, ata janë shumë të papërkulur
për ndryshuar të dhënat tona,

44
00:02:26,250 --> 00:02:29,360
por në qoftë se ne të kombinohen së bashku disa
nga bazat që ne kemi tashmë

45
00:02:29,360 --> 00:02:33,230
mësuar në lidhje me pointers dhe strukturave,
në veçanti duke përdorur kujtesën dinamike

46
00:02:33,230 --> 00:02:36,180
ndarja me malloc, ne
mund të vënë këto pjesë së bashku

47
00:02:36,180 --> 00:02:40,960
Për të krijuar një të dhëna të reja structure-- A
veçmas të lidhura listë ne mund say--

48
00:02:40,960 --> 00:02:45,400
që na lejon të rritet dhe
tkurret një koleksion të vlerave

49
00:02:45,400 --> 00:02:48,800
dhe ne nuk do të ketë ndonjë hapësirë ​​tretur.

50
00:02:48,800 --> 00:02:53,320
>> Pra, përsëri, ne e quajmë këtë ide,
ky nocion, një listë e lidhur.

51
00:02:53,320 --> 00:02:56,320
Në veçanti, në këtë video ne jemi
duke folur në lidhje me listën e lidhur në formë individuale,

52
00:02:56,320 --> 00:02:59,185
dhe pastaj një tjetër video ne do të flasim
Listat gati dyfish të lidhura, të cilat

53
00:02:59,185 --> 00:03:01,560
është vetëm një variacion mbi një temë këtu.

54
00:03:01,560 --> 00:03:05,200
Por një listë e lidhur në formë individuale
është i përbërë nga nyje,

55
00:03:05,200 --> 00:03:08,559
nyje vetëm duke qenë një term-- abstrakt
kjo është vetëm diçka që unë jam duke e quajtur

56
00:03:08,559 --> 00:03:10,350
kjo është një lloj i
Struktura, në thelb, unë jam?

57
00:03:10,350 --> 00:03:16,190
Vetëm duke shkuar për të thirrur atë një node-- dhe kjo
nyjë ka dy anëtarë, ose dy fusha.

58
00:03:16,190 --> 00:03:20,300
Ajo ka të dhëna, zakonisht një
numër i plotë, një noton karakter,

59
00:03:20,300 --> 00:03:23,790
ose mund të jetë një lloj tjetër të dhënat e
që e keni definuar me një def tipit.

60
00:03:23,790 --> 00:03:29,290
Dhe ai përmban një tregues për
tjetër nyje e të njëjtit lloj.

61
00:03:29,290 --> 00:03:34,710
>> Pra, ne kemi dy gjëra brenda
kjo nyje, të dhëna dhe një akrep

62
00:03:34,710 --> 00:03:36,380
në një tjetër nyje.

63
00:03:36,380 --> 00:03:39,370
Dhe në qoftë se ju filloni për të kujtoj
kjo, ju mund të mendoni për atë

64
00:03:39,370 --> 00:03:42,280
si një zinxhir nyjet që
janë të lidhura së bashku.

65
00:03:42,280 --> 00:03:45,070
Ne kemi nyjen e parë, atë
përmban të dhëna, dhe një akrep

66
00:03:45,070 --> 00:03:49,110
në nyjen e dytë, e cila përmban
të dhënave, dhe një tregues për nyjen e tretë.

67
00:03:49,110 --> 00:03:52,940
Dhe kështu kjo është arsyeja pse ne e quajmë atë një
listë e lidhur, ata janë të lidhura së bashku.

68
00:03:52,940 --> 00:03:56,070
>> Çfarë e bën këtë të veçantë
Struktura nyje të duken si?

69
00:03:56,070 --> 00:04:01,120
E pra, nëse ju kujtohet nga video tonë në
përcaktimin e llojeve me porosi, me tip def,

70
00:04:01,120 --> 00:04:05,400
ne mund të përcaktojë një structure-- dhe
shkruani përcaktojë një strukturë si kjo.

71
00:04:05,400 --> 00:04:11,240
tyepdef struct sllist, dhe atëherë unë jam
duke përdorur vlerën fjalën këtu në mënyrë arbitrare

72
00:04:11,240 --> 00:04:13,891
për të treguar çdo lloj të dhënave me të vërtetë.

73
00:04:13,891 --> 00:04:16,890
Ju mund të kalojë në një numër të plotë ose noton,
ju mund të ketë çdo gjë që ju dëshironi.

74
00:04:16,890 --> 00:04:19,389
Kjo nuk është e kufizuar për vetëm
integers, apo diçka të tillë.

75
00:04:19,389 --> 00:04:22,790
Pra, vlera është vetëm një arbitrare
llojin e të dhënave, dhe pastaj një akrep

76
00:04:22,790 --> 00:04:26,310
në një nyje e llojit të njëjtë.

77
00:04:26,310 --> 00:04:29,690
>> Tani, ka një kapur pak
këtu me përcaktimin e një strukture

78
00:04:29,690 --> 00:04:33,030
kur kjo është një strukturë referues vetë.

79
00:04:33,030 --> 00:04:35,340
Unë duhet të ketë një të përkohshme
përmendur për strukturën e mia.

80
00:04:35,340 --> 00:04:37,640
Në fund të ditës së Parë
qartë dëshironi të telefononi atë

81
00:04:37,640 --> 00:04:43,030
nyje SLL, kjo është në fund të fundit i ri
përmendur një pjesë të përkufizimit tim tipit,

82
00:04:43,030 --> 00:04:47,450
por unë nuk mund të përdorë nyjen sll
në mes të kësaj.

83
00:04:47,450 --> 00:04:51,430
Arsyeja është, unë nuk kam
krijoi një lloj të quajtur sll nyje

84
00:04:51,430 --> 00:04:55,200
deri sa unë goditi këtë pikë të fundit këtu.

85
00:04:55,200 --> 00:04:59,720
Deri në atë moment, unë duhet të ketë
një tjetër mënyrë për të referuar në këtë lloj të të dhënave.

86
00:04:59,720 --> 00:05:02,440
>> Dhe kjo është një vetë
referues lloj të të dhënave.

87
00:05:02,440 --> 00:05:06,314
Ajo, s një lloj të dhënave të një
strukturë që përmban një të dhënat,

88
00:05:06,314 --> 00:05:08,480
dhe një tregues për një tjetër
Struktura e të njëjtit lloj.

89
00:05:08,480 --> 00:05:11,750
Kështu që unë duhet të jetë në gjendje për t'iu referuar
ky lloj të dhëna të paktën përkohësisht,

90
00:05:11,750 --> 00:05:14,910
kështu duke i dhënë asaj një të përkohshme
Emri i struct sllist

91
00:05:14,910 --> 00:05:18,540
lejon mua që të pastaj thonë se unë dua një
treguesin në një tjetër sllist struct,

92
00:05:18,540 --> 00:05:24,690
një yll struct sllist, dhe pastaj
pasi unë e kam përfunduar definicionin,

93
00:05:24,690 --> 00:05:27,220
Unë tani mund të telefononi ky lloj një nyje SLL.

94
00:05:27,220 --> 00:05:30,520
>> Pra, kjo është arsyeja pse ju të shihni se ka
një emër i përkohshëm këtu,

95
00:05:30,520 --> 00:05:31,879
por një emër i përhershëm këtu.

96
00:05:31,879 --> 00:05:33,920
Ndonjëherë ju mund të shihni
përkufizimet e strukturës,

97
00:05:33,920 --> 00:05:36,570
për shembull, që nuk janë të
referues vetë, që

98
00:05:36,570 --> 00:05:39,390
nuk kanë një emër Specifier këtu.

99
00:05:39,390 --> 00:05:43,040
Ajo do të them vetëm typedef e strukturës,
hapur mbajtëse kaçurrel dhe pastaj të përcaktuar atë.

100
00:05:43,040 --> 00:05:45,620
Por nëse ju jeni struct është vetë
referues, pasi kjo është,

101
00:05:45,620 --> 00:05:49,010
ju duhet të specifikoni një
Emri llojin e përkohshme.

102
00:05:49,010 --> 00:05:51,310
Por në fund të fundit, tani
që ne kemi bërë këtë,

103
00:05:51,310 --> 00:05:53,620
ne vetëm mund t'i referohet
këto nyje, këto njësi,

104
00:05:53,620 --> 00:05:57,900
si nyje SLL për qëllime
e pjesës tjetër të kësaj video.

105
00:05:57,900 --> 00:06:00,900
>> Të gjithë të drejtë, kështu që ne e dimë se si për të
Krijo një listë nyje lidhur.

106
00:06:00,900 --> 00:06:03,240
Ne e dimë se si për të përcaktuar
një nyje e lidhur listë.

107
00:06:03,240 --> 00:06:06,670
Tani, në qoftë se ne jemi duke shkuar për të filluar
përdorimin e tyre për të mbledhur informacion,

108
00:06:06,670 --> 00:06:10,360
ka një çift i operacioneve ne
duhet të kuptojnë dhe të punojnë me të.

109
00:06:10,360 --> 00:06:12,860
Ne duhet të dimë se si për të krijuar
një listë e lidhur nga ajri hollë.

110
00:06:12,860 --> 00:06:14,901
Nëse nuk ka asnjë listë tashmë,
ne duam të fillojë një të tillë.

111
00:06:14,901 --> 00:06:16,960
Pra, ne duhet të jenë në gjendje
për të krijuar një listë të lidhur,

112
00:06:16,960 --> 00:06:19,130
ne kemi nevojë për siguri të kërkuar
nëpër lista Lidhje

113
00:06:19,130 --> 00:06:21,830
për të gjetur një element ne jemi duke kërkuar për të.

114
00:06:21,830 --> 00:06:24,430
Ne duhet të jenë në gjendje për të futur
gjëra të reja në listë,

115
00:06:24,430 --> 00:06:25,930
ne duam listën tonë për të të jetë në gjendje të rritet.

116
00:06:25,930 --> 00:06:28,638
Dhe në mënyrë të ngjashme, ne duam të jetë në gjendje
për të fshirë nga gjërat listën tonë,

117
00:06:28,638 --> 00:06:30,250
ne duam listën tonë për të të jetë në gjendje për të tkurret.

118
00:06:30,250 --> 00:06:32,160
Dhe në fund të tonë
programe, veçanërisht

119
00:06:32,160 --> 00:06:34,550
në qoftë se ju kujtohet se ne jemi
dinamike ndarjen e kujtesës

120
00:06:34,550 --> 00:06:38,337
për të ndërtuar këto lista në mënyrë tipike,
ne duam të lirë të gjithë që kujtesës

121
00:06:38,337 --> 00:06:39,670
kur ne jemi duke bërë punuar me të.

122
00:06:39,670 --> 00:06:44,627
Dhe kështu që ne duhet të jetë në gjendje të fshini një
tërë listë e lidhur në një dështojnë bie poshtë.

123
00:06:44,627 --> 00:06:46,460
Pra, le të shkojnë nëpër
disa nga këto operacione

124
00:06:46,460 --> 00:06:51,192
dhe se si ne mund të parashikoj ato,
duke folur në kodin pseudokod specifike.

125
00:06:51,192 --> 00:06:53,150
Pra, ne duam të krijojmë një
i lidhur listë, kështu që ndoshta ne

126
00:06:53,150 --> 00:06:56,480
duan për të përcaktuar një funksion
me këtë prototip.

127
00:06:56,480 --> 00:07:01,690
SLL yll nyje, të krijojë, dhe unë jam duke kaluar
në një argument, disa të dhëna arbitrare

128
00:07:01,690 --> 00:07:05,530
shkruani përsëri, e disa arbitrare lloj të të dhënave.

129
00:07:05,530 --> 00:07:10,482
Por unë jam returning-- këtë funksion duhet të
kthehuni tek unë një tregues, në një formë individuale

130
00:07:10,482 --> 00:07:11,190
i lidhur nyje listë.

131
00:07:11,190 --> 00:07:14,050
Përsëri, ne jemi duke u përpjekur për të krijuar
një listë e lidhur nga ajri i hollë,

132
00:07:14,050 --> 00:07:17,900
kështu që kam nevojë për një tregues për
se lista kur unë jam bërë.

133
00:07:17,900 --> 00:07:19,420
>> Pra, çfarë janë hapat përfshirë këtu?

134
00:07:19,420 --> 00:07:20,960
E pra, gjëja e parë që unë jam
do të bëni është dinamike

135
00:07:20,960 --> 00:07:22,550
ndajë hapësirë ​​për një nyje të re.

136
00:07:22,550 --> 00:07:26,689
Përsëri, ne jemi duke krijuar atë nga të hollë
ajrit, kështu që ne kemi nevojë për hapësirë ​​malloc për të.

137
00:07:26,689 --> 00:07:28,480
Dhe sigurisht, menjëherë
pasi ne malloc,

138
00:07:28,480 --> 00:07:31,692
ne gjithmonë kontrolloni për t'u siguruar që tonë
pointer-- nuk kemi marrë prapa null.

139
00:07:31,692 --> 00:07:33,650
Sepse në qoftë se ne të përpiqemi dhe
respekt një tregues null,

140
00:07:33,650 --> 00:07:36,190
ne jemi duke shkuar për të vuajnë një
segfault dhe ne nuk duam që.

141
00:07:36,190 --> 00:07:39,510
>> Pastaj ne duam për të mbushur në këtë fushë,
ne duam të nisja fushën e vlerës

142
00:07:39,510 --> 00:07:41,690
dhe nisja fushën e ardhshme.

143
00:07:41,690 --> 00:07:45,450
Dhe pastaj ne duam to-- përfundimisht si
Funksioni prototip indicates-- ne duam

144
00:07:45,450 --> 00:07:49,940
për t'u kthyer një tregues për një nyje sll.

145
00:07:49,940 --> 00:07:51,710
Pra, çfarë e bëjnë këtë të duket si vizualisht?

146
00:07:51,710 --> 00:07:55,230
E pra, së pari ne jemi duke shkuar për dinamike
ndajë hapësirë ​​për një nyje të re SLL,

147
00:07:55,230 --> 00:07:58,320
kështu që ne malloc-- që është
një përfaqësim pamor

148
00:07:58,320 --> 00:08:00,020
e nyjës ne vetëm krijuar.

149
00:08:00,020 --> 00:08:02,757
Dhe ne kontrolloni për t'u siguruar
kjo nuk është null-- në këtë rast,

150
00:08:02,757 --> 00:08:04,840
fotografia nuk do të ketë
treguar deri në qoftë se ajo ishte null,

151
00:08:04,840 --> 00:08:07,298
ne do të kishim dalë jashtë kujtesës,
kështu që ne jemi të mirë për të shkuar atje.

152
00:08:07,298 --> 00:08:10,200
Deri tani ne jemi në të hap C,
nisja fushën e vlerës nyjet.

153
00:08:10,200 --> 00:08:12,280
E pra, në bazë të këtij funksioni
më kërkojnë, unë jam duke përdorur këtu,

154
00:08:12,280 --> 00:08:16,700
duket si unë dua të kalojë në 6,
Kështu që unë do 6 në fushën e vlerës.

155
00:08:16,700 --> 00:08:18,865
Tani, nisja fushën e ardhshme.

156
00:08:18,865 --> 00:08:21,640
E pra, çfarë jam unë do të bëj atje,
nuk ka asgjë tjetër, të drejtë,

157
00:08:21,640 --> 00:08:23,600
kjo është e vetmja gjë në listë.

158
00:08:23,600 --> 00:08:27,206
Pra, çfarë është gjëja tjetër në listë?

159
00:08:27,206 --> 00:08:29,660
>> Ajo nuk duhet të tregojnë për ndonjë gjë, e drejtë.

160
00:08:29,660 --> 00:08:33,600
Nuk ka asgjë tjetër atje, kështu që ajo që është
koncepti ne e dimë se është nothing--

161
00:08:33,600 --> 00:08:35,638
pointers për asgjë?

162
00:08:35,638 --> 00:08:37,929
Ajo duhet të jetë ndoshta ne duam
për të vënë një tregues null atje,

163
00:08:37,929 --> 00:08:40,178
dhe unë do të përfaqësojë null
treguesin si vetëm një kuti të kuqe,

164
00:08:40,178 --> 00:08:41,559
ne nuk mund të shkojmë më tutje.

165
00:08:41,559 --> 00:08:44,430
Siç do të shohim pak më vonë,
ne do të kemi përfundimisht zinxhirët

166
00:08:44,430 --> 00:08:46,330
e shigjeta lidh
këto nyje së bashku,

167
00:08:46,330 --> 00:08:48,480
por kur ju goditi
kuti të kuqe, kjo është null,

168
00:08:48,480 --> 00:08:51,150
ne nuk mund të shkojmë më tutje,
ky është fundi i listës.

169
00:08:51,150 --> 00:08:53,960
>> Dhe së fundi, ne vetëm duam të
kthehet një tregues për këtë nyje.

170
00:08:53,960 --> 00:08:56,160
Pra, ne do të thërrasë atë të ri,
dhe do të kthehet të reja

171
00:08:56,160 --> 00:08:59,370
kështu që mund të përdoret në
çfarëdo funksioni krijoi atë.

172
00:08:59,370 --> 00:09:03,100
Kështu që nuk kemi shkuar, Ne kemi krijuar një formë individuale
lidhur Lista nyje nga ajri i hollë,

173
00:09:03,100 --> 00:09:05,920
dhe tani ne kemi një listë që ne mund të punojnë me të.

174
00:09:05,920 --> 00:09:08,260
>> Tani, le të thonë se ne tashmë
kanë një zinxhir të madh,

175
00:09:08,260 --> 00:09:09,800
dhe ne duam të gjeni diçka në të.

176
00:09:09,800 --> 00:09:12,716
Dhe ne duam një funksion që është duke shkuar
të kthehen vërtetë apo e rreme, në varësi

177
00:09:12,716 --> 00:09:15,840
nëse një vlerë ekziston në atë listë.

178
00:09:15,840 --> 00:09:18,160
Një prototip funksion, ose
Deklarata për këtë funksion,

179
00:09:18,160 --> 00:09:23,320
mund të duket si this-- bool gjeni, dhe
atëherë ne duam të kalojë në dy argumente.

180
00:09:23,320 --> 00:09:26,996
>> E para, është një tregues për
elementi i parë i lista e lidhur.

181
00:09:26,996 --> 00:09:29,620
Kjo është në fakt diçka që ju do të
gjithmonë duan të mbajnë gjurmët e,

182
00:09:29,620 --> 00:09:33,110
dhe në fakt mund të jetë diçka që
edhe ju vënë në një ndryshore globale.

183
00:09:33,110 --> 00:09:35,360
Pasi ta keni krijuar një listë,
ju gjithmonë, gjithmonë

184
00:09:35,360 --> 00:09:38,990
duan të mbajnë gjurmët e shumë
elementi i parë i lista.

185
00:09:38,990 --> 00:09:43,690
Në këtë mënyrë ju mund t'i referohet të gjitha të tjera
Elementet nga vetëm pas zinxhir,

186
00:09:43,690 --> 00:09:47,300
pa pasur nevojë për të mbajtur pointers
paprekur për çdo element të vetëm.

187
00:09:47,300 --> 00:09:50,920
Ju vetëm duhet të mbajnë gjurmët e parë
një në qoftë se ata janë të lidhur me zinxhirë të gjithë së bashku.

188
00:09:50,920 --> 00:09:52,460
>> Dhe pastaj gjëja e dytë
ne jemi duke kaluar në një herë

189
00:09:52,460 --> 00:09:54,376
është në mënyrë arbitrare some--
çfarëdo lloji të dhëna ne jemi

190
00:09:54,376 --> 00:09:59,640
në kërkim të ka brenda
shpresojmë se një nga nyjet në listë.

191
00:09:59,640 --> 00:10:00,980
Pra, çfarë janë hapat?

192
00:10:00,980 --> 00:10:04,250
E pra, gjëja e parë që ne bëjmë është
ne kemi krijuar një akrep transversale

193
00:10:04,250 --> 00:10:06,015
duke vënë në kokë listat.

194
00:10:06,015 --> 00:10:08,890
E pra, pse nuk e bëjmë këtë, ne tashmë
kanë një akrep në krye listave,

195
00:10:08,890 --> 00:10:10,974
pse nuk kemi vetëm të lëvizë se një rreth?

196
00:10:10,974 --> 00:10:13,140
E pra, si unë vetëm i tha,
është vërtet e rëndësishme për ne

197
00:10:13,140 --> 00:10:17,580
që gjithmonë të mbajnë gjurmët e të
Elementi i parë në listë.

198
00:10:17,580 --> 00:10:21,270
Dhe kështu është në fakt më mirë
për të krijuar një kopje të kësaj,

199
00:10:21,270 --> 00:10:25,350
dhe të përdorin që të lëvizë kështu që ne kurrë
aksidentalisht largohen, ose ne gjithmonë

200
00:10:25,350 --> 00:10:30,430
kanë një akrep në një pikë që është
drejtë në elementin e parë të lista.

201
00:10:30,430 --> 00:10:33,290
Pra, është më mirë për të krijuar një
e dyta që ne i përdorim për të lëvizur.

202
00:10:33,290 --> 00:10:35,877
>> Atëherë ne vetëm nëse krahasojmë
fusha vlera në atë nyje

203
00:10:35,877 --> 00:10:38,960
është ajo që ne jemi duke kërkuar për të, dhe në qoftë se është
jo, ne vetëm të shkojë në nyjen e ardhshëm.

204
00:10:38,960 --> 00:10:41,040
Dhe ne të vazhdojmë të bëjmë atë
mbi dhe mbi dhe mbi,

205
00:10:41,040 --> 00:10:44,811
derisa ne ose të gjejnë
element, ose ne hit

206
00:10:44,811 --> 00:10:47,310
null-- ne kemi arritur fundin
e listës dhe kjo nuk është atje.

207
00:10:47,310 --> 00:10:50,540
Kjo duhet të shpresojmë se të telefononi një zile
për ju si kërko vetëm lineare,

208
00:10:50,540 --> 00:10:54,430
ne jemi vetëm përsëritur atë në
një strukturë listë e lidhur në formë individuale

209
00:10:54,430 --> 00:10:56,280
në vend të duke përdorur një rrjet për të bërë atë.

210
00:10:56,280 --> 00:10:58,210
>> Kështu që këtu është një shembull i
një listë e lidhur në formë individuale.

211
00:10:58,210 --> 00:11:00,043
Kjo përbëhet nga
pesë nyjet, dhe ne kemi

212
00:11:00,043 --> 00:11:04,330
një tregues për kokën e të
Lista, e cila është quajtur listë.

213
00:11:04,330 --> 00:11:07,385
Gjëja e parë që ne duam të bëjmë është
përsëri, krijuar atë treguesin traversal.

214
00:11:07,385 --> 00:11:09,760
Pra, ne kemi tani dy pointers
që tregojnë për të njëjtën gjë.

215
00:11:09,760 --> 00:11:15,025
>> Tani, vini re edhe këtu, unë nuk e bëri
duhet të malloc ndonjë hapësirë ​​për trav.

216
00:11:15,025 --> 00:11:18,970
Unë nuk them trav barabartë malloc
diçka, që nyjen tashmë ekziston,

217
00:11:18,970 --> 00:11:21,160
se hapësira në kujtesë tashmë ekziston.

218
00:11:21,160 --> 00:11:24,290
Pra, të gjitha unë jam në të vërtetë duke bërë është
duke krijuar një tjetër tregues për të.

219
00:11:24,290 --> 00:11:28,210
Unë nuk jam mallocing një shtesë
hapësirë, vetëm të ketë tani dy pointers

220
00:11:28,210 --> 00:11:31,370
duke treguar të njëjtën gjë.

221
00:11:31,370 --> 00:11:33,710
>> Pra, është 2 ajo që unë jam duke kërkuar për?

222
00:11:33,710 --> 00:11:37,220
E pra, nuk ka, kështu që në vend të kësaj unë jam
do të shkojë në një tjetër.

223
00:11:37,220 --> 00:11:41,740
Pra, në thelb unë do të thoja,
Trav barabartë trav ardhshëm.

224
00:11:41,740 --> 00:11:43,630
Është 3 atë që unë jam duke kërkuar për të, nr.

225
00:11:43,630 --> 00:11:45,780
Kështu që unë të vazhdojë të shkojë
përmes, deri në fund

226
00:11:45,780 --> 00:11:48,690
merrni për 6 cila është ajo që unë jam duke kërkuar
për të bazuar në thirrjen e funksionit

227
00:11:48,690 --> 00:11:51,600
Unë kam në krye
atje, dhe kështu që unë jam bërë.

228
00:11:51,600 --> 00:11:54,150
>> Tani, çfarë nëse elementi unë jam
kërkoni nuk është në listë,

229
00:11:54,150 --> 00:11:55,510
po ajo ende do të punojë?

230
00:11:55,510 --> 00:11:57,120
Mirë, vini re se lista
këtu është Subtly të ndryshme,

231
00:11:57,120 --> 00:11:59,410
dhe kjo është një tjetër gjë që është
i rëndësishëm me listat e lidhura,

232
00:11:59,410 --> 00:12:01,780
ju nuk keni për të ruajtur
ata në asnjë mënyrë të veçantë.

233
00:12:01,780 --> 00:12:05,390
Ju mund të qoftë se ju doni, por
ju mund të keni vënë re tashmë

234
00:12:05,390 --> 00:12:09,310
se ne nuk jemi duke e mbajtur gjurmët e
çfarë numri element ne jemi në.

235
00:12:09,310 --> 00:12:13,150
>> Dhe kjo është lloj i një tregti që ne
kanë me listë të lidhura vargjet vargjeve,

236
00:12:13,150 --> 00:12:15,300
është ajo që ne nuk kemi
qasje të rastit më.

237
00:12:15,300 --> 00:12:18,150
Ne nuk mund të themi thjesht, unë dua
për të shkuar në elementin 0TH,

238
00:12:18,150 --> 00:12:21,410
ose elementi 6 e array tim,
që unë mund të bëjë në një grup.

239
00:12:21,410 --> 00:12:25,080
Unë nuk mund të them se unë dua të shkoj të
Element 0, ose element 6,

240
00:12:25,080 --> 00:12:30,360
ose elementi i 25-të listën time të lidhur,
nuk ka indeks të lidhur me to.

241
00:12:30,360 --> 00:12:33,660
Dhe kështu që nuk ka rëndësi
në qoftë se ne e ruajmë listën tonë në rregull.

242
00:12:33,660 --> 00:12:36,080
Në qoftë se ju doni të ju
me siguri mund të, por ka

243
00:12:36,080 --> 00:12:38,567
ka arsye pse ata duhet të
të ruhen në çdo mënyrë.

244
00:12:38,567 --> 00:12:40,400
Pra, përsëri, le të përpiqen dhe
gjeni 6 në këtë listë.

245
00:12:40,400 --> 00:12:43,200
E pra, ne të fillojë në nivel
fillim, ne nuk gjejmë 6,

246
00:12:43,200 --> 00:12:47,690
dhe atëherë ne nuk vazhdojmë gjetur
6, deri sa ne përfundimisht të marrë në këtu.

247
00:12:47,690 --> 00:12:52,790
Në mënyrë të drejtë pikë tani Trav në nyjen
permbajtur 8, dhe gjashtë nuk është në atje.

248
00:12:52,790 --> 00:12:55,250
>> Pra, hapi tjetër do të jetë
për të shkuar në treguesin e ardhshëm,

249
00:12:55,250 --> 00:12:57,440
kështu thonë Trav barabartë trav ardhshëm.

250
00:12:57,440 --> 00:13:00,750
E pra, trav tjetër, tregohet nga
kutia e kuqe atje, është i pavlefshëm.

251
00:13:00,750 --> 00:13:03,020
Pra, nuk ka askund tjetër për të
shkojnë, dhe kështu në këtë pikë

252
00:13:03,020 --> 00:13:06,120
mund të konstatojmë se ne kemi arritur
në fund të listës të lidhura,

253
00:13:06,120 --> 00:13:07,190
dhe 6 nuk është në atje.

254
00:13:07,190 --> 00:13:10,980
Dhe kjo do të kthehet
rreme në këtë rast.

255
00:13:10,980 --> 00:13:14,540
>> OK, si nuk kemi futur një të ri
Nyja në listën e lidhur?

256
00:13:14,540 --> 00:13:17,310
Pra, ne kemi qenë në gjendje për të krijuar
një listë e lidhur nga askund,

257
00:13:17,310 --> 00:13:19,370
por ne ndoshta dëshironi të
të ndërtuar një zinxhir dhe jo

258
00:13:19,370 --> 00:13:22,620
të krijojë një bandë e listave të dallueshme.

259
00:13:22,620 --> 00:13:25,700
Ne duam të kemi një listë që
ka një bandë e nyjeve në të,

260
00:13:25,700 --> 00:13:28,040
jo një bandë e listave me një nyje të vetme.

261
00:13:28,040 --> 00:13:31,260
Pra, ne nuk mund të mbajnë vetëm duke përdorur Krijo
Funksioni ne përcaktuar më herët, tani ne

262
00:13:31,260 --> 00:13:33,860
doni të futur në një
listë që tashmë ekziston.

263
00:13:33,860 --> 00:13:36,499
>> Pra këtë rast, ne jemi duke shkuar
për të kaluar në dy argumente,

264
00:13:36,499 --> 00:13:39,290
tregues në kokë e që
lidhur listë që doni të shtoni në.

265
00:13:39,290 --> 00:13:40,910
Përsëri, kjo është arsyeja pse është kaq
e rëndësishme që ne gjithmonë

266
00:13:40,910 --> 00:13:43,400
mbajnë gjurmët e saj, sepse
kjo është e vetmja mënyrë me të vërtetë

267
00:13:43,400 --> 00:13:46,690
duhet të referohen tërë lista është
vetëm nga një tregues të elementit të parë.

268
00:13:46,690 --> 00:13:49,360
Pra, ne duam të kalojë në një
treguesin për këtë elementin e parë,

269
00:13:49,360 --> 00:13:52,226
dhe çdo gjë që vlera ne
doni të shtoni në listën.

270
00:13:52,226 --> 00:13:54,600
Dhe përfundimisht ky funksion
do të kthehet një akrep

271
00:13:54,600 --> 00:13:57,980
të kreut të ri të një listë të lidhura.

272
00:13:57,980 --> 00:13:59,700
>> Cilat janë hapat e përfshira këtu?

273
00:13:59,700 --> 00:14:02,249
E pra, ashtu si me të krijuar,
ne kemi nevojë për dinamike ndajë

274
00:14:02,249 --> 00:14:05,540
hapësirë ​​për një nyje të re, dhe kontrolloni për të bërë
sigurt se ne nuk do të dalë jashtë kujtesës, përsëri,

275
00:14:05,540 --> 00:14:07,150
sepse ne jemi duke përdorur malloc.

276
00:14:07,150 --> 00:14:09,080
Atëherë ne duam të populloj
dhe futur nyjen,

277
00:14:09,080 --> 00:14:12,730
kështu që vënë numrin, çfarëdo
val është, në nyje.

278
00:14:12,730 --> 00:14:17,310
Ne duam të futur nyjen në
fillimi i listës lidhur.

279
00:14:17,310 --> 00:14:19,619
>> Ka një arsye që unë
duan për të bërë këtë, dhe kjo

280
00:14:19,619 --> 00:14:21,910
mund të jetë me vlerë duke marrë një të dytë
për pauzë video të këtu,

281
00:14:21,910 --> 00:14:25,860
dhe mendoj se pse unë do të duan të
futur në fillim të një i lidhur

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

283
00:14:26,589 --> 00:14:28,630
Përsëri, unë përmenda më parë
se ajo nuk ka të vërtetë

284
00:14:28,630 --> 00:14:33,020
rëndësi nëse ne e ruajmë atë në ndonjë
mënyrë, kështu që ndoshta kjo është një e dhënë.

285
00:14:33,020 --> 00:14:36,040
Dhe ju e panë se çfarë do të ndodhte nëse ne
donte to-- ose nga vetëm një sekondë

286
00:14:36,040 --> 00:14:37,360
më parë, kur ne ishim duke shkuar
përmes kërkimit të

287
00:14:37,360 --> 00:14:39,235
mund të shohin se çfarë mund të
të ndodhë në qoftë se ne ishim duke u përpjekur

288
00:14:39,235 --> 00:14:41,330
për të futur në fund të lista.

289
00:14:41,330 --> 00:14:44,750
Sepse ne nuk kemi një
tregues për fund te lista.

290
00:14:44,750 --> 00:14:47,490
>> Pra, arsyeja që unë do të duan
për të futur në fillim,

291
00:14:47,490 --> 00:14:49,380
është për shkak se unë mund ta bëjë këtë menjëherë.

292
00:14:49,380 --> 00:14:52,730
Unë kam një akrep në fillim, dhe
ne do të shohim këtë në një vizuale në një të dytë.

293
00:14:52,730 --> 00:14:55,605
Por në qoftë se unë dua të futur në fund,
Unë duhet të fillojë në fillim,

294
00:14:55,605 --> 00:14:58,760
përshkojnë gjithë rrugës për në
fund, dhe pastaj tack atë.

295
00:14:58,760 --> 00:15:01,420
Kështu që do të thotë se
futur në fund të lista

296
00:15:01,420 --> 00:15:04,140
do të bëhet një o të n
operacion, duke shkuar prapa

297
00:15:04,140 --> 00:15:06,720
në diskutimin tonë të
Kompleksiteti kompjuterike.

298
00:15:06,720 --> 00:15:10,140
Ajo do të bëhet një o e operimit n, ku
si lista mori të madhe, dhe më të mëdha,

299
00:15:10,140 --> 00:15:13,310
dhe më të mëdha, ajo do të bëhet gjithnjë e
më e vështirë për litar diçka

300
00:15:13,310 --> 00:15:14,661
më në fund.

301
00:15:14,661 --> 00:15:17,410
Por është gjithmonë vërtetë e lehtë për
litar diçka në në fillim,

302
00:15:17,410 --> 00:15:19,060
ju jeni gjithmonë në fillim.

303
00:15:19,060 --> 00:15:21,620
>> Dhe ne do të shohim një vizuale të këtë përsëri.

304
00:15:21,620 --> 00:15:24,100
Dhe pastaj një herë ne jemi duke bërë, dikur
ne kemi futur nyjen e re,

305
00:15:24,100 --> 00:15:26,880
ne duam të kthehen treguesin tonë për
kreu i ri i një liste të lidhura, të cilat

306
00:15:26,880 --> 00:15:29,213
që ne jemi futur në nivel
duke filluar, në të vërtetë do të jetë

307
00:15:29,213 --> 00:15:31,060
një tregues për nyjen ne vetëm krijuar.

308
00:15:31,060 --> 00:15:33,280
Le të kujtoj këtë,
sepse unë mendoj se kjo do të ndihmojë.

309
00:15:33,280 --> 00:15:36,661
>> Kështu që këtu është lista jonë, ajo përbëhet nga
katër elemente, një nyje që përmban 15,

310
00:15:36,661 --> 00:15:38,410
i cili tregon në një nyje
permbajtur 9, e cila

311
00:15:38,410 --> 00:15:41,370
tregon për një nyje përmban 13,
e cila tregon për një nyje që përmban

312
00:15:41,370 --> 00:15:44,840
10, e cila ka null
akrep si tregues të saj të ardhshëm

313
00:15:44,840 --> 00:15:47,010
kështu që është fundi i listës.

314
00:15:47,010 --> 00:15:50,200
Pra, ne duam të futur një
nyje e re me vlerën 12

315
00:15:50,200 --> 00:15:52,720
në fillim të kësaj
lista, çfarë bëjmë ne?

316
00:15:52,720 --> 00:15:58,770
E pra, së pari ne malloc hapësirë ​​për
nyje, dhe pastaj ne kemi vënë 12 në atje.

317
00:15:58,770 --> 00:16:02,211
>> Deri tani ne kemi arritur në një
Pika vendim, e drejtë?

318
00:16:02,211 --> 00:16:03,960
Ne kemi një çift të
pointers që ne mund të

319
00:16:03,960 --> 00:16:06,770
veprim, i cili duhet të ecim së pari?

320
00:16:06,770 --> 00:16:09,250
A duhet të bëjë 12 pikë për të
kreu i ri i list--

321
00:16:09,250 --> 00:16:13,020
ose më falni, duhet të bëjmë 12
tregojnë për kreun e vjetër të listës?

322
00:16:13,020 --> 00:16:15,319
Ose duhet të themi se
Lista e tani fillon në 12.

323
00:16:15,319 --> 00:16:17,110
Ka një dallim
atje, dhe ne do të shikojmë

324
00:16:17,110 --> 00:16:19,870
se çfarë ndodh me të dyja në një të dytë.

325
00:16:19,870 --> 00:16:23,350
>> Por kjo çon në një
temë e madhe për sidebar,

326
00:16:23,350 --> 00:16:26,280
cilës është që një nga
gjëra të mprehtë me listat e lidhura

327
00:16:26,280 --> 00:16:30,980
është për të rregulluar pointers
në mënyrë korrekte.

328
00:16:30,980 --> 00:16:34,520
Në qoftë se ju të lëvizur gjërat nga e rendit,
ju mund të përfundojnë aksidentalisht

329
00:16:34,520 --> 00:16:36,050
orphaning pjesën tjetër të listës.

330
00:16:36,050 --> 00:16:37,300
Dhe këtu është një shembull i kësaj.

331
00:16:37,300 --> 00:16:40,540
Pra, le të shkojë me idenë of--
mirë, ne kemi krijuar vetëm 12.

332
00:16:40,540 --> 00:16:43,180
Ne e dimë se 12 do të jetë
kreu i ri i listës,

333
00:16:43,180 --> 00:16:47,660
dhe kështu që pse nuk kemi vetëm të lëvizë
Lista tregues për pikë atje.

334
00:16:47,660 --> 00:16:49,070
>> OK, kështu që kjo është e mirë.

335
00:16:49,070 --> 00:16:51,560
Deri tani ku ka 12 pikë tjetër?

336
00:16:51,560 --> 00:16:54,580
Unë do të thotë, vizualisht ne mund të shohim
që do pikë në 15,

337
00:16:54,580 --> 00:16:57,250
si njerëzit është e vërtetë e qartë për ne.

338
00:16:57,250 --> 00:17:00,300
Si e kompjuterit e di?

339
00:17:00,300 --> 00:17:02,720
Ne nuk kemi asgjë
duke treguar për 15 më, e drejtë?

340
00:17:02,720 --> 00:17:05,869
>> Ne kemi humbur çdo aftësinë për t'iu referuar 15.

341
00:17:05,869 --> 00:17:11,460
Ne nuk mund të themi shigjetë e re është e barabartë e ardhshme
diçka, nuk ka asgjë atje.

342
00:17:11,460 --> 00:17:13,510
Në fakt, ne kemi jetimë
pjesa tjetër e listës

343
00:17:13,510 --> 00:17:16,465
duke bërë kështu, ne kemi
thyer aksidentalisht zinxhir.

344
00:17:16,465 --> 00:17:18,089
Dhe ne me siguri nuk duan ta bëjnë këtë.

345
00:17:18,089 --> 00:17:20,000
>> Pra, le të kthehemi dhe të provoni këtë përsëri.

346
00:17:20,000 --> 00:17:24,060
Ndoshta gjëja e drejtë për të bërë
është për të vendosur 12 për treguesin e ardhshme

347
00:17:24,060 --> 00:17:28,290
të kreut të vjetër të listës së parë,
atëherë ne mund të lëvizin listën e gjatë.

348
00:17:28,290 --> 00:17:30,420
Dhe në fakt, se është
mënyrë korrekte se ne

349
00:17:30,420 --> 00:17:32,836
duhet të ndiqni kur ne jemi
duke punuar me listën e lidhur në formë individuale.

350
00:17:32,836 --> 00:17:36,460
Ne gjithmonë duam të lidhë
element i ri në listë,

351
00:17:36,460 --> 00:17:41,010
para se të marrë këtë lloj të
hap i rëndësishëm i ndryshimit

352
00:17:41,010 --> 00:17:43,360
ku kreu i listës është lidhur.

353
00:17:43,360 --> 00:17:46,740
Përsëri, kjo është një gjë e tillë themelor,
ne nuk duan të humbasin gjurmët e saj.

354
00:17:46,740 --> 00:17:49,310
>> Pra, ne duam të sigurohemi që
çdo gjë është e lidhur me zinxhirë së bashku,

355
00:17:49,310 --> 00:17:52,040
para se të lëvizin atë treguesin.

356
00:17:52,040 --> 00:17:55,300
Dhe kështu kjo do të jetë mënyrë korrekte,
e cila është për të lidhur 12 në listë,

357
00:17:55,300 --> 00:17:57,630
pastaj thonë se lista fillon një 12.

358
00:17:57,630 --> 00:18:00,860
Nëse ne tha se lista fillon në 12 dhe
pastaj u përpoq për të lidhur 12 në listë,

359
00:18:00,860 --> 00:18:02,193
ne kemi parë tashmë se çfarë ndodh.

360
00:18:02,193 --> 00:18:04,920
Kemi humbur listën gabimisht.

361
00:18:04,920 --> 00:18:06,740
>> OK, kështu që një gjë më shumë për të folur rreth.

362
00:18:06,740 --> 00:18:09,750
Çfarë ndodh nëse ne duam që të shpëtoj të
një të tërë lidhur me listë në të njëjtën kohë?

363
00:18:09,750 --> 00:18:11,750
Përsëri, ne jemi mallocing
gjithë kjo hapësirë, dhe kështu që ne

364
00:18:11,750 --> 00:18:13,351
nevojë për të liruar atë, kur ne jemi duke bërë.

365
00:18:13,351 --> 00:18:15,350
Pra, tani ne duam të fshini
të gjithë listë e lidhur.

366
00:18:15,350 --> 00:18:16,850
E pra, çfarë duam të bëjmë?

367
00:18:16,850 --> 00:18:20,460
>> Në qoftë se ne kemi arritur treguesin null, ne
duan për të ndaluar, ndryshe, vetëm fshini

368
00:18:20,460 --> 00:18:23,420
pjesa tjetër e listës dhe pastaj të lirë më.

369
00:18:23,420 --> 00:18:28,890
Fshij pjesën tjetër të listës,
dhe pastaj pa nyjen aktual.

370
00:18:28,890 --> 00:18:32,850
Çfarë e bën atë të tingëllojë si,
çfarë teknikë kemi biseduar

371
00:18:32,850 --> 00:18:35,440
për më herët A tingëllon kjo si?

372
00:18:35,440 --> 00:18:39,560
Fshij gjithë të tjerët, atëherë
të kthehen dhe të fshini mua.

373
00:18:39,560 --> 00:18:42,380
>> Kjo është recursion, ne kemi bërë
Problemi pak më të vogël,

374
00:18:42,380 --> 00:18:46,910
ne jemi duke thënë të fshini të gjithë
tjetër, atëherë ju mund të fshini mua.

375
00:18:46,910 --> 00:18:50,940
Dhe më tej poshtë rrugës, që nyje
do të thotë, fshini gjithë të tjerët.

376
00:18:50,940 --> 00:18:53,940
Por në fund ne do të merrni të
Pika ku lista është i pavlefshëm,

377
00:18:53,940 --> 00:18:55,310
dhe kjo është rasti ynë bazë.

378
00:18:55,310 --> 00:18:57,010
>> Pra, le të marrin një vështrim në këtë,
dhe se si kjo mund të punojnë.

379
00:18:57,010 --> 00:18:59,759
Kështu që këtu është lista jonë, kjo është e njëjta
lista ne ishim vetëm duke folur për,

380
00:18:59,759 --> 00:19:00,980
dhe ka hapat.

381
00:19:00,980 --> 00:19:04,200
Nuk është një shumë e tekstit këtu, por
shpresojmë se vizualizimi do të ndihmojë.

382
00:19:04,200 --> 00:19:08,557
>> Pra, ne have-- dhe unë gjithashtu u tërhoq
up korniza rafte tonë ilustrim

383
00:19:08,557 --> 00:19:10,890
nga video tonë në oxhaqet e thirrjes,
dhe shpresojmë se e gjithë kjo

384
00:19:10,890 --> 00:19:13,260
së bashku do të ju tregojnë se çfarë po ndodh.

385
00:19:13,260 --> 00:19:14,510
Kështu që këtu është kodi ynë pseudokod.

386
00:19:14,510 --> 00:19:17,830
Nëse arrijmë një null
akrep, të ndaluar, ndryshe,

387
00:19:17,830 --> 00:19:21,320
fshini pjesën tjetër të listës,
pastaj pa nyjen aktual.

388
00:19:21,320 --> 00:19:25,700
Deri tani, list--
tregues se ne jemi

389
00:19:25,700 --> 00:19:28,410
duke kaluar në të shkatërrojë pikë për 12.

390
00:19:28,410 --> 00:19:33,340
12 nuk është një tregues i pavlefshëm, kështu që ne jemi
do të fshini pjesën tjetër të listës.

391
00:19:33,340 --> 00:19:35,450
>> Çfarë fshirjes
pjesa tjetër prej nesh të përfshirë?

392
00:19:35,450 --> 00:19:37,950
E pra, kjo do të thotë duke bërë një
thirrje për të shkatërruar, duke thënë:

393
00:19:37,950 --> 00:19:42,060
se 15 është fillimi i
Pjesa tjetër e listës ne duam për të shkatërruar.

394
00:19:42,060 --> 00:19:47,480
Dhe kështu thirrja për të shkatërruar
12 është lloj i në pritje.

395
00:19:47,480 --> 00:19:52,690
Është ngrirë atje, duke pritur për
thirrje për të shkatërruar 15, për të përfunduar punën e saj.

396
00:19:52,690 --> 00:19:56,280
>> E pra, 15 nuk është një tregues i pavlefshëm, dhe
kështu ajo do të thotë, të gjithë të drejtë,

397
00:19:56,280 --> 00:19:58,450
mirë, fshini pjesën tjetër të listës.

398
00:19:58,450 --> 00:20:00,760
Pjesa tjetër e listës fillon
në 9, dhe kështu që ne do të vetëm

399
00:20:00,760 --> 00:20:04,514
prisni deri sa ju të fshini të gjithë atë
gjëra, pastaj të kthehen dhe të fshini mua.

400
00:20:04,514 --> 00:20:06,680
E pra 9 do të them, mirë,
Unë nuk jam një tregues null,

401
00:20:06,680 --> 00:20:09,020
kështu fshini pjesa tjetër e listës nga këtu.

402
00:20:09,020 --> 00:20:11,805
Dhe kështu që të përpiqet dhe të shkatërrojë 13.

403
00:20:11,805 --> 00:20:15,550
13 thotë, unë nuk jam akrep null,
njëjta gjë, ai kalon dollar.

404
00:20:15,550 --> 00:20:17,930
10 nuk është tregues i pavlefshëm, 10
përmban një tregues null,

405
00:20:17,930 --> 00:20:20,200
por 10 nuk është në vetvete një
null treguesin e drejtë tani,

406
00:20:20,200 --> 00:20:22,470
dhe kështu ai kalon dollar shumë.

407
00:20:22,470 --> 00:20:25,560
>> Dhe tani lista pikë atje, atë
me të vërtetë do të tregojnë për some--

408
00:20:25,560 --> 00:20:28,710
në qoftë se kam pasur më shumë hapësirë ​​në imazhin,
kjo do të tregojnë për një hapësirë ​​të rastit

409
00:20:28,710 --> 00:20:29,960
që ne nuk e dimë se çfarë është ajo.

410
00:20:29,960 --> 00:20:34,680
Kjo është tregues null pse, lista
është fjalë për fjalë vendosur tani është vlera null.

411
00:20:34,680 --> 00:20:36,820
Është vënë të drejtë brenda asaj kutie të kuqe.

412
00:20:36,820 --> 00:20:39,960
Ne kemi arritur në një tregues null, kështu
ne mund të ndalojë, dhe ne jemi duke bërë.

413
00:20:39,960 --> 00:20:46,230
>> Dhe kështu kjo kornizë purpurt është now-- në nivel
krye të stack-- që është kornizë aktiv,

414
00:20:46,230 --> 00:20:47,017
por kjo është bërë.

415
00:20:47,017 --> 00:20:48,600
Në qoftë se ne kemi arritur në një tregues null, të ndaluar.

416
00:20:48,600 --> 00:20:51,290
Ne nuk bëjmë asgjë, ne
nuk mund të lirë një tregues null,

417
00:20:51,290 --> 00:20:55,070
ne nuk malloc asnjë
hapësirë, dhe kështu që ne jemi duke bërë.

418
00:20:55,070 --> 00:20:57,590
Pra, atë kornizë funksionit
është shkatërruar, dhe ne

419
00:20:57,590 --> 00:21:00,930
resume-- ne të vini deri ku kemi lënë
off me një tjetër më të lartë, i cili

420
00:21:00,930 --> 00:21:02,807
është kjo kornizë blu të errët këtu.

421
00:21:02,807 --> 00:21:04,390
Pra, ne të marr të drejtë ku ne u ndërpre.

422
00:21:04,390 --> 00:21:06,598
Ne fshihet pjesa tjetër e
Lista e tashmë, kështu që tani ne jemi

423
00:21:06,598 --> 00:21:08,000
duke shkuar për të liruar nyjet aktuale.

424
00:21:08,000 --> 00:21:12,920
Deri tani ne mund të lirë këtë nyje, dhe tani
ne kemi arritur në fund të funksionit.

425
00:21:12,920 --> 00:21:16,810
Dhe kështu që kornizë funksion është shkatërruar,
dhe ne të marr në një dritë blu.

426
00:21:16,810 --> 00:21:20,650
>> Pra, ajo që unë kam tashmë says-- done--
fshirjes pjesën tjetër të listës, kështu që

427
00:21:20,650 --> 00:21:23,140
pa nyjen aktual.

428
00:21:23,140 --> 00:21:26,520
Dhe tani kornizë e verdhë është
përsëri në krye të rafte.

429
00:21:26,520 --> 00:21:29,655
Dhe kështu siç e shihni, ne jemi tani
shkatërruar listën nga djathta në të majtë.

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

431
00:21:33,710 --> 00:21:37,280
>> Çfarë do të kishte ndodhur, edhe pse,
nëse do të kishim bërë gjëra rrugën e gabuar?

432
00:21:37,280 --> 00:21:39,410
Ashtu si kur ne u përpoqëm
për të shtuar një element.

433
00:21:39,410 --> 00:21:41,909
Nëse ne messed up zinxhir, nëse
ne nuk lidhë pointers

434
00:21:41,909 --> 00:21:44,690
në mënyrë korrekte, në qoftë se ne
vetëm liruar elementin e parë,

435
00:21:44,690 --> 00:21:47,420
në qoftë se ne vetëm liroi
kreu i listës, tani ne

436
00:21:47,420 --> 00:21:49,642
nuk kanë asnjë mënyrë për t'iu referuar
pjesa tjetër e listës.

437
00:21:49,642 --> 00:21:51,350
Dhe kështu ne do të kemi
çdo gjë jetimë,

438
00:21:51,350 --> 00:21:53,880
ne do të kishte çfarë është
quajtur një rrjedhje kujtim.

439
00:21:53,880 --> 00:21:56,800
Nëse ju kujtohet nga video tonë
në ndarjen e kujtesës dinamike,

440
00:21:56,800 --> 00:21:58,650
kjo nuk është gjë shumë e mirë.

441
00:21:58,650 --> 00:22:00,810
>> Pra, siç thashë, aty
disa operacione

442
00:22:00,810 --> 00:22:04,010
që ne duhet të përdorim për të punuar
me listën e lidhura në mënyrë efektive.

443
00:22:04,010 --> 00:22:08,430
Dhe ju mund të keni vënë re unë lënë jashtë një,
fshirjes një element të vetëm nga një i lidhur

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

445
00:22:09,064 --> 00:22:10,980
Arsyeja që unë e bëri atë
është në fakt lloj i

446
00:22:10,980 --> 00:22:14,360
ndërlikuar për të menduar rreth asaj se si për të fshirë
një element i vetëm nga një formë individuale

447
00:22:14,360 --> 00:22:15,600
listë e lidhur.

448
00:22:15,600 --> 00:22:19,950
Ne duhet të jenë në gjendje të kaloni mbi
diçka në listë, e cila

449
00:22:19,950 --> 00:22:22,975
do të thotë ne kemi marrë për një ne point--
dëshironi të fshini këtë node--

450
00:22:22,975 --> 00:22:25,350
por në mënyrë për ta bërë atë kështu që ne
nuk humbasin ndonjë informacion,

451
00:22:25,350 --> 00:22:30,530
ne kemi nevojë për të lidhur këtë
nyje këtu, këtu.

452
00:22:30,530 --> 00:22:33,390
>> Kështu që unë ndoshta e bëri atë gabim
nga një perspektivë vizuale.

453
00:22:33,390 --> 00:22:36,830
Pra, ne jemi në fillim të tonë
lista, ne jemi duke vazhduar përmes,

454
00:22:36,830 --> 00:22:40,510
ne duam të fshini këtë nyje.

455
00:22:40,510 --> 00:22:43,440
Nëse ne vetëm fshini atë,
ne kemi thyer zinxhir.

456
00:22:43,440 --> 00:22:45,950
Kjo nyje e drejtë këtu
i referohet çdo gjë tjetër,

457
00:22:45,950 --> 00:22:48,260
ai përmban zinxhir nga këtu në jashtë.

458
00:22:48,260 --> 00:22:51,190
>> Pra, ajo që ne duhet të bëjmë në fakt
pasi ne të merrni në këtë pikë,

459
00:22:51,190 --> 00:22:56,670
është që ne duhet të hap prapa një, dhe
lidhë këtë nyje mbi këtë nyje,

460
00:22:56,670 --> 00:22:58,590
kështu që ne pastaj mund të fshini
një në mes.

461
00:22:58,590 --> 00:23:02,120
Por listat lidhura veçmas nuk
na ofrojnë një mënyrë për të shkuar prapa.

462
00:23:02,120 --> 00:23:05,160
Pra, ne kemi nevojë për të mbajtur ose
dy pointers, dhe ata lëvizin

463
00:23:05,160 --> 00:23:09,527
lloj i hap jashtë, një prapa
tjetrin si ne do të shkojmë, ose të marrë në një pikë

464
00:23:09,527 --> 00:23:11,110
dhe pastaj të dërguar një tjetër treguesin përmes.

465
00:23:11,110 --> 00:23:13,150
Dhe si ju mund të shihni atë,
mund të merrni një helaq pak.

466
00:23:13,150 --> 00:23:15,360
Për fat të mirë, ne kemi
një tjetër mënyrë për të zgjidhur atë,

467
00:23:15,360 --> 00:23:17,810
kur flasim për listat lidhura dyfish.

468
00:23:17,810 --> 00:23:20,720
>> Unë jam Doug Lloyd, kjo është CS50.

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