[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.