>> [Music kucheza]
>> DOUG LLOYD: Sawa, hivyo katika hatua hii ya shaka,
tumekuwa kufunikwa mengi ya mambo ya msingi ya C. Tunajua mengi kuhusu vigezo, arrays,
kuyatumia, mambo ambayo yote mazuri.
Wale wote ni aina ya kujengwa katika kuona kama misingi,
lakini tunaweza kufanya zaidi, sawa?
Tunaweza kuchanganya mambo pamoja kwa njia ya kuvutia.
>> Na hivyo hebu kufanya hivyo, hebu kuanza tawi nje ya kile C inatupa,
na kuanza kujenga takwimu zetu wenyewe miundo kutumia jengo hizi
vitalu pamoja ili kufanya kitu kweli thamani, manufaa.
Njia moja tunaweza kufanya hivyo ni kuzungumzia makusanyo.
Hivyo hadi sasa tulikuwa na aina moja ya data muundo wa anayewakilisha makusanyo
ya kama maadili, maadili hayo.
Hiyo itakuwa safu.
Tuna makusanyo ya integers, au makusanyo ya wahusika na kadhalika.
>> Miundo pia aina ya data muundo wa kukusanya taarifa,
lakini siyo kwa ajili ya kukusanya kama maadili.
Ni kawaida huchanganyika aina mbalimbali data pamoja ndani ya sanduku moja.
Lakini siyo yenyewe kutumika mlolongo pamoja
au kuungana pamoja kama vitu, kama safu.
Arrays ni kubwa kwa kipengele kuangalia juu, lakini wanakumbuka
kwamba ni vigumu sana kuingiza ndani ya safu,
isipokuwa sisi ni kuingiza katika mwisho kabisa wa kwamba safu.
>> Na mfano bora nina kwa kuwa ni kuingizwa aina.
Kama unakumbuka video wetu juu ya kuingizwa aina,
kuna mengi ya gharama zinazohusika katika kuwa
kuchukua vipengele, na kuhama yao nje ya njia na kifafa kitu
ndani ya katikati ya safu yako.
Arrays pia wanakabiliwa na mwingine tatizo, ambayo ni kutokubadilika.
Wakati sisi kutangaza safu, sisi kupata risasi moja katika hilo.
Sisi kupata cha kusema, nataka hii mambo mengi.
Inaweza kuwa 100, inaweza kuwa 1,000, inaweza
kuwa x ambapo x ni idadi kwamba mtumiaji alitupa katika haraka au kwa amri
mstari.
>> Lakini sisi tu kupata risasi moja saa hiyo, sisi hawapati kisha kusema lo, kwa kweli mimi
inahitajika 101, au mimi zinahitajika x pamoja 20.
Kuchelewa, tumekuwa tayari alitangaza safu, na kama tunataka kupata 101 au x
pamoja na 20, tuna kutangaza safu tofauti kabisa,
nakala mambo yote ya safu juu, na kisha tuna kutosha.
Na nini kama sisi ni makosa tena, nini kama sisi kweli haja 102, au x plus 40,
tuna kufanya hii tena.
Hivyo wao ni usiobadilika sana kwa resizing takwimu zetu,
lakini kama sisi kuchanganya pamoja baadhi ya mambo ya msingi kwamba tumekuwa tayari
kujifunza kuhusu kuyatumia na miundo, hasa kwa kutumia kumbukumbu ya nguvu
mgao kwa malloc, sisi unaweza kuweka vipande hayo pamoja
kujenga takwimu mpya structure-- a moja moja wanaohusishwa orodha tupate say--
ambayo inaruhusu sisi kukua na kuogopa mkusanyiko wa maadili
na hatutakuwa na nafasi yoyote kupita.
>> Hivyo tena, tunatoa wito wazo hili, wazo hili, orodha wanaohusishwa.
Hasa, katika video hii tuko kuzungumza juu ya orodha moja moja wanaohusishwa,
na kisha mwingine video tutaweza majadiliano orodha kuhusu mara mbili wanaohusishwa, ambayo
ni tu tofauti juu ya mandhari hapa.
Lakini orodha moja moja wanaohusishwa inakuwa na nodes,
nodes tu kuwa term-- abstract ni tu kitu mimi nina wito
hiyo ni aina ya muundo, kimsingi, mimi nina?
Tu kwenda kumwita node-- na hii node ina wanachama wawili, au mashamba mawili.
Ina data, kwa kawaida integer, tabia kuelea,
au inaweza kuwa baadhi ya data aina nyingine kwamba umefanya inavyoelezwa na aina def.
Na ina pointer nodi nyingine ya aina moja.
>> Hivyo tuna mambo mawili ndani ya nodi hii, data na pointer
nodi mwingine.
Na kama kuanza kupiga taswira hivyo, unaweza kufikiri juu yake
kama mlolongo wa nodes kwamba ni kushikamana pamoja.
Tuna nodi ya kwanza, ina data, na pointer
nodi pili, ambayo ina data, na pointer nodi ya tatu.
Na hivyo ndiyo sababu sisi kuiita orodha wanaohusishwa, wao ni wanaohusishwa pamoja.
>> Je, hii maalum muundo wa nodi kuangalia kama?
Naam, kama unakumbuka kutoka sehemu yetu juu ya kufafanua aina desturi, na aina def,
tunaweza kufafanua structure-- na aina kufafanua muundo kama hii.
tyepdef struct sllist, na kisha mimi nina kutumia thamani neno hapa kiholela
zinaonyesha aina yoyote data kweli.
Unaweza kupita kwenye integer au kuelea, unaweza kuwa na chochote unataka.
Ni si vikwazo kwa tu integers, au kitu kama hicho.
Hivyo thamani ya kitu holela tu Aina ya data, na kisha pointer
nodi nyingine ya aina moja.
>> Sasa, kuna samaki kidogo hapa na kufafanua muundo
wakati ni muundo binafsi rejea.
Mimi kuwa na muda jina kwa mfumo wangu.
Mwisho wa siku mimi wazi unataka simu yake
SLL nodi, hiyo ni hatimaye mpya jina sehemu ya aina yangu ufafanuzi,
lakini siwezi kutumia SLL nodi katikati ya hii.
Sababu ya kuwa, nina si umba aina aitwaye SLL nodi
mpaka mimi hit hatua hii ya mwisho hapa.
Hadi hatua hiyo, mimi kuwa na njia nyingine ya kutaja aina hii ya data.
>> Na hii ni kwa mujibu rejea aina data.
Yake; s aina ya data muundo ambayo ina data,
na pointer mwingine muundo wa aina moja.
Hivyo mimi haja ya kuwa na uwezo wa kutaja aina hii data angalau kwa muda,
hivyo kutoa ni muda jina la struct sllist
inaruhusu mimi kisha kusema nataka pointer na mwingine sllist struct,
nyota struct sllist, na kisha baada nimekuwa kukamilika ufafanuzi,
Mimi sasa wanaweza kupiga aina hii SLL nodi.
>> Hivyo ndiyo sababu unaweza kuona kuna jina la muda hapa,
lakini jina kudumu hapa.
Wakati mwingine unaweza kuona ufafanuzi wa muundo,
kwa mfano, kwamba si binafsi rejea, kwamba
hawana jina specifier hapa.
Ingekuwa tu kusema typedef struct, kufungua curly brace na kisha kufafanua.
Lakini kama wewe ni struct ni kwa mujibu rejea, kama hii ni moja ya,
unahitaji kutaja muda aina jina.
Lakini hatimaye, sasa kwamba tumefanya huu,
tunaweza tu kutaja nodi hiyo, vitengo hivi,
kama nodes SLL kwa madhumuni ya mapumziko ya video hii.
>> Haki wote, hivyo tunajua jinsi ya kujenga uhusiano orodha nodi.
Tunajua jinsi ya kufafanua wanaohusishwa orodha nodi.
Sasa, kama sisi ni kwenda kuanza kutumia yao ya kukusanya taarifa,
kuna wanandoa wa shughuli sisi wanapaswa kuelewa na kufanya kazi pamoja.
Tunahitaji kujua jinsi ya kujenga orodha wanaohusishwa nje ya hewa nyembamba.
Kama hakuna orodha tayari, tunataka kuanza moja.
Kwa hiyo, tunahitaji kuwa na uwezo kuunda orodha wanaohusishwa,
tunahitaji pengine kutafuta kupitia orodha kiungo
kupata kipengele sisi ni kuangalia kwa.
Tunahitaji kuwa na uwezo wa kuingiza mambo mapya katika orodha,
tunataka orodha yetu kuwa na uwezo wa kukua.
Na vile vile, tunataka kuwa na uwezo kufuta vitu kutoka orodha yetu,
tunataka orodha yetu kuwa na uwezo wa kuogopa.
Na mwishoni mwa yetu mipango, hasa
kama unakumbuka kwamba tuko dynamically kugawa kumbukumbu
kujenga orodha hizi kwa kawaida, tunataka bure yote hayo kumbukumbu
wakati sisi ni kosa kufanya kazi kwa hayo.
Na hivyo tunahitaji kuwa na uwezo wa kufuta nzima wanaohusishwa orodha katika moja kushindwa swoop.
Basi hebu kwenda kupitia baadhi ya shughuli hizo
na jinsi sisi tupate taswira yao, kuzungumza katika pseudocode kificho mahsusi.
Hivyo tunataka kujenga wanaohusishwa orodha, hivyo labda sisi
wanataka kufafanua kazi kwa mfano huu.
SLL nyota nodi, kujenga, na mimi nina kupita katika hoja moja, baadhi ya data holela
aina tena, baadhi ya data aina holela.
Lakini mimi nina returning-- kazi hii lazima kurudi kwangu pointer, kwa mmoja-
wanaohusishwa orodha nodi.
Tena, sisi ni kujaribu kujenga orodha wanaohusishwa nje ya hewa nyembamba,
hivyo mimi haja pointer kwamba orodha wakati mimi nina kufanyika.
>> Hivyo hatua zinazohusika hapa ni nini?
Naam, jambo la kwanza mimi nina kwenda kufanya ni dynamically
kutenga nafasi kwa nodi mpya.
Tena, sisi ni kujenga nje ya nyembamba hewa, hivyo tunahitaji malloc nafasi kwa ajili yake.
Na bila shaka, mara moja baada ya sisi malloc,
sisi daima kuangalia ili kuhakikisha kwamba yetu pointer hatukuwa kupata nyuma null.
Kwa sababu kama sisi kujaribu na staha pointer null,
tunakwenda kuteseka segfault na hatutaki hilo.
>> Kisha tunataka kujaza katika uwanja, tunataka initialize shamba thamani
na initialize uwanja ijayo.
Na kisha tunataka to-- hatimaye kama kazi mfano indicates-- tunataka
kurudi pointer SLL nodi.
Kwa hiyo kile kufanya hili kuangalia kama kuibua?
Naam, kwanza tunakwenda dynamically kutenga nafasi kwa mwezi SLL nodi,
hivyo sisi malloc-- hiyo ni Visual uwakilishi
ya nodi sisi tu kuundwa.
Na sisi kuangalia kuhakikisha siyo NULL katika kesi hiyo,
picha bila kuwa na umeonyesha juu kama ilikuwa null,
tunataka kuwa kukimbia nje ya kumbukumbu, hivyo sisi ni vizuri kwenda huko.
Hivyo sasa sisi ni juu ya hatua C, initialize shamba nodes thamani.
Naam, kulingana na kazi hii piga mimi nina kutumia hapa,
Inaonekana kama nataka kupita katika 6, hivyo mimi itabidi 6 katika uwanja thamani.
Sasa, initialize uwanja ijayo.
Naam, je, Mimi kwenda kufanya huko, hakuna kitu ijayo, haki,
hii ni kitu pekee katika orodha.
Basi nini jambo la pili katika orodha?
>> Ni lazima uhakika na kitu chochote, haki.
Kuna kitu kingine huko, ili kile ni dhana tunajua ya kwamba ni nothing--
kuyatumia kwa kitu?
Ni lazima labda tunataka kuweka pointer null huko,
na mimi itabidi kuwakilisha null pointer kama tu sanduku nyekundu,
hatuwezi kwenda yoyote zaidi.
Kama tutaweza kuona baadaye kidogo juu ya, tutakuwa na hatimaye minyororo
ya mishale ya kuunganisha hizi nodes pamoja,
lakini wakati kugonga nyekundu sanduku, hiyo ni null,
hatuwezi kwenda yoyote zaidi, hiyo ni mwisho wa orodha.
>> Na mwisho, sisi tu wanataka kurudi pointer nodi hii.
Hivyo tutaweza simu yake mpya, tena atarejea mpya
hivyo inaweza kutumika katika chochote kazi aliyeliumba.
Kwa hiyo, kuna sisi kwenda, Tumeunda mmoja- wanaohusishwa orodha nodi nje ya hewa nyembamba,
na sasa tuna orodha tunaweza kufanya kazi pamoja.
>> Sasa, hebu sema sisi tayari kuwa na mkufu kubwa,
na tunataka kupata kitu ndani yake.
Na tunataka kazi hiyo ni kwenda kurudi kweli au uongo, kulingana
kama kweli thamani lipo katika orodha hiyo.
Mfano kazi, au Tamko kwa kazi hiyo,
ili kuangalia kama hii bool kupata, na kisha tunataka kupitisha katika hoja mbili.
>> Kwanza, ni pointer sehemu ya kwanza ya orodha wanaohusishwa.
Hii ni kweli kitu utasikia Siku zote unataka kuweka wimbo wa,
na kwa kweli inaweza kuwa kitu ambacho wewe hata kuweka katika variable kimataifa.
Mara baada ya kujenga orodha, nanyi siku zote, siku zote
wanataka kuweka wimbo wa sana sehemu ya kwanza ya orodha.
Kwa njia hiyo unaweza kutaja wengine wote mambo kwa kufuata tu mlolongo,
bila ya kuwa na kuweka kuyatumia intact kwa kila kipengele moja.
Wewe tu haja ya kuweka wimbo wa kwanza moja ikiwa wao ni wote minyororo pamoja.
>> Na kisha Jambo la pili sisi ni kupita katika tena
ni kiholela some-- chochote data aina tuko
kuangalia kwa huko ni ndani ya hopefully moja ya nodes katika orodha.
Hivyo hatua ni nini?
Naam, jambo la kwanza sisi kufanya ni sisi kujenga transversal pointer
akizungumzia orodha kichwa.
Naam, kwa nini sisi kufanya hivyo, sisi tayari na pointer katika orodha kichwa,
kwa nini sio sisi tu hoja kwamba moja karibu?
Naam, kama mimi tu alisema, ni kweli muhimu kwetu
daima kuweka wimbo wa kipengele sana kwanza katika orodha.
Na hivyo ni kweli bora kujenga duplicate ya kwamba,
na kutumia kuweza kuzunguka hivyo sisi kamwe ajali kuondokana, au sisi daima
na pointer wakati fulani kwamba ni haki juu ya kipengele kwanza ya orodha.
Hivyo ni bora ya kujenga pili moja kwamba sisi kutumia kutoa hoja.
>> Kisha sisi tu kulinganisha kama shamba thamani katika nodi kwamba
ni nini sisi ni kutafuta, na kama ni si, tunakwenda nodi ijayo.
Na sisi kuendelea kufanya hivyo tena na tena, na tena,
mpaka sisi ama kupata kipengele, au sisi kugonga
NULL tumekuwa kufikiwa mwisho ya orodha na si huko.
Hii lazima hopefully kuwapigia kengele na wewe kama tu tafuta linear,
sisi ni tu kujinakilisha katika moja moja wanaohusishwa orodha muundo
badala ya kutumia safu ya kufanya hivyo.
>> Hivyo hapa ni mfano wa orodha moja moja wanaohusishwa.
Hii moja lina nodes tano, na tuna
pointer kichwa cha orodha, iitwayo orodha.
Jambo la kwanza tunataka kufanya ni tena, kujenga kwamba traversal pointer.
Hivyo tuna sasa kuyatumia mbili hatua hiyo kwa kitu kimoja.
>> Sasa, taarifa hapa pia, sikuwa na malloc nafasi yoyote kwa trav.
Mimi hakusema trav sawa na malloc kitu, kwamba nodi tayari ipo,
kwamba nafasi katika kumbukumbu tayari ipo.
Basi wote mimi nina kweli kufanya ni kujenga pointer mwingine kwa hayo.
Mimi si mallocing ziada nafasi, tu na sasa kuyatumia mbili
akizungumzia kitu kimoja.
>> Hivyo ni nini 2 Mimi nina kuangalia kwa?
Naam, hapana, hivyo badala mimi nina kwenda hoja kwa moja ijayo.
Hivyo kimsingi napenda kusema, trav sawa na trav ijayo.
Ni 3 nini mimi kutafuta, hakuna.
Hivyo mimi kuendelea kwenda kupitia mpaka hatimaye
kupata 6 ambayo ni nini mimi nina kuangalia kwa kuzingatia kazi ya wito
Nina juu huko, na hivyo mimi nina kufanyika.
>> Sasa, nini kama kipengele mimi nina kutafuta ni si katika orodha,
ni bado kwenda kufanya kazi?
Naam, taarifa kwamba orodha hapa ni subtly tofauti,
na hii ni kitu kingine kwamba ni muhimu kwa orodha wanaohusishwa,
huna kuhifadhi yao ili yoyote.
Unaweza kama unataka, lakini unaweza kuwa tayari niliona
kwamba sisi siyo kuweka wimbo wa nini idadi kipengele sisi ni katika.
>> Na hiyo ni aina ya biashara moja kwamba sisi kuwa na uhusiano orodha mistari arrays,
je, ni hatuna random kupata tena.
Hatuwezi tu kusema, nataka kwenda kipengele 0,
au kipengele 6 wa safu yangu, ambayo siwezi kufanya katika safu.
Siwezi kusema mimi nataka kwenda 0 kipengele, au kipengele 6,
au kipengele 25 ya orodha yangu wanaohusishwa, hakuna ripoti kuhusishwa na wao.
Na hivyo hana kweli jambo kama sisi kuhifadhi orodha yetu katika utaratibu.
Kama unataka wewe hakika wanaweza, lakini kuna
hakuna sababu kwa nini wanahitaji kuhifadhiwa ili yeyote.
Hivyo tena, hebu jaribu na kupata 6 katika orodha hii.
Naam, sisi kuanza saa mwanzo, hatuoni 6,
na kisha tunaendelea si kutafuta 6, mpaka sisi hatimaye kupata hapa.
Hivyo sasa hivi trav pointi nodi zenye 8, na sita ni si huko.
>> Hivyo hatua ya pili itakuwa kwenda pointer ijayo,
hivyo kusema trav sawa na trav ijayo.
Naam, trav ijayo, unahitajika kwa sanduku nyekundu huko, ni null.
Hivyo kuna mahali popote kwa kwenda, na hivyo katika hatua hii
tunaweza kuhitimisha kwamba tumekuwa kufikiwa mwisho wa orodha wanaohusishwa,
na 6 ni si huko.
Na ingekuwa irudishwe uongo katika kesi hii.
>> OK, ni jinsi gani sisi kuingiza mpya nodi katika orodha wanaohusishwa?
Hivyo tumekuwa na uwezo wa kujenga orodha wanaohusishwa bila ya kutarajia,
lakini sisi pengine wanataka kujenga mlolongo na si
kujenga rundo la orodha tofauti.
Tunataka kuwa na orodha moja ambayo ina rundo la nodes ndani yake,
si kundi la orodha na nodi moja.
Hivyo hatuwezi tu kuendelea kutumia Kujenga kazi sisi kuelezwa hapo awali, sasa sisi
wanataka kuingiza ndani orodha ambayo tayari zipo.
>> Hivyo kesi hiyo, tunakwenda kupita katika hoja mbili,
pointer kichwa cha kwamba wanaohusishwa orodha kwamba tunataka kuongeza.
Tena, kwamba ni kwa nini ni hivyo muhimu kwamba huwa
kuweka wimbo wa jambo hilo, kwa sababu ni njia pekee sisi kweli
na kwa kutaja orodha nzima ni tu kwa pointer kipengele kwanza.
Hivyo tunataka kupitisha katika pointer kwa kuwa kipengele kwanza,
na chochote thamani sisi wanataka kuongeza orodha.
Na hatimaye kazi hii ni kwenda na kurudi pointer
kwa mkuu mpya wa orodha wanaohusishwa.
>> Ni hatua zinazohusika hapa ni nini?
Naam, tu kama kwa kujenga, tunahitaji dynamically kutenga
nafasi kwa ajili ya nodi mpya, na kuangalia kufanya hakika sisi si kukimbia nje ya kumbukumbu, tena,
kwa sababu sisi ni kutumia malloc.
Kisha tunataka idadi na kuingiza nodi,
hivyo kuweka idadi, chochote val ni, ndani ya nodi.
Tunataka kuingiza nodi katika mwanzo wa orodha wanaohusishwa.
>> Kuna sababu ya kuwa mimi wanataka kufanya hivyo, na ni
inaweza kuwa na thamani ya kuchukua pili kutulia video hapa,
na kufikiri kuhusu nini napenda wanataka kuingiza mwanzoni mwa wanaohusishwa
orodha.
Tena, nilivyoeleza awali kwamba ni kweli haina
jambo kama sisi kuhifadhi katika yoyote ili, hivyo labda hiyo ni habari.
Na wewe aliona nini kitatokea kama sisi alitaka to-- au kutoka tu pili
iliyopita wakati tulipokuwa tunakwenda njia ya kutafuta wewe
naweza kuona nini kinaweza kutokea kama sisi walikuwa wakijaribu
kuingiza mwishoni mwa orodha.
Kwa sababu hatuna pointer hadi mwisho wa orodha.
>> Hivyo sababu hiyo napenda wanataka kuingiza mwanzoni,
ni kwa sababu siwezi kufanya hivyo mara moja.
Nina pointer mwanzoni, na tutaweza kuona hii katika Visual katika pili.
Lakini kama nataka kuingiza mwishoni, Nina kuanza mwanzoni,
traverse njia yote ya mwisho, na kisha upepo juu.
Hivyo kwamba itakuwa na maana kwamba kuingiza mwishoni mwa orodha
angekuwa o ya n operesheni, kurejea
kwa mjadala wetu wa Computational utata.
Ni d kuwa o ya n operesheni, ambapo kama orodha got kubwa zaidi, na kubwa zaidi,
na kubwa zaidi, kutakuwa na kuwa zaidi na vigumu zaidi upepo kitu
juu ya mwishoni.
Lakini mara nyingi ni kweli rahisi upepo kitu juu mwanzoni,
wewe daima katika mwanzo.
>> Na tutaweza kuona Visual ya hii tena.
Na kisha mara moja sisi ni kosa, kwa mara nyingine tumekuwa kuingizwa nodi mpya,
tunataka kurudi pointer wetu mkuu mpya wa orodha wanaohusishwa, ambayo
tangu sisi ni kuingiza katika mwanzo, kwa kweli kuwa
pointer nodi sisi tu kuundwa.
Hebu taswira hii, kwa sababu nadhani utakuwa msaada.
>> Hivyo hapa ni orodha yetu, lina ya mambo manne, nodi zenye 15,
ambayo inaelekeza katika nodi zenye 9, ambayo
anazungumzia nodi zenye 13, ambayo inaelekeza katika nodi zenye
10, ambayo ina null pointer kama pointer yake ya pili
hivyo hiyo ni mwisho wa orodha.
Hivyo tunataka kuingiza nodi mpya kwa thamani 12
mwanzoni mwa hii orodha, tunafanya nini?
Naam, kwanza sisi malloc nafasi kwa nodi, na kisha sisi kuweka 12 katika huko.
>> Hivyo sasa tumekuwa kufikiwa uamuzi hatua, sawa?
Sisi kuwa wanandoa wa kuyatumia kwamba tunaweza
hoja, ambayo mtu anatakiwa sisi hoja ya kwanza?
Tunapaswa kufanya 12 hatua kwa Mkuu mpya ya orodha
au udhuru kwangu, tunapaswa kufanya 12 uhakika na kichwa wa zamani wa orodha?
Au lazima sisi kusema kwamba orodha sasa huanza saa 12.
Kuna tofauti huko, na tutaangalia
nini kinatokea na wote katika pili.
>> Lakini hii inaongoza kwa mada kuu kwa sidebar,
ambayo ni kwamba moja ya mambo trickiest na orodha wanaohusishwa
ni kupanga kuyatumia katika mpangilio sahihi.
Kama hoja mambo nje ya utaratibu, unaweza kuishia ajali
orphaning wengine wa orodha.
Na hapa ni mfano wa jambo hilo.
Basi hebu kwenda na wazo of-- vizuri, tumekuwa tu kuundwa 12.
Tunajua 12 ni kwenda kuwa mkuu mpya wa orodha,
na hivyo kwa nini sio sisi tu hoja orodha pointer kwa uhakika pale.
>> OK, hivyo hiyo ni nzuri.
Hivyo sasa wapi 12 hatua ya pili?
I mean, kuibua tunaweza kuona kuwa ni uhakika na 15,
kama binadamu ni kweli wazi kwetu.
Ni kwa jinsi gani kompyuta kujua?
Hatuna chochote akizungumzia 15 tena, sawa?
>> Tumekuwa kupoteza uwezo wowote kwa kutaja 15.
Hatuwezi kusema mshale mpya sawa ijayo kitu, kuna kitu huko.
Kwa kweli, tumekuwa yatima mapumziko ya orodha
kwa kufanya hivyo, tumekuwa ajali kuvunjwa mlolongo.
Na sisi hakika hawataki kufanya hivyo.
>> Basi hebu kwenda nyuma na kujaribu tena.
Labda jambo la haki ya kufanya ni kuweka 12 ijayo pointer
kwa kichwa wa zamani wa orodha ya kwanza, kisha tunaweza kusonga orodha zaidi.
Na kwa kweli, kwamba ni mpangilio sahihi kwamba sisi
haja ya kufuata wakati tuko kufanya kazi na orodha moja moja wanaohusishwa.
Sisi siku zote wanataka kuungana kipengele mpya katika orodha,
kabla ya sisi kuchukua aina hiyo ya hatua muhimu ya mabadiliko
ambapo mkuu wa orodha wanaohusishwa ni.
Tena, hiyo ni jambo kama hilo la msingi, hatutaki kupoteza wimbo wa hayo.
>> Hivyo tunataka kuhakikisha kwamba kila kitu ni minyororo pamoja,
kabla ya kuendelea kuwa pointer.
Na hivyo hii itakuwa ni mpangilio sahihi, ambayo ni kuungana 12 kwa orodha,
kisha kusema kwamba orodha kuanza 12.
Kama sisi alisema orodha kuanza saa 12 na kisha walijaribu kuunganisha 12 kwa orodha,
tumekuwa tayari kuona nini kinatokea.
Tunapoteza orodha kwa makosa.
>> OK, hivyo jambo moja zaidi ya kuzungumzia.
Nini kama tunataka kujikwamua nzima wanaohusishwa orodha kwa mara moja?
Tena, sisi ni mallocing nafasi yote haya, na hivyo sisi
unahitaji huru ni wakati sisi ni kosa.
Hivyo sasa tunataka kufuta nzima wanaohusishwa orodha.
Naam, je, tunataka kufanya?
>> Kama tumekuwa kufikiwa pointer null, sisi unataka kuacha, vinginevyo, tu kufuta
wengine wa orodha na kisha bure me.
Kufuta wengine wa orodha, na kisha bure nodi ya sasa.
Je kwamba sauti kama, nini mbinu na sisi aliyesema
kuhusu awali gani kwamba sauti kama?
Kufuta kila mtu mwingine, basi kurudi na kufuta yangu.
>> Hiyo ni kujirudia, tumekuwa alifanya Tatizo kidogo kidogo,
sisi ni kusema kila mtu kufuta kingine, basi unaweza kufuta yangu.
Na zaidi chini ya barabara, kwamba nodi watasema, kufuta kila mtu mwingine.
Lakini hatimaye tutaweza kupata mahali ambapo orodha ni null,
na kwamba msingi wetu kesi.
>> Basi hebu tuangalie hii, na jinsi hii inaweza kufanya kazi.
Hivyo hapa ni orodha yetu, ni sawa orodha tulikuwa tu kuzungumza juu,
na kuna hatua.
Kuna mengi ya maandishi hapa, lakini hopefully taswira itasaidia.
>> Hivyo sisi have-- na mimi pia vunjwa up yetu muafaka stack mfano
kutoka sehemu yetu juu ya wito mwingi, na pengine yote haya
pamoja kuonyesha nini kinaendelea.
Hivyo hapa ni pseudocode kanuni zetu.
Kama sisi kufikia null pointer, kuacha, vinginevyo,
kufuta wengine wa orodha, kisha bure nodi ya sasa.
Hivyo sasa hivi, list-- pointer kwamba tuko
kupita katika kuharibu pointi 12.
12 si pointer null, hivyo sisi ni kwenda kufuta wengine wa orodha.
>> Kile ni kufuta sisi wengine waliohusika?
Vizuri, ina maana kufanya piga kuharibu, akisema
kuwa 15 ni mwanzo wa mapumziko ya orodha tunataka kuharibu.
Na hivyo wito kuharibu 12 ni aina ya juu ya umiliki.
Ni waliohifadhiwa huko, kusubiri kwa piga kuharibu 15, na kumaliza kazi yake.
>> Naam, 15 si pointer null, na hivyo ni kwenda kusema, sawa,
vizuri, kufuta wengine wa orodha.
Mapumziko ya orodha kuanza saa 9, na hivyo tutaweza tu
kusubiri mpaka kufuta yote mambo, kisha kurudi na kufuta yangu.
Naam 9 kwenda kusema, vizuri, Sina pointer null,
hivyo kufuta wengine orodha kutoka hapa.
Na hivyo kujaribu na kuharibu 13.
13 anasema, mimi si pointer null, kitu kimoja, unapita mume.
10 si pointer null, 10 ina pointer null,
lakini 10 si yenyewe null pointer sasa hivi,
na hivyo unapita mume pia.
>> Na sasa orodha pointi huko, kweli ingekuwa uhakika na some--
kama ningekuwa na nafasi zaidi katika picha, ingekuwa uhakika na baadhi ya nafasi random
kwamba hatujui ni nini.
Ni pointer null ingawa, orodha ni halisi sasa kuweka ni maadili null.
Ni akizungumzia haki ndani ya kwamba sanduku nyekundu.
Sisi kufikiwa pointer null, hivyo tunaweza kuacha, na sisi ni kosa.
>> Na hivyo sura kwamba zambarau ni now-- katika juu ya stack-- hiyo ni sura ya kazi,
lakini ni kosa.
Kama tumekuwa kufikiwa pointer null, kuacha.
Hatuwezi kufanya kitu chochote, sisi Huwezi bure pointer null,
hatukuwa malloc yoyote nafasi, na hivyo sisi ni kosa.
Hivyo kwamba sura kazi ni kuharibiwa, na sisi
resume-- sisi kuchukua ambapo sisi kushoto mbali na ujao juu moja, ambayo
ni hii rangi ya bluu sura hapa.
Kwa hiyo sisi kuchukua haki ambapo sisi kushoto mbali.
Sisi kufutwa mapumziko ya orodha tayari, hivyo sasa tuko
kwenda bure nodes sasa.
Hivyo sasa tunaweza bure nodi hii, na sasa tumekuwa kufikiwa mwisho wa kazi.
Na hivyo kuwa sura kazi ni kuharibiwa, na sisi kuchukua katika mwanga wa bluu moja.
>> Hivyo ni says-- nimekuwa tayari done-- kufuta wengine wa orodha, hivyo
bure nodi ya sasa.
Na sasa sura ya njano ni nyuma juu ya stack.
Na hivyo kama unaweza kuona, sisi ni sasa kuharibu orodha kutoka kulia kwenda kushoto.
>> Nini kingetokea, ingawa, kama sisi alikuwa amefanya mambo kwa njia sahihi?
Tu kama wakati sisi walijaribu kuongeza kipengele.
Kama sisi messed up mlolongo, kama hatukuwa kuungana kuyatumia
katika mpangilio sahihi, kama sisi tu huru kipengele kwanza,
kama sisi tu huru mkuu wa orodha, sasa sisi
hawana njia ya kutaja wengine wa orodha.
Na hivyo tunataka kuwa yatima kila kitu,
tungekuwa na nini aitwaye kumbukumbu kuvuja.
Kama unakumbuka kutoka sehemu yetu juu ya mgao wa nguvu kumbukumbu,
si kwamba ni jambo jema sana.
>> Hivyo kama nilivyosema, kuna ni shughuli kadhaa
kuwa tunahitaji kutumia kufanya kazi kwa wanaohusishwa orodha kwa ufanisi.
Na unaweza kuwa niliona mimi liliondolewa moja, kufuta kipengele moja kutoka wanaohusishwa
orodha.
Sababu mimi kwamba ni ni kweli aina ya
gumu kufikiri kuhusu jinsi ya kufuta kipengele moja kutoka moja moja
wanaohusishwa orodha.
Tunahitaji kuwa na uwezo wa ruka juu kitu katika orodha, ambayo
ina maana sisi kupata point-- sisi unataka kufuta node-- hii
lakini ili kufanya hivyo sisi si kupoteza taarifa yoyote,
tunahitaji kuungana huu nodi hapa, hapa.
>> Hivyo mimi pengine alifanya hivyo vibaya kutokana na mtazamo Visual.
Hivyo sisi ni mwanzoni mwa yetu orodha, sisi ni kuendelea kupitia,
tunataka kufuta nodi hii.
Kama sisi tu kufuta, tumekuwa kuvunjwa mlolongo.
Nodi hii hapa hapa inahusu kila kitu kingine,
ina mlolongo kutoka hapa juu ya nje.
>> Kwa hiyo kile tunahitaji kufanya kweli baada ya sisi kupata hatua hii,
ni tunahitaji kurudi nyuma moja, na kuungana nodi hii juu ya nodi hii,
ili tuweze kisha kufuta moja katikati.
Lakini orodha moja moja wanaohusishwa hawana kutupatia njia ya kwenda nyuma.
Kwa hiyo, tunahitaji ama kuweka kuyatumia mbili, na hoja yao
aina ya hatua mbali, moja nyuma ya wengine kama sisi kwenda, au kupata kwa uhakika
na kisha kutuma pointer mwingine kwa njia ya.
Na kama unaweza kuona, ni wanaweza kupata messy kidogo.
Kwa bahati nzuri, tuna njia nyingine ya kutatua kwamba,
wakati sisi majadiliano juu ya orodha doubly wanaohusishwa.
>> Mimi nina Doug Lloyd, hii ni CS50.