1
00:00:00,000 --> 00:00:02,832
>> [MUSIC nagpe-play]

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

3
00:00:05,670 --> 00:00:08,560
>> DOUG LLOYD: OK, para sa
sa puntong ito sa panahon,

4
00:00:08,560 --> 00:00:15,300
sakop na namin ang isang pulutong ng mga pangunahing kaalaman ng C.
Alam namin ng maraming tungkol sa mga variable, array,

5
00:00:15,300 --> 00:00:17,610
mga payo, lahat na magagandang bagay-bagay.

6
00:00:17,610 --> 00:00:21,610
Ang mga ay ang lahat ng uri ng mga itinayo
in upang makita ang bilang batayan,

7
00:00:21,610 --> 00:00:23,880
ngunit maaari naming makagawa ng higit pa, i-right?

8
00:00:23,880 --> 00:00:27,930
Maaari naming pagsamahin ang mga bagay
sama-sama sa mga kawili-wiling paraan.

9
00:00:27,930 --> 00:00:31,010
>> At ni gawin iyon upang ipaalam, sabihin magsimula
upang magpalago ng negosiyo ng kung ano ang nagbibigay sa amin C,

10
00:00:31,010 --> 00:00:35,270
at simulan upang lumikha ng aming sariling data
kaayusan ng paggamit ng mga gusali

11
00:00:35,270 --> 00:00:40,590
bloke ng magkasama upang gawin ang isang bagay
talagang mahalaga, kapaki-pakinabang.

12
00:00:40,590 --> 00:00:43,420
Ang isang paraan na maaari naming gawin ito ay
upang makipag-usap tungkol sa mga koleksyon.

13
00:00:43,420 --> 00:00:48,360
Kaya ngayon kami ay nagkaroon ng isang uri ng data
structure para sa kumakatawan sa mga koleksyon

14
00:00:48,360 --> 00:00:51,030
ng gusto halaga, katulad na halaga.

15
00:00:51,030 --> 00:00:52,350
Iyon ay magiging isang array.

16
00:00:52,350 --> 00:00:57,020
Mayroon kaming mga koleksyon ng mga integer, o
mga koleksyon ng mga character at iba pa.

17
00:00:57,020 --> 00:01:00,890
>> Istruktura ay ayusin din ng isang data
structure para sa pagkolekta ng impormasyon,

18
00:01:00,890 --> 00:01:03,220
ngunit ito ay hindi para sa pagkolekta ng tulad ng mga halaga.

19
00:01:03,220 --> 00:01:08,090
Karaniwan itong mix iba't ibang mga uri ng data
sama sa loob ng isang kahon.

20
00:01:08,090 --> 00:01:10,750
Ngunit ito ay hindi mismo
ginagamit upang chain magkasama

21
00:01:10,750 --> 00:01:16,920
o kumonekta magkasama katulad
bagay, tulad ng isang array.

22
00:01:16,920 --> 00:01:20,960
Ang mga array ay mahalaga para sa
element maghanap, ngunit pagpapabalik

23
00:01:20,960 --> 00:01:24,262
na ito ay mahirap
upang ipasok sa isang array,

24
00:01:24,262 --> 00:01:26,470
maliban kung kami ay pagpasok sa
sa dulo ng array na.

25
00:01:26,470 --> 00:01:29,730
>> At ang pinakamahusay na halimbawa ko
para sa na ay uri insertion.

26
00:01:29,730 --> 00:01:31,650
Kung isipin mo ang aming mga video
on-uuri,

27
00:01:31,650 --> 00:01:34,110
nagkaroon ng maraming
gastos na kasangkot sa pagkakaroon

28
00:01:34,110 --> 00:01:37,970
upang kunin ang mga elemento, at ilipat ang mga ito
sa labas ng paraan upang magkasya ang isang bagay

29
00:01:37,970 --> 00:01:41,290
sa gitna ng iyong array.

30
00:01:41,290 --> 00:01:44,690
Magtiis din Arrays mula sa isa pang
problema, na kung saan ay katigasan.

31
00:01:44,690 --> 00:01:47,150
Kung ating sinasabing isang array,
makakakuha tayo ng isang shot at ito.

32
00:01:47,150 --> 00:01:49,790
Makuha namin upang sabihin, gusto ko
ito maraming mga sangkap.

33
00:01:49,790 --> 00:01:51,940
Maaaring maging 100, maaaring ito
maging 1000, maaaring ito

34
00:01:51,940 --> 00:01:55,930
maging x kung saan ang x ay isang numero na ang gumagamit
nagbigay sa amin sa isang prompt o sa utos

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

36
00:01:56,630 --> 00:01:59,905
>> Ngunit lamang namin makakuha ng isa pagbaril sa ito, kami
hindi makapunta sa pagkatapos ay sabihin oh, tunay na ako

37
00:01:59,905 --> 00:02:04,360
kailangan 101, o kailangan ko x plus 20.

38
00:02:04,360 --> 00:02:07,910
Masyadong huli, na ipinahayag na namin ang
array, at kung gusto naming makuha 101 o x

39
00:02:07,910 --> 00:02:12,050
plus 20, mayroon kaming na idedeklara
isang ganap na magkaibang array,

40
00:02:12,050 --> 00:02:15,540
kopyahin ang lahat ng mga elemento ng array
sa ibabaw, at pagkatapos kami ay may sapat.

41
00:02:15,540 --> 00:02:19,880
At paano kung tayo ay muli mali, kung ano
kung talagang kailangan namin ng 102, o x plus 40,

42
00:02:19,880 --> 00:02:21,970
kami ay may sa gawin ito muli.

43
00:02:21,970 --> 00:02:26,250
Kaya ang mga ito masyadong matigas
para sa pagbabago ng laki ng aming data,

44
00:02:26,250 --> 00:02:29,360
ngunit kung pagsamahin namin magkasama ang ilang mga
sa mga pangunahing kaalaman na kami na

45
00:02:29,360 --> 00:02:33,230
natutunan ang tungkol sa mga payo at kaayusan,
sa mga partikular na gumagamit ng mga dynamic memory

46
00:02:33,230 --> 00:02:36,180
laang-gugulin sa malloc, namin
maaaring ilagay ang mga piraso ng magkasama

47
00:02:36,180 --> 00:02:40,960
upang lumikha ng isang bagong data structure-- isang
isa-isa ang listahan upang tayo say-- naka-link

48
00:02:40,960 --> 00:02:45,400
na nagbibigay-daan sa amin upang maging at
pag-urong ng isang koleksyon ng mga halaga

49
00:02:45,400 --> 00:02:48,800
at hindi kami ay may anumang mga nasayang na espasyo.

50
00:02:48,800 --> 00:02:53,320
>> Kaya muli, ang tawag namin sa mga ideya na ito,
paniwala na ito, ang isang listahan ng mga link.

51
00:02:53,320 --> 00:02:56,320
Sa partikular, sa video na ito hindi namin
pakikipag-usap tungkol sa kanyang sarili na naka-link na listahan,

52
00:02:56,320 --> 00:02:59,185
at pagkatapos ng isa pang video namin makipag-usap
tungkol sa doble-link na listahan, kung saan

53
00:02:59,185 --> 00:03:01,560
ay isang pagkakaiba-iba lamang sa isang tema dito.

54
00:03:01,560 --> 00:03:05,200
Ngunit isang isa-isa listahan ng mga link
ay binubuo ng mga nodes,

55
00:03:05,200 --> 00:03:08,559
nodes lamang pagiging isang abstract term--
ito ay isang bagay na lang ako ng pagtawag

56
00:03:08,559 --> 00:03:10,350
iyan ay isang uri ng
istraktura, karaniwang, ako?

57
00:03:10,350 --> 00:03:16,190
Basta pagpunta sa tawag na ito ng isang node-- at ito
node ay may dalawang mga kasapi, o dalawang mga patlang.

58
00:03:16,190 --> 00:03:20,300
Ito ay may data, kadalasan ay isang
integer, isang character float,

59
00:03:20,300 --> 00:03:23,790
o maaaring ang ilang iba pang mga uri ng data
na tinukoy mo sa isang uri def.

60
00:03:23,790 --> 00:03:29,290
At ito ay naglalaman ng isang pointer sa
isa pang node ng parehong uri.

61
00:03:29,290 --> 00:03:34,710
>> Kaya kami ay may dalawang mga bagay-bagay sa loob ng
ito node, data at isang pointer

62
00:03:34,710 --> 00:03:36,380
sa ibang node.

63
00:03:36,380 --> 00:03:39,370
At kung nagsimula ka upang mailarawan
ito, maaari mong isipin ang tungkol dito

64
00:03:39,370 --> 00:03:42,280
tulad ng isang kadena ng mga nodes na
ay konektado magkasama.

65
00:03:42,280 --> 00:03:45,070
Tayo ang unang node, ito
naglalaman ng data, at ang isang pointer

66
00:03:45,070 --> 00:03:49,110
sa ikalawang node, na naglalaman ng
data, at isang pointer sa ikatlong node.

67
00:03:49,110 --> 00:03:52,940
At kaya na ang dahilan kung bakit ang tawag namin ito ng isang
listahan ng mga link, kasama ang mga ito ay naka-link.

68
00:03:52,940 --> 00:03:56,070
>> Ano ang ginagawa ng mga ito ng espesyal
istraktura node hitsura?

69
00:03:56,070 --> 00:04:01,120
Well, kung ang pagpapabalik sa iyo mula sa aming mga video sa
pagtukoy pasadyang uri, na may uri def,

70
00:04:01,120 --> 00:04:05,400
maaari naming tukuyin ang isang structure-- at
type tukuyin ang isang istraktura tulad nito.

71
00:04:05,400 --> 00:04:11,240
tyepdef struct sllist, at pagkatapos ay ako
gamit ang halaga ng salita dito nagkataon

72
00:04:11,240 --> 00:04:13,891
upang ipahiwatig ang anumang uri ng data talaga.

73
00:04:13,891 --> 00:04:16,890
Ikaw ay maaaring ipasa sa isang integer o float,
maaari kang magkaroon ng anumang nais mo.

74
00:04:16,890 --> 00:04:19,389
Hindi ito limitado sa mga lamang
integer, o anumang bagay tulad na.

75
00:04:19,389 --> 00:04:22,790
Kaya ang halaga ay lamang ng isang arbitrary
uri ng data, at pagkatapos ay isang pointer

76
00:04:22,790 --> 00:04:26,310
sa ibang node ng parehong uri.

77
00:04:26,310 --> 00:04:29,690
>> Ngayon, may isang maliit na catch
dito sa pagtukoy ng isang istraktura

78
00:04:29,690 --> 00:04:33,030
kapag ito ay isang istraktura sa sarili referential.

79
00:04:33,030 --> 00:04:35,340
Mayroon akong magkaroon ng isang pansamantalang
pangalan para sa aking mga istraktura.

80
00:04:35,340 --> 00:04:37,640
Sa katapusan ng araw ko
malinaw na gusto pangalanan ito

81
00:04:37,640 --> 00:04:43,030
sll node, na ang huli ang bagong
pangalanan bahagi ng aking mga kahulugan ng uri,

82
00:04:43,030 --> 00:04:47,450
ngunit hindi ako maaaring gumamit ng sll node
sa gitna ng mga ito.

83
00:04:47,450 --> 00:04:51,430
Ang dahilan ay, mayroon akong hindi
lumikha ng isang uri ng tinatawag sll node

84
00:04:51,430 --> 00:04:55,200
hanggang maabot ko ang huling punto dito.

85
00:04:55,200 --> 00:04:59,720
Hanggang sa puntong iyon, kailangan kong magkaroon
isa pang paraan upang sumangguni sa ganitong uri ng data.

86
00:04:59,720 --> 00:05:02,440
>> At ito ay isang self
referential uri ng data.

87
00:05:02,440 --> 00:05:06,314
Ito; s isang uri ng data ng isang
istraktura na naglalaman ng isang data,

88
00:05:06,314 --> 00:05:08,480
at isang pointer sa isa pang
istraktura ng parehong uri.

89
00:05:08,480 --> 00:05:11,750
Kaya kailangan ko upang ma-refer sa
ng ganitong uri ng data kahit pansamantala,

90
00:05:11,750 --> 00:05:14,910
kaya nagbibigay ito ng isang pansamantalang
pangalan ng struct sllist

91
00:05:14,910 --> 00:05:18,540
ay nagbibigay-daan sa akin na pagkatapos sabihin Gusto ko ng isang
pointer sa isa pang struct sllist,

92
00:05:18,540 --> 00:05:24,690
isang struct sllist star, at pagkatapos ay
matapos Nakumpleto ko na ang kahulugan,

93
00:05:24,690 --> 00:05:27,220
Maaari ko ngayon tumawag sa ganitong uri ng sll node.

94
00:05:27,220 --> 00:05:30,520
>> Kaya na ang dahilan kung bakit nakikita mo ang may
isang pansamantalang pangalan dito,

95
00:05:30,520 --> 00:05:31,879
ngunit isang permanenteng pangalan dito.

96
00:05:31,879 --> 00:05:33,920
Minsan maaari mong makita ang
mga kahulugan ng istraktura,

97
00:05:33,920 --> 00:05:36,570
halimbawa, na hindi
sa sarili referential, na

98
00:05:36,570 --> 00:05:39,390
hindi magkaroon ng isang pangalan specifier dito.

99
00:05:39,390 --> 00:05:43,040
Ito lamang sabihin typedef struct,
buksan kulot suhay at pagkatapos ay tukuyin ang mga ito.

100
00:05:43,040 --> 00:05:45,620
Ngunit kung ikaw ay struct ay self
referential, tulad ng isang ito ay,

101
00:05:45,620 --> 00:05:49,010
kailangan mong tukuyin ang isang
pansamantalang uri ng pangalan.

102
00:05:49,010 --> 00:05:51,310
Ngunit sa huli, ngayon
na tapos na namin ito,

103
00:05:51,310 --> 00:05:53,620
maaari naming lamang sumangguni sa
mga nodes, ang mga yunit,

104
00:05:53,620 --> 00:05:57,900
bilang sll nodes para sa mga layunin
ng ibang bahagi ng video na ito.

105
00:05:57,900 --> 00:06:00,900
>> Lahat ng mga karapatan, upang malaman namin kung paano sa
lumikha ng isang listahan ng mga link node.

106
00:06:00,900 --> 00:06:03,240
Alam namin kung paano upang tukuyin ang
isang listahan ng mga link node.

107
00:06:03,240 --> 00:06:06,670
Ngayon, kung kami ay pagpunta sa simulan
paggamit ng mga ito upang mangolekta ng impormasyon,

108
00:06:06,670 --> 00:06:10,360
may isang pares ng mga operasyon namin
kailangan upang maunawaan at gumagana sa.

109
00:06:10,360 --> 00:06:12,860
Kailangan nating malaman kung paano lumikha ng
isang listahan ng mga link sa labas ng manipis na hangin.

110
00:06:12,860 --> 00:06:14,901
Kung walang list na,
gusto naming magsimula ng isa.

111
00:06:14,901 --> 00:06:16,960
Kaya kailangan namin upang ma
upang lumikha ng isang listahan ng mga link,

112
00:06:16,960 --> 00:06:19,130
kailangan naming malamang na maghanap
sa pamamagitan ng listahan ng link

113
00:06:19,130 --> 00:06:21,830
upang maghanap ng isang elemento kaming naghahanap para sa.

114
00:06:21,830 --> 00:06:24,430
Kailangan namin upang magawang ipasok
ang mga bagong bagay sa listahan,

115
00:06:24,430 --> 00:06:25,930
gusto namin ang aming listahan upang ma-lalaki.

116
00:06:25,930 --> 00:06:28,638
At katulad, gusto naming ma
upang tanggalin ang mga bagay mula sa aming listahan,

117
00:06:28,638 --> 00:06:30,250
gusto namin ang aming listahan para ma-urong.

118
00:06:30,250 --> 00:06:32,160
At sa dulo ng ating
programa, lalo na

119
00:06:32,160 --> 00:06:34,550
kung isipin mo na hindi namin
magilas paglaan memory

120
00:06:34,550 --> 00:06:38,337
upang bumuo ng mga listahang ito kadalasan,
gusto naming magbakante ng lahat ng na memory

121
00:06:38,337 --> 00:06:39,670
kapag kami ay tapos na nagtatrabaho sa mga ito.

122
00:06:39,670 --> 00:06:44,627
At kaya kailangan namin upang ma-tanggalin ang isang
buong listahan na naka-link sa isa mabibigo mabilis na pagsalakay.

123
00:06:44,627 --> 00:06:46,460
Kaya sabihin pumunta sa pamamagitan ng
ang ilan sa mga operasyon

124
00:06:46,460 --> 00:06:51,192
at kung paano namin maaaring isalarawan ang mga ito,
pakikipag-usap sa pseudocode code mismo.

125
00:06:51,192 --> 00:06:53,150
Kaya gusto namin upang lumikha ng isang
list na naka-link, kaya siguro kami

126
00:06:53,150 --> 00:06:56,480
nais na tukuyin ang isang function
na may ganitong prototype.

127
00:06:56,480 --> 00:07:01,690
sll node star, lumikha, at ako makapasa
sa isang argument, ang ilang mga di-makatwirang data

128
00:07:01,690 --> 00:07:05,530
type muli, ng ilang di-makatwirang uri ng data.

129
00:07:05,530 --> 00:07:10,482
Ngunit ako returning-- ang function na ito ay dapat
bumalik sa akin ng isang pointer, sa isang isa-isa

130
00:07:10,482 --> 00:07:11,190
listahan ng mga link node.

131
00:07:11,190 --> 00:07:14,050
Muli, kami ay sinusubukan upang lumikha ng
isang listahan ng mga link sa labas ng manipis na hangin,

132
00:07:14,050 --> 00:07:17,900
kaya kailangan ko ng isang pointer sa
na listahan kapag ako tapos na.

133
00:07:17,900 --> 00:07:19,420
>> Kaya ano ang mga hakbang na kasangkot dito?

134
00:07:19,420 --> 00:07:20,960
Well, unang bagay na ako
pagpunta sa gawin ay magilas

135
00:07:20,960 --> 00:07:22,550
maglaan ng espasyo para sa isang bagong node.

136
00:07:22,550 --> 00:07:26,689
Muli, kami ay ang paglikha ito ng manipis
hangin, kaya kailangan naming malloc espasyo para dito.

137
00:07:26,689 --> 00:07:28,480
At siyempre, agad
pagkatapos naming malloc,

138
00:07:28,480 --> 00:07:31,692
palagi naming suriin upang tiyakin na ang aming
pointer-- hindi kami makabalik null.

139
00:07:31,692 --> 00:07:33,650
Dahil kung susubukan namin at
pagsang-ayon ng isang null pointer,

140
00:07:33,650 --> 00:07:36,190
kami ay pagpunta sa magdusa ng isang
segfault at hindi namin nais na.

141
00:07:36,190 --> 00:07:39,510
>> Pagkatapos na nais namin upang punan ang mga field,
gusto naming i-initialize ang patlang ng halaga

142
00:07:39,510 --> 00:07:41,690
at magpasimula ng mga susunod na field.

143
00:07:41,690 --> 00:07:45,450
At pagkatapos ay nais naming to-- huli bilang ang
function tularan indicates-- gusto namin

144
00:07:45,450 --> 00:07:49,940
upang magbalik ng pointer sa isang sll node.

145
00:07:49,940 --> 00:07:51,710
Kaya kung ano ang gumawa ng mga ito hitsura ng biswal?

146
00:07:51,710 --> 00:07:55,230
Well, first namin ang pagpunta sa mga dynamic na
maglaan ng espasyo para sa isang bagong sll node,

147
00:07:55,230 --> 00:07:58,320
kaya malloc-- namin na
isang visual na representasyon

148
00:07:58,320 --> 00:08:00,020
ng node na nilikha para lamang namin.

149
00:08:00,020 --> 00:08:02,757
At kami suriin upang tiyakin na
hindi ito null-- sa kasong ito,

150
00:08:02,757 --> 00:08:04,840
ang larawan ay hindi na kailangang
ipinapakita up kung ito ay null,

151
00:08:04,840 --> 00:08:07,298
Gusto namin Naubusan ng memorya,
kaya kami ay handa na upang pumunta doon.

152
00:08:07,298 --> 00:08:10,200
Kaya ngayon hindi namin sa hakbang C,
magpasimula ang patlang na halaga nodes.

153
00:08:10,200 --> 00:08:12,280
Well, ayon sa mga function na ito
tumawag ako ng gamit dito,

154
00:08:12,280 --> 00:08:16,700
Mukhang gusto kong pumasa sa 6,
kaya makikita ko ang 6 sa patlang ng halaga.

155
00:08:16,700 --> 00:08:18,865
Ngayon, magpasimula ang susunod na field.

156
00:08:18,865 --> 00:08:21,640
Well, kung ano ako pagpunta sa gawin doon,
walang anuman sa susunod, kanan,

157
00:08:21,640 --> 00:08:23,600
ito ay ang tanging bagay sa listahan.

158
00:08:23,600 --> 00:08:27,206
Kaya kung ano ang susunod na bagay sa listahan?

159
00:08:27,206 --> 00:08:29,660
>> Hindi ito dapat tumuro sa anumang bagay, right.

160
00:08:29,660 --> 00:08:33,600
May walang ibang tao doon, kaya kung ano ang
ang konsepto na aming kilala na nothing--

161
00:08:33,600 --> 00:08:35,638
mga payo sa wala?

162
00:08:35,638 --> 00:08:37,929
Dapat ito ay marahil ay gusto namin
maglagay ng isang null pointer doon,

163
00:08:37,929 --> 00:08:40,178
at kukunin ko na kumakatawan sa mga null
pointer bilang lamang ng isang red box,

164
00:08:40,178 --> 00:08:41,559
hindi namin maaaring pumunta sa anumang karagdagang.

165
00:08:41,559 --> 00:08:44,430
Tulad ng makikita namin makita ang isang maliit na sa susunod,
magkakaroon kami ng huli chains

166
00:08:44,430 --> 00:08:46,330
ng mga arrow sa pagkonekta
mga nodes magkasama,

167
00:08:46,330 --> 00:08:48,480
ngunit kapag ikaw ay pindutin ang
red box, na null,

168
00:08:48,480 --> 00:08:51,150
hindi namin maaaring pumunta anumang karagdagang,
iyon ang katapusan ng listahan.

169
00:08:51,150 --> 00:08:53,960
>> At bilang wakas, nais lang namin sa
ibalik ang isang pointer sa node.

170
00:08:53,960 --> 00:08:56,160
Kaya makikita tinatawag namin itong bago,
at babalik bagong

171
00:08:56,160 --> 00:08:59,370
kaya ito ay maaaring gamitin sa
kahit anong function lumikha nito.

172
00:08:59,370 --> 00:09:03,100
Kaya doon pumunta kami, Lumikha kami ng isa-isa
listahan ng mga link node sa labas ng manipis na hangin,

173
00:09:03,100 --> 00:09:05,920
at ngayon kami ay may isang listahan na maaari naming magtrabaho sa.

174
00:09:05,920 --> 00:09:08,260
>> Ngayon, sabihin natin na namin na
magkaroon ng isang malaking chain,

175
00:09:08,260 --> 00:09:09,800
at gusto naming mahanap ang isang bagay sa loob nito.

176
00:09:09,800 --> 00:09:12,716
At gusto namin ang isang function na pupuntahan
upang bumalik true o false, depende

177
00:09:12,716 --> 00:09:15,840
sa kung umiiral na ang isang halaga sa listahang iyon.

178
00:09:15,840 --> 00:09:18,160
Ang isang function prototype, o
deklarasyon para sa na function,

179
00:09:18,160 --> 00:09:23,320
maaaring magmukhang this-- bool mahanap, at
pagkatapos ay nais naming ipasa sa dalawang argumento.

180
00:09:23,320 --> 00:09:26,996
>> Ang una, ay isang pointer sa
unang elemento ng naka-link na listahan.

181
00:09:26,996 --> 00:09:29,620
Ito ay talagang isang bagay na makikita mo
laging nais na subaybayan,

182
00:09:29,620 --> 00:09:33,110
at ang tunay na maaaring maging isang bagay na
mong kahit na ilagay sa isang global variable.

183
00:09:33,110 --> 00:09:35,360
Sa sandaling lumikha ka ng listahan,
palagi kang, palaging

184
00:09:35,360 --> 00:09:38,990
nais na subaybayan ang mga tunay
unang elemento ng listahan.

185
00:09:38,990 --> 00:09:43,690
Sa ganoong paraan maaari kang sumangguni sa lahat ng iba pang
elemento sa pamamagitan ng mga sumusunod na lamang ang kadena,

186
00:09:43,690 --> 00:09:47,300
nang hindi na kinakailangang upang panatilihin ang mga payo
buo sa bawat solong elemento.

187
00:09:47,300 --> 00:09:50,920
Kailangan mo lamang na subaybayan ang mga unang
isa kung ang lahat ng mga ito ay chained magkasama.

188
00:09:50,920 --> 00:09:52,460
>> At pagkatapos ay ang ikalawang bagay
kami ay pagpasa sa muli

189
00:09:52,460 --> 00:09:54,376
ay nagkataon some--
kahit anong uri ng data hindi namin

190
00:09:54,376 --> 00:09:59,640
naghahanap para sa may loob ng
sana isa sa mga node sa listahan.

191
00:09:59,640 --> 00:10:00,980
Kaya ano ang mga hakbang na ito?

192
00:10:00,980 --> 00:10:04,250
Well, ang unang bagay na ginagawa namin ay
lumikha kami ng isang transversal pointer

193
00:10:04,250 --> 00:10:06,015
nakaturo sa mga listahan ng ulo.

194
00:10:06,015 --> 00:10:08,890
Well, bakit ginagawa namin na, kami ay
magkaroon ng isang pointer sa listahan ulo,

195
00:10:08,890 --> 00:10:10,974
bakit hindi lamang ilipat namin ang isa na sa paligid?

196
00:10:10,974 --> 00:10:13,140
Well, tulad ng sinabi ko,
ito ay talagang mahalaga para sa amin

197
00:10:13,140 --> 00:10:17,580
na laging subaybayan ang
pinakaunang elemento sa listahan.

198
00:10:17,580 --> 00:10:21,270
At kaya ito ay aktwal na mas mahusay na
upang lumikha ng isang dobleng ng iyon,

199
00:10:21,270 --> 00:10:25,350
at gamitin iyon upang gumalaw sa paligid kaya hindi namin
sinasadyang ilipat ang layo, o kami ay palaging

200
00:10:25,350 --> 00:10:30,430
magkaroon ng isang pointer sa ilang mga punto na
karapatan sa unang elemento ng listahan.

201
00:10:30,430 --> 00:10:33,290
Kaya ito ay mas mahusay na upang lumikha ng isang
pangalawang isa na ginagamit namin upang ilipat.

202
00:10:33,290 --> 00:10:35,877
>> Pagkatapos ay ihambing lang namin kung
ang halaga ng field sa na node

203
00:10:35,877 --> 00:10:38,960
ay kung ano ang aming hinahanap, at kung ito ay
hindi, lamang ilipat namin sa susunod na node.

204
00:10:38,960 --> 00:10:41,040
At patuloy na namin ang paggawa na
loob, at higit, at higit,

205
00:10:41,040 --> 00:10:44,811
hanggang namin mahanap ang alinman sa
ang elemento, o pindutin namin

206
00:10:44,811 --> 00:10:47,310
null-- naabot na namin ang dulo
ng listahan at ito ay hindi doon.

207
00:10:47,310 --> 00:10:50,540
Ito ay dapat sana ng singsing na kampanilya
sa iyo bilang lang linear paghahanap,

208
00:10:50,540 --> 00:10:54,430
lang kami Kinokopya ang mga ito sa
isang isa-isa na naka-link structure listahan

209
00:10:54,430 --> 00:10:56,280
sa halip ng paggamit ng isang hanay upang gawin ito.

210
00:10:56,280 --> 00:10:58,210
>> Kaya narito ang isang halimbawa ng
isang isa-isa naka-link na listahan.

211
00:10:58,210 --> 00:11:00,043
Isa na ito ay binubuo ng
limang nodes, at kami ay

212
00:11:00,043 --> 00:11:04,330
isang pointer sa pinuno ng
listahan, na kung saan ay tinatawag na listahan.

213
00:11:04,330 --> 00:11:07,385
Ang unang bagay na gusto naming gawin ay
muli, lumikha na traversal pointer.

214
00:11:07,385 --> 00:11:09,760
Kaya tayo ngayon ay dalawang payo
sa puntong iyon sa parehong bagay.

215
00:11:09,760 --> 00:11:15,025
>> Ngayon, mapapansin din dito, ako ay hindi
kung malloc anumang puwang para trav.

216
00:11:15,025 --> 00:11:18,970
Hindi ko sabihin trav katumbas malloc
ang isang bagay, mayroon na node,

217
00:11:18,970 --> 00:11:21,160
na espasyo sa memory ay mayroon na.

218
00:11:21,160 --> 00:11:24,290
Kaya lahat talaga ako ng paggawa ay
paglikha ng isa pang pointer sa mga ito.

219
00:11:24,290 --> 00:11:28,210
Hindi ko mallocing isang karagdagang
space, mayroon na lamang ngayon ng dalawang mga payo

220
00:11:28,210 --> 00:11:31,370
na tumuturo sa parehong bagay.

221
00:11:31,370 --> 00:11:33,710
>> Kaya ay 2 ano Naghahanap ako para sa?

222
00:11:33,710 --> 00:11:37,220
Well, hindi, kaya sa halip na Ako
pagpunta upang lumipat sa susunod na isa.

223
00:11:37,220 --> 00:11:41,740
Kaya talaga sasabihin ko,
trav katumbas trav susunod.

224
00:11:41,740 --> 00:11:43,630
Ay 3 ano Naghahanap ako, hindi.

225
00:11:43,630 --> 00:11:45,780
Kaya patuloy kong pumunta
pamamagitan, hanggang sa huli

226
00:11:45,780 --> 00:11:48,690
makakuha ng hanggang 6 na kung saan ay kung ano Naghahanap ako
para sa batay sa function ng tawag

227
00:11:48,690 --> 00:11:51,600
Mayroon akong sa tuktok
doon, at kaya ako tapos na.

228
00:11:51,600 --> 00:11:54,150
>> Ngayon, paano kung ang element Ako
hinahanap ay wala sa listahan,

229
00:11:54,150 --> 00:11:55,510
Pupunta pa rin ito sa trabaho?

230
00:11:55,510 --> 00:11:57,120
Well, mapapansin na ang listahan
dito ay subtly naiiba,

231
00:11:57,120 --> 00:11:59,410
at ito ay isa pang bagay na
mahalaga na may naka-link na mga listahan,

232
00:11:59,410 --> 00:12:01,780
hindi mo na kailangang upang mapanatili
ang mga ito sa anumang partikular na order.

233
00:12:01,780 --> 00:12:05,390
Maaari mo kung nais mo, ngunit
maaaring mayroon ka napansin

234
00:12:05,390 --> 00:12:09,310
na hindi kami ay nag-iingat ng track ng
ano ang bilang element na tayo sa.

235
00:12:09,310 --> 00:12:13,150
>> At iyon ay uri ng isa sa kalakalan na tayo
Mayroon na may listahan ng mga link talatang array,

236
00:12:13,150 --> 00:12:15,300
ay ito wala tayong
random access anymore.

237
00:12:15,300 --> 00:12:18,150
Hindi lamang namin maaaring sabihin, gusto ko
upang pumunta sa 0 element,

238
00:12:18,150 --> 00:12:21,410
o ika-6 na elemento ng aking array,
kung saan ang maaari kong gawin sa isang array.

239
00:12:21,410 --> 00:12:25,080
Hindi ko masabi na gusto kong pumunta sa
0 element, o ika-6 na elemento,

240
00:12:25,080 --> 00:12:30,360
o ang ika-25 na sangkap ng aking listahan na naka-link,
walang index kaugnay sa kanila.

241
00:12:30,360 --> 00:12:33,660
At kaya ito ay hindi tunay bagay
kung namin panatilihin ang aming listahan sa order.

242
00:12:33,660 --> 00:12:36,080
Kung nais mong iyo
ay tiyak na makakaya, ngunit mayroong

243
00:12:36,080 --> 00:12:38,567
walang dahilan kung bakit kailangan nila upang
hindi mapangalagaan sa anumang pagkakasunud-sunod.

244
00:12:38,567 --> 00:12:40,400
Kaya muli, sabihin subukan at
hanapin 6 sa listahan na ito.

245
00:12:40,400 --> 00:12:43,200
Well, kami ay magsisimula sa
simula, hindi namin mahanap ang 6,

246
00:12:43,200 --> 00:12:47,690
at pagkatapos ay hindi namin magpatuloy sa paghahanap
6, hanggang sa huli kami makarating sa dito.

247
00:12:47,690 --> 00:12:52,790
Kaya karapatan trav ngayon points sa node
na naglalaman ng 8, at anim na ito ay hindi sa doon.

248
00:12:52,790 --> 00:12:55,250
>> Kaya ang susunod na hakbang ay
upang pumunta sa susunod na pointer,

249
00:12:55,250 --> 00:12:57,440
kaya sabihin trav katumbas trav susunod.

250
00:12:57,440 --> 00:13:00,750
Well, trav susunod, na ipinapahiwatig ng
ang pulang kahon doon, ay null.

251
00:13:00,750 --> 00:13:03,020
Kaya may ibang tao na wala sa
pumunta, at kaya sa puntong ito

252
00:13:03,020 --> 00:13:06,120
maaari naming tapusin na naabot na namin ang
sa dulo ng listahan ng mga link,

253
00:13:06,120 --> 00:13:07,190
at 6 ay hindi sa doon.

254
00:13:07,190 --> 00:13:10,980
At ito ay ibabalik
false sa kasong ito.

255
00:13:10,980 --> 00:13:14,540
>> OK, paano ipasok namin ang isang bagong
node sa listahan ng mga link?

256
00:13:14,540 --> 00:13:17,310
Kaya nagawa naming upang lumikha ng
isang listahan ng mga link sa labas ng wala,

257
00:13:17,310 --> 00:13:19,370
ngunit malamang na gusto naming
bumuo ng isang hanay at hindi

258
00:13:19,370 --> 00:13:22,620
lumikha ng isang grupo ng mga natatanging mga listahan.

259
00:13:22,620 --> 00:13:25,700
Gusto naming magkaroon ng isang listahan na
ay may isang bungkos ng mga node sa loob nito,

260
00:13:25,700 --> 00:13:28,040
hindi isang grupo ng mga listahan na may isang solong node.

261
00:13:28,040 --> 00:13:31,260
Kaya hindi lamang namin ay maaaring panatilihin ang paggamit ng Lumikha
function na tinukoy ng mas maaga kami, ngayon kami

262
00:13:31,260 --> 00:13:33,860
nais na ipasok sa isang
list na mayroon na.

263
00:13:33,860 --> 00:13:36,499
>> Kaya kasong ito, kami ay pagpunta
upang pumasa sa dalawang argumento,

264
00:13:36,499 --> 00:13:39,290
ang pointer sa pinuno ng na
listahan ng mga link na gusto naming idagdag sa.

265
00:13:39,290 --> 00:13:40,910
Muli, na ang dahilan kung bakit ito ay kaya
Mahalaga na tayo ay palaging

266
00:13:40,910 --> 00:13:43,400
subaybayan ang mga ito, dahil
ito ay ang tanging paraan na kami ay talagang

267
00:13:43,400 --> 00:13:46,690
kung sumangguni sa buong listahan ay
sa pamamagitan lamang ng isang pointer sa unang elemento.

268
00:13:46,690 --> 00:13:49,360
Kaya gusto namin upang pumasa sa isang
pointer sa na unang elemento,

269
00:13:49,360 --> 00:13:52,226
at kahit anong halaga natin
nais na idagdag sa listahan.

270
00:13:52,226 --> 00:13:54,600
At sa huli ang function na ito
ay pagpunta upang magbalik ng pointer

271
00:13:54,600 --> 00:13:57,980
na ang bagong pinuno ng isang naka-link na listahan.

272
00:13:57,980 --> 00:13:59,700
>> Ano ang mga hakbang na kasangkot dito?

273
00:13:59,700 --> 00:14:02,249
Well, tulad ng sa lumikha,
kailangan namin upang magilas na magtalaga

274
00:14:02,249 --> 00:14:05,540
space para sa isang bagong node, at suriin upang
matiyak na hindi kami maubusan ng memory, muli,

275
00:14:05,540 --> 00:14:07,150
dahil kami ay gumagamit ng malloc.

276
00:14:07,150 --> 00:14:09,080
Pagkatapos na nais naming i-populate
at ipasok ang node,

277
00:14:09,080 --> 00:14:12,730
kaya ilagay ang numero, kahit na ano
Val ay, sa node.

278
00:14:12,730 --> 00:14:17,310
Gusto naming ipasok ang node sa
simula ng naka-link na listahan.

279
00:14:17,310 --> 00:14:19,619
>> May dahilan na ako
gusto mong gawin ito, at ito

280
00:14:19,619 --> 00:14:21,910
maaaring karapat-dapat sa pagkuha ng isang pangalawang
upang i-pause ang video dito,

281
00:14:21,910 --> 00:14:25,860
at sa tingin tungkol sa kung bakit Gusto ko nais na
ipasok sa simula ng isang naka-link

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

283
00:14:26,589 --> 00:14:28,630
Muli, nabanggit ko mas maaga
na ito ay hindi tunay

284
00:14:28,630 --> 00:14:33,020
mahalaga kung namin panatilihin ang mga ito sa anumang
order, kaya marahil na isang palatandaan.

285
00:14:33,020 --> 00:14:36,040
At nakita mo kung ano ang mangyayari kung namin
Nais to-- o mula sa isang segundo lamang

286
00:14:36,040 --> 00:14:37,360
nakalipas kapag kami ay pagpunta
sa pamamagitan ng paghahanap sa iyo

287
00:14:37,360 --> 00:14:39,235
maaaring makita kung ano ang maaaring
mangyayari kung kami ay nagsisikap

288
00:14:39,235 --> 00:14:41,330
upang magsingit ng sa dulo ng listahan.

289
00:14:41,330 --> 00:14:44,750
Dahil hindi namin ay may isang
pointer sa dulo ng listahan.

290
00:14:44,750 --> 00:14:47,490
>> Kaya ang dahilan na gusto ko gusto
upang ipasok sa simula,

291
00:14:47,490 --> 00:14:49,380
ay dahil ang maaari kong gawin ito kaagad.

292
00:14:49,380 --> 00:14:52,730
Mayroon akong isang pointer sa simula, at
kami ay makita ito sa isang visual na sa isang segundo.

293
00:14:52,730 --> 00:14:55,605
Ngunit kung gusto kong ipasok sa dulo,
Kailangan ko bang magsimula sa simula,

294
00:14:55,605 --> 00:14:58,760
tawirin ang lahat ng mga paraan upang ang
end, at pagkatapos ay tak ito sa.

295
00:14:58,760 --> 00:15:01,420
Kaya na ay nangangahulugan na
pagpasok sa dulo ng listahan

296
00:15:01,420 --> 00:15:04,140
ay maging isang o ng n
operasyon, balik

297
00:15:04,140 --> 00:15:06,720
sa aming mga talakayan ng
computational kumplikado.

298
00:15:06,720 --> 00:15:10,140
Gusto itong maging isang o ng n operasyon, na kung saan ang
bilang ang listahan nakuha ng mas malaki, at mas malaki,

299
00:15:10,140 --> 00:15:13,310
at mas malaki, makikita ito maging mas at
mas mahirap sa tak bagay

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

301
00:15:14,661 --> 00:15:17,410
Ngunit ito ay palaging tunay madali sa
tak ng isang bagay sa sa simula,

302
00:15:17,410 --> 00:15:19,060
ikaw ay palaging sa simula.

303
00:15:19,060 --> 00:15:21,620
>> At kami na makita ang isang visual ng mga ito muli.

304
00:15:21,620 --> 00:15:24,100
At pagkatapos ay sa sandaling tapos na kami, sa sandaling
nakapasok na namin ang bagong node,

305
00:15:24,100 --> 00:15:26,880
gusto naming ibalik ang aming pointer sa
ang bagong ulo ng isang listahan ng mga link, na kung saan

306
00:15:26,880 --> 00:15:29,213
dahil kami ay pagpasok sa
simula, ay tunay na maging

307
00:15:29,213 --> 00:15:31,060
isang pointer sa node na nilikha namin lamang.

308
00:15:31,060 --> 00:15:33,280
Ni maisalarawan na ito,
dahil sa tingin ko na ito ay tumulong.

309
00:15:33,280 --> 00:15:36,661
>> Kaya narito ang aming listahan, ito ay binubuo ng
apat na mga sangkap, ang isang node na naglalaman ng 15,

310
00:15:36,661 --> 00:15:38,410
na puntos sa isang node
na naglalaman ng 9, na

311
00:15:38,410 --> 00:15:41,370
puntos sa isang node na naglalaman ng 13,
na puntos sa isang node na naglalaman ng

312
00:15:41,370 --> 00:15:44,840
10, na kung saan ay may mga null
pointer bilang kanyang susunod na pointer

313
00:15:44,840 --> 00:15:47,010
kaya iyon ang katapusan ng listahan.

314
00:15:47,010 --> 00:15:50,200
Kaya gusto namin upang magsingit ng isang
bagong node sa halaga 12

315
00:15:50,200 --> 00:15:52,720
sa simula ng ito
list, ano ang gagawin namin?

316
00:15:52,720 --> 00:15:58,770
Well, unang-malloc namin na puwang para sa
node, at pagkatapos ay inilalagay namin 12 sa doon.

317
00:15:58,770 --> 00:16:02,211
>> Kaya ngayon naabot na namin ang isang
desisyon point, right?

318
00:16:02,211 --> 00:16:03,960
Kami ay may isang pares ng mga
mga payo na maaaring namin

319
00:16:03,960 --> 00:16:06,770
ilipat, kung saan ang isa ay dapat munang ilipat namin?

320
00:16:06,770 --> 00:16:09,250
Dapat gawin namin ang 12 point sa
ang bagong ulo ng list--

321
00:16:09,250 --> 00:16:13,020
o excuse me, dapat naming gumawa ng 12
point sa lumang ulo ng listahan?

322
00:16:13,020 --> 00:16:15,319
O kaya dapat naming sabihin na ang
list na ngayon ay nagsisimula sa 12.

323
00:16:15,319 --> 00:16:17,110
Mayroong isang pagkakaiba
doon, at kami ay tumingin

324
00:16:17,110 --> 00:16:19,870
sa kung ano ang mangyayari sa parehong sa isang segundo.

325
00:16:19,870 --> 00:16:23,350
>> Ngunit ito ay humahantong sa isang
mahusay na paksa para sa sidebar,

326
00:16:23,350 --> 00:16:26,280
na kung saan ay na ang isa sa mga
trickiest bagay na may mga listahan ng link

327
00:16:26,280 --> 00:16:30,980
ay upang ayusin ang mga payo
sa tamang pagkakasunod-sunod.

328
00:16:30,980 --> 00:16:34,520
Kung ililipat mo ang mga bagay-bagay sa labas ng order,
maaari mong tapusin up sinasadyang

329
00:16:34,520 --> 00:16:36,050
orphaning ang natitirang bahagi ng listahan.

330
00:16:36,050 --> 00:16:37,300
At narito ang isang halimbawa ng na.

331
00:16:37,300 --> 00:16:40,540
Kaya sabihin pumunta sa mga ideya of--
well, ako lamang nilikha namin 12.

332
00:16:40,540 --> 00:16:43,180
Alam namin 12 ay magiging
ang bagong ulo ng listahan,

333
00:16:43,180 --> 00:16:47,660
at sa gayon bakit hindi ilipat namin lamang
listahan pointer upang tumuro doon.

334
00:16:47,660 --> 00:16:49,070
>> OK, sa gayon ay maganda.

335
00:16:49,070 --> 00:16:51,560
Kaya ngayon kung saan ay 12 susunod point?

336
00:16:51,560 --> 00:16:54,580
Ibig kong sabihin, biswal maaari naming makita
na ito ay tumuturo sa 15,

337
00:16:54,580 --> 00:16:57,250
bilang mga tao na ito ay talagang halata sa amin.

338
00:16:57,250 --> 00:17:00,300
Paano nalalaman ng computer?

339
00:17:00,300 --> 00:17:02,720
Wala kaming anumang bagay
tumuturo sa 15 anymore, right?

340
00:17:02,720 --> 00:17:05,869
>> Nawala namin ang anumang kakayahan na mag-refer sa 15.

341
00:17:05,869 --> 00:17:11,460
Hindi namin sinasabi bagong arrow sa tabi equals
isang bagay, walang may.

342
00:17:11,460 --> 00:17:13,510
Sa katunayan, na naulila namin
ang natitirang bahagi ng listahan

343
00:17:13,510 --> 00:17:16,465
sa pamamagitan ng paggawa nito, na namin
sinasadyang nasira ang kadena.

344
00:17:16,465 --> 00:17:18,089
At kami ay tiyak na hindi mo nais na gawin iyon.

345
00:17:18,089 --> 00:17:20,000
>> Kaya sabihin bumalik at subukan muli.

346
00:17:20,000 --> 00:17:24,060
Siguro ang tamang gawin
ay mag-set ng 12 ni susunod na pointer

347
00:17:24,060 --> 00:17:28,290
sa lumang ulo ng listahan ng una,
pagkatapos ay maaari naming ilipat ang mga listahan ng higit.

348
00:17:28,290 --> 00:17:30,420
At sa katunayan, iyon ay ang
tamang pagkakasunod-sunod na tayo

349
00:17:30,420 --> 00:17:32,836
kailangang sundin kung hindi namin
nagtatrabaho sa isa-isa na naka-link na listahan.

350
00:17:32,836 --> 00:17:36,460
Lagi kaming nais na ikonekta ang mga
bagong elemento sa listahan,

351
00:17:36,460 --> 00:17:41,010
bago kami gumawa ng na uri ng
mahalagang hakbang ng pagbabago

352
00:17:41,010 --> 00:17:43,360
kung saan ang ulo ng listahan ng mga link ay.

353
00:17:43,360 --> 00:17:46,740
Muli, na tulad ng isang pangunahing bagay,
Hindi namin nais na mawala sa pagsubaybay ng mga ito.

354
00:17:46,740 --> 00:17:49,310
>> Kaya gusto naming siguraduhin na ang
lahat ng bagay ay chained magkasama,

355
00:17:49,310 --> 00:17:52,040
bago namin ilipat na pointer.

356
00:17:52,040 --> 00:17:55,300
At kaya ito ay ang tamang pagkakasunod-sunod,
na kung saan ay upang ikonekta ang 12 sa listahan,

357
00:17:55,300 --> 00:17:57,630
pagkatapos ay sabihin na ang listahan ay nagsisimula sa isang 12.

358
00:17:57,630 --> 00:18:00,860
Kung namin sinabi ang listahan ay nagsisimula sa 12 at
pagkatapos ay sinubukan upang kumonekta 12 sa listahan,

359
00:18:00,860 --> 00:18:02,193
na namin nakita kung ano ang mangyayari.

360
00:18:02,193 --> 00:18:04,920
Nawala namin ang listahan sa pamamagitan ng pagkakamali.

361
00:18:04,920 --> 00:18:06,740
>> OK, kaya ang isa pang bagay na makipag-usap tungkol sa.

362
00:18:06,740 --> 00:18:09,750
Paano kung gusto namin upang magtanggal ng
isang buong listahan ng mga link sa isang beses?

363
00:18:09,750 --> 00:18:11,750
Muli, kami ay mallocing
lahat ng puwang na ito, at kaya namin

364
00:18:11,750 --> 00:18:13,351
kailangan upang magbakante ito kapag tapos na kami.

365
00:18:13,351 --> 00:18:15,350
Kaya ngayon gusto naming tanggalin
ang buong listahan ng mga link.

366
00:18:15,350 --> 00:18:16,850
Well, ano ang gusto naming gawin?

367
00:18:16,850 --> 00:18:20,460
>> Kung naabot na namin ang null pointer, namin
gusto mong itigil, kung hindi man, tanggalin lamang

368
00:18:20,460 --> 00:18:23,420
ang natitirang bahagi ng listahan at pagkatapos ay libre ako.

369
00:18:23,420 --> 00:18:28,890
Burahin ang natitirang bahagi ng listahan,
at pagkatapos ay libre ang kasalukuyang node.

370
00:18:28,890 --> 00:18:32,850
Ano ang ibig sabihin na ang tunog tulad ng,
kung ano ang pamamaraan ay may usapan natin

371
00:18:32,850 --> 00:18:35,440
tungkol sa dati na ang tunog tulad ng?

372
00:18:35,440 --> 00:18:39,560
Tanggalin ang lahat ng iba pa, at pagkatapos ay
bumalik at tanggalin sa akin.

373
00:18:39,560 --> 00:18:42,380
>> Iyan ay recursion, ginawa naming ang
problema ng isang maliit na piraso ng mas maliit,

374
00:18:42,380 --> 00:18:46,910
namin sinasabi tanggalin ang lahat ng tao
iba pa, pagkatapos ay maaari mong tanggalin sa akin.

375
00:18:46,910 --> 00:18:50,940
At mas ibaba pa ng kalsada, na node
sasabihin ng iba, tanggalin lahat ng iba pa.

376
00:18:50,940 --> 00:18:53,940
Ngunit sa huli babalikan ka namin sa
punto kung saan ang listahan ay null,

377
00:18:53,940 --> 00:18:55,310
at iyon ang aming base kaso.

378
00:18:55,310 --> 00:18:57,010
>> Kaya sabihin kumuha ng isang pagtingin sa ito,
at kung paano ito maaaring gumana.

379
00:18:57,010 --> 00:18:59,759
Kaya narito ang aming listahan, ito ay ang parehong
listahan namin ay pakikipag-usap lamang tungkol sa,

380
00:18:59,759 --> 00:19:00,980
at mayroong mga hakbang.

381
00:19:00,980 --> 00:19:04,200
May isang pulutong ng mga teksto dito, ngunit
inaasahan namin na ang visualization ay makakatulong.

382
00:19:04,200 --> 00:19:08,557
>> Kaya have-- kami at hinila ko rin
up aming stack frame na paglalarawan

383
00:19:08,557 --> 00:19:10,890
mula sa aming mga video sa mga stack ng tawag,
at sana ang lahat ng ito

384
00:19:10,890 --> 00:19:13,260
magkasama ay magpapakita sa iyo kung ano ang nangyayari sa.

385
00:19:13,260 --> 00:19:14,510
Kaya narito ang aming pseudocode code.

386
00:19:14,510 --> 00:19:17,830
Kung naabot namin ang isang null
pointer, stop, sa kabilang banda,

387
00:19:17,830 --> 00:19:21,320
tanggalin ang natitirang bahagi ng listahan,
pagkatapos ay libre ang kasalukuyang node.

388
00:19:21,320 --> 00:19:25,700
Kaya ngayon, list--
ang pointer na hindi namin

389
00:19:25,700 --> 00:19:28,410
pagpasa sa upang sirain ang mga puntos sa 12.

390
00:19:28,410 --> 00:19:33,340
12 ay hindi isang null pointer, kaya kami ay
pagpunta sa tanggalin ang natitirang bahagi ng listahan.

391
00:19:33,340 --> 00:19:35,450
>> Ano ang pagtanggal ng mga
iba sa atin na kasangkot?

392
00:19:35,450 --> 00:19:37,950
Well, ito ay nangangahulugan ng paggawa ng isang
tumawag upang sirain, na sinasabi

393
00:19:37,950 --> 00:19:42,060
na ang 15 ay ang simula ng
natitirang bahagi ng listahan na gusto namin upang sirain.

394
00:19:42,060 --> 00:19:47,480
At upang ang mga tawag upang sirain
12 ay uri ng on hold.

395
00:19:47,480 --> 00:19:52,690
Ito ay frozen doon, naghihintay para sa mga
tumawag upang sirain 15, upang tapusin ang kanyang trabaho.

396
00:19:52,690 --> 00:19:56,280
>> Well, 15 ay hindi isang null pointer, at
kaya ito ay pagpunta sa sabihin, lahat ng karapatan,

397
00:19:56,280 --> 00:19:58,450
, tanggalin muna ang natitirang bahagi ng listahan.

398
00:19:58,450 --> 00:20:00,760
Ang natitirang bahagi ng listahan nagsisimula
sa 9, at iba idedetalye namin lamang

399
00:20:00,760 --> 00:20:04,514
maghintay hanggang sa tanggalin mo ang lahat na
mga bagay-bagay, at pagkatapos ay bumalik at tanggalin sa akin.

400
00:20:04,514 --> 00:20:06,680
Well 9 ay pagpunta sa sabihin, well,
Hindi ako isang null pointer,

401
00:20:06,680 --> 00:20:09,020
kaya tanggalin ang mga natitirang ang listahan mula dito.

402
00:20:09,020 --> 00:20:11,805
At kaya subukan at sirain 13.

403
00:20:11,805 --> 00:20:15,550
13 sabi, hindi ako null pointer,
parehong bagay, ito pumasa sa usang lalaki.

404
00:20:15,550 --> 00:20:17,930
10 ay hindi null pointer, 10
naglalaman ng isang null pointer,

405
00:20:17,930 --> 00:20:20,200
ngunit 10 ay hindi mismo ng
null pointer sa ngayon,

406
00:20:20,200 --> 00:20:22,470
at kaya ito pumasa sa usang lalaki masyadong.

407
00:20:22,470 --> 00:20:25,560
>> At ngayon ilista points doon, ito
talagang ay tumuturo sa some--

408
00:20:25,560 --> 00:20:28,710
kung ako ay mas maraming espasyo sa imahe,
ito ay tumuturo sa ilang mga random na space

409
00:20:28,710 --> 00:20:29,960
na hindi namin alam kung ano ito.

410
00:20:29,960 --> 00:20:34,680
Ito ay ang null pointer bagaman, ang listahan
Literal na ngayong itakda ito ay mga halaga null.

411
00:20:34,680 --> 00:20:36,820
Ito ay tumuturo sa loob mismo na red box.

412
00:20:36,820 --> 00:20:39,960
Naabot namin ang isang null pointer, kaya
maaari naming ihinto, at tapos na kami.

413
00:20:39,960 --> 00:20:46,230
>> At upang ang purple frame ay now-- sa
tuktok ng stack-- iyon ang aktibong frame,

414
00:20:46,230 --> 00:20:47,017
ngunit ito ay tapos na.

415
00:20:47,017 --> 00:20:48,600
Kung naabot na namin ang isang null pointer, itigil.

416
00:20:48,600 --> 00:20:51,290
Hindi namin gumawa ng anumang bagay, kami
hindi maaaring magbakante ng isang null pointer,

417
00:20:51,290 --> 00:20:55,070
hindi namin ginawa malloc anumang
space, at sa gayon kami ay tapos na.

418
00:20:55,070 --> 00:20:57,590
Kaya na function na frame
ay nasira, at tayo

419
00:20:57,590 --> 00:21:00,930
resume-- pick up namin kung saan kami iniwan
off sa susunod na pinakamataas na isa, na

420
00:21:00,930 --> 00:21:02,807
ay ang madilim na asul na frame dito.

421
00:21:02,807 --> 00:21:04,390
Kaya namin kukunin ang karapatan kung saan namin kaliwa off.

422
00:21:04,390 --> 00:21:06,598
Tinanggal namin ang natitirang bahagi ng
list na, kaya ngayon kami ay

423
00:21:06,598 --> 00:21:08,000
pagpunta sa magbakante ang kasalukuyang nodes.

424
00:21:08,000 --> 00:21:12,920
Kaya ngayon maaari naming magbakante ito node, at ngayon
naabot na namin ang dulo ng function.

425
00:21:12,920 --> 00:21:16,810
At upang ang mga function na frame ay pupuksain,
at kunin natin ang isa mapusyaw na asul.

426
00:21:16,810 --> 00:21:20,650
>> Kaya ito ako says-- na ako na done--
tinatanggal ang natitirang bahagi ng listahan, kaya

427
00:21:20,650 --> 00:21:23,140
libre ang kasalukuyang node.

428
00:21:23,140 --> 00:21:26,520
At ngayon, ang dilaw na frame ay
bumalik sa tuktok ng stack.

429
00:21:26,520 --> 00:21:29,655
At kaya tulad ng nakikita mo, hindi namin ngayon
pagsira sa mga listahan mula sa karapatan sa kaliwa.

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

431
00:21:33,710 --> 00:21:37,280
>> Ano kaya ang nangyari, bagaman,
kung kami ay tapos na bagay sa maling paraan?

432
00:21:37,280 --> 00:21:39,410
Katulad ng kapag sinubukan naming
upang magdagdag ng isang elemento.

433
00:21:39,410 --> 00:21:41,909
Kung messed up namin ang kadena, kung
hindi namin ay ikonekta ang mga payo

434
00:21:41,909 --> 00:21:44,690
sa tamang pagkakasunod-sunod, kung tayo
napalaya lang ang unang elemento,

435
00:21:44,690 --> 00:21:47,420
kung napalaya lang namin ang
ulo ng listahan, ngayon kami

436
00:21:47,420 --> 00:21:49,642
ay walang paraan upang tumukoy sa
ang natitirang bahagi ng listahan.

437
00:21:49,642 --> 00:21:51,350
At kaya kami ay may
naulila lahat ng bagay,

438
00:21:51,350 --> 00:21:53,880
Gusto namin ay may kung ano ang
tinatawag na isang memory tumagas.

439
00:21:53,880 --> 00:21:56,800
Kung isipin ang mo mula sa aming mga video
sa dynamic memory laang-gugulin,

440
00:21:56,800 --> 00:21:58,650
na hindi masyadong magandang bagay.

441
00:21:58,650 --> 00:22:00,810
>> Kaya tulad ng sinabi ko, may
ilang mga operasyon

442
00:22:00,810 --> 00:22:04,010
na kailangan namin upang gamitin sa trabaho
may listahan na naka-link nang epektibo.

443
00:22:04,010 --> 00:22:08,430
At maaari mong napansin na tinanggal ko ang isa,
pagtanggal ng isang solong elemento mula sa isang naka-link

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

445
00:22:09,064 --> 00:22:10,980
Ang dahilan ko na
ay ito ay aktwal na uri ng

446
00:22:10,980 --> 00:22:14,360
nakakalito na mag-isip tungkol sa kung paano tanggalin ang
isang solong elemento mula sa isang isa-isa

447
00:22:14,360 --> 00:22:15,600
naka-link na listahan.

448
00:22:15,600 --> 00:22:19,950
Kailangan namin upang ma-laktawan ang higit
isang bagay sa listahan, na

449
00:22:19,950 --> 00:22:22,975
nangangahulugan makuha namin sa isang point-- namin
nais na tanggalin ito node--

450
00:22:22,975 --> 00:22:25,350
ngunit upang gawin ito upang tayo
huwag mawalan ng anumang impormasyon,

451
00:22:25,350 --> 00:22:30,530
kailangan namin upang ikonekta ito
node sa paglipas dito, dito.

452
00:22:30,530 --> 00:22:33,390
>> Kaya marahil ginawa ko na mali
mula sa isang visual na pananaw.

453
00:22:33,390 --> 00:22:36,830
Kaya hindi namin sa simula ng aming
listahan, kami ay magpatuloy sa pamamagitan ng,

454
00:22:36,830 --> 00:22:40,510
gusto naming tanggalin ito node.

455
00:22:40,510 --> 00:22:43,440
Kung tatanggalin namin ito lamang,
nasira na namin ang kadena.

456
00:22:43,440 --> 00:22:45,950
Node Ito karapatan dito
ay tumutukoy sa lahat ng iba pa,

457
00:22:45,950 --> 00:22:48,260
naglalaman ito ng mga kadena mula dito sa labas.

458
00:22:48,260 --> 00:22:51,190
>> Kaya kung ano ang kailangan namin upang gawin ang tunay na
pagkatapos naming makarating sa puntong ito,

459
00:22:51,190 --> 00:22:56,670
ay kailangan namin sa hakbang likod ng isa, at
ikonekta ito node sa ibabaw sa node na ito,

460
00:22:56,670 --> 00:22:58,590
upang maaari naming pagkatapos ay tanggalin
ang isa sa gitna.

461
00:22:58,590 --> 00:23:02,120
Ngunit isa-isa mga listahan ng link ay hindi
ay nagbibigay sa amin ng isang paraan upang pumunta paurong.

462
00:23:02,120 --> 00:23:05,160
Kaya kailangan namin upang panatilihin ang alinman sa
dalawang payo, at ilipat ang mga ito

463
00:23:05,160 --> 00:23:09,527
uri ng off-hakbang, isa sa likod ng
iba pang mga bilang pumunta kami, o makakuha ng sa isang punto

464
00:23:09,527 --> 00:23:11,110
at pagkatapos ay magpadala ng isa pang pointer sa pamamagitan ng.

465
00:23:11,110 --> 00:23:13,150
At bilang maaari mong makita, ito
ay maaaring makakuha ng isang maliit na makalat.

466
00:23:13,150 --> 00:23:15,360
Sa kabutihang palad, kami ay
isa pang paraan upang malutas na,

467
00:23:15,360 --> 00:23:17,810
kapag kami makipag-usap tungkol sa mga doble-link list.

468
00:23:17,810 --> 00:23:20,720
>> Ako Doug Lloyd, ito ay CS50.

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